From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23080 invoked by alias); 27 Mar 2014 20:31:27 -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 23055 invoked by uid 89); 27 Mar 2014 20:31:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pd0-f177.google.com Received: from mail-pd0-f177.google.com (HELO mail-pd0-f177.google.com) (209.85.192.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Thu, 27 Mar 2014 20:31:23 +0000 Received: by mail-pd0-f177.google.com with SMTP id y10so3847626pdj.22 for ; Thu, 27 Mar 2014 13:31:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=E9GBZuu7ewyySMWFPqW9CDFkQOF20Egi75If3XG3eWo=; b=JsBSaoaZFqcWGFXUXgKUq69D7uTZhHHllbAATDqz4UQ7vUKIculJoLSYZrtlE1D+En FkuMMKq4pVfE0tnt8ScuRmtxb7NjxzErCMSRTrOwMptW3dLmZeZ73MX4706+xJ2mrmRW lr3XMHMnMZ9cCZp0zprS/CLoRzjQgcgXnSbeMagHSWCOrxj/FE4+95DTnj96mvwZ1AzP uf9lA8h29Z5/H/EkBxZZABDO7mWYHJ8E0abMlNSPMjA06KLa5OVAmTTOqG+L74U94w19 LRKGg3YUA7PhlYYBUFnhnErfjhrPeUkSVVBH6ey0/3Ga6fTK9pgoUbeZKbh+Z8sowWw7 kVzg== X-Gm-Message-State: ALoCoQkXLW5sbApoOC/G7mic5xEOowGFPkM8+eRnC/qPr0WWGgDaXpZ0n/P2QflCT8z2pC7XJqZY X-Received: by 10.68.60.225 with SMTP id k1mr4112747pbr.58.1395952281395; Thu, 27 Mar 2014 13:31:21 -0700 (PDT) Received: from [192.168.0.130] (121-99-56-58.bng1.tvc.orcon.net.nz. [121.99.56.58]) by mx.google.com with ESMTPSA id ha2sm13136511pbb.8.2014.03.27.13.31.18 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 27 Mar 2014 13:31:20 -0700 (PDT) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 7.2 \(1874\)) Subject: Re: [PATCH] Fix __lll_timedlock_wait busy-wait issue From: Maxim Kuvyrkov In-Reply-To: <1395409800-4457-1-git-send-email-bniebuhr@efjohnson.com> Date: Thu, 27 Mar 2014 20:31:00 -0000 Cc: uclibc@uclibc.org, libc-ports@sourceware.org Content-Transfer-Encoding: quoted-printable Message-Id: <09F962CB-595F-4FAB-9435-52C237DB402C@linaro.org> References: <1395409800-4457-1-git-send-email-bniebuhr@efjohnson.com> To: bniebuhr@efjohnson.com X-SW-Source: 2014-03/txt/msg00000.txt.bz2 [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 >=20 > __lll_timedlock_wait has a bug that is exposed in these conditions: >=20 > 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 >=20 > 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'. >=20 > 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. >=20 > 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 lo= oking at both glibc and uclibc, I agree that you are correct. Just to reit= erate for others, the problem here is not correctness, but busy-wait instea= d 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/lowlevelloc= k.c, but still present in glibc's ARM and sparc32 lowlevellock.c. Do you p= lan to fix these too? Interestingly, glibc's hppa lowlevellock.c has an alternative solution to t= his problem. I can't quite figure out which solution is faster, so would a= ppreciate a second pair of eyes. My feeling is that the generic (the one i= n your patch) version is faster. Thank you, -- Maxim Kuvyrkov www.linaro.org >=20 > Signed-off-by: Brian Niebuhr > --- > libpthread/nptl/sysdeps/unix/sysv/linux/arm/lowlevellock.c | 6 +----- > 1 file changed, 1 insertion(+), 5 deletions(-) >=20 > 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 timespe= c *abstime, int private) > return EINVAL; >=20 > /* 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; >=20 > @@ -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) !=3D 0); >=20 > return 0; > } > --=20 > 1.8.3.2 >=20 > _______________________________________________ > uClibc mailing list > uClibc@uclibc.org > http://lists.busybox.net/mailman/listinfo/uclibc