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 <tj@kernel.org> 32 */ 33 #ifndef _KERNEL_SCHED_EXT_CID_H 34 #define _KERNEL_SCHED_EXT_CID_H 35 36 #include "internal.h" 37 38 struct 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 */ 51 struct 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 62 extern u32 scx_nr_cid_shards; 63 extern s16 __rcu *scx_cid_to_cpu_tbl; 64 extern s16 __rcu *scx_cpu_to_cid_tbl; 65 extern s32 __rcu *scx_cid_to_shard; 66 extern s32 __rcu *scx_shard_node; 67 extern struct scx_cid_shard __rcu *scx_cid_shard_ranges; 68 extern struct scx_cid_topo __rcu *scx_cid_topo; 69 extern struct btf_id_set8 scx_kfunc_ids_init_cids; 70 extern struct btf_id_set8 scx_kfunc_ids_cid; 71 72 void scx_cmask_clear(struct scx_cmask *m); 73 void scx_cmask_fill(struct scx_cmask *m); 74 void scx_cmask_and(struct scx_cmask *dst, const struct scx_cmask *src); 75 void scx_cmask_or(struct scx_cmask *dst, const struct scx_cmask *src); 76 void scx_cmask_copy(struct scx_cmask *dst, const struct scx_cmask *src); 77 void scx_cmask_andnot(struct scx_cmask *dst, const struct scx_cmask *src); 78 bool scx_cmask_subset(const struct scx_cmask *sub, const struct scx_cmask *super); 79 bool scx_cmask_intersects(const struct scx_cmask *a, const struct scx_cmask *b); 80 bool scx_cmask_empty(const struct scx_cmask *m); 81 s32 scx_cid_init(struct scx_sched *sch); 82 void scx_cid_publish_tables(void); 83 void scx_cid_retire_tables(void); 84 int 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 */ 94 static 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 */ 109 static 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 */ 120 static 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 */ 137 static 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 */ 154 static 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 */ 166 static inline bool scx_is_cid_type(void) 167 { 168 return static_branch_unlikely(&__scx_is_cid_type); 169 } 170 171 static 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(). */ 177 static 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 */ 192 static 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 */ 212 static 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 */ 226 static 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 242 static 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 */ 257 static 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 */ 268 static 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 */ 299 static 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 306 static 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 313 int scx_cmask_ref_init(struct scx_sched *sch, const struct scx_cmask *src, 314 struct scx_cmask_ref *ref); 315 void scx_cmask_ref_init_kern(struct scx_sched *sch, struct scx_cmask *m, 316 u32 base, u32 nr_cids, struct scx_cmask_ref *ref); 317 void scx_cmask_ref_shard(const struct scx_cmask_ref *ref, s32 shard_idx, 318 struct scx_cmask *out); 319 void scx_cmask_ref_from_cpumask(const struct scx_cmask_ref *ref, 320 const struct cpumask *cpumask); 321 void scx_cmask_ref_or(const struct scx_cmask_ref *ref, const struct scx_cmask *src); 322 void scx_cmask_ref_copy(const struct scx_cmask_ref *ref, const struct scx_cmask *src); 323 324 #endif /* _KERNEL_SCHED_EXT_CID_H */ 325