Re: Race condition in libkern's OSAtomicDequeue()
Re: Race condition in libkern's OSAtomicDequeue()
- Subject: Re: Race condition in libkern's OSAtomicDequeue()
- From: Nikita Danilov <email@hidden>
- Date: Wed, 7 Dec 2005 16:57:24 +0300
Colin Hirsch writes:
[...]
>
> 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
I wouldn't call it "erronous", it is just that it assumes that certain
protocol guaranteeing that no ABA ever happens is followed by its
clients.
> 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
LL/SC cannot be emulated through x86 lock prefix, if that's what you are
talking about.
> 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...
Usual practice to avoid ABA is to implement some sort of garbage
collection based on RCU (read-copy-update).
>
> Regards, Colin
Nikita.
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Darwin-kernel mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden