Tag size for atomic free list
Anon
I'm working on a message passing framework that allows communication
between threads with minimal locking. Naturally, these types of
frameworks consist of a lot of short lived objects running around
between threads. Additionally, I use a lock-free channel with safe
memory reclamation that creates even more short lived objects of
predictable size. I've decided that some kind of pooling strategy will
be necessary - finally settling on a lock-free FreeList implementation
that closely resembles Maged Michael's lock free memory allocator.
Ok there's the background, here is my problem.
The FreeList has a superblock descriptor struct that will be packed into
a 32bit word for use in an atomic compare and swap operation.
struct Anchor{
unsigned index: INDEX_COUNT_BITS;
unsigned count: INDEX_COUNT_BITS;
unsigned tag: TAG_BITS;
};
The tag is there to help prevent the ABA problem, although it doesn't
make it impossible, we're trying to make it highly improbable. Both
index and count must be able to hold the same maximum value. Obviously,
I want to keep the maximum bounds on the freelist as high as possible,
while still having a tag that's large enough to resolve the ABA problem.
My first inclination was a 16bit tag and 8bits for index and count.
This gives us a puny 256 max capacity. Has anyone ran into this, what
is the lowest possible tag size I can have without running into the ABA
problem?
Dmitriy Vyukov
What platform you use?
You can use 64-bit CAS because you don't use pointers (only indexes).
On 32-bit platform you need double-word CAS, but on 64 bit system you
need only single-word CAS!
On x86 this is cmpxchg8b or InterlockedCompareExchange64()
So you can write:
struct Anchor{
unsigned index: 16;
unsigned count: 16;
unsigned tag: 32;
};
Dmitriy V'jukov
Chris Thomasson
news:HtXgj.34149$Wt7....@newsfe14.phx...
> Greetings,
>
[...]
> My first inclination was a 16bit tag and 8bits for index and count.
> This gives us a puny 256 max capacity. Has anyone ran into this, what
> is the lowest possible tag size I can have without running into the ABA
> problem?
Well, you can do some things to get better granularity. For instance, one
little trick is to keep a version per-object. For a lock-free stack, that
would mean incrementing the version count of an object before you push it
onto the anchor. You use the new value as the ABA version for the pointer
operation. Here is pseudo-code for a DWCAS version of this:
__________________________________________________________
struct obj {
obj* nx;
int ver;
};
struct anchor {
obj* hd;
int ver;
};
void push(anchor* const _this, obj* const o) {
anchor cmp, xchg;
xchg.hd = o;
xchg.ver = ++o->ver;
do {
cmp = *_this;
o->nx = cmp.hd;
} while (! DWCAS(_this, &cmp, &xchg));
}
obj* pop(anchor* const _this) {
anchor cmp, xchg;
do {
cmp = *_this;
if (! cmp.hd) { return 0; }
xchg.hd = cmp.hd->nx; /* hazard */
xchg.ver = cmp.ver;
/* to get better accuracy, you can do this omit
the line above and do this:
xchg.ver = cmp.hd->ver; /* hazard */
keep in mine that it's not required to do that...
*/
} while (! DWCAS(_this, &cmp, &xchg));
return cmp.hd;
}
__________________________________________________________
As for a general counter size, I would say, at least 32-bits. Any smaller
and you need to employ some other tricks, including the one above. If you
want to simulate smaller counter sizes with the above scheme, the alls you
have to do is decrease the size of the counter of the obj::ver member:
__________________________________________________________
struct obj {
obj* nx;
short ver;
};
__________________________________________________________
Also, you can read this:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/adb4562b978af3d3
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/133f764f1bc0c9f4
Anthony
Thanks Dmitriy, after sitting up last night, I finally capitulated and
decided to go with the 64bit wide anchor. I've used cmpxchg8b before,
but it seemed impure to me. In addition, when the code gets ported to
x86-64, it will be a TINY bit of extra work :/. As you said, because
I'm not using pointers, migration is much easier. In fact, I think it
will just stay as cmpxchg8b in 64bit mode.
Thanks,
Anthony
Chris Thomasson
news:7ochj.6$GS...@newsfe11.phx...[...]
>> Dmitriy V'jukov
>
> Thanks Dmitriy, after sitting up last night, I finally capitulated and
> decided to go with the 64bit wide anchor. I've used cmpxchg8b before, but
> it seemed impure to me. In addition, when the code gets ported to x86-64,
> it will be a TINY bit of extra work :/. As you said, because I'm not
> using pointers, migration is much easier.
A lot eaiser indeed. You can do atomic_ptr in 64-bit's that way:
http://groups.google.ca/group/comp.programming.threads/msg/aae28a0e1f9b0d66
> In fact, I think it will just stay as cmpxchg8b in 64bit mode.
IIRC cmpxchg8b is more expensive than cmpxchg on 32-bit system.
If you stick with 64-bit CAS, you can make more complex data-structures.
Think of using two of your 32-bit anchors in a single 64-bit struct:
struct List_Anchor32 {
unsigned head: 8;
unsigned tail: 8;
unsigned tag: 16;
};
- or -
struct List_Anchor32 {
unsigned head: 16;
unsigned tag: 16;
};
struct DoubleList_Anchor64 {
List_Anchor32 lists[2];
};
http://groups.google.com/group/comp.programming.threads/msg/504d569bfd109691
Anthony
I was toying with the notion of using the aligned 128bit swap, I presume
it uses the simd buffers internally. Does ppc have a similar instruction?
Chris Thomasson
> Chris Thomasson wrote:
[...]
> I was toying with the notion of using the aligned 128bit swap, I presume
> it uses the simd buffers internally.
LOCK cmpxchg16b is going to be an expensive instruction... Not sure I would
depend on it performing well, or even being available:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/4adaf3008b593404
Humm...
> Does ppc have a similar instruction?
I do not believe that PPC has 128-bit LL/SC...
BTW, here is some more fun you can have with ABA version counters:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/dc3c6791d43401c3
http://groups.google.com/group/comp.programming.threads/msg/632b6bdc2a137459
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/aa8c62ad06dbb380
:^)
Chris Thomasson
> > Chris Thomasson wrote:
[...]
> it uses the simd buffers internally. Does ppc have a similar instruction?
You don't really need ABA counters on PPC because your going to be working
with LL/SC.
Anthony
>> "Anthony" <an...@anon.net> wrote in message
>> news:wtdhj.14$GS...@newsfe11.phx...
>> > Chris Thomasson wrote:
> [...]
>
> working with LL/SC.
I was under the impression that LL/SC on PPC wasn't a true load
linked/store conditional implementation and works basically like a funky
cmpxchg. There would have to be some sort of built in memory protection
to avoid the ABA problem.
Chris Thomasson
More precisely, its a LL(reserved)/SC such that any store's into the
reservation granule will make the conditional store fail; even false sharing
can do this:
http://groups.google.com/group/comp.arch/msg/d40cf092b679169d
http://groups.google.com/group/comp.arch/browse_frm/thread/c9112fbef2afafa9