Hello,
This patchset implements a new futex operation, called FUTEX_WAIT_MULTIPLE,
which allows a thread to wait on several futexes at the same time, and be
awoken by any of them.
The use case lies in the Wine implementation of the Windows NT interface
WaitMultipleObjects. This Windows API function allows a thread to sleep
waiting on the first of a set of event sources (mutexes, timers, signal,
console input, etc) to signal. Considering this is a primitive
synchronization operation for Windows applications, being able to quickly
signal events on the producer side, and quickly go to sleep on the
consumer side is essential for good performance of those running over Wine.
Since this API exposes a mechanism to wait on multiple objects, and
we might have multiple waiters for each of these events, a M->N
relationship, the current Linux interfaces fell short on performance
evaluation of large M,N scenarios. We experimented, for instance, with
eventfd, which has performance problems discussed below, but we also
experimented with userspace solutions, like making each consumer wait on
a condition variable guarding the entire list of objects, and then
waking up multiple variables on the producer side, but this is
prohibitively expensive since we either need to signal many condition
variables or share that condition variable among multiple waiters, and
then verify for the event being signaled in userspace, which means
dealing with often false positive wakes ups.
The natural interface to implement the behavior we want, also
considering that one of the waitable objects is a mutex itself, would be
the futex interface. Therefore, this patchset proposes a mechanism for
a thread to wait on multiple futexes at once, and wake up on the first
futex that was awaken.
In particular, using futexes in our Wine use case reduced the CPU
utilization by 4% for the game Beat Saber and by 1.5% for the game
Shadow of Tomb Raider, both running over Proton (a Wine based solution
for Windows emulation), when compared to the eventfd interface. This
implementation also doesn't rely of file descriptors, so it doesn't risk
overflowing the resource.
In time, we are also proposing modifications to glibc and libpthread to
make this feature available for Linux native multithreaded applications
using libpthread, which can benefit from the behavior of waiting on any
of a group of futexes.
Technically, the existing FUTEX_WAIT implementation can be easily
reworked by using futex_wait_multiple() with a count of one, and I
have a patch showing how it works. I'm not proposing it, since
futex is such a tricky code, that I'd be more comfortable to have
FUTEX_WAIT_MULTIPLE running upstream for a couple development cycles,
before considering modifying FUTEX_WAIT.
The patch series includes an extensive set of kselftests validating
the behavior of the interface. We also implemented support[1] on
Syzkaller and survived the fuzzy testing.
Finally, if you'd rather pull directly a branch with this set you can
find it here:
https://gitlab.collabora.com/tonyk/linux/commits/futex-dev
=== Performance of eventfd ===
Polling on several eventfd contexts with semaphore semantics would
provide us with the exact semantics we are looking for. However, as
shown below, in a scenario with sufficient producers and consumers, the
eventfd interface itself becomes a bottleneck, in particular because
each thread will compete to acquire a sequence of waitqueue locks for
each eventfd context in the poll list. In addition, in the uncontended
case, where the producer is ready for consumption, eventfd still
requires going into the kernel on the consumer side.
When a write or a read operation in an eventfd file succeeds, it will try
to wake up all threads that are waiting to perform some operation to
the file. The lock (ctx->wqh.lock) that hold the access to the file value
(ctx->count) is the same lock used to control access the waitqueue. When
all those those thread woke, they will compete to get this lock. Along
with that, the poll() also manipulates the waitqueue and need to hold
this same lock. This lock is specially hard to acquire when poll() calls
poll_freewait(), where it tries to free all waitqueues associated with
this poll. While doing that, it will compete with a lot of read and
write operations that have been waken.
In our use case, with a huge number of parallel reads, writes and polls,
this lock is a bottleneck and hurts the performance of applications. Our
implementation of futex, however, decrease the calls of spin lock by more
than 80% in some user applications.
Finally, eventfd operates on file descriptors, which is a limited
resource that has shown its limitation in our use cases. Despite the
Windows interface not waiting on more than 64 objects at once, we still
have multiple waiters at the same time, and we were easily able to
exhaust the FD limits on applications like games.
The RFC for this patch can be found here:
https://lkml.org/lkml/2019/7/30/1399
Thanks,
André
[1] https://github.com/andrealmeid/syzkaller/tree/futex-wait-multiple
Gabriel Krisman Bertazi (4):
futex: Implement mechanism to wait on any of several futexes
selftests: futex: Add FUTEX_WAIT_MULTIPLE timeout test
selftests: futex: Add FUTEX_WAIT_MULTIPLE wouldblock test
selftests: futex: Add FUTEX_WAIT_MULTIPLE wake up test
include/uapi/linux/futex.h | 20 +
kernel/futex.c | 356 +++++++++++++++++-
.../selftests/futex/functional/.gitignore | 1 +
.../selftests/futex/functional/Makefile | 3 +-
.../futex/functional/futex_wait_multiple.c | 173 +++++++++
.../futex/functional/futex_wait_timeout.c | 38 +-
.../futex/functional/futex_wait_wouldblock.c | 28 +-
.../testing/selftests/futex/functional/run.sh | 3 +
.../selftests/futex/include/futextest.h | 22 +
9 files changed, 635 insertions(+), 7 deletions(-)
create mode 100644 tools/testing/selftests/futex/functional/futex_wait_multiple.c
--
2.25.0
From: Gabriel Krisman Bertazi <[email protected]>
Add test for timeout when waiting for multiple futexes. Skip the test if
it's a x32 application and the kernel returned the approtiaded error,
since this ABI is not supported for this operation.
Signed-off-by: Gabriel Krisman Bertazi <[email protected]>
Co-developed-by: André Almeida <[email protected]>
Signed-off-by: André Almeida <[email protected]>
---
.../futex/functional/futex_wait_timeout.c | 38 ++++++++++++++++++-
.../selftests/futex/include/futextest.h | 22 +++++++++++
2 files changed, 58 insertions(+), 2 deletions(-)
diff --git a/tools/testing/selftests/futex/functional/futex_wait_timeout.c b/tools/testing/selftests/futex/functional/futex_wait_timeout.c
index ee55e6d389a3..2a63e1c2cfb6 100644
--- a/tools/testing/selftests/futex/functional/futex_wait_timeout.c
+++ b/tools/testing/selftests/futex/functional/futex_wait_timeout.c
@@ -11,6 +11,7 @@
*
* HISTORY
* 2009-Nov-6: Initial version by Darren Hart <[email protected]>
+ * 2019-Dec-13: Add WAIT_MULTIPLE test by Krisman <[email protected]>
*
*****************************************************************************/
@@ -41,6 +42,8 @@ int main(int argc, char *argv[])
{
futex_t f1 = FUTEX_INITIALIZER;
struct timespec to;
+ time_t secs;
+ struct futex_wait_block fwb = {&f1, f1, 0};
int res, ret = RET_PASS;
int c;
@@ -65,7 +68,7 @@ int main(int argc, char *argv[])
}
ksft_print_header();
- ksft_set_plan(1);
+ ksft_set_plan(2);
ksft_print_msg("%s: Block on a futex and wait for timeout\n",
basename(argv[0]));
ksft_print_msg("\tArguments: timeout=%ldns\n", timeout_ns);
@@ -79,8 +82,39 @@ int main(int argc, char *argv[])
if (!res || errno != ETIMEDOUT) {
fail("futex_wait returned %d\n", ret < 0 ? errno : ret);
ret = RET_FAIL;
+ } else
+ ksft_test_result_pass("futex_wait timeout succeeds\n");
+
+ info("Calling futex_wait_multiple on f1: %u @ %p\n", f1, &f1);
+
+ /* Setup absolute time */
+ ret = clock_gettime(CLOCK_REALTIME, &to);
+ secs = (to.tv_nsec + timeout_ns) / 1000000000;
+ to.tv_nsec = ((int64_t)to.tv_nsec + timeout_ns) % 1000000000;
+ to.tv_sec += secs;
+ info("to.tv_sec = %ld\n", to.tv_sec);
+ info("to.tv_nsec = %ld\n", to.tv_nsec);
+
+ res = futex_wait_multiple(&fwb, 1, &to,
+ FUTEX_PRIVATE_FLAG | FUTEX_CLOCK_REALTIME);
+
+#ifdef __ILP32__
+ if (res == -1 && errno == ENOSYS) {
+ ksft_test_result_skip("futex_wait_multiple not supported at x32\n");
+ } else {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
}
+#else
+ if (!res || errno != ETIMEDOUT) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
+ } else
+ ksft_test_result_pass("futex_wait_multiple timeout succeeds\n");
+#endif /* __ILP32__ */
- print_result(TEST_NAME, ret);
+ ksft_print_cnts();
return ret;
}
diff --git a/tools/testing/selftests/futex/include/futextest.h b/tools/testing/selftests/futex/include/futextest.h
index ddbcfc9b7bac..bb103bef4557 100644
--- a/tools/testing/selftests/futex/include/futextest.h
+++ b/tools/testing/selftests/futex/include/futextest.h
@@ -38,6 +38,14 @@ typedef volatile u_int32_t futex_t;
#ifndef FUTEX_CMP_REQUEUE_PI
#define FUTEX_CMP_REQUEUE_PI 12
#endif
+#ifndef FUTEX_WAIT_MULTIPLE
+#define FUTEX_WAIT_MULTIPLE 13
+struct futex_wait_block {
+ futex_t *uaddr;
+ futex_t val;
+ __u32 bitset;
+};
+#endif
#ifndef FUTEX_WAIT_REQUEUE_PI_PRIVATE
#define FUTEX_WAIT_REQUEUE_PI_PRIVATE (FUTEX_WAIT_REQUEUE_PI | \
FUTEX_PRIVATE_FLAG)
@@ -80,6 +88,20 @@ futex_wait(futex_t *uaddr, futex_t val, struct timespec *timeout, int opflags)
return futex(uaddr, FUTEX_WAIT, val, timeout, NULL, 0, opflags);
}
+/**
+ * futex_wait_multiple() - block on several futexes with optional timeout
+ * @fwb: wait block user space address
+ * @count: number of entities at fwb
+ * @timeout: absolute timeout
+ */
+static inline int
+futex_wait_multiple(struct futex_wait_block *fwb, int count,
+ struct timespec *timeout, int opflags)
+{
+ return futex(fwb, FUTEX_WAIT_MULTIPLE, count, timeout, NULL, 0,
+ opflags);
+}
+
/**
* futex_wake() - wake one or more tasks blocked on uaddr
* @nr_wake: wake up to this many tasks
--
2.25.0
From: Gabriel Krisman Bertazi <[email protected]>
This is a new futex operation, called FUTEX_WAIT_MULTIPLE, which allows
a thread to wait on several futexes at the same time, and be awoken by
any of them. In a sense, it implements one of the features that was
supported by pooling on the old FUTEX_FD interface.
The use case lies in the Wine implementation of the Windows NT interface
WaitMultipleObjects. This Windows API function allows a thread to sleep
waiting on the first of a set of event sources (mutexes, timers, signal,
console input, etc) to signal. Considering this is a primitive
synchronization operation for Windows applications, being able to quickly
signal events on the producer side, and quickly go to sleep on the
consumer side is essential for good performance of those running over Wine.
Wine developers have an implementation that uses eventfd, but it suffers
from FD exhaustion (there is applications that go to the order of
multi-milion FDs), and higher CPU utilization than this new operation.
The futex list is passed as an array of `struct futex_wait_block`
(pointer, value, bitset) to the kernel, which will enqueue all of them
and sleep if none was already triggered. It returns a hint of which
futex caused the wake up event to userspace, but the hint doesn't
guarantee that is the only futex triggered. Before calling the syscall
again, userspace should traverse the list, trying to re-acquire any of
the other futexes, to prevent an immediate -EWOULDBLOCK return code from
the kernel.
This was tested using three mechanisms:
1) By reimplementing FUTEX_WAIT in terms of FUTEX_WAIT_MULTIPLE and
running the unmodified tools/testing/selftests/futex and a full linux
distro on top of this kernel.
2) By an example code that exercises the FUTEX_WAIT_MULTIPLE path on a
multi-threaded, event-handling setup.
3) By running the Wine fsync implementation and executing multi-threaded
applications, in particular modern games, on top of this implementation.
Changes were tested for the following ABIs: x86_64, i386 and x32.
Support for x32 applications is not implemented since it would
take a major rework adding a new entry point and splitting the current
futex 64 entry point in two and we can't change the current x32 syscall
number without breaking user space compatibility.
CC: Steven Rostedt <[email protected]>
Cc: Richard Yao <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Co-developed-by: Zebediah Figura <[email protected]>
Signed-off-by: Zebediah Figura <[email protected]>
Co-developed-by: Steven Noonan <[email protected]>
Signed-off-by: Steven Noonan <[email protected]>
Co-developed-by: Pierre-Loup A. Griffais <[email protected]>
Signed-off-by: Pierre-Loup A. Griffais <[email protected]>
Signed-off-by: Gabriel Krisman Bertazi <[email protected]>
[Added compatibility code]
Co-developed-by: André Almeida <[email protected]>
Signed-off-by: André Almeida <[email protected]>
---
Changes since RFC:
- Limit waitlist to 128 futexes
- Simplify wait loop
- Document functions
- Reduce allocated space
- Return hint if a futex was awoken during setup
- Check if any futex was awoken prior to sleep
- Drop relative timer logic
- Add compatibility struct and entry points
- Add selftests
---
include/uapi/linux/futex.h | 20 +++
kernel/futex.c | 356 ++++++++++++++++++++++++++++++++++++-
2 files changed, 374 insertions(+), 2 deletions(-)
diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h
index a89eb0accd5e..580001e89c6c 100644
--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -21,6 +21,7 @@
#define FUTEX_WAKE_BITSET 10
#define FUTEX_WAIT_REQUEUE_PI 11
#define FUTEX_CMP_REQUEUE_PI 12
+#define FUTEX_WAIT_MULTIPLE 13
#define FUTEX_PRIVATE_FLAG 128
#define FUTEX_CLOCK_REALTIME 256
@@ -40,6 +41,8 @@
FUTEX_PRIVATE_FLAG)
#define FUTEX_CMP_REQUEUE_PI_PRIVATE (FUTEX_CMP_REQUEUE_PI | \
FUTEX_PRIVATE_FLAG)
+#define FUTEX_WAIT_MULTIPLE_PRIVATE (FUTEX_WAIT_MULTIPLE | \
+ FUTEX_PRIVATE_FLAG)
/*
* Support for robust futexes: the kernel cleans up held futexes at
@@ -150,4 +153,21 @@ struct robust_list_head {
(((op & 0xf) << 28) | ((cmp & 0xf) << 24) \
| ((oparg & 0xfff) << 12) | (cmparg & 0xfff))
+/*
+ * Maximum number of multiple futexes to wait for
+ */
+#define FUTEX_MULTIPLE_MAX_COUNT 128
+
+/**
+ * struct futex_wait_block - Block of futexes to be waited for
+ * @uaddr: User address of the futex
+ * @val: Futex value expected by userspace
+ * @bitset: Bitset for the optional bitmasked wakeup
+ */
+struct futex_wait_block {
+ __u32 __user *uaddr;
+ __u32 val;
+ __u32 bitset;
+};
+
#endif /* _UAPI_LINUX_FUTEX_H */
diff --git a/kernel/futex.c b/kernel/futex.c
index 0cf84c8664f2..0580ab383e5c 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -215,6 +215,8 @@ struct futex_pi_state {
* @rt_waiter: rt_waiter storage for use with requeue_pi
* @requeue_pi_key: the requeue_pi target futex key
* @bitset: bitset for the optional bitmasked wakeup
+ * @uaddr: userspace address of futex
+ * @uval: expected futex's value
*
* We use this hashed waitqueue, instead of a normal wait_queue_entry_t, so
* we can wake only the relevant ones (hashed queues may be shared).
@@ -237,6 +239,8 @@ struct futex_q {
struct rt_mutex_waiter *rt_waiter;
union futex_key *requeue_pi_key;
u32 bitset;
+ u32 __user *uaddr;
+ u32 uval;
} __randomize_layout;
static const struct futex_q futex_q_init = {
@@ -2420,6 +2424,29 @@ static int unqueue_me(struct futex_q *q)
return ret;
}
+/**
+ * unqueue_multiple() - Remove several futexes from their futex_hash_bucket
+ * @q: The list of futexes to unqueue
+ * @count: Number of futexes in the list
+ *
+ * Helper to unqueue a list of futexes. This can't fail.
+ *
+ * Return:
+ * - >=0 - Index of the last futex that was awoken;
+ * - -1 - If no futex was awoken
+ */
+static int unqueue_multiple(struct futex_q *q, int count)
+{
+ int ret = -1;
+ int i;
+
+ for (i = 0; i < count; i++) {
+ if (!unqueue_me(&q[i]))
+ ret = i;
+ }
+ return ret;
+}
+
/*
* PI futexes can not be requeued and must remove themself from the
* hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
@@ -2783,6 +2810,210 @@ static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
return ret;
}
+/**
+ * futex_wait_multiple_setup() - Prepare to wait and enqueue multiple futexes
+ * @qs: The corresponding futex list
+ * @count: The size of the lists
+ * @flags: Futex flags (FLAGS_SHARED, etc.)
+ * @awaken: Index of the last awoken futex
+ *
+ * Prepare multiple futexes in a single step and enqueue them. This may fail if
+ * the futex list is invalid or if any futex was already awoken. On success the
+ * task is ready to interruptible sleep.
+ *
+ * Return:
+ * - 1 - One of the futexes was awaken by another thread
+ * - 0 - Success
+ * - <0 - -EFAULT, -EWOULDBLOCK or -EINVAL
+ */
+static int futex_wait_multiple_setup(struct futex_q *qs, int count,
+ unsigned int flags, int *awaken)
+{
+ struct futex_hash_bucket *hb;
+ int ret, i;
+ u32 uval;
+
+ /*
+ * Enqueuing multiple futexes is tricky, because we need to
+ * enqueue each futex in the list before dealing with the next
+ * one to avoid deadlocking on the hash bucket. But, before
+ * enqueuing, we need to make sure that current->state is
+ * TASK_INTERRUPTIBLE, so we don't absorb any awake events, which
+ * cannot be done before the get_futex_key of the next key,
+ * because it calls get_user_pages, which can sleep. Thus, we
+ * fetch the list of futexes keys in two steps, by first pinning
+ * all the memory keys in the futex key, and only then we read
+ * each key and queue the corresponding futex.
+ */
+retry:
+ for (i = 0; i < count; i++) {
+ qs[i].key = FUTEX_KEY_INIT;
+ ret = get_futex_key(qs[i].uaddr, flags & FLAGS_SHARED,
+ &qs[i].key, FUTEX_READ);
+ if (unlikely(ret)) {
+ for (--i; i >= 0; i--)
+ put_futex_key(&qs[i].key);
+ return ret;
+ }
+ }
+
+ set_current_state(TASK_INTERRUPTIBLE);
+
+ for (i = 0; i < count; i++) {
+ struct futex_q *q = &qs[i];
+
+ hb = queue_lock(q);
+
+ ret = get_futex_value_locked(&uval, q->uaddr);
+ if (ret) {
+ /*
+ * We need to try to handle the fault, which
+ * cannot be done without sleep, so we need to
+ * undo all the work already done, to make sure
+ * we don't miss any wake ups. Therefore, clean
+ * up, handle the fault and retry from the
+ * beginning.
+ */
+ queue_unlock(hb);
+
+ /*
+ * Keys 0..(i-1) are implicitly put
+ * on unqueue_multiple.
+ */
+ put_futex_key(&q->key);
+
+ *awaken = unqueue_multiple(qs, i);
+
+ __set_current_state(TASK_RUNNING);
+
+ /*
+ * On a real fault, prioritize the error even if
+ * some other futex was awoken. Userspace gave
+ * us a bad address, -EFAULT them.
+ */
+ ret = get_user(uval, q->uaddr);
+ if (ret)
+ return ret;
+
+ /*
+ * Even if the page fault was handled, If
+ * something was already awaken, we can safely
+ * give up and succeed to give a hint for userspace to
+ * acquire the right futex faster.
+ */
+ if (*awaken >= 0)
+ return 1;
+
+ goto retry;
+ }
+
+ if (uval != q->uval) {
+ queue_unlock(hb);
+
+ put_futex_key(&qs[i].key);
+
+ /*
+ * If something was already awaken, we can
+ * safely ignore the error and succeed.
+ */
+ *awaken = unqueue_multiple(qs, i);
+ __set_current_state(TASK_RUNNING);
+ if (*awaken >= 0)
+ return 1;
+
+ return -EWOULDBLOCK;
+ }
+
+ /*
+ * The bucket lock can't be held while dealing with the
+ * next futex. Queue each futex at this moment so hb can
+ * be unlocked.
+ */
+ queue_me(&qs[i], hb);
+ }
+ return 0;
+}
+
+/**
+ * futex_wait_multiple() - Prepare to wait on and enqueue several futexes
+ * @qs: The list of futexes to wait on
+ * @op: Operation code from futex's syscall
+ * @count: The number of objects
+ * @abs_time: Timeout before giving up and returning to userspace
+ *
+ * Entry point for the FUTEX_WAIT_MULTIPLE futex operation, this function
+ * sleeps on a group of futexes and returns on the first futex that
+ * triggered, or after the timeout has elapsed.
+ *
+ * Return:
+ * - >=0 - Hint to the futex that was awoken
+ * - <0 - On error
+ */
+static int futex_wait_multiple(struct futex_q *qs, int op,
+ u32 count, ktime_t *abs_time)
+{
+ struct hrtimer_sleeper timeout, *to;
+ int ret, i, flags = 0, hint = 0;
+
+ if (!(op & FUTEX_PRIVATE_FLAG))
+ flags |= FLAGS_SHARED;
+
+ if (op & FUTEX_CLOCK_REALTIME)
+ flags |= FLAGS_CLOCKRT;
+
+ to = futex_setup_timer(abs_time, &timeout, flags, 0);
+ while (1) {
+ ret = futex_wait_multiple_setup(qs, count, flags, &hint);
+ if (ret) {
+ if (ret > 0) {
+ /* A futex was awaken during setup */
+ ret = hint;
+ }
+ break;
+ }
+
+ if (to)
+ hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
+
+ /*
+ * Avoid sleeping if another thread already tried to
+ * wake us.
+ */
+ for (i = 0; i < count; i++) {
+ if (plist_node_empty(&qs[i].list))
+ break;
+ }
+
+ if (i == count && (!to || to->task))
+ freezable_schedule();
+
+ ret = unqueue_multiple(qs, count);
+
+ __set_current_state(TASK_RUNNING);
+
+ if (ret >= 0)
+ break;
+ if (to && !to->task) {
+ ret = -ETIMEDOUT;
+ break;
+ } else if (signal_pending(current)) {
+ ret = -ERESTARTSYS;
+ break;
+ }
+ /*
+ * The final case is a spurious wakeup, for
+ * which just retry.
+ */
+ }
+
+ if (to) {
+ hrtimer_cancel(&to->timer);
+ destroy_hrtimer_on_stack(&to->timer);
+ }
+
+ return ret;
+}
+
static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
ktime_t *abs_time, u32 bitset)
{
@@ -3907,6 +4138,43 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
return -ENOSYS;
}
+/**
+ * futex_read_wait_block - Read an array of futex_wait_block from userspace
+ * @uaddr: Userspace address of the block
+ * @count: Number of blocks to be read
+ *
+ * This function creates and allocate an array of futex_q (we zero it to
+ * initialize the fields) and then, for each futex_wait_block element from
+ * userspace, fill a futex_q element with proper values.
+ */
+inline struct futex_q *futex_read_wait_block(u32 __user *uaddr, u32 count)
+{
+ int i;
+ struct futex_q *qs;
+ struct futex_wait_block fwb;
+ struct futex_wait_block __user *entry =
+ (struct futex_wait_block __user *) uaddr;
+
+ if (!count || count > FUTEX_MULTIPLE_MAX_COUNT)
+ return ERR_PTR(-EINVAL);
+
+ qs = kcalloc(count, sizeof(*qs), GFP_KERNEL);
+ if (!qs)
+ return ERR_PTR(-ENOMEM);
+
+ for (i = 0; i < count; i++) {
+ if (copy_from_user(&fwb, &entry[i], sizeof(fwb))) {
+ kfree(qs);
+ return ERR_PTR(-EFAULT);
+ }
+
+ qs[i].uval = fwb.val;
+ qs[i].uaddr = fwb.uaddr;
+ qs[i].bitset = fwb.bitset;
+ }
+
+ return qs;
+}
SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
struct __kernel_timespec __user *, utime, u32 __user *, uaddr2,
@@ -3919,7 +4187,8 @@ SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
cmd == FUTEX_WAIT_BITSET ||
- cmd == FUTEX_WAIT_REQUEUE_PI)) {
+ cmd == FUTEX_WAIT_REQUEUE_PI ||
+ cmd == FUTEX_WAIT_MULTIPLE)) {
if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
return -EFAULT;
if (get_timespec64(&ts, utime))
@@ -3940,6 +4209,24 @@ SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
val2 = (u32) (unsigned long) utime;
+ if (cmd == FUTEX_WAIT_MULTIPLE) {
+ int ret;
+ struct futex_q *qs;
+
+ if (unlikely(in_x32_syscall()))
+ return -ENOSYS;
+
+ qs = futex_read_wait_block(uaddr, val);
+
+ if (IS_ERR(qs))
+ return PTR_ERR(qs);
+
+ ret = futex_wait_multiple(qs, op, val, tp);
+ kfree(qs);
+
+ return ret;
+ }
+
return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
}
@@ -4102,6 +4389,57 @@ COMPAT_SYSCALL_DEFINE3(get_robust_list, int, pid,
#endif /* CONFIG_COMPAT */
#ifdef CONFIG_COMPAT_32BIT_TIME
+/**
+ * struct compat_futex_wait_block - Block of futexes to be waited for
+ * @uaddr: User address of the futex (compatible pointer)
+ * @val: Futex value expected by userspace
+ * @bitset: Bitset for the optional bitmasked wakeup
+ */
+struct compat_futex_wait_block {
+ compat_uptr_t uaddr;
+ __u32 val;
+ __u32 bitset;
+};
+
+/**
+ * compat_futex_read_wait_block - Read an array of futex_wait_block from
+ * userspace
+ * @uaddr: Userspace address of the block
+ * @count: Number of blocks to be read
+ *
+ * This function does the same as futex_read_wait_block(), except that it
+ * converts the pointer to the futex from the compat version to the regular one.
+ */
+inline struct futex_q *compat_futex_read_wait_block(u32 __user *uaddr,
+ u32 count)
+{
+ int i;
+ struct futex_q *qs;
+ struct compat_futex_wait_block fwb;
+ struct compat_futex_wait_block __user *entry =
+ (struct compat_futex_wait_block __user *) uaddr;
+
+ if (!count || count > FUTEX_MULTIPLE_MAX_COUNT)
+ return ERR_PTR(-EINVAL);
+
+ qs = kcalloc(count, sizeof(*qs), GFP_KERNEL);
+ if (!qs)
+ return ERR_PTR(-ENOMEM);
+
+ for (i = 0; i < count; i++) {
+ if (copy_from_user(&fwb, &entry[i], sizeof(fwb))) {
+ kfree(qs);
+ return ERR_PTR(-EFAULT);
+ }
+
+ qs[i].uaddr = compat_ptr(fwb.uaddr);
+ qs[i].uval = fwb.val;
+ qs[i].bitset = fwb.bitset;
+ }
+
+ return qs;
+}
+
SYSCALL_DEFINE6(futex_time32, u32 __user *, uaddr, int, op, u32, val,
struct old_timespec32 __user *, utime, u32 __user *, uaddr2,
u32, val3)
@@ -4113,7 +4451,8 @@ SYSCALL_DEFINE6(futex_time32, u32 __user *, uaddr, int, op, u32, val,
if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
cmd == FUTEX_WAIT_BITSET ||
- cmd == FUTEX_WAIT_REQUEUE_PI)) {
+ cmd == FUTEX_WAIT_REQUEUE_PI ||
+ cmd == FUTEX_WAIT_MULTIPLE)) {
if (get_old_timespec32(&ts, utime))
return -EFAULT;
if (!timespec64_valid(&ts))
@@ -4128,6 +4467,19 @@ SYSCALL_DEFINE6(futex_time32, u32 __user *, uaddr, int, op, u32, val,
cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)
val2 = (int) (unsigned long) utime;
+ if (cmd == FUTEX_WAIT_MULTIPLE) {
+ int ret;
+ struct futex_q *qs = compat_futex_read_wait_block(uaddr, val);
+
+ if (IS_ERR(qs))
+ return PTR_ERR(qs);
+
+ ret = futex_wait_multiple(qs, op, val, tp);
+ kfree(qs);
+
+ return ret;
+ }
+
return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
}
#endif /* CONFIG_COMPAT_32BIT_TIME */
--
2.25.0
From: Gabriel Krisman Bertazi <[email protected]>
Add test for wouldblock return when waiting for multiple futexes. Skip
the test if it's a x32 application and the kernel returned the approtiaded
error, since this ABI is not supported for this operation.
Signed-off-by: Gabriel Krisman Bertazi <[email protected]>
Co-developed-by: André Almeida <[email protected]>
Signed-off-by: André Almeida <[email protected]>
---
.../futex/functional/futex_wait_wouldblock.c | 28 +++++++++++++++++--
1 file changed, 26 insertions(+), 2 deletions(-)
diff --git a/tools/testing/selftests/futex/functional/futex_wait_wouldblock.c b/tools/testing/selftests/futex/functional/futex_wait_wouldblock.c
index 0ae390ff8164..bcbac042992d 100644
--- a/tools/testing/selftests/futex/functional/futex_wait_wouldblock.c
+++ b/tools/testing/selftests/futex/functional/futex_wait_wouldblock.c
@@ -12,6 +12,7 @@
*
* HISTORY
* 2009-Nov-14: Initial version by Gowrishankar <[email protected]>
+ * 2019-Dec-13: Add WAIT_MULTIPLE test by Krisman <[email protected]>
*
*****************************************************************************/
@@ -40,6 +41,7 @@ int main(int argc, char *argv[])
{
struct timespec to = {.tv_sec = 0, .tv_nsec = timeout_ns};
futex_t f1 = FUTEX_INITIALIZER;
+ struct futex_wait_block fwb = {&f1, f1+1, 0};
int res, ret = RET_PASS;
int c;
@@ -61,7 +63,7 @@ int main(int argc, char *argv[])
}
ksft_print_header();
- ksft_set_plan(1);
+ ksft_set_plan(2);
ksft_print_msg("%s: Test the unexpected futex value in FUTEX_WAIT\n",
basename(argv[0]));
@@ -71,8 +73,30 @@ int main(int argc, char *argv[])
fail("futex_wait returned: %d %s\n",
res ? errno : res, res ? strerror(errno) : "");
ret = RET_FAIL;
+ } else
+ ksft_test_result_pass("futex_wait wouldblock succeeds\n");
+
+ info("Calling futex_wait_multiple on f1: %u @ %p with val=%u\n",
+ f1, &f1, f1+1);
+ res = futex_wait_multiple(&fwb, 1, NULL, FUTEX_PRIVATE_FLAG);
+
+#ifdef __ILP32__
+ if (res != -1 || errno != ENOSYS) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
+ } else {
+ ksft_test_result_skip("futex_wait_multiple not supported at x32\n");
+ }
+#else
+ if (!res || errno != EWOULDBLOCK) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
}
+ ksft_test_result_pass("futex_wait_multiple wouldblock succeeds\n");
+#endif /* __ILP32__ */
- print_result(TEST_NAME, ret);
+ ksft_print_cnts();
return ret;
}
--
2.25.0
From: Gabriel Krisman Bertazi <[email protected]>
Add test for wait at multiple futexes mechanism. Skip the test if it's a
x32 application and the kernel returned the approtiaded error, since this
ABI is not supported for this operation.
Signed-off-by: Gabriel Krisman Bertazi <[email protected]>
Co-developed-by: André Almeida <[email protected]>
Signed-off-by: André Almeida <[email protected]>
---
.../selftests/futex/functional/.gitignore | 1 +
.../selftests/futex/functional/Makefile | 3 +-
.../futex/functional/futex_wait_multiple.c | 173 ++++++++++++++++++
.../testing/selftests/futex/functional/run.sh | 3 +
4 files changed, 179 insertions(+), 1 deletion(-)
create mode 100644 tools/testing/selftests/futex/functional/futex_wait_multiple.c
diff --git a/tools/testing/selftests/futex/functional/.gitignore b/tools/testing/selftests/futex/functional/.gitignore
index a09f57061902..4660128a545e 100644
--- a/tools/testing/selftests/futex/functional/.gitignore
+++ b/tools/testing/selftests/futex/functional/.gitignore
@@ -5,3 +5,4 @@ futex_wait_private_mapped_file
futex_wait_timeout
futex_wait_uninitialized_heap
futex_wait_wouldblock
+futex_wait_multiple
diff --git a/tools/testing/selftests/futex/functional/Makefile b/tools/testing/selftests/futex/functional/Makefile
index 30996306cabc..75f9fface11f 100644
--- a/tools/testing/selftests/futex/functional/Makefile
+++ b/tools/testing/selftests/futex/functional/Makefile
@@ -14,7 +14,8 @@ TEST_GEN_FILES := \
futex_requeue_pi_signal_restart \
futex_requeue_pi_mismatched_ops \
futex_wait_uninitialized_heap \
- futex_wait_private_mapped_file
+ futex_wait_private_mapped_file \
+ futex_wait_multiple
TEST_PROGS := run.sh
diff --git a/tools/testing/selftests/futex/functional/futex_wait_multiple.c b/tools/testing/selftests/futex/functional/futex_wait_multiple.c
new file mode 100644
index 000000000000..b48422e79f42
--- /dev/null
+++ b/tools/testing/selftests/futex/functional/futex_wait_multiple.c
@@ -0,0 +1,173 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/******************************************************************************
+ *
+ * Copyright © Collabora, Ltd., 2019
+ *
+ * DESCRIPTION
+ * Test basic semantics of FUTEX_WAIT_MULTIPLE
+ *
+ * AUTHOR
+ * Gabriel Krisman Bertazi <[email protected]>
+ *
+ * HISTORY
+ * 2019-Dec-13: Initial version by Krisman <[email protected]>
+ *
+ *****************************************************************************/
+
+#include <errno.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <pthread.h>
+#include "futextest.h"
+#include "logging.h"
+
+#define TEST_NAME "futex-wait-multiple"
+#define timeout_ns 100000
+#define MAX_COUNT 128
+#define WAKE_WAIT_US 3000000
+
+int ret = RET_PASS;
+char *progname;
+futex_t f[MAX_COUNT] = {0};
+struct futex_wait_block fwb[MAX_COUNT];
+
+void usage(char *prog)
+{
+ printf("Usage: %s\n", prog);
+ printf(" -c Use color\n");
+ printf(" -h Display this help message\n");
+ printf(" -v L Verbosity level: %d=QUIET %d=CRITICAL %d=INFO\n",
+ VQUIET, VCRITICAL, VINFO);
+}
+
+void test_count_overflow(void)
+{
+ futex_t f = FUTEX_INITIALIZER;
+ struct futex_wait_block fwb[MAX_COUNT+1];
+ int res, i;
+
+ ksft_print_msg("%s: Test a too big number of futexes\n", progname);
+
+ for (i = 0; i < MAX_COUNT+1; i++) {
+ fwb[i].uaddr = &f;
+ fwb[i].val = f;
+ fwb[i].bitset = 0;
+ }
+
+ res = futex_wait_multiple(fwb, MAX_COUNT+1, NULL, FUTEX_PRIVATE_FLAG);
+
+#ifdef __ILP32__
+ if (res != -1 || errno != ENOSYS) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
+ } else {
+ ksft_test_result_skip("futex_wait_multiple not supported at x32\n");
+ }
+#else
+ if (res != -1 || errno != EINVAL) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
+ } else {
+ ksft_test_result_pass("futex_wait_multiple count overflow succeed\n");
+ }
+
+#endif /* __ILP32__ */
+}
+
+void *waiterfn(void *arg)
+{
+ int res;
+
+ res = futex_wait_multiple(fwb, MAX_COUNT, NULL, FUTEX_PRIVATE_FLAG);
+
+#ifdef __ILP32__
+ if (res != -1 || errno != ENOSYS) {
+ ksft_test_result_fail("futex_wait_multiple returned %d\n",
+ res < 0 ? errno : res);
+ ret = RET_FAIL;
+ } else {
+ ksft_test_result_skip("futex_wait_multiple not supported at x32\n");
+ }
+#else
+ if (res < 0)
+ ksft_print_msg("waiter failed %d\n", res);
+
+ info("futex_wait_multiple: Got hint futex %d was freed\n", res);
+#endif /* __ILP32__ */
+
+ return NULL;
+}
+
+void test_fwb_wakeup(void)
+{
+ int res, i;
+ pthread_t waiter;
+
+ ksft_print_msg("%s: Test wake up in a list of futex\n", progname);
+
+ for (i = 0; i < MAX_COUNT; i++) {
+ fwb[i].uaddr = &f[i];
+ fwb[i].val = f[i];
+ fwb[i].bitset = 0xffffffff;
+ }
+
+ res = pthread_create(&waiter, NULL, waiterfn, NULL);
+ if (res) {
+ ksft_test_result_fail("Creating waiting thread failed");
+ ksft_exit_fail();
+ }
+
+ usleep(WAKE_WAIT_US);
+ res = futex_wake(&(f[MAX_COUNT-1]), 1, FUTEX_PRIVATE_FLAG);
+ if (res != 1) {
+ ksft_test_result_fail("Failed to wake thread res=%d\n", res);
+ ksft_exit_fail();
+ }
+
+ pthread_join(waiter, NULL);
+ ksft_test_result_pass("%s succeed\n", __func__);
+}
+
+int main(int argc, char *argv[])
+{
+ int c;
+
+ while ((c = getopt(argc, argv, "cht:v:")) != -1) {
+ switch (c) {
+ case 'c':
+ log_color(1);
+ break;
+ case 'h':
+ usage(basename(argv[0]));
+ exit(0);
+ case 'v':
+ log_verbosity(atoi(optarg));
+ break;
+ default:
+ usage(basename(argv[0]));
+ exit(1);
+ }
+ }
+
+ progname = basename(argv[0]);
+
+ ksft_print_header();
+ ksft_set_plan(2);
+
+ test_count_overflow();
+
+#ifdef __ILP32__
+ // if it's a 32x binary, there's no futex to wakeup
+ ksft_test_result_skip("futex_wait_multiple not supported at x32\n");
+#else
+ test_fwb_wakeup();
+#endif /* __ILP32__ */
+
+ ksft_print_cnts();
+ return ret;
+}
diff --git a/tools/testing/selftests/futex/functional/run.sh b/tools/testing/selftests/futex/functional/run.sh
index 1acb6ace1680..a8be94f28ff7 100755
--- a/tools/testing/selftests/futex/functional/run.sh
+++ b/tools/testing/selftests/futex/functional/run.sh
@@ -73,3 +73,6 @@ echo
echo
./futex_wait_uninitialized_heap $COLOR
./futex_wait_private_mapped_file $COLOR
+
+echo
+./futex_wait_multiple $COLOR
--
2.25.0