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 2EBD7C4332F for ; Fri, 16 Dec 2022 20:30:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 778CB8E0003; Fri, 16 Dec 2022 15:30:48 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 729038E0002; Fri, 16 Dec 2022 15:30:48 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5F0CB8E0003; Fri, 16 Dec 2022 15:30:48 -0500 (EST) 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 4B79A8E0002 for ; Fri, 16 Dec 2022 15:30:48 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 126F4141287 for ; Fri, 16 Dec 2022 20:30:48 +0000 (UTC) X-FDA: 80249312976.19.18BC8C4 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf14.hostedemail.com (Postfix) with ESMTP id BB737100019 for ; Fri, 16 Dec 2022 20:30:44 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=Zb3aYLGg; spf=pass (imf14.hostedemail.com: domain of rppt@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1671222645; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=5Duo90Wzw3IPTyEgwT1S/s7QyCdRPezyK6ozawKBDy0=; b=Qj6DDlBZ+VHtrdNVP+SHPMouoO0X/w6WzMwvawuzT7gZ5Jq4/dNz4yxTdaHzaM9GKY9yR5 rTSeNUcfCYLluf+TJTS4MkPr2GvBISt2H3JoIVZ5Cso1DiRZ55d4tkotEwwA7/bdNpNlOG rcGLjYK7630Ah6vcc/yseGoprhx/Xuk= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=Zb3aYLGg; spf=pass (imf14.hostedemail.com: domain of rppt@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1671222645; a=rsa-sha256; cv=none; b=UWttoEm1P5nS2n3wr3aCUsQ6lfEnaRbsNHvmi0j4IZnLSdMB0VsPiA5gnB2gnChw7Hhl7R 8wRxYWX1WFFS22V7wHNI8n//cDVbx/JH7Vgty9YXRc0LyFDpFNT4Y+uz1hQbiMmLkPtNvd 0aXNfBV5KUNcZX3M34i3aRUUf+eJbdk= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id C278862203; Fri, 16 Dec 2022 20:30:43 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 3BA01C433D2; Fri, 16 Dec 2022 20:30:41 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1671222643; bh=tTI5+JlUZWGk4Qn2IlYwarGglLDZGP6vou+JfYABe2M=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Zb3aYLGgNXa2vW2C+Ixxpxl2gXR4ljbH5ylBHG8vY0UnZihFLElQJcS4SB1rnrLOE +FXG0lkDY1vbkIGSBYmNkgKAd8v7g8k9Eux9ziN0sLchl3+Fn4Lp4Puh1+33eUM7kI NePuVXU4naa741wujWHSMvG4tsayRBmuQyaGxkGyDtpZ1JeBeheYymDvn5cmXZdJq+ qeOc2nKmiO3zFx91Uzh/Wti4Ce1OjUp8WW2sv4VK9oACmd60O0GMeTjFTfa84AOrTO dUCuEr7Xe9vpRGDj5s7hVicxwrYKANwWo0KzGinOhdR1zeikghIr/DUYp7CxwVTr4i STk8ySIjcxLeQ== Date: Fri, 16 Dec 2022 22:30:30 +0200 From: Mike Rapoport To: Liam Howlett Cc: "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Andrew Morton , "maple-tree@lists.infradead.org" , Andrei Vagin , "usama.anjum@collabora.com" Subject: Re: [PATCH] maple_tree: Fix mas_spanning_rebalance() on insufficient data Message-ID: References: <20221216185233.2036415-1-Liam.Howlett@oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20221216185233.2036415-1-Liam.Howlett@oracle.com> X-Rspamd-Queue-Id: BB737100019 X-Stat-Signature: phetmhpeniifuz1fiufcbsdejisuptue X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1671222644-885779 X-HE-Meta: U2FsdGVkX19z+pR4I1LNlYMnLmpiJZ9IPWz6nUb2QsptVtahFFa/wsx3MKsYrBYCeORfKCez644zuHXtZ09979OBwXqy2/5F1/t3kwprl6IQs2gJfZDjFuMOUYpZdk2MqAP2WIuod1CACL3eTK89V9D/NwBmg/YqXnX2H0EjFSH9P45Jakxe5s81W1KMPUoUq4cAmNRbnvE1zm2LcoF3q0GWPI8g2x98foTfb2EOZQLPpywaH8IBZLWbwEC9b6GELjzUCZ2mdHyQcuwGsd5+9/usiH+gEqJwT5C5ZW9YVqYvZonFYFB8Ikl2/GUnIj3gTeXVnXZKROp3KQPGyr4OLvP7bHiNSKQtNS3AoZt3N4OXqxRS9oHq8+BKRU2BiKTCSU+zS75/l5sCGZbdvvwdwPt74Oz4sj3M5zltL9m0KOxyAzQYlJGrFOe3DGAgEtRqZJ3NN0dmkY4VpKFFd+bFXOoqZ1ALBb14RuIa8fsyOD7bdDBQ7j7w7j7oxnh8QrSVAzICQu7XPL78wrDZmWaWyfBK9LkH6GrmuC+9mc8bOpBs1z4d5lNi8B+fj/hGl8EHZEe/g+JhVp/w5EojHCpvYq+AU3rkuZVN7EwDYjAtdyKMzullb/Vbh/CbzkbrwJfH/d3nkTgMmPcPnnA/57EY12w0hQs5tIsVsmxSBox7fLSRT32Whpr7OkG6ng0llfQSXpd1S7PTvEYwfBTJtAwt1sXyUvwvZa5qq4idq5SCu/PO5amOL5kmIeEzKJMxiN3SlLXqB86Efj2+4Pm0mwmBTR5KrceKmt4Z5QCftaUz60o0izK+780+ram8NamhXEAq0es7L0h+4DCtQKOWH7lD/DnQb9drIW5YRZkZeiHc0Mm7/60NPRvUHyZc7evsFFSbW6Uar6s7bXuWSG57XTxRYJqiBidkTIHgMGf2LpT/B0Pr1i44w6k5SMMcG6i9Y4TmkDnC1AX/0bLTEcU0EE1 ZY3TN7Xy hmNmwc4MAini7b35D6nSq3o+mMVfZnnjMqVA3WMLFXPJWq9BcveHzzMrLB/ZzVySn98a+gD/XWZ3QrdcR65qXStEW5Z4QPInxYm3it+cPCxJRvMr3rkMW5rTAEA== 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: On Fri, Dec 16, 2022 at 06:53:15PM +0000, Liam Howlett wrote: > Mike Rapoport contacted me off-list with a regression in running criu. > Periodic tests fail with an RCU stall during execution. Although rare, > it is possible to hit this with other uses so this patch should be > backported to fix the regression. > > An insufficient node was causing an out-of-bounds access on the node in > mas_leaf_max_gap(). The cause was the faulty detection of the new node > being a root node when overwriting many entries at the end of the tree. > > Fix the detection of a new root and ensure there is sufficient data > prior to entering the spanning rebalance loop. > > Add a testcase to the maple tree test suite for this issue. > > Cc: Andrei Vagin > Cc: usama.anjum@collabora.com > Reported-by: Mike Rapoport > Fixes: 54a611b60590 ("Maple Tree: add new data structure") > Signed-off-by: Liam R. Howlett Tested-by: Mike Rapoport > --- > lib/maple_tree.c | 4 +++- > lib/test_maple_tree.c | 23 +++++++++++++++++++++++ > 2 files changed, 26 insertions(+), 1 deletion(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index fe3947b80069..26e2045d3cda 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -2994,7 +2994,9 @@ static int mas_spanning_rebalance(struct ma_state *mas, > mast->free = &free; > mast->destroy = &destroy; > l_mas.node = r_mas.node = m_mas.node = MAS_NONE; > - if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) && > + > + /* Check if this is not root and has sufficient data. */ > + if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) && > unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type])) > mast_spanning_rebalance(mast); > > diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c > index f425f169ef08..497fc93ccf9e 100644 > --- a/lib/test_maple_tree.c > +++ b/lib/test_maple_tree.c > @@ -2498,6 +2498,25 @@ static noinline void check_dup(struct maple_tree *mt) > } > } > > +static noinline void check_bnode_min_spanning(struct maple_tree *mt) > +{ > + int i = 50; > + MA_STATE(mas, mt, 0, 0); > + > + mt_set_non_kernel(9999); > + mas_lock(&mas); > + do { > + mas_set_range(&mas, i*10, i*10+9); > + mas_store(&mas, check_bnode_min_spanning); > + } while (i--); > + > + mas_set_range(&mas, 240, 509); > + mas_store(&mas, NULL); > + mas_unlock(&mas); > + mas_destroy(&mas); > + mt_set_non_kernel(0); > +} > + > static DEFINE_MTREE(tree); > static int maple_tree_seed(void) > { > @@ -2742,6 +2761,10 @@ static int maple_tree_seed(void) > check_dup(&tree); > mtree_destroy(&tree); > > + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); > + check_bnode_min_spanning(&tree); > + mtree_destroy(&tree); > + > #if defined(BENCH) > skip: > #endif > -- > 2.35.1 -- Sincerely yours, Mike.