Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[Ed Tomlinson]

----------  Forwarded Message  ----------
Subject: Re: [PATCH][RFC] appling preasure to icache and dcache
Date: Tue, 3 Apr 2001 17:22:10 -0400
From: Ed Tomlinson <tomlins@cam.org>
To: bredelin@ucla.edu
Cc: l 


On Tuesday 03 April 2001 11:03, Benjamin Redelings I wrote:
> Hi, I'm glad somebody is working on this!  VM-time seems like a pretty
> useful concept.

Think it might be useful for detecting trashing too.  If vmtime is made
to directly relate to the page allocation rate then you can do something
like this.  Let K be a number intially representing 25% of ram pages.
Because vmtime is directly releated to allocation rates its meanful to
subtract K from the current vmtime.  For each swapped out page, record
the current vmtime.  Now if the recorded vmtime of the page you are
swapping in is greater than vmtime-K increment A otherwise increment B.
If A>B we are thrashing.  We decay A and B via kswapd.  We adjust K
depending on the swapping rate.  Thoughts?

> 	I think you have a bug in your patch here:
>
> +       if (base > pages)       /* If the cache shrunk reset base,  The
> cache
> +               base = pages;    * growing applies preasure as does
> expanding
> +       if (free > old)          * free space - even if later shrinks */
> +               base -= (base>free-old) ? free-old : base;
>
> It looks like you unintentionally commented out two lines of code?

Geez.  That will teach me to add comments _after_ testing the code...
The patch as it stands, will not apply pressure as the caches expands.
Good catch.  Thanks.

> 	I have been successfully running your patch.  But I think it needs
> benchmarks.  At the very least, compile the kernel twice w/o and twice
> w/ your patch and see how it changes the times.  I do not think I will
> have time to do it myself anytime soon unfortunately.
> 	I have a 64Mb RAM machine, and the patch makes the system feel a little
> bit slower when hitting the disk.  BUt that is subjective...

Where I see a difference is with backups.  With the patch applied they take
about 2:20 or so, and use over 60K inodes/dentries, without the patch they
take 2:35 (plus or minus 5 mins) and use over 190K inodes/dentries.  On a box
with lots of memory pressure (ie with 64M) I doubt that the calls to shrink
the caches get triggered often from my code - expect that you are usually
shrinking via do_try_to_free_pages.  What might cause your subjective
 difference may be the change in:

refill_inactive_scan(DEF_PRIORITY, delta);

You might want to try replacing this delta with 0 (in kswapd).  If this
 improves things for you I have to do a little rethinking...

Corrected patch follows:

---
diff -u -r --exclude-from=ex.txt linux.ac28/mm/page_alloc.c
 linux/mm/page_alloc.c --- linux.ac28/mm/page_alloc.c	Sun Apr  1 18:52:22
 2001
+++ linux/mm/page_alloc.c	Mon Apr  2 07:54:05 2001
@@ -138,11 +138,9 @@

 	/*
 	 * We don't want to protect this variable from race conditions
-	 * since it's nothing important, but we do want to make sure
-	 * it never gets negative.
+	 * since it's nothing important.
 	 */
-	if (memory_pressure > NR_CPUS)
-		memory_pressure--;
+	inactivate_pressure++;
 }

 #define MARK_USED(index, order, area) \
diff -u -r --exclude-from=ex.txt linux.ac28/mm/swap.c linux/mm/swap.c
--- linux.ac28/mm/swap.c	Mon Jan 22 16:30:21 2001
+++ linux/mm/swap.c	Thu Mar 29 11:37:47 2001
@@ -47,10 +47,12 @@
  * many inactive pages we should have.
  *
  * In reclaim_page and __alloc_pages: memory_pressure++
- * In __free_pages_ok: memory_pressure--
+ * In __free_pages_ok: inactivate_pressure++
+ * In invalidate_pages_scan: inactivate_pressure++
  * In recalculate_vm_stats the value is decayed (once a second)
  */
 int memory_pressure;
+int inactivate_pressure;

 /* We track the number of pages currently being asynchronously swapped
    out, so that we don't try to swap TOO many pages out at once */
@@ -287,6 +289,7 @@
 	 * memory_pressure.
 	 */
 	memory_pressure -= (memory_pressure >> INACTIVE_SHIFT);
+	inactivate_pressure -= (inactivate_pressure >> INACTIVE_SHIFT);
 }

 /*
diff -u -r --exclude-from=ex.txt linux.ac28/mm/vmscan.c linux/mm/vmscan.c
--- linux.ac28/mm/vmscan.c	Sun Apr  1 18:52:22 2001
+++ linux/mm/vmscan.c	Mon Apr  2 07:42:55 2001
@@ -759,6 +791,8 @@
 	}
 	spin_unlock(&pagemap_lru_lock);

+	inactivate_pressure += nr_deactivated;
+
 	return nr_deactivated;
 }

@@ -937,6 +971,76 @@
 	return ret;
 }

+/*
+ * Try to shrink the dcache if either its size or free space
+ * has grown, and it looks like we might get the required pages.
+ * This function would simplify if the caches tracked how
+ * many _pages_ were freeable.
+ */
+int try_shrinking_dcache(int goal, unsigned int gfp_mask)
+{
+
+	/* base - projects the threshold above which we can free pages */
+
+	static int base, free = 0;
+	int pages, old, ret;
+
+	old = free;			/* save old free space size */
+
+	pages = (dentry_stat.nr_dentry * sizeof(struct dentry)) >> PAGE_SHIFT;
+	free = (dentry_stat.nr_unused * sizeof(struct dentry)) >> PAGE_SHIFT;
+
+	if (base > pages)	/* If the cache shrunk reset base,  The cache */
+		base = pages;	/* growing applies preasure as does expanding */
+	if (free > old)		/* free space - even if later shrinks */
+		base -= (base>free-old) ? free-old : base;
+
+	/* try free pages...  Note that the using inactive_pressure _is_
+	 * racy.  It does not matter, a bad guess will not hurt us.
+	 * Testing free here does not work effectivily.
+	 */
+
+	if (pages-base >= goal) {
+		ret = inactivate_pressure;
+       		shrink_dcache_memory(DEF_PRIORITY, gfp_mask);
+		ret = inactivate_pressure - ret;
+		base += (!ret) ? pages-base : (ret>goal) ? ret : goal;
+	} else
+		ret = 0;
+
+	return ret;
+}
+
+/*
+ * Same logic as above but for the icache.
+ */
+int try_shrinking_icache(int goal, unsigned int gfp_mask)
+{
+	static int base, free = 0;
+	int pages, old, ret;
+
+	old = free;
+
+	pages = (inodes_stat.nr_inodes * sizeof(struct inode)) >> PAGE_SHIFT;
+	free = (inodes_stat.nr_unused * sizeof(struct inode)) >> PAGE_SHIFT;
+
+	if (base > pages)
+		base = pages;
+	if (free > old)
+		base -= (base>free-old) ? free-old : base;
+
+	if (pages-base >= goal) {
+		ret = inactivate_pressure;
+       		shrink_icache_memory(DEF_PRIORITY, gfp_mask);
+		ret = inactivate_pressure - ret;
+		base += (!ret) ? pages-base : (ret>goal) ? ret : goal;
+	} else
+		ret = 0;
+
+	return ret;
+}
+
+
 DECLARE_WAIT_QUEUE_HEAD(kswapd_wait);
 DECLARE_WAIT_QUEUE_HEAD(kswapd_done);
 struct task_struct *kswapd_task;
@@ -984,18 +1088,28 @@
 	 */
 	for (;;) {
 		static int recalc = 0;
+		int delta = 0;

 		/* If needed, try to free some memory. */
 		if (inactive_shortage() || free_shortage())
 			do_try_to_free_pages(GFP_KSWAPD, 0);

 		/*
-		 * Do some (very minimal) background scanning. This
-		 * will scan all pages on the active list once
-		 * every minute. This clears old referenced bits
-		 * and moves unused pages to the inactive list.
+		 * Try to keep the rate of pages inactivations
+		 * similar to the rate of pages allocations.  This
+		 * also perform background page aging, but only
+		 * when there is preasure on the vm.  We get the
+		 * pages from the dcache and icache if its likely
+		 * there are enought freeable pages there.
 		 */
-		refill_inactive_scan(DEF_PRIORITY, 0);
+		delta = (memory_pressure >> INACTIVE_SHIFT) \
+			- (inactivate_pressure >> INACTIVE_SHIFT);
+		if (delta > 0)
+			delta -= try_shrinking_dcache(delta,GFP_KSWAPD);
+		if (delta > 0)
+			delta -= try_shrinking_icache(delta,GFP_KSWAPD);
+		if (delta > 0)
+			refill_inactive_scan(DEF_PRIORITY, delta);

 		/* Once a second, recalculate some VM stats. */
 		if (time_after(jiffies, recalc + HZ)) {
--- linux.ac28/include/linux/swap.h	Sun Apr  1 18:52:22 2001
+++ linux/include/linux/swap.h	Thu Mar 29 11:31:09 2001
@@ -102,6 +102,7 @@

 /* linux/mm/swap.c */
 extern int memory_pressure;
+extern int inactivate_pressure;
 extern void age_page_up(struct page *);
 extern void age_page_up_nolock(struct page *);
 extern void age_page_down(struct page *);
---

Ed Tomlinson <tomlins@cam.org>

-------------------------------------------------------
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[Rik van Riel]

On Tue, 3 Apr 2001, Ed Tomlinson wrote:
> On Tuesday 03 April 2001 11:03, Benjamin Redelings I wrote:
> > Hi, I'm glad somebody is working on this!  VM-time seems like a pretty
> > useful concept.
> 
> Think it might be useful for detecting trashing too.  If vmtime is
> made to directly relate to the page allocation rate then you can do
> something like this.  Let K be a number intially representing 25% of
> ram pages. Because vmtime is directly releated to allocation rates its
> meanful to subtract K from the current vmtime.  For each swapped out
> page, record the current vmtime.  Now if the recorded vmtime of the
> page you are swapping in is greater than vmtime-K increment A
> otherwise increment B. If A>B we are thrashing.  We decay A and B via
> kswapd.  We adjust K depending on the swapping rate.  Thoughts?

Hmmm, how exactly would this algorithm work ?

>From your description above, I can't quite see how it would
work (or why it would work).

regards,

Rik
--
Virtual memory is like a game you can't win;
However, without VM there's truly nothing to lose...

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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[Ed Tomlinson]

On Tuesday 03 April 2001 17:35, Rik van Riel wrote:
> On Tue, 3 Apr 2001, Ed Tomlinson wrote:
> > On Tuesday 03 April 2001 11:03, Benjamin Redelings I wrote:
> > > Hi, I'm glad somebody is working on this!  VM-time seems like a pretty
> > > useful concept.
> >
> > Think it might be useful for detecting trashing too.  If vmtime is
> > made to directly relate to the page allocation rate then you can do
> > something like this.  Let K be a number intially representing 25% of
> > ram pages. Because vmtime is directly releated to allocation rates its
> > meanful to subtract K from the current vmtime.  For each swapped out
> > page, record the current vmtime.  Now if the recorded vmtime of the
> > page you are swapping in is greater than vmtime-K increment A
> > otherwise increment B. If A>B we are thrashing.  We decay A and B via
> > kswapd.  We adjust K depending on the swapping rate.  Thoughts?
>
> Hmmm, how exactly would this algorithm work ?
>
> From your description above, I can't quite see how it would
> work (or why it would work).

First remember the vmtime increments when ever we allocate a page.  Second we
record the vmtime for each page as its swapped out.  If we are thrashing we are 
cycling through sets of pages.  The swap out vmtime of most (if not all) of these
pages will be greater than some K.  So what I see the above doing is telling us
we are swaping in stuff we reciently swapped out.  If we are swapping normally
this should not be a normal distribution.  Another way to look at this would
be to find a value of K such that |A-B| is small.  If K is small and the swap
rate is high we are thrashing.  What is trashing is another question...

I am not sure this would catch _all_ cases but bet it would get a large percentage
of them.

Ed  
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[sfkaplan]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi.  Just a few thoughts that I hope will be useful.

On Tue, 3 Apr 2001, Ed Tomlinson wrote:

> On Tuesday 03 April 2001 17:35, Rik van Riel wrote:
> > On Tue, 3 Apr 2001, Ed Tomlinson wrote:
> > > On Tuesday 03 April 2001 11:03, Benjamin Redelings I wrote:
> > > > Hi, I'm glad somebody is working on this!  VM-time seems like a pretty
> > > > useful concept.

The notion of VM time has been kicking around for about 10 years.  I
picked it up from my graduate advisor, and so it has worked its way
into a number of research ideas.  This approach to measuring VM time
is an interesting one, and slightly different from the way in which
I've approached it.

> > > Think it might be useful for detecting trashing too.  If vmtime is
> > > made to directly relate to the page allocation rate then you can do
> > > something like this.  Let K be a number intially representing 25% of
> > > ram pages. Because vmtime is directly releated to allocation rates its
> > > meanful to subtract K from the current vmtime.  For each swapped out
> > > page, record the current vmtime.  Now if the recorded vmtime of the
> > > page you are swapping in is greater than vmtime-K increment A
> > > otherwise increment B. If A>B we are thrashing.  We decay A and B via
> > > kswapd.  We adjust K depending on the swapping rate.  Thoughts?

A couple of thoughts:

1) Nit-pick:  You mean "thrashing", not "trashing", right?  Or is
   there a definition of "trashing" with which I'm not familiar?

2) There's a difference between detecting that the VM system is
   evicting pages and then using them shortly thereafter, and
   detecting thrashing.  Your description above may detect the former
   case -- It's something that AIX did many years ago (or so I'm told
   by some IBM researchers), and it's a simplified case of what EELRU,
   an algorithm I was part of developing, detects.  It's a useful
   case, because it likely indicates a loop-like reference pattern
   over slightly more memory than is available, forcing LRU to
   degenerate into FIFO.

   However, it is not necessarily detecting thrashing.  "Heavy paging"
   and "thrashing" aren't necessarily the same thing.  Thrashing
   occurs when so much time is spent servicing page faults that the
   CPU rarely has any work to do (i.e. no ready processes to run.)  It
   is easily possible to thrash without tripping the detection
   mechanism that you're describing.

3) Your detection mechanism seems as though it would detect something
   interesting.  However, I don't understand the response that you
   describe.  Decaying A and B seems fine, and an important part of
   accurate detection based on recent behavior.  However, why adjust
   K?  That doesn't seem to solve the problem.  The process may still
   continue to reference pages evicted not long ago.  Addressing
   this case reqires either a larger memory allocation (somehow or
   other) or a modification of the replacement policy (some non-LRU
   evictions).  If you adjust K to be smaller, than you're just less
   likely to trip the detection mechanism.  If you make K larger, it
   becomes more likely.  You'll still have the same problem.

I hope these comments help.  More likely than not, I've misunderstood
what you're proposing.  If so, please let me know what I've botched.

Scott Kaplan
sfkaplan@cs.amherst.edu
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE6yxZH8eFdWQtoOmgRAkggAJ4pY9eWIpl55yQteuYgD4eraCTk5wCgivNp
etqUh9afUf2cZ7zA1dAVf30=
=YGhN
-----END PGP SIGNATURE-----

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[Ed Tomlinson]

On Wednesday 04 April 2001 08:40, sfkaplan@cs.amherst.edu wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi.  Just a few thoughts that I hope will be useful.
>
> On Tue, 3 Apr 2001, Ed Tomlinson wrote:
> > On Tuesday 03 April 2001 17:35, Rik van Riel wrote:
> > > On Tue, 3 Apr 2001, Ed Tomlinson wrote:
> > > > On Tuesday 03 April 2001 11:03, Benjamin Redelings I wrote:
> > > > > Hi, I'm glad somebody is working on this!  VM-time seems like a
> > > > > pretty useful concept.
>
> The notion of VM time has been kicking around for about 10 years.  I
> picked it up from my graduate advisor, and so it has worked its way
> into a number of research ideas.  This approach to measuring VM time
> is an interesting one, and slightly different from the way in which
> I've approached it.

I am aware that vmtime has been around for a while - just not implemented
in linux.

> > > > Think it might be useful for detecting trashing too.  If vmtime is
> > > > made to directly relate to the page allocation rate then you can do
> > > > something like this.  Let K be a number intially representing 25% of
> > > > ram pages. Because vmtime is directly releated to allocation rates
> > > > its meanful to subtract K from the current vmtime.  For each swapped
> > > > out page, record the current vmtime.  Now if the recorded vmtime of
> > > > the page you are swapping in is greater than vmtime-K increment A
> > > > otherwise increment B. If A>B we are thrashing.  We decay A and B via
> > > > kswapd.  We adjust K depending on the swapping rate.  Thoughts?
>
> A couple of thoughts:
>
> 1) Nit-pick:  You mean "thrashing", not "trashing", right?  Or is
>    there a definition of "trashing" with which I'm not familiar?

Right - spelling is _not_ my forte.

> 2) There's a difference between detecting that the VM system is
>    evicting pages and then using them shortly thereafter, and
>    detecting thrashing.  Your description above may detect the former
>    case -- It's something that AIX did many years ago (or so I'm told
>    by some IBM researchers), and it's a simplified case of what EELRU,
>    an algorithm I was part of developing, detects.  It's a useful
>    case, because it likely indicates a loop-like reference pattern
>    over slightly more memory than is available, forcing LRU to
>    degenerate into FIFO.
>
>    However, it is not necessarily detecting thrashing.  "Heavy paging"
>    and "thrashing" aren't necessarily the same thing.  Thrashing
>    occurs when so much time is spent servicing page faults that the
>    CPU rarely has any work to do (i.e. no ready processes to run.)  It
>    is easily possible to thrash without tripping the detection
>    mechanism that you're describing.

I am very aware that heavy paging, which is ok _if_ you have the bandwidth, 
and thrashing are different.

> 3) Your detection mechanism seems as though it would detect something
>    interesting.  However, I don't understand the response that you
>    describe.  Decaying A and B seems fine, and an important part of
>    accurate detection based on recent behavior.  However, why adjust
>    K?  That doesn't seem to solve the problem.  The process may still
>    continue to reference pages evicted not long ago.  Addressing
>    this case reqires either a larger memory allocation (somehow or
>    other) or a modification of the replacement policy (some non-LRU
>    evictions).  If you adjust K to be smaller, than you're just less
>    likely to trip the detection mechanism.  If you make K larger, it
>    becomes more likely.  You'll still have the same problem.

Wonder what gets detected if you adjust K such that abs(A-B) is small?
if K is near the current vmtime you have a case where EELRU might help.
as K approaches vmtime+physical pages you have thrashing?  Think that,
with some work, these sorts of metrics could be effective in detecting
many cases of thrashing.

> I hope these comments help.  More likely than not, I've misunderstood
> what you're proposing.  If so, please let me know what I've botched.

Comments like these always help (even the spelling <grin>).  

Thanks

Ed Tomlinson <tomlins@cam.org>
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: Fwd: Re: [PATCH][RFC] appling preasure to icache and dcache

[Rik van Riel]

On Thu, 5 Apr 2001, Ed Tomlinson wrote:

> I am very aware that heavy paging, which is ok _if_ you have the
> bandwidth, and thrashing are different.

So can we conclude that for a simple "thrashing approximation"
we should at least measure if we're loading the disk subsystem
heavily ?

(heavy disk load -> more disk seeks -> self-perpetuating situation)

regards,

Rik
--
Virtual memory is like a game you can't win;
However, without VM there's truly nothing to lose...

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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/