bitmap.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836
  1. /*
  2. * lib/bitmap.c
  3. * Helper functions for bitmap.h.
  4. *
  5. * This source code is licensed under the GNU General Public License,
  6. * Version 2. See the file COPYING for more details.
  7. */
  8. #include <linux/module.h>
  9. #include <linux/ctype.h>
  10. #include <linux/errno.h>
  11. #include <linux/bitmap.h>
  12. #include <linux/bitops.h>
  13. #include <asm/uaccess.h>
  14. /*
  15. * bitmaps provide an array of bits, implemented using an an
  16. * array of unsigned longs. The number of valid bits in a
  17. * given bitmap does _not_ need to be an exact multiple of
  18. * BITS_PER_LONG.
  19. *
  20. * The possible unused bits in the last, partially used word
  21. * of a bitmap are 'don't care'. The implementation makes
  22. * no particular effort to keep them zero. It ensures that
  23. * their value will not affect the results of any operation.
  24. * The bitmap operations that return Boolean (bitmap_empty,
  25. * for example) or scalar (bitmap_weight, for example) results
  26. * carefully filter out these unused bits from impacting their
  27. * results.
  28. *
  29. * These operations actually hold to a slightly stronger rule:
  30. * if you don't input any bitmaps to these ops that have some
  31. * unused bits set, then they won't output any set unused bits
  32. * in output bitmaps.
  33. *
  34. * The byte ordering of bitmaps is more natural on little
  35. * endian architectures. See the big-endian headers
  36. * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  37. * for the best explanations of this ordering.
  38. */
  39. int __bitmap_empty(const unsigned long *bitmap, int bits)
  40. {
  41. int k, lim = bits/BITS_PER_LONG;
  42. for (k = 0; k < lim; ++k)
  43. if (bitmap[k])
  44. return 0;
  45. if (bits % BITS_PER_LONG)
  46. if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
  47. return 0;
  48. return 1;
  49. }
  50. EXPORT_SYMBOL(__bitmap_empty);
  51. int __bitmap_full(const unsigned long *bitmap, int bits)
  52. {
  53. int k, lim = bits/BITS_PER_LONG;
  54. for (k = 0; k < lim; ++k)
  55. if (~bitmap[k])
  56. return 0;
  57. if (bits % BITS_PER_LONG)
  58. if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
  59. return 0;
  60. return 1;
  61. }
  62. EXPORT_SYMBOL(__bitmap_full);
  63. int __bitmap_equal(const unsigned long *bitmap1,
  64. const unsigned long *bitmap2, int bits)
  65. {
  66. int k, lim = bits/BITS_PER_LONG;
  67. for (k = 0; k < lim; ++k)
  68. if (bitmap1[k] != bitmap2[k])
  69. return 0;
  70. if (bits % BITS_PER_LONG)
  71. if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  72. return 0;
  73. return 1;
  74. }
  75. EXPORT_SYMBOL(__bitmap_equal);
  76. void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
  77. {
  78. int k, lim = bits/BITS_PER_LONG;
  79. for (k = 0; k < lim; ++k)
  80. dst[k] = ~src[k];
  81. if (bits % BITS_PER_LONG)
  82. dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
  83. }
  84. EXPORT_SYMBOL(__bitmap_complement);
  85. /**
  86. * __bitmap_shift_right - logical right shift of the bits in a bitmap
  87. * @dst : destination bitmap
  88. * @src : source bitmap
  89. * @shift : shift by this many bits
  90. * @bits : bitmap size, in bits
  91. *
  92. * Shifting right (dividing) means moving bits in the MS -> LS bit
  93. * direction. Zeros are fed into the vacated MS positions and the
  94. * LS bits shifted off the bottom are lost.
  95. */
  96. void __bitmap_shift_right(unsigned long *dst,
  97. const unsigned long *src, int shift, int bits)
  98. {
  99. int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
  100. int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
  101. unsigned long mask = (1UL << left) - 1;
  102. for (k = 0; off + k < lim; ++k) {
  103. unsigned long upper, lower;
  104. /*
  105. * If shift is not word aligned, take lower rem bits of
  106. * word above and make them the top rem bits of result.
  107. */
  108. if (!rem || off + k + 1 >= lim)
  109. upper = 0;
  110. else {
  111. upper = src[off + k + 1];
  112. if (off + k + 1 == lim - 1 && left)
  113. upper &= mask;
  114. }
  115. lower = src[off + k];
  116. if (left && off + k == lim - 1)
  117. lower &= mask;
  118. dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
  119. if (left && k == lim - 1)
  120. dst[k] &= mask;
  121. }
  122. if (off)
  123. memset(&dst[lim - off], 0, off*sizeof(unsigned long));
  124. }
  125. EXPORT_SYMBOL(__bitmap_shift_right);
  126. /**
  127. * __bitmap_shift_left - logical left shift of the bits in a bitmap
  128. * @dst : destination bitmap
  129. * @src : source bitmap
  130. * @shift : shift by this many bits
  131. * @bits : bitmap size, in bits
  132. *
  133. * Shifting left (multiplying) means moving bits in the LS -> MS
  134. * direction. Zeros are fed into the vacated LS bit positions
  135. * and those MS bits shifted off the top are lost.
  136. */
  137. void __bitmap_shift_left(unsigned long *dst,
  138. const unsigned long *src, int shift, int bits)
  139. {
  140. int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
  141. int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
  142. for (k = lim - off - 1; k >= 0; --k) {
  143. unsigned long upper, lower;
  144. /*
  145. * If shift is not word aligned, take upper rem bits of
  146. * word below and make them the bottom rem bits of result.
  147. */
  148. if (rem && k > 0)
  149. lower = src[k - 1];
  150. else
  151. lower = 0;
  152. upper = src[k];
  153. if (left && k == lim - 1)
  154. upper &= (1UL << left) - 1;
  155. dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
  156. if (left && k + off == lim - 1)
  157. dst[k + off] &= (1UL << left) - 1;
  158. }
  159. if (off)
  160. memset(dst, 0, off*sizeof(unsigned long));
  161. }
  162. EXPORT_SYMBOL(__bitmap_shift_left);
  163. void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  164. const unsigned long *bitmap2, int bits)
  165. {
  166. int k;
  167. int nr = BITS_TO_LONGS(bits);
  168. for (k = 0; k < nr; k++)
  169. dst[k] = bitmap1[k] & bitmap2[k];
  170. }
  171. EXPORT_SYMBOL(__bitmap_and);
  172. void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  173. const unsigned long *bitmap2, int bits)
  174. {
  175. int k;
  176. int nr = BITS_TO_LONGS(bits);
  177. for (k = 0; k < nr; k++)
  178. dst[k] = bitmap1[k] | bitmap2[k];
  179. }
  180. EXPORT_SYMBOL(__bitmap_or);
  181. void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  182. const unsigned long *bitmap2, int bits)
  183. {
  184. int k;
  185. int nr = BITS_TO_LONGS(bits);
  186. for (k = 0; k < nr; k++)
  187. dst[k] = bitmap1[k] ^ bitmap2[k];
  188. }
  189. EXPORT_SYMBOL(__bitmap_xor);
  190. void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  191. const unsigned long *bitmap2, int bits)
  192. {
  193. int k;
  194. int nr = BITS_TO_LONGS(bits);
  195. for (k = 0; k < nr; k++)
  196. dst[k] = bitmap1[k] & ~bitmap2[k];
  197. }
  198. EXPORT_SYMBOL(__bitmap_andnot);
  199. int __bitmap_intersects(const unsigned long *bitmap1,
  200. const unsigned long *bitmap2, int bits)
  201. {
  202. int k, lim = bits/BITS_PER_LONG;
  203. for (k = 0; k < lim; ++k)
  204. if (bitmap1[k] & bitmap2[k])
  205. return 1;
  206. if (bits % BITS_PER_LONG)
  207. if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  208. return 1;
  209. return 0;
  210. }
  211. EXPORT_SYMBOL(__bitmap_intersects);
  212. int __bitmap_subset(const unsigned long *bitmap1,
  213. const unsigned long *bitmap2, int bits)
  214. {
  215. int k, lim = bits/BITS_PER_LONG;
  216. for (k = 0; k < lim; ++k)
  217. if (bitmap1[k] & ~bitmap2[k])
  218. return 0;
  219. if (bits % BITS_PER_LONG)
  220. if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  221. return 0;
  222. return 1;
  223. }
  224. EXPORT_SYMBOL(__bitmap_subset);
  225. int __bitmap_weight(const unsigned long *bitmap, int bits)
  226. {
  227. int k, w = 0, lim = bits/BITS_PER_LONG;
  228. for (k = 0; k < lim; k++)
  229. w += hweight_long(bitmap[k]);
  230. if (bits % BITS_PER_LONG)
  231. w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  232. return w;
  233. }
  234. EXPORT_SYMBOL(__bitmap_weight);
  235. /*
  236. * Bitmap printing & parsing functions: first version by Bill Irwin,
  237. * second version by Paul Jackson, third by Joe Korty.
  238. */
  239. #define CHUNKSZ 32
  240. #define nbits_to_hold_value(val) fls(val)
  241. #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
  242. #define BASEDEC 10 /* fancier cpuset lists input in decimal */
  243. /**
  244. * bitmap_scnprintf - convert bitmap to an ASCII hex string.
  245. * @buf: byte buffer into which string is placed
  246. * @buflen: reserved size of @buf, in bytes
  247. * @maskp: pointer to bitmap to convert
  248. * @nmaskbits: size of bitmap, in bits
  249. *
  250. * Exactly @nmaskbits bits are displayed. Hex digits are grouped into
  251. * comma-separated sets of eight digits per set.
  252. */
  253. int bitmap_scnprintf(char *buf, unsigned int buflen,
  254. const unsigned long *maskp, int nmaskbits)
  255. {
  256. int i, word, bit, len = 0;
  257. unsigned long val;
  258. const char *sep = "";
  259. int chunksz;
  260. u32 chunkmask;
  261. chunksz = nmaskbits & (CHUNKSZ - 1);
  262. if (chunksz == 0)
  263. chunksz = CHUNKSZ;
  264. i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;
  265. for (; i >= 0; i -= CHUNKSZ) {
  266. chunkmask = ((1ULL << chunksz) - 1);
  267. word = i / BITS_PER_LONG;
  268. bit = i % BITS_PER_LONG;
  269. val = (maskp[word] >> bit) & chunkmask;
  270. len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
  271. (chunksz+3)/4, val);
  272. chunksz = CHUNKSZ;
  273. sep = ",";
  274. }
  275. return len;
  276. }
  277. EXPORT_SYMBOL(bitmap_scnprintf);
  278. /**
  279. * __bitmap_parse - convert an ASCII hex string into a bitmap.
  280. * @buf: pointer to buffer containing string.
  281. * @buflen: buffer size in bytes. If string is smaller than this
  282. * then it must be terminated with a \0.
  283. * @is_user: location of buffer, 0 indicates kernel space
  284. * @maskp: pointer to bitmap array that will contain result.
  285. * @nmaskbits: size of bitmap, in bits.
  286. *
  287. * Commas group hex digits into chunks. Each chunk defines exactly 32
  288. * bits of the resultant bitmask. No chunk may specify a value larger
  289. * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
  290. * then leading 0-bits are prepended. %-EINVAL is returned for illegal
  291. * characters and for grouping errors such as "1,,5", ",44", "," and "".
  292. * Leading and trailing whitespace accepted, but not embedded whitespace.
  293. */
  294. int __bitmap_parse(const char *buf, unsigned int buflen,
  295. int is_user, unsigned long *maskp,
  296. int nmaskbits)
  297. {
  298. int c, old_c, totaldigits, ndigits, nchunks, nbits;
  299. u32 chunk;
  300. const char __user *ubuf = buf;
  301. bitmap_zero(maskp, nmaskbits);
  302. nchunks = nbits = totaldigits = c = 0;
  303. do {
  304. chunk = ndigits = 0;
  305. /* Get the next chunk of the bitmap */
  306. while (buflen) {
  307. old_c = c;
  308. if (is_user) {
  309. if (__get_user(c, ubuf++))
  310. return -EFAULT;
  311. }
  312. else
  313. c = *buf++;
  314. buflen--;
  315. if (isspace(c))
  316. continue;
  317. /*
  318. * If the last character was a space and the current
  319. * character isn't '\0', we've got embedded whitespace.
  320. * This is a no-no, so throw an error.
  321. */
  322. if (totaldigits && c && isspace(old_c))
  323. return -EINVAL;
  324. /* A '\0' or a ',' signal the end of the chunk */
  325. if (c == '\0' || c == ',')
  326. break;
  327. if (!isxdigit(c))
  328. return -EINVAL;
  329. /*
  330. * Make sure there are at least 4 free bits in 'chunk'.
  331. * If not, this hexdigit will overflow 'chunk', so
  332. * throw an error.
  333. */
  334. if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
  335. return -EOVERFLOW;
  336. chunk = (chunk << 4) | unhex(c);
  337. ndigits++; totaldigits++;
  338. }
  339. if (ndigits == 0)
  340. return -EINVAL;
  341. if (nchunks == 0 && chunk == 0)
  342. continue;
  343. __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
  344. *maskp |= chunk;
  345. nchunks++;
  346. nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
  347. if (nbits > nmaskbits)
  348. return -EOVERFLOW;
  349. } while (buflen && c == ',');
  350. return 0;
  351. }
  352. EXPORT_SYMBOL(__bitmap_parse);
  353. /**
  354. * bitmap_parse_user()
  355. *
  356. * @ubuf: pointer to user buffer containing string.
  357. * @ulen: buffer size in bytes. If string is smaller than this
  358. * then it must be terminated with a \0.
  359. * @maskp: pointer to bitmap array that will contain result.
  360. * @nmaskbits: size of bitmap, in bits.
  361. *
  362. * Wrapper for __bitmap_parse(), providing it with user buffer.
  363. *
  364. * We cannot have this as an inline function in bitmap.h because it needs
  365. * linux/uaccess.h to get the access_ok() declaration and this causes
  366. * cyclic dependencies.
  367. */
  368. int bitmap_parse_user(const char __user *ubuf,
  369. unsigned int ulen, unsigned long *maskp,
  370. int nmaskbits)
  371. {
  372. if (!access_ok(VERIFY_READ, ubuf, ulen))
  373. return -EFAULT;
  374. return __bitmap_parse((const char *)ubuf, ulen, 1, maskp, nmaskbits);
  375. }
  376. EXPORT_SYMBOL(bitmap_parse_user);
  377. /*
  378. * bscnl_emit(buf, buflen, rbot, rtop, bp)
  379. *
  380. * Helper routine for bitmap_scnlistprintf(). Write decimal number
  381. * or range to buf, suppressing output past buf+buflen, with optional
  382. * comma-prefix. Return len of what would be written to buf, if it
  383. * all fit.
  384. */
  385. static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
  386. {
  387. if (len > 0)
  388. len += scnprintf(buf + len, buflen - len, ",");
  389. if (rbot == rtop)
  390. len += scnprintf(buf + len, buflen - len, "%d", rbot);
  391. else
  392. len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
  393. return len;
  394. }
  395. /**
  396. * bitmap_scnlistprintf - convert bitmap to list format ASCII string
  397. * @buf: byte buffer into which string is placed
  398. * @buflen: reserved size of @buf, in bytes
  399. * @maskp: pointer to bitmap to convert
  400. * @nmaskbits: size of bitmap, in bits
  401. *
  402. * Output format is a comma-separated list of decimal numbers and
  403. * ranges. Consecutively set bits are shown as two hyphen-separated
  404. * decimal numbers, the smallest and largest bit numbers set in
  405. * the range. Output format is compatible with the format
  406. * accepted as input by bitmap_parselist().
  407. *
  408. * The return value is the number of characters which would be
  409. * generated for the given input, excluding the trailing '\0', as
  410. * per ISO C99.
  411. */
  412. int bitmap_scnlistprintf(char *buf, unsigned int buflen,
  413. const unsigned long *maskp, int nmaskbits)
  414. {
  415. int len = 0;
  416. /* current bit is 'cur', most recently seen range is [rbot, rtop] */
  417. int cur, rbot, rtop;
  418. rbot = cur = find_first_bit(maskp, nmaskbits);
  419. while (cur < nmaskbits) {
  420. rtop = cur;
  421. cur = find_next_bit(maskp, nmaskbits, cur+1);
  422. if (cur >= nmaskbits || cur > rtop + 1) {
  423. len = bscnl_emit(buf, buflen, rbot, rtop, len);
  424. rbot = cur;
  425. }
  426. }
  427. return len;
  428. }
  429. EXPORT_SYMBOL(bitmap_scnlistprintf);
  430. /**
  431. * bitmap_parselist - convert list format ASCII string to bitmap
  432. * @bp: read nul-terminated user string from this buffer
  433. * @maskp: write resulting mask here
  434. * @nmaskbits: number of bits in mask to be written
  435. *
  436. * Input format is a comma-separated list of decimal numbers and
  437. * ranges. Consecutively set bits are shown as two hyphen-separated
  438. * decimal numbers, the smallest and largest bit numbers set in
  439. * the range.
  440. *
  441. * Returns 0 on success, -errno on invalid input strings.
  442. * Error values:
  443. * %-EINVAL: second number in range smaller than first
  444. * %-EINVAL: invalid character in string
  445. * %-ERANGE: bit number specified too large for mask
  446. */
  447. int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
  448. {
  449. unsigned a, b;
  450. bitmap_zero(maskp, nmaskbits);
  451. do {
  452. if (!isdigit(*bp))
  453. return -EINVAL;
  454. b = a = simple_strtoul(bp, (char **)&bp, BASEDEC);
  455. if (*bp == '-') {
  456. bp++;
  457. if (!isdigit(*bp))
  458. return -EINVAL;
  459. b = simple_strtoul(bp, (char **)&bp, BASEDEC);
  460. }
  461. if (!(a <= b))
  462. return -EINVAL;
  463. if (b >= nmaskbits)
  464. return -ERANGE;
  465. while (a <= b) {
  466. set_bit(a, maskp);
  467. a++;
  468. }
  469. if (*bp == ',')
  470. bp++;
  471. } while (*bp != '\0' && *bp != '\n');
  472. return 0;
  473. }
  474. EXPORT_SYMBOL(bitmap_parselist);
  475. /**
  476. * bitmap_pos_to_ord(buf, pos, bits)
  477. * @buf: pointer to a bitmap
  478. * @pos: a bit position in @buf (0 <= @pos < @bits)
  479. * @bits: number of valid bit positions in @buf
  480. *
  481. * Map the bit at position @pos in @buf (of length @bits) to the
  482. * ordinal of which set bit it is. If it is not set or if @pos
  483. * is not a valid bit position, map to -1.
  484. *
  485. * If for example, just bits 4 through 7 are set in @buf, then @pos
  486. * values 4 through 7 will get mapped to 0 through 3, respectively,
  487. * and other @pos values will get mapped to 0. When @pos value 7
  488. * gets mapped to (returns) @ord value 3 in this example, that means
  489. * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
  490. *
  491. * The bit positions 0 through @bits are valid positions in @buf.
  492. */
  493. static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
  494. {
  495. int i, ord;
  496. if (pos < 0 || pos >= bits || !test_bit(pos, buf))
  497. return -1;
  498. i = find_first_bit(buf, bits);
  499. ord = 0;
  500. while (i < pos) {
  501. i = find_next_bit(buf, bits, i + 1);
  502. ord++;
  503. }
  504. BUG_ON(i != pos);
  505. return ord;
  506. }
  507. /**
  508. * bitmap_ord_to_pos(buf, ord, bits)
  509. * @buf: pointer to bitmap
  510. * @ord: ordinal bit position (n-th set bit, n >= 0)
  511. * @bits: number of valid bit positions in @buf
  512. *
  513. * Map the ordinal offset of bit @ord in @buf to its position in @buf.
  514. * Value of @ord should be in range 0 <= @ord < weight(buf), else
  515. * results are undefined.
  516. *
  517. * If for example, just bits 4 through 7 are set in @buf, then @ord
  518. * values 0 through 3 will get mapped to 4 through 7, respectively,
  519. * and all other @ord values return undefined values. When @ord value 3
  520. * gets mapped to (returns) @pos value 7 in this example, that means
  521. * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
  522. *
  523. * The bit positions 0 through @bits are valid positions in @buf.
  524. */
  525. static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
  526. {
  527. int pos = 0;
  528. if (ord >= 0 && ord < bits) {
  529. int i;
  530. for (i = find_first_bit(buf, bits);
  531. i < bits && ord > 0;
  532. i = find_next_bit(buf, bits, i + 1))
  533. ord--;
  534. if (i < bits && ord == 0)
  535. pos = i;
  536. }
  537. return pos;
  538. }
  539. /**
  540. * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
  541. * @dst: remapped result
  542. * @src: subset to be remapped
  543. * @old: defines domain of map
  544. * @new: defines range of map
  545. * @bits: number of bits in each of these bitmaps
  546. *
  547. * Let @old and @new define a mapping of bit positions, such that
  548. * whatever position is held by the n-th set bit in @old is mapped
  549. * to the n-th set bit in @new. In the more general case, allowing
  550. * for the possibility that the weight 'w' of @new is less than the
  551. * weight of @old, map the position of the n-th set bit in @old to
  552. * the position of the m-th set bit in @new, where m == n % w.
  553. *
  554. * If either of the @old and @new bitmaps are empty, or if @src and
  555. * @dst point to the same location, then this routine copies @src
  556. * to @dst.
  557. *
  558. * The positions of unset bits in @old are mapped to themselves
  559. * (the identify map).
  560. *
  561. * Apply the above specified mapping to @src, placing the result in
  562. * @dst, clearing any bits previously set in @dst.
  563. *
  564. * For example, lets say that @old has bits 4 through 7 set, and
  565. * @new has bits 12 through 15 set. This defines the mapping of bit
  566. * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
  567. * bit positions unchanged. So if say @src comes into this routine
  568. * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
  569. * 13 and 15 set.
  570. */
  571. void bitmap_remap(unsigned long *dst, const unsigned long *src,
  572. const unsigned long *old, const unsigned long *new,
  573. int bits)
  574. {
  575. int oldbit, w;
  576. if (dst == src) /* following doesn't handle inplace remaps */
  577. return;
  578. bitmap_zero(dst, bits);
  579. w = bitmap_weight(new, bits);
  580. for (oldbit = find_first_bit(src, bits);
  581. oldbit < bits;
  582. oldbit = find_next_bit(src, bits, oldbit + 1)) {
  583. int n = bitmap_pos_to_ord(old, oldbit, bits);
  584. if (n < 0 || w == 0)
  585. set_bit(oldbit, dst); /* identity map */
  586. else
  587. set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
  588. }
  589. }
  590. EXPORT_SYMBOL(bitmap_remap);
  591. /**
  592. * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
  593. * @oldbit: bit position to be mapped
  594. * @old: defines domain of map
  595. * @new: defines range of map
  596. * @bits: number of bits in each of these bitmaps
  597. *
  598. * Let @old and @new define a mapping of bit positions, such that
  599. * whatever position is held by the n-th set bit in @old is mapped
  600. * to the n-th set bit in @new. In the more general case, allowing
  601. * for the possibility that the weight 'w' of @new is less than the
  602. * weight of @old, map the position of the n-th set bit in @old to
  603. * the position of the m-th set bit in @new, where m == n % w.
  604. *
  605. * The positions of unset bits in @old are mapped to themselves
  606. * (the identify map).
  607. *
  608. * Apply the above specified mapping to bit position @oldbit, returning
  609. * the new bit position.
  610. *
  611. * For example, lets say that @old has bits 4 through 7 set, and
  612. * @new has bits 12 through 15 set. This defines the mapping of bit
  613. * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
  614. * bit positions unchanged. So if say @oldbit is 5, then this routine
  615. * returns 13.
  616. */
  617. int bitmap_bitremap(int oldbit, const unsigned long *old,
  618. const unsigned long *new, int bits)
  619. {
  620. int w = bitmap_weight(new, bits);
  621. int n = bitmap_pos_to_ord(old, oldbit, bits);
  622. if (n < 0 || w == 0)
  623. return oldbit;
  624. else
  625. return bitmap_ord_to_pos(new, n % w, bits);
  626. }
  627. EXPORT_SYMBOL(bitmap_bitremap);
  628. /*
  629. * Common code for bitmap_*_region() routines.
  630. * bitmap: array of unsigned longs corresponding to the bitmap
  631. * pos: the beginning of the region
  632. * order: region size (log base 2 of number of bits)
  633. * reg_op: operation(s) to perform on that region of bitmap
  634. *
  635. * Can set, verify and/or release a region of bits in a bitmap,
  636. * depending on which combination of REG_OP_* flag bits is set.
  637. *
  638. * A region of a bitmap is a sequence of bits in the bitmap, of
  639. * some size '1 << order' (a power of two), aligned to that same
  640. * '1 << order' power of two.
  641. *
  642. * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
  643. * Returns 0 in all other cases and reg_ops.
  644. */
  645. enum {
  646. REG_OP_ISFREE, /* true if region is all zero bits */
  647. REG_OP_ALLOC, /* set all bits in region */
  648. REG_OP_RELEASE, /* clear all bits in region */
  649. };
  650. static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
  651. {
  652. int nbits_reg; /* number of bits in region */
  653. int index; /* index first long of region in bitmap */
  654. int offset; /* bit offset region in bitmap[index] */
  655. int nlongs_reg; /* num longs spanned by region in bitmap */
  656. int nbitsinlong; /* num bits of region in each spanned long */
  657. unsigned long mask; /* bitmask for one long of region */
  658. int i; /* scans bitmap by longs */
  659. int ret = 0; /* return value */
  660. /*
  661. * Either nlongs_reg == 1 (for small orders that fit in one long)
  662. * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
  663. */
  664. nbits_reg = 1 << order;
  665. index = pos / BITS_PER_LONG;
  666. offset = pos - (index * BITS_PER_LONG);
  667. nlongs_reg = BITS_TO_LONGS(nbits_reg);
  668. nbitsinlong = min(nbits_reg, BITS_PER_LONG);
  669. /*
  670. * Can't do "mask = (1UL << nbitsinlong) - 1", as that
  671. * overflows if nbitsinlong == BITS_PER_LONG.
  672. */
  673. mask = (1UL << (nbitsinlong - 1));
  674. mask += mask - 1;
  675. mask <<= offset;
  676. switch (reg_op) {
  677. case REG_OP_ISFREE:
  678. for (i = 0; i < nlongs_reg; i++) {
  679. if (bitmap[index + i] & mask)
  680. goto done;
  681. }
  682. ret = 1; /* all bits in region free (zero) */
  683. break;
  684. case REG_OP_ALLOC:
  685. for (i = 0; i < nlongs_reg; i++)
  686. bitmap[index + i] |= mask;
  687. break;
  688. case REG_OP_RELEASE:
  689. for (i = 0; i < nlongs_reg; i++)
  690. bitmap[index + i] &= ~mask;
  691. break;
  692. }
  693. done:
  694. return ret;
  695. }
  696. /**
  697. * bitmap_find_free_region - find a contiguous aligned mem region
  698. * @bitmap: array of unsigned longs corresponding to the bitmap
  699. * @bits: number of bits in the bitmap
  700. * @order: region size (log base 2 of number of bits) to find
  701. *
  702. * Find a region of free (zero) bits in a @bitmap of @bits bits and
  703. * allocate them (set them to one). Only consider regions of length
  704. * a power (@order) of two, aligned to that power of two, which
  705. * makes the search algorithm much faster.
  706. *
  707. * Return the bit offset in bitmap of the allocated region,
  708. * or -errno on failure.
  709. */
  710. int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
  711. {
  712. int pos; /* scans bitmap by regions of size order */
  713. for (pos = 0; pos < bits; pos += (1 << order))
  714. if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
  715. break;
  716. if (pos == bits)
  717. return -ENOMEM;
  718. __reg_op(bitmap, pos, order, REG_OP_ALLOC);
  719. return pos;
  720. }
  721. EXPORT_SYMBOL(bitmap_find_free_region);
  722. /**
  723. * bitmap_release_region - release allocated bitmap region
  724. * @bitmap: array of unsigned longs corresponding to the bitmap
  725. * @pos: beginning of bit region to release
  726. * @order: region size (log base 2 of number of bits) to release
  727. *
  728. * This is the complement to __bitmap_find_free_region() and releases
  729. * the found region (by clearing it in the bitmap).
  730. *
  731. * No return value.
  732. */
  733. void bitmap_release_region(unsigned long *bitmap, int pos, int order)
  734. {
  735. __reg_op(bitmap, pos, order, REG_OP_RELEASE);
  736. }
  737. EXPORT_SYMBOL(bitmap_release_region);
  738. /**
  739. * bitmap_allocate_region - allocate bitmap region
  740. * @bitmap: array of unsigned longs corresponding to the bitmap
  741. * @pos: beginning of bit region to allocate
  742. * @order: region size (log base 2 of number of bits) to allocate
  743. *
  744. * Allocate (set bits in) a specified region of a bitmap.
  745. *
  746. * Return 0 on success, or %-EBUSY if specified region wasn't
  747. * free (not all bits were zero).
  748. */
  749. int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
  750. {
  751. if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
  752. return -EBUSY;
  753. __reg_op(bitmap, pos, order, REG_OP_ALLOC);
  754. return 0;
  755. }
  756. EXPORT_SYMBOL(bitmap_allocate_region);