From patchwork Mon Oct 9 09:03:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413122 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 39B86E95A91 for ; Mon, 9 Oct 2023 09:03:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AC7FC8D0025; Mon, 9 Oct 2023 05:03:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A776C8D0001; Mon, 9 Oct 2023 05:03:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 919EC8D0025; Mon, 9 Oct 2023 05:03:51 -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 7E6A68D0001 for ; Mon, 9 Oct 2023 05:03:51 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 58E51A00E6 for ; Mon, 9 Oct 2023 09:03:51 +0000 (UTC) X-FDA: 81325335462.04.EB09D67 Received: from mail-oo1-f53.google.com (mail-oo1-f53.google.com [209.85.161.53]) by imf28.hostedemail.com (Postfix) with ESMTP id 80700C0013 for ; Mon, 9 Oct 2023 09:03:49 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=O5tVtdKw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.53 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842229; a=rsa-sha256; cv=none; b=LnujEs9lvvH6Y/Lrxr2JAUlbRIlOqX027yh3R12uDv9fH/tmyDTg3dn2rZbk5R3kqK5JLv Kptco5kwdN869pTsUZUA2NJ26pXn2gvgN6N0pAR7E/zPoDu9bBDCcAe6lt1RtH4RLcaX5W 5ObPbteMmHnBRXCdN2AeVb60xW7+Huc= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=O5tVtdKw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.53 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=1696842229; 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=Vn4VBWQzj5W1GGyecNOIEAPBueVPsjsImBXm9m9YoY4=; b=YVB8M++8sLdg9WAZmzWNCOmT1Ysp9gxk41f9W2ToKPgKfB60Vmsc+W8XfW6RWMMjvJ9GKR xHAjGfJ/0sfyXqrJe6IzrOSBuTKqvI+lZS8aMcOSgShwazYXXk/6q+C7DHA04/Fd5TiNgy MXwVGMsA4g6O9hMvzEDBsFlTy4Vbh6w= Received: by mail-oo1-f53.google.com with SMTP id 006d021491bc7-57b9231e91dso2677962eaf.2 for ; Mon, 09 Oct 2023 02:03:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842228; x=1697447028; 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=Vn4VBWQzj5W1GGyecNOIEAPBueVPsjsImBXm9m9YoY4=; b=O5tVtdKwCDo+0qWvjJOVNhA7F1rSCrW3es8yF3kXKH2UhYRcWfGdoZV1HDEv9730zQ wNdKlxsg+td2TTmNO2IrOtOcVrHB+47GJXNiByjb4ng8m+wbDt4L87/hDTE5GxziZ7ig KGHjWPN9az7ERJRcQWgNndV3jLY2UxEFFx2WfHSvwdkZJ2XP5sIY4SPDVdwomfN/0Hcb jG68AENmN6eACRyuqBmhVWYyAP71UuA8tLImQKIy5SK9FjA7UiCP+4X9+AcFxoXee9Zz UTyJ6tgb8OmKb4o4R2PwBdiSxJtoLO92rsiKZwFv4ytVqWMRJqIGluz+vAXz3WYN8zKw oj+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842228; x=1697447028; 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=Vn4VBWQzj5W1GGyecNOIEAPBueVPsjsImBXm9m9YoY4=; b=CDWEMVbOCP/Z5oQZNs2+wUSOfCys8XNXlVsChmTo+QNXLqZ0QSFeYNywhb6Sq9YwbY dK6vQJNOfqLNwVqv6iKKpIFBx904YMn0/rH/g6YAzkjiM0dExj+5a8maiefqqg9tChbk sCzSK7PjeuS5wHEmgbDBKRfRraFho1XzhUe7kbUvGwWOVV0fFaMJnXaOyR1dJM7dp1fK VLBQ6ZjN49/35MKy/Z5E175xvdmIAvclWDY6paGHUmMF9+iv2eUn3CZn+1IbeDR7E+Bt KYI9kS4fBsDLzoNR9dnK2JI0Bib1gQh3aDChD86j/kSb1dlriXDMI9Za9FbFGATZGku+ RwVQ== X-Gm-Message-State: AOJu0Yx3VOvPXH6UVODFbuaPiAl+rtt3h3gVhOdPxQQEKepVbAvGXxp5 EJdshkJT2rxwgcF0RCuAnCRzIg== X-Google-Smtp-Source: AGHT+IEWY+HaVY8fp64WuczHV3IZD4vZBL6+LkZqahkWHktgA14SlAu5iH/y7MbQI8ixDAn9dfnWUA== X-Received: by 2002:a05:6358:4408:b0:134:c37f:4b64 with SMTP id z8-20020a056358440800b00134c37f4b64mr14018761rwc.30.1696842228498; Mon, 09 Oct 2023 02:03:48 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.03.42 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:03:48 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Mon, 9 Oct 2023 17:03:11 +0800 Message-Id: <20231009090320.64565-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 80700C0013 X-Stat-Signature: 8i145yk33fxdty4c844em9png7aqspcp X-HE-Tag: 1696842229-628229 X-HE-Meta: U2FsdGVkX1+avrlAtrYVJcpelp6RnVNOsWwlpdLNPT9FfR7Q2EMCuzVOVyiJJJ3JqgfFPmr7++VM1wJXpBrQiO57pJB4Up30BZ2LvMZpAwidRCzszWQeEdQ39oDLvqopDKyICJvR1PJ0y5OvKrVbx3fb6q8Q3NHYQ+czvQmZ5jzHM560s8g5S96FMC9qI6qM7Pu0uBReCt6Ij0mRFsHV0ZcP+8NAEKKn57rWg6cOgKU4ICXHvLQ+NTc9PO69fkP9Qg4o0OOexBzZUwh4EfQPM8a+vOauhAdI3vqAivuTj8M2OYRz/ZZAQJfsFEJuYexgfO21f1j8+ziEcOLF505Pq2hZGJreceXDJXxEmdsRaD/paqpE1QQ36Cx+5RZI3SGXqObaLDjgD1ikRC0T2Q+V0efpgz4/mYie815CxItYObWVWxlKzukXCWxO/RSszcnNUGu+JXNUy6rTDo2a77BvPAcyyeD/yjkEUKyRPUWWR7erDQAgSTskQzBkjJYnPH07e1R7aWG7Uw2ucmiOAk4mBWM9+Q7Yn6iyNV/c34nbBNR284iPGG/K7nEgCADDCrN3axycnmBqqlO2CFSyOPG8ev2QdvQXbmByECPgp1YZJsnxgLVS5cScc1hnUvGBWT5vda6WUOFobhu+6V3/72Bg421WaIjEiuz72B3xbxSM+k/oM7TIK7uT92MCQ/3nw0s8nYaEatKbWu9AEw7A3iWbNHtQ1ejNkOYW8GkrA4QDsD9SJ49XXIorNSwZO5ZNCO/Dmk9BQiW3PUFTdM46WFNDhF+PywqLuvcYcz1uaZk1B/0yaeMxnF1LVflTUGjIBPv0ZcdTZGPIih7u6IbK6151uA4kRZp8Dbb90khrxtaXpVzaT2mEAOeWWGjDfqx7mkVS9Y1naQacMzYSEd0ix8H7cq+/q9fB9GmW/mE7KDxAQo6Ba7d3mraZTeZgMBZSlpSIVM/zGoMuKMLvPXvIssg Y8caLhci ztwJiQTQZ9z0KSqrDfGGj3hmCRiWB/pTJDYcnot/ojEqyiC28JnGUXxIL0H8wQHiKFwI/rmi7j/rMHaes/E6JlVRLohncRzVQZQwyPG78X8vqY5sCCrpDw8PepCtr5fVhM/lQiPfbb/K/AxjOXsxkWSr5TfYFz5hjSKiGoOxXdmOkHy/YFlGduHZo2kW/RVouoiMmhjVsfz3BTsj15D2y7wMxxom1YmaVifZ0JYbIu+E2aOgCeMy9XTIxpxNJR29Dtk+ppqLaja6hscu2Au8AgTARaztQWsQjsJdBjATCLUgDwusYU6+Z4lEGMZd8xuRpiCDHz0/vo7QtCAYtSTp8zjeuLkLurbSJhf/FsTeHdu2gJkPT2Rkp/OYJmn8rYIuJMIvJ9MxsAXBMgSg4TjoCkjrxxTVRTq5L6pQCTWBa0ep3/Ad8QbnOTWc/gasfjED404wrEpP9YAuXEGs8H8htyLCVmA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add two helpers: 1. mt_free_one(), used to free a maple node. 2. mt_attr(), used to obtain the attributes of maple tree. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0e00a84e8e8f..28d8959386e7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -165,6 +165,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } +static inline void mt_free_one(struct maple_node *node) +{ + kmem_cache_free(maple_node_cache, node); +} + static inline void mt_free_bulk(size_t size, void __rcu **nodes) { kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); @@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas) return mt_height(mas->tree); } +static inline unsigned int mt_attr(struct maple_tree *mt) +{ + return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; +} + static inline enum maple_type mte_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & @@ -5573,7 +5583,7 @@ void mas_destroy(struct ma_state *mas) mt_free_bulk(count, (void __rcu **)&node->slot[1]); total -= count; } - kmem_cache_free(maple_node_cache, node); + mt_free_one(ma_mnode_ptr(node)); total--; } From patchwork Mon Oct 9 09:03:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413123 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 3A055E95A91 for ; Mon, 9 Oct 2023 09:03:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CEABF8D0026; Mon, 9 Oct 2023 05:03:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C9AAD8D0001; Mon, 9 Oct 2023 05:03:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B62878D0026; Mon, 9 Oct 2023 05:03:58 -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 A3FAF8D0001 for ; Mon, 9 Oct 2023 05:03:58 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 8402F16019B for ; Mon, 9 Oct 2023 09:03:58 +0000 (UTC) X-FDA: 81325335756.06.A2994A7 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf07.hostedemail.com (Postfix) with ESMTP id B0ED640008 for ; Mon, 9 Oct 2023 09:03:56 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=MP13Rg63; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1696842236; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=dsz3xjLwKM4S2X2XJskd5g4lXkzE6pgJFjNp2oJrr/yoqgTxniOaeNVchl9Vj5gz3hysXC dS2SJbk6kLWq6PcN3UM4sDo11dIJkSp/xN/53JJTTP08xpURN+Pu3Zvw0iPWxwLq24zFsL 5ojD3q05qzlpQHG6WPdSV5rqNjRfnnM= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=MP13Rg63; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842236; a=rsa-sha256; cv=none; b=bVJyfRdrHAK8MrSMCBoaPt1SVWbwJA7PCZ38SY+A4r/5ibq+TFRUL6UCAWmtvVNp8AtY7I 3MokDzuGKRRoBGyuKNUJ0ElnUwVe8gC9+W9H9JLJtz5CTXmF1D0seJlTeFikt3xwxXsu/Y Hazrg+2CPLmcbXrxuRdG3pN/wlacw5U= Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-693375d2028so3845972b3a.2 for ; Mon, 09 Oct 2023 02:03:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842235; x=1697447035; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=MP13Rg63y69ZViNt+AAUbSEz0FHYNUJ+anu2qXzv1RwlMy6Dx537TDzy35+x81YHA+ 8WbSgTGFPTeD1a4xIyAfy7XWnc3zKy8nVYgWo1bI4oyRrR0mKFehOIsgWR4DpFr6FULc x4Q+TGF/XM1MV6v6k017XGhaf72WA9ubMH3TeS9rASnbQj2PJ5dg5A8knvfUsP0r5GvN IZu7IDjduX3h5+SjWPvcbchBarQ2tdl7N3T0GePG9uq397gMZSJN2o3mGT8nw/VMYG8R rF6vMgJx7cIVoBzi6lJUXNM741vBTdbnKzDrb+nk4Ysf5hhuOkzOLJ2jrQdA2lv6i88B vIPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842235; x=1697447035; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=MxVNAI1gXkzu6z+nXkyv4mRsdS6P1lh+DbMke+ePgWOQQy/FXJOHwMzPxcBquWXO5b Lywj+IfF1CT1eicxXBFeQ6Wb/xUcLZynrXIyEEIwoSC9V3KWxf3JMKYu/ufQj8/yfEz7 dofMRtqS7H9vSNQO3f/l2Ry9flwkSfqoDurnH37h061bqSkG1QbhAqcYI8hX1O/F3Qny w/Y39i+7Peggz9DiUbW3e45QaEtqOgfNV9SJtPbsECjNsvxRs/ccey25zHhe2zn3uiUy f+pwqTkUaE2x+Upmqww/2ESISqohhhhtYinWm3Da6c6dzW8y9GjiE7nZSuYCjRNqvqPV JXpA== X-Gm-Message-State: AOJu0YyNMsXXfEgu/y1l4myZP3BJj/W9VMXQU52DwWKcVUUdXVu1KvT+ aGXHRABLy3rjjxCkkSBbLRaYXw== X-Google-Smtp-Source: AGHT+IFTziVEGjqko/GY6Y/gf0kzFA12JYrUPiEPy+KRrwJBQ6QE4OFwPoL+CRZrpwt2i9F5PSccSA== X-Received: by 2002:a05:6a00:1255:b0:68a:5449:7436 with SMTP id u21-20020a056a00125500b0068a54497436mr16185349pfi.32.1696842235402; Mon, 09 Oct 2023 02:03:55 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.03.48 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:03:54 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Mon, 9 Oct 2023 17:03:12 +0800 Message-Id: <20231009090320.64565-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: B0ED640008 X-Stat-Signature: qzbptqays87ysoetogzsjou6ykxsp5zt X-Rspam-User: X-HE-Tag: 1696842236-753680 X-HE-Meta: U2FsdGVkX1/H5HPezEj8/yK8kkU4gSm3ExrArt7k1svv/LNE4zjCr19cGIR/AmMugrrztMSO2G5pnFpt+80yQK+u/UPK+uSVRqr/qpnbXaVM6hbS4HkOIm45O9/qIglcT3oSXo5fi9z9B9BURCrdtkLu663tGA+8SuEZndIZ91RKzUodtS5MLVdCfsS7pTh/F/Y79BlA/RU7dIgxm4gRdLW36lOXUk3NA2ZapzQ1jZwpp3CWlgTHnquFf3VPTXk07uDsjYqPmNoCMAQ2kTMk7lGhgCT7bz0+Q7Z7pbZS6pPY87gz/CPe5ZpGNfMpTSBKKpt6gBq9FKMFbib6h/w99sfbUcQM38H2DOVKJl4SfIfj8cexg73LEowuE2pi3/+XyhXTIDGT1V1Dk+FFGszj02hwiVg0r3G8ldU4G1vqvuRdjJfTJY9m+ji2ktQuAgAc6QYfvajkkEOltfjzRiuVnzsSzcxyAh5izeuEmIUrQElNJNKXcrZlrOjoKbt478AdOIvro6srVobKjbYkw785LiSIPPLfKt/8N9kLGGo6sAcfL19G6qd9KSPmYoOhBmsMZD869wlv34k7glFpSiCvAxOjI7Y/feHuSLNvuXby+RDyj/kpFuom8t0nNbrAtEdu5dK1/16rSfMfuY7cBRaTjLQ22oa1MiXDqzFt4EMNbg5ERBUB2wNXnJZSI+wA8R0QUQIjuXtBeQEWDC56DhAtTQKfmNMiS7Qx+QUtOgC0dwFujup9UdHS3ZuAT+3Ko6HUoZKOdiqVfSAnWK8uaphtjaDPjaZcVQNRJs3J9YEa/MhJT/U/invdOgt2KqFP3PGyRuPobY61t+Beg1Xe6S93dgzBnA6ZAJ0OzXA39OqIAjdv1QRI4EKuhu1Rl0DQJjsOft5vItHuc4B4OXW8zsVIaw4qKngLPUBvc3h1Vlsbl6CND8g2E/ufCkbotudD88UjKMqmg1a+qvMTZlxdBYB 9SMObeLO C2nTlXdN3HhDXXBwAKv2ifDqdgPTI26at192C5hdLp4yD0As8P1ZD60gh4P+Mlf68I8TXhyDz3PcfSEO98+Pc1Pl9kc0Pt/TpIWGDGGs/9mMAT2IPLBtD4nxUiUMhv6p8C+4LTe1CgrqHpc9jwWU5tdBQdEMyM7xAo+5PXp11KEIK0oNqZ4qu3cNsDMbiC1ycxUVJlsPcoRwDh/CwOf04x1X0yus7eEhq6eeduMstn924NU2eKa4XBCSJB1WgmC/bqUc3Ov1DyiAW/678BnOEW7RySiBXKSXebhncs/Cc7sXpVhFgHzQXsnYe83rzccncd6ZTdVs4bl9wTz8TPhy8PsbmyWESoKlPn4X0uraUbQl4tXX737888YQx9fcFx9RphgeZ/GbKLV1z4ELBrM0HNQfarj+fPLlyMb8x/n2DOKGdEGTK2rUlyVHimW1L3VbMmMrujbwFeMLLKkQRwGyLAEdOyQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000116, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is introduced. For example, when duplicating maple tree, we need to hold the locks of two trees, in which case nested locks are needed. At the same time, add the definition of spin_lock_nested() in tools for testing. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 4 ++++ tools/include/linux/spinlock.h | 1 + 2 files changed, 5 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d01e850b570f..f91dbc7fe091 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -256,6 +256,8 @@ struct maple_tree { struct maple_tree name = MTREE_INIT(name, 0) #define mtree_lock(mt) spin_lock((&(mt)->ma_lock)) +#define mtree_lock_nested(mas, subclass) \ + spin_lock_nested((&(mt)->ma_lock), subclass) #define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock)) /* @@ -406,6 +408,8 @@ struct ma_wr_state { }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_lock_nested(mas, subclass) \ + spin_lock_nested(&((mas)->tree->ma_lock), subclass) #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h index 622266b197d0..a6cdf25b6b9d 100644 --- a/tools/include/linux/spinlock.h +++ b/tools/include/linux/spinlock.h @@ -11,6 +11,7 @@ #define spin_lock_init(x) pthread_mutex_init(x, NULL) #define spin_lock(x) pthread_mutex_lock(x) +#define spin_lock_nested(x, subclass) pthread_mutex_lock(x) #define spin_unlock(x) pthread_mutex_unlock(x) #define spin_lock_bh(x) pthread_mutex_lock(x) #define spin_unlock_bh(x) pthread_mutex_unlock(x) From patchwork Mon Oct 9 09:03:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413124 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 4DD21E95A91 for ; Mon, 9 Oct 2023 09:04:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DD5CB8D0029; Mon, 9 Oct 2023 05:04:05 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D852A8D0001; Mon, 9 Oct 2023 05:04:05 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C25DF8D0029; Mon, 9 Oct 2023 05:04:05 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id AEB8C8D0001 for ; Mon, 9 Oct 2023 05:04:05 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 8DFFA1A0002 for ; Mon, 9 Oct 2023 09:04:05 +0000 (UTC) X-FDA: 81325336050.21.A7D6924 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf27.hostedemail.com (Postfix) with ESMTP id 9EF004002B for ; Mon, 9 Oct 2023 09:04:03 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RELYnDGJ; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 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=1696842243; a=rsa-sha256; cv=none; b=zx8FUdNdY4PBbj8UsI2Jv44sj3jQiD6LJVYisTfKlTdoCW15Q65NBbeF+zbnOVpBpNU2EG qkxaqyaiumf5kg3GUh6uWExwZvsjFlT22FrGh1VCl793l6gCWtj6FWoiNWlcVrBxoB+bPL ot+fYngp0mpxjihBK+6GYmQmSe5eVrQ= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RELYnDGJ; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1696842243; 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=rFybNnWQdSCKln+hJq4fbSMz/Y70Fetb8e2rQd0Bxg4=; b=6YIiyiDc8sbKR+BaOOFnX/FQN3egC0XNSRVL1Joy2YUx42X4Z+iCdBoe5/XPVUn+OFgYrQ U0iE0OxNspwjlRHJYX/YK3eEKMORlBFKkjAqY0mt+Pm22W+1UI3pl/v+syhozjYzsv26Zo Iq01LKeiNPODpT+7GivilX1QeYLOovk= Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-690bd59322dso3072075b3a.3 for ; Mon, 09 Oct 2023 02:04:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842242; x=1697447042; 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=rFybNnWQdSCKln+hJq4fbSMz/Y70Fetb8e2rQd0Bxg4=; b=RELYnDGJCtzElIOd3hwMwvvB8egFuosOJe2RTxC5r45xAh4jv7Q0q5riFFacgJFO8s ADrn4k58kCuUZdXn4vHx05NPtnGvSMEhSgGC7qNINzWUKU5lnH6a9xj3isJ1hFwhS9Rp KEdu5UA3Bx0B9Xc1x0cO+3y7xIyxxugOYKZrmzV9IUT70bR24kHikOgN8c+u1ir1i4b/ 1tAvLHDuknf9BAHOJwziUIxi4MfxADVqCF96/JGq2xTLIje6a8bocftV32vSzkZVeN9J twbbC/UFEPz7YH8FixVv8Y/MNKjholkIyPMlP+PUtjpk1VcZlPDZdSQq+Ekx47bCFsBR 3rGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842242; x=1697447042; 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=rFybNnWQdSCKln+hJq4fbSMz/Y70Fetb8e2rQd0Bxg4=; b=a+PvWmgX8AF8WV51w+Ft7YOGKpIitJGhAsvM/uTBZbBEq0eCku1DNn55lsKcTa640u Rm/ZV45jxJAH8WZcOpOTvQY0YJ8rAV5O8lInfwDMoOw9cqFbyZsHCD4FnINQKdL0qzkk dnozUfsnbAgyidPwIUzLDbT4wgPIT1UDipB8g9OLv2c2tu7L8/ln+7BJYtQ06hK3NmP6 MQ4fr/CTjTgOyqX20mpTiL+8W9FdGcp1ekJNbMghnA7X9zK45wFwV2d5HMlt1ajDfEJe TYLsIAfe0ENBfud9ZvhlNAzDYe2D16aLPxHnhG4jHWAdFVuXRmiVk1QM3+f41wwS60Zd ok6A== X-Gm-Message-State: AOJu0Yy1+BdiXpJSBXHYrQdeqWxFQ6zeKHVlJdl179UdIkrjCl6JkaBH XeWqcLYOeYGpZQYbQ4E4StXVHA== X-Google-Smtp-Source: AGHT+IGW2yzeIoL6Ijf2WG+uM4T/YOjJkHs9DS92BATvDQd3QNrHABPOnV3/n3Q1RgtwoWVo3K2adw== X-Received: by 2002:a05:6a21:a5aa:b0:15d:fc71:1b9e with SMTP id gd42-20020a056a21a5aa00b0015dfc711b9emr17661321pzc.49.1696842242202; Mon, 09 Oct 2023 02:04:02 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.03.55 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04:02 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Mon, 9 Oct 2023 17:03:13 +0800 Message-Id: <20231009090320.64565-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 9EF004002B X-Stat-Signature: dmwhmokn1k6jt36pot8wb7chd6rft8oj X-Rspam-User: X-HE-Tag: 1696842243-769102 X-HE-Meta: U2FsdGVkX18/nKu/2zUzkkl3JkSxjZJikr3QigxJXue1Exgk5WHignu4TK40kyacWAukyWruo4QvyRps67VUB9L1ocSi/L0leAbKfW55vYlGPJw0E/26C8gvZnaki8j2/kqxciE2Z2HnSFOIuAP9bvgvgkk3KblPYCLB0YUAz447X2ycWVKjJa2M4ul0w55kSvHGnozOixm/tn4PqeJ4I4X3OIfeEMhHjdr6O58+6wiTlunkoR2zoBn8/LrnKu75usKBmrY3gdhoFkKbwvePOYQYCrOHMqsApJyXytjsI5w9iUlOZzX4vcpqtdQxr7Uaq8jGKyDJ9oqKXmrQ0TMsRi1JwfdN/QA69qvap2+b3KOK750+vGa7edbYlZckaXb3jpsj1HrE0ukrE/YNdVGaa1JOtNZ9COkYfIt2OIJi7x301vRm1jAZ9WP7L/Ly0fxqjBriUay7jLI8WUO6kvRauR3PNnHNr0AMMJnfkQvsp/EnH//5BVy/+G0VvDzaN0KSekaXrs42i6cA8Quhpqf85cZvLPlrXlBawkWvhIRd8XS1d4A3v8DXeY6DnvWwm5YqhUFaESE1/OlEVt1EVkzY4ILUxX/TliLhXg/XcaV0s/qTjV975R7LV2JspWzLyI1kkkiEXHxL3LE6qHbo5Pu0PHQ4qUqwrIfGBEFQkHB40LiIGK5TEVs5WtVKC77gYmwgf55VckYz6qf211UUsD9RzMusHGXyrSE4AFbhopEZOK9Wm65O8lYaP7Rml8wvtBHmf9eJfrKVGY1eKyzPiGRedS5t3U/3ZqM88aoI3oSCsFhc8sPhQ1zQMb6o+nf0IBDHg7EaKx630JUiQ7h9ApccXK7junclMxkSzNVHPP9DSCiwgzE/WijOqWNudsm/u8S9+I6Ef+6flTchFNlASROTSH+lWmyq+sL4qW3Tvnbde87lriGGBdEd+yjW70QVyje5LEMjV70Mevp/P5l8t76 zIGvpWth vupGra6W/Zsx//epZmZEGxeaKXbOtWFHgsOYqXZbvz0bYp0Tp6MZZkLIOjah1Kw87/fkJ1Btp1JDq0Rk55KfAG6ptNrzXimHwodQpDEATUrMLCamK0rwtKwtqkO6hkM+7HTymw8P6RQ5Z/dkqOPBmkA1W44Eek2fil92frsgNDbT7p4o8Tvn8fd+8dvIIR/d0E+TYGKmZwqxPLoys/It4PYO8DGyOJB1OcomAAJjqg8hnqN5m44+BBYmoxLvPLEbb2zk4wrGOZSg8DXfZsD8IPgJcdTKazuE35dhNXXDMX5nYbK5LSr5y+KYWhNECAsSvDEKE0Eczh6KK/v23zxPOe8u7FHVkVXN7uZRe5zDyz4KfOvHlgX4kyWEdDg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Introduce interfaces __mt_dup() and mtree_dup(), which are used to duplicate a maple tree. They duplicate a maple tree in Depth-First Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the source tree and allocate new child nodes in non-leaf nodes. The new node is exactly the same as the source node except for all the addresses stored in it. It will be faster than traversing all elements in the source tree and inserting them one by one into the new tree. The time complexity of these two functions is O(n). The difference between __mt_dup() and mtree_dup() is that mtree_dup() handles locks internally. Analysis of the average time complexity of this algorithm: For simplicity, let's assume that the maximum branching factor of all non-leaf nodes is 16 (in allocation mode, it is 10), and the tree is a full tree. Under the given conditions, if there is a maple tree with n elements, the number of its leaves is n/16. From bottom to top, the number of nodes in each level is 1/16 of the number of nodes in the level below. So the total number of nodes in the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1. This is a geometric series, and it has log(n) terms with base 16. According to the formula for the sum of a geometric series, the sum of this series can be calculated as (n-1)/15. Each node has only one parent node pointer, which can be considered as an edge. In total, there are (n-1)/15-1 edges. This algorithm consists of two operations: 1. Traversing all nodes in DFS order. 2. For each node, making a copy and performing necessary modifications to create a new node. For the first part, DFS traversal will visit each edge twice. Let T(ascend) represent the cost of taking one step downwards, and T(descend) represent the cost of taking one step upwards. And both of them are constants (although mas_ascend() may not be, as it contains a loop, but here we ignore it and treat it as a constant). So the time spent on the first part can be represented as ((n-1)/15-1) * (T(ascend) + T(descend)). For the second part, each node will be copied, and the cost of copying a node is denoted as T(copy_node). For each non-leaf node, it is necessary to reallocate all child nodes, and the cost of this operation is denoted as T(dup_alloc). The behavior behind memory allocation is complex and not specific to the maple tree operation. Here, we assume that the time required for a single allocation is constant. Since the size of a node is fixed, both of these symbols are also constants. We can calculate that the time spent on the second part is ((n-1)/15) * T(copy_node) + ((n-1)/15 - n/16) * T(dup_alloc). Adding both parts together, the total time spent by the algorithm can be represented as: ((n-1)/15) * (T(ascend) + T(descend) + T(copy_node) + T(dup_alloc)) - n/16 * T(dup_alloc) - (T(ascend) + T(descend)) Let C1 = T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) Let C2 = T(dup_alloc) Let C3 = T(ascend) + T(descend) Finally, the expression can be simplified as: ((16 * C1 - 15 * C2) / (15 * 16)) * n - (C1 / 15 + C3). This is a linear function, so the average time complexity is O(n). Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++ 2 files changed, 289 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 28d8959386e7..d5544382ff15 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6475,6 +6475,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mas_dup_free() - Free an incomplete duplication of a tree. + * @mas: The maple state of a incomplete tree. + * + * The parameter @mas->node passed in indicates that the allocation failed on + * this node. This function frees all nodes starting from @mas->node in the + * reverse order of mas_dup_build(). There is no need to hold the source tree + * lock at this time. + */ +static void mas_dup_free(struct ma_state *mas) +{ + struct maple_node *node; + enum maple_type type; + void __rcu **slots; + unsigned char count, i; + + /* Maybe the first node allocation failed. */ + if (mas_is_none(mas)) + return; + + while (!mte_is_root(mas->node)) { + mas_ascend(mas); + + if (mas->offset) { + mas->offset--; + do { + mas_descend(mas); + mas->offset = mas_data_end(mas); + } while (!mte_is_leaf(mas->node)); + + mas_ascend(mas); + } + + node = mte_to_node(mas->node); + type = mte_node_type(mas->node); + slots = ma_slots(node, type); + count = mas_data_end(mas) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + + mt_free_bulk(count, slots); + } + + node = mte_to_node(mas->node); + mt_free_one(node); +} + +/* + * mas_copy_node() - Copy a maple node and replace the parent. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @parent: The parent of the new node. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, + struct maple_pnode *parent) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + unsigned long val; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + + /* Update the parent node pointer. */ + val = (unsigned long)node->parent & MAPLE_NODE_MASK; + new_node->parent = ma_parent_ptr(val | (unsigned long)parent); +} + +/* + * mas_dup_alloc() - Allocate child nodes for a maple node. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function allocates child nodes for @new_mas->node during the duplication + * process. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + enum maple_type type; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + unsigned long val; + + /* Allocate memory for child nodes. */ + type = mte_node_type(mas->node); + new_slots = ma_slots(new_node, type); + request = mas_data_end(mas) + 1; + count = mt_alloc_bulk(gfp, request, (void **)new_slots); + if (unlikely(count < request)) { + if (count) + mt_free_bulk(count, new_slots); + + memset(new_slots, 0, request * sizeof(void *)); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots = ma_slots(node, type); + for (i = 0; i < count; i++) { + val = (unsigned long)mt_slot_locked(mas->tree, slots, i); + val &= MAPLE_NODE_MASK; + ((unsigned long *)new_slots)[i] |= val; + } +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree, need to be in MAS_START state. + * @new_mas: The maple state of new tree, need to be in MAS_START state. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function builds a new tree in DFS preorder. If the memory allocation + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the + * last node. mas_dup_free() will free the incomplete duplication of a tree. + * + * Note that the attributes of the two trees need to be exactly the same, and the + * new tree needs to be empty, otherwise -EINVAL will be set in @mas. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node; + struct maple_pnode *parent = NULL; + struct maple_enode *root; + enum maple_type type; + + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || + unlikely(!mtree_empty(new_mas->tree))) { + mas_set_err(mas, -EINVAL); + return; + } + + mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) { + root = mt_root_locked(mas->tree); + goto set_new_tree; + } + + node = mt_alloc_one(gfp); + if (!node) { + new_mas->node = MAS_NONE; + mas_set_err(mas, -ENOMEM); + return; + } + + type = mte_node_type(mas->node); + root = mt_mk_node(node, type); + new_mas->node = root; + new_mas->min = 0; + new_mas->max = ULONG_MAX; + root = mte_mk_root(root); + + while (1) { + mas_copy_node(mas, new_mas, parent); + + if (!mte_is_leaf(mas->node)) { + /* Only allocate child nodes for non-leaf nodes. */ + mas_dup_alloc(mas, new_mas, gfp); + if (unlikely(mas_is_err(mas))) + return; + } else { + /* + * This is the last leaf node and duplication is + * completed. + */ + if (mas->max == ULONG_MAX) + goto done; + + /* This is not the last leaf node and needs to go up. */ + do { + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset == mas_data_end(mas)); + + /* Move to the next subtree. */ + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent = ma_parent_ptr(mte_to_node(new_mas->node)); + mas_descend(new_mas); + mas->offset = 0; + new_mas->offset = 0; + } +done: + /* Specially handle the parent of the root node. */ + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas)); +set_new_tree: + /* Make them the same height */ + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, root); +} + +/** + * __mt_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcopy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * Note that the user needs to manually lock the source tree and the new tree. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_dup_build(&mas, &new_mas, gfp); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mtree_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcopy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_lock(&new_mas); + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + + mas_dup_build(&mas, &new_mas, gfp); + mas_unlock(&mas); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + mas_unlock(&new_mas); + + return ret; +} +EXPORT_SYMBOL(mtree_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree From patchwork Mon Oct 9 09:03:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413125 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 CCD00E95A8E for ; Mon, 9 Oct 2023 09:04:12 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 635068D002A; Mon, 9 Oct 2023 05:04:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5E41C8D0001; Mon, 9 Oct 2023 05:04:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4862D8D002A; Mon, 9 Oct 2023 05:04:12 -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 3571D8D0001 for ; Mon, 9 Oct 2023 05:04:12 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 06F9C160170 for ; Mon, 9 Oct 2023 09:04:12 +0000 (UTC) X-FDA: 81325336344.13.18BC7CC Received: from mail-oa1-f44.google.com (mail-oa1-f44.google.com [209.85.160.44]) by imf15.hostedemail.com (Postfix) with ESMTP id 35FEFA002F for ; Mon, 9 Oct 2023 09:04:10 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZnbcaTuB; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.44 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=1696842250; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=13v6CdAEIF4KjrFYvyEpYEdaHuHpreJiUYI2AdJtBE2FuLdoRGdpObcBtKyNOBFQdMo+EC aamcTs2Vu0b0vIOpsvTv9tdwm3CrMz+fBgGyK3pfpEtlZJskSPu/52h9+0dF8wTlvgxwTd HNFamC6LAFHGtG3K5GjUK1xpLaI66z4= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842250; a=rsa-sha256; cv=none; b=TbbaSXTzMFvse0w2s+qH2I1OK690vxIfbWNtth7etGY5Lb/hn6/L88NJhI6CCExDZQF6Dw Up5NfrWTYCM3xvQ5fJXAkONStM8tiGA6/jsYOXvUrYLPadN76IfwHBiyAMRjusZb35RPEH VYKbSgK0IVxBwrVYZlBop4YvEBH2FxE= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZnbcaTuB; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-oa1-f44.google.com with SMTP id 586e51a60fabf-1e562706d29so2459950fac.2 for ; Mon, 09 Oct 2023 02:04:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842249; x=1697447049; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=ZnbcaTuBXglv6Ox6WzyUzapYPoDcvNTOAWc4G9zuS0DN4dhS62Vetw32CwtnXR+dp3 6DEIblhTCXnQ/9eTjvHxDNlMp1GaHyXJSDwPJVQ2GOgzs2JZSDgx9xIEL9jXdSr301xG 1ikz5/L41dcbjQXxyPv642dvDdHO4I5cGe9P6uqIFofrf8GUbDXDtyI0LhCEN4tVha7n 6/eVp3d5kzPTXV5BTt3H14JdTYSNQMq5BVW7C+rGTthC95yFH/tu+En6sFyhfj/ujyZ4 6GSGTiMsR6HhzBOnkEZHYlMcLKwKSIieHccyt89/Wlw1l+48xHAAkd3vuEA6biiQqBOi NQwQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842249; x=1697447049; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=VKsg2uSzsMg9C8V08+H+pshX7zLvL7c3OcrS4ZVBuOvgNH2a3GEli/v4oWusJK+zQ+ CzCWaIIeFLT2m5unmFIFVhFjw2m7zQbXWgczJyDwS3FyhC9tWjwFHQWGysod/jzVKj1D BfONOUC5HJ7XwExU0YI4duHk4YoMK90UwZXFKbuf4fjHYGTR+8jeYfxsxUJLqESOfLdl bnrd9j3yUfyW4VRvTm1llDMndQMFBhiEV2g+fChpNvLBsy6hOzp1Kgjz4t52+vP/+LIY E5QpEPw5I9caR4LkmZ1HGNVaUyA7reKDO+baLP82SYL28pGiaBbwKlsAZvow9NGes8vg 6GQA== X-Gm-Message-State: AOJu0YxEZvloFPJ2OwtmdLpfguig+2K+zdde7ZXjRPkA4XU1THaGfsuq hqNGfWCc0/IkZt2zL1c+dbSSVA== X-Google-Smtp-Source: AGHT+IHn4oU8w8VyA+/fsyHj61zhR6VGnu4RwZZtoM9wLO0d06HTYfGfAoM8qObwlt0rsYXB73IVJg== X-Received: by 2002:a05:6870:b618:b0:1c8:d72a:d6ba with SMTP id cm24-20020a056870b61800b001c8d72ad6bamr17273488oab.45.1696842248950; Mon, 09 Oct 2023 02:04:08 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.02 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04: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 v4 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Mon, 9 Oct 2023 17:03:14 +0800 Message-Id: <20231009090320.64565-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 35FEFA002F X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: 9sw1u5qrdshcgrod39d1p4ystdswy9gf X-HE-Tag: 1696842250-654802 X-HE-Meta: U2FsdGVkX18W8mFLtROvouEI3KxAAXTDhXCZcxe7NxJUIWS2clOBon89Y8fV5uyIMHCD68BIcNcpGEvizyvOa78kEigHPHJqjbn1T3Nkgn9JWajbpHXTsC01f2TOpnp7ClvZMMvbuvOtqqU695pHhIKe3QW0Wwlyl3wDszISywnJndq1KbXhoNznMUAFTHflPik/nkVaQu1Fvqt3zwpEPbKjViiNz8wag1HbD5MXzzW5l9zlIO0+wXVIHdtxGs1DFpSINzZeVQe1k7WWZY2fR02Ouy+wUvNDIsNFsMu6+WwIBGT/P6bPXzUl12Yp+nKuFQCSyKf/4Hr+JvHbs/nfclqjuGbS67JwOhlGR0DNGeYptrE/+oVDzZ/xmKIeAkGLm65gfmVDV6gQoaehz/7gZn+5I+ttPTjslDwD2kiLp0f7Gh1egKe92lf8m7Tm7wuX+InZYuLoVoTfro27wubFnvIvwjEKJ3eo2JHNeDI7JU8spHRg1aBHvDYHv882YCQ8tuRSX8q3E4xOGeCrLgiGrxNVRIBGpsTeTPbwYiAap7gd4+XnSu5fhgcZGIqLYTi2enc4bPLvvNIMfB0uRcZB7mWJ1KtSavVJsuOLwBkVW9pQ8pt561puEre2I4YvP0deCy8d3NCr/xXOhwVldN63mGOxX6nrdzOAPtRGUSB9KM0K7SybCtWDtj5DfiL3md16jFfwMeVl/+qlW0FhpGmtVjrLOSoPa8XT7a6g2Z40bL6t8us3Qut1IQVQ+wc+XdwHVxbCOBi9HffIEjK6oPMGJteMkHmvk6mU9N8UoJhPzFUcw4NYwbx7o4cyc7xF3G14NmBJiEcoheNL6jbLX8vfOlJZFBPPdRiTsLcZJdyLOLJwOfHF0U5FXw8mTIKMkAbAuxYd3jFnsAfVMso25y/MMFEiaHuwrRoL/cfVaEoR2YgGrTDUYCONWGp3Oy4AzVerf1ChahXcVzWJtUrpUOg HTLtKh8T dsDsQGkwRTLXKGGw/O7/QbcpMPVSH4HnNGECN/tJrfA5pEaqp90eZFofWknvYaQWl/e7vTBtLyLVGnQgY5fumOls5lK83XcLdMPLREs0f+owxZW8YE7H3rjWaJD9i5ENahArIAn3qswzVp0/VjSYva0tb9K+xZXgh0GtNydWsYx1aOWTavH5E0tzzfBTl5YpXZU9KHGxSvbEcUDnADhkP7ZZ2swidlo4lRYp+4R+tBgUtOb5epp7d2UJ+0BRnq7R5M911DiAAMfK8rHl2TsrYol4etbwhu82XhCMG2D8+ZvQoUH+i3Dy81X+5Avn/bOi4fUFBvPK4tzlasr88XRppz6l8W57LA8J/P2378f22aXbBvYqJA+RZJ15CM2ZbRYNFeNUG2rOFxJglqc2vvqJGxHf5ki3Eyn3JxbVVZu+fIc4CJS9WFYUw/YRuVbvpm0JQpVaTV082llOq27Xbblb3LJ0wng== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: When kmem_cache_alloc_bulk() fails to allocate, leave the freed pointers in the array. This enables a more accurate simulation of the kernel's behavior and allows for testing potential double-free scenarios. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/linux.c | 45 +++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index 61fe2601cb3a..4eb442206d01 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -93,13 +93,9 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, return p; } -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) { assert(objp); - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); @@ -111,6 +107,15 @@ void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) } } +void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +{ + uatomic_dec(&nr_allocated); + uatomic_dec(&cachep->nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); + __kmem_cache_free_locked(cachep, objp); +} + void kmem_cache_free(struct kmem_cache *cachep, void *objp) { pthread_mutex_lock(&cachep->lock); @@ -141,18 +146,17 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, if (kmalloc_verbose) pr_debug("Bulk alloc %lu\n", size); - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (cachep->non_kernel < size) - return 0; - - cachep->non_kernel -= size; - } - pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs >= size) { struct radix_tree_node *node; for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + node = cachep->objs; cachep->nr_objs--; cachep->objs = node->parent; @@ -163,11 +167,19 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } else { pthread_mutex_unlock(&cachep->lock); for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + if (cachep->align) { posix_memalign(&p[i], cachep->align, cachep->size); } else { p[i] = malloc(cachep->size); + if (!p[i]) + break; } if (cachep->ctor) cachep->ctor(p[i]); @@ -176,6 +188,15 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } } + if (i < size) { + size = i; + pthread_mutex_lock(&cachep->lock); + for (i = 0; i < size; i++) + __kmem_cache_free_locked(cachep, p[i]); + pthread_mutex_unlock(&cachep->lock); + return 0; + } + for (i = 0; i < size; i++) { uatomic_inc(&nr_allocated); uatomic_inc(&cachep->nr_allocated); From patchwork Mon Oct 9 09:03:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413126 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 E07B0E95A8E for ; Mon, 9 Oct 2023 09:04:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7E2D78D002B; Mon, 9 Oct 2023 05:04:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 791E38D0001; Mon, 9 Oct 2023 05:04:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 659908D002B; Mon, 9 Oct 2023 05:04:19 -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 570A68D0001 for ; Mon, 9 Oct 2023 05:04:19 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 1F2FB1A013C for ; Mon, 9 Oct 2023 09:04:19 +0000 (UTC) X-FDA: 81325336638.01.E26D790 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf20.hostedemail.com (Postfix) with ESMTP id 37C731C0003 for ; Mon, 9 Oct 2023 09:04:17 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RT8wgQRn; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1696842257; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=GnfOI+Lt4eo+0dsNyhVoOcwz8RF8uhKZrFDQ+AlKZNforJ4vW4aZ9ZXSau1V0rOtQeIRDU 0KNYr4xNhmH/5AQmnmmVmh5OeWZsWubBI82nsghrb4mKpN0OX31qckXndzlJu8Y5AHxs7N Pjk/m6/g3G7CxwQ6mUDZGWjM8FeZ79w= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842257; a=rsa-sha256; cv=none; b=T8fGp8pt4mHVVVekKmvRE8lbmun3SwmtN7/+30y6GFiCt1k2zx9RHmld57la1YQX5NcG5I hssmsYIyEdWAkCgu/YtFGc1L/ZZenKPy53FYMSZvTCMP+Esfbi+l/Ao6KrNpkWDC0EsLIb NOhYxK5nu6hSCHo2ykfvy7zpmumUk/Y= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RT8wgQRn; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-692ada71d79so3205307b3a.1 for ; Mon, 09 Oct 2023 02:04:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842256; x=1697447056; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=RT8wgQRn082ouQ9be9vkkBQ4RFFYoMqGyvWFx6HX5x78CbCXJg9D/b/7TPTKbI0uki 8kqcpD4UrQh6G7ML/vQeEHwKp90hkYHqGvX8UZNBtt2uxRUcInZq7NVDlOkKg7D1LMtT N1b+U0ZNZcCGAfv6jKm3Tn2gzKKR4H1GSRLSjSJ+H4//g6ajh7d4DawtRZ6yQK+c6ZYf GeQmmUW1zNw8hJFiEnA91tqigKvxM/hsJdE6Vu7b3LfgY7f6WjxHIdrujMz30VjLf/1M 0IE+Ir4hjyJ2POs5QssyBIW3dWRT8MfY0XGzwFe+p0PLslCKYDP8JR6vLyppNp8mUsvh 8y4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842256; x=1697447056; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=cHgsNcPAQxrR7qN+G+HD8x8BI67pFkWvpf+4c+q9UxDb7QXuR/IZP0kPBaFxopKOab VI3idvzdbwqdKkL4QmtFdSuhbe0e1NB7CLp88KoYYzKxrvjpWhZTzjOHQWvLB76moEMJ S8VWVbr/4VFmrwJ1MoUC0Jq7ZyyDlxMLdFvqmPcN1DthMQP/Y6uhsRoTQjlv7y2OcfNi bfgON3KLNTygI3/PPJxvEltOOnVavHilj4Eth/bYYg/jb2tbfWtE+pd8GAhnMcqAYs1h OdXOABuGYV4NmrzfPpwY32M/hDO1qjllsYA2BRL1YnofGS7jd+4RW/l5RoCha1ChX5MT zl3Q== X-Gm-Message-State: AOJu0YyNL/KI0iKcJBAGgFfZkgt0aFbEvg6/30ZnJMiloFD1nwO7sByk 6oV+NufSROH6c0aGP+EcwHTbhg== X-Google-Smtp-Source: AGHT+IGhxQLr6e0qKbMl52zcDEJo1xj/bOdWt1iR+YCZ1wJBAvqt7Qzkrv8BWaR76GhnhbO+h6xSDQ== X-Received: by 2002:a05:6a20:1382:b0:14c:4dfc:9766 with SMTP id hn2-20020a056a20138200b0014c4dfc9766mr11293031pzc.46.1696842256084; Mon, 09 Oct 2023 02:04:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.09 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04: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 v4 05/10] maple_tree: Add test for mtree_dup() Date: Mon, 9 Oct 2023 17:03:15 +0800 Message-Id: <20231009090320.64565-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 37C731C0003 X-Rspam-User: X-Stat-Signature: 5xfyghjsu1sf58ew7dyymf4a1w59xstx X-Rspamd-Server: rspam03 X-HE-Tag: 1696842257-252244 X-HE-Meta: U2FsdGVkX1/23PYUQsR3A/5+EZ8QluXu1XsdsSu3+p+evYJ/7wsC1D+1rL9nEXL0QWQMYG57bGOk6jYN2dDlPkcANm3t7Dc1oRyAZ0tYHZ7jUpypmP5FzQSCaxA/1trORw0uHlOpEPElxRZT4zMWmciah9UUy3fSz7JizkhMLXag9G3xkU6ru1MCuAYdPfL5EXQT8mi7c/UAGTp7K8rRZy2PzFM5t7DMo3OmWHq1OaXV91305x/k6chss2gxfHHwrcv5wljLFxDSlXqKhksLJeJ6/6EV2FNatcwrp10N4DwWxWi0yoDRqPCjwHwY3ERDNePRbQqXT7ChnCNvBq7uOZdueqW/1aDQglIDVlGapYjSZ6YMgRsBKap6rHA+P8za4Nn00MnYL69VbZJVFvCpXlUQAO5aQqdS/Ef72kKHsdBK01362xajN5h5X4K111GHgGHMp2FCCvAdT5/6K1Exbs282u8/1l6npABzn18Csf8ew+QFAugY/fm8DjpEmrKtxW0FnDTZDiFxb3qQHLeF7mKfS1YPncz+NocluaIJDVk4YUIygzbYl6DDmr9o9H56WBSzSOlcCzcnI4qGHn6VUcz6+oLJFNkOKadRgHmmSzVwbCnqc+h8Ute0TZ6c2l+E9IURDSSYcH+JFuit2x0BLhV7RJ6YyyqSqYswROzBpZW3LWGGBFEYnOBCf6gUkvp9dcjY+moqENhxrfo8CJiUjxuO8yrfit2mmOlAoU8xuOjVxv4qJ1ocSmBe+TPKI02tUSSx/cUUwItKDJA0oUjFL4BQTycTYsiGkAmZkcS4sbajkZ7ijprnc5+S7Z7Krvzt+Adz1VJw858LuRqBJXDbkzOaSD/pfWIyQDhRIwV6YT32nHRlO8cHoLnvE+Ve5jzRha3fNfklH3OkDbtXGB3oOH1jknsKYRY3MZNVPcUgWSQdQ8w1ZwcQbPdWmmpRuhEJETYm3x+xCb1sMQLrkwS P8XLHijG b7KuONRRrlSAvcmpuet6ZReHtroEP7yc8zzJSplORERXk8qMOxetCCawQ0oP8XnbfAffosv7VRpsdYm/xQ7616Oa+iI/9wB1azzLtNMALNDrtXICi6AlZsKKX3/gvRB5mwGtX7vPLmD/wZzxeVkS5e37xgMDo3pCskXIq2zsH3xaG5/ZwHVnmcLpPxzbKRBN5LIXn/NNAhuzPLPHaTmkse7v/AoUD/5o1exsn9ykbolUbLaVPOeafWC1o/gcwdMyaUgZvumAQfFcrBwZGrjsGdwCVE0IMYqDsfurG9P9ckRDf/EBlzjad4g1llAup0lmLCMrqG+B1km3PoHwmh7U/orJyyNl5lsrQ6U/GcBZDA+DHk+m1U/p5a7X3GA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add test for mtree_dup(). Test by duplicating different maple trees and then comparing the two trees. Includes tests for duplicating full trees and memory allocation failures on different nodes. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..12b3390e9591 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compares two nodes except for the addresses stored in the nodes. + * Returns zero if they are the same, otherwise returns non-zero. + */ +static int __init compare_node(struct maple_enode *enode_a, + struct maple_enode *enode_b) +{ + struct maple_node *node_a, *node_b; + struct maple_node a, b; + void **slots_a, **slots_b; /* Do not use the rcu tag. */ + enum maple_type type; + int i; + + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type = mte_node_type(enode_a); + node_a = mte_to_node(enode_a); + node_b = mte_to_node(enode_b); + a = *node_a; + b = *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent != b.parent) { + pr_err("The lower 8 bits of parents are different. %p %p\n", + a.parent, b.parent); + return -1; + } + + /* + * If it is a leaf node, the slots do not contain the node address, and + * no special processing of slots is required. + */ + if (ma_is_leaf(type)) + goto cmp; + + slots_a = ma_slots(&a, type); + slots_b = ma_slots(&b, type); + + for (i = 0; i < mt_slots[type]; i++) { + if (!slots_a[i] && !slots_b[i]) + break; + + if (!slots_a[i] || !slots_b[i]) { + pr_err("The number of slots is different.\n"); + return -1; + } + + /* Do not compare addresses in slots. */ + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; + } + +cmp: + /* + * Compare all contents of two nodes, including parent (except address), + * slots (except address), pivots, gaps and metadata. + */ + return memcmp(&a, &b, sizeof(struct maple_node)); +} + +/* + * Compare two trees and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) +{ + MA_STATE(mas_a, mt_a, 0, 0); + MA_STATE(mas_b, mt_b, 0, 0); + + if (mt_a->ma_flags != mt_b->ma_flags) { + pr_err("The flags of the two trees are different.\n"); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { + pr_err("One is MAS_ROOT and the other is not.\n"); + return -1; + } + return 0; + } + + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { + + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { + pr_err("One is MAS_NONE and the other is not.\n"); + return -1; + } + + if (mas_a.min != mas_b.min || + mas_a.max != mas_b.max) { + pr_err("mas->min, mas->max do not match.\n"); + return -1; + } + + if (compare_node(mas_a.node, mas_b.node)) { + pr_err("The contents of nodes %p and %p are different.\n", + mas_a.node, mas_b.node); + mt_dump(mt_a, mt_dump_dec); + mt_dump(mt_b, mt_dump_dec); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + } + + return 0; +} + +static __init void mas_subtree_max_range(struct ma_state *mas) +{ + unsigned long limit = mas->max; + MA_STATE(newmas, mas->tree, 0, 0); + void *entry; + + mas_for_each(mas, entry, limit) { + if (mas->last - mas->index >= + newmas.last - newmas.index) { + newmas = *mas; + } + } + + *mas = newmas; +} + +/* + * build_full_tree() - Build a full tree. + * @mt: The tree to build. + * @flags: Use @flags to build the tree. + * @height: The height of the tree to build. + * + * Build a tree with full leaf nodes and internal nodes. Note that the height + * should not exceed 3, otherwise it will take a long time to build. + * Return: zero if the build is successful, non-zero if it fails. + */ +static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, + int height) +{ + MA_STATE(mas, mt, 0, 0); + unsigned long step; + int ret = 0, cnt = 1; + enum maple_type type; + + mt_init_flags(mt, flags); + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); + + mtree_lock(mt); + + while (1) { + mas_set(&mas, 0); + if (mt_height(mt) < height) { + mas.max = ULONG_MAX; + goto store; + } + + while (1) { + mas_dfs_preorder(&mas); + if (mas_is_none(&mas)) + goto unlock; + + type = mte_node_type(mas.node); + if (mas_data_end(&mas) + 1 < mt_slots[type]) { + mas_set(&mas, mas.min); + goto store; + } + } +store: + mas_subtree_max_range(&mas); + step = mas.last - mas.index; + if (step < 1) { + ret = -1; + goto unlock; + } + + step /= 2; + mas.last = mas.index + step; + mas_store_gfp(&mas, xa_mk_value(5), + GFP_KERNEL); + ++cnt; + } +unlock: + mtree_unlock(mt); + + MT_BUG_ON(mt, mt_height(mt) != height); + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ + return ret; +} + +static noinline void __init check_mtree_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count = 0; + unsigned int rand_seed = 17, rand; + + /* store a value at [0, 0] */ + mt_init_flags(mt, 0); + mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(mt, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, 0, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, 0); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i = 0; i < 30; i += 3) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + /* Failed at the first node. */ + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + mt_set_non_kernel(0); + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + MT_BUG_ON(&new, ret != -ENOMEM); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Random maple tree fails at a random node. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + /* + * The rand() library function is not used, so we can generate + * the same random numbers on any platform. + */ + rand_seed = rand_seed * 1103515245 + 12345; + rand = rand_seed / 65536 % 128; + mt_set_non_kernel(rand); + + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(mt); + continue; + } + + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* pr_info("mtree_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); void farmer_tests(void) @@ -35904,6 +36261,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, 0); + check_mtree_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); From patchwork Mon Oct 9 09:03:16 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413127 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 6EC88E95A91 for ; Mon, 9 Oct 2023 09:04:26 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 08F2F8D002D; Mon, 9 Oct 2023 05:04:26 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 040758D0001; Mon, 9 Oct 2023 05:04:25 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E227A8D002D; Mon, 9 Oct 2023 05:04:25 -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 CEF9E8D0001 for ; Mon, 9 Oct 2023 05:04:25 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id B0548A0170 for ; Mon, 9 Oct 2023 09:04:25 +0000 (UTC) X-FDA: 81325336890.17.761B8AB Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf15.hostedemail.com (Postfix) with ESMTP id E302EA0020 for ; Mon, 9 Oct 2023 09:04:23 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EuNFKob3; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1696842264; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=xLtR2iGiKpBWH7cj6dSx9GiocCYjGNPpbuNrUKbFSLVlkiF25hZfnUDjSRmqRxu1elJNwl NjNMRE+WORHfPrTc3X1qwB50VDVZ3/FdWBfSK1ZDHiWJ8BGI+g4Xpv4IVbel2VdbOGi986 6XqZYM+sRNlyLH4uSXdyA//nOLFJ//c= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EuNFKob3; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 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=1696842264; a=rsa-sha256; cv=none; b=QVxAqBekfFSLyVH3Fx65iBowLe5XCee5KfJfyOyrPw9dCBi7byXxDUrUYo11OiobwhAfUN 1i5GjEqvMgyeNaXa7vV8p6aWunWzRH3FUIlmnqdgGCRKHdOIsHjbU9mkq89KmkMOGvaETg u/IpY46flR0hmlWi08HhlpFFeDWgdc8= Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-692c70bc440so3185107b3a.3 for ; Mon, 09 Oct 2023 02:04:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842263; x=1697447063; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=EuNFKob3aZMN9SZAaPcF4VRTMM1DVAHsoippMtv6m4+NGgF7zh7pXp0urIMFsivYsw MEi0AVP/2iKKje2Ewd5r4Pi37a0oEAupHaIXxWB0K5/S2sxjc/9q+hL4J7z0MbiEODym UWqZkxkT+WPY6zAjUiRk+gsjzjlyTKlgD1kLS8UQ8/zdKj+7qew0bMVbPmSkArCVYD1K elh0JGZWrdGMGBo6267g0jJ1vZpQTBwSBxsfI/zljFepjAIwgo9+B+cUMfxq0zRVM8x+ knIov+UCpmuAGd81tkq3eMMgic85FSz6Cq95+BQcYx4JOyJHacJUTYdI8TCL8aisEFu7 rZYg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842263; x=1697447063; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=mOc5VunxNwxQHyBhtR0OBUukRrukyp6uvGXDNU7k0hIeFqURr59I5no1caxQOhedxL 2eJzGqvmVRDCcF5jf40GOYQq2aMvRulgKeSiN5KvsCCLTB8hd2MM0bm0gnCHEEMQmbAG Ex5MexqqWzT/YEIWbJCrRJ5xonvFwMM/9dpHEkkCU7tpwucUYbsO6r76/5xUbgZR6chA j7fyloWTkSKFZWWzckfkRCR90qCeRXzwe/Gtp+/6eKbO0OU6awFhd2nAe0I3YtMb8/p4 ZEk7N45NNFmw3A01URp6uYTh8PvTi2wybB627ZyxvuHZZM2OC2ulhms8OU+dq716dxXh b58A== X-Gm-Message-State: AOJu0YwbSGP9NAkeuvm4er11hUNAB2fia5p88eVgpSy6c8EDq3ymLQpE wxe+zRGh7uR/bT48iMT/B7BBWQ== X-Google-Smtp-Source: AGHT+IFKCVVlKWApUakuntFkxtH4uqaJa47bxlvJGIvckq1RZ8mrs/tVEi1bx2puyhb/HtfMhfqyng== X-Received: by 2002:a05:6a00:14d2:b0:693:3bed:e60b with SMTP id w18-20020a056a0014d200b006933bede60bmr13898154pfu.12.1696842262782; Mon, 09 Oct 2023 02:04:22 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.16 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04:22 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 06/10] maple_tree: Update the documentation of maple tree Date: Mon, 9 Oct 2023 17:03:16 +0800 Message-Id: <20231009090320.64565-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: E302EA0020 X-Rspam-User: X-Stat-Signature: hzg153htnx7qw4mynpi9nrgbhouusw3g X-Rspamd-Server: rspam01 X-HE-Tag: 1696842263-250508 X-HE-Meta: U2FsdGVkX1+ecsgSlpOFrO3tN2ThNeN45IWHYuJ9/9s0OxrpkT8UinIbk82GPzSWh9fEf3FH48Pv7Jhxpa3IJTVHKicMJF65/4C1Pssu1G76g8EQAx7Kq3gWhKY17N6Wd1NF8TcLYR31FsiRba+LpHdWlH9CJdKwXTZ4B9TcvZBSeb2a7P8M2reHR6vZ79K8L5EG7rqLOocuQdc0xurM2st+NN9KoDBO5qWNTlkOAanXN0khXfhJBmZ3elbEbdVqRz2gg4cyrVINRdHQjtRWH117uWRk/1WGQ9tuvqfZbEggVCAOvyPecHIzywuT2uskWw3+8QrPWkyCKFr9uytqG7xIWB0diETqsJvurXjZJS59w70YJNSwWgPRjDPnoWAoMB3qstrvHUGuVBX84rVUz2YC9869pntBKbVunAZJ1R82I95yMA81l2nqjI1EsMM+Y2cxjEfQafBCvRXIpD8MHrO9sAdllWixakaSocyY0GKQqbTlwEY3cp/vPnRl1eOOuDQPH5qAF6lS70hlL1y1iNzTQNkuumeWi575M7yvL2GqBnAJ24n6EFfMAHNrr+Z1KTPeAWoIEUrO3Z9ZviG/z+vE/gKKU/tHrGu7KXW75pGwni507fOPOYO55C/uwFOZHRLHnB7mPrduice+ZLUOB2hizlQc+6z0kTiVAHsieuB74RiiZA0JWwX4bDDJCxlLisaXej4USNo46+oiUnE1VPAu72nJ+2imQQsKv4X3eDFuH1X5qFWnUXO6iN4GeNZF+1HaVeObgymJ7XxCOjswtCEnEi8svgQgaRHdwP4LGQwyUuaD9N1hpmVhyCRY/k8RloS/B/xS1LE3XQqz7+4oKmGJ6r09GQAVx/3KWks+Rs2IZ9wl44Fm0k9J0dsZ5RIcpvMoGFrHBh3npq3xDu62jVoQxO0H8gpBYFhz7fuBGWZtYDGvQ9f2AS+bJwSTeBxSpUzktsd/Qlyo9DZMicT A5Z2jpsE jJ/TbIJ0046pmdlETQ2iPPS/HXysFl7X1/M0dGTwde9U0VLZeVGKNYl7R/9UkX3IXzZKTHHGtnk0WbCgmoGXL50wQgRYjWofLN25iZGL4jTaqk+FeiAbtrChSLFcDPt1ns2ev61Y8DZvcfG2PhYKgtHlzDJmao+ZQXiLnZ4KBBMoDofNoOG1nJPOcTf00v6SAczCgi3oZ635BBnKau2c2fbAHdB/cNKmIk5CQrjvN/k5yKayr5jv6M5oBctqAcfJGshrkW+oCB4W+TJ97UdMo7+kZau5nSa2d8ePGz5NR4XPV4gyeQFM30yCV5xEeYKlkIad5G6ywfuxCMS18gvOS89XGOXo1W4e5rjptCqS6s1EV48DEQrXt6eIvfQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000421, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Introduce the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang --- Documentation/core-api/maple_tree.rst | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst index 45defcf15da7..285e2d2b21ae 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -81,6 +81,9 @@ section. Sometimes it is necessary to ensure the next call to store to a maple tree does not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case. +You can use mtree_dup() to duplicate an entire maple tree. It is a more +efficient way than inserting all elements one by one into a new tree. + Finally, you can remove all entries from a maple tree by calling mtree_destroy(). If the maple tree entries are pointers, you may wish to free the entries first. @@ -112,6 +115,7 @@ Takes ma_lock internally: * mtree_insert() * mtree_insert_range() * mtree_erase() + * mtree_dup() * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() From patchwork Mon Oct 9 09:03:17 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413128 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 37083E95A91 for ; Mon, 9 Oct 2023 09:04:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C4E668D002E; Mon, 9 Oct 2023 05:04:32 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id BFFC98D0001; Mon, 9 Oct 2023 05:04:32 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AC6FD8D002E; Mon, 9 Oct 2023 05:04:32 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 980208D0001 for ; Mon, 9 Oct 2023 05:04:32 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 79714A018A for ; Mon, 9 Oct 2023 09:04:32 +0000 (UTC) X-FDA: 81325337184.03.F0B3813 Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) by imf17.hostedemail.com (Postfix) with ESMTP id 8322940004 for ; Mon, 9 Oct 2023 09:04:30 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hDWO2hVQ; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1696842270; 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=jnskIBrvSZEYEyApxx0F6Uk1TEGei79sZvSWDi4Yrxw=; b=1EhxCVbyYowJP6G7HuyMxOkCJUeVBhGGmySyWfG+7+QrWdTdD2SXuRWJPbg+pJkL/sbzU0 D1hnKZby5Qzmcf+ML165rYR9BXxArFkXYVp2MZrSDrrwHADx9L0pASJqKyQC+/NZpWtrWh eIUw5xiwvVAjKu8wXPAeCmyOrX61Czk= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hDWO2hVQ; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842270; a=rsa-sha256; cv=none; b=rgfQTzzUmBVRjKaBK6D4D/JWaBUOtv/W+C4vTtLcuY6LZEacGE6RBN3iquz78QrDz4aY0v jcPD6f180t78Gr1XEWm2OTfe4Rv4ezXWciy6wYphBdKjsD/zhbUrGVlMbqIhNqjwBQHd2w 0oXIjZ6m2U84fB1PpeUOPsBitgbwXmw= Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-690ba63891dso3072794b3a.2 for ; Mon, 09 Oct 2023 02:04:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842269; x=1697447069; 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=jnskIBrvSZEYEyApxx0F6Uk1TEGei79sZvSWDi4Yrxw=; b=hDWO2hVQpCwom71CUBW2Quz89x8bmNl0Gwcv5Ri3v0u/kJsKnDQgfnBOzAomVWb+d/ XZSzJgnhy+Z2YcPyX8solC/VJ3cZltm/j3tRd/MtllrXFyX4k7gcDhnaQkumsVRsFFtd YwlKTz1htRh1BKbqQTZwCNOcCiEVYIQDoWN+b08krjrJAgGqWVWAJJMQm8Yq5ZTizHk0 HrYD6gx+fzUimUO5p2KcWyesPT+ChcVqDO8NwO7Z7EjXEKuwdHSJSCCaV8LWF+iHQ1Ue t/ikrAXSKOxRKpaVvZWgg0tq/woLQ6zD+MLDh3d0HqN9aOpGh9E48ogqTowszCf4L8gQ ZCXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842269; x=1697447069; 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=jnskIBrvSZEYEyApxx0F6Uk1TEGei79sZvSWDi4Yrxw=; b=jRkoXDCOu/X4W9GPZzqOW0WSV5uZo7kdexOoS8zFwNBhVxasR9s1V50oGGhuiLFyhJ IMaIfFNtenwUj3L/a3PSY6lBW+WM8c4xNWTt2XNU3u7z+fAxxuprH/Bdq4DycJfUtoOj 8RmO5i7A0+mpNxUambdWqkh+IWokWALydwEaut/IdJ1zPgRh+X0twDPi/ShAXd61hmIT nG/OSxnIoZpYyuU5ZpOlY0a4rrI1SxBg7S8hV9kk+Z6ZadbwC+guOb8s90I8dOO/pJFT Uoc8GrLGrWi7cBMGgzRazkuBwwb4ToD6M84YiTgU7t7T/V/6XW6XIFVY4uKmmdYy1bZ3 3akQ== X-Gm-Message-State: AOJu0YyGepzjJMtaJcI4jXIZq6udIg10tvNKo4ksKluLhsblgRSLNQXm jVvULxIoaBqXkN3Eszb0gZuE2A== X-Google-Smtp-Source: AGHT+IET1qb2peUsO8cEnYgLpRkD93NRxlManliBfrRzGPRkgabOCFSqkeE2y8LdqsuC0g9EI5V17w== X-Received: by 2002:a05:6a21:1a6:b0:16b:afc2:3b69 with SMTP id le38-20020a056a2101a600b0016bafc23b69mr8157702pzb.36.1696842269350; Mon, 09 Oct 2023 02:04:29 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.23 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04: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 v4 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Mon, 9 Oct 2023 17:03:17 +0800 Message-Id: <20231009090320.64565-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 8322940004 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: 485o41nzi79rsrqfsrd51hoh4681anku X-HE-Tag: 1696842270-821185 X-HE-Meta: U2FsdGVkX1+6v5/WaUQp8fMQG9RFmKQIzEGfTlT4fYgN6dGYCtLFdS239owQGtZBaxOvoiNk1sp/ZR/0Q8giF/QTr8Du8rGRJKwxQx1ANT5Ac2SiNMIZ2o8gcQUbFSgoRdzx/1oYFIyWcbISGD6VkoGXIKjX3fiA9wHYKxCixujjPhxGIuDNi10mUX7JumL49b1YPRO9XOaC4YIYEi8VMivcQCCUyy0awHBZ31Oz0qRgOImnuZj5cyhMl8j4DwWgi39qN/AGW/7tXTIJEKBwDx2Yfv2oB/6SP1r1+GnYPHH9i/wjRvgcTdlzrfRLSsc4ypVODdxpk1GXKURZlbGUTYFPK/xTiBcXeg2hWH50DEJBEPbuodEpLWtfpjl2qeqMCddxN8Qku0L0t6fWN2/Z/VfllU5F5kSoJSEd5zsBuVRkfdHi4U/70+0VwQNSXbm4dpJPnJOZbTrgP6R5YpDFWy9R1CiYEnmcZk1TVrTBRiV22Xuy9nfEXWvjWNtvZWbhKTtP/VF5C90dZpzjrC2lmv3Xe5bV1zXBbruGcS3XvcdoiOE5H9BglVjDOt19ENt/Jgb4/v80r1sOG0pSJA2v5971BELmQH05D1OShhSmEFlDRAcWCwhR4f6qzae+BKAJRyKLZUIc9TicvOuGtmpGEUL10pZfhAIn59YBhcO+DMuAGl04732xjG9GN9i45cgPxEWKO4iBGwpx804w0EjCJGYYOSLjJumil2Z8ONxCLkLiO8DD9X7QlHoqHaOqpujhfkm6s1Dlcpz/0SIElzaHlEFEL1s0RA4c2Ad7M3PZT3gqdca7kUcFuhH8+5J2CruBoRYjnZU98pIul4zdmigkZwOk+D21zG2Q1RPytKjjP4YAoP+lUv+7NSwzzMfnjJOWWH20kg2b3oz0jL1TlkziRG0dGpix7i35fjrPEODApQs2luabt9QtF7AnWfw4vXbk+g4pqIQQQrv4/nKqBng Gluum1Rw wG22Rb2NxfNDdQB+br1mY7U958wIOcqifYEiFx8ExGYJy5Bt9sHu2qF0Wtrw3btjh4Yhgjt6j3Ohcsq66h5WgM4kqTu5ipg09mg9bphDmHfVNGi5fpECxkBvJE+iaQa18n9O2lzsbO3Y7XW42CvRsue0QkApMycEPbYB/cOKhQ4SJPAC2MSPVqXyDTL0bkfg7CrzyBAeu9qwCyEwXPNSo5PVXWXaNrI7bGldM8A1SP24xH18ZZ3j+GJ6IYBxBji45zx7/VB7/aa2wRyUiuc3AeeflVxzfa1+vMNgd8ECWXB7o5XD45YmRwxYtPK7k65CfWQVsvJhH5/lqVght99ez2UzrnbOLvuLxhkZY8Bt6DEKDlRp396V27TN/uT9+JpASxJJ/Wl3ZU8/v+rez5GMCemiMnDtnvngbvpmjrbgE+ra1zCZmk/F6VhYgdDv5tgJljsnvHNgBRJZJkQ6OOOeFqVqAUQ== 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: Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 8 ++++---- tools/testing/radix-tree/maple.c | 2 ++ 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 06959165e2f9..27d424fad797 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3572,10 +3572,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); @@ -3633,6 +3629,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_root_expand(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 12b3390e9591..cb5358674521 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36299,7 +36299,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Mon Oct 9 09:03:18 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413129 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 895C9E95A8E for ; Mon, 9 Oct 2023 09:04:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2159C8D002F; Mon, 9 Oct 2023 05:04:39 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1C6AA8D0001; Mon, 9 Oct 2023 05:04:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 067538D002F; Mon, 9 Oct 2023 05:04:38 -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 E68A98D0001 for ; Mon, 9 Oct 2023 05:04:38 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id BF565C01A3 for ; Mon, 9 Oct 2023 09:04:38 +0000 (UTC) X-FDA: 81325337436.26.1BD4E5B Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) by imf21.hostedemail.com (Postfix) with ESMTP id D3AE71C0013 for ; Mon, 9 Oct 2023 09:04:36 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=G6lAe9O2; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1696842276; 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=8v1OZEFv5O146V21vBTm5TeKaYSuxLzybT1UdN8aEPI=; b=h7XTfR6F3oPk+L7MrdLwwY5LsRKGGgC1Bpy9fRVwuxyuSEuaeFZbMrTd3uIMopL3pJ6cGD LOjyfhR4uyKeAP0JB1qKcwvWFikEY1r5jzWSY60nxUDi77M3LCE/CUJgPvIFBW9k/QNOjI 8ygEhv35rR6Pr8tT4W3TbtqcYepRIU4= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=G6lAe9O2; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842276; a=rsa-sha256; cv=none; b=J0fNk42BBEAf1nmoSKSDUso+UfGI+bCHxpfgxpnjAxTW5ICgA0D0niYM9/OX0dvVLXSLfc 8U4lxQJzjGG/GsxDhEHUWEthjXySOpe+ABv6uog7Uu8pdZrOyhsmlsHwuWzxhYD5iArz0A XqOZNRDCcYzqfTz9HtIZWGpt9aSi5eQ= Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-69fc829d7b1so1386493b3a.1 for ; Mon, 09 Oct 2023 02:04:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842276; x=1697447076; 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=8v1OZEFv5O146V21vBTm5TeKaYSuxLzybT1UdN8aEPI=; b=G6lAe9O23kfqVPmauSHtB/57vUmsUhNYaUcpCbc4gllw56usRnlHl9UR0jH2xy0+KM B/8om7XU6UkaWsIZ7sjEMO1ENTlM68K26M0ySz/6c8xU8jFBpIZ8MBapxfsrf3QTTvSg bJ4mlQMaWF7WleMLbH4gFORm0gc3ds1kYg8MgXgnh92BzDB78PxSN4QsCSOEEhWzdz0M KvomziVePacFSm0sReSuWNbvzxtSwSdAhoZl83KKhMtSdwwGURmyiu3u+e/IEbKScwcv Ia0zkZS6N6MA0nuo+McMLaT2pnLdQME+cGVImyrisvy4DEFpVC8f4HcIPbETaW/MwCG3 oVJQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842276; x=1697447076; 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=8v1OZEFv5O146V21vBTm5TeKaYSuxLzybT1UdN8aEPI=; b=PgLdqUCUriNvrOcFYHLJQGNspIcEaCpOupbEyMn5U28NOYrz25Lw8FyDgS8eLiqSmO Pn0Xk1etarPfMYyjIGYRYePK9R/FK5bah+pMh9ZhjEej6TkHx2NioUK3lYQi1GsXcU6X iwfF78AzfaJ9wSeEcsHu483sYU79vt0br8jpPzFlnhgSIII8xvbnru5tXT5NCGcbZLiN Pdcx4bU6LUWEhq3rh8KNL5j2hZHUDVJkJ7u06IY6IhGQd/rui3qKlJMJBKYHl5YOtX6P YgDXTc6m2LAuCkdomH71bylIaXUPCIwahDFGf/1AUo4o8KDQKURDPi0Y9whPNwfpUyO0 YH9w== X-Gm-Message-State: AOJu0YzNSaNvZCpBoi/E7D7ih730c6oxU9bJFk+uPPU4bs7eaZcANYTT Hg3VEFqXzSz6RqDLc+6fmaczmQ== X-Google-Smtp-Source: AGHT+IGW3goxheixUnKrkWUN2cRvqCUUmgS+X/SOAABQUeOP6LJPmPjlNnrYOpaxH5nwIYLNUCgF5Q== X-Received: by 2002:a05:6a00:158c:b0:690:b7a1:ac51 with SMTP id u12-20020a056a00158c00b00690b7a1ac51mr19018763pfk.31.1696842275718; Mon, 09 Oct 2023 02:04:35 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.29 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04:35 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 08/10] maple_tree: Update check_forking() and bench_forking() Date: Mon, 9 Oct 2023 17:03:18 +0800 Message-Id: <20231009090320.64565-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: D3AE71C0013 X-Rspam-User: X-Stat-Signature: 4h74dtochbg95fpizk1yopqanfzhdf67 X-Rspamd-Server: rspam01 X-HE-Tag: 1696842276-343872 X-HE-Meta: U2FsdGVkX1+LEFIskEBjDk9Szxx4c8lZf6+KY3Mp/lavm+QQ7st3seY3VMuwUvFA6fet1eeOvhDbflonONtqty1Nexu0A/3jbJNTV+uMapnFxFG2zU+TEGFt5xhD4RC7TXPyOTvUmRajOnw7XpyiVtXqO5wqwHm9TKf8V6Blt09Ns1cF1CB2wGKHfAFsl6Flt2oCjLUZ6oQ+fGb6I0kzwGyLDeEMmORtGz8h4/Bun0S91P1iF8G1nt8QG65pUCrylNwI4aGQrfsiGpUy1mK/8AM5gdSplz2SuS9qIDQdLFVqEr13WfkCLH9wvvrNjt8v/qeY3j3yZQ/k7R9/xDvV90WB287+ZZpsKDGn73ADJyIWiG5r8bS2NTvg3ydC9DnKXMhNcn8jOAh03EFBiMU3UtKCabth1hBdjc5ujhtE5/ICGWHPHJ3KZz+Ef1+sujvMJFcJKPoYMXLhiDaB4hSVxXE1L5HCwA2mw4k8opWiVxlmnLvPMas6AAArqUFu8e6udM3Cy0YDmgO0ZrtEwNkSDvwjg6d0TpbDsLAnBlXX0I1PWFxJSE9NOoUIoyA6r0LkImeXfCCMMFkvTX+0LEsP58XtqAw4CM9ukKCSsukPDv3gPrLcJyS6XStroYAl13hAK5Km33Y1JTmPaxbZWrWtdVm7hOpiW9lUd3WUFNm4DsLmHtiHnBwCAmO50azcjQPzlIfpxoN+Q77N2VzTGdFP/+BKXSH15IaaDBU2ROc8fDpGKrznjEbio1q+fuvVW/1jIEoItSuzIkob6Y0txBB9oW+zikhPSagRlzkrs/s0CbspL2ZEhhe3d4TiqQ9I/oFH1lT9lQWCR4/0p74XXpm5Cp0SZJtV7wvJQ6CdhK09P+cDdvem8OcZDgcsTJWESF48hP0R6A+6e932ua2omF34n7TDM8wHsvy7j+IAK4L/o3xceBlBd7d4F4UwYtKzHGNoIpcAY8Mos3gCnBCpi0H yNXU4xg4 wzo6k00ViHDZ0iUlTKQvK027LopSTIr7YHh/QQIcjp0jbf6uqbwGidxduZ/zPGMOFwRqD6Uk3qllza1sY5YEKYDTeFL7tlnbUpXvLFCv+GV3WbUcZ6WBC+yi4ASHJNyePnyI7PS5yds1gy/sSj0MTymcwfP/XezxMGb55RHh2N54KELDaV14BLv5kiMEz5+UEPin7bn6MWtpucd+shQai0y1k9uVry7AWjmTCTg95SWI3xqIyVrMPYl/BArFEX60fvhtjpVKR0t7RYyAtT8IwlnTDgIvheaHshqLFnLkMRE+xVl/Hz8ZkFtDQ0kYrCIS8C8xLWqJVcpW7TBW+UXHiMo+6Nib5rGBZ368GNjg//Ufu5NtPbN/6xhaz3TrbT7NCdZFVrj20eqJVQwB2JbwGdhNASjY6PCSYSnFNFRX4OufKHRz2xYY1aXNDCuo7az3GtwOaZFlVODpnyq6ngLcg5EYnKA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 61 +++++++++++++++++++++---------------------- 1 file changed, 30 insertions(+), 31 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 27d424fad797..bcd07c220a13 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1837,36 +1837,37 @@ static noinline void __init check_forking(struct maple_tree *mt) { struct maple_tree newmt; - int i, nr_entries = 134; + int i, nr_entries = 134, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + + mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL); + mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); mas_lock(&newmas); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + 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_unlock(&mas); mas_unlock(&newmas); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); @@ -1974,12 +1975,11 @@ 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) { - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, @@ -1988,25 +1988,24 @@ static noinline void __init bench_forking(struct maple_tree *mt) 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(); + mas_lock(&newmas); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + 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); + + mas_unlock(&mas); mas_unlock(&newmas); - rcu_read_unlock(); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); From patchwork Mon Oct 9 09:03:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413130 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 57A00E95A96 for ; Mon, 9 Oct 2023 09:04:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D13818D0030; Mon, 9 Oct 2023 05:04:45 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CC24D8D0001; Mon, 9 Oct 2023 05:04:45 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B8A728D0030; Mon, 9 Oct 2023 05:04:45 -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 A5F478D0001 for ; Mon, 9 Oct 2023 05:04:45 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 841D2B46B6 for ; Mon, 9 Oct 2023 09:04:45 +0000 (UTC) X-FDA: 81325337730.15.69BE19F Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) by imf30.hostedemail.com (Postfix) with ESMTP id A6FF280012 for ; Mon, 9 Oct 2023 09:04:43 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=SFDRRV3v; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1696842283; 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=54w8Wcln7nae9IbjCMSOqwvs+RMz0++Lh1/ZpbM0xiI=; b=NFHT4XTmH6DaExoIrkxMuizXcyEBrbcV+w+ZjmNkyPDmvCQB4z9p3nKby0go/srBNEj0Ra Z1lxtmtEz99e52qPqvZteiKUmAhd8Fgpvv6pfW/UASe8X9AXuuQtPUIGVDIBk3z+o1Ojq6 7VUOnTL3P/a5zMtguTS3T4wmEy5WRFU= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842283; a=rsa-sha256; cv=none; b=mEQUMjM+FdVJe+gDVoKvFnTaSydtMu1IXVwGlNNUSft5vEe26GhEj5E3aUvp5C393Lz00L urXd5SFpdnI4FLNaxh0aXZw1+O7L0X9DaJKNtedXZlLPeiE4qL+X206r0tBYCQq9aFeMT+ lE6p/1PZ64QVfToBrNWElBlhBP36viw= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=SFDRRV3v; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-690ba63891dso3072895b3a.2 for ; Mon, 09 Oct 2023 02:04:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842282; x=1697447082; 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=54w8Wcln7nae9IbjCMSOqwvs+RMz0++Lh1/ZpbM0xiI=; b=SFDRRV3v1sq/PvGB6azhLBDvpZYfdN9oXI6oVwO5Lad7qvVMsdV4MTdWtoLg7TPs4A 8i7u5bSpSEvAztK9Dypl7KwkRi7Tl3TjN5CjI72MLnHlGwilRjPMfXT48JJLmF9zLYgT b0HWgvp21j2Ep4v44O1/fUc/d5tTGVas8dqX3cXJzla32L89khjhFy9FEEOWirR7KSU1 6ue8gbcPrZOuhy+S8tlCs0TctlFXhZ1fx4eh+cqooGz/tL0YPazhpkMrVx9Nlxxpc7Ts ChJhIJigpjbgFnVm93UlyshMYDdExsneSDT/61Zt5iEdRYefxXA32LiJlOowmYlCwKW4 Oxyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842282; x=1697447082; 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=54w8Wcln7nae9IbjCMSOqwvs+RMz0++Lh1/ZpbM0xiI=; b=XSDiOa6dzCwhkgymJl1s1YtHkn4tbhGf1zCQistN4tXFqEYEpkFQbPXg+c3BJRATqW G9p5Gy178V5xGuA5ddhpchSMszGhl3BWsv/o9L98j/ttDjlWFydK4rgUUiqHTf+ycDY1 3GKOhiTBstqf+41mS1hY/Jq1cITrt5MVAIZ9kEbMabteBHhauZ3w4jgS1S8sOTz6yHIK MKJ1OxqWnCiHPIVOxUEfJl3yySyzgC5evMWayl6S5GfSwYmJooHS19D0d2wYnz10SGeZ 9V7XO5XlFVyk3AowuRvrtbJMeQ6Uw4n6n/QivLUfZJIQ71BFk0t4UnFDf7kSBF8glx1p TrUQ== X-Gm-Message-State: AOJu0YxSIOclz5YRC7R1lCiEg1oYiueLg4r58BDBzSucSfw1cmdO98WU uYge9chY4/laJOGIEQQ9i+n7cA== X-Google-Smtp-Source: AGHT+IH4ASgVACf0DF0bhjU6o17uphbOiGw/lY/A6lPr5sbkTIKGbp1G2HkSuztTS2B+TAnqtzva5A== X-Received: by 2002:a05:6a00:1346:b0:68f:e0f0:85f4 with SMTP id k6-20020a056a00134600b0068fe0f085f4mr14645034pfu.25.1696842282594; Mon, 09 Oct 2023 02:04:42 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.36 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04:42 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Mon, 9 Oct 2023 17:03:19 +0800 Message-Id: <20231009090320.64565-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: A6FF280012 X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: uephb1qhzszpnhjqyewwibi4fgw87aij X-HE-Tag: 1696842283-350255 X-HE-Meta: U2FsdGVkX19MMnD6KbZ3Vl92Lm7wd2oNTIyXRX9dnE7DohwinLVzbGXz+2YSfBGbRjuvV6MNM+87dvuXHxi9nT5UxbHGUv0q+9cJteEYyWwrmLl9KuGTozRf/ouXD+jPbbVi/LzAA6k4hafIxPAppgr87pvoRgAE6gMn3V/FBqScw+9gBmIdR8vyMYqOHBii2zwu1z5seQrGvsKnKKzq59fipu1+1OuTrKSLAOCqoZt7S5+j10KA9mvQprSu7vz1OEyKB5l42IFhd8IhH7RNPxWAmJeSiwP3kIaOwvf5FwOhyC6N0M9YtbkZBAL+mlN5sIS7TmVT0PSEDgpbsMcRPxOiluOZjvBsYrTldr6pZ4jOMQoCDHk9t49cHz8ECxgiZEPeKeUGDyvV5a2TJkG9in2KWaxUkWjfEnbnM+UVTUROmAYTalCMC5KUcamq/09Ap8Y48nbWmTrb+K2scEEN7XVTE18wpk3jf5llLQ/qd8iQi+EcWRbbaUGHbHCEYVYyXQAO0d0ww3Ng+aUepdQ8Fjt77F6DMz13viRHMBhJ5yWmCol/m6BCRRFbJI2Y/KzIYqd9z/PpWOJvVtvTN0knHTwJlmHgXC1lMHHwC0UcmOOpDinZQ1SMe2aFjh4s0LaawQKy7LmcXv3DLbhROn4+aqPUAT6YWo6cFBxgYEqPgg2d5Gl/XlB3gl9nS8O8rwFjjU0I0J9xRvMWc2hJg0u06LV8pChd1aGCDaUXFi5m9tXlOERFsb25jbcdE7caa7+Pb/+voQ0xL2C/mZPYOrZPUR20XlvTqcnb/cXlsLWQwWxHO3oP4HD2qf7UzIsbww9M4J0gvaXAiI5cXwfP8VJVK/nISXfVYQxmjMRnmvSxcN199N5nUadZtNkVKocZTfi1EkoCDcOGb3EXNe3fTfQ1XafBS7Rkw3WsDiSrOhibQRxiDxUxoZQN9QUVZ/u6wAXbHruLwfj04keZnnoBWw5 RcfGJoii CiXoobAXYnP4pAbDGvYTuYvjevodOL+VPhCfWd7ocCnZHypnC/FMlDkMz8/ce6Z2axhpgApXB/3fJ9UGhpyMZTTyRWn3/auCjKwxrSftE8NlVrErLiLgsCmv8YFgGo/5t5KLdHFarmA2zIfYR0hhgU2UWoUXH7G4lT4g5p4wRTqkyUzWMm/MUjpNxIT8phBug6Fbb+v/f0Nu9R6Ynh93MWgf4z5IxCinOAUQ4OrI64ypWbPzDWrCPgpX5DdCG6421uHCcz8tRCSGOnwA/d56WWnwhMU0TsyEFSzZdDr9YWFk3OeHKYXgMD1WWuQAjB5JPIio0s5zCJO/HfOuJkWNos18nIJUqolNOOCLCOP7O3tlGQMfpsaMpOPMgRcLrEPaAR5uc+eHWXRvmWgQ9EmhzkhgXWtYbooTQeE70uZ6IcGlTuBQBMFNWIfoy9MzWuCCS/o8/+W+q9hJKZMC9x0ezBW7fhg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: When destroying maple tree, preserve its attributes and then turn it into an empty tree. This allows it to be reused without needing to be reinitialized. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d5544382ff15..1745242092fb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6775,7 +6775,7 @@ void __mt_destroy(struct maple_tree *mt) if (xa_is_node(root)) mte_destroy_walk(root, mt); - mt->ma_flags = 0; + mt->ma_flags = mt_attr(mt); } EXPORT_SYMBOL_GPL(__mt_destroy); From patchwork Mon Oct 9 09:03:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13413154 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 1CE7CE95A8E for ; Mon, 9 Oct 2023 09:04:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B4A408D0001; Mon, 9 Oct 2023 05:04:52 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id ACC9E8D0033; Mon, 9 Oct 2023 05:04:52 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 87D4F8D0031; Mon, 9 Oct 2023 05:04:52 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 668FF8D0001 for ; Mon, 9 Oct 2023 05:04:52 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 3708A1CA379 for ; Mon, 9 Oct 2023 09:04:52 +0000 (UTC) X-FDA: 81325338024.30.676BF36 Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) by imf26.hostedemail.com (Postfix) with ESMTP id 691B4140002 for ; Mon, 9 Oct 2023 09:04:50 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=a14gKnxu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1696842290; 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=J9NBeOeUOKV7MjQXBf0OcDJpNNzzRaiKWMLyPnHJUCM=; b=wji19SGNrpOKOKEluLRAC8SfCUOBLQx1oKConUxnVML0Sf3DQ1lOvzPy+fhWFLxL406qsa IxhTe/+exWyFUJH55k/owQ+3TOxgwf9LSnYGsy18rilxYMy8eHzk7isUZN1X8n3rB1/Vu3 4KHnBk/siR2C7sVBSDHrhV6FVB9CuFw= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=a14gKnxu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696842290; a=rsa-sha256; cv=none; b=4Ldffu59m6CQD/3QZpnIxY6VYMNaD1TJoihHIPmYzikQK3R0ZEfSHYRKC6jXqGHlrp4cmk BMoqkqtE/YTNuugNg4+mtHAEilWsZ0q7HSTbHb8Za//7XX0+Gw8KjR636qQIevHBsAP/ey hIYSHS3nng0k3vncxXD1yvehYV2mFtA= Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-690bd59322dso3072548b3a.3 for ; Mon, 09 Oct 2023 02:04:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696842289; x=1697447089; 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=J9NBeOeUOKV7MjQXBf0OcDJpNNzzRaiKWMLyPnHJUCM=; b=a14gKnxuYoZFdjCOVV8A4F5YsUMsJTElL+40OdAgoQUxCV3vINPEyoKsJUHVzCB4aX OKtomq6otms+MbOPPd2NdwwRN9z81sUNkdH0QanaanvPQFMCQ7Cdb5fjOnzRyHslYmjt 6mQfDna97a3HvPA/x3ROr+cS4KJWfBhLhYeXqzjw5CzN+oIPiRDLe/itFU1Ry2/TMbRb LeaLMjUWFktfhcbGjW64VaUxznev7kBIsDmwmsxYVkluT2aYBeWtr7Nlw0NgBSbrO6p9 ys1edfe5ArGk9oXqZ/TzsbqLkv5pfw+pT+hGYJdFsLUFIcBDvHH04FYSbjIR7CCr51uO 5+zw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696842289; x=1697447089; 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=J9NBeOeUOKV7MjQXBf0OcDJpNNzzRaiKWMLyPnHJUCM=; b=RiltcEdEzAkKzjykOrTCpEGedk6AZtP8XaKPI/McbjdkjGa1p9WfQJTd5fo0UHrWeS 7/54nsYEdxloLZRaoWf+0M52BlOnQ+BCV18s6/2jl2lIqKv+TaUmjNYg/vksi3KkbTk/ kc0/Cd36lOZvkJLEcr9Rdm3m1/ZjImOfJpDNdew9xTjF7BbMIFHyyJijxghqLObR77pW pku6ci97SY3SFnYudwrVTvdUOIVLpnbHAB7ggCS/UJKKOiKRiH1vTVheTYNwRU30azky mWs5kNgrxITSqr1NguocvfI9J1rQWVioZBbeeXtiFMX/NlVZqgpD7MLcTZC6g/3Qlx26 Fj1g== X-Gm-Message-State: AOJu0YyPMvLJkpJi2DqEpzXxXqvK7S59kKYk6zsChNHpEE5jjn+t/9tP wElXE317mXjLXL554RXMRCHdnQ== X-Google-Smtp-Source: AGHT+IFWmVZ8CGi7MzxRf4NhvVXp4nBgy8RRUrzo84/q27FPUoZvvNAnKU3L14fffrsvBYvtEh1KAw== X-Received: by 2002:a05:6a21:1a6:b0:16b:afc2:3b69 with SMTP id le38-20020a056a2101a600b0016bafc23b69mr8158325pzb.36.1696842289307; Mon, 09 Oct 2023 02:04:49 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id fk3-20020a056a003a8300b00690ca4356f1sm5884847pfb.198.2023.10.09.02.04.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 09 Oct 2023 02:04:48 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v4 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Mon, 9 Oct 2023 17:03:20 +0800 Message-Id: <20231009090320.64565-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20231009090320.64565-1-zhangpeng.00@bytedance.com> References: <20231009090320.64565-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 691B4140002 X-Stat-Signature: qyty66y3t7arm3h9qgzkj6aa4ydo8u6m X-Rspam-User: X-HE-Tag: 1696842290-705047 X-HE-Meta: U2FsdGVkX1+n0E0npyikln8gAJbdaeBL+1cBS9JKzVpcFOC99cp0G+Uqzf8QcTOuuOzytVN8nykmlKMi/kr75A5FeFM/ta4jcB3mtLAYDU6pKuJ3Sxnjj98IuaEBJg2x1nKcr1UnjRVaUOUzt+02qIf3+loQyJrrb6MHH3D2KqUCwXsavjHElA+qFOKAgxcls+N0orf5QgeFDSBT43UdxlVG25PQu9NVTigzYJd+SLFKrfNSj0wiGF7m2jGzbdr9WXSZtxf+9FHm2HPQLwL05AD94QemPXf50nXNzXJfHZJ8XTwWDD36PuWr4hchJDjFei7c7jP+PhPTdiwUXUa2VdGm68SxtA6xJw3AtUcsDBH2wMZvBLeTFqbAWVb8EufH+BamI+WCe3vSkMT9m78B06Fh8t9lFSZY2c+JCmOMdcbq03nRIBrpSbHyf11IJSh4cJ0IuZbVXp6BYIKATH518Kn1b9GKqhO/L4ahouJYPt5BvjpmfOmD6Lfn9ie41EDus/2yahUMTSA0dbv09jlKO3GH0KQH0mwmH4mmLNVhbNVjTOoT9APgYLK5znr6tU6qRgKaZDx9e2sRk5bpcwNk/4xF7I0/dPZeyTP+qd05GSktYZZDDeTjb4t/PDgmcAD+vXsUHzPzbl+zLyPs4tN8iPtkdtSAkDEcE3DrlIcdfkhFM5IaVtVIlPo0VwjTcw2us6SgNz5ynmJ5gFqUBRDEELkQ21Cf1qdm0B5Z5bnl5HB+QPz8KgMpdHVSuYNMelMgDpqpkcUKL6JrT446lVt7EwRH2l+2v1VXHEAyy1Uu6R3b6lpznxW7kxLLUvL4d8DejzLRVC7eiJctkJ5JhhEYBq+QWRlDIWSFM9P3oKhoSEhr4R7SVz1vRVpXIitVydPc2DeADxhjkfux3bV5ZLV1AEYNVGOQsyaFeRxYTFEwzYILLoWZiA09mKc2+jMz+PyX0MJsUACUCCwwF/4Zu60 WMMaFHyK JkN4xmWWNde8+Kpq5//PI8Rxw3UAmQnBcfrjtZQd/qSw0ls2/q9SLyOFG8f8meKfEOlum2X4jbhoclLANDXusmNaltbjIzZ8PiS9nrBSVGorV/g8UPKzXUrPDg5oBzVcQJk/BJ6ASnltVuhmVdBX9tC8dj7lCFrniC4b8dQ4kbioi+lmbIHchc86lejdrQN5qx3VCe32k8QJxO1FZUhLCZk7fLhYL3OldHbalrtOT6ENDmOqSx3TMp/gwstHVvTMFtjGIbgQoPnCTZHEEaAzb7JG/hd9gQa8lhlL5b7oMZX7MUJsiMh2oMcnuujLktpCjU7LjuRRgRe2hzSM8LfrBvtm/C0uodcrAjQhszr0ypIs+7jqGfjBLKFcZFWsdHxa29bHPCBuVAguAI0Tx3yoDee/PQzPDcLGu9+8wevE/CctiDu4h4YLL9jK4SxbTR4NJh+MXlYeNcz5Zra5Mvu3i/x5YUTNJOvfpimE/18rR04u39cbB25iizP3x45N3f2APKJYo X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then directly replacing the entries of VMAs in the new maple tree can result in better performance. __mt_dup() uses DFS pre-order to duplicate the maple tree, so it is efficient. The average time complexity of __mt_dup() is O(n), where n is the number of VMAs. The proof of the time complexity is provided in the commit log that introduces __mt_dup(). After duplicating the maple tree, each element is traversed and replaced (ignoring the cases of deletion, which are rare). Since it is only a replacement operation for each element, this process is also O(n). Analyzing the exact time complexity of the previous algorithm is challenging because each insertion can involve appending to a node, pushing data to adjacent nodes, or even splitting nodes. The frequency of each action is difficult to calculate. The worst-case scenario for a single insertion is when the tree undergoes splitting at every level. If we consider each insertion as the worst-case scenario, we can determine that the upper bound of the time complexity is O(n*log(n)), although this is a loose upper bound. However, based on the test data, it appears that the actual time complexity is likely to be O(n). As the entire maple tree is duplicated using __mt_dup(), if dup_mmap() fails, there will be a portion of VMAs that have not been duplicated in the maple tree. This makes it impossible to unmap all VMAs in exit_mmap(). To solve this problem, undo_dup_mmap() is introduced to handle the failure of dup_mmap(). I have carefully tested the failure path and so far it seems there are no issues. 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 --- include/linux/mm.h | 1 + kernel/fork.c | 34 +++++++++++++++++++++---------- mm/internal.h | 3 ++- mm/memory.c | 7 ++++--- mm/mmap.c | 50 ++++++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 78 insertions(+), 17 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 14e50925b76d..d039f10d258e 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -3248,6 +3248,7 @@ extern void unlink_file_vma(struct vm_area_struct *); extern struct vm_area_struct *copy_vma(struct vm_area_struct **, unsigned long addr, unsigned long len, pgoff_t pgoff, bool *need_rmap_locks); +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end); extern void exit_mmap(struct mm_struct *); static inline int check_data_rlimit(unsigned long rlim, diff --git a/kernel/fork.c b/kernel/fork.c index 0ff2e0cd4109..5f24f6d68ea4 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,25 @@ 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) { + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL); + + /* If failed, undo all completed duplications. */ + if (unlikely(mas_is_err(&vmi.mas))) { + retval = xa_err(vmi.mas.node); + goto loop_out; + } + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, if (is_vm_hugetlb_page(tmp)) hugetlb_dup_vma_private(tmp); - /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + /* + * Link the vma into the MT. After using __mt_dup(), memory + * allocation is not necessary here, so it cannot fail. + */ + mas_store(&vmi.mas, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +770,19 @@ 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 (likely(!retval)) mt_set_in_rcu(vmi.mas.tree); + else + undo_dup_mmap(mm, mpnt); out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -778,8 +792,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 18e360fa53bc..bcd92a5b5474 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio); void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, struct vm_area_struct *start_vma, unsigned long floor, - unsigned long ceiling, bool mm_wr_locked); + unsigned long ceiling, unsigned long tree_end, + bool mm_wr_locked); void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte); struct zap_details; diff --git a/mm/memory.c b/mm/memory.c index b320af6466cc..51bb1d16a54e 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -363,7 +363,8 @@ void free_pgd_range(struct mmu_gather *tlb, void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, struct vm_area_struct *vma, unsigned long floor, - unsigned long ceiling, bool mm_wr_locked) + unsigned long ceiling, unsigned long tree_end, + bool mm_wr_locked) { do { unsigned long addr = vma->vm_start; @@ -373,7 +374,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, * Note: USER_PGTABLES_CEILING may be passed as ceiling and may * be 0. This will underflow and is okay. */ - next = mas_find(mas, ceiling - 1); + next = mas_find(mas, tree_end - 1); /* * Hide vma from rmap and truncate_pagecache before freeing @@ -394,7 +395,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, while (next && next->vm_start <= vma->vm_end + PMD_SIZE && !is_vm_hugetlb_page(next)) { vma = next; - next = mas_find(mas, ceiling - 1); + next = mas_find(mas, tree_end - 1); if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); diff --git a/mm/mmap.c b/mm/mmap.c index 1855a2d84200..d044d68d1361 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2337,7 +2337,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas, mas_set(mas, mt_start); free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS, next ? next->vm_start : USER_PGTABLES_CEILING, - mm_wr_locked); + tree_end, mm_wr_locked); tlb_finish_mmu(&tlb); } @@ -3197,6 +3197,52 @@ int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags) } EXPORT_SYMBOL(vm_brk_flags); +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end) +{ + unsigned long tree_end = USER_PGTABLES_CEILING; + VMA_ITERATOR(vmi, mm, 0); + struct vm_area_struct *vma; + unsigned long nr_accounted = 0; + int count = 0; + + /* + * vma_end points to the first VMA that has not been duplicated. We need + * to unmap all VMAs before it. + * If vma_end is NULL, it means that all VMAs in the maple tree have + * been duplicated, so setting tree_end to USER_PGTABLES_CEILING will + * unmap all VMAs in the maple tree. + */ + if (vma_end) { + tree_end = vma_end->vm_start; + if (tree_end == 0) + goto destroy; + } + + vma = vma_find(&vmi, tree_end); + if (!vma) + goto destroy; + + arch_unmap(mm, vma->vm_start, tree_end); + + vma_iter_set(&vmi, vma->vm_end); + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end, tree_end, true); + + vma_iter_set(&vmi, vma->vm_end); + do { + if (vma->vm_flags & VM_ACCOUNT) + nr_accounted += vma_pages(vma); + remove_vma(vma, true); + count++; + cond_resched(); + } for_each_vma_range(vmi, vma, tree_end); + + BUG_ON(count != mm->map_count); + vm_unacct_memory(nr_accounted); + +destroy: + __mt_destroy(&mm->mm_mt); +} + /* Release all mmaps. */ void exit_mmap(struct mm_struct *mm) { @@ -3236,7 +3282,7 @@ void exit_mmap(struct mm_struct *mm) mt_clear_in_rcu(&mm->mm_mt); mas_set(&mas, vma->vm_end); free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS, - USER_PGTABLES_CEILING, true); + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true); tlb_finish_mmu(&tlb); /*