bitmap.h 22 KB

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