aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig55
-rw-r--r--lib/Kconfig.debug105
-rw-r--r--lib/Makefile10
-rw-r--r--lib/bch.c1368
-rw-r--r--lib/bitmap.c2
-rw-r--r--lib/bsearch.c53
-rw-r--r--lib/btree.c4
-rw-r--r--lib/cpu_rmap.c269
-rw-r--r--lib/debugobjects.c9
-rw-r--r--lib/decompress_unxz.c2
-rw-r--r--lib/dma-debug.c18
-rw-r--r--lib/dynamic_debug.c61
-rw-r--r--lib/find_next_bit.c18
-rw-r--r--lib/kernel_lock.c143
-rw-r--r--lib/kstrtox.c224
-rw-r--r--lib/parser.c2
-rw-r--r--lib/plist.c135
-rw-r--r--lib/rwsem.c10
-rw-r--r--lib/show_mem.c4
-rw-r--r--lib/string.c29
-rw-r--r--lib/test-kstrtox.c739
-rw-r--r--lib/timerqueue.c2
-rw-r--r--lib/vsprintf.c175
-rw-r--r--lib/xz/xz_dec_lzma2.c6
-rw-r--r--lib/zlib_deflate/deflate.c31
-rw-r--r--lib/zlib_deflate/defutil.h17
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
22config GENERIC_FIND_NEXT_BIT 22config GENERIC_FIND_NEXT_BIT
23 bool 23 bool
24 24
25config GENERIC_FIND_BIT_LE
26 bool
27
25config GENERIC_FIND_LAST_BIT 28config GENERIC_FIND_LAST_BIT
26 bool 29 bool
27 default y 30 default y
@@ -155,6 +158,45 @@ config REED_SOLOMON_DEC16
155 boolean 158 boolean
156 159
157# 160#
161# BCH support is selected if needed
162#
163config BCH
164 tristate
165
166config BCH_CONST_PARAMS
167 boolean
168 help
169 Drivers may select this option to force specific constant
170 values for parameters 'm' (Galois field order) and 't'
171 (error correction capability). Those specific values must
172 be set by declaring default values for symbols BCH_CONST_M
173 and BCH_CONST_T.
174 Doing so will enable extra compiler optimizations,
175 improving encoding and decoding performance up to 2x for
176 usual (m,t) values (typically such that m*t < 200).
177 When this option is selected, the BCH library supports
178 only a single (m,t) configuration. This is mainly useful
179 for NAND flash board drivers requiring known, fixed BCH
180 parameters.
181
182config BCH_CONST_M
183 int
184 range 5 15
185 help
186 Constant value for Galois field order 'm'. If 'k' is the
187 number of data bits to protect, 'm' should be chosen such
188 that (k + m*t) <= 2**m - 1.
189 Drivers should declare a default value for this symbol if
190 they select option BCH_CONST_PARAMS.
191
192config BCH_CONST_T
193 int
194 help
195 Constant value for error correction capability in bits 't'.
196 Drivers should declare a default value for this symbol if
197 they select option BCH_CONST_PARAMS.
198
199#
158# Textsearch support is select'ed if needed 200# Textsearch support is select'ed if needed
159# 201#
160config TEXTSEARCH 202config TEXTSEARCH
@@ -201,6 +243,10 @@ config DISABLE_OBSOLETE_CPUMASK_FUNCTIONS
201 bool "Disable obsolete cpumask functions" if DEBUG_PER_CPU_MAPS 243 bool "Disable obsolete cpumask functions" if DEBUG_PER_CPU_MAPS
202 depends on EXPERIMENTAL && BROKEN 244 depends on EXPERIMENTAL && BROKEN
203 245
246config CPU_RMAP
247 bool
248 depends on SMP
249
204# 250#
205# Netlink attribute parsing support is select'ed if needed 251# Netlink attribute parsing support is select'ed if needed
206# 252#
@@ -217,6 +263,13 @@ config LRU_CACHE
217 tristate 263 tristate
218 264
219config AVERAGE 265config AVERAGE
220 bool 266 bool "Averaging functions"
267 help
268 This option is provided for the case where no in-kernel-tree
269 modules require averaging functions, but a module built outside
270 the kernel tree does. Such modules that use library averaging
271 functions require Y here.
272
273 If unsure, say N.
221 274
222endmenu 275endmenu
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
7 included in printk output. This allows you to measure 7 included in printk output. This allows you to measure
8 the interval between kernel operations, including bootup 8 the interval between kernel operations, including bootup
9 operations. This is useful for identifying long delays 9 operations. This is useful for identifying long delays
10 in kernel startup. 10 in kernel startup. Or add printk.time=1 at boot-time.
11 See Documentation/kernel-parameters.txt
12
13config DEFAULT_MESSAGE_LOGLEVEL
14 int "Default message log level (1-7)"
15 range 1 7
16 default "4"
17 help
18 Default log level for printk statements with no specified priority.
19
20 This was hard-coded to KERN_WARNING since at least 2.6.10 but folks
21 that are auditing their logs closely may want to set it to a lower
22 priority.
11 23
12config ENABLE_WARN_DEPRECATED 24config ENABLE_WARN_DEPRECATED
13 bool "Enable __deprecated logic" 25 bool "Enable __deprecated logic"
@@ -102,11 +114,6 @@ config HEADERS_CHECK
102 114
103config DEBUG_SECTION_MISMATCH 115config DEBUG_SECTION_MISMATCH
104 bool "Enable full Section mismatch analysis" 116 bool "Enable full Section mismatch analysis"
105 depends on UNDEFINED || (BLACKFIN)
106 default y
107 # This option is on purpose disabled for now.
108 # It will be enabled when we are down to a reasonable number
109 # of section mismatch warnings (< 10 for an allyesconfig build)
110 help 117 help
111 The section mismatch analysis checks if there are illegal 118 The section mismatch analysis checks if there are illegal
112 references from one section to another section. 119 references from one section to another section.
@@ -176,6 +183,23 @@ config HARDLOCKUP_DETECTOR
176 def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \ 183 def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \
177 !ARCH_HAS_NMI_WATCHDOG 184 !ARCH_HAS_NMI_WATCHDOG
178 185
186config BOOTPARAM_HARDLOCKUP_PANIC
187 bool "Panic (Reboot) On Hard Lockups"
188 depends on LOCKUP_DETECTOR
189 help
190 Say Y here to enable the kernel to panic on "hard lockups",
191 which are bugs that cause the kernel to loop in kernel
192 mode with interrupts disabled for more than 60 seconds.
193
194 Say N if unsure.
195
196config BOOTPARAM_HARDLOCKUP_PANIC_VALUE
197 int
198 depends on LOCKUP_DETECTOR
199 range 0 1
200 default 0 if !BOOTPARAM_HARDLOCKUP_PANIC
201 default 1 if BOOTPARAM_HARDLOCKUP_PANIC
202
179config BOOTPARAM_SOFTLOCKUP_PANIC 203config BOOTPARAM_SOFTLOCKUP_PANIC
180 bool "Panic (Reboot) On Soft Lockups" 204 bool "Panic (Reboot) On Soft Lockups"
181 depends on LOCKUP_DETECTOR 205 depends on LOCKUP_DETECTOR
@@ -215,6 +239,21 @@ config DETECT_HUNG_TASK
215 enabled then all held locks will also be reported. This 239 enabled then all held locks will also be reported. This
216 feature has negligible overhead. 240 feature has negligible overhead.
217 241
242config DEFAULT_HUNG_TASK_TIMEOUT
243 int "Default timeout for hung task detection (in seconds)"
244 depends on DETECT_HUNG_TASK
245 default 120
246 help
247 This option controls the default timeout (in seconds) used
248 to determine when a task has become non-responsive and should
249 be considered hung.
250
251 It can be adjusted at runtime via the kernel.hung_task_timeout
252 sysctl or by writing a value to /proc/sys/kernel/hung_task_timeout.
253
254 A timeout of 0 disables the check. The default is two minutes.
255 Keeping the default should be fine in most cases.
256
218config BOOTPARAM_HUNG_TASK_PANIC 257config BOOTPARAM_HUNG_TASK_PANIC
219 bool "Panic (Reboot) On Hung Tasks" 258 bool "Panic (Reboot) On Hung Tasks"
220 depends on DETECT_HUNG_TASK 259 depends on DETECT_HUNG_TASK
@@ -314,7 +353,7 @@ config DEBUG_OBJECTS_WORK
314 353
315config DEBUG_OBJECTS_RCU_HEAD 354config DEBUG_OBJECTS_RCU_HEAD
316 bool "Debug RCU callbacks objects" 355 bool "Debug RCU callbacks objects"
317 depends on DEBUG_OBJECTS && PREEMPT 356 depends on DEBUG_OBJECTS
318 help 357 help
319 Enable this to turn on debugging of RCU list heads (call_rcu() usage). 358 Enable this to turn on debugging of RCU list heads (call_rcu() usage).
320 359
@@ -375,9 +414,9 @@ config SLUB_STATS
375config DEBUG_KMEMLEAK 414config DEBUG_KMEMLEAK
376 bool "Kernel memory leak detector" 415 bool "Kernel memory leak detector"
377 depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \ 416 depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \
378 (X86 || ARM || PPC || S390 || SPARC64 || SUPERH || MICROBLAZE || TILE) 417 (X86 || ARM || PPC || MIPS || S390 || SPARC64 || SUPERH || MICROBLAZE || TILE)
379 418
380 select DEBUG_FS if SYSFS 419 select DEBUG_FS
381 select STACKTRACE if STACKTRACE_SUPPORT 420 select STACKTRACE if STACKTRACE_SUPPORT
382 select KALLSYMS 421 select KALLSYMS
383 select CRC32 422 select CRC32
@@ -411,11 +450,9 @@ config DEBUG_KMEMLEAK_EARLY_LOG_SIZE
411 450
412config DEBUG_KMEMLEAK_TEST 451config DEBUG_KMEMLEAK_TEST
413 tristate "Simple test for the kernel memory leak detector" 452 tristate "Simple test for the kernel memory leak detector"
414 depends on DEBUG_KMEMLEAK 453 depends on DEBUG_KMEMLEAK && m
415 help 454 help
416 Say Y or M here to build a test for the kernel memory leak 455 This option enables a module that explicitly leaks memory.
417 detector. This option enables a module that explicitly leaks
418 memory.
419 456
420 If unsure, say N. 457 If unsure, say N.
421 458
@@ -470,15 +507,6 @@ config DEBUG_MUTEXES
470 This feature allows mutex semantics violations to be detected and 507 This feature allows mutex semantics violations to be detected and
471 reported. 508 reported.
472 509
473config BKL
474 bool "Big Kernel Lock" if (SMP || PREEMPT)
475 default y
476 help
477 This is the traditional lock that is used in old code instead
478 of proper locking. All drivers that use the BKL should depend
479 on this symbol.
480 Say Y here unless you are working on removing the BKL.
481
482config DEBUG_LOCK_ALLOC 510config DEBUG_LOCK_ALLOC
483 bool "Lock debugging: detect incorrect freeing of live locks" 511 bool "Lock debugging: detect incorrect freeing of live locks"
484 depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT 512 depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
@@ -863,22 +891,9 @@ config RCU_TORTURE_TEST_RUNNABLE
863 Say N here if you want the RCU torture tests to start only 891 Say N here if you want the RCU torture tests to start only
864 after being manually enabled via /proc. 892 after being manually enabled via /proc.
865 893
866config RCU_CPU_STALL_DETECTOR
867 bool "Check for stalled CPUs delaying RCU grace periods"
868 depends on TREE_RCU || TREE_PREEMPT_RCU
869 default y
870 help
871 This option causes RCU to printk information on which
872 CPUs are delaying the current grace period, but only when
873 the grace period extends for excessive time periods.
874
875 Say N if you want to disable such checks.
876
877 Say Y if you are unsure.
878
879config RCU_CPU_STALL_TIMEOUT 894config RCU_CPU_STALL_TIMEOUT
880 int "RCU CPU stall timeout in seconds" 895 int "RCU CPU stall timeout in seconds"
881 depends on RCU_CPU_STALL_DETECTOR 896 depends on TREE_RCU || TREE_PREEMPT_RCU
882 range 3 300 897 range 3 300
883 default 60 898 default 60
884 help 899 help
@@ -887,22 +902,9 @@ config RCU_CPU_STALL_TIMEOUT
887 RCU grace period persists, additional CPU stall warnings are 902 RCU grace period persists, additional CPU stall warnings are
888 printed at more widely spaced intervals. 903 printed at more widely spaced intervals.
889 904
890config RCU_CPU_STALL_DETECTOR_RUNNABLE
891 bool "RCU CPU stall checking starts automatically at boot"
892 depends on RCU_CPU_STALL_DETECTOR
893 default y
894 help
895 If set, start checking for RCU CPU stalls immediately on
896 boot. Otherwise, RCU CPU stall checking must be manually
897 enabled.
898
899 Say Y if you are unsure.
900
901 Say N if you wish to suppress RCU CPU stall checking during boot.
902
903config RCU_CPU_STALL_VERBOSE 905config RCU_CPU_STALL_VERBOSE
904 bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR" 906 bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR"
905 depends on RCU_CPU_STALL_DETECTOR && TREE_PREEMPT_RCU 907 depends on TREE_PREEMPT_RCU
906 default y 908 default y
907 help 909 help
908 This option causes RCU to printk detailed per-task information 910 This option causes RCU to printk detailed per-task information
@@ -1236,3 +1238,6 @@ source "samples/Kconfig"
1236source "lib/Kconfig.kgdb" 1238source "lib/Kconfig.kgdb"
1237 1239
1238source "lib/Kconfig.kmemcheck" 1240source "lib/Kconfig.kmemcheck"
1241
1242config TEST_KSTRTOX
1243 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
21 21
22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ 22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ 23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o 24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
25 bsearch.o
26obj-y += kstrtox.o
27obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
25 28
26ifeq ($(CONFIG_DEBUG_KOBJECT),y) 29ifeq ($(CONFIG_DEBUG_KOBJECT),y)
27CFLAGS_kobject.o += -DDEBUG 30CFLAGS_kobject.o += -DDEBUG
@@ -38,12 +41,12 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
38lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o 41lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
39lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o 42lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o
40lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o 43lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
44lib-$(CONFIG_GENERIC_FIND_BIT_LE) += find_next_bit.o
41obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o 45obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o
42 46
43CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS)) 47CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
44obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o 48obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
45 49
46obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
47obj-$(CONFIG_BTREE) += btree.o 50obj-$(CONFIG_BTREE) += btree.o
48obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o 51obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
49obj-$(CONFIG_DEBUG_LIST) += list_debug.o 52obj-$(CONFIG_DEBUG_LIST) += list_debug.o
@@ -67,6 +70,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
67obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ 70obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
68obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ 71obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
69obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ 72obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
73obj-$(CONFIG_BCH) += bch.o
70obj-$(CONFIG_LZO_COMPRESS) += lzo/ 74obj-$(CONFIG_LZO_COMPRESS) += lzo/
71obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ 75obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
72obj-$(CONFIG_XZ_DEC) += xz/ 76obj-$(CONFIG_XZ_DEC) += xz/
@@ -110,6 +114,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
110 114
111obj-$(CONFIG_AVERAGE) += average.o 115obj-$(CONFIG_AVERAGE) += average.o
112 116
117obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
118
113hostprogs-y := gen_crc32table 119hostprogs-y := gen_crc32table
114clean-files := crc32table.h 120clean-files := crc32table.h
115 121
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 @@
1/*
2 * Generic binary BCH encoding/decoding library
3 *
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 as published by
6 * the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
11 * more details.
12 *
13 * You should have received a copy of the GNU General Public License along with
14 * this program; if not, write to the Free Software Foundation, Inc., 51
15 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
16 *
17 * Copyright © 2011 Parrot S.A.
18 *
19 * Author: Ivan Djelic <ivan.djelic@parrot.com>
20 *
21 * Description:
22 *
23 * This library provides runtime configurable encoding/decoding of binary
24 * Bose-Chaudhuri-Hocquenghem (BCH) codes.
25 *
26 * Call init_bch to get a pointer to a newly allocated bch_control structure for
27 * the given m (Galois field order), t (error correction capability) and
28 * (optional) primitive polynomial parameters.
29 *
30 * Call encode_bch to compute and store ecc parity bytes to a given buffer.
31 * Call decode_bch to detect and locate errors in received data.
32 *
33 * On systems supporting hw BCH features, intermediate results may be provided
34 * to decode_bch in order to skip certain steps. See decode_bch() documentation
35 * for details.
36 *
37 * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of
38 * parameters m and t; thus allowing extra compiler optimizations and providing
39 * better (up to 2x) encoding performance. Using this option makes sense when
40 * (m,t) are fixed and known in advance, e.g. when using BCH error correction
41 * on a particular NAND flash device.
42 *
43 * Algorithmic details:
44 *
45 * Encoding is performed by processing 32 input bits in parallel, using 4
46 * remainder lookup tables.
47 *
48 * The final stage of decoding involves the following internal steps:
49 * a. Syndrome computation
50 * b. Error locator polynomial computation using Berlekamp-Massey algorithm
51 * c. Error locator root finding (by far the most expensive step)
52 *
53 * In this implementation, step c is not performed using the usual Chien search.
54 * Instead, an alternative approach described in [1] is used. It consists in
55 * factoring the error locator polynomial using the Berlekamp Trace algorithm
56 * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial
57 * solving techniques [2] are used. The resulting algorithm, called BTZ, yields
58 * much better performance than Chien search for usual (m,t) values (typically
59 * m >= 13, t < 32, see [1]).
60 *
61 * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields
62 * of characteristic 2, in: Western European Workshop on Research in Cryptology
63 * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear.
64 * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over
65 * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996.
66 */
67
68#include <linux/kernel.h>
69#include <linux/errno.h>
70#include <linux/init.h>
71#include <linux/module.h>
72#include <linux/slab.h>
73#include <linux/bitops.h>
74#include <asm/byteorder.h>
75#include <linux/bch.h>
76
77#if defined(CONFIG_BCH_CONST_PARAMS)
78#define GF_M(_p) (CONFIG_BCH_CONST_M)
79#define GF_T(_p) (CONFIG_BCH_CONST_T)
80#define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
81#else
82#define GF_M(_p) ((_p)->m)
83#define GF_T(_p) ((_p)->t)
84#define GF_N(_p) ((_p)->n)
85#endif
86
87#define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32)
88#define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8)
89
90#ifndef dbg
91#define dbg(_fmt, args...) do {} while (0)
92#endif
93
94/*
95 * represent a polynomial over GF(2^m)
96 */
97struct gf_poly {
98 unsigned int deg; /* polynomial degree */
99 unsigned int c[0]; /* polynomial terms */
100};
101
102/* given its degree, compute a polynomial size in bytes */
103#define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int))
104
105/* polynomial of degree 1 */
106struct gf_poly_deg1 {
107 struct gf_poly poly;
108 unsigned int c[2];
109};
110
111/*
112 * same as encode_bch(), but process input data one byte at a time
113 */
114static void encode_bch_unaligned(struct bch_control *bch,
115 const unsigned char *data, unsigned int len,
116 uint32_t *ecc)
117{
118 int i;
119 const uint32_t *p;
120 const int l = BCH_ECC_WORDS(bch)-1;
121
122 while (len--) {
123 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff);
124
125 for (i = 0; i < l; i++)
126 ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++);
127
128 ecc[l] = (ecc[l] << 8)^(*p);
129 }
130}
131
132/*
133 * convert ecc bytes to aligned, zero-padded 32-bit ecc words
134 */
135static void load_ecc8(struct bch_control *bch, uint32_t *dst,
136 const uint8_t *src)
137{
138 uint8_t pad[4] = {0, 0, 0, 0};
139 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
140
141 for (i = 0; i < nwords; i++, src += 4)
142 dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3];
143
144 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords);
145 dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3];
146}
147
148/*
149 * convert 32-bit ecc words to ecc bytes
150 */
151static void store_ecc8(struct bch_control *bch, uint8_t *dst,
152 const uint32_t *src)
153{
154 uint8_t pad[4];
155 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
156
157 for (i = 0; i < nwords; i++) {
158 *dst++ = (src[i] >> 24);
159 *dst++ = (src[i] >> 16) & 0xff;
160 *dst++ = (src[i] >> 8) & 0xff;
161 *dst++ = (src[i] >> 0) & 0xff;
162 }
163 pad[0] = (src[nwords] >> 24);
164 pad[1] = (src[nwords] >> 16) & 0xff;
165 pad[2] = (src[nwords] >> 8) & 0xff;
166 pad[3] = (src[nwords] >> 0) & 0xff;
167 memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);
168}
169
170/**
171 * encode_bch - calculate BCH ecc parity of data
172 * @bch: BCH control structure
173 * @data: data to encode
174 * @len: data length in bytes
175 * @ecc: ecc parity data, must be initialized by caller
176 *
177 * The @ecc parity array is used both as input and output parameter, in order to
178 * allow incremental computations. It should be of the size indicated by member
179 * @ecc_bytes of @bch, and should be initialized to 0 before the first call.
180 *
181 * The exact number of computed ecc parity bits is given by member @ecc_bits of
182 * @bch; it may be less than m*t for large values of t.
183 */
184void encode_bch(struct bch_control *bch, const uint8_t *data,
185 unsigned int len, uint8_t *ecc)
186{
187 const unsigned int l = BCH_ECC_WORDS(bch)-1;
188 unsigned int i, mlen;
189 unsigned long m;
190 uint32_t w, r[l+1];
191 const uint32_t * const tab0 = bch->mod8_tab;
192 const uint32_t * const tab1 = tab0 + 256*(l+1);
193 const uint32_t * const tab2 = tab1 + 256*(l+1);
194 const uint32_t * const tab3 = tab2 + 256*(l+1);
195 const uint32_t *pdata, *p0, *p1, *p2, *p3;
196
197 if (ecc) {
198 /* load ecc parity bytes into internal 32-bit buffer */
199 load_ecc8(bch, bch->ecc_buf, ecc);
200 } else {
201 memset(bch->ecc_buf, 0, sizeof(r));
202 }
203
204 /* process first unaligned data bytes */
205 m = ((unsigned long)data) & 3;
206 if (m) {
207 mlen = (len < (4-m)) ? len : 4-m;
208 encode_bch_unaligned(bch, data, mlen, bch->ecc_buf);
209 data += mlen;
210 len -= mlen;
211 }
212
213 /* process 32-bit aligned data words */
214 pdata = (uint32_t *)data;
215 mlen = len/4;
216 data += 4*mlen;
217 len -= 4*mlen;
218 memcpy(r, bch->ecc_buf, sizeof(r));
219
220 /*
221 * split each 32-bit word into 4 polynomials of weight 8 as follows:
222 *
223 * 31 ...24 23 ...16 15 ... 8 7 ... 0
224 * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt
225 * tttttttt mod g = r0 (precomputed)
226 * zzzzzzzz 00000000 mod g = r1 (precomputed)
227 * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed)
228 * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed)
229 * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3
230 */
231 while (mlen--) {
232 /* input data is read in big-endian format */
233 w = r[0]^cpu_to_be32(*pdata++);
234 p0 = tab0 + (l+1)*((w >> 0) & 0xff);
235 p1 = tab1 + (l+1)*((w >> 8) & 0xff);
236 p2 = tab2 + (l+1)*((w >> 16) & 0xff);
237 p3 = tab3 + (l+1)*((w >> 24) & 0xff);
238
239 for (i = 0; i < l; i++)
240 r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i];
241
242 r[l] = p0[l]^p1[l]^p2[l]^p3[l];
243 }
244 memcpy(bch->ecc_buf, r, sizeof(r));
245
246 /* process last unaligned bytes */
247 if (len)
248 encode_bch_unaligned(bch, data, len, bch->ecc_buf);
249
250 /* store ecc parity bytes into original parity buffer */
251 if (ecc)
252 store_ecc8(bch, ecc, bch->ecc_buf);
253}
254EXPORT_SYMBOL_GPL(encode_bch);
255
256static inline int modulo(struct bch_control *bch, unsigned int v)
257{
258 const unsigned int n = GF_N(bch);
259 while (v >= n) {
260 v -= n;
261 v = (v & n) + (v >> GF_M(bch));
262 }
263 return v;
264}
265
266/*
267 * shorter and faster modulo function, only works when v < 2N.
268 */
269static inline int mod_s(struct bch_control *bch, unsigned int v)
270{
271 const unsigned int n = GF_N(bch);
272 return (v < n) ? v : v-n;
273}
274
275static inline int deg(unsigned int poly)
276{
277 /* polynomial degree is the most-significant bit index */
278 return fls(poly)-1;
279}
280
281static inline int parity(unsigned int x)
282{
283 /*
284 * public domain code snippet, lifted from
285 * http://www-graphics.stanford.edu/~seander/bithacks.html
286 */
287 x ^= x >> 1;
288 x ^= x >> 2;
289 x = (x & 0x11111111U) * 0x11111111U;
290 return (x >> 28) & 1;
291}
292
293/* Galois field basic operations: multiply, divide, inverse, etc. */
294
295static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a,
296 unsigned int b)
297{
298 return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
299 bch->a_log_tab[b])] : 0;
300}
301
302static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a)
303{
304 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;
305}
306
307static inline unsigned int gf_div(struct bch_control *bch, unsigned int a,
308 unsigned int b)
309{
310 return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
311 GF_N(bch)-bch->a_log_tab[b])] : 0;
312}
313
314static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a)
315{
316 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];
317}
318
319static inline unsigned int a_pow(struct bch_control *bch, int i)
320{
321 return bch->a_pow_tab[modulo(bch, i)];
322}
323
324static inline int a_log(struct bch_control *bch, unsigned int x)
325{
326 return bch->a_log_tab[x];
327}
328
329static inline int a_ilog(struct bch_control *bch, unsigned int x)
330{
331 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]);
332}
333
334/*
335 * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t
336 */
337static void compute_syndromes(struct bch_control *bch, uint32_t *ecc,
338 unsigned int *syn)
339{
340 int i, j, s;
341 unsigned int m;
342 uint32_t poly;
343 const int t = GF_T(bch);
344
345 s = bch->ecc_bits;
346
347 /* make sure extra bits in last ecc word are cleared */
348 m = ((unsigned int)s) & 31;
349 if (m)
350 ecc[s/32] &= ~((1u << (32-m))-1);
351 memset(syn, 0, 2*t*sizeof(*syn));
352
353 /* compute v(a^j) for j=1 .. 2t-1 */
354 do {
355 poly = *ecc++;
356 s -= 32;
357 while (poly) {
358 i = deg(poly);
359 for (j = 0; j < 2*t; j += 2)
360 syn[j] ^= a_pow(bch, (j+1)*(i+s));
361
362 poly ^= (1 << i);
363 }
364 } while (s > 0);
365
366 /* v(a^(2j)) = v(a^j)^2 */
367 for (j = 0; j < t; j++)
368 syn[2*j+1] = gf_sqr(bch, syn[j]);
369}
370
371static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src)
372{
373 memcpy(dst, src, GF_POLY_SZ(src->deg));
374}
375
376static int compute_error_locator_polynomial(struct bch_control *bch,
377 const unsigned int *syn)
378{
379 const unsigned int t = GF_T(bch);
380 const unsigned int n = GF_N(bch);
381 unsigned int i, j, tmp, l, pd = 1, d = syn[0];
382 struct gf_poly *elp = bch->elp;
383 struct gf_poly *pelp = bch->poly_2t[0];
384 struct gf_poly *elp_copy = bch->poly_2t[1];
385 int k, pp = -1;
386
387 memset(pelp, 0, GF_POLY_SZ(2*t));
388 memset(elp, 0, GF_POLY_SZ(2*t));
389
390 pelp->deg = 0;
391 pelp->c[0] = 1;
392 elp->deg = 0;
393 elp->c[0] = 1;
394
395 /* use simplified binary Berlekamp-Massey algorithm */
396 for (i = 0; (i < t) && (elp->deg <= t); i++) {
397 if (d) {
398 k = 2*i-pp;
399 gf_poly_copy(elp_copy, elp);
400 /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */
401 tmp = a_log(bch, d)+n-a_log(bch, pd);
402 for (j = 0; j <= pelp->deg; j++) {
403 if (pelp->c[j]) {
404 l = a_log(bch, pelp->c[j]);
405 elp->c[j+k] ^= a_pow(bch, tmp+l);
406 }
407 }
408 /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */
409 tmp = pelp->deg+k;
410 if (tmp > elp->deg) {
411 elp->deg = tmp;
412 gf_poly_copy(pelp, elp_copy);
413 pd = d;
414 pp = 2*i;
415 }
416 }
417 /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */
418 if (i < t-1) {
419 d = syn[2*i+2];
420 for (j = 1; j <= elp->deg; j++)
421 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);
422 }
423 }
424 dbg("elp=%s\n", gf_poly_str(elp));
425 return (elp->deg > t) ? -1 : (int)elp->deg;
426}
427
428/*
429 * solve a m x m linear system in GF(2) with an expected number of solutions,
430 * and return the number of found solutions
431 */
432static int solve_linear_system(struct bch_control *bch, unsigned int *rows,
433 unsigned int *sol, int nsol)
434{
435 const int m = GF_M(bch);
436 unsigned int tmp, mask;
437 int rem, c, r, p, k, param[m];
438
439 k = 0;
440 mask = 1 << m;
441
442 /* Gaussian elimination */
443 for (c = 0; c < m; c++) {
444 rem = 0;
445 p = c-k;
446 /* find suitable row for elimination */
447 for (r = p; r < m; r++) {
448 if (rows[r] & mask) {
449 if (r != p) {
450 tmp = rows[r];
451 rows[r] = rows[p];
452 rows[p] = tmp;
453 }
454 rem = r+1;
455 break;
456 }
457 }
458 if (rem) {
459 /* perform elimination on remaining rows */
460 tmp = rows[p];
461 for (r = rem; r < m; r++) {
462 if (rows[r] & mask)
463 rows[r] ^= tmp;
464 }
465 } else {
466 /* elimination not needed, store defective row index */
467 param[k++] = c;
468 }
469 mask >>= 1;
470 }
471 /* rewrite system, inserting fake parameter rows */
472 if (k > 0) {
473 p = k;
474 for (r = m-1; r >= 0; r--) {
475 if ((r > m-1-k) && rows[r])
476 /* system has no solution */
477 return 0;
478
479 rows[r] = (p && (r == param[p-1])) ?
480 p--, 1u << (m-r) : rows[r-p];
481 }
482 }
483
484 if (nsol != (1 << k))
485 /* unexpected number of solutions */
486 return 0;
487
488 for (p = 0; p < nsol; p++) {
489 /* set parameters for p-th solution */
490 for (c = 0; c < k; c++)
491 rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1);
492
493 /* compute unique solution */
494 tmp = 0;
495 for (r = m-1; r >= 0; r--) {
496 mask = rows[r] & (tmp|1);
497 tmp |= parity(mask) << (m-r);
498 }
499 sol[p] = tmp >> 1;
500 }
501 return nsol;
502}
503
504/*
505 * this function builds and solves a linear system for finding roots of a degree
506 * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m).
507 */
508static int find_affine4_roots(struct bch_control *bch, unsigned int a,
509 unsigned int b, unsigned int c,
510 unsigned int *roots)
511{
512 int i, j, k;
513 const int m = GF_M(bch);
514 unsigned int mask = 0xff, t, rows[16] = {0,};
515
516 j = a_log(bch, b);
517 k = a_log(bch, a);
518 rows[0] = c;
519
520 /* buid linear system to solve X^4+aX^2+bX+c = 0 */
521 for (i = 0; i < m; i++) {
522 rows[i+1] = bch->a_pow_tab[4*i]^
523 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^
524 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0);
525 j++;
526 k += 2;
527 }
528 /*
529 * transpose 16x16 matrix before passing it to linear solver
530 * warning: this code assumes m < 16
531 */
532 for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) {
533 for (k = 0; k < 16; k = (k+j+1) & ~j) {
534 t = ((rows[k] >> j)^rows[k+j]) & mask;
535 rows[k] ^= (t << j);
536 rows[k+j] ^= t;
537 }
538 }
539 return solve_linear_system(bch, rows, roots, 4);
540}
541
542/*
543 * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r))
544 */
545static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly,
546 unsigned int *roots)
547{
548 int n = 0;
549
550 if (poly->c[0])
551 /* poly[X] = bX+c with c!=0, root=c/b */
552 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+
553 bch->a_log_tab[poly->c[1]]);
554 return n;
555}
556
557/*
558 * compute roots of a degree 2 polynomial over GF(2^m)
559 */
560static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly,
561 unsigned int *roots)
562{
563 int n = 0, i, l0, l1, l2;
564 unsigned int u, v, r;
565
566 if (poly->c[0] && poly->c[1]) {
567
568 l0 = bch->a_log_tab[poly->c[0]];
569 l1 = bch->a_log_tab[poly->c[1]];
570 l2 = bch->a_log_tab[poly->c[2]];
571
572 /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */
573 u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));
574 /*
575 * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi):
576 * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) =
577 * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u)
578 * i.e. r and r+1 are roots iff Tr(u)=0
579 */
580 r = 0;
581 v = u;
582 while (v) {
583 i = deg(v);
584 r ^= bch->xi_tab[i];
585 v ^= (1 << i);
586 }
587 /* verify root */
588 if ((gf_sqr(bch, r)^r) == u) {
589 /* reverse z=a/bX transformation and compute log(1/r) */
590 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
591 bch->a_log_tab[r]+l2);
592 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
593 bch->a_log_tab[r^1]+l2);
594 }
595 }
596 return n;
597}
598
599/*
600 * compute roots of a degree 3 polynomial over GF(2^m)
601 */
602static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly,
603 unsigned int *roots)
604{
605 int i, n = 0;
606 unsigned int a, b, c, a2, b2, c2, e3, tmp[4];
607
608 if (poly->c[0]) {
609 /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */
610 e3 = poly->c[3];
611 c2 = gf_div(bch, poly->c[0], e3);
612 b2 = gf_div(bch, poly->c[1], e3);
613 a2 = gf_div(bch, poly->c[2], e3);
614
615 /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */
616 c = gf_mul(bch, a2, c2); /* c = a2c2 */
617 b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */
618 a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */
619
620 /* find the 4 roots of this affine polynomial */
621 if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
622 /* remove a2 from final list of roots */
623 for (i = 0; i < 4; i++) {
624 if (tmp[i] != a2)
625 roots[n++] = a_ilog(bch, tmp[i]);
626 }
627 }
628 }
629 return n;
630}
631
632/*
633 * compute roots of a degree 4 polynomial over GF(2^m)
634 */
635static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly,
636 unsigned int *roots)
637{
638 int i, l, n = 0;
639 unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4;
640
641 if (poly->c[0] == 0)
642 return 0;
643
644 /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */
645 e4 = poly->c[4];
646 d = gf_div(bch, poly->c[0], e4);
647 c = gf_div(bch, poly->c[1], e4);
648 b = gf_div(bch, poly->c[2], e4);
649 a = gf_div(bch, poly->c[3], e4);
650
651 /* use Y=1/X transformation to get an affine polynomial */
652 if (a) {
653 /* first, eliminate cX by using z=X+e with ae^2+c=0 */
654 if (c) {
655 /* compute e such that e^2 = c/a */
656 f = gf_div(bch, c, a);
657 l = a_log(bch, f);
658 l += (l & 1) ? GF_N(bch) : 0;
659 e = a_pow(bch, l/2);
660 /*
661 * use transformation z=X+e:
662 * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d
663 * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d
664 * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d
665 * z^4 + az^3 + b'z^2 + d'
666 */
667 d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;
668 b = gf_mul(bch, a, e)^b;
669 }
670 /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */
671 if (d == 0)
672 /* assume all roots have multiplicity 1 */
673 return 0;
674
675 c2 = gf_inv(bch, d);
676 b2 = gf_div(bch, a, d);
677 a2 = gf_div(bch, b, d);
678 } else {
679 /* polynomial is already affine */
680 c2 = d;
681 b2 = c;
682 a2 = b;
683 }
684 /* find the 4 roots of this affine polynomial */
685 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
686 for (i = 0; i < 4; i++) {
687 /* post-process roots (reverse transformations) */
688 f = a ? gf_inv(bch, roots[i]) : roots[i];
689 roots[i] = a_ilog(bch, f^e);
690 }
691 n = 4;
692 }
693 return n;
694}
695
696/*
697 * build monic, log-based representation of a polynomial
698 */
699static void gf_poly_logrep(struct bch_control *bch,
700 const struct gf_poly *a, int *rep)
701{
702 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]);
703
704 /* represent 0 values with -1; warning, rep[d] is not set to 1 */
705 for (i = 0; i < d; i++)
706 rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1;
707}
708
709/*
710 * compute polynomial Euclidean division remainder in GF(2^m)[X]
711 */
712static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a,
713 const struct gf_poly *b, int *rep)
714{
715 int la, p, m;
716 unsigned int i, j, *c = a->c;
717 const unsigned int d = b->deg;
718
719 if (a->deg < d)
720 return;
721
722 /* reuse or compute log representation of denominator */
723 if (!rep) {
724 rep = bch->cache;
725 gf_poly_logrep(bch, b, rep);
726 }
727
728 for (j = a->deg; j >= d; j--) {
729 if (c[j]) {
730 la = a_log(bch, c[j]);
731 p = j-d;
732 for (i = 0; i < d; i++, p++) {
733 m = rep[i];
734 if (m >= 0)
735 c[p] ^= bch->a_pow_tab[mod_s(bch,
736 m+la)];
737 }
738 }
739 }
740 a->deg = d-1;
741 while (!c[a->deg] && a->deg)
742 a->deg--;
743}
744
745/*
746 * compute polynomial Euclidean division quotient in GF(2^m)[X]
747 */
748static void gf_poly_div(struct bch_control *bch, struct gf_poly *a,
749 const struct gf_poly *b, struct gf_poly *q)
750{
751 if (a->deg >= b->deg) {
752 q->deg = a->deg-b->deg;
753 /* compute a mod b (modifies a) */
754 gf_poly_mod(bch, a, b, NULL);
755 /* quotient is stored in upper part of polynomial a */
756 memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int));
757 } else {
758 q->deg = 0;
759 q->c[0] = 0;
760 }
761}
762
763/*
764 * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X]
765 */
766static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a,
767 struct gf_poly *b)
768{
769 struct gf_poly *tmp;
770
771 dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b));
772
773 if (a->deg < b->deg) {
774 tmp = b;
775 b = a;
776 a = tmp;
777 }
778
779 while (b->deg > 0) {
780 gf_poly_mod(bch, a, b, NULL);
781 tmp = b;
782 b = a;
783 a = tmp;
784 }
785
786 dbg("%s\n", gf_poly_str(a));
787
788 return a;
789}
790
791/*
792 * Given a polynomial f and an integer k, compute Tr(a^kX) mod f
793 * This is used in Berlekamp Trace algorithm for splitting polynomials
794 */
795static void compute_trace_bk_mod(struct bch_control *bch, int k,
796 const struct gf_poly *f, struct gf_poly *z,
797 struct gf_poly *out)
798{
799 const int m = GF_M(bch);
800 int i, j;
801
802 /* z contains z^2j mod f */
803 z->deg = 1;
804 z->c[0] = 0;
805 z->c[1] = bch->a_pow_tab[k];
806
807 out->deg = 0;
808 memset(out, 0, GF_POLY_SZ(f->deg));
809
810 /* compute f log representation only once */
811 gf_poly_logrep(bch, f, bch->cache);
812
813 for (i = 0; i < m; i++) {
814 /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */
815 for (j = z->deg; j >= 0; j--) {
816 out->c[j] ^= z->c[j];
817 z->c[2*j] = gf_sqr(bch, z->c[j]);
818 z->c[2*j+1] = 0;
819 }
820 if (z->deg > out->deg)
821 out->deg = z->deg;
822
823 if (i < m-1) {
824 z->deg *= 2;
825 /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */
826 gf_poly_mod(bch, z, f, bch->cache);
827 }
828 }
829 while (!out->c[out->deg] && out->deg)
830 out->deg--;
831
832 dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out));
833}
834
835/*
836 * factor a polynomial using Berlekamp Trace algorithm (BTA)
837 */
838static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f,
839 struct gf_poly **g, struct gf_poly **h)
840{
841 struct gf_poly *f2 = bch->poly_2t[0];
842 struct gf_poly *q = bch->poly_2t[1];
843 struct gf_poly *tk = bch->poly_2t[2];
844 struct gf_poly *z = bch->poly_2t[3];
845 struct gf_poly *gcd;
846
847 dbg("factoring %s...\n", gf_poly_str(f));
848
849 *g = f;
850 *h = NULL;
851
852 /* tk = Tr(a^k.X) mod f */
853 compute_trace_bk_mod(bch, k, f, z, tk);
854
855 if (tk->deg > 0) {
856 /* compute g = gcd(f, tk) (destructive operation) */
857 gf_poly_copy(f2, f);
858 gcd = gf_poly_gcd(bch, f2, tk);
859 if (gcd->deg < f->deg) {
860 /* compute h=f/gcd(f,tk); this will modify f and q */
861 gf_poly_div(bch, f, gcd, q);
862 /* store g and h in-place (clobbering f) */
863 *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly;
864 gf_poly_copy(*g, gcd);
865 gf_poly_copy(*h, q);
866 }
867 }
868}
869
870/*
871 * find roots of a polynomial, using BTZ algorithm; see the beginning of this
872 * file for details
873 */
874static int find_poly_roots(struct bch_control *bch, unsigned int k,
875 struct gf_poly *poly, unsigned int *roots)
876{
877 int cnt;
878 struct gf_poly *f1, *f2;
879
880 switch (poly->deg) {
881 /* handle low degree polynomials with ad hoc techniques */
882 case 1:
883 cnt = find_poly_deg1_roots(bch, poly, roots);
884 break;
885 case 2:
886 cnt = find_poly_deg2_roots(bch, poly, roots);
887 break;
888 case 3:
889 cnt = find_poly_deg3_roots(bch, poly, roots);
890 break;
891 case 4:
892 cnt = find_poly_deg4_roots(bch, poly, roots);
893 break;
894 default:
895 /* factor polynomial using Berlekamp Trace Algorithm (BTA) */
896 cnt = 0;
897 if (poly->deg && (k <= GF_M(bch))) {
898 factor_polynomial(bch, k, poly, &f1, &f2);
899 if (f1)
900 cnt += find_poly_roots(bch, k+1, f1, roots);
901 if (f2)
902 cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
903 }
904 break;
905 }
906 return cnt;
907}
908
909#if defined(USE_CHIEN_SEARCH)
910/*
911 * exhaustive root search (Chien) implementation - not used, included only for
912 * reference/comparison tests
913 */
914static int chien_search(struct bch_control *bch, unsigned int len,
915 struct gf_poly *p, unsigned int *roots)
916{
917 int m;
918 unsigned int i, j, syn, syn0, count = 0;
919 const unsigned int k = 8*len+bch->ecc_bits;
920
921 /* use a log-based representation of polynomial */
922 gf_poly_logrep(bch, p, bch->cache);
923 bch->cache[p->deg] = 0;
924 syn0 = gf_div(bch, p->c[0], p->c[p->deg]);
925
926 for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) {
927 /* compute elp(a^i) */
928 for (j = 1, syn = syn0; j <= p->deg; j++) {
929 m = bch->cache[j];
930 if (m >= 0)
931 syn ^= a_pow(bch, m+j*i);
932 }
933 if (syn == 0) {
934 roots[count++] = GF_N(bch)-i;
935 if (count == p->deg)
936 break;
937 }
938 }
939 return (count == p->deg) ? count : 0;
940}
941#define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc)
942#endif /* USE_CHIEN_SEARCH */
943
944/**
945 * decode_bch - decode received codeword and find bit error locations
946 * @bch: BCH control structure
947 * @data: received data, ignored if @calc_ecc is provided
948 * @len: data length in bytes, must always be provided
949 * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc
950 * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data
951 * @syn: hw computed syndrome data (if NULL, syndrome is calculated)
952 * @errloc: output array of error locations
953 *
954 * Returns:
955 * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if
956 * invalid parameters were provided
957 *
958 * Depending on the available hw BCH support and the need to compute @calc_ecc
959 * separately (using encode_bch()), this function should be called with one of
960 * the following parameter configurations -
961 *
962 * by providing @data and @recv_ecc only:
963 * decode_bch(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc)
964 *
965 * by providing @recv_ecc and @calc_ecc:
966 * decode_bch(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc)
967 *
968 * by providing ecc = recv_ecc XOR calc_ecc:
969 * decode_bch(@bch, NULL, @len, NULL, ecc, NULL, @errloc)
970 *
971 * by providing syndrome results @syn:
972 * decode_bch(@bch, NULL, @len, NULL, NULL, @syn, @errloc)
973 *
974 * Once decode_bch() has successfully returned with a positive value, error
975 * locations returned in array @errloc should be interpreted as follows -
976 *
977 * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for
978 * data correction)
979 *
980 * if (errloc[n] < 8*len), then n-th error is located in data and can be
981 * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8);
982 *
983 * Note that this function does not perform any data correction by itself, it
984 * merely indicates error locations.
985 */
986int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len,
987 const uint8_t *recv_ecc, const uint8_t *calc_ecc,
988 const unsigned int *syn, unsigned int *errloc)
989{
990 const unsigned int ecc_words = BCH_ECC_WORDS(bch);
991 unsigned int nbits;
992 int i, err, nroots;
993 uint32_t sum;
994
995 /* sanity check: make sure data length can be handled */
996 if (8*len > (bch->n-bch->ecc_bits))
997 return -EINVAL;
998
999 /* if caller does not provide syndromes, compute them */
1000 if (!syn) {
1001 if (!calc_ecc) {
1002 /* compute received data ecc into an internal buffer */
1003 if (!data || !recv_ecc)
1004 return -EINVAL;
1005 encode_bch(bch, data, len, NULL);
1006 } else {
1007 /* load provided calculated ecc */
1008 load_ecc8(bch, bch->ecc_buf, calc_ecc);
1009 }
1010 /* load received ecc or assume it was XORed in calc_ecc */
1011 if (recv_ecc) {
1012 load_ecc8(bch, bch->ecc_buf2, recv_ecc);
1013 /* XOR received and calculated ecc */
1014 for (i = 0, sum = 0; i < (int)ecc_words; i++) {
1015 bch->ecc_buf[i] ^= bch->ecc_buf2[i];
1016 sum |= bch->ecc_buf[i];
1017 }
1018 if (!sum)
1019 /* no error found */
1020 return 0;
1021 }
1022 compute_syndromes(bch, bch->ecc_buf, bch->syn);
1023 syn = bch->syn;
1024 }
1025
1026 err = compute_error_locator_polynomial(bch, syn);
1027 if (err > 0) {
1028 nroots = find_poly_roots(bch, 1, bch->elp, errloc);
1029 if (err != nroots)
1030 err = -1;
1031 }
1032 if (err > 0) {
1033 /* post-process raw error locations for easier correction */
1034 nbits = (len*8)+bch->ecc_bits;
1035 for (i = 0; i < err; i++) {
1036 if (errloc[i] >= nbits) {
1037 err = -1;
1038 break;
1039 }
1040 errloc[i] = nbits-1-errloc[i];
1041 errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7));
1042 }
1043 }
1044 return (err >= 0) ? err : -EBADMSG;
1045}
1046EXPORT_SYMBOL_GPL(decode_bch);
1047
1048/*
1049 * generate Galois field lookup tables
1050 */
1051static int build_gf_tables(struct bch_control *bch, unsigned int poly)
1052{
1053 unsigned int i, x = 1;
1054 const unsigned int k = 1 << deg(poly);
1055
1056 /* primitive polynomial must be of degree m */
1057 if (k != (1u << GF_M(bch)))
1058 return -1;
1059
1060 for (i = 0; i < GF_N(bch); i++) {
1061 bch->a_pow_tab[i] = x;
1062 bch->a_log_tab[x] = i;
1063 if (i && (x == 1))
1064 /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */
1065 return -1;
1066 x <<= 1;
1067 if (x & k)
1068 x ^= poly;
1069 }
1070 bch->a_pow_tab[GF_N(bch)] = 1;
1071 bch->a_log_tab[0] = 0;
1072
1073 return 0;
1074}
1075
1076/*
1077 * compute generator polynomial remainder tables for fast encoding
1078 */
1079static void build_mod8_tables(struct bch_control *bch, const uint32_t *g)
1080{
1081 int i, j, b, d;
1082 uint32_t data, hi, lo, *tab;
1083 const int l = BCH_ECC_WORDS(bch);
1084 const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32);
1085 const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32);
1086
1087 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab));
1088
1089 for (i = 0; i < 256; i++) {
1090 /* p(X)=i is a small polynomial of weight <= 8 */
1091 for (b = 0; b < 4; b++) {
1092 /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */
1093 tab = bch->mod8_tab + (b*256+i)*l;
1094 data = i << (8*b);
1095 while (data) {
1096 d = deg(data);
1097 /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */
1098 data ^= g[0] >> (31-d);
1099 for (j = 0; j < ecclen; j++) {
1100 hi = (d < 31) ? g[j] << (d+1) : 0;
1101 lo = (j+1 < plen) ?
1102 g[j+1] >> (31-d) : 0;
1103 tab[j] ^= hi|lo;
1104 }
1105 }
1106 }
1107 }
1108}
1109
1110/*
1111 * build a base for factoring degree 2 polynomials
1112 */
1113static int build_deg2_base(struct bch_control *bch)
1114{
1115 const int m = GF_M(bch);
1116 int i, j, r;
1117 unsigned int sum, x, y, remaining, ak = 0, xi[m];
1118
1119 /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */
1120 for (i = 0; i < m; i++) {
1121 for (j = 0, sum = 0; j < m; j++)
1122 sum ^= a_pow(bch, i*(1 << j));
1123
1124 if (sum) {
1125 ak = bch->a_pow_tab[i];
1126 break;
1127 }
1128 }
1129 /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */
1130 remaining = m;
1131 memset(xi, 0, sizeof(xi));
1132
1133 for (x = 0; (x <= GF_N(bch)) && remaining; x++) {
1134 y = gf_sqr(bch, x)^x;
1135 for (i = 0; i < 2; i++) {
1136 r = a_log(bch, y);
1137 if (y && (r < m) && !xi[r]) {
1138 bch->xi_tab[r] = x;
1139 xi[r] = 1;
1140 remaining--;
1141 dbg("x%d = %x\n", r, x);
1142 break;
1143 }
1144 y ^= ak;
1145 }
1146 }
1147 /* should not happen but check anyway */
1148 return remaining ? -1 : 0;
1149}
1150
1151static void *bch_alloc(size_t size, int *err)
1152{
1153 void *ptr;
1154
1155 ptr = kmalloc(size, GFP_KERNEL);
1156 if (ptr == NULL)
1157 *err = 1;
1158 return ptr;
1159}
1160
1161/*
1162 * compute generator polynomial for given (m,t) parameters.
1163 */
1164static uint32_t *compute_generator_polynomial(struct bch_control *bch)
1165{
1166 const unsigned int m = GF_M(bch);
1167 const unsigned int t = GF_T(bch);
1168 int n, err = 0;
1169 unsigned int i, j, nbits, r, word, *roots;
1170 struct gf_poly *g;
1171 uint32_t *genpoly;
1172
1173 g = bch_alloc(GF_POLY_SZ(m*t), &err);
1174 roots = bch_alloc((bch->n+1)*sizeof(*roots), &err);
1175 genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err);
1176
1177 if (err) {
1178 kfree(genpoly);
1179 genpoly = NULL;
1180 goto finish;
1181 }
1182
1183 /* enumerate all roots of g(X) */
1184 memset(roots , 0, (bch->n+1)*sizeof(*roots));
1185 for (i = 0; i < t; i++) {
1186 for (j = 0, r = 2*i+1; j < m; j++) {
1187 roots[r] = 1;
1188 r = mod_s(bch, 2*r);
1189 }
1190 }
1191 /* build generator polynomial g(X) */
1192 g->deg = 0;
1193 g->c[0] = 1;
1194 for (i = 0; i < GF_N(bch); i++) {
1195 if (roots[i]) {
1196 /* multiply g(X) by (X+root) */
1197 r = bch->a_pow_tab[i];
1198 g->c[g->deg+1] = 1;
1199 for (j = g->deg; j > 0; j--)
1200 g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1];
1201
1202 g->c[0] = gf_mul(bch, g->c[0], r);
1203 g->deg++;
1204 }
1205 }
1206 /* store left-justified binary representation of g(X) */
1207 n = g->deg+1;
1208 i = 0;
1209
1210 while (n > 0) {
1211 nbits = (n > 32) ? 32 : n;
1212 for (j = 0, word = 0; j < nbits; j++) {
1213 if (g->c[n-1-j])
1214 word |= 1u << (31-j);
1215 }
1216 genpoly[i++] = word;
1217 n -= nbits;
1218 }
1219 bch->ecc_bits = g->deg;
1220
1221finish:
1222 kfree(g);
1223 kfree(roots);
1224
1225 return genpoly;
1226}
1227
1228/**
1229 * init_bch - initialize a BCH encoder/decoder
1230 * @m: Galois field order, should be in the range 5-15
1231 * @t: maximum error correction capability, in bits
1232 * @prim_poly: user-provided primitive polynomial (or 0 to use default)
1233 *
1234 * Returns:
1235 * a newly allocated BCH control structure if successful, NULL otherwise
1236 *
1237 * This initialization can take some time, as lookup tables are built for fast
1238 * encoding/decoding; make sure not to call this function from a time critical
1239 * path. Usually, init_bch() should be called on module/driver init and
1240 * free_bch() should be called to release memory on exit.
1241 *
1242 * You may provide your own primitive polynomial of degree @m in argument
1243 * @prim_poly, or let init_bch() use its default polynomial.
1244 *
1245 * Once init_bch() has successfully returned a pointer to a newly allocated
1246 * BCH control structure, ecc length in bytes is given by member @ecc_bytes of
1247 * the structure.
1248 */
1249struct bch_control *init_bch(int m, int t, unsigned int prim_poly)
1250{
1251 int err = 0;
1252 unsigned int i, words;
1253 uint32_t *genpoly;
1254 struct bch_control *bch = NULL;
1255
1256 const int min_m = 5;
1257 const int max_m = 15;
1258
1259 /* default primitive polynomials */
1260 static const unsigned int prim_poly_tab[] = {
1261 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b,
1262 0x402b, 0x8003,
1263 };
1264
1265#if defined(CONFIG_BCH_CONST_PARAMS)
1266 if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) {
1267 printk(KERN_ERR "bch encoder/decoder was configured to support "
1268 "parameters m=%d, t=%d only!\n",
1269 CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T);
1270 goto fail;
1271 }
1272#endif
1273 if ((m < min_m) || (m > max_m))
1274 /*
1275 * values of m greater than 15 are not currently supported;
1276 * supporting m > 15 would require changing table base type
1277 * (uint16_t) and a small patch in matrix transposition
1278 */
1279 goto fail;
1280
1281 /* sanity checks */
1282 if ((t < 1) || (m*t >= ((1 << m)-1)))
1283 /* invalid t value */
1284 goto fail;
1285
1286 /* select a primitive polynomial for generating GF(2^m) */
1287 if (prim_poly == 0)
1288 prim_poly = prim_poly_tab[m-min_m];
1289
1290 bch = kzalloc(sizeof(*bch), GFP_KERNEL);
1291 if (bch == NULL)
1292 goto fail;
1293
1294 bch->m = m;
1295 bch->t = t;
1296 bch->n = (1 << m)-1;
1297 words = DIV_ROUND_UP(m*t, 32);
1298 bch->ecc_bytes = DIV_ROUND_UP(m*t, 8);
1299 bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err);
1300 bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err);
1301 bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err);
1302 bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err);
1303 bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err);
1304 bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err);
1305 bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err);
1306 bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err);
1307 bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err);
1308
1309 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1310 bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);
1311
1312 if (err)
1313 goto fail;
1314
1315 err = build_gf_tables(bch, prim_poly);
1316 if (err)
1317 goto fail;
1318
1319 /* use generator polynomial for computing encoding tables */
1320 genpoly = compute_generator_polynomial(bch);
1321 if (genpoly == NULL)
1322 goto fail;
1323
1324 build_mod8_tables(bch, genpoly);
1325 kfree(genpoly);
1326
1327 err = build_deg2_base(bch);
1328 if (err)
1329 goto fail;
1330
1331 return bch;
1332
1333fail:
1334 free_bch(bch);
1335 return NULL;
1336}
1337EXPORT_SYMBOL_GPL(init_bch);
1338
1339/**
1340 * free_bch - free the BCH control structure
1341 * @bch: BCH control structure to release
1342 */
1343void free_bch(struct bch_control *bch)
1344{
1345 unsigned int i;
1346
1347 if (bch) {
1348 kfree(bch->a_pow_tab);
1349 kfree(bch->a_log_tab);
1350 kfree(bch->mod8_tab);
1351 kfree(bch->ecc_buf);
1352 kfree(bch->ecc_buf2);
1353 kfree(bch->xi_tab);
1354 kfree(bch->syn);
1355 kfree(bch->cache);
1356 kfree(bch->elp);
1357
1358 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1359 kfree(bch->poly_2t[i]);
1360
1361 kfree(bch);
1362 }
1363}
1364EXPORT_SYMBOL_GPL(free_bch);
1365
1366MODULE_LICENSE("GPL");
1367MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>");
1368MODULE_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);
830 * @orig (i.e. bits 3, 5, 7 and 9) were also set. 830 * @orig (i.e. bits 3, 5, 7 and 9) were also set.
831 * 831 *
832 * When bit 11 is set in @orig, it means turn on the bit in 832 * When bit 11 is set in @orig, it means turn on the bit in
833 * @dst corresponding to whatever is the twelth bit that is 833 * @dst corresponding to whatever is the twelfth bit that is
834 * turned on in @relmap. In the above example, there were 834 * turned on in @relmap. In the above example, there were
835 * only ten bits turned on in @relmap (30..39), so that bit 835 * only ten bits turned on in @relmap (30..39), so that bit
836 * 11 was set in @orig had no affect on @dst. 836 * 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 @@
1/*
2 * A generic implementation of binary search for the Linux kernel
3 *
4 * Copyright (C) 2008-2009 Ksplice, Inc.
5 * Author: Tim Abbott <tabbott@ksplice.com>
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; version 2.
10 */
11
12#include <linux/module.h>
13#include <linux/bsearch.h>
14
15/*
16 * bsearch - binary search an array of elements
17 * @key: pointer to item being searched for
18 * @base: pointer to first element to search
19 * @num: number of elements
20 * @size: size of each element
21 * @cmp: pointer to comparison function
22 *
23 * This function does a binary search on the given array. The
24 * contents of the array should already be in ascending sorted order
25 * under the provided comparison function.
26 *
27 * Note that the key need not have the same type as the elements in
28 * the array, e.g. key could be a string and the comparison function
29 * could compare the string with the struct's name field. However, if
30 * the key and elements in the array are of the same type, you can use
31 * the same comparison function for both sort() and bsearch().
32 */
33void *bsearch(const void *key, const void *base, size_t num, size_t size,
34 int (*cmp)(const void *key, const void *elt))
35{
36 size_t start = 0, end = num;
37 int result;
38
39 while (start < end) {
40 size_t mid = start + (end - start) / 2;
41
42 result = cmp(key, base + mid * size);
43 if (result < 0)
44 end = mid;
45 else if (result > 0)
46 start = mid + 1;
47 else
48 return (void *)base + mid * size;
49 }
50
51 return NULL;
52}
53EXPORT_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 @@
11 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch 11 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
12 * 12 *
13 * A relatively simple B+Tree implementation. I have written it as a learning 13 * A relatively simple B+Tree implementation. I have written it as a learning
14 * excercise to understand how B+Trees work. Turned out to be useful as well. 14 * exercise to understand how B+Trees work. Turned out to be useful as well.
15 * 15 *
16 * B+Trees can be used similar to Linux radix trees (which don't have anything 16 * B+Trees can be used similar to Linux radix trees (which don't have anything
17 * in common with textbook radix trees, beware). Prerequisite for them working 17 * 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,
541 int i, no_left, no_right; 541 int i, no_left, no_right;
542 542
543 if (fill == 0) { 543 if (fill == 0) {
544 /* Because we don't steal entries from a neigbour, this case 544 /* Because we don't steal entries from a neighbour, this case
545 * can happen. Parent node contains a single child, this 545 * can happen. Parent node contains a single child, this
546 * node, so merging with a sibling never happens. 546 * node, so merging with a sibling never happens.
547 */ 547 */
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 @@
1/*
2 * cpu_rmap.c: CPU affinity reverse-map support
3 * Copyright 2011 Solarflare Communications Inc.
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 as published
7 * by the Free Software Foundation, incorporated herein by reference.
8 */
9
10#include <linux/cpu_rmap.h>
11#ifdef CONFIG_GENERIC_HARDIRQS
12#include <linux/interrupt.h>
13#endif
14#include <linux/module.h>
15
16/*
17 * These functions maintain a mapping from CPUs to some ordered set of
18 * objects with CPU affinities. This can be seen as a reverse-map of
19 * CPU affinity. However, we do not assume that the object affinities
20 * cover all CPUs in the system. For those CPUs not directly covered
21 * by object affinities, we attempt to find a nearest object based on
22 * CPU topology.
23 */
24
25/**
26 * alloc_cpu_rmap - allocate CPU affinity reverse-map
27 * @size: Number of objects to be mapped
28 * @flags: Allocation flags e.g. %GFP_KERNEL
29 */
30struct cpu_rmap *alloc_cpu_rmap(unsigned int size, gfp_t flags)
31{
32 struct cpu_rmap *rmap;
33 unsigned int cpu;
34 size_t obj_offset;
35
36 /* This is a silly number of objects, and we use u16 indices. */
37 if (size > 0xffff)
38 return NULL;
39
40 /* Offset of object pointer array from base structure */
41 obj_offset = ALIGN(offsetof(struct cpu_rmap, near[nr_cpu_ids]),
42 sizeof(void *));
43
44 rmap = kzalloc(obj_offset + size * sizeof(rmap->obj[0]), flags);
45 if (!rmap)
46 return NULL;
47
48 rmap->obj = (void **)((char *)rmap + obj_offset);
49
50 /* Initially assign CPUs to objects on a rota, since we have
51 * no idea where the objects are. Use infinite distance, so
52 * any object with known distance is preferable. Include the
53 * CPUs that are not present/online, since we definitely want
54 * any newly-hotplugged CPUs to have some object assigned.
55 */
56 for_each_possible_cpu(cpu) {
57 rmap->near[cpu].index = cpu % size;
58 rmap->near[cpu].dist = CPU_RMAP_DIST_INF;
59 }
60
61 rmap->size = size;
62 return rmap;
63}
64EXPORT_SYMBOL(alloc_cpu_rmap);
65
66/* Reevaluate nearest object for given CPU, comparing with the given
67 * neighbours at the given distance.
68 */
69static bool cpu_rmap_copy_neigh(struct cpu_rmap *rmap, unsigned int cpu,
70 const struct cpumask *mask, u16 dist)
71{
72 int neigh;
73
74 for_each_cpu(neigh, mask) {
75 if (rmap->near[cpu].dist > dist &&
76 rmap->near[neigh].dist <= dist) {
77 rmap->near[cpu].index = rmap->near[neigh].index;
78 rmap->near[cpu].dist = dist;
79 return true;
80 }
81 }
82 return false;
83}
84
85#ifdef DEBUG
86static void debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix)
87{
88 unsigned index;
89 unsigned int cpu;
90
91 pr_info("cpu_rmap %p, %s:\n", rmap, prefix);
92
93 for_each_possible_cpu(cpu) {
94 index = rmap->near[cpu].index;
95 pr_info("cpu %d -> obj %u (distance %u)\n",
96 cpu, index, rmap->near[cpu].dist);
97 }
98}
99#else
100static inline void
101debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix)
102{
103}
104#endif
105
106/**
107 * cpu_rmap_add - add object to a rmap
108 * @rmap: CPU rmap allocated with alloc_cpu_rmap()
109 * @obj: Object to add to rmap
110 *
111 * Return index of object.
112 */
113int cpu_rmap_add(struct cpu_rmap *rmap, void *obj)
114{
115 u16 index;
116
117 BUG_ON(rmap->used >= rmap->size);
118 index = rmap->used++;
119 rmap->obj[index] = obj;
120 return index;
121}
122EXPORT_SYMBOL(cpu_rmap_add);
123
124/**
125 * cpu_rmap_update - update CPU rmap following a change of object affinity
126 * @rmap: CPU rmap to update
127 * @index: Index of object whose affinity changed
128 * @affinity: New CPU affinity of object
129 */
130int cpu_rmap_update(struct cpu_rmap *rmap, u16 index,
131 const struct cpumask *affinity)
132{
133 cpumask_var_t update_mask;
134 unsigned int cpu;
135
136 if (unlikely(!zalloc_cpumask_var(&update_mask, GFP_KERNEL)))
137 return -ENOMEM;
138
139 /* Invalidate distance for all CPUs for which this used to be
140 * the nearest object. Mark those CPUs for update.
141 */
142 for_each_online_cpu(cpu) {
143 if (rmap->near[cpu].index == index) {
144 rmap->near[cpu].dist = CPU_RMAP_DIST_INF;
145 cpumask_set_cpu(cpu, update_mask);
146 }
147 }
148
149 debug_print_rmap(rmap, "after invalidating old distances");
150
151 /* Set distance to 0 for all CPUs in the new affinity mask.
152 * Mark all CPUs within their NUMA nodes for update.
153 */
154 for_each_cpu(cpu, affinity) {
155 rmap->near[cpu].index = index;
156 rmap->near[cpu].dist = 0;
157 cpumask_or(update_mask, update_mask,
158 cpumask_of_node(cpu_to_node(cpu)));
159 }
160
161 debug_print_rmap(rmap, "after updating neighbours");
162
163 /* Update distances based on topology */
164 for_each_cpu(cpu, update_mask) {
165 if (cpu_rmap_copy_neigh(rmap, cpu,
166 topology_thread_cpumask(cpu), 1))
167 continue;
168 if (cpu_rmap_copy_neigh(rmap, cpu,
169 topology_core_cpumask(cpu), 2))
170 continue;
171 if (cpu_rmap_copy_neigh(rmap, cpu,
172 cpumask_of_node(cpu_to_node(cpu)), 3))
173 continue;
174 /* We could continue into NUMA node distances, but for now
175 * we give up.
176 */
177 }
178
179 debug_print_rmap(rmap, "after copying neighbours");
180
181 free_cpumask_var(update_mask);
182 return 0;
183}
184EXPORT_SYMBOL(cpu_rmap_update);
185
186#ifdef CONFIG_GENERIC_HARDIRQS
187
188/* Glue between IRQ affinity notifiers and CPU rmaps */
189
190struct irq_glue {
191 struct irq_affinity_notify notify;
192 struct cpu_rmap *rmap;
193 u16 index;
194};
195
196/**
197 * free_irq_cpu_rmap - free a CPU affinity reverse-map used for IRQs
198 * @rmap: Reverse-map allocated with alloc_irq_cpu_map(), or %NULL
199 *
200 * Must be called in process context, before freeing the IRQs, and
201 * without holding any locks required by global workqueue items.
202 */
203void free_irq_cpu_rmap(struct cpu_rmap *rmap)
204{
205 struct irq_glue *glue;
206 u16 index;
207
208 if (!rmap)
209 return;
210
211 for (index = 0; index < rmap->used; index++) {
212 glue = rmap->obj[index];
213 irq_set_affinity_notifier(glue->notify.irq, NULL);
214 }
215 irq_run_affinity_notifiers();
216
217 kfree(rmap);
218}
219EXPORT_SYMBOL(free_irq_cpu_rmap);
220
221static void
222irq_cpu_rmap_notify(struct irq_affinity_notify *notify, const cpumask_t *mask)
223{
224 struct irq_glue *glue =
225 container_of(notify, struct irq_glue, notify);
226 int rc;
227
228 rc = cpu_rmap_update(glue->rmap, glue->index, mask);
229 if (rc)
230 pr_warning("irq_cpu_rmap_notify: update failed: %d\n", rc);
231}
232
233static void irq_cpu_rmap_release(struct kref *ref)
234{
235 struct irq_glue *glue =
236 container_of(ref, struct irq_glue, notify.kref);
237 kfree(glue);
238}
239
240/**
241 * irq_cpu_rmap_add - add an IRQ to a CPU affinity reverse-map
242 * @rmap: The reverse-map
243 * @irq: The IRQ number
244 *
245 * This adds an IRQ affinity notifier that will update the reverse-map
246 * automatically.
247 *
248 * Must be called in process context, after the IRQ is allocated but
249 * before it is bound with request_irq().
250 */
251int irq_cpu_rmap_add(struct cpu_rmap *rmap, int irq)
252{
253 struct irq_glue *glue = kzalloc(sizeof(*glue), GFP_KERNEL);
254 int rc;
255
256 if (!glue)
257 return -ENOMEM;
258 glue->notify.notify = irq_cpu_rmap_notify;
259 glue->notify.release = irq_cpu_rmap_release;
260 glue->rmap = rmap;
261 glue->index = cpu_rmap_add(rmap, glue);
262 rc = irq_set_affinity_notifier(irq, &glue->notify);
263 if (rc)
264 kfree(glue);
265 return rc;
266}
267EXPORT_SYMBOL(irq_cpu_rmap_add);
268
269#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)
249 249
250static void debug_print_object(struct debug_obj *obj, char *msg) 250static void debug_print_object(struct debug_obj *obj, char *msg)
251{ 251{
252 struct debug_obj_descr *descr = obj->descr;
252 static int limit; 253 static int limit;
253 254
254 if (limit < 5 && obj->descr != descr_test) { 255 if (limit < 5 && descr != descr_test) {
256 void *hint = descr->debug_hint ?
257 descr->debug_hint(obj->object) : NULL;
255 limit++; 258 limit++;
256 WARN(1, KERN_ERR "ODEBUG: %s %s (active state %u) " 259 WARN(1, KERN_ERR "ODEBUG: %s %s (active state %u) "
257 "object type: %s\n", 260 "object type: %s hint: %pS\n",
258 msg, obj_states[obj->state], obj->astate, 261 msg, obj_states[obj->state], obj->astate,
259 obj->descr->name); 262 descr->name, hint);
260 } 263 }
261 debug_objects_warnings++; 264 debug_objects_warnings++;
262} 265}
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 @@
83 * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536 83 * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
84 * = 128 + (uncompressed_size >> 12) + 65536 84 * = 128 + (uncompressed_size >> 12) + 65536
85 * 85 *
86 * For comparision, according to arch/x86/boot/compressed/misc.c, the 86 * For comparison, according to arch/x86/boot/compressed/misc.c, the
87 * equivalent formula for Deflate is this: 87 * equivalent formula for Deflate is this:
88 * 88 *
89 * safety_margin = 18 + (uncompressed_size >> 12) + 32768 89 * 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:
649 return -ENOMEM; 649 return -ENOMEM;
650} 650}
651 651
652static int device_dma_allocations(struct device *dev) 652static int device_dma_allocations(struct device *dev, struct dma_debug_entry **out_entry)
653{ 653{
654 struct dma_debug_entry *entry; 654 struct dma_debug_entry *entry;
655 unsigned long flags; 655 unsigned long flags;
@@ -660,8 +660,10 @@ static int device_dma_allocations(struct device *dev)
660 for (i = 0; i < HASH_SIZE; ++i) { 660 for (i = 0; i < HASH_SIZE; ++i) {
661 spin_lock(&dma_entry_hash[i].lock); 661 spin_lock(&dma_entry_hash[i].lock);
662 list_for_each_entry(entry, &dma_entry_hash[i].list, list) { 662 list_for_each_entry(entry, &dma_entry_hash[i].list, list) {
663 if (entry->dev == dev) 663 if (entry->dev == dev) {
664 count += 1; 664 count += 1;
665 *out_entry = entry;
666 }
665 } 667 }
666 spin_unlock(&dma_entry_hash[i].lock); 668 spin_unlock(&dma_entry_hash[i].lock);
667 } 669 }
@@ -674,6 +676,7 @@ static int device_dma_allocations(struct device *dev)
674static int dma_debug_device_change(struct notifier_block *nb, unsigned long action, void *data) 676static int dma_debug_device_change(struct notifier_block *nb, unsigned long action, void *data)
675{ 677{
676 struct device *dev = data; 678 struct device *dev = data;
679 struct dma_debug_entry *uninitialized_var(entry);
677 int count; 680 int count;
678 681
679 if (global_disable) 682 if (global_disable)
@@ -681,12 +684,17 @@ static int dma_debug_device_change(struct notifier_block *nb, unsigned long acti
681 684
682 switch (action) { 685 switch (action) {
683 case BUS_NOTIFY_UNBOUND_DRIVER: 686 case BUS_NOTIFY_UNBOUND_DRIVER:
684 count = device_dma_allocations(dev); 687 count = device_dma_allocations(dev, &entry);
685 if (count == 0) 688 if (count == 0)
686 break; 689 break;
687 err_printk(dev, NULL, "DMA-API: device driver has pending " 690 err_printk(dev, entry, "DMA-API: device driver has pending "
688 "DMA allocations while released from device " 691 "DMA allocations while released from device "
689 "[count=%d]\n", count); 692 "[count=%d]\n"
693 "One of leaked entries details: "
694 "[device address=0x%016llx] [size=%llu bytes] "
695 "[mapped with %s] [mapped as %s]\n",
696 count, entry->dev_addr, entry->size,
697 dir2name[entry->direction], type2name[entry->type]);
690 break; 698 break;
691 default: 699 default:
692 break; 700 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 @@
7 * Copyright (C) 2008 Jason Baron <jbaron@redhat.com> 7 * Copyright (C) 2008 Jason Baron <jbaron@redhat.com>
8 * By Greg Banks <gnb@melbourne.sgi.com> 8 * By Greg Banks <gnb@melbourne.sgi.com>
9 * Copyright (c) 2008 Silicon Graphics Inc. All Rights Reserved. 9 * Copyright (c) 2008 Silicon Graphics Inc. All Rights Reserved.
10 * Copyright (C) 2011 Bart Van Assche. All Rights Reserved.
10 */ 11 */
11 12
12#include <linux/kernel.h> 13#include <linux/kernel.h>
@@ -27,6 +28,8 @@
27#include <linux/debugfs.h> 28#include <linux/debugfs.h>
28#include <linux/slab.h> 29#include <linux/slab.h>
29#include <linux/jump_label.h> 30#include <linux/jump_label.h>
31#include <linux/hardirq.h>
32#include <linux/sched.h>
30 33
31extern struct _ddebug __start___verbose[]; 34extern struct _ddebug __start___verbose[];
32extern struct _ddebug __stop___verbose[]; 35extern struct _ddebug __stop___verbose[];
@@ -63,15 +66,25 @@ static inline const char *basename(const char *path)
63 return tail ? tail+1 : path; 66 return tail ? tail+1 : path;
64} 67}
65 68
69static struct { unsigned flag:8; char opt_char; } opt_array[] = {
70 { _DPRINTK_FLAGS_PRINT, 'p' },
71 { _DPRINTK_FLAGS_INCL_MODNAME, 'm' },
72 { _DPRINTK_FLAGS_INCL_FUNCNAME, 'f' },
73 { _DPRINTK_FLAGS_INCL_LINENO, 'l' },
74 { _DPRINTK_FLAGS_INCL_TID, 't' },
75};
76
66/* format a string into buf[] which describes the _ddebug's flags */ 77/* format a string into buf[] which describes the _ddebug's flags */
67static char *ddebug_describe_flags(struct _ddebug *dp, char *buf, 78static char *ddebug_describe_flags(struct _ddebug *dp, char *buf,
68 size_t maxlen) 79 size_t maxlen)
69{ 80{
70 char *p = buf; 81 char *p = buf;
82 int i;
71 83
72 BUG_ON(maxlen < 4); 84 BUG_ON(maxlen < 4);
73 if (dp->flags & _DPRINTK_FLAGS_PRINT) 85 for (i = 0; i < ARRAY_SIZE(opt_array); ++i)
74 *p++ = 'p'; 86 if (dp->flags & opt_array[i].flag)
87 *p++ = opt_array[i].opt_char;
75 if (p == buf) 88 if (p == buf)
76 *p++ = '-'; 89 *p++ = '-';
77 *p = '\0'; 90 *p = '\0';
@@ -343,7 +356,7 @@ static int ddebug_parse_flags(const char *str, unsigned int *flagsp,
343 unsigned int *maskp) 356 unsigned int *maskp)
344{ 357{
345 unsigned flags = 0; 358 unsigned flags = 0;
346 int op = '='; 359 int op = '=', i;
347 360
348 switch (*str) { 361 switch (*str) {
349 case '+': 362 case '+':
@@ -358,13 +371,14 @@ static int ddebug_parse_flags(const char *str, unsigned int *flagsp,
358 printk(KERN_INFO "%s: op='%c'\n", __func__, op); 371 printk(KERN_INFO "%s: op='%c'\n", __func__, op);
359 372
360 for ( ; *str ; ++str) { 373 for ( ; *str ; ++str) {
361 switch (*str) { 374 for (i = ARRAY_SIZE(opt_array) - 1; i >= 0; i--) {
362 case 'p': 375 if (*str == opt_array[i].opt_char) {
363 flags |= _DPRINTK_FLAGS_PRINT; 376 flags |= opt_array[i].flag;
364 break; 377 break;
365 default: 378 }
366 return -EINVAL;
367 } 379 }
380 if (i < 0)
381 return -EINVAL;
368 } 382 }
369 if (flags == 0) 383 if (flags == 0)
370 return -EINVAL; 384 return -EINVAL;
@@ -413,6 +427,35 @@ static int ddebug_exec_query(char *query_string)
413 return 0; 427 return 0;
414} 428}
415 429
430int __dynamic_pr_debug(struct _ddebug *descriptor, const char *fmt, ...)
431{
432 va_list args;
433 int res;
434
435 BUG_ON(!descriptor);
436 BUG_ON(!fmt);
437
438 va_start(args, fmt);
439 res = printk(KERN_DEBUG);
440 if (descriptor->flags & _DPRINTK_FLAGS_INCL_TID) {
441 if (in_interrupt())
442 res += printk(KERN_CONT "<intr> ");
443 else
444 res += printk(KERN_CONT "[%d] ", task_pid_vnr(current));
445 }
446 if (descriptor->flags & _DPRINTK_FLAGS_INCL_MODNAME)
447 res += printk(KERN_CONT "%s:", descriptor->modname);
448 if (descriptor->flags & _DPRINTK_FLAGS_INCL_FUNCNAME)
449 res += printk(KERN_CONT "%s:", descriptor->function);
450 if (descriptor->flags & _DPRINTK_FLAGS_INCL_LINENO)
451 res += printk(KERN_CONT "%d ", descriptor->lineno);
452 res += vprintk(fmt, args);
453 va_end(args);
454
455 return res;
456}
457EXPORT_SYMBOL(__dynamic_pr_debug);
458
416static __initdata char ddebug_setup_string[1024]; 459static __initdata char ddebug_setup_string[1024];
417static __init int ddebug_setup_query(char *str) 460static __init int ddebug_setup_query(char *str)
418{ 461{
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);
160#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ 160#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
161 161
162#ifdef __BIG_ENDIAN 162#ifdef __BIG_ENDIAN
163#ifdef CONFIG_GENERIC_FIND_BIT_LE
163 164
164/* include/linux/byteorder does not support "unsigned long" type */ 165/* include/linux/byteorder does not support "unsigned long" type */
165static inline unsigned long ext2_swabp(const unsigned long * x) 166static inline unsigned long ext2_swabp(const unsigned long * x)
@@ -185,15 +186,16 @@ static inline unsigned long ext2_swab(const unsigned long y)
185#endif 186#endif
186} 187}
187 188
188unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned 189unsigned long find_next_zero_bit_le(const void *addr, unsigned
189 long size, unsigned long offset) 190 long size, unsigned long offset)
190{ 191{
191 const unsigned long *p = addr + BITOP_WORD(offset); 192 const unsigned long *p = addr;
192 unsigned long result = offset & ~(BITS_PER_LONG - 1); 193 unsigned long result = offset & ~(BITS_PER_LONG - 1);
193 unsigned long tmp; 194 unsigned long tmp;
194 195
195 if (offset >= size) 196 if (offset >= size)
196 return size; 197 return size;
198 p += BITOP_WORD(offset);
197 size -= result; 199 size -= result;
198 offset &= (BITS_PER_LONG - 1UL); 200 offset &= (BITS_PER_LONG - 1UL);
199 if (offset) { 201 if (offset) {
@@ -226,18 +228,18 @@ found_middle:
226found_middle_swap: 228found_middle_swap:
227 return result + ffz(ext2_swab(tmp)); 229 return result + ffz(ext2_swab(tmp));
228} 230}
231EXPORT_SYMBOL(find_next_zero_bit_le);
229 232
230EXPORT_SYMBOL(generic_find_next_zero_le_bit); 233unsigned long find_next_bit_le(const void *addr, unsigned
231
232unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
233 long size, unsigned long offset) 234 long size, unsigned long offset)
234{ 235{
235 const unsigned long *p = addr + BITOP_WORD(offset); 236 const unsigned long *p = addr;
236 unsigned long result = offset & ~(BITS_PER_LONG - 1); 237 unsigned long result = offset & ~(BITS_PER_LONG - 1);
237 unsigned long tmp; 238 unsigned long tmp;
238 239
239 if (offset >= size) 240 if (offset >= size)
240 return size; 241 return size;
242 p += BITOP_WORD(offset);
241 size -= result; 243 size -= result;
242 offset &= (BITS_PER_LONG - 1UL); 244 offset &= (BITS_PER_LONG - 1UL);
243 if (offset) { 245 if (offset) {
@@ -271,5 +273,7 @@ found_middle:
271found_middle_swap: 273found_middle_swap:
272 return result + __ffs(ext2_swab(tmp)); 274 return result + __ffs(ext2_swab(tmp));
273} 275}
274EXPORT_SYMBOL(generic_find_next_le_bit); 276EXPORT_SYMBOL(find_next_bit_le);
277
278#endif /* CONFIG_GENERIC_FIND_BIT_LE */
275#endif /* __BIG_ENDIAN */ 279#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 @@
1/*
2 * lib/kernel_lock.c
3 *
4 * This is the traditional BKL - big kernel lock. Largely
5 * relegated to obsolescence, but used by various less
6 * important (or lazy) subsystems.
7 */
8#include <linux/module.h>
9#include <linux/kallsyms.h>
10#include <linux/semaphore.h>
11#include <linux/smp_lock.h>
12
13#define CREATE_TRACE_POINTS
14#include <trace/events/bkl.h>
15
16/*
17 * The 'big kernel lock'
18 *
19 * This spinlock is taken and released recursively by lock_kernel()
20 * and unlock_kernel(). It is transparently dropped and reacquired
21 * over schedule(). It is used to protect legacy code that hasn't
22 * been migrated to a proper locking design yet.
23 *
24 * Don't use in new code.
25 */
26static __cacheline_aligned_in_smp DEFINE_RAW_SPINLOCK(kernel_flag);
27
28
29/*
30 * Acquire/release the underlying lock from the scheduler.
31 *
32 * This is called with preemption disabled, and should
33 * return an error value if it cannot get the lock and
34 * TIF_NEED_RESCHED gets set.
35 *
36 * If it successfully gets the lock, it should increment
37 * the preemption count like any spinlock does.
38 *
39 * (This works on UP too - do_raw_spin_trylock will never
40 * return false in that case)
41 */
42int __lockfunc __reacquire_kernel_lock(void)
43{
44 while (!do_raw_spin_trylock(&kernel_flag)) {
45 if (need_resched())
46 return -EAGAIN;
47 cpu_relax();
48 }
49 preempt_disable();
50 return 0;
51}
52
53void __lockfunc __release_kernel_lock(void)
54{
55 do_raw_spin_unlock(&kernel_flag);
56 preempt_enable_no_resched();
57}
58
59/*
60 * These are the BKL spinlocks - we try to be polite about preemption.
61 * If SMP is not on (ie UP preemption), this all goes away because the
62 * do_raw_spin_trylock() will always succeed.
63 */
64#ifdef CONFIG_PREEMPT
65static inline void __lock_kernel(void)
66{
67 preempt_disable();
68 if (unlikely(!do_raw_spin_trylock(&kernel_flag))) {
69 /*
70 * If preemption was disabled even before this
71 * was called, there's nothing we can be polite
72 * about - just spin.
73 */
74 if (preempt_count() > 1) {
75 do_raw_spin_lock(&kernel_flag);
76 return;
77 }
78
79 /*
80 * Otherwise, let's wait for the kernel lock
81 * with preemption enabled..
82 */
83 do {
84 preempt_enable();
85 while (raw_spin_is_locked(&kernel_flag))
86 cpu_relax();
87 preempt_disable();
88 } while (!do_raw_spin_trylock(&kernel_flag));
89 }
90}
91
92#else
93
94/*
95 * Non-preemption case - just get the spinlock
96 */
97static inline void __lock_kernel(void)
98{
99 do_raw_spin_lock(&kernel_flag);
100}
101#endif
102
103static inline void __unlock_kernel(void)
104{
105 /*
106 * the BKL is not covered by lockdep, so we open-code the
107 * unlocking sequence (and thus avoid the dep-chain ops):
108 */
109 do_raw_spin_unlock(&kernel_flag);
110 preempt_enable();
111}
112
113/*
114 * Getting the big kernel lock.
115 *
116 * This cannot happen asynchronously, so we only need to
117 * worry about other CPU's.
118 */
119void __lockfunc _lock_kernel(const char *func, const char *file, int line)
120{
121 int depth = current->lock_depth + 1;
122
123 trace_lock_kernel(func, file, line);
124
125 if (likely(!depth)) {
126 might_sleep();
127 __lock_kernel();
128 }
129 current->lock_depth = depth;
130}
131
132void __lockfunc _unlock_kernel(const char *func, const char *file, int line)
133{
134 BUG_ON(current->lock_depth < 0);
135 if (likely(--current->lock_depth < 0))
136 __unlock_kernel();
137
138 trace_unlock_kernel(func, file, line);
139}
140
141EXPORT_SYMBOL(_lock_kernel);
142EXPORT_SYMBOL(_unlock_kernel);
143
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 @@
1/*
2 * Convert integer string representation to an integer.
3 * If an integer doesn't fit into specified type, -E is returned.
4 *
5 * Integer starts with optional sign.
6 * kstrtou*() functions do not accept sign "-".
7 *
8 * Radix 0 means autodetection: leading "0x" implies radix 16,
9 * leading "0" implies radix 8, otherwise radix is 10.
10 * Autodetection hints work after optional sign, but not before.
11 *
12 * If -E is returned, result is not touched.
13 */
14#include <linux/ctype.h>
15#include <linux/errno.h>
16#include <linux/kernel.h>
17#include <linux/math64.h>
18#include <linux/module.h>
19#include <linux/types.h>
20
21static inline char _tolower(const char c)
22{
23 return c | 0x20;
24}
25
26static int _kstrtoull(const char *s, unsigned int base, unsigned long long *res)
27{
28 unsigned long long acc;
29 int ok;
30
31 if (base == 0) {
32 if (s[0] == '0') {
33 if (_tolower(s[1]) == 'x' && isxdigit(s[2]))
34 base = 16;
35 else
36 base = 8;
37 } else
38 base = 10;
39 }
40 if (base == 16 && s[0] == '0' && _tolower(s[1]) == 'x')
41 s += 2;
42
43 acc = 0;
44 ok = 0;
45 while (*s) {
46 unsigned int val;
47
48 if ('0' <= *s && *s <= '9')
49 val = *s - '0';
50 else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
51 val = _tolower(*s) - 'a' + 10;
52 else if (*s == '\n' && *(s + 1) == '\0')
53 break;
54 else
55 return -EINVAL;
56
57 if (val >= base)
58 return -EINVAL;
59 if (acc > div_u64(ULLONG_MAX - val, base))
60 return -ERANGE;
61 acc = acc * base + val;
62 ok = 1;
63
64 s++;
65 }
66 if (!ok)
67 return -EINVAL;
68 *res = acc;
69 return 0;
70}
71
72int kstrtoull(const char *s, unsigned int base, unsigned long long *res)
73{
74 if (s[0] == '+')
75 s++;
76 return _kstrtoull(s, base, res);
77}
78EXPORT_SYMBOL(kstrtoull);
79
80int kstrtoll(const char *s, unsigned int base, long long *res)
81{
82 unsigned long long tmp;
83 int rv;
84
85 if (s[0] == '-') {
86 rv = _kstrtoull(s + 1, base, &tmp);
87 if (rv < 0)
88 return rv;
89 if ((long long)(-tmp) >= 0)
90 return -ERANGE;
91 *res = -tmp;
92 } else {
93 rv = kstrtoull(s, base, &tmp);
94 if (rv < 0)
95 return rv;
96 if ((long long)tmp < 0)
97 return -ERANGE;
98 *res = tmp;
99 }
100 return 0;
101}
102EXPORT_SYMBOL(kstrtoll);
103
104/* Internal, do not use. */
105int _kstrtoul(const char *s, unsigned int base, unsigned long *res)
106{
107 unsigned long long tmp;
108 int rv;
109
110 rv = kstrtoull(s, base, &tmp);
111 if (rv < 0)
112 return rv;
113 if (tmp != (unsigned long long)(unsigned long)tmp)
114 return -ERANGE;
115 *res = tmp;
116 return 0;
117}
118EXPORT_SYMBOL(_kstrtoul);
119
120/* Internal, do not use. */
121int _kstrtol(const char *s, unsigned int base, long *res)
122{
123 long long tmp;
124 int rv;
125
126 rv = kstrtoll(s, base, &tmp);
127 if (rv < 0)
128 return rv;
129 if (tmp != (long long)(long)tmp)
130 return -ERANGE;
131 *res = tmp;
132 return 0;
133}
134EXPORT_SYMBOL(_kstrtol);
135
136int kstrtouint(const char *s, unsigned int base, unsigned int *res)
137{
138 unsigned long long tmp;
139 int rv;
140
141 rv = kstrtoull(s, base, &tmp);
142 if (rv < 0)
143 return rv;
144 if (tmp != (unsigned long long)(unsigned int)tmp)
145 return -ERANGE;
146 *res = tmp;
147 return 0;
148}
149EXPORT_SYMBOL(kstrtouint);
150
151int kstrtoint(const char *s, unsigned int base, int *res)
152{
153 long long tmp;
154 int rv;
155
156 rv = kstrtoll(s, base, &tmp);
157 if (rv < 0)
158 return rv;
159 if (tmp != (long long)(int)tmp)
160 return -ERANGE;
161 *res = tmp;
162 return 0;
163}
164EXPORT_SYMBOL(kstrtoint);
165
166int kstrtou16(const char *s, unsigned int base, u16 *res)
167{
168 unsigned long long tmp;
169 int rv;
170
171 rv = kstrtoull(s, base, &tmp);
172 if (rv < 0)
173 return rv;
174 if (tmp != (unsigned long long)(u16)tmp)
175 return -ERANGE;
176 *res = tmp;
177 return 0;
178}
179EXPORT_SYMBOL(kstrtou16);
180
181int kstrtos16(const char *s, unsigned int base, s16 *res)
182{
183 long long tmp;
184 int rv;
185
186 rv = kstrtoll(s, base, &tmp);
187 if (rv < 0)
188 return rv;
189 if (tmp != (long long)(s16)tmp)
190 return -ERANGE;
191 *res = tmp;
192 return 0;
193}
194EXPORT_SYMBOL(kstrtos16);
195
196int kstrtou8(const char *s, unsigned int base, u8 *res)
197{
198 unsigned long long tmp;
199 int rv;
200
201 rv = kstrtoull(s, base, &tmp);
202 if (rv < 0)
203 return rv;
204 if (tmp != (unsigned long long)(u8)tmp)
205 return -ERANGE;
206 *res = tmp;
207 return 0;
208}
209EXPORT_SYMBOL(kstrtou8);
210
211int kstrtos8(const char *s, unsigned int base, s8 *res)
212{
213 long long tmp;
214 int rv;
215
216 rv = kstrtoll(s, base, &tmp);
217 if (rv < 0)
218 return rv;
219 if (tmp != (long long)(s8)tmp)
220 return -ERANGE;
221 *res = tmp;
222 return 0;
223}
224EXPORT_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 @@
13 13
14/** 14/**
15 * match_one: - Determines if a string matches a simple pattern 15 * match_one: - Determines if a string matches a simple pattern
16 * @s: the string to examine for presense of the pattern 16 * @s: the string to examine for presence of the pattern
17 * @p: the string containing the pattern 17 * @p: the string containing the pattern
18 * @args: array of %MAX_OPT_ARGS &substring_t elements. Used to return match 18 * @args: array of %MAX_OPT_ARGS &substring_t elements. Used to return match
19 * locations. 19 * 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 @@
28 28
29#ifdef CONFIG_DEBUG_PI_LIST 29#ifdef CONFIG_DEBUG_PI_LIST
30 30
31static struct plist_head test_head;
32
31static void plist_check_prev_next(struct list_head *t, struct list_head *p, 33static void plist_check_prev_next(struct list_head *t, struct list_head *p,
32 struct list_head *n) 34 struct list_head *n)
33{ 35{
@@ -54,12 +56,13 @@ static void plist_check_list(struct list_head *top)
54 56
55static void plist_check_head(struct plist_head *head) 57static void plist_check_head(struct plist_head *head)
56{ 58{
57 WARN_ON(!head->rawlock && !head->spinlock); 59 WARN_ON(head != &test_head && !head->rawlock && !head->spinlock);
58 if (head->rawlock) 60 if (head->rawlock)
59 WARN_ON_SMP(!raw_spin_is_locked(head->rawlock)); 61 WARN_ON_SMP(!raw_spin_is_locked(head->rawlock));
60 if (head->spinlock) 62 if (head->spinlock)
61 WARN_ON_SMP(!spin_is_locked(head->spinlock)); 63 WARN_ON_SMP(!spin_is_locked(head->spinlock));
62 plist_check_list(&head->prio_list); 64 if (!plist_head_empty(head))
65 plist_check_list(&plist_first(head)->prio_list);
63 plist_check_list(&head->node_list); 66 plist_check_list(&head->node_list);
64} 67}
65 68
@@ -75,25 +78,33 @@ static void plist_check_head(struct plist_head *head)
75 */ 78 */
76void plist_add(struct plist_node *node, struct plist_head *head) 79void plist_add(struct plist_node *node, struct plist_head *head)
77{ 80{
78 struct plist_node *iter; 81 struct plist_node *first, *iter, *prev = NULL;
82 struct list_head *node_next = &head->node_list;
79 83
80 plist_check_head(head); 84 plist_check_head(head);
81 WARN_ON(!plist_node_empty(node)); 85 WARN_ON(!plist_node_empty(node));
86 WARN_ON(!list_empty(&node->prio_list));
87
88 if (plist_head_empty(head))
89 goto ins_node;
82 90
83 list_for_each_entry(iter, &head->prio_list, plist.prio_list) { 91 first = iter = plist_first(head);
84 if (node->prio < iter->prio) 92
85 goto lt_prio; 93 do {
86 else if (node->prio == iter->prio) { 94 if (node->prio < iter->prio) {
87 iter = list_entry(iter->plist.prio_list.next, 95 node_next = &iter->node_list;
88 struct plist_node, plist.prio_list); 96 break;
89 goto eq_prio;
90 } 97 }
91 }
92 98
93lt_prio: 99 prev = iter;
94 list_add_tail(&node->plist.prio_list, &iter->plist.prio_list); 100 iter = list_entry(iter->prio_list.next,
95eq_prio: 101 struct plist_node, prio_list);
96 list_add_tail(&node->plist.node_list, &iter->plist.node_list); 102 } while (iter != first);
103
104 if (!prev || prev->prio != node->prio)
105 list_add_tail(&node->prio_list, &iter->prio_list);
106ins_node:
107 list_add_tail(&node->node_list, node_next);
97 108
98 plist_check_head(head); 109 plist_check_head(head);
99} 110}
@@ -108,14 +119,98 @@ void plist_del(struct plist_node *node, struct plist_head *head)
108{ 119{
109 plist_check_head(head); 120 plist_check_head(head);
110 121
111 if (!list_empty(&node->plist.prio_list)) { 122 if (!list_empty(&node->prio_list)) {
112 struct plist_node *next = plist_first(&node->plist); 123 if (node->node_list.next != &head->node_list) {
124 struct plist_node *next;
125
126 next = list_entry(node->node_list.next,
127 struct plist_node, node_list);
113 128
114 list_move_tail(&next->plist.prio_list, &node->plist.prio_list); 129 /* add the next plist_node into prio_list */
115 list_del_init(&node->plist.prio_list); 130 if (list_empty(&next->prio_list))
131 list_add(&next->prio_list, &node->prio_list);
132 }
133 list_del_init(&node->prio_list);
116 } 134 }
117 135
118 list_del_init(&node->plist.node_list); 136 list_del_init(&node->node_list);
119 137
120 plist_check_head(head); 138 plist_check_head(head);
121} 139}
140
141#ifdef CONFIG_DEBUG_PI_LIST
142#include <linux/sched.h>
143#include <linux/module.h>
144#include <linux/init.h>
145
146static struct plist_node __initdata test_node[241];
147
148static void __init plist_test_check(int nr_expect)
149{
150 struct plist_node *first, *prio_pos, *node_pos;
151
152 if (plist_head_empty(&test_head)) {
153 BUG_ON(nr_expect != 0);
154 return;
155 }
156
157 prio_pos = first = plist_first(&test_head);
158 plist_for_each(node_pos, &test_head) {
159 if (nr_expect-- < 0)
160 break;
161 if (node_pos == first)
162 continue;
163 if (node_pos->prio == prio_pos->prio) {
164 BUG_ON(!list_empty(&node_pos->prio_list));
165 continue;
166 }
167
168 BUG_ON(prio_pos->prio > node_pos->prio);
169 BUG_ON(prio_pos->prio_list.next != &node_pos->prio_list);
170 prio_pos = node_pos;
171 }
172
173 BUG_ON(nr_expect != 0);
174 BUG_ON(prio_pos->prio_list.next != &first->prio_list);
175}
176
177static int __init plist_test(void)
178{
179 int nr_expect = 0, i, loop;
180 unsigned int r = local_clock();
181
182 printk(KERN_INFO "start plist test\n");
183 plist_head_init(&test_head, NULL);
184 for (i = 0; i < ARRAY_SIZE(test_node); i++)
185 plist_node_init(test_node + i, 0);
186
187 for (loop = 0; loop < 1000; loop++) {
188 r = r * 193939 % 47629;
189 i = r % ARRAY_SIZE(test_node);
190 if (plist_node_empty(test_node + i)) {
191 r = r * 193939 % 47629;
192 test_node[i].prio = r % 99;
193 plist_add(test_node + i, &test_head);
194 nr_expect++;
195 } else {
196 plist_del(test_node + i, &test_head);
197 nr_expect--;
198 }
199 plist_test_check(nr_expect);
200 }
201
202 for (i = 0; i < ARRAY_SIZE(test_node); i++) {
203 if (plist_node_empty(test_node + i))
204 continue;
205 plist_del(test_node + i, &test_head);
206 nr_expect--;
207 plist_test_check(nr_expect);
208 }
209
210 printk(KERN_INFO "end plist test\n");
211 return 0;
212}
213
214module_init(plist_test);
215
216#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,
222/* 222/*
223 * wait for the read lock to be granted 223 * wait for the read lock to be granted
224 */ 224 */
225asmregparm struct rw_semaphore __sched * 225struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
226rwsem_down_read_failed(struct rw_semaphore *sem)
227{ 226{
228 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_READ, 227 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_READ,
229 -RWSEM_ACTIVE_READ_BIAS); 228 -RWSEM_ACTIVE_READ_BIAS);
@@ -232,8 +231,7 @@ rwsem_down_read_failed(struct rw_semaphore *sem)
232/* 231/*
233 * wait for the write lock to be granted 232 * wait for the write lock to be granted
234 */ 233 */
235asmregparm struct rw_semaphore __sched * 234struct rw_semaphore __sched *rwsem_down_write_failed(struct rw_semaphore *sem)
236rwsem_down_write_failed(struct rw_semaphore *sem)
237{ 235{
238 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_WRITE, 236 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_WRITE,
239 -RWSEM_ACTIVE_WRITE_BIAS); 237 -RWSEM_ACTIVE_WRITE_BIAS);
@@ -243,7 +241,7 @@ rwsem_down_write_failed(struct rw_semaphore *sem)
243 * handle waking up a waiter on the semaphore 241 * handle waking up a waiter on the semaphore
244 * - up_read/up_write has decremented the active part of count if we come here 242 * - up_read/up_write has decremented the active part of count if we come here
245 */ 243 */
246asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem) 244struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
247{ 245{
248 unsigned long flags; 246 unsigned long flags;
249 247
@@ -263,7 +261,7 @@ asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
263 * - caller incremented waiting part of count and discovered it still negative 261 * - caller incremented waiting part of count and discovered it still negative
264 * - just wake up any readers at the front of the queue 262 * - just wake up any readers at the front of the queue
265 */ 263 */
266asmregparm struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem) 264struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem)
267{ 265{
268 unsigned long flags; 266 unsigned long flags;
269 267
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 @@
9#include <linux/nmi.h> 9#include <linux/nmi.h>
10#include <linux/quicklist.h> 10#include <linux/quicklist.h>
11 11
12void show_mem(void) 12void show_mem(unsigned int filter)
13{ 13{
14 pg_data_t *pgdat; 14 pg_data_t *pgdat;
15 unsigned long total = 0, reserved = 0, shared = 0, 15 unsigned long total = 0, reserved = 0, shared = 0,
16 nonshared = 0, highmem = 0; 16 nonshared = 0, highmem = 0;
17 17
18 printk("Mem-Info:\n"); 18 printk("Mem-Info:\n");
19 show_free_areas(); 19 __show_free_areas(filter);
20 20
21 for_each_online_pgdat(pgdat) { 21 for_each_online_pgdat(pgdat) {
22 unsigned long i, flags; 22 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)
535} 535}
536EXPORT_SYMBOL(sysfs_streq); 536EXPORT_SYMBOL(sysfs_streq);
537 537
538/**
539 * strtobool - convert common user inputs into boolean values
540 * @s: input string
541 * @res: result
542 *
543 * This routine returns 0 iff the first character is one of 'Yy1Nn0'.
544 * Otherwise it will return -EINVAL. Value pointed to by res is
545 * updated upon finding a match.
546 */
547int strtobool(const char *s, bool *res)
548{
549 switch (s[0]) {
550 case 'y':
551 case 'Y':
552 case '1':
553 *res = true;
554 break;
555 case 'n':
556 case 'N':
557 case '0':
558 *res = false;
559 break;
560 default:
561 return -EINVAL;
562 }
563 return 0;
564}
565EXPORT_SYMBOL(strtobool);
566
538#ifndef __HAVE_ARCH_MEMSET 567#ifndef __HAVE_ARCH_MEMSET
539/** 568/**
540 * memset - Fill a region of memory with the given value 569 * 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 @@
1#include <linux/init.h>
2#include <linux/kernel.h>
3#include <linux/module.h>
4
5#define for_each_test(i, test) \
6 for (i = 0; i < sizeof(test) / sizeof(test[0]); i++)
7
8struct test_fail {
9 const char *str;
10 unsigned int base;
11};
12
13#define DEFINE_TEST_FAIL(test) \
14 const struct test_fail test[] __initdata
15
16#define DECLARE_TEST_OK(type, test_type) \
17 test_type { \
18 const char *str; \
19 unsigned int base; \
20 type expected_res; \
21 }
22
23#define DEFINE_TEST_OK(type, test) \
24 const type test[] __initdata
25
26#define TEST_FAIL(fn, type, fmt, test) \
27{ \
28 unsigned int i; \
29 \
30 for_each_test(i, test) { \
31 const struct test_fail *t = &test[i]; \
32 type tmp; \
33 int rv; \
34 \
35 tmp = 0; \
36 rv = fn(t->str, t->base, &tmp); \
37 if (rv >= 0) { \
38 WARN(1, "str '%s', base %u, expected -E, got %d/" fmt "\n", \
39 t->str, t->base, rv, tmp); \
40 continue; \
41 } \
42 } \
43}
44
45#define TEST_OK(fn, type, fmt, test) \
46{ \
47 unsigned int i; \
48 \
49 for_each_test(i, test) { \
50 const typeof(test[0]) *t = &test[i]; \
51 type res; \
52 int rv; \
53 \
54 rv = fn(t->str, t->base, &res); \
55 if (rv != 0) { \
56 WARN(1, "str '%s', base %u, expected 0/" fmt ", got %d\n", \
57 t->str, t->base, t->expected_res, rv); \
58 continue; \
59 } \
60 if (res != t->expected_res) { \
61 WARN(1, "str '%s', base %u, expected " fmt ", got " fmt "\n", \
62 t->str, t->base, t->expected_res, res); \
63 continue; \
64 } \
65 } \
66}
67
68static void __init test_kstrtoull_ok(void)
69{
70 DECLARE_TEST_OK(unsigned long long, struct test_ull);
71 static DEFINE_TEST_OK(struct test_ull, test_ull_ok) = {
72 {"0", 10, 0ULL},
73 {"1", 10, 1ULL},
74 {"127", 10, 127ULL},
75 {"128", 10, 128ULL},
76 {"129", 10, 129ULL},
77 {"255", 10, 255ULL},
78 {"256", 10, 256ULL},
79 {"257", 10, 257ULL},
80 {"32767", 10, 32767ULL},
81 {"32768", 10, 32768ULL},
82 {"32769", 10, 32769ULL},
83 {"65535", 10, 65535ULL},
84 {"65536", 10, 65536ULL},
85 {"65537", 10, 65537ULL},
86 {"2147483647", 10, 2147483647ULL},
87 {"2147483648", 10, 2147483648ULL},
88 {"2147483649", 10, 2147483649ULL},
89 {"4294967295", 10, 4294967295ULL},
90 {"4294967296", 10, 4294967296ULL},
91 {"4294967297", 10, 4294967297ULL},
92 {"9223372036854775807", 10, 9223372036854775807ULL},
93 {"9223372036854775808", 10, 9223372036854775808ULL},
94 {"9223372036854775809", 10, 9223372036854775809ULL},
95 {"18446744073709551614", 10, 18446744073709551614ULL},
96 {"18446744073709551615", 10, 18446744073709551615ULL},
97
98 {"00", 8, 00ULL},
99 {"01", 8, 01ULL},
100 {"0177", 8, 0177ULL},
101 {"0200", 8, 0200ULL},
102 {"0201", 8, 0201ULL},
103 {"0377", 8, 0377ULL},
104 {"0400", 8, 0400ULL},
105 {"0401", 8, 0401ULL},
106 {"077777", 8, 077777ULL},
107 {"0100000", 8, 0100000ULL},
108 {"0100001", 8, 0100001ULL},
109 {"0177777", 8, 0177777ULL},
110 {"0200000", 8, 0200000ULL},
111 {"0200001", 8, 0200001ULL},
112 {"017777777777", 8, 017777777777ULL},
113 {"020000000000", 8, 020000000000ULL},
114 {"020000000001", 8, 020000000001ULL},
115 {"037777777777", 8, 037777777777ULL},
116 {"040000000000", 8, 040000000000ULL},
117 {"040000000001", 8, 040000000001ULL},
118 {"0777777777777777777777", 8, 0777777777777777777777ULL},
119 {"01000000000000000000000", 8, 01000000000000000000000ULL},
120 {"01000000000000000000001", 8, 01000000000000000000001ULL},
121 {"01777777777777777777776", 8, 01777777777777777777776ULL},
122 {"01777777777777777777777", 8, 01777777777777777777777ULL},
123
124 {"0x0", 16, 0x0ULL},
125 {"0x1", 16, 0x1ULL},
126 {"0x7f", 16, 0x7fULL},
127 {"0x80", 16, 0x80ULL},
128 {"0x81", 16, 0x81ULL},
129 {"0xff", 16, 0xffULL},
130 {"0x100", 16, 0x100ULL},
131 {"0x101", 16, 0x101ULL},
132 {"0x7fff", 16, 0x7fffULL},
133 {"0x8000", 16, 0x8000ULL},
134 {"0x8001", 16, 0x8001ULL},
135 {"0xffff", 16, 0xffffULL},
136 {"0x10000", 16, 0x10000ULL},
137 {"0x10001", 16, 0x10001ULL},
138 {"0x7fffffff", 16, 0x7fffffffULL},
139 {"0x80000000", 16, 0x80000000ULL},
140 {"0x80000001", 16, 0x80000001ULL},
141 {"0xffffffff", 16, 0xffffffffULL},
142 {"0x100000000", 16, 0x100000000ULL},
143 {"0x100000001", 16, 0x100000001ULL},
144 {"0x7fffffffffffffff", 16, 0x7fffffffffffffffULL},
145 {"0x8000000000000000", 16, 0x8000000000000000ULL},
146 {"0x8000000000000001", 16, 0x8000000000000001ULL},
147 {"0xfffffffffffffffe", 16, 0xfffffffffffffffeULL},
148 {"0xffffffffffffffff", 16, 0xffffffffffffffffULL},
149
150 {"0\n", 0, 0ULL},
151 };
152 TEST_OK(kstrtoull, unsigned long long, "%llu", test_ull_ok);
153}
154
155static void __init test_kstrtoull_fail(void)
156{
157 static DEFINE_TEST_FAIL(test_ull_fail) = {
158 {"", 0},
159 {"", 8},
160 {"", 10},
161 {"", 16},
162 {"\n", 0},
163 {"\n", 8},
164 {"\n", 10},
165 {"\n", 16},
166 {"\n0", 0},
167 {"\n0", 8},
168 {"\n0", 10},
169 {"\n0", 16},
170 {"+", 0},
171 {"+", 8},
172 {"+", 10},
173 {"+", 16},
174 {"-", 0},
175 {"-", 8},
176 {"-", 10},
177 {"-", 16},
178 {"0x", 0},
179 {"0x", 16},
180 {"0X", 0},
181 {"0X", 16},
182 {"0 ", 0},
183 {"1+", 0},
184 {"1-", 0},
185 {" 2", 0},
186 /* base autodetection */
187 {"0x0z", 0},
188 {"0z", 0},
189 {"a", 0},
190 /* digit >= base */
191 {"2", 2},
192 {"8", 8},
193 {"a", 10},
194 {"A", 10},
195 {"g", 16},
196 {"G", 16},
197 /* overflow */
198 {"10000000000000000000000000000000000000000000000000000000000000000", 2},
199 {"2000000000000000000000", 8},
200 {"18446744073709551616", 10},
201 {"10000000000000000", 16},
202 /* negative */
203 {"-0", 0},
204 {"-0", 8},
205 {"-0", 10},
206 {"-0", 16},
207 {"-1", 0},
208 {"-1", 8},
209 {"-1", 10},
210 {"-1", 16},
211 /* sign is first character if any */
212 {"-+1", 0},
213 {"-+1", 8},
214 {"-+1", 10},
215 {"-+1", 16},
216 /* nothing after \n */
217 {"0\n0", 0},
218 {"0\n0", 8},
219 {"0\n0", 10},
220 {"0\n0", 16},
221 {"0\n+", 0},
222 {"0\n+", 8},
223 {"0\n+", 10},
224 {"0\n+", 16},
225 {"0\n-", 0},
226 {"0\n-", 8},
227 {"0\n-", 10},
228 {"0\n-", 16},
229 {"0\n ", 0},
230 {"0\n ", 8},
231 {"0\n ", 10},
232 {"0\n ", 16},
233 };
234 TEST_FAIL(kstrtoull, unsigned long long, "%llu", test_ull_fail);
235}
236
237static void __init test_kstrtoll_ok(void)
238{
239 DECLARE_TEST_OK(long long, struct test_ll);
240 static DEFINE_TEST_OK(struct test_ll, test_ll_ok) = {
241 {"0", 10, 0LL},
242 {"1", 10, 1LL},
243 {"127", 10, 127LL},
244 {"128", 10, 128LL},
245 {"129", 10, 129LL},
246 {"255", 10, 255LL},
247 {"256", 10, 256LL},
248 {"257", 10, 257LL},
249 {"32767", 10, 32767LL},
250 {"32768", 10, 32768LL},
251 {"32769", 10, 32769LL},
252 {"65535", 10, 65535LL},
253 {"65536", 10, 65536LL},
254 {"65537", 10, 65537LL},
255 {"2147483647", 10, 2147483647LL},
256 {"2147483648", 10, 2147483648LL},
257 {"2147483649", 10, 2147483649LL},
258 {"4294967295", 10, 4294967295LL},
259 {"4294967296", 10, 4294967296LL},
260 {"4294967297", 10, 4294967297LL},
261 {"9223372036854775807", 10, 9223372036854775807LL},
262
263 {"-1", 10, -1LL},
264 {"-2", 10, -2LL},
265 {"-9223372036854775808", 10, LLONG_MIN},
266 };
267 TEST_OK(kstrtoll, long long, "%lld", test_ll_ok);
268}
269
270static void __init test_kstrtoll_fail(void)
271{
272 static DEFINE_TEST_FAIL(test_ll_fail) = {
273 {"9223372036854775808", 10},
274 {"9223372036854775809", 10},
275 {"18446744073709551614", 10},
276 {"18446744073709551615", 10},
277 {"-9223372036854775809", 10},
278 {"-18446744073709551614", 10},
279 {"-18446744073709551615", 10},
280 /* negative zero isn't an integer in Linux */
281 {"-0", 0},
282 {"-0", 8},
283 {"-0", 10},
284 {"-0", 16},
285 /* sign is first character if any */
286 {"-+1", 0},
287 {"-+1", 8},
288 {"-+1", 10},
289 {"-+1", 16},
290 };
291 TEST_FAIL(kstrtoll, long long, "%lld", test_ll_fail);
292}
293
294static void __init test_kstrtou64_ok(void)
295{
296 DECLARE_TEST_OK(u64, struct test_u64);
297 static DEFINE_TEST_OK(struct test_u64, test_u64_ok) = {
298 {"0", 10, 0},
299 {"1", 10, 1},
300 {"126", 10, 126},
301 {"127", 10, 127},
302 {"128", 10, 128},
303 {"129", 10, 129},
304 {"254", 10, 254},
305 {"255", 10, 255},
306 {"256", 10, 256},
307 {"257", 10, 257},
308 {"32766", 10, 32766},
309 {"32767", 10, 32767},
310 {"32768", 10, 32768},
311 {"32769", 10, 32769},
312 {"65534", 10, 65534},
313 {"65535", 10, 65535},
314 {"65536", 10, 65536},
315 {"65537", 10, 65537},
316 {"2147483646", 10, 2147483646},
317 {"2147483647", 10, 2147483647},
318 {"2147483648", 10, 2147483648ULL},
319 {"2147483649", 10, 2147483649ULL},
320 {"4294967294", 10, 4294967294ULL},
321 {"4294967295", 10, 4294967295ULL},
322 {"4294967296", 10, 4294967296ULL},
323 {"4294967297", 10, 4294967297ULL},
324 {"9223372036854775806", 10, 9223372036854775806ULL},
325 {"9223372036854775807", 10, 9223372036854775807ULL},
326 {"9223372036854775808", 10, 9223372036854775808ULL},
327 {"9223372036854775809", 10, 9223372036854775809ULL},
328 {"18446744073709551614", 10, 18446744073709551614ULL},
329 {"18446744073709551615", 10, 18446744073709551615ULL},
330 };
331 TEST_OK(kstrtou64, u64, "%llu", test_u64_ok);
332}
333
334static void __init test_kstrtou64_fail(void)
335{
336 static DEFINE_TEST_FAIL(test_u64_fail) = {
337 {"-2", 10},
338 {"-1", 10},
339 {"18446744073709551616", 10},
340 {"18446744073709551617", 10},
341 };
342 TEST_FAIL(kstrtou64, u64, "%llu", test_u64_fail);
343}
344
345static void __init test_kstrtos64_ok(void)
346{
347 DECLARE_TEST_OK(s64, struct test_s64);
348 static DEFINE_TEST_OK(struct test_s64, test_s64_ok) = {
349 {"-128", 10, -128},
350 {"-127", 10, -127},
351 {"-1", 10, -1},
352 {"0", 10, 0},
353 {"1", 10, 1},
354 {"126", 10, 126},
355 {"127", 10, 127},
356 {"128", 10, 128},
357 {"129", 10, 129},
358 {"254", 10, 254},
359 {"255", 10, 255},
360 {"256", 10, 256},
361 {"257", 10, 257},
362 {"32766", 10, 32766},
363 {"32767", 10, 32767},
364 {"32768", 10, 32768},
365 {"32769", 10, 32769},
366 {"65534", 10, 65534},
367 {"65535", 10, 65535},
368 {"65536", 10, 65536},
369 {"65537", 10, 65537},
370 {"2147483646", 10, 2147483646},
371 {"2147483647", 10, 2147483647},
372 {"2147483648", 10, 2147483648LL},
373 {"2147483649", 10, 2147483649LL},
374 {"4294967294", 10, 4294967294LL},
375 {"4294967295", 10, 4294967295LL},
376 {"4294967296", 10, 4294967296LL},
377 {"4294967297", 10, 4294967297LL},
378 {"9223372036854775806", 10, 9223372036854775806LL},
379 {"9223372036854775807", 10, 9223372036854775807LL},
380 };
381 TEST_OK(kstrtos64, s64, "%lld", test_s64_ok);
382}
383
384static void __init test_kstrtos64_fail(void)
385{
386 static DEFINE_TEST_FAIL(test_s64_fail) = {
387 {"9223372036854775808", 10},
388 {"9223372036854775809", 10},
389 {"18446744073709551614", 10},
390 {"18446744073709551615", 10},
391 {"18446744073709551616", 10},
392 {"18446744073709551617", 10},
393 };
394 TEST_FAIL(kstrtos64, s64, "%lld", test_s64_fail);
395}
396
397static void __init test_kstrtou32_ok(void)
398{
399 DECLARE_TEST_OK(u32, struct test_u32);
400 static DEFINE_TEST_OK(struct test_u32, test_u32_ok) = {
401 {"0", 10, 0},
402 {"1", 10, 1},
403 {"126", 10, 126},
404 {"127", 10, 127},
405 {"128", 10, 128},
406 {"129", 10, 129},
407 {"254", 10, 254},
408 {"255", 10, 255},
409 {"256", 10, 256},
410 {"257", 10, 257},
411 {"32766", 10, 32766},
412 {"32767", 10, 32767},
413 {"32768", 10, 32768},
414 {"32769", 10, 32769},
415 {"65534", 10, 65534},
416 {"65535", 10, 65535},
417 {"65536", 10, 65536},
418 {"65537", 10, 65537},
419 {"2147483646", 10, 2147483646},
420 {"2147483647", 10, 2147483647},
421 {"2147483648", 10, 2147483648U},
422 {"2147483649", 10, 2147483649U},
423 {"4294967294", 10, 4294967294U},
424 {"4294967295", 10, 4294967295U},
425 };
426 TEST_OK(kstrtou32, u32, "%u", test_u32_ok);
427}
428
429static void __init test_kstrtou32_fail(void)
430{
431 static DEFINE_TEST_FAIL(test_u32_fail) = {
432 {"-2", 10},
433 {"-1", 10},
434 {"4294967296", 10},
435 {"4294967297", 10},
436 {"9223372036854775806", 10},
437 {"9223372036854775807", 10},
438 {"9223372036854775808", 10},
439 {"9223372036854775809", 10},
440 {"18446744073709551614", 10},
441 {"18446744073709551615", 10},
442 {"18446744073709551616", 10},
443 {"18446744073709551617", 10},
444 };
445 TEST_FAIL(kstrtou32, u32, "%u", test_u32_fail);
446}
447
448static void __init test_kstrtos32_ok(void)
449{
450 DECLARE_TEST_OK(s32, struct test_s32);
451 static DEFINE_TEST_OK(struct test_s32, test_s32_ok) = {
452 {"-128", 10, -128},
453 {"-127", 10, -127},
454 {"-1", 10, -1},
455 {"0", 10, 0},
456 {"1", 10, 1},
457 {"126", 10, 126},
458 {"127", 10, 127},
459 {"128", 10, 128},
460 {"129", 10, 129},
461 {"254", 10, 254},
462 {"255", 10, 255},
463 {"256", 10, 256},
464 {"257", 10, 257},
465 {"32766", 10, 32766},
466 {"32767", 10, 32767},
467 {"32768", 10, 32768},
468 {"32769", 10, 32769},
469 {"65534", 10, 65534},
470 {"65535", 10, 65535},
471 {"65536", 10, 65536},
472 {"65537", 10, 65537},
473 {"2147483646", 10, 2147483646},
474 {"2147483647", 10, 2147483647},
475 };
476 TEST_OK(kstrtos32, s32, "%d", test_s32_ok);
477}
478
479static void __init test_kstrtos32_fail(void)
480{
481 static DEFINE_TEST_FAIL(test_s32_fail) = {
482 {"2147483648", 10},
483 {"2147483649", 10},
484 {"4294967294", 10},
485 {"4294967295", 10},
486 {"4294967296", 10},
487 {"4294967297", 10},
488 {"9223372036854775806", 10},
489 {"9223372036854775807", 10},
490 {"9223372036854775808", 10},
491 {"9223372036854775809", 10},
492 {"18446744073709551614", 10},
493 {"18446744073709551615", 10},
494 {"18446744073709551616", 10},
495 {"18446744073709551617", 10},
496 };
497 TEST_FAIL(kstrtos32, s32, "%d", test_s32_fail);
498}
499
500static void __init test_kstrtou16_ok(void)
501{
502 DECLARE_TEST_OK(u16, struct test_u16);
503 static DEFINE_TEST_OK(struct test_u16, test_u16_ok) = {
504 {"0", 10, 0},
505 {"1", 10, 1},
506 {"126", 10, 126},
507 {"127", 10, 127},
508 {"128", 10, 128},
509 {"129", 10, 129},
510 {"254", 10, 254},
511 {"255", 10, 255},
512 {"256", 10, 256},
513 {"257", 10, 257},
514 {"32766", 10, 32766},
515 {"32767", 10, 32767},
516 {"32768", 10, 32768},
517 {"32769", 10, 32769},
518 {"65534", 10, 65534},
519 {"65535", 10, 65535},
520 };
521 TEST_OK(kstrtou16, u16, "%hu", test_u16_ok);
522}
523
524static void __init test_kstrtou16_fail(void)
525{
526 static DEFINE_TEST_FAIL(test_u16_fail) = {
527 {"-2", 10},
528 {"-1", 10},
529 {"65536", 10},
530 {"65537", 10},
531 {"2147483646", 10},
532 {"2147483647", 10},
533 {"2147483648", 10},
534 {"2147483649", 10},
535 {"4294967294", 10},
536 {"4294967295", 10},
537 {"4294967296", 10},
538 {"4294967297", 10},
539 {"9223372036854775806", 10},
540 {"9223372036854775807", 10},
541 {"9223372036854775808", 10},
542 {"9223372036854775809", 10},
543 {"18446744073709551614", 10},
544 {"18446744073709551615", 10},
545 {"18446744073709551616", 10},
546 {"18446744073709551617", 10},
547 };
548 TEST_FAIL(kstrtou16, u16, "%hu", test_u16_fail);
549}
550
551static void __init test_kstrtos16_ok(void)
552{
553 DECLARE_TEST_OK(s16, struct test_s16);
554 static DEFINE_TEST_OK(struct test_s16, test_s16_ok) = {
555 {"-130", 10, -130},
556 {"-129", 10, -129},
557 {"-128", 10, -128},
558 {"-127", 10, -127},
559 {"-1", 10, -1},
560 {"0", 10, 0},
561 {"1", 10, 1},
562 {"126", 10, 126},
563 {"127", 10, 127},
564 {"128", 10, 128},
565 {"129", 10, 129},
566 {"254", 10, 254},
567 {"255", 10, 255},
568 {"256", 10, 256},
569 {"257", 10, 257},
570 {"32766", 10, 32766},
571 {"32767", 10, 32767},
572 };
573 TEST_OK(kstrtos16, s16, "%hd", test_s16_ok);
574}
575
576static void __init test_kstrtos16_fail(void)
577{
578 static DEFINE_TEST_FAIL(test_s16_fail) = {
579 {"32768", 10},
580 {"32769", 10},
581 {"65534", 10},
582 {"65535", 10},
583 {"65536", 10},
584 {"65537", 10},
585 {"2147483646", 10},
586 {"2147483647", 10},
587 {"2147483648", 10},
588 {"2147483649", 10},
589 {"4294967294", 10},
590 {"4294967295", 10},
591 {"4294967296", 10},
592 {"4294967297", 10},
593 {"9223372036854775806", 10},
594 {"9223372036854775807", 10},
595 {"9223372036854775808", 10},
596 {"9223372036854775809", 10},
597 {"18446744073709551614", 10},
598 {"18446744073709551615", 10},
599 {"18446744073709551616", 10},
600 {"18446744073709551617", 10},
601 };
602 TEST_FAIL(kstrtos16, s16, "%hd", test_s16_fail);
603}
604
605static void __init test_kstrtou8_ok(void)
606{
607 DECLARE_TEST_OK(u8, struct test_u8);
608 static DEFINE_TEST_OK(struct test_u8, test_u8_ok) = {
609 {"0", 10, 0},
610 {"1", 10, 1},
611 {"126", 10, 126},
612 {"127", 10, 127},
613 {"128", 10, 128},
614 {"129", 10, 129},
615 {"254", 10, 254},
616 {"255", 10, 255},
617 };
618 TEST_OK(kstrtou8, u8, "%hhu", test_u8_ok);
619}
620
621static void __init test_kstrtou8_fail(void)
622{
623 static DEFINE_TEST_FAIL(test_u8_fail) = {
624 {"-2", 10},
625 {"-1", 10},
626 {"256", 10},
627 {"257", 10},
628 {"32766", 10},
629 {"32767", 10},
630 {"32768", 10},
631 {"32769", 10},
632 {"65534", 10},
633 {"65535", 10},
634 {"65536", 10},
635 {"65537", 10},
636 {"2147483646", 10},
637 {"2147483647", 10},
638 {"2147483648", 10},
639 {"2147483649", 10},
640 {"4294967294", 10},
641 {"4294967295", 10},
642 {"4294967296", 10},
643 {"4294967297", 10},
644 {"9223372036854775806", 10},
645 {"9223372036854775807", 10},
646 {"9223372036854775808", 10},
647 {"9223372036854775809", 10},
648 {"18446744073709551614", 10},
649 {"18446744073709551615", 10},
650 {"18446744073709551616", 10},
651 {"18446744073709551617", 10},
652 };
653 TEST_FAIL(kstrtou8, u8, "%hhu", test_u8_fail);
654}
655
656static void __init test_kstrtos8_ok(void)
657{
658 DECLARE_TEST_OK(s8, struct test_s8);
659 static DEFINE_TEST_OK(struct test_s8, test_s8_ok) = {
660 {"-128", 10, -128},
661 {"-127", 10, -127},
662 {"-1", 10, -1},
663 {"0", 10, 0},
664 {"1", 10, 1},
665 {"126", 10, 126},
666 {"127", 10, 127},
667 };
668 TEST_OK(kstrtos8, s8, "%hhd", test_s8_ok);
669}
670
671static void __init test_kstrtos8_fail(void)
672{
673 static DEFINE_TEST_FAIL(test_s8_fail) = {
674 {"-130", 10},
675 {"-129", 10},
676 {"128", 10},
677 {"129", 10},
678 {"254", 10},
679 {"255", 10},
680 {"256", 10},
681 {"257", 10},
682 {"32766", 10},
683 {"32767", 10},
684 {"32768", 10},
685 {"32769", 10},
686 {"65534", 10},
687 {"65535", 10},
688 {"65536", 10},
689 {"65537", 10},
690 {"2147483646", 10},
691 {"2147483647", 10},
692 {"2147483648", 10},
693 {"2147483649", 10},
694 {"4294967294", 10},
695 {"4294967295", 10},
696 {"4294967296", 10},
697 {"4294967297", 10},
698 {"9223372036854775806", 10},
699 {"9223372036854775807", 10},
700 {"9223372036854775808", 10},
701 {"9223372036854775809", 10},
702 {"18446744073709551614", 10},
703 {"18446744073709551615", 10},
704 {"18446744073709551616", 10},
705 {"18446744073709551617", 10},
706 };
707 TEST_FAIL(kstrtos8, s8, "%hhd", test_s8_fail);
708}
709
710static int __init test_kstrtox_init(void)
711{
712 test_kstrtoull_ok();
713 test_kstrtoull_fail();
714 test_kstrtoll_ok();
715 test_kstrtoll_fail();
716
717 test_kstrtou64_ok();
718 test_kstrtou64_fail();
719 test_kstrtos64_ok();
720 test_kstrtos64_fail();
721
722 test_kstrtou32_ok();
723 test_kstrtou32_fail();
724 test_kstrtos32_ok();
725 test_kstrtos32_fail();
726
727 test_kstrtou16_ok();
728 test_kstrtou16_fail();
729 test_kstrtos16_ok();
730 test_kstrtos16_fail();
731
732 test_kstrtou8_ok();
733 test_kstrtou8_fail();
734 test_kstrtos8_ok();
735 test_kstrtos8_fail();
736 return -EINVAL;
737}
738module_init(test_kstrtox_init);
739MODULE_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 @@
5 * Uses rbtrees for quick list adds and expiration. 5 * Uses rbtrees for quick list adds and expiration.
6 * 6 *
7 * NOTE: All of the following functions need to be serialized 7 * NOTE: All of the following functions need to be serialized
8 * to avoid races. No locking is done by this libary code. 8 * to avoid races. No locking is done by this library code.
9 * 9 *
10 * This program is free software; you can redistribute it and/or modify 10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by 11 * 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)
120} 120}
121EXPORT_SYMBOL(simple_strtoll); 121EXPORT_SYMBOL(simple_strtoll);
122 122
123/**
124 * strict_strtoul - convert a string to an unsigned long strictly
125 * @cp: The string to be converted
126 * @base: The number base to use
127 * @res: The converted result value
128 *
129 * strict_strtoul converts a string to an unsigned long only if the
130 * string is really an unsigned long string, any string containing
131 * any invalid char at the tail will be rejected and -EINVAL is returned,
132 * only a newline char at the tail is acceptible because people generally
133 * change a module parameter in the following way:
134 *
135 * echo 1024 > /sys/module/e1000/parameters/copybreak
136 *
137 * echo will append a newline to the tail.
138 *
139 * It returns 0 if conversion is successful and *res is set to the converted
140 * value, otherwise it returns -EINVAL and *res is set to 0.
141 *
142 * simple_strtoul just ignores the successive invalid characters and
143 * return the converted value of prefix part of the string.
144 */
145int strict_strtoul(const char *cp, unsigned int base, unsigned long *res)
146{
147 char *tail;
148 unsigned long val;
149
150 *res = 0;
151 if (!*cp)
152 return -EINVAL;
153
154 val = simple_strtoul(cp, &tail, base);
155 if (tail == cp)
156 return -EINVAL;
157
158 if ((tail[0] == '\0') || (tail[0] == '\n' && tail[1] == '\0')) {
159 *res = val;
160 return 0;
161 }
162
163 return -EINVAL;
164}
165EXPORT_SYMBOL(strict_strtoul);
166
167/**
168 * strict_strtol - convert a string to a long strictly
169 * @cp: The string to be converted
170 * @base: The number base to use
171 * @res: The converted result value
172 *
173 * strict_strtol is similiar to strict_strtoul, but it allows the first
174 * character of a string is '-'.
175 *
176 * It returns 0 if conversion is successful and *res is set to the converted
177 * value, otherwise it returns -EINVAL and *res is set to 0.
178 */
179int strict_strtol(const char *cp, unsigned int base, long *res)
180{
181 int ret;
182 if (*cp == '-') {
183 ret = strict_strtoul(cp + 1, base, (unsigned long *)res);
184 if (!ret)
185 *res = -(*res);
186 } else {
187 ret = strict_strtoul(cp, base, (unsigned long *)res);
188 }
189
190 return ret;
191}
192EXPORT_SYMBOL(strict_strtol);
193
194/**
195 * strict_strtoull - convert a string to an unsigned long long strictly
196 * @cp: The string to be converted
197 * @base: The number base to use
198 * @res: The converted result value
199 *
200 * strict_strtoull converts a string to an unsigned long long only if the
201 * string is really an unsigned long long string, any string containing
202 * any invalid char at the tail will be rejected and -EINVAL is returned,
203 * only a newline char at the tail is acceptible because people generally
204 * change a module parameter in the following way:
205 *
206 * echo 1024 > /sys/module/e1000/parameters/copybreak
207 *
208 * echo will append a newline to the tail of the string.
209 *
210 * It returns 0 if conversion is successful and *res is set to the converted
211 * value, otherwise it returns -EINVAL and *res is set to 0.
212 *
213 * simple_strtoull just ignores the successive invalid characters and
214 * return the converted value of prefix part of the string.
215 */
216int strict_strtoull(const char *cp, unsigned int base, unsigned long long *res)
217{
218 char *tail;
219 unsigned long long val;
220
221 *res = 0;
222 if (!*cp)
223 return -EINVAL;
224
225 val = simple_strtoull(cp, &tail, base);
226 if (tail == cp)
227 return -EINVAL;
228 if ((tail[0] == '\0') || (tail[0] == '\n' && tail[1] == '\0')) {
229 *res = val;
230 return 0;
231 }
232
233 return -EINVAL;
234}
235EXPORT_SYMBOL(strict_strtoull);
236
237/**
238 * strict_strtoll - convert a string to a long long strictly
239 * @cp: The string to be converted
240 * @base: The number base to use
241 * @res: The converted result value
242 *
243 * strict_strtoll is similiar to strict_strtoull, but it allows the first
244 * character of a string is '-'.
245 *
246 * It returns 0 if conversion is successful and *res is set to the converted
247 * value, otherwise it returns -EINVAL and *res is set to 0.
248 */
249int strict_strtoll(const char *cp, unsigned int base, long long *res)
250{
251 int ret;
252 if (*cp == '-') {
253 ret = strict_strtoull(cp + 1, base, (unsigned long long *)res);
254 if (!ret)
255 *res = -(*res);
256 } else {
257 ret = strict_strtoull(cp, base, (unsigned long long *)res);
258 }
259
260 return ret;
261}
262EXPORT_SYMBOL(strict_strtoll);
263
264static noinline_for_stack 123static noinline_for_stack
265int skip_atoi(const char **s) 124int skip_atoi(const char **s)
266{ 125{
@@ -574,7 +433,9 @@ char *symbol_string(char *buf, char *end, void *ptr,
574 unsigned long value = (unsigned long) ptr; 433 unsigned long value = (unsigned long) ptr;
575#ifdef CONFIG_KALLSYMS 434#ifdef CONFIG_KALLSYMS
576 char sym[KSYM_SYMBOL_LEN]; 435 char sym[KSYM_SYMBOL_LEN];
577 if (ext != 'f' && ext != 's') 436 if (ext == 'B')
437 sprint_backtrace(sym, value);
438 else if (ext != 'f' && ext != 's')
578 sprint_symbol(sym, value); 439 sprint_symbol(sym, value);
579 else 440 else
580 kallsyms_lookup(value, NULL, NULL, NULL, sym); 441 kallsyms_lookup(value, NULL, NULL, NULL, sym);
@@ -936,7 +797,7 @@ char *uuid_string(char *buf, char *end, const u8 *addr,
936 return string(buf, end, uuid, spec); 797 return string(buf, end, uuid, spec);
937} 798}
938 799
939int kptr_restrict = 1; 800int kptr_restrict __read_mostly;
940 801
941/* 802/*
942 * Show a '%p' thing. A kernel extension is that the '%p' is followed 803 * Show a '%p' thing. A kernel extension is that the '%p' is followed
@@ -949,6 +810,7 @@ int kptr_restrict = 1;
949 * - 'f' For simple symbolic function names without offset 810 * - 'f' For simple symbolic function names without offset
950 * - 'S' For symbolic direct pointers with offset 811 * - 'S' For symbolic direct pointers with offset
951 * - 's' For symbolic direct pointers without offset 812 * - 's' For symbolic direct pointers without offset
813 * - 'B' For backtraced symbolic direct pointers with offset
952 * - 'R' For decoded struct resource, e.g., [mem 0x0-0x1f 64bit pref] 814 * - 'R' For decoded struct resource, e.g., [mem 0x0-0x1f 64bit pref]
953 * - 'r' For raw struct resource, e.g., [mem 0x0-0x1f flags 0x201] 815 * - 'r' For raw struct resource, e.g., [mem 0x0-0x1f flags 0x201]
954 * - 'M' For a 6-byte MAC address, it prints the address in the 816 * - 'M' For a 6-byte MAC address, it prints the address in the
@@ -991,7 +853,7 @@ static noinline_for_stack
991char *pointer(const char *fmt, char *buf, char *end, void *ptr, 853char *pointer(const char *fmt, char *buf, char *end, void *ptr,
992 struct printf_spec spec) 854 struct printf_spec spec)
993{ 855{
994 if (!ptr) { 856 if (!ptr && *fmt != 'K') {
995 /* 857 /*
996 * Print (null) with the same width as a pointer so it makes 858 * Print (null) with the same width as a pointer so it makes
997 * tabular output look nice. 859 * tabular output look nice.
@@ -1008,6 +870,7 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
1008 /* Fallthrough */ 870 /* Fallthrough */
1009 case 'S': 871 case 'S':
1010 case 's': 872 case 's':
873 case 'B':
1011 return symbol_string(buf, end, ptr, spec, *fmt); 874 return symbol_string(buf, end, ptr, spec, *fmt);
1012 case 'R': 875 case 'R':
1013 case 'r': 876 case 'r':
@@ -1047,16 +910,12 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
1047 if (spec.field_width == -1) 910 if (spec.field_width == -1)
1048 spec.field_width = 2 * sizeof(void *); 911 spec.field_width = 2 * sizeof(void *);
1049 return string(buf, end, "pK-error", spec); 912 return string(buf, end, "pK-error", spec);
1050 } else if ((kptr_restrict == 0) ||
1051 (kptr_restrict == 1 &&
1052 has_capability_noaudit(current, CAP_SYSLOG)))
1053 break;
1054
1055 if (spec.field_width == -1) {
1056 spec.field_width = 2 * sizeof(void *);
1057 spec.flags |= ZEROPAD;
1058 } 913 }
1059 return number(buf, end, 0, spec); 914 if (!((kptr_restrict == 0) ||
915 (kptr_restrict == 1 &&
916 has_capability_noaudit(current, CAP_SYSLOG))))
917 ptr = NULL;
918 break;
1060 } 919 }
1061 spec.flags |= SMALL; 920 spec.flags |= SMALL;
1062 if (spec.field_width == -1) { 921 if (spec.field_width == -1) {
@@ -1279,6 +1138,7 @@ qualifier:
1279 * %ps output the name of a text symbol without offset 1138 * %ps output the name of a text symbol without offset
1280 * %pF output the name of a function pointer with its offset 1139 * %pF output the name of a function pointer with its offset
1281 * %pf output the name of a function pointer without its offset 1140 * %pf output the name of a function pointer without its offset
1141 * %pB output the name of a backtrace symbol with its offset
1282 * %pR output the address range in a struct resource with decoded flags 1142 * %pR output the address range in a struct resource with decoded flags
1283 * %pr output the address range in a struct resource with raw flags 1143 * %pr output the address range in a struct resource with raw flags
1284 * %pM output a 6-byte MAC address with colons 1144 * %pM output a 6-byte MAC address with colons
@@ -1301,8 +1161,7 @@ qualifier:
1301 * return is greater than or equal to @size, the resulting 1161 * return is greater than or equal to @size, the resulting
1302 * string is truncated. 1162 * string is truncated.
1303 * 1163 *
1304 * Call this function if you are already dealing with a va_list. 1164 * If you're not already dealing with a va_list consider using snprintf().
1305 * You probably want snprintf() instead.
1306 */ 1165 */
1307int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) 1166int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
1308{ 1167{
@@ -1476,8 +1335,7 @@ EXPORT_SYMBOL(vsnprintf);
1476 * the @buf not including the trailing '\0'. If @size is == 0 the function 1335 * the @buf not including the trailing '\0'. If @size is == 0 the function
1477 * returns 0. 1336 * returns 0.
1478 * 1337 *
1479 * Call this function if you are already dealing with a va_list. 1338 * If you're not already dealing with a va_list consider using scnprintf().
1480 * You probably want scnprintf() instead.
1481 * 1339 *
1482 * See the vsnprintf() documentation for format string extensions over C99. 1340 * See the vsnprintf() documentation for format string extensions over C99.
1483 */ 1341 */
@@ -1556,8 +1414,7 @@ EXPORT_SYMBOL(scnprintf);
1556 * into @buf. Use vsnprintf() or vscnprintf() in order to avoid 1414 * into @buf. Use vsnprintf() or vscnprintf() in order to avoid
1557 * buffer overflows. 1415 * buffer overflows.
1558 * 1416 *
1559 * Call this function if you are already dealing with a va_list. 1417 * If you're not already dealing with a va_list consider using sprintf().
1560 * You probably want sprintf() instead.
1561 * 1418 *
1562 * See the vsnprintf() documentation for format string extensions over C99. 1419 * See the vsnprintf() documentation for format string extensions over C99.
1563 */ 1420 */
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,
969 */ 969 */
970 tmp = b->in[b->in_pos++]; 970 tmp = b->in[b->in_pos++];
971 971
972 if (tmp == 0x00)
973 return XZ_STREAM_END;
974
972 if (tmp >= 0xE0 || tmp == 0x01) { 975 if (tmp >= 0xE0 || tmp == 0x01) {
973 s->lzma2.need_props = true; 976 s->lzma2.need_props = true;
974 s->lzma2.need_dict_reset = false; 977 s->lzma2.need_dict_reset = false;
@@ -1001,9 +1004,6 @@ XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s,
1001 lzma_reset(s); 1004 lzma_reset(s);
1002 } 1005 }
1003 } else { 1006 } else {
1004 if (tmp == 0x00)
1005 return XZ_STREAM_END;
1006
1007 if (tmp > 0x02) 1007 if (tmp > 0x02)
1008 return XZ_DATA_ERROR; 1008 return XZ_DATA_ERROR;
1009 1009
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(
176 deflate_state *s; 176 deflate_state *s;
177 int noheader = 0; 177 int noheader = 0;
178 deflate_workspace *mem; 178 deflate_workspace *mem;
179 char *next;
179 180
180 ush *overlay; 181 ush *overlay;
181 /* We overlay pending_buf and d_buf+l_buf. This works since the average 182 /* We overlay pending_buf and d_buf+l_buf. This works since the average
@@ -199,6 +200,21 @@ int zlib_deflateInit2(
199 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 200 strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
200 return Z_STREAM_ERROR; 201 return Z_STREAM_ERROR;
201 } 202 }
203
204 /*
205 * Direct the workspace's pointers to the chunks that were allocated
206 * along with the deflate_workspace struct.
207 */
208 next = (char *) mem;
209 next += sizeof(*mem);
210 mem->window_memory = (Byte *) next;
211 next += zlib_deflate_window_memsize(windowBits);
212 mem->prev_memory = (Pos *) next;
213 next += zlib_deflate_prev_memsize(windowBits);
214 mem->head_memory = (Pos *) next;
215 next += zlib_deflate_head_memsize(memLevel);
216 mem->overlay_memory = next;
217
202 s = (deflate_state *) &(mem->deflate_memory); 218 s = (deflate_state *) &(mem->deflate_memory);
203 strm->state = (struct internal_state *)s; 219 strm->state = (struct internal_state *)s;
204 s->strm = strm; 220 s->strm = strm;
@@ -1247,7 +1263,18 @@ static block_state deflate_slow(
1247 return flush == Z_FINISH ? finish_done : block_done; 1263 return flush == Z_FINISH ? finish_done : block_done;
1248} 1264}
1249 1265
1250int zlib_deflate_workspacesize(void) 1266int zlib_deflate_workspacesize(int windowBits, int memLevel)
1251{ 1267{
1252 return sizeof(deflate_workspace); 1268 if (windowBits < 0) /* undocumented feature: suppress zlib header */
1269 windowBits = -windowBits;
1270
1271 /* Since the return value is typically passed to vmalloc() unchecked... */
1272 BUG_ON(memLevel < 1 || memLevel > MAX_MEM_LEVEL || windowBits < 9 ||
1273 windowBits > 15);
1274
1275 return sizeof(deflate_workspace)
1276 + zlib_deflate_window_memsize(windowBits)
1277 + zlib_deflate_prev_memsize(windowBits)
1278 + zlib_deflate_head_memsize(memLevel)
1279 + zlib_deflate_overlay_memsize(memLevel);
1253} 1280}
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 {
241typedef struct deflate_workspace { 241typedef struct deflate_workspace {
242 /* State memory for the deflator */ 242 /* State memory for the deflator */
243 deflate_state deflate_memory; 243 deflate_state deflate_memory;
244 Byte window_memory[2 * (1 << MAX_WBITS)]; 244 Byte *window_memory;
245 Pos prev_memory[1 << MAX_WBITS]; 245 Pos *prev_memory;
246 Pos head_memory[1 << (MAX_MEM_LEVEL + 7)]; 246 Pos *head_memory;
247 char overlay_memory[(1 << (MAX_MEM_LEVEL + 6)) * (sizeof(ush)+2)]; 247 char *overlay_memory;
248} deflate_workspace; 248} deflate_workspace;
249 249
250#define zlib_deflate_window_memsize(windowBits) \
251 (2 * (1 << (windowBits)) * sizeof(Byte))
252#define zlib_deflate_prev_memsize(windowBits) \
253 ((1 << (windowBits)) * sizeof(Pos))
254#define zlib_deflate_head_memsize(memLevel) \
255 ((1 << ((memLevel)+7)) * sizeof(Pos))
256#define zlib_deflate_overlay_memsize(memLevel) \
257 ((1 << ((memLevel)+6)) * (sizeof(ush)+2))
258
250/* Output a byte on the stream. 259/* Output a byte on the stream.
251 * IN assertion: there is enough room in pending_buf. 260 * IN assertion: there is enough room in pending_buf.
252 */ 261 */
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-09 22:35:21 -0500