Re: [RFC] first try for swap prefetch

[Andrew Morton]

Thomas Schlichter <[e-mail]> 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);

_