[PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[Mikulas Patocka]

Hi

This patch fixes a bug introduced in "mm: simplify find_vma_prev()". You 
can apply this, or alternatively revert the original patch.

Mikulas

---

mm: fix find_vma_prev

The commit mm: simplify find_vma_prev()
[6bd4837de96e7d9f9bf33e59117c24fc230862ac] broke memory management on PA-RISC.

After application of the patch, programs that allocate big arrays on the stack
crash with segfault, for example, this will crash if compiled without
optimization:
int main()
{
	char array[200000];
	array[199999] = 0;
	return 0;
}

The reason is that PA-RISC has up-growing stack and the stack is usually the
last memory area. In the above example, a page fault happens above the stack.

Previously, if we passed too high address to find_vma_prev, it returned NULL
and stored the last VMA in *pprev. After "simplify find_vma_prev" change, it
stores NULL in *pprev. Consequently, the stack area is not found and it is
not expanded, as it used to be before the change.

This patch restores the old behavior and makes it return the last VMA in *pprev
if the requested address is higher than address of any other VMA.

Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

---
 mm/mmap.c |   12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

Index: linux-3.3-rc6-fast/mm/mmap.c
===================================================================
--- linux-3.3-rc6-fast.orig/mm/mmap.c	2012-03-05 01:25:52.000000000 +0100
+++ linux-3.3-rc6-fast/mm/mmap.c	2012-03-05 01:29:22.000000000 +0100
@@ -1605,7 +1605,6 @@ EXPORT_SYMBOL(find_vma);
 
 /*
  * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
- * Note: pprev is set to NULL when return value is NULL.
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,
@@ -1614,7 +1613,16 @@ find_vma_prev(struct mm_struct *mm, unsi
 	struct vm_area_struct *vma;
 
 	vma = find_vma(mm, addr);
-	*pprev = vma ? vma->vm_prev : NULL;
+	if (vma) {
+		*pprev = vma->vm_prev;
+	} else {
+		struct rb_node *rb_node = mm->mm_rb.rb_node;
+		*pprev = NULL;
+		while (rb_node) {
+			*pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb);
+			rb_node = rb_node->rb_right;
+		}
+	}
 	return vma;
 }
 

Re: [PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[Linus Torvalds]

On Sun, Mar 4, 2012 at 4:52 PM, Mikulas Patocka <mpatocka@redhat.com> wrote:
>
> This patch fixes a bug introduced in "mm: simplify find_vma_prev()". You
> can apply this, or alternatively revert the original patch.

Hmm.

I realize the patch is a bug-fix, but I do wonder if we shouldn't look
at alternatives.

In particular, how about we just change the rule to be clearer, and
make the rule be:

 - no more find_vma_prev() AT ALL.

 - callers get turned into "find_vma()" and then we have a
"vma_prev()", which basically does your thing.

 - many of the callers seem to be interested in "prev" *only* if they
found a vma. For example, the do_mlock() kind of logic seems to be
common:

    vma = find_vma_prev(current->mm, start, &prev);
    if (!vma || vma->vm_start > start)
        return -ENOMEM;

   which implies that the current find_vma_prev() semantics are really
wrong, because they force us to do extra work in this case where we
really really don't care about the result.

So we could do an entirely mechanical conversion of

   vma = find_vma_prev(mm, address, &prev_vma);

into

   vma = find_vma(mm, address);
   prev_vma = vma_prev(vma);

and then after we've done that conversion, it looks like the bulk of
them will not care about "prev_vma" if vma is NULL, so they can then
be replaced with a pure

   prev_vma = vma->vm_prev;

instead. Leaving just the (few) cases that may care about the
"previous vma may be the last vma of the VM" case.

Hmm? And we'd get away from that horrible "find_vma_prev()" interface
that uses pointers to vma pointers for return values. Ugh. There only
seems to be nine callers in the whole kernel.

                 Linus

Re: [PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[Mikulas Patocka]

On Sun, 4 Mar 2012, Linus Torvalds wrote:

> On Sun, Mar 4, 2012 at 4:52 PM, Mikulas Patocka <mpatocka@redhat.com> wrote:
> >
> > This patch fixes a bug introduced in "mm: simplify find_vma_prev()". You
> > can apply this, or alternatively revert the original patch.
> 
> Hmm.
> 
> I realize the patch is a bug-fix, but I do wonder if we shouldn't look
> at alternatives.
> 
> In particular, how about we just change the rule to be clearer, and
> make the rule be:
> 
>  - no more find_vma_prev() AT ALL.
> 
>  - callers get turned into "find_vma()" and then we have a
> "vma_prev()", which basically does your thing.
> 
>  - many of the callers seem to be interested in "prev" *only* if they
> found a vma. For example, the do_mlock() kind of logic seems to be
> common:
> 
>     vma = find_vma_prev(current->mm, start, &prev);
>     if (!vma || vma->vm_start > start)
>         return -ENOMEM;
> 
>    which implies that the current find_vma_prev() semantics are really
> wrong, because they force us to do extra work in this case where we
> really really don't care about the result.
> 
> So we could do an entirely mechanical conversion of
> 
>    vma = find_vma_prev(mm, address, &prev_vma);
> 
> into
> 
>    vma = find_vma(mm, address);
>    prev_vma = vma_prev(vma);
> 
> and then after we've done that conversion, it looks like the bulk of
> them will not care about "prev_vma" if vma is NULL, so they can then
> be replaced with a pure
> 
>    prev_vma = vma->vm_prev;
> 
> instead. Leaving just the (few) cases that may care about the
> "previous vma may be the last vma of the VM" case.
> 
> Hmm? And we'd get away from that horrible "find_vma_prev()" interface
> that uses pointers to vma pointers for return values. Ugh. There only
> seems to be nine callers in the whole kernel.
> 
>                  Linus

You can try this to remove most users of find_vma_prev (only three are 
left --- those dealing with up-growing stack). But the patch should be 
delayed until the next merge window.

Mikulas

---

mm: don't use find_vma_prev

Convert find_vma_prev callers to use find_vma. As we have vma->vm_prev field,
we no longer need to use find_vma_prev, we can use find_vma instead.

find_vma_prev is used only in cases where address may be above all existing
vmas and we need the last vma (it is returned in pprev pointer).

Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

---
 arch/tile/mm/hugetlbpage.c |    4 +++-
 arch/x86/mm/hugetlbpage.c  |    4 +++-
 mm/madvise.c               |   10 +++++++---
 mm/mempolicy.c             |    4 +++-
 mm/mlock.c                 |    4 +++-
 mm/mprotect.c              |    4 +++-
 6 files changed, 22 insertions(+), 8 deletions(-)

Index: linux-3.3-rc6-fast/arch/tile/mm/hugetlbpage.c
===================================================================
--- linux-3.3-rc6-fast.orig/arch/tile/mm/hugetlbpage.c	2012-03-06 19:04:45.000000000 +0100
+++ linux-3.3-rc6-fast/arch/tile/mm/hugetlbpage.c	2012-03-06 19:05:05.000000000 +0100
@@ -226,12 +226,14 @@ try_again:
 		 * Lookup failure means no vma is above this address,
 		 * i.e. return with success:
 		 */
-		vma = find_vma_prev(mm, addr, &prev_vma);
+		vma = find_vma(mm, addr);
 		if (!vma) {
 			return addr;
 			break;
 		}
 
+		prev_vma = vma->vm_prev;
+
 		/*
 		 * new region fits between prev_vma->vm_end and
 		 * vma->vm_start, use it:
Index: linux-3.3-rc6-fast/arch/x86/mm/hugetlbpage.c
===================================================================
--- linux-3.3-rc6-fast.orig/arch/x86/mm/hugetlbpage.c	2012-03-06 19:02:56.000000000 +0100
+++ linux-3.3-rc6-fast/arch/x86/mm/hugetlbpage.c	2012-03-06 19:04:10.000000000 +0100
@@ -333,9 +333,11 @@ try_again:
 		 * Lookup failure means no vma is above this address,
 		 * i.e. return with success:
 		 */
-		if (!(vma = find_vma_prev(mm, addr, &prev_vma)))
+		if (!(vma = find_vma(mm, addr)))
 			return addr;
 
+		prev_vma = vma->vm_prev;
+
 		/*
 		 * new region fits between prev_vma->vm_end and
 		 * vma->vm_start, use it:
Index: linux-3.3-rc6-fast/mm/madvise.c
===================================================================
--- linux-3.3-rc6-fast.orig/mm/madvise.c	2012-03-06 19:06:04.000000000 +0100
+++ linux-3.3-rc6-fast/mm/madvise.c	2012-03-06 19:07:21.000000000 +0100
@@ -385,9 +385,13 @@ SYSCALL_DEFINE3(madvise, unsigned long, 
 	 * ranges, just ignore them, but return -ENOMEM at the end.
 	 * - different from the way of handling in mlock etc.
 	 */
-	vma = find_vma_prev(current->mm, start, &prev);
-	if (vma && start > vma->vm_start)
-		prev = vma;
+	vma = find_vma(current->mm, start);
+	if (vma) {
+		if (start > vma->vm_start)
+			prev = vma;
+		else
+			prev = vma->vm_prev;
+	}
 
 	for (;;) {
 		/* Still start < end. */
Index: linux-3.3-rc6-fast/mm/mempolicy.c
===================================================================
--- linux-3.3-rc6-fast.orig/mm/mempolicy.c	2012-03-06 19:05:38.000000000 +0100
+++ linux-3.3-rc6-fast/mm/mempolicy.c	2012-03-06 19:05:58.000000000 +0100
@@ -640,10 +640,12 @@ static int mbind_range(struct mm_struct 
 	unsigned long vmstart;
 	unsigned long vmend;
 
-	vma = find_vma_prev(mm, start, &prev);
+	vma = find_vma(mm, start);
 	if (!vma || vma->vm_start > start)
 		return -EFAULT;
 
+	prev = vma->vm_prev;
+
 	if (start > vma->vm_start)
 		prev = vma;
 
Index: linux-3.3-rc6-fast/mm/mlock.c
===================================================================
--- linux-3.3-rc6-fast.orig/mm/mlock.c	2012-03-06 19:07:27.000000000 +0100
+++ linux-3.3-rc6-fast/mm/mlock.c	2012-03-06 19:07:50.000000000 +0100
@@ -385,12 +385,14 @@ static int do_mlock(unsigned long start,
 		return -EINVAL;
 	if (end == start)
 		return 0;
-	vma = find_vma_prev(current->mm, start, &prev);
+	vma = find_vma(current->mm, start);
 	if (!vma || vma->vm_start > start)
 		return -ENOMEM;
 
 	if (start > vma->vm_start)
 		prev = vma;
+	else
+		prev = vma->vm_prev;
 
 	for (nstart = start ; ; ) {
 		vm_flags_t newflags;
Index: linux-3.3-rc6-fast/mm/mprotect.c
===================================================================
--- linux-3.3-rc6-fast.orig/mm/mprotect.c	2012-03-06 19:07:57.000000000 +0100
+++ linux-3.3-rc6-fast/mm/mprotect.c	2012-03-06 19:08:37.000000000 +0100
@@ -262,7 +262,7 @@ SYSCALL_DEFINE3(mprotect, unsigned long,
 
 	down_write(&current->mm->mmap_sem);
 
-	vma = find_vma_prev(current->mm, start, &prev);
+	vma = find_vma(current->mm, start);
 	error = -ENOMEM;
 	if (!vma)
 		goto out;
@@ -286,6 +286,8 @@ SYSCALL_DEFINE3(mprotect, unsigned long,
 	}
 	if (start > vma->vm_start)
 		prev = vma;
+	else
+		prev = vma->vm_prev;
 
 	for (nstart = start ; ; ) {
 		unsigned long newflags;

Re: [PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[KOSAKI Motohiro]

(3/6/12 1:57 PM), Mikulas Patocka wrote:
>
>
> On Sun, 4 Mar 2012, Linus Torvalds wrote:
>
>> On Sun, Mar 4, 2012 at 4:52 PM, Mikulas Patocka<mpatocka@redhat.com>  wrote:
>>>
>>> This patch fixes a bug introduced in "mm: simplify find_vma_prev()". You
>>> can apply this, or alternatively revert the original patch.
>>
>> Hmm.
>>
>> I realize the patch is a bug-fix, but I do wonder if we shouldn't look
>> at alternatives.
>>
>> In particular, how about we just change the rule to be clearer, and
>> make the rule be:
>>
>>   - no more find_vma_prev() AT ALL.
>>
>>   - callers get turned into "find_vma()" and then we have a
>> "vma_prev()", which basically does your thing.
>>
>>   - many of the callers seem to be interested in "prev" *only* if they
>> found a vma. For example, the do_mlock() kind of logic seems to be
>> common:
>>
>>      vma = find_vma_prev(current->mm, start,&prev);
>>      if (!vma || vma->vm_start>  start)
>>          return -ENOMEM;
>>
>>     which implies that the current find_vma_prev() semantics are really
>> wrong, because they force us to do extra work in this case where we
>> really really don't care about the result.
>>
>> So we could do an entirely mechanical conversion of
>>
>>     vma = find_vma_prev(mm, address,&prev_vma);
>>
>> into
>>
>>     vma = find_vma(mm, address);
>>     prev_vma = vma_prev(vma);
>>
>> and then after we've done that conversion, it looks like the bulk of
>> them will not care about "prev_vma" if vma is NULL, so they can then
>> be replaced with a pure
>>
>>     prev_vma = vma->vm_prev;
>>
>> instead. Leaving just the (few) cases that may care about the
>> "previous vma may be the last vma of the VM" case.
>>
>> Hmm? And we'd get away from that horrible "find_vma_prev()" interface
>> that uses pointers to vma pointers for return values. Ugh. There only
>> seems to be nine callers in the whole kernel.
>>
>>                   Linus
>
> You can try this to remove most users of find_vma_prev (only three are
> left --- those dealing with up-growing stack). But the patch should be
> delayed until the next merge window.
>
> Mikulas
>

Thank you, Mikulas for finding and fixing the bug. And sorry for the long
delay. I was offlined a while.

Following is the replacing last three caller of find_vma_prev. oh, I use
find_last_vma() instead vma_prev(vma) because parisc need last vma search
when Milulas's original testcase. Does this make sense to you? if yes, we
can remove find_vma_prev() completely.



=========================
Subject: [PATCH] mm: introduce find_last_vma()

Cc: Mikulas Patocka <mpatocka@redhat.com>
Signed-off-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
---
  arch/ia64/mm/fault.c   |   20 +++++++++++++-------
  arch/parisc/mm/fault.c |    6 +++---
  include/linux/mm.h     |    3 +++
  mm/mmap.c              |   32 +++++++++++++++++++++++++++++++-
  4 files changed, 50 insertions(+), 11 deletions(-)

diff --git a/arch/ia64/mm/fault.c b/arch/ia64/mm/fault.c
index 20b3593..27ca30c 100644
--- a/arch/ia64/mm/fault.c
+++ b/arch/ia64/mm/fault.c
@@ -112,18 +112,16 @@ ia64_do_page_fault (unsigned long address, unsigned long isr, struct pt_regs *re
  
  	down_read(&mm->mmap_sem);
  
-	vma = find_vma_prev(mm, address, &prev_vma);
-	if (!vma && !prev_vma )
-		goto bad_area;
+	vma = find_vma(mm, address);
  
-        /*
-         * find_vma_prev() returns vma such that address < vma->vm_end or NULL
+	/*
+         * find_vma() returns vma such that address < vma->vm_end or NULL
           *
           * May find no vma, but could be that the last vm area is the
           * register backing store that needs to expand upwards, in
-         * this case vma will be null, but prev_vma will ne non-null
+         * this case vma will be null and a stack need to be expanded.
           */
-        if (( !vma && prev_vma ) || (address < vma->vm_start) )
+	if (!vma || (address < vma->vm_start))
  		goto check_expansion;
  
    good_area:
@@ -177,6 +175,14 @@ ia64_do_page_fault (unsigned long address, unsigned long isr, struct pt_regs *re
  	return;
  
    check_expansion:
+	if (vma)
+		prev_vma = vma->vm_prev;
+	else {
+		prev_vma = find_last_vma(mm);
+		if (!prev_vma)
+			goto bad_area;
+	}
+
  	if (!(prev_vma && (prev_vma->vm_flags & VM_GROWSUP) && (address == prev_vma->vm_end))) {
  		if (!vma)
  			goto bad_area;
diff --git a/arch/parisc/mm/fault.c b/arch/parisc/mm/fault.c
index 18162ce..7b5a466 100644
--- a/arch/parisc/mm/fault.c
+++ b/arch/parisc/mm/fault.c
@@ -170,7 +170,7 @@ int fixup_exception(struct pt_regs *regs)
  void do_page_fault(struct pt_regs *regs, unsigned long code,
  			      unsigned long address)
  {
-	struct vm_area_struct *vma, *prev_vma;
+	struct vm_area_struct *vma;
  	struct task_struct *tsk = current;
  	struct mm_struct *mm = tsk->mm;
  	unsigned long acc_type;
@@ -180,7 +180,7 @@ void do_page_fault(struct pt_regs *regs, unsigned long code,
  		goto no_context;
  
  	down_read(&mm->mmap_sem);
-	vma = find_vma_prev(mm, address, &prev_vma);
+	vma = find_vma(mm, address);
  	if (!vma || address < vma->vm_start)
  		goto check_expansion;
  /*
@@ -222,7 +222,7 @@ good_area:
  	return;
  
  check_expansion:
-	vma = prev_vma;
+	vma = vma ? vma->vm_prev : find_last_vma(mm);
  	if (vma && (expand_stack(vma, address) == 0))
  		goto good_area;
  
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 17b27cd..d758818 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -1463,6 +1463,9 @@ extern int expand_upwards(struct vm_area_struct *vma, unsigned long address);
  
  /* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
  extern struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr);
+#if defined(CONFIG_STACK_GROWSUP) || defined(CONFIG_IA64)
+extern struct vm_area_struct *find_last_vma(struct mm_struct *mm);
+#endif
  extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
  					     struct vm_area_struct **pprev);
  
diff --git a/mm/mmap.c b/mm/mmap.c
index 22e1a0b..3e9c186 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -1605,6 +1605,32 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
  
  EXPORT_SYMBOL(find_vma);
  
+#if defined(CONFIG_STACK_GROWSUP) || defined(CONFIG_IA64)
+/* Look up the last VMA,  NULL if mm have no vma. */
+struct vm_area_struct *find_last_vma(struct mm_struct *mm)
+{
+	struct vm_area_struct *vma = NULL;
+	struct rb_node *rb_node;
+
+	BUG_ON(!mm);
+
+	rb_node = mm->mm_rb.rb_node;
+	while (rb_node) {
+		vma = rb_entry(rb_node, struct vm_area_struct, vm_rb);
+		rb_node = rb_node->rb_right;
+	}
+
+	/*
+	 * This function is mainly used for a page fault. Thus recording vma
+	 * may improve the performance.
+	 */
+	if (vma)
+		mm->mmap_cache = vma;
+
+	return vma;
+}
+#endif
+
  /*
   * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
   * Note: pprev is set to NULL when return value is NULL.
@@ -1789,9 +1815,13 @@ find_extend_vma(struct mm_struct *mm, unsigned long addr)
  	struct vm_area_struct *vma, *prev;
  
  	addr &= PAGE_MASK;
-	vma = find_vma_prev(mm, addr, &prev);
+	vma = find_vma(mm, addr);
  	if (vma && (vma->vm_start <= addr))
  		return vma;
+
+	prev = vma->vm_prev;
+	if (!prev)
+		prev = find_last_vma(mm);
  	if (!prev || expand_stack(prev, addr))
  		return NULL;
  	if (prev->vm_flags & VM_LOCKED) {
-- 
1.7.1

Re: [PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[KOSAKI Motohiro]

(3/4/12 7:52 PM), Mikulas Patocka wrote:
> Hi
>
> This patch fixes a bug introduced in "mm: simplify find_vma_prev()". You
> can apply this, or alternatively revert the original patch.
>
> Mikulas
>
> ---
>
> mm: fix find_vma_prev
>
> The commit mm: simplify find_vma_prev()
> [6bd4837de96e7d9f9bf33e59117c24fc230862ac] broke memory management on PA-RISC.
>
> After application of the patch, programs that allocate big arrays on the stack
> crash with segfault, for example, this will crash if compiled without
> optimization:
> int main()
> {
> 	char array[200000];
> 	array[199999] = 0;
> 	return 0;
> }
>
> The reason is that PA-RISC has up-growing stack and the stack is usually the
> last memory area. In the above example, a page fault happens above the stack.
>
> Previously, if we passed too high address to find_vma_prev, it returned NULL
> and stored the last VMA in *pprev. After "simplify find_vma_prev" change, it
> stores NULL in *pprev. Consequently, the stack area is not found and it is
> not expanded, as it used to be before the change.
>
> This patch restores the old behavior and makes it return the last VMA in *pprev
> if the requested address is higher than address of any other VMA.
>
> Signed-off-by: Mikulas Patocka<mpatocka@redhat.com>

Acked-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>


I prefer to remove find_vma_prev() eventually. but this is good short term solution.

Re: [PATCH] fix bug introduced in "mm: simplify find_vma_prev()"

[Linus Torvalds]

On Tue, Mar 6, 2012 at 4:30 PM, KOSAKI Motohiro
<kosaki.motohiro@gmail.com> wrote:
>
> Acked-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com>
>
> I prefer to remove find_vma_prev() eventually. but this is good short term
> solution.

Ok, applied.

And then I committed an extra patch that removed the really obvious
cases of find_vma_prev() (ie where it immediately returns if the
resulting "vma" is NULL.

There may well be a few more cases that really only need find_vma(),
but if it wasn't totally obvious from the grep output with just a
couple of lines of context, I left it alone for now.

                Linus