2002-03-22 01:13:09

by Russ Weight

[permalink] [raw]
Subject: [PATCH 2.5.7] Scalable CPU bitmasks

This version of the patch has been split into two files
(cpumap.h and cpumap.c) in order to avoid bloated inline functions.
I am also detecting the invalid use of the cpumap_to_ulong() and
cpumap_ulong_to_cpumap() interfaces at compile time (per Manfred's
suggestion).

This patch implements a scalable bitmask specifically
for tracking CPUs. It consists of two architecture-independent
files, cpumap.h and cpumap.c. These files add a new datatype and
supporting functions which allow 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 interfaces 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. The following
is a list of some of the bitmasks that could be converted to
the new datatype.

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. If these interfaces are
used when NR_CPUS is greater than the bitsize of (unsigned long),
they will cause a link-time failure.

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 21 15:47:34 2002
@@ -0,0 +1,114 @@
+/*
+ * cpumap_t data type and supporting functions
+ *
+ * Copyright (c) 2002 IBM Corp.
+ *
+ * 01/25/02 Initial Version Russ Weight <[email protected]>
+ * 03/20/02 Move larger functions to cpumap.c Russ Weight
+ *
+ * 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
+
+#include <linux/config.h>
+#include <linux/threads.h>
+#include <asm/types.h>
+
+#ifdef CONFIG_SMP
+#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 following interfaces are the same for SMP and UP.
+ */
+#define cpumap_clear_bit clear_bit
+#define cpumap_set_bit set_bit
+#define cpumap_test_and_set_bit test_and_set_bit
+#define cpumap_test_bit test_bit
+
+#if (NR_CPUS % BITS_PER_LONG)
+#define CPUMAP_FILLMASK ((1 << (NR_CPUS % BITS_PER_LONG)) -1)
+#else
+#define CPUMAP_FILLMASK (~0UL)
+#endif
+
+/*
+ * The following macros and prototype 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
+extern char *cpumap_format(cpumap_t map, char *buf, int size);
+
+#if CPUMAP_SIZE == 1
+/*
+ * 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.
+ */
+#define cpumap_to_ulong(cpumap) (cpumap[0])
+#define cpumap_ulong_to_cpumap(bitmap, cpumap) (cpumap[0] = bitmap)
+#define cpumap_is_empty(cpumap) (cpumap[0] == 0)
+#define cpumap_cmp_mask(map1, map2) (map1[0] == map2[0])
+#define cpumap_clear_mask(cpumap) (cpumap[0] = 0)
+#define cpumap_fill(cpumap) (cpumap[0] = CPUMAP_FILLMASK)
+#define cpumap_copy_mask(srcmap, destmap) (destmap[0] = srcmap[0])
+#define cpumap_and_mask(map1, map2, result) (result[0] = map1[0] & map2[0])
+
+#else
+
+/*
+ * The cpumap_to_ulong() and cpumap_ulong_to_cpumap() functions
+ * are provided to facilitate migration to the cpumap_t datatype.
+ * As currently defined, they are only valid for CPUMAP_SIZE==1.
+ * If they are referenced when CPUMAP_SIZE > 1, then we call a
+ * bogus function name in order to trigger a link-time error.
+ */
+extern unsigned long __bad_cpumap_to_ulong(void);
+extern void __bad_cpumap_ulong_to_cpumap(void);
+#define cpumap_to_ulong(cpumap) __bad_cpumap_to_ulong()
+#define cpumap_ulong_to_cpumap(bitmap, cpumap) __bad_cpumap_ulong_to_cpumap()
+
+extern int cpumap_is_empty(cpumap_t map);
+extern int cpumap_cmp_mask(cpumap_t map1, cpumap_t map2);
+extern void cpumap_clear_mask(cpumap_t cpumap);
+extern void cpumap_fill(cpumap_t cpumap);
+extern void cpumap_copy_mask(cpumap_t srcmap, cpumap_t destmap);
+extern void cpumap_and_mask(cpumap_t map1, cpumap_t map2, cpumap_t result);
+
+#endif
+#endif
+#endif
diff -Nru a/lib/Makefile b/lib/Makefile
--- a/lib/Makefile Thu Mar 21 15:47:34 2002
+++ b/lib/Makefile Thu Mar 21 15:47:34 2002
@@ -8,9 +8,9 @@

L_TARGET := lib.a

-export-objs := cmdline.o dec_and_lock.o rwsem-spinlock.o rwsem.o crc32.o
+export-objs := cmdline.o dec_and_lock.o rwsem-spinlock.o rwsem.o crc32.o cpumap.o

-obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o bust_spinlocks.o rbtree.o
+obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o bust_spinlocks.o rbtree.o cpumap.o

obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff -Nru a/lib/cpumap.c b/lib/cpumap.c
--- /dev/null Wed Dec 31 16:00:00 1969
+++ b/lib/cpumap.c Thu Mar 21 15:47:34 2002
@@ -0,0 +1,132 @@
+/*
+ * Supporting functions for cpumap_t data type
+ *
+ * Copyright (c) 2002 IBM Corp.
+ *
+ * 03/20/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.
+ *
+ */
+#include <linux/kernel.h>
+#include <linux/cpumap.h>
+#include <asm/string.h>
+
+/* Not all architectures define BUG() */
+#ifndef BUG
+ #define BUG() do { \
+ printk("kernel BUG at %s:%d!\n", __FILE__, __LINE__); \
+ * ((char *) 0) = 0; \
+ } while (0)
+#endif /* BUG */
+
+/*
+ * The cpumap_format() function is used to format a cpumap_t
+ * object for display. This function knows the minimum size
+ * required, which is provided as CPUMAP_BUFSIZE.
+ */
+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);
+}
+
+#if CPUMAP_SIZE > 1
+/*
+ * The following interfaces are provided for (CPUMAP_SIZE > 1).
+ * For the case of (CPUMAP_SIZE==1) (i.e. a single unsigned long),
+ * the same interfaces are provided as inline functions in cpumap.h.
+ */
+int cpumap_is_empty(cpumap_t cpumap)
+{
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ if (cpumap[i] != 0) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+/*
+ * Return 1 (non-zero) if they are equal, 0 if not equal
+ */
+int cpumap_cmp_mask(cpumap_t map1, cpumap_t map2)
+{
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ if (map1[i] != map2[i]) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+void cpumap_clear_mask(cpumap_t cpumap)
+{
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ cpumap[i] = 0UL;
+ }
+}
+
+void cpumap_fill(cpumap_t cpumap)
+{
+ int i;
+ for (i = 0; i < (CPUMAP_SIZE - 1); i++) {
+ cpumap[i] = ~0UL;
+ }
+ cpumap[CPUMAP_SIZE - 1] = CPUMAP_FILLMASK;
+}
+
+/*
+ * The following interfaces are optimized for the case where
+ * CPUMAP_SIZE==1 (i.e. a single unsigned long).
+ */
+void cpumap_copy_mask(cpumap_t srcmap, cpumap_t destmap)
+{
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ destmap[i] = srcmap[i];
+ }
+}
+
+void cpumap_and_mask(cpumap_t map1, cpumap_t map2, cpumap_t result)
+{
+ int i;
+ for (i = 0; i < CPUMAP_SIZE; i++) {
+ result[i] = map1[i] & map2[i];
+ }
+}
+
+#endif
--
Russ Weight ([email protected])
Linux Technology Center