Указатель с тегами

редактировать

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

Содержание
  • 1 Сворачивание тегов в указатель
  • 2 Примеры
  • 3 Нулевой или выровненный указатель
  • 4 Примеры
    • 4.1 Пример 1
    • 4.2 Пример 2
    • 4.3 Пример 3
  • 5 Преимущества
  • 6 Недостатки
  • 7 Ссылки
Сворачивание тегов в указатель

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

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

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

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

Примеры

Важным примером использования тегированных указателей является среда выполнения 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 optional_return_a_value (int * optional_return_value_pointer) {/ *... * / int value_to_return = 1; / * это не NULL? (обратите внимание, что NULL, логическая ложь и ноль сравниваются в C одинаково) * / if (optional_return_value_pointer) / * если да, используйте его для передачи значения вызывающей функции * / * optional_return_value_pointer = value_to_return; / * в противном случае указатель никогда не разыменовывается * /}

Пример 2

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

#define SENTINEL sentinel_s node_t sentinel_s; void do_something_to_a_node (node_t * p) {if (NULL == p) / * делать что-то * / else if (SENTINEL == p) / * делать что-то еще * / else / * рассматривать p как действительный указатель на узел * / }

Пример 3

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

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

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

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

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

Недостатки

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

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

Ссылки
Последняя правка сделана 2021-06-09 07:31:06
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте