Optimize cpumask functions for SMPs with < BITS_PER_LONG processors

PATCH Ralf Baechle 2 participants 2 messages Sep 25, 2007 – Sep 28, 2007

Subsystems (3)

Generic include/asm header files Bitmap API Bitops API

lore

Share & tools

lore

Ralf Baechle

author

2007-09-25 15:52 UTC #0 lore raw

When debugging a kernel using a logic analyzer (!) a colleague recently noticed that because the <linux/cpumasks.h> functions are based on the generic bitops which support arbitrary size bitfields we had a relativly high overhead resulting from this. Here's the chainsaw edition of a patch to optimize this for CONFIG_NR_CPUS <= BITS_PER_LONG. Comments?

Ralf

From: Ralf Baechle <[email protected]>
Date: Tue, 31 Jul 2007 13:03:16 +0100

[PATCH] Optimize bitop code for single long bitfields such as cpumask_t on small SMP.

Signed-off-by Ralf Baechle <[email protected]>

include/asm-alpha/bitops.h +2 -0

index 9e71201..87e207e 100644
@@ -236,6 +236,8 @@ test_bit(int nr, const volatile void * addr)
 	return (1UL & (((const int *) addr)[nr >> 5] >> (nr & 31))) != 0UL;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
+
 /*
  * ffz = Find First Zero in word. Undefined if no zero exists,
  * so code should check against ~0UL first..

include/asm-arm/bitops.h +2 -0

index b41831b..98dcd15 100644
@@ -117,7 +117,9 @@ ____atomic_test_and_change_bit(unsigned int bit, volatile unsigned long *p)
 	return res & mask;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 /*
  *  A note about Endian-ness.

include/asm-avr32/bitops.h +2 -0

index 5299f8c..784d60b 100644
@@ -230,7 +230,9 @@ static inline int test_and_change_bit(int nr, volatile void * addr)
 	return (old & mask) != 0;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 /* Find First bit Set */
 static inline unsigned long __ffs(unsigned long word)

include/asm-blackfin/bitops.h +1 -0

index 27c2d0e..2fec38f 100644
@@ -11,6 +11,7 @@
 
 #ifdef __KERNEL__
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/ffs.h>
 #include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/sched.h>

include/asm-cris/bitops.h +2 -0

index a569065..2832ebd 100644
@@ -141,7 +141,9 @@ static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
 	return retval;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 /*
  * Since we define it "external", it collides with the built-in

include/asm-frv/bitops.h +1 -0

index f8560ed..509d20b 100644
@@ -303,6 +303,7 @@ int __ilog2_u64(u64 n)
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/ext2-non-atomic.h>
 
 #define ext2_set_bit_atomic(lock,nr,addr)	test_and_set_bit  ((nr) ^ 0x18, (addr))

include/asm-generic/bitops.h +2 -0

index 1f9d991..c741462 100644
@@ -10,7 +10,9 @@
  */
 
 #include <asm-generic/bitops/atomic.h>
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 #include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/ffz.h>
 #include <asm-generic/bitops/fls.h>

include/asm-generic/bitops/atomic-long.h new file +112 -0

112 lines not on this page · raw message

include/asm-generic/bitops/non-atomic-long.h new file +119 -0

119 lines not on this page · raw message

include/asm-h8300/bitops.h +1 -0

index d76299c..ba6d3f5 100644
@@ -194,6 +194,7 @@ static __inline__ unsigned long __ffs(unsigned long word)
 #include <asm-generic/bitops/find.h>
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/ext2-non-atomic.h>
 #include <asm-generic/bitops/ext2-atomic.h>
 #include <asm-generic/bitops/minix.h>

include/asm-i386/bitops.h +17 -0

index a20fe98..1079ba8 100644
@@ -58,6 +58,8 @@ static inline void __set_bit(int nr, volatile unsigned long * addr)
 		:"Ir" (nr));
 }
 
+#define __long_set_bit(nr,addr) __set_bit((nr), (addr))
+
 /**
  * clear_bit - Clears a bit in memory
  * @nr: Bit to clear

@@ -83,6 +85,9 @@ static inline void __clear_bit(int nr, volatile unsigned long * addr)
 		:"+m" (ADDR)
 		:"Ir" (nr));
 }
+
+#define __long_clear_bit(nr,addr) __clear_bit((nr), (addr))
+
 #define smp_mb__before_clear_bit()	barrier()
 #define smp_mb__after_clear_bit()	barrier()

@@ -103,6 +108,8 @@ static inline void __change_bit(int nr, volatile unsigned long * addr)
 		:"Ir" (nr));
 }
 
+#define __long_change_bit(nr,addr) __change_bit((nr), (addr))
+
 /**
  * change_bit - Toggle a bit in memory
  * @nr: Bit to change

@@ -161,6 +168,8 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long * addr)
 	return oldbit;
 }
 
+#define __long_test_and_set_bit(nr,addr) __test_and_set_bit((nr), (addr))
+
 /**
  * test_and_clear_bit - Clear a bit and return its old value
  * @nr: Bit to clear

@@ -201,6 +210,8 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
 	return oldbit;
 }
 
+#define __long_test_and_clear_bit(nr,addr) __test_and_clear_bit((nr), (addr))
+
 /* WARNING: non atomic and it can be reordered! */
 static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
 {

@@ -213,6 +224,8 @@ static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
 	return oldbit;
 }
 
+#define __long_test_and_change_bit(nr,addr) __test_and_change_bit((nr), (addr))
+
 /**
  * test_and_change_bit - Change a bit and return its old value
  * @nr: Bit to change

@@ -262,6 +275,10 @@ static inline int variable_test_bit(int nr, const volatile unsigned long * addr)
  constant_test_bit((nr),(addr)) : \
  variable_test_bit((nr),(addr)))
 
+#define long_test_bit(nr,addr) test_bit((nr), (addr))
+
+#include <asm-generic/bitops/atomic-long.h>
+
 #undef ADDR
 
 /**

include/asm-ia64/bitops.h +2 -0

index 6cc517e..7c97528 100644
@@ -279,6 +279,8 @@ test_bit (int nr, const volatile void *addr)
 	return 1 & (((const volatile __u32 *) addr)[nr >> 5] >> (nr & 31));
 }
 
+#include <asm-generic/bitops/atomic-long.h>
+
 /**
  * ffz - find the first zero bit in a long word
  * @x: The long word to find the bit in

include/asm-m32r/bitops.h +2 -0

index 66ab672..20ecc60 100644
@@ -243,7 +243,9 @@ static __inline__ int test_and_change_bit(int nr, volatile void * addr)
 	return (oldbit != 0);
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 #include <asm-generic/bitops/ffz.h>
 #include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/fls.h>

include/asm-m68k/bitops.h +2 -0

index 1a61fdb..86d67ba 100644
@@ -172,6 +172,8 @@ static inline int test_bit(int nr, const unsigned long *vaddr)
 	return (vaddr[nr >> 5] & (1UL << (nr & 31))) != 0;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
+
 static inline int find_first_zero_bit(const unsigned long *vaddr,
 				      unsigned size)
 {

include/asm-m68knommu/bitops.h +1 -0

index 7d6075d..d8f9a20 100644
@@ -158,6 +158,7 @@ static __inline__ int __test_bit(int nr, const volatile unsigned long * addr)
  __constant_test_bit((nr),(addr)) : \
  __test_bit((nr),(addr)))
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/find.h>
 #include <asm-generic/bitops/hweight.h>

include/asm-mips/bitops.h +106 ~~-57~~

392 lines not on this page · raw message

include/asm-parisc/bitops.h +2 -0

index 015cb0d..8a091cd 100644
@@ -108,7 +108,9 @@ static __inline__ int test_and_change_bit(int nr, volatile unsigned long * addr)
 	return (oldbit & mask) ? 1 : 0;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 #ifdef __KERNEL__

include/asm-powerpc/bitops.h +2 -0

index 8144a27..032b39e 100644
@@ -183,7 +183,9 @@ static __inline__ void set_bits(unsigned long mask, unsigned long *addr)
 	: "cc");
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 /*
  * Return the zero-based bit position (LE, not IBM bit numbering) of

include/asm-s390/bitops.h +2 -0

index f79c9b7..a52679a 100644
@@ -435,6 +435,8 @@ __constant_test_bit(unsigned long nr, const volatile unsigned long *addr) {
  __constant_test_bit((nr),(addr)) : \
  __test_bit((nr),(addr)) )
 
+#include <asm-generic/bitops/atomic-long.h>
+
 /*
  * ffz = Find First Zero in word. Undefined if no zero exists,
  * so code should check against ~0UL first..

include/asm-sh/bitops.h +2 -0

index 1c16792..7b8c9b7 100644
@@ -98,7 +98,9 @@ static inline int test_and_change_bit(int nr, volatile void * addr)
 	return retval;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 static inline unsigned long ffz(unsigned long word)
 {

include/asm-sh64/bitops.h +2 -0

index f3bdcdb..09c8824 100644
@@ -109,7 +109,9 @@ static __inline__ int test_and_change_bit(int nr, volatile void * addr)
 	return retval;
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 static __inline__ unsigned long ffz(unsigned long word)
 {

include/asm-sparc/bitops.h +2 -0

index 329e696..1aa4cbd 100644
@@ -84,7 +84,9 @@ static inline void change_bit(unsigned long nr, volatile unsigned long *addr)
 	(void) ___change_bit(ADDR, mask);
 }
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 #define smp_mb__before_clear_bit()	do { } while(0)
 #define smp_mb__after_clear_bit()	do { } while(0)

include/asm-sparc64/bitops.h +2 -0

index 3d5e1af..9eacf61 100644
@@ -17,7 +17,9 @@ extern void set_bit(unsigned long nr, volatile unsigned long *addr);
 extern void clear_bit(unsigned long nr, volatile unsigned long *addr);
 extern void change_bit(unsigned long nr, volatile unsigned long *addr);
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 #ifdef CONFIG_SMP
 #define smp_mb__before_clear_bit()	membar_storeload_loadload()

include/asm-v850/bitops.h +1 -0

index 1fa99ba..0810259 100644
@@ -138,6 +138,7 @@ static inline int __test_bit (int nr, const void *addr)
 #define smp_mb__before_clear_bit()	barrier ()
 #define smp_mb__after_clear_bit()	barrier ()
 
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/ffs.h>
 #include <asm-generic/bitops/fls.h>
 #include <asm-generic/bitops/fls64.h>

include/asm-x86_64/bitops.h +2 -0

index d4dbbe5..1fb5315 100644
@@ -254,6 +254,8 @@ static __inline__ int variable_test_bit(int nr, volatile const void * addr)
 
 #undef ADDR
 
+#include <asm-generic/bitops/atomic-long.h>
+
 extern long find_first_zero_bit(const unsigned long * addr, unsigned long size);
 extern long find_next_zero_bit (const unsigned long * addr, long size, long offset);
 extern long find_first_bit(const unsigned long * addr, unsigned long size);

include/asm-xtensa/bitops.h +2 -0

index 1c1e0d9..1754bac 100644
@@ -27,7 +27,9 @@
 #define smp_mb__after_clear_bit()	barrier()
 
 #include <asm-generic/bitops/atomic.h>
+#include <asm-generic/bitops/atomic-long.h>
 #include <asm-generic/bitops/non-atomic.h>
+#include <asm-generic/bitops/non-atomic-long.h>
 
 #if XCHAL_HAVE_NSA

include/linux/cpumask.h +23 -4

index 23f5514..3147f21 100644
@@ -91,13 +91,19 @@ extern cpumask_t _unused_cpumask_arg_;
 #define cpu_set(cpu, dst) __cpu_set((cpu), &(dst))
 static inline void __cpu_set(int cpu, volatile cpumask_t *dstp)
 {
-	set_bit(cpu, dstp->bits);
+	if (NR_CPUS <= BITS_PER_LONG)
+		long_set_bit(cpu, dstp->bits);
+	else
+		set_bit(cpu, dstp->bits);
 }
 
 #define cpu_clear(cpu, dst) __cpu_clear((cpu), &(dst))
 static inline void __cpu_clear(int cpu, volatile cpumask_t *dstp)
 {
-	clear_bit(cpu, dstp->bits);
+	if (NR_CPUS <= BITS_PER_LONG)
+		long_clear_bit(cpu, dstp->bits);
+	else
+		clear_bit(cpu, dstp->bits);
 }
 
 #define cpus_setall(dst) __cpus_setall(&(dst), NR_CPUS)

@@ -113,12 +119,25 @@ static inline void __cpus_clear(cpumask_t *dstp, int nbits)
 }
 
 /* No static inline type checking - see Subtlety (1) above. */
-#define cpu_isset(cpu, cpumask) test_bit((cpu), (cpumask).bits)
+#define cpu_isset(cpu, cpumask)						\
+({									\
+	int __res;							\
+									\
+	if (NR_CPUS <= BITS_PER_LONG)					\
+		__res = long_test_bit((cpu), (cpumask).bits);		\
+	else								\
+		__res = test_bit((cpu), (cpumask).bits);		\
+									\
+	__res;								\
+})
 
 #define cpu_test_and_set(cpu, cpumask) __cpu_test_and_set((cpu), &(cpumask))
 static inline int __cpu_test_and_set(int cpu, cpumask_t *addr)
 {
-	return test_and_set_bit(cpu, addr->bits);
+	if (NR_CPUS <= BITS_PER_LONG)
+		return long_test_and_set_bit(cpu, addr->bits);
+	else
+		return test_and_set_bit(cpu, addr->bits);
 }
 
 #define cpus_and(dst, src1, src2) __cpus_and(&(dst), &(src1), &(src2), NR_CPUS)

Andi Kleen

2007-09-28 17:34 UTC #1 lore raw

Quoted 5 lines · On Tuesday 25 September 2007 17:52:00 Ralf Baechle wrote:

When debugging a kernel using a logic analyzer (!) a colleague recently noticed that because the <linux/cpumasks.h> functions are based on the generic bitops which support arbitrary size bitfields we had a relativly high overhead resulting from this. Here's the chainsaw edition of a patch to optimize this for CONFIG_NR_CPUS <= BITS_PER_LONG. Comments?

The right thing to test is not CONFIG_NR_CPUS, but just
do __builtin_constant_p(x) && (x) <= BITS_PER_LONG ? fast case : external call in find_*_bit()

x86-64 has done this already for some time. But one issue is that
that the cpumask walk functions currently do (n = find_*_bit()) >= maxbit ? maxbit : n which also creates more overhead because some architectures get this wrong (including x86-64 I must admit)

-Andi