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