From patchwork Wed Jul 26 08:09:05 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327563 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 8D20EC001DE for ; Wed, 26 Jul 2023 08:09:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EF75B6B0071; Wed, 26 Jul 2023 04:09:52 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E59376B0074; Wed, 26 Jul 2023 04:09:52 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CF9358D0001; Wed, 26 Jul 2023 04:09:52 -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 BDAAE6B0071 for ; Wed, 26 Jul 2023 04:09:52 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 8F6D8A0132 for ; Wed, 26 Jul 2023 08:09:52 +0000 (UTC) X-FDA: 81053039424.16.3A77164 Received: from mail-il1-f172.google.com (mail-il1-f172.google.com [209.85.166.172]) by imf13.hostedemail.com (Postfix) with ESMTP id A45C820027 for ; Wed, 26 Jul 2023 08:09:50 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=HnjyOJ+l; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf13.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.172 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=1690358990; 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=+2dLh/uGiMpMzYsXqB2cYj7xJxo2Ps0eqGhMV20FNlw=; b=B+DBHhy52XRXrGyNvp2U28p8R7KGAxfcgGORejoduEkH4n0+AwF7iQ/1nBhUnMJi1mY/We Fr4YKOwieTy0lsl0reC/Io1YZwZ6sUKje55W+bOa8UdiJyJ9LVyZi0mwv6QLl61nVdJ4py 0lkDL9/ks9lOlWnLQ/5r7MrocZ+q2vM= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=HnjyOJ+l; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf13.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690358990; a=rsa-sha256; cv=none; b=AA4geNddkhI8Utge/7w67I+T9U5J5LRBLAwF3S9yS8SKkJ7NjIVQOnKKmCiewA8+4XCTlU IeIBKcleMQ077K+HjmvNdQs+65/elACcmGzagAht6UF53sNR+XR5NbqzDQL6DWRHoDScZi 4G/9GMhE2r8hvCpSHXkG059HAa60oJ0= Received: by mail-il1-f172.google.com with SMTP id e9e14a558f8ab-3464c774f23so29972445ab.1 for ; Wed, 26 Jul 2023 01:09:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690358989; x=1690963789; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=+2dLh/uGiMpMzYsXqB2cYj7xJxo2Ps0eqGhMV20FNlw=; b=HnjyOJ+l7FNJ7d3Q68VgFo45FqzJSVRLcLrWfoocPC/tALn5DwJ4EzCz6W2zsrl1tz m3xlYewQbRATIsLvNNYPEJsYsl3PaTdzyv7kUE7HzT2iiN5tVv5fk67BbLok6xfsDglz lU/afwdiWaHWXRDAOoK5kDrJlpCGkJuXL64YymOBIZvmOoI++RDrLc7Dgc6YsYlGppKe 6yOlbC8kUtF4kcYykHIfxgVOFj4YoHQI7Ao5fFiBl4qpCYtm6n3zG1pn6VjEETMTsTJk BUKdur+CWRhocn35XByLCs68leeyZwgl8WydRdFQOn8JRQhPG60TFo1IWAW8OOk8edTw V2gw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690358989; x=1690963789; 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=+2dLh/uGiMpMzYsXqB2cYj7xJxo2Ps0eqGhMV20FNlw=; b=kMvcaLn3suQituzP+SO34hxvcsuvt6SjAi0SVSPh6ZG4xckVoYWV/cyK3vDrc0B9w5 dDgPxW4+i0WsvjyRc2GXvlEn6bW4EXyslBjcLAMt6fELGBUmVUrTENYN5NxI/Q7wmBlH m9WmlvuwjXAlLolywyZMxNjPyY2h4RdX/7NcOLmjsgNMVpgeEbtczLsfRXX+vK0pYGg6 Bb9wEjQkWipLV9kc8Olr8WZhwtujaTDvcNmE6mzlx+ndM3sLVGih660OlqLHCmE6mDDV OXD2RZ9xzkPHxajAev6JbcrVoGI+DLifda3f1JfgFYG/4NuJh+SqvBJLgTypZ6LdSX3v OV0g== X-Gm-Message-State: ABy/qLYWSxSkg5eiDSLPWdpA/QuTRbNo2MBchm/pUeBqHBwEfA2RAx/o INjZp5rzM4qPcDB/sXiNMf6cmQ== X-Google-Smtp-Source: APBJJlGFuOk5isZR4/+qS0sIxAc4XoYeJCy3FONS359I8jJMygiVODk1sNpeRSv1+vKLVQcpXvx+YQ== X-Received: by 2002:a05:6e02:1341:b0:346:6dc2:997b with SMTP id k1-20020a056e02134100b003466dc2997bmr1160807ilr.23.1690358989560; Wed, 26 Jul 2023 01:09:49 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id gc17-20020a17090b311100b002680b2d2ab6sm756540pjb.19.2023.07.26.01.09.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:09:49 -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 00/11] Introduce mt_dup() to improve the performance of fork() Date: Wed, 26 Jul 2023 16:09:05 +0800 Message-Id: <20230726080916.17454-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: A45C820027 X-Stat-Signature: ach7nfb5s9afzm1j67x519hup1bxpo1g X-HE-Tag: 1690358990-192707 X-HE-Meta: U2FsdGVkX1/zcSVuLIyA9vKVnry9OHL9q8q5hOOKtvXj2Nqzlva4BKGXA8cZC7/tTYFtCtyr6KAKIKHVJAAw8lev5XqB/HVtpPbuBfm1stsfCammdlLM4mF4D3ee+Q3KduJqcVl9/+guDhJhepOKAZZgWpgxCvITId9oxI1tSea0JdUFziIGgARVnJLYakN5b6axPd/Qu6R35tD0dapFJxWqjgtfEbrRuogFTf+HvOg4xwwfEieCAzHg1fcUus+2roHgd43TcwBfJ0d4yfc3RxYfs7YEKs7rq0oIEgq5taocSZuyP6fwbEj8sY0/hYQvRAjrDeKDonJijbfxmY8ei/bnvhr57VaceWQxUgCw3FhMtOoK/tK8vClD8wd7I7R5TlOHRJu/IR0rWuTtSoDyU+vK52DYIM3o8bDWEFbHk75zYNnP2aM4H2UKqrjljHZ9h5Ue2kHIXMsOlY6M8OEPO6G9/Gz+lt9DoKyEkBJu2qNixPXXL5sAanJgJC62IkcaMpI0L/smQRKmYrWg2FqMgg7uvWoBl+AQ4iCcZxNP+k7rNzXl9RwtKQKOR5p2rouDkkpdSpx0vRzGAoQGDZMLN6+5OiMz4a8Pk68CEG7mBi3/8PmUj3pHQfPhuxuuMCXKnF/4f4D+PsWhntOnvNUwWV5OIGh0zj/xWnEbigKUHigbthiLl2Ocp1Xy9W5jcyFiW/kP/TKVt4sB/Q/VBWjKcUpYKs8yxV2eUtLOiMsgG/w3KfkrMZ4xeAVZAnDy4avA/YUOQFZiYseQ93iwH4tz4aJp+alBBYLEvHC5mi7zP4D0PQA36Pu4BRbraCSBw0uu+jKW2eLCZvPhCgfKXRChQnggT61cbKVWzr+w1d4FEUYHwb/3eGZ6Xy5Ye5j1B9w8vHf2d4qXTG5gj28QUvEJRaEVEuVD5SkwHyxyRl9p0MVyTT6aAZq8JmFp8fJYjR+y550qySM/wJ26gJHjVhx LBYK4RH/ TFrqPLw6lpTquMsFLUdOXZozh8ryVvRw5jJiCZ4z4MAeEizqOvpeTKJLNptq3DFnMG/Hanf1n4dytsTD1PGXBXqiclP0CMmKcTDc+zPAV+GYUmE7ZOkMYC5IeIkaJg0tzQbd/wgx7tz0iAAH5nM4ETDIg2ERpbGCWloTTi+7PLwX0u5suncZyHYCy+jHeWlAv8R3XfnTD9LvtaMITZq7OpYnZPzLi1lDG2KCDOSwQOoDBWRvO9JUUXFNX0jQVtzt2h+Ml9YFDGhJpitviPlgI3/BO3SyGOuX1dWLpCt9qUI71LtQmXCoKdxViPAcOFfaFfQQV8h8wmEDOyDif2golyy/8+0KigZ2pPJwHdVmdU91vgexM1kWYeuPFzeb4Otr7Ll9Yj+vBkIIx9KBrxhGj1KkHkUlc7DwAmkE6QJOGEPNNoUktTz2ZngSCqw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000095, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: A few weeks ago, Liam and I discussed "Fork & Dup tree + Delete DONT_COPY" in [1]. Thanks Liam for a lot of useful information there. I didn't use the scheme of linking the leaf nodes, nor did I use the scheme of building the tree in BFS order. I ended up using the scheme of building the tree in DFS order. I implemented this algorithm and it seems to be very efficient. Use bench_forking() in lib/test_maple_tree.c to test in user space, and get the performance numbers of duplicating maple tree as follows: before: 13.52s after: 2.60s Their meaning is the time consumed by duplicating 80,000 maple trees with 134 entries. These numbers do not include the time consumed by mt_validate() and mtree_destroy(). It can be seen that the time consumed has been reduced by 80.77%. The performance improvement of fork() can be summarized as follows: With 23 VMAs, performance improves by about 3%, with 223 VMAs, performance improves by about 15%, and with 4023 VMAs, performance improves by about 30%. See patch[11/11] for details. In addition, I would like to assist Liam in maintaining the maple tree, which requires Liam's consent. In the future I will make some contributions to the development of maple tree. The layout of these patches: 001 - 003: Introduce some internal functions to facilitate the implementation of mt_dup(). 004 - 005: Introduce __mt_dup() and mt_dup(), and their tests. 006: Introduce mas_replace_entry() to efficiently replace an entry. 007 - 009: Follow-up work on introducing these things. 010: Add myself as co-maintainer for maple tree. 011: Use __mt_dup() to duplicate maple tree in dup_mmap(). [1] https://lore.kernel.org/lkml/463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com/ Peng Zhang (11): maple_tree: Introduce ma_nonleaf_data_end{_nocheck}() maple_tree: Validate MAPLE_ENODE and ma_nonleaf_data_end() maple_tree: Add some helper functions maple_tree: Introduce interfaces __mt_dup() and mt_dup() maple_tree: Add test for mt_dup() maple_tree: Introduce mas_replace_entry() to directly replace an entry 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() MAINTAINERS: Add co-maintainer for maple tree fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Documentation/core-api/maple_tree.rst | 10 + MAINTAINERS | 1 + include/linux/maple_tree.h | 4 + kernel/fork.c | 35 ++- lib/maple_tree.c | 389 ++++++++++++++++++++++++-- lib/test_maple_tree.c | 67 ++--- mm/mmap.c | 14 +- tools/testing/radix-tree/maple.c | 204 ++++++++++++++ 8 files changed, 658 insertions(+), 66 deletions(-)