io-wq: handle hashed writes in chains
Jens Axboe
maintainerPATCH v2 1/1 io-wq: handle hashed writes in chains
We always punt async buffered writes to an io-wq helper, as the core kernel does not have IOCB_NOWAIT support for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.
When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
---
Changes:
- Don't overwrite passed back work
fs/io-wq.c +69 -16
@@ -380,32 +380,65 @@ static inline unsigned int io_get_work_hash(struct io_wq_work *work)return work->flags >>IO_WQ_HASH_SHIFT ; } -static struct io_wq_work *io_get_next_work (struct io_wqe *wqe) +/* +* Returns the next work item to process, if any. For hashed work that hash +* to the same key, we can't process N+1 before N is done. To make the +* processing more efficient, return N+1 and later identically hashed work +* in the passed in list. This avoids repeated hammering on the wqe lock for, +* as the caller can just process items in the on-stack list. +*/ +static struct io_wq_work *io_get_next_work (struct io_wqe *wqe, +struct io_wq_work_list *list) __must_hold(wqe->lock) { -struct io_wq_work_node *node, *prev; -struct io_wq_work *work; -unsigned int hash; +struct io_wq_work *ret =NULL ; -wq_list_for_each (node, prev, &wqe->work_list) { - work = container_of(node, struct io_wq_work, list); +do { +unsigned int new_hash, hash; +struct io_wq_work *work; + + work = wq_first_entry(&wqe->work_list, struct io_wq_work, list); +if (!work) +break ;/* not hashed, can run anytime */ if (!io_wq_is_hashed (work)) { -wq_node_del (&wqe->work_list, node, prev); -return work; +/* already have hashed work, let new worker get this */ +if (ret) { +struct io_wqe_acct *acct; + +/* get new worker for unhashed, if none now */ + acct =io_work_get_acct (wqe, work); +if (!atomic_read (&acct->nr_running)) +io_wqe_wake_worker (wqe, acct); +break ; + } +wq_node_del (&wqe->work_list, &work->list); + ret = work; +break ; }/* hashed, can run if not already running */ - hash =io_get_work_hash (work); -if (!(wqe->hash_map &BIT (hash))) { + new_hash =io_get_work_hash (work); +if (wqe->hash_map &BIT (new_hash)) +break ; + +if (!ret) { + hash = new_hash; wqe->hash_map |=BIT (hash); -wq_node_del (&wqe->work_list, node, prev); -return work; + }else if (hash != new_hash) { +break ; } - } -return NULL ; +wq_node_del (&wqe->work_list, &work->list); +/* return first node, add subsequent same hash to the list */ +if (!ret) + ret = work; +else +wq_list_add_tail (&work->list, list); + }while (1 ); + +return ret; }static void io_wq_switch_mm (struct io_worker *worker,struct io_wq_work *work)
@@ -481,6 +514,7 @@ static void io_wqe_enqueue(struct io_wqe *wqe, struct io_wq_work *work);static void io_worker_handle_work (struct io_worker *worker) __releases(wqe->lock) { +struct io_wq_work_list list = { .first =NULL , .last =NULL };struct io_wqe *wqe = worker->wqe;struct io_wq *wq = wqe->wq;
@@ -495,7 +529,7 @@ static void io_worker_handle_work(struct io_worker *worker)* can't make progress, any work completion or insertion will * clear the stalled flag. */ - work =io_get_next_work (wqe); + work =io_get_next_work (wqe, &list);if (work)__io_worker_busy (wqe, worker, work);else if (!wq_list_empty (&wqe->work_list))
@@ -504,6 +538,7 @@ static void io_worker_handle_work(struct io_worker *worker)spin_unlock_irq (&wqe->lock);if (!work)break ; +got_work:io_assign_current_work (worker, work);/* handle a whole dependent link */
@@ -530,6 +565,24 @@ static void io_worker_handle_work(struct io_worker *worker) work =NULL ; }if (hash !=-1U ) { +/* +* If the local list is non-empty, then we +* have work that hashed to the same key. +* No need for a lock round-trip, or fiddling +* the the free/busy state of the worker, or +* clearing the hashed state. Just process the +* next one. +*/ +if (!work) { + work =wq_first_entry (&list, + struct io_wq_work, + list); +if (work) { +wq_node_del (&list, &work->list); + goto got_work; + } + } +spin_lock_irq (&wqe->lock); wqe->hash_map &= ~BIT_ULL (hash); wqe->flags &= ~IO_WQE_FLAG_STALLED ;
@@ -910,7 +963,7 @@ static enum io_wq_cancel io_wqe_cancel_work(struct io_wqe *wqe, work = container_of(node, struct io_wq_work, list);if (match->fn (work, match->data)) { -wq_node_del (&wqe->work_list, node, prev); +__wq_node_del (&wqe->work_list, node, prev); found = true;break ; }
fs/io-wq.h +18 -3
@@ -40,9 +40,9 @@ static inline void wq_list_add_tail(struct io_wq_work_node *node, } } -static inline void wq_node_del (struct io_wq_work_list *list, -struct io_wq_work_node *node, -struct io_wq_work_node *prev) +static inline void __wq_node_del (struct io_wq_work_list *list, +struct io_wq_work_node *node, +struct io_wq_work_node *prev) {if (node == list->first)WRITE_ONCE (list->first, node->next);
@@ -53,6 +53,21 @@ static inline void wq_node_del(struct io_wq_work_list *list, node->next =NULL ; } + +static inline void wq_node_del (struct io_wq_work_list *list, +struct io_wq_work_node *node) +{ +__wq_node_del (list, node,NULL ); +} + +#define wq_first_entry (list, type, member) \ +({ \ + struct io_wq_work *__work = NULL; \ + if (!wq_list_empty((list))) \ + __work = container_of((list)->first, type, member); \ + __work; \ +}) +#define wq_list_for_each (pos, prv, head) \ for (pos = (head)->first, prv = NULL; pos; prv = pos, pos = (pos)->next)
Signature · 1 line
Jens Axboe
Quoted 70 lines · Jens Axboe
We always punt async buffered writes to an io-wq helper, as the core kernel does not have
IOCB_NOWAITsupport for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
Signed-off-by Jens Axboe <[email protected]>---
Changes:
- Don't overwrite passed back workfs/io-wq.c +28
-8@@ -380,32 +380,65 @@ static inline unsigned int io_get_work_hash(struct io_wq_work *work)return work->flags >>IO_WQ_HASH_SHIFT ; } -static struct io_wq_work *io_get_next_work (struct io_wqe *wqe) +/* +* Returns the next work item to process, if any. For hashed work that hash +* to the same key, we can't process N+1 before N is done. To make the +* processing more efficient, return N+1 and later identically hashed work +* in the passed in list. This avoids repeated hammering on the wqe lock for, +* as the caller can just process items in the on-stack list. +*/ +static struct io_wq_work *io_get_next_work (struct io_wqe *wqe, +struct io_wq_work_list *list) __must_hold(wqe->lock) { -struct io_wq_work_node *node, *prev; -struct io_wq_work *work; -unsigned int hash; +struct io_wq_work *ret =NULL ; -wq_list_for_each (node, prev, &wqe->work_list) { - work = container_of(node, struct io_wq_work, list); + do { + unsigned int new_hash, hash; + struct io_wq_work *work; + + work = wq_first_entry(&wqe->work_list, struct io_wq_work, list); + if (!work) + break; /* not hashed, can run anytime */ if (!io_wq_is_hashed(work)) { -wq_node_del (&wqe->work_list, node, prev); -return work; + /* already have hashed work, let new worker get this */ + if (ret) { + struct io_wqe_acct *acct; + + /* get new worker for unhashed, if none now */ + acct = io_work_get_acct(wqe, work); + if (!atomic_read(&acct->nr_running)) + io_wqe_wake_worker(wqe, acct); + break; + } + wq_node_del(&wqe->work_list, &work->list);
fs/io-wq.c static inline unsigned int io_get_work_hash(struct io_wq_work *work) · line 424
Quoted 10 lines
fs/io-wq.c +5
-2+ ret = work; +break ; }/* hashed, can run if not already running */ - hash =io_get_work_hash (work); -if (!(wqe->hash_map &BIT (hash))) { + new_hash =io_get_work_hash (work); +if (wqe->hash_map &BIT (new_hash)) +break ;
This will always break for subsequent hashed, as the @hash_map bit is set. Isn't it? And anyway, it seems it doesn't optimise not-contiguous same-hashed requests, e.g.
0: Link(hash=0)
1: Link(hash=1)
2: Link(hash=0)
3: Link(not_hashed)
4: Link(hash=0)
...
Quoted 55 lines
fs/io-wq.c +19
-5+ +if (!ret) { + hash = new_hash; wqe->hash_map |=BIT (hash); -wq_node_del (&wqe->work_list, node, prev); -return work; + }else if (hash != new_hash) { +break ; } - } -return NULL ; +wq_node_del (&wqe->work_list, &work->list); +/* return first node, add subsequent same hash to the list */ +if (!ret) + ret = work; +else +wq_list_add_tail (&work->list, list); + }while (1 ); + +return ret; }static void io_wq_switch_mm (struct io_worker *worker,struct io_wq_work *work)@@ -481,6 +514,7 @@ static void io_wqe_enqueue(struct io_wqe *wqe, struct io_wq_work *work);static void io_worker_handle_work (struct io_worker *worker) __releases(wqe->lock) { +struct io_wq_work_list list = { .first =NULL , .last =NULL };struct io_wqe *wqe = worker->wqe;struct io_wq *wq = wqe->wq;@@ -495,7 +529,7 @@ static void io_worker_handle_work(struct io_worker *worker)* can't make progress, any work completion or insertion will * clear the stalled flag. */ - work =io_get_next_work (wqe); + work =io_get_next_work (wqe, &list);if (work)__io_worker_busy (wqe, worker, work);else if (!wq_list_empty (&wqe->work_list))@@ -504,6 +538,7 @@ static void io_worker_handle_work(struct io_worker *worker)spin_unlock_irq (&wqe->lock);if (!work)break ; +got_work:io_assign_current_work (worker, work);/* handle a whole dependent link */ @@ -530,6 +565,24 @@ static void io_worker_handle_work(struct io_worker *worker) work =NULL ; }if (hash !=-1U ) { +/* +* If the local list is non-empty, then we
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 579
Quoted 10 lines
fs/io-wq.c +10
-0+* have work that hashed to the same key. +* No need for a lock round-trip, or fiddling +* the the free/busy state of the worker, or +* clearing the hashed state. Just process the +* next one. +*/ +if (!work) { + work =wq_first_entry (&list, + struct io_wq_work, + list);
Wouldn't it just drop a linked request? Probably works because of the comment above.
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 581
Quoted 2 lines
fs/io-wq.c +2
-0+if (work) { +wq_node_del (&list, &work->list);
There is a bug, apparently from one of my commits, where it do io_assign_current_work() but then re-enqueue and reassign new work, though there is a gap for cancel to happen, which would screw everything up.
I'll send a patch, so it'd be more clear. However, this is a good point to look after for this as well.
Quoted 56 lines
fs/io-wq.c +5
-1+ goto got_work; + } + } +spin_lock_irq (&wqe->lock); wqe->hash_map &= ~BIT_ULL (hash); wqe->flags &= ~IO_WQE_FLAG_STALLED ;@@ -910,7 +963,7 @@ static enum io_wq_cancel io_wqe_cancel_work(struct io_wqe *wqe, work = container_of(node, struct io_wq_work, list);if (match->fn (work, match->data)) { -wq_node_del (&wqe->work_list, node, prev); +__wq_node_del (&wqe->work_list, node, prev); found = true;break ; }fs/io-wq.h +18
-3@@ -40,9 +40,9 @@ static inline void wq_list_add_tail(struct io_wq_work_node *node, } } -static inline void wq_node_del (struct io_wq_work_list *list, -struct io_wq_work_node *node, -struct io_wq_work_node *prev) +static inline void __wq_node_del (struct io_wq_work_list *list, +struct io_wq_work_node *node, +struct io_wq_work_node *prev) {if (node == list->first)WRITE_ONCE (list->first, node->next);@@ -53,6 +53,21 @@ static inline void wq_node_del(struct io_wq_work_list *list, node->next =NULL ; } + +static inline void wq_node_del (struct io_wq_work_list *list, +struct io_wq_work_node *node) +{ +__wq_node_del (list, node,NULL ); +} + +#define wq_first_entry (list, type, member) \ +({ \ + struct io_wq_work *__work = NULL; \ + if (!wq_list_empty((list))) \ + __work = container_of((list)->first, type, member); \ + __work; \ +}) +#define wq_list_for_each (pos, prv, head) \ for (pos = (head)->first, prv = NULL; pos; prv = pos, pos = (pos)->next)
Signature · 1 line
Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Jens Axboe
We always punt async buffered writes to an io-wq helper, as the core kernel does not have
IOCB_NOWAITsupport for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.
Quoted 3 lines
Quoted 3 lines
When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
I have an idea, how to do it a bit better. Let me try it.
Signature · 1 line
Pavel Begunkov
Jens Axboe
maintainerQuoted 10 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Jens Axboe
We always punt async buffered writes to an io-wq helper, as the core kernel does not have
IOCB_NOWAITsupport for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
I have an idea, how to do it a bit better. Let me try it.
Sure, go ahead!
Signature · 1 line
Jens Axboe
Quoted 10 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Jens Axboe
We always punt async buffered writes to an io-wq helper, as the core kernel does not have
IOCB_NOWAITsupport for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
I have an idea, how to do it a bit better. Let me try it.
The diff below is buggy (Ooopses somewhere in blk-mq for read-write.c:read_poll_link), I'll double check it on a fresh head.
The idea is to keep same-hashed works continuously in @work_list, so they can be spliced in one go. For each hash bucket, I keep last added work
- on enqueue, it adds a work after the last one
- on dequeue it splices [first, last]. Where @first is the current one, because of how we traverse @work_list.
It throws a bit of extra memory, but
- removes extra looping
- and also takes all hashed requests, but not only sequentially submitted
e.g. for the following submission sequence, it will take all (hash=0) requests. REQ(hash=0)
REQ(hash=1)
REQ(hash=0)REQ()
REQ(hash=0)
...
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
--- fs/io-wq.c | 49 +++++++++++++++++++++++++++++++++++++++++++------ fs/io-wq.h | 34 +++++++++++++++++++++++++++------- 2 files changed, 70 insertions(+), 13 deletions(-)
fs/io-wq.c +22 -5
@@ -69,6 +69,8 @@ struct io_worker {#define IO_WQ_HASH_ORDER 5#endif +#define IO_WQ_HASH_NR_BUCKETS (1u << IO_WQ_HASH_ORDER) +struct io_wqe_acct {unsigned nr_workers;unsigned max_workers;
@@ -98,6 +100,7 @@ struct io_wqe {struct list_head all_list;struct io_wq *wq; +struct io_wq_work *last_hashed[IO_WQ_HASH_NR_BUCKETS ]; };/*
@@ -400,7 +403,9 @@ static struct io_wq_work *io_get_next_work(struct io_wqe *wqe) hash =io_get_work_hash (work);if (!(wqe->hash_map &BIT (hash))) { wqe->hash_map |=BIT (hash); -wq_node_del (&wqe->work_list, node, prev); +wq_del_node_range (&wqe->work_list, + &wqe->last_hashed[hash]->list, prev); + wqe->last_hashed[hash] =NULL ;return work; } }
@@ -508,7 +513,11 @@ static void io_worker_handle_work(struct io_worker *worker)/* handle a whole dependent link */ do { - struct io_wq_work *old_work; + struct io_wq_work *old_work, *next_hashed = NULL; + + if (work->list.next) + next_hashed = container_of(work->list.next, + struct io_wq_work, list); io_impersonate_work(worker, work); /*
@@ -523,12 +532,20 @@ static void io_worker_handle_work(struct io_worker *worker) work->func (&work); work = (old_work == work) ?NULL : work; - assign_work = work; -if (work &&io_wq_is_hashed (work)) - assign_work =NULL ; + assign_work = next_hashed; +if (!next_hashed && work && !io_wq_is_hashed (work)) + assign_work = work; +io_assign_current_work (worker, assign_work); wq->free_work (old_work); +if (next_hashed) { +if (work) +io_wqe_enqueue (wqe, work); + work = next_hashed; +continue ; + } +if (work && !assign_work) {io_wqe_enqueue (wqe, work); work =NULL ;
@@ -776,6 +793,26 @@ static void io_run_cancel(struct io_wq_work *work, struct
io_wqe *wqe)
} while (work);
}
+static void io_wqe_insert_work(struct io_wqe *wqe, struct io_wq_work *work) +{
+ int hash;
+ struct io_wq_work *last_hashed;
+
+ if (!io_wq_is_hashed(work)) {
+append:
+ wq_list_add_tail(&work->list, &wqe->work_list);
+ return;
+ }
+
+ hash = io_get_work_hash(work);
+ last_hashed = wqe->last_hashed[hash];
+ wqe->last_hashed[hash] = work;
+ if (!last_hashed)
+ goto append;
+
+ wq_list_add_after(&work->list, &last_hashed->list, &wqe->work_list);
+}
+
static void io_wqe_enqueue(struct io_wqe *wqe, struct io_wq_work *work) {
struct io_wqe_acct *acct = io_work_get_acct(wqe, work);
@@ -795,7 +832,7 @@ static void io_wqe_enqueue(struct io_wqe *wqe, struct io_wq_work *work)
work_flags = work->flags; spin_lock_irqsave(&wqe->lock, flags);
- wq_list_add_tail(&work->list, &wqe->work_list);
+ io_wqe_insert_work(wqe, work);
wqe->flags &= ~IO_WQE_FLAG_STALLED; spin_unlock_irqrestore(&wqe->lock, flags);
fs/io-wq.h +0 -0
@@ -40,17 +40,37 @@ static inline void wq_list_add_tail(struct io_wq_work_node
*node,
}
}
+static inline void wq_list_add_after(struct io_wq_work_node *node,
+ struct io_wq_work_node *pos,
+ struct io_wq_work_list *list)
+{
+ struct io_wq_work_node *next = pos->next;
+
+ pos->next = node;
+ node->next = next;
+ if (!next)
+ list->last = node;
+}
+
+static inline void wq_del_node_range(struct io_wq_work_list *list,
+ struct io_wq_work_node *last,
+ struct io_wq_work_node *prev)
+{
+ if (!prev)
+ WRITE_ONCE(list->first, last->next);
+ else
+ prev->next = last->next;
+
+ if (last == list->last)
+ list->last = prev;
+ last->next = NULL;
+}
+
static inline void wq_node_del(struct io_wq_work_list *list,
struct io_wq_work_node *node, struct io_wq_work_node *prev)
{
- if (node == list->first)
- WRITE_ONCE(list->first, node->next);
- if (node == list->last)
- list->last = prev;
- if (prev)
- prev->next = node->next;
- node->next = NULL;
+ wq_del_node_range(list, node, prev);
}
#define wq_list_for_each(pos, prv, head) \
Signature · 1 line
2.24.0
Jens Axboe
maintainerQuoted 11 lines · Pavel Begunkov
Quoted 10 lines · Pavel Begunkov
Quoted 9 lines · Pavel Begunkov
Quoted 8 lines · Jens Axboe
We always punt async buffered writes to an io-wq helper, as the core kernel does not have
IOCB_NOWAITsupport for that. Most buffered async writes complete very quickly, as it's just a copy operation. This means that doing multiple locking roundtrips on the shared wqe lock for each buffered write is wasteful. Additionally, buffered writes are hashed work items, which means that any buffered write to a given file is serialized.
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
When looking for a new work item, build a chain of identicaly hashed work items, and then hand back that batch. Until the batch is done, the caller doesn't have to synchronize with the wqe or worker locks again.
I have an idea, how to do it a bit better. Let me try it.
The diff below is buggy (Ooopses somewhere in blk-mq for read-write.c:read_poll_link), I'll double check it on a fresh head.
Are you running for-5.7/io_uring merged with master? If not you're missing:
commit f1d96a8fcbbbb22d4fbc1d69eaaa678bbb0ff6e2
Author: Pavel Begunkov <[email protected]> Date: Fri Mar 13 22:29:14 2020 +0300
io_uring: NULL-deref for IOSQE_{ASYNC,DRAIN}which is what I ran into as well last week...
Quoted 26 lines
The idea is to keep same-hashed works continuously in @work_list, so they can be spliced in one go. For each hash bucket, I keep last added work
- on enqueue, it adds a work after the last one
- on dequeue it splices [first, last]. Where @first is the current one, becauseof how we traverse @work_list.
It throws a bit of extra memory, but
- removes extra looping
- and also takes all hashed requests, but not only sequentially submittede.g. for the following submission sequence, it will take all (hash=0) requests.
REQ(hash=0)
REQ(hash=1)
REQ(hash=0)REQ()
REQ(hash=0)
...
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
The extra memory isn't a bit deal, it's very minor. My main concern would be fairness, since we'd then be grabbing non-contig hashed chunks, before we did not. May not be a concern as long as we ensure the non-hasned (and differently hashed) work can proceed in parallel. For my end, I deliberately added:
+ /* already have hashed work, let new worker get this */
+ if (ret) {
+ struct io_wqe_acct *acct;
+
+ /* get new worker for unhashed, if none now */
+ acct = io_work_get_acct(wqe, work);
+ if (!atomic_read(&acct->nr_running))
+ io_wqe_wake_worker(wqe, acct);
+ break;
+ }
to try and improve that.
I'll run a quick test with yours.
Signature · 1 line
Jens Axboe
Jens Axboe
maintainerQuoted 2 lines · Jens Axboe
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
One quick guess would be that you're wanting to use both work->list and work->data, the latter is used by links which is where you are crashing. Didn't check your list management yet so don't know if that's the case, but if you're still on the list (or manipulating it after), then that would be a bug.
Signature · 1 line
Jens Axboe
Jens Axboe
maintainerQuoted 9 lines · Jens Axboe
Quoted 2 lines · Jens Axboe
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
One quick guess would be that you're wanting to use both
work->listandwork->data, the latter is used by links which is where you are crashing. Didn't check your list management yet so don't know if that's the case, but if you're still on the list (or manipulating it after), then that would be a bug.
IOW, by the time you do work->func(&work), the item must be off the list. Does indeed look like that's exactly the bug you have.
Signature · 1 line
Jens Axboe
Quoted 5 lines · Jens Axboe
Quoted 4 lines · Jens Axboe
Quoted 2 lines · Jens Axboe
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
Quoted 9 lines
Quoted 5 lines
One quick guess would be that you're wanting to use both
work->listandwork->data, the latter is used by links which is where you are crashing. Didn't check your list management yet so don't know if that's the case, but if you're still on the list (or manipulating it after), then that would be a bug.IOW, by the time you do
work->func(&work), the item must be off the list. Does indeed look like that's exactly the bug you have.
Good guess. I made sure to grab next before ->func(), see next_hashed. And it's not in @work_list, because io_get_next_work() removes it. However, somebody may expect it to be NULL or something. Thanks! I'll check it
Signature · 1 line
Pavel Begunkov
Quoted 12 lines · Pavel Begunkov
Quoted 11 lines · Jens Axboe
Quoted 9 lines · Jens Axboe
Quoted 2 lines · Jens Axboe
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
One quick guess would be that you're wanting to use both
work->listandwork->data, the latter is used by links which is where you are crashing. Didn't check your list management yet so don't know if that's the case, but if you're still on the list (or manipulating it after), then that would be a bug.
Quoted 7 lines
Quoted 3 lines
IOW, by the time you do
work->func(&work), the item must be off the list. Does indeed look like that's exactly the bug you have.Good guess. I made sure to grab next before ->func(), see
next_hashed. And it's not in @work_list, becauseio_get_next_work()removes it. However, somebody may expect it to be NULL or something. Thanks! I'll check it
You're right. Re-enqueue corrupts ->data, so should be fixed for previous patches as well. I'll send it
Signature · 1 line
Pavel Begunkov
Quoted 17 lines · Pavel Begunkov
Quoted 16 lines · Pavel Begunkov
Quoted 14 lines · Jens Axboe
Quoted 9 lines · Jens Axboe
Quoted 2 lines · Jens Axboe
Quoted 2 lines
Please, tell if you see a hole in the concept. And as said, there is still a bug somewhere.
One quick guess would be that you're wanting to use both
work->listandwork->data, the latter is used by links which is where you are crashing. Didn't check your list management yet so don't know if that's the case, but if you're still on the list (or manipulating it after), then that would be a bug.IOW, by the time you do
work->func(&work), the item must be off the list. Does indeed look like that's exactly the bug you have.
Quoted 7 lines
Quoted 3 lines
Good guess. I made sure to grab next before ->func(), see
next_hashed. And it's not in @work_list, becauseio_get_next_work()removes it. However, somebody may expect it to be NULL or something. Thanks! I'll check itYou're right. Re-enqueue corrupts ->data, so should be fixed for previous patches as well. I'll send it
And the diff works fine if put on top of the fix!
Signature · 1 line
Pavel Begunkov
Quoted 7 lines · Jens Axboe
commit
f1d96a8fcbbbb22d4fbc1d69eaaa678bbb0ff6e2Author: Pavel Begunkov <[email protected]> Date: Fri Mar 13 22:29:14 2020 +0300io_uring: NULL-deref for IOSQE_{ASYNC,DRAIN}which is what I ran into as well last week...
I picked it before testing
Quoted 5 lines
The extra memory isn't a bit deal, it's very minor. My main concern would be fairness, since we'd then be grabbing non-contig hashed chunks, before we did not. May not be a concern as long as we ensure the non-hasned (and differently hashed) work can proceed in parallel. For my end, I deliberately added:
Don't think it's really a problem, all ordering/scheduling is up to users (i.e. io_uring), and it can't infinitely postpone a work, because it's processing spliced requests without taking more, even if new ones hash to the same bit.
Quoted 11 lines
(quoted diff) +10
-0+ /* already have hashed work, let new worker get this */ + if (ret) { + struct io_wqe_acct *acct; + + /* get new worker for unhashed, if none now */ + acct = io_work_get_acct(wqe, work); + if (!atomic_read(&acct->nr_running)) + io_wqe_wake_worker(wqe, acct); + break; + }
Quoted 1 line
to try and improve that.
Is there performance problems with your patch without this chunk? I may see another problem with yours, I need to think it through.
Quoted 2 lines
I'll run a quick test with yours.
Signature · 1 line
Pavel Begunkov
Jens Axboe
maintainerQuoted 17 lines · Pavel Begunkov
Quoted 7 lines · Jens Axboe
commit
f1d96a8fcbbbb22d4fbc1d69eaaa678bbb0ff6e2Author: Pavel Begunkov <[email protected]> Date: Fri Mar 13 22:29:14 2020 +0300io_uring: NULL-deref for IOSQE_{ASYNC,DRAIN}which is what I ran into as well last week...
I picked it before testing
Quoted 5 lines
The extra memory isn't a bit deal, it's very minor. My main concern would be fairness, since we'd then be grabbing non-contig hashed chunks, before we did not. May not be a concern as long as we ensure the non-hasned (and differently hashed) work can proceed in parallel. For my end, I deliberately added:
Quoted 4 lines
Don't think it's really a problem, all ordering/scheduling is up to users (i.e.
io_uring), and it can't infinitely postpone a work, because it's processing spliced requests without taking more, even if new ones hash to the same bit.
I don't disagree with you, just wanted to bring it up!
Quoted 11 lines
Quoted 11 lines
(quoted diff) +10
-0+ /* already have hashed work, let new worker get this */ + if (ret) { + struct io_wqe_acct *acct; + + /* get new worker for unhashed, if none now */ + acct = io_work_get_acct(wqe, work); + if (!atomic_read(&acct->nr_running)) + io_wqe_wake_worker(wqe, acct); + break; + }
Quoted 4 lines
Quoted 1 line
to try and improve that.
Is there performance problems with your patch without this chunk? I may see another problem with yours, I need to think it through.
No, and in fact it probably should be a separate thing, but I kind of like your approach so not moving forward with mine. I do think it's worth looking into separately, as there's no reason why we can't wake a non-hashed worker if we're just doing hashed work from the existing thread. If that thread is just doing copies and not blocking, the unhashed (or next hashed) work is just sitting idle while it could be running instead.
Hence I added that hunk, to kick a new worker to proceed in parallel.
Signature · 1 line
Jens Axboe
Quoted 18 lines · Jens Axboe
Quoted 17 lines · Pavel Begunkov
Quoted 7 lines · Jens Axboe
commit
f1d96a8fcbbbb22d4fbc1d69eaaa678bbb0ff6e2Author: Pavel Begunkov <[email protected]> Date: Fri Mar 13 22:29:14 2020 +0300io_uring: NULL-deref for IOSQE_{ASYNC,DRAIN}which is what I ran into as well last week...
I picked it before testing
Quoted 5 lines
The extra memory isn't a bit deal, it's very minor. My main concern would be fairness, since we'd then be grabbing non-contig hashed chunks, before we did not. May not be a concern as long as we ensure the non-hasned (and differently hashed) work can proceed in parallel. For my end, I deliberately added:
Quoted 6 lines
Quoted 4 lines
Don't think it's really a problem, all ordering/scheduling is up to users (i.e.
io_uring), and it can't infinitely postpone a work, because it's processing spliced requests without taking more, even if new ones hash to the same bit.I don't disagree with you, just wanted to bring it up!
Sure, there is a lot to think about. E.g. I don't like this reenqueueing, and if all other thread have enough work to do, then it can avoided, but don't want to over-complicate.
Quoted 17 lines
Quoted 12 lines
Quoted 12 lines
(quoted diff) +10
-0+ /* already have hashed work, let new worker get this */ + if (ret) { + struct io_wqe_acct *acct; + + /* get new worker for unhashed, if none now */ + acct = io_work_get_acct(wqe, work); + if (!atomic_read(&acct->nr_running)) + io_wqe_wake_worker(wqe, acct); + break; + }Quoted 4 lines
Quoted 1 line
to try and improve that.
Is there performance problems with your patch without this chunk? I may see another problem with yours, I need to think it through.
Quoted 7 lines
No, and in fact it probably should be a separate thing, but I kind of like your approach so not moving forward with mine. I do think it's worth looking into separately, as there's no reason why we can't wake a non-hashed worker if we're just doing hashed work from the existing thread. If that thread is just doing copies and not blocking, the unhashed (or next hashed) work is just sitting idle while it could be running instead.
Then, I'll clean the diff, hopefully soon. Could I steal parts of your patch description?
Quoted 2 lines
Hence I added that hunk, to kick a new worker to proceed in parallel.
It seems, I need to take a closer look at this accounting in general.
Signature · 1 line
Pavel Begunkov
Jens Axboe
maintainerQuoted 10 lines · Pavel Begunkov
Quoted 7 lines
No, and in fact it probably should be a separate thing, but I kind of like your approach so not moving forward with mine. I do think it's worth looking into separately, as there's no reason why we can't wake a non-hashed worker if we're just doing hashed work from the existing thread. If that thread is just doing copies and not blocking, the unhashed (or next hashed) work is just sitting idle while it could be running instead.
Then, I'll clean the diff, hopefully soon. Could I steal parts of your patch description?
Of course, go ahead.
Quoted 3 lines
Quoted 1 line
Hence I added that hunk, to kick a new worker to proceed in parallel.
It seems, I need to take a closer look at this accounting in general.
Agree, I think we have some room for improvement there.
Signature · 1 line
Jens Axboe
Jens Axboe
maintainerQuoted 30 lines · Pavel Begunkov
Quoted 15 lines
fs/io-wq.c +11
-2/* not hashed, can run anytime */ if (!io_wq_is_hashed (work)) { -wq_node_del (&wqe->work_list, node, prev); -return work; +/* already have hashed work, let new worker get this */ +if (ret) { +struct io_wqe_acct *acct; + +/* get new worker for unhashed, if none now */ + acct =io_work_get_acct (wqe, work); +if (!atomic_read (&acct->nr_running)) +io_wqe_wake_worker (wqe, acct); +break ; + } +wq_node_del (&wqe->work_list, &work->list);fs/io-wq.c static inline unsigned int io_get_work_hash(struct io_wq_work *work) · line 424
Quoted 10 lines
fs/io-wq.c +5
-2+ ret = work; +break ; }/* hashed, can run if not already running */ - hash =io_get_work_hash (work); -if (!(wqe->hash_map &BIT (hash))) { + new_hash =io_get_work_hash (work); +if (wqe->hash_map &BIT (new_hash)) +break ;This will always break for subsequent hashed, as the @hash_map bit is set. Isn't it? And anyway, it seems it doesn't optimise not-contiguous same-hashed requests, e.g.
Quoted 6 lines
0: Link(hash=0)
1: Link(hash=1)
2: Link(hash=0)
3:Link(not_hashed)
4: Link(hash=0)
...
Yeah, I think I shuffled a bit too much there, should only break on that if hash != new_hash. Will fix!
Quoted 11 lines
Quoted 11 lines
fs/io-wq.c +7
-0@@ -530,6 +565,24 @@ static void io_worker_handle_work(struct io_worker *worker) work =NULL ; }if (hash !=-1U ) { +/* +* If the local list is non-empty, then we +* have work that hashed to the same key. +* No need for a lock round-trip, or fiddling +* the the free/busy state of the worker, or +* clearing the hashed state. Just process the +* next one.
Quoted 8 lines
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 579
Quoted 5 lines
fs/io-wq.c +5
-0+*/ +if (!work) { + work =wq_first_entry (&list, + struct io_wq_work, + list);Wouldn't it just drop a linked request? Probably works because of the comment above.
Only drops if if we always override 'work', if it's already set we use 'work' and don't grab from the list. So that should work for links.
Quoted 10 lines
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 581
Quoted 2 lines
fs/io-wq.c +2
-0+if (work) { +wq_node_del (&list, &work->list);There is a bug, apparently from one of my commits, where it do
io_assign_current_work()but then re-enqueue and reassign new work, though there is a gap for cancel to happen, which would screw everything up.I'll send a patch, so it'd be more clear. However, this is a good point to look after for this as well.
Saw it, I'll apply when you have the Fixes line. I'll respin this one after.
Signature · 1 line
Jens Axboe
Quoted 9 lines · Jens Axboe
Quoted 8 lines
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 579
Quoted 5 lines
fs/io-wq.c +5
-0+*/ +if (!work) { + work =wq_first_entry (&list, + struct io_wq_work, + list);Wouldn't it just drop a linked request? Probably works because of the comment above.
Quoted 3 lines
Only drops if if we always override 'work', if it's already set we use 'work' and don't grab from the list. So that should work for links.
Oh, right, the NULL check is just above.
Quoted 14 lines
Quoted 10 lines
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 581
Quoted 2 lines
fs/io-wq.c +2
-0+if (work) { +wq_node_del (&list, &work->list);There is a bug, apparently from one of my commits, where it do
io_assign_current_work()but then re-enqueue and reassign new work, though there is a gap for cancel to happen, which would screw everything up.I'll send a patch, so it'd be more clear. However, this is a good point to look after for this as well.
Saw it, I'll apply when you have the Fixes line. I'll respin this one after.
Signature · 1 line
Pavel Begunkov
Quoted 12 lines · Jens Axboe
fs/io-wq.c +11
-0if (hash !=-1U ) { +/* +* If the local list is non-empty, then we +* have work that hashed to the same key. +* No need for a lock round-trip, or fiddling +* the the free/busy state of the worker, or +* clearing the hashed state. Just process the +* next one. +*/ +if (!work) { + work = wq_first_entry(&list, + struct io_wq_work,
fs/io-wq.c static void io_worker_handle_work(struct io_worker *worker) · line 588
Quoted 10 lines
fs/io-wq.c +7
-0+ list); +if (work) { +wq_node_del (&list, &work->list); + goto got_work; + } + } +spin_lock_irq (&wqe->lock); wqe->hash_map &= ~BIT_ULL (hash); wqe->flags &= ~IO_WQE_FLAG_STALLED ;
Let's have an example, where "->" is a link
req0(hash=0) -> req1(not_hashed)
req2(hash=0)
1. it grabs @req0 (@work=@req0) and @req1 (in the local @list)
2. it do @req0->func(), sets @work=@req1 and goes to the hash updating code (see above).
3. ```if (!work)``` check fails, and it clears @hash_map, even though there is one of the same hash in the list. It messes up @hash_map accounting, but probably even can continue working fine.
4. Next, it goes for the second iteration (work == req1), do ->func(). Then checks @hash, which is -1 for non-hashed req1, and exits leaving req2 in the @list.
Can miss something by looking at diff only, but there are 2 potential points to fix.
BTW, yours patch executes all linked requests first and then goes to the next hashed. Mine do hashed first, and re-enqueue linked requests. The downside in my version is the extra re-enqueue. And your approach can't do some cases in parallel, e.g. the following is purely sequential:
req0(hash0) -> ... long link ->
req1(hash0) -> ... long link ->
req2(hash0) -> ... long link ->
req3(hash0) -> ... long link ->
It's not hard to convert, though
Signature · 1 line
Pavel Begunkov