site_archiver@lists.apple.com Delivered-To: darwin-dev@lists.apple.com Thread-index: AciqGISPww+FNhYLEd23XAAdT0T19A== Thread-topic: Synchronization primitives (was:Re: Where is atomicqueue?) User-agent: Microsoft-Entourage/11.4.0.080122 On 4/29/08 12:22 PM, "Steve Sisak" <sgs-lists@codewell.com> wrote:

At 11:11 AM -0400 4/29/08, Army Research Lab wrote:

...

I want to be able to use this from user space. Are there any functions that are supported from user space and capable of all that the OSAtomic* functions are?

I'm not sure how far back the OS* versions are declared by that name, but there's some version of CompareAndSwap32 in every Mac OS version since OpenTransport (Unix STREAMS) was introduced -- Mac OS 7.5, I think.

CompareAndSwap() from <DriverServices.h> is available back to Mac OS 8.0.

OTCompareAndSwap32() from <OpenTransport.h> is available back to the beginning of time.

As I mentioned previously, given CompareAndSwap32(), and CompareAndSwapPtr (correct size for a pointer) you can implement everything else.

-------

BTW, if you ever need really fast atomic queues from user space, look at OTLifo in <OpenTransport.h>.

These just implement a singly lined list with atomic enqueue/dequeue.

To implement a fast FIFO, you use two OTLifo's (call them head and tail) and a lock.

You enqueue (OTLIFOEnqueue()) to head and (OTLIFODequeue()) from tail.

If tail becomes empty:

if (head) is not empty: Take the lock retry the deque from case it's been filled while waiting If you get nil: Steal the contents of head (OTLIFOStealList()) If not nil: Reverse the list you get (OTReverseList()) Set fHead of tail to the reversed list Deque the first element as the result Release the lock

This has the desirable attributes of:

1) enqueuing to head never blocks 2) dequeing from tail only blocks when tail is empty.

(This is part of the reason why OpenTransport was so fast -- it didn't block much and used very clever memory allocation to avoid copying data much)

The above can all be implemented in C given an implementation of CompareAndSwapPtr(). (I could probably send you some code if you need it)

Implementing this is a good interview question. :-)

I'm not worried about implementing it, I've done it WAAAAY too many times already (I'm an embedded systems programmer, when you don't have a C standard library because its too big, and the OS is whatever you cook up...) I'm just a) ignorant; I don't know much about mac programming and b) lazy; if someone else already wrote it, I'm going to use their version of it. BTW large chunks of OpenTransport.h are marked AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION _10_4, including various bits that have to do with OTLifo. If your code still uses it, you may need to update it to something else. Thanks, Cem Karan _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev@lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.appl... This email sent to site_archiver@lists.apple.com