diff options
Diffstat (limited to 'lib')
72 files changed, 1511 insertions, 789 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 028aba9e72af..4a8aba2e5cc0 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -29,6 +29,10 @@ config GENERIC_IOMAP bool select GENERIC_PCI_IOMAP +config GENERIC_IO + boolean + default n + config CRC_CCITT tristate "CRC-CCITT functions" help @@ -61,14 +65,71 @@ config CRC_ITU_T functions require M here. config CRC32 - tristate "CRC32 functions" + tristate "CRC32/CRC32c functions" default y select BITREVERSE 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. + modules require CRC32/CRC32c functions, but a module built outside + the kernel tree does. Such modules that use library CRC32/CRC32c + functions require M here. + +config CRC32_SELFTEST + bool "CRC32 perform self test on init" + default n + depends on CRC32 + help + This option enables the CRC32 library functions to perform a + self test on initialization. The self test computes crc32_le + and crc32_be over byte strings with random alignment and length + and computes the total elapsed time and number of bytes processed. + +choice + prompt "CRC32 implementation" + depends on CRC32 + default CRC32_SLICEBY8 + help + This option allows a kernel builder to override the default choice + of CRC32 algorithm. Choose the default ("slice by 8") unless you + know that you need one of the others. + +config CRC32_SLICEBY8 + bool "Slice by 8 bytes" + help + Calculate checksum 8 bytes at a time with a clever slicing algorithm. + This is the fastest algorithm, but comes with a 8KiB lookup table. + Most modern processors have enough cache to hold this table without + thrashing the cache. + + This is the default implementation choice. Choose this one unless + you have a good reason not to. + +config CRC32_SLICEBY4 + bool "Slice by 4 bytes" + help + Calculate checksum 4 bytes at a time with a clever slicing algorithm. + This is a bit slower than slice by 8, but has a smaller 4KiB lookup + table. + + Only choose this option if you know what you are doing. + +config CRC32_SARWATE + bool "Sarwate's Algorithm (one byte at a time)" + help + Calculate checksum a byte at a time using Sarwate's algorithm. This + is not particularly fast, but has a small 256 byte lookup table. + + Only choose this option if you know what you are doing. + +config CRC32_BIT + bool "Classic Algorithm (one bit at a time)" + help + Calculate checksum one bit at a time. This is VERY slow, but has + no lookup table. This is provided as a debugging option. + + Only choose this option if you are debugging crc32. + +endchoice config CRC7 tristate "CRC7 functions" @@ -224,6 +285,7 @@ config BTREE config HAS_IOMEM boolean depends on !NO_IOMEM + select GENERIC_IO default y config HAS_IOPORT diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index f32a41f2a82a..6777153f18f3 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -184,7 +184,7 @@ config LOCKUP_DETECTOR config HARDLOCKUP_DETECTOR def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \ - !ARCH_HAS_NMI_WATCHDOG + !HAVE_NMI_WATCHDOG config BOOTPARAM_HARDLOCKUP_PANIC bool "Panic (Reboot) On Hard Lockups" @@ -1142,14 +1142,6 @@ config LATENCYTOP Enable this option if you want to use the LatencyTOP tool to find out which userspace is blocking on what kernel operations. -config SYSCTL_SYSCALL_CHECK - bool "Sysctl checks" - depends on SYSCTL - ---help--- - sys_sysctl uses binary paths that have been found challenging - to properly maintain and use. This enables checks that help - you to keep things correct. - source mm/Kconfig.debug source kernel/trace/Kconfig diff --git a/lib/argv_split.c b/lib/argv_split.c index 4b1b083f219c..1e9a6cbc3689 100644 --- a/lib/argv_split.c +++ b/lib/argv_split.c @@ -6,7 +6,7 @@ #include <linux/ctype.h> #include <linux/string.h> #include <linux/slab.h> -#include <linux/module.h> +#include <linux/export.h> static const char *skip_arg(const char *cp) { diff --git a/lib/atomic64.c b/lib/atomic64.c index 3975470caf4f..978537809d84 100644 --- a/lib/atomic64.c +++ b/lib/atomic64.c @@ -13,7 +13,7 @@ #include <linux/cache.h> #include <linux/spinlock.h> #include <linux/init.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/atomic.h> /* diff --git a/lib/atomic64_test.c b/lib/atomic64_test.c index 0c33cde2a1e6..cb99b91c3a1d 100644 --- a/lib/atomic64_test.c +++ b/lib/atomic64_test.c @@ -9,6 +9,7 @@ * (at your option) any later version. */ #include <linux/init.h> +#include <linux/bug.h> #include <linux/kernel.h> #include <linux/atomic.h> diff --git a/lib/average.c b/lib/average.c index 5576c2841496..99a67e662b3c 100644 --- a/lib/average.c +++ b/lib/average.c @@ -5,8 +5,9 @@ * Version 2. See the file COPYING for more details. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/average.h> +#include <linux/kernel.h> #include <linux/bug.h> #include <linux/log2.h> diff --git a/lib/bcd.c b/lib/bcd.c index d74257fd0fe7..55efaf742346 100644 --- a/lib/bcd.c +++ b/lib/bcd.c @@ -1,5 +1,5 @@ #include <linux/bcd.h> -#include <linux/module.h> +#include <linux/export.h> unsigned bcd2bin(unsigned char val) { diff --git a/lib/bitmap.c b/lib/bitmap.c index 0d4a127dd9b3..b5a8b6ad2454 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -5,11 +5,13 @@ * 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> /* diff --git a/lib/bsearch.c b/lib/bsearch.c index 5b54758e2afb..e33c179089db 100644 --- a/lib/bsearch.c +++ b/lib/bsearch.c @@ -9,7 +9,7 @@ * published by the Free Software Foundation; version 2. */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/bsearch.h> /* diff --git a/lib/check_signature.c b/lib/check_signature.c index fd6af199247b..6b49797980c4 100644 --- a/lib/check_signature.c +++ b/lib/check_signature.c @@ -1,5 +1,5 @@ #include <linux/io.h> -#include <linux/module.h> +#include <linux/export.h> /** * check_signature - find BIOS signatures diff --git a/lib/checksum.c b/lib/checksum.c index 8df2f91e6d98..12dceb27ff20 100644 --- a/lib/checksum.c +++ b/lib/checksum.c @@ -32,7 +32,7 @@ /* Revised by Kenneth Albanowski for m68knommu. Basic problem: unaligned access kills, so most of the assembly has to go. */ -#include <linux/module.h> +#include <linux/export.h> #include <net/checksum.h> #include <asm/byteorder.h> diff --git a/lib/cmdline.c b/lib/cmdline.c index f5f3ad8b62ff..eb6791188cf5 100644 --- a/lib/cmdline.c +++ b/lib/cmdline.c @@ -12,7 +12,7 @@ * */ -#include <linux/module.h> +#include <linux/export.h> #include <linux/kernel.h> #include <linux/string.h> diff --git a/lib/cpu_rmap.c b/lib/cpu_rmap.c index 987acfafeb83..145dec5267c9 100644 --- a/lib/cpu_rmap.c +++ b/lib/cpu_rmap.c @@ -11,7 +11,7 @@ #ifdef CONFIG_GENERIC_HARDIRQS #include <linux/interrupt.h> #endif -#include <linux/module.h> +#include <linux/export.h> /* * These functions maintain a mapping from CPUs to some ordered set of diff --git a/lib/cpumask.c b/lib/cpumask.c index af3e5817de98..402a54ac35cb 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -2,7 +2,7 @@ #include <linux/kernel.h> #include <linux/bitops.h> #include <linux/cpumask.h> -#include <linux/module.h> +#include <linux/export.h> #include <linux/bootmem.h> int __first_cpu(const cpumask_t *srcp) @@ -26,18 +26,6 @@ int __next_cpu_nr(int n, const cpumask_t *srcp) EXPORT_SYMBOL(__next_cpu_nr); #endif -int __any_online_cpu(const cpumask_t *mask) -{ - int cpu; - - for_each_cpu(cpu, mask) { - if (cpu_online(cpu)) - break; - } - return cpu; -} -EXPORT_SYMBOL(__any_online_cpu); - /** * cpumask_next_and - get the next cpu in *src1p & *src2p * @n: the cpu prior to the place to search (ie. return will be > @n) diff --git a/lib/crc32.c b/lib/crc32.c index 4b35d2b4437c..b0d278fb1d91 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -1,4 +1,8 @@ /* + * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin + * cleaned up code to current version of sparse and added the slicing-by-8 + * algorithm to the closely similar existing slicing-by-4 algorithm. + * * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! * Code was from the public domain, copyright abandoned. Code was @@ -20,52 +24,58 @@ * Version 2. See the file COPYING for more details. */ +/* see: Documentation/crc32.txt for a description of algorithms */ + #include <linux/crc32.h> -#include <linux/kernel.h> #include <linux/module.h> -#include <linux/compiler.h> #include <linux/types.h> -#include <linux/init.h> -#include <linux/atomic.h> #include "crc32defs.h" -#if CRC_LE_BITS == 8 -# define tole(x) __constant_cpu_to_le32(x) + +#if CRC_LE_BITS > 8 +# define tole(x) ((__force u32) __constant_cpu_to_le32(x)) #else # define tole(x) (x) #endif -#if CRC_BE_BITS == 8 -# define tobe(x) __constant_cpu_to_be32(x) +#if CRC_BE_BITS > 8 +# define tobe(x) ((__force u32) __constant_cpu_to_be32(x)) #else # define tobe(x) (x) #endif + #include "crc32table.h" MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); -MODULE_DESCRIPTION("Ethernet CRC32 calculations"); +MODULE_DESCRIPTION("Various CRC32 calculations"); MODULE_LICENSE("GPL"); -#if CRC_LE_BITS == 8 || CRC_BE_BITS == 8 +#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 +/* implements slicing-by-4 or slicing-by-8 algorithm */ static inline u32 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) { # ifdef __LITTLE_ENDIAN # define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8) -# define DO_CRC4 crc = t3[(crc) & 255] ^ \ - t2[(crc >> 8) & 255] ^ \ - t1[(crc >> 16) & 255] ^ \ - t0[(crc >> 24) & 255] +# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \ + t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255]) +# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \ + t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255]) # else # define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) -# define DO_CRC4 crc = t0[(crc) & 255] ^ \ - t1[(crc >> 8) & 255] ^ \ - t2[(crc >> 16) & 255] ^ \ - t3[(crc >> 24) & 255] +# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \ + t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255]) +# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \ + t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255]) # endif const u32 *b; size_t rem_len; +# ifdef CONFIG_X86 + size_t i; +# endif const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; + const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; + u32 q; /* Align it */ if (unlikely((long)buf & 3 && len)) { @@ -73,27 +83,51 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) DO_CRC(*buf++); } while ((--len) && ((long)buf)&3); } + +# if CRC_LE_BITS == 32 rem_len = len & 3; - /* load data 32 bits wide, xor data 32 bits wide. */ len = len >> 2; +# else + rem_len = len & 7; + len = len >> 3; +# endif + b = (const u32 *)buf; +# ifdef CONFIG_X86 + --b; + for (i = 0; i < len; i++) { +# else for (--b; len; --len) { - crc ^= *++b; /* use pre increment for speed */ - DO_CRC4; +# endif + q = crc ^ *++b; /* use pre increment for speed */ +# if CRC_LE_BITS == 32 + crc = DO_CRC4; +# else + crc = DO_CRC8; + q = *++b; + crc ^= DO_CRC4; +# endif } len = rem_len; /* And the last few bytes */ if (len) { u8 *p = (u8 *)(b + 1) - 1; +# ifdef CONFIG_X86 + for (i = 0; i < len; i++) + DO_CRC(*++p); /* use pre increment for speed */ +# else do { DO_CRC(*++p); /* use pre increment for speed */ } while (--len); +# endif } return crc; #undef DO_CRC #undef DO_CRC4 +#undef DO_CRC8 } #endif + /** * crc32_le() - Calculate bitwise little-endian Ethernet AUTODIN II CRC32 * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for @@ -101,53 +135,66 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) * @p: pointer to buffer over which CRC is run * @len: length of buffer @p */ -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len); - -#if CRC_LE_BITS == 1 -/* - * In fact, the table-based code will work in this case, but it can be - * simplified by inlining the table in ?: form. - */ - -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, + size_t len, const u32 (*tab)[256], + u32 polynomial) { +#if CRC_LE_BITS == 1 int i; while (len--) { crc ^= *p++; for (i = 0; i < 8; i++) - crc = (crc >> 1) ^ ((crc & 1) ? CRCPOLY_LE : 0); + crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); + } +# elif CRC_LE_BITS == 2 + while (len--) { + crc ^= *p++; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; + crc = (crc >> 2) ^ tab[0][crc & 3]; } - return crc; -} -#else /* Table-based approach */ - -u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) -{ -# if CRC_LE_BITS == 8 - const u32 (*tab)[] = crc32table_le; - - crc = __cpu_to_le32(crc); - crc = crc32_body(crc, p, len, tab); - return __le32_to_cpu(crc); # elif CRC_LE_BITS == 4 while (len--) { crc ^= *p++; - crc = (crc >> 4) ^ crc32table_le[crc & 15]; - crc = (crc >> 4) ^ crc32table_le[crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; + crc = (crc >> 4) ^ tab[0][crc & 15]; } - return crc; -# elif CRC_LE_BITS == 2 +# elif CRC_LE_BITS == 8 + /* aka Sarwate algorithm */ while (len--) { crc ^= *p++; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; - crc = (crc >> 2) ^ crc32table_le[crc & 3]; + crc = (crc >> 8) ^ tab[0][crc & 255]; } +# else + crc = (__force u32) __cpu_to_le32(crc); + crc = crc32_body(crc, p, len, tab); + crc = __le32_to_cpu((__force __le32)crc); +#endif return crc; -# endif +} + +#if CRC_LE_BITS == 1 +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRCPOLY_LE); +} +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) +{ + return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE); +} +#else +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) |