Re: [msysGit] Re: [PATCH/RFC] mingw: implement PTHREAD_MUTEX_INITIALIZER

On Thu, Oct 27, 2011 at 19:00, Atsushi Nakagawa [off-list ref] wrote:

Erik Faye-Lund [off-list ref] wrote:

quoted

On Wed, Oct 26, 2011 at 5:44 AM, Kyle Moffett [off-list ref] wrote:

quoted

On Tue, Oct 25, 2011 at 16:51, Erik Faye-Lund [off-list ref] wrote:

quoted

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. :)

quoted

quoted

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.

quoted

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/