diff options
author | David Woodhouse <David.Woodhouse@intel.com> | 2010-02-26 14:04:15 -0500 |
---|---|---|
committer | David Woodhouse <David.Woodhouse@intel.com> | 2010-02-26 14:06:24 -0500 |
commit | a7790532f5b7358c33a6b1834dc2b318de209f31 (patch) | |
tree | 0ceb9e24b3f54cb5c8453fb5a218e2a94a0f1cce /lib | |
parent | 2764fb4244cc1bc08df3667924ca4a972e90ac70 (diff) | |
parent | 60b341b778cc2929df16c0a504c91621b3c6a4ad (diff) |
Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
The SmartMedia FTL code depends on new kfifo bits from 2.6.33
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Kconfig | 4 | ||||
-rw-r--r-- | lib/Kconfig.debug | 1 | ||||
-rw-r--r-- | lib/Makefile | 3 | ||||
-rw-r--r-- | lib/decompress.c | 5 | ||||
-rw-r--r-- | lib/decompress_bunzip2.c | 10 | ||||
-rw-r--r-- | lib/decompress_unlzo.c | 209 | ||||
-rw-r--r-- | lib/dma-debug.c | 17 | ||||
-rw-r--r-- | lib/idr.c | 4 | ||||
-rw-r--r-- | lib/list_sort.c | 102 | ||||
-rw-r--r-- | lib/lmb.c | 7 | ||||
-rw-r--r-- | lib/lzo/lzo1x_decompress.c | 9 | ||||
-rw-r--r-- | lib/rational.c | 1 | ||||
-rw-r--r-- | lib/string.c | 33 | ||||
-rw-r--r-- | lib/vsprintf.c | 15 | ||||
-rw-r--r-- | lib/zlib_inflate/inffast.c | 75 |
15 files changed, 468 insertions, 27 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 1cfe51628e1b..97b136ff117e 100644 --- a/lib/Kconfig +++ b/lib/Kconfig | |||
@@ -117,6 +117,10 @@ config DECOMPRESS_BZIP2 | |||
117 | config DECOMPRESS_LZMA | 117 | config DECOMPRESS_LZMA |
118 | tristate | 118 | tristate |
119 | 119 | ||
120 | config DECOMPRESS_LZO | ||
121 | select LZO_DECOMPRESS | ||
122 | tristate | ||
123 | |||
120 | # | 124 | # |
121 | # Generic allocator support is selected if needed | 125 | # Generic allocator support is selected if needed |
122 | # | 126 | # |
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 8cf9938dd147..25c3ed594c54 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug | |||
@@ -360,6 +360,7 @@ config DEBUG_KMEMLEAK | |||
360 | select DEBUG_FS if SYSFS | 360 | select DEBUG_FS if SYSFS |
361 | select STACKTRACE if STACKTRACE_SUPPORT | 361 | select STACKTRACE if STACKTRACE_SUPPORT |
362 | select KALLSYMS | 362 | select KALLSYMS |
363 | select CRC32 | ||
363 | help | 364 | help |
364 | Say Y here if you want to enable the memory leak | 365 | Say Y here if you want to enable the memory leak |
365 | detector. The memory allocation/freeing is traced in a way | 366 | detector. The memory allocation/freeing is traced in a way |
diff --git a/lib/Makefile b/lib/Makefile index 347ad8db29d3..3b0b4a696db9 100644 --- a/lib/Makefile +++ b/lib/Makefile | |||
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o | |||
21 | 21 | ||
22 | obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ | 22 | obj-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 | 24 | string_helpers.o gcd.o list_sort.o |
25 | 25 | ||
26 | ifeq ($(CONFIG_DEBUG_KOBJECT),y) | 26 | ifeq ($(CONFIG_DEBUG_KOBJECT),y) |
27 | CFLAGS_kobject.o += -DDEBUG | 27 | CFLAGS_kobject.o += -DDEBUG |
@@ -69,6 +69,7 @@ obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ | |||
69 | lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o | 69 | lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o |
70 | lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o | 70 | lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o |
71 | lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o | 71 | lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o |
72 | lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o | ||
72 | 73 | ||
73 | obj-$(CONFIG_TEXTSEARCH) += textsearch.o | 74 | obj-$(CONFIG_TEXTSEARCH) += textsearch.o |
74 | obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o | 75 | obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o |
diff --git a/lib/decompress.c b/lib/decompress.c index d2842f571674..a7606815541f 100644 --- a/lib/decompress.c +++ b/lib/decompress.c | |||
@@ -9,6 +9,7 @@ | |||
9 | #include <linux/decompress/bunzip2.h> | 9 | #include <linux/decompress/bunzip2.h> |
10 | #include <linux/decompress/unlzma.h> | 10 | #include <linux/decompress/unlzma.h> |
11 | #include <linux/decompress/inflate.h> | 11 | #include <linux/decompress/inflate.h> |
12 | #include <linux/decompress/unlzo.h> | ||
12 | 13 | ||
13 | #include <linux/types.h> | 14 | #include <linux/types.h> |
14 | #include <linux/string.h> | 15 | #include <linux/string.h> |
@@ -22,6 +23,9 @@ | |||
22 | #ifndef CONFIG_DECOMPRESS_LZMA | 23 | #ifndef CONFIG_DECOMPRESS_LZMA |
23 | # define unlzma NULL | 24 | # define unlzma NULL |
24 | #endif | 25 | #endif |
26 | #ifndef CONFIG_DECOMPRESS_LZO | ||
27 | # define unlzo NULL | ||
28 | #endif | ||
25 | 29 | ||
26 | static const struct compress_format { | 30 | static const struct compress_format { |
27 | unsigned char magic[2]; | 31 | unsigned char magic[2]; |
@@ -32,6 +36,7 @@ static const struct compress_format { | |||
32 | { {037, 0236}, "gzip", gunzip }, | 36 | { {037, 0236}, "gzip", gunzip }, |
33 | { {0x42, 0x5a}, "bzip2", bunzip2 }, | 37 | { {0x42, 0x5a}, "bzip2", bunzip2 }, |
34 | { {0x5d, 0x00}, "lzma", unlzma }, | 38 | { {0x5d, 0x00}, "lzma", unlzma }, |
39 | { {0x89, 0x4c}, "lzo", unlzo }, | ||
35 | { {0, 0}, NULL, NULL } | 40 | { {0, 0}, NULL, NULL } |
36 | }; | 41 | }; |
37 | 42 | ||
diff --git a/lib/decompress_bunzip2.c b/lib/decompress_bunzip2.c index 76074209f9a2..a4e971dee102 100644 --- a/lib/decompress_bunzip2.c +++ b/lib/decompress_bunzip2.c | |||
@@ -637,6 +637,8 @@ static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len, | |||
637 | 637 | ||
638 | /* Allocate bunzip_data. Most fields initialize to zero. */ | 638 | /* Allocate bunzip_data. Most fields initialize to zero. */ |
639 | bd = *bdp = malloc(i); | 639 | bd = *bdp = malloc(i); |
640 | if (!bd) | ||
641 | return RETVAL_OUT_OF_MEMORY; | ||
640 | memset(bd, 0, sizeof(struct bunzip_data)); | 642 | memset(bd, 0, sizeof(struct bunzip_data)); |
641 | /* Setup input buffer */ | 643 | /* Setup input buffer */ |
642 | bd->inbuf = inbuf; | 644 | bd->inbuf = inbuf; |
@@ -664,6 +666,8 @@ static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len, | |||
664 | bd->dbufSize = 100000*(i-BZh0); | 666 | bd->dbufSize = 100000*(i-BZh0); |
665 | 667 | ||
666 | bd->dbuf = large_malloc(bd->dbufSize * sizeof(int)); | 668 | bd->dbuf = large_malloc(bd->dbufSize * sizeof(int)); |
669 | if (!bd->dbuf) | ||
670 | return RETVAL_OUT_OF_MEMORY; | ||
667 | return RETVAL_OK; | 671 | return RETVAL_OK; |
668 | } | 672 | } |
669 | 673 | ||
@@ -686,7 +690,7 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, | |||
686 | 690 | ||
687 | if (!outbuf) { | 691 | if (!outbuf) { |
688 | error("Could not allocate output bufer"); | 692 | error("Could not allocate output bufer"); |
689 | return -1; | 693 | return RETVAL_OUT_OF_MEMORY; |
690 | } | 694 | } |
691 | if (buf) | 695 | if (buf) |
692 | inbuf = buf; | 696 | inbuf = buf; |
@@ -694,6 +698,7 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, | |||
694 | inbuf = malloc(BZIP2_IOBUF_SIZE); | 698 | inbuf = malloc(BZIP2_IOBUF_SIZE); |
695 | if (!inbuf) { | 699 | if (!inbuf) { |
696 | error("Could not allocate input bufer"); | 700 | error("Could not allocate input bufer"); |
701 | i = RETVAL_OUT_OF_MEMORY; | ||
697 | goto exit_0; | 702 | goto exit_0; |
698 | } | 703 | } |
699 | i = start_bunzip(&bd, inbuf, len, fill); | 704 | i = start_bunzip(&bd, inbuf, len, fill); |
@@ -720,11 +725,14 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, | |||
720 | } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) { | 725 | } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) { |
721 | error("Compressed file ends unexpectedly"); | 726 | error("Compressed file ends unexpectedly"); |
722 | } | 727 | } |
728 | if (!bd) | ||
729 | goto exit_1; | ||
723 | if (bd->dbuf) | 730 | if (bd->dbuf) |
724 | large_free(bd->dbuf); | 731 | large_free(bd->dbuf); |
725 | if (pos) | 732 | if (pos) |
726 | *pos = bd->inbufPos; | 733 | *pos = bd->inbufPos; |
727 | free(bd); | 734 | free(bd); |
735 | exit_1: | ||
728 | if (!buf) | 736 | if (!buf) |
729 | free(inbuf); | 737 | free(inbuf); |
730 | exit_0: | 738 | exit_0: |
diff --git a/lib/decompress_unlzo.c b/lib/decompress_unlzo.c new file mode 100644 index 000000000000..db521f45626e --- /dev/null +++ b/lib/decompress_unlzo.c | |||
@@ -0,0 +1,209 @@ | |||
1 | /* | ||
2 | * LZO decompressor for the Linux kernel. Code borrowed from the lzo | ||
3 | * implementation by Markus Franz Xaver Johannes Oberhumer. | ||
4 | * | ||
5 | * Linux kernel adaptation: | ||
6 | * Copyright (C) 2009 | ||
7 | * Albin Tonnerre, Free Electrons <albin.tonnerre@free-electrons.com> | ||
8 | * | ||
9 | * Original code: | ||
10 | * Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer | ||
11 | * All Rights Reserved. | ||
12 | * | ||
13 | * lzop and the LZO library are free software; you can redistribute them | ||
14 | * and/or modify them under the terms of the GNU General Public License as | ||
15 | * published by the Free Software Foundation; either version 2 of | ||
16 | * the License, or (at your option) any later version. | ||
17 | * | ||
18 | * This program is distributed in the hope that it will be useful, | ||
19 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
20 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
21 | * GNU General Public License for more details. | ||
22 | * | ||
23 | * You should have received a copy of the GNU General Public License | ||
24 | * along with this program; see the file COPYING. | ||
25 | * If not, write to the Free Software Foundation, Inc., | ||
26 | * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | ||
27 | * | ||
28 | * Markus F.X.J. Oberhumer | ||
29 | * <markus@oberhumer.com> | ||
30 | * http://www.oberhumer.com/opensource/lzop/ | ||
31 | */ | ||
32 | |||
33 | #ifdef STATIC | ||
34 | #include "lzo/lzo1x_decompress.c" | ||
35 | #else | ||
36 | #include <linux/slab.h> | ||
37 | #include <linux/decompress/unlzo.h> | ||
38 | #endif | ||
39 | |||
40 | #include <linux/types.h> | ||
41 | #include <linux/lzo.h> | ||
42 | #include <linux/decompress/mm.h> | ||
43 | |||
44 | #include <linux/compiler.h> | ||
45 | #include <asm/unaligned.h> | ||
46 | |||
47 | static const unsigned char lzop_magic[] = { | ||
48 | 0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a }; | ||
49 | |||
50 | #define LZO_BLOCK_SIZE (256*1024l) | ||
51 | #define HEADER_HAS_FILTER 0x00000800L | ||
52 | |||
53 | STATIC inline int INIT parse_header(u8 *input, u8 *skip) | ||
54 | { | ||
55 | int l; | ||
56 | u8 *parse = input; | ||
57 | u8 level = 0; | ||
58 | u16 version; | ||
59 | |||
60 | /* read magic: 9 first bits */ | ||
61 | for (l = 0; l < 9; l++) { | ||
62 | if (*parse++ != lzop_magic[l]) | ||
63 | return 0; | ||
64 | } | ||
65 | /* get version (2bytes), skip library version (2), | ||
66 | * 'need to be extracted' version (2) and | ||
67 | * method (1) */ | ||
68 | version = get_unaligned_be16(parse); | ||
69 | parse += 7; | ||
70 | if (version >= 0x0940) | ||
71 | level = *parse++; | ||
72 | if (get_unaligned_be32(parse) & HEADER_HAS_FILTER) | ||
73 | parse += 8; /* flags + filter info */ | ||
74 | else | ||
75 | parse += 4; /* flags */ | ||
76 | |||
77 | /* skip mode and mtime_low */ | ||
78 | parse += 8; | ||
79 | if (version >= 0x0940) | ||
80 | parse += 4; /* skip mtime_high */ | ||
81 | |||
82 | l = *parse++; | ||
83 | /* don't care about the file name, and skip checksum */ | ||
84 | parse += l + 4; | ||
85 | |||
86 | *skip = parse - input; | ||
87 | return 1; | ||
88 | } | ||
89 | |||
90 | STATIC inline int INIT unlzo(u8 *input, int in_len, | ||
91 | int (*fill) (void *, unsigned int), | ||
92 | int (*flush) (void *, unsigned int), | ||
93 | u8 *output, int *posp, | ||
94 | void (*error_fn) (char *x)) | ||
95 | { | ||
96 | u8 skip = 0, r = 0; | ||
97 | u32 src_len, dst_len; | ||
98 | size_t tmp; | ||
99 | u8 *in_buf, *in_buf_save, *out_buf; | ||
100 | int obytes_processed = 0; | ||
101 | |||
102 | set_error_fn(error_fn); | ||
103 | |||
104 | if (output) { | ||
105 | out_buf = output; | ||
106 | } else if (!flush) { | ||
107 | error("NULL output pointer and no flush function provided"); | ||
108 | goto exit; | ||
109 | } else { | ||
110 | out_buf = malloc(LZO_BLOCK_SIZE); | ||
111 | if (!out_buf) { | ||
112 | error("Could not allocate output buffer"); | ||
113 | goto exit; | ||
114 | } | ||
115 | } | ||
116 | |||
117 | if (input && fill) { | ||
118 | error("Both input pointer and fill function provided, don't know what to do"); | ||
119 | goto exit_1; | ||
120 | } else if (input) { | ||
121 | in_buf = input; | ||
122 | } else if (!fill || !posp) { | ||
123 | error("NULL input pointer and missing position pointer or fill function"); | ||
124 | goto exit_1; | ||
125 | } else { | ||
126 | in_buf = malloc(lzo1x_worst_compress(LZO_BLOCK_SIZE)); | ||
127 | if (!in_buf) { | ||
128 | error("Could not allocate input buffer"); | ||
129 | goto exit_1; | ||
130 | } | ||
131 | } | ||
132 | in_buf_save = in_buf; | ||
133 | |||
134 | if (posp) | ||
135 | *posp = 0; | ||
136 | |||
137 | if (fill) | ||
138 | fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); | ||
139 | |||
140 | if (!parse_header(input, &skip)) { | ||
141 | error("invalid header"); | ||
142 | goto exit_2; | ||
143 | } | ||
144 | in_buf += skip; | ||
145 | |||
146 | if (posp) | ||
147 | *posp = skip; | ||
148 | |||
149 | for (;;) { | ||
150 | /* read uncompressed block size */ | ||
151 | dst_len = get_unaligned_be32(in_buf); | ||
152 | in_buf += 4; | ||
153 | |||
154 | /* exit if last block */ | ||
155 | if (dst_len == 0) { | ||
156 | if (posp) | ||
157 | *posp += 4; | ||
158 | break; | ||
159 | } | ||
160 | |||
161 | if (dst_len > LZO_BLOCK_SIZE) { | ||
162 | error("dest len longer than block size"); | ||
163 | goto exit_2; | ||
164 | } | ||
165 | |||
166 | /* read compressed block size, and skip block checksum info */ | ||
167 | src_len = get_unaligned_be32(in_buf); | ||
168 | in_buf += 8; | ||
169 | |||
170 | if (src_len <= 0 || src_len > dst_len) { | ||
171 | error("file corrupted"); | ||
172 | goto exit_2; | ||
173 | } | ||
174 | |||
175 | /* decompress */ | ||
176 | tmp = dst_len; | ||
177 | r = lzo1x_decompress_safe((u8 *) in_buf, src_len, | ||
178 | out_buf, &tmp); | ||
179 | |||
180 | if (r != LZO_E_OK || dst_len != tmp) { | ||
181 | error("Compressed data violation"); | ||
182 | goto exit_2; | ||
183 | } | ||
184 | |||
185 | obytes_processed += dst_len; | ||
186 | if (flush) | ||
187 | flush(out_buf, dst_len); | ||
188 | if (output) | ||
189 | out_buf += dst_len; | ||
190 | if (posp) | ||
191 | *posp += src_len + 12; | ||
192 | if (fill) { | ||
193 | in_buf = in_buf_save; | ||
194 | fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); | ||
195 | } else | ||
196 | in_buf += src_len; | ||
197 | } | ||
198 | |||
199 | exit_2: | ||
200 | if (!input) | ||
201 | free(in_buf); | ||
202 | exit_1: | ||
203 | if (!output) | ||
204 | free(out_buf); | ||
205 | exit: | ||
206 | return obytes_processed; | ||
207 | } | ||
208 | |||
209 | #define decompress unlzo | ||
diff --git a/lib/dma-debug.c b/lib/dma-debug.c index d9b08e0f7f55..ba8b67039d13 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c | |||
@@ -587,7 +587,7 @@ out_unlock: | |||
587 | return count; | 587 | return count; |
588 | } | 588 | } |
589 | 589 | ||
590 | const struct file_operations filter_fops = { | 590 | static const struct file_operations filter_fops = { |
591 | .read = filter_read, | 591 | .read = filter_read, |
592 | .write = filter_write, | 592 | .write = filter_write, |
593 | }; | 593 | }; |
@@ -670,12 +670,13 @@ static int device_dma_allocations(struct device *dev) | |||
670 | return count; | 670 | return count; |
671 | } | 671 | } |
672 | 672 | ||
673 | static int dma_debug_device_change(struct notifier_block *nb, | 673 | static int dma_debug_device_change(struct notifier_block *nb, unsigned long action, void *data) |
674 | unsigned long action, void *data) | ||
675 | { | 674 | { |
676 | struct device *dev = data; | 675 | struct device *dev = data; |
677 | int count; | 676 | int count; |
678 | 677 | ||
678 | if (global_disable) | ||
679 | return 0; | ||
679 | 680 | ||
680 | switch (action) { | 681 | switch (action) { |
681 | case BUS_NOTIFY_UNBOUND_DRIVER: | 682 | case BUS_NOTIFY_UNBOUND_DRIVER: |
@@ -697,6 +698,9 @@ void dma_debug_add_bus(struct bus_type *bus) | |||
697 | { | 698 | { |
698 | struct notifier_block *nb; | 699 | struct notifier_block *nb; |
699 | 700 | ||
701 | if (global_disable) | ||
702 | return; | ||
703 | |||
700 | nb = kzalloc(sizeof(struct notifier_block), GFP_KERNEL); | 704 | nb = kzalloc(sizeof(struct notifier_block), GFP_KERNEL); |
701 | if (nb == NULL) { | 705 | if (nb == NULL) { |
702 | pr_err("dma_debug_add_bus: out of memory\n"); | 706 | pr_err("dma_debug_add_bus: out of memory\n"); |
@@ -909,6 +913,9 @@ static void check_sync(struct device *dev, | |||
909 | ref->size); | 913 | ref->size); |
910 | } | 914 | } |
911 | 915 | ||
916 | if (entry->direction == DMA_BIDIRECTIONAL) | ||
917 | goto out; | ||
918 | |||
912 | if (ref->direction != entry->direction) { | 919 | if (ref->direction != entry->direction) { |
913 | err_printk(dev, entry, "DMA-API: device driver syncs " | 920 | err_printk(dev, entry, "DMA-API: device driver syncs " |
914 | "DMA memory with different direction " | 921 | "DMA memory with different direction " |
@@ -919,9 +926,6 @@ static void check_sync(struct device *dev, | |||
919 | dir2name[ref->direction]); | 926 | dir2name[ref->direction]); |
920 | } | 927 | } |
921 | 928 | ||
922 | if (entry->direction == DMA_BIDIRECTIONAL) | ||
923 | goto out; | ||
924 | |||
925 | if (to_cpu && !(entry->direction == DMA_FROM_DEVICE) && | 929 | if (to_cpu && !(entry->direction == DMA_FROM_DEVICE) && |
926 | !(ref->direction == DMA_TO_DEVICE)) | 930 | !(ref->direction == DMA_TO_DEVICE)) |
927 | err_printk(dev, entry, "DMA-API: device driver syncs " | 931 | err_printk(dev, entry, "DMA-API: device driver syncs " |
@@ -944,7 +948,6 @@ static void check_sync(struct device *dev, | |||
944 | 948 | ||
945 | out: | 949 | out: |
946 | put_hash_bucket(bucket, &flags); | 950 | put_hash_bucket(bucket, &flags); |
947 | |||
948 | } | 951 | } |
949 | 952 | ||
950 | void debug_dma_map_page(struct device *dev, struct page *page, size_t offset, | 953 | void debug_dma_map_page(struct device *dev, struct page *page, size_t offset, |
@@ -156,10 +156,12 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) | |||
156 | id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; | 156 | id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; |
157 | 157 | ||
158 | /* if already at the top layer, we need to grow */ | 158 | /* if already at the top layer, we need to grow */ |
159 | if (!(p = pa[l])) { | 159 | if (id >= 1 << (idp->layers * IDR_BITS)) { |
160 | *starting_id = id; | 160 | *starting_id = id; |
161 | return IDR_NEED_TO_GROW; | 161 | return IDR_NEED_TO_GROW; |
162 | } | 162 | } |
163 | p = pa[l]; | ||
164 | BUG_ON(!p); | ||
163 | 165 | ||
164 | /* If we need to go up one layer, continue the | 166 | /* If we need to go up one layer, continue the |
165 | * loop; otherwise, restart from the top. | 167 | * loop; otherwise, restart from the top. |
diff --git a/lib/list_sort.c b/lib/list_sort.c new file mode 100644 index 000000000000..19d11e0bb958 --- /dev/null +++ b/lib/list_sort.c | |||
@@ -0,0 +1,102 @@ | |||
1 | #include <linux/kernel.h> | ||
2 | #include <linux/module.h> | ||
3 | #include <linux/list_sort.h> | ||
4 | #include <linux/slab.h> | ||
5 | #include <linux/list.h> | ||
6 | |||
7 | /** | ||
8 | * list_sort - sort a list. | ||
9 | * @priv: private data, passed to @cmp | ||
10 | * @head: the list to sort | ||
11 | * @cmp: the elements comparison function | ||
12 | * | ||
13 | * This function has been implemented by Mark J Roberts <mjr@znex.org>. It | ||
14 | * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted | ||
15 | * in ascending order. | ||
16 | * | ||
17 | * The comparison function @cmp is supposed to return a negative value if @a is | ||
18 | * less than @b, and a positive value if @a is greater than @b. If @a and @b | ||
19 | * are equivalent, then it does not matter what this function returns. | ||
20 | */ | ||
21 | void list_sort(void *priv, struct list_head *head, | ||
22 | int (*cmp)(void *priv, struct list_head *a, | ||
23 | struct list_head *b)) | ||
24 | { | ||
25 | struct list_head *p, *q, *e, *list, *tail, *oldhead; | ||
26 | int insize, nmerges, psize, qsize, i; | ||
27 | |||
28 | if (list_empty(head)) | ||
29 | return; | ||
30 | |||
31 | 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 | |||
50 | qsize = insize; | ||
51 | while (psize > 0 || (qsize > 0 && q)) { | ||
52 | if (!psize) { | ||
53 | e = q; | ||
54 | q = q->next; | ||
55 | qsize--; | ||
56 | if (q == oldhead) | ||
57 | q = NULL; | ||
58 | } else if (!qsize || !q) { | ||
59 | e = p; | ||
60 | p = p->next; | ||
61 | psize--; | ||
62 | if (p == oldhead) | ||
63 | p = NULL; | ||
64 | } else if (cmp(priv, p, q) <= 0) { | ||
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 | } | ||
84 | p = q; | ||
85 | } | ||
86 | |||
87 | tail->next = list; | ||
88 | list->prev = tail; | ||
89 | |||
90 | if (nmerges <= 1) | ||
91 | break; | ||
92 | |||
93 | insize *= 2; | ||
94 | } | ||
95 | |||
96 | head->next = list; | ||
97 | head->prev = list->prev; | ||
98 | list->prev->next = head; | ||
99 | list->prev = head; | ||
100 | } | ||
101 | |||
102 | EXPORT_SYMBOL(list_sort); | ||
@@ -263,7 +263,7 @@ long __init lmb_reserve(u64 base, u64 size) | |||
263 | return lmb_add_region(_rgn, base, size); | 263 | return lmb_add_region(_rgn, base, size); |
264 | } | 264 | } |
265 | 265 | ||
266 | long __init lmb_overlaps_region(struct lmb_region *rgn, u64 base, u64 size) | 266 | long lmb_overlaps_region(struct lmb_region *rgn, u64 base, u64 size) |
267 | { | 267 | { |
268 | unsigned long i; | 268 | unsigned long i; |
269 | 269 | ||
@@ -493,6 +493,11 @@ int __init lmb_is_reserved(u64 addr) | |||
493 | return 0; | 493 | return 0; |
494 | } | 494 | } |
495 | 495 | ||
496 | int lmb_is_region_reserved(u64 base, u64 size) | ||
497 | { | ||
498 | return lmb_overlaps_region(&lmb.reserved, base, size); | ||
499 | } | ||
500 | |||
496 | /* | 501 | /* |
497 | * Given a <base, len>, find which memory regions belong to this range. | 502 | * Given a <base, len>, find which memory regions belong to this range. |
498 | * Adjust the request and return a contiguous chunk. | 503 | * Adjust the request and return a contiguous chunk. |
diff --git a/lib/lzo/lzo1x_decompress.c b/lib/lzo/lzo1x_decompress.c index 5dc6b29c1575..f2fd09850223 100644 --- a/lib/lzo/lzo1x_decompress.c +++ b/lib/lzo/lzo1x_decompress.c | |||
@@ -11,11 +11,13 @@ | |||
11 | * Richard Purdie <rpurdie@openedhand.com> | 11 | * Richard Purdie <rpurdie@openedhand.com> |
12 | */ | 12 | */ |
13 | 13 | ||
14 | #ifndef STATIC | ||
14 | #include <linux/module.h> | 15 | #include <linux/module.h> |
15 | #include <linux/kernel.h> | 16 | #include <linux/kernel.h> |
16 | #include <linux/lzo.h> | 17 | #endif |
17 | #include <asm/byteorder.h> | 18 | |
18 | #include <asm/unaligned.h> | 19 | #include <asm/unaligned.h> |
20 | #include <linux/lzo.h> | ||
19 | #include "lzodefs.h" | 21 | #include "lzodefs.h" |
20 | 22 | ||
21 | #define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x)) | 23 | #define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x)) |
@@ -244,9 +246,10 @@ lookbehind_overrun: | |||
244 | *out_len = op - out; | 246 | *out_len = op - out; |
245 | return LZO_E_LOOKBEHIND_OVERRUN; | 247 | return LZO_E_LOOKBEHIND_OVERRUN; |
246 | } | 248 | } |
247 | 249 | #ifndef STATIC | |
248 | EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); | 250 | EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); |
249 | 251 | ||
250 | MODULE_LICENSE("GPL"); | 252 | MODULE_LICENSE("GPL"); |
251 | MODULE_DESCRIPTION("LZO1X Decompressor"); | 253 | MODULE_DESCRIPTION("LZO1X Decompressor"); |
252 | 254 | ||
255 | #endif | ||
diff --git a/lib/rational.c b/lib/rational.c index b3c099b5478e..3ed247b80662 100644 --- a/lib/rational.c +++ b/lib/rational.c | |||
@@ -7,6 +7,7 @@ | |||
7 | */ | 7 | */ |
8 | 8 | ||
9 | #include <linux/rational.h> | 9 | #include <linux/rational.h> |
10 | #include <linux/module.h> | ||
10 | 11 | ||
11 | /* | 12 | /* |
12 | * calculate best rational approximation for a given fraction | 13 | * calculate best rational approximation for a given fraction |
diff --git a/lib/string.c b/lib/string.c index afce96af3afd..a1cdcfcc42d0 100644 --- a/lib/string.c +++ b/lib/string.c | |||
@@ -338,10 +338,10 @@ EXPORT_SYMBOL(strnchr); | |||
338 | #endif | 338 | #endif |
339 | 339 | ||
340 | /** | 340 | /** |
341 | * skip_spaces - Removes leading whitespace from @s. | 341 | * skip_spaces - Removes leading whitespace from @str. |
342 | * @s: The string to be stripped. | 342 | * @str: The string to be stripped. |
343 | * | 343 | * |
344 | * Returns a pointer to the first non-whitespace character in @s. | 344 | * Returns a pointer to the first non-whitespace character in @str. |
345 | */ | 345 | */ |
346 | char *skip_spaces(const char *str) | 346 | char *skip_spaces(const char *str) |
347 | { | 347 | { |
@@ -667,7 +667,7 @@ EXPORT_SYMBOL(memscan); | |||
667 | */ | 667 | */ |
668 | char *strstr(const char *s1, const char *s2) | 668 | char *strstr(const char *s1, const char *s2) |
669 | { | 669 | { |
670 | int l1, l2; | 670 | size_t l1, l2; |
671 | 671 | ||
672 | l2 = strlen(s2); | 672 | l2 = strlen(s2); |
673 | if (!l2) | 673 | if (!l2) |
@@ -684,6 +684,31 @@ char *strstr(const char *s1, const char *s2) | |||
684 | EXPORT_SYMBOL(strstr); | 684 | EXPORT_SYMBOL(strstr); |
685 | #endif | 685 | #endif |
686 | 686 | ||
687 | #ifndef __HAVE_ARCH_STRNSTR | ||
688 | /** | ||
689 | * strnstr - Find the first substring in a length-limited string | ||
690 | * @s1: The string to be searched | ||
691 | * @s2: The string to search for | ||
692 | * @len: the maximum number of characters to search | ||
693 | */ | ||
694 | char *strnstr(const char *s1, const char *s2, size_t len) | ||
695 | { | ||
696 | size_t l1 = len, l2; | ||
697 | |||
698 | l2 = strlen(s2); | ||
699 | if (!l2) | ||
700 | return (char *)s1; | ||
701 | while (l1 >= l2) { | ||
702 | l1--; | ||
703 | if (!memcmp(s1, s2, l2)) | ||
704 | return (char *)s1; | ||
705 | s1++; | ||
706 | } | ||
707 | return NULL; | ||
708 | } | ||
709 | EXPORT_SYMBOL(strnstr); | ||
710 | #endif | ||
711 | |||
687 | #ifndef __HAVE_ARCH_MEMCHR | 712 | #ifndef __HAVE_ARCH_MEMCHR |
688 | /** | 713 | /** |
689 | * memchr - Find a character in an area of memory. | 714 | * memchr - Find a character in an area of memory. |
diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 735343fc857a..3b8aeec4e327 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c | |||
@@ -903,7 +903,7 @@ static char *uuid_string(char *buf, char *end, const u8 *addr, | |||
903 | * IPv6 omits the colons (01020304...0f) | 903 | * IPv6 omits the colons (01020304...0f) |
904 | * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006) | 904 | * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006) |
905 | * - 'I6c' for IPv6 addresses printed as specified by | 905 | * - 'I6c' for IPv6 addresses printed as specified by |
906 | * http://www.ietf.org/id/draft-kawamura-ipv6-text-representation-03.txt | 906 | * 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 | 907 | * - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form |
908 | * "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx" | 908 | * "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx" |
909 | * Options for %pU are: | 909 | * Options for %pU are: |
@@ -1179,7 +1179,18 @@ qualifier: | |||
1179 | * %ps output the name of a text symbol without offset | 1179 | * %ps output the name of a text symbol without offset |
1180 | * %pF output the name of a function pointer with its offset | 1180 | * %pF output the name of a function pointer with its offset |
1181 | * %pf output the name of a function pointer without its offset | 1181 | * %pf output the name of a function pointer without its offset |
1182 | * %pR output the address range in a struct resource | 1182 | * %pR output the address range in a struct resource with decoded flags |
1183 | * %pr output the address range in a struct resource with raw flags | ||
1184 | * %pM output a 6-byte MAC address with colons | ||
1185 | * %pm output a 6-byte MAC address without colons | ||
1186 | * %pI4 print an IPv4 address without leading zeros | ||
1187 | * %pi4 print an IPv4 address with leading zeros | ||
1188 | * %pI6 print an IPv6 address with colons | ||
1189 | * %pi6 print an IPv6 address without colons | ||
1190 | * %pI6c print an IPv6 address as specified by | ||
1191 | * http://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-00 | ||
1192 | * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper | ||
1193 | * case. | ||
1183 | * %n is ignored | 1194 | * %n is ignored |
1184 | * | 1195 | * |
1185 | * The return value is the number of characters which would | 1196 | * The return value is the number of characters which would |
diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index 8550b0c05d00..215447c55261 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c | |||
@@ -8,6 +8,21 @@ | |||
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 | |||
11 | #ifndef ASMINF | 26 | #ifndef ASMINF |
12 | 27 | ||
13 | /* Allow machine dependent optimization for post-increment or pre-increment. | 28 | /* Allow machine dependent optimization for post-increment or pre-increment. |
@@ -24,9 +39,11 @@ | |||
24 | #ifdef POSTINC | 39 | #ifdef POSTINC |
25 | # define OFF 0 | 40 | # define OFF 0 |
26 | # define PUP(a) *(a)++ | 41 | # define PUP(a) *(a)++ |
42 | # define UP_UNALIGNED(a) get_unaligned((a)++) | ||
27 | #else | 43 | #else |
28 | # define OFF 1 | 44 | # define OFF 1 |
29 | # define PUP(a) *++(a) | 45 | # define PUP(a) *++(a) |
46 | # define UP_UNALIGNED(a) get_unaligned(++(a)) | ||
30 | #endif | 47 | #endif |
31 | 48 | ||
32 | /* | 49 | /* |
@@ -239,18 +256,62 @@ void inflate_fast(z_streamp strm, unsigned start) | |||
239 | } | 256 | } |
240 | } | 257 | } |
241 | else { | 258 | else { |
259 | #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS | ||
260 | unsigned short *sout; | ||
261 | unsigned long loops; | ||
262 | |||
263 | from = out - dist; /* copy direct from output */ | ||
264 | /* minimum length is three */ | ||
265 | /* Align out addr */ | ||
266 | if (!((long)(out - 1 + OFF) & 1)) { | ||
267 | PUP(out) = PUP(from); | ||
268 | len--; | ||
269 | } | ||
270 | sout = (unsigned short *)(out - OFF); | ||
271 | if (dist > 2) { | ||
272 | unsigned short *sfrom; | ||
273 | |||
274 | sfrom = (unsigned short *)(from - OFF); | ||
275 | loops = len >> 1; | ||
276 | do | ||
277 | PUP(sout) = UP_UNALIGNED(sfrom); | ||
278 | while (--loops); | ||
279 | out = (unsigned char *)sout + OFF; | ||
280 | from = (unsigned char *)sfrom + OFF; | ||
281 | } else { /* dist == 1 or dist == 2 */ | ||
282 | unsigned short pat16; | ||
283 | |||
284 | pat16 = *(sout-2+2*OFF); | ||
285 | if (dist == 1) | ||
286 | #if defined(__BIG_ENDIAN) | ||
287 | pat16 = (pat16 & 0xff) | ((pat16 & 0xff) << 8); | ||
288 | #elif defined(__LITTLE_ENDIAN) | ||
289 | pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00) >> 8); | ||
290 | #else | ||
291 | #error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined | ||
292 | #endif | ||
293 | loops = len >> 1; | ||
294 | do | ||
295 | PUP(sout) = pat16; | ||
296 | while (--loops); | ||
297 | out = (unsigned char *)sout + OFF; | ||
298 | } | ||
299 | if (len & 1) | ||
300 | PUP(out) = PUP(from); | ||
301 | #else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ | ||
242 | from = out - dist; /* copy direct from output */ | 302 | from = out - dist; /* copy direct from output */ |
243 | do { /* minimum length is three */ | 303 | do { /* minimum length is three */ |
244 | PUP(out) = PUP(from); | 304 | PUP(out) = PUP(from); |
245 | PUP(out) = PUP(from); | 305 | PUP(out) = PUP(from); |
246 | PUP(out) = PUP(from); | 306 | PUP(out) = PUP(from); |
247 | len -= 3; | 307 | len -= 3; |
248 | } while (len > 2); | 308 | } while (len > 2); |
249 | if (len) { | 309 | if (len) { |
250 | PUP(out) = PUP(from); | 310 | PUP(out) = PUP(from); |
251 | if (len > 1) | 311 | if (len > 1) |
252 | PUP(out) = PUP(from); | 312 | PUP(out) = PUP(from); |
253 | } | 313 | } |
314 | #endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ | ||
254 | } | 315 | } |
255 | } | 316 | } |
256 | else if ((op & 64) == 0) { /* 2nd level distance code */ | 317 | else if ((op & 64) == 0) { /* 2nd level distance code */ |