projects/linux·blob master · refs

324 lines · 10.8 KiB

1/* SPDX-License-Identifier: GPL-2.0 */
2/*
3 * Topological CPU IDs (cids)
4 * --------------------------
5 *
6 * Raw cpu numbers are clumsy for sharding work and communication across
7 * topology units, especially from BPF: the space can be sparse, numerical
8 * closeness doesn't imply topological closeness (x86 hyperthreading often puts
9 * SMT siblings far apart), and a range of cpu ids doesn't mean anything.
10 * Sub-scheds make this acute - cpu allocation, revocation and other state are
11 * constantly communicated across sub-scheds, and passing whole cpumasks scales
12 * poorly with cpu count. cpumasks are also awkward in BPF: a variable-length
13 * kernel type sized for the maximum NR_CPUS (4k), with verbose helper sequences
14 * for every op.
15 *
16 * cids give every cpu a dense, topology-ordered id. CPUs sharing a core, LLC or
17 * NUMA node get contiguous cid ranges, so a topology unit becomes a (start,
18 * length) slice of cid space. Communication can pass a slice instead of a
19 * cpumask, and BPF code can process, for example, a u64 word's worth of cids at
20 * a time.
21 *
22 * The mapping is built once at root scheduler enable time by walking the
23 * topology of online cpus only. Going by online cpus is out of necessity:
24 * depending on the arch, topology info isn't reliably available for offline
25 * cpus. The expected usage model is restarting the scheduler on hotplug events
26 * so the mapping is rebuilt against the new online set. A scheduler that wants
27 * to handle hotplug without a restart can provide its own cid and shard mapping
28 * through the override interface.
29 *
30 * Copyright (c) 2026 Meta Platforms, Inc. and affiliates.
31 * Copyright (c) 2026 Tejun Heo <[email protected]>
32 */
33#ifndef _KERNEL_SCHED_EXT_CID_H
34#define _KERNEL_SCHED_EXT_CID_H
35
36#include "internal.h"
37
38struct scx_sched;
39
40/*
41 * Cid space (total is always num_possible_cpus()) is laid out with
42 * topology-annotated cids first, then no-topo cids at the tail. The
43 * topology-annotated block covers the cpus that were online when scx_cid_init()
44 * ran and remains valid even after those cpus go offline. The tail block covers
45 * possible-but-not-online cpus and carries all-(-1) topo info (see
46 * scx_cid_topo); callers detect it via the -1 sentinels.
47 *
48 * See the comment above the table definitions in cid.c for the
49 * memory-ordering and visibility contract.
50 */
51struct scx_cid_tables {
52 u32 nr_shards;
53 s16 *cid_to_cpu; /* [num_possible_cpus()] */
54 s16 *cpu_to_cid; /* [nr_cpu_ids] */
55 s32 *cid_to_shard; /* [num_possible_cpus()] */
56 s32 *shard_node; /* [num_possible_cpus()] */
57 struct scx_cid_shard *shard_ranges; /* [num_possible_cpus()] */
58 struct scx_cid_topo *topo; /* [num_possible_cpus()] */
59 struct rcu_head rcu;
60};
61
62extern u32 scx_nr_cid_shards;
63extern s16 __rcu *scx_cid_to_cpu_tbl;
64extern s16 __rcu *scx_cpu_to_cid_tbl;
65extern s32 __rcu *scx_cid_to_shard;
66extern s32 __rcu *scx_shard_node;
67extern struct scx_cid_shard __rcu *scx_cid_shard_ranges;
68extern struct scx_cid_topo __rcu *scx_cid_topo;
69extern struct btf_id_set8 scx_kfunc_ids_init_cids;
70extern struct btf_id_set8 scx_kfunc_ids_cid;
71
72void scx_cmask_clear(struct scx_cmask *m);
73void scx_cmask_fill(struct scx_cmask *m);
74void scx_cmask_and(struct scx_cmask *dst, const struct scx_cmask *src);
75void scx_cmask_or(struct scx_cmask *dst, const struct scx_cmask *src);
76void scx_cmask_copy(struct scx_cmask *dst, const struct scx_cmask *src);
77void scx_cmask_andnot(struct scx_cmask *dst, const struct scx_cmask *src);
78bool scx_cmask_subset(const struct scx_cmask *sub, const struct scx_cmask *super);
79bool scx_cmask_intersects(const struct scx_cmask *a, const struct scx_cmask *b);
80bool scx_cmask_empty(const struct scx_cmask *m);
81s32 scx_cid_init(struct scx_sched *sch);
82void scx_cid_publish_tables(void);
83void scx_cid_retire_tables(void);
84int scx_cid_kfunc_init(void);
85
86/**
87 * cid_valid - Verify a cid value, to be used on ops input args
88 * @sch: scx_sched to abort on error
89 * @cid: cid which came from a BPF ops
90 *
91 * Return true if @cid is in [0, num_possible_cpus()). On failure, trigger
92 * scx_error() and return false.
93 */
94static inline bool cid_valid(struct scx_sched *sch, s32 cid)
95{
96 if (likely(cid >= 0 && cid < num_possible_cpus()))
97 return true;
98 scx_error(sch, "invalid cid %d", cid);
99 return false;
100}
101
102/**
103 * __scx_cid_to_cpu - Unchecked cid->cpu table lookup
104 * @cid: cid to look up. Must be in [0, num_possible_cpus()).
105 *
106 * Intended for callsites that have already validated @cid and that run on a
107 * live scheduler, which guarantees the tables are published and stable.
108 */
109static inline s32 __scx_cid_to_cpu(s32 cid)
110{
111 return rcu_dereference_all(scx_cid_to_cpu_tbl)[cid];
112}
113
114/**
115 * __scx_cpu_to_cid - Unchecked cpu->cid table lookup
116 * @cpu: cpu to look up. Must be a valid possible cpu id.
117 *
118 * Same usage constraints as __scx_cid_to_cpu().
119 */
120static inline s32 __scx_cpu_to_cid(s32 cpu)
121{
122 return rcu_dereference_all(scx_cpu_to_cid_tbl)[cpu];
123}
124
125/**
126 * scx_cid_to_cpu - Translate @cid to its cpu
127 * @sch: scx_sched for error reporting
128 * @cid: cid to look up
129 *
130 * Return the cpu for @cid or a negative errno on failure. Invalid cid triggers
131 * scx_error() on @sch. The mapping is stable while the scheduler is live.
132 *
133 * Return -EINVAL without triggering scx_error() if no tables have been
134 * published yet, which a prog-facing kfunc can observe while racing the root
135 * scheduler enable.
136 */
137static inline s32 scx_cid_to_cpu(struct scx_sched *sch, s32 cid)
138{
139 s16 *tbl = rcu_dereference_all(scx_cid_to_cpu_tbl);
140
141 if (!cid_valid(sch, cid) || unlikely(!tbl))
142 return -EINVAL;
143 return tbl[cid];
144}
145
146/**
147 * scx_cpu_to_cid - Translate @cpu to its cid
148 * @sch: scx_sched for error reporting
149 * @cpu: cpu to look up
150 *
151 * Return the cid for @cpu or a negative errno on failure. Invalid cpu triggers
152 * scx_error() on @sch. Same usage rules as scx_cid_to_cpu().
153 */
154static inline s32 scx_cpu_to_cid(struct scx_sched *sch, s32 cpu)
155{
156 s16 *tbl = rcu_dereference_all(scx_cpu_to_cid_tbl);
157
158 if (!scx_cpu_valid(sch, cpu, NULL) || unlikely(!tbl))
159 return -EINVAL;
160 return tbl[cpu];
161}
162
163/**
164 * scx_is_cid_type - Test whether the active scheduler hierarchy is cid-form
165 */
166static inline bool scx_is_cid_type(void)
167{
168 return static_branch_unlikely(&__scx_is_cid_type);
169}
170
171static inline bool __scx_cmask_contains(u32 cid, const struct scx_cmask *m)
172{
173 return likely(cid >= m->base && cid < m->base + m->nr_cids);
174}
175
176/* Word in bits[] covering @cid. @cid must satisfy __scx_cmask_contains(). */
177static inline u64 *__scx_cmask_word(u32 cid, const struct scx_cmask *m)
178{
179 return (u64 *)&m->bits[cid / 64 - m->base / 64];
180}
181
182/**
183 * __scx_cmask_init - Initialize @m with explicit storage capacity
184 * @m: cmask to initialize
185 * @base: first cid of the active range
186 * @nr_cids: number of cids in the active range
187 * @alloc_cids: storage capacity in cids, at least @nr_cids
188 *
189 * Use when storage is sized larger than the initial active range. All of
190 * bits[] is zeroed.
191 */
192static inline void __scx_cmask_init(struct scx_cmask *m, u32 base, u32 nr_cids,
193 u32 alloc_cids)
194{
195 if (WARN_ON_ONCE(alloc_cids < nr_cids))
196 nr_cids = alloc_cids;
197
198 m->base = base;
199 m->nr_cids = nr_cids;
200 m->alloc_words = SCX_CMASK_NR_WORDS(alloc_cids);
201 memset(m->bits, 0, m->alloc_words * sizeof(u64));
202}
203
204/**
205 * scx_cmask_init - Initialize @m on tight storage
206 * @m: cmask to initialize
207 * @base: first cid of the active range
208 * @nr_cids: number of cids in the active range
209 *
210 * All of bits[] is zeroed.
211 */
212static inline void scx_cmask_init(struct scx_cmask *m, u32 base, u32 nr_cids)
213{
214 __scx_cmask_init(m, base, nr_cids, nr_cids);
215}
216
217/**
218 * scx_cmask_reframe - Reshape @m's active range without resizing storage
219 * @m: cmask to reframe
220 * @base: new active range base
221 * @nr_cids: new active range length, must fit within @m->alloc_words
222 *
223 * Body bits within the new range become garbage - only the head and tail
224 * words are zeroed to keep the padding invariant.
225 */
226static inline void scx_cmask_reframe(struct scx_cmask *m, u32 base, u32 nr_cids)
227{
228 if (WARN_ON_ONCE(SCX_CMASK_NR_WORDS(nr_cids) > m->alloc_words))
229 return;
230
231 if (nr_cids) {
232 u32 last_word = ((base & 63) + nr_cids - 1) / 64;
233
234 m->bits[0] = 0;
235 m->bits[last_word] = 0;
236 }
237
238 m->base = base;
239 m->nr_cids = nr_cids;
240}
241
242static inline void __scx_cmask_set(u32 cid, struct scx_cmask *m)
243{
244 if (!__scx_cmask_contains(cid, m))
245 return;
246 *__scx_cmask_word(cid, m) |= BIT_U64(cid & 63);
247}
248
249/**
250 * scx_cmask_test - test whether @cid is set in @m
251 * @cid: cid to test
252 * @m: cmask to test
253 *
254 * Return %false if @cid is outside @m's active range. Otherwise return the
255 * bit's value. Read via READ_ONCE so callers can race set/clear writers.
256 */
257static inline bool scx_cmask_test(u32 cid, const struct scx_cmask *m)
258{
259 if (!__scx_cmask_contains(cid, m))
260 return false;
261 return READ_ONCE(*__scx_cmask_word(cid, m)) & BIT_U64(cid & 63);
262}
263
264/*
265 * Words of bits[] the active range spans, 0 if empty. Tighter than the storage
266 * SCX_CMASK_NR_WORDS() sizes for the worst-case base alignment.
267 */
268static inline u32 scx_cmask_nr_used_words(const struct scx_cmask *m)
269{
270 if (!m->nr_cids)
271 return 0;
272 return ((m->base & 63) + m->nr_cids - 1) / 64 + 1;
273}
274
275/**
276 * scx_cmask_for_each_cid - iterate set cids in @m
277 * @cid: s32 loop var that receives each set cid in turn
278 * @m: cmask to iterate
279 *
280 * Visits set bits within @m's active range in ascending order. Scans only the
281 * words the active range spans, where head and tail padding is kept zero, so
282 * no per-cid range check is needed.
283 */
284#define scx_cmask_for_each_cid(cid, m) \
285 for (u64 __bs = (m)->base & ~63u, __wi = 0, \
286 __nw = scx_cmask_nr_used_words(m); \
287 __wi < __nw; __wi++) \
288 for (u64 __w = READ_ONCE((m)->bits[__wi]); \
289 __w && ((cid) = __bs + __wi * 64 + __ffs64(__w), true); \
290 __w &= __w - 1)
291
292/*
293 * scx_cpu_arg() wraps a cpu arg being handed to an SCX op. For cid-form
294 * schedulers it resolves to the matching cid; for cpu-form it passes @cpu
295 * through. scx_cpu_ret() is the inverse for a cpu/cid returned from an op
296 * (currently only ops.select_cpu); it validates the BPF-supplied cid and
297 * triggers scx_error() on @sch if invalid.
298 */
299static inline s32 scx_cpu_arg(s32 cpu)
300{
301 if (scx_is_cid_type())
302 return __scx_cpu_to_cid(cpu);
303 return cpu;
304}
305
306static inline s32 scx_cpu_ret(struct scx_sched *sch, s32 cpu_or_cid)
307{
308 if (cpu_or_cid < 0 || !scx_is_cid_type())
309 return cpu_or_cid;
310 return scx_cid_to_cpu(sch, cpu_or_cid);
311}
312
313int scx_cmask_ref_init(struct scx_sched *sch, const struct scx_cmask *src,
314 struct scx_cmask_ref *ref);
315void scx_cmask_ref_init_kern(struct scx_sched *sch, struct scx_cmask *m,
316 u32 base, u32 nr_cids, struct scx_cmask_ref *ref);
317void scx_cmask_ref_shard(const struct scx_cmask_ref *ref, s32 shard_idx,
318 struct scx_cmask *out);
319void scx_cmask_ref_from_cpumask(const struct scx_cmask_ref *ref,
320 const struct cpumask *cpumask);
321void scx_cmask_ref_or(const struct scx_cmask_ref *ref, const struct scx_cmask *src);
322void scx_cmask_ref_copy(const struct scx_cmask_ref *ref, const struct scx_cmask *src);
323
324#endif /* _KERNEL_SCHED_EXT_CID_H */