linux-kernel - Re: [RFC PATCH 1/5] mm/page_alloc: always add freeing page at the tail of the buddy list

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: Windows password security audit tool. GUI, reports in PDF.

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

Date:   Wed, 26 Oct 2016 14:08:58 +0800
From:   Xishi Qiu <qiuxishi@...wei.com>
To:     Joonsoo Kim <iamjoonsoo.kim@....com>
CC:     Andrew Morton <akpm@...ux-foundation.org>,
        Johannes Weiner <hannes@...xchg.org>,
        Vlastimil Babka <vbabka@...e.cz>,
        Mel Gorman <mgorman@...hsingularity.net>, <linux-mm@...ck.org>,
        <linux-kernel@...r.kernel.org>
Subject: Re: [RFC PATCH 1/5] mm/page_alloc: always add freeing page at the
 tail of the buddy list

On 2016/10/26 13:59, Joonsoo Kim wrote:

> On Wed, Oct 26, 2016 at 01:50:37PM +0800, Xishi Qiu wrote:
>> On 2016/10/26 12:37, Joonsoo Kim wrote:
>>
>>> On Mon, Oct 17, 2016 at 05:21:54PM +0800, Xishi Qiu wrote:
>>>> On 2016/10/13 16:08, js1304@...il.com wrote:
>>>>
>>>>> From: Joonsoo Kim <iamjoonsoo.kim@....com>
>>>>>
>>>>> Currently, freeing page can stay longer in the buddy list if next higher
>>>>> order page is in the buddy list in order to help coalescence. However,
>>>>> it doesn't work for the simplest sequential free case. For example, think
>>>>> about the situation that 8 consecutive pages are freed in sequential
>>>>> order.
>>>>>
>>>>> page 0: attached at the head of order 0 list
>>>>> page 1: merged with page 0, attached at the head of order 1 list
>>>>> page 2: attached at the tail of order 0 list
>>>>> page 3: merged with page 2 and then merged with page 0, attached at
>>>>>  the head of order 2 list
>>>>> page 4: attached at the head of order 0 list
>>>>> page 5: merged with page 4, attached at the tail of order 1 list
>>>>> page 6: attached at the tail of order 0 list
>>>>> page 7: merged with page 6 and then merged with page 4. Lastly, merged
>>>>>  with page 0 and we get order 3 freepage.
>>>>>
>>>>> With excluding page 0 case, there are three cases that freeing page is
>>>>> attached at the head of buddy list in this example and if just one
>>>>> corresponding ordered allocation request comes at that moment, this page
>>>>> in being a high order page will be allocated and we would fail to make
>>>>> order-3 freepage.
>>>>>
>>>>> Allocation usually happens in sequential order and free also does. So, it
>>>>> would be important to detect such a situation and to give some chance
>>>>> to be coalesced.
>>>>>
>>>>> I think that simple and effective heuristic about this case is just
>>>>> attaching freeing page at the tail of the buddy list unconditionally.
>>>>> If freeing isn't merged during one rotation, it would be actual
>>>>> fragmentation and we don't need to care about it for coalescence.
>>>>>
>>>>
>>>> Hi Joonsoo,
>>>>
>>>> I find another two places to reduce fragmentation.
>>>>
>>>> 1)
>>>> __rmqueue_fallback
>>>> 	steal_suitable_fallback
>>>> 		move_freepages_block
>>>> 			move_freepages
>>>> 				list_move
>>>> If we steal some free pages, we will add these page at the head of start_migratetype list,
>>>> this will cause more fixed migratetype, because this pages will be allocated more easily.
>>>> So how about use list_move_tail instead of list_move?
>>>
>>> Yeah... I don't think deeply but, at a glance, it would be helpful.
>>>
>>>>
>>>> 2)
>>>> __rmqueue_fallback
>>>> 	expand
>>>> 		list_add
>>>> How about use list_add_tail instead of list_add? If add the tail, then the rest of pages
>>>> will be hard to be allocated and we can merge them again as soon as the page freed.
>>>
>>> I guess that it has no effect. When we do __rmqueue_fallback() and
>>> expand(), we don't have any freepage on this or more order. So,
>>> list_add or list_add_tail will show the same result.
>>>
>>
>> Hi Joonsoo,
>>
>> Usually this list is empty, but in the following case, the list is not empty.
>>
>> __rmqueue_fallback
>> 	steal_suitable_fallback
>> 		move_freepages_block  // move to the list of start_migratetype
>> 	expand  // split the largest order first
>> 		list_add  // add to the list of start_migratetype
> 
> In this case, stealed freepage on steal_suitable_fallback() and
> splitted freepage would come from the same pageblock. So, it doen't
> matter to use whatever list_add* function.
> 

Yes, they are from the same pageblock, stealed freepage will move to the
start_migratetype, and expand will move to the same migratetype too,
but the list may be not empty because of the stealed freepage.
So when we split the largest order, add to the tail will be allocated
less easily, right?

Thanks,
Xishi Qiu

> Thanks.
> 
> .
>