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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Примеры

Пример 1

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

пустота optionally_return_a_value (int* optional_return_value_pointer) {  /* ... */  int value_to_return = 1;  / * это не NULL? (обратите внимание, что NULL, логическая ложь и ноль сравниваются в C одинаково) * /  если (optional_return_value_pointer)    / * если это так, используйте его для передачи значения вызывающей функции * /    *optional_return_value_pointer = value_to_return;  / * в противном случае указатель никогда не разыменовывается * /}

Пример 2

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

#define SENTINEL & sentinel_snode_t sentinel_s;пустота do_something_to_a_node (node_t * п) {  если (НОЛЬ == п)    /* сделай что-нибудь */  еще если (SENTINEL == п)    / * делаем что-нибудь еще * /  еще    / * рассматривать p как действительный указатель на узел * /}

Пример 3

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

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

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

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

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

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

Недостатки

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

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

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

1. Пятница, вопросы и ответы, 27 июля 2012 г .: Давайте создадим указатели с тегами, Майк Эш
2. Пятница, вопросы и ответы, 27 сентября 2013 г .: ARM64 и вы, Майк Эш
3. [объяснение objc]: isa без указателя
4. Брикнелл, К. Дж. Macintosh C: Руководство для любителей по программированию Mac OS на C.
5. "Примеры Malloc". Библиотека GNU C. Получено 5 сентября 2018.
6. posix_memalign (3) – Linux Программиста Руководство - Библиотечные функции