| .. | .. |
|---|
| 4 | 4 | |
|---|
| 5 | 5 | #ifndef __ASSEMBLY__ |
|---|
| 6 | 6 | |
|---|
| 7 | | -#include <linux/types.h> |
|---|
| 8 | 7 | #include <linux/bitops.h> |
|---|
| 9 | | -#include <linux/string.h> |
|---|
| 10 | 8 | #include <linux/kernel.h> |
|---|
| 9 | +#include <linux/string.h> |
|---|
| 10 | +#include <linux/types.h> |
|---|
| 11 | + |
|---|
| 12 | +struct device; |
|---|
| 11 | 13 | |
|---|
| 12 | 14 | /* |
|---|
| 13 | 15 | * bitmaps provide bit arrays that consume one or more unsigned |
|---|
| .. | .. |
|---|
| 28 | 30 | * The available bitmap operations and their rough meaning in the |
|---|
| 29 | 31 | * case that the bitmap is a single unsigned long are thus: |
|---|
| 30 | 32 | * |
|---|
| 31 | | - * Note that nbits should be always a compile time evaluable constant. |
|---|
| 32 | | - * Otherwise many inlines will generate horrible code. |
|---|
| 33 | + * The generated code is more efficient when nbits is known at |
|---|
| 34 | + * compile-time and at most BITS_PER_LONG. |
|---|
| 33 | 35 | * |
|---|
| 34 | 36 | * :: |
|---|
| 35 | 37 | * |
|---|
| .. | .. |
|---|
| 50 | 52 | * bitmap_set(dst, pos, nbits) Set specified bit area |
|---|
| 51 | 53 | * bitmap_clear(dst, pos, nbits) Clear specified bit area |
|---|
| 52 | 54 | * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area |
|---|
| 53 | | - * bitmap_find_next_zero_area_off(buf, len, pos, n, mask) as above |
|---|
| 55 | + * bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above |
|---|
| 56 | + * bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region |
|---|
| 57 | + * bitmap_next_set_region(map, &start, &end, nbits) Find next set region |
|---|
| 58 | + * bitmap_for_each_clear_region(map, rs, re, start, end) |
|---|
| 59 | + * Iterate over all clear regions |
|---|
| 60 | + * bitmap_for_each_set_region(map, rs, re, start, end) |
|---|
| 61 | + * Iterate over all set regions |
|---|
| 54 | 62 | * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n |
|---|
| 55 | 63 | * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n |
|---|
| 64 | + * bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest |
|---|
| 65 | + * bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask) |
|---|
| 56 | 66 | * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) |
|---|
| 57 | 67 | * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit) |
|---|
| 58 | 68 | * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap |
|---|
| .. | .. |
|---|
| 66 | 76 | * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region |
|---|
| 67 | 77 | * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst |
|---|
| 68 | 78 | * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst |
|---|
| 79 | + * bitmap_get_value8(map, start) Get 8bit value from map at start |
|---|
| 80 | + * bitmap_set_value8(map, value, start) Set 8bit value to map at start |
|---|
| 69 | 81 | * |
|---|
| 70 | 82 | * Note, bitmap_zero() and bitmap_fill() operate over the region of |
|---|
| 71 | 83 | * unsigned longs, that is, bits behind bitmap till the unsigned long |
|---|
| .. | .. |
|---|
| 112 | 124 | extern unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags); |
|---|
| 113 | 125 | extern void bitmap_free(const unsigned long *bitmap); |
|---|
| 114 | 126 | |
|---|
| 127 | +/* Managed variants of the above. */ |
|---|
| 128 | +unsigned long *devm_bitmap_alloc(struct device *dev, |
|---|
| 129 | + unsigned int nbits, gfp_t flags); |
|---|
| 130 | +unsigned long *devm_bitmap_zalloc(struct device *dev, |
|---|
| 131 | + unsigned int nbits, gfp_t flags); |
|---|
| 132 | + |
|---|
| 115 | 133 | /* |
|---|
| 116 | 134 | * lib/bitmap.c provides these functions: |
|---|
| 117 | 135 | */ |
|---|
| .. | .. |
|---|
| 120 | 138 | extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits); |
|---|
| 121 | 139 | extern int __bitmap_equal(const unsigned long *bitmap1, |
|---|
| 122 | 140 | const unsigned long *bitmap2, unsigned int nbits); |
|---|
| 141 | +extern bool __pure __bitmap_or_equal(const unsigned long *src1, |
|---|
| 142 | + const unsigned long *src2, |
|---|
| 143 | + const unsigned long *src3, |
|---|
| 144 | + unsigned int nbits); |
|---|
| 123 | 145 | extern void __bitmap_complement(unsigned long *dst, const unsigned long *src, |
|---|
| 124 | 146 | unsigned int nbits); |
|---|
| 125 | 147 | extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, |
|---|
| 126 | 148 | unsigned int shift, unsigned int nbits); |
|---|
| 127 | 149 | extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, |
|---|
| 128 | 150 | unsigned int shift, unsigned int nbits); |
|---|
| 151 | +extern void bitmap_cut(unsigned long *dst, const unsigned long *src, |
|---|
| 152 | + unsigned int first, unsigned int cut, |
|---|
| 153 | + unsigned int nbits); |
|---|
| 129 | 154 | extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |
|---|
| 130 | 155 | const unsigned long *bitmap2, unsigned int nbits); |
|---|
| 131 | 156 | extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |
|---|
| .. | .. |
|---|
| 134 | 159 | const unsigned long *bitmap2, unsigned int nbits); |
|---|
| 135 | 160 | extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |
|---|
| 136 | 161 | const unsigned long *bitmap2, unsigned int nbits); |
|---|
| 162 | +extern void __bitmap_replace(unsigned long *dst, |
|---|
| 163 | + const unsigned long *old, const unsigned long *new, |
|---|
| 164 | + const unsigned long *mask, unsigned int nbits); |
|---|
| 137 | 165 | extern int __bitmap_intersects(const unsigned long *bitmap1, |
|---|
| 138 | 166 | const unsigned long *bitmap2, unsigned int nbits); |
|---|
| 139 | 167 | extern int __bitmap_subset(const unsigned long *bitmap1, |
|---|
| .. | .. |
|---|
| 172 | 200 | align_mask, 0); |
|---|
| 173 | 201 | } |
|---|
| 174 | 202 | |
|---|
| 175 | | -extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user, |
|---|
| 203 | +extern int bitmap_parse(const char *buf, unsigned int buflen, |
|---|
| 176 | 204 | unsigned long *dst, int nbits); |
|---|
| 177 | 205 | extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen, |
|---|
| 178 | 206 | unsigned long *dst, int nbits); |
|---|
| .. | .. |
|---|
| 214 | 242 | |
|---|
| 215 | 243 | static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) |
|---|
| 216 | 244 | { |
|---|
| 217 | | - if (small_const_nbits(nbits)) |
|---|
| 218 | | - *dst = 0UL; |
|---|
| 219 | | - else { |
|---|
| 220 | | - unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 221 | | - memset(dst, 0, len); |
|---|
| 222 | | - } |
|---|
| 245 | + unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 246 | + memset(dst, 0, len); |
|---|
| 223 | 247 | } |
|---|
| 224 | 248 | |
|---|
| 225 | 249 | static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) |
|---|
| 226 | 250 | { |
|---|
| 227 | | - if (small_const_nbits(nbits)) |
|---|
| 228 | | - *dst = ~0UL; |
|---|
| 229 | | - else { |
|---|
| 230 | | - unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 231 | | - memset(dst, 0xff, len); |
|---|
| 232 | | - } |
|---|
| 251 | + unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 252 | + memset(dst, 0xff, len); |
|---|
| 233 | 253 | } |
|---|
| 234 | 254 | |
|---|
| 235 | 255 | static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, |
|---|
| 236 | 256 | unsigned int nbits) |
|---|
| 237 | 257 | { |
|---|
| 238 | | - if (small_const_nbits(nbits)) |
|---|
| 239 | | - *dst = *src; |
|---|
| 240 | | - else { |
|---|
| 241 | | - unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 242 | | - memcpy(dst, src, len); |
|---|
| 243 | | - } |
|---|
| 258 | + unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
|---|
| 259 | + memcpy(dst, src, len); |
|---|
| 244 | 260 | } |
|---|
| 245 | 261 | |
|---|
| 246 | 262 | /* |
|---|
| .. | .. |
|---|
| 333 | 349 | return __bitmap_equal(src1, src2, nbits); |
|---|
| 334 | 350 | } |
|---|
| 335 | 351 | |
|---|
| 352 | +/** |
|---|
| 353 | + * bitmap_or_equal - Check whether the or of two bitmaps is equal to a third |
|---|
| 354 | + * @src1: Pointer to bitmap 1 |
|---|
| 355 | + * @src2: Pointer to bitmap 2 will be or'ed with bitmap 1 |
|---|
| 356 | + * @src3: Pointer to bitmap 3. Compare to the result of *@src1 | *@src2 |
|---|
| 357 | + * @nbits: number of bits in each of these bitmaps |
|---|
| 358 | + * |
|---|
| 359 | + * Returns: True if (*@src1 | *@src2) == *@src3, false otherwise |
|---|
| 360 | + */ |
|---|
| 361 | +static inline bool bitmap_or_equal(const unsigned long *src1, |
|---|
| 362 | + const unsigned long *src2, |
|---|
| 363 | + const unsigned long *src3, |
|---|
| 364 | + unsigned int nbits) |
|---|
| 365 | +{ |
|---|
| 366 | + if (!small_const_nbits(nbits)) |
|---|
| 367 | + return __bitmap_or_equal(src1, src2, src3, nbits); |
|---|
| 368 | + |
|---|
| 369 | + return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits)); |
|---|
| 370 | +} |
|---|
| 371 | + |
|---|
| 336 | 372 | static inline int bitmap_intersects(const unsigned long *src1, |
|---|
| 337 | 373 | const unsigned long *src2, unsigned int nbits) |
|---|
| 338 | 374 | { |
|---|
| .. | .. |
|---|
| 420 | 456 | __bitmap_shift_left(dst, src, shift, nbits); |
|---|
| 421 | 457 | } |
|---|
| 422 | 458 | |
|---|
| 423 | | -static inline int bitmap_parse(const char *buf, unsigned int buflen, |
|---|
| 424 | | - unsigned long *maskp, int nmaskbits) |
|---|
| 459 | +static inline void bitmap_replace(unsigned long *dst, |
|---|
| 460 | + const unsigned long *old, |
|---|
| 461 | + const unsigned long *new, |
|---|
| 462 | + const unsigned long *mask, |
|---|
| 463 | + unsigned int nbits) |
|---|
| 425 | 464 | { |
|---|
| 426 | | - return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits); |
|---|
| 465 | + if (small_const_nbits(nbits)) |
|---|
| 466 | + *dst = (*old & ~(*mask)) | (*new & *mask); |
|---|
| 467 | + else |
|---|
| 468 | + __bitmap_replace(dst, old, new, mask, nbits); |
|---|
| 427 | 469 | } |
|---|
| 470 | + |
|---|
| 471 | +static inline void bitmap_next_clear_region(unsigned long *bitmap, |
|---|
| 472 | + unsigned int *rs, unsigned int *re, |
|---|
| 473 | + unsigned int end) |
|---|
| 474 | +{ |
|---|
| 475 | + *rs = find_next_zero_bit(bitmap, end, *rs); |
|---|
| 476 | + *re = find_next_bit(bitmap, end, *rs + 1); |
|---|
| 477 | +} |
|---|
| 478 | + |
|---|
| 479 | +static inline void bitmap_next_set_region(unsigned long *bitmap, |
|---|
| 480 | + unsigned int *rs, unsigned int *re, |
|---|
| 481 | + unsigned int end) |
|---|
| 482 | +{ |
|---|
| 483 | + *rs = find_next_bit(bitmap, end, *rs); |
|---|
| 484 | + *re = find_next_zero_bit(bitmap, end, *rs + 1); |
|---|
| 485 | +} |
|---|
| 486 | + |
|---|
| 487 | +/* |
|---|
| 488 | + * Bitmap region iterators. Iterates over the bitmap between [@start, @end). |
|---|
| 489 | + * @rs and @re should be integer variables and will be set to start and end |
|---|
| 490 | + * index of the current clear or set region. |
|---|
| 491 | + */ |
|---|
| 492 | +#define bitmap_for_each_clear_region(bitmap, rs, re, start, end) \ |
|---|
| 493 | + for ((rs) = (start), \ |
|---|
| 494 | + bitmap_next_clear_region((bitmap), &(rs), &(re), (end)); \ |
|---|
| 495 | + (rs) < (re); \ |
|---|
| 496 | + (rs) = (re) + 1, \ |
|---|
| 497 | + bitmap_next_clear_region((bitmap), &(rs), &(re), (end))) |
|---|
| 498 | + |
|---|
| 499 | +#define bitmap_for_each_set_region(bitmap, rs, re, start, end) \ |
|---|
| 500 | + for ((rs) = (start), \ |
|---|
| 501 | + bitmap_next_set_region((bitmap), &(rs), &(re), (end)); \ |
|---|
| 502 | + (rs) < (re); \ |
|---|
| 503 | + (rs) = (re) + 1, \ |
|---|
| 504 | + bitmap_next_set_region((bitmap), &(rs), &(re), (end))) |
|---|
| 428 | 505 | |
|---|
| 429 | 506 | /** |
|---|
| 430 | 507 | * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap. |
|---|
| .. | .. |
|---|
| 477 | 554 | dst[1] = mask >> 32; |
|---|
| 478 | 555 | } |
|---|
| 479 | 556 | |
|---|
| 557 | +/** |
|---|
| 558 | + * bitmap_get_value8 - get an 8-bit value within a memory region |
|---|
| 559 | + * @map: address to the bitmap memory region |
|---|
| 560 | + * @start: bit offset of the 8-bit value; must be a multiple of 8 |
|---|
| 561 | + * |
|---|
| 562 | + * Returns the 8-bit value located at the @start bit offset within the @src |
|---|
| 563 | + * memory region. |
|---|
| 564 | + */ |
|---|
| 565 | +static inline unsigned long bitmap_get_value8(const unsigned long *map, |
|---|
| 566 | + unsigned long start) |
|---|
| 567 | +{ |
|---|
| 568 | + const size_t index = BIT_WORD(start); |
|---|
| 569 | + const unsigned long offset = start % BITS_PER_LONG; |
|---|
| 570 | + |
|---|
| 571 | + return (map[index] >> offset) & 0xFF; |
|---|
| 572 | +} |
|---|
| 573 | + |
|---|
| 574 | +/** |
|---|
| 575 | + * bitmap_set_value8 - set an 8-bit value within a memory region |
|---|
| 576 | + * @map: address to the bitmap memory region |
|---|
| 577 | + * @value: the 8-bit value; values wider than 8 bits may clobber bitmap |
|---|
| 578 | + * @start: bit offset of the 8-bit value; must be a multiple of 8 |
|---|
| 579 | + */ |
|---|
| 580 | +static inline void bitmap_set_value8(unsigned long *map, unsigned long value, |
|---|
| 581 | + unsigned long start) |
|---|
| 582 | +{ |
|---|
| 583 | + const size_t index = BIT_WORD(start); |
|---|
| 584 | + const unsigned long offset = start % BITS_PER_LONG; |
|---|
| 585 | + |
|---|
| 586 | + map[index] &= ~(0xFFUL << offset); |
|---|
| 587 | + map[index] |= value << offset; |
|---|
| 588 | +} |
|---|
| 589 | + |
|---|
| 480 | 590 | #endif /* __ASSEMBLY__ */ |
|---|
| 481 | 591 | |
|---|
| 482 | 592 | #endif /* __LINUX_BITMAP_H */ |
|---|