* KSWAPD Algorithm - 100% CPU
@ 2008-12-03 7:04 wassim dagash
2008-12-03 7:20 ` KAMEZAWA Hiroyuki
2008-12-03 9:20 ` KOSAKI Motohiro
0 siblings, 2 replies; 5+ messages in thread
From: wassim dagash @ 2008-12-03 7:04 UTC (permalink / raw)
To: linux-kernel
Hi All,
Description:
I countered a weird problem with kswapd:
it runs in some infinite loop trying to swap until order 10 of zone
highmem is OK, While zone higmem (as I understand) has nothing to do
with contiguous memory (cause there is no 1-1 mapping) which means
kswapd will continue to try to balance order 10 of zone highmem
forever (or until someone release a very large chunk of highmem).
Can anyone please explain me the algorithm of kswapd and why it tries
to balance order 10 of zone higmem ?
Details:
I build an instrumented kernel with debug messages in
"zone_watermark_ok" function, and from the code and debug messages I
see that "zone_watermark_ok" returns 0 when kswapd invokes it (through
balance_pgdat) in order to decide if zone highmem is balanced or not,
which lead in some configurations to infinite loop of kswapd ( if no
large chunks of highmem released) . I added a condition to
"balance_pgdat" so it doesn't try to balance order higher than 1 in
zone highmem and this conditon solved the problem, what are the risks
with such solution? isn't it a bug that kswapd is looking for
continuous memory in zone highmem ( as I understand there is no 1-1
mapping in zone highmem which is meaningless in kswapd)?
NOTE: I WANT TO BE CC'ed TO THE THREAD!
Regards,
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: KSWAPD Algorithm - 100% CPU
2008-12-03 7:04 KSWAPD Algorithm - 100% CPU wassim dagash
@ 2008-12-03 7:20 ` KAMEZAWA Hiroyuki
2008-12-03 9:20 ` KOSAKI Motohiro
1 sibling, 0 replies; 5+ messages in thread
From: KAMEZAWA Hiroyuki @ 2008-12-03 7:20 UTC (permalink / raw)
To: wassim dagash; +Cc: linux-kernel
On Wed, 3 Dec 2008 09:04:49 +0200
"wassim dagash" <wassim.dagash@gmail.com> wrote:
> Hi All,
> Description:
> I countered a weird problem with kswapd:
> it runs in some infinite loop trying to swap until order 10 of zone
> highmem is OK, While zone higmem (as I understand) has nothing to do
> with contiguous memory (cause there is no 1-1 mapping) which means
> kswapd will continue to try to balance order 10 of zone highmem
> forever (or until someone release a very large chunk of highmem).
> Can anyone please explain me the algorithm of kswapd and why it tries
> to balance order 10 of zone higmem ?
>
At first, what version of the kernel ?
-Kame
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: KSWAPD Algorithm - 100% CPU
2008-12-03 7:04 KSWAPD Algorithm - 100% CPU wassim dagash
2008-12-03 7:20 ` KAMEZAWA Hiroyuki
@ 2008-12-03 9:20 ` KOSAKI Motohiro
2008-12-04 14:02 ` Nick Piggin
1 sibling, 1 reply; 5+ messages in thread
From: KOSAKI Motohiro @ 2008-12-03 9:20 UTC (permalink / raw)
To: wassim dagash; +Cc: kosaki.motohiro, linux-kernel, Andrew Morton, Nick Piggin
(CC to Nick Piggin and Andrew Morton.)
Hi
At first, could you post reproduce program?
if nobody can reproduce, fixing is difficult.
obiously, we need the patch validate by reproduce program.
> Hi All,
> Description:
> I countered a weird problem with kswapd:
> it runs in some infinite loop trying to swap until order 10 of zone
> highmem is OK, While zone higmem (as I understand) has nothing to do
> with contiguous memory (cause there is no 1-1 mapping) which means
> kswapd will continue to try to balance order 10 of zone highmem
> forever (or until someone release a very large chunk of highmem).
> Can anyone please explain me the algorithm of kswapd and why it tries
> to balance order 10 of zone higmem ?
At second, I'd like to talk about kswapd background and algorithm.
1st kswapd balancing introduced following commit.
--------------------------------------------------------
commit 6cbd719443491404f63f9ff79ead9eba256511ee
Author: akpm <akpm>
Date: Fri Mar 12 16:24:40 2004 +0000
[PATCH] kswapd: fix lumpy page reclaim
As kswapd is now scanning zones in the highmem->normal->dma direction it can
get into competition with the page allocator: kswapd keep on trying to free
pages from highmem, then kswapd moves onto lowmem. By the time kswapd has
done proportional scanning in lowmem, someone has come in and allocated a few
pages from highmem. So kswapd goes back and frees some highmem, then some
lowmem again. But nobody has allocated any lowmem yet. So we keep on and on
scanning lowmem in response to highmem page allocations.
With a simple `dd' on a 1G box we get:
r b swpd free buff cache si so bi bo in cs us sy wa id
0 3 0 59340 4628 922348 0 0 4 28188 1072 808 0 10 46 44
0 3 0 29932 4660 951760 0 0 0 30752 1078 441 1 6 30 64
0 3 0 57568 4556 924052 0 0 0 30748 1075 478 0 8 43 49
0 3 0 29664 4584 952176 0 0 0 30752 1075 472 0 6 34 60
0 3 0 5304 4620 976280 0 0 4 40484 1073 456 1 7 52 41
0 3 0 104856 4508 877112 0 0 0 18452 1074 97 0 7 67 26
0 3 0 70768 4540 911488 0 0 0 35876 1078 746 0 7 34 59
1 2 0 42544 4568 939680 0 0 0 21524 1073 556 0 5 43 51
0 3 0 5520 4608 976428 0 0 4 37924 1076 836 0 7 41 51
0 2 0 4848 4632 976812 0 0 32 12308 1092 94 0 1 33 66
Simple fix: go back to scanning the zones in the dma->normal->highmem
direction so we meet the page allocator in the middle somewhere.
r b swpd free buff cache si so bi bo in cs us sy wa id
1 3 0 5152 3468 976548 0 0 4 37924 1071 650 0 8 64 28
1 2 0 4888 3496 976588 0 0 0 23576 1075 726 0 6 66 27
0 3 0 5336 3532 976348 0 0 0 31264 1072 708 0 8 60 32
0 3 0 6168 3560 975504 0 0 0 40992 1072 683 0 6 63 31
0 3 0 4560 3580 976844 0 0 0 18448 1073 233 0 4 59 37
0 3 0 5840 3624 975712 0 0 4 26660 1072 800 1 8 46 45
0 3 0 4816 3648 976640 0 0 0 40992 1073 526 0 6 47 47
0 3 0 5456 3672 976072 0 0 0 19984 1070 320 0 5 60 35
BKrev: 4051e448CiuO4KIoyJ6pqIVrkhuNnw
--------------------------------------------------------
At that time, kswapd didn't check memory contenious at all.
it has following code.
------------------------------------------------------------
+ if (zone->free_pages <= zone->pages_high) {
+ end_zone = i;
+ goto scan;
+ }
-----------------------------------------------------------------
2nd commit improve memory coutenious check.
--------------------------------------------------------
commit e0e1723229b6f96922d10bb932f94d899132b462
Author: nickpiggin <nickpiggin>
Date: Tue Jan 4 04:14:42 2005 +0000
[PATCH] mm: teach kswapd about higher order areas
Teach kswapd to free memory on behalf of higher order allocators. This
could be important for higher order atomic allocations because they
otherwise have no means to free the memory themselves.
Signed-off-by: Nick Piggin <nickpiggin@yahoo.com.au>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
BKrev: 41da1832E5flzqtNXq5m70WxihpcMw
--------------------------------------------------------
At that time, kswapd has following code.
--------------------------------------------------------
- if (zone->free_pages <= zone->pages_high) {
+ if (!zone_watermark_ok(zone, order,
+ zone->pages_high, 0, 0, 0)) {
end_zone = i;
goto scan;
}
--------------------------------------------------------
The problem is, alloc_pages(GFP_KERNEL, 10) need to contenious order-10 memory.
but doesn't need to highmem couteniously.
However alloc_pages() pass to order==10 information.
but doesn't pass to highmem coutinuous is unnecessary.
Oops, that is bug, I think.
So, I'd like to fix this bug.
However, I check my guessing is right or not at first.
please reproduce program.
> Details:
> I build an instrumented kernel with debug messages in
> "zone_watermark_ok" function, and from the code and debug messages I
> see that "zone_watermark_ok" returns 0 when kswapd invokes it (through
> balance_pgdat) in order to decide if zone highmem is balanced or not,
> which lead in some configurations to infinite loop of kswapd ( if no
> large chunks of highmem released) . I added a condition to
> "balance_pgdat" so it doesn't try to balance order higher than 1 in
> zone highmem and this conditon solved the problem, what are the risks
> with such solution? isn't it a bug that kswapd is looking for
> continuous memory in zone highmem ( as I understand there is no 1-1
> mapping in zone highmem which is meaningless in kswapd)?
simple removing seems no good.
because hugepage on highmem need to highmem coutenious.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: KSWAPD Algorithm - 100% CPU
2008-12-03 9:20 ` KOSAKI Motohiro
@ 2008-12-04 14:02 ` Nick Piggin
2008-12-05 2:53 ` KOSAKI Motohiro
0 siblings, 1 reply; 5+ messages in thread
From: Nick Piggin @ 2008-12-04 14:02 UTC (permalink / raw)
To: KOSAKI Motohiro; +Cc: wassim dagash, linux-kernel, Andrew Morton
On Wed, Dec 03, 2008 at 06:20:46PM +0900, KOSAKI Motohiro wrote:
> (CC to Nick Piggin and Andrew Morton.)
>
> Hi
>
> At first, could you post reproduce program?
> if nobody can reproduce, fixing is difficult.
>
> obiously, we need the patch validate by reproduce program.
>
>
> > Hi All,
> > Description:
> > I countered a weird problem with kswapd:
> > it runs in some infinite loop trying to swap until order 10 of zone
> > highmem is OK, While zone higmem (as I understand) has nothing to do
> > with contiguous memory (cause there is no 1-1 mapping) which means
> > kswapd will continue to try to balance order 10 of zone highmem
> > forever (or until someone release a very large chunk of highmem).
> > Can anyone please explain me the algorithm of kswapd and why it tries
> > to balance order 10 of zone higmem ?
>
> At second, I'd like to talk about kswapd background and algorithm.
>
> 1st kswapd balancing introduced following commit.
>
> --------------------------------------------------------
> commit 6cbd719443491404f63f9ff79ead9eba256511ee
> Author: akpm <akpm>
> Date: Fri Mar 12 16:24:40 2004 +0000
>
> [PATCH] kswapd: fix lumpy page reclaim
>
> As kswapd is now scanning zones in the highmem->normal->dma direction it can
> get into competition with the page allocator: kswapd keep on trying to free
> pages from highmem, then kswapd moves onto lowmem. By the time kswapd has
> done proportional scanning in lowmem, someone has come in and allocated a few
> pages from highmem. So kswapd goes back and frees some highmem, then some
> lowmem again. But nobody has allocated any lowmem yet. So we keep on and on
> scanning lowmem in response to highmem page allocations.
>
> With a simple `dd' on a 1G box we get:
>
> r b swpd free buff cache si so bi bo in cs us sy wa id
> 0 3 0 59340 4628 922348 0 0 4 28188 1072 808 0 10 46 44
> 0 3 0 29932 4660 951760 0 0 0 30752 1078 441 1 6 30 64
> 0 3 0 57568 4556 924052 0 0 0 30748 1075 478 0 8 43 49
> 0 3 0 29664 4584 952176 0 0 0 30752 1075 472 0 6 34 60
> 0 3 0 5304 4620 976280 0 0 4 40484 1073 456 1 7 52 41
> 0 3 0 104856 4508 877112 0 0 0 18452 1074 97 0 7 67 26
> 0 3 0 70768 4540 911488 0 0 0 35876 1078 746 0 7 34 59
> 1 2 0 42544 4568 939680 0 0 0 21524 1073 556 0 5 43 51
> 0 3 0 5520 4608 976428 0 0 4 37924 1076 836 0 7 41 51
> 0 2 0 4848 4632 976812 0 0 32 12308 1092 94 0 1 33 66
>
> Simple fix: go back to scanning the zones in the dma->normal->highmem
> direction so we meet the page allocator in the middle somewhere.
>
> r b swpd free buff cache si so bi bo in cs us sy wa id
> 1 3 0 5152 3468 976548 0 0 4 37924 1071 650 0 8 64 28
> 1 2 0 4888 3496 976588 0 0 0 23576 1075 726 0 6 66 27
> 0 3 0 5336 3532 976348 0 0 0 31264 1072 708 0 8 60 32
> 0 3 0 6168 3560 975504 0 0 0 40992 1072 683 0 6 63 31
> 0 3 0 4560 3580 976844 0 0 0 18448 1073 233 0 4 59 37
> 0 3 0 5840 3624 975712 0 0 4 26660 1072 800 1 8 46 45
> 0 3 0 4816 3648 976640 0 0 0 40992 1073 526 0 6 47 47
> 0 3 0 5456 3672 976072 0 0 0 19984 1070 320 0 5 60 35
>
> BKrev: 4051e448CiuO4KIoyJ6pqIVrkhuNnw
> --------------------------------------------------------
>
> At that time, kswapd didn't check memory contenious at all.
> it has following code.
>
> ------------------------------------------------------------
> + if (zone->free_pages <= zone->pages_high) {
> + end_zone = i;
> + goto scan;
> + }
> -----------------------------------------------------------------
>
>
>
> 2nd commit improve memory coutenious check.
>
> --------------------------------------------------------
> commit e0e1723229b6f96922d10bb932f94d899132b462
> Author: nickpiggin <nickpiggin>
> Date: Tue Jan 4 04:14:42 2005 +0000
>
> [PATCH] mm: teach kswapd about higher order areas
>
> Teach kswapd to free memory on behalf of higher order allocators. This
> could be important for higher order atomic allocations because they
> otherwise have no means to free the memory themselves.
>
> Signed-off-by: Nick Piggin <nickpiggin@yahoo.com.au>
> Signed-off-by: Andrew Morton <akpm@osdl.org>
> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
>
> BKrev: 41da1832E5flzqtNXq5m70WxihpcMw
> --------------------------------------------------------
>
> At that time, kswapd has following code.
>
> --------------------------------------------------------
> - if (zone->free_pages <= zone->pages_high) {
> + if (!zone_watermark_ok(zone, order,
> + zone->pages_high, 0, 0, 0)) {
> end_zone = i;
> goto scan;
> }
> --------------------------------------------------------
>
> The problem is, alloc_pages(GFP_KERNEL, 10) need to contenious order-10 memory.
> but doesn't need to highmem couteniously.
>
> However alloc_pages() pass to order==10 information.
> but doesn't pass to highmem coutinuous is unnecessary.
>
> Oops, that is bug, I think.
>
>
> So, I'd like to fix this bug.
> However, I check my guessing is right or not at first.
> please reproduce program.
>
>
>
> > Details:
> > I build an instrumented kernel with debug messages in
> > "zone_watermark_ok" function, and from the code and debug messages I
> > see that "zone_watermark_ok" returns 0 when kswapd invokes it (through
> > balance_pgdat) in order to decide if zone highmem is balanced or not,
> > which lead in some configurations to infinite loop of kswapd ( if no
> > large chunks of highmem released) . I added a condition to
> > "balance_pgdat" so it doesn't try to balance order higher than 1 in
> > zone highmem and this conditon solved the problem, what are the risks
> > with such solution? isn't it a bug that kswapd is looking for
> > continuous memory in zone highmem ( as I understand there is no 1-1
> > mapping in zone highmem which is meaningless in kswapd)?
>
>
> simple removing seems no good.
> because hugepage on highmem need to highmem coutenious.
kswapd_max_order check and reset should probably go inside
balance_pgdat:loop_again loop.
It is possible we could have a kswapd_max_order[MAX_NR_ZONES] or
something, but I don't know if the complexity would be worth while
given that huge order allocations aren't too common, and resetting
kswapd_max_order inside the loop should be a reasonable fix.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: KSWAPD Algorithm - 100% CPU
2008-12-04 14:02 ` Nick Piggin
@ 2008-12-05 2:53 ` KOSAKI Motohiro
0 siblings, 0 replies; 5+ messages in thread
From: KOSAKI Motohiro @ 2008-12-05 2:53 UTC (permalink / raw)
To: Nick Piggin, wassim dagash; +Cc: kosaki.motohiro, linux-kernel, Andrew Morton
> kswapd_max_order check and reset should probably go inside
> balance_pgdat:loop_again loop.
>
> It is possible we could have a kswapd_max_order[MAX_NR_ZONES] or
> something, but I don't know if the complexity would be worth while
> given that huge order allocations aren't too common, and resetting
> kswapd_max_order inside the loop should be a reasonable fix.
It seems excellent.
wassim, Could you please test this patch?
==
From: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
Subject: [PATCH] kswapd: add infinite loop stopper
Wassim Dagash reported following kswapd infinite loop problem.
kswapd runs in some infinite loop trying to swap until order 10 of zone
highmem is OK, While zone higmem (as I understand) has nothing to do
with contiguous memory (cause there is no 1-1 mapping) which means
kswapd will continue to try to balance order 10 of zone highmem
forever (or until someone release a very large chunk of highmem).
He proposed remove contenious checking on highmem at all.
However hugepage on highmem need contenious highmem page.
To add infinite loop stopper is simple and good.
Reported-by: wassim dagash <wassim.dagash@gmail.com>
Signed-off-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
---
mm/vmscan.c | 10 ++++++++++
1 file changed, 10 insertions(+)
Index: b/mm/vmscan.c
===================================================================
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -1921,6 +1921,16 @@ out:
try_to_freeze();
+ /*
+ When highmem is very fragmented,
+ alloc_pages(GFP_KERNEL, very-high-order) can cause
+ infinite loop because zone_watermark_ok(highmem) failed.
+ However, (alloc_pages(GFP_KERNEL..) indicate highmem memory
+ continuousness isn't necessary.
+ Therefore 2nd loop or after stop contenious check.
+ */
+ order = sc->order = 0;
+
goto loop_again;
}
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2008-12-05 2:53 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-12-03 7:04 KSWAPD Algorithm - 100% CPU wassim dagash
2008-12-03 7:20 ` KAMEZAWA Hiroyuki
2008-12-03 9:20 ` KOSAKI Motohiro
2008-12-04 14:02 ` Nick Piggin
2008-12-05 2:53 ` KOSAKI Motohiro
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®