From patchwork Wed Aug 30 12:56:48 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370227 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 CC35FC6FA8F for ; Wed, 30 Aug 2023 12:57:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 279FF44014A; Wed, 30 Aug 2023 08:57:23 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 229B0440009; Wed, 30 Aug 2023 08:57:23 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0CC6244014A; Wed, 30 Aug 2023 08:57:23 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id EE5FE440009 for ; Wed, 30 Aug 2023 08:57:22 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id BF969C018E for ; Wed, 30 Aug 2023 12:57:22 +0000 (UTC) X-FDA: 81180771924.27.FD7164A Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) by imf05.hostedemail.com (Postfix) with ESMTP id 3D0A1100003 for ; Wed, 30 Aug 2023 12:57:19 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=JUUd8OOx; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400241; a=rsa-sha256; cv=none; b=xc0AnNuMSzTcwXuZOaM5Y4JykniJ+k15sOgV1PJXUNmYr027NhBBv2k4AxhO+fOrOXTo+H 9pnjt5NbsWb1UCQXcVKaHRDVderNRWHelTqz46929KLy0w+HoSQgWPjNgosyZumSMb0YEC jX077k2ThgMGBx0hP+17Bazgfwffjcw= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=JUUd8OOx; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 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=1693400241; 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=dtd6q3SyxBvaZmQAvE8P+QtZVZRCjxwa7BoiOx4Ow2A=; b=RrDe6w9lb4/kifp5bGlzgK0ZhqTgAcn4ej3jCR+0+9KpnZ550ZUOJV0kH2HwKYF/nGKggQ 0J/H5b2mLvnckKvyObxvhyKTEtUSjRKXkkhpQGES6EKY+U0E2m+gdUh5IlM4ZzD3RmZ+1J iNpYOcwL/IKBll6gS708CGxz3vTgwhM= Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-1bdc19b782aso35310315ad.0 for ; Wed, 30 Aug 2023 05:57:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400239; x=1694005039; 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=dtd6q3SyxBvaZmQAvE8P+QtZVZRCjxwa7BoiOx4Ow2A=; b=JUUd8OOx+AXv0CorxYe9EsxaAYmVSQMLOu6PF4GLfxZuUaLl4cQuLicNwAOm5uxlpb kf30uO+BIZBhr4rO+084KHfuhIKmBN3L8AVmWspMnnnSm9tCKIflj6P+xNUT0q2TleZi en7Xu7dDWfv42hLmYEkWVmbiwv9iCpfJZVBcOC0AYjSbBLD+dL/5o3bqayRUA8qwdm/U DXkoEJBJpwR8qVFMJD0anUI27D8f664+NPEsdOfzNm4yZteyXArc2SmUoJvv95aAezx9 076k5RvtqI2lYeHNbNPR/kQqyb7gAK+TD08EJOHQbf2EK3Cbn9MS1isU8Ip5ApvlaV0F 3H0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400239; x=1694005039; 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=dtd6q3SyxBvaZmQAvE8P+QtZVZRCjxwa7BoiOx4Ow2A=; b=Msxv6PyG3bTJIsqflWslZq5S76fkjrTtY2qyc64BwzJKCiPLxUl7a5XoTlD/nzkIho Slo3GxbfYO4QmOM9vWM3U06NC7Y4c0IqP237BvJUPF8ws1M6NQsdZO4RroqEfavPX+mp SxD/zuaF6fE27UW7bevtFVeZSrQmVCWv5i/DjnWo8eLuAw3VryK6jMh5c7o8lK7EWiH8 eb1BQlMMePN2MqeZQcKFQOoQDq/dc409/ZHUcca9xa4Bfq9dTBZvaxEFVFJMGegQjqqG dq+TYhRk3Cm8pms8mo0FjRIPEFbg7UAXdfpWh6WlQz92Pg0UPnAQlaS1mP09BLHSCGYk 807g== X-Gm-Message-State: AOJu0YxE5vHzJ/ToEXhgmRc/3N1eeq5NtoJ3nqIhD5N3AzRta5AaNpsP oODPs+lL5DV81QjSB5/sVJu28w== X-Google-Smtp-Source: AGHT+IGKPuYQWBKa1a4+1P4c5NUAY3fS0w+iEhxnmdtT4j9dZZVQZKmRW9OE8TVjanTCPupqydzJDg== X-Received: by 2002:a17:903:110d:b0:1bf:6c4e:4d60 with SMTP id n13-20020a170903110d00b001bf6c4e4d60mr2040423plh.3.1693400238850; Wed, 30 Aug 2023 05:57:18 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.12 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:18 -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, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 0/6] Introduce __mt_dup() to improve the performance of fork() Date: Wed, 30 Aug 2023 20:56:48 +0800 Message-Id: <20230830125654.21257-1-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 3D0A1100003 X-Stat-Signature: 5znxtqbn5o1jdw633oy58nkoi1ng7p8e X-Rspam-User: X-HE-Tag: 1693400239-140584 X-HE-Meta: U2FsdGVkX18N3l6/qjM8H/goc86aD/6V4ffiOmFQepsE1BJMmVy9Q9D0QtDY2/2iZWRleZycRuVMjntQN9AQOc+KN32ZOza5gkfu51+pfJocLfoUbDqD4EeD7MhmdS9XrNSDU3g6v652aAAfcSCHqD9nVmR09i/3W1Fs8+11GetKvR3erDYLJGZR+kJ0LJa+QF6RZLwNe3NccGThYH+A3kELUEzDHZJ3EWs2eUIx1TrMMh3jq0Eq5h8CD640VC/P5YAUKNaUv8Gimt1Jkhn6vWaKz3LhXOlNJO9OlnMmZdZv5vCGMxN7Hl4fzkzuXJQXNNs50bXvzALMUUC4h/Nfea6XVM6ukRkeUZU71aFWDXcIXureCUIy4swr9/dCn/Pt1StLKILBa5hwESxpTLTsLl+w4nAQjEYvtXbO9IwegcTEdLWwAv5TF1lFRStxX3IyKOoFyZ/LXXo+UZfQhLxNnQ1offTbmr12k8HZnnEGL84NxAfmRu5YvFBnjZzLGI5nkkZET8dpaODGjaC6u5wYjPVN4hAC6bZJXiXQ0vibFZUf0hYViHfGiC94vBJ8vY2IaXheb83SR1xCAIN056ALe0N46O5JLL4jeH+60oYXoXcnE4CIJTZPYx0hvblyA/JErxWhQn2rimKmsRkFS+++xH43SBcmoD7AvLzNfJmTnzjpi+UvDC9TRw/mF5koSN59NX5078yjE5aANpeTGKw64dHLs66WxuihDdmvp9lgIMYA9xm3JiUZ2q6f9ZiPx05AzqBQUiXTil6d0sheHtkpM3u9gSL4slfyUsyewNTvu+KRYy/tLRjSLMO3r7XHnvY4Gs40aW6EIJ14J6/inKFC99fhZqYhZmoWhsot4u0/nn1UrdGfKqdnVHYf1jZnkWSKexdQ/MUHglvmAgJPws2TcWiQ658O0wvJZuKOetuWSIMBmcISq21v/G3nsg+Grovy6gts+oXw8ADpvJDVuzj Shaq9MrD QijK7FK2QYUo4KGzx/vxxiSdgqh6dEvFPZV7pZJm3D/Qk10LrMlvIHms+iXU+mZMa974W7VB7M76XUJcq6YRdRNealKMtGSpCQmE/ovPnX4c+iDxFYT0BjZf1uia7MF1CvqFgM8g6yE62xBxHihVCRA4gsvq4lnZ7et38QkUsObTxJkeEkwysPBkRq8SteNdO5hnPC5FwpB35II8zYR5FrkwOvFRCss5tWiAMb/qVFNK+POQ9BzUjqKnOQGkS92OfLXi1coyZJP6jxvzCCtkzN0Q1Iw+AChG7gR5IA8yLDOofra3msgBWryfK+uaqVm8yqILGoKD75q5kFZdy7uLRola6Uaeon+si2yDwTEzXyhcMevpWYaK1CCMQtf83flQw7pt4famGp06XZe4WLWZsOOErsKslOHjALz1i4siwjw59xAtb2XO/SM+jixNm8JZQF7yZZGg7wCmC7nQqwhxZG9/G44KaeD2N3oY6TZsPy58q+/AKOvYPVQnnfYlnC8swfrNXoBug/hVePOAUrBV+UyS/Bmu0aImyb78shPpMLELJjZTh0Q1xrwe7BZTQg3Pw0CD+ 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 the process of duplicating mmap in fork(), VMAs will be inserted into the new maple tree one by one. When inserting into the maple tree, the maple tree will be rebalanced multiple times. The rebalancing of maple tree is not as fast as the rebalancing of red-black tree and will be slower. Therefore, __mt_dup() is introduced to directly duplicate the structure of the old maple tree, and then modify each element of the new maple tree. This avoids rebalancing and some extra copying, so is faster than the original method. More information can refer to [1]. 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 numbers. There are 21 VMAs by default. The first row indicates the number of added VMAs. The following two lines are the number of fork() calls every 10 seconds. These numbers are different from the test results in v1 because this time the benchmark is bound to a CPU. This way the numbers are more stable. Increment of VMAs: 0 100 200 400 800 1600 3200 6400 6.5.0-next-20230829: 111878 75531 53683 35282 20741 11317 6110 3158 Apply this patchset: 114531 85420 64541 44592 28660 16371 9038 4831 +2.37% +13.09% +20.23% +26.39% +38.18% +44.66% +47.92% +52.98% Todo: - Update the documentation. Changes since v1: - Reimplement __mt_dup() and mtree_dup(). Loops are implemented without using goto instructions. - The new tree also needs to be locked to avoid some lockdep warnings. - Drop and add some helpers. - Add test for duplicating full tree. - Drop mas_replace_entry(), it doesn't seem to have a big impact on the performance of fork(). [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/ Peng Zhang (6): maple_tree: Add two helpers maple_tree: Introduce interfaces __mt_dup() and mtree_dup() maple_tree: Add test for mtree_dup() maple_tree: Skip other tests when BENCH is enabled maple_tree: Update check_forking() and bench_forking() fork: Use __mt_dup() to duplicate maple tree in dup_mmap() include/linux/maple_tree.h | 3 + kernel/fork.c | 34 ++- lib/maple_tree.c | 277 ++++++++++++++++++++++++- lib/test_maple_tree.c | 69 +++--- mm/mmap.c | 14 +- tools/testing/radix-tree/maple.c | 346 +++++++++++++++++++++++++++++++ 6 files changed, 697 insertions(+), 46 deletions(-)