// SPDX-License-Identifier: GPL-2.0/* * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst * * Sub-scheduler hierarchy support. * * A sub-scheduler is an scx_sched attached to a cgroup subtree under another * scx_sched. This file holds the sub-scheduler implementation: the scheduler * tree walk, capability delegation, per-shard cap state and its sync, and the * sub-scheduler enable/disable paths. The core dispatch/enqueue machinery it * builds on lives in ext.c. * * Copyright (c) 2026 Meta Platforms, Inc. and affiliates. * Copyright (c) 2026 Tejun Heo <tj@kernel.org> */#include <linux/rhashtable.h>#include "internal.h"#include "cid.h"#include "arena.h"#include "sub.h"#include "inlines.h" #ifdef CONFIG_EXT_SUB_SCHED /* * On while any sub-scheduler exists so that a root-only system doesn't pay for * the sub-sched portions of hot paths. See scx_has_subs(). */DEFINE_STATIC_KEY_FALSE(__scx_has_subs); /* latched at root enable before any rescue runs */static s32 scx_rescue_bw_1024;static s64 scx_rescue_quantum_ns;static s64 scx_rescue_sat_delta_ns;static unsigned long scx_rescue_decay_halflife;static unsigned long scx_rescue_overload_after; /** * scx_skip_subtree_pre - Skip @pos's subtree in a pre-order walk * @pos: current position * @root: walk root * * In a walk started by scx_next_descendant_pre(), continue past @pos's subtree: * return @pos's next sibling, or the closest ancestor's next sibling, or NULL * if @pos's subtree is the last under @root. Same locking rules. */struct scx_sched *scx_skip_subtree_pre(struct scx_sched *pos, struct scx_sched *root){	struct scx_sched *next; 	lockdep_assert(lockdep_is_held(&scx_enable_mutex) ||		       lockdep_is_held(&scx_sched_lock) ||		       rcu_read_lock_any_held()); 	while (pos != root) {		next = list_next_or_null_rcu(&scx_parent(pos)->children, &pos->sibling,					     struct scx_sched, sibling);		if (next)			return next;		pos = scx_parent(pos);	}	return NULL;} /** * scx_next_descendant_pre - find the next descendant for pre-order walk * @pos: the current position (%NULL to initiate traversal) * @root: sched whose descendants to walk * * To be used by scx_for_each_descendant_pre(). Find the next descendant to * visit for pre-order traversal of @root's descendants. @root is included in * the iteration and the first node to be visited. */struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos, struct scx_sched *root){	struct scx_sched *next; 	lockdep_assert(lockdep_is_held(&scx_enable_mutex) ||		       lockdep_is_held(&scx_sched_lock) ||		       rcu_read_lock_any_held()); 	/* if first iteration, visit @root */	if (!pos)		return root; 	/* visit the first child if exists */	next = list_first_or_null_rcu(&pos->children, struct scx_sched, sibling);	if (next)		return next; 	/* no child, visit my or the closest ancestor's next sibling */	return scx_skip_subtree_pre(pos, root);} static struct scx_sched *scx_find_sub_sched(u64 cgroup_id){	return rhashtable_lookup(&scx_sched_hash, &cgroup_id,				 scx_sched_hash_params);} void scx_set_task_sched(struct task_struct *p, struct scx_sched *sch){	rcu_assign_pointer(p->scx.sched, sch);} struct cgroup *sch_cgroup(struct scx_sched *sch){	return sch->cgrp;} /* for each descendant of @cgrp including self, set ->scx_sched to @sch */void set_cgroup_sched(struct cgroup *cgrp, struct scx_sched *sch){	struct cgroup *pos;	struct cgroup_subsys_state *css; 	cgroup_for_each_live_descendant_pre(pos, css, cgrp)		rcu_assign_pointer(pos->scx_sched, sch);} static void free_pshard(struct scx_pshard *pshard){	struct scx_caps_updated *cu; 	if (!pshard)		return;	cu = &pshard->caps_updated;	if (cu->cmask_arena_out)		scx_arena_free(pshard->sch, cu->cmask_arena_out,			       struct_size_t(struct scx_cmask, bits,					     SCX_CMASK_NR_WORDS(pshard->nr_cids)));	kfree(pshard);} void scx_free_pshards(struct scx_sched *sch){	s32 si; 	if (!sch->pshard)		return;	for (si = 0; si < sch->nr_pshards; si++)		free_pshard(sch->pshard[si]);	kfree(sch->pshard);} static struct scx_pshard *alloc_pshard(struct scx_sched *sch, s32 shard_idx, s32 node){	const struct scx_cid_shard *shard =		&rcu_dereference_protected(scx_cid_shard_ranges,					   lockdep_is_held(&scx_enable_mutex))[shard_idx];	size_t cmask_size = struct_size_t(struct scx_cmask, bits,					  SCX_CMASK_NR_WORDS(shard->nr_cids));	struct scx_pshard *pshard;	struct scx_caps_updated *cu;	s32 i; 	pshard = kzalloc_node(sizeof(*pshard), GFP_KERNEL, node);	if (!pshard)		return NULL; 	raw_spin_lock_init(&pshard->lock);	pshard->sch = sch;	pshard->base = shard->base_cid;	pshard->nr_cids = shard->nr_cids; 	for (i = 0; i < __SCX_NR_CAPS; i++)		scx_cmask_init(&pshard->caps[i].cmask, shard->base_cid, shard->nr_cids); 	cu = &pshard->caps_updated;	raw_spin_lock_init(&cu->lock);	INIT_LIST_HEAD(&cu->node_in_flight);	__scx_cmask_init(&cu->cmask, shard->base_cid, shard->nr_cids, SCX_CID_SHARD_MAX_CPUS); 	cu->cmask_arena_out = scx_arena_alloc(sch, cmask_size);	if (!cu->cmask_arena_out) {		free_pshard(pshard);		return NULL;	} 	scx_cmask_init(cu->cmask_arena_out, shard->base_cid, shard->nr_cids); 	return pshard;} s32 scx_alloc_pshards(struct scx_sched *sch){	struct scx_pshard **pshard;	s32 *shard_node;	s32 si; 	if (!sch->is_cid_type || !sch->arena_pool)		return 0; 	shard_node = rcu_dereference_protected(scx_shard_node,					       lockdep_is_held(&scx_enable_mutex)); 	pshard = kzalloc_objs(pshard[0], scx_nr_cid_shards);	if (!pshard)		return -ENOMEM; 	for (si = 0; si < scx_nr_cid_shards; si++) {		pshard[si] = alloc_pshard(sch, si, shard_node[si]);		if (!pshard[si]) {			while (--si >= 0)				free_pshard(pshard[si]);			kfree(pshard);			return -ENOMEM;		}	} 	sch->nr_pshards = scx_nr_cid_shards;	/*	 * Publish only after every entry is built so a reader observing	 * @sch->pshard never sees a partially-filled array or unpublished cid	 * tables. Pair the store with a barrier and an acquire load on the	 * read side.	 */	smp_wmb();	WRITE_ONCE(sch->pshard, pshard);	return 0;} /* * Seed the root's caps fully. Root owns all cids on all caps at enable time. * Children acquire caps via scx_bpf_sub_grant(). */void scx_init_root_caps(struct scx_sched *sch){	s32 si, i; 	for (si = 0; si < sch->nr_pshards; si++) {		struct scx_pshard *ps = sch->pshard[si]; 		for (i = 0; i < __SCX_NR_CAPS; i++)			scx_cmask_fill(&ps->caps[i].cmask);	}} /* unserved remainder of @rq's rescuee's admitted slice, 0 once fully served */static s64 scx_rescue_slice_remaining(struct rq *rq){	s64 served = rq->scx.rescue.curr->se.sum_exec_runtime - rq->scx.rescue.exec_snap; 	return max(rq->scx.rescue.slice - served, 0);} /* * Decay @pcpu's rescue usage average in place, halving per the knob-derived * halflife, see scx_rescue_set_knobs(). The timestamp advances only by whole * halflives. */static u64 scx_rescue_decay_avg(struct scx_sched_pcpu *pcpu){	unsigned long halflife = scx_rescue_decay_halflife;	u64 n = div_u64(get_jiffies_64() - pcpu->rescue_avg_at, halflife); 	if (n) {		pcpu->rescue_avg = n < 64 ? pcpu->rescue_avg >> n : 0;		pcpu->rescue_avg_at += n * halflife;	}	return pcpu->rescue_avg;} /** * scx_rescue_charge - Charge the rescuee's runtime * @rq: rq the rescuee is running on * @delta_exec: runtime being charged * * Also ends the rescue once the admitted slice has been served in full. Ending * on served time rather than slice exhaustion bounds both the rescue and the * charging when a scheduler extends the rescuee's slice. */void scx_rescue_charge(struct rq *rq, s64 delta_exec){	struct scx_sched_pcpu *pcpu; 	lockdep_assert_rq_held(rq); 	/*	 * A rescue slice is bounded by one quantum and tick-driven expiry can	 * overshoot by up to a tick. Clamp to avoid wild over-charges on VMs.	 */	delta_exec = min_t(s64, delta_exec, scx_rescue_quantum_ns + TICK_NSEC); 	rq->scx.rescue.budget -= delta_exec; 	/* per-cpu usage average feeds the overload victim pick */	pcpu = per_cpu_ptr(scx_task_sched(rq->curr)->pcpu, cpu_of(rq));	pcpu->rescue_avg = scx_rescue_decay_avg(pcpu) + delta_exec; 	if (!scx_rescue_slice_remaining(rq))		scx_task_slice_ended(rq, rq->scx.rescue.curr);} /** * scx_rescue_end - End the rescue execution on @rq * @rq: rq of interest * * When no rescuee is left pending, the session is over and the balance above * one quantum dies with it - it would otherwise become a banked license to * preempt the cid owner long after the starvation ended. While waiters remain, * the accrued deficit belongs to the queue and carries into the next rescue. */void scx_rescue_end(struct rq *rq){	lockdep_assert_rq_held(rq); 	rq->scx.rescue.curr = NULL;	if (list_empty(&rq->scx.rescue.dsq.list))		rq->scx.rescue.budget = min(rq->scx.rescue.budget, scx_rescue_quantum_ns);} /** * scx_rescue_keep - Keep the rescue going for a preempted-out rescuee * @rq: rq @p is running on * @p: task under rescue whose slice is exhausted * * Called from put_prev_task_scx() to decide what an exhausted slice means for * the rescuee. scx_rescue_charge() ends the rescue the moment the admitted * slice is fully served, so arriving here with the rescue still open means @p * was preempted. Restore the unserved remainder and return %true - @p stays the * rescuee and the caller reinserts it at the tail of the local DSQ, behind * whatever preempted the rescuee. * * Return %false to end the rescue instead - the slice is already fully served, * @p is leaving the rq or bypass is dismantling rescues. */bool scx_rescue_keep(struct rq *rq, struct task_struct *p){	s64 remaining = scx_rescue_slice_remaining(rq); 	lockdep_assert_rq_held(rq); 	if (!remaining || !(p->scx.flags & SCX_TASK_QUEUED) ||	    scx_bypassing(scx_task_sched(p), cpu_of(rq)))		return false; 	scx_set_task_slice(p, remaining);	return true;} /** * scx_rescue_accrue - Accrue budget at the configured fraction of elapsed time * @rq: rq of interest * * A session spans from the first arrival until no rescuee is left, pending or * admitted. While one is active the cap is three quanta and the balance drives * escalation, see scx_rescue_timerfn(). Outside a session the cap is one * quantum, so an idle gap funds the next arrival's admission but never an * escalation. */static void scx_rescue_accrue(struct rq *rq){	bool in_session = rq->scx.rescue.curr || !list_empty(&rq->scx.rescue.dsq.list);	s64 cap = in_session ? 3 * scx_rescue_quantum_ns : scx_rescue_quantum_ns;	s64 delta;	u64 now; 	lockdep_assert_rq_held(rq); 	/* not every path here holds an updated rq clock, use __scx_bpf_now() */	now = __scx_bpf_now(rq);	delta = now - rq->scx.rescue.clock;	rq->scx.rescue.clock = now; 	/*	 * Avoid multiplication overflows by taking a shortcut when the gap is	 * large enough to fill the budget.	 */	if (delta >= scx_rescue_sat_delta_ns)		rq->scx.rescue.budget = cap;	else		rq->scx.rescue.budget =			min(cap, rq->scx.rescue.budget +			    ((delta * scx_rescue_bw_1024) >> SCHED_CAPACITY_SHIFT));} /* * The slice for the next admission - the quantum divided across the stranded * tasks so that a crowded queue round-robins on shorter slices. */static s64 scx_rescue_next_slice(struct rq *rq){	s64 min_slice = max_t(s64, SCX_RESCUE_MIN_SLICE_US * NSEC_PER_USEC, TICK_NSEC);	u32 depth = rq->scx.rescue.dsq.nr ?: 1; 	return clamp(div_s64(scx_rescue_quantum_ns, depth), min_slice, scx_rescue_quantum_ns);} static void scx_rescue_timer_arm(struct rq *rq){	struct timer_list *timer = &rq->scx.rescue.timer;	s64 delay = scx_rescue_quantum_ns / 4;	/* should be granular enough */ 	if (timer_pending(timer))		return; 	/*	 * While the head waiter can't be admitted because the bucket is short	 * of a full quantum, stretch to the full funding delay.	 */	if (!rq->scx.rescue.curr && rq->scx.rescue.budget < scx_rescue_quantum_ns) {		s64 deficit = scx_rescue_quantum_ns - rq->scx.rescue.budget; 		delay = max(delay,			    div_s64(deficit << SCHED_CAPACITY_SHIFT, scx_rescue_bw_1024));	} 	/* +1 rounds up so the beat is due by the time the timer fires */	timer->expires = jiffies + nsecs_to_jiffies(delay) + 1;	add_timer_on(timer, cpu_of(rq));} /** * scx_rescue_admit - Start rescuing @p on @rq * @rq: rq @p is being admitted on * @p: task being admitted, off any DSQ * @slice: CPU time to grant * * The schedulers keep their normal control over @p and may preempt or reslice * it. @slice is measured on served CPU time against the snapshot taken here, so * neither shortens the rescue, see scx_rescue_charge() and scx_rescue_keep(). * Prolonged denial escalates into protected execution, see * scx_rescue_timerfn(). */static void scx_rescue_admit(struct rq *rq, struct task_struct *p, s64 slice){	lockdep_assert_rq_held(rq);	WARN_ON_ONCE(rq->scx.rescue.curr); 	rq->scx.rescue.curr = p;	rq->scx.rescue.slice = slice;	rq->scx.rescue.exec_snap = p->se.sum_exec_runtime;	scx_set_task_slice(p, slice);	scx_rescue_timer_arm(rq);} /** * scx_rescue_try_admit - Try to admit a freshly stranded task * @rq: rq @p is being inserted on * @p: stranded task being diverted to rescue * * One rescue at a time and earlier arrivals go first. Admission needs a full * quantum of budget, spent as the rescue runs. Return %true if @p was admitted * and should be inserted at the tail of @rq's local DSQ, %false if it has to * park on the rescue DSQ, with the timer armed to admit it later. */static bool scx_rescue_try_admit(struct rq *rq, struct task_struct *p){	scx_rescue_accrue(rq); 	if (!rq->scx.rescue.curr && list_empty(&rq->scx.rescue.dsq.list) &&	    rq->scx.rescue.budget >= scx_rescue_quantum_ns) {		scx_rescue_admit(rq, p, scx_rescue_quantum_ns);		return true;	} 	scx_rescue_timer_arm(rq);	return false;} /** * scx_rescue_check_overload - Eject the top rescue consumer on a stuck rescue * @rq: rq whose rescue timer fired * * If the oldest waiter on @rq's rescue DSQ has been queued for too long, rescue * demand on this cpu persistently exceeds the configured bandwidth. Eject the * sub with the highest recent rescue consumption instead of letting the * scheduler stall path blame the waiter's owner, who may just be crowded out. */static void scx_rescue_check_overload(struct rq *rq){	struct scx_sched *victim = NULL, *pos;	struct task_struct *p;	int cpu = cpu_of(rq);	u64 max_avg = 0;	u32 dur_ms; 	lockdep_assert_rq_held(rq); 	p = list_first_entry_or_null(&rq->scx.rescue.dsq.list, struct task_struct,				     scx.dsq_list.node);	if (!p)		return; 	/* has the head waiter been queued for longer than the threshold? */	if (time_before(jiffies, p->scx.rescue_at + scx_rescue_overload_after))		return; 	/*	 * Grace period after the last ejection on this cpu - the freed	 * bandwidth gets one threshold's worth of time to drain the backlog	 * before another sub is judged.	 */	if (time_before64(get_jiffies_64(), rq->scx.rescue.kill_at +			  scx_rescue_overload_after))		return; 	list_for_each_entry_rcu(pos, &scx_sched_all, all) {		u64 avg = scx_rescue_decay_avg(per_cpu_ptr(pos->pcpu, cpu));

Lines 1–500 of 2681. Load more