From patchwork Mon Oct 16 03:22:17 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422444 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 61E00CDB465 for ; Mon, 16 Oct 2023 03:22:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EE9A58D0020; Sun, 15 Oct 2023 23:22:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E994C8D0001; Sun, 15 Oct 2023 23:22:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D61F28D0020; Sun, 15 Oct 2023 23:22:51 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id C40618D0001 for ; Sun, 15 Oct 2023 23:22:51 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 95B99120A60 for ; Mon, 16 Oct 2023 03:22:51 +0000 (UTC) X-FDA: 81349877742.08.3883B87 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) by imf07.hostedemail.com (Postfix) with ESMTP id C40AB40014 for ; Mon, 16 Oct 2023 03:22:49 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AQY7y+oz; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.50 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426569; a=rsa-sha256; cv=none; b=wTmG6MFgXO2pwCtOAkz4C65dCK2+VTjREbfpZMxsPJN4cn+9AohZXbLQy0El4Ws0iTbpbO A6p2zJi/6U0PdIxRUg/bC96YWrJhffIEmT0AEx52pPtUwt2BcJEhbUJOZUE9DnpGYDqEeW CrQVmSEA0K0c5iBAymFVt1A94LkKFkw= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AQY7y+oz; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.50 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=1697426569; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=gMXBlwMJHWTw49yDUWiVwa4DNV9Ia0WYlBn1m2aDH/BoUpB5G5LGoZaQ0QsyO+66u2icVw tR6g4a9oEtDGCpnLO9naJDvCBtsiDK0cNsnrkmUxv6MWTV1y4ZaTXmlg9NNQMULgT90p95 7epTUfbK3U009ElDB5FRdED6QaXcnbc= Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-27b22de9b5bso2378873a91.3 for ; Sun, 15 Oct 2023 20:22:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426568; x=1698031368; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=AQY7y+ozjHCylxvTXRQGRm4qeLic2StD7qupIiVEIgzJCXkHL7yBIAm1Kjg/nfCZnE vMHeL9OfEphPZ1pzjyTQbdYvAuy0hYWxYfy6pB8NrJXWCMLQraCeE5oiN35l8CZJ1bGD QkZ60TdmhDnZ9Rb4ZSUj7VWfu8hg9mv0yuZmR4qkNjJAqWR6vO8lSfDZgTk3AASsX1WF vCpUlPSotNZQvLX/JxcX+vtYo4s5//FZNZQQ+DQ1UruuCcILtfk7JJnUTKGfQ+A49bAz P/bMDwOowBi3H9wbyLG7Gl/Cz4jdyOIDJuVdi1fCKHykobPS46O6YVZuCkhN44gs17fV ySDA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426568; x=1698031368; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=Ky+mNxf+Q+2G9wgBS2UYV5NP8vxvVJmgBJgAGymTQ7fGVLKZwrQCdb5gR/aFFOZOAy bioOXLpWPcSPz7APcwElN+B4WYcYghvY4Ryu0bS9BBQTSAfaD0nc/klpe8r78+4kBHb9 ZPK5IDfzi8vC0Ajz7SyhVB+oh456IaKbncKjttEtWnnxwTCktfjQCxr1BmXugv9X9VaZ hCS/8HB8ohrkczwANvYY24OU46ssGO8daTKrV1tavOVCbAkEJc6+Qe24k0/WsYeNLoqu 0kMvfUOjpyZO1EOr3g2Z0TgZjB2kFwfiqy1E+LdqsPAx9/6uglQITWO9w5szBIp2X3lL 06gA== X-Gm-Message-State: AOJu0YzQdtWUPiwRfyebku8/CefKQeo9fipvlIlq9wjIkmAfQU1XzIHl ObnPRem6Kyb6JiVhksLsGJYzzw== X-Google-Smtp-Source: AGHT+IGUNON6/iy5nHhowUF+lwNS0aMjdLqxBBty2ZXDevKfnR4hUvescHuITP1+A0eJuZZ+fdkYww== X-Received: by 2002:a17:90b:4b4a:b0:27d:54b9:c3c5 with SMTP id mi10-20020a17090b4b4a00b0027d54b9c3c5mr3463142pjb.17.1697426568534; Sun, 15 Oct 2023 20:22: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.22.42 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:22:48 -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 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Mon, 16 Oct 2023 11:22:17 +0800 Message-Id: <20231016032226.59199-2-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-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: C40AB40014 X-Stat-Signature: dh1ayj37tt8xgyjmm8asypr4534kg4zd X-HE-Tag: 1697426569-238934 X-HE-Meta: U2FsdGVkX189gUJbZMhwVG1rqN+c/s/ck4DPJAhUxBcWW+Mwou86pKQHgl3cQvgcXcknD0+Z88e/lz/0rmYr/hBPsKEvYVQ4pGlilVQm5OuM55LIcYOhpnZHCEf/QSNNnuUfdfW+BNhvJ6nxieyF2znPkRoSCjTHyEyKSxFUJun7NMKPr3k7VrTXoCJNxiujhcSi5vl5ared4rmqDDjwvB87POsSxj0xDY5ZEnLSmQ1J28ioGuJvxqHLhiSbAkx7N5ixmUGh51FMnZ9a19SBylai8KIxnOFQJxo6HI8Hu/30mZRZC5M+jkT5j2ajNLZs29/S9L22tSNPlOVQQWSzq8bFEosyNzUbwInFSlmH6FDs3j5fmYAAqEYTd/IJGEniPFMr8ruQeFlNts3t0bbQquUoee9IgS+RCCmZ0ARRzp6VFAza2ePONPsCUP1UAd/LeP+pJDQNpchpmFLS63FuK5ZgAjhceos91f4hxxC/BcTcGw0e7wIMjDwbQ7NtBPjPDcgmOkj4zfe2xy6dPr9NZZAeNA8/Plr4nkacQk5raO6qvW5o0jTS6n21YQP1RbmgzyyrndT09J1KSGd2mwoYMb9iH2KOfnXSC9OKPN/hRCiR5gtFC8Iu7cIWO5e6kedzJApqNJpfWcClj7dpl/gy8Xdx6G3Z6oz2+JsloWUxC5MfapineFtXe0NYu0a8yXlmrf1QijycxDwRBC1Tg7TGW2/oCl7B48o+FJmX5gtDpIhQq6GzjGlxq1yWerpbdXg8WHSiZtXDE8l2tIcE07VpvXq62RWUPrNXexV5Fii1wSqqhECDgQYJn6bsrqCfiASRlB3BrrJ3i1gMm+dHhJwJGStqYg7A2lBMNd6NcEZ4JIGRaVWCgpJf8pDNAYw7/7055JdtBCnn+7puJ2OsrPzQXhn5sT9/8yvd9i+64xDkaLCqoswqvycHkx6LBZGB8Etl9ADBclMCr/Lv9YCuWy5 nfwn0Wy7 3uhapdkD+lGRMfZ9yhB2WdBU1OknPrEQR/H2iF3byPIn+z4AI+uVXin/WThvNBRrT3pcDRX130LNgp/pVoQxyj+wz3obRCyHDzlsENOYouA7JbNefnfqGlwbdcoCc2/FN4kfAbxp8n+jAsG7UQGE10X2djvm+7HqRs25RUsRjm63EjmxjcAF6AFjxiTdNM8YV4tWGrrB2mtqlrmZE+XHlBuOc88h9oFyEL9250tGy8CGzIDhT/MkHZPM5b3hpaM8bAftGVJZ2JVb50VdDzVuSr0X/4YC0sqJnVSqWOU7FddHVu/LtwoCFX5PxqMCsycQesbOFL2JVtaR4TQ4GG8ex0WtHviG8BCiAegT4q9+O81yyXfcaYMh9Ea6ndWrb8lDueTuy8QMMWMFr8lo6L66f2P++ODx29LzuzfaheWo+uKH8rci94q4neTFVm8Lk71WpwIvAPpSO1CdjsxWLJHHLALKiFg== 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: Add two helpers: 1. mt_free_one(), used to free a maple node. 2. mt_attr(), used to obtain the attributes of maple tree. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index bb24d84a4922..ca7039633844 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -165,6 +165,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } +static inline void mt_free_one(struct maple_node *node) +{ + kmem_cache_free(maple_node_cache, node); +} + static inline void mt_free_bulk(size_t size, void __rcu **nodes) { kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); @@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas) return mt_height(mas->tree); } +static inline unsigned int mt_attr(struct maple_tree *mt) +{ + return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; +} + static inline enum maple_type mte_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & @@ -5573,7 +5583,7 @@ void mas_destroy(struct ma_state *mas) mt_free_bulk(count, (void __rcu **)&node->slot[1]); total -= count; } - kmem_cache_free(maple_node_cache, node); + mt_free_one(ma_mnode_ptr(node)); total--; } From patchwork Mon Oct 16 03:22:18 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422445 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 DCCBACDB465 for ; Mon, 16 Oct 2023 03:22:58 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 610328D0021; Sun, 15 Oct 2023 23:22:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5BF418D0001; Sun, 15 Oct 2023 23:22:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4612C8D0021; Sun, 15 Oct 2023 23:22:58 -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 31A7B8D0001 for ; Sun, 15 Oct 2023 23:22:58 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 07D1D1A0A67 for ; Mon, 16 Oct 2023 03:22:58 +0000 (UTC) X-FDA: 81349878036.02.1204F9F Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf29.hostedemail.com (Postfix) with ESMTP id 368CC12000B for ; Mon, 16 Oct 2023 03:22:55 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Qoxv3Unb; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 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=1697426576; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=dWwc+qeFM/XtD39AqbDvvj7By7e0rtqINqELWr+HEhNVVT5w5s8NzTrDDSnDvoopER4MdM sCZpHITqUQzeU5AIzDX9ze+HXfiGHNC9WeTVIXLpaCDtWAbn/eGF65gaOm5d3JYO3yNq9I mNInPS66SJvvc7vK61moPitJhoYtcXM= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Qoxv3Unb; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426576; a=rsa-sha256; cv=none; b=OAcjwVntJHtGB0ktraJr5vbjvVTaKeE394teTambxR6bxCaWzDHkVynunBEZN96WCNSf2P TWfoNOpfhg9QqBCo3lgUP3T/225Nau9m+PELVV/Cfm830W+/8rbzPw63ryOUHa1tommbtW dDGNj+Pf9shInV38LVs11zwuypvvvu0= Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-6bce254ba56so715900b3a.1 for ; Sun, 15 Oct 2023 20:22:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426575; x=1698031375; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=Qoxv3UnbcagXyW0U3BIqmMXqcGt+KStC+Kglx+tlUbUehJ+643E4vYkzXviCtI5cB3 tY9Ly6T5F9e51dBCb1SfCPWStY2KHA3yX14i/yq8ejGZQKZfvACH+hVQ/5BoXXf+2fqe A26LFd7OO1O/rO02j2vxfutzH3WJlAs4yJjdNI4N4FSJj2t6iWAMCuGNjkVUSpk2dmND QSNUoh1n/Yvwmx+M/dNX4LJ9s36hFJZno2Btaiz+HxDjv0IBH8734jXE6u8KEJjgH6i9 5ZgAO6YuGdyI8L2DiSX5NzjaRCTnrowBQUkTYlO+KP/PnVih1JFSs8qb9tjXSJbVfbWq Yr2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426575; x=1698031375; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=U+r9/nCpWt6IlvikX+jlGnlDn/aIH6wyMLoOUKoEf4EubO2NaI5wa7s8L5vSUWp9B6 CElWKorq0P5Dx8GUakJsQLJumIEdpgBOngM5ST1FUyY+fnloTCxQy1rk+u2CKhPYM68y Prfre0zlOeE+kcu0pwPw7M8XR/8wPXl0DSrjfSj8r/7JNhUeLfUz3g22auYH277o5vli xJelsMa4fZChQa6f5huQJycBuH9U/Iy782Pzaw0Db8I/TPdyMizpRc/1ODrZjIv12PUY NacGuCXbWMi1x95Ewo0pS+qfN0I2wPqBwEpGdazJLYSFcHc0pGmbc+HTqNj3RtBsXDEG 5Rxg== X-Gm-Message-State: AOJu0Yz08QLhhCkoj10t2uOoCnD0WpHN8VacIcaHfM4XLKSRbiAx7q9J DicHnu28FKLF8KoysR0Rfsk+GA== X-Google-Smtp-Source: AGHT+IF6N8e9Loe20mQNUBXUIhiXmTkb8m7FtzL5gkme8mgEaofINIog9sVAbKEQ8545hYi479/lHg== X-Received: by 2002:a05:6a20:1613:b0:15d:9ee7:180a with SMTP id l19-20020a056a20161300b0015d9ee7180amr33444332pzj.4.1697426575048; Sun, 15 Oct 2023 20:22:55 -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.22.49 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:22:54 -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 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Mon, 16 Oct 2023 11:22:18 +0800 Message-Id: <20231016032226.59199-3-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-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 368CC12000B X-Stat-Signature: pswxx7wxferq7gfw5f6ayqihi6u3oke6 X-Rspam-User: X-HE-Tag: 1697426575-628858 X-HE-Meta: U2FsdGVkX1+jpk5ROGs3CPd11eD4MOABTbHf84/THY5Mv8SeAJp4QQRrjI+aAfEGnq/hUiXujQw/pOZDdSDhWdL7HrGC27ZR469ghOKyUejCvDEC2mVD4l/XF7xo9ltGnmLiFOzHximx8JQM8BHjy3i64IGcO315SOA7vx0gzfkSZNw+xhfF02x2UB/AuAvVpNiwJgtFV7LSZCuHTkTkuN2gD5HV6mbjUynGcx5mmHF79g4htzwFys8kDFwmjndQsMyGAdo+jlcbQSPKE5WyOUERxgJkuOe6snrT4QvPWLw76cWL4WbYMxU9RbC/Q4IyKesf7HDReplcqV7sm1zbLrU9fmETlpidviYXM/0o8wYLchpSwx/jrUMw3rre4flTKGhQ476KoXO9i4ApDWrF6bV8pAGoprvgsJkwchML/IyQzE0ZroIva66lN4iz7dOLG59XCu44xj/jv8ULoZowT6lxN2RzAFip2AfQaVoVwN+q2oLOpY6JBxXUdGxJGi6ZSMfdr7tBHqA/pNkjWDkHbwO6PSKzWpP1TfYA7YudVh4sf2K0LjqpI6R7jDm3CxRWVmbshWrvbsCkfOLjKFg4xWR0wm5Fky6rQG15s/TTHQgGetVIsGD35YmLdFZJETWz3Bbgtw63QqBDq+aUqhcc8/MS1O6RUn+rr18lC5miE3u5nvbO+Iif8kPl3mH20LfHysePlM4FjHY7ESgdXHUjTZPB2O7GfE2uVck56eVd4tE9QmVrmGs8tNxjQTEaavAAFN4eoGyk96TFrHwzjF0nPyWxXpKCLB0Liw8TeceiiFxEBZ2aeFtzQRrPxHyrTn+FBZd3E2p/5GtHyaO7tRxlU2QJzH0T6149vOh1/vhuZRfiExewzlvyqzi8VRCTm+cHAhv0YlPy3Soy25zcoBBbGMtPUeWtrLm46yZOlkL9yENIRGTmztz5E2veVIH37vIlEXQUMzv3+1VRCUnJ+Vc llT9EwGQ 90XasYGwwrcN2huyPTry3IxdKNilqzkqly45C+Nj9989WYeSEw82xdzjbIFcW0v5VqaJjArTkuZinsMNlrTmccb3met8xyGMuMaBFty6h+TRtQQOdjZnsh2zlAc6OfGZ7bhxaHoQIUj9TU3kqXkqnYFaGvbOPiDX25O99yde23qJFel5Vr4yL2xGZ7sKUGgZA/elzWHqBfCmvwyMZIWRRwhlCk5PUTBxrK7/kvHr0A8KRc3G6/kIurf0AsZst0KW6wc/qxPwFLvDQYjoNPOFEBh3j/xkWlvl+OKaZGiVlD2kePxu+ZGBV10ItkQxjCW8mAWfHWb7Jr1qIq+pdkMao9LmV1dA6/GtdIik7p4fk8ubfQ0X3agLXLLZIJIp1EnwRrNyYds2DXg1IZYgxxRTFlvklPwqzvXldUNXmI/RFBuZXDbfzv84u+SJOTgK1Tg3e78rzElkPGza0CRarEg0hu8KWdA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.002101, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is introduced. For example, when duplicating maple tree, we need to hold the locks of two trees, in which case nested locks are needed. At the same time, add the definition of spin_lock_nested() in tools for testing. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 4 ++++ tools/include/linux/spinlock.h | 1 + 2 files changed, 5 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d01e850b570f..f91dbc7fe091 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -256,6 +256,8 @@ struct maple_tree { struct maple_tree name = MTREE_INIT(name, 0) #define mtree_lock(mt) spin_lock((&(mt)->ma_lock)) +#define mtree_lock_nested(mas, subclass) \ + spin_lock_nested((&(mt)->ma_lock), subclass) #define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock)) /* @@ -406,6 +408,8 @@ struct ma_wr_state { }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_lock_nested(mas, subclass) \ + spin_lock_nested(&((mas)->tree->ma_lock), subclass) #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h index 622266b197d0..a6cdf25b6b9d 100644 --- a/tools/include/linux/spinlock.h +++ b/tools/include/linux/spinlock.h @@ -11,6 +11,7 @@ #define spin_lock_init(x) pthread_mutex_init(x, NULL) #define spin_lock(x) pthread_mutex_lock(x) +#define spin_lock_nested(x, subclass) pthread_mutex_lock(x) #define spin_unlock(x) pthread_mutex_unlock(x) #define spin_lock_bh(x) pthread_mutex_lock(x) #define spin_unlock_bh(x) pthread_mutex_unlock(x) From patchwork Mon Oct 16 03:22:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422446 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 D9A3DCDB465 for ; Mon, 16 Oct 2023 03:23:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 23FE38D0022; Sun, 15 Oct 2023 23:23:05 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1EF178D0001; Sun, 15 Oct 2023 23:23:05 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 090058D0022; Sun, 15 Oct 2023 23:23:05 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id E72E78D0001 for ; Sun, 15 Oct 2023 23:23:04 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id CC3931CB4DB for ; Mon, 16 Oct 2023 03:23:04 +0000 (UTC) X-FDA: 81349878288.06.FD816F5 Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf28.hostedemail.com (Postfix) with ESMTP id 0624DC0008 for ; Mon, 16 Oct 2023 03:23:02 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=k5kQ4cmY; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 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=1697426583; 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=e/sF1y4M8+5TE0GCNNK3GGgEnktBWwP9VwP8zP44L9Y=; b=XMxZcKsoJPofk0OeR4VOTEEKPQzlPTgIOrRT3atSkt5TaMqxhJUvYc8jmqyAi1z/oNMfav 6iLp03X+b9yCRHnyAmY6mDrm0nBOvV9URelkYRG9DZiLV3IsQkemRL2xtFryGG0hJBpn0x CQi11G8Yd9vQepa8wLPJ3J6Jv+k+s2g= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=k5kQ4cmY; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426583; a=rsa-sha256; cv=none; b=2G+JXJV29FWhqdZGkbRC7/Cc+h7R39by3YyFiWOME2v61fAJ3VK8W7nfVXBPfMyvAReZ3X GMCeIsREau8wbXo/KKkmZXs49462BSFGoDv8BjVUUGYNrn8USP/qtVUV/M0xe2GfAt1LBU vWSD95cVxy8l5Y1w7knvCdeE+W7W/B0= Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-5aa7fdd1420so1255796a12.3 for ; Sun, 15 Oct 2023 20:23:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426582; x=1698031382; 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=e/sF1y4M8+5TE0GCNNK3GGgEnktBWwP9VwP8zP44L9Y=; b=k5kQ4cmYwzBBoV3U8+vB/OxWfvvbMaDBjJ12veONQUWpimKAE73FQSv0hiTX7bq1VA KiFejIbJCajGjDO/FXyyCncgAFQ4tFYcbeBoKFVWH53rh7wFhfdXB650/ibi22HbM3LT sYlQTXBrSEZaD9SEiXsHgI/+gVzqGW0KRp/Rmmx+DwEI+nPb8n6TI2FjWUa/AJ/IVO2F SkD4Qu3/hjSswRJsgHGVNrBreTEnFrLZLo5UsLfaZeME6VLj81hMMVEKoUnQb/YUpy2a EpW6xhTVdK7gygr2PkbMFGpnxfwVjylddbKW+FVIl7qstnuxGa+K49UOUGnvFlBjtm3H 2f7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426582; x=1698031382; 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=e/sF1y4M8+5TE0GCNNK3GGgEnktBWwP9VwP8zP44L9Y=; b=cx1BjU5e3Jo4rowAQ5doyCDPOowsSW4A6f3rcnJAy9sd41Q7vkbXhUvb/MGtGYefMT sBrZb1cohQO2bagd51Ffcq4IkX4RfbO+rG7LjdEqVZfCKBBcYvX0eZ1B2eMuILXWg/yP Adk88nKilNuK542lKPRt46a+VtSBWGo4bzeF12dvNL8jXcfckRpulyuHoE6pbWeBKvBj irvWhsqSpYyJp+ub4RLI1iGp2BzUTj/H/EINB1xkZRi0Pulq1Zhpqr6pWL3A6S6L24YL vQCGHdmMlKzR08PxUHQIVKtI8oOF9On0NPvZVY+yEWrMk10QQGU0DBAsQEXli1Fz9Ye7 r+jw== X-Gm-Message-State: AOJu0YzpEkfZbwwn16dDZHmKqDAWecnFntEQCT/OkgT0pUOrVzR0QTEm Tm6V+rleAQeh+SKDX6xFEk8Dfw== X-Google-Smtp-Source: AGHT+IGNszmmv6OXzfGiuGTzwsi3NCAXv1mbwF37K+8hIyYvm0XADpPiEGL9AP+98FGCJGisbDNSWQ== X-Received: by 2002:a05:6a20:7f9a:b0:140:a25:1c1d with SMTP id d26-20020a056a207f9a00b001400a251c1dmr36624545pzj.51.1697426581541; Sun, 15 Oct 2023 20:23:01 -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.22.55 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:01 -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 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Mon, 16 Oct 2023 11:22:19 +0800 Message-Id: <20231016032226.59199-4-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-Rspamd-Queue-Id: 0624DC0008 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 8rt85n4cwmz6szokiwoyepkwm1k3jc9n X-HE-Tag: 1697426582-762864 X-HE-Meta: U2FsdGVkX1+YAAhgAoRO1BPH+ASX0Pt2zzBmTg/SWsWbg8yaffhzZWIgSSk45SAcncRhh0CvQN9fb+IzPk0+gYWMejocvPMudBugJdS2bsmWqWrVhLVfMoO1u4EYdPQ4AgI/0WDdrzV0bMlySlTxNZJqWmnGaaq2BZR26IXJPuRtdbupqAIJk66USdVAgCUHVCeUOceAM1z7RCNGtXPDbHDS9LioSR/GKEfT9VmDUhdJd2E6nrVJ+JeiY30RGIIA/NhCqAb0jpcKYzVStDnFweNQFfiKukcoGYGwIzeTNLs59bGZnOVoxZXVwhJbhoniGJJAcCzovOipOTeIzhzJkGOvfvrQwxQW3czd0cnRKochpZ6MdMpzn3E3JP9UiwtttdaKuqVCLpj3UkIeod3d83H6bMISbaf7soV/U9eYni8y0fKyRt5Dxo1QYj3wmzyd7hvOniiJF5TN4pns8xhHzKfBOcFnRykXG4EtW1fBwyt1WazMHZWw5IbTktCf5dsHEMz9JsJk+6D1Ij+1S3ENzXgIWSauRjfHwbldy33aGnyc6JACEIvO4Mz3Lm+0B5tOr8YrSqFxoLKNeznKoXCktFsprmbe64nxLgsWsRggf0mUwwQiRrq09ZKT/OsBmO86L5KeBvYt1AA8PY/yla0CyPGvhZXpPH/+33oiz95HKTCr0FZksgWD0k+m24HsZUvePXBFmhGzms+NQcU/Qr1gvXoviVi06oCyg0iw5fTQupM3SaVkxBz4zLE1S3mEG1IRewmQW/E0GmwOK+PtNoLqa5FTtQpYaAs0VZbf5Ha9XHdrSYgRL+YHd9Y3It/U63SuEkYojLHZjMtkgyB7no9GMShYO11TzRzEQ12KeZCFc3EjdXlWscBz5lg0AwLSg2YY07tdg+LEHMVKHopPSTcO5crJSFWJ3FRHfHKOsXI4OUa8pA0LxYPl17uJlVX0xEAs7Jok/EsNGKV6DUaa7TP 1fE55H4z Zld/77xUgpGhwHRnjt8iZbknzfrQvt1j5d2qLfpyavNwmZ07t0MYQkCMuCcspCMsUozci9BNEr7DvKn/2ERbavFGQDMF2CAwZUkZNKNHBg4HeN6w5G563W9S/7GptRD4CYeuurtHmKErScLUj8lQNAHdV/4U20Hvuw6QXFEikmKg2OVS8hs9MBLVSIgXXR65BZNX1dMxMITYkNYUOCYDWe5F78l3syFnTZfGkdcuDH7otFF/sToRpzu71lDdWgF2JwHJUJvEUNcFoIU0mqMoX2uU55HEBcYdTOqQsg2QCuujqGuTm5wVpT3JfD1XLkG2airJBUMNFoNrCl0/VDcuBEzM2TUrXdHu/t5h5itEOfm5jZSU887v9Y1nuTLAcrJ7Ojr5u6JQJwQlCfblHDfFcK7IYraui9T3fYzjORq2efRgi0a3f+XCpTqYFa36dlULxCpx+0bDxu+PbBC9UBXeHIivC439vOPezZPSZjr2fEcjvr45tSIHKTt7BGeBq5CWW/nfESePVcz5AuymkCu2YUIrnhfgRYt8WGrUhXBYcjEIgK8Y= 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: Introduce interfaces __mt_dup() and mtree_dup(), which are used to duplicate a maple tree. They duplicate a maple tree in Depth-First Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the source tree and allocate new child nodes in non-leaf nodes. The new node is exactly the same as the source node except for all the addresses stored in it. It will be faster than traversing all elements in the source tree and inserting them one by one into the new tree. The time complexity of these two functions is O(n). The difference between __mt_dup() and mtree_dup() is that mtree_dup() handles locks internally. Analysis of the average time complexity of this algorithm: For simplicity, let's assume that the maximum branching factor of all non-leaf nodes is 16 (in allocation mode, it is 10), and the tree is a full tree. Under the given conditions, if there is a maple tree with n elements, the number of its leaves is n/16. From bottom to top, the number of nodes in each level is 1/16 of the number of nodes in the level below. So 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 series, and it has log(n) terms with base 16. According to the formula for the sum of a geometric series, the sum of this series can be calculated as (n-1)/15. Each node has only one parent node pointer, which can be considered as an edge. In total, there are (n-1)/15-1 edges. This algorithm consists of two operations: 1. Traversing all nodes in DFS order. 2. For each node, making a copy and performing necessary modifications to create a new node. For the first part, DFS traversal will visit each edge twice. Let T(ascend) represent the cost of taking one step downwards, and T(descend) represent the cost of taking one step upwards. And both of them are constants (although mas_ascend() may not be, as it contains a loop, but here we ignore it and treat it as a constant). So the time spent on the first part can be represented as ((n-1)/15-1) * (T(ascend) + T(descend)). For the second part, each node will be copied, and the cost of copying a node is denoted as T(copy_node). For each non-leaf node, it is necessary to reallocate all child nodes, and the cost of this operation is denoted as T(dup_alloc). The behavior behind memory allocation is complex and not specific to the maple tree operation. Here, we assume that the time required for a single allocation is constant. Since the size of a node is fixed, both of these symbols are also constants. We can calculate that the time spent on the second part is ((n-1)/15) * T(copy_node) + ((n-1)/15 - n/16) * T(dup_alloc). Adding both parts together, the total time spent by the algorithm can be represented as: ((n-1)/15) * (T(ascend) + T(descend) + T(copy_node) + T(dup_alloc)) - n/16 * T(dup_alloc) - (T(ascend) + T(descend)) Let C1 = T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) Let C2 = T(dup_alloc) Let C3 = T(ascend) + T(descend) Finally, the expression can be simplified as: ((16 * C1 - 15 * C2) / (15 * 16)) * n - (C1 / 15 + C3). This is a linear function, so the average time complexity is O(n). Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 290 +++++++++++++++++++++++++++++++++++++ 2 files changed, 293 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index f91dbc7fe091..a452dd8a1e5c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); + void mtree_destroy(struct maple_tree *mt); void __mt_destroy(struct maple_tree *mt); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ca7039633844..6e0ad83f14e3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,10 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * + * Algorithm for duplicating Maple Tree + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ /* @@ -6475,6 +6479,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mas_dup_free() - Free an incomplete duplication of a tree. + * @mas: The maple state of a incomplete tree. + * + * The parameter @mas->node passed in indicates that the allocation failed on + * this node. This function frees all nodes starting from @mas->node in the + * reverse order of mas_dup_build(). There is no need to hold the source tree + * lock at this time. + */ +static void mas_dup_free(struct ma_state *mas) +{ + struct maple_node *node; + enum maple_type type; + void __rcu **slots; + unsigned char count, i; + + /* Maybe the first node allocation failed. */ + if (mas_is_none(mas)) + return; + + while (!mte_is_root(mas->node)) { + mas_ascend(mas); + + if (mas->offset) { + mas->offset--; + do { + mas_descend(mas); + mas->offset = mas_data_end(mas); + } while (!mte_is_leaf(mas->node)); + + mas_ascend(mas); + } + + node = mte_to_node(mas->node); + type = mte_node_type(mas->node); + slots = ma_slots(node, type); + count = mas_data_end(mas) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + + mt_free_bulk(count, slots); + } + + node = mte_to_node(mas->node); + mt_free_one(node); +} + +/* + * mas_copy_node() - Copy a maple node and replace the parent. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @parent: The parent of the new node. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, + struct maple_pnode *parent) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + unsigned long val; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + + /* Update the parent node pointer. */ + val = (unsigned long)node->parent & MAPLE_NODE_MASK; + new_node->parent = ma_parent_ptr(val | (unsigned long)parent); +} + +/* + * mas_dup_alloc() - Allocate child nodes for a maple node. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function allocates child nodes for @new_mas->node during the duplication + * process. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + enum maple_type type; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + unsigned long val; + + /* Allocate memory for child nodes. */ + type = mte_node_type(mas->node); + new_slots = ma_slots(new_node, type); + request = mas_data_end(mas) + 1; + count = mt_alloc_bulk(gfp, request, (void **)new_slots); + if (unlikely(count < request)) { + if (count) + mt_free_bulk(count, new_slots); + + memset(new_slots, 0, request * sizeof(void *)); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots = ma_slots(node, type); + for (i = 0; i < count; i++) { + val = (unsigned long)mt_slot_locked(mas->tree, slots, i); + val &= MAPLE_NODE_MASK; + ((unsigned long *)new_slots)[i] |= val; + } +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree, need to be in MAS_START state. + * @new_mas: The maple state of new tree, need to be in MAS_START state. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function builds a new tree in DFS preorder. If the memory allocation + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the + * last node. mas_dup_free() will free the incomplete duplication of a tree. + * + * Note that the attributes of the two trees need to be exactly the same, and the + * new tree needs to be empty, otherwise -EINVAL will be set in @mas. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node; + struct maple_pnode *parent = NULL; + struct maple_enode *root; + enum maple_type type; + + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || + unlikely(!mtree_empty(new_mas->tree))) { + mas_set_err(mas, -EINVAL); + return; + } + + mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) { + root = mt_root_locked(mas->tree); + goto set_new_tree; + } + + node = mt_alloc_one(gfp); + if (!node) { + new_mas->node = MAS_NONE; + mas_set_err(mas, -ENOMEM); + return; + } + + type = mte_node_type(mas->node); + root = mt_mk_node(node, type); + new_mas->node = root; + new_mas->min = 0; + new_mas->max = ULONG_MAX; + root = mte_mk_root(root); + + while (1) { + mas_copy_node(mas, new_mas, parent); + + if (!mte_is_leaf(mas->node)) { + /* Only allocate child nodes for non-leaf nodes. */ + mas_dup_alloc(mas, new_mas, gfp); + if (unlikely(mas_is_err(mas))) + return; + } else { + /* + * This is the last leaf node and duplication is + * completed. + */ + if (mas->max == ULONG_MAX) + goto done; + + /* This is not the last leaf node and needs to go up. */ + do { + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset == mas_data_end(mas)); + + /* Move to the next subtree. */ + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent = ma_parent_ptr(mte_to_node(new_mas->node)); + mas_descend(new_mas); + mas->offset = 0; + new_mas->offset = 0; + } +done: + /* Specially handle the parent of the root node. */ + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas)); +set_new_tree: + /* Make them the same height */ + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, root); +} + +/** + * __mt_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcopy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * Note that the user needs to manually lock the source tree and the new tree. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_dup_build(&mas, &new_mas, gfp); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mtree_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcopy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_lock(&new_mas); + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + + mas_dup_build(&mas, &new_mas, gfp); + mas_unlock(&mas); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + mas_unlock(&new_mas); + + return ret; +} +EXPORT_SYMBOL(mtree_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree From patchwork Mon Oct 16 03:22:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422447 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 CFDCDCDB465 for ; Mon, 16 Oct 2023 03:23:11 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 668AF8D0023; Sun, 15 Oct 2023 23:23:11 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 60E658D0001; Sun, 15 Oct 2023 23:23:11 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4AFCE8D0023; Sun, 15 Oct 2023 23:23:11 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 37A298D0001 for ; Sun, 15 Oct 2023 23:23:11 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 05207B5C0E for ; Mon, 16 Oct 2023 03:23:10 +0000 (UTC) X-FDA: 81349878582.12.2BF406C Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) by imf21.hostedemail.com (Postfix) with ESMTP id 354A41C0005 for ; Mon, 16 Oct 2023 03:23:08 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hiI+Gy2T; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.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=1697426589; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=CUOaeNw7ocUnCYfL3RvQeQmWa8ja7bpcuGpxBPJE4zIUegamdTmViyaKAkIDPS/k1Smr9g nXvTEwRpN7vFa5a7GkYl+JIOnwqwc71ie2uFcq6qj+WTxBKT9E2GOr2wSIWuZqT3J/XxiE L++zbqJAfVsxMM/2tcS0iBkk2+JTGlg= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hiI+Gy2T; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.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=1697426589; a=rsa-sha256; cv=none; b=QLlUMwAf7PCeLpHsBrufeL5LePWJk0ZJ1Yn21ssopmj4fSwwRUKhnfWix9DSlbX0POGcx/ 5gg5G1eux0d8t5nN9tZljqQzA2X0j2amLs+CvN+3fBpthFV5D+UKBCWIEnmebstTFum+xC dgB0/kjIcyK14Exthoup8XHodMpTurI= Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-694ed847889so3078489b3a.2 for ; Sun, 15 Oct 2023 20:23:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426588; x=1698031388; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=hiI+Gy2TOw1F3sUdmvq9OnzSKqIf4GXZuWhnBym7zQ5S0Z85T3X6HIf47kPFM2IR+c srjELovHd4G6iCuKUzMNotrn6VVUMN5UG9lGZZnLhsePoxh3p29DrRlKS3TT+ZZ7pRid j9Rbg5P5ru0PUe6DZk9rv8p5tEpdsIDLiGevoPMstNKDvLrwkd4wsTx5db6Qa8401srs uXvO3ArU/wzCb2tAGgtL3M6DEFpXLBjUxd6IokodaRX0fbdztR5mzNmsw+akI8CxLRf+ 9Wq6uAHjvQSQ57BYWHAKc1+E38RBPvF9qCBE7Ae4BuqsDqOCJDfQi3hWcgOoa2peGuga aFog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426588; x=1698031388; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=J/BQ+cotZzpRoU0XYs93RoELE1ffYEnJ5JqHl4zEWCzPsK3r6oaUL67U8YICzMw9DD KsSylgxg/UwZah4+g3gjrDnavzOCjCLoBfGK5Om09mkB2AqBmp3xFLlRxLQJ06sO5grw O00O6ousHwmYI+NfikREEiAh8DNp7OOyEDWwBnX4zXLhHip0SyE86XPnZvbnoh34gLHZ eLNn9QTHvPOZe3HcIVptthiGkJhgN0KNtsvFnf57anMTg/KG9tRhANaIGkFiZfgC325z 3bgG8QnEZH48kNOKse3xZe6im4NTTQn2I0NTJ23bAXznX7rhYDdtbsCazlw9K7lnO+T0 lfwQ== X-Gm-Message-State: AOJu0YznCgWdbtTKRutccMQgWHPZmcoFaSh5fjVWle1kSx/3l/BYPmGc WiuR0QgbMVbb0WjUXomiHBzrjQ== X-Google-Smtp-Source: AGHT+IHJ/d4Imcp6odYT1h7aWQHUYbM1ac42oVm99u/t154/4XdiI3P2y5GHneaRUB847sqBMYQ7vA== X-Received: by 2002:a05:6a21:7784:b0:173:318:b1ec with SMTP id bd4-20020a056a21778400b001730318b1ecmr12877225pzc.35.1697426588170; Sun, 15 Oct 2023 20:23:08 -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.02 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:08 -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 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Mon, 16 Oct 2023 11:22:20 +0800 Message-Id: <20231016032226.59199-5-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-Rspamd-Queue-Id: 354A41C0005 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: mz6i5zn6i9dncjpdfwgmycx9au6zrytk X-HE-Tag: 1697426588-239597 X-HE-Meta: U2FsdGVkX19AIeL2XWgBpqJmHMJrq3Mi/JALsNQvK2+u8FC+6JHoKnWQV9yqu1+0q317tOBdeeEhZyzmDZVPONDXFnQ6rV/2LqHJfmMi7Z/AFM8Nqe6zSuBCrPcZYs1b8Sh+u40yIZ1SWTVvCwx9HMjQAnuprecZaXMcFHxzB34wJz4O1NRPo5j1fD1/G3dvIXK5BUIjrrlW0TB9/cXDX9jAZuyabk+lwY/7RGqhGShp100g6Am576AVlr848lpxRXqM8RAHBubPQCLPXBhOIHB7XblX0fUqj1Trxdi40jKMFlecRLKcKbIQ3TezKWxjnDrMoaORSP3pmGGMTgd4nZasi7ovZXsOBChh5SIaKd7J15Czwt9o+w2kTHr8eqRTN5KWk0n/XR9xXW0n0J3Qe/kMVdMDu/6uIquBeUe9A/s8DWohdgo4G8O4P7vAzVqzmOLNBtZWXeQ/36Sxtme4d8j32BMsccdNdo4aAbD5/kSLcwxbPVrOTmsxdir7OYALQ5O4XCKaXYqGhePitPNNgYs9aOiYQATfaphRIlFdG9b0vmcT0v/8izV2G4K3VXA9LZZKgV+awKM0z8xrJO590P7e4RfSB7MSyTibiT19ihMDGth7k3otww5LHVRKa2XdnXWVQRHQqNYKT3w5adfIdGdKXAWB7rX46hEbUrqsdA/cxvNWHWtm2wjm6zlhMgDr0h4/PQnNkX/sBQvXIKpHBU5TBGgt8udnzLnZ56ubJ/QNDafGx4kusvwt7G9TgdV7RIxPWM1S6m/62Ijr8himY1Aygn28ZD/u28qmnFa0NTzMszh9f8wzsCnXFnOupXK9CDBg2X72iyAN/sA6/U3ub6RcfYs0a0W6QnQt3rq6J3OX7fgKSNKmvWfzZfjSXWZ5nnkBabb4SSDQNB1UhIjPyfS7OfLCzAequ9pcvfkpnkcVBSoXRkO3tyVq2gOXMV57hvYdkVNerXdwpRssG+N v8nlLfKW iYbDVVf4hLTuUle17PaaeQFcFl9yyTvwkuxTHB9xmhB7pWmrY+Oiw4MBNXJkhUSLZWDEI3k0IQl5XWSOf7dz8aM23CggP8xQN+iscaeI5benZewME+gGetktOsweJpeSZI+GjKkoRKrm8HZaUmJhw+bf2JTybDjVh/TL9C6nDJAcjyozOASlCJkqfMpF7qINyjFWec+BB0PTIafOCPhGa5nE4S9O/nT2hfgWDT+aRLTQOQKEVsjIcmzuQD0Ws1FM2dBS7gX3rvadaDr+xCvdNPRSlIUS6Wu6yKZIuzhChZ1lsan4++ID1rdYCCpFbMIiK6jd6J0JGlPnp/w7jG44d27qxHALopVH446X0luPwLmv7ouHhblUVAeYPUL3jpONRPWsaKLc/+a9gsD+WXg6CIS9I4/U4fVgsUmUdj9EwTyDnNgD2o5TSU8iHs2wYG5T1PwOrZu14WDpIaZMLXG6rMjk+mw== 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: When kmem_cache_alloc_bulk() fails to allocate, leave the freed pointers in the array. This enables a more accurate simulation of the kernel's behavior and allows for testing potential double-free scenarios. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/linux.c | 45 +++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index 61fe2601cb3a..4eb442206d01 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -93,13 +93,9 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, return p; } -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) { assert(objp); - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); @@ -111,6 +107,15 @@ void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) } } +void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +{ + uatomic_dec(&nr_allocated); + uatomic_dec(&cachep->nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); + __kmem_cache_free_locked(cachep, objp); +} + void kmem_cache_free(struct kmem_cache *cachep, void *objp) { pthread_mutex_lock(&cachep->lock); @@ -141,18 +146,17 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, if (kmalloc_verbose) pr_debug("Bulk alloc %lu\n", size); - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (cachep->non_kernel < size) - return 0; - - cachep->non_kernel -= size; - } - pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs >= size) { struct radix_tree_node *node; for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + node = cachep->objs; cachep->nr_objs--; cachep->objs = node->parent; @@ -163,11 +167,19 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } else { pthread_mutex_unlock(&cachep->lock); for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + if (cachep->align) { posix_memalign(&p[i], cachep->align, cachep->size); } else { p[i] = malloc(cachep->size); + if (!p[i]) + break; } if (cachep->ctor) cachep->ctor(p[i]); @@ -176,6 +188,15 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } } + if (i < size) { + size = i; + pthread_mutex_lock(&cachep->lock); + for (i = 0; i < size; i++) + __kmem_cache_free_locked(cachep, p[i]); + pthread_mutex_unlock(&cachep->lock); + return 0; + } + for (i = 0; i < size; i++) { uatomic_inc(&nr_allocated); uatomic_inc(&cachep->nr_allocated); From patchwork Mon Oct 16 03:22:21 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422448 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 A2365CDB482 for ; Mon, 16 Oct 2023 03:23:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3C5EE8D0024; Sun, 15 Oct 2023 23:23:20 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 376338D0001; Sun, 15 Oct 2023 23:23:20 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 23E098D0024; Sun, 15 Oct 2023 23:23:20 -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 135B38D0001 for ; Sun, 15 Oct 2023 23:23:20 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id AA14D1CB4D6 for ; Mon, 16 Oct 2023 03:23:19 +0000 (UTC) X-FDA: 81349878918.19.DA28B88 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) by imf10.hostedemail.com (Postfix) with ESMTP id D73FAC0012 for ; Mon, 16 Oct 2023 03:23:16 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bk6AAYtO; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1697426596; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=EvnQwAnf6I38GuN3QOHSQW3mkNF+po9ftiuG7+mVV/VFpBmC+GiPZgVGK8lnhFSYl/8UT7 R8vM/NQdGV20AzQK6baNzr4nqVYCB7AGiwcSLHqYSmHnQHfSEe6ohXsmSMeCRAC9+27pC+ K/UTLPvQjUiTyXlm1w9gvoVWn0tzmmU= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bk6AAYtO; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426596; a=rsa-sha256; cv=none; b=VLdArQl+4M40l7FTH15i86UxMFkF1zhZ9b4ccRX9H8C4gxW77cWU3skxapAFYVLA77v7wA FRNE1g/gTrRCopjWa64vQK3G9H60t+LXpoQc6lCOhoVtsurlEZF4TfauBSuDL4S5qKCckw ymgzQLHsuec8KKitHU+KqHWHUb5PTGQ= Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-6b36e1fcee9so1743267b3a.3 for ; Sun, 15 Oct 2023 20:23:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426595; x=1698031395; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=bk6AAYtORUPoQj77zi6X6j3qF2TUPkDRUcGyJ6zte3PCEWBTSX46IWwRXYQ7W4xLcM irCZOCzhUtQmb9vr+xp2RkWKml7nIJm5iHlQoA7M/acv3rsdS1ZG/p6BnsF5Sgg+l9U7 5aG4MeSCPHI5S6/7P2/zXMF61sMLmNOHBRa3tWkCJ8ChaghUw03SkFjjTiDYLpqKhYZ9 MsKv9acMB1G7Q9pScoM8bJm0j88UxwjBikjDJkAH2Vctu4w1BIsfDlGVwVvdeTbBKyhC 2X38jsS7MP68FBRl2K0PgUlxs6fT86Ax4Zz7rh1yn373gd9aVxgmjvpMSnbO48/nrtjF Gx4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426595; x=1698031395; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=gKihEWp2mPDImbyFEk9zvAKVGDpH+X6sknwew7Sh7kJgflMBIX9LNn/ZbCw6iazc4k kUewY9AM5tUbOPk3m415C9nfZKSXThVGFKLz6qhhkRkTidHcJc7+X6jkpe90vHEyAXoL Sx8Bq+VNYVruSErjEUcC205I7IOlALwSbA2rIwxFHwx5SC3oZPmHTnHtGAak9yH/7Izm Pn2MX8+1pHxVegQGITeA4B0PMXHTeW7hjspndcY/7v6phoFXNx4Fi0A3cr4ovfvZ98cp 7mvcCKkffuiIQ1/Q6aTfpwqWUMapCfhrUyZfyfoYQEP94i2uW5hmhhqZPmvnB5dtsSkt kU5w== X-Gm-Message-State: AOJu0YzfMkCdswU+KlzQ4fMVRl6DLvSwPSV0VxwhXJZaJtTt0nVObTE+ Bdxj9/YL7SkWrJ5L1wDEd/P71Q== X-Google-Smtp-Source: AGHT+IGfkGw9y388wqErZbGuxg5O4sRO6G1a56lBOIRT0nXItmG3Y4vPWvZ0dvag+P/jrPSrL3fIAQ== X-Received: by 2002:a05:6a20:842a:b0:154:6480:83b4 with SMTP id c42-20020a056a20842a00b00154648083b4mr35089804pzd.14.1697426595460; Sun, 15 Oct 2023 20:23:15 -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.08 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:15 -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 05/10] maple_tree: Add test for mtree_dup() Date: Mon, 16 Oct 2023 11:22:21 +0800 Message-Id: <20231016032226.59199-6-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: uwbuj1ncpmfiencf18ftfy7rxy38sf5t X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: D73FAC0012 X-HE-Tag: 1697426596-580937 X-HE-Meta: U2FsdGVkX18NnhwNoiLtlhUNkua4Aj0tj3VredhPOhulU7gMz0ZT2We1u3RepY9so0EZIyoQD24ibQIbTYHjtjAGQuEQc2KF62wspt3MYhxNvftb+jy+6V2m0L2D66X4hXUvptZx0jLlypwhj3gXXkRzNR1p0OueL3Og+LkWRJKpf5HetDJXkqFUCKfimOVP2VYtOXXcithbd8wG6/6fs0CQdC5D+sCo5qxZHFy/UC2QGOSLvLGS+7F0kHRiBG+Fpaj5RApbCybhclDZQv115+US8clQJKcG5BG0kWHBiNZCAE0UBeC4oD+Rq6wlK45lseZ6kiIp8Tv83W3qOle+CuhRhMx+3YYjUDNV2UIsG+dVqOFZAQMkvE63b5u2Bd/sDOvm0wOkY+KhliEeq3i12jst1Kh13XSYyTWKGbIoh/A4iJgAp0gaodUTn3eIOd7JGuff7fRgXhUyz82yygk3nzs/s6OfPG5UVw/vJAdB87zHVJRYSwrSPMu855cnB52hR/OqISy3rSAORMuAP0YSRAdhu4OGGcGZdhUYfpyoxDUP8PpS1DhtsWRUOLT8LRyXBW331kRKsjeFpunzVVEJhANzA2bLfmA0mfH+CKrbV42BHdds2cI2EGfK73c3CyBmKGmkpboCHdQkULXCXeMhe3DwEThfTU38i1+vTMXSYKCy5mu7GaZerFMo1+31r9gL3xzJ02kNIOxlry1yrG/+fkvQ9AUoqg143jtqII/yEhbk6/MsscJH69w61thaBihKtqC6Hc9jtwUUq2u6QWqZ1zRlTOTEgFxbchUwyf4RF0wAsTE/RiCovtixWhDlWK/72Pi7tt4ry5/79qoXeUU34JZZyrPdbSV4KdXjqtn1kqAltu4Mp72dEbYQHf3ts8QdZMM9cQLuhHzhq37d4bXAduLEIAL1ZxTV/LxsWE/zHJIgkNyNE1AuRYifZKl7dQTCJBqvfa9VJFoe6c2r5O8 J6ZnVAQz uvKIhXZRSFHyFfy/BjwsIJ1vJRiGV3tT6pnhcRGkKVEEnL5n+LDJ5O3tp814h4OwDEIWuXLB0RYjjuaOe1wVMvzTDh2bkDs8J8ScmpTlR9pDNXTGlsTuIVdRztvEDuKgji1gcKYb78Y9g78DlDh4xLc0NQesGAsC3UwGgY1U0XJpqlbGRFj6PO2n84vOHlD6b1qxiia9ppkuVxMcOh4jXzhDK24Na+sXpOCAFe6oAKASQwHcWkQeYHM+jgnV+ijWSehFqRcE2GkRNpq7ctsaRWfwWZdXTJDjUG0AJLGEhTF2Ax4R89SLnztNNKoJVioZLz0RLHVXF5AQ7sKutyOu9wb2JKxYdJqKBN5kZ+iaLljvhKkP6bkgMyf2T/Q== 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: Add test for mtree_dup(). Test by duplicating different maple trees and then comparing the two trees. Includes tests for duplicating full trees and memory allocation failures on different nodes. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..12b3390e9591 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compares two nodes except for the addresses stored in the nodes. + * Returns zero if they are the same, otherwise returns non-zero. + */ +static int __init compare_node(struct maple_enode *enode_a, + struct maple_enode *enode_b) +{ + struct maple_node *node_a, *node_b; + struct maple_node a, b; + void **slots_a, **slots_b; /* Do not use the rcu tag. */ + enum maple_type type; + int i; + + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type = mte_node_type(enode_a); + node_a = mte_to_node(enode_a); + node_b = mte_to_node(enode_b); + a = *node_a; + b = *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent != b.parent) { + pr_err("The lower 8 bits of parents are different. %p %p\n", + a.parent, b.parent); + return -1; + } + + /* + * If it is a leaf node, the slots do not contain the node address, and + * no special processing of slots is required. + */ + if (ma_is_leaf(type)) + goto cmp; + + slots_a = ma_slots(&a, type); + slots_b = ma_slots(&b, type); + + for (i = 0; i < mt_slots[type]; i++) { + if (!slots_a[i] && !slots_b[i]) + break; + + if (!slots_a[i] || !slots_b[i]) { + pr_err("The number of slots is different.\n"); + return -1; + } + + /* Do not compare addresses in slots. */ + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; + } + +cmp: + /* + * Compare all contents of two nodes, including parent (except address), + * slots (except address), pivots, gaps and metadata. + */ + return memcmp(&a, &b, sizeof(struct maple_node)); +} + +/* + * Compare two trees and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) +{ + MA_STATE(mas_a, mt_a, 0, 0); + MA_STATE(mas_b, mt_b, 0, 0); + + if (mt_a->ma_flags != mt_b->ma_flags) { + pr_err("The flags of the two trees are different.\n"); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { + pr_err("One is MAS_ROOT and the other is not.\n"); + return -1; + } + return 0; + } + + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { + + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { + pr_err("One is MAS_NONE and the other is not.\n"); + return -1; + } + + if (mas_a.min != mas_b.min || + mas_a.max != mas_b.max) { + pr_err("mas->min, mas->max do not match.\n"); + return -1; + } + + if (compare_node(mas_a.node, mas_b.node)) { + pr_err("The contents of nodes %p and %p are different.\n", + mas_a.node, mas_b.node); + mt_dump(mt_a, mt_dump_dec); + mt_dump(mt_b, mt_dump_dec); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + } + + return 0; +} + +static __init void mas_subtree_max_range(struct ma_state *mas) +{ + unsigned long limit = mas->max; + MA_STATE(newmas, mas->tree, 0, 0); + void *entry; + + mas_for_each(mas, entry, limit) { + if (mas->last - mas->index >= + newmas.last - newmas.index) { + newmas = *mas; + } + } + + *mas = newmas; +} + +/* + * build_full_tree() - Build a full tree. + * @mt: The tree to build. + * @flags: Use @flags to build the tree. + * @height: The height of the tree to build. + * + * Build a tree with full leaf nodes and internal nodes. Note that the height + * should not exceed 3, otherwise it will take a long time to build. + * Return: zero if the build is successful, non-zero if it fails. + */ +static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, + int height) +{ + MA_STATE(mas, mt, 0, 0); + unsigned long step; + int ret = 0, cnt = 1; + enum maple_type type; + + mt_init_flags(mt, flags); + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); + + mtree_lock(mt); + + while (1) { + mas_set(&mas, 0); + if (mt_height(mt) < height) { + mas.max = ULONG_MAX; + goto store; + } + + while (1) { + mas_dfs_preorder(&mas); + if (mas_is_none(&mas)) + goto unlock; + + type = mte_node_type(mas.node); + if (mas_data_end(&mas) + 1 < mt_slots[type]) { + mas_set(&mas, mas.min); + goto store; + } + } +store: + mas_subtree_max_range(&mas); + step = mas.last - mas.index; + if (step < 1) { + ret = -1; + goto unlock; + } + + step /= 2; + mas.last = mas.index + step; + mas_store_gfp(&mas, xa_mk_value(5), + GFP_KERNEL); + ++cnt; + } +unlock: + mtree_unlock(mt); + + MT_BUG_ON(mt, mt_height(mt) != height); + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ + return ret; +} + +static noinline void __init check_mtree_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count = 0; + unsigned int rand_seed = 17, rand; + + /* store a value at [0, 0] */ + mt_init_flags(mt, 0); + mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(mt, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, 0, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, 0); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i = 0; i < 30; i += 3) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + /* Failed at the first node. */ + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + mt_set_non_kernel(0); + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + MT_BUG_ON(&new, ret != -ENOMEM); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Random maple tree fails at a random node. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + /* + * The rand() library function is not used, so we can generate + * the same random numbers on any platform. + */ + rand_seed = rand_seed * 1103515245 + 12345; + rand = rand_seed / 65536 % 128; + mt_set_non_kernel(rand); + + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(mt); + continue; + } + + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* pr_info("mtree_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); void farmer_tests(void) @@ -35904,6 +36261,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, 0); + check_mtree_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); From patchwork Mon Oct 16 03:22:22 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422449 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 BE069CDB465 for ; Mon, 16 Oct 2023 03:23:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1A33A8D0025; Sun, 15 Oct 2023 23:23:25 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 154508D0001; Sun, 15 Oct 2023 23:23:25 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F36B38D0025; Sun, 15 Oct 2023 23:23:24 -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 E4C8F8D0001 for ; Sun, 15 Oct 2023 23:23:24 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id C07B7C0A0F for ; Mon, 16 Oct 2023 03:23:24 +0000 (UTC) X-FDA: 81349879128.27.82CB697 Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf12.hostedemail.com (Postfix) with ESMTP id EEB8440012 for ; Mon, 16 Oct 2023 03:23:22 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LRMqQglo; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 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=1697426603; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=R+DvKzhCqwTo/7PDFuD4q4JkQR3uEd4fBbOKOCl8Gc1OwYYEpwVb0usgXB54EJPBF9uOK8 3xsa+imQgJIAxDOWpSb59pLNwkUPCGAaZCkqcSgIMj8sNNoDnRxg3aqjHAkMkUeHUf8Ixc hZaGMk96ilMq4GkbI2YJejV4uwKj3Oc= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LRMqQglo; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426603; a=rsa-sha256; cv=none; b=cCBlty9DdrZHJ/bLljxNGufk2+DUagJW5QZBZI1uTun+MUsujzix8e2JLg4hEyjnj4d5jB JHQqLBR5EyLTIZbV4xgTPKB6QYXGwc1gQ8x5NZouztI95Xlydilo92enf7kPJvfqnUBJk5 O6pgQ0FBjzlHk/IPV2Lhcaxm+KNvY0Q= Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-27d3ede72f6so2177542a91.1 for ; Sun, 15 Oct 2023 20:23:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426602; x=1698031402; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=LRMqQglohKS2fvPx+deBHqKj1iSxIn8NmpaqHDe9naa4xC/YBkpRYHvqCxvVX6TQT6 vDeY6aNIAddAgux4qyfBwKj7o+A/15VpltU0JFjmzg8IZU/3v+iKtPgO1XyDZi2IfnaJ kV4NAoi6JDCgactdU9cq6fCNoXH8McI771rJz8fsiwk06B4g7yAqeCtNCbEmSgKlFDVm UCC1RJb8Id59gBrQzCB9Roq9f+sTta7+4eM4kze/8nZWyGDorzXvtrYBGzltZgUU/DHj WdLNRwngnCeOz7CeLb7n7R1Um8+fjKd3NJ4W6cXhxMGzsV7iVKLh6igvba2J+r2bRfat zmow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426602; x=1698031402; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=KkSJl4R+/yYFUytzZrkFhWdVCBuWwkQuEjcs30G5DHC72vONafUM8OzAgTOc132uuq e7tT0RKaXVO4PcZ48ebxLb2uMoRHBcRdAdBHksLPp/pwvGDOZJdrpr64rmMko4487lc1 WvjkvQW4DX0OH4bvYkbIyq0+2Eo5Ien58CBmGQ+cbDOAMFKDCr234L1/o/zja+eS6dez 3VU1DpvZ7li3OeYCbw39dIVx3WqXJ5Vk8IfEvOWC9tA9S9h23MqOUOGN23F9KfTmBhaX 6VBm676XvUkcWIY7wCO6DN1ItLzbMuOqZ9LJ1BfacID36xVizRXx+g8cvMbtMyZpxGrt Uhug== X-Gm-Message-State: AOJu0YzvGCPEMAkvjdodzHGDiyor/b6DAeVieSeDNzEqoB6iTxaZU10Y p5vvdECjclmsOTPbhYfdgqYhrQ== X-Google-Smtp-Source: AGHT+IEmk/zJXO2kK7nOf720yU64zVWPpcUxkrQhPVMBOjATtllYWJlNEGVjqoAJdP0W8HkSSk7e1g== X-Received: by 2002:a17:90a:f408:b0:27d:f85:9505 with SMTP id ch8-20020a17090af40800b0027d0f859505mr11824455pjb.24.1697426601858; Sun, 15 Oct 2023 20:23:21 -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.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:21 -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 06/10] maple_tree: Update the documentation of maple tree Date: Mon, 16 Oct 2023 11:22:22 +0800 Message-Id: <20231016032226.59199-7-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-Rspamd-Queue-Id: EEB8440012 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 5yx1o8tkagtn5x84k3s9z4735qb9d5kh X-HE-Tag: 1697426602-218329 X-HE-Meta: U2FsdGVkX19GLQ5akti1YsKDQkv9liUrCytgDyBc1TgZupLNIv4Nb8O5Xixp6xRJzNVlU3/cjIuq7ws1LmbhV4xKjcSB52PYU0mxO0kN8et8VEyeEq9+KKX8erbhHlokUkbblUFr61Aq9LnVAw5JIdR8QLEk3C1LYGZscLRV5f1X15gh5LrdaLovMvipvtzprx6Sx+xhddpRGDH7HrVxMN1y/OmUinwzKxNmIHHVNJNrL/33nieCJPzynMKqezQEKQZ26gzNQDINPypbJfyG7/kJi1/5yZXIxhx8++JFteuOtm/0MnYz8f9120euzj6abR0sgAsEj8kBsZN5FXMIcp3/lMVzuH28FfIYU/9jSSEs1UojoVsoV/QfmMXFWbN4Xf8YCuxM76TWz5JKcTBVkNr62YdSnzgtjk2KTd83BiJYW71Vy+0msloJE80mINk2Ws17uOWGjOFKJTTVhSDmTzC6jyeW3SJNzDBCdpCxMdIF/VA4rCZ+l7ueQHhNPXkKn/cksc61OoVsnX1S8YNKsdG+6UDnrC0RsAuayGmBpNLmuwMbW6XL61wsrNHD4N7+hQLKGRjdeC68Wiv63bWAzyMFOYbLPBpQSf0yRWbR8DvArIAyYVMTAOJrOEVgV33Rg4337cqC6LAdqffYkWpJD4fVoNIBqxjBWRSoWPMeAyVibXgEbL9F5Wp4pJ9iyijBFRu8oPpww7em+TZBUnFv7vEmytVMYwICssfWJXf9U88wtRn5hRYaNdzF02WecHlCvAxNN3PcTYohwRCuAFygCZKK4Y84IJPRENadzDDIZ/CY/sGLaMMr3UxDKYRS1Z2HW22XbX4fx0tWKvBJaQt3lf7R46TGCHI3BrhtLQzs8zU2IstLdTb7vQWDYsSc+pWLEJQXU2yqp+TIXdt8HFNIN7lg4xeBJMvRAcXNVi5uAiDRjuo1dfO8L7Xcf8qwp9ZFG5QcHjEYKfN6h5P+JFz PDpNCXEJ yrjoK24tkm9aXQMT1UaCC0debvtG/cY6tP+eZY/9oEcQY1pO/7x86PpxPJNQY8vE531orNtVm9VvnXlJPqYCz+uS6giRy6JHjt5D5Gp45TaSPJa1p6i8LgRVACFuDkAXUkJ1oAjlNGvd56dYHJugMaZtdSA5L+87Cy+TBGRwFAKA50b5re1HoDdEi9ZjVVlhK0NV5FsJleMT6dbEvlYbfoSvD0Gqp6JPejZjFjpN++6SmQFJNPXD/iSbAb73ZSsc/bgzl6fppLb0WAdAb4LdkdzXh26DvEyA5UFlBwnzYg1Boufy6SlRXGKK8QMYLNDKxF5NFjra8p6lDR4A/Frc7teiXlNQ32kgiIAfuWFfl4pq8n6zZoswUFo/2MCKOaFtkZRwI2IkjbV4U89Xs2TsNN4IXSIVcqpmZVZtAywefuVKBPt4qoVG/ivfbH/0KPduysKeLbGSao0Bo0MNZyE8CQf006w== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000390, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Introduce the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang --- Documentation/core-api/maple_tree.rst | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst index 45defcf15da7..285e2d2b21ae 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -81,6 +81,9 @@ section. Sometimes it is necessary to ensure the next call to store to a maple tree does not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case. +You can use mtree_dup() to duplicate an entire maple tree. It is a more +efficient way than inserting all elements one by one into a new tree. + Finally, you can remove all entries from a maple tree by calling mtree_destroy(). If the maple tree entries are pointers, you may wish to free the entries first. @@ -112,6 +115,7 @@ Takes ma_lock internally: * mtree_insert() * mtree_insert_range() * mtree_erase() + * mtree_dup() * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() From patchwork Mon Oct 16 03:22:23 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422450 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 23944CDB465 for ; Mon, 16 Oct 2023 03:23:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B40768D0026; Sun, 15 Oct 2023 23:23:31 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id AF0668D0001; Sun, 15 Oct 2023 23:23:31 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9B8648D0026; Sun, 15 Oct 2023 23:23:31 -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 898B68D0001 for ; Sun, 15 Oct 2023 23:23:31 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 62579120A69 for ; Mon, 16 Oct 2023 03:23:31 +0000 (UTC) X-FDA: 81349879422.01.F5CE292 Received: from mail-pf1-f175.google.com (mail-pf1-f175.google.com [209.85.210.175]) by imf17.hostedemail.com (Postfix) with ESMTP id A25A940006 for ; Mon, 16 Oct 2023 03:23:29 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CBEtQwkg; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.175 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=1697426609; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=4H+Q2vr8xTn7/RFYtcTp1JndRSfV/y6DUWSX8xcyXBAyZHn+QaS8Oaf6GGXA3JobdarrCu wCQLClp797/LUEaCAYiEzzP0/TSrFLady10z5ZFqLZZLduL4OK/xK/DgQopsuhUcJpr1Bn Tyv2D+BiKOCS/uWzkyVCLfRdxB52jq0= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CBEtQwkg; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426609; a=rsa-sha256; cv=none; b=cRJu+8NI5FevMLmydCdtjUlDPGV3ICapkx1B+dE0IyGN0aKC59bK/VjCEBcwlL4cr0Cx3L kEGasa2KMha/Bq6Nbmt47VphsPePAx4bQV76wifCrdM+jmz6Roe4n/ZFCUuHfoNhuwp2aP UeKJXZ+Nnta0eWJVLYUFz8pPxKj2hGo= Received: by mail-pf1-f175.google.com with SMTP id d2e1a72fcca58-6bce254ba56so716153b3a.1 for ; Sun, 15 Oct 2023 20:23:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426608; x=1698031408; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=CBEtQwkg2haKEjFO3GpAUivB6JzBu+XVVUIodp6fo2eWgvfVSAFin8NIognGKfO2cf CGujbAMA5sK6Ulltf86WEFQxoMgvFxzkP4P6h7jZUl6Euopsk5sUmJJaS/QUxtyJOoRy OfP70C5QCa1n9GsahOVa2Kn4SaK0QLpLIKSeHzE+9v+4vC7rktwBynBR4KisrSeUCU4c 6KXR7n4MDHGl/Lkb+soaiFKaT73z9UwteGcnl6PRzaDyg8cAx+dt+PiM3mzw/7coB+e0 DanWXjPQQBJUhr1F/7ndt4w/Wuj3s1+DRG+JjneTkRSlC34p9DltZSDf/kILU2ejlrSm g4YQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426608; x=1698031408; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=xR2df6yW9L4zrPbi5lmgm7DcCXZgh8nM1bfyOE69CtCUolNOIgduXPNBKd3jZHg7ld Bjkf4cxmqrPwO4QBmtuJCYNjtNW3xqzF8MCx0oh02i7VmmObBXoP+xdUnbJZ1HrUfGZr vD9F94qIHGJRpWAasZZdlkPzMNlahL5YE3AbciF3SEBEs/7lZsdgM7y9NhytWTtFjr8x inQWK7cnjcOJKHv2jRP5pMZX4bgM8rUNbpguL9pGP68d4lg8BE6YjMVDAPVQ23ESgGQo sCFkt5+2Vrr0LLx43Pjj7l/EzGxlnpQXgKysqlBekEspmfDorY3fPh4R/Uvk2TOmhsSn d5Mw== X-Gm-Message-State: AOJu0YyO1hIl4pIDnt6VYtKx0L4JyEd6ZNKI82KwC/XBXGyAiRZ2Fdkp SNub5uJILaB2apNcmkRY67aVpg== X-Google-Smtp-Source: AGHT+IFvL4hHx8r3LC1uMkvj+QBP/kQF+gthm2OJTyOv0wHL/s0lrpx6RI7lgcxm3OD63XtqW60qEg== X-Received: by 2002:a05:6a21:a58b:b0:15d:607b:5a39 with SMTP id gd11-20020a056a21a58b00b0015d607b5a39mr34613164pzc.30.1697426608596; Sun, 15 Oct 2023 20:23:28 -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.22 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:28 -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 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Mon, 16 Oct 2023 11:22:23 +0800 Message-Id: <20231016032226.59199-8-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-Rspamd-Queue-Id: A25A940006 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: wt9rngzojfeyd89h7kyxcrxe31ye1y7q X-HE-Tag: 1697426609-826717 X-HE-Meta: U2FsdGVkX19hod8IcljIz4TJpw2Ijh49sB97PIiWeMs5PxUsPW1DqJBnGaQ1wjVwSUHNV2tEqZJ2iWkF+4LvOwxPVyzQhVKkrsDE883kW+S4fGwb9ft1Pg8iY7Vx8cLYEY1ZbDNR1YTMQKV2rO7k5XjwzW1y5sM1qXD0lPhwecqpCmkeg2ARXo4MyReJrIVpGCimR3W2gkAZviTKnVP9Gc61VXZxUOxb5T1rSltxs0hwnXSdGnD/GLIfL2c+uT9AtIxbapQ71fomzsIumTZqsc8wh9ZmVQz2+JtukSh3O4XOAuYSgWZHWMo0XQQG+5xrJDD8tMNj5UxOVTULBGWstx5nUKaoRzuFSvMCGEAj1ApcyCWdSnR187hlBpPr+CUvf6Fil6zjnapZyi4bSbGLYxhxpAyHLr9E5igmYEEokmkKMkRzSg+dMVaa19K6T6UuBAuWBHabj1owVCbRW0SrUdAEIxyuFA6rDyI+JATd9Oly5HY2Y/oRHJxwZD/4NIVYXu5OqJ0CZky8pttt/SPLReD3yRWjlm3dp9wkuiDeR2ASVn/jzhtObLNRM0t942sm7Cm3Fpq0Z/vg4bTIQyh2/DOclPbPnApJZKXBz411U2LLWoy/2jaTYi2VSBfvTwGwyvHyN1frLJWgdZWhC/K94qmWo4e6r+g+NRDCIEyUN5z1eqGXis9hFGA68kSHdZeciqGgRaaOeGsy3hWrbrCbc5DM8NwGfmo9vqczRz3inYO6sYX4LFWMSn6m0+6CIVMqLjvPand/rCvPGqS/Ijcebp8Wa2VhNSQomwUvIg4urML/kQYYN9XvBms6Loh8wAdG9hsJhPrH90COS7cr8qwGJ1y9xu+xsdKOa6tmsOn1K0Avja+ejvcpoD2aGChcm4jPFUYHDeXnzXOy6g3yT5zl8Py3OygBAsWscjCl0FGZqyBLHJcrybL2jYkbIiuLzbgGGIkH9Ed71Pfk1nL4pmg 60LDSFgC 00+dbx8t0gGDldIzYVwTEJxTHH1m/nbraoG4hxZTsJKJrMgt58UxlUI2faI2bGENMpPNz9Dc9cXZHayFEDbAGbeplhj96kdPG2DzG0zGo+e71lu9q4G3OanISTSHpvGi0Iy9QiP/ymNUGhrNNzDYploOA9BZWg2ugNTC5IGR+TieUeF8ogMAN4xiGWfdpfYauzFygk1TCDsYZl0O2aYPLKTHuekpsDXhT0ALiSemq7SuGd8dnQX74RE33jcsVHXKuDaTESYYlmRaayiWGfPvXhCkkA5blTQPliid01xDh8eOxQPua5TaH0aGwfJIFiNK3BKJg2LQI6MME2W1mf7QjpsKC5nxejYXNFUVivzB6LZ0OTzUTtyVSKIZ0dnuDzUkw5J0aBoEZuF1jaM55G3vift0W19jXDm8X1wDtD7jQ9U5GazquPuosHhS5p2nC3OMV4Oxm1Y5JeLK6OAYIIwRbpVl8SQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000023, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 8 ++++---- tools/testing/radix-tree/maple.c | 2 ++ 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 464eeb90d5ad..de470950714f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3585,10 +3585,6 @@ static int __init maple_tree_seed(void) pr_info("\nTEST STARTING\n\n"); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_root_expand(&tree); - mtree_destroy(&tree); - #if defined(BENCH_SLOT_STORE) #define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); @@ -3646,6 +3642,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_root_expand(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 12b3390e9591..cb5358674521 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36299,7 +36299,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Mon Oct 16 03:22:24 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422451 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 F0794CDB482 for ; Mon, 16 Oct 2023 03:23:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 882B28D0027; Sun, 15 Oct 2023 23:23:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 831DB8D0001; Sun, 15 Oct 2023 23:23:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6D3328D0027; Sun, 15 Oct 2023 23:23:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 5D25D8D0001 for ; Sun, 15 Oct 2023 23:23:38 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 3A4911CB463 for ; Mon, 16 Oct 2023 03:23:38 +0000 (UTC) X-FDA: 81349879716.07.9BBAB68 Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf06.hostedemail.com (Postfix) with ESMTP id 728B9180008 for ; Mon, 16 Oct 2023 03:23:36 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=OrHMjy6b; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 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=1697426616; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=zrQIFz7l5uL4fT5lpMEEF6K7AbOcnnz74Xk9srZLul6BAPZypkzsHlqzAIiFpBLQGS33FZ TIQJK6GmtaZo9GNvYXDQjc80z30lxXJeLKmtU5Ptkj18YuIryyWOuaa4k3Va1+mKrKIlnV 4emPU5UnNX323Ef4hoCeCnLZjltaZwY= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=OrHMjy6b; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426616; a=rsa-sha256; cv=none; b=7f4YIJM2oVnN7fotuz7MiDtRzNIyNdf7x20J9E8sn8R/Ou8lDsU16z5p5t4dllZOe4ZMKP L9p5y7ChBYBO901oYpvxX3qf73htA36OaHzHP1qDLffVH86MtrHLeKTx/R9GKHfRt3bivH R/Lr+GuMRGg7gEMfTcS2KafiRhxEhR0= Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-27cefb5ae1fso2083179a91.3 for ; Sun, 15 Oct 2023 20:23:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426615; x=1698031415; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=OrHMjy6bjcf2OwI+PieV6kSJwqgnhVT3qNqL1HYzKm9U7xwOEyIM73N612PhCvLEKV gIM8icFc3vsRjJIRZAjhu2hQ+Dw1MvDNq48ErMPDCWwxvlvPq2MiGqlNeysfZ1w/J4Su 5aPJpdVNHUPh2xNxC5JYAobmenR6ULjraUfSjiCTn7ftihdRxlndW9+DT0SLEK3lq+Tu 1tyKExKkkkzM54swyDWwLr75ghhircyBUGizoz1IkpnUBOq8Ckh5jJhVApBelSPTs5ji Ez3LT3aRF8H8NVB8zobk39OypN4Qh62e4rBH8GaaA0KbyMZ5wONdsI4+YtOUce9KLgVO vgbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426615; x=1698031415; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=SqAQYGdABRn2NtGtKNvT1tNF3JkHG71PBmaXvfNIFGfDV4AsVt+1Cyvc7YeYr++xEI HJ4vDp8lTQduGpcew6m5825WO71VVudjhXky/CnpCO5iJTOZgzU+Xjk1d1WSpv0Qecno tjcYMUpqN5NFijQqSu+GkP0u8JSLwPkt+865iYvRA9v9saMgLRTZh7eOPqu2v+PQwPBn ykCmoYAlWR1j6qZ9YU8zu8X0izrK34ALt4u5/Vqeoi2SUPSnOh0Fgy5c06p5kyWwqcJM GU/L+aKV+gCq8u6Rtc85j/TxwVPXuw6I03E2nYHtTASlg/SMbPv8foVk5VTM6rnWbN0s BliA== X-Gm-Message-State: AOJu0Yw18KpY3gcCIaJty95rUIdIcdCThhAZXfNampk4f/Q6TRvX25Br ufjlSVjS9eK3CJVdHJHFi/SEiw== X-Google-Smtp-Source: AGHT+IHmA+WtBu9NLQQzhIWS0nTFs0epfhl1qYL4Lf5DRNzLjrSSQh6nGRADfVlcdpst5WMiKPi/tw== X-Received: by 2002:a17:90b:4fc2:b0:278:f907:719d with SMTP id qa2-20020a17090b4fc200b00278f907719dmr25042669pjb.48.1697426615383; Sun, 15 Oct 2023 20:23:35 -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.29 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23:35 -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 08/10] maple_tree: Update check_forking() and bench_forking() Date: Mon, 16 Oct 2023 11:22:24 +0800 Message-Id: <20231016032226.59199-9-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-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 728B9180008 X-Stat-Signature: 1q7m1i9j6787ch1qimn3zo11xhjetamp X-Rspam-User: X-HE-Tag: 1697426616-344005 X-HE-Meta: U2FsdGVkX1+ULbCtxLVjIpH8bK2XxRRCsOcieD5IP2IsyGuEH+QGPndxSNrPpK9NHez321BHaL4PFn7KlITw2uQqVbL8m9kJjSGWo3ec6NVQhsyOgfi46joZAUV2q2d2KPTxvZqrxRbFjinFx7JQw+bBvB4j+ooly0FEK9P304Z1gQoQA0Y8l/5otDPezrjHkC4Ap7udGlEl6x+NqlHS4UikaIkOYaxXPczR2rUz+nnwBuPZHXEpTWhgcjHIgv3fPhkWTGp4zZ/pYRd3fTzCy467Zl4cXoUATAjquC101AMDDUGdrmU0QnXqnF8KNCQYjP18DLyY+a0N8szFJBCIkiwgncF3TdauGH6PPt5vblrnXMGAfl7FROkf0jHWqswyTmhAZMjPXYXUMEI9ZOAHrqTn88HM6Lo8dk4zcx36/vxP18aUp3kd3pMDej18Fb3FVPV+U0rxKWxbiz1J9CTsU6ApEGdvexrNiwC9URboVPHgGJvfK8oHVfju8H/zEzAwTYXiKgkLnxMzO2kHnYLc1bjuhBe8DsFQynxOf9kd9r0oWNRrge+ZI8Um3ThmDWGha4ls9gW9AGW9s/MYu0t4cXfpE60leCxleo2PAVkgAXGKhm//o9Hq140bgpwS/m0rhW8FK55SKuR0KHEqvlV38YEOKvEdhgku0EeDXUrQnBtWIqyHENm4W+Eni6vWk4xRmIu+B21galD3/5CEzZHfxgadQJNJ8cmAi1uUsqY8HDHalEZ4ORu1Fvp7mgVckR28HlaE2iAFzxX9f0JsEG25frhXFPH/y22yHMHmp6QIJST9j9wEbGljiAXNn32kR20gjAXe4lmV8dFCR/yHGQmdABzrJ0jpDCV9+McrrJwvJz3SSTz5TZAKczNW4s4VnNBq1N06VLEvyss+1xdJTAwgQvpl2PaUeUuoIQb6oO+iAvSV+C7QNuQb/xmaPQZ57cHou9soZ/y8kfYolmik9CT WZzWxgrb IXsj6VD2SbdD1KQK7Dh2jMxTh6+lDP32eaCjUZs0PF7dWBXzG2TNlsLz0iuDi2cIrWAZhPJ4pTmyyrHLHMwi/p1LsqUFzSyM6ryOyJODq6tb9Qozy/9t/C7+n1E/KuetUoYILezz4BiXDxas4c4UshZk6v/SAMOCeQIWmc1Z3+RescW7vCQ0o/1Z4rsK7tBjoTB4mUI494zZ3YC6wxoCIFTbQnJyaEwG18yaSgRzRoOoTM7D8GRBq5pB1WishjCi2rsPLcV3qbCGm6St03E/QFQiCnaj1CjA/zAhDpP7eLZMhsbw2VjfuUn1gzdpVfe5IJ4LocGzSk1NLBpqV9DU6WOmjtvIrpkuRS7nP+LtDKj5cPk/oUEk2qWIT9bChVloFgilrJpYob7wg10njB5qpqrq6wUnulR8mHhLbacdHw1uXuTCz81ujwC+uxeZi7etwOfocAfQNIrzNNGx+lJnk8it/iA== 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: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 117 ++++++++++++++++++------------------ tools/include/linux/rwsem.h | 4 ++ 2 files changed, 62 insertions(+), 59 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index de470950714f..3e4597fb49d3 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1834,47 +1834,48 @@ static noinline void __init bench_mas_prev(struct maple_tree *mt) } #endif /* check_forking - simulate the kernel forking sequence with the tree. */ -static noinline void __init check_forking(struct maple_tree *mt) +static noinline void __init check_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134; + struct maple_tree mt, newmt; + int i, nr_entries = 134, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); - mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - down_write(&newmt_lock); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + if (ret) { pr_err("OOM!"); BUG_ON(1); } - rcu_read_lock(); - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val); - } - rcu_read_unlock(); + mas_destroy(&newmas); + mas_destroy(&mas); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); + __mt_destroy(&mt); up_write(&newmt_lock); + up_write(&mt_lock); } static noinline void __init check_iteration(struct maple_tree *mt) @@ -1977,49 +1978,51 @@ static noinline void __init check_mas_store_gfp(struct maple_tree *mt) } #if defined(BENCH_FORK) -static noinline void __init bench_forking(struct maple_tree *mt) +static noinline void __init bench_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + struct maple_tree mt, newmt; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - mt_set_external_lock(&newmt, &newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } for (i = 0; i < nr_fork; i++) { - mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas.index = 0; - mas.last = 0; - rcu_read_lock(); - down_write(&newmt_lock); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mt_init_flags(&newmt, + MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&newmt, &newmt_lock); + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + if (ret) { + pr_err("OOM!"); BUG_ON(1); } - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val); - } + mas_destroy(&newmas); - rcu_read_unlock(); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); up_write(&newmt_lock); } + mas_destroy(&mas); + __mt_destroy(&mt); + up_write(&mt_lock); } #endif @@ -3615,9 +3618,7 @@ static int __init maple_tree_seed(void) #endif #if defined(BENCH_FORK) #define BENCH - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - bench_forking(&tree); - mtree_destroy(&tree); + bench_forking(); goto skip; #endif #if defined(BENCH_MT_FOR_EACH) @@ -3650,9 +3651,7 @@ static int __init maple_tree_seed(void) check_iteration(&tree); mtree_destroy(&tree); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_forking(&tree); - mtree_destroy(&tree); + check_forking(); mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_mas_store_gfp(&tree); diff --git a/tools/include/linux/rwsem.h b/tools/include/linux/rwsem.h index 83971b3cbfce..f8bffd4a987c 100644 --- a/tools/include/linux/rwsem.h +++ b/tools/include/linux/rwsem.h @@ -37,4 +37,8 @@ static inline int up_write(struct rw_semaphore *sem) { return pthread_rwlock_unlock(&sem->lock); } + +#define down_read_nested(sem, subclass) down_read(sem) +#define down_write_nested(sem, subclass) down_write(sem) + #endif /* _TOOLS_RWSEM_H */ From patchwork Mon Oct 16 03:22:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13422452 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 13673CDB465 for ; Mon, 16 Oct 2023 03:23:45 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A07AE8D002A; Sun, 15 Oct 2023 23:23:44 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 9B84A8D0001; Sun, 15 Oct 2023 23:23:44 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 880198D002A; Sun, 15 Oct 2023 23:23:44 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 7A54A8D0001 for ; Sun, 15 Oct 2023 23:23:44 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 5F5C41CB4DC for ; Mon, 16 Oct 2023 03:23:44 +0000 (UTC) X-FDA: 81349879968.15.9EF92A8 Received: from mail-pg1-f171.google.com (mail-pg1-f171.google.com [209.85.215.171]) by imf25.hostedemail.com (Postfix) with ESMTP id 95D3EA0008 for ; Mon, 16 Oct 2023 03:23:42 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EpRufxpO; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 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=1697426622; 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=AVtomugZIRVe5XO/IomDBee5ri378ZRM5/INN5nVYsk=; b=RQF3CqDJfJR/ucxR0D4FZSnI/WL1Xygkz3iZv5ptX7MG+lNqoDzFKU9ARif5ARuMA8MqZE B96vxlIVuZIoW9yf18H1Y0yP60jFZuNJhDwdUrSFeivE+5W+osPJZrc8E9zA6l860n570I 7+Hd3/iRtZg4nFc9phc6NKX780l+kEk= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697426622; a=rsa-sha256; cv=none; b=6qDPQpKwHe/X2gVm0WRD6feGJU6kkjq0zQDSR1YWTpCRZKXdvH2S93y7j+E5aISG3hhREI CVgetWVn3mZ9GDVC1Nuvh5czr/uAYlElMZu2FLwg7SoZeI/V/PDE07SfpLXIlHHJD20Vdi Qpa9NhB/qMwlq5C3XixIBPyAlLUNIdY= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EpRufxpO; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f171.google.com with SMTP id 41be03b00d2f7-5859a7d6556so3008845a12.0 for ; Sun, 15 Oct 2023 20:23:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697426621; x=1698031421; 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=AVtomugZIRVe5XO/IomDBee5ri378ZRM5/INN5nVYsk=; b=EpRufxpOd3zFayw7sN/jwNEpbeL0MX1O4zAF9x5n4L4bN6P8eQ9bvYQNaVNu3jRnWE ZjszyzZremxyBfE4fdG3EfIvv3NhS4I/KyMvRLOOoIhJct3pIcV7DSMxB8muANBooXvJ 3VJvP20VsaVUGy80TdeCZKaW57Oc3UW7ZIJraGR2ZqffJHYWRqRzxqCmj9XOUsOxXazs fRKL9f7e92cKjzz0F2e4GyS2MeOtcM2K3W5IizNqI75fRG9EhJkc5H0mjpwUyGdNGi0H Y4yJGofa4v93bTqywyvQj+6e4RlH96MHLRmLtEtG5d8cxOjaCMh2dp31HlCnCd6jhCK0 883Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697426621; x=1698031421; 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=AVtomugZIRVe5XO/IomDBee5ri378ZRM5/INN5nVYsk=; b=noivsorRbIw9lNeBeenlPhu7MarRhzEQTvcUB2SZq7UQU3n+nSx/ldZt0XiIbo37Oc HETfg+SZQGo+DjZNfdxA05PhAak1E6twoD0f+XBWQT+gbrzpsqvbUONlVZ9AbQMBxEwj NuDfGxEZcCgHF879DYAosEd/HOuvBr+EywzhEPdLIaNE0KifNavuWzgvsZvvMfL9m8lf qVt4lM8sBKUNaN4uzOYxZRmh6H68r42q6fJZG9JxVm0exMRsq8LEKAg4IEAywL6wMBJq xQwxtML/BDWCh42ujr8VaP0W/00DxkZVR6DhDRxLi/7+8edWH/AhV2zpNYVF4Os++dh9 XGew== X-Gm-Message-State: AOJu0YzhZNKX8QT+EvUw3ajm4oxnqHBGAcQUuYIZApaHGKEV7tqbWvM2 +wIvUiaFYI0nfY1DtWx8V3lmig== X-Google-Smtp-Source: AGHT+IHSb0DNGBGR2h/8IDjSmu+jqGvudTUl4FEPI1UTDCPUIrsebdcLp2Rpr+bgZ6cxOHBljaILuA== X-Received: by 2002:a17:90a:d48b:b0:27c:f2e5:a82 with SMTP id s11-20020a17090ad48b00b0027cf2e50a82mr15318761pju.15.1697426621551; Sun, 15 Oct 2023 20:23:41 -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.35 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 15 Oct 2023 20:23: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 v5 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Mon, 16 Oct 2023 11:22:25 +0800 Message-Id: <20231016032226.59199-10-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-Stat-Signature: a3g36rhczj479gghr14f3ofc6neyta84 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 95D3EA0008 X-Rspam-User: X-HE-Tag: 1697426622-684001 X-HE-Meta: U2FsdGVkX1+Hmv/M1zu9P2bxDYZfhtRbBQVQxscnw43o15+e4vm1//Nu4+16JUCBsRLp8xOuS8uJaKGNNnbGvcQL8GVGZBmb3Cq2ghH5xS5BmT39/Lb+pmGJJuCaFs5NKeIujEh45/GlVO32msHoM0lgdFRPAaU1XZTByedqSj52ITdcvRNC8tFyFGXOIFwwxYMEkeUnjQEXBttyYe3YzJh9so+I2jZqMVJ9Dyl0N7UbTbx4I7x36oaUcDnlZbjhYIohgxXD6HXBE7HQjiLVwKJyn9xrD1CofwTjWjIZLzZNP/afMoppfktALO5WCXmdpsBkdU1sZfjQvOEg06R/uZbFSqPpseEKSTbeh+ZGGqU8kEJhbTmuD2o7B7wUsAL/32XloNLzfDFNCiuKWdYjqa5Y3x2cANNfTb1rHpPDd4Skc/7qadeAqy4A6WGu7SYT9CnfkkXjkFJ61ok/TuYNEjBjWn7XDZnA62eot0r57fSsm3uss+t9tHSZDm5hbcqHzoHg7nYU6mF2cz/p7fZvVcfscHyDWbFgbyvFvQJJM1SXpEucZdNykdy7IoJ1LuYZW+MNUGvfzGp4wUh458NnFA3E1mqtlFNZQ+dKxK5Csu/CBwEkFxb+R/QRP3jOCB7soHmblgkRIqqD6XgX8mPhi6aO0J5hQj8dXlW/Nt+XyF9hQFi5PlSb6sZE0PICyiIgTfF0439+JES+CXdvMRiUJsMXZbpLyK3lCfsmNtb7DDgyuka1jjwFIBNN60wPvciHLB+/r4Wka9tmUsVHEiY0I8mCjRUiz3Lyr3Es155YL9BsWw3AbnPI1hCgyZcDSiXkd9PfeYB6QSLaZ2G0jgOQ4NmUqnfIEVcaYtRuI9sFG3r/PjF9QnQRZNMGeI9DnJ1I1GZmXz+mMjvUaEqXOtleLmZgrMxKoVWYF0kW7t6KQTs5gpoVxGXIgaQ85gkj78mpcFcayT2RQRp05wYQxKu jl9S/+fF nNxOajtCT6KJfOq6tQmVEkwwKClYWnuKxKUO7oL/O2DzMx8/m2uob3QGOQ4tAm+77LkAIz/GdgKGKXhdoq2MPUbSinOFZP63ifHZ2IXFSlAU0B7AsutAXAFlEfM6pq8DOdT/17Au0vtclfeDh4YDVtrw0FHFoO+bmBabGiavPy1yoZ5O8CX9xMBTZ4cBGqnpTpZNvR6nfPYdilpvpuiub0CNK+Tw5RUxtrHh6hfdj6JM+EtpY0DpoDcNR7KCGuhInodS8BjWYOsEzQxUZXfdI9FjhDo3Tl9L+Rd9emxaKAAQ5cvfGDRnq3vCyPtbTA/ByarKtBEyyezuXdt/rszaC7gl7+aYBMRBWadEC5o/Bdg9AWA/RNXa9rFaxByOot39xwIWWIdam0DxBPQH+iW/muxDQu+zVDW4koI4JkRYkQ+pn3EEy4RyPnkvZUIcVF63t9LOwvRf4NVJ0eEykinnw49cgNw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000082, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: When destroying maple tree, preserve its attributes and then turn it into an empty tree. This allows it to be reused without needing to be reinitialized. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6e0ad83f14e3..9b5e5580b252 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6779,7 +6779,7 @@ void __mt_destroy(struct maple_tree *mt) if (xa_is_node(root)) mte_destroy_walk(root, mt); - mt->ma_flags = 0; + mt->ma_flags = mt_attr(mt); } EXPORT_SYMBOL_GPL(__mt_destroy); 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);