Can kfree() sleep at runtime?

Can kfree() sleep at runtime?

[Jia-Ju Bai]

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

Hello,

I write a static analysis tool (DSAC), and it finds that kfree() can sleep.

Here is the call path for kfree().
Please look at it *from the bottom up*.

[FUNC] alloc_pages(GFP_KERNEL)
arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
arch/x86/mm/pageattr.c, 1391: __change_page_attr in 
__change_page_attr_set_clr
arch/x86/mm/pageattr.c, 2014: __change_page_attr_set_clr in __set_pages_np
arch/x86/mm/pageattr.c, 2034: __set_pages_np in __kernel_map_pages
./include/linux/mm.h, 2488: __kernel_map_pages in kernel_map_pages
mm/page_alloc.c, 1074: kernel_map_pages in free_pages_prepare
mm/page_alloc.c, 1264: free_pages_prepare in __free_pages_ok
mm/page_alloc.c, 4312: __free_pages_ok in __free_pages
mm/slub.c, 3914: __free_pages in kfree

I always have an impression that kfree() never sleeps, so I feel 
confused here.
So could someone please help me to find the mistake?
Thanks in advance :)

Best wishes,
Jia-Ju Bai

[-- Attachment #2: Type: text/html, Size: 1492 bytes --]

Re: Can kfree() sleep at runtime?

[Matthew Wilcox]

On Thu, May 31, 2018 at 09:10:07PM +0800, Jia-Ju Bai wrote:
> I write a static analysis tool (DSAC), and it finds that kfree() can sleep.
> 
> Here is the call path for kfree().
> Please look at it *from the bottom up*.
> 
> [FUNC] alloc_pages(GFP_KERNEL)
> arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
> arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr

Here's your bug.  Coming from kfree(), we can't end up in the
split_large_page() path.  __change_page_attr may be called in several
different circumstances in which it would have to split a large page,
but the path from kfree() is not one of them.

I think the path from kfree() will lead to the 'level == PG_LEVEL_4K'
path, but I'm not really familiar with this x86 code.

> arch/x86/mm/pageattr.c, 1391: __change_page_attr in
> __change_page_attr_set_clr
> arch/x86/mm/pageattr.c, 2014: __change_page_attr_set_clr in __set_pages_np
> arch/x86/mm/pageattr.c, 2034: __set_pages_np in __kernel_map_pages
> ./include/linux/mm.h, 2488: __kernel_map_pages in kernel_map_pages
> mm/page_alloc.c, 1074: kernel_map_pages in free_pages_prepare
> mm/page_alloc.c, 1264: free_pages_prepare in __free_pages_ok
> mm/page_alloc.c, 4312: __free_pages_ok in __free_pages
> mm/slub.c, 3914: __free_pages in kfree
> 
> I always have an impression that kfree() never sleeps, so I feel confused
> here.
> So could someone please help me to find the mistake?
> Thanks in advance :)
> 
> Best wishes,
> Jia-Ju Bai

Re: Can kfree() sleep at runtime?

[Christopher Lameter]

On Thu, 31 May 2018, Matthew Wilcox wrote:

> On Thu, May 31, 2018 at 09:10:07PM +0800, Jia-Ju Bai wrote:
> > I write a static analysis tool (DSAC), and it finds that kfree() can sleep.
> >
> > Here is the call path for kfree().
> > Please look at it *from the bottom up*.
> >
> > [FUNC] alloc_pages(GFP_KERNEL)
> > arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
> > arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
>
> Here's your bug.  Coming from kfree(), we can't end up in the
> split_large_page() path.  __change_page_attr may be called in several
> different circumstances in which it would have to split a large page,
> but the path from kfree() is not one of them.

Freeing a page in the page allocator also was traditionally not sleeping.
That has changed?

Re: Can kfree() sleep at runtime?

[Matthew Wilcox]

On Thu, May 31, 2018 at 02:12:00PM +0000, Christopher Lameter wrote:
> On Thu, 31 May 2018, Matthew Wilcox wrote:
> 
> > On Thu, May 31, 2018 at 09:10:07PM +0800, Jia-Ju Bai wrote:
> > > I write a static analysis tool (DSAC), and it finds that kfree() can sleep.
> > >
> > > Here is the call path for kfree().
> > > Please look at it *from the bottom up*.
> > >
> > > [FUNC] alloc_pages(GFP_KERNEL)
> > > arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
> > > arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
> >
> > Here's your bug.  Coming from kfree(), we can't end up in the
> > split_large_page() path.  __change_page_attr may be called in several
> > different circumstances in which it would have to split a large page,
> > but the path from kfree() is not one of them.
> 
> Freeing a page in the page allocator also was traditionally not sleeping.
> That has changed?

No.  "Your bug" being "The bug in your static analysis tool".  It probably
isn't following the data flow correctly (or deeply enough).

Re: Can kfree() sleep at runtime?

[Christopher Lameter]

On Thu, 31 May 2018, Matthew Wilcox wrote:

> > Freeing a page in the page allocator also was traditionally not sleeping.
> > That has changed?
>
> No.  "Your bug" being "The bug in your static analysis tool".  It probably
> isn't following the data flow correctly (or deeply enough).

Well ok this is not going to trigger for kfree(), this is x86 specific and
requires CONFIG_DEBUG_PAGEALLOC and a free of a page in a huge page.

Ok that is a very contorted situation but how would a static checker deal
with that?

Re: Can kfree() sleep at runtime?

[Jia-Ju Bai]

On 2018/5/31 22:30, Christopher Lameter wrote:
> On Thu, 31 May 2018, Matthew Wilcox wrote:
>
>>> Freeing a page in the page allocator also was traditionally not sleeping.
>>> That has changed?
>> No.  "Your bug" being "The bug in your static analysis tool".  It probably
>> isn't following the data flow correctly (or deeply enough).
> Well ok this is not going to trigger for kfree(), this is x86 specific and
> requires CONFIG_DEBUG_PAGEALLOC and a free of a page in a huge page.
>
> Ok that is a very contorted situation but how would a static checker deal
> with that?

I admit that my tool does not follow the data flow well, and I need to 
improve it.
In this case of kfree(), I want know how the data flow leads to my mistake.


Best wishes,
Jia-Ju Bai

Re: Can kfree() sleep at runtime?

[Nadav Amit]

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

Jia-Ju Bai <baijiaju1990@gmail.com> wrote:

> 
> 
> On 2018/5/31 22:30, Christopher Lameter wrote:
>> On Thu, 31 May 2018, Matthew Wilcox wrote:
>> 
>>>> Freeing a page in the page allocator also was traditionally not sleeping.
>>>> That has changed?
>>> No.  "Your bug" being "The bug in your static analysis tool".  It probably
>>> isn't following the data flow correctly (or deeply enough).
>> Well ok this is not going to trigger for kfree(), this is x86 specific and
>> requires CONFIG_DEBUG_PAGEALLOC and a free of a page in a huge page.
>> 
>> Ok that is a very contorted situation but how would a static checker deal
>> with that?
> 
> I admit that my tool does not follow the data flow well, and I need to improve it.
> In this case of kfree(), I want know how the data flow leads to my mistake.

Note that is only enabled in debug mode:

static inline void
kernel_map_pages(struct page *page, int numpages, int enable)
{
        if (!debug_pagealloc_enabled())
                return;

        __kernel_map_pages(page, numpages, enable);
}

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: Can kfree() sleep at runtime?

[Jia-Ju Bai]

On 2018/5/31 22:08, Matthew Wilcox wrote:
> On Thu, May 31, 2018 at 09:10:07PM +0800, Jia-Ju Bai wrote:
>> I write a static analysis tool (DSAC), and it finds that kfree() can sleep.
>>
>> Here is the call path for kfree().
>> Please look at it *from the bottom up*.
>>
>> [FUNC] alloc_pages(GFP_KERNEL)
>> arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
>> arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
> Here's your bug.  Coming from kfree(), we can't end up in the
> split_large_page() path.  __change_page_attr may be called in several
> different circumstances in which it would have to split a large page,
> but the path from kfree() is not one of them.
>
> I think the path from kfree() will lead to the 'level == PG_LEVEL_4K'
> path, but I'm not really familiar with this x86 code.

Thanks for reply :)
But from the code in my call path, I cannot find why kfree() will only lead to the 'level == PG_LEVEL_4K' path.
Could you please explain it in more detail?


Best wishes,
Jia-Ju Bai
  

Re: Can kfree() sleep at runtime?

[Christopher Lameter]

On Thu, 31 May 2018, Jia-Ju Bai wrote:

> I write a static analysis tool (DSAC), and it finds that kfree() can sleep.

That should not happen.

> Here is the call path for kfree().
> Please look at it *from the bottom up*.
>
> [FUNC] alloc_pages(GFP_KERNEL)
> arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
> arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
> arch/x86/mm/pageattr.c, 1391: __change_page_attr in __change_page_attr_set_clr
> arch/x86/mm/pageattr.c, 2014: __change_page_attr_set_clr in __set_pages_np
> arch/x86/mm/pageattr.c, 2034: __set_pages_np in __kernel_map_pages
> ./include/linux/mm.h, 2488: __kernel_map_pages in kernel_map_pages
> mm/page_alloc.c, 1074: kernel_map_pages in free_pages_prepare

mapping pages in the page allocator can cause allocations?? How did that
get in there?

> mm/page_alloc.c, 1264: free_pages_prepare in __free_pages_ok
> mm/page_alloc.c, 4312: __free_pages_ok in __free_pages
> mm/slub.c, 3914: __free_pages in kfree
>
> I always have an impression that kfree() never sleeps, so I feel confused
> here.

Correct.

Re: Can kfree() sleep at runtime?

[Jia-Ju Bai]

On 2018/5/31 22:09, Christopher Lameter wrote:
> On Thu, 31 May 2018, Jia-Ju Bai wrote:
>
>> I write a static analysis tool (DSAC), and it finds that kfree() can sleep.
> That should not happen.
>
>> Here is the call path for kfree().
>> Please look at it *from the bottom up*.
>>
>> [FUNC] alloc_pages(GFP_KERNEL)
>> arch/x86/mm/pageattr.c, 756: alloc_pages in split_large_page
>> arch/x86/mm/pageattr.c, 1283: split_large_page in __change_page_attr
>> arch/x86/mm/pageattr.c, 1391: __change_page_attr in __change_page_attr_set_clr
>> arch/x86/mm/pageattr.c, 2014: __change_page_attr_set_clr in __set_pages_np
>> arch/x86/mm/pageattr.c, 2034: __set_pages_np in __kernel_map_pages
>> ./include/linux/mm.h, 2488: __kernel_map_pages in kernel_map_pages
>> mm/page_alloc.c, 1074: kernel_map_pages in free_pages_prepare
> mapping pages in the page allocator can cause allocations?? How did that
> get in there?

Thanks for reply :)
I am also confused about it.

I get in here according to the definition of free_pages_prepare():
1022. static bool free_pages_prepare(...) {
              ...
1072.    arch_free_page(page, order);
1073.    kernel_poison_pages(page, 1 << order, 0);
1074.    kernel_map_pages(page, 1 << order, 0); // *Here*
1075.    kasan_free_pages(page, order);
1076.
1077.    return true;
1078. }


Best wishes,
Jia-Ju Bai