[patch 4/5]thp: correct order in lru list for split huge page

[patch 4/5]thp: correct order in lru list for split huge page

[Shaohua Li]

If a huge page is split, all the subpages should live in lru list adjacently
because they should be taken as a whole.
In page split, with current code:
a. if huge page is in lru list, the order is: page, page+HPAGE_PMD_NR-1,
page + HPAGE_PMD_NR-2, ..., page + 1(in lru page reclaim order)
b. otherwise, the order is: page, ..other pages.., page + 1, page + 2, ...(in
lru page reclaim order). page + 1 ... page + HPAGE_PMD_NR - 1 are in the lru
reclaim tail.

In case a, the order is wrong. In case b, page is isolated (to be reclaimed),
but other tail pages will not soon.

With below patch:
in case a, the order is: page, page + 1, ... page + HPAGE_PMD_NR-1(in lru page
reclaim order).
in case b, the order is: page + 1, ... page + HPAGE_PMD_NR-1 (in lru page reclaim
order). The tail pages are in the lru reclaim head.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
---
 mm/huge_memory.c |    5 ++---
 mm/swap.c        |    5 +++--
 2 files changed, 5 insertions(+), 5 deletions(-)

Index: linux/mm/huge_memory.c
===================================================================
--- linux.orig/mm/huge_memory.c	2011-10-25 09:06:55.000000000 +0800
+++ linux/mm/huge_memory.c	2011-10-25 09:31:07.000000000 +0800
@@ -1162,7 +1162,6 @@ static int __split_huge_page_splitting(s
 static void __split_huge_page_refcount(struct page *page)
 {
 	int i;
-	unsigned long head_index = page->index;
 	struct zone *zone = page_zone(page);
 	int zonestat;
 
@@ -1170,7 +1169,7 @@ static void __split_huge_page_refcount(s
 	spin_lock_irq(&zone->lru_lock);
 	compound_lock(page);
 
-	for (i = 1; i < HPAGE_PMD_NR; i++) {
+	for (i = HPAGE_PMD_NR - 1; i >= 1; i--) {
 		struct page *page_tail = page + i;
 
 		/* tail_page->_count cannot change */
@@ -1221,7 +1220,7 @@ static void __split_huge_page_refcount(s
 		BUG_ON(page_tail->mapping);
 		page_tail->mapping = page->mapping;
 
-		page_tail->index = ++head_index;
+		page_tail->index = page->index + i;
 
 		BUG_ON(!PageAnon(page_tail));
 		BUG_ON(!PageUptodate(page_tail));
Index: linux/mm/swap.c
===================================================================
--- linux.orig/mm/swap.c	2011-10-25 08:36:09.000000000 +0800
+++ linux/mm/swap.c	2011-10-25 09:31:07.000000000 +0800
@@ -661,11 +661,12 @@ void lru_add_page_tail(struct zone* zone
 		if (likely(PageLRU(page)))
 			head = page->lru.prev;
 		else
-			head = &zone->lru[lru].list;
+			head = zone->lru[lru].list.prev;
 		__add_page_to_lru_list(zone, page_tail, lru, head);
 	} else {
 		SetPageUnevictable(page_tail);
-		add_page_to_lru_list(zone, page_tail, LRU_UNEVICTABLE);
+		head = zone->lru[LRU_UNEVICTABLE].list.prev;
+		__add_page_to_lru_list(zone, page_tail, LRU_UNEVICTABLE, head);
 	}
 }
 


--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [patch 4/5]thp: correct order in lru list for split huge page

[Minchan Kim]

On Tue, Oct 25, 2011 at 10:59:37AM +0800, Shaohua Li wrote:
> If a huge page is split, all the subpages should live in lru list adjacently
> because they should be taken as a whole.
> In page split, with current code:
> a. if huge page is in lru list, the order is: page, page+HPAGE_PMD_NR-1,
> page + HPAGE_PMD_NR-2, ..., page + 1(in lru page reclaim order)
> b. otherwise, the order is: page, ..other pages.., page + 1, page + 2, ...(in
> lru page reclaim order). page + 1 ... page + HPAGE_PMD_NR - 1 are in the lru
> reclaim tail.
> 
> In case a, the order is wrong. In case b, page is isolated (to be reclaimed),
> but other tail pages will not soon.
> 
> With below patch:
> in case a, the order is: page, page + 1, ... page + HPAGE_PMD_NR-1(in lru page
> reclaim order).
> in case b, the order is: page + 1, ... page + HPAGE_PMD_NR-1 (in lru page reclaim
> order). The tail pages are in the lru reclaim head.
> 
> Signed-off-by: Shaohua Li <shaohua.li@intel.com>

In case of a, it doesn't matter ordering of subpages.
As a huge page, age of sub pages are same.

In case of b, what a page is located in tail and other subpages are located in head
isn't critical problem.

Having said that, it's more consistent and simple patch.
So I like that. Nice catch, Shaohua!

Reviewed-by: Minchan Kim <minchan.kim@gmail.com>
-- 
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [patch 4/5]thp: correct order in lru list for split huge page

[Shaohua Li]

On Fri, 2011-10-28 at 07:19 +0800, Minchan Kim wrote:
> On Tue, Oct 25, 2011 at 10:59:37AM +0800, Shaohua Li wrote:
> > If a huge page is split, all the subpages should live in lru list adjacently
> > because they should be taken as a whole.
> > In page split, with current code:
> > a. if huge page is in lru list, the order is: page, page+HPAGE_PMD_NR-1,
> > page + HPAGE_PMD_NR-2, ..., page + 1(in lru page reclaim order)
> > b. otherwise, the order is: page, ..other pages.., page + 1, page + 2, ...(in
> > lru page reclaim order). page + 1 ... page + HPAGE_PMD_NR - 1 are in the lru
> > reclaim tail.
> > 
> > In case a, the order is wrong. In case b, page is isolated (to be reclaimed),
> > but other tail pages will not soon.
> > 
> > With below patch:
> > in case a, the order is: page, page + 1, ... page + HPAGE_PMD_NR-1(in lru page
> > reclaim order).
> > in case b, the order is: page + 1, ... page + HPAGE_PMD_NR-1 (in lru page reclaim
> > order). The tail pages are in the lru reclaim head.
> > 
> > Signed-off-by: Shaohua Li <shaohua.li@intel.com>
> 
> In case of a, it doesn't matter ordering of subpages.
> As a huge page, age of sub pages are same.
It does matter. Hugepage is split first and then reclaim. if page, page
+HPAGE_PMD_NR-1 is reclaimed, you can't get an order-1 page. but if
page, page+1 is reclaimed, you can.

> In case of b, what a page is located in tail and other subpages are located in head
> isn't critical problem.
Same way 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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [patch 4/5]thp: correct order in lru list for split huge page

[Minchan Kim]

On Fri, Oct 28, 2011 at 01:08:58PM +0800, Shaohua Li wrote:
> On Fri, 2011-10-28 at 07:19 +0800, Minchan Kim wrote:
> > On Tue, Oct 25, 2011 at 10:59:37AM +0800, Shaohua Li wrote:
> > > If a huge page is split, all the subpages should live in lru list adjacently
> > > because they should be taken as a whole.
> > > In page split, with current code:
> > > a. if huge page is in lru list, the order is: page, page+HPAGE_PMD_NR-1,
> > > page + HPAGE_PMD_NR-2, ..., page + 1(in lru page reclaim order)
> > > b. otherwise, the order is: page, ..other pages.., page + 1, page + 2, ...(in
> > > lru page reclaim order). page + 1 ... page + HPAGE_PMD_NR - 1 are in the lru
> > > reclaim tail.
> > > 
> > > In case a, the order is wrong. In case b, page is isolated (to be reclaimed),
> > > but other tail pages will not soon.
> > > 
> > > With below patch:
> > > in case a, the order is: page, page + 1, ... page + HPAGE_PMD_NR-1(in lru page
> > > reclaim order).
> > > in case b, the order is: page + 1, ... page + HPAGE_PMD_NR-1 (in lru page reclaim
> > > order). The tail pages are in the lru reclaim head.
> > > 
> > > Signed-off-by: Shaohua Li <shaohua.li@intel.com>
> > 
> > In case of a, it doesn't matter ordering of subpages.
> > As a huge page, age of sub pages are same.
> It does matter. Hugepage is split first and then reclaim. if page, page
> +HPAGE_PMD_NR-1 is reclaimed, you can't get an order-1 page. but if
> page, page+1 is reclaimed, you can.

Right you are. I didn't catch up it.
It would be better to add it in description.
It's most important part in this patch.

Thanks.

-- 
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [patch 4/5]thp: correct order in lru list for split huge page

[Andrea Arcangeli]

Hi Minchan and Shaohua,

On Fri, Oct 28, 2011 at 04:21:25PM +0900, Minchan Kim wrote:
> On Fri, Oct 28, 2011 at 01:08:58PM +0800, Shaohua Li wrote:
> > On Fri, 2011-10-28 at 07:19 +0800, Minchan Kim wrote:
> > > On Tue, Oct 25, 2011 at 10:59:37AM +0800, Shaohua Li wrote:
> > > > If a huge page is split, all the subpages should live in lru list adjacently
> > > > because they should be taken as a whole.
> > > > In page split, with current code:
> > > > a. if huge page is in lru list, the order is: page, page+HPAGE_PMD_NR-1,
> > > > page + HPAGE_PMD_NR-2, ..., page + 1(in lru page reclaim order)
> > > > b. otherwise, the order is: page, ..other pages.., page + 1, page + 2, ...(in
> > > > lru page reclaim order). page + 1 ... page + HPAGE_PMD_NR - 1 are in the lru
> > > > reclaim tail.
> > > > 
> > > > In case a, the order is wrong. In case b, page is isolated (to be reclaimed),
> > > > but other tail pages will not soon.
> > > > 
> > > > With below patch:
> > > > in case a, the order is: page, page + 1, ... page + HPAGE_PMD_NR-1(in lru page
> > > > reclaim order).
> > > > in case b, the order is: page + 1, ... page + HPAGE_PMD_NR-1 (in lru page reclaim
> > > > order). The tail pages are in the lru reclaim head.
> > > > 
> > > > Signed-off-by: Shaohua Li <shaohua.li@intel.com>
> > > 
> > > In case of a, it doesn't matter ordering of subpages.
> > > As a huge page, age of sub pages are same.
> > It does matter. Hugepage is split first and then reclaim. if page, page
> > +HPAGE_PMD_NR-1 is reclaimed, you can't get an order-1 page. but if
> > page, page+1 is reclaimed, you can.
> 
> Right you are. I didn't catch up it.
> It would be better to add it in description.
> It's most important part in this patch.

Actually the way the buddy allocator works it will compact the
hugepage identically, regardless of the order of the freeing of the
subpages. It might be slightly more efficient because of CPU cache
effects to do it in order for the buddy algorithm so we may touch one
less cacheline by finishing building an entire 1m page before jumping
to the second half, but from a practical standpoint it's irrelevant.

Case b only can materialize if the splitted page is under VM
isolation, which is a fairly uncommon case, and the page being
isolated while I splitted it looked a tricky enough that I guess I
didn't attempt to optimize it for the lru ordering and I was happy
enough it could work safe too :). Now seeing this optimization it's
strightforward, so it's certainly good idea to apply. We can apply
both but for case a it's purely theoretical and no better runtime
change is possible out of 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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [patch 4/5]thp: correct order in lru list for split huge page

[Andrea Arcangeli]

I adjusted comment and removed the isolated lru changes which seem
unnecessary.

I would have preferred > 0, but I thought >= 1 may make it more
explicit it's really not meant to hit on the first page.

====
From: Shaohua Li <shaohua.li@intel.com>
Subject: thp: improve order in lru list for split huge page

Put the tail subpages of an isolated hugepage under splitting in the
lru reclaim head as they supposedly should be isolated too next.

Queues the subpages in physical order in the lru for non isolated
hugepages under splitting. That might provide some theoretical cache
benefit to the buddy allocator later.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
Signed-off-by: Andrea Arcangeli <aarcange@redhat.com>
---
 mm/huge_memory.c |    5 ++---
 mm/swap.c        |    2 +-
 2 files changed, 3 insertions(+), 4 deletions(-)

diff --git a/mm/huge_memory.c b/mm/huge_memory.c
index fd925d0..e221fbf 100644
--- a/mm/huge_memory.c
+++ b/mm/huge_memory.c
@@ -1199,7 +1199,6 @@ static int __split_huge_page_splitting(struct page *page,
 static void __split_huge_page_refcount(struct page *page)
 {
 	int i;
-	unsigned long head_index = page->index;
 	struct zone *zone = page_zone(page);
 	int zonestat;
 	int tail_count = 0;
@@ -1208,7 +1207,7 @@ static void __split_huge_page_refcount(struct page *page)
 	spin_lock_irq(&zone->lru_lock);
 	compound_lock(page);
 
-	for (i = 1; i < HPAGE_PMD_NR; i++) {
+	for (i = HPAGE_PMD_NR - 1; i >= 1; i--) {
 		struct page *page_tail = page + i;
 
 		/* tail_page->_mapcount cannot change */
@@ -1271,7 +1270,7 @@ static void __split_huge_page_refcount(struct page *page)
 		BUG_ON(page_tail->mapping);
 		page_tail->mapping = page->mapping;
 
-		page_tail->index = ++head_index;
+		page_tail->index = page->index + i;
 
 		BUG_ON(!PageAnon(page_tail));
 		BUG_ON(!PageUptodate(page_tail));
diff --git a/mm/swap.c b/mm/swap.c
index a91caf7..f8cfc91 100644
--- a/mm/swap.c
+++ b/mm/swap.c
@@ -684,7 +684,7 @@ void lru_add_page_tail(struct zone* zone,
 		if (likely(PageLRU(page)))
 			head = page->lru.prev;
 		else
-			head = &zone->lru[lru].list;
+			head = zone->lru[lru].list.prev;
 		__add_page_to_lru_list(zone, page_tail, lru, head);
 	} else {
 		SetPageUnevictable(page_tail);

--
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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>