[GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

Linus,

Add check of order < 0 before calling free_pages()

The function addresses that are traced by ftrace are stored in pages,
and the size is held in a variable. If there's some error in creating
them, the allocate ones will be freed. In this case, it is possible that
the order of pages to be freed may end up being negative due to a size of
zero passed to get_count_order(), and then that negative number will cause
free_pages() to free a very large section. Make sure that does not happen.


Please pull the latest trace-v5.12-rc5 tree, which can be found at:


  git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git
trace-v5.12-rc5

Tag SHA1: 30ee29d701d2b6848cfa1c7a163745fb68aabd36
Head SHA1: 59300b36f85f254260c81d9dd09195fa49eb0f98


Steven Rostedt (VMware) (1):
      ftrace: Check if pages were allocated before calling free_pages()

----
 kernel/trace/ftrace.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
---------------------------
commit 59300b36f85f254260c81d9dd09195fa49eb0f98
Author: Steven Rostedt (VMware) <rostedt@goodmis.org>
Date:   Tue Mar 30 09:58:38 2021 -0400

    ftrace: Check if pages were allocated before calling free_pages()
    
    It is possible that on error pg->size can be zero when getting its order,
    which would return a -1 value. It is dangerous to pass in an order of -1
    to free_pages(). Check if order is greater than or equal to zero before
    calling free_pages().
    
    Link: https://lore.kernel.org/lkml/20210330093916.432697c7@gandalf.local.home/
    
    Reported-by: Abaci Robot <abaci@linux.alibaba.com>
    Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 4d8e35575549..12223132eff4 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -3231,7 +3231,8 @@ ftrace_allocate_pages(unsigned long num_to_init)
 	pg = start_pg;
 	while (pg) {
 		order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-		free_pages((unsigned long)pg->records, order);
+		if (order >= 0)
+			free_pages((unsigned long)pg->records, order);
 		start_pg = pg->next;
 		kfree(pg);
 		pg = start_pg;
@@ -6418,7 +6419,8 @@ void ftrace_release_mod(struct module *mod)
 		clear_mod_from_hashes(pg);
 
 		order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-		free_pages((unsigned long)pg->records, order);
+		if (order >= 0)
+			free_pages((unsigned long)pg->records, order);
 		tmp_page = pg->next;
 		kfree(pg);
 		ftrace_number_of_pages -= 1 << order;
@@ -6778,7 +6780,8 @@ void ftrace_free_mem(struct module *mod, void *start_ptr, void *end_ptr)
 		if (!pg->index) {
 			*last_pg = pg->next;
 			order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-			free_pages((unsigned long)pg->records, order);
+			if (order >= 0)
+				free_pages((unsigned long)pg->records, order);
 			ftrace_number_of_pages -= 1 << order;
 			ftrace_number_of_groups--;
 			kfree(pg);

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Linus Torvalds]

On Wed, Mar 31, 2021 at 6:27 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
>                 order = get_count_order(pg->size / ENTRIES_PER_PAGE);
> -               free_pages((unsigned long)pg->records, order);
> +               if (order >= 0)
> +                       free_pages((unsigned long)pg->records, order);

Honestly, looking at that code, every single use of
"get_count_order()" seems really really confusing.

And really confused.

The comments are garbage, the code is odd, it's just all very very strange.

See here in ftrace_allocate_records():

        pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
        order = get_count_order(pages);

        /*
         * We want to fill as much as possible. No more than a page
         * may be empty.
         */
        if (!is_power_of_2(pages))
                order--;

can you actually explain what the logic is here?

The 'get_count_order()' function will return the smallest order that
the value fits in. But then if the value wasn't a power of two, you
subtract 1. If I understand the code correctly, that's just the same
as "what is the highest bit set", isn't it?

So afaik, what you *actually* want is just

        pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
        order = fls(pages)-1;

isn't it?

Did I misunderstand what the code wants to do? The "No more than a
page may be empty" seems wrong - you really mean "no empty pages".

I dunno. Maybe I'm wrong, but that code is really confusing (which is
why I may be wrong). It doesn't seem to make any sense at all to use
"get_count_order()" and then modify the end result.

             Linus

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 2278 bytes --]

On Wed, Mar 31, 2021 at 10:45 AM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> Honestly, looking at that code, every single use of
> "get_count_order()" seems really really confusing.

Side note: I've pulled your fix, but I really think that the bug is
almost entirely due to the code being so opaque and crazy hard to
read. I think the real fix would be to make the code a lot clearer.

I found another bug in there, for example:

                ftrace_number_of_pages -= 1 << order;

is also wrong if order is negative.

So I think the fix is something like the attached (TOTALLY UNTESTED!!)
that does two things:

 - make the "has it been allocated" test be about "pg->records" being
non-NULL, which honestly seems to be a hell of a lot more logical.

 - get rid of the crazy "size" field that then has to be converted
into a "page order", and just keep it being the page order

 - that makes all the calculations much simpler: the size of an
allocation is (trivially) just

        PAGE_SIZE << pg->order

   and the test whether the allocation has filled up is to just see
how much space we need:

        end_offset = (pg->index+1) * sizeof(pg->records[0]);

   and then you can compare that against that trivial allocation size.

Doesn't this make the code now make SENSE? Instead of that
incomprehensible mess it was before?

I dunno. Maybe it's just my "pee in the snow" thing, but honestly, the
fact that I seem to have found another bug wrt the whole
'ftrace_number_of_pages' handling really says that the code was
garbage.

And maybe it's just me who doesn't understand the subtle perfection of
the old code, and I'm being stupid. Feel free to educate me about it.

Final note: note the "TOTALLY UNTESTED" part of the patch. The patch
CompilesForMe(tm), but please consider it a "how about something like
this" rather than anything finished.

Also note that I did *not* change the initial "order" calculation
itself in ftrace_allocate_records() in this patch. I left that
particular oddity alone. Again, I *think* the math just ends up being

        pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
        order = fls(pages)-1;

but the attached patch is not about that, it's about the crazy "pg->size" games.

            Linus

PS. TOTALLY UNTESTED!!

[-- Attachment #2: patch --]
[-- Type: application/octet-stream, Size: 3588 bytes --]

 kernel/trace/ftrace.c | 35 +++++++++++++++++------------------
 1 file changed, 17 insertions(+), 18 deletions(-)

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 3ba52d4e1314..9c76db1f7060 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -1090,7 +1090,7 @@ struct ftrace_page {
 	struct ftrace_page	*next;
 	struct dyn_ftrace	*records;
 	int			index;
-	int			size;
+	int			order;
 };
 
 #define ENTRY_SIZE sizeof(struct dyn_ftrace)
@@ -3181,7 +3181,7 @@ static int ftrace_allocate_records(struct ftrace_page *pg, int count)
 	ftrace_number_of_groups++;
 
 	cnt = (PAGE_SIZE << order) / ENTRY_SIZE;
-	pg->size = cnt;
+	pg->order = order;
 
 	if (cnt > count)
 		cnt = count;
@@ -3194,7 +3194,6 @@ ftrace_allocate_pages(unsigned long num_to_init)
 {
 	struct ftrace_page *start_pg;
 	struct ftrace_page *pg;
-	int order;
 	int cnt;
 
 	if (!num_to_init)
@@ -3230,13 +3229,13 @@ ftrace_allocate_pages(unsigned long num_to_init)
  free_pages:
 	pg = start_pg;
 	while (pg) {
-		order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-		if (order >= 0)
-			free_pages((unsigned long)pg->records, order);
+		if (pg->records) {
+			free_pages((unsigned long)pg->records, pg->order);
+			ftrace_number_of_pages -= 1 << pg->order;
+		}
 		start_pg = pg->next;
 		kfree(pg);
 		pg = start_pg;
-		ftrace_number_of_pages -= 1 << order;
 		ftrace_number_of_groups--;
 	}
 	pr_info("ftrace: FAILED to allocate memory for functions\n");
@@ -6221,6 +6220,7 @@ static int ftrace_process_locs(struct module *mod,
 	p = start;
 	pg = start_pg;
 	while (p < end) {
+		unsigned long end_offset;
 		addr = ftrace_call_adjust(*p++);
 		/*
 		 * Some architecture linkers will pad between
@@ -6231,7 +6231,8 @@ static int ftrace_process_locs(struct module *mod,
 		if (!addr)
 			continue;
 
-		if (pg->index == pg->size) {
+		end_offset = (pg->index+1) * sizeof(pg->records[0]);
+		if (end_offset < PAGE_SIZE << pg->order) {
 			/* We should have allocated enough */
 			if (WARN_ON(!pg->next))
 				break;
@@ -6400,7 +6401,6 @@ void ftrace_release_mod(struct module *mod)
 	struct ftrace_page **last_pg;
 	struct ftrace_page *tmp_page = NULL;
 	struct ftrace_page *pg;
-	int order;
 
 	mutex_lock(&ftrace_lock);
 
@@ -6451,12 +6451,12 @@ void ftrace_release_mod(struct module *mod)
 		/* Needs to be called outside of ftrace_lock */
 		clear_mod_from_hashes(pg);
 
-		order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-		if (order >= 0)
-			free_pages((unsigned long)pg->records, order);
+		if (pg->records) {
+			free_pages((unsigned long)pg->records, pg->order);
+			ftrace_number_of_pages -= 1 << pg->order;
+		}
 		tmp_page = pg->next;
 		kfree(pg);
-		ftrace_number_of_pages -= 1 << order;
 		ftrace_number_of_groups--;
 	}
 }
@@ -6774,7 +6774,6 @@ void ftrace_free_mem(struct module *mod, void *start_ptr, void *end_ptr)
 	struct ftrace_mod_map *mod_map = NULL;
 	struct ftrace_init_func *func, *func_next;
 	struct list_head clear_hash;
-	int order;
 
 	INIT_LIST_HEAD(&clear_hash);
 
@@ -6812,10 +6811,10 @@ void ftrace_free_mem(struct module *mod, void *start_ptr, void *end_ptr)
 		ftrace_update_tot_cnt--;
 		if (!pg->index) {
 			*last_pg = pg->next;
-			order = get_count_order(pg->size / ENTRIES_PER_PAGE);
-			if (order >= 0)
-				free_pages((unsigned long)pg->records, order);
-			ftrace_number_of_pages -= 1 << order;
+			if (pg->records) {
+				free_pages((unsigned long)pg->records, pg->order);
+				ftrace_number_of_pages -= 1 << pg->order;
+			}
 			ftrace_number_of_groups--;
 			kfree(pg);
 			pg = container_of(last_pg, struct ftrace_page, next);

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

On Wed, 31 Mar 2021 11:03:21 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> I found another bug in there, for example:
> 
>                 ftrace_number_of_pages -= 1 << order;
> 
> is also wrong if order is negative.

True, but ftrace_number_of_pages is only used for accounting (used to
display the number of pages at boot up and the number in
/sys/kernel/tracing/dyn_ftrace_total_info). If order is negative, this
value could be used to debug what went wrong ;-)


> Doesn't this make the code now make SENSE? Instead of that
> incomprehensible mess it was before?

I'll look into it. This code has been there since pretty much the beginning
and slowly "grew". It suffered the thousand cuts, instead of going in and
doing surgery on making it clean. It hasn't changed in a long time, so it's
due for a clean up as I believe it's in a stable state now.

> 
> I dunno. Maybe it's just my "pee in the snow" thing, but honestly, the
> fact that I seem to have found another bug wrt the whole
> 'ftrace_number_of_pages' handling really says that the code was
> garbage.

Again, that variable was just used to see what the page count was. It was
never used for any logic.

> 
> And maybe it's just me who doesn't understand the subtle perfection of
> the old code, and I'm being stupid. Feel free to educate me about it.
> 
> Final note: note the "TOTALLY UNTESTED" part of the patch. The patch
> CompilesForMe(tm), but please consider it a "how about something like
> this" rather than anything finished.
> 
> Also note that I did *not* change the initial "order" calculation
> itself in ftrace_allocate_records() in this patch. I left that
> particular oddity alone. Again, I *think* the math just ends up being
> 
>         pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
>         order = fls(pages)-1;
> 
> but the attached patch is not about that, it's about the crazy "pg->size" games.
> 
>             Linus
> 
> PS. TOTALLY UNTESTED!!

Thanks, I'll look at it and see if it doesn't break anything, or if it can
be easily modified to not break anything.

-- Steve

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

On Wed, 31 Mar 2021 11:03:21 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> @@ -6231,7 +6231,8 @@ static int ftrace_process_locs(struct module *mod,
>  		if (!addr)
>  			continue;
>  
> -		if (pg->index == pg->size) {
> +		end_offset = (pg->index+1) * sizeof(pg->records[0]);
> +		if (end_offset < PAGE_SIZE << pg->order) {

I believe that needs to be:

	if (end_offset >= PAGE_SIZE << pg->order) {

But as you said, you didn't test it. I'll look to see what else needs to be
fixed.

-- Steve


>  			/* We should have allocated enough */
>  			if (WARN_ON(!pg->next))
>  				break;

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Linus Torvalds]

On Thu, Apr 1, 2021 at 1:07 PM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Wed, 31 Mar 2021 11:03:21 -0700
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
> > @@ -6231,7 +6231,8 @@ static int ftrace_process_locs(struct module *mod,
> >               if (!addr)
> >                       continue;
> >
> > -             if (pg->index == pg->size) {
> > +             end_offset = (pg->index+1) * sizeof(pg->records[0]);
> > +             if (end_offset < PAGE_SIZE << pg->order) {
>
> I believe that needs to be:
>
>         if (end_offset >= PAGE_SIZE << pg->order) {

No, but the "<" should be ">". That was just a typo.

It's ok for end_offset to be at the edge. That's the "we filled the
pages completely".

I'm not sure that can actually happen (it depends on the size of the
structure, and whether the size of the allocation is divisible by it),
but it's not wrong if it does.

Think of it this way: imagine that we have one 4kB page, and the size
of the structure is 1kB in size. You can fit 4 structures in it, and
end_offset for the last one will be index=3, so that you'll have:

        end_offset = (pg->index+1) * sizeof(pg->records[0]);

which will be

        end_offset = (3+1) * 1024;

ie 4096. That just means that the struct fill fill things _up_to_ the
end of the page.

So only when the end_offset is strictly larger than the page would it
have overflowed the allocation.

             Linus

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

On Thu, 1 Apr 2021 13:18:59 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Thu, Apr 1, 2021 at 1:07 PM Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> > On Wed, 31 Mar 2021 11:03:21 -0700
> > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >
> > > @@ -6231,7 +6231,8 @@ static int ftrace_process_locs(struct module *mod,
> > >               if (!addr)
> > >                       continue;
> > >
> > > -             if (pg->index == pg->size) {
> > > +             end_offset = (pg->index+1) * sizeof(pg->records[0]);
> > > +             if (end_offset < PAGE_SIZE << pg->order) {
> >
> > I believe that needs to be:
> >
> >         if (end_offset >= PAGE_SIZE << pg->order) {
> 

[..]

> which will be
> 
>         end_offset = (3+1) * 1024;
> 
> ie 4096. That just means that the struct fill fill things _up_to_ the
> end of the page.
> 
> So only when the end_offset is strictly larger than the page would it
> have overflowed the allocation.

Ah, I forgot about the "+1" you added to the pg->index, which would make it
equivalent to replacing:

	if (pg->index + 1 > pg->size) {


Will update and add your SOB.

Thanks,

-- Steve

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

On Thu, 1 Apr 2021 16:07:10 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> > @@ -6231,7 +6231,8 @@ static int ftrace_process_locs(struct module *mod,
> >  		if (!addr)
> >  			continue;
> >  
> > -		if (pg->index == pg->size) {
> > +		end_offset = (pg->index+1) * sizeof(pg->records[0]);
> > +		if (end_offset < PAGE_SIZE << pg->order) {  
> 
> I believe that needs to be:
> 
> 	if (end_offset >= PAGE_SIZE << pg->order) {
> 
> But as you said, you didn't test it. I'll look to see what else needs to be
> fixed.

After making the above change, it appears to work.

Want to give me your "Signed-off-by"?

-- Steve

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Steven Rostedt]

On Wed, 31 Mar 2021 10:45:01 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Wed, Mar 31, 2021 at 6:27 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> >                 order = get_count_order(pg->size / ENTRIES_PER_PAGE);
> > -               free_pages((unsigned long)pg->records, order);
> > +               if (order >= 0)
> > +                       free_pages((unsigned long)pg->records, order);  
> 
> Honestly, looking at that code, every single use of
> "get_count_order()" seems really really confusing.
> 
> And really confused.
> 
> The comments are garbage, the code is odd, it's just all very very strange.
> 
> See here in ftrace_allocate_records():
> 
>         pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
>         order = get_count_order(pages);
> 
>         /*
>          * We want to fill as much as possible. No more than a page
>          * may be empty.
>          */
>         if (!is_power_of_2(pages))
>                 order--;
> 
> can you actually explain what the logic is here?
> 
> The 'get_count_order()' function will return the smallest order that
> the value fits in. But then if the value wasn't a power of two, you
> subtract 1. If I understand the code correctly, that's just the same
> as "what is the highest bit set", isn't it?
> 
> So afaik, what you *actually* want is just
> 
>         pages = DIV_ROUND_UP(count, ENTRIES_PER_PAGE);
>         order = fls(pages)-1;
> 
> isn't it?

I'll have to look at this a bit more, but this could be a new improvement
of the logic. The last one was: 

b40c6eabfcd40 ("ftrace: Simplify the calculation of page number for ftrace_page->records")

This happens once at boot up (and once for each module loaded) so I never
thought about making it efficient.

> 
> Did I misunderstand what the code wants to do? The "No more than a
> page may be empty" seems wrong - you really mean "no empty pages".

Yeah, that could be worded better.

> 
> I dunno. Maybe I'm wrong, but that code is really confusing (which is
> why I may be wrong). It doesn't seem to make any sense at all to use
> "get_count_order()" and then modify the end result.
> 

The basic idea is that we are allocating a group of pages for 10s
of thousands of records (one for every function being traced). The way the
records are stored is by "page group" (pg). It's a link list of pages
filled with records. The records are sorted by instruction pointer of the
functions they represent. There are times we need to quickly search for a
record and this is done by iterating the link list of page groups, and then
doing a binary search of the records in the pages that are there.

The more records you store in a single group, the faster this algorithm is
(more binary searches, less iterating a link list). But since these records
are permanently in the memory, we also do not want to allocate more than
needed to store the records. Now because pages are only allocated in powers
of two (1, 2, 4, 8, 16, ...) If it takes 5 pages to store all the records,
we don't want to allocate 8 pages for it. Instead we make a link list where
the first entry has 4 pages the second has 1.

In the dmesg on boot up, you'll see something like this:

 ftrace: allocating 42979 entries in 168 pages
 ftrace: allocated 168 pages with 3 groups


That shows that the link list is size of 3, and it used 168 pages to
store the 42,979 records.

What the logic above does is to figure out how many pages are needed to
store all the records. If the value is not a power of two (say 5 pages),
where the order would give use 8 pages. We subtract one from the order (to
give us 4 pages), and store what we can there. The next time around we only
allocate 1 page to store the rest of the records.

Your fls() trick might work too (have to gawk at it more). And I should fix
the comments. But any work on that would be for the next merge window, and
doesn't affect that this patch fixes a possible issue.

-- Steve

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[Linus Torvalds]

On Wed, Mar 31, 2021 at 11:51 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> Your fls() trick might work too (have to gawk at it more). And I should fix
> the comments. But any work on that would be for the next merge window, and
> doesn't affect that this patch fixes a possible issue.

See my second email. It doesn't even fix the actual issues.

           Linus

Re: [GIT PULL] ftrace: Check if pages were allocated before calling free_pages()

[pr-tracker-bot]

The pull request you sent on Wed, 31 Mar 2021 09:27:11 -0400:

> git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git trace-v5.12-rc5

has been merged into torvalds/linux.git:
https://git.kernel.org/torvalds/c/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c

Thank you!

-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/prtracker.html