bitmap onto and fold operators for mempolicy extensions
Subsystems (2)
RFC 1/1 bitmap onto and fold operators for mempolicy extensions
[Beware - never tested, never booted.]
From: Paul Jackson <[email protected]>
The following adds two more bitmap operators, bitmap_onto() and bitmap_fold(), with the usual cpumask and nodemask wrappers.
The bitmap_onto() operator computes one bitmap relative to another. If the n-th bit in the origin mask is set, then the m-th bit of the destination mask will be set, where m is the position of the n-th set bit in the relative mask.
The bitmap_fold() operator folds a bitmap into a second that has bit m set iff the input bitmap has some bit n set, where m == n mod sz, for the specified sz value.
There are two substantive changes between this patch and its predecessor bitmap_relative:
1) Renamed bitmap_relative() to be bitmap_onto().
2) Added bitmap_fold().
The essential motivation for bitmap_onto() is to provide a mechanism for converting a cpuset-relative CPU or Node mask to an absolute mask. Cpuset relative masks are written as if the current task were in a cpuset whose CPUs or Nodes were just the consecutive ones numbered 0..N-1, for some N. The bitmap_onto() operator is provided in anticipation of adding support for the first such cpuset relative mask, by the mbind() and set_mempolicy() system calls, using a planned flag of MPOL_F_RELATIVE_NODES. These bitmap operators (and their nodemask wrappers, in particular) will be used in code that converts the user specified cpuset relative memory policy to a specific system node numbered policy, given the current mems_allowed of the tasks cpuset.
Such cpuset relative mempolicies will address two deficiencies of the existing interface between cpusets and mempolicies:
1) A task cannot at present reliably establish a cpuset relative mempolicy because there is an essential race condition, in that the tasks cpuset may be changed in between the time the task can query its cpuset placement, and the time the task can issue the applicable mbind or set_memplicy system call.
2) A task cannot at present establish what cpuset relative mempolicy it would like to have, if it is in a smaller cpuset than it might have mempolicy preferences for, because the existing interface only allows specifying mempolicies for nodes currently allowed by the cpuset.
Cpuset relative mempolicies are useful for tasks that don't distinguish particularly between one CPU or Node and another, but only between how many of each are allowed, and the proper placement of threads and memory pages on the various CPUs and Nodes available.
The motivation for the added bitmap_fold() can be seen in the following example.
Let's say an application has specified some mempolicies that presume 16 memory nodes, including say a mempolicy that specified MPOL_F_RELATIVE_NODES (cpuset relative) nodes 12-15. Then lets say that application is crammed into a cpuset that only has 8 memory nodes, 0-7. If one just uses bitmap_onto(), this mempolicy, mapped to that cpuset, would ignore the requested relative nodes above 7, leaving it empty of nodes. That's not good; better to fold the higher nodes down, so that some nodes are included in the resulting mapped mempolicy. In this case, the mempolicy nodes 12-15 are taken modulo 8 (the weight of the mems_allowed of the confining cpuset), resulting in a mempolicy specifying nodes 4-7.
--- include/linux/bitmap.h | 6 + include/linux/cpumask.h | 22 ++++++ include/linux/nodemask.h | 22 ++++++ lib/bitmap.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 206 insertions(+), 2 deletions(-)
include/linux/nodemask.h +21 -1
@@ -14,6 +14,8 @@* 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. +* For details of nodes_onto(), see bitmap_onto in lib/bitmap.c. +* For details of nodes_fold(), see bitmap_fold in lib/bitmap.c. * * The available nodemask operations are: *
@@ -55,7 +57,9 @@* 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) +* void nodes_remap(dst, src, old, new) *dst = map(old, new)(src) +* void nodes_onto(dst, orig, relmap) *dst = orig relative to relmap +* void nodes_fold(dst, orig, sz) dst bits = orig bits mod sz * * for_each_node_mask(node, mask) for-loop node over mask *
@@ -326,6 +330,22 @@ static inline void __nodes_remap(nodemasbitmap_remap (dstp->bits, srcp->bits, oldp->bits, newp->bits, nbits); } +#define nodes_onto (dst, orig, relmap) \ + __nodes_onto(&(dst), &(orig), &(relmap), MAX_NUMNODES) +static inline void __nodes_onto (nodemask_t *dstp,const nodemask_t *origp, +const nodemask_t *relmapp,int nbits) +{ +bitmap_onto (dstp->bits, origp->bits, relmapp->bits, nbits); +} + +#define nodes_fold (dst, orig, sz) \ + __nodes_fold(&(dst), &(orig), sz, MAX_NUMNODES) +static inline void __nodes_fold (nodemask_t *dstp,const nodemask_t *origp, +int sz,int nbits) +{ +bitmap_fold (dstp->bits, origp->bits, sz, nbits); +} +#if MAX_NUMNODES >1 #define for_each_node_mask (node, mask) \ for ((node) = first_node(mask); \
include/linux/bitmap.h +6 -0
@@ -46,6 +46,8 @@* 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_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap +* bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz * bitmap_scnprintf(buf, len, src, nbits) Print bitmap src to buf * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
@@ -120,6 +122,10 @@ extern void bitmap_remap(unsigned long * 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 void bitmap_onto (unsigned long *dst,const unsigned long *orig, +const unsigned long *relmap,int bits); +extern void bitmap_fold (unsigned long *dst,const unsigned long *orig, +int sz,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);
include/linux/cpumask.h +21 -1
@@ -14,6 +14,8 @@* 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. +* For details of cpus_onto(), see bitmap_onto in lib/bitmap.c. +* For details of cpus_fold(), see bitmap_fold in lib/bitmap.c. * * The available cpumask operations are: *
@@ -53,7 +55,9 @@* 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) +* void cpus_remap(dst, src, old, new) *dst = map(old, new)(src) +* void cpus_onto(dst, orig, relmap) *dst = orig relative to relmap +* void cpus_fold(dst, orig, sz) dst bits = orig bits mod sz * * for_each_cpu_mask(cpu, mask) for-loop cpu over mask *
@@ -311,6 +315,22 @@ static inline void __cpus_remap(cpumask_bitmap_remap (dstp->bits, srcp->bits, oldp->bits, newp->bits, nbits); } +#define cpus_onto (dst, orig, relmap) \ + __cpus_onto(&(dst), &(orig), &(relmap), NR_CPUS) +static inline void __cpus_onto (cpumask_t *dstp,const cpumask_t *origp, +const cpumask_t *relmapp,int nbits) +{ +bitmap_onto (dstp->bits, origp->bits, relmapp->bits, nbits); +} + +#define cpus_fold (dst, orig, sz) \ + __cpus_fold(&(dst), &(orig), sz, NR_CPUS) +static inline void __cpus_fold (cpumask_t *dstp,const cpumask_t *origp, +int sz,int nbits) +{ +bitmap_fold (dstp->bits, origp->bits, sz, nbits); +} +#if NR_CPUS >1 #define for_each_cpu_mask (cpu, mask) \ for ((cpu) = first_cpu(mask); \
lib/bitmap.c +158 -0
164 lines not on this page · raw message
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Hi Paul,
Quoted 3 lines
The
bitmap_fold()operator folds a bitmap into a second that has bit m set iff the input bitmap has some bit n set, where m == n mod sz, for the specified sz value.
iff?
other portions looks good :)
Thanks!
Quoted 2 lines · KOSAKI-san
iff?
other portions looks good :)
"iff" -- "if and only if"
It is from my days, a long long time ago, as a student of mathematical logic and set theory. I was too lazy to spell that one out. My bad.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.940.382.4214Hi Paul,
Quoted 7 lines
Quoted 2 lines
iff?
other portions looks good :)"iff" -- "if and only if"
It is from my days, a long long time ago, as a student of mathematical logic and set theory. I was too lazy to spell that one out. My bad.
not at all.
I did't know the abbreviation, sorry.
I think your patch has no bug.
Thanks.
- kosaki
Thank-you for the kind and prompt review, kosaki-san.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.940.382.4214Quoted 4 lines · Paul Jackson
Let's say an application has specified some mempolicies that presume 16 memory nodes, including say a mempolicy that specified
MPOL_F_RELATIVE_NODES(cpuset relative) nodes 12-15. Then lets say that application is crammed into a cpuset that only
Quoted 9 lines
has 8 memory nodes, 0-7. If one just uses
bitmap_onto(), this mempolicy, mapped to that cpuset, would ignore the requested relative nodes above 7, leaving it empty of nodes. That's not good; better to fold the higher nodes down, so that some nodes are included in the resulting mapped mempolicy. In this case, the mempolicy nodes 12-15 are taken modulo 8 (the weight of themems_allowedof the confining cpuset), resulting in a mempolicy specifying nodes 4-7.
So what is the MPOL_F_RELATIVE_NODES behavior? Is it a combination of nodes_onto() and nodes_fold()?
In your example, the only way we know to use nodes_fold() is if the resultant of nodes_onto() has a weight of 0. An MPOL_F_RELATIVE_NODES nodemask for 4-6, for example, works fine in your case of a cpuset with memory nodes 0-7 and no fold is required.
So it's easy enough to do this:
case MPOL_INTERLEAVE:
if (flags & MPOL_F_RELATIVE_NODES) {
nodes_onto(pol->v.nodes, pol->user_nodemask,
cpuset_context_nmask);
if (nodes_empty(pol->v.nodes))
nodes_fold(pol->v.nodes,
pol->user_nodemask,
nodes_weight(cpuset_context_nmask));
} else {
...
}
break;But what if we require a combination? Say the user asked for a policy of MPOL_INTERLEAVE | MPOL_F_RELATIVE_NODES over nodes 4-8 in a cpuset constrained to mems 0-7? Should the resultant be 0,4-7 (combination of nodes_onto() and nodes_fold()) or simply be 4-7 (just nodes_onto())?
And what if the MPOL_INTERLEAVE | MPOL_F_RELATIVE_NODES nodemask is 0,4-8 in the same cpuset constrained to mems 0-7? Should the resultant be
- 0,4-7 (nodes_onto() and nodes_fold()),
- 0,4-7 (just nodes_onto()), or
- 0-1,4-7 (nodes_onto(), nodes_fold(), and shift)?
The last option, 0-1,4-7, is the only one that preserves the same weight as the relative nodemask.
David
Quoted 2 lines · David
So what is the
MPOL_F_RELATIVE_NODESbehavior? Is it a combination ofnodes_onto()andnodes_fold()?
MPOL_F_RELATIVE_NODES should always combination of nodes_onto() and nodes_fold().
The reason I say that is consistency with the end cases. That is, we need fold in the case that no requested nodes have numbers smaller than the weight of the cpusets mems_allowed. At the opposite extreme, when -all- requested node numbers are smaller than the weight of mems_allowed, fold has no affect, so it's fine to use there. And for the in between cases, when some requested nodes are smaller and some not, fold is one possible reasonable answer. So use it everywhere for consistency.
Quoted 6 lines
So it's easy enough to do this:
case MPOL_INTERLEAVE: if (flags & MPOL_F_RELATIVE_NODES) { nodes_onto(pol->v.nodes, pol->user_nodemask, cpuset_context_nmask); if (nodes_empty(pol->v.nodes))
I hate any more special cases than I have to have -- so not that way.
Quoted 4 lines
But what if we require a combination? Say the user asked for a policy of
MPOL_INTERLEAVE|MPOL_F_RELATIVE_NODESover nodes 4-8 in a cpuset constrained to mems 0-7? Should the resultant be 0,4-7 (combination ofnodes_onto()andnodes_fold()) or simply be 4-7 (justnodes_onto())?
All fold, all the time ;). So this one should be 0,4-7.
Quoted 11 lines
And what if the
MPOL_INTERLEAVE|MPOL_F_RELATIVE_NODESnodemask is 0,4-8 in the same cpuset constrained to mems 0-7? Should the resultant be- 0,4-7 (
nodes_onto()andnodes_fold()),- 0,4-7 (just
nodes_onto()), or- 0-1,4-7 (
nodes_onto(),nodes_fold(), and shift)?The last option, 0-1,4-7, is the only one that preserves the same weight as the relative nodemask.
Again, 0,4-7.
Weight preservation is not a goal here, and would require special cases.
If someone crams a five pound cpuset relative memory policy into a two poound cpuset, they will likely loose weight. What matters in that case is that things plod along without too much distress, and that when the job is restored to a proper size cpuset, its memory policies recover their full health.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.940.382.4214