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>,
Yu Zhao <yuzhao@google.com>, Hugh Dickins <hughd@google.com>
Subject: [PATCH v11 11/69] mm/mmap: use the maple tree in find_vma() instead of the rbtree.
Date: Sun, 17 Jul 2022 02:46:40 +0000 [thread overview]
Message-ID: <20220717024615.2106835-12-Liam.Howlett@oracle.com> (raw)
In-Reply-To: <20220717024615.2106835-1-Liam.Howlett@oracle.com>
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Using the maple tree interface mt_find() will handle the RCU locking and
will start searching at the address up to the limit, ULONG_MAX in this
case.
Add kernel documentation to this API.
Link: https://lkml.kernel.org/r/20220504010716.661115-13-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20220621204632.3370049-12-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: David Hildenbrand <david@redhat.com>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: "Matthew Wilcox (Oracle)" <willy@infradead.org>
Cc: SeongJae Park <sj@kernel.org>
Cc: Will Deacon <will@kernel.org>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
mm/mmap.c | 28 ++++++++++------------------
1 file changed, 10 insertions(+), 18 deletions(-)
diff --git a/mm/mmap.c b/mm/mmap.c
index 1ba4074c75cf..96ff32ff97cd 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2494,11 +2494,18 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
EXPORT_SYMBOL(get_unmapped_area);
-/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
+/**
+ * find_vma() - Find the VMA for a given address, or the next VMA.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ *
+ * 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(struct mm_struct *mm, unsigned long addr)
{
- struct rb_node *rb_node;
struct vm_area_struct *vma;
+ unsigned long index = addr;
mmap_assert_locked(mm);
/* Check the cache first. */
@@ -2506,22 +2513,7 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
if (likely(vma))
return vma;
- rb_node = mm->mm_rb.rb_node;
-
- while (rb_node) {
- struct vm_area_struct *tmp;
-
- tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
-
- if (tmp->vm_end > addr) {
- vma = tmp;
- if (tmp->vm_start <= addr)
- break;
- rb_node = rb_node->rb_left;
- } else
- rb_node = rb_node->rb_right;
- }
-
+ vma = mt_find(&mm->mm_mt, &index, ULONG_MAX);
if (vma)
vmacache_update(addr, vma);
return vma;
--
2.35.1
next prev parent reply other threads:[~2022-07-17 2:46 UTC|newest]
Thread overview: 76+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-17 2:46 [PATCH v11 00/69] Introducing the Maple Tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 02/69] radix tree test suite: add pr_err define Liam Howlett
2022-07-17 2:46 ` [PATCH v11 01/69] Maple Tree: add new data structure Liam Howlett
2022-07-17 2:46 ` [PATCH v11 03/69] radix tree test suite: add kmem_cache_set_non_kernel() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 04/69] radix tree test suite: add allocation counts and size to kmem_cache Liam Howlett
2022-07-17 2:46 ` [PATCH v11 05/69] radix tree test suite: add support for slab bulk APIs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 06/69] radix tree test suite: add lockdep_is_held to header Liam Howlett
2022-07-17 2:46 ` [PATCH v11 07/69] lib/test_maple_tree: add testing for maple tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 10/69] mmap: use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 09/69] mm: add VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 08/69] mm: start tracking VMAs with maple tree Liam Howlett
2022-07-17 2:46 ` Liam Howlett [this message]
2022-07-17 2:46 ` [PATCH v11 12/69] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 13/69] mm/mmap: use maple tree for unmapped_area{_topdown} Liam Howlett
2022-07-17 2:46 ` [PATCH v11 16/69] proc: remove VMA rbtree use from nommu Liam Howlett
2022-07-17 2:46 ` [PATCH v11 15/69] damon: convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 14/69] kernel/fork: use maple tree for dup_mmap() during forking Liam Howlett
2022-07-17 2:46 ` [PATCH v11 18/69] mmap: change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 17/69] mm: remove rb tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 19/69] xen: use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 20/69] mm: optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 22/69] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 21/69] mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 23/69] mm: use maple tree operations for find_vma_intersection() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 24/69] mm/mmap: use advanced maple tree API for mmap_region() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 25/69] mm: remove vmacache Liam Howlett
2022-07-17 2:46 ` [PATCH v11 26/69] mm: convert vma_lookup() to use mtree_load() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 27/69] mm/mmap: move mmap_region() below do_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 29/69] mm/mmap: change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 28/69] mm/mmap: reorganize munmap to use maple states Liam Howlett
2022-07-17 2:46 ` [PATCH v11 30/69] arm64: remove mmap linked list from vdso Liam Howlett
2022-07-17 2:46 ` [PATCH v11 31/69] arm64: Change elfcore for_each_mte_vma() to use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 32/69] parisc: remove mmap linked list from cache handling Liam Howlett
2022-07-17 2:46 ` [PATCH v11 34/69] s390: remove vma linked list walks Liam Howlett
2022-07-17 2:46 ` [PATCH v11 33/69] powerpc: remove mmap " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 36/69] xtensa: remove vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 37/69] cxl: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 35/69] x86: remove vma linked list walks Liam Howlett
2022-07-17 2:46 ` [PATCH v11 39/69] um: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 38/69] optee: " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 41/69] exec: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 40/69] coredump: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 44/69] userfaultfd: use maple tree iterator to iterate VMAs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 42/69] fs/proc/base: use maple tree iterators in place of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 43/69] fs/proc/task_mmu: stop using linked list and highest_vm_end Liam Howlett
2022-07-17 2:46 ` [PATCH v11 46/69] acct: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 47/69] perf: use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 45/69] ipc/shm: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 49/69] fork: use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 48/69] sched: use maple tree iterator to walk VMAs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 50/69] bpf: remove VMA linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 54/69] mm/madvise: use vma_find() instead of vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 53/69] mm/ksm: use vma iterators " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 51/69] mm/gup: use maple tree navigation instead of " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 52/69] mm/khugepaged: stop using vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 57/69] mm/mlock: use vma iterator and maple state instead of " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 55/69] mm/memcontrol: stop using mm->highest_vm_end Liam Howlett
2022-07-17 2:46 ` [PATCH v11 56/69] mm/mempolicy: use vma iterator & maple state instead of vma linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 59/69] mm/mremap: use vma_find_intersection() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 60/69] mm/msync: use vma_find() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 58/69] mm/mprotect: use maple tree navigation " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 63/69] mm/swapfile: use vma iterator " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 62/69] mm/pagewalk: use vma_find() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 61/69] mm/oom_kill: use maple tree iterators " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 64/69] i915: use the VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 67/69] mm: remove the vma linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 66/69] riscv: use vma iterator for vdso Liam Howlett
2022-07-17 2:46 ` [PATCH v11 65/69] nommu: remove uses of VMA linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 68/69] mm/mmap: drop range_has_overlap() function Liam Howlett
2022-07-17 2:46 ` [PATCH v11 69/69] mm/mmap.c: pass in mapping to __vma_link_file() Liam Howlett
2022-07-17 4:20 ` [PATCH v11 00/69] Introducing the Maple Tree Andrew Morton
2022-07-17 5:57 ` Yu Zhao
2022-07-17 12:42 ` Liam Howlett
2022-07-17 13:06 ` Liam Howlett
2022-07-17 18:55 ` Yu Zhao
2022-07-17 13:01 ` 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=20220717024615.2106835-12-Liam.Howlett@oracle.com \
--to=liam.howlett@oracle.com \
--cc=akpm@linux-foundation.org \
--cc=hughd@google.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=maple-tree@lists.infradead.org \
--cc=yuzhao@google.com \
/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 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).