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.
- 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. :-)
Nikita.
_______________________________________________
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
