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:
>> On Tue, Oct 25, 2011 at 10:07 PM, Johannes Sixt <j6t@xxxxxxxx> wrote:
>>> Am 25.10.2011 17:42, schrieb Erik Faye-Lund:
>>>> On Tue, Oct 25, 2011 at 5:28 PM, Johannes Sixt <j.sixt@xxxxxxxxxxxxx> wrote:
>>>>> Am 10/25/2011 16:55, schrieb Erik Faye-Lund:
>>>>>> +int pthread_mutex_lock(pthread_mutex_t *mutex)
>>>>>> +{
>>>>>> + if (mutex->autoinit) {
>>>>>> + if (InterlockedCompareExchange(&mutex->autoinit, -1, 1) != -1) {
>>>>>> + pthread_mutex_init(mutex, NULL);
>>>>>> + mutex->autoinit = 0;
>>>>>> + } else
>>>>>> + while (mutex->autoinit != 0)
>>>>>> + ; /* wait for other thread */
>>>>>> + }
>>>>>
>>>>> The double-checked locking idiom. Very suspicious. Can you explain why it
>>>>> works in this case? Why are no Interlocked functions needed for the other
>>>>> accesses of autoinit? ("It is volatile" is the wrong answer to this last
>>>>> question, BTW.)
>>>>
>>>> I agree that it should look a bit suspicious; I'm generally skeptical
>>>> whenever I see 'volatile' in threading-code myself. But I think it's
>>>> the right answer in this case. "volatile" means that the compiler
>>>> cannot optimize away accesses, which is sufficient in this case.
>>>
>>> No, it is not, and it took me a train ride to see what's wrong. It has
>>> nothing to do with autoinit, but with all the other memory locations
>>> that are written. See here, with pthread_mutex_init() inlined:
>>>
>>> if (mutex->autoinit) {
>>>
>>> Assume two threads enter this block.
>>>
>>> if (InterlockedCompareExchange(&mutex->autoinit, -1, 1) != -1) {
>>>
>>> Only one thread, A, say on CPU A, will enter this block.
>>>
>>> InitializeCriticalSection(&mutex->cs);
>>>
>>> Thread A writes some values. Note that there are no memory barriers
>>> involved here. Not that I know of or that they would be documented.
>>>
>>> mutex->autoinit = 0;
>>>
>>> And it writes another one. Thread A continues below to contend for the
>>> mutex it just initialized.
>>>
>>> } else
>>>
>>> Meanwhile, thread B, say on CPU B, spins in this loop:
>>>
>>> while (mutex->autoinit != 0)
>>> ; /* wait for other thread */
>>>
>>> When thread B arrives here, it sees the value of autoinit that thread A
>>> has written above.
>>>
>>> HOWEVER, when it continues, there is NO [*] guarantee that it will also
>>> see the values that InitializeCriticalSection() has written, because
>>> there were no memory barriers involved. When it continues, there is a
>>> chance that it calls EnterCriticalSection() with uninitialized values!
>>>
>>
>> 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.
>
> 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 */
I really appreciate getting some extra eyes on this, thanks.
Concurrent programming is not my strong-suit (as this exercise has
shown) ;)
--
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