Re: [boost] [proposal]AtomicallyThread-SafeReferenceCountingAlgorithm...

From: Chris Thomasson (cristom_at_[hidden])
Date: 2006-10-21 23:30:55

"Peter Dimov" <pdimov_at_[hidden]> wrote in message 
news:000601c6f582$10c92890$6507a8c0_at_pdimov2...
> Chris Thomasson wrote:
>> The basic technique for 'copying' is as follows:

[...]

> I thought that that might be the case. Won't you need to undo the XADD
> before unlocking and retrying, though? That, or use CAS.

I could use CAS, however I wanted to try an come up with an algorithm that 
can avoid CAS...

> The decrement thread may not care, but if another increment thread gets in 
> first, bad
> things happen; or am I missing something else?

This is where the reload-and-compare logic comes into play. It basically 
boils down to a simple coherent lock-based snapshot algorithm. Load before 
lock, reload after lock, compare, if equal you know that the previous load 
is coherent with the loaded value that you grabbed under the protection of 
the lock, if not unlock and retry... This will detect ALL swaps from shared 
locations that jump in just before we lock; I guess its kind of similar 
logic to the double check in SMR... If SMR did not perform that 
double-check, that it would be broken beyond repair... Just like my 
algorithm would. The snapshot logic does not touch any part of a refcount 
object. It operates on shared locations that contain pointers to refcount 
object.

It is not possible for a increment thread to load a pointer to refcount 
object, after it drops to zero, except in the condition I described earlier 
wrt ABA occurs; the algorithm is compatible with ABA.

A refcount object drop to zero condition means that there are no shared 
locations that contain any pointers to it. Any increment threads that have 
loaded pointers, will fail when they reload-and-compare. If one gets 
through, and their compare succeeds, it doesn't matter because it has 
already locked the associated spinlock, so it has exclusive access to the 
refcount. Since its reload and compare succeeded, that means it happened 
before any decrement thread got to execute; swaps happen before decrements 
(e.g., swap shared loc with 0, dec the old ptr). A decrement thread will 
always lock the spinlock before it calls the destructor, so it will wait for 
the one that got through the compare logic...

One thing I forgot to mention in my last post, nit-picking, your algorithm 
sketch invoked the user-provided destructor in the context of the 
critical-section provided by the lock that is associated with the count ptr. 
Can't call function pointers while you hold a lock?   ;)

Humm... I have to admit that if I used CAS, the algorithm logic would be 
easier to understand...

;)

>> IMHO, anytime you can reduce the number of atomic operations and/or 
>> memory
>> barriers is a plus...
>
> Maybe... Given a choice between the two, I would prefer to somehow 
> eliminate
> the spinlock in 'copy', though. :-)

You can get rid of it by using PDR... I have a hybrid version of my 
algorithm that uses it. Things get tricky here because of all of the RCU, 
SMR patents, not to mention my vZOOM patent... I think Boost could make use 
of one of the following collectors:

http://groups.google.com/group/comp.programming.threads/msg/f443b38cf7bbca8a
http://groups.google.com/group/comp.programming.threads/msg/a4a796e25a157ca1

One of them uses DWCAS... I have workaround, you can make use of offset 
trick explained here:

http://groups.google.com/group/comp.arch/msg/a3ebfe80363a4399

The other one uses CAS, however it operated on fixed number of threads. I 
also have a workaround using an offset trick, or another technique that 
allows for X number of threads to acquire proxy reference without 
blocking...

This is good because reads and writes can be lock-free, and reads and writes 
are no longer mutually excludable... Humm... I don't have docs on the 
algorithm... Wonder if I should post it; its experimental...