stealing bits from a pointer

Question

In The Art of Multiprocessor Programming, p215, the authors say that in C, you could "steal" a bit from a pointer, and using bit-wise operators extract some flag (a mark) and the pointer from a single word. I don't know how this is done, so an example would help me.

Ormuz

It might be useful to know that this is generally bad practice unless there really is a legitimate reason to do so. – Wigwam

@Mysticial: it's common practice for implementing dynamic languages, though. – Dekko

@Mysticial: there is, when you need to do atomic ops on a single word. – Ormuz

I was thinking more on the lines of saving memory when you have large arrays of pointers (with a flag). But yes, those two also apply. (didn't cross my mind initially) – Wigwam

Answer 1

Imagine a system with a 32-bit pointer size, but only 1GB of memory is available. You need only 30 bits to address the entire memory space, so the upper 2 bits are unused. You can use these upper two bits for your own purposes - for example, to mark pointers by pointer type (stack/global vs. dynamic).

Note that the code that you get as the result is about as non-portable as it gets. You need to be intimately familiar with the CPU on which your code runs - specifically, you need to know if the upper bits get dropped when an address from the pointer is sent to the address bus.

Febrile

This was very common on 68000-based systems where the address space was only 24 bits - the top 8 bits of a 32 bit address could safely be used for various flags. The original Mac OS back in the 1980s used this trick for locked, purgeable and resource flags. – Usher

Answer 2

1. Make sure the pointee objects are aligned in memory so that all your pointers are even numbers. The last bit is then free for storing a single boolean flag. (This cannot be done completely portably. so you need knowledge of the platform.)

2. Move the pointers around as integers of type uintptr_t. These can easily be manipulated:

   bool get_flag(uintptr_t p)
   {
       return p & 1;
   }
   
   void *get_pointer(uintptr_t p)
   {
       return (void *)(p & (UINTPTR_MAX ^ 1));
   }
   
   uintptr_t set_flag(uintptr_t p, bool value)
   {
       return (p & (UINTPTR_MAX ^ 1)) | value;
   }
   

Dekko

How do achieve the same in java? – Steffi

In Java, the same functionality (with the intention of synchronising accesses to a shared object) is available with the AtomicMarkableReference class. The Nannies today are different than in the last millennia... – Antoninaantonino

is this means... that if the pointer is aligned to 8 bytes... we can steal 2 bits ? I have avl tree and I have 1 uint8_t (2 bits) , 3 pointers + data – Anni