Search code examples
c++pointersnonblockingcompare-and-swapconcurrent-queue

Using most significant bits of pointers as a tag in non-blocking queue c++


I am trying to implement a concurrent non-blocking queue where the tag is in the 16 most significant bits of the pointer. It follows this algorithm here: http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html

However, this algorithm assumes a pointer struct with a separate count variable for the tag (structure pointer_t {ptr: pointer to node_t, count: unsigned integer}). However, I have to do it with just the pointer like so:

template<class P>
struct pointer_t {
    P* ptr;
    //no uint to store the tag
    P* address(){
        return (P*)(ptr & 0x0000FFFFFFFFFFFF);
    }

    uint count(){
        return ptr & 0xFFFF000000000000;
    }
};

I have a couple of questions:

  1. How do I extract the count (16 most significant bits) of the pointer address and turn it into an uint to return? Currently my count function just returns the MSBs and not the uint.
  2. Is my address function correctly returning the 48 Least significant bits of the pointer?
  3. The compare and swap operation from the algorithm is given like so:

    CAS(&tail.ptr->next, next, <node, next.count+1>)

    How do I update both the address of tail and increment the count in one operation? I am required to use a CAS function already provided and is not visible to me. So I have to replace <node, next.count+1> with an operation that does both. I am assuming this also involves some bitwise operations.

Solution

    1. You could do this
    uint16_t count(){
        return ((uintptr_t)ptr >> 48) & 0xFFFF;
    }
    
    1. No, actually probably gives a compiling error. I'm using c++17 but this is how you could accomplish this.
    P* address(){
        return (P*)((uintptr_t)ptr & 0x0000FFFFFFFFFFFF);
    }
    
    1. You're correct, it will involve some bitwise operations, OR, you could just make a pointer to the last 16 bits like this and update it via a pointer:
    uint16_t* count = (uint16_t*)((uint8_t*)&ptr + 6);`
    
    *count++;
    

    I'd probably go the pointer route myself. you could even use this pointer to get the current count value and replace my #1 answer with

    uint16_t count(){
        return *count;
    }
    

    disclaimer: none of this is optimized, if you need to optimize for performance. there are definitely ways to make this better, but this is off the top of my head how i'd at least start to work out this problem