aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig3
-rw-r--r--lib/Kconfig.debug63
-rw-r--r--lib/Makefile8
-rw-r--r--lib/atomic64.c4
-rw-r--r--lib/atomic64_test.c164
-rw-r--r--lib/bitmap.c19
-rw-r--r--lib/btree.c798
-rw-r--r--lib/cpumask.c1
-rw-r--r--lib/crc32.c31
-rw-r--r--lib/debug_locks.c1
-rw-r--r--lib/debugobjects.c64
-rw-r--r--lib/decompress_unlzo.c22
-rw-r--r--lib/devres.c1
-rw-r--r--lib/dma-debug.c2
-rw-r--r--lib/dynamic_debug.c1
-rw-r--r--lib/flex_array.c2
-rw-r--r--lib/genalloc.c1
-rw-r--r--lib/hweight.c26
-rw-r--r--lib/idr.c8
-rw-r--r--lib/inflate.c1
-rw-r--r--lib/kasprintf.c1
-rw-r--r--lib/kobject.c6
-rw-r--r--lib/kobject_uevent.c3
-rw-r--r--lib/kref.c1
-rw-r--r--lib/lcm.c15
-rw-r--r--lib/list_sort.c263
-rw-r--r--lib/lmb.c13
-rw-r--r--lib/radix-tree.c37
-rw-r--r--lib/ratelimit.c11
-rw-r--r--lib/rbtree.c48
-rw-r--r--lib/rwsem-spinlock.c14
-rw-r--r--lib/rwsem.c5
-rw-r--r--lib/scatterlist.c1
-rw-r--r--lib/show_mem.c14
-rw-r--r--lib/string.c40
-rw-r--r--lib/swiotlb.c1
-rw-r--r--lib/textsearch.c1
-rw-r--r--lib/vsprintf.c133
-rw-r--r--lib/zlib_inflate/inffast.c72
39 files changed, 1610 insertions, 289 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 97b136ff117e..170d8ca901d8 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -160,6 +160,9 @@ config TEXTSEARCH_BM
160config TEXTSEARCH_FSM 160config TEXTSEARCH_FSM
161 tristate 161 tristate
162 162
163config BTREE
164 boolean
165
163config HAS_IOMEM 166config HAS_IOMEM
164 boolean 167 boolean
165 depends on !NO_IOMEM 168 depends on !NO_IOMEM
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 25c3ed594c54..d85be90d5888 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -103,7 +103,8 @@ config HEADERS_CHECK
103 103
104config DEBUG_SECTION_MISMATCH 104config DEBUG_SECTION_MISMATCH
105 bool "Enable full Section mismatch analysis" 105 bool "Enable full Section mismatch analysis"
106 depends on UNDEFINED 106 depends on UNDEFINED || (BLACKFIN)
107 default y
107 # This option is on purpose disabled for now. 108 # This option is on purpose disabled for now.
108 # It will be enabled when we are down to a reasonable number 109 # It will be enabled when we are down to a reasonable number
109 # of section mismatch warnings (< 10 for an allyesconfig build) 110 # of section mismatch warnings (< 10 for an allyesconfig build)
@@ -355,7 +356,7 @@ config SLUB_STATS
355config DEBUG_KMEMLEAK 356config DEBUG_KMEMLEAK
356 bool "Kernel memory leak detector" 357 bool "Kernel memory leak detector"
357 depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \ 358 depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \
358 (X86 || ARM || PPC || S390) 359 (X86 || ARM || PPC || S390 || SPARC64 || SUPERH || MICROBLAZE)
359 360
360 select DEBUG_FS if SYSFS 361 select DEBUG_FS if SYSFS
361 select STACKTRACE if STACKTRACE_SUPPORT 362 select STACKTRACE if STACKTRACE_SUPPORT
@@ -499,6 +500,30 @@ config PROVE_LOCKING
499 500
500 For more details, see Documentation/lockdep-design.txt. 501 For more details, see Documentation/lockdep-design.txt.
501 502
503config PROVE_RCU
504 bool "RCU debugging: prove RCU correctness"
505 depends on PROVE_LOCKING
506 default n
507 help
508 This feature enables lockdep extensions that check for correct
509 use of RCU APIs. This is currently under development. Say Y
510 if you want to debug RCU usage or help work on the PROVE_RCU
511 feature.
512
513 Say N if you are unsure.
514
515config PROVE_RCU_REPEATEDLY
516 bool "RCU debugging: don't disable PROVE_RCU on first splat"
517 depends on PROVE_RCU
518 default n
519 help
520 By itself, PROVE_RCU will disable checking upon issuing the
521 first warning (or "splat"). This feature prevents such
522 disabling, allowing multiple RCU-lockdep warnings to be printed
523 on a single reboot.
524
525 Say N if you are unsure.
526
502config LOCKDEP 527config LOCKDEP
503 bool 528 bool
504 depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT 529 depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT
@@ -520,6 +545,14 @@ config LOCK_STAT
520 545
521 For more details, see Documentation/lockstat.txt 546 For more details, see Documentation/lockstat.txt
522 547
548 This also enables lock events required by "perf lock",
549 subcommand of perf.
550 If you want to use "perf lock", you also need to turn on
551 CONFIG_EVENT_TRACING.
552
553 CONFIG_LOCK_STAT defines "contended" and "acquired" lock events.
554 (CONFIG_LOCKDEP defines "acquire" and "release" events.)
555
523config DEBUG_LOCKDEP 556config DEBUG_LOCKDEP
524 bool "Lock dependency engine debugging" 557 bool "Lock dependency engine debugging"
525 depends on DEBUG_KERNEL && LOCKDEP 558 depends on DEBUG_KERNEL && LOCKDEP
@@ -765,10 +798,22 @@ config RCU_CPU_STALL_DETECTOR
765 CPUs are delaying the current grace period, but only when 798 CPUs are delaying the current grace period, but only when
766 the grace period extends for excessive time periods. 799 the grace period extends for excessive time periods.
767 800
768 Say Y if you want RCU to perform such checks. 801 Say N if you want to disable such checks.
802
803 Say Y if you are unsure.
804
805config RCU_CPU_STALL_VERBOSE
806 bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR"
807 depends on RCU_CPU_STALL_DETECTOR && TREE_PREEMPT_RCU
808 default y
809 help
810 This option causes RCU to printk detailed per-task information
811 for any tasks that are stalling the current RCU grace period.
769 812
770 Say N if you are unsure. 813 Say N if you are unsure.
771 814
815 Say Y if you want to enable such checks.
816
772config KPROBES_SANITY_TEST 817config KPROBES_SANITY_TEST
773 bool "Kprobes sanity tests" 818 bool "Kprobes sanity tests"
774 depends on DEBUG_KERNEL 819 depends on DEBUG_KERNEL
@@ -840,8 +885,7 @@ config DEBUG_FORCE_WEAK_PER_CPU
840 885
841config LKDTM 886config LKDTM
842 tristate "Linux Kernel Dump Test Tool Module" 887 tristate "Linux Kernel Dump Test Tool Module"
843 depends on DEBUG_KERNEL 888 depends on DEBUG_FS
844 depends on KPROBES
845 depends on BLOCK 889 depends on BLOCK
846 default n 890 default n
847 help 891 help
@@ -852,7 +896,7 @@ config LKDTM
852 called lkdtm. 896 called lkdtm.
853 897
854 Documentation on how to use the module can be found in 898 Documentation on how to use the module can be found in
855 drivers/misc/lkdtm.c 899 Documentation/fault-injection/provoke-crashes.txt
856 900
857config FAULT_INJECTION 901config FAULT_INJECTION
858 bool "Fault-injection framework" 902 bool "Fault-injection framework"
@@ -1054,6 +1098,13 @@ config DMA_API_DEBUG
1054 This option causes a performance degredation. Use only if you want 1098 This option causes a performance degredation. Use only if you want
1055 to debug device drivers. If unsure, say N. 1099 to debug device drivers. If unsure, say N.
1056 1100
1101config ATOMIC64_SELFTEST
1102 bool "Perform an atomic64_t self-test at boot"
1103 help
1104 Enable this option to test the atomic64_t functions at boot.
1105
1106 If unsure, say N.
1107
1057source "samples/Kconfig" 1108source "samples/Kconfig"
1058 1109
1059source "lib/Kconfig.kgdb" 1110source "lib/Kconfig.kgdb"
diff --git a/lib/Makefile b/lib/Makefile
index 3b0b4a696db9..9e6d3c29d73a 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ 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 list_sort.o 24 string_helpers.o gcd.o lcm.o list_sort.o
25 25
26ifeq ($(CONFIG_DEBUG_KOBJECT),y) 26ifeq ($(CONFIG_DEBUG_KOBJECT),y)
27CFLAGS_kobject.o += -DDEBUG 27CFLAGS_kobject.o += -DDEBUG
@@ -39,8 +39,12 @@ lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
39lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o 39lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o
40lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o 40lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
41obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o 41obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o
42
43CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
42obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o 44obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
45
43obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o 46obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o
47obj-$(CONFIG_BTREE) += btree.o
44obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o 48obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
45obj-$(CONFIG_DEBUG_LIST) += list_debug.o 49obj-$(CONFIG_DEBUG_LIST) += list_debug.o
46obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o 50obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
@@ -100,6 +104,8 @@ obj-$(CONFIG_GENERIC_CSUM) += checksum.o
100 104
101obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o 105obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o
102 106
107obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
108
103hostprogs-y := gen_crc32table 109hostprogs-y := gen_crc32table
104clean-files := crc32table.h 110clean-files := crc32table.h
105 111
diff --git a/lib/atomic64.c b/lib/atomic64.c
index 8bee16ec7524..a21c12bc727c 100644
--- a/lib/atomic64.c
+++ b/lib/atomic64.c
@@ -162,12 +162,12 @@ int atomic64_add_unless(atomic64_t *v, long long a, long long u)
162{ 162{
163 unsigned long flags; 163 unsigned long flags;
164 spinlock_t *lock = lock_addr(v); 164 spinlock_t *lock = lock_addr(v);
165 int ret = 1; 165 int ret = 0;
166 166
167 spin_lock_irqsave(lock, flags); 167 spin_lock_irqsave(lock, flags);
168 if (v->counter != u) { 168 if (v->counter != u) {
169 v->counter += a; 169 v->counter += a;
170 ret = 0; 170 ret = 1;
171 } 171 }
172 spin_unlock_irqrestore(lock, flags); 172 spin_unlock_irqrestore(lock, flags);
173 return ret; 173 return ret;
diff --git a/lib/atomic64_test.c b/lib/atomic64_test.c
new file mode 100644
index 000000000000..65e482caf5e9
--- /dev/null
+++ b/lib/atomic64_test.c
@@ -0,0 +1,164 @@
1/*
2 * Testsuite for atomic64_t functions
3 *
4 * Copyright © 2010 Luca Barbieri
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 */
11#include <linux/init.h>
12#include <asm/atomic.h>
13
14#define INIT(c) do { atomic64_set(&v, c); r = c; } while (0)
15static __init int test_atomic64(void)
16{
17 long long v0 = 0xaaa31337c001d00dLL;
18 long long v1 = 0xdeadbeefdeafcafeLL;
19 long long v2 = 0xfaceabadf00df001LL;
20 long long onestwos = 0x1111111122222222LL;
21 long long one = 1LL;
22
23 atomic64_t v = ATOMIC64_INIT(v0);
24 long long r = v0;
25 BUG_ON(v.counter != r);
26
27 atomic64_set(&v, v1);
28 r = v1;
29 BUG_ON(v.counter != r);
30 BUG_ON(atomic64_read(&v) != r);
31
32 INIT(v0);
33 atomic64_add(onestwos, &v);
34 r += onestwos;
35 BUG_ON(v.counter != r);
36
37 INIT(v0);
38 atomic64_add(-one, &v);
39 r += -one;
40 BUG_ON(v.counter != r);
41
42 INIT(v0);
43 r += onestwos;
44 BUG_ON(atomic64_add_return(onestwos, &v) != r);
45 BUG_ON(v.counter != r);
46
47 INIT(v0);
48 r += -one;
49 BUG_ON(atomic64_add_return(-one, &v) != r);
50 BUG_ON(v.counter != r);
51
52 INIT(v0);
53 atomic64_sub(onestwos, &v);
54 r -= onestwos;
55 BUG_ON(v.counter != r);
56
57 INIT(v0);
58 atomic64_sub(-one, &v);
59 r -= -one;
60 BUG_ON(v.counter != r);
61
62 INIT(v0);
63 r -= onestwos;
64 BUG_ON(atomic64_sub_return(onestwos, &v) != r);
65 BUG_ON(v.counter != r);
66
67 INIT(v0);
68 r -= -one;
69 BUG_ON(atomic64_sub_return(-one, &v) != r);
70 BUG_ON(v.counter != r);
71
72 INIT(v0);
73 atomic64_inc(&v);
74 r += one;
75 BUG_ON(v.counter != r);
76
77 INIT(v0);
78 r += one;
79 BUG_ON(atomic64_inc_return(&v) != r);
80 BUG_ON(v.counter != r);
81
82 INIT(v0);
83 atomic64_dec(&v);
84 r -= one;
85 BUG_ON(v.counter != r);
86
87 INIT(v0);
88 r -= one;
89 BUG_ON(atomic64_dec_return(&v) != r);
90 BUG_ON(v.counter != r);
91
92 INIT(v0);
93 BUG_ON(atomic64_xchg(&v, v1) != v0);
94 r = v1;
95 BUG_ON(v.counter != r);
96
97 INIT(v0);
98 BUG_ON(atomic64_cmpxchg(&v, v0, v1) != v0);
99 r = v1;
100 BUG_ON(v.counter != r);
101
102 INIT(v0);
103 BUG_ON(atomic64_cmpxchg(&v, v2, v1) != v0);
104 BUG_ON(v.counter != r);
105
106 INIT(v0);
107 BUG_ON(atomic64_add_unless(&v, one, v0));
108 BUG_ON(v.counter != r);
109
110 INIT(v0);
111 BUG_ON(!atomic64_add_unless(&v, one, v1));
112 r += one;
113 BUG_ON(v.counter != r);
114
115#if defined(CONFIG_X86) || defined(CONFIG_MIPS) || defined(CONFIG_PPC) || defined(_ASM_GENERIC_ATOMIC64_H)
116 INIT(onestwos);
117 BUG_ON(atomic64_dec_if_positive(&v) != (onestwos - 1));
118 r -= one;
119 BUG_ON(v.counter != r);
120
121 INIT(0);
122 BUG_ON(atomic64_dec_if_positive(&v) != -one);
123 BUG_ON(v.counter != r);
124
125 INIT(-one);
126 BUG_ON(atomic64_dec_if_positive(&v) != (-one - one));
127 BUG_ON(v.counter != r);
128#else
129#warning Please implement atomic64_dec_if_positive for your architecture, and add it to the IF above
130#endif
131
132 INIT(onestwos);
133 BUG_ON(!atomic64_inc_not_zero(&v));
134 r += one;
135 BUG_ON(v.counter != r);
136
137 INIT(0);
138 BUG_ON(atomic64_inc_not_zero(&v));
139 BUG_ON(v.counter != r);
140
141 INIT(-one);
142 BUG_ON(!atomic64_inc_not_zero(&v));
143 r += one;
144 BUG_ON(v.counter != r);
145
146#ifdef CONFIG_X86
147 printk(KERN_INFO "atomic64 test passed for %s platform %s CX8 and %s SSE\n",
148#ifdef CONFIG_X86_64
149 "x86-64",
150#elif defined(CONFIG_X86_CMPXCHG64)
151 "i586+",
152#else
153 "i386+",
154#endif
155 boot_cpu_has(X86_FEATURE_CX8) ? "with" : "without",
156 boot_cpu_has(X86_FEATURE_XMM) ? "with" : "without");
157#else
158 printk(KERN_INFO "atomic64 test passed\n");
159#endif
160
161 return 0;
162}
163
164core_initcall(test_atomic64);
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 11bf49750583..ffb78c916ccd 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -487,7 +487,7 @@ int __bitmap_parse(const char *buf, unsigned int buflen,
487EXPORT_SYMBOL(__bitmap_parse); 487EXPORT_SYMBOL(__bitmap_parse);
488 488
489/** 489/**
490 * bitmap_parse_user() 490 * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
491 * 491 *
492 * @ubuf: pointer to user buffer containing string. 492 * @ubuf: pointer to user buffer containing string.
493 * @ulen: buffer size in bytes. If string is smaller than this 493 * @ulen: buffer size in bytes. If string is smaller than this
@@ -619,7 +619,7 @@ int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
619EXPORT_SYMBOL(bitmap_parselist); 619EXPORT_SYMBOL(bitmap_parselist);
620 620
621/** 621/**
622 * bitmap_pos_to_ord(buf, pos, bits) 622 * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
623 * @buf: pointer to a bitmap 623 * @buf: pointer to a bitmap
624 * @pos: a bit position in @buf (0 <= @pos < @bits) 624 * @pos: a bit position in @buf (0 <= @pos < @bits)
625 * @bits: number of valid bit positions in @buf 625 * @bits: number of valid bit positions in @buf
@@ -655,7 +655,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
655} 655}
656 656
657/** 657/**
658 * bitmap_ord_to_pos(buf, ord, bits) 658 * bitmap_ord_to_pos - find position of n-th set bit in bitmap
659 * @buf: pointer to bitmap 659 * @buf: pointer to bitmap
660 * @ord: ordinal bit position (n-th set bit, n >= 0) 660 * @ord: ordinal bit position (n-th set bit, n >= 0)
661 * @bits: number of valid bit positions in @buf 661 * @bits: number of valid bit positions in @buf
@@ -733,10 +733,9 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
733 bitmap_zero(dst, bits); 733 bitmap_zero(dst, bits);
734 734
735 w = bitmap_weight(new, bits); 735 w = bitmap_weight(new, bits);
736 for (oldbit = find_first_bit(src, bits); 736 for_each_set_bit(oldbit, src, bits) {
737 oldbit < bits;
738 oldbit = find_next_bit(src, bits, oldbit + 1)) {
739 int n = bitmap_pos_to_ord(old, oldbit, bits); 737 int n = bitmap_pos_to_ord(old, oldbit, bits);
738
740 if (n < 0 || w == 0) 739 if (n < 0 || w == 0)
741 set_bit(oldbit, dst); /* identity map */ 740 set_bit(oldbit, dst); /* identity map */
742 else 741 else
@@ -903,9 +902,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
903 */ 902 */
904 903
905 m = 0; 904 m = 0;
906 for (n = find_first_bit(relmap, bits); 905 for_each_set_bit(n, relmap, bits) {
907 n < bits;
908 n = find_next_bit(relmap, bits, n + 1)) {
909 /* m == bitmap_pos_to_ord(relmap, n, bits) */ 906 /* m == bitmap_pos_to_ord(relmap, n, bits) */
910 if (test_bit(m, orig)) 907 if (test_bit(m, orig))
911 set_bit(n, dst); 908 set_bit(n, dst);
@@ -934,9 +931,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig,
934 return; 931 return;
935 bitmap_zero(dst, bits); 932 bitmap_zero(dst, bits);
936 933
937 for (oldbit = find_first_bit(orig, bits); 934 for_each_set_bit(oldbit, orig, bits)
938 oldbit < bits;
939 oldbit = find_next_bit(orig, bits, oldbit + 1))
940 set_bit(oldbit % sz, dst); 935 set_bit(oldbit % sz, dst);
941} 936}
942EXPORT_SYMBOL(bitmap_fold); 937EXPORT_SYMBOL(bitmap_fold);
diff --git a/lib/btree.c b/lib/btree.c
new file mode 100644
index 000000000000..c9c6f0351526
--- /dev/null
+++ b/lib/btree.c
@@ -0,0 +1,798 @@
1/*
2 * lib/btree.c - Simple In-memory B+Tree
3 *
4 * As should be obvious for Linux kernel code, license is GPLv2
5 *
6 * Copyright (c) 2007-2008 Joern Engel <joern@logfs.org>
7 * Bits and pieces stolen from Peter Zijlstra's code, which is
8 * Copyright 2007, Red Hat Inc. Peter Zijlstra <pzijlstr@redhat.com>
9 * GPLv2
10 *
11 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
12 *
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.
15 *
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
18 * well is that access to a random tree node is much faster than a large number
19 * of operations within each node.
20 *
21 * Disks have fulfilled the prerequisite for a long time. More recently DRAM
22 * has gained similar properties, as memory access times, when measured in cpu
23 * cycles, have increased. Cacheline sizes have increased as well, which also
24 * helps B+Trees.
25 *
26 * Compared to radix trees, B+Trees are more efficient when dealing with a
27 * sparsely populated address space. Between 25% and 50% of the memory is
28 * occupied with valid pointers. When densely populated, radix trees contain
29 * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
30 * pointers.
31 *
32 * This particular implementation stores pointers identified by a long value.
33 * Storing NULL pointers is illegal, lookup will return NULL when no entry
34 * was found.
35 *
36 * A tricks was used that is not commonly found in textbooks. The lowest
37 * values are to the right, not to the left. All used slots within a node
38 * are on the left, all unused slots contain NUL values. Most operations
39 * simply loop once over all slots and terminate on the first NUL.
40 */
41
42#include <linux/btree.h>
43#include <linux/cache.h>
44#include <linux/kernel.h>
45#include <linux/slab.h>
46#include <linux/module.h>
47
48#define MAX(a, b) ((a) > (b) ? (a) : (b))
49#define NODESIZE MAX(L1_CACHE_BYTES, 128)
50
51struct btree_geo {
52 int keylen;
53 int no_pairs;
54 int no_longs;
55};
56
57struct btree_geo btree_geo32 = {
58 .keylen = 1,
59 .no_pairs = NODESIZE / sizeof(long) / 2,
60 .no_longs = NODESIZE / sizeof(long) / 2,
61};
62EXPORT_SYMBOL_GPL(btree_geo32);
63
64#define LONG_PER_U64 (64 / BITS_PER_LONG)
65struct btree_geo btree_geo64 = {
66 .keylen = LONG_PER_U64,
67 .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
68 .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
69};
70EXPORT_SYMBOL_GPL(btree_geo64);
71
72struct btree_geo btree_geo128 = {
73 .keylen = 2 * LONG_PER_U64,
74 .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
75 .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
76};
77EXPORT_SYMBOL_GPL(btree_geo128);
78
79static struct kmem_cache *btree_cachep;
80
81void *btree_alloc(gfp_t gfp_mask, void *pool_data)
82{
83 return kmem_cache_alloc(btree_cachep, gfp_mask);
84}
85EXPORT_SYMBOL_GPL(btree_alloc);
86
87void btree_free(void *element, void *pool_data)
88{
89 kmem_cache_free(btree_cachep, element);
90}
91EXPORT_SYMBOL_GPL(btree_free);
92
93static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
94{
95 unsigned long *node;
96
97 node = mempool_alloc(head->mempool, gfp);
98 if (likely(node))
99 memset(node, 0, NODESIZE);
100 return node;
101}
102
103static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
104{
105 size_t i;
106
107 for (i = 0; i < n; i++) {
108 if (l1[i] < l2[i])
109 return -1;
110 if (l1[i] > l2[i])
111 return 1;
112 }
113 return 0;
114}
115
116static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
117 size_t n)
118{
119 size_t i;
120
121 for (i = 0; i < n; i++)
122 dest[i] = src[i];
123 return dest;
124}
125
126static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
127{
128 size_t i;
129
130 for (i = 0; i < n; i++)
131 s[i] = c;
132 return s;
133}
134
135static void dec_key(struct btree_geo *geo, unsigned long *key)
136{
137 unsigned long val;
138 int i;
139
140 for (i = geo->keylen - 1; i >= 0; i--) {
141 val = key[i];
142 key[i] = val - 1;
143 if (val)
144 break;
145 }
146}
147
148static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
149{
150 return &node[n * geo->keylen];
151}
152
153static void *bval(struct btree_geo *geo, unsigned long *node, int n)
154{
155 return (void *)node[geo->no_longs + n];
156}
157
158static void setkey(struct btree_geo *geo, unsigned long *node, int n,
159 unsigned long *key)
160{
161 longcpy(bkey(geo, node, n), key, geo->keylen);
162}
163
164static void setval(struct btree_geo *geo, unsigned long *node, int n,
165 void *val)
166{
167 node[geo->no_longs + n] = (unsigned long) val;
168}
169
170static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
171{
172 longset(bkey(geo, node, n), 0, geo->keylen);
173 node[geo->no_longs + n] = 0;
174}
175
176static inline void __btree_init(struct btree_head *head)
177{
178 head->node = NULL;
179 head->height = 0;
180}
181
182void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
183{
184 __btree_init(head);
185 head->mempool = mempool;
186}
187EXPORT_SYMBOL_GPL(btree_init_mempool);
188
189int btree_init(struct btree_head *head)
190{
191 __btree_init(head);
192 head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
193 if (!head->mempool)
194 return -ENOMEM;
195 return 0;
196}
197EXPORT_SYMBOL_GPL(btree_init);
198
199void btree_destroy(struct btree_head *head)
200{
201 mempool_destroy(head->mempool);
202 head->mempool = NULL;
203}
204EXPORT_SYMBOL_GPL(btree_destroy);
205
206void *btree_last(struct btree_head *head, struct btree_geo *geo,
207 unsigned long *key)
208{
209 int height = head->height;
210 unsigned long *node = head->node;
211
212 if (height == 0)
213 return NULL;
214
215 for ( ; height > 1; height--)
216 node = bval(geo, node, 0);
217
218 longcpy(key, bkey(geo, node, 0), geo->keylen);
219 return bval(geo, node, 0);
220}
221EXPORT_SYMBOL_GPL(btree_last);
222
223static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
224 unsigned long *key)
225{
226 return longcmp(bkey(geo, node, pos), key, geo->keylen);
227}
228
229static int keyzero(struct btree_geo *geo, unsigned long *key)
230{
231 int i;
232
233 for (i = 0; i < geo->keylen; i++)
234 if (key[i])
235 return 0;
236
237 return 1;
238}
239
240void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
241 unsigned long *key)
242{
243 int i, height = head->height;
244 unsigned long *node = head->node;
245
246 if (height == 0)
247 return NULL;
248
249 for ( ; height > 1; height--) {
250 for (i = 0; i < geo->no_pairs; i++)
251 if (keycmp(geo, node, i, key) <= 0)
252 break;
253 if (i == geo->no_pairs)
254 return NULL;
255 node = bval(geo, node, i);
256 if (!node)
257 return NULL;
258 }
259
260 if (!node)
261 return NULL;
262
263 for (i = 0; i < geo->no_pairs; i++)
264 if (keycmp(geo, node, i, key) == 0)
265 return bval(geo, node, i);
266 return NULL;
267}
268EXPORT_SYMBOL_GPL(btree_lookup);
269
270int btree_update(struct btree_head *head, struct btree_geo *geo,
271 unsigned long *key, void *val)
272{
273 int i, height = head->height;
274 unsigned long *node = head->node;
275
276 if (height == 0)
277 return -ENOENT;
278
279 for ( ; height > 1; height--) {
280 for (i = 0; i < geo->no_pairs; i++)
281 if (keycmp(geo, node, i, key) <= 0)
282 break;
283 if (i == geo->no_pairs)
284 return -ENOENT;
285 node = bval(geo, node, i);
286 if (!node)
287 return -ENOENT;
288 }
289
290 if (!node)
291 return -ENOENT;
292
293 for (i = 0; i < geo->no_pairs; i++)
294 if (keycmp(geo, node, i, key) == 0) {
295 setval(geo, node, i, val);
296 return 0;
297 }
298 return -ENOENT;
299}
300EXPORT_SYMBOL_GPL(btree_update);
301
302/*
303 * Usually this function is quite similar to normal lookup. But the key of
304 * a parent node may be smaller than the smallest key of all its siblings.
305 * In such a case we cannot just return NULL, as we have only proven that no
306 * key smaller than __key, but larger than this parent key exists.
307 * So we set __key to the parent key and retry. We have to use the smallest
308 * such parent key, which is the last parent key we encountered.
309 */
310void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
311 unsigned long *__key)
312{
313 int i, height;
314 unsigned long *node, *oldnode;
315 unsigned long *retry_key = NULL, key[geo->keylen];
316
317 if (keyzero(geo, __key))
318 return NULL;
319
320 if (head->height == 0)
321 return NULL;
322retry:
323 longcpy(key, __key, geo->keylen);
324 dec_key(geo, key);
325
326 node = head->node;
327 for (height = head->height ; height > 1; height--) {
328 for (i = 0; i < geo->no_pairs; i++)
329 if (keycmp(geo, node, i, key) <= 0)
330 break;
331 if (i == geo->no_pairs)
332 goto miss;
333 oldnode = node;
334 node = bval(geo, node, i);
335 if (!node)
336 goto miss;
337 retry_key = bkey(geo, oldnode, i);
338 }
339
340 if (!node)
341 goto miss;
342
343 for (i = 0; i < geo->no_pairs; i++) {
344 if (keycmp(geo, node, i, key) <= 0) {
345 if (bval(geo, node, i)) {
346 longcpy(__key, bkey(geo, node, i), geo->keylen);
347 return bval(geo, node, i);
348 } else
349 goto miss;
350 }
351 }
352miss:
353 if (retry_key) {
354 __key = retry_key;
355 retry_key = NULL;
356 goto retry;
357 }
358 return NULL;
359}
360
361static int getpos(struct btree_geo *geo, unsigned long *node,
362 unsigned long *key)
363{
364 int i;
365
366 for (i = 0; i < geo->no_pairs; i++) {
367 if (keycmp(geo, node, i, key) <= 0)
368 break;
369 }
370 return i;
371}
372
373static int getfill(struct btree_geo *geo, unsigned long *node, int start)
374{
375 int i;
376
377 for (i = start; i < geo->no_pairs; i++)
378 if (!bval(geo, node, i))
379 break;
380 return i;
381}
382
383/*
384 * locate the correct leaf node in the btree
385 */
386static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
387 unsigned long *key, int level)
388{
389 unsigned long *node = head->node;
390 int i, height;
391
392 for (height = head->height; height > level; height--) {
393 for (i = 0; i < geo->no_pairs; i++)
394 if (keycmp(geo, node, i, key) <= 0)
395 break;
396
397 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
398 /* right-most key is too large, update it */
399 /* FIXME: If the right-most key on higher levels is
400 * always zero, this wouldn't be necessary. */
401 i--;
402 setkey(geo, node, i, key);
403 }
404 BUG_ON(i < 0);
405 node = bval(geo, node, i);
406 }
407 BUG_ON(!node);
408 return node;
409}
410
411static int btree_grow(struct btree_head *head, struct btree_geo *geo,
412 gfp_t gfp)
413{
414 unsigned long *node;
415 int fill;
416
417 node = btree_node_alloc(head, gfp);
418 if (!node)
419 return -ENOMEM;
420 if (head->node) {
421 fill = getfill(geo, head->node, 0);
422 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
423 setval(geo, node, 0, head->node);
424 }
425 head->node = node;
426 head->height++;
427 return 0;
428}
429
430static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
431{
432 unsigned long *node;
433 int fill;
434
435 if (head->height <= 1)
436 return;
437
438 node = head->node;
439 fill = getfill(geo, node, 0);
440 BUG_ON(fill > 1);
441 head->node = bval(geo, node, 0);
442 head->height--;
443 mempool_free(node, head->mempool);
444}
445
446static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
447 unsigned long *key, void *val, int level,
448 gfp_t gfp)
449{
450 unsigned long *node;
451 int i, pos, fill, err;
452
453 BUG_ON(!val);
454 if (head->height < level) {
455 err = btree_grow(head, geo, gfp);
456 if (err)
457 return err;
458 }
459
460retry:
461 node = find_level(head, geo, key, level);
462 pos = getpos(geo, node, key);
463 fill = getfill(geo, node, pos);
464 /* two identical keys are not allowed */
465 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
466
467 if (fill == geo->no_pairs) {
468 /* need to split node */
469 unsigned long *new;
470
471 new = btree_node_alloc(head, gfp);
472 if (!new)
473 return -ENOMEM;
474 err = btree_insert_level(head, geo,
475 bkey(geo, node, fill / 2 - 1),
476 new, level + 1, gfp);
477 if (err) {
478 mempool_free(new, head->mempool);
479 return err;
480 }
481 for (i = 0; i < fill / 2; i++) {
482 setkey(geo, new, i, bkey(geo, node, i));
483 setval(geo, new, i, bval(geo, node, i));
484 setkey(geo, node, i, bkey(geo, node, i + fill / 2));
485 setval(geo, node, i, bval(geo, node, i + fill / 2));
486 clearpair(geo, node, i + fill / 2);
487 }
488 if (fill & 1) {
489 setkey(geo, node, i, bkey(geo, node, fill - 1));
490 setval(geo, node, i, bval(geo, node, fill - 1));
491 clearpair(geo, node, fill - 1);
492 }
493 goto retry;
494 }
495 BUG_ON(fill >= geo->no_pairs);
496
497 /* shift and insert */
498 for (i = fill; i > pos; i--) {
499 setkey(geo, node, i, bkey(geo, node, i - 1));
500 setval(geo, node, i, bval(geo, node, i - 1));
501 }
502 setkey(geo, node, pos, key);
503 setval(geo, node, pos, val);
504
505 return 0;
506}
507
508int btree_insert(struct btree_head *head, struct btree_geo *geo,
509 unsigned long *key, void *val, gfp_t gfp)
510{
511 return btree_insert_level(head, geo, key, val, 1, gfp);
512}
513EXPORT_SYMBOL_GPL(btree_insert);
514
515static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
516 unsigned long *key, int level);
517static void merge(struct btree_head *head, struct btree_geo *geo, int level,
518 unsigned long *left, int lfill,
519 unsigned long *right, int rfill,
520 unsigned long *parent, int lpos)
521{
522 int i;
523
524 for (i = 0; i < rfill; i++) {
525 /* Move all keys to the left */
526 setkey(geo, left, lfill + i, bkey(geo, right, i));
527 setval(geo, left, lfill + i, bval(geo, right, i));
528 }
529 /* Exchange left and right child in parent */
530 setval(geo, parent, lpos, right);
531 setval(geo, parent, lpos + 1, left);
532 /* Remove left (formerly right) child from parent */
533 btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
534 mempool_free(right, head->mempool);
535}
536
537static void rebalance(struct btree_head *head, struct btree_geo *geo,
538 unsigned long *key, int level, unsigned long *child, int fill)
539{
540 unsigned long *parent, *left = NULL, *right = NULL;
541 int i, no_left, no_right;
542
543 if (fill == 0) {
544 /* Because we don't steal entries from a neigbour, this case
545 * can happen. Parent node contains a single child, this
546 * node, so merging with a sibling never happens.
547 */
548 btree_remove_level(head, geo, key, level + 1);
549 mempool_free(child, head->mempool);
550 return;
551 }
552
553 parent = find_level(head, geo, key, level + 1);
554 i = getpos(geo, parent, key);
555 BUG_ON(bval(geo, parent, i) != child);
556
557 if (i > 0) {
558 left = bval(geo, parent, i - 1);
559 no_left = getfill(geo, left, 0);
560 if (fill + no_left <= geo->no_pairs) {
561 merge(head, geo, level,
562 left, no_left,
563 child, fill,
564 parent, i - 1);
565 return;
566 }
567 }
568 if (i + 1 < getfill(geo, parent, i)) {
569 right = bval(geo, parent, i + 1);
570 no_right = getfill(geo, right, 0);
571 if (fill + no_right <= geo->no_pairs) {
572 merge(head, geo, level,
573 child, fill,
574 right, no_right,
575 parent, i);
576 return;
577 }
578 }
579 /*
580 * We could also try to steal one entry from the left or right
581 * neighbor. By not doing so we changed the invariant from
582 * "all nodes are at least half full" to "no two neighboring
583 * nodes can be merged". Which means that the average fill of
584 * all nodes is still half or better.
585 */
586}
587
588static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
589 unsigned long *key, int level)
590{
591 unsigned long *node;
592 int i, pos, fill;
593 void *ret;
594
595 if (level > head->height) {
596 /* we recursed all the way up */
597 head->height = 0;
598 head->node = NULL;
599 return NULL;
600 }
601
602 node = find_level(head, geo, key, level);
603 pos = getpos(geo, node, key);
604 fill = getfill(geo, node, pos);
605 if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
606 return NULL;
607 ret = bval(geo, node, pos);
608
609 /* remove and shift */
610 for (i = pos; i < fill - 1; i++) {
611 setkey(geo, node, i, bkey(geo, node, i + 1));
612 setval(geo, node, i, bval(geo, node, i + 1));
613 }
614 clearpair(geo, node, fill - 1);
615
616 if (fill - 1 < geo->no_pairs / 2) {
617 if (level < head->height)
618 rebalance(head, geo, key, level, node, fill - 1);
619 else if (fill - 1 == 1)
620 btree_shrink(head, geo);
621 }
622
623 return ret;
624}
625
626void *btree_remove(struct btree_head *head, struct btree_geo *geo,
627 unsigned long *key)
628{
629 if (head->height == 0)
630 return NULL;
631
632 return btree_remove_level(head, geo, key, 1);
633}
634EXPORT_SYMBOL_GPL(btree_remove);
635
636int btree_merge(struct btree_head *target, struct btree_head *victim,
637 struct btree_geo *geo, gfp_t gfp)
638{
639 unsigned long key[geo->keylen];
640 unsigned long dup[geo->keylen];
641 void *val;
642 int err;
643
644 BUG_ON(target == victim);
645
646 if (!(target->node)) {
647 /* target is empty, just copy fields over */
648 target->node = victim->node;
649 target->height = victim->height;
650 __btree_init(victim);
651 return 0;
652 }
653
654 /* TODO: This needs some optimizations. Currently we do three tree
655 * walks to remove a single object from the victim.
656 */
657 for (;;) {
658 if (!btree_last(victim, geo, key))
659 break;
660 val = btree_lookup(victim, geo, key);
661 err = btree_insert(target, geo, key, val, gfp);
662 if (err)
663 return err;
664 /* We must make a copy of the key, as the original will get
665 * mangled inside btree_remove. */
666 longcpy(dup, key, geo->keylen);
667 btree_remove(victim, geo, dup);
668 }
669 return 0;
670}
671EXPORT_SYMBOL_GPL(btree_merge);
672
673static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
674 unsigned long *node, unsigned long opaque,
675 void (*func)(void *elem, unsigned long opaque,
676 unsigned long *key, size_t index,
677 void *func2),
678 void *func2, int reap, int height, size_t count)
679{
680 int i;
681 unsigned long *child;
682
683 for (i = 0; i < geo->no_pairs; i++) {
684 child = bval(geo, node, i);
685 if (!child)
686 break;
687 if (height > 1)
688 count = __btree_for_each(head, geo, child, opaque,
689 func, func2, reap, height - 1, count);
690 else
691 func(child, opaque, bkey(geo, node, i), count++,
692 func2);
693 }
694 if (reap)
695 mempool_free(node, head->mempool);
696 return count;
697}
698
699static void empty(void *elem, unsigned long opaque, unsigned long *key,
700 size_t index, void *func2)
701{
702}
703
704void visitorl(void *elem, unsigned long opaque, unsigned long *key,
705 size_t index, void *__func)
706{
707 visitorl_t func = __func;
708
709 func(elem, opaque, *key, index);
710}
711EXPORT_SYMBOL_GPL(visitorl);
712
713void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
714 size_t index, void *__func)
715{
716 visitor32_t func = __func;
717 u32 *key = (void *)__key;
718
719 func(elem, opaque, *key, index);
720}
721EXPORT_SYMBOL_GPL(visitor32);
722
723void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
724 size_t index, void *__func)
725{
726 visitor64_t func = __func;
727 u64 *key = (void *)__key;
728
729 func(elem, opaque, *key, index);
730}
731EXPORT_SYMBOL_GPL(visitor64);
732
733void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
734 size_t index, void *__func)
735{
736 visitor128_t func = __func;
737 u64 *key = (void *)__key;
738
739 func(elem, opaque, key[0], key[1], index);
740}
741EXPORT_SYMBOL_GPL(visitor128);
742
743size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
744 unsigned long opaque,
745 void (*func)(void *elem, unsigned long opaque,
746 unsigned long *key,
747 size_t index, void *func2),
748 void *func2)
749{
750 size_t count = 0;
751
752 if (!func2)
753 func = empty;
754 if (head->node)
755 count = __btree_for_each(head, geo, head->node, opaque, func,
756 func2, 0, head->height, 0);
757 return count;
758}
759EXPORT_SYMBOL_GPL(btree_visitor);
760
761size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
762 unsigned long opaque,
763 void (*func)(void *elem, unsigned long opaque,
764 unsigned long *key,
765 size_t index, void *func2),
766 void *func2)
767{
768 size_t count = 0;
769
770 if (!func2)
771 func = empty;
772 if (head->node)
773 count = __btree_for_each(head, geo, head->node, opaque, func,
774 func2, 1, head->height, 0);
775 __btree_init(head);
776 return count;
777}
778EXPORT_SYMBOL_GPL(btree_grim_visitor);
779
780static int __init btree_module_init(void)
781{
782 btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
783 SLAB_HWCACHE_ALIGN, NULL);
784 return 0;
785}
786
787static void __exit btree_module_exit(void)
788{
789 kmem_cache_destroy(btree_cachep);
790}
791
792/* If core code starts using btree, initialization should happen even earlier */
793module_init(btree_module_init);
794module_exit(btree_module_exit);
795
796MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
797MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
798MODULE_LICENSE("GPL");
diff --git a/lib/cpumask.c b/lib/cpumask.c
index 7bb4142a502f..05d6aca7fc19 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -1,3 +1,4 @@
1#include <linux/slab.h>
1#include <linux/kernel.h> 2#include <linux/kernel.h>
2#include <linux/bitops.h> 3#include <linux/bitops.h>
3#include <linux/cpumask.h> 4#include <linux/cpumask.h>
diff --git a/lib/crc32.c b/lib/crc32.c
index 02e3b31b3a79..bc5b936e9142 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -25,16 +25,19 @@
25#include <linux/module.h> 25#include <linux/module.h>
26#include <linux/compiler.h> 26#include <linux/compiler.h>
27#include <linux/types.h> 27#include <linux/types.h>
28#include <linux/slab.h>
29#include <linux/init.h> 28#include <linux/init.h>
30#include <asm/atomic.h> 29#include <asm/atomic.h>
31#include "crc32defs.h" 30#include "crc32defs.h"
32#if CRC_LE_BITS == 8 31#if CRC_LE_BITS == 8
33#define tole(x) __constant_cpu_to_le32(x) 32# define tole(x) __constant_cpu_to_le32(x)
34#define tobe(x) __constant_cpu_to_be32(x)
35#else 33#else
36#define tole(x) (x) 34# define tole(x) (x)
37#define tobe(x) (x) 35#endif
36
37#if CRC_BE_BITS == 8
38# define tobe(x) __constant_cpu_to_be32(x)
39#else
40# define tobe(x) (x)
38#endif 41#endif
39#include "crc32table.h" 42#include "crc32table.h"
40 43
@@ -52,20 +55,19 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
52# else 55# else
53# define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) 56# define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
54# endif 57# endif
55 const u32 *b = (const u32 *)buf; 58 const u32 *b;
56 size_t rem_len; 59 size_t rem_len;
57 60
58 /* Align it */ 61 /* Align it */
59 if (unlikely((long)b & 3 && len)) { 62 if (unlikely((long)buf & 3 && len)) {
60 u8 *p = (u8 *)b;
61 do { 63 do {
62 DO_CRC(*p++); 64 DO_CRC(*buf++);
63 } while ((--len) && ((long)p)&3); 65 } while ((--len) && ((long)buf)&3);
64 b = (u32 *)p;
65 } 66 }
66 rem_len = len & 3; 67 rem_len = len & 3;
67 /* load data 32 bits wide, xor data 32 bits wide. */ 68 /* load data 32 bits wide, xor data 32 bits wide. */
68 len = len >> 2; 69 len = len >> 2;
70 b = (const u32 *)buf;
69 for (--b; len; --len) { 71 for (--b; len; --len) {
70 crc ^= *++b; /* use pre increment for speed */ 72 crc ^= *++b; /* use pre increment for speed */
71 DO_CRC(0); 73 DO_CRC(0);
@@ -82,6 +84,7 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab)
82 } while (--len); 84 } while (--len);
83 } 85 }
84 return crc; 86 return crc;
87#undef DO_CRC
85} 88}
86#endif 89#endif
87/** 90/**
@@ -119,9 +122,6 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
119 crc = __cpu_to_le32(crc); 122 crc = __cpu_to_le32(crc);
120 crc = crc32_body(crc, p, len, tab); 123 crc = crc32_body(crc, p, len, tab);
121 return __le32_to_cpu(crc); 124 return __le32_to_cpu(crc);
122#undef ENDIAN_SHIFT
123#undef DO_CRC
124
125# elif CRC_LE_BITS == 4 125# elif CRC_LE_BITS == 4
126 while (len--) { 126 while (len--) {
127 crc ^= *p++; 127 crc ^= *p++;
@@ -179,9 +179,6 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
179 crc = __cpu_to_be32(crc); 179 crc = __cpu_to_be32(crc);
180 crc = crc32_body(crc, p, len, tab); 180 crc = crc32_body(crc, p, len, tab);
181 return __be32_to_cpu(crc); 181 return __be32_to_cpu(crc);
182#undef ENDIAN_SHIFT
183#undef DO_CRC
184
185# elif CRC_BE_BITS == 4 182# elif CRC_BE_BITS == 4
186 while (len--) { 183 while (len--) {
187 crc ^= *p++ << 24; 184 crc ^= *p++ << 24;
diff --git a/lib/debug_locks.c b/lib/debug_locks.c
index bc3b11731b9c..5bf0020b9248 100644
--- a/lib/debug_locks.c
+++ b/lib/debug_locks.c
@@ -23,6 +23,7 @@
23 * shut up after that. 23 * shut up after that.
24 */ 24 */
25int debug_locks = 1; 25int debug_locks = 1;
26EXPORT_SYMBOL_GPL(debug_locks);
26 27
27/* 28/*
28 * The locking-testsuite uses <debug_locks_silent> to get a 29 * The locking-testsuite uses <debug_locks_silent> to get a
diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index a9a8996d286a..deebcc57d4e6 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -12,6 +12,7 @@
12#include <linux/sched.h> 12#include <linux/sched.h>
13#include <linux/seq_file.h> 13#include <linux/seq_file.h>
14#include <linux/debugfs.h> 14#include <linux/debugfs.h>
15#include <linux/slab.h>
15#include <linux/hash.h> 16#include <linux/hash.h>
16 17
17#define ODEBUG_HASH_BITS 14 18#define ODEBUG_HASH_BITS 14
@@ -140,6 +141,7 @@ alloc_object(void *addr, struct debug_bucket *b, struct debug_obj_descr *descr)
140 obj->object = addr; 141 obj->object = addr;
141 obj->descr = descr; 142 obj->descr = descr;
142 obj->state = ODEBUG_STATE_NONE; 143 obj->state = ODEBUG_STATE_NONE;
144 obj->astate = 0;
143 hlist_del(&obj->node); 145 hlist_del(&obj->node);
144 146
145 hlist_add_head(&obj->node, &b->list); 147 hlist_add_head(&obj->node, &b->list);
@@ -251,8 +253,10 @@ static void debug_print_object(struct debug_obj *obj, char *msg)
251 253
252 if (limit < 5 && obj->descr != descr_test) { 254 if (limit < 5 && obj->descr != descr_test) {
253 limit++; 255 limit++;
254 WARN(1, KERN_ERR "ODEBUG: %s %s object type: %s\n", msg, 256 WARN(1, KERN_ERR "ODEBUG: %s %s (active state %u) "
255 obj_states[obj->state], obj->descr->name); 257 "object type: %s\n",
258 msg, obj_states[obj->state], obj->astate,
259 obj->descr->name);
256 } 260 }
257 debug_objects_warnings++; 261 debug_objects_warnings++;
258} 262}
@@ -446,7 +450,10 @@ void debug_object_deactivate(void *addr, struct debug_obj_descr *descr)
446 case ODEBUG_STATE_INIT: 450 case ODEBUG_STATE_INIT:
447 case ODEBUG_STATE_INACTIVE: 451 case ODEBUG_STATE_INACTIVE:
448 case ODEBUG_STATE_ACTIVE: 452 case ODEBUG_STATE_ACTIVE:
449 obj->state = ODEBUG_STATE_INACTIVE; 453 if (!obj->astate)
454 obj->state = ODEBUG_STATE_INACTIVE;
455 else
456 debug_print_object(obj, "deactivate");
450 break; 457 break;
451 458
452 case ODEBUG_STATE_DESTROYED: 459 case ODEBUG_STATE_DESTROYED:
@@ -552,6 +559,53 @@ out_unlock:
552 raw_spin_unlock_irqrestore(&db->lock, flags); 559 raw_spin_unlock_irqrestore(&db->lock, flags);
553} 560}
554 561
562/**
563 * debug_object_active_state - debug checks object usage state machine
564 * @addr: address of the object
565 * @descr: pointer to an object specific debug description structure
566 * @expect: expected state
567 * @next: state to move to if expected state is found
568 */
569void
570debug_object_active_state(void *addr, struct debug_obj_descr *descr,
571 unsigned int expect, unsigned int next)
572{
573 struct debug_bucket *db;
574 struct debug_obj *obj;
575 unsigned long flags;
576
577 if (!debug_objects_enabled)
578 return;
579
580 db = get_bucket((unsigned long) addr);
581
582 raw_spin_lock_irqsave(&db->lock, flags);
583
584 obj = lookup_object(addr, db);
585 if (obj) {
586 switch (obj->state) {
587 case ODEBUG_STATE_ACTIVE:
588 if (obj->astate == expect)
589 obj->astate = next;
590 else
591 debug_print_object(obj, "active_state");
592 break;
593
594 default:
595 debug_print_object(obj, "active_state");
596 break;
597 }
598 } else {
599 struct debug_obj o = { .object = addr,
600 .state = ODEBUG_STATE_NOTAVAILABLE,
601 .descr = descr };
602
603 debug_print_object(&o, "active_state");
604 }
605
606 raw_spin_unlock_irqrestore(&db->lock, flags);
607}
608
555#ifdef CONFIG_DEBUG_OBJECTS_FREE 609#ifdef CONFIG_DEBUG_OBJECTS_FREE
556static void __debug_check_no_obj_freed(const void *address, unsigned long size) 610static void __debug_check_no_obj_freed(const void *address, unsigned long size)
557{ 611{
@@ -773,7 +827,7 @@ static int __init fixup_free(void *addr, enum debug_obj_state state)
773 } 827 }
774} 828}
775 829
776static int 830static int __init
777check_results(void *addr, enum debug_obj_state state, int fixups, int warnings) 831check_results(void *addr, enum debug_obj_state state, int fixups, int warnings)
778{ 832{
779 struct debug_bucket *db; 833 struct debug_bucket *db;
@@ -916,7 +970,7 @@ void __init debug_objects_early_init(void)
916/* 970/*
917 * Convert the statically allocated objects to dynamic ones: 971 * Convert the statically allocated objects to dynamic ones:
918 */ 972 */
919static int debug_objects_replace_static_objects(void) 973static int __init debug_objects_replace_static_objects(void)
920{ 974{
921 struct debug_bucket *db = obj_hash; 975 struct debug_bucket *db = obj_hash;
922 struct hlist_node *node, *tmp; 976 struct hlist_node *node, *tmp;
diff --git a/lib/decompress_unlzo.c b/lib/decompress_unlzo.c
index db521f45626e..bcb3a4bd68ff 100644
--- a/lib/decompress_unlzo.c
+++ b/lib/decompress_unlzo.c
@@ -97,7 +97,7 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
97 u32 src_len, dst_len; 97 u32 src_len, dst_len;
98 size_t tmp; 98 size_t tmp;
99 u8 *in_buf, *in_buf_save, *out_buf; 99 u8 *in_buf, *in_buf_save, *out_buf;
100 int obytes_processed = 0; 100 int ret = -1;
101 101
102 set_error_fn(error_fn); 102 set_error_fn(error_fn);
103 103
@@ -174,15 +174,22 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
174 174
175 /* decompress */ 175 /* decompress */
176 tmp = dst_len; 176 tmp = dst_len;
177 r = lzo1x_decompress_safe((u8 *) in_buf, src_len, 177
178 /* When the input data is not compressed at all,
179 * lzo1x_decompress_safe will fail, so call memcpy()
180 * instead */
181 if (unlikely(dst_len == src_len))
182 memcpy(out_buf, in_buf, src_len);
183 else {
184 r = lzo1x_decompress_safe((u8 *) in_buf, src_len,
178 out_buf, &tmp); 185 out_buf, &tmp);
179 186
180 if (r != LZO_E_OK || dst_len != tmp) { 187 if (r != LZO_E_OK || dst_len != tmp) {
181 error("Compressed data violation"); 188 error("Compressed data violation");
182 goto exit_2; 189 goto exit_2;
190 }
183 } 191 }
184 192
185 obytes_processed += dst_len;
186 if (flush) 193 if (flush)
187 flush(out_buf, dst_len); 194 flush(out_buf, dst_len);
188 if (output) 195 if (output)
@@ -196,6 +203,7 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
196 in_buf += src_len; 203 in_buf += src_len;
197 } 204 }
198 205
206 ret = 0;
199exit_2: 207exit_2:
200 if (!input) 208 if (!input)
201 free(in_buf); 209 free(in_buf);
@@ -203,7 +211,7 @@ exit_1:
203 if (!output) 211 if (!output)
204 free(out_buf); 212 free(out_buf);
205exit: 213exit:
206 return obytes_processed; 214 return ret;
207} 215}
208 216
209#define decompress unlzo 217#define decompress unlzo
diff --git a/lib/devres.c b/lib/devres.c
index 72c8909006da..49368608f988 100644
--- a/lib/devres.c
+++ b/lib/devres.c
@@ -1,5 +1,6 @@
1#include <linux/pci.h> 1#include <linux/pci.h>
2#include <linux/io.h> 2#include <linux/io.h>
3#include <linux/gfp.h>
3#include <linux/module.h> 4#include <linux/module.h>
4 5
5void devm_ioremap_release(struct device *dev, void *res) 6void devm_ioremap_release(struct device *dev, void *res)
diff --git a/lib/dma-debug.c b/lib/dma-debug.c
index ba8b67039d13..01e64270e246 100644
--- a/lib/dma-debug.c
+++ b/lib/dma-debug.c
@@ -570,7 +570,7 @@ static ssize_t filter_write(struct file *file, const char __user *userbuf,
570 * Now parse out the first token and use it as the name for the 570 * Now parse out the first token and use it as the name for the
571 * driver to filter for. 571 * driver to filter for.
572 */ 572 */
573 for (i = 0; i < NAME_MAX_LEN; ++i) { 573 for (i = 0; i < NAME_MAX_LEN - 1; ++i) {
574 current_driver_name[i] = buf[i]; 574 current_driver_name[i] = buf[i];
575 if (isspace(buf[i]) || buf[i] == ' ' || buf[i] == 0) 575 if (isspace(buf[i]) || buf[i] == ' ' || buf[i] == 0)
576 break; 576 break;
diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c
index f93502915988..d6b8b9b1abfe 100644
--- a/lib/dynamic_debug.c
+++ b/lib/dynamic_debug.c
@@ -25,6 +25,7 @@
25#include <linux/uaccess.h> 25#include <linux/uaccess.h>
26#include <linux/dynamic_debug.h> 26#include <linux/dynamic_debug.h>
27#include <linux/debugfs.h> 27#include <linux/debugfs.h>
28#include <linux/slab.h>
28 29
29extern struct _ddebug __start___verbose[]; 30extern struct _ddebug __start___verbose[];
30extern struct _ddebug __stop___verbose[]; 31extern struct _ddebug __stop___verbose[];
diff --git a/lib/flex_array.c b/lib/flex_array.c
index 66eef2e4483e..41b1804fa728 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -99,7 +99,7 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
99 ret->element_size = element_size; 99 ret->element_size = element_size;
100 ret->total_nr_elements = total; 100 ret->total_nr_elements = total;
101 if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO)) 101 if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
102 memset(ret->parts[0], FLEX_ARRAY_FREE, 102 memset(&ret->parts[0], FLEX_ARRAY_FREE,
103 FLEX_ARRAY_BASE_BYTES_LEFT); 103 FLEX_ARRAY_BASE_BYTES_LEFT);
104 return ret; 104 return ret;
105} 105}
diff --git a/lib/genalloc.c b/lib/genalloc.c
index e67f97495dd5..736c3b06398e 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -10,6 +10,7 @@
10 * Version 2. See the file COPYING for more details. 10 * Version 2. See the file COPYING for more details.
11 */ 11 */
12 12
13#include <linux/slab.h>
13#include <linux/module.h> 14#include <linux/module.h>
14#include <linux/bitmap.h> 15#include <linux/bitmap.h>
15#include <linux/genalloc.h> 16#include <linux/genalloc.h>
diff --git a/lib/hweight.c b/lib/hweight.c
index 389424ecb129..3c79d50814cf 100644
--- a/lib/hweight.c
+++ b/lib/hweight.c
@@ -9,37 +9,45 @@
9 * The Hamming Weight of a number is the total number of bits set in it. 9 * The Hamming Weight of a number is the total number of bits set in it.
10 */ 10 */
11 11
12unsigned int hweight32(unsigned int w) 12unsigned int __sw_hweight32(unsigned int w)
13{ 13{
14#ifdef ARCH_HAS_FAST_MULTIPLIER
15 w -= (w >> 1) & 0x55555555;
16 w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
17 w = (w + (w >> 4)) & 0x0f0f0f0f;
18 return (w * 0x01010101) >> 24;
19#else
14 unsigned int res = w - ((w >> 1) & 0x55555555); 20 unsigned int res = w - ((w >> 1) & 0x55555555);
15 res = (res & 0x33333333) + ((res >> 2) & 0x33333333); 21 res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
16 res = (res + (res >> 4)) & 0x0F0F0F0F; 22 res = (res + (res >> 4)) & 0x0F0F0F0F;
17 res = res + (res >> 8); 23 res = res + (res >> 8);
18 return (res + (res >> 16)) & 0x000000FF; 24 return (res + (res >> 16)) & 0x000000FF;
25#endif
19} 26}
20EXPORT_SYMBOL(hweight32); 27EXPORT_SYMBOL(__sw_hweight32);
21 28
22unsigned int hweight16(unsigned int w) 29unsigned int __sw_hweight16(unsigned int w)
23{ 30{
24 unsigned int res = w - ((w >> 1) & 0x5555); 31 unsigned int res = w - ((w >> 1) & 0x5555);
25 res = (res & 0x3333) + ((res >> 2) & 0x3333); 32 res = (res & 0x3333) + ((res >> 2) & 0x3333);
26 res = (res + (res >> 4)) & 0x0F0F; 33 res = (res + (res >> 4)) & 0x0F0F;
27 return (res + (res >> 8)) & 0x00FF; 34 return (res + (res >> 8)) & 0x00FF;
28} 35}
29EXPORT_SYMBOL(hweight16); 36EXPORT_SYMBOL(__sw_hweight16);
30 37
31unsigned int hweight8(unsigned int w) 38unsigned int __sw_hweight8(unsigned int w)
32{ 39{
33 unsigned int res = w - ((w >> 1) & 0x55); 40 unsigned int res = w - ((w >> 1) & 0x55);
34 res = (res & 0x33) + ((res >> 2) & 0x33); 41 res = (res & 0x33) + ((res >> 2) & 0x33);
35 return (res + (res >> 4)) & 0x0F; 42 return (res + (res >> 4)) & 0x0F;
36} 43}
37EXPORT_SYMBOL(hweight8); 44EXPORT_SYMBOL(__sw_hweight8);
38 45
39unsigned long hweight64(__u64 w) 46unsigned long __sw_hweight64(__u64 w)
40{ 47{
41#if BITS_PER_LONG == 32 48#if BITS_PER_LONG == 32
42 return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w); 49 return __sw_hweight32((unsigned int)(w >> 32)) +
50 __sw_hweight32((unsigned int)w);
43#elif BITS_PER_LONG == 64 51#elif BITS_PER_LONG == 64
44#ifdef ARCH_HAS_FAST_MULTIPLIER 52#ifdef ARCH_HAS_FAST_MULTIPLIER
45 w -= (w >> 1) & 0x5555555555555555ul; 53 w -= (w >> 1) & 0x5555555555555555ul;
@@ -56,4 +64,4 @@ unsigned long hweight64(__u64 w)
56#endif 64#endif
57#endif 65#endif
58} 66}
59EXPORT_SYMBOL(hweight64); 67EXPORT_SYMBOL(__sw_hweight64);
diff --git a/lib/idr.c b/lib/idr.c
index 0dc782216d4b..2eb1dca03681 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -504,7 +504,7 @@ void *idr_find(struct idr *idp, int id)
504 int n; 504 int n;
505 struct idr_layer *p; 505 struct idr_layer *p;
506 506
507 p = rcu_dereference(idp->top); 507 p = rcu_dereference_raw(idp->top);
508 if (!p) 508 if (!p)
509 return NULL; 509 return NULL;
510 n = (p->layer+1) * IDR_BITS; 510 n = (p->layer+1) * IDR_BITS;
@@ -519,7 +519,7 @@ void *idr_find(struct idr *idp, int id)
519 while (n > 0 && p) { 519 while (n > 0 && p) {
520 n -= IDR_BITS; 520 n -= IDR_BITS;
521 BUG_ON(n != p->layer*IDR_BITS); 521 BUG_ON(n != p->layer*IDR_BITS);
522 p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); 522 p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
523 } 523 }
524 return((void *)p); 524 return((void *)p);
525} 525}
@@ -552,7 +552,7 @@ int idr_for_each(struct idr *idp,
552 struct idr_layer **paa = &pa[0]; 552 struct idr_layer **paa = &pa[0];
553 553
554 n = idp->layers * IDR_BITS; 554 n = idp->layers * IDR_BITS;
555 p = rcu_dereference(idp->top); 555 p = rcu_dereference_raw(idp->top);
556 max = 1 << n; 556 max = 1 << n;
557 557
558 id = 0; 558 id = 0;
@@ -560,7 +560,7 @@ int idr_for_each(struct idr *idp,
560 while (n > 0 && p) { 560 while (n > 0 && p) {
561 n -= IDR_BITS; 561 n -= IDR_BITS;
562 *paa++ = p; 562 *paa++ = p;
563 p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); 563 p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
564 } 564 }
565 565
566 if (p) { 566 if (p) {
diff --git a/lib/inflate.c b/lib/inflate.c
index d10255973a9f..677b738c2204 100644
--- a/lib/inflate.c
+++ b/lib/inflate.c
@@ -103,6 +103,7 @@
103 the two sets of lengths. 103 the two sets of lengths.
104 */ 104 */
105#include <linux/compiler.h> 105#include <linux/compiler.h>
106#include <linux/slab.h>
106 107
107#ifdef RCSID 108#ifdef RCSID
108static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #"; 109static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #";
diff --git a/lib/kasprintf.c b/lib/kasprintf.c
index c5ff1fd10030..9c4233b23783 100644
--- a/lib/kasprintf.c
+++ b/lib/kasprintf.c
@@ -6,6 +6,7 @@
6 6
7#include <stdarg.h> 7#include <stdarg.h>
8#include <linux/module.h> 8#include <linux/module.h>
9#include <linux/slab.h>
9#include <linux/types.h> 10#include <linux/types.h>
10#include <linux/string.h> 11#include <linux/string.h>
11 12
diff --git a/lib/kobject.c b/lib/kobject.c
index b512b746d2af..8115eb1bbf4d 100644
--- a/lib/kobject.c
+++ b/lib/kobject.c
@@ -700,7 +700,7 @@ static ssize_t kobj_attr_store(struct kobject *kobj, struct attribute *attr,
700 return ret; 700 return ret;
701} 701}
702 702
703struct sysfs_ops kobj_sysfs_ops = { 703const struct sysfs_ops kobj_sysfs_ops = {
704 .show = kobj_attr_show, 704 .show = kobj_attr_show,
705 .store = kobj_attr_store, 705 .store = kobj_attr_store,
706}; 706};
@@ -789,7 +789,7 @@ static struct kobj_type kset_ktype = {
789 * If the kset was not able to be created, NULL will be returned. 789 * If the kset was not able to be created, NULL will be returned.
790 */ 790 */
791static struct kset *kset_create(const char *name, 791static struct kset *kset_create(const char *name,
792 struct kset_uevent_ops *uevent_ops, 792 const struct kset_uevent_ops *uevent_ops,
793 struct kobject *parent_kobj) 793 struct kobject *parent_kobj)
794{ 794{
795 struct kset *kset; 795 struct kset *kset;
@@ -832,7 +832,7 @@ static struct kset *kset_create(const char *name,
832 * If the kset was not able to be created, NULL will be returned. 832 * If the kset was not able to be created, NULL will be returned.
833 */ 833 */
834struct kset *kset_create_and_add(const char *name, 834struct kset *kset_create_and_add(const char *name,
835 struct kset_uevent_ops *uevent_ops, 835 const struct kset_uevent_ops *uevent_ops,
836 struct kobject *parent_kobj) 836 struct kobject *parent_kobj)
837{ 837{
838 struct kset *kset; 838 struct kset *kset;
diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c
index 920a3ca6e259..7b48d44ced6e 100644
--- a/lib/kobject_uevent.c
+++ b/lib/kobject_uevent.c
@@ -18,6 +18,7 @@
18#include <linux/string.h> 18#include <linux/string.h>
19#include <linux/kobject.h> 19#include <linux/kobject.h>
20#include <linux/module.h> 20#include <linux/module.h>
21#include <linux/slab.h>
21 22
22#include <linux/socket.h> 23#include <linux/socket.h>
23#include <linux/skbuff.h> 24#include <linux/skbuff.h>
@@ -95,7 +96,7 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action,
95 const char *subsystem; 96 const char *subsystem;
96 struct kobject *top_kobj; 97 struct kobject *top_kobj;
97 struct kset *kset; 98 struct kset *kset;
98 struct kset_uevent_ops *uevent_ops; 99 const struct kset_uevent_ops *uevent_ops;
99 u64 seq; 100 u64 seq;
100 int i = 0; 101 int i = 0;
101 int retval = 0; 102 int retval = 0;
diff --git a/lib/kref.c b/lib/kref.c
index 9ecd6e865610..6d19f690380b 100644
--- a/lib/kref.c
+++ b/lib/kref.c
@@ -13,6 +13,7 @@
13 13
14#include <linux/kref.h> 14#include <linux/kref.h>
15#include <linux/module.h> 15#include <linux/module.h>
16#include <linux/slab.h>
16 17
17/** 18/**
18 * kref_set - initialize object and set refcount to requested number. 19 * kref_set - initialize object and set refcount to requested number.
diff --git a/lib/lcm.c b/lib/lcm.c
new file mode 100644
index 000000000000..157cd88a6ffc
--- /dev/null
+++ b/lib/lcm.c
@@ -0,0 +1,15 @@
1#include <linux/kernel.h>
2#include <linux/gcd.h>
3#include <linux/module.h>
4
5/* Lowest common multiple */
6unsigned long lcm(unsigned long a, unsigned long b)
7{
8 if (a && b)
9 return (a * b) / gcd(a, b);
10 else if (b)
11 return b;
12
13 return a;
14}
15EXPORT_SYMBOL_GPL(lcm);
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 19d11e0bb958..4b5cb794c38b 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -4,99 +4,214 @@
4#include <linux/slab.h> 4#include <linux/slab.h>
5#include <linux/list.h> 5#include <linux/list.h>
6 6
7#define MAX_LIST_LENGTH_BITS 20
8
9/*
10 * Returns a list organized in an intermediate format suited
11 * to chaining of merge() calls: null-terminated, no reserved or
12 * sentinel head node, "prev" links not maintained.
13 */
14static struct list_head *merge(void *priv,
15 int (*cmp)(void *priv, struct list_head *a,
16 struct list_head *b),
17 struct list_head *a, struct list_head *b)
18{
19 struct list_head head, *tail = &head;
20
21 while (a && b) {
22 /* if equal, take 'a' -- important for sort stability */
23 if ((*cmp)(priv, a, b) <= 0) {
24 tail->next = a;
25 a = a->next;
26 } else {
27 tail->next = b;
28 b = b->next;
29 }
30 tail = tail->next;
31 }
32 tail->next = a?:b;
33 return head.next;
34}
35
36/*
37 * Combine final list merge with restoration of standard doubly-linked
38 * list structure. This approach duplicates code from merge(), but
39 * runs faster than the tidier alternatives of either a separate final
40 * prev-link restoration pass, or maintaining the prev links
41 * throughout.
42 */
43static void merge_and_restore_back_links(void *priv,
44 int (*cmp)(void *priv, struct list_head *a,
45 struct list_head *b),
46 struct list_head *head,
47 struct list_head *a, struct list_head *b)
48{
49 struct list_head *tail = head;
50
51 while (a && b) {
52 /* if equal, take 'a' -- important for sort stability */
53 if ((*cmp)(priv, a, b) <= 0) {
54 tail->next = a;
55 a->prev = tail;
56 a = a->next;
57 } else {
58 tail->next = b;
59 b->prev = tail;
60 b = b->next;
61 }
62 tail = tail->next;
63 }
64 tail->next = a ? : b;
65
66 do {
67 /*
68 * In worst cases this loop may run many iterations.
69 * Continue callbacks to the client even though no
70 * element comparison is needed, so the client's cmp()
71 * routine can invoke cond_resched() periodically.
72 */
73 (*cmp)(priv, tail, tail);
74
75 tail->next->prev = tail;
76 tail = tail->next;
77 } while (tail->next);
78
79 tail->next = head;
80 head->prev = tail;
81}
82
7/** 83/**
8 * list_sort - sort a list. 84 * list_sort - sort a list
9 * @priv: private data, passed to @cmp 85 * @priv: private data, opaque to list_sort(), passed to @cmp
10 * @head: the list to sort 86 * @head: the list to sort
11 * @cmp: the elements comparison function 87 * @cmp: the elements comparison function
12 * 88 *
13 * This function has been implemented by Mark J Roberts <mjr@znex.org>. It 89 * This function implements "merge sort", which has O(nlog(n))
14 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted 90 * complexity.
15 * in ascending order.
16 * 91 *
17 * The comparison function @cmp is supposed to return a negative value if @a is 92 * The comparison function @cmp must return a negative value if @a
18 * less than @b, and a positive value if @a is greater than @b. If @a and @b 93 * should sort before @b, and a positive value if @a should sort after
19 * are equivalent, then it does not matter what this function returns. 94 * @b. If @a and @b are equivalent, and their original relative
95 * ordering is to be preserved, @cmp must return 0.
20 */ 96 */
21void list_sort(void *priv, struct list_head *head, 97void list_sort(void *priv, struct list_head *head,
22 int (*cmp)(void *priv, struct list_head *a, 98 int (*cmp)(void *priv, struct list_head *a,
23 struct list_head *b)) 99 struct list_head *b))
24{ 100{
25 struct list_head *p, *q, *e, *list, *tail, *oldhead; 101 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
26 int insize, nmerges, psize, qsize, i; 102 -- last slot is a sentinel */
103 int lev; /* index into part[] */
104 int max_lev = 0;
105 struct list_head *list;
27 106
28 if (list_empty(head)) 107 if (list_empty(head))
29 return; 108 return;
30 109
110 memset(part, 0, sizeof(part));
111
112 head->prev->next = NULL;
31 list = head->next; 113 list = head->next;
32 list_del(head);
33 insize = 1;
34 for (;;) {
35 p = oldhead = list;
36 list = tail = NULL;
37 nmerges = 0;
38
39 while (p) {
40 nmerges++;
41 q = p;
42 psize = 0;
43 for (i = 0; i < insize; i++) {
44 psize++;
45 q = q->next == oldhead ? NULL : q->next;
46 if (!q)
47 break;
48 }
49 114
50 qsize = insize; 115 while (list) {
51 while (psize > 0 || (qsize > 0 && q)) { 116 struct list_head *cur = list;
52 if (!psize) { 117 list = list->next;
53 e = q; 118 cur->next = NULL;
54 q = q->next; 119
55 qsize--; 120 for (lev = 0; part[lev]; lev++) {
56 if (q == oldhead) 121 cur = merge(priv, cmp, part[lev], cur);
57 q = NULL; 122 part[lev] = NULL;
58 } else if (!qsize || !q) { 123 }
59 e = p; 124 if (lev > max_lev) {
60 p = p->next; 125 if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
61 psize--; 126 printk_once(KERN_DEBUG "list passed to"
62 if (p == oldhead) 127 " list_sort() too long for"
63 p = NULL; 128 " efficiency\n");
64 } else if (cmp(priv, p, q) <= 0) { 129 lev--;
65 e = p;
66 p = p->next;
67 psize--;
68 if (p == oldhead)
69 p = NULL;
70 } else {
71 e = q;
72 q = q->next;
73 qsize--;
74 if (q == oldhead)
75 q = NULL;
76 }
77 if (tail)
78 tail->next = e;
79 else
80 list = e;
81 e->prev = tail;
82 tail = e;
83 } 130 }
84 p = q; 131 max_lev = lev;
85 } 132 }
133 part[lev] = cur;
134 }
86 135
87 tail->next = list; 136 for (lev = 0; lev < max_lev; lev++)
88 list->prev = tail; 137 if (part[lev])
138 list = merge(priv, cmp, part[lev], list);
89 139
90 if (nmerges <= 1) 140 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
91 break; 141}
142EXPORT_SYMBOL(list_sort);
92 143
93 insize *= 2; 144#ifdef DEBUG_LIST_SORT
94 } 145struct debug_el {
146 struct list_head l_h;
147 int value;
148 unsigned serial;
149};
95 150
96 head->next = list; 151static int cmp(void *priv, struct list_head *a, struct list_head *b)
97 head->prev = list->prev; 152{
98 list->prev->next = head; 153 return container_of(a, struct debug_el, l_h)->value
99 list->prev = head; 154 - container_of(b, struct debug_el, l_h)->value;
100} 155}
101 156
102EXPORT_SYMBOL(list_sort); 157/*
158 * The pattern of set bits in the list length determines which cases
159 * are hit in list_sort().
160 */
161#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
162
163static int __init list_sort_test(void)
164{
165 int i, r = 1, count;
166 struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
167 struct list_head *cur;
168
169 printk(KERN_WARNING "testing list_sort()\n");
170
171 cur = head;
172 for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
173 struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
174 BUG_ON(!el);
175 /* force some equivalencies */
176 el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
177 el->serial = i;
178
179 el->l_h.prev = cur;
180 cur->next = &el->l_h;
181 cur = cur->next;
182 }
183 head->prev = cur;
184
185 list_sort(NULL, head, cmp);
186
187 count = 1;
188 for (cur = head->next; cur->next != head; cur = cur->next) {
189 struct debug_el *el = container_of(cur, struct debug_el, l_h);
190 int cmp_result = cmp(NULL, cur, cur->next);
191 if (cur->next->prev != cur) {
192 printk(KERN_EMERG "list_sort() returned "
193 "a corrupted list!\n");
194 return 1;
195 } else if (cmp_result > 0) {
196 printk(KERN_EMERG "list_sort() failed to sort!\n");
197 return 1;
198 } else if (cmp_result == 0 &&
199 el->serial >= container_of(cur->next,
200 struct debug_el, l_h)->serial) {
201 printk(KERN_EMERG "list_sort() failed to preserve order"
202 " of equivalent elements!\n");
203 return 1;
204 }
205 kfree(cur->prev);
206 count++;
207 }
208 kfree(cur);
209 if (count != LIST_SORT_TEST_LENGTH) {
210 printk(KERN_EMERG "list_sort() returned list of"
211 "different length!\n");
212 return 1;
213 }
214 return 0;
215}
216module_init(list_sort_test);
217#endif
diff --git a/lib/lmb.c b/lib/lmb.c
index 9cee17142b2c..b1fc52606524 100644
--- a/lib/lmb.c
+++ b/lib/lmb.c
@@ -205,9 +205,8 @@ long lmb_add(u64 base, u64 size)
205 205
206} 206}
207 207
208long lmb_remove(u64 base, u64 size) 208static long __lmb_remove(struct lmb_region *rgn, u64 base, u64 size)
209{ 209{
210 struct lmb_region *rgn = &(lmb.memory);
211 u64 rgnbegin, rgnend; 210 u64 rgnbegin, rgnend;
212 u64 end = base + size; 211 u64 end = base + size;
213 int i; 212 int i;
@@ -254,6 +253,16 @@ long lmb_remove(u64 base, u64 size)
254 return lmb_add_region(rgn, end, rgnend - end); 253 return lmb_add_region(rgn, end, rgnend - end);
255} 254}
256 255
256long lmb_remove(u64 base, u64 size)
257{
258 return __lmb_remove(&lmb.memory, base, size);
259}
260
261long __init lmb_free(u64 base, u64 size)
262{
263 return __lmb_remove(&lmb.reserved, base, size);
264}
265
257long __init lmb_reserve(u64 base, u64 size) 266long __init lmb_reserve(u64 base, u64 size)
258{ 267{
259 struct lmb_region *_rgn = &lmb.reserved; 268 struct lmb_region *_rgn = &lmb.reserved;
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 92cdd9936e3d..2a087e0f9863 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -28,7 +28,6 @@
28#include <linux/slab.h> 28#include <linux/slab.h>
29#include <linux/notifier.h> 29#include <linux/notifier.h>
30#include <linux/cpu.h> 30#include <linux/cpu.h>
31#include <linux/gfp.h>
32#include <linux/string.h> 31#include <linux/string.h>
33#include <linux/bitops.h> 32#include <linux/bitops.h>
34#include <linux/rcupdate.h> 33#include <linux/rcupdate.h>
@@ -364,7 +363,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
364 unsigned int height, shift; 363 unsigned int height, shift;
365 struct radix_tree_node *node, **slot; 364 struct radix_tree_node *node, **slot;
366 365
367 node = rcu_dereference(root->rnode); 366 node = rcu_dereference_raw(root->rnode);
368 if (node == NULL) 367 if (node == NULL)
369 return NULL; 368 return NULL;
370 369
@@ -384,7 +383,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
384 do { 383 do {
385 slot = (struct radix_tree_node **) 384 slot = (struct radix_tree_node **)
386 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); 385 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
387 node = rcu_dereference(*slot); 386 node = rcu_dereference_raw(*slot);
388 if (node == NULL) 387 if (node == NULL)
389 return NULL; 388 return NULL;
390 389
@@ -556,6 +555,10 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
556 * 555 *
557 * 0: tag not present or not set 556 * 0: tag not present or not set
558 * 1: tag set 557 * 1: tag set
558 *
559 * Note that the return value of this function may not be relied on, even if
560 * the RCU lock is held, unless tag modification and node deletion are excluded
561 * from concurrency.
559 */ 562 */
560int radix_tree_tag_get(struct radix_tree_root *root, 563int radix_tree_tag_get(struct radix_tree_root *root,
561 unsigned long index, unsigned int tag) 564 unsigned long index, unsigned int tag)
@@ -568,7 +571,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
568 if (!root_tag_get(root, tag)) 571 if (!root_tag_get(root, tag))
569 return 0; 572 return 0;
570 573
571 node = rcu_dereference(root->rnode); 574 node = rcu_dereference_raw(root->rnode);
572 if (node == NULL) 575 if (node == NULL)
573 return 0; 576 return 0;
574 577
@@ -596,13 +599,9 @@ int radix_tree_tag_get(struct radix_tree_root *root,
596 */ 599 */
597 if (!tag_get(node, tag, offset)) 600 if (!tag_get(node, tag, offset))
598 saw_unset_tag = 1; 601 saw_unset_tag = 1;
599 if (height == 1) { 602 if (height == 1)
600 int ret = tag_get(node, tag, offset); 603 return !!tag_get(node, tag, offset);
601 604 node = rcu_dereference_raw(node->slots[offset]);
602 BUG_ON(ret && saw_unset_tag);
603 return !!ret;
604 }
605 node = rcu_dereference(node->slots[offset]);
606 shift -= RADIX_TREE_MAP_SHIFT; 605 shift -= RADIX_TREE_MAP_SHIFT;
607 height--; 606 height--;
608 } 607 }
@@ -711,7 +710,7 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
711 } 710 }
712 711
713 shift -= RADIX_TREE_MAP_SHIFT; 712 shift -= RADIX_TREE_MAP_SHIFT;
714 slot = rcu_dereference(slot->slots[i]); 713 slot = rcu_dereference_raw(slot->slots[i]);
715 if (slot == NULL) 714 if (slot == NULL)
716 goto out; 715 goto out;
717 } 716 }
@@ -758,7 +757,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
758 unsigned long cur_index = first_index; 757 unsigned long cur_index = first_index;
759 unsigned int ret; 758 unsigned int ret;
760 759
761 node = rcu_dereference(root->rnode); 760 node = rcu_dereference_raw(root->rnode);
762 if (!node) 761 if (!node)
763 return 0; 762 return 0;
764 763
@@ -787,7 +786,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
787 slot = *(((void ***)results)[ret + i]); 786 slot = *(((void ***)results)[ret + i]);
788 if (!slot) 787 if (!slot)
789 continue; 788 continue;
790 results[ret + nr_found] = rcu_dereference(slot); 789 results[ret + nr_found] = rcu_dereference_raw(slot);
791 nr_found++; 790 nr_found++;
792 } 791 }
793 ret += nr_found; 792 ret += nr_found;
@@ -826,7 +825,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
826 unsigned long cur_index = first_index; 825 unsigned long cur_index = first_index;
827 unsigned int ret; 826 unsigned int ret;
828 827
829 node = rcu_dereference(root->rnode); 828 node = rcu_dereference_raw(root->rnode);
830 if (!node) 829 if (!node)
831 return 0; 830 return 0;
832 831
@@ -915,7 +914,7 @@ __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
915 } 914 }
916 } 915 }
917 shift -= RADIX_TREE_MAP_SHIFT; 916 shift -= RADIX_TREE_MAP_SHIFT;
918 slot = rcu_dereference(slot->slots[i]); 917 slot = rcu_dereference_raw(slot->slots[i]);
919 if (slot == NULL) 918 if (slot == NULL)
920 break; 919 break;
921 } 920 }
@@ -951,7 +950,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
951 if (!root_tag_get(root, tag)) 950 if (!root_tag_get(root, tag))
952 return 0; 951 return 0;
953 952
954 node = rcu_dereference(root->rnode); 953 node = rcu_dereference_raw(root->rnode);
955 if (!node) 954 if (!node)
956 return 0; 955 return 0;
957 956
@@ -980,7 +979,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
980 slot = *(((void ***)results)[ret + i]); 979 slot = *(((void ***)results)[ret + i]);
981 if (!slot) 980 if (!slot)
982 continue; 981 continue;
983 results[ret + nr_found] = rcu_dereference(slot); 982 results[ret + nr_found] = rcu_dereference_raw(slot);
984 nr_found++; 983 nr_found++;
985 } 984 }
986 ret += nr_found; 985 ret += nr_found;
@@ -1020,7 +1019,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1020 if (!root_tag_get(root, tag)) 1019 if (!root_tag_get(root, tag))
1021 return 0; 1020 return 0;
1022 1021
1023 node = rcu_dereference(root->rnode); 1022 node = rcu_dereference_raw(root->rnode);
1024 if (!node) 1023 if (!node)
1025 return 0; 1024 return 0;
1026 1025
diff --git a/lib/ratelimit.c b/lib/ratelimit.c
index 09f5ce1810dc..027a03f4c56d 100644
--- a/lib/ratelimit.c
+++ b/lib/ratelimit.c
@@ -16,9 +16,14 @@
16/* 16/*
17 * __ratelimit - rate limiting 17 * __ratelimit - rate limiting
18 * @rs: ratelimit_state data 18 * @rs: ratelimit_state data
19 * @func: name of calling function
19 * 20 *
20 * This enforces a rate limit: not more than @rs->ratelimit_burst callbacks 21 * This enforces a rate limit: not more than @rs->burst callbacks
21 * in every @rs->ratelimit_jiffies 22 * in every @rs->interval
23 *
24 * RETURNS:
25 * 0 means callbacks will be suppressed.
26 * 1 means go ahead and do it.
22 */ 27 */
23int ___ratelimit(struct ratelimit_state *rs, const char *func) 28int ___ratelimit(struct ratelimit_state *rs, const char *func)
24{ 29{
@@ -35,7 +40,7 @@ int ___ratelimit(struct ratelimit_state *rs, const char *func)
35 * the entity that is holding the lock already: 40 * the entity that is holding the lock already:
36 */ 41 */
37 if (!spin_trylock_irqsave(&rs->lock, flags)) 42 if (!spin_trylock_irqsave(&rs->lock, flags))
38 return 1; 43 return 0;
39 44
40 if (!rs->begin) 45 if (!rs->begin)
41 rs->begin = jiffies; 46 rs->begin = jiffies;
diff --git a/lib/rbtree.c b/lib/rbtree.c
index e2aa3be29858..15e10b1afdd2 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -44,6 +44,11 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
44 else 44 else
45 root->rb_node = right; 45 root->rb_node = right;
46 rb_set_parent(node, right); 46 rb_set_parent(node, right);
47
48 if (root->augment_cb) {
49 root->augment_cb(node);
50 root->augment_cb(right);
51 }
47} 52}
48 53
49static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 54static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
@@ -67,12 +72,20 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
67 else 72 else
68 root->rb_node = left; 73 root->rb_node = left;
69 rb_set_parent(node, left); 74 rb_set_parent(node, left);
75
76 if (root->augment_cb) {
77 root->augment_cb(node);
78 root->augment_cb(left);
79 }
70} 80}
71 81
72void rb_insert_color(struct rb_node *node, struct rb_root *root) 82void rb_insert_color(struct rb_node *node, struct rb_root *root)
73{ 83{
74 struct rb_node *parent, *gparent; 84 struct rb_node *parent, *gparent;
75 85
86 if (root->augment_cb)
87 root->augment_cb(node);
88
76 while ((parent = rb_parent(node)) && rb_is_red(parent)) 89 while ((parent = rb_parent(node)) && rb_is_red(parent))
77 { 90 {
78 gparent = rb_parent(parent); 91 gparent = rb_parent(parent);
@@ -227,12 +240,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
227 else 240 else
228 { 241 {
229 struct rb_node *old = node, *left; 242 struct rb_node *old = node, *left;
243 int old_parent_cb = 0;
244 int successor_parent_cb = 0;
230 245
231 node = node->rb_right; 246 node = node->rb_right;
232 while ((left = node->rb_left) != NULL) 247 while ((left = node->rb_left) != NULL)
233 node = left; 248 node = left;
234 249
235 if (rb_parent(old)) { 250 if (rb_parent(old)) {
251 old_parent_cb = 1;
236 if (rb_parent(old)->rb_left == old) 252 if (rb_parent(old)->rb_left == old)
237 rb_parent(old)->rb_left = node; 253 rb_parent(old)->rb_left = node;
238 else 254 else
@@ -247,8 +263,10 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
247 if (parent == old) { 263 if (parent == old) {
248 parent = node; 264 parent = node;
249 } else { 265 } else {
266 successor_parent_cb = 1;
250 if (child) 267 if (child)
251 rb_set_parent(child, parent); 268 rb_set_parent(child, parent);
269
252 parent->rb_left = child; 270 parent->rb_left = child;
253 271
254 node->rb_right = old->rb_right; 272 node->rb_right = old->rb_right;
@@ -259,6 +277,24 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
259 node->rb_left = old->rb_left; 277 node->rb_left = old->rb_left;
260 rb_set_parent(old->rb_left, node); 278 rb_set_parent(old->rb_left, node);
261 279
280 if (root->augment_cb) {
281 /*
282 * Here, three different nodes can have new children.
283 * The parent of the successor node that was selected
284 * to replace the node to be erased.
285 * The node that is getting erased and is now replaced
286 * by its successor.
287 * The parent of the node getting erased-replaced.
288 */
289 if (successor_parent_cb)
290 root->augment_cb(parent);
291
292 root->augment_cb(node);
293
294 if (old_parent_cb)
295 root->augment_cb(rb_parent(old));
296 }
297
262 goto color; 298 goto color;
263 } 299 }
264 300
@@ -267,15 +303,19 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
267 303
268 if (child) 304 if (child)
269 rb_set_parent(child, parent); 305 rb_set_parent(child, parent);
270 if (parent) 306
271 { 307 if (parent) {
272 if (parent->rb_left == node) 308 if (parent->rb_left == node)
273 parent->rb_left = child; 309 parent->rb_left = child;
274 else 310 else
275 parent->rb_right = child; 311 parent->rb_right = child;
276 } 312
277 else 313 if (root->augment_cb)
314 root->augment_cb(parent);
315
316 } else {
278 root->rb_node = child; 317 root->rb_node = child;
318 }
279 319
280 color: 320 color:
281 if (color == RB_BLACK) 321 if (color == RB_BLACK)
diff --git a/lib/rwsem-spinlock.c b/lib/rwsem-spinlock.c
index ccf95bff7984..ffc9fc7f3b05 100644
--- a/lib/rwsem-spinlock.c
+++ b/lib/rwsem-spinlock.c
@@ -143,13 +143,14 @@ void __sched __down_read(struct rw_semaphore *sem)
143{ 143{
144 struct rwsem_waiter waiter; 144 struct rwsem_waiter waiter;
145 struct task_struct *tsk; 145 struct task_struct *tsk;
146 unsigned long flags;
146 147
147 spin_lock_irq(&sem->wait_lock); 148 spin_lock_irqsave(&sem->wait_lock, flags);
148 149
149 if (sem->activity >= 0 && list_empty(&sem->wait_list)) { 150 if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
150 /* granted */ 151 /* granted */
151 sem->activity++; 152 sem->activity++;
152 spin_unlock_irq(&sem->wait_lock); 153 spin_unlock_irqrestore(&sem->wait_lock, flags);
153 goto out; 154 goto out;
154 } 155 }
155 156
@@ -164,7 +165,7 @@ void __sched __down_read(struct rw_semaphore *sem)
164 list_add_tail(&waiter.list, &sem->wait_list); 165 list_add_tail(&waiter.list, &sem->wait_list);
165 166
166 /* we don't need to touch the semaphore struct anymore */ 167 /* we don't need to touch the semaphore struct anymore */
167 spin_unlock_irq(&sem->wait_lock); 168 spin_unlock_irqrestore(&sem->wait_lock, flags);
168 169
169 /* wait to be given the lock */ 170 /* wait to be given the lock */
170 for (;;) { 171 for (;;) {
@@ -209,13 +210,14 @@ void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
209{ 210{
210 struct rwsem_waiter waiter; 211 struct rwsem_waiter waiter;
211 struct task_struct *tsk; 212 struct task_struct *tsk;
213 unsigned long flags;
212 214
213 spin_lock_irq(&sem->wait_lock); 215 spin_lock_irqsave(&sem->wait_lock, flags);
214 216
215 if (sem->activity == 0 && list_empty(&sem->wait_list)) { 217 if (sem->activity == 0 && list_empty(&sem->wait_list)) {
216 /* granted */ 218 /* granted */
217 sem->activity = -1; 219 sem->activity = -1;
218 spin_unlock_irq(&sem->wait_lock); 220 spin_unlock_irqrestore(&sem->wait_lock, flags);
219 goto out; 221 goto out;
220 } 222 }
221 223
@@ -230,7 +232,7 @@ void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
230 list_add_tail(&waiter.list, &sem->wait_list); 232 list_add_tail(&waiter.list, &sem->wait_list);
231 233
232 /* we don't need to touch the semaphore struct anymore */ 234 /* we don't need to touch the semaphore struct anymore */
233 spin_unlock_irq(&sem->wait_lock); 235 spin_unlock_irqrestore(&sem->wait_lock, flags);
234 236
235 /* wait to be given the lock */ 237 /* wait to be given the lock */
236 for (;;) { 238 for (;;) {
diff --git a/lib/rwsem.c b/lib/rwsem.c
index 3e3365e5665e..ceba8e28807a 100644
--- a/lib/rwsem.c
+++ b/lib/rwsem.c
@@ -136,9 +136,10 @@ __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
136 out: 136 out:
137 return sem; 137 return sem;
138 138
139 /* undo the change to count, but check for a transition 1->0 */ 139 /* undo the change to the active count, but check for a transition
140 * 1->0 */
140 undo: 141 undo:
141 if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) != 0) 142 if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
142 goto out; 143 goto out;
143 goto try_again; 144 goto try_again;
144} 145}
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 0d475d8167bf..9afa25b52a83 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -7,6 +7,7 @@
7 * Version 2. See the file COPYING for more details. 7 * Version 2. See the file COPYING for more details.
8 */ 8 */
9#include <linux/module.h> 9#include <linux/module.h>
10#include <linux/slab.h>
10#include <linux/scatterlist.h> 11#include <linux/scatterlist.h>
11#include <linux/highmem.h> 12#include <linux/highmem.h>
12 13
diff --git a/lib/show_mem.c b/lib/show_mem.c
index 238e72a18ce1..fdc77c82f922 100644
--- a/lib/show_mem.c
+++ b/lib/show_mem.c
@@ -15,7 +15,7 @@ void show_mem(void)
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(KERN_INFO "Mem-Info:\n"); 18 printk("Mem-Info:\n");
19 show_free_areas(); 19 show_free_areas();
20 20
21 for_each_online_pgdat(pgdat) { 21 for_each_online_pgdat(pgdat) {
@@ -49,15 +49,15 @@ void show_mem(void)
49 pgdat_resize_unlock(pgdat, &flags); 49 pgdat_resize_unlock(pgdat, &flags);
50 } 50 }
51 51
52 printk(KERN_INFO "%lu pages RAM\n", total); 52 printk("%lu pages RAM\n", total);
53#ifdef CONFIG_HIGHMEM 53#ifdef CONFIG_HIGHMEM
54 printk(KERN_INFO "%lu pages HighMem\n", highmem); 54 printk("%lu pages HighMem\n", highmem);
55#endif 55#endif
56 printk(KERN_INFO "%lu pages reserved\n", reserved); 56 printk("%lu pages reserved\n", reserved);
57 printk(KERN_INFO "%lu pages shared\n", shared); 57 printk("%lu pages shared\n", shared);
58 printk(KERN_INFO "%lu pages non-shared\n", nonshared); 58 printk("%lu pages non-shared\n", nonshared);
59#ifdef CONFIG_QUICKLIST 59#ifdef CONFIG_QUICKLIST
60 printk(KERN_INFO "%lu pages in pagetable cache\n", 60 printk("%lu pages in pagetable cache\n",
61 quicklist_total_size()); 61 quicklist_total_size());
62#endif 62#endif
63} 63}
diff --git a/lib/string.c b/lib/string.c
index a1cdcfcc42d0..f71bead1be3e 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -36,25 +36,21 @@ int strnicmp(const char *s1, const char *s2, size_t len)
36 /* Yes, Virginia, it had better be unsigned */ 36 /* Yes, Virginia, it had better be unsigned */
37 unsigned char c1, c2; 37 unsigned char c1, c2;
38 38
39 c1 = c2 = 0; 39 if (!len)
40 if (len) { 40 return 0;
41 do { 41
42 c1 = *s1; 42 do {
43 c2 = *s2; 43 c1 = *s1++;
44 s1++; 44 c2 = *s2++;
45 s2++; 45 if (!c1 || !c2)
46 if (!c1) 46 break;
47 break; 47 if (c1 == c2)
48 if (!c2) 48 continue;
49 break; 49 c1 = tolower(c1);
50 if (c1 == c2) 50 c2 = tolower(c2);
51 continue; 51 if (c1 != c2)
52 c1 = tolower(c1); 52 break;
53 c2 = tolower(c2); 53 } while (--len);
54 if (c1 != c2)
55 break;
56 } while (--len);
57 }
58 return (int)c1 - (int)c2; 54 return (int)c1 - (int)c2;
59} 55}
60EXPORT_SYMBOL(strnicmp); 56EXPORT_SYMBOL(strnicmp);
@@ -693,13 +689,13 @@ EXPORT_SYMBOL(strstr);
693 */ 689 */
694char *strnstr(const char *s1, const char *s2, size_t len) 690char *strnstr(const char *s1, const char *s2, size_t len)
695{ 691{
696 size_t l1 = len, l2; 692 size_t l2;
697 693
698 l2 = strlen(s2); 694 l2 = strlen(s2);
699 if (!l2) 695 if (!l2)
700 return (char *)s1; 696 return (char *)s1;
701 while (l1 >= l2) { 697 while (len >= l2) {
702 l1--; 698 len--;
703 if (!memcmp(s1, s2, l2)) 699 if (!memcmp(s1, s2, l2))
704 return (char *)s1; 700 return (char *)s1;
705 s1++; 701 s1++;
diff --git a/lib/swiotlb.c b/lib/swiotlb.c
index 437eedb5a53b..5fddf720da73 100644
--- a/lib/swiotlb.c
+++ b/lib/swiotlb.c
@@ -28,6 +28,7 @@
28#include <linux/types.h> 28#include <linux/types.h>
29#include <linux/ctype.h> 29#include <linux/ctype.h>
30#include <linux/highmem.h> 30#include <linux/highmem.h>
31#include <linux/gfp.h>
31 32
32#include <asm/io.h> 33#include <asm/io.h>
33#include <asm/dma.h> 34#include <asm/dma.h>
diff --git a/lib/textsearch.c b/lib/textsearch.c
index 9fbcb44c554f..d608331b3e47 100644
--- a/lib/textsearch.c
+++ b/lib/textsearch.c
@@ -103,6 +103,7 @@
103#include <linux/rcupdate.h> 103#include <linux/rcupdate.h>
104#include <linux/err.h> 104#include <linux/err.h>
105#include <linux/textsearch.h> 105#include <linux/textsearch.h>
106#include <linux/slab.h>
106 107
107static LIST_HEAD(ts_ops); 108static LIST_HEAD(ts_ops);
108static DEFINE_SPINLOCK(ts_mod_lock); 109static DEFINE_SPINLOCK(ts_mod_lock);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 3b8aeec4e327..46d34b0b74a8 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -118,6 +118,7 @@ long long simple_strtoll(const char *cp, char **endp, unsigned int base)
118 118
119 return simple_strtoull(cp, endp, base); 119 return simple_strtoull(cp, endp, base);
120} 120}
121EXPORT_SYMBOL(simple_strtoll);
121 122
122/** 123/**
123 * strict_strtoul - convert a string to an unsigned long strictly 124 * strict_strtoul - convert a string to an unsigned long strictly
@@ -381,8 +382,8 @@ static noinline char *put_dec(char *buf, unsigned long long num)
381#define PLUS 4 /* show plus */ 382#define PLUS 4 /* show plus */
382#define SPACE 8 /* space if plus */ 383#define SPACE 8 /* space if plus */
383#define LEFT 16 /* left justified */ 384#define LEFT 16 /* left justified */
384#define SMALL 32 /* Must be 32 == 0x20 */ 385#define SMALL 32 /* use lowercase in hex (must be 32 == 0x20) */
385#define SPECIAL 64 /* 0x */ 386#define SPECIAL 64 /* prefix hex with "0x", octal with "0" */
386 387
387enum format_type { 388enum format_type {
388 FORMAT_TYPE_NONE, /* Just a string part */ 389 FORMAT_TYPE_NONE, /* Just a string part */
@@ -408,12 +409,12 @@ enum format_type {
408}; 409};
409 410
410struct printf_spec { 411struct printf_spec {
411 enum format_type type; 412 u8 type; /* format_type enum */
412 int flags; /* flags to number() */ 413 u8 flags; /* flags to number() */
413 int field_width; /* width of output field */ 414 u8 base; /* number base, 8, 10 or 16 only */
414 int base; 415 u8 qualifier; /* number qualifier, one of 'hHlLtzZ' */
415 int precision; /* # of digits/chars */ 416 s16 field_width; /* width of output field */
416 int qualifier; 417 s16 precision; /* # of digits/chars */
417}; 418};
418 419
419static char *number(char *buf, char *end, unsigned long long num, 420static char *number(char *buf, char *end, unsigned long long num,
@@ -597,22 +598,35 @@ static char *resource_string(char *buf, char *end, struct resource *res,
597#ifndef MEM_RSRC_PRINTK_SIZE 598#ifndef MEM_RSRC_PRINTK_SIZE
598#define MEM_RSRC_PRINTK_SIZE 10 599#define MEM_RSRC_PRINTK_SIZE 10
599#endif 600#endif
600 struct printf_spec hex_spec = { 601 static const struct printf_spec io_spec = {
601 .base = 16, 602 .base = 16,
603 .field_width = IO_RSRC_PRINTK_SIZE,
602 .precision = -1, 604 .precision = -1,
603 .flags = SPECIAL | SMALL | ZEROPAD, 605 .flags = SPECIAL | SMALL | ZEROPAD,
604 }; 606 };
605 struct printf_spec dec_spec = { 607 static const struct printf_spec mem_spec = {
608 .base = 16,
609 .field_width = MEM_RSRC_PRINTK_SIZE,
610 .precision = -1,
611 .flags = SPECIAL | SMALL | ZEROPAD,
612 };
613 static const struct printf_spec bus_spec = {
614 .base = 16,
615 .field_width = 2,
616 .precision = -1,
617 .flags = SMALL | ZEROPAD,
618 };
619 static const struct printf_spec dec_spec = {
606 .base = 10, 620 .base = 10,
607 .precision = -1, 621 .precision = -1,
608 .flags = 0, 622 .flags = 0,
609 }; 623 };
610 struct printf_spec str_spec = { 624 static const struct printf_spec str_spec = {
611 .field_width = -1, 625 .field_width = -1,
612 .precision = 10, 626 .precision = 10,
613 .flags = LEFT, 627 .flags = LEFT,
614 }; 628 };
615 struct printf_spec flag_spec = { 629 static const struct printf_spec flag_spec = {
616 .base = 16, 630 .base = 16,
617 .precision = -1, 631 .precision = -1,
618 .flags = SPECIAL | SMALL, 632 .flags = SPECIAL | SMALL,
@@ -622,47 +636,48 @@ static char *resource_string(char *buf, char *end, struct resource *res,
622 * 64-bit res (sizeof==8): 20 chars in dec, 18 in hex ("0x" + 16) */ 636 * 64-bit res (sizeof==8): 20 chars in dec, 18 in hex ("0x" + 16) */
623#define RSRC_BUF_SIZE ((2 * sizeof(resource_size_t)) + 4) 637#define RSRC_BUF_SIZE ((2 * sizeof(resource_size_t)) + 4)
624#define FLAG_BUF_SIZE (2 * sizeof(res->flags)) 638#define FLAG_BUF_SIZE (2 * sizeof(res->flags))
625#define DECODED_BUF_SIZE sizeof("[mem - 64bit pref disabled]") 639#define DECODED_BUF_SIZE sizeof("[mem - 64bit pref window disabled]")
626#define RAW_BUF_SIZE sizeof("[mem - flags 0x]") 640#define RAW_BUF_SIZE sizeof("[mem - flags 0x]")
627 char sym[max(2*RSRC_BUF_SIZE + DECODED_BUF_SIZE, 641 char sym[max(2*RSRC_BUF_SIZE + DECODED_BUF_SIZE,
628 2*RSRC_BUF_SIZE + FLAG_BUF_SIZE + RAW_BUF_SIZE)]; 642 2*RSRC_BUF_SIZE + FLAG_BUF_SIZE + RAW_BUF_SIZE)];
629 643
630 char *p = sym, *pend = sym + sizeof(sym); 644 char *p = sym, *pend = sym + sizeof(sym);
631 int size = -1, addr = 0;
632 int decode = (fmt[0] == 'R') ? 1 : 0; 645 int decode = (fmt[0] == 'R') ? 1 : 0;
633 646 const struct printf_spec *specp;
634 if (res->flags & IORESOURCE_IO) {
635 size = IO_RSRC_PRINTK_SIZE;
636 addr = 1;
637 } else if (res->flags & IORESOURCE_MEM) {
638 size = MEM_RSRC_PRINTK_SIZE;
639 addr = 1;
640 }
641 647
642 *p++ = '['; 648 *p++ = '[';
643 if (res->flags & IORESOURCE_IO) 649 if (res->flags & IORESOURCE_IO) {
644 p = string(p, pend, "io ", str_spec); 650 p = string(p, pend, "io ", str_spec);
645 else if (res->flags & IORESOURCE_MEM) 651 specp = &io_spec;
652 } else if (res->flags & IORESOURCE_MEM) {
646 p = string(p, pend, "mem ", str_spec); 653 p = string(p, pend, "mem ", str_spec);
647 else if (res->flags & IORESOURCE_IRQ) 654 specp = &mem_spec;
655 } else if (res->flags & IORESOURCE_IRQ) {
648 p = string(p, pend, "irq ", str_spec); 656 p = string(p, pend, "irq ", str_spec);
649 else if (res->flags & IORESOURCE_DMA) 657 specp = &dec_spec;
658 } else if (res->flags & IORESOURCE_DMA) {
650 p = string(p, pend, "dma ", str_spec); 659 p = string(p, pend, "dma ", str_spec);
651 else { 660 specp = &dec_spec;
661 } else if (res->flags & IORESOURCE_BUS) {
662 p = string(p, pend, "bus ", str_spec);
663 specp = &bus_spec;
664 } else {
652 p = string(p, pend, "??? ", str_spec); 665 p = string(p, pend, "??? ", str_spec);
666 specp = &mem_spec;
653 decode = 0; 667 decode = 0;
654 } 668 }
655 hex_spec.field_width = size; 669 p = number(p, pend, res->start, *specp);
656 p = number(p, pend, res->start, addr ? hex_spec : dec_spec);
657 if (res->start != res->end) { 670 if (res->start != res->end) {
658 *p++ = '-'; 671 *p++ = '-';
659 p = number(p, pend, res->end, addr ? hex_spec : dec_spec); 672 p = number(p, pend, res->end, *specp);
660 } 673 }
661 if (decode) { 674 if (decode) {
662 if (res->flags & IORESOURCE_MEM_64) 675 if (res->flags & IORESOURCE_MEM_64)
663 p = string(p, pend, " 64bit", str_spec); 676 p = string(p, pend, " 64bit", str_spec);
664 if (res->flags & IORESOURCE_PREFETCH) 677 if (res->flags & IORESOURCE_PREFETCH)
665 p = string(p, pend, " pref", str_spec); 678 p = string(p, pend, " pref", str_spec);
679 if (res->flags & IORESOURCE_WINDOW)
680 p = string(p, pend, " window", str_spec);
666 if (res->flags & IORESOURCE_DISABLED) 681 if (res->flags & IORESOURCE_DISABLED)
667 p = string(p, pend, " disabled", str_spec); 682 p = string(p, pend, " disabled", str_spec);
668 } else { 683 } else {
@@ -681,24 +696,55 @@ static char *mac_address_string(char *buf, char *end, u8 *addr,
681 char mac_addr[sizeof("xx:xx:xx:xx:xx:xx")]; 696 char mac_addr[sizeof("xx:xx:xx:xx:xx:xx")];
682 char *p = mac_addr; 697 char *p = mac_addr;
683 int i; 698 int i;
699 char separator;
700
701 if (fmt[1] == 'F') { /* FDDI canonical format */
702 separator = '-';
703 } else {
704 separator = ':';
705 }
684 706
685 for (i = 0; i < 6; i++) { 707 for (i = 0; i < 6; i++) {
686 p = pack_hex_byte(p, addr[i]); 708 p = pack_hex_byte(p, addr[i]);
687 if (fmt[0] == 'M' && i != 5) 709 if (fmt[0] == 'M' && i != 5)
688 *p++ = ':'; 710 *p++ = separator;
689 } 711 }
690 *p = '\0'; 712 *p = '\0';
691 713
692 return string(buf, end, mac_addr, spec); 714 return string(buf, end, mac_addr, spec);
693} 715}
694 716
695static char *ip4_string(char *p, const u8 *addr, bool leading_zeros) 717static char *ip4_string(char *p, const u8 *addr, const char *fmt)
696{ 718{
697 int i; 719 int i;
698 720 bool leading_zeros = (fmt[0] == 'i');
721 int index;
722 int step;
723
724 switch (fmt[2]) {
725 case 'h':
726#ifdef __BIG_ENDIAN
727 index = 0;
728 step = 1;
729#else
730 index = 3;
731 step = -1;
732#endif
733 break;
734 case 'l':
735 index = 3;
736 step = -1;
737 break;
738 case 'n':
739 case 'b':
740 default:
741 index = 0;
742 step = 1;
743 break;
744 }
699 for (i = 0; i < 4; i++) { 745 for (i = 0; i < 4; i++) {
700 char temp[3]; /* hold each IP quad in reverse order */ 746 char temp[3]; /* hold each IP quad in reverse order */
701 int digits = put_dec_trunc(temp, addr[i]) - temp; 747 int digits = put_dec_trunc(temp, addr[index]) - temp;
702 if (leading_zeros) { 748 if (leading_zeros) {
703 if (digits < 3) 749 if (digits < 3)
704 *p++ = '0'; 750 *p++ = '0';
@@ -710,6 +756,7 @@ static char *ip4_string(char *p, const u8 *addr, bool leading_zeros)
710 *p++ = temp[digits]; 756 *p++ = temp[digits];
711 if (i < 3) 757 if (i < 3)
712 *p++ = '.'; 758 *p++ = '.';
759 index += step;
713 } 760 }
714 *p = '\0'; 761 *p = '\0';
715 762
@@ -789,7 +836,7 @@ static char *ip6_compressed_string(char *p, const char *addr)
789 if (useIPv4) { 836 if (useIPv4) {
790 if (needcolon) 837 if (needcolon)
791 *p++ = ':'; 838 *p++ = ':';
792 p = ip4_string(p, &in6.s6_addr[12], false); 839 p = ip4_string(p, &in6.s6_addr[12], "I4");
793 } 840 }
794 *p = '\0'; 841 *p = '\0';
795 842
@@ -829,7 +876,7 @@ static char *ip4_addr_string(char *buf, char *end, const u8 *addr,
829{ 876{
830 char ip4_addr[sizeof("255.255.255.255")]; 877 char ip4_addr[sizeof("255.255.255.255")];
831 878
832 ip4_string(ip4_addr, addr, fmt[0] == 'i'); 879 ip4_string(ip4_addr, addr, fmt);
833 880
834 return string(buf, end, ip4_addr, spec); 881 return string(buf, end, ip4_addr, spec);
835} 882}
@@ -896,12 +943,15 @@ static char *uuid_string(char *buf, char *end, const u8 *addr,
896 * - 'M' For a 6-byte MAC address, it prints the address in the 943 * - 'M' For a 6-byte MAC address, it prints the address in the
897 * usual colon-separated hex notation 944 * usual colon-separated hex notation
898 * - 'm' For a 6-byte MAC address, it prints the hex address without colons 945 * - 'm' For a 6-byte MAC address, it prints the hex address without colons
946 * - 'MF' For a 6-byte MAC FDDI address, it prints the address
947 * with a dash-separated hex notation
899 * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way 948 * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way
900 * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) 949 * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4)
901 * IPv6 uses colon separated network-order 16 bit hex with leading 0's 950 * IPv6 uses colon separated network-order 16 bit hex with leading 0's
902 * - 'i' [46] for 'raw' IPv4/IPv6 addresses 951 * - 'i' [46] for 'raw' IPv4/IPv6 addresses
903 * IPv6 omits the colons (01020304...0f) 952 * IPv6 omits the colons (01020304...0f)
904 * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006) 953 * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006)
954 * - '[Ii]4[hnbl]' IPv4 addresses in host, network, big or little endian order
905 * - 'I6c' for IPv6 addresses printed as specified by 955 * - 'I6c' for IPv6 addresses printed as specified by
906 * http://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-00 956 * http://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-00
907 * - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form 957 * - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form
@@ -939,6 +989,7 @@ static char *pointer(const char *fmt, char *buf, char *end, void *ptr,
939 return resource_string(buf, end, ptr, spec, fmt); 989 return resource_string(buf, end, ptr, spec, fmt);
940 case 'M': /* Colon separated: 00:01:02:03:04:05 */ 990 case 'M': /* Colon separated: 00:01:02:03:04:05 */
941 case 'm': /* Contiguous: 000102030405 */ 991 case 'm': /* Contiguous: 000102030405 */
992 /* [mM]F (FDDI, bit reversed) */
942 return mac_address_string(buf, end, ptr, spec, fmt); 993 return mac_address_string(buf, end, ptr, spec, fmt);
943 case 'I': /* Formatted IP supported 994 case 'I': /* Formatted IP supported
944 * 4: 1.2.3.4 995 * 4: 1.2.3.4
@@ -1297,7 +1348,7 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
1297 break; 1348 break;
1298 1349
1299 case FORMAT_TYPE_NRCHARS: { 1350 case FORMAT_TYPE_NRCHARS: {
1300 int qualifier = spec.qualifier; 1351 u8 qualifier = spec.qualifier;
1301 1352
1302 if (qualifier == 'l') { 1353 if (qualifier == 'l') {
1303 long *ip = va_arg(args, long *); 1354 long *ip = va_arg(args, long *);
@@ -1583,7 +1634,7 @@ do { \
1583 1634
1584 case FORMAT_TYPE_NRCHARS: { 1635 case FORMAT_TYPE_NRCHARS: {
1585 /* skip %n 's argument */ 1636 /* skip %n 's argument */
1586 int qualifier = spec.qualifier; 1637 u8 qualifier = spec.qualifier;
1587 void *skip_arg; 1638 void *skip_arg;
1588 if (qualifier == 'l') 1639 if (qualifier == 'l')
1589 skip_arg = va_arg(args, long *); 1640 skip_arg = va_arg(args, long *);
@@ -1849,7 +1900,9 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
1849 char *next; 1900 char *next;
1850 char digit; 1901 char digit;
1851 int num = 0; 1902 int num = 0;
1852 int qualifier, base, field_width; 1903 u8 qualifier;
1904 u8 base;
1905 s16 field_width;
1853 bool is_sign; 1906 bool is_sign;
1854 1907
1855 while (*fmt && *str) { 1908 while (*fmt && *str) {
@@ -1927,7 +1980,7 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
1927 { 1980 {
1928 char *s = (char *)va_arg(args, char *); 1981 char *s = (char *)va_arg(args, char *);
1929 if (field_width == -1) 1982 if (field_width == -1)
1930 field_width = INT_MAX; 1983 field_width = SHORT_MAX;
1931 /* first, skip leading white space in buffer */ 1984 /* first, skip leading white space in buffer */
1932 str = skip_spaces(str); 1985 str = skip_spaces(str);
1933 1986
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c
index 215447c55261..2c13ecc5bb2c 100644
--- a/lib/zlib_inflate/inffast.c
+++ b/lib/zlib_inflate/inffast.c
@@ -8,21 +8,6 @@
8#include "inflate.h" 8#include "inflate.h"
9#include "inffast.h" 9#include "inffast.h"
10 10
11/* Only do the unaligned "Faster" variant when
12 * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is set
13 *
14 * On powerpc, it won't be as we don't include autoconf.h
15 * automatically for the boot wrapper, which is intended as
16 * we run in an environment where we may not be able to deal
17 * with (even rare) alignment faults. In addition, we do not
18 * define __KERNEL__ for arch/powerpc/boot unlike x86
19 */
20
21#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
22#include <asm/unaligned.h>
23#include <asm/byteorder.h>
24#endif
25
26#ifndef ASMINF 11#ifndef ASMINF
27 12
28/* Allow machine dependent optimization for post-increment or pre-increment. 13/* Allow machine dependent optimization for post-increment or pre-increment.
@@ -36,14 +21,31 @@
36 - Pentium III (Anderson) 21 - Pentium III (Anderson)
37 - M68060 (Nikl) 22 - M68060 (Nikl)
38 */ 23 */
24union uu {
25 unsigned short us;
26 unsigned char b[2];
27};
28
29/* Endian independed version */
30static inline unsigned short
31get_unaligned16(const unsigned short *p)
32{
33 union uu mm;
34 unsigned char *b = (unsigned char *)p;
35
36 mm.b[0] = b[0];
37 mm.b[1] = b[1];
38 return mm.us;
39}
40
39#ifdef POSTINC 41#ifdef POSTINC
40# define OFF 0 42# define OFF 0
41# define PUP(a) *(a)++ 43# define PUP(a) *(a)++
42# define UP_UNALIGNED(a) get_unaligned((a)++) 44# define UP_UNALIGNED(a) get_unaligned16((a)++)
43#else 45#else
44# define OFF 1 46# define OFF 1
45# define PUP(a) *++(a) 47# define PUP(a) *++(a)
46# define UP_UNALIGNED(a) get_unaligned(++(a)) 48# define UP_UNALIGNED(a) get_unaligned16(++(a))
47#endif 49#endif
48 50
49/* 51/*
@@ -256,7 +258,6 @@ void inflate_fast(z_streamp strm, unsigned start)
256 } 258 }
257 } 259 }
258 else { 260 else {
259#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
260 unsigned short *sout; 261 unsigned short *sout;
261 unsigned long loops; 262 unsigned long loops;
262 263
@@ -274,22 +275,25 @@ void inflate_fast(z_streamp strm, unsigned start)
274 sfrom = (unsigned short *)(from - OFF); 275 sfrom = (unsigned short *)(from - OFF);
275 loops = len >> 1; 276 loops = len >> 1;
276 do 277 do
278#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
279 PUP(sout) = PUP(sfrom);
280#else
277 PUP(sout) = UP_UNALIGNED(sfrom); 281 PUP(sout) = UP_UNALIGNED(sfrom);
282#endif
278 while (--loops); 283 while (--loops);
279 out = (unsigned char *)sout + OFF; 284 out = (unsigned char *)sout + OFF;
280 from = (unsigned char *)sfrom + OFF; 285 from = (unsigned char *)sfrom + OFF;
281 } else { /* dist == 1 or dist == 2 */ 286 } else { /* dist == 1 or dist == 2 */
282 unsigned short pat16; 287 unsigned short pat16;
283 288
284 pat16 = *(sout-2+2*OFF); 289 pat16 = *(sout-1+OFF);
285 if (dist == 1) 290 if (dist == 1) {
286#if defined(__BIG_ENDIAN) 291 union uu mm;
287 pat16 = (pat16 & 0xff) | ((pat16 & 0xff) << 8); 292 /* copy one char pattern to both bytes */
288#elif defined(__LITTLE_ENDIAN) 293 mm.us = pat16;
289 pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00) >> 8); 294 mm.b[0] = mm.b[1];
290#else 295 pat16 = mm.us;
291#error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined 296 }
292#endif
293 loops = len >> 1; 297 loops = len >> 1;
294 do 298 do
295 PUP(sout) = pat16; 299 PUP(sout) = pat16;
@@ -298,20 +302,6 @@ void inflate_fast(z_streamp strm, unsigned start)
298 } 302 }
299 if (len & 1) 303 if (len & 1)
300 PUP(out) = PUP(from); 304 PUP(out) = PUP(from);
301#else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
302 from = out - dist; /* copy direct from output */
303 do { /* minimum length is three */
304 PUP(out) = PUP(from);
305 PUP(out) = PUP(from);
306 PUP(out) = PUP(from);
307 len -= 3;
308 } while (len > 2);
309 if (len) {
310 PUP(out) = PUP(from);
311 if (len > 1)
312 PUP(out) = PUP(from);
313 }
314#endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
315 } 305 }
316 } 306 }
317 else if ((op & 64) == 0) { /* 2nd level distance code */ 307 else if ((op & 64) == 0) { /* 2nd level distance code */
generated by cgit v1.2.2 (git 2.25.0) at 2025-12-24 19:27:00 -0500