On Thu, Oct 27, 2011 at 19:00, Atsushi Nakagawa <atnak@xxxxxxxxx> wrote: > Erik Faye-Lund <kusmabite@xxxxxxxxx> wrote: >> On Wed, Oct 26, 2011 at 5:44 AM, Kyle Moffett <kyle@xxxxxxxxxxxxxxx> wrote: >> > On Tue, Oct 25, 2011 at 16:51, Erik Faye-Lund <kusmabite@xxxxxxxxx> 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/ -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html