Tagged pointer

<h2 id="folding-tags-into-the-pointer">Folding tags into the pointer</h2>
<p>There are various techniques for folding tags into a pointer.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>[<i>unreliable source?</i>]
</p><p>Most architectures are <a href="/facts/Byte-addressable/TPghPMKg">byte-addressable</a> (the smallest addressable unit is a byte), but certain types of data will often be <i><a href="/facts/Data_Structure_Alignment/Bqk6zMNS">aligned</a></i> to the size of the data, often a <a href="/facts/Word_(computer_architecture)/2e5umRaj">word</a> or multiple thereof. This discrepancy leaves a few of the <a href="/facts/Least_significant_bits/94h4P3qr">least significant bits</a> of the pointer unused, which can be used for tags – most often as a <a href="/facts/Bit_field/fWgTjqvX">bit field</a> (each bit a separate tag) – as long as code that uses the pointer <a href="/facts/Bit_mask/d9Cu1A1Y">masks out</a> these bits before accessing memory. E.g., on a <a href="/facts/32-bit/TDMVce8s">32-bit</a> architecture (for both addresses and word size), a word is 32 bits = 4 bytes, so word-aligned addresses are always a multiple of 4, hence end in 00, leaving the last 2 bits available; while on a <a href="/facts/64-bit/AgvkQHkM">64-bit</a> architecture, a word is 64 bits = 8 bytes, so word-aligned addresses end in 000, leaving the last 3 bits available. In cases where data is aligned at a multiple of word size, further bits are available. In case of <a href="/facts/Word-addressable/n2HGojXK">word-addressable</a> architectures, word-aligned data does not leave any bits available, as there is no discrepancy between alignment and addressing, but data aligned at a multiple of word size does.
</p><p>Conversely, in some operating systems, <a href="/facts/Virtual_address/ILxbMjgv">virtual addresses</a> are narrower than the overall architecture width, which leaves the <a href="/facts/Most_significant_bits/94h4P3qr">most significant bits</a> 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 <a href="/facts/64-bit/AgvkQHkM">practical 64-bit processors</a> have narrower addresses. Note that the virtual address width may be narrower than the <a href="/facts/Physical_address/G01PUI6A">physical address</a> width, which in turn may be narrower than the architecture width; for tagging of pointers in <a href="/facts/User_space/0yIzMY8t">user space</a>, the virtual address space provided by the operating system (in turn provided by the <a href="/facts/Memory_management_unit/tJQtAQzI">memory management unit</a>) is the relevant width. In fact, some processors specifically forbid use of such tagged pointers at the processor level, notably <a href="/facts/X86-64/cyWvUFlP">x86-64</a>, which requires the use of <a href="/facts/X86-64/cyWvUFlP">canonical form addresses</a> by the operating system, with most significant bits all 0s or all 1s.
</p><p>Lastly, the <a href="/facts/Virtual_memory/Lw2GemF5">virtual memory</a> system in most modern <a href="/facts/Operating_system/8XTuvMh2">operating systems</a> 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 <a href="/facts/Null_pointer/66zwVEfL">null pointer</a> value. Unlike the previously mentioned techniques, this only allows a single special pointer value, not extra data for pointers generally.
</p>
<h2 id="examples">Examples</h2>
<p>One of the earliest examples of hardware support for tagged pointers in a commercial platform was the <a href="/facts/IBM_System/38/lwEK6d2A">IBM System/38</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> IBM later added tagged pointer support to the <a href="/facts/PowerPC/DqmM9y50">PowerPC</a> architecture to support the <a href="/facts/IBM_i/lsIRAUvn">IBM i</a> operating system, which is an evolution of the System/38 platform.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>A significant example of the use of tagged pointers is the <a href="/facts/Objective-C/5mM557BW">Objective-C</a> runtime on <a href="/facts/IOS_7/LP8uLlwP">iOS 7</a> on <a href="/facts/ARM64/bauXRos7">ARM64</a>, notably used on the <a href="/facts/IPhone_5S/5adgnjro">iPhone 5S</a>. 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 <a href="/facts/Destructor_(computer_programming)/gr4051ve">destructor</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p><p>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.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
<h2 id="null-versus-aligned-pointer">Null versus aligned pointer</h2>
<p>Use of zero to represent a null pointer is extremely common, with many programming languages (such as <a href="/facts/Ada_programming_language/Y2yHel4l">Ada</a>) explicitly relying on this behavior.  In theory, other values in an operating system-reserved block of logical memory could be used to tag conditions other than a null pointer, but these uses appear to be rare, perhaps because they are at best <a href="/facts/Porting/7s6tFs8B">non-portable</a>.  It is generally accepted practice in software design that if a special pointer value distinct from null (such as a <a href="/facts/Sentinel_value/Ma1rxg1q">sentinel</a> in certain <a href="/facts/Data_structure/yNsNvL1I">data structures</a>) is needed, the programmer should explicitly provide for it.
</p><p>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.
</p><p>In a <a href="/facts/Tagged_architecture/RQfWwKTH">tagged architecture</a>, a number of bits in every word of memory are reserved to act as a tag.  Tagged architectures, such as the <a href="/facts/Lisp_machine/8ULEHdF0">Lisp machines</a>, often have hardware support for interpreting and processing tagged pointers.
</p><p><a href="/facts/GNU_C_Library/AL6IYDkA">GNU libc</a> malloc() provides 8-byte aligned memory addresses for 32-bit platforms, and 16-byte alignment for 64-bit platforms.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> Larger alignment values can be obtained with posix_memalign().<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p>
<h2 id="examples">Examples</h2>
<h3>Example 1</h3>
<p>In the following C code, the value of zero is used to indicate a null pointer:
</p>
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 */
}

<h3>Example 2</h3>
<p>Here, the programmer has provided a global variable, whose address is then used as a sentinel:
</p>
#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 */
}

<h3>Example 3</h3>
<p>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.
</p><p>If pointers are 16-bit values, then:
</p>
<ul><li>0x3421 is a read-only pointer to the table_entry at address 0x3420</li>
<li>0xf472 is a pointer to a dirty table_entry at address 0xf470</li></ul>
<h2 id="advantages">Advantages</h2>
<p>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 href="/facts/Function_(computer_science)/9vFJrg0A">function</a>.  It can also be important in large tables of pointers.
</p><p>A more subtle advantage is that by storing a tag in the same place as the pointer, it is often possible to guarantee the <a href="/facts/Linearizability/u3pnNCvs">atomicity</a> of an operation that updates both the pointer and its tag without external <a href="/facts/Synchronization/L39sYwbr">synchronization</a> mechanisms.  This can be an extremely large performance gain, especially in operating systems.
</p>
<h2 id="disadvantages">Disadvantages</h2>
<p>Tagged pointers have some of the same difficulties as <a href="/facts/Xor_linked_list/fKfwKXmI">xor linked lists</a>, although to a lesser extent.  For example, not all <a href="/facts/Debugger/mCe6UsWj">debuggers</a> will be able to properly follow tagged pointers; however, this is not an issue for a debugger that is designed with tagged pointers in mind.
</p><p>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 <a href="/facts/Overload_resolution/wL27p4rD">overload resolution</a> in C++, where zero is treated as an integer rather than a pointer; for this reason the special value <a href="/facts/Nullptr/fI3YCoKQ">nullptr</a> is preferred over the integer zero.  However, with tagged pointers zeros are usually not used to represent null pointers.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Friday Q&A 2012-07-27: Let's Build Tagged Pointers, by Mike Ash <a href="https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html" target="_blank">https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Levy, Henry M. (1984). "The IBM System/38" (PDF). Capability-Based Computer Systems. Digital Press. ISBN 0-932376-22-3. <a href="0-932376-22-3" target="_blank">0-932376-22-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Frank G. Soltis (1997). Inside the AS/400, Second Edition. Duke Press. ISBN 978-1882419661. <a href="978-1882419661" target="_blank">978-1882419661</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Friday Q&A 2013-09-27: ARM64 and You, by Mike Ash <a href="https://www.mikeash.com/pyblog/friday-qa-2013-09-27-arm64-and-you.html" target="_blank">https://www.mikeash.com/pyblog/friday-qa-2013-09-27-arm64-and-you.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>[objc explain]: Non-pointer isa <a href="http://www.sealiesoftware.com/blog/archive/2013/09/24/objc_explain_Non-pointer_isa.html" target="_blank">http://www.sealiesoftware.com/blog/archive/2013/09/24/objc_explain_Non-pointer_isa.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Bricknell, K. J. Macintosh C: A Hobbyist's Guide To Programming the Mac OS in C. <a href="http://www.mactech.com/macintosh-c/classic-chap01-1.html" target="_blank">http://www.mactech.com/macintosh-c/classic-chap01-1.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>"Malloc Examples". The GNU C Library. Retrieved 5 September 2018. <a href="https://www.gnu.org/software/libc/manual/html_node/Malloc-Examples.html#Malloc-Examples" target="_blank">https://www.gnu.org/software/libc/manual/html_node/Malloc-Examples.html#Malloc-Examples</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>posix_memalign(3) – Linux Programmer's Manual – Library Functions <a href="https://manned.org/posix_memalign.3" target="_blank">https://manned.org/posix_memalign.3</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Tagged pointer open-in-new

Tagged pointer