From f4b0373b26567cafd421d91101852ed7a34e9e94 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Fri, 21 Aug 2009 09:26:15 -0700 Subject: Make bitmask 'and' operators return a result code When 'and'ing two bitmasks (where 'andnot' is a variation on it), some cases want to know whether the result is the empty set or not. In particular, the TLB IPI sending code wants to do cpumask operations and determine if there are any CPU's left in the final set. So this just makes the bitmask (and cpumask) functions return a boolean for whether the result has any bits set. Cc: stable@kernel.org (2.6.30, needed by TLB shootdown fix) Signed-off-by: Linus Torvalds --- include/linux/bitmap.h | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 2878811c6134..756d78b8c1c5 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -94,13 +94,13 @@ extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, int shift, int bits); extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, int shift, int bits); -extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, +extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); -extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, +extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); extern int __bitmap_intersects(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); @@ -171,13 +171,12 @@ static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, } } -static inline void bitmap_and(unsigned long *dst, const unsigned long *src1, +static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, int nbits) { if (small_const_nbits(nbits)) - *dst = *src1 & *src2; - else - __bitmap_and(dst, src1, src2, nbits); + return (*dst = *src1 & *src2) != 0; + return __bitmap_and(dst, src1, src2, nbits); } static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, @@ -198,13 +197,12 @@ static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, __bitmap_xor(dst, src1, src2, nbits); } -static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1, +static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, int nbits) { if (small_const_nbits(nbits)) - *dst = *src1 & ~(*src2); - else - __bitmap_andnot(dst, src1, src2, nbits); + return (*dst = *src1 & ~(*src2)) != 0; + return __bitmap_andnot(dst, src1, src2, nbits); } static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, -- cgit v1.2.3 From c1a2a962a2ad103846e7950b4591471fabecece7 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Tue, 15 Dec 2009 16:48:25 -0800 Subject: bitmap: introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area This introduces new bitmap functions: bitmap_set: Set specified bit area bitmap_clear: Clear specified bit area bitmap_find_next_zero_area: Find free bit area These are mostly stolen from iommu helper. The differences are: - Use find_next_bit instead of doing test_bit for each bit - Rewrite bitmap_set and bitmap_clear Instead of setting or clearing for each bit. - Check the last bit of the limit iommu-helper doesn't want to find such area - The return value if there is no zero area find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size Signed-off-by: Akinobu Mita Cc: FUJITA Tomonori Cc: "David S. Miller" Cc: Benjamin Herrenschmidt Cc: Paul Mackerras Cc: Thomas Gleixner Cc: Ingo Molnar Cc: "H. Peter Anvin" Cc: Greg Kroah-Hartman Cc: Lothar Wassmann Cc: Roland Dreier Cc: Yevgeny Petrilin Cc: Tony Luck Cc: Fenghua Yu Cc: Joerg Roedel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/bitmap.h | 11 +++++++ lib/bitmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+) (limited to 'include/linux/bitmap.h') diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 756d78b8c1c5..daf8c480c786 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -42,6 +42,9 @@ * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits + * bitmap_set(dst, pos, nbits) Set specified bit area + * bitmap_clear(dst, pos, nbits) Clear specified bit area + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) @@ -108,6 +111,14 @@ extern int __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); extern int __bitmap_weight(const unsigned long *bitmap, int bits); +extern void bitmap_set(unsigned long *map, int i, int len); +extern void bitmap_clear(unsigned long *map, int start, int nr); +extern unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask); + extern int bitmap_scnprintf(char *buf, unsigned int len, const unsigned long *src, int nbits); extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user, diff --git a/lib/bitmap.c b/lib/bitmap.c index 702565821c99..11bf49750583 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -271,6 +271,87 @@ int __bitmap_weight(const unsigned long *bitmap, int bits) } EXPORT_SYMBOL(__bitmap_weight); +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) + +void bitmap_set(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_set >= 0) { + *p |= mask_to_set; + nr -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (nr) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} +EXPORT_SYMBOL(bitmap_set); + +void bitmap_clear(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_clear >= 0) { + *p &= ~mask_to_clear; + nr -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + if (nr) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + *p &= ~mask_to_clear; + } +} +EXPORT_SYMBOL(bitmap_clear); + +/* + * bitmap_find_next_zero_area - find a contiguous aligned zero area + * @map: The address to base the search on + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + * @nr: The number of zeroed bits we're looking for + * @align_mask: Alignment mask for zero area + * + * The @align_mask should be one less than a power of 2; the effect is that + * the bit offset of all zero areas this function finds is multiples of that + * power of 2. A @align_mask of 0 means no alignment is required. + */ +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask) +{ + unsigned long index, end, i; +again: + index = find_next_zero_bit(map, size, start); + + /* Align allocation */ + index = __ALIGN_MASK(index, align_mask); + + end = index + nr; + if (end > size) + return end; + i = find_next_bit(map, end, index); + if (i < end) { + start = i + 1; + goto again; + } + return index; +} +EXPORT_SYMBOL(bitmap_find_next_zero_area); + /* * Bitmap printing & parsing functions: first version by Bill Irwin, * second version by Paul Jackson, third by Joe Korty. -- cgit v1.2.3 From 0ac0c0d0f837c499afd02a802f9cf52d3027fa3b Mon Sep 17 00:00:00 2001 From: Jack Steiner Date: Wed, 26 May 2010 14:42:51 -0700 Subject: cpusets: randomize node rotor used in cpuset_mem_spread_node() Some workloads that create a large number of small files tend to assign too many pages to node 0 (multi-node systems). Part of the reason is that the rotor (in cpuset_mem_spread_node()) used to assign nodes starts at node 0 for newly created tasks. This patch changes the rotor to be initialized to a random node number of the cpuset. [akpm@linux-foundation.org: fix layout] [Lee.Schermerhorn@hp.com: Define stub numa_random() for !NUMA configuration] Signed-off-by: Jack Steiner Signed-off-by: Lee Schermerhorn Cc: Christoph Lameter Cc: Pekka Enberg Cc: Paul Menage Cc: Jack Steiner Cc: Robin Holt Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- arch/x86/mm/numa.c | 17 +++++++++++++++++ include/linux/bitmap.h | 1 + include/linux/nodemask.h | 8 ++++++++ kernel/fork.c | 4 ++++ lib/bitmap.c | 2 +- 5 files changed, 31 insertions(+), 1 deletion(-) (limited to 'include/linux/bitmap.h') diff --git a/arch/x86/mm/numa.c b/arch/x86/mm/numa.c index 550df481accd..10c27bb1e95f 100644 --- a/arch/x86/mm/numa.c +++ b/arch/x86/mm/numa.c @@ -2,6 +2,7 @@ #include #include #include +#include #ifdef CONFIG_DEBUG_PER_CPU_MAPS # define DBG(x...) printk(KERN_DEBUG x) @@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(int node) } EXPORT_SYMBOL(cpumask_of_node); #endif + +/* + * Return the bit number of a random bit set in the nodemask. + * (returns -1 if nodemask is empty) + */ +int __node_random(const nodemask_t *maskp) +{ + int w, bit = -1; + + w = nodes_weight(*maskp); + if (w) + bit = bitmap_ord_to_pos(maskp->bits, + get_random_int() % w, MAX_NUMNODES); + return bit; +} +EXPORT_SYMBOL(__node_random); diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index daf8c480c786..6fb2720882fc 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -141,6 +141,7 @@ extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order); extern void bitmap_release_region(unsigned long *bitmap, int pos, int order); extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order); extern void bitmap_copy_le(void *dst, const unsigned long *src, int nbits); +extern int bitmap_ord_to_pos(const unsigned long *bitmap, int n, int bits); #define BITMAP_LAST_WORD_MASK(nbits) \ ( \ diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h index dba35e413371..8a8f1d09c133 100644 --- a/include/linux/nodemask.h +++ b/include/linux/nodemask.h @@ -66,6 +66,8 @@ * int num_online_nodes() Number of online Nodes * int num_possible_nodes() Number of all possible Nodes * + * int node_random(mask) Random node with set bit in mask + * * int node_online(node) Is some node online? * int node_possible(node) Is some node possible? * @@ -430,6 +432,10 @@ static inline void node_set_offline(int nid) node_clear_state(nid, N_ONLINE); nr_online_nodes = num_node_state(N_ONLINE); } + +#define node_random(mask) __node_random(&(mask)) +extern int __node_random(const nodemask_t *maskp); + #else static inline int node_state(int node, enum node_states state) @@ -460,6 +466,8 @@ static inline int num_node_state(enum node_states state) #define node_set_online(node) node_set_state((node), N_ONLINE) #define node_set_offline(node) node_clear_state((node), N_ONLINE) + +static inline int node_random(const nodemask_t mask) { return 0; } #endif #define node_online_map node_states[N_ONLINE] diff --git a/kernel/fork.c b/kernel/fork.c index 4d57d9e3a6e9..2e9cc3139ec6 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -1079,6 +1079,10 @@ static struct task_struct *copy_process(unsigned long clone_flags, } mpol_fix_fork_child_flag(p); #endif +#ifdef CONFIG_CPUSETS + p->cpuset_mem_spread_rotor = node_random(p->mems_allowed); + p->cpuset_slab_spread_rotor = node_random(p->mems_allowed); +#endif #ifdef CONFIG_TRACE_IRQFLAGS p->irq_events = 0; #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW diff --git a/lib/bitmap.c b/lib/bitmap.c index ffb78c916ccd..d7137e7e06e8 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -672,7 +672,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits) * * The bit positions 0 through @bits are valid positions in @buf. */ -static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) +int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) { int pos = 0; -- cgit v1.2.3 From 35926ff5fba8245bd1c6ac04155048f6f89232b1 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 30 May 2010 09:00:03 -0700 Subject: Revert "cpusets: randomize node rotor used in cpuset_mem_spread_node()" This reverts commit 0ac0c0d0f837c499afd02a802f9cf52d3027fa3b, which caused cross-architecture build problems for all the wrong reasons. IA64 already added its own version of __node_random(), but the fact is, there is nothing architectural about the function, and the original commit was just badly done. Revert it, since no fix is forthcoming. Requested-by: Stephen Rothwell Signed-off-by: Linus Torvalds --- arch/x86/mm/numa.c | 17 ----------------- include/linux/bitmap.h | 1 - include/linux/nodemask.h | 8 -------- kernel/fork.c | 4 ---- lib/bitmap.c | 2 +- 5 files changed, 1 insertion(+), 31 deletions(-) (limited to 'include/linux/bitmap.h') diff --git a/arch/x86/mm/numa.c b/arch/x86/mm/numa.c index 10c27bb1e95f..550df481accd 100644 --- a/arch/x86/mm/numa.c +++ b/arch/x86/mm/numa.c @@ -2,7 +2,6 @@ #include #include #include -#include #ifdef CONFIG_DEBUG_PER_CPU_MAPS # define DBG(x...) printk(KERN_DEBUG x) @@ -66,19 +65,3 @@ const struct cpumask *cpumask_of_node(int node) } EXPORT_SYMBOL(cpumask_of_node); #endif - -/* - * Return the bit number of a random bit set in the nodemask. - * (returns -1 if nodemask is empty) - */ -int __node_random(const nodemask_t *maskp) -{ - int w, bit = -1; - - w = nodes_weight(*maskp); - if (w) - bit = bitmap_ord_to_pos(maskp->bits, - get_random_int() % w, MAX_NUMNODES); - return bit; -} -EXPORT_SYMBOL(__node_random); diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 6fb2720882fc..daf8c480c786 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -141,7 +141,6 @@ extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order); extern void bitmap_release_region(unsigned long *bitmap, int pos, int order); extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order); extern void bitmap_copy_le(void *dst, const unsigned long *src, int nbits); -extern int bitmap_ord_to_pos(const unsigned long *bitmap, int n, int bits); #define BITMAP_LAST_WORD_MASK(nbits) \ ( \ diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h index 8a8f1d09c133..dba35e413371 100644 --- a/include/linux/nodemask.h +++ b/include/linux/nodemask.h @@ -66,8 +66,6 @@ * int num_online_nodes() Number of online Nodes * int num_possible_nodes() Number of all possible Nodes * - * int node_random(mask) Random node with set bit in mask - * * int node_online(node) Is some node online? * int node_possible(node) Is some node possible? * @@ -432,10 +430,6 @@ static inline void node_set_offline(int nid) node_clear_state(nid, N_ONLINE); nr_online_nodes = num_node_state(N_ONLINE); } - -#define node_random(mask) __node_random(&(mask)) -extern int __node_random(const nodemask_t *maskp); - #else static inline int node_state(int node, enum node_states state) @@ -466,8 +460,6 @@ static inline int num_node_state(enum node_states state) #define node_set_online(node) node_set_state((node), N_ONLINE) #define node_set_offline(node) node_clear_state((node), N_ONLINE) - -static inline int node_random(const nodemask_t mask) { return 0; } #endif #define node_online_map node_states[N_ONLINE] diff --git a/kernel/fork.c b/kernel/fork.c index bf9fef6d1bfe..b6cce14ba047 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -1086,10 +1086,6 @@ static struct task_struct *copy_process(unsigned long clone_flags, } mpol_fix_fork_child_flag(p); #endif -#ifdef CONFIG_CPUSETS - p->cpuset_mem_spread_rotor = node_random(p->mems_allowed); - p->cpuset_slab_spread_rotor = node_random(p->mems_allowed); -#endif #ifdef CONFIG_TRACE_IRQFLAGS p->irq_events = 0; #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW diff --git a/lib/bitmap.c b/lib/bitmap.c index d7137e7e06e8..ffb78c916ccd 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -672,7 +672,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits) * * The bit positions 0 through @bits are valid positions in @buf. */ -int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) +static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) { int pos = 0; -- cgit v1.2.3