From 37fce857bec00d26d0e8251c909da2bd8736c949 Mon Sep 17 00:00:00 2001 From: Paolo 'Blaisorblade' Giarrusso Date: Sat, 28 May 2005 15:51:59 -0700 Subject: [PATCH] uml: split CONFIG_FRAME_POINTER from DEBUG_INFO Until now, FRAME_POINTER was set = DEBUG_INFO for UML. Change it to be the default way, so that it can be enabled alone (for instance to get better backtraces on crashes). The call-trace dumper which uses the frame pointer is not yet in, I'm going to introduce it in a separate patch. Signed-off-by: Paolo 'Blaisorblade' Giarrusso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Kconfig.debug | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index ac23847ce0e3..0c421295e613 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -151,7 +151,8 @@ config DEBUG_FS config FRAME_POINTER bool "Compile the kernel with frame pointers" - depends on DEBUG_KERNEL && ((X86 && !X86_64) || CRIS || M68K || M68KNOMMU || FRV) + depends on DEBUG_KERNEL && ((X86 && !X86_64) || CRIS || M68K || M68KNOMMU || FRV || UML) + default y if DEBUG_INFO && UML help If you say Y here the resulting kernel image will be slightly larger and slower, but it will give very useful debugging information. -- cgit v1.2.3 From eb11d8ffceead1eb3d84366f1687daf2217e883e Mon Sep 17 00:00:00 2001 From: Dmitry Torokhov Date: Tue, 26 Apr 2005 02:29:58 -0500 Subject: [PATCH] kobject_hotplug() should use kobject_name() kobject: kobject_hotplug should use kobject_name() instead of accessing kobj->name directly since for objects with long names it can contain garbage. Signed-off-by: Dmitry Torokhov Signed-off-by: Greg Kroah-Hartman --- lib/kobject_uevent.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 2a4e7671eaf4..1ede5aa33376 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -246,7 +246,7 @@ void kobject_hotplug(struct kobject *kobj, enum kobject_action action) if (hotplug_ops->name) name = hotplug_ops->name(kset, kobj); if (name == NULL) - name = kset->kobj.name; + name = kobject_name(&kset->kobj); argv [0] = hotplug_path; argv [1] = name; -- cgit v1.2.3 From f3b4f3c6dec04c6c8261fe22645f07b39976595a Mon Sep 17 00:00:00 2001 From: Dmitry Torokhov Date: Tue, 26 Apr 2005 02:32:00 -0500 Subject: [PATCH] Make kobject's name be const char * kobject: make kobject's name const char * since users should not attempt to change it (except by calling kobject_rename). Signed-off-by: Dmitry Torokhov Signed-off-by: Greg Kroah-Hartman --- include/linux/kobject.h | 6 +++--- lib/kobject.c | 2 +- lib/kobject_uevent.c | 4 ++-- 3 files changed, 6 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/include/linux/kobject.h b/include/linux/kobject.h index 765d660d3bea..76dc67245c0c 100644 --- a/include/linux/kobject.h +++ b/include/linux/kobject.h @@ -33,7 +33,7 @@ extern u64 hotplug_seqnum; struct kobject { - char * k_name; + const char * k_name; char name[KOBJ_NAME_LEN]; struct kref kref; struct list_head entry; @@ -46,7 +46,7 @@ struct kobject { extern int kobject_set_name(struct kobject *, const char *, ...) __attribute__((format(printf,2,3))); -static inline char * kobject_name(struct kobject * kobj) +static inline const char * kobject_name(const struct kobject * kobj) { return kobj->k_name; } @@ -57,7 +57,7 @@ extern void kobject_cleanup(struct kobject *); extern int kobject_add(struct kobject *); extern void kobject_del(struct kobject *); -extern int kobject_rename(struct kobject *, char *new_name); +extern int kobject_rename(struct kobject *, const char *new_name); extern int kobject_register(struct kobject *); extern void kobject_unregister(struct kobject *); diff --git a/lib/kobject.c b/lib/kobject.c index 94048826624c..dd0917dd9fa9 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -279,7 +279,7 @@ EXPORT_SYMBOL(kobject_set_name); * @new_name: object's new name */ -int kobject_rename(struct kobject * kobj, char *new_name) +int kobject_rename(struct kobject * kobj, const char *new_name) { int error = 0; diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 1ede5aa33376..8e49d21057e4 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -197,7 +197,7 @@ void kobject_hotplug(struct kobject *kobj, enum kobject_action action) int i = 0; int retval; char *kobj_path = NULL; - char *name = NULL; + const char *name = NULL; char *action_string; u64 seq; struct kobject *top_kobj = kobj; @@ -249,7 +249,7 @@ void kobject_hotplug(struct kobject *kobj, enum kobject_action action) name = kobject_name(&kset->kobj); argv [0] = hotplug_path; - argv [1] = name; + argv [1] = (char *)name; /* won't be changed but 'const' has to go */ argv [2] = NULL; /* minimal command environment */ -- cgit v1.2.3 From 9a19fea43616066561e221359596ce532e631395 Mon Sep 17 00:00:00 2001 From: "mochel@digitalimplant.org" Date: Mon, 21 Mar 2005 11:45:16 -0800 Subject: [PATCH] Add initial implementation of klist helpers. This klist interface provides a couple of structures that wrap around struct list_head to provide explicit list "head" (struct klist) and list "node" (struct klist_node) objects. For struct klist, a spinlock is included that protects access to the actual list itself. struct klist_node provides a pointer to the klist that owns it and a kref reference count that indicates the number of current users of that node in the list. The entire point is to provide an interface for iterating over a list that is safe and allows for modification of the list during the iteration (e.g. insertion and removal), including modification of the current node on the list. It works using a 3rd object type - struct klist_iter - that is declared and initialized before an iteration. klist_next() is used to acquire the next element in the list. It returns NULL if there are no more items. This klist interface provides a couple of structures that wrap around struct list_head to provide explicit list "head" (struct klist) and list "node" (struct klist_node) objects. For struct klist, a spinlock is included that protects access to the actual list itself. struct klist_node provides a pointer to the klist that owns it and a kref reference count that indicates the number of current users of that node in the list. The entire point is to provide an interface for iterating over a list that is safe and allows for modification of the list during the iteration (e.g. insertion and removal), including modification of the current node on the list. It works using a 3rd object type - struct klist_iter - that is declared and initialized before an iteration. klist_next() is used to acquire the next element in the list. It returns NULL if there are no more items. Internally, that routine takes the klist's lock, decrements the reference count of the previous klist_node and increments the count of the next klist_node. It then drops the lock and returns. There are primitives for adding and removing nodes to/from a klist. When deleting, klist_del() will simply decrement the reference count. Only when the count goes to 0 is the node removed from the list. klist_remove() will try to delete the node from the list and block until it is actually removed. This is useful for objects (like devices) that have been removed from the system and must be freed (but must wait until all accessors have finished). Internally, that routine takes the klist's lock, decrements the reference count of the previous klist_node and increments the count of the next klist_node. It then drops the lock and returns. There are primitives for adding and removing nodes to/from a klist. When deleting, klist_del() will simply decrement the reference count. Only when the count goes to 0 is the node removed from the list. klist_remove() will try to delete the node from the list and block until it is actually removed. This is useful for objects (like devices) that have been removed from the system and must be freed (but must wait until all accessors have finished). Signed-off-by: Patrick Mochel Signed-off-by: Greg Kroah-Hartman diff -Nru a/include/linux/klist.h b/include/linux/klist.h --- include/linux/klist.h | 53 +++++++++++ lib/Makefile | 7 +- lib/klist.c | 248 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 305 insertions(+), 3 deletions(-) create mode 100644 include/linux/klist.h create mode 100644 lib/klist.c (limited to 'lib') diff --git a/include/linux/klist.h b/include/linux/klist.h new file mode 100644 index 000000000000..fb52f9d9d611 --- /dev/null +++ b/include/linux/klist.h @@ -0,0 +1,53 @@ +/* + * klist.h - Some generic list helpers, extending struct list_head a bit. + * + * Implementations are found in lib/klist.c + * + * + * Copyright (C) 2005 Patrick Mochel + * + * This file is rleased under the GPL v2. + */ + +#include +#include +#include +#include + + +struct klist { + spinlock_t k_lock; + struct list_head k_list; +}; + + +extern void klist_init(struct klist * k); + + +struct klist_node { + struct klist * n_klist; + struct list_head n_node; + struct kref n_ref; + struct completion n_removed; +}; + +extern void klist_add_tail(struct klist * k, struct klist_node * n); +extern void klist_add_head(struct klist * k, struct klist_node * n); + +extern void klist_del(struct klist_node * n); +extern void klist_remove(struct klist_node * n); + + +struct klist_iter { + struct klist * i_klist; + struct list_head * i_head; + struct klist_node * i_cur; +}; + + +extern void klist_iter_init(struct klist * k, struct klist_iter * i); +extern void klist_iter_init_node(struct klist * k, struct klist_iter * i, + struct klist_node * n); +extern void klist_iter_exit(struct klist_iter * i); +extern struct klist_node * klist_next(struct klist_iter * i); + diff --git a/lib/Makefile b/lib/Makefile index 7c70db79c0e0..9eccea9429a7 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -4,9 +4,10 @@ lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \ bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \ - kobject.o kref.o idr.o div64.o int_sqrt.o \ - bitmap.o extable.o kobject_uevent.o prio_tree.o sha1.o \ - halfmd4.o + idr.o div64.o int_sqrt.o bitmap.o extable.o prio_tree.o \ + sha1.o halfmd4.o + +lib-y += kobject.o kref.o kobject_uevent.o klist.o obj-y += sort.o parser.o diff --git a/lib/klist.c b/lib/klist.c new file mode 100644 index 000000000000..6f760424648b --- /dev/null +++ b/lib/klist.c @@ -0,0 +1,248 @@ +/* + * klist.c - Routines for manipulating klists. + * + * + * This klist interface provides a couple of structures that wrap around + * struct list_head to provide explicit list "head" (struct klist) and + * list "node" (struct klist_node) objects. For struct klist, a spinlock + * is included that protects access to the actual list itself. struct + * klist_node provides a pointer to the klist that owns it and a kref + * reference count that indicates the number of current users of that node + * in the list. + * + * The entire point is to provide an interface for iterating over a list + * that is safe and allows for modification of the list during the + * iteration (e.g. insertion and removal), including modification of the + * current node on the list. + * + * It works using a 3rd object type - struct klist_iter - that is declared + * and initialized before an iteration. klist_next() is used to acquire the + * next element in the list. It returns NULL if there are no more items. + * Internally, that routine takes the klist's lock, decrements the reference + * count of the previous klist_node and increments the count of the next + * klist_node. It then drops the lock and returns. + * + * There are primitives for adding and removing nodes to/from a klist. + * When deleting, klist_del() will simply decrement the reference count. + * Only when the count goes to 0 is the node removed from the list. + * klist_remove() will try to delete the node from the list and block + * until it is actually removed. This is useful for objects (like devices) + * that have been removed from the system and must be freed (but must wait + * until all accessors have finished). + * + * Copyright (C) 2005 Patrick Mochel + * + * This file is released under the GPL v2. + */ + +#include +#include + + +/** + * klist_init - Initialize a klist structure. + * @k: The klist we're initializing. + */ + +void klist_init(struct klist * k) +{ + INIT_LIST_HEAD(&k->k_list); + spin_lock_init(&k->k_lock); +} + +EXPORT_SYMBOL_GPL(klist_init); + + +static void add_head(struct klist * k, struct klist_node * n) +{ + spin_lock(&k->k_lock); + list_add(&n->n_node, &k->k_list); + spin_unlock(&k->k_lock); +} + +static void add_tail(struct klist * k, struct klist_node * n) +{ + spin_lock(&k->k_lock); + list_add_tail(&n->n_node, &k->k_list); + spin_unlock(&k->k_lock); +} + + +static void klist_node_init(struct klist * k, struct klist_node * n) +{ + INIT_LIST_HEAD(&n->n_node); + init_completion(&n->n_removed); + kref_init(&n->n_ref); + n->n_klist = k; +} + + +/** + * klist_add_head - Initialize a klist_node and add it to front. + * @k: klist it's going on. + * @n: node we're adding. + */ + +void klist_add_head(struct klist * k, struct klist_node * n) +{ + klist_node_init(k, n); + add_head(k, n); +} + +EXPORT_SYMBOL_GPL(klist_add_head); + + +/** + * klist_add_tail - Initialize a klist_node and add it to back. + * @k: klist it's going on. + * @n: node we're adding. + */ + +void klist_add_tail(struct klist * k, struct klist_node * n) +{ + klist_node_init(k, n); + add_tail(k, n); +} + +EXPORT_SYMBOL_GPL(klist_add_tail); + + +static void klist_release(struct kref * kref) +{ + struct klist_node * n = container_of(kref, struct klist_node, n_ref); + list_del(&n->n_node); + complete(&n->n_removed); +} + +static int klist_dec_and_del(struct klist_node * n) +{ + return kref_put(&n->n_ref, klist_release); +} + + +/** + * klist_del - Decrement the reference count of node and try to remove. + * @n: node we're deleting. + */ + +void klist_del(struct klist_node * n) +{ + struct klist * k = n->n_klist; + + spin_lock(&k->k_lock); + klist_dec_and_del(n); + spin_unlock(&k->k_lock); +} + +EXPORT_SYMBOL_GPL(klist_del); + + +/** + * klist_remove - Decrement the refcount of node and wait for it to go away. + * @n: node we're removing. + */ + +void klist_remove(struct klist_node * n) +{ + spin_lock(&n->n_klist->k_lock); + klist_dec_and_del(n); + spin_unlock(&n->n_klist->k_lock); + wait_for_completion(&n->n_removed); +} + +EXPORT_SYMBOL_GPL(klist_remove); + + +/** + * klist_iter_init_node - Initialize a klist_iter structure. + * @k: klist we're iterating. + * @i: klist_iter we're filling. + * @n: node to start with. + * + * Similar to klist_iter_init(), but starts the action off with @n, + * instead of with the list head. + */ + +void klist_iter_init_node(struct klist * k, struct klist_iter * i, struct klist_node * n) +{ + i->i_klist = k; + i->i_head = &k->k_list; + i->i_cur = n; +} + +EXPORT_SYMBOL_GPL(klist_iter_init_node); + + +/** + * klist_iter_init - Iniitalize a klist_iter structure. + * @k: klist we're iterating. + * @i: klist_iter structure we're filling. + * + * Similar to klist_iter_init_node(), but start with the list head. + */ + +void klist_iter_init(struct klist * k, struct klist_iter * i) +{ + klist_iter_init_node(k, i, NULL); +} + +EXPORT_SYMBOL_GPL(klist_iter_init); + + +/** + * klist_iter_exit - Finish a list iteration. + * @i: Iterator structure. + * + * Must be called when done iterating over list, as it decrements the + * refcount of the current node. Necessary in case iteration exited before + * the end of the list was reached, and always good form. + */ + +void klist_iter_exit(struct klist_iter * i) +{ + if (i->i_cur) { + klist_del(i->i_cur); + i->i_cur = NULL; + } +} + +EXPORT_SYMBOL_GPL(klist_iter_exit); + + +static struct klist_node * to_klist_node(struct list_head * n) +{ + return container_of(n, struct klist_node, n_node); +} + + +/** + * klist_next - Ante up next node in list. + * @i: Iterator structure. + * + * First grab list lock. Decrement the reference count of the previous + * node, if there was one. Grab the next node, increment its reference + * count, drop the lock, and return that next node. + */ + +struct klist_node * klist_next(struct klist_iter * i) +{ + struct list_head * next; + struct klist_node * knode = NULL; + + spin_lock(&i->i_klist->k_lock); + if (i->i_cur) { + next = i->i_cur->n_node.next; + klist_dec_and_del(i->i_cur); + } else + next = i->i_head->next; + + if (next != i->i_head) { + knode = to_klist_node(next); + kref_get(&knode->n_ref); + } + i->i_cur = knode; + spin_unlock(&i->i_klist->k_lock); + return knode; +} + +EXPORT_SYMBOL_GPL(klist_next); -- cgit v1.2.3 From 8b0c250be489dcbf1a3a33bb4ec4c7f33735a365 Mon Sep 17 00:00:00 2001 From: "mochel@digitalimplant.org" Date: Thu, 24 Mar 2005 12:58:57 -0800 Subject: [PATCH] add klist_node_attached() to determine if a node is on a list or not. Signed-off-by: Patrick Mochel Signed-off-by: Greg Kroah-Hartman diff -Nru a/include/linux/klist.h b/include/linux/klist.h --- include/linux/klist.h | 2 ++ lib/klist.c | 16 ++++++++++++++++ 2 files changed, 18 insertions(+) (limited to 'lib') diff --git a/include/linux/klist.h b/include/linux/klist.h index fb52f9d9d611..eebf5e5696ec 100644 --- a/include/linux/klist.h +++ b/include/linux/klist.h @@ -37,6 +37,8 @@ extern void klist_add_head(struct klist * k, struct klist_node * n); extern void klist_del(struct klist_node * n); extern void klist_remove(struct klist_node * n); +extern int klist_node_attached(struct klist_node * n); + struct klist_iter { struct klist * i_klist; diff --git a/lib/klist.c b/lib/klist.c index 6f760424648b..02177d72dc89 100644 --- a/lib/klist.c +++ b/lib/klist.c @@ -112,6 +112,7 @@ static void klist_release(struct kref * kref) struct klist_node * n = container_of(kref, struct klist_node, n_ref); list_del(&n->n_node); complete(&n->n_removed); + n->n_klist = NULL; } static int klist_dec_and_del(struct klist_node * n) @@ -153,6 +154,19 @@ void klist_remove(struct klist_node * n) EXPORT_SYMBOL_GPL(klist_remove); +/** + * klist_node_attached - Say whether a node is bound to a list or not. + * @n: Node that we're testing. + */ + +int klist_node_attached(struct klist_node * n) +{ + return (n->n_klist != NULL); +} + +EXPORT_SYMBOL_GPL(klist_node_attached); + + /** * klist_iter_init_node - Initialize a klist_iter structure. * @k: klist we're iterating. @@ -246,3 +260,5 @@ struct klist_node * klist_next(struct klist_iter * i) } EXPORT_SYMBOL_GPL(klist_next); + + -- cgit v1.2.3 From 0293a509405dccecc30783a5d729d615b68d6a77 Mon Sep 17 00:00:00 2001 From: "mochel@digitalimplant.org" Date: Thu, 24 Mar 2005 18:59:59 -0800 Subject: [PATCH] Don't reference NULL klist pointer in klist_remove(). Signed-off-by: Patrick Mochel Signed-off-by: Greg Kroah-Hartman diff -Nru a/lib/klist.c b/lib/klist.c --- lib/klist.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/klist.c b/lib/klist.c index 02177d72dc89..738ab810160a 100644 --- a/lib/klist.c +++ b/lib/klist.c @@ -145,9 +145,10 @@ EXPORT_SYMBOL_GPL(klist_del); void klist_remove(struct klist_node * n) { - spin_lock(&n->n_klist->k_lock); + struct klist * k = n->n_klist; + spin_lock(&k->k_lock); klist_dec_and_del(n); - spin_unlock(&n->n_klist->k_lock); + spin_unlock(&k->k_lock); wait_for_completion(&n->n_removed); } -- cgit v1.2.3 From 589777eab7360894b7ca1c4ba9d252e03b51225b Mon Sep 17 00:00:00 2001 From: Zaur Kambarov Date: Tue, 21 Jun 2005 17:14:31 -0700 Subject: [PATCH] coverity: idr_get_new_above_int() overrun fix This patch fixes overrun of array pa: 92 struct idr_layer *pa[MAX_LEVEL]; in 98 l = idp->layers; 99 pa[l--] = NULL; by passing idp->layers, set in 202 idp->layers = layers; to function sub_alloc in 203 v = sub_alloc(idp, ptr, &id); Signed-off-by: Zaur Kambarov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 81fc430602ee..c5be889de449 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -175,7 +175,7 @@ build_up: * Add a new layer to the top of the tree if the requested * id is larger than the currently allocated space. */ - while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) { + while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { layers++; if (!p->count) continue; -- cgit v1.2.3 From 39c715b71740c4a78ba4769fb54826929bac03cb Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Tue, 21 Jun 2005 17:14:34 -0700 Subject: [PATCH] smp_processor_id() cleanup This patch implements a number of smp_processor_id() cleanup ideas that Arjan van de Ven and I came up with. The previous __smp_processor_id/_smp_processor_id/smp_processor_id API spaghetti was hard to follow both on the implementational and on the usage side. Some of the complexity arose from picking wrong names, some of the complexity comes from the fact that not all architectures defined __smp_processor_id. In the new code, there are two externally visible symbols: - smp_processor_id(): debug variant. - raw_smp_processor_id(): nondebug variant. Replaces all existing uses of _smp_processor_id() and __smp_processor_id(). Defined by every SMP architecture in include/asm-*/smp.h. There is one new internal symbol, dependent on DEBUG_PREEMPT: - debug_smp_processor_id(): internal debug variant, mapped to smp_processor_id(). Also, i moved debug_smp_processor_id() from lib/kernel_lock.c into a new lib/smp_processor_id.c file. All related comments got updated and/or clarified. I have build/boot tested the following 8 .config combinations on x86: {SMP,UP} x {PREEMPT,!PREEMPT} x {DEBUG_PREEMPT,!DEBUG_PREEMPT} I have also build/boot tested x64 on UP/PREEMPT/DEBUG_PREEMPT. (Other architectures are untested, but should work just fine.) Signed-off-by: Ingo Molnar Signed-off-by: Arjan van de Ven Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- arch/i386/kernel/traps.c | 2 +- arch/i386/lib/delay.c | 2 +- arch/ppc/lib/locks.c | 4 +-- arch/ppc64/kernel/idle.c | 2 +- arch/sh/lib/delay.c | 2 +- arch/sparc64/lib/delay.c | 2 +- arch/x86_64/lib/delay.c | 2 +- drivers/acpi/processor_idle.c | 2 +- drivers/input/gameport/gameport.c | 2 +- drivers/oprofile/buffer_sync.c | 4 +-- fs/xfs/linux-2.6/xfs_linux.h | 6 ++--- include/asm-alpha/smp.h | 2 +- include/asm-arm/smp.h | 2 +- include/asm-i386/smp.h | 2 +- include/asm-ia64/smp.h | 2 +- include/asm-m32r/smp.h | 2 +- include/asm-mips/smp.h | 2 +- include/asm-parisc/smp.h | 2 +- include/asm-ppc/smp.h | 2 +- include/asm-ppc64/smp.h | 2 +- include/asm-s390/smp.h | 2 +- include/asm-sh/smp.h | 2 +- include/asm-sparc/smp.h | 2 +- include/asm-sparc64/smp.h | 2 +- include/asm-um/smp.h | 3 ++- include/asm-x86_64/smp.h | 2 +- include/linux/mmzone.h | 2 +- include/linux/smp.h | 40 ++++++++++++---------------- include/net/route.h | 2 +- include/net/snmp.h | 14 +++++----- kernel/module.c | 2 +- kernel/power/smp.c | 4 +-- kernel/sched.c | 4 +-- kernel/stop_machine.c | 4 +-- lib/Makefile | 1 + lib/kernel_lock.c | 55 --------------------------------------- lib/smp_processor_id.c | 55 +++++++++++++++++++++++++++++++++++++++ 37 files changed, 119 insertions(+), 125 deletions(-) create mode 100644 lib/smp_processor_id.c (limited to 'lib') diff --git a/arch/i386/kernel/traps.c b/arch/i386/kernel/traps.c index 00c63419c06f..83c579e82a81 100644 --- a/arch/i386/kernel/traps.c +++ b/arch/i386/kernel/traps.c @@ -306,7 +306,7 @@ void die(const char * str, struct pt_regs * regs, long err) }; static int die_counter; - if (die.lock_owner != _smp_processor_id()) { + if (die.lock_owner != raw_smp_processor_id()) { console_verbose(); spin_lock_irq(&die.lock); die.lock_owner = smp_processor_id(); diff --git a/arch/i386/lib/delay.c b/arch/i386/lib/delay.c index 080639f262b1..eb0cdfe9280f 100644 --- a/arch/i386/lib/delay.c +++ b/arch/i386/lib/delay.c @@ -34,7 +34,7 @@ inline void __const_udelay(unsigned long xloops) xloops *= 4; __asm__("mull %0" :"=d" (xloops), "=&a" (d0) - :"1" (xloops),"0" (cpu_data[_smp_processor_id()].loops_per_jiffy * (HZ/4))); + :"1" (xloops),"0" (cpu_data[raw_smp_processor_id()].loops_per_jiffy * (HZ/4))); __delay(++xloops); } diff --git a/arch/ppc/lib/locks.c b/arch/ppc/lib/locks.c index 694163d696d8..c450dc4b766e 100644 --- a/arch/ppc/lib/locks.c +++ b/arch/ppc/lib/locks.c @@ -130,7 +130,7 @@ void _raw_read_lock(rwlock_t *rw) while (!read_can_lock(rw)) { if (--stuck == 0) { printk("_read_lock(%p) CPU#%d lock %d\n", - rw, _smp_processor_id(), rw->lock); + rw, raw_smp_processor_id(), rw->lock); stuck = INIT_STUCK; } } @@ -158,7 +158,7 @@ void _raw_write_lock(rwlock_t *rw) while (!write_can_lock(rw)) { if (--stuck == 0) { printk("write_lock(%p) CPU#%d lock %d)\n", - rw, _smp_processor_id(), rw->lock); + rw, raw_smp_processor_id(), rw->lock); stuck = INIT_STUCK; } } diff --git a/arch/ppc64/kernel/idle.c b/arch/ppc64/kernel/idle.c index f24ce2b87200..ff8a7db142d3 100644 --- a/arch/ppc64/kernel/idle.c +++ b/arch/ppc64/kernel/idle.c @@ -292,7 +292,7 @@ static int native_idle(void) if (need_resched()) schedule(); - if (cpu_is_offline(_smp_processor_id()) && + if (cpu_is_offline(raw_smp_processor_id()) && system_state == SYSTEM_RUNNING) cpu_die(); } diff --git a/arch/sh/lib/delay.c b/arch/sh/lib/delay.c index 50b36037d86b..351714694d6d 100644 --- a/arch/sh/lib/delay.c +++ b/arch/sh/lib/delay.c @@ -24,7 +24,7 @@ inline void __const_udelay(unsigned long xloops) __asm__("dmulu.l %0, %2\n\t" "sts mach, %0" : "=r" (xloops) - : "0" (xloops), "r" (cpu_data[_smp_processor_id()].loops_per_jiffy) + : "0" (xloops), "r" (cpu_data[raw_smp_processor_id()].loops_per_jiffy) : "macl", "mach"); __delay(xloops * HZ); } diff --git a/arch/sparc64/lib/delay.c b/arch/sparc64/lib/delay.c index f6b4c784d53e..e8808727617a 100644 --- a/arch/sparc64/lib/delay.c +++ b/arch/sparc64/lib/delay.c @@ -31,7 +31,7 @@ void __const_udelay(unsigned long n) { n *= 4; - n *= (cpu_data(_smp_processor_id()).udelay_val * (HZ/4)); + n *= (cpu_data(raw_smp_processor_id()).udelay_val * (HZ/4)); n >>= 32; __delay(n + 1); diff --git a/arch/x86_64/lib/delay.c b/arch/x86_64/lib/delay.c index 6e2d66472eb1..aed61a668a1b 100644 --- a/arch/x86_64/lib/delay.c +++ b/arch/x86_64/lib/delay.c @@ -34,7 +34,7 @@ void __delay(unsigned long loops) inline void __const_udelay(unsigned long xloops) { - __delay(((xloops * cpu_data[_smp_processor_id()].loops_per_jiffy) >> 32) * HZ); + __delay(((xloops * cpu_data[raw_smp_processor_id()].loops_per_jiffy) >> 32) * HZ); } void __udelay(unsigned long usecs) diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c index ff64d333e95f..c9d671cf7857 100644 --- a/drivers/acpi/processor_idle.c +++ b/drivers/acpi/processor_idle.c @@ -171,7 +171,7 @@ static void acpi_processor_idle (void) int sleep_ticks = 0; u32 t1, t2 = 0; - pr = processors[_smp_processor_id()]; + pr = processors[raw_smp_processor_id()]; if (!pr) return; diff --git a/drivers/input/gameport/gameport.c b/drivers/input/gameport/gameport.c index 9b8ff396e6f8..e152d0fa0cdd 100644 --- a/drivers/input/gameport/gameport.c +++ b/drivers/input/gameport/gameport.c @@ -134,7 +134,7 @@ static int gameport_measure_speed(struct gameport *gameport) } gameport_close(gameport); - return (cpu_data[_smp_processor_id()].loops_per_jiffy * (unsigned long)HZ / (1000 / 50)) / (tx < 1 ? 1 : tx); + return (cpu_data[raw_smp_processor_id()].loops_per_jiffy * (unsigned long)HZ / (1000 / 50)) / (tx < 1 ? 1 : tx); #else diff --git a/drivers/oprofile/buffer_sync.c b/drivers/oprofile/buffer_sync.c index 55720dc6ec43..745a14183634 100644 --- a/drivers/oprofile/buffer_sync.c +++ b/drivers/oprofile/buffer_sync.c @@ -62,7 +62,7 @@ static int task_exit_notify(struct notifier_block * self, unsigned long val, voi /* To avoid latency problems, we only process the current CPU, * hoping that most samples for the task are on this CPU */ - sync_buffer(_smp_processor_id()); + sync_buffer(raw_smp_processor_id()); return 0; } @@ -86,7 +86,7 @@ static int munmap_notify(struct notifier_block * self, unsigned long val, void * /* To avoid latency problems, we only process the current CPU, * hoping that most samples for the task are on this CPU */ - sync_buffer(_smp_processor_id()); + sync_buffer(raw_smp_processor_id()); return 0; } diff --git a/fs/xfs/linux-2.6/xfs_linux.h b/fs/xfs/linux-2.6/xfs_linux.h index 71bb41019a12..7d7c8788ea75 100644 --- a/fs/xfs/linux-2.6/xfs_linux.h +++ b/fs/xfs/linux-2.6/xfs_linux.h @@ -145,10 +145,10 @@ static inline void set_buffer_unwritten_io(struct buffer_head *bh) #define xfs_inherit_nosymlinks xfs_params.inherit_nosym.val #define xfs_rotorstep xfs_params.rotorstep.val -#ifndef __smp_processor_id -#define __smp_processor_id() smp_processor_id() +#ifndef raw_smp_processor_id +#define raw_smp_processor_id() smp_processor_id() #endif -#define current_cpu() __smp_processor_id() +#define current_cpu() raw_smp_processor_id() #define current_pid() (current->pid) #define current_fsuid(cred) (current->fsuid) #define current_fsgid(cred) (current->fsgid) diff --git a/include/asm-alpha/smp.h b/include/asm-alpha/smp.h index cbc173ae45aa..9950706abdf8 100644 --- a/include/asm-alpha/smp.h +++ b/include/asm-alpha/smp.h @@ -43,7 +43,7 @@ extern struct cpuinfo_alpha cpu_data[NR_CPUS]; #define PROC_CHANGE_PENALTY 20 #define hard_smp_processor_id() __hard_smp_processor_id() -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern cpumask_t cpu_present_mask; extern cpumask_t cpu_online_map; diff --git a/include/asm-arm/smp.h b/include/asm-arm/smp.h index bd44f894690f..6c6c60adbbaa 100644 --- a/include/asm-arm/smp.h +++ b/include/asm-arm/smp.h @@ -21,7 +21,7 @@ # error " included in non-SMP build" #endif -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern cpumask_t cpu_present_mask; #define cpu_possible_map cpu_present_mask diff --git a/include/asm-i386/smp.h b/include/asm-i386/smp.h index e03a206dfa36..55ef31f66bbe 100644 --- a/include/asm-i386/smp.h +++ b/include/asm-i386/smp.h @@ -51,7 +51,7 @@ extern u8 x86_cpu_to_apicid[]; * from the initial startup. We map APIC_BASE very early in page_setup(), * so this is correct in the x86 case. */ -#define __smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern cpumask_t cpu_callout_map; extern cpumask_t cpu_callin_map; diff --git a/include/asm-ia64/smp.h b/include/asm-ia64/smp.h index 3ba1a061e4ae..a3914352c995 100644 --- a/include/asm-ia64/smp.h +++ b/include/asm-ia64/smp.h @@ -46,7 +46,7 @@ ia64_get_lid (void) #define SMP_IRQ_REDIRECTION (1 << 0) #define SMP_IPI_REDIRECTION (1 << 1) -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern struct smp_boot_data { int cpu_count; diff --git a/include/asm-m32r/smp.h b/include/asm-m32r/smp.h index 8cd4d0da4be1..b9a20cdad65f 100644 --- a/include/asm-m32r/smp.h +++ b/include/asm-m32r/smp.h @@ -66,7 +66,7 @@ extern volatile int cpu_2_physid[NR_CPUS]; #define physid_to_cpu(physid) physid_2_cpu[physid] #define cpu_to_physid(cpu_id) cpu_2_physid[cpu_id] -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern cpumask_t cpu_callout_map; #define cpu_possible_map cpu_callout_map diff --git a/include/asm-mips/smp.h b/include/asm-mips/smp.h index 8ba370ecfd4c..5618f1e12f40 100644 --- a/include/asm-mips/smp.h +++ b/include/asm-mips/smp.h @@ -21,7 +21,7 @@ #include #include -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) /* Map from cpu id to sequential logical cpu number. This will only not be idempotent when cpus failed to come on-line. */ diff --git a/include/asm-parisc/smp.h b/include/asm-parisc/smp.h index fde77ac35463..9413f67a540b 100644 --- a/include/asm-parisc/smp.h +++ b/include/asm-parisc/smp.h @@ -51,7 +51,7 @@ extern void smp_send_reschedule(int cpu); extern unsigned long cpu_present_mask; -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) #endif /* CONFIG_SMP */ diff --git a/include/asm-ppc/smp.h b/include/asm-ppc/smp.h index ebfb614f55f6..17530c232c76 100644 --- a/include/asm-ppc/smp.h +++ b/include/asm-ppc/smp.h @@ -44,7 +44,7 @@ extern void smp_message_recv(int, struct pt_regs *); #define NO_PROC_ID 0xFF /* No processor magic marker */ #define PROC_CHANGE_PENALTY 20 -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) extern int __cpu_up(unsigned int cpu); diff --git a/include/asm-ppc64/smp.h b/include/asm-ppc64/smp.h index c8646fa999c2..8115ecb8feee 100644 --- a/include/asm-ppc64/smp.h +++ b/include/asm-ppc64/smp.h @@ -45,7 +45,7 @@ void generic_cpu_die(unsigned int cpu); void generic_mach_cpu_die(void); #endif -#define __smp_processor_id() (get_paca()->paca_index) +#define raw_smp_processor_id() (get_paca()->paca_index) #define hard_smp_processor_id() (get_paca()->hw_cpu_id) extern cpumask_t cpu_sibling_map[NR_CPUS]; diff --git a/include/asm-s390/smp.h b/include/asm-s390/smp.h index 9473786387a3..dd50e57a928f 100644 --- a/include/asm-s390/smp.h +++ b/include/asm-s390/smp.h @@ -47,7 +47,7 @@ extern int smp_call_function_on(void (*func) (void *info), void *info, #define PROC_CHANGE_PENALTY 20 /* Schedule penalty */ -#define smp_processor_id() (S390_lowcore.cpu_data.cpu_nr) +#define raw_smp_processor_id() (S390_lowcore.cpu_data.cpu_nr) extern int smp_get_cpu(cpumask_t cpu_map); extern void smp_put_cpu(int cpu); diff --git a/include/asm-sh/smp.h b/include/asm-sh/smp.h index 38b54469d7d1..f19a8b3b69a6 100644 --- a/include/asm-sh/smp.h +++ b/include/asm-sh/smp.h @@ -25,7 +25,7 @@ extern cpumask_t cpu_possible_map; #define cpu_online(cpu) cpu_isset(cpu, cpu_online_map) -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) /* I've no idea what the real meaning of this is */ #define PROC_CHANGE_PENALTY 20 diff --git a/include/asm-sparc/smp.h b/include/asm-sparc/smp.h index f986c0d0922a..4f96d8333a12 100644 --- a/include/asm-sparc/smp.h +++ b/include/asm-sparc/smp.h @@ -148,7 +148,7 @@ extern __inline__ int hard_smp_processor_id(void) } #endif -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) #define prof_multiplier(__cpu) cpu_data(__cpu).multiplier #define prof_counter(__cpu) cpu_data(__cpu).counter diff --git a/include/asm-sparc64/smp.h b/include/asm-sparc64/smp.h index 5e3e06d908fe..110a2de89123 100644 --- a/include/asm-sparc64/smp.h +++ b/include/asm-sparc64/smp.h @@ -64,7 +64,7 @@ static __inline__ int hard_smp_processor_id(void) } } -#define smp_processor_id() (current_thread_info()->cpu) +#define raw_smp_processor_id() (current_thread_info()->cpu) #endif /* !(__ASSEMBLY__) */ diff --git a/include/asm-um/smp.h b/include/asm-um/smp.h index 4412d5d9c26b..d879eba2b52c 100644 --- a/include/asm-um/smp.h +++ b/include/asm-um/smp.h @@ -8,7 +8,8 @@ #include "asm/current.h" #include "linux/cpumask.h" -#define smp_processor_id() (current_thread->cpu) +#define raw_smp_processor_id() (current_thread->cpu) + #define cpu_logical_map(n) (n) #define cpu_number_map(n) (n) #define PROC_CHANGE_PENALTY 15 /* Pick a number, any number */ diff --git a/include/asm-x86_64/smp.h b/include/asm-x86_64/smp.h index 96844fecbde8..a7425aa5a3b7 100644 --- a/include/asm-x86_64/smp.h +++ b/include/asm-x86_64/smp.h @@ -68,7 +68,7 @@ static inline int num_booting_cpus(void) return cpus_weight(cpu_callout_map); } -#define __smp_processor_id() read_pda(cpunumber) +#define raw_smp_processor_id() read_pda(cpunumber) extern __inline int hard_smp_processor_id(void) { diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h index e530c6c092f1..beacd931b606 100644 --- a/include/linux/mmzone.h +++ b/include/linux/mmzone.h @@ -381,7 +381,7 @@ int lowmem_reserve_ratio_sysctl_handler(struct ctl_table *, int, struct file *, #include /* Returns the number of the current Node. */ -#define numa_node_id() (cpu_to_node(_smp_processor_id())) +#define numa_node_id() (cpu_to_node(raw_smp_processor_id())) #ifndef CONFIG_DISCONTIGMEM diff --git a/include/linux/smp.h b/include/linux/smp.h index dcf1db3b35d3..9dfa3ee769ae 100644 --- a/include/linux/smp.h +++ b/include/linux/smp.h @@ -92,10 +92,7 @@ void smp_prepare_boot_cpu(void); /* * These macros fold the SMP functionality into a single CPU system */ - -#if !defined(__smp_processor_id) || !defined(CONFIG_PREEMPT) -# define smp_processor_id() 0 -#endif +#define raw_smp_processor_id() 0 #define hard_smp_processor_id() 0 #define smp_call_function(func,info,retry,wait) ({ 0; }) #define on_each_cpu(func,info,retry,wait) ({ func(info); 0; }) @@ -106,30 +103,25 @@ static inline void smp_send_reschedule(int cpu) { } #endif /* !SMP */ /* - * DEBUG_PREEMPT support: check whether smp_processor_id() is being - * used in a preemption-safe way. + * smp_processor_id(): get the current CPU ID. * - * An architecture has to enable this debugging code explicitly. - * It can do so by renaming the smp_processor_id() macro to - * __smp_processor_id(). This should only be done after some minimal - * testing, because usually there are a number of false positives - * that an architecture will trigger. + * if DEBUG_PREEMPT is enabled the we check whether it is + * used in a preemption-safe way. (smp_processor_id() is safe + * if it's used in a preemption-off critical section, or in + * a thread that is bound to the current CPU.) * - * To fix a false positive (i.e. smp_processor_id() use that the - * debugging code reports but which use for some reason is legal), - * change the smp_processor_id() reference to _smp_processor_id(), - * which is the nondebug variant. NOTE: don't use this to hack around - * real bugs. + * NOTE: raw_smp_processor_id() is for internal use only + * (smp_processor_id() is the preferred variant), but in rare + * instances it might also be used to turn off false positives + * (i.e. smp_processor_id() use that the debugging code reports but + * which use for some reason is legal). Don't use this to hack around + * the warning message, as your code might not work under PREEMPT. */ -#ifdef __smp_processor_id -# if defined(CONFIG_PREEMPT) && defined(CONFIG_DEBUG_PREEMPT) - extern unsigned int smp_processor_id(void); -# else -# define smp_processor_id() __smp_processor_id() -# endif -# define _smp_processor_id() __smp_processor_id() +#ifdef CONFIG_DEBUG_PREEMPT + extern unsigned int debug_smp_processor_id(void); +# define smp_processor_id() debug_smp_processor_id() #else -# define _smp_processor_id() smp_processor_id() +# define smp_processor_id() raw_smp_processor_id() #endif #define get_cpu() ({ preempt_disable(); smp_processor_id(); }) diff --git a/include/net/route.h b/include/net/route.h index d34ca8fc6756..c3cd069a9aca 100644 --- a/include/net/route.h +++ b/include/net/route.h @@ -107,7 +107,7 @@ struct rt_cache_stat extern struct rt_cache_stat *rt_cache_stat; #define RT_CACHE_STAT_INC(field) \ - (per_cpu_ptr(rt_cache_stat, _smp_processor_id())->field++) + (per_cpu_ptr(rt_cache_stat, raw_smp_processor_id())->field++) extern struct ip_rt_acct *ip_rt_acct; diff --git a/include/net/snmp.h b/include/net/snmp.h index a15ab256276e..a36bed8ea210 100644 --- a/include/net/snmp.h +++ b/include/net/snmp.h @@ -128,18 +128,18 @@ struct linux_mib { #define SNMP_STAT_USRPTR(name) (name[1]) #define SNMP_INC_STATS_BH(mib, field) \ - (per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field]++) + (per_cpu_ptr(mib[0], raw_smp_processor_id())->mibs[field]++) #define SNMP_INC_STATS_OFFSET_BH(mib, field, offset) \ - (per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field + (offset)]++) + (per_cpu_ptr(mib[0], raw_smp_processor_id())->mibs[field + (offset)]++) #define SNMP_INC_STATS_USER(mib, field) \ - (per_cpu_ptr(mib[1], _smp_processor_id())->mibs[field]++) + (per_cpu_ptr(mib[1], raw_smp_processor_id())->mibs[field]++) #define SNMP_INC_STATS(mib, field) \ - (per_cpu_ptr(mib[!in_softirq()], _smp_processor_id())->mibs[field]++) + (per_cpu_ptr(mib[!in_softirq()], raw_smp_processor_id())->mibs[field]++) #define SNMP_DEC_STATS(mib, field) \ - (per_cpu_ptr(mib[!in_softirq()], _smp_processor_id())->mibs[field]--) + (per_cpu_ptr(mib[!in_softirq()], raw_smp_processor_id())->mibs[field]--) #define SNMP_ADD_STATS_BH(mib, field, addend) \ - (per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field] += addend) + (per_cpu_ptr(mib[0], raw_smp_processor_id())->mibs[field] += addend) #define SNMP_ADD_STATS_USER(mib, field, addend) \ - (per_cpu_ptr(mib[1], _smp_processor_id())->mibs[field] += addend) + (per_cpu_ptr(mib[1], raw_smp_processor_id())->mibs[field] += addend) #endif diff --git a/kernel/module.c b/kernel/module.c index 83b3d376708c..a566745dde62 100644 --- a/kernel/module.c +++ b/kernel/module.c @@ -379,7 +379,7 @@ static void module_unload_init(struct module *mod) for (i = 0; i < NR_CPUS; i++) local_set(&mod->ref[i].count, 0); /* Hold reference count during initialization. */ - local_set(&mod->ref[_smp_processor_id()].count, 1); + local_set(&mod->ref[raw_smp_processor_id()].count, 1); /* Backwards compatibility macros put refcount during init. */ mod->waiter = current; } diff --git a/kernel/power/smp.c b/kernel/power/smp.c index cba3584b80fe..457c2302ed42 100644 --- a/kernel/power/smp.c +++ b/kernel/power/smp.c @@ -48,11 +48,11 @@ void disable_nonboot_cpus(void) { oldmask = current->cpus_allowed; set_cpus_allowed(current, cpumask_of_cpu(0)); - printk("Freezing CPUs (at %d)", _smp_processor_id()); + printk("Freezing CPUs (at %d)", raw_smp_processor_id()); current->state = TASK_INTERRUPTIBLE; schedule_timeout(HZ); printk("..."); - BUG_ON(_smp_processor_id() != 0); + BUG_ON(raw_smp_processor_id() != 0); /* FIXME: for this to work, all the CPUs must be running * "idle" thread (or we deadlock). Is that guaranteed? */ diff --git a/kernel/sched.c b/kernel/sched.c index f12a0c8a7d98..deca041fc364 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -3814,7 +3814,7 @@ EXPORT_SYMBOL(yield); */ void __sched io_schedule(void) { - struct runqueue *rq = &per_cpu(runqueues, _smp_processor_id()); + struct runqueue *rq = &per_cpu(runqueues, raw_smp_processor_id()); atomic_inc(&rq->nr_iowait); schedule(); @@ -3825,7 +3825,7 @@ EXPORT_SYMBOL(io_schedule); long __sched io_schedule_timeout(long timeout) { - struct runqueue *rq = &per_cpu(runqueues, _smp_processor_id()); + struct runqueue *rq = &per_cpu(runqueues, raw_smp_processor_id()); long ret; atomic_inc(&rq->nr_iowait); diff --git a/kernel/stop_machine.c b/kernel/stop_machine.c index 6116b25aa7cf..84a9d18aa8da 100644 --- a/kernel/stop_machine.c +++ b/kernel/stop_machine.c @@ -100,7 +100,7 @@ static int stop_machine(void) stopmachine_state = STOPMACHINE_WAIT; for_each_online_cpu(i) { - if (i == _smp_processor_id()) + if (i == raw_smp_processor_id()) continue; ret = kernel_thread(stopmachine, (void *)(long)i,CLONE_KERNEL); if (ret < 0) @@ -182,7 +182,7 @@ struct task_struct *__stop_machine_run(int (*fn)(void *), void *data, /* If they don't care which CPU fn runs on, bind to any online one. */ if (cpu == NR_CPUS) - cpu = _smp_processor_id(); + cpu = raw_smp_processor_id(); p = kthread_create(do_stop, &smdata, "kstopmachine"); if (!IS_ERR(p)) { diff --git a/lib/Makefile b/lib/Makefile index 9eccea9429a7..5f10cb898407 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -20,6 +20,7 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o +obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o ifneq ($(CONFIG_HAVE_DEC_LOCK),y) lib-y += dec_and_lock.o diff --git a/lib/kernel_lock.c b/lib/kernel_lock.c index 99b0ae3d51dd..bd2bc5d887b8 100644 --- a/lib/kernel_lock.c +++ b/lib/kernel_lock.c @@ -9,61 +9,6 @@ #include #include -#if defined(CONFIG_PREEMPT) && defined(__smp_processor_id) && \ - defined(CONFIG_DEBUG_PREEMPT) - -/* - * Debugging check. - */ -unsigned int smp_processor_id(void) -{ - unsigned long preempt_count = preempt_count(); - int this_cpu = __smp_processor_id(); - cpumask_t this_mask; - - if (likely(preempt_count)) - goto out; - - if (irqs_disabled()) - goto out; - - /* - * Kernel threads bound to a single CPU can safely use - * smp_processor_id(): - */ - this_mask = cpumask_of_cpu(this_cpu); - - if (cpus_equal(current->cpus_allowed, this_mask)) - goto out; - - /* - * It is valid to assume CPU-locality during early bootup: - */ - if (system_state != SYSTEM_RUNNING) - goto out; - - /* - * Avoid recursion: - */ - preempt_disable(); - - if (!printk_ratelimit()) - goto out_enable; - - printk(KERN_ERR "BUG: using smp_processor_id() in preemptible [%08x] code: %s/%d\n", preempt_count(), current->comm, current->pid); - print_symbol("caller is %s\n", (long)__builtin_return_address(0)); - dump_stack(); - -out_enable: - preempt_enable_no_resched(); -out: - return this_cpu; -} - -EXPORT_SYMBOL(smp_processor_id); - -#endif /* PREEMPT && __smp_processor_id && DEBUG_PREEMPT */ - #ifdef CONFIG_PREEMPT_BKL /* * The 'big kernel semaphore' diff --git a/lib/smp_processor_id.c b/lib/smp_processor_id.c new file mode 100644 index 000000000000..42c08ef828c5 --- /dev/null +++ b/lib/smp_processor_id.c @@ -0,0 +1,55 @@ +/* + * lib/smp_processor_id.c + * + * DEBUG_PREEMPT variant of smp_processor_id(). + */ +#include +#include + +unsigned int debug_smp_processor_id(void) +{ + unsigned long preempt_count = preempt_count(); + int this_cpu = raw_smp_processor_id(); + cpumask_t this_mask; + + if (likely(preempt_count)) + goto out; + + if (irqs_disabled()) + goto out; + + /* + * Kernel threads bound to a single CPU can safely use + * smp_processor_id(): + */ + this_mask = cpumask_of_cpu(this_cpu); + + if (cpus_equal(current->cpus_allowed, this_mask)) + goto out; + + /* + * It is valid to assume CPU-locality during early bootup: + */ + if (system_state != SYSTEM_RUNNING) + goto out; + + /* + * Avoid recursion: + */ + preempt_disable(); + + if (!printk_ratelimit()) + goto out_enable; + + printk(KERN_ERR "BUG: using smp_processor_id() in preemptible [%08x] code: %s/%d\n", preempt_count(), current->comm, current->pid); + print_symbol("caller is %s\n", (long)__builtin_return_address(0)); + dump_stack(); + +out_enable: + preempt_enable_no_resched(); +out: + return this_cpu; +} + +EXPORT_SYMBOL(debug_smp_processor_id); + -- cgit v1.2.3 From f14f75b81187cdbe10cc53a521bf9fdf97b59f8c Mon Sep 17 00:00:00 2001 From: Jes Sorensen Date: Tue, 21 Jun 2005 17:15:02 -0700 Subject: [PATCH] ia64 uncached alloc This patch contains the ia64 uncached page allocator and the generic allocator (genalloc). The uncached allocator was formerly part of the SN2 mspec driver but there are several other users of it so it has been split off from the driver. The generic allocator can be used by device driver to manage special memory etc. The generic allocator is based on the allocator from the sym53c8xx_2 driver. Various users on ia64 needs uncached memory. The SGI SN architecture requires it for inter-partition communication between partitions within a large NUMA cluster. The specific user for this is the XPC code. Another application is large MPI style applications which use it for synchronization, on SN this can be done using special 'fetchop' operations but it also benefits non SN hardware which may use regular uncached memory for this purpose. Performance of doing this through uncached vs cached memory is pretty substantial. This is handled by the mspec driver which I will push out in a seperate patch. Rather than creating a specific allocator for just uncached memory I came up with genalloc which is a generic purpose allocator that can be used by device drivers and other subsystems as they please. For instance to handle onboard device memory. It was derived from the sym53c7xx_2 driver's allocator which is also an example of a potential user (I am refraining from modifying sym2 right now as it seems to have been under fairly heavy development recently). On ia64 memory has various properties within a granule, ie. it isn't safe to access memory as uncached within the same granule as currently has memory accessed in cached mode. The regular system therefore doesn't utilize memory in the lower granules which is mixed in with device PAL code etc. The uncached driver walks the EFI memmap and pulls out the spill uncached pages and sticks them into the uncached pool. Only after these chunks have been utilized, will it start converting regular cached memory into uncached memory. Hence the reason for the EFI related code additions. Signed-off-by: Jes Sorensen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- arch/ia64/Kconfig | 4 + arch/ia64/kernel/Makefile | 1 + arch/ia64/kernel/efi.c | 32 ++++++ arch/ia64/kernel/uncached.c | 246 ++++++++++++++++++++++++++++++++++++++++++++ include/asm-ia64/uncached.h | 12 +++ include/linux/genalloc.h | 40 +++++++ lib/Kconfig | 6 ++ lib/Makefile | 1 + lib/genalloc.c | 188 +++++++++++++++++++++++++++++++++ 9 files changed, 530 insertions(+) create mode 100644 arch/ia64/kernel/uncached.c create mode 100644 include/asm-ia64/uncached.h create mode 100644 include/linux/genalloc.h create mode 100644 lib/genalloc.c (limited to 'lib') diff --git a/arch/ia64/Kconfig b/arch/ia64/Kconfig index 3ad2c4af099c..295b5abee72f 100644 --- a/arch/ia64/Kconfig +++ b/arch/ia64/Kconfig @@ -50,6 +50,10 @@ config SCHED_NO_NO_OMIT_FRAME_POINTER bool default y +config IA64_UNCACHED_ALLOCATOR + bool + select GENERIC_ALLOCATOR + choice prompt "System type" default IA64_GENERIC diff --git a/arch/ia64/kernel/Makefile b/arch/ia64/kernel/Makefile index c1a02bbc252c..4c73d8ba2e3d 100644 --- a/arch/ia64/kernel/Makefile +++ b/arch/ia64/kernel/Makefile @@ -20,6 +20,7 @@ obj-$(CONFIG_SMP) += smp.o smpboot.o domain.o obj-$(CONFIG_PERFMON) += perfmon_default_smpl.o obj-$(CONFIG_IA64_CYCLONE) += cyclone.o obj-$(CONFIG_IA64_MCA_RECOVERY) += mca_recovery.o +obj-$(CONFIG_IA64_UNCACHED_ALLOCATOR) += uncached.o mca_recovery-y += mca_drv.o mca_drv_asm.o # The gate DSO image is built using a special linker script. diff --git a/arch/ia64/kernel/efi.c b/arch/ia64/kernel/efi.c index 4a3b1aac43e7..179f230816ed 100644 --- a/arch/ia64/kernel/efi.c +++ b/arch/ia64/kernel/efi.c @@ -409,6 +409,38 @@ efi_memmap_walk (efi_freemem_callback_t callback, void *arg) } } +/* + * Walk the EFI memory map to pull out leftover pages in the lower + * memory regions which do not end up in the regular memory map and + * stick them into the uncached allocator + * + * The regular walk function is significantly more complex than the + * uncached walk which means it really doesn't make sense to try and + * marge the two. + */ +void __init +efi_memmap_walk_uc (efi_freemem_callback_t callback) +{ + void *efi_map_start, *efi_map_end, *p; + efi_memory_desc_t *md; + u64 efi_desc_size, start, end; + + efi_map_start = __va(ia64_boot_param->efi_memmap); + efi_map_end = efi_map_start + ia64_boot_param->efi_memmap_size; + efi_desc_size = ia64_boot_param->efi_memdesc_size; + + for (p = efi_map_start; p < efi_map_end; p += efi_desc_size) { + md = p; + if (md->attribute == EFI_MEMORY_UC) { + start = PAGE_ALIGN(md->phys_addr); + end = PAGE_ALIGN((md->phys_addr+(md->num_pages << EFI_PAGE_SHIFT)) & PAGE_MASK); + if ((*callback)(start, end, NULL) < 0) + return; + } + } +} + + /* * Look for the PAL_CODE region reported by EFI and maps it using an * ITR to enable safe PAL calls in virtual mode. See IA-64 Processor diff --git a/arch/ia64/kernel/uncached.c b/arch/ia64/kernel/uncached.c new file mode 100644 index 000000000000..490dfc9ab47f --- /dev/null +++ b/arch/ia64/kernel/uncached.c @@ -0,0 +1,246 @@ +/* + * Copyright (C) 2001-2005 Silicon Graphics, Inc. All rights reserved. + * + * 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. + * + * A simple uncached page allocator using the generic allocator. This + * allocator first utilizes the spare (spill) pages found in the EFI + * memmap and will then start converting cached pages to uncached ones + * at a granule at a time. Node awareness is implemented by having a + * pool of pages per node. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define DEBUG 0 + +#if DEBUG +#define dprintk printk +#else +#define dprintk(x...) do { } while (0) +#endif + +void __init efi_memmap_walk_uc (efi_freemem_callback_t callback); + +#define MAX_UNCACHED_GRANULES 5 +static int allocated_granules; + +struct gen_pool *uncached_pool[MAX_NUMNODES]; + + +static void uncached_ipi_visibility(void *data) +{ + int status; + + status = ia64_pal_prefetch_visibility(PAL_VISIBILITY_PHYSICAL); + if ((status != PAL_VISIBILITY_OK) && + (status != PAL_VISIBILITY_OK_REMOTE_NEEDED)) + printk(KERN_DEBUG "pal_prefetch_visibility() returns %i on " + "CPU %i\n", status, get_cpu()); +} + + +static void uncached_ipi_mc_drain(void *data) +{ + int status; + status = ia64_pal_mc_drain(); + if (status) + printk(KERN_WARNING "ia64_pal_mc_drain() failed with %i on " + "CPU %i\n", status, get_cpu()); +} + + +static unsigned long +uncached_get_new_chunk(struct gen_pool *poolp) +{ + struct page *page; + void *tmp; + int status, i; + unsigned long addr, node; + + if (allocated_granules >= MAX_UNCACHED_GRANULES) + return 0; + + node = poolp->private; + page = alloc_pages_node(node, GFP_KERNEL | __GFP_ZERO, + IA64_GRANULE_SHIFT-PAGE_SHIFT); + + dprintk(KERN_INFO "get_new_chunk page %p, addr %lx\n", + page, (unsigned long)(page-vmem_map) << PAGE_SHIFT); + + /* + * Do magic if no mem on local node! XXX + */ + if (!page) + return 0; + tmp = page_address(page); + + /* + * There's a small race here where it's possible for someone to + * access the page through /dev/mem halfway through the conversion + * to uncached - not sure it's really worth bothering about + */ + for (i = 0; i < (IA64_GRANULE_SIZE / PAGE_SIZE); i++) + SetPageUncached(&page[i]); + + flush_tlb_kernel_range(tmp, tmp + IA64_GRANULE_SIZE); + + status = ia64_pal_prefetch_visibility(PAL_VISIBILITY_PHYSICAL); + + dprintk(KERN_INFO "pal_prefetch_visibility() returns %i on cpu %i\n", + status, get_cpu()); + + if (!status) { + status = smp_call_function(uncached_ipi_visibility, NULL, 0, 1); + if (status) + printk(KERN_WARNING "smp_call_function failed for " + "uncached_ipi_visibility! (%i)\n", status); + } + + if (ia64_platform_is("sn2")) + sn_flush_all_caches((unsigned long)tmp, IA64_GRANULE_SIZE); + else + flush_icache_range((unsigned long)tmp, + (unsigned long)tmp+IA64_GRANULE_SIZE); + + ia64_pal_mc_drain(); + status = smp_call_function(uncached_ipi_mc_drain, NULL, 0, 1); + if (status) + printk(KERN_WARNING "smp_call_function failed for " + "uncached_ipi_mc_drain! (%i)\n", status); + + addr = (unsigned long)tmp - PAGE_OFFSET + __IA64_UNCACHED_OFFSET; + + allocated_granules++; + return addr; +} + + +/* + * uncached_alloc_page + * + * Allocate 1 uncached page. Allocates on the requested node. If no + * uncached pages are available on the requested node, roundrobin starting + * with higher nodes. + */ +unsigned long +uncached_alloc_page(int nid) +{ + unsigned long maddr; + + maddr = gen_pool_alloc(uncached_pool[nid], PAGE_SIZE); + + dprintk(KERN_DEBUG "uncached_alloc_page returns %lx on node %i\n", + maddr, nid); + + /* + * If no memory is availble on our local node, try the + * remaining nodes in the system. + */ + if (!maddr) { + int i; + + for (i = MAX_NUMNODES - 1; i >= 0; i--) { + if (i == nid || !node_online(i)) + continue; + maddr = gen_pool_alloc(uncached_pool[i], PAGE_SIZE); + dprintk(KERN_DEBUG "uncached_alloc_page alternate search " + "returns %lx on node %i\n", maddr, i); + if (maddr) { + break; + } + } + } + + return maddr; +} +EXPORT_SYMBOL(uncached_alloc_page); + + +/* + * uncached_free_page + * + * Free a single uncached page. + */ +void +uncached_free_page(unsigned long maddr) +{ + int node; + + node = nasid_to_cnodeid(NASID_GET(maddr)); + + dprintk(KERN_DEBUG "uncached_free_page(%lx) on node %i\n", maddr, node); + + if ((maddr & (0XFUL << 60)) != __IA64_UNCACHED_OFFSET) + panic("uncached_free_page invalid address %lx\n", maddr); + + gen_pool_free(uncached_pool[node], maddr, PAGE_SIZE); +} +EXPORT_SYMBOL(uncached_free_page); + + +/* + * uncached_build_memmap, + * + * Called at boot time to build a map of pages that can be used for + * memory special operations. + */ +static int __init +uncached_build_memmap(unsigned long start, unsigned long end, void *arg) +{ + long length; + unsigned long vstart, vend; + int node; + + length = end - start; + vstart = start + __IA64_UNCACHED_OFFSET; + vend = end + __IA64_UNCACHED_OFFSET; + + dprintk(KERN_ERR "uncached_build_memmap(%lx %lx)\n", start, end); + + memset((char *)vstart, 0, length); + + node = nasid_to_cnodeid(NASID_GET(start)); + + for (; vstart < vend ; vstart += PAGE_SIZE) { + dprintk(KERN_INFO "sticking %lx into the pool!\n", vstart); + gen_pool_free(uncached_pool[node], vstart, PAGE_SIZE); + } + + return 0; +} + + +static int __init uncached_init(void) { + int i; + + for (i = 0; i < MAX_NUMNODES; i++) { + if (!node_online(i)) + continue; + uncached_pool[i] = gen_pool_create(0, IA64_GRANULE_SHIFT, + &uncached_get_new_chunk, i); + } + + efi_memmap_walk_uc(uncached_build_memmap); + + return 0; +} + +__initcall(uncached_init); diff --git a/include/asm-ia64/uncached.h b/include/asm-ia64/uncached.h new file mode 100644 index 000000000000..b82d923b73c1 --- /dev/null +++ b/include/asm-ia64/uncached.h @@ -0,0 +1,12 @@ +/* + * Copyright (C) 2001-2005 Silicon Graphics, Inc. All rights reserved. + * + * 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. + * + * Prototypes for the uncached page allocator + */ + +extern unsigned long uncached_alloc_page(int nid); +extern void uncached_free_page(unsigned long); diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h new file mode 100644 index 000000000000..7fd0576a4454 --- /dev/null +++ b/include/linux/genalloc.h @@ -0,0 +1,40 @@ +/* + * Basic general purpose allocator for managing special purpose memory + * not managed by the regular kmalloc/kfree interface. + * Uses for this includes on-device special memory, uncached memory + * etc. + * + * This code is based on the buddy allocator found in the sym53c8xx_2 + * driver, adapted for general purpose use. + * + * This source code is licensed under the GNU General Public License, + * Version 2. See the file COPYING for more details. + */ + +#include + +#define ALLOC_MIN_SHIFT 5 /* 32 bytes minimum */ +/* + * Link between free memory chunks of a given size. + */ +struct gen_pool_link { + struct gen_pool_link *next; +}; + +/* + * Memory pool descriptor. + */ +struct gen_pool { + spinlock_t lock; + unsigned long (*get_new_chunk)(struct gen_pool *); + struct gen_pool *next; + struct gen_pool_link *h; + unsigned long private; + int max_chunk_shift; +}; + +unsigned long gen_pool_alloc(struct gen_pool *poolp, int size); +void gen_pool_free(struct gen_pool *mp, unsigned long ptr, int size); +struct gen_pool *gen_pool_create(int nr_chunks, int max_chunk_shift, + unsigned long (*fp)(struct gen_pool *), + unsigned long data); diff --git a/lib/Kconfig b/lib/Kconfig index eeb45225248f..2d4d4e3bc4aa 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -39,6 +39,12 @@ config ZLIB_INFLATE config ZLIB_DEFLATE tristate +# +# Generic allocator support is selected if needed +# +config GENERIC_ALLOCATOR + boolean + # # reed solomon support is select'ed if needed # diff --git a/lib/Makefile b/lib/Makefile index 5f10cb898407..dcb4231916e2 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -30,6 +30,7 @@ obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o obj-$(CONFIG_CRC32) += crc32.o obj-$(CONFIG_LIBCRC32C) += libcrc32c.o obj-$(CONFIG_GENERIC_IOMAP) += iomap.o +obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ diff --git a/lib/genalloc.c b/lib/genalloc.c new file mode 100644 index 000000000000..d6d30d2e7166 --- /dev/null +++ b/lib/genalloc.c @@ -0,0 +1,188 @@ +/* + * Basic general purpose allocator for managing special purpose memory + * not managed by the regular kmalloc/kfree interface. + * Uses for this includes on-device special memory, uncached memory + * etc. + * + * This code is based on the buddy allocator found in the sym53c8xx_2 + * driver Copyright (C) 1999-2001 Gerard Roudier , + * and adapted for general purpose use. + * + * Copyright 2005 (C) Jes Sorensen + * + * This source code is licensed under the GNU General Public License, + * Version 2. See the file COPYING for more details. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + + +struct gen_pool *gen_pool_create(int nr_chunks, int max_chunk_shift, + unsigned long (*fp)(struct gen_pool *), + unsigned long data) +{ + struct gen_pool *poolp; + unsigned long tmp; + int i; + + /* + * This is really an arbitrary limit, +10 is enough for + * IA64_GRANULE_SHIFT, aka 16MB. If anyone needs a large limit + * this can be increased without problems. + */ + if ((max_chunk_shift > (PAGE_SHIFT + 10)) || + ((max_chunk_shift < ALLOC_MIN_SHIFT) && max_chunk_shift)) + return NULL; + + if (!max_chunk_shift) + max_chunk_shift = PAGE_SHIFT; + + poolp = kmalloc(sizeof(struct gen_pool), GFP_KERNEL); + if (!poolp) + return NULL; + memset(poolp, 0, sizeof(struct gen_pool)); + poolp->h = kmalloc(sizeof(struct gen_pool_link) * + (max_chunk_shift - ALLOC_MIN_SHIFT + 1), + GFP_KERNEL); + if (!poolp->h) { + printk(KERN_WARNING "gen_pool_alloc() failed to allocate\n"); + kfree(poolp); + return NULL; + } + memset(poolp->h, 0, sizeof(struct gen_pool_link) * + (max_chunk_shift - ALLOC_MIN_SHIFT + 1)); + + spin_lock_init(&poolp->lock); + poolp->get_new_chunk = fp; + poolp->max_chunk_shift = max_chunk_shift; + poolp->private = data; + + for (i = 0; i < nr_chunks; i++) { + tmp = poolp->get_new_chunk(poolp); + printk(KERN_INFO "allocated %lx\n", tmp); + if (!tmp) + break; + gen_pool_free(poolp, tmp, (1 << poolp->max_chunk_shift)); + } + + return poolp; +} +EXPORT_SYMBOL(gen_pool_create); + + +/* + * Simple power of two buddy-like generic allocator. + * Provides naturally aligned memory chunks. + */ +unsigned long gen_pool_alloc(struct gen_pool *poolp, int size) +{ + int j, i, s, max_chunk_size; + unsigned long a, flags; + struct gen_pool_link *h = poolp->h; + + max_chunk_size = 1 << poolp->max_chunk_shift; + + if (size > max_chunk_size) + return 0; + + i = 0; + + size = max(size, 1 << ALLOC_MIN_SHIFT); + s = roundup_pow_of_two(size); + + j = i; + + spin_lock_irqsave(&poolp->lock, flags); + while (!h[j].next) { + if (s == max_chunk_size) { + struct gen_pool_link *ptr; + spin_unlock_irqrestore(&poolp->lock, flags); + ptr = (struct gen_pool_link *)poolp->get_new_chunk(poolp); + spin_lock_irqsave(&poolp->lock, flags); + h[j].next = ptr; + if (h[j].next) + h[j].next->next = NULL; + break; + } + j++; + s <<= 1; + } + a = (unsigned long) h[j].next; + if (a) { + h[j].next = h[j].next->next; + /* + * This should be split into a seperate function doing + * the chunk split in order to support custom + * handling memory not physically accessible by host + */ + while (j > i) { + j -= 1; + s >>= 1; + h[j].next = (struct gen_pool_link *) (a + s); + h[j].next->next = NULL; + } + } + spin_unlock_irqrestore(&poolp->lock, flags); + return a; +} +EXPORT_SYMBOL(gen_pool_alloc); + + +/* + * Counter-part of the generic allocator. + */ +void gen_pool_free(struct gen_pool *poolp, unsigned long ptr, int size) +{ + struct gen_pool_link *q; + struct gen_pool_link *h = poolp->h; + unsigned long a, b, flags; + int i, s, max_chunk_size; + + max_chunk_size = 1 << poolp->max_chunk_shift; + + if (size > max_chunk_size) + return; + + i = 0; + + size = max(size, 1 << ALLOC_MIN_SHIFT); + s = roundup_pow_of_two(size); + + a = ptr; + + spin_lock_irqsave(&poolp->lock, flags); + while (1) { + if (s == max_chunk_size) { + ((struct gen_pool_link *)a)->next = h[i].next; + h[i].next = (struct gen_pool_link *)a; + break; + } + b = a ^ s; + q = &h[i]; + + while (q->next && q->next != (struct gen_pool_link *)b) + q = q->next; + + if (!q->next) { + ((struct gen_pool_link *)a)->next = h[i].next; + h[i].next = (struct gen_pool_link *)a; + break; + } + q->next = q->next->next; + a = a & b; + s <<= 1; + i++; + } + spin_unlock_irqrestore(&poolp->lock, flags); +} +EXPORT_SYMBOL(gen_pool_free); -- cgit v1.2.3 From 2de4ff7bd658c97fb357efa3095a509674dacb5a Mon Sep 17 00:00:00 2001 From: Thomas Graf Date: Thu, 23 Jun 2005 20:49:30 -0700 Subject: [LIB]: Textsearch infrastructure. The textsearch infrastructure provides text searching facitilies for both linear and non-linear data. Individual search algorithms are implemented in modules and chosen by the user. Signed-off-by: Thomas Graf Signed-off-by: David S. Miller --- include/linux/textsearch.h | 180 +++++++++++++++++++++++++ lib/Kconfig | 8 +- lib/Makefile | 2 + lib/textsearch.c | 317 +++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 506 insertions(+), 1 deletion(-) create mode 100644 include/linux/textsearch.h create mode 100644 lib/textsearch.c (limited to 'lib') diff --git a/include/linux/textsearch.h b/include/linux/textsearch.h new file mode 100644 index 000000000000..941f45ac117a --- /dev/null +++ b/include/linux/textsearch.h @@ -0,0 +1,180 @@ +#ifndef __LINUX_TEXTSEARCH_H +#define __LINUX_TEXTSEARCH_H + +#ifdef __KERNEL__ + +#include +#include +#include +#include +#include + +struct ts_config; + +/** + * TS_AUTOLOAD - Automatically load textsearch modules when needed + */ +#define TS_AUTOLOAD 1 + +/** + * struct ts_state - search state + * @offset: offset for next match + * @cb: control buffer, for persistant variables of get_next_block() + */ +struct ts_state +{ + unsigned int offset; + char cb[40]; +}; + +/** + * struct ts_ops - search module operations + * @name: name of search algorithm + * @init: initialization function to prepare a search + * @find: find the next occurrence of the pattern + * @destroy: destroy algorithm specific parts of a search configuration + * @get_pattern: return head of pattern + * @get_pattern_len: return length of pattern + * @owner: module reference to algorithm + */ +struct ts_ops +{ + const char *name; + struct ts_config * (*init)(const void *, unsigned int, int); + unsigned int (*find)(struct ts_config *, + struct ts_state *); + void (*destroy)(struct ts_config *); + void * (*get_pattern)(struct ts_config *); + unsigned int (*get_pattern_len)(struct ts_config *); + struct module *owner; + struct list_head list; +}; + +/** + * struct ts_config - search configuration + * @ops: operations of chosen algorithm + * @get_next_block: callback to fetch the next block to search in + * @finish: callback to finalize a search + */ +struct ts_config +{ + struct ts_ops *ops; + + /** + * get_next_block - fetch next block of data + * @consumed: number of bytes consumed by the caller + * @dst: destination buffer + * @conf: search configuration + * @state: search state + * + * Called repeatedly until 0 is returned. Must assign the + * head of the next block of data to &*dst and return the length + * of the block or 0 if at the end. consumed == 0 indicates + * a new search. May store/read persistant values in state->cb. + */ + unsigned int (*get_next_block)(unsigned int consumed, + const u8 **dst, + struct ts_config *conf, + struct ts_state *state); + + /** + * finish - finalize/clean a series of get_next_block() calls + * @conf: search configuration + * @state: search state + * + * Called after the last use of get_next_block(), may be used + * to cleanup any leftovers. + */ + void (*finish)(struct ts_config *conf, + struct ts_state *state); +}; + +/** + * textsearch_next - continue searching for a pattern + * @conf: search configuration + * @state: search state + * + * Continues a search looking for more occurrences of the pattern. + * textsearch_find() must be called to find the first occurrence + * in order to reset the state. + * + * Returns the position of the next occurrence of the pattern or + * UINT_MAX if not match was found. + */ +static inline unsigned int textsearch_next(struct ts_config *conf, + struct ts_state *state) +{ + unsigned int ret = conf->ops->find(conf, state); + + if (conf->finish) + conf->finish(conf, state); + + return ret; +} + +/** + * textsearch_find - start searching for a pattern + * @conf: search configuration + * @state: search state + * + * Returns the position of first occurrence of the pattern or + * UINT_MAX if no match was found. + */ +static inline unsigned int textsearch_find(struct ts_config *conf, + struct ts_state *state) +{ + state->offset = 0; + return textsearch_next(conf, state); +} + +/** + * textsearch_get_pattern - return head of the pattern + * @conf: search configuration + */ +static inline void *textsearch_get_pattern(struct ts_config *conf) +{ + return conf->ops->get_pattern(conf); +} + +/** + * textsearch_get_pattern_len - return length of the pattern + * @conf: search configuration + */ +static inline unsigned int textsearch_get_pattern_len(struct ts_config *conf) +{ + return conf->ops->get_pattern_len(conf); +} + +extern int textsearch_register(struct ts_ops *); +extern int textsearch_unregister(struct ts_ops *); +extern struct ts_config *textsearch_prepare(const char *, const void *, + unsigned int, int, int); +extern void textsearch_destroy(struct ts_config *conf); +extern unsigned int textsearch_find_continuous(struct ts_config *, + struct ts_state *, + const void *, unsigned int); + + +#define TS_PRIV_ALIGNTO 8 +#define TS_PRIV_ALIGN(len) (((len) + TS_PRIV_ALIGNTO-1) & ~(TS_PRIV_ALIGNTO-1)) + +static inline struct ts_config *alloc_ts_config(size_t payload, int gfp_mask) +{ + struct ts_config *conf; + + conf = kmalloc(TS_PRIV_ALIGN(sizeof(*conf)) + payload, gfp_mask); + if (conf == NULL) + return ERR_PTR(-ENOMEM); + + memset(conf, 0, TS_PRIV_ALIGN(sizeof(*conf)) + payload); + return conf; +} + +static inline void *ts_config_priv(struct ts_config *conf) +{ + return ((u8 *) conf + TS_PRIV_ALIGN(sizeof(struct ts_config))); +} + +#endif /* __KERNEL__ */ + +#endif diff --git a/lib/Kconfig b/lib/Kconfig index 2d4d4e3bc4aa..5bc2d523e6d1 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -63,5 +63,11 @@ config REED_SOLOMON_ENC16 config REED_SOLOMON_DEC16 boolean -endmenu +config TEXTSEARCH + boolean "Textsearch infrastructure" + default y + help + Say Y here if you want to provide a textsearch infrastructure + to other subsystems. +endmenu diff --git a/lib/Makefile b/lib/Makefile index dcb4231916e2..3e917436ad60 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -36,6 +36,8 @@ obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ +lib-$(CONFIG_TEXTSEARCH) += textsearch.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/textsearch.c b/lib/textsearch.c new file mode 100644 index 000000000000..1e934c196f0f --- /dev/null +++ b/lib/textsearch.c @@ -0,0 +1,317 @@ +/* + * lib/textsearch.c Generic text search interface + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + * + * Authors: Thomas Graf + * Pablo Neira Ayuso + * + * ========================================================================== + * + * INTRODUCTION + * + * The textsearch infrastructure provides text searching facitilies for + * both linear and non-linear data. Individual search algorithms are + * implemented in modules and chosen by the user. + * + * ARCHITECTURE + * + * User + * +----------------+ + * | finish()|<--------------(6)-----------------+ + * |get_next_block()|<--------------(5)---------------+ | + * | | Algorithm | | + * | | +------------------------------+ + * | | | init() find() destroy() | + * | | +------------------------------+ + * | | Core API ^ ^ ^ + * | | +---------------+ (2) (4) (8) + * | (1)|----->| prepare() |---+ | | + * | (3)|----->| find()/next() |-----------+ | + * | (7)|----->| destroy() |----------------------+ + * +----------------+ +---------------+ + * + * (1) User configures a search by calling _prepare() specifying the + * search parameters such as the pattern and algorithm name. + * (2) Core requests the algorithm to allocate and initialize a search + * 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. + * (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 + * to fetch the data to be searched in block by block. + * (6) Algorithm invokes finish() after the last call to get_next_block + * to clean up any leftovers from get_next_block. (Optional) + * (7) User destroys the configuration by calling _destroy(). + * (8) Core notifies the algorithm to destroy algorithm specific + * allocations. (Optional) + * + * USAGE + * + * Before a search can be performed, a configuration must be created + * by calling textsearch_prepare() specyfing the searching algorithm and + * the pattern to look for. The returned configuration may then be used + * for an arbitary amount of times and even in parallel as long as a + * separate struct ts_state variable is provided to every instance. + * + * The actual search is performed by either calling textsearch_find_- + * continuous() for linear data or by providing an own get_next_block() + * implementation and calling textsearch_find(). Both functions return + * the position of the first occurrence of the patern or UINT_MAX if + * no match was found. Subsequent occurences can be found by calling + * textsearch_next() regardless of the linearity of the data. + * + * Once you're done using a configuration it must be given back via + * textsearch_destroy. + * + * EXAMPLE + * + * int pos; + * struct ts_config *conf; + * struct ts_state state; + * const char *pattern = "chicken"; + * const char *example = "We dance the funky chicken"; + * + * conf = textsearch_prepare("kmp", pattern, strlen(pattern), + * GFP_KERNEL, TS_AUTOLOAD); + * if (IS_ERR(conf)) { + * err = PTR_ERR(conf); + * goto errout; + * } + * + * pos = textsearch_find_continuous(conf, &state, example, strlen(example)); + * if (pos != UINT_MAX) + * panic("Oh my god, dancing chickens at %d\n", pos); + * + * textsearch_destroy(conf); + * + * ========================================================================== + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +static LIST_HEAD(ts_ops); +static DEFINE_SPINLOCK(ts_mod_lock); + +static inline struct ts_ops *lookup_ts_algo(const char *name) +{ + struct ts_ops *o; + + rcu_read_lock(); + list_for_each_entry_rcu(o, &ts_ops, list) { + if (!strcmp(name, o->name)) { + if (!try_module_get(o->owner)) + o = NULL; + rcu_read_unlock(); + return o; + } + } + rcu_read_unlock(); + + return NULL; +} + +/** + * textsearch_register - register a textsearch module + * @ops: operations lookup table + * + * This function must be called by textsearch modules to announce + * their presence. The specified &@ops must have %name set to a + * unique identifier and the callbacks find(), init(), get_pattern(), + * and get_pattern_len() must be implemented. + * + * Returns 0 or -EEXISTS if another module has already registered + * with same name. + */ +int textsearch_register(struct ts_ops *ops) +{ + int err = -EEXIST; + struct ts_ops *o; + + if (ops->name == NULL || ops->find == NULL || ops->init == NULL || + ops->get_pattern == NULL || ops->get_pattern_len == NULL) + return -EINVAL; + + spin_lock(&ts_mod_lock); + list_for_each_entry(o, &ts_ops, list) { + if (!strcmp(ops->name, o->name)) + goto errout; + } + + list_add_tail_rcu(&ops->list, &ts_ops); + err = 0; +errout: + spin_unlock(&ts_mod_lock); + return err; +} + +/** + * textsearch_unregister - unregister a textsearch module + * @ops: operations lookup table + * + * This function must be called by textsearch modules to announce + * their disappearance for examples when the module gets unloaded. + * The &ops parameter must be the same as the one during the + * registration. + * + * Returns 0 on success or -ENOENT if no matching textsearch + * registration was found. + */ +int textsearch_unregister(struct ts_ops *ops) +{ + int err = 0; + struct ts_ops *o; + + spin_lock(&ts_mod_lock); + list_for_each_entry(o, &ts_ops, list) { + if (o == ops) { + list_del_rcu(&o->list); + goto out; + } + } + + err = -ENOENT; +out: + spin_unlock(&ts_mod_lock); + return err; +} + +struct ts_linear_state +{ + unsigned int len; + const void *data; +}; + +static unsigned int get_linear_data(unsigned int consumed, const u8 **dst, + struct ts_config *conf, + struct ts_state *state) +{ + struct ts_linear_state *st = (struct ts_linear_state *) state->cb; + + if (likely(consumed < st->len)) { + *dst = st->data + consumed; + return st->len - consumed; + } + + return 0; +} + +/** + * textsearch_find_continuous - search a pattern in continuous/linear data + * @conf: search configuration + * @state: search state + * @data: data to search in + * @len: length of data + * + * A simplified version of textsearch_find() for continuous/linear data. + * Call textsearch_next() to retrieve subsequent matches. + * + * Returns the position of first occurrence of the pattern or + * UINT_MAX if no occurrence was found. + */ +unsigned int textsearch_find_continuous(struct ts_config *conf, + struct ts_state *state, + const void *data, unsigned int len) +{ + struct ts_linear_state *st = (struct ts_linear_state *) state->cb; + + conf->get_next_block = get_linear_data; + st->data = data; + st->len = len; + + return textsearch_find(conf, state); +} + +/** + * textsearch_prepare - Prepare a search + * @algo: name of search algorithm + * @pattern: pattern data + * @len: length of pattern + * @gfp_mask: allocation mask + * @flags: search flags + * + * Looks up the search algorithm module and creates a new textsearch + * configuration for the specified pattern. Upon completion all + * necessary refcnts are held and the configuration must be put back + * using textsearch_put() after usage. + * + * Note: The format of the pattern may not be compatible between + * the various search algorithms. + * + * Returns a new textsearch configuration according to the specified + * parameters or a ERR_PTR(). + */ +struct ts_config *textsearch_prepare(const char *algo, const void *pattern, + unsigned int len, int gfp_mask, int flags) +{ + int err = -ENOENT; + struct ts_config *conf; + struct ts_ops *ops; + + ops = lookup_ts_algo(algo); +#ifdef CONFIG_KMOD + /* + * Why not always autoload you may ask. Some users are + * in a situation where requesting a module may deadlock, + * especially when the module is located on a NFS mount. + */ + if (ops == NULL && flags & TS_AUTOLOAD) { + request_module("ts_%s", algo); + ops = lookup_ts_algo(algo); + } +#endif + + if (ops == NULL) + goto errout; + + conf = ops->init(pattern, len, gfp_mask); + if (IS_ERR(conf)) { + err = PTR_ERR(conf); + goto errout; + } + + conf->ops = ops; + return conf; + +errout: + if (ops) + module_put(ops->owner); + + return ERR_PTR(err); +} + +/** + * textsearch_destroy - destroy a search configuration + * @conf: search configuration + * + * Releases all references of the configuration and frees + * up the memory. + */ +void textsearch_destroy(struct ts_config *conf) +{ + if (conf->ops) { + if (conf->ops->destroy) + conf->ops->destroy(conf); + module_put(conf->ops->owner); + } + + kfree(conf); +} + +EXPORT_SYMBOL(textsearch_register); +EXPORT_SYMBOL(textsearch_unregister); +EXPORT_SYMBOL(textsearch_prepare); +EXPORT_SYMBOL(textsearch_find_continuous); +EXPORT_SYMBOL(textsearch_destroy); -- cgit v1.2.3 From df3fb93ad9ec0b20c785c0ad82d42d159a1af272 Mon Sep 17 00:00:00 2001 From: Thomas Graf Date: Thu, 23 Jun 2005 20:58:37 -0700 Subject: [LIB]: Knuth-Morris-Pratt textsearch algorithm Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt [1]. Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") [2]. Since the array PI has only m entries, whereas DELTA has O(m|SIGMA|) entries, we save a factor of |SIGMA| in the preprocessing time by computing PI rather than DELTA. [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press [2] See finite automation theory Signed-off-by: Thomas Graf Signed-off-by: David S. Miller --- lib/Kconfig | 10 +++++ lib/Makefile | 1 + lib/ts_kmp.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 156 insertions(+) create mode 100644 lib/ts_kmp.c (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 5bc2d523e6d1..16b8fa2175e4 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -70,4 +70,14 @@ config TEXTSEARCH Say Y here if you want to provide a textsearch infrastructure to other subsystems. +config TEXTSEARCH_KMP + depends on TEXTSEARCH + tristate "Knuth-Morris-Pratt" + help + Say Y here if you want to be able to search text using the + Knuth-Morris-Pratt textsearch algorithm. + + To compile this code as a module, choose M here: the + module will be called ts_kmp. + endmenu diff --git a/lib/Makefile b/lib/Makefile index 3e917436ad60..6cdb10f312df 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -37,6 +37,7 @@ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ lib-$(CONFIG_TEXTSEARCH) += textsearch.o +obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/ts_kmp.c b/lib/ts_kmp.c new file mode 100644 index 000000000000..73266b975585 --- /dev/null +++ b/lib/ts_kmp.c @@ -0,0 +1,145 @@ +/* + * lib/ts_kmp.c Knuth-Morris-Pratt text search implementation + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + * + * Authors: Thomas Graf + * + * ========================================================================== + * + * Implements a linear-time string-matching algorithm due to Knuth, + * Morris, and Pratt [1]. Their algorithm avoids the explicit + * computation of the transition function DELTA altogether. Its + * matching time is O(n), for n being length(text), using just an + * auxiliary function PI[1..m], for m being length(pattern), + * precomputed from the pattern in time O(m). The array PI allows + * the transition function DELTA to be computed efficiently + * "on the fly" as needed. Roughly speaking, for any state + * "q" = 0,1,...,m and any character "a" in SIGMA, the value + * PI["q"] contains the information that is independent of "a" and + * is needed to compute DELTA("q", "a") [2]. Since the array PI + * has only m entries, whereas DELTA has O(m|SIGMA|) entries, we + * save a factor of |SIGMA| in the preprocessing time by computing + * PI rather than DELTA. + * + * [1] Cormen, Leiserson, Rivest, Stein + * Introdcution to Algorithms, 2nd Edition, MIT Press + * [2] See finite automation theory + */ + +#include +#include +#include +#include +#include + +struct ts_kmp +{ + u8 * pattern; + unsigned int pattern_len; + unsigned int prefix_tbl[0]; +}; + +static unsigned int kmp_find(struct ts_config *conf, struct ts_state *state) +{ + struct ts_kmp *kmp = ts_config_priv(conf); + unsigned int i, q = 0, text_len, consumed = state->offset; + const u8 *text; + + for (;;) { + text_len = conf->get_next_block(consumed, &text, conf, state); + + if (unlikely(text_len == 0)) + break; + + for (i = 0; i < text_len; i++) { + while (q > 0 && kmp->pattern[q] != text[i]) + q = kmp->prefix_tbl[q - 1]; + if (kmp->pattern[q] == text[i]) + q++; + if (unlikely(q == kmp->pattern_len)) { + state->offset = consumed + i + 1; + return state->offset - kmp->pattern_len; + } + } + + consumed += text_len; + } + + return UINT_MAX; +} + +static inline void compute_prefix_tbl(const u8 *pattern, unsigned int len, + unsigned int *prefix_tbl) +{ + unsigned int k, q; + + for (k = 0, q = 1; q < len; q++) { + while (k > 0 && pattern[k] != pattern[q]) + k = prefix_tbl[k-1]; + if (pattern[k] == pattern[q]) + k++; + prefix_tbl[q] = k; + } +} + +static struct ts_config *kmp_init(const void *pattern, unsigned int len, + int gfp_mask) +{ + struct ts_config *conf; + struct ts_kmp *kmp; + unsigned int prefix_tbl_len = len * sizeof(unsigned int); + size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len; + + conf = alloc_ts_config(priv_size, gfp_mask); + if (IS_ERR(conf)) + return conf; + + kmp = ts_config_priv(conf); + kmp->pattern_len = len; + compute_prefix_tbl(pattern, len, kmp->prefix_tbl); + kmp->pattern = (u8 *) kmp->prefix_tbl + prefix_tbl_len; + memcpy(kmp->pattern, pattern, len); + + return conf; +} + +static void *kmp_get_pattern(struct ts_config *conf) +{ + struct ts_kmp *kmp = ts_config_priv(conf); + return kmp->pattern; +} + +static unsigned int kmp_get_pattern_len(struct ts_config *conf) +{ + struct ts_kmp *kmp = ts_config_priv(conf); + return kmp->pattern_len; +} + +static struct ts_ops kmp_ops = { + .name = "kmp", + .find = kmp_find, + .init = kmp_init, + .get_pattern = kmp_get_pattern, + .get_pattern_len = kmp_get_pattern_len, + .owner = THIS_MODULE, + .list = LIST_HEAD_INIT(kmp_ops.list) +}; + +static int __init init_kmp(void) +{ + return textsearch_register(&kmp_ops); +} + +static void __exit exit_kmp(void) +{ + textsearch_unregister(&kmp_ops); +} + +MODULE_LICENSE("GPL"); + +module_init(init_kmp); +module_exit(exit_kmp); -- cgit v1.2.3 From 6408f79cce401e1bfecf923e7156f84f96e021e3 Mon Sep 17 00:00:00 2001 From: Thomas Graf Date: Thu, 23 Jun 2005 20:59:16 -0700 Subject: [LIB]: Naive finite state machine based textsearch A finite state machine consists of n states (struct ts_fsm_token) representing the pattern as a finite automation. The data is read sequentially on a octet basis. Every state token specifies the number of recurrences and the type of value accepted which can be either a specific character or ctype based set of characters. The available type of recurrences include 1, (0|1), [0 n], and [1 n]. The algorithm differs between strict/non-strict mode specyfing whether the pattern has to start at the first octect. Strict mode is enabled by default and can be disabled by inserting TS_FSM_HEAD_IGNORE as the first token in the chain. The runtime performance of the algorithm should be around O(n), however while in strict mode the average runtime can be better. Signed-off-by: Thomas Graf Signed-off-by: David S. Miller --- include/linux/textsearch_fsm.h | 48 ++++++ lib/Kconfig | 11 ++ lib/Makefile | 1 + lib/ts_fsm.c | 338 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 398 insertions(+) create mode 100644 include/linux/textsearch_fsm.h create mode 100644 lib/ts_fsm.c (limited to 'lib') diff --git a/include/linux/textsearch_fsm.h b/include/linux/textsearch_fsm.h new file mode 100644 index 000000000000..fdfa078c66e5 --- /dev/null +++ b/include/linux/textsearch_fsm.h @@ -0,0 +1,48 @@ +#ifndef __LINUX_TEXTSEARCH_FSM_H +#define __LINUX_TEXTSEARCH_FSM_H + +#include + +enum { + TS_FSM_SPECIFIC, /* specific character */ + TS_FSM_WILDCARD, /* any character */ + TS_FSM_DIGIT, /* isdigit() */ + TS_FSM_XDIGIT, /* isxdigit() */ + TS_FSM_PRINT, /* isprint() */ + TS_FSM_ALPHA, /* isalpha() */ + TS_FSM_ALNUM, /* isalnum() */ + TS_FSM_ASCII, /* isascii() */ + TS_FSM_CNTRL, /* iscntrl() */ + TS_FSM_GRAPH, /* isgraph() */ + TS_FSM_LOWER, /* islower() */ + TS_FSM_UPPER, /* isupper() */ + TS_FSM_PUNCT, /* ispunct() */ + TS_FSM_SPACE, /* isspace() */ + __TS_FSM_TYPE_MAX, +}; +#define TS_FSM_TYPE_MAX (__TS_FSM_TYPE_MAX - 1) + +enum { + TS_FSM_SINGLE, /* 1 occurrence */ + TS_FSM_PERHAPS, /* 1 or 0 occurrence */ + TS_FSM_ANY, /* 0..n occurrences */ + TS_FSM_MULTI, /* 1..n occurrences */ + TS_FSM_HEAD_IGNORE, /* 0..n ignored occurrences at head */ + __TS_FSM_RECUR_MAX, +}; +#define TS_FSM_RECUR_MAX (__TS_FSM_RECUR_MAX - 1) + +/** + * struct ts_fsm_token - state machine token (state) + * @type: type of token + * @recur: number of recurrences + * @value: character value for TS_FSM_SPECIFIC + */ +struct ts_fsm_token +{ + __u16 type; + __u8 recur; + __u8 value; +}; + +#endif diff --git a/lib/Kconfig b/lib/Kconfig index 16b8fa2175e4..455833a9e31a 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -80,4 +80,15 @@ config TEXTSEARCH_KMP To compile this code as a module, choose M here: the module will be called ts_kmp. +config TEXTSEARCH_FSM + depends on TEXTSEARCH + tristate "Finite state machine" + help + Say Y here if you want to be able to search text using a + naive finite state machine approach implementing a subset + of regular expressions. + + To compile this code as a module, choose M here: the + module will be called ts_fsm. + endmenu diff --git a/lib/Makefile b/lib/Makefile index 6cdb10f312df..7f6eda449102 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -38,6 +38,7 @@ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ lib-$(CONFIG_TEXTSEARCH) += textsearch.o obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o +obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c new file mode 100644 index 000000000000..d27c0a072940 --- /dev/null +++ b/lib/ts_fsm.c @@ -0,0 +1,338 @@ +/* + * lib/ts_fsm.c A naive finite state machine text search approach + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + * + * Authors: Thomas Graf + * + * ========================================================================== + * + * A finite state machine consists of n states (struct ts_fsm_token) + * representing the pattern as a finite automation. The data is read + * sequentially on a octet basis. Every state token specifies the number + * of recurrences and the type of value accepted which can be either a + * specific character or ctype based set of characters. The available + * type of recurrences include 1, (0|1), [0 n], and [1 n]. + * + * The algorithm differs between strict/non-strict mode specyfing + * whether the pattern has to start at the first octect. Strict mode + * is enabled by default and can be disabled by inserting + * TS_FSM_HEAD_IGNORE as the first token in the chain. + * + * The runtime performance of the algorithm should be around O(n), + * however while in strict mode the average runtime can be better. + */ + +#include +#include +#include +#include +#include +#include +#include + +struct ts_fsm +{ + unsigned int ntokens; + struct ts_fsm_token tokens[0]; +}; + +/* other values derived from ctype.h */ +#define _A 0x100 /* ascii */ +#define _W 0x200 /* wildcard */ + +/* Map to _ctype flags and some magic numbers */ +static u16 token_map[TS_FSM_TYPE_MAX+1] = { + [TS_FSM_SPECIFIC] = 0, + [TS_FSM_WILDCARD] = _W, + [TS_FSM_CNTRL] = _C, + [TS_FSM_LOWER] = _L, + [TS_FSM_UPPER] = _U, + [TS_FSM_PUNCT] = _P, + [TS_FSM_SPACE] = _S, + [TS_FSM_DIGIT] = _D, + [TS_FSM_XDIGIT] = _D | _X, + [TS_FSM_ALPHA] = _U | _L, + [TS_FSM_ALNUM] = _U | _L | _D, + [TS_FSM_PRINT] = _P | _U | _L | _D | _SP, + [TS_FSM_GRAPH] = _P | _U | _L | _D, + [TS_FSM_ASCII] = _A, +}; + +static u16 token_lookup_tbl[256] = { +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 0- 3 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 4- 7 */ +_W|_A|_C, _W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C|_S, /* 8- 11 */ +_W|_A|_C|_S, _W|_A|_C|_S, _W|_A|_C, _W|_A|_C, /* 12- 15 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 16- 19 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 20- 23 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 24- 27 */ +_W|_A|_C, _W|_A|_C, _W|_A|_C, _W|_A|_C, /* 28- 31 */ +_W|_A|_S|_SP, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 32- 35 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 36- 39 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 40- 43 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 44- 47 */ +_W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 48- 51 */ +_W|_A|_D, _W|_A|_D, _W|_A|_D, _W|_A|_D, /* 52- 55 */ +_W|_A|_D, _W|_A|_D, _W|_A|_P, _W|_A|_P, /* 56- 59 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 60- 63 */ +_W|_A|_P, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, /* 64- 67 */ +_W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U|_X, _W|_A|_U, /* 68- 71 */ +_W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 72- 75 */ +_W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 76- 79 */ +_W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 80- 83 */ +_W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_U, /* 84- 87 */ +_W|_A|_U, _W|_A|_U, _W|_A|_U, _W|_A|_P, /* 88- 91 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_P, /* 92- 95 */ +_W|_A|_P, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, /* 96- 99 */ +_W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L|_X, _W|_A|_L, /* 100-103 */ +_W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 104-107 */ +_W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 108-111 */ +_W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 112-115 */ +_W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_L, /* 116-119 */ +_W|_A|_L, _W|_A|_L, _W|_A|_L, _W|_A|_P, /* 120-123 */ +_W|_A|_P, _W|_A|_P, _W|_A|_P, _W|_A|_C, /* 124-127 */ +_W, _W, _W, _W, /* 128-131 */ +_W, _W, _W, _W, /* 132-135 */ +_W, _W, _W, _W, /* 136-139 */ +_W, _W, _W, _W, /* 140-143 */ +_W, _W, _W, _W, /* 144-147 */ +_W, _W, _W, _W, /* 148-151 */ +_W, _W, _W, _W, /* 152-155 */ +_W, _W, _W, _W, /* 156-159 */ +_W|_S|_SP, _W|_P, _W|_P, _W|_P, /* 160-163 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 164-167 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 168-171 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 172-175 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 176-179 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 180-183 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 184-187 */ +_W|_P, _W|_P, _W|_P, _W|_P, /* 188-191 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 192-195 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 196-199 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 200-203 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 204-207 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 208-211 */ +_W|_U, _W|_U, _W|_U, _W|_P, /* 212-215 */ +_W|_U, _W|_U, _W|_U, _W|_U, /* 216-219 */ +_W|_U, _W|_U, _W|_U, _W|_L, /* 220-223 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 224-227 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 228-231 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 232-235 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 236-239 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 240-243 */ +_W|_L, _W|_L, _W|_L, _W|_P, /* 244-247 */ +_W|_L, _W|_L, _W|_L, _W|_L, /* 248-251 */ +_W|_L, _W|_L, _W|_L, _W|_L}; /* 252-255 */ + +static inline int match_token(struct ts_fsm_token *t, u8 d) +{ + if (t->type) + return (token_lookup_tbl[d] & t->type) != 0; + else + return t->value == d; +} + +static unsigned int fsm_find(struct ts_config *conf, struct ts_state *state) +{ + struct ts_fsm *fsm = ts_config_priv(conf); + struct ts_fsm_token *cur = NULL, *next; + unsigned int match_start, block_idx = 0, tok_idx; + unsigned block_len = 0, strict, consumed = state->offset; + const u8 *data; + +#define GET_NEXT_BLOCK() \ +({ consumed += block_idx; \ + block_idx = 0; \ + block_len = conf->get_next_block(consumed, &data, conf, state); }) + +#define TOKEN_MISMATCH() \ + do { \ + if (strict) \ + goto no_match; \ + block_idx++; \ + goto startover; \ + } while(0) + +#define end_of_data() unlikely(block_idx >= block_len && !GET_NEXT_BLOCK()) + + if (end_of_data()) + goto no_match; + + strict = fsm->tokens[0].recur != TS_FSM_HEAD_IGNORE; + +startover: + match_start = consumed + block_idx; + + for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) { + cur = &fsm->tokens[tok_idx]; + + if (likely(tok_idx < (fsm->ntokens - 1))) + next = &fsm->tokens[tok_idx + 1]; + else + next = NULL; + + switch (cur->recur) { + case TS_FSM_SINGLE: + if (end_of_data()) + goto no_match; + + if (!match_token(cur, data[block_idx])) + TOKEN_MISMATCH(); + break; + + case TS_FSM_PERHAPS: + if (end_of_data() || + !match_token(cur, data[block_idx])) + continue; + break; + + case TS_FSM_MULTI: + if (end_of_data()) + goto no_match; + + if (!match_token(cur, data[block_idx])) + TOKEN_MISMATCH(); + + block_idx++; + /* fall through */ + + case TS_FSM_ANY: + if (next == NULL) + goto found_match; + + if (end_of_data()) + continue; + + while (!match_token(next, data[block_idx])) { + if (!match_token(cur, data[block_idx])) + TOKEN_MISMATCH(); + block_idx++; + if (end_of_data()) + goto no_match; + } + continue; + + /* + * Optimization: Prefer small local loop over jumping + * back and forth until garbage at head is munched. + */ + case TS_FSM_HEAD_IGNORE: + if (end_of_data()) + continue; + + while (!match_token(next, data[block_idx])) { + /* + * Special case, don't start over upon + * a mismatch, give the user the + * chance to specify the type of data + * allowed to be ignored. + */ + if (!match_token(cur, data[block_idx])) + goto no_match; + + block_idx++; + if (end_of_data()) + goto no_match; + } + + match_start = consumed + block_idx; + continue; + } + + block_idx++; + } + + if (end_of_data()) + goto found_match; + +no_match: + return UINT_MAX; + +found_match: + state->offset = consumed + block_idx; + return match_start; +} + +static struct ts_config *fsm_init(const void *pattern, unsigned int len, + int gfp_mask) +{ + int i, err = -EINVAL; + struct ts_config *conf; + struct ts_fsm *fsm; + struct ts_fsm_token *tokens = (struct ts_fsm_token *) pattern; + unsigned int ntokens = len / sizeof(*tokens); + size_t priv_size = sizeof(*fsm) + len; + + if (len % sizeof(struct ts_fsm_token) || ntokens < 1) + goto errout; + + for (i = 0; i < ntokens; i++) { + struct ts_fsm_token *t = &tokens[i]; + + if (t->type > TS_FSM_TYPE_MAX || t->recur > TS_FSM_RECUR_MAX) + goto errout; + + if (t->recur == TS_FSM_HEAD_IGNORE && + (i != 0 || i == (ntokens - 1))) + goto errout; + } + + conf = alloc_ts_config(priv_size, gfp_mask); + if (IS_ERR(conf)) + return conf; + + fsm = ts_config_priv(conf); + fsm->ntokens = ntokens; + memcpy(fsm->tokens, pattern, len); + + for (i = 0; i < fsm->ntokens; i++) { + struct ts_fsm_token *t = &fsm->tokens[i]; + t->type = token_map[t->type]; + } + + return conf; + +errout: + return ERR_PTR(err); +} + +static void *fsm_get_pattern(struct ts_config *conf) +{ + struct ts_fsm *fsm = ts_config_priv(conf); + return fsm->tokens; +} + +static unsigned int fsm_get_pattern_len(struct ts_config *conf) +{ + struct ts_fsm *fsm = ts_config_priv(conf); + return fsm->ntokens * sizeof(struct ts_fsm_token); +} + +static struct ts_ops fsm_ops = { + .name = "fsm", + .find = fsm_find, + .init = fsm_init, + .get_pattern = fsm_get_pattern, + .get_pattern_len = fsm_get_pattern_len, + .owner = THIS_MODULE, + .list = LIST_HEAD_INIT(fsm_ops.list) +}; + +static int __init init_fsm(void) +{ + return textsearch_register(&fsm_ops); +} + +static void __exit exit_fsm(void) +{ + textsearch_unregister(&fsm_ops); +} + +MODULE_LICENSE("GPL"); + +module_init(init_fsm); +module_exit(exit_fsm); -- cgit v1.2.3 From 65df877ab2e2328a4704af218efaed0a45176c86 Mon Sep 17 00:00:00 2001 From: "David S. Miller" Date: Thu, 23 Jun 2005 23:49:52 -0700 Subject: [LIB]: textsearch.o needs to be obj-y not lib-y. It exports symbols. Signed-off-by: David S. Miller --- lib/Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 7f6eda449102..beed1585294c 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -36,7 +36,7 @@ obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ -lib-$(CONFIG_TEXTSEARCH) += textsearch.o +obj-$(CONFIG_TEXTSEARCH) += textsearch.o obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o obj-$(CONFIG_TEXTSEARCH_FSM) += ts_fsm.o -- cgit v1.2.3 From f7704347a74fceaf79c89f8b8dbdd0111013e4d6 Mon Sep 17 00:00:00 2001 From: "David S. Miller" Date: Fri, 24 Jun 2005 17:39:03 -0700 Subject: [PKT_SCHED]: Make TEXTSEARCH* options only selected. Do not present these confusing new options to the user unless he picked some facility that makes use of it, such as NET_EMATCH_TEXT. Signed-off-by: David S. Miller --- lib/Kconfig | 28 ++++++---------------------- net/sched/Kconfig | 5 +++-- 2 files changed, 9 insertions(+), 24 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 455833a9e31a..eeb429a52152 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -63,32 +63,16 @@ config REED_SOLOMON_ENC16 config REED_SOLOMON_DEC16 boolean +# +# Textsearch support is select'ed if needed +# config TEXTSEARCH - boolean "Textsearch infrastructure" - default y - help - Say Y here if you want to provide a textsearch infrastructure - to other subsystems. + boolean config TEXTSEARCH_KMP - depends on TEXTSEARCH - tristate "Knuth-Morris-Pratt" - help - Say Y here if you want to be able to search text using the - Knuth-Morris-Pratt textsearch algorithm. - - To compile this code as a module, choose M here: the - module will be called ts_kmp. + tristate config TEXTSEARCH_FSM - depends on TEXTSEARCH - tristate "Finite state machine" - help - Say Y here if you want to be able to search text using a - naive finite state machine approach implementing a subset - of regular expressions. - - To compile this code as a module, choose M here: the - module will be called ts_fsm. + tristate endmenu diff --git a/net/sched/Kconfig b/net/sched/Kconfig index 447b89e556b1..7bac249258e3 100644 --- a/net/sched/Kconfig +++ b/net/sched/Kconfig @@ -453,10 +453,11 @@ config NET_EMATCH_TEXT tristate "Textsearch" depends on NET_EMATCH select TEXTSEARCH + select TEXTSEARCH_KMP + select TEXTSEARCH_FSM ---help--- Say Y here if you want to be ablt to classify packets based on - textsearch comparisons. Please select the appropriate textsearch - algorithms in the Library section. + textsearch comparisons. To compile this code as a module, choose M here: the module will be called em_text. -- cgit v1.2.3 From 23712b2fbf6b845289c1d41d929be0931fab2759 Mon Sep 17 00:00:00 2001 From: Domen Puncer Date: Sat, 25 Jun 2005 14:58:58 -0700 Subject: [PATCH] lib/sha1.c: fix sparse warning lib/sha1.c:44:10: warning: cast to restricted type Signed-off-by: Alexey Dobriyan Signed-off-by: Domen Puncer Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/sha1.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/sha1.c b/lib/sha1.c index 2f7f1148dfde..1cdabe3065f9 100644 --- a/lib/sha1.c +++ b/lib/sha1.c @@ -41,7 +41,7 @@ void sha_transform(__u32 *digest, const char *in, __u32 *W) __u32 a, b, c, d, e, t, i; for (i = 0; i < 16; i++) - W[i] = be32_to_cpu(((const __u32 *)in)[i]); + W[i] = be32_to_cpu(((const __be32 *)in)[i]); for (i = 0; i < 64; i++) W[i+16] = rol32(W[i+13] ^ W[i+8] ^ W[i+2] ^ W[i], 1); -- cgit v1.2.3 From 8c0e33c133021ee241e9d51255b9fb18eb34ef0e Mon Sep 17 00:00:00 2001 From: Nick Wilson Date: Sat, 25 Jun 2005 14:59:00 -0700 Subject: [PATCH] Use ALIGN to remove duplicate code This patch makes use of ALIGN() to remove duplicate round-up code. Signed-off-by: Nick Wilson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/a.out.h | 2 +- kernel/resource.c | 2 +- lib/bitmap.c | 3 +-- mm/bootmem.c | 6 +++--- 4 files changed, 6 insertions(+), 7 deletions(-) (limited to 'lib') diff --git a/include/linux/a.out.h b/include/linux/a.out.h index af8a1dfa5c32..f913cc3e1b0d 100644 --- a/include/linux/a.out.h +++ b/include/linux/a.out.h @@ -138,7 +138,7 @@ enum machine_type { #endif #endif -#define _N_SEGMENT_ROUND(x) (((x) + SEGMENT_SIZE - 1) & ~(SEGMENT_SIZE - 1)) +#define _N_SEGMENT_ROUND(x) ALIGN(x, SEGMENT_SIZE) #define _N_TXTENDADDR(x) (N_TXTADDR(x)+(x).a_text) diff --git a/kernel/resource.c b/kernel/resource.c index 52f696f11adf..26967e042201 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -263,7 +263,7 @@ static int find_resource(struct resource *root, struct resource *new, new->start = min; if (new->end > max) new->end = max; - new->start = (new->start + align - 1) & ~(align - 1); + new->start = ALIGN(new->start, align); if (alignf) alignf(alignf_data, new, size, align); if (new->start < new->end && new->end - new->start >= size - 1) { diff --git a/lib/bitmap.c b/lib/bitmap.c index d1388a5ce89c..fb9371fdd44a 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -289,7 +289,6 @@ EXPORT_SYMBOL(__bitmap_weight); #define CHUNKSZ 32 #define nbits_to_hold_value(val) fls(val) -#define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1)) #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10)) #define BASEDEC 10 /* fancier cpuset lists input in decimal */ @@ -316,7 +315,7 @@ int bitmap_scnprintf(char *buf, unsigned int buflen, if (chunksz == 0) chunksz = CHUNKSZ; - i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ; + i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ; for (; i >= 0; i -= CHUNKSZ) { chunkmask = ((1ULL << chunksz) - 1); word = i / BITS_PER_LONG; diff --git a/mm/bootmem.c b/mm/bootmem.c index 45275f1f8947..c1330cc19783 100644 --- a/mm/bootmem.c +++ b/mm/bootmem.c @@ -65,7 +65,7 @@ static unsigned long __init init_bootmem_core (pg_data_t *pgdat, pgdat->pgdat_next = pgdat_list; pgdat_list = pgdat; - mapsize = (mapsize + (sizeof(long) - 1UL)) & ~(sizeof(long) - 1UL); + mapsize = ALIGN(mapsize, sizeof(long)); bdata->node_bootmem_map = phys_to_virt(mapstart << PAGE_SHIFT); bdata->node_boot_start = (start << PAGE_SHIFT); bdata->node_low_pfn = end; @@ -186,7 +186,7 @@ __alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size, } else preferred = 0; - preferred = ((preferred + align - 1) & ~(align - 1)) >> PAGE_SHIFT; + preferred = ALIGN(preferred, align) >> PAGE_SHIFT; preferred += offset; areasize = (size+PAGE_SIZE-1)/PAGE_SIZE; incr = align >> PAGE_SHIFT ? : 1; @@ -227,7 +227,7 @@ found: */ if (align < PAGE_SIZE && bdata->last_offset && bdata->last_pos+1 == start) { - offset = (bdata->last_offset+align-1) & ~(align-1); + offset = ALIGN(bdata->last_offset, align); BUG_ON(offset > PAGE_SIZE); remaining_size = PAGE_SIZE-offset; if (size < remaining_size) { -- cgit v1.2.3