From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 870C4C38142 for ; Mon, 22 Aug 2022 19:21:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237287AbiHVTVW (ORCPT ); Mon, 22 Aug 2022 15:21:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47452 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238646AbiHVTUx (ORCPT ); Mon, 22 Aug 2022 15:20:53 -0400 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BB7C2B9B for ; Mon, 22 Aug 2022 12:19:51 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sin.source.kernel.org (Postfix) with ESMTPS id 0C1C0CE16DE for ; Mon, 22 Aug 2022 19:19:50 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 958ADC433C1; Mon, 22 Aug 2022 19:19:47 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1661195987; bh=JFkRsAmyVy6wr2+ImiW06/PA79VOqPGDlu537VihgyE=; h=Date:To:From:Subject:From; b=dEz8ImpSqS8MLQGfhANhc/HgJrgVKp4HGBzLeDqJEPsNkAxESXcG/zT4EOx8QnspQ TWRnllVbi60MwQN6U7E8l3ad6ZwsyeLeaFZMtVM917/iaLjah6sDeIiCeHegGNZdOi RM61MaZ72HdqRrnMRHcuJXnk4zdwR+fVfib5IJJE= Date: Mon, 22 Aug 2022 12:19:46 -0700 To: mm-commits@vger.kernel.org, yuzhao@google.com, willy@infradead.org, will@kernel.org, vbabka@suse.cz, svens@linux.ibm.com, sj@kernel.org, dhowells@redhat.com, david@redhat.com, catalin.marinas@arm.com, Liam.Howlett@Oracle.com, akpm@linux-foundation.org From: Andrew Morton Subject: + mm-mmap-use-the-maple-tree-for-find_vma_prev-instead-of-the-rbtree.patch added to mm-unstable branch Message-Id: <20220822191947.958ADC433C1@smtp.kernel.org> Precedence: bulk Reply-To: linux-kernel@vger.kernel.org List-ID: X-Mailing-List: mm-commits@vger.kernel.org The patch titled Subject: mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree has been added to the -mm mm-unstable branch. Its filename is mm-mmap-use-the-maple-tree-for-find_vma_prev-instead-of-the-rbtree.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/mm-mmap-use-the-maple-tree-for-find_vma_prev-instead-of-the-rbtree.patch This patch will later appear in the mm-unstable branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm Before you just go and hit "reply", please: a) Consider who else should be cc'ed b) Prefer to cc a suitable mailing list as well c) Ideally: find the original patch on the mailing list and do a reply-to-all to that, adding suitable additional cc's *** Remember to use Documentation/process/submit-checklist.rst when testing your code *** The -mm tree is included into linux-next via the mm-everything branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm and is updated there every 2-3 working days ------------------------------------------------------ From: "Liam R. Howlett" Subject: mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Date: Mon, 22 Aug 2022 15:03:05 +0000 Use the maple tree's advanced API and a maple state to walk the tree for the entry at the address of the next vma, then use the maple state to walk back one entry to find the previous entry. Add kernel documentation comments for this API. Link: https://lkml.kernel.org/r/20220822150128.1562046-13-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Signed-off-by: Matthew Wilcox (Oracle) Acked-by: Vlastimil Babka Reviewed-by: David Hildenbrand Cc: Catalin Marinas Cc: David Howells Cc: SeongJae Park Cc: Sven Schnelle Cc: Will Deacon Cc: Yu Zhao Signed-off-by: Andrew Morton --- mm/mmap.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) --- a/mm/mmap.c~mm-mmap-use-the-maple-tree-for-find_vma_prev-instead-of-the-rbtree +++ a/mm/mmap.c @@ -2475,23 +2475,30 @@ struct vm_area_struct *find_vma(struct m } 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 + * + * Note that RCU lock is missing here since the external mmap_lock() is used + * instead. + * + * 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 *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); - - *pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL; - } + vma = mas_walk(&mas); + *pprev = mas_prev(&mas, 0); + if (!vma) + vma = mas_next(&mas, ULONG_MAX); return vma; } _ Patches currently in -mm which might be from Liam.Howlett@Oracle.com are maple-tree-add-new-data-structure.patch radix-tree-test-suite-add-pr_err-define.patch radix-tree-test-suite-add-kmem_cache_set_non_kernel.patch radix-tree-test-suite-add-allocation-counts-and-size-to-kmem_cache.patch radix-tree-test-suite-add-support-for-slab-bulk-apis.patch radix-tree-test-suite-add-lockdep_is_held-to-header.patch lib-test_maple_tree-add-testing-for-maple-tree.patch mm-start-tracking-vmas-with-maple-tree.patch mm-mmap-use-the-maple-tree-in-find_vma-instead-of-the-rbtree.patch mm-mmap-use-the-maple-tree-for-find_vma_prev-instead-of-the-rbtree.patch mm-mmap-use-maple-tree-for-unmapped_area_topdown.patch kernel-fork-use-maple-tree-for-dup_mmap-during-forking.patch damon-convert-__damon_va_three_regions-to-use-the-vma-iterator.patch mm-remove-rb-tree.patch mmap-change-zeroing-of-maple-tree-in-__vma_adjust.patch xen-use-vma_lookup-in-privcmd_ioctl_mmap.patch mm-optimize-find_exact_vma-to-use-vma_lookup.patch mm-khugepaged-optimize-collapse_pte_mapped_thp-by-using-vma_lookup.patch mm-mmap-change-do_brk_flags-to-expand-existing-vma-and-add-do_brk_munmap.patch mm-use-maple-tree-operations-for-find_vma_intersection.patch mm-mmap-use-advanced-maple-tree-api-for-mmap_region.patch mm-remove-vmacache.patch mm-convert-vma_lookup-to-use-mtree_load.patch mm-mmap-move-mmap_region-below-do_munmap.patch mm-mmap-reorganize-munmap-to-use-maple-states.patch mm-mmap-change-do_brk_munmap-to-use-do_mas_align_munmap.patch arm64-change-elfcore-for_each_mte_vma-to-use-vma-iterator.patch fs-proc-base-use-maple-tree-iterators-in-place-of-linked-list.patch userfaultfd-use-maple-tree-iterator-to-iterate-vmas.patch ipc-shm-use-vma-iterator-instead-of-linked-list.patch bpf-remove-vma-linked-list.patch mm-gup-use-maple-tree-navigation-instead-of-linked-list.patch mm-madvise-use-vma_find-instead-of-vma-linked-list.patch mm-memcontrol-stop-using-mm-highest_vm_end.patch mm-mempolicy-use-vma-iterator-maple-state-instead-of-vma-linked-list.patch mm-mprotect-use-maple-tree-navigation-instead-of-vma-linked-list.patch mm-mremap-use-vma_find_intersection-instead-of-vma-linked-list.patch mm-msync-use-vma_find-instead-of-vma-linked-list.patch mm-oom_kill-use-maple-tree-iterators-instead-of-vma-linked-list.patch mm-swapfile-use-vma-iterator-instead-of-vma-linked-list.patch riscv-use-vma-iterator-for-vdso.patch mm-remove-the-vma-linked-list.patch mm-mmap-drop-range_has_overlap-function.patch mm-mmapc-pass-in-mapping-to-__vma_link_file.patch