[RFC/RFT 0/6] nommu: improve the vma list handling

[RFC/RFT 0/6] nommu: improve the vma list handling

[Namhyung Kim]

Hello,

When I was reading nommu code, I found that it handles the vma list/tree in
an unusual way. IIUC, because there can be more than one identical/overrapped
vmas in the list/tree, it sorts the tree more strictly and does a linear
search on the tree. But it doesn't applied to the list (i.e. the list could
be constructed in a different order than the tree so that we can't use the
list when finding the first vma in that order).

Since inserting/sorting a vma in the tree and link is done at the same time,
we can easily construct both of them in the same order. And linear searching
on the tree could be more costly than doing it on the list, it can be
converted to use the list.

Also, after the commit 297c5eee3724 ("mm: make the vma list be doubly linked")
made the list be doubly linked, there were a couple of code need to be fixed
to construct the list properly.

Patch 1/6 is a preparation. It maintains the list sorted same as the tree and
construct doubly-linked list properly. Patch 2/6 is a simple optimization for
the vma deletion. Patch 3/6 and 4/6 convert tree traversal to list traversal
and the rest are simple fixes and cleanups.

Note that I don't have a system to test on, so these are *totally untested*
patches. There could be some basic errors in the code. In that case, please
kindly let me know. :)

Anyway, I just compiled them on my x86_64 desktop using this command:

  make mm/nommu.o

(Of course this required few of dirty-fixes to proceed)

Also note that these are on top of v2.6.38.

Any comments are welcome.

Thanks.


---
Namhyung Kim (6):
  nommu: sort mm->mmap list properly
  nommu: don't scan the vma list when deleting
  nommu: find vma using the sorted vma list
  nommu: check the vma list when unmapping file-mapped vma
  nommu: fix a potential memory leak in do_mmap_private()
  nommu: fix a compile warning in do_mmap_pgoff()

 mm/nommu.c |  103 +++++++++++++++++++++++++++++++++--------------------------
 1 files changed, 58 insertions(+), 45 deletions(-)

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

[PATCH 1/6] nommu: sort mm->mmap list properly

[Namhyung Kim]

@vma added into @mm should be sorted by start addr, end addr and VMA struct
addr in that order because we may get identical VMAs in the @mm. However
this was true only for the rbtree, not for the list.

This patch fixes this by remembering 'rb_prev' during the tree traversal
like find_vma_prepare() does and linking the @vma via __vma_link_list().
After this patch, we can iterate the whole VMAs in correct order simply
by using @mm->mmap list.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |   62 ++++++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 40 insertions(+), 22 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index e7dbd3fae187..20d9c330eb0e 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -672,6 +672,30 @@ static void protect_vma(struct vm_area_struct *vma, unsigned long flags)
 #endif
 }
 
+/* borrowed from mm/mmap.c */
+static inline void
+__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
+		struct vm_area_struct *prev, struct rb_node *rb_parent)
+{
+	struct vm_area_struct *next;
+
+	vma->vm_prev = prev;
+	if (prev) {
+		next = prev->vm_next;
+		prev->vm_next = vma;
+	} else {
+		mm->mmap = vma;
+		if (rb_parent)
+			next = rb_entry(rb_parent,
+					struct vm_area_struct, vm_rb);
+		else
+			next = NULL;
+	}
+	vma->vm_next = next;
+	if (next)
+		next->vm_prev = vma;
+}
+
 /*
  * add a VMA into a process's mm_struct in the appropriate place in the list
  * and tree and add to the address space's page tree also if not an anonymous
@@ -680,9 +704,9 @@ static void protect_vma(struct vm_area_struct *vma, unsigned long flags)
  */
 static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 {
-	struct vm_area_struct *pvma, **pp, *next;
+	struct vm_area_struct *pvma, *prev;
 	struct address_space *mapping;
-	struct rb_node **p, *parent;
+	struct rb_node **p, *parent, *rb_prev;
 
 	kenter(",%p", vma);
 
@@ -703,7 +727,7 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 	}
 
 	/* add the VMA to the tree */
-	parent = NULL;
+	parent = rb_prev = NULL;
 	p = &mm->mm_rb.rb_node;
 	while (*p) {
 		parent = *p;
@@ -713,17 +737,20 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 		 * (the latter is necessary as we may get identical VMAs) */
 		if (vma->vm_start < pvma->vm_start)
 			p = &(*p)->rb_left;
-		else if (vma->vm_start > pvma->vm_start)
+		else if (vma->vm_start > pvma->vm_start) {
+			rb_prev = parent;
 			p = &(*p)->rb_right;
-		else if (vma->vm_end < pvma->vm_end)
+		} else if (vma->vm_end < pvma->vm_end)
 			p = &(*p)->rb_left;
-		else if (vma->vm_end > pvma->vm_end)
+		else if (vma->vm_end > pvma->vm_end) {
+			rb_prev = parent;
 			p = &(*p)->rb_right;
-		else if (vma < pvma)
+		} else if (vma < pvma)
 			p = &(*p)->rb_left;
-		else if (vma > pvma)
+		else if (vma > pvma) {
+			rb_prev = parent;
 			p = &(*p)->rb_right;
-		else
+		} else
 			BUG();
 	}
 
@@ -731,20 +758,11 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 	rb_insert_color(&vma->vm_rb, &mm->mm_rb);
 
 	/* add VMA to the VMA list also */
-	for (pp = &mm->mmap; (pvma = *pp); pp = &(*pp)->vm_next) {
-		if (pvma->vm_start > vma->vm_start)
-			break;
-		if (pvma->vm_start < vma->vm_start)
-			continue;
-		if (pvma->vm_end < vma->vm_end)
-			break;
-	}
+	prev = NULL;
+	if (rb_prev)
+		prev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
 
-	next = *pp;
-	*pp = vma;
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
+	__vma_link_list(mm, vma, prev, parent);
 }
 
 /*
-- 
1.7.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/ .
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 1/6] nommu: sort mm->mmap list properly

[Andrew Morton]

On Mon, 28 Mar 2011 22:56:42 +0900
Namhyung Kim <namhyung@gmail.com> wrote:

> @vma added into @mm should be sorted by start addr, end addr and VMA struct
> addr in that order because we may get identical VMAs in the @mm. However
> this was true only for the rbtree, not for the list.
> 
> This patch fixes this by remembering 'rb_prev' during the tree traversal
> like find_vma_prepare() does and linking the @vma via __vma_link_list().
> After this patch, we can iterate the whole VMAs in correct order simply
> by using @mm->mmap list.
> 
> Signed-off-by: Namhyung Kim <namhyung@gmail.com>
> ---
>  mm/nommu.c |   62 ++++++++++++++++++++++++++++++++++++++---------------------
>  1 files changed, 40 insertions(+), 22 deletions(-)
> 
> diff --git a/mm/nommu.c b/mm/nommu.c
> index e7dbd3fae187..20d9c330eb0e 100644
> --- a/mm/nommu.c
> +++ b/mm/nommu.c
> @@ -672,6 +672,30 @@ static void protect_vma(struct vm_area_struct *vma, unsigned long flags)
>  #endif
>  }
>  
> +/* borrowed from mm/mmap.c */
> +static inline void
> +__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> +		struct vm_area_struct *prev, struct rb_node *rb_parent)
> +{
> +	struct vm_area_struct *next;
> +
> +	vma->vm_prev = prev;
> +	if (prev) {
> +		next = prev->vm_next;
> +		prev->vm_next = vma;
> +	} else {
> +		mm->mmap = vma;
> +		if (rb_parent)
> +			next = rb_entry(rb_parent,
> +					struct vm_area_struct, vm_rb);
> +		else
> +			next = NULL;
> +	}
> +	vma->vm_next = next;
> +	if (next)
> +		next->vm_prev = vma;
> +}

Duplicating code is rather bad.  And putting random vma functions into
mm/util.c is pretty ugly too, but I suppose it's less bad.

 mm/internal.h |    4 ++++
 mm/mmap.c     |   22 ----------------------
 mm/nommu.c    |   24 ------------------------
 mm/util.c     |   24 ++++++++++++++++++++++++
 4 files changed, 28 insertions(+), 46 deletions(-)

diff -puN mm/nommu.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/nommu.c
--- a/mm/nommu.c~mm-nommu-sort-mm-mmap-list-properly-fix
+++ a/mm/nommu.c
@@ -672,30 +672,6 @@ static void protect_vma(struct vm_area_s
 #endif
 }
 
-/* borrowed from mm/mmap.c */
-static inline void
-__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev, struct rb_node *rb_parent)
-{
-	struct vm_area_struct *next;
-
-	vma->vm_prev = prev;
-	if (prev) {
-		next = prev->vm_next;
-		prev->vm_next = vma;
-	} else {
-		mm->mmap = vma;
-		if (rb_parent)
-			next = rb_entry(rb_parent,
-					struct vm_area_struct, vm_rb);
-		else
-			next = NULL;
-	}
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
-}
-
 /*
  * add a VMA into a process's mm_struct in the appropriate place in the list
  * and tree and add to the address space's page tree also if not an anonymous
diff -puN mm/util.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/util.c
--- a/mm/util.c~mm-nommu-sort-mm-mmap-list-properly-fix
+++ a/mm/util.c
@@ -6,6 +6,8 @@
 #include <linux/sched.h>
 #include <asm/uaccess.h>
 
+#include "internal.h"
+
 #define CREATE_TRACE_POINTS
 #include <trace/events/kmem.h>
 
@@ -215,6 +217,28 @@ char *strndup_user(const char __user *s,
 }
 EXPORT_SYMBOL(strndup_user);
 
+void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
+		struct vm_area_struct *prev, struct rb_node *rb_parent)
+{
+	struct vm_area_struct *next;
+
+	vma->vm_prev = prev;
+	if (prev) {
+		next = prev->vm_next;
+		prev->vm_next = vma;
+	} else {
+		mm->mmap = vma;
+		if (rb_parent)
+			next = rb_entry(rb_parent,
+					struct vm_area_struct, vm_rb);
+		else
+			next = NULL;
+	}
+	vma->vm_next = next;
+	if (next)
+		next->vm_prev = vma;
+}
+
 #if defined(CONFIG_MMU) && !defined(HAVE_ARCH_PICK_MMAP_LAYOUT)
 void arch_pick_mmap_layout(struct mm_struct *mm)
 {
diff -puN mm/internal.h~mm-nommu-sort-mm-mmap-list-properly-fix mm/internal.h
--- a/mm/internal.h~mm-nommu-sort-mm-mmap-list-properly-fix
+++ a/mm/internal.h
@@ -66,6 +66,10 @@ static inline unsigned long page_order(s
 	return page_private(page);
 }
 
+/* mm/util.c */
+void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
+		struct vm_area_struct *prev, struct rb_node *rb_parent);
+
 #ifdef CONFIG_MMU
 extern long mlock_vma_pages_range(struct vm_area_struct *vma,
 			unsigned long start, unsigned long end);
diff -puN mm/mmap.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/mmap.c
--- a/mm/mmap.c~mm-nommu-sort-mm-mmap-list-properly-fix
+++ a/mm/mmap.c
@@ -398,28 +398,6 @@ find_vma_prepare(struct mm_struct *mm, u
 	return vma;
 }
 
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev, struct rb_node *rb_parent)
-{
-	struct vm_area_struct *next;
-
-	vma->vm_prev = prev;
-	if (prev) {
-		next = prev->vm_next;
-		prev->vm_next = vma;
-	} else {
-		mm->mmap = vma;
-		if (rb_parent)
-			next = rb_entry(rb_parent,
-					struct vm_area_struct, vm_rb);
-		else
-			next = NULL;
-	}
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
-}
-
 void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
 		struct rb_node **rb_link, struct rb_node *rb_parent)
 {
_


--
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 1/6] nommu: sort mm->mmap list properly

[Namhyung Kim]

2011-03-31 (ea(C)), 11:51 -0700, Andrew Morton:
> On Mon, 28 Mar 2011 22:56:42 +0900
> Namhyung Kim <namhyung@gmail.com> wrote:
> 
> > @vma added into @mm should be sorted by start addr, end addr and VMA struct
> > addr in that order because we may get identical VMAs in the @mm. However
> > this was true only for the rbtree, not for the list.
> > 
> > This patch fixes this by remembering 'rb_prev' during the tree traversal
> > like find_vma_prepare() does and linking the @vma via __vma_link_list().
> > After this patch, we can iterate the whole VMAs in correct order simply
> > by using @mm->mmap list.
> > 
> > Signed-off-by: Namhyung Kim <namhyung@gmail.com>
> > ---
> >  mm/nommu.c |   62 ++++++++++++++++++++++++++++++++++++++---------------------
> >  1 files changed, 40 insertions(+), 22 deletions(-)
> > 
> > diff --git a/mm/nommu.c b/mm/nommu.c
> > index e7dbd3fae187..20d9c330eb0e 100644
> > --- a/mm/nommu.c
> > +++ b/mm/nommu.c
> > @@ -672,6 +672,30 @@ static void protect_vma(struct vm_area_struct *vma, unsigned long flags)
> >  #endif
> >  }
> >  
> > +/* borrowed from mm/mmap.c */
> > +static inline void
> > +__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> > +		struct vm_area_struct *prev, struct rb_node *rb_parent)
> > +{
> > +	struct vm_area_struct *next;
> > +
> > +	vma->vm_prev = prev;
> > +	if (prev) {
> > +		next = prev->vm_next;
> > +		prev->vm_next = vma;
> > +	} else {
> > +		mm->mmap = vma;
> > +		if (rb_parent)
> > +			next = rb_entry(rb_parent,
> > +					struct vm_area_struct, vm_rb);
> > +		else
> > +			next = NULL;
> > +	}
> > +	vma->vm_next = next;
> > +	if (next)
> > +		next->vm_prev = vma;
> > +}
> 
> Duplicating code is rather bad.  And putting random vma functions into
> mm/util.c is pretty ugly too, but I suppose it's less bad.
> 

Agreed. Thanks for doing this.


>  mm/internal.h |    4 ++++
>  mm/mmap.c     |   22 ----------------------
>  mm/nommu.c    |   24 ------------------------
>  mm/util.c     |   24 ++++++++++++++++++++++++
>  4 files changed, 28 insertions(+), 46 deletions(-)
> 
> diff -puN mm/nommu.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/nommu.c
> --- a/mm/nommu.c~mm-nommu-sort-mm-mmap-list-properly-fix
> +++ a/mm/nommu.c
> @@ -672,30 +672,6 @@ static void protect_vma(struct vm_area_s
>  #endif
>  }
>  
> -/* borrowed from mm/mmap.c */
> -static inline void
> -__vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> -		struct vm_area_struct *prev, struct rb_node *rb_parent)
> -{
> -	struct vm_area_struct *next;
> -
> -	vma->vm_prev = prev;
> -	if (prev) {
> -		next = prev->vm_next;
> -		prev->vm_next = vma;
> -	} else {
> -		mm->mmap = vma;
> -		if (rb_parent)
> -			next = rb_entry(rb_parent,
> -					struct vm_area_struct, vm_rb);
> -		else
> -			next = NULL;
> -	}
> -	vma->vm_next = next;
> -	if (next)
> -		next->vm_prev = vma;
> -}
> -
>  /*
>   * add a VMA into a process's mm_struct in the appropriate place in the list
>   * and tree and add to the address space's page tree also if not an anonymous
> diff -puN mm/util.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/util.c
> --- a/mm/util.c~mm-nommu-sort-mm-mmap-list-properly-fix
> +++ a/mm/util.c
> @@ -6,6 +6,8 @@
>  #include <linux/sched.h>
>  #include <asm/uaccess.h>
>  
> +#include "internal.h"
> +
>  #define CREATE_TRACE_POINTS
>  #include <trace/events/kmem.h>
>  
> @@ -215,6 +217,28 @@ char *strndup_user(const char __user *s,
>  }
>  EXPORT_SYMBOL(strndup_user);
>  
> +void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> +		struct vm_area_struct *prev, struct rb_node *rb_parent)
> +{
> +	struct vm_area_struct *next;
> +
> +	vma->vm_prev = prev;
> +	if (prev) {
> +		next = prev->vm_next;
> +		prev->vm_next = vma;
> +	} else {
> +		mm->mmap = vma;
> +		if (rb_parent)
> +			next = rb_entry(rb_parent,
> +					struct vm_area_struct, vm_rb);
> +		else
> +			next = NULL;
> +	}
> +	vma->vm_next = next;
> +	if (next)
> +		next->vm_prev = vma;
> +}
> +
>  #if defined(CONFIG_MMU) && !defined(HAVE_ARCH_PICK_MMAP_LAYOUT)
>  void arch_pick_mmap_layout(struct mm_struct *mm)
>  {
> diff -puN mm/internal.h~mm-nommu-sort-mm-mmap-list-properly-fix mm/internal.h
> --- a/mm/internal.h~mm-nommu-sort-mm-mmap-list-properly-fix
> +++ a/mm/internal.h
> @@ -66,6 +66,10 @@ static inline unsigned long page_order(s
>  	return page_private(page);
>  }
>  
> +/* mm/util.c */
> +void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> +		struct vm_area_struct *prev, struct rb_node *rb_parent);
> +
>  #ifdef CONFIG_MMU
>  extern long mlock_vma_pages_range(struct vm_area_struct *vma,
>  			unsigned long start, unsigned long end);
> diff -puN mm/mmap.c~mm-nommu-sort-mm-mmap-list-properly-fix mm/mmap.c
> --- a/mm/mmap.c~mm-nommu-sort-mm-mmap-list-properly-fix
> +++ a/mm/mmap.c
> @@ -398,28 +398,6 @@ find_vma_prepare(struct mm_struct *mm, u
>  	return vma;
>  }
>  
> -void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
> -		struct vm_area_struct *prev, struct rb_node *rb_parent)
> -{
> -	struct vm_area_struct *next;
> -
> -	vma->vm_prev = prev;
> -	if (prev) {
> -		next = prev->vm_next;
> -		prev->vm_next = vma;
> -	} else {
> -		mm->mmap = vma;
> -		if (rb_parent)
> -			next = rb_entry(rb_parent,
> -					struct vm_area_struct, vm_rb);
> -		else
> -			next = NULL;
> -	}
> -	vma->vm_next = next;
> -	if (next)
> -		next->vm_prev = vma;
> -}
> -
>  void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
>  		struct rb_node **rb_link, struct rb_node *rb_parent)
>  {
> _
> 
> 


-- 
Regards,
Namhyung 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>

[PATCH 2/6] nommu: don't scan the vma list when deleting

[Namhyung Kim]

Since the commit 297c5eee3724 ("mm: make the vma list be doubly linked")
made it a doubly linked list, we don't need to scan the list when
deleting @vma.

And the original code didn't update the prev pointer. Fix it too.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |   15 ++++++++-------
 1 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index 20d9c330eb0e..a6a073f0745a 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -770,7 +770,6 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
  */
 static void delete_vma_from_mm(struct vm_area_struct *vma)
 {
-	struct vm_area_struct **pp;
 	struct address_space *mapping;
 	struct mm_struct *mm = vma->vm_mm;
 
@@ -793,12 +792,14 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
 	/* remove from the MM's tree and list */
 	rb_erase(&vma->vm_rb, &mm->mm_rb);
-	for (pp = &mm->mmap; *pp; pp = &(*pp)->vm_next) {
-		if (*pp == vma) {
-			*pp = vma->vm_next;
-			break;
-		}
-	}
+
+	if (vma->vm_prev)
+		vma->vm_prev->vm_next = vma->vm_next;
+	else
+		mm->mmap = vma->vm_next;
+
+	if (vma->vm_next)
+		vma->vm_next->vm_prev = vma->vm_prev;
 
 	vma->vm_mm = NULL;
 }
-- 
1.7.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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 3/6] nommu: find vma using the sorted vma list

[Namhyung Kim]

Now we have the sorted vma list, use it in the find_vma[_exact]()
rather than doing linear search on the rb-tree.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |   12 ++++--------
 1 files changed, 4 insertions(+), 8 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index a6a073f0745a..6c5a13b507b4 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -828,17 +828,15 @@ static void delete_vma(struct mm_struct *mm, struct vm_area_struct *vma)
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
 	struct vm_area_struct *vma;
-	struct rb_node *n = mm->mm_rb.rb_node;
 
 	/* check the cache first */
 	vma = mm->mmap_cache;
 	if (vma && vma->vm_start <= addr && vma->vm_end > addr)
 		return vma;
 
-	/* trawl the tree (there may be multiple mappings in which addr
+	/* trawl the list (there may be multiple mappings in which addr
 	 * resides) */
-	for (n = rb_first(&mm->mm_rb); n; n = rb_next(n)) {
-		vma = rb_entry(n, struct vm_area_struct, vm_rb);
+	for (vma = mm->mmap; vma; vma = vma->vm_next) {
 		if (vma->vm_start > addr)
 			return NULL;
 		if (vma->vm_end > addr) {
@@ -878,7 +876,6 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 					     unsigned long len)
 {
 	struct vm_area_struct *vma;
-	struct rb_node *n = mm->mm_rb.rb_node;
 	unsigned long end = addr + len;
 
 	/* check the cache first */
@@ -886,10 +883,9 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 	if (vma && vma->vm_start == addr && vma->vm_end == end)
 		return vma;
 
-	/* trawl the tree (there may be multiple mappings in which addr
+	/* trawl the list (there may be multiple mappings in which addr
 	 * resides) */
-	for (n = rb_first(&mm->mm_rb); n; n = rb_next(n)) {
-		vma = rb_entry(n, struct vm_area_struct, vm_rb);
+	for (vma = mm->mmap; vma; vma = vma->vm_next) {
 		if (vma->vm_start < addr)
 			continue;
 		if (vma->vm_start > addr)
-- 
1.7.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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 4/6] nommu: check the vma list when unmapping file-mapped vma

[Namhyung Kim]

Now we have the sorted vma list, use it in do_munmap() to check that
we have an exact match.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |    6 ++----
 1 files changed, 2 insertions(+), 4 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index 6c5a13b507b4..33f5d23c6d44 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -1659,7 +1659,6 @@ static int shrink_vma(struct mm_struct *mm,
 int do_munmap(struct mm_struct *mm, unsigned long start, size_t len)
 {
 	struct vm_area_struct *vma;
-	struct rb_node *rb;
 	unsigned long end = start + len;
 	int ret;
 
@@ -1692,9 +1691,8 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len)
 			}
 			if (end == vma->vm_end)
 				goto erase_whole_vma;
-			rb = rb_next(&vma->vm_rb);
-			vma = rb_entry(rb, struct vm_area_struct, vm_rb);
-		} while (rb);
+			vma = vma->vm_next;
+		} while (vma);
 		kleave(" = -EINVAL [split file]");
 		return -EINVAL;
 	} else {
-- 
1.7.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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 5/6] nommu: fix a potential memory leak in do_mmap_private()

[Namhyung Kim]

If f_op->read() fails and sysctl_nr_trim_pages > 1, there could be a
memory leak between @region->vm_end and @region->vm_top.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index 33f5d23c6d44..662fd46449a6 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -1241,7 +1241,7 @@ static int do_mmap_private(struct vm_area_struct *vma,
 	return 0;
 
 error_free:
-	free_page_series(region->vm_start, region->vm_end);
+	free_page_series(region->vm_start, region->vm_top);
 	region->vm_start = vma->vm_start = 0;
 	region->vm_end   = vma->vm_end = 0;
 	region->vm_top   = 0;
-- 
1.7.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/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[PATCH 6/6] nommu: fix a compile warning in do_mmap_pgoff()

[Namhyung Kim]

Because 'ret' is declared as int, not unsigned long, no need to cast the
error contants into unsigned long. If you compile this code on a 64-bit
machine somehow, you'll see following warning:

  CC      mm/nommu.o
mm/nommu.c: In function a??do_mmap_pgoffa??:
mm/nommu.c:1411: warning: overflow in implicit constant conversion

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 mm/nommu.c |    6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/mm/nommu.c b/mm/nommu.c
index 662fd46449a6..c7af249076ac 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -1400,15 +1400,15 @@ unsigned long do_mmap_pgoff(struct file *file,
 		if (capabilities & BDI_CAP_MAP_DIRECT) {
 			addr = file->f_op->get_unmapped_area(file, addr, len,
 							     pgoff, flags);
-			if (IS_ERR((void *) addr)) {
+			if (IS_ERR_VALUE(addr)) {
 				ret = addr;
-				if (ret != (unsigned long) -ENOSYS)
+				if (ret != -ENOSYS)
 					goto error_just_free;
 
 				/* the driver refused to tell us where to site
 				 * the mapping so we'll have to attempt to copy
 				 * it */
-				ret = (unsigned long) -ENODEV;
+				ret = -ENODEV;
 				if (!(capabilities & BDI_CAP_MAP_COPY))
 					goto error_just_free;
 
-- 
1.7.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/ .
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: [RFC/RFT 0/6] nommu: improve the vma list handling

[Andrew Morton]

On Mon, 28 Mar 2011 22:56:41 +0900
Namhyung Kim <namhyung@gmail.com> wrote:

> When I was reading nommu code, I found that it handles the vma list/tree in
> an unusual way. IIUC, because there can be more than one identical/overrapped
> vmas in the list/tree, it sorts the tree more strictly and does a linear
> search on the tree. But it doesn't applied to the list (i.e. the list could
> be constructed in a different order than the tree so that we can't use the
> list when finding the first vma in that order).
> 
> Since inserting/sorting a vma in the tree and link is done at the same time,
> we can easily construct both of them in the same order. And linear searching
> on the tree could be more costly than doing it on the list, it can be
> converted to use the list.
> 
> Also, after the commit 297c5eee3724 ("mm: make the vma list be doubly linked")
> made the list be doubly linked, there were a couple of code need to be fixed
> to construct the list properly.
> 
> Patch 1/6 is a preparation. It maintains the list sorted same as the tree and
> construct doubly-linked list properly. Patch 2/6 is a simple optimization for
> the vma deletion. Patch 3/6 and 4/6 convert tree traversal to list traversal
> and the rest are simple fixes and cleanups.
> 
> Note that I don't have a system to test on, so these are *totally untested*
> patches. There could be some basic errors in the code. In that case, please
> kindly let me know. :)
> 
> Anyway, I just compiled them on my x86_64 desktop using this command:
> 
>   make mm/nommu.o
> 
> (Of course this required few of dirty-fixes to proceed)
> 
> Also note that these are on top of v2.6.38.
> 
> Any comments are welcome.

That seems like a nice set of changes.  There isn't much I can do with
them at this tims - hopefully some of the nommu people will be able to
find time to review and test the patches.  

(Is there a way in which one can run a nommu kernel on a regular PC?  Under
an emulator?)

--
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: [RFC/RFT 0/6] nommu: improve the vma list handling

[Greg Ungerer]

On 29/03/11 08:01, Andrew Morton wrote:
> On Mon, 28 Mar 2011 22:56:41 +0900
> Namhyung Kim<namhyung@gmail.com>  wrote:
>
>> When I was reading nommu code, I found that it handles the vma list/tree in
>> an unusual way. IIUC, because there can be more than one identical/overrapped
>> vmas in the list/tree, it sorts the tree more strictly and does a linear
>> search on the tree. But it doesn't applied to the list (i.e. the list could
>> be constructed in a different order than the tree so that we can't use the
>> list when finding the first vma in that order).
>>
>> Since inserting/sorting a vma in the tree and link is done at the same time,
>> we can easily construct both of them in the same order. And linear searching
>> on the tree could be more costly than doing it on the list, it can be
>> converted to use the list.
>>
>> Also, after the commit 297c5eee3724 ("mm: make the vma list be doubly linked")
>> made the list be doubly linked, there were a couple of code need to be fixed
>> to construct the list properly.
>>
>> Patch 1/6 is a preparation. It maintains the list sorted same as the tree and
>> construct doubly-linked list properly. Patch 2/6 is a simple optimization for
>> the vma deletion. Patch 3/6 and 4/6 convert tree traversal to list traversal
>> and the rest are simple fixes and cleanups.
>>
>> Note that I don't have a system to test on, so these are *totally untested*
>> patches. There could be some basic errors in the code. In that case, please
>> kindly let me know. :)
>>
>> Anyway, I just compiled them on my x86_64 desktop using this command:
>>
>>    make mm/nommu.o
>>
>> (Of course this required few of dirty-fixes to proceed)
>>
>> Also note that these are on top of v2.6.38.
>>
>> Any comments are welcome.
>
> That seems like a nice set of changes.  There isn't much I can do with
> them at this tims - hopefully some of the nommu people will be able to
> find time to review and test the patches.

That does seem like a nice set of changes. I have compiled and run
tested on my ColdFire non-mmu targets, and it looks good.

So for the whole series from me that is:

Acked-by: Greg Ungerer <gerg@uclinux>


> (Is there a way in which one can run a nommu kernel on a regular PC?  Under
> an emulator?)

There is some around. Though none I have used I could recommend
off hand. I have used Skyeye for emulating non-mmu ARM on a PC,
but the mainline kernel lacks a serial driver for console on that
(limiting its current usefullnedd quite a bit).

I ran the freely available ColdFire one many years ago, bu I haven't
tried it recently.

Regards
Greg


------------------------------------------------------------------------
Greg Ungerer  --  Principal Engineer        EMAIL:     gerg@snapgear.com
SnapGear Group, McAfee                      PHONE:       +61 7 3435 2888
8 Gardner Close                             FAX:         +61 7 3217 5323
Milton, QLD, 4064, Australia                WEB: http://www.SnapGear.com

--
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>