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/export.h> |

9 | #include <linux/thread_info.h> |

10 | #include <linux/ctype.h> |

11 | #include <linux/errno.h> |

12 | #include <linux/bitmap.h> |

13 | #include <linux/bitops.h> |

14 | #include <linux/bug.h> |

15 | #include <linux/kernel.h> |

16 | #include <linux/mm.h> |

17 | #include <linux/slab.h> |

18 | #include <linux/string.h> |

19 | #include <linux/uaccess.h> |

20 | |

21 | #include <asm/page.h> |

22 | |

23 | /** |

24 | * DOC: bitmap introduction |

25 | * |

26 | * bitmaps provide an array of bits, implemented using an an |

27 | * array of unsigned longs. The number of valid bits in a |

28 | * given bitmap does _not_ need to be an exact multiple of |

29 | * BITS_PER_LONG. |

30 | * |

31 | * The possible unused bits in the last, partially used word |

32 | * of a bitmap are 'don't care'. The implementation makes |

33 | * no particular effort to keep them zero. It ensures that |

34 | * their value will not affect the results of any operation. |

35 | * The bitmap operations that return Boolean (bitmap_empty, |

36 | * for example) or scalar (bitmap_weight, for example) results |

37 | * carefully filter out these unused bits from impacting their |

38 | * results. |

39 | * |

40 | * The byte ordering of bitmaps is more natural on little |

41 | * endian architectures. See the big-endian headers |

42 | * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h |

43 | * for the best explanations of this ordering. |

44 | */ |

45 | |

46 | int __bitmap_equal(const unsigned long *bitmap1, |

47 | const unsigned long *bitmap2, unsigned int bits) |

48 | { |

49 | unsigned int k, lim = bits/BITS_PER_LONG; |

50 | for (k = 0; k < lim; ++k) |

51 | if (bitmap1[k] != bitmap2[k]) |

52 | return 0; |

53 | |

54 | if (bits % BITS_PER_LONG) |

55 | if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) |

56 | return 0; |

57 | |

58 | return 1; |

59 | } |

60 | EXPORT_SYMBOL(__bitmap_equal); |

61 | |

62 | void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits) |

63 | { |

64 | unsigned int k, lim = BITS_TO_LONGS(bits); |

65 | for (k = 0; k < lim; ++k) |

66 | dst[k] = ~src[k]; |

67 | } |

68 | EXPORT_SYMBOL(__bitmap_complement); |

69 | |

70 | /** |

71 | * __bitmap_shift_right - logical right shift of the bits in a bitmap |

72 | * @dst : destination bitmap |

73 | * @src : source bitmap |

74 | * @shift : shift by this many bits |

75 | * @nbits : bitmap size, in bits |

76 | * |

77 | * Shifting right (dividing) means moving bits in the MS -> LS bit |

78 | * direction. Zeros are fed into the vacated MS positions and the |

79 | * LS bits shifted off the bottom are lost. |

80 | */ |

81 | void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, |

82 | unsigned shift, unsigned nbits) |

83 | { |

84 | unsigned k, lim = BITS_TO_LONGS(nbits); |

85 | unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; |

86 | unsigned long mask = BITMAP_LAST_WORD_MASK(nbits); |

87 | for (k = 0; off + k < lim; ++k) { |

88 | unsigned long upper, lower; |

89 | |

90 | /* |

91 | * If shift is not word aligned, take lower rem bits of |

92 | * word above and make them the top rem bits of result. |

93 | */ |

94 | if (!rem || off + k + 1 >= lim) |

95 | upper = 0; |

96 | else { |

97 | upper = src[off + k + 1]; |

98 | if (off + k + 1 == lim - 1) |

99 | upper &= mask; |

100 | upper <<= (BITS_PER_LONG - rem); |

101 | } |

102 | lower = src[off + k]; |

103 | if (off + k == lim - 1) |

104 | lower &= mask; |

105 | lower >>= rem; |

106 | dst[k] = lower | upper; |

107 | } |

108 | if (off) |

109 | memset(&dst[lim - off], 0, off*sizeof(unsigned long)); |

110 | } |

111 | EXPORT_SYMBOL(__bitmap_shift_right); |

112 | |

113 | |

114 | /** |

115 | * __bitmap_shift_left - logical left shift of the bits in a bitmap |

116 | * @dst : destination bitmap |

117 | * @src : source bitmap |

118 | * @shift : shift by this many bits |

119 | * @nbits : bitmap size, in bits |

120 | * |

121 | * Shifting left (multiplying) means moving bits in the LS -> MS |

122 | * direction. Zeros are fed into the vacated LS bit positions |

123 | * and those MS bits shifted off the top are lost. |

124 | */ |

125 | |

126 | void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, |

127 | unsigned int shift, unsigned int nbits) |

128 | { |

129 | int k; |

130 | unsigned int lim = BITS_TO_LONGS(nbits); |

131 | unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; |

132 | for (k = lim - off - 1; k >= 0; --k) { |

133 | unsigned long upper, lower; |

134 | |

135 | /* |

136 | * If shift is not word aligned, take upper rem bits of |

137 | * word below and make them the bottom rem bits of result. |

138 | */ |

139 | if (rem && k > 0) |

140 | lower = src[k - 1] >> (BITS_PER_LONG - rem); |

141 | else |

142 | lower = 0; |

143 | upper = src[k] << rem; |

144 | dst[k + off] = lower | upper; |

145 | } |

146 | if (off) |

147 | memset(dst, 0, off*sizeof(unsigned long)); |

148 | } |

149 | EXPORT_SYMBOL(__bitmap_shift_left); |

150 | |

151 | int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |

152 | const unsigned long *bitmap2, unsigned int bits) |

153 | { |

154 | unsigned int k; |

155 | unsigned int lim = bits/BITS_PER_LONG; |

156 | unsigned long result = 0; |

157 | |

158 | for (k = 0; k < lim; k++) |

159 | result |= (dst[k] = bitmap1[k] & bitmap2[k]); |

160 | if (bits % BITS_PER_LONG) |

161 | result |= (dst[k] = bitmap1[k] & bitmap2[k] & |

162 | BITMAP_LAST_WORD_MASK(bits)); |

163 | return result != 0; |

164 | } |

165 | EXPORT_SYMBOL(__bitmap_and); |

166 | |

167 | void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |

168 | const unsigned long *bitmap2, unsigned int bits) |

169 | { |

170 | unsigned int k; |

171 | unsigned int nr = BITS_TO_LONGS(bits); |

172 | |

173 | for (k = 0; k < nr; k++) |

174 | dst[k] = bitmap1[k] | bitmap2[k]; |

175 | } |

176 | EXPORT_SYMBOL(__bitmap_or); |

177 | |

178 | void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, |

179 | const unsigned long *bitmap2, unsigned int bits) |

180 | { |

181 | unsigned int k; |

182 | unsigned int nr = BITS_TO_LONGS(bits); |

183 | |

184 | for (k = 0; k < nr; k++) |

185 | dst[k] = bitmap1[k] ^ bitmap2[k]; |

186 | } |

187 | EXPORT_SYMBOL(__bitmap_xor); |

188 | |

189 | int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |

190 | const unsigned long *bitmap2, unsigned int bits) |

191 | { |

192 | unsigned int k; |

193 | unsigned int lim = bits/BITS_PER_LONG; |

194 | unsigned long result = 0; |

195 | |

196 | for (k = 0; k < lim; k++) |

197 | result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); |

198 | if (bits % BITS_PER_LONG) |

199 | result |= (dst[k] = bitmap1[k] & ~bitmap2[k] & |

200 | BITMAP_LAST_WORD_MASK(bits)); |

201 | return result != 0; |

202 | } |

203 | EXPORT_SYMBOL(__bitmap_andnot); |

204 | |

205 | int __bitmap_intersects(const unsigned long *bitmap1, |

206 | const unsigned long *bitmap2, unsigned int bits) |

207 | { |

208 | unsigned int k, lim = bits/BITS_PER_LONG; |

209 | for (k = 0; k < lim; ++k) |

210 | if (bitmap1[k] & bitmap2[k]) |

211 | return 1; |

212 | |

213 | if (bits % BITS_PER_LONG) |

214 | if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) |

215 | return 1; |

216 | return 0; |

217 | } |

218 | EXPORT_SYMBOL(__bitmap_intersects); |

219 | |

220 | int __bitmap_subset(const unsigned long *bitmap1, |

221 | const unsigned long *bitmap2, unsigned int bits) |

222 | { |

223 | unsigned int k, lim = bits/BITS_PER_LONG; |

224 | for (k = 0; k < lim; ++k) |

225 | if (bitmap1[k] & ~bitmap2[k]) |

226 | return 0; |

227 | |

228 | if (bits % BITS_PER_LONG) |

229 | if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) |

230 | return 0; |

231 | return 1; |

232 | } |

233 | EXPORT_SYMBOL(__bitmap_subset); |

234 | |

235 | int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) |

236 | { |

237 | unsigned int k, lim = bits/BITS_PER_LONG; |

238 | int w = 0; |

239 | |

240 | for (k = 0; k < lim; k++) |

241 | w += hweight_long(bitmap[k]); |

242 | |

243 | if (bits % BITS_PER_LONG) |

244 | w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); |

245 | |

246 | return w; |

247 | } |

248 | EXPORT_SYMBOL(__bitmap_weight); |

249 | |

250 | void __bitmap_set(unsigned long *map, unsigned int start, int len) |

251 | { |

252 | unsigned long *p = map + BIT_WORD(start); |

253 | const unsigned int size = start + len; |

254 | int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); |

255 | unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); |

256 | |

257 | while (len - bits_to_set >= 0) { |

258 | *p |= mask_to_set; |

259 | len -= bits_to_set; |

260 | bits_to_set = BITS_PER_LONG; |

261 | mask_to_set = ~0UL; |

262 | p++; |

263 | } |

264 | if (len) { |

265 | mask_to_set &= BITMAP_LAST_WORD_MASK(size); |

266 | *p |= mask_to_set; |

267 | } |

268 | } |

269 | EXPORT_SYMBOL(__bitmap_set); |

270 | |

271 | void __bitmap_clear(unsigned long *map, unsigned int start, int len) |

272 | { |

273 | unsigned long *p = map + BIT_WORD(start); |

274 | const unsigned int size = start + len; |

275 | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); |

276 | unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); |

277 | |

278 | while (len - bits_to_clear >= 0) { |

279 | *p &= ~mask_to_clear; |

280 | len -= bits_to_clear; |

281 | bits_to_clear = BITS_PER_LONG; |

282 | mask_to_clear = ~0UL; |

283 | p++; |

284 | } |

285 | if (len) { |

286 | mask_to_clear &= BITMAP_LAST_WORD_MASK(size); |

287 | *p &= ~mask_to_clear; |

288 | } |

289 | } |

290 | EXPORT_SYMBOL(__bitmap_clear); |

291 | |

292 | /** |

293 | * bitmap_find_next_zero_area_off - find a contiguous aligned zero area |

294 | * @map: The address to base the search on |

295 | * @size: The bitmap size in bits |

296 | * @start: The bitnumber to start searching at |

297 | * @nr: The number of zeroed bits we're looking for |

298 | * @align_mask: Alignment mask for zero area |

299 | * @align_offset: Alignment offset for zero area. |

300 | * |

301 | * The @align_mask should be one less than a power of 2; the effect is that |

302 | * the bit offset of all zero areas this function finds plus @align_offset |

303 | * is multiple of that power of 2. |

304 | */ |

305 | unsigned long bitmap_find_next_zero_area_off(unsigned long *map, |

306 | unsigned long size, |

307 | unsigned long start, |

308 | unsigned int nr, |

309 | unsigned long align_mask, |

310 | unsigned long align_offset) |

311 | { |

312 | unsigned long index, end, i; |

313 | again: |

314 | index = find_next_zero_bit(map, size, start); |

315 | |

316 | /* Align allocation */ |

317 | index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset; |

318 | |

319 | end = index + nr; |

320 | if (end > size) |

321 | return end; |

322 | i = find_next_bit(map, end, index); |

323 | if (i < end) { |

324 | start = i + 1; |

325 | goto again; |

326 | } |

327 | return index; |

328 | } |

329 | EXPORT_SYMBOL(bitmap_find_next_zero_area_off); |

330 | |

331 | /* |

332 | * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers, |

333 | * second version by Paul Jackson, third by Joe Korty. |

334 | */ |

335 | |

336 | #define CHUNKSZ 32 |

337 | #define nbits_to_hold_value(val) fls(val) |

338 | #define BASEDEC 10 /* fancier cpuset lists input in decimal */ |

339 | |

340 | /** |

341 | * __bitmap_parse - convert an ASCII hex string into a bitmap. |

342 | * @buf: pointer to buffer containing string. |

343 | * @buflen: buffer size in bytes. If string is smaller than this |

344 | * then it must be terminated with a \0. |

345 | * @is_user: location of buffer, 0 indicates kernel space |

346 | * @maskp: pointer to bitmap array that will contain result. |

347 | * @nmaskbits: size of bitmap, in bits. |

348 | * |

349 | * Commas group hex digits into chunks. Each chunk defines exactly 32 |

350 | * bits of the resultant bitmask. No chunk may specify a value larger |

351 | * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value |

352 | * then leading 0-bits are prepended. %-EINVAL is returned for illegal |

353 | * characters and for grouping errors such as "1,,5", ",44", "," and "". |

354 | * Leading and trailing whitespace accepted, but not embedded whitespace. |

355 | */ |

356 | int __bitmap_parse(const char *buf, unsigned int buflen, |

357 | int is_user, unsigned long *maskp, |

358 | int nmaskbits) |

359 | { |

360 | int c, old_c, totaldigits, ndigits, nchunks, nbits; |

361 | u32 chunk; |

362 | const char __user __force *ubuf = (const char __user __force *)buf; |

363 | |

364 | bitmap_zero(maskp, nmaskbits); |

365 | |

366 | nchunks = nbits = totaldigits = c = 0; |

367 | do { |

368 | chunk = 0; |

369 | ndigits = totaldigits; |

370 | |

371 | /* Get the next chunk of the bitmap */ |

372 | while (buflen) { |

373 | old_c = c; |

374 | if (is_user) { |

375 | if (__get_user(c, ubuf++)) |

376 | return -EFAULT; |

377 | } |

378 | else |

379 | c = *buf++; |

380 | buflen--; |

381 | if (isspace(c)) |

382 | continue; |

383 | |

384 | /* |

385 | * If the last character was a space and the current |

386 | * character isn't '\0', we've got embedded whitespace. |

387 | * This is a no-no, so throw an error. |

388 | */ |

389 | if (totaldigits && c && isspace(old_c)) |

390 | return -EINVAL; |

391 | |

392 | /* A '\0' or a ',' signal the end of the chunk */ |

393 | if (c == '\0' || c == ',') |

394 | break; |

395 | |

396 | if (!isxdigit(c)) |

397 | return -EINVAL; |

398 | |

399 | /* |

400 | * Make sure there are at least 4 free bits in 'chunk'. |

401 | * If not, this hexdigit will overflow 'chunk', so |

402 | * throw an error. |

403 | */ |

404 | if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1)) |

405 | return -EOVERFLOW; |

406 | |

407 | chunk = (chunk << 4) | hex_to_bin(c); |

408 | totaldigits++; |

409 | } |

410 | if (ndigits == totaldigits) |

411 | return -EINVAL; |

412 | if (nchunks == 0 && chunk == 0) |

413 | continue; |

414 | |

415 | __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); |

416 | *maskp |= chunk; |

417 | nchunks++; |

418 | nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; |

419 | if (nbits > nmaskbits) |

420 | return -EOVERFLOW; |

421 | } while (buflen && c == ','); |

422 | |

423 | return 0; |

424 | } |

425 | EXPORT_SYMBOL(__bitmap_parse); |

426 | |

427 | /** |

428 | * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap |

429 | * |

430 | * @ubuf: pointer to user buffer containing string. |

431 | * @ulen: buffer size in bytes. If string is smaller than this |

432 | * then it must be terminated with a \0. |

433 | * @maskp: pointer to bitmap array that will contain result. |

434 | * @nmaskbits: size of bitmap, in bits. |

435 | * |

436 | * Wrapper for __bitmap_parse(), providing it with user buffer. |

437 | * |

438 | * We cannot have this as an inline function in bitmap.h because it needs |

439 | * linux/uaccess.h to get the access_ok() declaration and this causes |

440 | * cyclic dependencies. |

441 | */ |

442 | int bitmap_parse_user(const char __user *ubuf, |

443 | unsigned int ulen, unsigned long *maskp, |

444 | int nmaskbits) |

445 | { |

446 | if (!access_ok(ubuf, ulen)) |

447 | return -EFAULT; |

448 | return __bitmap_parse((const char __force *)ubuf, |

449 | ulen, 1, maskp, nmaskbits); |

450 | |

451 | } |

452 | EXPORT_SYMBOL(bitmap_parse_user); |

453 | |

454 | /** |

455 | * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string |

456 | * @list: indicates whether the bitmap must be list |

457 | * @buf: page aligned buffer into which string is placed |

458 | * @maskp: pointer to bitmap to convert |

459 | * @nmaskbits: size of bitmap, in bits |

460 | * |

461 | * Output format is a comma-separated list of decimal numbers and |

462 | * ranges if list is specified or hex digits grouped into comma-separated |

463 | * sets of 8 digits/set. Returns the number of characters written to buf. |

464 | * |

465 | * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned |

466 | * area and that sufficient storage remains at @buf to accommodate the |

467 | * bitmap_print_to_pagebuf() output. Returns the number of characters |

468 | * actually printed to @buf, excluding terminating '\0'. |

469 | */ |

470 | int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, |

471 | int nmaskbits) |

472 | { |

473 | ptrdiff_t len = PAGE_SIZE - offset_in_page(buf); |

474 | |

475 | return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) : |

476 | scnprintf(buf, len, "%*pb\n", nmaskbits, maskp); |

477 | } |

478 | EXPORT_SYMBOL(bitmap_print_to_pagebuf); |

479 | |

480 | /** |

481 | * __bitmap_parselist - convert list format ASCII string to bitmap |

482 | * @buf: read nul-terminated user string from this buffer |

483 | * @buflen: buffer size in bytes. If string is smaller than this |

484 | * then it must be terminated with a \0. |

485 | * @is_user: location of buffer, 0 indicates kernel space |

486 | * @maskp: write resulting mask here |

487 | * @nmaskbits: number of bits in mask to be written |

488 | * |

489 | * Input format is a comma-separated list of decimal numbers and |

490 | * ranges. Consecutively set bits are shown as two hyphen-separated |

491 | * decimal numbers, the smallest and largest bit numbers set in |

492 | * the range. |

493 | * Optionally each range can be postfixed to denote that only parts of it |

494 | * should be set. The range will divided to groups of specific size. |

495 | * From each group will be used only defined amount of bits. |

496 | * Syntax: range:used_size/group_size |

497 | * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769 |

498 | * |

499 | * Returns: 0 on success, -errno on invalid input strings. Error values: |

500 | * |

501 | * - ``-EINVAL``: second number in range smaller than first |

502 | * - ``-EINVAL``: invalid character in string |

503 | * - ``-ERANGE``: bit number specified too large for mask |

504 | */ |

505 | static int __bitmap_parselist(const char *buf, unsigned int buflen, |

506 | int is_user, unsigned long *maskp, |

507 | int nmaskbits) |

508 | { |

509 | unsigned int a, b, old_a, old_b; |

510 | unsigned int group_size, used_size, off; |

511 | int c, old_c, totaldigits, ndigits; |

512 | const char __user __force *ubuf = (const char __user __force *)buf; |

513 | int at_start, in_range, in_partial_range; |

514 | |

515 | totaldigits = c = 0; |

516 | old_a = old_b = 0; |

517 | group_size = used_size = 0; |

518 | bitmap_zero(maskp, nmaskbits); |

519 | do { |

520 | at_start = 1; |

521 | in_range = 0; |

522 | in_partial_range = 0; |

523 | a = b = 0; |

524 | ndigits = totaldigits; |

525 | |

526 | /* Get the next cpu# or a range of cpu#'s */ |

527 | while (buflen) { |

528 | old_c = c; |

529 | if (is_user) { |

530 | if (__get_user(c, ubuf++)) |

531 | return -EFAULT; |

532 | } else |

533 | c = *buf++; |

534 | buflen--; |

535 | if (isspace(c)) |

536 | continue; |

537 | |

538 | /* A '\0' or a ',' signal the end of a cpu# or range */ |

539 | if (c == '\0' || c == ',') |

540 | break; |

541 | /* |

542 | * whitespaces between digits are not allowed, |

543 | * but it's ok if whitespaces are on head or tail. |

544 | * when old_c is whilespace, |

545 | * if totaldigits == ndigits, whitespace is on head. |

546 | * if whitespace is on tail, it should not run here. |

547 | * as c was ',' or '\0', |

548 | * the last code line has broken the current loop. |

549 | */ |

550 | if ((totaldigits != ndigits) && isspace(old_c)) |

551 | return -EINVAL; |

552 | |

553 | if (c == '/') { |

554 | used_size = a; |

555 | at_start = 1; |

556 | in_range = 0; |

557 | a = b = 0; |

558 | continue; |

559 | } |

560 | |

561 | if (c == ':') { |

562 | old_a = a; |

563 | old_b = b; |

564 | at_start = 1; |

565 | in_range = 0; |

566 | in_partial_range = 1; |

567 | a = b = 0; |

568 | continue; |

569 | } |

570 | |

571 | if (c == '-') { |

572 | if (at_start || in_range) |

573 | return -EINVAL; |

574 | b = 0; |

575 | in_range = 1; |

576 | at_start = 1; |

577 | continue; |

578 | } |

579 | |

580 | if (!isdigit(c)) |

581 | return -EINVAL; |

582 | |

583 | b = b * 10 + (c - '0'); |

584 | if (!in_range) |

585 | a = b; |

586 | at_start = 0; |

587 | totaldigits++; |

588 | } |

589 | if (ndigits == totaldigits) |

590 | continue; |

591 | if (in_partial_range) { |

592 | group_size = a; |

593 | a = old_a; |

594 | b = old_b; |

595 | old_a = old_b = 0; |

596 | } else { |

597 | used_size = group_size = b - a + 1; |

598 | } |

599 | /* if no digit is after '-', it's wrong*/ |

600 | if (at_start && in_range) |

601 | return -EINVAL; |

602 | if (!(a <= b) || group_size == 0 || !(used_size <= group_size)) |

603 | return -EINVAL; |

604 | if (b >= nmaskbits) |

605 | return -ERANGE; |

606 | while (a <= b) { |

607 | off = min(b - a + 1, used_size); |

608 | bitmap_set(maskp, a, off); |

609 | a += group_size; |

610 | } |

611 | } while (buflen && c == ','); |

612 | return 0; |

613 | } |

614 | |

615 | int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) |

616 | { |

617 | char *nl = strchrnul(bp, '\n'); |

618 | int len = nl - bp; |

619 | |

620 | return __bitmap_parselist(bp, len, 0, maskp, nmaskbits); |

621 | } |

622 | EXPORT_SYMBOL(bitmap_parselist); |

623 | |

624 | |

625 | /** |

626 | * bitmap_parselist_user() |

627 | * |

628 | * @ubuf: pointer to user buffer containing string. |

629 | * @ulen: buffer size in bytes. If string is smaller than this |

630 | * then it must be terminated with a \0. |

631 | * @maskp: pointer to bitmap array that will contain result. |

632 | * @nmaskbits: size of bitmap, in bits. |

633 | * |

634 | * Wrapper for bitmap_parselist(), providing it with user buffer. |

635 | * |

636 | * We cannot have this as an inline function in bitmap.h because it needs |

637 | * linux/uaccess.h to get the access_ok() declaration and this causes |

638 | * cyclic dependencies. |

639 | */ |

640 | int bitmap_parselist_user(const char __user *ubuf, |

641 | unsigned int ulen, unsigned long *maskp, |

642 | int nmaskbits) |

643 | { |

644 | if (!access_ok(ubuf, ulen)) |

645 | return -EFAULT; |

646 | return __bitmap_parselist((const char __force *)ubuf, |

647 | ulen, 1, maskp, nmaskbits); |

648 | } |

649 | EXPORT_SYMBOL(bitmap_parselist_user); |

650 | |

651 | |

652 | /** |

653 | * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap |

654 | * @buf: pointer to a bitmap |

655 | * @pos: a bit position in @buf (0 <= @pos < @nbits) |

656 | * @nbits: number of valid bit positions in @buf |

657 | * |

658 | * Map the bit at position @pos in @buf (of length @nbits) to the |

659 | * ordinal of which set bit it is. If it is not set or if @pos |

660 | * is not a valid bit position, map to -1. |

661 | * |

662 | * If for example, just bits 4 through 7 are set in @buf, then @pos |

663 | * values 4 through 7 will get mapped to 0 through 3, respectively, |

664 | * and other @pos values will get mapped to -1. When @pos value 7 |

665 | * gets mapped to (returns) @ord value 3 in this example, that means |

666 | * that bit 7 is the 3rd (starting with 0th) set bit in @buf. |

667 | * |

668 | * The bit positions 0 through @bits are valid positions in @buf. |

669 | */ |

670 | static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits) |

671 | { |

672 | if (pos >= nbits || !test_bit(pos, buf)) |

673 | return -1; |

674 | |

675 | return __bitmap_weight(buf, pos); |

676 | } |

677 | |

678 | /** |

679 | * bitmap_ord_to_pos - find position of n-th set bit in bitmap |

680 | * @buf: pointer to bitmap |

681 | * @ord: ordinal bit position (n-th set bit, n >= 0) |

682 | * @nbits: number of valid bit positions in @buf |

683 | * |

684 | * Map the ordinal offset of bit @ord in @buf to its position in @buf. |

685 | * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord |

686 | * >= weight(buf), returns @nbits. |

687 | * |

688 | * If for example, just bits 4 through 7 are set in @buf, then @ord |

689 | * values 0 through 3 will get mapped to 4 through 7, respectively, |

690 | * and all other @ord values returns @nbits. When @ord value 3 |

691 | * gets mapped to (returns) @pos value 7 in this example, that means |

692 | * that the 3rd set bit (starting with 0th) is at position 7 in @buf. |

693 | * |

694 | * The bit positions 0 through @nbits-1 are valid positions in @buf. |

695 | */ |

696 | unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits) |

697 | { |

698 | unsigned int pos; |

699 | |

700 | for (pos = find_first_bit(buf, nbits); |

701 | pos < nbits && ord; |

702 | pos = find_next_bit(buf, nbits, pos + 1)) |

703 | ord--; |

704 | |

705 | return pos; |

706 | } |

707 | |

708 | /** |

709 | * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap |

710 | * @dst: remapped result |

711 | * @src: subset to be remapped |

712 | * @old: defines domain of map |

713 | * @new: defines range of map |

714 | * @nbits: number of bits in each of these bitmaps |

715 | * |

716 | * Let @old and @new define a mapping of bit positions, such that |

717 | * whatever position is held by the n-th set bit in @old is mapped |

718 | * to the n-th set bit in @new. In the more general case, allowing |

719 | * for the possibility that the weight 'w' of @new is less than the |

720 | * weight of @old, map the position of the n-th set bit in @old to |

721 | * the position of the m-th set bit in @new, where m == n % w. |

722 | * |

723 | * If either of the @old and @new bitmaps are empty, or if @src and |

724 | * @dst point to the same location, then this routine copies @src |

725 | * to @dst. |

726 | * |

727 | * The positions of unset bits in @old are mapped to themselves |

728 | * (the identify map). |

729 | * |

730 | * Apply the above specified mapping to @src, placing the result in |

731 | * @dst, clearing any bits previously set in @dst. |

732 | * |

733 | * For example, lets say that @old has bits 4 through 7 set, and |

734 | * @new has bits 12 through 15 set. This defines the mapping of bit |

735 | * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other |

736 | * bit positions unchanged. So if say @src comes into this routine |

737 | * with bits 1, 5 and 7 set, then @dst should leave with bits 1, |

738 | * 13 and 15 set. |

739 | */ |

740 | void bitmap_remap(unsigned long *dst, const unsigned long *src, |

741 | const unsigned long *old, const unsigned long *new, |

742 | unsigned int nbits) |

743 | { |

744 | unsigned int oldbit, w; |

745 | |

746 | if (dst == src) /* following doesn't handle inplace remaps */ |

747 | return; |

748 | bitmap_zero(dst, nbits); |

749 | |

750 | w = bitmap_weight(new, nbits); |

751 | for_each_set_bit(oldbit, src, nbits) { |

752 | int n = bitmap_pos_to_ord(old, oldbit, nbits); |

753 | |

754 | if (n < 0 || w == 0) |

755 | set_bit(oldbit, dst); /* identity map */ |

756 | else |

757 | set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst); |

758 | } |

759 | } |

760 | EXPORT_SYMBOL(bitmap_remap); |

761 | |

762 | /** |

763 | * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit |

764 | * @oldbit: bit position to be mapped |

765 | * @old: defines domain of map |

766 | * @new: defines range of map |

767 | * @bits: number of bits in each of these bitmaps |

768 | * |

769 | * Let @old and @new define a mapping of bit positions, such that |

770 | * whatever position is held by the n-th set bit in @old is mapped |

771 | * to the n-th set bit in @new. In the more general case, allowing |

772 | * for the possibility that the weight 'w' of @new is less than the |

773 | * weight of @old, map the position of the n-th set bit in @old to |

774 | * the position of the m-th set bit in @new, where m == n % w. |

775 | * |

776 | * The positions of unset bits in @old are mapped to themselves |

777 | * (the identify map). |

778 | * |

779 | * Apply the above specified mapping to bit position @oldbit, returning |

780 | * the new bit position. |

781 | * |

782 | * For example, lets say that @old has bits 4 through 7 set, and |

783 | * @new has bits 12 through 15 set. This defines the mapping of bit |

784 | * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other |

785 | * bit positions unchanged. So if say @oldbit is 5, then this routine |

786 | * returns 13. |

787 | */ |

788 | int bitmap_bitremap(int oldbit, const unsigned long *old, |

789 | const unsigned long *new, int bits) |

790 | { |

791 | int w = bitmap_weight(new, bits); |

792 | int n = bitmap_pos_to_ord(old, oldbit, bits); |

793 | if (n < 0 || w == 0) |

794 | return oldbit; |

795 | else |

796 | return bitmap_ord_to_pos(new, n % w, bits); |

797 | } |

798 | EXPORT_SYMBOL(bitmap_bitremap); |

799 | |

800 | /** |

801 | * bitmap_onto - translate one bitmap relative to another |

802 | * @dst: resulting translated bitmap |

803 | * @orig: original untranslated bitmap |

804 | * @relmap: bitmap relative to which translated |

805 | * @bits: number of bits in each of these bitmaps |

806 | * |

807 | * Set the n-th bit of @dst iff there exists some m such that the |

808 | * n-th bit of @relmap is set, the m-th bit of @orig is set, and |

809 | * the n-th bit of @relmap is also the m-th _set_ bit of @relmap. |

810 | * (If you understood the previous sentence the first time your |

811 | * read it, you're overqualified for your current job.) |

812 | * |

813 | * In other words, @orig is mapped onto (surjectively) @dst, |

814 | * using the map { <n, m> | the n-th bit of @relmap is the |

815 | * m-th set bit of @relmap }. |

816 | * |

817 | * Any set bits in @orig above bit number W, where W is the |

818 | * weight of (number of set bits in) @relmap are mapped nowhere. |

819 | * In particular, if for all bits m set in @orig, m >= W, then |

820 | * @dst will end up empty. In situations where the possibility |

821 | * of such an empty result is not desired, one way to avoid it is |

822 | * to use the bitmap_fold() operator, below, to first fold the |

823 | * @orig bitmap over itself so that all its set bits x are in the |

824 | * range 0 <= x < W. The bitmap_fold() operator does this by |

825 | * setting the bit (m % W) in @dst, for each bit (m) set in @orig. |

826 | * |

827 | * Example [1] for bitmap_onto(): |

828 | * Let's say @relmap has bits 30-39 set, and @orig has bits |

829 | * 1, 3, 5, 7, 9 and 11 set. Then on return from this routine, |

830 | * @dst will have bits 31, 33, 35, 37 and 39 set. |

831 | * |

832 | * When bit 0 is set in @orig, it means turn on the bit in |

833 | * @dst corresponding to whatever is the first bit (if any) |

834 | * that is turned on in @relmap. Since bit 0 was off in the |

835 | * above example, we leave off that bit (bit 30) in @dst. |

836 | * |

837 | * When bit 1 is set in @orig (as in the above example), it |

838 | * means turn on the bit in @dst corresponding to whatever |

839 | * is the second bit that is turned on in @relmap. The second |

840 | * bit in @relmap that was turned on in the above example was |

841 | * bit 31, so we turned on bit 31 in @dst. |

842 | * |

843 | * Similarly, we turned on bits 33, 35, 37 and 39 in @dst, |

844 | * because they were the 4th, 6th, 8th and 10th set bits |

845 | * set in @relmap, and the 4th, 6th, 8th and 10th bits of |

846 | * @orig (i.e. bits 3, 5, 7 and 9) were also set. |

847 | * |

848 | * When bit 11 is set in @orig, it means turn on the bit in |

849 | * @dst corresponding to whatever is the twelfth bit that is |

850 | * turned on in @relmap. In the above example, there were |

851 | * only ten bits turned on in @relmap (30..39), so that bit |

852 | * 11 was set in @orig had no affect on @dst. |

853 | * |

854 | * Example [2] for bitmap_fold() + bitmap_onto(): |

855 | * Let's say @relmap has these ten bits set:: |

856 | * |

857 | * 40 41 42 43 45 48 53 61 74 95 |

858 | * |

859 | * (for the curious, that's 40 plus the first ten terms of the |

860 | * Fibonacci sequence.) |

861 | * |

862 | * Further lets say we use the following code, invoking |

863 | * bitmap_fold() then bitmap_onto, as suggested above to |

864 | * avoid the possibility of an empty @dst result:: |

865 | * |

866 | * unsigned long *tmp; // a temporary bitmap's bits |

867 | * |

868 | * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits); |

869 | * bitmap_onto(dst, tmp, relmap, bits); |

870 | * |

871 | * Then this table shows what various values of @dst would be, for |

872 | * various @orig's. I list the zero-based positions of each set bit. |

873 | * The tmp column shows the intermediate result, as computed by |

874 | * using bitmap_fold() to fold the @orig bitmap modulo ten |

875 | * (the weight of @relmap): |

876 | * |

877 | * =============== ============== ================= |

878 | * @orig tmp @dst |

879 | * 0 0 40 |

880 | * 1 1 41 |

881 | * 9 9 95 |

882 | * 10 0 40 [#f1]_ |

883 | * 1 3 5 7 1 3 5 7 41 43 48 61 |

884 | * 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45 |

885 | * 0 9 18 27 0 9 8 7 40 61 74 95 |

886 | * 0 10 20 30 0 40 |

887 | * 0 11 22 33 0 1 2 3 40 41 42 43 |

888 | * 0 12 24 36 0 2 4 6 40 42 45 53 |

889 | * 78 102 211 1 2 8 41 42 74 [#f1]_ |

890 | * =============== ============== ================= |

891 | * |

892 | * .. [#f1] |

893 | * |

894 | * For these marked lines, if we hadn't first done bitmap_fold() |

895 | * into tmp, then the @dst result would have been empty. |

896 | * |

897 | * If either of @orig or @relmap is empty (no set bits), then @dst |

898 | * will be returned empty. |

899 | * |

900 | * If (as explained above) the only set bits in @orig are in positions |

901 | * m where m >= W, (where W is the weight of @relmap) then @dst will |

902 | * once again be returned empty. |

903 | * |

904 | * All bits in @dst not set by the above rule are cleared. |

905 | */ |

906 | void bitmap_onto(unsigned long *dst, const unsigned long *orig, |

907 | const unsigned long *relmap, unsigned int bits) |

908 | { |

909 | unsigned int n, m; /* same meaning as in above comment */ |

910 | |

911 | if (dst == orig) /* following doesn't handle inplace mappings */ |

912 | return; |

913 | bitmap_zero(dst, bits); |

914 | |

915 | /* |

916 | * The following code is a more efficient, but less |

917 | * obvious, equivalent to the loop: |

918 | * for (m = 0; m < bitmap_weight(relmap, bits); m++) { |

919 | * n = bitmap_ord_to_pos(orig, m, bits); |

920 | * if (test_bit(m, orig)) |

921 | * set_bit(n, dst); |

922 | * } |

923 | */ |

924 | |

925 | m = 0; |

926 | for_each_set_bit(n, relmap, bits) { |

927 | /* m == bitmap_pos_to_ord(relmap, n, bits) */ |

928 | if (test_bit(m, orig)) |

929 | set_bit(n, dst); |

930 | m++; |

931 | } |

932 | } |

933 | EXPORT_SYMBOL(bitmap_onto); |

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 | |

951 | if (dst == orig) /* following doesn't handle inplace mappings */ |

952 | return; |

953 | bitmap_zero(dst, nbits); |

954 | |

955 | for_each_set_bit(oldbit, orig, nbits) |

956 | set_bit(oldbit % sz, dst); |

957 | } |

958 | EXPORT_SYMBOL(bitmap_fold); |

959 | |

960 | /* |

961 | * Common code for bitmap_*_region() routines. |

962 | * bitmap: array of unsigned longs corresponding to the bitmap |

963 | * pos: the beginning of the region |

964 | * order: region size (log base 2 of number of bits) |

965 | * reg_op: operation(s) to perform on that region of bitmap |

966 | * |

967 | * Can set, verify and/or release a region of bits in a bitmap, |

968 | * depending on which combination of REG_OP_* flag bits is set. |

969 | * |

970 | * A region of a bitmap is a sequence of bits in the bitmap, of |

971 | * some size '1 << order' (a power of two), aligned to that same |

972 | * '1 << order' power of two. |

973 | * |

974 | * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits). |

975 | * Returns 0 in all other cases and reg_ops. |

976 | */ |

977 | |

978 | enum { |

979 | REG_OP_ISFREE, /* true if region is all zero bits */ |

980 | REG_OP_ALLOC, /* set all bits in region */ |

981 | REG_OP_RELEASE, /* clear all bits in region */ |

982 | }; |

983 | |

984 | static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op) |

985 | { |

986 | int nbits_reg; /* number of bits in region */ |

987 | int index; /* index first long of region in bitmap */ |

988 | int offset; /* bit offset region in bitmap[index] */ |

989 | int nlongs_reg; /* num longs spanned by region in bitmap */ |

990 | int nbitsinlong; /* num bits of region in each spanned long */ |

991 | unsigned long mask; /* bitmask for one long of region */ |

992 | int i; /* scans bitmap by longs */ |

993 | int ret = 0; /* return value */ |

994 | |

995 | /* |

996 | * Either nlongs_reg == 1 (for small orders that fit in one long) |

997 | * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) |

998 | */ |

999 | nbits_reg = 1 << order; |

1000 | index = pos / BITS_PER_LONG; |

1001 | offset = pos - (index * BITS_PER_LONG); |

1002 | nlongs_reg = BITS_TO_LONGS(nbits_reg); |

1003 | nbitsinlong = min(nbits_reg, BITS_PER_LONG); |

1004 | |

1005 | /* |

1006 | * Can't do "mask = (1UL << nbitsinlong) - 1", as that |

1007 | * overflows if nbitsinlong == BITS_PER_LONG. |

1008 | */ |

1009 | mask = (1UL << (nbitsinlong - 1)); |

1010 | mask += mask - 1; |

1011 | mask <<= offset; |

1012 | |

1013 | switch (reg_op) { |

1014 | case REG_OP_ISFREE: |

1015 | for (i = 0; i < nlongs_reg; i++) { |

1016 | if (bitmap[index + i] & mask) |

1017 | goto done; |

1018 | } |

1019 | ret = 1; /* all bits in region free (zero) */ |

1020 | break; |

1021 | |

1022 | case REG_OP_ALLOC: |

1023 | for (i = 0; i < nlongs_reg; i++) |

1024 | bitmap[index + i] |= mask; |

1025 | break; |

1026 | |

1027 | case REG_OP_RELEASE: |

1028 | for (i = 0; i < nlongs_reg; i++) |

1029 | bitmap[index + i] &= ~mask; |

1030 | break; |

1031 | } |

1032 | done: |

1033 | return ret; |

1034 | } |

1035 | |

1036 | /** |

1037 | * bitmap_find_free_region - find a contiguous aligned mem region |

1038 | * @bitmap: array of unsigned longs corresponding to the bitmap |

1039 | * @bits: number of bits in the bitmap |

1040 | * @order: region size (log base 2 of number of bits) to find |

1041 | * |

1042 | * Find a region of free (zero) bits in a @bitmap of @bits bits and |

1043 | * allocate them (set them to one). Only consider regions of length |

1044 | * a power (@order) of two, aligned to that power of two, which |

1045 | * makes the search algorithm much faster. |

1046 | * |

1047 | * Return the bit offset in bitmap of the allocated region, |

1048 | * or -errno on failure. |

1049 | */ |

1050 | int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order) |

1051 | { |

1052 | unsigned int pos, end; /* scans bitmap by regions of size order */ |

1053 | |

1054 | for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) { |

1055 | if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) |

1056 | continue; |

1057 | __reg_op(bitmap, pos, order, REG_OP_ALLOC); |

1058 | return pos; |

1059 | } |

1060 | return -ENOMEM; |

1061 | } |

1062 | EXPORT_SYMBOL(bitmap_find_free_region); |

1063 | |

1064 | /** |

1065 | * bitmap_release_region - release allocated bitmap region |

1066 | * @bitmap: array of unsigned longs corresponding to the bitmap |

1067 | * @pos: beginning of bit region to release |

1068 | * @order: region size (log base 2 of number of bits) to release |

1069 | * |

1070 | * This is the complement to __bitmap_find_free_region() and releases |

1071 | * the found region (by clearing it in the bitmap). |

1072 | * |

1073 | * No return value. |

1074 | */ |

1075 | void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order) |

1076 | { |

1077 | __reg_op(bitmap, pos, order, REG_OP_RELEASE); |

1078 | } |

1079 | EXPORT_SYMBOL(bitmap_release_region); |

1080 | |

1081 | /** |

1082 | * bitmap_allocate_region - allocate bitmap region |

1083 | * @bitmap: array of unsigned longs corresponding to the bitmap |

1084 | * @pos: beginning of bit region to allocate |

1085 | * @order: region size (log base 2 of number of bits) to allocate |

1086 | * |

1087 | * Allocate (set bits in) a specified region of a bitmap. |

1088 | * |

1089 | * Return 0 on success, or %-EBUSY if specified region wasn't |

1090 | * free (not all bits were zero). |

1091 | */ |

1092 | int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order) |

1093 | { |

1094 | if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) |

1095 | return -EBUSY; |

1096 | return __reg_op(bitmap, pos, order, REG_OP_ALLOC); |

1097 | } |

1098 | EXPORT_SYMBOL(bitmap_allocate_region); |

1099 | |

1100 | /** |

1101 | * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order. |

1102 | * @dst: destination buffer |

1103 | * @src: bitmap to copy |

1104 | * @nbits: number of bits in the bitmap |

1105 | * |

1106 | * Require nbits % BITS_PER_LONG == 0. |

1107 | */ |

1108 | #ifdef __BIG_ENDIAN |

1109 | void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits) |

1110 | { |

1111 | unsigned int i; |

1112 | |

1113 | for (i = 0; i < nbits/BITS_PER_LONG; i++) { |

1114 | if (BITS_PER_LONG == 64) |

1115 | dst[i] = cpu_to_le64(src[i]); |

1116 | else |

1117 | dst[i] = cpu_to_le32(src[i]); |

1118 | } |

1119 | } |

1120 | EXPORT_SYMBOL(bitmap_copy_le); |

1121 | #endif |

1122 | |

1123 | unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags) |

1124 | { |

1125 | return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long), |

1126 | flags); |

1127 | } |

1128 | EXPORT_SYMBOL(bitmap_alloc); |

1129 | |

1130 | unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags) |

1131 | { |

1132 | return bitmap_alloc(nbits, flags | __GFP_ZERO); |

1133 | } |

1134 | EXPORT_SYMBOL(bitmap_zalloc); |

1135 | |

1136 | void bitmap_free(const unsigned long *bitmap) |

1137 | { |

1138 | kfree(bitmap); |

1139 | } |

1140 | EXPORT_SYMBOL(bitmap_free); |

1141 | |

1142 | #if BITS_PER_LONG == 64 |

1143 | /** |

1144 | * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap |

1145 | * @bitmap: array of unsigned longs, the destination bitmap |

1146 | * @buf: array of u32 (in host byte order), the source bitmap |

1147 | * @nbits: number of bits in @bitmap |

1148 | */ |

1149 | void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits) |

1150 | { |

1151 | unsigned int i, halfwords; |

1152 | |

1153 | halfwords = DIV_ROUND_UP(nbits, 32); |

1154 | for (i = 0; i < halfwords; i++) { |

1155 | bitmap[i/2] = (unsigned long) buf[i]; |

1156 | if (++i < halfwords) |

1157 | bitmap[i/2] |= ((unsigned long) buf[i]) << 32; |

1158 | } |

1159 | |

1160 | /* Clear tail bits in last word beyond nbits. */ |

1161 | if (nbits % BITS_PER_LONG) |

1162 | bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits); |

1163 | } |

1164 | EXPORT_SYMBOL(bitmap_from_arr32); |

1165 | |

1166 | /** |

1167 | * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits |

1168 | * @buf: array of u32 (in host byte order), the dest bitmap |

1169 | * @bitmap: array of unsigned longs, the source bitmap |

1170 | * @nbits: number of bits in @bitmap |

1171 | */ |

1172 | void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits) |

1173 | { |

1174 | unsigned int i, halfwords; |

1175 | |

1176 | halfwords = DIV_ROUND_UP(nbits, 32); |

1177 | for (i = 0; i < halfwords; i++) { |

1178 | buf[i] = (u32) (bitmap[i/2] & UINT_MAX); |

1179 | if (++i < halfwords) |

1180 | buf[i] = (u32) (bitmap[i/2] >> 32); |

1181 | } |

1182 | |

1183 | /* Clear tail bits in last element of array beyond nbits. */ |

1184 | if (nbits % BITS_PER_LONG) |

1185 | buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31)); |

1186 | } |

1187 | EXPORT_SYMBOL(bitmap_to_arr32); |

1188 | |

1189 | #endif |

1190 |