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

Currently, there is no BPF primitive for a program to sleep for arbitrary lengths of time while waiting for a wake up controlled by another program to happen. Several BPF programs run in contexts where such unbounded sleeping can be harmful.

Moreover, unbounded sleeps can be problematic, since a sleepable BPF program runs with migration disabled under a Tasks Trace RCU read section, and neither may be held across a sleep of unbounded length: the read section would stall every Tasks Trace grace period in the system, and a migration-disabled sleeper keeps rq->nr_pinned raised, which blocks CPU offline in balance_hotplug_wait() and pins its wakeup to the CPU it slept on.

Introduce low-level primitives that let BPF programs construct such patterns. bpf_task_park() puts the current task to sleep and bpf_task_wake() makes a task runnable. The program keeps its own queue of waiters and its own condition for when the event has arrived, in arena memory, in graph nodes holding a task kptr, or in a map value, and checks the condition in a loop around the park:

	waiter				waker

	while (!cond)			cond = true;
		bpf_task_park(...);	bpf_task_wake(task, 0);

The kernel owns nothing per queue: there is no object to allocate, initialize, tear down, or synchronize against the map value going away. It keeps one word per task, bpf_wake_pending, which has to make that loop work.

No wake is lost between the check and the sleep. The check is made in the program, so something has to carry a wake across the gap between it and the sleep, and the word does, the way the stop bit does for kthread_should_stop(). bpf_task_wake() stores the word and calls wake_up_state(); bpf_task_park() sets the task state, reads the word again, and sleeps only if it is clear. The barrier in set_current_state() pairs with the one in try_to_wake_up() that follows the waker's store, so either the waiter sees the pending wake or the waker sees it sleeping. A wake that finds its task running is kept until that task's next park, which then returns at once; a stale one costs a spurious turn of the loop.

The waiter sees the condition once the park has returned. The pairing above covers the sleep, but it does not order the word against the program's own condition, and the loop depends on that order: the waker stores the condition and then wakes, the waiter returns from the park and then reads the condition, and the read must see the store. Two things provide it. bpf_task_wake() stores the word with xchg(), which is fully ordered, so the condition stores before the call are visible to whoever observes the word. bpf_task_park() consumes the word with xchg() on every return, so the condition loads after the return cannot be satisfied before the word was observed. On a weakly ordered architecture a plain store and a plain load would let the waiter observe the wake, read a stale condition, park again with the word already cleared, and sleep with no one left to wake it.

A release is not enough for the store, because wakers race with each other. Of two wakers' stores one overwrites the other, and the waiter observes only the later one. A release orders a waker's condition before its own store of the word, for whoever reads that store; nobody reads the store that was overwritten, so nothing orders that waker's condition before the waiter's read of it. The waiter then consumes both wakes, misses one condition, and parks again while the waker saw it running. The kernel memory model allows that outcome with a release and forbids it with xchg().

The xchg() also makes the consume atomic. A wake that lands after the park observed the word but before it cleared it is not lost: the exchange returns the value at the instant of the reset, so the wake is either consumed by this park or still pending for the next one.

bpf_task_park() returns:

- 0 when it consumed a wake, or when the sleep ended for no recorded reason. The program tells a wake from such a spurious return by its own condition.
- -ESHUTDOWN when a stop or park request for a kthread is pending. Nothing clears the request while the thread's function runs, so every later park that finds no wake pending fails the same way and the caller has to return, which is why it is not reported as a signal is.
- -EINTR when a signal is pending. The signal and the request are both checked for every caller, since a kthread that called allow_signal() has signals too, and both before the sleep and after it.
- -ETIMEDOUT when the timeout passed. A timeout of 0 polls and U64_MAX sleeps without a timer.

When more than one of these applies, a wake wins over a stop request, a stop request over a signal, and either over the timeout. The wake wins because the waker may have dequeued or accounted for the sleeper on the strength of its wake having been delivered, and the sleeper's return value should agree, the way a futex that was woken returns 0 even if its timer also fired. The consuming xchg() is what makes it win: a wake that arrives while the timeout expires or a signal is noticed is reported rather than discarded with the word. A signal or a stop request wins over a timer that fired at the same time because the request stays pending and the timeout does not. schedule_hrtimeout() tells an expiry from an early return but not a wake from a signal, so the flags are read again after it and decide first.

bpf_task_wake() returns 1 when the task was asleep and 0 when it was not.

The sleep is interruptible for every caller. A kthread normally has no signals, so TASK_INTERRUPTIBLE is harmless there, avoids the load average and the hung task detector, and lets bpf_task_wake() use a TASK_INTERRUPTIBLE mask, which can never disturb an uninterruptible sleeper elsewhere in the kernel.

The word is an int rather than a byte so that the exchange is a plain 4-byte xchg() on every architecture. dup_task_struct() clears it: a child inherits nothing from a wake addressed to its parent.

The park drops migration and the Tasks Trace RCU section around the sleep. That is sound only where the invocation's runner holds the program, its maps and its context for the whole invocation, so that the program's own memory needs no grace period, and where nothing on the run path keeps per-CPU state across the program. The kfunc comment states that contract, and the verifier patches that follow confine the call to such contexts and invalidate what the sleep may free.

Both kfuncs take a flags argument that must be 0. Only the two functions and the word they share are added here: later patches register the kfuncs, and until then nothing can call them.

---
 include/linux/sched.h  |   2 +
 kernel/bpf/Makefile    |   2 +-
 kernel/bpf/task_park.c | 192 +++++++++++++++++++++++++++++++++++++++++
 kernel/fork.c          |   1 +
 4 files changed, 196 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/task_park.c

index 1c93da75226e..43222c34fab8 100644
@@ -1630,6 +1630,8 @@ struct task_struct {
 	struct bpf_local_storage __rcu	*bpf_storage;
 	/* Used for BPF run context */
 	struct bpf_run_ctx		*bpf_ctx;
+	/* Set by bpf_task_wake(), consumed by bpf_task_park() */
+	int				bpf_wake_pending;
 #endif
 	/* Used by BPF for per-TASK xdp storage */
 	struct bpf_net_context		*bpf_net_context;

index d26c62326e58..34357665c34c 100644
@@ -15,7 +15,7 @@ obj-$(CONFIG_BPF_SYSCALL) += fixups.o cfg.o states.o check_btf.o flow.o join.o
 obj-${CONFIG_BPF_LSM}	  += bpf_inode_storage.o
 obj-$(CONFIG_BPF_SYSCALL) += disasm.o mprog.o
 obj-$(CONFIG_BPF_JIT) += trampoline.o
-obj-$(CONFIG_BPF_SYSCALL) += btf.o memalloc.o rqspinlock.o stream.o
+obj-$(CONFIG_BPF_SYSCALL) += btf.o memalloc.o rqspinlock.o stream.o task_park.o
 ifeq ($(CONFIG_MMU)$(CONFIG_64BIT),yy)
 obj-$(CONFIG_BPF_SYSCALL) += arena.o range_tree.o
 endif

index 8b108ed37152..b66eb25626c9 100644
@@ -1019,6 +1019,7 @@ static struct task_struct *dup_task_struct(struct task_struct *orig, int node)
 #ifdef CONFIG_BPF_SYSCALL
 	RCU_INIT_POINTER(tsk->bpf_storage, NULL);
 	tsk->bpf_ctx = NULL;
+	tsk->bpf_wake_pending = 0;
 #endif
 	return tsk;
 

2.53.0

bpf_task_park() drops the Tasks Trace RCU read section and the disabled migration that a sleepable program runs under, for the length of its sleep. Anything the program holds whose lifetime rested on either is not safe to touch afterwards. Teach the verifier which registers and stack objects those are and treat the call accordingly.

A pointer register, direct or spilled, is kept only when something other than the dropped protection holds its target:

- the stack, function and instruction pointers, which describe the invocation itself;
- the context and the maps the program references directly, which the runner holds for the whole invocation;
- the values of the program's own array maps. An array allocates its values with the map and frees them only with the map, and the program holds the map, so nothing can free such a value during the sleep. The program's global variables are values of its .data, .bss and .rodata arrays, and the compiler hoists their address out of a loop; without this rule no loop around a park could read a global;
- arena memory, which the arena map holds and whose accesses tolerate faults;
- pointers backed by a verifier-tracked reference, found through their own id or through their parent's id, since the reference keeps the object alive regardless of grace periods.

Everything else is marked invalid:

- values of every other map type. A concurrent delete, an LRU eviction or the teardown of the owning socket, task or inode frees their elements after a grace period the sleeper no longer delays, or hands them straight back to a preallocated map's free list;
- RCU and trusted pointers without a reference, including the task pointer from bpf_get_current_task_btf();
- per-CPU pointers, since the task may resume on another CPU;
- inner maps found through a map-in-map lookup, together with their values, which only the outer element holds. A map or value with map_uid set came from such a lookup, so the array and map pointer exemptions apply only when map_uid is zero.

Dynptrs and iterators need a different treatment. They live in stack slots, and the program is obliged to release or destroy them later. The verifier cannot invalidate them the way it invalidates a register, and neither way of dropping them is sound:

- Marking the slot's register state invalid would keep the slots typed STACK_DYNPTR or STACK_ITER while zeroing the state that describes them. That breaks the invariants destroy_if_dynptr_stack_slot() relies on: with first_slot cleared, a later store to the slot repositions to the slot above and releases whatever reference id it finds there, or reads past the end of the stack array when the dynptr was the topmost object.
- Releasing their reference on the program's behalf instead would leave the runtime object, a ringbuf reservation or an iterator's kernel state, without the destroy the program can no longer issue.

The park is therefore refused while any dynptr or iterator is live in any frame, naming the frame and stack offset. The one exception is
bpf_iter_num: its state is two integers on the stack and its next and destroy touch nothing else, so an open-coded bpf_for() loop may contain a park.

The invalidation runs in check_kfunc_call() after the arguments are checked and before the caller-saved registers are clobbered and R0 is set up, so the kfunc's return value is unaffected. Each scrub is recorded for the diagnostics layer under a new reason, so a later access through an invalidated pointer explains that the park invalidated it.

The invalidation walks every frame of the current state, which covers the callers of the function that parks when they are in the state. They are not when the function is verified without them, as a global function is, and a static function that is verified on its own; later patches handle the two.

---
 kernel/bpf/diagnostics.c |   3 ++
 kernel/bpf/diagnostics.h |   1 +
 kernel/bpf/verifier.c    | 106 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 110 insertions(+)

index 3de3e1486bbd..33788d6f6155 100644
@@ -2231,6 +2231,9 @@ static void diag_print_mod(struct bpf_verifier_env *env, const struct bpf_diag_h
 	case BPF_DIAG_MOD_NON_OWN_REF:
 		reason = "leaving the protected region invalidated this borrowed pointer";
 		break;
+	case BPF_DIAG_MOD_TASK_PARK:
+		reason = "the sleep in bpf_task_park() invalidated this pointer";
+		break;
 	case BPF_DIAG_MOD_CALLER_SAVED:
 		reason = target->kind == BPF_DIAG_MOD_TARGET_STACK_ARG ?
 			 "call invalidated this outgoing stack argument" :

index e155d2588a51..656c0430f013 100644
@@ -26,6 +26,7 @@ enum bpf_diag_mod_reason {
 	BPF_DIAG_MOD_SLICE_BUF,
 	BPF_DIAG_MOD_NON_OWN_REF,
 	BPF_DIAG_MOD_CALLER_SAVED,
+	BPF_DIAG_MOD_TASK_PARK,
 };
 
 enum bpf_diag_context_kind {

2.53.0

Confine bpf_task_park() to the main body of the program and the functions it calls directly, at any depth, and refuse it in every callback frame: the synchronous callbacks of bpf_loop(), bpf_for_each_map_elem(), bpf_find_vma(), bpf_user_ringbuf_drain() and the graph helpers, the asynchronous callbacks of bpf_timer, bpf_wq, bpf_task_work and bpf_call_rcu(), and the exception callback.

The park is sound where the only thing around the program is its runner, which holds the program, its maps and its context for the whole invocation. A callback has more around it. Kernel code called by the program, or a worker acting on its behalf, holds state across the callback that was not written with a sleep that drops the program's protection in mind, and each case would need its own audit:

- bpf_for_each_map_elem() keeps an iteration position into the map across the callback. The verifier already refuses sleeping in the hash map variant; nothing would refuse it in the array variant.
- A bpf_wq callback runs from a kworker, and bpf_wq_work() holds the program through nothing but a Tasks Trace RCU read section, the very section the park drops. Today the free path survives only because bpf_async_cb_rcu_tasks_trace_free() notices work_busy() and waits for another grace period, which a park of unbounded length turns into an endless chain of grace periods after the element is deleted, and the comment there assumes the callback stays inside the section.
- A bpf_task_work callback also runs from exit_task_work() for an exiting task, after exit_signals() has set PF_EXITING; from then on wants_signal() refuses every signal for it, so a park without a timeout in that callback could not be interrupted.
- The exception callback runs while the program is being unwound after bpf_throw(); nothing in it should block.

Rather than audit and special-case each, the rule is that the park may only appear where the program is the only thing running: the main body, or a frame reached from it through plain calls. The check walks every frame of the current state and refuses the call if any is a callback frame. Asynchronous callbacks are verified as their own state with the callback as frame 0, so the walk sees them too. A static function that parks and is also used as a callback is rejected on the callback path, which is the right outcome: it cannot be made safe on that path.

---
 kernel/bpf/verifier.c | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

index e90cc127aedb..b42782c7f209 100644
@@ -11222,6 +11222,31 @@ static void invalidate_non_owning_refs(struct bpf_verifier_env *env)
 	}));
 }
 
+/*
+ * bpf_task_park() is confined to the main body of the program and the
+ * functions it calls directly. A callback runs from kernel code that holds
+ * state of its own around the call, an iteration position, a work item or
+ * timer that owns the program only through Tasks Trace RCU, an exiting task,
+ * none of it audited against a sleep that drops the program's protection.
+ * Refuse the park in any callback frame, synchronous, asynchronous or
+ * exception. Asynchronous callbacks are verified as a state of their own
+ * with the callback as frame 0, so the walk over the frames sees them too.
+ */
+static bool in_callback_frames(struct bpf_verifier_env *env)
+{
+	struct bpf_verifier_state *vstate = env->cur_state;
+	int i;
+
+	for (i = 0; i <= vstate->curframe; i++) {
+		struct bpf_func_state *frame = vstate->frame[i];
+
+		if (frame->in_callback_fn || frame->in_async_callback_fn ||
+		    frame->in_exception_callback_fn)
+			return true;
+	}
+	return false;
+}
+
 /*
  * bpf_task_park() sleeps without the Tasks Trace RCU read section and the
  * disabled migration that a sleepable program otherwise runs under. A dynptr

@@ -16366,6 +16391,12 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	}
 
 	if (is_bpf_task_park_kfunc(meta.func_id)) {
+		if (in_callback_frames(env)) {
+			verbose(env, "bpf_task_park() is not allowed in a callback\n");
+			bpf_diag_policy(env, insn_idx, "kfunc bpf_task_park", "the call is in a callback",
+					"Call bpf_task_park() from the main program or from a function it calls directly, not from a callback.");
+			return -EINVAL;
+		}
 		err = check_park_stack_objects(env, insn_idx);
 		if (err)
 			return err;

2.53.0

A global function is verified on its own, with no knowledge of its callers, and a call to it is checked against its declared contract rather than by walking into it. The two rules the previous patches added at the park are therefore blind to a park that happens inside a global function: the caller keeps its map value pointers across the call, and a callback may call a global function that parks. The first is a use after free waiting to happen, the second defeats the callback restriction.

Record the fact per subprogram the way might_sleep and changes_pkt_data are recorded. The CFG pass marks the subprogram containing a bpf_task_park() call and merges the mark into every caller through merge_callee_effects(), so might_park on a subprogram means that some call reachable from it may park, through static and global callees alike. Like the other two marks it is computed before dead code elimination, so an unreachable park still sets it; the consequence is conservative, a caller that invalidates more than it had to.

At a call to a global function with the mark, apply at the call site what the park would apply inside: refuse the call from any callback frame, refuse it while the caller holds a live dynptr or an iterator other than bpf_iter_num, and after the call invalidate the caller's registers that would not survive the sleep. The callee's own frame is covered when the callee is verified, where the park itself runs the checks; this patch completes them for the frames the callee cannot see. A global function that parks and is called from a non-sleepable context needs nothing new: a global function is verified once per calling context, and the park is registered as a sleepable kfunc.

Extension programs need no further rule. An extension replacing a global function of a syscall program resolves to the syscall type for its kfunc set and could name bpf_task_park(), but an extension cannot be loaded sleepable, so the park is refused there as any sleepable kfunc is in a non-sleepable program. Behind that, bpf_check_attach_target() refuses to extend a function that runs without an RCU read lock, which is every function a syscall program actually calls, since its sleepable main body marks each callee as called in a sleepable context; only a global function that nothing calls stays extendable, and nothing would run it.

The mark does not cross the instruction that only loads a callback's address, unless the program uses callx. A park in a synchronous callback is refused at the park, with the caller's frames in view, and an asynchronous callback is a root of its own, so the function that passes the callback does not park on its account. With the mark it would be treated as if it did, refused from callbacks and made to invalidate its caller's pointers, which matters as soon as some callback may park legitimately, as the body of a BPF kthread does. A loaded address may also be called through callx, which is a call like any other, so the mark follows it when the program has callx.

---
 include/linux/bpf_verifier.h |  3 +++
 kernel/bpf/cfg.c             | 23 +++++++++++++++++++++++
 kernel/bpf/verifier.c        | 27 +++++++++++++++++++++++++++
 3 files changed, 53 insertions(+)

index 4771c55d8f41..b304f3ebc983 100644
@@ -1056,6 +1056,8 @@ struct bpf_subprog_info {
 	bool keep_fastcall_stack: 1;
 	bool changes_pkt_data: 1;
 	bool might_sleep: 1;
+	/* some call reachable from this subprog may be bpf_task_park() */
+	bool might_park: 1;
 	bool uses_arena_sp: 1;
 	/* a callback that takes a stack in arena, like the main program does */
 	bool arena_stack_entry: 1;

@@ -2033,6 +2035,7 @@ static inline bool bpf_is_kfunc_sleepable(struct bpf_call_arg_meta *meta)
 }
 bool bpf_is_kfunc_pkt_changing(struct bpf_call_arg_meta *meta);
 bool bpf_is_cast_kfunc(const struct bpf_call_arg_meta *meta);
+bool bpf_is_task_park_kfunc(struct bpf_call_arg_meta *meta);
 struct bpf_iarray *bpf_iarray_realloc(struct bpf_iarray *old, size_t n_elem);
 int bpf_copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off);
 bool bpf_insn_is_cond_jump(u8 code);

index bbcf42eae9d9..0102df246633 100644
@@ -67,6 +67,14 @@ static void mark_subprog_might_sleep(struct bpf_verifier_env *env, int off)
 	subprog->might_sleep = true;
 }
 
+static void mark_subprog_might_park(struct bpf_verifier_env *env, int off)
+{
+	struct bpf_subprog_info *subprog;
+
+	subprog = bpf_find_containing_subprog(env, off);
+	subprog->might_park = true;
+}
+
 static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off)
 {
 	struct bpf_subprog_info *subprog;

@@ -86,15 +94,28 @@ static void mark_subprog_might_throw(struct bpf_verifier_env *env, int off)
 static bool merge_callee_effects(struct bpf_verifier_env *env, int t, int w)
 {
 	struct bpf_subprog_info *caller, *callee;
+	bool might_park;
 
 	caller = bpf_find_containing_subprog(env, t);
 	callee = bpf_find_containing_subprog(env, w);
+	/*
+	 * A park in a callback does not mark the function that only loads
+	 * the callback's address: a synchronous callback is refused at the
+	 * park with the caller's frames in view, and an asynchronous one is a
+	 * root of its own. The address may also be called through callx,
+	 * which is a call like any other, so the mark follows it when the
+	 * program has callx at all.
+	 */
+	might_park = callee->might_park &&
+		     (bpf_pseudo_call(&env->prog->insnsi[t]) || env->has_callx);
 	if (caller->changes_pkt_data >= callee->changes_pkt_data &&
 	    caller->might_sleep >= callee->might_sleep &&
+	    caller->might_park >= might_park &&
 	    caller->might_throw >= callee->might_throw)
 		return false;
 	caller->changes_pkt_data |= callee->changes_pkt_data;
 	caller->might_sleep |= callee->might_sleep;
+	caller->might_park |= might_park;
 	caller->might_throw |= callee->might_throw;
 	return true;
 }

@@ -618,6 +639,8 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 			 */
 			if (ret == 0 && bpf_is_kfunc_sleepable(&meta))
 				mark_subprog_might_sleep(env, t);
+			if (ret == 0 && bpf_is_task_park_kfunc(&meta))
+				mark_subprog_might_park(env, t);
 			if (ret == 0 && bpf_is_kfunc_pkt_changing(&meta))
 				mark_subprog_changes_pkt_data(env, t);
 			if (ret == 0 && bpf_is_throw_kfunc(insn))

index b42782c7f209..d8fbdd6b9658 100644
@@ -12129,6 +12129,26 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			return err;
 		}
 
+		/*
+		 * A park inside the callee is checked when the callee is verified,
+		 * but only against the callee's own frame. Apply the rules for the
+		 * frames the callee cannot see here, at the call.
+		 */
+		if (env->subprog_info[subprog].might_park) {
+			if (in_callback_frames(env)) {
+				verbose(env, "global function %s() may call bpf_task_park(), which is not allowed in a callback\n",
+					sub_name);
+				operation = bpf_diag_fmt(env, "global function %s() that may call bpf_task_park()",
+							 sub_name);
+				bpf_diag_policy(env, *insn_idx, operation, "the call is in a callback",
+						"Call the function from the main program or from a function it calls directly, not from a callback.");
+				return -EINVAL;
+			}
+			err = check_park_stack_objects(env, *insn_idx);
+			if (err)
+				return err;
+		}
+
 		if (env->log.level & BPF_LOG_LEVEL)
 			verbose(env, "Func#%d ('%s') is global and assumed valid.\n",
 				subprog, sub_name);

@@ -12141,6 +12161,8 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		returns_void = subprog_returns_void(env, subprog);
 		if (env->subprog_info[subprog].changes_pkt_data)
 			clear_all_pkt_pointers(env);
+		if (env->subprog_info[subprog].might_park)
+			invalidate_regs_across_park(env);
 		if (returns_void)
 			bpf_diag_record_scrub(env, &caller->regs[BPF_REG_0], BPF_DIAG_MOD_CALLER_SAVED);
 		else

@@ -14538,6 +14560,11 @@ bool bpf_is_kfunc_pkt_changing(struct bpf_call_arg_meta *meta)
 	       is_kfunc_dynptr_write(meta);
 }
 
+bool bpf_is_task_park_kfunc(struct bpf_call_arg_meta *meta)
+{
+	return is_kfunc_call(meta, special_kfunc_list[KF_bpf_task_park]);
+}
+
 static u32 kfunc_abi_slots(const struct btf_func_model *fm)
 {
 	const struct bpf_jit_arg_abi *abi = bpf_jit_arg_abi();

2.53.0

A static function is verified on its own when what it does depends on its arguments only: it gets a state with the function as frame 0, and bpf_flow_return() applies the states at its exits to every call that waits for it. The frames of its callers are not in that state. The rules of bpf_task_park() look at frames. The park is refused when a frame is a callback or holds a live dynptr or iterator, and it invalidates in every frame what the sleep may free. In a function that is verified on its own they see the function alone, so its caller keeps a hash map value across the park, and a callback gets to park by calling a function that does.

Verify such a function in the context of its caller, the way a function that changes packet data is. func_is_on_its_own() refuses a function that has the might_park mark, so its frame is set up on top of the caller's and the park finds every frame in the state.

The mark is not enough when the program has callx. The CFG pass gives the mark to the function that loads an address, not to the one that calls it, so a function that calls an address it got from its caller has no mark and is verified on its own. For that, record the park in the state. invalidate_regs_across_park(), which the park and the call of a global function that parks both run, sets parked in the state of a function that is verified on its own. bpf_flow_return() finds the flag in the state at the exit, sets the mark of the function and asks for the call to be verified in the context of the caller, as it does for changed_pkt_data. If that caller is verified on its own as well, the park sets the flag in its state and the same happens at its exit, one caller at a time.

The flag is a part of what a state stands for: states that differ in it are not joined, and neither is taken for the other.

---
 include/linux/bpf_verifier.h |  6 ++++++
 kernel/bpf/flow.c            |  3 ++-
 kernel/bpf/join.c            |  3 ++-
 kernel/bpf/states.c          |  3 ++-
 kernel/bpf/verifier.c        | 16 ++++++++++++++++
 5 files changed, 28 insertions(+), 3 deletions(-)

index b304f3ebc983..39ff1359adb9 100644
@@ -559,6 +559,12 @@ struct bpf_verifier_state {
 	 * and their packet pointers are not in the state, see bpf_flow_return().
 	 */
 	bool changed_pkt_data;
+	/*
+	 * A function that is verified on its own parked the task. Its callers,
+	 * what the sleep takes from them and whether one of them is a callback,
+	 * are not in the state, see bpf_flow_return().
+	 */
+	bool parked;
 	/*
 	 * Not zero in a function that is verified on its own: the call that the
 	 * state at its entry came from, see bpf_flow_call().

index c9458b3ad114..47ff2fb5f11a 100644
@@ -2309,7 +2309,8 @@ static void flow_shape_ctx(const struct bpf_verifier_state *st, struct flow_shap
 
 	ctx = jhash_3words(st->in_sleepable | st->callers_unknown << 1 |
 			   st->unwound << 2 | st->changed_pkt_data << 3 |
-			   (st->active_irq_id != 0) << 4 | (st->active_lock_id != 0) << 5,
+			   (st->active_irq_id != 0) << 4 | (st->active_lock_id != 0) << 5 |
+			   st->parked << 6,
 			   st->acquired_refs, st->active_locks, 0);
 	ctx = jhash_2words(st->active_preempt_locks, st->active_rcu_locks, ctx);
 	ctx = jhash_2words(lower_32_bits((unsigned long)st->active_lock_ptr),

index cc4494aef187..8bd92af087c0 100644
@@ -532,7 +532,8 @@ static bool join_check_state(const struct bpf_verifier_state *a,
 		return false;
 	if (a->speculative != b->speculative || a->in_sleepable != b->in_sleepable ||
 	    a->callers_unknown != b->callers_unknown ||
-	    a->unwound != b->unwound || a->changed_pkt_data != b->changed_pkt_data)
+	    a->unwound != b->unwound || a->changed_pkt_data != b->changed_pkt_data ||
+	    a->parked != b->parked)
 		return false;
 	if (a->active_locks != b->active_locks ||
 	    a->active_preempt_locks != b->active_preempt_locks ||

index efc0870b85c2..f75161423377 100644
@@ -745,7 +745,8 @@ bool bpf_state_subsumes(struct bpf_verifier_env *env, struct bpf_verifier_state
 	if (old->in_sleepable != cur->in_sleepable)
 		return false;
 
-	if (old->unwound != cur->unwound || old->changed_pkt_data != cur->changed_pkt_data)
+	if (old->unwound != cur->unwound || old->changed_pkt_data != cur->changed_pkt_data ||
+	    old->parked != cur->parked)
 		return false;
 
 	if (!refsafe(old, cur, &env->idmap_scratch))

index d8fbdd6b9658..8edc32153226 100644
@@ -1792,6 +1792,7 @@ int bpf_copy_verifier_state(struct bpf_verifier_state *dst_state,
 	dst_state->callers_unknown = src->callers_unknown;
 	dst_state->unwound = src->unwound;
 	dst_state->changed_pkt_data = src->changed_pkt_data;
+	dst_state->parked = src->parked;
 	dst_state->flow_entry = src->flow_entry;
 	dst_state->insn_idx = src->insn_idx;
 	dst_state->curframe = src->curframe;

@@ -11337,6 +11338,9 @@ static void invalidate_regs_across_park(struct bpf_verifier_env *env)
 		bpf_diag_record_scrub(env, reg, BPF_DIAG_MOD_TASK_PARK);
 		mark_reg_invalid(env, reg);
 	}));
+	/* the frames of the callers are looked at when the function returns to them */
+	if (env->cur_state->flow_entry)
+		env->cur_state->parked = true;
 }
 
 static void invalidate_rcu_protected_refs(struct bpf_verifier_env *env)

@@ -11757,6 +11761,9 @@ static bool func_is_on_its_own(struct bpf_verifier_env *env, struct bpf_verifier
 	if (sub->changes_pkt_data || sub->has_tail_call || sub->has_ld_abs ||
 	    sub->is_cb || sub->is_async_cb || sub->is_exception_cb)
 		return false;
+	/* a park looks at every frame, and takes from each what the sleep may free */
+	if (sub->might_park)
+		return false;
 	if (state->speculative)
 		return false;
 	if (sub->releases_inherited &&

@@ -11936,6 +11943,15 @@ int bpf_flow_return(struct bpf_verifier_env *env, struct bpf_verifier_state *cal
 		env->subprog_info[callee->subprogno].changes_pkt_data = true;
 		return 1;
 	}
+	/*
+	 * Likewise for a park behind such an address. It was checked against the frames
+	 * of the function only: which caller is a callback, and what the sleep takes
+	 * from each, is found out in the context of the caller.
+	 */
+	if (exit->parked) {
+		env->subprog_info[callee->subprogno].might_park = true;
+		return 1;
+	}
 
 	for (i = 0; i < CALLER_SAVED_REGS; i++)
 		bpf_mark_reg_not_init(env, &frame->regs[caller_saved[i]]);

2.53.0

bpf_task_wake() ends a park with try_to_wake_up(), which takes the task's pi_lock and a runqueue lock. The wake is meant for tracing programs as much as for the program that parked: the kernel event that makes a parked task worth waking is usually one a tracing program sees. Those programs run where try_to_wake_up() may not:

- the scheduler's own tracepoints fire with IRQs disabled, sched_waking under the woken task's pi_lock and sched_switch under the runqueue lock;
- a kprobe often runs in an interrupts-off region of the function it probes;
- a perf event program on a hardware event runs in NMI context.

Queue a wake that is asked for with IRQs disabled for irq_work on the calling CPU, which issues it as soon as IRQs are enabled again. One test covers both reasons to defer: a caller with IRQs enabled holds no scheduler lock, since every one of them is taken with IRQs disabled, and NMI context has IRQs disabled on every architecture. The usual case keeps its direct wake and pays one read of the IRQ flag. A program that wakes inside a bpf_local_irq_save() section holds no scheduler lock and could wake directly, but the kfunc cannot tell it from a caller that does, so its wake is deferred as well.

A deferred wake returns 2. It cannot tell whether the task was asleep, which is what the 1 and the 0 of a direct wake say, and a waker that reads 0 as a task that was already running, and picks another to wake, would otherwise wake every one of its candidates when it runs with IRQs disabled. The waiter learns from its own return value whether a wake ended its sleep.

The queue runs through a node of its own in the task, bpf_wake_node, under the rule the scheduler's wake queues follow for theirs:

- a task is on at most one queue;
- the claim is a cmpxchg() of the node's next pointer from NULL;
- whoever holds the claim wakes the task;
- a waker that finds the task claimed leaves the wake to the claimant.

A wake that loses the claim is not lost. The pending word is stored before the claim is tried, and the xchg() that stores it is a full barrier between the two. A claim that fails has therefore observed the node before the holder's reset of it, and the holder's wake, a full barrier after that reset, orders the word before the woken task's loads. If the task is parked, the claimant's wake ends the park, which then consumes the word; if it is not, the word waits for its next park, as a wake that finds the task running always has.

The task's wake_q node is not used for this, although it would save the field. Whoever claims that node may turn away a futex, rwsem or semaphore wakeup that then relies on the claimant, so the drain would have to wake with TASK_NORMAL, and a program could aim a wake of an uninterruptible sleep at any task it names. Not every such sleep tolerates one: a new kthread sleeps once, without a loop, until its creator wakes it. With a node of its own the drain wakes interruptible sleeps only, as the direct wake does.

The per-CPU queue is a stack rather than a wake_q_head. The head of a wake queue is two words updated without atomics, and this queue is pushed from NMI context while the irq_work that drains it runs in hard IRQ context on the same CPU. A push is a cmpxchg() on the one head pointer and the drain takes the whole stack with one xchg(), so a push that interrupts the drain lands on an empty stack and queues the work again, which irq_work permits because it clears its pending bit before running the callback. The work is a hard irq_work so that on PREEMPT_RT the wake is not queued behind the irq_work thread.

---
 include/linux/sched.h  |  2 +
 kernel/bpf/task_park.c | 86 +++++++++++++++++++++++++++++++++++++++++-
 kernel/fork.c          |  1 +
 3 files changed, 87 insertions(+), 2 deletions(-)

index 43222c34fab8..0fdd39174436 100644
@@ -1632,6 +1632,8 @@ struct task_struct {
 	struct bpf_run_ctx		*bpf_ctx;
 	/* Set by bpf_task_wake(), consumed by bpf_task_park() */
 	int				bpf_wake_pending;
+	/* On a CPU's queue of deferred bpf_task_wake() calls when not NULL */
+	struct wake_q_node		bpf_wake_node;
 #endif
 	/* Used by BPF for per-TASK xdp storage */
 	struct bpf_net_context		*bpf_net_context;

index b66eb25626c9..a272d11c6caf 100644
@@ -1020,6 +1020,7 @@ static struct task_struct *dup_task_struct(struct task_struct *orig, int node)
 	RCU_INIT_POINTER(tsk->bpf_storage, NULL);
 	tsk->bpf_ctx = NULL;
 	tsk->bpf_wake_pending = 0;
+	tsk->bpf_wake_node.next = NULL;
 #endif
 	return tsk;
 

2.53.0

bpf_task_park() lets a program's run end on another CPU than it started on, and leaves the Tasks Trace RCU read section while it sleeps. Parts of the BPF runtime rely on neither happening:

- The stack in arena is taken from the CPU the run starts on and given back to the CPU it ends on, see bpf_arena_stack_put(). A run that migrates releases the stack of another CPU, which a run there may be using, and leaves its own taken.
- The timed may_goto keeps its count and timestamp per CPU, set when the run starts. After a migration the loop reads the slice of another run, or one that was never set.
- A tail call runs its target on the caller's read section, and nothing else holds the target. A target that parks leaves that section, so deleting it from the prog array frees it under the sleeper. The caller's verifier does not see the park either, so the caller keeps pointers the sleep may free.
- kern_sys_bpf() runs a syscall program between __bpf_prog_enter_sleepable_recur() and its exit, which count the run per CPU. A run that migrates leaves one CPU's count raised for good.

Refuse these combinations until each of them is taught about the park. The verifier records in prog->aux->may_migrate that a program calls a kfunc which may migrate, and refuses the call in a program that uses R12. bpf_do_misc_fixups() refuses to give such a program a timed may_goto. That includes the one the verifier adds to a loop it cannot bound, so a loop in such a program needs a bound of its own, as bpf_repeat() gives it. A prog array refuses the program as a member, and kern_sys_bpf() refuses to run it.

bpf_task_park() is the only such kfunc so far.

---
 include/linux/bpf.h    |  2 ++
 kernel/bpf/arraymap.c  |  7 ++++++-
 kernel/bpf/fixups.c    |  6 ++++++
 kernel/bpf/syscall.c   |  3 ++-
 kernel/bpf/task_park.c | 20 ++++++++++++--------
 kernel/bpf/verifier.c  | 24 ++++++++++++++++++++++++
 6 files changed, 52 insertions(+), 10 deletions(-)

index 520fd72e21fd..5dec537fe688 100644
@@ -1943,6 +1943,8 @@ struct bpf_prog_aux {
 	bool changes_pkt_data;
 	bool has_prologue;
 	bool might_sleep;
+	/* a run may leave on another CPU than it started on, see bpf_task_park() */
+	bool may_migrate;
 	bool can_unwind;
 	/* frames of recursive subprogs can be on the stack when it is called */
 	bool in_recursion;

index 133f189bf6d2..541f0830cf79 100644
@@ -1028,7 +1028,12 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
 	if (IS_ERR(prog))
 		return prog;
 
-	if (prog->type == BPF_PROG_TYPE_EXT ||
+	/*
+	 * A tail call runs the program on the caller's Tasks Trace RCU read
+	 * section alone, and a program that parks leaves that section for its
+	 * sleep, see bpf_task_park().
+	 */
+	if (prog->type == BPF_PROG_TYPE_EXT || prog->aux->may_migrate ||
 	    !bpf_prog_map_compatible(map, prog)) {
 		bpf_prog_put(prog);
 		return ERR_PTR(-EINVAL);

index 1d33a78d9373..df5784a132d7 100644
@@ -2862,6 +2862,12 @@ int bpf_do_misc_fixups(struct bpf_verifier_env *env)
 			u16 live = env->insn_aux_data[i].live_regs_before;
 			int reg, save_off = 0;
 
+			/* The count and the time are kept per cpu, see bpf_timed_may_goto_save(). */
+			if (prog->aux->may_migrate) {
+				verbose(env, "may_goto cannot be used in a program that may migrate, also not in a loop that gets one\n");
+				return -EINVAL;
+			}
+
 			/* a register that is dead here holds the address of the count */
 			for (reg = BPF_REG_0; reg <= BPF_REG_9; reg++)
 				if (!(live & BIT(reg)))

index 9004f2673ccf..3f9728686d05 100644
@@ -6661,8 +6661,9 @@ int kern_sys_bpf(int cmd, union bpf_attr *attr, unsigned int size)
 		if (IS_ERR(prog))
 			return PTR_ERR(prog);
 
+		/* The run is counted per CPU, which a program that migrates would unbalance. */
 		if (attr->test.ctx_size_in < prog->aux->max_ctx_offset ||
-		    attr->test.ctx_size_in > U16_MAX) {
+		    attr->test.ctx_size_in > U16_MAX || prog->aux->may_migrate) {
 			bpf_prog_put(prog);
 			return -EINVAL;
 		}

index 5a9b3124312e..5043ccdfc0b8 100644
@@ -194,14 +194,18 @@ __bpf_kfunc int bpf_task_park(u64 timeout_ns, u64 flags)
 	 * program, and with it its maps and context, for the whole
 	 * invocation, so that the program's own memory needs no grace period,
 	 * and where nothing on the run path keeps per-CPU state across the
-	 * program. The verifier confines the call to such contexts: the main
-	 * body of a syscall program and the functions it calls directly, never
-	 * a callback, and never a region that pins the CPU, a lock, a saved
-	 * IRQ state or an RCU read section. It also invalidates every pointer
-	 * the program holds across the call except its stack, its context,
-	 * maps it references directly and the values of its arrays, arena
-	 * memory and verifier-tracked references. What remains is that the
-	 * program may resume on another CPU, which is part of the contract.
+	 * program. A program that keeps such state itself, a stack in arena or
+	 * the time slice of may_goto, is refused the call, and one that calls
+	 * it is kept out of prog arrays, where the caller of a tail call holds
+	 * it through this very read section. The verifier confines the call to
+	 * such contexts: the main body of a syscall program and the functions it
+	 * calls directly, never a callback, and never a region that pins the
+	 * CPU, a lock, a saved IRQ state or an RCU read section. It also
+	 * invalidates every pointer the program holds across the call except its
+	 * stack, its context, maps it references directly and the values of its
+	 * arrays, arena memory and verifier-tracked references. What remains is
+	 * that the program may resume on another CPU, which is part of the
+	 * contract.
 	 */
 	migrate_enable();
 	rcu_read_unlock_trace();

index 8edc32153226..a1b3ae59a68c 100644
@@ -14459,6 +14459,12 @@ static bool is_bpf_task_park_kfunc(u32 btf_id)
 	return btf_id == special_kfunc_list[KF_bpf_task_park];
 }
 
+/* The kfuncs that sleep or wait with migration enabled. */
+static bool is_migrating_kfunc(u32 btf_id)
+{
+	return btf_id == special_kfunc_list[KF_bpf_task_park];
+}
+
 static bool is_bpf_obj_new_kfunc(u32 func_id)
 {
 	return func_id == special_kfunc_list[KF_bpf_obj_new] ||

@@ -16262,6 +16268,24 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	if (!in_sleepable_context(env))
 		insn_aux->non_sleepable = true;
 
+	/*
+	 * The kfunc may return on another CPU. What a run takes on the CPU it
+	 * starts on and gives back on the CPU it ends on does not survive that.
+	 * The stack in arena is such a thing, see bpf_arena_stack_put(), and
+	 * the time slice of may_goto, which bpf_do_misc_fixups() refuses. For
+	 * the same reason the program is kept out of prog arrays, where it would
+	 * also run without a reference of its own, and away from runners that
+	 * count a run per CPU.
+	 */
+	if (is_migrating_kfunc(meta.func_id)) {
+		if (env->uses_arena_sp) {
+			verbose(env, "%s() cannot be called in a program that uses R%d\n",
+				func_name, BPF_REG_ARENA_SP);
+			return -EINVAL;
+		}
+		env->prog->aux->may_migrate = true;
+	}
+
 	/* Check the arguments */
 	err = check_func_args(env, &meta, insn_idx);
 	if (err < 0)

2.53.0

With the verifier rules in place, make bpf_task_park() callable from BPF_PROG_TYPE_SYSCALL, as a sleepable kfunc.

Syscall programs are the only type for now because their runner, bpf_prog_test_run_syscall(), is the one that has been audited against the sleep. The syscall holds a reference on the program, and through it on its maps, for the whole run, and the runner copies the context into kernel memory first, so neither depends on the Tasks Trace RCU read section the park drops. The run path keeps no per-CPU state across the
program: it has no recursion counter, and __bpf_prog_run() samples its stats only after the program returns, with migration disabled again. Helpers confine their per-CPU scratch to the call that uses it, and the verifier keeps the park out of every region that pins the CPU and out of every callback. What remains is that the program may resume on another CPU, which the comment on bpf_prog_run_pin_on_cpu() now says, since the pin it promises is lifted for the sleep.

Other program types stay off the list. A trampoline-attached sleepable program is freed after a Tasks Trace grace period the sleeper no longer delays and keeps a per-CPU recursion count that a migrating task would leave behind. Each new type needs its runner audited the same way first.

Deferred:

- A program type that runs with migration enabled and without Tasks Trace RCU, so that a BPF thread is a plain kernel-mode function of a user thread and the park needs no bracketing at all. It needs its own runner, since __bpf_prog_run() asserts cant_migrate(); an audit of every kfunc that relies on migration being disabled, starting with bpf_mem_alloc() and its users, per-CPU map lookups and bpf_this_cpu_ptr(); and a verifier rule that confines map helpers and map value pointers to bpf_rcu_read_lock() sections, since the helpers assert bpf_rcu_lock_held() and nothing else would protect the values.
- Registering the park for further program types. Each needs a runner that holds the program across the sleep and no per-CPU recursion count.
- Allowing the park in further callbacks whose kernel caller has been audited, beyond the body of a BPF kthread, which a later patch admits, and retaining dynptr and iterator stack slots beyond bpf_iter_num whose state does not depend on the dropped protection.
- The stack in arena, the timed may_goto and tail calls in a program that parks. Each relies on a run staying on its CPU or under its caller's protection and is refused for now.
- An opt-in flag to park with migration disabled, for per-CPU worker designs that accept the CPU offline cost.
- A per-task marker so that bpf_task_wake() can only wake a task inside bpf_task_park(). Today a wake for a task that is not parked may end an unrelated interruptible sleep of that task, which the kernel contract permits.
- Interoperation with user threads blocked in futex() on a word the program can also reach, such as an arena word.

---
 include/linux/filter.h |  6 ++++++
 kernel/bpf/task_park.c | 15 +++++++++++++++
 2 files changed, 21 insertions(+)

index 61448be53f8d..c30d05a5c26e 100644
@@ -883,6 +883,12 @@ static __always_inline u32 bpf_prog_run(const struct bpf_prog *prog, const void
  * This uses migrate_disable/enable() explicitly to document that the
  * invocation of a BPF program does not require reentrancy protection
  * against a BPF program which is invoked from a preempting task.
+ *
+ * A syscall program may call bpf_task_park(), which lifts the pin for the
+ * duration of its sleep and restores it before returning to the program,
+ * so such a program may resume on another CPU. Nothing on this path keeps
+ * per-CPU state across the program: __bpf_prog_run() samples its stats
+ * only after the program returns.
  */
 static inline u32 bpf_prog_run_pin_on_cpu(const struct bpf_prog *prog,
 					  const void *ctx)

index 5043ccdfc0b8..0e3d7f3ec597 100644
@@ -276,3 +276,18 @@ __bpf_kfunc int bpf_task_wake(struct task_struct *task, u64 flags)
 }
 
 __bpf_kfunc_end_defs();
+
+BTF_KFUNCS_START(bpf_task_park_kfunc_ids)
+BTF_ID_FLAGS(func, bpf_task_park, KF_SLEEPABLE)
+BTF_KFUNCS_END(bpf_task_park_kfunc_ids)
+
+static const struct btf_kfunc_id_set bpf_task_park_kfunc_set = {
+	.owner = THIS_MODULE,
+	.set = &bpf_task_park_kfunc_ids,
+};
+
+static int __init bpf_task_park_kfunc_init(void)
+{
+	return register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &bpf_task_park_kfunc_set);
+}
+late_initcall(bpf_task_park_kfunc_init);

2.53.0

The kernel event that makes a parked task worth waking is usually not one a syscall program sees. A thread parked until memory runs short wants the wakeup of kswapd or the start of direct reclaim to end its sleep; one parked for a queue wants the enqueue, which may happen in a tracing program, a callback of a BPF scheduler or a networking program. The program on that event has the task, as an argument or as a kptr in a map it shares with the waiter.

Register the wake for BPF_PROG_TYPE_UNSPEC, which makes it available to every program type, in a kfunc set of its own. It takes a referenced, trusted, or RCU-protected task, so a task kptr read under bpf_rcu_read_lock() works without a reference per wake. The park stays with syscall programs: the audit that confined it there concerned the runner, which has to hold the program across a sleep that drops its Tasks Trace RCU protection, and the wake sleeps nowhere and touches only the task and its pending word.

What the wake does depend on is a context in which try_to_wake_up() may run. It takes the task's pi_lock and a runqueue lock, and a program can run in kernel code that holds either: a tracing program on sched_waking runs under the pi_lock and one on sched_switch under the rq lock, as do the callbacks of a BPF scheduler, while a perf event program can run in NMI context, where neither lock may be taken. All of these run with IRQs disabled, and a wake asked for with IRQs disabled is queued for irq_work instead of being issued. A program that runs with IRQs enabled holds neither lock, whatever its type, so no program type needs a rule of its own.

---
 kernel/bpf/task_park.c | 20 +++++++++++++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

index 0e3d7f3ec597..9de1b496ead1 100644
@@ -281,13 +281,31 @@ BTF_KFUNCS_START(bpf_task_park_kfunc_ids)
 BTF_ID_FLAGS(func, bpf_task_park, KF_SLEEPABLE)
 BTF_KFUNCS_END(bpf_task_park_kfunc_ids)
 
+BTF_KFUNCS_START(bpf_task_wake_kfunc_ids)
+BTF_ID_FLAGS(func, bpf_task_wake, KF_RCU)
+BTF_KFUNCS_END(bpf_task_wake_kfunc_ids)
+
 static const struct btf_kfunc_id_set bpf_task_park_kfunc_set = {
 	.owner = THIS_MODULE,
 	.set = &bpf_task_park_kfunc_ids,
 };
 
+static const struct btf_kfunc_id_set bpf_task_wake_kfunc_set = {
+	.owner = THIS_MODULE,
+	.set = &bpf_task_wake_kfunc_ids,
+};
+
+/*
+ * The park stays with syscall programs, whose runner holds the program across
+ * the sleep. The wake touches only the task and defers itself where it cannot
+ * be issued, so every program type has it, to wake a parked task from the
+ * kernel event that makes it worth waking.
+ */
 static int __init bpf_task_park_kfunc_init(void)
 {
-	return register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &bpf_task_park_kfunc_set);
+	int ret;
+
+	ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &bpf_task_park_kfunc_set);
+	return ret ?: register_btf_kfunc_id_set(BPF_PROG_TYPE_UNSPEC, &bpf_task_wake_kfunc_set);
 }
 late_initcall(bpf_task_park_kfunc_init);

2.53.0

Currently, a BPF program that wants a thread of its own, to poll a queue or to serve events as they come, has no way to get one. It runs in the tasks that enter the kernel, in a kworker through bpf_wq, or in a task's return to user space through bpf_task_work, each for the length of one invocation and none under the program's control.

Introduce BPF kthreads, kernel threads whose thread function is a callback of the program that created them:

- bpf_kthread_create() creates the thread without starting it. The callback is the body of the thread and runs once: it loops, sleeps and returns on its own, and its return ends the thread, with its return value as the thread's result.
- bpf_kthread_start() runs the callback.
- bpf_kthread_stop() stops the thread and waits for it to exit. A thread cannot stop itself and gets -EDEADLK for trying.
- bpf_kthread_should_stop() tells the callback that a stop is pending, as kthread_should_stop() tells a kernel thread function.

The kernel runs the callback as it runs the body of a sleepable program, with migration disabled under a Tasks Trace RCU read section, and adds nothing around it. Register the kfuncs for BPF_PROG_TYPE_SYSCALL only for now.

The thread is named bpfk/<program id>:<index>, the index counting the threads the program has created, so that a program's controller and its workers are told apart. The prefix is short so that both numbers fit the fifteen characters of comm that tracepoints and perf report, as long as they have nine digits between them; /proc would show a kernel thread's full name anyway.

The program knows the thread by its task_struct. bpf_kthread_create() returns it with a reference of the kind bpf_task_acquire() takes, so that the program keeps the handle where it keeps task pointers, in a kptr of a map value or a graph node, hands it to the other kfuncs, and releases it with bpf_task_release(). The reference is taken before the thread is published on the lists, since from then on any program may stop it, and a stopped thread's exit drops the last reference the task had of its own. The control kfuncs tell a BPF kthread from any other task through a global list of the threads. bpf_kthread_start() takes an RCU-protected task as well, so that a kptr read under bpf_rcu_read_lock() will do.

A thread does not hold a reference on its program. If it did, a program whose user closed every file descriptor would live on through its own threads, with nothing left that could stop them, as a bpf_timer would without the map's user reference count to cancel it. Instead:

- The release of the program's last reference stops the threads it still has, and creation fails once the program has no reference left.
- The threads are stopped before the release waits for a grace period. The release of a sleepable program waits for a Tasks Trace RCU grace period before it frees anything, and a thread inside its callback would hold that up, so the threads are stopped before it, from the work item the release goes through whenever the program has threads.
- A thread whose callback has returned stays until bpf_kthread_stop() collects its result or the program goes, as a thread nobody joined does.

The one exception is a thread that bpf_kthread_stop() is stopping: the stop holds the program for it. The stop takes the thread off the program's list before it waits, so that the release of the program's last reference, which stops the threads it finds on that list, does not stop it a second time. A thread off the list and not yet exited is then held by nobody. It may be asleep in bpf_task_park(), outside the Tasks Trace read section that otherwise keeps the program for it, when the program's last reference goes, for instance because the stopper is a thread of another program and the user closing the last descriptor is unrelated. It would wake into a freed program.

The stop therefore holds a reference on the program from the moment it takes the thread off the list until the thread has exited. It refuses with -ESRCH a thread whose program has no reference left, since that program's release is stopping it. The reference is scoped to the stop rather than to the thread's life because a thread needs no handle to keep running, so a reference held by the thread would keep a program alive forever once its user is gone. The same cycle is what timers and prog_array break through a map's user count, which a program does not have.

Stops that would wait for each other are refused. kthread_stop() waits for the thread's exit in an uninterruptible wait that pays no attention to the waiter's own stop bit, because in the kernel a stopper is never itself a stop target. Here it can be. Two threads that stop each other each set the other's stop bit and each wait for an exit that needs its own wait to return first, with nothing that could end either, and a longer ring of threads behaves the same.

Each thread therefore records, under the lock, the thread it is about to wait for, and a stop walks that chain from its target before taking it. A chain that reaches the caller is refused with -EDEADLK, as a thread stopping itself is. The record and the check are one critical section, so of two threads stopping each other exactly one is refused; its body then sees its own stop bit and returns, and the other's wait completes. Every object on a chain belongs to a thread that has not exited, since a thread clears its record under the lock before it frees the object it points to, so the walk reads live memory.

What remains is bounded only by the callback's cooperation. The kernel cannot make a body return, so a body has to poll bpf_kthread_should_stop() in its loops, as a kernel thread function does, and a body that does not holds its stopper for the length of its loop bounds. That is the limit of a cooperative stop: the kernel has no way to end a program that does not return.

The kfuncs that wait for another task wait with migration enabled. Creation waits for kthreadd and the stop for the thread, and so do the placement kfuncs that follow, which wait for a running thread's next migrate_enable(). The kernel assumes that a task which has disabled migration enables it again soon, and several paths wait for that while holding locks:

- cpuset attach, under cgroup_mutex, cpus_read_lock() and the threadgroup rwsem;
- a cpuset.cpus write, under cpuset_mutex;
- CPU offline, in balance_hotplug_wait().

kthreadd's fork read-locks the threadgroup rwsem as well. A sleepable program is migration-disabled for its whole run and a thread body for its life outside the park, so one of these kfuncs waiting while pinned can close a cycle. A task that creates a thread while a cgroup.procs write moves it into a cpuset waits for kthreadd, whose fork waits for the rwsem the writer holds while the writer waits for the task to enable migration; nothing gives, and no kernel thread can be created anywhere afterwards. That is the default lock mode. Under favordynmods a cgroup.procs write holds only the moved process's own rwsem, but a subtree_control write still takes the global one, and the other cycles stand regardless.

The waits therefore run with migration enabled and the Tasks Trace read section kept. Nothing the read section protects depends on the CPU: the program, its maps and its context are held as before, per-CPU memory stays valid memory, and neither the syscall runner nor bpf_kthread_fn() keeps per-CPU state across the program, which the park established for the runner. The caller may return on another CPU, the contract the park carries too, so a per-CPU map value pointer or a CPU id obtained before such a call names the CPU of the lookup. Unlike the park, which also leaves the read section and so has the verifier invalidate what a grace period could free, these waits keep the program's protection, and the verifier has nothing to invalidate for them. They do count as kfuncs that may migrate: a program that keeps per-CPU state of its own across its run, a stack in arena or the time slice of may_goto, is refused the creation and the stop as it is refused the park, and a program that calls them stays out of prog arrays.

Two things follow from a body being code that the program wrote, running in a task the program can name. bpf_kthread_start() is not sleepable, so a timer callback may call it from softirq and a program may call it with IRQs disabled; the lock that guards the lists is therefore a raw lock taken with IRQs disabled. And a program can queue task work for its own thread. With TWA_SIGNAL that sets TIF_NOTIFY_SIGNAL, which a kernel thread never clears, so the thread blocks the notification for the length of its body. The work then runs when the thread exits, after its stopper may have freed the thread's object, so an exiting thread is no longer treated as a BPF kthread by the stop it may call there.

The verifier checks the callback as a sleepable asynchronous callback. Its one argument, the u64 the creator passed, is a scalar in R1, and its int return is compared in 32 bits, since that is the width it comes back in.

The callback is where the thread's loop goes, and what it can do while it waits for work decides what a BPF kthread is good for. It cannot loop without a bound, and nothing here lets it sleep: the sleep is bpf_task_park(), which drops the migration and RCU protection of a sleepable program for the length of the sleep, and whose verifier rules refuse a park in every callback frame until the next patch admits this one. Until then a kthread polls, and while it polls it keeps migration disabled, which holds off a CPU offline and an affinity change until it returns, as any migration-disabled task does; a thread that parks between checks does not.

---
 include/linux/bpf.h    |   3 +
 include/linux/filter.h |  11 +-
 kernel/bpf/Makefile    |   2 +-
 kernel/bpf/core.c      |   1 +
 kernel/bpf/kthread.c   | 461 +++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/syscall.c   |   9 +-
 kernel/bpf/verifier.c  |  56 ++++-
 7 files changed, 533 insertions(+), 10 deletions(-)
 create mode 100644 kernel/bpf/kthread.c

index 5dec537fe688..7c15593cb188 100644
@@ -2046,6 +2046,8 @@ struct bpf_prog_aux {
 	struct bpf_stream *stream[2];
 	spinlock_t st_ops_assoc_lock; /* protects st_ops_assoc */
 	struct bpf_map __rcu *st_ops_assoc;
+	struct list_head kthreads; /* BPF kthreads of the prog, see kernel/bpf/kthread.c */
+	atomic_t kthread_seq; /* index of the prog's next BPF kthread, in its name */
 };
 
 #define BPF_NR_CONTEXTS        4       /* normal, softirq, hardirq, NMI */

@@ -2970,6 +2972,7 @@ struct bpf_prog * __must_check bpf_prog_inc_not_zero(struct bpf_prog *prog);
 void bpf_prog_put(struct bpf_prog *prog);
 
 void bpf_prog_free_id(struct bpf_prog *prog);
+void bpf_prog_free_kthreads(struct bpf_prog_aux *aux);
 void bpf_map_free_id(struct bpf_map *map);
 
 struct btf_field *btf_record_find(const struct btf_record *rec,

index c30d05a5c26e..8a99b9aacfb0 100644
@@ -884,11 +884,12 @@ static __always_inline u32 bpf_prog_run(const struct bpf_prog *prog, const void
  * invocation of a BPF program does not require reentrancy protection
  * against a BPF program which is invoked from a preempting task.
  *
- * A syscall program may call bpf_task_park(), which lifts the pin for the
- * duration of its sleep and restores it before returning to the program,
- * so such a program may resume on another CPU. Nothing on this path keeps
- * per-CPU state across the program: __bpf_prog_run() samples its stats
- * only after the program returns.
+ * A syscall program may call bpf_task_park(), or a BPF kthread kfunc that
+ * waits for another task, which lift the pin for the duration of the sleep
+ * or wait and restore it before returning to the program, so such a program
+ * may resume on another CPU. Nothing on this path keeps per-CPU state
+ * across the program: __bpf_prog_run() samples its stats only after the
+ * program returns.
  */
 static inline u32 bpf_prog_run_pin_on_cpu(const struct bpf_prog *prog,
 					  const void *ctx)

index 34357665c34c..a754fbefae39 100644
@@ -15,7 +15,7 @@ obj-$(CONFIG_BPF_SYSCALL) += fixups.o cfg.o states.o check_btf.o flow.o join.o
 obj-${CONFIG_BPF_LSM}	  += bpf_inode_storage.o
 obj-$(CONFIG_BPF_SYSCALL) += disasm.o mprog.o
 obj-$(CONFIG_BPF_JIT) += trampoline.o
-obj-$(CONFIG_BPF_SYSCALL) += btf.o memalloc.o rqspinlock.o stream.o task_park.o
+obj-$(CONFIG_BPF_SYSCALL) += btf.o memalloc.o rqspinlock.o stream.o task_park.o kthread.o
 ifeq ($(CONFIG_MMU)$(CONFIG_64BIT),yy)
 obj-$(CONFIG_BPF_SYSCALL) += arena.o range_tree.o
 endif

index f88a1c041a7a..95f4be8ed405 100644
@@ -138,6 +138,7 @@ struct bpf_prog *bpf_prog_alloc_no_stats(unsigned int size, gfp_t gfp_extra_flag
 #ifdef CONFIG_FINEIBT
 	INIT_LIST_HEAD_RCU(&fp->aux->ksym_prefix.lnode);
 #endif
+	INIT_LIST_HEAD(&fp->aux->kthreads);
 	mutex_init(&fp->aux->used_maps_mutex);
 	mutex_init(&fp->aux->ext_mutex);
 	mutex_init(&fp->aux->dst_mutex);

index 3f9728686d05..9ea8c755651e 100644
@@ -2512,6 +2512,12 @@ static void bpf_prog_put_deferred(struct work_struct *work)
 
 	aux = container_of(work, struct bpf_prog_aux, work);
 	prog = aux->prog;
+	/*
+	 * The threads of the prog still run its code, each inside a Tasks
+	 * Trace RCU read section that the grace period below would wait for.
+	 * Stop them first; this waits for each of them to exit.
+	 */
+	bpf_prog_free_kthreads(aux);
 	perf_event_bpf_event(prog, PERF_BPF_EVENT_PROG_UNLOAD, 0);
 	bpf_audit_prog(prog, BPF_AUDIT_UNLOAD);
 	bpf_prog_free_id(prog);

@@ -2523,7 +2529,8 @@ static void __bpf_prog_put(struct bpf_prog *prog)
 	struct bpf_prog_aux *aux = prog->aux;
 
 	if (atomic64_dec_and_test(&aux->refcnt)) {
-		if (in_hardirq() || irqs_disabled()) {
+		/* Stopping the prog's threads blocks, which the direct path may not. */
+		if (in_hardirq() || irqs_disabled() || !list_empty(&aux->kthreads)) {
 			INIT_WORK(&aux->work, bpf_prog_put_deferred);
 			schedule_work(&aux->work);
 		} else {

2.53.0

The body of a BPF kthread is an asynchronous callback, and the verifier refuses bpf_task_park() in every callback frame, so a BPF kthread cannot sleep. It can only poll in a bounded loop with migration disabled, which holds off CPU offline and any change of its affinity for as long as it runs, and stalls every Tasks Trace RCU grace period meanwhile. A thread that serves a queue or ticks a controller spends most of its life waiting, and the one primitive the program has for waiting is closed to it.

The refusal exists because a callback runs from kernel code that keeps state of its own around the call, an iteration position, a timer or work item that owns the program only through Tasks Trace RCU, an exiting task, and none of that code has been audited against a sleep that drops the program's migration and RCU protection. bpf_kthread_fn() has been:
it is the whole of the thread, brackets the callback the way the runner of a syscall program brackets the program, keeps nothing across it, and the program with its maps and code is held until the thread has exited, since the release of the program's last reference stops its threads and waits for them before its code and maps are freed. The callback's one argument is a scalar, so the park has no context pointer to keep alive either.

Mark the frame the kthread callback runs in and let the walk that refuses the park skip it. Callbacks nested under the body, a bpf_loop() body or a timer callback the thread arms, stay refused as anywhere else, and a global function that may park is admitted from the thread body by the same walk. The rules on what survives the park are unchanged: the stack, array map values, arena memory and verifier-tracked references stay, and everything else is looked up again after the sleep.

At runtime the park nests inside the bracketing of bpf_kthread_fn(): it enables migration and leaves the Tasks Trace RCU read section for the sleep and restores both before returning to the callback. A stop request ends the sleep, since kthread_stop() wakes the thread, and the park reports it as -ESHUTDOWN, as does every park after it, so a body that checks bpf_kthread_should_stop() around its park, or the park's return value, returns as before.

The frame flag also takes part in state comparison. A static subprog may be passed both to bpf_kthread_create() and to bpf_wq_set_callback(), and both roles are verified as frame 0 of a sleepable asynchronous state over the same instructions, so a state explored in the kthread role, where the park is admitted, could stand for a state of the workqueue role, where it must be refused, or the reverse. bpf_state_subsumes() and join_func() therefore treat frames that differ in the flag as
different: neither state is taken for the other, and the two are not joined.

---
 include/linux/bpf_verifier.h |  6 ++++++
 kernel/bpf/join.c            |  1 +
 kernel/bpf/kthread.c         | 17 ++++++++++++-----
 kernel/bpf/states.c          |  7 +++++++
 kernel/bpf/task_park.c       | 16 ++++++++--------
 kernel/bpf/verifier.c        | 31 +++++++++++++++++++++----------
 6 files changed, 55 insertions(+), 23 deletions(-)

index 39ff1359adb9..7097bb7033e8 100644
@@ -469,6 +469,12 @@ struct bpf_func_state {
 	bool in_callback_fn;
 	bool in_async_callback_fn;
 	bool in_exception_callback_fn;
+	/*
+	 * The body of a BPF kthread: an async callback whose kernel caller,
+	 * bpf_kthread_fn(), keeps nothing across it that the sleep in
+	 * bpf_task_park() could invalidate, so the park is allowed in it.
+	 */
+	bool in_kthread_fn;
 	bool no_stack_arg_load;
 	/*
 	 * The helper invokes this callback under rcu_read_lock(), so the

index 8bd92af087c0..b63f99c66308 100644
@@ -452,6 +452,7 @@ static bool join_func(struct bpf_join_state *js, struct bpf_func_state *fd,
 			return false;
 		if (fa->in_callback_fn != fb->in_callback_fn ||
 		    fa->in_async_callback_fn != fb->in_async_callback_fn ||
+		    fa->in_kthread_fn != fb->in_kthread_fn ||
 		    fa->in_exception_callback_fn != fb->in_exception_callback_fn ||
 		    fa->in_rcu_callback_fn != fb->in_rcu_callback_fn ||
 		    fa->async_entry_cnt != fb->async_entry_cnt ||

index 3055e427fe76..d8f63461d756 100644
@@ -13,8 +13,8 @@
 /*
  * A BPF kthread is a kernel thread whose thread function is one callback of
  * the program that created it, run once. The callback is the body of the
- * thread: it loops, sleeps and returns on its own, and its return ends the
- * thread. The kernel adds nothing in between.
+ * thread: it loops, sleeps in bpf_task_park() and returns on its own, and its
+ * return ends the thread. The kernel adds nothing in between.
  *
  * The thread is known to the program by its task_struct. bpf_kthread_create()
  * returns it as a referenced pointer, and the control kfuncs take it back, so

@@ -99,9 +99,16 @@ static int bpf_kthread_fn(void *data)
 	/*
 	 * The callback runs as the body of a sleepable program does, with
 	 * migration disabled under a Tasks Trace RCU read section, except
-	 * while it waits in one of the kfuncs the comment at the top names,
-	 * which drop migration disable alone. The verifier checks it as a
-	 * sleepable callback.
+	 * while it sleeps in bpf_task_park(), which drops both for the sleep
+	 * and takes them again before it returns, and while it waits in one
+	 * of the kfuncs the comment at the top names, which drop migration
+	 * disable alone. That is
+	 * safe here for the reason it is safe in a syscall program: this
+	 * function keeps nothing across the callback, and the program, with
+	 * its maps and code, is held until the thread has exited, since the
+	 * release of its last reference stops the thread first. The verifier
+	 * checks the callback as a sleepable callback in which the park is
+	 * allowed.
 	 */
 	/*
 	 * A task work queued for this thread with TWA_SIGNAL sets

index f75161423377..d0db8074928a 100644
@@ -759,6 +759,13 @@ bool bpf_state_subsumes(struct bpf_verifier_env *env, struct bpf_verifier_state
 		insn_idx = bpf_frame_insn_idx(old, i);
 		if (old->frame[i]->callsite != cur->frame[i]->callsite)
 			return false;
+		/*
+		 * The body of a BPF kthread may park where another async
+		 * callback of the same subprog may not, so a state verified
+		 * in one role must not prune the other.
+		 */
+		if (old->frame[i]->in_kthread_fn != cur->frame[i]->in_kthread_fn)
+			return false;
 		if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx))
 			return false;
 	}

index 9de1b496ead1..b6980c1cc1bf 100644
@@ -198,14 +198,14 @@ __bpf_kfunc int bpf_task_park(u64 timeout_ns, u64 flags)
 	 * the time slice of may_goto, is refused the call, and one that calls
 	 * it is kept out of prog arrays, where the caller of a tail call holds
 	 * it through this very read section. The verifier confines the call to
-	 * such contexts: the main body of a syscall program and the functions it
-	 * calls directly, never a callback, and never a region that pins the
-	 * CPU, a lock, a saved IRQ state or an RCU read section. It also
-	 * invalidates every pointer the program holds across the call except its
-	 * stack, its context, maps it references directly and the values of its
-	 * arrays, arena memory and verifier-tracked references. What remains is
-	 * that the program may resume on another CPU, which is part of the
-	 * contract.
+	 * such contexts: the main body of a syscall program or of a BPF kthread
+	 * and the functions either calls directly, never any other callback,
+	 * and never a region that pins the CPU, a lock, a saved IRQ state or an
+	 * RCU read section. It also invalidates every pointer the program holds
+	 * across the call except its stack, its context, maps it references
+	 * directly and the values of its arrays, arena memory and
+	 * verifier-tracked references. What remains is that the program may
+	 * resume on another CPU, which is part of the contract.
 	 */
 	migrate_enable();
 	rcu_read_unlock_trace();

index 0cf0d3a85b35..ee409ac5be77 100644
@@ -11226,14 +11226,22 @@ static void invalidate_non_owning_refs(struct bpf_verifier_env *env)
 }
 
 /*
- * bpf_task_park() is confined to the main body of the program and the
- * functions it calls directly. A callback runs from kernel code that holds
- * state of its own around the call, an iteration position, a work item or
- * timer that owns the program only through Tasks Trace RCU, an exiting task,
- * none of it audited against a sleep that drops the program's protection.
- * Refuse the park in any callback frame, synchronous, asynchronous or
- * exception. Asynchronous callbacks are verified as a state of their own
- * with the callback as frame 0, so the walk over the frames sees them too.
+ * bpf_task_park() is confined to the main body of the program, the body of a
+ * BPF kthread, and the functions either calls directly. Any other callback
+ * runs from kernel code that holds state of its own around the call, an
+ * iteration position, a work item or timer that owns the program only through
+ * Tasks Trace RCU, an exiting task, none of it audited against a sleep that
+ * drops the program's protection. Refuse the park in any such callback frame,
+ * synchronous, asynchronous or exception. Asynchronous callbacks are verified
+ * as a state of their own with the callback as frame 0, so the walk over the
+ * frames sees them too.
+ *
+ * The body of a BPF kthread is the exception because its caller,
+ * bpf_kthread_fn(), is the whole of the thread: it brackets the callback the
+ * way the runner of a syscall program brackets the program, keeps no state
+ * across it, and the program's release stops the thread and waits for it
+ * before anything the callback uses is freed. Callbacks nested under the
+ * body are refused as anywhere else.
  */
 static bool in_callback_frames(struct bpf_verifier_env *env)
 {

@@ -11243,6 +11251,8 @@ static bool in_callback_frames(struct bpf_verifier_env *env)
 	for (i = 0; i <= vstate->curframe; i++) {
 		struct bpf_func_state *frame = vstate->frame[i];
 
+		if (frame->in_kthread_fn)
+			continue;
 		if (frame->in_callback_fn || frame->in_async_callback_fn ||
 		    frame->in_exception_callback_fn)
 			return true;

@@ -12159,7 +12169,7 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 				operation = bpf_diag_fmt(env, "global function %s() that may call bpf_task_park()",
 							 sub_name);
 				bpf_diag_policy(env, *insn_idx, operation, "the call is in a callback",
-						"Call the function from the main program or from a function it calls directly, not from a callback.");
+						"Call the function from the main program, from the body of a BPF kthread, or from a function either calls directly, not from any other callback.");
 				return -EINVAL;
 			}
 			err = check_park_stack_objects(env, *insn_idx);

@@ -12661,6 +12671,7 @@ static int set_kthread_callback_state(struct bpf_verifier_env *env,
 	bpf_mark_reg_not_init(env, &callee->regs[BPF_REG_4]);
 	bpf_mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
 	callee->in_async_callback_fn = true;
+	callee->in_kthread_fn = true;
 	/*
 	 * The callback returns an int, which comes back in the low 32 bits of
 	 * R0: compare those, as for a global function.

@@ -16511,7 +16522,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		if (in_callback_frames(env)) {
 			verbose(env, "bpf_task_park() is not allowed in a callback\n");
 			bpf_diag_policy(env, insn_idx, "kfunc bpf_task_park", "the call is in a callback",
-					"Call bpf_task_park() from the main program or from a function it calls directly, not from a callback.");
+					"Call bpf_task_park() from the main program, from the body of a BPF kthread, or from a function either calls directly, not from any other callback.");
 			return -EINVAL;
 		}
 		err = check_park_stack_objects(env, insn_idx);

2.53.0

A BPF kthread that services a per-CPU resource, such as a NAPI instance whose interrupt lands on a fixed CPU, wants to run where that resource lives. The program can read the thread's PID from its task and leave the placement to user space, but a program that creates threads as its load demands should not need a round trip through user space to place each one.

Add bpf_kthread_bind(), which restricts the thread to one CPU through set_cpus_allowed_ptr(). A thread that has not been started wakes on that CPU; one that has moves there at its next park or return, when it enables migration, and the call waits for that. The wait runs with migration enabled, for the reason given with the stop: a bind made while pinned could be the far side of a wait for the caller's own migrate_enable(), a bind or a stop issued by the thread being bound, and the two would wait on each other forever. It also lets a thread bind itself, which the scheduler refuses with a warning for a migration-disabled task whose target is not the CPU it is on.

Unlike kthread_bind() it leaves the affinity changeable from user space and subject to cpusets, like that of any other task, with one difference from a user's own affinity: the bind is not remembered as a user mask, so a cpuset.cpus write on the thread's cgroup resets the thread to the whole cpuset, as the CPU going offline does, where a user task's mask would be re-applied. The scheduler moves the thread, or places it elsewhere at its next wakeup. A change of the housekeeping CPUs resets the affinity too, as it does for every kernel thread that is not bound for good. A program that needs the binding re-applies it. The binding sticks whenever it is applied: the generic kthread prologue applies the default affinity of the thread's node when the thread first runs, which is why bpf_kthread_create() runs every thread through that prologue before it returns.

---
 kernel/bpf/kthread.c  | 48 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c |  5 ++++-
 2 files changed, 52 insertions(+), 1 deletion(-)

index d8f63461d756..444fff4bd102 100644
@@ -4,6 +4,7 @@
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/btf_ids.h>
+#include <linux/cpumask.h>
 #include <linux/kthread.h>
 #include <linux/rcupdate_trace.h>
 #include <linux/sched.h>

@@ -350,6 +351,52 @@ __bpf_kfunc int bpf_kthread_start(struct task_struct *task, u64 flags)
 	return 0;
 }
 
+/**
+ * bpf_kthread_bind - Restrict a BPF kthread to one CPU
+ * @task: a thread created by bpf_kthread_create()
+ * @cpu: the CPU the thread is to run on
+ * @flags: must be 0
+ *
+ * Sets the thread's affinity to @cpu. A thread that has not been started wakes
+ * on @cpu; one that has moves there at its next park or return, since its
+ * callback runs with migration disabled, and the call waits for that with
+ * migration enabled, so the caller may return on another CPU and a thread may
+ * bind itself. Unlike kthread_bind(), this leaves the affinity changeable from
+ * user space and subject to cpusets, like that of any other task. The binding
+ * is lost when @cpu goes offline or when the cpuset of the thread's cgroup
+ * changes its CPUs: the thread is moved, or placed elsewhere at its next
+ * wakeup, and its affinity reset to the cpuset's CPUs, as a user task's is
+ * after an offline. It is also lost when the housekeeping CPUs change, which
+ * resets the affinity of every kernel thread that is not bound for good. A
+ * program that needs the binding re-applies it.
+ *
+ * Return: 0 on success, -EINVAL if @flags is not 0 or @cpu is not a possible
+ * CPU or is offline, -ESRCH if @task is not a BPF kthread or has been stopped.
+ */
+__bpf_kfunc int bpf_kthread_bind(struct task_struct *task, u32 cpu, u64 flags)
+{
+	unsigned long irqflags;
+	bool found;
+	int ret;
+
+	if (flags)
+		return -EINVAL;
+	if (cpu >= nr_cpu_ids || !cpu_possible(cpu))
+		return -EINVAL;
+
+	raw_spin_lock_irqsave(&bpf_kthreads_lock, irqflags);
+	found = !!bpf_kthread_find(task);
+	raw_spin_unlock_irqrestore(&bpf_kthreads_lock, irqflags);
+	if (!found)
+		return -ESRCH;
+
+	/* A running thread moves at its next park: see the comment at the top. */
+	migrate_enable();
+	ret = set_cpus_allowed_ptr(task, cpumask_of(cpu));
+	migrate_disable();
+	return ret;
+}
+
 /**
  * bpf_kthread_stop - Stop a BPF kthread and wait for it to exit
  * @task: a thread created by bpf_kthread_create()

@@ -452,6 +499,7 @@ __bpf_kfunc_end_defs();
 BTF_KFUNCS_START(bpf_kthread_kfunc_ids)
 BTF_ID_FLAGS(func, bpf_kthread_create, KF_ACQUIRE | KF_RET_NULL | KF_SLEEPABLE | KF_IMPLICIT_ARGS)
 BTF_ID_FLAGS(func, bpf_kthread_start, KF_RCU)
+BTF_ID_FLAGS(func, bpf_kthread_bind, KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_kthread_stop, KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_kthread_should_stop)
 BTF_KFUNCS_END(bpf_kthread_kfunc_ids)

index ee409ac5be77..54fc44dd8fcc 100644
@@ -14366,6 +14366,7 @@ enum special_kfunc_type {
 	KF_bpf_call_rcu_tasks_trace,
 	KF_bpf_kthread_create,
 	KF_bpf_kthread_stop,
+	KF_bpf_kthread_bind,
 	KF_bpf_arena_alloc_pages,
 	KF_bpf_arena_free_pages,
 	KF_bpf_session_is_return,

@@ -14461,6 +14462,7 @@ BTF_ID(func, bpf_call_rcu)
 BTF_ID(func, bpf_call_rcu_tasks_trace)
 BTF_ID(func, bpf_kthread_create)
 BTF_ID(func, bpf_kthread_stop)
+BTF_ID(func, bpf_kthread_bind)
 #if defined(CONFIG_MMU) && defined(CONFIG_64BIT)
 BTF_ID(func, bpf_arena_alloc_pages)
 BTF_ID(func, bpf_arena_free_pages)

@@ -14507,7 +14509,8 @@ static bool is_migrating_kfunc(u32 btf_id)
 {
 	return btf_id == special_kfunc_list[KF_bpf_task_park] ||
 	       btf_id == special_kfunc_list[KF_bpf_kthread_create] ||
-	       btf_id == special_kfunc_list[KF_bpf_kthread_stop];
+	       btf_id == special_kfunc_list[KF_bpf_kthread_stop] ||
+	       btf_id == special_kfunc_list[KF_bpf_kthread_bind];
 }
 
 static bool is_bpf_obj_new_kfunc(u32 func_id)

2.53.0

A BPF kthread runs in the root cgroup, as every kernel thread does, so whatever it does is accounted to nobody. A pool of reclaim workers that serves one memory cgroup each, or a thread that does a container's work on its behalf, should have its CPU time and the pressure it causes charged to the cgroup it works for, and should run within that cgroup's cpuset. The program can read the thread's PID and leave the placement to user space, but the thread then runs unplaced until a round trip through user space completes, and a program that creates threads as its load demands has no user space thread waiting for each one.

Add bpf_kthread_attach_cgroup(), which moves the thread into a cgroup the program names, usually one it got from bpf_cgroup_from_id(). The cgroup core gains cgroup_attach_kthread() for it, which is what writing the thread's PID to cgroup.procs does once the permission check, which the program's privilege covers, is left out: it takes cgroup_mutex, cpus_read_lock() and the threadgroup rwsem, the moved process's own under favordynmods as cgroup.procs does, refuses a dying cgroup and one that cannot host processes on the default hierarchy, and migrates the thread as a thread group of one. The thread then counts as a member of the cgroup, which
cannot be removed until the thread leaves or exits; a program that places threads in cgroups it does not own has to stop them when the cgroup's owner wants it gone, which is why the move is a separate call and not a parameter of the creation. A cpuset applies its CPUs when the thread joins, so a bind has to follow the move.

The move does not make the thread a user task. Kernel memory it allocates is still charged to no memory cgroup, and it is not frozen with the cgroup, which then never reports frozen, as with any kernel thread in a cgroup.

A running thread joins a cpuset at its next park, and the move waits for that under cgroup_mutex, cpus_read_lock() and the threadgroup rwsem, so it runs with migration enabled, as the stop and the bind do. Pinned, it could wait for a thread that is itself waiting for the caller to enable migration, through a cpuset writer or through a stop, and a thread on a CPU going offline could wait for cpus_read_lock() while the offline waits for the thread to enable migration; migratable, the caller satisfies whatever waits for it and the move completes. The core helper refuses what
cgroup_procs_write_start() refuses, a task that may not migrate between cgroups or that has PF_NO_SETAFFINITY, and leaves a thread whose callback has returned where it is, as cgroup.procs leaves an exiting task.

---
 include/linux/cgroup.h |  3 +++
 kernel/bpf/kthread.c   | 56 ++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c  |  9 ++++++-
 kernel/cgroup/cgroup.c | 45 +++++++++++++++++++++++++++++++++
 4 files changed, 112 insertions(+), 1 deletion(-)

index 2afb4cb2bb4f..f649973801f4 100644
@@ -158,6 +158,7 @@ struct cgroup *cgroup_v1v2_get_from_fd(int fd);
 bool cgroup1_ssid_disabled(int ssid);
 
 int cgroup_attach_task_all(struct task_struct *from, struct task_struct *);
+int cgroup_attach_kthread(struct cgroup *dst_cgrp, struct task_struct *task);
 int cgroup_transfer_tasks(struct cgroup *to, struct cgroup *from);
 
 int cgroup_add_dfl_cftypes(struct cgroup_subsys *ss, struct cftype *cfts);

@@ -804,6 +805,8 @@ static inline void cgroup_lock(void) {}
 static inline void cgroup_unlock(void) {}
 static inline int cgroup_attach_task_all(struct task_struct *from,
 					 struct task_struct *t) { return 0; }
+static inline int cgroup_attach_kthread(struct cgroup *dst_cgrp,
+					struct task_struct *task) { return -ENODEV; }
 static inline int cgroupstats_build(struct cgroupstats *stats,
 				    struct dentry *dentry) { return -EINVAL; }
 

index 54fc44dd8fcc..e7769999e8c3 100644
@@ -14367,6 +14367,7 @@ enum special_kfunc_type {
 	KF_bpf_kthread_create,
 	KF_bpf_kthread_stop,
 	KF_bpf_kthread_bind,
+	KF_bpf_kthread_attach_cgroup,
 	KF_bpf_arena_alloc_pages,
 	KF_bpf_arena_free_pages,
 	KF_bpf_session_is_return,

@@ -14463,6 +14464,11 @@ BTF_ID(func, bpf_call_rcu_tasks_trace)
 BTF_ID(func, bpf_kthread_create)
 BTF_ID(func, bpf_kthread_stop)
 BTF_ID(func, bpf_kthread_bind)
+#ifdef CONFIG_CGROUPS
+BTF_ID(func, bpf_kthread_attach_cgroup)
+#else
+BTF_ID_UNUSED
+#endif
 #if defined(CONFIG_MMU) && defined(CONFIG_64BIT)
 BTF_ID(func, bpf_arena_alloc_pages)
 BTF_ID(func, bpf_arena_free_pages)

@@ -14510,7 +14516,8 @@ static bool is_migrating_kfunc(u32 btf_id)
 	return btf_id == special_kfunc_list[KF_bpf_task_park] ||
 	       btf_id == special_kfunc_list[KF_bpf_kthread_create] ||
 	       btf_id == special_kfunc_list[KF_bpf_kthread_stop] ||
-	       btf_id == special_kfunc_list[KF_bpf_kthread_bind];
+	       btf_id == special_kfunc_list[KF_bpf_kthread_bind] ||
+	       btf_id == special_kfunc_list[KF_bpf_kthread_attach_cgroup];
 }
 
 static bool is_bpf_obj_new_kfunc(u32 func_id)

2.53.0

Cover the runtime behaviour of the two kfuncs with the intended pattern. The waiter resets a condition in a map value, publishes itself through a task kptr, and loops on the condition around the park. The element is a value of an array map, which the program holds, so the loop keeps its pointer across the park; a value of a hash map would have to be looked up again on every turn. The waker loads the published task under bpf_rcu_read_lock(), and only if it finds one sets the condition and wakes it.

That order in the waker is what makes the wake test deterministic. If the waker set the condition first and then looked for a task, a turn that landed between the waiter's reset of the condition and its publication would set the condition with nobody to wake; the waiter would then see it set, return without any wake having reached it, and every later wake would find no task. The test would fail on a legal interleaving. Setting the condition only once a task is found closes the window: the waiter returns 0 only after a wake run that found it, and such a run reports 0 or 1. It is also the order the kfunc's release store pairs with: a park that consumes the wake sees the condition on its next look.

The subtests check that a park with nobody to wake it times out; that a wake delivered to a running task makes the next park return at once, even a poll with a zero timeout, and that the park consumes it so a second poll times out; that a waiter blocked with a timer returns 0 once a waker has found it and set the condition; that a waiter blocked without a timer is found asleep, which is made deterministic by waiting until the thread shows as sleeping in /proc before issuing the one wake that must return 1; that a signal ends the wait with -EINTR on the next park; that non-zero flags are rejected; and that a prog array takes a syscall program that wakes but refuses one that parks, which would otherwise sleep as the target of a tail call.

The waiter's park is bounded by a 10 second timeout from a global the harness can change, so that a lost wake fails the affected subtest with a timeout instead of hanging the run until the test_progs watchdog fires. Only the asleep subtest removes the bound, for the one park it observes, and restores it before draining the waiter.

---
 .../testing/selftests/bpf/bpf_experimental.h  |   3 +
 .../selftests/bpf/prog_tests/task_park.c      | 240 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/task_park.c | 172 +++++++++++++
 3 files changed, 415 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/task_park.c
 create mode 100644 tools/testing/selftests/bpf/progs/task_park.c

index 2893bf06ff25..ccb6e749edd5 100644
@@ -351,6 +351,9 @@ extern void bpf_iter_css_destroy(struct bpf_iter_css *it) __weak __ksym;
 extern int bpf_wq_init(struct bpf_wq *wq, void *p__map, unsigned int flags) __weak __ksym;
 extern int bpf_wq_start(struct bpf_wq *wq, unsigned int flags) __weak __ksym;
 
+extern int bpf_task_park(__u64 timeout_ns, __u64 flags) __weak __ksym;
+extern int bpf_task_wake(struct task_struct *task, __u64 flags) __weak __ksym;
+
 struct bpf_iter_kmem_cache;
 extern int bpf_iter_kmem_cache_new(struct bpf_iter_kmem_cache *it) __weak __ksym;
 extern struct kmem_cache *bpf_iter_kmem_cache_next(struct bpf_iter_kmem_cache *it) __weak __ksym;

2.53.0

Pin the verifier's contract for a park in the main program: what the sleep lets go, what the program keeps, and where the call is refused.

Gone after the park: a hash map value, in a register or spilled to the stack, since a concurrent delete frees the element after a grace period the sleeper no longer delays; a per-CPU array value, since the task may resume on another CPU; a trusted task pointer without a reference; an inner map pointer found through a map-in-map lookup, and a value of that inner map even though the inner map is an array, since only the outer element holds it.

Kept: a referenced task; the stack; the context; an arena pointer; the pointer to a map the program references directly; a value of the program's own array map, which the map allocates and frees with itself; and a global variable read in a loop around the park, which is the case that matters in practice, since globals are array values and the compiler hoists their address out of the loop. Whether it hoists is its own choice, so the hoisted form is pinned in assembly as well.

Refused: a live dynptr on the stack, local or ringbuf-backed, and a live bits iterator, both named with their frame, because the verifier can neither invalidate them without breaking the slot invariants nor release them on the program's behalf; the tests match the frame only, since the stack offset depends on the compiler. A bpf_iter_num loop around a park is accepted, since its state lives on the stack. Also
refused: a park under bpf_spin_lock or bpf_res_spin_lock, inside an RCU read section, a preempt-disabled region or an IRQ-disabled region, each with the verifier's exact message, and a park from a program type it is not registered for. The wake is registered for every type, which an XDP program that wakes pins.

Refused for now as well, since each keeps state per CPU across the run:
a park in a program with a may_goto, be it the program's own or the one the verifier adds to a loop without a bound, and a park in a program that uses the stack in arena, which is tested next to the other uses of R12.

For bpf_task_wake(), an untrusted task pointer and a possibly NULL RCU pointer are refused, while a task kptr read under bpf_rcu_read_lock() and checked for NULL is accepted.

The context test is load-only on purpose: the test runner refuses a context smaller than what the program reads, and the test loader passes none.

---
 .../selftests/bpf/prog_tests/task_park.c      |   3 +
 .../bpf/progs/verifier_arena_stack.c          |  27 +
 .../selftests/bpf/progs/verifier_task_park.c  | 550 ++++++++++++++++++
 3 files changed, 580 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_task_park.c

index a65539fdc412..2ba4c24ae598 100644
@@ -6,6 +6,7 @@
 #include <signal.h>
 #include <sys/syscall.h>
 #include "task_park.skel.h"
+#include "verifier_task_park.skel.h"
 
 static int run_syscall_prog(struct bpf_program *prog, __u32 *retval)
 {

@@ -219,6 +220,8 @@ void test_task_park(void)
 {
 	struct task_park *skel;
 
+	RUN_TESTS(verifier_task_park);
+
 	skel = task_park__open_and_load();
 	if (!ASSERT_OK_PTR(skel, "open_and_load"))
 		return;

index b46e30a9c67f..e09a9ce10187 100644
@@ -1307,6 +1307,33 @@ __naked void packet_write_prologue(void)
 	: __clobber_all);
 }
 
+extern int bpf_task_park(__u64 timeout_ns, __u64 flags) __ksym;
+
+/* the call is in asm, which gives the kfunc no BTF */
+void __park_btf_root(void)
+{
+	bpf_task_park(0, 0);
+}
+
+/* The stack goes back to the cpu that the run ends on, and a park may change that cpu. */
+SEC("syscall")
+__description("arena stack: a program that parks")
+__failure __msg("bpf_task_park() cannot be called in a program that uses R12")
+__naked void parks(void)
+{
+	asm volatile (
+	".8byte %[adj];"
+	"r1 = 0;"
+	"r2 = 0;"
+	"call %[bpf_task_park];"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm_insn(adj, ADJ(16)),
+	  __imm(bpf_task_park)
+	: __clobber_all);
+}
+
 #endif
 
 char _license[] SEC("license") = "GPL";

2.53.0

Pin where a park may sit in the call graph and what the frames above it lose.

A park in a static function and a park in a global function called directly from the main program are both accepted and both return the timeout. In either case the caller's hash map value does not survive the call: for the static function because a function that parks is verified in the state of its caller, where the park sees every frame, for the global function because the call site applies the might_park mark the CFG pass propagated. The mark travels: a static function that calls the global one invalidates its caller's value the same way, and so does a global function that calls the static one and sleeps in a helper of its own, where merging the callee's marks changes nothing but might_park. A dynptr or a bits iterator the caller holds across a global call that parks is refused with the same message as across the park itself.

With callx the function that parks may be called by a function that did not load its address. Such a caller has no mark and is verified on its own, without the frames above it, until its exit reports the park. A program that passes the address of the parking function to it loses its hash map value across the call all the same, and a bpf_loop() callback that does so is refused with the callback message.

No callback other than the body of a BPF kthread, which has its own tests, may park. A bpf_loop() callback and a bpf_for_each_map_elem() callback that call the kfunc directly, one that calls a static function which parks, a bpf_wq callback and a bpf_task_work callback, which the verifier checks as states of their own with the callback as frame 0, and the exception callback are all refused with the callback message. A bpf_loop() callback that calls a global function which parks, directly or through a second global function, is refused at the call site with the message naming the function it called, since the callee is verified without knowledge of its callers.

---
 .../selftests/bpf/prog_tests/task_park.c      |   2 +
 .../bpf/progs/verifier_task_park_frames.c     | 393 ++++++++++++++++++
 2 files changed, 395 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_task_park_frames.c

index 2ba4c24ae598..43514132e6e9 100644
@@ -7,6 +7,7 @@
 #include <sys/syscall.h>
 #include "task_park.skel.h"
 #include "verifier_task_park.skel.h"
+#include "verifier_task_park_frames.skel.h"
 
 static int run_syscall_prog(struct bpf_program *prog, __u32 *retval)
 {

@@ -221,6 +222,7 @@ void test_task_park(void)
 	struct task_park *skel;
 
 	RUN_TESTS(verifier_task_park);
+	RUN_TESTS(verifier_task_park_frames);
 
 	skel = task_park__open_and_load();
 	if (!ASSERT_OK_PTR(skel, "open_and_load"))

2.53.0

Wake the parked waiter from a tracing program in both of the contexts the wake distinguishes. Attached to task_rename, the program runs in process context when the test thread renames itself, so its wake is direct and reports that it found the task asleep. Attached to sched_waking, it runs when the test thread's own sleep ends, inside try_to_wake_up() with the thread's pi_lock held and IRQs disabled, so its wake is deferred to irq_work and returns 2, and the park ends when the irq_work runs. In each case the test checks that the waiter returned before the syscall drain was tried, which runs only as a fallback so that a lost wake fails the test instead of hanging it. The program is attached only once the waiter sleeps, since the thread's polling sleeps are wakeups of its own.

---
 .../selftests/bpf/prog_tests/task_park.c      | 66 +++++++++++++++++++
 tools/testing/selftests/bpf/progs/task_park.c | 48 +++++++++++++-
 2 files changed, 113 insertions(+), 1 deletion(-)

index 43514132e6e9..a479a183c696 100644
@@ -4,6 +4,7 @@
 #include <test_progs.h>
 #include <pthread.h>
 #include <signal.h>
+#include <sys/prctl.h>
 #include <sys/syscall.h>
 #include "task_park.skel.h"
 #include "verifier_task_park.skel.h"

@@ -169,6 +170,67 @@ static void test_wake_asleep(struct task_park *skel)
 	skel->data->park_timeout_ns = timeout;
 }
 
+/*
+ * Wait until the waiter sleeps, attach the tracing program @prog, let @fire
+ * raise its event for this thread, and check that the program's wake, not the
+ * syscall drain, ended the park and returned @expected_ret. The program
+ * attaches only once the waiter sleeps, since the polling sleeps of this
+ * thread are events of its own, and the drain runs only if the event failed.
+ */
+static void test_wake_tracing(struct task_park *skel, struct bpf_program *prog,
+			      int (*fire)(void), int expected_ret)
+{
+	__u64 timeout = skel->data->park_timeout_ns;
+	struct bpf_link *link = NULL;
+	struct waiter w;
+	bool woken;
+	int i;
+
+	skel->data->park_timeout_ns = ~0ULL;
+	skel->bss->waker_tid = syscall(SYS_gettid);
+	skel->data->tracing_wake_ret = -1;
+	if (!ASSERT_OK(start_waiter(&w, skel->progs.park_until_woken), "pthread_create"))
+		goto out;
+	for (i = 0; i < 5000 && !waiter_sleeping(&w); i++)
+		usleep(1000);
+	if (ASSERT_TRUE(waiter_sleeping(&w), "waiter_sleeping")) {
+		link = bpf_program__attach(prog);
+		if (ASSERT_OK_PTR(link, "attach"))
+			ASSERT_OK(fire(), "fire");
+	}
+	for (i = 0; i < 5000 && !waiter_done(&w); i++)
+		usleep(1000);
+	woken = waiter_done(&w);
+	bpf_link__destroy(link);
+	/* Bound any further park before draining, so a lost wake cannot hang the join. */
+	skel->data->park_timeout_ns = timeout;
+	if (!woken)
+		wake_until_done(skel, &w);
+	pthread_join(w.thread, NULL);
+	ASSERT_TRUE(woken, "woken_by_tracing_prog");
+	ASSERT_EQ(skel->data->tracing_wake_ret, expected_ret, "tracing_wake_ret");
+	ASSERT_OK(w.err, "park_until_woken");
+	ASSERT_EQ((__s32)w.retval, 0, "wake_park_ret");
+out:
+	skel->data->park_timeout_ns = timeout;
+}
+
+/* Renaming the thread to its own name still fires task_rename. */
+static int rename_self(void)
+{
+	char comm[16];
+
+	if (prctl(PR_GET_NAME, comm))
+		return -errno;
+	return prctl(PR_SET_NAME, comm) ? -errno : 0;
+}
+
+/* The timer that ends this sleep wakes the thread, which fires sched_waking. */
+static int sleep_self(void)
+{
+	return usleep(1000) ? -errno : 0;
+}
+
 static void sig_noop(int sig)
 {
 }

@@ -237,6 +299,10 @@ void test_task_park(void)
 		test_wake(skel);
 	if (test__start_subtest("wake_asleep"))
 		test_wake_asleep(skel);
+	if (test__start_subtest("wake_tracing"))
+		test_wake_tracing(skel, skel->progs.wake_on_rename, rename_self, 1);
+	if (test__start_subtest("wake_tracing_deferred"))
+		test_wake_tracing(skel, skel->progs.wake_on_waking, sleep_self, 2);
 	if (test__start_subtest("prog_array"))
 		test_prog_array(skel);
 	if (test__start_subtest("signal"))

2.53.0

Exercise the kthread kfuncs from syscall programs. The thread's body records its PID and parks until the test wakes it to return or a stop is pending. The subtests cover a thread that exits through its callback's return and reports that return to a later stop; a stop that ends a running callback through bpf_kthread_should_stop(); what the park returns to a thread that is being stopped, -ESHUTDOWN from then on except when it has a wake to consume; a stop before the start, which
runs no callback and reports -EINTR; a start through an RCU-protected kptr and a repeated start; a thread that cannot stop itself; a thread that creates and starts another from its callback; the control kfuncs on a task that is no BPF kthread, nonzero flags, and bpf_kthread_should_stop() from a thread of a user process; the thread's name; and the stop of a running thread when the last reference on its program goes.

The verifier cases pin the reference the creation returns and the program must release, the callback's scalar argument and 32-bit return, a callback that creates a thread, the task pointers the control kfuncs take, the registration for syscall programs only, and the refusal of may_goto in a program that creates a thread, since the creation may migrate.

The worker bodies sleep in bpf_task_park() between their checks, with a timeout of ten seconds, well past what any test waits, so that a lost wake fails a test instead of being covered by the timeout. The start_exit test checks that the thread sleeps before it wakes it to return. The verifier tests check that the park is allowed in the body and in a global function the body calls, and refused in a bpf_loop() callback under the body, directly or through that function. The name check expects the program's thread index after its id both in the full name /proc reports and in the comm the thread reads for itself with bpf_get_current_comm(), and the spawn test checks the second thread's index. A callback that indexes an array with its argument checks that the argument is a scalar the body can bound, and a global function that creates a thread with a parking body loads when called from a bpf_wq callback, since taking the body's address does not make the function park.

Two threads stopping each other, and three in a ring, exercise the refusal of the stop that would close a ring of waits: each thread waits until all of them are about to stop, or until its own stop arrives, so that the waits do form a ring, exactly one stop returns -EDEADLK, the others return their successor's exit code as the ring unwinds, every thread exits, and only the thread the refused stop was aimed at is left in its slot for the test to collect.

---
 .../testing/selftests/bpf/bpf_experimental.h  |   6 +
 .../selftests/bpf/prog_tests/bpf_kthread.c    | 434 ++++++++++++++++++
 .../testing/selftests/bpf/progs/bpf_kthread.c | 334 ++++++++++++++
 .../bpf/progs/verifier_bpf_kthread.c          | 398 ++++++++++++++++
 4 files changed, 1172 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_kthread.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_kthread.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_bpf_kthread.c

index ccb6e749edd5..0fcb969ba034 100644
@@ -354,6 +354,12 @@ extern int bpf_wq_start(struct bpf_wq *wq, unsigned int flags) __weak __ksym;
 extern int bpf_task_park(__u64 timeout_ns, __u64 flags) __weak __ksym;
 extern int bpf_task_wake(struct task_struct *task, __u64 flags) __weak __ksym;
 
+extern struct task_struct *bpf_kthread_create(int (callback_fn)(__u64 arg), __u64 arg,
+					      __u64 flags) __weak __ksym;
+extern int bpf_kthread_start(struct task_struct *task, __u64 flags) __weak __ksym;
+extern int bpf_kthread_stop(struct task_struct *task, __u64 flags) __weak __ksym;
+extern bool bpf_kthread_should_stop(void) __weak __ksym;
+
 struct bpf_iter_kmem_cache;
 extern int bpf_iter_kmem_cache_new(struct bpf_iter_kmem_cache *it) __weak __ksym;
 extern struct kmem_cache *bpf_iter_kmem_cache_next(struct bpf_iter_kmem_cache *it) __weak __ksym;

2.53.0

Bind a parked thread to the lowest CPU the test may run on and then to the highest, start it, and check that its callback runs on the highest. Also check that an impossible CPU is refused. A bind while the thread runs moves it as well: the body parks with migration enabled, so the bind completes at once, and the thread's next iteration, after a wake, records the new CPU. A thread also binds itself from its body and runs its first iteration on that CPU, since it is migratable during the call. The tests wait for the body's first iteration, not only for its entry, before they read the CPU it recorded.

---
 .../testing/selftests/bpf/bpf_experimental.h  |   1 +
 .../selftests/bpf/prog_tests/bpf_kthread.c    | 123 +++++++++++++++++-
 .../testing/selftests/bpf/progs/bpf_kthread.c |  49 ++++++-
 3 files changed, 166 insertions(+), 7 deletions(-)

index 0fcb969ba034..e41d326a0017 100644
@@ -357,6 +357,7 @@ extern int bpf_task_wake(struct task_struct *task, __u64 flags) __weak __ksym;
 extern struct task_struct *bpf_kthread_create(int (callback_fn)(__u64 arg), __u64 arg,
 					      __u64 flags) __weak __ksym;
 extern int bpf_kthread_start(struct task_struct *task, __u64 flags) __weak __ksym;
+extern int bpf_kthread_bind(struct task_struct *task, __u32 cpu, __u64 flags) __weak __ksym;
 extern int bpf_kthread_stop(struct task_struct *task, __u64 flags) __weak __ksym;
 extern bool bpf_kthread_should_stop(void) __weak __ksym;
 

2.53.0

Move a thread into a cgroup before its start and into another while it runs, and check through bpf_get_current_cgroup_id() in its body that each move took effect by its next iteration. The thread populates the cgroup it is in, which cgroup.events reports, and the cgroup it left is empty again; after the stop the second cgroup empties too, once the thread's exit has left it, which the test waits for since kthread_stop() returns before cgroup_exit() runs. The test's work directory has controllers enabled for its children, so a move into it is refused with -EBUSY, the constraint cgroup.procs enforces; the check needs a domain controller enabled there, since threaded controllers alone leave the parent able to hold processes, and is skipped otherwise. Nonzero flags and a task that is no BPF kthread are refused as by the other control kfuncs.

---
 .../testing/selftests/bpf/bpf_experimental.h  |  2 +
 .../selftests/bpf/prog_tests/bpf_kthread.c    | 88 +++++++++++++++++++
 .../testing/selftests/bpf/progs/bpf_kthread.c | 43 ++++++++-
 3 files changed, 132 insertions(+), 1 deletion(-)

index e41d326a0017..49d7a45f9707 100644
@@ -358,6 +358,8 @@ extern struct task_struct *bpf_kthread_create(int (callback_fn)(__u64 arg), __u6
 					      __u64 flags) __weak __ksym;
 extern int bpf_kthread_start(struct task_struct *task, __u64 flags) __weak __ksym;
 extern int bpf_kthread_bind(struct task_struct *task, __u32 cpu, __u64 flags) __weak __ksym;
+extern int bpf_kthread_attach_cgroup(struct task_struct *task, struct cgroup *cgrp,
+				     __u64 flags) __weak __ksym;
 extern int bpf_kthread_stop(struct task_struct *task, __u64 flags) __weak __ksym;
 extern bool bpf_kthread_should_stop(void) __weak __ksym;
 

2.53.0