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. Signed-off-by: Kumar Kartikeya Dwivedi --- include/linux/sched.h | 2 + kernel/bpf/task_park.c | 86 +++++++++++++++++++++++++++++++++++++++++- kernel/fork.c | 1 + 3 files changed, 87 insertions(+), 2 deletions(-) diff --git a/include/linux/sched.h b/include/linux/sched.h index 43222c34fab8..0fdd39174436 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -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; diff --git a/kernel/bpf/task_park.c b/kernel/bpf/task_park.c index 39c9f085f7a9..5a9b3124312e 100644 --- a/kernel/bpf/task_park.c +++ b/kernel/bpf/task_park.c @@ -5,10 +5,12 @@ #include #include #include +#include #include #include #include #include +#include /* * A BPF program that blocks for an event keeps its own queue of waiters and @@ -35,6 +37,75 @@ * not erased but stays pending for the next park. */ +/* + * A wake asked for with IRQs disabled cannot be issued there: the caller may + * have interrupted the scheduler with the task's pi_lock or a runqueue lock + * held, or may run in NMI context, where try_to_wake_up() may take neither. + * Such wakes are queued on the CPU and issued from irq_work once IRQs are + * enabled again. + * + * The queue goes through a node of its own in the task, under the rule the + * scheduler's wake queues follow for theirs: a task is on at most one queue, + * whoever claimed the node wakes the task, and a waker that finds it claimed + * leaves the wake to the claimant. The pending word is set before the claim + * is tried, so a wake left this way still reaches a parked task through the + * claimant's wake, and any other task through its next park. + * + * The task's wake_q node would save the field, but whoever claims that node + * may turn away a futex, rwsem or semaphore wakeup that then relies on the + * claimant, and so has to wake with TASK_NORMAL. A program could then aim a + * wake of an uninterruptible sleep at any task it names, and not every such + * sleep has a loop around it: a new kthread sleeps once until its creator + * wakes it. With its own node the drain wakes interruptible sleeps only, as + * the direct wake does. + * + * The queue is a stack with a per-CPU head: pushed with cmpxchg() from + * whatever context asks, emptied with one xchg() by the irq_work, so a push + * that interrupts the drain lands on an empty stack and queues the work + * again. + */ +static DEFINE_PER_CPU(struct wake_q_node *, bpf_task_wake_queue); + +static void bpf_task_wake_deferred(struct irq_work *work) +{ + struct wake_q_node *node = xchg(this_cpu_ptr(&bpf_task_wake_queue), NULL); + + while (node) { + struct task_struct *task = container_of(node, struct task_struct, bpf_wake_node); + + node = node->next == WAKE_Q_TAIL ? NULL : node->next; + /* The task may be queued again from here on. */ + WRITE_ONCE(task->bpf_wake_node.next, NULL); + wake_up_state(task, TASK_INTERRUPTIBLE); + put_task_struct(task); + } +} + +static DEFINE_PER_CPU(struct irq_work, bpf_task_wake_work) = + IRQ_WORK_INIT_HARD(bpf_task_wake_deferred); + +static void bpf_task_wake_defer(struct task_struct *task) +{ + struct wake_q_node *node = &task->bpf_wake_node, *head; + + /* + * The claim, as in __wake_q_add(): NULL is free, anything else is + * queued. The xchg() that stored the pending word is a full barrier + * between that store and the claim, so a claim lost to another holder + * is still covered: the holder's wake follows its own reset of the + * node, which this claim did not observe, so the task it wakes + * observes the word. + */ + if (cmpxchg_relaxed(&node->next, NULL, WAKE_Q_TAIL)) + return; + get_task_struct(task); + head = this_cpu_read(bpf_task_wake_queue); + do { + WRITE_ONCE(node->next, head ?: WAKE_Q_TAIL); + } while (!try_cmpxchg(this_cpu_ptr(&bpf_task_wake_queue), &head, node)); + irq_work_queue(this_cpu_ptr(&bpf_task_wake_work)); +} + /* * What ends a park besides a wake and the timeout: a stop or park request for * a kthread, or a signal. Both are checked for every caller, since a kthread @@ -169,8 +240,15 @@ __bpf_kfunc int bpf_task_park(u64 timeout_ns, u64 flags) * A task that is not parked keeps the pending wake until its next * bpf_task_park(), which then returns at once. * - * Return: 1 when @task was asleep and is now runnable, 0 when it was not, - * -EINVAL when @flags is not 0. + * The wake takes the task's pi_lock and a runqueue lock, which the kernel + * code a program runs in or interrupts may already hold, and it may not be + * issued in NMI context at all. Such code and NMI context both run with IRQs + * disabled, so a call with IRQs disabled marks the wake pending and queues it + * for irq_work on the calling CPU, which issues it once IRQs are enabled + * again. Such a call cannot tell whether the task was asleep and returns 2. + * + * Return: 1 when @task was asleep and is now runnable, 0 when it was not, 2 + * when the wake was deferred, -EINVAL when @flags is not 0. */ __bpf_kfunc int bpf_task_wake(struct task_struct *task, u64 flags) { @@ -186,6 +264,10 @@ __bpf_kfunc int bpf_task_wake(struct task_struct *task, u64 flags) * in bpf_task_park(). */ xchg(&task->bpf_wake_pending, 1); + if (unlikely(irqs_disabled())) { + bpf_task_wake_defer(task); + return 2; + } return wake_up_state(task, TASK_INTERRUPTIBLE); } diff --git a/kernel/fork.c b/kernel/fork.c index b66eb25626c9..a272d11c6caf 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -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