diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 55 | ||||
| -rw-r--r-- | lib/Kconfig.debug | 105 | ||||
| -rw-r--r-- | lib/Makefile | 10 | ||||
| -rw-r--r-- | lib/bch.c | 1368 | ||||
| -rw-r--r-- | lib/bitmap.c | 2 | ||||
| -rw-r--r-- | lib/bsearch.c | 53 | ||||
| -rw-r--r-- | lib/btree.c | 4 | ||||
| -rw-r--r-- | lib/cpu_rmap.c | 269 | ||||
| -rw-r--r-- | lib/debugobjects.c | 9 | ||||
| -rw-r--r-- | lib/decompress_unxz.c | 2 | ||||
| -rw-r--r-- | lib/dma-debug.c | 18 | ||||
| -rw-r--r-- | lib/dynamic_debug.c | 61 | ||||
| -rw-r--r-- | lib/find_next_bit.c | 18 | ||||
| -rw-r--r-- | lib/kernel_lock.c | 143 | ||||
| -rw-r--r-- | lib/kstrtox.c | 224 | ||||
| -rw-r--r-- | lib/parser.c | 2 | ||||
| -rw-r--r-- | lib/plist.c | 135 | ||||
| -rw-r--r-- | lib/rwsem.c | 10 | ||||
| -rw-r--r-- | lib/show_mem.c | 4 | ||||
| -rw-r--r-- | lib/string.c | 29 | ||||
| -rw-r--r-- | lib/test-kstrtox.c | 739 | ||||
| -rw-r--r-- | lib/timerqueue.c | 2 | ||||
| -rw-r--r-- | lib/vsprintf.c | 175 | ||||
| -rw-r--r-- | lib/xz/xz_dec_lzma2.c | 6 | ||||
| -rw-r--r-- | lib/zlib_deflate/deflate.c | 31 | ||||
| -rw-r--r-- | lib/zlib_deflate/defutil.h | 17 |
26 files changed, 3069 insertions, 422 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 0ee67e08ad3e..9c10e38fc609 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -22,6 +22,9 @@ config GENERIC_FIND_FIRST_BIT config GENERIC_FIND_NEXT_BIT bool +config GENERIC_FIND_BIT_LE + bool + config GENERIC_FIND_LAST_BIT bool default y @@ -155,6 +158,45 @@ config REED_SOLOMON_DEC16 boolean # +# BCH support is selected if needed +# +config BCH + tristate + +config BCH_CONST_PARAMS + boolean + help + Drivers may select this option to force specific constant + values for parameters 'm' (Galois field order) and 't' + (error correction capability). Those specific values must + be set by declaring default values for symbols BCH_CONST_M + and BCH_CONST_T. + Doing so will enable extra compiler optimizations, + improving encoding and decoding performance up to 2x for + usual (m,t) values (typically such that m*t < 200). + When this option is selected, the BCH library supports + only a single (m,t) configuration. This is mainly useful + for NAND flash board drivers requiring known, fixed BCH + parameters. + +config BCH_CONST_M + int + range 5 15 + help + Constant value for Galois field order 'm'. If 'k' is the + number of data bits to protect, 'm' should be chosen such + that (k + m*t) <= 2**m - 1. + Drivers should declare a default value for this symbol if + they select option BCH_CONST_PARAMS. + +config BCH_CONST_T + int + help + Constant value for error correction capability in bits 't'. + Drivers should declare a default value for this symbol if + they select option BCH_CONST_PARAMS. + +# # Textsearch support is select'ed if needed # config TEXTSEARCH @@ -201,6 +243,10 @@ config DISABLE_OBSOLETE_CPUMASK_FUNCTIONS bool "Disable obsolete cpumask functions" if DEBUG_PER_CPU_MAPS depends on EXPERIMENTAL && BROKEN +config CPU_RMAP + bool + depends on SMP + # # Netlink attribute parsing support is select'ed if needed # @@ -217,6 +263,13 @@ config LRU_CACHE tristate config AVERAGE - bool + bool "Averaging functions" + help + This option is provided for the case where no in-kernel-tree + modules require averaging functions, but a module built outside + the kernel tree does. Such modules that use library averaging + functions require Y here. + + If unsure, say N. endmenu diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 2b97418c67e2..0efcdca9751a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -7,7 +7,19 @@ config PRINTK_TIME 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. + in kernel startup. Or add printk.time=1 at boot-time. + See Documentation/kernel-parameters.txt + +config DEFAULT_MESSAGE_LOGLEVEL + int "Default message log level (1-7)" + range 1 7 + default "4" + help + Default log level for printk statements with no specified priority. + + This was hard-coded to KERN_WARNING since at least 2.6.10 but folks + that are auditing their logs closely may want to set it to a lower + priority. config ENABLE_WARN_DEPRECATED bool "Enable __deprecated logic" @@ -102,11 +114,6 @@ config HEADERS_CHECK config DEBUG_SECTION_MISMATCH bool "Enable full Section mismatch analysis" - depends on UNDEFINED || (BLACKFIN) - default y - # This option is on purpose disabled for now. - # It will be enabled when we are down to a reasonable number - # of section mismatch warnings (< 10 for an allyesconfig build) help The section mismatch analysis checks if there are illegal references from one section to another section. @@ -176,6 +183,23 @@ config HARDLOCKUP_DETECTOR def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \ !ARCH_HAS_NMI_WATCHDOG +config BOOTPARAM_HARDLOCKUP_PANIC + bool "Panic (Reboot) On Hard Lockups" + depends on LOCKUP_DETECTOR + help + Say Y here to enable the kernel to panic on "hard lockups", + which are bugs that cause the kernel to loop in kernel + mode with interrupts disabled for more than 60 seconds. + + Say N if unsure. + +config BOOTPARAM_HARDLOCKUP_PANIC_VALUE + int + depends on LOCKUP_DETECTOR + range 0 1 + default 0 if !BOOTPARAM_HARDLOCKUP_PANIC + default 1 if BOOTPARAM_HARDLOCKUP_PANIC + config BOOTPARAM_SOFTLOCKUP_PANIC bool "Panic (Reboot) On Soft Lockups" depends on LOCKUP_DETECTOR @@ -215,6 +239,21 @@ config DETECT_HUNG_TASK enabled then all held locks will also be reported. This feature has negligible overhead. +config DEFAULT_HUNG_TASK_TIMEOUT + int "Default timeout for hung task detection (in seconds)" + depends on DETECT_HUNG_TASK + default 120 + help + This option controls the default timeout (in seconds) used + to determine when a task has become non-responsive and should + be considered hung. + + It can be adjusted at runtime via the kernel.hung_task_timeout + sysctl or by writing a value to /proc/sys/kernel/hung_task_timeout. + + A timeout of 0 disables the check. The default is two minutes. + Keeping the default should be fine in most cases. + config BOOTPARAM_HUNG_TASK_PANIC bool "Panic (Reboot) On Hung Tasks" depends on DETECT_HUNG_TASK @@ -314,7 +353,7 @@ config DEBUG_OBJECTS_WORK config DEBUG_OBJECTS_RCU_HEAD bool "Debug RCU callbacks objects" - depends on DEBUG_OBJECTS && PREEMPT + depends on DEBUG_OBJECTS help Enable this to turn on debugging of RCU list heads (call_rcu() usage). @@ -375,9 +414,9 @@ config SLUB_STATS config DEBUG_KMEMLEAK bool "Kernel memory leak detector" depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \ - (X86 || ARM || PPC || S390 || SPARC64 || SUPERH || MICROBLAZE || TILE) + (X86 || ARM || PPC || MIPS || S390 || SPARC64 || SUPERH || MICROBLAZE || TILE) - select DEBUG_FS if SYSFS + select DEBUG_FS select STACKTRACE if STACKTRACE_SUPPORT select KALLSYMS select CRC32 @@ -411,11 +450,9 @@ config DEBUG_KMEMLEAK_EARLY_LOG_SIZE config DEBUG_KMEMLEAK_TEST tristate "Simple test for the kernel memory leak detector" - depends on DEBUG_KMEMLEAK + depends on DEBUG_KMEMLEAK && m help - Say Y or M here to build a test for the kernel memory leak - detector. This option enables a module that explicitly leaks - memory. + This option enables a module that explicitly leaks memory. If unsure, say N. @@ -470,15 +507,6 @@ config DEBUG_MUTEXES This feature allows mutex semantics violations to be detected and reported. -config BKL - bool "Big Kernel Lock" if (SMP || PREEMPT) - default y - help - This is the traditional lock that is used in old code instead - of proper locking. All drivers that use the BKL should depend - on this symbol. - Say Y here unless you are working on removing the BKL. - config DEBUG_LOCK_ALLOC bool "Lock debugging: detect incorrect freeing of live locks" depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT @@ -863,22 +891,9 @@ config RCU_TORTURE_TEST_RUNNABLE Say N here if you want the RCU torture tests to start only after being manually enabled via /proc. -config RCU_CPU_STALL_DETECTOR - bool "Check for stalled CPUs delaying RCU grace periods" - depends on TREE_RCU || TREE_PREEMPT_RCU - default y - help - This option causes RCU to printk information on which - CPUs are delaying the current grace period, but only when - the grace period extends for excessive time periods. - - Say N if you want to disable such checks. - - Say Y if you are unsure. - config RCU_CPU_STALL_TIMEOUT int "RCU CPU stall timeout in seconds" - depends on RCU_CPU_STALL_DETECTOR + depends on TREE_RCU || TREE_PREEMPT_RCU range 3 300 default 60 help @@ -887,22 +902,9 @@ config RCU_CPU_STALL_TIMEOUT RCU grace period persists, additional CPU stall warnings are printed at more widely spaced intervals. -config RCU_CPU_STALL_DETECTOR_RUNNABLE - bool "RCU CPU stall checking starts automatically at boot" - depends on RCU_CPU_STALL_DETECTOR - default y - help - If set, start checking for RCU CPU stalls immediately on - boot. Otherwise, RCU CPU stall checking must be manually - enabled. - - Say Y if you are unsure. - - Say N if you wish to suppress RCU CPU stall checking during boot. - config RCU_CPU_STALL_VERBOSE bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR" - depends on RCU_CPU_STALL_DETECTOR && TREE_PREEMPT_RCU + depends on TREE_PREEMPT_RCU default y help This option causes RCU to printk detailed per-task information @@ -1236,3 +1238,6 @@ source "samples/Kconfig" source "lib/Kconfig.kgdb" source "lib/Kconfig.kmemcheck" + +config TEST_KSTRTOX + tristate "Test kstrto*() family of functions at runtime" diff --git a/lib/Makefile b/lib/Makefile index cbb774f7d41d..4b49a249064b 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,10 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o + string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \ + bsearch.o +obj-y += kstrtox.o +obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG @@ -38,12 +41,12 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o +lib-$(CONFIG_GENERIC_FIND_BIT_LE) += find_next_bit.o obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS)) obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o -obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o @@ -67,6 +70,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ +obj-$(CONFIG_BCH) += bch.o obj-$(CONFIG_LZO_COMPRESS) += lzo/ obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ obj-$(CONFIG_XZ_DEC) += xz/ @@ -110,6 +114,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/bch.c b/lib/bch.c new file mode 100644 index 000000000000..bc89dfe4d1b3 --- /dev/null +++ b/lib/bch.c @@ -0,0 +1,1368 @@ +/* + * Generic binary BCH encoding/decoding library + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published by + * the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along with + * this program; if not, write to the Free Software Foundation, Inc., 51 + * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Copyright © 2011 Parrot S.A. + * + * Author: Ivan Djelic <ivan.djelic@parrot.com> + * + * Description: + * + * This library provides runtime configurable encoding/decoding of binary + * Bose-Chaudhuri-Hocquenghem (BCH) codes. + * + * Call init_bch to get a pointer to a newly allocated bch_control structure for + * the given m (Galois field order), t (error correction capability) and + * (optional) primitive polynomial parameters. + * + * Call encode_bch to compute and store ecc parity bytes to a given buffer. + * Call decode_bch to detect and locate errors in received data. + * + * On systems supporting hw BCH features, intermediate results may be provided + * to decode_bch in order to skip certain steps. See decode_bch() documentation + * for details. + * + * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of + * parameters m and t; thus allowing extra compiler optimizations and providing + * better (up to 2x) encoding performance. Using this option makes sense when + * (m,t) are fixed and known in advance, e.g. when using BCH error correction + * on a particular NAND flash device. + * + * Algorithmic details: + * + * Encoding is performed by processing 32 input bits in parallel, using 4 + * remainder lookup tables. + * + * The final stage of decoding involves the following internal steps: + * a. Syndrome computation + * b. Error locator polynomial computation using Berlekamp-Massey algorithm + * c. Error locator root finding (by far the most expensive step) + * + * In this implementation, step c is not performed using the usual Chien search. + * Instead, an alternative approach described in [1] is used. It consists in + * factoring the error locator polynomial using the Berlekamp Trace algorithm + * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial + * solving techniques [2] are used. The resulting algorithm, called BTZ, yields + * much better performance than Chien search for usual (m,t) values (typically + * m >= 13, t < 32, see [1]). + * + * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields + * of characteristic 2, in: Western European Workshop on Research in Cryptology + * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear. + * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over + * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996. + */ + +#include <linux/kernel.h> +#include <linux/errno.h> +#include <linux/init.h> +#include <linux/module.h> +#include <linux/slab.h> +#include <linux/bitops.h> +#include <asm/byteorder.h> +#include <linux/bch.h> + +#if defined(CONFIG_BCH_CONST_PARAMS) +#define GF_M(_p) (CONFIG_BCH_CONST_M) +#define GF_T(_p) (CONFIG_BCH_CONST_T) +#define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1) +#else +#define GF_M(_p) ((_p)->m) +#define GF_T(_p) ((_p)->t) +#define GF_N(_p) ((_p)->n) +#endif + +#define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32) +#define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8) + +#ifndef dbg +#define dbg(_fmt, args...) do {} while (0) +#endif + +/* + * represent a polynomial over GF(2^m) + */ +struct gf_poly { + unsigned int deg; /* polynomial degree */ + unsigned int c[0]; /* polynomial terms */ +}; + +/* given its degree, compute a polynomial size in bytes */ +#define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int)) + +/* polynomial of degree 1 */ +struct gf_poly_deg1 { + struct gf_poly poly; + unsigned int c[2]; +}; + +/* + * same as encode_bch(), but process input data one byte at a time + */ +static void encode_bch_unaligned(struct bch_control *bch, + const unsigned char *data, unsigned int len, + uint32_t *ecc) +{ + int i; + const uint32_t *p; + const int l = BCH_ECC_WORDS(bch)-1; + + while (len--) { + p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); + + for (i = 0; i < l; i++) + ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); + + ecc[l] = (ecc[l] << 8)^(*p); + } +} + +/* + * convert ecc bytes to aligned, zero-padded 32-bit ecc words + */ +static void load_ecc8(struct bch_control *bch, uint32_t *dst, + const uint8_t *src) +{ + uint8_t pad[4] = {0, 0, 0, 0}; + unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; + + for (i = 0; i < nwords; i++, src += 4) + dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; + + memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); + dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; +} + +/* + * convert 32-bit ecc words to ecc bytes + */ +static void store_ecc8(struct bch_control *bch, uint8_t *dst, + const uint32_t *src) +{ + uint8_t pad[4]; + unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; + + for (i = 0; i < nwords; i++) { + *dst++ = (src[i] >> 24); + *dst++ = (src[i] >> 16) & 0xff; + *dst++ = (src[i] >> 8) & 0xff; + *dst++ = (src[i] >> 0) & 0xff; + } + pad[0] = (src[nwords] >> 24); + pad[1] = (src[nwords] >> 16) & 0xff; + pad[2] = (src[nwords] >> 8) & 0xff; + pad[3] = (src[nwords] >> 0) & 0xff; + memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); +} + +/** + * encode_bch - calculate BCH ecc parity of data + * @bch: BCH control structure + * @data: data to encode + * @len: data length in bytes + * @ecc: ecc parity data, must be initialized by caller + * + * The @ecc parity array is used both as input and output parameter, in order to + * allow incremental computations. It should be of the size indicated by member + * @ecc_bytes of @bch, and should be initialized to 0 before the first call. + * + * The exact number of computed ecc parity bits is given by member @ecc_bits of + * @bch; it may be less than m*t for large values of t. + */ +void encode_bch(struct bch_control *bch, const uint8_t *data, + unsigned int len, uint8_t *ecc) +{ + const unsigned int l = BCH_ECC_WORDS(bch)-1; + unsigned int i, mlen; + unsigned long m; + uint32_t w, r[l+1]; + const uint32_t * const tab0 = bch->mod8_tab; + const uint32_t * const tab1 = tab0 + 256*(l+1); + const uint32_t * const tab2 = tab1 + 256*(l+1); + const uint32_t * const tab3 = tab2 + 256*(l+1); + const uint32_t *pdata, *p0, *p1, *p2, *p3; + + if (ecc) { + /* load ecc parity bytes into internal 32-bit buffer */ + load_ecc8(bch, bch->ecc_buf, ecc); + } else { + memset(bch->ecc_buf, 0, sizeof(r)); + } + + /* process first unaligned data bytes */ + m = ((unsigned long)data) & 3; + if (m) { + mlen = (len < (4-m)) ? len : 4-m; + encode_bch_unaligned(bch, data, mlen, bch->ecc_buf); + data += mlen; + len -= mlen; + } + + /* process 32-bit aligned data words */ + pdata = (uint32_t *)data; + mlen = len/4; + data += 4*mlen; + len -= 4*mlen; + memcpy(r, bch->ecc_buf, sizeof(r)); + + /* + * split each 32-bit word into 4 polynomials of weight 8 as follows: + * + * 31 ...24 23 ...16 15 ... 8 7 ... 0 + * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt + * tttttttt mod g = r0 (precomputed) + * zzzzzzzz 00000000 mod g = r1 (precomputed) + * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) + * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) + * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 + */ + while (mlen--) { + /* input data is read in big-endian format */ + w = r[0]^cpu_to_be32(*pdata++); + p0 = tab0 + (l+1)*((w >> 0) & 0xff); + p1 = tab1 + (l+1)*((w >> 8) & 0xff); + p2 = tab2 + (l+1)*((w >> 16) & 0xff); + p3 = tab3 + (l+1)*((w >> 24) & 0xff); + + for (i = 0; i < l; i++) + r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; + + r[l] = p0[l]^p1[l]^p2[l]^p3[l]; + } + memcpy(bch->ecc_buf, r, sizeof(r)); + + /* process last unaligned bytes */ + if (len) + encode_bch_unaligned(bch, data, len, bch->ecc_buf); + + /* store ecc parity bytes into original parity buffer */ + if (ecc) + store_ecc8(bch, ecc, bch->ecc_buf); +} +EXPORT_SYMBOL_GPL(encode_bch); + +static inline int modulo(struct bch_control *bch, unsigned int v) +{ + const unsigned int n = GF_N(bch); + while (v >= n) { + v -= n; + v = (v & n) + (v >> GF_M(bch)); + } + return v; +} + +/* + * shorter and faster modulo function, only works when v < 2N. + */ +static inline int mod_s(struct bch_control *bch, unsigned int v) +{ + const unsigned int n = GF_N(bch); + return (v < n) ? v : v-n; +} + +static inline int deg(unsigned int poly) +{ + /* polynomial degree is the most-significant bit index */ + return fls(poly)-1; +} + +static inline int parity(unsigned int x) +{ + /* + * public domain code snippet, lifted from + * http://www-graphics.stanford.edu/~seander/bithacks.html + */ + x ^= x >> 1; + x ^= x >> 2; + x = (x & 0x11111111U) * 0x11111111U; + return (x >> 28) & 1; +} + +/* Galois field basic operations: multiply, divide, inverse, etc. */ + +static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, + unsigned int b) +{ + return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ + bch->a_log_tab[b])] : 0; +} + +static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) +{ + return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; +} + +static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, + unsigned int b) +{ + return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ + GF_N(bch)-bch->a_log_tab[b])] : 0; +} + +static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) +{ + return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; +} + +static inline unsigned int a_pow(struct bch_control *bch, int i) +{ + return bch->a_pow_tab[modulo(bch, i)]; +} + +static inline int a_log(struct bch_control *bch, unsigned int x) +{ + return bch->a_log_tab[x]; +} + +static inline int a_ilog(struct bch_control *bch, unsigned int x) +{ + return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); +} + +/* + * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t + */ +static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, + unsigned int *syn) +{ + int i, j, s; + unsigned int m; + uint32_t poly; + const int t = GF_T(bch); + + s = bch->ecc_bits; + + /* make sure extra bits in last ecc word are cleared */ + m = ((unsigned int)s) & 31; + if (m) + ecc[s/32] &= ~((1u << (32-m))-1); + memset(syn, 0, 2*t*sizeof(*syn)); + + /* compute v(a^j) for j=1 .. 2t-1 */ + do { + poly = *ecc++; + s -= 32; + while (poly) { + i = deg(poly); + for (j = 0; j < 2*t; j += 2) + syn[j] ^= a_pow(bch, (j+1)*(i+s)); + + poly ^= (1 << i); + } + } while (s > 0); + + /* v(a^(2j)) = v(a^j)^2 */ + for (j = 0; j < t; j++) + syn[2*j+1] = gf_sqr(bch, syn[j]); +} + +static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) +{ + memcpy(dst, src, GF_POLY_SZ(src->deg)); +} + +static int compute_error_locator_polynomial(struct bch_control *bch, + const unsigned int *syn) +{ + const unsigned int t = GF_T(bch); + const unsigned int n = GF_N(bch); + unsigned int i, j, tmp, l, pd = 1, d = syn[0]; + struct gf_poly *elp = bch->elp; + struct gf_poly *pelp = bch->poly_2t[0]; + struct gf_poly *elp_copy = bch->poly_2t[1]; + int k, pp = -1; + + memset(pelp, 0, GF_POLY_SZ(2*t)); + memset(elp, 0, GF_POLY_SZ(2*t)); + + pelp->deg = 0; + pelp->c[0] = 1; + elp->deg = 0; + elp->c[0] = 1; + + /* use simplified binary Berlekamp-Massey algorithm */ + for (i = 0; (i < t) && (elp->deg <= t); i++) { + if (d) { + k = 2*i-pp; + gf_poly_copy(elp_copy, elp); + /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ + tmp = a_log(bch, d)+n-a_log(bch, pd); + for (j = 0; j <= pelp->deg; j++) { + if (pelp->c[j]) { + l = a_log(bch, pelp->c[j]); + elp->c[j+k] ^= a_pow(bch, tmp+l); + } + } + /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ + tmp = pelp->deg+k; + if (tmp > elp->deg) { + elp->deg = tmp; + gf_poly_copy(pelp, elp_copy); + pd = d; + pp = 2*i; + } + } + /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ + if (i < t-1) { + d = syn[2*i+2]; + for (j = 1; j <= elp->deg; j++) + d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); + } + } + dbg("elp=%s\n", gf_poly_str(elp)); + return (elp->deg > t) ? -1 : (int)elp->deg; +} + +/* + * solve a m x m linear system in GF(2) with an expected number of solutions, + * and return the number of found solutions + */ +static int solve_linear_system(struct bch_control *bch, unsigned int *rows, + unsigned int *sol, int nsol) +{ + const int m = GF_M(bch); + unsigned int tmp, mask; + int rem, c, r, p, k, param[m]; + + k = 0; + mask = 1 << m; + + /* Gaussian elimination */ + for (c = 0; c < m; c++) { + rem = 0; + p = c-k; + /* find suitable row for elimination */ + for (r = p; r < m; r++) { + if (rows[r] & mask) { + if (r != p) { + tmp = rows[r]; + rows[r] = rows[p]; + rows[p] = tmp; + } + rem = r+1; + break; + } + } + if (rem) { + /* perform elimination on remaining rows */ + tmp = rows[p]; + for (r = rem; r < m; r++) { + if (rows[r] & mask) + rows[r] ^= tmp; + } + } else { + /* elimination not needed, store defective row index */ + param[k++] = c; + } + mask >>= 1; + } + /* rewrite system, inserting fake parameter rows */ + if (k > 0) { + p = k; + for (r = m-1; r >= 0; r--) { + if ((r > m-1-k) && rows[r]) + /* system has no solution */ + return 0; + + rows[r] = (p && (r == param[p-1])) ? + p--, 1u << (m-r) : rows[r-p]; + } + } + + if (nsol != (1 << k)) + /* unexpected number of solutions */ + return 0; + + for (p = 0; p < nsol; p++) { + /* set parameters for p-th solution */ + for (c = 0; c < k; c++) + rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1); + + /* compute unique solution */ + tmp = 0; + for (r = m-1; r >= 0; r--) { + mask = rows[r] & (tmp|1); + tmp |= parity(mask) << (m-r); + } + sol[p] = tmp >> 1; + } + return nsol; +} + +/* + * this function builds and solves a linear system for finding roots of a degree + * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). + */ +static int find_affine4_roots(struct bch_control *bch, unsigned int a, + unsigned int b, unsigned int c, + unsigned int *roots) +{ + int i, j, k; + const int m = GF_M(bch); + unsigned int mask = 0xff, t, rows[16] = {0,}; + + j = a_log(bch, b); + k = a_log(bch, a); + rows[0] = c; + + /* buid linear system to solve X^4+aX^2+bX+c = 0 */ + for (i = 0; i < m; i++) { + rows[i+1] = bch->a_pow_tab[4*i]^ + (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ + (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); + j++; + k += 2; + } + /* + * transpose 16x16 matrix before passing it to linear solver + * warning: this code assumes m < 16 + */ + for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { + for (k = 0; k < 16; k = (k+j+1) & ~j) { + t = ((rows[k] >> j)^rows[k+j]) & mask; + rows[k] ^= (t << j); + rows[k+j] ^= t; + } + } + return solve_linear_system(bch, rows, roots, 4); +} + +/* + * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) + */ +static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int n = 0; + + if (poly->c[0]) + /* poly[X] = bX+c with c!=0, root=c/b */ + roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ + bch->a_log_tab[poly->c[1]]); + return n; +} + +/* + * compute roots of a degree 2 polynomial over GF(2^m) + */ +static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int n = 0, i, l0, l1, l2; + unsigned int u, v, r; + + if (poly->c[0] && poly->c[1]) { + + l0 = bch->a_log_tab[poly->c[0]]; + l1 = bch->a_log_tab[poly->c[1]]; + l2 = bch->a_log_tab[poly->c[2]]; + + /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */ + u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); + /* + * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): + * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) = + * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u) + * i.e. r and r+1 are roots iff Tr(u)=0 + */ + r = 0; + v = u; + while (v) { + i = deg(v); + r ^= bch->xi_tab[i]; + v ^= (1 << i); + } + /* verify root */ + if ((gf_sqr(bch, r)^r) == u) { + /* reverse z=a/bX transformation and compute log(1/r) */ + roots[n++] = modulo(bch, 2*GF_N(bch)-l1- + bch->a_log_tab[r]+l2); + roots[n++] = modulo(bch, 2*GF_N(bch)-l1- + bch->a_log_tab[r^1]+l2); + } + } + return n; +} + +/* + * compute roots of a degree 3 polynomial over GF(2^m) + */ +static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int i, n = 0; + unsigned int a, b, c, a2, b2, c2, e3, tmp[4]; + + if (poly->c[0]) { + /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */ + e3 = poly->c[3]; + c2 = gf_div(bch, poly->c[0], e3); + b2 = gf_div(bch, poly->c[1], e3); + a2 = gf_div(bch, poly->c[2], e3); + + /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */ + c = gf_mul(bch, a2, c2); /* c = a2c2 */ + b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ + a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ + + /* find the 4 roots of this affine polynomial */ + if (find_affine4_roots(bch, a, b, c, tmp) == 4) { + /* remove a2 from final list of roots */ + for (i = 0; i < 4; i++) { + if (tmp[i] != a2) + roots[n++] = a_ilog(bch, tmp[i]); + } + } + } + return n; +} + +/* + * compute roots of a degree 4 polynomial over GF(2^m) + */ +static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, + unsigned int *roots) +{ + int i, l, n = 0; + unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; + + if (poly->c[0] == 0) + return 0; + + /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */ + e4 = poly->c[4]; + d = gf_div(bch, poly->c[0], e4); + c = gf_div(bch, poly->c[1], e4); + b = gf_div(bch, poly->c[2], e4); + a = gf_div(bch, poly->c[3], e4); + + /* use Y=1/X transformation to get an affine polynomial */ + if (a) { + /* first, eliminate cX by using z=X+e with ae^2+c=0 */ + if (c) { + /* compute e such that e^2 = c/a */ + f = gf_div(bch, c, a); + l = a_log(bch, f); + l += (l & 1) ? GF_N(bch) : 0; + e = a_pow(bch, l/2); + /* + * use transformation z=X+e: + * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d + * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d + * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d + * z^4 + az^3 + b'z^2 + d' + */ + d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; + b = gf_mul(bch, a, e)^b; + } + /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */ + if (d == 0) + /* assume all roots have multiplicity 1 */ + return 0; + + c2 = gf_inv(bch, d); + b2 = gf_div(bch, a, d); + a2 = gf_div(bch, b, d); + } else { + /* polynomial is already affine */ + c2 = d; + b2 = c; + a2 = b; + } + /* find the 4 roots of this affine polynomial */ + if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { + for (i = 0; i < 4; i++) { + /* post-process roots (reverse transformations) */ + f = a ? gf_inv(bch, roots[i]) : roots[i]; + roots[i] = a_ilog(bch, f^e); + } + n = 4; + } + return n; +} + +/* + * build monic, log-based representation of a polynomial + */ +static void gf_poly_logrep(struct bch_control *bch, + const struct gf_poly *a, int *rep) +{ + int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); + + /* represent 0 values with -1; warning, rep[d] is not set to 1 */ + for (i = 0; i < d; i++) + rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; +} + +/* + * compute polynomial Euclidean division remainder in GF(2^m)[X] + */ +static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, + const struct gf_poly *b, int *rep) +{ + int la, p, m; + unsigned int i, j, *c = a->c; + const unsigned int d = b->deg; + + if (a->deg < d) + return; + + /* reuse or compute log representation of denominator */ + if (!rep) { + rep = bch->cache; + gf_poly_logrep(bch, b, rep); + } + + for (j = a->deg; j >= d; j--) { + if (c[j]) { + la = a_log(bch, c[j]); + p = j-d; + for (i = 0; i < d; i++, p++) { + m = rep[i]; + if (m >= 0) + c[p] ^= bch->a_pow_tab[mod_s(bch, + m+la)]; + } + } + } + a->deg = d-1; + while (!c[a->deg] && a->deg) + a->deg--; +} + +/* + * compute polynomial Euclidean division quotient in GF(2^m)[X] + */ +static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, + const struct gf_poly *b, struct gf_poly *q) +{ + if (a->deg >= b->deg) { + q->deg = a->deg-b->deg; + /* compute a mod b (modifies a) */ + gf_poly_mod(bch, a, b, NULL); + /* quotient is stored in upper part of polynomial a */ + memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); + } else { + q->deg = 0; + q->c[0] = 0; + } +} + +/* + * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] + */ +static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, + struct gf_poly *b) +{ + struct gf_poly *tmp; + + dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b)); + + if (a->deg < b->deg) { + tmp = b; + b = a; + a = tmp; + } + + while (b->deg > 0) { + gf_poly_mod(bch, a, b, NULL); + tmp = b; + b = a; + a = tmp; + } + + dbg("%s\n", gf_poly_str(a)); + + return a; +} + +/* + * Given a polynomial f and an integer k, compute Tr(a^kX) mod f + * This is used in Berlekamp Trace algorithm for splitting polynomials + */ +static void compute_trace_bk_mod(struct bch_control *bch, int k, + const struct gf_poly *f, struct gf_poly *z, + struct gf_poly *out) +{ + const int m = GF_M(bch); + int i, j; + + /* z contains z^2j mod f */ + z->deg = 1; + z->c[0] = 0; + z->c[1] = bch->a_pow_tab[k]; + + out->deg = 0; + memset(out, 0, GF_POLY_SZ(f->deg)); + + /* compute f log representation only once */ + gf_poly_logrep(bch, f, bch->cache); + + for (i = 0; i < m; i++) { + /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */ + for (j = z->deg; j >= 0; j--) { + out->c[j] ^= z->c[j]; + z->c[2*j] = gf_sqr(bch, z->c[j]); + z->c[2*j+1] = 0; + } + if (z->deg > out->deg) + out->deg = z->deg; + + if (i < m-1) { + z->deg *= 2; + /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */ + gf_poly_mod(bch, z, f, bch->cache); + } + } + while (!out->c[out->deg] && out->deg) + out->deg--; + + dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out)); +} + +/* + * factor a polynomial using Berlekamp Trace algorithm (BTA) + */ +static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, + struct gf_poly **g, struct gf_poly **h) +{ + struct gf_poly *f2 = bch->poly_2t[0]; + struct gf_poly *q = bch->poly_2t[1]; + struct gf_poly *tk = bch->poly_2t[2]; + struct gf_poly *z = bch->poly_2t[3]; + struct gf_poly *gcd; + + dbg("factoring %s...\n", gf_poly_str(f)); + + *g = f; + *h = NULL; + + /* tk = Tr(a^k.X) mod f */ + compute_trace_bk_mod(bch, k, f, z, tk); + + if (tk->deg > 0) { + /* compute g = gcd(f, tk) (destructive operation) */ + gf_poly_copy(f2, f); + gcd = gf_poly_gcd(bch, f2, tk); + if (gcd->deg < f->deg) { + /* compute h=f/gcd(f,tk); this will modify f and q */ + gf_poly_div(bch, f, gcd, q); + /* store g and h in-place (clobbering f) */ + *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; + gf_poly_copy(*g, gcd); + gf_poly_copy(*h, q); + } + } +} + +/* + * find roots of a polynomial, using BTZ algorithm; see the beginning of this + * file for details + */ +static int find_poly_roots(struct bch_control *bch, unsigned int k, + struct gf_poly *poly, unsigned int *roots) +{ + int cnt; + struct gf_poly *f1, *f2; + + switch (poly->deg) { + /* handle low degree polynomials with ad hoc techniques */ + case 1: + cnt = find_poly_deg1_roots(bch, poly, roots); + break; + case 2: + cnt = find_poly_deg2_roots(bch, poly, roots); + break; + case 3: + cnt = find_poly_deg3_roots(bch, poly, roots); + break; + case 4: + cnt = find_poly_deg4_roots(bch, poly, roots); + break; + default: + /* factor polynomial using Berlekamp Trace Algorithm (BTA) */ + cnt = 0; + if (poly->deg && (k <= GF_M(bch))) { + factor_polynomial(bch, k, poly, &f1, &f2); + if (f1) + cnt += find_poly_roots(bch, k+1, f1, roots); + if (f2) + cnt += find_poly_roots(bch, k+1, f2, roots+cnt); + } + break; + } + return cnt; +} + +#if defined(USE_CHIEN_SEARCH) +/* + * exhaustive root search (Chien) implementation - not used, included only for + * reference/comparison tests + */ +static int chien_search(struct bch_control *bch, unsigned int len, + struct gf_poly *p, unsigned int *roots) +{ + int m; + unsigned int i, j, syn, syn0, count = 0; + const unsigned int k = 8*len+bch->ecc_bits; + + /* use a log-based representation of polynomial */ + gf_poly_logrep(bch, p, bch->cache); + bch->cache[p->deg] = 0; + syn0 = gf_div(bch, p->c[0], p->c[p->deg]); + + for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { + /* compute elp(a^i) */ + for (j = 1, syn = syn0; j <= p->deg; j++) { + m = bch->cache[j]; + if (m >= 0) + syn ^= a_pow(bch, m+j*i); + } + if (syn == 0) { + roots[count++] = GF_N(bch)-i; + if (count == p->deg) + break; + } + } + return (count == p->deg) ? count : 0; +} +#define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc) +#endif /* USE_CHIEN_SEARCH */ + +/** + * decode_bch - decode received codeword and find bit error locations + * @bch: BCH control structure + * @data: received data, ignored if @calc_ecc is provided + * @len: data length in bytes, must always be provided + * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc + * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data + * @syn: hw computed syndrome data (if NULL, syndrome is calculated) + * @errloc: output array of error locations + * + * Returns: + * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if + * invalid parameters were provided + * + * Depending on the available hw BCH support and the need to compute @calc_ecc + * separately (using encode_bch()), this function should be called with one of + * the following parameter configurations - + * + * by providing @data and @recv_ecc only: + * decode_bch(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc) + * + * by providing @recv_ecc and @calc_ecc: + * decode_bch(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc) + * + * by providing ecc = recv_ecc XOR calc_ecc: + * decode_bch(@bch, NULL, @len, NULL, ecc, NULL, @errloc) + * + * by providing syndrome results @syn: + * decode_bch(@bch, NULL, @len, NULL, NULL, @syn, @errloc) + * + * Once decode_bch() has successfully returned with a positive value, error + * locations returned in array @errloc should be interpreted as follows - + * + * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for + * data correction) + * + * if (errloc[n] < 8*len), then n-th error is located in data and can be + * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8); + * + * Note that this function does not perform any data correction by itself, it + * merely indicates error locations. + */ +int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, + const uint8_t *recv_ecc, const uint8_t *calc_ecc, + const unsigned int *syn, unsigned int *errloc) +{ + const unsigned int ecc_words = BCH_ECC_WORDS(bch); + unsigned int nbits; + int i, err, nroots; + uint32_t sum; + + /* sanity check: make sure data length can be handled */ + if (8*len > (bch->n-bch->ecc_bits)) + return -EINVAL; + + /* if caller does not provide syndromes, compute them */ + if (!syn) { + if (!calc_ecc) { + /* compute received data ecc into an internal buffer */ + if (!data || !recv_ecc) + return -EINVAL; + encode_bch(bch, data, len, NULL); + } else { + /* load provided calculated ecc */ + load_ecc8(bch, bch->ecc_buf, calc_ecc); + } + /* load received ecc or assume it was XORed in calc_ecc */ + if (recv_ecc) { + load_ecc8(bch, bch->ecc_buf2, recv_ecc); + /* XOR received and calculated ecc */ + for (i = 0, sum = 0; i < (int)ecc_words; i++) { + bch->ecc_buf[i] ^= bch->ecc_buf2[i]; + sum |= bch->ecc_buf[i]; + } + if (!sum) + /* no error found */ + return 0; + } + compute_syndromes(bch, bch->ecc_buf, bch->syn); + syn = bch->syn; + } + + err = compute_error_locator_polynomial(bch, syn); + if (err > 0) { + nroots = find_poly_roots(bch, 1, bch->elp, errloc); + if (err != nroots) + err = -1; + } + if (err > 0) { + /* post-process raw error locations for easier correction */ + nbits = (len*8)+bch->ecc_bits; + for (i = 0; i < err; i++) { + if (errloc[i] >= nbits) { + err = -1; + break; + } + errloc[i] = nbits-1-errloc[i]; + errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7)); + } + } + return (err >= 0) ? err : -EBADMSG; +} +EXPORT_SYMBOL_GPL(decode_bch); + +/* + * generate Galois field lookup tables + */ +static int build_gf_tables(struct bch_control *bch, unsigned int poly) +{ + unsigned int i, x = 1; + const unsigned int k = 1 << deg(poly); + + /* primitive polynomial must be of degree m */ + if (k != (1u << GF_M(bch))) + return -1; + + for (i = 0; i < GF_N(bch); i++) { + bch->a_pow_tab[i] = x; + bch->a_log_tab[x] = i; + if (i && (x == 1)) + /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */ + return -1; + x <<= 1; + if (x & k) + x ^= poly; + } + bch->a_pow_tab[GF_N(bch)] = 1; + bch->a_log_tab[0] = 0; + + return 0; +} + +/* + * compute generator polynomial remainder tables for fast encoding + */ +static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) +{ + int i, j, b, d; + uint32_t data, hi, lo, *tab; + const int l = BCH_ECC_WORDS(bch); + const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32); + const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32); + + memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); + + for (i = 0; i < 256; i++) { + /* p(X)=i is a small polynomial of weight <= 8 */ + for (b = 0; b < 4; b++) { + /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */ + tab = bch->mod8_tab + (b*256+i)*l; + data = i << (8*b); + while (data) { + d = deg(data); + /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */ + data ^= g[0] >> (31-d); + for (j = 0; j < ecclen; j++) { + hi = (d < 31) ? g[j] << (d+1) : 0; + lo = (j+1 < plen) ? + g[j+1] >> (31-d) : 0; + tab[j] ^= hi|lo; + } + } + } + } +} + +/* + * build a base for factoring degree 2 polynomials + */ +static int build_deg2_base(struct bch_control *bch) +{ + const int m = GF_M(bch); + int i, j, r; + unsigned int sum, x, y, remaining, ak = 0, xi[m]; + + /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */ + for (i = 0; i < m; i++) { + for (j = 0, sum = 0; j < m; j++) + sum ^= a_pow(bch, i*(1 << j)); + + if (sum) { + ak = bch->a_pow_tab[i]; + break; + } + } + /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ + remaining = m; + memset(xi, 0, sizeof(xi)); + + for (x = 0; (x <= GF_N(bch)) && remaining; x++) { + y = gf_sqr(bch, x)^x; + for (i = 0; i < 2; i++) { + r = a_log(bch, y); + if (y && (r < m) && !xi[r]) { + bch->xi_tab[r] = x; + xi[r] = 1; + remaining--; + dbg("x%d = %x\n", r, x); + break; + } + y ^= ak; + } + } + /* should not happen but check anyway */ + return remaining ? -1 : 0; +} + +static void *bch_alloc(size_t size, int *err) +{ + void *ptr; + + ptr = kmalloc(size, GFP_KERNEL); + if (ptr == NULL) + *err = 1; + return ptr; +} + +/* + * compute generator polynomial for given (m,t) parameters. + */ +static uint32_t *compute_generator_polynomial(struct bch_control *bch) +{ + const unsigned int m = GF_M(bch); + const unsigned int t = GF_T(bch); + int n, err = 0; + unsigned int i, j, nbits, r, word, *roots; + struct gf_poly *g; + uint32_t *genpoly; + + g = bch_alloc(GF_POLY_SZ(m*t), &err); + roots = bch_alloc((bch->n+1)*sizeof(*roots), &err); + genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err); + + if (err) { + kfree(genpoly); + genpoly = NULL; + goto finish; + } + + /* enumerate all roots of g(X) */ + memset(roots , 0, (bch->n+1)*sizeof(*roots)); + for (i = 0; i < t; i++) { + for (j = 0, r = 2*i+1; j < m; j++) { + roots[r] = 1; + r = mod_s(bch, 2*r); + } + } + /* build generator polynomial g(X) */ + g->deg = 0; + g->c[0] = 1; + for (i = 0; i < GF_N(bch); i++) { + if (roots[i]) { + /* multiply g(X) by (X+root) */ + r = bch->a_pow_tab[i]; + g->c[g->deg+1] = 1; + for (j = g->deg; j > 0; j--) + g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1]; + + g->c[0] = gf_mul(bch, g->c[0], r); + g->deg++; + } + } + /* store left-justified binary representation of g(X) */ + n = g->deg+1; + i = 0; + + while (n > 0) { + nbits = (n > 32) ? 32 : n; + for (j = 0, word = 0; j < nbits; j++) { + if (g->c[n-1-j]) + word |= 1u << (31-j); + } + genpoly[i++] = word; + n -= nbits; + } + bch->ecc_bits = g->deg; + +finish: + kfree(g); + kfree(roots); + + return genpoly; +} + +/** + * init_bch - initialize a BCH encoder/decoder + * @m: Galois field order, should be in the range 5-15 + * @t: maximum error correction capability, in bits + * @prim_poly: user-provided primitive polynomial (or 0 to use default) + * + * Returns: + * a newly allocated BCH control structure if successful, NULL otherwise + * + * This initialization can take some time, as lookup tables are built for fast + * encoding/decoding; make sure not to call this function from a time critical + * path. Usually, init_bch() should be called on module/driver init and + * free_bch() should be called to release memory on exit. + * + * You may provide your own primitive polynomial of degree @m in argument + * @prim_poly, or let init_bch() use its default polynomial. + * + * Once init_bch() has successfully returned a pointer to a newly allocated + * BCH control structure, ecc length in bytes is given by member @ecc_bytes of + * the structure. + */ +struct bch_control *init_bch(int m, int t, unsigned int prim_poly) +{ + int err = 0; + unsigned int i, words; + uint32_t *genpoly; + struct bch_control *bch = NULL; + + const int min_m = 5; + const int max_m = 15; + + /* default primitive polynomials */ + static const unsigned int prim_poly_tab[] = { + 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b, + 0x402b, 0x8003, + }; + +#if defined(CONFIG_BCH_CONST_PARAMS) + if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) { + printk(KERN_ERR "bch encoder/decoder was configured to support " + "parameters m=%d, t=%d only!\n", + CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T); + goto fail; + } +#endif + if ((m < min_m) || (m > max_m)) + /* + * values of m greater than 15 are not currently supported; + * supporting m > 15 would require changing table base type + * (uint16_t) and a small patch in matrix transposition + */ + goto fail; + + /* sanity checks */ + if ((t < 1) || (m*t >= ((1 << m)-1))) + /* invalid t value */ + goto fail; + + /* select a primitive polynomial for generating GF(2^m) */ + if (prim_poly == 0) + prim_poly = prim_poly_tab[m-min_m]; + + bch = kzalloc(sizeof(*bch), GFP_KERNEL); + if (bch == NULL) + goto fail; + + bch->m = m; + bch->t = t; + bch->n = (1 << m)-1; + words = DIV_ROUND_UP(m*t, 32); + bch->ecc_bytes = DIV_ROUND_UP(m*t, 8); + bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err); + bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err); + bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err); + bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err); + bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err); + bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err); + bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err); + bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err); + bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err); + + for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) + bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err); + + if (err) + goto fail; + + err = build_gf_tables(bch, prim_poly); + if (err) + goto fail; + + /* use generator polynomial for computing encoding tables */ + genpoly = compute_generator_polynomial(bch); + if (genpoly == NULL) + goto fail; + + build_mod8_tables(bch, genpoly); + kfree(genpoly); + + err = build_deg2_base(bch); + if (err) + goto fail; + + return bch; + +fail: + free_bch(bch); + return NULL; +} +EXPORT_SYMBOL_GPL(init_bch); + +/** + * free_bch - free the BCH control structure + * @bch: BCH control structure to release + */ +void free_bch(struct bch_control *bch) +{ + unsigned int i; + + if (bch) { + kfree(bch->a_pow_tab); + kfree(bch->a_log_tab); + kfree(bch->mod8_tab); + kfree(bch->ecc_buf); + kfree(bch->ecc_buf2); + kfree(bch->xi_tab); + kfree(bch->syn); + kfree(bch->cache); + kfree(bch->elp); + + for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) + kfree(bch->poly_2t[i]); + + kfree(bch); + } +} +EXPORT_SYMBOL_GPL(free_bch); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>"); +MODULE_DESCRIPTION("Binary BCH encoder/decoder"); diff --git a/lib/bitmap.c b/lib/bitmap.c index 741fae905ae3..91e0ccfdb424 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -830,7 +830,7 @@ EXPORT_SYMBOL(bitmap_bitremap); * @orig (i.e. bits 3, 5, 7 and 9) were also set. * * When bit 11 is set in @orig, it means turn on the bit in - * @dst corresponding to whatever is the twelth bit that is + * @dst corresponding to whatever is the twelfth bit that is * turned on in @relmap. In the above example, there were * only ten bits turned on in @relmap (30..39), so that bit * 11 was set in @orig had no affect on @dst. diff --git a/lib/bsearch.c b/lib/bsearch.c new file mode 100644 index 000000000000..5b54758e2afb --- /dev/null +++ b/lib/bsearch.c @@ -0,0 +1,53 @@ +/* + * A generic implementation of binary search for the Linux kernel + * + * Copyright (C) 2008-2009 Ksplice, Inc. + * Author: Tim Abbott <tabbott@ksplice.com> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; version 2. + */ + +#include <linux/module.h> +#include <linux/bsearch.h> + +/* + * bsearch - binary search an array of elements + * @key: pointer to item being searched for + * @base: pointer to first element to search + * @num: number of elements + * @size: size of each element + * @cmp: pointer to comparison function + * + * This function does a binary search on the given array. The + * contents of the array should already be in ascending sorted order + * under the provided comparison function. + * + * Note that the key need not have the same type as the elements in + * the array, e.g. key could be a string and the comparison function + * could compare the string with the struct's name field. However, if + * the key and elements in the array are of the same type, you can use + * the same comparison function for both sort() and bsearch(). + */ +void *bsearch(const void *key, const void *base, size_t num, size_t size, + int (*cmp)(const void *key, const void *elt)) +{ + size_t start = 0, end = num; + int result; + + while (start < end) { + size_t mid = start + (end - start) / 2; + + result = cmp(key, base + mid * size); + if (result < 0) + end = mid; + else if (result > 0) + start = mid + 1; + else + return (void *)base + mid * size; + } + + return NULL; +} +EXPORT_SYMBOL(bsearch); diff --git a/lib/btree.c b/lib/btree.c index c9c6f0351526..2a34392bcecc 100644 --- a/lib/btree.c +++ b/lib/btree.c @@ -11,7 +11,7 @@ * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch * * A relatively simple B+Tree implementation. I have written it as a learning - * excercise to understand how B+Trees work. Turned out to be useful as well. + * exercise to understand how B+Trees work. Turned out to be useful as well. * * B+Trees can be used similar to Linux radix trees (which don't have anything * in common with textbook radix trees, beware). Prerequisite for them working @@ -541,7 +541,7 @@ static void rebalance(struct btree_head *head, struct btree_geo *geo, int i, no_left, no_right; if (fill == 0) { - /* Because we don't steal entries from a neigbour, this case + /* Because we don't steal entries from a neighbour, this case * can happen. Parent node contains a single child, this * node, so merging with a sibling never happens. */ diff --git a/lib/cpu_rmap.c b/lib/cpu_rmap.c new file mode 100644 index 000000000000..987acfafeb83 --- /dev/null +++ b/lib/cpu_rmap.c @@ -0,0 +1,269 @@ +/* + * cpu_rmap.c: CPU affinity reverse-map support + * Copyright 2011 Solarflare Communications Inc. + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 as published + * by the Free Software Foundation, incorporated herein by reference. + */ + +#include <linux/cpu_rmap.h> +#ifdef CONFIG_GENERIC_HARDIRQS +#include <linux/interrupt.h> +#endif +#include <linux/module.h> + +/* + * These functions maintain a mapping from CPUs to some ordered set of + * objects with CPU affinities. This can be seen as a reverse-map of + * CPU affinity. However, we do not assume that the object affinities + * cover all CPUs in the system. For those CPUs not directly covered + * by object affinities, we attempt to find a nearest object based on + * CPU topology. + */ + +/** + * alloc_cpu_rmap - allocate CPU affinity reverse-map + * @size: Number of objects to be mapped + * @flags: Allocation flags e.g. %GFP_KERNEL + */ +struct cpu_rmap *alloc_cpu_rmap(unsigned int size, gfp_t flags) +{ + struct cpu_rmap *rmap; + unsigned int cpu; + size_t obj_offset; + + /* This is a silly number of objects, and we use u16 indices. */ + if (size > 0xffff) + return NULL; + + /* Offset of object pointer array from base structure */ + obj_offset = ALIGN(offsetof(struct cpu_rmap, near[nr_cpu_ids]), + sizeof(void *)); + + rmap = kzalloc(obj_offset + size * sizeof(rmap->obj[0]), flags); + if (!rmap) + return NULL; + + rmap->obj = (void **)((char *)rmap + obj_offset); + + /* Initially assign CPUs to objects on a rota, since we have + * no idea where the objects are. Use infinite distance, so + * any object with known distance is preferable. Include the + * CPUs that are not present/online, since we definitely want + * any newly-hotplugged CPUs to have some object assigned. + */ + for_each_possible_cpu(cpu) { + rmap->near[cpu].index = cpu % size; + rmap->near[cpu].dist = CPU_RMAP_DIST_INF; + } + + rmap->size = size; + return rmap; +} +EXPORT_SYMBOL(alloc_cpu_rmap); + +/* Reevaluate nearest object for given CPU, comparing with the given + * neighbours at the given distance. + */ +static bool cpu_rmap_copy_neigh(struct cpu_rmap *rmap, unsigned int cpu, + const struct cpumask *mask, u16 dist) +{ + int neigh; + + for_each_cpu(neigh, mask) { + if (rmap->near[cpu].dist > dist && + rmap->near[neigh].dist <= dist) { + rmap->near[cpu].index = rmap->near[neigh].index; + rmap->near[cpu].dist = dist; + return true; + } + } + return false; +} + +#ifdef DEBUG +static void debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix) +{ + unsigned index; + unsigned int cpu; + + pr_info("cpu_rmap %p, %s:\n", rmap, prefix); + + for_each_possible_cpu(cpu) { + index = rmap->near[cpu].index; + pr_info("cpu %d -> obj %u (distance %u)\n", + cpu, index, rmap->near[cpu].dist); + } +} +#else +static inline void +debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix) +{ +} +#endif + +/** + * cpu_rmap_add - add object to a rmap + * @rmap: CPU rmap allocated with alloc_cpu_rmap() + * @obj: Object to add to rmap + * + * Return index of object. + */ +int cpu_rmap_add(struct cpu_rmap *rmap, void *obj) +{ + u16 index; + + BUG_ON(rmap->used >= rmap->size); + index = rmap->used++; + rmap->obj[index] = obj; + return index; +} +EXPORT_SYMBOL(cpu_rmap_add); + +/** + * cpu_rmap_update - update CPU rmap following a change of object affinity + * @rmap: CPU rmap to update + * @index: Index of object whose affinity changed + * @affinity: New CPU affinity of object + */ +int cpu_rmap_update(struct cpu_rmap *rmap, u16 index, + const struct cpumask *affinity) +{ + cpumask_var_t update_mask; + unsigned int cpu; + + if (unlikely(!zalloc_cpumask_var(&update_mask, GFP_KERNEL))) + return -ENOMEM; + + /* Invalidate distance for all CPUs for which this used to be + * the nearest object. Mark those CPUs for update. + */ + for_each_online_cpu(cpu) { + if (rmap->near[cpu].index == index) { + rmap->near[cpu].dist = CPU_RMAP_DIST_INF; + cpumask_set_cpu(cpu, update_mask); + } + } + + debug_print_rmap(rmap, "after invalidating old distances"); + + /* Set distance to 0 for all CPUs in the new affinity mask. + * Mark all CPUs within their NUMA nodes for update. + */ + for_each_cpu(cpu, affinity) { + rmap->near[cpu].index = index; + rmap->near[cpu].dist = 0; + cpumask_or(update_mask, update_mask, + cpumask_of_node(cpu_to_node(cpu))); + } + + debug_print_rmap(rmap, "after updating neighbours"); + + /* Update distances based on topology */ + for_each_cpu(cpu, update_mask) { + if (cpu_rmap_copy_neigh(rmap, cpu, + topology_thread_cpumask(cpu), 1)) + continue; + if (cpu_rmap_copy_neigh(rmap, cpu, + topology_core_cpumask(cpu), 2)) + continue; + if (cpu_rmap_copy_neigh(rmap, cpu, + cpumask_of_node(cpu_to_node(cpu)), 3)) + continue; + /* We could continue into NUMA node distances, but for now + * we give up. + */ + } + + debug_print_rmap(rmap, "after copying neighbours"); + + free_cpumask_var(update_mask); + return 0; +} +EXPORT_SYMBOL(cpu_rmap_update); + +#ifdef CONFIG_GENERIC_HARDIRQS + +/* Glue between IRQ affinity notifiers and CPU rmaps */ + +struct irq_glue { + struct irq_affinity_notify notify; + struct cpu_rmap *rmap; + u16 index; +}; + +/** + * free_irq_cpu_rmap - free a CPU affinity reverse-map used for IRQs + * @rmap: Reverse-map allocated with alloc_irq_cpu_map(), or %NULL + * + * Must be called in process context, before freeing the IRQs, and + * without holding any locks required by global workqueue items. + */ +void free_irq_cpu_rmap(struct cpu_rmap *rmap) +{ + struct irq_glue *glue; + u16 index; + + if (!rmap) + return; + + for (index = 0; index < rmap->used; index++) { + glue = rmap->obj[index]; + irq_set_affinity_notifier(glue->notify.irq, NULL); + } + irq_run_affinity_notifiers(); + + kfree(rmap); +} +EXPORT_SYMBOL(free_irq_cpu_rmap); + +static void +irq_cpu_rmap_notify(struct irq_affinity_notify *notify, const cpumask_t *mask) +{ + struct irq_glue *glue = + container_of(notify, struct irq_glue, notify); + int rc; + + rc = cpu_rmap_update(glue->rmap, glue->index, mask); + if (rc) + pr_warning("irq_cpu_rmap_notify: update failed: %d\n", rc); +} + +static void irq_cpu_rmap_release(struct kref *ref) +{ + struct irq_glue *glue = + container_of(ref, struct irq_glue, notify.kref); + kfree(glue); +} + +/** + * irq_cpu_rmap_add - add an IRQ to a CPU affinity reverse-map + * @rmap: The reverse-map + * @irq: The IRQ number + * + * This adds an IRQ affinity notifier that will update the reverse-map + * automatically. + * + * Must be called in process context, after the IRQ is allocated but + * before it is bound with request_irq(). + */ +int irq_cpu_rmap_add(struct cpu_rmap *rmap, int irq) +{ + struct irq_glue *glue = kzalloc(sizeof(*glue), GFP_KERNEL); + int rc; + + if (!glue) + return -ENOMEM; + glue->notify.notify = irq_cpu_rmap_notify; + glue->notify.release = irq_cpu_rmap_release; + glue->rmap = rmap; + glue->index = cpu_rmap_add(rmap, glue); + rc = irq_set_affinity_notifier(irq, &glue->notify); + if (rc) + kfree(glue); + return rc; +} +EXPORT_SYMBOL(irq_cpu_rmap_add); + +#endif /* CONFIG_GENERIC_HARDIRQS */ diff --git a/lib/debugobjects.c b/lib/debugobjects.c index deebcc57d4e6..9d86e45086f5 100644 --- a/lib/debugobjects.c +++ b/lib/debugobjects.c @@ -249,14 +249,17 @@ static struct debug_bucket *get_bucket(unsigned long addr) static void debug_print_object(struct debug_obj *obj, char *msg) { + struct debug_obj_descr *descr = obj->descr; static int limit; - if (limit < 5 && obj->descr != descr_test) { + if (limit < 5 && descr != descr_test) { + void *hint = descr->debug_hint ? + descr->debug_hint(obj->object) : NULL; limit++; WARN(1, KERN_ERR "ODEBUG: %s %s (active state %u) " - "object type: %s\n", + "object type: %s hint: %pS\n", msg, obj_states[obj->state], obj->astate, - obj->descr->name); + descr->name, hint); } debug_objects_warnings++; } diff --git a/lib/decompress_unxz.c b/lib/decompress_unxz.c index cecd23df2b9a..9f34eb56854d 100644 --- a/lib/decompress_unxz.c +++ b/lib/decompress_unxz.c @@ -83,7 +83,7 @@ * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536 * = 128 + (uncompressed_size >> 12) + 65536 * - * For comparision, according to arch/x86/boot/compressed/misc.c, the + * For comparison, according to arch/x86/boot/compressed/misc.c, the * equivalent formula for Deflate is this: * * safety_margin = 18 + (uncompressed_size >> 12) + 32768 diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 4bfb0471f106..db07bfd9298e 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -649,7 +649,7 @@ out_err: return -ENOMEM; } -static int device_dma_allocations(struct device *dev) +static int device_dma_allocations(struct device *dev, struct dma_debug_entry **out_entry) { struct dma_debug_entry *entry; unsigned long flags; @@ -660,8 +660,10 @@ static int device_dma_allocations(struct device *dev) for (i = 0; i < HASH_SIZE; ++i) { spin_lock(&dma_entry_hash[i].lock); list_for_each_entry(entry, &dma_entry_hash[i].list, list) { - if (entry->dev == dev) + if (entry->dev == dev) { count += 1; + *out_entry = entry; + } } spin_unlock(&dma_entry_hash[i].lock); } @@ -674,6 +676,7 @@ static int device_dma_allocations(struct device *dev) static int dma_debug_device_change(struct notifier_block *nb, unsigned long action, void *data) { struct device *dev = data; + struct dma_debug_entry *uninitialized_var(entry); int count; if (global_disable) @@ -681,12 +684,17 @@ static int dma_debug_device_change(struct notifier_block *nb, unsigned long acti switch (action) { case BUS_NOTIFY_UNBOUND_DRIVER: - count = device_dma_allocations(dev); + count = device_dma_allocations(dev, &entry); if (count == 0) break; - err_printk(dev, NULL, "DMA-API: device driver has pending " + err_printk(dev, entry, "DMA-API: device driver has pending " "DMA allocations while released from device " - "[count=%d]\n", count); + "[count=%d]\n" + "One of leaked entries details: " + "[device address=0x%016llx] [size=%llu bytes] " + "[mapped with %s] [mapped as %s]\n", + count, entry->dev_addr, entry->size, + dir2name[entry->direction], type2name[entry->type]); break; default: break; diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c index b335acb43be2..75ca78f3a8c9 100644 --- a/lib/dynamic_debug.c +++ b/lib/dynamic_debug.c @@ -7,6 +7,7 @@ * Copyright (C) 2008 Jason Baron <jbaron@redhat.com> * By Greg Banks <gnb@melbourne.sgi.com> * Copyright (c) 2008 Silicon Graphics Inc. All Rights Reserved. + * Copyright (C) 2011 Bart Van Assche. All Rights Reserved. */ #include <linux/kernel.h> @@ -27,6 +28,8 @@ #include <linux/debugfs.h> #include <linux/slab.h> #include <linux/jump_label.h> +#include <linux/hardirq.h> +#include <linux/sched.h> extern struct _ddebug __start___verbose[]; extern struct _ddebug __stop___verbose[]; @@ -63,15 +66,25 @@ static inline const char *basename(const char *path) return tail ? tail+1 : path; } +static struct { unsigned flag:8; char opt_char; } opt_array[] = { + { _DPRINTK_FLAGS_PRINT, 'p' }, + { _DPRINTK_FLAGS_INCL_MODNAME, 'm' }, + { _DPRINTK_FLAGS_INCL_FUNCNAME, 'f' }, + { _DPRINTK_FLAGS_INCL_LINENO, 'l' }, + { _DPRINTK_FLAGS_INCL_TID, 't' }, +}; + /* format a string into buf[] which describes the _ddebug's flags */ static char *ddebug_describe_flags(struct _ddebug *dp, char *buf, size_t maxlen) { char *p = buf; + int i; BUG_ON(maxlen < 4); - if (dp->flags & _DPRINTK_FLAGS_PRINT) - *p++ = 'p'; + for (i = 0; i < ARRAY_SIZE(opt_array); ++i) + if (dp->flags & opt_array[i].flag) + *p++ = opt_array[i].opt_char; if (p == buf) *p++ = '-'; *p = '\0'; @@ -343,7 +356,7 @@ static int ddebug_parse_flags(const char *str, unsigned int *flagsp, unsigned int *maskp) { unsigned flags = 0; - int op = '='; + int op = '=', i; switch (*str) { case '+': @@ -358,13 +371,14 @@ static int ddebug_parse_flags(const char *str, unsigned int *flagsp, printk(KERN_INFO "%s: op='%c'\n", __func__, op); for ( ; *str ; ++str) { - switch (*str) { - case 'p': - flags |= _DPRINTK_FLAGS_PRINT; - break; - default: - return -EINVAL; + for (i = ARRAY_SIZE(opt_array) - 1; i >= 0; i--) { + if (*str == opt_array[i].opt_char) { + flags |= opt_array[i].flag; + break; + } } + if (i < 0) + return -EINVAL; } if (flags == 0) return -EINVAL; @@ -413,6 +427,35 @@ static int ddebug_exec_query(char *query_string) return 0; } +int __dynamic_pr_debug(struct _ddebug *descriptor, const char *fmt, ...) +{ + va_list args; + int res; + + BUG_ON(!descriptor); + BUG_ON(!fmt); + + va_start(args, fmt); + res = printk(KERN_DEBUG); + if (descriptor->flags & _DPRINTK_FLAGS_INCL_TID) { + if (in_interrupt()) + res += printk(KERN_CONT "<intr> "); + else + res += printk(KERN_CONT "[%d] ", task_pid_vnr(current)); + } + if (descriptor->flags & _DPRINTK_FLAGS_INCL_MODNAME) + res += printk(KERN_CONT "%s:", descriptor->modname); + if (descriptor->flags & _DPRINTK_FLAGS_INCL_FUNCNAME) + res += printk(KERN_CONT "%s:", descriptor->function); + if (descriptor->flags & _DPRINTK_FLAGS_INCL_LINENO) + res += printk(KERN_CONT "%d ", descriptor->lineno); + res += vprintk(fmt, args); + va_end(args); + + return res; +} +EXPORT_SYMBOL(__dynamic_pr_debug); + static __initdata char ddebug_setup_string[1024]; static __init int ddebug_setup_query(char *str) { diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c index 24c59ded47a0..b0a8767282bf 100644 --- a/lib/find_next_bit.c +++ b/lib/find_next_bit.c @@ -160,6 +160,7 @@ EXPORT_SYMBOL(find_first_zero_bit); #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ #ifdef __BIG_ENDIAN +#ifdef CONFIG_GENERIC_FIND_BIT_LE /* include/linux/byteorder does not support "unsigned long" type */ static inline unsigned long ext2_swabp(const unsigned long * x) @@ -185,15 +186,16 @@ static inline unsigned long ext2_swab(const unsigned long y) #endif } -unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned +unsigned long find_next_zero_bit_le(const void *addr, unsigned long size, unsigned long offset) { - const unsigned long *p = addr + BITOP_WORD(offset); + const unsigned long *p = addr; unsigned long result = offset & ~(BITS_PER_LONG - 1); unsigned long tmp; if (offset >= size) return size; + p += BITOP_WORD(offset); size -= result; offset &= (BITS_PER_LONG - 1UL); if (offset) { @@ -226,18 +228,18 @@ found_middle: found_middle_swap: return result + ffz(ext2_swab(tmp)); } +EXPORT_SYMBOL(find_next_zero_bit_le); -EXPORT_SYMBOL(generic_find_next_zero_le_bit); - -unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned +unsigned long find_next_bit_le(const void *addr, unsigned long size, unsigned long offset) { - const unsigned long *p = addr + BITOP_WORD(offset); + const unsigned long *p = addr; unsigned long result = offset & ~(BITS_PER_LONG - 1); unsigned long tmp; if (offset >= size) return size; + p += BITOP_WORD(offset); size -= result; offset &= (BITS_PER_LONG - 1UL); if (offset) { @@ -271,5 +273,7 @@ found_middle: found_middle_swap: return result + __ffs(ext2_swab(tmp)); } -EXPORT_SYMBOL(generic_find_next_le_bit); +EXPORT_SYMBOL(find_next_bit_le); + +#endif /* CONFIG_GENERIC_FIND_BIT_LE */ #endif /* __BIG_ENDIAN */ diff --git a/lib/kernel_lock.c b/lib/kernel_lock.c deleted file mode 100644 index b135d04aa48a..000000000000 --- a/lib/kernel_lock.c +++ /dev/null @@ -1,143 +0,0 @@ -/* - * lib/kernel_lock.c - * - * This is the traditional BKL - big kernel lock. Largely - * relegated to obsolescence, but used by various less - * important (or lazy) subsystems. - */ -#include <linux/module.h> -#include <linux/kallsyms.h> -#include <linux/semaphore.h> -#include <linux/smp_lock.h> - -#define CREATE_TRACE_POINTS -#include <trace/events/bkl.h> - -/* - * The 'big kernel lock' - * - * This spinlock is taken and released recursively by lock_kernel() - * and unlock_kernel(). It is transparently dropped and reacquired - * over schedule(). It is used to protect legacy code that hasn't - * been migrated to a proper locking design yet. - * - * Don't use in new code. - */ -static __cacheline_aligned_in_smp DEFINE_RAW_SPINLOCK(kernel_flag); - - -/* - * Acquire/release the underlying lock from the scheduler. - * - * This is called with preemption disabled, and should - * return an error value if it cannot get the lock and - * TIF_NEED_RESCHED gets set. - * - * If it successfully gets the lock, it should increment - * the preemption count like any spinlock does. - * - * (This works on UP too - do_raw_spin_trylock will never - * return false in that case) - */ -int __lockfunc __reacquire_kernel_lock(void) -{ - while (!do_raw_spin_trylock(&kernel_flag)) { - if (need_resched()) - return -EAGAIN; - cpu_relax(); - } - preempt_disable(); - return 0; -} - -void __lockfunc __release_kernel_lock(void) -{ - do_raw_spin_unlock(&kernel_flag); - preempt_enable_no_resched(); -} - -/* - * These are the BKL spinlocks - we try to be polite about preemption. - * If SMP is not on (ie UP preemption), this all goes away because the - * do_raw_spin_trylock() will always succeed. - */ -#ifdef CONFIG_PREEMPT -static inline void __lock_kernel(void) -{ - preempt_disable(); - if (unlikely(!do_raw_spin_trylock(&kernel_flag))) { - /* - * If preemption was disabled even before this - * was called, there's nothing we can be polite - * about - just spin. - */ - if (preempt_count() > 1) { - do_raw_spin_lock(&kernel_flag); - return; - } - - /* - * Otherwise, let's wait for the kernel lock - * with preemption enabled.. - */ - do { - preempt_enable(); - while (raw_spin_is_locked(&kernel_flag)) - cpu_relax(); - preempt_disable(); - } while (!do_raw_spin_trylock(&kernel_flag)); - } -} - -#else - -/* - * Non-preemption case - just get the spinlock - */ -static inline void __lock_kernel(void) -{ - do_raw_spin_lock(&kernel_flag); -} -#endif - -static inline void __unlock_kernel(void) -{ - /* - * the BKL is not covered by lockdep, so we open-code the - * unlocking sequence (and thus avoid the dep-chain ops): - */ - do_raw_spin_unlock(&kernel_flag); - preempt_enable(); -} - -/* - * Getting the big kernel lock. - * - * This cannot happen asynchronously, so we only need to - * worry about other CPU's. - */ -void __lockfunc _lock_kernel(const char *func, const char *file, int line) -{ - int depth = current->lock_depth + 1; - - trace_lock_kernel(func, file, line); - - if (likely(!depth)) { - might_sleep(); - __lock_kernel(); - } - current->lock_depth = depth; -} - -void __lockfunc _unlock_kernel(const char *func, const char *file, int line) -{ - BUG_ON(current->lock_depth < 0); - if (likely(--current->lock_depth < 0)) - __unlock_kernel(); - - trace_unlock_kernel(func, file, line); -} - -EXPORT_SYMBOL(_lock_kernel); -EXPORT_SYMBOL(_unlock_kernel); - diff --git a/lib/kstrtox.c b/lib/kstrtox.c new file mode 100644 index 000000000000..a235f3cc471c --- /dev/null +++ b/lib/kstrtox.c @@ -0,0 +1,224 @@ +/* + * Convert integer string representation to an integer. + * If an integer doesn't fit into specified type, -E is returned. + * + * Integer starts with optional sign. + * kstrtou*() functions do not accept sign "-". + * + * Radix 0 means autodetection: leading "0x" implies radix 16, + * leading "0" implies radix 8, otherwise radix is 10. + * Autodetection hints work after optional sign, but not before. + * + * If -E is returned, result is not touched. + */ +#include <linux/ctype.h> +#include <linux/errno.h> +#include <linux/kernel.h> +#include <linux/math64.h> +#include <linux/module.h> +#include <linux/types.h> + +static inline char _tolower(const char c) +{ + return c | 0x20; +} + +static int _kstrtoull(const char *s, unsigned int base, unsigned long long *res) +{ + unsigned long long acc; + int ok; + + if (base == 0) { + if (s[0] == '0') { + if (_tolower(s[1]) == 'x' && isxdigit(s[2])) + base = 16; + else + base = 8; + } else + base = 10; + } + if (base == 16 && s[0] == '0' && _tolower(s[1]) == 'x') + s += 2; + + acc = 0; + ok = 0; + while (*s) { + unsigned int val; + + if ('0' <= *s && *s <= '9') + val = *s - '0'; + else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f') + val = _tolower(*s) - 'a' + 10; + else if (*s == '\n' && *(s + 1) == '\0') + break; + else + return -EINVAL; + + if (val >= base) + return -EINVAL; + if (acc > div_u64(ULLONG_MAX - val, base)) + return -ERANGE; + acc = acc * base + val; + ok = 1; + + s++; + } + if (!ok) + return -EINVAL; + *res = acc; + return 0; +} + +int kstrtoull(const char *s, unsigned int base, unsigned long long *res) +{ + if (s[0] == '+') + s++; + return _kstrtoull(s, base, res); +} +EXPORT_SYMBOL(kstrtoull); + +int kstrtoll(const char *s, unsigned int base, long long *res) +{ + unsigned long long tmp; + int rv; + + if (s[0] == '-') { + rv = _kstrtoull(s + 1, base, &tmp); + if (rv < 0) + return rv; + if ((long long)(-tmp) >= 0) + return -ERANGE; + *res = -tmp; + } else { + rv = kstrtoull(s, base, &tmp); + if (rv < 0) + return rv; + if ((long long)tmp < 0) + return -ERANGE; + *res = tmp; + } + return 0; +} +EXPORT_SYMBOL(kstrtoll); + +/* Internal, do not use. */ +int _kstrtoul(const char *s, unsigned int base, unsigned long *res) +{ + unsigned long long tmp; + int rv; + + rv = kstrtoull(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (unsigned long long)(unsigned long)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(_kstrtoul); + +/* Internal, do not use. */ +int _kstrtol(const char *s, unsigned int base, long *res) +{ + long long tmp; + int rv; + + rv = kstrtoll(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (long long)(long)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(_kstrtol); + +int kstrtouint(const char *s, unsigned int base, unsigned int *res) +{ + unsigned long long tmp; + int rv; + + rv = kstrtoull(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (unsigned long long)(unsigned int)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtouint); + +int kstrtoint(const char *s, unsigned int base, int *res) +{ + long long tmp; + int rv; + + rv = kstrtoll(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (long long)(int)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtoint); + +int kstrtou16(const char *s, unsigned int base, u16 *res) +{ + unsigned long long tmp; + int rv; + + rv = kstrtoull(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (unsigned long long)(u16)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtou16); + +int kstrtos16(const char *s, unsigned int base, s16 *res) +{ + long long tmp; + int rv; + + rv = kstrtoll(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (long long)(s16)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtos16); + +int kstrtou8(const char *s, unsigned int base, u8 *res) +{ + unsigned long long tmp; + int rv; + + rv = kstrtoull(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (unsigned long long)(u8)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtou8); + +int kstrtos8(const char *s, unsigned int base, s8 *res) +{ + long long tmp; + int rv; + + rv = kstrtoll(s, base, &tmp); + if (rv < 0) + return rv; + if (tmp != (long long)(s8)tmp) + return -ERANGE; + *res = tmp; + return 0; +} +EXPORT_SYMBOL(kstrtos8); diff --git a/lib/parser.c b/lib/parser.c index 6e89eca5cca0..dcbaaef6cf11 100644 --- a/lib/parser.c +++ b/lib/parser.c @@ -13,7 +13,7 @@ /** * match_one: - Determines if a string matches a simple pattern - * @s: the string to examine for presense of the pattern + * @s: the string to examine for presence of the pattern * @p: the string containing the pattern * @args: array of %MAX_OPT_ARGS &substring_t elements. Used to return match * locations. diff --git a/lib/plist.c b/lib/plist.c index 1471988d9190..0ae7e6431726 100644 --- a/lib/plist.c +++ b/lib/plist.c @@ -28,6 +28,8 @@ #ifdef CONFIG_DEBUG_PI_LIST +static struct plist_head test_head; + static void plist_check_prev_next(struct list_head *t, struct list_head *p, struct list_head *n) { @@ -54,12 +56,13 @@ static void plist_check_list(struct list_head *top) static void plist_check_head(struct plist_head *head) { - WARN_ON(!head->rawlock && !head->spinlock); + WARN_ON(head != &test_head && !head->rawlock && !head->spinlock); if (head->rawlock) WARN_ON_SMP(!raw_spin_is_locked(head->rawlock)); if (head->spinlock) WARN_ON_SMP(!spin_is_locked(head->spinlock)); - plist_check_list(&head->prio_list); + if (!plist_head_empty(head)) + plist_check_list(&plist_first(head)->prio_list); plist_check_list(&head->node_list); } @@ -75,25 +78,33 @@ static void plist_check_head(struct plist_head *head) */ void plist_add(struct plist_node *node, struct plist_head *head) { - struct plist_node *iter; + struct plist_node *first, *iter, *prev = NULL; + struct list_head *node_next = &head->node_list; plist_check_head(head); WARN_ON(!plist_node_empty(node)); + WARN_ON(!list_empty(&node->prio_list)); + + if (plist_head_empty(head)) + goto ins_node; - list_for_each_entry(iter, &head->prio_list, plist.prio_list) { - if (node->prio < iter->prio) - goto lt_prio; - else if (node->prio == iter->prio) { - iter = list_entry(iter->plist.prio_list.next, - struct plist_node, plist.prio_list); - goto eq_prio; + first = iter = plist_first(head); + + do { + if (node->prio < iter->prio) { + node_next = &iter->node_list; + break; } - } -lt_prio: - list_add_tail(&node->plist.prio_list, &iter->plist.prio_list); -eq_prio: - list_add_tail(&node->plist.node_list, &iter->plist.node_list); + prev = iter; + iter = list_entry(iter->prio_list.next, + struct plist_node, prio_list); + } while (iter != first); + + if (!prev || prev->prio != node->prio) + list_add_tail(&node->prio_list, &iter->prio_list); +ins_node: + list_add_tail(&node->node_list, node_next); plist_check_head(head); } @@ -108,14 +119,98 @@ void plist_del(struct plist_node *node, struct plist_head *head) { plist_check_head(head); - if (!list_empty(&node->plist.prio_list)) { - struct plist_node *next = plist_first(&node->plist); + if (!list_empty(&node->prio_list)) { + if (node->node_list.next != &head->node_list) { + struct plist_node *next; + + next = list_entry(node->node_list.next, + struct plist_node, node_list); - list_move_tail(&next->plist.prio_list, &node->plist.prio_list); - list_del_init(&node->plist.prio_list); + /* add the next plist_node into prio_list */ + if (list_empty(&next->prio_list)) + list_add(&next->prio_list, &node->prio_list); + } + list_del_init(&node->prio_list); } - list_del_init(&node->plist.node_list); + list_del_init(&node->node_list); plist_check_head(head); } + +#ifdef CONFIG_DEBUG_PI_LIST +#include <linux/sched.h> +#include <linux/module.h> +#include <linux/init.h> + +static struct plist_node __initdata test_node[241]; + +static void __init plist_test_check(int nr_expect) +{ + struct plist_node *first, *prio_pos, *node_pos; + + if (plist_head_empty(&test_head)) { + BUG_ON(nr_expect != 0); + return; + } + + prio_pos = first = plist_first(&test_head); + plist_for_each(node_pos, &test_head) { + if (nr_expect-- < 0) + break; + if (node_pos == first) + continue; + if (node_pos->prio == prio_pos->prio) { + BUG_ON(!list_empty(&node_pos->prio_list)); + continue; + } + + BUG_ON(prio_pos->prio > node_pos->prio); + BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list); + prio_pos = node_pos; + } + + BUG_ON(nr_expect != 0); + BUG_ON(prio_pos->prio_list.next != &first->prio_list); +} + +static int __init plist_test(void) +{ + int nr_expect = 0, i, loop; + unsigned int r = local_clock(); + + printk(KERN_INFO "start plist test\n"); + plist_head_init(&test_head, NULL); + for (i = 0; i < ARRAY_SIZE(test_node); i++) + plist_node_init(test_node + i, 0); + + for (loop = 0; loop < 1000; loop++) { + r = r * 193939 % 47629; + i = r % ARRAY_SIZE(test_node); + if (plist_node_empty(test_node + i)) { + r = r * 193939 % 47629; + test_node[i].prio = r % 99; + plist_add(test_node + i, &test_head); + nr_expect++; + } else { + plist_del(test_node + i, &test_head); + nr_expect--; + } + plist_test_check(nr_expect); + } + + for (i = 0; i < ARRAY_SIZE(test_node); i++) { + if (plist_node_empty(test_node + i)) + continue; + plist_del(test_node + i, &test_head); + nr_expect--; + plist_test_check(nr_expect); + } + + printk(KERN_INFO "end plist test\n"); + return 0; +} + +module_init(plist_test); + +#endif diff --git a/lib/rwsem.c b/lib/rwsem.c index f236d7cd5cf3..aa7c3052261f 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -222,8 +222,7 @@ rwsem_down_failed_common(struct rw_semaphore *sem, /* * wait for the read lock to be granted */ -asmregparm struct rw_semaphore __sched * -rwsem_down_read_failed(struct rw_semaphore *sem) +struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem) { return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_READ, -RWSEM_ACTIVE_READ_BIAS); @@ -232,8 +231,7 @@ rwsem_down_read_failed(struct rw_semaphore *sem) /* * wait for the write lock to be granted */ -asmregparm struct rw_semaphore __sched * -rwsem_down_write_failed(struct rw_semaphore *sem) +struct rw_semaphore __sched *rwsem_down_write_failed(struct rw_semaphore *sem) { return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_WRITE, -RWSEM_ACTIVE_WRITE_BIAS); @@ -243,7 +241,7 @@ rwsem_down_write_failed(struct rw_semaphore *sem) * handle waking up a waiter on the semaphore * - up_read/up_write has decremented the active part of count if we come here */ -asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) +struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) { unsigned long flags; @@ -263,7 +261,7 @@ asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) * - caller incremented waiting part of count and discovered it still negative * - just wake up any readers at the front of the queue */ -asmregparm struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem) +struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem) { unsigned long flags; diff --git a/lib/show_mem.c b/lib/show_mem.c index fdc77c82f922..90cbe4bb5960 100644 --- a/lib/show_mem.c +++ b/lib/show_mem.c @@ -9,14 +9,14 @@ #include <linux/nmi.h> #include <linux/quicklist.h> -void show_mem(void) +void show_mem(unsigned int filter) { pg_data_t *pgdat; unsigned long total = 0, reserved = 0, shared = 0, nonshared = 0, highmem = 0; printk("Mem-Info:\n"); - show_free_areas(); + __show_free_areas(filter); for_each_online_pgdat(pgdat) { unsigned long i, flags; diff --git a/lib/string.c b/lib/string.c index f71bead1be3e..01fad9b203e1 100644 --- a/lib/string.c +++ b/lib/string.c @@ -535,6 +535,35 @@ bool sysfs_streq(const char *s1, const char *s2) } EXPORT_SYMBOL(sysfs_streq); +/** + * strtobool - convert common user inputs into boolean values + * @s: input string + * @res: result + * + * This routine returns 0 iff the first character is one of 'Yy1Nn0'. + * Otherwise it will return -EINVAL. Value pointed to by res is + * updated upon finding a match. + */ +int strtobool(const char *s, bool *res) +{ + switch (s[0]) { + case 'y': + case 'Y': + case '1': + *res = true; + break; + case 'n': + case 'N': + case '0': + *res = false; + break; + default: + return -EINVAL; + } + return 0; +} +EXPORT_SYMBOL(strtobool); + #ifndef __HAVE_ARCH_MEMSET /** * memset - Fill a region of memory with the given value diff --git a/lib/test-kstrtox.c b/lib/test-kstrtox.c new file mode 100644 index 000000000000..d55769d63cb8 --- /dev/null +++ b/lib/test-kstrtox.c @@ -0,0 +1,739 @@ +#include <linux/init.h> +#include <linux/kernel.h> +#include <linux/module.h> + +#define for_each_test(i, test) \ + for (i = 0; i < sizeof(test) / sizeof(test[0]); i++) + +struct test_fail { + const char *str; + unsigned int base; +}; + +#define DEFINE_TEST_FAIL(test) \ + const struct test_fail test[] __initdata + +#define DECLARE_TEST_OK(type, test_type) \ + test_type { \ + const char *str; \ + unsigned int base; \ + type expected_res; \ + } + +#define DEFINE_TEST_OK(type, test) \ + const type test[] __initdata + +#define TEST_FAIL(fn, type, fmt, test) \ +{ \ + unsigned int i; \ + \ + for_each_test(i, test) { \ + const struct test_fail *t = &test[i]; \ + type tmp; \ + int rv; \ + \ + tmp = 0; \ + rv = fn(t->str, t->base, &tmp); \ + if (rv >= 0) { \ + WARN(1, "str '%s', base %u, expected -E, got %d/" fmt "\n", \ + t->str, t->base, rv, tmp); \ + continue; \ + } \ + } \ +} + +#define TEST_OK(fn, type, fmt, test) \ +{ \ + unsigned int i; \ + \ + for_each_test(i, test) { \ + const typeof(test[0]) *t = &test[i]; \ + type res; \ + int rv; \ + \ + rv = fn(t->str, t->base, &res); \ + if (rv != 0) { \ + WARN(1, "str '%s', base %u, expected 0/" fmt ", got %d\n", \ + t->str, t->base, t->expected_res, rv); \ + continue; \ + } \ + if (res != t->expected_res) { \ + WARN(1, "str '%s', base %u, expected " fmt ", got " fmt "\n", \ + t->str, t->base, t->expected_res, res); \ + continue; \ + } \ + } \ +} + +static void __init test_kstrtoull_ok(void) +{ + DECLARE_TEST_OK(unsigned long long, struct test_ull); + static DEFINE_TEST_OK(struct test_ull, test_ull_ok) = { + {"0", 10, 0ULL}, + {"1", 10, 1ULL}, + {"127", 10, 127ULL}, + {"128", 10, 128ULL}, + {"129", 10, 129ULL}, + {"255", 10, 255ULL}, + {"256", 10, 256ULL}, + {"257", 10, 257ULL}, + {"32767", 10, 32767ULL}, + {"32768", 10, 32768ULL}, + {"32769", 10, 32769ULL}, + {"65535", 10, 65535ULL}, + {"65536", 10, 65536ULL}, + {"65537", 10, 65537ULL}, + {"2147483647", 10, 2147483647ULL}, + {"2147483648", 10, 2147483648ULL}, + {"2147483649", 10, 2147483649ULL}, + {"4294967295", 10, 4294967295ULL}, + {"4294967296", 10, 4294967296ULL}, + {"4294967297", 10, 4294967297ULL}, + {"9223372036854775807", 10, 9223372036854775807ULL}, + {"9223372036854775808", 10, 9223372036854775808ULL}, + {"9223372036854775809", 10, 9223372036854775809ULL}, + {"18446744073709551614", 10, 18446744073709551614ULL}, + {"18446744073709551615", 10, 18446744073709551615ULL}, + + {"00", 8, 00ULL}, + {"01", 8, 01ULL}, + {"0177", 8, 0177ULL}, + {"0200", 8, 0200ULL}, + {"0201", 8, 0201ULL}, + {"0377", 8, 0377ULL}, + {"0400", 8, 0400ULL}, + {"0401", 8, 0401ULL}, + {"077777", 8, 077777ULL}, + {"0100000", 8, 0100000ULL}, + {"0100001", 8, 0100001ULL}, + {"0177777", 8, 0177777ULL}, + {"0200000", 8, 0200000ULL}, + {"0200001", 8, 0200001ULL}, + {"017777777777", 8, 017777777777ULL}, + {"020000000000", 8, 020000000000ULL}, + {"020000000001", 8, 020000000001ULL}, + {"037777777777", 8, 037777777777ULL}, + {"040000000000", 8, 040000000000ULL}, + {"040000000001", 8, 040000000001ULL}, + {"0777777777777777777777", 8, 0777777777777777777777ULL}, + {"01000000000000000000000", 8, 01000000000000000000000ULL}, + {"01000000000000000000001", 8, 01000000000000000000001ULL}, + {"01777777777777777777776", 8, 01777777777777777777776ULL}, + {"01777777777777777777777", 8, 01777777777777777777777ULL}, + + {"0x0", 16, 0x0ULL}, + {"0x1", 16, 0x1ULL}, + {"0x7f", 16, 0x7fULL}, + {"0x80", 16, 0x80ULL}, + {"0x81", 16, 0x81ULL}, + {"0xff", 16, 0xffULL}, + {"0x100", 16, 0x100ULL}, + {"0x101", 16, 0x101ULL}, + {"0x7fff", 16, 0x7fffULL}, + {"0x8000", 16, 0x8000ULL}, + {"0x8001", 16, 0x8001ULL}, + {"0xffff", 16, 0xffffULL}, + {"0x10000", 16, 0x10000ULL}, + {"0x10001", 16, 0x10001ULL}, + {"0x7fffffff", 16, 0x7fffffffULL}, + {"0x80000000", 16, 0x80000000ULL}, + {"0x80000001", 16, 0x80000001ULL}, + {"0xffffffff", 16, 0xffffffffULL}, + {"0x100000000", 16, 0x100000000ULL}, + {"0x100000001", 16, 0x100000001ULL}, + {"0x7fffffffffffffff", 16, 0x7fffffffffffffffULL}, + {"0x8000000000000000", 16, 0x8000000000000000ULL}, + {"0x8000000000000001", 16, 0x8000000000000001ULL}, + {"0xfffffffffffffffe", 16, 0xfffffffffffffffeULL}, + {"0xffffffffffffffff", 16, 0xffffffffffffffffULL}, + + {"0\n", 0, 0ULL}, + }; + TEST_OK(kstrtoull, unsigned long long, "%llu", test_ull_ok); +} + +static void __init test_kstrtoull_fail(void) +{ + static DEFINE_TEST_FAIL(test_ull_fail) = { + {"", 0}, + {"", 8}, + {"", 10}, + {"", 16}, + {"\n", 0}, + {"\n", 8}, + {"\n", 10}, + {"\n", 16}, + {"\n0", 0}, + {"\n0", 8}, + {"\n0", 10}, + {"\n0", 16}, + {"+", 0}, + {"+", 8}, + {"+", 10}, + {"+", 16}, + {"-", 0}, + {"-", 8}, + {"-", 10}, + {"-", 16}, + {"0x", 0}, + {"0x", 16}, + {"0X", 0}, + {"0X", 16}, + {"0 ", 0}, + {"1+", 0}, + {"1-", 0}, + {" 2", 0}, + /* base autodetection */ + {"0x0z", 0}, + {"0z", 0}, + {"a", 0}, + /* digit >= base */ + {"2", 2}, + {"8", 8}, + {"a", 10}, + {"A", 10}, + {"g", 16}, + {"G", 16}, + /* overflow */ + {"10000000000000000000000000000000000000000000000000000000000000000", 2}, + {"2000000000000000000000", 8}, + {"18446744073709551616", 10}, + {"10000000000000000", 16}, + /* negative */ + {"-0", 0}, + {"-0", 8}, + {"-0", 10}, + {"-0", 16}, + {"-1", 0}, + {"-1", 8}, + {"-1", 10}, + {"-1", 16}, + /* sign is first character if any */ + {"-+1", 0}, + {"-+1", 8}, + {"-+1", 10}, + {"-+1", 16}, + /* nothing after \n */ + {"0\n0", 0}, + {"0\n0", 8}, + {"0\n0", 10}, + {"0\n0", 16}, + {"0\n+", 0}, + {"0\n+", 8}, + {"0\n+", 10}, + {"0\n+", 16}, + {"0\n-", 0}, + {"0\n-", 8}, + {"0\n-", 10}, + {"0\n-", 16}, + {"0\n ", 0}, + {"0\n ", 8}, + {"0\n ", 10}, + {"0\n ", 16}, + }; + TEST_FAIL(kstrtoull, unsigned long long, "%llu", test_ull_fail); +} + +static void __init test_kstrtoll_ok(void) +{ + DECLARE_TEST_OK(long long, struct test_ll); + static DEFINE_TEST_OK(struct test_ll, test_ll_ok) = { + {"0", 10, 0LL}, + {"1", 10, 1LL}, + {"127", 10, 127LL}, + {"128", 10, 128LL}, + {"129", 10, 129LL}, + {"255", 10, 255LL}, + {"256", 10, 256LL}, + {"257", 10, 257LL}, + {"32767", 10, 32767LL}, + {"32768", 10, 32768LL}, + {"32769", 10, 32769LL}, + {"65535", 10, 65535LL}, + {"65536", 10, 65536LL}, + {"65537", 10, 65537LL}, + {"2147483647", 10, 2147483647LL}, + {"2147483648", 10, 2147483648LL}, + {"2147483649", 10, 2147483649LL}, + {"4294967295", 10, 4294967295LL}, + {"4294967296", 10, 4294967296LL}, + {"4294967297", 10, 4294967297LL}, + {"9223372036854775807", 10, 9223372036854775807LL}, + + {"-1", 10, -1LL}, + {"-2", 10, -2LL}, + {"-9223372036854775808", 10, LLONG_MIN}, + }; + TEST_OK(kstrtoll, long long, "%lld", test_ll_ok); +} + +static void __init test_kstrtoll_fail(void) +{ + static DEFINE_TEST_FAIL(test_ll_fail) = { + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"-9223372036854775809", 10}, + {"-18446744073709551614", 10}, + {"-18446744073709551615", 10}, + /* negative zero isn't an integer in Linux */ + {"-0", 0}, + {"-0", 8}, + {"-0", 10}, + {"-0", 16}, + /* sign is first character if any */ + {"-+1", 0}, + {"-+1", 8}, + {"-+1", 10}, + {"-+1", 16}, + }; + TEST_FAIL(kstrtoll, long long, "%lld", test_ll_fail); +} + +static void __init test_kstrtou64_ok(void) +{ + DECLARE_TEST_OK(u64, struct test_u64); + static DEFINE_TEST_OK(struct test_u64, test_u64_ok) = { + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + {"32768", 10, 32768}, + {"32769", 10, 32769}, + {"65534", 10, 65534}, + {"65535", 10, 65535}, + {"65536", 10, 65536}, + {"65537", 10, 65537}, + {"2147483646", 10, 2147483646}, + {"2147483647", 10, 2147483647}, + {"2147483648", 10, 2147483648ULL}, + {"2147483649", 10, 2147483649ULL}, + {"4294967294", 10, 4294967294ULL}, + {"4294967295", 10, 4294967295ULL}, + {"4294967296", 10, 4294967296ULL}, + {"4294967297", 10, 4294967297ULL}, + {"9223372036854775806", 10, 9223372036854775806ULL}, + {"9223372036854775807", 10, 9223372036854775807ULL}, + {"9223372036854775808", 10, 9223372036854775808ULL}, + {"9223372036854775809", 10, 9223372036854775809ULL}, + {"18446744073709551614", 10, 18446744073709551614ULL}, + {"18446744073709551615", 10, 18446744073709551615ULL}, + }; + TEST_OK(kstrtou64, u64, "%llu", test_u64_ok); +} + +static void __init test_kstrtou64_fail(void) +{ + static DEFINE_TEST_FAIL(test_u64_fail) = { + {"-2", 10}, + {"-1", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtou64, u64, "%llu", test_u64_fail); +} + +static void __init test_kstrtos64_ok(void) +{ + DECLARE_TEST_OK(s64, struct test_s64); + static DEFINE_TEST_OK(struct test_s64, test_s64_ok) = { + {"-128", 10, -128}, + {"-127", 10, -127}, + {"-1", 10, -1}, + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + {"32768", 10, 32768}, + {"32769", 10, 32769}, + {"65534", 10, 65534}, + {"65535", 10, 65535}, + {"65536", 10, 65536}, + {"65537", 10, 65537}, + {"2147483646", 10, 2147483646}, + {"2147483647", 10, 2147483647}, + {"2147483648", 10, 2147483648LL}, + {"2147483649", 10, 2147483649LL}, + {"4294967294", 10, 4294967294LL}, + {"4294967295", 10, 4294967295LL}, + {"4294967296", 10, 4294967296LL}, + {"4294967297", 10, 4294967297LL}, + {"9223372036854775806", 10, 9223372036854775806LL}, + {"9223372036854775807", 10, 9223372036854775807LL}, + }; + TEST_OK(kstrtos64, s64, "%lld", test_s64_ok); +} + +static void __init test_kstrtos64_fail(void) +{ + static DEFINE_TEST_FAIL(test_s64_fail) = { + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtos64, s64, "%lld", test_s64_fail); +} + +static void __init test_kstrtou32_ok(void) +{ + DECLARE_TEST_OK(u32, struct test_u32); + static DEFINE_TEST_OK(struct test_u32, test_u32_ok) = { + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + {"32768", 10, 32768}, + {"32769", 10, 32769}, + {"65534", 10, 65534}, + {"65535", 10, 65535}, + {"65536", 10, 65536}, + {"65537", 10, 65537}, + {"2147483646", 10, 2147483646}, + {"2147483647", 10, 2147483647}, + {"2147483648", 10, 2147483648U}, + {"2147483649", 10, 2147483649U}, + {"4294967294", 10, 4294967294U}, + {"4294967295", 10, 4294967295U}, + }; + TEST_OK(kstrtou32, u32, "%u", test_u32_ok); +} + +static void __init test_kstrtou32_fail(void) +{ + static DEFINE_TEST_FAIL(test_u32_fail) = { + {"-2", 10}, + {"-1", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtou32, u32, "%u", test_u32_fail); +} + +static void __init test_kstrtos32_ok(void) +{ + DECLARE_TEST_OK(s32, struct test_s32); + static DEFINE_TEST_OK(struct test_s32, test_s32_ok) = { + {"-128", 10, -128}, + {"-127", 10, -127}, + {"-1", 10, -1}, + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + {"32768", 10, 32768}, + {"32769", 10, 32769}, + {"65534", 10, 65534}, + {"65535", 10, 65535}, + {"65536", 10, 65536}, + {"65537", 10, 65537}, + {"2147483646", 10, 2147483646}, + {"2147483647", 10, 2147483647}, + }; + TEST_OK(kstrtos32, s32, "%d", test_s32_ok); +} + +static void __init test_kstrtos32_fail(void) +{ + static DEFINE_TEST_FAIL(test_s32_fail) = { + {"2147483648", 10}, + {"2147483649", 10}, + {"4294967294", 10}, + {"4294967295", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtos32, s32, "%d", test_s32_fail); +} + +static void __init test_kstrtou16_ok(void) +{ + DECLARE_TEST_OK(u16, struct test_u16); + static DEFINE_TEST_OK(struct test_u16, test_u16_ok) = { + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + {"32768", 10, 32768}, + {"32769", 10, 32769}, + {"65534", 10, 65534}, + {"65535", 10, 65535}, + }; + TEST_OK(kstrtou16, u16, "%hu", test_u16_ok); +} + +static void __init test_kstrtou16_fail(void) +{ + static DEFINE_TEST_FAIL(test_u16_fail) = { + {"-2", 10}, + {"-1", 10}, + {"65536", 10}, + {"65537", 10}, + {"2147483646", 10}, + {"2147483647", 10}, + {"2147483648", 10}, + {"2147483649", 10}, + {"4294967294", 10}, + {"4294967295", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtou16, u16, "%hu", test_u16_fail); +} + +static void __init test_kstrtos16_ok(void) +{ + DECLARE_TEST_OK(s16, struct test_s16); + static DEFINE_TEST_OK(struct test_s16, test_s16_ok) = { + {"-130", 10, -130}, + {"-129", 10, -129}, + {"-128", 10, -128}, + {"-127", 10, -127}, + {"-1", 10, -1}, + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + {"256", 10, 256}, + {"257", 10, 257}, + {"32766", 10, 32766}, + {"32767", 10, 32767}, + }; + TEST_OK(kstrtos16, s16, "%hd", test_s16_ok); +} + +static void __init test_kstrtos16_fail(void) +{ + static DEFINE_TEST_FAIL(test_s16_fail) = { + {"32768", 10}, + {"32769", 10}, + {"65534", 10}, + {"65535", 10}, + {"65536", 10}, + {"65537", 10}, + {"2147483646", 10}, + {"2147483647", 10}, + {"2147483648", 10}, + {"2147483649", 10}, + {"4294967294", 10}, + {"4294967295", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtos16, s16, "%hd", test_s16_fail); +} + +static void __init test_kstrtou8_ok(void) +{ + DECLARE_TEST_OK(u8, struct test_u8); + static DEFINE_TEST_OK(struct test_u8, test_u8_ok) = { + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + {"128", 10, 128}, + {"129", 10, 129}, + {"254", 10, 254}, + {"255", 10, 255}, + }; + TEST_OK(kstrtou8, u8, "%hhu", test_u8_ok); +} + +static void __init test_kstrtou8_fail(void) +{ + static DEFINE_TEST_FAIL(test_u8_fail) = { + {"-2", 10}, + {"-1", 10}, + {"256", 10}, + {"257", 10}, + {"32766", 10}, + {"32767", 10}, + {"32768", 10}, + {"32769", 10}, + {"65534", 10}, + {"65535", 10}, + {"65536", 10}, + {"65537", 10}, + {"2147483646", 10}, + {"2147483647", 10}, + {"2147483648", 10}, + {"2147483649", 10}, + {"4294967294", 10}, + {"4294967295", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtou8, u8, "%hhu", test_u8_fail); +} + +static void __init test_kstrtos8_ok(void) +{ + DECLARE_TEST_OK(s8, struct test_s8); + static DEFINE_TEST_OK(struct test_s8, test_s8_ok) = { + {"-128", 10, -128}, + {"-127", 10, -127}, + {"-1", 10, -1}, + {"0", 10, 0}, + {"1", 10, 1}, + {"126", 10, 126}, + {"127", 10, 127}, + }; + TEST_OK(kstrtos8, s8, "%hhd", test_s8_ok); +} + +static void __init test_kstrtos8_fail(void) +{ + static DEFINE_TEST_FAIL(test_s8_fail) = { + {"-130", 10}, + {"-129", 10}, + {"128", 10}, + {"129", 10}, + {"254", 10}, + {"255", 10}, + {"256", 10}, + {"257", 10}, + {"32766", 10}, + {"32767", 10}, + {"32768", 10}, + {"32769", 10}, + {"65534", 10}, + {"65535", 10}, + {"65536", 10}, + {"65537", 10}, + {"2147483646", 10}, + {"2147483647", 10}, + {"2147483648", 10}, + {"2147483649", 10}, + {"4294967294", 10}, + {"4294967295", 10}, + {"4294967296", 10}, + {"4294967297", 10}, + {"9223372036854775806", 10}, + {"9223372036854775807", 10}, + {"9223372036854775808", 10}, + {"9223372036854775809", 10}, + {"18446744073709551614", 10}, + {"18446744073709551615", 10}, + {"18446744073709551616", 10}, + {"18446744073709551617", 10}, + }; + TEST_FAIL(kstrtos8, s8, "%hhd", test_s8_fail); +} + +static int __init test_kstrtox_init(void) +{ + test_kstrtoull_ok(); + test_kstrtoull_fail(); + test_kstrtoll_ok(); + test_kstrtoll_fail(); + + test_kstrtou64_ok(); + test_kstrtou64_fail(); + test_kstrtos64_ok(); + test_kstrtos64_fail(); + + test_kstrtou32_ok(); + test_kstrtou32_fail(); + test_kstrtos32_ok(); + test_kstrtos32_fail(); + + test_kstrtou16_ok(); + test_kstrtou16_fail(); + test_kstrtos16_ok(); + test_kstrtos16_fail(); + + test_kstrtou8_ok(); + test_kstrtou8_fail(); + test_kstrtos8_ok(); + test_kstrtos8_fail(); + return -EINVAL; +} +module_init(test_kstrtox_init); +MODULE_LICENSE("Dual BSD/GPL"); diff --git a/lib/timerqueue.c b/lib/timerqueue.c index e3a1050e6820..191176a43e9a 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -5,7 +5,7 @@ * Uses rbtrees for quick list adds and expiration. * * NOTE: All of the following functions need to be serialized - * to avoid races. No locking is done by this libary code. + * to avoid races. No locking is done by this library code. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by diff --git a/lib/vsprintf.c b/lib/vsprintf.c index d3023df8477f..1d659d7bb0f8 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -120,147 +120,6 @@ long long simple_strtoll(const char *cp, char **endp, unsigned int base) } EXPORT_SYMBOL(simple_strtoll); -/** - * strict_strtoul - convert a string to an unsigned long strictly - * @cp: The string to be converted - * @base: The number base to use - * @res: The converted result value - * - * strict_strtoul converts a string to an unsigned long only if the - * string is really an unsigned long string, any string containing - * any invalid char at the tail will be rejected and -EINVAL is returned, - * only a newline char at the tail is acceptible because people generally - * change a module parameter in the following way: - * - * echo 1024 > /sys/module/e1000/parameters/copybreak - * - * echo will append a newline to the tail. - * - * It returns 0 if conversion is successful and *res is set to the converted - * value, otherwise it returns -EINVAL and *res is set to 0. - * - * simple_strtoul just ignores the successive invalid characters and - * return the converted value of prefix part of the string. - */ -int strict_strtoul(const char *cp, unsigned int base, unsigned long *res) -{ - char *tail; - unsigned long val; - - *res = 0; - if (!*cp) - return -EINVAL; - - val = simple_strtoul(cp, &tail, base); - if (tail == cp) - return -EINVAL; - - if ((tail[0] == '\0') || (tail[0] == '\n' && tail[1] == '\0')) { - *res = val; - return 0; - } - - return -EINVAL; -} -EXPORT_SYMBOL(strict_strtoul); - -/** - * strict_strtol - convert a string to a long strictly - * @cp: The string to be converted - * @base: The number base to use - * @res: The converted result value - * - * strict_strtol is similiar to strict_strtoul, but it allows the first - * character of a string is '-'. - * - * It returns 0 if conversion is successful and *res is set to the converted - * value, otherwise it returns -EINVAL and *res is set to 0. - */ -int strict_strtol(const char *cp, unsigned int base, long *res) -{ - int ret; - if (*cp == '-') { - ret = strict_strtoul(cp + 1, base, (unsigned long *)res); - if (!ret) - *res = -(*res); - } else { - ret = strict_strtoul(cp, base, (unsigned long *)res); - } - - return ret; -} -EXPORT_SYMBOL(strict_strtol); - -/** - * strict_strtoull - convert a string to an unsigned long long strictly - * @cp: The string to be converted - * @base: The number base to use - * @res: The converted result value - * - * strict_strtoull converts a string to an unsigned long long only if the - * string is really an unsigned long long string, any string containing - * any invalid char at the tail will be rejected and -EINVAL is returned, - * only a newline char at the tail is acceptible because people generally - * change a module parameter in the following way: - * - * echo 1024 > /sys/module/e1000/parameters/copybreak - * - * echo will append a newline to the tail of the string. - * - * It returns 0 if conversion is successful and *res is set to the converted - * value, otherwise it returns -EINVAL and *res is set to 0. - * - * simple_strtoull just ignores the successive invalid characters and - * return the converted value of prefix part of the string. - */ -int strict_strtoull(const char *cp, unsigned int base, unsigned long long *res) -{ - char *tail; - unsigned long long val; - - *res = 0; - if (!*cp) - return -EINVAL; - - val = simple_strtoull(cp, &tail, base); - if (tail == cp) - return -EINVAL; - if ((tail[0] == '\0') || (tail[0] == '\n' && tail[1] == '\0')) { - *res = val; - return 0; - } - - return -EINVAL; -} -EXPORT_SYMBOL(strict_strtoull); - -/** - * strict_strtoll - convert a string to a long long strictly - * @cp: The string to be converted - * @base: The number base to use - * @res: The converted result value - * - * strict_strtoll is similiar to strict_strtoull, but it allows the first - * character of a string is '-'. - * - * It returns 0 if conversion is successful and *res is set to the converted - * value, otherwise it returns -EINVAL and *res is set to 0. - */ -int strict_strtoll(const char *cp, unsigned int base, long long *res) -{ - int ret; - if (*cp == '-') { - ret = strict_strtoull(cp + 1, base, (unsigned long long *)res); - if (!ret) - *res = -(*res); - } else { - ret = strict_strtoull(cp, base, (unsigned long long *)res); - } - - return ret; -} -EXPORT_SYMBOL(strict_strtoll); - static noinline_for_stack int skip_atoi(const char **s) { @@ -574,7 +433,9 @@ char *symbol_string(char *buf, char *end, void *ptr, unsigned long value = (unsigned long) ptr; #ifdef CONFIG_KALLSYMS char sym[KSYM_SYMBOL_LEN]; - if (ext != 'f' && ext != 's') + if (ext == 'B') + sprint_backtrace(sym, value); + else if (ext != 'f' && ext != 's') sprint_symbol(sym, value); else kallsyms_lookup(value, NULL, NULL, NULL, sym); @@ -936,7 +797,7 @@ char *uuid_string(char *buf, char *end, const u8 *addr, return string(buf, end, uuid, spec); } -int kptr_restrict = 1; +int kptr_restrict __read_mostly; /* * Show a '%p' thing. A kernel extension is that the '%p' is followed @@ -949,6 +810,7 @@ int kptr_restrict = 1; * - 'f' For simple symbolic function names without offset * - 'S' For symbolic direct pointers with offset * - 's' For symbolic direct pointers without offset + * - 'B' For backtraced symbolic direct pointers with offset * - 'R' For decoded struct resource, e.g., [mem 0x0-0x1f 64bit pref] * - 'r' For raw struct resource, e.g., [mem 0x0-0x1f flags 0x201] * - 'M' For a 6-byte MAC address, it prints the address in the @@ -991,7 +853,7 @@ static noinline_for_stack char *pointer(const char *fmt, char *buf, char *end, void *ptr, struct printf_spec spec) { - if (!ptr) { + if (!ptr && *fmt != 'K') { /* * Print (null) with the same width as a pointer so it makes * tabular output look nice. @@ -1008,6 +870,7 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, /* Fallthrough */ case 'S': case 's': + case 'B': return symbol_string(buf, end, ptr, spec, *fmt); case 'R': case 'r': @@ -1047,16 +910,12 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, if (spec.field_width == -1) spec.field_width = 2 * sizeof(void *); return string(buf, end, "pK-error", spec); - } else if ((kptr_restrict == 0) || - (kptr_restrict == 1 && - has_capability_noaudit(current, CAP_SYSLOG))) - break; - - if (spec.field_width == -1) { - spec.field_width = 2 * sizeof(void *); - spec.flags |= ZEROPAD; } - return number(buf, end, 0, spec); + if (!((kptr_restrict == 0) || + (kptr_restrict == 1 && + has_capability_noaudit(current, CAP_SYSLOG)))) + ptr = NULL; + break; } spec.flags |= SMALL; if (spec.field_width == -1) { @@ -1279,6 +1138,7 @@ qualifier: * %ps output the name of a text symbol without offset * %pF output the name of a function pointer with its offset * %pf output the name of a function pointer without its offset + * %pB output the name of a backtrace symbol with its offset * %pR output the address range in a struct resource with decoded flags * %pr output the address range in a struct resource with raw flags * %pM output a 6-byte MAC address with colons @@ -1301,8 +1161,7 @@ qualifier: * return is greater than or equal to @size, the resulting * string is truncated. * - * Call this function if you are already dealing with a va_list. - * You probably want snprintf() instead. + * If you're not already dealing with a va_list consider using snprintf(). */ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) { @@ -1476,8 +1335,7 @@ EXPORT_SYMBOL(vsnprintf); * the @buf not including the trailing '\0'. If @size is == 0 the function * returns 0. * - * Call this function if you are already dealing with a va_list. - * You probably want scnprintf() instead. + * If you're not already dealing with a va_list consider using scnprintf(). * * See the vsnprintf() documentation for format string extensions over C99. */ @@ -1556,8 +1414,7 @@ EXPORT_SYMBOL(scnprintf); * into @buf. Use vsnprintf() or vscnprintf() in order to avoid * buffer overflows. * - * Call this function if you are already dealing with a va_list. - * You probably want sprintf() instead. + * If you're not already dealing with a va_list consider using sprintf(). * * See the vsnprintf() documentation for format string extensions over C99. */ diff --git a/lib/xz/xz_dec_lzma2.c b/lib/xz/xz_dec_lzma2.c index ea5fa4fe9d67..a6cdc969ea42 100644 --- a/lib/xz/xz_dec_lzma2.c +++ b/lib/xz/xz_dec_lzma2.c @@ -969,6 +969,9 @@ XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, */ tmp = b->in[b->in_pos++]; + if (tmp == 0x00) + return XZ_STREAM_END; + if (tmp >= 0xE0 || tmp == 0x01) { s->lzma2.need_props = true; s->lzma2.need_dict_reset = false; @@ -1001,9 +1004,6 @@ XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, lzma_reset(s); } } else { - if (tmp == 0x00) - return XZ_STREAM_END; - if (tmp > 0x02) return XZ_DATA_ERROR; diff --git a/lib/zlib_deflate/deflate.c b/lib/zlib_deflate/deflate.c index 46a31e5f49c3..d63381e8e333 100644 --- a/lib/zlib_deflate/deflate.c +++ b/lib/zlib_deflate/deflate.c @@ -176,6 +176,7 @@ int zlib_deflateInit2( deflate_state *s; int noheader = 0; deflate_workspace *mem; + char *next; ush *overlay; /* We overlay pending_buf and d_buf+l_buf. This works since the average @@ -199,6 +200,21 @@ int zlib_deflateInit2( strategy < 0 || strategy > Z_HUFFMAN_ONLY) { return Z_STREAM_ERROR; } + + /* + * Direct the workspace's pointers to the chunks that were allocated + * along with the deflate_workspace struct. + */ + next = (char *) mem; + next += sizeof(*mem); + mem->window_memory = (Byte *) next; + next += zlib_deflate_window_memsize(windowBits); + mem->prev_memory = (Pos *) next; + next += zlib_deflate_prev_memsize(windowBits); + mem->head_memory = (Pos *) next; + next += zlib_deflate_head_memsize(memLevel); + mem->overlay_memory = next; + s = (deflate_state *) &(mem->deflate_memory); strm->state = (struct internal_state *)s; s->strm = strm; @@ -1247,7 +1263,18 @@ static block_state deflate_slow( return flush == Z_FINISH ? finish_done : block_done; } -int zlib_deflate_workspacesize(void) +int zlib_deflate_workspacesize(int windowBits, int memLevel) { - return sizeof(deflate_workspace); + if (windowBits < 0) /* undocumented feature: suppress zlib header */ + windowBits = -windowBits; + + /* Since the return value is typically passed to vmalloc() unchecked... */ + BUG_ON(memLevel < 1 || memLevel > MAX_MEM_LEVEL || windowBits < 9 || + windowBits > 15); + + return sizeof(deflate_workspace) + + zlib_deflate_window_memsize(windowBits) + + zlib_deflate_prev_memsize(windowBits) + + zlib_deflate_head_memsize(memLevel) + + zlib_deflate_overlay_memsize(memLevel); } diff --git a/lib/zlib_deflate/defutil.h b/lib/zlib_deflate/defutil.h index 6b15a909ca3f..b640b6402e99 100644 --- a/lib/zlib_deflate/defutil.h +++ b/lib/zlib_deflate/defutil.h @@ -241,12 +241,21 @@ typedef struct deflate_state { typedef struct deflate_workspace { /* State memory for the deflator */ deflate_state deflate_memory; - Byte window_memory[2 * (1 << MAX_WBITS)]; - Pos prev_memory[1 << MAX_WBITS]; - Pos head_memory[1 << (MAX_MEM_LEVEL + 7)]; - char overlay_memory[(1 << (MAX_MEM_LEVEL + 6)) * (sizeof(ush)+2)]; + Byte *window_memory; + Pos *prev_memory; + Pos *head_memory; + char *overlay_memory; } deflate_workspace; +#define zlib_deflate_window_memsize(windowBits) \ + (2 * (1 << (windowBits)) * sizeof(Byte)) +#define zlib_deflate_prev_memsize(windowBits) \ + ((1 << (windowBits)) * sizeof(Pos)) +#define zlib_deflate_head_memsize(memLevel) \ + ((1 << ((memLevel)+7)) * sizeof(Pos)) +#define zlib_deflate_overlay_memsize(memLevel) \ + ((1 << ((memLevel)+6)) * (sizeof(ush)+2)) + /* Output a byte on the stream. * IN assertion: there is enough room in pending_buf. */ |