[PATCH] token based thrashing control

[PATCH] token based thrashing control

[Rik van Riel]

	
The following experimental patch implements token based thrashing
protection, using the algorithm described in:

	http://www.cs.wm.edu/~sjiang/token.htm

When there are pageins going on, a task can grab a token, that
protects the task from pageout (except by itself) until it is
no longer doing heavy pageins, or until the maximum hold time
of the token is over.

If the maximum hold time is exceeded, the task isn't eligable
to hold the token for a while more, since it wasn't doing it
much good anyway.

I have run a very unscientific benchmark on my system to test
the effectiveness of the patch, timing how a 230MB two-process
qsbench run takes, with and without the token thrashing
protection present.

normal 2.6.8-rc6:	6m45s
2.6.8-rc6 + token:	4m24s

This is a quick hack, implemented without having talked to the
inventor of the algorithm.  He's copied on the mail and I suspect
we'll be able to do better than my quick implementation ...

Please test this patch.

 include/linux/sched.h |    4 ++
 include/linux/swap.h  |   21 ++++++++++
 kernel/fork.c         |    2 +
 mm/Makefile           |    2 -
 mm/filemap.c          |    1 
 mm/memory.c           |    1 
 mm/rmap.c             |    3 +
 mm/thrash.c           |  100 ++++++++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 133 insertions(+), 1 deletion(-)

--- linux-2.6.7/include/linux/swap.h.token	2004-07-30 13:22:17.000000000 -0400
+++ linux-2.6.7/include/linux/swap.h	2004-07-30 16:39:27.000000000 -0400
@@ -204,6 +204,27 @@
 extern struct page * lookup_swap_cache(swp_entry_t);
 extern struct page * read_swap_cache_async(swp_entry_t, struct vm_area_struct *vma,
 					   unsigned long addr);
+/* linux/mm/thrash.c */
+#ifdef CONFIG_SWAP
+extern struct mm_struct * swap_token_mm;
+extern void grab_swap_token(void);
+extern void __put_swap_token(struct mm_struct *);
+
+static inline int has_swap_token(struct mm_struct * mm)
+{
+	return (mm == swap_token_mm);
+}
+
+static inline void put_swap_token(struct mm_struct * mm)
+{
+	if (has_swap_token(mm))
+		__put_swap_token(mm);
+}
+#else /* CONFIG_SWAP */
+#define put_swap_token do { } while(0)
+#define grab_swap_token  do { } while(0)
+#define has_swap_token 0
+#endif /* CONFIG_SWAP */
 
 /* linux/mm/swapfile.c */
 extern long total_swap_pages;
--- linux-2.6.7/include/linux/sched.h.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/include/linux/sched.h	2004-07-30 13:22:29.000000000 -0400
@@ -239,6 +239,10 @@
 	/* Architecture-specific MM context */
 	mm_context_t context;
 
+	/* Token based thrashing protection. */
+	unsigned long swap_token_time;
+	char recent_pagein;
+
 	/* coredumping support */
 	int core_waiters;
 	struct completion *core_startup_done, core_done;
--- linux-2.6.7/kernel/fork.c.token	2004-07-30 13:22:27.000000000 -0400
+++ linux-2.6.7/kernel/fork.c	2004-07-30 13:22:29.000000000 -0400
@@ -36,6 +36,7 @@
 #include <linux/mount.h>
 #include <linux/audit.h>
 #include <linux/rmap.h>
+#include <linux/swap.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -463,6 +464,7 @@
 		exit_aio(mm);
 		exit_mmap(mm);
 		mmdrop(mm);
+		put_swap_token(mm);
 	}
 }
 
--- linux-2.6.7/mm/memory.c.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/mm/memory.c	2004-07-30 13:22:29.000000000 -0400
@@ -1433,6 +1433,7 @@
 		/* Had to read the page from swap area: Major fault */
 		ret = VM_FAULT_MAJOR;
 		inc_page_state(pgmajfault);
+		grab_swap_token();
 	}
 
 	mark_page_accessed(page);
--- linux-2.6.7/mm/filemap.c.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/mm/filemap.c	2004-07-30 13:22:29.000000000 -0400
@@ -1195,6 +1195,7 @@
 	 * effect.
 	 */
 	error = page_cache_read(file, pgoff);
+	grab_swap_token();
 
 	/*
 	 * The page we want has now been added to the page cache.
--- /dev/null	2003-09-15 09:40:47.000000000 -0400
+++ linux-2.6.7/mm/thrash.c	2004-07-30 16:55:00.000000000 -0400
@@ -0,0 +1,100 @@
+/*
+ * mm/thrash.c
+ *
+ * Copyright (C) 2004, Red Hat, Inc.
+ * Copyright (C) 2004, Rik van Riel <riel@redhat.com>
+ * Released under the GPL, see the file COPYING for details.
+ *
+ * Simple token based thrashing protection, using the algorithm
+ * described in:  http://www.cs.wm.edu/~sjiang/token.pdf
+ */
+#include <linux/jiffies.h>
+#include <linux/mm.h>
+#include <linux/sched.h>
+#include <linux/swap.h>
+
+static spinlock_t swap_token_lock = SPIN_LOCK_UNLOCKED;
+static unsigned long swap_token_timeout;
+unsigned long swap_token_check;
+struct mm_struct * swap_token_mm = &init_mm;
+
+#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2)
+#define SWAP_TOKEN_TIMEOUT (HZ * 300)
+
+/*
+ * Take the token away if the process had no page faults
+ * in the last interval, or if it has held the token for
+ * too long.
+ */
+#define SWAP_TOKEN_ENOUGH_RSS 1
+#define SWAP_TOKEN_TIMED_OUT 2
+static int should_release_swap_token(struct mm_struct * mm)
+{
+	int ret = 0;
+	if (!mm->recent_pagein)
+		ret = SWAP_TOKEN_ENOUGH_RSS;
+	else if (time_after(jiffies, swap_token_timeout))
+		ret = SWAP_TOKEN_TIMED_OUT;
+	mm->recent_pagein = 0;
+	return ret;
+}
+
+/*
+ * Try to grab the swapout protection token.  We only try to
+ * grab it once every TOKEN_CHECK_INTERVAL, both to prevent
+ * SMP lock contention and to check that the process that held
+ * the token before is no longer thrashing.
+ */
+void grab_swap_token(void)
+{
+	struct mm_struct * mm;
+	int reason;
+
+	/* We have the token. Let others know we still need it. */
+	if (has_swap_token(current->mm)) {
+		current->mm->recent_pagein = 1;
+		return;
+	}
+
+	if (time_after(jiffies, swap_token_check)) {
+
+		/* Can't get swapout protection if we exceed our RSS limit. */
+		// if (current->mm->rss > current->mm->rlimit_rss)
+		//	return;
+
+		/* ... or if we recently held the token. */
+		if (time_before(jiffies, current->mm->swap_token_time))
+			return;
+
+		if (!spin_trylock(&swap_token_lock))
+			return;
+
+		swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
+
+		mm = swap_token_mm;
+		if ((reason = should_release_swap_token(mm))) {
+			unsigned long eligable = jiffies;
+			if (reason == SWAP_TOKEN_TIMED_OUT) {
+				eligable += SWAP_TOKEN_TIMEOUT;
+			}
+			mm->swap_token_time = eligable;
+			swap_token_timeout = jiffies + SWAP_TOKEN_TIMEOUT;
+			swap_token_mm = current->mm;
+			printk("Took swap token, pid %d (%s)\n",
+				 current->pid, current->comm);
+		}
+		spin_unlock(&swap_token_lock);
+	}
+	return;
+}
+
+/* Called on process exit. */
+void __put_swap_token(struct mm_struct * mm)
+{
+	spin_lock(&swap_token_lock);
+	if (mm == swap_token_mm) {
+		swap_token_mm = &init_mm;
+		swap_token_check = jiffies;
+	}
+	spin_unlock(&swap_token_lock);
+}
--- linux-2.6.7/mm/rmap.c.token	2004-07-30 13:22:24.000000000 -0400
+++ linux-2.6.7/mm/rmap.c	2004-07-30 13:22:29.000000000 -0400
@@ -230,6 +230,9 @@
 	if (ptep_clear_flush_young(vma, address, pte))
 		referenced++;
 
+	if (mm != current->mm && has_swap_token(mm))
+		referenced++;
+
 	(*mapcount)--;
 
 out_unmap:
--- linux-2.6.7/mm/Makefile.token	2004-07-30 13:22:27.000000000 -0400
+++ linux-2.6.7/mm/Makefile	2004-07-30 13:22:29.000000000 -0400
@@ -12,7 +12,7 @@
 			   readahead.o slab.o swap.o truncate.o vmscan.o \
 			   $(mmu-y)
 
-obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o
+obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o
 obj-$(CONFIG_X86_4G)	+= usercopy.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Nikita Danilov]

Rik van Riel writes:
 > 	
 > The following experimental patch implements token based thrashing
 > protection, using the algorithm described in:
 > 
 > 	http://www.cs.wm.edu/~sjiang/token.htm
 > 
 > When there are pageins going on, a task can grab a token, that
 > protects the task from pageout (except by itself) until it is
 > no longer doing heavy pageins, or until the maximum hold time
 > of the token is over.
 > 
 > If the maximum hold time is exceeded, the task isn't eligable
 > to hold the token for a while more, since it wasn't doing it
 > much good anyway.

[...]

 > --- linux-2.6.7/mm/filemap.c.token	2004-07-30 13:22:28.000000000 -0400
 > +++ linux-2.6.7/mm/filemap.c	2004-07-30 13:22:29.000000000 -0400
 > @@ -1195,6 +1195,7 @@
 >  	 * effect.
 >  	 */
 >  	error = page_cache_read(file, pgoff);
 > +	grab_swap_token();

Token functions are declared to be no-ops if !CONFIG_SWAP, but here
token is used for file-system backed page-fault.

 >  

Nikita.
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Sat, 31 Jul 2004, Nikita Danilov wrote:

> Token functions are declared to be no-ops if !CONFIG_SWAP, but here
> token is used for file-system backed page-fault.

I figure that if somebody disables CONFIG_SWAP they don't
want the extra code of token based thrashing control ;)

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Andrew Morton]

Rik van Riel <riel@redhat.com> wrote:
>
> The following experimental patch implements token based thrashing
>  protection, 

Thanks for this - it is certainly needed.

As you say, qsbench throughput is greatly increased (4x here).  But the old
`make -j4 vmlinux' with mem=64m shows no benefit at all.

I figured it was the short-lived processes, so I added the below, which
passes the token to the child across exec, and back to the parent on exit. 
Although it appears to work correctly, it too make no difference.

btw, in page_referenced_one():

+	if (mm != current->mm && has_swap_token(mm))
+		referenced++;

what's the reason for the `mm != current->mm' test?



diff -puN fs/exec.c~token-based-thrashing-control-inheritance fs/exec.c
--- 25/fs/exec.c~token-based-thrashing-control-inheritance	2004-08-01 03:42:04.191461248 -0700
+++ 25-akpm/fs/exec.c	2004-08-01 03:42:04.199460032 -0700
@@ -1146,6 +1146,7 @@ int do_execve(char * filename,
 
 		/* execve success */
 		security_bprm_free(&bprm);
+		take_swap_token();
 		return retval;
 	}
 
diff -puN include/linux/swap.h~token-based-thrashing-control-inheritance include/linux/swap.h
--- 25/include/linux/swap.h~token-based-thrashing-control-inheritance	2004-08-01 03:42:04.193460944 -0700
+++ 25-akpm/include/linux/swap.h	2004-08-01 03:42:04.198460184 -0700
@@ -209,6 +209,7 @@ extern struct page * read_swap_cache_asy
 extern struct mm_struct * swap_token_mm;
 extern void grab_swap_token(void);
 extern void __put_swap_token(struct mm_struct *);
+extern void take_swap_token(void);
 
 static inline int has_swap_token(struct mm_struct *mm)
 {
diff -puN mm/thrash.c~token-based-thrashing-control-inheritance mm/thrash.c
--- 25/mm/thrash.c~token-based-thrashing-control-inheritance	2004-08-01 03:42:04.194460792 -0700
+++ 25-akpm/mm/thrash.c	2004-08-01 03:53:13.590697096 -0700
@@ -93,8 +93,34 @@ void __put_swap_token(struct mm_struct *
 {
 	spin_lock(&swap_token_lock);
 	if (mm == swap_token_mm) {
-		swap_token_mm = &init_mm;
-		swap_token_check = jiffies;
+		struct task_struct *parent;
+
+		read_lock(&tasklist_lock);
+		parent = current->parent;
+		if (parent && parent->mm) {
+			parent->mm->swap_token_time = mm->swap_token_time;
+			parent->mm->recent_pagein = mm->recent_pagein;
+			swap_token_mm = parent->mm;
+			printk("%s gives token back to parent %s\n",
+					current->comm, parent->comm);
+		} else {
+			swap_token_mm = &init_mm;
+			swap_token_check = jiffies;
+		}
+		read_unlock(&tasklist_lock);
 	}
 	spin_unlock(&swap_token_lock);
 }
+
+void take_swap_token(void)
+{
+	struct task_struct *parent;
+
+	read_lock(&tasklist_lock);
+	parent = current->parent;
+	if (parent && current->mm && parent->mm == swap_token_mm) {
+		printk("%s takes token from %s\n", current->comm, parent->comm);
+		swap_token_mm = current->mm;
+	}
+	read_unlock(&tasklist_lock);
+}
_

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 292 bytes --]


> btw, in page_referenced_one():
> 
> +	if (mm != current->mm && has_swap_token(mm))
> +		referenced++;
> 
> what's the reason for the `mm != current->mm' test?
> 

so that you can steal pages from yourself if you really need to, say if
your own working set is bigger than ram.


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Fri, 30 Jul 2004, Rik van Riel wrote:

> I have run a very unscientific benchmark on my system to test
> the effectiveness of the patch, timing how a 230MB two-process
> qsbench run takes, with and without the token thrashing
> protection present.
> 
> normal 2.6.8-rc2:	6m45s
> 2.6.8-rc2 + token:	4m24s

OK, I've now also ran day-long kernel compilate tests,
3 times each with make -j 10, 20, 30, 40, 50 and 60 on
my dual pIII w/ 384 MB and a 180 MB named in the background.

For make -j 10 through make -j 50 the differences are in
the noise, basically giving the same result for each kernel.

However, for make -j 60 there's a dramatic difference between
a kernel with the token based swapout and a kernel without.

normal 2.6.8-rc2:	1h20m runtime / ~26% CPU use average
2.6.8-rc2 + token:	  42m runtime / ~52% CPU use average

Time to dig out a dedicated test machine at the office and
do some testing with (RE-)AIM7, I wonder if the max number
of users supported will grow...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Sun, 1 Aug 2004, Andrew Morton wrote:
> Rik van Riel <riel@redhat.com> wrote:
> >
> > The following experimental patch implements token based thrashing
> >  protection, 
> 
> Thanks for this - it is certainly needed.

I'm glad you like it ;)

> As you say, qsbench throughput is greatly increased (4x here).  But the old
> `make -j4 vmlinux' with mem=64m shows no benefit at all.

I tested increasing make loads on my system here.  The system
is a dual pIII with 384MB RAM and a 180MB named daemon in the
background.

With -j 10, 20, 30, 40 and 50 the patch didn't make much of a
difference at all.  However, with 'make -j 60' it sped up the
average compile time about a factor of 2, from 1:20 down to
40 minutes.  CPU consumption also went up from ~26% to over 50%.

> I figured it was the short-lived processes, so I added the below, which
> passes the token to the child across exec, and back to the parent on exit. 
> Although it appears to work correctly, it too make no difference.

I've got some ideas for potential improvement, too.  However,
I'd like to get the simplest code tested first ;)

> btw, in page_referenced_one():
> 
> +	if (mm != current->mm && has_swap_token(mm))
> +		referenced++;
> 
> what's the reason for the `mm != current->mm' test?

It's possible that the process that's currently holding
the token wants more memory than the system has available.

In that case it needs to be able to page part of itself
out of memory, otherwise the system will deadlock until
the moment where the token is handed off to the next
task...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Andrew Morton]

Rik van Riel <riel@redhat.com> wrote:
>
> On Fri, 30 Jul 2004, Rik van Riel wrote:
> 
>  > I have run a very unscientific benchmark on my system to test
>  > the effectiveness of the patch, timing how a 230MB two-process
>  > qsbench run takes, with and without the token thrashing
>  > protection present.
>  > 
>  > normal 2.6.8-rc2:	6m45s
>  > 2.6.8-rc2 + token:	4m24s
> 
>  OK, I've now also ran day-long kernel compilate tests,
>  3 times each with make -j 10, 20, 30, 40, 50 and 60 on
>  my dual pIII w/ 384 MB and a 180 MB named in the background.
> 
>  For make -j 10 through make -j 50 the differences are in
>  the noise, basically giving the same result for each kernel.
> 
>  However, for make -j 60 there's a dramatic difference between
>  a kernel with the token based swapout and a kernel without.
> 
>  normal 2.6.8-rc2:	1h20m runtime / ~26% CPU use average
>  2.6.8-rc2 + token:	  42m runtime / ~52% CPU use average

OK.  My test is usually around 50-60% CPU occupancy so we're not gaining in
the moderate swapping range.
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Sun, 1 Aug 2004, Andrew Morton wrote:
> Rik van Riel <riel@redhat.com> wrote:

> >  However, for make -j 60 there's a dramatic difference between
> >  a kernel with the token based swapout and a kernel without.
> > 
> >  normal 2.6.8-rc2:	1h20m runtime / ~26% CPU use average
> >  2.6.8-rc2 + token:	  42m runtime / ~52% CPU use average
> 
> OK.  My test is usually around 50-60% CPU occupancy so we're not gaining
> in the moderate swapping range.

I wonder if measuring minor faults too would help here ...

Btw, here's a slightly updated patch.  It's got the definition
for put_swap_token fixed for !CONFIG_SWAP and calls put_swap_token
before mmput.

I also cut the 4G/4G split line out of the mm/Makefile patch chunk,
so that should now apply better.

It doesn't have any functional changes I'm aware of.

--- linux-2.6.7/include/linux/swap.h.token	2004-07-30 13:22:17.000000000 -0400
+++ linux-2.6.7/include/linux/swap.h	2004-08-01 21:28:29.411274311 -0400
@@ -204,6 +204,27 @@
 extern struct page * lookup_swap_cache(swp_entry_t);
 extern struct page * read_swap_cache_async(swp_entry_t, struct vm_area_struct *vma,
 					   unsigned long addr);
+/* linux/mm/thrash.c */
+#ifdef CONFIG_SWAP
+extern struct mm_struct * swap_token_mm;
+extern void grab_swap_token(void);
+extern void __put_swap_token(struct mm_struct *);
+
+static inline int has_swap_token(struct mm_struct * mm)
+{
+	return (mm == swap_token_mm);
+}
+
+static inline void put_swap_token(struct mm_struct * mm)
+{
+	if (has_swap_token(mm))
+		__put_swap_token(mm);
+}
+#else /* CONFIG_SWAP */
+#define put_swap_token(x) do { } while(0)
+#define grab_swap_token  do { } while(0)
+#define has_swap_token 0
+#endif /* CONFIG_SWAP */
 
 /* linux/mm/swapfile.c */
 extern long total_swap_pages;
--- linux-2.6.7/include/linux/sched.h.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/include/linux/sched.h	2004-07-30 13:22:29.000000000 -0400
@@ -239,6 +239,10 @@
 	/* Architecture-specific MM context */
 	mm_context_t context;
 
+	/* Token based thrashing protection. */
+	unsigned long swap_token_time;
+	char recent_pagein;
+
 	/* coredumping support */
 	int core_waiters;
 	struct completion *core_startup_done, core_done;
--- linux-2.6.7/kernel/fork.c.token	2004-07-30 13:22:27.000000000 -0400
+++ linux-2.6.7/kernel/fork.c	2004-08-01 20:44:50.000000000 -0400
@@ -36,6 +36,7 @@
 #include <linux/mount.h>
 #include <linux/audit.h>
 #include <linux/rmap.h>
+#include <linux/swap.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -462,6 +463,7 @@
 		spin_unlock(&mmlist_lock);
 		exit_aio(mm);
 		exit_mmap(mm);
+		put_swap_token(mm);
 		mmdrop(mm);
 	}
 }
--- linux-2.6.7/mm/memory.c.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/mm/memory.c	2004-07-30 13:22:29.000000000 -0400
@@ -1433,6 +1433,7 @@
 		/* Had to read the page from swap area: Major fault */
 		ret = VM_FAULT_MAJOR;
 		inc_page_state(pgmajfault);
+		grab_swap_token();
 	}
 
 	mark_page_accessed(page);
--- linux-2.6.7/mm/filemap.c.token	2004-07-30 13:22:28.000000000 -0400
+++ linux-2.6.7/mm/filemap.c	2004-07-30 13:22:29.000000000 -0400
@@ -1195,6 +1195,7 @@
 	 * effect.
 	 */
 	error = page_cache_read(file, pgoff);
+	grab_swap_token();
 
 	/*
 	 * The page we want has now been added to the page cache.
--- /dev/null	2003-09-15 09:40:47.000000000 -0400
+++ linux-2.6.7/mm/thrash.c	2004-07-31 01:54:26.000000000 -0400
@@ -0,0 +1,100 @@
+/*
+ * mm/thrash.c
+ *
+ * Copyright (C) 2004, Red Hat, Inc.
+ * Copyright (C) 2004, Rik van Riel <riel@redhat.com>
+ * Released under the GPL, see the file COPYING for details.
+ *
+ * Simple token based thrashing protection, using the algorithm
+ * described in:  http://www.cs.wm.edu/~sjiang/token.pdf
+ */
+#include <linux/jiffies.h>
+#include <linux/mm.h>
+#include <linux/sched.h>
+#include <linux/swap.h>
+
+static spinlock_t swap_token_lock = SPIN_LOCK_UNLOCKED;
+static unsigned long swap_token_timeout;
+unsigned long swap_token_check;
+struct mm_struct * swap_token_mm = &init_mm;
+
+#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2)
+#define SWAP_TOKEN_TIMEOUT (HZ * 300)
+
+/*
+ * Take the token away if the process had no page faults
+ * in the last interval, or if it has held the token for
+ * too long.
+ */
+#define SWAP_TOKEN_ENOUGH_RSS 1
+#define SWAP_TOKEN_TIMED_OUT 2
+static int should_release_swap_token(struct mm_struct * mm)
+{
+	int ret = 0;
+	if (!mm->recent_pagein)
+		ret = SWAP_TOKEN_ENOUGH_RSS;
+	else if (time_after(jiffies, swap_token_timeout))
+		ret = SWAP_TOKEN_TIMED_OUT;
+	mm->recent_pagein = 0;
+	return ret;
+}
+
+/*
+ * Try to grab the swapout protection token.  We only try to
+ * grab it once every TOKEN_CHECK_INTERVAL, both to prevent
+ * SMP lock contention and to check that the process that held
+ * the token before is no longer thrashing.
+ */
+void grab_swap_token(void)
+{
+	struct mm_struct * mm;
+	int reason;
+
+	/* We have the token. Let others know we still need it. */
+	if (has_swap_token(current->mm)) {
+		current->mm->recent_pagein = 1;
+		return;
+	}
+
+	if (time_after(jiffies, swap_token_check)) {
+
+		/* Can't get swapout protection if we exceed our RSS limit. */
+		// if (current->mm->rss > current->mm->rlimit_rss)
+		//	return;
+
+		/* ... or if we recently held the token. */
+		if (time_before(jiffies, current->mm->swap_token_time))
+			return;
+
+		if (!spin_trylock(&swap_token_lock))
+			return;
+
+		swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
+
+		mm = swap_token_mm;
+		if ((reason = should_release_swap_token(mm))) {
+			unsigned long eligible = jiffies;
+			if (reason == SWAP_TOKEN_TIMED_OUT) {
+				eligible += SWAP_TOKEN_TIMEOUT;
+			}
+			mm->swap_token_time = eligible;
+			swap_token_timeout = jiffies + SWAP_TOKEN_TIMEOUT;
+			swap_token_mm = current->mm;
+			printk("Took swap token, pid %d (%s)\n",
+				 current->pid, current->comm);
+		}
+		spin_unlock(&swap_token_lock);
+	}
+	return;
+}
+
+/* Called on process exit. */
+void __put_swap_token(struct mm_struct * mm)
+{
+	spin_lock(&swap_token_lock);
+	if (likely(mm == swap_token_mm)) {
+		swap_token_mm = &init_mm;
+		swap_token_check = jiffies;
+	}
+	spin_unlock(&swap_token_lock);
+}
--- linux-2.6.7/mm/rmap.c.token	2004-07-30 13:22:24.000000000 -0400
+++ linux-2.6.7/mm/rmap.c	2004-08-01 21:15:29.861020222 -0400
@@ -230,6 +230,9 @@
 	if (ptep_clear_flush_young(vma, address, pte))
 		referenced++;
 
+	if (mm != current->mm && has_swap_token(mm))
+		referenced++;
+
 	(*mapcount)--;
 
 out_unmap:
--- linux-2.6.7/mm/Makefile.token	2004-07-30 13:22:27.000000000 -0400
+++ linux-2.6.7/mm/Makefile	2004-07-30 13:22:29.000000000 -0400
@@ -12,6 +12,6 @@
 			   readahead.o slab.o swap.o truncate.o vmscan.o \
 			   $(mmu-y)
 
-obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o
+obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 2158 bytes --]

Andrew Morton wrote:
> Rik van Riel <riel@redhat.com> wrote:
> 
>>On Fri, 30 Jul 2004, Rik van Riel wrote:
>>
>> > I have run a very unscientific benchmark on my system to test
>> > the effectiveness of the patch, timing how a 230MB two-process
>> > qsbench run takes, with and without the token thrashing
>> > protection present.
>> > 
>> > normal 2.6.8-rc2:	6m45s
>> > 2.6.8-rc2 + token:	4m24s
>>
>> OK, I've now also ran day-long kernel compilate tests,
>> 3 times each with make -j 10, 20, 30, 40, 50 and 60 on
>> my dual pIII w/ 384 MB and a 180 MB named in the background.
>>
>> For make -j 10 through make -j 50 the differences are in
>> the noise, basically giving the same result for each kernel.
>>
>> However, for make -j 60 there's a dramatic difference between
>> a kernel with the token based swapout and a kernel without.
>>
>> normal 2.6.8-rc2:	1h20m runtime / ~26% CPU use average
>> 2.6.8-rc2 + token:	  42m runtime / ~52% CPU use average
> 
> 
> OK.  My test is usually around 50-60% CPU occupancy so we're not gaining in
> the moderate swapping range.

We have some results that need interpreting with contest.
mem_load:
Kernel    [runs]	Time	CPU%	Loads	LCPU%	Ratio
2.6.8-rc2      4	78	146.2	94.5	4.7	1.30
2.6.8-rc2t     4	318	40.9	95.2	1.3	5.13

The "load" with mem_load is basically trying to allocate 110% of free 
ram, so the number of "loads" although similar is not a true indication 
of how much ram was handed out to mem_load. What is interesting is that 
since mem_load runs continuously and constantly asks for too much ram it 
seems to be receiving the token most frequently in preference to the cc 
processes which are short lived. I'd say it is quite hard to say 
convincingly that this is bad because the point of this patch is to 
prevent swap thrash.

It would get far more complicated to create a list of tasks trying to 
get the token and refuse to hand it back to the same task until it 
cycled through all the other tasks to prevent this... and I'm not even 
sure that would help since these are all short lived tasks... Any other 
thoughts?

To be honest I dont think this contest result is truly a bad thing...

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Mon, 2 Aug 2004, Con Kolivas wrote:

> We have some results that need interpreting with contest.
> mem_load:
> Kernel    [runs]	Time	CPU%	Loads	LCPU%	Ratio
> 2.6.8-rc2      4	78	146.2	94.5	4.7	1.30
> 2.6.8-rc2t     4	318	40.9	95.2	1.3	5.13
> 
> The "load" with mem_load is basically trying to allocate 110% of free 
> ram, so the number of "loads" although similar is not a true indication 
> of how much ram was handed out to mem_load. What is interesting is that 
> since mem_load runs continuously and constantly asks for too much ram it 
> seems to be receiving the token most frequently in preference to the cc 
> processes which are short lived. I'd say it is quite hard to say 
> convincingly that this is bad because the point of this patch is to 
> prevent swap thrash.

It may be worth trying with a shorter token timeout
time - maybe even keeping the long ineligibility ?

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 1087 bytes --]

Rik van Riel wrote:
> On Mon, 2 Aug 2004, Con Kolivas wrote:
> 
> 
>>We have some results that need interpreting with contest.
>>mem_load:
>>Kernel    [runs]	Time	CPU%	Loads	LCPU%	Ratio
>>2.6.8-rc2      4	78	146.2	94.5	4.7	1.30
>>2.6.8-rc2t     4	318	40.9	95.2	1.3	5.13
>>
>>The "load" with mem_load is basically trying to allocate 110% of free 
>>ram, so the number of "loads" although similar is not a true indication 
>>of how much ram was handed out to mem_load. What is interesting is that 
>>since mem_load runs continuously and constantly asks for too much ram it 
>>seems to be receiving the token most frequently in preference to the cc 
>>processes which are short lived. I'd say it is quite hard to say 
>>convincingly that this is bad because the point of this patch is to 
>>prevent swap thrash.
> 
> 
> It may be worth trying with a shorter token timeout
> time - maybe even keeping the long ineligibility ?

Give them a "refractory" bit which is set if they take the token? Next 
time they try to take the token unset the refractory bit instead of 
taking the token.

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] token based thrashing control

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 1408 bytes --]

Con Kolivas wrote:
> Rik van Riel wrote:
> 
>> On Mon, 2 Aug 2004, Con Kolivas wrote:
>>
>>
>>> We have some results that need interpreting with contest.
>>> mem_load:
>>> Kernel    [runs]    Time    CPU%    Loads    LCPU%    Ratio
>>> 2.6.8-rc2      4    78    146.2    94.5    4.7    1.30
>>> 2.6.8-rc2t     4    318    40.9    95.2    1.3    5.13
>>>
>>> The "load" with mem_load is basically trying to allocate 110% of free 
>>> ram, so the number of "loads" although similar is not a true 
>>> indication of how much ram was handed out to mem_load. What is 
>>> interesting is that since mem_load runs continuously and constantly 
>>> asks for too much ram it seems to be receiving the token most 
>>> frequently in preference to the cc processes which are short lived. 
>>> I'd say it is quite hard to say convincingly that this is bad because 
>>> the point of this patch is to prevent swap thrash.
>>
>>
>>
>> It may be worth trying with a shorter token timeout
>> time - maybe even keeping the long ineligibility ?
> 
> 
> Give them a "refractory" bit which is set if they take the token? Next 
> time they try to take the token unset the refractory bit instead of 
> taking the token.

Or take that concept even further; Give them an absolute refractory 
period where they cannot take the token again and a relative refractory 
bit which can only be reset after the refractory period is over.

Con

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 256 bytes --]

Re: [PATCH] token based thrashing control

[Song Jiang]

When there is memory competition among multiple processes,
Which process grabs the token first is important.
A process with its memory demand exceeding the total
ram gets the token first and finally has to give it up 
due to a time-out would have little performance gain from token,
It could also hurt others. Ideally we could make small processes
more easily grab the token first and enjoy the benifis from
token. That is, we want to protect those that are deserved to be
protected. Can we take the rss or other available memory demand
information for each process into the consideration of whether 
a token should be taken, or given up and how long a token is held.  
  Song

On Mon, 2 Aug 2004, Con Kolivas wrote:

> Con Kolivas wrote:
> > Rik van Riel wrote:
> > 
> >> On Mon, 2 Aug 2004, Con Kolivas wrote:
> >>
> >>
> >>> We have some results that need interpreting with contest.
> >>> mem_load:
> >>> Kernel    [runs]    Time    CPU%    Loads    LCPU%    Ratio
> >>> 2.6.8-rc2      4    78    146.2    94.5    4.7    1.30
> >>> 2.6.8-rc2t     4    318    40.9    95.2    1.3    5.13
> >>>
> >>> The "load" with mem_load is basically trying to allocate 110% of free 
> >>> ram, so the number of "loads" although similar is not a true 
> >>> indication of how much ram was handed out to mem_load. What is 
> >>> interesting is that since mem_load runs continuously and constantly 
> >>> asks for too much ram it seems to be receiving the token most 
> >>> frequently in preference to the cc processes which are short lived. 
> >>> I'd say it is quite hard to say convincingly that this is bad because 
> >>> the point of this patch is to prevent swap thrash.
> >>
> >>
> >>
> >> It may be worth trying with a shorter token timeout
> >> time - maybe even keeping the long ineligibility ?
> > 
> > 
> > Give them a "refractory" bit which is set if they take the token? Next 
> > time they try to take the token unset the refractory bit instead of 
> > taking the token.
> 
> Or take that concept even further; Give them an absolute refractory 
> period where they cannot take the token again and a relative refractory 
> bit which can only be reset after the refractory period is over.
> 
> Con
> 

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Mon, 2 Aug 2004, Song Jiang wrote:

> When there is memory competition among multiple processes,
> Which process grabs the token first is important.
> A process with its memory demand exceeding the total
> ram gets the token first and finally has to give it up 
> due to a time-out would have little performance gain from token,
> It could also hurt others. Ideally we could make small processes
> more easily grab the token first and enjoy the benifis from
> token. That is, we want to protect those that are deserved to be
> protected. Can we take the rss or other available memory demand
> information for each process into the consideration of whether 
> a token should be taken, or given up and how long a token is held.  

I like this idea.  I'm trying to think of a way to skew
the "lottery" so small processes get an advantage, but
the only thing I can come up with is as follows:

1) when a process tries to grab the token, it "registers"
   itself

2) a subsequent process can "register" itself to get the
   token, but only if it has a better score than the
   process that already has it

3) the score can be calculated based on a few factors,
   like (a) size of the process (b) time since it last
   had the token

4) a simple formula could be (time / size), giving big
   processes the token every once in a blue moon and
   letting small processes have the token all the time

5) the token would be grabbed in pretty much the same way
   we do currently, except the token can be handed to
   another process instead of the current process, if there
   is a better candidate registered - all the locking is there

6) since there is only one candidate, we won't have any
   queueing complexities and the algorithm should be just
   as cheap as it is currently

What do you think ?

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Song Jiang]

On Mon, 2 Aug 2004, Rik van Riel wrote:

> On Mon, 2 Aug 2004, Song Jiang wrote:
> 
> > When there is memory competition among multiple processes,
> > Which process grabs the token first is important.
> > A process with its memory demand exceeding the total
> > ram gets the token first and finally has to give it up 
> > due to a time-out would have little performance gain from token,
> > It could also hurt others. Ideally we could make small processes
> > more easily grab the token first and enjoy the benifis from
> > token. That is, we want to protect those that are deserved to be
> > protected. Can we take the rss or other available memory demand
> > information for each process into the consideration of whether 
> > a token should be taken, or given up and how long a token is held.  
> 
> I like this idea.  I'm trying to think of a way to skew
> the "lottery" so small processes get an advantage, but
> the only thing I can come up with is as follows:
> 
> 1) when a process tries to grab the token, it "registers"
>    itself
> 
> 2) a subsequent process can "register" itself to get the
>    token, but only if it has a better score than the
>    process that already has it b
> 
> 3) the score can be calculated based on a few factors,
>    like (a) size of the process (b) time since it last
>    had the token
> 
> 4) a simple formula could be (time / size), giving big
>    processes the token every once in a blue moon and
>    letting small processes have the token all the time

So the score of each registered process, with or without 
token, is calculated periodically. After each calculation,
a registered process with the highest score will take the token.
So a process gives up its token in these 4 cases:
(1) its page fault rate below a threshold (2) its score below
a threshold; (3) it holds a token for too long time (4) it is 
done. 

However, we have to avoid "token thrashing": a token is transfered
among processes too frequently, which could actually create unnecessarily
addtional page faults. So once a process gets the token, we can let
it hold the token for at least a minimal period of time. 
The intention behind the score = time/size is very sound, but
I am not sure how sensitive the performance is to the formula.
We may need to tune it carefully to make it valid.    

Which process will register itself? In my original design,
I allow a process with any major page faults to take the token.
However, I think now we should only allow the processes with their
page fault rate higher than a threshold to register themselves.
In this way we can limit the queue size.



> 
> 5) the token would be grabbed in pretty much the same way
>    we do currently, except the token can be handed to
>    another process instead of the current process, if there
>    is a better candidate registered - all the locking is there
> 
> 6) since there is only one candidate, we won't have any
>    queueing complexities and the algorithm should be just
>    as cheap as it is currently
> 

Do we need to periodically compare the scores of registered processes?
If yes, that would take queueing complexity.

> What do you think ?
> 
> 

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>

Re: [PATCH] token based thrashing control

[Rik van Riel]

On Wed, 4 Aug 2004, Song Jiang wrote:

> The intention behind the score = time/size is very sound, but
> I am not sure how sensitive the performance is to the formula.
> We may need to tune it carefully to make it valid.    

[snip]

> Do we need to periodically compare the scores of registered processes?
> If yes, that would take queueing complexity.

Hmmm, good points.  And my "queue of one" idea has the danger
of registering a process that doesn't want the token any more
by the time it's handed off...

Maybe we should use the "time/size" score to influence the
chance that a process gets to try and steal the token, in
effect just modifying the odds.

After all, thrashing should be a relatively rare situation,
so the code should be as low impact as possible...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

--
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-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>