[BENCHMARKS] Namesys VM patches improve kbuild

[BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Hi,

The two namesys patches help kbuild quite a lot here.
http://www.kerneltrap.org/~npiggin/vm/1/

The patches can be found at
http://thebsh.namesys.com/snapshots/LATEST/extra/

I don't have much to comment on the patches. They do include
some cleanup stuff which should be broken out.

I don't really understand the dont-rotate-active-list patch:
I don't see why we're losing LRU information because the pages
that go to the head of the active list get their referenced
bits cleared.

Anyway, comments?


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Andrew Morton]

Nick Piggin <piggin@cyberone.com.au> wrote:
>
> Hi,
> 
> The two namesys patches help kbuild quite a lot here.
> http://www.kerneltrap.org/~npiggin/vm/1/
> 
> The patches can be found at
> http://thebsh.namesys.com/snapshots/LATEST/extra/

I played with these back in July.  Had a few stability problems then but
yes, they did speed up some workloads a lot.


> I don't have much to comment on the patches. They do include
> some cleanup stuff which should be broken out.

Yup.  <dig, dig>  See below - it's six months old though.

> I don't really understand the dont-rotate-active-list patch:
> I don't see why we're losing LRU information because the pages
> that go to the head of the active list get their referenced
> bits cleared.

Yes, I do think that the "LRU" is a bit of a misnomer - it's very
approximate and only really suits simple workloads.  I suspect that once
things get hot and heavy the "lru" is only four-deep:
unreferenced/inactive, referenced/inactive, unreferenced/active and
referenced/active.

Can you test the patches separately, see what bits are actually helping?

Watch out for kswapd CPU utilisation as well - some of those changes have
the potential to increase it.




 include/linux/page-flags.h |    7 +++++++
 mm/page_alloc.c            |    1 +
 mm/truncate.c              |    2 ++
 mm/vmscan.c                |   10 ++++++++--
 5 files changed, 18 insertions(+), 2 deletions(-)

diff -puN include/linux/mm_inline.h~skip-writepage include/linux/mm_inline.h
diff -puN include/linux/page-flags.h~skip-writepage include/linux/page-flags.h
--- 25/include/linux/page-flags.h~skip-writepage	2003-07-09 02:58:48.000000000 -0700
+++ 25-akpm/include/linux/page-flags.h	2003-07-09 02:58:48.000000000 -0700
@@ -75,6 +75,7 @@
 #define PG_mappedtodisk		17	/* Has blocks allocated on-disk */
 #define PG_reclaim		18	/* To be reclaimed asap */
 #define PG_compound		19	/* Part of a compound page */
+#define PG_skipped		20	/* ->writepage() was skipped on this page */
 
 
 /*
@@ -267,6 +268,12 @@ extern void get_full_page_state(struct p
 #define SetPageCompound(page)	set_bit(PG_compound, &(page)->flags)
 #define ClearPageCompound(page)	clear_bit(PG_compound, &(page)->flags)
 
+#define PageSkipped(page)	test_bit(PG_skipped, &(page)->flags)
+#define SetPageSkipped(page)	set_bit(PG_skipped, &(page)->flags)
+#define TestSetPageSkipped(page)	test_and_set_bit(PG_skipped, &(page)->flags)
+#define ClearPageSkipped(page)		clear_bit(PG_skipped, &(page)->flags)
+#define TestClearPageSkipped(page)	test_and_clear_bit(PG_skipped, &(page)->flags)
+
 /*
  * The PageSwapCache predicate doesn't use a PG_flag at this time,
  * but it may again do so one day.
diff -puN mm/vmscan.c~skip-writepage mm/vmscan.c
--- 25/mm/vmscan.c~skip-writepage	2003-07-09 02:58:48.000000000 -0700
+++ 25-akpm/mm/vmscan.c	2003-07-09 03:05:43.000000000 -0700
@@ -328,6 +328,8 @@ shrink_list(struct list_head *page_list,
 		 * See swapfile.c:page_queue_congested().
 		 */
 		if (PageDirty(page)) {
+			if (!TestSetPageSkipped(page))
+				goto keep_locked;
 			if (!is_page_cache_freeable(page))
 				goto keep_locked;
 			if (!mapping)
@@ -351,6 +353,7 @@ shrink_list(struct list_head *page_list,
 				list_move(&page->list, &mapping->locked_pages);
 				spin_unlock(&mapping->page_lock);
 
+				ClearPageSkipped(page);
 				SetPageReclaim(page);
 				res = mapping->a_ops->writepage(page, &wbc);
 
@@ -533,10 +536,13 @@ shrink_cache(const int nr_pages, struct 
 			if (TestSetPageLRU(page))
 				BUG();
 			list_del(&page->lru);
-			if (PageActive(page))
+			if (PageActive(page)) {
+				if (PageSkipped(page))
+					ClearPageSkipped(page);
 				add_page_to_active_list(zone, page);
-			else
+			} else {
 				add_page_to_inactive_list(zone, page);
+			}
 			if (!pagevec_add(&pvec, page)) {
 				spin_unlock_irq(&zone->lru_lock);
 				__pagevec_release(&pvec);
diff -puN mm/truncate.c~skip-writepage mm/truncate.c
--- 25/mm/truncate.c~skip-writepage	2003-07-09 03:05:53.000000000 -0700
+++ 25-akpm/mm/truncate.c	2003-07-09 03:06:37.000000000 -0700
@@ -53,6 +53,7 @@ truncate_complete_page(struct address_sp
 	clear_page_dirty(page);
 	ClearPageUptodate(page);
 	ClearPageMappedToDisk(page);
+	ClearPageSkipped(page);
 	remove_from_page_cache(page);
 	page_cache_release(page);	/* pagecache ref */
 }
@@ -81,6 +82,7 @@ invalidate_complete_page(struct address_
 	__remove_from_page_cache(page);
 	spin_unlock(&mapping->page_lock);
 	ClearPageUptodate(page);
+	ClearPageSkipped(page);
 	page_cache_release(page);	/* pagecache ref */
 	return 1;
 }
diff -puN mm/page_alloc.c~skip-writepage mm/page_alloc.c
--- 25/mm/page_alloc.c~skip-writepage	2003-07-09 03:06:33.000000000 -0700
+++ 25-akpm/mm/page_alloc.c	2003-07-09 03:06:48.000000000 -0700
@@ -220,6 +220,7 @@ static inline void free_pages_check(cons
 			1 << PG_locked	|
 			1 << PG_active	|
 			1 << PG_reclaim	|
+			1 << PG_skipped	|
 			1 << PG_writeback )))
 		bad_page(function, page);
 	if (PageDirty(page))

_


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

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



Andrew Morton wrote:

>Nick Piggin <piggin@cyberone.com.au> wrote:
>
>>Hi,
>>
>>The two namesys patches help kbuild quite a lot here.
>>http://www.kerneltrap.org/~npiggin/vm/1/
>>
>>The patches can be found at
>>http://thebsh.namesys.com/snapshots/LATEST/extra/
>>
>
>I played with these back in July.  Had a few stability problems then but
>yes, they did speed up some workloads a lot.
>
>
>
>>I don't have much to comment on the patches. They do include
>>some cleanup stuff which should be broken out.
>>
>
>Yup.  <dig, dig>  See below - it's six months old though.
>
>
>>I don't really understand the dont-rotate-active-list patch:
>>I don't see why we're losing LRU information because the pages
>>that go to the head of the active list get their referenced
>>bits cleared.
>>
>
>Yes, I do think that the "LRU" is a bit of a misnomer - it's very
>approximate and only really suits simple workloads.  I suspect that once
>things get hot and heavy the "lru" is only four-deep:
>unreferenced/inactive, referenced/inactive, unreferenced/active and
>referenced/active.
>

Yep that was my thinking.

>
>Can you test the patches separately, see what bits are actually helping?
>


OK, I'll see how the second chance one alone does. By the way, what
do you think of this? Did I miss something non obvious?

Seems to make little difference on the benchmarks. Without the patch,
the active list would generally be attacked more aggressively.


[-- Attachment #2: vm-fix-shrink-zone.patch --]
[-- Type: text/plain, Size: 2582 bytes --]


Use the actual number of pages difference when trying to keep the inactive
list 1/2 the size of the active list (1/3 the size of all pages) instead of
a meaningless ratio.


 linux-2.6-npiggin/mm/vmscan.c |   37 +++++++++++++++++++------------------
 1 files changed, 19 insertions(+), 18 deletions(-)

diff -puN mm/vmscan.c~vm-fix-shrink-zone mm/vmscan.c
--- linux-2.6/mm/vmscan.c~vm-fix-shrink-zone	2004-01-22 14:47:25.000000000 +1100
+++ linux-2.6-npiggin/mm/vmscan.c	2004-01-22 16:25:04.000000000 +1100
@@ -745,38 +745,39 @@ static int
 shrink_zone(struct zone *zone, int max_scan, unsigned int gfp_mask,
 	const int nr_pages, int *nr_mapped, struct page_state *ps, int priority)
 {
-	unsigned long ratio;
+	unsigned long imbalance;
+	unsigned long nr_refill_inact;
 
 	/*
 	 * Try to keep the active list 2/3 of the size of the cache.  And
 	 * make sure that refill_inactive is given a decent number of pages.
 	 *
-	 * The "ratio+1" here is important.  With pagecache-intensive workloads
-	 * the inactive list is huge, and `ratio' evaluates to zero all the
-	 * time.  Which pins the active list memory.  So we add one to `ratio'
-	 * just to make sure that the kernel will slowly sift through the
-	 * active list.
+	 * Keeping imbalance > 0 is important.  With pagecache-intensive loads
+	 * the inactive list is huge, and imbalance evaluates to zero all the
+	 * time which would pin the active list memory.
 	 */
-	ratio = (unsigned long)nr_pages * zone->nr_active /
-				((zone->nr_inactive | 1) * 2);
-	atomic_add(ratio+1, &zone->refill_counter);
-	if (atomic_read(&zone->refill_counter) > SWAP_CLUSTER_MAX) {
-		int count;
-
+	imbalance = zone->nr_active - (zone->nr_inactive*2);
+	if (imbalance <= 0)
+		imbalance = 1;
+	else {
 		/*
 		 * Don't try to bring down too many pages in one attempt.
 		 * If this fails, the caller will increase `priority' and
 		 * we'll try again, with an increased chance of reclaiming
 		 * mapped memory.
 		 */
-		count = atomic_read(&zone->refill_counter);
-		if (count > SWAP_CLUSTER_MAX * 4)
-			count = SWAP_CLUSTER_MAX * 4;
+
+		imbalance >>= priority;
+	}
+
+	atomic_add(imbalance, &zone->refill_counter);
+	nr_refill_inact = atomic_read(&zone->refill_counter);
+	if (nr_refill_inact > SWAP_CLUSTER_MAX) {
 		atomic_set(&zone->refill_counter, 0);
-		refill_inactive_zone(zone, count, ps, priority);
+		refill_inactive_zone(zone, nr_refill_inact, ps, priority);
 	}
-	return shrink_cache(nr_pages, zone, gfp_mask,
-				max_scan, nr_mapped);
+
+	return shrink_cache(nr_pages, zone, gfp_mask, max_scan, nr_mapped);
 }
 
 /*

_

Re: [BENCHMARKS] Namesys VM patches improve kbuild

[Andrew Morton]

Nick Piggin <piggin@cyberone.com.au> wrote:
>
>  By the way, what
>  do you think of this? Did I miss something non obvious?
> 
>  Seems to make little difference on the benchmarks. Without the patch,
>  the active list would generally be attacked more aggressively.
> 
> 
> 
> [vm-fix-shrink-zone.patch  text/plain (2741 bytes)]
> 
>  Use the actual number of pages difference when trying to keep the inactive
>  list 1/2 the size of the active list (1/3 the size of all pages) instead of
>  a meaningless ratio.

Frankly, that `ratio' thing has always hurt my brain, so I left it as-is
from 2.4 because it never caused any obvious problems.

If we can put some clearer rationale behind what we're doing in there then
great.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Andrew Morton wrote:

>Nick Piggin <piggin@cyberone.com.au> wrote:
>
>> By the way, what
>> do you think of this? Did I miss something non obvious?
>>
>> Seems to make little difference on the benchmarks. Without the patch,
>> the active list would generally be attacked more aggressively.
>>
>>
>>
>>[vm-fix-shrink-zone.patch  text/plain (2741 bytes)]
>>
>> Use the actual number of pages difference when trying to keep the inactive
>> list 1/2 the size of the active list (1/3 the size of all pages) instead of
>> a meaningless ratio.
>>
>
>Frankly, that `ratio' thing has always hurt my brain, so I left it as-is
>from 2.4 because it never caused any obvious problems.
>
>If we can put some clearer rationale behind what we're doing in there then
>great.
>

Hmm, I actually did misread it a bit. The ratio is:
nr_pages * zone->nr_active / (zone->nr_inactive * 2)
Which is nr_pages if the active list is size we want.

So its not so bad as I thought. Scaling by nr_pages would
seem to couple it strongly with free pages though. My
patch makes it more independent. No I don't know if thats
good or not, it would obviously need a lot of testing.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[William Lee Irwin III]

On Thu, Jan 22, 2004 at 06:19:01PM +1100, Nick Piggin wrote:
> Hmm, I actually did misread it a bit. The ratio is:
> nr_pages * zone->nr_active / (zone->nr_inactive * 2)
> Which is nr_pages if the active list is size we want.
> So its not so bad as I thought. Scaling by nr_pages would
> seem to couple it strongly with free pages though. My
> patch makes it more independent. No I don't know if thats
> good or not, it would obviously need a lot of testing.

Could something symbolic be banged out to represent this "desired
(in)active_list size" to reduce confusion? You're not the only one
needing to review various calculations twice over or more at every
turn.


-- wli
--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Andrew Morton writes:
 > Nick Piggin <piggin@cyberone.com.au> wrote:
 > >
 > > Hi,
 > > 
 > > The two namesys patches help kbuild quite a lot here.
 > > http://www.kerneltrap.org/~npiggin/vm/1/
 > > 
 > > The patches can be found at
 > > http://thebsh.namesys.com/snapshots/LATEST/extra/
 > 
 > I played with these back in July.  Had a few stability problems then but
 > yes, they did speed up some workloads a lot.

Yes, there were glaring bugs at that time, and they were fixed. I am
using these patches all the time while stressing/testing reiser4.

 > 
 > 
 > > I don't have much to comment on the patches. They do include
 > > some cleanup stuff which should be broken out.
 > 

I think that shrink_list() is way too big, and too complex. All
pre-writepage checks and ->writepage() call handling itself fits nicely
to being separated into special function.

 > Yup.  <dig, dig>  See below - it's six months old though.
 > 
 > > I don't really understand the dont-rotate-active-list patch:
 > > I don't see why we're losing LRU information because the pages
 > > that go to the head of the active list get their referenced
 > > bits cleared.
 > 
 > Yes, I do think that the "LRU" is a bit of a misnomer - it's very
 > approximate and only really suits simple workloads.  I suspect that once
 > things get hot and heavy the "lru" is only four-deep:
 > unreferenced/inactive, referenced/inactive, unreferenced/active and
 > referenced/active.

Note that during referenced/inactive->unreferenced/active transition
page is moved to the _head_ of the active list.

refill_inactive_zone(), on the other hand, takes cold (not-referenced)
mapped pages from the tail of active list and throws them to the head
too. As a result:

1. time that it takes for a page to migrate from the head to the tail of
the active list varies, because irrelevant cold pages are added to the
head of it. Hence, page_referenced() check at the tail of active list
becomes worse estimation of the page hotness.

2. CPU usage increases, because until reclaim_mapped level of pressure
is reached, unreferenced mapped pages are scanned over and over again.

As an aside: our "lru" is four deep for mapped pages only:
refill_inactive_zone() doesn't take referenced bit on the file system
cache into account, so, actually, until recently when page_referenced()
check was added before calling ->writepage(), file system cache was
using plain FIFO.

Unfortunately simply adding check for TestClearPageReferenced(page) for
not-mapped pages in the refill_inactive_zone() doesn't help, because it
results in active list refusing to shrink at all under file system load.

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Nikita Danilov wrote:

>Andrew Morton writes:
> > Nick Piggin <piggin@cyberone.com.au> wrote:
> > >
> > > Hi,
> > > 
> > > The two namesys patches help kbuild quite a lot here.
> > > http://www.kerneltrap.org/~npiggin/vm/1/
> > > 
> > > The patches can be found at
> > > http://thebsh.namesys.com/snapshots/LATEST/extra/
> > 
> > I played with these back in July.  Had a few stability problems then but
> > yes, they did speed up some workloads a lot.
>
>Yes, there were glaring bugs at that time, and they were fixed. I am
>using these patches all the time while stressing/testing reiser4.
>
> > 
> > 
> > > I don't have much to comment on the patches. They do include
> > > some cleanup stuff which should be broken out.
> > 
>
>I think that shrink_list() is way too big, and too complex. All
>pre-writepage checks and ->writepage() call handling itself fits nicely
>to being separated into special function.
>
> > Yup.  <dig, dig>  See below - it's six months old though.
> > 
> > > I don't really understand the dont-rotate-active-list patch:
> > > I don't see why we're losing LRU information because the pages
> > > that go to the head of the active list get their referenced
> > > bits cleared.
> > 
> > Yes, I do think that the "LRU" is a bit of a misnomer - it's very
> > approximate and only really suits simple workloads.  I suspect that once
> > things get hot and heavy the "lru" is only four-deep:
> > unreferenced/inactive, referenced/inactive, unreferenced/active and
> > referenced/active.
>
>Note that during referenced/inactive->unreferenced/active transition
>page is moved to the _head_ of the active list.
>
>refill_inactive_zone(), on the other hand, takes cold (not-referenced)
>mapped pages from the tail of active list and throws them to the head
>too. As a result:
>
>1. time that it takes for a page to migrate from the head to the tail of
>the active list varies, because irrelevant cold pages are added to the
>head of it. Hence, page_referenced() check at the tail of active list
>becomes worse estimation of the page hotness.
>

But those cold mapped pages are basically ignored until the
reclaim_mapped threshold, however they do continue to have their
referenced bits cleared - hence page_referenced check should
become a better estimation when reclaim_mapped is reached, right?


>
>2. CPU usage increases, because until reclaim_mapped level of pressure
>is reached, unreferenced mapped pages are scanned over and over again.
>

Yes I agree here.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

William Lee Irwin III wrote:

>On Thu, Jan 22, 2004 at 06:19:01PM +1100, Nick Piggin wrote:
>
>>Hmm, I actually did misread it a bit. The ratio is:
>>nr_pages * zone->nr_active / (zone->nr_inactive * 2)
>>Which is nr_pages if the active list is size we want.
>>So its not so bad as I thought. Scaling by nr_pages would
>>seem to couple it strongly with free pages though. My
>>patch makes it more independent. No I don't know if thats
>>good or not, it would obviously need a lot of testing.
>>
>
>Could something symbolic be banged out to represent this "desired
>(in)active_list size" to reduce confusion? You're not the only one
>needing to review various calculations twice over or more at every
>turn.
>

That probably would help. I still don't like the ratio that much
but I guess it works. I'll see if I can get any improvements out
of my version.



--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Andrew Morton wrote:

>
>Yes, I do think that the "LRU" is a bit of a misnomer - it's very
>approximate and only really suits simple workloads.  I suspect that once
>things get hot and heavy the "lru" is only four-deep:
>unreferenced/inactive, referenced/inactive, unreferenced/active and
>referenced/active.
>
>Can you test the patches separately, see what bits are actually helping?
>

OK, sorry for the delay.
http://www.kerneltrap.org/~npiggin/vm/namesys.png

The LRU patch is the one that does it.

--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Nick Piggin writes:
 > 
 > 
 > Andrew Morton wrote:
 > 
 > >
 > >Yes, I do think that the "LRU" is a bit of a misnomer - it's very
 > >approximate and only really suits simple workloads.  I suspect that once
 > >things get hot and heavy the "lru" is only four-deep:
 > >unreferenced/inactive, referenced/inactive, unreferenced/active and
 > >referenced/active.
 > >
 > >Can you test the patches separately, see what bits are actually helping?
 > >
 > 
 > OK, sorry for the delay.
 > http://www.kerneltrap.org/~npiggin/vm/namesys.png
 > 
 > The LRU patch is the one that does it.
 > 

I presume (from the picture) that dont-rotate-active-list is meant, right?

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Nick Piggin writes:
 > 

[...]

 > 
 > But those cold mapped pages are basically ignored until the
 > reclaim_mapped threshold, however they do continue to have their
 > referenced bits cleared - hence page_referenced check should
 > become a better estimation when reclaim_mapped is reached, right?

Right.

By the way here lies another problem: refill_inactive_zone() never
removes referenced mapped page from the active list. Which allows for
the simple DoS:

----oomme.c-----------------------------------------------------------
#include <stdlib.h>
#include <unistd.h>

int
main(int argc, char **argv)
{
        unsigned long memuse;
        char *base;
        char *scan;
        int   shift;
        int   i;

        memuse = strtoul(argv[1], NULL, 0);
        shift = getpagesize();

        base = malloc(memuse);
        if (base == NULL) {
                perror("malloc");
                exit(1);
        }

        for (i = 0;; ++i) {
                for (scan = base; scan < base + memuse; scan += shift)
                        *scan += i;
                printf("%i\n", i);
        }
}
----oomme.c-----------------------------------------------------------

This program will re-reference allocated pages much faster than VM
scanner(s) will be able to analyze and clear their reference bits. In
effect it mlocks memory.

 > 
 > 

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Nikita Danilov wrote:

>Nick Piggin writes:
> > 
> > 
> > Andrew Morton wrote:
> > 
> > >
> > >Yes, I do think that the "LRU" is a bit of a misnomer - it's very
> > >approximate and only really suits simple workloads.  I suspect that once
> > >things get hot and heavy the "lru" is only four-deep:
> > >unreferenced/inactive, referenced/inactive, unreferenced/active and
> > >referenced/active.
> > >
> > >Can you test the patches separately, see what bits are actually helping?
> > >
> > 
> > OK, sorry for the delay.
> > http://www.kerneltrap.org/~npiggin/vm/namesys.png
> > 
> > The LRU patch is the one that does it.
> > 
>
>I presume (from the picture) that dont-rotate-active-list is meant, right?
>  
>

Thats right


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Nikita Danilov wrote:

>Nick Piggin writes:
> > 
>
>[...]
>
> > 
> > But those cold mapped pages are basically ignored until the
> > reclaim_mapped threshold, however they do continue to have their
> > referenced bits cleared - hence page_referenced check should
> > become a better estimation when reclaim_mapped is reached, right?
>
>Right.
>
>By the way here lies another problem: refill_inactive_zone() never
>removes referenced mapped page from the active list. Which allows for
>the simple DoS:
>

Yeah you are right. I actually have a test program that triggers
the DoS. I think it is also related to the fairness issues in 2.4
(some still exist in 2.6).

Basically the more memory a process has allocated, the faster they
are able to touch it, so the more they are given, etc etc.

But all the same, that should not be hurting low memory performance
if you are trying to do real work.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

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



Nikita Danilov wrote:

>Nick Piggin writes:
> > 
>
>[...]
>
> > 
> > But those cold mapped pages are basically ignored until the
> > reclaim_mapped threshold, however they do continue to have their
> > referenced bits cleared - hence page_referenced check should
> > become a better estimation when reclaim_mapped is reached, right?
>
>Right.
>


I still am a bit skeptical that the LRU lists are actually LRU,
however I'm running out of other explainations for your patch's
improvements :)

One ideas I had turns out to have little effect for kbuild, but
it might still be worth including?

When reclaim_mapped == 0 mapped referenced pages are treated
the same way as mapped unreferenced pages, and the referenced
info is thrown out. Fixed by not clearing referenced bits.


[-- Attachment #2: vm-info.patch --]
[-- Type: text/plain, Size: 923 bytes --]

 linux-2.6-npiggin/mm/vmscan.c |   10 ++++++----
 1 files changed, 6 insertions(+), 4 deletions(-)

diff -puN mm/vmscan.c~vm-info mm/vmscan.c
--- linux-2.6/mm/vmscan.c~vm-info	2004-01-24 00:50:15.000000000 +1100
+++ linux-2.6-npiggin/mm/vmscan.c	2004-01-24 01:58:56.000000000 +1100
@@ -656,6 +656,12 @@ refill_inactive_zone(struct zone *zone, 
 		page = list_entry(l_hold.prev, struct page, lru);
 		list_del(&page->lru);
 		if (page_mapped(page)) {
+
+			if (!reclaim_mapped) {
+				list_add(&page->lru, &l_active);
+				continue;
+			}
+
 			pte_chain_lock(page);
 			if (page_mapped(page) && page_referenced(page)) {
 				pte_chain_unlock(page);
@@ -663,10 +669,6 @@ refill_inactive_zone(struct zone *zone, 
 				continue;
 			}
 			pte_chain_unlock(page);
-			if (!reclaim_mapped) {
-				list_add(&page->lru, &l_active);
-				continue;
-			}
 		}
 		/*
 		 * FIXME: need to consider page_count(page) here if/when we

_

Re: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Nick Piggin writes:
 > 
 > 
 > Nikita Danilov wrote:
 > 
 > >Nick Piggin writes:
 > > > 
 > >
 > >[...]
 > >
 > > > 
 > > > But those cold mapped pages are basically ignored until the
 > > > reclaim_mapped threshold, however they do continue to have their
 > > > referenced bits cleared - hence page_referenced check should
 > > > become a better estimation when reclaim_mapped is reached, right?
 > >
 > >Right.
 > >
 > 
 > 
 > I still am a bit skeptical that the LRU lists are actually LRU,
 > however I'm running out of other explainations for your patch's
 > improvements :)

They are not LRU, it is impossible (and useless) to have LRU in the VM.

The problem that we have, and that dont-rotate-active-list tries to
address, is that two different LRU _approximations_ are maintained
within the same page queues. This patch tries (lazily) to separate pages
handled differently so that they don't interfere with each other.

 > 
 > One ideas I had turns out to have little effect for kbuild, but
 > it might still be worth including?
 > 
 > When reclaim_mapped == 0 mapped referenced pages are treated
 > the same way as mapped unreferenced pages, and the referenced
 > info is thrown out. Fixed by not clearing referenced bits.

I think that purpose of having active/inactive lists in the first place
is to tell hot pages from cold one. Hotness of page is estimated on the
basis of how frequently it has been accessed _recently_: if page was
accessed while migrating through the active list---it is hot. When the
memory pressure increases, the active list is scanned more aggressively
and the time that the page spends on it (which is the time it has to get
a reference) decreases, thus adjusting VM's notion of the hotness.

By not clearing the referenced bit, one loses the ability to tell recent
accesses from the old ones. As a result, all mapped pages that were ever
accessed from the bootup would appear as hot when reclaim_mapped is
reached.

But,

"The practice is the criterion of the truth" :)

 > 
 >  linux-2.6-npiggin/mm/vmscan.c |   10 ++++++----
 >  1 files changed, 6 insertions(+), 4 deletions(-)
 > 
 > diff -puN mm/vmscan.c~vm-info mm/vmscan.c
 > --- linux-2.6/mm/vmscan.c~vm-info	2004-01-24 00:50:15.000000000 +1100

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Nikita Danilov wrote:

>Nick Piggin writes:
> > 
> > 
> > Nikita Danilov wrote:
> > 
> > >Nick Piggin writes:
> > > > 
> > >
> > >[...]
> > >
> > > > 
> > > > But those cold mapped pages are basically ignored until the
> > > > reclaim_mapped threshold, however they do continue to have their
> > > > referenced bits cleared - hence page_referenced check should
> > > > become a better estimation when reclaim_mapped is reached, right?
> > >
> > >Right.
> > >
> > 
> > 
> > I still am a bit skeptical that the LRU lists are actually LRU,
> > however I'm running out of other explainations for your patch's
> > improvements :)
>
>They are not LRU, it is impossible (and useless) to have LRU in the VM.
>
>The problem that we have, and that dont-rotate-active-list tries to
>address, is that two different LRU _approximations_ are maintained
>within the same page queues. This patch tries (lazily) to separate pages
>handled differently so that they don't interfere with each other.
>

Yes, but why doesn't my small patch have the same effect?
It doesn't do it by nicely seperating mapped and non mapped
pages like yours, but it should do something similar: ignore
all mapped pages until the reclaim_mapped threshold.

>
>
> > 
> > One ideas I had turns out to have little effect for kbuild, but
> > it might still be worth including?
> > 
> > When reclaim_mapped == 0 mapped referenced pages are treated
> > the same way as mapped unreferenced pages, and the referenced
> > info is thrown out. Fixed by not clearing referenced bits.
>
>I think that purpose of having active/inactive lists in the first place
>is to tell hot pages from cold one. Hotness of page is estimated on the
>basis of how frequently it has been accessed _recently_: if page was
>accessed while migrating through the active list---it is hot. When the
>memory pressure increases, the active list is scanned more aggressively
>and the time that the page spends on it (which is the time it has to get
>a reference) decreases, thus adjusting VM's notion of the hotness.
>
>By not clearing the referenced bit, one loses the ability to tell recent
>accesses from the old ones. As a result, all mapped pages that were ever
>accessed from the bootup would appear as hot when reclaim_mapped is
>reached.
>

But by clearing the referenced bit when below the reclaim_mapped
threshold, you're throwing this information away.

Say you have 16 mapped pages on the active list, 8 referenced, 8 not.
You do a !reclaim_mapped scan. Your 16 pages are now in the same
order and none are referenced. You now do a reclaim_mapped scan and
reclaim 8 pages. 4 of them were the referenced ones, 4 were not.

With my change, you would reclaim all 8 non referenced pages.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Nick Piggin writes:
 > 

[...]

 > 
 > But by clearing the referenced bit when below the reclaim_mapped
 > threshold, you're throwing this information away.
 > 
 > Say you have 16 mapped pages on the active list, 8 referenced, 8 not.
 > You do a !reclaim_mapped scan. Your 16 pages are now in the same
 > order and none are referenced. You now do a reclaim_mapped scan and
 > reclaim 8 pages. 4 of them were the referenced ones, 4 were not.
 > 
 > With my change, you would reclaim all 8 non referenced pages.

Which is wrong, because none of them was referenced _recently_. These
pages are cold, according to the VM's notion of hotness. (Long time
probably has passed between !reclaim_mapped and reclaim_mapped scans in
your example.)

It seems correct to make deactivation decision on the basic of recent
accesses to the page rather than by checking whether page was ever
accessed.

 > 

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Nikita Danilov wrote:

>Nick Piggin writes:
> > 
>
>[...]
>
> > 
> > But by clearing the referenced bit when below the reclaim_mapped
> > threshold, you're throwing this information away.
> > 
> > Say you have 16 mapped pages on the active list, 8 referenced, 8 not.
> > You do a !reclaim_mapped scan. Your 16 pages are now in the same
> > order and none are referenced. You now do a reclaim_mapped scan and
> > reclaim 8 pages. 4 of them were the referenced ones, 4 were not.
> > 
> > With my change, you would reclaim all 8 non referenced pages.
>
>Which is wrong, because none of them was referenced _recently_. These
>pages are cold, according to the VM's notion of hotness. (Long time
>probably has passed between !reclaim_mapped and reclaim_mapped scans in
>your example.)
>

Well you'd have to admit the referenced pages are hotter, but
I guess I can't argue with the numbers: it must not be very
significant.

I just wonder why your patch makes such an improvement. You're
basically putting mapped pages to one side until reclaim_mapped,
which is similar to what my patch does, right?


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Nick Piggin writes:
 > 
 > 
 > Nikita Danilov wrote:
 > 
 > >Nick Piggin writes:
 > > > 
 > >
 > >[...]
 > >
 > > > 
 > > > But by clearing the referenced bit when below the reclaim_mapped
 > > > threshold, you're throwing this information away.
 > > > 
 > > > Say you have 16 mapped pages on the active list, 8 referenced, 8 not.
 > > > You do a !reclaim_mapped scan. Your 16 pages are now in the same
 > > > order and none are referenced. You now do a reclaim_mapped scan and
 > > > reclaim 8 pages. 4 of them were the referenced ones, 4 were not.
 > > > 
 > > > With my change, you would reclaim all 8 non referenced pages.
 > >
 > >Which is wrong, because none of them was referenced _recently_. These
 > >pages are cold, according to the VM's notion of hotness. (Long time
 > >probably has passed between !reclaim_mapped and reclaim_mapped scans in
 > >your example.)
 > >
 > 
 > Well you'd have to admit the referenced pages are hotter, but
 > I guess I can't argue with the numbers: it must not be very
 > significant.
 > 
 > I just wonder why your patch makes such an improvement. You're
 > basically putting mapped pages to one side until reclaim_mapped,
 > which is similar to what my patch does, right?

Difference is that dont-rotate-active-list leaves mapped pages behind
the scanning point, in stead of moving them to the head of the active
list. Moving these pages to the head of the active list destroys LRU
approximation for the file system cache (see mark_page_accessed()): in
LRU, a page is moved to the head of the queue when accessed and later
migrates through the queue because other _hotter_ pages are added to the
head of the queue. But in the un-patched VM a page migrates through the
queue, because:

   (1) other hotter pages are added to the head of the queue.

   (2) other possibly _colder_ mapped pages are added to the head of the
       queue.

(2) is obviously bad for the LRU approximation, and
dont-rotate-active-list patch gets rid of it.

 > 
 > 

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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nick Piggin]

Hi Nikita,

Just having a look at your patch. I think maybe this array
should be in a seperate cacheline per node?

+/* dummy pages used to scan active lists */
+static struct page scan_pages[MAX_NUMNODES][MAX_NR_ZONES];
+

 

--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Andrew Morton]

Nick Piggin <piggin@cyberone.com.au> wrote:
>
> Hi Nikita,
> 
> Just having a look at your patch. I think maybe this array
> should be in a seperate cacheline per node?
> 
> +/* dummy pages used to scan active lists */
> +static struct page scan_pages[MAX_NUMNODES][MAX_NR_ZONES];
> +

You really want it a member of `struct zone', don't you?

That'll cause include dependency hell, so maybe a page* in struct zone.


--
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: [BENCHMARKS] Namesys VM patches improve kbuild

[Nikita Danilov]

Andrew Morton writes:
 > Nick Piggin <piggin@cyberone.com.au> wrote:
 > >
 > > Hi Nikita,
 > > 
 > > Just having a look at your patch. I think maybe this array
 > > should be in a seperate cacheline per node?
 > > 
 > > +/* dummy pages used to scan active lists */
 > > +static struct page scan_pages[MAX_NUMNODES][MAX_NR_ZONES];
 > > +
 > 
 > You really want it a member of `struct zone', don't you?
 > 
 > That'll cause include dependency hell, so maybe a page* in struct zone.

I don't quite understand:

struct zone {

    ....

	/*
	 * dummy page used as place holder during scanning of
	 * active_list in refill_inactive_zone()
	 */
	struct page *scan_page;

    ....

};

is already here. Array scan_pages[][] contains struct pages to which
zone->scan_page's point to. Yes, I didn't embed struct page into struct
zone exactly due to dependencies problems.

 > 
 > 

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>