[PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
original scan targets introduces extra 40 bytes on the stack. This patch
is able to avoid this situation and the call to memcpy(). At the same time,
it does not change the relative design idea.

ratio = original_nr_file / original_nr_anon;

If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
 x = nr_file - ratio * nr_anon;

if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
 x = nr_anon - nr_file / ratio;

Signed-off-by: Chen Yucong <slaoub@gmail.com>
---
 mm/vmscan.c |   28 +++++++++-------------------
 1 file changed, 9 insertions(+), 19 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index a8ffe4e..daaf89c 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -2057,8 +2057,7 @@ out:
 static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
 {
 	unsigned long nr[NR_LRU_LISTS];
-	unsigned long targets[NR_LRU_LISTS];
-	unsigned long nr_to_scan;
+	unsigned long nr_to_scan, ratio;
 	enum lru_list lru;
 	unsigned long nr_reclaimed = 0;
 	unsigned long nr_to_reclaim = sc->nr_to_reclaim;
@@ -2067,8 +2066,8 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
 
 	get_scan_count(lruvec, sc, nr);
 
-	/* Record the original scan target for proportional adjustments later */
-	memcpy(targets, nr, sizeof(nr));
+	ratio = (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE] + 1) /
+			(nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON] + 1);
 
 	/*
 	 * Global reclaiming within direct reclaim at DEF_PRIORITY is a normal
@@ -2088,7 +2087,6 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
 	while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
 					nr[LRU_INACTIVE_FILE]) {
 		unsigned long nr_anon, nr_file, percentage;
-		unsigned long nr_scanned;
 
 		for_each_evictable_lru(lru) {
 			if (nr[lru]) {
@@ -2123,15 +2121,13 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
 			break;
 
 		if (nr_file > nr_anon) {
-			unsigned long scan_target = targets[LRU_INACTIVE_ANON] +
-						targets[LRU_ACTIVE_ANON] + 1;
+			nr_to_scan = nr_file - ratio * nr_anon;
+			percentage = nr[LRU_FILE] * 100 / nr_file;
 			lru = LRU_BASE;
-			percentage = nr_anon * 100 / scan_target;
 		} else {
-			unsigned long scan_target = targets[LRU_INACTIVE_FILE] +
-						targets[LRU_ACTIVE_FILE] + 1;
+			nr_to_scan = nr_anon - nr_file / ratio;
+			percentage = nr[LRU_BASE] * 100 / nr_anon;
 			lru = LRU_FILE;
-			percentage = nr_file * 100 / scan_target;
 		}
 
 		/* Stop scanning the smaller of the LRU */
@@ -2143,14 +2139,8 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
 		 * scan target and the percentage scanning already complete
 		 */
 		lru = (lru == LRU_FILE) ? LRU_BASE : LRU_FILE;
-		nr_scanned = targets[lru] - nr[lru];
-		nr[lru] = targets[lru] * (100 - percentage) / 100;
-		nr[lru] -= min(nr[lru], nr_scanned);
-
-		lru += LRU_ACTIVE;
-		nr_scanned = targets[lru] - nr[lru];
-		nr[lru] = targets[lru] * (100 - percentage) / 100;
-		nr[lru] -= min(nr[lru], nr_scanned);
+		nr[lru] = nr_to_scan * percentage / 100;
+		nr[lru + LRU_ACTIVE] = nr_to_scan - nr[lru];
 
 		scan_adjusted = true;
 	}
-- 
1.7.10.4

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Minchan Kim]

Hello,

On Mon, Jun 09, 2014 at 09:27:16PM +0800, Chen Yucong wrote:
> Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> original scan targets introduces extra 40 bytes on the stack. This patch
> is able to avoid this situation and the call to memcpy(). At the same time,
> it does not change the relative design idea.
> 
> ratio = original_nr_file / original_nr_anon;
> 
> If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
>  x = nr_file - ratio * nr_anon;
> 
> if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
>  x = nr_anon - nr_file / ratio;

Nice cleanup!

Below one nitpick.

> 
> Signed-off-by: Chen Yucong <slaoub@gmail.com>
> ---
>  mm/vmscan.c |   28 +++++++++-------------------
>  1 file changed, 9 insertions(+), 19 deletions(-)
> 
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index a8ffe4e..daaf89c 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -2057,8 +2057,7 @@ out:
>  static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  {
>  	unsigned long nr[NR_LRU_LISTS];
> -	unsigned long targets[NR_LRU_LISTS];
> -	unsigned long nr_to_scan;
> +	unsigned long nr_to_scan, ratio;
>  	enum lru_list lru;
>  	unsigned long nr_reclaimed = 0;
>  	unsigned long nr_to_reclaim = sc->nr_to_reclaim;
> @@ -2067,8 +2066,8 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  
>  	get_scan_count(lruvec, sc, nr);
>  
> -	/* Record the original scan target for proportional adjustments later */
> -	memcpy(targets, nr, sizeof(nr));
> +	ratio = (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE] + 1) /
> +			(nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON] + 1);
>  
>  	/*
>  	 * Global reclaiming within direct reclaim at DEF_PRIORITY is a normal
> @@ -2088,7 +2087,6 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  	while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
>  					nr[LRU_INACTIVE_FILE]) {
>  		unsigned long nr_anon, nr_file, percentage;
> -		unsigned long nr_scanned;
>  
>  		for_each_evictable_lru(lru) {
>  			if (nr[lru]) {
> @@ -2123,15 +2121,13 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  			break;
>  
>  		if (nr_file > nr_anon) {
> -			unsigned long scan_target = targets[LRU_INACTIVE_ANON] +
> -						targets[LRU_ACTIVE_ANON] + 1;
> +			nr_to_scan = nr_file - ratio * nr_anon;
> +			percentage = nr[LRU_FILE] * 100 / nr_file;
>  			lru = LRU_BASE;
> -			percentage = nr_anon * 100 / scan_target;
>  		} else {
> -			unsigned long scan_target = targets[LRU_INACTIVE_FILE] +
> -						targets[LRU_ACTIVE_FILE] + 1;
> +			nr_to_scan = nr_anon - nr_file / ratio;
> +			percentage = nr[LRU_BASE] * 100 / nr_anon;

If both nr_file and nr_anon are zero, then the nr_anon could be zero
if HugePage are reclaimed so that it could pass the below check

        if (nr_reclaimed < nr_to_reclaim || scan_adjusted)


>  			lru = LRU_FILE;
> -			percentage = nr_file * 100 / scan_target;
>  		}
>  
>  		/* Stop scanning the smaller of the LRU */
> @@ -2143,14 +2139,8 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  		 * scan target and the percentage scanning already complete
>  		 */
>  		lru = (lru == LRU_FILE) ? LRU_BASE : LRU_FILE;
> -		nr_scanned = targets[lru] - nr[lru];
> -		nr[lru] = targets[lru] * (100 - percentage) / 100;
> -		nr[lru] -= min(nr[lru], nr_scanned);
> -
> -		lru += LRU_ACTIVE;
> -		nr_scanned = targets[lru] - nr[lru];
> -		nr[lru] = targets[lru] * (100 - percentage) / 100;
> -		nr[lru] -= min(nr[lru], nr_scanned);
> +		nr[lru] = nr_to_scan * percentage / 100;
> +		nr[lru + LRU_ACTIVE] = nr_to_scan - nr[lru];
>  
>  		scan_adjusted = true;
>  	}
> -- 
> 1.7.10.4
> 
> --
> 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:"dont@kvack.org"> email@kvack.org </a>

-- 
Kind regards,
Minchan Kim

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Tue, 2014-06-10 at 08:24 +0900, Minchan Kim wrote:
> Hello,
> 
> On Mon, Jun 09, 2014 at 09:27:16PM +0800, Chen Yucong wrote:
> > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > original scan targets introduces extra 40 bytes on the stack. This patch
> > is able to avoid this situation and the call to memcpy(). At the same time,
> > it does not change the relative design idea.
> > 
> > ratio = original_nr_file / original_nr_anon;
> > 
> > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> >  x = nr_file - ratio * nr_anon;
> > 
> > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> >  x = nr_anon - nr_file / ratio;
> 
> Nice cleanup!
> 
> Below one nitpick.
> 

> 
> If both nr_file and nr_anon are zero, then the nr_anon could be zero
> if HugePage are reclaimed so that it could pass the below check
> 
>         if (nr_reclaimed < nr_to_reclaim || scan_adjusted)
> 
> 
The Mel Gorman's patch has already handled this situation you're
describing. It's called:
 
mm: vmscan: use proportional scanning during direct reclaim and full
scan at DEF_PRIORITY

thx!
cyc

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Minchan Kim]

On Tue, Jun 10, 2014 at 08:10:51AM +0800, Chen Yucong wrote:
> On Tue, 2014-06-10 at 08:24 +0900, Minchan Kim wrote:
> > Hello,
> > 
> > On Mon, Jun 09, 2014 at 09:27:16PM +0800, Chen Yucong wrote:
> > > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > > original scan targets introduces extra 40 bytes on the stack. This patch
> > > is able to avoid this situation and the call to memcpy(). At the same time,
> > > it does not change the relative design idea.
> > > 
> > > ratio = original_nr_file / original_nr_anon;
> > > 
> > > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> > >  x = nr_file - ratio * nr_anon;
> > > 
> > > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> > >  x = nr_anon - nr_file / ratio;
> > 
> > Nice cleanup!
> > 
> > Below one nitpick.
> > 
> 
> > 
> > If both nr_file and nr_anon are zero, then the nr_anon could be zero
> > if HugePage are reclaimed so that it could pass the below check
> > 
> >         if (nr_reclaimed < nr_to_reclaim || scan_adjusted)
> > 
> > 
> The Mel Gorman's patch has already handled this situation you're
> describing. It's called:
>  
> mm: vmscan: use proportional scanning during direct reclaim and full
> scan at DEF_PRIORITY

It seems I was far away from vmscan.c for a while.
Thanks for the pointing out. So,

Acked-by: Minchan Kim <minchan@kernel.org>

-- 
Kind regards,
Minchan Kim

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Andrew Morton]

On Mon,  9 Jun 2014 21:27:16 +0800 Chen Yucong <slaoub@gmail.com> wrote:

> Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> original scan targets introduces extra 40 bytes on the stack. This patch
> is able to avoid this situation and the call to memcpy(). At the same time,
> it does not change the relative design idea.
> 
> ratio = original_nr_file / original_nr_anon;
> 
> If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
>  x = nr_file - ratio * nr_anon;
> 
> if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
>  x = nr_anon - nr_file / ratio;
> 
> ...
>

Are you sure this is an equivalent-to-before change?  If so, then I
can't immediately see why :(

> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -2057,8 +2057,7 @@ out:
>  static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  {
>  	unsigned long nr[NR_LRU_LISTS];
> -	unsigned long targets[NR_LRU_LISTS];
> -	unsigned long nr_to_scan;
> +	unsigned long nr_to_scan, ratio;
>  	enum lru_list lru;
>  	unsigned long nr_reclaimed = 0;
>  	unsigned long nr_to_reclaim = sc->nr_to_reclaim;
> @@ -2067,8 +2066,8 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  
>  	get_scan_count(lruvec, sc, nr);
>  
> -	/* Record the original scan target for proportional adjustments later */
> -	memcpy(targets, nr, sizeof(nr));
> +	ratio = (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE] + 1) /
> +			(nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON] + 1);
>  
>  	/*
>  	 * Global reclaiming within direct reclaim at DEF_PRIORITY is a normal
> @@ -2088,7 +2087,6 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  	while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
>  					nr[LRU_INACTIVE_FILE]) {
>  		unsigned long nr_anon, nr_file, percentage;
> -		unsigned long nr_scanned;
>  
>  		for_each_evictable_lru(lru) {
>  			if (nr[lru]) {
> @@ -2123,15 +2121,13 @@ static void shrink_lruvec(struct lruvec *lruvec, struct scan_control *sc)
>  			break;
>  
>  		if (nr_file > nr_anon) {
> -			unsigned long scan_target = targets[LRU_INACTIVE_ANON] +
> -						targets[LRU_ACTIVE_ANON] + 1;
> +			nr_to_scan = nr_file - ratio * nr_anon;
> +			percentage = nr[LRU_FILE] * 100 / nr_file;

here, nr_file and nr_anon are derived from the contents of nr[].  But
nr[] was modified in the for_each_evictable_lru() loop, so its contents
now may differ from what was in targets[]?

>  			lru = LRU_BASE;
> -			percentage = nr_anon * 100 / scan_target;
>  		} else {
> -			unsigned long scan_target = targets[LRU_INACTIVE_FILE] +
> -						targets[LRU_ACTIVE_FILE] + 1;
> +			nr_to_scan = nr_anon - nr_file / ratio;
> +			percentage = nr[LRU_BASE] * 100 / nr_anon;
>  			lru = LRU_FILE;
> -			percentage = nr_file * 100 / scan_target;
>  		}
>  
>  		/* Stop scanning the smaller of the LRU */
> ...

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Tue, 2014-06-10 at 16:33 -0700, Andrew Morton wrote:
> On Mon,  9 Jun 2014 21:27:16 +0800 Chen Yucong <slaoub@gmail.com> wrote:
> 
> > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > original scan targets introduces extra 40 bytes on the stack. This patch
> > is able to avoid this situation and the call to memcpy(). At the same time,
> > it does not change the relative design idea.
> > 
> > ratio = original_nr_file / original_nr_anon;
> > 
> > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> >  x = nr_file - ratio * nr_anon;
> > 
> > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> >  x = nr_anon - nr_file / ratio;
> > 
> > ...
> >
> 
> Are you sure this is an equivalent-to-before change?  If so, then I
> can't immediately see why :(
> 
The relative design idea is to keep

   ratio
	== scan_target[anon] : scan_target[file]
              == really_scanned_num[anon] : really_scanned_num[file]

The original implementation is 
   ratio 
        == (scan_target[anon] * percentage_anon) / 
           (scan_target[file] * percentage_file) 

To keep the original ratio, percentage_anon should equal to
percentage_file. In other word, we need to calculate the difference
value between percentage_anon and percentage_file, we also have to
record the original scan targets for this.

Instead, we can calculate the *ratio* at the beginning of
shrink_lruvec(). As a result, this can avoid introducing the extra 40
bytes.

In short, we have the same goal: keep the same *ratio* from beginning to
end.

thx!
cyc
 
       

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Tue, 2014-06-10 at 16:33 -0700, Andrew Morton wrote:
> >                       break;
> >  
> >               if (nr_file > nr_anon) {
> > -                     unsigned long scan_target =
> targets[LRU_INACTIVE_ANON] +
> >
> -                                             targets[LRU_ACTIVE_ANON]
> + 1;
> > +                     nr_to_scan = nr_file - ratio * nr_anon;
> > +                     percentage = nr[LRU_FILE] * 100 / nr_file;
> 
> here, nr_file and nr_anon are derived from the contents of nr[].  But
> nr[] was modified in the for_each_evictable_lru() loop, so its
> contents
> now may differ from what was in targets[]? 

nr_to_scan is used for recording the number of pages that should be
scanned to keep original *ratio*.

We can assume that the value of (nr_file > nr_anon) is true, nr_to_scan
should be distribute to nr[LRU_ACTIVE_FILE] and nr[LRU_INACTIVE_FILE] in
proportion.

    nr_file = nr[LRU_ACTIVE_FILE] + nr[LRU_INACTIVE_FILE];
    percentage = nr[LRU_FILE] / nr_file;

Note that in comparison with *old* percentage, the "new" percentage has
the different meaning. It is just used to divide nr_so_scan pages
appropriately.

thx!
cyc     

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Hugh Dickins]

On Wed, 11 Jun 2014, Chen Yucong wrote:
> On Tue, 2014-06-10 at 16:33 -0700, Andrew Morton wrote:
> > >                       break;
> > >  
> > >               if (nr_file > nr_anon) {
> > > -                     unsigned long scan_target =
> > targets[LRU_INACTIVE_ANON] +
> > >
> > -                                             targets[LRU_ACTIVE_ANON]
> > + 1;
> > > +                     nr_to_scan = nr_file - ratio * nr_anon;
> > > +                     percentage = nr[LRU_FILE] * 100 / nr_file;
> > 
> > here, nr_file and nr_anon are derived from the contents of nr[].  But
> > nr[] was modified in the for_each_evictable_lru() loop, so its
> > contents
> > now may differ from what was in targets[]? 
> 
> nr_to_scan is used for recording the number of pages that should be
> scanned to keep original *ratio*.
> 
> We can assume that the value of (nr_file > nr_anon) is true, nr_to_scan
> should be distribute to nr[LRU_ACTIVE_FILE] and nr[LRU_INACTIVE_FILE] in
> proportion.
> 
>     nr_file = nr[LRU_ACTIVE_FILE] + nr[LRU_INACTIVE_FILE];
>     percentage = nr[LRU_FILE] / nr_file;
> 
> Note that in comparison with *old* percentage, the "new" percentage has
> the different meaning. It is just used to divide nr_so_scan pages
> appropriately.

[PATCH] mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch

I have not reviewed your logic at all, but soon hit a divide-by-zero
crash on mmotm: it needs some such fix as below.

Signed-off-by: Hugh Dickins <hughd@google.com>
---

 mm/vmscan.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

--- mmotm/mm/vmscan.c	2014-06-12 17:46:36.632008452 -0700
+++ linux/mm/vmscan.c	2014-06-12 18:55:18.832425713 -0700
@@ -2122,11 +2122,12 @@ static void shrink_lruvec(struct lruvec
 			nr_to_scan = nr_file - ratio * nr_anon;
 			percentage = nr[LRU_FILE] * 100 / nr_file;
 			lru = LRU_BASE;
-		} else {
+		} else if (ratio) {
 			nr_to_scan = nr_anon - nr_file / ratio;
 			percentage = nr[LRU_BASE] * 100 / nr_anon;
 			lru = LRU_FILE;
-		}
+		} else
+			break;
 
 		/* Stop scanning the smaller of the LRU */
 		nr[lru] = 0;

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Sun, 2014-06-15 at 17:47 -0700, Hugh Dickins wrote:
> On Wed, 11 Jun 2014, Chen Yucong wrote:
> > On Tue, 2014-06-10 at 16:33 -0700, Andrew Morton wrote:
> > > >                       break;
> > > >  
> > > >               if (nr_file > nr_anon) {
> > > > -                     unsigned long scan_target =
> > > targets[LRU_INACTIVE_ANON] +
> > > >
> > > -                                             targets[LRU_ACTIVE_ANON]
> > > + 1;
> > > > +                     nr_to_scan = nr_file - ratio * nr_anon;
> > > > +                     percentage = nr[LRU_FILE] * 100 / nr_file;
> > > 
> > > here, nr_file and nr_anon are derived from the contents of nr[].  But
> > > nr[] was modified in the for_each_evictable_lru() loop, so its
> > > contents
> > > now may differ from what was in targets[]? 
> > 
> > nr_to_scan is used for recording the number of pages that should be
> > scanned to keep original *ratio*.
> > 
> > We can assume that the value of (nr_file > nr_anon) is true, nr_to_scan
> > should be distribute to nr[LRU_ACTIVE_FILE] and nr[LRU_INACTIVE_FILE] in
> > proportion.
> > 
> >     nr_file = nr[LRU_ACTIVE_FILE] + nr[LRU_INACTIVE_FILE];
> >     percentage = nr[LRU_FILE] / nr_file;
> > 
> > Note that in comparison with *old* percentage, the "new" percentage has
> > the different meaning. It is just used to divide nr_so_scan pages
> > appropriately.
> 
> [PATCH] mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch
> 
> I have not reviewed your logic at all, but soon hit a divide-by-zero
> crash on mmotm: it needs some such fix as below.
> 
> Signed-off-by: Hugh Dickins <hughd@google.com>
> ---
> 
>  mm/vmscan.c |    5 +++--
>  1 file changed, 3 insertions(+), 2 deletions(-)
> 
> --- mmotm/mm/vmscan.c	2014-06-12 17:46:36.632008452 -0700
> +++ linux/mm/vmscan.c	2014-06-12 18:55:18.832425713 -0700
> @@ -2122,11 +2122,12 @@ static void shrink_lruvec(struct lruvec
>  			nr_to_scan = nr_file - ratio * nr_anon;
>  			percentage = nr[LRU_FILE] * 100 / nr_file;
>  			lru = LRU_BASE;
> -		} else {
> +		} else if (ratio) {
>  			nr_to_scan = nr_anon - nr_file / ratio;
>  			percentage = nr[LRU_BASE] * 100 / nr_anon;
>  			lru = LRU_FILE;
> -		}
> +		} else
> +			break;
>  
>  		/* Stop scanning the smaller of the LRU */
>  		nr[lru] = 0;

I think I made a terrible mistake. If the value of
     (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE]) <
     (nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON])
is true , the ratio will always be zero in original patch. This is too
terrible. It is unfair for anon list. Although the above fix can avoid
hitting a divide-by-zero crash, it can not solve the problem of
fairness.

The following fix can solve divide-by-zero and unfair problems
simultaneously. But it needs to introduce a new variable for saving the
ratio of anon to file and relative operations.

thx!
cyc


Signed-off-by: Chen Yucong <slaoub@gmail.com>
---
 mm/vmscan.c |   30 +++++++++++-------------------
 1 file changed, 11 insertions(+), 19 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index a8ffe4e..cf8d0a3 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -2057,8 +2057,7 @@ out:
 static void shrink_lruvec(struct lruvec *lruvec, struct scan_control
*sc)
 {
 	unsigned long nr[NR_LRU_LISTS];
-	unsigned long targets[NR_LRU_LISTS];
-	unsigned long nr_to_scan;
+	unsigned long nr_to_scan, ratio_file_to_anon, ratio_anon_to_file;
 	enum lru_list lru;
 	unsigned long nr_reclaimed = 0;
 	unsigned long nr_to_reclaim = sc->nr_to_reclaim;
@@ -2067,8 +2066,10 @@ static void shrink_lruvec(struct lruvec *lruvec,
struct scan_control *sc)
 
 	get_scan_count(lruvec, sc, nr);
 
-	/* Record the original scan target for proportional adjustments later
*/
-	memcpy(targets, nr, sizeof(nr));
+	ratio_file_to_anon = (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE] +
1) /
+			     (nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON] + 1);
+	ratio_anon_to_file = (nr[LRU_INACTIVE_ANON] + nr[LRU_ACTIVE_ANON] +
1) /
+			     (nr[LRU_INACTIVE_FILE] + nr[LRU_ACTIVE_FILE] + 1);
 
 	/*
 	 * Global reclaiming within direct reclaim at DEF_PRIORITY is a normal
@@ -2088,7 +2089,6 @@ static void shrink_lruvec(struct lruvec *lruvec,
struct scan_control *sc)
 	while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
 					nr[LRU_INACTIVE_FILE]) {
 		unsigned long nr_anon, nr_file, percentage;
-		unsigned long nr_scanned;
 
 		for_each_evictable_lru(lru) {
 			if (nr[lru]) {
@@ -2123,15 +2123,13 @@ static void shrink_lruvec(struct lruvec *lruvec,
struct scan_control *sc)
 			break;
 
 		if (nr_file > nr_anon) {
-			unsigned long scan_target = targets[LRU_INACTIVE_ANON] +
-						targets[LRU_ACTIVE_ANON] + 1;
+			nr_to_scan = nr_file - ratio_file_to_anon * nr_anon;
+			percentage = nr[LRU_FILE] * 100 / nr_file;
 			lru = LRU_BASE;
-			percentage = nr_anon * 100 / scan_target;
 		} else {
-			unsigned long scan_target = targets[LRU_INACTIVE_FILE] +
-						targets[LRU_ACTIVE_FILE] + 1;
+			nr_to_scan = nr_anon - ratio_anon_to_file * nr_file;
+			percentage = nr[LRU_BASE] * 100 / nr_anon;
 			lru = LRU_FILE;
-			percentage = nr_file * 100 / scan_target;
 		}
 
 		/* Stop scanning the smaller of the LRU */
@@ -2143,14 +2141,8 @@ static void shrink_lruvec(struct lruvec *lruvec,
struct scan_control *sc)
 		 * scan target and the percentage scanning already complete
 		 */
 		lru = (lru == LRU_FILE) ? LRU_BASE : LRU_FILE;
-		nr_scanned = targets[lru] - nr[lru];
-		nr[lru] = targets[lru] * (100 - percentage) / 100;
-		nr[lru] -= min(nr[lru], nr_scanned);
-
-		lru += LRU_ACTIVE;
-		nr_scanned = targets[lru] - nr[lru];
-		nr[lru] = targets[lru] * (100 - percentage) / 100;
-		nr[lru] -= min(nr[lru], nr_scanned);
+		nr[lru] = nr_to_scan * percentage / 100;
+		nr[lru + LRU_ACTIVE] = nr_to_scan - nr[lru];
 
 		scan_adjusted = true;
 	}
-- 
1.7.10.4



--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Mon, 2014-06-09 at 21:27 +0800, Chen Yucong wrote:
> Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> original scan targets introduces extra 40 bytes on the stack. This patch
> is able to avoid this situation and the call to memcpy(). At the same time,
> it does not change the relative design idea.
> 
> ratio = original_nr_file / original_nr_anon;
> 
> If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
>  x = nr_file - ratio * nr_anon;
> 
> if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
>  x = nr_anon - nr_file / ratio;
> 
Hi Andrew Morton,

I think the patch
 
[PATCH]
mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch

which I committed should be discarded. Because It have some critical
defects.
    1) If we want to solve the divide-by-zero and unfair problems, it
needs to two variables for recording the ratios.
 
    2) For "x = nr_file - ratio * nr_anon", the "x" is likely to be a
negative number. we can assume:

      nr[LRU_ACTIVE_FILE] = 30
      nr[LRU_INACTIVE_FILE] = 30
      nr[LRU_ACTIVE_ANON] = 0
      nr[LRU_INACTIVE_ANON] = 40

      ratio = 60/40 = 3/2

When the value of (nr_reclaimed < nr_to_reclaim) become false, there are
the following results:
      nr[LRU_ACTIVE_FILE] = 15
      nr[LRU_INACTIVE_FILE] = 15
      nr[LRU_ACTIVE_ANON] = 0
      nr[LRU_INACTIVE_ANON] = 25
 
      nr_file = 30
      nr_anon = 25

      x = 30 - 25 * (3/2) = 30 - 37.5 = -7.5.

The result is too terrible. 
   
   3) This method is less accurate than the original, especially for the
qualitative difference between FILE and ANON that is very small.

thx!
cyc  
   

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Andrew Morton]

On Mon, 16 Jun 2014 20:57:54 +0800 Chen Yucong <slaoub@gmail.com> wrote:

> On Mon, 2014-06-09 at 21:27 +0800, Chen Yucong wrote:
> > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > original scan targets introduces extra 40 bytes on the stack. This patch
> > is able to avoid this situation and the call to memcpy(). At the same time,
> > it does not change the relative design idea.
> > 
> > ratio = original_nr_file / original_nr_anon;
> > 
> > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> >  x = nr_file - ratio * nr_anon;
> > 
> > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> >  x = nr_anon - nr_file / ratio;
> > 
> Hi Andrew Morton,
> 
> I think the patch
>  
> [PATCH]
> mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch
> 
> which I committed should be discarded.

OK, thanks.

I assume you're referring to
mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec.patch
- I don't think a -fix.patch existed?

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Chen Yucong]

On Mon, 2014-06-16 at 16:42 -0700, Andrew Morton wrote:
> On Mon, 16 Jun 2014 20:57:54 +0800 Chen Yucong <slaoub@gmail.com> wrote:
> 
> > On Mon, 2014-06-09 at 21:27 +0800, Chen Yucong wrote:
> > > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > > original scan targets introduces extra 40 bytes on the stack. This patch
> > > is able to avoid this situation and the call to memcpy(). At the same time,
> > > it does not change the relative design idea.
> > > 
> > > ratio = original_nr_file / original_nr_anon;
> > > 
> > > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> > >  x = nr_file - ratio * nr_anon;
> > > 
> > > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> > >  x = nr_anon - nr_file / ratio;
> > > 
> > Hi Andrew Morton,
> > 
> > I think the patch
> >  
> > [PATCH]
> > mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch
> > 
> > which I committed should be discarded.
> 
> OK, thanks.
> 
> I assume you're referring to
> mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec.patch
> - I don't think a -fix.patch existed?

Yes. the patch that should be discarded is 
mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec.patch

thx!
cyc


--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Minchan Kim]

On Mon, Jun 16, 2014 at 04:42:37PM -0700, Andrew Morton wrote:
> On Mon, 16 Jun 2014 20:57:54 +0800 Chen Yucong <slaoub@gmail.com> wrote:
> 
> > On Mon, 2014-06-09 at 21:27 +0800, Chen Yucong wrote:
> > > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > > original scan targets introduces extra 40 bytes on the stack. This patch
> > > is able to avoid this situation and the call to memcpy(). At the same time,
> > > it does not change the relative design idea.
> > > 
> > > ratio = original_nr_file / original_nr_anon;
> > > 
> > > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> > >  x = nr_file - ratio * nr_anon;
> > > 
> > > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> > >  x = nr_anon - nr_file / ratio;
> > > 
> > Hi Andrew Morton,
> > 
> > I think the patch
> >  
> > [PATCH]
> > mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch
> > 
> > which I committed should be discarded.
> 
> OK, thanks.
> 
> I assume you're referring to
> mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec.patch

True.

-- 
Kind regards,
Minchan Kim

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] mm/vmscan.c: avoid recording the original scan targets in shrink_lruvec()

[Minchan Kim]

On Mon, Jun 16, 2014 at 08:57:54PM +0800, Chen Yucong wrote:
> On Mon, 2014-06-09 at 21:27 +0800, Chen Yucong wrote:
> > Via https://lkml.org/lkml/2013/4/10/334 , we can find that recording the
> > original scan targets introduces extra 40 bytes on the stack. This patch
> > is able to avoid this situation and the call to memcpy(). At the same time,
> > it does not change the relative design idea.
> > 
> > ratio = original_nr_file / original_nr_anon;
> > 
> > If (nr_file > nr_anon), then ratio = (nr_file - x) / nr_anon.
> >  x = nr_file - ratio * nr_anon;
> > 
> > if (nr_file <= nr_anon), then ratio = nr_file / (nr_anon - x).
> >  x = nr_anon - nr_file / ratio;
> > 
> Hi Andrew Morton,
> 
> I think the patch
>  
> [PATCH]
> mm-vmscanc-avoid-recording-the-original-scan-targets-in-shrink_lruvec-fix.patch
> 
> which I committed should be discarded. Because It have some critical
> defects.
>     1) If we want to solve the divide-by-zero and unfair problems, it
> needs to two variables for recording the ratios.
>  
>     2) For "x = nr_file - ratio * nr_anon", the "x" is likely to be a
> negative number. we can assume:
> 
>       nr[LRU_ACTIVE_FILE] = 30
>       nr[LRU_INACTIVE_FILE] = 30
>       nr[LRU_ACTIVE_ANON] = 0
>       nr[LRU_INACTIVE_ANON] = 40
> 
>       ratio = 60/40 = 3/2
> 
> When the value of (nr_reclaimed < nr_to_reclaim) become false, there are
> the following results:
>       nr[LRU_ACTIVE_FILE] = 15
>       nr[LRU_INACTIVE_FILE] = 15
>       nr[LRU_ACTIVE_ANON] = 0
>       nr[LRU_INACTIVE_ANON] = 25
>  
>       nr_file = 30
>       nr_anon = 25
> 
>       x = 30 - 25 * (3/2) = 30 - 37.5 = -7.5.
> 
> The result is too terrible. 
>    
>    3) This method is less accurate than the original, especially for the
> qualitative difference between FILE and ANON that is very small.

Yes, 3 changed old behavior. I'm ashamed but wanted to clean it up.
Is it worth to clean it up?