From: Peter Oskolkov <[email protected]>
This is an RFC!
As Paul Turner presented at LPC in 2013 ...
- pdf: http://pdxplumbers.osuosl.org/2013/ocw//system/presentations/1653/original/LPC%20-%20User%20Threading.pdf
- video: https://www.youtube.com/watch?v=KXuZi9aeGTw
... Google has developed an M:N userspace threading subsystem backed
by Google-private SwitchTo Linux Kernel API (page 17 in the pdf referenced
above). This subsystem provides latency-sensitive services at Google with
fine-grained user-space control/scheduling over what is running when,
and this subsystem is used widely internally (called schedulers or fibers).
This RFC patchset is the first step to open-source this work. As explained
in the linked pdf and video, SwitchTo API has three core operations: wait,
resume, and swap (=switch). So this patchset adds a FUTEX_SWAP operation
that, in addition to FUTEX_WAIT and FUTEX_WAKE, will provide a foundation
on top of which user-space threading libraries can be built.
Another common use case for FUTEX_SWAP is message passing a-la RPC
between tasks: task/thread T1 prepares a message,
wakes T2 to work on it, and waits for the results; when T2 is done, it
wakes T1 and waits for more work to arrive. Currently the simplest
way to implement this is
a. T1: futex-wake T2, futex-wait
b. T2: wakes, does what it has been woken to do
c. T2: futex-wake T1, futex-wait
With FUTEX_SWAP, steps a and c above can be reduced to one futex operation
that runs 5-10 times faster.
Patches in this patchset:
Patch 1: introduce FUTEX_SWAP futex operation that,
internally, does wake + wait. The purpose of this patch is
to work out the API.
Patch 2: a first rough attempt to make FUTEX_SWAP faster than
what wake + wait can do.
Patch 3: a selftest that can also be used to benchmark FUTEX_SWAP vs
FUTEX_WAKE + FUTEX_WAIT.
v2: fix undefined symbol error ifndef CONFIG_SMP.
v3: rebased onto the latest tip/locking/core.
Peter Oskolkov (3):
futex: introduce FUTEX_SWAP operation
futex/sched: add wake_up_process_prefer_current_cpu, use in FUTEX_SWAP
selftests/futex: add futex_swap selftest
include/linux/sched.h | 1 +
include/uapi/linux/futex.h | 2 +
kernel/futex.c | 96 ++++++--
kernel/sched/core.c | 5 +
kernel/sched/fair.c | 3 +
kernel/sched/sched.h | 1 +
.../selftests/futex/functional/.gitignore | 1 +
.../selftests/futex/functional/Makefile | 1 +
.../selftests/futex/functional/futex_swap.c | 209 ++++++++++++++++++
.../selftests/futex/include/futextest.h | 19 ++
10 files changed, 322 insertions(+), 16 deletions(-)
create mode 100644 tools/testing/selftests/futex/functional/futex_swap.c
--
2.25.1
From: Peter Oskolkov <[email protected]>
This is the final RFC patch in FUTEX_SWAP patchset. It
adds a test/benchmark to validate behavior and
compare performance of a new FUTEX_SWAP futex operation.
Detailed API design and behavior considerations are provided
in the commit messages of the previous two patches.
Signed-off-by: Peter Oskolkov <[email protected]>
---
.../selftests/futex/functional/.gitignore | 1 +
.../selftests/futex/functional/Makefile | 1 +
.../selftests/futex/functional/futex_swap.c | 209 ++++++++++++++++++
.../selftests/futex/include/futextest.h | 19 ++
4 files changed, 230 insertions(+)
create mode 100644 tools/testing/selftests/futex/functional/futex_swap.c
diff --git a/tools/testing/selftests/futex/functional/.gitignore b/tools/testing/selftests/futex/functional/.gitignore
index 0efcd494daab..d661ef0946cc 100644
--- a/tools/testing/selftests/futex/functional/.gitignore
+++ b/tools/testing/selftests/futex/functional/.gitignore
@@ -2,6 +2,7 @@
futex_requeue_pi
futex_requeue_pi_mismatched_ops
futex_requeue_pi_signal_restart
+futex_swap
futex_wait_private_mapped_file
futex_wait_timeout
futex_wait_uninitialized_heap
diff --git a/tools/testing/selftests/futex/functional/Makefile b/tools/testing/selftests/futex/functional/Makefile
index 23207829ec75..6992fac38b15 100644
--- a/tools/testing/selftests/futex/functional/Makefile
+++ b/tools/testing/selftests/futex/functional/Makefile
@@ -13,6 +13,7 @@ TEST_GEN_FILES := \
futex_requeue_pi \
futex_requeue_pi_signal_restart \
futex_requeue_pi_mismatched_ops \
+ futex_swap \
futex_wait_uninitialized_heap \
futex_wait_private_mapped_file
diff --git a/tools/testing/selftests/futex/functional/futex_swap.c b/tools/testing/selftests/futex/functional/futex_swap.c
new file mode 100644
index 000000000000..9034d04372d3
--- /dev/null
+++ b/tools/testing/selftests/futex/functional/futex_swap.c
@@ -0,0 +1,209 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#include <errno.h>
+#include <getopt.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include "atomic.h"
+#include "futextest.h"
+
+/* The futex the main thread waits on. */
+futex_t futex_main = FUTEX_INITIALIZER;
+/* The futex the other thread wats on. */
+futex_t futex_other = FUTEX_INITIALIZER;
+
+/* The number of iterations to run (>1 => run benchmarks. */
+static int cfg_iterations = 1;
+
+/* If != 0, print diagnostic messages. */
+static int cfg_verbose;
+
+/* If == 0, do not use validation_counter. Useful for benchmarking. */
+static int cfg_validate = 1;
+
+/* How to swap threads. */
+#define SWAP_WAKE_WAIT 1
+#define SWAP_SWAP 2
+
+/* Futex values. */
+#define FUTEX_WAITING 0
+#define FUTEX_WAKEUP 1
+
+/* An atomic counter used to validate proper swapping. */
+static atomic_t validation_counter;
+
+void futex_swap_op(int mode, futex_t *futex_this, futex_t *futex_that)
+{
+ int ret;
+
+ switch (mode) {
+ case SWAP_WAKE_WAIT:
+ futex_set(futex_this, FUTEX_WAITING);
+ futex_set(futex_that, FUTEX_WAKEUP);
+ futex_wake(futex_that, 1, FUTEX_PRIVATE_FLAG);
+ futex_wait(futex_this, FUTEX_WAITING, NULL, FUTEX_PRIVATE_FLAG);
+ if (*futex_this != FUTEX_WAKEUP) {
+ fprintf(stderr, "unexpected futex_this value on wakeup\n");
+ exit(1);
+ }
+ break;
+
+ case SWAP_SWAP:
+ futex_set(futex_this, FUTEX_WAITING);
+ futex_set(futex_that, FUTEX_WAKEUP);
+ ret = futex_swap(futex_this, FUTEX_WAITING, NULL,
+ futex_that, FUTEX_PRIVATE_FLAG);
+ if (ret < 0 && errno == ENOSYS) {
+ /* futex_swap not implemented */
+ perror("futex_swap");
+ exit(1);
+ }
+ if (*futex_this != FUTEX_WAKEUP) {
+ fprintf(stderr, "unexpected futex_this value on wakeup\n");
+ exit(1);
+ }
+ break;
+
+ default:
+ fprintf(stderr, "unknown mode in %s\n", __func__);
+ exit(1);
+ }
+}
+
+void *other_thread(void *arg)
+{
+ int mode = *((int *)arg);
+ int counter;
+
+ if (cfg_verbose)
+ printf("%s started\n", __func__);
+
+ futex_wait(&futex_other, 0, NULL, FUTEX_PRIVATE_FLAG);
+
+ for (counter = 0; counter < cfg_iterations; ++counter) {
+ if (cfg_validate) {
+ int prev = 2 * counter + 1;
+
+ if (prev != atomic_cmpxchg(&validation_counter, prev,
+ prev + 1)) {
+ fprintf(stderr, "swap validation failed\n");
+ exit(1);
+ }
+ }
+ futex_swap_op(mode, &futex_other, &futex_main);
+ }
+
+ if (cfg_verbose)
+ printf("%s finished: %d iteration(s)\n", __func__, counter);
+
+ return NULL;
+}
+
+void run_test(int mode)
+{
+ struct timespec start, stop;
+ int ret, counter;
+ pthread_t thread;
+ uint64_t duration;
+
+ futex_set(&futex_other, FUTEX_WAITING);
+ atomic_set(&validation_counter, 0);
+ ret = pthread_create(&thread, NULL, &other_thread, &mode);
+ if (ret) {
+ perror("pthread_create");
+ exit(1);
+ }
+
+ ret = clock_gettime(CLOCK_MONOTONIC, &start);
+ if (ret) {
+ perror("clock_gettime");
+ exit(1);
+ }
+
+ for (counter = 0; counter < cfg_iterations; ++counter) {
+ if (cfg_validate) {
+ int prev = 2 * counter;
+
+ if (prev != atomic_cmpxchg(&validation_counter, prev,
+ prev + 1)) {
+ fprintf(stderr, "swap validation failed\n");
+ exit(1);
+ }
+ }
+ futex_swap_op(mode, &futex_main, &futex_other);
+ }
+ if (cfg_validate && validation_counter.val != 2 * cfg_iterations) {
+ fprintf(stderr, "final swap validation failed\n");
+ exit(1);
+ }
+
+ ret = clock_gettime(CLOCK_MONOTONIC, &stop);
+ if (ret) {
+ perror("clock_gettime");
+ exit(1);
+ }
+
+ duration = (stop.tv_sec - start.tv_sec) * 1000000000LL +
+ stop.tv_nsec - start.tv_nsec;
+ if (cfg_verbose || cfg_iterations > 1) {
+ printf("completed %d swap and back iterations in %lu ns: %lu ns per swap\n",
+ cfg_iterations, duration,
+ duration / (cfg_iterations * 2));
+ }
+
+ /* The remote thread is blocked; send it the final wake. */
+ futex_set(&futex_other, FUTEX_WAKEUP);
+ futex_wake(&futex_other, 1, FUTEX_PRIVATE_FLAG);
+ if (pthread_join(thread, NULL)) {
+ perror("pthread_join");
+ exit(1);
+ }
+}
+
+void usage(char *prog)
+{
+ printf("Usage: %s\n", prog);
+ printf(" -h Display this help message\n");
+ printf(" -i N Use N iterations to benchmark\n");
+ printf(" -n Do not validate swapping correctness\n");
+ printf(" -v Print diagnostic messages\n");
+}
+
+int main(int argc, char *argv[])
+{
+ int c;
+
+ while ((c = getopt(argc, argv, "hi:nv")) != -1) {
+ switch (c) {
+ case 'h':
+ usage(basename(argv[0]));
+ exit(0);
+ case 'i':
+ cfg_iterations = atoi(optarg);
+ break;
+ case 'n':
+ cfg_validate = 0;
+ break;
+ case 'v':
+ cfg_verbose = 1;
+ break;
+ default:
+ usage(basename(argv[0]));
+ exit(1);
+ }
+ }
+
+ printf("\n\n------- running SWAP_WAKE_WAIT -----------\n\n");
+ run_test(SWAP_WAKE_WAIT);
+ printf("PASS\n");
+
+ printf("\n\n------- running SWAP_SWAP -----------\n\n");
+ run_test(SWAP_SWAP);
+ printf("PASS\n");
+
+ return 0;
+}
diff --git a/tools/testing/selftests/futex/include/futextest.h b/tools/testing/selftests/futex/include/futextest.h
index ddbcfc9b7bac..4d6a0a18445a 100644
--- a/tools/testing/selftests/futex/include/futextest.h
+++ b/tools/testing/selftests/futex/include/futextest.h
@@ -38,6 +38,9 @@ typedef volatile u_int32_t futex_t;
#ifndef FUTEX_CMP_REQUEUE_PI
#define FUTEX_CMP_REQUEUE_PI 12
#endif
+#ifndef FUTEX_SWAP
+#define FUTEX_SWAP 13
+#endif
#ifndef FUTEX_WAIT_REQUEUE_PI_PRIVATE
#define FUTEX_WAIT_REQUEUE_PI_PRIVATE (FUTEX_WAIT_REQUEUE_PI | \
FUTEX_PRIVATE_FLAG)
@@ -46,6 +49,9 @@ typedef volatile u_int32_t futex_t;
#define FUTEX_CMP_REQUEUE_PI_PRIVATE (FUTEX_CMP_REQUEUE_PI | \
FUTEX_PRIVATE_FLAG)
#endif
+#ifndef FUTEX_SWAP_PRIVATE
+#define FUTEX_SWAP_PRIVATE (FUTEX_WAIT_WAKE | FUTEX_PRIVATE_FLAG)
+#endif
/**
* futex() - SYS_futex syscall wrapper
@@ -204,6 +210,19 @@ futex_cmp_requeue_pi(futex_t *uaddr, futex_t val, futex_t *uaddr2, int nr_wake,
val, opflags);
}
+/**
+ * futex_swap() - block on uaddr and wake one task blocked on uaddr2.
+ * @uaddr: futex to block the current task on
+ * @timeout: relative timeout for the current task block
+ * @uaddr2: futex to wake tasks at (can be the same as uaddr)
+ */
+static inline int
+futex_swap(futex_t *uaddr, futex_t val, struct timespec *timeout,
+ futex_t *uaddr2, int opflags)
+{
+ return futex(uaddr, FUTEX_SWAP, val, timeout, uaddr2, 0, opflags);
+}
+
/**
* futex_cmpxchg() - atomic compare and exchange
* @uaddr: The address of the futex to be modified
--
2.25.1
From: Peter Oskolkov <[email protected]>
This is an RFC!
As Paul Turner presented at LPC in 2013 ...
- pdf: http://pdxplumbers.osuosl.org/2013/ocw//system/presentations/1653/original/LPC%20-%20User%20Threading.pdf
- video: https://www.youtube.com/watch?v=KXuZi9aeGTw
... Google has developed an M:N userspace threading subsystem backed
by Google-private SwitchTo Linux Kernel API (page 17 in the pdf referenced
above). This subsystem provides latency-sensitive services at Google with
fine-grained user-space control/scheduling over what is running when,
and this subsystem is used widely internally (called schedulers or fibers).
This RFC patchset is the first step to open-source this work. As explained
in the linked pdf and video, SwitchTo API has three core operations: wait,
resume, and swap (=switch). So this patchset adds a FUTEX_SWAP operation
that, in addition to FUTEX_WAIT and FUTEX_WAKE, will provide a foundation
on top of which user-space threading libraries can be built.
Another common use case for FUTEX_SWAP is message passing a-la RPC
between tasks: task/thread T1 prepares a message,
wakes T2 to work on it, and waits for the results; when T2 is done, it
wakes T1 and waits for more work to arrive. Currently the simplest
way to implement this is
a. T1: futex-wake T2, futex-wait
b. T2: wakes, does what it has been woken to do
c. T2: futex-wake T1, futex-wait
With FUTEX_SWAP, steps a and c above can be reduced to one futex operation
that runs 5-10 times faster.
Patches in this patchset:
Patch 1: (this patch) introduce FUTEX_SWAP futex operation that,
internally, does wake + wait. The purpose of this patch is
to work out the API.
Patch 2: a first rough attempt to make FUTEX_SWAP faster than
what wake + wait can do.
Patch 3: a selftest that can also be used to benchmark FUTEX_SWAP vs
FUTEX_WAKE + FUTEX_WAIT.
Tested: see patch 3 in this patchset.
Signed-off-by: Peter Oskolkov <[email protected]>
---
include/uapi/linux/futex.h | 2 +
kernel/futex.c | 97 +++++++++++++++++++++++++++++++-------
2 files changed, 83 insertions(+), 16 deletions(-)
diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h
index a89eb0accd5e..c1d151d97dea 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_SWAP 13
#define FUTEX_PRIVATE_FLAG 128
#define FUTEX_CLOCK_REALTIME 256
@@ -40,6 +41,7 @@
FUTEX_PRIVATE_FLAG)
#define FUTEX_CMP_REQUEUE_PI_PRIVATE (FUTEX_CMP_REQUEUE_PI | \
FUTEX_PRIVATE_FLAG)
+#define FUTEX_SWAP_PRIVATE (FUTEX_SWAP | FUTEX_PRIVATE_FLAG)
/*
* Support for robust futexes: the kernel cleans up held futexes at
diff --git a/kernel/futex.c b/kernel/futex.c
index e646661f6282..670d6d113561 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1595,16 +1595,16 @@ double_unlock_hb(struct futex_hash_bucket *hb1, struct futex_hash_bucket *hb2)
}
/*
- * Wake up waiters matching bitset queued on this futex (uaddr).
+ * Prepare wake queue matching bitset queued on this futex (uaddr).
*/
static int
-futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
+prepare_wake_q(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset,
+ struct wake_q_head *wake_q)
{
struct futex_hash_bucket *hb;
struct futex_q *this, *next;
union futex_key key = FUTEX_KEY_INIT;
int ret;
- DEFINE_WAKE_Q(wake_q);
if (!bitset)
return -EINVAL;
@@ -1632,20 +1632,34 @@ futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
if (!(this->bitset & bitset))
continue;
- mark_wake_futex(&wake_q, this);
+ mark_wake_futex(wake_q, this);
if (++ret >= nr_wake)
break;
}
}
spin_unlock(&hb->lock);
- wake_up_q(&wake_q);
out_put_key:
put_futex_key(&key);
out:
return ret;
}
+/*
+ * Wake up waiters matching bitset queued on this futex (uaddr).
+ */
+static int
+futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
+{
+ int ret;
+ DEFINE_WAKE_Q(wake_q);
+
+ ret = prepare_wake_q(uaddr, flags, nr_wake, bitset, &wake_q);
+ wake_up_q(&wake_q);
+
+ return ret;
+}
+
static int futex_atomic_op_inuser(unsigned int encoded_op, u32 __user *uaddr)
{
unsigned int op = (encoded_op & 0x70000000) >> 28;
@@ -2603,9 +2617,12 @@ static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
* @hb: the futex hash bucket, must be locked by the caller
* @q: the futex_q to queue up on
* @timeout: the prepared hrtimer_sleeper, or null for no timeout
+ * @next: if present, wake next and hint to the scheduler that we'd
+ * prefer to execute it locally.
*/
static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
- struct hrtimer_sleeper *timeout)
+ struct hrtimer_sleeper *timeout,
+ struct task_struct *next)
{
/*
* The task state is guaranteed to be set before another task can
@@ -2630,10 +2647,27 @@ static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
* flagged for rescheduling. Only call schedule if there
* is no timeout, or if it has yet to expire.
*/
- if (!timeout || timeout->task)
+ if (!timeout || timeout->task) {
+ if (next) {
+ /*
+ * wake_up_process() below will be replaced
+ * in the next patch with
+ * wake_up_process_prefer_current_cpu().
+ */
+ wake_up_process(next);
+ put_task_struct(next);
+ next = NULL;
+ }
freezable_schedule();
+ }
}
__set_current_state(TASK_RUNNING);
+
+ if (next) {
+ /* Maybe call wake_up_process_prefer_current_cpu()? */
+ wake_up_process(next);
+ put_task_struct(next);
+ }
}
/**
@@ -2713,7 +2747,7 @@ static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
}
static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
- ktime_t *abs_time, u32 bitset)
+ ktime_t *abs_time, u32 bitset, struct task_struct *next)
{
struct hrtimer_sleeper timeout, *to;
struct restart_block *restart;
@@ -2737,7 +2771,8 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
goto out;
/* queue_me and wait for wakeup, timeout, or a signal. */
- futex_wait_queue_me(hb, &q, to);
+ futex_wait_queue_me(hb, &q, to, next);
+ next = NULL;
/* If we were woken (and unqueued), we succeeded, whatever. */
ret = 0;
@@ -2770,6 +2805,10 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
ret = -ERESTART_RESTARTBLOCK;
out:
+ if (next) {
+ wake_up_process(next);
+ put_task_struct(next);
+ }
if (to) {
hrtimer_cancel(&to->timer);
destroy_hrtimer_on_stack(&to->timer);
@@ -2777,7 +2816,6 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
return ret;
}
-
static long futex_wait_restart(struct restart_block *restart)
{
u32 __user *uaddr = restart->futex.uaddr;
@@ -2789,10 +2827,35 @@ static long futex_wait_restart(struct restart_block *restart)
}
restart->fn = do_no_restart_syscall;
- return (long)futex_wait(uaddr, restart->futex.flags,
- restart->futex.val, tp, restart->futex.bitset);
+ return (long)futex_wait(uaddr, restart->futex.flags, restart->futex.val,
+ tp, restart->futex.bitset, NULL);
}
+static int futex_swap(u32 __user *uaddr, unsigned int flags, u32 val,
+ ktime_t *abs_time, u32 __user *uaddr2)
+{
+ u32 bitset = FUTEX_BITSET_MATCH_ANY;
+ struct task_struct *next = NULL;
+ DEFINE_WAKE_Q(wake_q);
+ int ret;
+
+ ret = prepare_wake_q(uaddr2, flags, 1, bitset, &wake_q);
+ if (!wake_q_empty(&wake_q)) {
+ /* Pull the first wakee out of the queue to swap into. */
+ next = container_of(wake_q.first, struct task_struct, wake_q);
+ wake_q.first = wake_q.first->next;
+ next->wake_q.next = NULL;
+ /*
+ * Note that wake_up_q does not touch wake_q.last, so we
+ * do not bother with it here.
+ */
+ wake_up_q(&wake_q);
+ }
+ if (ret < 0)
+ return ret;
+
+ return futex_wait(uaddr, flags, val, abs_time, bitset, next);
+}
/*
* Userspace tried a 0 -> TID atomic transition of the futex value
@@ -3278,7 +3341,7 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
}
/* Queue the futex_q, drop the hb lock, wait for wakeup. */
- futex_wait_queue_me(hb, &q, to);
+ futex_wait_queue_me(hb, &q, to, NULL);
spin_lock(&hb->lock);
ret = handle_early_requeue_pi_wakeup(hb, &q, &key2, to);
@@ -3808,7 +3871,7 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
val3 = FUTEX_BITSET_MATCH_ANY;
/* fall through */
case FUTEX_WAIT_BITSET:
- return futex_wait(uaddr, flags, val, timeout, val3);
+ return futex_wait(uaddr, flags, val, timeout, val3, NULL);
case FUTEX_WAKE:
val3 = FUTEX_BITSET_MATCH_ANY;
/* fall through */
@@ -3832,6 +3895,8 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
uaddr2);
case FUTEX_CMP_REQUEUE_PI:
return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
+ case FUTEX_SWAP:
+ return futex_swap(uaddr, flags, val, timeout, uaddr2);
}
return -ENOSYS;
}
@@ -3848,7 +3913,7 @@ 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_SWAP)) {
if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
return -EFAULT;
if (get_timespec64(&ts, utime))
@@ -3857,7 +3922,7 @@ SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
return -EINVAL;
t = timespec64_to_ktime(ts);
- if (cmd == FUTEX_WAIT)
+ if (cmd == FUTEX_WAIT || cmd == FUTEX_SWAP)
t = ktime_add_safe(ktime_get(), t);
tp = &t;
}
--
2.25.1
Hi Thomas, Ingo!
Do you have any comments/suggestions/objections here? FUTEX_SWAP seems
to be quite useful for fast task context switching, and several teams
at Google would like to see this capability upstreamed.
Thanks,
Peter
On Wed, Jun 24, 2020 at 11:53 AM Peter Oskolkov <[email protected]> wrote:
>
> From: Peter Oskolkov <[email protected]>
>
> This is an RFC!
>
> As Paul Turner presented at LPC in 2013 ...
> - pdf: http://pdxplumbers.osuosl.org/2013/ocw//system/presentations/1653/original/LPC%20-%20User%20Threading.pdf
> - video: https://www.youtube.com/watch?v=KXuZi9aeGTw
>
> ... Google has developed an M:N userspace threading subsystem backed
> by Google-private SwitchTo Linux Kernel API (page 17 in the pdf referenced
> above). This subsystem provides latency-sensitive services at Google with
> fine-grained user-space control/scheduling over what is running when,
> and this subsystem is used widely internally (called schedulers or fibers).
>
> This RFC patchset is the first step to open-source this work. As explained
> in the linked pdf and video, SwitchTo API has three core operations: wait,
> resume, and swap (=switch). So this patchset adds a FUTEX_SWAP operation
> that, in addition to FUTEX_WAIT and FUTEX_WAKE, will provide a foundation
> on top of which user-space threading libraries can be built.
>
> Another common use case for FUTEX_SWAP is message passing a-la RPC
> between tasks: task/thread T1 prepares a message,
> wakes T2 to work on it, and waits for the results; when T2 is done, it
> wakes T1 and waits for more work to arrive. Currently the simplest
> way to implement this is
>
> a. T1: futex-wake T2, futex-wait
> b. T2: wakes, does what it has been woken to do
> c. T2: futex-wake T1, futex-wait
>
> With FUTEX_SWAP, steps a and c above can be reduced to one futex operation
> that runs 5-10 times faster.
>
> Patches in this patchset:
>
> Patch 1: introduce FUTEX_SWAP futex operation that,
> internally, does wake + wait. The purpose of this patch is
> to work out the API.
> Patch 2: a first rough attempt to make FUTEX_SWAP faster than
> what wake + wait can do.
> Patch 3: a selftest that can also be used to benchmark FUTEX_SWAP vs
> FUTEX_WAKE + FUTEX_WAIT.
>
> v2: fix undefined symbol error ifndef CONFIG_SMP.
> v3: rebased onto the latest tip/locking/core.
>
> Peter Oskolkov (3):
> futex: introduce FUTEX_SWAP operation
> futex/sched: add wake_up_process_prefer_current_cpu, use in FUTEX_SWAP
> selftests/futex: add futex_swap selftest
>
> include/linux/sched.h | 1 +
> include/uapi/linux/futex.h | 2 +
> kernel/futex.c | 96 ++++++--
> kernel/sched/core.c | 5 +
> kernel/sched/fair.c | 3 +
> kernel/sched/sched.h | 1 +
> .../selftests/futex/functional/.gitignore | 1 +
> .../selftests/futex/functional/Makefile | 1 +
> .../selftests/futex/functional/futex_swap.c | 209 ++++++++++++++++++
> .../selftests/futex/include/futextest.h | 19 ++
> 10 files changed, 322 insertions(+), 16 deletions(-)
> create mode 100644 tools/testing/selftests/futex/functional/futex_swap.c
>
> --
> 2.25.1
>
Hi Jim, thank you for your interest!
While FUTEX_SWAP seems to be a nonstarter, there is a discussion
off-list on how to approach the larger problem of userspace
scheduling. A full userspace scheduling patchset is likely to take
some time to shape out, but the "core" patches of wait/wake/swap are
more or less ready, so I'll probably post an early RFC version here in
the next week or two.
CC-ing the maintainers.
Thanks,
Peter
On Wed, Mar 17, 2021 at 10:59 AM Jim Newsome <[email protected]> wrote:
>
> I'm not well versed in this part of the kernel (ok, any part, really),
> but I wanted to chime in from a user perspective that I'm very
> interested in this functionality.
>
> We (Rob + Ryan + I, cc'd) are currently developing the second generation
> of the Shadow simulator <https://shadow.github.io/>, which is used by
> various researchers and the Tor Project. In this new architecture,
> simulated network-application processes (such as tor, browsers, and web
> servers) are each run as a native OS process, started by forking and
> exec'ing its unmodified binary. We are interested in supporting large
> simulations (e.g. 50k+ processes), and expect them to take on the order
> of hours or even days to execute, so scalability and performance matters.
>
> We've prototyped two mechanisms for controlling these simulated
> processes, and a third hybrid mechanism that combines the two. I've
> mentioned one of these (ptrace) in another thread ("do_wait: make
> PIDTYPE_PID case O(1) instead of O(n)"). The other mechanism is to use
> an LD_PRELOAD'd shim that implements the libc interface, and
> communicates with Shadow via a syscall-like API over IPC.
>
> So far the most performant version we've tried of this IPC is with a bit
> of shared memory and a pair of semaphores. It looks much like the
> example in Peter's proposal:
>
> > a. T1: futex-wake T2, futex-wait
> > b. T2: wakes, does what it has been woken to do
> > c. T2: futex-wake T1, futex-wait
>
> We've been able to get the switching costs down using CPU pinning and
> SCHED_FIFO. Each physical CPU spends most of its time swapping back and
> forth between a Shadow worker thread and an emulated process. Even so,
> the new architecture is so far slower than the first generation of
> Shadow, which multiplexes the simulated processes into its own handful
> of OS processes (but is complex and fragile).
>
> > With FUTEX_SWAP, steps a and c above can be reduced to one futex
> > operation that runs 5-10 times faster.
>
> IIUC the proposed primitives could let us further improve performance,
> and perhaps drop some of the complexity of attempting to control the
> scheduler via pinning and SCHED_FIFO.
I'm not well versed in this part of the kernel (ok, any part, really),
but I wanted to chime in from a user perspective that I'm very
interested in this functionality.
We (Rob + Ryan + I, cc'd) are currently developing the second generation
of the Shadow simulator <https://shadow.github.io/>, which is used by
various researchers and the Tor Project. In this new architecture,
simulated network-application processes (such as tor, browsers, and web
servers) are each run as a native OS process, started by forking and
exec'ing its unmodified binary. We are interested in supporting large
simulations (e.g. 50k+ processes), and expect them to take on the order
of hours or even days to execute, so scalability and performance matters.
We've prototyped two mechanisms for controlling these simulated
processes, and a third hybrid mechanism that combines the two. I've
mentioned one of these (ptrace) in another thread ("do_wait: make
PIDTYPE_PID case O(1) instead of O(n)"). The other mechanism is to use
an LD_PRELOAD'd shim that implements the libc interface, and
communicates with Shadow via a syscall-like API over IPC.
So far the most performant version we've tried of this IPC is with a bit
of shared memory and a pair of semaphores. It looks much like the
example in Peter's proposal:
> a. T1: futex-wake T2, futex-wait
> b. T2: wakes, does what it has been woken to do
> c. T2: futex-wake T1, futex-wait
We've been able to get the switching costs down using CPU pinning and
SCHED_FIFO. Each physical CPU spends most of its time swapping back and
forth between a Shadow worker thread and an emulated process. Even so,
the new architecture is so far slower than the first generation of
Shadow, which multiplexes the simulated processes into its own handful
of OS processes (but is complex and fragile).
> With FUTEX_SWAP, steps a and c above can be reduced to one futex
> operation that runs 5-10 times faster.
IIUC the proposed primitives could let us further improve performance,
and perhaps drop some of the complexity of attempting to control the
scheduler via pinning and SCHED_FIFO.