From patchwork Mon Oct 9 09:03:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413121 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 B4258E95A91 for ; Mon, 9 Oct 2023 09:03:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4ADA68D0024; Mon, 9 Oct 2023 05:03:46 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 45D468D0001; Mon, 9 Oct 2023 05:03:46 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 325298D0024; Mon, 9 Oct 2023 05:03:46 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 21DFD8D0001 for ; Mon, 9 Oct 2023 05:03:46 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id E628840119 for ; Mon, 9 Oct 2023 09:03:45 +0000 (UTC) X-FDA: 81325335210.19.D6DBBCF Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) by imf23.hostedemail.com (Postfix) with ESMTP id 5ECB414001E for ; Mon, 9 Oct 2023 09:03:43 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=QJTVINcV; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 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=1696842224; 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:references:dkim-signature; bh=zVPBUts0sM4ll2vXGLp7ZtXBxcW/h1TyBHpbZpV8ZlI=; b=SwZNx1u9zW0fpUPlKVjQ7QzkuhnRA5vv20UqJw6fPCs5TPH65IFnYCkU1olggEGc24v8FZ KTvAt/uFBsmN65oL5zatiz+EIi4+Mgrhbe4zgby7r5kjm5JmJ1slHY+aPOaajjIOU+2eV1 U/Uga+e/QtPwxplRMU1fOFO/qU9NwRY= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=QJTVINcV; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842224; a=rsa-sha256; cv=none; b=4NF4GhRtu8jv9OsSDkN2o1nMTz2C8FIm95AV86p7T2vvn4jkxf04GreL9VumcsPATUHF26 VG32Inh5oDXcVdFolXustg82aTWcajzhLHWzo5I7y+yFmW2FJSeXd4HNKUyGQjbE6REYA/ wSLJ2j3vYM3IkjO8upBHkqlY79tZyvU= Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-693375d2028so3845852b3a.2 for ; Mon, 09 Oct 2023 02:03:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842222; x=1697447022; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=zVPBUts0sM4ll2vXGLp7ZtXBxcW/h1TyBHpbZpV8ZlI=; b=QJTVINcViMy3UeILyvef/L0W1CBM6Qs9GQolHYmIMYNTHQ8FuL6oJrjgNTbqQJZ4Yf oq18WoPRo9K+AcSAbcxLpggWqowe07Xu1D+TDZsN5lWQZQlfoEBOlnpG0YqfWjxcPzcc upL8KMa5A56WM0/bKkJifbLRzlrS/FUdggDFsgMqmA3mV+3LSzMZ5214QVJrhBlcN5TL kgE7CfKFYoHyESmN2zu3gwVrr3gicVaumwDPUqZnytzBW9I1OXz+QnHXhR/XD0ErKP4G jEVJVJkI+J07j1bL7nb54gmlmACsepXvotW7aQFsXAQSzQSO9SrdAw2W/lnx7rfGAQK+ Rf3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842222; x=1697447022; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=zVPBUts0sM4ll2vXGLp7ZtXBxcW/h1TyBHpbZpV8ZlI=; b=RXLxvYNyYfwj+wffi43KMoYkMprw6/3kdo1/HZpPZm8x9JXD8VsLnPy6595/RIuHpr Vcv03wPyfsA2dDCT2zPgvK4bUrTVRO02L2rKYUKcz+9DMUBwjXNsJN6E/aBbAQr5Vmga QOCkXTW+XmiR3Luccj3Ph6SUbHfIxxyMKstNNrS1QLMQEiA4hpTFmISJIFSkC1KyCWNb tMl6lMUV15w9Odkz6U9kfGk7tV+bEByPf6W7D/xRAYpxhGwr5h90wLRbTXgiONoWs6TI iJolYM5lziziWz+NjcMilvvJ6qg0FFjGelAeXnZJvej7PC8shLZ8lmrjVuPAFUJasSQ5 I4KQ== X-Gm-Message-State: AOJu0YzAePGTbHYUUz1rmdan5SgVQx+uVw0L4gXSpQnH+VAQMLCFtgwS zrP8lxWVOqPLwZSzv0Bi9P9b0w== X-Google-Smtp-Source: AGHT+IGL5ggcIxz/u0/Y14JkIJ+W5YgdS64GhkUPDuRS8uFzbKt1pKOfnH6ukCzYRqW5rAeL6aDlFA== X-Received: by 2002:a05:6a20:72a2:b0:16b:d470:b403 with SMTP id o34-20020a056a2072a200b0016bd470b403mr9389736pzk.28.1696842221863; Mon, 09 Oct 2023 02:03:41 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.03.35 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:03:41 -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 v4 00/10] Introduce __mt_dup() to improve the performance of fork() Date: Mon, 9 Oct 2023 17:03:10 +0800 Message-Id: <20231009090320.64565-1-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 5ECB414001E X-Stat-Signature: 33y9f98sh8s75n3g9gcqpm58ne5cofnk X-HE-Tag: 1696842223-524940 X-HE-Meta: U2FsdGVkX19qEhu2FT6dBI3Ko28KSconO0Op7PF+XvGk3O6qmOzXhxRLuxTibG21dwiK7rHDsWrElQTCwW6uR22oratLERtTZfvTTWicXoPFoNJ9z2TrOfL9nHwwNVOoB9lj83HZiFJrE1NrLzdH/KGHhdVbpJ2JfCj42k8VacVX9BhLBiplDRMw1yCGzLUjSASoeqD7+bQw5xp+yYC0FF/uimPUaxrcUCD/VTJAqyptVrEC/bZ5QNdpOsanBEbQML8WNXrEPaZbVcuV466PqOdQP1vfAqlCHIHW9UnB7V0Leqv/oEcHl2kKPDKfeQaiVYpmg/L2Uv/fLu3EfdzpKr5zNJ22i/+Ye+mEkKNTU4lyQOimJ/BxKrQzYnaI5LmhRwQH7vVTYv4XHSBQvHhLI5YP9b2BgTYirRVY3QyEUMWfYENFgn/5eSwpDLP96dCXSfUiE24eWCz/Mzojk53MpPol7FSjvS1frqudmrESTkTyfE0lDvbPboka+4BIkHemEOJMVq87gGVi0uGoh34OLnOXNP/aMjPrGCeo8lrxIhvlBRpkPjfIiJ0pHPV738Pz3mWcI6C+6Z/hr4g7Gvga3PYEFHy2WsQnl9QgSWIs3N8u92hYG7UtypQJWgyY0Rk6XAyuOfDubt/Degxes3CFO2JWniVXKI+eNM66AaLU9rpsaBkzTTpYaVq2p/CSX4isxmrHmRoK3KOmBN2udMKdL6GnWvgFXdks0ke8Jb6SrWMP+ntvnmI6rqUkPEtVoqQthAC+cypVZ7GpI41HDZk0PqmG3f2DvCVl6SDIL78BQVgXILMxK+rdUU+nH9Vaa10UxAVIUOjdW5tFD+UZ3Wub1Ks5zz9pdC6GT5IsThe0BTA88Hxn8EfICh7iR8HKAmGGpGrAJqDoC+ZOpbgcCMhpf9iQEOSCJbqcUWr6dziQzDejIFRq3Q1KsDdevK6mOIu4tiOK1unK2fbV18oHFlR JlRIjudH OZrk2FAY+d9YhiLP+1W3AC4SjaPIcKUr/dLQL6hyUVlz2ACQMuEx0rhCYCYj+08R0rz5Iq3oPEvzkTMFv9OnaJAHINOLOn/2MKqDC+BXy4vQhisgbagOF0hb/gTkW/WZmO4rwtwDsg9aYpCPV9kuEystwAHZUuQpJxy7FByP6tH872SEx3XxLJmC9MUGIY4D+58q8CA3tiU/tu8E293LAvaaf/LFZjLTEJFekU0B3ozaGnxXClsy5SZrkXjQoOOYV/o4yGE6zeBoC1LnGt3prIyVSDK5qekpuiBPaxtI4ZUKj0GDw1a8eMnng1SLXyBLMH2DQzOiuULbbS3AAJvgwF8fYguhITSWQco+W4K35OoiH9b4xYf+XHQaqyXnzz31DlCCMULyTh8AJgpEDkMT6CCa8Y8wZ651Sat/jox6G1XpxIQu6LSrZn6xizspp2KeB81ijwCQocv8lCs0dsUBSDlBrn7zp4E2syoPy 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: Hi all, This series introduces __mt_dup() to improve the performance of fork(). During the duplication process of mmap, all VMAs are traversed and inserted one by one into the new maple tree, causing the maple tree to be rebalanced multiple times. Balancing the maple tree is a costly operation. To duplicate VMAs more efficiently, mtree_dup() and __mt_dup() are introduced for the maple tree. They can efficiently duplicate a maple tree. Here are some algorithmic details about {mtree, __mt}_dup(). We perform a DFS pre-order traversal of all nodes in the source maple tree. During this process, we fully copy the nodes from the source tree to the new tree. This involves memory allocation, and when encountering a new node, if it is a non-leaf node, all its child nodes are allocated at once. Some previous discussions can be referred to as [1]. For a more detailed analysis of the algorithm, please refer to the logs for patch [3/10] and patch [10/10] There is a "spawn" in byte-unixbench[2], 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% Thanks for Liam's review. Changes since v3: - Modified the user-space kmem_cache_alloc_bulk() to align its behavior with that of the kernel. - Made minor modifications to the comments for {__mt,mtree}_dup() and their sub-functions. - Made minor modifications to the error handling of mas_dup_alloc(). - Adjusted the code style of undo_dup_mmap() and also fixed a potential bug in it. - Rebased onto next-20231006. [1] https://lore.kernel.org/lkml/463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com/ [2] https://github.com/kdlucas/byte-unixbench/tree/master v1: https://lore.kernel.org/lkml/20230726080916.17454-1-zhangpeng.00@bytedance.com/ v2: https://lore.kernel.org/lkml/20230830125654.21257-1-zhangpeng.00@bytedance.com/ v3: https://lore.kernel.org/lkml/20230925035617.84767-1-zhangpeng.00@bytedance.com/ Peng Zhang (10): maple_tree: Add mt_free_one() and mt_attr() helpers maple_tree: Introduce {mtree,mas}_lock_nested() maple_tree: Introduce interfaces __mt_dup() and mtree_dup() radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. maple_tree: Add test for mtree_dup() maple_tree: Update the documentation of maple tree maple_tree: Skip other tests when BENCH is enabled maple_tree: Update check_forking() and bench_forking() maple_tree: Preserve the tree attributes when destroying maple tree fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Documentation/core-api/maple_tree.rst | 4 + include/linux/maple_tree.h | 7 + include/linux/mm.h | 1 + kernel/fork.c | 34 ++- lib/maple_tree.c | 300 ++++++++++++++++++++- lib/test_maple_tree.c | 69 +++-- mm/internal.h | 3 +- mm/memory.c | 7 +- mm/mmap.c | 50 +++- tools/include/linux/spinlock.h | 1 + tools/testing/radix-tree/linux.c | 45 +++- tools/testing/radix-tree/maple.c | 363 ++++++++++++++++++++++++++ 12 files changed, 818 insertions(+), 66 deletions(-)