Re: [boost] [Lockfree] Tagged pointers

Subject: Re: [boost] [Lockfree] Tagged pointers
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-28 05:05:14

hi phil,

> I understand that your implementation uses tagged pointers to avoid ABA
> problems.  An issue with tagged pointers is that naively they will be
> 2*sizeof(T*) and systems may not have atomic operations that operate on
> things of that size.  Looking at the code, I see that you also have a
> "compressed" tagged pointer that is enabled for some architectures.
> Having found this code, I now vaguely recall some previous mailing list
> discussions about this.

actually i think that most 64bit architectures do not use the full 64bit address 
space, but unfortunately this is often not defined in the specifications :/

> Sometimes it may be possible to claim that users (& reviewers?) of a
> library do not need to know about details of this sort because the
> library "just works", and that if they are curious they can read the
> source.  I don't think this is one of those cases.  The documentation
> should explain in outline how this works, and provide rationale for why
> it is how it is.

well, this just is the case for these data structures. however there is lock-
free dequeue for example, which requires access to two tagged pointers (an 
implementation of it was posted a few months ago, but i didn't want to include 
that into boost.lockfree for now).
however i could add a section about `internals' of the library to the docs.

anyway, yesterday i started to implement a modified version of the freelist, 
that does not use pointers, but 16bit indices. this limits the possible size of 
the data structure to 2**16-1 elements, but 16bit pointer and 16bit aba 
prevention tag can be packed into one 32bit word. it really complicates the 
implementation, but it should ensure the lock-freedom on many ll/sc-based 
platforms (like ppc).

> IIRC, ARM has 64-bit atomics only from architecture version 6k onwards,
> and my Boost.Atomic ARM code doesn't use them.  This could be fixed.

that would be great! do you know if the pointer compression would be feasible on 
arm as well?

cheers, tim