linux-kernel - Re: [RFC] mm: support multi_freearea to the reduction of external fragmentation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <a7bb16c0-31b2-6aa5-2186-8c957955649e@suse.cz>
Date:   Fri, 16 Apr 2021 13:06:49 +0200
From:   Vlastimil Babka <vbabka@...e.cz>
To:     lipeifeng@...o.com, peifengl55@...il.com, schwidefsky@...ibm.com,
        heiko.carstens@...ibm.com
Cc:     linux-s390@...r.kernel.org, linux-kernel@...r.kernel.org,
        linux-mm@...ck.org
Subject: Re: [RFC] mm: support multi_freearea to the reduction of external
 fragmentation

On 4/14/21 4:38 AM, lipeifeng@...o.com wrote:
> From: lipeifeng <lipeifeng@...o.com>
> 
> This patch would "sort" the free-pages in buddy by pages-PFN to concentrate
> low-order-pages allocation in the front area of memory and high-order-pages
> allcation on the contrary so that few memory-pollution in the back area of
> memory and the probablity of high-order-pages allocation would be increased
> significantly.
> -----------------------------------------------------------------------
> 
>   1) Divide memory into several segments by pages-PFN
>      "Multi_freearea" would divide memory into FREE_AREA_COUNTS segments
>      by pages-PFN,each memory-segment corresponds to a free_area.
> 
>      Example: machine(4G of physical memery) and FREE_AREA_COUNTS(4):
>         page-PFN:0x0     0x40000(1G)   0x80000(2G)  0xc0000(3G) 0xFFFFF(4G)
>                  |------------|--------------|--------------|-------------|
>         free_area:  [0][]           [1][]           [2][]        [3][]
> 
>      NOTE: Selecting the corresponding freearea when pages are freed back
> 	       to buddy:
>         - pages-PFN[0, free_area_segment[0].max_pfn] -> free_area[0][]
>         - pages-PFN[free_area_segment[flc - 1].max_pfn,
> 	            free_area_segment[flc].max_pfn] -> free_area[flc][]
>                    (flc > 0)
> 
>      By this way, all pages in the same segment/free_area is within a
>      certain range of pages-PFN.
> 
>   2) Select the corresponding freearea to alloc-pages
>      "Multi_freearea" would select the corresponding free_area by the
>      allocation-order when alloc-pages.
>         - order <  HIGH_ORDER_TO_FLC:
> 	        free_area[0] -> ... -> free_area[FREE_AREA_COUNTS - 1]
>         - order >= HIGH_ORDER_TO_FLC:
> 	        free_area[FREE_AREA_COUNTS - 1] -> ... -> free_area[0]
> 
>      Example:
>         The machine(4G of physical memery) and FREE_AREA_COUNTS(4)
>         and HIGH_ORDER_TO_FLC(3).
> 	If user allocs page(order = 0),it would take page from
> 	free_area[0][] first, if that fails,try free_area[1][] and so on.
> 	If user allocs page(order = 4),it would take page from
> 	free_area[3][] first, if that fails,try free_area[2][] and so on.
> 
>      By this way,low-order pages will be concentrated in the front area
>      of memory.Because of few memory-pollution in the back area of memory,
>      the sussessful probablity of high-order allocation would be improved.
> 
>   3) Adjust the location of free-pages in the free_list
>      "Multi_freearea" would place free-pages in the head of free_list if
>      pages-PFN is smaller than free_area_segment[flc]->median_pfn and in
>      the tail of free_list on the contrary.
> 
>      Example:
>         page-PFN:        free_area_segment[flc]->median_pfn
>                                         |
>         free_list: page->page->page->...|...page->page->page
>         pages-PFN:|   < median_pfn      |  >= median_pfn    |
> 
>      Because it would take pages from the head of the freelist first in
>      buddy system,the free-pages in the tail are more likely to keep in the
>      buddy system.The closer the PFN of pages kept in buddy system, the
>      greater the probablity of merging that into high-order pages.

I think this part 3) would be worth to be tried separately first, as it's not a
big change compared to the other ones.