From b283f09cf8f51c29bf90e42e22099f76d0f33378 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 22:41:20 -0700 Subject: [PATCH] Fix get_wchan() FIXME wrt. order of functions From: William Lee Irwin III This addresses the issue with get_wchan() that the various functions acting as scheduling-related primitives are not, in fact, contiguous in the text segment. It creates an ELF section for scheduling primitives to be placed in, and places currently-detected (i.e. skipped during stack decoding) scheduling primitives and others like io_schedule() and down(), which are currently missed by get_wchan() code, into this section also. The net effects are more reliability of get_wchan()'s results and the new ability, made use of by this code, to arbitrarily place scheduling primitives in the source code without disturbing get_wchan()'s accuracy. Suggestions by Arnd Bergmann and Matthew Wilcox regarding reducing the invasiveness of the patch were incorporated during prior rounds of review. I've at least tried to sweep all arches in this patch. --- lib/rwsem.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/rwsem.c b/lib/rwsem.c index 95469d7fb796..85dcae7e9337 100644 --- a/lib/rwsem.c +++ b/lib/rwsem.c @@ -5,6 +5,7 @@ */ #include #include +#include #include struct rwsem_waiter { @@ -162,7 +163,7 @@ static inline struct rw_semaphore *rwsem_down_failed_common(struct rw_semaphore /* * wait for the read lock to be granted */ -struct rw_semaphore fastcall *rwsem_down_read_failed(struct rw_semaphore *sem) +struct rw_semaphore fastcall __sched *rwsem_down_read_failed(struct rw_semaphore *sem) { struct rwsem_waiter waiter; @@ -178,7 +179,7 @@ struct rw_semaphore fastcall *rwsem_down_read_failed(struct rw_semaphore *sem) /* * wait for the write lock to be granted */ -struct rw_semaphore fastcall *rwsem_down_write_failed(struct rw_semaphore *sem) +struct rw_semaphore fastcall __sched *rwsem_down_write_failed(struct rw_semaphore *sem) { struct rwsem_waiter waiter; -- cgit v1.2.3 From f951179269c98ac7b58dcfa3de2e68d4a0a3d680 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 23:00:10 -0700 Subject: [PATCH] Broken bitmap_parse for ncpus > 32 From: Joe Korty This patch replaces the call to bitmap_shift_right() in bitmap_parse() with bitmap_shift_left(). I also prepended comments to the bitmap_shift_* functions defining what 'left' and 'right' means. This is under the theory that if I and all the reviewers were bamboozled, others in the future occasionally might be too. --- lib/bitmap.c | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index 6793ac002915..68abf679808b 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -71,6 +71,17 @@ void bitmap_complement(unsigned long *bitmap, int bits) } EXPORT_SYMBOL(bitmap_complement); +/* + * bitmap_shift_write - logical right shift of the bits in a bitmap + * @dst - destination bitmap + * @src - source bitmap + * @nbits - shift by this many bits + * @bits - bitmap size, in bits + * + * Shifting right (dividing) means moving bits in the MS -> LS bit + * direction. Zeros are fed into the vacated MS positions and the + * LS bits shifted off the bottom are lost. + */ void bitmap_shift_right(unsigned long *dst, const unsigned long *src, int shift, int bits) { @@ -86,6 +97,17 @@ void bitmap_shift_right(unsigned long *dst, } EXPORT_SYMBOL(bitmap_shift_right); +/* + * bitmap_shift_left - logical left shift of the bits in a bitmap + * @dst - destination bitmap + * @src - source bitmap + * @nbits - shift by this many bits + * @bits - bitmap size, in bits + * + * Shifting left (multiplying) means moving bits in the LS -> MS + * direction. Zeros are fed into the vacated LS bit positions + * and those MS bits shifted off the top are lost. + */ void bitmap_shift_left(unsigned long *dst, const unsigned long *src, int shift, int bits) { @@ -269,7 +291,7 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, if (nchunks == 0 && chunk == 0) continue; - bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits); + bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); *maskp |= chunk; nchunks++; nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; -- cgit v1.2.3 From 77c8efaeba52f0ebe0aaab689bdbb53bf6f5a723 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 23:05:41 -0700 Subject: [PATCH] Remove bitmap_shift_*() bitmap length limits From: William Lee Irwin III Chang bitmap_shift_left()/bitmap_shift_right() to have O(1) stackspace requirements. Given zeroed tail preconditions these implementations satisfy zeroed tail postconditions, which makes them compatible with whatever changes from Paul Jackson one may want to merge in the future. No particular effort was required to ensure this. A small (but hopefully forgiveable) cleanup is a spelling correction: s/bitmap_shift_write/bitmap_shift_right/ in one of the kerneldoc comments. The primary effect of the patch is to remove the MAX_BITMAP_BITS limitation, so restoring the NR_CPUS to be limited only by stackspace and slab allocator maximums. They also look vaguely more efficient than the current code, though as this was not done for performance reasons, no performance testing was done. --- lib/bitmap.c | 70 ++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 49 insertions(+), 21 deletions(-) (limited to 'lib') diff --git a/lib/bitmap.c b/lib/bitmap.c index 68abf679808b..602b919ef551 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -12,8 +12,6 @@ #include #include -#define MAX_BITMAP_BITS 512U /* for ia64 NR_CPUS maximum */ - int bitmap_empty(const unsigned long *bitmap, int bits) { int k, lim = bits/BITS_PER_LONG; @@ -72,7 +70,7 @@ void bitmap_complement(unsigned long *bitmap, int bits) EXPORT_SYMBOL(bitmap_complement); /* - * bitmap_shift_write - logical right shift of the bits in a bitmap + * bitmap_shift_right - logical right shift of the bits in a bitmap * @dst - destination bitmap * @src - source bitmap * @nbits - shift by this many bits @@ -85,15 +83,32 @@ EXPORT_SYMBOL(bitmap_complement); void bitmap_shift_right(unsigned long *dst, const unsigned long *src, int shift, int bits) { - int k; - DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS); - - BUG_ON(bits > MAX_BITMAP_BITS); - bitmap_clear(__shr_tmp, bits); - for (k = 0; k < bits - shift; ++k) - if (test_bit(k + shift, src)) - set_bit(k, __shr_tmp); - bitmap_copy(dst, __shr_tmp, bits); + int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; + int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; + unsigned long mask = (1UL << left) - 1; + for (k = 0; off + k < lim; ++k) { + unsigned long upper, lower; + + /* + * If shift is not word aligned, take lower rem bits of + * word above and make them the top rem bits of result. + */ + if (!rem || off + k + 1 >= lim) + upper = 0; + else { + upper = src[off + k + 1]; + if (off + k + 1 == lim - 1 && left) + upper &= mask; + } + lower = src[off + k]; + if (left && off + k == lim - 1) + lower &= mask; + dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem; + if (left && k == lim - 1) + dst[k] &= mask; + } + if (off) + memset(&dst[lim - off], 0, off*sizeof(unsigned long)); } EXPORT_SYMBOL(bitmap_shift_right); @@ -111,15 +126,28 @@ EXPORT_SYMBOL(bitmap_shift_right); void bitmap_shift_left(unsigned long *dst, const unsigned long *src, int shift, int bits) { - int k; - DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS); - - BUG_ON(bits > MAX_BITMAP_BITS); - bitmap_clear(__shl_tmp, bits); - for (k = bits; k >= shift; --k) - if (test_bit(k - shift, src)) - set_bit(k, __shl_tmp); - bitmap_copy(dst, __shl_tmp, bits); + int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; + int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; + for (k = lim - off - 1; k >= 0; --k) { + unsigned long upper, lower; + + /* + * If shift is not word aligned, take upper rem bits of + * word below and make them the bottom rem bits of result. + */ + if (rem && k > 0) + lower = src[k - 1]; + else + lower = 0; + upper = src[k]; + if (left && k == lim - 1) + upper &= (1UL << left) - 1; + dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem; + if (left && k + off == lim - 1) + dst[k + off] &= (1UL << left) - 1; + } + if (off) + memset(dst, 0, off*sizeof(unsigned long)); } EXPORT_SYMBOL(bitmap_shift_left); -- cgit v1.2.3 From 8691fb836b268c622c61281238219fc166f0eee5 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 23:10:27 -0700 Subject: [PATCH] radix-tree tags for selective lookup Add radix-tree tagging so we can look up dirty or writeback pages in O(log64(n)) time. Each radix-tree node gains two bits for each slot: one for page dirtiness and one for page writebackness. If a tag bit is set on a leaf node, it indicates that item at the corresponding slot is tagged (say, a dirty page). If a tag bit is set in a non-leaf node it indicates that the same tag bit is set in the subtree which lies under the corresponding slot. ie: "there is a dirty page under here somewhere, but you need to search down further to find it". A gang lookup function is provided which can walk the radix tree in logarithmic time looking for items which are tagged, starting from a specified offset. We use this for in-order searches for dirty or writeback pages. There is a userspace test harness for this code at http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz --- include/linux/radix-tree.h | 38 ++-- lib/radix-tree.c | 444 ++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 426 insertions(+), 56 deletions(-) (limited to 'lib') diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index c32a45fd1f0d..8081a281fa5e 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -20,8 +20,7 @@ #define _LINUX_RADIX_TREE_H #include - -struct radix_tree_node; +#include struct radix_tree_root { unsigned int height; @@ -29,25 +28,40 @@ struct radix_tree_root { struct radix_tree_node *rnode; }; -#define RADIX_TREE_INIT(mask) {0, (mask), NULL} +#define RADIX_TREE_INIT(mask) { \ + .height = 0, \ + .gfp_mask = (mask), \ + .rnode = NULL, \ +} #define RADIX_TREE(name, mask) \ struct radix_tree_root name = RADIX_TREE_INIT(mask) -#define INIT_RADIX_TREE(root, mask) \ -do { \ - (root)->height = 0; \ - (root)->gfp_mask = (mask); \ - (root)->rnode = NULL; \ +#define INIT_RADIX_TREE(root, mask) \ +do { \ + (root)->height = 0; \ + (root)->gfp_mask = (mask); \ + (root)->rnode = NULL; \ } while (0) -extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); -extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long); -extern void *radix_tree_delete(struct radix_tree_root *, unsigned long); -extern unsigned int +int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); +void *radix_tree_lookup(struct radix_tree_root *, unsigned long); +void *radix_tree_delete(struct radix_tree_root *, unsigned long); +unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items); int radix_tree_preload(int gfp_mask); +void radix_tree_init(void); +void *radix_tree_tag_set(struct radix_tree_root *root, + unsigned long index, int tag); +void *radix_tree_tag_clear(struct radix_tree_root *root, + unsigned long index, int tag); +int radix_tree_tag_get(struct radix_tree_root *root, + unsigned long index, int tag); +unsigned int +radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, + unsigned long first_index, unsigned int max_items, int tag); +int radix_tree_tagged(struct radix_tree_root *root, int tag); static inline void radix_tree_preload_end(void) { diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 70ad32ff37ca..5fb59f715eab 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -6,12 +6,12 @@ * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2, or (at * your option) any later version. - * + * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. - * + * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. @@ -28,21 +28,36 @@ #include #include #include +#include /* * Radix tree node definition. + * + * RADIX_TREE_MAP_SHIFT must be >= log2(BITS_PER_LONG). Otherwise the tags + * array will have zero size and the set_tag() arithmetic will go wrong. */ -#define RADIX_TREE_MAP_SHIFT 6 -#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) -#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) +#ifdef __KERNEL__ +#define RADIX_TREE_MAP_SHIFT 6 +#else +#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ +#endif +#define RADIX_TREE_TAGS 2 + +#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) + +#define RADIX_TREE_TAG_LONGS \ + ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) struct radix_tree_node { unsigned int count; void *slots[RADIX_TREE_MAP_SIZE]; + unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; }; struct radix_tree_path { struct radix_tree_node *node, **slot; + int offset; }; #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) @@ -124,6 +139,22 @@ out: return ret; } +static inline void tag_set(struct radix_tree_node *node, int tag, int offset) +{ + if (!test_bit(offset, &node->tags[tag][0])) + __set_bit(offset, &node->tags[tag][0]); +} + +static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) +{ + __clear_bit(offset, &node->tags[tag][0]); +} + +static inline int tag_get(struct radix_tree_node *node, int tag, int offset) +{ + return test_bit(offset, &node->tags[tag][0]); +} + /* * Return the maximum key which can be store into a * radix tree with height HEIGHT. @@ -140,26 +171,53 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) { struct radix_tree_node *node; unsigned int height; + char tags[RADIX_TREE_TAGS]; + int tag; /* Figure out what the height should be. */ height = root->height + 1; while (index > radix_tree_maxindex(height)) height++; - if (root->rnode) { - do { - if (!(node = radix_tree_node_alloc(root))) - return -ENOMEM; - - /* Increase the height. */ - node->slots[0] = root->rnode; - node->count = 1; - root->rnode = node; - root->height++; - } while (height > root->height); - } else + if (root->rnode == NULL) { root->height = height; + goto out; + } + + /* + * Prepare the tag status of the top-level node for propagation + * into the newly-pushed top-level node(s) + */ + for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { + int idx; + + tags[tag] = 0; + for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { + if (root->rnode->tags[tag][idx]) { + tags[tag] = 1; + break; + } + } + } + + do { + if (!(node = radix_tree_node_alloc(root))) + return -ENOMEM; + + /* Increase the height. */ + node->slots[0] = root->rnode; + /* Propagate the aggregated tag info into the new root */ + for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { + if (tags[tag]) + tag_set(node, tag, 0); + } + + node->count = 1; + root->rnode = node; + root->height++; + } while (height > root->height); +out: return 0; } @@ -171,23 +229,27 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) * * Insert an item into the radix tree at position @index. */ -int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) +int radix_tree_insert(struct radix_tree_root *root, + unsigned long index, void *item) { struct radix_tree_node *node = NULL, *tmp, **slot; unsigned int height, shift; + int offset; int error; /* Make sure the tree is high enough. */ - if (index > radix_tree_maxindex(root->height)) { + if ((!index && !root->rnode) || + index > radix_tree_maxindex(root->height)) { error = radix_tree_extend(root, index); if (error) return error; } - + slot = &root->rnode; height = root->height; shift = (height-1) * RADIX_TREE_MAP_SHIFT; + offset = 0; /* uninitialised var warning */ while (height > 0) { if (*slot == NULL) { /* Have to add a child node. */ @@ -198,18 +260,21 @@ int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *i node->count++; } - /* Go a level down. */ + /* Go a level down */ + offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = *slot; - slot = (struct radix_tree_node **) - (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK)); + slot = (struct radix_tree_node **)(node->slots + offset); shift -= RADIX_TREE_MAP_SHIFT; height--; } if (*slot != NULL) return -EEXIST; - if (node) + if (node) { node->count++; + BUG_ON(tag_get(node, 0, offset)); + BUG_ON(tag_get(node, 1, offset)); + } *slot = item; return 0; @@ -221,7 +286,7 @@ EXPORT_SYMBOL(radix_tree_insert); * @root: radix tree root * @index: index key * - * Lookup them item at the position @index in the radix tree @root. + * Lookup the item at the position @index in the radix tree @root. */ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { @@ -240,16 +305,174 @@ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) return NULL; slot = (struct radix_tree_node **) - ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK)); + ((*slot)->slots + + ((index >> shift) & RADIX_TREE_MAP_MASK)); shift -= RADIX_TREE_MAP_SHIFT; height--; } - return (void *) *slot; + return *slot; } EXPORT_SYMBOL(radix_tree_lookup); -static /* inline */ unsigned int +/** + * radix_tree_tag_set - set a tag on a radix tree node + * @root: radix tree root + * @index: index key + * @tag: tag index + * + * Set the search tag corresponging to @index in the radix tree. From + * the root all the way down to the leaf node. + * + * Returns the address of the tagged item. Setting a tag on a not-present + * item is a bug. + */ +void *radix_tree_tag_set(struct radix_tree_root *root, + unsigned long index, int tag) +{ + unsigned int height, shift; + struct radix_tree_node **slot; + + height = root->height; + if (index > radix_tree_maxindex(height)) + return NULL; + + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + slot = &root->rnode; + + while (height > 0) { + int offset; + + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + tag_set(*slot, tag, offset); + slot = (struct radix_tree_node **)((*slot)->slots + offset); + BUG_ON(*slot == NULL); + shift -= RADIX_TREE_MAP_SHIFT; + height--; + } + + return *slot; +} +EXPORT_SYMBOL(radix_tree_tag_set); + +/** + * radix_tree_tag_clear - clear a tag on a radix tree node + * @root: radix tree root + * @index: index key + * @tag: tag index + * + * Clear the search tag corresponging to @index in the radix tree. If + * this causes the leaf node to have no tags set then clear the tag in the + * next-to-leaf node, etc. + * + * Returns the address of the tagged item on success, else NULL. ie: + * has the same return value and semantics as radix_tree_lookup(). + */ +void *radix_tree_tag_clear(struct radix_tree_root *root, + unsigned long index, int tag) +{ + struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; + unsigned int height, shift; + void *ret = NULL; + + height = root->height; + if (index > radix_tree_maxindex(height)) + goto out; + + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + pathp->node = NULL; + pathp->slot = &root->rnode; + + while (height > 0) { + int offset; + + if (*pathp->slot == NULL) + goto out; + + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + pathp[1].offset = offset; + pathp[1].node = *pathp[0].slot; + pathp[1].slot = (struct radix_tree_node **) + (pathp[1].node->slots + offset); + pathp++; + shift -= RADIX_TREE_MAP_SHIFT; + height--; + } + + ret = *pathp[0].slot; + if (ret == NULL) + goto out; + + do { + int idx; + + tag_clear(pathp[0].node, tag, pathp[0].offset); + for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { + if (pathp[0].node->tags[tag][idx]) + goto out; + } + pathp--; + } while (pathp[0].node); +out: + return ret; +} +EXPORT_SYMBOL(radix_tree_tag_clear); + +#ifndef __KERNEL__ /* Only the test harness uses this at present */ +/** + * radix_tree_tag_get - get a tag on a radix tree node + * @root: radix tree root + * @index: index key + * @tag: tag index + * + * Return the search tag corresponging to @index in the radix tree. + * + * Returns zero if the tag is unset, or if there is no corresponding item + * in the tree. + */ +int radix_tree_tag_get(struct radix_tree_root *root, + unsigned long index, int tag) +{ + unsigned int height, shift; + struct radix_tree_node **slot; + int saw_unset_tag = 0; + + height = root->height; + if (index > radix_tree_maxindex(height)) + return 0; + + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + slot = &root->rnode; + + for ( ; ; ) { + int offset; + + if (*slot == NULL) + return 0; + + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + + /* + * This is just a debug check. Later, we can bale as soon as + * we see an unset tag. + */ + if (!tag_get(*slot, tag, offset)) + saw_unset_tag = 1; + if (height == 1) { + int ret = tag_get(*slot, tag, offset); + + BUG_ON(ret && saw_unset_tag); + return ret; + } + slot = (struct radix_tree_node **)((*slot)->slots + offset); + shift -= RADIX_TREE_MAP_SHIFT; + height--; + } +} +EXPORT_SYMBOL(radix_tree_tag_get); +#endif + +static unsigned int __lookup(struct radix_tree_root *root, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index) { @@ -316,17 +539,6 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long cur_index = first_index; unsigned int ret = 0; - if (root->rnode == NULL) - goto out; - if (max_index == 0) { /* Bah. Special case */ - if (first_index == 0) { - if (max_items > 0) { - *results = root->rnode; - ret = 1; - } - } - goto out; - } while (ret < max_items) { unsigned int nr_found; unsigned long next_index; /* Index of next search */ @@ -340,11 +552,101 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results, break; cur_index = next_index; } -out: return ret; } EXPORT_SYMBOL(radix_tree_gang_lookup); +/* + * FIXME: the two tag_get()s here should use find_next_bit() instead of + * open-coding the search. + */ +static unsigned int +__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, + unsigned int max_items, unsigned long *next_index, int tag) +{ + unsigned int nr_found = 0; + unsigned int shift; + unsigned int height = root->height; + struct radix_tree_node *slot; + + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; + slot = root->rnode; + + while (height > 0) { + unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; + + for ( ; i < RADIX_TREE_MAP_SIZE; i++) { + if (tag_get(slot, tag, i)) { + BUG_ON(slot->slots[i] == NULL); + break; + } + index &= ~((1 << shift) - 1); + index += 1 << shift; + if (index == 0) + goto out; /* 32-bit wraparound */ + } + if (i == RADIX_TREE_MAP_SIZE) + goto out; + height--; + if (height == 0) { /* Bottom level: grab some items */ + unsigned long j = index & RADIX_TREE_MAP_MASK; + + for ( ; j < RADIX_TREE_MAP_SIZE; j++) { + index++; + if (tag_get(slot, tag, j)) { + BUG_ON(slot->slots[j] == NULL); + results[nr_found++] = slot->slots[j]; + if (nr_found == max_items) + goto out; + } + } + } + shift -= RADIX_TREE_MAP_SHIFT; + slot = slot->slots[i]; + } +out: + *next_index = index; + return nr_found; +} + +/** + * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree + * based on a tag + * @root: radix tree root + * @results: where the results of the lookup are placed + * @first_index: start the lookup from this key + * @max_items: place up to this many items at *results + * @tag: the tag index + * + * Performs an index-ascending scan of the tree for present items which + * have the tag indexed by @tag set. Places the items at *@results and + * returns the number of items which were placed at *@results. + */ +unsigned int +radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, + unsigned long first_index, unsigned int max_items, int tag) +{ + const unsigned long max_index = radix_tree_maxindex(root->height); + unsigned long cur_index = first_index; + unsigned int ret = 0; + + while (ret < max_items) { + unsigned int nr_found; + unsigned long next_index; /* Index of next search */ + + if (cur_index > max_index) + break; + nr_found = __lookup_tag(root, results + ret, cur_index, + max_items - ret, &next_index, tag); + ret += nr_found; + if (next_index == 0) + break; + cur_index = next_index; + } + return ret; +} +EXPORT_SYMBOL(radix_tree_gang_lookup_tag); + /** * radix_tree_delete - delete an item from a radix tree * @root: radix tree root @@ -357,24 +659,31 @@ EXPORT_SYMBOL(radix_tree_gang_lookup); void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) { struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; + struct radix_tree_path *orig_pathp; unsigned int height, shift; void *ret = NULL; + char tags[RADIX_TREE_TAGS]; + int nr_cleared_tags; height = root->height; if (index > radix_tree_maxindex(height)) goto out; - shift = (height-1) * RADIX_TREE_MAP_SHIFT; + shift = (height - 1) * RADIX_TREE_MAP_SHIFT; pathp->node = NULL; pathp->slot = &root->rnode; while (height > 0) { + int offset; + if (*pathp->slot == NULL) goto out; + offset = (index >> shift) & RADIX_TREE_MAP_MASK; + pathp[1].offset = offset; pathp[1].node = *pathp[0].slot; pathp[1].slot = (struct radix_tree_node **) - (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK)); + (pathp[1].node->slots + offset); pathp++; shift -= RADIX_TREE_MAP_SHIFT; height--; @@ -384,20 +693,67 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) if (ret == NULL) goto out; + orig_pathp = pathp; + + /* + * Clear all tags associated with the just-deleted item + */ + memset(tags, 0, sizeof(tags)); + do { + int tag; + + nr_cleared_tags = RADIX_TREE_TAGS; + for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { + int idx; + + if (!tags[tag]) + tag_clear(pathp[0].node, tag, pathp[0].offset); + + for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { + if (pathp[0].node->tags[tag][idx]) { + tags[tag] = 1; + nr_cleared_tags--; + break; + } + } + } + pathp--; + } while (pathp[0].node && nr_cleared_tags); + + pathp = orig_pathp; *pathp[0].slot = NULL; while (pathp[0].node && --pathp[0].node->count == 0) { pathp--; + BUG_ON(*pathp[0].slot == NULL); *pathp[0].slot = NULL; radix_tree_node_free(pathp[1].node); } - if (root->rnode == NULL) - root->height = 0; /* Empty tree, we can reset the height */ + root->height = 0; out: return ret; } EXPORT_SYMBOL(radix_tree_delete); +/** + * radix_tree_tagged - test whether any items in the tree are tagged + * @root: radix tree root + * @tag: tag to test + */ +int radix_tree_tagged(struct radix_tree_root *root, int tag) +{ + int idx; + + if (!root->rnode) + return 0; + for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { + if (root->rnode->tags[tag][idx]) + return 1; + } + return 0; +} +EXPORT_SYMBOL(radix_tree_tagged); + static void radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) { -- cgit v1.2.3 From 8447ac2688647d261af7a7397a53548a2a1afc13 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Mon, 12 Apr 2004 01:03:29 -0700 Subject: [PATCH] Rename bitmap_clear to bitmap_zero, remove CLEAR_BITMAP From: Rusty Russell clear_bit(n, addr) clears the nth bit. test_and_clear_bit(n, addr) clears the nth bit. cpu_clear(n, cpumask) clears the nth bit (vs. cpus_clear()). bitmap_clear(bitmap, n) clears out all the bits up to n. Moreover, there's a CLEAR_BITMAP() in linux/types.h which bitmap_clear() is a wrapper for. Rename bitmap_clear to bitmap_zero, which is harder to confuse (yes, it bit me), and make everyone use it. --- arch/ia64/sn/kernel/sn2/sn2_smp.c | 2 +- drivers/atm/lanai.c | 6 +++--- drivers/ieee1394/ieee1394_types.h | 2 +- drivers/scsi/atari_NCR5380.c | 4 ++-- include/asm-generic/cpumask_array.h | 2 +- include/asm-i386/mpspec.h | 2 +- include/asm-x86_64/mpspec.h | 2 +- include/linux/bitmap.h | 4 ++-- include/linux/types.h | 2 -- lib/bitmap.c | 2 +- mm/page_alloc.c | 2 +- 11 files changed, 14 insertions(+), 16 deletions(-) (limited to 'lib') diff --git a/arch/ia64/sn/kernel/sn2/sn2_smp.c b/arch/ia64/sn/kernel/sn2/sn2_smp.c index 3cfb3cd74d51..e8bc389edebb 100644 --- a/arch/ia64/sn/kernel/sn2/sn2_smp.c +++ b/arch/ia64/sn/kernel/sn2/sn2_smp.c @@ -91,7 +91,7 @@ sn2_global_tlb_purge (unsigned long start, unsigned long end, unsigned long nbit short nasids[NR_NODES], nix; DECLARE_BITMAP(nodes_flushed, NR_NODES); - CLEAR_BITMAP(nodes_flushed, NR_NODES); + bitmap_zero(nodes_flushed, NR_NODES); i = 0; diff --git a/drivers/atm/lanai.c b/drivers/atm/lanai.c index 402e78a5ac97..5a7037af6add 100644 --- a/drivers/atm/lanai.c +++ b/drivers/atm/lanai.c @@ -1743,7 +1743,7 @@ static void run_service(struct lanai_dev *lanai) read_lock(&vcc_sklist_lock); vci_bitfield_iterate(lanai, lanai->transmit_ready, iter_transmit); - CLEAR_BITMAP(&lanai->transmit_ready, NUM_VCI); + bitmap_zero(lanai->transmit_ready, NUM_VCI); read_unlock(&vcc_sklist_lock); } } @@ -2158,8 +2158,8 @@ static int __init lanai_dev_open(struct atm_dev *atmdev) /* Basic device fields */ lanai->number = atmdev->number; lanai->num_vci = NUM_VCI; - CLEAR_BITMAP(&lanai->backlog_vccs, NUM_VCI); - CLEAR_BITMAP(&lanai->transmit_ready, NUM_VCI); + bitmap_zero(lanai->backlog_vccs, NUM_VCI); + bitmap_zero(lanai->transmit_ready, NUM_VCI); lanai->naal0 = 0; #ifdef USE_POWERDOWN lanai->nbound = 0; diff --git a/drivers/ieee1394/ieee1394_types.h b/drivers/ieee1394/ieee1394_types.h index 552667142ce1..3165609ec1ec 100644 --- a/drivers/ieee1394/ieee1394_types.h +++ b/drivers/ieee1394/ieee1394_types.h @@ -24,7 +24,7 @@ struct hpsb_tlabel_pool { #define HPSB_TPOOL_INIT(_tp) \ do { \ - CLEAR_BITMAP((_tp)->pool, 64); \ + bitmap_zero((_tp)->pool, 64); \ spin_lock_init(&(_tp)->lock); \ (_tp)->next = 0; \ (_tp)->allocations = 0; \ diff --git a/drivers/scsi/atari_NCR5380.c b/drivers/scsi/atari_NCR5380.c index cd8ddb7084a2..5d1e78ebed83 100644 --- a/drivers/scsi/atari_NCR5380.c +++ b/drivers/scsi/atari_NCR5380.c @@ -329,7 +329,7 @@ static void __init init_tags( void ) for( target = 0; target < 8; ++target ) { for( lun = 0; lun < 8; ++lun ) { ta = &TagAlloc[target][lun]; - CLEAR_BITMAP( ta->allocated, MAX_TAGS ); + bitmap_zero(ta->allocated, MAX_TAGS); ta->nr_allocated = 0; /* At the beginning, assume the maximum queue size we could * support (MAX_TAGS). This value will be decreased if the target @@ -438,7 +438,7 @@ static void free_all_tags( void ) for( target = 0; target < 8; ++target ) { for( lun = 0; lun < 8; ++lun ) { ta = &TagAlloc[target][lun]; - CLEAR_BITMAP( ta->allocated, MAX_TAGS ); + bitmap_zero(ta->allocated, MAX_TAGS); ta->nr_allocated = 0; } } diff --git a/include/asm-generic/cpumask_array.h b/include/asm-generic/cpumask_array.h index bd5c49133c6c..c7e2db29dc53 100644 --- a/include/asm-generic/cpumask_array.h +++ b/include/asm-generic/cpumask_array.h @@ -16,7 +16,7 @@ #define cpus_and(dst,src1,src2) bitmap_and((dst).mask,(src1).mask, (src2).mask, NR_CPUS) #define cpus_or(dst,src1,src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, NR_CPUS) -#define cpus_clear(map) bitmap_clear((map).mask, NR_CPUS) +#define cpus_clear(map) bitmap_zero((map).mask, NR_CPUS) #define cpus_complement(map) bitmap_complement((map).mask, NR_CPUS) #define cpus_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, NR_CPUS) #define cpus_empty(map) bitmap_empty(map.mask, NR_CPUS) diff --git a/include/asm-i386/mpspec.h b/include/asm-i386/mpspec.h index 78bd12b7ae42..b376b093749c 100644 --- a/include/asm-i386/mpspec.h +++ b/include/asm-i386/mpspec.h @@ -52,7 +52,7 @@ typedef struct physid_mask physid_mask_t; #define physids_and(dst, src1, src2) bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS) #define physids_or(dst, src1, src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS) -#define physids_clear(map) bitmap_clear((map).mask, MAX_APICS) +#define physids_clear(map) bitmap_zero((map).mask, MAX_APICS) #define physids_complement(map) bitmap_complement((map).mask, MAX_APICS) #define physids_empty(map) bitmap_empty((map).mask, MAX_APICS) #define physids_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, MAX_APICS) diff --git a/include/asm-x86_64/mpspec.h b/include/asm-x86_64/mpspec.h index 896b99f11cec..cbe6058e9270 100644 --- a/include/asm-x86_64/mpspec.h +++ b/include/asm-x86_64/mpspec.h @@ -211,7 +211,7 @@ typedef struct physid_mask physid_mask_t; #define physids_and(dst, src1, src2) bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS) #define physids_or(dst, src1, src2) bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS) -#define physids_clear(map) bitmap_clear((map).mask, MAX_APICS) +#define physids_clear(map) bitmap_zero((map).mask, MAX_APICS) #define physids_complement(map) bitmap_complement((map).mask, MAX_APICS) #define physids_empty(map) bitmap_empty((map).mask, MAX_APICS) #define physids_equal(map1, map2) bitmap_equal((map1).mask, (map2).mask, MAX_APICS) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 2ad5fb97fa26..81e73cdc1a62 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -16,9 +16,9 @@ int bitmap_equal(const unsigned long *bitmap1, unsigned long *bitmap2, int bits); void bitmap_complement(unsigned long *bitmap, int bits); -static inline void bitmap_clear(unsigned long *bitmap, int bits) +static inline void bitmap_zero(unsigned long *bitmap, int bits) { - CLEAR_BITMAP((unsigned long *)bitmap, bits); + memset(bitmap, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long)); } static inline void bitmap_fill(unsigned long *bitmap, int bits) diff --git a/include/linux/types.h b/include/linux/types.h index 93f5f3653561..23c414f11cbe 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -8,8 +8,6 @@ (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG) #define DECLARE_BITMAP(name,bits) \ unsigned long name[BITS_TO_LONGS(bits)] -#define CLEAR_BITMAP(name,bits) \ - memset(name, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long)) #endif #include diff --git a/lib/bitmap.c b/lib/bitmap.c index 602b919ef551..779d30365e46 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -273,7 +273,7 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, int c, old_c, totaldigits, ndigits, nchunks, nbits; u32 chunk; - bitmap_clear(maskp, nmaskbits); + bitmap_zero(maskp, nmaskbits); nchunks = nbits = totaldigits = c = 0; do { diff --git a/mm/page_alloc.c b/mm/page_alloc.c index 6b4d5dc0c930..8d3f6f46105e 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -1222,7 +1222,7 @@ static void __init build_zonelists(pg_data_t *pgdat) local_node = pgdat->node_id; load = numnodes; prev_node = local_node; - CLEAR_BITMAP(used_mask, MAX_NUMNODES); + bitmap_zero(used_mask, MAX_NUMNODES); while ((node = find_next_best_node(local_node, used_mask)) >= 0) { /* * We don't want to pressure a particular node. -- cgit v1.2.3