From patchwork Fri Oct 18 02:39:43 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13841029 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 52B29D3C544 for ; Fri, 18 Oct 2024 02:40:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 02AD86B0095; Thu, 17 Oct 2024 22:40:14 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F1DD56B0096; Thu, 17 Oct 2024 22:40:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DBD386B0098; Thu, 17 Oct 2024 22:40:13 -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 BA0116B0095 for ; Thu, 17 Oct 2024 22:40:13 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 9127F41798 for ; Fri, 18 Oct 2024 02:40:06 +0000 (UTC) X-FDA: 82685168244.03.0F133F1 Received: from mail-ej1-f41.google.com (mail-ej1-f41.google.com [209.85.218.41]) by imf06.hostedemail.com (Postfix) with ESMTP id 0F53618000A for ; Fri, 18 Oct 2024 02:40:03 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=KSraYkdv; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729219093; a=rsa-sha256; cv=none; b=OisM/cQsPcnL8zT632+auRkl3DZtQfeow1bvyF4uI7fxNVu4BCJSmsiOF0oUbW2udvw4d2 7+0T6Veo14AdX9dAyfLSVqRUXMqO73KnhMp8aznT1o8WpC/pMPDh0gXKQwcbnEcI36VA4s JP3XivuYbUTF4GhObOo+zL37FrFk4qM= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=KSraYkdv; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 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=1729219093; 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=OB4aw/MWjvXDmbK8D7r6VWSH+ZtnOwNKP21OPvmuvq4=; b=7pg2S11eOnHdK6m7PRojoy4cyF53AJd0q/mvnMX1OtZ3MmTR5J77eKwMGSIcWCisydgnOK KZmvK6/yA6aJU/qc9IDyaUkl+bC/n+W7LjCpHT+hMsJAUmSEkXfir3WXjLp+4VQ3Zwp+jH QsjAuj+3By0Ql5gIaL1huZOctZEMFgI= Received: by mail-ej1-f41.google.com with SMTP id a640c23a62f3a-a9a0474e70eso217154666b.0 for ; Thu, 17 Oct 2024 19:40:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729219210; x=1729824010; 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=OB4aw/MWjvXDmbK8D7r6VWSH+ZtnOwNKP21OPvmuvq4=; b=KSraYkdvA9W44n8Ql/nKkmIFYAQ0nfT1CTTZe0QM2bveNkCqoC+7pchb8zJK3eSAPw PqUhBOebQ03VjPhfiu3L7dm7tktpG/i9HAlrFyxKYTWrQhycisk2R+lrKX5ov0U8LuHY szxrEcOCuEjq5jqnUPXfG9fIM+U6cV2vX8gB1Rd8xNpyCgPh0yxVdqYifoKkhJqHtSO4 AoViVL4N08slZLRhy0ZSJb4XmZcchMDVrTgbzZd0eWkOa7gMB8N8/PNJKZDYuV+DhukB HcpoQC6KxueYrGrMEnnmP1FGxu28fTojWjDadBntBr/LVUO+Lq+k76Fm9B8uMrxJpS/r iFew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729219210; x=1729824010; 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=OB4aw/MWjvXDmbK8D7r6VWSH+ZtnOwNKP21OPvmuvq4=; b=MA60FK9UYI9supzxUpGdOQx33XVvSa19XvQOrc47VGXYA8K7SgeQAwP1c4KKD6Tyde ENiqc1UP6n2zmkmwtMrTBGbKjKyJEfRodCOgHgXI/9SFZPcqN9YYg0MLgnp1D3ywJmo9 q8L0huVCg7vExNwlyjtNSel/w4ha7R0PbGfvjsyBq8L8BcuPx0g4H+ikP9x/IEqs+doj GKTfEYDBpFyUBLYoz0MSwii0G2Fgvo9ZKNpdY326thPRsxwYPC1sWuQz/PY55LcmELVJ F+BMnNxwLhRBSSkZ3mtnDL6vRTeMN7Ir79Yy3XdcPv8Ktkj64N+5i5JbRIJlC5amA6RJ /51g== X-Forwarded-Encrypted: i=1; AJvYcCUFoTqzMRDjReSVWBsQYzA0epHGNNe32XPzKujQLShztGIUv7zcYv3zTWfEsIsUT+GW+3nxCKme1Q==@kvack.org X-Gm-Message-State: AOJu0Yw4vWkVVKHvscRTwFpdDhWI5OxdJCMbNGXf0heSBBuRp/N0+CMQ ZrNtRD3YzeR0hP+KFy7R7nMlm4iCO/FPpu9qMrA4rCyK+RQZBNFfExe2dOAJ X-Google-Smtp-Source: AGHT+IGqC29DcQDFewDeXZ+UrsBiayCraGpxIdQo8g83Ep8MgqOaZanImDVTrzY/HsroUXwjn6SyiQ== X-Received: by 2002:a17:907:7f17:b0:a99:742c:5b5 with SMTP id a640c23a62f3a-a9a69a63325mr76706866b.13.1729219210156; Thu, 17 Oct 2024 19:40:10 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a68ae545esm34373566b.67.2024.10.17.19.40.09 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 17 Oct 2024 19:40:09 -0700 (PDT) From: Wei Yang To: Liam.Howlett@oracle.com, akpm@linux-foundation.org Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v3 5/5] maple_tree: add a test checking storing null Date: Fri, 18 Oct 2024 02:39:43 +0000 Message-Id: <20241018023943.13860-6-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241018023943.13860-1-richard.weiyang@gmail.com> References: <20241018023943.13860-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 0F53618000A X-Stat-Signature: fook8oxqk8uozzzhttsw9i535otbr41o X-Rspam-User: X-HE-Tag: 1729219203-574374 X-HE-Meta: U2FsdGVkX18wJC3de1HRa0ql7G3eYN/LRhK05jvyd/eNUeZdxhvmXrRP2OoHv8DLl8Npr1KVbCoWUzJ7OSHBy/IZUe1a20qY3F/wyb3REQ9xn3FBjg35GeoY6eAIexrRebHTF3qlO9cwNgmtMLOOJhuz3Wa+nZCYeGhAApi83mndgJXbBEHQCHA0iKvcD3MYFE0crRkAXCufhPFnN9Ong4ZLQNHZH3rZ8ojPHJPGWfXTuoinoP6+KIRClR8ZBypuS5SGUehIASDVjf37WFKpLtURZ4KmXsty0VpZfHTzl6pZzEx0ILdhqTqwDiYwicYSoHmDqCI2+VbRJFdOEoBfq6HyZQkSUJPYHBWSnEyqAUAIVrc7rGosHAyqgBcU6LKdTuVHitkzV595Mwh8M9baCoqXAF9ELnjql8KTn2NdCW2JS83t/0youKxfrdOJIo1+utnZpqzTa0HyPIEWrpXN8pQBkRoKj97e40UV+L3sG+OPwY7PcPIb3/lhRYKj17gPY07bM0OYafSoTUmy+d6PFEDXOKcNovpJoiOxU8wdqeiE5Q6iJG21hyyGvpL3FQLDSmPhZqI3M+R8DHCrsYyErg84iFG3vlDFTG/QYsp7rST2Rpp2ykGFlHqWX0fmAzp/pmhlWa6hn/sNwOcOgpEJ4Sugv9dwsclW6G9gPGFQJkryk64N7Sc46d/t8S2tBl8KUgFENnt2V93itt0wEHnteVBgdu56ZzHnyN/7600feHogM3m5Q+xx1uUxTwibo7eVp7NW0K8tr9f2iYrRxXYM+2yM2TDdxYcXBUwIDpzuKWk+bn0ImV+EAqxAiWyrxPCy9Ke9GnF1qBoP2kHwSHfMzLhMbJUSCnttH9w3N9lb4AOHdxhNI4oIZP0+gmlF79F+Y/Q3NnGxbHHXFHGKfIhXXZXzUboDhlmW9ZSuSytpKKgFL54oAYEyllzM/xwuBnZkZ6ToUaMyPEGOnOSmMT8 W0fpIKeJ DoWfjcNA2h/k+XAXFyJR8sI3ObdwAljs6tXOwvXKunHIPYNgJ1PE9UZGjzqtwCxMHpMe0nhxHZQ3uPz9+XcToQHIWv2gKck0JaphwpCacrg638HAr+UEDilk14OrKaA4MWw2LBSj0qS6ZEorR4ZRgVGHStX9oTXWDnu6ijKHzdQE8/CAXVP1VTrtbqgMsNhxqsUcpkY6ju+4rbw3jpt2BYbnsvU4zXXdPmDT+CBRpsiEm6RA8ZKVIzv3K3zHB3G351+umC8nTyoUpHjKp64Un1QYgROiB3Z7d5pJ+BMHWTEE3tA1Su9+zDOrgsimL2kZoCuV4tkDpPyQqFABeA2LJJez0aO3BZO1L4glwhNhw7SpH8mWw54R3hVUEgLNMS5LG8WulPF1bBNPCR2pDeHBA/gYAmVxOvXA/5pVBocTzORKzHvLQhwKQeoyaN9dnlYGfPSnoOBXzdIBdUeuhj0uUPEUBIVecrzxxmNtP11PvKxxmT4e5HShTWtv1ndq0mPqjHaLp 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 that, when storing null to am empty tree or a single entry tree it will not result into: * a root node with range [0, ULONG_MAX] set to NULL * a root node with consecutive slot set to NULL Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes --- v3: move test into lib/test_maple_tree.c --- lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 31561e0e1a0d..2ef72f6c6d1b 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1387,6 +1387,92 @@ static noinline void __init check_prev_entry(struct maple_tree *mt) mas_unlock(&mas); } +static noinline void __init check_store_null(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 0, ULONG_MAX); + + /* + * Store NULL at range [0, ULONG_MAX] to an empty tree should result + * in an empty tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, !mtree_empty(mt)); + mas_unlock(&mas); + mtree_destroy(mt); + + /* + * Store NULL at any range to an empty tree should result in an empty + * tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_set_range(&mas, 3, 10); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, !mtree_empty(mt)); + mas_unlock(&mas); + mtree_destroy(mt); + + /* + * Store NULL at range [0, ULONG_MAX] to a single entry tree should + * result in an empty tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_set(&mas, 0); + mas_store_gfp(&mas, &mas, GFP_KERNEL); + mas_set_range(&mas, 0, ULONG_MAX); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, !mtree_empty(mt)); + mas_unlock(&mas); + mtree_destroy(mt); + + /* + * Store NULL at range [0, n] to a single entry tree should + * result in an empty tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_set(&mas, 0); + mas_store_gfp(&mas, &mas, GFP_KERNEL); + mas_set_range(&mas, 0, 5); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, !mtree_empty(mt)); + mas_unlock(&mas); + mtree_destroy(mt); + + /* + * Store NULL at range [m, n] where m > 0 to a single entry tree + * should still be a single entry tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_set(&mas, 0); + mas_store_gfp(&mas, &mas, GFP_KERNEL); + mas_set_range(&mas, 2, 5); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, mtree_empty(mt)); + MT_BUG_ON(mt, xa_is_node(mt->ma_root)); + mas_unlock(&mas); + mtree_destroy(mt); + + /* + * Store NULL at range [0, ULONG_MAX] to a tree with node should + * result in an empty tree + */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mas_lock(&mas); + mas_set_range(&mas, 1, 3); + mas_store_gfp(&mas, &mas, GFP_KERNEL); + MT_BUG_ON(mt, !xa_is_node(mt->ma_root)); + mas_set_range(&mas, 0, ULONG_MAX); + mas_store_gfp(&mas, NULL, GFP_KERNEL); + MT_BUG_ON(mt, !mtree_empty(mt)); + mas_unlock(&mas); + mtree_destroy(mt); +} + static noinline void __init check_root_expand(struct maple_tree *mt) { MA_STATE(mas, mt, 0, 0); @@ -3710,6 +3796,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_store_null(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_root_expand(&tree); mtree_destroy(&tree);