Теговый указатель

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

Сворачивание тегов в указатель

Существуют различные методы свертывания тегов в указатель. ^[1]^{[ ненадежный источник? ]}

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

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

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

Примеры

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

Ярким примером использования помеченных указателей является среда выполнения Objective-C в iOS 7 на ARM64 , особенно используемая на iPhone 5S . В iOS 7 виртуальные адреса содержат только 33 бита адресной информации, но имеют длину 64 бита, оставляя 31 бит для тегов. Указатели классов Objective-C выравниваются по 8 байтам, что освобождает дополнительные 3 бита адресного пространства, а поля тегов используются для многих целей, например для хранения счетчика ссылок и определения наличия у объекта деструктора . ^[4]^[5]

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

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

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

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

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

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

Примеры

Пример 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 ( $24 = 16$ ). Мы могли бы использовать эти 4 бита, чтобы пометить запись таблицы дополнительной информацией. Например, бит 0 может означать только чтение, бит 1 может означать «грязный» (необходимо обновить запись таблицы) и т. д.

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

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

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

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

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

Недостатки

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

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

Ссылки

^ Пятничные вопросы и ответы, 27 июля 2012 г.: Давайте создадим указатели с тегами , Майк Эш.
^ Леви, Генри М. (1984). «IBM System/38» (PDF) . Компьютерные системы, основанные на возможностях . Цифровая пресса. ISBN 0-932376-22-3 .
^ Фрэнк Г. Солтис (1997). Внутри AS/400, второе издание . Дьюк Пресс. ISBN 978-1882419661 .
^ Пятничные вопросы и ответы, 27 сентября 2013 г.: ARM64 и вы , Майк Эш.
^ [объяснение объекта]: isa без указателя
^ Брикнелл, К.Дж. Macintosh C: Руководство для любителей по программированию Mac OS на C.
^ «Примеры Malloc» . Библиотека GNU C. Проверено 5 сентября 2018 г.
^ posix_memalign(3) – Linux программиста Руководство – Библиотечные функции

[1] Пятничные вопросы и ответы, 27 июля 2012 г.: Давайте создадим указатели с тегами , Майк Эш.

[2] Леви, Генри М. (1984). «IBM System/38» (PDF) . Компьютерные системы, основанные на возможностях . Цифровая пресса. ISBN 0-932376-22-3 .

[inside-as400-3] Фрэнк Г. Солтис (1997). Внутри AS/400, второе издание . Дьюк Пресс. ISBN 978-1882419661 .

[mikeash2013097-4] Пятничные вопросы и ответы, 27 сентября 2013 г.: ARM64 и вы , Майк Эш.

[gregparker20130924-5] [объяснение объекта]: isa без указателя

[6] Брикнелл, К.Дж. Macintosh C: Руководство для любителей по программированию Mac OS на C.

[7] «Примеры Malloc» . Библиотека GNU C. Проверено 5 сентября 2018 г.

[8] posix_memalign(3) – Linux программиста Руководство – Библиотечные функции

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]