Index: head/share/man/man9/bitset.9 =================================================================== --- head/share/man/man9/bitset.9 (revision 365974) +++ head/share/man/man9/bitset.9 (revision 365975) @@ -1,540 +1,540 @@ .\" Copyright (c) 2015 Conrad Meyer .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' .\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE .\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE .\" POSSIBILITY OF SUCH DAMAGE. .\" .\" $FreeBSD$ .\" .Dd August 25, 2020 .Dt BITSET 9 .Os .Sh NAME .Nm bitset(9) \(em .Nm BITSET_DEFINE , .Nm BITSET_T_INITIALIZER , .Nm BITSET_FSET , .Nm BIT_CLR , .Nm BIT_COPY , .Nm BIT_ISSET , .Nm BIT_SET , .Nm BIT_ZERO , .Nm BIT_FILL , .Nm BIT_SETOF , .Nm BIT_EMPTY , .Nm BIT_ISFULLSET , .Nm BIT_FFS , .Nm BIT_FFS_AT , .Nm BIT_FLS , .Nm BIT_COUNT , .Nm BIT_SUBSET , .Nm BIT_OVERLAP , .Nm BIT_CMP , .Nm BIT_OR , .Nm BIT_OR2 , .Nm BIT_AND , .Nm BIT_AND2 , .Nm BIT_ANDNOT , .Nm BIT_ANDNOT2 , .Nm BIT_XOR , .Nm BIT_XOR2 , .Nm BIT_CLR_ATOMIC , .Nm BIT_SET_ATOMIC , .Nm BIT_SET_ATOMIC_ACQ , .Nm BIT_AND_ATOMIC , .Nm BIT_OR_ATOMIC , .Nm BIT_COPY_STORE_REL .Nd bitset manipulation macros .Sh SYNOPSIS .In sys/_bitset.h .In sys/bitset.h .\" .Fn BITSET_DEFINE "STRUCTNAME" "const SETSIZE" .Fn BITSET_T_INITIALIZER "ARRAY_CONTENTS" .Fn BITSET_FSET "N_WORDS" .\" .Fn BIT_CLR "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Fn BIT_COPY "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to" .Ft bool .Fn BIT_ISSET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Fn BIT_SET "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Fn BIT_ZERO "const SETSIZE" "struct STRUCTNAME *bitset" .Fn BIT_FILL "const SETSIZE" "struct STRUCTNAME *bitset" .Fn BIT_SETOF "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Ft bool .Fn BIT_EMPTY "const SETSIZE" "struct STRUCTNAME *bitset" .Ft bool .Fn BIT_ISFULLSET "const SETSIZE" "struct STRUCTNAME *bitset" -.Ft int +.Ft long .Fn BIT_FFS "const SETSIZE" "struct STRUCTNAME *bitset" -.Ft int -.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "int start" -.Ft int +.Ft long +.Fn BIT_FFS_AT "const SETSIZE" "struct STRUCTNAME *bitset" "long start" +.Ft long .Fn BIT_FLS "const SETSIZE" "struct STRUCTNAME *bitset" -.Ft int +.Ft long .Fn BIT_COUNT "const SETSIZE" "struct STRUCTNAME *bitset" .\" .Ft bool .Fo BIT_SUBSET .Fa "const SETSIZE" "struct STRUCTNAME *haystack" "struct STRUCTNAME *needle" .Fc .Ft bool .Fo BIT_OVERLAP .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2" .Fc .Ft bool .Fo BIT_CMP .Fa "const SETSIZE" "struct STRUCTNAME *bitset1" "struct STRUCTNAME *bitset2" .Fc .Fn BIT_OR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fo BIT_OR2 .Fa "const SETSIZE" .Fa "struct STRUCTNAME *dst" .Fa "struct STRUCTNAME *src1" .Fa "struct STRUCTNAME *src2" .Fc .Fn BIT_AND "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fo BIT_AND2 .Fa "const SETSIZE" .Fa "struct STRUCTNAME *dst" .Fa "struct STRUCTNAME *src1" .Fa "struct STRUCTNAME *src2" .Fc .Fn BIT_ANDNOT "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fo BIT_ANDNOT2 .Fa "const SETSIZE" .Fa "struct STRUCTNAME *dst" .Fa "struct STRUCTNAME *src1" .Fa "struct STRUCTNAME *src2" .Fc .Fn BIT_XOR "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fo BIT_XOR2 .Fa "const SETSIZE" .Fa "struct STRUCTNAME *dst" .Fa "struct STRUCTNAME *src1" .Fa "struct STRUCTNAME *src2" .Fc .\" .Fn BIT_CLR_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Fn BIT_SET_ATOMIC "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .Fn BIT_SET_ATOMIC_ACQ "const SETSIZE" "size_t bit" "struct STRUCTNAME *bitset" .\" .Fo BIT_AND_ATOMIC .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fc .Fo BIT_OR_ATOMIC .Fa "const SETSIZE" "struct STRUCTNAME *dst" "struct STRUCTNAME *src" .Fc .Fo BIT_COPY_STORE_REL .Fa "const SETSIZE" "struct STRUCTNAME *from" "struct STRUCTNAME *to" .Fc .Sh DESCRIPTION The .Nm family of macros provide a flexible and efficient bitset implementation if the maximum size of the set is known at compilation. Throughout this manual page, the name .Fa SETSIZE refers to the size of the bitset in bits. Individual bits in bitsets are referenced with indices zero through .Fa SETSIZE - 1 . One example use of .In sys/bitset.h is .In sys/cpuset.h . .Pp The .Fn BITSET_DEFINE macro defines a bitset struct .Fa STRUCTNAME with room to represent .Fa SETSIZE bits. .Pp The .Fn BITSET_T_INITIALIZER macro allows one to initialize a bitset struct with a compile time literal value. .Pp The .Fn BITSET_FSET macro generates a compile time literal, usable by .Fn BITSET_T_INITIALIZER , representing a full bitset (all bits set). For examples of .Fn BITSET_T_INITIALIZER and .Fn BITSET_FSET usage, see the .Sx BITSET_T_INITIALIZER EXAMPLE section. The .Fa N_WORDS parameter to .Fn BITSET_FSET should be: .Bd -literal -offset indent __bitset_words(SETSIZE) .Ed .Pp The .Fn BIT_CLR macro clears bit .Fa bit in the bitset pointed to by .Fa bitset . The .Fn BIT_CLR_ATOMIC macro is identical, but the bit is cleared atomically. .Pp The .Fn BIT_COPY macro copies the contents of the bitset .Fa from to the bitset .Fa to . .Fn BIT_COPY_STORE_REL is similar, but copies component machine words from .Fa from and writes them to .Fa to with atomic store with release semantics. (That is, if .Fa to is composed of multiple machine words, .Fn BIT_COPY_STORE_REL performs multiple individually atomic operations.) .Pp The .Fn BIT_SET macro sets bit .Fa bit in the bitset pointed to by .Fa bitset . The .Fn BIT_SET_ATOMIC macro is identical, but the bit is set atomically. The .Fn BIT_SET_ATOMIC_ACQ macro sets the bit with acquire semantics. .Pp The .Fn BIT_ZERO macro clears all bits in .Fa bitset . .Pp The .Fn BIT_FILL macro sets all bits in .Fa bitset . .Pp The .Fn BIT_SETOF macro clears all bits in .Fa bitset before setting only bit .Fa bit . .Pp The .Fn BIT_EMPTY macro returns .Dv true if .Fa bitset is empty. .Pp The .Fn BIT_ISFULLSET macro returns .Dv true if .Fa bitset is full (all bits set). .Pp The .Fn BIT_FFS macro returns the 1-index of the first (lowest) set bit in .Fa bitset , or zero if .Fa bitset is empty. Like with .Xr ffs 3 , to use the non-zero result of .Fn BIT_FFS as a .Fa bit index parameter to any other .Nm macro, you must subtract one from the result. .Pp The .Fn BIT_FFS_AT macro returns the 1-index of the first (lowest) set bit in .Fa bitset , which is greater than the given 1-indexed .Fa start , or zero if no bits in .Fa bitset greater than .Fa start are set. .Pp The .Fn BIT_FLS macro returns the 1-index of the last (highest) set bit in .Fa bitset , or zero if .Fa bitset is empty. Like with .Xr fls 3 , to use the non-zero result of .Fn BIT_FLS as a .Fa bit index parameter to any other .Nm macro, you must subtract one from the result. .Pp The .Fn BIT_COUNT macro returns the total number of set bits in .Fa bitset . .Pp The .Fn BIT_SUBSET macro returns .Dv true if .Fa needle is a subset of .Fa haystack . .Pp The .Fn BIT_OVERLAP macro returns .Dv true if .Fa bitset1 and .Fa bitset2 have any common bits. (That is, if .Fa bitset1 AND .Fa bitset2 is not the empty set.) .Pp The .Fn BIT_CMP macro returns .Dv true if .Fa bitset1 is NOT equal to .Fa bitset2 . .Pp The .Fn BIT_OR macro sets bits present in .Fa src in .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst |= .Fa src . ) .Fn BIT_OR_ATOMIC is similar, but sets bits in the component machine words in .Fa dst atomically. (That is, if .Fa dst is composed of multiple machine words, .Fn BIT_OR_ATOMIC performs multiple individually atomic operations.) .Pp The .Fn BIT_OR2 macro computes .Fa src1 bitwise or .Fa src2 and assigns the result to .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst = .Fa src1 | .Fa src2 . ) .Pp The .Fn BIT_AND macro clears bits absent from .Fa src from .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst &= .Fa src . ) .Fn BIT_AND_ATOMIC is similar, with the same atomic semantics as .Fn BIT_OR_ATOMIC . .Pp The .Fn BIT_AND2 macro computes .Fa src1 bitwise and .Fa src2 and assigns the result to .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst = .Fa src1 & .Fa src2 . ) .Pp The .Fn BIT_ANDNOT macro clears bits set in .Fa src from .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst &= .Fa ~ src . ) .Pp The .Fn BIT_ANDNOT2 macro computes .Fa src1 bitwise and not .Fa src2 and assigns the result to .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst = .Fa src1 & ~ .Fa src2 . ) .Pp The .Fn BIT_XOR macro toggles bits set in .Fa src in .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst ^= .Fa src . ) .Pp The .Fn BIT_XOR2 macro computes .Fa src1 bitwise exclusive or .Fa src2 and assigns the result to .Fa dst . (It is the .Nm equivalent of the scalar: .Fa dst = .Fa src1 ^ .Fa src2 . ) .Sh BITSET_T_INITIALIZER EXAMPLE .Bd -literal BITSET_DEFINE(_myset, MYSETSIZE); struct _myset myset; /* Initialize myset to filled (all bits set) */ myset = BITSET_T_INITIALIZER(BITSET_FSET(__bitset_words(MYSETSIZE))); /* Initialize myset to only the lowest bit set */ myset = BITSET_T_INITIALIZER(0x1); .Ed .Sh SEE ALSO .Xr bitstring 3 , .Xr cpuset 9 .Sh HISTORY The .Nm macros first appeared in .Fx 10.0 in January 2014. They were MFCed to .Fx 9.3 , released in July 2014. .Pp This manual page first appeared in .Fx 11.0 . .Sh AUTHORS .An -nosplit The .Nm macros were generalized and pulled out of .In sys/cpuset.h as .In sys/_bitset.h and .In sys/bitset.h by .An Attilio Rao Aq Mt attilio@FreeBSD.org . This manual page was written by .An Conrad Meyer Aq Mt cem@FreeBSD.org . .Sh CAVEATS The .Fa SETSIZE argument to all of these macros must match the value given to .Fn BITSET_DEFINE . .Pp Unlike every other reference to individual set members, which are zero-indexed, .Fn BIT_FFS , .Fn BIT_FFS_AT and .Fn BIT_FLS return a one-indexed result (or zero if the set is empty). Index: head/sys/sys/bitset.h =================================================================== --- head/sys/sys/bitset.h (revision 365974) +++ head/sys/sys/bitset.h (revision 365975) @@ -1,274 +1,273 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2008, Jeffrey Roberson * All rights reserved. * * Copyright (c) 2008 Nokia Corporation * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _SYS_BITSET_H_ #define _SYS_BITSET_H_ /* * Whether expr is both constant and true. Result is itself constant. * Used to enable optimizations for sets with a known small size. */ #define __constexpr_cond(expr) (__builtin_constant_p((expr)) && (expr)) #define __bitset_mask(_s, n) \ (1UL << (__constexpr_cond(__bitset_words((_s)) == 1) ? \ (__size_t)(n) : ((n) % _BITSET_BITS))) #define __bitset_word(_s, n) \ (__constexpr_cond(__bitset_words((_s)) == 1) ? \ 0 : ((n) / _BITSET_BITS)) #define BIT_CLR(_s, n, p) \ ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n))) #define BIT_COPY(_s, f, t) (void)(*(t) = *(f)) #define BIT_ISSET(_s, n, p) \ ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0)) #define BIT_SET(_s, n, p) \ ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n))) #define BIT_ZERO(_s, p) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (p)->__bits[__i] = 0L; \ } while (0) #define BIT_FILL(_s, p) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (p)->__bits[__i] = -1L; \ } while (0) #define BIT_SETOF(_s, n, p) do { \ BIT_ZERO(_s, p); \ (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \ } while (0) /* Is p empty. */ #define BIT_EMPTY(_s, p) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if ((p)->__bits[__i]) \ break; \ __i == __bitset_words((_s)); \ }) /* Is p full set. */ #define BIT_ISFULLSET(_s, p) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if ((p)->__bits[__i] != (long)-1) \ break; \ __i == __bitset_words((_s)); \ }) /* Is c a subset of p. */ #define BIT_SUBSET(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] & \ (p)->__bits[__i]) != \ (c)->__bits[__i]) \ break; \ __i == __bitset_words((_s)); \ }) /* Are there any common bits between b & c? */ #define BIT_OVERLAP(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] & \ (p)->__bits[__i]) != 0) \ break; \ __i != __bitset_words((_s)); \ }) /* Compare two sets, returns 0 if equal 1 otherwise. */ #define BIT_CMP(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] != \ (p)->__bits[__i])) \ break; \ __i != __bitset_words((_s)); \ }) #define BIT_OR(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] |= (s)->__bits[__i]; \ } while (0) #define BIT_OR2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\ } while (0) #define BIT_AND(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] &= (s)->__bits[__i]; \ } while (0) #define BIT_AND2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\ } while (0) #define BIT_ANDNOT(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] &= ~(s)->__bits[__i]; \ } while (0) #define BIT_ANDNOT2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\ } while (0) #define BIT_XOR(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] ^= (s)->__bits[__i]; \ } while (0) #define BIT_XOR2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\ } while (0) #define BIT_CLR_ATOMIC(_s, n, p) \ atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) #define BIT_SET_ATOMIC(_s, n, p) \ atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) #define BIT_SET_ATOMIC_ACQ(_s, n, p) \ atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) /* Convenience functions catering special cases. */ #define BIT_AND_ATOMIC(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_clear_long(&(d)->__bits[__i], \ ~(s)->__bits[__i]); \ } while (0) #define BIT_OR_ATOMIC(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_set_long(&(d)->__bits[__i], \ (s)->__bits[__i]); \ } while (0) #define BIT_COPY_STORE_REL(_s, f, t) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_store_rel_long(&(t)->__bits[__i], \ (f)->__bits[__i]); \ } while (0) /* * Note that `start` and the returned value from BIT_FFS_AT are * 1-based bit indices. */ #define BIT_FFS_AT(_s, p, start) __extension__ ({ \ __size_t __i; \ - long __mask; \ - int __bit; \ + long __bit, __mask; \ \ __mask = ~0UL << ((start) % _BITSET_BITS); \ __bit = 0; \ for (__i = __bitset_word((_s), (start)); \ __i < __bitset_words((_s)); \ __i++) { \ if (((p)->__bits[__i] & __mask) != 0) { \ __bit = ffsl((p)->__bits[__i] & __mask); \ __bit += __i * _BITSET_BITS; \ break; \ } \ __mask = ~0UL; \ } \ __bit; \ }) #define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 0) #define BIT_FLS(_s, p) __extension__ ({ \ __size_t __i; \ - int __bit; \ + long __bit; \ \ __bit = 0; \ for (__i = __bitset_words((_s)); __i > 0; __i--) { \ if ((p)->__bits[__i - 1] != 0) { \ __bit = flsl((p)->__bits[__i - 1]); \ __bit += (__i - 1) * _BITSET_BITS; \ break; \ } \ } \ __bit; \ }) #define BIT_COUNT(_s, p) __extension__ ({ \ __size_t __i; \ - int __count; \ + long __count; \ \ __count = 0; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ __count += __bitcountl((p)->__bits[__i]); \ __count; \ }) #define BITSET_T_INITIALIZER(x) \ { .__bits = { x } } #define BITSET_FSET(n) \ [ 0 ... ((n) - 1) ] = (-1L) #define BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long)) /* * Dynamically allocate a bitset. */ #define BITSET_ALLOC(_s, mt, mf) malloc(BITSET_SIZE((_s)), mt, (mf)) #endif /* !_SYS_BITSET_H_ */ Index: head/sys/sys/cpuset.h =================================================================== --- head/sys/sys/cpuset.h (revision 365974) +++ head/sys/sys/cpuset.h (revision 365975) @@ -1,159 +1,159 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2008, Jeffrey Roberson * All rights reserved. * * Copyright (c) 2008 Nokia Corporation * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _SYS_CPUSET_H_ #define _SYS_CPUSET_H_ #include #include #define _NCPUBITS _BITSET_BITS #define _NCPUWORDS __bitset_words(CPU_SETSIZE) #define CPUSETBUFSIZ ((2 + sizeof(long) * 2) * _NCPUWORDS) #define CPU_CLR(n, p) BIT_CLR(CPU_SETSIZE, n, p) #define CPU_COPY(f, t) BIT_COPY(CPU_SETSIZE, f, t) #define CPU_ISSET(n, p) BIT_ISSET(CPU_SETSIZE, n, p) #define CPU_SET(n, p) BIT_SET(CPU_SETSIZE, n, p) #define CPU_ZERO(p) BIT_ZERO(CPU_SETSIZE, p) #define CPU_FILL(p) BIT_FILL(CPU_SETSIZE, p) #define CPU_SETOF(n, p) BIT_SETOF(CPU_SETSIZE, n, p) #define CPU_EMPTY(p) BIT_EMPTY(CPU_SETSIZE, p) #define CPU_ISFULLSET(p) BIT_ISFULLSET(CPU_SETSIZE, p) #define CPU_SUBSET(p, c) BIT_SUBSET(CPU_SETSIZE, p, c) #define CPU_OVERLAP(p, c) BIT_OVERLAP(CPU_SETSIZE, p, c) #define CPU_CMP(p, c) BIT_CMP(CPU_SETSIZE, p, c) #define CPU_OR(d, s) BIT_OR(CPU_SETSIZE, d, s) #define CPU_AND(d, s) BIT_AND(CPU_SETSIZE, d, s) #define CPU_ANDNOT(d, s) BIT_ANDNOT(CPU_SETSIZE, d, s) #define CPU_CLR_ATOMIC(n, p) BIT_CLR_ATOMIC(CPU_SETSIZE, n, p) #define CPU_SET_ATOMIC(n, p) BIT_SET_ATOMIC(CPU_SETSIZE, n, p) #define CPU_SET_ATOMIC_ACQ(n, p) BIT_SET_ATOMIC_ACQ(CPU_SETSIZE, n, p) #define CPU_AND_ATOMIC(n, p) BIT_AND_ATOMIC(CPU_SETSIZE, n, p) #define CPU_OR_ATOMIC(d, s) BIT_OR_ATOMIC(CPU_SETSIZE, d, s) #define CPU_COPY_STORE_REL(f, t) BIT_COPY_STORE_REL(CPU_SETSIZE, f, t) #define CPU_FFS(p) BIT_FFS(CPU_SETSIZE, p) -#define CPU_COUNT(p) BIT_COUNT(CPU_SETSIZE, p) +#define CPU_COUNT(p) ((int)BIT_COUNT(CPU_SETSIZE, p)) #define CPUSET_FSET BITSET_FSET(_NCPUWORDS) #define CPUSET_T_INITIALIZER BITSET_T_INITIALIZER /* * Valid cpulevel_t values. */ #define CPU_LEVEL_ROOT 1 /* All system cpus. */ #define CPU_LEVEL_CPUSET 2 /* Available cpus for which. */ #define CPU_LEVEL_WHICH 3 /* Actual mask/id for which. */ /* * Valid cpuwhich_t values. */ #define CPU_WHICH_TID 1 /* Specifies a thread id. */ #define CPU_WHICH_PID 2 /* Specifies a process id. */ #define CPU_WHICH_CPUSET 3 /* Specifies a set id. */ #define CPU_WHICH_IRQ 4 /* Specifies an irq #. */ #define CPU_WHICH_JAIL 5 /* Specifies a jail id. */ #define CPU_WHICH_DOMAIN 6 /* Specifies a NUMA domain id. */ #define CPU_WHICH_INTRHANDLER 7 /* Specifies an irq # (not ithread). */ #define CPU_WHICH_ITHREAD 8 /* Specifies an irq's ithread. */ /* * Reserved cpuset identifiers. */ #define CPUSET_INVALID -1 #define CPUSET_DEFAULT 0 #ifdef _KERNEL #include LIST_HEAD(setlist, cpuset); /* * cpusets encapsulate cpu binding information for one or more threads. * * a - Accessed with atomics. * s - Set at creation, never modified. Only a ref required to read. * c - Locked internally by a cpuset lock. * * The bitmask is only modified while holding the cpuset lock. It may be * read while only a reference is held but the consumer must be prepared * to deal with inconsistent results. */ struct cpuset { cpuset_t cs_mask; /* bitmask of valid cpus. */ struct domainset *cs_domain; /* (c) NUMA policy. */ volatile u_int cs_ref; /* (a) Reference count. */ int cs_flags; /* (s) Flags from below. */ cpusetid_t cs_id; /* (s) Id or INVALID. */ struct cpuset *cs_parent; /* (s) Pointer to our parent. */ LIST_ENTRY(cpuset) cs_link; /* (c) All identified sets. */ LIST_ENTRY(cpuset) cs_siblings; /* (c) Sibling set link. */ struct setlist cs_children; /* (c) List of children. */ }; #define CPU_SET_ROOT 0x0001 /* Set is a root set. */ #define CPU_SET_RDONLY 0x0002 /* No modification allowed. */ extern cpuset_t *cpuset_root; struct prison; struct proc; struct thread; struct cpuset *cpuset_thread0(void); struct cpuset *cpuset_ref(struct cpuset *); void cpuset_rel(struct cpuset *); int cpuset_setthread(lwpid_t id, cpuset_t *); int cpuset_setithread(lwpid_t id, int cpu); int cpuset_create_root(struct prison *, struct cpuset **); int cpuset_setproc_update_set(struct proc *, struct cpuset *); int cpuset_which(cpuwhich_t, id_t, struct proc **, struct thread **, struct cpuset **); void cpuset_kernthread(struct thread *); char *cpusetobj_strprint(char *, const cpuset_t *); int cpusetobj_strscan(cpuset_t *, const char *); #ifdef DDB void ddb_display_cpuset(const cpuset_t *); #endif #else __BEGIN_DECLS int cpuset(cpusetid_t *); int cpuset_setid(cpuwhich_t, id_t, cpusetid_t); int cpuset_getid(cpulevel_t, cpuwhich_t, id_t, cpusetid_t *); int cpuset_getaffinity(cpulevel_t, cpuwhich_t, id_t, size_t, cpuset_t *); int cpuset_setaffinity(cpulevel_t, cpuwhich_t, id_t, size_t, const cpuset_t *); __END_DECLS #endif #endif /* !_SYS_CPUSET_H_ */ Index: head/sys/sys/domainset.h =================================================================== --- head/sys/sys/domainset.h (revision 365974) +++ head/sys/sys/domainset.h (revision 365975) @@ -1,126 +1,126 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2017, Jeffrey Roberson * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef _SYS_DOMAINSET_H_ #define _SYS_DOMAINSET_H_ #include #include #include #define _NDOMAINSETBITS _BITSET_BITS #define _NDOMAINSETWORDS __bitset_words(DOMAINSET_SETSIZE) #define DOMAINSETBUFSIZ \ (((2 + sizeof(long) * 2) * _NDOMAINSETWORDS) + \ sizeof("::") + sizeof(__XSTRING(DOMAINSET_POLICY_MAX)) + \ sizeof(__XSTRING(MAXMEMDOM))) #define DOMAINSET_CLR(n, p) BIT_CLR(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_COPY(f, t) BIT_COPY(DOMAINSET_SETSIZE, f, t) #define DOMAINSET_ISSET(n, p) BIT_ISSET(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_SET(n, p) BIT_SET(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_ZERO(p) BIT_ZERO(DOMAINSET_SETSIZE, p) #define DOMAINSET_FILL(p) BIT_FILL(DOMAINSET_SETSIZE, p) #define DOMAINSET_SETOF(n, p) BIT_SETOF(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_EMPTY(p) BIT_EMPTY(DOMAINSET_SETSIZE, p) #define DOMAINSET_ISFULLSET(p) BIT_ISFULLSET(DOMAINSET_SETSIZE, p) #define DOMAINSET_SUBSET(p, c) BIT_SUBSET(DOMAINSET_SETSIZE, p, c) #define DOMAINSET_OVERLAP(p, c) BIT_OVERLAP(DOMAINSET_SETSIZE, p, c) #define DOMAINSET_CMP(p, c) BIT_CMP(DOMAINSET_SETSIZE, p, c) #define DOMAINSET_OR(d, s) BIT_OR(DOMAINSET_SETSIZE, d, s) #define DOMAINSET_AND(d, s) BIT_AND(DOMAINSET_SETSIZE, d, s) #define DOMAINSET_ANDNOT(d, s) BIT_ANDNOT(DOMAINSET_SETSIZE, d, s) #define DOMAINSET_CLR_ATOMIC(n, p) BIT_CLR_ATOMIC(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_SET_ATOMIC(n, p) BIT_SET_ATOMIC(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_SET_ATOMIC_ACQ(n, p) \ BIT_SET_ATOMIC_ACQ(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_AND_ATOMIC(n, p) BIT_AND_ATOMIC(DOMAINSET_SETSIZE, n, p) #define DOMAINSET_OR_ATOMIC(d, s) BIT_OR_ATOMIC(DOMAINSET_SETSIZE, d, s) #define DOMAINSET_COPY_STORE_REL(f, t) \ BIT_COPY_STORE_REL(DOMAINSET_SETSIZE, f, t) #define DOMAINSET_FFS(p) BIT_FFS(DOMAINSET_SETSIZE, p) #define DOMAINSET_FLS(p) BIT_FLS(DOMAINSET_SETSIZE, p) -#define DOMAINSET_COUNT(p) BIT_COUNT(DOMAINSET_SETSIZE, p) +#define DOMAINSET_COUNT(p) ((int)BIT_COUNT(DOMAINSET_SETSIZE, p)) #define DOMAINSET_FSET BITSET_FSET(_NDOMAINSETWORDS) #define DOMAINSET_T_INITIALIZER BITSET_T_INITIALIZER #define DOMAINSET_POLICY_INVALID 0 #define DOMAINSET_POLICY_ROUNDROBIN 1 #define DOMAINSET_POLICY_FIRSTTOUCH 2 #define DOMAINSET_POLICY_PREFER 3 #define DOMAINSET_POLICY_INTERLEAVE 4 #define DOMAINSET_POLICY_MAX DOMAINSET_POLICY_INTERLEAVE #ifdef _KERNEL #if MAXMEMDOM < 256 typedef uint8_t domainid_t; #else typedef uint16_t domainid_t; #endif struct domainset { LIST_ENTRY(domainset) ds_link; domainset_t ds_mask; /* allowed domains. */ uint16_t ds_policy; /* Policy type. */ domainid_t ds_prefer; /* Preferred domain or -1. */ domainid_t ds_cnt; /* popcnt from above. */ domainid_t ds_order[MAXMEMDOM]; /* nth domain table. */ }; extern struct domainset domainset_fixed[MAXMEMDOM], domainset_prefer[MAXMEMDOM]; #define DOMAINSET_FIXED(domain) (&domainset_fixed[(domain)]) #define DOMAINSET_PREF(domain) (&domainset_prefer[(domain)]) extern struct domainset domainset_roundrobin; #define DOMAINSET_RR() (&domainset_roundrobin) void domainset_init(void); void domainset_zero(void); /* * Add a domainset to the system based on a key initializing policy, prefer, * and mask. Do not create and directly use domainset structures. The * returned value will not match the key pointer. */ struct domainset *domainset_create(const struct domainset *); #ifdef _SYS_SYSCTL_H_ int sysctl_handle_domainset(SYSCTL_HANDLER_ARGS); #endif #else __BEGIN_DECLS int cpuset_getdomain(cpulevel_t, cpuwhich_t, id_t, size_t, domainset_t *, int *); int cpuset_setdomain(cpulevel_t, cpuwhich_t, id_t, size_t, const domainset_t *, int); __END_DECLS #endif #endif /* !_SYS_DOMAINSET_H_ */