From patchwork Sat Oct 19 02:37:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842544 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 625B8D3E1A8 for ; Sat, 19 Oct 2024 02:37:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CA82C6B00A5; Fri, 18 Oct 2024 22:37:42 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C31CC6B00A6; Fri, 18 Oct 2024 22:37:42 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A34686B00A7; Fri, 18 Oct 2024 22:37:42 -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 7C2166B00A5 for ; Fri, 18 Oct 2024 22:37:42 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id B5C38120523 for ; Sat, 19 Oct 2024 02:37:30 +0000 (UTC) X-FDA: 82688790618.13.4574B22 Received: from mail-ej1-f53.google.com (mail-ej1-f53.google.com [209.85.218.53]) by imf19.hostedemail.com (Postfix) with ESMTP id C64071A0003 for ; Sat, 19 Oct 2024 02:37:25 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dNbs1Utk; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.53 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=1729305386; 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=ij///pLm++5T5nUb7YBgFMSaSJgWvaZ/9GyrSRxF50yzawklePzyr2Kmk098t+p9RKP+L/ 3C+/KjY2pBeEMu4IDdGWb3AlCvQwCcvAdjyH1qcnMHwzyaXAvYh7W+YwaL2D1Sb0JNW7E6 9csYbcRsPZyiT8BMVWmeq1KpDljHlcs= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=dNbs1Utk; spf=pass (imf19.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.53 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=1729305386; a=rsa-sha256; cv=none; b=2B9LxhYopWjN8wk5eQdiFKGNhflKB3XWOoBlWvuHCt0WmC1G1TEXNdqmlW4AA9senWpswm DEvwtXsqOBhtsLhs/4gXveCFotNWO0Hg7p12BQ7Fu4T638AS8RAmH4EZS3VuKpQc42E+Ng uJTeMcT7e7j3A+lnGbk681D7cYdbMIA= Received: by mail-ej1-f53.google.com with SMTP id a640c23a62f3a-a99f646ff1bso327957966b.2 for ; Fri, 18 Oct 2024 19:37:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729305459; x=1729910259; 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=dNbs1Utkg+dootsgO/7nFvLOGh4D5fDKbGPPBF3kPZhA27Dh1AwYVy/z0qDL3s9ygu kXAeYPu7/OiKZDKRIauyJtc1qJqczPA/E98ZLbKC2VsFYU2nfTTdKrCy1K5GfJrmNgMz 6+bk5vdJWjZ+gYX0AtkPRgBWs0IJA2zqkKSZFL+uJ5nv/pyE8fIhuME5UwDPf2BxBLOt qKCk7n1S0acyVzcdAWz/Xde7c6PiLSAYgUo1QeKNs8Hcp+hdmTXwvE+Oc7lg8mRxHm3p yjdz1490+rf9hDqS65KjiVuStyuYDbZBUpMRDHMNyAqbuOIrwyR+1GdWGkt6Gj54/N5Y wZDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729305459; x=1729910259; 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=AMntgDGjV+kxCamNBZPf5fJzezb6FT+BTnGgiIkDMl7sYOyTXCVpQtKPR7rBt6Ufk9 LtdpFgeM05p9abkOqilDsb9qrg9tY6sj29/Dzmaev9GnVSWevLaIKwW6TnHT47ZDyhvV dn9+exvCl+PFFBW5RRU9YTFy4y8Yjb51cM573xqXmpoqT/K+/3lwQtlxP+5umEIlB3+t e4cvdb4bQLa5K2CwgbjEFtQmQswjk6TLZGPei2fWkrpCub9vsyurHfcZqVUp/QTeA4GL C7ca44nDCek/ApZiodMyLkT3BVlOckYeyhPFphNCYiZUIFfYyTgoGuuRVMr1SZ4Q23kz gIlA== X-Forwarded-Encrypted: i=1; AJvYcCXAlsrACMqq7hoa49QnX2wcMXEnlmRDwTTp19klJAQBsCocEY2uxcIZRSRFnHmh3H3AplJocKz5ew==@kvack.org X-Gm-Message-State: AOJu0Yz/D9snKwoQxEwchVA8TecnTXgH2lEU9yRLZqUXW4/vKf4f6kf4 kNSUuMOfM37UNzQ8YtvwRyna2Q0XfKXwmG25omKmzWlnWNlALtno X-Google-Smtp-Source: AGHT+IFUqAxMKu4KAhewhvBI0mdz0eqghs/kee0UYmXbNthOUIgi7hy0sT/wo724scKykqr20h+a9g== X-Received: by 2002:a17:907:3f25:b0:a8a:6c5d:63b2 with SMTP id a640c23a62f3a-a9a69a7862bmr325575366b.18.1729305458817; Fri, 18 Oct 2024 19:37:38 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a68a92186sm159941866b.7.2024.10.18.19.37.36 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 18 Oct 2024 19:37:38 -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 v4 5/5] maple_tree: add a test checking storing null Date: Sat, 19 Oct 2024 02:37:16 +0000 Message-Id: <20241019023716.4516-6-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241019023716.4516-1-richard.weiyang@gmail.com> References: <20241019023716.4516-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: C64071A0003 X-Stat-Signature: 56gnc1a9wusiz17pk3cembtnhj4ptwxi X-HE-Tag: 1729305445-854303 X-HE-Meta: U2FsdGVkX1+juCfOi/y3VpHnaAkYoj/YntnthG2sbDMJyXPgTcs65USubv2Z21OAa8wdKC5rt/15Zspxj+yc/esW5GdYBw1R+Di3UxdsTx/e8oaWNX3r83ZHRn/add68/ea2AcByEB3VrwpmuZory4eaR+fQV8QXmYUMqlGAyG1n7MkDf1gUtbmKSUfvPhMJ5JDagTbwMlAfjoESjXB2B9oU1GMbhnR2zctKPkPulFFxmRDEXsA0JzyvNR/yK1dHFU68HM0Av+MgrmNqN1RufZ1bNutHBNFytcIQseZdXiC4NMWq623wXulc1zY3Ureo/LWKKSbzHPKOEVBwpvflzJa3flmFBqIqjPjbjLc28PeZF6jhKIGQMq2NxruE5HQkdE5ryXMK9jU3IxzRC0yu1iZFYgUhpgC3o3GG2kTYqjtY8aLikowfPdbDj+8m1v+XTmnraRR+823Thrai0lJ6bd6rJMb+0bV7tOfGerFjKrKw61KQTsiIARUGayFvcD+qszZfEtv/C52EfMazZyxeDioaJp/68z7AFZuL6vrnU1JavXvNK/dEvGC5Up+LTkbxej/fsJHUBORttUMHfXqAgCbUjhKfJVYp2jBbKVuJgK2lCM3+8iS6Rp7ZJMPVwn/jq/0k2SxNCXMazb2U/9aSlj3G1OUzSPQ4olRzEZA4ly0ZIdGDQPkxRSYsPlMM2NgEogvLb36R2liQ2JIvZsWbB61A2jLyZas8hIEfoks6SOt5v5Kpk3bvs9Xkxndv5lMwKQkKcZZmlxbAdgfdOjJ34jHF9cat3jGVtoXxn+v/aCh5eKRf3RPXaybcXPL9edi3TdLNg2Gpt4eOMaRYtOEFr/Imh2dxYMU0WxbFN7gliUqIDO9YrVC+9mrScrdeRGRzOtewe8WjLVCXjk3QFrKiFeqkKUKQN3xDpx17p90nCuG3mp97c+6qr0YLfHSqcvGjKtH5hCK+STG+WvyXF0e teKIbfAB fJeoXaq81qPrNtlgeJzGVA8I8CiSu+Onql+P3MbI7zVff9uzfw+QzK66xJFAHWIFOHAN8sfjhyTR0lE7LeT9BRpdMh3tcVDi/BkmsNDID3i/VEVsztdB5NHZe6L2DE5i0lzyIP87J46C1BBTTNCAfqMH3mrP2fYWdP1u4jr1XNpHmqEx1znbGHTwWiklioS216mDLeI8OnAVy/o4mSkL0+mRbwytE44NymOcLuoxp+G353SzqQB/rdzKzo23OgnkcGkX/ZuQGnwuGQ0bP/2Ab7iIVot9QrS7YWC1emVrtcX4plNCMvmyFbZpyU2WfO76gAtuN+7rH2LJL40zxvkVztr/7OrEyeb6MPt8iMh0M3DNrGPLCsucmss2J/StQj2I3S2fA4mZjfMY4Cne9cvgcHzoLrM92ZZjCjAj8656OrMzIzsoySni4tjI4H7TXTBkPgMhHaoIW2rgQGEvWNeQ5kQ86cTIu42HKcuLqZBgLmL49/pi/JXhX3jwTFD1uhmFXqnvN 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 Reviewed-by: Liam R. Howlett --- 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);