#StackBounty: #lock-free How many ABA tag bits are needed in lock-free data structures?

Bounty: 200

One popular solution to the ABA problem in lock-free data structures is to tag pointers with an additional monotonically incrementing tag.

 struct aba {
      void *ptr;
      uint32_t tag;
 };

However, this approach has a problem. It is really slow and has huge cache problems. I can obtain a speed-up of twice as much if I ditch the tag field. But this is unsafe.

So my next attempt stuff for 64 bit platforms stuffs bits in the ptr field.

struct aba {
    uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }

But someone said to me that only 16 bits for the tag is unsafe. My new plan is to use pointer alignment to cache-lines to stuff more tag bits in but I want to know if that’ll work.

How many bits do I need for the ABA tag in lock-free data-structures?


Get this bounty!!!

Leave a Reply