[PATCH bpf-next v1 00/20] BPF kthreads and waitqueues

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

Currently, a BPF program has no thread of its own and no way to sleep
until another program wakes it. It runs for the length of one
invocation, in a task that entered the kernel or in a kworker, so a
program that waits for work can only poll for it.

This series introduces two low-level primitives that let BPF programs
build such patterns themselves:

 - bpf_task_park() and bpf_task_wake(), which put the current task to
   sleep and make a task runnable.
 - BPF kthreads, kernel threads whose body is a callback of the program
   that created them.

The kernel provides the mechanism and the program keeps the policy.
There is no wait queue object in the kernel. A wait queue is what the
program builds out of the two kfuncs: a list of parked tasks, kept in a
map or in arena memory, with its own rule for whom to wake and in which
order. The kernel only guarantees that a wake is not lost between the
program's check of its condition and its sleep. Likewise, a thread is
just a task. The program holds it as a task kptr and decides how many
threads it runs, where they run, and when they stop.

We are doing various experiments with synthetic and production workloads
for various use cases (dynamically scaled proactive reclamation, and
dynamically scaled network stack processing) where such primitives
provide foundations for building more adaptive policies to enable better
efficiency and workload isolation.

API Examples
------------

For example, a worker that sleeps until there is work, the program that
creates it, and a waker on the event the worker waits for. q is a value
of an array map with a flag and the worker's task kptr:

	static int worker(u64 arg)
	{
		bpf_repeat(BPF_MAX_LOOPS) {
			if (bpf_kthread_should_stop())
				break;
			if (READ_ONCE(q->ready))
				serve(q);
			else
				bpf_task_park(U64_MAX, 0); /* no timeout */
		}
		return 0;
	}

	SEC("syscall")
	int start(struct start_args *ctx)
	{
		struct task_struct *t;

		t = bpf_kthread_create(worker, ctx->arg, 0);
		if (!t)
			return -ENOMEM;
		bpf_kthread_bind(t, ctx->cpu, 0);
		bpf_kthread_start(t, 0);
		/* Keep t in q for bpf_task_wake() and bpf_kthread_stop(). */
		...
	}

	SEC("tp_btf/mm_vmscan_direct_reclaim_begin")
	int BPF_PROG(reclaim_begin, gfp_t gfp_flags, int order)
	{
		struct task_struct *t;

		bpf_rcu_read_lock();
		t = q->worker;
		if (t) {
			WRITE_ONCE(q->ready, 1);
			bpf_task_wake(t, 0);
		}
		bpf_rcu_read_unlock();
		return 0;
	}

A syscall program parks the same way, in the user thread that runs it.

Sleeping for an unbounded time is new for BPF programs, and most of the
series is about keeping it safe:

 - The park drops the program's Tasks Trace RCU section and its CPU pin
   for the sleep, since neither may be held that long. It is therefore
   limited to syscall programs and kthread bodies, whose runner holds
   the program for the whole run, and the program may resume on another
   CPU. The verifier invalidates the pointers the sleep may free, such
   as hash map values, and refuses the park in other callbacks, under a lock,
   in RCU, preempt-disabled and IRQ-disabled sections, and while a
   dynptr or an iterator other than bpf_iter_num is live.
 - The wake is available to every program type and in every context.
   Where it cannot be issued, with IRQs disabled under the scheduler's
   locks or in NMI, it is deferred to irq_work.
 - A program's threads end with the program: releasing its last
   reference stops them. A stop is cooperative, so a thread body has to
   check bpf_kthread_should_stop(), and it cannot loop without a bound.
   The kthread kfuncs are for syscall programs only for now.
 - Tail calls, the stack in arena and may_goto do not know yet about a
   program that sleeps and may resume on another CPU. They are refused
   for now in a program that parks or uses the kthread kfuncs, so a
   loop in such a program needs a bound of its own, as bpf_repeat()
   gives it.

Kumar Kartikeya Dwivedi (20):
  bpf: Add bpf_task_park() and bpf_task_wake()
  bpf: Invalidate what a bpf_task_park() sleep may free
  bpf: Refuse bpf_task_park() in callbacks
  bpf: Propagate bpf_task_park() through global functions
  bpf: Verify a function that parks in the context of its caller
  bpf: Defer bpf_task_wake() to irq_work when IRQs are disabled
  bpf: Keep programs that park away from per-CPU state and tail calls
  bpf: Register bpf_task_park() for syscall programs
  bpf: Register bpf_task_wake() for all program types
  bpf: Add BPF kthreads for syscall programs
  bpf: Let a BPF kthread sleep in bpf_task_park()
  bpf: Add bpf_kthread_bind() to pin a BPF kthread to a CPU
  bpf: Add bpf_kthread_attach_cgroup() to place a BPF kthread in a
    cgroup
  selftests/bpf: Test bpf_task_park() and bpf_task_wake()
  selftests/bpf: Test what survives bpf_task_park()
  selftests/bpf: Test bpf_task_park() across functions and callbacks
  selftests/bpf: Test bpf_task_wake() from tracing programs
  selftests/bpf: Test BPF kthreads
  selftests/bpf: Test bpf_kthread_bind()
  selftests/bpf: Test bpf_kthread_attach_cgroup()

 include/linux/bpf.h                           |   5 +
 include/linux/bpf_verifier.h                  |  15 +
 include/linux/cgroup.h                        |   3 +
 include/linux/filter.h                        |   7 +
 include/linux/sched.h                         |   4 +
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/arraymap.c                         |   7 +-
 kernel/bpf/cfg.c                              |  23 +
 kernel/bpf/core.c                             |   1 +
 kernel/bpf/diagnostics.c                      |   3 +
 kernel/bpf/diagnostics.h                      |   1 +
 kernel/bpf/fixups.c                           |   6 +
 kernel/bpf/flow.c                             |   3 +-
 kernel/bpf/join.c                             |   4 +-
 kernel/bpf/kthread.c                          | 572 ++++++++++++++++
 kernel/bpf/states.c                           |  10 +-
 kernel/bpf/syscall.c                          |  12 +-
 kernel/bpf/task_park.c                        | 311 +++++++++
 kernel/bpf/verifier.c                         | 279 +++++++-
 kernel/cgroup/cgroup.c                        |  45 ++
 kernel/fork.c                                 |   2 +
 .../testing/selftests/bpf/bpf_experimental.h  |  12 +
 .../selftests/bpf/prog_tests/bpf_kthread.c    | 641 ++++++++++++++++++
 .../selftests/bpf/prog_tests/task_park.c      | 311 +++++++++
 .../testing/selftests/bpf/progs/bpf_kthread.c | 414 +++++++++++
 tools/testing/selftests/bpf/progs/task_park.c | 218 ++++++
 .../bpf/progs/verifier_arena_stack.c          |  27 +
 .../bpf/progs/verifier_bpf_kthread.c          | 398 +++++++++++
 .../selftests/bpf/progs/verifier_task_park.c  | 550 +++++++++++++++
 .../bpf/progs/verifier_task_park_frames.c     | 393 +++++++++++
 30 files changed, 4270 insertions(+), 9 deletions(-)
 create mode 100644 kernel/bpf/kthread.c
 create mode 100644 kernel/bpf/task_park.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_kthread.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/task_park.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_kthread.c
 create mode 100644 tools/testing/selftests/bpf/progs/task_park.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_bpf_kthread.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_task_park.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_task_park_frames.c


base-commit: 0fb18ce8a2e9de830433923cf65838933d615359
-- 
2.53.0