> > > In xnu-792.6.22/libkern/gen/OSAtomicOperations.c the following code is
> > > used for the dequeue. I believe the problem to be that the value in
> > > newListHead is not necessarily current by the time the atomic CAS is
> > > executed.
> > >
> > > This is a pretty contrived case, as it requires one thread to be
> > > preempted between the assignment to newListHead and the CAS, and
> > > then two (or more) elements must be dequeued and at least the first
> > > dequeued element be put back again [last] so that the CAS succeeds.
>
> This is a common predicament of CAS based lock-free data-types (if I
> understand your description correctly). It's called ABA problem, when
> CAS controlled pointer changes from A to B and then back to A, leading
> to falsely positive CASs. Common solutions include:
>
> - do not use CAS, use LL/SC (load-linked, store-conditional)
> instruction pair instead. That requires hardware support, of course.
I have now found an implementation using LL/SC for the PPC in the Darwin
kernel, however what disconcerts me is the fact that the erronous CAS
based solution is still part of the kernel source(!), and that AFAIK x86
does not have LL/SC instructions [and a whole bunch of other read-modify-
write instructions can be made atomic with a lock prefix] - I posted a bug
report with Apple so that they remove this algorithm and, in particular
don't use it for their x86 implementation.
> - data-type clients have to guarantee that ABA never happens. E.g.,
> elements removed from queue are never put back, or only put back
> sufficiently late. There is a whole cottage industry built around these
> techniques. :-)
Now that I read this - perhaps the functions are only used for moving data
from one thread to another, however I would expect some data structure that
behaves like a queue, rather than a stack...
Regards, Colin
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Darwin-kernel mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/darwin-kernel/email@hidden
This email sent to email@hidden
