CODEWITHSUNDEEP
c++cc++11thread-safetyatomic
user3217789
user3217789

Reputation: 211

Lock-free with 8byte CAS only? C++

I am using a 64-bit x86 system limited to a 8 byte maximum for compare and swap operations. Since pointers are 8-bytes and I require a counter to avoid the ABA problem, is it possible to modify the upper 16 bits of the pointer which are unused to store a counter?

pointer_as_dec = reinterpret_cast<uintptr_t>(&node); // Node address
pointer_as_dec+(1LLU<<48); // Initialize the counter in one of the upper bits

Is it possible to use the __sync_bool_compare_and_swap function to store the modified pointer address?

Upvotes: 0

Views: 427

Answers (1)

abarnert
abarnert

Reputation: 365817

Well, this isn't guaranteed to work according to any standard—the only thing you're really allowed to do with a pointer cast to an int is cast it back to a pointer unchanged. But practically, it will work on any x86_64 platform, and almost any other current platform. And obviously you weren't expecting gcc-specific, x86_64-specific code to be portable. So, no problem here.

Also, uintptr_t is not one of the supported types for gcc atomic functions—but it's completely compatible with unsigned long long int, which is. (If you're worried about that, you can always add a second cast…) So, no problem here either.

Meanwhile, __sync_bool_compare_and_swap doesn't care that you're smuggling a pointer in that uintptr_t; as far as it's concerned, it's just an unsigned 64-bit integer. So, no problem here.

Can you really be sure that the top 16 bits are always empty? In x86_64 linux, they are for your normal user memory. They may not be for pointers to kernel memory or memory-mapped hardware, and they may not be on other x86_64 systems—but if not, they'll be all 1s instead. And as Brendan points out, that's guaranteed for anything running on x86_64 hardware without 128-bit CAS.* So, if you need to point at such memory or port to such systems, just use 15 bits instead of 16. (And even if that weren't true, assuming you're pointing to, say, 64-bit-aligned objects, you've also got 6 free bits at the other end of the pointer, which you could use instead/in addition.) So, no problem here either.

* Except in the highly unlikely event that AMD or Intel or someone else decides to change the virtual address size and also decides to take away 128-bit CAS…

Upvotes: 2

Related Questions