Re: [PATCH v2] lowlevellock comments

[Torvald Riegel <triegel at redhat dot com>]

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;					\