xref: /netbsd-src/sys/kern/subr_kcpuset.c (revision 901e7e84758515fbf39dfc064cb0b45ab146d8b0) 
1 /*	$NetBSD: subr_kcpuset.c,v 1.15 2023/04/09 09:18:09 riastradh Exp $	*/
2 
3 /*-
4  * Copyright (c) 2011 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to The NetBSD Foundation
8  * by Mindaugas Rasiukevicius.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29  * POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 /*
33  * Kernel CPU set implementation.
34  *
35  * Interface can be used by kernel subsystems as a unified dynamic CPU
36  * bitset implementation handling many CPUs.  Facility also supports early
37  * use by MD code on boot, as it fixups bitsets on further boot.
38  *
39  * TODO:
40  * - Handle "reverse" bitset on fixup/grow.
41  */
42 
43 #include <sys/cdefs.h>
44 __KERNEL_RCSID(0, "$NetBSD: subr_kcpuset.c,v 1.15 2023/04/09 09:18:09 riastradh Exp $");
45 
46 #include <sys/param.h>
47 #include <sys/types.h>
48 
49 #include <sys/atomic.h>
50 #include <sys/sched.h>
51 #include <sys/kcpuset.h>
52 #include <sys/pool.h>
53 
54 /* Number of CPUs to support. */
55 #define	KC_MAXCPUS		roundup2(MAXCPUS, 32)
56 
57 /*
58  * Structure of dynamic CPU set in the kernel.
59  */
60 struct kcpuset {
61 	uint32_t		bits[0];
62 };
63 
64 typedef struct kcpuset_impl {
65 	/* Reference count. */
66 	u_int			kc_refcnt;
67 	/* Next to free, if non-NULL (used when multiple references). */
68 	struct kcpuset *	kc_next;
69 	/* Actual variable-sized field of bits. */
70 	struct kcpuset		kc_field;
71 } kcpuset_impl_t;
72 
73 #define	KC_BITS_OFF		(offsetof(struct kcpuset_impl, kc_field))
74 #define	KC_GETSTRUCT(b)		((kcpuset_impl_t *)((char *)(b) - KC_BITS_OFF))
75 #define	KC_GETCSTRUCT(b)	((const kcpuset_impl_t *)((const char *)(b) - KC_BITS_OFF))
76 
77 /* Sizes of a single bitset. */
78 #define	KC_SHIFT		5
79 #define	KC_MASK			31
80 
81 /* An array of noted early kcpuset creations and data. */
82 #define	KC_SAVE_NITEMS		8
83 
84 /* Structures for early boot mechanism (must be statically initialised). */
85 static kcpuset_t **		kc_noted_early[KC_SAVE_NITEMS];
86 static uint32_t			kc_bits_early[KC_SAVE_NITEMS];
87 static int			kc_last_idx = 0;
88 static bool			kc_initialised = false;
89 
90 #define	KC_BITSIZE_EARLY	sizeof(kc_bits_early[0])
91 #define	KC_NFIELDS_EARLY	1
92 
93 /*
94  * The size of whole bitset fields and amount of fields.
95  * The whole size must statically initialise for early case.
96  */
97 static size_t			kc_bitsize __read_mostly = KC_BITSIZE_EARLY;
98 static size_t			kc_nfields __read_mostly = KC_NFIELDS_EARLY;
99 
100 static pool_cache_t		kc_cache __read_mostly;
101 
102 static kcpuset_t *		kcpuset_create_raw(bool);
103 
104 /*
105  * kcpuset_sysinit: initialize the subsystem, transfer early boot cases
106  * to dynamically allocated sets.
107  */
108 void
109 kcpuset_sysinit(void)
110 {
111 	kcpuset_t *kc_dynamic[KC_SAVE_NITEMS], *kcp;
112 	int i, s;
113 
114 	/* Set a kcpuset_t sizes. */
115 	kc_nfields = (KC_MAXCPUS >> KC_SHIFT);
116 	kc_bitsize = sizeof(uint32_t) * kc_nfields;
117 	KASSERT(kc_nfields != 0);
118 	KASSERT(kc_bitsize != 0);
119 
120 	kc_cache = pool_cache_init(sizeof(kcpuset_impl_t) + kc_bitsize,
121 	    coherency_unit, 0, 0, "kcpuset", NULL, IPL_NONE, NULL, NULL, NULL);
122 
123 	/* First, pre-allocate kcpuset entries. */
124 	for (i = 0; i < kc_last_idx; i++) {
125 		kcp = kcpuset_create_raw(true);
126 		kc_dynamic[i] = kcp;
127 	}
128 
129 	/*
130 	 * Prepare to convert all early noted kcpuset uses to dynamic sets.
131 	 * All processors, except the one we are currently running (primary),
132 	 * must not be spinned yet.  Since MD facilities can use kcpuset,
133 	 * raise the IPL to high.
134 	 */
135 	KASSERT(mp_online == false);
136 
137 	s = splhigh();
138 	for (i = 0; i < kc_last_idx; i++) {
139 		/*
140 		 * Transfer the bits from early static storage to the kcpuset.
141 		 */
142 		KASSERT(kc_bitsize >= KC_BITSIZE_EARLY);
143 		memcpy(kc_dynamic[i], &kc_bits_early[i], KC_BITSIZE_EARLY);
144 
145 		/*
146 		 * Store the new pointer, pointing to the allocated kcpuset.
147 		 * Note: we are not in an interrupt context and it is the only
148 		 * CPU running - thus store is safe (e.g. no need for pointer
149 		 * variable to be volatile).
150 		 */
151 		*kc_noted_early[i] = kc_dynamic[i];
152 	}
153 	kc_initialised = true;
154 	kc_last_idx = 0;
155 	splx(s);
156 }
157 
158 /*
159  * kcpuset_early_ptr: note an early boot use by saving the pointer and
160  * returning a pointer to a static, temporary bit field.
161  */
162 static kcpuset_t *
163 kcpuset_early_ptr(kcpuset_t **kcptr)
164 {
165 	kcpuset_t *kcp;
166 	int s;
167 
168 	s = splhigh();
169 	if (kc_last_idx < KC_SAVE_NITEMS) {
170 		/*
171 		 * Save the pointer, return pointer to static early field.
172 		 * Need to zero it out.
173 		 */
174 		kc_noted_early[kc_last_idx] = kcptr;
175 		kcp = (kcpuset_t *)&kc_bits_early[kc_last_idx];
176 		kc_last_idx++;
177 		memset(kcp, 0, KC_BITSIZE_EARLY);
178 		KASSERT(kc_bitsize == KC_BITSIZE_EARLY);
179 	} else {
180 		panic("kcpuset(9): all early-use entries exhausted; "
181 		    "increase KC_SAVE_NITEMS\n");
182 	}
183 	splx(s);
184 
185 	return kcp;
186 }
187 
188 /*
189  * Routines to create or destroy the CPU set.
190  * Early boot case is handled.
191  */
192 
193 static kcpuset_t *
194 kcpuset_create_raw(bool zero)
195 {
196 	kcpuset_impl_t *kc;
197 
198 	kc = pool_cache_get(kc_cache, PR_WAITOK);
199 	kc->kc_refcnt = 1;
200 	kc->kc_next = NULL;
201 
202 	if (zero) {
203 		memset(&kc->kc_field, 0, kc_bitsize);
204 	}
205 
206 	/* Note: return pointer to the actual field of bits. */
207 	KASSERT((uint8_t *)kc + KC_BITS_OFF == (uint8_t *)&kc->kc_field);
208 	return &kc->kc_field;
209 }
210 
211 void
212 kcpuset_create(kcpuset_t **retkcp, bool zero)
213 {
214 	if (__predict_false(!kc_initialised)) {
215 		/* Early boot use - special case. */
216 		*retkcp = kcpuset_early_ptr(retkcp);
217 		return;
218 	}
219 	*retkcp = kcpuset_create_raw(zero);
220 }
221 
222 void
223 kcpuset_clone(kcpuset_t **retkcp, const kcpuset_t *kcp)
224 {
225 	kcpuset_create(retkcp, false);
226 	memcpy(*retkcp, kcp, kc_bitsize);
227 }
228 
229 void
230 kcpuset_destroy(kcpuset_t *kcp)
231 {
232 	kcpuset_impl_t *kc;
233 
234 	KASSERT(kc_initialised);
235 	KASSERT(kcp != NULL);
236 
237 	do {
238 		kc = KC_GETSTRUCT(kcp);
239 		kcp = kc->kc_next;
240 		pool_cache_put(kc_cache, kc);
241 	} while (kcp);
242 }
243 
244 /*
245  * Routines to reference/unreference the CPU set.
246  * Note: early boot case is not supported by these routines.
247  */
248 
249 void
250 kcpuset_use(kcpuset_t *kcp)
251 {
252 	kcpuset_impl_t *kc = KC_GETSTRUCT(kcp);
253 
254 	KASSERT(kc_initialised);
255 	atomic_inc_uint(&kc->kc_refcnt);
256 }
257 
258 void
259 kcpuset_unuse(kcpuset_t *kcp, kcpuset_t **lst)
260 {
261 	kcpuset_impl_t *kc = KC_GETSTRUCT(kcp);
262 
263 	KASSERT(kc_initialised);
264 	KASSERT(kc->kc_refcnt > 0);
265 
266 	membar_release();
267 	if (atomic_dec_uint_nv(&kc->kc_refcnt) != 0) {
268 		return;
269 	}
270 	membar_acquire();
271 	KASSERT(kc->kc_next == NULL);
272 	if (lst == NULL) {
273 		kcpuset_destroy(kcp);
274 		return;
275 	}
276 	kc->kc_next = *lst;
277 	*lst = kcp;
278 }
279 
280 /*
281  * Routines to transfer the CPU set from / to userspace.
282  * Note: early boot case is not supported by these routines.
283  */
284 
285 int
286 kcpuset_copyin(const cpuset_t *ucp, kcpuset_t *kcp, size_t len)
287 {
288 	kcpuset_impl_t *kc __diagused = KC_GETSTRUCT(kcp);
289 
290 	KASSERT(kc_initialised);
291 	KASSERT(kc->kc_refcnt > 0);
292 	KASSERT(kc->kc_next == NULL);
293 
294 	if (len > kc_bitsize) { /* XXX */
295 		return EINVAL;
296 	}
297 	return copyin(ucp, kcp, len);
298 }
299 
300 int
301 kcpuset_copyout(kcpuset_t *kcp, cpuset_t *ucp, size_t len)
302 {
303 	kcpuset_impl_t *kc __diagused = KC_GETSTRUCT(kcp);
304 
305 	KASSERT(kc_initialised);
306 	KASSERT(kc->kc_refcnt > 0);
307 	KASSERT(kc->kc_next == NULL);
308 
309 	if (len > kc_bitsize) { /* XXX */
310 		return EINVAL;
311 	}
312 	return copyout(kcp, ucp, len);
313 }
314 
315 void
316 kcpuset_export_u32(const kcpuset_t *kcp, uint32_t *bitfield, size_t len)
317 {
318 	size_t rlen = MIN(kc_bitsize, len);
319 
320 	KASSERT(kcp != NULL);
321 	memcpy(bitfield, kcp->bits, rlen);
322 }
323 
324 /*
325  * Routines to change bit field - zero, fill, copy, set, unset, etc.
326  */
327 
328 void
329 kcpuset_zero(kcpuset_t *kcp)
330 {
331 
332 	KASSERT(!kc_initialised || KC_GETSTRUCT(kcp)->kc_refcnt > 0);
333 	KASSERT(!kc_initialised || KC_GETSTRUCT(kcp)->kc_next == NULL);
334 	memset(kcp, 0, kc_bitsize);
335 }
336 
337 void
338 kcpuset_fill(kcpuset_t *kcp)
339 {
340 
341 	KASSERT(!kc_initialised || KC_GETSTRUCT(kcp)->kc_refcnt > 0);
342 	KASSERT(!kc_initialised || KC_GETSTRUCT(kcp)->kc_next == NULL);
343 	memset(kcp, ~0, kc_bitsize);
344 }
345 
346 void
347 kcpuset_copy(kcpuset_t *dkcp, const kcpuset_t *skcp)
348 {
349 
350 	KASSERT(!kc_initialised || KC_GETSTRUCT(dkcp)->kc_refcnt > 0);
351 	KASSERT(!kc_initialised || KC_GETSTRUCT(dkcp)->kc_next == NULL);
352 	memcpy(dkcp, skcp, kc_bitsize);
353 }
354 
355 void
356 kcpuset_set(kcpuset_t *kcp, cpuid_t i)
357 {
358 	const size_t j = i >> KC_SHIFT;
359 
360 	KASSERT(!kc_initialised || KC_GETSTRUCT(kcp)->kc_next == NULL);
361 	KASSERT(j < kc_nfields);
362 
363 	kcp->bits[j] |= __BIT(i & KC_MASK);
364 }
365 
366 void
367 kcpuset_clear(kcpuset_t *kcp, cpuid_t i)
368 {
369 	const size_t j = i >> KC_SHIFT;
370 
371 	KASSERT(!kc_initialised || KC_GETCSTRUCT(kcp)->kc_next == NULL);
372 	KASSERT(j < kc_nfields);
373 
374 	kcp->bits[j] &= ~(__BIT(i & KC_MASK));
375 }
376 
377 bool
378 kcpuset_isset(const kcpuset_t *kcp, cpuid_t i)
379 {
380 	const size_t j = i >> KC_SHIFT;
381 
382 	KASSERT(kcp != NULL);
383 	KASSERT(!kc_initialised || KC_GETCSTRUCT(kcp)->kc_refcnt > 0);
384 	KASSERT(!kc_initialised || KC_GETCSTRUCT(kcp)->kc_next == NULL);
385 	KASSERT(j < kc_nfields);
386 
387 	return ((__BIT(i & KC_MASK)) & kcp->bits[j]) != 0;
388 }
389 
390 bool
391 kcpuset_isotherset(const kcpuset_t *kcp, cpuid_t i)
392 {
393 	const size_t j2 = i >> KC_SHIFT;
394 	const uint32_t mask = ~(__BIT(i & KC_MASK));
395 
396 	for (size_t j = 0; j < kc_nfields; j++) {
397 		const uint32_t bits = kcp->bits[j];
398 		if (bits && (j != j2 || (bits & mask) != 0)) {
399 			return true;
400 		}
401 	}
402 	return false;
403 }
404 
405 bool
406 kcpuset_iszero(const kcpuset_t *kcp)
407 {
408 
409 	for (size_t j = 0; j < kc_nfields; j++) {
410 		if (kcp->bits[j] != 0) {
411 			return false;
412 		}
413 	}
414 	return true;
415 }
416 
417 bool
418 kcpuset_match(const kcpuset_t *kcp1, const kcpuset_t *kcp2)
419 {
420 
421 	return memcmp(kcp1, kcp2, kc_bitsize) == 0;
422 }
423 
424 bool
425 kcpuset_intersecting_p(const kcpuset_t *kcp1, const kcpuset_t *kcp2)
426 {
427 
428 	for (size_t j = 0; j < kc_nfields; j++) {
429 		if (kcp1->bits[j] & kcp2->bits[j])
430 			return true;
431 	}
432 	return false;
433 }
434 
435 cpuid_t
436 kcpuset_ffs(const kcpuset_t *kcp)
437 {
438 
439 	for (size_t j = 0; j < kc_nfields; j++) {
440 		if (kcp->bits[j])
441 			return 32 * j + ffs(kcp->bits[j]);
442 	}
443 	return 0;
444 }
445 
446 cpuid_t
447 kcpuset_ffs_intersecting(const kcpuset_t *kcp1, const kcpuset_t *kcp2)
448 {
449 
450 	for (size_t j = 0; j < kc_nfields; j++) {
451 		uint32_t bits = kcp1->bits[j] & kcp2->bits[j];
452 		if (bits)
453 			return 32 * j + ffs(bits);
454 	}
455 	return 0;
456 }
457 
458 void
459 kcpuset_merge(kcpuset_t *kcp1, const kcpuset_t *kcp2)
460 {
461 
462 	for (size_t j = 0; j < kc_nfields; j++) {
463 		kcp1->bits[j] |= kcp2->bits[j];
464 	}
465 }
466 
467 void
468 kcpuset_intersect(kcpuset_t *kcp1, const kcpuset_t *kcp2)
469 {
470 
471 	for (size_t j = 0; j < kc_nfields; j++) {
472 		kcp1->bits[j] &= kcp2->bits[j];
473 	}
474 }
475 
476 void
477 kcpuset_remove(kcpuset_t *kcp1, const kcpuset_t *kcp2)
478 {
479 
480 	for (size_t j = 0; j < kc_nfields; j++) {
481 		kcp1->bits[j] &= ~kcp2->bits[j];
482 	}
483 }
484 
485 int
486 kcpuset_countset(const kcpuset_t *kcp)
487 {
488 	int count = 0;
489 
490 	for (size_t j = 0; j < kc_nfields; j++) {
491 		count += popcount32(kcp->bits[j]);
492 	}
493 	return count;
494 }
495 
496 /*
497  * Routines to set/clear the flags atomically.
498  */
499 
500 void
501 kcpuset_atomic_set(kcpuset_t *kcp, cpuid_t i)
502 {
503 	const size_t j = i >> KC_SHIFT;
504 
505 	KASSERT(j < kc_nfields);
506 	atomic_or_32(&kcp->bits[j], __BIT(i & KC_MASK));
507 }
508 
509 void
510 kcpuset_atomic_clear(kcpuset_t *kcp, cpuid_t i)
511 {
512 	const size_t j = i >> KC_SHIFT;
513 
514 	KASSERT(j < kc_nfields);
515 	atomic_and_32(&kcp->bits[j], ~(__BIT(i & KC_MASK)));
516 }
517 
518 void
519 kcpuset_atomicly_intersect(kcpuset_t *kcp1, const kcpuset_t *kcp2)
520 {
521 
522 	for (size_t j = 0; j < kc_nfields; j++) {
523 		if (kcp2->bits[j])
524 			atomic_and_32(&kcp1->bits[j], kcp2->bits[j]);
525 	}
526 }
527 
528 void
529 kcpuset_atomicly_merge(kcpuset_t *kcp1, const kcpuset_t *kcp2)
530 {
531 
532 	for (size_t j = 0; j < kc_nfields; j++) {
533 		if (kcp2->bits[j])
534 			atomic_or_32(&kcp1->bits[j], kcp2->bits[j]);
535 	}
536 }
537 
538 void
539 kcpuset_atomicly_remove(kcpuset_t *kcp1, const kcpuset_t *kcp2)
540 {
541 
542 	for (size_t j = 0; j < kc_nfields; j++) {
543 		if (kcp2->bits[j])
544 			atomic_and_32(&kcp1->bits[j], ~kcp2->bits[j]);
545 	}
546 }
547