From mboxrd@z Thu Jan 1 00:00:00 1970 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 08DD6D11186 for ; Sun, 3 Nov 2024 23:47:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 356346B008C; Sun, 3 Nov 2024 18:47:15 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 306786B0092; Sun, 3 Nov 2024 18:47:15 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1CDB86B0093; Sun, 3 Nov 2024 18:47:15 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 0022A6B008C for ; Sun, 3 Nov 2024 18:47:14 -0500 (EST) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id AC8521C6D2F for ; Sun, 3 Nov 2024 23:47:14 +0000 (UTC) X-FDA: 82746421632.15.0F43393 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf25.hostedemail.com (Postfix) with ESMTP id 4FB05A0003 for ; Sun, 3 Nov 2024 23:46:50 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BlK1OdM4; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf25.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730677511; a=rsa-sha256; cv=none; b=Hq6mn5ieiRRNJ8sDliVlp90UuM12f201t4mww7XzcTgINIZqUTpFPRH7miwKyJyGEBPI0H lGG7YTN3S/i6HyS3uIrSeZlUZKKHC/PRDLjZpZAVqwVFjVm68ceepAyN13zd2dnOZo4kL6 i6KfYlL6fnABhF/Vn9GQWCNqE3hhNtU= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BlK1OdM4; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf25.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1730677511; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=C9l/ISSXfk7dYBxlp5pXoNOF1dgb4OVUI8Z3x/NknL8=; b=ekq8LAaosYP1GhZjshfNsvwMRSCHJswIu9BYUyOMRHcsMYl6cRzoSzfabRTMh1pxR2ub9K fv4LTfNOxqLY0jgi0/CV8bx8f3Y/Wz3hc0SVUR1troaxiBhxhN8yBKixq8d3I9h9ZwShWC 5TYFzfNgbk6U8qvzI7o71GnaKpNVrn8= Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5c9388a00cfso4497638a12.3 for ; Sun, 03 Nov 2024 15:47:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730677631; x=1731282431; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=C9l/ISSXfk7dYBxlp5pXoNOF1dgb4OVUI8Z3x/NknL8=; b=BlK1OdM4tgX464qu8AF18hCu8tosapf0t/Vx4VsIpoOqmXEj69ey/8/SYir6YGmRde o1iSULNk5nTINxTWrbKu16udZ9qFO+2A4bmpD0iIaNFdQ7o5s0LDbmROBJVTh9zy2lLS pR1SOf/U3qtFhBCuk9ryuKuyj8U6erV3IRzQVa9ChfrbTmPQffCZXQ2P4g9YaOEcZMKI FIkUz6dFPgmpG3lzQyKyRbz15MbJhY70b7I9n6xWkfrXiX37k7NbDuDQh3Qm5EgyOZum Rulk7Sz+LrxKWH7QansF7GQncjnYP403nTHilQJFdrS47D4D/ecY5J3fL+e5gYPAad59 XELQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730677631; x=1731282431; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=C9l/ISSXfk7dYBxlp5pXoNOF1dgb4OVUI8Z3x/NknL8=; b=UIqVwmb4jwh9uFAP5hjivyn7fAf86IXiDb3OX1/NbD3iadcgLY2n5XLfnt17YqOQlE CQZ9FHm7CFQfHHt3gSczYG0ZPjbW3XRBc1ahb3XL3xGJ/cfpmsnPLxoNg2aIqfXiLq0C aFQKu+n/a04pYSZJAoLjmLCuIaukU7NYqYkWhiSlhF8fUhRc3KKEHJhWvjsSSuBmG9Xd 7S5FO3dI6ai0M6kET/Xm978LaYwPqpUwbuMk8ZcRffx7VrRxFQ3QKpg1bdnk1Bqwp0fP tNhHGbT03dPQx+vf/L0/q5vHNj0IXBF1+BM5WsoU4rwJtqLJ1+x/5kPV8hYk5dhLDSQM oNfw== X-Forwarded-Encrypted: i=1; AJvYcCXPGzzmQbhumtbW0pUgXXDcSqwVjEKaqkh2gbWdMHaPRKPDCVKoAciDQqmwwevvmXxbuxOsaYV2Cw==@kvack.org X-Gm-Message-State: AOJu0YxU/2f/p8rqGVXyRozUCwmou8iCTpzY1R6F+OncFsuO42fvKfzl TsxCgzgNIJsOwqIzmPaG3dwdVIPHSqwAw83b2x1X6xhFXDf8mYEU X-Google-Smtp-Source: AGHT+IFeF8krTO+fIrrezQ3p6GdLve7LIK5i0eZIFDqKkgFhaevF4NHHt+Un6GTIULp7m4EWAjKHAg== X-Received: by 2002:a17:907:944f:b0:a9a:825:4c39 with SMTP id a640c23a62f3a-a9de5d00e3emr3325925366b.20.1730677630906; Sun, 03 Nov 2024 15:47:10 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9e565e098asm478736966b.132.2024.11.03.15.47.08 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sun, 03 Nov 2024 15:47:10 -0800 (PST) Date: Sun, 3 Nov 2024 23:47:08 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH 1/4] maple_tree: current split may result in deficient node Message-ID: <20241103234708.opoxwhlk4zagcii5@master> Reply-To: Wei Yang References: <20241020024628.22469-1-richard.weiyang@gmail.com> <20241020024628.22469-2-richard.weiyang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Rspamd-Queue-Id: 4FB05A0003 X-Stat-Signature: tkebjej8r413af1mmk3rkgdx99ck5q3o X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1730677610-341365 X-HE-Meta: U2FsdGVkX1+ICzlTyUrKssnkmZR9bDKNTZ7vpNRrg060HVwB0cLBY5yGJD+o+H77/V3ClxmiV7CqiNF5fRYaBrC4GNyeTHBrEEXPWYMhMn5Sc8CNMBmZFLz+BOK+3SCYactDTDBFh7rNFuj1WfF1jpqdSBeublJiJ5ugkm6bQwveHYCEbWDeyAm1k6ZRrTmUNDhIl9h0F22qU8V4zbScH810pCuNwjYFpWrxthOPkRY1tNwvxfRK6m+ed36VlBq6h80wT7VMYH6DtqyDtYjTwEWW4l0pXJGFl9aL5PgkJVQ3rKVkW8mYHljk1VChRabY+RtHb7pFEFEkaauHTEGlxAL00/Btjn4Lb2c2w49rrlJlhVd+vGF0NliP5oSYVKXypLzHhb8wikNBVtcflqlLPCUS8UbCZ0F2QY/YvEu8JQ+aaGrd+EW+rJHf8vdkwlFYNUIk43XqzmcR1kHu8g/04zQjcsGjwpkRwqzx1AVt6kuaURguwb5TpOR/LTItLggbZTQ6UfhhUohzwMC/37XO/MZy7JR2zmJhU6Hc/XjswpURNpgKCj8zvhyCR9LvYnMI9FbOPLm8dERja8noAwtjbIAPo3Djv3grrYlEIe1Vj9XaSmIO90ipstUPgdCl9nDDbTFlfLeeq/v1I8kQoizLQBu7GbO00JUcHyDbw3/y8kJKAXpVk7BkKFBtbf1CUUUBwR+Osuo28gfKvjPgAHaKQ7ReW6cheJSwQit20dTT8OIBudisSeN1mogQfkQ6FqVSvY9XDXuvU60+I204NdHJv8Dv3g/VeWu6I300xUpCWioDCriFSeH8o5qFdQml0jZ1uouF61GHQNiuEOfhA20Ld+yN1d6S4Wl7zuCLLYA1NH9taqa8tuvhbWMY7dRyYRjsZOtCKGJu/8zviab0A1oGivr7qP96NGaAfutEe7q2Dn4/u5B5EZ5v4CR1xlE+NpFs26jy3xirg1V88vauzJO JkBdnguN OaMVHx0YOjA2ir4OUO6yI8qod80E/+bqMy8KshBj7ObODMPBvVKr5Z0MBt6O+P/RTuLAxUEjdlwZl65LkGbjULZyCAAenEsyZrtsRNuQBRjOPMeb9/MPS6hFzKlYrSNepyhy3x4CquYkhgB0Y8NISvX5ZOQUiwZyyVIcuYu/jyfYkDEg/XfvlXNU2wbQ8llogPEY3W30duOhb0vgVnZLo4c3gfbCYXMzP0UzKen3kAP4p6kMZ7vAVWL4tTxm/6O2IleREu6Q0smpdSus7QyHqY7KZ4OpnJCjw2hJBPspLOba1i8BNeSGebm6aQLDetoqFdYC4ntQZ1PrQzkzKtMjAhxsfb1U7uZb1RcyeFEct2REEKKgHGIGqiBNqDEp7Re6xbWI/QjvesFg3ubUqehx/eX5iv3mCa6/T5TsyXHle+li0PoRU2nxuqrh0b+MMJvIHKnxEmH+lWjTPAyWo5Bef2DV5KlumjwbEWomMaa/qdjmYZ4rTcAAGsQXa/rf1LL30VNXKAN3fRoDCVkYuudsn+AmyudaCJcNMZ+Zomav3YUqLdMPp1mGsqreeoyg23amA6o2cVMorb0OFDSNYWGs9zw61kPM8GFmx4X+AEw+v/De2dnnOTQFoxqOEAaAa4+sysLASKNQCpXhSUlmGssfmVqcuBqLWpikIPfuaHRtRB3X5ZuFdJ4KCaQQsHMh7JhYYwFLRu/lIthBGGaXQmd4bSOdrtw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000004, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Sun, Oct 20, 2024 at 05:55:10PM -0400, Liam R. Howlett wrote: >* Wei Yang [241019 22:46]: >> Current split would result in deficient node in rare case. >> >> For example: >> >> mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE) >> for (count = 0; count < 10; count++) { >> mas_set(&mas, count); >> mas_store(&mas, xa_mk_value(count)); >> } >> >> for (count = 20; count < 39; count++) { >> mas_set(&mas, count); >> mas_store(&mas, xa_mk_value(count)); >> } >> >> for (count = 10; count < 12; count++) { >> mas_set(&mas, count); >> mas_store(&mas, xa_mk_value(count)); >> } >> mt_validate(mt); >> >> The validation would report deficient node. > >I think you can explain it better than this? > >If we fill a left node with the right node being already full, the split >of the left node will result in the new middle node being insufficient. > Thanks, I will put the explanation later. >> >> The reason is we don't leave enough room for the right node. > >The reason is we don't leave enough data for the node on the right of >the split. The node on the right has too much room from what I see? > Too much room? Or too much empty room? I may missed here. >> >> The deficient check is (end < mt_min_slot[]), which means a node must >> have at least (mt_min_slot[] + 1) number of data. The right node's index >> range is [split + 1, b_end], which means the number of data in right >> node is (b_end - (split + 1) + 1) = (b_end - split). >> >> Then the check between the number of data and (mt_min_slot[] + 1) is >> (b_end - split) > (mt_min_slot[] + 1), which leads to >> (b_end - split - 1) > (mt_min_slot[]). > >Don't state the code, it's stated below. Sure, will remote this part. > >I am still concerned about jitter that this patch set may cause. Per my understanding, a jitter is a removal which cause a deficient node which is just created from a split, right? > >> >> Signed-off-by: Wei Yang >> CC: Liam R. Howlett >> CC: Sidhartha Kumar >> CC: Lorenzo Stoakes >> --- >> lib/maple_tree.c | 4 ++-- >> 1 file changed, 2 insertions(+), 2 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 1205a5208cfe..894dc5e9436e 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node, >> * still be sufficient, then increment the split on NULL. >> */ >> if ((split < slot_count - 1) && >> - (b_node->b_end - split) > (mt_min_slots[b_node->type])) >> + (b_node->b_end - split - 1) > (mt_min_slots[b_node->type])) >> split++; >> else >> split--; >> @@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas, >> */ >> while ((split < slot_count - 1) && >> ((bn->pivot[split] - min) < slot_count - 1) && >> - (b_end - split > slot_min)) >> + (b_end - split - 1 > slot_min)) >> split++; >> } >> >> -- >> 2.34.1 >> -- Wei Yang Help you, Help me