[PATCH 1/2] Add futex wrappers with error checking

[Torvald Riegel <triegel at redhat dot com>]

This adds new functions for futex operations, starting with wait,
timedwait, wake.  They add documentation and error checking according to
the outcomes of this thread:
https://sourceware.org/ml/libc-alpha/2014-09/msg00381.html

My intent is to move over other futex callers incrementally, over time.
Right now, this is not intended to replace the futex operations aimed at
lowlevellocks, but just those in other places that uses the lll_futex_*
functions now.

It is implemented on top of lll_futex_*, so that we can expose the raw
futex to users via a syscall wrapper (or external futex_wait,...
functions), should we want to do that in the future.

We can add other futex operations as necessary, and when there is a need
(e.g., PI cmp requeue).

They have been tested on x86 and x86_64 with pthread_once (patch 2/2)
and the new semaphore implementation I'm about to post.


2014-12-05  Torvald Riegel  <triegel@redhat.com>

	* nptl/futex-internal.h: New file.

commit c3ee46bfe1d25142bb572a28643bfebf460e8285
Author: Torvald Riegel <triegel@redhat.com>
Date:   Thu Dec 4 14:12:23 2014 +0100

    Add wrappers for futex operations for glibc-internal use.

diff --git a/nptl/futex-internal.h b/nptl/futex-internal.h
new file mode 100644
index 0000000..ea55e61
--- /dev/null
+++ b/nptl/futex-internal.h
@@ -0,0 +1,173 @@
+/* futex operations for glibc-internal use.
+   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 FUTEX_INTERNAL_H
+#define FUTEX_INTERNAL_H
+
+#include <errno.h>
+#include <lowlevellock.h>
+#include <sys/time.h>
+
+/* This file defines futex operations used internally in glibc.  They are
+   wrappers for the syscalls and add glibc-specific error checking of the
+   syscall return value.  We abort on error codes that are caused by bugs in
+   glibc or in the calling application, or when an error code is not know.
+   We return error codes that can arise in correct executions to the caller.
+   Each operation calls out exactly the return values that callers need to
+   handle.
+
+   The private flag must be either FUTEX_PRIVATE or FUTEX_SHARED.
+
+   We expect callers to only use these operations if futexes are supported.
+
+   Due to POSIX requirements on when synchronization data structures such
+   as mutexes or semaphores can be destructed and due to the futex design
+   having separate fast/slow paths for wake-ups, we need to consider that
+   futex_wake calls might effectively target a data structure that has been
+   destructed and reused for another object, or unmapped; thus, some
+   errors or spurious wake-ups can happen in correct executions that would
+   not be possible in a program using just a single futex whose lifetime
+   does not end before the program terminates.  For background, see:
+   https://sourceware.org/ml/libc-alpha/2014-04/msg00075.html
+   https://lkml.org/lkml/2014/11/27/472  */
+
+#define FUTEX_PRIVATE LLL_PRIVATE
+#define FUTEX_SHARED  LLL_SHARED
+
+/* Returns FUTEX_PRIVATE if pshared is zero and private futexes are supported;
+   returns FUTEX_SHARED otherwise.  */
+static int __attribute__ ((unused))
+futex_private_if_supported (int pshared)
+{
+#ifdef __ASSUME_PRIVATE_FUTEX
+  return pshared != 0 ? FUTEX_SHARED : FUTEX_PRIVATE;
+#else
+  return pshared != 0 ? FUTEX_SHARED :
+      THREAD_GETMEM (THREAD_SELF, header.private_futex) ^ FUTEX_PRIVATE_FLAG;
+#endif
+}
+
+
+/* Atomically wrt. other futex operations, this blocks iff the value at
+   *futex matches the expected value.  This is semantically equivalent to:
+     l = <get lock associated with futex> (futex);
+     wait_flag = <get wait_flag associated with futex> (futex);
+     lock (l);
+     val = atomic_load_relaxed (futex);
+     if (val != expected) { unlock (l); return EWOULDBLOCK; }
+     atomic_store_relaxed (wait_flag, 1);
+     unlock (l);
+     // Now block; can time out in futex_time_wait (see below)
+     while (atomic_load_relaxed(wait_flag));
+
+   Note that no guarantee of a happens-before relation between a woken
+   futex_wait and a futex_wake is documented; however, this does not matter
+   in practice because we have to consider spurious wake-ups (see below),
+   and thus would not be able to reason which futex_wake woke us anyway.
+
+   Returns 0 if woken by a futex operation or spuriously.  (Note that due to
+   the POSIX requirements mentioned above, we need to conservatively assume
+   that unrelated futex_wake operations could wake this futex; it is easiest
+   to just be prepared for spurious wake-ups.)
+   Returns -EWOULDBLOCK if the futex' value did not match the expected value.
+   Returns -EINTR if signals or other spurious wake-ups happened.
+
+   Note that some previous code in glibc assumed the futex syscall to start
+   with the equivalent of a seq_cst fence; this allows one to avoid an
+   explicit seq_cst fence before a futex_wait call when synchronizing similar
+   to Dekker synchronization.  However, this is not documented by the kernel
+   to be guaranteed, so we do not assume it here.
+   */
+static int __attribute__ ((unused))
+futex_wait (unsigned* futex, unsigned expected, int private)
+{
+  int err = lll_futex_timed_wait (futex, expected, NULL, private);
+  if (err == 0 || err == -EWOULDBLOCK || err == -EINTR)
+    return err;
+  /* ETIMEDOUT cannot have happened because we provided no timeout.
+     EFAULT must have been caused by a glibc or application bug.
+     EINVAL (wrong alignment or timeout is not normalized) must have been
+     caused by a glibc or application bug.
+     ENOSYS must have been caused by a glibc bug.
+     No other errors are documented at this time.  */
+  abort();
+}
+
+/* Like futex_timed_wait, but will eventually time out (i.e., stop being
+   blocked) after the absolute point in time provided has passed (abstime).
+   We require the caller to provide a normalized abstime.
+
+   Returns 0 if woken by a futex operation or spuriously.  (Note that due to
+   the POSIX requirements mentioned above, we need to conservatively assume
+   that unrelated futex_wake operations could wake this futex; it is easiest
+   to just be prepared for spurious wake-ups.)
+   Returns -EWOULDBLOCK if the futex' value did not match the expected value.
+   Returns -EINTR if signals or other spurious wake-ups happened.
+   Returns -ETIMEDOUT if the timeout expired.
+   */
+static int __attribute__ ((unused))
+futex_timed_wait (unsigned* futex, unsigned expected,
+    const struct timespec* abstime, int private)
+{
+  int err = lll_futex_timed_wait (futex, expected, abstime, private);
+  if (err == 0 || err == -EWOULDBLOCK || err == -EINTR || err == -ETIMEDOUT)
+    return err;
+  /* EFAULT must have been caused by a glibc or application bug.
+     EINVAL (wrong alignment or timeout is not normalized) must have been
+     caused by a glibc or application bug.
+     ENOSYS must have been caused by a glibc bug.
+     No other errors are documented at this time.  */
+  abort();
+}
+
+/* Atomically wrt. to other futex operations, this unblocks the specified
+   number of processes, or all processes blocked on this futex if there are
+   fewer than the specified number.  Semantically, this is equivalent to:
+     l = <get lock associated with futex> (futex);
+     lock (l);
+     for (res = 0; processes_to_wake > 0; processes_to_wake--, res++) {
+       if (<no process blocked on futex>) break;
+       wf = <get wait_flag of a process blocked on futex> (futex);
+       // No happens-before guarantee with woken futex_wait (see above)
+       atomic_store_relaxed (wf, 0);
+     }
+     return res;
+
+   Returns the number of processes woken up.  Note that we need to support
+   futex_wake calls to past futexes whose memory has potentially been reused
+   due to POSIX' requirements on synchronization object destruction (see
+   above);  therefore, we must not report or abort on most errors.  */
+static int __attribute__ ((unused))
+futex_wake (unsigned* futex, int processes_to_wake, int private)
+{
+  int res = lll_futex_wake (futex, processes_to_wake, private);
+  /* EFAULT could have happened due to memory reuse.
+     EINVAL could be either due to incorrect alignment (a bug in glibc or the
+     application) or due to memory being reused for a PI futex.  We cannot
+     distinguish between the two causes, and one of them is correct use, so
+     we do not act in this case.  */
+  if (res == -EFAULT || res == -EINVAL)
+    return 0;
+  /* ENOSYS must have been caused by a glibc bug.
+     No other errors are documented at this time.  */
+  if (res < 0)
+    abort ();
+  return res;
+}
+
+#endif  /* futex-internal.h */