From patchwork Thu Oct 23 12:12:51 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernard Ogden X-Patchwork-Id: 402461 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3B56314009A for ; Thu, 23 Oct 2014 23:13:36 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=xlIV80JHxUth0z2yPB7jnUyvVmverVQ fgEiLdLV5bHBeYv2J3niZCaZFrCBbUVh5bFhwT9ooOfgKGdsyknnZW9yLWi7EKmb Opowjkm8eVpBkOQkwLCNdK4EraPEkLKszJ2GEypvhx4g+YB37ddpGQN9nMixEV/N 6NRJ3JwKDfiQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id:in-reply-to :references; s=default; bh=WKbOpDASOma6dNELGrNqK3b0jrQ=; b=d4r9V bldtRMGap2MZv+E0y/jlKR2TbnoZ7rlEiBmOKjz9i+GU1KHS+MGo1uhrKc5Yokuh SBrkbwq6U8iEsv4Pe1rc1Iz+DQWDkgW8PYzNTr2pdPruEsK1lgdNrfu1R6VmVqB7 YJYodJ09bH2+qlQf41NOz37Lc4IPlFIRtHtXwU= Received: (qmail 13659 invoked by alias); 23 Oct 2014 12:13:30 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 13649 invoked by uid 89); 23 Oct 2014 12:13:29 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-wg0-f44.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=pHzQOt7opZFKd8mXHwg+kMyTXwA1qM0tSoy6cwtN1rA=; b=XolEukApFg3fv9Dfl9ZVtnSx4jEZYnWP5R5WHXXPVjIpFvS29oX7hh1qsPQuzjv5PL y1zX6nrbQAjtv1nuIX2o3zThEFgwQDGBNse1QpwW5n0AikYgx2HrdH9Nym7VSBeZLu+6 FXDDiErPk+ARuoWKUc/fLAwYEDtBqfgAbVNjWt+MkrmZfUqSunAMda/0ZBtuBAQTs+yu vBvRlZbpulgVNwvzIMV0+Bq+A9MFDtcRH9VlbBf4HtpBrjplrye+cyHM5Gq6AXUYIosn XEwhBYCc7CJY24IAZEPK+cUQkVtI5AmLvwJBVx/8ykEMGU3O8QEUWdvDxSHmHF3ScwF8 qFdQ== X-Gm-Message-State: ALoCoQnrScbbnbyhbD75EHPDxmBKt0WakKAFYDR5mAZV1R46Xm9wWuTgR5dGc/C3aKVBP7B0tAdA X-Received: by 10.180.212.78 with SMTP id ni14mr12451453wic.2.1414066402981; Thu, 23 Oct 2014 05:13:22 -0700 (PDT) From: Bernard Ogden To: libc-alpha@sourceware.org Cc: triegel@redhat.com, carlos@redhat.com, Bernard Ogden Subject: [PATCH v3] lowlevellock comments Date: Thu, 23 Oct 2014 13:12:51 +0100 Message-Id: <1414066371-394-1-git-send-email-bernie.ogden@linaro.org> In-Reply-To: References: Here's a v3. All comments addressed - replies to comments I have something to say about inline below. On 6 October 2014 13:26, Torvald Riegel wrote: >> To make the >1 state easier to refer to in comments I've gone for: >> >1 - locked-with-waiters, there _may_ be waiters >> >> If I'm right then strictly >1 means locked-possibly-with-waiters, but that's >> really getting too much of a mouthful (as 'potentially contended' would have >> been in the earlier terminology). > > But "locked possibly with waiters" is the right description, so I'd > rather use this. OK, changed throughout to 'acquired, possibly with waiters' (based on the suggested text below). >> > Please use locked, or unlocked terms everywhere. >> >> I've gone for unlocked, locked and locked with waiters. > > My vote would be for "acquired" / "not acquired", as in "the lock has > been acquired". Switched to acquired/not acquired, as no-one defended locked/unlocked. >> + thread ID while the clone is running and is reset to zero >> + afterwards. */ > > Could you add who resets it? Done (it's the kernel). >> >> +/* Uses futexes to avoid unnecessary calls into the kernel. Likely paths are > > I'd say it uses futexes to block using the kernel. That's the purpose > of the futex call, so that we don't need to just spin-wait. >> + the cases with no waiters and hence do not involve syscalls. Unlikely paths >> + usually will involve syscalls to wait or to wake. > > The "likely" path is not necessarily likely, but we try to make > uncontended mutexes fast, so that's why we avoid the syscalls in these > cases. I would suggest: > > Low-level locks use a combination of atomic operations (to acquire and > release lock ownership) and futex operations (to block until the state > of a lock changes). A lock can be in one of three states: > 0: not acquired, > 1: acquired; no other threads are blocked or about to block for changes > to the lock state, >>1: acquired, other threads are potentially blocked or about to block > for changes to the lock state. > > We expect that the common case is an uncontended lock, so we just need > to transition the lock between states 0 and 1; releasing the lock does > not need to wake any other blocked threads. If the lock is contended > and a thread decides to block using a futex operation, then this thread > needs to first change the state to >1; if this state is observed during > lock release, the releasing thread will wake one of the potentially > blocked threads. Used your text, tweaked slightly to make the difference between 1 and >1 even more explicit. Also reworded the >1 description to a form that makes a bit more sense to the pedant in me. >> + cond_locks are never in the locked state, they are either unlocked or >> + locked with waiters. > > Change that to the following?: > > Condition variables contain an optimization for broadcasts that requeues > waiting threads on a lock's futex. Therefore, there is a special > variant of the locks (whose name contains "cond") that makes sure to > always set the lock state to >1 and not just 1. And just used this as is. >> +/* If LOCK is 0 (unlocked), set to 1 (locked) and return 0 to indicate the >> + lock was acquired. Otherwise leave the lock unchanged and return non-zero >> + to indicate the lock was not acquired. */ > > If you use acquired / not acquired instead of locked / unlocked, this > gets simpler. In that I can be a bit less verbose about the meaning of returns? Done. >> + 2) The previous owner of the lock dies. FUTEX will be >> + ID | FUTEX_OWNER_DIED. FUTEX_WAITERS may also be set. Return FUTEX to >> + indicate that the lock is not acquired. */ > > I'd say "this value" instead of the second occurence of "FUTEX" to > highlight that we do NOT read FUTEX twice. Fixed - also put the FUTEX_WAITERS part in brackets and cleared up some ambiguity. 2014-10-23 Bernard Ogden * nptl/lowlevellock.c: Add comments. * nptl/lowlevelrobustlock.c: Likewise. * sysdeps/nptl/lowlevellock.h: Likewise. diff --git a/nptl/lowlevellock.c b/nptl/lowlevellock.c index e198af7..99cca8e 100644 --- a/nptl/lowlevellock.c +++ b/nptl/lowlevellock.c @@ -27,10 +27,10 @@ void __lll_lock_wait_private (int *futex) { if (*futex == 2) - lll_futex_wait (futex, 2, LLL_PRIVATE); + lll_futex_wait (futex, 2, LLL_PRIVATE); /* Wait if *futex == 2. */ while (atomic_exchange_acq (futex, 2) != 0) - lll_futex_wait (futex, 2, LLL_PRIVATE); + lll_futex_wait (futex, 2, LLL_PRIVATE); /* Wait if *futex == 2. */ } @@ -40,10 +40,10 @@ void __lll_lock_wait (int *futex, int private) { if (*futex == 2) - lll_futex_wait (futex, 2, private); + lll_futex_wait (futex, 2, private); /* Wait if *futex == 2. */ while (atomic_exchange_acq (futex, 2) != 0) - lll_futex_wait (futex, 2, private); + lll_futex_wait (futex, 2, private); /* Wait if *futex == 2. */ } @@ -75,7 +75,7 @@ __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private) if (rt.tv_sec < 0) return ETIMEDOUT; - /* Wait. */ + /* If *futex == 2, wait until woken or timeout. */ lll_futex_timed_wait (futex, 2, &rt, private); } @@ -83,6 +83,11 @@ __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private) } +/* The kernel notifies a process which uses CLONE_CHILD_CLEARTID via futex + wake-up when the clone terminates. The memory location contains the + thread ID while the clone is running and is reset to zero by the kernel + afterwards. The kernel up to version 3.16.3 does not use the private futex + operations for futex wake-up when the clone terminates. */ int __lll_timedwait_tid (int *tidp, const struct timespec *abstime) { @@ -113,8 +118,10 @@ __lll_timedwait_tid (int *tidp, const struct timespec *abstime) if (rt.tv_sec < 0) return ETIMEDOUT; - /* Wait until thread terminates. The kernel so far does not use - the private futex operations for this. */ + /* If *tidp == tid, wait until thread terminates or the wait times out. + The kernel to version 3.16.3 does not use the private futex + operations for futex wake-up when the clone terminates. + */ if (lll_futex_timed_wait (tidp, tid, &rt, LLL_SHARED) == -ETIMEDOUT) return ETIMEDOUT; } diff --git a/nptl/lowlevelrobustlock.c b/nptl/lowlevelrobustlock.c index 3525807..2f4f314 100644 --- a/nptl/lowlevelrobustlock.c +++ b/nptl/lowlevelrobustlock.c @@ -36,14 +36,17 @@ __lll_robust_lock_wait (int *futex, int private) do { + /* If the owner died, return the present value of the futex. */ if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED)) return oldval; + /* Attempt to put lock into state 'acquired, possibly with waiters'. */ int newval = oldval | FUTEX_WAITERS; if (oldval != newval && atomic_compare_and_exchange_bool_acq (futex, newval, oldval)) continue; + /* If *futex == 2, wait until woken. */ lll_futex_wait (futex, newval, private); try: @@ -100,15 +103,17 @@ __lll_robust_timedlock_wait (int *futex, const struct timespec *abstime, return ETIMEDOUT; #endif - /* Wait. */ + /* If the owner died, return the present value of the futex. */ if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED)) return oldval; + /* Attempt to put lock into state 'acquired, possibly with waiters'. */ int newval = oldval | FUTEX_WAITERS; if (oldval != newval && atomic_compare_and_exchange_bool_acq (futex, newval, oldval)) continue; + /* If *futex == 2, wait until woken or timeout. */ #if (!defined __ASSUME_FUTEX_CLOCK_REALTIME \ || !defined lll_futex_timed_wait_bitset) lll_futex_timed_wait (futex, newval, &rt, private); diff --git a/sysdeps/nptl/lowlevellock.h b/sysdeps/nptl/lowlevellock.h index 28f4ba3..8f6e270 100644 --- a/sysdeps/nptl/lowlevellock.h +++ b/sysdeps/nptl/lowlevellock.h @@ -22,9 +22,53 @@ #include #include +/* Low-level locks use a combination of atomic operations (to acquire and + release lock ownership) and futex operations (to block until the state + of a lock changes). A lock can be in one of three states: + 0: not acquired, + 1: acquired with no waiters; no other threads are blocked or about to block + for changes to the lock state, + >1: acquired, possibly with waiters; there may be other threads blocked or + about to block for changes to the lock state. + + We expect that the common case is an uncontended lock, so we just need + to transition the lock between states 0 and 1; releasing the lock does + not need to wake any other blocked threads. If the lock is contended + and a thread decides to block using a futex operation, then this thread + needs to first change the state to >1; if this state is observed during + lock release, the releasing thread will wake one of the potentially + blocked threads. + + Much of this code takes a 'private' parameter. This may be: + LLL_PRIVATE: lock only shared within a process + LLL_SHARED: lock may be shared across processes. + + Condition variables contain an optimization for broadcasts that requeues + waiting threads on a lock's futex. Therefore, there is a special + variant of the locks (whose name contains "cond") that makes sure to + always set the lock state to >1 and not just 1. + + Robust locks set the lock to the id of the owner. This allows detection + of the case where the owner exits without releasing the lock. Flags are + OR'd with the owner id to record additional information about lock state. + Therefore the states of robust locks are: + 0: not acquired + id: acquired (by user identified by id & FUTEX_TID_MASK) + + The following flags may be set in the robust lock value: + FUTEX_WAITERS - possibly has waiters + FUTEX_OWNER_DIED - owning user has exited without releasing the futex. */ + + +/* If LOCK is 0 (not acquired), set to 1 (acquired) and return 0. Otherwise + leave lock unchanged and return non-zero to indicate that the lock was not + acquired. */ #define lll_trylock(lock) \ atomic_compare_and_exchange_bool_acq (&(lock), 1, 0) +/* If LOCK is 0 (not acquired), set to 2 (acquired, possibly with waiters) and + return 0. Otherwise leave lock unchanged and return non-zero to indicate + that the lock was not acquired. */ #define lll_cond_trylock(lock) \ atomic_compare_and_exchange_bool_acq (&(lock), 2, 0) @@ -35,6 +79,13 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden; /* This is an expression rather than a statement even though its value is void, so that it can be used in a comma expression or as an expression that's cast to void. */ +/* The inner conditional compiles to a call to __lll_lock_wait_private if + private is known at compile time to be LLL_PRIVATE, and to a call to + __lll_lock_wait otherwise. */ +/* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and + return. Otherwise block until we acquire the lock, at which point FUTEX is + 2 (acquired, possibly with waiters), then return. The lock is aways + acquired on return. */ #define __lll_lock(futex, private) \ ((void) \ ({ \ @@ -52,6 +103,14 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden; __lll_lock (&(futex), private) +/* If FUTEX is 0 (not acquired), set to ID (acquired with no waiters) and + return 0. Otherwise, block until either: + 1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS + (acquired, possibly with waiters), then return 0. + 2) The previous owner of the lock dies. FUTEX will be the value of id as + set by the previous owner, with FUTEX_OWNER_DIED set (FUTEX_WAITERS may + also be set). Return this value to indicate that the lock is not + acquired. */ #define __lll_robust_lock(futex, id, private) \ ({ \ int *__futex = (futex); \ @@ -69,6 +128,12 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden; /* This is an expression rather than a statement even though its value is void, so that it can be used in a comma expression or as an expression that's cast to void. */ +/* Unconditionally set FUTEX to 2 (acquired, possibly with waiters). condvar + locks only have 'not acquired' and 'acquired, possibly with waiters' states, + so there is no need to check FUTEX before setting. + If FUTEX was 0 (not acquired) then return. Otherwise, block until the lock + is acquired, at which point FUTEX is 2 (acquired, possibly with waiters). + The lock is always acquired on return. */ #define __lll_cond_lock(futex, private) \ ((void) \ ({ \ @@ -79,6 +144,14 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden; #define lll_cond_lock(futex, private) __lll_cond_lock (&(futex), private) +/* If FUTEX is 0 (not acquired), set to ID | FUTEX_WAITERS (acquired, possibly + with waiters) and return 0. Otherwise, block until either: + 1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS + (acquired, possibly with waiters), then return 0. + 2) The previous owner of the lock dies. FUTEX will be the value of id as + set by the previous owner, with FUTEX_OWNER_DIED set (FUTEX_WAITERS may + also be set). Return this value to indicate that the lock is not + acquired. */ #define lll_robust_cond_lock(futex, id, private) \ __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private) @@ -88,8 +161,9 @@ extern int __lll_timedlock_wait (int *futex, const struct timespec *, extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, int private) attribute_hidden; -/* Take futex if it is untaken. - Otherwise block until either we get the futex or abstime runs out. */ + +/* As __lll_lock, but with a timeout. If the timeout occurs then return + ETIMEDOUT. If ABSTIME is invalid, return EINVAL. */ #define __lll_timedlock(futex, abstime, private) \ ({ \ int *__futex = (futex); \ @@ -104,6 +178,8 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, __lll_timedlock (&(futex), abstime, private) +/* As __lll_robust_lock, but with a timeout. If the timeout occurs then return + ETIMEDOUT. If ABSTIME is invalid, return EINVAL. */ #define __lll_robust_timedlock(futex, abstime, id, private) \ ({ \ int *__futex = (futex); \ @@ -121,6 +197,9 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, /* This is an expression rather than a statement even though its value is void, so that it can be used in a comma expression or as an expression that's cast to void. */ +/* Unconditionally set FUTEX to 0 (not acquired), releasing the lock. If FUTEX + was >1 (acquired, possibly with waiters), then wake any waiters. The waiter + who acquires the lock will set FUTEX to >1. */ #define __lll_unlock(futex, private) \ ((void) \ ({ \ @@ -136,6 +215,9 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, /* This is an expression rather than a statement even though its value is void, so that it can be used in a comma expression or as an expression that's cast to void. */ +/* Unconditionally set FUTEX to 0 (not acquired), releasing the lock. If FUTEX + had FUTEX_WAITERS set then wake any waiters. The waiter who acquires the + lock will set FUTEX_WAITERS. */ #define __lll_robust_unlock(futex, private) \ ((void) \ ({ \ @@ -159,15 +241,12 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, #define LLL_LOCK_INITIALIZER (0) #define LLL_LOCK_INITIALIZER_LOCKED (1) -/* The states of a lock are: - 0 - untaken - 1 - taken by one user - >1 - taken by more users */ /* The kernel notifies a process which uses CLONE_CHILD_CLEARTID via futex - wakeup when the clone terminates. The memory location contains the - thread ID while the clone is running and is reset to zero - afterwards. */ + wake-up when the clone terminates. The memory location contains the + thread ID while the clone is running and is reset to zero by the kernel + afterwards. The kernel up to version 3.16.3 does not use the private futex + operations for futex wake-up when the clone terminates. */ #define lll_wait_tid(tid) \ do { \ __typeof (tid) __tid; \ @@ -178,6 +257,8 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *, extern int __lll_timedwait_tid (int *, const struct timespec *) attribute_hidden; +/* As lll_wait_tid, but with a timeout. If the timeout occurs then return + ETIMEDOUT. If ABSTIME is invalid, return EINVAL. */ #define lll_timedwait_tid(tid, abstime) \ ({ \ int __res = 0; \