cpuset bitmap and mask remap operators

In the forthcoming task migration support, a key calculation will be mapping cpu and node numbers from the old set to the new set while preserving cpuset-relative offset.

For example, if a task and its pages on nodes 8-11 are being migrated to nodes 24-27, then pages on node 9 (the 2nd node in the old set) should be moved to node 25 (the 2nd node in the new set.)

As with other bitmap operations, the proper way to code this is to provide the underlying calculation in lib/bitmap.c, and then to provide the usual cpumask and nodemask wrappers.

This patch provides that. These operations are termed 'remap' operations. Both remapping a single bit and a set of bits is supported.

---

 include/linux/bitmap.h   |    6 +
 include/linux/cpumask.h  |   20 +++++
 include/linux/nodemask.h |   20 +++++
 lib/bitmap.c             |  166 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 212 insertions(+)

@@ -40,6 +40,8 @@
  * bitmap_weight(src, nbits)			Hamming Weight: number set bits
  * 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)
+ * bitmap_bitremap(oldbit, old, new, nbits)	newbit = map(old, new)(oldbit)
  * bitmap_scnprintf(buf, len, src, nbits)	Print bitmap src to buf
  * bitmap_parse(ubuf, ulen, dst, nbits)		Parse bitmap dst from user buf
  * bitmap_scnlistprintf(buf, len, src, nbits)	Print bitmap src as list to buf

@@ -104,6 +106,10 @@ extern int bitmap_scnlistprintf(char *bu
 			const unsigned long *src, int nbits);
 extern int bitmap_parselist(const char *buf, unsigned long *maskp,
 			int nmaskbits);
+extern void bitmap_remap(const unsigned long *dst, unsigned long *src,
+		const unsigned long *old, const unsigned long *new, int bits);
+extern int bitmap_bitremap(int oldbit,
+		const unsigned long *old, const unsigned long *new, int bits);
 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);

@@ -12,6 +12,8 @@
  * see bitmap_scnprintf() and bitmap_parse() in lib/bitmap.c.
  * For details of cpulist_scnprintf() and cpulist_parse(), see
  * bitmap_scnlistprintf() and bitmap_parselist(), also in bitmap.c.
+ * For details of cpu_remap(), see bitmap_bitremap in lib/bitmap.c
+ * For details of cpus_remap(), see bitmap_remap in lib/bitmap.c.
  *
  * The available cpumask operations are:
  *

@@ -50,6 +52,8 @@
  * int cpumask_parse(ubuf, ulen, mask)	Parse ascii string as cpumask
  * int cpulist_scnprintf(buf, len, mask) Format cpumask as list for printing
  * int cpulist_parse(buf, map)		Parse ascii string as cpulist
+ * int cpu_remap(oldbit, old, new)	newbit = map(old, new)(oldbit)
+ * int cpus_remap(dst, src, old, new)	*dst = map(old, new)(src)
  *
  * for_each_cpu_mask(cpu, mask)		for-loop cpu over mask
  *

@@ -294,6 +298,22 @@ static inline int __cpulist_parse(const 
 	return bitmap_parselist(buf, dstp->bits, nbits);
 }
 
+#define cpu_remap(oldbit, old, new) \
+		__cpu_remap((oldbit), &(old), &(new), NR_CPUS)
+static inline int __cpu_remap(int oldbit,
+		const cpumask_t *oldp, const cpumask_t *newp, int nbits)
+{
+	return bitmap_bitremap(oldbit, oldp->bits, newp->bits, nbits);
+}
+
+#define cpus_remap(dst, src, old, new) \
+		__cpus_remap(&(dst), &(src), &(old), &(new), NR_CPUS)
+static inline void __cpus_remap(const cpumask_t *dstp, cpumask_t *srcp,
+		const cpumask_t *oldp, const cpumask_t *newp, int nbits)
+{
+	bitmap_remap(dstp->bits, srcp->bits, oldp->bits, newp->bits, nbits);
+}
+
 #if NR_CPUS > 1
 #define for_each_cpu_mask(cpu, mask)		\
 	for ((cpu) = first_cpu(mask);		\

@@ -12,6 +12,8 @@
  * see bitmap_scnprintf() and bitmap_parse() in lib/bitmap.c.
  * For details of nodelist_scnprintf() and nodelist_parse(), see
  * bitmap_scnlistprintf() and bitmap_parselist(), also in bitmap.c.
+ * For details of node_remap(), see bitmap_bitremap in lib/bitmap.c.
+ * For details of nodes_remap(), see bitmap_remap in lib/bitmap.c.
  *
  * The available nodemask operations are:
  *

@@ -52,6 +54,8 @@
  * int nodemask_parse(ubuf, ulen, mask)	Parse ascii string as nodemask
  * int nodelist_scnprintf(buf, len, mask) Format nodemask as list for printing
  * int nodelist_parse(buf, map)		Parse ascii string as nodelist
+ * int node_remap(oldbit, old, new)	newbit = map(old, new)(oldbit)
+ * int nodes_remap(dst, src, old, new)	*dst = map(old, new)(dst)
  *
  * for_each_node_mask(node, mask)	for-loop node over mask
  *

@@ -307,6 +311,22 @@ static inline int __nodelist_parse(const
 	return bitmap_parselist(buf, dstp->bits, nbits);
 }
 
+#define node_remap(oldbit, old, new) \
+		__node_remap((oldbit), &(old), &(new), MAX_NUMNODES)
+static inline int __node_remap(int oldbit,
+		const nodemask_t *oldp, const nodemask_t *newp, int nbits)
+{
+	return bitmap_bitremap(oldbit, oldp->bits, newp->bits, nbits);
+}
+
+#define nodes_remap(dst, src, old, new) \
+		__nodes_remap(&(dst), &(src), &(old), &(new), MAX_NUMNODES)
+static inline void __nodes_remap(const nodemask_t *dstp, nodemask_t *srcp,
+		const nodemask_t *oldp, const nodemask_t *newp, int nbits)
+{
+	bitmap_remap(dstp->bits, srcp->bits, oldp->bits, newp->bits, nbits);
+}
+
 #if MAX_NUMNODES > 1
 #define for_each_node_mask(node, mask)			\
 	for ((node) = first_node(mask);			\

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

This patch automatically updates a tasks NUMA mempolicy when its cpuset memory placement changes. It does so within the context of the task, without any need to support low level external mempolicy manipulation.

If a system is not using cpusets, or if running on a system with just the root (all-encompassing) cpuset, then this remap is a no-op. Only when a task is moved between cpusets, or a cpusets memory placement is changed does the following apply. Otherwise, the main routine below, rebind_policy() is not even called.

When mixing cpusets, scheduler affinity, and NUMA mempolicies, the essential role of cpusets is to place jobs (several related tasks) on a set of CPUs and Memory Nodes, the essential role of sched_setaffinity is to manage a jobs processor placement within its allowed cpuset, and the essential role of NUMA mempolicy (mbind, set_mempolicy) is to manage a jobs memory placement within its allowed cpuset.

However, CPU affinity and NUMA memory placement are managed within the kernel using absolute system wide numbering, not cpuset relative numbering.

This is ok until a job is migrated to a different cpuset, or what's the same, a jobs cpuset is moved to different CPUs and Memory Nodes.

Then the CPU affinity and NUMA memory placement of the tasks in the job need to be updated, to preserve their cpuset-relative position. This can be done for CPU affinity using sched_setaffinity() from user code, as one task can modify anothers CPU affinity. This cannot be done from an external task for NUMA memory placement, as that can only be modified in the context of the task using it.

However, it easy enough to remap a tasks NUMA mempolicy automatically when a task is migrated, using the existing cpuset mechanism to trigger a refresh of a tasks memory placement after its cpuset has changed. All that is needed is the old and new nodemask, and notice to the task that it needs to rebind its mempolicy. The tasks mems_allowed has the old mask, the tasks cpuset has the new mask, and the existing cpuset_update_current_mems_allowed() mechanism provides the notice. The bitmap/cpumask/nodemask remap operators provide the cpuset relative calculations.

This patch leaves open a couple of issues:

1) Updating vma and shmfs/tmpfs/hugetlbfs memory policies:

These mempolicies may reference nodes outside of those allowed to the current task by its cpuset. Tasks are migrated as part of jobs, which reside on what might be several cpusets in a subtree. When such a job is migrated, all NUMA memory policy references to nodes within that cpuset subtree should be translated, and references to any nodes outside that subtree should be left untouched. A future patch will provide the cpuset mechanism needed to mark such subtrees. With that patch, we will be able to correctly migrate these other memory policies across a job migration.

2) Updating cpuset, affinity and memory policies in user space:

This is harder. Any placement state stored in user space using system-wide numbering will be invalidated across a migration. More work will be required to provide user code with a migration-safe means to manage its cpuset relative placement, while preserving the current API's that pass system wide numbers, not cpuset relative numbers across the kernel-user boundary.

---

 include/linux/mempolicy.h |    6 ++++
 kernel/cpuset.c           |    4 ++
 mm/mempolicy.c            |   64 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 74 insertions(+)

@@ -155,6 +155,7 @@ struct mempolicy *get_vma_policy(struct 
 
 extern void numa_default_policy(void);
 extern void numa_policy_init(void);
+extern void numa_policy_rebind(const nodemask_t *old, const nodemask_t *new);
 extern struct mempolicy default_policy;
 
 #else

@@ -227,6 +228,11 @@ static inline void numa_default_policy(v
 {
 }
 
+static inline void numa_policy_rebind(const nodemask_t *old,
+					const nodemask_t *new)
+{
+}
+
 #endif /* CONFIG_NUMA */
 #endif /* __KERNEL__ */
 

@@ -32,6 +32,7 @@
 #include <linux/kernel.h>
 #include <linux/kmod.h>
 #include <linux/list.h>
+#include <linux/mempolicy.h>
 #include <linux/mm.h>
 #include <linux/module.h>
 #include <linux/mount.h>

@@ -600,6 +601,7 @@ static void refresh_mems(void)
 
 	if (current->cpuset_mems_generation != my_cpusets_mem_gen) {
 		struct cpuset *cs;
+		nodemask_t oldmem = current->mems_allowed;
 
 		down(&callback_sem);
 		task_lock(current);

@@ -608,6 +610,8 @@ static void refresh_mems(void)
 		current->cpuset_mems_generation = cs->mems_generation;
 		task_unlock(current);
 		up(&callback_sem);
+		if (!nodes_equal(oldmem, current->mems_allowed))
+			numa_policy_rebind(&oldmem, &current->mems_allowed);
 	}
 }
 

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

I was just copying Andi's coding style for these cases, with this BUG() if no policy matched. When in Rome, do as the Romans.

Eh ... that entire routine still fits on a page of my screen. I'm not sure that adding a helper function would clarify the code any.

Thanks for looking at it. If you're pretty sure I should change one of the above, squeek a little louder.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

I really just meant it was hard to read having two braces at the same level. This was due to the extra block inside of the switch() for the 'case MPOL_BIND:'. Not a huge deal, but it did cause me a bit of a brain fault for a moment.

-- Dave

Ah - yes. That.

Such is life.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

What's the reason for the wrapper macro?

+EXPORT_SYMBOL(bitmap_bitremap);

Is that deliberately not EXPORT_SYMBOL_GPL?

Most all the nodemask/cpumask operators are like that. It allows writing *mask code as if masks were pass by value (which is how the vast majority of kernel hackers, working on systems with one-word masks, think of them), while actually passing by reference, to avoid unnecessary stack copies of multiword masks.

It's not deliberate that I am aware of.

But it does seem to be the common practice ....

All the bitmap routines are that way - no GPL. In fact it seems that almost all the EXPORT_SYMBOLS in the lib/*.c routines are that way - 12 with GPL and 174 without GPL, or some such. The only lib/*.c GPL exports are in lib/klist.c and lib/kobject_uevent.c.

Is this bad?

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

hm. That hides what's really going on from the programmer.

Oh well - you're the only guy who dinks with that stuff anyway ;)

Ah, the bitmap library - sorry I thought it was in the cpuset code.

Making the bitmap library non-GPL makes sense I guess.

Halloween comes a week early to the Morton household. The patch from hell, circa April 2004, lives on to haunt Andrew <grin>.

By the time we (wli, rusty, colpatch, ...) incorporated the following various constraints on these cpumask/nodemask macros, we were fortunate to only violate the "obvious to the programmer" constraint on the implementation internals:
- near perfect code gen on small systems (1 word masks)
- near perfect code gen on large systems (multiword masks)
- type checking on arguments
- keep the existing macro-style calling conventions:
cpus_and(result, input1, input2)
- a single bitmap internal implementation - the rest just wrappers
- dramatic shinkage of kernel source devoted to this stuff
- reduction in kernel text size across all architectures.

Probably it is best that we not ask too many questions at this time ;).

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401