1
2#ifndef __LINUX_BITMAP_H
3#define __LINUX_BITMAP_H
4
5#ifndef __ASSEMBLY__
6
7#include <linux/types.h>
8#include <linux/bitops.h>
9#include <linux/string.h>
10#include <linux/kernel.h>
11
12
13
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
111extern unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags);
112extern unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags);
113extern void bitmap_free(const unsigned long *bitmap);
114
115
116
117
118
119extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits);
120extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits);
121extern int __bitmap_equal(const unsigned long *bitmap1,
122 const unsigned long *bitmap2, unsigned int nbits);
123extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
124 unsigned int nbits);
125extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
126 unsigned int shift, unsigned int nbits);
127extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
128 unsigned int shift, unsigned int nbits);
129extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
130 const unsigned long *bitmap2, unsigned int nbits);
131extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
132 const unsigned long *bitmap2, unsigned int nbits);
133extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
134 const unsigned long *bitmap2, unsigned int nbits);
135extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
136 const unsigned long *bitmap2, unsigned int nbits);
137extern int __bitmap_intersects(const unsigned long *bitmap1,
138 const unsigned long *bitmap2, unsigned int nbits);
139extern int __bitmap_subset(const unsigned long *bitmap1,
140 const unsigned long *bitmap2, unsigned int nbits);
141extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
142extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
143extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
144
145extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
146 unsigned long size,
147 unsigned long start,
148 unsigned int nr,
149 unsigned long align_mask,
150 unsigned long align_offset);
151
152
153
154
155
156
157
158
159
160
161
162
163
164static inline unsigned long
165bitmap_find_next_zero_area(unsigned long *map,
166 unsigned long size,
167 unsigned long start,
168 unsigned int nr,
169 unsigned long align_mask)
170{
171 return bitmap_find_next_zero_area_off(map, size, start, nr,
172 align_mask, 0);
173}
174
175extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
176 unsigned long *dst, int nbits);
177extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
178 unsigned long *dst, int nbits);
179extern int bitmap_parselist(const char *buf, unsigned long *maskp,
180 int nmaskbits);
181extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
182 unsigned long *dst, int nbits);
183extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
184 const unsigned long *old, const unsigned long *new, unsigned int nbits);
185extern int bitmap_bitremap(int oldbit,
186 const unsigned long *old, const unsigned long *new, int bits);
187extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
188 const unsigned long *relmap, unsigned int bits);
189extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
190 unsigned int sz, unsigned int nbits);
191extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
192extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
193extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
194
195#ifdef __BIG_ENDIAN
196extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
197#else
198#define bitmap_copy_le bitmap_copy
199#endif
200extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
201extern int bitmap_print_to_pagebuf(bool list, char *buf,
202 const unsigned long *maskp, int nmaskbits);
203
204#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
205#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
206
207
208
209
210
211
212#define small_const_nbits(nbits) \
213 (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)
214
215static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
216{
217 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
218 memset(dst, 0, len);
219}
220
221static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
222{
223 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
224 memset(dst, 0xff, len);
225}
226
227static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
228 unsigned int nbits)
229{
230 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
231 memcpy(dst, src, len);
232}
233
234
235
236
237static inline void bitmap_copy_clear_tail(unsigned long *dst,
238 const unsigned long *src, unsigned int nbits)
239{
240 bitmap_copy(dst, src, nbits);
241 if (nbits % BITS_PER_LONG)
242 dst[nbits / BITS_PER_LONG] &= BITMAP_LAST_WORD_MASK(nbits);
243}
244
245
246
247
248
249#if BITS_PER_LONG == 64
250extern void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf,
251 unsigned int nbits);
252extern void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap,
253 unsigned int nbits);
254#else
255#define bitmap_from_arr32(bitmap, buf, nbits) \
256 bitmap_copy_clear_tail((unsigned long *) (bitmap), \
257 (const unsigned long *) (buf), (nbits))
258#define bitmap_to_arr32(buf, bitmap, nbits) \
259 bitmap_copy_clear_tail((unsigned long *) (buf), \
260 (const unsigned long *) (bitmap), (nbits))
261#endif
262
263static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
264 const unsigned long *src2, unsigned int nbits)
265{
266 if (small_const_nbits(nbits))
267 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
268 return __bitmap_and(dst, src1, src2, nbits);
269}
270
271static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
272 const unsigned long *src2, unsigned int nbits)
273{
274 if (small_const_nbits(nbits))
275 *dst = *src1 | *src2;
276 else
277 __bitmap_or(dst, src1, src2, nbits);
278}
279
280static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
281 const unsigned long *src2, unsigned int nbits)
282{
283 if (small_const_nbits(nbits))
284 *dst = *src1 ^ *src2;
285 else
286 __bitmap_xor(dst, src1, src2, nbits);
287}
288
289static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
290 const unsigned long *src2, unsigned int nbits)
291{
292 if (small_const_nbits(nbits))
293 return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
294 return __bitmap_andnot(dst, src1, src2, nbits);
295}
296
297static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
298 unsigned int nbits)
299{
300 if (small_const_nbits(nbits))
301 *dst = ~(*src);
302 else
303 __bitmap_complement(dst, src, nbits);
304}
305
306#ifdef __LITTLE_ENDIAN
307#define BITMAP_MEM_ALIGNMENT 8
308#else
309#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
310#endif
311#define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
312
313static inline int bitmap_equal(const unsigned long *src1,
314 const unsigned long *src2, unsigned int nbits)
315{
316 if (small_const_nbits(nbits))
317 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
318 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
319 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
320 return !memcmp(src1, src2, nbits / 8);
321 return __bitmap_equal(src1, src2, nbits);
322}
323
324static inline int bitmap_intersects(const unsigned long *src1,
325 const unsigned long *src2, unsigned int nbits)
326{
327 if (small_const_nbits(nbits))
328 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
329 else
330 return __bitmap_intersects(src1, src2, nbits);
331}
332
333static inline int bitmap_subset(const unsigned long *src1,
334 const unsigned long *src2, unsigned int nbits)
335{
336 if (small_const_nbits(nbits))
337 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
338 else
339 return __bitmap_subset(src1, src2, nbits);
340}
341
342static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
343{
344 if (small_const_nbits(nbits))
345 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
346
347 return find_first_bit(src, nbits) == nbits;
348}
349
350static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
351{
352 if (small_const_nbits(nbits))
353 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
354
355 return find_first_zero_bit(src, nbits) == nbits;
356}
357
358static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
359{
360 if (small_const_nbits(nbits))
361 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
362 return __bitmap_weight(src, nbits);
363}
364
365static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
366 unsigned int nbits)
367{
368 if (__builtin_constant_p(nbits) && nbits == 1)
369 __set_bit(start, map);
370 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
371 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
372 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
373 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
374 memset((char *)map + start / 8, 0xff, nbits / 8);
375 else
376 __bitmap_set(map, start, nbits);
377}
378
379static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
380 unsigned int nbits)
381{
382 if (__builtin_constant_p(nbits) && nbits == 1)
383 __clear_bit(start, map);
384 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
385 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
386 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
387 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
388 memset((char *)map + start / 8, 0, nbits / 8);
389 else
390 __bitmap_clear(map, start, nbits);
391}
392
393static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
394 unsigned int shift, unsigned int nbits)
395{
396 if (small_const_nbits(nbits))
397 *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
398 else
399 __bitmap_shift_right(dst, src, shift, nbits);
400}
401
402static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
403 unsigned int shift, unsigned int nbits)
404{
405 if (small_const_nbits(nbits))
406 *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
407 else
408 __bitmap_shift_left(dst, src, shift, nbits);
409}
410
411static inline int bitmap_parse(const char *buf, unsigned int buflen,
412 unsigned long *maskp, int nmaskbits)
413{
414 return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
415}
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443#if __BITS_PER_LONG == 64
444#define BITMAP_FROM_U64(n) (n)
445#else
446#define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
447 ((unsigned long) ((u64)(n) >> 32))
448#endif
449
450
451
452
453
454
455
456
457
458
459
460static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
461{
462 dst[0] = mask & ULONG_MAX;
463
464 if (sizeof(mask) > sizeof(unsigned long))
465 dst[1] = mask >> 32;
466}
467
468#endif
469
470#endif
471