An experimental algo to avoid ABA on 32/64-bit cpus...

[SenderX]

The following pseudo-code might be able to be used to avoid ABA counts on
lock-free collections.

It uses normal atomic ops, no CAS64 on 32-bit cpus...

Please critique it:

/* The node */
typedef struct SLfNode_
{
volatile struct SLfNode* pNext;
volatile struct SLfNode* pGarbageNext;
const void* pAppState;

} SLfNode;

/* A stack */
typedef struct SLfStack_
{
volatile SLfNode* pFront;

} SLfStack;

/* The garbage */
typedef struct SLfGarbage_
{
SLfStack CollectedNodes;
int iRefs;

} SLfGarbage;

/**** Garbage API

/* Reference the garbage collector */
int LfGarbageAddRef( SLfGarbage* pGarbage )
{
int iRefs = InterlockedIncrement( &pGarbage->iRefs );

assert( iRefs > 0 );

return iRefs;
}

/* Collects garbage */
int LfGarbageCollect( SLfGarbage* pGarbage, SLfNode* pNode )
{
SLfNode* pLocal;

/* Garbage collect push is ABA safe */

do
{
assert( pGarbage->iRefs > 0 );

pLocal = pGarbage->CollectedNodes.pFront;

pNode->pGarbageNext = pLocal;
}

while( InterlockedCompareExchangePointer
( &pGarbage->CollectedNodes.pFront,
pNode,
pLocal ) != pLocal );

return 1;
}

/* Releases the garbage collector */
int LfGarbageRelease( SLfGarbage* pGarbage )
{
/* Take a pre-decrement snap-shot */
SLfNode* pLocal = pGarbage->CollectedNodes.pFront;

int iRefs = InterlockedDecrement( &pGarbage->iRefs );

assert( iRefs >= 0 );

/* If we dropped to zero, we know for SURE that ALL of the nodes
in the pre-decrement snap-shot of the collector, are not in
ANY other threads lock-free collection CAS section. */
if ( iRefs == 0 && pLocal )
{

/* Cas is needed here to make sure that the
front of CollectedNodes has not changed since the
previous pre-decrement snapshot. If it has changed, the garbage
collector was
referenced and collected to since the decrement. No problem. */

/* Setting the stack to zero is ok because we never pop & reuse
pointers here */
if ( InterlockedCompareExchangePointer
( &pGarbage->CollectedNodes.pFront,
0,
pLocal ) == pLocal )
{
SLfNode* pNext;

while( pLocal )
{
pNext = pLocal->pGarbageNext;

/* We can reuse as well, store in per-thread list */
free( pLocal );

pLocal = pNext;
}
}
}

return iRefs;
}

/**** Stack API

int LfStackPush( SLfStack* pStack, SLfGarbage* pGarbage, const void*
pAppState )
{
/* Stack push is ABA safe */

... normal lock-free cas push, without ABA.. cmpxchg
}

void* LfStackPop( SLfStack* pStack, SLfGarbage* pGarbage )
{
void* pAppState;

SLfNode* pNode, *pLocal;

/* Begin a garbage cycle */
LfGarbageAddRef( pGarbage );

do
{
if ( ! ( pLocal = pStack->pFront ) )
{
/* End the garbage cycle */
LfGarbageRelease( pGarbage );

return 0;
}
}

/* Try and pop the node */
while( InterlockedCompareExchangePointer
( &pStack->pFront,
pLocal->pNext,
pLocal ) != pLocal );

pAppState = pLocal->pAppState;

/* Collect the node that the stack popped */
LfGarbageCollect( pGarbage, pLocal );

/* End the garbage cycle */
LfGarbageRelease( pGarbage );

return pAppState;
}

Initial testing is going well. No crashes so far...

=)

What do you think of it?

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

http://AppCore.home.comcast.net

[Neill Clift [MSFT]]

"SenderX" <x...@xxx.xxx> wrote in message
news:R6fmb.18865$Fm2.9642@attbi_s04...

> The following pseudo-code might be able to be used to avoid ABA counts on
> lock-free collections.
>
> It uses normal atomic ops, no CAS64 on 32-bit cpus...
>
> Please critique it:
>
>

Only took a brief look but don't you have an issue inside your
garbage release function.
For example one pop guys calls it and sees a pFront of P1.
He sees the reference count go to zero. Before he gets to the
swap another thread does garbage collect and the P1 element
is freed an reused by the package. It may reenter this package
and get on the front of the list before the swap is continued.
They you garbage collect the node when the refrence count
is not zero right?

pLocal = pNext;
}
}
}

--
This posting is provided "AS IS" with no warranties, and confers no rights.

[SenderX]

> Only took a brief look but don't you have an issue inside your
> garbage release function.

Thanks for the input!

I only created this algo a couple of days ago, and haven't had too much time
to extremely examine race-conditions in critical areas... That's why I
posted it here, to get some feedback.

But lets see here...

> Before he gets to the
> swap another thread does garbage collect and the P1 element
> is freed an reused by the package.

So Thread B increments the garbage RIGHT AFTER Thread A dropped to zero.
Thread B pops a node P2 from the lock-free collection, and collects it. Now,
the Thread A would fail its cas of the garbage collector head, as it is not
P1 anymore, all normal. But, I see the condition you found could be valid.
Yes, this is a classic race-condition caused by normal reference counting.
The pre-decrement snapshot and cas after decrement, seems to make it very
remote, like ABA does. But more can be done to virtually eliminate the
race-condition, much like an ABA count...

> It may reenter this package
> and get on the front of the list before the swap is continued.

I have to study this issue. Lets say your right, and this will cause crash.
The conditions for this to occur seem unlikely. There is a fix to this
possible condition. You would free the nodes to the back of a per-thread
fifo queue. The per-thread queue would delay pointer reuse. Delaying pointer
reuse would make the condition you found virtually impossible. The depth of
the per-thread queue would be equivalent to the depth of an ABA count.

I believe this gc'tor using per-thread queues for a per-thread pointer reuse
delay system, is going to work just as good as ABA. For sure.

Any thoughts?

> They you garbage collect the node when the refrence count
> is not zero right?

If the pre-decrement snapshot is the same, then is does not matter if the
snapshot is popped while the reference is incremented.

Thank you for your comments.

[Neill Clift [MSFT]]

"SenderX" <x...@xxx.xxx> wrote in message

news:DWfmb.20468$HS4.71355@attbi_s01...

> > Only took a brief look but don't you have an issue inside your
> > garbage release function.
>
> Thanks for the input!
>

...
No problem. Hard to tell if you agree with me from this mail though.
You could correct this by exchanging first then decrementing and
repushing if the decrement didn't go to zero. Obviously you could
test up front to limit the number of times you have to back out.
Problem with this is you have a thread that hols no locks that has to
run to free up stuff. Not quite lock free just liek the stuff I mention
below.

>
> Any thoughts?
>

You know in the Windows XP and Windows Server 2003 kernels
we did something similar the handle table code:

The pop code takes a shared lock based on a hash of the top of the
free list. We had I think 4 locks.
The push code looks to see if the lock for the hash of the node (really
the handle) its freeing is acquired. If its acquired it pushes the node
on an alternate list otherwise it does the normal push.
When all the nodes are on the alternate list we acquire all the locks
and transfer al the nodes over to the free list.

Very complicated to analyze and I don't think it worked as well
as just using a lock. I didn't realize this till I improved the locks.
Neill.

[Alexander Terekhov]

"Neill Clift [MSFT]" wrote: ....

<topic drift> ;-)

Neill, can you tell me how close does my "critical section" comes
to what you folks did for windows in the era of 386?

http://groups.google.com/groups?selm=3F914DCB.47C35771%40web.de

TIA.

regards,
alexander.

[Neill Clift [MSFT]]

"Alexander Terekhov" <tere...@web.de> wrote in message
news:3F9995BF...@web.de...

Before my time sorry. I started part way into Win2k. The oldest stuff
I have ever looked at is the nt4 codebase.
Why wouldn't they have just use inc like we do for
CriticalSections? We have the ownership passing issues of course.

Neill.

> regards,
> alexander.

[SenderX]

> No problem. Hard to tell if you agree with me from this mail though.

The condition you found could be/probably is real. I have to really look at
it.

The condition can be virtually eliminated, if a per-thread fifo queue was
used to delay pointer reuse.

In order for the condition to happen, a thread would have to fill its local
queue with a certain amount of nodes. Then the thread would have to pop
through all of the nodes to actually start reusing a particular node. The
whole problem stems from the rapid reuse of nodes. By delaying the reuse you
basically destroy ABA.

What do you think of this pointer delay schema?

The pointer delay could/might be able to be used to avoid ABA, without any
garbage collector whatsoever...

Humm...

> Problem with this is you have a thread that hols no locks that has to
> run to free up stuff. Not quite lock free just liek the stuff I mention
> below.

Could you please clarify?

The current algo is lock-free, as far as I can tell...

Are you talking about any of these issues:

http://groups.google.com/groups?selm=3F2EB82B.7B1EA981%40xemaps.com&rnum=1

P.S.

Here is the CAS64 version of my collector:

http://intel.forums.liveworld.com/thread.jsp?forum=242&thread=6721

[SenderX]

> No problem. Hard to tell if you agree with me from this mail though.

I totally agree now.

=)

The race-condition you found is now impossible, because I crammed a 16-bit
reference count and an offset to a garbage node stack, into "a single 32-bit
value."

This apparently had to be done. The race-conditions that evolved from not
keeping the reference count and garbage-node stack atomic, was too much.

> You could correct this by exchanging first then decrementing and
> repushing if the decrement didn't go to zero.

The correction involved some really nifty array offset tricks with the
32-bit garbage-node stack.

The cas32 garbage collector is now just as stable as the cas64 version.

Dyanamic, pointer based, lock-free collections are now possible on virtually
every 64-bit cpu.

Yeah!