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: Liam Howlett <liam.howlett@oracle.com>
Subject: [PATCH v14 23/70] mm: use maple tree operations for find_vma_intersection()
Date: Tue, 6 Sep 2022 19:48:50 +0000 [thread overview]
Message-ID: <20220906194824.2110408-24-Liam.Howlett@oracle.com> (raw)
In-Reply-To: <20220906194824.2110408-1-Liam.Howlett@oracle.com>
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Move find_vma_intersection() to mmap.c and change implementation to maple
tree.
When searching for a vma within a range, it is easier to use the maple
tree interface.
Exported find_vma_intersection() for kvm module.
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
include/linux/mm.h | 22 ++++------------------
mm/mmap.c | 29 +++++++++++++++++++++++++++++
mm/nommu.c | 11 +++++++++++
3 files changed, 44 insertions(+), 18 deletions(-)
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 3f9cf513e046..9ed579168f87 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -2782,26 +2782,12 @@ extern struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long add
extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
struct vm_area_struct **pprev);
-/**
- * find_vma_intersection() - Look up the first VMA which intersects the interval
- * @mm: The process address space.
- * @start_addr: The inclusive start user address.
- * @end_addr: The exclusive end user address.
- *
- * Returns: The first VMA within the provided range, %NULL otherwise. Assumes
- * start_addr < end_addr.
+/*
+ * Look up the first VMA which intersects the interval [start_addr, end_addr)
+ * NULL if none. Assume start_addr < end_addr.
*/
-static inline
struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
- unsigned long start_addr,
- unsigned long end_addr)
-{
- struct vm_area_struct *vma = find_vma(mm, start_addr);
-
- if (vma && end_addr <= vma->vm_start)
- vma = NULL;
- return vma;
-}
+ unsigned long start_addr, unsigned long end_addr);
/**
* vma_lookup() - Find a VMA at a specific address
diff --git a/mm/mmap.c b/mm/mmap.c
index 0baa2ca5b0bf..699af34c3573 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2061,6 +2061,35 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
EXPORT_SYMBOL(get_unmapped_area);
+/**
+ * find_vma_intersection() - Look up the first VMA which intersects the interval
+ * @mm: The process address space.
+ * @start_addr: The inclusive start user address.
+ * @end_addr: The exclusive end user address.
+ *
+ * Returns: The first VMA within the provided range, %NULL otherwise. Assumes
+ * start_addr < end_addr.
+ */
+struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
+ unsigned long start_addr,
+ unsigned long end_addr)
+{
+ struct vm_area_struct *vma;
+ unsigned long index = start_addr;
+
+ mmap_assert_locked(mm);
+ /* Check the cache first. */
+ vma = vmacache_find(mm, start_addr);
+ if (likely(vma))
+ return vma;
+
+ vma = mt_find(&mm->mm_mt, &index, end_addr - 1);
+ if (vma)
+ vmacache_update(start_addr, vma);
+ return vma;
+}
+EXPORT_SYMBOL(find_vma_intersection);
+
/**
* find_vma() - Find the VMA for a given address, or the next VMA.
* @mm: The mm_struct to check
diff --git a/mm/nommu.c b/mm/nommu.c
index 321c7e6718a8..2702790d05d3 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -642,6 +642,17 @@ static void delete_vma(struct mm_struct *mm, struct vm_area_struct *vma)
vm_area_free(vma);
}
+struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
+ unsigned long start_addr,
+ unsigned long end_addr)
+{
+ unsigned long index = start_addr;
+
+ mmap_assert_locked(mm);
+ return mt_find(&mm->mm_mt, &index, end_addr - 1);
+}
+EXPORT_SYMBOL(find_vma_intersection);
+
/*
* look up the first VMA in which addr resides, NULL if none
* - should be called with mm->mmap_lock at least held readlocked
--
2.35.1
next prev parent reply other threads:[~2022-09-06 19:49 UTC|newest]
Thread overview: 89+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-06 19:48 [PATCH v14 00/70] Introducing the Maple Tree Liam Howlett
2022-09-06 19:48 ` [PATCH v14 02/70] radix tree test suite: add pr_err define Liam Howlett
2022-09-06 19:48 ` [PATCH v14 01/70] Maple Tree: add new data structure Liam Howlett
2022-09-12 8:42 ` Bagas Sanjaya
2022-09-14 10:16 ` Liam Howlett
2022-09-06 19:48 ` [PATCH v14 04/70] radix tree test suite: add allocation counts and size to kmem_cache Liam Howlett
2022-09-06 19:48 ` [PATCH v14 03/70] radix tree test suite: add kmem_cache_set_non_kernel() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 05/70] radix tree test suite: add support for slab bulk APIs Liam Howlett
2022-09-06 19:48 ` [PATCH v14 06/70] radix tree test suite: add lockdep_is_held to header Liam Howlett
2022-09-06 19:48 ` [PATCH v14 07/70] lib/test_maple_tree: add testing for maple tree Liam Howlett
2022-10-11 12:16 ` Geert Uytterhoeven
2022-10-11 12:56 ` Matthew Wilcox
2022-10-11 12:59 ` Geert Uytterhoeven
2022-10-11 16:13 ` Liam Howlett
2022-09-06 19:48 ` [PATCH v14 08/70] mm: start tracking VMAs with " Liam Howlett
2022-09-06 19:48 ` [PATCH v14 11/70] mm/mmap: use the maple tree in find_vma() instead of the rbtree Liam Howlett
2022-09-06 19:48 ` [PATCH v14 10/70] mmap: use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 09/70] mm: add VMA iterator Liam Howlett
2022-09-06 19:48 ` [PATCH v14 14/70] kernel/fork: use maple tree for dup_mmap() during forking Liam Howlett
2022-09-06 19:48 ` [PATCH v14 12/70] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Liam Howlett
2022-09-06 19:48 ` [PATCH v14 13/70] mm/mmap: use maple tree for unmapped_area{_topdown} Liam Howlett
2022-09-06 19:48 ` [PATCH v14 17/70] mm: remove rb tree Liam Howlett
2022-09-06 19:48 ` [PATCH v14 16/70] proc: remove VMA rbtree use from nommu Liam Howlett
2022-09-06 19:48 ` [PATCH v14 15/70] damon: convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-09-06 19:48 ` [PATCH v14 20/70] mm: optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 18/70] mmap: change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 19/70] xen: use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 22/70] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 21/70] mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-09-06 19:48 ` Liam Howlett [this message]
2022-09-06 19:48 ` [PATCH v14 24/70] mm/mmap: use advanced maple tree API for mmap_region() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 25/70] mm: remove vmacache Liam Howlett
2022-09-06 19:48 ` [PATCH v14 26/70] mm: convert vma_lookup() to use mtree_load() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 28/70] mm/mmap: reorganize munmap to use maple states Liam Howlett
2022-09-06 19:48 ` [PATCH v14 27/70] mm/mmap: move mmap_region() below do_munmap() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 29/70] mm/mmap: change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-09-06 19:48 ` [PATCH v14 30/70] arm64: remove mmap linked list from vdso Liam Howlett
2022-09-06 19:48 ` [PATCH v14 31/70] arm64: Change elfcore for_each_mte_vma() to use VMA iterator Liam Howlett
2022-09-06 19:48 ` [PATCH v14 32/70] parisc: remove mmap linked list from cache handling Liam Howlett
2022-09-06 19:48 ` [PATCH v14 33/70] powerpc: remove mmap linked list walks Liam Howlett
2022-09-06 19:48 ` [PATCH v14 34/70] s390: remove vma " Liam Howlett
2022-09-06 19:48 ` [PATCH v14 35/70] x86: " Liam Howlett
2022-09-06 19:48 ` [PATCH v14 38/70] optee: remove vma linked list walk Liam Howlett
2022-09-06 19:48 ` [PATCH v14 36/70] xtensa: remove vma linked list walks Liam Howlett
2022-09-06 19:48 ` [PATCH v14 37/70] cxl: remove vma linked list walk Liam Howlett
2022-09-06 19:48 ` [PATCH v14 39/70] um: " Liam Howlett
2022-09-06 19:48 ` [PATCH v14 41/70] exec: use VMA iterator instead of linked list Liam Howlett
2022-09-06 19:48 ` [PATCH v14 40/70] coredump: remove vma linked list walk Liam Howlett
2022-09-06 19:48 ` [PATCH v14 42/70] fs/proc/base: use the vma iterators in place of linked list Liam Howlett
2022-09-06 19:48 ` [PATCH v14 43/70] fs/proc/task_mmu: stop using linked list and highest_vm_end Liam Howlett
2022-09-06 19:48 ` [PATCH v14 44/70] userfaultfd: use maple tree iterator to iterate VMAs Liam Howlett
2022-09-06 19:48 ` [PATCH v14 45/70] ipc/shm: use VMA iterator instead of linked list Liam Howlett
2022-09-06 19:48 ` [PATCH v14 46/70] acct: " Liam Howlett
2022-09-06 19:48 ` [PATCH v14 47/70] perf: use VMA iterator Liam Howlett
2022-09-06 19:48 ` [PATCH v14 50/70] bpf: remove VMA linked list Liam Howlett
2022-09-06 19:48 ` [PATCH v14 49/70] fork: use VMA iterator Liam Howlett
2022-09-06 19:48 ` [PATCH v14 48/70] sched: use maple tree iterator to walk VMAs Liam Howlett
2022-09-06 19:49 ` [PATCH v14 52/70] mm/khugepaged: stop using vma linked list Liam Howlett
2022-09-06 19:49 ` [PATCH v14 51/70] mm/gup: use maple tree navigation instead of " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 55/70] mm/memcontrol: stop using mm->highest_vm_end Liam Howlett
2022-09-06 19:49 ` [PATCH v14 54/70] mm/madvise: use vma_find() instead of vma linked list Liam Howlett
2022-09-06 19:49 ` [PATCH v14 53/70] mm/ksm: use vma iterators " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 57/70] mm/mlock: use vma iterator and maple state " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 56/70] mm/mempolicy: use vma iterator & " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 58/70] mm/mprotect: use maple tree navigation instead of VMA " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 59/70] mm/mremap: use vma_find_intersection() instead of vma " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 60/70] mm/msync: use vma_find() " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 61/70] mm/oom_kill: use vma iterators " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 64/70] i915: use the VMA iterator Liam Howlett
2022-09-06 19:49 ` [PATCH v14 63/70] mm/swapfile: use vma iterator instead of vma linked list Liam Howlett
2022-09-06 19:49 ` [PATCH v14 62/70] mm/pagewalk: use vma_find() " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 65/70] nommu: remove uses of VMA " Liam Howlett
2022-09-06 19:49 ` [PATCH v14 67/70] mm/vmscan: Use vma iterator instead of vm_next Liam Howlett
2022-09-12 6:55 ` Yu Zhao
2022-09-12 7:13 ` Yu Zhao
2022-09-12 7:14 ` Liam Howlett
2022-09-12 19:45 ` Andrew Morton
2022-09-12 20:01 ` Yu Zhao
2022-09-12 21:03 ` Andrew Morton
2022-09-13 3:39 ` Yu Zhao
2022-09-06 19:49 ` [PATCH v14 66/70] riscv: use vma iterator for vdso Liam Howlett
2022-09-06 19:49 ` [PATCH v14 70/70] mm/mmap.c: pass in mapping to __vma_link_file() Liam Howlett
2022-09-06 19:49 ` [PATCH v14 68/70] mm: remove the vma linked list Liam Howlett
2022-09-06 19:49 ` [PATCH v14 69/70] mm/mmap: drop range_has_overlap() function Liam Howlett
2022-09-06 23:51 ` [PATCH v14 00/70] Introducing the Maple Tree Andrew Morton
2022-09-07 0:24 ` Liam Howlett
2022-09-12 0:20 ` Andrew Morton
2022-09-15 18:03 ` Yu Zhao
2022-09-17 8:24 ` Yu Zhao
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=20220906194824.2110408-24-Liam.Howlett@oracle.com \
--to=liam.howlett@oracle.com \
--cc=akpm@linux-foundation.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=maple-tree@lists.infradead.org \
/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).