From dc566127dd161b6c997466a2349ac179527ea89b Mon Sep 17 00:00:00 2001 From: Wu Fengguang Date: Tue, 16 Jun 2009 15:31:32 -0700 Subject: radix-tree: add radix_tree_prev_hole() The counterpart of radix_tree_next_hole(). To be used by context readahead. Signed-off-by: Wu Fengguang Cc: Vladislav Bolkhovitin Cc: Jens Axboe Cc: Jeff Moyer Cc: Nick Piggin Cc: Ying Han Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/radix-tree.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 4bb42a0344ec..5301a52cdb4d 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -666,6 +666,43 @@ unsigned long radix_tree_next_hole(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_next_hole); +/** + * radix_tree_prev_hole - find the prev hole (not-present entry) + * @root: tree root + * @index: index key + * @max_scan: maximum range to search + * + * Search backwards in the range [max(index-max_scan+1, 0), index] + * for the first hole. + * + * Returns: the index of the hole if found, otherwise returns an index + * outside of the set specified (in which case 'index - return >= max_scan' + * will be true). In rare cases of wrap-around, LONG_MAX will be returned. + * + * radix_tree_next_hole may be called under rcu_read_lock. However, like + * radix_tree_gang_lookup, this will not atomically search a snapshot of + * the tree at a single point in time. For example, if a hole is created + * at index 10, then subsequently a hole is created at index 5, + * radix_tree_prev_hole covering both indexes may return 5 if called under + * rcu_read_lock. + */ +unsigned long radix_tree_prev_hole(struct radix_tree_root *root, + unsigned long index, unsigned long max_scan) +{ + unsigned long i; + + for (i = 0; i < max_scan; i++) { + if (!radix_tree_lookup(root, index)) + break; + index--; + if (index == LONG_MAX) + break; + } + + return index; +} +EXPORT_SYMBOL(radix_tree_prev_hole); + static unsigned int __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, unsigned int max_items, unsigned long *next_index) -- cgit v1.2.2 From 417dcdf99ec9f8d8d6917189130bdc17cb67c678 Mon Sep 17 00:00:00 2001 From: Jan Blunck Date: Tue, 16 Jun 2009 15:33:33 -0700 Subject: atomic: only take lock when the counter drops to zero on UP as well _atomic_dec_and_lock() should not unconditionally take the lock before calling atomic_dec_and_test() in the UP case. For consistency reasons it should behave exactly like in the SMP case. Besides that this works around the problem that with CONFIG_DEBUG_SPINLOCK this spins in __spin_lock_debug() if the lock is already taken even if the counter doesn't drop to 0. Signed-off-by: Jan Blunck Acked-by: Paul E. McKenney Acked-by: Nick Piggin Cc: Valerie Aurora Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/dec_and_lock.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/dec_and_lock.c b/lib/dec_and_lock.c index a65c31455541..e73822aa6e9a 100644 --- a/lib/dec_and_lock.c +++ b/lib/dec_and_lock.c @@ -19,11 +19,10 @@ */ int _atomic_dec_and_lock(atomic_t *atomic, spinlock_t *lock) { -#ifdef CONFIG_SMP /* Subtract 1 from counter unless that drops it to 0 (ie. it was 1) */ if (atomic_add_unless(atomic, -1, 1)) return 0; -#endif + /* Otherwise do it the slow way */ spin_lock(lock); if (atomic_dec_and_test(atomic)) -- cgit v1.2.2 From b72b71c6cb6ecc564d4d5f9c512a7df269837846 Mon Sep 17 00:00:00 2001 From: Huang Shijie Date: Tue, 16 Jun 2009 15:33:42 -0700 Subject: lib: do code optimization for radix_tree_lookup() and radix_tree_lookup_slot() radix_tree_lookup() and radix_tree_lookup_slot() have much the same code except for the return value. Introduce radix_tree_lookup_element() to do the real work. /* * is_slot == 1 : search for the slot. * is_slot == 0 : search for the node. */ static void * radix_tree_lookup_element(struct radix_tree_root *root, unsigned long index, int is_slot); Signed-off-by: Huang Shijie Cc: Nick Piggin Cc: Christoph Lameter Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/radix-tree.c | 73 ++++++++++++++++++++------------------------------------ 1 file changed, 26 insertions(+), 47 deletions(-) (limited to 'lib') diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 5301a52cdb4d..23abbd93cae1 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -351,20 +351,12 @@ int radix_tree_insert(struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_insert); -/** - * radix_tree_lookup_slot - lookup a slot in a radix tree - * @root: radix tree root - * @index: index key - * - * Returns: the slot corresponding to the position @index in the - * radix tree @root. This is useful for update-if-exists operations. - * - * This function can be called under rcu_read_lock iff the slot is not - * modified by radix_tree_replace_slot, otherwise it must be called - * exclusive from other writers. Any dereference of the slot must be done - * using radix_tree_deref_slot. +/* + * is_slot == 1 : search for the slot. + * is_slot == 0 : search for the node. */ -void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) +static void *radix_tree_lookup_element(struct radix_tree_root *root, + unsigned long index, int is_slot) { unsigned int height, shift; struct radix_tree_node *node, **slot; @@ -376,7 +368,7 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) if (!radix_tree_is_indirect_ptr(node)) { if (index > 0) return NULL; - return (void **)&root->rnode; + return is_slot ? (void *)&root->rnode : node; } node = radix_tree_indirect_to_ptr(node); @@ -397,7 +389,25 @@ void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) height--; } while (height > 0); - return (void **)slot; + return is_slot ? (void *)slot:node; +} + +/** + * radix_tree_lookup_slot - lookup a slot in a radix tree + * @root: radix tree root + * @index: index key + * + * Returns: the slot corresponding to the position @index in the + * radix tree @root. This is useful for update-if-exists operations. + * + * This function can be called under rcu_read_lock iff the slot is not + * modified by radix_tree_replace_slot, otherwise it must be called + * exclusive from other writers. Any dereference of the slot must be done + * using radix_tree_deref_slot. + */ +void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) +{ + return (void **)radix_tree_lookup_element(root, index, 1); } EXPORT_SYMBOL(radix_tree_lookup_slot); @@ -415,38 +425,7 @@ EXPORT_SYMBOL(radix_tree_lookup_slot); */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { - unsigned int height, shift; - struct radix_tree_node *node, **slot; - - node = rcu_dereference(root->rnode); - if (node == NULL) - return NULL; - - if (!radix_tree_is_indirect_ptr(node)) { - if (index > 0) - return NULL; - return node; - } - node = radix_tree_indirect_to_ptr(node); - - height = node->height; - if (index > radix_tree_maxindex(height)) - return NULL; - - shift = (height-1) * RADIX_TREE_MAP_SHIFT; - - do { - slot = (struct radix_tree_node **) - (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); - node = rcu_dereference(*slot); - if (node == NULL) - return NULL; - - shift -= RADIX_TREE_MAP_SHIFT; - height--; - } while (height > 0); - - return node; + return radix_tree_lookup_element(root, index, 0); } EXPORT_SYMBOL(radix_tree_lookup); -- cgit v1.2.2 From c67ae69b661f3c2fe1a9c8259bc948c68b082166 Mon Sep 17 00:00:00 2001 From: Li Zefan Date: Tue, 16 Jun 2009 15:33:45 -0700 Subject: hexdump: remove the trailing space For example: hex_dump_to_buffer("AB", 2, 16, 1, buf, 100, 0); pr_info("[%s]\n", buf); I'd expect the output to be "[41 42]", but actually it's "[41 42 ]" This patch also makes the required buf to be minimum. To print the hex format of "AB", a buf with size 6 should be sufficient, but hex_dump_to_buffer() required at least 8. Signed-off-by: Li Zefan Acked-by: Randy Dunlap Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/hexdump.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/hexdump.c b/lib/hexdump.c index f07c0db81d26..39af2560f765 100644 --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -65,7 +65,8 @@ void hex_dump_to_buffer(const void *buf, size_t len, int rowsize, for (j = 0; j < ngroups; j++) lx += scnprintf(linebuf + lx, linebuflen - lx, - "%16.16llx ", (unsigned long long)*(ptr8 + j)); + "%s%16.16llx", j ? " " : "", + (unsigned long long)*(ptr8 + j)); ascii_column = 17 * ngroups + 2; break; } @@ -76,7 +77,7 @@ void hex_dump_to_buffer(const void *buf, size_t len, int rowsize, for (j = 0; j < ngroups; j++) lx += scnprintf(linebuf + lx, linebuflen - lx, - "%8.8x ", *(ptr4 + j)); + "%s%8.8x", j ? " " : "", *(ptr4 + j)); ascii_column = 9 * ngroups + 2; break; } @@ -87,19 +88,21 @@ void hex_dump_to_buffer(const void *buf, size_t len, int rowsize, for (j = 0; j < ngroups; j++) lx += scnprintf(linebuf + lx, linebuflen - lx, - "%4.4x ", *(ptr2 + j)); + "%s%4.4x", j ? " " : "", *(ptr2 + j)); ascii_column = 5 * ngroups + 2; break; } default: - for (j = 0; (j < rowsize) && (j < len) && (lx + 4) < linebuflen; - j++) { + for (j = 0; (j < len) && (lx + 3) <= linebuflen; j++) { ch = ptr[j]; linebuf[lx++] = hex_asc_hi(ch); linebuf[lx++] = hex_asc_lo(ch); linebuf[lx++] = ' '; } + if (j) + lx--; + ascii_column = 3 * rowsize + 2; break; } @@ -108,7 +111,7 @@ void hex_dump_to_buffer(const void *buf, size_t len, int rowsize, while (lx < (linebuflen - 1) && lx < (ascii_column - 1)) linebuf[lx++] = ' '; - for (j = 0; (j < rowsize) && (j < len) && (lx + 2) < linebuflen; j++) + for (j = 0; (j < len) && (lx + 2) < linebuflen; j++) linebuf[lx++] = (isascii(ptr[j]) && isprint(ptr[j])) ? ptr[j] : '.'; nil: -- cgit v1.2.2 From 8e8a2dea0ca91fe2cb7de7ea212124cfe8c82c35 Mon Sep 17 00:00:00 2001 From: Zygo Blaxell Date: Tue, 16 Jun 2009 15:33:57 -0700 Subject: lib/genalloc.c: remove unmatched write_lock() in gen_pool_destroy There is a call to write_lock() in gen_pool_destroy which is not balanced by any corresponding write_unlock(). This causes problems with preemption because the preemption-disable counter is incremented in the write_lock() call, but never decremented by any call to write_unlock(). This bug is gen_pool_destroy, and one of them is non-x86 arch-specific code. Signed-off-by: Zygo Blaxell Cc: Jiri Kosina Cc: Steve Wise Cc: Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/genalloc.c | 1 - 1 file changed, 1 deletion(-) (limited to 'lib') diff --git a/lib/genalloc.c b/lib/genalloc.c index f6d276db2d58..eed2bdb865e7 100644 --- a/lib/genalloc.c +++ b/lib/genalloc.c @@ -85,7 +85,6 @@ void gen_pool_destroy(struct gen_pool *pool) int bit, end_bit; - write_lock(&pool->lock); list_for_each_safe(_chunk, _next_chunk, &pool->chunks) { chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk); list_del(&chunk->next_chunk); -- cgit v1.2.2 From 16c047add3ceaf0ab882e3e094d1ec904d02312d Mon Sep 17 00:00:00 2001 From: Wolfram Strepp Date: Tue, 16 Jun 2009 15:34:11 -0700 Subject: rb_tree: reorganize code in rb_erase() for additional changes First, move some code around in order to make the next change more obvious. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Peter Zijlstra Signed-off-by: Wolfram Strepp Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index f653659e0bc1..0455685f6a73 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -231,6 +231,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node = node->rb_right; while ((left = node->rb_left) != NULL) node = left; + + if (rb_parent(old)) { + if (rb_parent(old)->rb_left == old) + rb_parent(old)->rb_left = node; + else + rb_parent(old)->rb_right = node; + } else + root->rb_node = node; + child = node->rb_right; parent = rb_parent(node); color = rb_color(node); @@ -247,15 +256,6 @@ void rb_erase(struct rb_node *node, struct rb_root *root) node->rb_right = old->rb_right; node->rb_left = old->rb_left; - if (rb_parent(old)) - { - if (rb_parent(old)->rb_left == old) - rb_parent(old)->rb_left = node; - else - rb_parent(old)->rb_right = node; - } else - root->rb_node = node; - rb_set_parent(old->rb_left, node); if (old->rb_right) rb_set_parent(old->rb_right, node); -- cgit v1.2.2 From 4c60117811171d867d4f27f17ea07d7419d45dae Mon Sep 17 00:00:00 2001 From: Wolfram Strepp Date: Tue, 16 Jun 2009 15:34:12 -0700 Subject: rb_tree: make clear distinction between two different cases in rb_erase() There are two cases when a node, having 2 childs, is erased: 'normal case': the successor is not the right-hand-child of the node to be erased 'special case': the successor is the right-hand child of the node to be erased Here some ascii-art, with following symbols (referring to the code): O: node to be deleted N: the successor of O P: parent of N C: child of N L: some other node normal case: O N / \ / \ / \ / \ L \ L \ / \ P ----> / \ P / \ / \ / / N C \ / \ \ C / \ special case: O|P N / \ / \ / \ / \ L \ L \ / \ N ----> / C \ / \ \ C / \ Notice that for the special case we don't have to reconnect C to N. Signed-off-by: Wolfram Strepp Signed-off-by: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 0455685f6a73..4b4b29b4577d 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -244,13 +244,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root) parent = rb_parent(node); color = rb_color(node); - if (child) - rb_set_parent(child, parent); if (parent == old) { - parent->rb_right = child; parent = node; - } else + } else { + if (child) + rb_set_parent(child, parent); parent->rb_left = child; + } node->rb_parent_color = old->rb_parent_color; node->rb_right = old->rb_right; -- cgit v1.2.2 From 4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee Mon Sep 17 00:00:00 2001 From: Wolfram Strepp Date: Tue, 16 Jun 2009 15:34:13 -0700 Subject: rb_tree: remove redundant if()-condition in rb_erase() Furthermore, notice that the initial checks: if (!node->rb_left) child = node->rb_right; else if (!node->rb_right) child = node->rb_left; else { ... } guarantee that old->rb_right is set in the final else branch, therefore we can omit checking that again. Signed-off-by: Wolfram Strepp Signed-off-by: Peter Zijlstra Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rbtree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/rbtree.c b/lib/rbtree.c index 4b4b29b4577d..e2aa3be29858 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -250,15 +250,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root) if (child) rb_set_parent(child, parent); parent->rb_left = child; + + node->rb_right = old->rb_right; + rb_set_parent(old->rb_right, node); } node->rb_parent_color = old->rb_parent_color; - node->rb_right = old->rb_right; node->rb_left = old->rb_left; - rb_set_parent(old->rb_left, node); - if (old->rb_right) - rb_set_parent(old->rb_right, node); + goto color; } -- cgit v1.2.2