Re: Race condition in libkern's OSAtomicDequeue()
Re: Race condition in libkern's OSAtomicDequeue()
- Subject: Re: Race condition in libkern's OSAtomicDequeue()
- From: Dominic Giampaolo <email@hidden>
- Date: Tue, 6 Dec 2005 16:04:16 -0800
Colin Hirsch <email@hidden> writes:
Subject: Race condition in libkern's OSAtomicDequeue()
playing with all kinds of SMB-safe atomic operations I stumbled
over the
OSAtomicDequeue() and ...Enqueue() operations in the kernel source
code.
The reason I was looking there was that my first singly-linked-list
kept
crashing immediately (in a test program that does nothing but
enqueue()/
dequeue() in 3 threads on my Quad G5). However the libkern function
has
the same problem, as explained below and as can be verified easily
with
the source linked below.
Since I get this in digest mode I hope that there aren't
already 20 replies to this....
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.
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.
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.
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
And one last thing, you should almost always use the
*Barrier() variant of the OSAtomic routines. The only time
you do not need to use them is if you're updating a global
counter that has no other data dependencies. Any time you
use the atomic routines to update a data structure or to
indicate that something is ready or valid you need to use
the *Barrier() variants to insure that all the preceding
writes to memory are visible by the other processors.
--dominic
_______________________________________________
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