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