[RFC v3 0/3] block: Introduce a BPF-based I/O scheduler

[Kaitao Cheng <kaitao.cheng@linux.dev>]

From: Kaitao Cheng <chengkaitao@kylinos.cn>

Hi,

This is the third RFC version of UFQ (User-programmable Flexible Queueing),
a BPF-based I/O scheduler for blk-mq. The goal is to let developers build
and iterate on I/O scheduling policies as BPF programs, with userspace
loaders handling configuration and attachment.

The code in this series is an intermediate version under active development
and continued iteration. I am posting it to seek community feedback on
whether the overall direction and design make sense, identify problems in
the approach, and get suggestions for improving the design.

UFQ provides the block-layer integration and request lifecycle management.
It exposes struct_ops callbacks for scheduler initialization and teardown,
request insertion, dispatch, completion, and request and bio merging.
Without an attached BPF scheduler, UFQ uses a simple per-ctx queueing
policy. Once a BPF scheduler is attached, its callbacks implement the
scheduling policy, while UFQ retains fallback handling for failed inserts
and resumes its built-in policy after detach.

The series contains three patches:

1. Add the UFQ elevator, struct_ops interface, and request-management and
   merge kfuncs.
2. Add ufq_simple, a minimal BPF scheduler for exercising the UFQ interface,
   together with userspace loading helpers and build scaffolding.
3. Add PFQ (Priority Fair Queue), a newly developed BPF scheduler that
   demonstrates a more complete policy on top of UFQ.

PFQ gives us a concrete policy to explore how well the UFQ interface
supports more involved scheduling decisions and to guide further work on
the framework. It has not yet been used in production, and further testing
and workload evaluation are needed.

The underlying BPF support needed by UFQ and its examples, including the
graph APIs and support for KF_SPINLOCK_SAFE kfuncs, has been merged upstream.
Those changes are therefore omitted from this version, which contains only
the UFQ framework and its example schedulers.

TODO:
- More thorough correctness and stress testing, including scheduler
  transitions, merging, and error paths.
- Evaluate PFQ fairness, latency, and throughput across workloads.
- Split the kernel implementation into smaller patches for review.

In particular, I would appreciate suggestions on the boundary between the
UFQ framework and BPF policies, the struct_ops interface, and request
ownership and fallback handling. Feedback on alternative approaches or
missing pieces would also help guide the next iteration.

Changes in v3:
- Add PFQ, its userspace loader, statistics, and usage documentation.
- Serialize BPF scheduler attach/detach and combine the callback enable
  state and user count into a single atomic state.
- Refine request reference handling and isolate failed BPF inserts on a
  separate fallback dispatch list.
- Use trylocks in merge kfuncs to avoid blocking on nested scheduler and
  ctx locks, and add a kfunc for setting request->elv.priv[1].
- Drop the BPF kfunc spin-lock support patch included in v2, since the
  required support has been merged upstream.

Changes in v2:
- Remove bpf_request_put (Alexei Starovoitov)
- Update the UFQ README (Miguel Ojeda)
- Add bio merge support
- Fix synchronization issues during UFQ scheduler transitions

Link to v2:
https://lore.kernel.org/all/20260503035623.28771-1-kaitao.cheng@linux.dev/

Link to v1:
https://lore.kernel.org/bpf/20260327114741.91500-1-pilgrimtao@gmail.com/

Kaitao Cheng (3):
  block: Introduce the UFQ I/O scheduler
  tools/ufq_iosched: add BPF example scheduler and build scaffolding
  tools/ufq_iosched: add PFQ eBPF I/O scheduler

 block/Kconfig.iosched                         |    8 +
 block/Makefile                                |    1 +
 block/blk-merge.c                             |   28 +-
 block/blk-mq.c                                |    8 +-
 block/blk-mq.h                                |    2 +-
 block/blk.h                                   |    5 +
 block/ufq-bpfops.c                            |  267 ++
 block/ufq-iosched.c                           |  789 +++++
 block/ufq-iosched.h                           |   79 +
 block/ufq-kfunc.c                             |  169 +
 tools/ufq_iosched/.gitignore                  |    2 +
 tools/ufq_iosched/Makefile                    |  262 ++
 tools/ufq_iosched/README.md                   |  198 ++
 .../include/bpf-compat/gnu/stubs.h            |    7 +
 tools/ufq_iosched/include/ufq/common.bpf.h    |   83 +
 tools/ufq_iosched/include/ufq/common.h        |   87 +
 tools/ufq_iosched/include/ufq/pfq.bpf.h       |  125 +
 tools/ufq_iosched/include/ufq/pfq_disk.h      |   38 +
 tools/ufq_iosched/include/ufq/pfq_stat.h      |   44 +
 tools/ufq_iosched/include/ufq/pfq_tunable.h   |   23 +
 tools/ufq_iosched/include/ufq/simple_stat.h   |   23 +
 tools/ufq_iosched/pfq.bpf.c                   | 2736 +++++++++++++++++
 tools/ufq_iosched/pfq.c                       |  329 ++
 tools/ufq_iosched/ufq_simple.bpf.c            |  604 ++++
 tools/ufq_iosched/ufq_simple.c                |  120 +
 25 files changed, 6024 insertions(+), 13 deletions(-)
 create mode 100644 block/ufq-bpfops.c
 create mode 100644 block/ufq-iosched.c
 create mode 100644 block/ufq-iosched.h
 create mode 100644 block/ufq-kfunc.c
 create mode 100644 tools/ufq_iosched/.gitignore
 create mode 100644 tools/ufq_iosched/Makefile
 create mode 100644 tools/ufq_iosched/README.md
 create mode 100644 tools/ufq_iosched/include/bpf-compat/gnu/stubs.h
 create mode 100644 tools/ufq_iosched/include/ufq/common.bpf.h
 create mode 100644 tools/ufq_iosched/include/ufq/common.h
 create mode 100644 tools/ufq_iosched/include/ufq/pfq.bpf.h
 create mode 100644 tools/ufq_iosched/include/ufq/pfq_disk.h
 create mode 100644 tools/ufq_iosched/include/ufq/pfq_stat.h
 create mode 100644 tools/ufq_iosched/include/ufq/pfq_tunable.h
 create mode 100644 tools/ufq_iosched/include/ufq/simple_stat.h
 create mode 100644 tools/ufq_iosched/pfq.bpf.c
 create mode 100644 tools/ufq_iosched/pfq.c
 create mode 100644 tools/ufq_iosched/ufq_simple.bpf.c
 create mode 100644 tools/ufq_iosched/ufq_simple.c

-- 
2.53.0