Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:6 as permitted sender) client-ip=2620:137:e000::3:6;
Date:   Fri, 8 Dec 2023 12:54:02 -0500
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Kees Cook <keescook@chromium.org>
Cc:     Andrew Morton <akpm@linux-foundation.org>,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, Mark Brown <broonie@kernel.org>,
        Naresh Kamboju <naresh.kamboju@linaro.org>,
        linux-kselftest@vger.kernel.org,
        Linux ARM <linux-arm-kernel@lists.infradead.org>,
        kft-triage@lists.linaro.org, regressions@lists.linux.dev,
        Will Deacon <will@kernel.org>,
        Catalin Marinas <catalin.marinas@arm.com>,
        Dan Carpenter <dan.carpenter@linaro.org>,
        Eric Biederman <ebiederm@xmission.com>,
        linux-next@vger.kernel.org
Subject: Re: [PATCH] maple_tree: Fix mas_prev() state separation code
Message-ID: <20231208175402.hvy2htzs45oa5psx@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Kees Cook <keescook@chromium.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, Mark Brown <broonie@kernel.org>,
        Naresh Kamboju <naresh.kamboju@linaro.org>,
        linux-kselftest@vger.kernel.org,
        Linux ARM <linux-arm-kernel@lists.infradead.org>,
        kft-triage@lists.linaro.org, regressions@lists.linux.dev,
        Will Deacon <will@kernel.org>,
        Catalin Marinas <catalin.marinas@arm.com>,
        Dan Carpenter <dan.carpenter@linaro.org>,
        Eric Biederman <ebiederm@xmission.com>, linux-next@vger.kernel.org
References: <20231207014104.n6vul2ylgqjnsfia@revolve>
 <20231207193319.4025462-1-Liam.Howlett@oracle.com>
 <202312071302.99D5B1BB76@keescook>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <202312071302.99D5B1BB76@keescook>
User-Agent: NeoMutt/20220429
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?DvOs2WnHxYRg4dyoPmMZBJQ15vlg1xTK0Hs5ZAki2hOCEAvmvbJswA9bm9ds?=
 =?us-ascii?Q?6kdYneEj7gAO3ep7bpRxHcadlEJdu+lRiGvXbYU0czvxPak5lXi7PX2B0Lx0?=
 =?us-ascii?Q?ORNSItzi4CSPmKKidyOTFRQaoQIogXuVKkGLn7Y2X6oSHXBiNzUOEzVThuB4?=
 =?us-ascii?Q?m/IqLgUdERrxvirjWs2THpUA/U6eJxhruS3Ljpw9HbrIIdi/Dnu8qyq2P0/j?=
 =?us-ascii?Q?5gTeLSlSf+17rmr6lSOjKWl5aXWuNch0l/QQNuQ3Z7wsWNAiu3kQU15VkVP1?=
 =?us-ascii?Q?0qrhlE5HdmtY5PPodJlShZRtg/vodmR1h2Ja6VJSAidrOKssqtlnBycGQrc7?=
 =?us-ascii?Q?lYn3dSnt0du9F4RhLbGJqcD4vPZPUTbU1FtaAys3yUnF4QGDgWgxWD1XU17w?=
 =?us-ascii?Q?gKgZNr27ciEvdN5XkM7rofPX0rPooZJux811jyyL1x0NRynsN/PVFeTiiaGj?=
 =?us-ascii?Q?2SjFc+qZuvkv0GOwOclzFWIBfwL0FvjS+AkW4dtndpslm24i7wtzC4v4Yxxc?=
 =?us-ascii?Q?hYhHHtEGLusXbpB58UVKptjclOh/uZVd7tEiYFHZZtv2F4cZdBrbIJdTQ8jb?=
 =?us-ascii?Q?tzUv3LJDXwEtI3HDJ0/XuC4a3Zv5/yIFOV1DGCvYwvsBOfkB16V5xGp3gJsi?=
 =?us-ascii?Q?hlQg+8RddutlM1/Ayc06fAGh73jSzHyvGdpr7l2Y3QW4KnQrmkxJhDs1qQsj?=
 =?us-ascii?Q?CHtQ0xjlTXmPoQtQ593C/jvSUL0R8tPBmsL06uvH3mkwPLUCj/UlfzZmlgqf?=
 =?us-ascii?Q?X1Wxswr8XGbLPhbRyg8cs2gEwJ9hNYFNPEJty9JUvT+A/+XKeI+DKNerokkA?=
 =?us-ascii?Q?i5jrQW+eH3SoG5DN/N/M/ra8AhjdJsyMoAWQ+WX3QxlA3PBDEU/5CuBOaL3o?=
 =?us-ascii?Q?1LWF3SpPuHod3em5V6rgPucABc1Ug74JxUAVs7XkQDHwop0sGC8f5iirjFPE?=
 =?us-ascii?Q?LWoRwfGnTc5qvYYJ1iUGZQorjv1VeoJ7rH+HJ7jReKDgcYugyAcYizeV6OwI?=
 =?us-ascii?Q?u8R0YN7YIxba7aPStEN6CtnEsPutYNYPDqZeZRLn+niIIMp9dMSAFgUtnYrN?=
 =?us-ascii?Q?9UmhMlAJDfnyZrLTt8cUay6cmZcuQjimyEoPW7eoW3M4zwBFio7i+Cz8yGZ2?=
 =?us-ascii?Q?Ji+HI9B9qFHsH3MSlKaL4MqEeSAY3CKznyheF5RVEqv6JqHIr7gW5nnmw3ON?=
 =?us-ascii?Q?C5JjaKvyHAPAGLA+7JqUHH25h4CIM3IGHo4nVfwWqPD/KqmjPpd+9efMVp63?=
 =?us-ascii?Q?lZaPirGzKz0R4x5KYi5Al4wQB8js4v72hq1vtxrXMHsmnvcGWFEj6nGteLLY?=
 =?us-ascii?Q?eJAnD6nzTPKVt7x/GvbUZcRbGMjPOT32Ha3GpdRQKmLO+uKREKvmab8mfiKv?=
 =?us-ascii?Q?NZR2eJTLR9vjMAmeoKrmShdcn+xUqmMzNYrN1j6fXNHirFRrhxS3cyhD33i9?=
 =?us-ascii?Q?PJ5evRgPb9IpvmXLmv1a4uK04CqoWSJDoeHzM/CrLbEauldxS7J+AASTQ4+r?=
 =?us-ascii?Q?6B5wpIkax0S6bPd8TYkhKIaZ4iCuaP0mbKy7hU+41ehfqVRKCU8kfTtIcmty?=
 =?us-ascii?Q?iefXtka7Gkuh4ZnBlYOnGUxVDpedRl+/Ilbkoim1?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?5I6eJVDrGytBeEqfKyNJSa8RSo38rkyy0tA0jIrvASo3LmOxe1Yu1I+Afhng?=
 =?us-ascii?Q?HTsDd9mgGqrr7VJc5kRvk5ooklR7kd0yrrREyr6aR/tzy2rRIdqPGoH65U7Z?=
 =?us-ascii?Q?l0kLngmMnS7XOsr3TnDZdQzQb5bslNDoKIBCG3uOs62nSA7LCt0aGKr1YRja?=
 =?us-ascii?Q?aTInFyM1LKJpS7q1Zy8txR2ucO6h5TEd6GKEmAM8Co4Xke3YyLUWFVWu6V7r?=
 =?us-ascii?Q?B3VKNvN1nHoWvJKuEyfy4gc23Epx/DuOJD0ZQsC2ODqt2gpPDWVmvQkfAp+5?=
 =?us-ascii?Q?9m5yQW3hhe3n3aENuDNXvEAP4DPFBm1tdB5m8wwIak0UwBQjTsAqehbMq2rt?=
 =?us-ascii?Q?Vf5NwkrYhQxQL/tOjL+QSqMA0IcYJ2KvzBzqCCYt6JTlbgILmlRwM6L7Vn5F?=
 =?us-ascii?Q?Gqf5Nu/VBigz6v6fZl7ADgDHOXS5fBOp9k/9fSrKzl0eXlJFbuIaogJ4HEbl?=
 =?us-ascii?Q?YBoqUNRMOLrldE/GxUiU+idTXeNepCnIOtJOPtHcjsr8Cok8ejq+rBsJbY4J?=
 =?us-ascii?Q?OtvdJsSvn8t7NInN8h2nXznYYGU/Soex8wvZXj4IFu4aid7TAYGWcb1PZ+yW?=
 =?us-ascii?Q?GWbk1KlQ1AlxV+hCY34tCCjPGSHl0rK3Q8vUcBw3wNRV2qoeBnE5rE2PNu4Q?=
 =?us-ascii?Q?1O70Xa0F5LZuMUKwLBIKBmn5HTI2wU/tyUw70jTaP++YGGxDbVnt0lFJLh9R?=
 =?us-ascii?Q?tG+uXK0yiD84obkBM2JIOWfqo9LUzL+2f/orukTdSHl+LEH5+TcpkPFnLPcY?=
 =?us-ascii?Q?sfEJSTlN+7YnNPZ7bgzBkIN4ZZ9HSEJSBnGJDHJbcpSAKl1hUDPofPOnHREd?=
 =?us-ascii?Q?wV+uqDNtC0dn/8iqDtQWmBDSWpGTbaDwif4L4MCaUMc8luDP2leLWLPw2XHf?=
 =?us-ascii?Q?mnr3TbzZq83w9ctj4fZnz3+875IXizdYbF07D4yb1AgUWFBsnAwIP57MXJss?=
 =?us-ascii?Q?Mcz8cZl3p4BhNcIAnbqTgI98OYZgKVTYopAmtjby45Pfms322zUTIwqTSrQm?=
 =?us-ascii?Q?q4MjtMpzUTKTznJbfqfJJCI9UhI5R1dOKTG7AeBxBkjSiSYcz5HZmTwv48UH?=
 =?us-ascii?Q?CMEw4gUy+snKTkP17pHC17/q6zyrkB/HxczYVNzSA97UYVXNUFIqLD1B/70u?=
 =?us-ascii?Q?X2ttCSEFot12?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4652afb2-d85b-4d9e-5807-08dbf816ab7f
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 08 Dec 2023 17:54:05.4938
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: +EhxsrkIHnf13i4qaBqyNjBNDelfLQlIHTv5DQDXAkn6MhVY2v5YaR8DGLvMAJaL1FkOuLJ4gp4NvdT3DfYw6A==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW4PR10MB5752
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.997,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-12-08_12,2023-12-07_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 spamscore=0 malwarescore=0
 bulkscore=0 mlxlogscore=999 phishscore=0 suspectscore=0 adultscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000
 definitions=main-2312080148
X-Proofpoint-ORIG-GUID: WH9UxD5ozggxI_0sRq2IZJ2AYYOdKHqC
X-Proofpoint-GUID: WH9UxD5ozggxI_0sRq2IZJ2AYYOdKHqC
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on pete.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (pete.vger.email [0.0.0.0]); Fri, 08 Dec 2023 09:55:17 -0800 (PST)

* Kees Cook <keescook@chromium.org> [231207 16:04]:
> 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 <Liam.Howlett@oracle.com>
> 
> Is this is related to the report[1] I forwarded? If so, please add these tags
> too:
> 
>  Reported-by: Linux Kernel Functional Testing <lkft@linaro.org>
>  Closes: https://lore.kernel.org/all/CA+G9fYs-j2FYZSFSVZj48mgoM9gQd4-7M2mu2Ez3D1DqDdW2bQ@mail.gmail.com/ [1]
> 

Ah, yes it is.  I missed these tags. Sorry about that.

I have another patch to send in regards to this area on the
mmap_region() side but it's less urgent.  I'll Cc you on that one as
well.


> 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