1
2#ifndef __LINUX_BITMAP_H
3#define __LINUX_BITMAP_H
4
5#ifndef __ASSEMBLY__
6
7#include <linux/align.h>
8#include <linux/bitops.h>
9#include <linux/find.h>
10#include <linux/limits.h>
11#include <linux/string.h>
12#include <linux/types.h>
13
14struct device;
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags);
120unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags);
121unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node);
122unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node);
123void bitmap_free(const unsigned long *bitmap);
124
125
126unsigned long *devm_bitmap_alloc(struct device *dev,
127 unsigned int nbits, gfp_t flags);
128unsigned long *devm_bitmap_zalloc(struct device *dev,
129 unsigned int nbits, gfp_t flags);
130
131
132
133
134
135int __bitmap_equal(const unsigned long *bitmap1,
136 const unsigned long *bitmap2, unsigned int nbits);
137bool __pure __bitmap_or_equal(const unsigned long *src1,
138 const unsigned long *src2,
139 const unsigned long *src3,
140 unsigned int nbits);
141void __bitmap_complement(unsigned long *dst, const unsigned long *src,
142 unsigned int nbits);
143void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
144 unsigned int shift, unsigned int nbits);
145void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
146 unsigned int shift, unsigned int nbits);
147void bitmap_cut(unsigned long *dst, const unsigned long *src,
148 unsigned int first, unsigned int cut, unsigned int nbits);
149int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
150 const unsigned long *bitmap2, unsigned int nbits);
151void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
152 const unsigned long *bitmap2, unsigned int nbits);
153void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
154 const unsigned long *bitmap2, unsigned int nbits);
155int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
156 const unsigned long *bitmap2, unsigned int nbits);
157void __bitmap_replace(unsigned long *dst,
158 const unsigned long *old, const unsigned long *new,
159 const unsigned long *mask, unsigned int nbits);
160int __bitmap_intersects(const unsigned long *bitmap1,
161 const unsigned long *bitmap2, unsigned int nbits);
162int __bitmap_subset(const unsigned long *bitmap1,
163 const unsigned long *bitmap2, unsigned int nbits);
164int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
165void __bitmap_set(unsigned long *map, unsigned int start, int len);
166void __bitmap_clear(unsigned long *map, unsigned int start, int len);
167
168unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
169 unsigned long size,
170 unsigned long start,
171 unsigned int nr,
172 unsigned long align_mask,
173 unsigned long align_offset);
174
175
176
177
178
179
180
181
182
183
184
185
186
187static inline unsigned long
188bitmap_find_next_zero_area(unsigned long *map,
189 unsigned long size,
190 unsigned long start,
191 unsigned int nr,
192 unsigned long align_mask)
193{
194 return bitmap_find_next_zero_area_off(map, size, start, nr,
195 align_mask, 0);
196}
197
198int bitmap_parse(const char *buf, unsigned int buflen,
199 unsigned long *dst, int nbits);
200int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
201 unsigned long *dst, int nbits);
202int bitmap_parselist(const char *buf, unsigned long *maskp,
203 int nmaskbits);
204int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
205 unsigned long *dst, int nbits);
206void bitmap_remap(unsigned long *dst, const unsigned long *src,
207 const unsigned long *old, const unsigned long *new, unsigned int nbits);
208int bitmap_bitremap(int oldbit,
209 const unsigned long *old, const unsigned long *new, int bits);
210void bitmap_onto(unsigned long *dst, const unsigned long *orig,
211 const unsigned long *relmap, unsigned int bits);
212void bitmap_fold(unsigned long *dst, const unsigned long *orig,
213 unsigned int sz, unsigned int nbits);
214int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
215void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
216int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
217
218#ifdef __BIG_ENDIAN
219void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
220#else
221#define bitmap_copy_le bitmap_copy
222#endif
223unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
224int bitmap_print_to_pagebuf(bool list, char *buf,
225 const unsigned long *maskp, int nmaskbits);
226
227extern int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
228 int nmaskbits, loff_t off, size_t count);
229
230extern int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
231 int nmaskbits, loff_t off, size_t count);
232
233#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
234#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
235
236static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
237{
238 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
239 memset(dst, 0, len);
240}
241
242static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
243{
244 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
245 memset(dst, 0xff, len);
246}
247
248static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
249 unsigned int nbits)
250{
251 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
252 memcpy(dst, src, len);
253}
254
255
256
257
258static inline void bitmap_copy_clear_tail(unsigned long *dst,
259 const unsigned long *src, unsigned int nbits)
260{
261 bitmap_copy(dst, src, nbits);
262 if (nbits % BITS_PER_LONG)
263 dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
264}
265
266
267
268
269
270#if BITS_PER_LONG == 64
271void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
272 unsigned int nbits);
273void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
274 unsigned int nbits);
275#else
276#define bitmap_from_arr32(bitmap, buf, nbits) \
277 bitmap_copy_clear_tail((unsigned long *) (bitmap), \
278 (const unsigned long *) (buf), (nbits))
279#define bitmap_to_arr32(buf, bitmap, nbits) \
280 bitmap_copy_clear_tail((unsigned long *) (buf), \
281 (const unsigned long *) (bitmap), (nbits))
282#endif
283
284static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
285 const unsigned long *src2, unsigned int nbits)
286{
287 if (small_const_nbits(nbits))
288 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
289 return __bitmap_and(dst, src1, src2, nbits);
290}
291
292static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
293 const unsigned long *src2, unsigned int nbits)
294{
295 if (small_const_nbits(nbits))
296 *dst = *src1 | *src2;
297 else
298 __bitmap_or(dst, src1, src2, nbits);
299}
300
301static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
302 const unsigned long *src2, unsigned int nbits)
303{
304 if (small_const_nbits(nbits))
305 *dst = *src1 ^ *src2;
306 else
307 __bitmap_xor(dst, src1, src2, nbits);
308}
309
310static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
311 const unsigned long *src2, unsigned int nbits)
312{
313 if (small_const_nbits(nbits))
314 return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
315 return __bitmap_andnot(dst, src1, src2, nbits);
316}
317
318static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
319 unsigned int nbits)
320{
321 if (small_const_nbits(nbits))
322 *dst = ~(*src);
323 else
324 __bitmap_complement(dst, src, nbits);
325}
326
327#ifdef __LITTLE_ENDIAN
328#define BITMAP_MEM_ALIGNMENT 8
329#else
330#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
331#endif
332#define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
333
334static inline int bitmap_equal(const unsigned long *src1,
335 const unsigned long *src2, unsigned int nbits)
336{
337 if (small_const_nbits(nbits))
338 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
339 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
340 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
341 return !memcmp(src1, src2, nbits / 8);
342 return __bitmap_equal(src1, src2, nbits);
343}
344
345
346
347
348
349
350
351
352
353
354static inline bool bitmap_or_equal(const unsigned long *src1,
355 const unsigned long *src2,
356 const unsigned long *src3,
357 unsigned int nbits)
358{
359 if (!small_const_nbits(nbits))
360 return __bitmap_or_equal(src1, src2, src3, nbits);
361
362 return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits));
363}
364
365static inline int bitmap_intersects(const unsigned long *src1,
366 const unsigned long *src2, unsigned int nbits)
367{
368 if (small_const_nbits(nbits))
369 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
370 else
371 return __bitmap_intersects(src1, src2, nbits);
372}
373
374static inline int bitmap_subset(const unsigned long *src1,
375 const unsigned long *src2, unsigned int nbits)
376{
377 if (small_const_nbits(nbits))
378 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
379 else
380 return __bitmap_subset(src1, src2, nbits);
381}
382
383static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
384{
385 if (small_const_nbits(nbits))
386 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
387
388 return find_first_bit(src, nbits) == nbits;
389}
390
391static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
392{
393 if (small_const_nbits(nbits))
394 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
395
396 return find_first_zero_bit(src, nbits) == nbits;
397}
398
399static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
400{
401 if (small_const_nbits(nbits))
402 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
403 return __bitmap_weight(src, nbits);
404}
405
406static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
407 unsigned int nbits)
408{
409 if (__builtin_constant_p(nbits) && nbits == 1)
410 __set_bit(start, map);
411 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
412 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
413 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
414 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
415 memset((char *)map + start / 8, 0xff, nbits / 8);
416 else
417 __bitmap_set(map, start, nbits);
418}
419
420static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
421 unsigned int nbits)
422{
423 if (__builtin_constant_p(nbits) && nbits == 1)
424 __clear_bit(start, map);
425 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
426 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
427 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
428 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
429 memset((char *)map + start / 8, 0, nbits / 8);
430 else
431 __bitmap_clear(map, start, nbits);
432}
433
434static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
435 unsigned int shift, unsigned int nbits)
436{
437 if (small_const_nbits(nbits))
438 *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
439 else
440 __bitmap_shift_right(dst, src, shift, nbits);
441}
442
443static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
444 unsigned int shift, unsigned int nbits)
445{
446 if (small_const_nbits(nbits))
447 *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
448 else
449 __bitmap_shift_left(dst, src, shift, nbits);
450}
451
452static inline void bitmap_replace(unsigned long *dst,
453 const unsigned long *old,
454 const unsigned long *new,
455 const unsigned long *mask,
456 unsigned int nbits)
457{
458 if (small_const_nbits(nbits))
459 *dst = (*old & ~(*mask)) | (*new & *mask);
460 else
461 __bitmap_replace(dst, old, new, mask, nbits);
462}
463
464static inline void bitmap_next_set_region(unsigned long *bitmap,
465 unsigned int *rs, unsigned int *re,
466 unsigned int end)
467{
468 *rs = find_next_bit(bitmap, end, *rs);
469 *re = find_next_zero_bit(bitmap, end, *rs + 1);
470}
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498#if __BITS_PER_LONG == 64
499#define BITMAP_FROM_U64(n) (n)
500#else
501#define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
502 ((unsigned long) ((u64)(n) >> 32))
503#endif
504
505
506
507
508
509
510
511
512
513
514
515static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
516{
517 dst[0] = mask & ULONG_MAX;
518
519 if (sizeof(mask) > sizeof(unsigned long))
520 dst[1] = mask >> 32;
521}
522
523
524
525
526
527
528
529
530
531static inline unsigned long bitmap_get_value8(const unsigned long *map,
532 unsigned long start)
533{
534 const size_t index = BIT_WORD(start);
535 const unsigned long offset = start % BITS_PER_LONG;
536
537 return (map[index] >> offset) & 0xFF;
538}
539
540
541
542
543
544
545
546static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
547 unsigned long start)
548{
549 const size_t index = BIT_WORD(start);
550 const unsigned long offset = start % BITS_PER_LONG;
551
552 map[index] &= ~(0xFFUL << offset);
553 map[index] |= value << offset;
554}
555
556#endif
557
558#endif
559