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/

Powered by blists - more mailing lists