[zeromq-dev] atomic ops

[john skaller]

On 09/02/2012, at 8:50 AM, Martin Lucina wrote:

>> 
>> First, I surely wouldn't trust inline assembler, and I'm suspicious of
>> "lock; xadd". This code also won't be selected except on x86 or x86_64.
> 
> What exactly do you find suspicious about "lock; xadd"? Standard way to
> implement atomics on x86.

History... also note, atomic isn't really related to memory barrier.

Hmm .. I'm thinking this through online.. but I think it can't work,
atomic or not.  ... hmm .. ouch...

There's a standard problem here with ref counting here,
I will have to check the code does fall into the trap.
Actually, I think it must because you cannot transfer
data from one thread to another without a semaphore based
double handshake.

It goes like this:

	a) there is a pointer, 2 reference
	b) make a copy of the pointer
	c) increment the refcount
	d) CORE DUMP

Why? Because the references reduced to 0 before we could
grab the pointer. Lets try the other way:

	a) increment the ref count
	b) grab the pointer
	c) CORE DUMP

It didn't help. Another thread STILL deleted the pointer
before we could increment the ref count.

It follows atomic increment of the ref count isn't enough.
You HAVE to set a mutex, TEST the refcount hasn't gone
to zero, then increment it, and grab the pointer.

If the refcount does go to zero you're screwed.
The object is gone before you can grab it.

Lets consider an actual scenario and see what is required.
A thread A creates a refcounted object and wants to pass it to B.

Thread A makes the object with refcount 1, then it waits using a 
semaphore until B gets the object and increments the count to 2.
Then A decrements the count by one, and deletes the object
if it goes to 0.

There's no way to do this with mere atomics. You HAVE to use
a semaphore and synchronise the sender A and receiver B
threads.

In Felix, I implement this with a monitor object. It REQUIRES a double
hand-shake. The operation isn't ref-counting (Felix is garbage collected),
just pointer passing. But it requires a double handshake all the same
(because the pointer has to be stored somewhere for the object to
be considered reachable).

Now, in the special case a thread A is creating a new object,
it can just pass the object to B with refcount 1. B then grabs
the object and doesn't bother to increment the refcount.

Python uses this trick. It ONLY works if you certainly have a
producer consumer situation. 

In 0MQ inproc this is not the case (I guess!). Thread A may pass
a message to thread B with any refcount. It cannot work.

As before the supplier must increment the refcount on the expectation
the consumer will grab the object without doing so. This certainly
cannot support a fanout. In fact if you already know it's a 1-1 transaction
you don't need to bother with a ref-count at all.

Ok .. so all the above is just non-serious musing .. but you can see why I'm suspicious.

The standard "lock free" way to do this is to do a tentative transfer and then
check it succeeded. Eg you increment the ref count then grab the pointer
then you check the refcount is what you set it to. If not, you retry,
unless it dropped to zero in which case you're screwed.

--
john skaller
skaller at users.sourceforge.net