From: Will Newton <will.newton@linaro.org>
To: Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org>
Cc: bniebuhr@efjohnson.com, uclibc@uclibc.org,
"libc-ports@sourceware.org" <libc-ports@sourceware.org>,
libc-alpha <libc-alpha@sourceware.org>
Subject: Re: [PATCH] Fix __lll_timedlock_wait busy-wait issue
Date: Thu, 27 Mar 2014 20:54:00 -0000 [thread overview]
Message-ID: <CANu=Dmhn-a-PUNA88OfpoAQyvUZGd3UH+LB+cf=fLWyUNyyU+A@mail.gmail.com> (raw)
In-Reply-To: <09F962CB-595F-4FAB-9435-52C237DB402C@linaro.org>
And CC libc-alpha, as libc-ports has mostly become disused.
On 27 March 2014 20:31, Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org> wrote:
> [CC: libc-ports as glibc's ARM and sparc32 lowlevellock.c need same patch.]
>
> On Mar 22, 2014, at 2:50 AM, bniebuhr@efjohnson.com wrote:
>
>> From: Brian Niebuhr <bniebuhr@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@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@uclibc.org
>> http://lists.busybox.net/mailman/listinfo/uclibc
>
--
Will Newton
Toolchain Working Group, Linaro
next prev parent reply other threads:[~2014-03-27 20:54 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <1395409800-4457-1-git-send-email-bniebuhr@efjohnson.com>
2014-03-27 20:31 ` Maxim Kuvyrkov
2014-03-27 20:54 ` Will Newton [this message]
2014-03-27 22:01 ` Joseph S. Myers
2014-03-27 22:14 ` Maxim Kuvyrkov
2014-03-27 22:19 ` Joseph S. Myers
2014-03-28 18:25 ` Torvald Riegel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CANu=Dmhn-a-PUNA88OfpoAQyvUZGd3UH+LB+cf=fLWyUNyyU+A@mail.gmail.com' \
--to=will.newton@linaro.org \
--cc=bniebuhr@efjohnson.com \
--cc=libc-alpha@sourceware.org \
--cc=libc-ports@sourceware.org \
--cc=maxim.kuvyrkov@linaro.org \
--cc=uclibc@uclibc.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).