1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst 4 * 5 * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. 6 * Copyright (c) 2022 Tejun Heo <tj@kernel.org> 7 * Copyright (c) 2022 David Vernet <dvernet@meta.com> 8 */ 9 #ifndef _LINUX_SCHED_EXT_H 10 #define _LINUX_SCHED_EXT_H 11 12 #ifdef CONFIG_SCHED_CLASS_EXT 13 14 #include <linux/llist.h> 15 #include <linux/rhashtable-types.h> 16 17 enum scx_public_consts { 18 SCX_OPS_NAME_LEN = 128, 19 20 /* 21 * %SCX_SLICE_DFL is used to refill slices when the BPF scheduler misses 22 * to set the slice for a task that is selected for execution. 23 * %SCX_EV_REFILL_SLICE_DFL counts the number of times the default slice 24 * refill has been triggered. 25 * 26 * %SCX_SLICE_BYPASS is used as the slice for all tasks in the bypass 27 * mode. As making forward progress for all tasks is the main goal of 28 * the bypass mode, a shorter slice is used. 29 */ 30 SCX_SLICE_DFL = 20 * 1000000, /* 20ms */ 31 SCX_SLICE_BYPASS = 5 * 1000000, /* 5ms */ 32 SCX_SLICE_INF = U64_MAX, /* infinite, implies nohz */ 33 }; 34 35 /* 36 * DSQ (dispatch queue) IDs are 64bit of the format: 37 * 38 * Bits: [63] [62 .. 0] 39 * [ B] [ ID ] 40 * 41 * B: 1 for IDs for built-in DSQs, 0 for ops-created user DSQs 42 * ID: 63 bit ID 43 * 44 * Built-in IDs: 45 * 46 * Bits: [63] [62] [61..32] [31 .. 0] 47 * [ 1] [ L] [ R ] [ V ] 48 * 49 * 1: 1 for built-in DSQs. 50 * L: 1 for LOCAL_ON DSQ IDs, 0 for others 51 * V: For LOCAL_ON DSQ IDs, a CPU number. For others, a pre-defined value. 52 */ 53 enum scx_dsq_id_flags { 54 SCX_DSQ_FLAG_BUILTIN = 1LLU << 63, 55 SCX_DSQ_FLAG_LOCAL_ON = 1LLU << 62, 56 57 SCX_DSQ_INVALID = SCX_DSQ_FLAG_BUILTIN | 0, 58 SCX_DSQ_GLOBAL = SCX_DSQ_FLAG_BUILTIN | 1, 59 SCX_DSQ_LOCAL = SCX_DSQ_FLAG_BUILTIN | 2, 60 SCX_DSQ_BYPASS = SCX_DSQ_FLAG_BUILTIN | 3, 61 SCX_DSQ_REJECT = SCX_DSQ_FLAG_BUILTIN | 4, /* internal - see find_dsq_for_dispatch() */ 62 SCX_DSQ_RESCUE = SCX_DSQ_FLAG_BUILTIN | 5, /* internal - see find_dsq_for_dispatch() */ 63 SCX_DSQ_LOCAL_ON = SCX_DSQ_FLAG_BUILTIN | SCX_DSQ_FLAG_LOCAL_ON, 64 SCX_DSQ_LOCAL_CPU_MASK = 0xffffffffLLU, 65 }; 66 67 struct scx_deferred_reenq_user { 68 struct list_head node; 69 u64 flags; 70 }; 71 72 struct scx_dsq_pcpu { 73 struct scx_dispatch_q *dsq; 74 struct scx_deferred_reenq_user deferred_reenq_user; 75 }; 76 77 /* 78 * A dispatch queue (DSQ) can be either a FIFO or p->scx.dsq_vtime ordered 79 * queue. A built-in DSQ is always a FIFO. The built-in local DSQs are used to 80 * buffer between the scheduler core and the BPF scheduler. See the 81 * documentation for more details. 82 */ 83 struct scx_dispatch_q { 84 raw_spinlock_t lock; 85 struct task_struct __rcu *first_task; /* lockless peek at head */ 86 struct list_head list; /* tasks in dispatch order */ 87 struct rb_root priq; /* used to order by p->scx.dsq_vtime */ 88 u32 nr; 89 u32 seq; /* used by BPF iter */ 90 u64 id; 91 struct rhash_head hash_node; 92 struct llist_node free_node; 93 struct scx_sched *sched; 94 struct scx_dsq_pcpu __percpu *pcpu_user; 95 struct rcu_head rcu; 96 }; 97 98 /* sched_ext_entity.flags */ 99 enum scx_ent_flags { 100 SCX_TASK_QUEUED = 1 << 0, /* on ext runqueue */ 101 SCX_TASK_IN_CUSTODY = 1 << 1, /* in custody, needs ops.dequeue() when leaving */ 102 SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */ 103 SCX_TASK_DEQD_FOR_SLEEP = 1 << 3, /* last dequeue was for SLEEP */ 104 SCX_TASK_SUB_INIT = 1 << 4, /* task being initialized for a sub sched */ 105 SCX_TASK_IMMED = 1 << 5, /* task is on local DSQ with %SCX_ENQ_IMMED */ 106 SCX_TASK_PROTECTED = 1 << 6, /* slice and DSQ head position protected */ 107 SCX_TASK_RUN_TRACKED = 1 << 7, /* task is in an ops.running()/stopping() session */ 108 109 /* 110 * Bits 8 to 10 are used to carry task state: 111 * 112 * NONE ops.init_task() not called yet 113 * INIT_BEGIN ops.init_task() in flight; see sched_ext_dead() 114 * INIT ops.init_task() succeeded, but task can be cancelled 115 * READY fully initialized, but not in sched_ext 116 * ENABLED fully initialized and in sched_ext 117 * DEAD terminal state set by sched_ext_dead() 118 */ 119 SCX_TASK_STATE_SHIFT = 8, 120 SCX_TASK_STATE_BITS = 3, 121 SCX_TASK_STATE_MASK = ((1 << SCX_TASK_STATE_BITS) - 1) << SCX_TASK_STATE_SHIFT, 122 123 SCX_TASK_NONE = 0 << SCX_TASK_STATE_SHIFT, 124 SCX_TASK_INIT_BEGIN = 1 << SCX_TASK_STATE_SHIFT, 125 SCX_TASK_INIT = 2 << SCX_TASK_STATE_SHIFT, 126 SCX_TASK_READY = 3 << SCX_TASK_STATE_SHIFT, 127 SCX_TASK_ENABLED = 4 << SCX_TASK_STATE_SHIFT, 128 SCX_TASK_DEAD = 5 << SCX_TASK_STATE_SHIFT, 129 130 /* 131 * Bits 12 to 14 are used to carry reenqueue reason. In addition to 132 * %SCX_ENQ_REENQ flag, ops.enqueue() can also test for 133 * %SCX_TASK_REENQ_REASON_NONE to distinguish reenqueues. 134 * 135 * NONE not being reenqueued 136 * KFUNC reenqueued by scx_bpf_dsq_reenq() and friends 137 * IMMED reenqueued due to failed ENQ_IMMED 138 * PREEMPTED preempted while running 139 * CAP sub-sched cap miss, see p->scx.reenq_reason_* 140 * PROXY proxy state prevented a remote DSQ transfer 141 */ 142 SCX_TASK_REENQ_REASON_SHIFT = 12, 143 SCX_TASK_REENQ_REASON_BITS = 3, 144 SCX_TASK_REENQ_REASON_MASK = ((1 << SCX_TASK_REENQ_REASON_BITS) - 1) << SCX_TASK_REENQ_REASON_SHIFT, 145 146 SCX_TASK_REENQ_NONE = 0 << SCX_TASK_REENQ_REASON_SHIFT, 147 SCX_TASK_REENQ_KFUNC = 1 << SCX_TASK_REENQ_REASON_SHIFT, 148 SCX_TASK_REENQ_IMMED = 2 << SCX_TASK_REENQ_REASON_SHIFT, 149 SCX_TASK_REENQ_PREEMPTED = 3 << SCX_TASK_REENQ_REASON_SHIFT, 150 SCX_TASK_REENQ_CAP = 4 << SCX_TASK_REENQ_REASON_SHIFT, 151 SCX_TASK_REENQ_PROXY = 5 << SCX_TASK_REENQ_REASON_SHIFT, 152 153 /* iteration cursor, not a task */ 154 SCX_TASK_CURSOR = 1 << 31, 155 }; 156 157 /* scx_entity.dsq_flags */ 158 enum scx_ent_dsq_flags { 159 SCX_TASK_DSQ_ON_PRIQ = 1 << 0, /* task is queued on the priority queue of a dsq */ 160 SCX_TASK_DSQ_REENQ = 1 << 1, /* marked by scx_bpf_dsq_reenq_task() */ 161 }; 162 163 enum scx_dsq_lnode_flags { 164 SCX_DSQ_LNODE_ITER_CURSOR = 1 << 0, 165 166 /* high 16 bits can be for iter cursor flags */ 167 __SCX_DSQ_LNODE_PRIV_SHIFT = 16, 168 }; 169 170 struct scx_dsq_list_node { 171 struct list_head node; 172 u32 flags; 173 u32 priv; /* can be used by iter cursor */ 174 }; 175 176 #define INIT_DSQ_LIST_CURSOR(__cursor, __dsq, __flags) \ 177 (struct scx_dsq_list_node) { \ 178 .node = LIST_HEAD_INIT((__cursor).node), \ 179 .flags = SCX_DSQ_LNODE_ITER_CURSOR | (__flags), \ 180 .priv = READ_ONCE((__dsq)->seq), \ 181 } 182 183 struct scx_sched; 184 185 /* 186 * The following is embedded in task_struct and contains all fields necessary 187 * for a task to be scheduled by SCX. 188 */ 189 struct sched_ext_entity { 190 #ifdef CONFIG_CGROUPS 191 /* 192 * Associated scx_sched. Updated either during fork or while holding 193 * both p->pi_lock and rq lock. 194 */ 195 struct scx_sched __rcu *sched; 196 #endif 197 struct scx_dispatch_q *dsq; 198 atomic_long_t ops_state; 199 u64 ddsp_dsq_id; 200 u64 ddsp_enq_flags; 201 u64 ddsp_slice; 202 u64 ddsp_vtime; 203 struct scx_dsq_list_node dsq_list; /* dispatch order */ 204 u32 dsq_seq; 205 u32 dsq_flags; /* protected by DSQ lock */ 206 207 /* 208 * Used to order tasks when dispatching to the vtime-ordered priority 209 * queue of a dsq. This is usually set through 210 * scx_bpf_dsq_insert_vtime() but can also be modified directly by the 211 * BPF scheduler. Modifying it while a task is queued on a dsq may 212 * mangle the ordering and is not recommended. Kept next to @dsq_priq 213 * as rbtree insertion reads both on every visited node. 214 */ 215 u64 dsq_vtime; 216 struct rb_node dsq_priq; /* p->scx.dsq_vtime order */ 217 u32 flags; /* protected by rq lock */ 218 u32 weight; 219 u32 reenq_cnt; /* reenqueues since last run */ 220 s32 sticky_cpu; 221 s32 holding_cpu; 222 s32 selected_cpu; 223 s32 runnable_cpu; /* cpu @p is runnable on, -1 if not */ 224 u32 ops_qseq; /* protected by rq lock */ 225 struct task_struct *kf_tasks[2]; /* see SCX_CALL_OP_TASK() */ 226 227 struct list_head runnable_node; /* rq->scx.runnable_list */ 228 unsigned long runnable_at; 229 230 #ifdef CONFIG_EXT_SUB_SCHED 231 unsigned long rescue_at; /* queued on a rescue DSQ at, jiffies */ 232 #endif 233 234 /* 235 * Unique non-zero task ID assigned at fork. Persists across exec and 236 * is never reused. Lets BPF schedulers identify tasks without storing 237 * kernel pointers - arena-backed schedulers being one example. See 238 * scx_bpf_tid_to_task(). 239 */ 240 u64 tid; 241 struct rhash_head tid_hash_node; /* see SCX_OPS_TID_TO_TASK */ 242 243 /* BPF scheduler modifiable fields, along with @dsq_vtime above */ 244 245 /* 246 * Runtime budget in nsecs - how long the task may hold its cpu. Owned 247 * by the task's scheduler. Set it when enqueuing via 248 * scx_bpf_dsq_insert(), or otherwise via scx_bpf_task_set_slice(). 249 * Automatically decreased as the task executes. On depletion a 250 * scheduling event is triggered. 251 * 252 * This value is cleared to zero if the task is preempted by 253 * %SCX_KICK_PREEMPT and shouldn't be used to determine how long the 254 * task ran. Use p->se.sum_exec_runtime instead. 255 */ 256 u64 slice; 257 258 /* 259 * Out-of-band slice request from scx_bpf_task_set_slice() when the 260 * caller does not hold the rq lock, applied under the rq lock at the 261 * next slice consideration. One atomic64 packs the pending flag, the 262 * issuing sch's id, and the requested slice. See scx_slice_oob_consts. 263 */ 264 atomic64_t slice_oob; 265 266 /* 267 * Sub-sched cap rejected reenq context, valid only while 268 * %SCX_TASK_REENQ_CAP is set. @reenq_reason_caps is the SCX_CAP_* bits 269 * that were needed but missing. @reenq_reason_cid is the target cid. 270 */ 271 u64 reenq_reason_caps; 272 s32 reenq_reason_cid; 273 274 /* 275 * If set, reject future sched_setscheduler(2) calls updating the policy 276 * to %SCHED_EXT with -%EACCES. 277 * 278 * Can be set from ops.init_task() while the BPF scheduler is being 279 * loaded. If set and the task's policy is already %SCHED_EXT, the 280 * task's policy is rejected and forcefully reverted to %SCHED_NORMAL. 281 * The number of such events are reported through 282 * /sys/kernel/sched_ext/nr_rejected. Setting this flag from any other 283 * ops.init_task() invocation, such as during fork, fails the scheduler. 284 */ 285 bool disallow; /* reject switching into SCX */ 286 287 /* 288 * If set, depletion of this task's slice at the scheduler tick requests 289 * lazy instead of immediate rescheduling. Initialized from 290 * %SCX_OPS_LAZY_RESCHED immediately before ops.enable() and may be 291 * modified afterwards with scx_bpf_task_set_lazy_resched(). 292 */ 293 bool lazy_resched; 294 295 /* cold fields */ 296 #ifdef CONFIG_EXT_GROUP_SCHED 297 struct cgroup *cgrp_moving_from; 298 #endif 299 struct list_head tasks_node; 300 }; 301 302 void sched_ext_dead(struct task_struct *p); 303 void print_scx_info(const char *log_lvl, struct task_struct *p); 304 void scx_softlockup(u32 dur_s); 305 bool scx_hardlockup(int cpu); 306 bool scx_rcu_cpu_stall(const struct cpumask *stalled_mask); 307 308 #else /* !CONFIG_SCHED_CLASS_EXT */ 309 310 static inline void sched_ext_dead(struct task_struct *p) {} 311 static inline void print_scx_info(const char *log_lvl, struct task_struct *p) {} 312 static inline void scx_softlockup(u32 dur_s) {} 313 static inline bool scx_hardlockup(int cpu) { return false; } 314 static inline bool scx_rcu_cpu_stall(const struct cpumask *stalled_mask) { return false; } 315 316 #endif /* CONFIG_SCHED_CLASS_EXT */ 317 318 struct scx_task_group { 319 #ifdef CONFIG_EXT_GROUP_SCHED 320 /* 321 * The sched this tg is on, NULL if none. SCX_TG_INITED tracks whether 322 * ops.cgroup_init() succeeded on it. When a child sched exits and its 323 * tgs move to the parent, a failed init leaves the tg on the parent 324 * with INITED clear (see scx_cgroup_return_subtree()). 325 * 326 * This is tracked separately from cgrp->scx_sched because the tg 327 * hierarchy can diverge from the cgroup2 hierarchy in both lifetime and 328 * shape. A tg stays online past its cgroup's removal while the 329 * cgrp->scx_sched rewrites visit only live cgroups, leaving a removed 330 * cgroup's pointer stale. The cpu controller can also be mounted on 331 * cgroup1. 332 */ 333 struct scx_sched *sched; 334 335 u32 flags; /* SCX_TG_* */ 336 u32 weight; 337 u64 bw_period_us; 338 u64 bw_quota_us; 339 u64 bw_burst_us; 340 bool sched_idle; 341 #endif 342 }; 343 344 #endif /* _LINUX_SCHED_EXT_H */ 345