d9974c7a0a61c29f76865a215e2d7aead29a72d0
[muen/linux.git] / include / linux / bitmap.h
1 #ifndef __LINUX_BITMAP_H
2 #define __LINUX_BITMAP_H
3
4 #ifndef __ASSEMBLY__
5
6 #include <linux/types.h>
7 #include <linux/bitops.h>
8 #include <linux/string.h>
9 #include <linux/kernel.h>
10
11 /*
12  * bitmaps provide bit arrays that consume one or more unsigned
13  * longs.  The bitmap interface and available operations are listed
14  * here, in bitmap.h
15  *
16  * Function implementations generic to all architectures are in
17  * lib/bitmap.c.  Functions implementations that are architecture
18  * specific are in various include/asm-<arch>/bitops.h headers
19  * and other arch/<arch> specific files.
20  *
21  * See lib/bitmap.c for more details.
22  */
23
24 /**
25  * DOC: bitmap overview
26  *
27  * The available bitmap operations and their rough meaning in the
28  * case that the bitmap is a single unsigned long are thus:
29  *
30  * Note that nbits should be always a compile time evaluable constant.
31  * Otherwise many inlines will generate horrible code.
32  *
33  * ::
34  *
35  *  bitmap_zero(dst, nbits)                     *dst = 0UL
36  *  bitmap_fill(dst, nbits)                     *dst = ~0UL
37  *  bitmap_copy(dst, src, nbits)                *dst = *src
38  *  bitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2
39  *  bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2
40  *  bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2
41  *  bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)
42  *  bitmap_complement(dst, src, nbits)          *dst = ~(*src)
43  *  bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?
44  *  bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?
45  *  bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?
46  *  bitmap_empty(src, nbits)                    Are all bits zero in *src?
47  *  bitmap_full(src, nbits)                     Are all bits set in *src?
48  *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
49  *  bitmap_set(dst, pos, nbits)                 Set specified bit area
50  *  bitmap_clear(dst, pos, nbits)               Clear specified bit area
51  *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
52  *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask)  as above
53  *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
54  *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
55  *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
56  *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
57  *  bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
58  *  bitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod sz
59  *  bitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel buf
60  *  bitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user buf
61  *  bitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel buf
62  *  bitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user buf
63  *  bitmap_find_free_region(bitmap, bits, order)  Find and allocate bit region
64  *  bitmap_release_region(bitmap, pos, order)   Free specified bit region
65  *  bitmap_allocate_region(bitmap, pos, order)  Allocate specified bit region
66  *  bitmap_from_u32array(dst, nbits, buf, nwords)  *dst = *buf (nwords 32b words)
67  *  bitmap_to_u32array(buf, nwords, src, nbits) *buf = *dst (nwords 32b words)
68  *
69  */
70
71 /**
72  * DOC: bitmap bitops
73  *
74  * Also the following operations in asm/bitops.h apply to bitmaps.::
75  *
76  *  set_bit(bit, addr)                  *addr |= bit
77  *  clear_bit(bit, addr)                *addr &= ~bit
78  *  change_bit(bit, addr)               *addr ^= bit
79  *  test_bit(bit, addr)                 Is bit set in *addr?
80  *  test_and_set_bit(bit, addr)         Set bit and return old value
81  *  test_and_clear_bit(bit, addr)       Clear bit and return old value
82  *  test_and_change_bit(bit, addr)      Change bit and return old value
83  *  find_first_zero_bit(addr, nbits)    Position first zero bit in *addr
84  *  find_first_bit(addr, nbits)         Position first set bit in *addr
85  *  find_next_zero_bit(addr, nbits, bit)  Position next zero bit in *addr >= bit
86  *  find_next_bit(addr, nbits, bit)     Position next set bit in *addr >= bit
87  *
88  */
89
90 /**
91  * DOC: declare bitmap
92  * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
93  * to declare an array named 'name' of just enough unsigned longs to
94  * contain all bit positions from 0 to 'bits' - 1.
95  */
96
97 /*
98  * lib/bitmap.c provides these functions:
99  */
100
101 extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits);
102 extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits);
103 extern int __bitmap_equal(const unsigned long *bitmap1,
104                           const unsigned long *bitmap2, unsigned int nbits);
105 extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
106                         unsigned int nbits);
107 extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
108                                 unsigned int shift, unsigned int nbits);
109 extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
110                                 unsigned int shift, unsigned int nbits);
111 extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
112                         const unsigned long *bitmap2, unsigned int nbits);
113 extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
114                         const unsigned long *bitmap2, unsigned int nbits);
115 extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
116                         const unsigned long *bitmap2, unsigned int nbits);
117 extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
118                         const unsigned long *bitmap2, unsigned int nbits);
119 extern int __bitmap_intersects(const unsigned long *bitmap1,
120                         const unsigned long *bitmap2, unsigned int nbits);
121 extern int __bitmap_subset(const unsigned long *bitmap1,
122                         const unsigned long *bitmap2, unsigned int nbits);
123 extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
124 extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
125 extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
126
127 extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
128                                                     unsigned long size,
129                                                     unsigned long start,
130                                                     unsigned int nr,
131                                                     unsigned long align_mask,
132                                                     unsigned long align_offset);
133
134 /**
135  * bitmap_find_next_zero_area - find a contiguous aligned zero area
136  * @map: The address to base the search on
137  * @size: The bitmap size in bits
138  * @start: The bitnumber to start searching at
139  * @nr: The number of zeroed bits we're looking for
140  * @align_mask: Alignment mask for zero area
141  *
142  * The @align_mask should be one less than a power of 2; the effect is that
143  * the bit offset of all zero areas this function finds is multiples of that
144  * power of 2. A @align_mask of 0 means no alignment is required.
145  */
146 static inline unsigned long
147 bitmap_find_next_zero_area(unsigned long *map,
148                            unsigned long size,
149                            unsigned long start,
150                            unsigned int nr,
151                            unsigned long align_mask)
152 {
153         return bitmap_find_next_zero_area_off(map, size, start, nr,
154                                               align_mask, 0);
155 }
156
157 extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
158                         unsigned long *dst, int nbits);
159 extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
160                         unsigned long *dst, int nbits);
161 extern int bitmap_parselist(const char *buf, unsigned long *maskp,
162                         int nmaskbits);
163 extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
164                         unsigned long *dst, int nbits);
165 extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
166                 const unsigned long *old, const unsigned long *new, unsigned int nbits);
167 extern int bitmap_bitremap(int oldbit,
168                 const unsigned long *old, const unsigned long *new, int bits);
169 extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
170                 const unsigned long *relmap, unsigned int bits);
171 extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
172                 unsigned int sz, unsigned int nbits);
173 extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
174 extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
175 extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
176 extern unsigned int bitmap_from_u32array(unsigned long *bitmap,
177                                          unsigned int nbits,
178                                          const u32 *buf,
179                                          unsigned int nwords);
180 extern unsigned int bitmap_to_u32array(u32 *buf,
181                                        unsigned int nwords,
182                                        const unsigned long *bitmap,
183                                        unsigned int nbits);
184 #ifdef __BIG_ENDIAN
185 extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
186 #else
187 #define bitmap_copy_le bitmap_copy
188 #endif
189 extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
190 extern int bitmap_print_to_pagebuf(bool list, char *buf,
191                                    const unsigned long *maskp, int nmaskbits);
192
193 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
194 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
195
196 #define small_const_nbits(nbits) \
197         (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
198
199 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
200 {
201         if (small_const_nbits(nbits))
202                 *dst = 0UL;
203         else {
204                 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
205                 memset(dst, 0, len);
206         }
207 }
208
209 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
210 {
211         unsigned int nlongs = BITS_TO_LONGS(nbits);
212         if (!small_const_nbits(nbits)) {
213                 unsigned int len = (nlongs - 1) * sizeof(unsigned long);
214                 memset(dst, 0xff,  len);
215         }
216         dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
217 }
218
219 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
220                         unsigned int nbits)
221 {
222         if (small_const_nbits(nbits))
223                 *dst = *src;
224         else {
225                 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
226                 memcpy(dst, src, len);
227         }
228 }
229
230 static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
231                         const unsigned long *src2, unsigned int nbits)
232 {
233         if (small_const_nbits(nbits))
234                 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
235         return __bitmap_and(dst, src1, src2, nbits);
236 }
237
238 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
239                         const unsigned long *src2, unsigned int nbits)
240 {
241         if (small_const_nbits(nbits))
242                 *dst = *src1 | *src2;
243         else
244                 __bitmap_or(dst, src1, src2, nbits);
245 }
246
247 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
248                         const unsigned long *src2, unsigned int nbits)
249 {
250         if (small_const_nbits(nbits))
251                 *dst = *src1 ^ *src2;
252         else
253                 __bitmap_xor(dst, src1, src2, nbits);
254 }
255
256 static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
257                         const unsigned long *src2, unsigned int nbits)
258 {
259         if (small_const_nbits(nbits))
260                 return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
261         return __bitmap_andnot(dst, src1, src2, nbits);
262 }
263
264 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
265                         unsigned int nbits)
266 {
267         if (small_const_nbits(nbits))
268                 *dst = ~(*src);
269         else
270                 __bitmap_complement(dst, src, nbits);
271 }
272
273 static inline int bitmap_equal(const unsigned long *src1,
274                         const unsigned long *src2, unsigned int nbits)
275 {
276         if (small_const_nbits(nbits))
277                 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
278         if (__builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
279                 return !memcmp(src1, src2, nbits / 8);
280         return __bitmap_equal(src1, src2, nbits);
281 }
282
283 static inline int bitmap_intersects(const unsigned long *src1,
284                         const unsigned long *src2, unsigned int nbits)
285 {
286         if (small_const_nbits(nbits))
287                 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
288         else
289                 return __bitmap_intersects(src1, src2, nbits);
290 }
291
292 static inline int bitmap_subset(const unsigned long *src1,
293                         const unsigned long *src2, unsigned int nbits)
294 {
295         if (small_const_nbits(nbits))
296                 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
297         else
298                 return __bitmap_subset(src1, src2, nbits);
299 }
300
301 static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
302 {
303         if (small_const_nbits(nbits))
304                 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
305
306         return find_first_bit(src, nbits) == nbits;
307 }
308
309 static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
310 {
311         if (small_const_nbits(nbits))
312                 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
313
314         return find_first_zero_bit(src, nbits) == nbits;
315 }
316
317 static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
318 {
319         if (small_const_nbits(nbits))
320                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
321         return __bitmap_weight(src, nbits);
322 }
323
324 static __always_inline void bitmap_set(unsigned long *map, unsigned int start,
325                 unsigned int nbits)
326 {
327         if (__builtin_constant_p(nbits) && nbits == 1)
328                 __set_bit(start, map);
329         else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
330                  __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
331                 memset((char *)map + start / 8, 0xff, nbits / 8);
332         else
333                 __bitmap_set(map, start, nbits);
334 }
335
336 static __always_inline void bitmap_clear(unsigned long *map, unsigned int start,
337                 unsigned int nbits)
338 {
339         if (__builtin_constant_p(nbits) && nbits == 1)
340                 __clear_bit(start, map);
341         else if (__builtin_constant_p(start & 7) && IS_ALIGNED(start, 8) &&
342                  __builtin_constant_p(nbits & 7) && IS_ALIGNED(nbits, 8))
343                 memset((char *)map + start / 8, 0, nbits / 8);
344         else
345                 __bitmap_clear(map, start, nbits);
346 }
347
348 static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
349                                 unsigned int shift, int nbits)
350 {
351         if (small_const_nbits(nbits))
352                 *dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
353         else
354                 __bitmap_shift_right(dst, src, shift, nbits);
355 }
356
357 static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
358                                 unsigned int shift, unsigned int nbits)
359 {
360         if (small_const_nbits(nbits))
361                 *dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
362         else
363                 __bitmap_shift_left(dst, src, shift, nbits);
364 }
365
366 static inline int bitmap_parse(const char *buf, unsigned int buflen,
367                         unsigned long *maskp, int nmaskbits)
368 {
369         return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
370 }
371
372 /**
373  * BITMAP_FROM_U64() - Represent u64 value in the format suitable for bitmap.
374  * @n: u64 value
375  *
376  * Linux bitmaps are internally arrays of unsigned longs, i.e. 32-bit
377  * integers in 32-bit environment, and 64-bit integers in 64-bit one.
378  *
379  * There are four combinations of endianness and length of the word in linux
380  * ABIs: LE64, BE64, LE32 and BE32.
381  *
382  * On 64-bit kernels 64-bit LE and BE numbers are naturally ordered in
383  * bitmaps and therefore don't require any special handling.
384  *
385  * On 32-bit kernels 32-bit LE ABI orders lo word of 64-bit number in memory
386  * prior to hi, and 32-bit BE orders hi word prior to lo. The bitmap on the
387  * other hand is represented as an array of 32-bit words and the position of
388  * bit N may therefore be calculated as: word #(N/32) and bit #(N%32) in that
389  * word.  For example, bit #42 is located at 10th position of 2nd word.
390  * It matches 32-bit LE ABI, and we can simply let the compiler store 64-bit
391  * values in memory as it usually does. But for BE we need to swap hi and lo
392  * words manually.
393  *
394  * With all that, the macro BITMAP_FROM_U64() does explicit reordering of hi and
395  * lo parts of u64.  For LE32 it does nothing, and for BE environment it swaps
396  * hi and lo words, as is expected by bitmap.
397  */
398 #if __BITS_PER_LONG == 64
399 #define BITMAP_FROM_U64(n) (n)
400 #else
401 #define BITMAP_FROM_U64(n) ((unsigned long) ((u64)(n) & ULONG_MAX)), \
402                                 ((unsigned long) ((u64)(n) >> 32))
403 #endif
404
405 /**
406  * bitmap_from_u64 - Check and swap words within u64.
407  *  @mask: source bitmap
408  *  @dst:  destination bitmap
409  *
410  * In 32-bit Big Endian kernel, when using ``(u32 *)(&val)[*]``
411  * to read u64 mask, we will get the wrong word.
412  * That is ``(u32 *)(&val)[0]`` gets the upper 32 bits,
413  * but we expect the lower 32-bits of u64.
414  */
415 static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
416 {
417         dst[0] = mask & ULONG_MAX;
418
419         if (sizeof(mask) > sizeof(unsigned long))
420                 dst[1] = mask >> 32;
421 }
422
423 #endif /* __ASSEMBLY__ */
424
425 #endif /* __LINUX_BITMAP_H */