Re: [POC RFC 0/3] support graph like dependent sqes

[Pavel Begunkov <asml.silence@gmail.com>]

On 12/14/21 05:57, Hao Xu wrote:
> This is just a proof of concept which is incompleted, send it early for
> thoughts and suggestions.
> 
> We already have IOSQE_IO_LINK to describe linear dependency
> relationship sqes. While this patchset provides a new feature to
> support DAG dependency. For instance, 4 sqes have a relationship
> as below:
>        --> 2 --
>       /        \
> 1 ---          ---> 4
>       \        /
>        --> 3 --
> IOSQE_IO_LINK serializes them to 1-->2-->3-->4, which unneccessarily
> serializes 2 and 3. But a DAG can fully describe it.
> 
> For the detail usage, see the following patches' messages.
> 
> Tested it with 100 direct read sqes, each one reads a BS=4k block data
> in a same file, blocks are not overlapped. These sqes form a graph:
>        2
>        3
> 1 --> 4 --> 100
>       ...
>        99
> 
> This is an extreme case, just to show the idea.
> 
> results below:
> io_link:
> IOPS: 15898251
> graph_link:
> IOPS: 29325513
> io_link:
> IOPS: 16420361
> graph_link:
> IOPS: 29585798
> io_link:
> IOPS: 18148820
> graph_link:
> IOPS: 27932960

Hmm, what do we compare here? IIUC,
"io_link" is a huge link of 100 requests. Around 15898251 IOPS
"graph_link" is a graph of diameter 3. Around 29585798 IOPS

Is that right? If so it'd more more fair to compare with a
similar graph-like scheduling on the userspace side.

submit(req={1});
wait(nr=1);
submit({2-99});
wait(nr=98);
submit(req={100});
wait(nr=1);


> Tested many times, numbers are not very stable but shows the difference.
> 
> something to concern:
> 1. overhead to the hot path: several IF checks
> 2. many memory allocations
> 3. many atomic_read/inc/dec stuff
> 
> many things to be done:
> 1. cancellation, failure path
> 2. integrate with other features.
> 3. maybe need some cache design to overcome the overhead of memory
>     allcation
> 4. some thing like topological sorting to avoid rings in the graph
> 
> Any thoughts?
> 
> Hao Xu (3):
>    io_uring: add data structure for graph sqe feature
>    io_uring: implement new sqe opcode to build graph like links
>    io_uring: implement logic of IOSQE_GRAPH request
> 
>   fs/io_uring.c                 | 231 +++++++++++++++++++++++++++++++++-
>   include/uapi/linux/io_uring.h |   9 ++
>   2 files changed, 235 insertions(+), 5 deletions(-)
> 

-- 
Pavel Begunkov