From patchwork Thu Nov 14 17:05:24 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sid Kumar X-Patchwork-Id: 13875509 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 7C1A4D637D4 for ; Thu, 14 Nov 2024 17:07:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0FA936B0096; Thu, 14 Nov 2024 12:07:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 083786B00B1; Thu, 14 Nov 2024 12:07:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E3FB96B00B2; Thu, 14 Nov 2024 12:07:31 -0500 (EST) 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 BDFD56B0096 for ; Thu, 14 Nov 2024 12:07:31 -0500 (EST) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 7528D8137E for ; Thu, 14 Nov 2024 17:07:31 +0000 (UTC) X-FDA: 82785328836.20.4C141C8 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf06.hostedemail.com (Postfix) with ESMTP id 7436F1800EC for ; Thu, 14 Nov 2024 17:05:03 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=e5sEXTDf; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf06.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731603872; a=rsa-sha256; cv=none; b=jTrCW9crt6AevTvwgaoc1MU+i0MNp29QR/qhbGZRa1mM/spFiBWBvFH4ZGYBKyNer/ONEo IWSLhldyvxy+BbMxWvuL5vDQPCWNcgD6c+G3YblMMCut35+sz+uTXK18ntTzwojqPiNBNy JsW+/C60chDxUT9DlmDHuKLqwbdp+RQ= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=e5sEXTDf; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf06.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731603872; 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=ynPl9gjds2k6dEiCMO+N2WSsdWiMIGwmXOvf0GpdocM=; b=IvZI4v92TR2M5G5LAscNjNQ3CwoJhWBQF8Dw9AwdUCCUArsfFpwOj3o/H0kCg+pSYa7w1z 5bbNhZqpgD8ykMtpxrWu8xCqTuBeaejXHuxPXvr5lBtc19VOpRk9KOEqLSS59nY98mvKCI FzCOEdZNT8AkzPQe9W0JoSyZN/yLmjw= Received: from pps.filterd (m0246631.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 4AECsbMo014973; Thu, 14 Nov 2024 17:05:34 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=ynPl9 gjds2k6dEiCMO+N2WSsdWiMIGwmXOvf0GpdocM=; b=e5sEXTDfO+9txCvBL2gaO PseoX1Eu4WM0EXd5Ua2tbRQFg21bv7KA3iM8o1O9Ft/JnW2n7NXbXDLVd2ziBk4b HscKR7HmWMTNgTGw3TQqz9OnMETwj0az+WHOz0BSHqUZBkEKrL3b7mgPxFwOP6wr fb7ChzvfT+YXJa30KiBDpU5nzGBWGHT4IaHV+vZZS3M6rdnwaoW9YKxnTtHw21XG ynTRsJtRJV7yyXi9d37B+uPJBA1l58W9KM3JE+Vib6QPzG0qEzJUJC/GrrVUq941 kPpJLdtycht+uHqGQqLt5B4LUBADwoePYA/GJvskSxqxsD5PWrafIOr1CUicb/6Q A== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0k29phu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:32 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEGqCFR022850; Thu, 14 Nov 2024 17:05:31 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy9u-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:31 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmR032739; Thu, 14 Nov 2024 17:05:31 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-6; Thu, 14 Nov 2024 17:05:31 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, Sidhartha Kumar Subject: [PATCH 5/5] maple_tree: add sufficient height Date: Thu, 14 Nov 2024 12:05:24 -0500 Message-ID: <20241114170524.64391-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: Y-Yt0maQHdk3t4xGXgbaBnY9e5HIwRyM X-Proofpoint-GUID: Y-Yt0maQHdk3t4xGXgbaBnY9e5HIwRyM X-Rspam-User: X-Rspamd-Queue-Id: 7436F1800EC X-Rspamd-Server: rspam01 X-Stat-Signature: p9fw148r43zkoqe3e1awkxpknj3dy4k8 X-HE-Tag: 1731603903-638366 X-HE-Meta: U2FsdGVkX1+U+LIsQHdhEi6sJCp83Zzuo+hOhX2T1tvjL0eGsxurAPLQQXC0leAxaHcyX3crGAags/2vCBReq1qSrr5sUKNE51v+AqShisqWTnbYdAvT6T4jilATIsZuev2wwUiyRihGDnfeQuPnIOTsDXNU6gUA9MU6g2UgYjJzjEyzQWjLNzhI7nxgC45xz/7TtjMcCJsZQ8CTV03Fk4+hOq+0+4YSEvhy40LFaOq54EwqhU2XVUQJR3rhZpnXLUPBWazDhuHYieGAGf/w6LtCxgl4x1E8TW0CKXIiJ8e4zMpDOJhaniGn9fysk4XYQUNR/16JOEbGnembkob6onW1iXNfXdWwH6wHrqnkFzwFVlJhyE38Ze9VvdLxM8qHfj4CvcBH4ER5RLZ666y84bIAm5DYXoN13cAgtpc7DyZXLWWLFtTpVn/OZ0sxvLwID7VJS9eOseQfRu8h2Yhs3/qDKjoek9a3bfEbg1R2iGFtlK207q5VnovDr1TZ6EMwQBw5Zxw6pKx8kAJRtPSQTQDIJuF25jjWVA2+8qwrKlxPv2rMxBAa8b9Q3Rd6VfKwlelEDyp/XbQlHmv4Yv72jKT9hnZPMLg3Gw10zbB+KldFUgN4aoIA11bY9x73n8GrV76u7sXuOxb7O745Q/rZv9J2O2apWAQb90H/AGxTG7AvwmjG3hNjqRJq844vIvb+UepCsik+G2y/kbAROk+B6W129yXPtTFMKqmuP60BWaN+K+9KS5Xm6yohFjfPmEXh23rq3lFYoQ4X+g/vp0LiPD1+6/XnOltRG6KkxvAMxKw5M6mvbSgpCFyUqq01vo+gO8fJWXNUJEcH5dM73z8nyEdy23lfJJsFVo5YaqgLetF4OlcNReEBx8Qp93RboAtOo1BzZvVkI+Gj5KY5RVNA3mn/zEAXWBngI0dfnUF3OQ0QOHtRGbIpVF5+jYZ1nk+WSVsqbYcQa7bohZJiCZ0 iD6Kb6fz McoFhDqvuEodIC/1mweAQ6qAUGckI0HRC7wi/ozf8HUorTkzAFrRFeQQn23o5myLP+oh/Z4zTxpvUBJvzWUnMpAEjAEpkbN7Fls5DeXRrrMpVMD7cv/ZGnHH4Sk/5erSZyuVCJDl+/XpvPqHW5BBh6+DjMpyutmnWmp+UbSXsHghL1J3XGkoVZBWbfELveGRFGRLrxAW83sY7ykw7SHW0F60ZbP+0AEZipTQg5y8b0Kuf8EQK99vkph2W6YqskOn2hgFBQ6pheTa5WLul0blGEstYLQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: If a parent node is vacant but holds mt_min_slots + 1 entries, rebalancing with a leaf node could cause this parent node to become insufficient. This will lead to another level of rebalancing in the tree and requires more node allocations. Therefore, we also have to track the level at which there is a node with > mt_min_slots entries. We can use this as the worst case for the wr_rebalance case. Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 14 +++++++++++++- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 44 insertions(+), 2 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7d777aa2d9ed..37dc9525dff6 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -464,6 +464,7 @@ struct ma_wr_state { void *entry; /* The entry to write */ void *content; /* The existing entry that is being overwritten */ unsigned char vacant_height; /* Depth of lowest node with free space */ + unsigned char sufficient_height;/* Depth of lowest node with min sufficiency + 1 nodes */ }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -499,7 +500,8 @@ struct ma_wr_state { .mas = ma_state, \ .content = NULL, \ .entry = wr_entry, \ - .vacant_height = 0 \ + .vacant_height = 0, \ + .sufficient_height = 0 \ } #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 59c5c3f8db30..3d39773601d3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3558,6 +3558,14 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (mas->end < mt_slots[wr_mas->type] - 1) wr_mas->vacant_height = mas->depth + 1; + if (ma_is_root(mas_mn(mas))) + /* root needs more than 2 entries to be sufficient + 1 */ + if (mas->end > 2) + wr_mas->sufficient_height = 1; + + if (mas->end > mt_min_slots[wr_mas->type] + 1) + wr_mas->sufficient_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4198,7 +4206,11 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = delta * 2 + 1; break; case wr_rebalance: - ret = height * 2 + 1; + if (wr_mas->sufficient_height < wr_mas->vacant_height) { + ret = (height - wr_mas->sufficient_height) * 2 + 1; + break; + } + ret = delta * 2 + 1; break; case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index bc8b107e0177..f55ab8c8b491 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36329,6 +36329,30 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +/* + * Test to check the path of a spanning rebalance which results in + * a collapse where the rebalancing of the child node leads to + * insufficieny in the parent node. + */ +static void check_collapsing_rebalance(struct maple_tree *mt) +{ + int i = 0; + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + + /* create a height 4 tree */ + while (mt_height(mt) < 4) { + mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL); + i += 9; + } + + /* delete all entries one at a time, starting from the right */ + do { + mas_erase(&mas); + } while (mas_prev(&mas, 0) != NULL); + + mtree_unlock(mt); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36495,6 +36519,10 @@ void farmer_tests(void) check_spanning_write(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_collapsing_rebalance(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree);