From patchwork Mon Oct 16 03:22:26 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422453 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 BFB71CDB465 for ; Mon, 16 Oct 2023 03:23:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5C3458D002B; Sun, 15 Oct 2023 23:23:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5A2BD8D0001; Sun, 15 Oct 2023 23:23:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 461D08D002B; Sun, 15 Oct 2023 23:23:51 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 384FC8D0001 for ; Sun, 15 Oct 2023 23:23:51 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 1321B1CB2B0 for ; Mon, 16 Oct 2023 03:23:51 +0000 (UTC) X-FDA: 81349880262.15.1BB6A53 Received: from mail-pg1-f170.google.com (mail-pg1-f170.google.com [209.85.215.170]) by imf25.hostedemail.com (Postfix) with ESMTP id 2DA33A0008 for ; Mon, 16 Oct 2023 03:23:48 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hK69Oizh; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1697426629; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=YVqlJjWp+julEUMAnNu/poDkRQ8jCvWS/3JoCR4jyXk=; b=BHvmYiubG2SCXQtXGmpzR8LIcJFVnuRhjrS2BCSkGP5d4P3R1kSOaCsUL/omfDtKuksOGl bi1Ez8hUiDlGxY7LZ44b0tjIqLvVOu6aleTJWYjzfMAaS54SBfrTU08mw6SPUMHTdTu9fD Wi/kRoCugPPPW+Erb17MMJdmXPDuYYY= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hK69Oizh; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426629; a=rsa-sha256; cv=none; b=GMF5YJ6OLn3JcQS7O+KrzQGC+WHSCl38fdxXkdTUMApAXqQ3j2j/VzBlrEYye/+BLqG/l+ aO7orVkjIqVXF3rkcFzWDXsBjD4VMT86BBfVIZOlcp4de1dNuwMU2sDPLtXLc//eCTw8LJ O1xoUlHxRMVojSs+4OGVW5lkqcVK4c8= Received: by mail-pg1-f170.google.com with SMTP id 41be03b00d2f7-5ac865d1358so1336139a12.3 for ; Sun, 15 Oct 2023 20:23:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426628; x=1698031428; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=YVqlJjWp+julEUMAnNu/poDkRQ8jCvWS/3JoCR4jyXk=; b=hK69Oizh1pZSOumq2gLG36fPDnJJ2mUI6uAW8w9B5MB9Qjt4DDfXT6L8TlBP2HaI+r /7w/WPRDurANcZdBlVxuY7r6P7ty0dmJFbEKAK3JYXQtvh90uYCoWm7/GYvSwAGnopR+ FXDQWrEo4ZR26DGPg+bUgkuoU3oYfHBEynlH3z6Job55tVpcj0/WyJJL5Xk/g7yw9xfh vw50jocEUAd9FgdZ4+JYhAcBtN/KeA8+nPEUEtYK6GpKQFDCihlgxHmNn+hNjdbBUo9Z R9FhX8yuESVMv2D2uwViW7/n2GuT9U4GLg+qss+86O0tza/WMLrs2plddA0EjIbIiioK 4xWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426628; x=1698031428; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=YVqlJjWp+julEUMAnNu/poDkRQ8jCvWS/3JoCR4jyXk=; b=Q04F7ypY4QitM2+aUkimwnccH/hPrLdPVhR6YI26Xwjq+2nECmmltQD9dhTh15awuN 6g3b9E79txznIjcdlzgNHCPIbP0KF4kvCT6kkOG1ZlTTkXP3guNu7oRzG/ruivgwoNX3 wvlbu/MdqhSHecn833fn1jLvmqWFyv7w1qKRRfBc0mdI6XAbF2expH+lGulqli1x1iGA GD9px+xgFX5smRAmYUkDN+tU4bGiQ25TWzkINyxbfkaac55unjhna6nN8fGyXAelutP9 /yCpCd6ctSOnSrbB2H2WYpb2VX0vL9hEXeWnGlbGe9L4+P+zOGrmv1vNYlnKSMvEUl9v iKaA== X-Gm-Message-State: AOJu0Yw1qAAc6MzTck9wa++Y1l2XiCYY6jYqFpaf7IB10wBpz93MofGW ZF25J324CLZE5StmhfNgPvLiWw== X-Google-Smtp-Source: AGHT+IEbtACnFwjalGKrQUsNTxnw+Q9lJ3N5Y1iJnUQdx2iVRQ7BWuSFP1gHP8DWufFa6yDaaFK+cw== X-Received: by 2002:a17:90a:7782:b0:27d:5cca:9b69 with SMTP id v2-20020a17090a778200b0027d5cca9b69mr2361681pjk.45.1697426628084; Sun, 15 Oct 2023 20:23:48 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.232]) by smtp.gmail.com with ESMTPSA id d8-20020a17090ae28800b0027758c7f585sm3452770pjz.52.2023.10.15.20.23.41 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:47 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, 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, mst@redhat.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v5 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Mon, 16 Oct 2023 11:22:26 +0800 Message-Id: <20231016032226.59199-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231016032226.59199-1-zhangpeng.00@bytedance.com> References: <20231016032226.59199-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: yfnfeuq9xecr5up3bwksz77ak1t33bqg X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 2DA33A0008 X-HE-Tag: 1697426628-803794 X-HE-Meta: U2FsdGVkX182qN7tOL9GRWtZGZt3x5XYCcd3Vpe1zNRo7WNoLTtJyY1Ou2IXPatfdg3ghasXwGhiTGi1zmidui2rlXCsPjMoUCErKqVxIzYlfBvm3B01uHwVKxj/F8TDEECfqsGeVvMkJK36VS2OYYw/5TDv84sWoi/lQESnevoIcko/QXmxgmwCRXJ4Tmax/kN95l27V6ZqYEEA2bdOjbJRTmpPzo/yEGLfeRlwDRKhLiGC+Vipm/RNarO5+qPzroZNelx/6cNmVxZ/bMLyP0FDC6cihu7ZugflqLaJ6IF381K6OWwrkunQWpZedN9VmAhCU4nkzJYm4+Pu4Z2FST+wZtjqCWwFysUAH1l+RaMU89I2wOb/dwf2+4S9ajgr5J06Wyhdgv/qINyRIH/vsQU/vehOYUv4Tq65I9NU+u8HQVjwuLA1NIklWrKNAPFgloGFUsVNjd4GC84hbvYdK7QDo//Hi2dR19+hH/mUkWxUTtQMvxgpi95/RsYVD2Zq33VPjwqVjtF2GYRmSnnxBRfW1HrfqwV92H9EM3vWZLLH+Ss6Nnwk//oxYx0Unly1j9Vx0sMlRce9r5R+mDrVGjlchzgLv8psR8Ee7yzqK8DU+lhN/LNc9NDdGohSw4qJojxa9wO2cL7RqLJdiq8Qex3vtR/asCNHm1z4CuvcfE4/7RC3QLjLKkTaluAfbZ9aSuZJK5mfVh1LXfwYaAmOPKe8YM1FGpPnY88gcFz2O+XbZ4Qv12XUaXTZixsfzLhkfGrwjDJ77oreVuN00Quc+NxFDX7PQiXLCatnlqZLR7zMFGgeIFrJcQ55pkeEBm7VKywJQM0GS6K126T1r++RR+kYihYSWrc7nYATv/UH9ZbctRqasXwjnSBeNy8lcKBiTyzXpFE2pFx+5bw9auHusY/tWbE8ptfbP09bz91cBjHh318GlN52XmngZ9hB9ts4fZQXIVItqh951Upb5Kn U2r379jV DZKtzumZnKbNNj/odF1bGkyqGncoDeEFxNz7QmAD0pVHsRvm1+hmY4L64e7lt17NwAEJcUf8wsEQCg224T9pNTNLs6/puaQbK7bWvnk/+5v7MsJs5Fu8fWi8qqmD70j5YxffeHLZB/m/w9lwvCDI6JjEGjgOoB7t3IxALk6zzKeleU+wzF9knYtosBhoaOiTDQCFt2DNA2LEQRDB7dL3c4dPpLgWYeVNYC6eJMTY5a63fnxfUcFX4hwlITp54YWc6RMuFXiT2WprkqQlU24KKS3VwhZ0ll1SbRcUL2tM/pNI+ooR15Mmvt/Xt7r/soss8E9jy1b73H7lHC/1rjxSRz/rTFas19FPc7L6Ix/I/h5NQZTAOdXDxbrdwaO7YS7dZAq/73VX+cmovGNuy3f5lGOCBuglLGAvJNhOzRJLDECYhhxqfb2TySwEo1N32mbZRR8X5hqpTXWHa47NP1+3J1M8FlJfjMrEUqgQl6fwS72fRWRQW2GQnq1pX/NYA147nJtTX 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: 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 efficient. The average time complexity of __mt_dup() is O(n), where n is the number of VMAs. The proof of the time complexity is provided in the commit log that introduces __mt_dup(). After duplicating the maple tree, each element is traversed and replaced (ignoring the cases of deletion, which are rare). Since it is only a replacement operation for each element, this process is also O(n). Analyzing the exact time complexity of the previous algorithm is challenging because each insertion can involve appending to a node, pushing data to adjacent nodes, or even splitting nodes. The frequency of each action is difficult to calculate. The worst-case scenario for a single insertion is when the tree undergoes splitting at every level. If we consider each insertion as the worst-case scenario, we can determine that the upper bound of the time complexity is O(n*log(n)), although this is a loose upper bound. However, based on the test data, it appears that the actual time complexity is likely to be O(n). 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. To handle this, we mark the failure point with XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, stop releasing VMAs that have not been duplicated after this point. 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. The first row shows the number of VMAs. The second and third rows show the number of fork() calls per ten seconds, corresponding to next-20231006 and the this patchset, respectively. 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. 21 121 221 421 821 1621 3221 6421 12821 25621 51221 112100 76261 54227 34035 20195 11112 6017 3161 1606 802 393 114558 83067 65008 45824 28751 16072 8922 4747 2436 1233 599 2.19% 8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang --- kernel/fork.c | 39 ++++++++++++++++++++++++++++----------- mm/memory.c | 7 ++++++- mm/mmap.c | 9 ++++++--- 3 files changed, 40 insertions(+), 15 deletions(-) diff --git a/kernel/fork.c b/kernel/fork.c index 0ff2e0cd4109..0be15501e52e 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,21 @@ 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) { + retval = mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL); + if (retval) + goto loop_out; + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +753,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 +766,28 @@ 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 (!retval) { mt_set_in_rcu(vmi.mas.tree); + } else if (mpnt) { + /* + * The entire maple tree has already been duplicated. If the + * mmap duplication fails, mark the failure point with + * XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, + * stop releasing VMAs that have not been duplicated after this + * point. + */ + mas_set_range(&vmi.mas, mpnt->vm_start, mpnt->vm_end - 1); + mas_store(&vmi.mas, XA_ZERO_ENTRY); + } out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -778,8 +797,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/memory.c b/mm/memory.c index b320af6466cc..ea48bd4b1feb 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -374,6 +374,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, * be 0. This will underflow and is okay. */ next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; /* * Hide vma from rmap and truncate_pagecache before freeing @@ -395,6 +397,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, && !is_vm_hugetlb_page(next)) { vma = next; next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); @@ -1743,7 +1747,8 @@ void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas, unmap_single_vma(tlb, vma, start, end, &details, mm_wr_locked); hugetlb_zap_end(vma, &details); - } while ((vma = mas_find(mas, tree_end - 1)) != NULL); + vma = mas_find(mas, tree_end - 1); + } while (vma && likely(!xa_is_zero(vma))); mmu_notifier_invalidate_range_end(&range); } diff --git a/mm/mmap.c b/mm/mmap.c index 1855a2d84200..12ce17863e62 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3213,10 +3213,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); vma = mas_find(&mas, ULONG_MAX); - if (!vma) { + if (!vma || unlikely(xa_is_zero(vma))) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); - return; + mmap_write_lock(mm); + goto destroy; } lru_add_drain(); @@ -3251,11 +3252,13 @@ void exit_mmap(struct mm_struct *mm) remove_vma(vma, true); count++; cond_resched(); - } while ((vma = mas_find(&mas, ULONG_MAX)) != NULL); + vma = mas_find(&mas, ULONG_MAX); + } while (vma && likely(!xa_is_zero(vma))); BUG_ON(count != mm->map_count); trace_exit_mmap(mm); +destroy: __mt_destroy(&mm->mm_mt); mmap_write_unlock(mm); vm_unacct_memory(nr_accounted);