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
230#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
231#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
232
233static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
234{
235 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
236 memset(dst, 0, len);
237}
238
239static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
240{
241 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
242 memset(dst, 0xff, len);
243}
244
245static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
246 unsigned int nbits)
247{
248 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
249 memcpy(dst, src, len);
250}
251
252
253
254
255static inline void bitmap_copy_clear_tail(unsigned long *dst,
256 const unsigned long *src, unsigned int nbits)
257{
258 bitmap_copy(dst, src, nbits);
259 if (nbits % BITS_PER_LONG)
260 dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
261}
262
263
264
265
266
267#if BITS_PER_LONG == 64
268void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
269 unsigned int nbits);
270void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
271 unsigned int nbits);
272#else
273#define bitmap_from_arr32(bitmap, buf, nbits) \
274 bitmap_copy_clear_tail((unsigned long *) (bitmap), \
275 (const unsigned long *) (buf), (nbits))
276#define bitmap_to_arr32(buf, bitmap, nbits) \
277 bitmap_copy_clear_tail((unsigned long *) (buf), \
278 (const unsigned long *) (bitmap), (nbits))
279#endif
280
281static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
282 const unsigned long *src2, unsigned int nbits)
283{
284 if (small_const_nbits(nbits))
285 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
286 return __bitmap_and(dst, src1, src2, nbits);
287}
288
289static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
290 const unsigned long *src2, unsigned int nbits)
291{
292 if (small_const_nbits(nbits))
293 *dst = *src1 | *src2;
294 else
295 __bitmap_or(dst, src1, src2, nbits);
296}
297
298static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
299 const unsigned long *src2, unsigned int nbits)
300{
301 if (small_const_nbits(nbits))
302 *dst = *src1 ^ *src2;
303 else
304 __bitmap_xor(dst, src1, src2, nbits);
305}
306
307static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
308 const unsigned long *src2, unsigned int nbits)
309{
310 if (small_const_nbits(nbits))
311 return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
312 return __bitmap_andnot(dst, src1, src2, nbits);
313}
314
315static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
316 unsigned int nbits)
317{
318 if (small_const_nbits(nbits))
319 *dst = ~(*src);
320 else
321 __bitmap_complement(dst, src, nbits);
322}
323
324#ifdef __LITTLE_ENDIAN
325#define BITMAP_MEM_ALIGNMENT 8
326#else
327#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
328#endif
329#define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
330
331static inline int bitmap_equal(const unsigned long *src1,
332 const unsigned long *src2, unsigned int nbits)
333{
334 if (small_const_nbits(nbits))
335 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
336 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
337 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
338 return !memcmp(src1, src2, nbits / 8);
339 return __bitmap_equal(src1, src2, nbits);
340}
341
342
343
344
345
346
347
348
349
350
351static inline bool bitmap_or_equal(const unsigned long *src1,
352 const unsigned long *src2,
353 const unsigned long *src3,
354 unsigned int nbits)
355{
356 if (!small_const_nbits(nbits))
357 return __bitmap_or_equal(src1, src2, src3, nbits);
358
359 return !(((*src1 | *src2) ^ *src3) & BITMAP_LAST_WORD_MASK(nbits));
360}
361
362static inline int bitmap_intersects(const unsigned long *src1,
363 const unsigned long *src2, unsigned int nbits)
364{
365 if (small_const_nbits(nbits))
366 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
367 else
368 return __bitmap_intersects(src1, src2, nbits);
369}
370
371static inline int bitmap_subset(const unsigned long *src1,
372 const unsigned long *src2, unsigned int nbits)
373{
374 if (small_const_nbits(nbits))
375 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
376 else
377 return __bitmap_subset(src1, src2, nbits);
378}
379
380static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
381{
382 if (small_const_nbits(nbits))
383 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
384
385 return find_first_bit(src, nbits) == nbits;
386}
387
388static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
389{
390 if (small_const_nbits(nbits))
391 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
392
393 return find_first_zero_bit(src, nbits) == nbits;
394}
395
396static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
397{
398 if (small_const_nbits(nbits))
399 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
400 return __bitmap_weight(src, nbits);
401}
402
403static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
404 unsigned int nbits)
405{
406 if (__builtin_constant_p(nbits) && nbits == 1)
407 __set_bit(start, map);
408 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
409 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
410 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
411 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
412 memset((char *)map + start / 8, 0xff, nbits / 8);
413 else
414 __bitmap_set(map, start, nbits);
415}
416
417static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
418 unsigned int nbits)
419{
420 if (__builtin_constant_p(nbits) && nbits == 1)
421 __clear_bit(start, map);
422 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
423 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
424 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
425 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
426 memset((char *)map + start / 8, 0, nbits / 8);
427 else
428 __bitmap_clear(map, start, nbits);
429}
430
431static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
432 unsigned int shift, unsigned int nbits)
433{
434 if (small_const_nbits(nbits))
435 *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
436 else
437 __bitmap_shift_right(dst, src, shift, nbits);
438}
439
440static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
441 unsigned int shift, unsigned int nbits)
442{
443 if (small_const_nbits(nbits))
444 *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
445 else
446 __bitmap_shift_left(dst, src, shift, nbits);
447}
448
449static inline void bitmap_replace(unsigned long *dst,
450 const unsigned long *old,
451 const unsigned long *new,
452 const unsigned long *mask,
453 unsigned int nbits)
454{
455 if (small_const_nbits(nbits))
456 *dst = (*old & ~(*mask)) | (*new & *mask);
457 else
458 __bitmap_replace(dst, old, new, mask, nbits);
459}
460
461static inline void bitmap_next_clear_region(unsigned long *bitmap,
462 unsigned int *rs, unsigned int *re,
463 unsigned int end)
464{
465 *rs = find_next_zero_bit(bitmap, end, *rs);
466 *re = find_next_bit(bitmap, end, *rs + 1);
467}
468
469static inline void bitmap_next_set_region(unsigned long *bitmap,
470 unsigned int *rs, unsigned int *re,
471 unsigned int end)
472{
473 *rs = find_next_bit(bitmap, end, *rs);
474 *re = find_next_zero_bit(bitmap, end, *rs + 1);
475}
476
477
478
479
480
481
482#define bitmap_for_each_clear_region(bitmap, rs, re, start, end) \
483 for ((rs) = (start), \
484 bitmap_next_clear_region((bitmap), &(rs), &(re), (end)); \
485 (rs) < (re); \
486 (rs) = (re) + 1, \
487 bitmap_next_clear_region((bitmap), &(rs), &(re), (end)))
488
489#define bitmap_for_each_set_region(bitmap, rs, re, start, end) \
490 for ((rs) = (start), \
491 bitmap_next_set_region((bitmap), &(rs), &(re), (end)); \
492 (rs) < (re); \
493 (rs) = (re) + 1, \
494 bitmap_next_set_region((bitmap), &(rs), &(re), (end)))
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522#if __BITS_PER_LONG == 64
523#define BITMAP_FROM_U64(n) (n)
524#else
525#define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
526 ((unsigned long) ((u64)(n) >> 32))
527#endif
528
529
530
531
532
533
534
535
536
537
538
539static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
540{
541 dst[0] = mask & ULONG_MAX;
542
543 if (sizeof(mask) > sizeof(unsigned long))
544 dst[1] = mask >> 32;
545}
546
547
548
549
550
551
552
553
554
555static inline unsigned long bitmap_get_value8(const unsigned long *map,
556 unsigned long start)
557{
558 const size_t index = BIT_WORD(start);
559 const unsigned long offset = start % BITS_PER_LONG;
560
561 return (map[index] >> offset) & 0xFF;
562}
563
564
565
566
567
568
569
570static inline void bitmap_set_value8(unsigned long *map, unsigned long value,
571 unsigned long start)
572{
573 const size_t index = BIT_WORD(start);
574 const unsigned long offset = start % BITS_PER_LONG;
575
576 map[index] &= ~(0xFFUL << offset);
577 map[index] |= value << offset;
578}
579
580#endif
581
582#endif
583