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 E8EE6C4167B for ; Thu, 7 Dec 2023 21:04:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 881956B0072; Thu, 7 Dec 2023 16:04:44 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 831686B0074; Thu, 7 Dec 2023 16:04:44 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6ABC06B0075; Thu, 7 Dec 2023 16:04:44 -0500 (EST) 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 5957E6B0072 for ; Thu, 7 Dec 2023 16:04:44 -0500 (EST) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 1E6DF140279 for ; Thu, 7 Dec 2023 21:04:44 +0000 (UTC) X-FDA: 81541251288.23.0B8A8EB Received: from mail-pj1-f52.google.com (mail-pj1-f52.google.com [209.85.216.52]) by imf24.hostedemail.com (Postfix) with ESMTP id 38440180020 for ; Thu, 7 Dec 2023 21:04:42 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=jy7mjsmZ; dmarc=pass (policy=none) header.from=chromium.org; spf=pass (imf24.hostedemail.com: domain of keescook@chromium.org designates 209.85.216.52 as permitted sender) smtp.mailfrom=keescook@chromium.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1701983082; 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=P1df2F2aMLldf9qn7FPBt3am2yl+mT6QC0UrRj9+Dnw=; b=sRSQ5YrJU4vVAENgHTQDx2ns2xVirMlQ+sbxnrkKExgV/eA88ncmbl6+n/i9swmt9V5CZv i8cHAQ0gXgrS7g67VL4Q3g67lYvfYTT/7gScVGuMZBeSMycSrLwTWiynTi2Wi8U/33BG+s 7P4aZzOWFqMz8BXLthXHVTZpo6I33Go= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=jy7mjsmZ; dmarc=pass (policy=none) header.from=chromium.org; spf=pass (imf24.hostedemail.com: domain of keescook@chromium.org designates 209.85.216.52 as permitted sender) smtp.mailfrom=keescook@chromium.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1701983082; a=rsa-sha256; cv=none; b=S+6rS5u62dHLhckDRmGtz1yIIfJQP7JvghFJ8VouforGSurLbxXi4k5H5ZbdEvVSRqSnt3 F/2XYSjexxX/soH7noqjsn31kU4asBNkSnlI9jevzi2cUUlutZhc5dmmMByOKJoX3m8vt2 wzejtzgqmQVso37QKEC4FGTc6Jw929c= Received: by mail-pj1-f52.google.com with SMTP id 98e67ed59e1d1-2865742e256so1206710a91.0 for ; Thu, 07 Dec 2023 13:04:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; t=1701983081; x=1702587881; darn=kvack.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=P1df2F2aMLldf9qn7FPBt3am2yl+mT6QC0UrRj9+Dnw=; b=jy7mjsmZMRE4LM5GNikzCc6HhL19LwUA3axHdsiTbz2GLrvXZeX9WJ2QaVK2oMOL69 YOqmpIAF8fG7PxTd63BLcBbD9f0qV6K5jUlN3tYA67uZJdY4tivNmWVu0PTlzP97YCQJ Q8rP3319Ff4efgiw4rrd8V8F0vJwsgN04jlTU= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701983081; x=1702587881; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=P1df2F2aMLldf9qn7FPBt3am2yl+mT6QC0UrRj9+Dnw=; b=EQY0o9j0km9eJFMLAnhdP4qxgtYdMBNpA5tg/Wkg9m/3f+Alq4Szg7s039/R5PPaxm PA2v4v/CqisvDRLn6VIFHzaCMsyuQ1jeV8Z1+UGddBdP5DqdCU4W7yWPT7Fw4ci+54c7 XeZ5mwGwlKZBv+JHYy0g1DParkR2XQ2CDDODuXtyWU44WVFe/gCN1m769ZaI8/h/r62S yJiHA0Ysb/sBFc4ruIrC0STfqZ2FuHhHhOOYdw6SGyKrru6S8ZEuNCvn1qGls/il9TzK 87/k7lmoqUitfpLof20L21wctJpjQzOruck/M5hvvmKP6OwWhlqs7tvEKzpkeIWlYNK7 5Opw== X-Gm-Message-State: AOJu0Yw4FKg3m+O3xDZx5TS3T5nH6WKwBaCZlxMB2u81mw+i95jF7C9n gS71uIHF17jgOeEOzexW2mmbPA== X-Google-Smtp-Source: AGHT+IF4dR+ozEHEoTeZ5KlcYJqBauEZDgcWSu4X4MZ186gCsrYPLTr0XOCn3gkc/RW+9rLwjr8oiw== X-Received: by 2002:a17:90b:350a:b0:285:b3a8:40ac with SMTP id ls10-20020a17090b350a00b00285b3a840acmr2717736pjb.19.1701983080991; Thu, 07 Dec 2023 13:04:40 -0800 (PST) Received: from www.outflux.net (198-0-35-241-static.hfc.comcastbusiness.net. [198.0.35.241]) by smtp.gmail.com with ESMTPSA id sc4-20020a17090b510400b002868d090c27sm354680pjb.25.2023.12.07.13.04.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Dec 2023 13:04:40 -0800 (PST) Date: Thu, 7 Dec 2023 13:04:39 -0800 From: Kees Cook To: "Liam R. Howlett" Cc: Andrew Morton , maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Mark Brown , Naresh Kamboju , linux-kselftest@vger.kernel.org, Linux ARM , kft-triage@lists.linaro.org, regressions@lists.linux.dev, Will Deacon , Catalin Marinas , Dan Carpenter , Eric Biederman , linux-next@vger.kernel.org Subject: Re: [PATCH] maple_tree: Fix mas_prev() state separation code Message-ID: <202312071302.99D5B1BB76@keescook> References: <20231207014104.n6vul2ylgqjnsfia@revolve> <20231207193319.4025462-1-Liam.Howlett@oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20231207193319.4025462-1-Liam.Howlett@oracle.com> X-Rspam-User: X-Stat-Signature: bnk3qkcmuake5aaunqnoh1u641qikjut X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 38440180020 X-HE-Tag: 1701983082-994178 X-HE-Meta: U2FsdGVkX18rSumpI7Pwex/VGXsDN2Lr4OPgw+oqCjs1MuMuruMArgBZgW0qIzSW+NpDIMpBqbN7bT70wnKjhvm0J+BNCX72IB9hnxbKNHtxUnMv3+13R3K+Hg4rM0RSiZkgPcQTcWxKapT/5oSQcfLhGQcJcxVJzM/lfUxgR5kKRUHpM1HeA2Haj2paIu0DvHQxNOEbDUGA5u0jwqgyPvG6Er2ZZthuZMljd20NjUBEIbc5s+7b90W30raG4q3l+/XLa3/tHIvoBZEaN7NSmlQy3Fx1qIoVoW73aRnM+GHBZZnzreUmpNmwkHN8ynM6G4TT3otKfGIZjPTysvGfzjR2ODjgdMxv/WKYuUTG7sIxhxFlLzonv9zvFSk8foiXTAErc0K6+nNUbwjhA7jYRBBmDPKtoAUWjGtX7iMgHB/22X5l2JScd/byDzwSPVulcKeCKpS6kFJ2l3lsMbe6nB7eBL+NiP7d8jx8hBbLyy2EskCSrSw4rzx8/sfZIMBbni6pwUJ6xNUOzW5L5J9m1Ye02S49IPi8FHoV2Sp39LUo9Ydf+iF6Le3bsSbiUG1jpasgPRUEMU3zltG8iC9UXr9tSqXjfiY1d2ilM6BRN0KISUPSLvc8sWYGLB29DhgvgdtKyJFSVoIYv38KaEcqR+cbfwJ1KJMReab12+joVhe82sP0s6yp5oyOZvfMy4oa0l/Xf6Wb9MJKlHEYdkFUDamtXWz1hIVaoE8t1Qp7TOHRzwSistHjq5fZJTH4IPJoAyVKHc1THBjX/Ey0E6TdyzMYjyUzcMTWkZ3F3oH6mdX2I9cRq8iMyWZcWRlg/GwlNEqMExSQSMWluZQ8ywOhxkvMRz6pxKO6YphoPCwNshTdPi+0GHIFVkVO1mZOdtYj+7ij6ZDw9D0JGhXCDkqgrePuDLA05nto9ztm0/rIDFBgqGqOevM9mCmvYOYl9o165pWKXtC2Y62EdNNM1+8 +xIkqUSn KHruI+vjJZdfLtCPHdP5hbszs25mh8FmorblcmKS2PTwg9L0ACMm1gDi/0ZaKnKlxdzWYIDZKvhqRZIecw2VAMXqCRlxr4S9/Q++v+6DxSM7OHAdvCYtKncR6/aP+FrlHDuf1AsYR+WBKKfSzw26I3cfVQ2kIZVR6mX04g7XxdOcsVZJ11eWowfy6Twxrryj9q883eP8eZSIEY3MDHDdgs/BxiuBWfcw2PAk7KvOIG3hP/JodHpu4PQoJARNk/aGuDxzMmULLoArj4IWPahNLwBfbXf/95zeMkyXes13grSmGgwRg34WjZmNfHSZAd+MG+O5svI02spRibLzn1iHQkv2i360DASBeRd37ENnoMuqX+S3C07rnatLM8h0XduFZbGGGB6IIA/qj9NuYJqCLfNfD+W21UfETMQYI1W9eFoG0S6yweodkiy5SOj/Zm8Fggfo6hOBma/eGLKiSPkWWTmDWGtzU2sNLCNueI8l3UzB9NAmwIu51kotOnypeQmM3rZMv/8tAysvbUSDSQpitSJA6s3gOyyU5y5Vb3IzIzHJ7VqpK5Tu0DoaEwQ== 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 Thu, Dec 07, 2023 at 02:33:19PM -0500, Liam R. Howlett wrote: > mas_prev() was setting the ma_underflow condition when the limit was > reached and not when the limit was attempting to go lower. This > resulted in the incorrect behaviour on subsequent actions. > > This commit fixes the status setting to only set ma_underflow when the > lower limit is attempted to be decremented, and modifies the testing to > ensure that's the case. > > Signed-off-by: Liam R. Howlett Is this is related to the report[1] I forwarded? If so, please add these tags too: Reported-by: Linux Kernel Functional Testing Closes: https://lore.kernel.org/all/CA+G9fYs-j2FYZSFSVZj48mgoM9gQd4-7M2mu2Ez3D1DqDdW2bQ@mail.gmail.com/ [1] Thanks either way! -Kees > --- > > Andrew, > > This should be clean to squash into 7f79fdb1d94d7 ("maple_tree: separate > ma_state node from status.") which is currently in your mm-unstable > branch. > > Thanks, > Liam > > > lib/maple_tree.c | 16 ++++++++++++---- > lib/test_maple_tree.c | 9 +++++++-- > 2 files changed, 19 insertions(+), 6 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 89f8d21602774..47f2a7a973852 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -4432,6 +4432,9 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) > mas->last = mas->index - 1; > mas->index = mas_safe_min(mas, pivots, mas->offset); > } else { > + if (mas->index <= min) > + goto underflow; > + > if (mas_prev_node(mas, min)) { > mas_rewalk(mas, save_point); > goto retry; > @@ -4452,15 +4455,15 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) > if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > goto retry; > > - if (mas->index <= min) > - mas->status = ma_underflow; > > if (likely(entry)) > return entry; > > if (!empty) { > - if (mas_is_underflow(mas)) > + if (mas->index <= min) { > + mas->status = ma_underflow; > return NULL; > + } > > goto again; > } > @@ -4596,7 +4599,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) > if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > goto retry; > > - if (pivot >= max) { > + if (pivot >= max) { /* Was at the limit, next will extend beyond */ > mas->status = ma_overflow; > return NULL; > } > @@ -4611,6 +4614,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) > else > mas->last = mas->max; > } else { > + if (mas->last >= max) { > + mas->status = ma_overflow; > + return NULL; > + } > + > if (mas_next_node(mas, node, max)) { > mas_rewalk(mas, save_point); > goto retry; > diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c > index 15fbeb788f3ac..29185ac5c727f 100644 > --- a/lib/test_maple_tree.c > +++ b/lib/test_maple_tree.c > @@ -3294,8 +3294,8 @@ static noinline void __init check_state_handling(struct maple_tree *mt) > MT_BUG_ON(mt, mas.last != 0x1500); > MT_BUG_ON(mt, !mas_is_active(&mas)); > > - /* next:active ->active */ > - entry = mas_next(&mas, ULONG_MAX); > + /* next:active ->active (spanning limit) */ > + entry = mas_next(&mas, 0x2100); > MT_BUG_ON(mt, entry != ptr2); > MT_BUG_ON(mt, mas.index != 0x2000); > MT_BUG_ON(mt, mas.last != 0x2500); > @@ -3360,6 +3360,11 @@ static noinline void __init check_state_handling(struct maple_tree *mt) > MT_BUG_ON(mt, entry != ptr); > MT_BUG_ON(mt, mas.index != 0x1000); > MT_BUG_ON(mt, mas.last != 0x1500); > + MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */ > + entry = mas_prev(&mas, 0x1200); /* underflow */ > + MT_BUG_ON(mt, entry != NULL); > + MT_BUG_ON(mt, mas.index != 0x1000); > + MT_BUG_ON(mt, mas.last != 0x1500); > MT_BUG_ON(mt, !mas_is_underflow(&mas)); > > /* prev:underflow -> underflow (lower limit) spanning end range */ > -- > 2.40.1 > -- Kees Cook