bitmap.h 13.2 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8
#ifndef __LINUX_BITMAP_H
#define __LINUX_BITMAP_H

#ifndef __ASSEMBLY__

#include <linux/types.h>
#include <linux/bitops.h>
#include <linux/string.h>
J
Jiri Slaby 已提交
9
#include <linux/kernel.h>
L
Linus Torvalds 已提交
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/*
 * bitmaps provide bit arrays that consume one or more unsigned
 * longs.  The bitmap interface and available operations are listed
 * here, in bitmap.h
 *
 * Function implementations generic to all architectures are in
 * lib/bitmap.c.  Functions implementations that are architecture
 * specific are in various include/asm-<arch>/bitops.h headers
 * and other arch/<arch> specific files.
 *
 * See lib/bitmap.c for more details.
 */

/*
 * The available bitmap operations and their rough meaning in the
 * case that the bitmap is a single unsigned long are thus:
 *
28 29 30
 * Note that nbits should be always a compile time evaluable constant.
 * Otherwise many inlines will generate horrible code.
 *
L
Linus Torvalds 已提交
31 32 33 34 35 36 37 38 39 40 41 42 43 44
 * bitmap_zero(dst, nbits)			*dst = 0UL
 * bitmap_fill(dst, nbits)			*dst = ~0UL
 * bitmap_copy(dst, src, nbits)			*dst = *src
 * bitmap_and(dst, src1, src2, nbits)		*dst = *src1 & *src2
 * bitmap_or(dst, src1, src2, nbits)		*dst = *src1 | *src2
 * bitmap_xor(dst, src1, src2, nbits)		*dst = *src1 ^ *src2
 * bitmap_andnot(dst, src1, src2, nbits)	*dst = *src1 & ~(*src2)
 * bitmap_complement(dst, src, nbits)		*dst = ~(*src)
 * bitmap_equal(src1, src2, nbits)		Are *src1 and *src2 equal?
 * bitmap_intersects(src1, src2, nbits) 	Do *src1 and *src2 overlap?
 * bitmap_subset(src1, src2, nbits)		Is *src1 a subset of *src2?
 * bitmap_empty(src, nbits)			Are all bits zero in *src?
 * bitmap_full(src, nbits)			Are all bits set in *src?
 * bitmap_weight(src, nbits)			Hamming Weight: number set bits
45 46 47
 * bitmap_set(dst, pos, nbits)			Set specified bit area
 * bitmap_clear(dst, pos, nbits)		Clear specified bit area
 * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
48
 * bitmap_find_next_zero_area_off(buf, len, pos, n, mask)	as above
L
Linus Torvalds 已提交
49 50
 * bitmap_shift_right(dst, src, n, nbits)	*dst = *src >> n
 * bitmap_shift_left(dst, src, n, nbits)	*dst = *src << n
51 52
 * bitmap_remap(dst, src, old, new, nbits)	*dst = map(old, new)(src)
 * bitmap_bitremap(oldbit, old, new, nbits)	newbit = map(old, new)(oldbit)
53 54
 * bitmap_onto(dst, orig, relmap, nbits)	*dst = orig relative to relmap
 * bitmap_fold(dst, orig, sz, nbits)		dst bits = orig bits mod sz
55 56
 * bitmap_parse(buf, buflen, dst, nbits)	Parse bitmap dst from kernel buf
 * bitmap_parse_user(ubuf, ulen, dst, nbits)	Parse bitmap dst from user buf
57 58
 * bitmap_parselist(buf, dst, nbits)		Parse bitmap dst from kernel buf
 * bitmap_parselist_user(buf, dst, nbits)	Parse bitmap dst from user buf
P
Paul Jackson 已提交
59 60 61
 * bitmap_find_free_region(bitmap, bits, order)	Find and allocate bit region
 * bitmap_release_region(bitmap, pos, order)	Free specified bit region
 * bitmap_allocate_region(bitmap, pos, order)	Allocate specified bit region
62 63
 * bitmap_from_u32array(dst, nbits, buf, nwords) *dst = *buf (nwords 32b words)
 * bitmap_to_u32array(buf, nwords, src, nbits)	*buf = *dst (nwords 32b words)
L
Linus Torvalds 已提交
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
 */

/*
 * Also the following operations in asm/bitops.h apply to bitmaps.
 *
 * set_bit(bit, addr)			*addr |= bit
 * clear_bit(bit, addr)			*addr &= ~bit
 * change_bit(bit, addr)		*addr ^= bit
 * test_bit(bit, addr)			Is bit set in *addr?
 * test_and_set_bit(bit, addr)		Set bit and return old value
 * test_and_clear_bit(bit, addr)	Clear bit and return old value
 * test_and_change_bit(bit, addr)	Change bit and return old value
 * find_first_zero_bit(addr, nbits)	Position first zero bit in *addr
 * find_first_bit(addr, nbits)		Position first set bit in *addr
 * find_next_zero_bit(addr, nbits, bit)	Position next zero bit in *addr >= bit
 * find_next_bit(addr, nbits, bit)	Position next set bit in *addr >= bit
 */

/*
 * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
 * to declare an array named 'name' of just enough unsigned longs to
 * contain all bit positions from 0 to 'bits' - 1.
 */

/*
 * lib/bitmap.c provides these functions:
 */

92
extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits);
93
extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits);
L
Linus Torvalds 已提交
94
extern int __bitmap_equal(const unsigned long *bitmap1,
95
			  const unsigned long *bitmap2, unsigned int nbits);
L
Linus Torvalds 已提交
96
extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
97
			unsigned int nbits);
98 99
extern void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
				unsigned int shift, unsigned int nbits);
100 101
extern void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
				unsigned int shift, unsigned int nbits);
102
extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
103
			const unsigned long *bitmap2, unsigned int nbits);
L
Linus Torvalds 已提交
104
extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
105
			const unsigned long *bitmap2, unsigned int nbits);
L
Linus Torvalds 已提交
106
extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
107
			const unsigned long *bitmap2, unsigned int nbits);
108
extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
109
			const unsigned long *bitmap2, unsigned int nbits);
L
Linus Torvalds 已提交
110
extern int __bitmap_intersects(const unsigned long *bitmap1,
111
			const unsigned long *bitmap2, unsigned int nbits);
L
Linus Torvalds 已提交
112
extern int __bitmap_subset(const unsigned long *bitmap1,
113
			const unsigned long *bitmap2, unsigned int nbits);
114
extern int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
L
Linus Torvalds 已提交
115

116
extern void bitmap_set(unsigned long *map, unsigned int start, int len);
117
extern void bitmap_clear(unsigned long *map, unsigned int start, int len);
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147

extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
						    unsigned long size,
						    unsigned long start,
						    unsigned int nr,
						    unsigned long align_mask,
						    unsigned long align_offset);

/**
 * bitmap_find_next_zero_area - find a contiguous aligned zero area
 * @map: The address to base the search on
 * @size: The bitmap size in bits
 * @start: The bitnumber to start searching at
 * @nr: The number of zeroed bits we're looking for
 * @align_mask: Alignment mask for zero area
 *
 * The @align_mask should be one less than a power of 2; the effect is that
 * the bit offset of all zero areas this function finds is multiples of that
 * power of 2. A @align_mask of 0 means no alignment is required.
 */
static inline unsigned long
bitmap_find_next_zero_area(unsigned long *map,
			   unsigned long size,
			   unsigned long start,
			   unsigned int nr,
			   unsigned long align_mask)
{
	return bitmap_find_next_zero_area_off(map, size, start, nr,
					      align_mask, 0);
}
148

149 150 151
extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
			unsigned long *dst, int nbits);
extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
L
Linus Torvalds 已提交
152 153 154
			unsigned long *dst, int nbits);
extern int bitmap_parselist(const char *buf, unsigned long *maskp,
			int nmaskbits);
155 156
extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
			unsigned long *dst, int nbits);
157
extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
158
		const unsigned long *old, const unsigned long *new, unsigned int nbits);
159 160
extern int bitmap_bitremap(int oldbit,
		const unsigned long *old, const unsigned long *new, int bits);
161
extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
162
		const unsigned long *relmap, unsigned int bits);
163
extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
164
		unsigned int sz, unsigned int nbits);
165 166 167
extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
168 169 170 171 172 173 174 175
extern unsigned int bitmap_from_u32array(unsigned long *bitmap,
					 unsigned int nbits,
					 const u32 *buf,
					 unsigned int nwords);
extern unsigned int bitmap_to_u32array(u32 *buf,
				       unsigned int nwords,
				       const unsigned long *bitmap,
				       unsigned int nbits);
176
#ifdef __BIG_ENDIAN
177
extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
178 179 180
#else
#define bitmap_copy_le bitmap_copy
#endif
181
extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
182 183
extern int bitmap_print_to_pagebuf(bool list, char *buf,
				   const unsigned long *maskp, int nmaskbits);
L
Linus Torvalds 已提交
184

185 186
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
L
Linus Torvalds 已提交
187

188 189 190
#define small_const_nbits(nbits) \
	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

191
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
L
Linus Torvalds 已提交
192
{
193
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
194 195
		*dst = 0UL;
	else {
196
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
L
Linus Torvalds 已提交
197 198 199 200
		memset(dst, 0, len);
	}
}

201
static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
L
Linus Torvalds 已提交
202
{
203
	unsigned int nlongs = BITS_TO_LONGS(nbits);
204
	if (!small_const_nbits(nbits)) {
205
		unsigned int len = (nlongs - 1) * sizeof(unsigned long);
L
Linus Torvalds 已提交
206 207 208 209 210 211
		memset(dst, 0xff,  len);
	}
	dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
212
			unsigned int nbits)
L
Linus Torvalds 已提交
213
{
214
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
215 216
		*dst = *src;
	else {
217
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
L
Linus Torvalds 已提交
218 219 220 221
		memcpy(dst, src, len);
	}
}

222
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
223
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
224
{
225
	if (small_const_nbits(nbits))
226
		return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
227
	return __bitmap_and(dst, src1, src2, nbits);
L
Linus Torvalds 已提交
228 229 230
}

static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
231
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
232
{
233
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
234 235 236 237 238 239
		*dst = *src1 | *src2;
	else
		__bitmap_or(dst, src1, src2, nbits);
}

static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
240
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
241
{
242
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
243 244 245 246 247
		*dst = *src1 ^ *src2;
	else
		__bitmap_xor(dst, src1, src2, nbits);
}

248
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
249
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
250
{
251
	if (small_const_nbits(nbits))
252
		return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
253
	return __bitmap_andnot(dst, src1, src2, nbits);
L
Linus Torvalds 已提交
254 255 256
}

static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
257
			unsigned int nbits)
L
Linus Torvalds 已提交
258
{
259
	if (small_const_nbits(nbits))
260
		*dst = ~(*src);
L
Linus Torvalds 已提交
261 262 263 264 265
	else
		__bitmap_complement(dst, src, nbits);
}

static inline int bitmap_equal(const unsigned long *src1,
266
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
267
{
268
	if (small_const_nbits(nbits))
A
Andrew Morton 已提交
269
		return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
270
#ifdef CONFIG_S390
A
Andrew Morton 已提交
271
	if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
272 273
		return !memcmp(src1, src2, nbits / 8);
#endif
A
Andrew Morton 已提交
274
	return __bitmap_equal(src1, src2, nbits);
L
Linus Torvalds 已提交
275 276 277
}

static inline int bitmap_intersects(const unsigned long *src1,
278
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
279
{
280
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
281 282 283 284 285 286
		return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
	else
		return __bitmap_intersects(src1, src2, nbits);
}

static inline int bitmap_subset(const unsigned long *src1,
287
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
288
{
289
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
290 291 292 293 294
		return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_subset(src1, src2, nbits);
}

295
static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
L
Linus Torvalds 已提交
296
{
297
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
298
		return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
299 300

	return find_first_bit(src, nbits) == nbits;
L
Linus Torvalds 已提交
301 302
}

303
static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
L
Linus Torvalds 已提交
304
{
305
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
306
		return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
307 308

	return find_first_zero_bit(src, nbits) == nbits;
L
Linus Torvalds 已提交
309 310
}

311
static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
L
Linus Torvalds 已提交
312
{
313
	if (small_const_nbits(nbits))
314
		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
L
Linus Torvalds 已提交
315 316 317
	return __bitmap_weight(src, nbits);
}

318 319
static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
				unsigned int shift, int nbits)
L
Linus Torvalds 已提交
320
{
321
	if (small_const_nbits(nbits))
322
		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
L
Linus Torvalds 已提交
323
	else
324
		__bitmap_shift_right(dst, src, shift, nbits);
L
Linus Torvalds 已提交
325 326
}

327 328
static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
				unsigned int shift, unsigned int nbits)
L
Linus Torvalds 已提交
329
{
330
	if (small_const_nbits(nbits))
331
		*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
L
Linus Torvalds 已提交
332
	else
333
		__bitmap_shift_left(dst, src, shift, nbits);
L
Linus Torvalds 已提交
334 335
}

336 337 338 339 340 341
static inline int bitmap_parse(const char *buf, unsigned int buflen,
			unsigned long *maskp, int nmaskbits)
{
	return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
}

342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359
/*
 * bitmap_from_u64 - Check and swap words within u64.
 *  @mask: source bitmap
 *  @dst:  destination bitmap
 *
 * In 32-bit Big Endian kernel, when using (u32 *)(&val)[*]
 * to read u64 mask, we will get the wrong word.
 * That is "(u32 *)(&val)[0]" gets the upper 32 bits,
 * but we expect the lower 32-bits of u64.
 */
static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
{
	dst[0] = mask & ULONG_MAX;

	if (sizeof(mask) > sizeof(unsigned long))
		dst[1] = mask >> 32;
}

L
Linus Torvalds 已提交
360 361 362
#endif /* __ASSEMBLY__ */

#endif /* __LINUX_BITMAP_H */