Re: [msysGit] Re: [PATCH/RFC] mingw: implement PTHREAD_MUTEX_INITIALIZER
- From
- Kyle Moffett <kyle@moffetthome.net>
- Date
- Oct 27, 2011, 23:20 UTC
- Message-ID
- <CAGZ=bqKA7P_FJz447AZA5HjWdghKnZqAWGuKAuvjsGp5bAGC1w@mail.gmail.com>
- In-Reply-To
- <20111028080033.57FC.B013761@chejz.com>
On Thu, Oct 27, 2011 at 19:00, Atsushi Nakagawa <atnak@chejz.com> wrote:
Show 55 quoted lines
> Erik Faye-Lund <kusmabite@gmail.com> wrote: >> On Wed, Oct 26, 2011 at 5:44 AM, Kyle Moffett <kyle@moffetthome.net> wrote: >> > On Tue, Oct 25, 2011 at 16:51, Erik Faye-Lund <kusmabite@gmail.com> wrote: >> >> Thanks for pointing this out, I completely forgot about write re-ordering. >> >> >> >> This is indeed a problem. So, shouldn't replacing "mutex->autoinit = >> >> 0;" with "InterlockedExchange(&mutex->autoinit, 0)" solve the problem? >> >> InterlockedExchange generates a full memory barrier: >> >> http://msdn.microsoft.com/en-us/library/windows/desktop/ms683590(v=vs.85).aspx >> > >> > No, I'm afraid that won't solve the issue (at least in GCC, not sure about MSVC) >> > >> > A write barrier in one thread is only effective if it is paired with a >> > read barrier in the other thread. >> > >> > Since there's no read barrier in the "while(mutex->autoinit != 0)", >> > you don't have any guaranteed ordering. > > Out of curiosity, where could re-ordering be a problem here? I'm > thinking probably at "EnterCriticalSection(&mutex->cs)" and the contents > of "mutex->cs" not being propagated to the waiting thread. However, > shouldn't that be a non-problem, as far as compiler reordering goes, > because it's an external function call and only the address of mutex->cs > is passed? > > The only other cause I could think of is if ordering at the CPU was > somehow different (it could be if there're no special provisions for > calling external functions) or if "InterlockedExchange(&mutex->autoinit, > 0)" wasn't atomic in updating autoinit and doing the memory barrier. > > Either way, I couldn't vouch for the safety of the above logic without > a memory barrier so this question is purely of an academical nature. :) > >> > I guess if MSVC assumes that volatile reads imply barriers then it might work... >> >> OK, so I should probably do something like this instead? >> >> while (InterlockedCompareExchange(&mutex->autoinit, 0, 0) != 0) >> ; /* wait for other thread */ > > Technically, assuming only the updating of "mutex->cs" is in question, > the ICE should only be required once after exiting the loop... > > There's a question of the propagation of the value of "mutex->autoinit" > itself, but my take is that the memory barrier on the writing thread > will push out the updated value across all CPUs, thus preventing an > infinite loop. The other factors, value caching and loop optimization > by the compiler, should be prevented by the "volatile" keyword even with > gcc or MSVC 2003. > >> I really appreciate getting some extra eyes on this, thanks. >> Concurrent programming is not my strong-suit (as this exercise has >> shown) ;) > > So would I. :)
Ok, so here's the race condition:
Thread1 Thread2 /* Speculative prefetch */ prefetch(*mutex);
if (mutex->autoinit) { if (ICE(&mutex->autoinit, -1, 1) != -1) { /* Now mutex->autoinit == -1 */ pthread_mutex_init(mutex, NULL); /* This forces writes out to memory */ ICE(&mutex->autoinit, 0, -1);
if (mutex->autoinit) {} /* false */
/* No read barrier here */
EnterCriticalSection(&mutex->cs);
/* Use cached mutex->cs from earlier */Even though you forced the memory write to be ordered in Thread 1 you did not ensure that the read of autoinit occurred before the read of mutex->cs in Thread 2. If the first thing that EnterCriticalSection does is follow a pointer or read a mutex key value in mutex->cs then won't necessarily get the right answer.
The rule of memory barriers is the ALWAYS come in pairs. This simple example guarantees that Thread2 will read "tmp_a" == 1 if it previously read "tmp_b" == 1, although getting "tmp_a" == 1 and "tmp_b" != 1 is still possible.
Thread1: a = 1; write_barrier(); b = 1;
Thread2: tmp_b = b; read_barrier(); tmp_a = a;
I think there's a Documentation/memory-barriers.txt file in the kernel source code with more helpful info.
Cheers, Kyle Moffett
-- Curious about my work on the Debian powerpcspe port? I'm keeping a blog here: http://pureperl.blogspot.com/