xref: /linux/kernel/sched/ext/cid.c (revision 3b1ce3e0ccba4aadbf6330a5ed8bda78f0c9353a)
1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst
4  *
5  * Copyright (c) 2026 Meta Platforms, Inc. and affiliates.
6  * Copyright (c) 2026 Tejun Heo <tj@kernel.org>
7  */
8 #include <linux/cacheinfo.h>
9 
10 #include "internal.h"
11 #include "cid.h"
12 
13 /*
14  * cid tables. The cid kfuncs are available whether the root scheduler is
15  * cid-form or cpu-form, the latter to allow gradual migration to cids, so every
16  * root builds a default mapping. Each root enable allocates a fresh set, builds
17  * it privately and publishes the __rcu globals below once the layout is final.
18  * Root disable unpublishes and RCU-frees the set. kfuncs may run before the
19  * tables are published and must check for NULL.
20  */
21 u32 scx_nr_cid_shards;
22 s16 __rcu *scx_cid_to_cpu_tbl;
23 s16 __rcu *scx_cpu_to_cid_tbl;
24 s32 __rcu *scx_cid_to_shard;
25 s32 __rcu *scx_shard_node;
26 struct scx_cid_shard __rcu *scx_cid_shard_ranges;
27 struct scx_cid_topo __rcu *scx_cid_topo;
28 
29 static struct scx_cid_tables *scx_cid_tables;	/* used only during alloc/free */
30 
31 #define SCX_CID_TOPO_NEG	(struct scx_cid_topo) {				\
32 	.core_cid = -1, .core_idx = -1, .llc_cid = -1, .llc_idx = -1,		\
33 	.node_cid = -1, .node_idx = -1, .shard_cid = -1, .shard_idx = -1,	\
34 	.cluster_cid = -1, .cluster_idx = -1,					\
35 }
36 
37 /*
38  * Return @cpu's LLC shared_cpu_map. If cacheinfo isn't populated (offline or
39  * !present), record @cpu in @fallbacks and return its node mask instead - the
40  * worst that can happen is that the cpu's LLC becomes coarser than reality.
41  */
42 static const struct cpumask *cpu_llc_mask(int cpu, struct cpumask *fallbacks)
43 {
44 	struct cpu_cacheinfo *ci = get_cpu_cacheinfo(cpu);
45 
46 	if (!ci || !ci->info_list || !ci->num_leaves) {
47 		cpumask_set_cpu(cpu, fallbacks);
48 		return cpumask_of_node(cpu_to_node(cpu));
49 	}
50 	return &ci->info_list[ci->num_leaves - 1].shared_cpu_map;
51 }
52 
53 /*
54  * Compute per-LLC shard layout. Each shard holds at most @shard_size cids, and
55  * in any case no more than SCX_CID_SHARD_MAX_CPUS. Cores are spread as evenly
56  * as possible across shards so cpu count is balanced: the first *@nr_large_p
57  * shards get (*@cores_per_shard_p + 1) cores, the rest get *@cores_per_shard_p.
58  */
59 static void calc_shard_layout(const struct cpumask *llc_cpus, u32 shard_size,
60 			      u32 *cores_per_shard_p, u32 *nr_large_p)
61 {
62 	u32 nr_cores = 0, nr_cpus = 0, nr_shards;
63 	int cpu;
64 
65 	for_each_cpu(cpu, llc_cpus) {
66 		nr_cpus++;
67 		/*
68 		 * scx_cid_init() forms each core from the siblings in
69 		 * @llc_cpus. The sibling mask may include cpus outside
70 		 * @llc_cpus, so count a core at its first sibling in @llc_cpus.
71 		 */
72 		if (cpumask_first_and(topology_sibling_cpumask(cpu),
73 				      llc_cpus) == cpu)
74 			nr_cores++;
75 	}
76 
77 	nr_shards = max_t(u32, 1, DIV_ROUND_UP(nr_cpus, shard_size));
78 	nr_shards = max_t(u32, nr_shards,
79 			  DIV_ROUND_UP(nr_cpus, SCX_CID_SHARD_MAX_CPUS));
80 
81 	*cores_per_shard_p = nr_cores / nr_shards;
82 	*nr_large_p = nr_cores % nr_shards;
83 }
84 
85 static void scx_cid_tables_free(struct scx_cid_tables *tbls)
86 {
87 	if (!tbls)
88 		return;
89 	kvfree(tbls->cid_to_cpu);
90 	kvfree(tbls->cpu_to_cid);
91 	kvfree(tbls->cid_to_shard);
92 	kvfree(tbls->shard_node);
93 	kvfree(tbls->shard_ranges);
94 	kvfree(tbls->topo);
95 	kfree(tbls);
96 }
97 
98 static void scx_cid_tables_free_rcufn(struct rcu_head *rcu)
99 {
100 	scx_cid_tables_free(container_of(rcu, struct scx_cid_tables, rcu));
101 }
102 
103 static struct scx_cid_tables *scx_cid_alloc_tables(void)
104 {
105 	u32 npossible = num_possible_cpus();
106 	struct scx_cid_tables *tbls;
107 
108 	tbls = kzalloc_obj(*tbls);
109 	if (!tbls)
110 		return NULL;
111 
112 	tbls->cid_to_cpu = kvzalloc_objs(*tbls->cid_to_cpu, npossible);
113 	tbls->cpu_to_cid = kvzalloc_objs(*tbls->cpu_to_cid, nr_cpu_ids);
114 	tbls->cid_to_shard = kvzalloc_objs(*tbls->cid_to_shard, npossible);
115 	tbls->shard_node = kvzalloc_objs(*tbls->shard_node, npossible);
116 	tbls->shard_ranges = kvzalloc_objs(*tbls->shard_ranges, npossible);
117 	tbls->topo = kvzalloc_objs(*tbls->topo, npossible);
118 
119 	if (!tbls->cid_to_cpu || !tbls->cpu_to_cid || !tbls->cid_to_shard ||
120 	    !tbls->shard_node || !tbls->shard_ranges || !tbls->topo) {
121 		scx_cid_tables_free(tbls);
122 		return NULL;
123 	}
124 
125 	return tbls;
126 }
127 
128 /**
129  * scx_cid_publish_tables - Publish the tables scx_cid_init() built
130  *
131  * Called after ops.init_cids() where the layout is final.
132  */
133 void scx_cid_publish_tables(void)
134 {
135 	struct scx_cid_tables *tbls = scx_cid_tables;
136 
137 	lockdep_assert_held(&scx_enable_mutex);
138 
139 	scx_nr_cid_shards = tbls->nr_shards;
140 	rcu_assign_pointer(scx_cid_to_cpu_tbl, tbls->cid_to_cpu);
141 	rcu_assign_pointer(scx_cpu_to_cid_tbl, tbls->cpu_to_cid);
142 	rcu_assign_pointer(scx_cid_to_shard, tbls->cid_to_shard);
143 	rcu_assign_pointer(scx_shard_node, tbls->shard_node);
144 	rcu_assign_pointer(scx_cid_shard_ranges, tbls->shard_ranges);
145 	rcu_assign_pointer(scx_cid_topo, tbls->topo);
146 }
147 
148 /**
149  * scx_cid_retire_tables - Unpublish and retire the cid tables
150  *
151  * Called by root disable after the readers which dereference without NULL
152  * checks are drained, inside cpus_read_lock() to exclude the hotplug path.
153  */
154 void scx_cid_retire_tables(void)
155 {
156 	struct scx_cid_tables *tbls = scx_cid_tables;
157 
158 	lockdep_assert_held(&scx_enable_mutex);
159 	lockdep_assert_cpus_held();
160 
161 	if (!tbls)
162 		return;
163 
164 	scx_cid_tables = NULL;
165 	RCU_INIT_POINTER(scx_cid_to_cpu_tbl, NULL);
166 	RCU_INIT_POINTER(scx_cpu_to_cid_tbl, NULL);
167 	RCU_INIT_POINTER(scx_cid_to_shard, NULL);
168 	RCU_INIT_POINTER(scx_shard_node, NULL);
169 	RCU_INIT_POINTER(scx_cid_shard_ranges, NULL);
170 	RCU_INIT_POINTER(scx_cid_topo, NULL);
171 	call_rcu(&tbls->rcu, scx_cid_tables_free_rcufn);
172 }
173 
174 /**
175  * scx_cid_init - build the cid mapping
176  * @sch: the scx_sched being initialized; used as the scx_error() target
177  *
178  * Build a fresh table set. It becomes visible through scx_cid_publish_tables()
179  * and is retired by scx_cid_retire_tables() at disable.
180  *
181  * See "Topological CPU IDs" in cid.h for the model. Walk online cpus by
182  * intersection at each level (parent_scratch & this_level_mask), which keeps
183  * containment correct by construction and naturally splits a physical LLC
184  * straddling two NUMA nodes into two LLC units. The caller must hold
185  * cpus_read_lock.
186  */
187 s32 scx_cid_init(struct scx_sched *sch)
188 {
189 	cpumask_var_t to_walk __free(free_cpumask_var) = CPUMASK_VAR_NULL;
190 	cpumask_var_t node_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL;
191 	cpumask_var_t llc_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL;
192 	cpumask_var_t cluster_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL;
193 	cpumask_var_t core_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL;
194 	cpumask_var_t llc_fallback __free(free_cpumask_var) = CPUMASK_VAR_NULL;
195 	cpumask_var_t online_no_topo __free(free_cpumask_var) = CPUMASK_VAR_NULL;
196 	struct scx_cid_tables *tbls;
197 	u32 next_cid = 0;
198 	s32 next_node_idx = 0, next_llc_idx = 0, next_core_idx = 0;
199 	s32 next_cluster_idx = 0;
200 	s32 next_shard_idx = 0;
201 	u32 shard_size, max_cids;
202 	u32 notopo_in_shard;
203 	s32 notopo_shard_cid, notopo_shard_idx;
204 	s32 cpu, cid, si;
205 
206 	/* CMASK_MAX_WORDS in cid.bpf.h covers NR_CPUS up to 8192 */
207 	BUILD_BUG_ON(NR_CPUS > 8192);
208 
209 	lockdep_assert_cpus_held();
210 	lockdep_assert_held(&scx_enable_mutex);
211 
212 	shard_size = sch->ops.cid_shard_size ?: SCX_CID_SHARD_SIZE_DFL;
213 	max_cids = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS);
214 
215 	tbls = scx_cid_alloc_tables();
216 	if (!tbls)
217 		return -ENOMEM;
218 
219 	scx_cid_tables = tbls;
220 
221 	for (si = 0; si < num_possible_cpus(); si++)
222 		tbls->shard_node[si] = NUMA_NO_NODE;
223 
224 	if (!zalloc_cpumask_var(&to_walk, GFP_KERNEL) ||
225 	    !zalloc_cpumask_var(&node_scratch, GFP_KERNEL) ||
226 	    !zalloc_cpumask_var(&llc_scratch, GFP_KERNEL) ||
227 	    !zalloc_cpumask_var(&cluster_scratch, GFP_KERNEL) ||
228 	    !zalloc_cpumask_var(&core_scratch, GFP_KERNEL) ||
229 	    !zalloc_cpumask_var(&llc_fallback, GFP_KERNEL) ||
230 	    !zalloc_cpumask_var(&online_no_topo, GFP_KERNEL))
231 		return -ENOMEM;
232 
233 	/* -1 sentinels for sparse-possible cpu id holes (0 is a valid cid) */
234 	for (cpu = 0; cpu < nr_cpu_ids; cpu++)
235 		tbls->cpu_to_cid[cpu] = -1;
236 
237 	cpumask_copy(to_walk, cpu_online_mask);
238 
239 	while (!cpumask_empty(to_walk)) {
240 		s32 next_cpu = cpumask_first(to_walk);
241 		s32 nid = cpu_to_node(next_cpu);
242 		s32 node_cid = next_cid;
243 		s32 node_idx;
244 
245 		/*
246 		 * No NUMA info: skip and let the tail loop assign a no-topo
247 		 * cid. cpumask_of_node(-1) is undefined.
248 		 */
249 		if (nid < 0) {
250 			cpumask_clear_cpu(next_cpu, to_walk);
251 			continue;
252 		}
253 
254 		node_idx = next_node_idx++;
255 
256 		/* node_scratch = to_walk & this node */
257 		cpumask_and(node_scratch, to_walk, cpumask_of_node(nid));
258 		if (WARN_ON_ONCE(!cpumask_test_cpu(next_cpu, node_scratch)))
259 			return -EINVAL;
260 
261 		while (!cpumask_empty(node_scratch)) {
262 			s32 ncpu = cpumask_first(node_scratch);
263 			const struct cpumask *llc_mask = cpu_llc_mask(ncpu, llc_fallback);
264 			s32 llc_cid = next_cid;
265 			s32 llc_idx = next_llc_idx++;
266 			u32 cores_per_shard, nr_large;
267 			u32 shard_local = 0, cores_in_shard = 0, cids_in_shard = 0;
268 			s32 shard_cid, shard_idx;
269 			s32 cluster_cid = -1, cluster_idx = -1;
270 
271 			/* llc_scratch = node_scratch & this llc */
272 			cpumask_and(llc_scratch, node_scratch, llc_mask);
273 			if (WARN_ON_ONCE(!cpumask_test_cpu(ncpu, llc_scratch)))
274 				return -EINVAL;
275 
276 			calc_shard_layout(llc_scratch, shard_size, &cores_per_shard, &nr_large);
277 			shard_cid = next_cid;
278 			shard_idx = next_shard_idx++;
279 			tbls->shard_node[shard_idx] = nid;
280 
281 			while (!cpumask_empty(llc_scratch)) {
282 				const struct cpumask *sib;
283 				s32 core_cid, core_idx, lcpu, ccpu;
284 				u32 max_cores, cids_in_core;
285 
286 				/*
287 				 * Take the cores of one cluster before moving
288 				 * on, so that a cluster is a contiguous cid
289 				 * range like the core, LLC and node levels.
290 				 */
291 				if (cpumask_empty(cluster_scratch)) {
292 					s32 xcpu = cpumask_first(llc_scratch);
293 
294 					cpumask_or(cluster_scratch, topology_cluster_cpumask(xcpu),
295 						   topology_sibling_cpumask(xcpu));
296 					cpumask_and(cluster_scratch, cluster_scratch, llc_scratch);
297 					cluster_cid = next_cid;
298 					cluster_idx = next_cluster_idx++;
299 				}
300 
301 				lcpu = cpumask_first(cluster_scratch);
302 				sib = topology_sibling_cpumask(lcpu);
303 				core_cid = next_cid;
304 				core_idx = next_core_idx++;
305 
306 				/* core_scratch = cluster_scratch & this core */
307 				cpumask_and(core_scratch, cluster_scratch, sib);
308 				if (WARN_ON_ONCE(!cpumask_test_cpu(lcpu, core_scratch)))
309 					return -EINVAL;
310 
311 				/*
312 				 * Advance to a new shard when either core or
313 				 * cid count reaches max. The latter bounds
314 				 * shard sizes under uneven SMT. Never start an
315 				 * empty shard.
316 				 */
317 				cids_in_core = cpumask_weight(core_scratch);
318 				if (cids_in_core > SCX_CID_SHARD_MAX_CPUS) {
319 					scx_error(sch, "core with %u cpus exceeds max shard size %d",
320 						  cids_in_core, SCX_CID_SHARD_MAX_CPUS);
321 					return -E2BIG;
322 				}
323 
324 				max_cores = cores_per_shard + (shard_local < nr_large ? 1 : 0);
325 				if (cores_in_shard &&
326 				    (cores_in_shard >= max_cores ||
327 				     cids_in_shard + cids_in_core > max_cids)) {
328 					shard_local++;
329 					cores_in_shard = 0;
330 					cids_in_shard = 0;
331 					shard_cid = next_cid;
332 					shard_idx = next_shard_idx++;
333 					tbls->shard_node[shard_idx] = nid;
334 				}
335 				cores_in_shard++;
336 				cids_in_shard += cids_in_core;
337 
338 				for_each_cpu(ccpu, core_scratch) {
339 					s32 cid = next_cid++;
340 
341 					tbls->cid_to_cpu[cid] = ccpu;
342 					tbls->cpu_to_cid[ccpu] = cid;
343 					tbls->cid_to_shard[cid] = shard_idx;
344 					tbls->topo[cid] = (struct scx_cid_topo){
345 						.core_cid = core_cid,
346 						.core_idx = core_idx,
347 						.llc_cid = llc_cid,
348 						.llc_idx = llc_idx,
349 						.node_cid = node_cid,
350 						.node_idx = node_idx,
351 						.shard_cid = shard_cid,
352 						.shard_idx = shard_idx,
353 						.cluster_cid = cluster_cid,
354 						.cluster_idx = cluster_idx,
355 					};
356 
357 					cpumask_clear_cpu(ccpu, cluster_scratch);
358 					cpumask_clear_cpu(ccpu, llc_scratch);
359 					cpumask_clear_cpu(ccpu, node_scratch);
360 					cpumask_clear_cpu(ccpu, to_walk);
361 				}
362 			}
363 		}
364 	}
365 
366 	/*
367 	 * No-topo section: any possible cpu without a cid - normally just the
368 	 * not-online ones. Pack into shards of up to min(@shard_size,
369 	 * SCX_CID_SHARD_MAX_CPUS) cids so that every cid has a valid shard
370 	 * assignment and the hard cap holds even with a large @shard_size.
371 	 * Collect any currently-online cpus that land here in @online_no_topo
372 	 * so we can warn about them at the end.
373 	 */
374 	notopo_in_shard = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS);
375 	notopo_shard_cid = -1;
376 	notopo_shard_idx = -1;
377 
378 	for_each_cpu(cpu, cpu_possible_mask) {
379 		if (tbls->cpu_to_cid[cpu] != -1)
380 			continue;
381 		if (cpu_online(cpu))
382 			cpumask_set_cpu(cpu, online_no_topo);
383 
384 		cid = next_cid++;
385 		tbls->cid_to_cpu[cid] = cpu;
386 		tbls->cpu_to_cid[cpu] = cid;
387 
388 		if (notopo_in_shard >= min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS)) {
389 			notopo_shard_cid = cid;
390 			notopo_shard_idx = next_shard_idx++;
391 			notopo_in_shard = 0;
392 		}
393 		notopo_in_shard++;
394 
395 		tbls->cid_to_shard[cid] = notopo_shard_idx;
396 		tbls->topo[cid] = SCX_CID_TOPO_NEG;
397 		tbls->topo[cid].shard_cid = notopo_shard_cid;
398 		tbls->topo[cid].shard_idx = notopo_shard_idx;
399 	}
400 
401 	if (!cpumask_empty(llc_fallback))
402 		pr_warn("scx_cid: cpus without cacheinfo, using node mask as llc: %*pbl\n",
403 			cpumask_pr_args(llc_fallback));
404 	if (!cpumask_empty(online_no_topo))
405 		pr_warn("scx_cid: online cpus with no usable topology: %*pbl\n",
406 			cpumask_pr_args(online_no_topo));
407 
408 	/*
409 	 * Fill cid_shard_ranges[] from cid_to_shard[]. Shards are contiguous
410 	 * cid ranges by construction: base_cid is the first cid landing in a
411 	 * shard, nr_cids is the count.
412 	 */
413 	for (cid = 0; cid < next_cid; cid++) {
414 		s32 sidx = tbls->cid_to_shard[cid];
415 
416 		if (tbls->shard_ranges[sidx].nr_cids == 0)
417 			tbls->shard_ranges[sidx].base_cid = cid;
418 		tbls->shard_ranges[sidx].nr_cids++;
419 	}
420 
421 	tbls->nr_shards = next_shard_idx;
422 	return 0;
423 }
424 
425 /**
426  * scx_cmask_clear - Zero every bit in @m's active range
427  * @m: cmask to clear
428  *
429  * Storage past the active range is left as is.
430  */
431 void scx_cmask_clear(struct scx_cmask *m)
432 {
433 	u32 nr_words;
434 
435 	if (!m->nr_cids)
436 		return;
437 	nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1;
438 	memset(m->bits, 0, nr_words * sizeof(u64));
439 }
440 
441 /**
442  * scx_cmask_fill - Set every bit in @m's active range
443  * @m: cmask to fill
444  *
445  * Counterpart to scx_cmask_clear(). Storage past the active range is left as is.
446  */
447 void scx_cmask_fill(struct scx_cmask *m)
448 {
449 	u32 nr_words, head_bits, tail_bits;
450 
451 	if (!m->nr_cids)
452 		return;
453 	nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1;
454 	memset(m->bits, 0xff, nr_words * sizeof(u64));
455 
456 	/* clear word-0 bits below base */
457 	head_bits = m->base & 63;
458 	if (head_bits)
459 		m->bits[0] &= ~((1ULL << head_bits) - 1);
460 
461 	/* clear last-word bits at or past base + nr_cids */
462 	tail_bits = (m->base + m->nr_cids) & 63;
463 	if (tail_bits)
464 		m->bits[nr_words - 1] &= (1ULL << tail_bits) - 1;
465 }
466 
467 /*
468  * Return the index of the largest entry in @counts, or NUMA_NO_NODE if all
469  * entries are zero. Ties resolve to the lowest index.
470  */
471 static s32 pick_max_node(const u32 *counts, u32 n)
472 {
473 	s32 best = NUMA_NO_NODE;
474 	u32 best_count = 0, i;
475 
476 	for (i = 0; i < n; i++) {
477 		if (counts[i] > best_count) {
478 			best_count = counts[i];
479 			best = i;
480 		}
481 	}
482 	return best;
483 }
484 
485 __bpf_kfunc_start_defs();
486 
487 /**
488  * scx_bpf_cid_override - Install an explicit cpu->cid mapping with shard info
489  * @cpu_to_cid__arena: array of nr_cpu_ids s32 entries (cid for each cpu)
490  * @cpu_to_cid_cnt: number of entries, must be nr_cpu_ids
491  * @shard_start__arena: array of first-cid-of-each-shard, one entry per shard
492  * @shard_start_cnt: number of shards
493  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
494  *
495  * May only be called from ops.init_cids() of the root scheduler. Replace the
496  * topology-probed cid mapping and shard layout with caller-provided ones. Each
497  * possible cpu must map to a unique cid in [0, num_possible_cpus()). The shard
498  * starts must be strictly increasing with the first entry 0 and all values <
499  * num_possible_cpus(). The last shard extends to num_possible_cpus() and no
500  * shard may span more than SCX_CID_SHARD_MAX_CPUS cids. Topo info
501  * (core/cluster/LLC/node) is cleared and the shard layout is set from the
502  * input. On invalid input, abort the scheduler.
503  */
504 __bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid__arena, u32 cpu_to_cid_cnt,
505 				      const s32 *shard_start__arena, u32 shard_start_cnt,
506 				      const struct bpf_prog_aux *aux)
507 {
508 	cpumask_var_t seen __free(free_cpumask_var) = CPUMASK_VAR_NULL;
509 	u32 *node_counts __free(kfree) = NULL;
510 	s32 *cpu_to_cid __free(kfree) = NULL;
511 	s32 *shard_start __free(kfree) = NULL;
512 	u32 npossible = num_possible_cpus();
513 	struct scx_cid_tables *tbls;
514 	struct scx_sched *sch;
515 	u32 nr_shards = shard_start_cnt;
516 	bool alloced;
517 	s32 cpu, cid, si;
518 
519 	/*
520 	 * GFP_KERNEL allocs must happen before the rcu read section. Snapshot
521 	 * the BPF-supplied arrays so a concurrent arena write can't change
522 	 * them between validation and use.
523 	 *
524 	 * The BPF-supplied counts size the snapshots and thus the arena reads.
525 	 * Gate the copies on the count bounds, reported below once @sch is
526 	 * available. The bounded reads, at most 32KB, stay within the guard
527 	 * region that arena fault recovery covers.
528 	 */
529 	alloced = zalloc_cpumask_var(&seen, GFP_KERNEL);
530 	node_counts = kzalloc_objs(*node_counts, nr_node_ids);
531 	if (cpu_to_cid_cnt == nr_cpu_ids)
532 		cpu_to_cid = kmemdup(cpu_to_cid__arena, cpu_to_cid_cnt * sizeof(s32),
533 				     GFP_KERNEL);
534 	if (nr_shards && nr_shards <= npossible)
535 		shard_start = kmemdup(shard_start__arena, nr_shards * sizeof(s32),
536 				      GFP_KERNEL);
537 
538 	guard(rcu)();
539 
540 	sch = scx_prog_sched(aux);
541 	if (unlikely(!sch))
542 		return;
543 
544 	/* called from ops.init_cids(), so the tables exist and are unpublished */
545 	lockdep_assert_held(&scx_enable_mutex);
546 	tbls = scx_cid_tables;
547 
548 	if (cpu_to_cid_cnt != nr_cpu_ids) {
549 		scx_error(sch, "scx_bpf_cid_override: cpu_to_cid expected %u entries, got %u",
550 			  nr_cpu_ids, cpu_to_cid_cnt);
551 		return;
552 	}
553 
554 	if (!nr_shards || nr_shards > npossible) {
555 		scx_error(sch, "scx_bpf_cid_override: invalid shard_start count %u",
556 			  nr_shards);
557 		return;
558 	}
559 
560 	if (!alloced || !node_counts || !cpu_to_cid || !shard_start) {
561 		scx_error(sch, "scx_bpf_cid_override: allocation failed");
562 		return;
563 	}
564 
565 	/* validate shard_start[]: starts at 0, strictly increasing, in range */
566 	if (shard_start[0] != 0) {
567 		scx_error(sch, "scx_bpf_cid_override: shard_start[0] must be 0, got %d",
568 			  shard_start[0]);
569 		return;
570 	}
571 	for (si = 1; si < nr_shards; si++) {
572 		if (shard_start[si] <= shard_start[si - 1]) {
573 			scx_error(sch, "scx_bpf_cid_override: shard_start not increasing at [%d]",
574 				  si);
575 			return;
576 		}
577 		if (shard_start[si] >= npossible) {
578 			scx_error(sch, "scx_bpf_cid_override: shard_start[%d]=%d >= %u",
579 				  si, shard_start[si], npossible);
580 			return;
581 		}
582 		if (shard_start[si] - shard_start[si - 1] > SCX_CID_SHARD_MAX_CPUS) {
583 			scx_error(sch, "scx_bpf_cid_override: shard[%d] span %d exceeds max %d",
584 				  si - 1, shard_start[si] - shard_start[si - 1],
585 				  SCX_CID_SHARD_MAX_CPUS);
586 			return;
587 		}
588 	}
589 	if (npossible - shard_start[nr_shards - 1] > SCX_CID_SHARD_MAX_CPUS) {
590 		scx_error(sch, "scx_bpf_cid_override: shard[%d] span %d exceeds max %d",
591 			  nr_shards - 1, npossible - shard_start[nr_shards - 1],
592 			  SCX_CID_SHARD_MAX_CPUS);
593 		return;
594 	}
595 
596 	/* validate first so that invalid input leaves the tables untouched */
597 	for_each_possible_cpu(cpu) {
598 		s32 c = cpu_to_cid[cpu];
599 
600 		if (!cid_valid(sch, c))
601 			return;
602 		if (cpumask_test_and_set_cpu(c, seen)) {
603 			scx_error(sch, "cid %d assigned to multiple cpus", c);
604 			return;
605 		}
606 	}
607 
608 	for_each_possible_cpu(cpu) {
609 		s32 c = cpu_to_cid[cpu];
610 
611 		tbls->cpu_to_cid[cpu] = c;
612 		tbls->cid_to_cpu[c] = cpu;
613 	}
614 
615 	/*
616 	 * Derive shard_node[] by majority count: an overridden shard may
617 	 * span NUMA nodes, so assign each to the node that owns the most cpus.
618 	 */
619 	for (si = 0; si < nr_shards; si++) {
620 		u32 end = (si + 1 < nr_shards) ? shard_start[si + 1] : npossible;
621 
622 		memset(node_counts, 0, nr_node_ids * sizeof(*node_counts));
623 		for (cid = shard_start[si]; cid < end; cid++) {
624 			s32 node = cpu_to_node(tbls->cid_to_cpu[cid]);
625 
626 			if (numa_valid_node(node))
627 				node_counts[node]++;
628 		}
629 		tbls->shard_node[si] = pick_max_node(node_counts, nr_node_ids);
630 	}
631 
632 	/*
633 	 * Invalidate stale topo info and install shard layout from
634 	 * @shard_start. Walk shards to derive shard_cid/shard_idx for each cid.
635 	 */
636 	si = 0;
637 	for (cid = 0; cid < npossible; cid++) {
638 		if (si + 1 < nr_shards && cid >= shard_start[si + 1])
639 			si++;
640 		tbls->cid_to_shard[cid] = si;
641 		tbls->topo[cid] = SCX_CID_TOPO_NEG;
642 		tbls->topo[cid].shard_cid = shard_start[si];
643 		tbls->topo[cid].shard_idx = si;
644 	}
645 
646 	/* Rebuild shard_ranges[] for the new layout. */
647 	memset(tbls->shard_ranges, 0, npossible * sizeof(*tbls->shard_ranges));
648 	for (si = 0; si < nr_shards; si++) {
649 		u32 end = (si + 1 < nr_shards) ? shard_start[si + 1] : npossible;
650 
651 		tbls->shard_ranges[si].base_cid = shard_start[si];
652 		tbls->shard_ranges[si].nr_cids = end - shard_start[si];
653 	}
654 
655 	tbls->nr_shards = nr_shards;
656 }
657 
658 /**
659  * scx_bpf_cid_to_cpu - Return the raw CPU id for @cid
660  * @cid: cid to look up
661  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
662  *
663  * Return the raw CPU id for @cid. Trigger scx_error() and return -EINVAL if
664  * @cid is invalid. The cid<->cpu mapping is static for the lifetime of the
665  * loaded scheduler, so the BPF side can cache the result to avoid repeated
666  * kfunc invocations.
667  */
668 __bpf_kfunc s32 scx_bpf_cid_to_cpu(s32 cid, const struct bpf_prog_aux *aux)
669 {
670 	struct scx_sched *sch;
671 
672 	guard(rcu)();
673 
674 	sch = scx_prog_sched(aux);
675 	if (unlikely(!sch))
676 		return -EINVAL;
677 	return scx_cid_to_cpu(sch, cid);
678 }
679 
680 /**
681  * scx_bpf_cid_node - Return the NUMA node the given @cid belongs to
682  * @cid: cid to look up
683  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
684  *
685  * Return NUMA_NO_NODE if @cid is invalid or there is no scheduler. Unlike
686  * scx_bpf_cpu_node(), this kfunc is available only with CID support, so BPF
687  * schedulers can use its presence to detect NUMA-aware CID lookups.
688  */
689 __bpf_kfunc s32 scx_bpf_cid_node(s32 cid, const struct bpf_prog_aux *aux)
690 {
691 	struct scx_sched *sch;
692 	s32 cpu;
693 
694 	guard(rcu)();
695 
696 	sch = scx_prog_sched(aux);
697 	if (unlikely(!sch))
698 		return NUMA_NO_NODE;
699 	cpu = scx_cid_to_cpu(sch, cid);
700 	return cpu < 0 ? NUMA_NO_NODE : cpu_to_node(cpu);
701 }
702 
703 /**
704  * scx_bpf_cpu_to_cid - Return the cid for @cpu
705  * @cpu: cpu to look up
706  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
707  *
708  * Return the cid for @cpu. Trigger scx_error() and return -EINVAL if @cpu is
709  * invalid. The cid<->cpu mapping is static for the lifetime of the loaded
710  * scheduler, so the BPF side can cache the result to avoid repeated kfunc
711  * invocations.
712  */
713 __bpf_kfunc s32 scx_bpf_cpu_to_cid(s32 cpu, const struct bpf_prog_aux *aux)
714 {
715 	struct scx_sched *sch;
716 
717 	guard(rcu)();
718 
719 	sch = scx_prog_sched(aux);
720 	if (unlikely(!sch))
721 		return -EINVAL;
722 	return scx_cpu_to_cid(sch, cpu);
723 }
724 
725 /*
726  * Set ops on cmasks. cmask_walk_op2() shares one walk across mutating
727  * (and/or/copy/andnot) and predicate (subset/intersects) two-cmask forms;
728  * cmask_walk_op1() does the same shape over a single cmask range. Every public
729  * entry passes a compile-time-constant @op; cmask_walk_op{1,2}() and
730  * cmask_word_op{1,2}() are __always_inline so the inner switch collapses to the
731  * selected op and cmask_op2_is_pred() folds the predicate early-exit out of
732  * mutating ops.
733  *
734  * Two-cmask ops only touch @dst bits inside the intersection of the two ranges;
735  * bits outside stay untouched. In particular, scx_cmask_copy() does NOT zero
736  * @dst bits that lie outside @src's range.
737  *
738  * Word accesses use READ_ONCE/WRITE_ONCE so a caller may read @src
739  * locklessly. Memory ordering against concurrent writers is the caller's
740  * responsibility.
741  */
742 enum cmask_op2 {
743 	/* mutating */
744 	CMASK_OP2_AND,
745 	CMASK_OP2_OR,
746 	CMASK_OP2_COPY,
747 	CMASK_OP2_ANDNOT,
748 	/* predicates - short-circuit when the per-word result is true */
749 	CMASK_OP2_SUBSET,
750 	CMASK_OP2_INTERSECTS,
751 	/*
752 	 * @a is a BPF-arena cmask. Words on @a use READ_ONCE/WRITE_ONCE since
753 	 * BPF may read/write concurrently. See scx_cmask_ref_or() / _copy().
754 	 */
755 	CMASK_OP2_REF_OR,
756 	CMASK_OP2_REF_COPY,
757 };
758 
759 static __always_inline bool cmask_op2_is_pred(const enum cmask_op2 op)
760 {
761 	return op == CMASK_OP2_SUBSET || op == CMASK_OP2_INTERSECTS;
762 }
763 
764 static __always_inline bool cmask_word_op2(u64 *av, const u64 *bp, u64 mask,
765 					   const enum cmask_op2 op)
766 {
767 	switch (op) {
768 	case CMASK_OP2_AND:
769 		WRITE_ONCE(*av, *av & (~mask | READ_ONCE(*bp)));
770 		return false;
771 	case CMASK_OP2_OR:
772 		WRITE_ONCE(*av, *av | (READ_ONCE(*bp) & mask));
773 		return false;
774 	case CMASK_OP2_COPY:
775 		WRITE_ONCE(*av, (*av & ~mask) | (READ_ONCE(*bp) & mask));
776 		return false;
777 	case CMASK_OP2_ANDNOT:
778 		WRITE_ONCE(*av, *av & ~(READ_ONCE(*bp) & mask));
779 		return false;
780 	case CMASK_OP2_SUBSET:
781 		/* stop on the first bit in @sub not set in @super */
782 		return (READ_ONCE(*bp) & ~READ_ONCE(*av)) & mask;
783 	case CMASK_OP2_INTERSECTS:
784 		return (READ_ONCE(*av) & READ_ONCE(*bp)) & mask;
785 	case CMASK_OP2_REF_OR:
786 		WRITE_ONCE(*av, READ_ONCE(*av) | (READ_ONCE(*bp) & mask));
787 		return false;
788 	case CMASK_OP2_REF_COPY:
789 		WRITE_ONCE(*av, (READ_ONCE(*av) & ~mask) | (READ_ONCE(*bp) & mask));
790 		return false;
791 	}
792 	unreachable();
793 }
794 
795 /*
796  * Walk the intersection of [@a_base, @a_base + @a_nr_cids) with [@b_base,
797  * @b_base + @b_nr_cids) word by word, applying @op. Mutating ops walk all words
798  * and return false; predicates return true on the first word whose per-word
799  * test is true. Empty intersection returns false (matches "no bits to consider"
800  * for both mutate and predicate).
801  *
802  * Base/nr_cids are taken as parameters so callers with snapshotted bounds can
803  * drive the walk with values independent of the cmask's header.
804  */
805 static __always_inline bool cmask_walk_op2(u64 *a_bits, u32 a_base, u32 a_nr_cids,
806 					   const u64 *b_bits, u32 b_base, u32 b_nr_cids,
807 					   const enum cmask_op2 op)
808 {
809 	u32 lo = max(a_base, b_base);
810 	u32 hi = min(a_base + a_nr_cids, b_base + b_nr_cids);
811 	u32 a_word_off = a_base / 64;
812 	u32 b_word_off = b_base / 64;
813 	u32 lo_word = lo / 64;
814 	u32 hi_word = (hi - 1) / 64;
815 	u64 head_mask = GENMASK_U64(63, lo & 63);
816 	u64 tail_mask = GENMASK_U64((hi - 1) & 63, 0);
817 	u32 w;
818 
819 	if (lo >= hi)
820 		return false;
821 
822 	if (lo_word == hi_word)
823 		return cmask_word_op2(&a_bits[lo_word - a_word_off],
824 				      &b_bits[lo_word - b_word_off],
825 				      head_mask & tail_mask, op);
826 
827 	if (cmask_word_op2(&a_bits[lo_word - a_word_off],
828 			   &b_bits[lo_word - b_word_off], head_mask, op) &&
829 	    cmask_op2_is_pred(op))
830 		return true;
831 
832 	for (w = lo_word + 1; w < hi_word; w++)
833 		if (cmask_word_op2(&a_bits[w - a_word_off],
834 				   &b_bits[w - b_word_off], ~0ULL, op) &&
835 		    cmask_op2_is_pred(op))
836 			return true;
837 
838 	return cmask_word_op2(&a_bits[hi_word - a_word_off],
839 			      &b_bits[hi_word - b_word_off], tail_mask, op);
840 }
841 
842 enum cmask_op1 {
843 	CMASK_OP1_ANY_SET,
844 };
845 
846 static __always_inline bool cmask_word_op1(const u64 *ap, u64 mask,
847 					   const enum cmask_op1 op)
848 {
849 	switch (op) {
850 	case CMASK_OP1_ANY_SET:
851 		return READ_ONCE(*ap) & mask;
852 	}
853 	unreachable();
854 }
855 
856 /*
857  * Walk [@a_base, @a_base + @a_nr_cids) of @a_bits word by word, applying @op.
858  * Returns true on the first word whose per-word test is true; returns false if
859  * no word matches or the range is empty. All current op1s short-circuit on
860  * per-word true; if a non-predicate op1 lands here, add a cmask_op1_is_pred()
861  * guard analogous to cmask_op2_is_pred().
862  */
863 static __always_inline bool cmask_walk_op1(const u64 *a_bits, u32 a_base,
864 					   u32 a_nr_cids,
865 					   const enum cmask_op1 op)
866 {
867 	u32 lo = a_base;
868 	u32 hi = a_base + a_nr_cids;
869 	u32 a_word_off = a_base / 64;
870 	u32 lo_word = lo / 64;
871 	u32 hi_word = (hi - 1) / 64;
872 	u64 head_mask = GENMASK_U64(63, lo & 63);
873 	u64 tail_mask = GENMASK_U64((hi - 1) & 63, 0);
874 	u32 w;
875 
876 	if (lo >= hi)
877 		return false;
878 
879 	if (lo_word == hi_word)
880 		return cmask_word_op1(&a_bits[lo_word - a_word_off],
881 				      head_mask & tail_mask, op);
882 
883 	if (cmask_word_op1(&a_bits[lo_word - a_word_off], head_mask, op))
884 		return true;
885 	for (w = lo_word + 1; w < hi_word; w++)
886 		if (cmask_word_op1(&a_bits[w - a_word_off], ~0ULL, op))
887 			return true;
888 	return cmask_word_op1(&a_bits[hi_word - a_word_off], tail_mask, op);
889 }
890 
891 void scx_cmask_and(struct scx_cmask *dst, const struct scx_cmask *src)
892 {
893 	cmask_walk_op2(dst->bits, dst->base, dst->nr_cids,
894 		       src->bits, src->base, src->nr_cids, CMASK_OP2_AND);
895 }
896 
897 void scx_cmask_or(struct scx_cmask *dst, const struct scx_cmask *src)
898 {
899 	cmask_walk_op2(dst->bits, dst->base, dst->nr_cids,
900 		       src->bits, src->base, src->nr_cids, CMASK_OP2_OR);
901 }
902 
903 void scx_cmask_copy(struct scx_cmask *dst, const struct scx_cmask *src)
904 {
905 	cmask_walk_op2(dst->bits, dst->base, dst->nr_cids,
906 		       src->bits, src->base, src->nr_cids, CMASK_OP2_COPY);
907 }
908 
909 void scx_cmask_andnot(struct scx_cmask *dst, const struct scx_cmask *src)
910 {
911 	cmask_walk_op2(dst->bits, dst->base, dst->nr_cids,
912 		       src->bits, src->base, src->nr_cids, CMASK_OP2_ANDNOT);
913 }
914 
915 /*
916  * Return true if @cm has any bit set in [@lo, @hi). Caller must ensure
917  * [@lo, @hi) is contained in @cm's range.
918  */
919 static bool cmask_any_set_in_range(const struct scx_cmask *cm, u32 lo, u32 hi)
920 {
921 	if (lo >= hi)
922 		return false;
923 	return cmask_walk_op1(&cm->bits[lo / 64 - cm->base / 64], lo, hi - lo,
924 			      CMASK_OP1_ANY_SET);
925 }
926 
927 /**
928  * scx_cmask_subset - test whether @sub is a subset of @super
929  * @sub: cmask to test
930  * @super: cmask to test against
931  *
932  * Return true iff every set bit of @sub is also set in @super.
933  */
934 bool scx_cmask_subset(const struct scx_cmask *sub, const struct scx_cmask *super)
935 {
936 	u32 super_end = super->base + super->nr_cids;
937 	u32 sub_end = sub->base + sub->nr_cids;
938 
939 	/*
940 	 * Set bits in @sub outside @super's range can't be in @super, so any
941 	 * such bit means not a subset. The walk below only visits words
942 	 * common to both ranges, so these need a separate scan.
943 	 */
944 	if (sub->base < super->base &&
945 	    cmask_any_set_in_range(sub, sub->base, min(super->base, sub_end)))
946 		return false;
947 	if (sub_end > super_end &&
948 	    cmask_any_set_in_range(sub, max(sub->base, super_end), sub_end))
949 		return false;
950 
951 	return !cmask_walk_op2((u64 *)super->bits, super->base, super->nr_cids,
952 			       sub->bits, sub->base, sub->nr_cids, CMASK_OP2_SUBSET);
953 }
954 
955 bool scx_cmask_intersects(const struct scx_cmask *a, const struct scx_cmask *b)
956 {
957 	return cmask_walk_op2((u64 *)a->bits, a->base, a->nr_cids,
958 			      b->bits, b->base, b->nr_cids, CMASK_OP2_INTERSECTS);
959 }
960 
961 /**
962  * scx_cmask_empty - Test whether @m has no bits set
963  * @m: cmask to test
964  *
965  * Return true iff @m's active range has no bits set.
966  */
967 bool scx_cmask_empty(const struct scx_cmask *m)
968 {
969 	return !cmask_any_set_in_range(m, m->base, m->base + m->nr_cids);
970 }
971 
972 /**
973  * scx_bpf_cid_topo - Copy out per-cid topology info
974  * @cid: cid to look up
975  * @out: where to copy the topology info
976  * @out__sz: size of @out, the program's sizeof(struct scx_cid_topo)
977  * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs
978  *
979  * Fill @out with the topology info for @cid. Trigger scx_error() if @cid is out
980  * of range. If @cid is valid but in the no-topo section, all fields are set to
981  * -1. All fields are also set to -1 when no cid tables have been published yet,
982  * which a program may observe while racing the root enable.
983  *
984  * The program's struct may be older or newer than the kernel's. The smaller of
985  * @out__sz and the kernel's size is copied and the rest of @out is set to -1.
986  */
987 __bpf_kfunc void scx_bpf_cid_topo(s32 cid, struct scx_cid_topo *out, size_t out__sz,
988 				  const struct bpf_prog_aux *aux)
989 {
990 	size_t len = min(out__sz, sizeof(*out));
991 	struct scx_cid_topo *topo;
992 	struct scx_sched *sch;
993 
994 	/* the error cases and fields the kernel lacks read as -1 */
995 	memset(out, 0xff, out__sz);
996 
997 	guard(rcu)();
998 
999 	sch = scx_prog_sched(aux);
1000 	topo = rcu_dereference(scx_cid_topo);
1001 	if (unlikely(!sch) || !cid_valid(sch, cid) || unlikely(!topo))
1002 		return;
1003 
1004 	memcpy(out, &topo[cid], len);
1005 }
1006 
1007 __bpf_kfunc_end_defs();
1008 
1009 BTF_KFUNCS_START(scx_kfunc_ids_init_cids)
1010 BTF_ID_FLAGS(func, scx_bpf_cid_override, KF_IMPLICIT_ARGS | KF_SLEEPABLE)
1011 BTF_KFUNCS_END(scx_kfunc_ids_init_cids)
1012 
1013 static const struct btf_kfunc_id_set scx_kfunc_set_init_cids = {
1014 	.owner	= THIS_MODULE,
1015 	.set	= &scx_kfunc_ids_init_cids,
1016 	.filter	= scx_kfunc_context_filter,
1017 };
1018 
1019 BTF_KFUNCS_START(scx_kfunc_ids_cid)
1020 BTF_ID_FLAGS(func, scx_bpf_cid_to_cpu, KF_IMPLICIT_ARGS)
1021 BTF_ID_FLAGS(func, scx_bpf_cid_node, KF_IMPLICIT_ARGS)
1022 BTF_ID_FLAGS(func, scx_bpf_cpu_to_cid, KF_IMPLICIT_ARGS)
1023 BTF_ID_FLAGS(func, scx_bpf_cid_topo, KF_IMPLICIT_ARGS)
1024 BTF_KFUNCS_END(scx_kfunc_ids_cid)
1025 
1026 static const struct btf_kfunc_id_set scx_kfunc_set_cid = {
1027 	.owner	= THIS_MODULE,
1028 	.set	= &scx_kfunc_ids_cid,
1029 };
1030 
1031 /**
1032  * scx_cmask_ref_init - Bind a scx_cmask_ref to a BPF-arena cmask
1033  * @sch: scheduler whose arena hosts @src
1034  * @src: BPF-supplied cmask, rebased to its kernel address
1035  * @ref: output ref
1036  *
1037  * Snapshot @src's @base, @nr_cids and @alloc_words. The snapshot is necessary
1038  * because BPF may mutate the live header asynchronously.
1039  *
1040  * Return 0 on success, -EINVAL if the range is out of bounds or @alloc_words
1041  * doesn't cover it.
1042  */
1043 int scx_cmask_ref_init(struct scx_sched *sch, const struct scx_cmask *src,
1044 		       struct scx_cmask_ref *ref)
1045 {
1046 	u32 base, nr_cids, alloc_words, npossible = num_possible_cpus();
1047 	s32 *cid_to_shard;
1048 
1049 	base = READ_ONCE(src->base);
1050 	nr_cids = READ_ONCE(src->nr_cids);
1051 	alloc_words = READ_ONCE(src->alloc_words);
1052 
1053 	if (unlikely(base >= npossible || nr_cids > npossible - base ||
1054 		     SCX_CMASK_NR_WORDS(nr_cids) > alloc_words))
1055 		return -EINVAL;
1056 
1057 	ref->sch = sch;
1058 	ref->src = (struct scx_cmask *)src;
1059 	ref->base = base;
1060 	ref->nr_cids = nr_cids;
1061 
1062 	cid_to_shard = rcu_dereference_all(scx_cid_to_shard);
1063 	ref->shard_first = cid_to_shard[base];
1064 	if (likely(nr_cids))
1065 		ref->shard_end = cid_to_shard[base + nr_cids - 1] + 1;
1066 	else
1067 		ref->shard_end = ref->shard_first;
1068 
1069 	return 0;
1070 }
1071 
1072 /**
1073  * scx_cmask_ref_init_kern - Bind a scx_cmask_ref to a kernel-owned cmask
1074  * @sch: scheduler the cmask belongs to
1075  * @m: kernel address of the target cmask, storage sized for @nr_cids at @base
1076  * @base: first cid of the active range
1077  * @nr_cids: active range length
1078  * @ref: output ref
1079  *
1080  * Like scx_cmask_ref_init() but the geometry is supplied by the caller, not
1081  * read from @m's header, so a concurrent BPF write to the header can't steer
1082  * later sizing or offsets. Rewrite the header from the trusted geometry and
1083  * bind @ref to it.
1084  */
1085 void scx_cmask_ref_init_kern(struct scx_sched *sch, struct scx_cmask *m,
1086 			     u32 base, u32 nr_cids, struct scx_cmask_ref *ref)
1087 {
1088 	s32 *cid_to_shard;
1089 
1090 	WRITE_ONCE(m->base, base);
1091 	WRITE_ONCE(m->nr_cids, nr_cids);
1092 	WRITE_ONCE(m->alloc_words, SCX_CMASK_NR_WORDS(nr_cids));
1093 
1094 	ref->sch = sch;
1095 	ref->src = m;
1096 	ref->base = base;
1097 	ref->nr_cids = nr_cids;
1098 
1099 	cid_to_shard = rcu_dereference_all(scx_cid_to_shard);
1100 	ref->shard_first = cid_to_shard[base];
1101 	if (likely(nr_cids))
1102 		ref->shard_end = cid_to_shard[base + nr_cids - 1] + 1;
1103 	else
1104 		ref->shard_end = ref->shard_first;
1105 }
1106 
1107 /**
1108  * scx_cmask_ref_shard - Read one shard from @ref into @out
1109  * @ref: validated ref
1110  * @shard_idx: target shard, in [@ref->shard_first, @ref->shard_end)
1111  * @out: output cmask whose @out->alloc_words must hold the shard
1112  *
1113  * Set @out to the intersection of @ref's range with @shard_idx's cid range,
1114  * with bits[] read from @ref->src via READ_ONCE. Empty intersection sets
1115  * @out->nr_cids to 0. scx_error()s on @ref's sched if @out can't hold the
1116  * shard.
1117  */
1118 void scx_cmask_ref_shard(const struct scx_cmask_ref *ref, s32 shard_idx,
1119 			 struct scx_cmask *out)
1120 {
1121 	const struct scx_cid_shard *shard =
1122 		&rcu_dereference_all(scx_cid_shard_ranges)[shard_idx];
1123 	u32 shard_base = shard->base_cid;
1124 	u32 shard_end = shard_base + shard->nr_cids;
1125 	u32 isect_base, isect_end, nr_words, src_off, wi;
1126 	u64 head_mask, tail_mask;
1127 
1128 	isect_base = max(ref->base, shard_base);
1129 	isect_end = min(ref->base + ref->nr_cids, shard_end);
1130 
1131 	if (isect_base >= isect_end) {
1132 		out->base = shard_base;
1133 		out->nr_cids = 0;
1134 		return;
1135 	}
1136 
1137 	nr_words = ((isect_end - 1) / 64) - (isect_base / 64) + 1;
1138 	if (nr_words > out->alloc_words) {
1139 		scx_error(ref->sch, "scx_cmask_ref_shard: out alloc_words=%u < %u for shard %d",
1140 			  out->alloc_words, nr_words, shard_idx);
1141 		out->base = shard_base;
1142 		out->nr_cids = 0;
1143 		return;
1144 	}
1145 
1146 	out->base = isect_base;
1147 	out->nr_cids = isect_end - isect_base;
1148 	src_off = (isect_base / 64) - (ref->base / 64);
1149 
1150 	for (wi = 0; wi < nr_words; wi++)
1151 		out->bits[wi] = READ_ONCE(ref->src->bits[src_off + wi]);
1152 
1153 	head_mask = GENMASK_U64(63, isect_base & 63);
1154 	out->bits[0] &= head_mask;
1155 	tail_mask = GENMASK_U64((isect_end - 1) & 63, 0);
1156 	out->bits[nr_words - 1] &= tail_mask;
1157 }
1158 
1159 /**
1160  * scx_cmask_ref_or - OR @src into the arena cmask referenced by @ref
1161  * @ref: validated ref
1162  * @src: stable kernel cmask
1163  *
1164  * Bits inside the intersection of @ref's snapshotted range with @src's range
1165  * are OR'd into @ref->src and bits outside are left unchanged. Stores on
1166  * @ref->src use WRITE_ONCE since BPF may read/write concurrently.
1167  */
1168 void scx_cmask_ref_or(const struct scx_cmask_ref *ref, const struct scx_cmask *src)
1169 {
1170 	cmask_walk_op2(ref->src->bits, ref->base, ref->nr_cids,
1171 		       src->bits, src->base, src->nr_cids, CMASK_OP2_REF_OR);
1172 }
1173 
1174 /**
1175  * scx_cmask_ref_copy - Copy @src into the arena cmask referenced by @ref
1176  * @ref: validated ref
1177  * @src: stable kernel cmask
1178  *
1179  * Bits inside the intersection of @ref's snapshotted range with @src's range
1180  * take @src's values and bits outside are left unchanged. Stores on @ref->src
1181  * use WRITE_ONCE since BPF may read/write concurrently.
1182  */
1183 void scx_cmask_ref_copy(const struct scx_cmask_ref *ref, const struct scx_cmask *src)
1184 {
1185 	cmask_walk_op2(ref->src->bits, ref->base, ref->nr_cids,
1186 		       src->bits, src->base, src->nr_cids, CMASK_OP2_REF_COPY);
1187 }
1188 
1189 /**
1190  * scx_cmask_ref_from_cpumask - Populate @ref's arena cmask from a cpumask
1191  * @ref: kern-bound ref, see scx_cmask_ref_init_kern()
1192  * @cpumask: cpus to translate into cids
1193  *
1194  * Write @ref's active range one word at a time, setting each cid's bit when
1195  * its cpu is in @cpumask. Offsets and length come from @ref's trusted geometry
1196  * and stores use WRITE_ONCE since BPF may read concurrently, so the arena
1197  * header is never read.
1198  */
1199 void scx_cmask_ref_from_cpumask(const struct scx_cmask_ref *ref,
1200 				const struct cpumask *cpumask)
1201 {
1202 	struct scx_cmask *m = ref->src;
1203 	u32 base = ref->base, nr_cids = ref->nr_cids;
1204 	u32 wi, nr_words;
1205 
1206 	if (!nr_cids)
1207 		return;
1208 
1209 	nr_words = (base + nr_cids - 1) / 64 - base / 64 + 1;
1210 	for (wi = 0; wi < nr_words; wi++) {
1211 		u32 word_first_cid = (base / 64 + wi) * 64;
1212 		u64 word = 0;
1213 		u32 bit;
1214 
1215 		for (bit = 0; bit < 64; bit++) {
1216 			u32 cid = word_first_cid + bit;
1217 
1218 			if (cid < base || cid >= base + nr_cids)
1219 				continue;
1220 			if (cpumask_test_cpu(__scx_cid_to_cpu(cid), cpumask))
1221 				word |= BIT_U64(bit);
1222 		}
1223 		WRITE_ONCE(m->bits[wi], word);
1224 	}
1225 }
1226 
1227 int scx_cid_kfunc_init(void)
1228 {
1229 	return register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_init_cids) ?:
1230 		register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_cid) ?:
1231 		register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &scx_kfunc_set_cid) ?:
1232 		register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &scx_kfunc_set_cid);
1233 }
1234