From 80fc9f532d8c05d4cb12d55660624ce53a378349 Mon Sep 17 00:00:00 2001 From: Dmitry Torokhov Date: Wed, 11 Oct 2006 01:43:58 -0400 Subject: Input: add missing exports to fix modular build Signed-off-by: Dmitry Torokhov --- lib/kobject.c | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/kobject.c b/lib/kobject.c index 1699eb9..7dd5c0e 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -119,6 +119,7 @@ char *kobject_get_path(struct kobject *kobj, gfp_t gfp_mask) return path; } +EXPORT_SYMBOL_GPL(kobject_get_path); /** * kobject_init - initialize object. -- cgit v1.1 From 4dfbb9d8c6cbfc32faa5c71145bd2a43e1f8237c Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Wed, 11 Oct 2006 01:45:14 -0400 Subject: Lockdep: add lockdep_set_class_and_subclass() and lockdep_set_subclass() This annotation makes it possible to assign a subclass on lock init. This annotation is meant to reduce the _nested() annotations by assigning a default subclass. One could do without this annotation and rely on lockdep_set_class() exclusively, but that would require a manual stack of struct lock_class_key objects. Signed-off-by: Peter Zijlstra Signed-off-by: Dmitry Torokhov --- lib/rwsem-spinlock.c | 2 +- lib/rwsem.c | 2 +- lib/spinlock_debug.c | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/rwsem-spinlock.c b/lib/rwsem-spinlock.c index db4fed7..c4cfd6c 100644 --- a/lib/rwsem-spinlock.c +++ b/lib/rwsem-spinlock.c @@ -28,7 +28,7 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name, * Make sure we are not reinitializing a held semaphore: */ debug_check_no_locks_freed((void *)sem, sizeof(*sem)); - lockdep_init_map(&sem->dep_map, name, key); + lockdep_init_map(&sem->dep_map, name, key, 0); #endif sem->activity = 0; spin_lock_init(&sem->wait_lock); diff --git a/lib/rwsem.c b/lib/rwsem.c index 901d0e7..cdb4e3d 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -19,7 +19,7 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name, * Make sure we are not reinitializing a held semaphore: */ debug_check_no_locks_freed((void *)sem, sizeof(*sem)); - lockdep_init_map(&sem->dep_map, name, key); + lockdep_init_map(&sem->dep_map, name, key, 0); #endif sem->count = RWSEM_UNLOCKED_VALUE; spin_lock_init(&sem->wait_lock); diff --git a/lib/spinlock_debug.c b/lib/spinlock_debug.c index dafaf1d..b6c4f89 100644 --- a/lib/spinlock_debug.c +++ b/lib/spinlock_debug.c @@ -20,7 +20,7 @@ void __spin_lock_init(spinlock_t *lock, const char *name, * Make sure we are not reinitializing a held lock: */ debug_check_no_locks_freed((void *)lock, sizeof(*lock)); - lockdep_init_map(&lock->dep_map, name, key); + lockdep_init_map(&lock->dep_map, name, key, 0); #endif lock->raw_lock = (raw_spinlock_t)__RAW_SPIN_LOCK_UNLOCKED; lock->magic = SPINLOCK_MAGIC; @@ -38,7 +38,7 @@ void __rwlock_init(rwlock_t *lock, const char *name, * Make sure we are not reinitializing a held lock: */ debug_check_no_locks_freed((void *)lock, sizeof(*lock)); - lockdep_init_map(&lock->dep_map, name, key); + lockdep_init_map(&lock->dep_map, name, key, 0); #endif lock->raw_lock = (raw_rwlock_t) __RAW_RW_LOCK_UNLOCKED; lock->magic = RWLOCK_MAGIC; -- cgit v1.1 From aaa248f6c9c81b2683db7dbb0689cd5ed1c86d88 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Tue, 17 Oct 2006 00:09:42 -0700 Subject: [PATCH] rename net_random to random32 Make net_random() more widely available by calling it random32 akpm: hopefully this will permit the removal of carta_random32. That needs confirmation from Stephane - this code looks somewhat more computationally expensive, and has a different (ie: callee-stateful) interface. [akpm@osdl.org: lots of build fixes, cleanups] Signed-off-by: Stephen Hemminger Signed-off-by: David S. Miller Cc: Stephane Eranian Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Makefile | 2 +- lib/random32.c | 142 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 143 insertions(+), 1 deletion(-) create mode 100644 lib/random32.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 59070db..4b8052f 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -12,7 +12,7 @@ lib-$(CONFIG_SMP) += cpumask.o lib-y += kobject.o kref.o kobject_uevent.o klist.o -obj-y += sort.o parser.o halfmd4.o iomap_copy.o debug_locks.o +obj-y += sort.o parser.o halfmd4.o iomap_copy.o debug_locks.o random32.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/random32.c b/lib/random32.c new file mode 100644 index 0000000..4a15ce5 --- /dev/null +++ b/lib/random32.c @@ -0,0 +1,142 @@ +/* + This is a maximally equidistributed combined Tausworthe generator + based on code from GNU Scientific Library 1.5 (30 Jun 2004) + + x_n = (s1_n ^ s2_n ^ s3_n) + + s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19)) + s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25)) + s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11)) + + The period of this generator is about 2^88. + + From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe + Generators", Mathematics of Computation, 65, 213 (1996), 203--213. + + This is available on the net from L'Ecuyer's home page, + + http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps + ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps + + There is an erratum in the paper "Tables of Maximally + Equidistributed Combined LFSR Generators", Mathematics of + Computation, 68, 225 (1999), 261--269: + http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps + + ... the k_j most significant bits of z_j must be non- + zero, for each j. (Note: this restriction also applies to the + computer code given in [4], but was mistakenly not mentioned in + that paper.) + + This affects the seeding procedure by imposing the requirement + s1 > 1, s2 > 7, s3 > 15. + +*/ + +#include +#include +#include +#include + +struct rnd_state { + u32 s1, s2, s3; +}; + +static DEFINE_PER_CPU(struct rnd_state, net_rand_state); + +static u32 __random32(struct rnd_state *state) +{ +#define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b) + + state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); + state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); + state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); + + return (state->s1 ^ state->s2 ^ state->s3); +} + +static void __set_random32(struct rnd_state *state, unsigned long s) +{ + if (s == 0) + s = 1; /* default seed is 1 */ + +#define LCG(n) (69069 * n) + state->s1 = LCG(s); + state->s2 = LCG(state->s1); + state->s3 = LCG(state->s2); + + /* "warm it up" */ + __random32(state); + __random32(state); + __random32(state); + __random32(state); + __random32(state); + __random32(state); +} + +/** + * random32 - pseudo random number generator + * + * A 32 bit pseudo-random number is generated using a fast + * algorithm suitable for simulation. This algorithm is NOT + * considered safe for cryptographic use. + */ +u32 random32(void) +{ + unsigned long r; + struct rnd_state *state = &get_cpu_var(net_rand_state); + r = __random32(state); + put_cpu_var(state); + return r; +} +EXPORT_SYMBOL(random32); + +/** + * srandom32 - add entropy to pseudo random number generator + * @seed: seed value + * + * Add some additional seeding to the random32() pool. + * Note: this pool is per cpu so it only affects current CPU. + */ +void srandom32(u32 entropy) +{ + struct rnd_state *state = &get_cpu_var(net_rand_state); + __set_random32(state, state->s1 ^ entropy); + put_cpu_var(state); +} +EXPORT_SYMBOL(srandom32); + +/* + * Generate some initially weak seeding values to allow + * to start the random32() engine. + */ +static int __init random32_init(void) +{ + int i; + + for_each_possible_cpu(i) { + struct rnd_state *state = &per_cpu(net_rand_state,i); + __set_random32(state, i + jiffies); + } + return 0; +} +core_initcall(random32_init); + +/* + * Generate better values after random number generator + * is fully initalized. + */ +static int __init random32_reseed(void) +{ + int i; + unsigned long seed; + + for_each_possible_cpu(i) { + struct rnd_state *state = &per_cpu(net_rand_state,i); + + get_random_bytes(&seed, sizeof(seed)); + __set_random32(state, seed); + } + return 0; +} +late_initcall(random32_reseed); -- cgit v1.1 From 5c496374a72320279ddb86291ef709e090a5d531 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Tue, 17 Oct 2006 00:09:44 -0700 Subject: [PATCH] remove carta_random32 This library function should be in obj-y and not in lib-y. But when we do that it clashes unpleasantly with the assembly-language implementation in the ia64 architecture. Instead of trying to fix it all up, just remove the generic carta_random32 in the expectation that the recently-made-generic random32() will suffice. If/when perfmon is migrated to random32, ia64's private carta_random32 implementation can also be removed. Cc: Stephane Eranian Cc: "Luck, Tony" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Makefile | 2 +- lib/carta_random32.c | 41 ----------------------------------------- 2 files changed, 1 insertion(+), 42 deletions(-) delete mode 100644 lib/carta_random32.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 4b8052f..cf98fab 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -5,7 +5,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \ idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \ - sha1.o irq_regs.o carta_random32.o + sha1.o irq_regs.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o diff --git a/lib/carta_random32.c b/lib/carta_random32.c deleted file mode 100644 index ca82df7..0000000 --- a/lib/carta_random32.c +++ /dev/null @@ -1,41 +0,0 @@ -/* - * Copyright (c) 2002-2006 Hewlett-Packard Development Company, L.P. - * Contributed by David Mosberger-Tang - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of version 2 of the GNU General Public - * License as published by the Free Software Foundation. - * - * 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; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA - * 02111-1307 USA - */ -#include -#include - -/* - * Fast, simple, yet decent quality random number generator based on - * a paper by David G. Carta ("Two Fast Implementations of the - * `Minimal Standard' Random Number Generator," Communications of the - * ACM, January, 1990). - */ -u64 carta_random32 (u64 seed) -{ -# define A 16807 -# define M ((u32) 1 << 31) - u64 s, prod = A * seed, p, q; - - p = (prod >> 31) & (M - 1); - q = (prod >> 0) & (M - 1); - s = p + q; - if (s >= M) - s -= M - 1; - return s; -} -EXPORT_SYMBOL_GPL(carta_random32); -- cgit v1.1 From 6220ec7844fda2686496013a66b5b9169976b991 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Thu, 19 Oct 2006 23:29:05 -0700 Subject: [PATCH] highest_possible_node_id() linkage fix Qooting Adrian: - net/sunrpc/svc.c uses highest_possible_node_id() - include/linux/nodemask.h says highest_possible_node_id() is out-of-line #if MAX_NUMNODES > 1 - the out-of-line highest_possible_node_id() is in lib/cpumask.c - lib/Makefile: lib-$(CONFIG_SMP) += cpumask.o CONFIG_ARCH_DISCONTIGMEM_ENABLE=y, CONFIG_SMP=n, CONFIG_SUNRPC=y -> highest_possible_node_id() is used in net/sunrpc/svc.c CONFIG_NODES_SHIFT defined and > 0 -> include/linux/numa.h: MAX_NUMNODES > 1 -> compile error The bug is not present on architectures where ARCH_DISCONTIGMEM_ENABLE depends on NUMA (but m32r isn't the only affected architecture). So move the function into page_alloc.c Cc: Adrian Bunk Cc: Paul Jackson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/cpumask.c | 16 ---------------- 1 file changed, 16 deletions(-) (limited to 'lib') diff --git a/lib/cpumask.c b/lib/cpumask.c index 7a2a73f..3a67dc5 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -43,19 +43,3 @@ int __any_online_cpu(const cpumask_t *mask) return cpu; } EXPORT_SYMBOL(__any_online_cpu); - -#if MAX_NUMNODES > 1 -/* - * Find the highest possible node id. - */ -int highest_possible_node_id(void) -{ - unsigned int node; - unsigned int highest = 0; - - for_each_node_mask(node, node_possible_map) - highest = node; - return highest; -} -EXPORT_SYMBOL(highest_possible_node_id); -#endif -- cgit v1.1 From 75e31aaaf43b53517fd2b36cedc08bd4e4af14d5 Mon Sep 17 00:00:00 2001 From: Kevin Hilman Date: Wed, 25 Oct 2006 23:07:50 +0100 Subject: [ARM] 3909/1: Disable UWIND_INFO for ARM (again) According to Daniel Jacobowitz, UNWIND_INFO is not useful on ARM, and in fact doesn't even compile. This patch disables the option for ARM. Signed-off-by: Kevin Hilman Signed-off-by: Russell King --- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 77491e3..d367910 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -341,7 +341,7 @@ config FRAME_POINTER config UNWIND_INFO bool "Compile the kernel with frame unwind information" - depends on !IA64 && !PARISC + depends on !IA64 && !PARISC && !ARM depends on !MODULES || !(MIPS || PPC || SUPERH || V850) help If you say Y here the resulting kernel image will be slightly larger -- cgit v1.1 From 6e6d9fa6f95e382bb2d5725dda18b9e811418e79 Mon Sep 17 00:00:00 2001 From: Michael Holzheu Date: Sat, 28 Oct 2006 10:38:47 -0700 Subject: [PATCH] strstrip remove last blank fix strstrip() does not remove the last blank from strings which only consist of blanks. Example: char string[] = " "; strstrip(string); results in " ", but should produce an empty string! The following patch solves this problem: Acked-by: Martin Schwidefsky Signed-off-by: Michael Holzheu Acked-by: Pekka Enberg Acked-by Joern Engel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/string.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/string.c b/lib/string.c index 6307726..a485d75 100644 --- a/lib/string.c +++ b/lib/string.c @@ -320,7 +320,7 @@ char *strstrip(char *s) return s; end = s + size - 1; - while (end != s && isspace(*end)) + while (end >= s && isspace(*end)) end--; *(end + 1) = '\0'; -- cgit v1.1 From 03a67a46af8647b2c7825107045ecae641e103d3 Mon Sep 17 00:00:00 2001 From: Jan Engelhardt Date: Thu, 30 Nov 2006 05:32:19 +0100 Subject: Fix typos in doc and comments Changes persistant -> persistent. www.dictionary.com does not know persistant (with an A), but should it be one of those things you can spell in more than one correct way, let me know. Signed-off-by: Jan Engelhardt Signed-off-by: Adrian Bunk --- lib/textsearch.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/textsearch.c b/lib/textsearch.c index 2cb4a43..98bcadc 100644 --- a/lib/textsearch.c +++ b/lib/textsearch.c @@ -40,7 +40,7 @@ * configuration according to the specified parameters. * (3) User starts the search(es) by calling _find() or _next() to * fetch subsequent occurrences. A state variable is provided - * to the algorihtm to store persistant variables. + * to the algorihtm to store persistent variables. * (4) Core eventually resets the search offset and forwards the find() * request to the algorithm. * (5) Algorithm calls get_next_block() provided by the user continously -- cgit v1.1 From 8a82472f86bf693b8e91ed56c9ca4f62fbbdcfa3 Mon Sep 17 00:00:00 2001 From: Cornelia Huck Date: Mon, 20 Nov 2006 17:07:51 +0100 Subject: driver core: Introduce device_move(): move a device to a new parent. Provide a function device_move() to move a device to a new parent device. Add auxilliary functions kobject_move() and sysfs_move_dir(). kobject_move() generates a new uevent of type KOBJ_MOVE, containing the previous path (DEVPATH_OLD) in addition to the usual values. For this, a new interface kobject_uevent_env() is created that allows to add further environmental data to the uevent at the kobject layer. Signed-off-by: Cornelia Huck Acked-by: Kay Sievers Signed-off-by: Greg Kroah-Hartman --- lib/kobject.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++ lib/kobject_uevent.c | 28 ++++++++++++++++++++++++---- 2 files changed, 74 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/kobject.c b/lib/kobject.c index 7dd5c0e..744a4b1 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -311,6 +311,56 @@ int kobject_rename(struct kobject * kobj, const char *new_name) } /** + * kobject_move - move object to another parent + * @kobj: object in question. + * @new_parent: object's new parent + */ + +int kobject_move(struct kobject *kobj, struct kobject *new_parent) +{ + int error; + struct kobject *old_parent; + const char *devpath = NULL; + char *devpath_string = NULL; + char *envp[2]; + + kobj = kobject_get(kobj); + if (!kobj) + return -EINVAL; + new_parent = kobject_get(new_parent); + if (!new_parent) { + error = -EINVAL; + goto out; + } + /* old object path */ + devpath = kobject_get_path(kobj, GFP_KERNEL); + if (!devpath) { + error = -ENOMEM; + goto out; + } + devpath_string = kmalloc(strlen(devpath) + 15, GFP_KERNEL); + if (!devpath_string) { + error = -ENOMEM; + goto out; + } + sprintf(devpath_string, "DEVPATH_OLD=%s", devpath); + envp[0] = devpath_string; + envp[1] = NULL; + error = sysfs_move_dir(kobj, new_parent); + if (error) + goto out; + old_parent = kobj->parent; + kobj->parent = new_parent; + kobject_put(old_parent); + kobject_uevent_env(kobj, KOBJ_MOVE, envp); +out: + kobject_put(kobj); + kfree(devpath_string); + kfree(devpath); + return error; +} + +/** * kobject_del - unlink kobject from hierarchy. * @kobj: object. */ diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 7f20e7b..a192276 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -50,18 +50,22 @@ static char *action_to_string(enum kobject_action action) return "offline"; case KOBJ_ONLINE: return "online"; + case KOBJ_MOVE: + return "move"; default: return NULL; } } /** - * kobject_uevent - notify userspace by ending an uevent + * kobject_uevent_env - send an uevent with environmental data * - * @action: action that is happening (usually KOBJ_ADD and KOBJ_REMOVE) + * @action: action that is happening (usually KOBJ_MOVE) * @kobj: struct kobject that the action is happening to + * @envp_ext: pointer to environmental data */ -void kobject_uevent(struct kobject *kobj, enum kobject_action action) +void kobject_uevent_env(struct kobject *kobj, enum kobject_action action, + char *envp_ext[]) { char **envp; char *buffer; @@ -76,6 +80,7 @@ void kobject_uevent(struct kobject *kobj, enum kobject_action action) char *seq_buff; int i = 0; int retval; + int j; pr_debug("%s\n", __FUNCTION__); @@ -134,7 +139,8 @@ void kobject_uevent(struct kobject *kobj, enum kobject_action action) scratch += sprintf (scratch, "DEVPATH=%s", devpath) + 1; envp [i++] = scratch; scratch += sprintf(scratch, "SUBSYSTEM=%s", subsystem) + 1; - + for (j = 0; envp_ext && envp_ext[j]; j++) + envp[i++] = envp_ext[j]; /* just reserve the space, overwrite it after kset call has returned */ envp[i++] = seq_buff = scratch; scratch += strlen("SEQNUM=18446744073709551616") + 1; @@ -200,6 +206,20 @@ exit: kfree(envp); return; } + +EXPORT_SYMBOL_GPL(kobject_uevent_env); + +/** + * kobject_uevent - notify userspace by ending an uevent + * + * @action: action that is happening (usually KOBJ_ADD and KOBJ_REMOVE) + * @kobj: struct kobject that the action is happening to + */ +void kobject_uevent(struct kobject *kobj, enum kobject_action action) +{ + kobject_uevent_env(kobj, action, NULL); +} + EXPORT_SYMBOL_GPL(kobject_uevent); /** -- cgit v1.1 From 34ba8a5cd0b0d57f7775023e6e3fec473a7291cc Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 11 Nov 2006 17:24:46 +1100 Subject: [PATCH] Arch provides generic iomap missing accessors Allow architectures to provide their own implementation of the big endian MMIO accessors and "repeat" MMIO accessors for use by the generic iomap. Signed-off-by: Linus Torvalds More-or-less-tested-by: Benjamin Herrenschmidt Signed-off-by: Paul Mackerras --- lib/iomap.c | 32 ++++++++++++++++++++++++++++---- 1 file changed, 28 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/iomap.c b/lib/iomap.c index 55689c5..d6ccdd8 100644 --- a/lib/iomap.c +++ b/lib/iomap.c @@ -50,6 +50,16 @@ } \ } while (0) +#ifndef pio_read16be +#define pio_read16be(port) swab16(inw(port)) +#define pio_read32be(port) swab32(inl(port)) +#endif + +#ifndef mmio_read16be +#define mmio_read16be(addr) be16_to_cpu(__raw_readw(addr)) +#define mmio_read32be(addr) be32_to_cpu(__raw_readl(addr)) +#endif + unsigned int fastcall ioread8(void __iomem *addr) { IO_COND(addr, return inb(port), return readb(addr)); @@ -60,7 +70,7 @@ unsigned int fastcall ioread16(void __iomem *addr) } unsigned int fastcall ioread16be(void __iomem *addr) { - IO_COND(addr, return inw(port), return be16_to_cpu(__raw_readw(addr))); + IO_COND(addr, return pio_read16be(port), return mmio_read16be(addr)); } unsigned int fastcall ioread32(void __iomem *addr) { @@ -68,7 +78,7 @@ unsigned int fastcall ioread32(void __iomem *addr) } unsigned int fastcall ioread32be(void __iomem *addr) { - IO_COND(addr, return inl(port), return be32_to_cpu(__raw_readl(addr))); + IO_COND(addr, return pio_read32be(port), return mmio_read32be(addr)); } EXPORT_SYMBOL(ioread8); EXPORT_SYMBOL(ioread16); @@ -76,6 +86,16 @@ EXPORT_SYMBOL(ioread16be); EXPORT_SYMBOL(ioread32); EXPORT_SYMBOL(ioread32be); +#ifndef pio_write16be +#define pio_write16be(val,port) outw(swab16(val),port) +#define pio_write32be(val,port) outl(swab32(val),port) +#endif + +#ifndef mmio_write16be +#define mmio_write16be(val,port) __raw_writew(be16_to_cpu(val),port) +#define mmio_write32be(val,port) __raw_writel(be32_to_cpu(val),port) +#endif + void fastcall iowrite8(u8 val, void __iomem *addr) { IO_COND(addr, outb(val,port), writeb(val, addr)); @@ -86,7 +106,7 @@ void fastcall iowrite16(u16 val, void __iomem *addr) } void fastcall iowrite16be(u16 val, void __iomem *addr) { - IO_COND(addr, outw(val,port), __raw_writew(cpu_to_be16(val), addr)); + IO_COND(addr, pio_write16be(val,port), mmio_write16be(val, addr)); } void fastcall iowrite32(u32 val, void __iomem *addr) { @@ -94,7 +114,7 @@ void fastcall iowrite32(u32 val, void __iomem *addr) } void fastcall iowrite32be(u32 val, void __iomem *addr) { - IO_COND(addr, outl(val,port), __raw_writel(cpu_to_be32(val), addr)); + IO_COND(addr, pio_write32be(val,port), mmio_write32be(val, addr)); } EXPORT_SYMBOL(iowrite8); EXPORT_SYMBOL(iowrite16); @@ -108,6 +128,7 @@ EXPORT_SYMBOL(iowrite32be); * convert to CPU byte order. We write in "IO byte * order" (we also don't have IO barriers). */ +#ifndef mmio_insb static inline void mmio_insb(void __iomem *addr, u8 *dst, int count) { while (--count >= 0) { @@ -132,7 +153,9 @@ static inline void mmio_insl(void __iomem *addr, u32 *dst, int count) dst++; } } +#endif +#ifndef mmio_outsb static inline void mmio_outsb(void __iomem *addr, const u8 *src, int count) { while (--count >= 0) { @@ -154,6 +177,7 @@ static inline void mmio_outsl(void __iomem *addr, const u32 *src, int count) src++; } } +#endif void fastcall ioread8_rep(void __iomem *addr, void *dst, unsigned long count) { -- cgit v1.1 From f6a570333e554b48ad589e7137c77c57809eee81 Mon Sep 17 00:00:00 2001 From: Al Viro Date: Wed, 18 Oct 2006 01:47:25 -0400 Subject: [PATCH] severing module.h->sched.h Signed-off-by: Al Viro --- lib/random32.c | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/random32.c b/lib/random32.c index 4a15ce5..ec7f81d 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -36,6 +36,7 @@ #include #include #include +#include #include struct rnd_state { -- cgit v1.1 From bb81a09e55eaf7e5f798468ab971469b6f66a259 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Thu, 7 Dec 2006 02:14:01 +0100 Subject: [PATCH] x86: all cpu backtrace When a spinlock lockup occurs, arrange for the NMI code to emit an all-cpu backtrace, so we get to see which CPU is holding the lock, and where. Cc: Andi Kleen Cc: Ingo Molnar Cc: Badari Pulavarty Signed-off-by: Andrew Morton Signed-off-by: Andi Kleen --- lib/spinlock_debug.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'lib') diff --git a/lib/spinlock_debug.c b/lib/spinlock_debug.c index b6c4f89..479fd46 100644 --- a/lib/spinlock_debug.c +++ b/lib/spinlock_debug.c @@ -7,6 +7,7 @@ */ #include +#include #include #include #include @@ -117,6 +118,9 @@ static void __spin_lock_debug(spinlock_t *lock) raw_smp_processor_id(), current->comm, current->pid, lock); dump_stack(); +#ifdef CONFIG_SMP + trigger_all_cpu_backtrace(); +#endif } } } -- cgit v1.1 From e18b890bb0881bbab6f4f1a6cd20d9c60d66b003 Mon Sep 17 00:00:00 2001 From: Christoph Lameter Date: Wed, 6 Dec 2006 20:33:20 -0800 Subject: [PATCH] slab: remove kmem_cache_t Replace all uses of kmem_cache_t with struct kmem_cache. The patch was generated using the following script: #!/bin/sh # # Replace one string by another in all the kernel sources. # set -e for file in `find * -name "*.c" -o -name "*.h"|xargs grep -l $1`; do quilt add $file sed -e "1,\$s/$1/$2/g" $file >/tmp/$$ mv /tmp/$$ $file quilt refresh done The script was run like this sh replace kmem_cache_t "struct kmem_cache" Signed-off-by: Christoph Lameter Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 4 ++-- lib/radix-tree.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 16d2143..7185353 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -33,7 +33,7 @@ #include #include -static kmem_cache_t *idr_layer_cache; +static struct kmem_cache *idr_layer_cache; static struct idr_layer *alloc_layer(struct idr *idp) { @@ -445,7 +445,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id) } EXPORT_SYMBOL(idr_replace); -static void idr_cache_ctor(void * idr_layer, kmem_cache_t *idr_layer_cache, +static void idr_cache_ctor(void * idr_layer, struct kmem_cache *idr_layer_cache, unsigned long flags) { memset(idr_layer, 0, sizeof(struct idr_layer)); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index aa9bfd0..9eb2595 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -63,7 +63,7 @@ static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; /* * Radix tree node cache. */ -static kmem_cache_t *radix_tree_node_cachep; +static struct kmem_cache *radix_tree_node_cachep; /* * Per-cpu pool of preloaded nodes @@ -846,7 +846,7 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) EXPORT_SYMBOL(radix_tree_tagged); static void -radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) +radix_tree_node_ctor(void *node, struct kmem_cache *cachep, unsigned long flags) { memset(node, 0, sizeof(struct radix_tree_node)); } -- cgit v1.1 From 7cf9c2c76c1a17b32f2da85b50cd4fe468ed44b5 Mon Sep 17 00:00:00 2001 From: Nick Piggin Date: Wed, 6 Dec 2006 20:33:44 -0800 Subject: [PATCH] radix-tree: RCU lockless readside Make radix tree lookups safe to be performed without locks. Readers are protected against nodes being deleted by using RCU based freeing. Readers are protected against new node insertion by using memory barriers to ensure the node itself will be properly written before it is visible in the radix tree. Each radix tree node keeps a record of their height (above leaf nodes). This height does not change after insertion -- when the radix tree is extended, higher nodes are only inserted in the top. So a lookup can take the pointer to what is *now* the root node, and traverse down it even if the tree is concurrently extended and this node becomes a subtree of a new root. "Direct" pointers (tree height of 0, where root->rnode points directly to the data item) are handled by using the low bit of the pointer to signal whether rnode is a direct pointer or a pointer to a radix tree node. When a reader wants to traverse the next branch, they will take a copy of the pointer. This pointer will be either NULL (and the branch is empty) or non-NULL (and will point to a valid node). [akpm@osdl.org: cleanups] [Lee.Schermerhorn@hp.com: bugfixes, comments, simplifications] [clameter@sgi.com: build fix] Signed-off-by: Nick Piggin Cc: "Paul E. McKenney" Signed-off-by: Lee Schermerhorn Cc: Christoph Lameter Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/radix-tree.c | 327 ++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 227 insertions(+), 100 deletions(-) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 9eb2595..e2cefab 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -2,6 +2,7 @@ * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig * Copyright (C) 2005 SGI, Christoph Lameter + * Copyright (C) 2006 Nick Piggin * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as @@ -30,6 +31,7 @@ #include #include #include +#include #ifdef __KERNEL__ @@ -45,7 +47,9 @@ ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) struct radix_tree_node { + unsigned int height; /* Height from the bottom */ unsigned int count; + struct rcu_head rcu_head; void *slots[RADIX_TREE_MAP_SIZE]; unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; }; @@ -100,13 +104,21 @@ radix_tree_node_alloc(struct radix_tree_root *root) rtp->nr--; } } + BUG_ON(radix_tree_is_direct_ptr(ret)); return ret; } +static void radix_tree_node_rcu_free(struct rcu_head *head) +{ + struct radix_tree_node *node = + container_of(head, struct radix_tree_node, rcu_head); + kmem_cache_free(radix_tree_node_cachep, node); +} + static inline void radix_tree_node_free(struct radix_tree_node *node) { - kmem_cache_free(radix_tree_node_cachep, node); + call_rcu(&node->rcu_head, radix_tree_node_rcu_free); } /* @@ -222,11 +234,12 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) } do { + unsigned int newheight; if (!(node = radix_tree_node_alloc(root))) return -ENOMEM; /* Increase the height. */ - node->slots[0] = root->rnode; + node->slots[0] = radix_tree_direct_to_ptr(root->rnode); /* Propagate the aggregated tag info into the new root */ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { @@ -234,9 +247,11 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) tag_set(node, tag, 0); } + newheight = root->height+1; + node->height = newheight; node->count = 1; - root->rnode = node; - root->height++; + rcu_assign_pointer(root->rnode, node); + root->height = newheight; } while (height > root->height); out: return 0; @@ -258,6 +273,8 @@ int radix_tree_insert(struct radix_tree_root *root, int offset; int error; + BUG_ON(radix_tree_is_direct_ptr(item)); + /* Make sure the tree is high enough. */ if (index > radix_tree_maxindex(root->height)) { error = radix_tree_extend(root, index); @@ -275,11 +292,12 @@ int radix_tree_insert(struct radix_tree_root *root, /* Have to add a child node. */ if (!(slot = radix_tree_node_alloc(root))) return -ENOMEM; + slot->height = height; if (node) { - node->slots[offset] = slot; + rcu_assign_pointer(node->slots[offset], slot); node->count++; } else - root->rnode = slot; + rcu_assign_pointer(root->rnode, slot); } /* Go a level down */ @@ -295,11 +313,11 @@ int radix_tree_insert(struct radix_tree_root *root, if (node) { node->count++; - node->slots[offset] = item; + rcu_assign_pointer(node->slots[offset], item); BUG_ON(tag_get(node, 0, offset)); BUG_ON(tag_get(node, 1, offset)); } else { - root->rnode = item; + rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item)); BUG_ON(root_tag_get(root, 0)); BUG_ON(root_tag_get(root, 1)); } @@ -308,49 +326,54 @@ int radix_tree_insert(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_insert); -static inline void **__lookup_slot(struct radix_tree_root *root, - unsigned long index) +/** + * radix_tree_lookup_slot - lookup a slot in a radix tree + * @root: radix tree root + * @index: index key + * + * Returns: the slot corresponding to the position @index in the + * radix tree @root. This is useful for update-if-exists operations. + * + * This function cannot be called under rcu_read_lock, it must be + * excluded from writers, as must the returned slot for subsequent + * use by radix_tree_deref_slot() and radix_tree_replace slot. + * Caller must hold tree write locked across slot lookup and + * replace. + */ +void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) { unsigned int height, shift; - struct radix_tree_node **slot; - - height = root->height; + struct radix_tree_node *node, **slot; - if (index > radix_tree_maxindex(height)) + node = root->rnode; + if (node == NULL) return NULL; - if (height == 0 && root->rnode) + if (radix_tree_is_direct_ptr(node)) { + if (index > 0) + return NULL; return (void **)&root->rnode; + } + + height = node->height; + if (index > radix_tree_maxindex(height)) + return NULL; shift = (height-1) * RADIX_TREE_MAP_SHIFT; - slot = &root->rnode; - while (height > 0) { - if (*slot == NULL) + do { + slot = (struct radix_tree_node **) + (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); + node = *slot; + if (node == NULL) return NULL; - slot = (struct radix_tree_node **) - ((*slot)->slots + - ((index >> shift) & RADIX_TREE_MAP_MASK)); shift -= RADIX_TREE_MAP_SHIFT; height--; - } + } while (height > 0); return (void **)slot; } - -/** - * radix_tree_lookup_slot - lookup a slot in a radix tree - * @root: radix tree root - * @index: index key - * - * Lookup the slot corresponding to the position @index in the radix tree - * @root. This is useful for update-if-exists operations. - */ -void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) -{ - return __lookup_slot(root, index); -} EXPORT_SYMBOL(radix_tree_lookup_slot); /** @@ -359,13 +382,45 @@ EXPORT_SYMBOL(radix_tree_lookup_slot); * @index: index key * * Lookup the item at the position @index in the radix tree @root. + * + * This function can be called under rcu_read_lock, however the caller + * must manage lifetimes of leaf nodes (eg. RCU may also be used to free + * them safely). No RCU barriers are required to access or modify the + * returned item, however. */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { - void **slot; + unsigned int height, shift; + struct radix_tree_node *node, **slot; + + node = rcu_dereference(root->rnode); + if (node == NULL) + return NULL; + + if (radix_tree_is_direct_ptr(node)) { + if (index > 0) + return NULL; + return radix_tree_direct_to_ptr(node); + } + + height = node->height; + if (index > radix_tree_maxindex(height)) + return NULL; + + shift = (height-1) * RADIX_TREE_MAP_SHIFT; - slot = __lookup_slot(root, index); - return slot != NULL ? *slot : NULL; + do { + slot = (struct radix_tree_node **) + (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); + node = rcu_dereference(*slot); + if (node == NULL) + return NULL; + + shift -= RADIX_TREE_MAP_SHIFT; + height--; + } while (height > 0); + + return node; } EXPORT_SYMBOL(radix_tree_lookup); @@ -495,27 +550,30 @@ int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag) { unsigned int height, shift; - struct radix_tree_node *slot; + struct radix_tree_node *node; int saw_unset_tag = 0; - height = root->height; - if (index > radix_tree_maxindex(height)) - return 0; - /* check the root's tag bit */ if (!root_tag_get(root, tag)) return 0; - if (height == 0) - return 1; + node = rcu_dereference(root->rnode); + if (node == NULL) + return 0; + + if (radix_tree_is_direct_ptr(node)) + return (index == 0); + + height = node->height; + if (index > radix_tree_maxindex(height)) + return 0; shift = (height - 1) * RADIX_TREE_MAP_SHIFT; - slot = root->rnode; for ( ; ; ) { int offset; - if (slot == NULL) + if (node == NULL) return 0; offset = (index >> shift) & RADIX_TREE_MAP_MASK; @@ -524,15 +582,15 @@ int radix_tree_tag_get(struct radix_tree_root *root, * This is just a debug check. Later, we can bale as soon as * we see an unset tag. */ - if (!tag_get(slot, tag, offset)) + if (!tag_get(node, tag, offset)) saw_unset_tag = 1; if (height == 1) { - int ret = tag_get(slot, tag, offset); + int ret = tag_get(node, tag, offset); BUG_ON(ret && saw_unset_tag); return !!ret; } - slot = slot->slots[offset]; + node = rcu_dereference(node->slots[offset]); shift -= RADIX_TREE_MAP_SHIFT; height--; } @@ -541,47 +599,45 @@ EXPORT_SYMBOL(radix_tree_tag_get); #endif static unsigned int -__lookup(struct radix_tree_root *root, void **results, unsigned long index, +__lookup(struct radix_tree_node *slot, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index) { unsigned int nr_found = 0; unsigned int shift, height; - struct radix_tree_node *slot; unsigned long i; - height = root->height; - if (height == 0) { - if (root->rnode && index == 0) - results[nr_found++] = root->rnode; + height = slot->height; + if (height == 0) goto out; - } - shift = (height-1) * RADIX_TREE_MAP_SHIFT; - slot = root->rnode; for ( ; height > 1; height--) { - - for (i = (index >> shift) & RADIX_TREE_MAP_MASK ; - i < RADIX_TREE_MAP_SIZE; i++) { + i = (index >> shift) & RADIX_TREE_MAP_MASK; + for (;;) { if (slot->slots[i] != NULL) break; index &= ~((1UL << shift) - 1); index += 1UL << shift; if (index == 0) goto out; /* 32-bit wraparound */ + i++; + if (i == RADIX_TREE_MAP_SIZE) + goto out; } - if (i == RADIX_TREE_MAP_SIZE) - goto out; shift -= RADIX_TREE_MAP_SHIFT; - slot = slot->slots[i]; + slot = rcu_dereference(slot->slots[i]); + if (slot == NULL) + goto out; } /* Bottom level: grab some items */ for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { + struct radix_tree_node *node; index++; - if (slot->slots[i]) { - results[nr_found++] = slot->slots[i]; + node = slot->slots[i]; + if (node) { + results[nr_found++] = rcu_dereference(node); if (nr_found == max_items) goto out; } @@ -603,28 +659,51 @@ out: * *@results. * * The implementation is naive. + * + * Like radix_tree_lookup, radix_tree_gang_lookup may be called under + * rcu_read_lock. In this case, rather than the returned results being + * an atomic snapshot of the tree at a single point in time, the semantics + * of an RCU protected gang lookup are as though multiple radix_tree_lookups + * have been issued in individual locks, and results stored in 'results'. */ unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items) { - const unsigned long max_index = radix_tree_maxindex(root->height); + unsigned long max_index; + struct radix_tree_node *node; unsigned long cur_index = first_index; - unsigned int ret = 0; + unsigned int ret; + + node = rcu_dereference(root->rnode); + if (!node) + return 0; + if (radix_tree_is_direct_ptr(node)) { + if (first_index > 0) + return 0; + node = radix_tree_direct_to_ptr(node); + results[0] = rcu_dereference(node); + return 1; + } + + max_index = radix_tree_maxindex(node->height); + + ret = 0; while (ret < max_items) { unsigned int nr_found; unsigned long next_index; /* Index of next search */ if (cur_index > max_index) break; - nr_found = __lookup(root, results + ret, cur_index, + nr_found = __lookup(node, results + ret, cur_index, max_items - ret, &next_index); ret += nr_found; if (next_index == 0) break; cur_index = next_index; } + return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup); @@ -634,55 +713,64 @@ EXPORT_SYMBOL(radix_tree_gang_lookup); * open-coding the search. */ static unsigned int -__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, +__lookup_tag(struct radix_tree_node *slot, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index, unsigned int tag) { unsigned int nr_found = 0; - unsigned int shift; - unsigned int height = root->height; - struct radix_tree_node *slot; + unsigned int shift, height; - if (height == 0) { - if (root->rnode && index == 0) - results[nr_found++] = root->rnode; + height = slot->height; + if (height == 0) goto out; - } - - shift = (height - 1) * RADIX_TREE_MAP_SHIFT; - slot = root->rnode; + shift = (height-1) * RADIX_TREE_MAP_SHIFT; - do { - unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; + while (height > 0) { + unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ; - for ( ; i < RADIX_TREE_MAP_SIZE; i++) { - if (tag_get(slot, tag, i)) { - BUG_ON(slot->slots[i] == NULL); + for (;;) { + if (tag_get(slot, tag, i)) break; - } index &= ~((1UL << shift) - 1); index += 1UL << shift; if (index == 0) goto out; /* 32-bit wraparound */ + i++; + if (i == RADIX_TREE_MAP_SIZE) + goto out; } - if (i == RADIX_TREE_MAP_SIZE) - goto out; height--; if (height == 0) { /* Bottom level: grab some items */ unsigned long j = index & RADIX_TREE_MAP_MASK; for ( ; j < RADIX_TREE_MAP_SIZE; j++) { + struct radix_tree_node *node; index++; - if (tag_get(slot, tag, j)) { - BUG_ON(slot->slots[j] == NULL); - results[nr_found++] = slot->slots[j]; + if (!tag_get(slot, tag, j)) + continue; + node = slot->slots[j]; + /* + * Even though the tag was found set, we need to + * recheck that we have a non-NULL node, because + * if this lookup is lockless, it may have been + * subsequently deleted. + * + * Similar care must be taken in any place that + * lookup ->slots[x] without a lock (ie. can't + * rely on its value remaining the same). + */ + if (node) { + node = rcu_dereference(node); + results[nr_found++] = node; if (nr_found == max_items) goto out; } } } shift -= RADIX_TREE_MAP_SHIFT; - slot = slot->slots[i]; - } while (height > 0); + slot = rcu_dereference(slot->slots[i]); + if (slot == NULL) + break; + } out: *next_index = index; return nr_found; @@ -706,27 +794,44 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag) { - const unsigned long max_index = radix_tree_maxindex(root->height); + struct radix_tree_node *node; + unsigned long max_index; unsigned long cur_index = first_index; - unsigned int ret = 0; + unsigned int ret; /* check the root's tag bit */ if (!root_tag_get(root, tag)) return 0; + node = rcu_dereference(root->rnode); + if (!node) + return 0; + + if (radix_tree_is_direct_ptr(node)) { + if (first_index > 0) + return 0; + node = radix_tree_direct_to_ptr(node); + results[0] = rcu_dereference(node); + return 1; + } + + max_index = radix_tree_maxindex(node->height); + + ret = 0; while (ret < max_items) { unsigned int nr_found; unsigned long next_index; /* Index of next search */ if (cur_index > max_index) break; - nr_found = __lookup_tag(root, results + ret, cur_index, + nr_found = __lookup_tag(node, results + ret, cur_index, max_items - ret, &next_index, tag); ret += nr_found; if (next_index == 0) break; cur_index = next_index; } + return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup_tag); @@ -742,8 +847,19 @@ static inline void radix_tree_shrink(struct radix_tree_root *root) root->rnode->count == 1 && root->rnode->slots[0]) { struct radix_tree_node *to_free = root->rnode; + void *newptr; - root->rnode = to_free->slots[0]; + /* + * We don't need rcu_assign_pointer(), since we are simply + * moving the node from one part of the tree to another. If + * it was safe to dereference the old pointer to it + * (to_free->slots[0]), it will be safe to dereference the new + * one (root->rnode). + */ + newptr = to_free->slots[0]; + if (root->height == 1) + newptr = radix_tree_ptr_to_direct(newptr); + root->rnode = newptr; root->height--; /* must only free zeroed nodes into the slab */ tag_clear(to_free, 0, 0); @@ -767,6 +883,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) { struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; struct radix_tree_node *slot = NULL; + struct radix_tree_node *to_free; unsigned int height, shift; int tag; int offset; @@ -777,6 +894,7 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) slot = root->rnode; if (height == 0 && root->rnode) { + slot = radix_tree_direct_to_ptr(slot); root_tag_clear_all(root); root->rnode = NULL; goto out; @@ -809,10 +927,17 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) radix_tree_tag_clear(root, index, tag); } + to_free = NULL; /* Now free the nodes we do not need anymore */ while (pathp->node) { pathp->node->slots[pathp->offset] = NULL; pathp->node->count--; + /* + * Queue the node for deferred freeing after the + * last reference to it disappears (set NULL, above). + */ + if (to_free) + radix_tree_node_free(to_free); if (pathp->node->count) { if (pathp->node == root->rnode) @@ -821,13 +946,15 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) } /* Node with zero slots in use so free it */ - radix_tree_node_free(pathp->node); - + to_free = pathp->node; pathp--; + } root_tag_clear_all(root); root->height = 0; root->rnode = NULL; + if (to_free) + radix_tree_node_free(to_free); out: return slot; -- cgit v1.1 From d3b8b6e5f20031890e09a8eab72fd596d2e2227d Mon Sep 17 00:00:00 2001 From: Randy Dunlap Date: Wed, 6 Dec 2006 20:36:38 -0800 Subject: [PATCH] kconfig: PRINTK_TIME depends on PRINTK Make PRINTK_TIME depend on PRINTK. Only display/offer it if PRINTK is enabled. Signed-off-by: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 1 + 1 file changed, 1 insertion(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index d367910..b75fed7 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1,6 +1,7 @@ config PRINTK_TIME bool "Show timing information on printks" + depends on PRINTK help Selecting this option causes timing information to be included in printk output. This allows you to measure -- cgit v1.1 From 8f63fdbbd6de7d734c036948bf7c4b2bebe3ad99 Mon Sep 17 00:00:00 2001 From: Dave Jones Date: Wed, 6 Dec 2006 20:37:09 -0800 Subject: [PATCH] More list debugging context Print the other (hopefully) known good pointer when list_head debugging too, which may yield additional clues. Also fix for 80-columns to win akpm brownie points. Signed-off-by: Dave Jones Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_debug.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/list_debug.c b/lib/list_debug.c index 7ba9d82..4350ba9 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -21,13 +21,15 @@ void __list_add(struct list_head *new, struct list_head *next) { if (unlikely(next->prev != prev)) { - printk(KERN_ERR "list_add corruption. next->prev should be %p, but was %p\n", - prev, next->prev); + printk(KERN_ERR "list_add corruption. next->prev should be " + "prev (%p), but was %p. (next=%p).\n", + prev, next->prev, next); BUG(); } if (unlikely(prev->next != next)) { - printk(KERN_ERR "list_add corruption. prev->next should be %p, but was %p\n", - next, prev->next); + printk(KERN_ERR "list_add corruption. prev->next should be " + "next (%p), but was %p. (prev=%p).\n", + next, prev->next, prev); BUG(); } next->prev = new; -- cgit v1.1 From 22f2e280179946b8be1e2205b8654f2cb4abbf64 Mon Sep 17 00:00:00 2001 From: Derek Fults Date: Wed, 6 Dec 2006 20:37:11 -0800 Subject: [PATCH] get_options to allow a hypenated range for isolcpus This allows a hyphenated range of positive numbers in the string passed to command line helper function, get_options. Currently the command line option "isolcpus=" takes as its argument a list of cpus. Format: ,..., Valid values of include all cpus, 0 to "number of CPUs in system - 1". This can get extremely long when isolating the majority of cpus on a large system. The kernel isolcpus code would not need any changing to use this feature. To use it, the change would be in the command line format for 'isolcpus=' Format: ,..., or - (must be a positive range in ascending order.) or a mixture ,...,- Signed-off-by: Derek Fults Cc: "Randy.Dunlap" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/cmdline.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/cmdline.c b/lib/cmdline.c index 0331ed8..8a5b530 100644 --- a/lib/cmdline.c +++ b/lib/cmdline.c @@ -16,6 +16,23 @@ #include #include +/* + * If a hyphen was found in get_option, this will handle the + * range of numbers, M-N. This will expand the range and insert + * the values[M, M+1, ..., N] into the ints array in get_options. + */ + +static int get_range(char **str, int *pint) +{ + int x, inc_counter, upper_range; + + (*str)++; + upper_range = simple_strtol((*str), NULL, 0); + inc_counter = upper_range - *pint; + for (x = *pint; x < upper_range; x++) + *pint++ = x; + return inc_counter; +} /** * get_option - Parse integer from an option string @@ -29,6 +46,7 @@ * 0 : no int in string * 1 : int found, no subsequent comma * 2 : int found including a subsequent comma + * 3 : hyphen found to denote a range */ int get_option (char **str, int *pint) @@ -44,6 +62,8 @@ int get_option (char **str, int *pint) (*str)++; return 2; } + if (**str == '-') + return 3; return 1; } @@ -55,7 +75,8 @@ int get_option (char **str, int *pint) * @ints: integer array * * This function parses a string containing a comma-separated - * list of integers. The parse halts when the array is + * list of integers, a hyphen-separated range of _positive_ integers, + * or a combination of both. The parse halts when the array is * full, or when no more numbers can be retrieved from the * string. * @@ -72,6 +93,18 @@ char *get_options(const char *str, int nints, int *ints) res = get_option ((char **)&str, ints + i); if (res == 0) break; + if (res == 3) { + int range_nums; + range_nums = get_range((char **)&str, ints + i); + if (range_nums < 0) + break; + /* + * Decrement the result by one to leave out the + * last number in the range. The next iteration + * will handle the upper number in the range + */ + i += (range_nums - 1); + } i++; if (res == 1) break; -- cgit v1.1 From 02316067852187b8bec781bec07410e91af79627 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Wed, 6 Dec 2006 20:38:17 -0800 Subject: [PATCH] hotplug CPU: clean up hotcpu_notifier() use There was lots of #ifdef noise in the kernel due to hotcpu_notifier(fn, prio) not correctly marking 'fn' as used in the !HOTPLUG_CPU case, and thus generating compiler warnings of unused symbols, hence forcing people to add #ifdefs. the compiler can skip truly unused functions just fine: text data bss dec hex filename 1624412 728710 3674856 6027978 5bfaca vmlinux.before 1624412 728710 3674856 6027978 5bfaca vmlinux.after [akpm@osdl.org: topology.c fix] Signed-off-by: Ingo Molnar Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/radix-tree.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index e2cefab..d69ddbe 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -996,7 +996,6 @@ static __init void radix_tree_init_maxindex(void) height_to_maxindex[i] = __maxindex(i); } -#ifdef CONFIG_HOTPLUG_CPU static int radix_tree_callback(struct notifier_block *nfb, unsigned long action, void *hcpu) @@ -1016,7 +1015,6 @@ static int radix_tree_callback(struct notifier_block *nfb, } return NOTIFY_OK; } -#endif /* CONFIG_HOTPLUG_CPU */ void __init radix_tree_init(void) { -- cgit v1.1 From 4668edc334ee90cf50c382c3e423cfc510b5a126 Mon Sep 17 00:00:00 2001 From: Burman Yan Date: Wed, 6 Dec 2006 20:38:51 -0800 Subject: [PATCH] kernel core: replace kmalloc+memset with kzalloc Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/kobject.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/kobject.c b/lib/kobject.c index 744a4b1..7ce6dc1 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -111,10 +111,9 @@ char *kobject_get_path(struct kobject *kobj, gfp_t gfp_mask) len = get_kobj_path_length(kobj); if (len == 0) return NULL; - path = kmalloc(len, gfp_mask); + path = kzalloc(len, gfp_mask); if (!path) return NULL; - memset(path, 0x00, len); fill_kobj_path(kobj, path, len); return path; -- cgit v1.1 From 702a28b1e64be3dc313f5f0ceb6dc95edfbc5e18 Mon Sep 17 00:00:00 2001 From: Randy Dunlap Date: Wed, 6 Dec 2006 20:39:16 -0800 Subject: [PATCH] lib functions: always build hweight for loadable modules Always build hweight8/16/32/64() functions into the kernel so that loadable modules may use them. I didn't remove GENERIC_HWEIGHT since ALPHA_EV67, ia64, and some variants of UltraSparc(64) provide their own hweight functions. Fixes config/build problems with NTFS=m and JOYSTICK_ANALOG=m. Kernel: arch/x86_64/boot/bzImage is ready (#19) Building modules, stage 2. MODPOST 94 modules WARNING: "hweight32" [fs/ntfs/ntfs.ko] undefined! WARNING: "hweight16" [drivers/input/joystick/analog.ko] undefined! WARNING: "hweight8" [drivers/input/joystick/analog.ko] undefined! make[1]: *** [__modpost] Error 1 make: *** [modules] Error 2 Signed-off-by: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index cf98fab..fea8f90 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -25,7 +25,7 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o -lib-$(CONFIG_GENERIC_HWEIGHT) += hweight.o +obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_PLIST) += plist.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o -- cgit v1.1 From 2ee91f197c0bc654b24eed5831fd12aa0d566a7d Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Wed, 6 Dec 2006 20:39:32 -0800 Subject: [PATCH] lockdep: show more details about self-test failures Make the locking self-test failures (of 'FAILURE' type) easier to debug by printing more information. Signed-off-by: Ingo Molnar Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/locking-selftest.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib') diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index 7945787..280332c 100644 --- a/lib/locking-selftest.c +++ b/lib/locking-selftest.c @@ -963,7 +963,9 @@ static void dotest(void (*testcase_fn)(void), int expected, int lockclass_mask) printk("failed|"); } else { unexpected_testcase_failures++; + printk("FAILED|"); + dump_stack(); } } else { testcase_successes++; -- cgit v1.1 From 7664c5a1da4711bb6383117f51b94c8dc8f3f1cd Mon Sep 17 00:00:00 2001 From: Jeremy Fitzhardinge Date: Fri, 8 Dec 2006 02:36:19 -0800 Subject: [PATCH] Generic BUG implementation This patch adds common handling for kernel BUGs, for use by architectures as they wish. The code is derived from arch/powerpc. The advantages of having common BUG handling are: - consistent BUG reporting across architectures - shared implementation of out-of-line file/line data - implement CONFIG_DEBUG_BUGVERBOSE consistently This means that in inline impact of BUG is just the illegal instruction itself, which is an improvement for i386 and x86-64. A BUG is represented in the instruction stream as an illegal instruction, which has file/line information associated with it. This extra information is stored in the __bug_table section in the ELF file. When the kernel gets an illegal instruction, it first confirms it might possibly be from a BUG (ie, in kernel mode, the right illegal instruction). It then calls report_bug(). This searches __bug_table for a matching instruction pointer, and if found, prints the corresponding file/line information. If report_bug() determines that it wasn't a BUG which caused the trap, it returns BUG_TRAP_TYPE_NONE. Some architectures (powerpc) implement WARN using the same mechanism; if the illegal instruction was the result of a WARN, then report_bug(Q) returns CONFIG_DEBUG_BUGVERBOSE; otherwise it returns BUG_TRAP_TYPE_BUG. lib/bug.c keeps a list of loaded modules which can be searched for __bug_table entries. The architecture must call module_bug_finalize()/module_bug_cleanup() from its corresponding module_finalize/cleanup functions. Unsetting CONFIG_DEBUG_BUGVERBOSE will reduce the kernel size by some amount. At the very least, filename and line information will not be recorded for each but, but architectures may decide to store no extra information per BUG at all. Unfortunately, gcc doesn't have a general way to mark an asm() as noreturn, so architectures will generally have to include an infinite loop (or similar) in the BUG code, so that gcc knows execution won't continue beyond that point. gcc does have a __builtin_trap() operator which may be useful to achieve the same effect, unfortunately it cannot be used to actually implement the BUG itself, because there's no way to get the instruction's address for use in generating the __bug_table entry. [randy.dunlap@oracle.com: Handle BUG=n, GENERIC_BUG=n to prevent build errors] [bunk@stusta.de: include/linux/bug.h must always #include Cc: Andi Kleen Cc: Hugh Dickens Cc: Michael Ellerman Cc: Paul Mackerras Cc: Benjamin Herrenschmidt Cc: Rusty Russell Signed-off-by: Adrian Bunk Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 2 +- lib/Makefile | 2 + lib/bug.c | 163 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 166 insertions(+), 1 deletion(-) create mode 100644 lib/bug.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index b75fed7..ee46fb3 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -285,7 +285,7 @@ config DEBUG_HIGHMEM config DEBUG_BUGVERBOSE bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EMBEDDED depends on BUG - depends on ARM || ARM26 || AVR32 || M32R || M68K || SPARC32 || SPARC64 || X86_32 || FRV || SUPERH + depends on ARM || ARM26 || AVR32 || M32R || M68K || SPARC32 || SPARC64 || X86_32 || FRV || SUPERH || GENERIC_BUG default !EMBEDDED help Say Y here to make BUG() panics output the file name and line number diff --git a/lib/Makefile b/lib/Makefile index fea8f90..7ab486b 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -55,6 +55,8 @@ obj-$(CONFIG_AUDIT_GENERIC) += audit.o obj-$(CONFIG_SWIOTLB) += swiotlb.o +lib-$(CONFIG_GENERIC_BUG) += bug.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/bug.c b/lib/bug.c new file mode 100644 index 0000000..014b582 --- /dev/null +++ b/lib/bug.c @@ -0,0 +1,163 @@ +/* + Generic support for BUG() + + This respects the following config options: + + CONFIG_BUG - emit BUG traps. Nothing happens without this. + CONFIG_GENERIC_BUG - enable this code. + CONFIG_DEBUG_BUGVERBOSE - emit full file+line information for each BUG + + CONFIG_BUG and CONFIG_DEBUG_BUGVERBOSE are potentially user-settable + (though they're generally always on). + + CONFIG_GENERIC_BUG is set by each architecture using this code. + + To use this, your architecture must: + + 1. Set up the config options: + - Enable CONFIG_GENERIC_BUG if CONFIG_BUG + + 2. Implement BUG (and optionally BUG_ON, WARN, WARN_ON) + - Define HAVE_ARCH_BUG + - Implement BUG() to generate a faulting instruction + - NOTE: struct bug_entry does not have "file" or "line" entries + when CONFIG_DEBUG_BUGVERBOSE is not enabled, so you must generate + the values accordingly. + + 3. Implement the trap + - In the illegal instruction trap handler (typically), verify + that the fault was in kernel mode, and call report_bug() + - report_bug() will return whether it was a false alarm, a warning, + or an actual bug. + - You must implement the is_valid_bugaddr(bugaddr) callback which + returns true if the eip is a real kernel address, and it points + to the expected BUG trap instruction. + + Jeremy Fitzhardinge 2006 + */ +#include +#include +#include + +extern const struct bug_entry __start___bug_table[], __stop___bug_table[]; + +#ifdef CONFIG_MODULES +static LIST_HEAD(module_bug_list); + +static const struct bug_entry *module_find_bug(unsigned long bugaddr) +{ + struct module *mod; + + list_for_each_entry(mod, &module_bug_list, bug_list) { + const struct bug_entry *bug = mod->bug_table; + unsigned i; + + for (i = 0; i < mod->num_bugs; ++i, ++bug) + if (bugaddr == bug->bug_addr) + return bug; + } + return NULL; +} + +int module_bug_finalize(const Elf_Ehdr *hdr, const Elf_Shdr *sechdrs, + struct module *mod) +{ + char *secstrings; + unsigned int i; + + mod->bug_table = NULL; + mod->num_bugs = 0; + + /* Find the __bug_table section, if present */ + secstrings = (char *)hdr + sechdrs[hdr->e_shstrndx].sh_offset; + for (i = 1; i < hdr->e_shnum; i++) { + if (strcmp(secstrings+sechdrs[i].sh_name, "__bug_table")) + continue; + mod->bug_table = (void *) sechdrs[i].sh_addr; + mod->num_bugs = sechdrs[i].sh_size / sizeof(struct bug_entry); + break; + } + + /* + * Strictly speaking this should have a spinlock to protect against + * traversals, but since we only traverse on BUG()s, a spinlock + * could potentially lead to deadlock and thus be counter-productive. + */ + list_add(&mod->bug_list, &module_bug_list); + + return 0; +} + +void module_bug_cleanup(struct module *mod) +{ + list_del(&mod->bug_list); +} + +#else + +static inline const struct bug_entry *module_find_bug(unsigned long bugaddr) +{ + return NULL; +} +#endif + +const struct bug_entry *find_bug(unsigned long bugaddr) +{ + const struct bug_entry *bug; + + for (bug = __start___bug_table; bug < __stop___bug_table; ++bug) + if (bugaddr == bug->bug_addr) + return bug; + + return module_find_bug(bugaddr); +} + +enum bug_trap_type report_bug(unsigned long bugaddr) +{ + const struct bug_entry *bug; + const char *file; + unsigned line, warning; + + if (!is_valid_bugaddr(bugaddr)) + return BUG_TRAP_TYPE_NONE; + + bug = find_bug(bugaddr); + + printk(KERN_EMERG "------------[ cut here ]------------\n"); + + file = NULL; + line = 0; + warning = 0; + + if (bug) { +#ifdef CONFIG_DEBUG_BUGVERBOSE + file = bug->file; + line = bug->line; +#endif + warning = (bug->flags & BUGFLAG_WARNING) != 0; + } + + if (warning) { + /* this is a WARN_ON rather than BUG/BUG_ON */ + if (file) + printk(KERN_ERR "Badness at %s:%u\n", + file, line); + else + printk(KERN_ERR "Badness at %p " + "[verbose debug info unavailable]\n", + (void *)bugaddr); + + dump_stack(); + return BUG_TRAP_TYPE_WARN; + } + + if (file) + printk(KERN_CRIT "kernel BUG at %s:%u!\n", + file, line); + else + printk(KERN_CRIT "Kernel BUG at %p " + "[verbose debug info unavailable]\n", + (void *)bugaddr); + + return BUG_TRAP_TYPE_BUG; +} -- cgit v1.1 From 91768d6c2bad0d2766a166f13f2f57e197de3458 Mon Sep 17 00:00:00 2001 From: Jeremy Fitzhardinge Date: Fri, 8 Dec 2006 02:36:21 -0800 Subject: [PATCH] Generic BUG for i386 This makes i386 use the generic BUG machinery. There are no functional changes from the old i386 implementation. The main advantage in using the generic BUG machinery for i386 is that the inlined overhead of BUG is just the ud2a instruction; the file+line(+function) information are no longer inlined into the instruction stream. This reduces cache pollution, and makes disassembly work properly. Signed-off-by: Jeremy Fitzhardinge Cc: Andi Kleen Cc: Hugh Dickens Cc: Michael Ellerman Cc: Paul Mackerras Cc: Benjamin Herrenschmidt Cc: Rusty Russell Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index ee46fb3..2c133c0 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -285,7 +285,7 @@ config DEBUG_HIGHMEM config DEBUG_BUGVERBOSE bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EMBEDDED depends on BUG - depends on ARM || ARM26 || AVR32 || M32R || M68K || SPARC32 || SPARC64 || X86_32 || FRV || SUPERH || GENERIC_BUG + depends on ARM || ARM26 || AVR32 || M32R || M68K || SPARC32 || SPARC64 || FRV || SUPERH || GENERIC_BUG default !EMBEDDED help Say Y here to make BUG() panics output the file name and line number -- cgit v1.1 From a5cfc1ec58a07074dacb6aa8c79eff864c966d12 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:36:25 -0800 Subject: [PATCH] bit reverse library This patch provides two bit reverse functions and bit reverse table. - reverse the order of bits in a u32 value u8 bitrev8(u8 x); - reverse the order of bits in a u32 value u32 bitrev32(u32 x); - byte reverse table const u8 byte_rev_table[256]; Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig | 3 +++ lib/Makefile | 1 + lib/bitrev.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 58 insertions(+) create mode 100644 lib/bitrev.c (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 734ce95..0d68355 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -4,6 +4,9 @@ menu "Library routines" +config BITREVERSE + tristate + config CRC_CCITT tristate "CRC-CCITT functions" help diff --git a/lib/Makefile b/lib/Makefile index 7ab486b..6f675c6 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -35,6 +35,7 @@ ifneq ($(CONFIG_HAVE_DEC_LOCK),y) lib-y += dec_and_lock.o endif +obj-$(CONFIG_BITREVERSE) += bitrev.o obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o obj-$(CONFIG_CRC16) += crc16.o obj-$(CONFIG_CRC32) += crc32.o diff --git a/lib/bitrev.c b/lib/bitrev.c new file mode 100644 index 0000000..f4e1c49 --- /dev/null +++ b/lib/bitrev.c @@ -0,0 +1,54 @@ +#include +#include +#include + +const u8 byte_rev_table[256] = { + 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, + 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, + 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, + 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, + 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, + 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, + 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, + 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, + 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, + 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, + 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, + 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, + 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, + 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, + 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, + 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, + 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, + 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, + 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, + 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, + 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, + 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, + 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, + 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, + 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, + 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, + 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, + 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, + 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, + 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, + 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, + 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, +}; +EXPORT_SYMBOL_GPL(byte_rev_table); + +static __always_inline u16 bitrev16(u16 x) +{ + return (bitrev8(x & 0xff) << 8) | bitrev8(x >> 8); +} + +/** + * bitrev32 - reverse the order of bits in a u32 value + * @x: value to be bit-reversed + */ +u32 bitrev32(u32 x) +{ + return (bitrev16(x & 0xffff) << 16) | bitrev16(x >> 16); +} +EXPORT_SYMBOL(bitrev32); -- cgit v1.1 From 906d66df18faa4aac8d898ae6920d1014694a932 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:36:25 -0800 Subject: [PATCH] crc32: replace bitreverse by bitrev32 This patch replaces bitreverse() by bitrev32. The only users of bitreverse() are crc32 itself and via-velocity. Cc: Jeff Garzik Cc: Matt Domsch Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig | 1 + lib/crc32.c | 28 +++++----------------------- 2 files changed, 6 insertions(+), 23 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 0d68355..47b172d 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -26,6 +26,7 @@ config CRC16 config CRC32 tristate "CRC32 functions" default y + select BITREVERSE help This option is provided for the case where no in-kernel-tree modules require CRC32 functions, but a module built outside the diff --git a/lib/crc32.c b/lib/crc32.c index 285fd9b..bfc3331 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -235,23 +235,8 @@ u32 __attribute_pure__ crc32_be(u32 crc, unsigned char const *p, size_t len) } #endif -/** - * bitreverse - reverse the order of bits in a u32 value - * @x: value to be bit-reversed - */ -u32 bitreverse(u32 x) -{ - x = (x >> 16) | (x << 16); - x = (x >> 8 & 0x00ff00ff) | (x << 8 & 0xff00ff00); - x = (x >> 4 & 0x0f0f0f0f) | (x << 4 & 0xf0f0f0f0); - x = (x >> 2 & 0x33333333) | (x << 2 & 0xcccccccc); - x = (x >> 1 & 0x55555555) | (x << 1 & 0xaaaaaaaa); - return x; -} - EXPORT_SYMBOL(crc32_le); EXPORT_SYMBOL(crc32_be); -EXPORT_SYMBOL(bitreverse); /* * A brief CRC tutorial. @@ -400,10 +385,7 @@ buf_dump(char const *prefix, unsigned char const *buf, size_t len) static void bytereverse(unsigned char *buf, size_t len) { while (len--) { - unsigned char x = *buf; - x = (x >> 4) | (x << 4); - x = (x >> 2 & 0x33) | (x << 2 & 0xcc); - x = (x >> 1 & 0x55) | (x << 1 & 0xaa); + unsigned char x = bitrev8(*buf); *buf++ = x; } } @@ -460,11 +442,11 @@ static u32 test_step(u32 init, unsigned char *buf, size_t len) /* Now swap it around for the other test */ bytereverse(buf, len + 4); - init = bitreverse(init); - crc2 = bitreverse(crc1); - if (crc1 != bitreverse(crc2)) + init = bitrev32(init); + crc2 = bitrev32(crc1); + if (crc1 != bitrev32(crc2)) printf("\nBit reversal fail: 0x%08x -> 0x%08x -> 0x%08x\n", - crc1, crc2, bitreverse(crc2)); + crc1, crc2, bitrev32(crc2)); crc1 = crc32_le(init, buf, len); if (crc1 != crc2) printf("\nCRC endianness fail: 0x%08x != 0x%08x\n", crc1, -- cgit v1.1 From 6ff1cb355e628f8fc55fa2d01e269e5e1bbc2fe9 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:43 -0800 Subject: [PATCH] fault-injection capabilities infrastructure This patch provides base functions implement to fault-injection capabilities. - The function should_fail() is taken from failmalloc-1.0 (http://www.nongnu.org/failmalloc/) [akpm@osdl.org: cleanups, comments, add __init] Cc: Signed-off-by: Akinobu Mita Signed-off-by: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 12 ++++ lib/Makefile | 1 + lib/fault-inject.c | 183 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 196 insertions(+) create mode 100644 lib/fault-inject.c (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 2c133c0..35228b3 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -413,3 +413,15 @@ config LKDTM Documentation on how to use the module can be found in drivers/misc/lkdtm.c + +config FAULT_INJECTION + bool + +config FAULT_INJECTION_DEBUG_FS + bool "Debugfs entries for fault-injection capabilities" + depends on FAULT_INJECTION && SYSFS + select DEBUG_FS + help + This option enable configuration of fault-injection capabilities via + debugfs. + diff --git a/lib/Makefile b/lib/Makefile index 6f675c6..2d6106a 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -55,6 +55,7 @@ obj-$(CONFIG_SMP) += percpu_counter.o obj-$(CONFIG_AUDIT_GENERIC) += audit.o obj-$(CONFIG_SWIOTLB) += swiotlb.o +obj-$(CONFIG_FAULT_INJECTION) += fault-inject.o lib-$(CONFIG_GENERIC_BUG) += bug.o diff --git a/lib/fault-inject.c b/lib/fault-inject.c new file mode 100644 index 0000000..a7cb3af --- /dev/null +++ b/lib/fault-inject.c @@ -0,0 +1,183 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +/* + * setup_fault_attr() is a helper function for various __setup handlers, so it + * returns 0 on error, because that is what __setup handlers do. + */ +int __init setup_fault_attr(struct fault_attr *attr, char *str) +{ + unsigned long probability; + unsigned long interval; + int times; + int space; + + /* ",,," */ + if (sscanf(str, "%lu,%lu,%d,%d", + &interval, &probability, &space, ×) < 4) { + printk(KERN_WARNING + "FAULT_INJECTION: failed to parse arguments\n"); + return 0; + } + + attr->probability = probability; + attr->interval = interval; + atomic_set(&attr->times, times); + atomic_set(&attr->space, space); + + return 1; +} + +static void fail_dump(struct fault_attr *attr) +{ + if (attr->verbose > 0) + printk(KERN_NOTICE "FAULT_INJECTION: forcing a failure\n"); + if (attr->verbose > 1) + dump_stack(); +} + +#define atomic_dec_not_zero(v) atomic_add_unless((v), -1, 0) + +/* + * This code is stolen from failmalloc-1.0 + * http://www.nongnu.org/failmalloc/ + */ + +int should_fail(struct fault_attr *attr, ssize_t size) +{ + if (atomic_read(&attr->times) == 0) + return 0; + + if (atomic_read(&attr->space) > size) { + atomic_sub(size, &attr->space); + return 0; + } + + if (attr->interval > 1) { + attr->count++; + if (attr->count % attr->interval) + return 0; + } + + if (attr->probability > random32() % 100) + goto fail; + + return 0; + +fail: + fail_dump(attr); + + if (atomic_read(&attr->times) != -1) + atomic_dec_not_zero(&attr->times); + + return 1; +} + +#ifdef CONFIG_FAULT_INJECTION_DEBUG_FS + +static void debugfs_ul_set(void *data, u64 val) +{ + *(unsigned long *)data = val; +} + +static u64 debugfs_ul_get(void *data) +{ + return *(unsigned long *)data; +} + +DEFINE_SIMPLE_ATTRIBUTE(fops_ul, debugfs_ul_get, debugfs_ul_set, "%llu\n"); + +static struct dentry *debugfs_create_ul(const char *name, mode_t mode, + struct dentry *parent, unsigned long *value) +{ + return debugfs_create_file(name, mode, parent, value, &fops_ul); +} + +static void debugfs_atomic_t_set(void *data, u64 val) +{ + atomic_set((atomic_t *)data, val); +} + +static u64 debugfs_atomic_t_get(void *data) +{ + return atomic_read((atomic_t *)data); +} + +DEFINE_SIMPLE_ATTRIBUTE(fops_atomic_t, debugfs_atomic_t_get, + debugfs_atomic_t_set, "%lld\n"); + +static struct dentry *debugfs_create_atomic_t(const char *name, mode_t mode, + struct dentry *parent, atomic_t *value) +{ + return debugfs_create_file(name, mode, parent, value, &fops_atomic_t); +} + +void cleanup_fault_attr_dentries(struct fault_attr *attr) +{ + debugfs_remove(attr->dentries.probability_file); + attr->dentries.probability_file = NULL; + + debugfs_remove(attr->dentries.interval_file); + attr->dentries.interval_file = NULL; + + debugfs_remove(attr->dentries.times_file); + attr->dentries.times_file = NULL; + + debugfs_remove(attr->dentries.space_file); + attr->dentries.space_file = NULL; + + debugfs_remove(attr->dentries.verbose_file); + attr->dentries.verbose_file = NULL; + + if (attr->dentries.dir) + WARN_ON(!simple_empty(attr->dentries.dir)); + + debugfs_remove(attr->dentries.dir); + attr->dentries.dir = NULL; +} + +int init_fault_attr_dentries(struct fault_attr *attr, const char *name) +{ + mode_t mode = S_IFREG | S_IRUSR | S_IWUSR; + struct dentry *dir; + + memset(&attr->dentries, 0, sizeof(attr->dentries)); + + dir = debugfs_create_dir(name, NULL); + if (!dir) + goto fail; + attr->dentries.dir = dir; + + attr->dentries.probability_file = + debugfs_create_ul("probability", mode, dir, &attr->probability); + + attr->dentries.interval_file = + debugfs_create_ul("interval", mode, dir, &attr->interval); + + attr->dentries.times_file = + debugfs_create_atomic_t("times", mode, dir, &attr->times); + + attr->dentries.space_file = + debugfs_create_atomic_t("space", mode, dir, &attr->space); + + attr->dentries.verbose_file = + debugfs_create_ul("verbose", mode, dir, &attr->verbose); + + if (!attr->dentries.probability_file || !attr->dentries.interval_file + || !attr->dentries.times_file || !attr->dentries.space_file + || !attr->dentries.verbose_file) + goto fail; + + return 0; +fail: + cleanup_fault_attr_dentries(attr); + return -ENOMEM; +} + +#endif /* CONFIG_FAULT_INJECTION_DEBUG_FS */ -- cgit v1.1 From 8a8b6502fb669c3a0638a08955442814cedc86b1 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:44 -0800 Subject: [PATCH] fault-injection capability for kmalloc This patch provides fault-injection capability for kmalloc. Boot option: failslab=,,, -- specifies the interval of failures. -- specifies how often it should fail in percent. -- specifies the size of free space where memory can be allocated safely in bytes. -- specifies how many times failures may happen at most. Debugfs: /debug/failslab/interval /debug/failslab/probability /debug/failslab/specifies /debug/failslab/times /debug/failslab/ignore-gfp-highmem /debug/failslab/ignore-gfp-wait Example: failslab=10,100,0,-1 slab allocation (kmalloc(), kmem_cache_alloc(),..) fails once per 10 times. Cc: Pekka Enberg Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 35228b3..c7f567a 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -417,6 +417,13 @@ config LKDTM config FAULT_INJECTION bool +config FAILSLAB + bool "Fault-injection capabilitiy for kmalloc" + depends on DEBUG_KERNEL + select FAULT_INJECTION + help + This option provides fault-injection capabilitiy for kmalloc. + config FAULT_INJECTION_DEBUG_FS bool "Debugfs entries for fault-injection capabilities" depends on FAULT_INJECTION && SYSFS -- cgit v1.1 From 933e312e73f8fc39652bd4d216a5393cc3a014b9 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:45 -0800 Subject: [PATCH] fault-injection capability for alloc_pages() This patch provides fault-injection capability for alloc_pages() Boot option: fail_page_alloc=,,, -- specifies the interval of failures. -- specifies how often it should fail in percent. -- specifies the size of free space where memory can be allocated safely in pages. -- specifies how many times failures may happen at most. Debugfs: /debug/fail_page_alloc/interval /debug/fail_page_alloc/probability /debug/fail_page_alloc/specifies /debug/fail_page_alloc/times /debug/fail_page_alloc/ignore-gfp-highmem /debug/fail_page_alloc/ignore-gfp-wait Example: fail_page_alloc=10,100,0,-1 The page allocation (alloc_pages(), ...) fails once per 10 times. Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index c7f567a..c66b7b4 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -424,6 +424,13 @@ config FAILSLAB help This option provides fault-injection capabilitiy for kmalloc. +config FAIL_PAGE_ALLOC + bool "Fault-injection capabilitiy for alloc_pages()" + depends on DEBUG_KERNEL + select FAULT_INJECTION + help + This option provides fault-injection capabilitiy for alloc_pages(). + config FAULT_INJECTION_DEBUG_FS bool "Debugfs entries for fault-injection capabilities" depends on FAULT_INJECTION && SYSFS -- cgit v1.1 From c17bb4951752d3e0f49cd1ea9d2e868422f9e0d6 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:46 -0800 Subject: [PATCH] fault-injection capability for disk IO This patch provides fault-injection capability for disk IO. Boot option: fail_make_request=,,, -- specifies the interval of failures. -- specifies how often it should fail in percent. -- specifies the size of free space where disk IO can be issued safely in bytes. -- specifies how many times failures may happen at most. Debugfs: /debug/fail_make_request/interval /debug/fail_make_request/probability /debug/fail_make_request/specifies /debug/fail_make_request/times Example: fail_make_request=10,100,0,-1 echo 1 > /sys/blocks/hda/hda1/make-it-fail generic_make_request() on /dev/hda1 fails once per 10 times. Cc: Jens Axboe Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index c66b7b4..336241b 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -431,6 +431,13 @@ config FAIL_PAGE_ALLOC help This option provides fault-injection capabilitiy for alloc_pages(). +config FAIL_MAKE_REQUEST + bool "Fault-injection capabilitiy for disk IO" + depends on DEBUG_KERNEL + select FAULT_INJECTION + help + This option provides fault-injection capabilitiy to disk IO. + config FAULT_INJECTION_DEBUG_FS bool "Debugfs entries for fault-injection capabilities" depends on FAULT_INJECTION && SYSFS -- cgit v1.1 From f4f154fd920b2178382a6a24a236348e4429ebc1 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:47 -0800 Subject: [PATCH] fault injection: process filtering for fault-injection capabilities This patch provides process filtering feature. The process filter allows failing only permitted processes by /proc//make-it-fail Please see the example that demostrates how to inject slab allocation failures into module init/cleanup code in Documentation/fault-injection/fault-injection.txt Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/fault-inject.c | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/fault-inject.c b/lib/fault-inject.c index a7cb3af..0346860 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -5,6 +5,7 @@ #include #include #include +#include #include /* @@ -44,6 +45,11 @@ static void fail_dump(struct fault_attr *attr) #define atomic_dec_not_zero(v) atomic_add_unless((v), -1, 0) +static int fail_task(struct fault_attr *attr, struct task_struct *task) +{ + return !in_interrupt() && task->make_it_fail; +} + /* * This code is stolen from failmalloc-1.0 * http://www.nongnu.org/failmalloc/ @@ -51,6 +57,9 @@ static void fail_dump(struct fault_attr *attr) int should_fail(struct fault_attr *attr, ssize_t size) { + if (attr->task_filter && !fail_task(attr, current)) + return 0; + if (atomic_read(&attr->times) == 0) return 0; @@ -135,6 +144,9 @@ void cleanup_fault_attr_dentries(struct fault_attr *attr) debugfs_remove(attr->dentries.verbose_file); attr->dentries.verbose_file = NULL; + debugfs_remove(attr->dentries.task_filter_file); + attr->dentries.task_filter_file = NULL; + if (attr->dentries.dir) WARN_ON(!simple_empty(attr->dentries.dir)); @@ -169,9 +181,12 @@ int init_fault_attr_dentries(struct fault_attr *attr, const char *name) attr->dentries.verbose_file = debugfs_create_ul("verbose", mode, dir, &attr->verbose); + attr->dentries.task_filter_file = debugfs_create_bool("task-filter", + mode, dir, &attr->task_filter); + if (!attr->dentries.probability_file || !attr->dentries.interval_file || !attr->dentries.times_file || !attr->dentries.space_file - || !attr->dentries.verbose_file) + || !attr->dentries.verbose_file || !attr->dentries.task_filter_file) goto fail; return 0; -- cgit v1.1 From 329409aeda064c4aff00c51f837fcd3bbdaeeba6 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 8 Dec 2006 02:39:48 -0800 Subject: [PATCH] fault injection: stacktrace filtering This patch provides stacktrace filtering feature. The stacktrace filter allows failing only for the caller you are interested in. For example someone may want to inject kmalloc() failures into only e100 module. they want to inject not only direct kmalloc() call, but also indirect allocation, too. - e100_poll --> netif_receive_skb --> packet_rcv_spkt --> skb_clone --> kmem_cache_alloc This patch enables to detect function calls like this by stacktrace and inject failures. The script Documentaion/fault-injection/failmodule.sh helps it. The range of text section of loaded e100 is expected to be [/sys/module/e100/sections/.text, /sys/module/e100/sections/.exit.text) So failmodule.sh stores these values into /debug/failslab/address-start and /debug/failslab/address-end. The maximum stacktrace depth is specified by /debug/failslab/stacktrace-depth. Please see the example that demonstrates how to inject slab allocation failures only for a specific module in Documentation/fault-injection/fault-injection.txt [dwm@meer.net: reject failure if any caller lies within specified range] Signed-off-by: Akinobu Mita Signed-off-by: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 5 +++ lib/fault-inject.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 130 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 336241b..1449ca1 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -416,6 +416,11 @@ config LKDTM config FAULT_INJECTION bool + select STACKTRACE + select FRAME_POINTER + help + Provide fault-injection framework. + For more details, see Documentation/fault-injection/. config FAILSLAB bool "Fault-injection capabilitiy for kmalloc" diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 0346860..361c6e9 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -6,6 +6,9 @@ #include #include #include +#include +#include +#include #include /* @@ -50,6 +53,86 @@ static int fail_task(struct fault_attr *attr, struct task_struct *task) return !in_interrupt() && task->make_it_fail; } +#ifdef CONFIG_STACK_UNWIND + +static asmlinkage int fail_stacktrace_callback(struct unwind_frame_info *info, + void *arg) +{ + int depth; + struct fault_attr *attr = arg; + bool found = (attr->require_start == 0 && attr->require_end == ULONG_MAX); + + for (depth = 0; depth < attr->stacktrace_depth + && unwind(info) == 0 && UNW_PC(info); depth++) { + if (arch_unw_user_mode(info)) + break; + if (attr->reject_start <= UNW_PC(info) && + UNW_PC(info) < attr->reject_end) + return 0; + if (attr->require_start <= UNW_PC(info) && + UNW_PC(info) < attr->require_end) + found = 1; + } + return found; +} + +static int fail_stacktrace(struct fault_attr *attr) +{ + struct unwind_frame_info info; + + return unwind_init_running(&info, fail_stacktrace_callback, attr); +} + +#elif defined(CONFIG_STACKTRACE) + +#define MAX_STACK_TRACE_DEPTH 32 + +static int fail_stacktrace(struct fault_attr *attr) +{ + struct stack_trace trace; + int depth = attr->stacktrace_depth; + unsigned long entries[MAX_STACK_TRACE_DEPTH]; + int n; + bool found = (attr->require_start == 0 && attr->require_end == ULONG_MAX); + + if (depth == 0) + return found; + + trace.nr_entries = 0; + trace.entries = entries; + trace.max_entries = (depth < MAX_STACK_TRACE_DEPTH) ? + depth : MAX_STACK_TRACE_DEPTH; + trace.skip = 1; + trace.all_contexts = 0; + + save_stack_trace(&trace, NULL); + for (n = 0; n < trace.nr_entries; n++) { + if (attr->reject_start <= entries[n] && + entries[n] < attr->reject_end) + return 0; + if (attr->require_start <= entries[n] && + entries[n] < attr->require_end) + found = 1; + } + return found; +} + +#else + +static inline int fail_stacktrace(struct fault_attr *attr) +{ + static int firsttime = 1; + + if (firsttime) { + printk(KERN_WARNING + "This architecture does not implement save_stack_trace()\n"); + firsttime = 0; + } + return 0; +} + +#endif + /* * This code is stolen from failmalloc-1.0 * http://www.nongnu.org/failmalloc/ @@ -60,6 +143,9 @@ int should_fail(struct fault_attr *attr, ssize_t size) if (attr->task_filter && !fail_task(attr, current)) return 0; + if (!fail_stacktrace(attr)) + return 0; + if (atomic_read(&attr->times) == 0) return 0; @@ -147,6 +233,21 @@ void cleanup_fault_attr_dentries(struct fault_attr *attr) debugfs_remove(attr->dentries.task_filter_file); attr->dentries.task_filter_file = NULL; + debugfs_remove(attr->dentries.stacktrace_depth_file); + attr->dentries.stacktrace_depth_file = NULL; + + debugfs_remove(attr->dentries.require_start_file); + attr->dentries.require_start_file = NULL; + + debugfs_remove(attr->dentries.require_end_file); + attr->dentries.require_end_file = NULL; + + debugfs_remove(attr->dentries.reject_start_file); + attr->dentries.reject_start_file = NULL; + + debugfs_remove(attr->dentries.reject_end_file); + attr->dentries.reject_end_file = NULL; + if (attr->dentries.dir) WARN_ON(!simple_empty(attr->dentries.dir)); @@ -184,9 +285,32 @@ int init_fault_attr_dentries(struct fault_attr *attr, const char *name) attr->dentries.task_filter_file = debugfs_create_bool("task-filter", mode, dir, &attr->task_filter); + attr->dentries.stacktrace_depth_file = + debugfs_create_ul("stacktrace-depth", mode, dir, + &attr->stacktrace_depth); + + attr->dentries.require_start_file = + debugfs_create_ul("require-start", mode, dir, &attr->require_start); + + attr->dentries.require_end_file = + debugfs_create_ul("require-end", mode, dir, &attr->require_end); + + attr->dentries.reject_start_file = + debugfs_create_ul("reject-start", mode, dir, &attr->reject_start); + + attr->dentries.reject_end_file = + debugfs_create_ul("reject-end", mode, dir, &attr->reject_end); + + if (!attr->dentries.probability_file || !attr->dentries.interval_file || !attr->dentries.times_file || !attr->dentries.space_file - || !attr->dentries.verbose_file || !attr->dentries.task_filter_file) + || !attr->dentries.verbose_file || !attr->dentries.task_filter_file + || !attr->dentries.stacktrace_depth_file + || !attr->dentries.require_start_file + || !attr->dentries.require_end_file + || !attr->dentries.reject_start_file + || !attr->dentries.reject_end_file + ) goto fail; return 0; -- cgit v1.1 From 1ab8509a31187998615e6dd7f53cc02db5be594c Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Fri, 8 Dec 2006 02:39:49 -0800 Subject: [PATCH] fault-injection Kconfig cleanup - Fix some spelling and grammatical errors - Make the Kconfig menu more conventional. First you select fault-injection, then under that you select particular clients of it. Cc: Akinobu Mita Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 27 +++++++++++---------------- 1 file changed, 11 insertions(+), 16 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 1449ca1..c24db72 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -415,7 +415,8 @@ config LKDTM drivers/misc/lkdtm.c config FAULT_INJECTION - bool + bool "Fault-injection framework" + depends on DEBUG_KERNEL select STACKTRACE select FRAME_POINTER help @@ -423,31 +424,25 @@ config FAULT_INJECTION For more details, see Documentation/fault-injection/. config FAILSLAB - bool "Fault-injection capabilitiy for kmalloc" - depends on DEBUG_KERNEL - select FAULT_INJECTION + bool "Fault-injection capability for kmalloc" + depends on FAULT_INJECTION help - This option provides fault-injection capabilitiy for kmalloc. + Provide fault-injection capability for kmalloc. config FAIL_PAGE_ALLOC bool "Fault-injection capabilitiy for alloc_pages()" - depends on DEBUG_KERNEL - select FAULT_INJECTION + depends on FAULT_INJECTION help - This option provides fault-injection capabilitiy for alloc_pages(). + Provide fault-injection capability for alloc_pages(). config FAIL_MAKE_REQUEST bool "Fault-injection capabilitiy for disk IO" - depends on DEBUG_KERNEL - select FAULT_INJECTION + depends on FAULT_INJECTION help - This option provides fault-injection capabilitiy to disk IO. + Provide fault-injection capability for disk IO. config FAULT_INJECTION_DEBUG_FS bool "Debugfs entries for fault-injection capabilities" - depends on FAULT_INJECTION && SYSFS - select DEBUG_FS + depends on FAULT_INJECTION && SYSFS && DEBUG_FS help - This option enable configuration of fault-injection capabilities via - debugfs. - + Enable configuration of fault-injection capabilities via debugfs. -- cgit v1.1 From 83ba254688f0edd6fa29512e538c721f1f46a424 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Fri, 8 Dec 2006 02:39:49 -0800 Subject: [PATCH] fault-injection: stacktrace filtering kconfig fix `select' doesn't work very well. With alpha `make allmodconfig' we end up with CONFIG_STACKTRACE enabled, so we end up with undefined save_stacktrace() at link time. Cc: Akinobu Mita Cc: Don Mullis Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index c24db72..6eccc64 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -417,7 +417,7 @@ config LKDTM config FAULT_INJECTION bool "Fault-injection framework" depends on DEBUG_KERNEL - select STACKTRACE + depends on STACKTRACE select FRAME_POINTER help Provide fault-injection framework. -- cgit v1.1 From 08b3df2d16cbebf7d72c09dcbc071696c14d07e3 Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 8 Dec 2006 02:39:51 -0800 Subject: [PATCH] fault-injection: Use bool-true-false throughout Use bool-true-false throughout. Signed-off-by: Don Mullis Cc: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/fault-inject.c | 40 +++++++++++++++++++--------------------- 1 file changed, 19 insertions(+), 21 deletions(-) (limited to 'lib') diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 361c6e9..2447829 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -48,7 +48,7 @@ static void fail_dump(struct fault_attr *attr) #define atomic_dec_not_zero(v) atomic_add_unless((v), -1, 0) -static int fail_task(struct fault_attr *attr, struct task_struct *task) +static bool fail_task(struct fault_attr *attr, struct task_struct *task) { return !in_interrupt() && task->make_it_fail; } @@ -68,15 +68,15 @@ static asmlinkage int fail_stacktrace_callback(struct unwind_frame_info *info, break; if (attr->reject_start <= UNW_PC(info) && UNW_PC(info) < attr->reject_end) - return 0; + return false; if (attr->require_start <= UNW_PC(info) && UNW_PC(info) < attr->require_end) - found = 1; + found = true; } return found; } -static int fail_stacktrace(struct fault_attr *attr) +static bool fail_stacktrace(struct fault_attr *attr) { struct unwind_frame_info info; @@ -85,9 +85,7 @@ static int fail_stacktrace(struct fault_attr *attr) #elif defined(CONFIG_STACKTRACE) -#define MAX_STACK_TRACE_DEPTH 32 - -static int fail_stacktrace(struct fault_attr *attr) +static bool fail_stacktrace(struct fault_attr *attr) { struct stack_trace trace; int depth = attr->stacktrace_depth; @@ -109,26 +107,26 @@ static int fail_stacktrace(struct fault_attr *attr) for (n = 0; n < trace.nr_entries; n++) { if (attr->reject_start <= entries[n] && entries[n] < attr->reject_end) - return 0; + return false; if (attr->require_start <= entries[n] && entries[n] < attr->require_end) - found = 1; + found = true; } return found; } #else -static inline int fail_stacktrace(struct fault_attr *attr) +static inline bool fail_stacktrace(struct fault_attr *attr) { - static int firsttime = 1; + static bool firsttime = true; if (firsttime) { printk(KERN_WARNING "This architecture does not implement save_stack_trace()\n"); - firsttime = 0; + firsttime = false; } - return 0; + return false; } #endif @@ -138,32 +136,32 @@ static inline int fail_stacktrace(struct fault_attr *attr) * http://www.nongnu.org/failmalloc/ */ -int should_fail(struct fault_attr *attr, ssize_t size) +bool should_fail(struct fault_attr *attr, ssize_t size) { if (attr->task_filter && !fail_task(attr, current)) - return 0; + return false; if (!fail_stacktrace(attr)) - return 0; + return false; if (atomic_read(&attr->times) == 0) - return 0; + return false; if (atomic_read(&attr->space) > size) { atomic_sub(size, &attr->space); - return 0; + return false; } if (attr->interval > 1) { attr->count++; if (attr->count % attr->interval) - return 0; + return false; } if (attr->probability > random32() % 100) goto fail; - return 0; + return false; fail: fail_dump(attr); @@ -171,7 +169,7 @@ fail: if (atomic_read(&attr->times) != -1) atomic_dec_not_zero(&attr->times); - return 1; + return true; } #ifdef CONFIG_FAULT_INJECTION_DEBUG_FS -- cgit v1.1 From a124c28ef85d9b780c418b2c5d8f01cd6a06ff3e Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 8 Dec 2006 02:39:52 -0800 Subject: [PATCH] fault-injection: Clamp debugfs stacktrace-depth to MAX_STACK_TRACE_DEPTH Clamp /debug/fail*/stacktrace-depth to MAX_STACK_TRACE_DEPTH. Ensures that a read of /debug/fail*/stacktrace-depth always returns a truthful answer. Signed-off-by: Don Mullis Cc: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/fault-inject.c | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 2447829..5da665a 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -53,6 +53,8 @@ static bool fail_task(struct fault_attr *attr, struct task_struct *task) return !in_interrupt() && task->make_it_fail; } +#define MAX_STACK_TRACE_DEPTH 32 + #ifdef CONFIG_STACK_UNWIND static asmlinkage int fail_stacktrace_callback(struct unwind_frame_info *info, @@ -98,8 +100,7 @@ static bool fail_stacktrace(struct fault_attr *attr) trace.nr_entries = 0; trace.entries = entries; - trace.max_entries = (depth < MAX_STACK_TRACE_DEPTH) ? - depth : MAX_STACK_TRACE_DEPTH; + trace.max_entries = depth; trace.skip = 1; trace.all_contexts = 0; @@ -179,6 +180,13 @@ static void debugfs_ul_set(void *data, u64 val) *(unsigned long *)data = val; } +static void debugfs_ul_set_MAX_STACK_TRACE_DEPTH(void *data, u64 val) +{ + *(unsigned long *)data = + val < MAX_STACK_TRACE_DEPTH ? + val : MAX_STACK_TRACE_DEPTH; +} + static u64 debugfs_ul_get(void *data) { return *(unsigned long *)data; @@ -192,6 +200,17 @@ static struct dentry *debugfs_create_ul(const char *name, mode_t mode, return debugfs_create_file(name, mode, parent, value, &fops_ul); } +DEFINE_SIMPLE_ATTRIBUTE(fops_ul_MAX_STACK_TRACE_DEPTH, debugfs_ul_get, + debugfs_ul_set_MAX_STACK_TRACE_DEPTH, "%llu\n"); + +static struct dentry *debugfs_create_ul_MAX_STACK_TRACE_DEPTH( + const char *name, mode_t mode, + struct dentry *parent, unsigned long *value) +{ + return debugfs_create_file(name, mode, parent, value, + &fops_ul_MAX_STACK_TRACE_DEPTH); +} + static void debugfs_atomic_t_set(void *data, u64 val) { atomic_set((atomic_t *)data, val); @@ -284,8 +303,8 @@ int init_fault_attr_dentries(struct fault_attr *attr, const char *name) mode, dir, &attr->task_filter); attr->dentries.stacktrace_depth_file = - debugfs_create_ul("stacktrace-depth", mode, dir, - &attr->stacktrace_depth); + debugfs_create_ul_MAX_STACK_TRACE_DEPTH( + "stacktrace-depth", mode, dir, &attr->stacktrace_depth); attr->dentries.require_start_file = debugfs_create_ul("require-start", mode, dir, &attr->require_start); -- cgit v1.1 From f1729c28a37e4f11ea5d9f468ab26adadb1aadab Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 8 Dec 2006 02:39:53 -0800 Subject: [PATCH] fault-injection: optimize and simplify should_fail() Trivial optimization and simplification of should_fail(). Do cheaper disqualification tests first (performance gain not quantified). Simplify logic; eliminate goto. Signed-off-by: Don Mullis Cc: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/fault-inject.c | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'lib') diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 5da665a..d143c0f 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -142,9 +142,6 @@ bool should_fail(struct fault_attr *attr, ssize_t size) if (attr->task_filter && !fail_task(attr, current)) return false; - if (!fail_stacktrace(attr)) - return false; - if (atomic_read(&attr->times) == 0) return false; @@ -159,12 +156,12 @@ bool should_fail(struct fault_attr *attr, ssize_t size) return false; } - if (attr->probability > random32() % 100) - goto fail; + if (attr->probability <= random32() % 100) + return false; - return false; + if (!fail_stacktrace(attr)) + return false; -fail: fail_dump(attr); if (atomic_read(&attr->times) != -1) -- cgit v1.1 From bf4735a46a6b8dfc1a951f05683e80374d8baa70 Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Sun, 10 Dec 2006 02:18:37 -0800 Subject: [PATCH] Kconfig refactoring for better menu nesting Refactor Kconfig content to maximize nesting of menus by menuconfig and xconfig. Tested by simultaneously running `make xconfig` with and without patch, and comparing displays. Signed-off-by: Don Mullis Signed-off-by: Randy Dunlap Cc: Sam Ravnborg Cc: Roman Zippel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 49 +++++++++++++++++++++++++------------------------ 1 file changed, 25 insertions(+), 24 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 6eccc64..0701ddd 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -47,6 +47,30 @@ config UNUSED_SYMBOLS you really need it, and what the merge plan to the mainline kernel for your module is. +config DEBUG_FS + bool "Debug Filesystem" + depends on SYSFS + help + debugfs is a virtual file system that kernel developers use to put + debugging files into. Enable this option to be able to read and + write to these files. + + If unsure, say N. + +config HEADERS_CHECK + bool "Run 'make headers_check' when building vmlinux" + depends on !UML + help + This option will extract the user-visible kernel headers whenever + building the kernel, and will run basic sanity checks on them to + ensure that exported files do not attempt to include files which + were not exported, etc. + + If you're making modifications to header files which are + relevant for userspace, say 'Y', and check the headers + exported to $(INSTALL_HDR_PATH) (usually 'usr/include' in + your build tree), to make sure they're suitable. + config DEBUG_KERNEL bool "Kernel debugging" help @@ -302,16 +326,6 @@ config DEBUG_INFO If unsure, say N. -config DEBUG_FS - bool "Debug Filesystem" - depends on SYSFS - help - debugfs is a virtual file system that kernel developers use to put - debugging files into. Enable this option to be able to read and - write to these files. - - If unsure, say N. - config DEBUG_VM bool "Debug VM" depends on DEBUG_KERNEL @@ -372,20 +386,6 @@ config FORCED_INLINING become the default in the future, until then this option is there to test gcc for this. -config HEADERS_CHECK - bool "Run 'make headers_check' when building vmlinux" - depends on !UML - help - This option will extract the user-visible kernel headers whenever - building the kernel, and will run basic sanity checks on them to - ensure that exported files do not attempt to include files which - were not exported, etc. - - If you're making modifications to header files which are - relevant for userspace, say 'Y', and check the headers - exported to $(INSTALL_HDR_PATH) (usually 'usr/include' in - your build tree), to make sure they're suitable. - config RCU_TORTURE_TEST tristate "torture tests for RCU" depends on DEBUG_KERNEL @@ -402,6 +402,7 @@ config RCU_TORTURE_TEST config LKDTM tristate "Linux Kernel Dump Test Tool Module" + depends on DEBUG_KERNEL depends on KPROBES default n help -- cgit v1.1 From 0258736a0a2cde8ab30725b601aeca4cf8bc93ab Mon Sep 17 00:00:00 2001 From: Cal Peake Date: Sun, 10 Dec 2006 06:22:05 -0500 Subject: [PATCH] add MODULE_* attributes to bit reversal library Add MODULE_* attributes to the new bit reversal library. Most notably MODULE_LICENSE which prevents superfluous kernel tainting. Signed-off-by: Cal Peake Signed-off-by: Linus Torvalds --- lib/bitrev.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'lib') diff --git a/lib/bitrev.c b/lib/bitrev.c index f4e1c49..989aff7 100644 --- a/lib/bitrev.c +++ b/lib/bitrev.c @@ -2,6 +2,10 @@ #include #include +MODULE_AUTHOR("Akinobu Mita "); +MODULE_DESCRIPTION("Bit ordering reversal functions"); +MODULE_LICENSE("GPL"); + const u8 byte_rev_table[256] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, -- cgit v1.1