- Randomize node rotor used in cpuset_mem_spread_node()

PATCH In review Jack Steiner 5 participants 10 messages Apr 28, 2010 – Apr 29, 2010

Subsystems (8)

Memory management x86 Library code MM core +4 more subsystems

lore

Share & tools

lore

Jack Steiner

author

2010-04-28 13:12 UTC #0 lore raw

PATCH 1/1 - 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.

Signed-off-by Jack Steiner <[email protected]>

---
 arch/x86/mm/numa.c       |   17 +++++++++++++++++
 include/linux/bitmap.h   |    1 +
 include/linux/nodemask.h |    5 +++++
 kernel/fork.c            |    4 ++++
 lib/bitmap.c             |   19 +++++++++++++++++++
 5 files changed, 46 insertions(+)

arch/x86/mm/numa.c +17 -0

Index: linux/arch/x86/mm/numa.c
===================================================================
@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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->bits);
+	if (w)
+		bit = bitmap_find_nth_bit(maskp->bits,
+				get_random_int() % w, MAX_NUMNODES);
+	return bit;
+}
+EXPORT_SYMBOL(__node_random);

include/linux/bitmap.h +1 -0

Index: linux/include/linux/bitmap.h
===================================================================
@@ -130,6 +130,7 @@ extern int bitmap_find_free_region(unsig
 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_find_nth_bit(const unsigned long *bitmap, int n, int bits);
 
 #define BITMAP_LAST_WORD_MASK(nbits)					\
 (									\

include/linux/nodemask.h +5 -0

Index: linux/include/linux/nodemask.h
===================================================================
@@ -71,6 +71,8 @@
  *
  * int any_online_node(mask)		First online node in mask
  *
+ * int node_random(mask)		Random node that is set in mask
+ *
  * node_set_online(node)		set bit 'node' in node_online_map
  * node_set_offline(node)		clear bit 'node' in node_online_map
  *

@@ -264,6 +266,9 @@ static inline int __first_unset_node(con
 			find_first_zero_bit(maskp->bits, MAX_NUMNODES));
 }
 
+#define node_random(mask) __node_random(&(mask))
+extern int __node_random(const nodemask_t *maskp);
+
 #define NODE_MASK_LAST_WORD BITMAP_LAST_WORD_MASK(MAX_NUMNODES)
 
 #if MAX_NUMNODES <= BITS_PER_LONG

kernel/fork.c +4 -0

Index: linux/kernel/fork.c
===================================================================
@@ -1097,6 +1097,10 @@ static struct task_struct *copy_process(
  	}
 	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

lib/bitmap.c +19 -0

Index: linux/lib/bitmap.c
===================================================================
@@ -1022,3 +1022,22 @@ void bitmap_copy_le(void *dst, const uns
 	}
 }
 EXPORT_SYMBOL(bitmap_copy_le);
+
+/**
+ * bitmap_find_nth_bit(buf, ord, bits)
+ *	@buf: pointer to bitmap
+ *	@n: ordinal bit position (n-th set bit, n >= 0)
+ * @nbits: number of bits in the bitmap
+ *
+ * find the Nth bit that is set in the bitmap
+ * Value of @n should be in range 0 <= @n < weight(buf), else
+ * results are undefined.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */
+int bitmap_find_nth_bit(const unsigned long *bitmap, int n, int bits)
+{
+	return bitmap_ord_to_pos(bitmap, n, bits);
+}
+EXPORT_SYMBOL(bitmap_find_nth_bit);
+

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Jack Steiner

author

2010-04-28 15:04 UTC #1 lore raw

This patch changes the rotor to be initialized to a random node number of the cpuset.

NOTE: this patch is on TOP of the previous patch:

	[PATCH] - New round-robin rotor for SLAB allocations
	http://marc.info/?l=linux-mm&m=127231565321947&w=2

Signed-off-by Jack Steiner <[email protected]>

---

V2 - initial patch was generated against the wrong tree. This patch is based on linux-next.

 arch/x86/mm/numa.c       |   17 +++++++++++++++++
 include/linux/bitmap.h   |    1 +
 include/linux/nodemask.h |    5 +++++
 kernel/fork.c            |    4 ++++
 lib/bitmap.c             |   19 +++++++++++++++++++
 5 files changed, 46 insertions(+)

arch/x86/mm/numa.c +17 -0

Index: linux/arch/x86/mm/numa.c
===================================================================
@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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_find_nth_bit(maskp->bits,
+			get_random_int() % w, MAX_NUMNODES);
+	return bit;
+}
+EXPORT_SYMBOL(__node_random);

include/linux/bitmap.h +1 -0

Index: linux/include/linux/bitmap.h
===================================================================
@@ -141,6 +141,7 @@ extern int bitmap_find_free_region(unsig
 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_find_nth_bit(const unsigned long *bitmap, int n, int bits);
 
 #define BITMAP_LAST_WORD_MASK(nbits)					\
 (									\

include/linux/nodemask.h +5 -0

Index: linux/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?
  *

@@ -267,6 +269,9 @@ static inline int __first_unset_node(con
 			find_first_zero_bit(maskp->bits, MAX_NUMNODES));
 }
 
+#define node_random(mask) __node_random(&(mask))
+extern int __node_random(const nodemask_t *maskp);
+
 #define NODE_MASK_LAST_WORD BITMAP_LAST_WORD_MASK(MAX_NUMNODES)
 
 #if MAX_NUMNODES <= BITS_PER_LONG

kernel/fork.c +4 -0

Index: linux/kernel/fork.c
===================================================================
@@ -1079,6 +1079,10 @@ static struct task_struct *copy_process(
  	}
 	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

lib/bitmap.c +19 -0

Index: linux/lib/bitmap.c
===================================================================
@@ -1098,3 +1098,22 @@ void bitmap_copy_le(void *dst, const uns
 	}
 }
 EXPORT_SYMBOL(bitmap_copy_le);
+
+/**
+ * bitmap_find_nth_bit(buf, ord, bits)
+ *	@buf: pointer to bitmap
+ *	@n: ordinal bit position (n-th set bit, n >= 0)
+ * @nbits: number of bits in the bitmap
+ *
+ * find the Nth bit that is set in the bitmap
+ * Value of @n should be in range 0 <= @n < weight(buf), else
+ * results are undefined.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */
+int bitmap_find_nth_bit(const unsigned long *bitmap, int n, int bits)
+{
+	return bitmap_ord_to_pos(bitmap, n, bits);
+}
+EXPORT_SYMBOL(bitmap_find_nth_bit);
+

Andrew Morton

maintainer

2010-04-28 22:40 UTC #2 lore raw

Quoted 4 lines · On Wed, 28 Apr 2010 10:04:32 -0500 Jack Steiner <[email protected]> wrote:

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.

And, presumably, your secret testcase forks lots of subprocesses which do the file creation?

Quoted 2 lines

This patch changes the rotor to be initialized to a random node number of the cpuset.

Why random as opposed to, say, inherit-rotor-from-parent?

Quoted 22 lines

Index: linux/arch/x86/mm/numa.c
===================================================================

arch/x86/mm/numa.c +7 -0

@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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)

arch/x86/mm/numa.c const struct cpumask *cpumask_of_node(in · line 84

Quoted 10 lines

arch/x86/mm/numa.c +10 -0

+{
+	int w, bit = -1;
+
+	w = nodes_weight(*maskp);
+	if (w)
+		bit = bitmap_find_nth_bit(maskp->bits,
+			get_random_int() % w, MAX_NUMNODES);
+	return bit;
+}
+EXPORT_SYMBOL(__node_random);

I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.

Quoted 8 lines

arch/x86/mm/numa.c +8 -0

+
+/**
+ * bitmap_find_nth_bit(buf, ord, bits)
+ *	@buf: pointer to bitmap
+ *	@n: ordinal bit position (n-th set bit, n >= 0)
+ * @nbits: number of bits in the bitmap
+ *
+ * find the Nth bit that is set in the bitmap

arch/x86/mm/numa.c

Quoted 10 lines

arch/x86/mm/numa.c +10 -0

+ * Value of @n should be in range 0 <= @n < weight(buf), else
+ * results are undefined.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */
+int bitmap_find_nth_bit(const unsigned long *bitmap, int n, int bits)
+{
+	return bitmap_ord_to_pos(bitmap, n, bits);
+}
+EXPORT_SYMBOL(bitmap_find_nth_bit);

This does nothing apart from consume more stack? Better to rename bitmap_ord_to_pos() and export it.

Matt Mackall

2010-04-28 23:04 UTC #3 lore raw

Quoted 8 lines · Andrew Morton

Quoted 4 lines · On Wed, 28 Apr 2010 10:04:32 -0500 Jack Steiner <[email protected]> wrote:
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.

Quoted 7 lines

And, presumably, your secret testcase forks lots of subprocesses which do the file creation?
Quoted 2 lines
This patch changes the rotor to be initialized to a random node number of the cpuset.
Why random as opposed to, say, inherit-rotor-from-parent?

That'd be fine, I bet.

Quoted 27 lines

Index: linux/arch/x86/mm/numa.c
===================================================================

arch/x86/mm/numa.c +12 -0

@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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)

Quoted 8 lines

arch/x86/mm/numa.c const struct cpumask *cpumask_of_node(in · line 84
Quoted 5 lines
arch/x86/mm/numa.c +5 -0
+		bit = bitmap_find_nth_bit(maskp->bits,
+			get_random_int() % w, MAX_NUMNODES);
+	return bit;
+}
+EXPORT_SYMBOL(__node_random);
I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.

I wouldn't worry about that. get_random_int() touches the urandom pool, which will always leave entropy around. Also, Ted and I decided over a year ago that we should drop the whole entropy accounting framework, which I'll get around to some rainy weekend.

Signature · 8 lines

http://selenic.com : development and support for Mercurial and Linux


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Andrew Morton

maintainer

2010-04-28 23:12 UTC #4 lore raw

Quoted 7 lines · On Wed, 28 Apr 2010 18:04:06 -0500 Matt Mackall <[email protected]> wrote:

Quoted 2 lines
I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.
I wouldn't worry about that. get_random_int() touches the urandom pool, which will always leave entropy around. Also, Ted and I decided over a year ago that we should drop the whole entropy accounting framework, which I'll get around to some rainy weekend.

hm, so why does random32() exist? Speed?

Stephen Hemminger

2010-04-28 23:22 UTC #5 lore raw

Quoted 6 lines · On Wed, 28 Apr 2010 16:12:44 -0700 Andrew Morton <[email protected]>…

Quoted 3 lines · On Wed, 28 Apr 2010 18:04:06 -0500 Matt Mackall <[email protected]> wrote:
Quoted 2 lines
I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.

Quoted 6 lines

Quoted 4 lines
I wouldn't worry about that. get_random_int() touches the urandom pool, which will always leave entropy around. Also, Ted and I decided over a year ago that we should drop the whole entropy accounting framework, which I'll get around to some rainy weekend.
hm, so why does random32() exist? Speed?

Because I need a cheap fast pseudo-random source for emulation and it got used for more and more non-cryptographic uses. And like most random generators people keep forgetting that it was not intended for security use.

Matt Mackall

2010-04-28 23:28 UTC #6 lore raw

In reply to Andrew Morton

Quoted 6 lines · Andrew Morton

Quoted 3 lines · On Wed, 28 Apr 2010 18:04:06 -0500 Matt Mackall <[email protected]> wrote:
Quoted 2 lines
I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.

Quoted 6 lines

Quoted 4 lines
I wouldn't worry about that. get_random_int() touches the urandom pool, which will always leave entropy around. Also, Ted and I decided over a year ago that we should drop the whole entropy accounting framework, which I'll get around to some rainy weekend.
hm, so why does random32() exist? Speed?

Yep. There are lots of RNG uses that aren't security sensitive and this is one: the kernel won't be DoSed by an attacker that gets all pages preferentially allocated on one node. Performance will suffer, but it's reasonably bounded.

One of my goals is to call these sorts of trade-offs out in the API, ie:

get_fast_random_u32()
get_fast_random_bytes()
get_secure_random_u32()
get_secure_random_bytes()

Signature · 8 lines

http://selenic.com : development and support for Mercurial and Linux


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Robin Holt

2010-04-29 03:57 UTC #7 lore raw

In reply to Andrew Morton

Quoted 10 lines · Andrew Morton

Quoted 4 lines · On Wed, 28 Apr 2010 10:04:32 -0500 Jack Steiner <[email protected]> wrote:
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.
And, presumably, your secret testcase forks lots of subprocesses which do the file creation?

I think the test case he was using was aim7 or a kernel compile. Anything that opens a lot of small files will quickly deplete node 0.

Quoted 4 lines

Quoted 2 lines
This patch changes the rotor to be initialized to a random node number of the cpuset.
Why random as opposed to, say, inherit-rotor-from-parent?

If I have something like a find ... -exec grep ..., won't the pages be biased towards the nodes adjacent to the parent's rotor values. Maybe I misunderstood Jack's problem, but I believe that was what he was seeing and why he chose random.

I hope I did not misunderstand Jack's problem and mislead this discussion.

Thanks,
Robin Holt

Jack Steiner

author

2010-04-29 20:08 UTC #8 lore raw

In reply to Andrew Morton

Quoted 10 lines · Andrew Morton

Quoted 4 lines · On Wed, 28 Apr 2010 10:04:32 -0500 Jack Steiner <[email protected]> wrote:
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.
And, presumably, your secret testcase forks lots of subprocesses which do the file creation?

We've seen this on several workloads. None were contrived - just standard benchmarks that use tasks/scripts to create a large number of files. I have not looked in detail at the tasks/scripts. It seemed desirable to have each new task start with a random value in the rotor. That would provide
the best randomness.

Quoted 5 lines

Quoted 3 lines
This patch changes the rotor to be initialized to a random node number of the cpuset.
Why random as opposed to, say, inherit-rotor-from-parent?

I was concerned that inherit-from-parant might not be effective if the files were created using a single task that forked child processes to create the files. Each child would inherit the same rotor value.

Quoted 50 lines

Quoted 23 lines

Index: linux/arch/x86/mm/numa.c
===================================================================

arch/x86/mm/numa.c +7 -0

@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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)

arch/x86/mm/numa.c const struct cpumask *cpumask_of_node(in · line 84

Quoted 10 lines

arch/x86/mm/numa.c +10 -0

+{
+	int w, bit = -1;
+
+	w = nodes_weight(*maskp);
+	if (w)
+		bit = bitmap_find_nth_bit(maskp->bits,
+			get_random_int() % w, MAX_NUMNODES);
+	return bit;
+}
+EXPORT_SYMBOL(__node_random);

I suspect random32() would suffice here. It avoids depleting the entropy pool altogether.

Quoted 13 lines

arch/x86/mm/numa.c +13 -0

+
+/**
+ * bitmap_find_nth_bit(buf, ord, bits)
+ *	@buf: pointer to bitmap
+ *	@n: ordinal bit position (n-th set bit, n >= 0)
+ * @nbits: number of bits in the bitmap
+ *
+ * find the Nth bit that is set in the bitmap
+ * Value of @n should be in range 0 <= @n < weight(buf), else
+ * results are undefined.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */

Quoted 8 lines

arch/x86/mm/numa.c
Quoted 5 lines
arch/x86/mm/numa.c +5 -0
+int bitmap_find_nth_bit(const unsigned long *bitmap, int n, int bits)
+{
+	return bitmap_ord_to_pos(bitmap, n, bits);
+}
+EXPORT_SYMBOL(bitmap_find_nth_bit);
This does nothing apart from consume more stack? Better to rename bitmap_ord_to_pos() and export it.

Agree. Not sure why I did it that way. Fixed in next version of the patch.

--- jack

Jack Steiner

author

2010-04-29 20:09 UTC #9 lore raw

In reply to Andrew Morton

This patch changes the rotor to be initialized to a random node number of the cpuset.

NOTE: this patch is on TOP of the previous patch:

	[PATCH] - New round-robin rotor for SLAB allocations
	http://marc.info/?l=linux-mm&m=127231565321947&w=2

Signed-off-by Jack Steiner <[email protected]>

---

V2 - initial patch was generated against the wrong tree. This patch is based on linux-next.

V3 - Eliminate new function bitmap_find_nth_bit(). Rename bitmap_ord_to_pos() and export it.

 arch/x86/mm/numa.c       |   17 +++++++++++++++++
 include/linux/bitmap.h   |    1 +
 include/linux/nodemask.h |    5 +++++
 kernel/fork.c            |    4 ++++
 lib/bitmap.c             |    2 +-
 5 files changed, 28 insertions(+), 1 deletion(-)

arch/x86/mm/numa.c +17 -0

Index: linux/arch/x86/mm/numa.c
===================================================================
@@ -2,6 +2,7 @@
 #include <linux/topology.h>
 #include <linux/module.h>
 #include <linux/bootmem.h>
+#include <linux/random.h>
 
 #ifdef CONFIG_DEBUG_PER_CPU_MAPS
 # define DBG(x...) printk(KERN_DEBUG x)

@@ -65,3 +66,19 @@ const struct cpumask *cpumask_of_node(in
 }
 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);

include/linux/bitmap.h +1 -0

Index: linux/include/linux/bitmap.h
===================================================================
@@ -141,6 +141,7 @@ extern int bitmap_find_free_region(unsig
 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)					\
 (									\

include/linux/nodemask.h +5 -0

Index: linux/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?
  *

@@ -267,6 +269,9 @@ static inline int __first_unset_node(con
 			find_first_zero_bit(maskp->bits, MAX_NUMNODES));
 }
 
+#define node_random(mask) __node_random(&(mask))
+extern int __node_random(const nodemask_t *maskp);
+
 #define NODE_MASK_LAST_WORD BITMAP_LAST_WORD_MASK(MAX_NUMNODES)
 
 #if MAX_NUMNODES <= BITS_PER_LONG

kernel/fork.c +4 -0

Index: linux/kernel/fork.c
===================================================================
@@ -1079,6 +1079,10 @@ static struct task_struct *copy_process(
  	}
 	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

lib/bitmap.c +1 -1

Index: linux/lib/bitmap.c
===================================================================
@@ -672,7 +672,7 @@ static int bitmap_pos_to_ord(const unsig
  *
  * 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;