summaryrefslogtreecommitdiff
path: root/lib/bitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/bitmap.c')
-rw-r--r--lib/bitmap.c280
1 files changed, 155 insertions, 125 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 98872e9025da..f235434df87b 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -20,6 +20,8 @@
#include <asm/page.h>
+#include "kstrtox.h"
+
/**
* DOC: bitmap introduction
*
@@ -477,12 +479,128 @@ int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
}
EXPORT_SYMBOL(bitmap_print_to_pagebuf);
+/*
+ * Region 9-38:4/10 describes the following bitmap structure:
+ * 0 9 12 18 38
+ * .........****......****......****......
+ * ^ ^ ^ ^
+ * start off group_len end
+ */
+struct region {
+ unsigned int start;
+ unsigned int off;
+ unsigned int group_len;
+ unsigned int end;
+};
+
+static int bitmap_set_region(const struct region *r,
+ unsigned long *bitmap, int nbits)
+{
+ unsigned int start;
+
+ if (r->end >= nbits)
+ return -ERANGE;
+
+ for (start = r->start; start <= r->end; start += r->group_len)
+ bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
+
+ return 0;
+}
+
+static int bitmap_check_region(const struct region *r)
+{
+ if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
+ return -EINVAL;
+
+ return 0;
+}
+
+static const char *bitmap_getnum(const char *str, unsigned int *num)
+{
+ unsigned long long n;
+ unsigned int len;
+
+ len = _parse_integer(str, 10, &n);
+ if (!len)
+ return ERR_PTR(-EINVAL);
+ if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
+ return ERR_PTR(-EOVERFLOW);
+
+ *num = n;
+ return str + len;
+}
+
+static inline bool end_of_str(char c)
+{
+ return c == '\0' || c == '\n';
+}
+
+static inline bool __end_of_region(char c)
+{
+ return isspace(c) || c == ',';
+}
+
+static inline bool end_of_region(char c)
+{
+ return __end_of_region(c) || end_of_str(c);
+}
+
+/*
+ * The format allows commas and whitespases at the beginning
+ * of the region.
+ */
+static const char *bitmap_find_region(const char *str)
+{
+ while (__end_of_region(*str))
+ str++;
+
+ return end_of_str(*str) ? NULL : str;
+}
+
+static const char *bitmap_parse_region(const char *str, struct region *r)
+{
+ str = bitmap_getnum(str, &r->start);
+ if (IS_ERR(str))
+ return str;
+
+ if (end_of_region(*str))
+ goto no_end;
+
+ if (*str != '-')
+ return ERR_PTR(-EINVAL);
+
+ str = bitmap_getnum(str + 1, &r->end);
+ if (IS_ERR(str))
+ return str;
+
+ if (end_of_region(*str))
+ goto no_pattern;
+
+ if (*str != ':')
+ return ERR_PTR(-EINVAL);
+
+ str = bitmap_getnum(str + 1, &r->off);
+ if (IS_ERR(str))
+ return str;
+
+ if (*str != '/')
+ return ERR_PTR(-EINVAL);
+
+ return bitmap_getnum(str + 1, &r->group_len);
+
+no_end:
+ r->end = r->start;
+no_pattern:
+ r->off = r->end + 1;
+ r->group_len = r->end + 1;
+
+ return end_of_str(*str) ? NULL : str;
+}
+
/**
- * __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
+ * bitmap_parselist - convert list format ASCII string to bitmap
+ * @buf: read user string from this buffer; must be terminated
+ * with a \0 or \n.
* @maskp: write resulting mask here
* @nmaskbits: number of bits in mask to be written
*
@@ -498,127 +616,38 @@ EXPORT_SYMBOL(bitmap_print_to_pagebuf);
*
* Returns: 0 on success, -errno on invalid input strings. Error values:
*
- * - ``-EINVAL``: second number in range smaller than first
+ * - ``-EINVAL``: wrong region format
* - ``-EINVAL``: invalid character in string
* - ``-ERANGE``: bit number specified too large for mask
+ * - ``-EOVERFLOW``: integer overflow in the input parameters
*/
-static int __bitmap_parselist(const char *buf, unsigned int buflen,
- int is_user, unsigned long *maskp,
- int nmaskbits)
+int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
{
- unsigned int a, b, old_a, old_b;
- unsigned int group_size, used_size, off;
- int c, old_c, totaldigits, ndigits;
- const char __user __force *ubuf = (const char __user __force *)buf;
- int at_start, in_range, in_partial_range;
+ struct region r;
+ long ret;
- totaldigits = c = 0;
- old_a = old_b = 0;
- group_size = used_size = 0;
bitmap_zero(maskp, nmaskbits);
- do {
- at_start = 1;
- in_range = 0;
- in_partial_range = 0;
- a = b = 0;
- ndigits = totaldigits;
-
- /* 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;
-
- /* A '\0' or a ',' signal the end of a cpu# or range */
- if (c == '\0' || c == ',')
- break;
- /*
- * whitespaces between digits are not allowed,
- * but it's ok if whitespaces are on head or tail.
- * when old_c is whilespace,
- * if totaldigits == ndigits, whitespace is on head.
- * if whitespace is on tail, it should not run here.
- * as c was ',' or '\0',
- * the last code line has broken the current loop.
- */
- if ((totaldigits != ndigits) && isspace(old_c))
- return -EINVAL;
- if (c == '/') {
- used_size = a;
- at_start = 1;
- in_range = 0;
- a = b = 0;
- continue;
- }
+ while (buf) {
+ buf = bitmap_find_region(buf);
+ if (buf == NULL)
+ return 0;
- if (c == ':') {
- old_a = a;
- old_b = b;
- at_start = 1;
- in_range = 0;
- in_partial_range = 1;
- a = b = 0;
- continue;
- }
+ buf = bitmap_parse_region(buf, &r);
+ if (IS_ERR(buf))
+ return PTR_ERR(buf);
- if (c == '-') {
- if (at_start || in_range)
- return -EINVAL;
- b = 0;
- in_range = 1;
- at_start = 1;
- continue;
- }
+ ret = bitmap_check_region(&r);
+ if (ret)
+ return ret;
- if (!isdigit(c))
- return -EINVAL;
+ ret = bitmap_set_region(&r, maskp, nmaskbits);
+ if (ret)
+ return ret;
+ }
- b = b * 10 + (c - '0');
- if (!in_range)
- a = b;
- at_start = 0;
- totaldigits++;
- }
- if (ndigits == totaldigits)
- continue;
- if (in_partial_range) {
- group_size = a;
- a = old_a;
- b = old_b;
- old_a = old_b = 0;
- } else {
- used_size = group_size = b - a + 1;
- }
- /* if no digit is after '-', it's wrong*/
- if (at_start && in_range)
- return -EINVAL;
- if (!(a <= b) || group_size == 0 || !(used_size <= group_size))
- return -EINVAL;
- if (b >= nmaskbits)
- return -ERANGE;
- while (a <= b) {
- off = min(b - a + 1, used_size);
- bitmap_set(maskp, a, off);
- a += group_size;
- }
- } while (buflen && c == ',');
return 0;
}
-
-int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
-{
- char *nl = strchrnul(bp, '\n');
- int len = nl - bp;
-
- return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
-}
EXPORT_SYMBOL(bitmap_parselist);
@@ -632,23 +661,27 @@ EXPORT_SYMBOL(bitmap_parselist);
* @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(ubuf, ulen))
- return -EFAULT;
- return __bitmap_parselist((const char __force *)ubuf,
- ulen, 1, maskp, nmaskbits);
+ char *buf;
+ int ret;
+
+ buf = memdup_user_nul(ubuf, ulen);
+ if (IS_ERR(buf))
+ return PTR_ERR(buf);
+
+ ret = bitmap_parselist(buf, maskp, nmaskbits);
+
+ kfree(buf);
+ return ret;
}
EXPORT_SYMBOL(bitmap_parselist_user);
+#ifdef CONFIG_NUMA
/**
* bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
* @buf: pointer to a bitmap
@@ -757,7 +790,6 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
}
}
-EXPORT_SYMBOL(bitmap_remap);
/**
* bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
@@ -795,7 +827,6 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
else
return bitmap_ord_to_pos(new, n % w, bits);
}
-EXPORT_SYMBOL(bitmap_bitremap);
/**
* bitmap_onto - translate one bitmap relative to another
@@ -930,7 +961,6 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
m++;
}
}
-EXPORT_SYMBOL(bitmap_onto);
/**
* bitmap_fold - fold larger bitmap into smaller, modulo specified size
@@ -955,7 +985,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
for_each_set_bit(oldbit, orig, nbits)
set_bit(oldbit % sz, dst);
}
-EXPORT_SYMBOL(bitmap_fold);
+#endif /* CONFIG_NUMA */
/*
* Common code for bitmap_*_region() routines.