Тегированный указатель - Tagged pointer

В информатике , A меченый указатель является указателем (конкретно адрес памяти ) с дополнительными данными , связанными с ним, такими как бит косвенного или счетчик ссылок . Эти дополнительные данные часто «свернуты» в указатель, то есть хранятся внутри данных, представляющих адрес, с использованием определенных свойств адресации памяти. Название происходит от систем с « тегированной архитектурой », в которых на аппаратном уровне зарезервированы биты для обозначения значения каждого слова; дополнительные данные называются «тегом» или «тегами», хотя, строго говоря, «тег» относится к данным, определяющим тип, а не к другим данным; однако использование «помеченного указателя» повсеместно.

Складывание тегов в указатель

Существуют различные методы сворачивания тегов в указатель.

Большинство архитектур имеют байтовую адресацию (наименьшая адресуемая единица - байт), но определенные типы данных часто будут выровнены по размеру данных, часто по слову или кратному размеру . Это несоответствие оставляет неиспользованными несколько наименее значимых битов указателя, которые могут использоваться для тегов - чаще всего как битовое поле (каждый бит - отдельный тег) - до тех пор, пока код, который использует указатель, маскирует эти биты перед доступом к объем памяти. Например, в 32-битной архитектуре (как для адресов, так и для размера слова) слово составляет 32 бита = 4 байта, поэтому выровненные по словам адреса всегда кратны 4, следовательно, заканчиваются на 00, оставляя последние 2 бита доступными; в то время как в 64-битной архитектуре слово имеет размер 64 бита = 8 байтов, поэтому адреса с выравниванием по словам заканчиваются на 000, оставляя последние 3 бита доступными. В случаях, когда данные выровнены по размеру, кратному размеру слова, доступны дополнительные биты. В случае архитектур с адресацией по словам данные, выровненные по словам, не оставляют доступных битов, поскольку нет расхождений между выравниванием и адресацией, но данные, выровненные по размеру слова, остаются.

И наоборот, в некоторых операционных системах виртуальные адреса уже, чем общая ширина архитектуры, поэтому наиболее значимые биты остаются доступными для тегов; это можно комбинировать с предыдущей техникой в ​​случае выровненных адресов. Это особенно характерно для 64-битных архитектур, поскольку 64-битное адресное пространство намного превышает требования к данным всех приложений, кроме самых крупных, и поэтому многие практические 64-битные процессоры имеют более узкие адреса. Обратите внимание, что ширина виртуального адреса может быть уже, чем ширина физического адреса , которая, в свою очередь, может быть уже ширины архитектуры; для маркировки указателей в пользовательском пространстве соответствующей шириной является виртуальное адресное пространство, предоставляемое операционной системой (в свою очередь, предоставляемое блоком управления памятью ). Фактически, некоторые процессоры специально запрещают использование таких помеченных указателей на уровне процессора, особенно x86-64 , что требует использования операционной системой адресов канонической формы , в которых наиболее значимые биты содержат все нули или все единицы.

Наконец, система виртуальной памяти в большинстве современных операционных систем резервирует блок логической памяти около адреса 0 как неиспользуемый. Это означает, что, например, указатель на 0 никогда не является допустимым указателем и может использоваться как специальное значение нулевого указателя . В отличие от ранее упомянутых методов, это позволяет использовать только одно специальное значение указателя, а не дополнительные данные для указателей в целом.

Примеры

Одним из первых примеров аппаратной поддержки тегированных указателей на коммерческой платформе была IBM System / 38 . Позднее IBM добавила поддержку тегированных указателей в архитектуру PowerPC для поддержки операционной системы IBM i , которая является развитием платформы System / 38.

Важным примером использования тегированных указателей является среда выполнения Objective-C в iOS 7 на ARM64 , особенно используемая на iPhone 5S . В iOS 7 виртуальные адреса составляют 33 бита (с выравниванием по байтам), поэтому адреса с выравниванием по словам используют только 30 бит, оставляя 3 бита для тегов. Указатели классов Objective-C выровнены по словам, а поля тегов используются для многих целей, таких как хранение счетчика ссылок и наличия у объекта деструктора .

Ранние версии MacOS использовали тегированные адреса, называемые дескрипторами, для хранения ссылок на объекты данных. Старшие биты адреса указывали, был ли объект данных заблокирован, очищен и / или возник из файла ресурсов соответственно. Это вызвало проблемы совместимости, когда адресация MacOS увеличилась с 24 до 32 бит в Системе 7.

Нулевой или выровненный указатель

Использование нуля для представления нулевого указателя чрезвычайно распространено, поскольку многие языки программирования (например, Ada ) явно полагаются на это поведение. Теоретически другие значения в блоке логической памяти, зарезервированном операционной системой, могут использоваться для обозначения условий, отличных от нулевого указателя, но такое использование кажется редким, возможно, потому, что они в лучшем случае непереносимы . Общепринятая практика в разработке программного обеспечения заключается в том, что если требуется специальное значение указателя, отличное от нуля (например, сигнальное устройство в определенных структурах данных ), программист должен явно указать его.

Использование преимущества выравнивания указателей обеспечивает большую гибкость, чем нулевые указатели / индикаторы, поскольку позволяет помечать указатели информацией о типе данных, на которые они указывают, условиях, при которых к ним можно получить доступ, или другой аналогичной информации об использовании указателя. Эта информация может быть предоставлена ​​вместе с каждым действительным указателем. Напротив, нулевые указатели / индикаторы предоставляют только конечное число помеченных значений, отличных от действительных указателей.

В архитектуре с тегами некоторое количество битов в каждом слове памяти зарезервировано для работы в качестве тега. Тегированные архитектуры, такие как машины на Лиспе , часто имеют аппаратную поддержку для интерпретации и обработки тегированных указателей.

GNU libc malloc() предоставляет 8-байтовые выровненные адреса памяти для 32-битных платформ и 16-байтовые выравнивания для 64-битных платформ. Большие значения выравнивания можно получить с помощью posix_memalign() .

Примеры

Пример 1

В следующем коде C нулевое значение используется для обозначения нулевого указателя: 

void optionally_return_a_value (int* optional_return_value_pointer) {
  /* ... */
  int value_to_return = 1;

  /* is it non-NULL? (note that NULL, logical false, and zero compare equally in C) */
  if (optional_return_value_pointer)
    /* if so, use it to pass a value to the calling function */
    *optional_return_value_pointer = value_to_return;

  /* otherwise, the pointer is never dereferenced */
}

Пример 2

Здесь программист предоставил глобальную переменную, адрес которой затем используется в качестве дозорного: 

#define SENTINEL &sentinel_s

node_t sentinel_s;

void do_something_to_a_node (node_t * p) {
  if (NULL == p)
    /* do something */
  else if (SENTINEL == p)
    /* do something else */
  else
    /* treat p as a valid pointer to a node */
}

Пример 3

Предположим, у нас есть структура данных, table_entry которая всегда выровнена по границе 16 байт. Другими словами, 4 младших бита адреса записи таблицы всегда равны 0 ( 2 4 = 16 ). Мы могли бы использовать эти 4 бита, чтобы пометить запись в таблице дополнительной информацией. Например, бит 0 может означать только чтение, бит 1 может означать грязный (необходимо обновить запись в таблице) и так далее.

Если указатели являются 16-битными значениями, то:

  • 0x3421 доступный только для чтения указатель table_entry на адрес 0x3420
  • 0xf472 указатель на грязный table_entry по адресу 0xf470

Преимущества

Основное преимущество помеченных указателей заключается в том, что они занимают меньше места, чем указатель вместе с отдельным полем тега. Это может быть особенно важно, когда указатель является значением, возвращаемым функцией . Это также может быть важно в больших таблицах указателей.

Более тонкое преимущество состоит в том, что, сохраняя тег в том же месте, что и указатель, часто можно гарантировать атомарность операции, которая обновляет как указатель, так и его тег без внешних механизмов синхронизации . Это может быть чрезвычайно большим приростом производительности, особенно в операционных системах.

Недостатки

Указатели с тегами имеют те же трудности, что и связанные списки xor , хотя и в меньшей степени. Например, не все отладчики смогут правильно отслеживать помеченные указатели; однако это не проблема для отладчика, который разработан с учетом тегированных указателей.

Использование нуля для представления нулевого указателя не страдает этими недостатками: оно широко распространено, большинство языков программирования рассматривают ноль как особое нулевое значение, и это полностью доказало свою надежность. Исключением является то, как ноль участвует в разрешении перегрузки в C ++, где ноль обрабатывается как целое число, а не как указатель; по этой причине специальное значение nullptr предпочтительнее целого нуля. Однако с помеченными указателями нули обычно не используются для представления нулевых указателей.

Рекомендации