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 D9BEDC021B2 for ; Sat, 22 Feb 2025 09:25:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F2C6E6B007B; Sat, 22 Feb 2025 04:25:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id EDD256B0083; Sat, 22 Feb 2025 04:25:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D7C7A6B0085; Sat, 22 Feb 2025 04:25:02 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id BB3766B007B for ; Sat, 22 Feb 2025 04:25:02 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id E27C4C0F00 for ; Sat, 22 Feb 2025 09:25:01 +0000 (UTC) X-FDA: 83147046402.06.BA96C97 Received: from mail-ej1-f45.google.com (mail-ej1-f45.google.com [209.85.218.45]) by imf15.hostedemail.com (Postfix) with ESMTP id EE9B0A0002 for ; Sat, 22 Feb 2025 09:24:59 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=kXsfpmGk; spf=pass (imf15.hostedemail.com: domain of lilithpgkini@gmail.com designates 209.85.218.45 as permitted sender) smtp.mailfrom=lilithpgkini@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740216300; a=rsa-sha256; cv=none; b=8D4V6nqM2JRD2oXyxnxLgZDkFg6H7M0UI7xJ37AmJDJQ3W5rVo1VVkovzKFanaO6mvfn1x 8M7zvIp3mcoRSVHUylGmAA5BD8fwTwXBRYN4mWkpswiScC/TDHBtXo6//BuUKNQNQpPSRD 06D9GvRBauVtPd4sbnsPRcC18te8AEc= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=kXsfpmGk; spf=pass (imf15.hostedemail.com: domain of lilithpgkini@gmail.com designates 209.85.218.45 as permitted sender) smtp.mailfrom=lilithpgkini@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=1740216300; 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=3yD6gjY6AcVo0spaca0J4KOetQq7mGQ5hrKWIAthpNI=; b=JjSuEzGlC8dUPOn5RWDUJI+kpKDt85B2LYt9otpikaXJ7s+DX4cpyIYUqFdCUqWiAZBJey k6bL7TlLP0ypzsWeLmdU6zt06thwuR+qKKR0izFGbnhxTIdyzuFRZBmC7+bfv0NDpVsSx+ SZ39XnFB2BAXalkwqVFFKi/I19PFSG4= Received: by mail-ej1-f45.google.com with SMTP id a640c23a62f3a-aaeec07b705so463132466b.2 for ; Sat, 22 Feb 2025 01:24:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1740216298; x=1740821098; 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=3yD6gjY6AcVo0spaca0J4KOetQq7mGQ5hrKWIAthpNI=; b=kXsfpmGkKI0lHBMgL1wW65qSv/k1xFexI+Pd3MCmCxdIY5JEemE1Rq8sArtOFALNeg 5yGtLffsGm7zwb6AMAcHFr0DNOmJ9SW2sDzomDbRcpyymluWkv6dl4X7HXW3i8RMbxdi +3yieS0TiBmJ59SqwSkHZAz+mT92rofkg2Bpxspd75gGpIlP4wBtHJvzA0ZdNN48TOF9 Oyed0UDBbIbY1r2QXNd7VwWxB76N4JzwzrETezl/DiCSpiyvjXJfkZ4tNZSupwdUmhSJ GE02+/8yKGaHMP3IL4Ql0d2OKU4OybK0Drd4Kas/P/0SQmbbXyD110Qveo4mEAIG5z3E 40+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740216298; x=1740821098; 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=3yD6gjY6AcVo0spaca0J4KOetQq7mGQ5hrKWIAthpNI=; b=kMN7k2Yeuhqdga05+O3nWylHDy8O74qCyZG54BDQbxIFuG/MH8RaTLVRwuxD8CkBU0 PzKwRgDNhSFWfplb075nifGMatJ0ARk+8b/U02IlrWQWM9bDqumRab9+BE+SAUP85d2r FJM2RUKvs0mLZdBEbfyn44SXojgkdPoRCqFv/phyhgixlEpQWSscP19ePmcJ4fzRZPqO oJG7tmjilf56JLK0bJ6UsCrMnQBpO77Z+B//E2RRIbZjxmhX4F5CpgNYHRzeqejvKEZu m4iYpopeyu9FGaf88TJvEvHEfG4kQ81HXpWpcn+Rqzydqv1dfwAutDR7uOu54gi3oADZ 7LMQ== X-Forwarded-Encrypted: i=1; AJvYcCUr9HCqSCLu7hu7zLXrb4NgvawtnWYZKYKXUThrLZVeft9zSvoxFuSXiQnVDu4zkjSQjn44sVbeMw==@kvack.org X-Gm-Message-State: AOJu0YyCDLUFQVU7Y5EFNjIiBw1oBJO0ka8btirCNYJve8GwENP+3KXV 5uLd591lY/rG+GxDGUfbIn/Ki9Xgq/yvsiptyYT+V7K+WUNYJAQR X-Gm-Gg: ASbGncvPUbEXLTwfk1o7NUGFZcPunnR++CAFdKK+VhXqO6/68vyHHJa7iRlYv3KC03d 2loh9BbF5NZK/IAxrKjYmEalPMr8dRe37QCZsM1Brdvdl4w6Ep3Q5ZAEV4Js0aEljajEuOZuHue Nw6bPQEmLPHZKzcvs8ewB2zowxWQAaI4lNq2xCsA2QaaCs8sETAhAA0iqeevCHGFl8ottYogqlF fH/tsvwr2IqqvliN7TqE8xFJACnfPhdAEdLhhyGcSKhEAf3y2b3rpyZq+DC9i8FHp5kW3KI8xAq +HejstAKiXJo0LLr5CYh6/gZLEXCPw== X-Google-Smtp-Source: AGHT+IEut/GnIJBBNogqaoK2P1dFuBK0cH+uLmMcDLZBmoF4AfCfhulOqPyPmL25bvVwu8oP6DK0SQ== X-Received: by 2002:a17:907:6d05:b0:abb:cb01:f3b7 with SMTP id a640c23a62f3a-abc0d988619mr611112466b.1.1740216297857; Sat, 22 Feb 2025 01:24:57 -0800 (PST) Received: from localhost ([2a02:587:860d:d0f9:2a79:b9e6:e503:40e9]) by smtp.gmail.com with UTF8SMTPSA id a640c23a62f3a-abb77551c60sm1408859466b.63.2025.02.22.01.24.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 22 Feb 2025 01:24:57 -0800 (PST) Date: Sat, 22 Feb 2025 11:24:56 +0200 From: Lilith Gkini To: Harry Yoo Cc: Christoph Lameter , Pekka Enberg , David Rientjes , Joonsoo Kim , Andrew Morton , Vlastimil Babka , Roman Gushchin , Hyeonggon Yoo <42.hyeyoo@gmail.com>, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist() Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Rspamd-Queue-Id: EE9B0A0002 X-Stat-Signature: dzysrzbn1dp13mau6yom18ob6z9chhco X-Rspam-User: X-Rspamd-Server: rspam10 X-HE-Tag: 1740216299-89394 X-HE-Meta: U2FsdGVkX19hR7GKsc2hEakaczNH3Qh43EYOHET1GT3yY5599qUksZXZtWitJ0vWdY1e1A7HZl+Zft8iEBQoDbwvI8qX3mJKl9kyk92Yiv9mSOyn/m815HEN4CcBmiAYY+DeDCwjr4C3yvq8mILkL6uFe/rGjSY1KSq8h3cOVM2J2BtO8u8l84KOMXWoy6tOqrs8BF/LWFnfkJNkhcpzJT7yV8zVj46arHpKK2I1fjhoKHj2RGNgFhhxpRPNCWHSPhN7A8vKocDIL0FBOSCotXitts1pbZWolnqMi61nL8NKaT8XFdYc0IBzPG0hX8fbTqJU7zMMBKGeweCuSEUF/4kIW8ntLBLbddzz5bs3X2Sp7a6rtpEVqbSIC8WnO9dmwraw9etDlFeZA0g2H251yJo5Y3WDqZra7DTVK7AA0n8r9oGkt76ViL17gxHOis9KLe0gKhgLWsQKY0ZmVNed2rt8EsUTzUiu8kYOiQI3a1ELTr8JFg7230ic/5NJeDRCWsN9e6lXCh8awVr5kll4CoJ24fzcYnTsxlEU1HOx0mXQahfzmA8aadT2bK0z1VFbSN+W4jrISPuGdRd0yn0stFoAFChmg9EdDXG4v4c9crBXh8FPoAznqHuT3S2aG88Z/bmsdBqhyW6RwDR7o3PeO96TNRBs3QPBPx96bW1TY4JtSAI0dBCgra3yrO9ZoWX/CCVucsdrVhcLTX4GhyyqXvuVi4R/vN3NdvX64JTfKOuIdZQ/EcIgZCCzkkw83qudSQKWUMOFzd7v1JmRaJdCANXorL12EFwinbf/Y5zUvf1CerlYTQphEpygb/65HZ5tA8pxz+LMthYmUV0Lc/UzOWtrm0G2csOnC3ELejaPrOo9rhbvgWg6JSyA69eN7fzxG5oPdCRGFCtqR1Q9G/9BdI5tdXv64AUeWX0tET0KoAHZRUbChI8NskD/3/OWsFnR7GlcGTFbu7K49pXitfz rQ+nWEP+ Y87+CKBf0vXVmgE/fhWhhrmwNxfudDSZruw1I52Ekdb+5ZWkFZCITzlRVpMj6W5HtV++I4TGtUTKKGkWkltrLvp5E2ZsDdLPEwAwpMk4v/25BdSYM8vIPD2rT7eYXnhqQxYAE5mCTKkLR6Fbicts1EheOa/g3xnA+T3kbpeQ4XuLOSFGjxeQU270lV2F4Mm6wAggTBb6LgzqzTXKKudXz2IU3SLbaqvxqF0f2SpTqbtHJUvbCctB8NoP9M2NCr0WwizXs9Z4pQjCTohVnVoKBDjuCeuzdaW1iCYoyvF42tFCIvJKM+9KT0Zifx81ih0Rf+MY+SVEEnVn6hwBDPyGDdpyz0HD+59fgz2L6oyO2VvCzGDWDDjYoKwhmI82+P3deF3B9pzLRoke4f9YpvBDpQRA43lW3a0zjMtKKme/2zuT5KdVGOqiDjNiBQgvrj9EcN+oDyR+x0Y0BcQMN9riBXSWaNFLZFfbYhV7QXYHAMOrOeUCSHk8Wz84adpCzMrmHuyr6LlFGaTbBQMeyuc/slLxpL/BDmg+vJcT3D8jUSBeS4P5e/9FRpHVdqYgYz2F7apS8QZP8Rk4sBMLXfx9NLoDALZA83OP1hA6PUg9/DFX/2PA= 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 Sat, Feb 22, 2025 at 12:58:20PM +0900, Harry Yoo wrote: > On Fri, Feb 21, 2025 at 04:57:24PM +0200, Lilith Gkini wrote: > > On Thu, Feb 20, 2025 at 06:21:14PM +0900, Harry Yoo wrote: > > > On Thu, Feb 20, 2025 at 05:20:00PM +0900, Harry Yoo wrote: > > > > On Sat, Feb 15, 2025 at 06:57:01PM +0200, Lilitha Persefoni Gkini wrote: > > > > > The condition `nr <= slab->objects` in the `on_freelist()` serves as > > > > > bound while walking through the `freelist` linked list because we can't > > > > > have more free objects than the maximum amount of objects in the slab. > > > > > But the `=` can result in an extra unnecessary iteration. > > > > > > > > > > The patch changes it to `nr < slab->objects` to ensure it iterates > > > > > at most `slab->objects` number of times. > > > > > > > > > > Signed-off-by: Lilitha Persefoni Gkini > > > > > --- > > > > > mm/slub.c | 2 +- > > > > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > > > > > diff --git a/mm/slub.c b/mm/slub.c > > > > > index 1f50129dcfb3..ad42450d4b0f 100644 > > > > > --- a/mm/slub.c > > > > > +++ b/mm/slub.c > > > > > @@ -1435,7 +1435,7 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search) > > > > > int max_objects; > > > > > > > > > > fp = slab->freelist; > > > > > - while (fp && nr <= slab->objects) { > > > > > + while (fp && nr < slab->objects) { > > > > > > > > Hi, this makes sense to me. > > > > > > > > But based on what the name of the variable suggests (nr of objects), > > > > I think it makes clearer to initialize it to 1 instead? > > > > > > Oh, actually iterating at most (slab->objects + 1) times allows it to catch > > > cases where the freelist does not end with NULL (see how validate_slab() > > > calls on_freelist(), passing search = NULL). > > > > > > It's very subtle. A comment like this would help: > > > > > > /* > > > * Iterate at most slab->objects + 1 times to handle cases > > > * where the freelist does not end with NULL. > > > */ > > > > > > -- > > > Cheers, > > > Harry > > > > nr is the number of "free objects" in the freelist, so it should start > > from zero for the case when there are no free objects. > > Hi Lilith, > > You're right. It was an oversight. > > > Oh, you think its on purpose to catch edgecases, like a defensive > > programing sort of way? Huh, thats interesting! > > > > In that case it would prevent a case where every object in the slab is > > freed and the tail of the freelist isnt NULL like it should be, maybe because > > of some Out-Of-Bounds write from another object, or a Use-After-Free. > > If that pointer is some gibberish then the chech_valid_pointer() check > > on line 1441 will catch it, set it as NULL in line 1445 with > > set_freepointer() and then break from the While and continue with the > > rest of the program. nr will correctly remain as the number of freed > > objects and the freelist will have a NULL in its tail, as it should! > > Yes, but corrupted freelist implies that the number of the free > objects (nr) may be invalid? (if free pointer in the middle is > corrupted). > > But that's another story... > > > But if the pointer isn't some random address and instead is an address in > > the slab, lets say as an example the address of a free object in the > > linked list (making the freelist cicrular) it wont get caught by the > > check_valid_pointer() since technically it is a valid pointer, it will > > increment nr to slab->objects + 1 and then exit the While loop because > > it will fail the conditional nr <= slab->objects. > > > > Then later on, in line 1470 slab->objects - nr will be -1 which is not > > equals to slab->inuse and enter the If case where it will set the > > slab->inuse to -1, but because slab-inuse is an unsinged short it will > > be stored as 0xFFFF, ie 65535, corrupting the slab struct with an > > unreasonably large "inuse" value. > > While (slab->inuse + nr != slab->objects) will prevent overflow, > I think either way is functional, because it prints error when there are > more or less objects than it should have on the freelist. > > > You mentioned validate_slab(), I assume you are refering to how it > > searches for NULL when it calls on_freelist() and if it does find NULL > > in the freelist it will return 1 (basicaly TRUE). > > Yes. > > > In the example where every object is freed it will return TRUE > > regardless if NULL is in the freelist or not, because on_freelist() > > returns search == NULL if it doesnt find the search in the freelist. In > > this case it would be NULL == NULL which is TRUE again. > > This will have the same behavior even if we remove the equals sign from > > the While, like the Patch suggests. > > Ok. that's actually a good point. > > But as validate_slab() expects to return false if there is no NULL > in the freelist, I think we need to fix on_freelist() to support that? > > I'm not sure why on_freelist() returns (search == NULL). > It has been there since the beginning of the SLUB allocator > (commit 81819f0fc828). > > Since commit 53e15af03be4 ("slub: validation of slabs (metadata and guard > zones)"), validate_slab() started passing NULL to on_freelist(). > Looks like passing NULL to on_freelist() has never worked as intended... > > Can we return false in on_freelist(), if it could not find > target object (search) in the loop? (need some testing to verify, > though...) regardless of search is NULL or not? > > > I am still pretty new to this so I apologize for any mistakes. I > > appreciate the feedback! > > Your questions are valid. > > > Is it ok to refer to lines of code, or should I copy paste the entire line? > > I prefer copy-and-paste because sometimes it's not obvious what commit > is HEAD of your repository. > > > I understand that even small changes could have a huge effect to some > > other function or subsystem in ways that might not be obvious to someone > > not as familiar with the codebase. > > That's why we need to be as careful as possible and test the code ;-) > > > I hope I am not coming off to strong or anything. > > It's ok. I don't think so. > > -- > Cheers, > Harry Hi! > Since commit 53e15af03be4 ("slub: validation of slabs (metadata and guard > zones)"), validate_slab() started passing NULL to on_freelist(). > Looks like passing NULL to on_freelist() has never worked as intended... Haha, yeah, it would seem like. > Can we return false in on_freelist(), if it could not find > target object (search) in the loop? (need some testing to verify, > though...) regardless of search is NULL or not? You are right, I should write a test driver that uses on_freelist() and analyze it through GDB with QEMU to see how it actually behaves when I have the time, but just looking at it I am thiking that something like `return fp == NULL` could replace the `search == NULL` and check if NULL is at the end of the freelist or not, in addition to my original patch. The reason I m saying this is cause the While loop is looking through every non-NULL freelist pointer for the "search" pattern. If someone wants to search for NULL in the freelist that return 1 will never trigger, even for normal freelists. If "fp" was ever null it wouldn't re enter the loop. Thus the result of the function would be search == NULL because the original writers assumed the freelist will always end with NULL. As you correctly pointed out there might be a case where the freelist is corrupted and it doesnt end in NULL. In that case two things could happen: 1) The check_valid_pointer() catches it and fixes it, restoring the corrupted freelist. 2) The check_valid_pointer() fails to catch it and there isn't any NULL. In the first case the problem fixes itself and thats probably why validate_slab() worked fine all this time. The second case is pretty rare, but thats the case that validate_slab() wants to rout out when it checks the `!on_freelist(s, slab, NULL)`, right? Also to make my added suggestion of `return fp == NULL` work in the first case (since it does corrrect the freelist we want it to now return TRUE) we could also add a line that nulls out the fp right after the `set_freepointer(s, object, NULL);`. But words are cheap, I should test it out dynamically rather than just reading the code to see how it behaves. Feel free to also test it yourself. I know I am supposed to send a proper Patch with the multiple added lines, but for now we are mostly brainstorming solutions. It will be better to see its behavior first in a debugger I think. I hope I am making sense with the thought process I outlined for the return thing. I probably shouldn't be writing emails ealry Saturday morning, haha. Also I really appreciate the kind feedback! The Linux Kernel is infamously known for how rude and unhinged people can be, which can make it a bit stressful and intimidating sending any emails, especially for someone starting out such as myself. Thank you.