0

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.
Clifford
  • 88,407
  • 13
  • 85
  • 165
callum arul
  • 159
  • 6
  • Does this answer your question? [Using the extra 16 bits in 64-bit pointers](https://stackoverflow.com/questions/16198700/using-the-extra-16-bits-in-64-bit-pointers) – BoP Mar 11 '23 at 10:57

1 Answers1

1
  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

Clifford
  • 88,407
  • 13
  • 85
  • 165
deviantgeek
  • 121
  • 3
  • Thank you! However, for the 3rd part, I am not allowed to add a a separate variable for count. So is there any way I can replace the 3rd parameter of '''CAS(&tail.ptr->next, next, )''' with some operation that updates the address and increments the count at the same time? – callum arul Mar 11 '23 at 22:34
  • Essentially I want to update the address (48 LSB) and also increment the counter (16 MSB). I am thinking of adding 1 to the 16th most significant bit like this: '''CAS(&tail.address()->next.ptr, next.ptr, node + 0x0001000000000000'''. Will this work? – callum arul Mar 11 '23 at 23:12
  • 1
    I think that will work. Since your setting next.ptr to (node + 0x1000000000000), it will both set the count value, address, and at the same time assign next.ptr in the CAS function. I'm trying to wrap my head around the need for the count though, because this whole thing just seems like a linked list and count will only ever be 1 for every node that has a next node assigned. i'm probably missing additional context and thats why. You could do some tests in [Compiler Explorer](https://godbolt.org/) to see if anything works or not, or write some unit tests to make sure you get the desired results – deviantgeek Mar 12 '23 at 12:55