Re: [boost] [thread] Can Boost.Thread use Boost.Atomic without falling on a compatibility issue?

Subject: Re: [boost] [thread] Can Boost.Thread use Boost.Atomic without falling on a compatibility issue?
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2013-01-14 02:24:50

Le 14/01/13 04:23, Andrey Semashev a écrit :
> On Mon, Jan 14, 2013 at 2:24 AM, Vicente J. Botet Escriba
> <vicente.botet_at_[hidden]> wrote:
>> Le 13/01/13 21:32, Andrey Semashev a écrit :
>>
>>> No, that code is not correct either. The lock in commit and rollback
>>> functions *is* needed and it *must* cover both the store and broadcast
>>> exactly to prevent missed notifications. Otherwise thread A can check
>>> for the flag value but not yet enter pthread_cond_wait and thread B
>>> can store the new flag value and issue pthread_cond_broadcast.
>>>
>>>
>> Wouldn't be useful to use double check here
>>
>>      BOOST_THREAD_DECL bool enter_once_region(once_flag& flag) BOOST_NOEXCEPT
>>
>>      {
>>        atomic_type& f = reinterpret_cast< atomic_type& >(flag.storage);
>>        if (f.load(memory_order_acquire) != initialized)
>>        {
>>          pthread::pthread_mutex_scoped_lock lk(&once_mutex);
>>          if (f.load(memory_order_acquire) != initialized)
>>          {
>>            while (true)
>>            {
>>              atomic_int_type expected = uninitialized;
>>              if (f.compare_exchange_strong(expected, in_progress,
>> memory_order_acq_rel, memory_order_acquire))
>>              {
>>                // We have set the flag to in_progress
>>                return true;
>>              }
>>              else if (expected == initialized)
>>              {
>>                // Another thread managed to complete the initialization
>>                return false;
>>              }
>>              else
>>              {
>                 // ****
>>                // Wait until the initialization is complete
>>                BOOST_VERIFY(!pthread_cond_wait(&once_cv, &once_mutex));
>>              }
>>            }
>>          }
>>        }
>>        return false;
>>
>>      }
>>
>>      BOOST_THREAD_DECL void commit_once_region(once_flag& flag)
>> BOOST_NOEXCEPT
>>      {
>>        atomic_type& f = reinterpret_cast< atomic_type& >(flag.storage);
>>        {
>>          pthread::pthread_mutex_scoped_lock lk(&once_mutex);
>>          f.store(initialized, memory_order_release);
>>        }
                 // C***
>>        BOOST_VERIFY(!pthread_cond_broadcast(&once_cv));
>>      }
>>
>>      BOOST_THREAD_DECL void rollback_once_region(once_flag& flag)
>> BOOST_NOEXCEPT
>>
>>      {
>>        atomic_type& f = reinterpret_cast< atomic_type& >(flag.storage);
>>        {
>>          pthread::pthread_mutex_scoped_lock lk(&once_mutex);
>>          f.store(uninitialized, memory_order_release);
>>        }
                // R***
>>        BOOST_VERIFY(!pthread_cond_broadcast(&once_cv));
>>
>>      }
> 1. You have the race condition I described in my previous post. The
> broadcast is missed if it happens when the other thread is executing
> at **** position.
I don't think so. The thread B has notified a commit in C*** or rollback 
in R***, the thread A could not be in //**** as the access to the flag 
is protected with the lock.

Here follows the algorithm in libc++. You could see that the lock is 
released before notifying.

void
__call_once(volatile unsigned long& flag, void* arg, void(*func)(void*))
{
     pthread_mutex_lock(&mut);
     while (flag == 1)
         pthread_cond_wait(&cv, &mut);
     if (flag == 0)
     {
#ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
#endif  // _LIBCPP_NO_EXCEPTIONS
             flag = 1;
             pthread_mutex_unlock(&mut);
             func(arg);
             pthread_mutex_lock(&mut);
             flag = ~0ul;
             pthread_mutex_unlock(&mut);
             pthread_cond_broadcast(&cv);
#ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             pthread_mutex_lock(&mut);
             flag = 0ul;
             pthread_mutex_unlock(&mut);
             pthread_cond_broadcast(&cv);
             throw;
         }
#endif  // _LIBCPP_NO_EXCEPTIONS
     }
     else
         pthread_mutex_unlock(&mut);
}

> 2. If you use the double-check pattern with the lock, you don't need
> to CAS the flag.
Well this was the issue with the Trac ticket. The first check works only 
if T is such that the load/save is atomic. Maybe the access to the 
atomic flag inside the lock protected part could be relaxed I don't know 
all the possibilities of Boost.Atomic.
> 3. I think your code will have worse performance because you lock the
> mutex whenever you are about to enter the execution block while mine
> code will only lock in case of contention. This difference is not in
> the most performance critical path but it still exists. However, I
> didn't perform any tests to confirm that.
>
I agree. But the condition variable needs that the code changing/getting 
the protect data needs to be protected with the same mutex that is used 
on the wait.
IMHO, your previous implementation failed to do that as every access to 
the once flag in enter_once_region was not protected.
Maybe Howard or Anthony (or someone else of course) could help us to 
determine the correctness of both implementations.

Best,
Vicente