io_uring: fix skipping of old timeout events
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
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
@@ -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
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 insideio_get_cqring().Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)fs/io_uring.c +1
-3@@ -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
-4return &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
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 insideio_get_cqring().Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)fs/io_uring.c +1
-3@@ -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
-2return &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
PATCH v2 2/2 io_uring: flush timeouts that should already have expired
In reply to Marcelo Diop-GonzalezRight 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
@@ -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
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 inio_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.Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)fs/io_uring.c +4
-1@@ -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
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 inio_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
Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)fs/io_uring.c +4
-1@@ -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_seqsubtraction can have got wrapped aroundstart_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 haveQuoted 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
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 inio_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_tailwith 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 u64cached_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
@@ -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
Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)fs/io_uring.c +4
-1@@ -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_seqsubtraction can have got wrapped aroundstart_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 haveQuoted 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
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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_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@@ -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
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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_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@@ -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
Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired
In reply to Marcelo Diop-GonzalezQuoted 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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?fs/io_uring.c +0
-0
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
-0unsigned 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
-2while (!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
-0break ;
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
-0list_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
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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?fs/io_uring.c +0
-0fs/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
-0unsigned 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
-2while (!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
-0break ;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 ringsQuoted 10 lines
fs/io_uring.c +2
-0list_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
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}, thentarget_seq==
1. Then let's say there's 1 cqe added, so the timeout should trigger. Thenevents_needed== 1 andevents_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
Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired
In reply to Pavel BegunkovQuoted 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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?fs/io_uring.c +0
-0fs/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
-0unsigned 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
-0static 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
-2while (!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
-0break ;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 ringsQuoted 10 lines
fs/io_uring.c +2
-0list_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
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 inio_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_tailwith 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 u64cached_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 ofIORING_SETUP_IOPOLL,io_iopoll_complete()doesn't take that lock, and ->uring_lock will not be held ifio_timeout()is called fromio_wq_submit_work(), but maybe could still be worth it since that was already possibly a problem?fs/io_uring.c +0
-0fs/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
-0unsigned 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
-0static 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 iflist_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. Iflast_flushis 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
Re: [PATCH v2 2/2] io_uring: flush timeouts that should already have expired
In reply to Pavel BegunkovQuoted 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 inio_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.Signed-off-by Marcelo Diop-Gonzalez <[email protected]>--- fs/io_uring.c | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)fs/io_uring.c +4
-1@@ -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_seqsubtraction can have got wrapped aroundstart_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