Subversion Repositories Kolibri OS

Rev

Rev 6082 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * lib/bitmap.c
  3.  * Helper functions for bitmap.h.
  4.  *
  5.  * This source code is licensed under the GNU General Public License,
  6.  * Version 2.  See the file COPYING for more details.
  7.  */
  8. #include <syscall.h>
  9. #include <linux/export.h>
  10. #include <linux/thread_info.h>
  11. #include <linux/ctype.h>
  12. #include <linux/errno.h>
  13. #include <linux/bitmap.h>
  14. #include <linux/bitops.h>
  15. #include <linux/bug.h>
  16. #include <linux/kernel.h>
  17. #include <linux/string.h>
  18.  
  19. #include <asm/page.h>
  20. //#include <asm/uaccess.h>
  21.  
  22. /*
  23.  * bitmaps provide an array of bits, implemented using an an
  24.  * array of unsigned longs.  The number of valid bits in a
  25.  * given bitmap does _not_ need to be an exact multiple of
  26.  * BITS_PER_LONG.
  27.  *
  28.  * The possible unused bits in the last, partially used word
  29.  * of a bitmap are 'don't care'.  The implementation makes
  30.  * no particular effort to keep them zero.  It ensures that
  31.  * their value will not affect the results of any operation.
  32.  * The bitmap operations that return Boolean (bitmap_empty,
  33.  * for example) or scalar (bitmap_weight, for example) results
  34.  * carefully filter out these unused bits from impacting their
  35.  * results.
  36.  *
  37.  * These operations actually hold to a slightly stronger rule:
  38.  * if you don't input any bitmaps to these ops that have some
  39.  * unused bits set, then they won't output any set unused bits
  40.  * in output bitmaps.
  41.  *
  42.  * The byte ordering of bitmaps is more natural on little
  43.  * endian architectures.  See the big-endian headers
  44.  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  45.  * for the best explanations of this ordering.
  46.  */
  47.  
  48. int __bitmap_equal(const unsigned long *bitmap1,
  49.                 const unsigned long *bitmap2, unsigned int bits)
  50. {
  51.         unsigned int k, lim = bits/BITS_PER_LONG;
  52.         for (k = 0; k < lim; ++k)
  53.                 if (bitmap1[k] != bitmap2[k])
  54.                         return 0;
  55.  
  56.         if (bits % BITS_PER_LONG)
  57.                 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  58.                         return 0;
  59.  
  60.         return 1;
  61. }
  62. EXPORT_SYMBOL(__bitmap_equal);
  63.  
  64. void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
  65. {
  66.         unsigned int k, lim = bits/BITS_PER_LONG;
  67.         for (k = 0; k < lim; ++k)
  68.                 dst[k] = ~src[k];
  69.  
  70.         if (bits % BITS_PER_LONG)
  71.                 dst[k] = ~src[k];
  72. }
  73. EXPORT_SYMBOL(__bitmap_complement);
  74.  
  75. /**
  76.  * __bitmap_shift_right - logical right shift of the bits in a bitmap
  77.  *   @dst : destination bitmap
  78.  *   @src : source bitmap
  79.  *   @shift : shift by this many bits
  80.  *   @nbits : bitmap size, in bits
  81.  *
  82.  * Shifting right (dividing) means moving bits in the MS -> LS bit
  83.  * direction.  Zeros are fed into the vacated MS positions and the
  84.  * LS bits shifted off the bottom are lost.
  85.  */
  86. void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
  87.                         unsigned shift, unsigned nbits)
  88. {
  89.         unsigned k, lim = BITS_TO_LONGS(nbits);
  90.         unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
  91.         unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
  92.         for (k = 0; off + k < lim; ++k) {
  93.                 unsigned long upper, lower;
  94.  
  95.                 /*
  96.                  * If shift is not word aligned, take lower rem bits of
  97.                  * word above and make them the top rem bits of result.
  98.                  */
  99.                 if (!rem || off + k + 1 >= lim)
  100.                         upper = 0;
  101.                 else {
  102.                         upper = src[off + k + 1];
  103.                         if (off + k + 1 == lim - 1)
  104.                                 upper &= mask;
  105.                         upper <<= (BITS_PER_LONG - rem);
  106.                 }
  107.                 lower = src[off + k];
  108.                 if (off + k == lim - 1)
  109.                         lower &= mask;
  110.                 lower >>= rem;
  111.                 dst[k] = lower | upper;
  112.         }
  113.         if (off)
  114.                 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
  115. }
  116. EXPORT_SYMBOL(__bitmap_shift_right);
  117.  
  118.  
  119. /**
  120.  * __bitmap_shift_left - logical left shift of the bits in a bitmap
  121.  *   @dst : destination bitmap
  122.  *   @src : source bitmap
  123.  *   @shift : shift by this many bits
  124.  *   @nbits : bitmap size, in bits
  125.  *
  126.  * Shifting left (multiplying) means moving bits in the LS -> MS
  127.  * direction.  Zeros are fed into the vacated LS bit positions
  128.  * and those MS bits shifted off the top are lost.
  129.  */
  130.  
  131. void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
  132.                         unsigned int shift, unsigned int nbits)
  133. {
  134.         int k;
  135.         unsigned int lim = BITS_TO_LONGS(nbits);
  136.         unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
  137.         for (k = lim - off - 1; k >= 0; --k) {
  138.                 unsigned long upper, lower;
  139.  
  140.                 /*
  141.                  * If shift is not word aligned, take upper rem bits of
  142.                  * word below and make them the bottom rem bits of result.
  143.                  */
  144.                 if (rem && k > 0)
  145.                         lower = src[k - 1] >> (BITS_PER_LONG - rem);
  146.                 else
  147.                         lower = 0;
  148.                 upper = src[k] << rem;
  149.                 dst[k + off] = lower | upper;
  150.         }
  151.         if (off)
  152.                 memset(dst, 0, off*sizeof(unsigned long));
  153. }
  154. EXPORT_SYMBOL(__bitmap_shift_left);
  155.  
  156. int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  157.                                 const unsigned long *bitmap2, unsigned int bits)
  158. {
  159.         unsigned int k;
  160.         unsigned int lim = bits/BITS_PER_LONG;
  161.         unsigned long result = 0;
  162.  
  163.         for (k = 0; k < lim; k++)
  164.                 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
  165.         if (bits % BITS_PER_LONG)
  166.                 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
  167.                            BITMAP_LAST_WORD_MASK(bits));
  168.         return result != 0;
  169. }
  170. EXPORT_SYMBOL(__bitmap_and);
  171.  
  172. void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  173.                                 const unsigned long *bitmap2, unsigned int bits)
  174. {
  175.         unsigned int k;
  176.         unsigned int nr = BITS_TO_LONGS(bits);
  177.  
  178.         for (k = 0; k < nr; k++)
  179.                 dst[k] = bitmap1[k] | bitmap2[k];
  180. }
  181. EXPORT_SYMBOL(__bitmap_or);
  182.  
  183. void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  184.                                 const unsigned long *bitmap2, unsigned int bits)
  185. {
  186.         unsigned int k;
  187.         unsigned int nr = BITS_TO_LONGS(bits);
  188.  
  189.         for (k = 0; k < nr; k++)
  190.                 dst[k] = bitmap1[k] ^ bitmap2[k];
  191. }
  192. EXPORT_SYMBOL(__bitmap_xor);
  193.  
  194. int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  195.                                 const unsigned long *bitmap2, unsigned int bits)
  196. {
  197.         unsigned int k;
  198.         unsigned int lim = bits/BITS_PER_LONG;
  199.         unsigned long result = 0;
  200.  
  201.         for (k = 0; k < lim; k++)
  202.                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
  203.         if (bits % BITS_PER_LONG)
  204.                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
  205.                            BITMAP_LAST_WORD_MASK(bits));
  206.         return result != 0;
  207. }
  208. EXPORT_SYMBOL(__bitmap_andnot);
  209.  
  210. int __bitmap_intersects(const unsigned long *bitmap1,
  211.                         const unsigned long *bitmap2, unsigned int bits)
  212. {
  213.         unsigned int k, lim = bits/BITS_PER_LONG;
  214.         for (k = 0; k < lim; ++k)
  215.                 if (bitmap1[k] & bitmap2[k])
  216.                         return 1;
  217.  
  218.         if (bits % BITS_PER_LONG)
  219.                 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  220.                         return 1;
  221.         return 0;
  222. }
  223. EXPORT_SYMBOL(__bitmap_intersects);
  224.  
  225. int __bitmap_subset(const unsigned long *bitmap1,
  226.                     const unsigned long *bitmap2, unsigned int bits)
  227. {
  228.         unsigned int k, lim = bits/BITS_PER_LONG;
  229.         for (k = 0; k < lim; ++k)
  230.                 if (bitmap1[k] & ~bitmap2[k])
  231.                         return 0;
  232.  
  233.         if (bits % BITS_PER_LONG)
  234.                 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  235.                         return 0;
  236.         return 1;
  237. }
  238. EXPORT_SYMBOL(__bitmap_subset);
  239.  
  240. int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
  241. {
  242.         unsigned int k, lim = bits/BITS_PER_LONG;
  243.         int w = 0;
  244.  
  245.         for (k = 0; k < lim; k++)
  246.                 w += hweight_long(bitmap[k]);
  247.  
  248.         if (bits % BITS_PER_LONG)
  249.                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  250.  
  251.         return w;
  252. }
  253. EXPORT_SYMBOL(__bitmap_weight);
  254.  
  255. void bitmap_set(unsigned long *map, unsigned int start, int len)
  256. {
  257.         unsigned long *p = map + BIT_WORD(start);
  258.         const unsigned int size = start + len;
  259.         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  260.         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  261.  
  262.         while (len - bits_to_set >= 0) {
  263.                 *p |= mask_to_set;
  264.                 len -= bits_to_set;
  265.                 bits_to_set = BITS_PER_LONG;
  266.                 mask_to_set = ~0UL;
  267.                 p++;
  268.         }
  269.         if (len) {
  270.                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
  271.                 *p |= mask_to_set;
  272.         }
  273. }
  274. EXPORT_SYMBOL(bitmap_set);
  275.  
  276. void bitmap_clear(unsigned long *map, unsigned int start, int len)
  277. {
  278.         unsigned long *p = map + BIT_WORD(start);
  279.         const unsigned int size = start + len;
  280.         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
  281.         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
  282.  
  283.         while (len - bits_to_clear >= 0) {
  284.                 *p &= ~mask_to_clear;
  285.                 len -= bits_to_clear;
  286.                 bits_to_clear = BITS_PER_LONG;
  287.                 mask_to_clear = ~0UL;
  288.                 p++;
  289.         }
  290.         if (len) {
  291.                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
  292.                 *p &= ~mask_to_clear;
  293.         }
  294. }
  295. EXPORT_SYMBOL(bitmap_clear);
  296.  
  297. /**
  298.  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
  299.  * @map: The address to base the search on
  300.  * @size: The bitmap size in bits
  301.  * @start: The bitnumber to start searching at
  302.  * @nr: The number of zeroed bits we're looking for
  303.  * @align_mask: Alignment mask for zero area
  304.  * @align_offset: Alignment offset for zero area.
  305.  *
  306.  * The @align_mask should be one less than a power of 2; the effect is that
  307.  * the bit offset of all zero areas this function finds plus @align_offset
  308.  * is multiple of that power of 2.
  309.  */
  310. unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
  311.                                              unsigned long size,
  312.                                              unsigned long start,
  313.                                              unsigned int nr,
  314.                                              unsigned long align_mask,
  315.                                              unsigned long align_offset)
  316. {
  317.         unsigned long index, end, i;
  318. again:
  319.         index = find_next_zero_bit(map, size, start);
  320.  
  321.         /* Align allocation */
  322.         index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
  323.  
  324.         end = index + nr;
  325.         if (end > size)
  326.                 return end;
  327.         i = find_next_bit(map, end, index);
  328.         if (i < end) {
  329.                 start = i + 1;
  330.                 goto again;
  331.         }
  332.         return index;
  333. }
  334. EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
  335.  
  336. /*
  337.  * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
  338.  * second version by Paul Jackson, third by Joe Korty.
  339.  */
  340.  
  341. #define CHUNKSZ                         32
  342. #define nbits_to_hold_value(val)        fls(val)
  343. #define BASEDEC 10              /* fancier cpuset lists input in decimal */
  344.  
  345.  
  346.  
  347.  
  348.  
  349. /**
  350.  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
  351.  *      @buf: pointer to a bitmap
  352.  *      @pos: a bit position in @buf (0 <= @pos < @nbits)
  353.  *      @nbits: number of valid bit positions in @buf
  354.  *
  355.  * Map the bit at position @pos in @buf (of length @nbits) to the
  356.  * ordinal of which set bit it is.  If it is not set or if @pos
  357.  * is not a valid bit position, map to -1.
  358.  *
  359.  * If for example, just bits 4 through 7 are set in @buf, then @pos
  360.  * values 4 through 7 will get mapped to 0 through 3, respectively,
  361.  * and other @pos values will get mapped to -1.  When @pos value 7
  362.  * gets mapped to (returns) @ord value 3 in this example, that means
  363.  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
  364.  *
  365.  * The bit positions 0 through @bits are valid positions in @buf.
  366.  */
  367. static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
  368. {
  369.         if (pos >= nbits || !test_bit(pos, buf))
  370.                 return -1;
  371.  
  372.         return __bitmap_weight(buf, pos);
  373. }
  374.  
  375. /**
  376.  * bitmap_ord_to_pos - find position of n-th set bit in bitmap
  377.  *      @buf: pointer to bitmap
  378.  *      @ord: ordinal bit position (n-th set bit, n >= 0)
  379.  *      @nbits: number of valid bit positions in @buf
  380.  *
  381.  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
  382.  * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
  383.  * >= weight(buf), returns @nbits.
  384.  *
  385.  * If for example, just bits 4 through 7 are set in @buf, then @ord
  386.  * values 0 through 3 will get mapped to 4 through 7, respectively,
  387.  * and all other @ord values returns @nbits.  When @ord value 3
  388.  * gets mapped to (returns) @pos value 7 in this example, that means
  389.  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
  390.  *
  391.  * The bit positions 0 through @nbits-1 are valid positions in @buf.
  392.  */
  393. unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
  394. {
  395.         unsigned int pos;
  396.  
  397.         for (pos = find_first_bit(buf, nbits);
  398.              pos < nbits && ord;
  399.              pos = find_next_bit(buf, nbits, pos + 1))
  400.                 ord--;
  401.  
  402.         return pos;
  403. }
  404.  
  405. /**
  406.  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
  407.  *      @dst: remapped result
  408.  *      @src: subset to be remapped
  409.  *      @old: defines domain of map
  410.  *      @new: defines range of map
  411.  *      @nbits: number of bits in each of these bitmaps
  412.  *
  413.  * Let @old and @new define a mapping of bit positions, such that
  414.  * whatever position is held by the n-th set bit in @old is mapped
  415.  * to the n-th set bit in @new.  In the more general case, allowing
  416.  * for the possibility that the weight 'w' of @new is less than the
  417.  * weight of @old, map the position of the n-th set bit in @old to
  418.  * the position of the m-th set bit in @new, where m == n % w.
  419.  *
  420.  * If either of the @old and @new bitmaps are empty, or if @src and
  421.  * @dst point to the same location, then this routine copies @src
  422.  * to @dst.
  423.  *
  424.  * The positions of unset bits in @old are mapped to themselves
  425.  * (the identify map).
  426.  *
  427.  * Apply the above specified mapping to @src, placing the result in
  428.  * @dst, clearing any bits previously set in @dst.
  429.  *
  430.  * For example, lets say that @old has bits 4 through 7 set, and
  431.  * @new has bits 12 through 15 set.  This defines the mapping of bit
  432.  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
  433.  * bit positions unchanged.  So if say @src comes into this routine
  434.  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
  435.  * 13 and 15 set.
  436.  */
  437. void bitmap_remap(unsigned long *dst, const unsigned long *src,
  438.                 const unsigned long *old, const unsigned long *new,
  439.                 unsigned int nbits)
  440. {
  441.         unsigned int oldbit, w;
  442.  
  443.         if (dst == src)         /* following doesn't handle inplace remaps */
  444.                 return;
  445.         bitmap_zero(dst, nbits);
  446.  
  447.         w = bitmap_weight(new, nbits);
  448.         for_each_set_bit(oldbit, src, nbits) {
  449.                 int n = bitmap_pos_to_ord(old, oldbit, nbits);
  450.  
  451.                 if (n < 0 || w == 0)
  452.                         set_bit(oldbit, dst);   /* identity map */
  453.                 else
  454.                         set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
  455.         }
  456. }
  457. EXPORT_SYMBOL(bitmap_remap);
  458.  
  459. /**
  460.  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
  461.  *      @oldbit: bit position to be mapped
  462.  *      @old: defines domain of map
  463.  *      @new: defines range of map
  464.  *      @bits: number of bits in each of these bitmaps
  465.  *
  466.  * Let @old and @new define a mapping of bit positions, such that
  467.  * whatever position is held by the n-th set bit in @old is mapped
  468.  * to the n-th set bit in @new.  In the more general case, allowing
  469.  * for the possibility that the weight 'w' of @new is less than the
  470.  * weight of @old, map the position of the n-th set bit in @old to
  471.  * the position of the m-th set bit in @new, where m == n % w.
  472.  *
  473.  * The positions of unset bits in @old are mapped to themselves
  474.  * (the identify map).
  475.  *
  476.  * Apply the above specified mapping to bit position @oldbit, returning
  477.  * the new bit position.
  478.  *
  479.  * For example, lets say that @old has bits 4 through 7 set, and
  480.  * @new has bits 12 through 15 set.  This defines the mapping of bit
  481.  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
  482.  * bit positions unchanged.  So if say @oldbit is 5, then this routine
  483.  * returns 13.
  484.  */
  485. int bitmap_bitremap(int oldbit, const unsigned long *old,
  486.                                 const unsigned long *new, int bits)
  487. {
  488.         int w = bitmap_weight(new, bits);
  489.         int n = bitmap_pos_to_ord(old, oldbit, bits);
  490.         if (n < 0 || w == 0)
  491.                 return oldbit;
  492.         else
  493.                 return bitmap_ord_to_pos(new, n % w, bits);
  494. }
  495. EXPORT_SYMBOL(bitmap_bitremap);
  496.  
  497. /**
  498.  * bitmap_onto - translate one bitmap relative to another
  499.  *      @dst: resulting translated bitmap
  500.  *      @orig: original untranslated bitmap
  501.  *      @relmap: bitmap relative to which translated
  502.  *      @bits: number of bits in each of these bitmaps
  503.  *
  504.  * Set the n-th bit of @dst iff there exists some m such that the
  505.  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
  506.  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
  507.  * (If you understood the previous sentence the first time your
  508.  * read it, you're overqualified for your current job.)
  509.  *
  510.  * In other words, @orig is mapped onto (surjectively) @dst,
  511.  * using the map { <n, m> | the n-th bit of @relmap is the
  512.  * m-th set bit of @relmap }.
  513.  *
  514.  * Any set bits in @orig above bit number W, where W is the
  515.  * weight of (number of set bits in) @relmap are mapped nowhere.
  516.  * In particular, if for all bits m set in @orig, m >= W, then
  517.  * @dst will end up empty.  In situations where the possibility
  518.  * of such an empty result is not desired, one way to avoid it is
  519.  * to use the bitmap_fold() operator, below, to first fold the
  520.  * @orig bitmap over itself so that all its set bits x are in the
  521.  * range 0 <= x < W.  The bitmap_fold() operator does this by
  522.  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
  523.  *
  524.  * Example [1] for bitmap_onto():
  525.  *  Let's say @relmap has bits 30-39 set, and @orig has bits
  526.  *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
  527.  *  @dst will have bits 31, 33, 35, 37 and 39 set.
  528.  *
  529.  *  When bit 0 is set in @orig, it means turn on the bit in
  530.  *  @dst corresponding to whatever is the first bit (if any)
  531.  *  that is turned on in @relmap.  Since bit 0 was off in the
  532.  *  above example, we leave off that bit (bit 30) in @dst.
  533.  *
  534.  *  When bit 1 is set in @orig (as in the above example), it
  535.  *  means turn on the bit in @dst corresponding to whatever
  536.  *  is the second bit that is turned on in @relmap.  The second
  537.  *  bit in @relmap that was turned on in the above example was
  538.  *  bit 31, so we turned on bit 31 in @dst.
  539.  *
  540.  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
  541.  *  because they were the 4th, 6th, 8th and 10th set bits
  542.  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
  543.  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
  544.  *
  545.  *  When bit 11 is set in @orig, it means turn on the bit in
  546.  *  @dst corresponding to whatever is the twelfth bit that is
  547.  *  turned on in @relmap.  In the above example, there were
  548.  *  only ten bits turned on in @relmap (30..39), so that bit
  549.  *  11 was set in @orig had no affect on @dst.
  550.  *
  551.  * Example [2] for bitmap_fold() + bitmap_onto():
  552.  *  Let's say @relmap has these ten bits set:
  553.  *              40 41 42 43 45 48 53 61 74 95
  554.  *  (for the curious, that's 40 plus the first ten terms of the
  555.  *  Fibonacci sequence.)
  556.  *
  557.  *  Further lets say we use the following code, invoking
  558.  *  bitmap_fold() then bitmap_onto, as suggested above to
  559.  *  avoid the possibility of an empty @dst result:
  560.  *
  561.  *      unsigned long *tmp;     // a temporary bitmap's bits
  562.  *
  563.  *      bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
  564.  *      bitmap_onto(dst, tmp, relmap, bits);
  565.  *
  566.  *  Then this table shows what various values of @dst would be, for
  567.  *  various @orig's.  I list the zero-based positions of each set bit.
  568.  *  The tmp column shows the intermediate result, as computed by
  569.  *  using bitmap_fold() to fold the @orig bitmap modulo ten
  570.  *  (the weight of @relmap).
  571.  *
  572.  *      @orig           tmp            @dst
  573.  *      0                0             40
  574.  *      1                1             41
  575.  *      9                9             95
  576.  *      10               0             40 (*)
  577.  *      1 3 5 7          1 3 5 7       41 43 48 61
  578.  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
  579.  *      0 9 18 27        0 9 8 7       40 61 74 95
  580.  *      0 10 20 30       0             40
  581.  *      0 11 22 33       0 1 2 3       40 41 42 43
  582.  *      0 12 24 36       0 2 4 6       40 42 45 53
  583.  *      78 102 211       1 2 8         41 42 74 (*)
  584.  *
  585.  * (*) For these marked lines, if we hadn't first done bitmap_fold()
  586.  *     into tmp, then the @dst result would have been empty.
  587.  *
  588.  * If either of @orig or @relmap is empty (no set bits), then @dst
  589.  * will be returned empty.
  590.  *
  591.  * If (as explained above) the only set bits in @orig are in positions
  592.  * m where m >= W, (where W is the weight of @relmap) then @dst will
  593.  * once again be returned empty.
  594.  *
  595.  * All bits in @dst not set by the above rule are cleared.
  596.  */
  597. void bitmap_onto(unsigned long *dst, const unsigned long *orig,
  598.                         const unsigned long *relmap, unsigned int bits)
  599. {
  600.         unsigned int n, m;      /* same meaning as in above comment */
  601.  
  602.         if (dst == orig)        /* following doesn't handle inplace mappings */
  603.                 return;
  604.         bitmap_zero(dst, bits);
  605.  
  606.         /*
  607.          * The following code is a more efficient, but less
  608.          * obvious, equivalent to the loop:
  609.          *      for (m = 0; m < bitmap_weight(relmap, bits); m++) {
  610.          *              n = bitmap_ord_to_pos(orig, m, bits);
  611.          *              if (test_bit(m, orig))
  612.          *                      set_bit(n, dst);
  613.          *      }
  614.          */
  615.  
  616.         m = 0;
  617.         for_each_set_bit(n, relmap, bits) {
  618.                 /* m == bitmap_pos_to_ord(relmap, n, bits) */
  619.                 if (test_bit(m, orig))
  620.                         set_bit(n, dst);
  621.                 m++;
  622.         }
  623. }
  624. EXPORT_SYMBOL(bitmap_onto);
  625.  
  626. /**
  627.  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
  628.  *      @dst: resulting smaller bitmap
  629.  *      @orig: original larger bitmap
  630.  *      @sz: specified size
  631.  *      @nbits: number of bits in each of these bitmaps
  632.  *
  633.  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
  634.  * Clear all other bits in @dst.  See further the comment and
  635.  * Example [2] for bitmap_onto() for why and how to use this.
  636.  */
  637. void bitmap_fold(unsigned long *dst, const unsigned long *orig,
  638.                         unsigned int sz, unsigned int nbits)
  639. {
  640.         unsigned int oldbit;
  641.  
  642.         if (dst == orig)        /* following doesn't handle inplace mappings */
  643.                 return;
  644.         bitmap_zero(dst, nbits);
  645.  
  646.         for_each_set_bit(oldbit, orig, nbits)
  647.                 set_bit(oldbit % sz, dst);
  648. }
  649. EXPORT_SYMBOL(bitmap_fold);
  650.  
  651. /*
  652.  * Common code for bitmap_*_region() routines.
  653.  *      bitmap: array of unsigned longs corresponding to the bitmap
  654.  *      pos: the beginning of the region
  655.  *      order: region size (log base 2 of number of bits)
  656.  *      reg_op: operation(s) to perform on that region of bitmap
  657.  *
  658.  * Can set, verify and/or release a region of bits in a bitmap,
  659.  * depending on which combination of REG_OP_* flag bits is set.
  660.  *
  661.  * A region of a bitmap is a sequence of bits in the bitmap, of
  662.  * some size '1 << order' (a power of two), aligned to that same
  663.  * '1 << order' power of two.
  664.  *
  665.  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
  666.  * Returns 0 in all other cases and reg_ops.
  667.  */
  668.  
  669. enum {
  670.         REG_OP_ISFREE,          /* true if region is all zero bits */
  671.         REG_OP_ALLOC,           /* set all bits in region */
  672.         REG_OP_RELEASE,         /* clear all bits in region */
  673. };
  674.  
  675. static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
  676. {
  677.         int nbits_reg;          /* number of bits in region */
  678.         int index;              /* index first long of region in bitmap */
  679.         int offset;             /* bit offset region in bitmap[index] */
  680.         int nlongs_reg;         /* num longs spanned by region in bitmap */
  681.         int nbitsinlong;        /* num bits of region in each spanned long */
  682.         unsigned long mask;     /* bitmask for one long of region */
  683.         int i;                  /* scans bitmap by longs */
  684.         int ret = 0;            /* return value */
  685.  
  686.         /*
  687.          * Either nlongs_reg == 1 (for small orders that fit in one long)
  688.          * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
  689.          */
  690.         nbits_reg = 1 << order;
  691.         index = pos / BITS_PER_LONG;
  692.         offset = pos - (index * BITS_PER_LONG);
  693.         nlongs_reg = BITS_TO_LONGS(nbits_reg);
  694.         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
  695.  
  696.         /*
  697.          * Can't do "mask = (1UL << nbitsinlong) - 1", as that
  698.          * overflows if nbitsinlong == BITS_PER_LONG.
  699.          */
  700.         mask = (1UL << (nbitsinlong - 1));
  701.         mask += mask - 1;
  702.         mask <<= offset;
  703.  
  704.         switch (reg_op) {
  705.         case REG_OP_ISFREE:
  706.                 for (i = 0; i < nlongs_reg; i++) {
  707.                         if (bitmap[index + i] & mask)
  708.                                 goto done;
  709.                 }
  710.                 ret = 1;        /* all bits in region free (zero) */
  711.                 break;
  712.  
  713.         case REG_OP_ALLOC:
  714.                 for (i = 0; i < nlongs_reg; i++)
  715.                         bitmap[index + i] |= mask;
  716.                 break;
  717.  
  718.         case REG_OP_RELEASE:
  719.                 for (i = 0; i < nlongs_reg; i++)
  720.                         bitmap[index + i] &= ~mask;
  721.                 break;
  722.         }
  723. done:
  724.         return ret;
  725. }
  726.  
  727. /**
  728.  * bitmap_find_free_region - find a contiguous aligned mem region
  729.  *      @bitmap: array of unsigned longs corresponding to the bitmap
  730.  *      @bits: number of bits in the bitmap
  731.  *      @order: region size (log base 2 of number of bits) to find
  732.  *
  733.  * Find a region of free (zero) bits in a @bitmap of @bits bits and
  734.  * allocate them (set them to one).  Only consider regions of length
  735.  * a power (@order) of two, aligned to that power of two, which
  736.  * makes the search algorithm much faster.
  737.  *
  738.  * Return the bit offset in bitmap of the allocated region,
  739.  * or -errno on failure.
  740.  */
  741. int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
  742. {
  743.         unsigned int pos, end;          /* scans bitmap by regions of size order */
  744.  
  745.         for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
  746.                 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
  747.                         continue;
  748.                 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
  749.                 return pos;
  750.         }
  751.         return -ENOMEM;
  752. }
  753. EXPORT_SYMBOL(bitmap_find_free_region);
  754.  
  755. /**
  756.  * bitmap_release_region - release allocated bitmap region
  757.  *      @bitmap: array of unsigned longs corresponding to the bitmap
  758.  *      @pos: beginning of bit region to release
  759.  *      @order: region size (log base 2 of number of bits) to release
  760.  *
  761.  * This is the complement to __bitmap_find_free_region() and releases
  762.  * the found region (by clearing it in the bitmap).
  763.  *
  764.  * No return value.
  765.  */
  766. void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
  767. {
  768.         __reg_op(bitmap, pos, order, REG_OP_RELEASE);
  769. }
  770. EXPORT_SYMBOL(bitmap_release_region);
  771.  
  772. /**
  773.  * bitmap_allocate_region - allocate bitmap region
  774.  *      @bitmap: array of unsigned longs corresponding to the bitmap
  775.  *      @pos: beginning of bit region to allocate
  776.  *      @order: region size (log base 2 of number of bits) to allocate
  777.  *
  778.  * Allocate (set bits in) a specified region of a bitmap.
  779.  *
  780.  * Return 0 on success, or %-EBUSY if specified region wasn't
  781.  * free (not all bits were zero).
  782.  */
  783. int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
  784. {
  785.         if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
  786.                 return -EBUSY;
  787.         return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
  788. }
  789. EXPORT_SYMBOL(bitmap_allocate_region);
  790.  
  791. /**
  792.  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
  793.  * @dst:   destination buffer
  794.  * @src:   bitmap to copy
  795.  * @nbits: number of bits in the bitmap
  796.  *
  797.  * Require nbits % BITS_PER_LONG == 0.
  798.  */
  799. #ifdef __BIG_ENDIAN
  800. void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
  801. {
  802.         unsigned int i;
  803.  
  804.         for (i = 0; i < nbits/BITS_PER_LONG; i++) {
  805.                 if (BITS_PER_LONG == 64)
  806.                         dst[i] = cpu_to_le64(src[i]);
  807.                 else
  808.                         dst[i] = cpu_to_le32(src[i]);
  809.         }
  810. }
  811. EXPORT_SYMBOL(bitmap_copy_le);
  812. #endif
  813.