LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Liam Howlett <liam.howlett@oracle.com>
To: "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
	"linux-mm@kvack.org" <linux-mm@kvack.org>,
	"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
	Andrew Morton <akpm@linux-foundation.org>
Cc: Song Liu <songliubraving@fb.com>,
	Davidlohr Bueso <dave@stgolabs.net>,
	"Paul E . McKenney" <paulmck@kernel.org>,
	Matthew Wilcox <willy@infradead.org>,
	Laurent Dufour <ldufour@linux.ibm.com>,
	David Rientjes <rientjes@google.com>,
	Axel Rasmussen <axelrasmussen@google.com>,
	Suren Baghdasaryan <surenb@google.com>,
	Vlastimil Babka <vbabka@suse.cz>, Rik van Riel <riel@surriel.com>,
	Peter Zijlstra <peterz@infradead.org>,
	Michel Lespinasse <walken.cr@gmail.com>,
	Liam Howlett <liam.howlett@oracle.com>
Subject: [PATCH v2 08/61] mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree
Date: Tue, 17 Aug 2021 15:47:11 +0000	[thread overview]
Message-ID: <20210817154651.1570984-9-Liam.Howlett@oracle.com> (raw)
In-Reply-To: <20210817154651.1570984-1-Liam.Howlett@oracle.com>

From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>

Use the maple tree's advanced API and a maple state to walk the tree for
the entry at the address or the next vma, then use the maple state to
walk back one entry to find the previous entry.  Note, the advanced
maple tree interface does not handle the rcu locking.

Add kernel documentation comments for this API.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 mm/mmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 899747a75d5c..4d996ab2372a 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2513,23 +2513,30 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
 
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * set %pprev to the previous VMA, if any.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * Returns: The VMA associated with @addr, or the next vma.
+ * May return %NULL in the case of no vma at addr or above.
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,
-			struct vm_area_struct **pprev)
+	      struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	vma = find_vma(mm, addr);
-	if (vma) {
-		*pprev = vma->vm_prev;
-	} else {
-		struct rb_node *rb_node = rb_last(&mm->mm_rb);
+	rcu_read_lock();
+	vma = mas_find(&mas, ULONG_MAX);
+	if (!vma)
+		mas_reset(&mas);
 
-		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
-	}
+	*pprev = mas_prev(&mas, 0);
+	rcu_read_unlock();
 	return vma;
 }
 
-- 
2.30.2

  parent reply	other threads:[~2021-08-17 15:52 UTC|newest]

Thread overview: 67+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-17 15:47 [PATCH v2 00/61] Introducing the Maple Tree Liam Howlett
2021-08-17 15:47 ` [PATCH v2 01/61] radix tree test suite: Add pr_err define Liam Howlett
2021-08-17 15:47 ` [PATCH v2 04/61] radix tree test suite: Add support for slab bulk APIs Liam Howlett
2021-08-17 15:47 ` [PATCH v2 02/61] radix tree test suite: Add kmem_cache_set_non_kernel() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 03/61] radix tree test suite: Add allocation counts and size to kmem_cache Liam Howlett
2021-08-17 15:47 ` [PATCH v2 05/61] Maple Tree: Add new data structure Liam Howlett
2021-08-17 15:47 ` [PATCH v2 06/61] mm: Start tracking VMAs with maple tree Liam Howlett
2021-08-17 15:47 ` [PATCH v2 07/61] mm/mmap: Use the maple tree in find_vma() instead of the rbtree Liam Howlett
2021-08-17 15:47 ` [PATCH v2 09/61] mm/mmap: Use maple tree for unmapped_area{_topdown} Liam Howlett
2021-08-17 15:47 ` Liam Howlett [this message]
2021-08-17 15:47 ` [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking Liam Howlett
2021-08-17 15:47 ` [PATCH v2 12/61] xen/privcmd: Optimized privcmd_ioctl_mmap() by using vma_lookup() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 13/61] mm: Optimize find_exact_vma() to use vma_lookup() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 11/61] mm: Remove rb tree Liam Howlett
2021-08-23  9:49   ` David Hildenbrand
2021-08-31 14:40     ` Liam Howlett
2021-08-17 15:47 ` [PATCH v2 16/61] mm: Use maple tree operations for find_vma_intersection() and find_vma() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 15/61] mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 17/61] mm/mmap: Use advanced maple tree API for mmap_region() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 14/61] mm/khugepaged: Optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 18/61] mm: Remove vmacache Liam Howlett
2021-08-17 15:47 ` [PATCH v2 19/61] mm/mmap: Move mmap_region() below do_munmap() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 21/61] mm/mmap: Reorganize munmap to use maple states Liam Howlett
2021-08-17 15:47 ` [PATCH v2 20/61] mm/mmap: Convert count_vma_pages_range() to use ma_state Liam Howlett
2021-08-17 15:47 ` [PATCH v2 22/61] mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 24/61] arch/arm64: Remove mmap linked list from vdso Liam Howlett
2021-08-17 15:47 ` [PATCH v2 23/61] mm: Introduce vma_next() and vma_prev() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 26/61] arch/powerpc: Remove mmap linked list from mm/book3s32/tlb Liam Howlett
2021-08-17 15:47 ` [PATCH v2 25/61] arch/parisc: Remove mmap linked list from kernel/cache Liam Howlett
2021-08-17 15:47 ` [PATCH v2 28/61] arch/s390: Use maple tree iterators instead of linked list Liam Howlett
2021-08-17 15:47 ` [PATCH v2 27/61] arch/powerpc: Remove mmap linked list from mm/book3s64/subpage_prot Liam Howlett
2021-08-17 15:47 ` [PATCH v2 31/61] drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 30/61] arch/xtensa: Use maple tree iterators for unmapped area Liam Howlett
2021-08-17 15:47 ` [PATCH v2 29/61] arch/x86: Use maple tree iterators for vdso/vma Liam Howlett
2021-08-17 15:47 ` [PATCH v2 33/61] fs/binfmt_elf: Use maple tree iterators for fill_files_note() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 32/61] drivers/tee/optee: Use maple tree iterators for __check_mem_type() Liam Howlett
2021-08-17 15:47 ` [PATCH v2 34/61] fs/coredump: Use maple tree iterators in place of linked list Liam Howlett
2021-08-17 15:47 ` [PATCH v2 38/61] fs/userfaultfd: Stop using vma " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 37/61] fs/proc/task_mmu: Stop using linked list and highest_vm_end Liam Howlett
2021-08-17 15:47 ` [PATCH v2 36/61] fs/proc/base: Use maple tree iterators in place of linked list Liam Howlett
2021-08-17 15:47 ` [PATCH v2 35/61] fs/exec: Use vma_next() instead " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 39/61] ipc/shm: Stop using the vma " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 41/61] kernel/events/core: Use maple tree iterators instead of " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 40/61] kernel/acct: " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 45/61] arch/um/kernel/tlb: Stop using " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 42/61] kernel/events/uprobes: Use maple tree iterators instead of " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 44/61] kernel/sys: " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 43/61] kernel/sched/fair: " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 46/61] bpf: Remove VMA " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 48/61] mm/khugepaged: Use maple tree iterators instead of vma " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 47/61] mm/gup: Use maple tree navigation instead of " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 51/61] mm/memcontrol: Stop using mm->highest_vm_end Liam Howlett
2021-08-17 15:47 ` [PATCH v2 49/61] mm/ksm: Use maple tree iterators instead of vma linked list Liam Howlett
2021-08-17 15:47 ` [PATCH v2 52/61] mm/mempolicy: " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 50/61] mm/madvise: Use vma_next " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 54/61] mm/mprotect: Use maple tree navigation " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 56/61] mm/msync: Use vma_next() " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 53/61] mm/mlock: Use maple tree iterators " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 55/61] mm/mremap: Use vma_next() " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 57/61] mm/oom_kill: Use maple tree iterators " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 59/61] mm/swapfile: Use maple tree iterator " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 58/61] mm/pagewalk: Use vma_next() " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 60/61] mm: Remove the " Liam Howlett
2021-08-17 15:47 ` [PATCH v2 61/61] mm/mmap: Drop range_has_overlap() function Liam Howlett
     [not found] ` <20210818083610.3698-1-hdanton@sina.com>
2021-08-18 14:54   ` [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking Liam Howlett
     [not found]   ` <20210819020105.3756-1-hdanton@sina.com>
2021-08-19 13:32     ` Liam Howlett
2021-08-20 17:45     ` Liam Howlett

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=20210817154651.1570984-9-Liam.Howlett@oracle.com \
    --to=liam.howlett@oracle.com \
    --cc=akpm@linux-foundation.org \
    --cc=axelrasmussen@google.com \
    --cc=dave@stgolabs.net \
    --cc=ldufour@linux.ibm.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=maple-tree@lists.infradead.org \
    --cc=paulmck@kernel.org \
    --cc=peterz@infradead.org \
    --cc=riel@surriel.com \
    --cc=rientjes@google.com \
    --cc=songliubraving@fb.com \
    --cc=surenb@google.com \
    --cc=vbabka@suse.cz \
    --cc=walken.cr@gmail.com \
    --cc=willy@infradead.org \
    --subject='Re: [PATCH v2 08/61] mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree' \
    /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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).