How cma allocation works ?

How cma allocation works ?

[Pankaj Suryawanshi]

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

Hello,

Hard time to understand cma allocation how differs from normal allocation ?

I know theoretically how cma works.

1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
functions ?
2. How alloc_contig_range() works ? it isolate all the pages including
unevictable pages, what is the practical work flow ? all this works with
virtual pages or physical pages ?
3.what start_isolate_page_range() does ?
4. what alloc_contig_migrate_range does() ?
5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
 migrate_pages() and shrink_page_list() is doing ?

Please let me know the flow with simple example.

Regards,
Pankaj

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

Re: How cma allocation works ?

[Michal Hocko]

On Wed 21-08-19 22:58:03, Pankaj Suryawanshi wrote:
> Hello,
> 
> Hard time to understand cma allocation how differs from normal allocation ?

The buddy allocator which is built for order-N sized allocations and it
is highly optimized because it used from really hot paths. The allocator
also involves memory reclaim to get memory when there is none
immediatelly available.

CMA allocator operates on a pre reserved physical memory range(s) and
focuses on allocating areas that require physically contigous memory of
larger sizes. Very broadly speaking. LWN usually contains nice writeups
for many kernel internals. E.g. quick googling pointed to https://lwn.net/Articles/486301/

> I know theoretically how cma works.
> 
> 1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
> functions ?

Not sure what you are asking here TBH

> 2. How alloc_contig_range() works ? it isolate all the pages including
> unevictable pages, what is the practical work flow ? all this works with
> virtual pages or physical pages ?

Yes it isolates a specific physical contiguous (pfn) range, tries to
move any used memory within that range and make it available for the
caller.

> 3.what start_isolate_page_range() does ?

There is some documentation for that function. Which part is not clear?

> 4. what alloc_contig_migrate_range does() ?

Have you checked the code? It simply tries to reclaim and/or migrate
pages off the pfn range.

> 5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
>  migrate_pages() and shrink_page_list() is doing ?

Again, have you checked the code/comments? What exactly is not clear?
 
> Please let me know the flow with simple example.

Look at alloc_gigantic_page which is using the contiguous allocator to
get 1GB physically contiguous memory ranges to be used for hugetlb
pages.

HTH
-- 
Michal Hocko
SUSE Labs

Re: How cma allocation works ?

[Pankaj Suryawanshi]

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

On Thu, Aug 22, 2019 at 6:32 PM Michal Hocko <mhocko@kernel.org> wrote:
>
> On Wed 21-08-19 22:58:03, Pankaj Suryawanshi wrote:
> > Hello,
> >
> > Hard time to understand cma allocation how differs from normal
allocation ?
>
> The buddy allocator which is built for order-N sized allocations and it
> is highly optimized because it used from really hot paths. The allocator
> also involves memory reclaim to get memory when there is none
> immediatelly available.
>
> CMA allocator operates on a pre reserved physical memory range(s) and
> focuses on allocating areas that require physically contigous memory of
> larger sizes. Very broadly speaking. LWN usually contains nice writeups
> for many kernel internals. E.g. quick googling pointed to
https://lwn.net/Articles/486301/
>
> > I know theoretically how cma works.
> >
> > 1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
> > functions ?
>
> Not sure what you are asking here TBH
I know it reserved memory at boot time from start pfn to end pfn, but when
i am requesting memory from cma it has different bitmap_*() in cma_alloc()
what they are ?
because we pass pfn and pfn+count to alloc_contig_range and pfn is come
from bitmap_*() function.
lets say i have reserved 100MB cma memory at boot time (strart pfn to end
pfn) and i am requesting allocation of 30MB from cma area then what is pfn
passed to alloc_contig_range() it is same as start pfn or
different.(calucaled by bitmap_*()) ?
>
> > 2. How alloc_contig_range() works ? it isolate all the pages including
> > unevictable pages, what is the practical work flow ? all this works with
> > virtual pages or physical pages ?
>
> Yes it isolates a specific physical contiguous (pfn) range, tries to
> move any used memory within that range and make it available for the
> caller.
what i understood here is that it isolate pages between range as
MIGRATE_ISOLATE, removed pages from buddy allocator including
allocated(movable/unevictable) pages. how unevictable pages isolated here ?
>
> > 3.what start_isolate_page_range() does ?
>
> There is some documentation for that function. Which part is not clear?
>
mention in above question

> > 4. what alloc_contig_migrate_range does() ?
>
> Have you checked the code? It simply tries to reclaim and/or migrate
> pages off the pfn range.
>
What is difference between migration, isolation and reclamation of pages ?

> > 5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
> >  migrate_pages() and shrink_page_list() is doing ?
>
> Again, have you checked the code/comments? What exactly is not clear?
>
Why again migrate_isolate_range() ?
(reclaim_clean_pages_fron_list) if we are reclaiming only clean pages then
pages will not contiguous ? we have only clean pages which are not
contiguous ?
What is work of shrink_page_list() ? please explain all flow with taking
one allocation for example let say reserved cma 100MB and then request
allocation of 30MB then how all the flow/function will work ?
> > Please let me know the flow with simple example.
>
> Look at alloc_gigantic_page which is using the contiguous allocator to
> get 1GB physically contiguous memory ranges to be used for hugetlb
> pages.
>
Thanks
> HTH
> --
> Michal Hocko
> SUSE Labs

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

Re: How cma allocation works ?

[Michal Hocko]

On Fri 23-08-19 00:17:22, Pankaj Suryawanshi wrote:
> On Thu, Aug 22, 2019 at 6:32 PM Michal Hocko <mhocko@kernel.org> wrote:
> >
> > On Wed 21-08-19 22:58:03, Pankaj Suryawanshi wrote:
> > > Hello,
> > >
> > > Hard time to understand cma allocation how differs from normal
> > > allocation ?
> >
> > The buddy allocator which is built for order-N sized allocations and it
> > is highly optimized because it used from really hot paths. The allocator
> > also involves memory reclaim to get memory when there is none
> > immediatelly available.
> >
> > CMA allocator operates on a pre reserved physical memory range(s) and
> > focuses on allocating areas that require physically contigous memory of
> > larger sizes. Very broadly speaking. LWN usually contains nice writeups
> > for many kernel internals. E.g. quick googling pointed to
> > https://lwn.net/Articles/486301/
> >
> > > I know theoretically how cma works.
> > >
> > > 1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
> > > functions ?
> >
> > Not sure what you are asking here TBH
> I know it reserved memory at boot time from start pfn to end pfn, but when
> i am requesting memory from cma it has different bitmap_*() in cma_alloc()
> what they are ?
> because we pass pfn and pfn+count to alloc_contig_range and pfn is come
> from bitmap_*() function.
> lets say i have reserved 100MB cma memory at boot time (strart pfn to end
> pfn) and i am requesting allocation of 30MB from cma area then what is pfn
> passed to alloc_contig_range() it is same as start pfn or
> different.(calucaled by bitmap_*()) ?

I am not deeply familiar with the CMA implementation but from a very
brief look it seems that the bitmap simply denotes which portions of the
reserved area are used and therefore it is easy to find portions of the
requested size by scanning it.

> > Have you checked the code? It simply tries to reclaim and/or migrate
> > pages off the pfn range.
> >
> What is difference between migration, isolation and reclamation of pages ?

Isolation will set the migrate type to MIGRATE_ISOLATE, btw the comment
in the code I referred to says this:
 * Making page-allocation-type to be MIGRATE_ISOLATE means free pages in
 * the range will never be allocated. Any free pages and pages freed in the
 * future will not be allocated again. If specified range includes migrate types
 * other than MOVABLE or CMA, this will fail with -EBUSY. For isolating all
 * pages in the range finally, the caller have to free all pages in the range.
 * test_page_isolated() can be used for test it.

Reclaim part will simply drop all pages that are easily reclaimable
(e.g. a clean pagecache) and migration will move existing allocations to
a different physical location + update references to it from other data
structures (e.g. page tables to point to a new location).

> > > 5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
> > >  migrate_pages() and shrink_page_list() is doing ?
> >
> > Again, have you checked the code/comments? What exactly is not clear?
> >
> Why again migrate_isolate_range() ?
> (reclaim_clean_pages_fron_list) if we are reclaiming only clean pages then
> pages will not contiguous ? we have only clean pages which are not
> contiguous ?

reclaim_clean_pages_from_list is a simple wrapper on top of shrink_page_list.
It simply takes clean page cache pages to reclaim it because that might
be less expensive than migrating that memory.

> What is work of shrink_page_list() ?

This is a core of the memory reclaim. It unmaps/frees pages and try to
free them.

> please explain all flow with taking
> one allocation for example let say reserved cma 100MB and then request
> allocation of 30MB then how all the flow/function will work ?

I would recommend to read the code carefully and following the git
history of the code is very helpful as well. This is not a rocket
science, really.
-- 
Michal Hocko
SUSE Labs

Re: How cma allocation works ?

[Pankaj Suryawanshi]

On Mon, Aug 26, 2019 at 12:55 PM Michal Hocko <mhocko@kernel.org> wrote:
>
> On Fri 23-08-19 00:17:22, Pankaj Suryawanshi wrote:
> > On Thu, Aug 22, 2019 at 6:32 PM Michal Hocko <mhocko@kernel.org> wrote:
> > >
> > > On Wed 21-08-19 22:58:03, Pankaj Suryawanshi wrote:
> > > > Hello,
> > > >
> > > > Hard time to understand cma allocation how differs from normal
> > > > allocation ?
> > >
> > > The buddy allocator which is built for order-N sized allocations and it
> > > is highly optimized because it used from really hot paths. The allocator
> > > also involves memory reclaim to get memory when there is none
> > > immediatelly available.
> > >
> > > CMA allocator operates on a pre reserved physical memory range(s) and
> > > focuses on allocating areas that require physically contigous memory of
> > > larger sizes. Very broadly speaking. LWN usually contains nice writeups
> > > for many kernel internals. E.g. quick googling pointed to
> > > https://lwn.net/Articles/486301/
> > >
> > > > I know theoretically how cma works.
> > > >
> > > > 1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
> > > > functions ?
> > >
> > > Not sure what you are asking here TBH
> > I know it reserved memory at boot time from start pfn to end pfn, but when
> > i am requesting memory from cma it has different bitmap_*() in cma_alloc()
> > what they are ?
> > because we pass pfn and pfn+count to alloc_contig_range and pfn is come
> > from bitmap_*() function.
> > lets say i have reserved 100MB cma memory at boot time (strart pfn to end
> > pfn) and i am requesting allocation of 30MB from cma area then what is pfn
> > passed to alloc_contig_range() it is same as start pfn or
> > different.(calucaled by bitmap_*()) ?
>
> I am not deeply familiar with the CMA implementation but from a very
> brief look it seems that the bitmap simply denotes which portions of the
> reserved area are used and therefore it is easy to find portions of the
> requested size by scanning it.
> okay
> > > Have you checked the code? It simply tries to reclaim and/or migrate
> > > pages off the pfn range.
> > >
> > What is difference between migration, isolation and reclamation of pages ?
>
> Isolation will set the migrate type to MIGRATE_ISOLATE, btw the comment
> in the code I referred to says this:
>  * Making page-allocation-type to be MIGRATE_ISOLATE means free pages in
>  * the range will never be allocated. Any free pages and pages freed in the
>  * future will not be allocated again. If specified range includes migrate types
>  * other than MOVABLE or CMA, this will fail with -EBUSY. For isolating all
>  * pages in the range finally, the caller have to free all pages in the range.
>  * test_page_isolated() can be used for test it.
>
> Reclaim part will simply drop all pages that are easily reclaimable
> (e.g. a clean pagecache) and migration will move existing allocations to
> a different physical location + update references to it from other data
> structures (e.g. page tables to point to a new location).


Okay Thanks michal, now it will easy to understand.
>
>
>
> > > > 5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
> > > >  migrate_pages() and shrink_page_list() is doing ?
> > >
> > > Again, have you checked the code/comments? What exactly is not clear?
> > >
> > Why again migrate_isolate_range() ?
> > (reclaim_clean_pages_fron_list) if we are reclaiming only clean pages then
> > pages will not contiguous ? we have only clean pages which are not
> > contiguous ?
>
> reclaim_clean_pages_from_list is a simple wrapper on top of shrink_page_list.
> It simply takes clean page cache pages to reclaim it because that might
> be less expensive than migrating that memory.
> okay
> > What is work of shrink_page_list() ?
>
> This is a core of the memory reclaim. It unmaps/frees pages and try to
> free them.
> okay
> > please explain all flow with taking
> > one allocation for example let say reserved cma 100MB and then request
> > allocation of 30MB then how all the flow/function will work ?
>
> I would recommend to read the code carefully and following the git
> history of the code is very helpful as well. This is not a rocket
> science, really.
hahaha rocket science !!! I think linux memory management should be
part of rocket science.
>
> --
> Michal Hocko
> SUSE Labs

Re: How cma allocation works ?

[Pankaj Suryawanshi]

On Mon, Aug 26, 2019 at 12:55 PM Michal Hocko <mhocko@kernel.org> wrote:
>
> On Fri 23-08-19 00:17:22, Pankaj Suryawanshi wrote:
> > On Thu, Aug 22, 2019 at 6:32 PM Michal Hocko <mhocko@kernel.org> wrote:
> > >
> > > On Wed 21-08-19 22:58:03, Pankaj Suryawanshi wrote:
> > > > Hello,
> > > >
> > > > Hard time to understand cma allocation how differs from normal
> > > > allocation ?
> > >
> > > The buddy allocator which is built for order-N sized allocations and it
> > > is highly optimized because it used from really hot paths. The allocator
> > > also involves memory reclaim to get memory when there is none
> > > immediatelly available.
> > >
> > > CMA allocator operates on a pre reserved physical memory range(s) and
> > > focuses on allocating areas that require physically contigous memory of
> > > larger sizes. Very broadly speaking. LWN usually contains nice writeups
> > > for many kernel internals. E.g. quick googling pointed to
> > > https://lwn.net/Articles/486301/
> > >
> > > > I know theoretically how cma works.
> > > >
> > > > 1. How it reserved the memory (start pfn to end pfn) ? what is bitmap_*
> > > > functions ?
> > >
> > > Not sure what you are asking here TBH
> > I know it reserved memory at boot time from start pfn to end pfn, but when
> > i am requesting memory from cma it has different bitmap_*() in cma_alloc()
> > what they are ?
> > because we pass pfn and pfn+count to alloc_contig_range and pfn is come
> > from bitmap_*() function.
> > lets say i have reserved 100MB cma memory at boot time (strart pfn to end
> > pfn) and i am requesting allocation of 30MB from cma area then what is pfn
> > passed to alloc_contig_range() it is same as start pfn or
> > different.(calucaled by bitmap_*()) ?
>
> I am not deeply familiar with the CMA implementation but from a very
> brief look it seems that the bitmap simply denotes which portions of the
> reserved area are used and therefore it is easy to find portions of the
> requested size by scanning it.
> okay
> > > Have you checked the code? It simply tries to reclaim and/or migrate
> > > pages off the pfn range.
> > >
> > What is difference between migration, isolation and reclamation of pages ?
>
> Isolation will set the migrate type to MIGRATE_ISOLATE, btw the comment
> in the code I referred to says this:
>  * Making page-allocation-type to be MIGRATE_ISOLATE means free pages in
>  * the range will never be allocated. Any free pages and pages freed in the
>  * future will not be allocated again. If specified range includes migrate types
>  * other than MOVABLE or CMA, this will fail with -EBUSY. For isolating all
>  * pages in the range finally, the caller have to free all pages in the range.
>  * test_page_isolated() can be used for test it.
>
> Reclaim part will simply drop all pages that are easily reclaimable
> (e.g. a clean pagecache) and migration will move existing allocations to
> a different physical location + update references to it from other data
> structures (e.g. page tables to point to a new location).


Okay Thanks michal, now it will easy to understand.
>
>
>
> > > > 5.what isolate_migratepages_range(), reclaim_clean_pages_from_list(),
> > > >  migrate_pages() and shrink_page_list() is doing ?
> > >
> > > Again, have you checked the code/comments? What exactly is not clear?
> > >
> > Why again migrate_isolate_range() ?
> > (reclaim_clean_pages_fron_list) if we are reclaiming only clean pages then
> > pages will not contiguous ? we have only clean pages which are not
> > contiguous ?
>
> reclaim_clean_pages_from_list is a simple wrapper on top of shrink_page_list.
> It simply takes clean page cache pages to reclaim it because that might
> be less expensive than migrating that memory.
> okay
> > What is work of shrink_page_list() ?
>
> This is a core of the memory reclaim. It unmaps/frees pages and try to
> free them.
> okay
> > please explain all flow with taking
> > one allocation for example let say reserved cma 100MB and then request
> > allocation of 30MB then how all the flow/function will work ?
>
> I would recommend to read the code carefully and following the git
> history of the code is very helpful as well. This is not a rocket
> science, really.
hahaha rocket science !!! I think linux memory management should be
part of rocket science.
>
> --
> Michal Hocko
> SUSE Labs