Re: Race condition in libkern's OSAtomicDequeue()
Re: Race condition in libkern's OSAtomicDequeue()
- Subject: Re: Race condition in libkern's OSAtomicDequeue()
- From: Colin Hirsch <email@hidden>
- Date: Wed, 7 Dec 2005 02:08:20 +0100
> We believe that OSAtomicCompareAndSwap32() is correct.
> The test program is flawed.
>
> The bug is that the compare and swap can succeed but the
> list head in oldListHead may have been recycled by someone
> else (that is, dequeued and enqueued again) so the list
> will become inconsistent -- newListHead will not refer to
> the correct new list head.
Erm, as I mentioned, the supposed bug is in OSDequeueAtomic,
not in OSAtomicCompareAndSwap32...
> You can not implement list queue and dequeue functions
> on ppc using a compare-and-swap function. You could do
> it if you could protect the entire operation inside a
> single lwarx/stwcx pair but the OSAtomic routines do not
> have a way to do that.
...and this is exactly the bug in OSDequeueAtomic that I was
referring to, i.e. my "test_broken.cc" test program was
created only to have an easily compilable and executable
program that uses the algorithm from OSDequeueAtomic - and
therefore crashes more or less immediately.
> The reason that list_fixed.cc works is because it implements
> a completely different algorithm for dequeuing that avoids
> the race condition by temporarily unlinking the entire list.
It was a quick hack to see how one can layer atomic dequeue
on atomic CAS and/or SWAP, however as somebody else already
mentioned to me privately, my "fixed" version still crashes
in some cases.
> Further, your compare-and-swap routines are not correct
> because they do not take into account the various processor
> bugs (some of which are quite severe if not handled). I
> strongly advise people to
Thank you for this hint, I will hunt for documentation
regarding these bugs as I might have other uses for an
atomic unconditional swap, an operation that does not
seem currently available.
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:
This email sent to email@hidden