Blame view
include/linux/bitmap.h
21.8 KB
b24413180
|
1 |
/* SPDX-License-Identifier: GPL-2.0 */ |
1da177e4c
|
2 3 4 5 6 7 8 9 |
#ifndef __LINUX_BITMAP_H #define __LINUX_BITMAP_H #ifndef __ASSEMBLY__ #include <linux/types.h> #include <linux/bitops.h> #include <linux/string.h> |
14ed9d23a
|
10 |
#include <linux/kernel.h> |
1da177e4c
|
11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* * bitmaps provide bit arrays that consume one or more unsigned * longs. The bitmap interface and available operations are listed * here, in bitmap.h * * Function implementations generic to all architectures are in * lib/bitmap.c. Functions implementations that are architecture * specific are in various include/asm-<arch>/bitops.h headers * and other arch/<arch> specific files. * * See lib/bitmap.c for more details. */ |
7d7363e40
|
24 25 26 |
/** * DOC: bitmap overview * |
1da177e4c
|
27 28 29 |
* The available bitmap operations and their rough meaning in the * case that the bitmap is a single unsigned long are thus: * |
41e7b1661
|
30 31 |
* The generated code is more efficient when nbits is known at * compile-time and at most BITS_PER_LONG. |
08cd36570
|
32 |
* |
7d7363e40
|
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
* :: * * bitmap_zero(dst, nbits) *dst = 0UL * bitmap_fill(dst, nbits) *dst = ~0UL * bitmap_copy(dst, src, nbits) *dst = *src * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) * bitmap_complement(dst, src, nbits) *dst = ~(*src) * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2? * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area |
780d2a9c8
|
52 |
* bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off) as above |
a392d26f3
|
53 54 55 56 57 58 |
* bitmap_next_clear_region(map, &start, &end, nbits) Find next clear region * bitmap_next_set_region(map, &start, &end, nbits) Find next set region * bitmap_for_each_clear_region(map, rs, re, start, end) * Iterate over all clear regions * bitmap_for_each_set_region(map, rs, re, start, end) * Iterate over all set regions |
7d7363e40
|
59 60 |
* bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n |
209276716
|
61 |
* bitmap_cut(dst, src, first, n, nbits) Cut n bits from first, copy rest |
30544ed5d
|
62 |
* bitmap_replace(dst, old, new, mask, nbits) *dst = (*old & ~(*mask)) | (*new & *mask) |
7d7363e40
|
63 64 65 66 67 68 69 70 71 72 73 |
* bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit) * bitmap_onto(dst, orig, relmap, nbits) *dst = orig relative to relmap * bitmap_fold(dst, orig, sz, nbits) dst bits = orig bits mod sz * bitmap_parse(buf, buflen, dst, nbits) Parse bitmap dst from kernel buf * bitmap_parse_user(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from kernel buf * bitmap_parselist_user(buf, dst, nbits) Parse bitmap dst from user buf * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region * bitmap_release_region(bitmap, pos, order) Free specified bit region * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region |
c724f1936
|
74 75 |
* bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst |
169c474fb
|
76 77 |
* bitmap_get_value8(map, start) Get 8bit value from map at start * bitmap_set_value8(map, value, start) Set 8bit value to map at start |
7d7363e40
|
78 |
* |
334cfa48d
|
79 80 81 82 83 |
* Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long * boundary will be zeroed or filled as well. Consider to use * bitmap_clear() or bitmap_set() to make explicit zeroing or filling * respectively. |
1da177e4c
|
84 |
*/ |
7d7363e40
|
85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
/** * DOC: bitmap bitops * * Also the following operations in asm/bitops.h apply to bitmaps.:: * * set_bit(bit, addr) *addr |= bit * clear_bit(bit, addr) *addr &= ~bit * change_bit(bit, addr) *addr ^= bit * test_bit(bit, addr) Is bit set in *addr? * test_and_set_bit(bit, addr) Set bit and return old value * test_and_clear_bit(bit, addr) Clear bit and return old value * test_and_change_bit(bit, addr) Change bit and return old value * find_first_zero_bit(addr, nbits) Position first zero bit in *addr * find_first_bit(addr, nbits) Position first set bit in *addr |
0ade34c37
|
99 100 |
* find_next_zero_bit(addr, nbits, bit) * Position next zero bit in *addr >= bit |
7d7363e40
|
101 |
* find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit |
0ade34c37
|
102 103 104 |
* find_next_and_bit(addr1, addr2, nbits, bit) * Same as find_next_bit, but in * (*addr1 & *addr2) |
1da177e4c
|
105 |
* |
1da177e4c
|
106 |
*/ |
7d7363e40
|
107 108 |
/** * DOC: declare bitmap |
1da177e4c
|
109 110 111 112 113 114 |
* The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used * to declare an array named 'name' of just enough unsigned longs to * contain all bit positions from 0 to 'bits' - 1. */ /* |
c42b65e36
|
115 116 117 118 119 120 121 122 |
* Allocation and deallocation of bitmap. * Provided in lib/bitmap.c to avoid circular dependency. */ extern unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags); extern unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags); extern void bitmap_free(const unsigned long *bitmap); /* |
1da177e4c
|
123 124 |
* lib/bitmap.c provides these functions: */ |
0679cc483
|
125 |
extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits); |
8397927c8
|
126 |
extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits); |
1da177e4c
|
127 |
extern int __bitmap_equal(const unsigned long *bitmap1, |
5e0680693
|
128 |
const unsigned long *bitmap2, unsigned int nbits); |
b9fa6442f
|
129 130 131 132 |
extern bool __pure __bitmap_or_equal(const unsigned long *src1, const unsigned long *src2, const unsigned long *src3, unsigned int nbits); |
1da177e4c
|
133 |
extern void __bitmap_complement(unsigned long *dst, const unsigned long *src, |
3d6684f4e
|
134 |
unsigned int nbits); |
2fbad2991
|
135 136 |
extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, unsigned int shift, unsigned int nbits); |
dba94c255
|
137 138 |
extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, unsigned int shift, unsigned int nbits); |
209276716
|
139 140 141 |
extern void bitmap_cut(unsigned long *dst, const unsigned long *src, unsigned int first, unsigned int cut, unsigned int nbits); |
f4b0373b2
|
142 |
extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |
2f9305eb3
|
143 |
const unsigned long *bitmap2, unsigned int nbits); |
1da177e4c
|
144 |
extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |
2f9305eb3
|
145 |
const unsigned long *bitmap2, unsigned int nbits); |
1da177e4c
|
146 |
extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, |
2f9305eb3
|
147 |
const unsigned long *bitmap2, unsigned int nbits); |
f4b0373b2
|
148 |
extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |
2f9305eb3
|
149 |
const unsigned long *bitmap2, unsigned int nbits); |
30544ed5d
|
150 151 152 |
extern void __bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, const unsigned long *mask, unsigned int nbits); |
1da177e4c
|
153 |
extern int __bitmap_intersects(const unsigned long *bitmap1, |
6dfe9799c
|
154 |
const unsigned long *bitmap2, unsigned int nbits); |
1da177e4c
|
155 |
extern int __bitmap_subset(const unsigned long *bitmap1, |
5be20213e
|
156 |
const unsigned long *bitmap2, unsigned int nbits); |
877d9f3b6
|
157 |
extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits); |
e5af323c9
|
158 159 |
extern void __bitmap_set(unsigned long *map, unsigned int start, int len); extern void __bitmap_clear(unsigned long *map, unsigned int start, int len); |
5e19b013f
|
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map, unsigned long size, unsigned long start, unsigned int nr, unsigned long align_mask, unsigned long align_offset); /** * bitmap_find_next_zero_area - find a contiguous aligned zero area * @map: The address to base the search on * @size: The bitmap size in bits * @start: The bitnumber to start searching at * @nr: The number of zeroed bits we're looking for * @align_mask: Alignment mask for zero area * * The @align_mask should be one less than a power of 2; the effect is that * the bit offset of all zero areas this function finds is multiples of that * power of 2. A @align_mask of 0 means no alignment is required. */ static inline unsigned long bitmap_find_next_zero_area(unsigned long *map, unsigned long size, unsigned long start, unsigned int nr, unsigned long align_mask) { return bitmap_find_next_zero_area_off(map, size, start, nr, align_mask, 0); } |
c1a2a962a
|
190 |
|
2d6261583
|
191 |
extern int bitmap_parse(const char *buf, unsigned int buflen, |
01a3ee2b2
|
192 193 |
unsigned long *dst, int nbits); extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen, |
1da177e4c
|
194 |
unsigned long *dst, int nbits); |
1da177e4c
|
195 196 |
extern int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits); |
4b060420a
|
197 198 |
extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen, unsigned long *dst, int nbits); |
fb5eeeee4
|
199 |
extern void bitmap_remap(unsigned long *dst, const unsigned long *src, |
9814ec135
|
200 |
const unsigned long *old, const unsigned long *new, unsigned int nbits); |
fb5eeeee4
|
201 202 |
extern int bitmap_bitremap(int oldbit, const unsigned long *old, const unsigned long *new, int bits); |
7ea931c9f
|
203 |
extern void bitmap_onto(unsigned long *dst, const unsigned long *orig, |
eb5698837
|
204 |
const unsigned long *relmap, unsigned int bits); |
7ea931c9f
|
205 |
extern void bitmap_fold(unsigned long *dst, const unsigned long *orig, |
b26ad5836
|
206 |
unsigned int sz, unsigned int nbits); |
9279d3286
|
207 208 209 |
extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order); extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order); extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order); |
3aa56885e
|
210 |
|
e8f242783
|
211 |
#ifdef __BIG_ENDIAN |
9b6c2d2e2
|
212 |
extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits); |
e8f242783
|
213 214 215 |
#else #define bitmap_copy_le bitmap_copy #endif |
f6a1f5db8
|
216 |
extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits); |
5aaba3631
|
217 218 |
extern int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, int nmaskbits); |
1da177e4c
|
219 |
|
89c1e79eb
|
220 221 |
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) |
1da177e4c
|
222 |
|
7275b0978
|
223 224 225 226 227 |
/* * The static inlines below do not handle constant nbits==0 correctly, * so make such users (should any ever turn up) call the out-of-line * versions. */ |
4b0bc0bca
|
228 |
#define small_const_nbits(nbits) \ |
7275b0978
|
229 |
(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0) |
4b0bc0bca
|
230 |
|
8b4daad52
|
231 |
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) |
1da177e4c
|
232 |
{ |
c8cebc553
|
233 234 |
unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memset(dst, 0, len); |
1da177e4c
|
235 |
} |
8b4daad52
|
236 |
static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) |
1da177e4c
|
237 |
{ |
c8cebc553
|
238 239 |
unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memset(dst, 0xff, len); |
1da177e4c
|
240 241 242 |
} static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, |
8b4daad52
|
243 |
unsigned int nbits) |
1da177e4c
|
244 |
{ |
c8cebc553
|
245 246 |
unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); memcpy(dst, src, len); |
1da177e4c
|
247 |
} |
c724f1936
|
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 |
/* * Copy bitmap and clear tail bits in last word. */ static inline void bitmap_copy_clear_tail(unsigned long *dst, const unsigned long *src, unsigned int nbits) { bitmap_copy(dst, src, nbits); if (nbits % BITS_PER_LONG) dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits); } /* * On 32-bit systems bitmaps are represented as u32 arrays internally, and * therefore conversion is not needed when copying data from/to arrays of u32. */ #if BITS_PER_LONG == 64 extern void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits); extern void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits); #else #define bitmap_from_arr32(bitmap, buf, nbits) \ bitmap_copy_clear_tail((unsigned long *) (bitmap), \ (const unsigned long *) (buf), (nbits)) #define bitmap_to_arr32(buf, bitmap, nbits) \ bitmap_copy_clear_tail((unsigned long *) (buf), \ (const unsigned long *) (bitmap), (nbits)) #endif |
f4b0373b2
|
276 |
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1, |
2f9305eb3
|
277 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
278 |
{ |
4b0bc0bca
|
279 |
if (small_const_nbits(nbits)) |
7e5f97d19
|
280 |
return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; |
f4b0373b2
|
281 |
return __bitmap_and(dst, src1, src2, nbits); |
1da177e4c
|
282 283 284 |
} static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, |
2f9305eb3
|
285 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
286 |
{ |
4b0bc0bca
|
287 |
if (small_const_nbits(nbits)) |
1da177e4c
|
288 289 290 291 292 293 |
*dst = *src1 | *src2; else __bitmap_or(dst, src1, src2, nbits); } static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, |
2f9305eb3
|
294 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
295 |
{ |
4b0bc0bca
|
296 |
if (small_const_nbits(nbits)) |
1da177e4c
|
297 298 299 300 |
*dst = *src1 ^ *src2; else __bitmap_xor(dst, src1, src2, nbits); } |
f4b0373b2
|
301 |
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1, |
2f9305eb3
|
302 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
303 |
{ |
4b0bc0bca
|
304 |
if (small_const_nbits(nbits)) |
74e765319
|
305 |
return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; |
f4b0373b2
|
306 |
return __bitmap_andnot(dst, src1, src2, nbits); |
1da177e4c
|
307 308 309 |
} static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, |
3d6684f4e
|
310 |
unsigned int nbits) |
1da177e4c
|
311 |
{ |
4b0bc0bca
|
312 |
if (small_const_nbits(nbits)) |
65b4ee62c
|
313 |
*dst = ~(*src); |
1da177e4c
|
314 315 316 |
else __bitmap_complement(dst, src, nbits); } |
21035965f
|
317 318 319 320 321 322 |
#ifdef __LITTLE_ENDIAN #define BITMAP_MEM_ALIGNMENT 8 #else #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) #endif #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) |
1da177e4c
|
323 |
static inline int bitmap_equal(const unsigned long *src1, |
3d6684f4e
|
324 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
325 |
{ |
4b0bc0bca
|
326 |
if (small_const_nbits(nbits)) |
4b9d314ce
|
327 |
return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); |
21035965f
|
328 329 |
if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) && IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) |
7dd968163
|
330 |
return !memcmp(src1, src2, nbits / 8); |
4b9d314ce
|
331 |
return __bitmap_equal(src1, src2, nbits); |
1da177e4c
|
332 |
} |
b9fa6442f
|
333 |
/** |
2a7e582f4
|
334 |
* bitmap_or_equal - Check whether the or of two bitmaps is equal to a third |
b9fa6442f
|
335 336 337 |
* @src1: Pointer to bitmap 1 * @src2: Pointer to bitmap 2 will be or'ed with bitmap 1 * @src3: Pointer to bitmap 3. Compare to the result of *@src1 | *@src2 |
2a7e582f4
|
338 |
* @nbits: number of bits in each of these bitmaps |
b9fa6442f
|
339 340 341 342 343 344 345 346 347 348 349 350 351 |
* * Returns: True if (*@src1 | *@src2) == *@src3, false otherwise */ static inline bool bitmap_or_equal(const unsigned long *src1, const unsigned long *src2, const unsigned long *src3, unsigned int nbits) { if (!small_const_nbits(nbits)) return __bitmap_or_equal(src1, src2, src3, nbits); return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits)); } |
1da177e4c
|
352 |
static inline int bitmap_intersects(const unsigned long *src1, |
6dfe9799c
|
353 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
354 |
{ |
4b0bc0bca
|
355 |
if (small_const_nbits(nbits)) |
1da177e4c
|
356 357 358 359 360 361 |
return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; else return __bitmap_intersects(src1, src2, nbits); } static inline int bitmap_subset(const unsigned long *src1, |
5be20213e
|
362 |
const unsigned long *src2, unsigned int nbits) |
1da177e4c
|
363 |
{ |
4b0bc0bca
|
364 |
if (small_const_nbits(nbits)) |
1da177e4c
|
365 366 367 368 |
return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits)); else return __bitmap_subset(src1, src2, nbits); } |
0679cc483
|
369 |
static inline int bitmap_empty(const unsigned long *src, unsigned nbits) |
1da177e4c
|
370 |
{ |
4b0bc0bca
|
371 |
if (small_const_nbits(nbits)) |
1da177e4c
|
372 |
return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); |
2afe27c71
|
373 374 |
return find_first_bit(src, nbits) == nbits; |
1da177e4c
|
375 |
} |
8397927c8
|
376 |
static inline int bitmap_full(const unsigned long *src, unsigned int nbits) |
1da177e4c
|
377 |
{ |
4b0bc0bca
|
378 |
if (small_const_nbits(nbits)) |
1da177e4c
|
379 |
return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); |
2afe27c71
|
380 381 |
return find_first_zero_bit(src, nbits) == nbits; |
1da177e4c
|
382 |
} |
1a1d48a4a
|
383 |
static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits) |
1da177e4c
|
384 |
{ |
4b0bc0bca
|
385 |
if (small_const_nbits(nbits)) |
08cd36570
|
386 |
return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); |
1da177e4c
|
387 388 |
return __bitmap_weight(src, nbits); } |
e5af323c9
|
389 390 391 392 393 |
static __always_inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) { if (__builtin_constant_p(nbits) && nbits == 1) __set_bit(start, map); |
21035965f
|
394 395 396 397 |
else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) |
2a98dc028
|
398 |
memset((char *)map + start / 8, 0xff, nbits / 8); |
e5af323c9
|
399 400 401 402 403 404 405 406 407 |
else __bitmap_set(map, start, nbits); } static __always_inline void bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) { if (__builtin_constant_p(nbits) && nbits == 1) __clear_bit(start, map); |
21035965f
|
408 409 410 411 |
else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && __builtin_constant_p(nbits & BITMAP_MEM_MASK) && IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) |
2a98dc028
|
412 |
memset((char *)map + start / 8, 0, nbits / 8); |
e5af323c9
|
413 414 415 |
else __bitmap_clear(map, start, nbits); } |
2fbad2991
|
416 |
static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src, |
d9873969f
|
417 |
unsigned int shift, unsigned int nbits) |
1da177e4c
|
418 |
{ |
4b0bc0bca
|
419 |
if (small_const_nbits(nbits)) |
2fbad2991
|
420 |
*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift; |
1da177e4c
|
421 |
else |
2fbad2991
|
422 |
__bitmap_shift_right(dst, src, shift, nbits); |
1da177e4c
|
423 |
} |
dba94c255
|
424 425 |
static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src, unsigned int shift, unsigned int nbits) |
1da177e4c
|
426 |
{ |
4b0bc0bca
|
427 |
if (small_const_nbits(nbits)) |
dba94c255
|
428 |
*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits); |
1da177e4c
|
429 |
else |
dba94c255
|
430 |
__bitmap_shift_left(dst, src, shift, nbits); |
1da177e4c
|
431 |
} |
30544ed5d
|
432 433 434 435 436 437 438 439 440 441 442 |
static inline void bitmap_replace(unsigned long *dst, const unsigned long *old, const unsigned long *new, const unsigned long *mask, unsigned int nbits) { if (small_const_nbits(nbits)) *dst = (*old & ~(*mask)) | (*new & *mask); else __bitmap_replace(dst, old, new, mask, nbits); } |
e837dfde1
|
443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 |
static inline void bitmap_next_clear_region(unsigned long *bitmap, unsigned int *rs, unsigned int *re, unsigned int end) { *rs = find_next_zero_bit(bitmap, end, *rs); *re = find_next_bit(bitmap, end, *rs + 1); } static inline void bitmap_next_set_region(unsigned long *bitmap, unsigned int *rs, unsigned int *re, unsigned int end) { *rs = find_next_bit(bitmap, end, *rs); *re = find_next_zero_bit(bitmap, end, *rs + 1); } /* * Bitmap region iterators. Iterates over the bitmap between [@start, @end). * @rs and @re should be integer variables and will be set to start and end * index of the current clear or set region. */ #define bitmap_for_each_clear_region(bitmap, rs, re, start, end) \ for ((rs) = (start), \ bitmap_next_clear_region((bitmap), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, \ bitmap_next_clear_region((bitmap), &(rs), &(re), (end))) #define bitmap_for_each_set_region(bitmap, rs, re, start, end) \ for ((rs) = (start), \ bitmap_next_set_region((bitmap), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, \ bitmap_next_set_region((bitmap), &(rs), &(re), (end))) |
404376af7
|
477 |
/** |
60ef69001
|
478 |
* BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap. |
404376af7
|
479 |
* @n: u64 value |
60ef69001
|
480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 |
* * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit * integers in 32-bit environment, and 64-bit integers in 64-bit one. * * There are four combinations of endianness and length of the word in linux * ABIs: LE64, BE64, LE32 and BE32. * * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in * bitmaps and therefore don't require any special handling. * * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the * other hand is represented as an array of 32-bit words and the position of * bit N may therefore be calculated as: word #(N/32) and bit #(N%32) in that * word. For example, bit #42 is located at 10th position of 2nd word. * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit * values in memory as it usually does. But for BE we need to swap hi and lo * words manually. * * With all that, the macro BITMAP_FROM_U64() does explicit reordering of hi and * lo parts of u64. For LE32 it does nothing, and for BE environment it swaps * hi and lo words, as is expected by bitmap. */ #if __BITS_PER_LONG == 64 #define BITMAP_FROM_U64(n) (n) #else #define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \ ((unsigned long) ((u64)(n) >> 32)) #endif |
404376af7
|
509 |
/** |
29dd32887
|
510 511 512 513 |
* bitmap_from_u64 - Check and swap words within u64. * @mask: source bitmap * @dst: destination bitmap * |
404376af7
|
514 |
* In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]`` |
29dd32887
|
515 |
* to read u64 mask, we will get the wrong word. |
404376af7
|
516 |
* That is ``(u32 *)(&val)[0]`` gets the upper 32 bits, |
29dd32887
|
517 518 519 520 521 522 523 524 525 |
* but we expect the lower 32-bits of u64. */ static inline void bitmap_from_u64(unsigned long *dst, u64 mask) { dst[0] = mask & ULONG_MAX; if (sizeof(mask) > sizeof(unsigned long)) dst[1] = mask >> 32; } |
169c474fb
|
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 |
/** * bitmap_get_value8 - get an 8-bit value within a memory region * @map: address to the bitmap memory region * @start: bit offset of the 8-bit value; must be a multiple of 8 * * Returns the 8-bit value located at the @start bit offset within the @src * memory region. */ static inline unsigned long bitmap_get_value8(const unsigned long *map, unsigned long start) { const size_t index = BIT_WORD(start); const unsigned long offset = start % BITS_PER_LONG; return (map[index] >> offset) & 0xFF; } /** * bitmap_set_value8 - set an 8-bit value within a memory region * @map: address to the bitmap memory region * @value: the 8-bit value; values wider than 8 bits may clobber bitmap * @start: bit offset of the 8-bit value; must be a multiple of 8 */ static inline void bitmap_set_value8(unsigned long *map, unsigned long value, unsigned long start) { const size_t index = BIT_WORD(start); const unsigned long offset = start % BITS_PER_LONG; map[index] &= ~(0xFFUL << offset); map[index] |= value << offset; } |
1da177e4c
|
558 559 560 |
#endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */ |