From 5db53f3e80dee2d9dff5e534f9e9fe1db17c9936 Mon Sep 17 00:00:00 2001 From: Joern Engel Date: Fri, 20 Nov 2009 20:13:39 +0100 Subject: [LogFS] add new flash file system This is a new flash file system. See Documentation/filesystems/logfs.txt Signed-off-by: Joern Engel --- lib/Kconfig | 3 + lib/Makefile | 1 + lib/btree.c | 797 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 801 insertions(+) create mode 100644 lib/btree.c (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index bb1326d3839c..277fbfb233b9 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -156,6 +156,9 @@ config TEXTSEARCH_BM config TEXTSEARCH_FSM tristate +config BTREE + boolean + config HAS_IOMEM boolean depends on !NO_IOMEM diff --git a/lib/Makefile b/lib/Makefile index 2e78277eff9d..cff82612e98b 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -41,6 +41,7 @@ lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o +obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o diff --git a/lib/btree.c b/lib/btree.c new file mode 100644 index 000000000000..41859a820218 --- /dev/null +++ b/lib/btree.c @@ -0,0 +1,797 @@ +/* + * lib/btree.c - Simple In-memory B+Tree + * + * As should be obvious for Linux kernel code, license is GPLv2 + * + * Copyright (c) 2007-2008 Joern Engel + * Bits and pieces stolen from Peter Zijlstra's code, which is + * Copyright 2007, Red Hat Inc. Peter Zijlstra + * GPLv2 + * + * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch + * + * A relatively simple B+Tree implementation. I have written it as a learning + * excercise to understand how B+Trees work. Turned out to be useful as well. + * + * B+Trees can be used similar to Linux radix trees (which don't have anything + * in common with textbook radix trees, beware). Prerequisite for them working + * well is that access to a random tree node is much faster than a large number + * of operations within each node. + * + * Disks have fulfilled the prerequisite for a long time. More recently DRAM + * has gained similar properties, as memory access times, when measured in cpu + * cycles, have increased. Cacheline sizes have increased as well, which also + * helps B+Trees. + * + * Compared to radix trees, B+Trees are more efficient when dealing with a + * sparsely populated address space. Between 25% and 50% of the memory is + * occupied with valid pointers. When densely populated, radix trees contain + * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2% + * pointers. + * + * This particular implementation stores pointers identified by a long value. + * Storing NULL pointers is illegal, lookup will return NULL when no entry + * was found. + * + * A tricks was used that is not commonly found in textbooks. The lowest + * values are to the right, not to the left. All used slots within a node + * are on the left, all unused slots contain NUL values. Most operations + * simply loop once over all slots and terminate on the first NUL. + */ + +#include +#include +#include +#include +#include + +#define MAX(a, b) ((a) > (b) ? (a) : (b)) +#define NODESIZE MAX(L1_CACHE_BYTES, 128) + +struct btree_geo { + int keylen; + int no_pairs; + int no_longs; +}; + +struct btree_geo btree_geo32 = { + .keylen = 1, + .no_pairs = NODESIZE / sizeof(long) / 2, + .no_longs = NODESIZE / sizeof(long) / 2, +}; +EXPORT_SYMBOL_GPL(btree_geo32); + +#define LONG_PER_U64 (64 / BITS_PER_LONG) +struct btree_geo btree_geo64 = { + .keylen = LONG_PER_U64, + .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64), + .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)), +}; +EXPORT_SYMBOL_GPL(btree_geo64); + +struct btree_geo btree_geo128 = { + .keylen = 2 * LONG_PER_U64, + .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64), + .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)), +}; +EXPORT_SYMBOL_GPL(btree_geo128); + +static struct kmem_cache *btree_cachep; + +void *btree_alloc(gfp_t gfp_mask, void *pool_data) +{ + return kmem_cache_alloc(btree_cachep, gfp_mask); +} +EXPORT_SYMBOL_GPL(btree_alloc); + +void btree_free(void *element, void *pool_data) +{ + kmem_cache_free(btree_cachep, element); +} +EXPORT_SYMBOL_GPL(btree_free); + +static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp) +{ + unsigned long *node; + + node = mempool_alloc(head->mempool, gfp); + memset(node, 0, NODESIZE); + return node; +} + +static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) { + if (l1[i] < l2[i]) + return -1; + if (l1[i] > l2[i]) + return 1; + } + return 0; +} + +static unsigned long *longcpy(unsigned long *dest, const unsigned long *src, + size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) + dest[i] = src[i]; + return dest; +} + +static unsigned long *longset(unsigned long *s, unsigned long c, size_t n) +{ + size_t i; + + for (i = 0; i < n; i++) + s[i] = c; + return s; +} + +static void dec_key(struct btree_geo *geo, unsigned long *key) +{ + unsigned long val; + int i; + + for (i = geo->keylen - 1; i >= 0; i--) { + val = key[i]; + key[i] = val - 1; + if (val) + break; + } +} + +static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n) +{ + return &node[n * geo->keylen]; +} + +static void *bval(struct btree_geo *geo, unsigned long *node, int n) +{ + return (void *)node[geo->no_longs + n]; +} + +static void setkey(struct btree_geo *geo, unsigned long *node, int n, + unsigned long *key) +{ + longcpy(bkey(geo, node, n), key, geo->keylen); +} + +static void setval(struct btree_geo *geo, unsigned long *node, int n, + void *val) +{ + node[geo->no_longs + n] = (unsigned long) val; +} + +static void clearpair(struct btree_geo *geo, unsigned long *node, int n) +{ + longset(bkey(geo, node, n), 0, geo->keylen); + node[geo->no_longs + n] = 0; +} + +static inline void __btree_init(struct btree_head *head) +{ + head->node = NULL; + head->height = 0; +} + +void btree_init_mempool(struct btree_head *head, mempool_t *mempool) +{ + __btree_init(head); + head->mempool = mempool; +} +EXPORT_SYMBOL_GPL(btree_init_mempool); + +int btree_init(struct btree_head *head) +{ + __btree_init(head); + head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); + if (!head->mempool) + return -ENOMEM; + return 0; +} +EXPORT_SYMBOL_GPL(btree_init); + +void btree_destroy(struct btree_head *head) +{ + mempool_destroy(head->mempool); + head->mempool = NULL; +} +EXPORT_SYMBOL_GPL(btree_destroy); + +void *btree_last(struct btree_head *head, struct btree_geo *geo, + unsigned long *key) +{ + int height = head->height; + unsigned long *node = head->node; + + if (height == 0) + return NULL; + + for ( ; height > 1; height--) + node = bval(geo, node, 0); + + longcpy(key, bkey(geo, node, 0), geo->keylen); + return bval(geo, node, 0); +} +EXPORT_SYMBOL_GPL(btree_last); + +static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, + unsigned long *key) +{ + return longcmp(bkey(geo, node, pos), key, geo->keylen); +} + +static int keyzero(struct btree_geo *geo, unsigned long *key) +{ + int i; + + for (i = 0; i < geo->keylen; i++) + if (key[i]) + return 0; + + return 1; +} + +void *btree_lookup(struct btree_head *head, struct btree_geo *geo, + unsigned long *key) +{ + int i, height = head->height; + unsigned long *node = head->node; + + if (height == 0) + return NULL; + + for ( ; height > 1; height--) { + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) <= 0) + break; + if (i == geo->no_pairs) + return NULL; + node = bval(geo, node, i); + if (!node) + return NULL; + } + + if (!node) + return NULL; + + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) == 0) + return bval(geo, node, i); + return NULL; +} +EXPORT_SYMBOL_GPL(btree_lookup); + +int btree_update(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, void *val) +{ + int i, height = head->height; + unsigned long *node = head->node; + + if (height == 0) + return -ENOENT; + + for ( ; height > 1; height--) { + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) <= 0) + break; + if (i == geo->no_pairs) + return -ENOENT; + node = bval(geo, node, i); + if (!node) + return -ENOENT; + } + + if (!node) + return -ENOENT; + + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) == 0) { + setval(geo, node, i, val); + return 0; + } + return -ENOENT; +} +EXPORT_SYMBOL_GPL(btree_update); + +/* + * Usually this function is quite similar to normal lookup. But the key of + * a parent node may be smaller than the smallest key of all its siblings. + * In such a case we cannot just return NULL, as we have only proven that no + * key smaller than __key, but larger than this parent key exists. + * So we set __key to the parent key and retry. We have to use the smallest + * such parent key, which is the last parent key we encountered. + */ +void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, + unsigned long *__key) +{ + int i, height; + unsigned long *node, *oldnode; + unsigned long *retry_key = NULL, key[geo->keylen]; + + if (keyzero(geo, __key)) + return NULL; + + if (head->height == 0) + return NULL; +retry: + longcpy(key, __key, geo->keylen); + dec_key(geo, key); + + node = head->node; + for (height = head->height ; height > 1; height--) { + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) <= 0) + break; + if (i == geo->no_pairs) + goto miss; + oldnode = node; + node = bval(geo, node, i); + if (!node) + goto miss; + retry_key = bkey(geo, oldnode, i); + } + + if (!node) + goto miss; + + for (i = 0; i < geo->no_pairs; i++) { + if (keycmp(geo, node, i, key) <= 0) { + if (bval(geo, node, i)) { + longcpy(__key, bkey(geo, node, i), geo->keylen); + return bval(geo, node, i); + } else + goto miss; + } + } +miss: + if (retry_key) { + __key = retry_key; + retry_key = NULL; + goto retry; + } + return NULL; +} + +static int getpos(struct btree_geo *geo, unsigned long *node, + unsigned long *key) +{ + int i; + + for (i = 0; i < geo->no_pairs; i++) { + if (keycmp(geo, node, i, key) <= 0) + break; + } + return i; +} + +static int getfill(struct btree_geo *geo, unsigned long *node, int start) +{ + int i; + + for (i = start; i < geo->no_pairs; i++) + if (!bval(geo, node, i)) + break; + return i; +} + +/* + * locate the correct leaf node in the btree + */ +static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, int level) +{ + unsigned long *node = head->node; + int i, height; + + for (height = head->height; height > level; height--) { + for (i = 0; i < geo->no_pairs; i++) + if (keycmp(geo, node, i, key) <= 0) + break; + + if ((i == geo->no_pairs) || !bval(geo, node, i)) { + /* right-most key is too large, update it */ + /* FIXME: If the right-most key on higher levels is + * always zero, this wouldn't be necessary. */ + i--; + setkey(geo, node, i, key); + } + BUG_ON(i < 0); + node = bval(geo, node, i); + } + BUG_ON(!node); + return node; +} + +static int btree_grow(struct btree_head *head, struct btree_geo *geo, + gfp_t gfp) +{ + unsigned long *node; + int fill; + + node = btree_node_alloc(head, gfp); + if (!node) + return -ENOMEM; + if (head->node) { + fill = getfill(geo, head->node, 0); + setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); + setval(geo, node, 0, head->node); + } + head->node = node; + head->height++; + return 0; +} + +static void btree_shrink(struct btree_head *head, struct btree_geo *geo) +{ + unsigned long *node; + int fill; + + if (head->height <= 1) + return; + + node = head->node; + fill = getfill(geo, node, 0); + BUG_ON(fill > 1); + head->node = bval(geo, node, 0); + head->height--; + mempool_free(node, head->mempool); +} + +static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, void *val, int level, + gfp_t gfp) +{ + unsigned long *node; + int i, pos, fill, err; + + BUG_ON(!val); + if (head->height < level) { + err = btree_grow(head, geo, gfp); + if (err) + return err; + } + +retry: + node = find_level(head, geo, key, level); + pos = getpos(geo, node, key); + fill = getfill(geo, node, pos); + /* two identical keys are not allowed */ + BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); + + if (fill == geo->no_pairs) { + /* need to split node */ + unsigned long *new; + + new = btree_node_alloc(head, gfp); + if (!new) + return -ENOMEM; + err = btree_insert_level(head, geo, + bkey(geo, node, fill / 2 - 1), + new, level + 1, gfp); + if (err) { + mempool_free(new, head->mempool); + return err; + } + for (i = 0; i < fill / 2; i++) { + setkey(geo, new, i, bkey(geo, node, i)); + setval(geo, new, i, bval(geo, node, i)); + setkey(geo, node, i, bkey(geo, node, i + fill / 2)); + setval(geo, node, i, bval(geo, node, i + fill / 2)); + clearpair(geo, node, i + fill / 2); + } + if (fill & 1) { + setkey(geo, node, i, bkey(geo, node, fill - 1)); + setval(geo, node, i, bval(geo, node, fill - 1)); + clearpair(geo, node, fill - 1); + } + goto retry; + } + BUG_ON(fill >= geo->no_pairs); + + /* shift and insert */ + for (i = fill; i > pos; i--) { + setkey(geo, node, i, bkey(geo, node, i - 1)); + setval(geo, node, i, bval(geo, node, i - 1)); + } + setkey(geo, node, pos, key); + setval(geo, node, pos, val); + + return 0; +} + +int btree_insert(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, void *val, gfp_t gfp) +{ + return btree_insert_level(head, geo, key, val, 1, gfp); +} +EXPORT_SYMBOL_GPL(btree_insert); + +static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, int level); +static void merge(struct btree_head *head, struct btree_geo *geo, int level, + unsigned long *left, int lfill, + unsigned long *right, int rfill, + unsigned long *parent, int lpos) +{ + int i; + + for (i = 0; i < rfill; i++) { + /* Move all keys to the left */ + setkey(geo, left, lfill + i, bkey(geo, right, i)); + setval(geo, left, lfill + i, bval(geo, right, i)); + } + /* Exchange left and right child in parent */ + setval(geo, parent, lpos, right); + setval(geo, parent, lpos + 1, left); + /* Remove left (formerly right) child from parent */ + btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1); + mempool_free(right, head->mempool); +} + +static void rebalance(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, int level, unsigned long *child, int fill) +{ + unsigned long *parent, *left = NULL, *right = NULL; + int i, no_left, no_right; + + if (fill == 0) { + /* Because we don't steal entries from a neigbour, this case + * can happen. Parent node contains a single child, this + * node, so merging with a sibling never happens. + */ + btree_remove_level(head, geo, key, level + 1); + mempool_free(child, head->mempool); + return; + } + + parent = find_level(head, geo, key, level + 1); + i = getpos(geo, parent, key); + BUG_ON(bval(geo, parent, i) != child); + + if (i > 0) { + left = bval(geo, parent, i - 1); + no_left = getfill(geo, left, 0); + if (fill + no_left <= geo->no_pairs) { + merge(head, geo, level, + left, no_left, + child, fill, + parent, i - 1); + return; + } + } + if (i + 1 < getfill(geo, parent, i)) { + right = bval(geo, parent, i + 1); + no_right = getfill(geo, right, 0); + if (fill + no_right <= geo->no_pairs) { + merge(head, geo, level, + child, fill, + right, no_right, + parent, i); + return; + } + } + /* + * We could also try to steal one entry from the left or right + * neighbor. By not doing so we changed the invariant from + * "all nodes are at least half full" to "no two neighboring + * nodes can be merged". Which means that the average fill of + * all nodes is still half or better. + */ +} + +static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, + unsigned long *key, int level) +{ + unsigned long *node; + int i, pos, fill; + void *ret; + + if (level > head->height) { + /* we recursed all the way up */ + head->height = 0; + head->node = NULL; + return NULL; + } + + node = find_level(head, geo, key, level); + pos = getpos(geo, node, key); + fill = getfill(geo, node, pos); + if ((level == 1) && (keycmp(geo, node, pos, key) != 0)) + return NULL; + ret = bval(geo, node, pos); + + /* remove and shift */ + for (i = pos; i < fill - 1; i++) { + setkey(geo, node, i, bkey(geo, node, i + 1)); + setval(geo, node, i, bval(geo, node, i + 1)); + } + clearpair(geo, node, fill - 1); + + if (fill - 1 < geo->no_pairs / 2) { + if (level < head->height) + rebalance(head, geo, key, level, node, fill - 1); + else if (fill - 1 == 1) + btree_shrink(head, geo); + } + + return ret; +} + +void *btree_remove(struct btree_head *head, struct btree_geo *geo, + unsigned long *key) +{ + if (head->height == 0) + return NULL; + + return btree_remove_level(head, geo, key, 1); +} +EXPORT_SYMBOL_GPL(btree_remove); + +int btree_merge(struct btree_head *target, struct btree_head *victim, + struct btree_geo *geo, gfp_t gfp) +{ + unsigned long key[geo->keylen]; + unsigned long dup[geo->keylen]; + void *val; + int err; + + BUG_ON(target == victim); + + if (!(target->node)) { + /* target is empty, just copy fields over */ + target->node = victim->node; + target->height = victim->height; + __btree_init(victim); + return 0; + } + + /* TODO: This needs some optimizations. Currently we do three tree + * walks to remove a single object from the victim. + */ + for (;;) { + if (!btree_last(victim, geo, key)) + break; + val = btree_lookup(victim, geo, key); + err = btree_insert(target, geo, key, val, gfp); + if (err) + return err; + /* We must make a copy of the key, as the original will get + * mangled inside btree_remove. */ + longcpy(dup, key, geo->keylen); + btree_remove(victim, geo, dup); + } + return 0; +} +EXPORT_SYMBOL_GPL(btree_merge); + +static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, + unsigned long *node, unsigned long opaque, + void (*func)(void *elem, unsigned long opaque, + unsigned long *key, size_t index, + void *func2), + void *func2, int reap, int height, size_t count) +{ + int i; + unsigned long *child; + + for (i = 0; i < geo->no_pairs; i++) { + child = bval(geo, node, i); + if (!child) + break; + if (height > 1) + count = __btree_for_each(head, geo, child, opaque, + func, func2, reap, height - 1, count); + else + func(child, opaque, bkey(geo, node, i), count++, + func2); + } + if (reap) + mempool_free(node, head->mempool); + return count; +} + +static void empty(void *elem, unsigned long opaque, unsigned long *key, + size_t index, void *func2) +{ +} + +void visitorl(void *elem, unsigned long opaque, unsigned long *key, + size_t index, void *__func) +{ + visitorl_t func = __func; + + func(elem, opaque, *key, index); +} +EXPORT_SYMBOL_GPL(visitorl); + +void visitor32(void *elem, unsigned long opaque, unsigned long *__key, + size_t index, void *__func) +{ + visitor32_t func = __func; + u32 *key = (void *)__key; + + func(elem, opaque, *key, index); +} +EXPORT_SYMBOL_GPL(visitor32); + +void visitor64(void *elem, unsigned long opaque, unsigned long *__key, + size_t index, void *__func) +{ + visitor64_t func = __func; + u64 *key = (void *)__key; + + func(elem, opaque, *key, index); +} +EXPORT_SYMBOL_GPL(visitor64); + +void visitor128(void *elem, unsigned long opaque, unsigned long *__key, + size_t index, void *__func) +{ + visitor128_t func = __func; + u64 *key = (void *)__key; + + func(elem, opaque, key[0], key[1], index); +} +EXPORT_SYMBOL_GPL(visitor128); + +size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, + unsigned long opaque, + void (*func)(void *elem, unsigned long opaque, + unsigned long *key, + size_t index, void *func2), + void *func2) +{ + size_t count = 0; + + if (!func2) + func = empty; + if (head->node) + count = __btree_for_each(head, geo, head->node, opaque, func, + func2, 0, head->height, 0); + return count; +} +EXPORT_SYMBOL_GPL(btree_visitor); + +size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, + unsigned long opaque, + void (*func)(void *elem, unsigned long opaque, + unsigned long *key, + size_t index, void *func2), + void *func2) +{ + size_t count = 0; + + if (!func2) + func = empty; + if (head->node) + count = __btree_for_each(head, geo, head->node, opaque, func, + func2, 1, head->height, 0); + __btree_init(head); + return count; +} +EXPORT_SYMBOL_GPL(btree_grim_visitor); + +static int __init btree_module_init(void) +{ + btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0, + SLAB_HWCACHE_ALIGN, NULL); + return 0; +} + +static void __exit btree_module_exit(void) +{ + kmem_cache_destroy(btree_cachep); +} + +/* If core code starts using btree, initialization should happen even earlier */ +module_init(btree_module_init); +module_exit(btree_module_exit); + +MODULE_AUTHOR("Joern Engel "); +MODULE_AUTHOR("Johannes Berg "); +MODULE_LICENSE("GPL"); -- cgit v1.2.3 From 39d997b514e12d5aff0dca206eb8996b3957927e Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Mon, 21 Dec 2009 16:20:16 -0800 Subject: x86, core: Optimize hweight32() Optimize hweight32 by using the same technique in hweight64. The proof of this technique can be found in the commit log for f9b4192923fa6e38331e88214b1fe5fc21583fcc ("bitops: hweight() speedup"). The userspace benchmark on x86_32 showed 20% speedup with bitmap_weight() which uses hweight32 to count bits for each unsigned long on 32bit architectures. int main(void) { #define SZ (1024 * 1024 * 512) static DECLARE_BITMAP(bitmap, SZ) = { [0 ... 100] = 1, }; return bitmap_weight(bitmap, SZ); } Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Cc: Linus Torvalds LKML-Reference: <1258603932-4590-1-git-send-email-akinobu.mita@gmail.com> [ only x86 sets ARCH_HAS_FAST_MULTIPLIER so we do this via the x86 tree] Signed-off-by: Ingo Molnar --- lib/hweight.c | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib') diff --git a/lib/hweight.c b/lib/hweight.c index 389424ecb129..63ee4eb1228d 100644 --- a/lib/hweight.c +++ b/lib/hweight.c @@ -11,11 +11,18 @@ unsigned int hweight32(unsigned int w) { +#ifdef ARCH_HAS_FAST_MULTIPLIER + w -= (w >> 1) & 0x55555555; + w = (w & 0x33333333) + ((w >> 2) & 0x33333333); + w = (w + (w >> 4)) & 0x0f0f0f0f; + return (w * 0x01010101) >> 24; +#else unsigned int res = w - ((w >> 1) & 0x55555555); res = (res & 0x33333333) + ((res >> 2) & 0x33333333); res = (res + (res >> 4)) & 0x0F0F0F0F; res = res + (res >> 8); return (res + (res >> 16)) & 0x000000FF; +#endif } EXPORT_SYMBOL(hweight32); -- cgit v1.2.3 From bc7259a2ce764ea16200eb9e53f6e136e918d065 Mon Sep 17 00:00:00 2001 From: Joe Perches Date: Thu, 7 Jan 2010 11:43:50 +0000 Subject: lib/vsprintf.c: Add %pMF to format FDDI bit reversed MAC addresses On Mon, 2010-01-04 at 23:43 +0000, Maciej W. Rozycki wrote: > The example below shows an address, and the sequence of bits or symbols > that would be transmitted when the address is used in the Source Address > or Destination Address fields on the MAC header. The transmission line > shows the address bits in the order transmitted, from left to right. For > IEEE 802 LANs these correspond to actual bits on the medium. The FDDI > symbols line shows how the FDDI PHY sends the address bits as encoded > symbols. > > MSB: 35:7B:12:00:00:01 > Canonical: AC-DE-48-00-00-80 > Transmission: 00110101 01111011 00010010 00000000 00000000 00000001 > FDDI Symbols: 35 7B 12 00 00 01" > > Please note that this address has its group bit clear. > > This notation is also defined in the "FDDI MEDIA ACCESS CONTROL-2 > (MAC-2)" (X3T9/92-120) document although that book does not have a need > to use the MSB form and it's skipped. Adds 6 bytes to object size for x86 New: $ size lib/vsprintf.o text data bss dec hex filename 8664 0 2 8666 21da lib/vsprintf.o $ size lib/vsprintf.o text data bss dec hex filename 8658 0 2 8660 21d4 lib/vsprintf.o Signed-off-by: Joe Perches Signed-off-by: David S. Miller --- lib/vsprintf.c | 20 ++++++++++++++++++-- 1 file changed, 18 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index d4996cf46eb6..dc48d2b32ebd 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -25,6 +25,7 @@ #include #include #include +#include #include #include /* for PAGE_SIZE */ @@ -681,11 +682,21 @@ static char *mac_address_string(char *buf, char *end, u8 *addr, char mac_addr[sizeof("xx:xx:xx:xx:xx:xx")]; char *p = mac_addr; int i; + bool bitrev; + char separator; + + if (fmt[1] == 'F') { /* FDDI canonical format */ + bitrev = true; + separator = '-'; + } else { + bitrev = false; + separator = ':'; + } for (i = 0; i < 6; i++) { - p = pack_hex_byte(p, addr[i]); + p = pack_hex_byte(p, bitrev ? bitrev8(addr[i]) : addr[i]); if (fmt[0] == 'M' && i != 5) - *p++ = ':'; + *p++ = separator; } *p = '\0'; @@ -896,6 +907,10 @@ static char *uuid_string(char *buf, char *end, const u8 *addr, * - 'M' For a 6-byte MAC address, it prints the address in the * usual colon-separated hex notation * - 'm' For a 6-byte MAC address, it prints the hex address without colons + * - 'MF' For a 6-byte MAC FDDI address, it prints the address + * with a dash-separated hex notation with bit reversed bytes + * - 'mF' For a 6-byte MAC FDDI address, it prints the address + * in hex notation without separators with bit reversed bytes * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) * IPv6 uses colon separated network-order 16 bit hex with leading 0's @@ -939,6 +954,7 @@ static char *pointer(const char *fmt, char *buf, char *end, void *ptr, return resource_string(buf, end, ptr, spec, fmt); case 'M': /* Colon separated: 00:01:02:03:04:05 */ case 'm': /* Contiguous: 000102030405 */ + /* [mM]F (FDDI, bit reversed) */ return mac_address_string(buf, end, ptr, spec, fmt); case 'I': /* Formatted IP supported * 4: 1.2.3.4 -- cgit v1.2.3 From c8e000604bce02a87742240a9b716a0f1b680c0b Mon Sep 17 00:00:00 2001 From: Joe Perches Date: Mon, 11 Jan 2010 00:44:14 -0800 Subject: lib: Kill bit-reversed FDDI MAC output case, it's bogus. Signed-off-by: Joe Perches Signed-off-by: David S. Miller --- lib/vsprintf.c | 10 ++-------- 1 file changed, 2 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index dc48d2b32ebd..e83e3e79a989 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -25,7 +25,6 @@ #include #include #include -#include #include #include /* for PAGE_SIZE */ @@ -682,19 +681,16 @@ static char *mac_address_string(char *buf, char *end, u8 *addr, char mac_addr[sizeof("xx:xx:xx:xx:xx:xx")]; char *p = mac_addr; int i; - bool bitrev; char separator; if (fmt[1] == 'F') { /* FDDI canonical format */ - bitrev = true; separator = '-'; } else { - bitrev = false; separator = ':'; } for (i = 0; i < 6; i++) { - p = pack_hex_byte(p, bitrev ? bitrev8(addr[i]) : addr[i]); + p = pack_hex_byte(p, addr[i]); if (fmt[0] == 'M' && i != 5) *p++ = separator; } @@ -908,9 +904,7 @@ static char *uuid_string(char *buf, char *end, const u8 *addr, * usual colon-separated hex notation * - 'm' For a 6-byte MAC address, it prints the hex address without colons * - 'MF' For a 6-byte MAC FDDI address, it prints the address - * with a dash-separated hex notation with bit reversed bytes - * - 'mF' For a 6-byte MAC FDDI address, it prints the address - * in hex notation without separators with bit reversed bytes + * with a dash-separated hex notation * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) * IPv6 uses colon separated network-order 16 bit hex with leading 0's -- cgit v1.2.3 From 0159f24ee764927bf44c1a25473bd4517febd21c Mon Sep 17 00:00:00 2001 From: Joe Perches Date: Wed, 13 Jan 2010 20:23:30 -0800 Subject: lib/vsprintf.c: Add IPV4 options %pI4[hnbl] for host, network, big and little endian This should allow the removal of the #defines and uses of NIPQUAD and NIPQUAD_FMT Signed-off-by: Joe Perches Signed-off-by: David S. Miller --- lib/vsprintf.c | 36 +++++++++++++++++++++++++++++++----- 1 file changed, 31 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index e83e3e79a989..add0446dd921 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -699,13 +699,37 @@ static char *mac_address_string(char *buf, char *end, u8 *addr, return string(buf, end, mac_addr, spec); } -static char *ip4_string(char *p, const u8 *addr, bool leading_zeros) +static char *ip4_string(char *p, const u8 *addr, const char *fmt) { int i; - + bool leading_zeros = (fmt[0] == 'i'); + int index; + int step; + + switch (fmt[2]) { + case 'h': +#ifdef __BIG_ENDIAN + index = 0; + step = 1; +#else + index = 3; + step = -1; +#endif + break; + case 'l': + index = 3; + step = -1; + break; + case 'n': + case 'b': + default: + index = 0; + step = 1; + break; + } for (i = 0; i < 4; i++) { char temp[3]; /* hold each IP quad in reverse order */ - int digits = put_dec_trunc(temp, addr[i]) - temp; + int digits = put_dec_trunc(temp, addr[index]) - temp; if (leading_zeros) { if (digits < 3) *p++ = '0'; @@ -717,6 +741,7 @@ static char *ip4_string(char *p, const u8 *addr, bool leading_zeros) *p++ = temp[digits]; if (i < 3) *p++ = '.'; + index += step; } *p = '\0'; @@ -796,7 +821,7 @@ static char *ip6_compressed_string(char *p, const char *addr) if (useIPv4) { if (needcolon) *p++ = ':'; - p = ip4_string(p, &in6.s6_addr[12], false); + p = ip4_string(p, &in6.s6_addr[12], "I4"); } *p = '\0'; @@ -836,7 +861,7 @@ static char *ip4_addr_string(char *buf, char *end, const u8 *addr, { char ip4_addr[sizeof("255.255.255.255")]; - ip4_string(ip4_addr, addr, fmt[0] == 'i'); + ip4_string(ip4_addr, addr, fmt); return string(buf, end, ip4_addr, spec); } @@ -911,6 +936,7 @@ static char *uuid_string(char *buf, char *end, const u8 *addr, * - 'i' [46] for 'raw' IPv4/IPv6 addresses * IPv6 omits the colons (01020304...0f) * IPv4 uses dot-separated decimal with leading 0's (010.123.045.006) + * - '[Ii]4[hnbl]' IPv4 addresses in host, network, big or little endian order * - 'I6c' for IPv6 addresses printed as specified by * http://www.ietf.org/id/draft-kawamura-ipv6-text-representation-03.txt * - 'U' For a 16 byte UUID/GUID, it prints the UUID/GUID in the form -- cgit v1.2.3 From d5f1fb53353edc38da326445267c1df0c9676df2 Mon Sep 17 00:00:00 2001 From: Li Zefan Date: Thu, 14 Jan 2010 10:53:55 +0800 Subject: lib: Introduce strnstr() It differs strstr() in that it limits the length to be searched in the first string. Signed-off-by: Li Zefan LKML-Reference: <4B4E8743.6030805@cn.fujitsu.com> Acked-by: Frederic Weisbecker Signed-off-by: Steven Rostedt --- include/linux/string.h | 5 ++++- lib/string.c | 27 ++++++++++++++++++++++++++- 2 files changed, 30 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/include/linux/string.h b/include/linux/string.h index 651839a2a755..a716ee2a8adb 100644 --- a/include/linux/string.h +++ b/include/linux/string.h @@ -72,7 +72,10 @@ static inline __must_check char *strstrip(char *str) } #ifndef __HAVE_ARCH_STRSTR -extern char * strstr(const char *,const char *); +extern char * strstr(const char *, const char *); +#endif +#ifndef __HAVE_ARCH_STRNSTR +extern char * strnstr(const char *, const char *, size_t); #endif #ifndef __HAVE_ARCH_STRLEN extern __kernel_size_t strlen(const char *); diff --git a/lib/string.c b/lib/string.c index 9f75b4ec50b8..a1cdcfcc42d0 100644 --- a/lib/string.c +++ b/lib/string.c @@ -667,7 +667,7 @@ EXPORT_SYMBOL(memscan); */ char *strstr(const char *s1, const char *s2) { - int l1, l2; + size_t l1, l2; l2 = strlen(s2); if (!l2) @@ -684,6 +684,31 @@ char *strstr(const char *s1, const char *s2) EXPORT_SYMBOL(strstr); #endif +#ifndef __HAVE_ARCH_STRNSTR +/** + * strnstr - Find the first substring in a length-limited string + * @s1: The string to be searched + * @s2: The string to search for + * @len: the maximum number of characters to search + */ +char *strnstr(const char *s1, const char *s2, size_t len) +{ + size_t l1 = len, l2; + + l2 = strlen(s2); + if (!l2) + return (char *)s1; + while (l1 >= l2) { + l1--; + if (!memcmp(s1, s2, l2)) + return (char *)s1; + s1++; + } + return NULL; +} +EXPORT_SYMBOL(strnstr); +#endif + #ifndef __HAVE_ARCH_MEMCHR /** * memchr - Find a character in an area of memory. -- cgit v1.2.3 From 4c54005ca438a8b46dd542b497d4f0dc2ca375e8 Mon Sep 17 00:00:00 2001 From: Paul E. McKenney Date: Thu, 14 Jan 2010 16:10:57 -0800 Subject: rcu: 1Q2010 update for RCU documentation Add expedited functions. Review documentation and update obsolete verbiage. Also fix the advice for the RCU CPU-stall kernel configuration parameter, and document RCU CPU-stall warnings. Signed-off-by: Paul E. McKenney Cc: laijs@cn.fujitsu.com Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: josh@joshtriplett.org Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: dhowells@redhat.com LKML-Reference: <12635142581866-git-send-email-> Signed-off-by: Ingo Molnar --- Documentation/RCU/00-INDEX | 8 +- Documentation/RCU/RTFP.txt | 58 +++++++- Documentation/RCU/checklist.txt | 200 ++++++++++++++++----------- Documentation/RCU/rcu.txt | 48 +------ Documentation/RCU/stallwarn.txt | 58 ++++++++ Documentation/RCU/torture.txt | 12 ++ Documentation/RCU/whatisRCU.txt | 3 +- Documentation/filesystems/dentry-locking.txt | 3 +- lib/Kconfig.debug | 4 +- 9 files changed, 258 insertions(+), 136 deletions(-) create mode 100644 Documentation/RCU/stallwarn.txt (limited to 'lib') diff --git a/Documentation/RCU/00-INDEX b/Documentation/RCU/00-INDEX index 9bb62f7b89c3..0a27ea9621fa 100644 --- a/Documentation/RCU/00-INDEX +++ b/Documentation/RCU/00-INDEX @@ -8,14 +8,18 @@ listRCU.txt - Using RCU to Protect Read-Mostly Linked Lists NMI-RCU.txt - Using RCU to Protect Dynamic NMI Handlers +rcubarrier.txt + - RCU and Unloadable Modules +rculist_nulls.txt + - RCU list primitives for use with SLAB_DESTROY_BY_RCU rcuref.txt - Reference-count design for elements of lists/arrays protected by RCU rcu.txt - RCU Concepts -rcubarrier.txt - - Unloading modules that use RCU callbacks RTFP.txt - List of RCU papers (bibliography) going back to 1980. +stallwarn.txt + - RCU CPU stall warnings (CONFIG_RCU_CPU_STALL_DETECTOR) torture.txt - RCU Torture Test Operation (CONFIG_RCU_TORTURE_TEST) trace.txt diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt index d2b85237c76e..5051209e6835 100644 --- a/Documentation/RCU/RTFP.txt +++ b/Documentation/RCU/RTFP.txt @@ -25,10 +25,10 @@ to be referencing the data structure. However, this mechanism was not optimized for modern computer systems, which is not surprising given that these overheads were not so expensive in the mid-80s. Nonetheless, passive serialization appears to be the first deferred-destruction -mechanism to be used in production. Furthermore, the relevant patent has -lapsed, so this approach may be used in non-GPL software, if desired. -(In contrast, use of RCU is permitted only in software licensed under -GPL. Sorry!!!) +mechanism to be used in production. Furthermore, the relevant patent +has lapsed, so this approach may be used in non-GPL software, if desired. +(In contrast, implementation of RCU is permitted only in software licensed +under either GPL or LGPL. Sorry!!!) In 1990, Pugh [Pugh90] noted that explicitly tracking which threads were reading a given data structure permitted deferred free to operate @@ -150,6 +150,18 @@ preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally, PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI]. +2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ], +a history of how Linux changed RCU more than RCU changed Linux +[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU +[PaulEMcKenney2008HierarchicalRCU]. + +2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU], +which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU] +[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made +its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU]. +The problem of resizeable RCU-protected hash tables may now be on a path +to a solution [JoshTriplett2009RPHash]. + Bibtex Entries @article{Kung80 @@ -730,6 +742,11 @@ Revised: " } +# +# "What is RCU?" LWN series. +# +######################################################################## + @article{DinakarGuniguntala2008IBMSysJ ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" @@ -820,3 +837,36 @@ Revised: Uniprocessor assumptions allow simplified RCU implementation. " } + +@unpublished{PaulEMcKenney2009expeditedRCU +,Author="Paul E. McKenney" +,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods" +,month="June" +,day="25" +,year="2009" +,note="Available: +\url{http://lkml.org/lkml/2009/6/25/306} +[Viewed August 16, 2009]" +,annotation=" + First posting of expedited RCU to be accepted into -tip. +" +} + +@unpublished{JoshTriplett2009RPHash +,Author="Josh Triplett" +,Title="Scalable concurrent hash tables via relativistic programming" +,month="September" +,year="2009" +,note="Linux Plumbers Conference presentation" +,annotation=" + RP fun with hash tables. +" +} + +@phdthesis{MathieuDesnoyersPhD +, title = "Low-impact Operating System Tracing" +, author = "Mathieu Desnoyers" +, school = "Ecole Polytechnique de Montr\'{e}al" +, month = "December" +, year = 2009 +} diff --git a/Documentation/RCU/checklist.txt b/Documentation/RCU/checklist.txt index 51525a30e8b4..767cf06a4276 100644 --- a/Documentation/RCU/checklist.txt +++ b/Documentation/RCU/checklist.txt @@ -8,13 +8,12 @@ would cause. This list is based on experiences reviewing such patches over a rather long period of time, but improvements are always welcome! 0. Is RCU being applied to a read-mostly situation? If the data - structure is updated more than about 10% of the time, then - you should strongly consider some other approach, unless - detailed performance measurements show that RCU is nonetheless - the right tool for the job. Yes, you might think of RCU - as simply cutting overhead off of the readers and imposing it - on the writers. That is exactly why normal uses of RCU will - do much more reading than updating. + structure is updated more than about 10% of the time, then you + should strongly consider some other approach, unless detailed + performance measurements show that RCU is nonetheless the right + tool for the job. Yes, RCU does reduce read-side overhead by + increasing write-side overhead, which is exactly why normal uses + of RCU will do much more reading than updating. Another exception is where performance is not an issue, and RCU provides a simpler implementation. An example of this situation @@ -35,13 +34,13 @@ over a rather long period of time, but improvements are always welcome! If you choose #b, be prepared to describe how you have handled memory barriers on weakly ordered machines (pretty much all of - them -- even x86 allows reads to be reordered), and be prepared - to explain why this added complexity is worthwhile. If you - choose #c, be prepared to explain how this single task does not - become a major bottleneck on big multiprocessor machines (for - example, if the task is updating information relating to itself - that other tasks can read, there by definition can be no - bottleneck). + them -- even x86 allows later loads to be reordered to precede + earlier stores), and be prepared to explain why this added + complexity is worthwhile. If you choose #c, be prepared to + explain how this single task does not become a major bottleneck on + big multiprocessor machines (for example, if the task is updating + information relating to itself that other tasks can read, there + by definition can be no bottleneck). 2. Do the RCU read-side critical sections make proper use of rcu_read_lock() and friends? These primitives are needed @@ -51,8 +50,10 @@ over a rather long period of time, but improvements are always welcome! actuarial risk of your kernel. As a rough rule of thumb, any dereference of an RCU-protected - pointer must be covered by rcu_read_lock() or rcu_read_lock_bh() - or by the appropriate update-side lock. + pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(), + rcu_read_lock_sched(), or by the appropriate update-side lock. + Disabling of preemption can serve as rcu_read_lock_sched(), but + is less readable. 3. Does the update code tolerate concurrent accesses? @@ -62,25 +63,27 @@ over a rather long period of time, but improvements are always welcome! of ways to handle this concurrency, depending on the situation: a. Use the RCU variants of the list and hlist update - primitives to add, remove, and replace elements on an - RCU-protected list. Alternatively, use the RCU-protected - trees that have been added to the Linux kernel. + primitives to add, remove, and replace elements on + an RCU-protected list. Alternatively, use the other + RCU-protected data structures that have been added to + the Linux kernel. This is almost always the best approach. b. Proceed as in (a) above, but also maintain per-element locks (that are acquired by both readers and writers) that guard per-element state. Of course, fields that - the readers refrain from accessing can be guarded by the - update-side lock. + the readers refrain from accessing can be guarded by + some other lock acquired only by updaters, if desired. This works quite well, also. c. Make updates appear atomic to readers. For example, - pointer updates to properly aligned fields will appear - atomic, as will individual atomic primitives. Operations - performed under a lock and sequences of multiple atomic - primitives will -not- appear to be atomic. + pointer updates to properly aligned fields will + appear atomic, as will individual atomic primitives. + Sequences of perations performed under a lock will -not- + appear to be atomic to RCU readers, nor will sequences + of multiple atomic primitives. This can work, but is starting to get a bit tricky. @@ -98,9 +101,9 @@ over a rather long period of time, but improvements are always welcome! a new structure containing updated values. 4. Weakly ordered CPUs pose special challenges. Almost all CPUs - are weakly ordered -- even i386 CPUs allow reads to be reordered. - RCU code must take all of the following measures to prevent - memory-corruption problems: + are weakly ordered -- even x86 CPUs allow later loads to be + reordered to precede earlier stores. RCU code must take all of + the following measures to prevent memory-corruption problems: a. Readers must maintain proper ordering of their memory accesses. The rcu_dereference() primitive ensures that @@ -113,14 +116,21 @@ over a rather long period of time, but improvements are always welcome! The rcu_dereference() primitive is also an excellent documentation aid, letting the person reading the code know exactly which pointers are protected by RCU. - - The rcu_dereference() primitive is used by the various - "_rcu()" list-traversal primitives, such as the - list_for_each_entry_rcu(). Note that it is perfectly - legal (if redundant) for update-side code to use - rcu_dereference() and the "_rcu()" list-traversal - primitives. This is particularly useful in code - that is common to readers and updaters. + Please note that compilers can also reorder code, and + they are becoming increasingly aggressive about doing + just that. The rcu_dereference() primitive therefore + also prevents destructive compiler optimizations. + + The rcu_dereference() primitive is used by the + various "_rcu()" list-traversal primitives, such + as the list_for_each_entry_rcu(). Note that it is + perfectly legal (if redundant) for update-side code to + use rcu_dereference() and the "_rcu()" list-traversal + primitives. This is particularly useful in code that + is common to readers and updaters. However, neither + rcu_dereference() nor the "_rcu()" list-traversal + primitives can substitute for a good concurrency design + coordinating among multiple updaters. b. If the list macros are being used, the list_add_tail_rcu() and list_add_rcu() primitives must be used in order @@ -135,11 +145,14 @@ over a rather long period of time, but improvements are always welcome! readers. Similarly, if the hlist macros are being used, the hlist_del_rcu() primitive is required. - The list_replace_rcu() primitive may be used to - replace an old structure with a new one in an - RCU-protected list. + The list_replace_rcu() and hlist_replace_rcu() primitives + may be used to replace an old structure with a new one + in their respective types of RCU-protected lists. + + d. Rules similar to (4b) and (4c) apply to the "hlist_nulls" + type of RCU-protected linked lists. - d. Updates must ensure that initialization of a given + e. Updates must ensure that initialization of a given structure happens before pointers to that structure are publicized. Use the rcu_assign_pointer() primitive when publicizing a pointer to a structure that can @@ -151,16 +164,31 @@ over a rather long period of time, but improvements are always welcome! it cannot block. 6. Since synchronize_rcu() can block, it cannot be called from - any sort of irq context. Ditto for synchronize_sched() and - synchronize_srcu(). - -7. If the updater uses call_rcu(), then the corresponding readers - must use rcu_read_lock() and rcu_read_unlock(). If the updater - uses call_rcu_bh(), then the corresponding readers must use - rcu_read_lock_bh() and rcu_read_unlock_bh(). If the updater - uses call_rcu_sched(), then the corresponding readers must - disable preemption. Mixing things up will result in confusion - and broken kernels. + any sort of irq context. The same rule applies for + synchronize_rcu_bh(), synchronize_sched(), synchronize_srcu(), + synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(), + synchronize_sched_expedite(), and synchronize_srcu_expedited(). + + The expedited forms of these primitives have the same semantics + as the non-expedited forms, but expediting is both expensive + and unfriendly to real-time workloads. Use of the expedited + primitives should be restricted to rare configuration-change + operations that would not normally be undertaken while a real-time + workload is running. + +7. If the updater uses call_rcu() or synchronize_rcu(), then the + corresponding readers must use rcu_read_lock() and + rcu_read_unlock(). If the updater uses call_rcu_bh() or + synchronize_rcu_bh(), then the corresponding readers must + use rcu_read_lock_bh() and rcu_read_unlock_bh(). If the + updater uses call_rcu_sched() or synchronize_sched(), then + the corresponding readers must disable preemption, possibly + by calling rcu_read_lock_sched() and rcu_read_unlock_sched(). + If the updater uses synchronize_srcu(), the the corresponding + readers must use srcu_read_lock() and srcu_read_unlock(), + and with the same srcu_struct. The rules for the expedited + primitives are the same as for their non-expedited counterparts. + Mixing things up will result in confusion and broken kernels. One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() @@ -212,6 +240,8 @@ over a rather long period of time, but improvements are always welcome! e. Periodically invoke synchronize_rcu(), permitting a limited number of updates per grace period. + The same cautions apply to call_rcu_bh() and call_rcu_sched(). + 9. All RCU list-traversal primitives, which include rcu_dereference(), list_for_each_entry_rcu(), list_for_each_continue_rcu(), and list_for_each_safe_rcu(), @@ -229,7 +259,8 @@ over a rather long period of time, but improvements are always welcome! 10. Conversely, if you are in an RCU read-side critical section, and you don't hold the appropriate update-side lock, you -must- use the "_rcu()" variants of the list macros. Failing to do so - will break Alpha and confuse people reading your code. + will break Alpha, cause aggressive compilers to generate bad code, + and confuse people trying to read your code. 11. Note that synchronize_rcu() -only- guarantees to wait until all currently executing rcu_read_lock()-protected RCU read-side @@ -239,15 +270,21 @@ over a rather long period of time, but improvements are always welcome! rcu_read_lock()-protected read-side critical sections, do -not- use synchronize_rcu(). - If you want to wait for some of these other things, you might - instead need to use synchronize_irq() or synchronize_sched(). + Similarly, disabling preemption is not an acceptable substitute + for rcu_read_lock(). Code that attempts to use preemption + disabling where it should be using rcu_read_lock() will break + in real-time kernel builds. + + If you want to wait for interrupt handlers, NMI handlers, and + code under the influence of preempt_disable(), you instead + need to use synchronize_irq() or synchronize_sched(). 12. Any lock acquired by an RCU callback must be acquired elsewhere with softirq disabled, e.g., via spin_lock_irqsave(), spin_lock_bh(), etc. Failing to disable irq on a given - acquisition of that lock will result in deadlock as soon as the - RCU callback happens to interrupt that acquisition's critical - section. + acquisition of that lock will result in deadlock as soon as + the RCU softirq handler happens to run your RCU callback while + interrupting that acquisition's critical section. 13. RCU callbacks can be and are executed in parallel. In many cases, the callback code simply wrappers around kfree(), so that this @@ -265,29 +302,30 @@ over a rather long period of time, but improvements are always welcome! not the case, a self-spawning RCU callback would prevent the victim CPU from ever going offline.) -14. SRCU (srcu_read_lock(), srcu_read_unlock(), and synchronize_srcu()) - may only be invoked from process context. Unlike other forms of - RCU, it -is- permissible to block in an SRCU read-side critical - section (demarked by srcu_read_lock() and srcu_read_unlock()), - hence the "SRCU": "sleepable RCU". Please note that if you - don't need to sleep in read-side critical sections, you should - be using RCU rather than SRCU, because RCU is almost always - faster and easier to use than is SRCU. +14. SRCU (srcu_read_lock(), srcu_read_unlock(), synchronize_srcu(), + and synchronize_srcu_expedited()) may only be invoked from + process context. Unlike other forms of RCU, it -is- permissible + to block in an SRCU read-side critical section (demarked by + srcu_read_lock() and srcu_read_unlock()), hence the "SRCU": + "sleepable RCU". Please note that if you don't need to sleep + in read-side critical sections, you should be using RCU rather + than SRCU, because RCU is almost always faster and easier to + use than is SRCU. Also unlike other forms of RCU, explicit initialization and cleanup is required via init_srcu_struct() and cleanup_srcu_struct(). These are passed a "struct srcu_struct" that defines the scope of a given SRCU domain. Once initialized, the srcu_struct is passed to srcu_read_lock(), srcu_read_unlock() - and synchronize_srcu(). A given synchronize_srcu() waits only - for SRCU read-side critical sections governed by srcu_read_lock() - and srcu_read_unlock() calls that have been passd the same - srcu_struct. This property is what makes sleeping read-side - critical sections tolerable -- a given subsystem delays only - its own updates, not those of other subsystems using SRCU. - Therefore, SRCU is less prone to OOM the system than RCU would - be if RCU's read-side critical sections were permitted to - sleep. + synchronize_srcu(), and synchronize_srcu_expedited(). A given + synchronize_srcu() waits only for SRCU read-side critical + sections governed by srcu_read_lock() and srcu_read_unlock() + calls that have been passed the same srcu_struct. This property + is what makes sleeping read-side critical sections tolerable -- + a given subsystem delays only its own updates, not those of other + subsystems using SRCU. Therefore, SRCU is less prone to OOM the + system than RCU would be if RCU's read-side critical sections + were permitted to sleep. The ability to sleep in read-side critical sections does not come for free. First, corresponding srcu_read_lock() and @@ -311,12 +349,12 @@ over a rather long period of time, but improvements are always welcome! destructive operation, and -only- -then- invoke call_rcu(), synchronize_rcu(), or friends. - Because these primitives only wait for pre-existing readers, - it is the caller's responsibility to guarantee safety to - any subsequent readers. + Because these primitives only wait for pre-existing readers, it + is the caller's responsibility to guarantee that any subsequent + readers will execute safely. -16. The various RCU read-side primitives do -not- contain memory - barriers. The CPU (and in some cases, the compiler) is free - to reorder code into and out of RCU read-side critical sections. - It is the responsibility of the RCU update-side primitives to - deal with this. +16. The various RCU read-side primitives do -not- necessarily contain + memory barriers. You should therefore plan for the CPU + and the compiler to freely reorder code into and out of RCU + read-side critical sections. It is the responsibility of the + RCU update-side primitives to deal with this. diff --git a/Documentation/RCU/rcu.txt b/Documentation/RCU/rcu.txt index 2a23523ce471..31852705b586 100644 --- a/Documentation/RCU/rcu.txt +++ b/Documentation/RCU/rcu.txt @@ -75,6 +75,8 @@ o I hear that RCU is patented? What is with that? search for the string "Patent" in RTFP.txt to find them. Of these, one was allowed to lapse by the assignee, and the others have been contributed to the Linux kernel under GPL. + There are now also LGPL implementations of user-level RCU + available (http://lttng.org/?q=node/18). o I hear that RCU needs work in order to support realtime kernels? @@ -91,48 +93,4 @@ o Where can I find more information on RCU? o What are all these files in this directory? - - NMI-RCU.txt - - Describes how to use RCU to implement dynamic - NMI handlers, which can be revectored on the fly, - without rebooting. - - RTFP.txt - - List of RCU-related publications and web sites. - - UP.txt - - Discussion of RCU usage in UP kernels. - - arrayRCU.txt - - Describes how to use RCU to protect arrays, with - resizeable arrays whose elements reference other - data structures being of the most interest. - - checklist.txt - - Lists things to check for when inspecting code that - uses RCU. - - listRCU.txt - - Describes how to use RCU to protect linked lists. - This is the simplest and most common use of RCU - in the Linux kernel. - - rcu.txt - - You are reading it! - - rcuref.txt - - Describes how to combine use of reference counts - with RCU. - - whatisRCU.txt - - Overview of how the RCU implementation works. Along - the way, presents a conceptual view of RCU. + See 00-INDEX for the list. diff --git a/Documentation/RCU/stallwarn.txt b/Documentation/RCU/stallwarn.txt new file mode 100644 index 000000000000..1423d2570d78 --- /dev/null +++ b/Documentation/RCU/stallwarn.txt @@ -0,0 +1,58 @@ +Using RCU's CPU Stall Detector + +The CONFIG_RCU_CPU_STALL_DETECTOR kernel config parameter enables +RCU's CPU stall detector, which detects conditions that unduly delay +RCU grace periods. The stall detector's idea of what constitutes +"unduly delayed" is controlled by a pair of C preprocessor macros: + +RCU_SECONDS_TILL_STALL_CHECK + + This macro defines the period of time that RCU will wait from + the beginning of a grace period until it issues an RCU CPU + stall warning. It is normally ten seconds. + +RCU_SECONDS_TILL_STALL_RECHECK + + This macro defines the period of time that RCU will wait after + issuing a stall warning until it issues another stall warning. + It is normally set to thirty seconds. + +RCU_STALL_RAT_DELAY + + The CPU stall detector tries to make the offending CPU rat on itself, + as this often gives better-quality stack traces. However, if + the offending CPU does not detect its own stall in the number + of jiffies specified by RCU_STALL_RAT_DELAY, then other CPUs will + complain. This is normally set to two jiffies. + +The following problems can result in an RCU CPU stall warning: + +o A CPU looping in an RCU read-side critical section. + +o A CPU looping with interrupts disabled. + +o A CPU looping with preemption disabled. + +o For !CONFIG_PREEMPT kernels, a CPU looping anywhere in the kernel + without invoking schedule(). + +o A bug in the RCU implementation. + +o A hardware failure. This is quite unlikely, but has occurred + at least once in a former life. A CPU failed in a running system, + becoming unresponsive, but not causing an immediate crash. + This resulted in a series of RCU CPU stall warnings, eventually + leading the realization that the CPU had failed. + +The RCU, RCU-sched, and RCU-bh implementations have CPU stall warning. +SRCU does not do so directly, but its calls to synchronize_sched() will +result in RCU-sched detecting any CPU stalls that might be occurring. + +To diagnose the cause of the stall, inspect the stack traces. The offending +function will usually be near the top of the stack. If you have a series +of stall warnings from a single extended stall, comparing the stack traces +can often help determine where the stall is occurring, which will usually +be in the function nearest the top of the stack that stays the same from +trace to trace. + +RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE. diff --git a/Documentation/RCU/torture.txt b/Documentation/RCU/torture.txt index 9dba3bb90e60..0e50bc2aa1e2 100644 --- a/Documentation/RCU/torture.txt +++ b/Documentation/RCU/torture.txt @@ -30,6 +30,18 @@ MODULE PARAMETERS This module has the following parameters: +fqs_duration Duration (in microseconds) of artificially induced bursts + of force_quiescent_state() invocations. In RCU + implementations having force_quiescent_state(), these + bursts help force races between forcing a given grace + period and that grace period ending on its own. + +fqs_holdoff Holdoff time (in microseconds) between consecutive calls + to force_quiescent_state() within a burst. + +fqs_stutter Wait time (in seconds) between consecutive bursts + of calls to force_quiescent_state(). + irqreaders Says to invoke RCU readers from irq level. This is currently done via timers. Defaults to "1" for variants of RCU that permit this. (Or, more accurately, variants of RCU that do diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt index d542ca243b80..469a58b2e67e 100644 --- a/Documentation/RCU/whatisRCU.txt +++ b/Documentation/RCU/whatisRCU.txt @@ -327,7 +327,8 @@ a. synchronize_rcu() rcu_read_lock() / rcu_read_unlock() b. call_rcu_bh() rcu_read_lock_bh() / rcu_read_unlock_bh() -c. synchronize_sched() preempt_disable() / preempt_enable() +c. synchronize_sched() rcu_read_lock_sched() / rcu_read_unlock_sched() + preempt_disable() / preempt_enable() local_irq_save() / local_irq_restore() hardirq enter / hardirq exit NMI enter / NMI exit diff --git a/Documentation/filesystems/dentry-locking.txt b/Documentation/filesystems/dentry-locking.txt index 4c0c575a4012..79334ed5daa7 100644 --- a/Documentation/filesystems/dentry-locking.txt +++ b/Documentation/filesystems/dentry-locking.txt @@ -62,7 +62,8 @@ changes are : 2. Insertion of a dentry into the hash table is done using hlist_add_head_rcu() which take care of ordering the writes - the writes to the dentry must be visible before the dentry is - inserted. This works in conjunction with hlist_for_each_rcu() while + inserted. This works in conjunction with hlist_for_each_rcu(), + which has since been replaced by hlist_for_each_entry_rcu(), while walking the hash chain. The only requirement is that all initialization to the dentry must be done before hlist_add_head_rcu() since we don't have dcache_lock protection diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 25c3ed594c54..6bf97d176326 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -765,9 +765,9 @@ config RCU_CPU_STALL_DETECTOR CPUs are delaying the current grace period, but only when the grace period extends for excessive time periods. - Say Y if you want RCU to perform such checks. + Say N if you want to disable such checks. - Say N if you are unsure. + Say Y if you are unsure. config KPROBES_SANITY_TEST bool "Kprobes sanity tests" -- cgit v1.2.3 From aeb583d08172e038552bdefe0a79a9aa9e2ecd7c Mon Sep 17 00:00:00 2001 From: Thiago Farina Date: Mon, 18 Jan 2010 18:57:33 -0500 Subject: lib/dma-debug.c: mark file-local struct symbol static. warning: symbol 'filter_fops' was not declared. Should it be static? Signed-off-by: Thiago Farina Signed-off-by: Joerg Roedel --- lib/dma-debug.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 739974460c32..e03995851e60 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -587,7 +587,7 @@ out_unlock: return count; } -const struct file_operations filter_fops = { +static const struct file_operations filter_fops = { .read = filter_read, .write = filter_write, }; -- cgit v1.2.3 From 660e2acad81c19b404f7d7d06e57a6d5e6ce7426 Mon Sep 17 00:00:00 2001 From: Chris Smith Date: Wed, 27 Jan 2010 22:03:11 +0900 Subject: sh: kmemleak support. Enables support for kmemleak on sh. Signed-off-by: Chris Smith Signed-off-by: Paul Mundt --- arch/sh/kernel/vmlinux.lds.S | 6 +++--- lib/Kconfig.debug | 2 +- 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/arch/sh/kernel/vmlinux.lds.S b/arch/sh/kernel/vmlinux.lds.S index 93e9b25a1811..f0bc6b886eed 100644 --- a/arch/sh/kernel/vmlinux.lds.S +++ b/arch/sh/kernel/vmlinux.lds.S @@ -50,12 +50,12 @@ SECTIONS } = 0x0009 EXCEPTION_TABLE(16) - NOTES + + _sdata = .; RO_DATA(PAGE_SIZE) RW_DATA_SECTION(L1_CACHE_BYTES, PAGE_SIZE, THREAD_SIZE) - - _edata = .; /* End of data section */ + _edata = .; DWARF_EH_FRAME diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 25c3ed594c54..d62e3cdab357 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -355,7 +355,7 @@ config SLUB_STATS config DEBUG_KMEMLEAK bool "Kernel memory leak detector" depends on DEBUG_KERNEL && EXPERIMENTAL && !MEMORY_HOTPLUG && \ - (X86 || ARM || PPC || S390) + (X86 || ARM || PPC || S390 || SUPERH) select DEBUG_FS if SYSFS select STACKTRACE if STACKTRACE_SUPPORT -- cgit v1.2.3 From 859ddf09743a8cc680af33f7259ccd0fd36bfe9d Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Tue, 2 Feb 2010 13:43:58 -0800 Subject: idr: fix a critical misallocation bug Eric Paris located a bug in idr. With IDR_BITS of 6, it grows to three layers when id 4096 is first allocated. When that happens, idr wraps incorrectly and searches the idr array ignoring the high bits. The following test code from Eric demonstrates the bug nicely. #include #include #include static DEFINE_IDR(test_idr); int init_module(void) { int ret, forty95, forty96; void *addr; /* add 2 entries both with 4095 as the start address */ again1: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4095, 4095, &forty95); if (ret) { if (ret == -EAGAIN) goto again1; return ret; } if (forty95 != 4095) printk(KERN_ERR "hmmm, forty95=%d\n", forty95); again2: if (!idr_pre_get(&test_idr, GFP_KERNEL)) return -ENOMEM; ret = idr_get_new_above(&test_idr, (void *)4096, 4095, &forty96); if (ret) { if (ret == -EAGAIN) goto again2; return ret; } if (forty96 != 4096) printk(KERN_ERR "hmmm, forty96=%d\n", forty96); /* try to find the 2 entries, noticing that 4096 broke */ addr = idr_find(&test_idr, forty95); if ((int)addr != forty95) printk(KERN_ERR "hmmm, after find forty95=%d addr=%d\n", forty95, (int)addr); addr = idr_find(&test_idr, forty96); if ((int)addr != forty96) printk(KERN_ERR "hmmm, after find forty96=%d addr=%d\n", forty96, (int)addr); /* really weird, the entry which should be at 4096 is actually at 0!! */ addr = idr_find(&test_idr, 0); if ((int)addr) printk(KERN_ERR "found an entry at id=0 for addr=%d\n", (int)addr); idr_remove(&test_idr, forty95); idr_remove(&test_idr, forty96); return 0; } void cleanup_module(void) { } MODULE_AUTHOR("Eric Paris "); MODULE_DESCRIPTION("Simple idr test"); MODULE_LICENSE("GPL"); This happens because when sub_alloc() back tracks it doesn't always do it step-by-step while the over-the-limit detection assumes step-by-step backtracking. The logic in sub_alloc() looks like the following. restart: clear pa[top level + 1] for end cond detection l = top level while (true) { search for empty slot at this level if (not found) { push id to the next possible value l++ A: if (pa[l] is clear) failed, return asking caller to grow the tree if (going up 1 level gives more slots to search) continue the while loop above with the incremented l else C: goto restart } adjust id accordingly to the found slot if (l == 0) return found id; create lower level if not there yet record pa[l] and l-- } Test A is the fail exit condition but this assumes that failure is propagated upwared one level at a time but the B optimization path breaks the assumption and restarts the whole thing with a start value which is above the possible limit with the current layers. sub_alloc() assumes the start id value is inside the limit when called and test A is the only exit condition check, so it ends up searching for empty slot while ignoring high set bit. So, for 4095->4096 test, level0 search fails but pa[1] contains a valid pointer. However, going up 1 level wouldn't give any more empty slot so it takes C and when the whole thing restarts nobody notices the high bit set beyond the top level. This patch fixes the bug by changing the fail exit condition check to full id limit check. Based-on-patch-from: Eric Paris Reported-by: Eric Paris Signed-off-by: Tejun Heo Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1cac726c44bc..ba7d37cf7847 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,8 +140,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = idp->layers; - pa[l--] = NULL; + l = p->layer; while (1) { /* * We run around this while until we reach the leaf node... @@ -155,8 +154,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* if already at the top layer, we need to grow */ - if (!(p = pa[l])) { + /* did id go over the limit? */ + if (id >= (1 << (idp->layers * IDR_BITS))) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit v1.2.3 From 24551f64d47af9539a7f324343bffeea09d9dcfa Mon Sep 17 00:00:00 2001 From: Michael Ellerman Date: Tue, 12 Jan 2010 21:25:24 +0000 Subject: lmb: Add lmb_free() We can free memory allocated with lmb_alloc() by removing it from the list of reserved LMBs. Rework lmb_remove() to allow that possibility and add lmb_free() which exploits it. BenH: Removed some useless parenthesis Signed-off-by: Michael Ellerman Signed-off-by: Benjamin Herrenschmidt --- include/linux/lmb.h | 1 + lib/lmb.c | 13 +++++++++++-- 2 files changed, 12 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/include/linux/lmb.h b/include/linux/lmb.h index ef82b8fcbddb..f3d14333ebed 100644 --- a/include/linux/lmb.h +++ b/include/linux/lmb.h @@ -42,6 +42,7 @@ extern void __init lmb_init(void); extern void __init lmb_analyze(void); extern long lmb_add(u64 base, u64 size); extern long lmb_remove(u64 base, u64 size); +extern long __init lmb_free(u64 base, u64 size); extern long __init lmb_reserve(u64 base, u64 size); extern u64 __init lmb_alloc_nid(u64 size, u64 align, int nid, u64 (*nid_range)(u64, u64, int *)); diff --git a/lib/lmb.c b/lib/lmb.c index 9cee17142b2c..b1fc52606524 100644 --- a/lib/lmb.c +++ b/lib/lmb.c @@ -205,9 +205,8 @@ long lmb_add(u64 base, u64 size) } -long lmb_remove(u64 base, u64 size) +static long __lmb_remove(struct lmb_region *rgn, u64 base, u64 size) { - struct lmb_region *rgn = &(lmb.memory); u64 rgnbegin, rgnend; u64 end = base + size; int i; @@ -254,6 +253,16 @@ long lmb_remove(u64 base, u64 size) return lmb_add_region(rgn, end, rgnend - end); } +long lmb_remove(u64 base, u64 size) +{ + return __lmb_remove(&lmb.memory, base, size); +} + +long __init lmb_free(u64 base, u64 size) +{ + return __lmb_remove(&lmb.reserved, base, size); +} + long __init lmb_reserve(u64 base, u64 size) { struct lmb_region *_rgn = &lmb.reserved; -- cgit v1.2.3 From 6f14a668f1a8b715a6e855f4e32705e54a6e86a1 Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Thu, 4 Feb 2010 17:57:37 +0900 Subject: idr: revert misallocation bug fix Commit 859ddf09743a8cc680af33f7259ccd0fd36bfe9d tried to fix misallocation bug but broke full bit marking by not clearing pa[idp->layers] and also is causing X failures due to lookup failure in drm code. The cause of the latter hasn't been found yet. Revert the fix for now. Signed-off-by: Tejun Heo Signed-off-by: Linus Torvalds --- lib/idr.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index ba7d37cf7847..1cac726c44bc 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -140,7 +140,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = *starting_id; restart: p = idp->top; - l = p->layer; + l = idp->layers; + pa[l--] = NULL; while (1) { /* * We run around this while until we reach the leaf node... @@ -154,8 +155,8 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) oid = id; id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; - /* did id go over the limit? */ - if (id >= (1 << (idp->layers * IDR_BITS))) { + /* if already at the top layer, we need to grow */ + if (!(p = pa[l])) { *starting_id = id; return IDR_NEED_TO_GROW; } -- cgit v1.2.3 From d2e7276b6b5e4bc2148891a056d5862c5314342d Mon Sep 17 00:00:00 2001 From: Tejun Heo Date: Mon, 22 Feb 2010 12:44:19 -0800 Subject: idr: fix a critical misallocation bug, take#2 This is retry of reverted 859ddf09743a8cc680af33f7259ccd0fd36bfe9d ("idr: fix a critical misallocation bug") which contained two bugs. * pa[idp->layers] should be cleared even if it's not used by sub_alloc() because it's used by mark idr_mark_full(). * The original condition check also assigned pa[l] to p which the new code didn't do thus leaving p pointing at the wrong layer. Both problems have been fixed and the idr code has received good amount testing using userland testing setup where simple bitmap allocator is run parallel to verify the result of idr allocation. The bug this patch fixes is caused by sub_alloc() optimization path bypassing out-of-room condition check and restarting allocation loop with starting value higher than maximum allowed value. For detailed description, please read commit message of 859ddf09. Signed-off-by: Tejun Heo Based-on-patch-from: Eric Paris Reported-by: Eric Paris Tested-by: Stefan Lippers-Hollmann Tested-by: Serge Hallyn Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/idr.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 1cac726c44bc..0dc782216d4b 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -156,10 +156,12 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; /* if already at the top layer, we need to grow */ - if (!(p = pa[l])) { + if (id >= 1 << (idp->layers * IDR_BITS)) { *starting_id = id; return IDR_NEED_TO_GROW; } + p = pa[l]; + BUG_ON(!p); /* If we need to go up one layer, continue the * loop; otherwise, restart from the top. -- cgit v1.2.3 From 632ee200130899252508c478ad0e808222573fbc Mon Sep 17 00:00:00 2001 From: Paul E. McKenney Date: Mon, 22 Feb 2010 17:04:45 -0800 Subject: rcu: Introduce lockdep-based checking to RCU read-side primitives Inspection is proving insufficient to catch all RCU misuses, which is understandable given that rcu_dereference() might be protected by any of four different flavors of RCU (RCU, RCU-bh, RCU-sched, and SRCU), and might also/instead be protected by any of a number of locking primitives. It is therefore time to enlist the aid of lockdep. This set of patches is inspired by earlier work by Peter Zijlstra and Thomas Gleixner, and takes the following approach: o Set up separate lockdep classes for RCU, RCU-bh, and RCU-sched. o Set up separate lockdep classes for each instance of SRCU. o Create primitives that check for being in an RCU read-side critical section. These return exact answers if lockdep is fully enabled, but if unsure, report being in an RCU read-side critical section. (We want to avoid false positives!) The primitives are: For RCU: rcu_read_lock_held(void) For RCU-bh: rcu_read_lock_bh_held(void) For RCU-sched: rcu_read_lock_sched_held(void) For SRCU: srcu_read_lock_held(struct srcu_struct *sp) o Add rcu_dereference_check(), which takes a second argument in which one places a boolean expression based on the above primitives and/or lockdep_is_held(). o A new kernel configuration parameter, CONFIG_PROVE_RCU, enables rcu_dereference_check(). This depends on CONFIG_PROVE_LOCKING, and should be quite helpful during the transition period while CONFIG_PROVE_RCU-unaware patches are in flight. The existing rcu_dereference() primitive does no checking, but upcoming patches will change that. Signed-off-by: Paul E. McKenney Cc: laijs@cn.fujitsu.com Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: josh@joshtriplett.org Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: dhowells@redhat.com LKML-Reference: <1266887105-1528-1-git-send-email-paulmck@linux.vnet.ibm.com> Signed-off-by: Ingo Molnar --- include/linux/rcupdate.h | 126 +++++++++++++++++++++++++++++++++++++++++++---- include/linux/srcu.h | 87 +++++++++++++++++++++++++++++++- kernel/rcupdate.c | 10 ++++ kernel/rcutorture.c | 12 ++++- kernel/srcu.c | 50 ++++++++++++------- lib/Kconfig.debug | 12 +++++ lib/debug_locks.c | 1 + 7 files changed, 267 insertions(+), 31 deletions(-) (limited to 'lib') diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index 24440f4bf476..e3d37efe2703 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -78,14 +78,120 @@ extern void rcu_init(void); } while (0) #ifdef CONFIG_DEBUG_LOCK_ALLOC + extern struct lockdep_map rcu_lock_map; -# define rcu_read_acquire() \ - lock_acquire(&rcu_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_) +# define rcu_read_acquire() \ + lock_acquire(&rcu_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_) # define rcu_read_release() lock_release(&rcu_lock_map, 1, _THIS_IP_) -#else -# define rcu_read_acquire() do { } while (0) -# define rcu_read_release() do { } while (0) -#endif + +extern struct lockdep_map rcu_bh_lock_map; +# define rcu_read_acquire_bh() \ + lock_acquire(&rcu_bh_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_) +# define rcu_read_release_bh() lock_release(&rcu_bh_lock_map, 1, _THIS_IP_) + +extern struct lockdep_map rcu_sched_lock_map; +# define rcu_read_acquire_sched() \ + lock_acquire(&rcu_sched_lock_map, 0, 0, 2, 1, NULL, _THIS_IP_) +# define rcu_read_release_sched() \ + lock_release(&rcu_sched_lock_map, 1, _THIS_IP_) + +/** + * rcu_read_lock_held - might we be in RCU read-side critical section? + * + * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in + * an RCU read-side critical section. In absence of CONFIG_PROVE_LOCKING, + * this assumes we are in an RCU read-side critical section unless it can + * prove otherwise. + */ +static inline int rcu_read_lock_held(void) +{ + if (debug_locks) + return lock_is_held(&rcu_lock_map); + return 1; +} + +/** + * rcu_read_lock_bh_held - might we be in RCU-bh read-side critical section? + * + * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in + * an RCU-bh read-side critical section. In absence of CONFIG_PROVE_LOCKING, + * this assumes we are in an RCU-bh read-side critical section unless it can + * prove otherwise. + */ +static inline int rcu_read_lock_bh_held(void) +{ + if (debug_locks) + return lock_is_held(&rcu_bh_lock_map); + return 1; +} + +/** + * rcu_read_lock_sched_held - might we be in RCU-sched read-side critical section? + * + * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in an + * RCU-sched read-side critical section. In absence of CONFIG_PROVE_LOCKING, + * this assumes we are in an RCU-sched read-side critical section unless it + * can prove otherwise. Note that disabling of preemption (including + * disabling irqs) counts as an RCU-sched read-side critical section. + */ +static inline int rcu_read_lock_sched_held(void) +{ + int lockdep_opinion = 0; + + if (debug_locks) + lockdep_opinion = lock_is_held(&rcu_sched_lock_map); + return lockdep_opinion || preempt_count() != 0; +} + +#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + +# define rcu_read_acquire() do { } while (0) +# define rcu_read_release() do { } while (0) +# define rcu_read_acquire_bh() do { } while (0) +# define rcu_read_release_bh() do { } while (0) +# define rcu_read_acquire_sched() do { } while (0) +# define rcu_read_release_sched() do { } while (0) + +static inline int rcu_read_lock_held(void) +{ + return 1; +} + +static inline int rcu_read_lock_bh_held(void) +{ + return 1; +} + +static inline int rcu_read_lock_sched_held(void) +{ + return preempt_count() != 0; +} + +#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + +#ifdef CONFIG_PROVE_RCU + +/** + * rcu_dereference_check - rcu_dereference with debug checking + * + * Do an rcu_dereference(), but check that the context is correct. + * For example, rcu_dereference_check(gp, rcu_read_lock_held()) to + * ensure that the rcu_dereference_check() executes within an RCU + * read-side critical section. It is also possible to check for + * locks being held, for example, by using lockdep_is_held(). + */ +#define rcu_dereference_check(p, c) \ + ({ \ + if (debug_locks) \ + WARN_ON_ONCE(!(c)); \ + rcu_dereference(p); \ + }) + +#else /* #ifdef CONFIG_PROVE_RCU */ + +#define rcu_dereference_check(p, c) rcu_dereference(p) + +#endif /* #else #ifdef CONFIG_PROVE_RCU */ /** * rcu_read_lock - mark the beginning of an RCU read-side critical section. @@ -160,7 +266,7 @@ static inline void rcu_read_lock_bh(void) { __rcu_read_lock_bh(); __acquire(RCU_BH); - rcu_read_acquire(); + rcu_read_acquire_bh(); } /* @@ -170,7 +276,7 @@ static inline void rcu_read_lock_bh(void) */ static inline void rcu_read_unlock_bh(void) { - rcu_read_release(); + rcu_read_release_bh(); __release(RCU_BH); __rcu_read_unlock_bh(); } @@ -188,7 +294,7 @@ static inline void rcu_read_lock_sched(void) { preempt_disable(); __acquire(RCU_SCHED); - rcu_read_acquire(); + rcu_read_acquire_sched(); } /* Used by lockdep and tracing: cannot be traced, cannot call lockdep. */ @@ -205,7 +311,7 @@ static inline notrace void rcu_read_lock_sched_notrace(void) */ static inline void rcu_read_unlock_sched(void) { - rcu_read_release(); + rcu_read_release_sched(); __release(RCU_SCHED); preempt_enable(); } diff --git a/include/linux/srcu.h b/include/linux/srcu.h index 4765d97dcafb..adbe1670b366 100644 --- a/include/linux/srcu.h +++ b/include/linux/srcu.h @@ -35,6 +35,9 @@ struct srcu_struct { int completed; struct srcu_struct_array *per_cpu_ref; struct mutex mutex; +#ifdef CONFIG_DEBUG_LOCK_ALLOC + struct lockdep_map dep_map; +#endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ }; #ifndef CONFIG_PREEMPT @@ -43,12 +46,92 @@ struct srcu_struct { #define srcu_barrier() #endif /* #else #ifndef CONFIG_PREEMPT */ +#ifdef CONFIG_DEBUG_LOCK_ALLOC + +int __init_srcu_struct(struct srcu_struct *sp, const char *name, + struct lock_class_key *key); + +#define init_srcu_struct(sp) \ +({ \ + static struct lock_class_key __srcu_key; \ + \ + __init_srcu_struct((sp), #sp, &__srcu_key); \ +}) + +# define srcu_read_acquire(sp) \ + lock_acquire(&(sp)->dep_map, 0, 0, 2, 1, NULL, _THIS_IP_) +# define srcu_read_release(sp) \ + lock_release(&(sp)->dep_map, 1, _THIS_IP_) + +#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + int init_srcu_struct(struct srcu_struct *sp); + +# define srcu_read_acquire(sp) do { } while (0) +# define srcu_read_release(sp) do { } while (0) + +#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + void cleanup_srcu_struct(struct srcu_struct *sp); -int srcu_read_lock(struct srcu_struct *sp) __acquires(sp); -void srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp); +int __srcu_read_lock(struct srcu_struct *sp) __acquires(sp); +void __srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp); void synchronize_srcu(struct srcu_struct *sp); void synchronize_srcu_expedited(struct srcu_struct *sp); long srcu_batches_completed(struct srcu_struct *sp); +#ifdef CONFIG_DEBUG_LOCK_ALLOC + +/** + * srcu_read_lock_held - might we be in SRCU read-side critical section? + * + * If CONFIG_PROVE_LOCKING is selected and enabled, returns nonzero iff in + * an SRCU read-side critical section. In absence of CONFIG_PROVE_LOCKING, + * this assumes we are in an SRCU read-side critical section unless it can + * prove otherwise. + */ +static inline int srcu_read_lock_held(struct srcu_struct *sp) +{ + if (debug_locks) + return lock_is_held(&sp->dep_map); + return 1; +} + +#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + +static inline int srcu_read_lock_held(struct srcu_struct *sp) +{ + return 1; +} + +#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + +/** + * srcu_read_lock - register a new reader for an SRCU-protected structure. + * @sp: srcu_struct in which to register the new reader. + * + * Enter an SRCU read-side critical section. Note that SRCU read-side + * critical sections may be nested. + */ +static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp) +{ + int retval = __srcu_read_lock(sp); + + srcu_read_acquire(sp); + return retval; +} + +/** + * srcu_read_unlock - unregister a old reader from an SRCU-protected structure. + * @sp: srcu_struct in which to unregister the old reader. + * @idx: return value from corresponding srcu_read_lock(). + * + * Exit an SRCU read-side critical section. + */ +static inline void srcu_read_unlock(struct srcu_struct *sp, int idx) + __releases(sp) +{ + srcu_read_release(sp); + __srcu_read_unlock(sp, idx); +} + #endif diff --git a/kernel/rcupdate.c b/kernel/rcupdate.c index 9b7fd4723878..033cb55c26df 100644 --- a/kernel/rcupdate.c +++ b/kernel/rcupdate.c @@ -50,6 +50,16 @@ static struct lock_class_key rcu_lock_key; struct lockdep_map rcu_lock_map = STATIC_LOCKDEP_MAP_INIT("rcu_read_lock", &rcu_lock_key); EXPORT_SYMBOL_GPL(rcu_lock_map); + +static struct lock_class_key rcu_bh_lock_key; +struct lockdep_map rcu_bh_lock_map = + STATIC_LOCKDEP_MAP_INIT("rcu_read_lock_bh", &rcu_bh_lock_key); +EXPORT_SYMBOL_GPL(rcu_bh_lock_map); + +static struct lock_class_key rcu_sched_lock_key; +struct lockdep_map rcu_sched_lock_map = + STATIC_LOCKDEP_MAP_INIT("rcu_read_lock_sched", &rcu_sched_lock_key); +EXPORT_SYMBOL_GPL(rcu_sched_lock_map); #endif /* diff --git a/kernel/rcutorture.c b/kernel/rcutorture.c index adda92bfafac..5f43f30fcd1d 100644 --- a/kernel/rcutorture.c +++ b/kernel/rcutorture.c @@ -796,7 +796,11 @@ static void rcu_torture_timer(unsigned long unused) idx = cur_ops->readlock(); completed = cur_ops->completed(); - p = rcu_dereference(rcu_torture_current); + p = rcu_dereference_check(rcu_torture_current, + rcu_read_lock_held() || + rcu_read_lock_bh_held() || + rcu_read_lock_sched_held() || + srcu_read_lock_held(&srcu_ctl)); if (p == NULL) { /* Leave because rcu_torture_writer is not yet underway */ cur_ops->readunlock(idx); @@ -853,7 +857,11 @@ rcu_torture_reader(void *arg) } idx = cur_ops->readlock(); completed = cur_ops->completed(); - p = rcu_dereference(rcu_torture_current); + p = rcu_dereference_check(rcu_torture_current, + rcu_read_lock_held() || + rcu_read_lock_bh_held() || + rcu_read_lock_sched_held() || + srcu_read_lock_held(&srcu_ctl)); if (p == NULL) { /* Wait for rcu_torture_writer to get underway */ cur_ops->readunlock(idx); diff --git a/kernel/srcu.c b/kernel/srcu.c index 31b275b9c112..bde4295774c8 100644 --- a/kernel/srcu.c +++ b/kernel/srcu.c @@ -34,6 +34,30 @@ #include #include +static int init_srcu_struct_fields(struct srcu_struct *sp) +{ + sp->completed = 0; + mutex_init(&sp->mutex); + sp->per_cpu_ref = alloc_percpu(struct srcu_struct_array); + return sp->per_cpu_ref ? 0 : -ENOMEM; +} + +#ifdef CONFIG_DEBUG_LOCK_ALLOC + +int __init_srcu_struct(struct srcu_struct *sp, const char *name, + struct lock_class_key *key) +{ +#ifdef CONFIG_DEBUG_LOCK_ALLOC + /* Don't re-initialize a lock while it is held. */ + debug_check_no_locks_freed((void *)sp, sizeof(*sp)); + lockdep_init_map(&sp->dep_map, name, key, 0); +#endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + return init_srcu_struct_fields(sp); +} +EXPORT_SYMBOL_GPL(__init_srcu_struct); + +#else /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + /** * init_srcu_struct - initialize a sleep-RCU structure * @sp: structure to initialize. @@ -44,13 +68,12 @@ */ int init_srcu_struct(struct srcu_struct *sp) { - sp->completed = 0; - mutex_init(&sp->mutex); - sp->per_cpu_ref = alloc_percpu(struct srcu_struct_array); - return (sp->per_cpu_ref ? 0 : -ENOMEM); + return init_srcu_struct_fields(sp); } EXPORT_SYMBOL_GPL(init_srcu_struct); +#endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */ + /* * srcu_readers_active_idx -- returns approximate number of readers * active on the specified rank of per-CPU counters. @@ -100,15 +123,12 @@ void cleanup_srcu_struct(struct srcu_struct *sp) } EXPORT_SYMBOL_GPL(cleanup_srcu_struct); -/** - * srcu_read_lock - register a new reader for an SRCU-protected structure. - * @sp: srcu_struct in which to register the new reader. - * +/* * Counts the new reader in the appropriate per-CPU element of the * srcu_struct. Must be called from process context. * Returns an index that must be passed to the matching srcu_read_unlock(). */ -int srcu_read_lock(struct srcu_struct *sp) +int __srcu_read_lock(struct srcu_struct *sp) { int idx; @@ -120,26 +140,22 @@ int srcu_read_lock(struct srcu_struct *sp) preempt_enable(); return idx; } -EXPORT_SYMBOL_GPL(srcu_read_lock); +EXPORT_SYMBOL_GPL(__srcu_read_lock); -/** - * srcu_read_unlock - unregister a old reader from an SRCU-protected structure. - * @sp: srcu_struct in which to unregister the old reader. - * @idx: return value from corresponding srcu_read_lock(). - * +/* * Removes the count for the old reader from the appropriate per-CPU * element of the srcu_struct. Note that this may well be a different * CPU than that which was incremented by the corresponding srcu_read_lock(). * Must be called from process context. */ -void srcu_read_unlock(struct srcu_struct *sp, int idx) +void __srcu_read_unlock(struct srcu_struct *sp, int idx) { preempt_disable(); srcu_barrier(); /* ensure compiler won't misorder critical section. */ per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]--; preempt_enable(); } -EXPORT_SYMBOL_GPL(srcu_read_unlock); +EXPORT_SYMBOL_GPL(__srcu_read_unlock); /* * Helper function for synchronize_srcu() and synchronize_srcu_expedited(). diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 6bf97d176326..6af20a8a0a54 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -499,6 +499,18 @@ config PROVE_LOCKING For more details, see Documentation/lockdep-design.txt. +config PROVE_RCU + bool "RCU debugging: prove RCU correctness" + depends on PROVE_LOCKING + default n + help + This feature enables lockdep extensions that check for correct + use of RCU APIs. This is currently under development. Say Y + if you want to debug RCU usage or help work on the PROVE_RCU + feature. + + Say N if you are unsure. + config LOCKDEP bool depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT diff --git a/lib/debug_locks.c b/lib/debug_locks.c index bc3b11731b9c..5bf0020b9248 100644 --- a/lib/debug_locks.c +++ b/lib/debug_locks.c @@ -23,6 +23,7 @@ * shut up after that. */ int debug_locks = 1; +EXPORT_SYMBOL_GPL(debug_locks); /* * The locking-testsuite uses to get a -- cgit v1.2.3 From 2676a58c980b7ef076cc9bbff3fd8c9d2d5417ea Mon Sep 17 00:00:00 2001 From: Paul E. McKenney Date: Mon, 22 Feb 2010 17:04:54 -0800 Subject: radix-tree: Disable RCU lockdep checking in radix tree Because the radix tree is used with many different locking designs, we cannot do any effective checking without changing the radix-tree APIs. It might make sense to do this later, but only if the RCU lockdep checking proves itself sufficiently valuable. Signed-off-by: Paul E. McKenney Cc: laijs@cn.fujitsu.com Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: josh@joshtriplett.org Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: dhowells@redhat.com LKML-Reference: <1266887105-1528-10-git-send-email-paulmck@linux.vnet.ibm.com> Signed-off-by: Ingo Molnar --- lib/radix-tree.c | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 92cdd9936e3d..6b9670d6bbf9 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -364,7 +364,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root, unsigned int height, shift; struct radix_tree_node *node, **slot; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (node == NULL) return NULL; @@ -384,7 +384,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root, do { slot = (struct radix_tree_node **) (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); - node = rcu_dereference(*slot); + node = rcu_dereference_raw(*slot); if (node == NULL) return NULL; @@ -568,7 +568,7 @@ int radix_tree_tag_get(struct radix_tree_root *root, if (!root_tag_get(root, tag)) return 0; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (node == NULL) return 0; @@ -602,7 +602,7 @@ int radix_tree_tag_get(struct radix_tree_root *root, BUG_ON(ret && saw_unset_tag); return !!ret; } - node = rcu_dereference(node->slots[offset]); + node = rcu_dereference_raw(node->slots[offset]); shift -= RADIX_TREE_MAP_SHIFT; height--; } @@ -711,7 +711,7 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, } shift -= RADIX_TREE_MAP_SHIFT; - slot = rcu_dereference(slot->slots[i]); + slot = rcu_dereference_raw(slot->slots[i]); if (slot == NULL) goto out; } @@ -758,7 +758,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long cur_index = first_index; unsigned int ret; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (!node) return 0; @@ -787,7 +787,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, slot = *(((void ***)results)[ret + i]); if (!slot) continue; - results[ret + nr_found] = rcu_dereference(slot); + results[ret + nr_found] = rcu_dereference_raw(slot); nr_found++; } ret += nr_found; @@ -826,7 +826,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, unsigned long cur_index = first_index; unsigned int ret; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (!node) return 0; @@ -915,7 +915,7 @@ __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index, } } shift -= RADIX_TREE_MAP_SHIFT; - slot = rcu_dereference(slot->slots[i]); + slot = rcu_dereference_raw(slot->slots[i]); if (slot == NULL) break; } @@ -951,7 +951,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, if (!root_tag_get(root, tag)) return 0; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (!node) return 0; @@ -980,7 +980,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, slot = *(((void ***)results)[ret + i]); if (!slot) continue; - results[ret + nr_found] = rcu_dereference(slot); + results[ret + nr_found] = rcu_dereference_raw(slot); nr_found++; } ret += nr_found; @@ -1020,7 +1020,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, if (!root_tag_get(root, tag)) return 0; - node = rcu_dereference(root->rnode); + node = rcu_dereference_raw(root->rnode); if (!node) return 0; -- cgit v1.2.3 From 96be753af91fc9d582450a84722f6a6721d218ad Mon Sep 17 00:00:00 2001 From: Paul E. McKenney Date: Mon, 22 Feb 2010 17:04:55 -0800 Subject: idr: Apply lockdep-based diagnostics to rcu_dereference() uses Because idr can be used with any of a number of locks or with any flavor of RCU, just disable the lockdep-based diagnostics. If idr needs diagnostics, the check expression will need to be passed into the relevant idr primitives as an additional argument. Signed-off-by: Paul E. McKenney Cc: laijs@cn.fujitsu.com Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: josh@joshtriplett.org Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: dhowells@redhat.com LKML-Reference: <1266887105-1528-11-git-send-email-paulmck@linux.vnet.ibm.com> Signed-off-by: Ingo Molnar --- lib/idr.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/idr.c b/lib/idr.c index 0dc782216d4b..2eb1dca03681 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -504,7 +504,7 @@ void *idr_find(struct idr *idp, int id) int n; struct idr_layer *p; - p = rcu_dereference(idp->top); + p = rcu_dereference_raw(idp->top); if (!p) return NULL; n = (p->layer+1) * IDR_BITS; @@ -519,7 +519,7 @@ void *idr_find(struct idr *idp, int id) while (n > 0 && p) { n -= IDR_BITS; BUG_ON(n != p->layer*IDR_BITS); - p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); + p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); } return((void *)p); } @@ -552,7 +552,7 @@ int idr_for_each(struct idr *idp, struct idr_layer **paa = &pa[0]; n = idp->layers * IDR_BITS; - p = rcu_dereference(idp->top); + p = rcu_dereference_raw(idp->top); max = 1 << n; id = 0; @@ -560,7 +560,7 @@ int idr_for_each(struct idr *idp, while (n > 0 && p) { n -= IDR_BITS; *paa++ = p; - p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]); + p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); } if (p) { -- cgit v1.2.3 From 1ed509a225008c9e8c0644fbd22168e09a7383a0 Mon Sep 17 00:00:00 2001 From: Paul E. McKenney Date: Mon, 22 Feb 2010 17:05:05 -0800 Subject: rcu: Add RCU_CPU_STALL_VERBOSE to dump detailed per-task information When RCU detects a grace-period stall, it currently just prints out the PID of any tasks doing the stalling. This patch adds RCU_CPU_STALL_VERBOSE, which enables the more-verbose reporting from sched_show_task(). Suggested-by: Thomas Gleixner Signed-off-by: Paul E. McKenney Cc: laijs@cn.fujitsu.com Cc: dipankar@in.ibm.com Cc: mathieu.desnoyers@polymtl.ca Cc: josh@joshtriplett.org Cc: dvhltc@us.ibm.com Cc: niv@us.ibm.com Cc: peterz@infradead.org Cc: rostedt@goodmis.org Cc: Valdis.Kletnieks@vt.edu Cc: dhowells@redhat.com LKML-Reference: <1266887105-1528-21-git-send-email-paulmck@linux.vnet.ibm.com> Signed-off-by: Ingo Molnar --- kernel/rcutree.c | 4 ++++ kernel/rcutree.h | 1 + kernel/rcutree_plugin.h | 52 +++++++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig.debug | 12 ++++++++++++ 4 files changed, 69 insertions(+) (limited to 'lib') diff --git a/kernel/rcutree.c b/kernel/rcutree.c index b07be37d2aa3..525d39810616 100644 --- a/kernel/rcutree.c +++ b/kernel/rcutree.c @@ -489,6 +489,10 @@ static void print_other_cpu_stall(struct rcu_state *rsp) smp_processor_id(), (long)(jiffies - rsp->gp_start)); trigger_all_cpu_backtrace(); + /* If so configured, complain about tasks blocking the grace period. */ + + rcu_print_detail_task_stall(rsp); + force_quiescent_state(rsp, 0); /* Kick them all. */ } diff --git a/kernel/rcutree.h b/kernel/rcutree.h index 6a82c34ce669..2ceb08388582 100644 --- a/kernel/rcutree.h +++ b/kernel/rcutree.h @@ -352,6 +352,7 @@ static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags); #endif /* #ifdef CONFIG_HOTPLUG_CPU */ #ifdef CONFIG_RCU_CPU_STALL_DETECTOR +static void rcu_print_detail_task_stall(struct rcu_state *rsp); static void rcu_print_task_stall(struct rcu_node *rnp); #endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ static void rcu_preempt_check_blocked_tasks(struct rcu_node *rnp); diff --git a/kernel/rcutree_plugin.h b/kernel/rcutree_plugin.h index aecfe37e0117..3516de7091a1 100644 --- a/kernel/rcutree_plugin.h +++ b/kernel/rcutree_plugin.h @@ -312,6 +312,50 @@ EXPORT_SYMBOL_GPL(__rcu_read_unlock); #ifdef CONFIG_RCU_CPU_STALL_DETECTOR +#ifdef CONFIG_RCU_CPU_STALL_VERBOSE + +/* + * Dump detailed information for all tasks blocking the current RCU + * grace period on the specified rcu_node structure. + */ +static void rcu_print_detail_task_stall_rnp(struct rcu_node *rnp) +{ + unsigned long flags; + struct list_head *lp; + int phase; + struct task_struct *t; + + if (rcu_preempted_readers(rnp)) { + raw_spin_lock_irqsave(&rnp->lock, flags); + phase = rnp->gpnum & 0x1; + lp = &rnp->blocked_tasks[phase]; + list_for_each_entry(t, lp, rcu_node_entry) + sched_show_task(t); + raw_spin_unlock_irqrestore(&rnp->lock, flags); + } +} + +/* + * Dump detailed information for all tasks blocking the current RCU + * grace period. + */ +static void rcu_print_detail_task_stall(struct rcu_state *rsp) +{ + struct rcu_node *rnp = rcu_get_root(rsp); + + rcu_print_detail_task_stall_rnp(rnp); + rcu_for_each_leaf_node(rsp, rnp) + rcu_print_detail_task_stall_rnp(rnp); +} + +#else /* #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */ + +static void rcu_print_detail_task_stall(struct rcu_state *rsp) +{ +} + +#endif /* #else #ifdef CONFIG_RCU_CPU_STALL_VERBOSE */ + /* * Scan the current list of tasks blocked within RCU read-side critical * sections, printing out the tid of each. @@ -760,6 +804,14 @@ static void rcu_report_unblock_qs_rnp(struct rcu_node *rnp, unsigned long flags) #ifdef CONFIG_RCU_CPU_STALL_DETECTOR +/* + * Because preemptable RCU does not exist, we never have to check for + * tasks blocked within RCU read-side critical sections. + */ +static void rcu_print_detail_task_stall(struct rcu_state *rsp) +{ +} + /* * Because preemptable RCU does not exist, we never have to check for * tasks blocked within RCU read-side critical sections. diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 6af20a8a0a54..4cdab452bfe2 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -781,6 +781,18 @@ config RCU_CPU_STALL_DETECTOR Say Y if you are unsure. +config RCU_CPU_STALL_VERBOSE + bool "Print additional per-task information for RCU_CPU_STALL_DETECTOR" + depends on RCU_CPU_STALL_DETECTOR && TREE_PREEMPT_RCU + default n + help + This option causes RCU to printk detailed per-task information + for any tasks that are stalling the current RCU grace period. + + Say N if you are unsure. + + Say Y if you want to enable such checks. + config KPROBES_SANITY_TEST bool "Kprobes sanity tests" depends on DEBUG_KERNEL -- cgit v1.2.3 From 84c6f88fc8265d7a712d7d6ed8fc1a878dfc84d1 Mon Sep 17 00:00:00 2001 From: Hitoshi Mitake Date: Thu, 4 Feb 2010 16:08:15 +0900 Subject: perf lock: Fix and add misc documentally things I've forgot to add 'perf lock' line to command-list.txt, so users of perf could not find perf lock when they type 'perf'. Fixing command-list.txt requires document (tools/perf/Documentation/perf-lock.txt). But perf lock is too much "under construction" to write a stable document, so this is something like pseudo document for now. And I wrote description of perf lock at help section of CONFIG_LOCK_STAT, this will navigate users of lock trace events. Signed-off-by: Hitoshi Mitake Cc: Peter Zijlstra Cc: Paul Mackerras Cc: Arnaldo Carvalho de Melo LKML-Reference: <1265267295-8388-1-git-send-email-mitake@dcl.info.waseda.ac.jp> Signed-off-by: Frederic Weisbecker --- lib/Kconfig.debug | 6 ++++++ tools/perf/Documentation/perf-lock.txt | 29 +++++++++++++++++++++++++++++ tools/perf/command-list.txt | 1 + 3 files changed, 36 insertions(+) create mode 100644 tools/perf/Documentation/perf-lock.txt (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 25c3ed594c54..65f964e7fe78 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -520,6 +520,12 @@ config LOCK_STAT For more details, see Documentation/lockstat.txt + You can analyze lock events with "perf lock", subcommand of perf. + If you want to use "perf lock", you need to turn on CONFIG_EVENT_TRACING. + + CONFIG_LOCK_STAT defines "contended" and "acquired" lock events. + (CONFIG_LOCKDEP defines "acquire" and "release" events.) + config DEBUG_LOCKDEP bool "Lock dependency engine debugging" depends on DEBUG_KERNEL && LOCKDEP diff --git a/tools/perf/Documentation/perf-lock.txt b/tools/perf/Documentation/perf-lock.txt new file mode 100644 index 000000000000..b317102138c8 --- /dev/null +++ b/tools/perf/Documentation/perf-lock.txt @@ -0,0 +1,29 @@ +perf-lock(1) +============ + +NAME +---- +perf-lock - Analyze lock events + +SYNOPSIS +-------- +[verse] +'perf lock' {record|report|trace} + +DESCRIPTION +----------- +You can analyze various lock behaviours +and statistics with this 'perf lock' command. + + 'perf lock record ' records lock events + between start and end . And this command + produces the file "perf.data" which contains tracing + results of lock events. + + 'perf lock trace' shows raw lock events. + + 'perf lock report' reports statistical data. + +SEE ALSO +-------- +linkperf:perf[1] diff --git a/tools/perf/command-list.txt b/tools/perf/command-list.txt index 9afcff2e3ae5..db6ee94d4a8e 100644 --- a/tools/perf/command-list.txt +++ b/tools/perf/command-list.txt @@ -18,3 +18,4 @@ perf-top mainporcelain common perf-trace mainporcelain common perf-probe mainporcelain common perf-kmem mainporcelain common +perf-lock mainporcelain common -- cgit v1.2.3 From dd8b1cf681eab40bc5afb67bdd06b2ca341f5669 Mon Sep 17 00:00:00 2001 From: Frederic Weisbecker Date: Sat, 27 Feb 2010 17:10:39 +0100 Subject: perf: Remove pointless breakpoint union Remove pointless union in the breakpoint field of hw_perf_event. Signed-off-by: Frederic Weisbecker Cc: Peter Zijlstra Cc: Paul Mackerras --- include/linux/perf_event.h | 5 ++--- lib/Kconfig.debug | 8 +++++--- 2 files changed, 7 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/include/linux/perf_event.h b/include/linux/perf_event.h index 7b18b4fd5df7..04f06b4be297 100644 --- a/include/linux/perf_event.h +++ b/include/linux/perf_event.h @@ -487,9 +487,8 @@ struct hw_perf_event { struct hrtimer hrtimer; }; #ifdef CONFIG_HAVE_HW_BREAKPOINT - union { /* breakpoint */ - struct arch_hw_breakpoint info; - }; + /* breakpoint */ + struct arch_hw_breakpoint info; #endif }; atomic64_t prev_count; diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 65f964e7fe78..4dc24cc13f5c 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -520,11 +520,13 @@ config LOCK_STAT For more details, see Documentation/lockstat.txt - You can analyze lock events with "perf lock", subcommand of perf. - If you want to use "perf lock", you need to turn on CONFIG_EVENT_TRACING. + This also enables lock events required by "perf lock", + subcommand of perf. + If you want to use "perf lock", you also need to turn on + CONFIG_EVENT_TRACING. CONFIG_LOCK_STAT defines "contended" and "acquired" lock events. - (CONFIG_LOCKDEP defines "acquire" and "release" events.) + (CONFIG_LOCKDEP defines "acquire" and "release" events.) config DEBUG_LOCKDEP bool "Lock dependency engine debugging" -- cgit v1.2.3 From f047f4f3792344901e1ea18a180515d7d5349e02 Mon Sep 17 00:00:00 2001 From: Amerigo Wang Date: Fri, 5 Mar 2010 13:42:24 -0800 Subject: mm: use the same log level for show_mem() Use the same log level for printk's in show_mem(), so that those messages can be shown completely when using log level 6. Signed-off-by: WANG Cong Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/show_mem.c | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'lib') diff --git a/lib/show_mem.c b/lib/show_mem.c index 238e72a18ce1..fdc77c82f922 100644 --- a/lib/show_mem.c +++ b/lib/show_mem.c @@ -15,7 +15,7 @@ void show_mem(void) unsigned long total = 0, reserved = 0, shared = 0, nonshared = 0, highmem = 0; - printk(KERN_INFO "Mem-Info:\n"); + printk("Mem-Info:\n"); show_free_areas(); for_each_online_pgdat(pgdat) { @@ -49,15 +49,15 @@ void show_mem(void) pgdat_resize_unlock(pgdat, &flags); } - printk(KERN_INFO "%lu pages RAM\n", total); + printk("%lu pages RAM\n", total); #ifdef CONFIG_HIGHMEM - printk(KERN_INFO "%lu pages HighMem\n", highmem); + printk("%lu pages HighMem\n", highmem); #endif - printk(KERN_INFO "%lu pages reserved\n", reserved); - printk(KERN_INFO "%lu pages shared\n", shared); - printk(KERN_INFO "%lu pages non-shared\n", nonshared); + printk("%lu pages reserved\n", reserved); + printk("%lu pages shared\n", shared); + printk("%lu pages non-shared\n", nonshared); #ifdef CONFIG_QUICKLIST - printk(KERN_INFO "%lu pages in pagetable cache\n", + printk("%lu pages in pagetable cache\n", quicklist_total_size()); #endif } -- cgit v1.2.3 From 0347af4ee3922220f6bfe74b87b526aa709a0365 Mon Sep 17 00:00:00 2001 From: Simon Kagstrom Date: Fri, 5 Mar 2010 13:42:49 -0800 Subject: lkdtm: add debugfs access and loosen KPROBE ties Add adds a debugfs interface and additional failure modes to LKDTM to provide similar functionality to the provoke-crash driver submitted here: http://lwn.net/Articles/371208/ Crashes can now be induced either through module parameters (as before) or through the debugfs interface as in provoke-crash. The patch also provides a new "direct" interface, where KPROBES are not used, i.e., the crash is invoked directly upon write to the debugfs file. When built without KPROBES configured, only this mode is available. Signed-off-by: Simon Kagstrom Cc: M. Mohan Kumar Cc: Americo Wang Cc: David Woodhouse Cc: Ingo Molnar Cc: "Eric W. Biederman" , Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- Documentation/fault-injection/provoke-crashes.txt | 38 ++ drivers/misc/lkdtm.c | 472 ++++++++++++++++++---- lib/Kconfig.debug | 5 +- 3 files changed, 430 insertions(+), 85 deletions(-) create mode 100644 Documentation/fault-injection/provoke-crashes.txt (limited to 'lib') diff --git a/Documentation/fault-injection/provoke-crashes.txt b/Documentation/fault-injection/provoke-crashes.txt new file mode 100644 index 000000000000..7a9d3d81525b --- /dev/null +++ b/Documentation/fault-injection/provoke-crashes.txt @@ -0,0 +1,38 @@ +The lkdtm module provides an interface to crash or injure the kernel at +predefined crashpoints to evaluate the reliability of crash dumps obtained +using different dumping solutions. The module uses KPROBEs to instrument +crashing points, but can also crash the kernel directly without KRPOBE +support. + + +You can provide the way either through module arguments when inserting +the module, or through a debugfs interface. + +Usage: insmod lkdtm.ko [recur_count={>0}] cpoint_name=<> cpoint_type=<> + [cpoint_count={>0}] + + recur_count : Recursion level for the stack overflow test. Default is 10. + + cpoint_name : Crash point where the kernel is to be crashed. It can be + one of INT_HARDWARE_ENTRY, INT_HW_IRQ_EN, INT_TASKLET_ENTRY, + FS_DEVRW, MEM_SWAPOUT, TIMERADD, SCSI_DISPATCH_CMD, + IDE_CORE_CP, DIRECT + + cpoint_type : Indicates the action to be taken on hitting the crash point. + It can be one of PANIC, BUG, EXCEPTION, LOOP, OVERFLOW, + CORRUPT_STACK, UNALIGNED_LOAD_STORE_WRITE, OVERWRITE_ALLOCATION, + WRITE_AFTER_FREE, + + cpoint_count : Indicates the number of times the crash point is to be hit + to trigger an action. The default is 10. + +You can also induce failures by mounting debugfs and writing the type to +/provoke-crash/. E.g., + + mount -t debugfs debugfs /mnt + echo EXCEPTION > /mnt/provoke-crash/INT_HARDWARE_ENTRY + + +A special file is `DIRECT' which will induce the crash directly without +KPROBE instrumentation. This mode is the only one available when the module +is built on a kernel without KPROBEs support. diff --git a/drivers/misc/lkdtm.c b/drivers/misc/lkdtm.c index 3648b23d5c92..4a0648301fdf 100644 --- a/drivers/misc/lkdtm.c +++ b/drivers/misc/lkdtm.c @@ -26,21 +26,9 @@ * It is adapted from the Linux Kernel Dump Test Tool by * Fernando Luis Vazquez Cao * - * Usage : insmod lkdtm.ko [recur_count={>0}] cpoint_name=<> cpoint_type=<> - * [cpoint_count={>0}] + * Debugfs support added by Simon Kagstrom * - * recur_count : Recursion level for the stack overflow test. Default is 10. - * - * cpoint_name : Crash point where the kernel is to be crashed. It can be - * one of INT_HARDWARE_ENTRY, INT_HW_IRQ_EN, INT_TASKLET_ENTRY, - * FS_DEVRW, MEM_SWAPOUT, TIMERADD, SCSI_DISPATCH_CMD, - * IDE_CORE_CP - * - * cpoint_type : Indicates the action to be taken on hitting the crash point. - * It can be one of PANIC, BUG, EXCEPTION, LOOP, OVERFLOW - * - * cpoint_count : Indicates the number of times the crash point is to be hit - * to trigger an action. The default is 10. + * See Documentation/fault-injection/provoke-crashes.txt for instructions */ #include @@ -53,13 +41,12 @@ #include #include #include +#include #ifdef CONFIG_IDE #include #endif -#define NUM_CPOINTS 8 -#define NUM_CPOINT_TYPES 5 #define DEFAULT_COUNT 10 #define REC_NUM_DEFAULT 10 @@ -72,7 +59,8 @@ enum cname { MEM_SWAPOUT, TIMERADD, SCSI_DISPATCH_CMD, - IDE_CORE_CP + IDE_CORE_CP, + DIRECT, }; enum ctype { @@ -81,7 +69,11 @@ enum ctype { BUG, EXCEPTION, LOOP, - OVERFLOW + OVERFLOW, + CORRUPT_STACK, + UNALIGNED_LOAD_STORE_WRITE, + OVERWRITE_ALLOCATION, + WRITE_AFTER_FREE, }; static char* cp_name[] = { @@ -92,7 +84,8 @@ static char* cp_name[] = { "MEM_SWAPOUT", "TIMERADD", "SCSI_DISPATCH_CMD", - "IDE_CORE_CP" + "IDE_CORE_CP", + "DIRECT", }; static char* cp_type[] = { @@ -100,7 +93,11 @@ static char* cp_type[] = { "BUG", "EXCEPTION", "LOOP", - "OVERFLOW" + "OVERFLOW", + "CORRUPT_STACK", + "UNALIGNED_LOAD_STORE_WRITE", + "OVERWRITE_ALLOCATION", + "WRITE_AFTER_FREE", }; static struct jprobe lkdtm; @@ -193,34 +190,66 @@ int jp_generic_ide_ioctl(ide_drive_t *drive, struct file *file, } #endif +/* Return the crashpoint number or NONE if the name is invalid */ +static enum ctype parse_cp_type(const char *what, size_t count) +{ + int i; + + for (i = 0; i < ARRAY_SIZE(cp_type); i++) { + if (!strcmp(what, cp_type[i])) + return i + 1; + } + + return NONE; +} + +static const char *cp_type_to_str(enum ctype type) +{ + if (type == NONE || type < 0 || type > ARRAY_SIZE(cp_type)) + return "None"; + + return cp_type[type - 1]; +} + +static const char *cp_name_to_str(enum cname name) +{ + if (name == INVALID || name < 0 || name > ARRAY_SIZE(cp_name)) + return "INVALID"; + + return cp_name[name - 1]; +} + + static int lkdtm_parse_commandline(void) { int i; - if (cpoint_name == NULL || cpoint_type == NULL || - cpoint_count < 1 || recur_count < 1) + if (cpoint_count < 1 || recur_count < 1) return -EINVAL; - for (i = 0; i < NUM_CPOINTS; ++i) { + count = cpoint_count; + + /* No special parameters */ + if (!cpoint_type && !cpoint_name) + return 0; + + /* Neither or both of these need to be set */ + if (!cpoint_type || !cpoint_name) + return -EINVAL; + + cptype = parse_cp_type(cpoint_type, strlen(cpoint_type)); + if (cptype == NONE) + return -EINVAL; + + for (i = 0; i < ARRAY_SIZE(cp_name); i++) { if (!strcmp(cpoint_name, cp_name[i])) { cpoint = i + 1; - break; - } - } - - for (i = 0; i < NUM_CPOINT_TYPES; ++i) { - if (!strcmp(cpoint_type, cp_type[i])) { - cptype = i + 1; - break; + return 0; } } - if (cpoint == INVALID || cptype == NONE) - return -EINVAL; - - count = cpoint_count; - - return 0; + /* Could not find a valid crash point */ + return -EINVAL; } static int recursive_loop(int a) @@ -235,53 +264,92 @@ static int recursive_loop(int a) return recursive_loop(a); } -void lkdtm_handler(void) +static void lkdtm_do_action(enum ctype which) { - printk(KERN_INFO "lkdtm : Crash point %s of type %s hit\n", - cpoint_name, cpoint_type); - --count; + switch (which) { + case PANIC: + panic("dumptest"); + break; + case BUG: + BUG(); + break; + case EXCEPTION: + *((int *) 0) = 0; + break; + case LOOP: + for (;;) + ; + break; + case OVERFLOW: + (void) recursive_loop(0); + break; + case CORRUPT_STACK: { + volatile u32 data[8]; + volatile u32 *p = data; + + p[12] = 0x12345678; + break; + } + case UNALIGNED_LOAD_STORE_WRITE: { + static u8 data[5] __attribute__((aligned(4))) = {1, 2, + 3, 4, 5}; + u32 *p; + u32 val = 0x12345678; + + p = (u32 *)(data + 1); + if (*p == 0) + val = 0x87654321; + *p = val; + break; + } + case OVERWRITE_ALLOCATION: { + size_t len = 1020; + u32 *data = kmalloc(len, GFP_KERNEL); + + data[1024 / sizeof(u32)] = 0x12345678; + kfree(data); + break; + } + case WRITE_AFTER_FREE: { + size_t len = 1024; + u32 *data = kmalloc(len, GFP_KERNEL); + + kfree(data); + schedule(); + memset(data, 0x78, len); + break; + } + case NONE: + default: + break; + } + +} + +static void lkdtm_handler(void) +{ + count--; + printk(KERN_INFO "lkdtm: Crash point %s of type %s hit, trigger in %d rounds\n", + cp_name_to_str(cpoint), cp_type_to_str(cptype), count); if (count == 0) { - switch (cptype) { - case NONE: - break; - case PANIC: - printk(KERN_INFO "lkdtm : PANIC\n"); - panic("dumptest"); - break; - case BUG: - printk(KERN_INFO "lkdtm : BUG\n"); - BUG(); - break; - case EXCEPTION: - printk(KERN_INFO "lkdtm : EXCEPTION\n"); - *((int *) 0) = 0; - break; - case LOOP: - printk(KERN_INFO "lkdtm : LOOP\n"); - for (;;); - break; - case OVERFLOW: - printk(KERN_INFO "lkdtm : OVERFLOW\n"); - (void) recursive_loop(0); - break; - default: - break; - } + lkdtm_do_action(cptype); count = cpoint_count; } } -static int __init lkdtm_module_init(void) +static int lkdtm_register_cpoint(enum cname which) { int ret; - if (lkdtm_parse_commandline() == -EINVAL) { - printk(KERN_INFO "lkdtm : Invalid command\n"); - return -EINVAL; - } + cpoint = INVALID; + if (lkdtm.entry != NULL) + unregister_jprobe(&lkdtm); - switch (cpoint) { + switch (which) { + case DIRECT: + lkdtm_do_action(cptype); + return 0; case INT_HARDWARE_ENTRY: lkdtm.kp.symbol_name = "do_IRQ"; lkdtm.entry = (kprobe_opcode_t*) jp_do_irq; @@ -315,28 +383,268 @@ static int __init lkdtm_module_init(void) lkdtm.kp.symbol_name = "generic_ide_ioctl"; lkdtm.entry = (kprobe_opcode_t*) jp_generic_ide_ioctl; #else - printk(KERN_INFO "lkdtm : Crash point not available\n"); + printk(KERN_INFO "lkdtm: Crash point not available\n"); + return -EINVAL; #endif break; default: - printk(KERN_INFO "lkdtm : Invalid Crash Point\n"); - break; + printk(KERN_INFO "lkdtm: Invalid Crash Point\n"); + return -EINVAL; } + cpoint = which; if ((ret = register_jprobe(&lkdtm)) < 0) { - printk(KERN_INFO "lkdtm : Couldn't register jprobe\n"); - return ret; + printk(KERN_INFO "lkdtm: Couldn't register jprobe\n"); + cpoint = INVALID; + } + + return ret; +} + +static ssize_t do_register_entry(enum cname which, struct file *f, + const char __user *user_buf, size_t count, loff_t *off) +{ + char *buf; + int err; + + if (count >= PAGE_SIZE) + return -EINVAL; + + buf = (char *)__get_free_page(GFP_KERNEL); + if (!buf) + return -ENOMEM; + if (copy_from_user(buf, user_buf, count)) { + free_page((unsigned long) buf); + return -EFAULT; + } + /* NULL-terminate and remove enter */ + buf[count] = '\0'; + strim(buf); + + cptype = parse_cp_type(buf, count); + free_page((unsigned long) buf); + + if (cptype == NONE) + return -EINVAL; + + err = lkdtm_register_cpoint(which); + if (err < 0) + return err; + + *off += count; + + return count; +} + +/* Generic read callback that just prints out the available crash types */ +static ssize_t lkdtm_debugfs_read(struct file *f, char __user *user_buf, + size_t count, loff_t *off) +{ + char *buf; + int i, n, out; + + buf = (char *)__get_free_page(GFP_KERNEL); + + n = snprintf(buf, PAGE_SIZE, "Available crash types:\n"); + for (i = 0; i < ARRAY_SIZE(cp_type); i++) + n += snprintf(buf + n, PAGE_SIZE - n, "%s\n", cp_type[i]); + buf[n] = '\0'; + + out = simple_read_from_buffer(user_buf, count, off, + buf, n); + free_page((unsigned long) buf); + + return out; +} + +static int lkdtm_debugfs_open(struct inode *inode, struct file *file) +{ + return 0; +} + + +static ssize_t int_hardware_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(INT_HARDWARE_ENTRY, f, buf, count, off); +} + +static ssize_t int_hw_irq_en(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(INT_HW_IRQ_EN, f, buf, count, off); +} + +static ssize_t int_tasklet_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(INT_TASKLET_ENTRY, f, buf, count, off); +} + +static ssize_t fs_devrw_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(FS_DEVRW, f, buf, count, off); +} + +static ssize_t mem_swapout_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(MEM_SWAPOUT, f, buf, count, off); +} + +static ssize_t timeradd_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(TIMERADD, f, buf, count, off); +} + +static ssize_t scsi_dispatch_cmd_entry(struct file *f, + const char __user *buf, size_t count, loff_t *off) +{ + return do_register_entry(SCSI_DISPATCH_CMD, f, buf, count, off); +} + +static ssize_t ide_core_cp_entry(struct file *f, const char __user *buf, + size_t count, loff_t *off) +{ + return do_register_entry(IDE_CORE_CP, f, buf, count, off); +} + +/* Special entry to just crash directly. Available without KPROBEs */ +static ssize_t direct_entry(struct file *f, const char __user *user_buf, + size_t count, loff_t *off) +{ + enum ctype type; + char *buf; + + if (count >= PAGE_SIZE) + return -EINVAL; + if (count < 1) + return -EINVAL; + + buf = (char *)__get_free_page(GFP_KERNEL); + if (!buf) + return -ENOMEM; + if (copy_from_user(buf, user_buf, count)) { + free_page((unsigned long) buf); + return -EFAULT; + } + /* NULL-terminate and remove enter */ + buf[count] = '\0'; + strim(buf); + + type = parse_cp_type(buf, count); + free_page((unsigned long) buf); + if (type == NONE) + return -EINVAL; + + printk(KERN_INFO "lkdtm: Performing direct entry %s\n", + cp_type_to_str(type)); + lkdtm_do_action(type); + *off += count; + + return count; +} + +struct crash_entry { + const char *name; + const struct file_operations fops; +}; + +static const struct crash_entry crash_entries[] = { + {"DIRECT", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = direct_entry} }, + {"INT_HARDWARE_ENTRY", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = int_hardware_entry} }, + {"INT_HW_IRQ_EN", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = int_hw_irq_en} }, + {"INT_TASKLET_ENTRY", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = int_tasklet_entry} }, + {"FS_DEVRW", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = fs_devrw_entry} }, + {"MEM_SWAPOUT", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = mem_swapout_entry} }, + {"TIMERADD", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = timeradd_entry} }, + {"SCSI_DISPATCH_CMD", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = scsi_dispatch_cmd_entry} }, + {"IDE_CORE_CP", {.read = lkdtm_debugfs_read, + .open = lkdtm_debugfs_open, + .write = ide_core_cp_entry} }, +}; + +static struct dentry *lkdtm_debugfs_root; + +static int __init lkdtm_module_init(void) +{ + int ret = -EINVAL; + int n_debugfs_entries = 1; /* Assume only the direct entry */ + int i; + + /* Register debugfs interface */ + lkdtm_debugfs_root = debugfs_create_dir("provoke-crash", NULL); + if (!lkdtm_debugfs_root) { + printk(KERN_ERR "lkdtm: creating root dir failed\n"); + return -ENODEV; + } + +#ifdef CONFIG_KPROBES + n_debugfs_entries = ARRAY_SIZE(crash_entries); +#endif + + for (i = 0; i < n_debugfs_entries; i++) { + const struct crash_entry *cur = &crash_entries[i]; + struct dentry *de; + + de = debugfs_create_file(cur->name, 0644, lkdtm_debugfs_root, + NULL, &cur->fops); + if (de == NULL) { + printk(KERN_ERR "lkdtm: could not create %s\n", + cur->name); + goto out_err; + } + } + + if (lkdtm_parse_commandline() == -EINVAL) { + printk(KERN_INFO "lkdtm: Invalid command\n"); + goto out_err; + } + + if (cpoint != INVALID && cptype != NONE) { + ret = lkdtm_register_cpoint(cpoint); + if (ret < 0) { + printk(KERN_INFO "lkdtm: Invalid crash point %d\n", + cpoint); + goto out_err; + } + printk(KERN_INFO "lkdtm: Crash point %s of type %s registered\n", + cpoint_name, cpoint_type); + } else { + printk(KERN_INFO "lkdtm: No crash points registered, enable through debugfs\n"); } - printk(KERN_INFO "lkdtm : Crash point %s of type %s registered\n", - cpoint_name, cpoint_type); return 0; + +out_err: + debugfs_remove_recursive(lkdtm_debugfs_root); + return ret; } static void __exit lkdtm_module_exit(void) { - unregister_jprobe(&lkdtm); - printk(KERN_INFO "lkdtm : Crash point unregistered\n"); + debugfs_remove_recursive(lkdtm_debugfs_root); + + unregister_jprobe(&lkdtm); + printk(KERN_INFO "lkdtm: Crash point unregistered\n"); } module_init(lkdtm_module_init); diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 5e3407d997b2..b520ec1f33c5 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -864,8 +864,7 @@ config DEBUG_FORCE_WEAK_PER_CPU config LKDTM tristate "Linux Kernel Dump Test Tool Module" - depends on DEBUG_KERNEL - depends on KPROBES + depends on DEBUG_FS depends on BLOCK default n help @@ -876,7 +875,7 @@ config LKDTM called lkdtm. Documentation on how to use the module can be found in - drivers/misc/lkdtm.c + Documentation/fault-injection/provoke-crashes.txt config FAULT_INJECTION bool "Fault-injection framework" -- cgit v1.2.3 From a11d2b64e1f2556953120d516241243ea365f0ae Mon Sep 17 00:00:00 2001 From: André Goddard Rosa Date: Fri, 5 Mar 2010 13:43:11 -0800 Subject: lib/string.c: simplify stricmp() Removes 32 bytes on core2 with gcc 4.4.1: text data bss dec hex filename 3196 0 0 3196 c7c lib/string-BEFORE.o 3164 0 0 3164 c5c lib/string-AFTER.o Signed-off-by: André Goddard Rosa Cc: Joe Perches Cc: Frederic Weisbecker Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/string.c | 34 +++++++++++++++------------------- 1 file changed, 15 insertions(+), 19 deletions(-) (limited to 'lib') diff --git a/lib/string.c b/lib/string.c index a1cdcfcc42d0..0f8624532082 100644 --- a/lib/string.c +++ b/lib/string.c @@ -36,25 +36,21 @@ int strnicmp(const char *s1, const char *s2, size_t len) /* Yes, Virginia, it had better be unsigned */ unsigned char c1, c2; - c1 = c2 = 0; - if (len) { - do { - c1 = *s1; - c2 = *s2; - s1++; - s2++; - if (!c1) - break; - if (!c2) - break; - if (c1 == c2) - continue; - c1 = tolower(c1); - c2 = tolower(c2); - if (c1 != c2) - break; - } while (--len); - } + if (!len) + return 0; + + do { + c1 = *s1++; + c2 = *s2++; + if (!c1 || !c2) + break; + if (c1 == c2) + continue; + c1 = tolower(c1); + c2 = tolower(c2); + if (c1 != c2) + break; + } while (--len); return (int)c1 - (int)c2; } EXPORT_SYMBOL(strnicmp); -- cgit v1.2.3 From d6a2eedfddcded92c8f9b0ac022a99c4134696b0 Mon Sep 17 00:00:00 2001 From: André Goddard Rosa Date: Fri, 5 Mar 2010 13:43:12 -0800 Subject: lib/string.c: simplify strnstr() Signed-off-by: André Goddard Rosa Cc: Li Zefan Cc: Joe Perches Cc: Frederic Weisbecker Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/string.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/string.c b/lib/string.c index 0f8624532082..f71bead1be3e 100644 --- a/lib/string.c +++ b/lib/string.c @@ -689,13 +689,13 @@ EXPORT_SYMBOL(strstr); */ char *strnstr(const char *s1, const char *s2, size_t len) { - size_t l1 = len, l2; + size_t l2; l2 = strlen(s2); if (!l2) return (char *)s1; - while (l1 >= l2) { - l1--; + while (len >= l2) { + len--; if (!memcmp(s1, s2, l2)) return (char *)s1; s1++; -- cgit v1.2.3 From 835cc0c8477fdbc59e0217891d6f11061b1ac4e2 Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 5 Mar 2010 13:43:15 -0800 Subject: lib: more scalable list_sort() XFS and UBIFS can pass long lists to list_sort(); this alternative implementation scales better, reaching ~3x performance gain when list length exceeds the L2 cache size. Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 581 bytes compared to 455 for Mark J. Roberts' code. Worst case for either implementation is a list length just over a power of two, and to roughly the same degree, so here are timing results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; initial order was random. time (msec) Tatham-Roberts | generic-Mullis-v2 loop_count length | | ratio 4000000 2 206 294 1.427 2000000 3 176 227 1.289 1000000 5 199 172 0.864 500000 9 235 178 0.757 250000 17 243 182 0.748 125000 33 261 196 0.750 62500 65 277 209 0.754 31250 129 292 219 0.75 15625 257 317 235 0.741 7812 513 340 252 0.741 3906 1025 362 267 0.737 1953 2049 388 283 0.729 ~ L1 size 976 4097 556 323 0.580 488 8193 678 361 0.532 244 16385 773 395 0.510 122 32769 844 418 0.495 61 65537 917 454 0.495 30 131073 1128 543 0.481 15 262145 2355 869 0.369 ~ L2 size 7 524289 5597 1714 0.306 3 1048577 6218 2022 0.325 Mark's code does not actually implement the usual or generic mergesort, but rather a variant from Simon Tatham described here: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Simon's algorithm performs O(log N) passes over the entire input list, doing merges of sublists that double in size on each pass. The generic algorithm instead merges pairs of equal length lists as early as possible, in recursive order. For either algorithm, the elements that extend the list beyond power-of-two length are a special case, handled as nearly as possible as a "rounding-up" to a full POT. Some intuition for the locality of reference implications of merge order may be gotten by watching this animation: http://www.sorting-algorithms.com/merge-sort Simon's algorithm requires only O(1) extra space rather than the generic algorithm's O(log N), but in my non-recursive implementation the actual O(log N) data is merely a vector of ~20 pointers, which I've put on the stack. Long-running list_sort() calls: If the list passed in may be long, or the client's cmp() callback function is slow, the client's cmp() may periodically invoke cond_resched() to voluntarily yield the CPU. All inner loops of list_sort() call back to cmp(). Stability of the sort: distinct elements that compare equal emerge from the sort in the same order as with Mark's code, for simple test cases. A boot-time test is provided to verify this and other correctness requirements. A kernel that uses drm.ko appears to run normally with this change; I have no suitable hardware to similarly test the use by UBIFS. [akpm@linux-foundation.org: style tweaks, fix comment, make list_sort_test __init] Signed-off-by: Don Mullis Cc: Dave Airlie Cc: Andi Kleen Cc: Dave Chinner Cc: Artem Bityutskiy Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 252 ++++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 183 insertions(+), 69 deletions(-) (limited to 'lib') diff --git a/lib/list_sort.c b/lib/list_sort.c index 19d11e0bb958..362c10f1653f 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -4,99 +4,213 @@ #include #include +#define MAX_LIST_LENGTH_BITS 20 + +/* + * Returns a list organized in an intermediate format suited + * to chaining of merge() calls: null-terminated, no reserved or + * sentinel head node, "prev" links not maintained. + */ +static struct list_head *merge(void *priv, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b), + struct list_head *a, struct list_head *b) +{ + struct list_head head, *tail = &head; + + while (a && b) { + /* if equal, take 'a' -- important for sort stability */ + if ((*cmp)(priv, a, b) <= 0) { + tail->next = a; + a = a->next; + } else { + tail->next = b; + b = b->next; + } + tail = tail->next; + } + tail->next = a?:b; + return head.next; +} + +/* + * Combine final list merge with restoration of standard doubly-linked + * list structure. This approach duplicates code from merge(), but + * runs faster than the tidier alternatives of either a separate final + * prev-link restoration pass, or maintaining the prev links + * throughout. + */ +static void merge_and_restore_back_links(void *priv, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b), + struct list_head *head, + struct list_head *a, struct list_head *b) +{ + struct list_head *tail = head; + + while (a && b) { + /* if equal, take 'a' -- important for sort stability */ + if ((*cmp)(priv, a, b) <= 0) { + tail->next = a; + a->prev = tail; + a = a->next; + } else { + tail->next = b; + b->prev = tail; + b = b->next; + } + tail = tail->next; + } + tail->next = a ? : b; + + do { + /* + * In worst cases this loop may run many iterations. + * Continue callbacks to the client even though no + * element comparison is needed, so the client's cmp() + * routine can invoke cond_resched() periodically. + */ + (*cmp)(priv, tail, tail); + + tail->next->prev = tail; + tail = tail->next; + } while (tail->next); + + tail->next = head; + head->prev = tail; +} + /** * list_sort - sort a list. * @priv: private data, passed to @cmp * @head: the list to sort * @cmp: the elements comparison function * - * This function has been implemented by Mark J Roberts . It - * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted - * in ascending order. + * This function implements "merge sort" which has O(nlog(n)) complexity. + * The list is sorted in ascending order. * * The comparison function @cmp is supposed to return a negative value if @a is * less than @b, and a positive value if @a is greater than @b. If @a and @b * are equivalent, then it does not matter what this function returns. */ void list_sort(void *priv, struct list_head *head, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b)) + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b)) { - struct list_head *p, *q, *e, *list, *tail, *oldhead; - int insize, nmerges, psize, qsize, i; + struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists + -- last slot is a sentinel */ + int lev; /* index into part[] */ + int max_lev = 0; + struct list_head *list; if (list_empty(head)) return; + memset(part, 0, sizeof(part)); + + head->prev->next = NULL; list = head->next; - list_del(head); - insize = 1; - for (;;) { - p = oldhead = list; - list = tail = NULL; - nmerges = 0; - - while (p) { - nmerges++; - q = p; - psize = 0; - for (i = 0; i < insize; i++) { - psize++; - q = q->next == oldhead ? NULL : q->next; - if (!q) - break; - } - qsize = insize; - while (psize > 0 || (qsize > 0 && q)) { - if (!psize) { - e = q; - q = q->next; - qsize--; - if (q == oldhead) - q = NULL; - } else if (!qsize || !q) { - e = p; - p = p->next; - psize--; - if (p == oldhead) - p = NULL; - } else if (cmp(priv, p, q) <= 0) { - e = p; - p = p->next; - psize--; - if (p == oldhead) - p = NULL; - } else { - e = q; - q = q->next; - qsize--; - if (q == oldhead) - q = NULL; - } - if (tail) - tail->next = e; - else - list = e; - e->prev = tail; - tail = e; + while (list) { + struct list_head *cur = list; + list = list->next; + cur->next = NULL; + + for (lev = 0; part[lev]; lev++) { + cur = merge(priv, cmp, part[lev], cur); + part[lev] = NULL; + } + if (lev > max_lev) { + if (unlikely(lev >= ARRAY_SIZE(part)-1)) { + printk_once(KERN_DEBUG "list passed to" + " list_sort() too long for" + " efficiency\n"); + lev--; } - p = q; + max_lev = lev; } + part[lev] = cur; + } - tail->next = list; - list->prev = tail; + for (lev = 0; lev < max_lev; lev++) + if (part[lev]) + list = merge(priv, cmp, part[lev], list); - if (nmerges <= 1) - break; + merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); +} +EXPORT_SYMBOL(list_sort); - insize *= 2; - } +#ifdef DEBUG_LIST_SORT +struct debug_el { + struct list_head l_h; + int value; + unsigned serial; +}; - head->next = list; - head->prev = list->prev; - list->prev->next = head; - list->prev = head; +static int cmp(void *priv, struct list_head *a, struct list_head *b) +{ + return container_of(a, struct debug_el, l_h)->value + - container_of(b, struct debug_el, l_h)->value; } -EXPORT_SYMBOL(list_sort); +/* + * The pattern of set bits in the list length determines which cases + * are hit in list_sort(). + */ +#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */ + +static int __init list_sort_test(void) +{ + int i, r = 1, count; + struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL); + struct list_head *cur; + + printk(KERN_WARNING "testing list_sort()\n"); + + cur = head; + for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) { + struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL); + BUG_ON(!el); + /* force some equivalencies */ + el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3); + el->serial = i; + + el->l_h.prev = cur; + cur->next = &el->l_h; + cur = cur->next; + } + head->prev = cur; + + list_sort(NULL, head, cmp); + + count = 1; + for (cur = head->next; cur->next != head; cur = cur->next) { + struct debug_el *el = container_of(cur, struct debug_el, l_h); + int cmp_result = cmp(NULL, cur, cur->next); + if (cur->next->prev != cur) { + printk(KERN_EMERG "list_sort() returned " + "a corrupted list!\n"); + return 1; + } else if (cmp_result > 0) { + printk(KERN_EMERG "list_sort() failed to sort!\n"); + return 1; + } else if (cmp_result == 0 && + el->serial >= container_of(cur->next, + struct debug_el, l_h)->serial) { + printk(KERN_EMERG "list_sort() failed to preserve order" + " of equivalent elements!\n"); + return 1; + } + kfree(cur->prev); + count++; + } + kfree(cur); + if (count != LIST_SORT_TEST_LENGTH) { + printk(KERN_EMERG "list_sort() returned list of" + "different length!\n"); + return 1; + } + return 0; +} +module_init(list_sort_test); +#endif -- cgit v1.2.3 From 02b12b7a28faa2e9ed5a361cd08ea576ab1f1509 Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 5 Mar 2010 13:43:15 -0800 Subject: lib: revise list_sort() header comment Clarify and correct header comment of list_sort(). Signed-off-by: Don Mullis Cc: Dave Airlie Cc: Andi Kleen Cc: Dave Chinner Cc: Artem Bityutskiy Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/list_sort.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'lib') diff --git a/lib/list_sort.c b/lib/list_sort.c index 362c10f1653f..4b5cb794c38b 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -81,17 +81,18 @@ static void merge_and_restore_back_links(void *priv, } /** - * list_sort - sort a list. - * @priv: private data, passed to @cmp + * list_sort - sort a list + * @priv: private data, opaque to list_sort(), passed to @cmp * @head: the list to sort * @cmp: the elements comparison function * - * This function implements "merge sort" which has O(nlog(n)) complexity. - * The list is sorted in ascending order. + * This function implements "merge sort", which has O(nlog(n)) + * complexity. * - * The comparison function @cmp is supposed to return a negative value if @a is - * less than @b, and a positive value if @a is greater than @b. If @a and @b - * are equivalent, then it does not matter what this function returns. + * The comparison function @cmp must return a negative value if @a + * should sort before @b, and a positive value if @a should sort after + * @b. If @a and @b are equivalent, and their original relative + * ordering is to be preserved, @cmp must return 0. */ void list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, struct list_head *a, -- cgit v1.2.3 From a069c266ae5fdfbf5b4aecf2c672413aa33b2504 Mon Sep 17 00:00:00 2001 From: Don Mullis Date: Fri, 5 Mar 2010 13:43:16 -0800 Subject: lib: build list_sort() only if needed Build list_sort() only for configs that need it -- those that don't save ~581 bytes (i386). Signed-off-by: Don Mullis Cc: Dave Airlie Cc: Andi Kleen Cc: Dave Chinner Cc: Artem Bityutskiy Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- drivers/gpu/drm/Kconfig | 1 + fs/ubifs/Kconfig | 1 + lib/Kconfig | 3 +++ lib/Makefile | 3 ++- 4 files changed, 7 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig index 305c59003963..3d2ab03f1296 100644 --- a/drivers/gpu/drm/Kconfig +++ b/drivers/gpu/drm/Kconfig @@ -9,6 +9,7 @@ menuconfig DRM depends on (AGP || AGP=n) && PCI && !EMULATED_CMPXCHG && MMU select I2C select I2C_ALGOBIT + select LIST_SORT help Kernel-level support for the Direct Rendering Infrastructure (DRI) introduced in XFree86 4.0. If you say Y here, you need to select diff --git a/fs/ubifs/Kconfig b/fs/ubifs/Kconfig index 830e3f76f442..430c69f39842 100644 --- a/fs/ubifs/Kconfig +++ b/fs/ubifs/Kconfig @@ -7,6 +7,7 @@ config UBIFS_FS select CRYPTO if UBIFS_FS_ZLIB select CRYPTO_LZO if UBIFS_FS_LZO select CRYPTO_DEFLATE if UBIFS_FS_ZLIB + select LIST_SORT depends on MTD_UBI help UBIFS is a file system for flash devices which works on top of UBI. diff --git a/lib/Kconfig b/lib/Kconfig index 97b136ff117e..8034c46327cb 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -160,6 +160,9 @@ config TEXTSEARCH_BM config TEXTSEARCH_FSM tristate +config LIST_SORT + boolean + config HAS_IOMEM boolean depends on !NO_IOMEM diff --git a/lib/Makefile b/lib/Makefile index 3b0b4a696db9..e39c361b0be3 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o list_sort.o + string_helpers.o gcd.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG @@ -40,6 +40,7 @@ lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o +obj-$(CONFIG_LIST_SORT) += list_sort.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_DEBUG_LIST) += list_debug.o -- cgit v1.2.3 From 9a86e2bad0b9fbf3290ae496da6dab9536dd6bf7 Mon Sep 17 00:00:00 2001 From: Ben Hutchings Date: Fri, 5 Mar 2010 13:43:17 -0800 Subject: lib: fix first line of kernel-doc for a few functions The function name must be followed by a space, hypen, space, and a short description. Signed-off-by: Ben Hutchings Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/list.h | 6 +++--- lib/bitmap.c | 6 +++--- 2 files changed, 6 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/include/linux/list.h b/include/linux/list.h index 5d9c6558e8ab..8392884a2977 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -498,7 +498,7 @@ static inline void list_splice_tail_init(struct list_head *list, pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** - * list_for_each_entry_safe_continue + * list_for_each_entry_safe_continue - continue list iteration safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. @@ -514,7 +514,7 @@ static inline void list_splice_tail_init(struct list_head *list, pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** - * list_for_each_entry_safe_from + * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. @@ -529,7 +529,7 @@ static inline void list_splice_tail_init(struct list_head *list, pos = n, n = list_entry(n->member.next, typeof(*n), member)) /** - * list_for_each_entry_safe_reverse + * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. diff --git a/lib/bitmap.c b/lib/bitmap.c index 11bf49750583..61998c5924fe 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -487,7 +487,7 @@ int __bitmap_parse(const char *buf, unsigned int buflen, EXPORT_SYMBOL(__bitmap_parse); /** - * bitmap_parse_user() + * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap * * @ubuf: pointer to user buffer containing string. * @ulen: buffer size in bytes. If string is smaller than this @@ -619,7 +619,7 @@ int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) EXPORT_SYMBOL(bitmap_parselist); /** - * bitmap_pos_to_ord(buf, pos, bits) + * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap * @buf: pointer to a bitmap * @pos: a bit position in @buf (0 <= @pos < @bits) * @bits: number of valid bit positions in @buf @@ -655,7 +655,7 @@ static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits) } /** - * bitmap_ord_to_pos(buf, ord, bits) + * bitmap_ord_to_pos - find position of n-th set bit in bitmap * @buf: pointer to bitmap * @ord: ordinal bit position (n-th set bit, n >= 0) * @bits: number of valid bit positions in @buf -- cgit v1.2.3 From 08564fb7ab9ead9226b6154439c3fecd17972eb0 Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Fri, 5 Mar 2010 13:43:18 -0800 Subject: bitmap: use for_each_set_bit() Replace open-coded loop with for_each_set_bit(). Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/bitmap.c | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index 61998c5924fe..ffb78c916ccd 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -733,10 +733,9 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src, bitmap_zero(dst, bits); w = bitmap_weight(new, bits); - for (oldbit = find_first_bit(src, bits); - oldbit < bits; - oldbit = find_next_bit(src, bits, oldbit + 1)) { + for_each_set_bit(oldbit, src, bits) { int n = bitmap_pos_to_ord(old, oldbit, bits); + if (n < 0 || w == 0) set_bit(oldbit, dst); /* identity map */ else @@ -903,9 +902,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig, */ m = 0; - for (n = find_first_bit(relmap, bits); - n < bits; - n = find_next_bit(relmap, bits, n + 1)) { + for_each_set_bit(n, relmap, bits) { /* m == bitmap_pos_to_ord(relmap, n, bits) */ if (test_bit(m, orig)) set_bit(n, dst); @@ -934,9 +931,7 @@ void bitmap_fold(unsigned long *dst, const unsigned long *orig, return; bitmap_zero(dst, bits); - for (oldbit = find_first_bit(orig, bits); - oldbit < bits; - oldbit = find_next_bit(orig, bits, oldbit + 1)) + for_each_set_bit(oldbit, orig, bits) set_bit(oldbit % sz, dst); } EXPORT_SYMBOL(bitmap_fold); -- cgit v1.2.3 From 4f2a9463d18517a9839401c3de6419ee1435875b Mon Sep 17 00:00:00 2001 From: Joakim Tjernlund Date: Fri, 5 Mar 2010 13:43:55 -0800 Subject: crc32: some minor cleanups Signed-off-by: Joakim Tjernlund Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/crc32.c | 30 ++++++++++++++---------------- 1 file changed, 14 insertions(+), 16 deletions(-) (limited to 'lib') diff --git a/lib/crc32.c b/lib/crc32.c index 02e3b31b3a79..0f45fbff34cb 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -30,11 +30,15 @@ #include #include "crc32defs.h" #if CRC_LE_BITS == 8 -#define tole(x) __constant_cpu_to_le32(x) -#define tobe(x) __constant_cpu_to_be32(x) +# define tole(x) __constant_cpu_to_le32(x) #else -#define tole(x) (x) -#define tobe(x) (x) +# define tole(x) (x) +#endif + +#if CRC_BE_BITS == 8 +# define tobe(x) __constant_cpu_to_be32(x) +#else +# define tobe(x) (x) #endif #include "crc32table.h" @@ -52,20 +56,19 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab) # else # define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) # endif - const u32 *b = (const u32 *)buf; + const u32 *b; size_t rem_len; /* Align it */ - if (unlikely((long)b & 3 && len)) { - u8 *p = (u8 *)b; + if (unlikely((long)buf & 3 && len)) { do { - DO_CRC(*p++); - } while ((--len) && ((long)p)&3); - b = (u32 *)p; + DO_CRC(*buf++); + } while ((--len) && ((long)buf)&3); } rem_len = len & 3; /* load data 32 bits wide, xor data 32 bits wide. */ len = len >> 2; + b = (const u32 *)buf; for (--b; len; --len) { crc ^= *++b; /* use pre increment for speed */ DO_CRC(0); @@ -82,6 +85,7 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 *tab) } while (--len); } return crc; +#undef DO_CRC } #endif /** @@ -119,9 +123,6 @@ u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len) crc = __cpu_to_le32(crc); crc = crc32_body(crc, p, len, tab); return __le32_to_cpu(crc); -#undef ENDIAN_SHIFT -#undef DO_CRC - # elif CRC_LE_BITS == 4 while (len--) { crc ^= *p++; @@ -179,9 +180,6 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len) crc = __cpu_to_be32(crc); crc = crc32_body(crc, p, len, tab); return __be32_to_cpu(crc); -#undef ENDIAN_SHIFT -#undef DO_CRC - # elif CRC_BE_BITS == 4 while (len--) { crc ^= *p++ << 24; -- cgit v1.2.3 From ef0658f3de484bf9b173639cd47544584e01efa5 Mon Sep 17 00:00:00 2001 From: Joe Perches Date: Sat, 6 Mar 2010 17:10:14 -0800 Subject: vsprintf.c: Reduce sizeof struct printf_spec from 24 to 8 bytes Reducing the size of struct printf_spec is a good thing because multiple instances are commonly passed on stack. It's possible for type to be u8 and field_width to be s8, but this is likely small enough for now. Signed-off-by: Joe Perches Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index af4aaa6c36f3..e994cea385c8 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -408,12 +408,12 @@ enum format_type { }; struct printf_spec { - enum format_type type; - int flags; /* flags to number() */ - int field_width; /* width of output field */ - int base; - int precision; /* # of digits/chars */ - int qualifier; + u16 type; + s16 field_width; /* width of output field */ + u8 flags; /* flags to number() */ + u8 base; + s8 precision; /* # of digits/chars */ + u8 qualifier; }; static char *number(char *buf, char *end, unsigned long long num, @@ -1333,7 +1333,7 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) break; case FORMAT_TYPE_NRCHARS: { - int qualifier = spec.qualifier; + u8 qualifier = spec.qualifier; if (qualifier == 'l') { long *ip = va_arg(args, long *); @@ -1619,7 +1619,7 @@ do { \ case FORMAT_TYPE_NRCHARS: { /* skip %n 's argument */ - int qualifier = spec.qualifier; + u8 qualifier = spec.qualifier; void *skip_arg; if (qualifier == 'l') skip_arg = va_arg(args, long *); @@ -1885,7 +1885,9 @@ int vsscanf(const char *buf, const char *fmt, va_list args) char *next; char digit; int num = 0; - int qualifier, base, field_width; + u8 qualifier; + u8 base; + s16 field_width; bool is_sign; while (*fmt && *str) { @@ -1963,7 +1965,7 @@ int vsscanf(const char *buf, const char *fmt, va_list args) { char *s = (char *)va_arg(args, char *); if (field_width == -1) - field_width = INT_MAX; + field_width = SHORT_MAX; /* first, skip leading white space in buffer */ str = skip_spaces(str); -- cgit v1.2.3 From b89dc5d6b0981c1096ccffbf8f4413c7bb1bcc0a Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Fri, 5 Mar 2010 10:47:31 -0700 Subject: vsprintf: clarify comments for printf_spec flags Add clues about what the SMALL and SPECIAL flags do. Signed-off-by: Bjorn Helgaas Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index e994cea385c8..a900d136e643 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -381,8 +381,8 @@ static noinline char *put_dec(char *buf, unsigned long long num) #define PLUS 4 /* show plus */ #define SPACE 8 /* space if plus */ #define LEFT 16 /* left justified */ -#define SMALL 32 /* Must be 32 == 0x20 */ -#define SPECIAL 64 /* 0x */ +#define SMALL 32 /* use lowercase in hex (must be 32 == 0x20) */ +#define SPECIAL 64 /* prefix hex with "0x", octal with "0" */ enum format_type { FORMAT_TYPE_NONE, /* Just a string part */ -- cgit v1.2.3 From 4da0b66c6e9ea7ba78a19f9f186779826d89f8b0 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Fri, 5 Mar 2010 10:47:37 -0700 Subject: vsprintf: move %pR resource printf_specs off the stack This adds separate I/O and memory specs, so we don't have to change the field width in a shared spec, which then lets us make all the specs const and static, since they never change. Signed-off-by: Bjorn Helgaas Signed-off-by: Linus Torvalds --- lib/vsprintf.c | 45 ++++++++++++++++++++++++--------------------- 1 file changed, 24 insertions(+), 21 deletions(-) (limited to 'lib') diff --git a/lib/vsprintf.c b/lib/vsprintf.c index a900d136e643..0d461c7c14db 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -597,22 +597,29 @@ static char *resource_string(char *buf, char *end, struct resource *res, #ifndef MEM_RSRC_PRINTK_SIZE #define MEM_RSRC_PRINTK_SIZE 10 #endif - struct printf_spec hex_spec = { + static const struct printf_spec io_spec = { .base = 16, + .field_width = IO_RSRC_PRINTK_SIZE, .precision = -1, .flags = SPECIAL | SMALL | ZEROPAD, }; - struct printf_spec dec_spec = { + static const struct printf_spec mem_spec = { + .base = 16, + .field_width = MEM_RSRC_PRINTK_SIZE, + .precision = -1, + .flags = SPECIAL | SMALL | ZEROPAD, + }; + static const struct printf_spec dec_spec = { .base = 10, .precision = -1, .flags = 0, }; - struct printf_spec str_spec = { + static const struct printf_spec str_spec = { .field_width = -1, .precision = 10, .flags = LEFT, }; - struct printf_spec flag_spec = { + static const struct printf_spec flag_spec = { .base = 16, .precision = -1, .flags = SPECIAL | SMALL, @@ -628,35 +635,31 @@ static char *resource_string(char *buf, char *end, struct resource *res, 2*RSRC_BUF_SIZE + FLAG_BUF_SIZE + RAW_BUF_SIZE)]; char *p = sym, *pend = sym + sizeof(sym); - int size = -1, addr = 0; int decode = (fmt[0] == 'R') ? 1 : 0; - - if (res->flags & IORESOURCE_IO) { - size = IO_RSRC_PRINTK_SIZE; - addr = 1; - } else if (res->flags & IORESOURCE_MEM) { - size = MEM_RSRC_PRINTK_SIZE; - addr = 1; - } + const struct printf_spec *specp; *p++ = '['; - if (res->flags & IORESOURCE_IO) + if (res->flags & IORESOURCE_IO) { p = string(p, pend, "io ", str_spec); - else if (res->flags & IORESOURCE_MEM) + specp = &io_spec; + } else if (res->flags & IORESOURCE_MEM) { p = string(p, pend, "mem ", str_spec); - else if (res->flags & IORESOURCE_IRQ) + specp = &mem_spec; + } else if (res->flags & IORESOURCE_IRQ) { p = string(p, pend, "irq ", str_spec); - else if (res->flags & IORESOURCE_DMA) + specp = &dec_spec; + } else if (res->flags & IORESOURCE_DMA) { p = string(p, pend, "dma ", str_spec); - else { + specp = &dec_spec; + } else { p = string(p, pend, "??? ", str_spec); + specp = &mem_spec; decode = 0; } - hex_spec.field_width = size; - p = number(p, pend, res->start, addr ? hex_spec : dec_spec); + p = number(p, pend, res->start, *specp); if (res->start != res->end) { *p++ = '-'; - p = number(p, pend, res->end, addr ? hex_spec : dec_spec); + p = number(p, pend, res->end, *specp); } if (decode) { if (res->flags & IORESOURCE_MEM_64) -- cgit v1.2.3 From b8fa05719ba4349be80ce929237249b57886a203 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 7 Mar 2010 09:54:44 -0800 Subject: Revert "lib: build list_sort() only if needed" This reverts commit a069c266ae5fdfbf5b4aecf2c672413aa33b2504. It turns ou that not only was it missing a case (XFS) that needed it, but perhaps more importantly, people sometimes want to enable new modules that they hadn't had enabled before, and if such a module uses list_sort(), it can't easily be inserted any more. So rather than add a "select LIST_SORT" to the XFS case, just leave it compiled in. It's not all _that_ big, after all, and the inconvenience isn't worth it. Requested-by: Alexey Dobriyan Cc: Christoph Hellwig Cc: Don Mullis Cc: Andrew Morton Cc: Dave Chinner Signed-off-by: Linus Torvalds --- drivers/gpu/drm/Kconfig | 1 - fs/ubifs/Kconfig | 1 - lib/Kconfig | 3 --- lib/Makefile | 3 +-- 4 files changed, 1 insertion(+), 7 deletions(-) (limited to 'lib') diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig index 3d2ab03f1296..305c59003963 100644 --- a/drivers/gpu/drm/Kconfig +++ b/drivers/gpu/drm/Kconfig @@ -9,7 +9,6 @@ menuconfig DRM depends on (AGP || AGP=n) && PCI && !EMULATED_CMPXCHG && MMU select I2C select I2C_ALGOBIT - select LIST_SORT help Kernel-level support for the Direct Rendering Infrastructure (DRI) introduced in XFree86 4.0. If you say Y here, you need to select diff --git a/fs/ubifs/Kconfig b/fs/ubifs/Kconfig index 430c69f39842..830e3f76f442 100644 --- a/fs/ubifs/Kconfig +++ b/fs/ubifs/Kconfig @@ -7,7 +7,6 @@ config UBIFS_FS select CRYPTO if UBIFS_FS_ZLIB select CRYPTO_LZO if UBIFS_FS_LZO select CRYPTO_DEFLATE if UBIFS_FS_ZLIB - select LIST_SORT depends on MTD_UBI help UBIFS is a file system for flash devices which works on top of UBI. diff --git a/lib/Kconfig b/lib/Kconfig index 496d16e1fa2c..170d8ca901d8 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -160,9 +160,6 @@ config TEXTSEARCH_BM config TEXTSEARCH_FSM tristate -config LIST_SORT - boolean - config BTREE boolean diff --git a/lib/Makefile b/lib/Makefile index 59e46a014bc6..2e152aed7198 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o + string_helpers.o gcd.o list_sort.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG @@ -40,7 +40,6 @@ lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o -obj-$(CONFIG_LIST_SORT) += list_sort.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o -- cgit v1.2.3 From 9cd43611ccfb46632bfa7d19f688924ea93f1613 Mon Sep 17 00:00:00 2001 From: Emese Revfy Date: Thu, 31 Dec 2009 14:52:51 +0100 Subject: kobject: Constify struct kset_uevent_ops Constify struct kset_uevent_ops. This is part of the ops structure constification effort started by Arjan van de Ven et al. Benefits of this constification: * prevents modification of data that is shared (referenced) by many other structure instances at runtime * detects/prevents accidental (but not intentional) modification attempts on archs that enforce read-only kernel data at runtime * potentially better optimized code as the compiler can assume that the const data cannot be changed * the compiler/linker move const data into .rodata and therefore exclude them from false sharing Signed-off-by: Emese Revfy Signed-off-by: Greg Kroah-Hartman --- drivers/base/bus.c | 2 +- drivers/base/core.c | 2 +- drivers/base/memory.c | 2 +- fs/gfs2/sys.c | 2 +- include/linux/kobject.h | 10 +++++----- kernel/params.c | 2 +- lib/kobject.c | 4 ++-- lib/kobject_uevent.c | 2 +- mm/slub.c | 2 +- 9 files changed, 14 insertions(+), 14 deletions(-) (limited to 'lib') diff --git a/drivers/base/bus.c b/drivers/base/bus.c index c0c5a43d9fb3..2afe599eb35d 100644 --- a/drivers/base/bus.c +++ b/drivers/base/bus.c @@ -154,7 +154,7 @@ static int bus_uevent_filter(struct kset *kset, struct kobject *kobj) return 0; } -static struct kset_uevent_ops bus_uevent_ops = { +static const struct kset_uevent_ops bus_uevent_ops = { .filter = bus_uevent_filter, }; diff --git a/drivers/base/core.c b/drivers/base/core.c index f6c73a9e3d95..58ec1069f4b0 100644 --- a/drivers/base/core.c +++ b/drivers/base/core.c @@ -252,7 +252,7 @@ static int dev_uevent(struct kset *kset, struct kobject *kobj, return retval; } -static struct kset_uevent_ops device_uevent_ops = { +static const struct kset_uevent_ops device_uevent_ops = { .filter = dev_uevent_filter, .name = dev_uevent_name, .uevent = dev_uevent, diff --git a/drivers/base/memory.c b/drivers/base/memory.c index 495f15e92d4c..2f8691511190 100644 --- a/drivers/base/memory.c +++ b/drivers/base/memory.c @@ -44,7 +44,7 @@ static int memory_uevent(struct kset *kset, struct kobject *obj, struct kobj_uev return retval; } -static struct kset_uevent_ops memory_uevent_ops = { +static const struct kset_uevent_ops memory_uevent_ops = { .name = memory_uevent_name, .uevent = memory_uevent, }; diff --git a/fs/gfs2/sys.c b/fs/gfs2/sys.c index b5f1a46133c8..543503010ed0 100644 --- a/fs/gfs2/sys.c +++ b/fs/gfs2/sys.c @@ -574,7 +574,7 @@ static int gfs2_uevent(struct kset *kset, struct kobject *kobj, return 0; } -static struct kset_uevent_ops gfs2_uevent_ops = { +static const struct kset_uevent_ops gfs2_uevent_ops = { .uevent = gfs2_uevent, }; diff --git a/include/linux/kobject.h b/include/linux/kobject.h index 58ae8e00fcdd..57a1eaae9096 100644 --- a/include/linux/kobject.h +++ b/include/linux/kobject.h @@ -118,9 +118,9 @@ struct kobj_uevent_env { }; struct kset_uevent_ops { - int (*filter)(struct kset *kset, struct kobject *kobj); - const char *(*name)(struct kset *kset, struct kobject *kobj); - int (*uevent)(struct kset *kset, struct kobject *kobj, + int (* const filter)(struct kset *kset, struct kobject *kobj); + const char *(* const name)(struct kset *kset, struct kobject *kobj); + int (* const uevent)(struct kset *kset, struct kobject *kobj, struct kobj_uevent_env *env); }; @@ -155,14 +155,14 @@ struct kset { struct list_head list; spinlock_t list_lock; struct kobject kobj; - struct kset_uevent_ops *uevent_ops; + const struct kset_uevent_ops *uevent_ops; }; extern void kset_init(struct kset *kset); extern int __must_check kset_register(struct kset *kset); extern void kset_unregister(struct kset *kset); extern struct kset * __must_check kset_create_and_add(const char *name, - struct kset_uevent_ops *u, + const struct kset_uevent_ops *u, struct kobject *parent_kobj); static inline struct kset *to_kset(struct kobject *kobj) diff --git a/kernel/params.c b/kernel/params.c index 8d95f5451b22..48370be3c0a1 100644 --- a/kernel/params.c +++ b/kernel/params.c @@ -736,7 +736,7 @@ static int uevent_filter(struct kset *kset, struct kobject *kobj) return 0; } -static struct kset_uevent_ops module_uevent_ops = { +static const struct kset_uevent_ops module_uevent_ops = { .filter = uevent_filter, }; diff --git a/lib/kobject.c b/lib/kobject.c index b512b746d2af..cecf5a0ef6e1 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -789,7 +789,7 @@ static struct kobj_type kset_ktype = { * If the kset was not able to be created, NULL will be returned. */ static struct kset *kset_create(const char *name, - struct kset_uevent_ops *uevent_ops, + const struct kset_uevent_ops *uevent_ops, struct kobject *parent_kobj) { struct kset *kset; @@ -832,7 +832,7 @@ static struct kset *kset_create(const char *name, * If the kset was not able to be created, NULL will be returned. */ struct kset *kset_create_and_add(const char *name, - struct kset_uevent_ops *uevent_ops, + const struct kset_uevent_ops *uevent_ops, struct kobject *parent_kobj) { struct kset *kset; diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 920a3ca6e259..c9d3a3e8405d 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -95,7 +95,7 @@ int kobject_uevent_env(struct kobject *kobj, enum kobject_action action, const char *subsystem; struct kobject *top_kobj; struct kset *kset; - struct kset_uevent_ops *uevent_ops; + const struct kset_uevent_ops *uevent_ops; u64 seq; int i = 0; int retval = 0; diff --git a/mm/slub.c b/mm/slub.c index 0bfd3863d521..a26753c12dcd 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -4409,7 +4409,7 @@ static int uevent_filter(struct kset *kset, struct kobject *kobj) return 0; } -static struct kset_uevent_ops slab_uevent_ops = { +static const struct kset_uevent_ops slab_uevent_ops = { .filter = uevent_filter, }; -- cgit v1.2.3 From 52cf25d0ab7f78eeecc59ac652ed5090f69b619e Mon Sep 17 00:00:00 2001 From: Emese Revfy Date: Tue, 19 Jan 2010 02:58:23 +0100 Subject: Driver core: Constify struct sysfs_ops in struct kobj_type Constify struct sysfs_ops. This is part of the ops structure constification effort started by Arjan van de Ven et al. Benefits of this constification: * prevents modification of data that is shared (referenced) by many other structure instances at runtime * detects/prevents accidental (but not intentional) modification attempts on archs that enforce read-only kernel data at runtime * potentially better optimized code as the compiler can assume that the const data cannot be changed * the compiler/linker move const data into .rodata and therefore exclude them from false sharing Signed-off-by: Emese Revfy Acked-by: David Teigland Acked-by: Matt Domsch Acked-by: Maciej Sosnowski Acked-by: Hans J. Koch Acked-by: Pekka Enberg Acked-by: Jens Axboe Acked-by: Stephen Hemminger Signed-off-by: Greg Kroah-Hartman --- Documentation/kobject.txt | 2 +- arch/ia64/kernel/topology.c | 2 +- arch/powerpc/kernel/cacheinfo.c | 2 +- arch/sh/kernel/cpu/sh4/sq.c | 2 +- arch/x86/kernel/cpu/intel_cacheinfo.c | 2 +- arch/x86/kernel/cpu/mcheck/mce_amd.c | 2 +- block/blk-integrity.c | 2 +- block/blk-sysfs.c | 2 +- block/elevator.c | 2 +- drivers/base/bus.c | 4 ++-- drivers/base/class.c | 2 +- drivers/base/core.c | 2 +- drivers/base/sys.c | 4 ++-- drivers/block/pktcdvd.c | 2 +- drivers/cpufreq/cpufreq.c | 2 +- drivers/cpuidle/sysfs.c | 4 ++-- drivers/dma/ioat/dma.c | 2 +- drivers/dma/ioat/dma.h | 2 +- drivers/edac/edac_device_sysfs.c | 6 +++--- drivers/edac/edac_mc_sysfs.c | 4 ++-- drivers/edac/edac_pci_sysfs.c | 4 ++-- drivers/firmware/edd.c | 2 +- drivers/firmware/efivars.c | 2 +- drivers/firmware/iscsi_ibft.c | 2 +- drivers/firmware/memmap.c | 2 +- drivers/gpu/drm/ttm/ttm_bo.c | 2 +- drivers/gpu/drm/ttm/ttm_memory.c | 2 +- drivers/infiniband/core/cm.c | 2 +- drivers/infiniband/core/sysfs.c | 2 +- drivers/md/dm-sysfs.c | 2 +- drivers/md/md.c | 4 ++-- drivers/net/ibmveth.c | 2 +- drivers/net/iseries_veth.c | 4 ++-- drivers/parisc/pdc_stable.c | 2 +- drivers/pci/hotplug/fakephp.c | 2 +- drivers/pci/slot.c | 2 +- drivers/uio/uio.c | 4 ++-- drivers/uwb/wlp/sysfs.c | 3 +-- drivers/video/omap2/dss/manager.c | 2 +- drivers/video/omap2/dss/overlay.c | 2 +- drivers/xen/sys-hypervisor.c | 2 +- fs/btrfs/sysfs.c | 4 ++-- fs/dlm/lockspace.c | 2 +- fs/ext4/super.c | 2 +- fs/gfs2/sys.c | 2 +- fs/ocfs2/cluster/masklog.c | 2 +- fs/sysfs/file.c | 8 ++++---- include/linux/kobject.h | 4 ++-- kernel/params.c | 2 +- lib/kobject.c | 2 +- mm/slub.c | 2 +- net/bridge/br_private.h | 2 +- net/bridge/br_sysfs_if.c | 2 +- samples/kobject/kset-example.c | 2 +- 54 files changed, 69 insertions(+), 70 deletions(-) (limited to 'lib') diff --git a/Documentation/kobject.txt b/Documentation/kobject.txt index c79ab996dada..bdb13817e1e9 100644 --- a/Documentation/kobject.txt +++ b/Documentation/kobject.txt @@ -266,7 +266,7 @@ kobj_type: struct kobj_type { void (*release)(struct kobject *); - struct sysfs_ops *sysfs_ops; + const struct sysfs_ops *sysfs_ops; struct attribute **default_attrs; }; diff --git a/arch/ia64/kernel/topology.c b/arch/ia64/kernel/topology.c index 8f060352e129..b3a5818088d9 100644 --- a/arch/ia64/kernel/topology.c +++ b/arch/ia64/kernel/topology.c @@ -282,7 +282,7 @@ static ssize_t cache_show(struct kobject * kobj, struct attribute * attr, char * return ret; } -static struct sysfs_ops cache_sysfs_ops = { +static const struct sysfs_ops cache_sysfs_ops = { .show = cache_show }; diff --git a/arch/powerpc/kernel/cacheinfo.c b/arch/powerpc/kernel/cacheinfo.c index bb37b1d19a58..01fe9ce28379 100644 --- a/arch/powerpc/kernel/cacheinfo.c +++ b/arch/powerpc/kernel/cacheinfo.c @@ -642,7 +642,7 @@ static struct kobj_attribute *cache_index_opt_attrs[] = { &cache_assoc_attr, }; -static struct sysfs_ops cache_index_ops = { +static const struct sysfs_ops cache_index_ops = { .show = cache_index_show, }; diff --git a/arch/sh/kernel/cpu/sh4/sq.c b/arch/sh/kernel/cpu/sh4/sq.c index fc065f9da6e5..14726eef1ce0 100644 --- a/arch/sh/kernel/cpu/sh4/sq.c +++ b/arch/sh/kernel/cpu/sh4/sq.c @@ -326,7 +326,7 @@ static struct attribute *sq_sysfs_attrs[] = { NULL, }; -static struct sysfs_ops sq_sysfs_ops = { +static const struct sysfs_ops sq_sysfs_ops = { .show = sq_sysfs_show, .store = sq_sysfs_store, }; diff --git a/arch/x86/kernel/cpu/intel_cacheinfo.c b/arch/x86/kernel/cpu/intel_cacheinfo.c index eddb1bdd1b8f..b3eeb66c0a51 100644 --- a/arch/x86/kernel/cpu/intel_cacheinfo.c +++ b/arch/x86/kernel/cpu/intel_cacheinfo.c @@ -903,7 +903,7 @@ static ssize_t store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops sysfs_ops = { +static const struct sysfs_ops sysfs_ops = { .show = show, .store = store, }; diff --git a/arch/x86/kernel/cpu/mcheck/mce_amd.c b/arch/x86/kernel/cpu/mcheck/mce_amd.c index 83a3d1f4efca..cda932ca3ade 100644 --- a/arch/x86/kernel/cpu/mcheck/mce_amd.c +++ b/arch/x86/kernel/cpu/mcheck/mce_amd.c @@ -388,7 +388,7 @@ static ssize_t store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops threshold_ops = { +static const struct sysfs_ops threshold_ops = { .show = show, .store = store, }; diff --git a/block/blk-integrity.c b/block/blk-integrity.c index 15c630813b1c..96e83c2bdb94 100644 --- a/block/blk-integrity.c +++ b/block/blk-integrity.c @@ -278,7 +278,7 @@ static struct attribute *integrity_attrs[] = { NULL, }; -static struct sysfs_ops integrity_ops = { +static const struct sysfs_ops integrity_ops = { .show = &integrity_attr_show, .store = &integrity_attr_store, }; diff --git a/block/blk-sysfs.c b/block/blk-sysfs.c index e85442415db3..2ae2cb3f362f 100644 --- a/block/blk-sysfs.c +++ b/block/blk-sysfs.c @@ -450,7 +450,7 @@ static void blk_release_queue(struct kobject *kobj) kmem_cache_free(blk_requestq_cachep, q); } -static struct sysfs_ops queue_sysfs_ops = { +static const struct sysfs_ops queue_sysfs_ops = { .show = queue_attr_show, .store = queue_attr_store, }; diff --git a/block/elevator.c b/block/elevator.c index ee3a883840f2..df75676f6671 100644 --- a/block/elevator.c +++ b/block/elevator.c @@ -892,7 +892,7 @@ elv_attr_store(struct kobject *kobj, struct attribute *attr, return error; } -static struct sysfs_ops elv_sysfs_ops = { +static const struct sysfs_ops elv_sysfs_ops = { .show = elv_attr_show, .store = elv_attr_store, }; diff --git a/drivers/base/bus.c b/drivers/base/bus.c index 2afe599eb35d..cca1aa10054c 100644 --- a/drivers/base/bus.c +++ b/drivers/base/bus.c @@ -70,7 +70,7 @@ static ssize_t drv_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops driver_sysfs_ops = { +static const struct sysfs_ops driver_sysfs_ops = { .show = drv_attr_show, .store = drv_attr_store, }; @@ -115,7 +115,7 @@ static ssize_t bus_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops bus_sysfs_ops = { +static const struct sysfs_ops bus_sysfs_ops = { .show = bus_attr_show, .store = bus_attr_store, }; diff --git a/drivers/base/class.c b/drivers/base/class.c index 2e297cc4cd3d..0147f476b8a9 100644 --- a/drivers/base/class.c +++ b/drivers/base/class.c @@ -63,7 +63,7 @@ static void class_release(struct kobject *kobj) kfree(cp); } -static struct sysfs_ops class_sysfs_ops = { +static const struct sysfs_ops class_sysfs_ops = { .show = class_attr_show, .store = class_attr_store, }; diff --git a/drivers/base/core.c b/drivers/base/core.c index 58ec1069f4b0..b0d6646a2814 100644 --- a/drivers/base/core.c +++ b/drivers/base/core.c @@ -100,7 +100,7 @@ static ssize_t dev_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops dev_sysfs_ops = { +static const struct sysfs_ops dev_sysfs_ops = { .show = dev_attr_show, .store = dev_attr_store, }; diff --git a/drivers/base/sys.c b/drivers/base/sys.c index 747c99e0568b..8980feec5d14 100644 --- a/drivers/base/sys.c +++ b/drivers/base/sys.c @@ -54,7 +54,7 @@ sysdev_store(struct kobject *kobj, struct attribute *attr, return -EIO; } -static struct sysfs_ops sysfs_ops = { +static const struct sysfs_ops sysfs_ops = { .show = sysdev_show, .store = sysdev_store, }; @@ -104,7 +104,7 @@ static ssize_t sysdev_class_store(struct kobject *kobj, struct attribute *attr, return -EIO; } -static struct sysfs_ops sysfs_class_ops = { +static const struct sysfs_ops sysfs_class_ops = { .show = sysdev_class_show, .store = sysdev_class_store, }; diff --git a/drivers/block/pktcdvd.c b/drivers/block/pktcdvd.c index 73d815d3f1b2..39c8514442eb 100644 --- a/drivers/block/pktcdvd.c +++ b/drivers/block/pktcdvd.c @@ -284,7 +284,7 @@ static ssize_t kobj_pkt_store(struct kobject *kobj, return len; } -static struct sysfs_ops kobj_pkt_ops = { +static const struct sysfs_ops kobj_pkt_ops = { .show = kobj_pkt_show, .store = kobj_pkt_store }; diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index 67bc2ece7b4b..2d5d575e889d 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -766,7 +766,7 @@ static void cpufreq_sysfs_release(struct kobject *kobj) complete(&policy->kobj_unregister); } -static struct sysfs_ops sysfs_ops = { +static const struct sysfs_ops sysfs_ops = { .show = show, .store = store, }; diff --git a/drivers/cpuidle/sysfs.c b/drivers/cpuidle/sysfs.c index c9cefacabf37..8719b36e1a4d 100644 --- a/drivers/cpuidle/sysfs.c +++ b/drivers/cpuidle/sysfs.c @@ -195,7 +195,7 @@ static ssize_t cpuidle_store(struct kobject * kobj, struct attribute * attr, return ret; } -static struct sysfs_ops cpuidle_sysfs_ops = { +static const struct sysfs_ops cpuidle_sysfs_ops = { .show = cpuidle_show, .store = cpuidle_store, }; @@ -281,7 +281,7 @@ static ssize_t cpuidle_state_show(struct kobject * kobj, return ret; } -static struct sysfs_ops cpuidle_state_sysfs_ops = { +static const struct sysfs_ops cpuidle_state_sysfs_ops = { .show = cpuidle_state_show, }; diff --git a/drivers/dma/ioat/dma.c b/drivers/dma/ioat/dma.c index af14c9a5b8d4..0099340b9616 100644 --- a/drivers/dma/ioat/dma.c +++ b/drivers/dma/ioat/dma.c @@ -1138,7 +1138,7 @@ ioat_attr_show(struct kobject *kobj, struct attribute *attr, char *page) return entry->show(&chan->common, page); } -struct sysfs_ops ioat_sysfs_ops = { +const struct sysfs_ops ioat_sysfs_ops = { .show = ioat_attr_show, }; diff --git a/drivers/dma/ioat/dma.h b/drivers/dma/ioat/dma.h index 4f747a254074..86b97ac8774e 100644 --- a/drivers/dma/ioat/dma.h +++ b/drivers/dma/ioat/dma.h @@ -346,7 +346,7 @@ bool ioat_cleanup_preamble(struct ioat_chan_common *chan, unsigned long *phys_complete); void ioat_kobject_add(struct ioatdma_device *device, struct kobj_type *type); void ioat_kobject_del(struct ioatdma_device *device); -extern struct sysfs_ops ioat_sysfs_ops; +extern const struct sysfs_ops ioat_sysfs_ops; extern struct ioat_sysfs_entry ioat_version_attr; extern struct ioat_sysfs_entry ioat_cap_attr; #endif /* IOATDMA_H */ diff --git a/drivers/edac/edac_device_sysfs.c b/drivers/edac/edac_device_sysfs.c index 53764577035f..5fdedbc0f545 100644 --- a/drivers/edac/edac_device_sysfs.c +++ b/drivers/edac/edac_device_sysfs.c @@ -137,7 +137,7 @@ static ssize_t edac_dev_ctl_info_store(struct kobject *kobj, } /* edac_dev file operations for an 'ctl_info' */ -static struct sysfs_ops device_ctl_info_ops = { +static const struct sysfs_ops device_ctl_info_ops = { .show = edac_dev_ctl_info_show, .store = edac_dev_ctl_info_store }; @@ -373,7 +373,7 @@ static ssize_t edac_dev_instance_store(struct kobject *kobj, } /* edac_dev file operations for an 'instance' */ -static struct sysfs_ops device_instance_ops = { +static const struct sysfs_ops device_instance_ops = { .show = edac_dev_instance_show, .store = edac_dev_instance_store }; @@ -476,7 +476,7 @@ static ssize_t edac_dev_block_store(struct kobject *kobj, } /* edac_dev file operations for a 'block' */ -static struct sysfs_ops device_block_ops = { +static const struct sysfs_ops device_block_ops = { .show = edac_dev_block_show, .store = edac_dev_block_store }; diff --git a/drivers/edac/edac_mc_sysfs.c b/drivers/edac/edac_mc_sysfs.c index e1d4ce083481..88840e9fa3e0 100644 --- a/drivers/edac/edac_mc_sysfs.c +++ b/drivers/edac/edac_mc_sysfs.c @@ -245,7 +245,7 @@ static ssize_t csrowdev_store(struct kobject *kobj, struct attribute *attr, return -EIO; } -static struct sysfs_ops csrowfs_ops = { +static const struct sysfs_ops csrowfs_ops = { .show = csrowdev_show, .store = csrowdev_store }; @@ -575,7 +575,7 @@ static ssize_t mcidev_store(struct kobject *kobj, struct attribute *attr, } /* Intermediate show/store table */ -static struct sysfs_ops mci_ops = { +static const struct sysfs_ops mci_ops = { .show = mcidev_show, .store = mcidev_store }; diff --git a/drivers/edac/edac_pci_sysfs.c b/drivers/edac/edac_pci_sysfs.c index fb60a877d768..bef94e3d9944 100644 --- a/drivers/edac/edac_pci_sysfs.c +++ b/drivers/edac/edac_pci_sysfs.c @@ -121,7 +121,7 @@ static ssize_t edac_pci_instance_store(struct kobject *kobj, } /* fs_ops table */ -static struct sysfs_ops pci_instance_ops = { +static const struct sysfs_ops pci_instance_ops = { .show = edac_pci_instance_show, .store = edac_pci_instance_store }; @@ -261,7 +261,7 @@ static ssize_t edac_pci_dev_store(struct kobject *kobj, return -EIO; } -static struct sysfs_ops edac_pci_sysfs_ops = { +static const struct sysfs_ops edac_pci_sysfs_ops = { .show = edac_pci_dev_show, .store = edac_pci_dev_store }; diff --git a/drivers/firmware/edd.c b/drivers/firmware/edd.c index 9e4f59dc7f1e..110e24e50883 100644 --- a/drivers/firmware/edd.c +++ b/drivers/firmware/edd.c @@ -122,7 +122,7 @@ edd_attr_show(struct kobject * kobj, struct attribute *attr, char *buf) return ret; } -static struct sysfs_ops edd_attr_ops = { +static const struct sysfs_ops edd_attr_ops = { .show = edd_attr_show, }; diff --git a/drivers/firmware/efivars.c b/drivers/firmware/efivars.c index f4f709d1370b..082f06ecd327 100644 --- a/drivers/firmware/efivars.c +++ b/drivers/firmware/efivars.c @@ -362,7 +362,7 @@ static ssize_t efivar_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops efivar_attr_ops = { +static const struct sysfs_ops efivar_attr_ops = { .show = efivar_attr_show, .store = efivar_attr_store, }; diff --git a/drivers/firmware/iscsi_ibft.c b/drivers/firmware/iscsi_ibft.c index a3600e3ed0fa..ed2801c378de 100644 --- a/drivers/firmware/iscsi_ibft.c +++ b/drivers/firmware/iscsi_ibft.c @@ -519,7 +519,7 @@ static ssize_t ibft_show_attribute(struct kobject *kobj, return ret; } -static struct sysfs_ops ibft_attr_ops = { +static const struct sysfs_ops ibft_attr_ops = { .show = ibft_show_attribute, }; diff --git a/drivers/firmware/memmap.c b/drivers/firmware/memmap.c index 20f645743ead..d59f7cad2269 100644 --- a/drivers/firmware/memmap.c +++ b/drivers/firmware/memmap.c @@ -74,7 +74,7 @@ static struct attribute *def_attrs[] = { NULL }; -static struct sysfs_ops memmap_attr_ops = { +static const struct sysfs_ops memmap_attr_ops = { .show = memmap_attr_show, }; diff --git a/drivers/gpu/drm/ttm/ttm_bo.c b/drivers/gpu/drm/ttm/ttm_bo.c index c7320ce4567d..89c38c49066f 100644 --- a/drivers/gpu/drm/ttm/ttm_bo.c +++ b/drivers/gpu/drm/ttm/ttm_bo.c @@ -128,7 +128,7 @@ static struct attribute *ttm_bo_global_attrs[] = { NULL }; -static struct sysfs_ops ttm_bo_global_ops = { +static const struct sysfs_ops ttm_bo_global_ops = { .show = &ttm_bo_global_show }; diff --git a/drivers/gpu/drm/ttm/ttm_memory.c b/drivers/gpu/drm/ttm/ttm_memory.c index f5245c02b8fd..eb143e04d402 100644 --- a/drivers/gpu/drm/ttm/ttm_memory.c +++ b/drivers/gpu/drm/ttm/ttm_memory.c @@ -152,7 +152,7 @@ static struct attribute *ttm_mem_zone_attrs[] = { NULL }; -static struct sysfs_ops ttm_mem_zone_ops = { +static const struct sysfs_ops ttm_mem_zone_ops = { .show = &ttm_mem_zone_show, .store = &ttm_mem_zone_store }; diff --git a/drivers/infiniband/core/cm.c b/drivers/infiniband/core/cm.c index 5130fc55b8e2..764787ebe8d8 100644 --- a/drivers/infiniband/core/cm.c +++ b/drivers/infiniband/core/cm.c @@ -3597,7 +3597,7 @@ static ssize_t cm_show_counter(struct kobject *obj, struct attribute *attr, atomic_long_read(&group->counter[cm_attr->index])); } -static struct sysfs_ops cm_counter_ops = { +static const struct sysfs_ops cm_counter_ops = { .show = cm_show_counter }; diff --git a/drivers/infiniband/core/sysfs.c b/drivers/infiniband/core/sysfs.c index 158a214da2f7..1558bb7fc74d 100644 --- a/drivers/infiniband/core/sysfs.c +++ b/drivers/infiniband/core/sysfs.c @@ -79,7 +79,7 @@ static ssize_t port_attr_show(struct kobject *kobj, return port_attr->show(p, port_attr, buf); } -static struct sysfs_ops port_sysfs_ops = { +static const struct sysfs_ops port_sysfs_ops = { .show = port_attr_show }; diff --git a/drivers/md/dm-sysfs.c b/drivers/md/dm-sysfs.c index f91b40942e07..84d2b91e4efb 100644 --- a/drivers/md/dm-sysfs.c +++ b/drivers/md/dm-sysfs.c @@ -75,7 +75,7 @@ static struct attribute *dm_attrs[] = { NULL, }; -static struct sysfs_ops dm_sysfs_ops = { +static const struct sysfs_ops dm_sysfs_ops = { .show = dm_attr_show, }; diff --git a/drivers/md/md.c b/drivers/md/md.c index a20a71e5efd3..fdc1890b6ac5 100644 --- a/drivers/md/md.c +++ b/drivers/md/md.c @@ -2642,7 +2642,7 @@ static void rdev_free(struct kobject *ko) mdk_rdev_t *rdev = container_of(ko, mdk_rdev_t, kobj); kfree(rdev); } -static struct sysfs_ops rdev_sysfs_ops = { +static const struct sysfs_ops rdev_sysfs_ops = { .show = rdev_attr_show, .store = rdev_attr_store, }; @@ -4059,7 +4059,7 @@ static void md_free(struct kobject *ko) kfree(mddev); } -static struct sysfs_ops md_sysfs_ops = { +static const struct sysfs_ops md_sysfs_ops = { .show = md_attr_show, .store = md_attr_store, }; diff --git a/drivers/net/ibmveth.c b/drivers/net/ibmveth.c index f2b937966950..0bc777bac9b4 100644 --- a/drivers/net/ibmveth.c +++ b/drivers/net/ibmveth.c @@ -1577,7 +1577,7 @@ static struct attribute * veth_pool_attrs[] = { NULL, }; -static struct sysfs_ops veth_pool_ops = { +static const struct sysfs_ops veth_pool_ops = { .show = veth_pool_show, .store = veth_pool_store, }; diff --git a/drivers/net/iseries_veth.c b/drivers/net/iseries_veth.c index 966de5d69521..e6e972d9b7ca 100644 --- a/drivers/net/iseries_veth.c +++ b/drivers/net/iseries_veth.c @@ -384,7 +384,7 @@ static struct attribute *veth_cnx_default_attrs[] = { NULL }; -static struct sysfs_ops veth_cnx_sysfs_ops = { +static const struct sysfs_ops veth_cnx_sysfs_ops = { .show = veth_cnx_attribute_show }; @@ -441,7 +441,7 @@ static struct attribute *veth_port_default_attrs[] = { NULL }; -static struct sysfs_ops veth_port_sysfs_ops = { +static const struct sysfs_ops veth_port_sysfs_ops = { .show = veth_port_attribute_show }; diff --git a/drivers/parisc/pdc_stable.c b/drivers/parisc/pdc_stable.c index 0bc5d474b168..1062b8ffe244 100644 --- a/drivers/parisc/pdc_stable.c +++ b/drivers/parisc/pdc_stable.c @@ -481,7 +481,7 @@ pdcspath_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static struct sysfs_ops pdcspath_attr_ops = { +static const struct sysfs_ops pdcspath_attr_ops = { .show = pdcspath_attr_show, .store = pdcspath_attr_store, }; diff --git a/drivers/pci/hotplug/fakephp.c b/drivers/pci/hotplug/fakephp.c index 6151389fd903..0a894efd4b9b 100644 --- a/drivers/pci/hotplug/fakephp.c +++ b/drivers/pci/hotplug/fakephp.c @@ -73,7 +73,7 @@ static void legacy_release(struct kobject *kobj) } static struct kobj_type legacy_ktype = { - .sysfs_ops = &(struct sysfs_ops){ + .sysfs_ops = &(const struct sysfs_ops){ .store = legacy_store, .show = legacy_show }, .release = &legacy_release, diff --git a/drivers/pci/slot.c b/drivers/pci/slot.c index 49c9e6c9779a..f75a44d37fbe 100644 --- a/drivers/pci/slot.c +++ b/drivers/pci/slot.c @@ -29,7 +29,7 @@ static ssize_t pci_slot_attr_store(struct kobject *kobj, return attribute->store ? attribute->store(slot, buf, len) : -EIO; } -static struct sysfs_ops pci_slot_sysfs_ops = { +static const struct sysfs_ops pci_slot_sysfs_ops = { .show = pci_slot_attr_show, .store = pci_slot_attr_store, }; diff --git a/drivers/uio/uio.c b/drivers/uio/uio.c index e941367dd28f..4de382acd8f2 100644 --- a/drivers/uio/uio.c +++ b/drivers/uio/uio.c @@ -129,7 +129,7 @@ static ssize_t map_type_show(struct kobject *kobj, struct attribute *attr, return entry->show(mem, buf); } -static struct sysfs_ops map_sysfs_ops = { +static const struct sysfs_ops map_sysfs_ops = { .show = map_type_show, }; @@ -217,7 +217,7 @@ static ssize_t portio_type_show(struct kobject *kobj, struct attribute *attr, return entry->show(port, buf); } -static struct sysfs_ops portio_sysfs_ops = { +static const struct sysfs_ops portio_sysfs_ops = { .show = portio_type_show, }; diff --git a/drivers/uwb/wlp/sysfs.c b/drivers/uwb/wlp/sysfs.c index 0370399ff4bb..6627c94cc854 100644 --- a/drivers/uwb/wlp/sysfs.c +++ b/drivers/uwb/wlp/sysfs.c @@ -615,8 +615,7 @@ ssize_t wlp_wss_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -static -struct sysfs_ops wss_sysfs_ops = { +static const struct sysfs_ops wss_sysfs_ops = { .show = wlp_wss_attr_show, .store = wlp_wss_attr_store, }; diff --git a/drivers/video/omap2/dss/manager.c b/drivers/video/omap2/dss/manager.c index 913142d4cab1..9acef00c47ea 100644 --- a/drivers/video/omap2/dss/manager.c +++ b/drivers/video/omap2/dss/manager.c @@ -341,7 +341,7 @@ static ssize_t manager_attr_store(struct kobject *kobj, struct attribute *attr, return manager_attr->store(manager, buf, size); } -static struct sysfs_ops manager_sysfs_ops = { +static const struct sysfs_ops manager_sysfs_ops = { .show = manager_attr_show, .store = manager_attr_store, }; diff --git a/drivers/video/omap2/dss/overlay.c b/drivers/video/omap2/dss/overlay.c index 0c5bea263ac6..aed3f3194347 100644 --- a/drivers/video/omap2/dss/overlay.c +++ b/drivers/video/omap2/dss/overlay.c @@ -320,7 +320,7 @@ static ssize_t overlay_attr_store(struct kobject *kobj, struct attribute *attr, return overlay_attr->store(overlay, buf, size); } -static struct sysfs_ops overlay_sysfs_ops = { +static const struct sysfs_ops overlay_sysfs_ops = { .show = overlay_attr_show, .store = overlay_attr_store, }; diff --git a/drivers/xen/sys-hypervisor.c b/drivers/xen/sys-hypervisor.c index ae5cb05a1a1c..bb71ab2336c8 100644 --- a/drivers/xen/sys-hypervisor.c +++ b/drivers/xen/sys-hypervisor.c @@ -426,7 +426,7 @@ static ssize_t hyp_sysfs_store(struct kobject *kobj, return 0; } -static struct sysfs_ops hyp_sysfs_ops = { +static const struct sysfs_ops hyp_sysfs_ops = { .show = hyp_sysfs_show, .store = hyp_sysfs_store, }; diff --git a/fs/btrfs/sysfs.c b/fs/btrfs/sysfs.c index a240b6fa81df..4ce16ef702a3 100644 --- a/fs/btrfs/sysfs.c +++ b/fs/btrfs/sysfs.c @@ -164,12 +164,12 @@ static void btrfs_root_release(struct kobject *kobj) complete(&root->kobj_unregister); } -static struct sysfs_ops btrfs_super_attr_ops = { +static const struct sysfs_ops btrfs_super_attr_ops = { .show = btrfs_super_attr_show, .store = btrfs_super_attr_store, }; -static struct sysfs_ops btrfs_root_attr_ops = { +static const struct sysfs_ops btrfs_root_attr_ops = { .show = btrfs_root_attr_show, .store = btrfs_root_attr_store, }; diff --git a/fs/dlm/lockspace.c b/fs/dlm/lockspace.c index 26a8bd40400a..f994a7dfda85 100644 --- a/fs/dlm/lockspace.c +++ b/fs/dlm/lockspace.c @@ -148,7 +148,7 @@ static void lockspace_kobj_release(struct kobject *k) kfree(ls); } -static struct sysfs_ops dlm_attr_ops = { +static const struct sysfs_ops dlm_attr_ops = { .show = dlm_attr_show, .store = dlm_attr_store, }; diff --git a/fs/ext4/super.c b/fs/ext4/super.c index 2b83b96cb2eb..ce84a6ed4a48 100644 --- a/fs/ext4/super.c +++ b/fs/ext4/super.c @@ -2358,7 +2358,7 @@ static void ext4_sb_release(struct kobject *kobj) } -static struct sysfs_ops ext4_attr_ops = { +static const struct sysfs_ops ext4_attr_ops = { .show = ext4_attr_show, .store = ext4_attr_store, }; diff --git a/fs/gfs2/sys.c b/fs/gfs2/sys.c index 543503010ed0..419042f7f0b6 100644 --- a/fs/gfs2/sys.c +++ b/fs/gfs2/sys.c @@ -49,7 +49,7 @@ static ssize_t gfs2_attr_store(struct kobject *kobj, struct attribute *attr, return a->store ? a->store(sdp, buf, len) : len; } -static struct sysfs_ops gfs2_attr_ops = { +static const struct sysfs_ops gfs2_attr_ops = { .show = gfs2_attr_show, .store = gfs2_attr_store, }; diff --git a/fs/ocfs2/cluster/masklog.c b/fs/ocfs2/cluster/masklog.c index b39da877b12f..3bb928a2bf7d 100644 --- a/fs/ocfs2/cluster/masklog.c +++ b/fs/ocfs2/cluster/masklog.c @@ -136,7 +136,7 @@ static ssize_t mlog_store(struct kobject *obj, struct attribute *attr, return mlog_mask_store(mlog_attr->mask, buf, count); } -static struct sysfs_ops mlog_attr_ops = { +static const struct sysfs_ops mlog_attr_ops = { .show = mlog_show, .store = mlog_store, }; diff --git a/fs/sysfs/file.c b/fs/sysfs/file.c index 50b725bcc3f3..ced2299f1c9a 100644 --- a/fs/sysfs/file.c +++ b/fs/sysfs/file.c @@ -53,7 +53,7 @@ struct sysfs_buffer { size_t count; loff_t pos; char * page; - struct sysfs_ops * ops; + const struct sysfs_ops * ops; struct mutex mutex; int needs_read_fill; int event; @@ -75,7 +75,7 @@ static int fill_read_buffer(struct dentry * dentry, struct sysfs_buffer * buffer { struct sysfs_dirent *attr_sd = dentry->d_fsdata; struct kobject *kobj = attr_sd->s_parent->s_dir.kobj; - struct sysfs_ops * ops = buffer->ops; + const struct sysfs_ops * ops = buffer->ops; int ret = 0; ssize_t count; @@ -199,7 +199,7 @@ flush_write_buffer(struct dentry * dentry, struct sysfs_buffer * buffer, size_t { struct sysfs_dirent *attr_sd = dentry->d_fsdata; struct kobject *kobj = attr_sd->s_parent->s_dir.kobj; - struct sysfs_ops * ops = buffer->ops; + const struct sysfs_ops * ops = buffer->ops; int rc; /* need attr_sd for attr and ops, its parent for kobj */ @@ -335,7 +335,7 @@ static int sysfs_open_file(struct inode *inode, struct file *file) struct sysfs_dirent *attr_sd = file->f_path.dentry->d_fsdata; struct kobject *kobj = attr_sd->s_parent->s_dir.kobj; struct sysfs_buffer *buffer; - struct sysfs_ops *ops; + const struct sysfs_ops *ops; int error = -EACCES; char *p; diff --git a/include/linux/kobject.h b/include/linux/kobject.h index 57a1eaae9096..3950d3c2850d 100644 --- a/include/linux/kobject.h +++ b/include/linux/kobject.h @@ -106,7 +106,7 @@ extern char *kobject_get_path(struct kobject *kobj, gfp_t flag); struct kobj_type { void (*release)(struct kobject *kobj); - struct sysfs_ops *sysfs_ops; + const struct sysfs_ops *sysfs_ops; struct attribute **default_attrs; }; @@ -132,7 +132,7 @@ struct kobj_attribute { const char *buf, size_t count); }; -extern struct sysfs_ops kobj_sysfs_ops; +extern const struct sysfs_ops kobj_sysfs_ops; /** * struct kset - a set of kobjects of a specific type, belonging to a specific subsystem. diff --git a/kernel/params.c b/kernel/params.c index 48370be3c0a1..68396d73c838 100644 --- a/kernel/params.c +++ b/kernel/params.c @@ -722,7 +722,7 @@ static ssize_t module_attr_store(struct kobject *kobj, return ret; } -static struct sysfs_ops module_sysfs_ops = { +static const struct sysfs_ops module_sysfs_ops = { .show = module_attr_show, .store = module_attr_store, }; diff --git a/lib/kobject.c b/lib/kobject.c index cecf5a0ef6e1..8115eb1bbf4d 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -700,7 +700,7 @@ static ssize_t kobj_attr_store(struct kobject *kobj, struct attribute *attr, return ret; } -struct sysfs_ops kobj_sysfs_ops = { +const struct sysfs_ops kobj_sysfs_ops = { .show = kobj_attr_show, .store = kobj_attr_store, }; diff --git a/mm/slub.c b/mm/slub.c index a26753c12dcd..a2b8969ba6d0 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -4390,7 +4390,7 @@ static void kmem_cache_release(struct kobject *kobj) kfree(s); } -static struct sysfs_ops slab_sysfs_ops = { +static const struct sysfs_ops slab_sysfs_ops = { .show = slab_attr_show, .store = slab_attr_store, }; diff --git a/net/bridge/br_private.h b/net/bridge/br_private.h index 1cf2cef78584..fef0384e3c0b 100644 --- a/net/bridge/br_private.h +++ b/net/bridge/br_private.h @@ -423,7 +423,7 @@ extern void br_ifinfo_notify(int event, struct net_bridge_port *port); #ifdef CONFIG_SYSFS /* br_sysfs_if.c */ -extern struct sysfs_ops brport_sysfs_ops; +extern const struct sysfs_ops brport_sysfs_ops; extern int br_sysfs_addif(struct net_bridge_port *p); /* br_sysfs_br.c */ diff --git a/net/bridge/br_sysfs_if.c b/net/bridge/br_sysfs_if.c index 696596cd3384..0b9916489d6b 100644 --- a/net/bridge/br_sysfs_if.c +++ b/net/bridge/br_sysfs_if.c @@ -238,7 +238,7 @@ static ssize_t brport_store(struct kobject * kobj, return ret; } -struct sysfs_ops brport_sysfs_ops = { +const struct sysfs_ops brport_sysfs_ops = { .show = brport_show, .store = brport_store, }; diff --git a/samples/kobject/kset-example.c b/samples/kobject/kset-example.c index 7c6088140528..3b126d1f8599 100644 --- a/samples/kobject/kset-example.c +++ b/samples/kobject/kset-example.c @@ -87,7 +87,7 @@ static ssize_t foo_attr_store(struct kobject *kobj, } /* Our custom sysfs_ops that we will associate with our ktype later on */ -static struct sysfs_ops foo_sysfs_ops = { +static const struct sysfs_ops foo_sysfs_ops = { .show = foo_attr_show, .store = foo_attr_store, }; -- cgit v1.2.3 From e69eae65523b457a3ac4262a66cfff57f2c924a9 Mon Sep 17 00:00:00 2001 From: Joakim Tjernlund Date: Wed, 10 Mar 2010 15:23:55 -0800 Subject: zlib: make new optimized inflate endian independent Commit 6846ee5ca68d81e6baccf0d56221d7a00c1be18b ("zlib: Fix build of powerpc boot wrapper") made the new optimized inflate only available on arch's that define CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS. This patch will again enable the optimization for all arch's by defining our own endian independent version of unaligned access. As an added bonus, arch's that define CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS do a plain load instead. Signed-off-by: Joakim Tjernlund Cc: Anton Blanchard Cc: Benjamin Herrenschmidt Cc: David Woodhouse Cc: Kumar Gala Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/zlib_inflate/inffast.c | 70 ++++++++++++++++++++-------------------------- 1 file changed, 30 insertions(+), 40 deletions(-) (limited to 'lib') diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index 215447c55261..fa62fc7a94f9 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c @@ -8,21 +8,6 @@ #include "inflate.h" #include "inffast.h" -/* Only do the unaligned "Faster" variant when - * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is set - * - * On powerpc, it won't be as we don't include autoconf.h - * automatically for the boot wrapper, which is intended as - * we run in an environment where we may not be able to deal - * with (even rare) alignment faults. In addition, we do not - * define __KERNEL__ for arch/powerpc/boot unlike x86 - */ - -#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS -#include -#include -#endif - #ifndef ASMINF /* Allow machine dependent optimization for post-increment or pre-increment. @@ -36,14 +21,31 @@ - Pentium III (Anderson) - M68060 (Nikl) */ +union uu { + unsigned short us; + unsigned char b[2]; +}; + +/* Endian independed version */ +static inline unsigned short +get_unaligned16(const unsigned short *p) +{ + union uu mm; + unsigned char *b = (unsigned char *)p; + + mm.b[0] = b[0]; + mm.b[1] = b[1]; + return mm.us; +} + #ifdef POSTINC # define OFF 0 # define PUP(a) *(a)++ -# define UP_UNALIGNED(a) get_unaligned((a)++) +# define UP_UNALIGNED(a) get_unaligned16((a)++) #else # define OFF 1 # define PUP(a) *++(a) -# define UP_UNALIGNED(a) get_unaligned(++(a)) +# define UP_UNALIGNED(a) get_unaligned16(++(a)) #endif /* @@ -256,7 +258,6 @@ void inflate_fast(z_streamp strm, unsigned start) } } else { -#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS unsigned short *sout; unsigned long loops; @@ -274,7 +275,11 @@ void inflate_fast(z_streamp strm, unsigned start) sfrom = (unsigned short *)(from - OFF); loops = len >> 1; do +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS + PUP(sout) = PUP(sfrom); +#else PUP(sout) = UP_UNALIGNED(sfrom); +#endif while (--loops); out = (unsigned char *)sout + OFF; from = (unsigned char *)sfrom + OFF; @@ -282,14 +287,13 @@ void inflate_fast(z_streamp strm, unsigned start) unsigned short pat16; pat16 = *(sout-2+2*OFF); - if (dist == 1) -#if defined(__BIG_ENDIAN) - pat16 = (pat16 & 0xff) | ((pat16 & 0xff) << 8); -#elif defined(__LITTLE_ENDIAN) - pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00) >> 8); -#else -#error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined -#endif + if (dist == 1) { + union uu mm; + /* copy one char pattern to both bytes */ + mm.us = pat16; + mm.b[0] = mm.b[1]; + pat16 = mm.us; + } loops = len >> 1; do PUP(sout) = pat16; @@ -298,20 +302,6 @@ void inflate_fast(z_streamp strm, unsigned start) } if (len & 1) PUP(out) = PUP(from); -#else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ - from = out - dist; /* copy direct from output */ - do { /* minimum length is three */ - PUP(out) = PUP(from); - PUP(out) = PUP(from); - PUP(out) = PUP(from); - len -= 3; - } while (len > 2); - if (len) { - PUP(out) = PUP(from); - if (len > 1) - PUP(out) = PUP(from); - } -#endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ } } else if ((op & 64) == 0) { /* 2nd level distance code */ -- cgit v1.2.3 From 51ea3f6a4571e9283e2ff79b74bcedfc2986dbe2 Mon Sep 17 00:00:00 2001 From: Joakim Tjernlund Date: Wed, 10 Mar 2010 15:23:57 -0800 Subject: inflate_fast: sout is already a short so ptr arith was off by one. inflate_fast() can do either POST INC or PRE INC on its pointers walking the memory to decompress. Default is PRE INC. The sout pointer offset was miscalculated in one case as the calculation assumed sout was a char * This breaks inflate_fast() iff configured to do POST INC. Signed-off-by: Joakim Tjernlund Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/zlib_inflate/inffast.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index fa62fc7a94f9..2c13ecc5bb2c 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c @@ -286,7 +286,7 @@ void inflate_fast(z_streamp strm, unsigned start) } else { /* dist == 1 or dist == 2 */ unsigned short pat16; - pat16 = *(sout-2+2*OFF); + pat16 = *(sout-1+OFF); if (dist == 1) { union uu mm; /* copy one char pattern to both bytes */ -- cgit v1.2.3 From 0f4050c7d3ba0275e5f39513c0670a717d43048c Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Fri, 5 Mar 2010 10:47:42 -0700 Subject: resource: add bus number support Add support for bus number resources. This is for bridges with a range of bus numbers behind them. Signed-off-by: Bjorn Helgaas Signed-off-by: Len Brown --- include/linux/ioport.h | 1 + lib/vsprintf.c | 9 +++++++++ 2 files changed, 10 insertions(+) (limited to 'lib') diff --git a/include/linux/ioport.h b/include/linux/ioport.h index b126209a40e2..510e4ac918dd 100644 --- a/include/linux/ioport.h +++ b/include/linux/ioport.h @@ -39,6 +39,7 @@ struct resource_list { #define IORESOURCE_MEM 0x00000200 #define IORESOURCE_IRQ 0x00000400 #define IORESOURCE_DMA 0x00000800 +#define IORESOURCE_BUS 0x00001000 #define IORESOURCE_PREFETCH 0x00002000 /* No side effects */ #define IORESOURCE_READONLY 0x00004000 diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 0d461c7c14db..ebbecf90d5d7 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -609,6 +609,12 @@ static char *resource_string(char *buf, char *end, struct resource *res, .precision = -1, .flags = SPECIAL | SMALL | ZEROPAD, }; + static const struct printf_spec bus_spec = { + .base = 16, + .field_width = 2, + .precision = -1, + .flags = SMALL | ZEROPAD, + }; static const struct printf_spec dec_spec = { .base = 10, .precision = -1, @@ -651,6 +657,9 @@ static char *resource_string(char *buf, char *end, struct resource *res, } else if (res->flags & IORESOURCE_DMA) { p = string(p, pend, "dma ", str_spec); specp = &dec_spec; + } else if (res->flags & IORESOURCE_BUS) { + p = string(p, pend, "bus ", str_spec); + specp = &bus_spec; } else { p = string(p, pend, "??? ", str_spec); specp = &mem_spec; -- cgit v1.2.3 From 9d7cca04211d4eb104eaaa424b98f650bc29c730 Mon Sep 17 00:00:00 2001 From: Bjorn Helgaas Date: Fri, 5 Mar 2010 10:47:47 -0700 Subject: resource: add window support Add support for resource windows. This is for bridge resources, i.e., regions where a bridge forwards transactions from the primary to the secondary side. Signed-off-by: Bjorn Helgaas Signed-off-by: Len Brown --- include/linux/ioport.h | 1 + lib/vsprintf.c | 4 +++- 2 files changed, 4 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/include/linux/ioport.h b/include/linux/ioport.h index 510e4ac918dd..71ab79da7e7f 100644 --- a/include/linux/ioport.h +++ b/include/linux/ioport.h @@ -51,6 +51,7 @@ struct resource_list { #define IORESOURCE_STARTALIGN 0x00080000 /* start field is alignment */ #define IORESOURCE_MEM_64 0x00100000 +#define IORESOURCE_WINDOW 0x00200000 /* forwarded by bridge */ #define IORESOURCE_EXCLUSIVE 0x08000000 /* Userland may not map this resource */ #define IORESOURCE_DISABLED 0x10000000 diff --git a/lib/vsprintf.c b/lib/vsprintf.c index ebbecf90d5d7..24112e5a5780 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -635,7 +635,7 @@ static char *resource_string(char *buf, char *end, struct resource *res, * 64-bit res (sizeof==8): 20 chars in dec, 18 in hex ("0x" + 16) */ #define RSRC_BUF_SIZE ((2 * sizeof(resource_size_t)) + 4) #define FLAG_BUF_SIZE (2 * sizeof(res->flags)) -#define DECODED_BUF_SIZE sizeof("[mem - 64bit pref disabled]") +#define DECODED_BUF_SIZE sizeof("[mem - 64bit pref window disabled]") #define RAW_BUF_SIZE sizeof("[mem - flags 0x]") char sym[max(2*RSRC_BUF_SIZE + DECODED_BUF_SIZE, 2*RSRC_BUF_SIZE + FLAG_BUF_SIZE + RAW_BUF_SIZE)]; @@ -675,6 +675,8 @@ static char *resource_string(char *buf, char *end, struct resource *res, p = string(p, pend, " 64bit", str_spec); if (res->flags & IORESOURCE_PREFETCH) p = string(p, pend, " pref", str_spec); + if (res->flags & IORESOURCE_WINDOW) + p = string(p, pend, " window", str_spec); if (res->flags & IORESOURCE_DISABLED) p = string(p, pend, " disabled", str_spec); } else { -- cgit v1.2.3