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);