All of lore.kernel.org
 help / color / mirror / Atom feed
From: Hillf Danton <dhillf@gmail.com>
To: Hugh Dickins <hughd@google.com>
Cc: Mel Gorman <mgorman@suse.de>,
	Johannes Weiner <hannes@cmpxchg.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Linux-MM <linux-mm@kvack.org>,
	LKML <linux-kernel@vger.kernel.org>,
	Hillf Danton <dhillf@gmail.com>
Subject: [RFC patch] mmap: permute find_vma with find_vma_prev
Date: Mon, 6 Aug 2012 20:56:27 +0800	[thread overview]
Message-ID: <CAJd=RBB2Hsqnn58idvs5azMonRhk0A6EOKZ=tTskRngGk=XCOw@mail.gmail.com> (raw)

Both find_vma and find_vma_prev have code for walking rb tree, and we can
walk less.

To cut the walk in find_vma_prev off, find_vma is changed to take care of
vm_prev while walking rb tree, and we end up wrapping find_vma_prev with
find_vma.

btw, what happened to LKML?

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- a/mm/mmap.c	Fri Aug  3 07:38:10 2012
+++ b/mm/mmap.c	Mon Aug  6 20:10:18 2012
@@ -1602,11 +1602,18 @@ get_unmapped_area(struct file *file, uns

 EXPORT_SYMBOL(get_unmapped_area);

-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
-struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+/*
+ * Look up the first VMA which satisfies  addr < vm_end,  NULL if none.
+ * Also return a pointer to the previous VMA.
+ */
+struct vm_area_struct *
+find_vma_prev(struct mm_struct *mm, unsigned long addr,
+			struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma = NULL;

+	*pprev = NULL; /* Should be removed with WARN_ON_ONCE(!mm) */
+
 	if (WARN_ON_ONCE(!mm))		/* Remove this in linux-3.6 */
 		return NULL;

@@ -1630,39 +1637,29 @@ struct vm_area_struct *find_vma(struct m
 				if (vma_tmp->vm_start <= addr)
 					break;
 				rb_node = rb_node->rb_left;
-			} else
+			} else {
 				rb_node = rb_node->rb_right;
+				*pprev = vma_tmp;
+			}
 		}
-		if (vma)
+		if (vma) {
 			mm->mmap_cache = vma;
+			/* remove false positive produced while walking rb tree */
+			*pprev = vma->vm_prev;
+		}
+	} else {
+		*pprev = vma->vm_prev;
 	}
 	return vma;
 }

-EXPORT_SYMBOL(find_vma);
-
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
- */
-struct vm_area_struct *
-find_vma_prev(struct mm_struct *mm, unsigned long addr,
-			struct vm_area_struct **pprev)
+struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
-	struct vm_area_struct *vma;
+	struct vm_area_struct *prev;

-	vma = find_vma(mm, addr);
-	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;
+	return find_vma_prev(mm, addr, &prev);
 }
+EXPORT_SYMBOL(find_vma);

 /*
  * Verify that the stack growth is acceptable and
--

WARNING: multiple messages have this Message-ID (diff)
From: Hillf Danton <dhillf@gmail.com>
To: Hugh Dickins <hughd@google.com>
Cc: Mel Gorman <mgorman@suse.de>,
	Johannes Weiner <hannes@cmpxchg.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Linux-MM <linux-mm@kvack.org>,
	LKML <linux-kernel@vger.kernel.org>,
	Hillf Danton <dhillf@gmail.com>
Subject: [RFC patch] mmap: permute find_vma with find_vma_prev
Date: Mon, 6 Aug 2012 20:56:27 +0800	[thread overview]
Message-ID: <CAJd=RBB2Hsqnn58idvs5azMonRhk0A6EOKZ=tTskRngGk=XCOw@mail.gmail.com> (raw)

Both find_vma and find_vma_prev have code for walking rb tree, and we can
walk less.

To cut the walk in find_vma_prev off, find_vma is changed to take care of
vm_prev while walking rb tree, and we end up wrapping find_vma_prev with
find_vma.

btw, what happened to LKML?

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- a/mm/mmap.c	Fri Aug  3 07:38:10 2012
+++ b/mm/mmap.c	Mon Aug  6 20:10:18 2012
@@ -1602,11 +1602,18 @@ get_unmapped_area(struct file *file, uns

 EXPORT_SYMBOL(get_unmapped_area);

-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
-struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+/*
+ * Look up the first VMA which satisfies  addr < vm_end,  NULL if none.
+ * Also return a pointer to the previous VMA.
+ */
+struct vm_area_struct *
+find_vma_prev(struct mm_struct *mm, unsigned long addr,
+			struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma = NULL;

+	*pprev = NULL; /* Should be removed with WARN_ON_ONCE(!mm) */
+
 	if (WARN_ON_ONCE(!mm))		/* Remove this in linux-3.6 */
 		return NULL;

@@ -1630,39 +1637,29 @@ struct vm_area_struct *find_vma(struct m
 				if (vma_tmp->vm_start <= addr)
 					break;
 				rb_node = rb_node->rb_left;
-			} else
+			} else {
 				rb_node = rb_node->rb_right;
+				*pprev = vma_tmp;
+			}
 		}
-		if (vma)
+		if (vma) {
 			mm->mmap_cache = vma;
+			/* remove false positive produced while walking rb tree */
+			*pprev = vma->vm_prev;
+		}
+	} else {
+		*pprev = vma->vm_prev;
 	}
 	return vma;
 }

-EXPORT_SYMBOL(find_vma);
-
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
- */
-struct vm_area_struct *
-find_vma_prev(struct mm_struct *mm, unsigned long addr,
-			struct vm_area_struct **pprev)
+struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
-	struct vm_area_struct *vma;
+	struct vm_area_struct *prev;

-	vma = find_vma(mm, addr);
-	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;
+	return find_vma_prev(mm, addr, &prev);
 }
+EXPORT_SYMBOL(find_vma);

 /*
  * Verify that the stack growth is acceptable and
--

--
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/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

             reply	other threads:[~2012-08-06 12:56 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-08-06 12:56 Hillf Danton [this message]
2012-08-06 12:56 ` [RFC patch] mmap: permute find_vma with find_vma_prev Hillf Danton
2012-08-07  2:08 ` Hugh Dickins
2012-08-07  2:08   ` Hugh Dickins
2012-08-07 12:13   ` Hillf Danton
2012-08-07 12:13     ` Hillf Danton

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAJd=RBB2Hsqnn58idvs5azMonRhk0A6EOKZ=tTskRngGk=XCOw@mail.gmail.com' \
    --to=dhillf@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=hannes@cmpxchg.org \
    --cc=hughd@google.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=mgorman@suse.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.