Proxy GC
Joe Seigh
Even though you can only do acyclic traversals, not cyclic,
traversals with RCU+SMR, you can do cyclic traversals with
proxy based GC. Provided your data structure logic supports
lock-free cyclic traversal.
Also, if you're using a mutex on the write side, you don't
need to hold it while calling the proxy defer routine as
long as the proxy object swap logic maintains FIFO order
(proxy objects are freed in same order as the swap order).
This means I can put the Kung Fu monkey through the trees
swap logic back into atomic pointer proxy collector defer
routine (appc::defer) if and when I ever release it again.
Could even do it for other proxy GC like RCU+SMR as well
though the latter is pretty much moot.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Joe Seigh
>
> Also, if you're using a mutex on the write side, you don't
> need to hold it while calling the proxy defer routine as
> long as the proxy object swap logic maintains FIFO order
> (proxy objects are freed in same order as the swap order).
> This means I can put the Kung Fu monkey through the trees
> swap logic back into atomic pointer proxy collector defer
> routine (appc::defer) if and when I ever release it again.
> Could even do it for other proxy GC like RCU+SMR as well
> though the latter is pretty much moot.
>
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.
Joe Seigh
> 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
> Also the restriction I stated earlier about only using acyclic
> traversal doesn't apply. You can do cyclic traversals if you
Yet another correction here. You can't do cyclic traversals in
RCU+SMR, just for proxy collectors. This is just for the record.
Nobody will be using this stuff for a while yet so there's plenty
of time to bang out the details.
Chris Thomasson
> 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.
Well, yes and no... ;)
It depends on the synchronization strategy an application chooses to use.
The algorithm basically requires threads to "episodically or periodically"
perform a "synchronization operation", that's all. An application can decide
to take full control of this requirement ( very portable; FIFO not
required ), or it can let the algorithm take care of it ( os and/or cpu
dependant; FIFO required ).
I prefer the first method, because it gives you control over the polling
logic, and its highly portable.
[...]
> RCU and other proxy schemes allow unlimited
> remembering for the duration of the proxy guarded access.
My algorithm refers to these types of references as "non-persistent",
because they simply cannot persist across "synchronization points". However,
it does defines another type of reference that can indeed persist across
them. The algorithm allows a thread to acquire basically any number of these
types of "persistent references".
With persistent references, you could do recursive/cyclic traversals with
synchronization points in random places throughout the duration of the
traversal, no problem. Also, VZOOM allows a thread to safely traverse, while
calling user-provided function pointers that may call synchronization points
and/or traverse another structures. I don't think that there are very many
schemes out there that can do that...
;)