From patchwork Wed Nov 13 03:16:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13873132 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 4CA6DD597D2 for ; Wed, 13 Nov 2024 03:17:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BB4036B00C1; Tue, 12 Nov 2024 22:17:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B648B6B00C2; Tue, 12 Nov 2024 22:17:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9904A6B00C3; Tue, 12 Nov 2024 22:17:02 -0500 (EST) 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 784D86B00C1 for ; Tue, 12 Nov 2024 22:17:02 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id F33561C56C3 for ; Wed, 13 Nov 2024 03:17:01 +0000 (UTC) X-FDA: 82779608100.01.714B1AE Received: from mail-wr1-f43.google.com (mail-wr1-f43.google.com [209.85.221.43]) by imf21.hostedemail.com (Postfix) with ESMTP id CE3EA1C0009 for ; Wed, 13 Nov 2024 03:15:39 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GqVuiDZS; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.43 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=1731467732; 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=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=XdxptMo/+NjfWHNaGx4me+tTbh1L2ChqVzJPlxzf5Z5D+ocFrlN1N9mpF0kU+hoNeTYlsw gPJyd6hH7DwyGMunqOd2ZNN14fsqEhWyQ3ka9rf4Q28ue0dGc2VUiHb7mK4oc+xODfsxvQ WcH3w8JPt5uEQDYNW8GubSqAXIegCB0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731467732; a=rsa-sha256; cv=none; b=wXrAGSXoLCZu+C/uFPPkEKwMNRJq68g9VZ2Rc0pym1RxmC0s2rYNIr9dQFkPAnjkoubHK/ h2a3a5s+ZiYtn2hHEgnR07yuQI8gUBYdHqBknZW8g2DCQGKzzFxUyiC5KpBRg8pBP1+DfC +CJFBAdTL7+6zhYuRqeD6o+6Qudki2o= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=GqVuiDZS; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.43 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-wr1-f43.google.com with SMTP id ffacd0b85a97d-37d70df0b1aso4075375f8f.3 for ; Tue, 12 Nov 2024 19:16:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731467819; x=1732072619; 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=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=GqVuiDZSxSJuVDbGotc5ngKLsR19A3ATohSQY+U3Sa9MUEkkByYx3H+3FPblYqSx0i MG6SXvitPE3SNZez1DVA+pvBcZJZa5NfdeyOC1/SzYQOVlF5PIixcFnRdZewmhWWRqfV 3wlVqk5ZwwyBhsJJo2jtXhFYkfR3QLYBq4MEFFNbHuhDJekJuGipg44XJ5gLBDdolJOo Mc/lojv0z5/mRNNVcMl1zR2XQpwhiD8FzJGYIsUGQYiplHcicF68CNaxtOVJxElNJDIB sPMkCVh5yrXUgOyIg9FqSY3VMRFDrSwxI6UGKfB6C85t7A4NocblRosNbA0TwMcRck3C 7c1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731467819; x=1732072619; 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=qeCBTUPs9/Vlmfwx00wPewAGx73R3k2M6pY02l1BFx8=; b=amdbYVJqPngRXGUJhu+GVz7ujmRCL/n6hHFLRwGEAqAS6WV7PP+wLd7OhxjmOt1l3u HpPfwbZTCtlV7HEn4dmW2CK96yYLoBrOwXaCPmhKdZE2hdHU5ZgKPZDZdMrTW/kCN9+w yy8/VRFS7DJ7NvxexttPhgidwf2lnEvHxazVgru3FKpw7Ii2CQuEaGiUi1Qe+qBxb6C2 eRU/RdapD+tYlzgrvNBb4xEB0iljzuMISfjrCmXf4YQJxSuZeB5g03MA5RqvkbvMW8nh W/DmLyBjJzvxp6wJvyxTIHHLfmgvvkVxFvnemmdxSMTxoL9AgxXDZhb7IiJNA0R2PPrn lB8g== X-Forwarded-Encrypted: i=1; AJvYcCVSvG9GIyberz0ESRyskHDDuoS+jHJoOAABD/Nkxhh5w+m/UOHuZ7CrpTIZ7Gt6rHNZRBSMoEQ9Kw==@kvack.org X-Gm-Message-State: AOJu0YxWF7J9WHukhd1v2f5t6zN5Ah76vE7MuigtbjVzJTKaTTqaeFSH wlk9piJ/Ah5uIg4jOrd/VAWe9iShFzl4JTHRhpSkPcNZhzOjtBYw X-Google-Smtp-Source: AGHT+IEddt00vX2l2YXz0+piP+2d3c29Bf5BqMddTwACF1f8JwgSO8ZpmXyWAMitikDto96XifWZLQ== X-Received: by 2002:a5d:6d81:0:b0:37d:5133:8cba with SMTP id ffacd0b85a97d-381f186d161mr15789433f8f.20.1731467818617; Tue, 12 Nov 2024 19:16:58 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03b9b661sm6677648a12.36.2024.11.12.19.16.56 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 12 Nov 2024 19:16:57 -0800 (PST) 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 v3 2/3] maple_tree: add a test check deficient node Date: Wed, 13 Nov 2024 03:16:15 +0000 Message-Id: <20241113031616.10530-3-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241113031616.10530-1-richard.weiyang@gmail.com> References: <20241113031616.10530-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam10 X-Stat-Signature: wf43hgjsza6j9fpy74pfrby8hazyx55z X-Rspamd-Queue-Id: CE3EA1C0009 X-Rspam-User: X-HE-Tag: 1731467739-475572 X-HE-Meta: U2FsdGVkX1/FhysiKrIF6PgjcgrTdU0FfFy0jLnUWBaF/avaPwm8eCtIRDvj9jNXwQjVaF3LGxNRUmV5XHWB6oMW+48eut+WxN+yb882Kjsmkp+AE0ePlXQJkrn0Un6x52G1ehA3LN4I6c5sHrvtyR8Lq7EaM4KA4lYE281bv57FyoNuO5Bzr9pHRDhbPq1W07GuHmFUmSwjdjzv1NuGYxrlgf0p9OXhOwKLPjoC659tMeGENcfYVGJK8tIX5BsphvMPnlmAF+2um2yCxNTv/lXzgAMPT8JstESSMeJC1Q+j4k7g2xiAo5RD7xKEtTt/2XffaqWuXOxu+brDpZcT2AgvVJMYL+n1dCwnAHoRMhOBdXWFicvvGeG31K2JBRB+xPdwi3ARxSSxWOOE5dw4rf8nCYUnfO9qHnSiQ4XX6qpQKnSorjUJOMgt2cKLgru492FUBU1WrmO0Y31DSrQMwBa8pstvLV0I+5Qr/NKNnU1kef04NEAqOSAcL5wt58MW6SmCxOWcaEeoSrnk7z8Tybn9cm0f/Oc6cDkGABz6lqfWl8BTkQ4XFe0r4TQ8xXL3cYq+C3LPEbCCvJAheqfVw8RtZ3Ff7BOMhrHW0wlzmMtBACWkZXbYa/ipVLedNtPrTAPOTpsWyyhTO1syMa9WARgmTuIFZYazecrzSGR0MGgXtiGjFwe+qhTxtJETOHeB1tpBV65rCPleoWVUsiyKdm8kMOWBtIF9kfg1puATK6ksNCZdpg1jdRjPcl52N+/jbMuocXM61izOafpYbW4xglpTUNMDzcye5/6dLWev+dhrwMGgCtLebf/IasTpBo6n+WxZKiTrr/mmmjEicnWhJoVhhAsrhBEc45H1AEFfuhxQNv5lQkuZV0IDHEWQvUe8xvuc5HolF18o7aQCSBcygNbMLksKjMDxXT00HOaNOukwM5QRvvY4pl5BP6x2bvi/3lw3kLjpo6TePgTPnTD /8qitJke NfPnz9zaD0VyDGZwcGQBHhG48PAZ4tsrYv9w/NZ7a7sCNkJUqZxfKMgW1NyR26O79miD+/4mHPMR1/hTIZYsu3f2HauCwqRzSqrlTS1rEhd88BBVLOy98KYJ3VUsEn4cQiiTCp4K8q858pIo0chnLg+fdyXas7M0WMoVKn9ufIkQnv6dRhcK1o9skJQD6pL3wYJ/j9kMR8x8DyslTMwNFuZXYgGeBTuq+bLUEtMvjHHOi5BY+naljSMwPxQbV4208P8nXEcE4RSNx7hhmBUN7kjgGCvYA1m6uZuCFAMtIDU8MR9exMXWKDqqCeqtsCOv0U2TdOZly9ADX8fKL/dJiKjliWTg39EzKPPPM6dHWbAa+hQFb5YPE/gKvsaP2gGaV5jYUJ60eVDP5Is3BLqBQT61TdsyIlnF16sK/Jqx0YnFhIVllheCKPJ1f9tFY545LNjuet/vWx6MyoI7WKcGIbpgIOFZ53mhxfcNNHslDrNnLDVE4mtiiaNUmTp1IAxQt0cde 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. Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes Reviewed-by: Liam R. Howlett --- 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 704cb1093ae8..72bda304b595 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; @@ -3796,6 +3820,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_deficient_node(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_store_null(&tree); mtree_destroy(&tree);