aboutsummaryrefslogtreecommitdiffstats
path: root/lib/bitmap.c
diff options
context:
space:
mode:
authorPaul Jackson <pj@sgi.com>2008-04-28 05:12:29 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2008-04-28 11:58:19 -0400
commit7ea931c9fc80c4d0a4306c30ec92eb0f1d922a0b (patch)
tree4f2c85d658c75e8679e01943e3e95866b3729b54 /lib/bitmap.c
parentf5b087b52f1710eb0bf15a2d2b030c51a6a1ca9e (diff)
mempolicy: add bitmap_onto() and bitmap_fold() operations
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. Signed-off-by: Paul Jackson <pj@sgi.com> Signed-off-by: David Rientjes <rientjes@google.com> Cc: Christoph Lameter <clameter@sgi.com> Cc: Andi Kleen <ak@suse.de> Cc: Mel Gorman <mel@csn.ul.ie> Cc: Lee Schermerhorn <lee.schermerhorn@hp.com> Cc: <kosaki.motohiro@jp.fujitsu.com> Cc: <ray-lk@madrabbit.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/bitmap.c')
-rw-r--r--lib/bitmap.c158
1 files changed, 158 insertions, 0 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c
index a6939e18d7bb..c4cb48f77f0c 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -714,6 +714,164 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
714} 714}
715EXPORT_SYMBOL(bitmap_bitremap); 715EXPORT_SYMBOL(bitmap_bitremap);
716 716
717/**
718 * bitmap_onto - translate one bitmap relative to another
719 * @dst: resulting translated bitmap
720 * @orig: original untranslated bitmap
721 * @relmap: bitmap relative to which translated
722 * @bits: number of bits in each of these bitmaps
723 *
724 * Set the n-th bit of @dst iff there exists some m such that the
725 * n-th bit of @relmap is set, the m-th bit of @orig is set, and
726 * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
727 * (If you understood the previous sentence the first time your
728 * read it, you're overqualified for your current job.)
729 *
730 * In other words, @orig is mapped onto (surjectively) @dst,
731 * using the the map { <n, m> | the n-th bit of @relmap is the
732 * m-th set bit of @relmap }.
733 *
734 * Any set bits in @orig above bit number W, where W is the
735 * weight of (number of set bits in) @relmap are mapped nowhere.
736 * In particular, if for all bits m set in @orig, m >= W, then
737 * @dst will end up empty. In situations where the possibility
738 * of such an empty result is not desired, one way to avoid it is
739 * to use the bitmap_fold() operator, below, to first fold the
740 * @orig bitmap over itself so that all its set bits x are in the
741 * range 0 <= x < W. The bitmap_fold() operator does this by
742 * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
743 *
744 * Example [1] for bitmap_onto():
745 * Let's say @relmap has bits 30-39 set, and @orig has bits
746 * 1, 3, 5, 7, 9 and 11 set. Then on return from this routine,
747 * @dst will have bits 31, 33, 35, 37 and 39 set.
748 *
749 * When bit 0 is set in @orig, it means turn on the bit in
750 * @dst corresponding to whatever is the first bit (if any)
751 * that is turned on in @relmap. Since bit 0 was off in the
752 * above example, we leave off that bit (bit 30) in @dst.
753 *
754 * When bit 1 is set in @orig (as in the above example), it
755 * means turn on the bit in @dst corresponding to whatever
756 * is the second bit that is turned on in @relmap. The second
757 * bit in @relmap that was turned on in the above example was
758 * bit 31, so we turned on bit 31 in @dst.
759 *
760 * Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
761 * because they were the 4th, 6th, 8th and 10th set bits
762 * set in @relmap, and the 4th, 6th, 8th and 10th bits of
763 * @orig (i.e. bits 3, 5, 7 and 9) were also set.
764 *
765 * When bit 11 is set in @orig, it means turn on the bit in
766 * @dst corresponding to whatever is the twelth bit that is
767 * turned on in @relmap. In the above example, there were
768 * only ten bits turned on in @relmap (30..39), so that bit
769 * 11 was set in @orig had no affect on @dst.
770 *
771 * Example [2] for bitmap_fold() + bitmap_onto():
772 * Let's say @relmap has these ten bits set:
773 * 40 41 42 43 45 48 53 61 74 95
774 * (for the curious, that's 40 plus the first ten terms of the
775 * Fibonacci sequence.)
776 *
777 * Further lets say we use the following code, invoking
778 * bitmap_fold() then bitmap_onto, as suggested above to
779 * avoid the possitility of an empty @dst result:
780 *
781 * unsigned long *tmp; // a temporary bitmap's bits
782 *
783 * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
784 * bitmap_onto(dst, tmp, relmap, bits);
785 *
786 * Then this table shows what various values of @dst would be, for
787 * various @orig's. I list the zero-based positions of each set bit.
788 * The tmp column shows the intermediate result, as computed by
789 * using bitmap_fold() to fold the @orig bitmap modulo ten
790 * (the weight of @relmap).
791 *
792 * @orig tmp @dst
793 * 0 0 40
794 * 1 1 41
795 * 9 9 95
796 * 10 0 40 (*)
797 * 1 3 5 7 1 3 5 7 41 43 48 61
798 * 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45
799 * 0 9 18 27 0 9 8 7 40 61 74 95
800 * 0 10 20 30 0 40
801 * 0 11 22 33 0 1 2 3 40 41 42 43
802 * 0 12 24 36 0 2 4 6 40 42 45 53
803 * 78 102 211 1 2 8 41 42 74 (*)
804 *
805 * (*) For these marked lines, if we hadn't first done bitmap_fold()
806 * into tmp, then the @dst result would have been empty.
807 *
808 * If either of @orig or @relmap is empty (no set bits), then @dst
809 * will be returned empty.
810 *
811 * If (as explained above) the only set bits in @orig are in positions
812 * m where m >= W, (where W is the weight of @relmap) then @dst will
813 * once again be returned empty.
814 *
815 * All bits in @dst not set by the above rule are cleared.
816 */
817void bitmap_onto(unsigned long *dst, const unsigned long *orig,
818 const unsigned long *relmap, int bits)
819{
820 int n, m; /* same meaning as in above comment */
821
822 if (dst == orig) /* following doesn't handle inplace mappings */
823 return;
824 bitmap_zero(dst, bits);
825
826 /*
827 * The following code is a more efficient, but less
828 * obvious, equivalent to the loop:
829 * for (m = 0; m < bitmap_weight(relmap, bits); m++) {
830 * n = bitmap_ord_to_pos(orig, m, bits);
831 * if (test_bit(m, orig))
832 * set_bit(n, dst);
833 * }
834 */
835
836 m = 0;
837 for (n = find_first_bit(relmap, bits);
838 n < bits;
839 n = find_next_bit(relmap, bits, n + 1)) {
840 /* m == bitmap_pos_to_ord(relmap, n, bits) */
841 if (test_bit(m, orig))
842 set_bit(n, dst);
843 m++;
844 }
845}
846EXPORT_SYMBOL(bitmap_onto);
847
848/**
849 * bitmap_fold - fold larger bitmap into smaller, modulo specified size
850 * @dst: resulting smaller bitmap
851 * @orig: original larger bitmap
852 * @sz: specified size
853 * @bits: number of bits in each of these bitmaps
854 *
855 * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
856 * Clear all other bits in @dst. See further the comment and
857 * Example [2] for bitmap_onto() for why and how to use this.
858 */
859void bitmap_fold(unsigned long *dst, const unsigned long *orig,
860 int sz, int bits)
861{
862 int oldbit;
863
864 if (dst == orig) /* following doesn't handle inplace mappings */
865 return;
866 bitmap_zero(dst, bits);
867
868 for (oldbit = find_first_bit(orig, bits);
869 oldbit < bits;
870 oldbit = find_next_bit(orig, bits, oldbit + 1))
871 set_bit(oldbit % sz, dst);
872}
873EXPORT_SYMBOL(bitmap_fold);
874
717/* 875/*
718 * Common code for bitmap_*_region() routines. 876 * Common code for bitmap_*_region() routines.
719 * bitmap: array of unsigned longs corresponding to the bitmap 877 * bitmap: array of unsigned longs corresponding to the bitmap