[PATCH v2] lowlevellock comments

[Bernard Ogden <bernie dot ogden at linaro dot org>]

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.

---

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