From: Andrew Morton <akpm@digeo.com>
To: Thomas Schlichter <schlicht@uni-mannheim.de>
Cc: linux-kernel@vger.kernel.org
Subject: Re: [RFC] first try for swap prefetch
Date: Fri, 11 Apr 2003 14:39:32 -0700 [thread overview]
Message-ID: <20030411143932.6bd0b08a.akpm@digeo.com> (raw)
In-Reply-To: <200304111352.05774.schlicht@uni-mannheim.de>
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);
_
next prev parent reply other threads:[~2003-04-11 21:27 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-04-10 17:47 [RFC] first try for swap prefetch Thomas Schlichter
2003-04-10 23:18 ` Andrew Morton
2003-04-11 11:51 ` Thomas Schlichter
2003-04-11 12:13 ` William Lee Irwin III
2003-04-11 12:21 ` John Bradford
2003-04-11 12:22 ` Zwane Mwaikambo
2003-04-11 13:29 ` John Bradford
2003-04-11 21:39 ` Andrew Morton [this message]
2003-04-12 5:05 ` Thomas Schlichter
2003-04-12 5:37 ` Andrew Morton
2003-04-17 16:02 ` [RFC] second try for swap prefetch (does Oops!) Thomas Schlichter
2003-04-11 16:57 [RFC] first try for swap prefetch Chuck Ebbert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20030411143932.6bd0b08a.akpm@digeo.com \
--to=akpm@digeo.com \
--cc=linux-kernel@vger.kernel.org \
--cc=schlicht@uni-mannheim.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).