December 2005 - Darwin-kernel

Re: Threading and Synchronization in Mass storage driver
by Yogesh P 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Hi Herb, Sorry Herb. Now I am replying to the old thread. I am actually implementing a threading and synchronization mechanism for accessing a request queue which is a queue of write data structure having singly linklist. I am creating kernel threads in my init() driver function. These threads access the request queue paralelly by using IOKit's IOLock synchronization primitives. Each thread acquire the lock calling IOLockLock() function and check the request queue whether it is empty or not. If the request queue is empty then the thread release the lock by calling IOLockUnLock() function. So that other threads can access the request queue. After loading the driver, threads get created successfully and each thread goes in a big while loop and the loop goes on infinitely. Now I have to put each thread on a conditional wait. The conditional wait means that if there is no request in the request queue the thread delays for a nanosecond and release the lock from the request queue for that specified time delay, and as soon as the request comes in the request queue, thread wake ups, acquire the lock and process that specified request. Is there any mechanism in IOKit so that I can put the thread on conditional wait ?? After that condition met, wake up that thread to process the specified request ?? Thanks in advance, Yogesh Pahilwan On Wed, 2005-12-07 at 22:01, Herb Petschauer wrote: > Again, this email seems to be a new thread. Why not just reply to the > old thread? > > Anway: http://developer.apple.com/documentation/Darwin/Conceptual/KernelProgrammin… > > You will find the entire document enlightening actually :-) > > H. > > On 07 Dec 2005 18:22:18 +0530, Yogesh P <pahilwan.yogesh(a)spsoftindia.com> wrote: > > 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/bogvardi%40gmail.com > > > > This email sent to bogvardi(a)gmail.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: Race condition in libkern's OSAtomicDequeue()
by Nikita Danilov 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com 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 (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: what version of gcc is apple using for it's kernel these days?
by Kevin Van Vechten 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com On Dec 7, 2005, at 6:15 PM, Herbert wrote: - Kevin _______________________________________________ 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.… The question says it all. Is Tiger compiled all the way through with 4.0? No, in fact none of it was. Most projects were compiled with gcc 3.3 as found in the gcc_os project. Projects with ppc64 support were built with gcc 3.5 as found in gcc_os_35. Starting in 10.4.3, some projects are built with gcc 4.0 as found in the gcc project, and I believe gcc_os_35 was deprecated in favor of gcc. This email sent to site_archiver(a)lists.apple.com

1 0

Re: moving from gcc 3.3 to gcc 4.0
by Kevin Van Vechten 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com On Dec 7, 2005, at 6:16 PM, Herbert wrote: - Kevin _______________________________________________ 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.… I have a driver I'm trying to update to Tiger and gcc 4.0. I'm getting missing header errors. If I move back to compiling it in Tiger with gcc 3.3 it works, but I'm guessing apple is using gcc 4 so I presume I must too. Any help out there? The Tiger kernel (8.0.0, build 8A428) was compiled with gcc 3.3, found in the gcc_os project. This email sent to site_archiver(a)lists.apple.com

1 0

moving from gcc 3.3 to gcc 4.0
by Herbert 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com Any help out there? _______________________________________________ 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.… I have a driver I'm trying to update to Tiger and gcc 4.0. I'm getting missing header errors. If I move back to compiling it in Tiger with gcc 3.3 it works, but I'm guessing apple is using gcc 4 so I presume I must too. This email sent to site_archiver(a)lists.apple.com

1 0

what version of gcc is apple using for it's kernel these days?
by Herbert 08 Dec '05

08 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com The question says it all. Is Tiger compiled all the way through with 4.0? _______________________________________________ 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 Terry Lambert 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com I wouldn't call it "erronous", it is just that it assumes that certain protocol guaranteeing that no ABA ever happens is followed by its clients. I'd say: (2) You can implement LL/SC from either RLL/RSC or CAS primitives: You can access the paper through the ACM portal, or from www.cs.dartmouth.edu/~spetrovic/papers/podc_LLSC.pdf There's also a 2004 IBM research report on using CAS at www.research.ibm.com/people/m/michael/RC23220.pdf -- 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 7, 2005, at 5:57 AM, Nikita Danilov wrote: Colin Hirsch writes: 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 LL/SC cannot be emulated through x86 lock prefix, if that's what you are talking about. (1) IMO, it's a bug; thanks for filing the bug report, Colin; do you have the # handy? I'd like to look at it... Efficient and practical constructions of LL/SC variables Annual ACM Symposium on Principles of Distributed Computing Proceedings of the twenty-second annual symposium on Principles of distributed computing Prasad Jayanti, Srdjan Petrovic - Dartmouth College Hanover, NH This email sent to site_archiver(a)lists.apple.com

1 0

Re: Race condition in libkern's OSAtomicDequeue()
by Kevin Van Vechten 07 Dec '05

07 Dec '05

site_archiver(a)lists.apple.com Delivered-To: darwin-kernel(a)lists.apple.com To be clear, I didn't write any of the following: On Dec 7, 2005, at 4:14 AM, Nikita Danilov wrote: Kevin Van Vechten writes: [...] 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 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.… 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. - 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. This email sent to site_archiver(a)lists.apple.com

1 0

Re: Threading and Synchronization in Mass storage driver
by Herb Petschauer 07 Dec '05

07 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:content-transfer-encoding:content-disposition:references; b=pvAe9u0jQLbf9at/3SRCUsAPT73jYOjmUqntY5k56J7ptCfSxniEGMdNMGNabAOVjJJYpvZNBdPof5Br4khWf8qmIGeNOvNgtPk8tGiGerYf9H0avvMsuwqumvUZPPJaVIMDF9xgl375NYhOkqJ2sAOZXAY+p/hrUWaOn5M2cXQ= Again, this email seems to be a new thread. Why not just reply to the old thread? Anway: http://developer.apple.com/documentation/Darwin/Conceptual/KernelProgrammin… You will find the entire document enlightening actually :-) H. On 07 Dec 2005 18:22:18 +0530, Yogesh P <pahilwan.yogesh(a)spsoftindia.com> wrote: > 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/bogvardi%40gmail.com > > This email sent to bogvardi(a)gmail.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: 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 Colin Hirsch writes: [...] > > 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 I wouldn't call it "erronous", it is just that it assumes that certain protocol guaranteeing that no ABA ever happens is followed by its clients. > 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 LL/SC cannot be emulated through x86 lock prefix, if that's what you are talking about. > 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... Usual practice to avoid ABA is to implement some sort of garbage collection based on RCU (read-copy-update). > > Regards, Colin 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