This patch consists of a single architecture-independent
header file and should apply to any version of the linux kernel.
This patch implements a scalable bitmask specifically
for tracking CPUs. It consists of a single architecture-independent
header file which simply adds a new datatype and supporting functions.
It allows for future expansion to a CPU count which is not confined
to the bit-size of (unsigned long). The new datatype (cpumap_t) and
supporting functions are optimized at compile-time according to
the definition of NR_CPUS.
While systems with more than 32 processors are still
out in the future, these interfaces provide a path for gradual
code migration. One of the primary goals is to provide current
functionality without affecting performance.
phys_cpu_present_map
cpu_initialized
wait_init_idle
cpu_online_map/cpu_present_mask
cpu_callin_map
cpu_callout_map
NOTE: The cpumap_to_ulong() and cpumap_ulong_to_cpumap() interfaces
are provided specifically for migration. In their current form,
they call BUG() if NR_CPUS is defined to be greater than the
bit-size of (unsigned long).
diff -Nru a/include/linux/cpumap.h b/include/linux/cpumap.h
--- /dev/null Wed Dec 31 16:00:00 1969
+++ b/include/linux/cpumap.h Thu Mar 14 11:27:55 2002
@@ -0,0 +1,246 @@
+/*
+ * cpumap_t data type and supporting functions
+ *
+ * Copyright (c) 2001 IBM Corp.
+ *
+ * 01/25/02 Initial Version Russ Weight <[email protected]>
+ *
+ * All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or (at
+ * your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or
+ * NON INFRINGEMENT. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef __LINUX_CPUMAP_H
+#define __LINUX_CPUMAP_H
+
+#ifdef CONFIG_SMP
+ #include <asm/types.h>
+ #define CPUMAP_SIZE ((NR_CPUS + BITS_PER_LONG - 1) / BITS_PER_LONG)
+#else
+ #define CPUMAP_SIZE 1
+#endif
+
+#ifndef __ASSEMBLY__
+#include <linux/bitops.h>
+typedef unsigned long cpumap_t[CPUMAP_SIZE];
+
+/*
+ * The cpumap_to_ulong() and cpumap_ulong_to_cpumap() functions
+ * are provided primarily for migration to the cpumap_t datatype.
+ * As currently defined, they are only valid for CPUMAP_SIZE==1.
+ */
+static inline unsigned long cpumap_to_ulong(cpumap_t cpumap)
+{
+#if CPUMAP_SIZE > 1
+ BUG(); /* Not supported */
+ return 0;
+#else
+ return cpumap[0];
+#endif
+}
+
+static inline void cpumap_ulong_to_cpumap(unsigned long bitmap, cpumap_t cpumap)
+{
+#if CPUMAP_SIZE > 1
+ BUG(); /* Not supported */
+#else
+ cpumap[0] = bitmap;
+#endif
+}
+
+
+/*
+ * The first set of interfaces are the same for SMP and UP.
+ */
+static inline void cpumap_clear_bit(int nr, cpumap_t cpumap)
+{
+ if (nr < NR_CPUS) {
+ clear_bit(nr, cpumap);
+ } else {
+ BUG();
+ }
+}
+
+static inline void cpumap_set_bit(int nr, cpumap_t cpumap)
+{
+ if (nr < NR_CPUS) {
+ set_bit(nr, cpumap);
+ } else {
+ BUG();
+ }
+}
+
+static inline int cpumap_test_and_set_bit(int nr, cpumap_t cpumap)
+{
+ if (nr < NR_CPUS) {
+ return test_and_set_bit(nr, cpumap);
+ } else {
+ BUG();
+ return -1;
+ }
+}
+
+/*
+ * Return 1 (non-zero) if they are equal, 0 if not equal
+ */
+static inline int cpumap_test_bit(int nr, cpumap_t cpumap)
+{
+ if (nr < NR_CPUS) {
+ return test_bit(nr, cpumap);
+ } else {
+ return 0;
+ }
+}
+
+/*
+ * The following interfaces are optimized for the case where
+ * CPUMAP_SIZE==1 (i.e. a single unsigned long). The single
+ * CPU case falls into the CPUMAP_SIZE==1 case.
+ */
+static inline void cpumap_clear_mask(cpumap_t cpumap)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ cpumap[i] = 0UL;
+ }
+#else
+ cpumap[0] = 0;
+#endif
+}
+
+static inline int cpumap_is_empty(cpumap_t map)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ if (map[i] != 0) {
+ return 0;
+ }
+ }
+ return 1;
+#else
+ return (map[0] == 0);
+#endif
+}
+
+/*
+ * Return 1 (non-zero) if they are equal, 0 if not equal
+ */
+static inline int cpumap_cmp_mask(cpumap_t map1, cpumap_t map2)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ if (map1[i] != map2[i]) {
+ return 0;
+ }
+ }
+ return 1;
+#else
+ return (map1[0] == map2[0]);
+#endif
+}
+
+#if (NR_CPUS % BITS_PER_LONG)
+#define CPUMAP_FILLMASK ((1 << (NR_CPUS % BITS_PER_LONG)) -1)
+#else
+#define CPUMAP_FILLMASK (~0UL)
+#endif
+
+static inline void cpumap_fill(cpumap_t cpumap)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+
+ for (i = 0; i < (CPUMAP_SIZE - 1); i++) {
+ cpumap[i] = ~0UL;
+ }
+ cpumap[CPUMAP_SIZE - 1] = CPUMAP_FILLMASK;
+#else
+ cpumap[0] = CPUMAP_FILLMASK;
+#endif
+}
+
+/*
+ * The following interfaces are optimized for the case where
+ * CPUMAP_SIZE==1 (i.e. a single unsigned long).
+ */
+static inline void cpumap_copy_mask(cpumap_t srcmap, cpumap_t destmap)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ destmap[i] = srcmap[i];
+ }
+#else
+ destmap[0] = srcmap[0];
+#endif
+}
+
+static inline void cpumap_and_mask(cpumap_t map1, cpumap_t map2, cpumap_t result)
+{
+#if CPUMAP_SIZE > 1
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ result[i] = map1[i] & map2[i];
+ }
+#else
+ result[0] = map1[0] & map2[0];
+#endif
+}
+
+/*
+ * The following macros and functions are used to format
+ * a cpumap_t object for display. This function knows the
+ * minimum size required, which is provided as CPUMAP_BUFSIZE.
+ *
+ * The CPUMAP_BUFSIZE is an exact calcuation of the byte count
+ * required to display a cpumap_t object.
+ */
+
+#define CPUMAP_BUFSIZE (((sizeof(long) * 2) + 1) * CPUMAP_SIZE + 2)
+
+#if BITS_PER_LONG > 32
+#define CPUMAP_FORMAT_STR "%016lx"
+#else
+#define CPUMAP_FORMAT_STR "%08lx"
+#endif
+
+static inline char *cpumap_format(cpumap_t map, char *buf, int size)
+{
+ if (size < CPUMAP_BUFSIZE) {
+ BUG();
+ }
+
+#if CPUMAP_SIZE > 1
+ sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[CPUMAP_SIZE-1]);
+ {
+ int i;
+ char *p = buf + strlen(buf);
+ for (i = CPUMAP_SIZE-2; i >= 0; i--, p += (sizeof(long) + 1)) {
+ sprintf(p, " " CPUMAP_FORMAT_STR, map[i]);
+ }
+ }
+#else
+ sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[0]);
+#endif
+ return(buf);
+}
+
+#endif /* __ASSEMBLY__ */
+#endif /* __LINUX_CPUMAP_H */
--
Russ Weight ([email protected])
Linux Technology Center
>
>
> NOTE: The cpumap_to_ulong() and cpumap_ulong_to_cpumap() interfaces
> are provided specifically for migration. In their current
> form, they call BUG() if NR_CPUS is defined to be greater
> than the bit-size of (unsigned long).
Why BUG? NR_CPUS is known at compile time, is there a reason why you
can't use a call to an undefined function in order to get a link time
error message? (like __bad_udelay in linux/asm-i386/udelay.h)
--
Manfred
> > NOTE: The cpumap_to_ulong() and cpumap_ulong_to_cpumap() interfaces
> > are provided specifically for migration. In their current
> > form, they call BUG() if NR_CPUS is defined to be greater
> > than the bit-size of (unsigned long).
>
> Why BUG? NR_CPUS is known at compile time, is there a reason why you
> can't use a call to an undefined function in order to get a link time
> error message? (like __bad_udelay in linux/asm-i386/udelay.h)
why that, rather than #error ?
Good point - I'll catch this at compile time. I'll resubmit shortly...
- Russ
On Mon, Mar 18, 2002 at 02:42:59PM -0800, Tim Hockin wrote:
> > > NOTE: The cpumap_to_ulong() and cpumap_ulong_to_cpumap() interfaces
> > > are provided specifically for migration. In their current
> > > form, they call BUG() if NR_CPUS is defined to be greater
> > > than the bit-size of (unsigned long).
> >
> > Why BUG? NR_CPUS is known at compile time, is there a reason why you
> > can't use a call to an undefined function in order to get a link time
> > error message? (like __bad_udelay in linux/asm-i386/udelay.h)
>
> why that, rather than #error ?
>
>
--
Russ Weight ([email protected])
Linux Technology Center
On 18 March 2002 20:07, Russ Weight wrote:
> While systems with more than 32 processors are still
> out in the future, these interfaces provide a path for gradual
> code migration. One of the primary goals is to provide current
> functionality without affecting performance.
Not so far in the future. "7.52 second kernel compile" thread is about
timing kernel compile on the 32 CPU SMP box.
I don't know whether BUG() in inlines makes them too big, but
_for() _loops_ in inline functions definitely do that.
Here's one of the overgrown inlines:
> +static inline char *cpumap_format(cpumap_t map, char *buf, int size)
> +{
> + if (size < CPUMAP_BUFSIZE) {
> + BUG();
> + }
> +
> +#if CPUMAP_SIZE > 1
> + sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[CPUMAP_SIZE-1]);
> + {
> + int i;
> + char *p = buf + strlen(buf);
> + for (i = CPUMAP_SIZE-2; i >= 0; i--, p += (sizeof(long) + 1)) {
> + sprintf(p, " " CPUMAP_FORMAT_STR, map[i]);
> + }
> + }
> +#else
> + sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[0]);
> +#endif
> + return(buf);
> +}
--
vda
Denis Vlasenko wrote:
>
> On 18 March 2002 20:07, Russ Weight wrote:
> > While systems with more than 32 processors are still
> > out in the future, these interfaces provide a path for gradual
> > code migration. One of the primary goals is to provide current
> > functionality without affecting performance.
>
> Not so far in the future. "7.52 second kernel compile" thread is about
> timing kernel compile on the 32 CPU SMP box.
The x86 spinlock implementation underflows at 128 CPUs [1].
> I don't know whether BUG() in inlines makes them too big,
It does, on all but very recent gcc's. Strings in inlines
generally cause vast kernel bloatage.
> but _for() _loops_ in inline functions definitely do that.
> Here's one of the overgrown inlines:
Sigh. There is far too much inlining in Linux.
[1] Untested.
-
On Tue, Mar 19, 2002 at 09:28:25AM -0200, Denis Vlasenko wrote:
> On 18 March 2002 20:07, Russ Weight wrote:
> > While systems with more than 32 processors are still
> > out in the future, these interfaces provide a path for gradual
> > code migration. One of the primary goals is to provide current
> > functionality without affecting performance.
>
> Not so far in the future. "7.52 second kernel compile" thread is about
> timing kernel compile on the 32 CPU SMP box.
>
> I don't know whether BUG() in inlines makes them too big, but
> _for() _loops_ in inline functions definitely do that.
> Here's one of the overgrown inlines:
I was hoping for some feedback regarding the use of BUG(). I have
been experimenting with the patch - changing various bitmasks to
use this new datatype. None of them do the error checking that I am
adding. Is it worth the overhead to have these checks at all? If
they ever trigger, they are indicative of an error elsewhere in the
kernel...
With respect to the for loops: For CPUMAP_SIZE > 1, most of the
interfaces expand to a "for loop". This is a performance vs. bloat
tradeoff. The "for-loop" versions of the functions _could_ be moved
to a cpumap.c file under lib. Is this the recommended approach?
The cpumap_format() function below is probably the worst offender.
There is no real performance value in making it an inline function...
>
> > +static inline char *cpumap_format(cpumap_t map, char *buf, int size)
> > +{
> > + if (size < CPUMAP_BUFSIZE) {
> > + BUG();
> > + }
> > +
> > +#if CPUMAP_SIZE > 1
> > + sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[CPUMAP_SIZE-1]);
> > + {
> > + int i;
> > + char *p = buf + strlen(buf);
> > + for (i = CPUMAP_SIZE-2; i >= 0; i--, p += (sizeof(long) + 1)) {
> > + sprintf(p, " " CPUMAP_FORMAT_STR, map[i]);
> > + }
> > + }
> > +#else
> > + sprintf(buf, "0x" CPUMAP_FORMAT_STR, map[0]);
> > +#endif
> > + return(buf);
> > +}
> --
> vda
--
Russ Weight ([email protected])
Linux Technology Center