From f797d9881b62c2ddb1d2e7bd80d87141949c84aa Mon Sep 17 00:00:00 2001 From: Shaun Ruffell Date: Thu, 17 Dec 2009 18:00:36 -0600 Subject: dma-debug: Do not add notifier when dma debugging is disabled. If CONFIG_HAVE_DMA_API_DEBUG is defined and "dma_debug=off" is specified on the kernel command line, when you detach a driver from a device you can cause the following NULL pointer dereference: BUG: unable to handle kernel NULL pointer dereference at (null) IP: [] dma_debug_device_change+0x5d/0x117 The problem is that the dma_debug_device_change notifier function is added to the bus notifier chain even though the dma_entry_hash array was never initialized. If dma debugging is disabled, this patch both prevents dma_debug_device_change notifiers from being added to the chain, and additionally ensures that the dma_debug_device_change notifier function is a no-op. Cc: stable@kernel.org Signed-off-by: Shaun Ruffell Signed-off-by: Joerg Roedel --- lib/dma-debug.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index d9b08e0f7f55..739974460c32 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -676,6 +676,8 @@ static int dma_debug_device_change(struct notifier_block *nb, struct device *dev = data; int count; + if (global_disable) + return; switch (action) { case BUS_NOTIFY_UNBOUND_DRIVER: @@ -697,6 +699,9 @@ void dma_debug_add_bus(struct bus_type *bus) { struct notifier_block *nb; + if (global_disable) + return; + nb = kzalloc(sizeof(struct notifier_block), GFP_KERNEL); if (nb == NULL) { pr_err("dma_debug_add_bus: out of memory\n"); -- cgit v1.2.3 From a8fe9ea200ea21421ea750423d1d4d4f7ce037cf Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Thu, 31 Dec 2009 15:16:23 +0100 Subject: dma-debug: Fix bug causing build warning Stephen Rothwell reported the following build warning: lib/dma-debug.c: In function 'dma_debug_device_change': lib/dma-debug.c:680: warning: 'return' with no value, in function returning non-void Introduced by commit f797d9881b62c2ddb1d2e7bd80d87141949c84aa ("dma-debug: Do not add notifier when dma debugging is disabled"). Return 0 [notify-done] when disabled. (this is standard bus notifier behavior.) Signed-off-by: Shaun Ruffell Signed-off-by: Joerg Roedel Cc: Linus Torvalds Cc: LKML-Reference: <20091231125624.GA14666@liondog.tnic> Signed-off-by: Ingo Molnar --- lib/dma-debug.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 739974460c32..cf906201aecf 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -670,14 +670,13 @@ static int device_dma_allocations(struct device *dev) return count; } -static int dma_debug_device_change(struct notifier_block *nb, - unsigned long action, void *data) +static int dma_debug_device_change(struct notifier_block *nb, unsigned long action, void *data) { struct device *dev = data; int count; if (global_disable) - return; + return 0; switch (action) { case BUS_NOTIFY_UNBOUND_DRIVER: -- cgit v1.2.3 From 42d53b4ff7d61487d18274ebdf1f70c1aef6f122 Mon Sep 17 00:00:00 2001 From: Krzysztof Halasa Date: Fri, 8 Jan 2010 14:42:36 -0800 Subject: dma-debug: allow DMA_BIDIRECTIONAL mappings to be synced with DMA_FROM_DEVICE and There is no need to perform full BIDIR sync (copying the buffers in case of swiotlb and similar schemes) if we know that the owner (CPU or device) hasn't altered the data. Addresses the false-positive reported at http://bugzilla.kernel.org/show_bug.cgi?id=14169 Signed-off-by: Krzysztof Halasa Cc: David Miller Cc: Joerg Roedel Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/dma-debug.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index cf906201aecf..7d2f0b33e5a8 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -913,6 +913,9 @@ static void check_sync(struct device *dev, ref->size); } + if (entry->direction == DMA_BIDIRECTIONAL) + goto out; + if (ref->direction != entry->direction) { err_printk(dev, entry, "DMA-API: device driver syncs " "DMA memory with different direction " @@ -923,9 +926,6 @@ static void check_sync(struct device *dev, dir2name[ref->direction]); } - if (entry->direction == DMA_BIDIRECTIONAL) - goto out; - if (to_cpu && !(entry->direction == DMA_FROM_DEVICE) && !(ref->direction == DMA_TO_DEVICE)) err_printk(dev, entry, "DMA-API: device driver syncs " @@ -948,7 +948,6 @@ static void check_sync(struct device *dev, out: put_hash_bucket(bucket, &flags); - } void debug_dma_map_page(struct device *dev, struct page *page, size_t offset, -- cgit v1.2.3 From ac4c2a3bbe5db5fc570b1d0ee1e474db7cb22585 Mon Sep 17 00:00:00 2001 From: Joakim Tjernlund Date: Fri, 8 Jan 2010 14:42:40 -0800 Subject: zlib: optimize inffast when copying direct from output JFFS2 uses lesser compression ratio and inflate always ends up in "copy direct from output" case. This patch tries to optimize the direct copy procedure. Uses get_unaligned() but only in one place. The copy loop just above this one can also use this optimization, but I havn't done so as I have not tested if it is a win there too. On my MPC8321 this is about 17% faster on my JFFS2 root FS than the original. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Joakim Tjernlund Cc: Roel Kluin Cc: Richard Purdie Cc: David Woodhouse Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/zlib_inflate/inffast.c | 55 ++++++++++++++++++++++++++++++++++++---------- 1 file changed, 44 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index 8550b0c05d00..05e1559fa156 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c @@ -4,6 +4,8 @@ */ #include +#include +#include #include "inftrees.h" #include "inflate.h" #include "inffast.h" @@ -24,9 +26,11 @@ #ifdef POSTINC # define OFF 0 # define PUP(a) *(a)++ +# define UP_UNALIGNED(a) get_unaligned((a)++) #else # define OFF 1 # define PUP(a) *++(a) +# define UP_UNALIGNED(a) get_unaligned(++(a)) #endif /* @@ -239,18 +243,47 @@ void inflate_fast(z_streamp strm, unsigned start) } } else { + unsigned short *sout; + unsigned long loops; + from = out - dist; /* copy direct from output */ - do { /* minimum length is three */ - PUP(out) = PUP(from); - PUP(out) = PUP(from); - PUP(out) = PUP(from); - len -= 3; - } while (len > 2); - if (len) { - PUP(out) = PUP(from); - if (len > 1) - PUP(out) = PUP(from); - } + /* minimum length is three */ + /* Align out addr */ + if (!((long)(out - 1 + OFF) & 1)) { + PUP(out) = PUP(from); + len--; + } + sout = (unsigned short *)(out - OFF); + if (dist > 2) { + unsigned short *sfrom; + + sfrom = (unsigned short *)(from - OFF); + loops = len >> 1; + do + PUP(sout) = UP_UNALIGNED(sfrom); + while (--loops); + out = (unsigned char *)sout + OFF; + from = (unsigned char *)sfrom + OFF; + } else { /* dist == 1 or dist == 2 */ + unsigned short pat16; + + pat16 = *(sout-2+2*OFF); + if (dist == 1) +#if defined(__BIG_ENDIAN) + pat16 = (pat16 & 0xff) | ((pat16 & 0xff) << 8); +#elif defined(__LITTLE_ENDIAN) + pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00) >> 8); +#else +#error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined +#endif + loops = len >> 1; + do + PUP(sout) = pat16; + while (--loops); + out = (unsigned char *)sout + OFF; + } + if (len & 1) + PUP(out) = PUP(from); } } else if ((op & 64) == 0) { /* 2nd level distance code */ -- cgit v1.2.3 From 7dd65feb6c603e13eba501c34c662259ab38e70e Mon Sep 17 00:00:00 2001 From: Albin Tonnerre Date: Fri, 8 Jan 2010 14:42:42 -0800 Subject: lib: add support for LZO-compressed kernels This patch series adds generic support for creating and extracting LZO-compressed kernel images, as well as support for using such images on the x86 and ARM architectures, and support for creating and using LZO-compressed initrd and initramfs images. Russell King said: : Testing on a Cortex A9 model: : - lzo decompressor is 65% of the time gzip takes to decompress a kernel : - lzo kernel is 9% larger than a gzip kernel : : which I'm happy to say confirms your figures when comparing the two. : : However, when comparing your new gzip code to the old gzip code: : - new is 99% of the size of the old code : - new takes 42% of the time to decompress than the old code : : What this means is that for a proper comparison, the results get even better: : - lzo is 7.5% larger than the old gzip'd kernel image : - lzo takes 28% of the time that the old gzip code took : : So the expense seems definitely worth the effort. The only reason I : can think of ever using gzip would be if you needed the additional : compression (eg, because you have limited flash to store the image.) : : I would argue that the default for ARM should therefore be LZO. This patch: The lzo compressor is worse than gzip at compression, but faster at extraction. Here are some figures for an ARM board I'm working on: Uncompressed size: 3.24Mo gzip 1.61Mo 0.72s lzo 1.75Mo 0.48s So for a compression ratio that is still relatively close to gzip, it's much faster to extract, at least in that case. This part contains: - Makefile routine to support lzo compression - Fixes to the existing lzo compressor so that it can be used in compressed kernels - wrapper around the existing lzo1x_decompress, as it only extracts one block at a time, while we need to extract a whole file here - config dialog for kernel compression [akpm@linux-foundation.org: coding-style fixes] [akpm@linux-foundation.org: cleanup] Signed-off-by: Albin Tonnerre Tested-by: Wu Zhangjin Acked-by: "H. Peter Anvin" Cc: Ingo Molnar Cc: Thomas Gleixner Tested-by: Russell King Acked-by: Russell King Cc: Ralf Baechle Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/decompress_unlzo.c | 209 +++++++++++++++++++++++++++++++++++++++++++++ lib/lzo/lzo1x_decompress.c | 9 +- 2 files changed, 215 insertions(+), 3 deletions(-) create mode 100644 lib/decompress_unlzo.c (limited to 'lib') 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 @@ +/* + * LZO decompressor for the Linux kernel. Code borrowed from the lzo + * implementation by Markus Franz Xaver Johannes Oberhumer. + * + * Linux kernel adaptation: + * Copyright (C) 2009 + * Albin Tonnerre, Free Electrons + * + * Original code: + * Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer + * All Rights Reserved. + * + * lzop and the LZO library are free software; you can redistribute them + * and/or modify them under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of + * the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; see the file COPYING. + * If not, write to the Free Software Foundation, Inc., + * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * Markus F.X.J. Oberhumer + * + * http://www.oberhumer.com/opensource/lzop/ + */ + +#ifdef STATIC +#include "lzo/lzo1x_decompress.c" +#else +#include +#include +#endif + +#include +#include +#include + +#include +#include + +static const unsigned char lzop_magic[] = { + 0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a }; + +#define LZO_BLOCK_SIZE (256*1024l) +#define HEADER_HAS_FILTER 0x00000800L + +STATIC inline int INIT parse_header(u8 *input, u8 *skip) +{ + int l; + u8 *parse = input; + u8 level = 0; + u16 version; + + /* read magic: 9 first bits */ + for (l = 0; l < 9; l++) { + if (*parse++ != lzop_magic[l]) + return 0; + } + /* get version (2bytes), skip library version (2), + * 'need to be extracted' version (2) and + * method (1) */ + version = get_unaligned_be16(parse); + parse += 7; + if (version >= 0x0940) + level = *parse++; + if (get_unaligned_be32(parse) & HEADER_HAS_FILTER) + parse += 8; /* flags + filter info */ + else + parse += 4; /* flags */ + + /* skip mode and mtime_low */ + parse += 8; + if (version >= 0x0940) + parse += 4; /* skip mtime_high */ + + l = *parse++; + /* don't care about the file name, and skip checksum */ + parse += l + 4; + + *skip = parse - input; + return 1; +} + +STATIC inline int INIT unlzo(u8 *input, int in_len, + int (*fill) (void *, unsigned int), + int (*flush) (void *, unsigned int), + u8 *output, int *posp, + void (*error_fn) (char *x)) +{ + u8 skip = 0, r = 0; + u32 src_len, dst_len; + size_t tmp; + u8 *in_buf, *in_buf_save, *out_buf; + int obytes_processed = 0; + + set_error_fn(error_fn); + + if (output) { + out_buf = output; + } else if (!flush) { + error("NULL output pointer and no flush function provided"); + goto exit; + } else { + out_buf = malloc(LZO_BLOCK_SIZE); + if (!out_buf) { + error("Could not allocate output buffer"); + goto exit; + } + } + + if (input && fill) { + error("Both input pointer and fill function provided, don't know what to do"); + goto exit_1; + } else if (input) { + in_buf = input; + } else if (!fill || !posp) { + error("NULL input pointer and missing position pointer or fill function"); + goto exit_1; + } else { + in_buf = malloc(lzo1x_worst_compress(LZO_BLOCK_SIZE)); + if (!in_buf) { + error("Could not allocate input buffer"); + goto exit_1; + } + } + in_buf_save = in_buf; + + if (posp) + *posp = 0; + + if (fill) + fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); + + if (!parse_header(input, &skip)) { + error("invalid header"); + goto exit_2; + } + in_buf += skip; + + if (posp) + *posp = skip; + + for (;;) { + /* read uncompressed block size */ + dst_len = get_unaligned_be32(in_buf); + in_buf += 4; + + /* exit if last block */ + if (dst_len == 0) { + if (posp) + *posp += 4; + break; + } + + if (dst_len > LZO_BLOCK_SIZE) { + error("dest len longer than block size"); + goto exit_2; + } + + /* read compressed block size, and skip block checksum info */ + src_len = get_unaligned_be32(in_buf); + in_buf += 8; + + if (src_len <= 0 || src_len > dst_len) { + error("file corrupted"); + goto exit_2; + } + + /* decompress */ + tmp = dst_len; + r = lzo1x_decompress_safe((u8 *) in_buf, src_len, + out_buf, &tmp); + + if (r != LZO_E_OK || dst_len != tmp) { + error("Compressed data violation"); + goto exit_2; + } + + obytes_processed += dst_len; + if (flush) + flush(out_buf, dst_len); + if (output) + out_buf += dst_len; + if (posp) + *posp += src_len + 12; + if (fill) { + in_buf = in_buf_save; + fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE)); + } else + in_buf += src_len; + } + +exit_2: + if (!input) + free(in_buf); +exit_1: + if (!output) + free(out_buf); +exit: + return obytes_processed; +} + +#define decompress unlzo 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 @@ * Richard Purdie */ +#ifndef STATIC #include #include -#include -#include +#endif + #include +#include #include "lzodefs.h" #define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x)) @@ -244,9 +246,10 @@ lookbehind_overrun: *out_len = op - out; return LZO_E_LOOKBEHIND_OVERRUN; } - +#ifndef STATIC EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("LZO1X Decompressor"); +#endif -- cgit v1.2.3 From cacb246f8db2b9eba89d44a0f0dd4f6ed93bc113 Mon Sep 17 00:00:00 2001 From: Albin Tonnerre Date: Fri, 8 Jan 2010 14:42:46 -0800 Subject: Add LZO compression support for initramfs and old-style initrd Signed-off-by: Albin Tonnerre Tested-by: Wu Zhangjin Acked-by: "H. Peter Anvin" Cc: Ingo Molnar Cc: Thomas Gleixner Tested-by: Russell King Acked-by: Russell King Cc: Ralf Baechle Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig | 4 ++++ lib/Makefile | 1 + lib/decompress.c | 5 +++++ 3 files changed, 10 insertions(+) (limited to 'lib') 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 config DECOMPRESS_LZMA tristate +config DECOMPRESS_LZO + select LZO_DECOMPRESS + tristate + # # Generic allocator support is selected if needed # diff --git a/lib/Makefile b/lib/Makefile index 347ad8db29d3..911b25aed1e7 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -69,6 +69,7 @@ obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o +lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o obj-$(CONFIG_TEXTSEARCH) += textsearch.o 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 @@ #include #include #include +#include #include #include @@ -22,6 +23,9 @@ #ifndef CONFIG_DECOMPRESS_LZMA # define unlzma NULL #endif +#ifndef CONFIG_DECOMPRESS_LZO +# define unlzo NULL +#endif static const struct compress_format { unsigned char magic[2]; @@ -32,6 +36,7 @@ static const struct compress_format { { {037, 0236}, "gzip", gunzip }, { {0x42, 0x5a}, "bzip2", bunzip2 }, { {0x5d, 0x00}, "lzma", unlzma }, + { {0x89, 0x4c}, "lzo", unlzo }, { {0, 0}, NULL, NULL } }; -- cgit v1.2.3 From 7ee3aebe31d2cb22c84e1c8f48182947b13a3607 Mon Sep 17 00:00:00 2001 From: Sascha Hauer Date: Fri, 8 Jan 2010 14:42:47 -0800 Subject: lib/rational.c needs module.h MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit lib/rational.c:62: warning: data definition has no type or storage class lib/rational.c:62: warning: type defaults to 'int' in declaration of 'EXPORT_SYMBOL' lib/rational.c:62: warning: parameter names (without types) in function declaration Signed-off-by: Sascha Hauer Signed-off-by: Uwe Kleine-König Acked-by: WANG Cong Cc: Oskar Schirmer Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rational.c | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') 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 @@ */ #include +#include /* * calculate best rational approximation for a given fraction -- cgit v1.2.3 From 3f4724027bfe38644146252f7aa979dea7f80720 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Uwe=20Kleine-K=C3=B6nig?= Date: Fri, 8 Jan 2010 14:43:02 -0800 Subject: vsnprintf: fix reference for compressed ipv6 addresses MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Uwe Kleine-König Reported-by: Josip Rodin Cc: Joe Perches Cc: David S. Miller Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index d4996cf46eb6..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, * IPv6 omits the colons (01020304...0f) * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006) * - 'I6c' for IPv6 addresses printed as specified by - * http://www.ietf.org/id/draft-kawamura-ipv6-text-representation-03.txt + * http://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-00 * - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form * "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx" * Options for %pU are: @@ -1188,7 +1188,7 @@ qualifier: * %pI6 print an IPv6 address with colons * %pi6 print an IPv6 address without colons * %pI6c print an IPv6 address as specified by - * http://www.ietf.org/id/draft-kawamura-ipv6-text-representation-03.txt + * http://tools.ietf.org/html/draft-ietf-6man-text-addr-representation-00 * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper * case. * %n is ignored -- cgit v1.2.3 From 2c761270d5520dd84ab0b4e47c24d99ff8503c38 Mon Sep 17 00:00:00 2001 From: Dave Chinner Date: Tue, 12 Jan 2010 17:39:16 +1100 Subject: lib: Introduce generic list_sort function There are two copies of list_sort() in the tree already, one in the DRM code, another in ubifs. Now XFS needs this as well. Create a generic list_sort() function from the ubifs version and convert existing users to it so we don't end up with yet another copy in the tree. Signed-off-by: Dave Chinner Acked-by: Dave Airlie Acked-by: Artem Bityutskiy Signed-off-by: Linus Torvalds --- lib/Makefile | 2 +- lib/list_sort.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+), 1 deletion(-) create mode 100644 lib/list_sort.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 911b25aed1e7..3b0b4a696db9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o + string_helpers.o gcd.o list_sort.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG 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 @@ +#include +#include +#include +#include +#include + +/** + * list_sort - sort a list. + * @priv: private data, passed to @cmp + * @head: the list to sort + * @cmp: the elements comparison function + * + * This function has been implemented by Mark J Roberts . It + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted + * in ascending order. + * + * The comparison function @cmp is supposed to return a negative value if @a is + * less than @b, and a positive value if @a is greater than @b. If @a and @b + * are equivalent, then it does not matter what this function returns. + */ +void list_sort(void *priv, struct list_head *head, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b)) +{ + struct list_head *p, *q, *e, *list, *tail, *oldhead; + int insize, nmerges, psize, qsize, i; + + if (list_empty(head)) + return; + + list = head->next; + list_del(head); + insize = 1; + for (;;) { + p = oldhead = list; + list = tail = NULL; + nmerges = 0; + + while (p) { + nmerges++; + q = p; + psize = 0; + for (i = 0; i < insize; i++) { + psize++; + q = q->next == oldhead ? NULL : q->next; + if (!q) + break; + } + + qsize = insize; + while (psize > 0 || (qsize > 0 && q)) { + if (!psize) { + e = q; + q = q->next; + qsize--; + if (q == oldhead) + q = NULL; + } else if (!qsize || !q) { + e = p; + p = p->next; + psize--; + if (p == oldhead) + p = NULL; + } else if (cmp(priv, p, q) <= 0) { + e = p; + p = p->next; + psize--; + if (p == oldhead) + p = NULL; + } else { + e = q; + q = q->next; + qsize--; + if (q == oldhead) + q = NULL; + } + if (tail) + tail->next = e; + else + list = e; + e->prev = tail; + tail = e; + } + p = q; + } + + tail->next = list; + list->prev = tail; + + if (nmerges <= 1) + break; + + insize *= 2; + } + + head->next = list; + head->prev = list->prev; + list->prev->next = head; + list->prev = head; +} + +EXPORT_SYMBOL(list_sort); -- cgit v1.2.3 From 6846ee5ca68d81e6baccf0d56221d7a00c1be18b Mon Sep 17 00:00:00 2001 From: Benjamin Herrenschmidt Date: Wed, 13 Jan 2010 16:19:34 +1100 Subject: zlib: Fix build of powerpc boot wrapper Commit ac4c2a3bbe5db5fc570b1d0ee1e474db7cb22585 broke the build of all powerpc boot wrappers. It attempts to add an include of autoconf.h but used the wrong path for it. It also adds -D__KERNEL__ to our boot wrapper, both things that we pretty much didn't do on purpose so far. We want our boot wrapper to remain independent enough of the kernel for various reasons, one of them being that you can "wrap" an existing kernel at distro install time which allows to ship one kernel image and a set of boot wrappers for different platforms, the wrappers don't have to be built out of the same kernel build tree. It's also incorrect to do what the patch does in our boot environment since we may not have a proper alignment exception handler which means we may not be able to fixup the few cases where an unaligned access will need SW emulation (depends on the core variant, could be when crossing page or segment boundaries for example). This patch fixes it by putting the old code back in and using the new "fancy" variant only when CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is set, which happens not to be set on powerpc since we don't include autoconf.h. It also reverts the changes to our boot wrapper Makefile. This means that x86 should, afaik, keep the optimisations since its boot wrapper does include autoconf.h and define __KERNEL__ (though I doubt they make that much different outside of slow embedded processors). Signed-off-by: Benjamin Herrenschmidt Signed-off-by: Linus Torvalds --- lib/zlib_inflate/inffast.c | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index 05e1559fa156..215447c55261 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c @@ -4,12 +4,25 @@ */ #include -#include -#include #include "inftrees.h" #include "inflate.h" #include "inffast.h" +/* Only do the unaligned "Faster" variant when + * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is set + * + * On powerpc, it won't be as we don't include autoconf.h + * automatically for the boot wrapper, which is intended as + * we run in an environment where we may not be able to deal + * with (even rare) alignment faults. In addition, we do not + * define __KERNEL__ for arch/powerpc/boot unlike x86 + */ + +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +#include +#include +#endif + #ifndef ASMINF /* Allow machine dependent optimization for post-increment or pre-increment. @@ -243,6 +256,7 @@ void inflate_fast(z_streamp strm, unsigned start) } } else { +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS unsigned short *sout; unsigned long loops; @@ -284,6 +298,20 @@ void inflate_fast(z_streamp strm, unsigned start) } if (len & 1) PUP(out) = PUP(from); +#else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ + from = out - dist; /* copy direct from output */ + do { /* minimum length is three */ + PUP(out) = PUP(from); + PUP(out) = PUP(from); + PUP(out) = PUP(from); + len -= 3; + } while (len > 2); + if (len) { + PUP(out) = PUP(from); + if (len > 1) + PUP(out) = PUP(from); + } +#endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ } } else if ((op & 64) == 0) { /* 2nd level distance code */ -- cgit v1.2.3 From d5f1fb53353edc38da326445267c1df0c9676df2 Mon Sep 17 00:00:00 2001 From: Li Zefan Date: Thu, 14 Jan 2010 10:53:55 +0800 Subject: lib: Introduce strnstr() It differs strstr() in that it limits the length to be searched in the first string. Signed-off-by: Li Zefan LKML-Reference: <4B4E8743.6030805@cn.fujitsu.com> Acked-by: Frederic Weisbecker Signed-off-by: Steven Rostedt --- lib/string.c | 27 ++++++++++++++++++++++++++- 1 file changed, 26 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/string.c b/lib/string.c index 9f75b4ec50b8..a1cdcfcc42d0 100644 --- a/lib/string.c +++ b/lib/string.c @@ -667,7 +667,7 @@ EXPORT_SYMBOL(memscan); */ char *strstr(const char *s1, const char *s2) { - int l1, l2; + size_t l1, l2; l2 = strlen(s2); if (!l2) @@ -684,6 +684,31 @@ char *strstr(const char *s1, const char *s2) EXPORT_SYMBOL(strstr); #endif +#ifndef __HAVE_ARCH_STRNSTR +/** + * strnstr - Find the first substring in a length-limited string + * @s1: The string to be searched + * @s2: The string to search for + * @len: the maximum number of characters to search + */ +char *strnstr(const char *s1, const char *s2, size_t len) +{ + size_t l1 = len, l2; + + l2 = strlen(s2); + if (!l2) + return (char *)s1; + while (l1 >= l2) { + l1--; + if (!memcmp(s1, s2, l2)) + return (char *)s1; + s1++; + } + return NULL; +} +EXPORT_SYMBOL(strnstr); +#endif + #ifndef __HAVE_ARCH_MEMCHR /** * memchr - Find a character in an area of memory. -- cgit v1.2.3