Markierter Zeiger

In der Informatik ist ein getaggter Zeiger ein Zeiger (konkret eine Speicheradresse ) mit zugehörigen Zusatzdaten, wie beispielsweise einem Indirektionsbit oder einem Referenzzähler . Diese Zusatzdaten werden oft in den Zeiger „eingefaltet“, d. h. direkt in den Daten gespeichert, die die Adresse repräsentieren, wodurch bestimmte Eigenschaften der Speicheradressierung ausgenutzt werden. Der Name stammt von Systemen mit „ Tagged Architecture “, die auf Hardwareebene Bits reservierten, um die Bedeutung jedes Wortes anzugeben. Die Zusatzdaten werden als „Tag“ oder „Tags“ bezeichnet, wobei „Tag“ streng genommen Daten bezeichnet, die einen Typ spezifizieren, und nicht andere Daten. Die Verwendung des Begriffs „getaggter Zeiger“ ist jedoch weit verbreitet.

Es gibt verschiedene Techniken, um Tags in einen Zeiger zu falten. ^{[ 1 ]}

Die meisten Architekturen sind byteadressierbar (die kleinste adressierbare Einheit ist ein Byte), aber bestimmte Datentypen werden oft an ihrer Größe ausgerichtet , häufig an einem Wort oder einem Vielfachen davon. Diese Diskrepanz führt dazu, dass einige der niedrigstwertigen Bits des Zeigers ungenutzt bleiben. Diese können für Tags verwendet werden – meist als Bitfeld (jedes Bit ein separater Tag) –, solange der Code, der den Zeiger verwendet, diese Bits vor dem Speicherzugriff maskiert . Beispiel: Auf einer 32-Bit -Architektur (sowohl für Adressen als auch für Wortgröße) entspricht ein Wort 32 Bit = 4 Byte, daher sind wortausgerichtete Adressen immer ein Vielfaches von 4 und enden mit 00, wodurch die letzten 2 Bits verfügbar sind. Auf einer 64-Bit -Architektur hingegen entspricht ein Wort 64 Bit = 8 Byte, daher enden wortausgerichtete Adressen mit 000, wodurch die letzten 3 Bits verfügbar sind. Wenn Daten an einem Vielfachen der Wortgröße ausgerichtet sind, stehen weitere Bits zur Verfügung. Bei wortadressierbaren Architekturen bleiben bei wortausgerichteten Daten keine Bits übrig, da es keine Diskrepanz zwischen Ausrichtung und Adressierung gibt. Bei Daten, die an einem Vielfachen der Wortgröße ausgerichtet sind, ist dies jedoch der Fall.

Conversely, in some operating systems, virtual addresses are narrower than the overall architecture width, which leaves the most significant bits available for tags; this can be combined with the previous technique in case of aligned addresses. This is particularly the case on 64-bit architectures, as 64 bits of address space are far above the data requirements of all but the largest applications, and thus many practical 64-bit processors have narrower addresses. Note that the virtual address width may be narrower than the physical address width, which in turn may be narrower than the architecture width; for tagging of pointers in user space, the virtual address space provided by the operating system (in turn provided by the memory management unit) is the relevant width. In fact, some processors specifically forbid use of such tagged pointers at the processor level, notably x86-64, which requires the use of canonical form addresses by the operating system, with most significant bits all 0s or all 1s.

Lastly, the virtual memory system in most modern operating systems reserves a block of logical memory around address 0 as unusable. This means that, for example, a pointer to 0 is never a valid pointer and can be used as a special null pointer value. Unlike the previously mentioned techniques, this only allows a single special pointer value, not extra data for pointers generally.

One of the earliest examples of hardware support for tagged pointers in a commercial platform was the IBM System/38.^[2] IBM later added tagged pointer support to the PowerPC architecture to support the IBM i operating system, which is an evolution of the System/38 platform.^[3]

A significant example of the use of tagged pointers is the Objective-C runtime on iOS 7 on ARM64, notably used on the iPhone 5S. In iOS 7, virtual addresses only contain 33 bits of address information but are 64-bits long leaving 31 bits for tags. Objective-C class pointers are 8-byte aligned freeing up an additional 3 bits of address space, and the tag fields are used for many purposes, such as storing a reference count and whether the object has a destructor.^[4][5]

Frühe Versionen von macOS verwendeten getaggte Adressen, sogenannte Handles, um Referenzen auf Datenobjekte zu speichern. Die höherwertigen Bits der Adresse gaben an, ob das Datenobjekt gesperrt, löschbar bzw. aus einer Ressourcendatei stammte. Dies führte zu Kompatibilitätsproblemen, als die macOS-Adressierung in System 7 von 24 Bit auf 32 Bit erweitert wurde. ^{[ 6 ]}

Die Verwendung von Null als Nullzeiger ist weit verbreitet, und viele Programmiersprachen (wie Ada ) nutzen dieses Verhalten explizit. Theoretisch könnten auch andere Werte in einem vom Betriebssystem reservierten Speicherbereich verwendet werden, um andere Zustände als einen Nullzeiger zu kennzeichnen. Diese Verwendungen scheinen jedoch selten zu sein, möglicherweise weil sie bestenfalls nicht portabel sind . Es gilt allgemein als Standard in der Softwareentwicklung, dass Programmierer, wenn ein spezieller, von Null verschiedener Zeigerwert benötigt wird (z. B. ein Sentinel in bestimmten Datenstrukturen ), diesen explizit bereitstellen sollten.

Die Nutzung der Ausrichtung von Zeigern bietet mehr Flexibilität als Nullzeiger/Sentinel-Zeiger, da Zeiger mit Informationen über den Datentyp, auf den sie zeigen, die Zugriffsbedingungen oder ähnliche Informationen über ihre Verwendung versehen werden können. Diese Informationen können jedem gültigen Zeiger beigefügt werden. Im Gegensatz dazu bieten Nullzeiger/Sentinel-Zeiger nur eine begrenzte Anzahl von Werten, die sich von gültigen Zeigern unterscheiden.

In einer getaggten Architektur ist eine bestimmte Anzahl von Bits in jedem Speicherwort als Tag reserviert. Getaggte Architekturen, wie beispielsweise Lisp-Maschinen , verfügen häufig über Hardwareunterstützung für die Interpretation und Verarbeitung getaggter Zeiger.

Die GNU libcmalloc() bietet 8-Byte-ausgerichtete Speicheradressen für 32-Bit-Plattformen und 16-Byte-Ausrichtung für 64-Bit-Plattformen. ^{[ 7 ]} Größere Ausrichtungswerte können mit erreicht werden posix_memalign(). ^{[ 8 ]}

Im folgenden C-Code wird der Wert Null verwendet, um einen Nullzeiger anzuzeigen:

void optional_return_a_value ( int * optional_return_value_pointer ) { /* ... */ int value_to_return = 1 ;/* Ist es nicht NULL? (Beachte, dass NULL, logisch falsch und Null in C gleichwertig sind.) */ if ( optional_return_value_pointer ) /* Falls ja, verwende ihn, um einen Wert an die aufrufende Funktion zu übergeben. */ * optional_return_value_pointer = value_to_return ;/* andernfalls wird der Zeiger nie dereferenziert */ }

Hier hat der Programmierer eine globale Variable bereitgestellt, deren Adresse dann als Wächter verwendet wird:

#define SENTINEL &sentinel_snode_t sentinel_s ;void do_something_to_a_node ( node_t * p ) { if ( NULL == p ) /* etwas tun */ else if ( SENTINEL == p ) /* etwas anderes tun */ else /* p als gültigen Zeiger auf einen Knoten behandeln */ }

Angenommen, wir haben eine Datenstruktur table_entry, die immer an einer 16-Byte-Grenze ausgerichtet ist. Das heißt, die vier niedrigstwertigen Bits der Adresse eines Tabelleneintrags sind immer 0 ( 2⁴ = 16 ). Wir könnten diese vier Bits verwenden, um den Tabelleneintrag mit zusätzlichen Informationen zu versehen. Beispielsweise könnte Bit 0 „schreibgeschützt“ bedeuten, Bit 1 ^„ geändert“ (der Tabelleneintrag muss aktualisiert werden) usw.

Wenn Zeiger 16-Bit-Werte sind, dann gilt:

• 0x3421ist ein schreibgeschützter Zeiger auf die table_entryAdresse0x3420
• 0xf472ist ein Zeiger auf eine geänderte table_entryAdresse0xf470

Der größte Vorteil von getaggten Zeigern besteht darin, dass sie weniger Speicherplatz benötigen als ein Zeiger mit einem separaten Tag-Feld. Dies ist besonders wichtig, wenn ein Zeiger der Rückgabewert einer Funktion ist . Auch bei großen Zeigertabellen kann dies von Bedeutung sein.

Ein subtilerer Vorteil besteht darin, dass durch das Speichern eines Tags am selben Ort wie der Zeiger die Atomarität einer Operation, die sowohl den Zeiger als auch seinen Tag aktualisiert, oft ohne externe Synchronisierungsmechanismen gewährleistet werden kann . Dies kann insbesondere bei Betriebssystemen einen enormen Leistungszuwachs bedeuten.

Getaggte Zeiger weisen ähnliche Schwierigkeiten wie XOR-verkettete Listen auf , wenn auch in geringerem Maße. Beispielsweise können nicht alle Debugger getaggten Zeigern korrekt folgen; dies stellt jedoch kein Problem für einen Debugger dar, der speziell für die Verwendung mit getaggten Zeigern entwickelt wurde.

Die Verwendung von Null zur Darstellung eines Nullzeigers hat diese Nachteile nicht: Sie ist weit verbreitet, die meisten Programmiersprachen behandeln Null als speziellen Nullwert, und ihre Robustheit hat sich umfassend bewährt. Eine Ausnahme bildet die Art und Weise, wie Null an der Überladungsauflösung in C++ beteiligt ist, wo Null als Ganzzahl und nicht als Zeiger behandelt wird; aus diesem Grund wird der spezielle Wert ` nullptr` der Ganzzahl Null vorgezogen. Bei getaggten Zeigern wird Null jedoch üblicherweise nicht zur Darstellung von Nullzeigern verwendet.