[v2] lowlevellock comments

Message ID 1412005158-24337-1-git-send-email-bernie.ogden@linaro.org
State New
Headers show

Commit Message

Bernie Ogden Sept. 29, 2014, 3:39 p.m.
Hi Carlos,

Thanks for the review. I think I've addressed all the comments - more specific
responses inline below, v2 of patch even further below.

Regards,

Bernie

On 26 September 2014 15:55, Carlos O'Donell <carlos@redhat.com> wrote:
> On 09/26/2014 07:55 AM, Bernard Ogden wrote:
> Shouldn't this be "until thread terminates or the wait times out."?

Yep, fixed.

> Please verify the kernel does not use the private futex operations for this,
> and when complete come back and update the comment to say:
>
> "As of kernel X.Y.Z, the private futex operation is not used."

IIUC, the comment is still correct - the relevant code being this snippet
(kernel/fork.c:817 in linux-stable):

if (tsk->clear_child_tid) {
         if (!(tsk->flags & PF_SIGNALED) &&
             atomic_read(&mm->mm_users) > 1) {
                 /*
                  * We don't check the error code - if userspace has
                  * not set up a proper pointer then tough luck.
                  */
                  put_user(0, tsk->clear_child_tid);
                  sys_futex(tsk->clear_child_tid, FUTEX_WAKE,
                                 1, NULL, NULL, 0);
         }
         tsk->clear_child_tid = NULL;
}

(FUTEX_WAKE without an explicit private flag meaning shared.)

I've made the comments for lll_timedwait_tid (lowlevellock.c) and lll_wait_tid
(lowlevellock.h) more consistent and hopefully therefore clearer.

Is your form of words the idiom for this? - to me it suggests that the private
futex operation went out of use in that kernel version, so I changed it a
little.

>>       return oldval;
>>
>> +      /* Put lock into contended state.  */
>
> Suggest: "Attempt to put lock into contended state."

Changed to "Attempt to put lock into state locked with waiters" - on the
principle of using consistent terminology everywhere.

>> +      /* Put lock into contended state.  */
>
> Suggest: "Attempt to put lock into contended state."

Changed to "Attempt to put lock into state locked with waiters" - on the
principle of using consistent terminology everywhere.

> unneccessary => unnecessary, spell check please.

>> +   the uncontended cases and hence do not involve syscalls. Unlikely
>> +   (contended case) paths usually will involve syscalls to wait or to wake.
>> +
>> +   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.  */
>> +
>> +/* The states of locks are:
>> +    0  -  untaken
>> +    1  -  taken (by one user)
>> +   >1  -  contended (taken by 1 user, there may be other users waiting)
>
> I don't think this is true, I think 2 is explicitly "locked, one or more waiters"
>
> Suggest:
>
> 0 - unlocked.
> 1 - locked, no waiters.
> 2 - locked, one or more waiters.

I did consider putting '2', but abandoned it because the checks are all for
>1 and I haven't proved that nothing in glibc is fiddling the values of
futexes to >2.

I think we can be in state >1 with no waiters - for example, when the final
waiter is woken.

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).

>> +
>> +   cond_locks are never in the taken state, they are either untaken or
>> +   contended.
>
> Please use locked, or unlocked terms everywhere.

I've gone for unlocked, locked and locked with waiters.

>
>> +/* If lock is 0 (untaken), set to 1 (taken). Return 0. Lock acquired.
>> +   Otherwise lock is unchanged. Return nonzero. Lock not acquired.  */
>
> Use GNU style variable name and value usage i.e. `lock` is the variable name,
> while `LOCK` is the value of `lock`. So you can say "If the value of lock is..."
> or "If LOCK is...".
>
> Suggest:
>
> If LOCK is 0 (unlocked), set to 1 (locked) and return 0 to indicate the
> lock was acquired, otherwise the lock is unchanged and return non-zero
> to indicate the lock was not acquired.

Split into two sentences, but basically used your suggestion.

>>  #define lll_trylock(lock)    \
>>    atomic_compare_and_exchange_bool_acq (&(lock), 1, 0)
>>
>> +/* If lock is 0 (untaken), set to 2 (contended). Return 0. Lock acquired.
>> +   Otherwise lock is unchanged. Return nonzero. Lock not acquired.  */
>
> Please rewrite into full sentences.

Done.

>> +/* If futex is 0 (untaken), set to 1 (taken). Lock acquired.
>> +   Otherwise, block until lock is acquired. After blocking, futex is 2
>> +   (contended).  */
>
> Please rewrite into full sentences.

Done.

>>  #define __lll_lock(futex, private)                                      \
>>    ((void)                                                               \
>>     ({                                                                   \
>> @@ -52,6 +87,11 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden;
>>    __lll_lock (&(futex), private)
>>
>>
>> +/* If futex is 0 (untaken), set to id (taken). Return 0. Lock acquired.
>> +   Otherwise, block until either:
>> +   1) Lock is acquired. Return 0. futex is id | FUTEX_WAITERS (contended).
>> +   2) Previous owner of futex dies. Return value of futex, which is id of
>> +      dead owner with FUTEX_OWNER_DIED set. Lock not acquired.  */
>
> Please rewrite into full sentences.

Done.

>>  #define __lll_robust_lock(futex, id, private)                           \
>>    ({                                                                    \
>>      int *__futex = (futex);                                             \
>> @@ -69,6 +109,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 (contended). cond locks only have
>> +   untaken and contended states, so there is no need to check the value of
>> +   futex before setting.
>> +   If previous value of futex was 0 (untaken), lock is acquired.
>> +   Otherwise, block until lock is acquired. futex will still be 2 (contended)
>> +   after acquisition.  */
>
> Please rewrite into full sentences.
>

Done.

>>  #define __lll_cond_lock(futex, private)                                 \
>>    ((void)                                                               \
>>     ({                                                                   \
>> @@ -79,6 +125,12 @@ 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 (untaken), set to id | FUTEX_WAITERS (contended). Lock
>> +   acquired.
>> +   Otherwise, block until either:
>> +   1) Lock is acquired. Return 0. futex is id | FUTEX_WAITERS (contended).
>> +   2) Previous owner of futex dies. Return the value of futex, which is id of
>> +      dead owner with FUTEX_OWNER_DIED set. Lock not acquired.  */
>
> Please rewrite into full sentences.
>

Done.

>>  #define lll_robust_cond_lock(futex, id, private)     \
>>    __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private)
>>
>> @@ -88,8 +140,7 @@ 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.  */
>
> Can you comment on the return value of the futex if it times out?
>

Done.

>>  #define __lll_timedlock(futex, abstime, private)                \
>>    ({                                                            \
>>      int *__futex = (futex);                                     \
>> @@ -104,6 +155,7 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
>>    __lll_timedlock (&(futex), abstime, private)
>>
>>
>> +/* As __lll_robust_lock, but with a timeout.  */
>
> Similarly.
>

Similarly done.

>>  #define __lll_robust_timedlock(futex, abstime, id, private)             \
>>    ({                                                                    \
>>      int *__futex = (futex);                                             \
>> @@ -121,6 +173,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 (untaken). Lock is released.
>> +   If previous value of futex was > 1 (contended), wake any waiters. (Waiter
>> +   that acquires the lock will set futex to >1 (contended).)  */
>
> Please rewrite into full sentences.
>

Done.

>>  #define __lll_unlock(futex, private)                    \
>>    ((void)                                               \
>>     ({                                                   \
>> @@ -132,10 +187,12 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
>>  #define lll_unlock(futex, private)   \
>>    __lll_unlock (&(futex), private)
>>
>> -
>>  /* 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 (untaken). Lock is released.
>> +   If previous value of futex had FUTEX_WAITERS set, wake any waiters. (Waiter
>> +   that acquires the lock will set FUTEX_WAITERS.)  */
>
> Please rewrite into full sentences.
>

Done.

2014-09-26  Bernard Ogden  <bernie.ogden@linaro.org>

	* nptl/lowlevellock.c: Add comments.
	* nptl/lowlevelrobustlock.c: Likewise.
	* sysdeps/nptl/lowlevellock.h: Likewise.

---

Comments

Torvald Riegel Oct. 6, 2014, 12:26 p.m. | #1
On Mon, 2014-09-29 at 16:39 +0100, Bernard Ogden wrote:
> > unneccessary => unnecessary, spell check please.
> 
> >> +   the uncontended cases and hence do not involve syscalls. Unlikely
> >> +   (contended case) paths usually will involve syscalls to wait or to wake.
> >> +
> >> +   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.  */
> >> +
> >> +/* The states of locks are:
> >> +    0  -  untaken
> >> +    1  -  taken (by one user)
> >> +   >1  -  contended (taken by 1 user, there may be other users waiting)
> >
> > I don't think this is true, I think 2 is explicitly "locked, one or more waiters"
> >
> > Suggest:
> >
> > 0 - unlocked.
> > 1 - locked, no waiters.
> > 2 - locked, one or more waiters.
> 
> I did consider putting '2', but abandoned it because the checks are all for
> >1 and I haven't proved that nothing in glibc is fiddling the values of
> futexes to >2.

Sounds good to me.  In a future cleanup, we can change 0/1/2 to enums or
such.

> I think we can be in state >1 with no waiters - for example, when the final
> waiter is woken.

Agreed.  "2" tells unlock that there *may* be waiters that are blocked
due to using futex_wait.

> 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.

> >> +
> >> +   cond_locks are never in the taken state, they are either untaken or
> >> +   contended.
> >
> > 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".

> diff --git a/nptl/lowlevellock.c b/nptl/lowlevellock.c
> index e198af7..c14b24a 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,10 @@ __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private)
>  }
>  
> 
> +/* The kernel notifies a process which uses CLONE_CHILD_CLEARTID via futex
> +   wakeup when the clone terminates.  The memory location contains the

/wakeup/wake-up/

> +   thread ID while the clone is running and is reset to zero
> +   afterwards.	*/

Could you add who resets it?

>  int
>  __lll_timedwait_tid (int *tidp, const struct timespec *abstime)
>  {
> @@ -113,8 +117,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

/to/up to/

> +         operations for futex wakeup when the clone terminates.

/wakeup/wake-up/

> +      */
>        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..470fe00 100644
> --- a/nptl/lowlevelrobustlock.c
> +++ b/nptl/lowlevelrobustlock.c
> @@ -36,14 +36,17 @@ __lll_robust_lock_wait (int *futex, int private)
>  
>    do
>      {
> +      /* If owner died, return the present value of the futex.  */

/owner/the owner/

>        if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED))
>  	return oldval;
>  
> +      /* Attempt to put lock into state locked 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 owner died, return the present value of the futex.  */

/owner/the owner/

>        if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED))
>  	return oldval;
>  
> +      /* Attempt to put lock into state locked 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..d8c9846 100644
> --- a/sysdeps/nptl/lowlevellock.h
> +++ b/sysdeps/nptl/lowlevellock.h
> @@ -22,9 +22,40 @@
>  #include <atomic.h>
>  #include <lowlevellock-futex.h>
>  
> +/* 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.

Then this...

> +   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.  */


> +   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.

> +   The states of robust locks are:
> +    0  - unlocked
> +   id  - locked (by user identified by id & FUTEX_TID_MASK)
> +
> +   The following flags may be set in the robust lock value:
> +   FUTEX_WAITERS     - locked with waiters (there _may_ be waiters)
> +   FUTEX_OWNER_DIED  - owning user has exited without releasing the futex.  */
> +
> +
> +/* 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.

>  #define lll_trylock(lock)	\
>    atomic_compare_and_exchange_bool_acq (&(lock), 1, 0)
>  
> +/* If LOCK is 0 (unlocked), set to 2 (locked with waiters) 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.  */
>  #define lll_cond_trylock(lock)	\
>    atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)
>  
> @@ -35,6 +66,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.  */
> +/* 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 (unlocked), set to 1 (locked) and return. Otherwise block
> +   until we acquire the lock, at which point FUTEX is 2 (locked with waiters),
> +   then return. The lock is aways acquired on return.  */
>  #define __lll_lock(futex, private)                                      \
>    ((void)                                                               \
>     ({                                                                   \
> @@ -52,6 +89,13 @@ extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden;
>    __lll_lock (&(futex), private)
>  
> 
> +/* If FUTEX is 0 (unlocked), set to ID (locked) and return 0 to indicate the
> +   lock was acquired. Otherwise, block until either:
> +   1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS
> +      (locked with waiters).  Return 0 to indicate that the lock was acquired.
> +   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.

>  #define __lll_robust_lock(futex, id, private)                           \
>    ({                                                                    \
>      int *__futex = (futex);                                             \
> @@ -69,6 +113,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 (locked with waiters). cond locks only have
/cond/condvar/ or /cond/condition variable/
> +   unlocked and locked with waiters states, so there is no need to check FUTEX
> +   before setting.
> +   If FUTEX was 0 (unlocked) then return. Otherwise, block until the lock is
> +   acquired, at which point FUTEX is 2 (locked with waiters). The lock is
> +   always acquired on return.  */
>  #define __lll_cond_lock(futex, private)                                 \
>    ((void)                                                               \
>     ({                                                                   \
> @@ -79,6 +129,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 (unlocked), set to ID | FUTEX_WAITERS (locked with waiters)
> +   and return, indicating that the lock is acquired. Otherwise, block until
> +   either:
> +   1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS
> +      (locked with waiters), then return.
> +   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.  */
>  #define lll_robust_cond_lock(futex, id, private)	\
>    __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private)
>  
> @@ -88,8 +146,8 @@ 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

double space after .

> +   ETIMEDOUT. If ABSTIME is invalid, return EINVAL.  */
>  #define __lll_timedlock(futex, abstime, private)                \
>    ({                                                            \
>      int *__futex = (futex);                                     \
> @@ -104,6 +162,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 +181,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 (unlocked), releasing the lock. If FUTEX was
> +   >1 (locked with waiters) then wake any waiters. (The waiter who acquires

, before "then"

> +   the lock will set FUTEX to >1.)  */
>  #define __lll_unlock(futex, private)                    \
>    ((void)                                               \
>     ({                                                   \
> @@ -132,10 +195,12 @@ extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
>  #define lll_unlock(futex, private)	\
>    __lll_unlock (&(futex), private)
>  
> -
>  /* 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 (unlocked), 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 +224,11 @@ 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.	*/
> +   afterwards. The kernel to version 3.16.3 does not use the private futex
> +   operations for futex wakeup when the clone terminates.  */
>  #define lll_wait_tid(tid) \
>    do {					\
>      __typeof (tid) __tid;		\
> @@ -178,6 +239,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;					\
Bernie Ogden Oct. 9, 2014, 3:47 p.m. | #2
Thanks. I've incorporated most of your comments locally.

Before I post another version, can we agree on the terms for the lock states?
>> >> +
>> >> +   cond_locks are never in the taken state, they are either untaken or
>> >> +   contended.
>> >
>> > 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".

I also prefer acquired/not acquired, but didn't feel strongly enough
about it to argue the point with Carlos. I would prefer not to keep
switching between terminologies, though.

Carlos (or anyone else), do you feel strongly that locked/unlocked is
the better terminology here?

Patch

diff --git a/nptl/lowlevellock.c b/nptl/lowlevellock.c
index e198af7..c14b24a 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,10 @@  __lll_timedlock_wait (int *futex, const struct timespec *abstime, int private)
 }
 
 
+/* 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.	*/
 int
 __lll_timedwait_tid (int *tidp, const struct timespec *abstime)
 {
@@ -113,8 +117,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 wakeup 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..470fe00 100644
--- a/nptl/lowlevelrobustlock.c
+++ b/nptl/lowlevelrobustlock.c
@@ -36,14 +36,17 @@  __lll_robust_lock_wait (int *futex, int private)
 
   do
     {
+      /* If owner died, return the present value of the futex.  */
       if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED))
 	return oldval;
 
+      /* Attempt to put lock into state locked 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 owner died, return the present value of the futex.  */
       if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED))
 	return oldval;
 
+      /* Attempt to put lock into state locked 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..d8c9846 100644
--- a/sysdeps/nptl/lowlevellock.h
+++ b/sysdeps/nptl/lowlevellock.h
@@ -22,9 +22,40 @@ 
 #include <atomic.h>
 #include <lowlevellock-futex.h>
 
+/* Uses futexes to avoid unnecessary calls into the kernel. Likely paths are
+   the cases with no waiters and hence do not involve syscalls. Unlikely paths
+   usually will involve syscalls to wait or to wake.
+
+   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.  */
+
+/* The states of locks are:
+    0  -  unlocked
+    1  -  locked, no waiters
+   >1  -  locked with waiters, there _may_ be waiters
+
+   cond_locks are never in the locked state, they are either unlocked or
+   locked with waiters.
+
+   The states of robust locks are:
+    0  - unlocked
+   id  - locked (by user identified by id & FUTEX_TID_MASK)
+
+   The following flags may be set in the robust lock value:
+   FUTEX_WAITERS     - locked with waiters (there _may_ be waiters)
+   FUTEX_OWNER_DIED  - owning user has exited without releasing the futex.  */
+
+
+/* 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.  */
 #define lll_trylock(lock)	\
   atomic_compare_and_exchange_bool_acq (&(lock), 1, 0)
 
+/* If LOCK is 0 (unlocked), set to 2 (locked with waiters) 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.  */
 #define lll_cond_trylock(lock)	\
   atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)
 
@@ -35,6 +66,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.  */
+/* 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 (unlocked), set to 1 (locked) and return. Otherwise block
+   until we acquire the lock, at which point FUTEX is 2 (locked with waiters),
+   then return. The lock is aways acquired on return.  */
 #define __lll_lock(futex, private)                                      \
   ((void)                                                               \
    ({                                                                   \
@@ -52,6 +89,13 @@  extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden;
   __lll_lock (&(futex), private)
 
 
+/* If FUTEX is 0 (unlocked), set to ID (locked) and return 0 to indicate the
+   lock was acquired. Otherwise, block until either:
+   1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS
+      (locked with waiters).  Return 0 to indicate that the lock was acquired.
+   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.  */
 #define __lll_robust_lock(futex, id, private)                           \
   ({                                                                    \
     int *__futex = (futex);                                             \
@@ -69,6 +113,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 (locked with waiters). cond locks only have
+   unlocked and locked with waiters states, so there is no need to check FUTEX
+   before setting.
+   If FUTEX was 0 (unlocked) then return. Otherwise, block until the lock is
+   acquired, at which point FUTEX is 2 (locked with waiters). The lock is
+   always acquired on return.  */
 #define __lll_cond_lock(futex, private)                                 \
   ((void)                                                               \
    ({                                                                   \
@@ -79,6 +129,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 (unlocked), set to ID | FUTEX_WAITERS (locked with waiters)
+   and return, indicating that the lock is acquired. Otherwise, block until
+   either:
+   1) We acquire the lock, at which point FUTEX will be ID | FUTEX_WAITERS
+      (locked with waiters), then return.
+   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.  */
 #define lll_robust_cond_lock(futex, id, private)	\
   __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private)
 
@@ -88,8 +146,8 @@  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 +162,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 +181,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 (unlocked), releasing the lock. If FUTEX was
+   >1 (locked with waiters) then wake any waiters. (The waiter who acquires
+   the lock will set FUTEX to >1.)  */
 #define __lll_unlock(futex, private)                    \
   ((void)                                               \
    ({                                                   \
@@ -132,10 +195,12 @@  extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
 #define lll_unlock(futex, private)	\
   __lll_unlock (&(futex), private)
 
-
 /* 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 (unlocked), 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 +224,11 @@  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.	*/
+   afterwards. The kernel to version 3.16.3 does not use the private futex
+   operations for futex wakeup when the clone terminates.  */
 #define lll_wait_tid(tid) \
   do {					\
     __typeof (tid) __tid;		\
@@ -178,6 +239,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;					\