Re: [PATCH roland/lll-futex] Separate Linuxisms from lowlevellock.h, make a generic one

[Bernard Ogden <bernie dot ogden at linaro dot org>]

On 9 Jul 2014, at 22:54, Roland McGrath <roland@hack.frob.com> wrote:

>> On 3 Jul 2014, at 00:14, Roland McGrath <roland@hack.frob.com> wrote:
>> 
>>> +#define __lll_robust_trylock(futex, id) \
>>> +  (atomic_compare_and_exchange_val_acq (futex, id, 0) != 0)
>> 
>> My first thought was that the != 0 is superfluous. Either way you return
>> 0 if you changed the memory, and non-zero if you didn't.
>> 
>> But looking at the call in pthread_mutex_trylock.c, I wonder if both
>> patches have this wrong. Should we be returning the old value here?
>> That's what (at least) m68k does, so there's a difference that'll need
>> resolving.
> 
> Indeed this seems clearly wrong.  Unfortunately it looks to me like the
> scenario where it makes a difference can only come up in a race.  The logic
> in pthread_mutex_trylock is somewhat intricate, so I'm not completely sure.
> Can you see a way to come up with a (non-racy) regression test for this?

To test that particular case, it looks like we'd have to force a thread to die in an unclean way in the middle of the function. I don't think we can do that.

Perhaps there should be a test that we get EOWNERDEAD if a lock holder dies in an unclean way before the call to __pthread_mutex_trylock - I didn't see one and I guess that would be doable with a pair of threads. But that's getting further away from issues relating to this patch.

> 
>>> +#define __lll_cond_lock(futex, private)                         \
>>> +  ((void)                                                       \
>>> +   ({                                                           \
>>> +     int *__futex = (futex);                                    \
>>> +     if (__glibc_unlikely (atomic_exchange_acq (__futex, 2)))   \
>>> +       __lll_lock_wait (__futex, private);                      \
>>> +   }))
>> 
>> This is unconditionally setting the futex to 2, where my patch (based
>> on Tile) sets it to 2 only if it was previously 0. Again, the
>> platforms are inconsistent so it'll need resolving.
> 
> The lay of the land is pretty similar for this case.  Many have exactly
> equivalent code.  Many others have code that uses one of
> atomic_compare_and_exchange_{bool,val}_acq and so match the behavior of
> yours rather than mine.  A few others open-code assembly that is
> equivalent to one or the other.
> 
> Unlike lll_robust_trylock, there is one outlier: sparc is almost the
> same (as yours), but uses atomic_compare_and_exchange_val_24_acq (a
> special sparcism).  So it's not a candidate for removing entirely even
> though it too has only one user (pthread_mutex_cond_lock.c).
> 
> Off hand I don't understand the use here well enough to be completely
> sure which is correct.  In the contended case, they all get to
> __lll_lock_wait.  The generic C and the x86 assembly versions of that do
> the equivalent of the unconditional atomic_exchange_acq.  I suspect that
> is actually what's correct: if it was 0 before that's the
> unlocked/uncontended case; if it was 1 before, your code leaves it 1
> (until it gets into __lll_lock_wait, anyway) but there is now
> contention, so it should be 2; when it gets into __lll_lock_wait, that
> will do an unconditional atomic_exchange_acq anyway.
> 
> Given this control flow, I think it's impossible to write any test that
> can tell the difference.  Your version is just going to be slightly
> suboptimal in the contended case, because it will skip installing 2 and
> then do an additional atomic operation in __lll_lock_wait to install it
> before going into the kernel.
> 
> So we just have to reason it out.  Do you agree with my reasoning above?

I only learned about condition variables at all through looking at this patch, but I think your reasoning is correct.

> 
>>> +#define __lll_timedlock(futex, abstime, private)                \
>>> +  ({                                                            \
>>> +    int *__futex = (futex);                                     \
>>> +    int __val = 0;                                              \
>>> +                                                                \
>>> +    if (__glibc_unlikely (atomic_exchange_acq (__futex, 1)))    \
>>> +      __val = __lll_timedlock_wait (__futex, abstime, private); \
>>> +    __val;                                                      \
>>> +  })
>> 
>> This'll spread BZ 16892 (and be a binary difference on the currently
>> unaffected platforms).
>> 
>> Should be something like:
>> 
>> if (__glibc_unlikely (atomic_compare_and_exchange_bool_acq (__futex, 1, 0)))
> 
> OK.  I concur with the rationale described in the bug.  But as I said
> above, I'm inclined to separate that fix to be done after the pure
> refactoring has gone in.

That makes sense.

So in summary:
__lll_robust_trylock: Has already been removed, we can't test.
__lll_cond_lock: Your patch looks fine.
__lll_timedlock: To be fixed once the refactoring has gone in.