В информатике маркированный указатель — это указатель (конкретно адрес памяти ) с дополнительными данными, связанными с ним, такими как бит косвенности или счетчик ссылок . Эти дополнительные данные часто «сворачиваются» в указатель, то есть хранятся в данных, представляющих адрес, используя определенные свойства адресации памяти. Название происходит от систем « маркированной архитектуры », которые резервируют биты на аппаратном уровне для указания значимости каждого слова; дополнительные данные называются «тегом» или «тегами», хотя, строго говоря, «тег» относится к данным, указывающим тип , а не к другим данным; однако использование «маркированного указателя» является повсеместным.
Существуют различные методы сворачивания тегов в указатель. [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 использовали тегированные адреса, называемые Handles, для хранения ссылок на объекты данных. Старшие биты адреса указывали, был ли объект данных заблокирован, очищаем и/или произошел из файла ресурсов, соответственно. Это вызвало проблемы совместимости, когда адресация macOS увеличилась с 24 до 32 бит в System 7. [6]
Использование нуля для представления нулевого указателя чрезвычайно распространено, и многие языки программирования (например, Ada ) явно полагаются на это поведение. Теоретически, другие значения в зарезервированном операционной системой блоке логической памяти могут использоваться для обозначения условий, отличных от нулевого указателя, но такие случаи использования, по-видимому, редки, возможно, потому, что они в лучшем случае непереносимы . Общепринятой практикой в разработке программного обеспечения является то, что если требуется особое значение указателя, отличное от нуля (например, контрольная точка в определенных структурах данных ), программист должен явно предусмотреть его.
Использование выравнивания указателей обеспечивает большую гибкость, чем нулевые указатели/сигнализаторы, поскольку позволяет помечать указатели информацией о типе данных, на которые они указывают, условиях, при которых к ним можно получить доступ, или другой подобной информацией об использовании указателя. Эта информация может быть предоставлена вместе с каждым допустимым указателем. Напротив, нулевые указатели/сигнализаторы предоставляют только конечное число помеченных значений, отличных от допустимых указателей.
В архитектуре с тегами ряд битов в каждом слове памяти зарезервирован для работы в качестве тега. Архитектуры с тегами, такие как машины Lisp , часто имеют аппаратную поддержку для интерпретации и обработки указателей с тегами.
GNU libc malloc() обеспечивает 8-байтовое выравнивание адресов памяти для 32-битных платформ и 16-байтовое выравнивание для 64-битных платформ. [7] Большие значения выравнивания можно получить с помощью posix_memalign(). [8]
В следующем коде на языке C значение нуля используется для обозначения нулевого указателя:
void Optionally_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 ; /* в противном случае указатель никогда не разыменовывается */ }Здесь программист предоставил глобальную переменную, адрес которой затем используется в качестве контрольной точки:
#define SENTINEL &sentinel_snode_t sentinel_s ; void do_something_to_a_node ( node_t * p ) { if ( NULL == p ) /* сделать что-то */ else if ( SENTINEL == p ) /* сделать что-то еще */ else /* рассматривать p как допустимый указатель на узел */ } Предположим, у нас есть структура данных table_entry, которая всегда выровнена по границе 16 байт. Другими словами, наименее значимые 4 бита адреса записи таблицы всегда равны 0 ( 2 4 = 16 ). Мы могли бы использовать эти 4 бита, чтобы пометить запись таблицы дополнительной информацией. Например, бит 0 может означать только чтение, бит 1 может означать грязный (запись таблицы необходимо обновить) и т. д.
Если указатели представляют собой 16-битные значения, то:
0x3421является указателем только для чтения на table_entryадрес at0x34200xf472является указателем на грязный table_entryадрес0xf470Главное преимущество тегированных указателей в том, что они занимают меньше места, чем указатель вместе с отдельным полем тега. Это может быть особенно важно, когда указатель является возвращаемым значением из функции . Это также может быть важно в больших таблицах указателей.
Более тонкое преимущество заключается в том, что, сохраняя тег в том же месте, что и указатель, часто можно гарантировать атомарность операции, которая обновляет как указатель, так и его тег без внешних механизмов синхронизации . [ необходимо дополнительное объяснение ] Это может дать чрезвычайно большой прирост производительности, особенно в операционных системах.
Указатели с тегами имеют некоторые из тех же трудностей, что и списки с xor-связями , хотя и в меньшей степени. Например, не все отладчики смогут правильно следовать указателям с тегами; однако это не проблема для отладчика, который разработан с учетом указателей с тегами.
Использование нуля для представления нулевого указателя не страдает от этих недостатков: оно распространено, большинство языков программирования рассматривают ноль как особое значение null, и оно полностью доказало свою надежность. Исключением является способ, которым ноль участвует в разрешении перегрузки в C++, где ноль рассматривается как целое число, а не указатель; по этой причине специальное значение nullptr предпочтительнее целого нуля. Однако с тегированными указателями нули обычно не используются для представления нулевых указателей.