[RFC PATCH 0/2] io_uring: futex wakeups that a preempted lower-priority task can't delay

[Austin Schuh <austin.linux@gmail.com>]

Thanks for the prompt reviews, Jens!

I run robot control systems on kernels built with CONFIG_PREEMPT_RT.
Each process runs an io_uring event loop, and processes publish to each
other through shared-memory queues, with the publisher waking each
subscriber's loop.  Real-time and lower-priority processes publish and
subscribe on the same queues.  The real-time ones run on CPUs kept free
of interrupts, and the interrupt threads and everything else run on the
rest.

io_uring fits this well, for the same reasons it is fast: most of its
state is per ring.  The submission and completion rings are shared with
userspace without a lock, and the kernel-side ring locks belong to the
ring.  Requests and single futex wait data come from per-ring caches
once warm, not the slab.  With DEFER_TASKRUN, completions run in the
ring's own task when it waits, so no other task posts to its completion
ring, and another task hands it work with a push onto a lock-free list
and a wake up, taking no lock that sleeps on PREEMPT_RT.  Each of those
removes a place where a lower-priority task could be holding something
the real-time task needs.  And io_uring already lets a ring register
files and buffers once, so each request skips looking them up again.

The wakeup between event loops is where that breaks down.  What I need
is for a real-time publisher to wake a real-time subscriber on time,
whatever the lower-priority processes on the same queue are doing and
however busy their CPUs are with interrupts.  Which mechanism carries
the wakeup doesn't matter to me.  Running the real-time tasks above the
interrupt threads isn't a great answer: a lower-priority task boosted
to their priority would then outrank the interrupt threads on the CPUs
they were moved to, which undoes the isolation.

Each mechanism I've looked at lets a preempted lower-priority task hold
that wakeup back:

 - A futex wake takes the futex hash bucket lock, and so does every
   one-shot IORING_OP_FUTEX_WAIT arm, which an event loop does after
   every wakeup.  On PREEMPT_RT that is a sleeping lock, and priority
   inheritance lifts the lower-priority holder only to the waker's
   priority, which loses to threaded interrupt handlers above it.

 - IORING_OP_MSG_RING allocates an io_kiocb per send from a shared slab
   cache, whose slow path takes the slab's list_lock, a sleeping lock
   on PREEMPT_RT that any task on the system can be holding.

 - eventfd and signals take a spinlock_t, the eventfd's wait queue lock
   or the target's siglock, which on PREEMPT_RT is a sleeping lock that
   lower-priority writers and readers of the same eventfd or process
   hold too.

I measured each on a Jetson Orin Nano with PREEMPT_RT.  A SCHED_FIFO 40
sender on CPU 4 sends a message every 500us to a SCHED_FIFO 40
receiver's event loop on CPU 5.  On CPUs 0 and 1, lower-priority
processes send and receive on the same queue every 200us, starting and
stopping, beside SCHED_FIFO 50 threads running 20us to 1ms bursts and
interrupt and system load.  Ten minutes and 1.2 million messages a run.
Counted here is the real-time sender's time in the call that wakes the
receiver, which is where it waits on the lock:

                                       runs  over 100us   longest
  futex, one-shot io_uring wait (7.4)    1       10,285    1.0ms
  MSG_RING (7.4)                         1           55    1.0ms
  signal, signalfd (6.18)                2  33,080-36,122  1.7ms

Traced on 6.18, the futex sender waits on the bucket lock, the MSG_RING
sender on the slab's list_lock, and the signal sender on the receiver's
siglock, each held by a lower-priority task boosted to 40 and preempted
by the SCHED_FIFO 50 threads.  The receiver's one-shot futex arms wait
on the same bucket lock, so for futexes 10,348 messages reached the
receiver over 100us after they were sent, worst 3.5ms.

The options I see:

 1. Persistent futex waits and registered wakes: look the futex up
    once and cache it.  The waker registers the futex word with its
    ring once, and the waiter arms a wait on it once and keeps it
    armed.  Both meet in one node for that futex, so a wake goes
    straight to the cached node and walks its waiters, with no key
    lookup, no futex hash bucket, no lock that sleeps on PREEMPT_RT
    and no allocation.  Patch 2; prototyped and measured.

 2. An allocation-free MSG_RING: IORING_MSG_DOORBELL.  A ring's task
    registers a doorbell, and a sender ORs bits into a word in the
    target ctx and wakes its task; the target posts one CQE per drain.
    Real-time kernels solve this problem the same way: seL4
    notifications and FreeRTOS task notifications OR bits into a word
    the waiter owns.  Prototyped on 6.18, not posted: at SCHED_FIFO 40,
    no message over 100us late, worst 43us.

 3. Keep MSG_RING's data messages, but take the io_kiocb from a cache
    on the target ring instead of the slab.  Not prototyped.

Patch 2 is option 1.  A persistent wait posts one CQE per wakeup and
is re-armed by its slot, without looking the futex up again.  Futexes
also simplify discovery: a publisher wakes whoever waits on the word
without knowing who they are, where a doorbell or MSG_RING needs every
subscriber's ring fd.  In the same test, with persistent waits no send
took over 100us, the longest 25us, and no message reached the receiver
over 100us after it was sent, the worst 30.5us.

Patch 2 is here to start the discussion, not as a polished solution.
It is probably more useful to discuss the design before digging too far
into the details of that patch.

Patch 1 is a fix to the DEFER_TASKRUN wake up that patch 2 depends on.
It stands on its own; its commit message has the details.

I'd love any feedback you've got, or suggestions on other options that
I've missed.

Austin Schuh (2):
  io_uring: don't let a preempted task_work add hold back the wake up
  io_uring/futex: add persistent waits and registered wakes

 include/linux/io_uring_types.h |   6 +
 include/uapi/linux/io_uring.h  |  52 ++-
 io_uring/futex.c               | 788 ++++++++++++++++++++++++++++++++-
 io_uring/futex.h               |  28 ++
 io_uring/io_uring.c            |   1 +
 io_uring/register.c            |  13 +
 io_uring/tw.c                  | 124 ++++--
 io_uring/tw.h                  |   4 +-
 8 files changed, 983 insertions(+), 33 deletions(-)


base-commit: 5b01d5955ac206e38097f777eff6ab2a8b948c41
-- 
2.47.3