From b60e26a2f03d963f8c79ad7920d64abc4d38ecbc Mon Sep 17 00:00:00 2001 From: Randy Dunlap Date: Fri, 6 Nov 2009 15:33:45 -0800 Subject: kmemleak: fix kconfig for crc32 build error kmemleak uses crc32 functions so it needs to select CRC32. Fixes build error: kmemleak.c:(.text+0x7ce62): undefined reference to `crc32_le' Signed-off-by: Randy Dunlap Signed-off-by: Catalin Marinas --- lib/Kconfig.debug | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 30df5865ecb..732b9f6ab1e 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -352,6 +352,7 @@ config DEBUG_KMEMLEAK select DEBUG_FS if SYSFS select STACKTRACE if STACKTRACE_SUPPORT select KALLSYMS + select CRC32 help Say Y here if you want to enable the memory leak detector. The memory allocation/freeing is traced in a way -- cgit From c5df7f775148723de39274537a886e9502eef336 Mon Sep 17 00:00:00 2001 From: Albert Herranz Date: Sat, 12 Dec 2009 06:31:54 +0000 Subject: powerpc: allow ioremap within reserved memory regions Add a flag to let a platform ioremap memory regions marked as reserved. This flag will be used later by the Nintendo Wii support code to allow ioremapping the I/O region sitting between MEM1 and MEM2 and marked as reserved RAM in the patch "wii: use both mem1 and mem2 as ram". This will no longer be needed when proper discontig memory support for 32-bit PowerPC is added to the kernel. Signed-off-by: Albert Herranz Acked-by: Benjamin Herrenschmidt Signed-off-by: Grant Likely --- lib/lmb.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/lmb.c b/lib/lmb.c index 0343c05609f..9cee17142b2 100644 --- a/lib/lmb.c +++ b/lib/lmb.c @@ -263,7 +263,7 @@ long __init lmb_reserve(u64 base, u64 size) return lmb_add_region(_rgn, base, size); } -long __init lmb_overlaps_region(struct lmb_region *rgn, u64 base, u64 size) +long lmb_overlaps_region(struct lmb_region *rgn, u64 base, u64 size) { unsigned long i; @@ -493,6 +493,11 @@ int __init lmb_is_reserved(u64 addr) return 0; } +int lmb_is_region_reserved(u64 base, u64 size) +{ + return lmb_overlaps_region(&lmb.reserved, base, size); +} + /* * Given a , find which memory regions belong to this range. * Adjust the request and return a contiguous chunk. -- cgit From d4529862cae4de19fda8d4bbcbddc60f3e48a4cf Mon Sep 17 00:00:00 2001 From: Phillip Lougher Date: Mon, 14 Dec 2009 21:45:19 +0000 Subject: bzip2: Add missing checks for malloc returning NULL Signed-off-by: Phillip Lougher LKML-Reference: <4b26b1ef.ln20bM9Mn4gzB21L%phillip@lougher.demon.co.uk> Signed-off-by: H. Peter Anvin --- lib/decompress_bunzip2.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/decompress_bunzip2.c b/lib/decompress_bunzip2.c index 76074209f9a..a4e971dee10 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, /* Allocate bunzip_data. Most fields initialize to zero. */ bd = *bdp = malloc(i); + if (!bd) + return RETVAL_OUT_OF_MEMORY; memset(bd, 0, sizeof(struct bunzip_data)); /* Setup input buffer */ bd->inbuf = inbuf; @@ -664,6 +666,8 @@ static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int len, bd->dbufSize = 100000*(i-BZh0); bd->dbuf = large_malloc(bd->dbufSize * sizeof(int)); + if (!bd->dbuf) + return RETVAL_OUT_OF_MEMORY; return RETVAL_OK; } @@ -686,7 +690,7 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, if (!outbuf) { error("Could not allocate output bufer"); - return -1; + return RETVAL_OUT_OF_MEMORY; } if (buf) inbuf = buf; @@ -694,6 +698,7 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, inbuf = malloc(BZIP2_IOBUF_SIZE); if (!inbuf) { error("Could not allocate input bufer"); + i = RETVAL_OUT_OF_MEMORY; goto exit_0; } i = start_bunzip(&bd, inbuf, len, fill); @@ -720,11 +725,14 @@ STATIC int INIT bunzip2(unsigned char *buf, int len, } else if (i == RETVAL_UNEXPECTED_OUTPUT_EOF) { error("Compressed file ends unexpectedly"); } + if (!bd) + goto exit_1; if (bd->dbuf) large_free(bd->dbuf); if (pos) *pos = bd->inbufPos; free(bd); +exit_1: if (!buf) free(inbuf); exit_0: -- cgit From 8a79503aa83d0f889abc64a2fc0a020411837222 Mon Sep 17 00:00:00 2001 From: Uwe Kleine-König Date: Thu, 17 Dec 2009 15:27:12 -0800 Subject: lib/vsprintf.c: document more vsnprintf extensions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit These were added in 9ac6e44 (lib/vsprintf.c: add %pU to print UUID/GUIDs) c7dabef (vsprintf: use %pR, %pr instead of %pRt, %pRf) 8a27f7c (lib/vsprintf.c: Add "%pI6c" - print pointer as compressed ipv6 address) 4aa9960 (printk: add %I4, %I6, %i4, %i6 format specifiers) dd45c9c (printk: add %pM format specifier for MAC addresses) but only added comments to pointer() not vsnprintf() that is refered to by printk's comments. Signed-off-by: Uwe Kleine-König Cc: Harvey Harrison Cc: David S. Miller Cc: Joe Perches Cc: Jens Rosenboom Cc: David S. Miller Cc: Bjorn Helgaas Cc: Jesse Barnes Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 735343fc857..d4996cf46eb 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -1179,7 +1179,18 @@ qualifier: * %ps output the name of a text symbol without offset * %pF output the name of a function pointer with its offset * %pf output the name of a function pointer without its offset - * %pR output the address range in a struct resource + * %pR output the address range in a struct resource with decoded flags + * %pr output the address range in a struct resource with raw flags + * %pM output a 6-byte MAC address with colons + * %pm output a 6-byte MAC address without colons + * %pI4 print an IPv4 address without leading zeros + * %pi4 print an IPv4 address with leading zeros + * %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 + * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper + * case. * %n is ignored * * The return value is the number of characters which would -- cgit 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 d9b08e0f7f5..739974460c3 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 From a6cd13f3c98d1d16213e3b61054b9c209d93f877 Mon Sep 17 00:00:00 2001 From: Randy Dunlap Date: Mon, 21 Dec 2009 14:37:22 -0800 Subject: lib/string.c: fix kernel-doc warnings Fix kernel-doc warnings (@arg name) in string.c::skip_spaces(). Warning(lib/string.c:347): No description found for parameter 'str' Warning(lib/string.c:347): Excess function parameter 's' description in 'skip_spaces' Signed-off-by: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/string.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/string.c b/lib/string.c index afce96af3af..9f75b4ec50b 100644 --- a/lib/string.c +++ b/lib/string.c @@ -338,10 +338,10 @@ EXPORT_SYMBOL(strnchr); #endif /** - * skip_spaces - Removes leading whitespace from @s. - * @s: The string to be stripped. + * skip_spaces - Removes leading whitespace from @str. + * @str: The string to be stripped. * - * Returns a pointer to the first non-whitespace character in @s. + * Returns a pointer to the first non-whitespace character in @str. */ char *skip_spaces(const char *str) { -- cgit 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 739974460c3..cf906201aec 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 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 cf906201aec..7d2f0b33e5a 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 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 8550b0c05d0..05e1559fa15 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 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 00000000000..db521f45626 --- /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 5dc6b29c157..f2fd0985022 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 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 1cfe51628e1..97b136ff117 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 347ad8db29d..911b25aed1e 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 d2842f57167..a7606815541 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 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 b3c099b5478..3ed247b8066 100644 --- a/lib/rational.c +++ b/lib/rational.c @@ -7,6 +7,7 @@ */ #include +#include /* * calculate best rational approximation for a given fraction -- cgit From 3f4724027bfe38644146252f7aa979dea7f80720 Mon Sep 17 00:00:00 2001 From: Uwe Kleine-König 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 d4996cf46eb..3b8aeec4e32 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 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 911b25aed1e..3b0b4a696db 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 00000000000..19d11e0bb95 --- /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 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 05e1559fa15..215447c5526 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 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 9f75b4ec50b..a1cdcfcc42d 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 From aeb583d08172e038552bdefe0a79a9aa9e2ecd7c Mon Sep 17 00:00:00 2001 From: Thiago Farina Date: Mon, 18 Jan 2010 18:57:33 -0500 Subject: lib/dma-debug.c: mark file-local struct symbol static. warning: symbol 'filter_fops' was not declared. Should it be static? Signed-off-by: Thiago Farina Signed-off-by: Joerg Roedel --- lib/dma-debug.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 739974460c3..e03995851e6 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -587,7 +587,7 @@ out_unlock: return count; } -const struct file_operations filter_fops = { +static const struct file_operations filter_fops = { .read = filter_read, .write = filter_write, }; -- cgit From 859ddf09743a8cc680af33f7259ccd0fd36bfe9d Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Tue, 2 Feb 2010 13:43:58 -0800 Subject: idr: fix a critical misallocation bug Eric Paris located a bug in idr. With IDR_BITS of 6, it grows to three layers when id 4096 is first allocated. When that happens, idr wraps incorrectly and searches the idr array ignoring the high bits. The following test code from Eric demonstrates the bug nicely. #include #include #include static DEFINE_IDR(test_idr); int init_module(void) { int ret, forty95, forty96; void *addr; /* add 2 entries both with 4095 as the start address */ again1: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4095, 4095, &forty95); if (ret) { if (ret == -EAGAIN) goto again1; return ret; } if (forty95 != 4095) printk(KERN_ERR "hmmm, forty95=%d\n", forty95); again2: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4096, 4095, &forty96); if (ret) { if (ret == -EAGAIN) goto again2; return ret; } if (forty96 != 4096) printk(KERN_ERR "hmmm, forty96=%d\n", forty96); /* try to find the 2 entries, noticing that 4096 broke */ addr = idr_find(&test_idr, forty95); if ((int)addr != forty95) printk(KERN_ERR "hmmm, after find forty95=%d addr=%d\n", forty95, (int)addr); addr = idr_find(&test_idr, forty96); if ((int)addr != forty96) printk(KERN_ERR "hmmm, after find forty96=%d addr=%d\n", forty96, (int)addr); /* really weird, the entry which should be at 4096 is actually at 0!! */ addr = idr_find(&test_idr, 0); if ((int)addr) printk(KERN_ERR "found an entry at id=0 for addr=%d\n", (int)addr); idr_remove(&test_idr, forty95); idr_remove(&test_idr, forty96); return 0; } void cleanup_module(void) { } MODULE_AUTHOR("Eric Paris "); MODULE_DESCRIPTION("Simple idr test"); MODULE_LICENSE("GPL"); This happens because when sub_alloc() back tracks it doesn't always do it step-by-step while the over-the-limit detection assumes step-by-step backtracking. The logic in sub_alloc() looks like the following. restart: clear pa[top level + 1] for end cond detection l = top level while (true) { search for empty slot at this level if (not found) { push id to the next possible value l++ A: if (pa[l] is clear) failed, return asking caller to grow the tree if (going up 1 level gives more slots to search) continue the while loop above with the incremented l else C: goto restart } adjust id accordingly to the found slot if (l == 0) return found id; create lower level if not there yet record pa[l] and l-- } Test A is the fail exit condition but this assumes that failure is propagated upwared one level at a time but the B optimization path breaks the assumption and restarts the whole thing with a start value which is above the possible limit with the current layers. sub_alloc() assumes the start id value is inside the limit when called and test A is the only exit condition check, so it ends up searching for empty slot while ignoring high set bit. So, for 4095->4096 test, level0 search fails but pa[1] contains a valid pointer. However, going up 1 level wouldn't give any more empty slot so it takes C and when the whole thing restarts nobody notices the high bit set beyond the top level. This patch fixes the bug by changing the fail exit condition check to full id limit check. Based-on-patch-from: Eric Paris Reported-by: Eric Paris Signed-off-by: Tejun Heo Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1cac726c44b..ba7d37cf784 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,8 +140,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = idp->layers; - pa[l--] = NULL; + l = p->layer; while (1) { /* * We run around this while until we reach the leaf node... @@ -155,8 +154,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* if already at the top layer, we need to grow */ - if (!(p = pa[l])) { + /* did id go over the limit? */ + if (id >= (1 << (idp->layers * IDR_BITS))) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit From 6f14a668f1a8b715a6e855f4e32705e54a6e86a1 Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Thu, 4 Feb 2010 17:57:37 +0900 Subject: idr: revert misallocation bug fix Commit 859ddf09743a8cc680af33f7259ccd0fd36bfe9d tried to fix misallocation bug but broke full bit marking by not clearing pa[idp->layers] and also is causing X failures due to lookup failure in drm code. The cause of the latter hasn't been found yet. Revert the fix for now. Signed-off-by: Tejun Heo Signed-off-by: Linus Torvalds --- lib/idr.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index ba7d37cf784..1cac726c44b 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,7 +140,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = p->layer; + l = idp->layers; + pa[l--] = NULL; while (1) { /* * We run around this while until we reach the leaf node... @@ -154,8 +155,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* did id go over the limit? */ - if (id >= (1 << (idp->layers * IDR_BITS))) { + /* if already at the top layer, we need to grow */ + if (!(p = pa[l])) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit From d2e7276b6b5e4bc2148891a056d5862c5314342d Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Mon, 22 Feb 2010 12:44:19 -0800 Subject: idr: fix a critical misallocation bug, take#2 This is retry of reverted 859ddf09743a8cc680af33f7259ccd0fd36bfe9d ("idr: fix a critical misallocation bug") which contained two bugs. * pa[idp->layers] should be cleared even if it's not used by sub_alloc() because it's used by mark idr_mark_full(). * The original condition check also assigned pa[l] to p which the new code didn't do thus leaving p pointing at the wrong layer. Both problems have been fixed and the idr code has received good amount testing using userland testing setup where simple bitmap allocator is run parallel to verify the result of idr allocation. The bug this patch fixes is caused by sub_alloc() optimization path bypassing out-of-room condition check and restarting allocation loop with starting value higher than maximum allowed value. For detailed description, please read commit message of 859ddf09. Signed-off-by: Tejun Heo Based-on-patch-from: Eric Paris Reported-by: Eric Paris Tested-by: Stefan Lippers-Hollmann Tested-by: Serge Hallyn Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1cac726c44b..0dc782216d4 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -156,10 +156,12 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; /* if already at the top layer, we need to grow */ - if (!(p = pa[l])) { + if (id >= 1 << (idp->layers * IDR_BITS)) { *starting_id = id; return IDR_NEED_TO_GROW; } + p = pa[l]; + BUG_ON(!p); /* If we need to go up one layer, continue the * loop; otherwise, restart from the top. -- cgit