lkml.org 
[lkml]   [2004]   [Jan]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH] bitmap parsing routines, version 3
Andrew, Paul, Matthew,
This bitmask parsing/printing patch addresses all concerns except code
size, that I am aware of.

The most significant change is the replacement of the rather complex
firstchunk, chunkmask system of detecting if the value fits into
nmaskbits, with one that directly measures the #bits in the value as
accumulated so far and compares that with nmaskbits. This resulted
in a significant slimming-down of bitmap_parse, though not to the point
of approaching Paul's original version in simplicity.

Applies against 2.6.1-mm4.

Regards,
Joe

Changelog:
o forbid embedded whitespace, allow leading whitespace (Paul Jackson)
o trailing whitespace stops parsing, like \0 does.
o chunk size now 32 bits (Matthew Dobson)
o cleaner, smaller fit-into-nbits error checking code.
o bugfix, j < 32 should be j < CHUNKSZ (Paul Jackson)
o fix sometimes consumption of bytes between \0 and eobuf



diff -Nura base/include/linux/bitmap.h new/include/linux/bitmap.h
--- base/include/linux/bitmap.h 2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/bitmap.h 2004-01-17 00:13:50.000000000 -0500
@@ -42,6 +42,12 @@
const unsigned long *bitmap2, int bits);
int bitmap_weight(const unsigned long *bitmap, int bits);

+extern int bitmap_snprintf(char *buf, unsigned int buflen,
+ const unsigned long *maskp, int bits);
+
+extern int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+ unsigned long *maskp, int bits);
+
#endif /* __ASSEMBLY__ */

#endif /* __LINUX_BITMAP_H */
diff -Nura base/include/linux/cpumask.h new/include/linux/cpumask.h
--- base/include/linux/cpumask.h 2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/cpumask.h 2004-01-17 00:13:50.000000000 -0500
@@ -2,6 +2,7 @@
#define __LINUX_CPUMASK_H

#include <linux/threads.h>
+#include <linux/bitmap.h>
#include <asm/cpumask.h>
#include <asm/bug.h>

@@ -31,16 +32,10 @@
#define for_each_online_cpu(cpu) for (cpu = 0; cpu < 1; cpu++)
#endif

-extern int __mask_snprintf_len(char *buf, unsigned int buflen,
- const unsigned long *maskp, unsigned int maskbytes);
-
#define cpumask_snprintf(buf, buflen, map) \
- __mask_snprintf_len(buf, buflen, cpus_addr(map), sizeof(map))
-
-extern int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
- unsigned long *maskp, unsigned int maskbytes);
+ bitmap_snprintf(buf, buflen, cpus_addr(map), NR_CPUS)

#define cpumask_parse(buf, buflen, map) \
- __mask_parse_len(buf, buflen, cpus_addr(map), sizeof(map))
+ bitmap_parse(buf, buflen, cpus_addr(map), NR_CPUS)

#endif /* __LINUX_CPUMASK_H */
diff -Nura base/lib/Makefile new/lib/Makefile
--- base/lib/Makefile 2004-01-17 00:10:11.000000000 -0500
+++ new/lib/Makefile 2004-01-17 00:13:50.000000000 -0500
@@ -5,7 +5,7 @@

lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
- kobject.o idr.o div64.o parser.o int_sqrt.o mask.o \
+ kobject.o idr.o div64.o parser.o int_sqrt.o \
bitmap.o

lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
diff -Nura base/lib/bitmap.c new/lib/bitmap.c
--- base/lib/bitmap.c 2004-01-17 00:10:11.000000000 -0500
+++ new/lib/bitmap.c 2004-01-17 00:34:02.000000000 -0500
@@ -1,5 +1,16 @@
-#include <linux/bitmap.h>
+/*
+ * 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 <asm/bitops.h>
+#include <asm/uaccess.h>

int bitmap_empty(const unsigned long *bitmap, int bits)
{
@@ -138,3 +149,115 @@
#endif
EXPORT_SYMBOL(bitmap_weight);

+/*
+ * Bitmap printing & parsing functions: first version by Bill Irwin,
+ * second version by Paul Jackson, third by Joe Korty.
+ */
+
+#define CHUNKSZ 32
+#define bits_to_hold_value(val) fls(val)
+#define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
+#define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
+
+/**
+ * bitmap_snprintf - convert bitmap to a 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_snprintf(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 = roundup_power2(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 += snprintf(buf+len, buflen-len, "%s%0*lx", sep,
+ (chunksz+3)/4, val);
+ chunksz = CHUNKSZ;
+ sep = ",";
+ }
+ return len;
+}
+EXPORT_SYMBOL(bitmap_snprintf);
+
+/**
+ * bitmap_parse - convert a hex string into a bitmap.
+ * @buf: pointer to buffer in user space containing string.
+ * @buflen: buffer size in bytes. If string is smaller than this
+ * then it must be terminated with a \0 or whitespace.
+ * @maskp: pointer to bitmap 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 appended. Leading spaces accepted. -EINVAL
+ * is returned for illegal characters and grouping errors such as "1,,5",
+ " ,44", "," and "".
+ */
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+ unsigned long *maskp, int nmaskbits)
+{
+ int i, j, c, n, nt, nb;
+ u32 chunk;
+
+ bitmap_clear(maskp, nmaskbits);
+
+ i = nt = nb = 0;
+ do {
+ chunk = c = n = 0;
+ while (ubuflen) {
+ if (get_user(c, ubuf++))
+ return -EFAULT;
+ ubuflen--;
+ if (!c || c == ',')
+ break;
+ if (isspace(c)) {
+ if (nt == 0)
+ continue;
+ c = '\0';
+ break;
+ }
+ if (!isxdigit(c))
+ return -EINVAL;
+ if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+ return -EOVERFLOW;
+ chunk = (chunk << 4) | unhex(c);
+ n++; nt++;
+ }
+ if (n == 0)
+ break;
+ if (i > 0 || chunk) {
+ bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+ for (j = 0; j < CHUNKSZ; j++)
+ if (chunk & (1 << j))
+ set_bit(j, maskp);
+ i++;
+ nb += (i == 1) ? bits_to_hold_value(chunk) : CHUNKSZ;
+ if (nb > nmaskbits)
+ return -EOVERFLOW;
+ }
+ } while (ubuflen && c == ',');
+
+ if (nt == 0 || c == ',')
+ return -EINVAL;
+ return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);
diff -Nura base/lib/mask.c new/lib/mask.c
--- base/lib/mask.c 2004-01-09 01:59:34.000000000 -0500
+++ new/lib/mask.c 1969-12-31 19:00:00.000000000 -0500
@@ -1,178 +0,0 @@
-/*
- * lib/mask.c
- *
- * This file is subject to the terms and conditions of the GNU General Public
- * License. See the file "COPYING" in the main directory of this archive
- * for more details.
- *
- * Copyright (C) 2003 Silicon Graphics, Inc. All Rights Reserved.
- */
-
-/*
- * Routines to manipulate multi-word bit masks, such as cpumasks.
- *
- * The ascii representation of multi-word bit masks displays each
- * 32bit word in hex (not zero filled), and for masks longer than
- * one word, uses a comma separator between words. Words are
- * displayed in big-endian order most significant first. And hex
- * digits within a word are also in big-endian order, of course.
- *
- * Examples:
- * A mask with just bit 0 set displays as "1".
- * A mask with just bit 127 set displays as "80000000,0,0,0".
- * A mask with just bit 64 set displays as "1,0,0".
- * A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
- * as "1,1,10117". The first "1" is for bit 64, the second
- * for bit 32, the third for bit 16, and so forth, to the
- * "7", which is for bits 2, 1 and 0.
- * A mask with bits 32 through 39 set displays as "ff,0".
- *
- * The internal binary representation of masks is as one or
- * an array of unsigned longs, perhaps wrapped in a struct for
- * convenient use as an lvalue. The following code doesn't know
- * about any such struct details, relying on inline macros in
- * files such as cpumask.h to pass in an unsigned long pointer
- * and a length (in bytes), describing the mask contents.
- * The 32bit words in the array are in little-endian order,
- * low order word first. Beware that this is the reverse order
- * of the ascii representation.
- *
- * Even though the size of the input mask is provided in bytes,
- * the following code may assume that the mask is a multiple of
- * 32 or 64 bit words long, and ignore any fractional portion
- * of a word at the end. The main reason the size is passed in
- * bytes is because it is so easy to write 'sizeof(somemask_t)'
- * in the macros.
- *
- * Masks are not a single,simple type, like classic 'C'
- * nul-term strings. Rather they are a family of types, one
- * for each different length. Inline macros are used to pick
- * up the actual length, where it is known to the compiler, and
- * pass it down to these routines, which work on any specified
- * length array of unsigned longs. Poor man's templates.
- *
- * Many of the inline macros don't call into the following
- * routines. Some of them call into other kernel routines,
- * such as memset(), set_bit() or ffs(). Some of them can
- * accomplish their task right inline, such as returning the
- * size or address of the unsigned long array, or optimized
- * versions of the macros for the most common case of an array
- * of a single unsigned long.
- */
-
-#include <linux/kernel.h>
-#include <linux/string.h>
-#include <linux/ctype.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-#include <linux/gfp.h>
-#include <asm/uaccess.h>
-
-#define MAX_HEX_PER_BYTE 4 /* dont need > 4 hex chars to encode byte */
-#define BASE 16 /* masks are input in hex (base 16) */
-#define NUL ((char)'\0') /* nul-terminator */
-
-/**
- * __mask_snprintf_len - represent multi-word bit mask as string.
- * @buf: The buffer to place the result into
- * @buflen: The size of the buffer, including the trailing null space
- * @maskp: Points to beginning of multi-word bit mask.
- * @maskbytes: Number of bytes in bit mask at maskp.
- *
- * This routine is expected to be called from a macro such as:
- *
- * #define cpumask_snprintf(buf, buflen, mask) \
- * __mask_snprintf_len(buf, buflen, cpus_addr(mask), sizeof(mask))
- */
-
-int __mask_snprintf_len(char *buf, unsigned int buflen,
- const unsigned long *maskp, unsigned int maskbytes)
-{
- u32 *wordp = (u32 *)maskp;
- int i = maskbytes/sizeof(u32) - 1;
- int len = 0;
- char *sep = "";
-
- while (i >= 1 && wordp[i] == 0)
- i--;
- while (i >= 0) {
- len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
- sep = ",";
- i--;
- }
- return len;
-}
-
-/**
- * __mask_parse_len - parse user string into maskbytes mask at maskp
- * @ubuf: The user buffer from which to take the string
- * @ubuflen: The size of this buffer, including the terminating char
- * @maskp: Place resulting mask (array of unsigned longs) here
- * @masklen: Construct mask at @maskp to have exactly @masklen bytes
- *
- * @masklen is a multiple of sizeof(unsigned long). A mask of
- * @masklen bytes is constructed starting at location @maskp.
- * The value of this mask is specified by the user provided
- * string starting at address @ubuf. Only bytes in the range
- * [@ubuf, @ubuf+@ubuflen) can be read from user space, and
- * reading will stop after the first byte that is not a comma
- * or valid hex digit in the characters [,0-9a-fA-F], or at
- * the point @ubuf+@ubuflen, whichever comes first.
- *
- * Since the user only needs about 2.25 chars per byte to encode
- * a mask (one char per nibble plus one comma separator or nul
- * terminator per byte), we blow them off with -EINVAL if they
- * claim a @ubuflen more than 4 (MAX_HEX_PER_BYTE) times maskbytes.
- * An empty word (delimited by two consecutive commas, for example)
- * is taken as zero. If @buflen is zero, the entire @maskp is set
- * to zero.
- *
- * If the user provides fewer comma-separated ascii words
- * than there are 32 bit words in maskbytes, we zero fill the
- * remaining high order words. If they provide more, they fail
- * with -EINVAL. Each comma-separate ascii word is taken as
- * a hex representation; leading zeros are ignored, and do not
- * imply octal. '00e1', 'e1', '00E1', 'E1' are all the same.
- * If user passes a word that is larger than fits in a u32,
- * they fail with -EOVERFLOW.
- */
-
-int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
- unsigned long *maskp, unsigned int maskbytes)
-{
- char buf[maskbytes * MAX_HEX_PER_BYTE + sizeof(NUL)];
- char *bp = buf;
- u32 *wordp = (u32 *)maskp;
- char *p;
- int i, j;
-
- if (ubuflen > maskbytes * MAX_HEX_PER_BYTE)
- return -EINVAL;
- if (copy_from_user(buf, ubuf, ubuflen))
- return -EFAULT;
- buf[ubuflen] = NUL;
-
- /*
- * Put the words into wordp[] in big-endian order,
- * then go back and reverse them.
- */
- memset(wordp, 0, maskbytes);
- i = j = 0;
- while ((p = strsep(&bp, ",")) != NULL) {
- unsigned long long t;
- if (j == maskbytes/sizeof(u32))
- return -EINVAL;
- t = simple_strtoull(p, 0, BASE);
- if (t != (u32)t)
- return -EOVERFLOW;
- wordp[j++] = t;
- }
- --j;
- while (i < j) {
- u32 t = wordp[i];
- wordp[i] = wordp[j];
- wordp[j] = t;
- i++, --j;
- }
- return 0;
-}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
\
 
 \ /
  Last update: 2005-03-22 14:00    [W:0.257 / U:0.044 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site