February 2005 - Darwin-dev - lists.apple.com

Re: Thread safety question
by Matt Watson 20 Feb '05

20 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com matt. _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… [Apologies for boring subscribers with more nitpicking which might not be directly relevant to the Darwin platform, threading and parallel programming pitfalls are just too much fun to pass on] While this is an interesting topic, it's really outside the scope of darwin-dev. I suggest reading the threads on double-checked initialization in the comp.programming.threads newsgroup, where this has been discussed ad nauseum. This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Eric Gouriou 19 Feb '05

19 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com [Apologies for boring subscribers with more nitpicking which might not be directly relevant to the Darwin platform, threading and parallel programming pitfalls are just too much fun to pass on] Apologies for using examples not immediately relevant to Darwin, but I don't want this idiom to become more prevalent. It is broken, even if in not so obvious ways. e.g void * myVariable = 0; volatile UInt32 sentinel = 0; void* instance(void) { if ( !OSCompareAndSwap( 0, -1, &sentinel)) { /* initialize variables */ if ( ! myVariable ) myVariable = allocateObject(); /* etc */ sentinel = 1; } else { while (sentinel != 1) /* yield, whatever that function is...pthread_yield()? */; } return myVariable; } Grabbing an uncontented lock shouldn't be too expensive compared to invoking a successful OSCompareAndSwap. So someone objecting to the trivial idiom on the basis of performance might not like this version much. Note also that the compare&swap version causes two writes to the sentinel, while the proposed double-checked idiom attempts to perform a single read once initialization occurred (very cache and SMP/cc-NUMA friendly). So the idiom above won't please performance seekers. I have a hard time constructing a scenario where making myVariable volatile would be a concern for performance. If one uses a function instance(), then presumably no direct access to myVariable should occur outside of this function. The price of thread-safety has to be paid somewhere. You might be thinking of users of this global using an idiom such as: void* myLocal = myVariable; if (NULL == myLocal) { myLocal = instance() } foo = myLocal->field1; The problem is that this would not be thread-safe, at least on some systems with relaxed memory ordering. Reading a non-NULL myVariable is not a guarantee that reading myLocal->field1 will return the expected value. To guarantee this, one needs to have an ordering constraint between the writes that can occur in instance() and the reads occurring in this snippet. For those into formal correctness proofs, the following document explain why this is the case, in Table 9 on page 23: <URL:http://www.intel.com/design/itanium/downloads/25142901.pdf> instance() would perform the operations in the left column (p), while the snippet above performs the operations in the right column (q), with x being the address of myVariable->field1 and y being the address of myVariable. There might be cases for which using a separate sentinel makes sense (e.g., for variables where no value can be used to denote the uninitialized state). However one cannot ever bypass the sentinel (and the price of 'volatile') and access the global directly. I do not understand the difference this could make. Modern compiler can (legally) optimize this intermediate step away. Or am I missing something ? Regards - Eric _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… On Feb 19, 2005, at 14:28, Matthew T. Russotto wrote: On Feb 19, 2005, at 12:40 PM, Eric Gouriou wrote: Doesn't the use of a compare-and-swap or similar pattern (such as test-and-set) solve this problem without a lock at all? This idiom is a custom spinlock (or yielding spinlock) variant of the trivial (and correct) initialization idiom that always grabs a lock. The reason double-checked initialization is used is the perception (real or not) that grabbing a lock is too expensive to afford. The version above also relies on the compiler/process honoring the ordering properties on the write "sentinel = 1". If one is willing to assume that this property stands, then the idiom that doesn't use Compare&Swap is valid. You could use myVariable as the sentinel also but that introduces other dependencies, and besides you probably don't want to declare it volatile. If one is concerned about the cost of volatile, then the only viable approach is to avoid accessing the global too often, by invoking instance() rarely and caching the result in a local variable when possible. Since accessing a global has its cost (GOT/PLT access), it is often a good idea anyway if performance is paramount, even when volatile isn't used. YMMV. If you were to do that, to avoid the inline-ordering problem you'd assign the output of allocateObject to a local variable, then to the global. -- Eric Gouriou eric.gouriou(a)pobox.com This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Matthew T. Russotto 19 Feb '05

19 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Apologies for using examples not immediately relevant to Darwin, but I don't want this idiom to become more prevalent. It is broken, even if in not so obvious ways. e.g void * myVariable = 0; volatile UInt32 sentinel = 0; void* instance(void) { if ( !OSCompareAndSwap( 0, -1, &sentinel)) { /* initialize variables */ if ( ! myVariable ) myVariable = allocateObject(); /* etc */ sentinel = 1; } else { while (sentinel != 1) /* yield, whatever that function is...pthread_yield()? */; } return myVariable; } _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… On Feb 19, 2005, at 12:40 PM, Eric Gouriou wrote: Doesn't the use of a compare-and-swap or similar pattern (such as test-and-set) solve this problem without a lock at all? You could use myVariable as the sentinel also but that introduces other dependencies, and besides you probably don't want to declare it volatile. If you were to do that, to avoid the inline-ordering problem you'd assign the output of allocateObject to a local variable, then to the global. This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Eric Gouriou 19 Feb '05

19 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com void* myVariable = 0; NSLock* myLock; // assume lock has been initialized in main void* instance(void) { if ( ! myVariable ) { [myLock lock]; if ( ! myVariable ) myVariable = allocateObject(); [myLock unlock]; } return myVariable; } In practice ? maybe. In theory ? no. If allocateObject gets inlined, the compiler _or_ processor could process the write into myVariable (making it non-NULL) before all the necessary allocation steps are complete. This is legal since no ordering information has been specified in the source. Since inter-procedural and inter-module inlining is one of the best way to expose optimization opportunities, you can bet that compilers will increasingly use it. This practice is only valid if the compiler/processor guarantees that all or part of the ordering implied by the source is honored at execution time. Some platforms guarantee that, some don't. I don't know enough about the PPC semantics, but I can tell you that this is not valid on Itanium cpus. Even if we disregard reordering (legally) performed by the compiler, the processor is free to perform loads and stores out of order, _unless_ they are marked as ordered, using the 'acquire' and 'release' qualifiers (ld.acq, st.rel) or if a (full) memory fence instruction is used. 'st.rel' and 'ld.acq' work in pairs: Some thread Another thread st .... ld.acq rx=[addr] st .... ld ... st.rel [addr]=newVal ld ... The semantics are that if a ld.acq sees the new value, then subsequent loads following this ld.acq will also see the values that were set in stores preceding the st.rel. st.rel is a write barrier, while ld.acq is a load barrier. To use the pattern above in a valid way, myVariable should be declared volatile. The Itanium compilers I am familiar with will emit a ld.acq on reading a volatile variable, and a st.rel when setting a volatile variable. My understanding is that the Alpha processor had similar requirements to guarantee correctness. Unfortunately the C standard does not offer enough guarantees to make this usage trivially portable, one has to check the semantics of each target platform (compiler + processor) to validate the idiom. At this point I do not know of any platform where the usage of volatile won't work, yet I'll repeat that this is not guaranteed by any standard (C<year>/Posix/Unix <year>/etc.). Apologies for using examples not immediately relevant to Darwin, but I don't want this idiom to become more prevalent. It is broken, even if in not so obvious ways. Regards - Eric _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… On Feb 18, 2005, at 06:59, Rich Seibel wrote: This is a slight variation of the double check pattern that the ACE (Open Source MiddleWare in C++) uses, shown below. This will always work on a uni-processor. If pre-emption occurs and another thread gets scheduled _on the same processor_ and enters the same function, then it could see myVariable non-NULL but an incomplete initialization. The problem comes when there are multiple CPUs and cache between the shared memory. The combined compiler, OS, and hardware must be able in insure that a variable, specifically myVariable above, is treated atomically across the processors. That is, myVariable, if changed in one processor and stored to memory, must be seen as changed on any other processor even if still in cache on that processor. Secondly, the lock must work atomically across all processors. The second requirement is a must for any multi-processor OS, so we can assume that one is true. Given our experience with ACE across many processors, we have only seen one we had to add a machine instruction to correct the first requirement. However, I am not a darwin developer and I would like assurance from them that this is true, in both the examples shown. -- Eric Gouriou eric.gouriou(a)pobox.com This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Rich Seibel 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com On Feb 18, 2005, at 11:27 AM, Shawn Erickson wrote: On Feb 18, 2005, at 8:33 AM, Ernesto Corvi wrote: Hi Steve. volatile BOOL variable_initialized=NO; Actually this isn't correct. This is exactly the kind of assurance I was looking for. If on 10.3 or later consider... static void* mySingletonObject = 0; if (mySingletonObject == nil) { mySingletonObject = allocateObject(); } } return mySingletonObject; } This is good information to have going into the future. Thank you very much, Rich -Shawn _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… The problem you might encounter here, if you have global register allocation turned on, is that the compiler might cache 'variable_initialized' in a register. So let's contemplate this scenario: Thread1 -> Caches variable_initialized into R2, gets swapped out between the 'if ( !variable_initialized )' and the '[myLock lock]'. Thread2 -> Executes the entire function and initializes the variable. Thread1 -> Resumes execution, but since it cached 'variable_initialized' into R2, it still thinks its unitialized, and initializes again. A portable solution to this problem is to declare 'variable_initialized' as: The 'volatile' keyword hints the compiler not to cache the variable and force direct access to the variable every time it's accessed. Calling lock (in fact any function) will force the compiler to reload the external variable for all following code since the function call could have changed it (threads doesn't affect this requirement). So the use of volatile shouldn't be needed nor is it really that portable because of the freedoms of implementation that exist for the keyword volatile (however it is likely going to do exactly what you are expecting). It can also come with overhead depending on how your volatile var is used. See... <http://groups.google.com/groups?selm=3A5F0778.8B60A01F%40compaq.com> ...and... <http://lists.apple.com/archives/darwin-development/2004/Mar/ msg00154.html> Calling lock will put out a memory barrier so it will insure that data is written/read in order such that "myVariable" will be correct to the current state while inside of lock bracketing (assuming all other writes to that variable are also protected by the same lock, other reads should be wrapped as well but that is not important here). In other words it is best to use provided locking constructs when having to do shared access like this from multiple threads (of course sometimes the checking of a boolean, etc. for say an exit from a working loop doesn't always require the use of any locking or even volatile depending on what is needed and how things function). The fast check pathway however could result in a bogus pointer getting returned if the write of a pointer to the variable isn't atomic but on PPC for a 32b value I believe it will be (won't get a partial pointer read out of it, all or nothing) but it is a fragile thing to be doing without consideration for future/different system architectures. True. This code has been in use for a long time and we haven't run into that processor yet, but we will have to be watchful on every new processor to come along. I question if the use of this fast check is really needed...? Do you know how often this function is called such that avoiding locking is actually gaining you anything? Often best to go with simpler code when possible. If it is a hot function why not move initialization to some up front function call and then have all later use just assume the variable has been initialized. In the case of ACE, this code is used to instantiate singletons, so the probability that the lock will be taken more than once per singleton is essentially zero. Since, this is middleware used by thousands of applications, I can't even guess the number of times it is called, the range is a few to billions. The code has been around for over ten years and used on dozens of different platforms, so any change would certainly require a proven failure. void* instance(void) { // possibly use self in the following if this is actually going to be a class or instance method @synchronized(someObjectOrUniqueValue) { I am not familiar with this syntax or function. Can it provide synchronization without a context switch? This email sent to site_archiver(a)lists.apple.com

1 0

Re: login item for all users
by Pete Gontier 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com User-agent: Microsoft-Entourage/10.1.6.040913.0 circa 2/18/05 4:28 AM, "Finlay Dobbie" <finlay.dobbie(a)gmail.com> wrote: >> To be clear mach_init_per_user.d IS a valid startup >> mechanism for daemons which replaced StartupItems as of 10.3.x. > It didn't replace StartupItems, though. More change in this area is > coming with Tiger and launchd (see the 'initng' project at > <http://www.opensource.apple.com/darwinsource/WWDC2004/>), fwiw. I just read some of these docs. Factoring is yummy, but I'm concerned about how much backward compatibility we can expect. I've just rather laboriously migrated a startup item to a per-user bootstrap daemon (though I must admit I did this not in pursuit of architectural purity but because my hand was forced by an obscure technicality). It would be a frustrating shame if it broke so soon. Also, what do these changes coming in Tiger imply for the techniques described in the unpublished-except-via-request-to-DTS Technote 2120 (née 2077)? -- Pete Gontier http://www.m-audio.com/ _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Shawn Erickson 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com On Feb 18, 2005, at 8:33 AM, Ernesto Corvi wrote: Hi Steve. volatile BOOL variable_initialized=NO; Actually this isn't correct. If on 10.3 or later consider... static void* mySingletonObject = 0; return mySingletonObject; } -Shawn _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… The problem you might encounter here, if you have global register allocation turned on, is that the compiler might cache 'variable_initialized' in a register. So let's contemplate this scenario: Thread1 -> Caches variable_initialized into R2, gets swapped out between the 'if ( !variable_initialized )' and the '[myLock lock]'. Thread2 -> Executes the entire function and initializes the variable. Thread1 -> Resumes execution, but since it cached 'variable_initialized' into R2, it still thinks its unitialized, and initializes again. A portable solution to this problem is to declare 'variable_initialized' as: The 'volatile' keyword hints the compiler not to cache the variable and force direct access to the variable every time it's accessed. Calling lock (in fact any function) will force the compiler to reload the external variable for all following code since the function call could have changed it (threads doesn't affect this requirement). So the use of volatile shouldn't be needed nor is it really that portable because of the freedoms of implementation that exist for the keyword volatile (however it is likely going to do exactly what you are expecting). It can also come with overhead depending on how your volatile var is used. See... <http://groups.google.com/groups?selm=3A5F0778.8B60A01F%40compaq.com> ...and... <http://lists.apple.com/archives/darwin-development/2004/Mar/ msg00154.html> Calling lock will put out a memory barrier so it will insure that data is written/read in order such that "myVariable" will be correct to the current state while inside of lock bracketing (assuming all other writes to that variable are also protected by the same lock, other reads should be wrapped as well but that is not important here). In other words it is best to use provided locking constructs when having to do shared access like this from multiple threads (of course sometimes the checking of a boolean, etc. for say an exit from a working loop doesn't always require the use of any locking or even volatile depending on what is needed and how things function). The fast check pathway however could result in a bogus pointer getting returned if the write of a pointer to the variable isn't atomic but on PPC for a 32b value I believe it will be (won't get a partial pointer read out of it, all or nothing) but it is a fragile thing to be doing without consideration for future/different system architectures. I question if the use of this fast check is really needed...? Do you know how often this function is called such that avoiding locking is actually gaining you anything? Often best to go with simpler code when possible. If it is a hot function why not move initialization to some up front function call and then have all later use just assume the variable has been initialized. void* instance(void) { // possibly use self in the following if this is actually going to be a class or instance method @synchronized(someObjectOrUniqueValue) { if (mySingletonObject == nil) { mySingletonObject = allocateObject(); } } This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Ernesto Corvi 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This email sent to site_archiver(a)lists.apple.com BOOL variable_initialized=NO; void* myVariable; NSLock* myLock; // assume lock has been initialized in main - (void)isThisThreadSafe; { if ( !variable_initialized ) { [myLock lock]; if ( !variable_initialized ) myVariable = allocateStuff(); variable_initialized = YES; [myLock unlock]; } return myVariable; } Can anyone confirm this, or offer advice on an alternate solution? Thanks. -steve

1 0

bad fsync?
by A.M. 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com MySQL makes the following claim at: http://dev.mysql.com/doc/mysql/en/news-4-1-9.html _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… "InnoDB: Use the fcntl() file flush method on Mac OS X versions 10.3 and up. Apple had disabled fsync() in Mac OS X for internal disk drives, which caused corruption at power outages." First of all, is this accurate? A pointer to some docs or a tech note on this would be helpful. This change implies that the regular fsync() is somehow intentionally crippled on 10.3+. What is the reasoning for this and does it truly have the consequences that MySQL claims (namely, corruption)? This email sent to site_archiver(a)lists.apple.com

1 0

Re: Thread safety question
by Rich Seibel 18 Feb '05

18 Feb '05

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com On Feb 18, 2005, at 4:47 AM, Steve Gehrman wrote: BOOL variable_initialized=NO; void* myVariable; NSLock* myLock; // assume lock has been initialized in main - (void)isThisThreadSafe; { if ( !variable_initialized ) { [myLock lock]; if ( !variable_initialized ) myVariable = allocateStuff(); variable_initialized = YES; [myLock unlock]; } return myVariable; } void* myVariable = 0; NSLock* myLock; // assume lock has been initialized in main void* instance(void) { if ( ! myVariable ) { [myLock lock]; if ( ! myVariable ) myVariable = allocateObject(); [myLock unlock]; } return myVariable; } Thanks, Rich Thanks. -steve _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/seibel_r%40ociweb.com _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… I have an object that lazily initializes it's variables when accessed and I want it to be thread safe, but I would like to avoid locking and unlocking the lock everytime every method is called. Below is one solution, but I don't think it is thread safe. I'm assuming that if variable_initialized is YES, then dataPtr must be valid, but I'm afraid that the OS might not guarantee when and how data is flushed, so could it be possible for variable_initialized and myVariable to be invalid? Can anyone confirm this, or offer advice on an alternate solution? This is a slight variation of the double check pattern that the ACE (Open Source MiddleWare in C++) uses, shown below. This will always work on a uni-processor. The problem comes when there are multiple CPUs and cache between the shared memory. The combined compiler, OS, and hardware must be able in insure that a variable, specifically myVariable above, is treated atomically across the processors. That is, myVariable, if changed in one processor and stored to memory, must be seen as changed on any other processor even if still in cache on that processor. Secondly, the lock must work atomically across all processors. The second requirement is a must for any multi-processor OS, so we can assume that one is true. Given our experience with ACE across many processors, we have only seen one we had to add a machine instruction to correct the first requirement. However, I am not a darwin developer and I would like assurance from them that this is true, in both the examples shown. This email sent to seibel_r(a)ociweb.com This email sent to site_archiver(a)lists.apple.com

1 0