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