site_archiver@lists.apple.com Delivered-To: darwin-kernel@lists.apple.com - Kevin On Dec 6, 2005, at 5:51 AM, Colin Hirsch wrote: Hi, But first the issue: 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. void * OSDequeueAtomic(void ** inList, SInt32 inOffset) { void * oldListHead; void * newListHead; do { oldListHead = *inList; if (oldListHead == NULL) { break; } return oldListHead; } In practice, my test program http://www.colin-hirsch.net/source/list_broken.cc http://www.colin-hirsch.net/source/list_fixed.cc Regards, Colin _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-kernel mailing list (Darwin-kernel@lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-kernel/site_archiver%40lists.a... You might want to report this to <http://developer.apple.com/ bugreporter/> in addition to posting to the list. There are some benefits to you for doing this. These lists are read by Apple engineers on a voluntary basis, whereas responding to bug reports is a bit more compulsory. And you'll be able to track its progress. 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. newListHead = *(void **) (((char *) oldListHead) + inOffset); } while (! OSCompareAndSwap((UInt32)oldListHead, (UInt32)newListHead, (UInt32 *)inList)); which uses the same list operations as libkern, crashes immediately, whereas the "fixed" version has been running for several minutes now, so it might actually be correct ;-) The crux is to temporarily take ownership of the complete list during dequeue() to prevent other CPUs from doing the aforementioned sequence of dequeues()s and enqueue()s, and then giving the rest of the list back (i.e. the list minus the dequeued head). I would be grateful if somebody (at Apple?) could double-check my analysis and the fixed version and, if applicable, crate a patch for libkern... (My fixed version is not fit for general purpose use since it does not detect an empty list.) PS: Yes, the commented "isync" in the fixed version is at the wrong place. This email sent to site_archiver@lists.apple.com