From mboxrd@z Thu Jan 1 00:00:00 1970 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 AFB2ECFB440 for ; Mon, 7 Oct 2024 12:15:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4916F6B00B2; Mon, 7 Oct 2024 08:15:13 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 441B06B00DB; Mon, 7 Oct 2024 08:15:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E25A6B00DE; Mon, 7 Oct 2024 08:15:13 -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 0F2326B00B2 for ; Mon, 7 Oct 2024 08:15:13 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 6CDF61601F8 for ; Mon, 7 Oct 2024 12:15:12 +0000 (UTC) X-FDA: 82646700864.15.A56E361 Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by imf09.hostedemail.com (Postfix) with ESMTP id 11900140015 for ; Mon, 7 Oct 2024 12:15:09 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=suse.cz header.s=susede2_rsa header.b=lhTXB80a; dkim=pass header.d=suse.cz header.s=susede2_ed25519 header.b=+83ssanX; dkim=pass header.d=suse.cz header.s=susede2_rsa header.b=lhTXB80a; dkim=pass header.d=suse.cz header.s=susede2_ed25519 header.b=+83ssanX; dmarc=none; spf=pass (imf09.hostedemail.com: domain of vbabka@suse.cz designates 195.135.223.130 as permitted sender) smtp.mailfrom=vbabka@suse.cz ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1728303162; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=u2ouv1GShtv7jkf/iHriBRHJG0IgJ+grVNYQ8hpVznw=; b=EeSiw0JwS7Mac7DjrgKXMVTrY+7Wh1JKGj7ksi6Qx09Y8+nA14qqy/Bewd5SYNe5vJK5MC FgBA5DpALqMGMag1qjUdfnmuLjW9r59DgHmWtc0pBxUm+1cdjmGVrLz+SCglFTCs/qOjom /K3fltWzfnc/03hE42viBtdcITxm7hk= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1728303162; a=rsa-sha256; cv=none; b=MbOJmree+XOiZtcZUeqHxmko1pWKlc5wDfIh125XHtP2Yuzl77q/tOJM3/llupwscI8REl vGG64WNro1XMAPkq6mMqR5jNFK6Y9Lnl+GGEWQN8DD8+KzYNVzMicAbekQ6XhBVx4xvynz Zbqvtj67Wid2NFfSThjpcjqYNFgwYZU= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=suse.cz header.s=susede2_rsa header.b=lhTXB80a; dkim=pass header.d=suse.cz header.s=susede2_ed25519 header.b=+83ssanX; dkim=pass header.d=suse.cz header.s=susede2_rsa header.b=lhTXB80a; dkim=pass header.d=suse.cz header.s=susede2_ed25519 header.b=+83ssanX; dmarc=none; spf=pass (imf09.hostedemail.com: domain of vbabka@suse.cz designates 195.135.223.130 as permitted sender) smtp.mailfrom=vbabka@suse.cz Received: from imap1.dmz-prg2.suse.org (imap1.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 72C1321B71; Mon, 7 Oct 2024 12:15:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1728303308; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=u2ouv1GShtv7jkf/iHriBRHJG0IgJ+grVNYQ8hpVznw=; b=lhTXB80alR9VCihHgs2B6QQPX4Z5rqoCcxpMZ7rnSScjnN250O6p+4ddEAgEYw3+GWXfZe Fjr8jMLtizpkCH+iUJKudjia12/+QfbVr9MMG8WlmB+iS1smlROphNOdtNwtDxS9Tn9NpW hvJoWJD2nW598iqhUDWWhUTTOFTjCkM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1728303308; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=u2ouv1GShtv7jkf/iHriBRHJG0IgJ+grVNYQ8hpVznw=; b=+83ssanXsYqqgSdiFHh+eFHz0Bviyv7SFUXvw6ZrHZkoMZT9qgobu1KjrB+iY7rQ48Z56e p3/KWZPg4KeMVfDQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1728303308; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=u2ouv1GShtv7jkf/iHriBRHJG0IgJ+grVNYQ8hpVznw=; b=lhTXB80alR9VCihHgs2B6QQPX4Z5rqoCcxpMZ7rnSScjnN250O6p+4ddEAgEYw3+GWXfZe Fjr8jMLtizpkCH+iUJKudjia12/+QfbVr9MMG8WlmB+iS1smlROphNOdtNwtDxS9Tn9NpW hvJoWJD2nW598iqhUDWWhUTTOFTjCkM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1728303308; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=u2ouv1GShtv7jkf/iHriBRHJG0IgJ+grVNYQ8hpVznw=; b=+83ssanXsYqqgSdiFHh+eFHz0Bviyv7SFUXvw6ZrHZkoMZT9qgobu1KjrB+iY7rQ48Z56e p3/KWZPg4KeMVfDQ== Received: from imap1.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap1.dmz-prg2.suse.org (Postfix) with ESMTPS id 5CEE513786; Mon, 7 Oct 2024 12:15:08 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap1.dmz-prg2.suse.org with ESMTPSA id 09eoFczQA2feTAAAD6G6ig (envelope-from ); Mon, 07 Oct 2024 12:15:08 +0000 Message-ID: <1cd350d3-a450-4804-aabe-0e5b4accffa4@suse.cz> Date: Mon, 7 Oct 2024 14:15:08 +0200 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2 hotfix 6.12 2/2] maple_tree: add regression test for spanning store bug To: Lorenzo Stoakes , Andrew Morton , "Liam R . Howlett" Cc: Matthew Wilcox , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Sidhartha Kumar , Bert Karwatzki , Mikhail Gavrilov , maple-tree@lists.infradead.org References: <12af588c6b3338bf6a73cd2d95943a83a44c3b42.1728223996.git.lorenzo.stoakes@oracle.com> From: Vlastimil Babka Content-Language: en-US In-Reply-To: <12af588c6b3338bf6a73cd2d95943a83a44c3b42.1728223996.git.lorenzo.stoakes@oracle.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Rspamd-Action: no action X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 11900140015 X-Stat-Signature: cdmuq4nrzg5eoenp9ygwgdx43pzyhqhc X-Rspam-User: X-HE-Tag: 1728303309-218637 X-HE-Meta: U2FsdGVkX1/zVm+Am5Q+SOcXOdzrB986RR4iI/s4oOj3BkvnfBbaaX2akE7wnwPEcRf/q5eI32S59LMteKByh8B5/37vewcj1m5035fYikFhpYvnyPghzU2efPnzKXXgEPwAdg/CEEHjf2MLADN90r2PA2d6l259xEz43hcOn0hnEFyHQao9ngG4ChoTgAN0nsnjgJCTtcFemKnzu3nApLoMYWwhB7KYXfrNI+qD4kWKGGEVgNw8Jfv5H87bdh99w4lNalmYjxcDzko76yFr5n1Y65VEbD1+HSvA8bMmBe+/SvZaSpmILbAtSD+MuejSwphHZW3orlYx4eo4q4u2hXe/n0Vr/6UPXN9DwJD8Uw81uYRQHG/2SZ/1mS+lAsdqSgJ3OhdDY8aGPSBqTM7lPHyRRfxLQLoC4tYwKabanOI9mGTHadMqZaBp9OuJxWuhPagP43PDVzAAONOgOC+IWs9dU4XaHbWkj6212NdYljkfNxMMxwSN9V4MeWiGaEuHXUlrjoFQ68OjVe98KZZzYZZIMu/MA1Pn9dcHS1xvUcyqUmHAPVh8wF7ehGQieYp7MOUPvIVSzojZEgOpfDlIm6YCQiIpY/O9HJNBoRfvh1ESTuiONu0ch0w93Q3WPjk0hW1upyJm20g0sAQ1ChPPZH8+ArzQof4F1SR9rjhOL8CeVrh3aGlgBMfOCrE6/sZtbkVUhGxF8FGNVLCUoGeMnPAzCVQscPMMZj/oAJOln6DEcjhf3iDBbpjJ2V13ixLkEKhucuBdu7YOAW6b4Yn3Ngf9eQyQJlpH76Q+VyeA/bqxZ2bYFEE5cVDV5H06eEMIxipU6jtUvrA9VhA66Czva1EIGImZ46CUycPLl3KNMYu3BmlceTDpjkxZqJ6mmcFVoFqDG9m6Es0FGu8+5x51mLeiZ5afL77DPA03LavSGt3QjFbzB1tGWDKUDHb+ZTXTLzXhucXCKaOXJAtC3V7 xVaACx2W jCtwXEcWOf19pMDpGLKjGas29ygGXlGGYRcW56Q8Soik5Z1mr2y6girO5L0wET1WyFgBy/IstUwYaExbgBnxNmC+K2AeVtYAXRUK5vYZUV7VzHGIImaWLmJ4WDSdkfMPaXyHLpG7pveFs1AfgBkf/oerhyOYwJ1/9AsAwnXyHTzQQA3kcWEPdmneazz02v6+0GLz1cO1pQIacV9hxBxAZGSB67ZetHRGZ7keOPH9yG4SABfsSp25jj/6lYv4avnh0TJ8VFMroXCQX1XjTovei1yXhnQuO/yUpDqf0wjsjU4GizlOkSt94vw84q2jm0I5TAcsb21/xf7eiw6olBOTctK4AMa+QJrktZZ2eBZtZR9qk8wsdwvinBK1OFXOF3p4x+JdB6Xn8m2lrFroc7JEF0VOiKr+PIAh5ptWHc8rvtokP5TQ= 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: On 10/6/24 4:31 PM, Lorenzo Stoakes wrote: > Add a regression test to assert that, when performing a spanning store > which consumes the entirety of the rightmost right leaf node does not > result in maple tree corruption when doing so. > > This achieves this by building a test tree of 3 levels and establishing a > store which ultimately results in a spanned store of this nature. > > Signed-off-by: Lorenzo Stoakes Acked-by: Vlastimil Babka > --- > tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++ > 1 file changed, 84 insertions(+) > > diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c > index 1873ddbe16cc..5fde09999be4 100644 > --- a/tools/testing/radix-tree/maple.c > +++ b/tools/testing/radix-tree/maple.c > @@ -36406,9 +36406,93 @@ void farmer_tests(void) > check_nomem(&tree); > } > > +static unsigned long get_last_index(struct ma_state *mas) > +{ > + struct maple_node *node = mas_mn(mas); > + enum maple_type mt = mte_node_type(mas->node); > + unsigned long *pivots = ma_pivots(node, mt); > + unsigned long last_index = mas_data_end(mas); > + > + BUG_ON(last_index == 0); > + > + return pivots[last_index - 1] + 1; > +} > + > +/* > + * Assert that we handle spanning stores that consume the entirety of the right > + * leaf node correctly. > + */ > +static void test_spanning_store_regression(void) > +{ > + unsigned long from = 0, to = 0; > + DEFINE_MTREE(tree); > + MA_STATE(mas, &tree, 0, 0); > + > + /* > + * Build a 3-level tree. We require a parent node below the root node > + * and 2 leaf nodes under it, so we can span the entirety of the right > + * hand node. > + */ > + build_full_tree(&tree, 0, 3); > + > + /* Descend into position at depth 2. */ > + mas_reset(&mas); > + mas_start(&mas); > + mas_descend(&mas); > + mas_descend(&mas); > + > + /* > + * We need to establish a tree like the below. > + * > + * Then we can try a store in [from, to] which results in a spanned > + * store across nodes B and C, with the maple state at the time of the > + * write being such that only the subtree at A and below is considered. > + * > + * Height > + * 0 Root Node > + * / \ > + * pivot = to / \ pivot = ULONG_MAX > + * / \ > + * 1 A [-----] ... > + * / \ > + * pivot = from / \ pivot = to > + * / \ > + * 2 (LEAVES) B [-----] [-----] C > + * ^--- Last pivot to. > + */ > + while (true) { > + unsigned long tmp = get_last_index(&mas); > + > + if (mas_next_sibling(&mas)) { > + from = tmp; > + to = mas.max; > + } else { > + break; > + } > + } > + > + BUG_ON(from == 0 && to == 0); > + > + /* Perform the store. */ > + mas_set_range(&mas, from, to); > + mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL); > + > + /* If the regression occurs, the validation will fail. */ > + mt_validate(&tree); > + > + /* Cleanup. */ > + __mt_destroy(&tree); > +} > + > +static void regression_tests(void) > +{ > + test_spanning_store_regression(); > +} > + > void maple_tree_tests(void) > { > #if !defined(BENCH) > + regression_tests(); > farmer_tests(); > #endif > maple_tree_seed(); > -- > 2.46.2