linux-kernel - [PATCH -mm 1/2] mm: fix quadratic behaviour in get_unmapped_area

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 23 Feb 2012 14:56:36 -0500
From:	Rik van Riel <riel@...hat.com>
To:	linux-mm@...ck.org
Cc:	linux-kernel@...r.kernel.org, akpm@...ux-foundation.org,
	Mel Gorman <mel@....ul.ie>,
	Johannes Weiner <hannes@...xchg.org>,
	KOSAKI Motohiro <kosaki.motohiro@...il.com>,
	Andrea Arcangeli <aarcange@...hat.com>, hughd@...gle.com
Subject: [PATCH -mm 1/2] mm: fix quadratic behaviour in
 get_unmapped_area_topdown

When we look for a VMA smaller than the cached_hole_size, we set the
starting search address to mm->mmap_base, to try and find our hole.

However, even in the case where we fall through and found nothing at
the mm->free_area_cache, we still reset the search address to mm->mmap_base.
This bug results in quadratic behaviour, with observed mmap times of 0.4
seconds for processes that have very fragmented memory.

If there is no hole small enough for us to fit the VMA, and we have
no good spot for us right at mm->free_area_cache, we are much better
off continuing the search down from mm->free_area_cache, instead of
all the way from the top.

Signed-off-by: Rik van Riel <riel@...hat.com>
---
Tested on x86-64, the other architectures have the exact same bug cut'n'pasted.

 arch/sh/mm/mmap.c            |    1 -
 arch/sparc/mm/hugetlbpage.c  |    2 --
 arch/x86/kernel/sys_x86_64.c |    2 --
 mm/mmap.c                    |    2 --
 4 files changed, 0 insertions(+), 7 deletions(-)

diff --git a/arch/sh/mm/mmap.c b/arch/sh/mm/mmap.c
index afeb710..fba1b32 100644
--- a/arch/sh/mm/mmap.c
+++ b/arch/sh/mm/mmap.c
@@ -188,7 +188,6 @@ arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
 	if (unlikely(mm->mmap_base < len))
 		goto bottomup;
 
-	addr = mm->mmap_base-len;
 	if (do_colour_align)
 		addr = COLOUR_ALIGN_DOWN(addr, pgoff);
 
diff --git a/arch/sparc/mm/hugetlbpage.c b/arch/sparc/mm/hugetlbpage.c
index 07e1453..603a01d 100644
--- a/arch/sparc/mm/hugetlbpage.c
+++ b/arch/sparc/mm/hugetlbpage.c
@@ -115,8 +115,6 @@ hugetlb_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
 	if (unlikely(mm->mmap_base < len))
 		goto bottomup;
 
-	addr = (mm->mmap_base-len) & HPAGE_MASK;
-
 	do {
 		/*
 		 * Lookup failure means no vma is above this address,
diff --git a/arch/x86/kernel/sys_x86_64.c b/arch/x86/kernel/sys_x86_64.c
index 0514890..1a3fa81 100644
--- a/arch/x86/kernel/sys_x86_64.c
+++ b/arch/x86/kernel/sys_x86_64.c
@@ -240,8 +240,6 @@ arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
 	if (mm->mmap_base < len)
 		goto bottomup;
 
-	addr = mm->mmap_base-len;
-
 	do {
 		addr = align_addr(addr, filp, ALIGN_TOPDOWN);
 
diff --git a/mm/mmap.c b/mm/mmap.c
index 3f758c7..5eafe26 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -1479,8 +1479,6 @@ arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
 	if (mm->mmap_base < len)
 		goto bottomup;
 
-	addr = mm->mmap_base-len;
-
 	do {
 		/*
 		 * Lookup failure means no vma is above this address,

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/