bitmap.c 38 KB

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