Need help deciphering a lock-free memory reclamation algorithm...
Chris M. Thomasson
http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/34116dd115826b54
I can't see how this thing can work. Can you?
:^|
I am swamped with work right now, but I thought I should bring this to the
attention of the group.
I don't think it works. If it its seems very prove to live-lock in the
shared pointer to local pointer transaction.
Anthony Williams
> Here is outline:
>
> http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/34116dd115826b54
>
> I can't see how this thing can work. Can you?
At first glance it looks OK. It relies on the memory used for the A
objects not being reused for anything other than new A objects. This
means the pointers can still be dereferenced, but the version field
will be different if the A object has been destroyed and a new one
constructed. If the version field is different we have a different
object so attempts to increase the ref count fail.
I've done something similar myself before now.
> I don't think it works. If it its seems very prove to live-lock in the
> shared pointer to local pointer transaction.
If the CAS fails it restarts completely because it has to reload the
value :-(
I would expect to see the CAS return the old value, in which case the
code doesn't need to restart --- it now knows the value it has is
valid, thus reducing the potential for livelock.
Anthony
--
Anthony Williams | Just Software Solutions Ltd
Custom Software Development | http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL
Chris M. Thomasson
news:u3akbg...@gmail.com...
> "Chris M. Thomasson" <n...@spam.invalid> writes:
>
>> Here is outline:
>>
>> http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/34116dd115826b54
>>
>> I can't see how this thing can work. Can you?
>
> At first glance it looks OK. It relies on the memory used for the A
> objects not being reused for anything other than new A objects.
Okay. I think that's what I was missing. I really need to examine the
algorithm in more detail and perhaps create some C pseudo-code. I suppose
the data-structures in C would be something like:
struct refcnt {
atomicword refs;
atomicword ver;
};
struct global_ptr {
struct refcnt* ptr;
atomicword ver;
};
the "internal" increment function would look like:
<assume DWCAS automatically returns updated value>
atomicword
refcnt_sys_inc(
struct refcnt* _this,
atomicword ver
) {
struct refcnt cmp = *_this;
struct refcnt xchg;
xchg.ver = ver;
do {
if (cmp.ver != ver) {
return 0;
}
xchg.refs = cmp.refs + 1;
} while (! DWCAS(_this, &cmp, &xchg));
return xchg.refs;
}
the internal decrement function:
void
refcnt_sys_dec(
struct refcnt* _this
) {
struct refcnt cmp = *_this;
struct refcnt xchg;
do {
if (! cmp.ver) {
return 0;
}
xchg.refs = cmp.refs - 1;
xchg.ver = ! xchg.refs ? 0 : cmp.ver;
} while (! DWCAS(_this, &cmp, &xchg));
if (! xchg.refs) {
/* _this is in persistent quiescent state? Humm... */
}
}
Now, the all important global-to-local increment:
struct refcnt*
global_ptr_inc(
struct global_ptr* _this
) {
struct refcnt* rc;
struct global_ptr cmp = *_this;
for (;;) {
struct global_ptr xchg;
xchg.ptr = cmp.ptr;
xchg.ver = cmp.ver + 1;
if (DWCAS(_this, &cmp, &xchg)) {
rc = cmp.ptr;
if (! rc) {
break;
}
if (refcnt_sys_inc(rc, cmp.ver)) {
break;
}
sched_yield();
cmp = *_this;
}
}
return rc;
}
Did I copy his algorithm correctly? Humm...
> This
> means the pointers can still be dereferenced, but the version field
> will be different if the A object has been destroyed and a new one
> constructed. If the version field is different we have a different
> object so attempts to increase the ref count fail.
Thanks.
> I've done something similar myself before now.
Humm... Well, as long as DWCAS is used, why not just utilize Joe Seighs
excellent atomic_ptr? It does not suffer from the caveats that come along
with this approach.
;^)
>> I don't think it works. If it its seems very prove to live-lock in the
>> shared pointer to local pointer transaction.
>
> If the CAS fails it restarts completely because it has to reload the
> value :-(
>
> I would expect to see the CAS return the old value, in which case the
> code doesn't need to restart --- it now knows the value it has is
> valid, thus reducing the potential for livelock.
Indeed!
Anthony Williams
> "Anthony Williams" <antho...@gmail.com> wrote in message
> news:u3akbg...@gmail.com...
>> "Chris M. Thomasson" <n...@spam.invalid> writes:
>>
>>> Here is outline:
>>>
>>> http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/34116dd115826b54
>>>
>>> I can't see how this thing can work. Can you?
>>
>> At first glance it looks OK. It relies on the memory used for the A
>> objects not being reused for anything other than new A objects.
>
> Okay. I think that's what I was missing. I really need to examine the
> algorithm in more detail and perhaps create some C pseudo-code. I
> suppose the data-structures in C would be something like:
>
>
> struct refcnt {
> atomicword refs;
> atomicword ver;
> };
>
> struct global_ptr {
> struct refcnt* ptr;
> atomicword ver;
> };
Yes, looks like it.
> the "internal" increment function would look like:
[snip]
> the internal decrement function:
>
> void
> refcnt_sys_dec(
> struct refcnt* _this
> ) {
> struct refcnt cmp = *_this;
> struct refcnt xchg;
> do {
> if (! cmp.ver) {
> return 0;
> }
> xchg.refs = cmp.refs - 1;
> xchg.ver = ! xchg.refs ? 0 : cmp.ver;
> } while (! DWCAS(_this, &cmp, &xchg));
> if (! xchg.refs) {
> /* _this is in persistent quiescent state? Humm... */
> }
> }
_this isn't in a "persistent quiescent state" --- it's released the
allocator to be reused as a new object refcounted under the same
scheme.
> Now, the all important global-to-local increment:
>
> struct refcnt*
> global_ptr_inc(
> struct global_ptr* _this
> ) {
> struct refcnt* rc;
> struct global_ptr cmp = *_this;
> for (;;) {
> struct global_ptr xchg;
> xchg.ptr = cmp.ptr;
> xchg.ver = cmp.ver + 1;
> if (DWCAS(_this, &cmp, &xchg)) {
No. The DWCAS here is just used to ensure that the value is read
correctly, not to update the version. As I understand Lance's email,
the version is only updated by the allocator (i.e. new version => new
object).
>> I've done something similar myself before now.
>
> Humm... Well, as long as DWCAS is used, why not just utilize Joe
> Seighs excellent atomic_ptr? It does not suffer from the caveats that
> come along with this approach.
At the time I wasn't aware of Joe's atomic_ptr. If I wanted to do the
same again I might well use it.
Chris M. Thomasson
Okay.
>> Now, the all important global-to-local increment:
>>
>> struct refcnt*
>> global_ptr_inc(
>> struct global_ptr* _this
>> ) {
>> struct refcnt* rc;
>> struct global_ptr cmp = *_this;
>> for (;;) {
>> struct global_ptr xchg;
>> xchg.ptr = cmp.ptr;
>> xchg.ver = cmp.ver + 1;
>> if (DWCAS(_this, &cmp, &xchg)) {
>
> No. The DWCAS here is just used to ensure that the value is read
> correctly, not to update the version. As I understand Lance's email,
> the version is only updated by the allocator (i.e. new version => new
> object).
Ahhhh. Well, I don't think you need DWCAS at all here. AFAICT, alls you
would need is an atomic snapshot algorithm to grab a coherent view:
struct refcnt*
global_ptr_inc(
struct global_ptr volatile* _this
) {
struct refcnt* rc;
for (;;) {
struct global_ptr cmp1 = *_this;
struct global_ptr cmp2 = *_this;
if (cmp1.ptr == cmp2.ptr &&
cmp1.ver == cmp2.ver) {
rc = cmp1.ptr;
if (! rc) {
break;
}
if (refcnt_sys_inc(rc, cmp1.ver)) {
break;
}
sched_yield();
}
}
return rc;
}
http://research.sun.com/people/moir/Papers/p004-luchangco.pdf
(refer to section 3.3)
It seems like it should work with this algorithm as well...
>>> I've done something similar myself before now.
Thanks for your help. I understand how this works now.
>> Humm... Well, as long as DWCAS is used, why not just utilize Joe
>> Seighs excellent atomic_ptr? It does not suffer from the caveats that
>> come along with this approach.
>
> At the time I wasn't aware of Joe's atomic_ptr. If I wanted to do the
> same again I might well use it.
Joes algorithm is awesome!
:^)
Anthony Williams
Yes, I'd have thought so. Except that on x86 you really ought to use
the same size operations for all loads and stores (i.e. all 64-bit or
all 32-bit, or whatever) in order to avoid messing with the cache
control. Whether it really matters or not I don't know for sure.
>>>> I've done something similar myself before now.
>
> Thanks for your help. I understand how this works now.
You're welcome.