BPF kthreads and waitqueues

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