From patchwork Sun Oct 20 02:46:25 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842953 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 34ED3D3C931 for ; Sun, 20 Oct 2024 02:46:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8539A6B0083; Sat, 19 Oct 2024 22:46:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 803B86B0088; Sat, 19 Oct 2024 22:46:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6A5396B0089; Sat, 19 Oct 2024 22:46:40 -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 49B406B0083 for ; Sat, 19 Oct 2024 22:46:40 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id DFD8840896 for ; Sun, 20 Oct 2024 02:46:31 +0000 (UTC) X-FDA: 82692442224.05.7F24FDE Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf19.hostedemail.com (Postfix) with ESMTP id C8D271A0003 for ; Sun, 20 Oct 2024 02:46:21 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BFE4jyrd; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.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=1729392362; a=rsa-sha256; cv=none; b=LSqduhyDwZCTbKHhaJIARLUKkeLBco9PyFXeRWCqIWTxAZDnjCSeaxETVKrckaMQHoAHDv X3xon+zIWAuNAKaQZl6Gx/djYF93BHKVvJVedsdGLT7sXgNinSNNOyK81C0dRmKGX3cENs WPyfSR0yAcPQp5d3jJh9cY16QUXApa0= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=BFE4jyrd; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.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=1729392362; 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=ki0vfcVMuL/TwPb9lptZcTrOX94I9BNvwasGjFBkB0g=; b=aW9m645weMzymmaT3U6rj87b8nZxFK5jY2yy9zJaUIq7mG7N2HrIfkVHw/ZcPHwiD6YsTD b50Ud5yUzUNvHNp5r0EauCn/WOts7NAAN08vNK2CI2gkX5DXoiwzbcsZpOAvqkhiRh8gUl xVBHaiunAFhGwsV7L0hHXVAIEx06Rgs= Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5c9362c26d8so7402056a12.1 for ; Sat, 19 Oct 2024 19:46:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729392396; x=1729997196; 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=ki0vfcVMuL/TwPb9lptZcTrOX94I9BNvwasGjFBkB0g=; b=BFE4jyrdzhVHIDhbck3cEy0xBS0en7jHhYUQ73ZqN2zdk7sVpMQh0B3AeovMF02QGf ml314OA7uLoLZF+AzGZrJANJjjjwkw7fgQBX3/+lMIgDNygIIJ6Y68JOyYuRHAVVi4eh h8R1DXJ9DNC8fi+I1nFFwbDTzOD2d9Xrhz9w/B124Mdti1s7MrwQrtzxeUsqNPQOWk0F +Gb/zu1NXJWgM+4cGHP6WsFT74ZI0TYQu87KiPBG6umOAZehOp/kgUuvvfb2vHTcW1WI ZgOdx7ueScB5e38tgdPFLC668zIVpQ5fY1kmFDBz/t7TWvO3HvPfe6DxsHvDZzChgnA6 DGxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729392396; x=1729997196; 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=ki0vfcVMuL/TwPb9lptZcTrOX94I9BNvwasGjFBkB0g=; b=GT67AKbFHE3kgIlWmNCmpV+Fd1AqN0aErS2xzmaRCb4TzzBHV5RcjHEkweU+hUY+/u qwbRjXCJnM3EhQerJfWMUGb5HMApj2YKdKPsbjQywoO3hv5r1+rojvr1Don+sKQpJoT/ oqFVlyWh6U94Da7dwMjvo85yKYSm84/eAnwy8H3YndV4b0K5J1XYz+mmP3eRf1nXw95m sxxak9DEQTDzeeVZibMzEJfNFxpvesty92ILCx5VYclYyxjSEz/7IkFll49CamsB6WV5 OOe7e4hXFZ0ng7YXbFDEAzcGnAgu8ykW8s3EIyn5vR3YIB/+2qTc7HWprHSmzQ53YX7M b5Mw== X-Forwarded-Encrypted: i=1; AJvYcCXWSopIl65+7U97Sct8CIfpZnqppymiLBK/NIxE3bG6pJxnWeIc1vhRySfsovyNQoX3EG6AlLdTZg==@kvack.org X-Gm-Message-State: AOJu0Yy3CsLkvW7yr3ccgqSxBmqW7dn2/YEgTfH1TNkXX3R8ytehEI1R Vmp3q0yIX1/dNz8K2wjXMQbI+AME8rS63+rsMoAMWW5xLBHSZCfs X-Google-Smtp-Source: AGHT+IEXQrNPwyxryCuq+0ksyO4cHEYijOuRBp18+F0j7os/BLE73E3mb+3CA6T6N4Z0zAKDJXJX4Q== X-Received: by 2002:a05:6402:2552:b0:5ca:18c9:f382 with SMTP id 4fb4d7f45d1cf-5ca18c9f948mr2373179a12.3.1729392396114; Sat, 19 Oct 2024 19:46:36 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cb6696b500sm420201a12.13.2024.10.19.19.46.33 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 19:46:34 -0700 (PDT) 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 1/4] maple_tree: current split may result in deficient node Date: Sun, 20 Oct 2024 02:46:25 +0000 Message-Id: <20241020024628.22469-2-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241020024628.22469-1-richard.weiyang@gmail.com> References: <20241020024628.22469-1-richard.weiyang@gmail.com> X-Rspam-User: X-Stat-Signature: 8b911y5a3kmd3kxbtk16x8fkrn78peg8 X-Rspamd-Queue-Id: C8D271A0003 X-Rspamd-Server: rspam02 X-HE-Tag: 1729392381-662904 X-HE-Meta: U2FsdGVkX18/2xCuqcyeZQKiHFYoYTXhTSzBcja6DGf0ntX4JQK8q6iGLtUg1vBmsrk9rYuhzryzLMjm7ZMXJYNd9rtsqMml8Sq9lVKudPEFbG2Gc4gPTvwbca1/X96cnj6TmsgegaARf6EoucrqpLc3NimD3iZYvji/qPbbDzuGFpqb6oXd5ein6SXEZsVlgcIt+ooSJqeJimnjZXQCa3cB22H++ao5i/FMMMP+HLjc4B6RpY0Ysvg4t4CFtNMtacf7Otk6aOJv9tK/MfGScJwU3H+Z4kIfZSYmr67UA6+oDqxfyZmNLp9fP32jc+yPsvMhfv+lUbTGz83resRG42a//dhzZ6RsSS6DedpHs4yXbbLt9TLgYstMYMyV4DCAsEgm8D+2gFrTp+YXnYFTcTedADYJkMsntoQXE6l4JiX+hw/nMrWYNHjSt88bnhQNdZgOrYN9KIB13UuRyeClyG5Cd2xGQjG9XC0bOZKRLK4IqGJ8pvhuTVtsUuSdcpYd10j0SRo+m3wu8auWgkLo49DtWOIKPXX/UFg6jVV2uhAd9OoYI7Oj7z+NUp0awWz3O5qa5tWK+BQaQaXoO2X0s82KGen10Rxl76Cs2x610qG6VowgISscaz3KRKdjU2wagsLqZEVtRxx5dWdP9AJytoFDt401v4FWxlEHS4YhDxfyxTPoSYKu1ghpyKMcZnS0bWt5/e62nUQP3kfyBsR88rOzmpBZYuDfJNonjJ2sI6kjptW7GB/K1V6NNUkTW13g+IpSWNlXZm1Zn61CyNZ3IwzAocdbvNKHRVMe3r65Nu6dkhgUzC3y8Mb94YiVoqZm7dzAETvnWdmK9cTZjocFfpD1CRq+LI7+ZrMP8KXWPehbVjBkSy/DCP0ijsfWImHRZbwz05VNEg1RoR0HFdEuMMlNxlcfNpAuI3bLQnZU5FrkTebk9zdwNHxOL4p6VTgB6tiFerkxl5sdz0bp7/D Ql3lttPq zdl2oxWpWcamRaZonEhZ/AgX6mGkhha8B/A2k5WCNvY/E7XlTN8HB64k5iOZdoaN/kTctx+M35wCWSlpP8HYcX0q67RSQHINTv6UI+KBBy2oA/9gexagfoEtGEAjIAQLDl+OlxPxpOa01vYW5JhpfIrd8OKIGgyudjkW4Dm0srFWMmsGQ0MUYYDpFQD8DGnn/ikPSsqYCMsv/gmZcd4bW3pOfKsBVaJPV99aMCOp2U02CSPp+4qHLTQekY6r25Y0RrOwjQH0SThoKZhuPAjY9ltGoCrgL0Dkw/ze+sD/6L1mADqGMAaySBF2JKX5C1QiZIRhieMm4JfSs7xyMaSDAVWD/JIWdlO0RJCIyJvzX6B6a+j2g0uiwmteSOZnBLhQOAUJYo9XuAZTCO20++x/mejhln1sEzHzYZC46btWEwM3DvdRvH2FWB+kqu+SL3WVaSeee1HsS7TSHIgtrcRqCD6Qk4Mj7L8tK+9Ei23JYw71ZbTIm1xhIYLT2LdYhBhiuYYDU X-Bogosity: Ham, tests=bogofilter, spamicity=0.000007, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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. The reason is we don't leave enough room for the right node. 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[]). 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++; }