[PATCH] dcache 2nd chance replacement

[PATCH] dcache 2nd chance replacement

[Rik van Riel]

Hi,

I rediffed this trivial patch by Andrea (that went
into 2.2.19-pre5) which adds 2nd chance replacement
to the dentry cache, this should make our dcache
behave a little bit better than the current FIFO.

I know this probably isn't of any help under very low
and very high loads, but it should provide a nice
improvement under medium loads...

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/



--- linux-2.4.0-prerelease/include/linux/dcache.h.orig	Wed Jan  3 16:33:43 2001
+++ linux-2.4.0-prerelease/include/linux/dcache.h	Wed Jan  3 16:43:29 2001
@@ -115,6 +115,7 @@
 					 * If this dentry points to a directory, then
 					 * s_nfsd_free_path semaphore will be down
 					 */
+#define DCACHE_REFERENCED	0x0008  /* Recently used, don't discard. */
 
 extern spinlock_t dcache_lock;
 
--- linux-2.4.0-prerelease/fs/dcache.c.orig	Wed Jan  3 16:33:09 2001
+++ linux-2.4.0-prerelease/fs/dcache.c	Wed Jan  3 16:43:10 2001
@@ -339,10 +339,18 @@
 
 		if (tmp == &dentry_unused)
 			break;
-		dentry_stat.nr_unused--;
 		list_del_init(tmp);
 		dentry = list_entry(tmp, struct dentry, d_lru);
 
+		/* If the dentry was recently referenced, don't free it. */
+		if (dentry->d_flags & DCACHE_REFERENCED) {
+			dentry->d_flags &= ~DCACHE_REFERENCED;
+			list_add(&dentry->d_lru, &dentry_unused);
+			count--;
+			continue;
+		}
+		dentry_stat.nr_unused--;
+
 		/* Unused dentry with a count? */
 		if (atomic_read(&dentry->d_count))
 			BUG();
@@ -733,6 +741,7 @@
 		}
 		__dget_locked(dentry);
 		spin_unlock(&dcache_lock);
+		dentry->d_flags |= DCACHE_REFERENCED;
 		return dentry;
 	}
 	spin_unlock(&dcache_lock);

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Linus Torvalds]

On Wed, 3 Jan 2001, Rik van Riel wrote:
> 
> I rediffed this trivial patch by Andrea (that went
> into 2.2.19-pre5) which adds 2nd chance replacement
> to the dentry cache, this should make our dcache
> behave a little bit better than the current FIFO.

Looks ok, but I'd be happier if the

	dentry->d_flags |= DCACHE_REFERENCED;

line would be inside the dcache lock (ie just move it up a line). 

		Linus

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Wed, 3 Jan 2001, Linus Torvalds wrote:
> On Wed, 3 Jan 2001, Rik van Riel wrote:
> > 
> > I rediffed this trivial patch by Andrea (that went
> > into 2.2.19-pre5) which adds 2nd chance replacement
> > to the dentry cache, this should make our dcache
> > behave a little bit better than the current FIFO.
> 
> Looks ok, but I'd be happier if the
> 
> 	dentry->d_flags |= DCACHE_REFERENCED;
> 
> line would be inside the dcache lock (ie just move it up a line). 

OK, here's a new patch ;)

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/


--- linux-2.4.0-prerelease/include/linux/dcache.h.orig	Wed Jan  3 16:33:43 2001
+++ linux-2.4.0-prerelease/include/linux/dcache.h	Wed Jan  3 16:43:29 2001
@@ -115,6 +115,7 @@
 					 * If this dentry points to a directory, then
 					 * s_nfsd_free_path semaphore will be down
 					 */
+#define DCACHE_REFERENCED	0x0008  /* Recently used, don't discard. */
 
 extern spinlock_t dcache_lock;
 
--- linux-2.4.0-prerelease/fs/dcache.c.orig	Wed Jan  3 16:33:09 2001
+++ linux-2.4.0-prerelease/fs/dcache.c	Wed Jan  3 17:10:50 2001
@@ -339,10 +339,17 @@
 
 		if (tmp == &dentry_unused)
 			break;
-		dentry_stat.nr_unused--;
 		list_del_init(tmp);
 		dentry = list_entry(tmp, struct dentry, d_lru);
 
+		/* If the dentry was recently referenced, don't free it. */
+		if (dentry->d_flags & DCACHE_REFERENCED) {
+			dentry->d_flags &= ~DCACHE_REFERENCED;
+			list_add(&dentry->d_lru, &dentry_unused);
+			continue;
+		}
+		dentry_stat.nr_unused--;
+
 		/* Unused dentry with a count? */
 		if (atomic_read(&dentry->d_count))
 			BUG();
@@ -732,6 +739,7 @@
 				continue;
 		}
 		__dget_locked(dentry);
+		dentry->d_flags |= DCACHE_REFERENCED;
 		spin_unlock(&dcache_lock);
 		return dentry;
 	}

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Wed, Jan 03, 2001 at 04:59:16PM -0200, Rik van Riel wrote:
> I know this probably isn't of any help under very low
> and very high loads, but it should provide a nice
> improvement under medium loads...

It should provide an improvement under high VFS load (lots of files lookedup
and not kept referenced all the time).

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Wed, 3 Jan 2001, Andrea Arcangeli wrote:
> On Wed, Jan 03, 2001 at 04:59:16PM -0200, Rik van Riel wrote:
> > I know this probably isn't of any help under very low
> > and very high loads, but it should provide a nice
> > improvement under medium loads...
> 
> It should provide an improvement under high VFS load (lots of
> files lookedup and not kept referenced all the time).

Not really. Under very high VFS loads we'd just scan
through the list twice and free the entries anyway.

The only time when this scanning is an improvement is
when we have something like a "working set" for the
dentry cache *and* the refill/scan rate is constant
enough that that "working set" doesn't get flooded out
by the new dentry pages.

Note that creating a new dentry doesn't set the
referenced bit exactly to avoid this from happening.

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Wed, Jan 03, 2001 at 05:47:39PM -0200, Rik van Riel wrote:
> Not really. Under very high VFS loads we'd just scan
> through the list twice and free the entries anyway.

You're obviously wrong.

The higher was the load, the faster your working set was getting dropped from
the dcache. (with the patch the working set will have a chance to remains in
cache also with polluting going on instead, that's the whole point of aging:
to find out if something is worthwhile to keep in cache or not)

So the higher the VFS load definitely the higher improvement you will get.

The example with only pollution in the cache doesn't make sense, if you want to
optimize that case then remove the dcache in first place since it's only
overhead for such case.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Wed, 3 Jan 2001, Andrea Arcangeli wrote:
> On Wed, Jan 03, 2001 at 05:47:39PM -0200, Rik van Riel wrote:
> > Not really. Under very high VFS loads we'd just scan
> > through the list twice and free the entries anyway.
> 
> You're obviously wrong.
> 
> The higher was the load, the faster your working set was getting
> dropped from the dcache. (with the patch the working set will
> have a chance to remains in cache also with polluting going on
> instead,

> The example with only pollution in the cache doesn't make sense,

Ever heard of slocate / updatedb ?

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Wed, Jan 03, 2001 at 09:09:01PM -0200, Rik van Riel wrote:
> Ever heard of slocate / updatedb ?

ever heard of somebody killing all other tasks while updatedb is running?

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Thu, 4 Jan 2001, Andrea Arcangeli wrote:
> On Wed, Jan 03, 2001 at 09:09:01PM -0200, Rik van Riel wrote:
> > Ever heard of slocate / updatedb ?
> 
> ever heard of somebody killing all other tasks while updatedb is
> running?

Other tasks tend not to stress the dcache like updatedb does,
leading to the effect that updatedb can "flush out" the other
cached values faster than the other processes reference them.

This is something no amount of 2nd chance replacement or even
aging can prevent.

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Thu, Jan 04, 2001 at 01:00:28PM -0200, Rik van Riel wrote:
> Other tasks tend not to stress the dcache like updatedb does,
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> leading to the effect that updatedb can "flush out" the other
> cached values faster than the other processes reference them.
> 
> This is something no amount of 2nd chance replacement or even
> aging can prevent.

Your arguments are senseless.

The dcache aging is mostly useful with _high_ VFS load like updatedb in
background. The logic is the same of the VM aging (ask yourself when the VM
aging is most useful: when there's high VM load, like a `cp /dev/zero .` in
background, the updatedb is the equivalent of `cp /dev/zero .` but for the
dcache).  Without the aging the "referenced" cache would be thrown away as well
with the rest of the cache pollution, while with the aging the "referenced"
cache will have a chance to remain in cache. This is true for both VM cache and
dcache.  The higher the load, the more times your working set would been thrown
away without the aging, so the higher improvement you get thanks to the aging.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Thu, 4 Jan 2001, Andrea Arcangeli wrote:
> On Thu, Jan 04, 2001 at 01:00:28PM -0200, Rik van Riel wrote:
> > Other tasks tend not to stress the dcache like updatedb does,
>   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > leading to the effect that updatedb can "flush out" the other
> > cached values faster than the other processes reference them.
> > 
> > This is something no amount of 2nd chance replacement or even
> > aging can prevent.
> 
> Your arguments are senseless.

I could say the same of yours if I let myself
sink to that level ;) </obflamebait>

> The dcache aging is mostly useful with _high_ VFS load like
> updatedb in background. The logic is the same of the VM aging
> (ask yourself when the VM aging is most useful: when there's
> high VM load, like a `cp /dev/zero .`

This is exactly the point where page aging alone isn't good
enough and you need something like drop-behind...

(yes, there IS a reason why we have drop_behind() and page
deactivation in generic_file_write)

regards,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Thu, Jan 04, 2001 at 02:23:53PM -0200, Rik van Riel wrote:
> > The dcache aging is mostly useful with _high_ VFS load like
> > updatedb in background. The logic is the same of the VM aging
> > (ask yourself when the VM aging is most useful: when there's
> > high VM load, like a `cp /dev/zero .`
> 
> This is exactly the point where page aging alone isn't good
> enough and you need something like drop-behind...
> 
> (yes, there IS a reason why we have drop_behind() and page
> deactivation in generic_file_write)

This is totally offtopic. We were _not_ talking about other algorithms.  We
were _only_ talking about _when_ the 1 bit of aging I introduced with my
algorithm improves performance at max.  My answer is that the max performance
improvement happens when there's the _highest_ VFS load in background and you
disagreed.  Everything else has nothing to do with this our previous discussion
so your above reply partly still doesn't make sense to me.

Talking about the new topic you introduced above with your offtopic reply, I
think that for a thing like dcache 1 bit of aging is more than enough
(and btw, in my 2.4.x VM tree I put a 1 bit of aging also in the icache).  In
case you didn't realized the frequency the dcache gets recycled completly is
much much much lower than the frequency something like the pagecache can be
recycled completly. So you have relatively plenty of time before the referenced
dentries gets collected.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Thu, 4 Jan 2001, Andrea Arcangeli wrote:

> This is totally offtopic. We were _not_ talking about other
> algorithms.  We were _only_ talking about _when_ the 1 bit of
> aging I introduced with my algorithm improves performance at
> max.  My answer is that the max performance improvement happens
> when there's the _highest_ VFS load in background and you
> disagreed.  Everything else has nothing to do with this our
> previous discussion so your above reply partly still doesn't
> make sense to me.

Not only did I disagree, I also explained you why it
doesn't work the way you envision.

Unfortunately you seem to ignore my arguments, so lets
close this thread.

EOT,

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Andrea Arcangeli]

On Thu, Jan 04, 2001 at 02:59:49PM -0200, Rik van Riel wrote:
> Unfortunately you seem to ignore my arguments, so lets

I've not ignored them, as said they were either obviously wrong of offtopic.

Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Rik van Riel]

On Thu, 4 Jan 2001, Andrea Arcangeli wrote:
> On Thu, Jan 04, 2001 at 02:59:49PM -0200, Rik van Riel wrote:
> > Unfortunately you seem to ignore my arguments, so lets
> 
> I've not ignored them, as said they were either obviously wrong
> of offtopic.

Without giving any arguments ;)

Rik
--
Hollywood goes for world dumbination,
	Trailer at 11.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com.br/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Alan Cox]

> On Thu, Jan 04, 2001 at 02:59:49PM -0200, Rik van Riel wrote:
> > Unfortunately you seem to ignore my arguments, so lets
> I've not ignored them, as said they were either obviously wrong of offtopic.

Would the two of you ajourn this debate to alt.flame

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [PATCH] dcache 2nd chance replacement

[Chris Evans]

On Thu, 4 Jan 2001, Alan Cox wrote:

> > On Thu, Jan 04, 2001 at 02:59:49PM -0200, Rik van Riel wrote:
> > > Unfortunately you seem to ignore my arguments, so lets
> > I've not ignored them, as said they were either obviously wrong of offtopic.
>
> Would the two of you ajourn this debate to alt.flame

Better still stop _theorizing_ and start _measuring_

Cheers
Chris

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/