/* * lib/bitmap.c * Helper functions for bitmap.h. * * This source code is licensed under the GNU General Public License, * Version 2.  See the file COPYING for more details. */#include <linux/module.h>#include <linux/ctype.h>#include <linux/errno.h>#include <linux/bitmap.h>#include <linux/bitops.h>#include <asm/uaccess.h> /* * bitmaps provide an array of bits, implemented using an an * array of unsigned longs.  The number of valid bits in a * given bitmap does _not_ need to be an exact multiple of * BITS_PER_LONG. * * The possible unused bits in the last, partially used word * of a bitmap are 'don't care'.  The implementation makes * no particular effort to keep them zero.  It ensures that * their value will not affect the results of any operation. * The bitmap operations that return Boolean (bitmap_empty, * for example) or scalar (bitmap_weight, for example) results * carefully filter out these unused bits from impacting their * results. * * These operations actually hold to a slightly stronger rule: * if you don't input any bitmaps to these ops that have some * unused bits set, then they won't output any set unused bits * in output bitmaps. * * The byte ordering of bitmaps is more natural on little * endian architectures.  See the big-endian headers * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h * for the best explanations of this ordering. */ int __bitmap_empty(const unsigned long *bitmap, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		if (bitmap[k])			return 0; 	if (bits % BITS_PER_LONG)		if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))			return 0; 	return 1;}EXPORT_SYMBOL(__bitmap_empty); int __bitmap_full(const unsigned long *bitmap, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		if (~bitmap[k])			return 0; 	if (bits % BITS_PER_LONG)		if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))			return 0; 	return 1;}EXPORT_SYMBOL(__bitmap_full); int __bitmap_equal(const unsigned long *bitmap1,		const unsigned long *bitmap2, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		if (bitmap1[k] != bitmap2[k])			return 0; 	if (bits % BITS_PER_LONG)		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))			return 0; 	return 1;}EXPORT_SYMBOL(__bitmap_equal); void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		dst[k] = ~src[k]; 	if (bits % BITS_PER_LONG)		dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);}EXPORT_SYMBOL(__bitmap_complement); /** * __bitmap_shift_right - logical right shift of the bits in a bitmap *   @dst : destination bitmap *   @src : source bitmap *   @shift : shift by this many bits *   @bits : bitmap size, in bits * * Shifting right (dividing) means moving bits in the MS -> LS bit * direction.  Zeros are fed into the vacated MS positions and the * LS bits shifted off the bottom are lost. */void __bitmap_shift_right(unsigned long *dst,			const unsigned long *src, int shift, int bits){	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;	unsigned long mask = (1UL << left) - 1;	for (k = 0; off + k < lim; ++k) {		unsigned long upper, lower; 		/*		 * If shift is not word aligned, take lower rem bits of		 * word above and make them the top rem bits of result.		 */		if (!rem || off + k + 1 >= lim)			upper = 0;		else {			upper = src[off + k + 1];			if (off + k + 1 == lim - 1 && left)				upper &= mask;		}		lower = src[off + k];		if (left && off + k == lim - 1)			lower &= mask;		dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;		if (left && k == lim - 1)			dst[k] &= mask;	}	if (off)		memset(&dst[lim - off], 0, off*sizeof(unsigned long));}EXPORT_SYMBOL(__bitmap_shift_right);  /** * __bitmap_shift_left - logical left shift of the bits in a bitmap *   @dst : destination bitmap *   @src : source bitmap *   @shift : shift by this many bits *   @bits : bitmap size, in bits * * Shifting left (multiplying) means moving bits in the LS -> MS * direction.  Zeros are fed into the vacated LS bit positions * and those MS bits shifted off the top are lost. */ void __bitmap_shift_left(unsigned long *dst,			const unsigned long *src, int shift, int bits){	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;	for (k = lim - off - 1; k >= 0; --k) {		unsigned long upper, lower; 		/*		 * If shift is not word aligned, take upper rem bits of		 * word below and make them the bottom rem bits of result.		 */		if (rem && k > 0)			lower = src[k - 1];		else			lower = 0;		upper = src[k];		if (left && k == lim - 1)			upper &= (1UL << left) - 1;		dst[k + off] = lower  >> (BITS_PER_LONG - rem) | upper << rem;		if (left && k + off == lim - 1)			dst[k + off] &= (1UL << left) - 1;	}	if (off)		memset(dst, 0, off*sizeof(unsigned long));}EXPORT_SYMBOL(__bitmap_shift_left); int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k;	int nr = BITS_TO_LONGS(bits);	unsigned long result = 0; 	for (k = 0; k < nr; k++)		result |= (dst[k] = bitmap1[k] & bitmap2[k]);	return result != 0;}EXPORT_SYMBOL(__bitmap_and); void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k;	int nr = BITS_TO_LONGS(bits); 	for (k = 0; k < nr; k++)		dst[k] = bitmap1[k] | bitmap2[k];}EXPORT_SYMBOL(__bitmap_or); void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k;	int nr = BITS_TO_LONGS(bits); 	for (k = 0; k < nr; k++)		dst[k] = bitmap1[k] ^ bitmap2[k];}EXPORT_SYMBOL(__bitmap_xor); int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k;	int nr = BITS_TO_LONGS(bits);	unsigned long result = 0; 	for (k = 0; k < nr; k++)		result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);	return result != 0;}EXPORT_SYMBOL(__bitmap_andnot); int __bitmap_intersects(const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		if (bitmap1[k] & bitmap2[k])			return 1; 	if (bits % BITS_PER_LONG)		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))			return 1;	return 0;}EXPORT_SYMBOL(__bitmap_intersects); int __bitmap_subset(const unsigned long *bitmap1,				const unsigned long *bitmap2, int bits){	int k, lim = bits/BITS_PER_LONG;	for (k = 0; k < lim; ++k)		if (bitmap1[k] & ~bitmap2[k])			return 0; 	if (bits % BITS_PER_LONG)		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))			return 0;	return 1;}EXPORT_SYMBOL(__bitmap_subset); int __bitmap_weight(const unsigned long *bitmap, int bits){	int k, w = 0, lim = bits/BITS_PER_LONG; 	for (k = 0; k < lim; k++)		w += hweight_long(bitmap[k]); 	if (bits % BITS_PER_LONG)		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); 	return w;}EXPORT_SYMBOL(__bitmap_weight); #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) void bitmap_set(unsigned long *map, int start, int nr){	unsigned long *p = map + BIT_WORD(start);	const int size = start + nr;	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 	while (nr - bits_to_set >= 0) {		*p |= mask_to_set;		nr -= bits_to_set;		bits_to_set = BITS_PER_LONG;		mask_to_set = ~0UL;		p++;	}	if (nr) {		mask_to_set &= BITMAP_LAST_WORD_MASK(size);		*p |= mask_to_set;	}}EXPORT_SYMBOL(bitmap_set); void bitmap_clear(unsigned long *map, int start, int nr){	unsigned long *p = map + BIT_WORD(start);	const int size = start + nr;	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 	while (nr - bits_to_clear >= 0) {		*p &= ~mask_to_clear;		nr -= bits_to_clear;		bits_to_clear = BITS_PER_LONG;		mask_to_clear = ~0UL;		p++;	}	if (nr) {		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);		*p &= ~mask_to_clear;	}}EXPORT_SYMBOL(bitmap_clear); /* * 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. */unsigned long bitmap_find_next_zero_area(unsigned long *map,					 unsigned long size,					 unsigned long start,					 unsigned int nr,					 unsigned long align_mask){	unsigned long index, end, i;again:	index = find_next_zero_bit(map, size, start); 	/* Align allocation */	index = __ALIGN_MASK(index, align_mask); 	end = index + nr;	if (end > size)		return end;	i = find_next_bit(map, end, index);	if (i < end) {		start = i + 1;		goto again;	}	return index;}EXPORT_SYMBOL(bitmap_find_next_zero_area); /* * Bitmap printing & parsing functions: first version by Bill Irwin, * second version by Paul Jackson, third by Joe Korty. */ #define CHUNKSZ				32#define nbits_to_hold_value(val)	fls(val)#define unhex(c)			(isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))#define BASEDEC 10		/* fancier cpuset lists input in decimal */ /** * bitmap_scnprintf - convert bitmap to an ASCII hex string. * @buf: byte buffer into which string is placed * @buflen: reserved size of @buf, in bytes * @maskp: pointer to bitmap to convert * @nmaskbits: size of bitmap, in bits * * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into * comma-separated sets of eight digits per set. */int bitmap_scnprintf(char *buf, unsigned int buflen,	const unsigned long *maskp, int nmaskbits){	int i, word, bit, len = 0;	unsigned long val;	const char *sep = "";	int chunksz;	u32 chunkmask; 	chunksz = nmaskbits & (CHUNKSZ - 1);	if (chunksz == 0)		chunksz = CHUNKSZ; 	i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;	for (; i >= 0; i -= CHUNKSZ) {		chunkmask = ((1ULL << chunksz) - 1);		word = i / BITS_PER_LONG;		bit = i % BITS_PER_LONG;		val = (maskp[word] >> bit) & chunkmask;		len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,			(chunksz+3)/4, val);		chunksz = CHUNKSZ;		sep = ",";	}	return len;}EXPORT_SYMBOL(bitmap_scnprintf); /** * __bitmap_parse - convert an ASCII hex string into a bitmap. * @buf: pointer to buffer containing string. * @buflen: buffer size in bytes.  If string is smaller than this *    then it must be terminated with a \0. * @is_user: location of buffer, 0 indicates kernel space * @maskp: pointer to bitmap array that will contain result. * @nmaskbits: size of bitmap, in bits. * * Commas group hex digits into chunks.  Each chunk defines exactly 32 * bits of the resultant bitmask.  No chunk may specify a value larger * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value * then leading 0-bits are prepended.  %-EINVAL is returned for illegal * characters and for grouping errors such as "1,,5", ",44", "," and "". * Leading and trailing whitespace accepted, but not embedded whitespace. */int __bitmap_parse(const char *buf, unsigned int buflen,		int is_user, unsigned long *maskp,		int nmaskbits){	int c, old_c, totaldigits, ndigits, nchunks, nbits;	u32 chunk;	const char __user *ubuf = buf; 	bitmap_zero(maskp, nmaskbits); 	nchunks = nbits = totaldigits = c = 0;	do {		chunk = ndigits = 0; 		/* Get the next chunk of the bitmap */		while (buflen) {			old_c = c;			if (is_user) {				if (__get_user(c, ubuf++))					return -EFAULT;			}			else				c = *buf++;			buflen--;			if (isspace(c))				continue; 			/*			 * If the last character was a space and the current			 * character isn't '\0', we've got embedded whitespace.			 * This is a no-no, so throw an error.			 */			if (totaldigits && c && isspace(old_c))				return -EINVAL; 			/* A '\0' or a ',' signal the end of the chunk */			if (c == '\0' || c == ',')				break; 			if (!isxdigit(c))				return -EINVAL; 			/*			 * Make sure there are at least 4 free bits in 'chunk'.			 * If not, this hexdigit will overflow 'chunk', so			 * throw an error.			 */			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))				return -EOVERFLOW; 			chunk = (chunk << 4) | unhex(c);			ndigits++; totaldigits++;		}		if (ndigits == 0)			return -EINVAL;		if (nchunks == 0 && chunk == 0)			continue; 		__bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);		*maskp |= chunk;		nchunks++;		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;		if (nbits > nmaskbits)			return -EOVERFLOW;	} while (buflen && c == ','); 	return 0;}EXPORT_SYMBOL(__bitmap_parse); /** * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap * * @ubuf: pointer to user buffer containing string. * @ulen: buffer size in bytes.  If string is smaller than this *    then it must be terminated with a \0. * @maskp: pointer to bitmap array that will contain result. * @nmaskbits: size of bitmap, in bits. * * Wrapper for __bitmap_parse(), providing it with user buffer. * * We cannot have this as an inline function in bitmap.h because it needs

Lines 1–500 of 1100. Load more