Skip to contentSkip to conversation

io_uring: fix skipping of old timeout events

PATCH Superseded Marcelo Diop-Gonzalez 2 participants 16 messages Dec 19, 2020 – Jan 14, 2021

Subsystems (2)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v2 cover io_uring: fix skipping of old timeout events

These two patches try to fix a problem with IORING_OP_TIMEOUT events not being flushed if they should already have expired. The test below hangs before this change (unless you run with $ ./a.out ~/somefile 1):

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <liburing.h>

int main(int argc, char **argv) {
	if (argc < 2)
		return 1;

	int fd = open(argv[1], O_RDONLY);
	if (fd < 0) {
		perror("open");
		return 1;
	}

	struct io_uring ring;
	io_uring_queue_init(4, &ring, 0);

	struct io_uring_sqe *sqe = io_uring_get_sqe(&ring);

	struct __kernel_timespec ts = { .tv_sec = 9999999 };
	io_uring_prep_timeout(sqe, &ts, 1, 0);
	sqe->user_data = 123;
	int ret = io_uring_submit(&ring);
	if (ret < 0) {
		fprintf(stderr, "submit(timeout_sqe): %d\n", ret);
		return 1;
	}

	int n = 2;
	if (argc > 2)
		n = atoi(argv[2]);

	char buf;
	for (int i = 0; i < n; i++) {
		sqe = io_uring_get_sqe(&ring);
		if (!sqe) {
			fprintf(stderr, "too many\n");
			exit(1);
		}
		io_uring_prep_read(sqe, fd, &buf, 1, 0);
	}
	ret = io_uring_submit(&ring);
	if (ret < 0) {
		fprintf(stderr, "submit(read_sqe): %d\n", ret);
		exit(1);
	}

	struct io_uring_cqe *cqe;
	for (int i = 0; i < n+1; i++) {
		struct io_uring_cqe *cqe;
		int ret = io_uring_wait_cqe(&ring, &cqe);
		if (ret < 0) {
			fprintf(stderr, "wait_cqe(): %d\n", ret);
			return 1;
		}
		if (cqe->user_data == 123)
			printf("timeout found\n");
		io_uring_cqe_seen(&ring, cqe);
	}
}

v2: Properly handle u32 overflow issues

Marcelo Diop-Gonzalez (2):
io_uring: only increment ->cq_timeouts along with ->cached_cq_tail
io_uring: flush timeouts that should already have expired

 fs/io_uring.c | 44 ++++++++++++++++++++++++++++++--------------
 1 file changed, 30 insertions(+), 14 deletions(-)
Signature · 1 line
2.20.1
#1 lore raw

PATCH v2 1/2 io_uring: only increment ->cq_timeouts along with ->cached_cq_tail

The quantity ->cached_cq_tail - ->cq_timeouts is used to tell how many non-timeout events have happened, but this subtraction could overflow if ->cq_timeouts is incremented more times than ->cached_cq_tail. It's maybe unlikely, but currently this can happen if a timeout event overflows the cqring, since in that case io_get_cqring() doesn't increment ->cached_cq_tail, but ->cq_timeouts is incremented by the caller. Fix it by incrementing ->cq_timeouts inside io_get_cqring().

---
 fs/io_uring.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)
fs/io_uring.c +7 -7
index f3690dfdd564..f394bf358022 100644
@@ -1582,8 +1582,6 @@ static void io_kill_timeout(struct io_kiocb *req)
 
 	ret = hrtimer_try_to_cancel(&io->timer);
 	if (ret != -1) {
-		atomic_set(&req->ctx->cq_timeouts,
-			atomic_read(&req->ctx->cq_timeouts) + 1);
 		list_del_init(&req->timeout.list);
 		io_cqring_fill_event(req, 0);
 		io_put_req_deferred(req, 1);
@@ -1664,7 +1662,7 @@ static inline bool io_sqring_full(struct io_ring_ctx *ctx)
 	return READ_ONCE(r->sq.tail) - ctx->cached_sq_head == r->sq_ring_entries;
 }
 
-static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
+static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx, u8 opcode)
 {
 	struct io_rings *rings = ctx->rings;
 	unsigned tail;
@@ -1679,6 +1677,10 @@ static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
 		return NULL;
 
 	ctx->cached_cq_tail++;
+	if (opcode == IORING_OP_TIMEOUT)
+		atomic_set(&ctx->cq_timeouts,
+			   atomic_read(&ctx->cq_timeouts) + 1);
+
 	return &rings->cqes[tail & ctx->cq_mask];
 }
 
@@ -1728,7 +1730,7 @@ static bool io_cqring_overflow_flush(struct io_ring_ctx *ctx, bool force,
 		if (!io_match_task(req, tsk, files))
 			continue;
 
-		cqe = io_get_cqring(ctx);
+		cqe = io_get_cqring(ctx, req->opcode);
 		if (!cqe && !force)
 			break;
 
@@ -1776,7 +1778,7 @@ static void __io_cqring_fill_event(struct io_kiocb *req, long res, long cflags)
 	 * submission (by quite a lot). Increment the overflow count in
 	 * the ring.
 	 */
-	cqe = io_get_cqring(ctx);
+	cqe = io_get_cqring(ctx, req->opcode);
 	if (likely(cqe)) {
 		WRITE_ONCE(cqe->user_data, req->user_data);
 		WRITE_ONCE(cqe->res, res);
@@ -5618,8 +5620,6 @@ static enum hrtimer_restart io_timeout_fn(struct hrtimer *timer)
 
 	spin_lock_irqsave(&ctx->completion_lock, flags);
 	list_del_init(&req->timeout.list);
-	atomic_set(&req->ctx->cq_timeouts,
-		atomic_read(&req->ctx->cq_timeouts) + 1);
 
 	io_cqring_fill_event(req, -ETIME);
 	io_commit_cqring(ctx);
Signature · 1 line
2.20.1
#2 lore raw

Re: [PATCH v2 1/2] io_uring: only increment ->cq_timeouts along with ->cached_cq_tail

Quoted 36 lines · Marcelo Diop-Gonzalez

The quantity ->cached_cq_tail - ->cq_timeouts is used to tell how many non-timeout events have happened, but this subtraction could overflow if ->cq_timeouts is incremented more times than ->cached_cq_tail. It's maybe unlikely, but currently this can happen if a timeout event overflows the cqring, since in that case io_get_cqring() doesn't increment ->cached_cq_tail, but ->cq_timeouts is incremented by the caller. Fix it by incrementing ->cq_timeouts inside io_get_cqring().

---
 fs/io_uring.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)
fs/io_uring.c +1 -3
index f3690dfdd564..f394bf358022 100644
@@ -1582,8 +1582,6 @@ static void io_kill_timeout(struct io_kiocb *req)
 
 	ret = hrtimer_try_to_cancel(&io->timer);
 	if (ret != -1) {
-		atomic_set(&req->ctx->cq_timeouts,
-			atomic_read(&req->ctx->cq_timeouts) + 1);
 		list_del_init(&req->timeout.list);
 		io_cqring_fill_event(req, 0);
 		io_put_req_deferred(req, 1);
@@ -1664,7 +1662,7 @@ static inline bool io_sqring_full(struct io_ring_ctx *ctx)
 	return READ_ONCE(r->sq.tail) - ctx->cached_sq_head == r->sq_ring_entries;
 }
 
-static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
+static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx, u8 opcode)
 {
 	struct io_rings *rings = ctx->rings;
 	unsigned tail;

fs/io_uring.c static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx) · line 1683

Quoted 7 lines
fs/io_uring.c +4 -0
@@ -1679,6 +1677,10 @@ static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
 		return NULL;
 
 	ctx->cached_cq_tail++;
+	if (opcode == IORING_OP_TIMEOUT)
+		atomic_set(&ctx->cq_timeouts,
+			   atomic_read(&ctx->cq_timeouts) + 1);
+

Don't think I like it. The function is pretty hot, so wouldn't want that extra burden just for timeouts, which should be cold enough especially with the new timeout CQ waits. Also passing opcode here is awkward and not very great abstraction wise.

Quoted 31 lines
fs/io_uring.c +2 -4
 	return &rings->cqes[tail & ctx->cq_mask];
 }
 
@@ -1728,7 +1730,7 @@ static bool io_cqring_overflow_flush(struct io_ring_ctx *ctx, bool force,
 		if (!io_match_task(req, tsk, files))
 			continue;
 
-		cqe = io_get_cqring(ctx);
+		cqe = io_get_cqring(ctx, req->opcode);
 		if (!cqe && !force)
 			break;
 
@@ -1776,7 +1778,7 @@ static void __io_cqring_fill_event(struct io_kiocb *req, long res, long cflags)
 	 * submission (by quite a lot). Increment the overflow count in
 	 * the ring.
 	 */
-	cqe = io_get_cqring(ctx);
+	cqe = io_get_cqring(ctx, req->opcode);
 	if (likely(cqe)) {
 		WRITE_ONCE(cqe->user_data, req->user_data);
 		WRITE_ONCE(cqe->res, res);
@@ -5618,8 +5620,6 @@ static enum hrtimer_restart io_timeout_fn(struct hrtimer *timer)
 
 	spin_lock_irqsave(&ctx->completion_lock, flags);
 	list_del_init(&req->timeout.list);
-	atomic_set(&req->ctx->cq_timeouts,
-		atomic_read(&req->ctx->cq_timeouts) + 1);
 
 	io_cqring_fill_event(req, -ETIME);
 	io_commit_cqring(ctx);
Signature · 1 line
Pavel Begunkov
#3 lore raw

Re: [PATCH v2 1/2] io_uring: only increment ->cq_timeouts along with ->cached_cq_tail

Yeah I agree this one is kindof ugly... I'll try to think of a different way

-Marcelo

Quoted 85 lines · Pavel Begunkov
Quoted 36 lines · Marcelo Diop-Gonzalez

The quantity ->cached_cq_tail - ->cq_timeouts is used to tell how many non-timeout events have happened, but this subtraction could overflow if ->cq_timeouts is incremented more times than ->cached_cq_tail. It's maybe unlikely, but currently this can happen if a timeout event overflows the cqring, since in that case io_get_cqring() doesn't increment ->cached_cq_tail, but ->cq_timeouts is incremented by the caller. Fix it by incrementing ->cq_timeouts inside io_get_cqring().

---
 fs/io_uring.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)
fs/io_uring.c +1 -3
index f3690dfdd564..f394bf358022 100644
@@ -1582,8 +1582,6 @@ static void io_kill_timeout(struct io_kiocb *req)
 
      ret = hrtimer_try_to_cancel(&io->timer);
      if (ret != -1) {
-             atomic_set(&req->ctx->cq_timeouts,
-                     atomic_read(&req->ctx->cq_timeouts) + 1);
              list_del_init(&req->timeout.list);
              io_cqring_fill_event(req, 0);
              io_put_req_deferred(req, 1);
@@ -1664,7 +1662,7 @@ static inline bool io_sqring_full(struct io_ring_ctx *ctx)
      return READ_ONCE(r->sq.tail) - ctx->cached_sq_head == r->sq_ring_entries;
 }
 
-static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
+static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx, u8 opcode)
 {
      struct io_rings *rings = ctx->rings;
      unsigned tail;

fs/io_uring.c static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx) · line 1683

Quoted 7 lines
fs/io_uring.c +4 -0
@@ -1679,6 +1677,10 @@ static struct io_uring_cqe *io_get_cqring(struct io_ring_ctx *ctx)
              return NULL;
 
      ctx->cached_cq_tail++;
+     if (opcode == IORING_OP_TIMEOUT)
+             atomic_set(&ctx->cq_timeouts,
+                        atomic_read(&ctx->cq_timeouts) + 1);
+

Don't think I like it. The function is pretty hot, so wouldn't want that extra burden just for timeouts, which should be cold enough especially with the new timeout CQ waits. Also passing opcode here is awkward and not very great abstraction wise.

Quoted 23 lines
fs/io_uring.c +2 -2
      return &rings->cqes[tail & ctx->cq_mask];
 }
 
@@ -1728,7 +1730,7 @@ static bool io_cqring_overflow_flush(struct io_ring_ctx *ctx, bool force,
              if (!io_match_task(req, tsk, files))
                      continue;
 
-             cqe = io_get_cqring(ctx);
+             cqe = io_get_cqring(ctx, req->opcode);
              if (!cqe && !force)
                      break;
 
@@ -1776,7 +1778,7 @@ static void __io_cqring_fill_event(struct io_kiocb *req, long res, long cflags)
       * submission (by quite a lot). Increment the overflow count in
       * the ring.
       */
-     cqe = io_get_cqring(ctx);
+     cqe = io_get_cqring(ctx, req->opcode);
      if (likely(cqe)) {
              WRITE_ONCE(cqe->user_data, req->user_data);
              WRITE_ONCE(cqe->res, res);

fs/io_uring.c static enum hrtimer_restart io_timeout_fn(struct hrtimer *timer) · line 5625

Quoted 8 lines
fs/io_uring.c +0 -2
@@ -5618,8 +5620,6 @@ static enum hrtimer_restart io_timeout_fn(struct hrtimer *timer)
 
      spin_lock_irqsave(&ctx->completion_lock, flags);
      list_del_init(&req->timeout.list);
-     atomic_set(&req->ctx->cq_timeouts,
-             atomic_read(&req->ctx->cq_timeouts) + 1);
 
      io_cqring_fill_event(req, -ETIME);
      io_commit_cqring(ctx);

--
Pavel Begunkov

#4 lore raw

PATCH v2 2/2 io_uring: flush timeouts that should already have expired

In reply to Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

---
 fs/io_uring.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/io_uring.c +23 -7
index f394bf358022..f62de0cb5fc4 100644
@@ -444,7 +444,7 @@ struct io_cancel {
 struct io_timeout {
 	struct file			*file;
 	u32				off;
-	u32				target_seq;
+	u32				start_seq;
 	struct list_head		list;
 	/* head of the link, used by linked timeouts only */
 	struct io_kiocb			*head;
@@ -1629,6 +1629,24 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 	} while (!list_empty(&ctx->defer_list));
 }
 
+static inline u32 io_timeout_events_left(struct io_kiocb *req)
+{
+	struct io_ring_ctx *ctx = req->ctx;
+	u32 events;
+
+	/*
+	 * events -= req->timeout.start_seq and the comparison between
+	 * ->timeout.off and events will not overflow because each time
+	 * ->cq_timeouts is incremented, ->cached_cq_tail is incremented too.
+	 */
+
+	events = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+	events -= req->timeout.start_seq;
+	if (req->timeout.off > events)
+		return req->timeout.off - events;
+	return 0;
+}
+
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
 	while (!list_empty(&ctx->timeout_list)) {
@@ -1637,8 +1655,7 @@ static void io_flush_timeouts(struct io_ring_ctx *ctx)
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+		if (io_timeout_events_left(req) > 0)
 			break;
 
 		list_del_init(&req->timeout.list);
@@ -5785,7 +5802,6 @@ static int io_timeout(struct io_kiocb *req)
 	struct io_ring_ctx *ctx = req->ctx;
 	struct io_timeout_data *data = req->async_data;
 	struct list_head *entry;
-	u32 tail, off = req->timeout.off;
 
 	spin_lock_irq(&ctx->completion_lock);
 
@@ -5799,8 +5815,8 @@ static int io_timeout(struct io_kiocb *req)
 		goto add;
 	}
 
-	tail = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
-	req->timeout.target_seq = tail + off;
+	req->timeout.start_seq = ctx->cached_cq_tail -
+		atomic_read(&ctx->cq_timeouts);
 
 	/*
 	 * Insertion sort, ensuring the first entry in the list is always
@@ -5813,7 +5829,7 @@ static int io_timeout(struct io_kiocb *req)
 		if (io_is_timeout_noseq(nxt))
 			continue;
 		/* nxt.seq is behind @tail, otherwise would've been completed */
-		if (off >= nxt->timeout.target_seq - tail)
+		if (req->timeout.off >= io_timeout_events_left(nxt))
 			break;
 	}
 add:
Signature · 1 line
2.20.1
#5 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 34 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

---
 fs/io_uring.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/io_uring.c +4 -1
index f394bf358022..f62de0cb5fc4 100644
@@ -444,7 +444,7 @@ struct io_cancel {
 struct io_timeout {
 	struct file			*file;
 	u32				off;
-	u32				target_seq;
+	u32				start_seq;
 	struct list_head		list;
 	/* head of the link, used by linked timeouts only */
 	struct io_kiocb			*head;
@@ -1629,6 +1629,24 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 	} while (!list_empty(&ctx->defer_list));
 }
 
+static inline u32 io_timeout_events_left(struct io_kiocb *req)
+{
+	struct io_ring_ctx *ctx = req->ctx;

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1644

Quoted 10 lines
fs/io_uring.c +10 -0
+	u32 events;
+
+	/*
+	 * events -= req->timeout.start_seq and the comparison between
+	 * ->timeout.off and events will not overflow because each time
+	 * ->cq_timeouts is incremented, ->cached_cq_tail is incremented too.
+	 */
+
+	events = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+	events -= req->timeout.start_seq;

It looks to me that events before the start_seq subtraction can have got wrapped around start_seq.

e.g.
1) you submit a timeout with off=0xff...ff (start_seq=0 for convenience)

2) some time has passed, let @events = 0xff..ff - 1 so the timeout still waits

3) we commit 5 requests at once and call io_commit_cqring() only once for them, so we get @events == 0xff..ff - 1 + 5, i.e. 4

@events == 4 < off == 0xff...ff,
so we didn't trigger out timeout even though should have

Quoted 47 lines
fs/io_uring.c +9 -6
+	if (req->timeout.off > events)
+		return req->timeout.off - events;
+	return 0;
+}
+
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
 	while (!list_empty(&ctx->timeout_list)) {
@@ -1637,8 +1655,7 @@ static void io_flush_timeouts(struct io_ring_ctx *ctx)
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+		if (io_timeout_events_left(req) > 0)
 			break;
 
 		list_del_init(&req->timeout.list);
@@ -5785,7 +5802,6 @@ static int io_timeout(struct io_kiocb *req)
 	struct io_ring_ctx *ctx = req->ctx;
 	struct io_timeout_data *data = req->async_data;
 	struct list_head *entry;
-	u32 tail, off = req->timeout.off;
 
 	spin_lock_irq(&ctx->completion_lock);
 
@@ -5799,8 +5815,8 @@ static int io_timeout(struct io_kiocb *req)
 		goto add;
 	}
 
-	tail = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
-	req->timeout.target_seq = tail + off;
+	req->timeout.start_seq = ctx->cached_cq_tail -
+		atomic_read(&ctx->cq_timeouts);
 
 	/*
 	 * Insertion sort, ensuring the first entry in the list is always
@@ -5813,7 +5829,7 @@ static int io_timeout(struct io_kiocb *req)
 		if (io_is_timeout_noseq(nxt))
 			continue;
 		/* nxt.seq is behind @tail, otherwise would've been completed */
-		if (off >= nxt->timeout.target_seq - tail)
+		if (req->timeout.off >= io_timeout_events_left(nxt))
 			break;
 	}
 add:
Signature · 1 line
Pavel Begunkov
#6 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

Quoted 100 lines
Quoted 26 lines
---
 fs/io_uring.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/io_uring.c +4 -1
index f394bf358022..f62de0cb5fc4 100644
@@ -444,7 +444,7 @@ struct io_cancel {
 struct io_timeout {
 	struct file			*file;
 	u32				off;
-	u32				target_seq;
+	u32				start_seq;
 	struct list_head		list;
 	/* head of the link, used by linked timeouts only */
 	struct io_kiocb			*head;
@@ -1629,6 +1629,24 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 	} while (!list_empty(&ctx->defer_list));
 }
 
+static inline u32 io_timeout_events_left(struct io_kiocb *req)
+{
+	struct io_ring_ctx *ctx = req->ctx;

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1644

Quoted 10 lines
fs/io_uring.c +10 -0
+	u32 events;
+
+	/*
+	 * events -= req->timeout.start_seq and the comparison between
+	 * ->timeout.off and events will not overflow because each time
+	 * ->cq_timeouts is incremented, ->cached_cq_tail is incremented too.
+	 */
+
+	events = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+	events -= req->timeout.start_seq;

It looks to me that events before the start_seq subtraction can have got wrapped around start_seq.

e.g.
1) you submit a timeout with off=0xff...ff (start_seq=0 for convenience)

2) some time has passed, let @events = 0xff..ff - 1 so the timeout still waits

3) we commit 5 requests at once and call io_commit_cqring() only once for them, so we get @events == 0xff..ff - 1 + 5, i.e. 4

@events == 4 < off == 0xff...ff,
so we didn't trigger out timeout even though should have

Quoted 47 lines
fs/io_uring.c +9 -6
+	if (req->timeout.off > events)
+		return req->timeout.off - events;
+	return 0;
+}
+
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
 	while (!list_empty(&ctx->timeout_list)) {
@@ -1637,8 +1655,7 @@ static void io_flush_timeouts(struct io_ring_ctx *ctx)
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+		if (io_timeout_events_left(req) > 0)
 			break;
 
 		list_del_init(&req->timeout.list);
@@ -5785,7 +5802,6 @@ static int io_timeout(struct io_kiocb *req)
 	struct io_ring_ctx *ctx = req->ctx;
 	struct io_timeout_data *data = req->async_data;
 	struct list_head *entry;
-	u32 tail, off = req->timeout.off;
 
 	spin_lock_irq(&ctx->completion_lock);
 
@@ -5799,8 +5815,8 @@ static int io_timeout(struct io_kiocb *req)
 		goto add;
 	}
 
-	tail = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
-	req->timeout.target_seq = tail + off;
+	req->timeout.start_seq = ctx->cached_cq_tail -
+		atomic_read(&ctx->cq_timeouts);
 
 	/*
 	 * Insertion sort, ensuring the first entry in the list is always
@@ -5813,7 +5829,7 @@ static int io_timeout(struct io_kiocb *req)
 		if (io_is_timeout_noseq(nxt))
 			continue;
 		/* nxt.seq is behind @tail, otherwise would've been completed */
-		if (off >= nxt->timeout.target_seq - tail)
+		if (req->timeout.off >= io_timeout_events_left(nxt))
 			break;
 	}
 add:
Signature · 1 line
Pavel Begunkov
#7 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

fs/io_uring.c +10 -2
index cb57e0360fcb..50984709879c 100644
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed)
 			break;
 
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
Signature · 1 line
2.20.1
Quoted 103 lines
Quoted 100 lines
Quoted 26 lines
---
 fs/io_uring.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/io_uring.c +4 -1
index f394bf358022..f62de0cb5fc4 100644
@@ -444,7 +444,7 @@ struct io_cancel {
 struct io_timeout {
 	struct file			*file;
 	u32				off;
-	u32				target_seq;
+	u32				start_seq;
 	struct list_head		list;
 	/* head of the link, used by linked timeouts only */
 	struct io_kiocb			*head;
@@ -1629,6 +1629,24 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 	} while (!list_empty(&ctx->defer_list));
 }
 
+static inline u32 io_timeout_events_left(struct io_kiocb *req)
+{
+	struct io_ring_ctx *ctx = req->ctx;

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1644

Quoted 10 lines
fs/io_uring.c +10 -0
+	u32 events;
+
+	/*
+	 * events -= req->timeout.start_seq and the comparison between
+	 * ->timeout.off and events will not overflow because each time
+	 * ->cq_timeouts is incremented, ->cached_cq_tail is incremented too.
+	 */
+
+	events = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+	events -= req->timeout.start_seq;

It looks to me that events before the start_seq subtraction can have got wrapped around start_seq.

e.g.
1) you submit a timeout with off=0xff...ff (start_seq=0 for convenience)

2) some time has passed, let @events = 0xff..ff - 1 so the timeout still waits

3) we commit 5 requests at once and call io_commit_cqring() only once for them, so we get @events == 0xff..ff - 1 + 5, i.e. 4

@events == 4 < off == 0xff...ff,
so we didn't trigger out timeout even though should have

Quoted 47 lines
fs/io_uring.c +9 -6
+	if (req->timeout.off > events)
+		return req->timeout.off - events;
+	return 0;
+}
+
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
 	while (!list_empty(&ctx->timeout_list)) {
@@ -1637,8 +1655,7 @@ static void io_flush_timeouts(struct io_ring_ctx *ctx)
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+		if (io_timeout_events_left(req) > 0)
 			break;
 
 		list_del_init(&req->timeout.list);
@@ -5785,7 +5802,6 @@ static int io_timeout(struct io_kiocb *req)
 	struct io_ring_ctx *ctx = req->ctx;
 	struct io_timeout_data *data = req->async_data;
 	struct list_head *entry;
-	u32 tail, off = req->timeout.off;
 
 	spin_lock_irq(&ctx->completion_lock);
 
@@ -5799,8 +5815,8 @@ static int io_timeout(struct io_kiocb *req)
 		goto add;
 	}
 
-	tail = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
-	req->timeout.target_seq = tail + off;
+	req->timeout.start_seq = ctx->cached_cq_tail -
+		atomic_read(&ctx->cq_timeouts);
 
 	/*
 	 * Insertion sort, ensuring the first entry in the list is always
@@ -5813,7 +5829,7 @@ static int io_timeout(struct io_kiocb *req)
 		if (io_is_timeout_noseq(nxt))
 			continue;
 		/* nxt.seq is behind @tail, otherwise would've been completed */
-		if (off >= nxt->timeout.target_seq - tail)
+		if (req->timeout.off >= io_timeout_events_left(nxt))
 			break;
 	}
 add:
Signature · 1 line
Pavel Begunkov
#8 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 30 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

Quoted 6 lines

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

I'll take a look later, but IOPOLL doesn't support timeouts, see the first if in io_timeout_prep(), so that's not a problem, but would better to leave a comment.

Quoted 43 lines
fs/io_uring.c +10 -2
index cb57e0360fcb..50984709879c 100644
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed)
 			break;
 
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
Signature · 1 line
Pavel Begunkov
#9 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 38 lines · Pavel Begunkov
Quoted 30 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

Quoted 6 lines

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

Quoted 4 lines

I'll take a look later, but IOPOLL doesn't support timeouts, see the first if in io_timeout_prep(), so that's not a problem, but would better to leave a comment.

Ah right! Nevermind about that then.

Quoted 46 lines
Quoted 43 lines
fs/io_uring.c +10 -2
index cb57e0360fcb..50984709879c 100644
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed)
 			break;
 
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
Signature · 1 line
Pavel Begunkov
#10 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

In reply to Marcelo Diop-Gonzalez
Quoted 42 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

fs/io_uring.c +0 -0
index cb57e0360fcb..50984709879c 100644

fs/io_uring.c struct io_ring_ctx { · line 356

Quoted 4 lines
fs/io_uring.c +1 -0
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;

It looks like that "last flush" is a good direction. I think there can be problems at extremes like completing 2^32 requests at once, but should be ok in practice. Anyway better than it's now.

What about the first patch about overflows and cq_timeouts? I assume that problem is still there, isn't it?

See comments below, but if it passes liburing tests, please send a patch.

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1638

Quoted 9 lines
fs/io_uring.c +2 -0
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+

a nit,

if (list_empty()) return; + do {} while();

timeouts can be rare enough

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1646

Quoted 10 lines
fs/io_uring.c +2 -2
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+

extra new line

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1649

Quoted 3 lines
fs/io_uring.c +3 -0
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed) 

probably <=

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1650

Quoted 1 line
fs/io_uring.c +0 -0
 			break;

basically it checks that @target is in [last_flush, cur_seq], it can use such a comment + a note about underflows and using the modulus arithmetic, like with algebraic rings

Quoted 10 lines
fs/io_uring.c +2 -0
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
 
Signature · 1 line
Pavel Begunkov
#11 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 53 lines · Pavel Begunkov
Quoted 42 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

fs/io_uring.c +0 -0
index cb57e0360fcb..50984709879c 100644

fs/io_uring.c struct io_ring_ctx { · line 356

Quoted 4 lines
fs/io_uring.c +1 -0
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;

It looks like that "last flush" is a good direction. I think there can be problems at extremes like completing 2^32 requests at once, but should be ok in practice. Anyway better than it's now.

Quoted 2 lines

What about the first patch about overflows and cq_timeouts? I assume that problem is still there, isn't it?

Yeah it's still there I think, I just couldn't think of a good way to fix it. So I figured I would just send this one since at least it doesn't make that problem worse. Maybe could send a fix for that one later if I think of something

Quoted 3 lines

See comments below, but if it passes liburing tests, please send a patch.

will do!

Quoted 30 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1638

Quoted 10 lines
fs/io_uring.c +2 -0
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+

a nit,

if (list_empty()) return; + do {} while();

timeouts can be rare enough

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1646

Quoted 10 lines
fs/io_uring.c +2 -2
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+

extra new line

Quoted 5 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1649

Quoted 3 lines
fs/io_uring.c +3 -0
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed) 

probably <=

Won't that make it break too early though? If you submit a timeout with off = 1 when {seq == 0, last_flush == 0}, then target_seq ==
1. Then let's say there's 1 cqe added, so the timeout should trigger. Then events_needed == 1 and events_got == 1, right?

Quoted 20 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1650

Quoted 2 lines
fs/io_uring.c +0 -0
 			break;

basically it checks that @target is in [last_flush, cur_seq], it can use such a comment + a note about underflows and using the modulus arithmetic, like with algebraic rings

Quoted 10 lines
fs/io_uring.c +2 -0
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
 
Signature · 1 line
Pavel Begunkov
#12 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 8 lines · Marcelo Diop-Gonzalez
Quoted 2 lines · Pavel Begunkov

What about the first patch about overflows and cq_timeouts? I assume that problem is still there, isn't it?

Yeah it's still there I think, I just couldn't think of a good way to fix it. So I figured I would just send this one since at least it doesn't make that problem worse. Maybe could send a fix for that one later if I think of something

sounds good to me

Quoted 10 lines
Quoted 5 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1649

Quoted 3 lines
fs/io_uring.c +3 -0
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed) 

probably <=

Won't that make it break too early though? If you submit a timeout with off = 1 when {seq == 0, last_flush == 0}, then target_seq ==
1. Then let's say there's 1 cqe added, so the timeout should trigger. Then events_needed == 1 and events_got == 1, right?

Yep, you're right. I had in mind

@target in [last_flush, cur_flush], and so

(!(target - last_flush <= cur_flush - last_flush))

	break;

but that's same but reshuffled. Thanks for double checking.

Quoted 3 lines
Quoted 3 lines

basically it checks that @target is in [last_flush, cur_seq], it can use such a comment + a note about underflows and using the modulus arithmetic, like with algebraic rings

Signature · 1 line
Pavel Begunkov
#13 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

In reply to Pavel Begunkov
Quoted 64 lines · Pavel Begunkov
Quoted 42 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

fs/io_uring.c +0 -0
index cb57e0360fcb..50984709879c 100644

fs/io_uring.c struct io_ring_ctx { · line 356

Quoted 4 lines
fs/io_uring.c +1 -0
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;

It looks like that "last flush" is a good direction. I think there can be problems at extremes like completing 2^32 requests at once, but should be ok in practice. Anyway better than it's now.

What about the first patch about overflows and cq_timeouts? I assume that problem is still there, isn't it?

See comments below, but if it passes liburing tests, please send a patch.

Quoted 5 lines
fs/io_uring.c +0 -0
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
Quoted 8 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1638

Quoted 4 lines
fs/io_uring.c +2 -0
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+

a nit,

if (list_empty()) return; + do {} while();

Ah btw, so then we would have to add ->last_flush = seq in io_timeout() too? I think that should be correct but just wanna make sure that's what you meant. Because otherwise if list_empty() is true for a while without updating ->last_flush then there could be problems. Like for example if there are no timeouts for a while, and seq == 2^32-2, then we add a timeout with off == 4. If last_flush is still 0 then target-last_flush == 2, but seq - last_flush == 2^32-2

Quoted 41 lines

timeouts can be rare enough

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1646

Quoted 10 lines
fs/io_uring.c +2 -2
 	while (!list_empty(&ctx->timeout_list)) {
+		u32 events_needed, events_got;
 		struct io_kiocb *req = list_first_entry(&ctx->timeout_list,
 						struct io_kiocb, timeout.list);
 
 		if (io_is_timeout_noseq(req))
 			break;
-		if (req->timeout.target_seq != ctx->cached_cq_tail
-					- atomic_read(&ctx->cq_timeouts))
+

extra new line

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1649

Quoted 3 lines
fs/io_uring.c +3 -0
+		events_needed = req->timeout.target_seq - ctx->cq_last_tm_flush;
+		events_got = seq - ctx->cq_last_tm_flush;
+		if (events_got < events_needed) 

probably <=

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1650

Quoted 1 line
fs/io_uring.c +0 -0
 			break;

basically it checks that @target is in [last_flush, cur_seq], it can use such a comment + a note about underflows and using the modulus arithmetic, like with algebraic rings

Quoted 10 lines
fs/io_uring.c +2 -0
 		list_del_init(&req->timeout.list);
 		io_kill_timeout(req);
 	}
+
+	ctx->cq_last_tm_flush = seq;
 }
 
 static void io_commit_cqring(struct io_ring_ctx *ctx)
 
Signature · 1 line
Pavel Begunkov
#14 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

Quoted 74 lines · Marcelo Diop-Gonzalez
Quoted 64 lines · Pavel Begunkov
Quoted 42 lines · Marcelo Diop-Gonzalez
Quoted 20 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

https://www.spinics.net/lists/kernel/msg3475160.html

The idea was to replace u32 cached_cq_tail with u64 while keeping timeout offsets u32. Assuming that we won't ever hit ~2^62 inflight requests, complete all requests falling into some large enough window behind that u64 cached_cq_tail.

simplifying:

Quoted 8 lines

i64 d = target_off - ctx->u64_cq_tail
if (d <= 0 && d > -2^32)
complete_it()

Not fond of it, but at least worked at that time. You can try out this approach if you want, but would be perfect if you would find something more elegant :)

What do you think about something like this? I think it's not totally correct because it relies on having ->completion_lock in io_timeout() so that ->cq_last_tm_flushed is updated, but in case of IORING_SETUP_IOPOLL, io_iopoll_complete() doesn't take that lock, and ->uring_lock will not be held if io_timeout() is called from io_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?

fs/io_uring.c +0 -0
index cb57e0360fcb..50984709879c 100644

fs/io_uring.c struct io_ring_ctx { · line 356

Quoted 4 lines
fs/io_uring.c +1 -0
@@ -353,6 +353,7 @@ struct io_ring_ctx {
 		unsigned		cq_entries;
 		unsigned		cq_mask;
 		atomic_t		cq_timeouts;
+		unsigned		cq_last_tm_flush;

It looks like that "last flush" is a good direction. I think there can be problems at extremes like completing 2^32 requests at once, but should be ok in practice. Anyway better than it's now.

What about the first patch about overflows and cq_timeouts? I assume that problem is still there, isn't it?

See comments below, but if it passes liburing tests, please send a patch.

Quoted 5 lines
fs/io_uring.c +0 -0
 		unsigned long		cq_check_overflow;
 		struct wait_queue_head	cq_wait;
 		struct fasync_struct	*cq_fasync;
@@ -1633,19 +1634,26 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
 
Quoted 8 lines

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1638

Quoted 4 lines
fs/io_uring.c +2 -0
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
+	u32 seq = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+

a nit,

if (list_empty()) return; + do {} while();

Quoted 7 lines

Ah btw, so then we would have to add ->last_flush = seq in io_timeout() too? I think that should be correct but just wanna make sure that's what you meant. Because otherwise if list_empty() is true for a while without updating ->last_flush then there could be problems. Like for example if there are no timeouts for a while, and seq == 2^32-2, then we add a timeout with off == 4. If last_flush is still 0 then target-last_flush == 2, but seq - last_flush == 2^32-2

You've just answered your question :) You need to update it somehow, either unconditionally in commit, or in io_timeout(), or anyhow else.

btw, I like your idea to do it in io_timeout(), because it adds a timeout anyway, so makes that list_empty() fails and kind of automatically pushes all that tracking.

Signature · 1 line
Pavel Begunkov
#15 lore raw

Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired

In reply to Pavel Begunkov
Quoted 53 lines · Pavel Begunkov
Quoted 34 lines · Marcelo Diop-Gonzalez

Right now io_flush_timeouts() checks if the current number of events is equal to ->timeout.target_seq, but this will miss some timeouts if there have been more than 1 event added since the last time they were flushed (possible in io_submit_flush_completions(), for example). Fix it by recording the starting value of ->cached_cq_overflow - ->cq_timeouts instead of the target value, so that we can safely (without overflow problems) compare the number of events that have happened with the number of events needed to trigger the timeout.

---
 fs/io_uring.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)
fs/io_uring.c +4 -1
index f394bf358022..f62de0cb5fc4 100644
@@ -444,7 +444,7 @@ struct io_cancel {
 struct io_timeout {
      struct file                     *file;
      u32                             off;
-     u32                             target_seq;
+     u32                             start_seq;
      struct list_head                list;
      /* head of the link, used by linked timeouts only */
      struct io_kiocb                 *head;
@@ -1629,6 +1629,24 @@ static void __io_queue_deferred(struct io_ring_ctx *ctx)
      } while (!list_empty(&ctx->defer_list));
 }
 
+static inline u32 io_timeout_events_left(struct io_kiocb *req)
+{
+     struct io_ring_ctx *ctx = req->ctx;

fs/io_uring.c static void __io_queue_deferred(struct io_ring_ctx *ctx) · line 1644

Quoted 10 lines
fs/io_uring.c +10 -0
+     u32 events;
+
+     /*
+      * events -= req->timeout.start_seq and the comparison between
+      * ->timeout.off and events will not overflow because each time
+      * ->cq_timeouts is incremented, ->cached_cq_tail is incremented too.
+      */
+
+     events = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
+     events -= req->timeout.start_seq;

It looks to me that events before the start_seq subtraction can have got wrapped around start_seq.

e.g.
1) you submit a timeout with off=0xff...ff (start_seq=0 for convenience)

Quoted 7 lines

2) some time has passed, let @events = 0xff..ff - 1 so the timeout still waits

3) we commit 5 requests at once and call io_commit_cqring() only once for them, so we get @events == 0xff..ff - 1 + 5, i.e. 4

@events == 4 < off == 0xff...ff,

Oof, good catch... I'll try to think about it some more. Feels like there ought to
be a nice way to do it but maybe it's quite tricky :/

-Marcelo

Quoted 52 lines

so we didn't trigger out timeout even though should have

Quoted 39 lines
fs/io_uring.c +8 -5
+     if (req->timeout.off > events)
+             return req->timeout.off - events;
+     return 0;
+}
+
 static void io_flush_timeouts(struct io_ring_ctx *ctx)
 {
      while (!list_empty(&ctx->timeout_list)) {
@@ -1637,8 +1655,7 @@ static void io_flush_timeouts(struct io_ring_ctx *ctx)
 
              if (io_is_timeout_noseq(req))
                      break;
-             if (req->timeout.target_seq != ctx->cached_cq_tail
-                                     - atomic_read(&ctx->cq_timeouts))
+             if (io_timeout_events_left(req) > 0)
                      break;
 
              list_del_init(&req->timeout.list);
@@ -5785,7 +5802,6 @@ static int io_timeout(struct io_kiocb *req)
      struct io_ring_ctx *ctx = req->ctx;
      struct io_timeout_data *data = req->async_data;
      struct list_head *entry;
-     u32 tail, off = req->timeout.off;
 
      spin_lock_irq(&ctx->completion_lock);
 
@@ -5799,8 +5815,8 @@ static int io_timeout(struct io_kiocb *req)
              goto add;
      }
 
-     tail = ctx->cached_cq_tail - atomic_read(&ctx->cq_timeouts);
-     req->timeout.target_seq = tail + off;
+     req->timeout.start_seq = ctx->cached_cq_tail -
+             atomic_read(&ctx->cq_timeouts);
 
      /*
       * Insertion sort, ensuring the first entry in the list is always

fs/io_uring.c static int io_timeout(struct io_kiocb *req) · line 5835

Quoted 8 lines
fs/io_uring.c +1 -1
@@ -5813,7 +5829,7 @@ static int io_timeout(struct io_kiocb *req)
              if (io_is_timeout_noseq(nxt))
                      continue;
              /* nxt.seq is behind @tail, otherwise would've been completed */
-             if (off >= nxt->timeout.target_seq - tail)
+             if (req->timeout.off >= io_timeout_events_left(nxt))
                      break;
      }
 add:

--
Pavel Begunkov