/* * 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/export.h>#include <linux/thread_info.h>#include <linux/ctype.h>#include <linux/errno.h>#include <linux/bitmap.h>#include <linux/bitops.h>#include <linux/bug.h>#include <linux/kernel.h>#include <linux/string.h>#include <linux/uaccess.h> #include <asm/page.h> /** * DOC: bitmap introduction * * 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_equal(const unsigned long *bitmap1,		const unsigned long *bitmap2, unsigned int bits){	unsigned 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, unsigned int bits){	unsigned int k, lim = BITS_TO_LONGS(bits);	for (k = 0; k < lim; ++k)		dst[k] = ~src[k];}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 *   @nbits : 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,			unsigned shift, unsigned nbits){	unsigned k, lim = BITS_TO_LONGS(nbits);	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);	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)				upper &= mask;			upper <<= (BITS_PER_LONG - rem);		}		lower = src[off + k];		if (off + k == lim - 1)			lower &= mask;		lower >>= rem;		dst[k] = lower | upper;	}	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 *   @nbits : 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,			unsigned int shift, unsigned int nbits){	int k;	unsigned int lim = BITS_TO_LONGS(nbits);	unsigned 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] >> (BITS_PER_LONG - rem);		else			lower = 0;		upper = src[k] << rem;		dst[k + off] = lower | upper;	}	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, unsigned int bits){	unsigned int k;	unsigned int lim = bits/BITS_PER_LONG;	unsigned long result = 0; 	for (k = 0; k < lim; k++)		result |= (dst[k] = bitmap1[k] & bitmap2[k]);	if (bits % BITS_PER_LONG)		result |= (dst[k] = bitmap1[k] & bitmap2[k] &			   BITMAP_LAST_WORD_MASK(bits));	return result != 0;}EXPORT_SYMBOL(__bitmap_and); void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,				const unsigned long *bitmap2, unsigned int bits){	unsigned int k;	unsigned 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, unsigned int bits){	unsigned int k;	unsigned 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, unsigned int bits){	unsigned int k;	unsigned int lim = bits/BITS_PER_LONG;	unsigned long result = 0; 	for (k = 0; k < lim; k++)		result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);	if (bits % BITS_PER_LONG)		result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &			   BITMAP_LAST_WORD_MASK(bits));	return result != 0;}EXPORT_SYMBOL(__bitmap_andnot); int __bitmap_intersects(const unsigned long *bitmap1,			const unsigned long *bitmap2, unsigned int bits){	unsigned 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, unsigned int bits){	unsigned 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, unsigned int bits){	unsigned int k, lim = bits/BITS_PER_LONG;	int w = 0; 	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); void __bitmap_set(unsigned long *map, unsigned int start, int len){	unsigned long *p = map + BIT_WORD(start);	const unsigned int size = start + len;	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 	while (len - bits_to_set >= 0) {		*p |= mask_to_set;		len -= bits_to_set;		bits_to_set = BITS_PER_LONG;		mask_to_set = ~0UL;		p++;	}	if (len) {		mask_to_set &= BITMAP_LAST_WORD_MASK(size);		*p |= mask_to_set;	}}EXPORT_SYMBOL(__bitmap_set); void __bitmap_clear(unsigned long *map, unsigned int start, int len){	unsigned long *p = map + BIT_WORD(start);	const unsigned int size = start + len;	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 	while (len - bits_to_clear >= 0) {		*p &= ~mask_to_clear;		len -= bits_to_clear;		bits_to_clear = BITS_PER_LONG;		mask_to_clear = ~0UL;		p++;	}	if (len) {		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);		*p &= ~mask_to_clear;	}}EXPORT_SYMBOL(__bitmap_clear); /** * bitmap_find_next_zero_area_off - 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 * @align_offset: Alignment offset 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 plus @align_offset * is multiple of that power of 2. */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){	unsigned long index, end, i;again:	index = find_next_zero_bit(map, size, start); 	/* Align allocation */	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset; 	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_off); /* * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers, * second version by Paul Jackson, third by Joe Korty. */ #define CHUNKSZ				32#define nbits_to_hold_value(val)	fls(val)#define BASEDEC 10		/* fancier cpuset lists input in decimal */ /** * __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 __force *ubuf = (const char __user __force *)buf; 	bitmap_zero(maskp, nmaskbits); 	nchunks = nbits = totaldigits = c = 0;	do {		chunk = 0;		ndigits = totaldigits; 		/* 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) | hex_to_bin(c);			totaldigits++;		}		if (ndigits == totaldigits)			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 * linux/uaccess.h to get the access_ok() declaration and this causes * cyclic dependencies. */int bitmap_parse_user(const char __user *ubuf,			unsigned int ulen, unsigned long *maskp,			int nmaskbits){	if (!access_ok(VERIFY_READ, ubuf, ulen))		return -EFAULT;	return __bitmap_parse((const char __force *)ubuf,				ulen, 1, maskp, nmaskbits); }EXPORT_SYMBOL(bitmap_parse_user); /** * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string * @list: indicates whether the bitmap must be list * @buf: page aligned buffer into which string is placed * @maskp: pointer to bitmap to convert * @nmaskbits: size of bitmap, in bits * * Output format is a comma-separated list of decimal numbers and * ranges if list is specified or hex digits grouped into comma-separated * sets of 8 digits/set. Returns the number of characters written to buf. * * It is assumed that @buf is a pointer into a PAGE_SIZE area and that * sufficient storage remains at @buf to accommodate the * bitmap_print_to_pagebuf() output. */int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,			    int nmaskbits){	ptrdiff_t len = PTR_ALIGN(buf + PAGE_SIZE - 1, PAGE_SIZE) - buf;	int n = 0; 	if (len > 1)		n = list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :			   scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);	return n;}EXPORT_SYMBOL(bitmap_print_to_pagebuf); /** * __bitmap_parselist - convert list format ASCII string to bitmap * @buf: read nul-terminated user string from this buffer * @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: write resulting mask here * @nmaskbits: number of bits in mask to be written * * Input format is a comma-separated list of decimal numbers and * ranges.  Consecutively set bits are shown as two hyphen-separated * decimal numbers, the smallest and largest bit numbers set in * the range. * Optionally each range can be postfixed to denote that only parts of it * should be set. The range will divided to groups of specific size. * From each group will be used only defined amount of bits.

Lines 1–500 of 1182. Load more