lock-free reference counting for PPC/Alpha

[Joseph Seigh]

This scheme for incrementing a reference count while avoiding any
race conditions seems like it might work.

loop:
load pointer to refcounted object.
load locked (lwarx) on refcount in object.
reload pointer to refcounted object.
goto loop if pointer changed.
store conditional (stwcx) to increment refcount.
goto loop if store conditional failed.

Add membars as appropiate.

It needs the virtual storage to always be valid so the load locked won't segfault.
The reload is to verify that your load locked (reserve) is for a valid location.

I'm suspicious of things this simple though. Either there's something wrong with
it that I am overlooking, or it's already known and I've just never heard of it.

Joe Seigh

[SenderX]

> loop:
> load pointer to refcounted object.
> load locked (lwarx) on refcount in object.
> reload pointer to refcounted object.
> goto loop if pointer changed.
> store conditional (stwcx) to increment refcount.
> goto loop if store conditional failed.

What if right after or before the load locked, another thread decrements the
refcount to zero and destroys the pointer?

> It needs the virtual storage

Will that over come that possibility?

for(;;)
{
pLocal = pRefObj;

lRefs = pLocal->RefCount.lRefs;

lAba = pLocal->RefCount.lAba;

pReload = pRefObj;

if ( pReload != pLocal )
{
continue;
}

if ( CAS64( &pLocal->RefCount,
lRefs,
lAba,
lRefs + 1,
lAba + 1 ) )
{
break;
}
}

Would that mimic your pseudo code?

--
The designer of the SMP and HyperThread friendly, AppCore library.

http://AppCore.home.attbi.com

[Joseph Seigh]

SenderX wrote:
>
> > loop:
> > load pointer to refcounted object.
> > load locked (lwarx) on refcount in object.
> > reload pointer to refcounted object.
> > goto loop if pointer changed.
> > store conditional (stwcx) to increment refcount.
> > goto loop if store conditional failed.
>
> What if right after or before the load locked, another thread decrements the
> refcount to zero and destroys the pointer?

It's delete pointer, decrement refcount to zero, and then destroy object.
If it's after the load locked, the reservation is lost. If it's before,
either the second check of the pointer will fail, or if the object is
reused and the reservation was not lost due to that, then everything is
ok. The reservation is on a valid refcount.

>
> > It needs the virtual storage
>
> Will that over come that possibility?

Same requirement that the lock-free ABA counted LIFO stack has. When it does that
load of the first objects next pointer from what it thinks is that objects storage,
it has to be valid storage even if it's not an object at that time.

(snip)

>
> Would that mimic your pseudo code?

No. CAS won't work if it makes assumptions about that state of storage that it's
working on. Heap storage won't let you make any assumptions. If you use a free
object pool where you can control the freed objects states, maybe then.
>

Anyway, it allows an implementation of atomic_ptr on 32 bit PowerPC since it doesn't
have a doublewide CAS (lwarx/stwcx). This is not a problem since atomic_ptr doesn't
have any implementation dependent methods like some other smart pointers.

And it's double checked, so another DC.. acronym for somebody. DCRC?

Joe Seigh

[SenderX]

> If you use a free
> object pool where you can control the freed objects states, maybe then.

Yes, the IBM FreeList works that way by acting as the free object pool
itself.

> When it does that
> load of the first objects next pointer from what it thinks is that objects
storage,
> it has to be valid storage even if it's not an object at that time.

Well, yeah that would make atomic_ptr unneeded.

Atomic_ptr solves this race condition in all the lock-free algos I've used
it in.

CAS would work for this if it operated on " virtual storage "...

Is there be a way to implement a memory scheme that will work like that on
Windows?

I don't believe VirtualMem API's are even close?