* 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/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 <asm/uaccess.h>
/*
}
EXPORT_SYMBOL(__bitmap_shift_left);
-void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+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++)
- dst[k] = bitmap1[k] & bitmap2[k];
+ result |= (dst[k] = bitmap1[k] & bitmap2[k]);
+ return result != 0;
}
EXPORT_SYMBOL(__bitmap_and);
}
EXPORT_SYMBOL(__bitmap_xor);
-void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+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++)
- dst[k] = bitmap1[k] & ~bitmap2[k];
+ result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
+ return result != 0;
}
EXPORT_SYMBOL(__bitmap_andnot);
}
EXPORT_SYMBOL(__bitmap_weight);
+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 */
/**
EXPORT_SYMBOL(bitmap_scnprintf);
/**
- * bitmap_scnprintf_len - return buffer length needed to convert
- * bitmap to an ASCII hex string
- * @nr_bits: number of bits to be converted
- */
-int bitmap_scnprintf_len(unsigned int nr_bits)
-{
- unsigned int nr_nibbles = ALIGN(nr_bits, 4) / 4;
- return nr_nibbles + ALIGN(nr_nibbles, CHUNKSZ / 4) / (CHUNKSZ / 4) - 1;
-}
-
-/**
* __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
{
int c, old_c, totaldigits, ndigits, nchunks, nbits;
u32 chunk;
- const char __user *ubuf = buf;
+ const char __user __force *ubuf = (const char __user __force *)buf;
bitmap_zero(maskp, nmaskbits);
if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
return -EOVERFLOW;
- chunk = (chunk << 4) | unhex(c);
+ chunk = (chunk << 4) | hex_to_bin(c);
ndigits++; totaldigits++;
}
if (ndigits == 0)
EXPORT_SYMBOL(__bitmap_parse);
/**
- * bitmap_parse_user()
+ * 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
{
if (!access_ok(VERIFY_READ, ubuf, ulen))
return -EFAULT;
- return __bitmap_parse((const char *)ubuf, ulen, 1, maskp, nmaskbits);
+ return __bitmap_parse((const char __force *)ubuf,
+ ulen, 1, maskp, nmaskbits);
+
}
EXPORT_SYMBOL(bitmap_parse_user);
EXPORT_SYMBOL(bitmap_scnlistprintf);
/**
- * bitmap_parselist - convert list format ASCII string to bitmap
- * @bp: read nul-terminated user string from this buffer
+ * __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
*
* %-EINVAL: invalid character in string
* %-ERANGE: bit number specified too large for mask
*/
-int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
+static int __bitmap_parselist(const char *buf, unsigned int buflen,
+ int is_user, unsigned long *maskp,
+ int nmaskbits)
{
unsigned a, b;
+ int c, old_c, totaldigits;
+ const char __user __force *ubuf = (const char __user __force *)buf;
+ int exp_digit, in_range;
+ totaldigits = c = 0;
bitmap_zero(maskp, nmaskbits);
do {
- if (!isdigit(*bp))
- return -EINVAL;
- b = a = simple_strtoul(bp, (char **)&bp, BASEDEC);
- if (*bp == '-') {
- bp++;
- if (!isdigit(*bp))
+ exp_digit = 1;
+ in_range = 0;
+ a = b = 0;
+
+ /* Get the next cpu# or a range of cpu#'s */
+ 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 a cpu# or range */
+ if (c == '\0' || c == ',')
+ break;
+
+ if (c == '-') {
+ if (exp_digit || in_range)
+ return -EINVAL;
+ b = 0;
+ in_range = 1;
+ exp_digit = 1;
+ continue;
+ }
+
+ if (!isdigit(c))
return -EINVAL;
- b = simple_strtoul(bp, (char **)&bp, BASEDEC);
+
+ b = b * 10 + (c - '0');
+ if (!in_range)
+ a = b;
+ exp_digit = 0;
+ totaldigits++;
}
if (!(a <= b))
return -EINVAL;
set_bit(a, maskp);
a++;
}
- if (*bp == ',')
- bp++;
- } while (*bp != '\0' && *bp != '\n');
+ } while (buflen && c == ',');
return 0;
}
+
+int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
+{
+ char *nl = strchr(bp, '\n');
+ int len;
+
+ if (nl)
+ len = nl - bp;
+ else
+ len = strlen(bp);
+
+ return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
+}
EXPORT_SYMBOL(bitmap_parselist);
+
+/**
+ * bitmap_parselist_user()
+ *
+ * @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_parselist(), 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_parselist_user(const char __user *ubuf,
+ unsigned int ulen, unsigned long *maskp,
+ int nmaskbits)
+{
+ if (!access_ok(VERIFY_READ, ubuf, ulen))
+ return -EFAULT;
+ return __bitmap_parselist((const char __force *)ubuf,
+ ulen, 1, maskp, nmaskbits);
+}
+EXPORT_SYMBOL(bitmap_parselist_user);
+
+
/**
- * bitmap_pos_to_ord(buf, pos, bits)
+ * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
* @buf: pointer to a bitmap
* @pos: a bit position in @buf (0 <= @pos < @bits)
* @bits: number of valid bit positions in @buf
}
/**
- * bitmap_ord_to_pos(buf, ord, bits)
+ * bitmap_ord_to_pos - find position of n-th set bit in bitmap
* @buf: pointer to bitmap
* @ord: ordinal bit position (n-th set bit, n >= 0)
* @bits: number of valid bit positions in @buf
*
* The bit positions 0 through @bits are valid positions in @buf.
*/
-static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
+int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
{
int pos = 0;
bitmap_zero(dst, bits);
w = bitmap_weight(new, bits);
- for (oldbit = find_first_bit(src, bits);
- oldbit < bits;
- oldbit = find_next_bit(src, bits, oldbit + 1)) {
+ for_each_set_bit(oldbit, src, bits) {
int n = bitmap_pos_to_ord(old, oldbit, bits);
+
if (n < 0 || w == 0)
set_bit(oldbit, dst); /* identity map */
else
* @orig (i.e. bits 3, 5, 7 and 9) were also set.
*
* When bit 11 is set in @orig, it means turn on the bit in
- * @dst corresponding to whatever is the twelth bit that is
+ * @dst corresponding to whatever is the twelfth bit that is
* turned on in @relmap. In the above example, there were
* only ten bits turned on in @relmap (30..39), so that bit
* 11 was set in @orig had no affect on @dst.
*/
m = 0;
- for (n = find_first_bit(relmap, bits);
- n < bits;
- n = find_next_bit(relmap, bits, n + 1)) {
+ for_each_set_bit(n, relmap, bits) {
/* m == bitmap_pos_to_ord(relmap, n, bits) */
if (test_bit(m, orig))
set_bit(n, dst);
return;
bitmap_zero(dst, bits);
- for (oldbit = find_first_bit(orig, bits);
- oldbit < bits;
- oldbit = find_next_bit(orig, bits, oldbit + 1))
+ for_each_set_bit(oldbit, orig, bits)
set_bit(oldbit % sz, dst);
}
EXPORT_SYMBOL(bitmap_fold);
*/
int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
- int pos; /* scans bitmap by regions of size order */
+ int pos, end; /* scans bitmap by regions of size order */
- for (pos = 0; pos < bits; pos += (1 << order))
- if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
- break;
- if (pos == bits)
- return -ENOMEM;
- __reg_op(bitmap, pos, order, REG_OP_ALLOC);
- return pos;
+ for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
+ if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+ continue;
+ __reg_op(bitmap, pos, order, REG_OP_ALLOC);
+ return pos;
+ }
+ return -ENOMEM;
}
EXPORT_SYMBOL(bitmap_find_free_region);
return 0;
}
EXPORT_SYMBOL(bitmap_allocate_region);
+
+/**
+ * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
+ * @dst: destination buffer
+ * @src: bitmap to copy
+ * @nbits: number of bits in the bitmap
+ *
+ * Require nbits % BITS_PER_LONG == 0.
+ */
+void bitmap_copy_le(void *dst, const unsigned long *src, int nbits)
+{
+ unsigned long *d = dst;
+ int i;
+
+ for (i = 0; i < nbits/BITS_PER_LONG; i++) {
+ if (BITS_PER_LONG == 64)
+ d[i] = cpu_to_le64(src[i]);
+ else
+ d[i] = cpu_to_le32(src[i]);
+ }
+}
+EXPORT_SYMBOL(bitmap_copy_le);
projects / linux-flexiantxendom0-3.2.10.git / blobdiff