Tagged pointer
In
Folding tags into the pointer
There are various techniques for folding tags into a pointer.[1][unreliable source?]
Most architectures are
Conversely, in some operating systems,
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.
Examples
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
Early versions of macOS used tagged addresses called Handles to store references to data objects. The high bits of the address indicated whether the data object was locked, purgeable, and/or originated from a resource file, respectively. This caused compatibility problems, when macOS addressing advanced from 24 bits to 32 bits in System 7.[6]
Null versus aligned pointer
Use of zero to represent a null pointer is extremely common, with many programming languages (such as
Taking advantage of the alignment of pointers provides more flexibility than null pointers/sentinels because it allows pointers to be tagged with information about the type of data pointed to, conditions under which it may be accessed, or other similar information about the pointer's use. This information can be provided along with every valid pointer. In contrast, null pointers/sentinels provide only a finite number of tagged values distinct from valid pointers.
In a tagged architecture, a number of bits in every word of memory are reserved to act as a tag. Tagged architectures, such as the Lisp machines, often have hardware support for interpreting and processing tagged pointers.
malloc()
provides 8-byte aligned memory addresses for 32-bit platforms, and 16-byte alignment for 64-bit platforms.[7] Larger alignment values can be obtained with posix_memalign()
.[8]Examples
Example 1
In the following C code, the value of zero is used to indicate a null pointer:
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 */
}
Example 2
Here, the programmer has provided a global variable, whose address is then used as a sentinel:
#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 */
}
Example 3
Assume we have a data structure table_entry
that is always aligned to a 16 byte boundary. In other words, the least significant 4 bits of a table entry's address are always 0 (24 = 16). We could use these 4 bits to mark the table entry with extra information. For example, bit 0 might mean read only, bit 1 might mean dirty (the table entry needs to be updated), and so on.
If pointers are 16-bit values, then:
0x3421
is a read-only pointer to thetable_entry
at address0x3420
0xf472
is a pointer to a dirtytable_entry
at address0xf470
Advantages
The major advantage of tagged pointers is that they take up less space than a pointer along with a separate tag field. This can be especially important when a pointer is a return value from a
A more subtle advantage is that by storing a tag in the same place as the pointer, it is often possible to guarantee the atomicity of an operation that updates both the pointer and its tag without external synchronization mechanisms.[further explanation needed] This can be an extremely large performance gain, especially in operating systems.
Disadvantages
Tagged pointers have some of the same difficulties as
The use of zero to represent a null pointer does not suffer from these disadvantages: it is pervasive, most programming languages treat zero as a special null value, and it has thoroughly proven its robustness. An exception is the way that zero participates in
References
- ^ Friday Q&A 2012-07-27: Let's Build Tagged Pointers, by Mike Ash
- ISBN 0-932376-22-3.
- ISBN 978-1882419661.
- ^ Friday Q&A 2013-09-27: ARM64 and You, by Mike Ash
- ^ [objc explain]: Non-pointer isa
- ^ Bricknell, K. J. Macintosh C: A Hobbyist's Guide To Programming the Mac OS in C.
- ^ "Malloc Examples". The GNU C Library. Retrieved 5 September 2018.
- ^ Linux Programmer's Manual – Library Functions –