[PATCH] Fix __lll_timedlock_wait busy-wait issue

[Maxim Kuvyrkov]

[Re-sending from subscribed address.]

On Mar 22, 2014, at 2:50 AM, bniebuhr at efjohnson.com wrote:

> From: Brian Niebuhr <bniebuhr at efjohnson.com>
> 
> __lll_timedlock_wait has a bug that is exposed in these conditions:
> 
> 1. Thread 1 acquires the lock
> 2. Thread 2 attempts to acquire the lock and waits via futex syscall
> 3. Thread 1 unlocks the lock and wakes the waiting thread
> 4. Thread 1 re-aquires the lock before thread 2 gets the CPU
> 
> What happens in this case is that the futex value is set to '1' since
> Thread 1 reaquired the lock through the fast path (since it had just been
> released).  The problem is that Thread 2 is in the loop in
> __lll_timedlock_wait and it expects the futex value to be '2'.
> atomic_compare_and_exchange_bool_acq only sets the futex value to '2' if
> it is already set to '0', and since Thread 1 reaquired the lock, the
> futex remains set to '1'.
> 
> When Thread 2 attempts to wait on the futex, the operating system returns
> -EWOULDBLOCK since the futex value is not '2'.  This causes a busy wait
> condition where Thread 2 continuously attempts to wait on the futex and
> the kernel immediately returns -EWOULDBLOCK.  This continues until Thread
> 1 releases the lock.
> 
> The fix is to use atomic_exchange_acq instead of
> atomic_compare_and_exchange_bool_acq which will force the futex value to
> '2' on each loop iteration.

You know, I started this reply as a you-are-wrong-here-is-why, but after looking at both glibc and uclibc, I agree that you are correct.  Just to reiterate for others, the problem here is not correctness, but busy-wait instead of sleep under certain conditions.

> This change makes uClibc line up with
> glibc's implementation.

This problem is fixed in glibc's ./nptl/sysdeps/unix/sysv/linux/lowlevellock.c, but still present in glibc's ARM and sparc32 lowlevellock.c.  Do you plan to fix these too?

Interestingly, glibc's hppa lowlevellock.c has an alternative solution to this problem.  I can't quite figure out which solution is faster, so would appreciate a second pair of eyes.  My feeling is that the generic (the one in your patch) version is faster.

Thank you,

--
Maxim Kuvyrkov
www.linaro.org

> 
> Signed-off-by: Brian Niebuhr <bniebuhr at efjohnson.com>
> ---
> libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c | 6 +-----
> 1 file changed, 1 insertion(+), 5 deletions(-)
> 
> diff --git a/libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c b/libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c
> index af864b3..4f7e890 100644
> --- a/libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c
> +++ b/libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c
> @@ -60,10 +60,7 @@ __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private)
>    return EINVAL;
> 
>  /* Upgrade the lock.  */
> -  if (atomic_exchange_acq (futex, 2) == 0)
> -    return 0;
> -
> -  do
> +  while (atomic_exchange_acq (futex, 2) != 0)
>    {
>      struct timeval tv;
> 
> @@ -86,7 +83,6 @@ __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private)
>      // XYZ: Lost the lock to check whether it was private.
>      lll_futex_timed_wait (futex, 2, &rt, private);
>    }
> -  while (atomic_compare_and_exchange_bool_acq (futex, 2, 0) != 0);
> 
>  return 0;
> }
> -- 
> 1.8.3.2
> 
> _______________________________________________
> uClibc mailing list
> uClibc at uclibc.org
> http://lists.busybox.net/mailman/listinfo/uclibc