Generalize the bitset operations, present in cpuset and offer a KPI to

redefine such operations for different consumers.
This will be used when NUMA support will be finished and numaset
will need to be used.

Sponsored by:	EMC / Isilon storage division
Obtained from:	jeff
Reviewed by:	alc

4 files changed, 243 insertions, 126 deletions

diff --git a/sys/sys/_bitset.h b/sys/sys/_bitset.h
new file mode 100644
index 0000000..05d5bca
--- /dev/null
+++ b/sys/sys/_bitset.h
@@ -0,0 +1,61 @@
+/*-
+ * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
+ * 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_
+
+/*
+ * Macros addressing word and bit within it, tuned to make compiler
+ * optimize cases when SETSIZE fits into single machine word.
+ */
+#define	_BITSET_BITS		(sizeof(long) * NBBY)
+
+#define	__bitset_words(_s)	(howmany(_s, _BITSET_BITS))
+
+#define	__bitset_mask(_s, n)						\
+	(1L << ((__bitset_words((_s)) == 1) ?				\
+	    (__size_t)(n) : ((n) % _BITSET_BITS)))
+
+#define	__bitset_word(_s, n)						\
+	((__bitset_words((_s)) == 1) ? 0 : ((n) / _BITSET_BITS))
+
+#define	BITSET_DEFINE(t, _s)						\
+struct t {								\
+        long    __bits[__bitset_words((_s))];				\
+};
+
+#define	BITSET_T_INITIALIZER(x)						\
+	{ .__bits = { x } }
+
+#define	BITSET_FSET(n)							\
+	[ 0 ... ((n) - 1) ] = (-1L)
+
+#endif /* !_SYS__BITSET_H_ */
diff --git a/sys/sys/_cpuset.h b/sys/sys/_cpuset.h
index a11c0f0..a488700 100644
--- a/sys/sys/_cpuset.h
+++ b/sys/sys/_cpuset.h
@@ -32,6 +32,8 @@
 #ifndef _SYS__CPUSET_H_
 #define	_SYS__CPUSET_H_
 
+#include <sys/_bitset.h>
+
 #ifdef _KERNEL
 #define	CPU_SETSIZE	MAXCPU
 #endif
@@ -42,17 +44,13 @@
 #define	CPU_SETSIZE	CPU_MAXSIZE
 #endif
 
-#define	_NCPUBITS	(sizeof(long) * NBBY)	/* bits per mask */
-#define	_NCPUWORDS	howmany(CPU_SETSIZE, _NCPUBITS)
-
-typedef	struct _cpuset {
-	long	__bits[howmany(CPU_SETSIZE, _NCPUBITS)];
-} cpuset_t;
+#define	_NCPUBITS	_BITSET_BITS
+#define	_NCPUWORDS	__bitset_words(CPU_SETSIZE)
 
-#define	CPUSET_FSET							\
-	[ 0 ... (_NCPUWORDS - 1) ] = (-1L)
+BITSET_DEFINE(_cpuset, CPU_SETSIZE);
+typedef struct _cpuset cpuset_t;
 
-#define	CPUSET_T_INITIALIZER(x)						\
-	{ .__bits = { x } }
+#define	CPUSET_FSET		BITSET_FSET(_NCPUWORDS)
+#define	CPUSET_T_INITIALIZER	BITSET_T_INITIALIZER
 
 #endif /* !_SYS__CPUSET_H_ */
diff --git a/sys/sys/bitset.h b/sys/sys/bitset.h
new file mode 100644
index 0000000..c93cb2c
--- /dev/null
+++ b/sys/sys/bitset.h
@@ -0,0 +1,153 @@
+/*-
+ * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
+ * 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_
+
+#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_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_NAND(_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_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))
+
+/* Convenience functions catering special cases. */ 
+#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)
+
+#endif /* !_SYS_BITSET_H_ */
diff --git a/sys/sys/cpuset.h b/sys/sys/cpuset.h
index 9e6c125..259070b 100644
--- a/sys/sys/cpuset.h
+++ b/sys/sys/cpuset.h
@@ -34,124 +34,29 @@
 
 #include <sys/_cpuset.h>
 
-#define	CPUSETBUFSIZ	((2 + sizeof(long) * 2) * _NCPUWORDS)
-
-/*
- * Macros addressing word and bit within it, tuned to make compiler
- * optimize cases when CPU_SETSIZE fits into single machine word.
- */
-#define	__cpuset_mask(n)				\
-	((long)1 << ((_NCPUWORDS == 1) ? (__size_t)(n) : ((n) % _NCPUBITS)))
-#define	__cpuset_word(n)	((_NCPUWORDS == 1) ? 0 : ((n) / _NCPUBITS))
-
-#define	CPU_CLR(n, p)	((p)->__bits[__cpuset_word(n)] &= ~__cpuset_mask(n))
-#define	CPU_COPY(f, t)	(void)(*(t) = *(f))
-#define	CPU_ISSET(n, p)	(((p)->__bits[__cpuset_word(n)] & __cpuset_mask(n)) != 0)
-#define	CPU_SET(n, p)	((p)->__bits[__cpuset_word(n)] |= __cpuset_mask(n))
-#define	CPU_ZERO(p) do {				\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		(p)->__bits[__i] = 0;			\
-} while (0)
-
-#define	CPU_FILL(p) do {				\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		(p)->__bits[__i] = -1;			\
-} while (0)
-
-#define	CPU_SETOF(n, p) do {					\
-	CPU_ZERO(p);						\
-	((p)->__bits[__cpuset_word(n)] = __cpuset_mask(n));	\
-} while (0)
-
-/* Is p empty. */
-#define	CPU_EMPTY(p) __extension__ ({			\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		if ((p)->__bits[__i])			\
-			break;				\
-	__i == _NCPUWORDS;				\
-})
-
-/* Is p full set. */
-#define	CPU_ISFULLSET(p) __extension__ ({		\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		if ((p)->__bits[__i] != (long)-1)	\
-			break;				\
-	__i == _NCPUWORDS;				\
-})
+#include <sys/bitset.h>
 
-/* Is c a subset of p. */
-#define	CPU_SUBSET(p, c) __extension__ ({		\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		if (((c)->__bits[__i] &			\
-		    (p)->__bits[__i]) !=		\
-		    (c)->__bits[__i])			\
-			break;				\
-	__i == _NCPUWORDS;				\
-})
-
-/* Are there any common bits between b & c? */
-#define	CPU_OVERLAP(p, c) __extension__ ({		\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		if (((c)->__bits[__i] &			\
-		    (p)->__bits[__i]) != 0)		\
-			break;				\
-	__i != _NCPUWORDS;				\
-})
-
-/* Compare two sets, returns 0 if equal 1 otherwise. */
-#define	CPU_CMP(p, c) __extension__ ({			\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		if (((c)->__bits[__i] !=		\
-		    (p)->__bits[__i]))			\
-			break;				\
-	__i != _NCPUWORDS;				\
-})
-
-#define	CPU_OR(d, s) do {				\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		(d)->__bits[__i] |= (s)->__bits[__i];	\
-} while (0)
-
-#define	CPU_AND(d, s) do {				\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		(d)->__bits[__i] &= (s)->__bits[__i];	\
-} while (0)
-
-#define	CPU_NAND(d, s) do {				\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		(d)->__bits[__i] &= ~(s)->__bits[__i];	\
-} while (0)
-
-#define	CPU_CLR_ATOMIC(n, p)						\
-	atomic_clear_long(&(p)->__bits[__cpuset_word(n)], __cpuset_mask(n))
-
-#define	CPU_SET_ATOMIC(n, p)						\
-	atomic_set_long(&(p)->__bits[__cpuset_word(n)], __cpuset_mask(n))
-
-/* Convenience functions catering special cases. */ 
-#define	CPU_OR_ATOMIC(d, s) do {			\
-	__size_t __i;					\
-	for (__i = 0; __i < _NCPUWORDS; __i++)		\
-		atomic_set_long(&(d)->__bits[__i],	\
-		    (s)->__bits[__i]);			\
-} while (0)
+#define	CPUSETBUFSIZ	((2 + sizeof(long) * 2) * _NCPUWORDS)
 
-#define	CPU_COPY_STORE_REL(f, t) do {				\
-	__size_t __i;						\
-	for (__i = 0; __i < _NCPUWORDS; __i++)			\
-		atomic_store_rel_long(&(t)->__bits[__i],	\
-		    (f)->__bits[__i]);				\
-} while (0)
+#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_NAND(d, s)			BIT_NAND(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_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)
 
 /*
  * Valid cpulevel_t values.