From patchwork Wed Nov 13 03:16:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13873131 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 E76DCD597CF for ; Wed, 13 Nov 2024 03:17:00 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6F8B46B00C0; Tue, 12 Nov 2024 22:17:00 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 634406B00C1; Tue, 12 Nov 2024 22:17:00 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 486306B00C2; Tue, 12 Nov 2024 22:17:00 -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 24AD56B00C0 for ; Tue, 12 Nov 2024 22:17:00 -0500 (EST) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id DA4D116075A for ; Wed, 13 Nov 2024 03:16:59 +0000 (UTC) X-FDA: 82779608898.30.628D391 Received: from mail-ed1-f47.google.com (mail-ed1-f47.google.com [209.85.208.47]) by imf19.hostedemail.com (Postfix) with ESMTP id E134B1A0017 for ; Wed, 13 Nov 2024 03:16:04 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Jm05i2bh; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.47 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731467688; a=rsa-sha256; cv=none; b=sbxKF4cn9fvGltz0/jeUZQhkyPKfS0rxWp6/1lz/s9Ol51JW/GU1tsRXrX5FcXgzMUp6n8 whb0S3l18tg1wmKzfo9TxyazjLXjfxXYb2hOvO6RY+JmFOX8d43XEPZK2cbBsKqLv8sKqv 9ViRoFbX3Uod2CvOVgUJpD/fu4UxlxY= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=Jm05i2bh; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.47 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731467688; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=iEgZKKTvneh89a13mEBq6vv3iiCLjOOI/49JujqqZgI=; b=JQtOCr86uG+/pv+emj5VDvVgZidj6/gsKGa5KdFSS9rvh4K0TkeDnA16Xu5WWUIyHjOeh+ 3l3iI5zCCQVPJC2kigNWY5qCHdo4gRhH1jlyWvAFq3pQqSobC9lXx9gNxSUmZ34B2x8ZJZ 4jicaa5ezLf6LolLPhIVfK9dLasr2h8= Received: by mail-ed1-f47.google.com with SMTP id 4fb4d7f45d1cf-5cece886771so536705a12.0 for ; Tue, 12 Nov 2024 19:16:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731467817; x=1732072617; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=iEgZKKTvneh89a13mEBq6vv3iiCLjOOI/49JujqqZgI=; b=Jm05i2bhz1ArGGiYxqvDI/Uh7phOnLKxvkmLs7tcSzJNYtbV/YuNP7neRiDFkHw1NT HrWIY30aeXelCvS7nyEkvFMX755M2o27rbaMIF1Utdf+6kXv+I43coScX/3C4pk+pkNb t415m1OeYW9RvKedqIx5jT49HDfZfVJbJG9YJXAubO2RFVKU9Fq6YKtAf5Kcdmd76IcK RQy3j/q2htlTcAUNasXYZiMl8Y6fP5oOj7wUxWgV401Qc4f8pKtvvXgdVpgSXysubNyi b3QD462rGRBrkDQihPfBWbESsiLsoc4PzjXQuBBGTTrpaqf0W4dadWF1Pi6/UZonbm9o pB3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731467817; x=1732072617; h=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=iEgZKKTvneh89a13mEBq6vv3iiCLjOOI/49JujqqZgI=; b=pIkfF9XTYfRepHqPxadWkms7Fh+j5Qv7neMwMGvAQniSxyzlwVIogSNd3fCFbdg4YG n2yLgLe42JdHrjgChUPITLx3IgauGwyAkJ8RM6gY+JFjxpbFyRipj4zOsInMZUjYEOfT dQ8JHLJr/RNgquvIMfqgZ2vut6PxCANLRsfjyVGMXBOpCTJmFzpLFsolQgofeiBY9mul uDEGzsEsvZEdekoaWVh6P7SVWL2cthUOB7QNL1bG5lPTne+SmchC4vu9IdgWXUAgYjeL 7Kv18++3K+7pG8WUBG+WV8Jxzjsdpzw5pIS4Scm7DA5Puf7guTfjj1fYr3w78CoEkWOS yqYA== X-Forwarded-Encrypted: i=1; AJvYcCXWLxqAboEXMDXLRfMmNjuSA5oqkp7dGPXYXn2bZFVS44TEubPyGOMGYeZJxIl/IVF9hoPEJmabNg==@kvack.org X-Gm-Message-State: AOJu0YxNHFcp3D96kxYU75UvZEQhaQ4y1/CUacTGL6pfyXS8qB+7rtgJ 1u1rymAxDiTYTz8hApmPsjZ7rTLCPeCN3cI5UeNcj5MCEdME76Zh X-Google-Smtp-Source: AGHT+IHLC0hnl8Hfqn+qfXRGiHO91GsYvql01efPD0cTYfYAZNxgzfHPSpovsnzh3qlX4vaXmtO+lw== X-Received: by 2002:a05:6402:5cb:b0:5c5:c2a7:d535 with SMTP id 4fb4d7f45d1cf-5cf0a50d38cmr15970042a12.16.1731467816406; Tue, 12 Nov 2024 19:16:56 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03b7e8d0sm6705345a12.33.2024.11.12.19.16.53 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 12 Nov 2024 19:16:54 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes , stable@vger.kernel.org Subject: [PATCH v3 1/3] maple_tree: simplify split calculation Date: Wed, 13 Nov 2024 03:16:14 +0000 Message-Id: <20241113031616.10530-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241113031616.10530-1-richard.weiyang@gmail.com> References: <20241113031616.10530-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: E134B1A0017 X-Stat-Signature: b6m79jaik5ew3rwmgw4r8ahtxcqh47pu X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1731467764-302878 X-HE-Meta: U2FsdGVkX1+yvKucdo9wY1Dtihz5CHMey4plgvdn1cn+hb/h+ZwQcjD+YDvjBxOwYHR1fPrRGR/I61Kyda6AELbxQZB5CSHyyu8mYJu47j4XXCQK3el4krHFmAtVkRxLQvVG36aS02h8Fk6HxA6AXJadnrkdn7q8ypstemR2swI6y0bRDgZBfUGoF/l+n52OipxZNohO2SfsNLvhH+5l1xzStcgYb8wcSSF9OGTgyYBT9oyF/tK+ns8KHO3+4bI5GpEYhk0ZgLjNdp/N5c6kx24pRCWWV91NsLx3IQCznuyw9cuIoojnLDFGPds7CDoY8ufGvWq4TPEn0ltMoPiEhyCttlxfCMXcWehQS8RK2VG3xcGy3HGDUsASYvRpK2TlWaML+hav+QvUJ1ESRt10zGNnZmwVzPSqEVZjVXTKKBfjaGzzro8o79/uZXZrzvip8s9Zphy/+SeHWEiNAuMlSC+J8u8JbhkFdU/zTacocF8GpRUXoFOicxZn+zE6Us1hUItKNdtJuE8V5c1WfIKVZ6T3Rs7Rda7VUT48mCxrl7P2Soj6TPZK01Pgcbdd3wPvxm6wkrssIds4QX50DFkcS3LkFWSIV1xB9eRNglvZfuNhy7fIYM4U+CNdp1oo+XmhGmEyASd4f7S4YdfpUOZt8Pyemexf3ipCzqC5cKuZZCgh4wdWZPDDz3X2M5l9etQOthiRtCO1bssd1zhRr66vjZbrM4qCnRIS25y6n98iRgJ7pidp0rCHWLMJ2vqXRTGTx1NX8jxU5k6t4HptZMVw5Hkg/m9a/wXwkaqGepTI1p1R29cFTAytZky4f+sIXuGbEpdDDihLpX5MD2yqpJj8ULl/tEORwgX33pCyEA/9arbl6LwlGjfgSx2xnc3zUnZRqjb9AT5Rsk6Z4Qc4c9PdoLc59sy9NJomeZPPFoDDMAHtc93UOFg3zP0IvZzoXNLH9axlAsIEqHT5SN9QfgQ wgMkUAEb T1UjJ8hUmXPHShbpSXGaARLoPRF/iSac4qpqapqH1pjMvaNdeSwZnMAzxKcLl4pTxTgPTc+V85XeDsWo163MjHR1EUHXN45c/vqN+hzc/nt+VhN5wovJ+eMu3r9S6mHA+2wtPKVEFre3O9FtC1dORuO+AAi/x+37OM/nF72gJE3Lc9lTLhUh+m8WolraGYoWllXbwWVcZC6IWR89YntqhNUNC5a7nVUXeu9/jXeVSljwoyCewJlVUEw7rEUVHV/GOtAbxRMyydSJbtn9pX+epanc7/qtvQ1u7XrpHCH9bDRXJ8f1oK9p0NQU5m3aY2HPsbhXrdqU8rnI5dKZcaRBgmPf0ITVjZ7GbAv/NhtvI5qsczhXYhTaai7fwwIsKQOFO7qCl8W9w9KShovsMCmw6b7RMlUWKodAnVECK+kRayGOrU00wbrk6FzC1XqjCUT2M0Mn/haFWgXSO+fjQ3Bb8pYr/njoEbH1nV6oy/mywtc3Lnm0ljuk5u8LZ3L5dvzbRWm947VnzOQd+uTkVYERp72u5Og== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000112, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: The current calculation for splitting nodes tries to enforce a minimum span on the leaf nodes. This code is complex and never worked correctly to begin with, due to the min value being passed as 0 for all leaves. The calculation should just split the data as equally as possible between the new nodes. Note that b_end will be one more than the data, so the left side is still favoured in the calculation. The current code may also lead to a deficient node by not leaving enough data for the right side of the split. This issue is also addressed with the split calculation change. [liam: rephrase the change log] Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes Cc: Reviewed-by: Liam R. Howlett --- v3: * Liam helps rephrase the change log * add fix tag and cc stable --- lib/maple_tree.c | 23 ++++++----------------- 1 file changed, 6 insertions(+), 17 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d0ae808f3a14..4f2950a1c38d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1863,11 +1863,11 @@ static inline int mab_no_null_split(struct maple_big_node *b_node, * Return: The first split location. The middle split is set in @mid_split. */ static inline int mab_calc_split(struct ma_state *mas, - struct maple_big_node *bn, unsigned char *mid_split, unsigned long min) + struct maple_big_node *bn, unsigned char *mid_split) { unsigned char b_end = bn->b_end; int split = b_end / 2; /* Assume equal split. */ - unsigned char slot_min, slot_count = mt_slots[bn->type]; + unsigned char slot_count = mt_slots[bn->type]; /* * To support gap tracking, all NULL entries are kept together and a node cannot @@ -1900,18 +1900,7 @@ static inline int mab_calc_split(struct ma_state *mas, split = b_end / 3; *mid_split = split * 2; } else { - slot_min = mt_min_slots[bn->type]; - *mid_split = 0; - /* - * Avoid having a range less than the slot count unless it - * causes one node to be deficient. - * NOTE: mt_min_slots is 1 based, b_end and split are zero. - */ - while ((split < slot_count - 1) && - ((bn->pivot[split] - min) < slot_count - 1) && - (b_end - split > slot_min)) - split++; } /* Avoid ending a node on a NULL entry */ @@ -2377,7 +2366,7 @@ static inline struct maple_enode static inline unsigned char mas_mab_to_node(struct ma_state *mas, struct maple_big_node *b_node, struct maple_enode **left, struct maple_enode **right, struct maple_enode **middle, - unsigned char *mid_split, unsigned long min) + unsigned char *mid_split) { unsigned char split = 0; unsigned char slot_count = mt_slots[b_node->type]; @@ -2390,7 +2379,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, if (b_node->b_end < slot_count) { split = b_node->b_end; } else { - split = mab_calc_split(mas, b_node, mid_split, min); + split = mab_calc_split(mas, b_node, mid_split); *right = mas_new_ma_node(mas, b_node); } @@ -2877,7 +2866,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, mast->bn->b_end--; mast->bn->type = mte_node_type(mast->orig_l->node); split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, - &mid_split, mast->orig_l->min); + &mid_split); mast_set_split_parents(mast, left, middle, right, split, mid_split); mast_cp_to_nodes(mast, left, middle, right, split, mid_split); @@ -3365,7 +3354,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) if (mas_push_data(mas, height, &mast, false)) break; - split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min); + split = mab_calc_split(mas, b_node, &mid_split); mast_split_data(&mast, mas, split); /* * Usually correct, mab_mas_cp in the above call overwrites From patchwork Wed Nov 13 03:16:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13873132 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 4CA6DD597D2 for ; Wed, 13 Nov 2024 03:17:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BB4036B00C1; Tue, 12 Nov 2024 22:17:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B648B6B00C2; Tue, 12 Nov 2024 22:17:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9904A6B00C3; Tue, 12 Nov 2024 22:17:02 -0500 (EST) 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 784D86B00C1 for ; Tue, 12 Nov 2024 22:17:02 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id F33561C56C3 for ; Wed, 13 Nov 2024 03:17:01 +0000 (UTC) X-FDA: 82779608100.01.714B1AE Received: from mail-wr1-f43.google.com (mail-wr1-f43.google.com [209.85.221.43]) by imf21.hostedemail.com (Postfix) with ESMTP id CE3EA1C0009 for ; Wed, 13 Nov 2024 03:15:39 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GqVuiDZS; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.43 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731467732; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=XdxptMo/+NjfWHNaGx4me+tTbh1L2ChqVzJPlxzf5Z5D+ocFrlN1N9mpF0kU+hoNeTYlsw gPJyd6hH7DwyGMunqOd2ZNN14fsqEhWyQ3ka9rf4Q28ue0dGc2VUiHb7mK4oc+xODfsxvQ WcH3w8JPt5uEQDYNW8GubSqAXIegCB0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731467732; a=rsa-sha256; cv=none; b=wXrAGSXoLCZu+C/uFPPkEKwMNRJq68g9VZ2Rc0pym1RxmC0s2rYNIr9dQFkPAnjkoubHK/ h2a3a5s+ZiYtn2hHEgnR07yuQI8gUBYdHqBknZW8g2DCQGKzzFxUyiC5KpBRg8pBP1+DfC +CJFBAdTL7+6zhYuRqeD6o+6Qudki2o= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GqVuiDZS; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.43 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-wr1-f43.google.com with SMTP id ffacd0b85a97d-37d70df0b1aso4075375f8f.3 for ; Tue, 12 Nov 2024 19:16:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731467819; x=1732072619; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=GqVuiDZSxSJuVDbGotc5ngKLsR19A3ATohSQY+U3Sa9MUEkkByYx3H+3FPblYqSx0i MG6SXvitPE3SNZez1DVA+pvBcZJZa5NfdeyOC1/SzYQOVlF5PIixcFnRdZewmhWWRqfV 3wlVqk5ZwwyBhsJJo2jtXhFYkfR3QLYBq4MEFFNbHuhDJekJuGipg44XJ5gLBDdolJOo Mc/lojv0z5/mRNNVcMl1zR2XQpwhiD8FzJGYIsUGQYiplHcicF68CNaxtOVJxElNJDIB sPMkCVh5yrXUgOyIg9FqSY3VMRFDrSwxI6UGKfB6C85t7A4NocblRosNbA0TwMcRck3C 7c1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731467819; x=1732072619; h=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=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=amdbYVJqPngRXGUJhu+GVz7ujmRCL/n6hHFLRwGEAqAS6WV7PP+wLd7OhxjmOt1l3u HpPfwbZTCtlV7HEn4dmW2CK96yYLoBrOwXaCPmhKdZE2hdHU5ZgKPZDZdMrTW/kCN9+w yy8/VRFS7DJ7NvxexttPhgidwf2lnEvHxazVgru3FKpw7Ii2CQuEaGiUi1Qe+qBxb6C2 eRU/RdapD+tYlzgrvNBb4xEB0iljzuMISfjrCmXf4YQJxSuZeB5g03MA5RqvkbvMW8nh W/DmLyBjJzvxp6wJvyxTIHHLfmgvvkVxFvnemmdxSMTxoL9AgxXDZhb7IiJNA0R2PPrn lB8g== X-Forwarded-Encrypted: i=1; AJvYcCVSvG9GIyberz0ESRyskHDDuoS+jHJoOAABD/Nkxhh5w+m/UOHuZ7CrpTIZ7Gt6rHNZRBSMoEQ9Kw==@kvack.org X-Gm-Message-State: AOJu0YxWF7J9WHukhd1v2f5t6zN5Ah76vE7MuigtbjVzJTKaTTqaeFSH wlk9piJ/Ah5uIg4jOrd/VAWe9iShFzl4JTHRhpSkPcNZhzOjtBYw X-Google-Smtp-Source: AGHT+IEddt00vX2l2YXz0+piP+2d3c29Bf5BqMddTwACF1f8JwgSO8ZpmXyWAMitikDto96XifWZLQ== X-Received: by 2002:a5d:6d81:0:b0:37d:5133:8cba with SMTP id ffacd0b85a97d-381f186d161mr15789433f8f.20.1731467818617; Tue, 12 Nov 2024 19:16:58 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03b9b661sm6677648a12.36.2024.11.12.19.16.56 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 12 Nov 2024 19:16:57 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v3 2/3] maple_tree: add a test check deficient node Date: Wed, 13 Nov 2024 03:16:15 +0000 Message-Id: <20241113031616.10530-3-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241113031616.10530-1-richard.weiyang@gmail.com> References: <20241113031616.10530-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam10 X-Stat-Signature: wf43hgjsza6j9fpy74pfrby8hazyx55z X-Rspamd-Queue-Id: CE3EA1C0009 X-Rspam-User: X-HE-Tag: 1731467739-475572 X-HE-Meta: U2FsdGVkX1/FhysiKrIF6PgjcgrTdU0FfFy0jLnUWBaF/avaPwm8eCtIRDvj9jNXwQjVaF3LGxNRUmV5XHWB6oMW+48eut+WxN+yb882Kjsmkp+AE0ePlXQJkrn0Un6x52G1ehA3LN4I6c5sHrvtyR8Lq7EaM4KA4lYE281bv57FyoNuO5Bzr9pHRDhbPq1W07GuHmFUmSwjdjzv1NuGYxrlgf0p9OXhOwKLPjoC659tMeGENcfYVGJK8tIX5BsphvMPnlmAF+2um2yCxNTv/lXzgAMPT8JstESSMeJC1Q+j4k7g2xiAo5RD7xKEtTt/2XffaqWuXOxu+brDpZcT2AgvVJMYL+n1dCwnAHoRMhOBdXWFicvvGeG31K2JBRB+xPdwi3ARxSSxWOOE5dw4rf8nCYUnfO9qHnSiQ4XX6qpQKnSorjUJOMgt2cKLgru492FUBU1WrmO0Y31DSrQMwBa8pstvLV0I+5Qr/NKNnU1kef04NEAqOSAcL5wt58MW6SmCxOWcaEeoSrnk7z8Tybn9cm0f/Oc6cDkGABz6lqfWl8BTkQ4XFe0r4TQ8xXL3cYq+C3LPEbCCvJAheqfVw8RtZ3Ff7BOMhrHW0wlzmMtBACWkZXbYa/ipVLedNtPrTAPOTpsWyyhTO1syMa9WARgmTuIFZYazecrzSGR0MGgXtiGjFwe+qhTxtJETOHeB1tpBV65rCPleoWVUsiyKdm8kMOWBtIF9kfg1puATK6ksNCZdpg1jdRjPcl52N+/jbMuocXM61izOafpYbW4xglpTUNMDzcye5/6dLWev+dhrwMGgCtLebf/IasTpBo6n+WxZKiTrr/mmmjEicnWhJoVhhAsrhBEc45H1AEFfuhxQNv5lQkuZV0IDHEWQvUe8xvuc5HolF18o7aQCSBcygNbMLksKjMDxXT00HOaNOukwM5QRvvY4pl5BP6x2bvi/3lw3kLjpo6TePgTPnTD /8qitJke NfPnz9zaD0VyDGZwcGQBHhG48PAZ4tsrYv9w/NZ7a7sCNkJUqZxfKMgW1NyR26O79miD+/4mHPMR1/hTIZYsu3f2HauCwqRzSqrlTS1rEhd88BBVLOy98KYJ3VUsEn4cQiiTCp4K8q858pIo0chnLg+fdyXas7M0WMoVKn9ufIkQnv6dRhcK1o9skJQD6pL3wYJ/j9kMR8x8DyslTMwNFuZXYgGeBTuq+bLUEtMvjHHOi5BY+naljSMwPxQbV4208P8nXEcE4RSNx7hhmBUN7kjgGCvYA1m6uZuCFAMtIDU8MR9exMXWKDqqCeqtsCOv0U2TdOZly9ADX8fKL/dJiKjliWTg39EzKPPPM6dHWbAa+hQFb5YPE/gKvsaP2gGaV5jYUJ60eVDP5Is3BLqBQT61TdsyIlnF16sK/Jqx0YnFhIVllheCKPJ1f9tFY545LNjuet/vWx6MyoI7WKcGIbpgIOFZ53mhxfcNNHslDrNnLDVE4mtiiaNUmTp1IAxQt0cde X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Add a test to assert when resulting a deficient node on splitting. We can achieve this by build a tree with two nodes. With the left node with consecutive data from 0 and leave some room for the final insert to locate in left node. And the right node a full node to force the split happens on the left node. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes Reviewed-by: Liam R. Howlett --- lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 704cb1093ae8..72bda304b595 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1563,6 +1563,30 @@ static noinline void __init check_root_expand(struct maple_tree *mt) mas_unlock(&mas); } +static noinline void __init check_deficient_node(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 0, 0); + int count; + + mas_lock(&mas); + for (count = 0; count < 10; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + + for (count = 20; count < 39; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + + for (count = 10; count < 12; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + mas_unlock(&mas); + mt_validate(mt); +} + static noinline void __init check_gap_combining(struct maple_tree *mt) { struct maple_enode *mn1, *mn2; @@ -3796,6 +3820,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_deficient_node(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_store_null(&tree); mtree_destroy(&tree); From patchwork Wed Nov 13 03:16:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13873133 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 43D2AD597D2 for ; Wed, 13 Nov 2024 03:17:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C78ED6B009F; Tue, 12 Nov 2024 22:17:05 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id C27426B00A1; Tue, 12 Nov 2024 22:17:05 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A7BEF6B00C2; Tue, 12 Nov 2024 22:17:05 -0500 (EST) 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 7DD1A6B009F for ; Tue, 12 Nov 2024 22:17:05 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 3B9B21A0734 for ; Wed, 13 Nov 2024 03:17:05 +0000 (UTC) X-FDA: 82779609990.14.038EB09 Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com [209.85.221.41]) by imf27.hostedemail.com (Postfix) with ESMTP id 1DF3640009 for ; Wed, 13 Nov 2024 03:16:19 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=lmPvkwxe; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf27.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731467760; a=rsa-sha256; cv=none; b=6CqeC3rw3gSdsgx4b/21FjmAN8V5bbUUvE5p//WyTabRRQn7c+7x+FGv6re16Mrxf37kPz jXH47TDg9hEbpAJlsKrM8JQp7lmqjE4RCNPo98gOEUHhLtVAxMdif6Y8KLCFFRTNMnfelY zRgCsb9YY8yESc+dznKqDOMrL2y19jA= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=lmPvkwxe; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf27.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731467760; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=lJ7HTuz3Rv2vEaHiKIC8XdXmD+QLTTo8xZwxCH639FI=; b=5KD17x9EFfmuvxOs4hLn3x5kAQ8YJDeQMxgstlj77M8lE0FF2tB20IOW45hsXnVBOr85Zo FGM+gMYShfsAmzebsEF5qJPe7HtLJiHNzhzrhFT+3fRuhGqpQyQZUB4NPoivveaurBEicA a7gFm2hkFw/Y2wa38hO3FI50xAZbcPs= Received: by mail-wr1-f41.google.com with SMTP id ffacd0b85a97d-37d495d217bso5772747f8f.0 for ; Tue, 12 Nov 2024 19:17:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731467822; x=1732072622; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=lJ7HTuz3Rv2vEaHiKIC8XdXmD+QLTTo8xZwxCH639FI=; b=lmPvkwxe2d4rwYQ5M1c5N/xmOMASZHGecni4MJcCCpg4btZx0Fp7oinT4aHaCuublf 80Ee8RmZXu5hXGbbFEoCmQx0K6+BYmqs2q42bm1NMuT7D7dfPVlaBWrbfGujqgotBrMF ts/TMBfWHqol6X0TgiMm+fkmUwTfwNFoHsoDUxbg0xhqTRw75dii26MzY8+OdC1Q/AxJ Rm/OnJkDB8OkDUpp6+dBq0hz5AyJfLImngcricGXWCtrGFRyYuqv2IvuAVPNAbQifEXa wfGo+NPYJmuBQMDwFGX577ORRJeWWSptgkRkbpAirJx7/1GZ7n3YEHmVtb3ZVQ1jfMUE h7ng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731467822; x=1732072622; h=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=lJ7HTuz3Rv2vEaHiKIC8XdXmD+QLTTo8xZwxCH639FI=; b=oAdkRdhZ3F7yLrAApiFurgM8xKoiit856UD/o8Epk4SMiahMjcevnf0zfXu9xntLJG 6qox9xTI++ff/37btBnymNep8d0NS1zCGZe2uBN5coPm20uwtwMdhaNWjzttZ2ZJyhs7 9PeDA4sc4JrQi60jdyw4Nd2ZNCpbyD/KWyuPON8o+Ao/WSvpMkrhFfC1B8O4TGqbWUp2 FVgk0c6e0gajYQm8SBpOrCF0HzV2MEeDsuV9UjSfnT6fCjmWrZQxx1+cjd2JCf4LMAcQ am0nDokT3lVi43mbL+IyC9WhqqxPCPESnM46BG6L2MyHrFKhVODp7+WBE4D6Uk77SEZf PH0g== X-Forwarded-Encrypted: i=1; AJvYcCUhs8q2Hwnl4QOCUXEdNq3yBkJ0It/nbJbIliOO2vle6e27/hhmgBPOIUPS5qUab2x8RqfhSjfjiw==@kvack.org X-Gm-Message-State: AOJu0Yzt2U25foJgGN6yFwSp/iwc28Kx45auQRXiPCCh8jAKZT7FC4ie p5SelNfNiMxR81DggxvxdEXDJzLQhz8Jzyrchhajp4MYKWEmaxfe X-Google-Smtp-Source: AGHT+IGAUWoLA0UyyIuf1kZL1fMAmyZtXXP8DIeO+vUEBI0jC++vATblxM24SA3vDcpC5iFYUHKcmQ== X-Received: by 2002:a5d:64e7:0:b0:37d:4833:38f5 with SMTP id ffacd0b85a97d-381f1872349mr20321029f8f.30.1731467821924; Tue, 12 Nov 2024 19:17:01 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9ee0dc4933sm798476666b.99.2024.11.12.19.16.58 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 12 Nov 2024 19:17:00 -0800 (PST) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v3 3/3] maple_tree: only root node could be deficient Date: Wed, 13 Nov 2024 03:16:16 +0000 Message-Id: <20241113031616.10530-4-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241113031616.10530-1-richard.weiyang@gmail.com> References: <20241113031616.10530-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Queue-Id: 1DF3640009 X-Rspamd-Server: rspam11 X-Stat-Signature: zw697t7bky6x5cxghe3fx83k41miwed6 X-HE-Tag: 1731467779-79649 X-HE-Meta: U2FsdGVkX18pm4u+l6MmaHA7w12D1/f+g9SkKs1yk6ipH6l3xpJGGirM/eahUlGn3Oq+/w971i9pmg8GgeUYttyPts1ToCoFNoPHE8vuWXNZ7VPa4BVfBWC1xCnhuhCNJ26imhpWNykxivqT93EJ+4Y40jJrPmfGCMQOxn6JbJIMlKv7IcQ9n3WRpTWX8ZI+tCitOTV+z5FcbwPpky1kPY5eesXSr4HxROlO+McB7y2/E5BKMq5uB2Mznq0cYEJkxO9RaS10JgmiRhsfvVLlYZg9p6YGsS1he4Q8UDUp/3A+uyTFYze+aViRqi9Mn7VJFp19bnBgG3IjqgbZOtZrS2PZjhXu6HIy7ITFzarnikxQJk6B17t5E+N8pEkaPVrHyGoSQlL9LteQ9NpFK/JpilB97zg6j1jHjKVOf188lYw/40Js8AbKF/wtK/V2RcABkG3c42qSgQiw7hcq52K9hB/KxvCEKn6rdZne4nNSIeR7kOGRqJEk7Sf40k6kDB+SvInGC/rZrhjdMz9cFa7WsPfF+WD/km6iN5rtvpNN01XG0qPO0iUt4yAT8LAq7Y5h8GrbXfS5rO7vpyUMB46phoPS/zDlYVqKkFKne99898vnUAx0klIXnovlsme0CQO+gKyrr3r1Q5/S0v0DuxjdJeoUHOZ0+etr750AatIEams8rQ1gzBGjROIikv6SvMw7c6Do5qbx0XtvM4XHBeP71QEMm6KcFIUttI9j+5nc9AB+0AXROwpNEmIHHBB5qeurGPcjPtuQcBRVnybzKegeugv0IfUN/2hHXBd2PZKMvShPAT/xUFPJszyWRTQiF/hra6nP7HB0r7ezHySbDveWjJIq5VC3x6DcQAOhVaBbNgUZ5Oi6+7uBQiMsBivjYnRZmWxoZmFgUKwVLRsl2WVSnzeEcOftiF+CXRX5dLqnE2GWBoC+GStYGH9uC7b4+I9M8F/6YI0PteUL0/6IJdy 8TvS5NDa WPChKEyZ650dC8BZQZinRk9NsD2MLcRiHUZQeWL4hD3w8RgCPIv25Qn1OlgciScrxfgEkwYmACHv+JaackTAcXEpGsNvTfPRhW86cN/fgWRgt8vziTZy1Scxggqeeu1tWsmb5Lg77H2aTS16MZY0do9j9ioMaDW12enFzqZWiamScrYJuHmoTZVpPVUpV8h6liz0eStNn2N4O/fVFJmBZLywOycCfPYZulnH299Vcy+BQV//3DWYkq44tqLGHTpTIIrsM4jPD/vr802MiDVuUBmtDz4AmM2g/UIwZkS4tBGDC+EEVRuuMPwGynuXFX+nP2rTLi8srRt4NyAp7FhPV1UK+57LV5C4+7FQMtZBXv0KfYEBIpGIBZ8tBfpnXjaXYvi8x2YfkNvaOKPS5OdflirGD2T7qbBwYXtsUPZRY/dtDHlum18mUyR5XCN/CTZjBFUqT62DsvK10eIv5E15K7waMcbuSNoNuIfgqry9nv60YKIZwo51j1+HqnRq9XhbI6LGQ 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: Each level's right most node should have (max == ULONG_MAX). This means current validation skips the right most node on each level. Only the root node may be below the minimum data threshold. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes Reviewed-by: Liam R. Howlett --- v2: adjust the change log --- 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 4f2950a1c38d..667326717f35 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7585,7 +7585,7 @@ void mt_validate(struct maple_tree *mt) MAS_WARN_ON(&mas, mte_dead_node(mas.node)); end = mas_data_end(&mas); if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { + (!mte_is_root(mas.node)))) { pr_err("Invalid size %u of " PTR_FMT "\n", end, mas_mn(&mas)); }