• 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: Nikita Danilov <email@hidden>
  • Date: Thu, 8 Dec 2005 13:46:06 +0300

Kevin Van Vechten writes:
 > To be clear, I didn't write any of the following:

Sorry, mea culpa, I trimmed original message over-zealously.

 >
 > On Dec 7, 2005, at 4:14 AM, Nikita Danilov wrote:
 >
 > > Kevin Van Vechten writes:
 > >
 > > [...]
 > >
 > >>>
 > >>> 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:

This email sent to email@hidden

References: 
 >Race condition in libkern's OSAtomicDequeue() (From: Colin Hirsch <email@hidden>)
 >Re: Race condition in libkern's OSAtomicDequeue() (From: Kevin Van Vechten <email@hidden>)
 >Re: Race condition in libkern's OSAtomicDequeue() (From: Nikita Danilov <email@hidden>)
 >Re: Race condition in libkern's OSAtomicDequeue() (From: Kevin Van Vechten <email@hidden>)

  • Prev by Date: Re: what version of gcc is apple using for it's kernel these days?
  • Next by Date: Re: Threading and Synchronization in Mass storage driver
  • Previous by thread: Re: Race condition in libkern's OSAtomicDequeue()
  • Next by thread: Re: Race condition in libkern's OSAtomicDequeue()
  • Index(es):
    • Date
    • Thread