December 2005 - Darwin-kernel

Re: Race condition in libkern's OSAtomicDequeue()
by Colin Hirsch 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com User-agent: Mutt/1.5.9i > > > 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. 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 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 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... Regards, Colin _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Threading and Synchronization in Mass storage driver
by Yogesh P 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Hi Herb, Thanks for your valuable suggestion about the threading and synchronization in Mac OS X. I am also thankful to Garth for his suggestions. Now my driver is not getting crash when I call the IOCreateThread() function. Is there any API to put the kernel thread in a wait for a nanosecond in sleep in IOKit?? Thanks, Yogesh _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Re: Race condition in libkern's OSAtomicDequeue()
by Nikita Danilov 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com 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 (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Re: POSIX Semaphores support.
by Terry Lambert 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Hi, On 12/6/05, Eric Welch <ericw(a)innosys.com> wrote: Miguel, For some time OSX has had Posix thread support including semaphores. -- Terry _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… On Dec 6, 2005, at 12:30 PM, Miguel Filipe wrote: In that case, my app has a very strange behaviour on OSX, I make use of sem_init(), sem_wait() & sem_post(), and in OSX my threads never wait on sem_wait(). MacOS X supports named POSIX semaphores, but not unnamed POSIX semaphores. I expect you must be trapping SIGSYS to prevent your program exiting because of an unsupported system call on the call to sem_init(), since it's implementation is a return of the error ENOSYS. I googled after that problem and saw a lot of "OSX doesn't support POSIX Semaphores", after which I irresponsibly stopped looking for the cause of the problem. Apparently that could be the case in OSX 10.3, but I'm using 10.4. Is there any kind of peculiarity in how I should use posix semaphores? (header files, semaphore inicialization or linker flags...) The first thing you should do is #include <unistd.h> and conditionalize your use of POSIX semaphores on the manifest constant _POSIX_SEMAPHORES, e.g.: #if ((_POSIX_SEMAPHORES - 200112L) >= 0) /* This platform fully supports POSIX semaphores */ #else #if defined(__APPLE__) /* This platform can support POSIX named semaphores, but not unnamed semaphores */ #else /* this platform requires that I Google code for P/V semaphores and include it here */ #endif #endif The proper list was more likely "unix-porting", but that's OK; this question comes up from time to time. This email sent to site_archiver(a)lists.apple.com

1 0

Re: Race condition in libkern's OSAtomicDequeue()
by Colin Hirsch 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com User-agent: Mutt/1.5.9i > 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 (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Re: Race condition in libkern's OSAtomicDequeue()
by Dominic Giampaolo 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Subject: Race condition in libkern's OSAtomicDequeue() 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 (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… Colin Hirsch <share-darwin(a)think42.com> writes: 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. This email sent to site_archiver(a)lists.apple.com

1 0

Re: Where is the filename?
by Don Brady 06 Dec '05

06 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Re: POSIX Semaphores support.
by Miguel Filipe 06 Dec '05

06 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=rpWXCW1TlRwAFTJsAl6lR7bMZSo1lDQlVu8ikDlnaOLGEcwfjZTprlyfX9f7KMVMe8wS1EUW0l9uMUoz5soIsLof3kJm6nTQrh0luMdCv2HyjyGPNc/cKKvAM9xAiFJEcoah/m26xKRmdVP3vUO9vPWM2soNRVvprtlK25ZN0Ko= _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0

Re: POSIX Semaphores support.
by Eric Welch 06 Dec '05

06 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Miguel, For some time OSX has had Posix thread support including semaphores. eric On Dec 6, 2005, at 11:54 AM, Miguel Filipe wrote: Hi, are there any plans to add Posix semaphores to OSX? Several pure unix aplications make use of it.. (mine also.. ) Thanks in Advance. _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… -- Miguel Sousa Filipe _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/ericw% 40innosys.com This email sent to ericw(a)innosys.com This email sent to site_archiver(a)lists.apple.com

1 0

POSIX Semaphores support.
by Miguel Filipe 06 Dec '05

06 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=rq0YWHS57FClYe+gEs0v3Zm+eZ48W2xpdrvmegIEQaQLTS7SLve3dbfZlpCwmX5wefL3OqS1uD7+4Sxu18ptbDHr/gX8eu/kkb4MqCc/+ZJpFKr3XzGMsSlzh7TqAPdCVlFY3eElXuVPGny4Z6UOLdlmJrhhQo487Nb59SQPcw0= _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.… This email sent to site_archiver(a)lists.apple.com

1 0