Skip to contentSkip to conversation

Add io_uring support for futex wait/wake

RFC PATCH In review Jens Axboe 3 participants 16 messages Jun 9, 2023 – Jun 23, 2023

Subsystems (2)
lore
Share & tools
lore

Jens Axboe

author maintainer
#0 lore raw

cover Add io_uring support for futex wait/wake

Hi,

Sending this just to the io_uring list for now so we can iron out details, questions, concerns, etc before going a bit broader to get the futex parts reviewed. Those are pretty straight forward though, and try not to get too entangled into futex internals.

Anyway, this adds support for IORING_OP_FUTEX_{WAIT,WAKE}. The WAKE part is pretty trivial, as we can just call into the wake side of things. For wait, obviously we cannot, as we don't want to block on waiting on a futex. When futex currently does a wait, it queues up the futex_q in question and then does a sync wait/schedule on that. The futex handler futex_wake_mark() is responsible for waking the task that is synchronousely sleeping on that futex_q. This default handler is hardwired, and we simply add a wake handler in futex_q for this intead and change the hardwired futex_q->task to be a generic data piece for the handler.

With that, we can queue up a futex_q and get a callback when it would have woken. With that, we can sanely implement async WAIT support without blocking.

Notable omissions in this code so far:

- We don't support timeouts with futex wait. We could definitely add this support. Outside of some complications with racing with wake (and cancelation), it is certainly doable. The main question here is we need it? And if we do, can we get by with just using linked timeouts for this? That's the io_uring idiomatic way of achieving this goal. That said, I may just go ahead and add it if I can solve the races in a clean fashion. Because at that point, seems the right thing to do.

- No PI support. This can certainly get added later.

Code can also be found here:

git://git.kernel.dk/linux io_uring-futex

or on cgit:

https://git.kernel.dk/cgit/linux/log/?h=io_uring-futex

Very simple sample code below showing how to do a wait and wake, Obviously not that exciting, just a brief demo.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <linux/futex.h>
#include <liburing.h>

#define IORING_OP_FUTEX_WAIT (IORING_OP_SENDMSG_ZC + 1)
#define IORING_OP_FUTEX_WAKE (IORING_OP_FUTEX_WAIT + 1)

static void io_uring_prep_futex_wait(struct io_uring_sqe *sqe, void *futex,
int val)

{
	memset(sqe, 0, sizeof(*sqe));
	sqe->opcode = IORING_OP_FUTEX_WAIT;
	sqe->fd = FUTEX_WAIT;
	sqe->addr = (unsigned long) futex;
	sqe->len = val;
	sqe->file_index = FUTEX_BITSET_MATCH_ANY;
}

static void io_uring_prep_futex_wake(struct io_uring_sqe *sqe, void *futex,
int val)

{
	memset(sqe, 0, sizeof(*sqe));
	sqe->opcode = IORING_OP_FUTEX_WAKE;
	sqe->fd = FUTEX_WAIT;
	sqe->addr = (unsigned long) futex;
	sqe->len = val;
	sqe->file_index = FUTEX_BITSET_MATCH_ANY;
}

int main(int argc, char *argv[])

{
	struct io_uring_sqe *sqe;
	struct io_uring_cqe *cqe;
	struct io_uring ring;
	unsigned int *futex;
	int ret, i;

	futex = malloc(sizeof(*futex));
	*futex = 0;

	io_uring_queue_init(8, &ring, 0);

	sqe = io_uring_get_sqe(&ring);
	io_uring_prep_futex_wait(sqe, futex, 0);
	sqe->user_data = 1;
	
	io_uring_submit(&ring);

	*futex = 1;
	sqe = io_uring_get_sqe(&ring);
	io_uring_prep_futex_wake(sqe, futex, 1);
	sqe->user_data = 2;

	io_uring_submit(&ring);

	for (i = 0; i < 2; i++) {
		ret = io_uring_wait_cqe(&ring, &cqe);
		if (ret)
			return 1;

		io_uring_cqe_seen(&ring, cqe);
	}

	return 0;
}
Signature · 1 line
Jens Axboe
author maintainer
#1 lore raw

PATCH 1/6 futex: abstract out futex_op_to_flags() helper

Rather than needing to duplicate this for the io_uring hook of futexes, abstract out a helper.

No functional changes intended in this patch.

---
 kernel/futex/futex.h    | 15 +++++++++++++++
 kernel/futex/syscalls.c | 11 ++---------
 2 files changed, 17 insertions(+), 9 deletions(-)
kernel/futex/futex.h +15 -0
index b5379c0e6d6d..d2949fca37d1 100644
@@ -291,4 +291,19 @@ extern int futex_unlock_pi(u32 __user *uaddr, unsigned int flags);
 
 extern int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int trylock);
 
+static inline bool futex_op_to_flags(int op, int cmd, unsigned int *flags)
+{
+	if (!(op & FUTEX_PRIVATE_FLAG))
+		*flags |= FLAGS_SHARED;
+
+	if (op & FUTEX_CLOCK_REALTIME) {
+		*flags |= FLAGS_CLOCKRT;
+		if (cmd != FUTEX_WAIT_BITSET && cmd != FUTEX_WAIT_REQUEUE_PI &&
+		    cmd != FUTEX_LOCK_PI2)
+			return false;
+	}
+
+	return true;
+}
+
 #endif /* _FUTEX_H */
kernel/futex/syscalls.c +2 -9
index a8074079b09e..75ca8c41cc94 100644
@@ -88,15 +88,8 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 	int cmd = op & FUTEX_CMD_MASK;
 	unsigned int flags = 0;
 
-	if (!(op & FUTEX_PRIVATE_FLAG))
-		flags |= FLAGS_SHARED;
-
-	if (op & FUTEX_CLOCK_REALTIME) {
-		flags |= FLAGS_CLOCKRT;
-		if (cmd != FUTEX_WAIT_BITSET && cmd != FUTEX_WAIT_REQUEUE_PI &&
-		    cmd != FUTEX_LOCK_PI2)
-			return -ENOSYS;
-	}
+	if (!futex_op_to_flags(op, cmd, &flags))
+		return -ENOSYS;
 
 	switch (cmd) {
 	case FUTEX_WAIT:
Signature · 1 line
2.39.2
author maintainer
#2 lore raw

PATCH 2/6 futex: factor out the futex wake handling

In reply to Jens Axboe

In preparation for having another waker that isn't futex_wake_mark(), add a wake handler in futex_q and rename the futex_q->task field to just be wake_data. futex_wake_mark() is defined as the standard wakeup helper.

---
 kernel/futex/core.c     | 2 +-
 kernel/futex/futex.h    | 3 ++-
 kernel/futex/requeue.c  | 7 ++++---
 kernel/futex/waitwake.c | 8 ++++----
 4 files changed, 11 insertions(+), 9 deletions(-)
kernel/futex/core.c +1 -1
index 514e4582b863..6223cce3d876 100644
@@ -556,7 +556,7 @@ void __futex_queue(struct futex_q *q, struct futex_hash_bucket *hb)
 
 	plist_node_init(&q->list, prio);
 	plist_add(&q->list, &hb->chain);
-	q->task = current;
+	q->wake_data = current;
 }
 
 /**
kernel/futex/futex.h +2 -1
index d2949fca37d1..1b7dd5266dd2 100644
@@ -96,7 +96,6 @@ struct futex_pi_state {
 struct futex_q {
 	struct plist_node list;
 
-	struct task_struct *task;
 	spinlock_t *lock_ptr;
 	union futex_key key;
 	struct futex_pi_state *pi_state;
@@ -107,6 +106,8 @@ struct futex_q {
 #ifdef CONFIG_PREEMPT_RT
 	struct rcuwait requeue_wait;
 #endif
+	void (*wake)(struct wake_q_head *wake_q, struct futex_q *);
+	void *wake_data;
 } __randomize_layout;
 
 extern const struct futex_q futex_q_init;
kernel/futex/requeue.c +4 -3
index cba8b1a6a4cc..6aee8408c341 100644
@@ -61,6 +61,7 @@ const struct futex_q futex_q_init = {
 	.key		= FUTEX_KEY_INIT,
 	.bitset		= FUTEX_BITSET_MATCH_ANY,
 	.requeue_state	= ATOMIC_INIT(Q_REQUEUE_PI_NONE),
+	.wake		= futex_wake_mark,
 };
 
 /**
@@ -234,7 +235,7 @@ void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
 
 	/* Signal locked state to the waiter */
 	futex_requeue_pi_complete(q, 1);
-	wake_up_state(q->task, TASK_NORMAL);
+	wake_up_state(q->wake_data, TASK_NORMAL);
 }
 
 /**
@@ -316,7 +317,7 @@ futex_proxy_trylock_atomic(u32 __user *pifutex, struct futex_hash_bucket *hb1,
 	 * the user space lock can be acquired then PI state is attached to
 	 * the new owner (@top_waiter->task) when @set_waiters is true.
 	 */
-	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
+	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->wake_data,
 				   exiting, set_waiters);
 	if (ret == 1) {
 		/*
@@ -626,7 +627,7 @@ int futex_requeue(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
 
 		ret = rt_mutex_start_proxy_lock(&pi_state->pi_mutex,
 						this->rt_waiter,
-						this->task);
+						this->wake_data);
 
 		if (ret == 1) {
 			/*
kernel/futex/waitwake.c +4 -4
index ba01b9408203..5151c83e2db8 100644
@@ -114,7 +114,7 @@
  */
 void futex_wake_mark(struct wake_q_head *wake_q, struct futex_q *q)
 {
-	struct task_struct *p = q->task;
+	struct task_struct *p = q->wake_data;
 
 	if (WARN(q->pi_state || q->rt_waiter, "refusing to wake PI futex\n"))
 		return;
@@ -174,7 +174,7 @@ int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
 			if (!(this->bitset & bitset))
 				continue;
 
-			futex_wake_mark(&wake_q, this);
+			this->wake(&wake_q, this);
 			if (++ret >= nr_wake)
 				break;
 		}
@@ -289,7 +289,7 @@ int futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
 				ret = -EINVAL;
 				goto out_unlock;
 			}
-			futex_wake_mark(&wake_q, this);
+			this->wake(&wake_q, this);
 			if (++ret >= nr_wake)
 				break;
 		}
@@ -303,7 +303,7 @@ int futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
 					ret = -EINVAL;
 					goto out_unlock;
 				}
-				futex_wake_mark(&wake_q, this);
+				this->wake(&wake_q, this);
 				if (++op_ret >= nr_wake2)
 					break;
 			}
Signature · 1 line
2.39.2
author maintainer
#3 lore raw

PATCH 3/6 futex: assign default futex_q->wait_data at insertion time

In reply to Jens Axboe

Rather than do it in the lower level queueing helper, move it to the upper level one. This enables use of that helper with the caller setting the wake handler data prior to calling it, rather than assume that futex_wake_mark() is the handler for this futex_q.

---
 kernel/futex/core.c  | 1 -
 kernel/futex/futex.h | 1 +
 2 files changed, 1 insertion(+), 1 deletion(-)
kernel/futex/core.c +0 -1
index 6223cce3d876..b9d8619c06fc 100644
@@ -556,7 +556,6 @@ void __futex_queue(struct futex_q *q, struct futex_hash_bucket *hb)
 
 	plist_node_init(&q->list, prio);
 	plist_add(&q->list, &hb->chain);
-	q->wake_data = current;
 }
 
 /**
kernel/futex/futex.h +1 -0
index 1b7dd5266dd2..8c12cef83d38 100644
@@ -171,6 +171,7 @@ extern int futex_unqueue(struct futex_q *q);
 static inline void futex_queue(struct futex_q *q, struct futex_hash_bucket *hb)
 	__releases(&hb->lock)
 {
+	q->wake_data = current;
 	__futex_queue(q, hb);
 	spin_unlock(&hb->lock);
 }
Signature · 1 line
2.39.2
author maintainer
#4 lore raw

PATCH 4/6 futex: add futex wait variant that takes a futex_q directly

In reply to Jens Axboe

For async trigger of the wait, we need to be able to pass in a futex_q that is already setup. Add that helper.

---
 kernel/futex/futex.h    |  3 +++
 kernel/futex/waitwake.c | 17 +++++++++++++++++
 2 files changed, 20 insertions(+)
kernel/futex/futex.h +3 -0
index 8c12cef83d38..29bf78a1f475 100644
@@ -156,6 +156,9 @@ extern void __futex_unqueue(struct futex_q *q);
 extern void __futex_queue(struct futex_q *q, struct futex_hash_bucket *hb);
 extern int futex_unqueue(struct futex_q *q);
 
+extern int futex_queue_wait(struct futex_q *q, u32 __user *uaddr,
+			    unsigned int flags, u32 val);
+
 /**
  * futex_queue() - Enqueue the futex_q on the futex_hash_bucket
  * @q:	The futex_q to enqueue
kernel/futex/waitwake.c +17 -0
index 5151c83e2db8..442dafdfa22a 100644
@@ -706,3 +706,20 @@ static long futex_wait_restart(struct restart_block *restart)
 				restart->futex.val, tp, restart->futex.bitset);
 }
 
+int futex_queue_wait(struct futex_q *q, u32 __user *uaddr, unsigned int flags,
+		     u32 val)
+{
+	struct futex_hash_bucket *hb;
+	int ret;
+
+	if (!q->bitset)
+		return -EINVAL;
+
+	ret = futex_wait_setup(uaddr, val, flags, q, &hb);
+	if (ret)
+		return ret;
+
+	__futex_queue(q, hb);
+	spin_unlock(&hb->lock);
+	return 0;
+}
Signature · 1 line
2.39.2
author maintainer
#5 lore raw

PATCH 5/6 io_uring: add support for futex wake and wait

In reply to Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

FUTEX_WAKE is straight forward, as we can always just do those inline. FUTEX_WAIT will queue the futex with an appropriate callback, and that callback will in turn post a CQE when it has triggered.

Cancelations are supported, both from the application point-of-view, but also to be able to cancel pending waits if the ring exits before all events have occurred.

This is just the barebones wait/wake support. Features to be added later:

- We do not support the PI or requeue operations. The immediate use case don't need them, unsure if future support for these would be useful.

- Should we support futex wait with timeout? Not clear if this is necessary, as the usual io_uring linked timeouts could fill this purpose.

- Would be nice to support registered futexes, just like we do buffers. This would avoid mapping in user memory for each operation.

- Probably lots more that I just didn't think of.

---
 include/linux/io_uring_types.h |   2 +
 include/uapi/linux/io_uring.h  |   3 +
 io_uring/Makefile              |   4 +-
 io_uring/cancel.c              |   5 +
 io_uring/cancel.h              |   4 +
 io_uring/futex.c               | 194 +++++++++++++++++++++++++++++++++
 io_uring/futex.h               |  26 +++++
 io_uring/io_uring.c            |   3 +
 io_uring/opdef.c               |  25 ++++-
 9 files changed, 264 insertions(+), 2 deletions(-)
 create mode 100644 io_uring/futex.c
 create mode 100644 io_uring/futex.h
include/linux/io_uring_types.h +2 -0
index f04ce513fadb..d796b578c129 100644
@@ -273,6 +273,8 @@ struct io_ring_ctx {
 	struct io_wq_work_list	locked_free_list;
 	unsigned int		locked_free_nr;
 
+	struct hlist_head	futex_list;
+
 	const struct cred	*sq_creds;	/* cred used for __io_sq_thread() */
 	struct io_sq_data	*sq_data;	/* if using sq thread polling */
 
include/uapi/linux/io_uring.h +3 -0
index f222d263bc55..b1a151ab8150 100644
@@ -65,6 +65,7 @@ struct io_uring_sqe {
 		__u32		xattr_flags;
 		__u32		msg_ring_flags;
 		__u32		uring_cmd_flags;
+		__u32		futex_flags;
 	};
 	__u64	user_data;	/* data to be passed back at completion time */
 	/* pack this to avoid bogus arm OABI complaints */
@@ -235,6 +236,8 @@ enum io_uring_op {
 	IORING_OP_URING_CMD,
 	IORING_OP_SEND_ZC,
 	IORING_OP_SENDMSG_ZC,
+	IORING_OP_FUTEX_WAIT,
+	IORING_OP_FUTEX_WAKE,
 
 	/* this goes last, obviously */
 	IORING_OP_LAST,
io_uring/Makefile +3 -1
index 8cc8e5387a75..2e4779bc550c 100644
@@ -7,5 +7,7 @@ obj-$(CONFIG_IO_URING)		+= io_uring.o xattr.o nop.o fs.o splice.o \
 					openclose.o uring_cmd.o epoll.o \
 					statx.o net.o msg_ring.o timeout.o \
 					sqpoll.o fdinfo.o tctx.o poll.o \
-					cancel.o kbuf.o rsrc.o rw.o opdef.o notif.o
+					cancel.o kbuf.o rsrc.o rw.o opdef.o \
+					notif.o
 obj-$(CONFIG_IO_WQ)		+= io-wq.o
+obj-$(CONFIG_FUTEX)		+= futex.o
io_uring/cancel.c +5 -0
index b4f5dfacc0c3..280fb83145d3 100644
@@ -15,6 +15,7 @@
 #include "tctx.h"
 #include "poll.h"
 #include "timeout.h"
+#include "futex.h"
 #include "cancel.h"
 
 struct io_cancel {
@@ -98,6 +99,10 @@ int io_try_cancel(struct io_uring_task *tctx, struct io_cancel_data *cd,
 	if (ret != -ENOENT)
 		return ret;
 
+	ret = io_futex_cancel(ctx, cd, issue_flags);
+	if (ret != -ENOENT)
+		return ret;
+
 	spin_lock(&ctx->completion_lock);
 	if (!(cd->flags & IORING_ASYNC_CANCEL_FD))
 		ret = io_timeout_cancel(ctx, cd);
io_uring/cancel.h +4 -0
index 6a59ee484d0c..6a2a38df7159 100644
@@ -1,4 +1,6 @@
 // SPDX-License-Identifier: GPL-2.0
+#ifndef IORING_CANCEL_H
+#define IORING_CANCEL_H
 
 #include <linux/io_uring_types.h>
 
@@ -21,3 +23,5 @@ int io_try_cancel(struct io_uring_task *tctx, struct io_cancel_data *cd,
 void init_hash_table(struct io_hash_table *table, unsigned size);
 
 int io_sync_cancel(struct io_ring_ctx *ctx, void __user *arg);
+
+#endif
io_uring/futex.c new file +194 -0

194 lines not on this page · raw message

io_uring/futex.h new file +26 -0
new file mode 100644
index 000000000000..16add2c069cc
@@ -0,0 +1,26 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "cancel.h"
+
+int io_futex_prep(struct io_kiocb *req, const struct io_uring_sqe *sqe);
+int io_futex_wait(struct io_kiocb *req, unsigned int issue_flags);
+int io_futex_wake(struct io_kiocb *req, unsigned int issue_flags);
+
+#if defined(CONFIG_FUTEX)
+int io_futex_cancel(struct io_ring_ctx *ctx, struct io_cancel_data *cd,
+		    unsigned int issue_flags);
+bool io_futex_remove_all(struct io_ring_ctx *ctx, struct task_struct *task,
+			 bool cancel_all);
+#else
+static inline int io_futex_cancel(struct io_ring_ctx *ctx,
+				  struct io_cancel_data *cd,
+				  unsigned int issue_flags);
+{
+	return 0;
+}
+static inline bool io_futex_remove_all(struct io_ring_ctx *ctx,
+				       struct task_struct *task, bool cancel_all)
+{
+	return false;
+}
+#endif
io_uring/io_uring.c +3 -0
index a467064da1af..8270f37c312d 100644
@@ -92,6 +92,7 @@
 #include "cancel.h"
 #include "net.h"
 #include "notif.h"
+#include "futex.h"
 
 #include "timeout.h"
 #include "poll.h"
@@ -336,6 +337,7 @@ static __cold struct io_ring_ctx *io_ring_ctx_alloc(struct io_uring_params *p)
 	INIT_LIST_HEAD(&ctx->tctx_list);
 	ctx->submit_state.free_list.next = NULL;
 	INIT_WQ_LIST(&ctx->locked_free_list);
+	INIT_HLIST_HEAD(&ctx->futex_list);
 	INIT_DELAYED_WORK(&ctx->fallback_work, io_fallback_req_func);
 	INIT_WQ_LIST(&ctx->submit_state.compl_reqs);
 	return ctx;
@@ -3309,6 +3311,7 @@ static __cold bool io_uring_try_cancel_requests(struct io_ring_ctx *ctx,
 	ret |= io_cancel_defer_files(ctx, task, cancel_all);
 	mutex_lock(&ctx->uring_lock);
 	ret |= io_poll_remove_all(ctx, task, cancel_all);
+	ret |= io_futex_remove_all(ctx, task, cancel_all);
 	mutex_unlock(&ctx->uring_lock);
 	ret |= io_kill_timeouts(ctx, task, cancel_all);
 	if (task)
io_uring/opdef.c +24 -1
index 3b9c6489b8b6..e6b03d7f82e5 100644
@@ -33,6 +33,7 @@
 #include "poll.h"
 #include "cancel.h"
 #include "rw.h"
+#include "futex.h"
 
 static int io_no_issue(struct io_kiocb *req, unsigned int issue_flags)
 {
@@ -426,11 +427,26 @@ const struct io_issue_def io_issue_defs[] = {
 		.issue			= io_sendmsg_zc,
 #else
 		.prep			= io_eopnotsupp_prep,
+#endif
+	},
+	[IORING_OP_FUTEX_WAIT] = {
+#if defined(CONFIG_FUTEX)
+		.prep			= io_futex_prep,
+		.issue			= io_futex_wait,
+#else
+		.prep			= io_eopnotsupp_prep,
+#endif
+	},
+	[IORING_OP_FUTEX_WAKE] = {
+#if defined(CONFIG_FUTEX)
+		.prep			= io_futex_prep,
+		.issue			= io_futex_wake,
+#else
+		.prep			= io_eopnotsupp_prep,
 #endif
 	},
 };
 
-
 const struct io_cold_def io_cold_defs[] = {
 	[IORING_OP_NOP] = {
 		.name			= "NOP",
@@ -648,6 +664,13 @@ const struct io_cold_def io_cold_defs[] = {
 		.fail			= io_sendrecv_fail,
 #endif
 	},
+	[IORING_OP_FUTEX_WAIT] = {
+		.name			= "FUTEX_WAIT",
+	},
+
+	[IORING_OP_FUTEX_WAKE] = {
+		.name			= "FUTEX_WAKE",
+	},
 };
 
 const char *io_uring_get_opcode(u8 opcode)
Signature · 1 line
2.39.2
#6 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 1 line · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

This is great. I was so sure io_uring had this support already for some reason. I might have dreamed it.

The semantics are tricky, though. You might want to CC peterZ and tglx directly.

Quoted 2 lines

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

As far as I know, the _BITSET variant are not commonly used in the current interface. I haven't seen any code that really benefits from it.

Quoted 2 lines

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

But it is definitely safe to have a single one, basically with the _BITSET semantics.

Quoted 3 lines

FUTEX_WAKE is straight forward, as we can always just do those inline. FUTEX_WAIT will queue the futex with an appropriate callback, and that callback will in turn post a CQE when it has triggered.

Even with an asynchronous model, it might make sense to halt execution of further queued operations until futex completes. I think IOSQE_IO_DRAIN is a barrier only against the submission part, so it wouldn't hep. Is there a way to ensure this ordering?

I know, it goes against the asynchronous nature of io_uring, but I think it might be a valid use case. Say we extend FUTEX_WAIT with a way to acquire the futex in kernel space. Then, when the CQE returns, we know the lock is acquired. if we can queue dependencies on that (stronger than the link semantics), we could queue operations to be executed once the lock is taken. Makes sense?

Quoted 6 lines

Cancelations are supported, both from the application point-of-view, but also to be able to cancel pending waits if the ring exits before all events have occurred.

This is just the barebones wait/wake support. Features to be added later:

One item high on my wishlist would be the futexv semantics (wait on any of a set of futexes). It cannot be implemented by issuing several FUTEX_WAIT.

Signature · 1 line
Gabriel Krisman Bertazi
author maintainer
#7 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 6 lines · Gabriel Krisman Bertazi
Quoted 1 line · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

This is great. I was so sure io_uring had this support already for some reason. I might have dreamed it.

I think you did :-)

Quoted 2 lines

The semantics are tricky, though. You might want to CC peterZ and tglx directly.

For sure, I'll take it wider soon enough. Just wanted to iron out io_uring details first.

Quoted 6 lines
Quoted 2 lines

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

As far as I know, the _BITSET variant are not commonly used in the current interface. I haven't seen any code that really benefits from it.

Since FUTEX_WAKE is a strict subset of FUTEX_WAKE_BITSET, makes little sense to not just support both imho.

Quoted 5 lines
Quoted 2 lines

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

But it is definitely safe to have a single one, basically with the _BITSET semantics.

Yep I think so.

Quoted 8 lines
Quoted 3 lines

FUTEX_WAKE is straight forward, as we can always just do those inline. FUTEX_WAIT will queue the futex with an appropriate callback, and that callback will in turn post a CQE when it has triggered.

Even with an asynchronous model, it might make sense to halt execution of further queued operations until futex completes. I think IOSQE_IO_DRAIN is a barrier only against the submission part, so it wouldn't hep. Is there a way to ensure this ordering?

You'd use link for that - link whatever depends on the wake to the futex wait. Or just queue it up once you reap the wait completion, when that is posted because we got woken.

Quoted 6 lines

I know, it goes against the asynchronous nature of io_uring, but I think it might be a valid use case. Say we extend FUTEX_WAIT with a way to acquire the futex in kernel space. Then, when the CQE returns, we know the lock is acquired. if we can queue dependencies on that (stronger than the link semantics), we could queue operations to be executed once the lock is taken. Makes sense?

It does, and acquiring it _may_ make sense indeed. But I'd rather punt that to a later thing, and focus on getting the standard (and smaller) primitives done first.

Quoted 10 lines
Quoted 6 lines

Cancelations are supported, both from the application point-of-view, but also to be able to cancel pending waits if the ring exits before all events have occurred.

This is just the barebones wait/wake support. Features to be added later:

One item high on my wishlist would be the futexv semantics (wait on any of a set of futexes). It cannot be implemented by issuing several FUTEX_WAIT.

Yep, I do think that one is interesting enough to consider upfront. Unfortunately the internal implementation of that does not look that great, though I'm sure we can make that work. But would likely require some futexv refactoring to make it work. I can take a look at it.

You could obviously do futexv with this patchset, just posting N futex waits and canceling N-1 when you get woken by one. Though that's of course not very pretty or nice to use, but design wise it would totally work as you don't actually block on these with io_uring.

Signature · 1 line
Jens Axboe
#8 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 9 lines · Jens Axboe
Quoted 6 lines · Gabriel Krisman Bertazi
Quoted 1 line · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

This is great. I was so sure io_uring had this support already for some reason. I might have dreamed it.

I think you did :-)

Premonitory! Still, there should be better things to dream about than with the kernel code.

Quoted 8 lines
Quoted 4 lines

Even with an asynchronous model, it might make sense to halt execution of further queued operations until futex completes. I think IOSQE_IO_DRAIN is a barrier only against the submission part, so it wouldn't hep. Is there a way to ensure this ordering?

You'd use link for that - link whatever depends on the wake to the futex wait. Or just queue it up once you reap the wait completion, when that is posted because we got woken.

The challenge of linked requests, in my opinion, is that once a link chain starts, everything needs to be link together, and a single error fails everything, which is ok when operations are related, but not so much when doing IO to different files from the same ring.

Quoted 11 lines
Quoted 10 lines
Quoted 6 lines

Cancelations are supported, both from the application point-of-view, but also to be able to cancel pending waits if the ring exits before all events have occurred.

This is just the barebones wait/wake support. Features to be added later:

One item high on my wishlist would be the futexv semantics (wait on any of a set of futexes). It cannot be implemented by issuing several FUTEX_WAIT.

Quoted 5 lines

Yep, I do think that one is interesting enough to consider upfront. Unfortunately the internal implementation of that does not look that great, though I'm sure we can make that work. ? But would likely require some futexv refactoring to make it work. I can take a look at it.

No disagreement here. To be fair, the main challenge was making the new interface compatible with a futex being waited on/waked the original interface. At some point, we had a really nice design for a single object, but we spent two years bikesheding over the interface and ended up merging something pretty much similar to the proposal from two years prior.

Quoted 4 lines

You could obviously do futexv with this patchset, just posting N futex waits and canceling N-1 when you get woken by one. Though that's of course not very pretty or nice to use, but design wise it would totally work as you don't actually block on these with io_uring.

Yes, but at that point, i guess it'd make more sense to implement the same semantics by polling over a set of eventfds or having a single futex and doing dispatch in userspace.

thanks,

Signature · 1 line
Gabriel Krisman Bertazi
author maintainer
#9 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 7 lines · Gabriel Krisman Bertazi
Quoted 5 lines · Jens Axboe
Quoted 4 lines · Gabriel Krisman Bertazi
Quoted 1 line · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

This is great. I was so sure io_uring had this support already for some reason. I might have dreamed it.

I think you did :-)

Premonitory! Still, there should be better things to dream about than with the kernel code.

I dunno, if it's io_uring related I'm a supporter.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

Even with an asynchronous model, it might make sense to halt execution of further queued operations until futex completes. I think IOSQE_IO_DRAIN is a barrier only against the submission part, so it wouldn't hep. Is there a way to ensure this ordering?

Quoted 8 lines
Quoted 3 lines

You'd use link for that - link whatever depends on the wake to the futex wait. Or just queue it up once you reap the wait completion, when that is posted because we got woken.

The challenge of linked requests, in my opinion, is that once a link chain starts, everything needs to be link together, and a single error fails everything, which is ok when operations are related, but not so much when doing IO to different files from the same ring.

Not quite sure if you're misunderstanding links, or just have a different use case in mind. You can certainly have several independent chains of links.

Quoted 17 lines
Quoted 11 lines
Quoted 10 lines
Quoted 6 lines

Cancelations are supported, both from the application point-of-view, but also to be able to cancel pending waits if the ring exits before all events have occurred.

This is just the barebones wait/wake support. Features to be added later:

One item high on my wishlist would be the futexv semantics (wait on any of a set of futexes). It cannot be implemented by issuing several FUTEX_WAIT.

Quoted 5 lines

Yep, I do think that one is interesting enough to consider upfront. Unfortunately the internal implementation of that does not look that great, though I'm sure we can make that work. ? But would likely require some futexv refactoring to make it work. I can take a look at it.

Quoted 6 lines

No disagreement here. To be fair, the main challenge was making the new interface compatible with a futex being waited on/waked the original interface. At some point, we had a really nice design for a single object, but we spent two years bikesheding over the interface and ended up merging something pretty much similar to the proposal from two years prior.

It turned out not to be too bad - here's a poc:

https://git.kernel.dk/cgit/linux/commit/?h=io_uring-futex&id=421b12df4ed0bb25c53afe496370bc2b70b04e15

needs a bit of splitting and cleaning, notably I think I need to redo the futex_q->wake_data bit to make that cleaner with the current use case and the async use case. With that, then everything can just use futex_queue() and the only difference really is that the sync variants will do timer setup upfront and then sleep at the bottom, where the async part just calls the meat of the function.

Quoted 8 lines
Quoted 4 lines

You could obviously do futexv with this patchset, just posting N futex waits and canceling N-1 when you get woken by one. Though that's of course not very pretty or nice to use, but design wise it would totally work as you don't actually block on these with io_uring.

Yes, but at that point, i guess it'd make more sense to implement the same semantics by polling over a set of eventfds or having a single futex and doing dispatch in userspace.

Oh yeah, would not recommend the above approach. Just saying that you COULD do that if you really wanted to, which is not something you could do with futex before waitv. But kind of moot now that there's at least a prototype.

Signature · 1 line
Jens Axboe
#10 lore raw

io_uring link semantics (was [PATCH 5/6] io_uring: add support for futex wake and wait)

Quoted 11 lines · Jens Axboe
Quoted 9 lines · Gabriel Krisman Bertazi
Quoted 8 lines
Quoted 4 lines

Even with an asynchronous model, it might make sense to halt execution of further queued operations until futex completes. I think IOSQE_IO_DRAIN is a barrier only against the submission part, so it wouldn't hep. Is there a way to ensure this ordering?

You'd use link for that - link whatever depends on the wake to the futex wait. Or just queue it up once you reap the wait completion, when that is posted because we got woken.

Quoted 8 lines
Quoted 4 lines

The challenge of linked requests, in my opinion, is that once a link chain starts, everything needs to be link together, and a single error fails everything, which is ok when operations are related, but not so much when doing IO to different files from the same ring.

Not quite sure if you're misunderstanding links, or just have a different use case in mind. You can certainly have several independent chains of links.

I might be. Or my use case might be bogus. Please, correct me if either is the case.

My understanding is that a link is a sequence of commands all carrying the IOSQE_IO_LINK flag. io_uring guarantees the ordering within the link and, if a previous command fails, the rest of the link chain is aborted.

But, if I have independent commands to submit in between, i.e. on a different fd, I might want an intermediary operation to not be dependent on the rest of the link without breaking the chain. Most of the time I know ahead of time the entire chain, and I can batch the operations together. But, I think it might be a problem specifically for some unbounded commands like FUTEX_WAIT and recv. I want a specific operation to depend on a recv, but I might not be able to specify ahead of time all of the dependent operations. I'd need to wait for a recv command to complete and only then issue the dependency, to guarantee ordering, or I make sure that everything I put on the ring in the meantime is part of one big link submitted sequentially.

A related issue/example that comes to mind would be two recvs/sends against the same socket. When doing a syscall, I know the first recv will return ahead of the second because it is, well, synchronous. On io_uring, I think it must be a link. I might be recv'ing a huge stream from the network, and I can't tell if the packet is done on a single recv. I could have to issue a second recv but I either make it linked ahead of time, or I need to wait for the first recv to complete, to only then submit the second one. The problem is the ordering of recvs; from my understanding of the code, I cannot assure the first recv will complete before the second, without a link.

Sorry if I'm wrong and there are ways around it, but it is a struggling points for me at the moment with using io_uring.

Signature · 1 line
Gabriel Krisman Bertazi
#11 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

In reply to Jens Axboe

Hi,

I'd been chatting with Jens about this, so obviously I'm interested in the feature...

Quoted 7 lines · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

One thing I was wondering about is what happens when there are multiple OP_FUTEX_WAITs queued for the same futex, and that futex gets woken up. I don't really have an opinion about what would be best, just that it'd be helpful to specify the behaviour.

Greetings,

Andres Freund

author maintainer
#12 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 11 lines · Andres Freund

Hi,

I'd been chatting with Jens about this, so obviously I'm interested in the feature...

Quoted 5 lines · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

Quoted 7 lines
Quoted 2 lines

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

One thing I was wondering about is what happens when there are multiple OP_FUTEX_WAITs queued for the same futex, and that futex gets woken up. I don't really have an opinion about what would be best, just that it'd be helpful to specify the behaviour.

Not sure I follow the question, can you elaborate?

If you have N futex waits on the same futex and someone does a wait (with wakenum >= N), then they'd all wake and post a CQE. If less are woken because the caller asked for less than N, than that number should be woken.

IOW, should have the same semantics as "normal" futex waits.

Or maybe I'm totally missing what is being asked here...

Signature · 1 line
Jens Axboe
#13 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Hi,

Quoted 20 lines · Jens Axboe
Quoted 11 lines · Andres Freund

Hi,

I'd been chatting with Jens about this, so obviously I'm interested in the feature...

Quoted 5 lines · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

Quoted 7 lines
Quoted 2 lines

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

One thing I was wondering about is what happens when there are multiple OP_FUTEX_WAITs queued for the same futex, and that futex gets woken up. I don't really have an opinion about what would be best, just that it'd be helpful to specify the behaviour.

Quoted 8 lines

Not sure I follow the question, can you elaborate?

If you have N futex waits on the same futex and someone does a wait (with wakenum >= N), then they'd all wake and post a CQE. If less are woken because the caller asked for less than N, than that number should be woken.

IOW, should have the same semantics as "normal" futex waits.

With a normal futex wait you can't wait multiple times on the same futex in one thread. But with the proposed io_uring interface, one can.

Basically, what is the defined behaviour for:

   sqe = io_uring_get_sqe(ring);
   io_uring_prep_futex_wait(sqe, futex, 0, FUTEX_BITSET_MATCH_ANY);

   sqe = io_uring_get_sqe(ring);
   io_uring_prep_futex_wait(sqe, futex, 0, FUTEX_BITSET_MATCH_ANY);

io_uring_submit(ring)

when someone does:
futex(FUTEX_WAKE, futex, 1, 0, 0, 0);
or
futex(FUTEX_WAKE, futex, INT_MAX, 0, 0, 0);

or the equivalent io_uring operation.

Is it an error? Will there always be two cqes queued? Will it depend on the number of wakeups specified by the waker? I'd assume the latter, but it'd be good to specify that.

Greetings,

Andres Freund

author maintainer
#14 lore raw

Re: [PATCH 5/6] io_uring: add support for futex wake and wait

Quoted 30 lines · Andres Freund

Hi,

Quoted 27 lines · Jens Axboe
Quoted 11 lines · Andres Freund

Hi,

I'd been chatting with Jens about this, so obviously I'm interested in the feature...

Quoted 5 lines · Jens Axboe

Add support for FUTEX_WAKE/WAIT primitives.

IORING_OP_FUTEX_WAKE is mix of FUTEX_WAKE and FUTEX_WAKE_BITSET, as it does support passing in a bitset.

Quoted 7 lines
Quoted 2 lines

Similary, IORING_OP_FUTEX_WAIT is a mix of FUTEX_WAIT and FUTEX_WAIT_BITSET.

One thing I was wondering about is what happens when there are multiple OP_FUTEX_WAITs queued for the same futex, and that futex gets woken up. I don't really have an opinion about what would be best, just that it'd be helpful to specify the behaviour.

Not sure I follow the question, can you elaborate?

If you have N futex waits on the same futex and someone does a wait (with wakenum >= N), then they'd all wake and post a CQE. If less are woken because the caller asked for less than N, than that number should be woken.

Quoted 4 lines
Quoted 1 line

IOW, should have the same semantics as "normal" futex waits.

With a normal futex wait you can't wait multiple times on the same futex in one thread. But with the proposed io_uring interface, one can.

Right, but you could have N threads waiting on the same futex.

Quoted 8 lines

Basically, what is the defined behaviour for:

   sqe = io_uring_get_sqe(ring);
   io_uring_prep_futex_wait(sqe, futex, 0, FUTEX_BITSET_MATCH_ANY);

   sqe = io_uring_get_sqe(ring);
   io_uring_prep_futex_wait(sqe, futex, 0, FUTEX_BITSET_MATCH_ANY);
Quoted 8 lines

io_uring_submit(ring)

when someone does:

   futex(FUTEX_WAKE, futex, 1, 0, 0, 0);
   or
   futex(FUTEX_WAKE, futex, INT_MAX, 0, 0, 0);

or the equivalent io_uring operation.

Waking with num=1 should wake just one of them, which one is really down to the futex ordering which depends on task priority (which would be the same here), and ordered after that. So first one should wake the first sqe queued.

Second one will wake all of them, in that order.

I'll put that in the the test case.

Quoted 3 lines

Is it an error? Will there always be two cqes queued? Will it depend on the number of wakeups specified by the waker? I'd assume the latter, but it'd be good to specify that.

It's not an error, I would not want to police that. It will purely depend on the number of wakes specified by the wake operation. If it's 1, one will be triggered. If it's INT_MAX, then both of them will trigger. First case will generate one CQE, second one will generate both CQEs.

No documentation has been written for the io_uring bits yet. But the current branch is ready for wider posting, so I should get that written up too...

Signature · 1 line
Jens Axboe
author maintainer
#15 lore raw

PATCH 6/6 io_uring/futex: enable use of the allocation caches for futex_q

In reply to Jens Axboe

We're under the ctx uring_lock for the issue and completion path anyway, wire up the futex_q allocator so we can just recycle entries rather than hit the allocator every time.

---
 include/linux/io_uring_types.h |  1 +
 io_uring/futex.c               | 65 +++++++++++++++++++++++++++-------
 io_uring/futex.h               |  8 +++++
 io_uring/io_uring.c            |  2 ++
 4 files changed, 63 insertions(+), 13 deletions(-)
include/linux/io_uring_types.h +1 -0
index d796b578c129..a7f03d8d879f 100644
@@ -274,6 +274,7 @@ struct io_ring_ctx {
 	unsigned int		locked_free_nr;
 
 	struct hlist_head	futex_list;
+	struct io_alloc_cache	futex_cache;
 
 	const struct cred	*sq_creds;	/* cred used for __io_sq_thread() */
 	struct io_sq_data	*sq_data;	/* if using sq thread polling */
io_uring/futex.c +52 -13

115 lines not on this page · raw message

io_uring/futex.h +8 -0
index 16add2c069cc..e60d0abaf676 100644
@@ -11,6 +11,8 @@ int io_futex_cancel(struct io_ring_ctx *ctx, struct io_cancel_data *cd,
 		    unsigned int issue_flags);
 bool io_futex_remove_all(struct io_ring_ctx *ctx, struct task_struct *task,
 			 bool cancel_all);
+void io_futex_cache_init(struct io_ring_ctx *ctx);
+void io_futex_cache_free(struct io_ring_ctx *ctx);
 #else
 static inline int io_futex_cancel(struct io_ring_ctx *ctx,
 				  struct io_cancel_data *cd,
@@ -23,4 +25,10 @@ static inline bool io_futex_remove_all(struct io_ring_ctx *ctx,
 {
 	return false;
 }
+static inline void io_futex_cache_init(struct io_ring_ctx *ctx)
+{
+}
+static inline void io_futex_cache_free(struct io_ring_ctx *ctx)
+{
+}
 #endif
io_uring/io_uring.c +2 -0
index 8270f37c312d..7db2a139d110 100644
@@ -318,6 +318,7 @@ static __cold struct io_ring_ctx *io_ring_ctx_alloc(struct io_uring_params *p)
 			    sizeof(struct async_poll));
 	io_alloc_cache_init(&ctx->netmsg_cache, IO_ALLOC_CACHE_MAX,
 			    sizeof(struct io_async_msghdr));
+	io_futex_cache_init(ctx);
 	init_completion(&ctx->ref_comp);
 	xa_init_flags(&ctx->personalities, XA_FLAGS_ALLOC1);
 	mutex_init(&ctx->uring_lock);
@@ -2917,6 +2918,7 @@ static __cold void io_ring_ctx_free(struct io_ring_ctx *ctx)
 	io_eventfd_unregister(ctx);
 	io_alloc_cache_free(&ctx->apoll_cache, io_apoll_cache_free);
 	io_alloc_cache_free(&ctx->netmsg_cache, io_netmsg_cache_free);
+	io_futex_cache_free(ctx);
 	io_destroy_buffers(ctx);
 	mutex_unlock(&ctx->uring_lock);
 	if (ctx->sq_creds)
Signature · 1 line
2.39.2