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

["lipeifeng@oppo.com" <lipeifeng@oppo.com>]

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


>> Let's consider part 3 only and ignore the 1) multi freearea (which might
>> be problematic with sparcity) and 2) the modified allocation scheme
>> (which doesn't yet quite sense to me yet, e.g., because we group by
>> mobility and have compaction in place; I assume this really only helps
>> in some special cases -- like the test case you are giving; I might be
>> wrong)
 
>> Right now, we decide whether to but to head or tail based on how likely
>> it is that we might merge to a higher-order page (buddy_merge_likely())
>> in the future. So we only consider the current "neighborhood" of the
>> page we're freeing. As we restrict our neighborhood to MAX_ORDER - 1
>> pages (what we can actually merge). Of course, we can easily be wrong
>> here. Grouping by movability and compaction only helps to some degree I
>> guess.
 
>> AFAIK, what you propose is basing the decisions where to place a page
>> (in addition?) on a median_pfn. Without 1) and 2) I cannot completely
>> understand if 3) itself would help at all (and how to set the
>> median_pfn). But it would certainly be interesting if we can tweak the
>> current logic to better identify merge targets simply by tweaking
>> buddy_merge_likely() or the assumptions it is making.



Hi David Hildenbrand， Vlastimil Babka:
    Thank you very much indeed for advices.

>> 2) the modified allocation scheme
>> (which doesn't yet quite sense to me yet, e.g., because we group by
>> mobility and have compaction in place; I assume this really only helps
>> in some special cases -- like the test case you are giving;
 ---------------------------------------------------------------------------------
1) Divide memory into several segments by pages-PFN 
2) Select the corresponding freearea to alloc-pages         
    These two parts art for the same purpose: 
    low-order-pages allocation will be concentrated in the front area of physical  memory
    so that few memory-pollution in the back area of memory, the sussessful probablity
    of high-order allocation would be improved.

    I think that it would help in almost all cases of high-oder-pages allocation, instead
    of special case, because it can let more high-order free-pages in buddy, example:
when user alloc 64K bytes, if the unit is page(4K bytes) and it needs to 16 times.  
             if the unit is 64Kbytes, it only takes once.
if there are more free-high-order-pages in buddy that few compact-stall in
             alloction-process, the allocstall-time would be shortened.

    We tested the speed of the high-orders-pages(order=4 and order = 8) allocation
    after monkey and found that it increased by more than 18%.

3) Adjust the location of free-pages in the free_list
>>Without 1) and 2) I cannot completely
>>understand if 3) itself would help at all (and how to set the median_pfn)
-----------------------------------------------------------------------------------------------------
    Median_pfn is set by the range of pages-PFN of free_area. if part 3) would be tried separately
    without 1) and 2), the simple setting is the median of the entire memory. But i think it will play the
    better role in optimization based on the 1) and 2).



>> Last but not least, there have to be more benchmarks and test cases that
>> proof that other workload won't be degraded to a degree that people
>> care; as one example, this includes runtime overhead when
>> allocating/freeing pages.    
---------------------------------------------
1. For modification of buddy: the modified allocation scheme 1)+2)
    Is thers any standard detailed test-list  of the modified allocation in the community? like benchmarks
    or any other tests? if  i pass the test required by communiry that can proof the patch will not degraded
    to a degree that people care and can merge it in the baseline?

   
    Thanks.
    
    



lipeifeng@oppo.com
 
From: David Hildenbrand
Date: 2021-04-22 17:29
To: Vlastimil Babka; lipeifeng; peifengl55; schwidefsky; heiko.carstens
CC: linux-s390; linux-kernel; linux-mm
Subject: Re: [RFC] mm: support multi_freearea to the reduction of external fragmentation
On 16.04.21 13:06, Vlastimil Babka wrote:
> On 4/14/21 4:38 AM, lipeifeng@oppo.com wrote:
>> From: lipeifeng <lipeifeng@oppo.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.
> 
 
Let's consider part 3 only and ignore the 1) multi freearea (which might 
be problematic with sparcity) and 2) the modified allocation scheme 
(which doesn't yet quite sense to me yet, e.g., because we group by 
mobility and have compaction in place; I assume this really only helps 
in some special cases -- like the test case you are giving; I might be 
wrong)
 
Right now, we decide whether to but to head or tail based on how likely 
it is that we might merge to a higher-order page (buddy_merge_likely()) 
in the future. So we only consider the current "neighborhood" of the 
page we're freeing. As we restrict our neighborhood to MAX_ORDER - 1 
pages (what we can actually merge). Of course, we can easily be wrong 
here. Grouping by movability and compaction only helps to some degree I 
guess.
 
AFAIK, what you propose is basing the decisions where to place a page 
(in addition?) on a median_pfn. Without 1) and 2) I cannot completely 
understand if 3) itself would help at all (and how to set the 
median_pfn). But it would certainly be interesting if we can tweak the 
current logic to better identify merge targets simply by tweaking 
buddy_merge_likely() or the assumptions it is making.
 
-- 
Thanks,
 
David / dhildenb
 

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