From patchwork Thu Oct 31 23:16: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: 13858440 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 E6F47E67490 for ; Thu, 31 Oct 2024 23:17:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 89D126B00A0; Thu, 31 Oct 2024 19:17:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 821E86B009F; Thu, 31 Oct 2024 19:17:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 69B5A6B00A0; Thu, 31 Oct 2024 19:17:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 439396B009E for ; Thu, 31 Oct 2024 19:17:03 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 0D8BB141B5B for ; Thu, 31 Oct 2024 23:17:03 +0000 (UTC) X-FDA: 82735459086.30.6F22178 Received: from mail-ed1-f54.google.com (mail-ed1-f54.google.com [209.85.208.54]) by imf20.hostedemail.com (Postfix) with ESMTP id 1316D1C0012 for ; Thu, 31 Oct 2024 23:16:26 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=U2YjJcNE; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf20.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.54 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730416502; a=rsa-sha256; cv=none; b=d1n3FaSGZAXbF4uUv788yKW4R9dWGD9kKO2SdyIgWNJq3G7oapFVL7pWmx27WacjpF+7zk yHx/upW2mloITazBkdknHq6F6JaVPucjhRU8t0u5hIBxyNeYnQw0wWmYY46GgediZ4NgHd PM6RDthu554i6yXkfyVZvB8WLpiB2U4= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=U2YjJcNE; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf20.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.54 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=1730416502; 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=P9CSRGwy1VJIBoSqz5GF5VVPAFI1YgXTSL6P1gi2Dd8=; b=DCgU2+kLv3nlJwubGgd1vzfmdP/lTWJnaqrjTSsP5gAXPNwsXl4ixUCUm2mjbiKjEGGc29 5HqnReVx7QB8QdQTJ3DiqNhQrUBnzNs+qakvLY9SAQ4obokPl2JmyhAmRgox/X5WyscFG2 7np+CHuOtniA1BbBJtjzoh0B90q34ns= Received: by mail-ed1-f54.google.com with SMTP id 4fb4d7f45d1cf-5c9362c26d8so3976973a12.1 for ; Thu, 31 Oct 2024 16:17:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730416620; x=1731021420; 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=P9CSRGwy1VJIBoSqz5GF5VVPAFI1YgXTSL6P1gi2Dd8=; b=U2YjJcNEXWo39ZCAig5J5EuJYq4QoHDGSzLJa1iBrbBQrutjD9lwEOBGm+msjV7QSf 5dlr7zeHedPM/+wFIOfLrRZzX0uK4dlFZmh/1dL6tkXEtHALRdRj1o1Z519uklCVcWFz ys8SWYMfW050b3zOJt9GqYWuzPruHHUi0LhjvHS5Fz3fnRKqKcHzuIfjDZbcwG9k5B16 9uT+zof1Ch1alsMt02d/qfoHReQYwuziSoCxkNx1X8zxrdZvPyM27SjyPLSeVDHIPD7O vixuc3+/34i6wSNRGve9ZvR1QmfIbbfr+cZ9CDKiUWxyLJb9gQ6Bw0ghP8ge2HA0HYMs YAZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730416620; x=1731021420; 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=P9CSRGwy1VJIBoSqz5GF5VVPAFI1YgXTSL6P1gi2Dd8=; b=UGuk/yqo/5Ihnz+LSP3BMlFrLopZl2ZDLFW3EHYvGmXqvFsIBxjkL1LcfR6XVBUctk IfzwCdNVFwFwcd2XidaqmkNtLjFp6iiBsWyC80C/789I/2XIXfikvW7xPEHwHWmce+JG LVJ7MyNCcs4IAkJPpd7vbyuZsrgRIRmx3vDmeG5ds6re+cf/aMoW7jQtLyJZ+LHFMROG hQQJlv3HdGQnevx7K/ly4pRtSgmykRfMWBPWByct3tpcxNxL77RkEB03VdN3z/tu640S VLbnMIrT0HihK/OLmqK/bMUQmvOwkaAmOXXHoPfYS5ltudWIuCOhpBNAQKSUsA7efRGe McAw== X-Forwarded-Encrypted: i=1; AJvYcCUoIvYZQmsRczAa1krrMxPt4rhK/7mgDtkn3vztbi102aWKilqdCGYGyp1SJcE2L/4ZpjXN55KO+w==@kvack.org X-Gm-Message-State: AOJu0Yz7ux85rliQV/+Rm7HhQ8KM5XiEPsqMOtVwH3KDwXr7mT4iRstY FWc9WjF9ZUp/nO8BZh/BF2JGy+Au6sLwPE17BqqJmm+T28ZrdzF3 X-Google-Smtp-Source: AGHT+IFJ6tmN4yYb8ERMkaSpwtA+zX9Ypn5jLHsJl6p2VlTr8UwYTltK2X90Vlmb0rFEwLmBd2diUw== X-Received: by 2002:a17:907:6d20:b0:a9a:139:c3de with SMTP id a640c23a62f3a-a9e6549249bmr172423466b.29.1730416619530; Thu, 31 Oct 2024 16:16:59 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9e56679c05sm114176366b.193.2024.10.31.16.16.58 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 31 Oct 2024 16:16:58 -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 v5 5/5] maple_tree: add a test checking storing null Date: Thu, 31 Oct 2024 23:16:27 +0000 Message-Id: <20241031231627.14316-6-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241031231627.14316-1-richard.weiyang@gmail.com> References: <20241031231627.14316-1-richard.weiyang@gmail.com> X-Rspamd-Queue-Id: 1316D1C0012 X-Stat-Signature: zyk6ba1gdah1a8dwnc58ewh775uxju7g X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1730416586-557005 X-HE-Meta: U2FsdGVkX1/hvX4ucoKr0i9BdVbh8A6yyOVWxJgTPeTdFYButy5C2dT+i33K1x57dLGvYvYbZwDVEfkyaTtYvJGAsICRSgOIbJ7RRwYO0zXwB/P/1EkePYWFB0WEY8q8hmv/O9RiGtNTxfD45M0vOvRfQpBwP8J3gCcjrY7y08jAAbDauq/MtuZz8VONkXaCIHshh98lJZYJnBvneYJBtCnD38LFhK9MnaRrEhgbwHPvYmYmLTmUp1lkcIXL8AQ0vbf/c+i2Fi52pR1fkOrgk5StT7nRQgFlivoN54ImXD9ovlh5TL/S5xIWpcTuFYnu7KJG5v53SiL77qcL5nxkutzO+k+RNWShrMnJWkjOv6+V1FPu1e3LJWWdis+GjpfxO3Wqy+HLqcRibLEiWqou0bAufSqhILErojYlU00VvjuOyS6iwZIrFPn1hTVY4rRKVAVnDbBEELxq20reJBFWc2Qh7R/KYSgwC2OTiGdy2vKHvH9b+Gsghsl7EnGDQCeidHTRtRyKGYVyrqdMnjxg4BLKLzkJj9qgbdx3fjMLosQ7cbGH8M3BW6cvTJW1RptN76OpDnoTEsWl44bJqEMrRgrj5wYSSOflmxjKDT/R2H0QDgF7kkFZVDvffFgT3A+wvGGtf4IyG/hU+zCqdLGe8g01FaooaHTRqtBIubHZLoCgo8aavi5eFFdlo5jhvEmK/aOvWHvL3pva1QAiDpM4ZrD+kW3s+X1R+W6Zdh3sRDxH13JHgvF86oGNy9ifGx7NUHtyybqXYXwoo0kqdIhBNtXirPNi/19YRvytsAsd++lkNy/6ublXnemQneQjgHU8AWin3DD3HimsCnP7NKUmstXjjshlFbns7e1HERWW8+EUL4lGMS/4L4EqyfODRC11KRbllaxbp7q/b1nMx83DSXHM2ax1Wrm2fjo+/EwH34kzRgP+7argv8cfPh2xyRKcmgdPydVymZXl2ere+x/ t8HyeVOG KD2GsZ0J1iLKSzftswn36gCpE5OudjD+dTkwMrBsT3NgMbSyXCzkko9JzW8dpOEsqiIOEyHaQWgPFLOP7mo3WaGULQE2D1Bwmw72XcggrHLo1rxBCKU9RKDtm9UAcRx1BnGV435MAhl6PWaMN4z0oreBT1bezrGnYzMtntl0SWJuiCIJtERwV1jkf76Sh/TxCujVfkNrRJfXSFitbWMWq7X5qR+IxtzJiULKQBnqEyPyYCPdS+G+BpnURFQSIn5/mtx1EzBLcxXJsD1PHHD5fDCjHdHJAYvf46lMlxl7VHxUtueC4geceWcpS9lrpCmEsXyr9kxTTpNAhyMAy7sFiZMoC5u5/pJ7RlsIazorFQMj1qtl/f0rCT4QWbHSOSaWxnFRMKUYEgPwkNWIxizg96A5N3XMSQuqC69Ezzam7FJPQV0nkdCPUvx5h5xhoXb3MniO9ps8mBcM5Ct6sY12uY4Fv76QZW/k6p6IYQGDkgvZgfHoAZcIpPRmeF9ajoPca/Tmt 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 v5: fix a build warning on xa_is_node() --- 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..6f76093170bb 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(mas_root(&mas))); + 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(mas_root(&mas))); + 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);