bitmap.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef __LINUX_BITMAP_H
  3. #define __LINUX_BITMAP_H
  4. #ifndef __ASSEMBLY__
  5. #include <linux/types.h>
  6. #include <linux/bitops.h>
  7. #include <linux/string.h>
  8. #include <linux/kernel.h>
  9. /*
  10. * bitmaps provide bit arrays that consume one or more unsigned
  11. * longs. The bitmap interface and available operations are listed
  12. * here, in bitmap.h
  13. *
  14. * Function implementations generic to all architectures are in
  15. * lib/bitmap.c. Functions implementations that are architecture
  16. * specific are in various include/asm-<arch>/bitops.h headers
  17. * and other arch/<arch> specific files.
  18. *
  19. * See lib/bitmap.c for more details.
  20. */
  21. /**
  22. * DOC: bitmap overview
  23. *
  24. * The available bitmap operations and their rough meaning in the
  25. * case that the bitmap is a single unsigned long are thus:
  26. *
  27. * The generated code is more efficient when nbits is known at
  28. * compile-time and at most BITS_PER_LONG.
  29. *
  30. * ::
  31. *
  32. * bitmap_zero(dst, nbits) *dst = 0UL
  33. * bitmap_fill(dst, nbits) *dst = ~0UL
  34. * bitmap_copy(dst, src, nbits) *dst = *src
  35. * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2
  36. * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2
  37. * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2
  38. * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2)
  39. * bitmap_complement(dst, src, nbits) *dst = ~(*src)
  40. * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal?
  41. * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap?
  42. * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2?
  43. * bitmap_empty(src, nbits) Are all bits zero in *src?
  44. * bitmap_full(src, nbits) Are all bits set in *src?
  45. * bitmap_weight(src, nbits) Hamming Weight: number set bits
  46. * bitmap_set(dst, pos, nbits) Set specified bit area
  47. * bitmap_clear(dst, pos, nbits) Clear specified bit area
  48. * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area
  49. * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above
  50. * bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region
  51. * bitmap_next_set_region(map, &start, &end, nbits) Find next set region
  52. * bitmap_for_each_clear_region(map, rs, re, start, end)
  53. * Iterate over all clear regions
  54. * bitmap_for_each_set_region(map, rs, re, start, end)
  55. * Iterate over all set regions
  56. * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n
  57. * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
  58. * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest
  59. * bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask)
  60. * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
  61. * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
  62. * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap
  63. * bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz
  64. * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf
  65. * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
  66. * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from kernel buf
  67. * bitmap_parselist_user(buf, dst, nbits) Parse bitmap dst from user buf
  68. * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region
  69. * bitmap_release_region(bitmap, pos, order) Free specified bit region
  70. * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region
  71. * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst
  72. * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst
  73. * bitmap_get_value8(map, start) Get 8bit value from map at start
  74. * bitmap_set_value8(map, value, start) Set 8bit value to map at start
  75. *
  76. * Note, bitmap_zero() and bitmap_fill() operate over the region of
  77. * unsigned longs, that is, bits behind bitmap till the unsigned long
  78. * boundary will be zeroed or filled as well. Consider to use
  79. * bitmap_clear() or bitmap_set() to make explicit zeroing or filling
  80. * respectively.
  81. */
  82. /**
  83. * DOC: bitmap bitops
  84. *
  85. * Also the following operations in asm/bitops.h apply to bitmaps.::
  86. *
  87. * set_bit(bit, addr) *addr |= bit
  88. * clear_bit(bit, addr) *addr &= ~bit
  89. * change_bit(bit, addr) *addr ^= bit
  90. * test_bit(bit, addr) Is bit set in *addr?
  91. * test_and_set_bit(bit, addr) Set bit and return old value
  92. * test_and_clear_bit(bit, addr) Clear bit and return old value
  93. * test_and_change_bit(bit, addr) Change bit and return old value
  94. * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
  95. * find_first_bit(addr, nbits) Position first set bit in *addr
  96. * find_next_zero_bit(addr, nbits, bit)
  97. * Position next zero bit in *addr >= bit
  98. * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit
  99. * find_next_and_bit(addr1, addr2, nbits, bit)
  100. * Same as find_next_bit, but in
  101. * (*addr1 & *addr2)
  102. *
  103. */
  104. /**
  105. * DOC: declare bitmap
  106. * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
  107. * to declare an array named 'name' of just enough unsigned longs to
  108. * contain all bit positions from 0 to 'bits' - 1.
  109. */
  110. /*
  111. * Allocation and deallocation of bitmap.
  112. * Provided in lib/bitmap.c to avoid circular dependency.
  113. */
  114. extern unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags);
  115. extern unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags);
  116. extern void bitmap_free(const unsigned long *bitmap);
  117. /*
  118. * lib/bitmap.c provides these functions:
  119. */
  120. extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits);
  121. extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits);
  122. extern int __bitmap_equal(const unsigned long *bitmap1,
  123. const unsigned long *bitmap2, unsigned int nbits);
  124. extern bool __pure __bitmap_or_equal(const unsigned long *src1,
  125. const unsigned long *src2,
  126. const unsigned long *src3,
  127. unsigned int nbits);
  128. extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
  129. unsigned int nbits);
  130. extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
  131. unsigned int shift, unsigned int nbits);
  132. extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
  133. unsigned int shift, unsigned int nbits);
  134. extern void bitmap_cut(unsigned long *dst, const unsigned long *src,
  135. unsigned int first, unsigned int cut,
  136. unsigned int nbits);
  137. extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  138. const unsigned long *bitmap2, unsigned int nbits);
  139. extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  140. const unsigned long *bitmap2, unsigned int nbits);
  141. extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  142. const unsigned long *bitmap2, unsigned int nbits);
  143. extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  144. const unsigned long *bitmap2, unsigned int nbits);
  145. extern void __bitmap_replace(unsigned long *dst,
  146. const unsigned long *old, const unsigned long *new,
  147. const unsigned long *mask, unsigned int nbits);
  148. extern int __bitmap_intersects(const unsigned long *bitmap1,
  149. const unsigned long *bitmap2, unsigned int nbits);
  150. extern int __bitmap_subset(const unsigned long *bitmap1,
  151. const unsigned long *bitmap2, unsigned int nbits);
  152. extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
  153. extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
  154. extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
  155. extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
  156. unsigned long size,
  157. unsigned long start,
  158. unsigned int nr,
  159. unsigned long align_mask,
  160. unsigned long align_offset);
  161. /**
  162. * bitmap_find_next_zero_area - find a contiguous aligned zero area
  163. * @map: The address to base the search on
  164. * @size: The bitmap size in bits
  165. * @start: The bitnumber to start searching at
  166. * @nr: The number of zeroed bits we're looking for
  167. * @align_mask: Alignment mask for zero area
  168. *
  169. * The @align_mask should be one less than a power of 2; the effect is that
  170. * the bit offset of all zero areas this function finds is multiples of that
  171. * power of 2. A @align_mask of 0 means no alignment is required.
  172. */
  173. static inline unsigned long
  174. bitmap_find_next_zero_area(unsigned long *map,
  175. unsigned long size,
  176. unsigned long start,
  177. unsigned int nr,
  178. unsigned long align_mask)
  179. {
  180. return bitmap_find_next_zero_area_off(map, size, start, nr,
  181. align_mask, 0);
  182. }
  183. extern int bitmap_parse(const char *buf, unsigned int buflen,
  184. unsigned long *dst, int nbits);
  185. extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
  186. unsigned long *dst, int nbits);
  187. extern int bitmap_parselist(const char *buf, unsigned long *maskp,
  188. int nmaskbits);
  189. extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
  190. unsigned long *dst, int nbits);
  191. extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
  192. const unsigned long *old, const unsigned long *new, unsigned int nbits);
  193. extern int bitmap_bitremap(int oldbit,
  194. const unsigned long *old, const unsigned long *new, int bits);
  195. extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
  196. const unsigned long *relmap, unsigned int bits);
  197. extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
  198. unsigned int sz, unsigned int nbits);
  199. extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
  200. extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
  201. extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
  202. #ifdef __BIG_ENDIAN
  203. extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
  204. #else
  205. #define bitmap_copy_le bitmap_copy
  206. #endif
  207. extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
  208. extern int bitmap_print_to_pagebuf(bool list, char *buf,
  209. const unsigned long *maskp, int nmaskbits);
  210. #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
  211. #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
  212. /*
  213. * The static inlines below do not handle constant nbits==0 correctly,
  214. * so make such users (should any ever turn up) call the out-of-line
  215. * versions.
  216. */
  217. #define small_const_nbits(nbits) \
  218. (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
  219. static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
  220. {
  221. unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  222. memset(dst, 0, len);
  223. }
  224. static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
  225. {
  226. unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  227. memset(dst, 0xff, len);
  228. }
  229. static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
  230. unsigned int nbits)
  231. {
  232. unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  233. memcpy(dst, src, len);
  234. }
  235. /*
  236. * Copy bitmap and clear tail bits in last word.
  237. */
  238. static inline void bitmap_copy_clear_tail(unsigned long *dst,
  239. const unsigned long *src, unsigned int nbits)
  240. {
  241. bitmap_copy(dst, src, nbits);
  242. if (nbits % BITS_PER_LONG)
  243. dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
  244. }
  245. /*
  246. * On 32-bit systems bitmaps are represented as u32 arrays internally, and
  247. * therefore conversion is not needed when copying data from/to arrays of u32.
  248. */
  249. #if BITS_PER_LONG == 64
  250. extern void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
  251. unsigned int nbits);
  252. extern void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
  253. unsigned int nbits);
  254. #else
  255. #define bitmap_from_arr32(bitmap, buf, nbits) \
  256. bitmap_copy_clear_tail((unsigned long *) (bitmap), \
  257. (const unsigned long *) (buf), (nbits))
  258. #define bitmap_to_arr32(buf, bitmap, nbits) \
  259. bitmap_copy_clear_tail((unsigned long *) (buf), \
  260. (const unsigned long *) (bitmap), (nbits))
  261. #endif
  262. static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
  263. const unsigned long *src2, unsigned int nbits)
  264. {
  265. if (small_const_nbits(nbits))
  266. return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  267. return __bitmap_and(dst, src1, src2, nbits);
  268. }
  269. static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  270. const unsigned long *src2, unsigned int nbits)
  271. {
  272. if (small_const_nbits(nbits))
  273. *dst = *src1 | *src2;
  274. else
  275. __bitmap_or(dst, src1, src2, nbits);
  276. }
  277. static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
  278. const unsigned long *src2, unsigned int nbits)
  279. {
  280. if (small_const_nbits(nbits))
  281. *dst = *src1 ^ *src2;
  282. else
  283. __bitmap_xor(dst, src1, src2, nbits);
  284. }
  285. static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
  286. const unsigned long *src2, unsigned int nbits)
  287. {
  288. if (small_const_nbits(nbits))
  289. return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  290. return __bitmap_andnot(dst, src1, src2, nbits);
  291. }
  292. static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  293. unsigned int nbits)
  294. {
  295. if (small_const_nbits(nbits))
  296. *dst = ~(*src);
  297. else
  298. __bitmap_complement(dst, src, nbits);
  299. }
  300. #ifdef __LITTLE_ENDIAN
  301. #define BITMAP_MEM_ALIGNMENT 8
  302. #else
  303. #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
  304. #endif
  305. #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
  306. static inline int bitmap_equal(const unsigned long *src1,
  307. const unsigned long *src2, unsigned int nbits)
  308. {
  309. if (small_const_nbits(nbits))
  310. return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
  311. if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
  312. IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
  313. return !memcmp(src1, src2, nbits / 8);
  314. return __bitmap_equal(src1, src2, nbits);
  315. }
  316. /**
  317. * bitmap_or_equal - Check whether the or of two bitmaps is equal to a third
  318. * @src1: Pointer to bitmap 1
  319. * @src2: Pointer to bitmap 2 will be or'ed with bitmap 1
  320. * @src3: Pointer to bitmap 3. Compare to the result of *@src1 | *@src2
  321. * @nbits: number of bits in each of these bitmaps
  322. *
  323. * Returns: True if (*@src1 | *@src2) == *@src3, false otherwise
  324. */
  325. static inline bool bitmap_or_equal(const unsigned long *src1,
  326. const unsigned long *src2,
  327. const unsigned long *src3,
  328. unsigned int nbits)
  329. {
  330. if (!small_const_nbits(nbits))
  331. return __bitmap_or_equal(src1, src2, src3, nbits);
  332. return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits));
  333. }
  334. static inline int bitmap_intersects(const unsigned long *src1,
  335. const unsigned long *src2, unsigned int nbits)
  336. {
  337. if (small_const_nbits(nbits))
  338. return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  339. else
  340. return __bitmap_intersects(src1, src2, nbits);
  341. }
  342. static inline int bitmap_subset(const unsigned long *src1,
  343. const unsigned long *src2, unsigned int nbits)
  344. {
  345. if (small_const_nbits(nbits))
  346. return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
  347. else
  348. return __bitmap_subset(src1, src2, nbits);
  349. }
  350. static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
  351. {
  352. if (small_const_nbits(nbits))
  353. return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
  354. return find_first_bit(src, nbits) == nbits;
  355. }
  356. static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
  357. {
  358. if (small_const_nbits(nbits))
  359. return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
  360. return find_first_zero_bit(src, nbits) == nbits;
  361. }
  362. static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
  363. {
  364. if (small_const_nbits(nbits))
  365. return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  366. return __bitmap_weight(src, nbits);
  367. }
  368. static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
  369. unsigned int nbits)
  370. {
  371. if (__builtin_constant_p(nbits) && nbits == 1)
  372. __set_bit(start, map);
  373. else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
  374. IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
  375. __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
  376. IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
  377. memset((char *)map + start / 8, 0xff, nbits / 8);
  378. else
  379. __bitmap_set(map, start, nbits);
  380. }
  381. static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
  382. unsigned int nbits)
  383. {
  384. if (__builtin_constant_p(nbits) && nbits == 1)
  385. __clear_bit(start, map);
  386. else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
  387. IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
  388. __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
  389. IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
  390. memset((char *)map + start / 8, 0, nbits / 8);
  391. else
  392. __bitmap_clear(map, start, nbits);
  393. }
  394. static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
  395. unsigned int shift, unsigned int nbits)
  396. {
  397. if (small_const_nbits(nbits))
  398. *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
  399. else
  400. __bitmap_shift_right(dst, src, shift, nbits);
  401. }
  402. static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
  403. unsigned int shift, unsigned int nbits)
  404. {
  405. if (small_const_nbits(nbits))
  406. *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
  407. else
  408. __bitmap_shift_left(dst, src, shift, nbits);
  409. }
  410. static inline void bitmap_replace(unsigned long *dst,
  411. const unsigned long *old,
  412. const unsigned long *new,
  413. const unsigned long *mask,
  414. unsigned int nbits)
  415. {
  416. if (small_const_nbits(nbits))
  417. *dst = (*old & ~(*mask)) | (*new & *mask);
  418. else
  419. __bitmap_replace(dst, old, new, mask, nbits);
  420. }
  421. static inline void bitmap_next_clear_region(unsigned long *bitmap,
  422. unsigned int *rs, unsigned int *re,
  423. unsigned int end)
  424. {
  425. *rs = find_next_zero_bit(bitmap, end, *rs);
  426. *re = find_next_bit(bitmap, end, *rs + 1);
  427. }
  428. static inline void bitmap_next_set_region(unsigned long *bitmap,
  429. unsigned int *rs, unsigned int *re,
  430. unsigned int end)
  431. {
  432. *rs = find_next_bit(bitmap, end, *rs);
  433. *re = find_next_zero_bit(bitmap, end, *rs + 1);
  434. }
  435. /*
  436. * Bitmap region iterators. Iterates over the bitmap between [@start, @end).
  437. * @rs and @re should be integer variables and will be set to start and end
  438. * index of the current clear or set region.
  439. */
  440. #define bitmap_for_each_clear_region(bitmap, rs, re, start, end) \
  441. for ((rs) = (start), \
  442. bitmap_next_clear_region((bitmap), &(rs), &(re), (end)); \
  443. (rs) < (re); \
  444. (rs) = (re) + 1, \
  445. bitmap_next_clear_region((bitmap), &(rs), &(re), (end)))
  446. #define bitmap_for_each_set_region(bitmap, rs, re, start, end) \
  447. for ((rs) = (start), \
  448. bitmap_next_set_region((bitmap), &(rs), &(re), (end)); \
  449. (rs) < (re); \
  450. (rs) = (re) + 1, \
  451. bitmap_next_set_region((bitmap), &(rs), &(re), (end)))
  452. /**
  453. * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
  454. * @n: u64 value
  455. *
  456. * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit
  457. * integers in 32-bit environment, and 64-bit integers in 64-bit one.
  458. *
  459. * There are four combinations of endianness and length of the word in linux
  460. * ABIs: LE64, BE64, LE32 and BE32.
  461. *
  462. * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in
  463. * bitmaps and therefore don't require any special handling.
  464. *
  465. * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory
  466. * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the
  467. * other hand is represented as an array of 32-bit words and the position of
  468. * bit N may therefore be calculated as: word #(N/32) and bit #(N%32) in that
  469. * word. For example, bit #42 is located at 10th position of 2nd word.
  470. * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
  471. * values in memory as it usually does. But for BE we need to swap hi and lo
  472. * words manually.
  473. *
  474. * With all that, the macro BITMAP_FROM_U64() does explicit reordering of hi and
  475. * lo parts of u64. For LE32 it does nothing, and for BE environment it swaps
  476. * hi and lo words, as is expected by bitmap.
  477. */
  478. #if __BITS_PER_LONG == 64
  479. #define BITMAP_FROM_U64(n) (n)
  480. #else
  481. #define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
  482. ((unsigned long) ((u64)(n) >> 32))
  483. #endif
  484. /**
  485. * bitmap_from_u64 - Check and swap words within u64.
  486. * @mask: source bitmap
  487. * @dst: destination bitmap
  488. *
  489. * In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]``
  490. * to read u64 mask, we will get the wrong word.
  491. * That is ``(u32 *)(&val)[0]`` gets the upper 32 bits,
  492. * but we expect the lower 32-bits of u64.
  493. */
  494. static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
  495. {
  496. dst[0] = mask & ULONG_MAX;
  497. if (sizeof(mask) > sizeof(unsigned long))
  498. dst[1] = mask >> 32;
  499. }
  500. /**
  501. * bitmap_get_value8 - get an 8-bit value within a memory region
  502. * @map: address to the bitmap memory region
  503. * @start: bit offset of the 8-bit value; must be a multiple of 8
  504. *
  505. * Returns the 8-bit value located at the @start bit offset within the @src
  506. * memory region.
  507. */
  508. static inline unsigned long bitmap_get_value8(const unsigned long *map,
  509. unsigned long start)
  510. {
  511. const size_t index = BIT_WORD(start);
  512. const unsigned long offset = start % BITS_PER_LONG;
  513. return (map[index] >> offset) & 0xFF;
  514. }
  515. /**
  516. * bitmap_set_value8 - set an 8-bit value within a memory region
  517. * @map: address to the bitmap memory region
  518. * @value: the 8-bit value; values wider than 8 bits may clobber bitmap
  519. * @start: bit offset of the 8-bit value; must be a multiple of 8
  520. */
  521. static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
  522. unsigned long start)
  523. {
  524. const size_t index = BIT_WORD(start);
  525. const unsigned long offset = start % BITS_PER_LONG;
  526. map[index] &= ~(0xFFUL << offset);
  527. map[index] |= value << offset;
  528. }
  529. #endif /* __ASSEMBLY__ */
  530. #endif /* __LINUX_BITMAP_H */