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;
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
108 /*
109 * Bits 8 to 10 are used to carry task state:
110 *
111 * NONE ops.init_task() not called yet
112 * INIT_BEGIN ops.init_task() in flight; see sched_ext_dead()
113 * INIT ops.init_task() succeeded, but task can be cancelled
114 * READY fully initialized, but not in sched_ext
115 * ENABLED fully initialized and in sched_ext
116 * DEAD terminal state set by sched_ext_dead()
117 */
118 SCX_TASK_STATE_SHIFT = 8,
119 SCX_TASK_STATE_BITS = 3,
120 SCX_TASK_STATE_MASK = ((1 << SCX_TASK_STATE_BITS) - 1) << SCX_TASK_STATE_SHIFT,
121
122 SCX_TASK_NONE = 0 << SCX_TASK_STATE_SHIFT,
123 SCX_TASK_INIT_BEGIN = 1 << SCX_TASK_STATE_SHIFT,
124 SCX_TASK_INIT = 2 << SCX_TASK_STATE_SHIFT,
125 SCX_TASK_READY = 3 << SCX_TASK_STATE_SHIFT,
126 SCX_TASK_ENABLED = 4 << SCX_TASK_STATE_SHIFT,
127 SCX_TASK_DEAD = 5 << SCX_TASK_STATE_SHIFT,
128
129 /*
130 * Bits 12 to 14 are used to carry reenqueue reason. In addition to
131 * %SCX_ENQ_REENQ flag, ops.enqueue() can also test for
132 * %SCX_TASK_REENQ_REASON_NONE to distinguish reenqueues.
133 *
134 * NONE not being reenqueued
135 * KFUNC reenqueued by scx_bpf_dsq_reenq() and friends
136 * IMMED reenqueued due to failed ENQ_IMMED
137 * PREEMPTED preempted while running
138 * CAP sub-sched cap miss, see p->scx.reenq_reason_*
139 */
140 SCX_TASK_REENQ_REASON_SHIFT = 12,
141 SCX_TASK_REENQ_REASON_BITS = 3,
142 SCX_TASK_REENQ_REASON_MASK = ((1 << SCX_TASK_REENQ_REASON_BITS) - 1) << SCX_TASK_REENQ_REASON_SHIFT,
143
144 SCX_TASK_REENQ_NONE = 0 << SCX_TASK_REENQ_REASON_SHIFT,
145 SCX_TASK_REENQ_KFUNC = 1 << SCX_TASK_REENQ_REASON_SHIFT,
146 SCX_TASK_REENQ_IMMED = 2 << SCX_TASK_REENQ_REASON_SHIFT,
147 SCX_TASK_REENQ_PREEMPTED = 3 << SCX_TASK_REENQ_REASON_SHIFT,
148 SCX_TASK_REENQ_CAP = 4 << SCX_TASK_REENQ_REASON_SHIFT,
149
150 /* iteration cursor, not a task */
151 SCX_TASK_CURSOR = 1 << 31,
152 };
153
154 /* scx_entity.dsq_flags */
155 enum scx_ent_dsq_flags {
156 SCX_TASK_DSQ_ON_PRIQ = 1 << 0, /* task is queued on the priority queue of a dsq */
157 };
158
159 enum scx_dsq_lnode_flags {
160 SCX_DSQ_LNODE_ITER_CURSOR = 1 << 0,
161
162 /* high 16 bits can be for iter cursor flags */
163 __SCX_DSQ_LNODE_PRIV_SHIFT = 16,
164 };
165
166 struct scx_dsq_list_node {
167 struct list_head node;
168 u32 flags;
169 u32 priv; /* can be used by iter cursor */
170 };
171
172 #define INIT_DSQ_LIST_CURSOR(__cursor, __dsq, __flags) \
173 (struct scx_dsq_list_node) { \
174 .node = LIST_HEAD_INIT((__cursor).node), \
175 .flags = SCX_DSQ_LNODE_ITER_CURSOR | (__flags), \
176 .priv = READ_ONCE((__dsq)->seq), \
177 }
178
179 struct scx_sched;
180
181 /*
182 * The following is embedded in task_struct and contains all fields necessary
183 * for a task to be scheduled by SCX.
184 */
185 struct sched_ext_entity {
186 #ifdef CONFIG_CGROUPS
187 /*
188 * Associated scx_sched. Updated either during fork or while holding
189 * both p->pi_lock and rq lock.
190 */
191 struct scx_sched __rcu *sched;
192 #endif
193 struct scx_dispatch_q *dsq;
194 atomic_long_t ops_state;
195 u64 ddsp_dsq_id;
196 u64 ddsp_enq_flags;
197 u64 ddsp_slice;
198 u64 ddsp_vtime;
199 struct scx_dsq_list_node dsq_list; /* dispatch order */
200 struct rb_node dsq_priq; /* p->scx.dsq_vtime order */
201 u32 dsq_seq;
202 u32 dsq_flags; /* protected by DSQ lock */
203 u32 flags; /* protected by rq lock */
204 u32 weight;
205 u32 reenq_cnt; /* reenqueues since last run */
206 s32 sticky_cpu;
207 s32 holding_cpu;
208 s32 selected_cpu;
209 s32 runnable_cpu; /* cpu @p is runnable on, -1 if not */
210 struct task_struct *kf_tasks[2]; /* see SCX_CALL_OP_TASK() */
211
212 struct list_head runnable_node; /* rq->scx.runnable_list */
213 unsigned long runnable_at;
214
215 #ifdef CONFIG_EXT_SUB_SCHED
216 unsigned long rescue_at; /* queued on a rescue DSQ at, jiffies */
217 #endif
218
219 /*
220 * Unique non-zero task ID assigned at fork. Persists across exec and
221 * is never reused. Lets BPF schedulers identify tasks without storing
222 * kernel pointers - arena-backed schedulers being one example. See
223 * scx_bpf_tid_to_task().
224 */
225 u64 tid;
226 struct rhash_head tid_hash_node; /* see SCX_OPS_TID_TO_TASK */
227
228 /* BPF scheduler modifiable fields */
229
230 /*
231 * Runtime budget in nsecs - how long the task may hold its cpu. Owned
232 * by the task's scheduler. Set it when enqueuing via
233 * scx_bpf_dsq_insert(), or otherwise via scx_bpf_task_set_slice().
234 * Automatically decreased as the task executes. On depletion a
235 * scheduling event is triggered.
236 *
237 * This value is cleared to zero if the task is preempted by
238 * %SCX_KICK_PREEMPT and shouldn't be used to determine how long the
239 * task ran. Use p->se.sum_exec_runtime instead.
240 */
241 u64 slice;
242
243 /*
244 * Used to order tasks when dispatching to the vtime-ordered priority
245 * queue of a dsq. This is usually set through
246 * scx_bpf_dsq_insert_vtime() but can also be modified directly by the
247 * BPF scheduler. Modifying it while a task is queued on a dsq may
248 * mangle the ordering and is not recommended.
249 */
250 u64 dsq_vtime;
251
252 /*
253 * Out-of-band slice request from scx_bpf_task_set_slice() when the
254 * caller does not hold the rq lock, applied under the rq lock at the
255 * next slice consideration. One atomic64 packs the pending flag, the
256 * issuing sch's id, and the requested slice. See scx_slice_oob_consts.
257 */
258 atomic64_t slice_oob;
259
260 /*
261 * Sub-sched cap rejected reenq context, valid only while
262 * %SCX_TASK_REENQ_CAP is set. @reenq_reason_caps is the SCX_CAP_* bits
263 * that were needed but missing. @reenq_reason_cid is the target cid.
264 */
265 u64 reenq_reason_caps;
266 s32 reenq_reason_cid;
267
268 /*
269 * If set, reject future sched_setscheduler(2) calls updating the policy
270 * to %SCHED_EXT with -%EACCES.
271 *
272 * Can be set from ops.init_task() while the BPF scheduler is being
273 * loaded. If set and the task's policy is already %SCHED_EXT, the
274 * task's policy is rejected and forcefully reverted to %SCHED_NORMAL.
275 * The number of such events are reported through
276 * /sys/kernel/sched_ext/nr_rejected. Setting this flag from any other
277 * ops.init_task() invocation, such as during fork, fails the scheduler.
278 */
279 bool disallow; /* reject switching into SCX */
280
281 /* cold fields */
282 #ifdef CONFIG_EXT_GROUP_SCHED
283 struct cgroup *cgrp_moving_from;
284 #endif
285 struct list_head tasks_node;
286 };
287
288 void sched_ext_dead(struct task_struct *p);
289 void print_scx_info(const char *log_lvl, struct task_struct *p);
290 void scx_softlockup(u32 dur_s);
291 bool scx_hardlockup(int cpu);
292 bool scx_rcu_cpu_stall(const struct cpumask *stalled_mask);
293
294 #else /* !CONFIG_SCHED_CLASS_EXT */
295
sched_ext_dead(struct task_struct * p)296 static inline void sched_ext_dead(struct task_struct *p) {}
print_scx_info(const char * log_lvl,struct task_struct * p)297 static inline void print_scx_info(const char *log_lvl, struct task_struct *p) {}
scx_softlockup(u32 dur_s)298 static inline void scx_softlockup(u32 dur_s) {}
scx_hardlockup(int cpu)299 static inline bool scx_hardlockup(int cpu) { return false; }
scx_rcu_cpu_stall(const struct cpumask * stalled_mask)300 static inline bool scx_rcu_cpu_stall(const struct cpumask *stalled_mask) { return false; }
301
302 #endif /* CONFIG_SCHED_CLASS_EXT */
303
304 struct scx_task_group {
305 #ifdef CONFIG_EXT_GROUP_SCHED
306 /*
307 * The sched this tg is on, NULL if none. SCX_TG_INITED tracks whether
308 * ops.cgroup_init() succeeded on it. When a child sched exits and its
309 * tgs move to the parent, a failed init leaves the tg on the parent
310 * with INITED clear (see scx_cgroup_return_subtree()).
311 *
312 * This is tracked separately from cgrp->scx_sched because the tg
313 * hierarchy can diverge from the cgroup2 hierarchy in both lifetime and
314 * shape. A tg stays online past its cgroup's removal while the
315 * cgrp->scx_sched rewrites visit only live cgroups, leaving a removed
316 * cgroup's pointer stale. The cpu controller can also be mounted on
317 * cgroup1.
318 */
319 struct scx_sched *sched;
320
321 u32 flags; /* SCX_TG_* */
322 u32 weight;
323 u64 bw_period_us;
324 u64 bw_quota_us;
325 u64 bw_burst_us;
326 bool idle;
327 #endif
328 };
329
330 #endif /* _LINUX_SCHED_EXT_H */
331