C++: Atomic Tagged pointer with 16-bit counter in upper bits, can't seem to increment the counter

Question

I'm trying to implement an atomic tagged/packed pointer, for the sake of learning.

I want to use the upper 16 bits for a uint16_t counter, and the lower 3 bits for a 3-bit tag.

So far, I've managed to get everything working except the ability to increment the counter. I'm not very familiar with bitwise operations, so I assume the mistake is probably somewhere in my use of them.

The implementation I have is below:

• (Godbolt link: https://godbolt.org/z/ez7PnWxjG)

The current output is:

AtomicTaggedPointer(ptr=0x5589e2dc92b0, val=42, tag=4, count=0) 
0000000000000000 0101010110001001 1110001011011100 1001001010110 100

AtomicTaggedPointer(ptr=0x5589e2dca2e0, val=43, tag=5, count=0) 
0000000000000000 0101010110001001 1110001011011100 1010001011100 101

What I'm trying to achieve is that count=1 when it's printed the second time, and that we see that stored in the upper 16 bits.

#include <atomic>
#include <cassert>
#include <cstdint>
#include <cstdio>

// A word-aligned, atomic tagged pointer.
// Uses both the upper 16 bits for storage, and the lower 3 bits for tagging.
//
//   64                48                32                16
// 0xXXXXXXXXXXXXXXXX  0000000000000000  0000000000000000  0000000000000XXX
//   ^                 ^                                                ^
//   |                 |                                                +-- Tag (3 bits)
//   |                 +-- Pointer (48 bits)
//   +-- Counter (16 bits)
//
//
// The tag is 3 bits, allowing for up to 8 different tags.
//
// The version is incremented every time the pointer is CAS'd. This is useful
// for detecting concurrent modifications to a pointer.
template <typename T>
struct AtomicTaggedPointer
{
    static_assert(sizeof(T*) == 8, "T* must be 8 bytes");
    static_assert(sizeof(std::atomic<uintptr_t>) == 8, "uintptr_t must be 8 bytes");

  private:
    static constexpr uintptr_t kTagMask      = 0x7;                // 3 bits
    static constexpr uintptr_t kCounterMask  = 0xFFFF000000000000; // 16 bits
    static constexpr uintptr_t kPointerMask  = ~kTagMask;          // All bits except tag bits
    static constexpr uintptr_t kCounterShift = 48;                 // Shift counter bits to the left

    std::atomic<uintptr_t> value;

  public:
    AtomicTaggedPointer(T* ptr, uint8_t tag = 0)
    {
        value.store(reinterpret_cast<uintptr_t>(ptr) | tag, std::memory_order_relaxed);
    }

    T* get() const
    {
        return reinterpret_cast<T*>(value.load(std::memory_order_relaxed) & kPointerMask);
    }

    uint8_t tag() const
    {
        return value.load(std::memory_order_relaxed) & kTagMask;
    }

    uint16_t counter() const
    {
        return value.load(std::memory_order_relaxed) >> kCounterShift;
    }

    // Compare and swap the pointer with the desired value, and optionally set the tag.
    // Returns true if the swap was successful.
    // Also increments the version counter by 1.
    bool cas(T* desired, uint8_t tag = 0)
    {
        uintptr_t expected = value.load(std::memory_order_relaxed);
        uintptr_t desired_value =
            reinterpret_cast<uintptr_t>(desired) | (tag & kTagMask) | ((expected + 1) & kCounterMask) << 48;
        return value.compare_exchange_strong(expected, desired_value, std::memory_order_relaxed);
    }

    void print() const
    {
        printf("AtomicTaggedPointer(ptr=%p, val=%d, tag=%hhu, count=%hu) \n", get(), *get(), tag(), counter());
        // Print each bit of the pointer's 64-bit value
        // In the format:
        // 0xXXXXXXXXXXXXXXXX  0000000000000000  0000000000000000  0000000000000XXX
        uintptr_t v = value.load(std::memory_order_relaxed);
        for (int i = 63; i >= 0; i--)
        {
            if (i == 2 || i == 15 || i == 31 || i == 47)
            {
                printf(" ");
            }
            printf("%lu", (v >> i) & 1);
        }
        printf("\n");
    }
};

int
main()
{
    AtomicTaggedPointer<int> p = AtomicTaggedPointer<int>(new int(42), 4);
    p.print();
    assert(p.get() != nullptr);
    assert(*p.get() == 42);
    assert(p.tag() == 4);
    assert(p.counter() == 0);

    int* expected = p.get();
    p.cas(new int(43), 5);
    p.print();
}

Answer 1

You increment expected by adding 1. That would be an increment at the lowest bit. But that is where you put the tag. The counter is at the highest bits. So you need to shift 1 first to the lowest counter bit, i.e. by kCounterShift (and to do so you should first cast 1 to the appropriate type uintptr_t, so that the shift is sure to be in-range).

Also, your kPointerMask is wrong as it doesn't mask the counter bits.

Also, to make sure that the pointers are suitably aligned you should add a static assert on alignof(T) being large enough. Then you should be fine, since it is not possible to pass valid unaligned pointer values for a type in standard C++ and even on platforms where unaligned access is allowed, it is not allowed to pass and dereference incorrectly aligned pointers like this. (see comments under the answer)

In your specific example int is not going to satisfy that requirement. It will have an alignment of only 4 bytes, not the 8 bytes you need. That you are using new to create the objects is probably saving you from getting pointers that are not 8 byte aligned, but even for new int this is not guaranteed in general.

Also, of course a lot here is implementation-defined behavior. For example the layout of the bits in the pointer used and how they map to uintptr_t is specific to x86-64 and a typical ABI. I could imagine a compiler using the unused bits in the pointer itself for some purpose or similar.

There might also be a broader question of whether the whole approach is compatible with pointer provenance, which I am not sure about.