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++; } From patchwork Sun Oct 20 02:46:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842954 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 179F1D3C931 for ; Sun, 20 Oct 2024 02:46:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8AC7B6B0088; Sat, 19 Oct 2024 22:46:43 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 804AB6B0089; Sat, 19 Oct 2024 22:46:43 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6A5356B008A; Sat, 19 Oct 2024 22:46:43 -0400 (EDT) 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 4ADED6B0088 for ; Sat, 19 Oct 2024 22:46:43 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 19CF0C063D for ; Sun, 20 Oct 2024 02:46:28 +0000 (UTC) X-FDA: 82692442182.25.FE001B9 Received: from mail-ed1-f54.google.com (mail-ed1-f54.google.com [209.85.208.54]) by imf24.hostedemail.com (Postfix) with ESMTP id A99E4180003 for ; Sun, 20 Oct 2024 02:46:38 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TlxBQYBS; spf=pass (imf24.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.54 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=1729392326; 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=U0mnBT8IUJmvL49JXkqQtj3dA/3SbCv6VuqCNJaPeIk=; b=cJqrEsx0eOfJ1TJIjKmBmQXY53JFzTBbnwfAWW72i3dl8oeE/JlyjOiIRblgkCt8E+9JlY SvJoOdkAKHV5Jyhuzt/ohrto1eVGrP/L8BGoxLjJzbi1C7I3bk+WtOAVjYZYT7BkpDFkoK XxlD42F3RpyMSEfzXMXZh+7+2dgNUW4= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=TlxBQYBS; spf=pass (imf24.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.54 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729392326; a=rsa-sha256; cv=none; b=Oh0cUvMqFjQ0mxyTwOaA4/bnOhRBm9SKCG99ToCGzzmOyWCxdKMjsoVIsEh7YUT6O4azvm UBt+tw1agcpxdVYZeVjgRC62VSsXwAHv09eRL5JqoJx3xUEf/OOl7bzlwnyIWgfy/PwkKo Y3z+FvTQAJnKu5yj8NN6T+pmM/7ZT3s= Received: by mail-ed1-f54.google.com with SMTP id 4fb4d7f45d1cf-5c903f5bd0eso6036220a12.3 for ; Sat, 19 Oct 2024 19:46:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729392399; x=1729997199; 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=U0mnBT8IUJmvL49JXkqQtj3dA/3SbCv6VuqCNJaPeIk=; b=TlxBQYBSH3MclbTE+XJ3+q9xrh7E09xf/XwJ1YzmT2TATeb+GK95tmGaTs1dbZvPDo 4QibK/MyS+FYBTB5WrPbu0gjujx28tVOASb9k/Ov2wzy1CFFfEVhH9tmrUO28SqdcDnW PBSEKFdosjeRcoSoRXvt2h0slE0oqCqitrYeEWwd2bit7rqYEwJ0ykuehI51MaVkX1X1 RRNz5EJHMR/wmmg3vcKIUfMceKJVidr/ts9OC6qxHR0gxGJJHXBUpF+21zBFmD2oXa/v a40uYpeHmYTjdRE+UFjavyU4mGvF46KBmpPdRSLyKfAsERpCpkq5DNCIGXAMjJeIX2Km +kZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729392399; x=1729997199; 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=U0mnBT8IUJmvL49JXkqQtj3dA/3SbCv6VuqCNJaPeIk=; b=RT68PJVuHXducQ9byJEwMF5vsqDgt3VvtcAB24bkBv5+PJDAIwZzloqeYlKi3be9bB DfE6llWWJAV9bw6vvC+28vvmtjQBWUWrIXZqe/Z5v6YjyN83AP9KWl+g8ZJHNTyEAoFX YhApCYr5fBYwJRbRENboR15z+H7rtVixdU7/v2P5Zia6ivvTbxh3wlLXK0oz1y+19NvT M7+I3rcpizGpINly9ZnKMNRR4TbfcK2s7ib93qPJAtZY+7wwrh7V5finIr7/Vux+1flj ASt/4g59sN+hrCrnp0Tr1qDH/dOqQ+s1XPbEWJTh8KE+R4VSvYLQo1APr4Q+Vr6ZfCEu n0pQ== X-Forwarded-Encrypted: i=1; AJvYcCU9tcbnvAiMzAe4ZQtkthdmahDrW2h07gLplnHteikVfuXd6aH4ZztpbsaGgBivZnCmUkm4gI9Jqg==@kvack.org X-Gm-Message-State: AOJu0YyJ35hHAIYLpxkVQbrJ3bqLtasUpMKgbtwd2fWKspdDtfGfmsIc kyqNHsoaI3fN7jIZVVULMQr2h79LUL5aIgHpmYFpPThqNOeSrnex X-Google-Smtp-Source: AGHT+IHvG1zya74uy6hjY+vRg38pf1ZfmCW3bZ+vkWhsYGYpmfJYXNWnvKvbTCsZ8ohOWg+9Q8V6Ig== X-Received: by 2002:a17:907:3a95:b0:a9a:80f9:d4e0 with SMTP id a640c23a62f3a-a9a80f9d8bamr270518966b.34.1729392399278; Sat, 19 Oct 2024 19:46:39 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a913706b2sm41095466b.121.2024.10.19.19.46.36 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 19:46:37 -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 2/4] maple_tree: add a test check deficient node Date: Sun, 20 Oct 2024 02:46:26 +0000 Message-Id: <20241020024628.22469-3-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-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: A99E4180003 X-Stat-Signature: s6pysnjs54zswaacqf5u73ht5zcqm83m X-HE-Tag: 1729392398-147284 X-HE-Meta: U2FsdGVkX19kNe/yfiOcXqkbWh2gXh2/Qnaj51if6wNL0js0/GZAHlwbIQfbmnKQAIThwEh8SLqCrDRwTExQA622weYeCIOgQN/UbEFjFthTmxmUjiL8m7cieLpZ1jUV+gh7w0mFdhvK2A639MBVaML2s25hOeR4vMLvFWzBMKM/gxqGhAf2X6eeI55Ae9/oK2mkSj9OcxlGu5nruCwfL6LIHI8sUNzAh+dLYIYsQFzesdzQGIAc9TIH0ymZkGN0sOQRxTDFAx5IsHQQvl3SANVzVXww/tBvJcsvsPn9as0wN52IwOdN4vlU2Bw7VUsnuCxwcuyLyoQnw2gOJnj7ka1dw95+S9fRWClYk1/iFWtINxY38tFNBQ6bvOKJEixH3Wp3ZtiK+lI/gzTXiDaegeueT5rnCzruyFlI5H5LCNDH53SgsfRC+h2rs2g5vzMJ9HHVwiSsNq3SAkdJ43wXqkCPszwkXAmh2N35yGLRESUgyFrosfprFL1lGIEdFJFPDLKSQtT90lSxyOjUJd8kbf8FFU8RyEuX7nm5PL9RDO7mVxAJU3S9BhyLentXXlvRPN73K4QWHuVqetOEG4fKze7QMRXl1snGnK4roQRBQncwuDo4OgiqhOsM0ql3ErSfR8BOmG7ohGcqQxUNf5o5dJLCbXo7yR3OOZi0SIGFEJnacgUHdNYjo44jLMX92AsFpd0w/5R9hAQnaymFP5Iud3GW2kFdhlJBVoUbPAgf3CrtbOpdQuJ//kLbulzLpGWIRQEGFa+JtqinVjuXJO4ATss5+awD8AP5Q1kNwW2rUFqrdo87CpE8G0tuXlctyiFrfI4GjI8WCi5VDGitBKoxjraojWTbUoJc1J01NLRFC1tT3pl4f3WX+n/OXb+aHgLhvUsKI/Iz9KmvfD/qEmijmdKYltju0fZBkGjfd3/1FitY4xg/N6eB2viM5gaNgl9LqdpGjVS8dVFf64jb76e EZRmaivy F/SCUq4a6FRcmZE70888Ewq60X2Wiwe/TFFxMpKhJGXtpo05CYmJj24b9DjJb1UdD0+YzO+QIprAmynAcAyYLgCI5mGoP56pwaNHxrSaDWm1V5IR5pFgF852orq7GpqNaNgVbMRuYMseN1LsNXXnyLEGNk7v6dhjIAx49iq6YBk5HBhr4FvSMsjDGWmaepUrAGmVvwPSkIiKJ7FHPmOXZBd6HxnXy0Xrlh/vFAHqNyp63jDuye5GFlCxAi8ywFY1FVsf3qIo8NhSk3vAFl3zclEevuWtMCo/vG6AcgiBgYzDWDCtC5qlSzPZO3af+IBkp+NhNIrRKGj3dcUx22cceeAKzyyhqxf8U4ynsn2LKYUmel9T1Ls9+CEwuQ+lJ5ufAiL2XeLDbZpi+CjPPuB+MdNqYJ7UYP3xbNJ4t6kIVjsiGxjFr69aMUzHK68e/16QUJ+or+sl7sayO1uEtOxVg4ZVoAPY4vFf77rOv9U4K0SO09ha1exKAnmHNMGdZPMzUmtTs 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. Another simple way to trigger this is to inserting from 0 to 16 till the first split happens. The new right node is deficient. But current validation skip the right node. This will be fixed in next patch. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- 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 2ef72f6c6d1b..7cd38c884869 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; @@ -3804,6 +3828,10 @@ static int __init maple_tree_seed(void) check_root_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_deficient_node(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); From patchwork Sun Oct 20 02:46:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842955 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 CAD5DD3C927 for ; Sun, 20 Oct 2024 02:46:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4AC8F6B0089; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 45D8D6B008C; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 286F66B0092; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) 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 065D56B0089 for ; Sat, 19 Oct 2024 22:46:46 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 38150120349 for ; Sun, 20 Oct 2024 02:46:33 +0000 (UTC) X-FDA: 82692442350.26.93CE1AA Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf05.hostedemail.com (Postfix) with ESMTP id 29DD5100005 for ; Sun, 20 Oct 2024 02:46:18 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=g38MJfAp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729392283; a=rsa-sha256; cv=none; b=6hKHKHodtMW9jxMpcLj+f1y2R5tmsw3CFnkf1DQjoCuNZIYUPSufvkTEnemJ1G1Hefj8mQ yK0Z4Ghhfa6+lMXtTMwFWfOrboRWkeA/Qz14uxDPelzLhKiDIre/Xt3rtQ6BFQAlhaSCYZ n5/7NcRtmJRrdkDc0VPeehZhlYR7j9M= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=g38MJfAp; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 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=1729392283; 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=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=w2Czo2WLSEk7CaIld7JKmGh5vIqrIFIPXvnO7KiDvTViD4jJdmvtdIePWmi5nidfUBe7pF 3sz021NBHBLTIvaPDiUFm7aWmgGtU1wYaCwA53IXBZe4jkFurDYuFahN0uYt45oft9awd6 1btHc+miFOq3ibPD4CvzqqPY24IDjLk= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5c9693dc739so4319201a12.3 for ; Sat, 19 Oct 2024 19:46:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729392402; x=1729997202; 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=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=g38MJfApkTUxMV60aV0R3l3x/sABz/hY7zRr98uEGPm/oiZpGv0E1fqC/u/KCecPKc qsagwLMhy1dX4vIooRZ1uw59ywvGzn5ldCj+Zjh0VZTJw4tlo6PAR0ekcMwXT9NnDrtt 0dpYIQdfca+qqsKlkPEGxnrRr0uPINosrZxeuiN/AbJe7JpFPiq0tVqx8eM+SOrr6BL0 0WrSnW273AaQMVmWE6o7RPxrBAvjw0LxoCD4wn81Jys2QipmxLfiOTT2o1+I8PCM2/2h NZAhTfTFUqKVxrc4HSYPif0Vvau1zxxqCpARBEBHrQ2VOP403iolEAPWDgRcilHTfw/s 0Rrg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729392402; x=1729997202; 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=wDYhY81SHGesAdPbefqYjjjvSq6qJTQTX1e0bGodZLs=; b=Rl8ZKuexhPOSi5Olcez+DNjk1EzY7cezds027TdSU6t5fSJbkyKASfm19Fnk9q0aTm XrtvdYniOQpCtdNIhJn45rh/dFOjRipqPLxFkX3H25leOxBctzwNlbZK+G5jfu2ncY8W PQ7LiLhPSRWi6dqHped0sx6ZYcUJzwGoxk4+uirHPD3sZnbIJzBeiWvY+qqpMcB84wua gLJJZJX2YuiBExVTef0yOz6cAadX98XFRfukVCyIR0QhQH51x/T01xNvCew0bAqChy7X MGPO8DPNURzPDq0o1R2CVP2F+WGw4UQzr72UmNrMZxVCgyZbEvJ3IvMTFrsQ/wJdB0N5 ZLuw== X-Forwarded-Encrypted: i=1; AJvYcCUJ4rH7A10YoAS5IZKsrNd5dHX/1qTUpQpCu5dLWXUP6JSvSShF7JahXD/lx9RVhQSqKTuuXWEoGg==@kvack.org X-Gm-Message-State: AOJu0YyyjlihVOAGIHiRR0MW1lZ48syUcBiW2E6k+P4Xb3bWWUxwC/8g xMeRpv2M3zXMXJBfvYmo/nJiH1ZoibrOdo3CxAAj4dRK8BAgdp30 X-Google-Smtp-Source: AGHT+IG9TU6YFWoe8nI1KvqfcEts+0UB9XrQ+D3X09pG1eButUKOg+cLAxSGLd/JbnJTIbIDRMcy9A== X-Received: by 2002:a05:6402:13d6:b0:5c9:218d:7071 with SMTP id 4fb4d7f45d1cf-5ca0ac71049mr6497448a12.20.1729392402408; Sat, 19 Oct 2024 19:46:42 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cb66a6d798sm433292a12.50.2024.10.19.19.46.39 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 19:46:40 -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 3/4] maple_tree: use the correct min to calculate split Date: Sun, 20 Oct 2024 02:46:27 +0000 Message-Id: <20241020024628.22469-4-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-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 29DD5100005 X-Stat-Signature: zmxi3e3z7amrzzasse6p3mt8b4s664j6 X-Rspam-User: X-HE-Tag: 1729392378-520325 X-HE-Meta: U2FsdGVkX1/aErq6S322vozNdkuEOA8nF2y6HXQXTEYY1p9dIrln49PXnqvM5cL5yxe4HP1GypxZlaxabLwgjoyZJq9F7KE6+hoLcUc29P8z0ovkgB+RlcYWzizoNTR8pH5MYETjfHUJh8zZbrJbgGDmpWlqTWDQkhojNLjLuJlrk4kmxB/rjCcEHoFJAKvatbHFTBptsvghAYOQhwnhrBlgM3iIiaRQKtcKhcvKJAF95qEqxgDqx+Kyaru9DQf6TvRLeTM5wVHLBLQzBau8U7awrJNbA6tMa6dz50jJafAHiR9QcIpnIGhof3krz62D3KnLfsd7cMyT5LWq+A36+hIVRS5Mw9yR7k7Wzv9Td7e2hLN1u3qXClaOQ2iCEM9pCFxDwF5LsB5fE/9JJZueDhK9OX+xKEf1U/IzO0UZVmCCWsaZSmPCkvGeYE8Cjhsj85P/kSHPS9v3ERbv4cTZAQGf/sA8unN6MfK9Jr6CtHOUSKdesNv2ArtWj2zcZYr1SjhTpyyAx/WU5D85NccwT0RSN0RlG3U9DAI75qVB2SvWlBpVpUFm7Ez7v+Vhw1G27Q+esWEu4GSE30TbMITxtnDR5VbmVHmts4oDaNQS6FZBHkHEHt6fUQ2Fk+U7dTD46BRA1SBAIJAiD8gtPPu6Cko+cq6q+Qy4iZoD+mvsmWvIpS3D+Hf4dPVxX43ARC8ybwbOZmhyRDJYRDnePZ5YU/XmX1RU2MRlLDLeidudSWpvAEI684b44yEhjtDNV0dBRs8KCbdiM9ufdAT749axCxfVoltOgT5acEu4NHWMIu//CtFt1AQXT3wn0ThR9GVSIfzb9puyK/XQVAgy8LjtXFtg2f+k7NIEknhroASUw4pIXJ7Q6YaGeWH8UN2qBAJqjk5ASD8z8JuPcSYxXxR//Ik6w5oYBGqLZnoVFuT74n9+aziN/5bkZxN9FkIPnTWpE0SEeNqv+D18otu2Lck bdzzX2nX FjN051JUe2kQ9AWmVZ3gK1iJRYeHvJ3fr4/7sUqwd0jcn5M40/obGTo8thfrZ0tq/jnbTYXOf0ce6MtE8DJFcaUIMFEcYRHr9tMKvdeVSv9OPxiI35vrddpyhHCoMZXB+kc+sWakONKEtGIe5BYU57Dcqt+XoE6zHCV1Y+hZU9es9kydif7/E7EyRGwcYuxzUKgCaefE64kYaf35l69f8pH0CW2aaeKPGTUXhNp5bkhx/mbUCti5+Zut49rHGk92ovm2EfBO25aYbd2pE7NhXGQoxRcxuxLH0ZJpPyD3mFCS0mm1XdxtV/b2Lc3icZuUST01aySBnjOUdDGhr2kTbY1CCmOMfktXjvrn1WTsvpBMab/ADgerhF04Asvz1UwhP69NAFfAS7TFymbAMuW6re+IbxFhpWM9KOrHVxqlcipL19rkErqlBiGKMmdyk7/P0e+gCIvGymVfRiouaVmSJVXupCkmvzLuJjCXe2KvdA6MmiPWB8DGuInWSrV27Oekg9XoH 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: The check in mab_calc_split() is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min. First we may encounter a pivot[split] smaller than min. For example: mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min). Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect. Since we are now calculating the split of mas->node, we should use the mas->min instead of prev_l_mas.min. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- 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 894dc5e9436e..c2d4b188646c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3357,7 +3357,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, mas->min); mast_split_data(&mast, mas, split); /* * Usually correct, mab_mas_cp in the above call overwrites From patchwork Sun Oct 20 02:46:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842956 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 21B40D3C927 for ; Sun, 20 Oct 2024 02:46:50 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6A6676B0092; Sat, 19 Oct 2024 22:46:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 630FC6B0093; Sat, 19 Oct 2024 22:46:49 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4AA956B0095; Sat, 19 Oct 2024 22:46:49 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 2394C6B0092 for ; Sat, 19 Oct 2024 22:46:49 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 0003A4090D for ; Sun, 20 Oct 2024 02:46:40 +0000 (UTC) X-FDA: 82692442518.21.4CA18A5 Received: from mail-ej1-f41.google.com (mail-ej1-f41.google.com [209.85.218.41]) by imf02.hostedemail.com (Postfix) with ESMTP id 3C38F80009 for ; Sun, 20 Oct 2024 02:46:22 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=jK1P2MW7; spf=pass (imf02.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 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=1729392258; 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=NEPlZtP+6HEZ7aeAcDKAIgjcSGU62mJCiKqbJmO7MfM=; b=tX3RcjMyLwi0mKE096rf5X7F9xwooIAgtsPAX4Qj6r9QTqwNSjLS3ZFTLB8iQt/ZRqygwF Ejvdg8P/4McjUbd/9AfOVz2eKVDE55UsmPqLVwkhd2p7xD33k4/i34+oO53ty4ZsyPCXmG DZujnpyVdkI0Ou6PhQg0S/lrMiz1sHE= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729392258; a=rsa-sha256; cv=none; b=6Gm1IG8wi9TxiyvCehC3XD/eKc1ZjZX00Q7CAJWMCNCOE5joMHaB8KQhhy6QNf9XVPowPY XH8SkWY3UBtgdkDdjeo0IYcF5FpIlUqJfksIZlNB/8iy7+HeMJuj4/bK7wtkp5r5Z81l6e FNvGXE3bhPsA4K6MUPef0ZhxRN01m+k= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=jK1P2MW7; spf=pass (imf02.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f41.google.com with SMTP id a640c23a62f3a-a9a3dc089d8so440531266b.3 for ; Sat, 19 Oct 2024 19:46:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729392405; x=1729997205; 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=NEPlZtP+6HEZ7aeAcDKAIgjcSGU62mJCiKqbJmO7MfM=; b=jK1P2MW7K1sX7fzJ8/p+qpA48AGcnCjeM9Q+Wbtav2WC/q45KLXCcLSDTjRiqT+5E5 JFw9grdxOeAqgJ/45pdjjv+toWG3cK89yXVev8Xezyjc1ol/3a+hw1r7MLYinj29DI6T t8eLNeuMybBtA671KIm/m8Y4Xo1DUv70T0WM90WMxUBWZXwjKYvGgRpC2+L63KDawY1C SuQyGzwibDn6DIhEM+ydRZJac4VJMpzTpk8SOoPm8Dn6hRFzLEz3tsPxxQRWcH3/y8cu wLeXAYGesSs8qizL0AodzD4qTDTE8RmlIgk8XFRlbYtKTa5eqQTivSjPmagd3K6KUYcT SrNg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729392405; x=1729997205; 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=NEPlZtP+6HEZ7aeAcDKAIgjcSGU62mJCiKqbJmO7MfM=; b=EselUSUCDmeFIYyoiQmSdrqYuCt52MFuzFTd9e3mWZedx7zUuiXAyrqGHrgQa23s4a NRVU/mAguC+seKgO+DJ+E2u0MHw/hbfYzOTZRCXwD4VpzWXidkJoe3hYQtGHDg2XQS7k eVaUuQjEtdHl61bov0cZ+hB4qyKkXgUBV6XxXUgaejXBrFqmOQznGxdB1SqwQyNYIrKS Ip1R2nyndG4kxWh4AEEdkjsGQUO6Tk+F1fqvqFqEhbxSEBPwvVnPU/XL1jis8V4f/UAE kshTPbvarBNxRpGl5xPabewnFxJdlwhkb5qqJtGqKmmcXJm3eUm+O+4AjtlOZVYTlOPL tKzw== X-Forwarded-Encrypted: i=1; AJvYcCX0vnN7ePkFd4wthy8bfXMM5qlZRx1Mk22bW/WwihTBEc9B0xQs59aJeL1wVuJAtdHGEPjmc/IzJQ==@kvack.org X-Gm-Message-State: AOJu0YwElDQhOgZqvdVBcQuUMFjPTk8eIB1msNRTeaANw4tCv6jio7/X Lm2W9Fn0myyMq1rJq+RmKvQ+B3KtLjglXZZ6sruisAzxic+/2dLY X-Google-Smtp-Source: AGHT+IH2ROK2/CkAp25C/PTnE60KevPEY93Eqzgm8b0Ypac8xM9DHO7Hctt4iZ7ZK8taGHHXVXZCng== X-Received: by 2002:a17:907:86a5:b0:a99:77f0:51f7 with SMTP id a640c23a62f3a-a9a69ca375amr629427866b.61.1729392405464; Sat, 19 Oct 2024 19:46:45 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a912d660esm41905366b.34.2024.10.19.19.46.42 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 19:46:43 -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 4/4] maple_tree: only root node could be deficient Date: Sun, 20 Oct 2024 02:46:28 +0000 Message-Id: <20241020024628.22469-5-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-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 3C38F80009 X-Stat-Signature: jhzs5c5er3ucgabk4yw93ao5ufkqfybf X-HE-Tag: 1729392382-659555 X-HE-Meta: U2FsdGVkX1/yxDWHKW9kmq+ZfvN+Sk/eJEQHeY7TVGlLY7/DQTD9WG3xBwP9u9iYWR4jw33D1vWwg5mj+7LkL8/4kH6qcIn4MmhPVhLMxsK6ja0Xn3I5hS9RSZIotEyQERknO795dVKprGs682Hdiy3f+dTTRfeksiY2aDBi8tIo8Ki29DxEsuSCjj5C69iWAxDwB0WQnGPgq3zSfmtPQSsA/6jjFTjBRPkLGZfDvtxhlzmvMH0exu2eSMwDu/8qE/XVsi39vFAL+dJ3M8jqOEiCaOdKEcnsmasNlbzTVY5azHMN13gsGJYWNQN5rShFIWNLviFvVBAXDVyH42NYQRxXgw9jI325oagexSzg9HzIS+aQLChU8oSkT21hotleUvMryw9L15ANgG/ZW6x48K7V+flW9K4sdtewnTeWQeRZGFY7TWo8tmH80HAy7n2+bU6m38vx98CPGKzayn1Rp87RX8jMtntrtsYN9yWFpsUBR8WFdPk7P2qLJz+JrtvH+9TSVOem0vn3kCALZ1O+jiARfpR1jsAQ/Gy5JF1QQXejTJHO21qMSZWiA16ztcSc6oY5Q0Wy/ff7HZXc3hAuameZRX15hv0HWjNQ/WD/VMbA3g/fpQY7b8mNKmbKFsA/pkHH0E/40/+YSzzqzqibpRSZlXY7rw2YFDxHSdyzQUY32cr3cj13G5QyQq38kFRobrD3va/Bc2oYSvV4oY5E9Wp4VuAoNyipHVpg+/RmNjMTM5UqH8fBHAzgplcMP6fGeZf1U2v6+YtkpCqlvgNuS+hWtn5ch/+tNK4qrMwAC/W0MXWXX1c2bEh9kAePm2Zv22KIL8NmgN24itNhw4Oq6hSSBCBi9G9P7Zfl6q5OBTAQQ+Oo6jPcRSS8SMDti/ns1GnkaW5gUWAY4wtnV3I3NJRxVkF0arKbMbbCnbokfVl6t/7k/44eT0ue9n2R9y4vWwR8di879UDdSeneiQr 0ajZTDgQ SxS+iixHK0l2cSYjAWpPaJfleSf70AkiE5fUqU6T6jOCitcKRyNRwCyaJATc0eXDoVgZddqNrn2RV5JdF/UrSGV5nFkLtiiiwEje4bk15mlhGNYWAesk3yAg0hQ9kAOFbuEOLU+jnUgzHiN15C0bOEBjA5Bd2Y56afkN657RZySSo0z/5OP7O2neRSnByl0PtiIj3d9BkeFQxEPhlqAujTwmYZ1CSberfDT6Ylk5jqf0i0u0btpVVSq6xNsb82eoz6Uwd5V2ONLY76lA6m6dbX5l+bq51Dahj89L/ANmUC/s9T9j6Le4GVDNMxwlHM34Qd8xfwrLcWiT5V6LE+UAgaV3bCGJySj5nn8aHJM0pZKKfE9iX817bmsayuuVEXYbv9srHytwc9NYClr56AVDoqr/Uenx+RKpV5twUsKrifXg4nJc2UvrnZtZsKTcE/x92HkmR37WEdWLyn63jFwYKv5VSIK5urwwLvRZr61HOJZyYFnDhuWynUKQEIu0XVNcDTmna 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 could have (max == ULONG_MAX). Only root node could be deficient. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- 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 c2d4b188646c..e6b2ab5e27b0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7610,7 +7610,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 %p\n", end, mas_mn(&mas)); }