From patchwork Fri Oct 27 03:38:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438094 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 06052C25B48 for ; Fri, 27 Oct 2023 03:39:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 649676B0386; Thu, 26 Oct 2023 23:39:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5F9126B0387; Thu, 26 Oct 2023 23:39:10 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 49AFA6B0388; Thu, 26 Oct 2023 23:39:10 -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 3A1156B0386 for ; Thu, 26 Oct 2023 23:39:10 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 140FF1CAF63 for ; Fri, 27 Oct 2023 03:39:10 +0000 (UTC) X-FDA: 81389835660.15.122A8E4 Received: from mail-pg1-f181.google.com (mail-pg1-f181.google.com [209.85.215.181]) by imf04.hostedemail.com (Postfix) with ESMTP id 415734000C for ; Fri, 27 Oct 2023 03:39:08 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=TlpYTaSH; spf=pass (imf04.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.181 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=1698377948; 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=tMjhw76FECkOO5zRdU6IjOHgP+3TMOQK2mZ19zJdvuE=; b=wqXlM+DB69bPQpNNTx3LFJC8SaJtvpSa6BCu3eIFPwGKI2pUtTkXJNv3tnI7s38nuLnglW RMqAjZnWqPKMlWAb0F9/6xwHYxHIrOsyLvM4ziRZUNPeKV6ej/Tsjx9vrHJiYNdP9zancl oR8BVA4NiM7y26p+VAWr5pXlI98O788= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377948; a=rsa-sha256; cv=none; b=v9cAsIKGudpCrBjMD1mexvWUN5bZotL95razLnwHSsgTSGO8fpaGakXHVEpcKueKInscGt /wTBtMD/cYEcHORsDrmf8l50MtI4FxVaMtPe3T6FR14qgfCLo//1mMeE4dHR21hUV6LHw8 NimIvFFEqLkF4yYBb15RBLyCXHwQVYU= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=TlpYTaSH; spf=pass (imf04.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f181.google.com with SMTP id 41be03b00d2f7-5b7f3f470a9so1332776a12.0 for ; Thu, 26 Oct 2023 20:39:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377947; x=1698982747; 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=tMjhw76FECkOO5zRdU6IjOHgP+3TMOQK2mZ19zJdvuE=; b=TlpYTaSHDTozxFc2Q6mTuuqZHiY3qWwSD68s4ArcIbLJMGu2Kzeu9dp+olJYLRyJD5 0J3GX1qHRktLSRSUafwNpAm/2eSEfLkzyK8uJ0LgP/2zGlGNdxCZTE25aVKbBmh+Y5Ih wWbBAOWQjjDCILqw5d8vAe/WZnQ98WQ8btclj/oLvzHsie00BOVrx5DlVdhsiA53UV8C mgywIoZc6oylNnYxzodwl3Sx5xFGm5wuwpK1peY2EeQfMSGMAkGsfHU9Cx6BJxCA8eir CUaww2XA1SmPplXayibf5RSbJoEu5bOErVF2aNnzk9qi+8DsQpOFzLijxEVrsn683vxq 23eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377947; x=1698982747; 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=tMjhw76FECkOO5zRdU6IjOHgP+3TMOQK2mZ19zJdvuE=; b=mYK4EOZqIvEne9aSiIXMsmRELSwBYbQaiRY3kjasvcYHf0FE5xYcfHDY7lmkYnlBmV EOJlhhgLxMh33u0DRhTrXr5Z4Q4KB4MkuJJShUl6TifjMFj59qxyvkrVGCgHKHQ0uqbY QEOQUckwryc+YBc0nv3gNwM4kTet5YZtLFEGVrvPTvLqMMoUlM/N2962PZYT3P2ZLhAU o6rTaGP1V/BkYBr8p+gwrVUBxno3NtUG/XHdaKFQeKVp3SzhXFa/0eL6uM/mDqsI5x1T Egv2IK49lO2/P+i+BUm9tKwqihW98zljFxQ1aKXjwFLV3uGRF3A/4vrMzffKDuyschR1 dc4g== X-Gm-Message-State: AOJu0YzmJ56B4+g6trFhXEK2YecQcORCcRLhTM2+Ws5OmOxojOb4XpTQ pqKHmng8QALkdjjirmkIWRr2QQ== X-Google-Smtp-Source: AGHT+IE+9o1D6mC/tBfbhMEHSHxO+4OKy9VNzv+o8iR1rqr4G54ZqAEfL4OOVueaw3fQnMy76xQeKg== X-Received: by 2002:a05:6a21:3d89:b0:17b:3cd6:b1bc with SMTP id bj9-20020a056a213d8900b0017b3cd6b1bcmr1812360pzc.14.1698377946837; Thu, 26 Oct 2023 20:39:06 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.38.59 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:06 -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 v7 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Fri, 27 Oct 2023 11:38:36 +0800 Message-Id: <20231027033845.90608-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 415734000C X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: ewdkn9bk8jb5am5eirkp5rf7pk51d8sz X-HE-Tag: 1698377948-851270 X-HE-Meta: U2FsdGVkX199lK6Sz3/a1E8lRCEDRxKwRHcxDdh4YIUOU9eyRTJJ5ZKF40yBDF8fuJuu3i6DxAYG+Ss/2ES6FdJ9vQz9DNFmPHX9RB64fDgD6l28DEZmhVyazT5EfDWu/uXHJDhgih6oeSOT2DuMC6Y96j8gKvE2i3rgq9BqRh2n1cFsw/43/GBgzpw4QibXeJfMfiStajF4vS9r94Q0TIytDEIJ/jv/4DXYaUIs6sf96G9abfVyuhoNhFo89h4eCOSnk8cMMiMKIjVdnrj0pPVZO5X/Te38cnni/b+xYsdk6OveefmzgF1QHAS+cIUZQxDJy52NfnXSmQpnUUPVo3WKM1XtlduijWtYAXU1ufhf2uMJgSktTtDjiLpbkCMsBGZ1KUbutFLSkltf8n2u6NeM9xoAqe0CyPLUYxKI+X2knbISM1JzD1/FCe08GaP6bFvc7RCcqBhrPOSrdPfsLe1Ic3D8VdOQ3nkP07vSGrhKLDO2GS6z+iFSPfdQ+5TAI4q48Vq0VxxNYZoSx/Ew3RX3vYD/Vwi8jfCfRmAaVEh4IaERrtDF5ssUslpq8V0jsE7KbYUJymkXAubn9RzIHHhpHMHdTpiFJVUd/c7MDxjNCts5iAC28+AA/7IVq2KcSoJOAAU53r8wXA+FRM42b+4IIyJmTv0mSX8WMy8HYJZkzwn3ONstdPIoHzMGCH08M5CdOvN+jaGl7tDklusbtAU2YtsbtxrjlcYTNEsIga/nFjRkpO/082ARi7OAtbsJiqjJjdaCeM80mDV2OlN6+NiwzVrL9SXSzy9TkBtEwU4iC9idX/0ESkowoCugDQcF6CmUlFSvGObe9z7T6/T+Alb/xtjQCIHsC3rNebUBe8j8wIq/I7t5YhuJYZZGPoH0/RAAV5tIERv0sMtV0Hl2+p7c6HG6QPhCmZAha32LrVBf0X50WoK5rQMD05zM9DygNMaaACPwm0m87Oh7X7o wbtbVUiP xYDj2oCS4idx86a2aciSHOeAwYR2wu+Om7x428oMXLv1dRLnEe4VA0iEKZ0bMkl+quMvIP2ssDIahfP2U9Vg7mm9wreLzlutf+632HLfCFFYUoC7uR2SloV0QGbVRuajk8EpG3zVP1u2Hjl3pQg321beojODRvFm1ktfNsJnWZ4nBp9y4f8sXYBZ9+CjtrpRzD6i9L3m9PDYb9NOkN9T2C2KE1OkZ4Hp/ErSiMb0N7oAcJlGW6etn/AeUQE9e9/l5mzHzjPXHWKjgmOVQt68WH1Ctyjc5DuudwBISGIPFtJvv7gzmleR3ND255oO4J/dM2YGWDy/LxWNlFkZmcui9Ci/AJJjQY8XTG2pBYxhHiGfce9nq5QyWIw8P5OWo/bk9bbp5HL7sbzBkgH2CUBTk3llPrrPRWiZxPa+Al3M+YGHvPlhtYKxojIJ4OuBdrxHLVXrD/Jx1XXjxEs89oEbdr66byIfOfyoknO8nLlFu6C3jkDY= 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: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438095 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 4A550C25B47 for ; Fri, 27 Oct 2023 03:39:18 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DC3CE6B0388; Thu, 26 Oct 2023 23:39:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D73366B0389; Thu, 26 Oct 2023 23:39:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C142D6B038A; Thu, 26 Oct 2023 23:39:17 -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 AF86A6B0388 for ; Thu, 26 Oct 2023 23:39:17 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 94F52B6423 for ; Fri, 27 Oct 2023 03:39:17 +0000 (UTC) X-FDA: 81389835954.03.0FACCE6 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) by imf06.hostedemail.com (Postfix) with ESMTP id C5471180007 for ; Fri, 27 Oct 2023 03:39:15 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=aKQAQVMU; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.54 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=1698377955; 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=W3VhzpPT4L+mg3QuUru0Nd/vnRDIbmeOsA1YFHm0EaI=; b=2VuLl69askqss3Sr4uTIxnRtFli0eDRvwFQuzOCmDic3hTowoAieDBv2xDi5AT0p5Ah7/2 g7HzUwcT5fimG/DDFTo+f9PgteZdRwiIxQI3GFuDrF7UJksESyzOVBAJGah5tBKcGml22p QDmXsTu4w9Mg9b4KiNHO+rnrPcG1q9w= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=aKQAQVMU; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.54 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377955; a=rsa-sha256; cv=none; b=oTHuZMvItNzcCakUPk8K2jdzSfzY2F8RZOq6B2Utf64DLOZJ4SZ0Of83z7faHQWOZT7BDD xuoZYhA2r45cs8Aqj4QCl7dsV5z7wov5gaCl2SGTvOfJ2kh2NWu+8F7AVrEYsfiDdH2Gqs GjjyrAkDpKOifsA+IEMGet5gGWiuXuo= Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-27ff83feb29so1096994a91.3 for ; Thu, 26 Oct 2023 20:39:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377954; x=1698982754; 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=W3VhzpPT4L+mg3QuUru0Nd/vnRDIbmeOsA1YFHm0EaI=; b=aKQAQVMUU1Gkwa/JjqnkQQiFqAjD/JNwurcoZIzsMbY4CcVTulZC5FC+4Dcn7JqD79 UtIKlHO44yMkEEPnmTAzazDaYAdmYUmo9qTKPvyH3IC9XVSD1d9aEkLNYlJ5SBRpYtCR q+26xd2f6yWS0R8LSYrIhlbxlFeVw5eL1px36RvVsj3ATRMSHObLOWn6Ok67GreW6s6K wvFY1iMEkDIQgzQcmtI8bsq7IxDnyt24hj3lBphctCgnLjDglEFE9CVqWFaNJqvD4lg3 yqfx1iuIDEoZk19xP2bJJPVpW08MP0Ix0msFCQ1j4/ZCtWJk23E3cL9rWF1/dOFcJdOr OAvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377954; x=1698982754; 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=W3VhzpPT4L+mg3QuUru0Nd/vnRDIbmeOsA1YFHm0EaI=; b=DhKCxsozmfs+V90Lfp1lMWZbdOKrbPdLXFpGuG/F3H2pu320isx57Bz/KRGTdGyRlG uzpXF7/gzB8XmDPmXI5/cNuePixcm0gmmv3daV+AckVYFXrFZZicT5j+UC5t8NjKwvHM rUrQiBgtGXNRSeDkPS1mEUd4mpbl2VCG6S18aBGuH2Otwf1GJbGZ013GXd+W9FNqBuBS d+bTkPHu0yYdyNjFNmtKWPtEZsXdrywf14rzmRy6Mx5npPdGXSzWSeqVX8et0wroNIYK p/ZxQXQr0Yn9JqWp+eMsasUkOjfs1TBJ9FwP2CdLyan0+9mgLgVtkQI9baMUTXTjfSmU YfbQ== X-Gm-Message-State: AOJu0YxAdIsStA2uf/jCK6jGmOsNKdG9lHunZOCzgllEAu7+AljbV9f1 Vw2xsoAgs5hxwKMyC1NV44PsWQ== X-Google-Smtp-Source: AGHT+IErUxQpQyE6ZDI+WeBZM1BwVdK0VivW/g4FmIFgZocyNbqWFR+q60M1qzJpJ7pOns/5IgyeQA== X-Received: by 2002:a17:90a:bf04:b0:27f:f9e5:b8d6 with SMTP id c4-20020a17090abf0400b0027ff9e5b8d6mr1386794pjs.41.1698377954626; Thu, 26 Oct 2023 20:39:14 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:14 -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 v7 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Fri, 27 Oct 2023 11:38:37 +0800 Message-Id: <20231027033845.90608-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: C5471180007 X-Stat-Signature: h71qxedodemspxijjo8ppq8gmk1spu65 X-HE-Tag: 1698377955-623030 X-HE-Meta: U2FsdGVkX1/mbyLq1XzUcgfyr4QICKu7M3wx1nd63vj+u9/3gXj0XnN485RgvsND7q7+F+toZVxZY+g9sFQtkuUYt+jHy19Zzr6f3SIXUigOFe/kJvgBpkEm+/JZF/t8HBg2Sr0csw3skoFQO1916Ma0ABcjw/tlXPXe5hpYz1zLYUHjbuv0F5lsJwXOI1eSj33oVMqPDfzSlmbW/E8flyAxGBu/q+X0m0mhGVlZrmC+VdvjoHGtfpJepHyUAlgV8V8hKB0Pa3uOSemFXhOt+tS0Rge08nIZVKCzcYd64HgS3Hdbp1zdB5mASy/bAAKUeEqcZBwWu//9Km4GXhYbq9lR1yHr6qo05hJaYSM17ZsuMalsNz3bJN+5vGa7HW0BUmaOauK+qGYldcKlILJBJc9l5MWSj5qYxTSKuhm+03S9n1VnwUzq6Xr2eaT7mfVrXu4xv40FvuYQH4zmail5ExZHXGZD7AusxFzaUn8FiQIgV5mwgfOFDeBPNuqI4nrQottz4r2DfT85ygHW8VulDkSjlNAq9WWw/b7aAD+x4xMWTO5mSZpmrkiS7RZfHM43plrlXX8RlTyN0C/+GaM8SeRKw7BslP+y6wl+1h0vDFyUvsrW9FWL0GANLrb9HmJ9aejCnvRlxJ2U+AoRSDcsxajTBVUidE7EYeYoMgvFCy0I8pG2Kly3oS8Sj4rp9iOBjFVizT9eH09EhmlR8S/QzkQmU4MEi+4lbG9MgcjowkTsxvHPl517W/LBm2lqayiVO5ulgNNakcM/aA0hHNUPA6aMUp5r4xygqS6IxYh3ElxApQF58tMv4Yp61yB5Ru2auJpODMkMIH59AptTvwWzjMsDCyL3h+gIqiWwp/wl52KIdBY1iRZ6S8QFaKvwqdNA9wPtqlLnzmksTXX3SNclwaRotgEfRFoxSIrPe+yCjWyG7nbQzztXm7w1IviWsoQBgiB6iwpK+ar5LjnFxxJ 0YkOOX4S Ex5gvGXfnFRh9s1sJyiJKPnWSgig3iVR+yGte2EzRsKsW2A50qwr9OEfbrn94BXKb168C4y1ts9GcKugdnuBcCBdGHWXXhQK3kG1tfznMd5dZkTyi62GKTZAyRmV9Q2wmnF291VTR/OXnOLSfmBpHMPSYdcCbLObupwTg3UdnSHwXG+SpKpiH9LISC0mlt7qV40SaKLasqIajPoGHMM6UbDfuvLBt6rmsU2aVhD0qPFCOdMIcRj7p5J9JDRpUypV6BZX5BxqMMgsB68KeNWRdOuOjurZvAi3j8bzLC2uxZvstLft7vHqtxY3JRop387+G5uUI/Q69vJSTfY/DTGu1Q776tzcd2L9J8jFIGYkGZuU6MqBhxi+uiqLyY0Z0NTPm9bBtO0pxyDDPj6Q= 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: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438096 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 2A3F9C25B48 for ; Fri, 27 Oct 2023 03:39:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B51E06B038A; Thu, 26 Oct 2023 23:39:26 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B01E86B038B; Thu, 26 Oct 2023 23:39:26 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9A38D6B038C; Thu, 26 Oct 2023 23:39:26 -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 899E26B038A for ; Thu, 26 Oct 2023 23:39:26 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 4330BC0FDC for ; Fri, 27 Oct 2023 03:39:26 +0000 (UTC) X-FDA: 81389836332.12.3435237 Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) by imf30.hostedemail.com (Postfix) with ESMTP id 51D7580004 for ; Fri, 27 Oct 2023 03:39:23 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bz5qeNZb; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 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=1698377963; 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=/zo8HpYmb+yYCFm1lxy89mJtImc6tDFF4y7FplR5LLY=; b=2PRBJTEQZzngtuieu+LZeBeZMCa/fuqWeK8nYhKsSn9s2r3Z/E9foI7ncVB9eCZQRSnPeG 0DgqHgGcIfdPFiqu51KjcbUJlKPDbXIYTEMvRXmJVHd1K/EDLrI9blVvdWChRRILqQOeak WrEj/6ByNG+S9e5QvFEAHuS5+KurJ6I= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bz5qeNZb; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377963; a=rsa-sha256; cv=none; b=Cqo46Wg6CrOfmDxkghBByxRKknEs6bXSNR4NFAPVBK3I2vF1xl5D6xXJvC7coqAiaGezDU rS+OmMDzjNP3Wp+fWPG3/2ZX/bZ0Bu8L5c6MqbsiA733xYp+xPnZDGSxOPXJmHYKnqvdQb gaUwH5SIkKvc2WJvpCMbjdZ02HXS3+I= Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-27d425a2dd0so1378139a91.2 for ; Thu, 26 Oct 2023 20:39:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377962; x=1698982762; 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=/zo8HpYmb+yYCFm1lxy89mJtImc6tDFF4y7FplR5LLY=; b=bz5qeNZberuJUMq9mNgkOb4jesVZ40VXM3VsoXMJ66n3HsPJDAh1txSNBLs0zXURIW 8jT4Bi6W/0t9KocuJxzI3R5jZjl3avVpUoUA/GXAXcT+nGEL+eY7ReA9u9PUR3t9Edcr yzYdCsjEc4+x+AE5zwAQuG0JNK+LPZrUvyIkTEu4rhXbPTrWyOIOEhDma2uhSnNVV6ea O8o8ADRAhTo6jzYyUbRGqkSE26HNqsWV6JUp4sYRX+BFJ1OSBoLIWavYC0Xaat86Vpxy 3LpMtiQn5xMZ+J5oj54UMY2FyJoFj+AScH3EagATWmICtUssEcCgcViE/xyhW/ctiL52 ipog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377962; x=1698982762; 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=/zo8HpYmb+yYCFm1lxy89mJtImc6tDFF4y7FplR5LLY=; b=GBSSnnf7ZN608o84N8htUpQ4Lv1kIam/qX8lf/ECaILlYi3I9qwHoNAhfsW+YYHf9m 8bO+YVHGmZivf7uP9tlgC3bBi+goUI6ILZWfWztSv7qddTOhb+oGMMx/gYS33hrqhj+q E70mpJyEBHlcB5wPldzd94Xa+f6OaGdrg/xlj6TjWu2O11KOKENLYRJebpUR1u2XDYsN 2FRV8nySGfxgXb9AqHfdabl0j070lxmnoXqRqoGgLGSFsFNOX1kp1rGGQMpxyoQ5ZNuN pcblXhbLefDki/yGlT5ALhpP2NLdfZU5aUzadAI1tZhWokDjYinIrKx+CogVhi7QoJzD 5HNA== X-Gm-Message-State: AOJu0Yzp9Z7/Fw3oJCQ8cqAspZ7hdQ+K/T9l8levDGB0nC0kZFx8bwX2 hVhpo197W8FtfdG4VWcCf80I+g== X-Google-Smtp-Source: AGHT+IFJyTlfaI8qKkOHCOjK/mg77WKAGEOyYjoN/vc2NbRHINXO7Ov6pwVEdyk1SfKcLLiGTsuL1A== X-Received: by 2002:a17:90b:3449:b0:27d:3f08:cc21 with SMTP id lj9-20020a17090b344900b0027d3f08cc21mr1456679pjb.5.1698377962177; Thu, 26 Oct 2023 20:39:22 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39: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 v7 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Fri, 27 Oct 2023 11:38:38 +0800 Message-Id: <20231027033845.90608-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: aq44nqwucmcptcirurqoncumx6qe38mn X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 51D7580004 X-HE-Tag: 1698377963-882754 X-HE-Meta: U2FsdGVkX1+WpNJWDKYUZQv1+hBeFULMBy/qtfWb+92wMLP/bh2TJfoisAblNEtZIHNGcQHdHL+BQ4JYkRdTxpBpDQvDfhkF6Ot6CKzqYRdtTl1GKNL6TQDd/vZnLdwmZyw3rl9GFHwWSB3GHpvWGEgjqeyrjMqsLAYEAr4Av/WfaI7l9blZsTGk7Xh36AklY4AgC7k5EiUCmrBue/k1lvq+FM92ahZxV+4+DFEqRuYk/aF0wbNYm8BVCblX626vXcQgQ17GvuXtg32XqhNEkvWReqAexb850QWKnSYEFu9J2s0b8Dd1E2gpLzKTp6LMQ1m+GmpO6GhZZZLEcaZdhpqDupzt7M70XjuaEMAOpBpv7y1qBpQ/MFx4wj5b4/70L7ZYFqCOOvWmFJY/dvHkAQTRCPxyUsEcsl3tCLMtlceASPLLb6cszvJPFredc8bBfw598GVp+GRHJqRV/S+9VaDQpARH9IZusoIFly1LNN3upMU7zeZow6sf7/n4FmxcQ1VxE+++bPpWNIQO09uvdcfFYbw6+AEbJ1s2tHB9CFuq8rvPwhZoPrz5ZKfSZBKiIo2eSi5rfPpBCmT6gSGaEGrRimZ1TRaJ4Slp+YbXS9brKfQeLvWliku5GdWkrWDIoOh8xXwfFXZ6lUJ4F0j7ik3FThrySpPkumlKNFfCIQu5A9ae+nU/0RCwQwj8rohlMbMjSdXL03L2BUlnf0KyTEs0jVQd/mzBDtcWnmmhL7NCTr257mlF8ZwYAY640ovOxFT2fs2Ofda409UfVC++yj1znIR/aY7t0O+ENdPfk/mMNFqvJ9+9Rq8GSrRSpXmUDXT2fPg8YnkSwCnw8Mz1LLBP+BLV1MX8NeNfZcBK6zknkhFNUOq2WXaaxYSaNpI+qZyR3J7FEEa+aPn8ZeG364/3YsZwkl6okPGgernNyUs8ZJBWzYqLSoYx57rc3Y7nWMLlxSXpMkco+hWrM+M 5Aa8Q0me YilFQIjzkHByDlx1nmC/Q3WduPpGX82OuapIvprcTmOaxcZ5CBcL9W+ddLV9Py/UQUDnH4TwLDXqbQvt0X0OVgvr9YCiv34BPafcFk/LhtVlSH41Hzid8xuSJ7F09+iEpuAQ43Yb6CeVVgY+hpln3+nzLoeGXS4qHjbhMdymuReA7Fmbgvh/bKsLf/Ikk69eye5Qh9OWVlhEy4rE5j7JJrBbx2SogBnXc27O7wTh8pFFHKRfWESjEngPiwmiDqjpQ2Q/krlITCeoqVmcHTNGoZ1UgqKvdh7UaufMPYrdnNNth5QSE4HmJr3LB6W1zNGEqxGIqnIzmnA6Mjv9Lu0ggzQg+vzDFXb/7G2cpyIQJK6UcdG3Y6MIjNPrhrx7VbJ93qN9twgGScT+sPBNdIelK8R2omT2Onc4vDdfnmdhnhUtStcxceZnIXNYWPm9p3HO35rvLCAZjIgT8FO7Wob7NydDGV+rBtCfL8cz3iy5XY0BBlz/bNQyrsZMU66Gzk/4vtH92OtESJY4w/LEjSAsLKt32iPMz53PLo57xrXRJs/r3yhM= 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: List-Subscribe: List-Unsubscribe: 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 Suggested-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 274 +++++++++++++++++++++++++++++++++++++ 2 files changed, 277 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..718a222cc090 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,8 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ /* @@ -6475,6 +6477,278 @@ 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)) { + 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; + } + + root = mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) + 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 memcpy() 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 memcpy() 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 Fri Oct 27 03:38:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438097 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 DD805C25B47 for ; Fri, 27 Oct 2023 03:39:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6708C6B038C; Thu, 26 Oct 2023 23:39:34 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6210D6B038D; Thu, 26 Oct 2023 23:39:34 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4C1686B038E; Thu, 26 Oct 2023 23:39:34 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 39FC76B038C for ; Thu, 26 Oct 2023 23:39:34 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 168881A0FFC for ; Fri, 27 Oct 2023 03:39:34 +0000 (UTC) X-FDA: 81389836668.03.C5E18A3 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) by imf14.hostedemail.com (Postfix) with ESMTP id 3BE8410000B for ; Fri, 27 Oct 2023 03:39:31 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="jULV/eMJ"; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.178 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=1698377971; 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=foGetFZ9t8EgLLDV0Dnb7jyONvdftSjfOOfLaWzQbAY=; b=Phgbd1htyxfF/eNGhSXIhxXl5moouSB87PM4ihEoqrj4xPPXLMmcym5w7yF80PQ/0IPRRY 7gwDU88VrrvTKoISUjfBnIC87u4tkGXmUHl2zaRBaqCI8zMvTeoykx0L6y677YUpHyBQal YEAbEn2fevA9MhrQlEYS1bpbk/iTohY= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377971; a=rsa-sha256; cv=none; b=yRQfe8+BZuOcJyIGOYNH2/0go9OjLz+3pWNCGdBVHcIhVLUID50IuzP9VQCouPnTHICeIt Y1DSw0cRHrIdMGeo9Ow/xN8khGgiT3NZEX15cNbrhtKqyCh/N4pkNfonXR9iB0g0AJu2hu BeyxDNckzaXngAHqpw6ZhbjySiOfm2k= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="jULV/eMJ"; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1caa371dcd8so14331525ad.0 for ; Thu, 26 Oct 2023 20:39:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377970; x=1698982770; 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=foGetFZ9t8EgLLDV0Dnb7jyONvdftSjfOOfLaWzQbAY=; b=jULV/eMJetP/m1/CX+iGXRcPz61o2s+dPLtQNvlxGiPrkoZceoa8rC3zT5af7Gxv4p ClZZO/rqnq7dtSTRZrokfFIIohJbUE326ngHIUMg7AsigA4xAofiCHju+Gj7YqbueGAS LWDq0CuczHKhc9XyFLzx7K228Qsy4i5k46W4epXdjjiZM5bFszy2T0gqnprssu6OcAbE 288zWRu3SBC8I28ZVsVm5fnFu9ZpepAJjPQizJxTFiBc1ckQsXdAXdDT3QxatkhltEz+ ErQFafeHLOdqXh1lAGl+s8nqrYIM6FnccfIqFSteUmkEMDXIARDWwVBdeSbb7VVXnjG5 FhNg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377970; x=1698982770; 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=foGetFZ9t8EgLLDV0Dnb7jyONvdftSjfOOfLaWzQbAY=; b=DFuifZjvxgjK6JzdQsEgTBiFOQcg8QOG+48ndEEBLzFuvndFkGauLEIRgEfzHZjzi3 mV+VBxsGxUHMFELoSbycJ1wJrbv8gt/pTOji9VG98U661KIERnLnxfNDBTNPxn5+WrPp xHMDKX5aAAjsu18nKQb9PaiRGIP8nbRc36RlWHqEwx+TNT6P87USTqvUAF4DbKTZm1rm xH9LE2WziKj9ACS1sZ4WtlCASNMDr9fzLiKqB5y/6abIZjGApX4Lnw/mjPxEcWHW5Epk ZwG8aFJ+/K+JHUre21aFL1IgUKueF3dBKDLuL5uH3Vcfw8m1O3bczFWP1YlPwSINsQzp zfgg== X-Gm-Message-State: AOJu0YyMWl9GLMwz3mrDMv1i2CUw+Vg4ygQNVGCG11oEA1a6A+gLxYJm ZB9bMmhO+ekcaPw8ueq4TUmO3Q== X-Google-Smtp-Source: AGHT+IEXV//tpE9s5GCs40kvntDCcan4ON4xoFdITglGv9jOXpY7Lz29M0cQjMI93TcPesAbndJDog== X-Received: by 2002:a17:90a:1a03:b0:280:f4a:86b4 with SMTP id 3-20020a17090a1a0300b002800f4a86b4mr240851pjk.17.1698377970124; Thu, 26 Oct 2023 20:39:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.22 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:29 -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 v7 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Fri, 27 Oct 2023 11:38:39 +0800 Message-Id: <20231027033845.90608-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 3BE8410000B X-Rspam-User: X-Stat-Signature: sxtcjx5r69iei8yijjy6hi37g31chet3 X-Rspamd-Server: rspam03 X-HE-Tag: 1698377971-737099 X-HE-Meta: U2FsdGVkX18lPqxE4UbqaCB5XlzBq1+EYm0SQk8vkI/TPOq5z2vOGvDpO+gTWvhnWkZcOyVRx0hZJJnJuiZB/w4aO6VvD7rhAkJuEtIHxG8GgCEPORX4JXaCN3uoyDJF2HxwyR8fdqjV0gUw8PovxcolPsCyMNk53tFqXpzTnnTzmu9Vf83GgICDz/NXkVo1I4ZzPWglVeArzYSCyMLUp55PW+B9eD8ZCWY3f1CgqtbHVxfZm7k8UHBu39qqZvbFBcYk/UMRP3uDNuu5Qc7x5kgoq8fERx15jU01iieo8U7YsIfqq1W8vQ/lybwl2KcnPY3gwy7JG+ZhH8Lk8Gmth1GmInxdxnRhsn1DLZEk125T5Bt5hY/SK0NASQpEmePwsa5MJWZ1LPULUzmZyz3a6O6NY+TILmv7xFOkwPqgRdMEHxcfUt/7YBuabMr17aeiko1qKWv5RYQADXDDm67ibBfki3upwWcar7vZlXgxXLZOX5trf0TUfTgliDj1+UoZ4sJKXg+sFy70wn0bdYhedcncoNeuhwwvI33d/liESU7dydmYRRUtkg9APeupKBkOBUjkVhvgSqiWDV8lJ80BGv40P05duk9SGIcZbgxytIXpro7HWxhctTnIbt3eVvZnoxLbfYtqKIw4yUdSswvznNcUHaWlwadH2+MHyIQPx45h0hvN301A+zC92N8gvBONljv5NEN4amGb8sucBWj8vFK2Z+lkp6VzQhnOztInxT6eZkxTkloAnGzTrAp9sPFAFASvYUe5FJn5fPX4VPphQTwQveJWY5rAnbnT8EW3QbFKPRxb33/56E1Y+cv7YwIfwcqWIZTsVZh5w2it9P4hQMyaD9rDAS6+6AbZCZ3bUR2nynmqlaLnFt66L2Lvf6CGNsO1tD/2DeZ+7sKkdXjsNXPwIw6wGNxs9hFKr+U/Cv683/+QQqe7pKpdN/y4VrDDqvQg3VVPELSkbugxh/H U31v2pih fh19YUJtxIhRVaeUNOHJoKubzKidXTENaF6ONHi7j5VXCNvtEKh9/xGe2ls1b0eDS+EJazDsJjORVtcUS/KyTOokogcUe7y2QmMcWR3FrWUs7Ul5lTEphK5tycvbsw6UJPOjvbLAC/1zjr6nZpHmOf7fQAdKmM73bM4rGxqXNzo6tCAe0WBb0EvOmzISHdia3XSMHlQULkiPg3wqOvUz56k2LDREh5vAc7m+c4z13BaqMOiNZNPxhlMebdRI2UmQHJY428IWWDj4m1ZbRJYl9zU3ZwLQCSnabOYtniPNrc2zj6wiBN0azLMTudUVll2A3S1TU3km9swKBgEWs88ykH38R1NeIeM5mq/27kefoODBuHD6K/v26r1UJ/3R5aW8hKz913cWsBnrLFpjvi51hvaBfm4peR+2vJnnMcE99ITqp73YIC8ejRm/PTx3hDGPrJsv14NxM3YXxPNnf7ST+0V8/ckkfqXFfXrcWDPq+qEk0jnU= 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: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438098 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 AFF9BC25B48 for ; Fri, 27 Oct 2023 03:39:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4C4E56B038E; Thu, 26 Oct 2023 23:39:41 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4735D6B038F; Thu, 26 Oct 2023 23:39:41 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2EE2E6B0390; Thu, 26 Oct 2023 23:39:41 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 1BB786B038E for ; Thu, 26 Oct 2023 23:39:41 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id E5578161038 for ; Fri, 27 Oct 2023 03:39:40 +0000 (UTC) X-FDA: 81389836920.24.713D195 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) by imf12.hostedemail.com (Postfix) with ESMTP id 1F4EF40015 for ; Fri, 27 Oct 2023 03:39:38 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CtFoUhOP; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 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=1698377979; 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=c33eXUxcaBLnS1cYMMJhWOrJpLBYqdwLmRTJuXXfNIA=; b=1bjbMJTLN/xBPeYC0gcCWPkUU3GxX8qVOwN9v+5H45iiu+ui1iszIM/FkKHsqe/Qz2J89f 39XGdWw0/lQEOFKaupYJPVF698K4jdpwBg+al9O2pZlaUp7Rt/aJUFJMYPPL6PDE4XC1+g r1jykyRmFS+DU0I9Qkrx/mtJZ6OPVlo= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CtFoUhOP; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377979; a=rsa-sha256; cv=none; b=2nS5lmcOpoJCAYDDREcUcb+mBzPRFT2sgqB4A6C8LuKd9hh2JCRyd4jxwxT9D3KiNug589 AGiKemC18T6OaGbK+woYW9dPm5KUlE8Slba8tZBNBlpCatUMEEPoplejdvXRqnQK6zeEmy CNhHdJRfJ1a4FGCTGmobkJoFN5X2EHg= Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-27d329a704bso1287858a91.0 for ; Thu, 26 Oct 2023 20:39:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377978; x=1698982778; 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=c33eXUxcaBLnS1cYMMJhWOrJpLBYqdwLmRTJuXXfNIA=; b=CtFoUhOPfedf59MOZpJzqHi9CdW6+ndakeDWnnirigsGnmRDGaxelXepDF1WZJwnXO taNHhaHDW0PqBq32TKwB9QmkpqUM2rTyQ6Ue/Rrj5AOOiM222cOMNoyPFo21nP1TDLLx Z+hqIbBF5w/eLj5s8ZLQK+DWj3X7AWlrwRED79zwOHDfyTtiT3fwdoO4pHUlGPDVSoe3 CgHoepdsJutUlmrg32Sgc5JiCBQPWxEGLgjAGNCt+pbgeVi2lxIL2SUYp8d9PrIQDGmW Fy/zgxc8cH7x33AGr71+PE5UKy3etFdj+iHcq6LW1PJ5Wqd6+yx2fMLikBwrlONyt7gj lbKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377978; x=1698982778; 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=c33eXUxcaBLnS1cYMMJhWOrJpLBYqdwLmRTJuXXfNIA=; b=oZt7GeGKl0qnV1Ljmg5t9j/SSX3Ca28a8OdBkS03PenmoQ4lls+WiNcOrrydnNRz3n h3MAoOOm54+P9ci18QkFL6xb2P9fUfJmfBaez4/IZ8jFDMIaeyC49j8oRkiT++ysktgl Qa+3L5/pJrNOY8th4G8jJbJi9QSH/Cgeh1SSN14/s7IFHLKBab/zuoS7G01GNtdqCyz4 Z0F0W4uWp83gLzRoz2Y82iPyANageb6r2vAlyk4UbGf0A1jQFxHEp8eBdhPZoUfUDaQD AFt1QJ4NpLAZcf0ExC+5s72soVpPeK9nam2f7SIL7sPAJa4BK4/JXoxHaDmRzZbJS+wp IyvA== X-Gm-Message-State: AOJu0Yz5XJDpTmqW3JBDmV6v7VKN8juo3iE0unpqtZuBwY8JmHG7WDe1 bi3Pnp8bP44PRkPcC+zAQYE1bw== X-Google-Smtp-Source: AGHT+IHa6xzp6B+Hd6qod6wThw8VgUCQkutV3uFt7t+Mr9ZaRucfgzggvrM+TvB2ROpiG0s6ITCt5A== X-Received: by 2002:a17:90a:5381:b0:27f:fe79:eb6c with SMTP id y1-20020a17090a538100b0027ffe79eb6cmr1351310pjh.29.1698377978039; Thu, 26 Oct 2023 20:39:38 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:37 -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 v7 05/10] maple_tree: Add test for mtree_dup() Date: Fri, 27 Oct 2023 11:38:40 +0800 Message-Id: <20231027033845.90608-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 1F4EF40015 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: y3z3mzxqsg84fzc39es4kquc8wu8w7iq X-HE-Tag: 1698377978-445471 X-HE-Meta: U2FsdGVkX19tS+pNLciiUQN7ygzNJo8PZxXGWvUAlipn9hpkuAlcpcyJgpdz1KB+gnvV3JmVs/Sajx+57mK30ZDtD18bNWZVhZqAlboZeBQh+MFi5ELE0ndGMQ/oXnBMqYSu6iHEcbRAHK5C9AZjTeEAgcFAQmKRlBUs0I9Qbey6aM+m0RNH6T/SikbL0KSpIp06Rb0JzIBKyQ4KHhvMvX/FSLvYgMi/Hac2O32zqw6wHg7bCVNmgixtY2NYUTcHYpGpVZYwcNhkpCVgOviyqANPwU/WZ+55FJJlQyUfxPdJEUz5RnGFNGL2GIlAXIO03EUA2eDFmT2++XH69FiJEA19HPNwH7MSuWDh8n2mZuhDBQHypz4mCjcrKESUW3UXeTIpYV61ay+JIrI8BzEe6nCFUfemKcgo6uHzgpj34oWxRM3iyqCEh7t2cJXI8dYWYWOrsOccdNxXExz8rQsqOGEP29MhCTUHJi3GeYFPUaS5afCS/81XvfCw7VuUfEOw6Q5oUDN+trDIgpP2/cwAmiL47yey/VKbZW+nBHMoqk1D2TeB7t+guYS+mvlfyEI0GqMs1o8BW/a4aJeS0NjsLMlsJ+PwQB8uC8wmRcSbIQsld1V10ldywT0yMxWeaPS+jU/dRsL3xwQozWZBMyMWlO5FikUz/pFHtNpSEpxrX4zSZsDp+pNjuo7ZwwTIo3c+E7kJR8BcqCB5g4g6sM56zTyrhp1p7uud8w8ccjqY8j0DWb0FOu15R7tnzmCwpphrcjJXGdRNIHzywAmV8kGbL8WRyb9F0jbsHtMcQrN7TtfIJcrukKtWpIM9UxrwVYC29F1wBvpFAmoYBtqHB/j00G9TR/JuFLvzWW394N3RfAqGwV2nj76nEjqOSoviBXFFjD6L9owXqrPU9Yh3/IetMNmELPsp0e1c85CEWWVP05NTJiiqOE0OFOdvIG8jvW2zYxyUIC+I4i0qovn1s4M sjPgCQT9 yTi6lpCCoeIsCzONDUqhK/qGtVvQC1k2+/klbiagWdMTv6O+bNLhZI3vC/X2/qKBR++fdXQDaKjIUyiiuZwBiQHfT407Okg2FbE0jyeHqK/sta0e/5ms2ssMmSONcH+9aOmJVWtcPimLoC6OXcyFcc/4p+ngRskGcIHkrwBV/YZcyDoAdB8uhJc71J1joS0RrcqXotKcpfhIdIVLDYaYFhQNgM+1OnkLTiLO5mwRoT1tLzT0dE+MqigKXFU4s56t9sXWF7p6NSvbkzQCN/KVv4xKwTa5dlZc9r3K23HXnSwdThbXej8LIJUQ9MhvWZhqU/GvO2YBJrVFYvXdjzbI1ViKk4ma8QDpcptQHi8jMNUY0uK6Dj3h/wGXfipb4uTH9HftcfEsjI1ZIluo= 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: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438099 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 0E2D6C25B47 for ; Fri, 27 Oct 2023 03:39:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 956876B0390; Thu, 26 Oct 2023 23:39:48 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 906F16B0392; Thu, 26 Oct 2023 23:39:48 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7D9096B0393; Thu, 26 Oct 2023 23:39:48 -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 6CAA36B0390 for ; Thu, 26 Oct 2023 23:39:48 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 49C23160F46 for ; Fri, 27 Oct 2023 03:39:48 +0000 (UTC) X-FDA: 81389837256.05.25E57F1 Received: from mail-pg1-f175.google.com (mail-pg1-f175.google.com [209.85.215.175]) by imf28.hostedemail.com (Postfix) with ESMTP id 7A456C0013 for ; Fri, 27 Oct 2023 03:39:46 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Of0bswXg; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.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=1698377986; 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=74qqxidjqyd9XulDVkugPZl+GB+TldL/DBrAezqtgJY=; b=yiQcMLUgMt674Wdon42r2QFsUklgEM7RPW00RoadjnSA1LLt3c/Iyawm8pR3HcjOKPyvZr AufImFVKam1hH+w0tF6le3SIbTqskmS9f7bV56EZWfdd/56zWwbDo1srThQLRi/u1ERw/1 IdtTv5RU+aOERwnlUC0OStgpj+kreAU= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Of0bswXg; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377986; a=rsa-sha256; cv=none; b=P54SAg3ndUCFAU4/QZhTBopVmrzVzt20gNnbwrp0p0N+92+uKhhsN926bYmt4x0SJM/ZOu jT9MPd4fh+m+dB33ApAq9JrsJQwPwXQSDE0ndgWp5UMdblp+O/Sk0otcIEokWG/2ToCFHK waZKaWdOiCCTc0neapMjijn1sDybY+M= Received: by mail-pg1-f175.google.com with SMTP id 41be03b00d2f7-5b9390d6bd3so578679a12.0 for ; Thu, 26 Oct 2023 20:39:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377985; x=1698982785; 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=74qqxidjqyd9XulDVkugPZl+GB+TldL/DBrAezqtgJY=; b=Of0bswXgBHDRPu7+yMA4IhFURUxANsdogVjX0LM7xw3jKjnZom89EzzmC80oAURtBm frUhax2o6XU12ktjtC+R4ICWaxI/l9fki0aQYmb4ow0inXN0usmz4DfYw5B7GP9CbJaw BbgygLFnaJV4Zz9Ook3NudfELiqZPPe6Ut7tXlz8pSn9Cf+E/KL9jHG0bTG32vawhXEe GTbuF+xnqxuMBydIaEM6jDOsc8FUXNqg+0MGVmGVtRnAU9VbVEM7VNctN6VR4M+whlRp fyk+gBRxtuC9DFY680j2GEPbaIExqWtQQP6vx3QtK6uaoU2WtGehBJTbwa45Jia66znP hNmQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377985; x=1698982785; 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=74qqxidjqyd9XulDVkugPZl+GB+TldL/DBrAezqtgJY=; b=O9FHRCRdITbFr3bwY/regy5tKvhrVvmLG1IeuV9dWNlfl215n5r8fwCTQwFighkyzq teVZIQtywOK+ZUCx2a+NaC4bXQG98CmzqcjNQchvx/rUOvhkLGpNo1D/1acBUzW+SHiM pg7eowQxGG3GdlK70HO6HodH3OB5JSJoTNcgcv2zYCsm6qDHuIIUwvGx77uc7XGFp9E5 rUhA+1UAnYaxrpa/8Z/QuZiZbPqsUXEa9ndCEt/BGxSqR6ymmZOeyrHJd7Ez3/XkGeBk /srRiLUgMpTXffkstlbg12vBNj2xZGg2jd9a7vSL5yPrzOyvIVPl8F2Qs9xyazwQ8MiX dOxg== X-Gm-Message-State: AOJu0YwFaFhaMzWDni03KeABk29zjZALs6Wo8nW5rv2By/UcrJAM1cKC Rw0JLFWlpHuXQlU0lS0gLXYdfA== X-Google-Smtp-Source: AGHT+IE0WBlgixccb7xQyscB6ftmdLDZ7xdSH5V+CyxdwveadRU+NlM0bptvnd1oQV9FJPaGCIUEEQ== X-Received: by 2002:a17:90a:9708:b0:268:808:8e82 with SMTP id x8-20020a17090a970800b0026808088e82mr1969715pjo.1.1698377985415; Thu, 26 Oct 2023 20:39:45 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.38 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:45 -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 v7 06/10] maple_tree: Update the documentation of maple tree Date: Fri, 27 Oct 2023 11:38:41 +0800 Message-Id: <20231027033845.90608-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: 4ufj15axbwj88nww3mpg19ihux1n7wgq X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 7A456C0013 X-HE-Tag: 1698377986-595762 X-HE-Meta: U2FsdGVkX1/WY0atIFzEcTrpKfQV7DSrYryLvY3PGNhKjeD9+h5w3ffsHR2r7bsy2r5Y9/sYk7YBKfV+CclYIhQ4+eG/J5jxjxL/auLIgEBZPUZugmVW4nd0/N8kP3Ij+UZsY5Grv2c2YljvQKvF/ViGWtCM+OtNghNasHBCOsR4G5pNZrGcoirRHnhMkO5ZMbqlx6kqrEk8uUP98mS2YDAtLKAk23LlxVWdMeIFIsoxUzPlV+LJ4j+Pq6w3hASu5afb9qxjIoezojXA3T5NK7x36ZHYvfeYqyPgWPnJ/XPP6KcGgTWh78oRSidYNTiGr6XtH93IymEhOKmdIpjmoEGb7sP/Ya0AuMQ/VhRdfftZ1UTAsD0r2vQZ5d+w51L4+ZZY7F53jhvqB2sLmG3MECo6VCVVR8qwRaEDc9oi918myd+cAgWNNaFPgkpMi5eV491x1eWcAD6OauIe0jg64JGHLXjjDWM1+e7MTKsizg+SKAI2QBapkgqSB9FQA4nBLcLnL6aGlhPPUxB4kcW2gc72rwQbtiGEQxhUdYJY3gjbENJ/aPVdiudj4McxEKcHj6iGcZzVLQCad6CXar8qk3ny/ffc1rDUTszy/mjYVjaFR8cH7g6Jt1nRYLK27r3txBpPXPedN6SzrskZB8YUT1uXV2DTr2uNac8ewEsUniEx+UDFJa8Uir+tPEt1l4/nYYkdmQ83XQhl3B7d7KJ9WTiTPoJX7pGAI5zAm6zzuNL1x7/9YcaMUelS9hxNKyrw5FgXVhcSKk8Y5QpaBYHlemi68UUXNNjGoBuurysEV0XEdWhKxIelwtjrw8WBoC5QxYCUOtOF+tsx71RS3OTBfGyl89xUjGmrReQDBMyDkGir48YDPVWSf6VxMP8ncPJA11xHaq+3ZtpAqmNuD3e3mx9rSI/E30jae+fHSPvOXdu/hxq/Ilqd7NpyPFbszLmBexoKn9ubBG4zUyq6XvO hzng2ejS Oi+xgwuQMeybrM4CH6dGMJDSiQBzgI0uWKM9BZOef0zTKK8oUKRPuEZV4/OHkcCcy9UxVflQMKPj7FsvjJS0+hL2biGkxQimWyGVvCNhKJQyi+LcRd0sFHFD3n+XhwzVAJH1QXPrpUxPe5UyaGAnCTtVBqfJbnIGKDtnjpQwZLS/W4oh2vka8/WSwjDvOoSKUwaQ07FQjP7COWjwD7SG8/Bo5tNAMlVLZ4OEnGvzJv4ditOJGp5Stj3CLXsPJyuxtg+tkVcs3i/wanoLDpUjsOMlTDPzYVZHRK+h7pJI88nNlIaEqWZDbVwRWmsOR9A6D0ZMFpswIA2Q3ydcmpYtvEocp9aNY3ywGlTMLhZGNVNiUPXkaFdGJVIummaisIKQdacl87Q2q3ZA5BzTI7MhlXs8fUinIZPoEpLqD3K5OtVAsvHV40I1fO7xHqUDjYpiVxuAwbUFMjEaRPaKInohv0Uu80nqSMthjECcojIb/O0HL8wI= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000009, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Introduce the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- 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 96f3d5f076b5..ccdd1615cf97 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 Fri Oct 27 03:38:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438100 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 D0DA5C25B47 for ; Fri, 27 Oct 2023 03:39:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 733A46B0393; Thu, 26 Oct 2023 23:39:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6E3FA6B0394; Thu, 26 Oct 2023 23:39:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5AD496B0395; Thu, 26 Oct 2023 23:39:56 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 4CEA06B0393 for ; Thu, 26 Oct 2023 23:39:56 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 1DB48120FFD for ; Fri, 27 Oct 2023 03:39:56 +0000 (UTC) X-FDA: 81389837592.23.A4F002B Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) by imf26.hostedemail.com (Postfix) with ESMTP id 4CA98140004 for ; Fri, 27 Oct 2023 03:39:54 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CgvXwu8A; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 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=1698377994; 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=h5YTmJUCjjpdhuy3lqQAZ858a5z7S5zSCc8pR4j7dSE=; b=yDejT1MLQkGQt96UURxk+6ve2hgmaz+H2Zcv2BQJAPj1aypVircEaVoDY7WCose/MVYHdO vyHRq0RaRrYTdGHfB6biImrqR4rLxVgE05E4RKsuWVEZJ7zugIsDHu1jn7FpkHoQ0kyWtt 8iFOnyhAUMBCatv0U4KEdJbMdyAKa98= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CgvXwu8A; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698377994; a=rsa-sha256; cv=none; b=8GhYg0/Sl4sbCX7lRL1KPN0Cq4XM64itdbTetYmmAopHYPGI24P++9gr0UU+FRETwhuNIJ aUOth/oVwvTIGi27Fh4spRPHLs2WBooK5qwOHyjCkGSPty114Y6ATwrad2tf/1yN61aacu PWnCgOecviu+sLFbKwGk3nNvps6EJyU= Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-27db9fdec0dso1392292a91.0 for ; Thu, 26 Oct 2023 20:39:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377993; x=1698982793; 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=h5YTmJUCjjpdhuy3lqQAZ858a5z7S5zSCc8pR4j7dSE=; b=CgvXwu8AuAQJqWSomBCoOCZoRU5W/Gk7RMq3ThD+5XZ5BkKRJi34cnI8IlTKpoj6Sr x0b91fW+U+3OwRvAF8bgdG5WMrcxhUAQScQjeo6szttDU4I+kUMlTMPrf87jwvJXQiRX x7FqyyHnR1GC+KuIiHoZYVxBAj3pYmaz9gh1ZYRO9K7xSm80UKyMRX/AIDk/lREsGywq WLyOTJyf9j4e29mQvpvuCWWY4APhfElpFePGm7kJ4b9cKyiFtAnUUFhEocLzXN05Bgfh 6qAE3/2IVZipKXTZ9XotM11dBCL24Jnx3xRmzsuwzoZpi+4MgYT8VAMUdv2a9+M8c2q3 J9+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377993; x=1698982793; 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=h5YTmJUCjjpdhuy3lqQAZ858a5z7S5zSCc8pR4j7dSE=; b=PjwMD5jFSiH17vCxIuK6CvKOjdRWc3aAsgQGVbtmkbS5ZvAUHPr78mPeJCA4dfU7Oe XkLLmXsnqI9Z+s80SISz9g+Ozmwa3vC0T7JaKozxns9m9itzAV1RY9WiFEIaQgHwpICM jtsHO9yvdkaPDL8P3fX+oUYIFarmf9D97hfJud84J+ON3HE73HrJzS01Vw1xXYmLt/HE phXqDHJf35gBdHofl8ywfEwDEDe4Mz1nAH2+VyOw0fGYs0FldDDkOom6XPRDGMrDvGU3 KxO756zScY18i7CFow1zkHoAf19n3m/eXZ8ZL1mHVGp2lTRwJZBemJxAzs6lJaXa3URk pzBQ== X-Gm-Message-State: AOJu0Yx49imRfjVhXe6kfxLQ72z6hdPcgczBauNYkpWjUgnhn4M4eT0m CSSEJmMplHLKyhamKaUeWRV4cg== X-Google-Smtp-Source: AGHT+IGP7vALm36zcf78WOHdDsQMZ6gR6l+CE8E8raNCoeG3jAG7u2Ud7OkIO091/2fqWLXD+y+pYw== X-Received: by 2002:a17:90b:1486:b0:27d:e1c:5345 with SMTP id js6-20020a17090b148600b0027d0e1c5345mr1376337pjb.15.1698377993313; Thu, 26 Oct 2023 20:39:53 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.45 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:52 -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 v7 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Fri, 27 Oct 2023 11:38:42 +0800 Message-Id: <20231027033845.90608-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 4CA98140004 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: upid3n7qt79jwpu1w1efbnyu8dq8qqq7 X-HE-Tag: 1698377994-50703 X-HE-Meta: U2FsdGVkX183fuypV8pxiLOq3pkDbvcIht0VvAOme/abtX9+BMGFh/m9pEJuWRvgG3OX4opd7cAEDv7wAXAiQQqzjIlQ6LJTcGht7Yl1CE3zzxZpImHdihmBy7a20pacDZ2E/Vr0pnrsJamEBbvs2AJMRKygr4nQfX62YKo00r8LxKN34KwnOHckymEdX+l8oFXpWD6GJZBNP/+WRYKrs1Y1vfMPL9qtjJ7gRJXxm3oHJ2CxBGoy29KOtblkF1KpSNcOAHCp1LRg2Qjnki8oN/J0fpn3g0n0i8R6k1/4ETSNxMZuzQRL3urFklqC06Wcwcv1xdn9YKQv0fKNvdxRyOTjp+vQEYnB3KtSqo0UtLY+FQx5ZtKj2YPVHvCUupz7As49W8HE2E279ogkwi4eQkMafghPQ4M+cx9Bos4AUvSi+FZegC2O6qDiEedABY0o8Zsog9tBzBwxOJU0PClPzp8/Db1QhbPK850DzHcm0NetnaW9rpXLtKCzTJD7Q2ERQVx7hWMyXNd8P3VK3PPKxpXtp7c7FOiRfRBcwbwvj+mbdmR15QK85+WJ9r6xkB4Dd+AnqcmEhjdRoKBxn2zn4W3iY3EDUvOMQmET1+szoXD/mTsxyKdLnv6d+4uHgDVYjoxmb+airRZEyOZnwsLnapyuN2iq7JaRd0zUyF1L2FL0cIIdRfu9/IH/6L5l1z0zg8Y/ZrpuHqQz4p7dGiCXEVqAjG0t403J9eiqDdxuduNwzE365UVwOnTIyCF3peHzsuGFONpZRENYGhwWYxH6AIs3gir+97N9+B0nVhWrLOYfqrl9DeMiwa7VEGZQzzJOjEgBRr5lm2EyMTjwRTFoEHaE5rziFfK507vs/LrSENGRclK6vAamNaGOQg5Gyy/oKLo/5am0MvQkJtL38UwmpgKKejvMkS+6Q9m1sSVFru8Y8YgIYc1gW2HLn78gXLVtLkiPKbq8PPPdArBwdnN oSqGfBP7 ZCCljfMAFVuX3odjBc3aaoWU5ADmV0X3lDAAAkOESo+NDY/uiNixVddfNMe3B8I6ZQqZtxzU7vUpNStTGdc/VhMlbPXP+bQjdIWNfIZdSzRR2n7nI7BrOkPhD24sdg3LRpU6G6AQn07kcE+mdvom7NfbcdtOkK8+eivm6oCxeM/QZiusuV7Hvdh+N8GIXUL4Ys8SPu4rBC7mztGnDI9m4COc//x3EaaGD2NIaGtdDH6P++9SM/3WiX9xGV6k/M8ja3FQsc8LAemRN8mCCOwAM1Mim2+vobcQArW39jylH3rd0g+WU+xIBlhG8zho7R9ky7i7F6t85CmSiZd62mwAZkbPZdUWWdMM9Lu6OlJZcwf4RS09dM3qR2A3ajRjsv4tSPkAdybbxiL7hP3lxkfeMXKE/u1gJICC0yimY6W7AwUlgYY5tmAJ5ARHbB8ImY8jMLVm6s/aQEmvDzzyY1hcwx8dATaG7cAl5TD/uAw+a7QJ6Xv8= 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: List-Subscribe: List-Unsubscribe: Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438101 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 6C5E1C25B48 for ; Fri, 27 Oct 2023 03:40:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0F24D6B0395; Thu, 26 Oct 2023 23:40:04 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0A3086B0396; Thu, 26 Oct 2023 23:40:04 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E85F46B0397; Thu, 26 Oct 2023 23:40:03 -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 D3F7F6B0395 for ; Thu, 26 Oct 2023 23:40:03 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id AB2E9A0FEE for ; Fri, 27 Oct 2023 03:40:03 +0000 (UTC) X-FDA: 81389837886.14.1712C34 Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf22.hostedemail.com (Postfix) with ESMTP id D4BB5C0005 for ; Fri, 27 Oct 2023 03:40:01 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RJSuLF41; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf22.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=1698378001; 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=x6aKxmDhD/mYQG3DiCaoAvSr06SUW/o1u/OdA/jXWcA=; b=EoCp3lCAaKNBmPLvE7cHNKxp8XNRidmHrv9gXl8aDqy5QmwOvIkqljK5ss86Wu407+X4Go BP9c6Z+vNM2Fm2kt8RKnjmL/U7oez7hTAICM0XV/3d5SaEJCfB2gH96UrwJuvdUGPqDNkV ddEZTd6GcaxnkATsFSv1hr+lQ1Nkq58= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RJSuLF41; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf22.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=1698378001; a=rsa-sha256; cv=none; b=bpRXZcXQcmo4Iw3sJZbS58lX9WVU0ilUn1QRONQy7nCDi9wc5A4BI3c6FKWCI5El3M3YyH gye8DiG+cFdUb10/tUdMfXEhM9gdh+RgeTq8xcMiMwjvb6/08smTTrpgFasdAt8A/ja6jG Zy1gZRkI4F0x1UVbcqKZYCe7MzoKAvk= Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2800bb246ceso232331a91.1 for ; Thu, 26 Oct 2023 20:40:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378001; x=1698982801; 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=x6aKxmDhD/mYQG3DiCaoAvSr06SUW/o1u/OdA/jXWcA=; b=RJSuLF41flqbZ5O+o/KQrLP8MpIZ9/VLv1J4ShhRVu2uUfv3PbOHn0b8ErhF3lehZM J0exXiSakwAqRwTzqmExNbEx8Yo8WXlrzpPPS/OCepeDPnd8py/6wm/3hLZaEel1HBst 9PG3OrnWgDK85vmsgwPQlDVYU6tq1AMfCKlCgRMRkpALMKX0vcVWmnQeAyjnF3BFFwY3 fXGAMpHXIUAZ2L5hYWzw0RPz1YQ4roidcVkN+Rgli6s21n7yzlFkqBnfScQxfrBDIyBx SxIWe+2gMkh2R92B6kH4filJtwRC+7hgkJoPFkgRnRI0/RZ2HX7Bn5hrMfObZHd7UcWt woVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378001; x=1698982801; 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=x6aKxmDhD/mYQG3DiCaoAvSr06SUW/o1u/OdA/jXWcA=; b=VILp5bN8UfRDQSr3aNqP9g5ehvJaVrhAupHLKcTZjx/e9k5rxk8iCGeZmQOLXXlvi8 TLylX2ObzH3U2Z0GqIe2jsYEyM/OJ149ldbAkTZ53ix0KJK4dAxuOxPu0yShl+H1IeeC 7bKhsSFWFAfRPYjc0lQkex5FacZyLGe+EQMqEOZtvs2H97IOZWS7gI6uwMuFhWBTBLM6 H9014LWtFuUVYNjcPVZA35kV51vqRDpKO21PvTNWUdQsVbc6e/sIm7mRtgEsYCdcPKzL /CgRiLIyu4TTnhxrpFCwLPqa9QQ9aNLh3RjBDg9UL6wXj9cQykHQ6oSZzYafQKomk9bd EnOA== X-Gm-Message-State: AOJu0YyC6Nta408mbYS5KmKtb1rJ0zy3leLTYRHfG6xyMf/fX3xPsxSQ CGkxZjCx2s280PXA/pRbhtpTOQ== X-Google-Smtp-Source: AGHT+IH1injlMTgSGoHntNmgiaj1ZHobC4M78EJdUrrHo1lR+rYQIgDSUugUVcu6Xg6S9M0L5Xxffw== X-Received: by 2002:a17:90b:1912:b0:27d:3be:8e13 with SMTP id mp18-20020a17090b191200b0027d03be8e13mr1371267pjb.12.1698378000792; Thu, 26 Oct 2023 20:40:00 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.53 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40:00 -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 v7 08/10] maple_tree: Update check_forking() and bench_forking() Date: Fri, 27 Oct 2023 11:38:43 +0800 Message-Id: <20231027033845.90608-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: D4BB5C0005 X-Stat-Signature: q5bp1po758n5cnzkufc75k4gzkqs8cug X-Rspam-User: X-HE-Tag: 1698378001-777462 X-HE-Meta: U2FsdGVkX1+cVgmzjfzS/pK15w++W3GxzP3Pbu6YOc+lLMhuhhQSo9lMOdmD8Hn3ZKlot0fudY/4gGpdmclmfJ5gnY3qcqNnumN8RbaRTU4fW0guXvVH7EedTz7dMxWXSZg5oznd4HqDgdIFP5Ur1w5sAWXT4oilDF6i8elklPMM33lChDzcGSiuGSPI1ftvsfopZCHthv5wuOAz71v/HMgtfJFFi1t09UhwXz+KN7ttgketRdSqQSsWI3JY/sRkve1dlpJ7Rcvp9pahf91MguRodtmC/gw6zaz59Yfdv6uWuk1CHPhnaE5/r57KRhyGrJBLMYKX6aAnz5Sj4/RzGT8Jwpd8v3hiPEQaooqn7v1KVd2VJx40FW+Jvqle56U9KWvdNFLFPByL+2VM50vNd3QTwgbBhTe+vCaa5TTKSO/c6YOMiZLvoq4tZijdC/oiV3mKcncQfqHddVb6+DPUenqhlky2En5EnY+KFHsVfZiHh4j3Kan5HJydPq0Z4MpKOx0HyplL2EdCOE4T5X4YaBQxTiLGpalpSnTzjMN4UQnvCB3dhKnZZFCegf0IDt9FZZOxhGYNT4Yf1mgoMfkQsnO97HcI7ztpwrUvQLsFGEIIXhdFJ2HQSfzHp2/IoFqoPkkRRRYPhGMABG8BQNeJ4gx+S8MZDNpOn7Aze8/DUzB/KJp0W/UIfL1XrJ8zMSGyLuwODbKx4fXq18PfpXj/Rh9a9g+xmGxyajQM7hzWBK0tFPzXCAqX37pOh3O3lG3Gc9xv+Gg/bVtH4Rh22vR8yeQf77Q1L2lxQ3i7riSbzo6jKFtm7wCzTayvYb7WxX8+0ovkcmVUKsj8pnM8JCx0loBCUFZYUBeVjxNyf3AzU6dBo1sXJOVnQ3xMlHXid+LIPPEVN9CpejgRQZ7iKkgaDE9IETFAtOnHHkKwQcFdZzBeSMwUOhdETH/YbfuvkAb3WjyEC0htX5QxUZU7MWh B38qNl3K 8YwXQU6O7bV4vTwcOYRqPHlaAQstkuq4smwst07vwT+GlHLUEvZqgBJ6xB8mH3D5v4SUJ6xLf+H/oSvV7i4ZDsU3rqQ0Kuc97zYUjV6FzLzscuczR7RgJlMnOAjUXFAfNwE3RHPEifssWQdWUGOEYZVna1lyuvlOs0nGgpwNKedz96+aPVLV2eT5ImLtOXFY8wRoXeV+p0K9IQpuPD5CW7xAfxM6hRfTeruqHCuXgm1fu1I9iXT+G6bbQvUCv8T2th3sG69lFuWmkuGWP+XHMvZdf6kxxp0G4r65/pn3ZE4vNOJT6ohZCM7OI7ejE2k9bjEnOTwt6WihF2QSBR/6nYTyn/hasiFlC4eDRRQtJn2Hvbf8WcJQ7f0TGEIDm3Vwnr3OJj2w+BNSO3DOmQW56U9jfiGlJEL6JYyjN/Ib+06I4W1MSwa/m0gXYzbk8tc5+lVGRLhMGKjXjXy6pF4jdSUaizlpU+3xZ31FOs5XCmf753M8= 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: List-Subscribe: List-Unsubscribe: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- 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 Fri Oct 27 03:38:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438102 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 00B89C25B47 for ; Fri, 27 Oct 2023 03:40:11 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8E3746B0397; Thu, 26 Oct 2023 23:40:11 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 891706B0398; Thu, 26 Oct 2023 23:40:11 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 780F06B0399; Thu, 26 Oct 2023 23:40:11 -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 68ED66B0397 for ; Thu, 26 Oct 2023 23:40:11 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 3E15040F95 for ; Fri, 27 Oct 2023 03:40:11 +0000 (UTC) X-FDA: 81389838222.08.4598CA5 Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) by imf20.hostedemail.com (Postfix) with ESMTP id 6E5961C0005 for ; Fri, 27 Oct 2023 03:40:09 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=FVzhXTmN; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698378009; a=rsa-sha256; cv=none; b=7e8Tav6ZzO7DxSUNnfn4sB8fGYI/Gj7oMWPtbrPeGYTDmE6YPy+irXL7kI2hqbPK5uunGt z3VKt0+RQyPHzZZzi+DRnHeiEJGrUD2hyc19A6gY9DvOaD1L/lmDWxwziOFG74mDzD4ItZ utziw7jBGWwcKWUR9Vzf8gxP0i77z8w= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=FVzhXTmN; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.43 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=1698378009; 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=t/TBSsqo/3PZG//kKjzBxqBhIhs+Qitm7vuazfD4aPI=; b=uL5e9PaO2a4Sl2uS03bU1CJs7NI3P6uR6PvpR9K0rdJV/g2evepazm3PHSOChY9YIHT1Om S08G1LtoebruliWPBllbAoiOr9bSnK+67gZA/i9oSWv0VRX/qv+8FbUfVDSSVtIUvuZPx5 dHipALHqvZblSw/5XaAMfNIl89lx6eI= Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-27dc1e4d8b6so1367986a91.0 for ; Thu, 26 Oct 2023 20:40:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378008; x=1698982808; 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=t/TBSsqo/3PZG//kKjzBxqBhIhs+Qitm7vuazfD4aPI=; b=FVzhXTmNpfK/YafHOxlklyWhwmOdZ8KmVRZ/mrLnDnrLfU3V/YGeFGRhImqQtIFtqq +lKKz/5SOOVExPTLvP0v46wWD04S+eBX8yOsuKDRhPQoO3grLaorNVpsfGVdXL1eQ4C7 kyl/wEUd4xPcPFfAnTfNTofXSxWvvSXCRMVbD3VcpNolbfWTfjfgbCkTo/mLilzRjxbd 3OJZ9Sv2AUEVLyE0OPqgPr4OfKDtas/t3Nec4dKoYjS3tk5LIJ5snDuF2A7tNjNueb0g H0rXV8OAP2LwoO34n+byBIzVXK+nUMmyOe+3Rz8dSd39nYb1wkOWYPv0pOl9GV3Z0Eg6 Zq9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378008; x=1698982808; 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=t/TBSsqo/3PZG//kKjzBxqBhIhs+Qitm7vuazfD4aPI=; b=tumIBhdPM6i+L70FdosqydA5nW+JI5n0yfbHBZPL3qs4jkG+6xltUotZS840LuF/HK mrJFi4nGSo8Yt9W08iefo8u+8o9qpIXIJX3OjFxvJKk4QXgZKQ/vs4CZn28Xzt8yWP/P h3bexXGEKSBQryYofUONEoKn/cFF46G5pRGij0C3T77HGbq46iCt1ZtA9S4d5DW8qcO2 V4e1EAeXxgf5Jlm7LyBUVn+jA4OQrhOAdu1o+DYNkiLHpn/QQGOEm3N24jir3J9nRTxy LooR3+N3Qeo6KdPeX3+SpJAKrIMZXlfR7e3SEO0QVMwDC387EJKGByqkWw0EqL+CnEGc oB8g== X-Gm-Message-State: AOJu0Yza+OErrCZnu0voCOfB2dxugewhAC/+CMqHiajXNvKAK7407wHV bAh/dx6M/mZ6k79hh5KCo/vj+w== X-Google-Smtp-Source: AGHT+IExlg2G7fYOUnFWtBHLrBsW1lyYgFaUWIXf6NstZ6E0c++iEGcYR48s2/F7tPuX752NBLahNg== X-Received: by 2002:a17:90b:18e:b0:27d:2663:c5f4 with SMTP id t14-20020a17090b018e00b0027d2663c5f4mr1538778pjs.47.1698378008501; Thu, 26 Oct 2023 20:40:08 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.40.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40: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 v7 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Fri, 27 Oct 2023 11:38:44 +0800 Message-Id: <20231027033845.90608-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 6E5961C0005 X-Stat-Signature: qp96ixi78h397o3qx3oidpnwkhoowe33 X-Rspam-User: X-HE-Tag: 1698378009-346311 X-HE-Meta: U2FsdGVkX19GAfTQHKZr7px3Lr3HfBAKPxM4191mWGYJAIbiaGHtKPdZ9+pY2ly8IfOuoTa0Kq8aVn+QVPdAttLOr8txirL6R5tY826Wi0Iwpp3G3bijmWjQ8VpjvFuYLyYS/OG7vTrLrnIIN73quXQib3G5uF0I/ju5/hor4a0xFJykzTtFrTkTJv+TM4FRqXzmprjfPdeucleksdVfmSkluFJTjlIOQbj/x+KjMoy3NrGTIfl49CocWsob16YY24geATtxMfUyoUpcbIMCnRxVmL7ekubyjWawivlA8w93SG7Fi8TKuVOXd3TJhopuOnUYXAjv1mpGW4xsplUvvFb5A4LgP9YftYPWZfQLyIop/u+h65W5dwlwrc0cG0H7EMi+v+TEvxEdmolU6B/P7w60IpuZ8jb5GFC+qLqx2jm+ZmcSB3YOGlVWI1SHtGIj+8v4HX2zrXq1T1iM7Hm0FEHZwtyJk7DW/U9akG0DKybjJijXylQe9/qYSPDP/lOKVTjwhLDyG3mH0qdTEiJFDRoIzPtziJPvyEDSHmyGA5VaDHOM1yPpp4gJ0L1nxt522aoQ+2c/DKnYikZ0IwqSfmwsjbqQ6EFOaQ02IQS44i2wOL5Emxxz6ZMZJHRVDjFie1P5B+HqtVr8nb94pBMoazp3gAU3vudT4MVeKqlV8DtOT+iskyYv6y/NS5vM/sVrxXyCfKpDFOSW62Mp0vCViVwRhzbiLQwsUMDmUWzLyvWBNKoeCe+ZVRmtRtNGJumEMfEvu6nvtdDoZom2Sx5ryEmj3wuzcwBUdJ2vXPrzaqu+N2bv9+uG8IkmSUBYI4Y1X3D1NFqF3rA6d1EHAKMGhwjBWkGz1IOx88o15U4EFyjuf2GyLripCgFjhw2f721O4pszthdIWFjzOmloH6pVqn4m/x1Cy9xkJMnuYPDUBPH+spKOe2nq8I13S4UdLNxrVba/T6aLJ7yOg5ACAh6 cbMR4wQh fWBSywicqptxk/oQ7K/2UCXEbBcXQIPW0oA0okysmCPZL3iyUToV+wzLZbaRym+HvT597ihkEoCdqtanHPeIaNr3atjFjMDgyx4cvHefD6cb64pyZ2XBEVFezNuggIxYIn+0lBuQjZtVvulsRUg/aBTKICRFmsVC3rvY0u9ODWD4zJycYY6l7i3q4tcI2mMNhMY/NEeEpJFa+G1X2JbnNtPmRc+u/AW+/2vEgL6hjxn3J4JOcdDp4n0QvZnlJo0ja8bK4cfqP3Y6UYuqsHrNNj6Zj7FAy8CTO3WbreybRzLt1NHzd25NcEq0cMBH4YETsM+wqu0ca9a4qDeuRRQ0wgtHO0Hv/y88cxRHetx9dVUcU5GpP6vXWowEMEOWdNJTwDtrIyBsC94xR5iInXVknVpyLapin8ptv78190rQrvCp9HxEhfYKZz2xLhF7qeTRgi7HUxu3EaGFAlwjcqQy9kCXNJvnwX3fgdeQ/Z+0642in4tM= 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: List-Subscribe: List-Unsubscribe: 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 Reviewed-by: Liam R. Howlett --- 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 718a222cc090..4439469442c7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6763,7 +6763,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 Fri Oct 27 03:38:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13438103 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 BC58DC25B47 for ; Fri, 27 Oct 2023 03:40:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3661B6B0399; Thu, 26 Oct 2023 23:40:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 313996B039A; Thu, 26 Oct 2023 23:40:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1B4D26B039B; Thu, 26 Oct 2023 23:40:19 -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 0ADA26B0399 for ; Thu, 26 Oct 2023 23:40:19 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id DEEA91A0FF7 for ; Fri, 27 Oct 2023 03:40:18 +0000 (UTC) X-FDA: 81389838516.09.F420C5C Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) by imf17.hostedemail.com (Postfix) with ESMTP id 0C85340007 for ; Fri, 27 Oct 2023 03:40:16 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="gjD8HFd/"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.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=1698378017; 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=Ky4w3uAtFSkvxKCreCTuy48cfBYAXj8C3Bu1f6A1ISE=; b=2iXDswc3Ey56BCMPwbnNcBM3T0TigXDenTX8Q5dDiRPsqbEz5s0nzcFwHiSYPN1z85dUNq 7qi65ijRlgoEmCZsz7dd3mzAECwtK0Sfkw8TY/y3GBQ9AcdX6ArY1dmBmSHD7monXAPjvk 4oU484pLV1d/Vs7yxqvisMulabQMWKg= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="gjD8HFd/"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.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=1698378017; a=rsa-sha256; cv=none; b=sux4YBVvnFJySsPD30fUhJ4kMBtJeADHvAod/bEx6voPzFEc66+5DhiH6CDkApMuRiCEN9 dXpCJ2JXxhCZi4DQNiSLjD0pPxA8l1IlDgYr0jExxRlB2eUuxOZwuNMjwLIznend0HKLCv 2EvaNUhahlOZqUJYf7BKABKGFnsk/gc= Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-27d17f5457fso2115861a91.0 for ; Thu, 26 Oct 2023 20:40:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378016; x=1698982816; 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=Ky4w3uAtFSkvxKCreCTuy48cfBYAXj8C3Bu1f6A1ISE=; b=gjD8HFd/3WOtI9QJP3TU+g4B7W5NTroBOuvkcJOWGBo9g14UW1TZxOiUw6L6E3fy4S eVabn8gUqptwMb+qcIyMHqSlvBAHlN/WCPGeGjg2q1ARxLCXaJ1WriJMVekaoxcDldb+ XWVVXOGGFA+q4YvpOQNYhSLOwmVs8G3cv/2eKSzDAUn8p4z1nxXw3wGIbzQA6rYkp0wz Oj+pGqVDSlhuEUu8xsqRh0B/4wLDL7QBGRpe5EY3z7HGxwpDUUp7VPm6AlXMKU3i1hv8 qDU40YDSimSC9m5E04i4joWwZyO42LlqagFWUFGpvm56AwmgMhw1nzW46xMmVkAAJ7ve ueNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378016; x=1698982816; 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=Ky4w3uAtFSkvxKCreCTuy48cfBYAXj8C3Bu1f6A1ISE=; b=LR1OkpBvEUlj8sOunHllGZ+poXcZISdf66YD973W0kpnDRO8OCZqKKZKG6V7cXrlkM BeRQfDWYe2sMm6T7EfmrfGnsk5FeGJ3WfrHumElsSIzkhHcnX0j3vCrJxBdPRiN/a+K2 TZQU+YTbXGhIl+bveQbi6MV1/Kancq8vLL0aRiOif4eBpABRWErPkgqT5GXl5fVmmO+3 TtoYtuH63HBQC/n3s5BN1ZKM5ZsR6HzCmEauguWU62zTCyzXikMbGczu5vEqzuv4taSQ 6hsrvnsU+ZvJupjs9Hqut3m1cH0+N6dLeUu1faYN1xOfLABEcKKfHxGUPHQTMhJ2+xfj /XSg== X-Gm-Message-State: AOJu0YxdMHqI3OZVqfx/zZnji8Om8opDysKFglkMyxasUCfS04DgtJ62 D45cS6PbBMc+iSB/ioqq+ThRLg== X-Google-Smtp-Source: AGHT+IFJRCeA+OUFMxyndHyvFf1XFZD0IulFfw6dGetvqF75UjjqNY1IEWlGGaZ1U8Eieo7P5Fin/w== X-Received: by 2002:a17:90b:1bc6:b0:27d:4935:8d9a with SMTP id oa6-20020a17090b1bc600b0027d49358d9amr5489370pjb.4.1698378015924; Thu, 26 Oct 2023 20:40:15 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.40.08 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40: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 v7 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Fri, 27 Oct 2023 11:38:45 +0800 Message-Id: <20231027033845.90608-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 0C85340007 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 81s9uda4nkwg6rkz41if6qm13gw4bgtr X-HE-Tag: 1698378016-579926 X-HE-Meta: U2FsdGVkX19xcc3iKL6XF+hcCJ0EcpVljhwzt/IdgEha7WjXmiwM+VGOnDhKbX+/E+ANkh+kNjOMTuLcCyScuvTpvJyl4uqTrmERx7vWX/N9smSNQ2qwqj8FIK1tFKanAaBFN4yJAYBdMFuqU0gP0Cxamrm00QRF2XpwYMolF1xDiJukya1B9zWFjRFU2ucqfbeBxAAXkmTfFrM3/WVqUiUu1xPPOJuYiMCS0V0XU2xD5uZgikGuF9C3JGJQ9LRtY+W2W4JUIQXntRQlo4dKsJ7tPSzOHx8x6E0E1LEsnfSD7qAChsLgPvBzOzruvsxA77AtdHweVHd0HW23aKyaM4coIfb719P0jyN7j6xEt/DFb4cfOrQWiWV1727nY3Z3MlSReAvrt8hgaIpW/H0G8MwmvBcG/UP3ngyU5+oRgocSiV44hkRd5fK39kV9CfiL7eIGMFd5UvNOtw6t6wbccHjgZinHkvUvTIiFwDWaLs4AtjpZmlfB7Sukzd4gL2Ny3isk16X9juryMjraq59wPY/GXTR3bcyuhmQ0zVSkeE7kFtpYSfeiv6T8OP+drf4n1Hbjh6MAKe2uLLJ/psgvPNdkCoaJ00GxkATRNv33LWKymSehDhL8HOzeRTNqEqk6q7GiXjVzEMv6bsbEUTP2SJjuXypX3R5uQol9NxHev9jeAcWh+ghG+iNE6bj+97UzzIXVJ1t4eeeTeuloAFeeRwuBWJbUysX9Q//6IMJph8Bqc3Mwnscoautqs7h0S2Hi6fKAhHbeenn1BOAreYwc4EHRox7hrOJvVzBL6w5N3/Rfch+3+KO5sf/9OTWeWe8Q5XPbOqarHFQ2kMDUYg4wFeeLEZx2lgfqdSbaorTfGwQZ1kefI362xrj8OKBTmidzij1R7fmlTjEI/kIDTWIOiM+wKCAIbzJm9NESGUfXFrYeRxM5PTWp7Dl+gJAWsdnM5bPBYDl4514WIAXOdbs xnMl7nKs WLBCoLKZIH/O78fOmeUmpRvslsgPnJrbDwVt96niT6udglpaU6ppv1Nu+ZaL60o4m5rN7ESTaRB76ZBlOp7DA+1UTKMQkSTgj/+YFKIxXJ4aJ/wJ8BdugNMNw8b2ZcROhqB1DY3nMc+3hQKRE0Nky6mohIeB2TOqZaU+cdee1DybCM1a7jfaH2SB6EwtBThd/Ji/mwESM8svISc6ua9h8dZBCqWPAbPgEQXg/xu4geJaLs3W/nSiWaEWYc558928ogjWgFrCApf2kKxxo4JFCM6ocobMJhn4TmzA17Us+/naXeJvgPlaXf6Rb+26uzP724Rv2vMmRQtn4YJjApYhaUDpJDo/gBX/8D/x8QSNfyR7u8aO39Sz1uuk2fEUTk8nJd1TSKy/GcCEsRpkYm2RK4dZPb5c4RkWdHmfi3In1zmDlc6S5dESzwYszwpJEzHZ8bDMupbnQZZTNun+nop7H/KushVwjiXHVCynOHbzW2s2jtMDvPXp1TWdAQiLEexhg0LRIoRW0wIH3Iasc6vmkapipMuseBEqKI5Hs8o/8C1Wx5gs= 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: List-Subscribe: List-Unsubscribe: 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 Suggested-by: Liam R. Howlett Reviewed-by: Liam R. Howlett --- include/linux/mm.h | 11 +++++++++++ kernel/fork.c | 40 +++++++++++++++++++++++++++++----------- mm/internal.h | 11 ----------- mm/memory.c | 7 ++++++- mm/mmap.c | 9 ++++++--- 5 files changed, 52 insertions(+), 26 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 14d5aaff96d0..e9111ec5808c 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -996,6 +996,17 @@ static inline int vma_iter_bulk_alloc(struct vma_iterator *vmi, return mas_expected_entries(&vmi->mas, count); } +static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, + unsigned long start, unsigned long end, gfp_t gfp) +{ + __mas_set_range(&vmi->mas, start, end - 1); + mas_store_gfp(&vmi->mas, NULL, gfp); + if (unlikely(mas_is_err(&vmi->mas))) + return -ENOMEM; + + return 0; +} + /* Free any unused preallocations */ static inline void vma_iter_free(struct vma_iterator *vmi) { diff --git a/kernel/fork.c b/kernel/fork.c index 1e6c656e0857..1552ee66517b 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,22 @@ 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 = vma_iter_clear_gfp(&vmi, mpnt->vm_start, + mpnt->vm_end, GFP_KERNEL); + if (retval) + goto loop_out; + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +754,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. + */ + vma_iter_bulk_store(&vmi, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +767,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 +798,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/internal.h b/mm/internal.h index b61034bd50f5..89a5a794d68f 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -1154,17 +1154,6 @@ static inline void vma_iter_clear(struct vma_iterator *vmi) mas_store_prealloc(&vmi->mas, NULL); } -static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, - unsigned long start, unsigned long end, gfp_t gfp) -{ - __mas_set_range(&vmi->mas, start, end - 1); - mas_store_gfp(&vmi->mas, NULL, gfp); - if (unlikely(mas_is_err(&vmi->mas))) - return -ENOMEM; - - return 0; -} - static inline struct vm_area_struct *vma_iter_load(struct vma_iterator *vmi) { return mas_walk(&vmi->mas); diff --git a/mm/memory.c b/mm/memory.c index 1f18ed4a5497..20cc6e3586e7 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 984804d77ae1..e98e9715afb2 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3300,10 +3300,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(); @@ -3338,11 +3339,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);