Re: [RFC] kernel facilities for cache prefetching

[Wu Fengguang <wfg@mail.ustc.edu.cn>]

On Thu, May 04, 2006 at 08:03:50AM -0700, Linus Torvalds wrote:
> Actually, I did something even simpler for a totally one-off thing: you 
> don't actually even need to drop caches or track pretty much anything, 
> it's sufficient for most analysis to just have a timestamp on each page 
> cache, and then have some way to read out the current cached contents.
> 
> You can then use the timestamps to get a pretty good idea of what order 
> things happened in.
 
> The really nice thing was that you don't even have to set the timestamp in 
> any complex place: you do it at page _allocation_ time. That automatically 
> gets the right answer for any page cache page, and you can do it in a 
> single place.

Looks nice.  A detailed scheme might be:

1) ctime/atime for each radixtree node(or, cluser of pages)
It seems to be a good accuracy/overhead compromise.
And is perfect for the most common case of sequential accesses.

struct radix_tree_node {
+        unsigned long ctime, atime;
} 

radix_tree_node_alloc()
{
+        node->ctime = some_virtual_time();
}

radix_tree_lookup_slot()
{
+        node->atime = some_virtual_time();
}

2) eviction-time for each recently evicted page
Store eviction-time _in place_ in the slot that used to store the
page's address, with minimal space/time impact.

+#define SLOT_IS_EVICTION_TIME  1
radix_tree_delete()
{
-                pathp->node->slots[pathp->offset] = NULL;
+                pathp->node->slots[pathp->offset] =
+                                 some_virtual_time() | SLOT_IS_EVICTION_TIME;
}

Regards,
Wu