Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

stealing bits from a pointer

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.

like image 672
Dervin Thunk Avatar asked Oct 15 '13 19:10

Dervin Thunk


2 Answers

  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;
    }
    
like image 119
Fred Foo Avatar answered Oct 28 '22 04:10

Fred Foo


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.

like image 29
Sergey Kalinichenko Avatar answered Oct 28 '22 05:10

Sergey Kalinichenko