40b0b3f8fb2d8 (Thomas Gleixner 2019-06-03 07:44:46 +0200 1) // SPDX-License-Identifier: GPL-2.0-only
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 2) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 3) * lib/bitmap.c
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 4) * Helper functions for bitmap.h.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 5) */
c13656b904b61 (Bartosz Golaszewski 2021-03-15 10:13:55 +0100 6)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7) #include <linux/bitmap.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 8) #include <linux/bitops.h>
50af5ead3b44c (Paul Gortmaker 2012-01-20 18:35:53 -0500 9) #include <linux/bug.h>
c13656b904b61 (Bartosz Golaszewski 2021-03-15 10:13:55 +0100 10) #include <linux/ctype.h>
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 11) #include <linux/device.h>
c13656b904b61 (Bartosz Golaszewski 2021-03-15 10:13:55 +0100 12) #include <linux/errno.h>
c13656b904b61 (Bartosz Golaszewski 2021-03-15 10:13:55 +0100 13) #include <linux/export.h>
e52bc7c28ac9f (David Decotigny 2016-02-19 09:23:59 -0500 14) #include <linux/kernel.h>
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 15) #include <linux/mm.h>
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 16) #include <linux/slab.h>
e52bc7c28ac9f (David Decotigny 2016-02-19 09:23:59 -0500 17) #include <linux/string.h>
c13656b904b61 (Bartosz Golaszewski 2021-03-15 10:13:55 +0100 18) #include <linux/thread_info.h>
13d4ea097d18b (Andy Lutomirski 2016-07-14 13:22:57 -0700 19) #include <linux/uaccess.h>
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 20)
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 21) #include <asm/page.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 22)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 23) #include "kstrtox.h"
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 24)
7d7363e403ce9 (Randy Dunlap 2017-10-16 16:32:51 -0700 25) /**
7d7363e403ce9 (Randy Dunlap 2017-10-16 16:32:51 -0700 26) * DOC: bitmap introduction
7d7363e403ce9 (Randy Dunlap 2017-10-16 16:32:51 -0700 27) *
197d6c1dde4e1 (Randy Dunlap 2020-10-15 20:10:45 -0700 28) * bitmaps provide an array of bits, implemented using an
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 29) * array of unsigned longs. The number of valid bits in a
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 30) * given bitmap does _not_ need to be an exact multiple of
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 31) * BITS_PER_LONG.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 32) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 33) * The possible unused bits in the last, partially used word
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 34) * of a bitmap are 'don't care'. The implementation makes
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 35) * no particular effort to keep them zero. It ensures that
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 36) * their value will not affect the results of any operation.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 37) * The bitmap operations that return Boolean (bitmap_empty,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 38) * for example) or scalar (bitmap_weight, for example) results
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 39) * carefully filter out these unused bits from impacting their
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 40) * results.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 41) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 42) * The byte ordering of bitmaps is more natural on little
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 43) * endian architectures. See the big-endian headers
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 44) * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 45) * for the best explanations of this ordering.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 46) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 47)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 48) int __bitmap_equal(const unsigned long *bitmap1,
5e068069319a9 (Rasmus Villemoes 2014-08-06 16:09:53 -0700 49) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 50) {
5e068069319a9 (Rasmus Villemoes 2014-08-06 16:09:53 -0700 51) unsigned int k, lim = bits/BITS_PER_LONG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 52) for (k = 0; k < lim; ++k)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 53) if (bitmap1[k] != bitmap2[k])
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 54) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 55)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 56) if (bits % BITS_PER_LONG)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 57) if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 58) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 59)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 60) return 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 61) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 62) EXPORT_SYMBOL(__bitmap_equal);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 63)
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 64) bool __bitmap_or_equal(const unsigned long *bitmap1,
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 65) const unsigned long *bitmap2,
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 66) const unsigned long *bitmap3,
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 67) unsigned int bits)
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 68) {
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 69) unsigned int k, lim = bits / BITS_PER_LONG;
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 70) unsigned long tmp;
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 71)
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 72) for (k = 0; k < lim; ++k) {
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 73) if ((bitmap1[k] | bitmap2[k]) != bitmap3[k])
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 74) return false;
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 75) }
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 76)
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 77) if (!(bits % BITS_PER_LONG))
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 78) return true;
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 79)
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 80) tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 81) return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 82) }
b9fa6442f7043 (Thomas Gleixner 2019-07-22 20:47:24 +0200 83)
3d6684f4e6a46 (Rasmus Villemoes 2014-08-06 16:09:55 -0700 84) void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 85) {
ca1250bbd4e0b (Yury Norov 2018-06-07 17:10:41 -0700 86) unsigned int k, lim = BITS_TO_LONGS(bits);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 87) for (k = 0; k < lim; ++k)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 88) dst[k] = ~src[k];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 89) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 90) EXPORT_SYMBOL(__bitmap_complement);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 91)
72fd4a35a8243 (Robert P. J. Day 2007-02-10 01:45:59 -0800 92) /**
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 93) * __bitmap_shift_right - logical right shift of the bits in a bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 94) * @dst : destination bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 95) * @src : source bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 96) * @shift : shift by this many bits
2fbad29917c98 (Rasmus Villemoes 2015-02-13 14:36:02 -0800 97) * @nbits : bitmap size, in bits
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 98) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 99) * Shifting right (dividing) means moving bits in the MS -> LS bit
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 100) * direction. Zeros are fed into the vacated MS positions and the
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 101) * LS bits shifted off the bottom are lost.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 102) */
2fbad29917c98 (Rasmus Villemoes 2015-02-13 14:36:02 -0800 103) void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
2fbad29917c98 (Rasmus Villemoes 2015-02-13 14:36:02 -0800 104) unsigned shift, unsigned nbits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 105) {
cfac1d080a005 (Rasmus Villemoes 2015-02-13 14:36:10 -0800 106) unsigned k, lim = BITS_TO_LONGS(nbits);
2fbad29917c98 (Rasmus Villemoes 2015-02-13 14:36:02 -0800 107) unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
cfac1d080a005 (Rasmus Villemoes 2015-02-13 14:36:10 -0800 108) unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 109) for (k = 0; off + k < lim; ++k) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 110) unsigned long upper, lower;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 111)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 112) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 113) * If shift is not word aligned, take lower rem bits of
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 114) * word above and make them the top rem bits of result.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 115) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 116) if (!rem || off + k + 1 >= lim)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 117) upper = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 118) else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 119) upper = src[off + k + 1];
cfac1d080a005 (Rasmus Villemoes 2015-02-13 14:36:10 -0800 120) if (off + k + 1 == lim - 1)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 121) upper &= mask;
9d8a6b2a02c5f (Rasmus Villemoes 2015-02-13 14:36:05 -0800 122) upper <<= (BITS_PER_LONG - rem);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 123) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 124) lower = src[off + k];
cfac1d080a005 (Rasmus Villemoes 2015-02-13 14:36:10 -0800 125) if (off + k == lim - 1)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 126) lower &= mask;
9d8a6b2a02c5f (Rasmus Villemoes 2015-02-13 14:36:05 -0800 127) lower >>= rem;
9d8a6b2a02c5f (Rasmus Villemoes 2015-02-13 14:36:05 -0800 128) dst[k] = lower | upper;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 129) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 130) if (off)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 131) memset(&dst[lim - off], 0, off*sizeof(unsigned long));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 132) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 133) EXPORT_SYMBOL(__bitmap_shift_right);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 135)
72fd4a35a8243 (Robert P. J. Day 2007-02-10 01:45:59 -0800 136) /**
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137) * __bitmap_shift_left - logical left shift of the bits in a bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 138) * @dst : destination bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 139) * @src : source bitmap
05fb6bf0b2955 (Randy Dunlap 2007-02-28 20:12:13 -0800 140) * @shift : shift by this many bits
dba94c2553da1 (Rasmus Villemoes 2015-02-13 14:36:13 -0800 141) * @nbits : bitmap size, in bits
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 142) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143) * Shifting left (multiplying) means moving bits in the LS -> MS
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 144) * direction. Zeros are fed into the vacated LS bit positions
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 145) * and those MS bits shifted off the top are lost.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 146) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 147)
dba94c2553da1 (Rasmus Villemoes 2015-02-13 14:36:13 -0800 148) void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
dba94c2553da1 (Rasmus Villemoes 2015-02-13 14:36:13 -0800 149) unsigned int shift, unsigned int nbits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 150) {
dba94c2553da1 (Rasmus Villemoes 2015-02-13 14:36:13 -0800 151) int k;
7f590657937f1 (Rasmus Villemoes 2015-02-13 14:36:19 -0800 152) unsigned int lim = BITS_TO_LONGS(nbits);
dba94c2553da1 (Rasmus Villemoes 2015-02-13 14:36:13 -0800 153) unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154) for (k = lim - off - 1; k >= 0; --k) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 155) unsigned long upper, lower;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 157) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 158) * If shift is not word aligned, take upper rem bits of
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) * word below and make them the bottom rem bits of result.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 161) if (rem && k > 0)
6d874eca65956 (Rasmus Villemoes 2015-02-13 14:36:16 -0800 162) lower = src[k - 1] >> (BITS_PER_LONG - rem);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 163) else
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164) lower = 0;
7f590657937f1 (Rasmus Villemoes 2015-02-13 14:36:19 -0800 165) upper = src[k] << rem;
6d874eca65956 (Rasmus Villemoes 2015-02-13 14:36:16 -0800 166) dst[k + off] = lower | upper;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) if (off)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) memset(dst, 0, off*sizeof(unsigned long));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171) EXPORT_SYMBOL(__bitmap_shift_left);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 173) /**
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 174) * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 175) * @dst: destination bitmap, might overlap with src
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 176) * @src: source bitmap
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 177) * @first: start bit of region to be removed
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 178) * @cut: number of bits to remove
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 179) * @nbits: bitmap size, in bits
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 180) *
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 181) * Set the n-th bit of @dst iff the n-th bit of @src is set and
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 182) * n is less than @first, or the m-th bit of @src is set for any
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 183) * m such that @first <= n < nbits, and m = n + @cut.
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 184) *
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 185) * In pictures, example for a big-endian 32-bit architecture:
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 186) *
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 187) * The @src bitmap is::
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 188) *
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 189) * 31 63
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 190) * | |
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 191) * 10000000 11000001 11110010 00010101 10000000 11000001 01110010 00010101
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 192) * | | | |
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 193) * 16 14 0 32
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 194) *
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 195) * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 196) *
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 197) * 31 63
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 198) * | |
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 199) * 10110000 00011000 00110010 00010101 00010000 00011000 00101110 01000010
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 200) * | | |
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 201) * 14 (bit 17 0 32
4642289b5f660 (Mauro Carvalho Chehab 2020-04-14 18:48:59 +0200 202) * from @src)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 203) *
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 204) * Note that @dst and @src might overlap partially or entirely.
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 205) *
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 206) * This is implemented in the obvious way, with a shift and carry
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 207) * step for each moved bit. Optimisation is left as an exercise
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 208) * for the compiler.
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 209) */
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 210) void bitmap_cut(unsigned long *dst, const unsigned long *src,
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 211) unsigned int first, unsigned int cut, unsigned int nbits)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 212) {
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 213) unsigned int len = BITS_TO_LONGS(nbits);
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 214) unsigned long keep = 0, carry;
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 215) int i;
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 216)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 217) if (first % BITS_PER_LONG) {
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 218) keep = src[first / BITS_PER_LONG] &
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 219) (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 220) }
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 221)
5959f829a93c1 (Stefano Brivio 2020-08-11 18:34:29 -0700 222) memmove(dst, src, len * sizeof(*dst));
5959f829a93c1 (Stefano Brivio 2020-08-11 18:34:29 -0700 223)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 224) while (cut--) {
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 225) for (i = first / BITS_PER_LONG; i < len; i++) {
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 226) if (i < len - 1)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 227) carry = dst[i + 1] & 1UL;
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 228) else
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 229) carry = 0;
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 230)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 231) dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 232) }
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 233) }
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 234)
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 235) dst[first / BITS_PER_LONG] &= ~0UL << (first % BITS_PER_LONG);
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 236) dst[first / BITS_PER_LONG] |= keep;
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 237) }
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 238) EXPORT_SYMBOL(bitmap_cut);
2092767168f06 (Stefano Brivio 2020-01-22 00:17:54 +0100 239)
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 240) int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 241) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 242) {
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 243) unsigned int k;
7e5f97d1927f4 (Rasmus Villemoes 2014-08-06 16:10:22 -0700 244) unsigned int lim = bits/BITS_PER_LONG;
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 245) unsigned long result = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 246)
7e5f97d1927f4 (Rasmus Villemoes 2014-08-06 16:10:22 -0700 247) for (k = 0; k < lim; k++)
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 248) result |= (dst[k] = bitmap1[k] & bitmap2[k]);
7e5f97d1927f4 (Rasmus Villemoes 2014-08-06 16:10:22 -0700 249) if (bits % BITS_PER_LONG)
7e5f97d1927f4 (Rasmus Villemoes 2014-08-06 16:10:22 -0700 250) result |= (dst[k] = bitmap1[k] & bitmap2[k] &
7e5f97d1927f4 (Rasmus Villemoes 2014-08-06 16:10:22 -0700 251) BITMAP_LAST_WORD_MASK(bits));
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 252) return result != 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 253) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 254) EXPORT_SYMBOL(__bitmap_and);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 255)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 256) void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 257) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 258) {
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 259) unsigned int k;
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 260) unsigned int nr = BITS_TO_LONGS(bits);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 261)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 262) for (k = 0; k < nr; k++)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 263) dst[k] = bitmap1[k] | bitmap2[k];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 264) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 265) EXPORT_SYMBOL(__bitmap_or);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 266)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 267) void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 268) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 269) {
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 270) unsigned int k;
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 271) unsigned int nr = BITS_TO_LONGS(bits);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 272)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 273) for (k = 0; k < nr; k++)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 274) dst[k] = bitmap1[k] ^ bitmap2[k];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 275) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 276) EXPORT_SYMBOL(__bitmap_xor);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 277)
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 278) int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 279) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 280) {
2f9305eb31097 (Rasmus Villemoes 2014-08-06 16:09:59 -0700 281) unsigned int k;
74e765319084b (Rasmus Villemoes 2014-08-06 16:10:24 -0700 282) unsigned int lim = bits/BITS_PER_LONG;
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 283) unsigned long result = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 284)
74e765319084b (Rasmus Villemoes 2014-08-06 16:10:24 -0700 285) for (k = 0; k < lim; k++)
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 286) result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
74e765319084b (Rasmus Villemoes 2014-08-06 16:10:24 -0700 287) if (bits % BITS_PER_LONG)
74e765319084b (Rasmus Villemoes 2014-08-06 16:10:24 -0700 288) result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
74e765319084b (Rasmus Villemoes 2014-08-06 16:10:24 -0700 289) BITMAP_LAST_WORD_MASK(bits));
f4b0373b26567 (Linus Torvalds 2009-08-21 09:26:15 -0700 290) return result != 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 291) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 292) EXPORT_SYMBOL(__bitmap_andnot);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 293)
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 294) void __bitmap_replace(unsigned long *dst,
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 295) const unsigned long *old, const unsigned long *new,
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 296) const unsigned long *mask, unsigned int nbits)
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 297) {
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 298) unsigned int k;
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 299) unsigned int nr = BITS_TO_LONGS(nbits);
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 300)
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 301) for (k = 0; k < nr; k++)
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 302) dst[k] = (old[k] & ~mask[k]) | (new[k] & mask[k]);
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 303) }
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 304) EXPORT_SYMBOL(__bitmap_replace);
30544ed5de431 (Andy Shevchenko 2019-12-04 16:53:26 -0800 305)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 306) int __bitmap_intersects(const unsigned long *bitmap1,
6dfe9799c2a03 (Rasmus Villemoes 2014-08-06 16:10:01 -0700 307) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 308) {
6dfe9799c2a03 (Rasmus Villemoes 2014-08-06 16:10:01 -0700 309) unsigned int k, lim = bits/BITS_PER_LONG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 310) for (k = 0; k < lim; ++k)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 311) if (bitmap1[k] & bitmap2[k])
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 312) return 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 313)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 314) if (bits % BITS_PER_LONG)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 315) if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 316) return 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 317) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 318) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 319) EXPORT_SYMBOL(__bitmap_intersects);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 320)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 321) int __bitmap_subset(const unsigned long *bitmap1,
5be20213e8555 (Rasmus Villemoes 2014-08-06 16:10:03 -0700 322) const unsigned long *bitmap2, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 323) {
5be20213e8555 (Rasmus Villemoes 2014-08-06 16:10:03 -0700 324) unsigned int k, lim = bits/BITS_PER_LONG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 325) for (k = 0; k < lim; ++k)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 326) if (bitmap1[k] & ~bitmap2[k])
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 327) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 328)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 329) if (bits % BITS_PER_LONG)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 330) if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 331) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 332) return 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 333) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 334) EXPORT_SYMBOL(__bitmap_subset);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 335)
877d9f3b63ac2 (Rasmus Villemoes 2014-08-06 16:10:05 -0700 336) int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 337) {
877d9f3b63ac2 (Rasmus Villemoes 2014-08-06 16:10:05 -0700 338) unsigned int k, lim = bits/BITS_PER_LONG;
877d9f3b63ac2 (Rasmus Villemoes 2014-08-06 16:10:05 -0700 339) int w = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 340)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 341) for (k = 0; k < lim; k++)
37d54111c133b (Akinobu Mita 2006-03-26 01:39:56 -0800 342) w += hweight_long(bitmap[k]);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 343)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 344) if (bits % BITS_PER_LONG)
37d54111c133b (Akinobu Mita 2006-03-26 01:39:56 -0800 345) w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 346)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 347) return w;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 348) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 349) EXPORT_SYMBOL(__bitmap_weight);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 350)
e5af323c9badd (Matthew Wilcox 2017-07-10 15:51:29 -0700 351) void __bitmap_set(unsigned long *map, unsigned int start, int len)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 352) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 353) unsigned long *p = map + BIT_WORD(start);
fb5ac54263ef3 (Rasmus Villemoes 2014-08-06 16:10:07 -0700 354) const unsigned int size = start + len;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 355) int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 356) unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 357)
fb5ac54263ef3 (Rasmus Villemoes 2014-08-06 16:10:07 -0700 358) while (len - bits_to_set >= 0) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 359) *p |= mask_to_set;
fb5ac54263ef3 (Rasmus Villemoes 2014-08-06 16:10:07 -0700 360) len -= bits_to_set;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 361) bits_to_set = BITS_PER_LONG;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 362) mask_to_set = ~0UL;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 363) p++;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 364) }
fb5ac54263ef3 (Rasmus Villemoes 2014-08-06 16:10:07 -0700 365) if (len) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 366) mask_to_set &= BITMAP_LAST_WORD_MASK(size);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 367) *p |= mask_to_set;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 368) }
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 369) }
e5af323c9badd (Matthew Wilcox 2017-07-10 15:51:29 -0700 370) EXPORT_SYMBOL(__bitmap_set);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 371)
e5af323c9badd (Matthew Wilcox 2017-07-10 15:51:29 -0700 372) void __bitmap_clear(unsigned long *map, unsigned int start, int len)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 373) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 374) unsigned long *p = map + BIT_WORD(start);
154f5e38f30f2 (Rasmus Villemoes 2014-08-06 16:10:10 -0700 375) const unsigned int size = start + len;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 376) int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 377) unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 378)
154f5e38f30f2 (Rasmus Villemoes 2014-08-06 16:10:10 -0700 379) while (len - bits_to_clear >= 0) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 380) *p &= ~mask_to_clear;
154f5e38f30f2 (Rasmus Villemoes 2014-08-06 16:10:10 -0700 381) len -= bits_to_clear;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 382) bits_to_clear = BITS_PER_LONG;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 383) mask_to_clear = ~0UL;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 384) p++;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 385) }
154f5e38f30f2 (Rasmus Villemoes 2014-08-06 16:10:10 -0700 386) if (len) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 387) mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 388) *p &= ~mask_to_clear;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 389) }
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 390) }
e5af323c9badd (Matthew Wilcox 2017-07-10 15:51:29 -0700 391) EXPORT_SYMBOL(__bitmap_clear);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 392)
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 393) /**
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 394) * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 395) * @map: The address to base the search on
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 396) * @size: The bitmap size in bits
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 397) * @start: The bitnumber to start searching at
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 398) * @nr: The number of zeroed bits we're looking for
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 399) * @align_mask: Alignment mask for zero area
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 400) * @align_offset: Alignment offset for zero area.
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 401) *
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 402) * The @align_mask should be one less than a power of 2; the effect is that
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 403) * the bit offset of all zero areas this function finds plus @align_offset
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 404) * is multiple of that power of 2.
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 405) */
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 406) unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 407) unsigned long size,
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 408) unsigned long start,
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 409) unsigned int nr,
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 410) unsigned long align_mask,
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 411) unsigned long align_offset)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 412) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 413) unsigned long index, end, i;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 414) again:
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 415) index = find_next_zero_bit(map, size, start);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 416)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 417) /* Align allocation */
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 418) index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 419)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 420) end = index + nr;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 421) if (end > size)
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 422) return end;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 423) i = find_next_bit(map, end, index);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 424) if (i < end) {
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 425) start = i + 1;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 426) goto again;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 427) }
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 428) return index;
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 429) }
5e19b013f55a8 (Michal Nazarewicz 2014-12-12 16:54:45 -0800 430) EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
c1a2a962a2ad1 (Akinobu Mita 2009-12-15 16:48:25 -0800 431)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 432) /*
6d49e352ae9ae (Nadia Yvette Chambers 2012-12-06 10:39:54 +0100 433) * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 434) * second version by Paul Jackson, third by Joe Korty.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 435) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 436)
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 437) /**
9a86e2bad0b9f (Ben Hutchings 2010-03-05 13:43:17 -0800 438) * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 439) *
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 440) * @ubuf: pointer to user buffer containing string.
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 441) * @ulen: buffer size in bytes. If string is smaller than this
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 442) * then it must be terminated with a \0.
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 443) * @maskp: pointer to bitmap array that will contain result.
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 444) * @nmaskbits: size of bitmap, in bits.
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 445) */
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 446) int bitmap_parse_user(const char __user *ubuf,
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 447) unsigned int ulen, unsigned long *maskp,
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 448) int nmaskbits)
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 449) {
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 450) char *buf;
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 451) int ret;
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 452)
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 453) buf = memdup_user_nul(ubuf, ulen);
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 454) if (IS_ERR(buf))
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 455) return PTR_ERR(buf);
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 456)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 457) ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
b9c321fd87b61 (H Hartley Sweeten 2011-10-31 17:12:32 -0700 458)
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 459) kfree(buf);
e66eda0615c87 (Yury Norov 2020-02-03 17:37:31 -0800 460) return ret;
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 461) }
01a3ee2b203e5 (Reinette Chatre 2006-10-11 01:21:55 -0700 462) EXPORT_SYMBOL(bitmap_parse_user);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 463)
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 464) /**
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 465) * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 466) * @list: indicates whether the bitmap must be list
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 467) * @buf: page aligned buffer into which string is placed
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 468) * @maskp: pointer to bitmap to convert
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 469) * @nmaskbits: size of bitmap, in bits
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 470) *
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 471) * Output format is a comma-separated list of decimal numbers and
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 472) * ranges if list is specified or hex digits grouped into comma-separated
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 473) * sets of 8 digits/set. Returns the number of characters written to buf.
9cf79d115f0d1 (Sudeep Holla 2015-06-25 15:02:17 -0700 474) *
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 475) * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 476) * area and that sufficient storage remains at @buf to accommodate the
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 477) * bitmap_print_to_pagebuf() output. Returns the number of characters
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 478) * actually printed to @buf, excluding terminating '\0'.
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 479) */
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 480) int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 481) int nmaskbits)
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 482) {
ce1091d471107 (Rasmus Villemoes 2018-10-30 15:05:14 -0700 483) ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 484)
8ec3d76863d8b (Rasmus Villemoes 2018-10-30 15:05:18 -0700 485) return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
8ec3d76863d8b (Rasmus Villemoes 2018-10-30 15:05:18 -0700 486) scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 487) }
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 488) EXPORT_SYMBOL(bitmap_print_to_pagebuf);
5aaba36318e59 (Sudeep Holla 2014-09-30 14:48:22 +0100 489)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 490) /*
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 491) * Region 9-38:4/10 describes the following bitmap structure:
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 492) * 0 9 12 18 38 N
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 493) * .........****......****......****..................
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 494) * ^ ^ ^ ^ ^
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 495) * start off group_len end nbits
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 496) */
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 497) struct region {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 498) unsigned int start;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 499) unsigned int off;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 500) unsigned int group_len;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 501) unsigned int end;
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 502) unsigned int nbits;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 503) };
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 504)
f3c869caef648 (Paul Gortmaker 2021-02-21 03:08:24 -0500 505) static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 506) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 507) unsigned int start;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 508)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 509) for (start = r->start; start <= r->end; start += r->group_len)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 510) bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 511) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 512)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 513) static int bitmap_check_region(const struct region *r)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 514) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 515) if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 516) return -EINVAL;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 517)
f3c869caef648 (Paul Gortmaker 2021-02-21 03:08:24 -0500 518) if (r->end >= r->nbits)
f3c869caef648 (Paul Gortmaker 2021-02-21 03:08:24 -0500 519) return -ERANGE;
f3c869caef648 (Paul Gortmaker 2021-02-21 03:08:24 -0500 520)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 521) return 0;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 522) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 523)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 524) static const char *bitmap_getnum(const char *str, unsigned int *num,
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 525) unsigned int lastbit)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 526) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 527) unsigned long long n;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 528) unsigned int len;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 529)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 530) if (str[0] == 'N') {
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 531) *num = lastbit;
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 532) return str + 1;
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 533) }
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 534)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 535) len = _parse_integer(str, 10, &n);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 536) if (!len)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 537) return ERR_PTR(-EINVAL);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 538) if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 539) return ERR_PTR(-EOVERFLOW);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 540)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 541) *num = n;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 542) return str + len;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 543) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 544)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 545) static inline bool end_of_str(char c)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 546) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 547) return c == '\0' || c == '\n';
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 548) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 549)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 550) static inline bool __end_of_region(char c)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 551) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 552) return isspace(c) || c == ',';
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 553) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 554)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 555) static inline bool end_of_region(char c)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 556) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 557) return __end_of_region(c) || end_of_str(c);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 558) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 559)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 560) /*
20607434113b8 (Randy Dunlap 2020-03-30 17:22:11 -0700 561) * The format allows commas and whitespaces at the beginning
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 562) * of the region.
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 563) */
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 564) static const char *bitmap_find_region(const char *str)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 565) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 566) while (__end_of_region(*str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 567) str++;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 568)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 569) return end_of_str(*str) ? NULL : str;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 570) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 571)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 572) static const char *bitmap_find_region_reverse(const char *start, const char *end)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 573) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 574) while (start <= end && __end_of_region(*end))
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 575) end--;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 576)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 577) return end;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 578) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 579)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 580) static const char *bitmap_parse_region(const char *str, struct region *r)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 581) {
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 582) unsigned int lastbit = r->nbits - 1;
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 583)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 584) str = bitmap_getnum(str, &r->start, lastbit);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 585) if (IS_ERR(str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 586) return str;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 587)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 588) if (end_of_region(*str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 589) goto no_end;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 590)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 591) if (*str != '-')
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 592) return ERR_PTR(-EINVAL);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 593)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 594) str = bitmap_getnum(str + 1, &r->end, lastbit);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 595) if (IS_ERR(str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 596) return str;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 597)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 598) if (end_of_region(*str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 599) goto no_pattern;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 600)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 601) if (*str != ':')
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 602) return ERR_PTR(-EINVAL);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 603)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 604) str = bitmap_getnum(str + 1, &r->off, lastbit);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 605) if (IS_ERR(str))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 606) return str;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 607)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 608) if (*str != '/')
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 609) return ERR_PTR(-EINVAL);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 610)
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 611) return bitmap_getnum(str + 1, &r->group_len, lastbit);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 612)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 613) no_end:
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 614) r->end = r->start;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 615) no_pattern:
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 616) r->off = r->end + 1;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 617) r->group_len = r->end + 1;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 618)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 619) return end_of_str(*str) ? NULL : str;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 620) }
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 621)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 622) /**
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 623) * bitmap_parselist - convert list format ASCII string to bitmap
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 624) * @buf: read user string from this buffer; must be terminated
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 625) * with a \0 or \n.
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 626) * @maskp: write resulting mask here
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 627) * @nmaskbits: number of bits in mask to be written
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 628) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 629) * Input format is a comma-separated list of decimal numbers and
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 630) * ranges. Consecutively set bits are shown as two hyphen-separated
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 631) * decimal numbers, the smallest and largest bit numbers set in
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 632) * the range.
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 633) * Optionally each range can be postfixed to denote that only parts of it
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 634) * should be set. The range will divided to groups of specific size.
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 635) * From each group will be used only defined amount of bits.
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 636) * Syntax: range:used_size/group_size
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 637) * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 638) * The value 'N' can be used as a dynamically substituted token for the
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 639) * maximum allowed value; i.e (nmaskbits - 1). Keep in mind that it is
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 640) * dynamic, so if system changes cause the bitmap width to change, such
2c4885d24e649 (Paul Gortmaker 2021-02-21 03:08:25 -0500 641) * as more cores in a CPU list, then any ranges using N will also change.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 642) *
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 643) * Returns: 0 on success, -errno on invalid input strings. Error values:
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 644) *
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 645) * - ``-EINVAL``: wrong region format
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 646) * - ``-EINVAL``: invalid character in string
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 647) * - ``-ERANGE``: bit number specified too large for mask
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 648) * - ``-EOVERFLOW``: integer overflow in the input parameters
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 649) */
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 650) int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 651) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 652) struct region r;
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 653) long ret;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 654)
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 655) r.nbits = nmaskbits;
9d7a3366b7028 (Paul Gortmaker 2021-02-21 03:08:23 -0500 656) bitmap_zero(maskp, r.nbits);
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 657)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 658) while (buf) {
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 659) buf = bitmap_find_region(buf);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 660) if (buf == NULL)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 661) return 0;
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 662)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 663) buf = bitmap_parse_region(buf, &r);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 664) if (IS_ERR(buf))
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 665) return PTR_ERR(buf);
2d13e6ca429c0 (Noam Camus 2016-10-11 13:51:35 -0700 666)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 667) ret = bitmap_check_region(&r);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 668) if (ret)
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 669) return ret;
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 670)
f3c869caef648 (Paul Gortmaker 2021-02-21 03:08:24 -0500 671) bitmap_set_region(&r, maskp);
e371c481d89cd (Yury Norov 2019-05-14 15:43:14 -0700 672) }
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 673)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 674) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 675) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 676) EXPORT_SYMBOL(bitmap_parselist);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 677)
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 678)
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 679) /**
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 680) * bitmap_parselist_user()
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 681) *
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 682) * @ubuf: pointer to user buffer containing string.
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 683) * @ulen: buffer size in bytes. If string is smaller than this
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 684) * then it must be terminated with a \0.
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 685) * @maskp: pointer to bitmap array that will contain result.
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 686) * @nmaskbits: size of bitmap, in bits.
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 687) *
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 688) * Wrapper for bitmap_parselist(), providing it with user buffer.
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 689) */
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 690) int bitmap_parselist_user(const char __user *ubuf,
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 691) unsigned int ulen, unsigned long *maskp,
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 692) int nmaskbits)
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 693) {
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 694) char *buf;
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 695) int ret;
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 696)
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 697) buf = memdup_user_nul(ubuf, ulen);
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 698) if (IS_ERR(buf))
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 699) return PTR_ERR(buf);
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 700)
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 701) ret = bitmap_parselist(buf, maskp, nmaskbits);
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 702)
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 703) kfree(buf);
281327c99bcaa (Yury Norov 2019-05-14 15:43:11 -0700 704) return ret;
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 705) }
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 706) EXPORT_SYMBOL(bitmap_parselist_user);
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 707)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 708) static const char *bitmap_get_x32_reverse(const char *start,
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 709) const char *end, u32 *num)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 710) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 711) u32 ret = 0;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 712) int c, i;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 713)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 714) for (i = 0; i < 32; i += 4) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 715) c = hex_to_bin(*end--);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 716) if (c < 0)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 717) return ERR_PTR(-EINVAL);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 718)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 719) ret |= c << i;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 720)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 721) if (start > end || __end_of_region(*end))
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 722) goto out;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 723) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 724)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 725) if (hex_to_bin(*end--) >= 0)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 726) return ERR_PTR(-EOVERFLOW);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 727) out:
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 728) *num = ret;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 729) return end;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 730) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 731)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 732) /**
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 733) * bitmap_parse - convert an ASCII hex string into a bitmap.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 734) * @start: pointer to buffer containing string.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 735) * @buflen: buffer size in bytes. If string is smaller than this
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 736) * then it must be terminated with a \0 or \n. In that case,
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 737) * UINT_MAX may be provided instead of string length.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 738) * @maskp: pointer to bitmap array that will contain result.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 739) * @nmaskbits: size of bitmap, in bits.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 740) *
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 741) * Commas group hex digits into chunks. Each chunk defines exactly 32
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 742) * bits of the resultant bitmask. No chunk may specify a value larger
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 743) * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 744) * then leading 0-bits are prepended. %-EINVAL is returned for illegal
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 745) * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 746) * Leading, embedded and trailing whitespace accepted.
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 747) */
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 748) int bitmap_parse(const char *start, unsigned int buflen,
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 749) unsigned long *maskp, int nmaskbits)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 750) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 751) const char *end = strnchrnul(start, buflen, '\n') - 1;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 752) int chunks = BITS_TO_U32(nmaskbits);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 753) u32 *bitmap = (u32 *)maskp;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 754) int unset_bit;
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 755) int chunk;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 756)
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 757) for (chunk = 0; ; chunk++) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 758) end = bitmap_find_region_reverse(start, end);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 759) if (start > end)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 760) break;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 761)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 762) if (!chunks--)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 763) return -EOVERFLOW;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 764)
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 765) #if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 766) end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 767) #else
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 768) end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
81c4f4d924d5d (Alexander Gordeev 2020-06-10 18:41:41 -0700 769) #endif
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 770) if (IS_ERR(end))
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 771) return PTR_ERR(end);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 772) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 773)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 774) unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 775) if (unset_bit < nmaskbits) {
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 776) bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 777) return 0;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 778) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 779)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 780) if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 781) return -EOVERFLOW;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 782)
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 783) return 0;
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 784) }
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 785) EXPORT_SYMBOL(bitmap_parse);
2d6261583be00 (Yury Norov 2020-02-03 17:37:34 -0800 786)
4b060420a5960 (Mike Travis 2011-05-24 17:13:12 -0700 787)
cdc90a1871d6e (Rasmus Villemoes 2019-05-14 15:42:43 -0700 788) #ifdef CONFIG_NUMA
72fd4a35a8243 (Robert P. J. Day 2007-02-10 01:45:59 -0800 789) /**
9a86e2bad0b9f (Ben Hutchings 2010-03-05 13:43:17 -0800 790) * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 791) * @buf: pointer to a bitmap
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 792) * @pos: a bit position in @buf (0 <= @pos < @nbits)
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 793) * @nbits: number of valid bit positions in @buf
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 794) *
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 795) * Map the bit at position @pos in @buf (of length @nbits) to the
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 796) * ordinal of which set bit it is. If it is not set or if @pos
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 797) * is not a valid bit position, map to -1.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 798) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 799) * If for example, just bits 4 through 7 are set in @buf, then @pos
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 800) * values 4 through 7 will get mapped to 0 through 3, respectively,
a855174878f06 (Rasmus Villemoes 2014-08-06 16:10:14 -0700 801) * and other @pos values will get mapped to -1. When @pos value 7
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 802) * gets mapped to (returns) @ord value 3 in this example, that means
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 803) * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 804) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 805) * The bit positions 0 through @bits are valid positions in @buf.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 806) */
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 807) static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 808) {
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 809) if (pos >= nbits || !test_bit(pos, buf))
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 810) return -1;
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 811)
df1d80a9eb16d (Rasmus Villemoes 2015-02-12 15:02:07 -0800 812) return __bitmap_weight(buf, pos);
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 813) }
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 814)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 815) /**
9a86e2bad0b9f (Ben Hutchings 2010-03-05 13:43:17 -0800 816) * bitmap_ord_to_pos - find position of n-th set bit in bitmap
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 817) * @buf: pointer to bitmap
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 818) * @ord: ordinal bit position (n-th set bit, n >= 0)
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 819) * @nbits: number of valid bit positions in @buf
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 820) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 821) * Map the ordinal offset of bit @ord in @buf to its position in @buf.
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 822) * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 823) * >= weight(buf), returns @nbits.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 824) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 825) * If for example, just bits 4 through 7 are set in @buf, then @ord
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 826) * values 0 through 3 will get mapped to 4 through 7, respectively,
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 827) * and all other @ord values returns @nbits. When @ord value 3
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 828) * gets mapped to (returns) @pos value 7 in this example, that means
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 829) * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 830) *
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 831) * The bit positions 0 through @nbits-1 are valid positions in @buf.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 832) */
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 833) unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 834) {
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 835) unsigned int pos;
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 836)
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 837) for (pos = find_first_bit(buf, nbits);
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 838) pos < nbits && ord;
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 839) pos = find_next_bit(buf, nbits, pos + 1))
f6a1f5db8d7a7 (Rasmus Villemoes 2015-02-12 15:02:10 -0800 840) ord--;
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 841)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 842) return pos;
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 843) }
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 844)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 845) /**
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 846) * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 847) * @dst: remapped result
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 848) * @src: subset to be remapped
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 849) * @old: defines domain of map
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 850) * @new: defines range of map
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 851) * @nbits: number of bits in each of these bitmaps
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 852) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 853) * Let @old and @new define a mapping of bit positions, such that
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 854) * whatever position is held by the n-th set bit in @old is mapped
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 855) * to the n-th set bit in @new. In the more general case, allowing
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 856) * for the possibility that the weight 'w' of @new is less than the
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 857) * weight of @old, map the position of the n-th set bit in @old to
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 858) * the position of the m-th set bit in @new, where m == n % w.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 859) *
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 860) * If either of the @old and @new bitmaps are empty, or if @src and
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 861) * @dst point to the same location, then this routine copies @src
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 862) * to @dst.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 863) *
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 864) * The positions of unset bits in @old are mapped to themselves
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 865) * (the identify map).
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 866) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 867) * Apply the above specified mapping to @src, placing the result in
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 868) * @dst, clearing any bits previously set in @dst.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 869) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 870) * For example, lets say that @old has bits 4 through 7 set, and
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 871) * @new has bits 12 through 15 set. This defines the mapping of bit
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 872) * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 873) * bit positions unchanged. So if say @src comes into this routine
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 874) * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 875) * 13 and 15 set.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 876) */
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 877) void bitmap_remap(unsigned long *dst, const unsigned long *src,
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 878) const unsigned long *old, const unsigned long *new,
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 879) unsigned int nbits)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 880) {
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 881) unsigned int oldbit, w;
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 882)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 883) if (dst == src) /* following doesn't handle inplace remaps */
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 884) return;
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 885) bitmap_zero(dst, nbits);
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 886)
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 887) w = bitmap_weight(new, nbits);
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 888) for_each_set_bit(oldbit, src, nbits) {
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 889) int n = bitmap_pos_to_ord(old, oldbit, nbits);
08564fb7ab9ea (Akinobu Mita 2010-03-05 13:43:18 -0800 890)
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 891) if (n < 0 || w == 0)
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 892) set_bit(oldbit, dst); /* identity map */
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 893) else
9814ec135dedb (Rasmus Villemoes 2015-02-12 15:02:13 -0800 894) set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 895) }
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 896) }
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 897)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 898) /**
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 899) * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 900) * @oldbit: bit position to be mapped
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 901) * @old: defines domain of map
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 902) * @new: defines range of map
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 903) * @bits: number of bits in each of these bitmaps
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 904) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 905) * Let @old and @new define a mapping of bit positions, such that
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 906) * whatever position is held by the n-th set bit in @old is mapped
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 907) * to the n-th set bit in @new. In the more general case, allowing
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 908) * for the possibility that the weight 'w' of @new is less than the
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 909) * weight of @old, map the position of the n-th set bit in @old to
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 910) * the position of the m-th set bit in @new, where m == n % w.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 911) *
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 912) * The positions of unset bits in @old are mapped to themselves
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 913) * (the identify map).
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 914) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 915) * Apply the above specified mapping to bit position @oldbit, returning
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 916) * the new bit position.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 917) *
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 918) * For example, lets say that @old has bits 4 through 7 set, and
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 919) * @new has bits 12 through 15 set. This defines the mapping of bit
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 920) * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 921) * bit positions unchanged. So if say @oldbit is 5, then this routine
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 922) * returns 13.
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 923) */
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 924) int bitmap_bitremap(int oldbit, const unsigned long *old,
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 925) const unsigned long *new, int bits)
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 926) {
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 927) int w = bitmap_weight(new, bits);
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 928) int n = bitmap_pos_to_ord(old, oldbit, bits);
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 929) if (n < 0 || w == 0)
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 930) return oldbit;
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 931) else
96b7f34143c2c (Paul Jackson 2006-01-08 01:01:46 -0800 932) return bitmap_ord_to_pos(new, n % w, bits);
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 933) }
fb5eeeee44edb (Paul Jackson 2005-10-30 15:02:33 -0800 934)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 935) /**
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 936) * bitmap_onto - translate one bitmap relative to another
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 937) * @dst: resulting translated bitmap
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 938) * @orig: original untranslated bitmap
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 939) * @relmap: bitmap relative to which translated
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 940) * @bits: number of bits in each of these bitmaps
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 941) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 942) * Set the n-th bit of @dst iff there exists some m such that the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 943) * n-th bit of @relmap is set, the m-th bit of @orig is set, and
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 944) * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 945) * (If you understood the previous sentence the first time your
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 946) * read it, you're overqualified for your current job.)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 947) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 948) * In other words, @orig is mapped onto (surjectively) @dst,
da3dae54e4ff0 (Masanari Iida 2014-09-09 01:27:23 +0900 949) * using the map { <n, m> | the n-th bit of @relmap is the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 950) * m-th set bit of @relmap }.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 951) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 952) * Any set bits in @orig above bit number W, where W is the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 953) * weight of (number of set bits in) @relmap are mapped nowhere.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 954) * In particular, if for all bits m set in @orig, m >= W, then
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 955) * @dst will end up empty. In situations where the possibility
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 956) * of such an empty result is not desired, one way to avoid it is
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 957) * to use the bitmap_fold() operator, below, to first fold the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 958) * @orig bitmap over itself so that all its set bits x are in the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 959) * range 0 <= x < W. The bitmap_fold() operator does this by
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 960) * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 961) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 962) * Example [1] for bitmap_onto():
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 963) * Let's say @relmap has bits 30-39 set, and @orig has bits
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 964) * 1, 3, 5, 7, 9 and 11 set. Then on return from this routine,
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 965) * @dst will have bits 31, 33, 35, 37 and 39 set.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 966) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 967) * When bit 0 is set in @orig, it means turn on the bit in
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 968) * @dst corresponding to whatever is the first bit (if any)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 969) * that is turned on in @relmap. Since bit 0 was off in the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 970) * above example, we leave off that bit (bit 30) in @dst.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 971) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 972) * When bit 1 is set in @orig (as in the above example), it
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 973) * means turn on the bit in @dst corresponding to whatever
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 974) * is the second bit that is turned on in @relmap. The second
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 975) * bit in @relmap that was turned on in the above example was
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 976) * bit 31, so we turned on bit 31 in @dst.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 977) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 978) * Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 979) * because they were the 4th, 6th, 8th and 10th set bits
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 980) * set in @relmap, and the 4th, 6th, 8th and 10th bits of
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 981) * @orig (i.e. bits 3, 5, 7 and 9) were also set.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 982) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 983) * When bit 11 is set in @orig, it means turn on the bit in
25985edcedea6 (Lucas De Marchi 2011-03-30 22:57:33 -0300 984) * @dst corresponding to whatever is the twelfth bit that is
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 985) * turned on in @relmap. In the above example, there were
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 986) * only ten bits turned on in @relmap (30..39), so that bit
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 987) * 11 was set in @orig had no affect on @dst.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 988) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 989) * Example [2] for bitmap_fold() + bitmap_onto():
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 990) * Let's say @relmap has these ten bits set::
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 991) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 992) * 40 41 42 43 45 48 53 61 74 95
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 993) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 994) * (for the curious, that's 40 plus the first ten terms of the
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 995) * Fibonacci sequence.)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 996) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 997) * Further lets say we use the following code, invoking
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 998) * bitmap_fold() then bitmap_onto, as suggested above to
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 999) * avoid the possibility of an empty @dst result::
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1000) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1001) * unsigned long *tmp; // a temporary bitmap's bits
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1002) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1003) * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1004) * bitmap_onto(dst, tmp, relmap, bits);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1005) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1006) * Then this table shows what various values of @dst would be, for
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1007) * various @orig's. I list the zero-based positions of each set bit.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1008) * The tmp column shows the intermediate result, as computed by
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1009) * using bitmap_fold() to fold the @orig bitmap modulo ten
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1010) * (the weight of @relmap):
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1011) *
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1012) * =============== ============== =================
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1013) * @orig tmp @dst
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1014) * 0 0 40
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1015) * 1 1 41
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1016) * 9 9 95
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1017) * 10 0 40 [#f1]_
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1018) * 1 3 5 7 1 3 5 7 41 43 48 61
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1019) * 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1020) * 0 9 18 27 0 9 8 7 40 61 74 95
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1021) * 0 10 20 30 0 40
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1022) * 0 11 22 33 0 1 2 3 40 41 42 43
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1023) * 0 12 24 36 0 2 4 6 40 42 45 53
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1024) * 78 102 211 1 2 8 41 42 74 [#f1]_
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1025) * =============== ============== =================
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1026) *
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1027) * .. [#f1]
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1028) *
40bf19a8d9af9 (Mauro Carvalho Chehab 2017-03-30 17:11:35 -0300 1029) * For these marked lines, if we hadn't first done bitmap_fold()
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1030) * into tmp, then the @dst result would have been empty.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1031) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1032) * If either of @orig or @relmap is empty (no set bits), then @dst
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1033) * will be returned empty.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1034) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1035) * If (as explained above) the only set bits in @orig are in positions
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1036) * m where m >= W, (where W is the weight of @relmap) then @dst will
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1037) * once again be returned empty.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1038) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1039) * All bits in @dst not set by the above rule are cleared.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1040) */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1041) void bitmap_onto(unsigned long *dst, const unsigned long *orig,
eb56988378816 (Rasmus Villemoes 2015-02-12 15:02:01 -0800 1042) const unsigned long *relmap, unsigned int bits)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1043) {
eb56988378816 (Rasmus Villemoes 2015-02-12 15:02:01 -0800 1044) unsigned int n, m; /* same meaning as in above comment */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1045)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1046) if (dst == orig) /* following doesn't handle inplace mappings */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1047) return;
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1048) bitmap_zero(dst, bits);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1049)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1050) /*
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1051) * The following code is a more efficient, but less
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1052) * obvious, equivalent to the loop:
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1053) * for (m = 0; m < bitmap_weight(relmap, bits); m++) {
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1054) * n = bitmap_ord_to_pos(orig, m, bits);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1055) * if (test_bit(m, orig))
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1056) * set_bit(n, dst);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1057) * }
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1058) */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1059)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1060) m = 0;
08564fb7ab9ea (Akinobu Mita 2010-03-05 13:43:18 -0800 1061) for_each_set_bit(n, relmap, bits) {
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1062) /* m == bitmap_pos_to_ord(relmap, n, bits) */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1063) if (test_bit(m, orig))
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1064) set_bit(n, dst);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1065) m++;
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1066) }
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1067) }
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1068)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1069) /**
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1070) * bitmap_fold - fold larger bitmap into smaller, modulo specified size
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1071) * @dst: resulting smaller bitmap
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1072) * @orig: original larger bitmap
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1073) * @sz: specified size
b26ad5836c3a0 (Rasmus Villemoes 2015-02-12 15:02:04 -0800 1074) * @nbits: number of bits in each of these bitmaps
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1075) *
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1076) * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1077) * Clear all other bits in @dst. See further the comment and
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1078) * Example [2] for bitmap_onto() for why and how to use this.
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1079) */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1080) void bitmap_fold(unsigned long *dst, const unsigned long *orig,
b26ad5836c3a0 (Rasmus Villemoes 2015-02-12 15:02:04 -0800 1081) unsigned int sz, unsigned int nbits)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1082) {
b26ad5836c3a0 (Rasmus Villemoes 2015-02-12 15:02:04 -0800 1083) unsigned int oldbit;
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1084)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1085) if (dst == orig) /* following doesn't handle inplace mappings */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1086) return;
b26ad5836c3a0 (Rasmus Villemoes 2015-02-12 15:02:04 -0800 1087) bitmap_zero(dst, nbits);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1088)
b26ad5836c3a0 (Rasmus Villemoes 2015-02-12 15:02:04 -0800 1089) for_each_set_bit(oldbit, orig, nbits)
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1090) set_bit(oldbit % sz, dst);
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1091) }
cdc90a1871d6e (Rasmus Villemoes 2019-05-14 15:42:43 -0700 1092) #endif /* CONFIG_NUMA */
7ea931c9fc80c (Paul Jackson 2008-04-28 02:12:29 -0700 1093)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1094) /*
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1095) * Common code for bitmap_*_region() routines.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1096) * bitmap: array of unsigned longs corresponding to the bitmap
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1097) * pos: the beginning of the region
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1098) * order: region size (log base 2 of number of bits)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1099) * reg_op: operation(s) to perform on that region of bitmap
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1100) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1101) * Can set, verify and/or release a region of bits in a bitmap,
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1102) * depending on which combination of REG_OP_* flag bits is set.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1103) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1104) * A region of a bitmap is a sequence of bits in the bitmap, of
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1105) * some size '1 << order' (a power of two), aligned to that same
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1106) * '1 << order' power of two.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1107) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1108) * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1109) * Returns 0 in all other cases and reg_ops.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1110) */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1111)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1112) enum {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1113) REG_OP_ISFREE, /* true if region is all zero bits */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1114) REG_OP_ALLOC, /* set all bits in region */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1115) REG_OP_RELEASE, /* clear all bits in region */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1116) };
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1117)
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1118) static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1119) {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1120) int nbits_reg; /* number of bits in region */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1121) int index; /* index first long of region in bitmap */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1122) int offset; /* bit offset region in bitmap[index] */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1123) int nlongs_reg; /* num longs spanned by region in bitmap */
74373c6acc524 (Paul Mundt 2006-03-24 03:15:45 -0800 1124) int nbitsinlong; /* num bits of region in each spanned long */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1125) unsigned long mask; /* bitmask for one long of region */
74373c6acc524 (Paul Mundt 2006-03-24 03:15:45 -0800 1126) int i; /* scans bitmap by longs */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1127) int ret = 0; /* return value */
74373c6acc524 (Paul Mundt 2006-03-24 03:15:45 -0800 1128)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1129) /*
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1130) * Either nlongs_reg == 1 (for small orders that fit in one long)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1131) * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1132) */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1133) nbits_reg = 1 << order;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1134) index = pos / BITS_PER_LONG;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1135) offset = pos - (index * BITS_PER_LONG);
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1136) nlongs_reg = BITS_TO_LONGS(nbits_reg);
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1137) nbitsinlong = min(nbits_reg, BITS_PER_LONG);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1138)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1139) /*
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1140) * Can't do "mask = (1UL << nbitsinlong) - 1", as that
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1141) * overflows if nbitsinlong == BITS_PER_LONG.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1142) */
74373c6acc524 (Paul Mundt 2006-03-24 03:15:45 -0800 1143) mask = (1UL << (nbitsinlong - 1));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1144) mask += mask - 1;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1145) mask <<= offset;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1146)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1147) switch (reg_op) {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1148) case REG_OP_ISFREE:
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1149) for (i = 0; i < nlongs_reg; i++) {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1150) if (bitmap[index + i] & mask)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1151) goto done;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1152) }
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1153) ret = 1; /* all bits in region free (zero) */
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1154) break;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1155)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1156) case REG_OP_ALLOC:
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1157) for (i = 0; i < nlongs_reg; i++)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1158) bitmap[index + i] |= mask;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1159) break;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1160)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1161) case REG_OP_RELEASE:
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1162) for (i = 0; i < nlongs_reg; i++)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1163) bitmap[index + i] &= ~mask;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1164) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1165) }
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1166) done:
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1167) return ret;
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1168) }
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1169)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1170) /**
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1171) * bitmap_find_free_region - find a contiguous aligned mem region
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1172) * @bitmap: array of unsigned longs corresponding to the bitmap
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1173) * @bits: number of bits in the bitmap
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1174) * @order: region size (log base 2 of number of bits) to find
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1175) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1176) * Find a region of free (zero) bits in a @bitmap of @bits bits and
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1177) * allocate them (set them to one). Only consider regions of length
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1178) * a power (@order) of two, aligned to that power of two, which
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1179) * makes the search algorithm much faster.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1180) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1181) * Return the bit offset in bitmap of the allocated region,
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1182) * or -errno on failure.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1183) */
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1184) int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1185) {
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1186) unsigned int pos, end; /* scans bitmap by regions of size order */
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1187)
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1188) for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1189) if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1190) continue;
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1191) __reg_op(bitmap, pos, order, REG_OP_ALLOC);
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1192) return pos;
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1193) }
aa8e4fc68d802 (Linus Torvalds 2009-03-12 19:32:51 -0700 1194) return -ENOMEM;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1195) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1196) EXPORT_SYMBOL(bitmap_find_free_region);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1197)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1198) /**
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1199) * bitmap_release_region - release allocated bitmap region
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1200) * @bitmap: array of unsigned longs corresponding to the bitmap
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1201) * @pos: beginning of bit region to release
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1202) * @order: region size (log base 2 of number of bits) to release
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1203) *
72fd4a35a8243 (Robert P. J. Day 2007-02-10 01:45:59 -0800 1204) * This is the complement to __bitmap_find_free_region() and releases
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1205) * the found region (by clearing it in the bitmap).
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1206) *
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1207) * No return value.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1208) */
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1209) void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1210) {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1211) __reg_op(bitmap, pos, order, REG_OP_RELEASE);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1212) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1213) EXPORT_SYMBOL(bitmap_release_region);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1214)
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1215) /**
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1216) * bitmap_allocate_region - allocate bitmap region
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1217) * @bitmap: array of unsigned longs corresponding to the bitmap
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1218) * @pos: beginning of bit region to allocate
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1219) * @order: region size (log base 2 of number of bits) to allocate
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1220) *
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1221) * Allocate (set bits in) a specified region of a bitmap.
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1222) *
6e1907ffdc694 (Randy Dunlap 2006-06-25 05:48:57 -0700 1223) * Return 0 on success, or %-EBUSY if specified region wasn't
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1224) * free (not all bits were zero).
87e2480258633 (Paul Jackson 2006-03-24 03:15:44 -0800 1225) */
9279d3286e107 (Rasmus Villemoes 2014-08-06 16:10:16 -0700 1226) int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1227) {
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1228) if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
3cf64b933c90b (Paul Jackson 2006-03-24 03:15:46 -0800 1229) return -EBUSY;
2ac521d3325a2 (Rasmus Villemoes 2014-08-06 16:10:18 -0700 1230) return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1231) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 1232) EXPORT_SYMBOL(bitmap_allocate_region);
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1233)
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1234) /**
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1235) * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1236) * @dst: destination buffer
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1237) * @src: bitmap to copy
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1238) * @nbits: number of bits in the bitmap
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1239) *
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1240) * Require nbits % BITS_PER_LONG == 0.
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1241) */
e8f24278329dc (Rasmus Villemoes 2015-02-13 14:36:00 -0800 1242) #ifdef __BIG_ENDIAN
9b6c2d2e2ba52 (Rasmus Villemoes 2015-02-13 14:35:57 -0800 1243) void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1244) {
9b6c2d2e2ba52 (Rasmus Villemoes 2015-02-13 14:35:57 -0800 1245) unsigned int i;
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1246)
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1247) for (i = 0; i < nbits/BITS_PER_LONG; i++) {
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1248) if (BITS_PER_LONG == 64)
9b6c2d2e2ba52 (Rasmus Villemoes 2015-02-13 14:35:57 -0800 1249) dst[i] = cpu_to_le64(src[i]);
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1250) else
9b6c2d2e2ba52 (Rasmus Villemoes 2015-02-13 14:35:57 -0800 1251) dst[i] = cpu_to_le32(src[i]);
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1252) }
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1253) }
ccbe329bcd879 (David Vrabel 2008-09-17 16:34:03 +0100 1254) EXPORT_SYMBOL(bitmap_copy_le);
e8f24278329dc (Rasmus Villemoes 2015-02-13 14:36:00 -0800 1255) #endif
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1256)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1257) unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1258) {
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1259) return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1260) flags);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1261) }
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1262) EXPORT_SYMBOL(bitmap_alloc);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1263)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1264) unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1265) {
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1266) return bitmap_alloc(nbits, flags | __GFP_ZERO);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1267) }
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1268) EXPORT_SYMBOL(bitmap_zalloc);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1269)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1270) void bitmap_free(const unsigned long *bitmap)
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1271) {
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1272) kfree(bitmap);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1273) }
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1274) EXPORT_SYMBOL(bitmap_free);
c42b65e363ce9 (Andy Shevchenko 2018-08-01 15:42:56 -0700 1275)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1276) static void devm_bitmap_free(void *data)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1277) {
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1278) unsigned long *bitmap = data;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1279)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1280) bitmap_free(bitmap);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1281) }
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1282)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1283) unsigned long *devm_bitmap_alloc(struct device *dev,
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1284) unsigned int nbits, gfp_t flags)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1285) {
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1286) unsigned long *bitmap;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1287) int ret;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1288)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1289) bitmap = bitmap_alloc(nbits, flags);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1290) if (!bitmap)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1291) return NULL;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1292)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1293) ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1294) if (ret)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1295) return NULL;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1296)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1297) return bitmap;
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1298) }
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1299) EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1300)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1301) unsigned long *devm_bitmap_zalloc(struct device *dev,
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1302) unsigned int nbits, gfp_t flags)
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1303) {
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1304) return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1305) }
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1306) EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
e829c2e474485 (Bartosz Golaszewski 2021-03-15 10:13:56 +0100 1307)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1308) #if BITS_PER_LONG == 64
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1309) /**
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1310) * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1311) * @bitmap: array of unsigned longs, the destination bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1312) * @buf: array of u32 (in host byte order), the source bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1313) * @nbits: number of bits in @bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1314) */
ccf7a6d457a8b (Andy Shevchenko 2018-08-21 21:56:59 -0700 1315) void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1316) {
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1317) unsigned int i, halfwords;
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1318)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1319) halfwords = DIV_ROUND_UP(nbits, 32);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1320) for (i = 0; i < halfwords; i++) {
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1321) bitmap[i/2] = (unsigned long) buf[i];
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1322) if (++i < halfwords)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1323) bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1324) }
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1325)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1326) /* Clear tail bits in last word beyond nbits. */
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1327) if (nbits % BITS_PER_LONG)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1328) bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1329) }
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1330) EXPORT_SYMBOL(bitmap_from_arr32);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1331)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1332) /**
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1333) * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1334) * @buf: array of u32 (in host byte order), the dest bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1335) * @bitmap: array of unsigned longs, the source bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1336) * @nbits: number of bits in @bitmap
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1337) */
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1338) void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1339) {
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1340) unsigned int i, halfwords;
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1341)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1342) halfwords = DIV_ROUND_UP(nbits, 32);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1343) for (i = 0; i < halfwords; i++) {
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1344) buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1345) if (++i < halfwords)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1346) buf[i] = (u32) (bitmap[i/2] >> 32);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1347) }
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1348)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1349) /* Clear tail bits in last element of array beyond nbits. */
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1350) if (nbits % BITS_PER_LONG)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1351) buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1352) }
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1353) EXPORT_SYMBOL(bitmap_to_arr32);
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1354)
c724f193619c8 (Yury Norov 2018-02-06 15:38:02 -0800 1355) #endif
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
33 Branches
57 Tags