cpointersmemory-address

Justification of storing metadata in 2 least significant bits of address


I read this code that seems to use lower 2 bits of addresses to store binary flag, see below (obfuscated due to sensitivity):

void *setFlag4Addr( void *addr, BOOLEAN flag )
{
    // long for 32-bit machine.
    long long ret;
    if ( flag ) {
        ret = (long long)addr | 0x2;
    } else {
        ret = (long long)addr | 0x1;
    }
    return (void *)ret;
}

I wonder what is the justification behind it? does it mean every address has the 2 least significant bits 0b00?
It is because of alignment? for instance, IIRC, address obtained by say malloc has an alignment of 16 bytes on 64-bit machines. But what if alignas is somewhere used?


Solution

  • This function stores the value 1 or 2 in the least significant bits of the address passed as an argument and returns the updated address.

    This method is used to implement tagged pointers. It relies on the following assumptions:

    The code posted is not optimal as it performs a test. A simpler and more general solution would take the tag as an argument and use a single expression.

    Here is a simple example:

    #include <stdint.h>
    
    typedef enum {
        ptr_NONE,
        ptr_INT,
        ptr_STR,
        ptr_OBJ,
        ptr_MASK = 3,
    } ptr_TAG;
    
    void *pointer_set_tag(void *addr, ptr_TAG tag) {
        return (void *)((uintptr_t)addr + tag);
    }
    
    ptr_TAG pointer_get_tag(void *addr) {
        return (ptr_TAG)((uintptr_t)addr & ptr_MASK);
    }
    
    void *pointer_remove_tag(void *addr, ptr_TAG tag) {
        return (void *)((uintptr_t)addr - tag);
    }
    
    void *pointer_untag(void *addr) {
        return (void *)((uintptr_t)addr & ~(uintptr_t)ptr_MASK);
    }
    

    To help distinguish tagged pointers from actual object pointers, it is easy to add an incomplete type:

    #include <stdint.h>
    
    typedef enum {
        ptr_NONE,
        ptr_INT,
        ptr_STR,
        ptr_OBJ,
        ptr_MASK = 3,
    } ptr_TAG;
    
    typedef struct tag_stuff *tagged_ptr;
    
    tagged_ptr pointer_set_tag(void *addr, ptr_TAG tag) {
        return (tagged_ptr)((uintptr_t)addr + tag);
    }
    
    ptr_TAG pointer_get_tag(tagged_ptr addr) {
        return (ptr_TAG)((uintptr_t)addr & ptr_MASK);
    }
    
    void *pointer_remove_tag(tagged_ptr addr, ptr_TAG tag) {
        return (void *)((uintptr_t)addr - tag);
    }
    
    void *pointer_untag(tagged_ptr addr) {
        return (void *)((uintptr_t)addr & ~(uintptr_t)ptr_MASK);
    }