[PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilitha Persefoni Gkini]

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 <lilithpgkini@gmail.com>
---
 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) {
 		if (fp == search)
 			return 1;
 		if (!check_valid_pointer(s, slab, fp)) {
-- 
2.48.1

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

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 <lilithpgkini@gmail.com>
> ---
>  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?

--
Cheers,
Harry

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

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 <lilithpgkini@gmail.com>
> > ---
> >  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

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

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 <lilithpgkini@gmail.com>
> > > ---
> > >  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.

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!

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.

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).

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.


I am still pretty new to this so I apologize for any mistakes. I
appreciate the feedback!
Is it ok to refer to lines of code, or should I copy paste the entire line?
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. I hope I am not coming off to
strong or anything.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

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 <lilithpgkini@gmail.com>
> > > > ---
> > > >  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

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

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 <lilithpgkini@gmail.com>
> > > > > ---
> > > > >  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.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

On Sat, Feb 22, 2025 at 11:24:56AM +0200, Lilith Gkini wrote:
> 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 <lilithpgkini@gmail.com>
> > > > > > ---
> > > > > >  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.

On second thought (after reading your email),
I think it should be (fp == NULL) && (search == NULL)?

When fp is NULL after the loop, it means (the end of the freelist
is NULL) AND (there were equal to or less than (slab->objects - nr) objects
on the freelist).

If the loop has ended after observing fp == NULL,
on_freelist() should return true only when search == NULL.

If fp != NULL, it means there were more objects than it should have on          
the free list. In that case, we can't take risk of iterating the loop
forever and it's reasonable to assume that the freelist does not               
end with NULL.

> 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.

Agreed.

> 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?

Yes.

> 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);`.

Why?
fp = get_freepionter() will observe NULL anyway.

> 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.

Yes, testing is important, and you should test
to some extent before submitting a patch.

> 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 think it's generally considered good practice to discuss before
writing any code.

> 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.

You're welcome ;-)

-- 
Cheers,
Harry

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Mon, Feb 24, 2025 at 09:00:14AM +0900, Harry Yoo wrote:
> On second thought (after reading your email),
> I think it should be (fp == NULL) && (search == NULL)?
> 
> When fp is NULL after the loop, it means (the end of the freelist
> is NULL) AND (there were equal to or less than (slab->objects - nr) objects
> on the freelist).
> 
> If the loop has ended after observing fp == NULL,
> on_freelist() should return true only when search == NULL.
> 
> If fp != NULL, it means there were more objects than it should have on          
> the free list. In that case, we can't take risk of iterating the loop
> forever and it's reasonable to assume that the freelist does not               
> end with NULL.
> 
> > 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.
> 
> Agreed.
> 
> > 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?
> 
> Yes.
> 
> > 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);`.
> 
> Why?
> fp = get_freepionter() will observe NULL anyway.
> 
> > 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.
> 
> Yes, testing is important, and you should test
> to some extent before submitting a patch.
> 
> > 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 think it's generally considered good practice to discuss before
> writing any code.
> 
> > 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.
> 
> You're welcome ;-)
> 
> -- 
> Cheers,
> Harry

Alright, I managed to run some tests through a debugger.

You are right, my code isn't correct, `return fp == search` should be
more appropriate.

So I think the right way would be to do these changes:
- 	while (fp && nr < slab->objects) {

-				fp = NULL;

-	return fp == search;

The first line removes the "=" so it doesnt iterate more times than
slab->objects.

The second line sets fp to NULL for the case where the code caught a
corrupted freelist (check_valid_pointer) and fixes it by setting 
the freepointer to NULL (set_freepointer). Now NULL will be in the
freelist.

The third line is the return value:
TRUE if the final fp we got happens to be the search value the caller
was looking for in the freelist.
FALSE if the final fp we got was not the same as the search value.

This should make the validate_slab() work right and if anyone ever uses
the on_freelist() again with some other search value other than NULL it
should also work as intended.


For my tests I wrote a kernel module that creates an isolated cache with
8 objects per slab, allocated all 8 of them and freed them. Then called
validate_slab_cache() with my cache and set a breakpoint at on_freelist().
From there I could set any value I wanted and observe its behavior
through GDB (I used QEMU and GDB-ed remotely from my host).
This way I didn't have to set a bunch of EXPORT_SYMBOL() and change
stuff to not static; It made testing a lot easier.

Here are the tests I did with this new change I just mentioned.

Note: By "full slab" I mean that I allocated every object in the slab
and freed them. By "partial" I mean that I only allocated and freed some
objects, but not every object in the slab, ie if the total objects can
be 8 I only alloc-ed and freed 7.

search == NULL
- full slab
	- correct tail				true
	- corrupted tail with garbage		false
	- corrupted tail with valid address	false

- partial slab
	- correct tail			        true
	- corrupted tail with garbage	        true
	- corrupted tail with valid address	false


search == some fake address
- full slab
	- correct tail			        false
	- corrupted tail with garbage	        false
	- corrupted tail with valid address	false

- partial slab
	- correct tail			        false
	- corrupted tail with garbage	        false
	- corrupted tail with valid address	false


search == some address in the freelist
- full slab
	- correct tail			        true
	- corrupted tail with garbage	        true
	- corrupted tail with valid address	true

- partial slab
	- correct tail			        true
	- corrupted tail with garbage	        true
	- corrupted tail with valid address	true


I apologize if am going into too many details with my testing, I just
wanna make sure I didn't miss anything.

If my proposed changes look confusing I can send a proper patch.
Should I send it in this chain as a reply, or send a new email
and add you as well to the cc?

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

On Mon, Feb 24, 2025 at 02:12:13PM +0200, Lilith Gkini wrote:
> On Mon, Feb 24, 2025 at 09:00:14AM +0900, Harry Yoo wrote:
> > On second thought (after reading your email),
> > I think it should be (fp == NULL) && (search == NULL)?
> > 
> > When fp is NULL after the loop, it means (the end of the freelist
> > is NULL) AND (there were equal to or less than (slab->objects - nr) objects
> > on the freelist).
> > 
> > If the loop has ended after observing fp == NULL,
> > on_freelist() should return true only when search == NULL.
> > 
> > If fp != NULL, it means there were more objects than it should have on          
> > the free list. In that case, we can't take risk of iterating the loop
> > forever and it's reasonable to assume that the freelist does not               
> > end with NULL.
> > 
> > > 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.
> > 
> > Agreed.
> > 
> > > 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?
> > 
> > Yes.
> > 
> > > 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);`.
> > 
> > Why?
> > fp = get_freepionter() will observe NULL anyway.
> > 
> > > 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.
> > 
> > Yes, testing is important, and you should test
> > to some extent before submitting a patch.
> > 
> > > 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 think it's generally considered good practice to discuss before
> > writing any code.
> > 
> > > 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.
> > 
> > You're welcome ;-)
> > 
> > -- 
> > Cheers,
> > Harry

Hi, Lilith.

If you don't mind, could you please avoid bottom posting and
reply with inline comments like how I reply to you?
It makes it easier to follow the conversation.

> Alright, I managed to run some tests through a debugger.
> 
> You are right, my code isn't correct, `return fp == search` should be
> more appropriate.
>
> So I think the right way would be to do these changes:
> - 	while (fp && nr < slab->objects) {
> 
> -				fp = NULL;
> 
> -	return fp == search;
>
> The first line removes the "=" so it doesnt iterate more times than
> slab->objects.

Yes.

> The second line sets fp to NULL for the case where the code caught a
> corrupted freelist (check_valid_pointer) and fixes it by setting 
> the freepointer to NULL (set_freepointer). Now NULL will be in the
> freelist.

Yes. but do we care about the return value of on_freelist()
when the freelist is corrupted? (we don't know if it was null-terminated
or not because it's corrupted.)

> The third line is the return value:
> TRUE if the final fp we got happens to be the search value the caller
> was looking for in the freelist.
> FALSE if the final fp we got was not the same as the search value.
> 
> This should make the validate_slab() work right and if anyone ever uses
> the on_freelist() again with some other search value other than NULL it
> should also work as intended.

Yes! that makes sense to me.

> For my tests I wrote a kernel module that creates an isolated cache with
> 8 objects per slab, allocated all 8 of them and freed them. Then called
> validate_slab_cache() with my cache and set a breakpoint at on_freelist().
> From there I could set any value I wanted and observe its behavior
> through GDB (I used QEMU and GDB-ed remotely from my host).
> This way I didn't have to set a bunch of EXPORT_SYMBOL() and change
> stuff to not static; It made testing a lot easier.
>
> Here are the tests I did with this new change I just mentioned.
> 
> Note: By "full slab" I mean that I allocated every object in the slab
> and freed them.

FYI in slab terms (slab->inuse == slab->objects) means full slab,
You probably meant empty slab?

> By "partial" I mean that I only allocated and freed some
> objects, but not every object in the slab, ie if the total objects can
> be 8 I only alloc-ed and freed 7.
>
> search == NULL
> - full slab
> 	- correct tail				true

> 	- corrupted tail with garbage		false
> 	- corrupted tail with valid address	false

Two falses because when the freepointer of the tail object
is corrupted, the loop stops when nr equals slab->objects?

> - partial slab
> 	- correct tail			        true

> 	- corrupted tail with garbage	        true

This is true because for partial slabs, the number of objects
plus 1 for the garbage, does not exceed slab->objects?

> 	- corrupted tail with valid address	false
>
> search == some fake address
> - full slab
> 	- correct tail			        false
> 	- corrupted tail with garbage	        false
> 	- corrupted tail with valid address	false
> 
> - partial slab
> 	- correct tail			        false
> 	- corrupted tail with garbage	        false
> 	- corrupted tail with valid address	false
> 
> 
> search == some address in the freelist
> - full slab
> 	- correct tail			        true
> 	- corrupted tail with garbage	        true
> 	- corrupted tail with valid address	true
> 
> - partial slab
> 	- correct tail			        true
> 	- corrupted tail with garbage	        true
> 	- corrupted tail with valid address	true

The result seems valid to me. At least, this is the best SLUB can do
while avoiding the risk of infinite loop iteration.

> I apologize if am going into too many details with my testing, I just
> wanna make sure I didn't miss anything.

No, it's ok ;-)

> If my proposed changes look confusing I can send a proper patch.
> Should I send it in this chain as a reply, or send a new email
> and add you as well to the cc?

You can either send a new email or reply to this email with
In-Reply-To header. And please cc SLAB ALLOCATOR folks in MAINTAINERS file
including me—I recently changed my name and email (previously Hyeonggon Yoo).

-- 
Cheers,
Harry

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Tue, Feb 25, 2025 at 07:08:09PM +0900, Harry Yoo wrote:
> On Mon, Feb 24, 2025 at 02:12:13PM +0200, Lilith Gkini wrote:
> > On Mon, Feb 24, 2025 at 09:00:14AM +0900, Harry Yoo wrote:
> > > On second thought (after reading your email),
> > > I think it should be (fp == NULL) && (search == NULL)?
> > > 
> > > When fp is NULL after the loop, it means (the end of the freelist
> > > is NULL) AND (there were equal to or less than (slab->objects - nr) objects
> > > on the freelist).
> > > 
> > > If the loop has ended after observing fp == NULL,
> > > on_freelist() should return true only when search == NULL.
> > > 
> > > If fp != NULL, it means there were more objects than it should have on          
> > > the free list. In that case, we can't take risk of iterating the loop
> > > forever and it's reasonable to assume that the freelist does not               
> > > end with NULL.
> > > 
> > > > 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.
> > > 
> > > Agreed.
> > > 
> > > > 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?
> > > 
> > > Yes.
> > > 
> > > > 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);`.
> > > 
> > > Why?
> > > fp = get_freepionter() will observe NULL anyway.
> > > 
> > > > 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.
> > > 
> > > Yes, testing is important, and you should test
> > > to some extent before submitting a patch.
> > > 
> > > > 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 think it's generally considered good practice to discuss before
> > > writing any code.
> > > 
> > > > 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.
> > > 
> > > You're welcome ;-)
> > > 
> > > -- 
> > > Cheers,
> > > Harry
> 
> Hi, Lilith.
> 
> If you don't mind, could you please avoid bottom posting and
> reply with inline comments like how I reply to you?
> It makes it easier to follow the conversation.
> 
> > Alright, I managed to run some tests through a debugger.
> > 
> > You are right, my code isn't correct, `return fp == search` should be
> > more appropriate.
> >
> > So I think the right way would be to do these changes:
> > - 	while (fp && nr < slab->objects) {
> > 
> > -				fp = NULL;
> > 
> > -	return fp == search;
> >
> > The first line removes the "=" so it doesnt iterate more times than
> > slab->objects.
> 
> Yes.
> 
> > The second line sets fp to NULL for the case where the code caught a
> > corrupted freelist (check_valid_pointer) and fixes it by setting 
> > the freepointer to NULL (set_freepointer). Now NULL will be in the
> > freelist.
> 
> Yes. but do we care about the return value of on_freelist()
> when the freelist is corrupted? (we don't know if it was null-terminated
> or not because it's corrupted.)
> 
> > The third line is the return value:
> > TRUE if the final fp we got happens to be the search value the caller
> > was looking for in the freelist.
> > FALSE if the final fp we got was not the same as the search value.
> > 
> > This should make the validate_slab() work right and if anyone ever uses
> > the on_freelist() again with some other search value other than NULL it
> > should also work as intended.
> 
> Yes! that makes sense to me.
> 
> > For my tests I wrote a kernel module that creates an isolated cache with
> > 8 objects per slab, allocated all 8 of them and freed them. Then called
> > validate_slab_cache() with my cache and set a breakpoint at on_freelist().
> > From there I could set any value I wanted and observe its behavior
> > through GDB (I used QEMU and GDB-ed remotely from my host).
> > This way I didn't have to set a bunch of EXPORT_SYMBOL() and change
> > stuff to not static; It made testing a lot easier.
> >
> > Here are the tests I did with this new change I just mentioned.
> > 
> > Note: By "full slab" I mean that I allocated every object in the slab
> > and freed them.
> 
> FYI in slab terms (slab->inuse == slab->objects) means full slab,
> You probably meant empty slab?
> 
> > By "partial" I mean that I only allocated and freed some
> > objects, but not every object in the slab, ie if the total objects can
> > be 8 I only alloc-ed and freed 7.
> >
> > search == NULL
> > - full slab
> > 	- correct tail				true
> 
> > 	- corrupted tail with garbage		false
> > 	- corrupted tail with valid address	false
> 
> Two falses because when the freepointer of the tail object
> is corrupted, the loop stops when nr equals slab->objects?
> 
> > - partial slab
> > 	- correct tail			        true
> 
> > 	- corrupted tail with garbage	        true
> 
> This is true because for partial slabs, the number of objects
> plus 1 for the garbage, does not exceed slab->objects?
> 
> > 	- corrupted tail with valid address	false
> >
> > search == some fake address
> > - full slab
> > 	- correct tail			        false
> > 	- corrupted tail with garbage	        false
> > 	- corrupted tail with valid address	false
> > 
> > - partial slab
> > 	- correct tail			        false
> > 	- corrupted tail with garbage	        false
> > 	- corrupted tail with valid address	false
> > 
> > 
> > search == some address in the freelist
> > - full slab
> > 	- correct tail			        true
> > 	- corrupted tail with garbage	        true
> > 	- corrupted tail with valid address	true
> > 
> > - partial slab
> > 	- correct tail			        true
> > 	- corrupted tail with garbage	        true
> > 	- corrupted tail with valid address	true
> 
> The result seems valid to me. At least, this is the best SLUB can do
> while avoiding the risk of infinite loop iteration.
> 
> > I apologize if am going into too many details with my testing, I just
> > wanna make sure I didn't miss anything.
> 
> No, it's ok ;-)
> 
> > If my proposed changes look confusing I can send a proper patch.
> > Should I send it in this chain as a reply, or send a new email
> > and add you as well to the cc?
> 
> You can either send a new email or reply to this email with
> In-Reply-To header. And please cc SLAB ALLOCATOR folks in MAINTAINERS file
> including me—I recently changed my name and email (previously Hyeonggon Yoo).
> 
> -- 
> Cheers,
> Harry

Hey, Harry.

> Yes. but do we care about the return value of on_freelist()
> when the freelist is corrupted? (we don't know if it was null-terminated
> or not because it's corrupted.)

Oh! So we shouldn't care about the return value of on_freelist() if the
freelist is corrupted? My thinking was that if the check_valid_pointer()
detects a corrupted freelist and fixes it by setting the freepointer to
NULL it fixes it, so we would care about the result. But maybe if the
whole object_err() triggers, I think that causes an OOPs if I recall, we
should consider this as corrupted and we shouldn't care about what it
returns, cause something went terribly wrong?

I guess that sounds like a sound logic.

If that is how we should do this then yeah, my second suggested line is
moot and in my later patch I shouldn't include it.

> FYI in slab terms (slab->inuse == slab->objects) means full slab,
> You probably meant empty slab?

Thats fair. I was thinking more like "I allocated everything and then
freed everything in the slab, therefore the freelist will be full".
But hopefully since I specified what I meant it wasn't too confusing.

> Two falses because when the freepointer of the tail object
> is corrupted, the loop stops when nr equals slab->objects?

Yeah! Since the freelist pointer is corrupted and doesn't end in NULL
on_freelist() won't find a NULL, and in the case of the tail having
garbage that the check_valid_pointer() would normally catch, the code
won't catch it, because it's at the tail which would exceed the
slab->objects and the While loop will exit before that, since the
freelist* (not slab, as you pointed out) is full.

> This is true because for partial slabs, the number of objects
> plus 1 for the garbage, does not exceed slab->objects?

Yeah. That goes back to that second line I suggested in the previous
email. If the number of objects in the freelist is less than the
slab->objects and the corrupted freelist has some garbage address that
the check_valid_pointer() will catch, it will set it to NULL instead, and
as I said since the freelist now includes a NULL, my thinking was that
on_freelist() should return true if we were searching for NULL.

But if thats not how on_freelist() should work in a case of a corrupted
freelist and we don't add my second line that nulls the "fp" then this
will return false instead.

> The result seems valid to me. At least, this is the best SLUB can do
> while avoiding the risk of infinite loop iteration.

Yeah! There were no infinite loop iterations in my tests inside
on_freelist(). There were in some cases in other functions, but not in
on_freelist().

Fortunately the While condition prevents any infinite loopings, even
without my patch.

> If you don't mind, could you please avoid bottom posting and
> reply with inline comments like how I reply to you?
> It makes it easier to follow the conversation.

Hopefully I did that correctly this time. Should I always include all
the previous messages in the reply chain? It was getting rather long and
I thought it would look messy.

> You can either send a new email or reply to this email with
> In-Reply-To header. And please cc SLAB ALLOCATOR folks in MAINTAINERS file
> including me—I recently changed my name and email (previously Hyeonggon Yoo).

Oh! You are one of the maintainers? That explains a lot, haha. I just
assumed you were someone from the mailing list who happened to be really
passionate about SLUB.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Harry Yoo]

On Thu, Feb 27, 2025 at 06:40:16PM +0200, Lilith Gkini wrote:
> Hey, Harry.
> 
> > Yes. but do we care about the return value of on_freelist()
> > when the freelist is corrupted? (we don't know if it was null-terminated
> > or not because it's corrupted.)
> 
> Oh! So we shouldn't care about the return value of on_freelist() if the
> freelist is corrupted? My thinking was that if the check_valid_pointer()
> detects a corrupted freelist and fixes it by setting the freepointer to
> NULL it fixes it, so we would care about the result. But maybe if the
> whole object_err() triggers, I think that causes an OOPs if I recall, we
> should consider this as corrupted and we shouldn't care about what it
> returns, cause something went terribly wrong?
> 
> I guess that sounds like a sound logic.
> 
> If that is how we should do this then yeah, my second suggested line is
> moot and in my later patch I shouldn't include it.

I think either way is fine, as both are not 100% accurate anyway if the
freelist is corrupted.
 
> > Two falses because when the freepointer of the tail object
> > is corrupted, the loop stops when nr equals slab->objects?
> 
> Yeah! Since the freelist pointer is corrupted and doesn't end in NULL
> on_freelist() won't find a NULL, and in the case of the tail having
> garbage that the check_valid_pointer() would normally catch, the code
> won't catch it, because it's at the tail which would exceed the
> slab->objects and the While loop will exit before that, since the
> freelist* (not slab, as you pointed out) is full.
> 
> > This is true because for partial slabs, the number of objects
> > plus 1 for the garbage, does not exceed slab->objects?
> 
> Yeah. That goes back to that second line I suggested in the previous
> email. If the number of objects in the freelist is less than the
> slab->objects and the corrupted freelist has some garbage address that
> the check_valid_pointer() will catch, it will set it to NULL instead, and
> as I said since the freelist now includes a NULL, my thinking was that
> on_freelist() should return true if we were searching for NULL.
> 
> But if thats not how on_freelist() should work in a case of a corrupted
> freelist and we don't add my second line that nulls the "fp" then this
> will return false instead.
> 
> > If you don't mind, could you please avoid bottom posting and
> > reply with inline comments like how I reply to you?
> > It makes it easier to follow the conversation.
> 
> Hopefully I did that correctly this time. Should I always include all
> the previous messages in the reply chain? It was getting rather long and
> I thought it would look messy.

You can omit some parts of the email if you're not replying to it.

Also, you don't have to copy and paste parts of the message when replying.
You can break the original message into into smaller sections and add
your comments in between—just like I do.

> > You can either send a new email or reply to this email with
> > In-Reply-To header. And please cc SLAB ALLOCATOR folks in MAINTAINERS file
> > including me—I recently changed my name and email (previously Hyeonggon Yoo).
> 
> Oh! You are one of the maintainers? That explains a lot, haha.

Not a maintainer (M:) but a reviewer (R:) :-)

> I just assumed you were someone from the mailing list who happened to be
> really passionate about SLUB.

Many people start by being curious and passionate about a specific
subsystem.

Anyway, as we discussed major concerns, (I think you can either add or not
add the second suggested line), could you please send a patch with a
nice commit message?

-- 
Cheers,
Harry

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Tue, Mar 04, 2025 at 03:25:26PM +0100, Vlastimil Babka wrote:
> On 3/4/25 13:18, Lilith Gkini wrote:
> > On Tue, Mar 04, 2025 at 12:20:03PM +0100, Vlastimil Babka wrote:
> > I was also thinking of fixing two lines to adhere to the "Breaking long
> > lines and strings" (2) from the coding-style.
> 
> Hm AFAIK checkpatch was adjusted to only warn at 100 lines. While the style
> document wasn't updated, we can leave such a small excess with no change.

Yeah, it didn't complain about it, I noticed it while having multiple
windows open with the diffs and all.

> > ---
> >  mm/slub.c | 24 +++++++++++++++++-------
> >  1 file changed, 17 insertions(+), 7 deletions(-)
> > 
> > diff --git a/mm/slub.c b/mm/slub.c
> > index 1f50129dcfb3..e06b88137705 100644
> > --- a/mm/slub.c
> > +++ b/mm/slub.c
> > @@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
> >   * Determine if a certain object in a slab is on the freelist. Must hold the
> >   * slab lock to guarantee that the chains are in a consistent state.
> >   */
> > -static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> > +static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> >  {
> >  	int nr = 0;
> >  	void *fp;
> > @@ -1437,38 +1437,48 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> >  	fp = slab->freelist;
> >  	while (fp && nr <= slab->objects) {
> >  		if (fp == search)
> > -			return 1;
> > +			return true;
> >  		if (!check_valid_pointer(s, slab, fp)) {
> >  			if (object) {
> >  				object_err(s, slab, object,
> >  					"Freechain corrupt");
> >  				set_freepointer(s, object, NULL);
> > +				break;
> >  			} else {
> >  				slab_err(s, slab, "Freepointer corrupt");
> >  				slab->freelist = NULL;
> >  				slab->inuse = slab->objects;
> >  				slab_fix(s, "Freelist cleared");
> > -				return 0;
> > +				return false;
> >  			}
> > -			break;
> >  		}
> >  		object = fp;
> >  		fp = get_freepointer(s, object);
> >  		nr++;
> >  	}
> >  
> > -	max_objects = order_objects(slab_order(slab), s->size);
> > +	if (fp != NULL && nr > slab->objects) {
> 
> In case nr > slab->objects we already know fp can't be NULL, no? So we don't
> have to test it?

...Yeah. All these different diffs got me confused. What a mess.

I just tested it in a debugger. That fp null check isn't necessary.

I'll send the full patch tomorrow or something, when I check it again
with a clear head. I dont want to do any mistakes in the actual patch.

> > I do have to note that the last slab_err is of length 81 with my change,
> > but it looks fine. If that one extra character is unacceptable let me
> > know so I can change it to something else.
> > Or if you think it's completely unnecessary I could leave it as it was
> > in the first place.
> 
> Yeah can leave it.
> 

Alright, I wont include the line breaks in the patch then! I'll leave it as it
was.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Vlastimil Babka]

On 3/4/25 13:18, Lilith Gkini wrote:
> On Tue, Mar 04, 2025 at 12:20:03PM +0100, Vlastimil Babka wrote:
> Thats true. I still had the return fp == search; in my mind, but with all

Ah, right.

> these changes we can just leave it as return search == NULL; as it was,
> because we are handing the edge cases.
> 
> By the time it reaches that return line it should be fine.

True.

> I was also thinking of fixing two lines to adhere to the "Breaking long
> lines and strings" (2) from the coding-style.

Hm AFAIK checkpatch was adjusted to only warn at 100 lines. While the style
document wasn't updated, we can leave such a small excess with no change.

> ---
>  mm/slub.c | 24 +++++++++++++++++-------
>  1 file changed, 17 insertions(+), 7 deletions(-)
> 
> diff --git a/mm/slub.c b/mm/slub.c
> index 1f50129dcfb3..e06b88137705 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
>   * Determine if a certain object in a slab is on the freelist. Must hold the
>   * slab lock to guarantee that the chains are in a consistent state.
>   */
> -static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> +static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
>  {
>  	int nr = 0;
>  	void *fp;
> @@ -1437,38 +1437,48 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
>  	fp = slab->freelist;
>  	while (fp && nr <= slab->objects) {
>  		if (fp == search)
> -			return 1;
> +			return true;
>  		if (!check_valid_pointer(s, slab, fp)) {
>  			if (object) {
>  				object_err(s, slab, object,
>  					"Freechain corrupt");
>  				set_freepointer(s, object, NULL);
> +				break;
>  			} else {
>  				slab_err(s, slab, "Freepointer corrupt");
>  				slab->freelist = NULL;
>  				slab->inuse = slab->objects;
>  				slab_fix(s, "Freelist cleared");
> -				return 0;
> +				return false;
>  			}
> -			break;
>  		}
>  		object = fp;
>  		fp = get_freepointer(s, object);
>  		nr++;
>  	}
>  
> -	max_objects = order_objects(slab_order(slab), s->size);
> +	if (fp != NULL && nr > slab->objects) {

In case nr > slab->objects we already know fp can't be NULL, no? So we don't
have to test it?

> +		slab_err(s, slab, "Freelist cycle detected");
> +		slab->freelist = NULL;
> +		slab->inuse = slab->objects;
> +		slab_fix(s, "Freelist cleared");
> +		return false;
> +	}
> +
> +	max_objects = order_objects(slab_or0der(slab), s->size);
>  	if (max_objects > MAX_OBJS_PER_PAGE)
>  		max_objects = MAX_OBJS_PER_PAGE;
>  
>  	if (slab->objects != max_objects) {
> -		slab_err(s, slab, "Wrong number of objects. Found %d but should be %d",
> +		slab_err(s, slab,
> +			 "Wrong number of objects. Found %d but should be %d",
>  			 slab->objects, max_objects);
>  		slab->objects = max_objects;
>  		slab_fix(s, "Number of objects adjusted");
>  	}
>  	if (slab->inuse != slab->objects - nr) {
> -		slab_err(s, slab, "Wrong object count. Counter is %d but counted were %d",
> +		slab_err(s, slab,
> +			 "Wrong object count. Counter is %d but counted were %d",
>  			 slab->inuse, slab->objects - nr);
>  		slab->inuse = slab->objects - nr;
>  		slab_fix(s, "Object count adjusted");
> 
> I do have to note that the last slab_err is of length 81 with my change,
> but it looks fine. If that one extra character is unacceptable let me
> know so I can change it to something else.
> Or if you think it's completely unnecessary I could leave it as it was
> in the first place.

Yeah can leave it.

> I just thought since we are trying to modernaze I should fix the length
> as well.
> 
> Also the CHECKPATCH is complaining about the `fp != NULL` that we can
> just check fp on it's own, which is technically true, but wouldn't make
> readability worse?
> I think its better as it's in my diff cause it's more obvious, but if
> you prefer the singular fp I can change it.

I think it's not necessary to test at all but in case I'm wrong, we can do
what checkpatch suggests to be consistent with the while() condition.

> If these changes are acceptable and we don't have anything further to
> change or add I can send it as a proper commit again, But I should
> probably break it into multiple patches.

It's fine as a single patch. Thanks!

> Maybe one patch for the lines and another for the rest? Or should I
> break the bool change in it's own patch?

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Tue, Mar 04, 2025 at 12:20:03PM +0100, Vlastimil Babka wrote:
> On 3/4/25 12:06, Lilith Gkini wrote:
> > On Tue, Mar 04, 2025 at 09:41:23AM +0100, Vlastimil Babka wrote:
> > -- 
> > 
> > and in the case where we want the code to not display "Freelist cycle
> > detected" we could do something like this:
> > 
> > ---
> >  mm/slub.c | 19 ++++++++++++++-----
> >  1 file changed, 14 insertions(+), 5 deletions(-)
> > 
> > diff --git a/mm/slub.c b/mm/slub.c
> > index 1f50129dcfb3..eef879d4feb1 100644
> > --- a/mm/slub.c
> > +++ b/mm/slub.c
> > @@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
> >   * Determine if a certain object in a slab is on the freelist. Must hold the
> >   * slab lock to guarantee that the chains are in a consistent state.
> >   */
> > -static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> > +static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> >  {
> >  	int nr = 0;
> >  	void *fp;
> > @@ -1437,27 +1437,36 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> >  	fp = slab->freelist;
> >  	while (fp && nr <= slab->objects) {
> >  		if (fp == search)
> > -			return 1;
> > +			return true;
> >  		if (!check_valid_pointer(s, slab, fp)) {
> >  			if (object) {
> >  				object_err(s, slab, object,
> >  					"Freechain corrupt");
> >  				set_freepointer(s, object, NULL);
> > +				fp = NULL;
> > +				break;
> 
> Since we break, nr is not incremented to slab->objects + 1.
> 
> >  			} else {
> >  				slab_err(s, slab, "Freepointer corrupt");
> >  				slab->freelist = NULL;
> >  				slab->inuse = slab->objects;
> >  				slab_fix(s, "Freelist cleared");
> > -				return 0;
> > +				return false;
> >  			}
> > -			break;
> >  		}
> >  		object = fp;
> >  		fp = get_freepointer(s, object);
> >  		nr++;
> >  	}
> >  
> > -	max_objects = order_objects(slab_order(slab), s->size);
> > +	if (fp != NULL && nr > slab->objects) {
> 
> And thus we should not need to set fp to NULL and test it here? Am I missing
> something?

Thats true. I still had the return fp == search; in my mind, but with all
these changes we can just leave it as return search == NULL; as it was,
because we are handing the edge cases.

By the time it reaches that return line it should be fine.

I was also thinking of fixing two lines to adhere to the "Breaking long
lines and strings" (2) from the coding-style.

---
 mm/slub.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 1f50129dcfb3..e06b88137705 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
  * Determine if a certain object in a slab is on the freelist. Must hold the
  * slab lock to guarantee that the chains are in a consistent state.
  */
-static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
+static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 {
 	int nr = 0;
 	void *fp;
@@ -1437,38 +1437,48 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 	fp = slab->freelist;
 	while (fp && nr <= slab->objects) {
 		if (fp == search)
-			return 1;
+			return true;
 		if (!check_valid_pointer(s, slab, fp)) {
 			if (object) {
 				object_err(s, slab, object,
 					"Freechain corrupt");
 				set_freepointer(s, object, NULL);
+				break;
 			} else {
 				slab_err(s, slab, "Freepointer corrupt");
 				slab->freelist = NULL;
 				slab->inuse = slab->objects;
 				slab_fix(s, "Freelist cleared");
-				return 0;
+				return false;
 			}
-			break;
 		}
 		object = fp;
 		fp = get_freepointer(s, object);
 		nr++;
 	}
 
-	max_objects = order_objects(slab_order(slab), s->size);
+	if (fp != NULL && nr > slab->objects) {
+		slab_err(s, slab, "Freelist cycle detected");
+		slab->freelist = NULL;
+		slab->inuse = slab->objects;
+		slab_fix(s, "Freelist cleared");
+		return false;
+	}
+
+	max_objects = order_objects(slab_or0der(slab), s->size);
 	if (max_objects > MAX_OBJS_PER_PAGE)
 		max_objects = MAX_OBJS_PER_PAGE;
 
 	if (slab->objects != max_objects) {
-		slab_err(s, slab, "Wrong number of objects. Found %d but should be %d",
+		slab_err(s, slab,
+			 "Wrong number of objects. Found %d but should be %d",
 			 slab->objects, max_objects);
 		slab->objects = max_objects;
 		slab_fix(s, "Number of objects adjusted");
 	}
 	if (slab->inuse != slab->objects - nr) {
-		slab_err(s, slab, "Wrong object count. Counter is %d but counted were %d",
+		slab_err(s, slab,
+			 "Wrong object count. Counter is %d but counted were %d",
 			 slab->inuse, slab->objects - nr);
 		slab->inuse = slab->objects - nr;
 		slab_fix(s, "Object count adjusted");
-- 

I do have to note that the last slab_err is of length 81 with my change,
but it looks fine. If that one extra character is unacceptable let me
know so I can change it to something else.

Or if you think it's completely unnecessary I could leave it as it was
in the first place.
I just thought since we are trying to modernaze I should fix the length
as well.

Also the CHECKPATCH is complaining about the `fp != NULL` that we can
just check fp on it's own, which is technically true, but wouldn't make
readability worse?
I think its better as it's in my diff cause it's more obvious, but if
you prefer the singular fp I can change it.

If these changes are acceptable and we don't have anything further to
change or add I can send it as a proper commit again, But I should
probably break it into multiple patches.

Maybe one patch for the lines and another for the rest? Or should I
break the bool change in it's own patch?

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Vlastimil Babka]

On 3/4/25 12:06, Lilith Gkini wrote:
> On Tue, Mar 04, 2025 at 09:41:23AM +0100, Vlastimil Babka wrote:
>> It sets the tail to NULL but then also breaks out of the loop (btw that
>> break; could be moved to the if (object) branch to make it more obvious) to
>> the code below, which should also set slab->inuse properly. So the result
>> should be consistent? In that case we're able to salvage at least the
>> uncorrupted part of the freelist. It's likely corrupted by a use-after-free
>> of a single object overwriting the freepointer.
> 
> Yes! You are right!
> 
> I also just tested this. The "Freelist cycle detected" will get
> triggered even if there is an invalid address at the tail in the case
> of a full freelist, which is a bit... inacurate, right? It's technically

Yes. But see my comments on the code below. I wonder why you got it triggered.

> not a cycle in that case since the freepointer is invalid and it doesn't
> point back to the slab.
> 
> - We could avoid this by nulling the fp in that case (as I suggested in v1
> in previous emails) inside the "Freechain corrupt" branch, but also
> reverting the while condition back to it's equal sign like it was and
> then changing the new if check to:
> 	if (fp != NULL && nr > slab->objects) {
> but it feels a bit messy.

I think it's not so bad.

> - Or we could just change the "Freelist cycle detected" message to
> something else.
> 
> - Or we could leave it as "Freelist cycle detected".

I'd prefer that.

> This is only a problem if the freelist is full and the tail is junk.

If the tail is junk it would be better to just fix it to NULL and not report
wrongly a cycle.

> If the freelist is not full the code will act as you suggested.
> 
> 
> If this is becoming too hard to follow I'll include the two diffs.
> 
> For the case were we are fine with the "Freelist cycle detected"
> message, even in the case of a junk tail:

<snip>

> 
> -- 
> 
> and in the case where we want the code to not display "Freelist cycle
> detected" we could do something like this:
> 
> ---
>  mm/slub.c | 19 ++++++++++++++-----
>  1 file changed, 14 insertions(+), 5 deletions(-)
> 
> diff --git a/mm/slub.c b/mm/slub.c
> index 1f50129dcfb3..eef879d4feb1 100644
> --- a/mm/slub.c
> +++ b/mm/slub.c
> @@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
>   * Determine if a certain object in a slab is on the freelist. Must hold the
>   * slab lock to guarantee that the chains are in a consistent state.
>   */
> -static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
> +static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
>  {
>  	int nr = 0;
>  	void *fp;
> @@ -1437,27 +1437,36 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
>  	fp = slab->freelist;
>  	while (fp && nr <= slab->objects) {
>  		if (fp == search)
> -			return 1;
> +			return true;
>  		if (!check_valid_pointer(s, slab, fp)) {
>  			if (object) {
>  				object_err(s, slab, object,
>  					"Freechain corrupt");
>  				set_freepointer(s, object, NULL);
> +				fp = NULL;
> +				break;

Since we break, nr is not incremented to slab->objects + 1.

>  			} else {
>  				slab_err(s, slab, "Freepointer corrupt");
>  				slab->freelist = NULL;
>  				slab->inuse = slab->objects;
>  				slab_fix(s, "Freelist cleared");
> -				return 0;
> +				return false;
>  			}
> -			break;
>  		}
>  		object = fp;
>  		fp = get_freepointer(s, object);
>  		nr++;
>  	}
>  
> -	max_objects = order_objects(slab_order(slab), s->size);
> +	if (fp != NULL && nr > slab->objects) {

And thus we should not need to set fp to NULL and test it here? Am I missing
something?

> +		slab_err(s, slab, "Freelist cycle detected");
> +		slab->freelist = NULL;
> +		slab->inuse = slab->objects;
> +		slab_fix(s, "Freelist cleared");
> +		return false;
> +	}
> +
> +	max_objects = order_objects(slab_or0der(slab), s->size);
>  	if (max_objects > MAX_OBJS_PER_PAGE)
>  		max_objects = MAX_OBJS_PER_PAGE;
>  
> -- 
> 
> Let me know what you think!

The latter would be better, thanks!

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Tue, Mar 04, 2025 at 09:41:23AM +0100, Vlastimil Babka wrote:
> On 3/4/25 09:24, Lilith Gkini wrote:
> > On Mon, Mar 03, 2025 at 08:06:32PM +0100, Vlastimil Babka wrote:
> >> Yeah, I think bools were not used initially int the kernel, but we're fine
> >> with them now and changing a function for other reasons is a good
> >> opportunity to modernize. There are some guidelines in
> >> Documentation/process/coding-style.rst about this (paragraphs 16 and 17).
> >> int is recommended if 0 means success and -EXXX for error, bool for simple
> >> true/false which is the case here.
> > 
> > Oh! because of the emote I thought you were being sarcastic that I didnt
> > report it properly.
> 
> Ah, sorry about that misunderstanding.
> 
> > Thank you for clarifying! That should be an easy fix!
> 
> Great!
> 
> >> > When it reaches nr == slab->objects and we are still in the while loop
> >> > it means that fp != NULL and therefore the freelist is corrupted (note
> >> > that nr starts from 0).
> >> > 
> >> > This would add fewer lines of code and there won't be any repeating
> >> > code.
> >> > It will enter in the "Freechain corrupt" branch and set the tail of 
> >> > the freelist to NULL, inform us of the error and it won't get a chance
> >> > to do the nr++ part, leaving nr == slab->objects in that particular 
> >> > case, because it breaks of the loop afterwards.
> >> > 
> >> > But it will not Null-out the freelist and set inuse to objects like you
> >> > suggested. If that is the desired behavior instead then we could do
> >> > something like you suggested.
> >> 
> >> We could change if (object) to if (object && nr != slab->objects) to force
> >> it into the "Freepointer corrupt" variant which is better. But then the
> > 
> > We could add a ternary operator in addition to you suggestion.
> > Changing this:
> > `slab_err(s, slab, "Freepointer corrupt");`
> > 
> > to this (needs adjusting for the proper formating ofc...):
> > `slab_err(s, slab, (nr == slab->objects) ? "Freelist cycle detected" : "Freepointer corrupt");`
> > 
> > But this might be too much voodoo...
> 
> Yeah it means 3 places where we check (nr == slab->objects) so it's not very
> readable.
> 
> >> message should be also adjusted depending on nr... it should really report
> > 
> > I m not sure what you have in mind about the adjusting the message on
> > nr. Do we really need to report the nr in the error? Do we need to
> > mention anything besides "Freelist cycle detected" like you mentioned?
> 
> I meant just the Freelist cycle detected" message. As "nr" equals
> slab->objects it's not so interesting.
> 
> >> "Freelist cycle detected", but that's adding too many conditions just to
> >> reuse the cleanup code so maybe it's more readable to check that outside of
> >> the while loop after all.
> > 
> > If the ternary operator is too unreadable we could do something like you
> > suggested
> > 
> > ```
> > if (fp != NULL && nr == slab->objects) {
> > 	slab_err(s, slab, "Freelist cycle detected");
> > 	slab->freelist = NULL;
> > 	slab->inuse = slab->objects;
> > 	slab_fix(s, "Freelist cleared");
> > 	return false;
> > }
> > ```
> 
> Yeah looks good.
> > 
> > What more would you like to add in the error message?
> > 
> > In a previous email you mentioned this
> > 
> >> >> I think there's a problem that none of this will fix or even report the
> >> >> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
> >> >> all objects are free. This goes contrary to the other places that respond to
> >> >> slab corruption by setting all objects to used and trying not to touch the
> >> >> slab again at all.
> > 
> > If nuking it is how we should hangle corrupted freelists shouldn't we
> > also do the same in the "Freechain corrupt" branch? Otherwise it
> > wouldn't be consistent. Instead the code now just sets the tail to NULL.
> 
> It sets the tail to NULL but then also breaks out of the loop (btw that
> break; could be moved to the if (object) branch to make it more obvious) to
> the code below, which should also set slab->inuse properly. So the result
> should be consistent? In that case we're able to salvage at least the
> uncorrupted part of the freelist. It's likely corrupted by a use-after-free
> of a single object overwriting the freepointer.

Yes! You are right!

I also just tested this. The "Freelist cycle detected" will get
triggered even if there is an invalid address at the tail in the case
of a full freelist, which is a bit... inacurate, right? It's technically
not a cycle in that case since the freepointer is invalid and it doesn't
point back to the slab.

- We could avoid this by nulling the fp in that case (as I suggested in v1
in previous emails) inside the "Freechain corrupt" branch, but also
reverting the while condition back to it's equal sign like it was and
then changing the new if check to:
	if (fp != NULL && nr > slab->objects) {
but it feels a bit messy.

- Or we could just change the "Freelist cycle detected" message to
something else.

- Or we could leave it as "Freelist cycle detected".

This is only a problem if the freelist is full and the tail is junk.

If the freelist is not full the code will act as you suggested.


If this is becoming too hard to follow I'll include the two diffs.

For the case were we are fine with the "Freelist cycle detected"
message, even in the case of a junk tail:

---
 mm/slub.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 1f50129dcfb3..25e972a3b914 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
  * Determine if a certain object in a slab is on the freelist. Must hold the
  * slab lock to guarantee that the chains are in a consistent state.
  */
-static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
+static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 {
 	int nr = 0;
 	void *fp;
@@ -1435,29 +1435,37 @@ 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) {
 		if (fp == search)
-			return 1;
+			return true;
 		if (!check_valid_pointer(s, slab, fp)) {
 			if (object) {
 				object_err(s, slab, object,
 					"Freechain corrupt");
 				set_freepointer(s, object, NULL);
+				break;
 			} else {
 				slab_err(s, slab, "Freepointer corrupt");
 				slab->freelist = NULL;
 				slab->inuse = slab->objects;
 				slab_fix(s, "Freelist cleared");
-				return 0;
+				return false;
 			}
-			break;
 		}
 		object = fp;
 		fp = get_freepointer(s, object);
 		nr++;
 	}
 
-	max_objects = order_objects(slab_order(slab), s->size);
+	if (fp != NULL && nr == slab->objects) {
+		slab_err(s, slab, "Freelist cycle detected");
+		slab->freelist = NULL;
+		slab->inuse = slab->objects;
+		slab_fix(s, "Freelist cleared");
+		return false;
+	}
+
+	max_objects = order_objects(slab_or0der(slab), s->size);
 	if (max_objects > MAX_OBJS_PER_PAGE)
 		max_objects = MAX_OBJS_PER_PAGE;
 
-- 

and in the case where we want the code to not display "Freelist cycle
detected" we could do something like this:

---
 mm/slub.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 1f50129dcfb3..eef879d4feb1 100644
--- a/mm/slub.c
+++ b/mm/slub.c
@@ -1427,7 +1427,7 @@ static int check_slab(struct kmem_cache *s, struct slab *slab)
  * Determine if a certain object in a slab is on the freelist. Must hold the
  * slab lock to guarantee that the chains are in a consistent state.
  */
-static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
+static bool on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 {
 	int nr = 0;
 	void *fp;
@@ -1437,27 +1437,36 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 	fp = slab->freelist;
 	while (fp && nr <= slab->objects) {
 		if (fp == search)
-			return 1;
+			return true;
 		if (!check_valid_pointer(s, slab, fp)) {
 			if (object) {
 				object_err(s, slab, object,
 					"Freechain corrupt");
 				set_freepointer(s, object, NULL);
+				fp = NULL;
+				break;
 			} else {
 				slab_err(s, slab, "Freepointer corrupt");
 				slab->freelist = NULL;
 				slab->inuse = slab->objects;
 				slab_fix(s, "Freelist cleared");
-				return 0;
+				return false;
 			}
-			break;
 		}
 		object = fp;
 		fp = get_freepointer(s, object);
 		nr++;
 	}
 
-	max_objects = order_objects(slab_order(slab), s->size);
+	if (fp != NULL && nr > slab->objects) {
+		slab_err(s, slab, "Freelist cycle detected");
+		slab->freelist = NULL;
+		slab->inuse = slab->objects;
+		slab_fix(s, "Freelist cleared");
+		return false;
+	}
+
+	max_objects = order_objects(slab_or0der(slab), s->size);
 	if (max_objects > MAX_OBJS_PER_PAGE)
 		max_objects = MAX_OBJS_PER_PAGE;
 
-- 

Let me know what you think!

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Vlastimil Babka]

On 3/4/25 09:24, Lilith Gkini wrote:
> On Mon, Mar 03, 2025 at 08:06:32PM +0100, Vlastimil Babka wrote:
>> Yeah, I think bools were not used initially int the kernel, but we're fine
>> with them now and changing a function for other reasons is a good
>> opportunity to modernize. There are some guidelines in
>> Documentation/process/coding-style.rst about this (paragraphs 16 and 17).
>> int is recommended if 0 means success and -EXXX for error, bool for simple
>> true/false which is the case here.
> 
> Oh! because of the emote I thought you were being sarcastic that I didnt
> report it properly.

Ah, sorry about that misunderstanding.

> Thank you for clarifying! That should be an easy fix!

Great!

>> > When it reaches nr == slab->objects and we are still in the while loop
>> > it means that fp != NULL and therefore the freelist is corrupted (note
>> > that nr starts from 0).
>> > 
>> > This would add fewer lines of code and there won't be any repeating
>> > code.
>> > It will enter in the "Freechain corrupt" branch and set the tail of 
>> > the freelist to NULL, inform us of the error and it won't get a chance
>> > to do the nr++ part, leaving nr == slab->objects in that particular 
>> > case, because it breaks of the loop afterwards.
>> > 
>> > But it will not Null-out the freelist and set inuse to objects like you
>> > suggested. If that is the desired behavior instead then we could do
>> > something like you suggested.
>> 
>> We could change if (object) to if (object && nr != slab->objects) to force
>> it into the "Freepointer corrupt" variant which is better. But then the
> 
> We could add a ternary operator in addition to you suggestion.
> Changing this:
> `slab_err(s, slab, "Freepointer corrupt");`
> 
> to this (needs adjusting for the proper formating ofc...):
> `slab_err(s, slab, (nr == slab->objects) ? "Freelist cycle detected" : "Freepointer corrupt");`
> 
> But this might be too much voodoo...

Yeah it means 3 places where we check (nr == slab->objects) so it's not very
readable.

>> message should be also adjusted depending on nr... it should really report
> 
> I m not sure what you have in mind about the adjusting the message on
> nr. Do we really need to report the nr in the error? Do we need to
> mention anything besides "Freelist cycle detected" like you mentioned?

I meant just the Freelist cycle detected" message. As "nr" equals
slab->objects it's not so interesting.

>> "Freelist cycle detected", but that's adding too many conditions just to
>> reuse the cleanup code so maybe it's more readable to check that outside of
>> the while loop after all.
> 
> If the ternary operator is too unreadable we could do something like you
> suggested
> 
> ```
> if (fp != NULL && nr == slab->objects) {
> 	slab_err(s, slab, "Freelist cycle detected");
> 	slab->freelist = NULL;
> 	slab->inuse = slab->objects;
> 	slab_fix(s, "Freelist cleared");
> 	return false;
> }
> ```

Yeah looks good.
> 
> What more would you like to add in the error message?
> 
> In a previous email you mentioned this
> 
>> >> I think there's a problem that none of this will fix or even report the
>> >> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
>> >> all objects are free. This goes contrary to the other places that respond to
>> >> slab corruption by setting all objects to used and trying not to touch the
>> >> slab again at all.
> 
> If nuking it is how we should hangle corrupted freelists shouldn't we
> also do the same in the "Freechain corrupt" branch? Otherwise it
> wouldn't be consistent. Instead the code now just sets the tail to NULL.

It sets the tail to NULL but then also breaks out of the loop (btw that
break; could be moved to the if (object) branch to make it more obvious) to
the code below, which should also set slab->inuse properly. So the result
should be consistent? In that case we're able to salvage at least the
uncorrupted part of the freelist. It's likely corrupted by a use-after-free
of a single object overwriting the freepointer.

In case of the cycle we could also in theory replace the freepointer causing
the cycle to NULL. But we'd have to spend more effort to determine which it
was. Cycle is also probably due to a more serious issue than single object
overwrite - it's unlikely a random overwrite would corrupt a freepointer in
a way that it's valid but causing a cycle. So throwing out everything seems
the easiest.

> In that case we'll need to do a lot more rewriting, but it might help
> out with avoiding the reuse of cleanup code.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Mon, Mar 03, 2025 at 08:06:32PM +0100, Vlastimil Babka wrote:
> On 3/3/25 17:41, Lilith Gkini wrote:
> > On Mon, Mar 03, 2025 at 12:06:58PM +0100, Vlastimil Babka wrote:
> >> On 3/2/25 19:01, Lilith Persefoni Gkini wrote:
> >> > If the `search` pattern is not found in the freelist then the function
> >> > should return `fp == search` where fp is the last freepointer from the
> >> > while loop.
> >> > 
> >> > If the caller of the function was searching for NULL and the freelist is
> >> > valid it should return True (1), otherwise False (0).
> >> 
> >> This suggests we should change the function return value to bool :)
> >> 
> > 
> > Alright, If you want to be more technical it's
> > `1 (true), otherwise 0 (false).`
> > Its just easier to communicate with the true or false concepts, but in C
> > we usually don't use bools cause its just 1s or 0s.
> 
> Yeah, I think bools were not used initially int the kernel, but we're fine
> with them now and changing a function for other reasons is a good
> opportunity to modernize. There are some guidelines in
> Documentation/process/coding-style.rst about this (paragraphs 16 and 17).
> int is recommended if 0 means success and -EXXX for error, bool for simple
> true/false which is the case here.

Oh! because of the emote I thought you were being sarcastic that I didnt
report it properly.
Thank you for clarifying! That should be an easy fix!

> >> I think there's a problem that none of this will fix or even report the
> >> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
> >> all objects are free. This goes contrary to the other places that respond to
> >> slab corruption by setting all objects to used and trying not to touch the
> >> slab again at all.
> >> 
> >> So I think after the while loop we could determine there was a cycle if (nr
> >> == slab->objects && fp != NULL), right? In that case we could perform the
> >> same report and fix as in the "Freepointer corrupt" case?
> > 
> > True! We could either add an if check after the while as you said to
> > replicate the "Freepointer corrupt" behavior...
> > Or...
> > 
> > I hate to say it, or we could leave the while condition with the equal
> > sign intact, as it was, and change that `if` check from
> > `if (!check_valid_pointer(s, slab, fp)) {`
> > to
> > `if (!check_valid_pointer(s, slab, fp) || nr == slab->objects) {`
> 
> You're right!
> 
> > When it reaches nr == slab->objects and we are still in the while loop
> > it means that fp != NULL and therefore the freelist is corrupted (note
> > that nr starts from 0).
> > 
> > This would add fewer lines of code and there won't be any repeating
> > code.
> > It will enter in the "Freechain corrupt" branch and set the tail of 
> > the freelist to NULL, inform us of the error and it won't get a chance
> > to do the nr++ part, leaving nr == slab->objects in that particular 
> > case, because it breaks of the loop afterwards.
> > 
> > But it will not Null-out the freelist and set inuse to objects like you
> > suggested. If that is the desired behavior instead then we could do
> > something like you suggested.
> 
> We could change if (object) to if (object && nr != slab->objects) to force
> it into the "Freepointer corrupt" variant which is better. But then the

We could add a ternary operator in addition to you suggestion.
Changing this:
`slab_err(s, slab, "Freepointer corrupt");`

to this (needs adjusting for the proper formating ofc...):
`slab_err(s, slab, (nr == slab->objects) ? "Freelist cycle detected" : "Freepointer corrupt");`

But this might be too much voodoo...

> message should be also adjusted depending on nr... it should really report

I m not sure what you have in mind about the adjusting the message on
nr. Do we really need to report the nr in the error? Do we need to
mention anything besides "Freelist cycle detected" like you mentioned?

> "Freelist cycle detected", but that's adding too many conditions just to
> reuse the cleanup code so maybe it's more readable to check that outside of
> the while loop after all.

If the ternary operator is too unreadable we could do something like you
suggested

```
if (fp != NULL && nr == slab->objects) {
	slab_err(s, slab, "Freelist cycle detected");
	slab->freelist = NULL;
	slab->inuse = slab->objects;
	slab_fix(s, "Freelist cleared");
	return false;
}
```

What more would you like to add in the error message?

In a previous email you mentioned this

> >> I think there's a problem that none of this will fix or even report the
> >> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
> >> all objects are free. This goes contrary to the other places that respond to
> >> slab corruption by setting all objects to used and trying not to touch the
> >> slab again at all.

If nuking it is how we should hangle corrupted freelists shouldn't we
also do the same in the "Freechain corrupt" branch? Otherwise it
wouldn't be consistent. Instead the code now just sets the tail to NULL.

In that case we'll need to do a lot more rewriting, but it might help
out with avoiding the reuse of cleanup code.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Vlastimil Babka]

On 3/3/25 17:41, Lilith Gkini wrote:
> On Mon, Mar 03, 2025 at 12:06:58PM +0100, Vlastimil Babka wrote:
>> On 3/2/25 19:01, Lilith Persefoni Gkini wrote:
>> > If the `search` pattern is not found in the freelist then the function
>> > should return `fp == search` where fp is the last freepointer from the
>> > while loop.
>> > 
>> > If the caller of the function was searching for NULL and the freelist is
>> > valid it should return True (1), otherwise False (0).
>> 
>> This suggests we should change the function return value to bool :)
>> 
> 
> Alright, If you want to be more technical it's
> `1 (true), otherwise 0 (false).`
> Its just easier to communicate with the true or false concepts, but in C
> we usually don't use bools cause its just 1s or 0s.

Yeah, I think bools were not used initially int the kernel, but we're fine
with them now and changing a function for other reasons is a good
opportunity to modernize. There are some guidelines in
Documentation/process/coding-style.rst about this (paragraphs 16 and 17).
int is recommended if 0 means success and -EXXX for error, bool for simple
true/false which is the case here.

>> I think there's a problem that none of this will fix or even report the
>> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
>> all objects are free. This goes contrary to the other places that respond to
>> slab corruption by setting all objects to used and trying not to touch the
>> slab again at all.
>> 
>> So I think after the while loop we could determine there was a cycle if (nr
>> == slab->objects && fp != NULL), right? In that case we could perform the
>> same report and fix as in the "Freepointer corrupt" case?
> 
> True! We could either add an if check after the while as you said to
> replicate the "Freepointer corrupt" behavior...
> Or...
> 
> I hate to say it, or we could leave the while condition with the equal
> sign intact, as it was, and change that `if` check from
> `if (!check_valid_pointer(s, slab, fp)) {`
> to
> `if (!check_valid_pointer(s, slab, fp) || nr == slab->objects) {`

You're right!

> When it reaches nr == slab->objects and we are still in the while loop
> it means that fp != NULL and therefore the freelist is corrupted (note
> that nr starts from 0).
> 
> This would add fewer lines of code and there won't be any repeating
> code.
> It will enter in the "Freechain corrupt" branch and set the tail of 
> the freelist to NULL, inform us of the error and it won't get a chance
> to do the nr++ part, leaving nr == slab->objects in that particular 
> case, because it breaks of the loop afterwards.
> 
> But it will not Null-out the freelist and set inuse to objects like you
> suggested. If that is the desired behavior instead then we could do
> something like you suggested.

We could change if (object) to if (object && nr != slab->objects) to force
it into the "Freepointer corrupt" variant which is better. But then the
message should be also adjusted depending on nr... it should really report
"Freelist cycle detected", but that's adding too many conditions just to
reuse the cleanup code so maybe it's more readable to check that outside of
the while loop after all.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Christoph Lameter (Ampere)]

In Mon, 3 Mar 2025, Lilith Gkini wrote:

> Alright, If you want to be more technical it's
> `1 (true), otherwise 0 (false).`
> Its just easier to communicate with the true or false concepts, but in C
> we usually don't use bools cause its just 1s or 0s.

Its not about "technicalities". Please use the bool return type as
provided for kernel code.

Compare f.e.


static inline bool kmem_cache_has_cpu_partial(struct kmem_cache *s)
{
#ifdef CONFIG_SLUB_CPU_PARTIAL
        return !kmem_cache_debug(s);
#else
        return false;
#endif
}

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Gkini]

On Mon, Mar 03, 2025 at 12:06:58PM +0100, Vlastimil Babka wrote:
> On 3/2/25 19:01, Lilith Persefoni Gkini wrote:
> > If the `search` pattern is not found in the freelist then the function
> > should return `fp == search` where fp is the last freepointer from the
> > while loop.
> > 
> > If the caller of the function was searching for NULL and the freelist is
> > valid it should return True (1), otherwise False (0).
> 
> This suggests we should change the function return value to bool :)
> 

Alright, If you want to be more technical it's
`1 (true), otherwise 0 (false).`
Its just easier to communicate with the true or false concepts, but in C
we usually don't use bools cause its just 1s or 0s.

> I think there's a problem that none of this will fix or even report the
> situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
> all objects are free. This goes contrary to the other places that respond to
> slab corruption by setting all objects to used and trying not to touch the
> slab again at all.
> 
> So I think after the while loop we could determine there was a cycle if (nr
> == slab->objects && fp != NULL), right? In that case we could perform the
> same report and fix as in the "Freepointer corrupt" case?

True! We could either add an if check after the while as you said to
replicate the "Freepointer corrupt" behavior...
Or...

I hate to say it, or we could leave the while condition with the equal
sign intact, as it was, and change that `if` check from
`if (!check_valid_pointer(s, slab, fp)) {`
to
`if (!check_valid_pointer(s, slab, fp) || nr == slab->objects) {`

When it reaches nr == slab->objects and we are still in the while loop
it means that fp != NULL and therefore the freelist is corrupted (note
that nr starts from 0).

This would add fewer lines of code and there won't be any repeating
code.
It will enter in the "Freechain corrupt" branch and set the tail of 
the freelist to NULL, inform us of the error and it won't get a chance
to do the nr++ part, leaving nr == slab->objects in that particular 
case, because it breaks of the loop afterwards.

But it will not Null-out the freelist and set inuse to objects like you
suggested. If that is the desired behavior instead then we could do
something like you suggested.

Re: [PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Vlastimil Babka]

On 3/2/25 19:01, Lilith Persefoni Gkini wrote:
> The on_freelist() uses a while loop to walk through the linked list
> freelist of a particular slab until it finds the `search` pattern and
> breaks if there is a freepointer in the list that is NULL, or invalid
> (fails the check_valid_pointer() check), or the number of objects (nr)
> in the freelist is more than `slab->objects + 1`
> 
> No valid freelist should have more than slab->objects non NULL pointers,
> therefore the while conditional should check until slab->objects amount
> of times, not more.

In v1 discussion you explained how this can later lead to setting
slab->inuse to -1. I think it's useful to say it here in the changelog
because it's fixing a more serious problem than just doing an unnecessary
loop iteration.

> If the `search` pattern is not found in the freelist then the function
> should return `fp == search` where fp is the last freepointer from the
> while loop.
> 
> If the caller of the function was searching for NULL and the freelist is
> valid it should return True (1), otherwise False (0).

This suggests we should change the function return value to bool :)

> Signed-off-by: Lilith Persefoni Gkini <lilithgkini@proton.me>
> ---
>  mm/slub.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/mm/slub.c b/mm/slub.c
> index 1f50129dcfb3..0d3dd429b095 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) {
>  		if (fp == search)
>  			return 1;
>  		if (!check_valid_pointer(s, slab, fp)) {
> @@ -1473,7 +1473,7 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
>  		slab->inuse = slab->objects - nr;
>  		slab_fix(s, "Object count adjusted");
>  	}
> -	return search == NULL;
> +	return fp == search;
>  }

This seems ok and fixes the issue with setting inuse to -1, while
on_freelist(..., NULL) keeps working, AFAICS.

But I'm wondering if we still have some gap in case there's a cycle in the
freelist as such that we finish the loop with nr == slab->objects and fp is
not NULL. check_valid_pointer() will not catch it as every pointer seems
valid on its own.

This will happen either
- from free_consistency_checks() when searching for an object that's not on
the freelist. Notet his check should avoid the freelist cycle happening in
the first place, by preventing a double free. But it could also happen due
to some other (deliberate?) corruption.
- the call validate_slab() searching for NULL will be returning false

I think there's a problem that none of this will fix or even report the
situation properly. Even worse we'll set slab->inuse to 0 and thus pretend
all objects are free. This goes contrary to the other places that respond to
slab corruption by setting all objects to used and trying not to touch the
slab again at all.

So I think after the while loop we could determine there was a cycle if (nr
== slab->objects && fp != NULL), right? In that case we could perform the
same report and fix as in the "Freepointer corrupt" case?

[PATCH] slub: Fix Off-By-One in the While condition in on_freelist()

[Lilith Persefoni Gkini]

The on_freelist() uses a while loop to walk through the linked list
freelist of a particular slab until it finds the `search` pattern and
breaks if there is a freepointer in the list that is NULL, or invalid
(fails the check_valid_pointer() check), or the number of objects (nr)
in the freelist is more than `slab->objects + 1`

No valid freelist should have more than slab->objects non NULL pointers,
therefore the while conditional should check until slab->objects amount
of times, not more.

If the `search` pattern is not found in the freelist then the function
should return `fp == search` where fp is the last freepointer from the
while loop.

If the caller of the function was searching for NULL and the freelist is
valid it should return True (1), otherwise False (0).

Signed-off-by: Lilith Persefoni Gkini <lilithgkini@proton.me>
---
 mm/slub.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/mm/slub.c b/mm/slub.c
index 1f50129dcfb3..0d3dd429b095 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) {
 		if (fp == search)
 			return 1;
 		if (!check_valid_pointer(s, slab, fp)) {
@@ -1473,7 +1473,7 @@ static int on_freelist(struct kmem_cache *s, struct slab *slab, void *search)
 		slab->inuse = slab->objects - nr;
 		slab_fix(s, "Object count adjusted");
 	}
-	return search == NULL;
+	return fp == search;
 }
 
 static void trace(struct kmem_cache *s, struct slab *slab, void *object,
-- 
2.48.1