Messages in this thread Patch in this message |  | | Date | Wed, 11 Sep 2002 01:31:22 -0700 | From | Andrew Morton <> | Subject | [patch] radix_tree_gang_lookup |
| |
Adds a gang lookup facility to radix trees. It provides an efficient means of locating a bunch of pages starting at a particular offset.
The implementation is a bit dumb, but is efficient enough. And it is amenable to the `tagged lookup' extension which is proving tricky to write, but which will allow the dirty pages within a mapping to be located in pgoff_t order.
fs/inode.c | 6 +- include/linux/radix-tree.h | 3 + lib/radix-tree.c | 101 ++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 106 insertions(+), 4 deletions(-)
--- 2.5.34/lib/radix-tree.c~radix_tree_gang_lookup Wed Sep 11 01:16:33 2002 +++ 2.5.34-akpm/lib/radix-tree.c Wed Sep 11 01:16:38 2002 @@ -43,6 +43,7 @@ struct radix_tree_path { }; #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) +#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) /* * Radix tree node cache. @@ -218,9 +219,105 @@ void *radix_tree_lookup(struct radix_tre return (void *) *slot; } - EXPORT_SYMBOL(radix_tree_lookup); +static /* inline */ unsigned int +__lookup(struct radix_tree_root *root, void **results, unsigned long index, + unsigned int max_items, unsigned long *next_index, + unsigned long max_index) +{ + unsigned int nr_found = 0; + unsigned int shift; + unsigned int height = root->height; + struct radix_tree_node *slot; + + if (index > max_index) + return 0; + 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 (slot->slots[i] != NULL) + break; + index &= ~((1 << shift) - 1); + index += 1 << shift; + } + if (i == RADIX_TREE_MAP_SIZE) + goto out; + height--; + shift -= RADIX_TREE_MAP_SHIFT; + if (height == 0) { + /* Bottom level: grab some items */ + unsigned long j; + + BUG_ON((shift + RADIX_TREE_MAP_SHIFT) != 0); + + j = index & RADIX_TREE_MAP_MASK; + for ( ; j < RADIX_TREE_MAP_SIZE; j++) { + index++; + if (slot->slots[j]) { + results[nr_found++] = slot->slots[j]; + if (nr_found == max_items) + goto out; + } + } + } + slot = slot->slots[i]; + } +out: + *next_index = index; + return nr_found; + +} +/** + * radix_tree_gang_lookup - perform multiple lookup on a radix tree + * @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 + * + * Performs an index-ascending scan of the tree for present items. Places + * them at *@results and returns the number of items which were placed at + * *@results. + * + * The implementation is naive. + */ +unsigned int +radix_tree_gang_lookup(struct radix_tree_root *root, void **results, + unsigned long first_index, unsigned int max_items) +{ + const unsigned long max_index = radix_tree_maxindex(root->height); + unsigned long 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 */ + + nr_found = __lookup(root, results + ret, cur_index, + max_items - ret, &next_index, max_index); + if (nr_found == 0) + break; + ret += nr_found; + cur_index = next_index; + } +out: + return ret; +} +EXPORT_SYMBOL(radix_tree_gang_lookup); /** * radix_tree_delete - delete an item from a radix tree @@ -231,7 +328,7 @@ EXPORT_SYMBOL(radix_tree_lookup); */ int radix_tree_delete(struct radix_tree_root *root, unsigned long index) { - struct radix_tree_path path[RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2], *pathp = path; + struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; unsigned int height, shift; height = root->height; --- 2.5.34/include/linux/radix-tree.h~radix_tree_gang_lookup Wed Sep 11 01:16:33 2002 +++ 2.5.34-akpm/include/linux/radix-tree.h Wed Sep 11 01:16:38 2002 @@ -45,5 +45,8 @@ extern int radix_tree_reserve(struct rad extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long); extern int radix_tree_delete(struct radix_tree_root *, unsigned long); +extern unsigned int +radix_tree_gang_lookup(struct radix_tree_root *root, void **results, + unsigned long first_index, unsigned int max_items); #endif /* _LINUX_RADIX_TREE_H */ --- 2.5.34/fs/inode.c~radix_tree_gang_lookup Wed Sep 11 01:16:33 2002 +++ 2.5.34-akpm/fs/inode.c Wed Sep 11 01:16:33 2002 @@ -147,10 +147,12 @@ static void destroy_inode(struct inode * if (inode_has_buffers(inode)) BUG(); security_ops->inode_free_security(inode); - if (inode->i_sb->s_op->destroy_inode) + if (inode->i_sb->s_op->destroy_inode) { inode->i_sb->s_op->destroy_inode(inode); - else + } else { + BUG_ON(inode->i_data.page_tree.rnode != NULL); kmem_cache_free(inode_cachep, (inode)); + } } . - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
|  |