83f
Subj : Re: Proxy GC
To   : comp.programming.threads
From : Joe Seigh
Date : Tue Sep 27 2005 11:13 am

I wrote:
> No, that's wrong now that I think about it a little more.
> You have to delete the proxy objects in the same order that
> you do the deletes on your data structure.  The formal
> reasoning for this is similar to the fifo logic used for
> the RCU+SMR.
> 

I should mention what that reasoning is since I don't think
I posted it in c.p.t. yet.

In lock-free you "delete" an object from a linked data structure
by making it unreachable and freeing it when it's no longer
referenced.  "deleted" objects can be reached from earlier
deleted objects since the pointers in the earlier deleted objects
aren't changed.  But earlier deleted objects can't be reached
from later deleted objects since by definition the earlier deleted
objects were unreachable at that time.  So freeing the objects
in the same order they were "deleted" is the safe way to go.

This allows lock-free traversal of the linked data structure.
RCU uses FIFO order.  The RCU+SMR I did used FIFO order.  APPC,
atomic pointer proxy collector, used FIFO order.   Chris can
confirm whether VZOOM uses FIFO order.   Note that the orginal
SMR algorithms published by Maged Michael don't use this and
can't be used to safely traverse linked data structures without
some other mechanism like reference counting to ensure safety.

Also the restriction I stated earlier about only using acyclic
traversal doesn't apply.  You can do cyclic traversals if you
have a data structure where that's meaningful.  If you "remember"
previously visited nodes and revisit them, you need to do it
in a method that safe given the GC.  For things like SMR you
need extra hazard pointers to remember with.  For reference
counting, you remember with an incremented reference count on
the remembered node.  RCU and other proxy schemes allow unlimited
remembering for the duration of the proxy guarded access.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.

0