summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /lib
Linux-2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig61
-rw-r--r--lib/Kconfig.debug159
-rw-r--r--lib/Makefile45
-rw-r--r--lib/bitmap.c595
-rw-r--r--lib/bust_spinlocks.c39
-rw-r--r--lib/cmdline.c120
-rw-r--r--lib/crc-ccitt.c69
-rw-r--r--lib/crc32.c529
-rw-r--r--lib/crc32defs.h32
-rw-r--r--lib/ctype.c36
-rw-r--r--lib/dec_and_lock.c40
-rw-r--r--lib/div64.c61
-rw-r--r--lib/dump_stack.c15
-rw-r--r--lib/errno.c7
-rw-r--r--lib/extable.c79
-rw-r--r--lib/find_next_bit.c55
-rw-r--r--lib/gen_crc32table.c82
-rw-r--r--lib/halfmd4.c66
-rw-r--r--lib/idr.c408
-rw-r--r--lib/inflate.c1210
-rw-r--r--lib/int_sqrt.c32
-rw-r--r--lib/iomap.c212
-rw-r--r--lib/kernel_lock.c264
-rw-r--r--lib/kobject.c544
-rw-r--r--lib/kobject_uevent.c369
-rw-r--r--lib/kref.c64
-rw-r--r--lib/libcrc32c.c200
-rw-r--r--lib/parser.c220
-rw-r--r--lib/prio_tree.c484
-rw-r--r--lib/radix-tree.c807
-rw-r--r--lib/rbtree.c394
-rw-r--r--lib/reed_solomon/Makefile6
-rw-r--r--lib/reed_solomon/decode_rs.c272
-rw-r--r--lib/reed_solomon/encode_rs.c54
-rw-r--r--lib/reed_solomon/reed_solomon.c335
-rw-r--r--lib/rwsem-spinlock.c344
-rw-r--r--lib/rwsem.c268
-rw-r--r--lib/sha1.c96
-rw-r--r--lib/sort.c119
-rw-r--r--lib/string.c601
-rw-r--r--lib/vsprintf.c846
-rw-r--r--lib/zlib_deflate/Makefile11
-rw-r--r--lib/zlib_deflate/deflate.c1268
-rw-r--r--lib/zlib_deflate/deflate_syms.c21
-rw-r--r--lib/zlib_deflate/deftree.c1113
-rw-r--r--lib/zlib_deflate/defutil.h334
-rw-r--r--lib/zlib_inflate/Makefile19
-rw-r--r--lib/zlib_inflate/infblock.c361
-rw-r--r--lib/zlib_inflate/infblock.h44
-rw-r--r--lib/zlib_inflate/infcodes.c202
-rw-r--r--lib/zlib_inflate/infcodes.h33
-rw-r--r--lib/zlib_inflate/inffast.c176
-rw-r--r--lib/zlib_inflate/inffast.h17
-rw-r--r--lib/zlib_inflate/inflate.c248
-rw-r--r--lib/zlib_inflate/inflate_syms.c22
-rw-r--r--lib/zlib_inflate/inflate_sync.c148
-rw-r--r--lib/zlib_inflate/inftrees.c412
-rw-r--r--lib/zlib_inflate/inftrees.h64
-rw-r--r--lib/zlib_inflate/infutil.c88
-rw-r--r--lib/zlib_inflate/infutil.h197
60 files changed, 15017 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
new file mode 100644
index 000000000000..eeb45225248f
--- /dev/null
+++ b/lib/Kconfig
@@ -0,0 +1,61 @@
+#
+# Library configuration
+#
+
+menu "Library routines"
+
+config CRC_CCITT
+ tristate "CRC-CCITT functions"
+ help
+ This option is provided for the case where no in-kernel-tree
+ modules require CRC-CCITT functions, but a module built outside
+ the kernel tree does. Such modules that use library CRC-CCITT
+ functions require M here.
+
+config CRC32
+ tristate "CRC32 functions"
+ default y
+ help
+ This option is provided for the case where no in-kernel-tree
+ modules require CRC32 functions, but a module built outside the
+ kernel tree does. Such modules that use library CRC32 functions
+ require M here.
+
+config LIBCRC32C
+ tristate "CRC32c (Castagnoli, et al) Cyclic Redundancy-Check"
+ help
+ This option is provided for the case where no in-kernel-tree
+ modules require CRC32c functions, but a module built outside the
+ kernel tree does. Such modules that use library CRC32c functions
+ require M here. See Castagnoli93.
+ Module will be libcrc32c.
+
+#
+# compression support is select'ed if needed
+#
+config ZLIB_INFLATE
+ tristate
+
+config ZLIB_DEFLATE
+ tristate
+
+#
+# reed solomon support is select'ed if needed
+#
+config REED_SOLOMON
+ tristate
+
+config REED_SOLOMON_ENC8
+ boolean
+
+config REED_SOLOMON_DEC8
+ boolean
+
+config REED_SOLOMON_ENC16
+ boolean
+
+config REED_SOLOMON_DEC16
+ boolean
+
+endmenu
+
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
new file mode 100644
index 000000000000..426a0cf7b11c
--- /dev/null
+++ b/lib/Kconfig.debug
@@ -0,0 +1,159 @@
+
+config PRINTK_TIME
+ bool "Show timing information on printks"
+ help
+ Selecting this option causes timing information to be
+ included in printk output. This allows you to measure
+ the interval between kernel operations, including bootup
+ operations. This is useful for identifying long delays
+ in kernel startup.
+
+
+config DEBUG_KERNEL
+ bool "Kernel debugging"
+ help
+ Say Y here if you are developing drivers or trying to debug and
+ identify kernel problems.
+
+config MAGIC_SYSRQ
+ bool "Magic SysRq key"
+ depends on DEBUG_KERNEL && !UML
+ help
+ If you say Y here, you will have some control over the system even
+ if the system crashes for example during kernel debugging (e.g., you
+ will be able to flush the buffer cache to disk, reboot the system
+ immediately or dump some status information). This is accomplished
+ by pressing various keys while holding SysRq (Alt+PrintScreen). It
+ also works on a serial console (on PC hardware at least), if you
+ send a BREAK and then within 5 seconds a command keypress. The
+ keys are documented in <file:Documentation/sysrq.txt>. Don't say Y
+ unless you really know what this hack does.
+
+config LOG_BUF_SHIFT
+ int "Kernel log buffer size (16 => 64KB, 17 => 128KB)" if DEBUG_KERNEL
+ range 12 21
+ default 17 if ARCH_S390
+ default 16 if X86_NUMAQ || IA64
+ default 15 if SMP
+ default 14
+ help
+ Select kernel log buffer size as a power of 2.
+ Defaults and Examples:
+ 17 => 128 KB for S/390
+ 16 => 64 KB for x86 NUMAQ or IA-64
+ 15 => 32 KB for SMP
+ 14 => 16 KB for uniprocessor
+ 13 => 8 KB
+ 12 => 4 KB
+
+config SCHEDSTATS
+ bool "Collect scheduler statistics"
+ depends on DEBUG_KERNEL && PROC_FS
+ help
+ If you say Y here, additional code will be inserted into the
+ scheduler and related routines to collect statistics about
+ scheduler behavior and provide them in /proc/schedstat. These
+ stats may be useful for both tuning and debugging the scheduler
+ If you aren't debugging the scheduler or trying to tune a specific
+ application, you can say N to avoid the very slight overhead
+ this adds.
+
+config DEBUG_SLAB
+ bool "Debug memory allocations"
+ depends on DEBUG_KERNEL
+ help
+ Say Y here to have the kernel do limited verification on memory
+ allocation as well as poisoning memory on free to catch use of freed
+ memory. This can make kmalloc/kfree-intensive workloads much slower.
+
+config DEBUG_PREEMPT
+ bool "Debug preemptible kernel"
+ depends on DEBUG_KERNEL && PREEMPT
+ default y
+ help
+ If you say Y here then the kernel will use a debug variant of the
+ commonly used smp_processor_id() function and will print warnings
+ if kernel code uses it in a preemption-unsafe way. Also, the kernel
+ will detect preemption count underflows.
+
+config DEBUG_SPINLOCK
+ bool "Spinlock debugging"
+ depends on DEBUG_KERNEL
+ help
+ Say Y here and build SMP to catch missing spinlock initialization
+ and certain other kinds of spinlock errors commonly made. This is
+ best used in conjunction with the NMI watchdog so that spinlock
+ deadlocks are also debuggable.
+
+config DEBUG_SPINLOCK_SLEEP
+ bool "Sleep-inside-spinlock checking"
+ depends on DEBUG_KERNEL
+ help
+ If you say Y here, various routines which may sleep will become very
+ noisy if they are called with a spinlock held.
+
+config DEBUG_KOBJECT
+ bool "kobject debugging"
+ depends on DEBUG_KERNEL
+ help
+ If you say Y here, some extra kobject debugging messages will be sent
+ to the syslog.
+
+config DEBUG_HIGHMEM
+ bool "Highmem debugging"
+ depends on DEBUG_KERNEL && HIGHMEM
+ help
+ This options enables addition error checking for high memory systems.
+ Disable for production systems.
+
+config DEBUG_BUGVERBOSE
+ bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EMBEDDED
+ depends on ARM || ARM26 || M32R || M68K || SPARC32 || SPARC64 || (X86 && !X86_64) || FRV
+ default !EMBEDDED
+ help
+ Say Y here to make BUG() panics output the file name and line number
+ of the BUG call as well as the EIP and oops trace. This aids
+ debugging but costs about 70-100K of memory.
+
+config DEBUG_INFO
+ bool "Compile the kernel with debug info"
+ depends on DEBUG_KERNEL
+ help
+ If you say Y here the resulting kernel image will include
+ debugging info resulting in a larger kernel image.
+ Say Y here only if you plan to debug the kernel.
+
+ If unsure, say N.
+
+config DEBUG_IOREMAP
+ bool "Enable ioremap() debugging"
+ depends on DEBUG_KERNEL && PARISC
+ help
+ Enabling this option will cause the kernel to distinguish between
+ ioremapped and physical addresses. It will print a backtrace (at
+ most one every 10 seconds), hopefully allowing you to see which
+ drivers need work. Fixing all these problems is a prerequisite
+ for turning on USE_HPPA_IOREMAP. The warnings are harmless;
+ the kernel has enough information to fix the broken drivers
+ automatically, but we'd like to make it more efficient by not
+ having to do that.
+
+config DEBUG_FS
+ bool "Debug Filesystem"
+ depends on DEBUG_KERNEL
+ help
+ debugfs is a virtual file system that kernel developers use to put
+ debugging files into. Enable this option to be able to read and
+ write to these files.
+
+ If unsure, say N.
+
+config FRAME_POINTER
+ bool "Compile the kernel with frame pointers"
+ depends on DEBUG_KERNEL && ((X86 && !X86_64) || CRIS || M68K || M68KNOMMU || FRV)
+ help
+ If you say Y here the resulting kernel image will be slightly larger
+ and slower, but it will give very useful debugging information.
+ If you don't debug the kernel, you can say N, but we may not be able
+ to solve problems without frame pointers.
+
diff --git a/lib/Makefile b/lib/Makefile
new file mode 100644
index 000000000000..7c70db79c0e0
--- /dev/null
+++ b/lib/Makefile
@@ -0,0 +1,45 @@
+#
+# Makefile for some libs needed in the kernel.
+#
+
+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 kref.o idr.o div64.o int_sqrt.o \
+ bitmap.o extable.o kobject_uevent.o prio_tree.o sha1.o \
+ halfmd4.o
+
+obj-y += sort.o parser.o
+
+ifeq ($(CONFIG_DEBUG_KOBJECT),y)
+CFLAGS_kobject.o += -DDEBUG
+CFLAGS_kobject_uevent.o += -DDEBUG
+endif
+
+lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
+lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
+lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
+obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
+
+ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
+ lib-y += dec_and_lock.o
+endif
+
+obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
+obj-$(CONFIG_CRC32) += crc32.o
+obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
+obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
+
+obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
+obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
+obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+
+hostprogs-y := gen_crc32table
+clean-files := crc32table.h
+
+$(obj)/crc32.o: $(obj)/crc32table.h
+
+quiet_cmd_crc32 = GEN $@
+ cmd_crc32 = $< > $@
+
+$(obj)/crc32table.h: $(obj)/gen_crc32table
+ $(call cmd,crc32)
diff --git a/lib/bitmap.c b/lib/bitmap.c
new file mode 100644
index 000000000000..d1388a5ce89c
--- /dev/null
+++ b/lib/bitmap.c
@@ -0,0 +1,595 @@
+/*
+ * 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
+ * @nbits - 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
+ * @nbits - 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);
+
+void __bitmap_and(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_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);
+
+void __bitmap_andnot(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_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);
+
+#if BITS_PER_LONG == 32
+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 += hweight32(bitmap[k]);
+
+ if (bits % BITS_PER_LONG)
+ w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+ return w;
+}
+#else
+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 += hweight64(bitmap[k]);
+
+ if (bits % BITS_PER_LONG)
+ w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+ return w;
+}
+#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 nbits_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))
+#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 = 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 += 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 in user space containing string.
+ * @buflen: 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.
+ *
+ * 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 __user *ubuf, unsigned int ubuflen,
+ unsigned long *maskp, int nmaskbits)
+{
+ int c, old_c, totaldigits, ndigits, nchunks, nbits;
+ u32 chunk;
+
+ bitmap_zero(maskp, nmaskbits);
+
+ nchunks = nbits = totaldigits = c = 0;
+ do {
+ chunk = ndigits = 0;
+
+ /* Get the next chunk of the bitmap */
+ while (ubuflen) {
+ old_c = c;
+ if (get_user(c, ubuf++))
+ return -EFAULT;
+ ubuflen--;
+ 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 |= c