From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1926 invoked by alias); 27 Mar 2014 20:54:12 -0000 Mailing-List: contact libc-ports-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: libc-ports-owner@sourceware.org Received: (qmail 1912 invoked by uid 89); 27 Mar 2014 20:54:12 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-ie0-f181.google.com Received: from mail-ie0-f181.google.com (HELO mail-ie0-f181.google.com) (209.85.223.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 27 Mar 2014 20:54:10 +0000 Received: by mail-ie0-f181.google.com with SMTP id tp5so3823561ieb.26 for ; Thu, 27 Mar 2014 13:54:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=x/LhoH1ohc0D3zJDD3aRnU5vvs5SyJhmP/0Ye8vpqMk=; b=AylNGo5RAZV6Lrxx23asRbmVnPugx/j5fw5pfVJQwxca0oDsMxKgLMVy4akjyx3IG7 6GN2ZVfiySNXPtOKKUvk6PlZQq2FMCFHGfqOsM1cGa977GsuHqZvyjCnpqaEKt5QbxO7 +TaPf1If0WhFUTKOjdg9tfxS1qMjI5a8xruKwAOnzamAilFMUhqLOhZrAaldwDenoLpC nTHZ2+JK8DnPtQwNFOH4gPgxIrgaTB6fIdlWx3KbxNYlTaWrsmJVBhMdl8UhEd3Cg9TJ o6uo8xm3b2yx2jyjPg/FyTt5+eaN4l3i1Iuwzz7gEJjHpt6p7wJwSAqP/HQX6+TWKnGq yx2g== X-Gm-Message-State: ALoCoQlsuLzKnLORqwvgQXm7ZBDmcrDYmpS83aZCYQIyPkIICfda+f4hhhYVirNMU9xatEV1SjYB MIME-Version: 1.0 X-Received: by 10.50.137.71 with SMTP id qg7mr33945178igb.30.1395953649040; Thu, 27 Mar 2014 13:54:09 -0700 (PDT) Received: by 10.64.7.228 with HTTP; Thu, 27 Mar 2014 13:54:08 -0700 (PDT) In-Reply-To: <09F962CB-595F-4FAB-9435-52C237DB402C@linaro.org> References: <1395409800-4457-1-git-send-email-bniebuhr@efjohnson.com> <09F962CB-595F-4FAB-9435-52C237DB402C@linaro.org> Date: Thu, 27 Mar 2014 20:54:00 -0000 Message-ID: Subject: Re: [PATCH] Fix __lll_timedlock_wait busy-wait issue From: Will Newton To: Maxim Kuvyrkov Cc: bniebuhr@efjohnson.com, uclibc@uclibc.org, "libc-ports@sourceware.org" , libc-alpha Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2014-03/txt/msg00001.txt.bz2 And CC libc-alpha, as libc-ports has mostly become disused. On 27 March 2014 20:31, Maxim Kuvyrkov 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 >> >> __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 re= iterate for others, the problem here is not correctness, but busy-wait inst= ead 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/lowlevell= ock.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 >> --- >> 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 timesp= ec *abstime, int private) >> return EINVAL; >> >> /* Upgrade the lock. */ >> - if (atomic_exchange_acq (futex, 2) =3D=3D 0) >> - return 0; >> - >> - do >> + while (atomic_exchange_acq (futex, 2) !=3D 0) >> { >> struct timeval tv; >> >> @@ -86,7 +83,6 @@ __lll_timedlock_wait (int *futex, const struct timespe= c *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) !=3D 0); >> >> return 0; >> } >> -- >> 1.8.3.2 >> >> _______________________________________________ >> uClibc mailing list >> uClibc@uclibc.org >> http://lists.busybox.net/mailman/listinfo/uclibc > --=20 Will Newton Toolchain Working Group, Linaro