• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: Race condition in libkern's OSAtomicDequeue()
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

References: 
 >Re: Race condition in libkern's OSAtomicDequeue() (From: Dominic Giampaolo <email@hidden>)

  • Prev by Date: Re: Race condition in libkern's OSAtomicDequeue()
  • Next by Date: Re: POSIX Semaphores support.
  • Previous by thread: Re: Race condition in libkern's OSAtomicDequeue()
  • Next by thread: POSIX Semaphores support.
  • Index(es):
    • Date
    • Thread