[BZ,18743] PowerPC: Fix a race condition when eliding a lock

On 31-07-2015 11:57, Tulio Magno Quites Machado Filho wrote:
> Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
> 
>> On 30-07-2015 23:06, Tulio Magno Quites Machado Filho wrote:
>>> Using pthread_rwlock_rdlock as an example, is_lock_free would be a preprocessor
>>> token with the following contents:
>>>
>>>  128   if (ELIDE_LOCK (rwlock->__data.__rwelision,
>>>  129                   rwlock->__data.__lock == 0
>>>  130                   && rwlock->__data.__writer == 0
>>>  131                   && rwlock->__data.__nr_readers == 0))
>>>
>>> And this is where the important memory access happens.
>>> If one of these fields are changed by another thread after this point, but
>>> before __builtin_tbegin, we're able to reproduce the first problem I mentioned
>>> previously.
>>
>> My understanding is this fields will be changed only in the lock taken path. Let's
>> say a thread t1 grab the lock (either by a transaction or by using a default lock)
>> and modifies any 'rwlock->__data' fields after the ELIDE_LOCK check and before
>> the transaction begin on a second thread t2.  My understanding of the issue you
>> are seeing is the transaction will initiate and since is_lock_free is 1 it won't
>> abort and continue as the a lock taken in both threads.
> 
> I agree with you.  But this won't reproduce the bug.  You have to change the
> order of events.
> 
> Let's say t1 is the first one to read rwlock->__data fields and they're all 0.
> t1 will set is_lock_free to 0.

I believe you mean is_lock_free will be set to '1' if all fields are '0' (since
the lock will not be held).

> Then t2 modifies rwlock->__data before t1 starts the transaction (as in: get a
> lock, instead of a transaction).
> After that, t1 starts the transaction.  Here comes the problem: the memory
> barrier is created with rwlock->__data saying that someone took the lock,
> but is_lock_free is set to 0.  In this scenario, t1 will proceed with the
> transaction.
> 
>> However my understanding is the transaction won't be able to commit since it
>> will have a conflict in the 'rwlock->__data.lock' or in any memory being access
>> in the critical region.
> 
> Yes, but with the order of events I mentioned, when t1 calls
> pthread_rwlock_unlock, it will run the following code:
> 
>   38   if (ELIDE_UNLOCK (rwlock->__data.__writer == 0
>   39                     && rwlock->__data.__nr_readers == 0))
>   40     return 0;
> 
> Where ELIDE_UNLOCK is:
> 
>   89 static inline bool
>   90 __elide_unlock (int is_lock_free)
>   91 {
>   92   if (is_lock_free)
>   93     {
>   94       __builtin_tend (0);
>   95       return true;
>   96     }
>   97   return false;
>   98 }
>   99 
>  100 # define ELIDE_UNLOCK(is_lock_free) \
>  101   __elide_unlock (is_lock_free)
> 
> Remember that t1 started the transaction even if rwlock->__data said someone
> was holding the lock.
> So now, in __elide_unlock, is_lock_free will be 1.  __elide_unlock will
> return false and t1 will unlock a lock acquired by t2.

I see now a window where the pthread_rwlock_t internal structures might have 
concurrent access and the transaction is never finished. However I do not 
think this is a powerpc specific and thus I think it should be fixed in generic
algorithm instead. Something like this:

--

--

I did not fix the x86_64 code, which would require some adjustments.  I checked
on ppc64le and make nptl/tests passes.  It would be good if you could create a
testcase to stress this issue (and I do see this could be quite hard since it is
very timing dependent).

The problem with this approach is it couple the elide macros with rdlock
fields, and I think the idea would make this header more generic for multiple
elide algorithms.  Suggestions?

> 
>> Are you saying that the transaction is not being aborted
>> in the critical region?
> 
> No.  I'm saying the memory access to rwlock->__data is critical and should
> happen inside the transaction.  Without this, we can't say the whole process
> is atomic.
> 
>> If compiler is doing memory reordering around HTM builtin it is *clearly* a bug
>> since transaction begin/end acts a full memory barrier (sync).  You should also
>> add a compiler barrier in pthread elision code as well.
> 
> Agreed.  But I guess that's out of scope for this particular bug.
> I could prepare a separate patch with these changes if you agree with that.
>

On 31-07-2015 18:44, Tulio Magno Quites Machado Filho wrote:
> Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
> 
>> On 31-07-2015 11:57, Tulio Magno Quites Machado Filho wrote:
>>> Let's say t1 is the first one to read rwlock->__data fields and they're all 0.
>>> t1 will set is_lock_free to 0.
>>
>> I believe you mean is_lock_free will be set to '1' if all fields are '0' (since
>> the lock will not be held).
> 
> Yes!  I'm sorry.
> 
>> I see now a window where the pthread_rwlock_t internal structures might have 
>> concurrent access and the transaction is never finished. However I do not 
>> think this is a powerpc specific and thus I think it should be fixed in generic
>> algorithm instead. Something like this:
>>
>> ...
>>
>> I did not fix the x86_64 code, which would require some adjustments.  I checked
>> on ppc64le and make nptl/tests passes.
> 
> I didn't test your patch, but after reading it, I'm sure it does fix the
> problem too.
> 
>> It would be good if you could create a
>> testcase to stress this issue (and I do see this could be quite hard since it is
>> very timing dependent).
> 
> Yes.
> I tried, but I didn't like the idea of creating a testcase that would only
> provide intermittent failures.  Especially because it's very difficult to
> reproduce this failure.
> Any suggestions?
> 
>> The problem with this approach is it couple the elide macros with rdlock
>> fields, and I think the idea would make this header more generic for multiple
>> elide algorithms.  Suggestions?
> 
> And that's why I preferred to modify only the powerpc implementation.
> Both proposals are identical, in the sense that they move the memory access
> to the transaction.
> 
> I'd appreciate if you could explain why you prefer to change the argument list
> of ELIDE_LOCK instead of the powerpc specific code.
> 

Mainly because I see this issue is not powerpc specific and I think we should
also fix for x86 (that currently also uses the same mechanism) and for future
arches that also might potentially implement lock elision using this.

> Em 31/07/2015, às 20:05, Tulio Magno Quites Machado Filho <tuliom@linux.vnet.ibm.com> escreveu:
> 
> Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
> 
>> Mainly because I see this issue is not powerpc specific and I think we should
>> also fix for x86 (that currently also uses the same mechanism) and for future
>> arches that also might potentially implement lock elision using this.
> 
> AFAICS, this is powerpc specific.  x86 ensures the memory access happens
> inside the transaction.
> 
> Here is the x86 implementation:
> 

Right, x86 is evaluated as a macro. Indeed your initial approach seems to be better indeed. Thanks for catching it. I would suggest add a comment similar to x86 as well.

>  50 /* is_lock_free must be executed inside the transaction */
>  51 
>  52 /* Returns true if lock defined by IS_LOCK_FREE was elided.
>  53    ADAPT_COUNT is a pointer to per-lock state variable. */
>  54 
>  55 #define ELIDE_LOCK(adapt_count, is_lock_free)                   \
>  56   ({                                                            \
>  57     int ret = 0;                                                \
>  58                                                                 \
>  59     if ((adapt_count) <= 0)                                     \
>  60       {                                                         \
>  61         for (int i = __elision_aconf.retry_try_xbegin; i > 0; i--) \
>  62           {                                                     \
>  63             unsigned int status;                                \
>  64             if ((status = _xbegin ()) == _XBEGIN_STARTED)       \
>  65               {                                                 \
>  66                 if (is_lock_free)                               \
>  67                   {                                             \
>  68                     ret = 1;                                    \
>  69                     break;                                      \
>  70                   }                                             \
>  71                 _xabort (_ABORT_LOCK_BUSY);                     \
>  72               }                                                 \
>  73             if (!elision_adapt (&(adapt_count), status))        \
>  74               break;                                            \
>  75           }                                                     \
>  76       }                                                         \
>  77     else                                                        \
>  78       (adapt_count)--; /* missing updates ok */                 \
>  79     ret;                                                        \
>  80   })
> 
> -- 
> Tulio Magno
>