diff options
author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-04-16 15:20:36 -0700 |
---|---|---|
committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-04-16 15:20:36 -0700 |
commit | 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch) | |
tree | 0bba044c4ce775e45a88a51686b5d9f90697ea9d /lib |
Linux-2.6.12-rc2v2.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')
60 files changed, 15017 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig new file mode 100644 index 00000000000..eeb45225248 --- /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 00000000000..426a0cf7b11 --- /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 00000000000..7c70db79c0e --- /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 00000000000..d1388a5ce89 --- /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; + + / |