Back to home page

OSCL-LXR
 
 

     

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef __LINUX_BITMAP_H
0003 #define __LINUX_BITMAP_H
0004 
0005 #ifndef __ASSEMBLY__
0006 
0007 #include <linux/align.h>
0008 #include <linux/bitops.h>
0009 #include <linux/find.h>
0010 #include <linux/limits.h>
0011 #include <linux/string.h>
0012 #include <linux/types.h>
0013 
0014 struct device;
0015 
0016 /*
0017  * bitmaps provide bit arrays that consume one or more unsigned
0018  * longs.  The bitmap interface and available operations are listed
0019  * here, in bitmap.h
0020  *
0021  * Function implementations generic to all architectures are in
0022  * lib/bitmap.c.  Functions implementations that are architecture
0023  * specific are in various include/asm-<arch>/bitops.h headers
0024  * and other arch/<arch> specific files.
0025  *
0026  * See lib/bitmap.c for more details.
0027  */
0028 
0029 /**
0030  * DOC: bitmap overview
0031  *
0032  * The available bitmap operations and their rough meaning in the
0033  * case that the bitmap is a single unsigned long are thus:
0034  *
0035  * The generated code is more efficient when nbits is known at
0036  * compile-time and at most BITS_PER_LONG.
0037  *
0038  * ::
0039  *
0040  *  bitmap_zero(dst, nbits)                     *dst = 0UL
0041  *  bitmap_fill(dst, nbits)                     *dst = ~0UL
0042  *  bitmap_copy(dst, src, nbits)                *dst = *src
0043  *  bitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2
0044  *  bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2
0045  *  bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2
0046  *  bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)
0047  *  bitmap_complement(dst, src, nbits)          *dst = ~(*src)
0048  *  bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?
0049  *  bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?
0050  *  bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?
0051  *  bitmap_empty(src, nbits)                    Are all bits zero in *src?
0052  *  bitmap_full(src, nbits)                     Are all bits set in *src?
0053  *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
0054  *  bitmap_set(dst, pos, nbits)                 Set specified bit area
0055  *  bitmap_clear(dst, pos, nbits)               Clear specified bit area
0056  *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
0057  *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off)  as above
0058  *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
0059  *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
0060  *  bitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy rest
0061  *  bitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
0062  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
0063  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
0064  *  bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
0065  *  bitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod sz
0066  *  bitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel buf
0067  *  bitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user buf
0068  *  bitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel buf
0069  *  bitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user buf
0070  *  bitmap_find_free_region(bitmap, bits, order)  Find and allocate bit region
0071  *  bitmap_release_region(bitmap, pos, order)   Free specified bit region
0072  *  bitmap_allocate_region(bitmap, pos, order)  Allocate specified bit region
0073  *  bitmap_from_arr32(dst, buf, nbits)          Copy nbits from u32[] buf to dst
0074  *  bitmap_from_arr64(dst, buf, nbits)          Copy nbits from u64[] buf to dst
0075  *  bitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dst
0076  *  bitmap_to_arr64(buf, src, nbits)            Copy nbits from buf to u64[] dst
0077  *  bitmap_get_value8(map, start)               Get 8bit value from map at start
0078  *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
0079  *
0080  * Note, bitmap_zero() and bitmap_fill() operate over the region of
0081  * unsigned longs, that is, bits behind bitmap till the unsigned long
0082  * boundary will be zeroed or filled as well. Consider to use
0083  * bitmap_clear() or bitmap_set() to make explicit zeroing or filling
0084  * respectively.
0085  */
0086 
0087 /**
0088  * DOC: bitmap bitops
0089  *
0090  * Also the following operations in asm/bitops.h apply to bitmaps.::
0091  *
0092  *  set_bit(bit, addr)                  *addr |= bit
0093  *  clear_bit(bit, addr)                *addr &= ~bit
0094  *  change_bit(bit, addr)               *addr ^= bit
0095  *  test_bit(bit, addr)                 Is bit set in *addr?
0096  *  test_and_set_bit(bit, addr)         Set bit and return old value
0097  *  test_and_clear_bit(bit, addr)       Clear bit and return old value
0098  *  test_and_change_bit(bit, addr)      Change bit and return old value
0099  *  find_first_zero_bit(addr, nbits)    Position first zero bit in *addr
0100  *  find_first_bit(addr, nbits)         Position first set bit in *addr
0101  *  find_next_zero_bit(addr, nbits, bit)
0102  *                                      Position next zero bit in *addr >= bit
0103  *  find_next_bit(addr, nbits, bit)     Position next set bit in *addr >= bit
0104  *  find_next_and_bit(addr1, addr2, nbits, bit)
0105  *                                      Same as find_next_bit, but in
0106  *                                      (*addr1 & *addr2)
0107  *
0108  */
0109 
0110 /**
0111  * DOC: declare bitmap
0112  * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
0113  * to declare an array named 'name' of just enough unsigned longs to
0114  * contain all bit positions from 0 to 'bits' - 1.
0115  */
0116 
0117 /*
0118  * Allocation and deallocation of bitmap.
0119  * Provided in lib/bitmap.c to avoid circular dependency.
0120  */
0121 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags);
0122 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags);
0123 unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node);
0124 unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node);
0125 void bitmap_free(const unsigned long *bitmap);
0126 
0127 /* Managed variants of the above. */
0128 unsigned long *devm_bitmap_alloc(struct device *dev,
0129                  unsigned int nbits, gfp_t flags);
0130 unsigned long *devm_bitmap_zalloc(struct device *dev,
0131                   unsigned int nbits, gfp_t flags);
0132 
0133 /*
0134  * lib/bitmap.c provides these functions:
0135  */
0136 
0137 bool __bitmap_equal(const unsigned long *bitmap1,
0138             const unsigned long *bitmap2, unsigned int nbits);
0139 bool __pure __bitmap_or_equal(const unsigned long *src1,
0140                   const unsigned long *src2,
0141                   const unsigned long *src3,
0142                   unsigned int nbits);
0143 void __bitmap_complement(unsigned long *dst, const unsigned long *src,
0144              unsigned int nbits);
0145 void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
0146               unsigned int shift, unsigned int nbits);
0147 void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
0148              unsigned int shift, unsigned int nbits);
0149 void bitmap_cut(unsigned long *dst, const unsigned long *src,
0150         unsigned int first, unsigned int cut, unsigned int nbits);
0151 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
0152          const unsigned long *bitmap2, unsigned int nbits);
0153 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
0154          const unsigned long *bitmap2, unsigned int nbits);
0155 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
0156           const unsigned long *bitmap2, unsigned int nbits);
0157 bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
0158             const unsigned long *bitmap2, unsigned int nbits);
0159 void __bitmap_replace(unsigned long *dst,
0160               const unsigned long *old, const unsigned long *new,
0161               const unsigned long *mask, unsigned int nbits);
0162 bool __bitmap_intersects(const unsigned long *bitmap1,
0163              const unsigned long *bitmap2, unsigned int nbits);
0164 bool __bitmap_subset(const unsigned long *bitmap1,
0165              const unsigned long *bitmap2, unsigned int nbits);
0166 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
0167 void __bitmap_set(unsigned long *map, unsigned int start, int len);
0168 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
0169 
0170 unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
0171                          unsigned long size,
0172                          unsigned long start,
0173                          unsigned int nr,
0174                          unsigned long align_mask,
0175                          unsigned long align_offset);
0176 
0177 /**
0178  * bitmap_find_next_zero_area - find a contiguous aligned zero area
0179  * @map: The address to base the search on
0180  * @size: The bitmap size in bits
0181  * @start: The bitnumber to start searching at
0182  * @nr: The number of zeroed bits we're looking for
0183  * @align_mask: Alignment mask for zero area
0184  *
0185  * The @align_mask should be one less than a power of 2; the effect is that
0186  * the bit offset of all zero areas this function finds is multiples of that
0187  * power of 2. A @align_mask of 0 means no alignment is required.
0188  */
0189 static inline unsigned long
0190 bitmap_find_next_zero_area(unsigned long *map,
0191                unsigned long size,
0192                unsigned long start,
0193                unsigned int nr,
0194                unsigned long align_mask)
0195 {
0196     return bitmap_find_next_zero_area_off(map, size, start, nr,
0197                           align_mask, 0);
0198 }
0199 
0200 int bitmap_parse(const char *buf, unsigned int buflen,
0201             unsigned long *dst, int nbits);
0202 int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
0203             unsigned long *dst, int nbits);
0204 int bitmap_parselist(const char *buf, unsigned long *maskp,
0205             int nmaskbits);
0206 int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
0207             unsigned long *dst, int nbits);
0208 void bitmap_remap(unsigned long *dst, const unsigned long *src,
0209         const unsigned long *old, const unsigned long *new, unsigned int nbits);
0210 int bitmap_bitremap(int oldbit,
0211         const unsigned long *old, const unsigned long *new, int bits);
0212 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
0213         const unsigned long *relmap, unsigned int bits);
0214 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
0215         unsigned int sz, unsigned int nbits);
0216 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
0217 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
0218 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
0219 
0220 #ifdef __BIG_ENDIAN
0221 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
0222 #else
0223 #define bitmap_copy_le bitmap_copy
0224 #endif
0225 unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
0226 int bitmap_print_to_pagebuf(bool list, char *buf,
0227                    const unsigned long *maskp, int nmaskbits);
0228 
0229 extern int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
0230                       int nmaskbits, loff_t off, size_t count);
0231 
0232 extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
0233                       int nmaskbits, loff_t off, size_t count);
0234 
0235 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
0236 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
0237 
0238 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
0239 {
0240     unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
0241 
0242     if (small_const_nbits(nbits))
0243         *dst = 0;
0244     else
0245         memset(dst, 0, len);
0246 }
0247 
0248 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
0249 {
0250     unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
0251 
0252     if (small_const_nbits(nbits))
0253         *dst = ~0UL;
0254     else
0255         memset(dst, 0xff, len);
0256 }
0257 
0258 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
0259             unsigned int nbits)
0260 {
0261     unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
0262 
0263     if (small_const_nbits(nbits))
0264         *dst = *src;
0265     else
0266         memcpy(dst, src, len);
0267 }
0268 
0269 /*
0270  * Copy bitmap and clear tail bits in last word.
0271  */
0272 static inline void bitmap_copy_clear_tail(unsigned long *dst,
0273         const unsigned long *src, unsigned int nbits)
0274 {
0275     bitmap_copy(dst, src, nbits);
0276     if (nbits % BITS_PER_LONG)
0277         dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
0278 }
0279 
0280 /*
0281  * On 32-bit systems bitmaps are represented as u32 arrays internally. On LE64
0282  * machines the order of hi and lo parts of numbers match the bitmap structure.
0283  * In both cases conversion is not needed when copying data from/to arrays of
0284  * u32. But in LE64 case, typecast in bitmap_copy_clear_tail() may lead
0285  * to out-of-bound access. To avoid that, both LE and BE variants of 64-bit
0286  * architectures are not using bitmap_copy_clear_tail().
0287  */
0288 #if BITS_PER_LONG == 64
0289 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
0290                             unsigned int nbits);
0291 void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
0292                             unsigned int nbits);
0293 #else
0294 #define bitmap_from_arr32(bitmap, buf, nbits)           \
0295     bitmap_copy_clear_tail((unsigned long *) (bitmap),  \
0296             (const unsigned long *) (buf), (nbits))
0297 #define bitmap_to_arr32(buf, bitmap, nbits)         \
0298     bitmap_copy_clear_tail((unsigned long *) (buf),     \
0299             (const unsigned long *) (bitmap), (nbits))
0300 #endif
0301 
0302 /*
0303  * On 64-bit systems bitmaps are represented as u64 arrays internally. On LE32
0304  * machines the order of hi and lo parts of numbers match the bitmap structure.
0305  * In both cases conversion is not needed when copying data from/to arrays of
0306  * u64.
0307  */
0308 #if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN)
0309 void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits);
0310 void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits);
0311 #else
0312 #define bitmap_from_arr64(bitmap, buf, nbits)           \
0313     bitmap_copy_clear_tail((unsigned long *)(bitmap), (const unsigned long *)(buf), (nbits))
0314 #define bitmap_to_arr64(buf, bitmap, nbits)         \
0315     bitmap_copy_clear_tail((unsigned long *)(buf), (const unsigned long *)(bitmap), (nbits))
0316 #endif
0317 
0318 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,
0319             const unsigned long *src2, unsigned int nbits)
0320 {
0321     if (small_const_nbits(nbits))
0322         return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
0323     return __bitmap_and(dst, src1, src2, nbits);
0324 }
0325 
0326 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
0327             const unsigned long *src2, unsigned int nbits)
0328 {
0329     if (small_const_nbits(nbits))
0330         *dst = *src1 | *src2;
0331     else
0332         __bitmap_or(dst, src1, src2, nbits);
0333 }
0334 
0335 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
0336             const unsigned long *src2, unsigned int nbits)
0337 {
0338     if (small_const_nbits(nbits))
0339         *dst = *src1 ^ *src2;
0340     else
0341         __bitmap_xor(dst, src1, src2, nbits);
0342 }
0343 
0344 static inline bool bitmap_andnot(unsigned long *dst, const unsigned long *src1,
0345             const unsigned long *src2, unsigned int nbits)
0346 {
0347     if (small_const_nbits(nbits))
0348         return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
0349     return __bitmap_andnot(dst, src1, src2, nbits);
0350 }
0351 
0352 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
0353             unsigned int nbits)
0354 {
0355     if (small_const_nbits(nbits))
0356         *dst = ~(*src);
0357     else
0358         __bitmap_complement(dst, src, nbits);
0359 }
0360 
0361 #ifdef __LITTLE_ENDIAN
0362 #define BITMAP_MEM_ALIGNMENT 8
0363 #else
0364 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
0365 #endif
0366 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
0367 
0368 static inline bool bitmap_equal(const unsigned long *src1,
0369                 const unsigned long *src2, unsigned int nbits)
0370 {
0371     if (small_const_nbits(nbits))
0372         return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
0373     if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
0374         IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
0375         return !memcmp(src1, src2, nbits / 8);
0376     return __bitmap_equal(src1, src2, nbits);
0377 }
0378 
0379 /**
0380  * bitmap_or_equal - Check whether the or of two bitmaps is equal to a third
0381  * @src1:   Pointer to bitmap 1
0382  * @src2:   Pointer to bitmap 2 will be or'ed with bitmap 1
0383  * @src3:   Pointer to bitmap 3. Compare to the result of *@src1 | *@src2
0384  * @nbits:  number of bits in each of these bitmaps
0385  *
0386  * Returns: True if (*@src1 | *@src2) == *@src3, false otherwise
0387  */
0388 static inline bool bitmap_or_equal(const unsigned long *src1,
0389                    const unsigned long *src2,
0390                    const unsigned long *src3,
0391                    unsigned int nbits)
0392 {
0393     if (!small_const_nbits(nbits))
0394         return __bitmap_or_equal(src1, src2, src3, nbits);
0395 
0396     return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits));
0397 }
0398 
0399 static inline bool bitmap_intersects(const unsigned long *src1,
0400                      const unsigned long *src2,
0401                      unsigned int nbits)
0402 {
0403     if (small_const_nbits(nbits))
0404         return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
0405     else
0406         return __bitmap_intersects(src1, src2, nbits);
0407 }
0408 
0409 static inline bool bitmap_subset(const unsigned long *src1,
0410                  const unsigned long *src2, unsigned int nbits)
0411 {
0412     if (small_const_nbits(nbits))
0413         return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
0414     else
0415         return __bitmap_subset(src1, src2, nbits);
0416 }
0417 
0418 static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
0419 {
0420     if (small_const_nbits(nbits))
0421         return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
0422 
0423     return find_first_bit(src, nbits) == nbits;
0424 }
0425 
0426 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
0427 {
0428     if (small_const_nbits(nbits))
0429         return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
0430 
0431     return find_first_zero_bit(src, nbits) == nbits;
0432 }
0433 
0434 static __always_inline
0435 unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)
0436 {
0437     if (small_const_nbits(nbits))
0438         return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
0439     return __bitmap_weight(src, nbits);
0440 }
0441 
0442 static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
0443         unsigned int nbits)
0444 {
0445     if (__builtin_constant_p(nbits) && nbits == 1)
0446         __set_bit(start, map);
0447     else if (small_const_nbits(start + nbits))
0448         *map |= GENMASK(start + nbits - 1, start);
0449     else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
0450          IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
0451          __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
0452          IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
0453         memset((char *)map + start / 8, 0xff, nbits / 8);
0454     else
0455         __bitmap_set(map, start, nbits);
0456 }
0457 
0458 static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
0459         unsigned int nbits)
0460 {
0461     if (__builtin_constant_p(nbits) && nbits == 1)
0462         __clear_bit(start, map);
0463     else if (small_const_nbits(start + nbits))
0464         *map &= ~GENMASK(start + nbits - 1, start);
0465     else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
0466          IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
0467          __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
0468          IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
0469         memset((char *)map + start / 8, 0, nbits / 8);
0470     else
0471         __bitmap_clear(map, start, nbits);
0472 }
0473 
0474 static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
0475                 unsigned int shift, unsigned int nbits)
0476 {
0477     if (small_const_nbits(nbits))
0478         *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
0479     else
0480         __bitmap_shift_right(dst, src, shift, nbits);
0481 }
0482 
0483 static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
0484                 unsigned int shift, unsigned int nbits)
0485 {
0486     if (small_const_nbits(nbits))
0487         *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
0488     else
0489         __bitmap_shift_left(dst, src, shift, nbits);
0490 }
0491 
0492 static inline void bitmap_replace(unsigned long *dst,
0493                   const unsigned long *old,
0494                   const unsigned long *new,
0495                   const unsigned long *mask,
0496                   unsigned int nbits)
0497 {
0498     if (small_const_nbits(nbits))
0499         *dst = (*old & ~(*mask)) | (*new & *mask);
0500     else
0501         __bitmap_replace(dst, old, new, mask, nbits);
0502 }
0503 
0504 static inline void bitmap_next_set_region(unsigned long *bitmap,
0505                       unsigned int *rs, unsigned int *re,
0506                       unsigned int end)
0507 {
0508     *rs = find_next_bit(bitmap, end, *rs);
0509     *re = find_next_zero_bit(bitmap, end, *rs + 1);
0510 }
0511 
0512 /**
0513  * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
0514  * @n: u64 value
0515  *
0516  * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit
0517  * integers in 32-bit environment, and 64-bit integers in 64-bit one.
0518  *
0519  * There are four combinations of endianness and length of the word in linux
0520  * ABIs: LE64, BE64, LE32 and BE32.
0521  *
0522  * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in
0523  * bitmaps and therefore don't require any special handling.
0524  *
0525  * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory
0526  * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the
0527  * other hand is represented as an array of 32-bit words and the position of
0528  * bit N may therefore be calculated as: word #(N/32) and bit #(N%32) in that
0529  * word.  For example, bit #42 is located at 10th position of 2nd word.
0530  * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
0531  * values in memory as it usually does. But for BE we need to swap hi and lo
0532  * words manually.
0533  *
0534  * With all that, the macro BITMAP_FROM_U64() does explicit reordering of hi and
0535  * lo parts of u64.  For LE32 it does nothing, and for BE environment it swaps
0536  * hi and lo words, as is expected by bitmap.
0537  */
0538 #if __BITS_PER_LONG == 64
0539 #define BITMAP_FROM_U64(n) (n)
0540 #else
0541 #define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
0542                 ((unsigned long) ((u64)(n) >> 32))
0543 #endif
0544 
0545 /**
0546  * bitmap_from_u64 - Check and swap words within u64.
0547  *  @mask: source bitmap
0548  *  @dst:  destination bitmap
0549  *
0550  * In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]``
0551  * to read u64 mask, we will get the wrong word.
0552  * That is ``(u32 *)(&val)[0]`` gets the upper 32 bits,
0553  * but we expect the lower 32-bits of u64.
0554  */
0555 static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
0556 {
0557     bitmap_from_arr64(dst, &mask, 64);
0558 }
0559 
0560 /**
0561  * bitmap_get_value8 - get an 8-bit value within a memory region
0562  * @map: address to the bitmap memory region
0563  * @start: bit offset of the 8-bit value; must be a multiple of 8
0564  *
0565  * Returns the 8-bit value located at the @start bit offset within the @src
0566  * memory region.
0567  */
0568 static inline unsigned long bitmap_get_value8(const unsigned long *map,
0569                           unsigned long start)
0570 {
0571     const size_t index = BIT_WORD(start);
0572     const unsigned long offset = start % BITS_PER_LONG;
0573 
0574     return (map[index] >> offset) & 0xFF;
0575 }
0576 
0577 /**
0578  * bitmap_set_value8 - set an 8-bit value within a memory region
0579  * @map: address to the bitmap memory region
0580  * @value: the 8-bit value; values wider than 8 bits may clobber bitmap
0581  * @start: bit offset of the 8-bit value; must be a multiple of 8
0582  */
0583 static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
0584                      unsigned long start)
0585 {
0586     const size_t index = BIT_WORD(start);
0587     const unsigned long offset = start % BITS_PER_LONG;
0588 
0589     map[index] &= ~(0xFFUL << offset);
0590     map[index] |= value << offset;
0591 }
0592 
0593 #endif /* __ASSEMBLY__ */
0594 
0595 #endif /* __LINUX_BITMAP_H */
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!