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

[Hao Xu <haoxu@linux.alibaba.com>]

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

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(-)

-- 
2.25.1