Re: [PATCH roland/lll-futex] Separate Linuxisms from lowlevellock.h, make a generic one

[Torvald Riegel <triegel at redhat dot com>]

On Wed, 2014-07-02 at 16:14 -0700, Roland McGrath wrote:
> diff --git a/sysdeps/nptl/lowlevellock-futex.h b/sysdeps/nptl/lowlevellock-futex.h
> new file mode 100644
> index 0000000..12f3876
> --- /dev/null
> +++ b/sysdeps/nptl/lowlevellock-futex.h
> @@ -0,0 +1,86 @@
> +/* Low-level locking access to futex facilities.  Stub version.
> +   Copyright (C) 2014 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library.  If not, see
> +   <http://www.gnu.org/licenses/>.  */
> +
> +#ifndef _LOWLEVELLOCK_FUTEX_H
> +#define _LOWLEVELLOCK_FUTEX_H   1
> +
> +#include <errno.h>
> +
> +
> +/* Values for 'private' parameter of locking macros.  Note pthreadP.h
> +   optimizes for these exact values, though they are not required.  */
> +#define LLL_PRIVATE     0
> +#define LLL_SHARED      128
> +
> +
> +/* For most of these macros, the return value is never really used.
> +   Nevertheless, the protocol is that each one returns a negated errno
> +   code for failure or zero for success.  (Note that the corresponding
> +   Linux system calls can sometimes return positive values for success
> +   cases too.  We never use those values.)  */
> +
> +
> +/* Wait while *FUTEXP == VAL for an lll_futex_wake call on FUTEXP.  */
> +#define lll_futex_wait(futexp, val, private) \
> +  lll_futex_timed_wait (futexp, val, NULL, private)
> +
> +/* Wait until a lll_futex_wake call on FUTEXP, or TIMEOUT elapses.  */
> +#define lll_futex_timed_wait(futexp, val, timeout, private)             \
> +  -ENOSYS

I'd prefer if the comment would explicitly mention spurious wake-ups;
what you write could be implementable but is not precisely how we use
futexes.  Maybe just say that it waits until a real or a spurious
wake-up occurs?

> +/* This macro should be defined only if FUTEX_CLOCK_REALTIME is also defined.
> +   If CLOCKBIT is zero, this is identical to lll_futex_timed_wait.
> +   If CLOCKBIT has FUTEX_CLOCK_REALTIME set, then it's the same but
> +   TIMEOUT is counted by CLOCK_REALTIME rather than CLOCK_MONOTONIC.  */
> +#define lll_futex_timed_wait_bitset(futexp, val, timeout, clockbit, private) \
> +  -ENOSYS
> +
> +/* Wake up up to NR waiters on FUTEXP.  */
> +#define lll_futex_wake(futexp, nr, private)                             \
> +  -ENOSYS
> +
> +/* Wake up up to NR_WAKE waiters on FUTEXP.  Move up to NR_MOVE of the
> +   rest from waiting on FUTEXP to waiting on MUTEX (a different futex).  */
> +#define lll_futex_requeue(futexp, nr_wake, nr_move, mutex, val, private) \
> +  -ENOSYS

Call mutex futexp2 (or something else) instead?  (It's just a parameter
name, but it's also not one of our mutexes, really...)

> +
> +/* Wake up up to NR_WAKE waiters on FUTEXP and NR_WAKE2 on FUTEXP2.  */
> +#define lll_futex_wake_unlock(futexp, nr_wake, nr_wake2, futexp2, private) \
> +  -ENOSYS
> +
> +
> +/* Like lll_futex_wait (FUTEXP, VAL, PRIVATE) but with the expectation
> +   that lll_futex_cmp_requeue_pi (FUTEXP, _, _, MUTEX, _, PRIVATE) will
> +   be used to do the wakeup.  Confers priority-inheritance behavior on
> +   the waiter.  */
> +#define lll_futex_wait_requeue_pi(futexp, val, mutex, private) \
> +  lll_futex_timed_wait_requeue_pi (futexp, val, NULL, 0, mutex, private)
> +
> +/* Like lll_futex_wait_requeue_pi, but with a timeout.  */
> +#define lll_futex_timed_wait_requeue_pi(futexp, val, timeout, clockbit, \
> +                                        mutex, private)                 \
> +  -ENOSYS
> +
> +/* Like lll_futex_requeue, but pairs with lll_futex_wait_requeue_pi
> +   and inherits priority from the waiter.  */
> +#define lll_futex_cmp_requeue_pi(futexp, nr_wake, nr_move, mutex,       \
> +                                 val, private)                          \
> +  -ENOSYS
> +
> +
> +#endif  /* lowlevellock-futex.h */
> diff --git a/sysdeps/nptl/lowlevellock.h b/sysdeps/nptl/lowlevellock.h
> new file mode 100644
> index 0000000..e440bb4
> --- /dev/null
> +++ b/sysdeps/nptl/lowlevellock.h
> @@ -0,0 +1,201 @@
> +/* Low-level lock implementation.  Generic futex-based version.
> +   Copyright (C) 2005-2014 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library.  If not, see
> +   <http://www.gnu.org/licenses/>.  */
> +
> +#ifndef _LOWLEVELLOCK_H
> +#define _LOWLEVELLOCK_H	1
> +
> +#include <atomic.h>
> +#include <lowlevellock-futex.h>

I believe it would be good if we could document these later on; now that
there's a generic version, there's (more or less) just one place we'd
need documentation at.

> +#define lll_robust_dead(futexv, private) \
> +  do									      \
> +    {									      \
> +      int *__futexp = &(futexv);					      \
> +      atomic_or (__futexp, FUTEX_OWNER_DIED);				      \
> +      lll_futex_wake (__futexp, 1, private);				      \
> +    }									      \
> +  while (0)
> +
> +#define lll_trylock(lock)	\
> +  atomic_compare_and_exchange_bool_acq (&(lock), 1, 0)
> +
> +#define lll_cond_trylock(lock)	\
> +  atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)
> +
> +#define __lll_robust_trylock(futex, id) \
> +  (atomic_compare_and_exchange_val_acq (futex, id, 0) != 0)

Use atomic_compare_and_exchange_bool_acq (or clean that up later)?

> +#define lll_robust_trylock(lock, id) \
> +  __lll_robust_trylock (&(lock), id)
> +
> +extern void __lll_lock_wait_private (int *futex) attribute_hidden;
> +extern void __lll_lock_wait (int *futex, int private) attribute_hidden;
> +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.  */
> +#define __lll_lock(futex, private)                                      \
> +  ((void)                                                               \
> +   ({                                                                   \
> +     int *__futex = (futex);                                            \
> +     if (__glibc_unlikely                                               \
> +         (atomic_compare_and_exchange_bool_acq (__futex, 1, 0)))        \
> +       {                                                                \
> +         if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \
> +           __lll_lock_wait_private (__futex);                           \
> +         else                                                           \
> +           __lll_lock_wait (__futex, private);                          \
> +       }                                                                \
> +   }))
> +#define lll_lock(futex, private)	\
> +  __lll_lock (&(futex), private)
> +
> +
> +#define __lll_robust_lock(futex, id, private)                           \
> +  ({                                                                    \
> +    int *__futex = (futex);                                             \
> +    int __val = 0;                                                      \
> +                                                                        \
> +    if (__glibc_unlikely                                                \
> +        (atomic_compare_and_exchange_bool_acq (__futex, id, 0)))        \
> +      __val = __lll_robust_lock_wait (__futex, private);                \
> +    __val;                                                              \
> +  })
> +#define lll_robust_lock(futex, id, private)     \
> +  __lll_robust_lock (&(futex), id, 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.  */
> +#define __lll_cond_lock(futex, private)                         \
> +  ((void)                                                       \
> +   ({                                                           \
> +     int *__futex = (futex);                                    \
> +     if (__glibc_unlikely (atomic_exchange_acq (__futex, 2)))   \
> +       __lll_lock_wait (__futex, private);                      \
> +   }))
> +#define lll_cond_lock(futex, private) __lll_cond_lock (&(futex), private)
> +
> +
> +#define lll_robust_cond_lock(futex, id, private)	\
> +  __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private)
> +
> +
> +extern int __lll_timedlock_wait (int *futex, const struct timespec *,
> +				 int private) attribute_hidden;
> +extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
> +					int private) attribute_hidden;
> +
> +#define __lll_timedlock(futex, abstime, private)                \
> +  ({                                                            \
> +    int *__futex = (futex);                                     \
> +    int __val = 0;                                              \
> +                                                                \
> +    if (__glibc_unlikely (atomic_exchange_acq (__futex, 1)))    \
> +      __val = __lll_timedlock_wait (__futex, abstime, private); \
> +    __val;                                                      \
> +  })
> +#define lll_timedlock(futex, abstime, private)  \
> +  __lll_timedlock (&(futex), abstime, private)

This differs from __lll_lock (e.g., CAS vs. atomic_exchange).  I suppose
that resembles the current code we have; nonetheless, I find it
surprising (e.g., lll_lock will not overwrite a value of 2 in the lock
(ie, contended), whereas timedlock will).  That changes whether a
subsequent lll_unlock will do a lll_futex_wake or not.

> +
> +
> +#define __lll_robust_timedlock(futex, abstime, id, private)             \
> +  ({                                                                    \
> +    int *__futex = (futex);                                             \
> +    int __val = 0;                                                      \
> +                                                                        \
> +    if (__glibc_unlikely                                                \
> +        (atomic_compare_and_exchange_bool_acq (__futex, id, 0)))        \
> +      __val = __lll_robust_timedlock_wait (__futex, abstime, private);  \
> +    __val;                                                              \
> +  })
> +#define lll_robust_timedlock(futex, abstime, id, private)       \
> +  __lll_robust_timedlock (&(futex), abstime, id, 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.  */
> +#define __lll_unlock(futex, private)                    \
> +  ((void)                                               \
> +   ({                                                   \
> +     int *__futex = (futex);                            \
> +     int __oldval = atomic_exchange_rel (__futex, 0);   \
> +     if (__glibc_unlikely (__oldval > 1))               \
> +       lll_futex_wake (__futex, 1, private);            \
> +   }))
> +#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.  */
> +#define __lll_robust_unlock(futex, private)             \
> +  ((void)                                               \
> +   ({                                                   \
> +     int *__futex = (futex);                            \
> +     int __oldval = atomic_exchange_rel (__futex, 0);   \
> +     if (__glibc_unlikely (__oldval & FUTEX_WAITERS))	\
> +       lll_futex_wake (__futex, 1, private);            \
> +   }))
> +#define lll_robust_unlock(futex, private)       \
> +  __lll_robust_unlock (&(futex), private)
> +
> +
> +#define lll_islocked(futex) \
> +  ((futex) != LLL_LOCK_INITIALIZER)
> +
> +
> +/* Our internal lock implementation is identical to the binary-compatible
> +   mutex implementation. */
> +
> +/* Initializers for lock.  */
> +#define LLL_LOCK_INITIALIZER		(0)
> +#define LLL_LOCK_INITIALIZER_LOCKED	(1)
> +
> +/* The states of a lock are:
> +    0  -  untaken
> +    1  -  taken by one user

I guess "(not) acquired" is a better term here?

> +   >1  -  taken by more users */

A mutex is never acquired by more than one thread.  IIRC, this state
means that the lock is acquired by one thread, and other threads _might_
be trying to acquire the lock as well (including being blocked on the
futex).

> +
> +/* 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.	*/
> +#define lll_wait_tid(tid) \
> +  do {					\
> +    __typeof (tid) __tid;		\
> +    while ((__tid = (tid)) != 0)	\
> +      lll_futex_wait (&(tid), __tid, LLL_SHARED);\
> +  } while (0)
> +
> +extern int __lll_timedwait_tid (int *, const struct timespec *)
> +     attribute_hidden;
> +
> +#define lll_timedwait_tid(tid, abstime) \
> +  ({							\
> +    int __res = 0;					\
> +    if ((tid) != 0)					\
> +      __res = __lll_timedwait_tid (&(tid), (abstime));	\
> +    __res;						\
> +  })
> +
> +
> +#endif	/* lowlevellock.h */