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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3BB6FE8FDDF for ; Wed, 4 Oct 2023 09:10:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AED406B0280; Wed, 4 Oct 2023 05:10:24 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A9D6D6B0282; Wed, 4 Oct 2023 05:10:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 965406B0283; Wed, 4 Oct 2023 05:10:24 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 832D96B0280 for ; Wed, 4 Oct 2023 05:10:24 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 56E5C1A0274 for ; Wed, 4 Oct 2023 09:10:24 +0000 (UTC) X-FDA: 81307207968.24.C083DF2 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) by imf09.hostedemail.com (Postfix) with ESMTP id 7017114000B for ; Wed, 4 Oct 2023 09:10:22 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=YANwGVPW; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1696410622; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=rKJAwIYAUhDqBrrCvu2WwShRLzJ5jUywMV1ELPZIW+U=; b=AsFZKd9Cdq6iHzibvdmS8nmMQiyP+MPg3rSLXZzuZ6Ag9pIDl1+VLZwgmXsTnNeqIV1uwA ESNFRDRHNJJtkdWgBqDnMFIc+FnMg5M3l7ttvC3BXk6LSPn5oI1ZpJR9pWxcHYUVDpNORL qyLVAwzjLOu0sRaOT+NNUxgpd3KljM8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696410622; a=rsa-sha256; cv=none; b=VG+kn85Jh3EprC5kfhBuy+QoVzO3neouJD7KIk3c+M7Dqgxesle2fhvV0RO0ocmMxJGoMB zOKhSMyBywwG6SX/gYeAJ7yfK8m/25kzm7kKO4nXvqVNGeVOHktDMIOcuHeOxzNCOvIlGV 9PVjFisdi5VhLJdAnZjC85zodx3uby8= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=YANwGVPW; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1c60f1a2652so5762905ad.0 for ; Wed, 04 Oct 2023 02:10:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696410621; x=1697015421; darn=kvack.org; h=content-transfer-encoding:in-reply-to:references:cc:to:subject:from :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=rKJAwIYAUhDqBrrCvu2WwShRLzJ5jUywMV1ELPZIW+U=; b=YANwGVPWd5EbmeSYh2HH0/NENI3W8TaJ09NQ8MSDM2FI5QqjUMZaexv4OR1h/xIVTJ eb/SgBSnLseSVA/LK/11FePvb6+iLX6TF0tUuQdT+oFew02RD6XsFEA2jPVZy+8zRPYS TZDchXya7wa0Q3aq/XcUNTtmMRXz8phsY21DerYEGzF+wBYGsLrU1QQDfGAlQ6RApGqR 16+oMb2mA9aaxIEhB2pj+WE3ac6ymAtqlMucMfEsq+em0tE8ZDZ4G770BOty/+eZZET4 OaNHwfFxEBZn+wBdGy71CUS8kanQhXei+HsbtSS4uX2l8MwDgKGonZtwqG2x0QyKPHqy M+Mg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696410621; x=1697015421; h=content-transfer-encoding:in-reply-to:references:cc:to:subject:from :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=rKJAwIYAUhDqBrrCvu2WwShRLzJ5jUywMV1ELPZIW+U=; b=tVwHCAKfJ8kT3zIeLyMBCXkm0gWu0BcTtSGDNTPk1lrWXpHujKjPjzRgOdhXBGf64o ZE8gWbq02L+bObca9S1mVFjpZSoLWR2+M4SSblNuAaj2qMjcBJDgDBFNBcu/Tv8lHMww qefBTA4askq2yUhdlqp6p88FmLXAbGER5P2ouVC4S6QniyOhxgk2kuPaReuHdINHPJ3y VjjOnHR9D9sHf0UlUmUidLZ5G38g+JBAhL/SsdSgeRRxpMNJq0KKoTN5sN3gqKTQQP99 eHWj9yGC+RYndlYRQXLy8cZ5TDrHjTJ7IqG+vGUZoD4BWmmPjvRtJdsGqUDo0zcdRXi+ JSJA== X-Gm-Message-State: AOJu0YwAwGwBCTta2dQWLcB2Vxxj/VKmSFf9uKAN57s23thOOEYaN7t9 6XV3i0rIddU04X4Bf5+AfitEQA== X-Google-Smtp-Source: AGHT+IH+2ztlmD8iaFNKs4yOGEQavd7SBWvqEEZakwnzE699TvF3bs7LYI7CQ0CZ36qHVaEX6KMesw== X-Received: by 2002:a17:902:c9c5:b0:1c3:b268:ecba with SMTP id q5-20020a170902c9c500b001c3b268ecbamr5890215pld.18.1696410620906; Wed, 04 Oct 2023 02:10:20 -0700 (PDT) Received: from [10.254.225.239] ([139.177.225.225]) by smtp.gmail.com with ESMTPSA id p5-20020a170902bd0500b001b9f032bb3dsm3103724pls.3.2023.10.04.02.10.14 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 04 Oct 2023 02:10:20 -0700 (PDT) Message-ID: <58ec7a15-6983-d199-bc1a-6161c3b75e0f@bytedance.com> Date: Wed, 4 Oct 2023 17:10:13 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.15.1 From: Peng Zhang Subject: Re: [PATCH v3 9/9] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() To: "Liam R. Howlett" Cc: corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> <20230925035617.84767-10-zhangpeng.00@bytedance.com> <20231003184634.bbb5c5ezkvi6tkdv@revolver> In-Reply-To: <20231003184634.bbb5c5ezkvi6tkdv@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 7017114000B X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: g9w6867wp87mo8yuw68639uoqab9mksm X-HE-Tag: 1696410622-818667 X-HE-Meta: U2FsdGVkX18eBZf0xzIEz0b+5sVvLRMbz+TCtJwfs7yA3VcvlD7X0uWEHue6Nx+T/Mr6dZhMIWPMdnjiui06mOaAUYe93/LkveV4Gxxyk9NhNfFIkLKWc+2tTC1YEontfTfeioGVTEJnr7xE4V4vZRjT/zfDqbKPFd2BMfJrha3saGgWWsk4O+aI4UtfQZkTnIhGzM1fH1EiPWNTqIU699Jx7wLH9DZT/LaJYRfURBDQQiLc+2QnTduBgtykTXgO8MoPtzceUarPfH8lh91FPzB7jpxojNrpM8tUPWgCLQbRSmPiySQS3lX59TWi7h0SqykRIoChiD+33FsmBg3Si7rJwsrJ0TaJtaYB/0GjIhg+mfzsc/OSlruEm+Ik/Vo3p17K94t0oQHlrWazoxG1Mhpal7cqHybXIwOcZXM+C45N2QGjXv2r9KUtjSJfUukM/pXbbdT4zmlGcTZTDJs0Nt3mvOcI5CM/oHeowwdtqx8sgdbfJOe3vlQFwcV5R1En7fukvIJKAgujHSd6MPJaGHKwGDYteaF9V8q1D0p89UD9g3QI7VfoLfqp9/gpArdd/LffyYLKA8Evvu2Ch9o8n69M4Wh/QUJrM2NwxttEOCMdn2uSqYt0PWTDmb3sIKiQv4z3+LtayRY8micGpr2RBDhGkOxBuw9aC/0VWH5atiBVeIYV43f4ZE+PbnIjKDKT2y5ICQHjAPip1hUdQcMyWmn5lDF+NdwpDiaEyvBavrsLJtgzQjzZXAFr9eDS/YqnaPTM4Up7rAeK+lruWOq5WrZ0r/Mkg5kVrOI2dkQBW5cMJdX2PsW5pYMpVIVlrsh6pq3nEMnlynfp3mPAyaCqemEzzrphTK0iQIRI9p9Z2Oi7dkHNxd6YSwLiW2Gu85LT6zhB/w72WL5FdEVkBTJR7MCwbAKiHdJ2L1krARvvU1vKSOyKm8yPoryjNNE6T8wIGRmDDNPd0c1ZgzGvV0k /EAQ1ON7 qbCz4EafUR+6E0YpNUVpbY9LdXVyFGXRLWJyUCriDQ+2bDuvaE/sHmg/d6EpYZifOW1GOLKhu2f6VF9sTCIcfcX2njO7RpXbn06NaIN1Ypi40IE11PKmwLNCUJxnzETFg/HJGfRxRjBsRhG6qk/YdmCDjJlbu+gLEatyjVMgAeR9cZX+aeqd804eW07tDUfENk62W/rM4LfEHJWi6ngOKkFJEo1o6qsUNWmecepH8rTIEtPheg4F+BlfM4NagMcKuc7EWqAVuZTFAofN3o6q1VxJiccTjB/ZsXfW8+hQPR0BpqFnxOM/+1uLeIma959VQBILx9xDb+YJuvp4bJvZy6hsbvj9DiXIAk7K2qK5eO5pMXie3bzLpGTnuz4tQaUKP6DHibNKZOwptmymANK+s7Srziw2EiDFAqK1nmCLJMU7wEC2ywyyjiXsUV5U93aJn5U8berJWypciub57XL9NqUlEDgQhYa2VZ9Z3Jz8NoObThPh1sq8BmJD81+nWClF6qjk1exdLR22/GIoinr9oGMoH0g== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 2023/10/4 02:46, Liam R. Howlett 写道: > * Peng Zhang [230924 23:58]: >> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then >> directly replacing the entries of VMAs in the new maple tree can result >> in better performance. __mt_dup() uses DFS pre-order to duplicate the >> maple tree, so it is very efficient. The average time complexity of >> duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization >> effect is proportional to the number of VMAs. > > I am not confident in the big O calculations here. Although the addition > of the tree is reduced, adding a VMA still needs to create the nodes > above it - which are a function of n. How did you get O(n * log(n)) for > the existing fork? > > I would think your new algorithm is n * log(n/16), while the > previous was n * log(n/16) * f(n). Where f(n) would be something > to do with the decision to split/rebalance in bulk insert mode. > > It's certainly a better algorithm to duplicate trees, but I don't think > it is O(n). Can you please explain? The following is a non-professional analysis of the algorithm. Let's first analyze the average time complexity of the new algorithm, as it is relatively easy to analyze. The maximum number of branches for internal nodes in a maple tree in allocation mode is 10. However, to simplify the analysis, we will not consider this case and assume that all nodes have a maximum of 16 branches. The new algorithm assumes that there is no case where a VMA with the VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot be applied. The operations of the new algorithm consist of three parts: 1. DFS traversal of each node in the source tree 2. For each node in the source tree, create a copy and construct a new node 3. Traverse the new tree using mas_find() and replace each element If there are a total of n elements in the maple tree, we can conclude that there are n/16 leaf nodes. Regarding the second-to-last level, we can conclude that there are n/16^2 nodes. The total number of nodes in the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1. This is a geometric progression with a total of log base 16 of n terms. According to the formula for the sum of a geometric progression, the sum is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and (n-1)/15 - 1 edges. For the operations in the first part of this algorithm, since DFS traverses each edge twice, the time complexity would be 2*((n-1)/15 - 1). For the second part, each operation involves copying a node and making necessary modifications. Therefore, the time complexity is 16*(n-1)/15. For the third part, we use mas_find() to traverse and replace each element, which is essentially similar to the combination of the first and second parts. mas_find() traverses all nodes and within each node, it iterates over all elements and performs replacements. The time complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all nodes, the time complexity of replacing all their elements is 16*(n-1)/15. By ignoring all constant factors, each of the three parts of the algorithm has a time complexity of O(n). Therefore, this new algorithm is O(n). The exact time complexity of the old algorithm is difficult to analyze. I can only provide an upper bound estimation. There are two possible scenarios for each insertion: 1. Appending at the end of a node. 2. Splitting nodes multiple times. For the first scenario, the individual operation has a time complexity of O(1). As for the second scenario, it involves node splitting. The challenge lies in determining which insertions trigger splits and how many splits occur each time, which is difficult to calculate. In the worst-case scenario, each insertion requires splitting the tree's height log(n) times. Assuming every insertion is in the worst-case scenario, the time complexity would be n*log(n). However, not every insertion requires splitting, and the number of splits each time may not necessarily be log(n). Therefore, this is an estimation of the upper bound. > >> >> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap() >> fails, there will be a portion of VMAs that have not been duplicated in >> the maple tree. This makes it impossible to unmap all VMAs in exit_mmap(). >> To solve this problem, undo_dup_mmap() is introduced to handle the failure >> of dup_mmap(). I have carefully tested the failure path and so far it >> seems there are no issues. >> >> There is a "spawn" in byte-unixbench[1], which can be used to test the >> performance of fork(). I modified it slightly to make it work with >> different number of VMAs. >> >> Below are the test results. By default, there are 21 VMAs. The first row >> shows the number of additional VMAs added on top of the default. The last >> two rows show the number of fork() calls per ten seconds. The test results >> were obtained with CPU binding to avoid scheduler load balancing that >> could cause unstable results. There are still some fluctuations in the >> test results, but at least they are better than the original performance. >> >> Increment of VMAs: 0 100 200 400 800 1600 3200 6400 >> next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183 >> Apply this: 116505 85971 67121 46080 29722 16665 9050 4805 >> +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96% >> >> [1] https://github.com/kdlucas/byte-unixbench/tree/master >> >> Signed-off-by: Peng Zhang >> --- >> include/linux/mm.h | 1 + >> kernel/fork.c | 34 ++++++++++++++++++++---------- >> mm/internal.h | 3 ++- >> mm/memory.c | 7 ++++--- >> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++-- >> 5 files changed, 80 insertions(+), 17 deletions(-) >> >> diff --git a/include/linux/mm.h b/include/linux/mm.h >> index 1f1d0d6b8f20..10c59dc7ffaa 100644 >> --- a/include/linux/mm.h >> +++ b/include/linux/mm.h >> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *); >> extern struct vm_area_struct *copy_vma(struct vm_area_struct **, >> unsigned long addr, unsigned long len, pgoff_t pgoff, >> bool *need_rmap_locks); >> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end); >> extern void exit_mmap(struct mm_struct *); >> >> static inline int check_data_rlimit(unsigned long rlim, >> diff --git a/kernel/fork.c b/kernel/fork.c >> index 7ae36c2e7290..2f3d83e89fe6 100644 >> --- a/kernel/fork.c >> +++ b/kernel/fork.c >> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, >> int retval; >> unsigned long charge = 0; >> LIST_HEAD(uf); >> - VMA_ITERATOR(old_vmi, oldmm, 0); >> VMA_ITERATOR(vmi, mm, 0); >> >> uprobe_start_dup_mmap(); >> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, >> goto out; >> khugepaged_fork(mm, oldmm); >> >> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count); >> - if (retval) >> + /* Use __mt_dup() to efficiently build an identical maple tree. */ >> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL); >> + if (unlikely(retval)) >> goto out; >> >> mt_clear_in_rcu(vmi.mas.tree); >> - for_each_vma(old_vmi, mpnt) { >> + for_each_vma(vmi, mpnt) { >> struct file *file; >> >> vma_start_write(mpnt); >> if (mpnt->vm_flags & VM_DONTCOPY) { >> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL); >> + >> + /* If failed, undo all completed duplications. */ >> + if (unlikely(mas_is_err(&vmi.mas))) { >> + retval = xa_err(vmi.mas.node); >> + goto loop_out; >> + } >> + >> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); >> continue; >> } >> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, >> if (is_vm_hugetlb_page(tmp)) >> hugetlb_dup_vma_private(tmp); >> >> - /* Link the vma into the MT */ >> - if (vma_iter_bulk_store(&vmi, tmp)) >> - goto fail_nomem_vmi_store; >> + /* >> + * Link the vma into the MT. After using __mt_dup(), memory >> + * allocation is not necessary here, so it cannot fail. >> + */ >> + mas_store(&vmi.mas, tmp); >> >> mm->map_count++; >> if (!(tmp->vm_flags & VM_WIPEONFORK)) >> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, >> if (tmp->vm_ops && tmp->vm_ops->open) >> tmp->vm_ops->open(tmp); >> >> - if (retval) >> + if (retval) { >> + mpnt = vma_next(&vmi); >> goto loop_out; >> + } >> } >> /* a new mm has just been created */ >> retval = arch_dup_mmap(oldmm, mm); >> loop_out: >> vma_iter_free(&vmi); >> - if (!retval) >> + if (likely(!retval)) >> mt_set_in_rcu(vmi.mas.tree); >> + else >> + undo_dup_mmap(mm, mpnt); >> out: >> mmap_write_unlock(mm); >> flush_tlb_mm(oldmm); >> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, >> uprobe_end_dup_mmap(); >> return retval; >> >> -fail_nomem_vmi_store: >> - unlink_anon_vmas(tmp); >> fail_nomem_anon_vma_fork: >> mpol_put(vma_policy(tmp)); >> fail_nomem_policy: >> diff --git a/mm/internal.h b/mm/internal.h >> index 7a961d12b088..288ec81770cb 100644 >> --- a/mm/internal.h >> +++ b/mm/internal.h >> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio); >> >> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, >> struct vm_area_struct *start_vma, unsigned long floor, >> - unsigned long ceiling, bool mm_wr_locked); >> + unsigned long ceiling, unsigned long tree_end, >> + bool mm_wr_locked); >> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte); >> >> struct zap_details; >> diff --git a/mm/memory.c b/mm/memory.c >> index 983a40f8ee62..1fd66a0d5838 100644 >> --- a/mm/memory.c >> +++ b/mm/memory.c >> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb, >> >> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, >> struct vm_area_struct *vma, unsigned long floor, >> - unsigned long ceiling, bool mm_wr_locked) >> + unsigned long ceiling, unsigned long tree_end, >> + bool mm_wr_locked) >> { >> do { >> unsigned long addr = vma->vm_start; >> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, >> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may >> * be 0. This will underflow and is okay. >> */ >> - next = mas_find(mas, ceiling - 1); >> + next = mas_find(mas, tree_end - 1); >> >> /* >> * Hide vma from rmap and truncate_pagecache before freeing >> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, >> while (next && next->vm_start <= vma->vm_end + PMD_SIZE >> && !is_vm_hugetlb_page(next)) { >> vma = next; >> - next = mas_find(mas, ceiling - 1); >> + next = mas_find(mas, tree_end - 1); >> if (mm_wr_locked) >> vma_start_write(vma); >> unlink_anon_vmas(vma); >> diff --git a/mm/mmap.c b/mm/mmap.c >> index 2ad950f773e4..daed3b423124 100644 >> --- a/mm/mmap.c >> +++ b/mm/mmap.c >> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas, >> mas_set(mas, mt_start); >> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS, >> next ? next->vm_start : USER_PGTABLES_CEILING, >> - mm_wr_locked); >> + tree_end, mm_wr_locked); >> tlb_finish_mmu(&tlb); >> } >> >> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len) >> } >> EXPORT_SYMBOL(vm_brk); >> >> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end) >> +{ >> + unsigned long tree_end; >> + VMA_ITERATOR(vmi, mm, 0); >> + struct vm_area_struct *vma; >> + unsigned long nr_accounted = 0; >> + int count = 0; >> + >> + /* >> + * vma_end points to the first VMA that has not been duplicated. We need >> + * to unmap all VMAs before it. >> + * If vma_end is NULL, it means that all VMAs in the maple tree have >> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX >> + * when using it. >> + */ >> + if (vma_end) { >> + tree_end = vma_end->vm_start; >> + if (tree_end == 0) >> + goto destroy; >> + } else >> + tree_end = 0; >> + >> + vma = mas_find(&vmi.mas, tree_end - 1); >> + >> + if (vma) { >> + arch_unmap(mm, vma->vm_start, tree_end); >> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end, >> + tree_end, true); > > next is vma_end, as per your comment above. Using next = vma_end allows > you to avoid adding another argument to free_pgtables(). Unfortunately, it cannot be done this way. I fell into this trap before, and it caused incomplete page table cleanup. To solve this problem, the only solution I can think of right now is to add an additional parameter. free_pgtables() will be called in unmap_region() to free the page table, like this: free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS, next ? next->vm_start : USER_PGTABLES_CEILING, mm_wr_locked); The problem is with 'next'. Our 'vma_end' does not exist in the actual mmap because it has not been duplicated and cannot be used as 'next'. If there is a real 'next', we can use 'next->vm_start' as the ceiling, which is not a problem. If there is no 'next' (next is 'vma_end'), we can only use 'USER_PGTABLES_CEILING' as the ceiling. Using 'vma_end->vm_start' as the ceiling will cause the page table not to be fully freed, which may be related to alignment in 'free_pgd_range()'. To solve this problem, we have to introduce 'tree_end', and separating 'tree_end' and 'ceiling' can solve this problem. > >> + >> + mas_set(&vmi.mas, vma->vm_end); >> + do { >> + if (vma->vm_flags & VM_ACCOUNT) >> + nr_accounted += vma_pages(vma); >> + remove_vma(vma, true); >> + count++; >> + cond_resched(); >> + vma = mas_find(&vmi.mas, tree_end - 1); >> + } while (vma != NULL); >> + >> + BUG_ON(count != mm->map_count); >> + >> + vm_unacct_memory(nr_accounted); >> + } >> + >> +destroy: >> + __mt_destroy(&mm->mm_mt); >> +} >> + >> /* Release all mmaps. */ >> void exit_mmap(struct mm_struct *mm) >> { >> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm) >> mt_clear_in_rcu(&mm->mm_mt); >> mas_set(&mas, vma->vm_end); >> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS, >> - USER_PGTABLES_CEILING, true); >> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true); >> tlb_finish_mmu(&tlb); >> >> /* >> -- >> 2.20.1 >> >