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 1E726C32774 for ; Mon, 22 Aug 2022 19:21:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238432AbiHVTVb (ORCPT ); Mon, 22 Aug 2022 15:21:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47428 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238624AbiHVTUw (ORCPT ); Mon, 22 Aug 2022 15:20:52 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9D9BC52DF0 for ; Mon, 22 Aug 2022 12:19:46 -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 dfw.source.kernel.org (Postfix) with ESMTPS id 1E66661234 for ; Mon, 22 Aug 2022 19:19:46 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 732F2C43470; Mon, 22 Aug 2022 19:19:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1661195985; bh=3uDdhzppJm4e3MaITZ20JrhiQ+Vaqi67f+75yLo98Dk=; h=Date:To:From:Subject:From; b=U0cbFeZ1z1GmuwlDqTnPjrhc3BggmZvaak1tsC/XKNOI1K0SK7SVQ1byZH3pVmmic eH+6YUNBo8QawtTP+yb+kZ7Q+KlW5Aa8WEHng8YtQQZrRTQvpRgCyBjs4nEBU1Ljoe oWSydQ4Nns82PvVvt+8eRtl4j9rGEOvUJ0rhWK8c= Date: Mon, 22 Aug 2022 12:19:44 -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-in-find_vma-instead-of-the-rbtree.patch added to mm-unstable branch Message-Id: <20220822191945.732F2C43470@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 in find_vma() instead of the rbtree. has been added to the -mm mm-unstable branch. Its filename is mm-mmap-use-the-maple-tree-in-find_vma-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-in-find_vma-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 in find_vma() instead of the rbtree. Date: Mon, 22 Aug 2022 15:03:02 +0000 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/20220822150128.1562046-12-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Acked-by: Vlastimil Babka Reviewed-by: David Hildenbrand Cc: Catalin Marinas Cc: David Howells Cc: "Matthew Wilcox (Oracle)" Cc: SeongJae Park Cc: Sven Schnelle Cc: Will Deacon Cc: Yu Zhao Signed-off-by: Andrew Morton --- mm/mmap.c | 28 ++++++++++------------------ 1 file changed, 10 insertions(+), 18 deletions(-) --- a/mm/mmap.c~mm-mmap-use-the-maple-tree-in-find_vma-instead-of-the-rbtree +++ a/mm/mmap.c @@ -2449,11 +2449,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. */ +/** + * 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. */ @@ -2461,22 +2468,7 @@ struct vm_area_struct *find_vma(struct m 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; _ 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