Messages in this thread Patch in this message | | | Date | Fri, 11 Apr 2003 14:39:32 -0700 | From | Andrew Morton <> | Subject | Re: [RFC] first try for swap prefetch |
| |
Thomas Schlichter <schlicht@uni-mannheim.de> wrote: > > > you can just do > > > > if (radix_tree_delete(...) != -ENOENT) > > list_del(...) > > > > + read_swap_cache_async(entry); > > Sorry, but I think I can not. The list_del() needs the value returned by > radix_tree_lookup(), so I can not kick it...
OK, I'll change radix_tree_delete() to return the deleted object address if it was found, else NULL. That's a better API.
> Do you know how expensive the radix_tree_lookup() is? O(1) or O(log(n))?? For > my shame I do not really know that data structure... :-(
It is proportional to
log_base_64(largest index which the tree has ever stored)
log_base_64: because each node has 64 slots. Each time maxindex grows by a factor of 64 we need to introduce a new level.
"largest index ever": because we do not (and cannot feasibly) reduce the height when items are removed.
> > It might make sense to poke the speculative swapin code in the page-freeing > > path too. > > I wanted to do this but don't know which function is the correct one for this. > But I will search harder... or can you give me a hint?
free_pages_bulk() would probably suit.
diff -puN fs/nfs/write.c~radix_tree_delete-api-cleanup fs/nfs/write.c diff -puN lib/radix-tree.c~radix_tree_delete-api-cleanup lib/radix-tree.c --- 25/lib/radix-tree.c~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003 +++ 25-akpm/lib/radix-tree.c Fri Apr 11 14:30:30 2003 @@ -349,15 +349,18 @@ EXPORT_SYMBOL(radix_tree_gang_lookup); * @index: index key * * Remove the item at @index from the radix tree rooted at @root. + * + * Returns the address of the deleted item, or NULL if it was not present. */ -int radix_tree_delete(struct radix_tree_root *root, unsigned long index) +void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) { 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)) - return -ENOENT; + goto out; shift = (height-1) * RADIX_TREE_MAP_SHIFT; pathp->node = NULL; @@ -365,7 +368,7 @@ int radix_tree_delete(struct radix_tree_ while (height > 0) { if (*pathp->slot == NULL) - return -ENOENT; + goto out; pathp[1].node = *pathp[0].slot; pathp[1].slot = (struct radix_tree_node **) @@ -375,8 +378,9 @@ int radix_tree_delete(struct radix_tree_ height--; } - if (*pathp[0].slot == NULL) - return -ENOENT; + ret = *pathp[0].slot; + if (ret == NULL) + goto out; *pathp[0].slot = NULL; while (pathp[0].node && --pathp[0].node->count == 0) { @@ -387,8 +391,8 @@ int radix_tree_delete(struct radix_tree_ if (root->rnode == NULL) root->height = 0; /* Empty tree, we can reset the height */ - - return 0; +out: + return ret; } EXPORT_SYMBOL(radix_tree_delete); diff -puN mm/filemap.c~radix_tree_delete-api-cleanup mm/filemap.c diff -puN include/linux/radix-tree.h~radix_tree_delete-api-cleanup include/linux/radix-tree.h --- 25/include/linux/radix-tree.h~radix_tree_delete-api-cleanup Fri Apr 11 14:30:30 2003 +++ 25-akpm/include/linux/radix-tree.h Fri Apr 11 14:30:30 2003 @@ -43,7 +43,7 @@ do { \ 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 void *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); _
- 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/
| |