[PATCH] find_vma_prev rewrite

[PATCH] find_vma_prev rewrite

[Matthew Wilcox]

find_vma_prev doesn't return a pointer to the `prev' vma if the address
is greater than the last existing vma.  This doesn't matter unless you're
on a PA-RISC machine :-)

This rewrite should speed up & make find_vma_prev simpler, as well as
fixing the previous behaviour.

--- linux-t10/mm/mmap.c	Fri Oct 13 20:10:30 2000
+++ linux-mine/mm/mmap.c	Wed Dec 20 15:22:53 2000
@@ -417,54 +417,48 @@
 struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
 				      struct vm_area_struct **pprev)
 {
-	if (mm) {
-		if (!mm->mmap_avl) {
-			/* Go through the linear list. */
-			struct vm_area_struct * prev = NULL;
-			struct vm_area_struct * vma = mm->mmap;
-			while (vma && vma->vm_end <= addr) {
-				prev = vma;
-				vma = vma->vm_next;
-			}
-			*pprev = prev;
-			return vma;
-		} else {
-			/* Go through the AVL tree quickly. */
-			struct vm_area_struct * vma = NULL;
-			struct vm_area_struct * last_turn_right = NULL;
-			struct vm_area_struct * prev = NULL;
-			struct vm_area_struct * tree = mm->mmap_avl;
-			for (;;) {
-				if (tree == vm_avl_empty)
+	struct vm_area_struct *vma = NULL;
+	struct vm_area_struct *prev = NULL;
+	if (!mm)
+		goto out;
+	prev = mm->mmap_cache;
+	if (prev) {
+		vma = prev->vm_next;
+		if (prev->vm_end < addr &&
+				((vma == NULL) || (addr < vma->vm_end)))
+			goto out;
+		prev = NULL;
+	}
+	vma = mm->mmap; /* guard against there being no prev */
+	if (!mm->mmap_avl) {
+		/* Go through the linear list. */
+		while (vma && vma->vm_end <= addr) {
+			prev = vma;
+			vma = vma->vm_next;
+		}
+	} else {
+		/* Go through the AVL tree quickly. */
+		struct vm_area_struct * tree = mm->mmap_avl;
+		while (tree != vm_avl_empty) {
+			if (addr < tree->vm_end) {
+				tree = tree->vm_avl_left;
+			} else {
+				prev = tree;
+				if (tree->vm_next == NULL)
 					break;
-				if (tree->vm_end > addr) {
-					vma = tree;
-					prev = last_turn_right;
-					if (tree->vm_start <= addr)
-						break;
-					tree = tree->vm_avl_left;
-				} else {
-					last_turn_right = tree;
-					tree = tree->vm_avl_right;
-				}
-			}
-			if (vma) {
-				if (vma->vm_avl_left != vm_avl_empty) {
-					prev = vma->vm_avl_left;
-					while (prev->vm_avl_right != vm_avl_empty)
-						prev = prev->vm_avl_right;
-				}
-				if ((prev ? prev->vm_next : mm->mmap) != vma)
-					printk("find_vma_prev: tree inconsistent with list\n");
-				*pprev = prev;
-				return vma;
+				if (addr < tree->vm_next->vm_end)
+					break;
+				tree = tree->vm_avl_right;
 			}
 		}
 	}
-	*pprev = NULL;
-	return NULL;
+	mm->mmap_cache = prev;
+out:
+	*pprev = prev;
+	return prev ? prev->vm_next : vma;
 }
 
+/* XXX: Needs to be fixed for PA-RISC -- won't grow our stack. */
 struct vm_area_struct * find_extend_vma(struct mm_struct * mm, unsigned long addr)
 {
 	struct vm_area_struct * vma;

-- 
Revolutions do not require corporate support.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

[PATCH] find_vma_prev rewrite

[Matthew Wilcox]

I've been sending patches like this for over 18 months now with
no comments.  I'm sending it to Linus early next week.  It benefits
ia64's fault handler path and is required for PA-RISC's fault handler.
It works, it's tested.  I realise this puts it in a very different class
from the kind of VM patches which are allowed in a stable kernel tree.

There's also a chunk after find_vma_prev which adds an implementation
of find_extend_vma for machines with stacks which grow up.  I couldn't
be bothered to split it out, since it won't affect any other architecture.

diff -urNX dontdiff linux-2.5.24/mm/mmap.c linux-2.5.24-mm/mm/mmap.c
--- linux-2.5.24/mm/mmap.c	Thu Jun 20 16:53:43 2002
+++ linux-2.5.24-mm/mm/mmap.c	Thu Jun 27 07:35:55 2002
@@ -669,49 +669,53 @@
 struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
 				      struct vm_area_struct **pprev)
 {
-	if (mm) {
-		/* Go through the RB tree quickly. */
-		struct vm_area_struct * vma;
-		rb_node_t * rb_node, * rb_last_right, * rb_prev;
-		
-		rb_node = mm->mm_rb.rb_node;
-		rb_last_right = rb_prev = NULL;
-		vma = NULL;
-
-		while (rb_node) {
-			struct vm_area_struct * vma_tmp;
-
-			vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
-
-			if (vma_tmp->vm_end > addr) {
-				vma = vma_tmp;
-				rb_prev = rb_last_right;
-				if (vma_tmp->vm_start <= addr)
-					break;
-				rb_node = rb_node->rb_left;
-			} else {
-				rb_last_right = rb_node;
-				rb_node = rb_node->rb_right;
-			}
-		}
-		if (vma) {
-			if (vma->vm_rb.rb_left) {
-				rb_prev = vma->vm_rb.rb_left;
-				while (rb_prev->rb_right)
-					rb_prev = rb_prev->rb_right;
-			}
-			*pprev = NULL;
-			if (rb_prev)
-				*pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
-			if ((rb_prev ? (*pprev)->vm_next : mm->mmap) != vma)
-				BUG();
-			return vma;
+	struct vm_area_struct *vma = NULL, *prev = NULL;
+	rb_node_t * rb_node;
+	if (!mm)
+		goto out;
+
+	/* Guard against addr being lower than the first VMA */
+	vma = mm->mmap;
+
+	/* Go through the RB tree quickly. */
+	rb_node = mm->mm_rb.rb_node;
+
+	while (rb_node) {
+		struct vm_area_struct *vma_tmp;
+		vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
+
+		if (addr < vma_tmp->vm_end) {
+			rb_node = rb_node->rb_left;
+		} else {
+			prev = vma_tmp;
+			if (!prev->vm_next || (addr < prev->vm_next->vm_end))
+				break;
+			rb_node = rb_node->rb_right;
 		}
 	}
-	*pprev = NULL;
-	return NULL;
+
+ out:
+	*pprev = prev;
+	return prev ? prev->vm_next : vma;
 }
 
+#ifdef ARCH_STACK_GROWSUP
+struct vm_area_struct * 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);
+	if (vma && (vma->vm_start <= addr))
+		return vma;
+	if (!prev || expand_stack(prev, addr))
+		return NULL;
+	if (prev->vm_flags & VM_LOCKED) {
+		make_pages_present(addr, prev->vm_end);
+	}
+	return prev;
+}
+#else
 struct vm_area_struct * find_extend_vma(struct mm_struct * mm, unsigned long addr)
 {
 	struct vm_area_struct * vma;
@@ -733,6 +737,7 @@
 	}
 	return vma;
 }
+#endif
 
 /*
  * Try to free as many page directory entries as we can,

-- 
Revolutions do not require corporate support.
--
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/

Re: [PATCH] find_vma_prev rewrite

[Rik van Riel]

On Thu, 27 Jun 2002, Matthew Wilcox wrote:

> I've been sending patches like this for over 18 months now with
> no comments.  I'm sending it to Linus early next week.  It benefits
> ia64's fault handler path and is required for PA-RISC's fault handler.
> It works, it's tested.

It still looks good to me ;)

I hope Linus will merge it this time.

regards,

Rik
-- 
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.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/

Re: [PATCH] find_vma_prev rewrite

[William Lee Irwin III]

On Thu, Jun 27, 2002 at 04:07:57PM +0100, Matthew Wilcox wrote:
> I've been sending patches like this for over 18 months now with
> no comments.  I'm sending it to Linus early next week.  It benefits
> ia64's fault handler path and is required for PA-RISC's fault handler.
> It works, it's tested.  I realise this puts it in a very different class
> from the kind of VM patches which are allowed in a stable kernel tree.

That's discouraging to hear... perhaps some other time to discuss it.


On Thu, Jun 27, 2002 at 04:07:57PM +0100, Matthew Wilcox wrote:
> There's also a chunk after find_vma_prev which adds an implementation
> of find_extend_vma for machines with stacks which grow up.  I couldn't
> be bothered to split it out, since it won't affect any other architecture.

It should be there for correctness.

I say it should go in.


Cheers,
Bill
--
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/