linux-kernel - Re: [RFC PATCH 3/4] mm/compaction: optimize >0 order folio compaction by sorting source pages.

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20230912175610.GC34089@cmpxchg.org>
Date:   Tue, 12 Sep 2023 13:56:10 -0400
From:   Johannes Weiner <hannes@...xchg.org>
To:     Zi Yan <zi.yan@...t.com>
Cc:     linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        Zi Yan <ziy@...dia.com>, Ryan Roberts <ryan.roberts@....com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        "Matthew Wilcox (Oracle)" <willy@...radead.org>,
        David Hildenbrand <david@...hat.com>,
        "Yin, Fengwei" <fengwei.yin@...el.com>,
        Yu Zhao <yuzhao@...gle.com>, Vlastimil Babka <vbabka@...e.cz>,
        Baolin Wang <baolin.wang@...ux.alibaba.com>,
        Kemeng Shi <shikemeng@...weicloud.com>,
        Mel Gorman <mgorman@...hsingularity.net>,
        Rohan Puri <rohan.puri15@...il.com>,
        Mcgrof Chamberlain <mcgrof@...nel.org>,
        Adam Manzanares <a.manzanares@...sung.com>,
        John Hubbard <jhubbard@...dia.com>
Subject: Re: [RFC PATCH 3/4] mm/compaction: optimize >0 order folio
 compaction by sorting source pages.

On Tue, Sep 12, 2023 at 12:28:14PM -0400, Zi Yan wrote:
> From: Zi Yan <ziy@...dia.com>
> 
> It should maximize high order free page use and minimize free page splits.
> It might be useful before free page merging is implemented.

The premise sounds reasonable to me: start with the largest chunks in
the hope of producing the desired block size before having to piece
things together from the order-0s dribbles.

> @@ -145,6 +145,38 @@ static void sort_free_pages(struct list_head *src, struct free_list *dst)
>  	}
>  }
>  
> +static void sort_folios_by_order(struct list_head *pages)
> +{
> +	struct free_list page_list[MAX_ORDER + 1];
> +	int order;
> +	struct folio *folio, *next;
> +
> +	for (order = 0; order <= MAX_ORDER; order++) {
> +		INIT_LIST_HEAD(&page_list[order].pages);
> +		page_list[order].nr_free = 0;
> +	}
> +
> +	list_for_each_entry_safe(folio, next, pages, lru) {
> +		order = folio_order(folio);
> +
> +		if (order > MAX_ORDER)
> +			continue;
> +
> +		list_move(&folio->lru, &page_list[order].pages);
> +		page_list[order].nr_free++;
> +	}
> +
> +	for (order = MAX_ORDER; order >= 0; order--) {
> +		if (page_list[order].nr_free) {
> +
> +			list_for_each_entry_safe(folio, next,
> +						 &page_list[order].pages, lru) {
> +				list_move_tail(&folio->lru, pages);
> +			}
> +		}
> +	}
> +}
> +
>  #ifdef CONFIG_COMPACTION
>  bool PageMovable(struct page *page)
>  {
> @@ -2636,6 +2668,8 @@ compact_zone(struct compact_control *cc, struct capture_control *capc)
>  				pageblock_start_pfn(cc->migrate_pfn - 1));
>  		}
>  
> +		sort_folios_by_order(&cc->migratepages);

Would it make sense to have isolate_migratepages_block() produce a
sorted list already? By collecting into a struct free_list in there
and finishing with that `for (order = MAX...) list_add_tail()' loop.

That would save quite a bit of shuffling around. Compaction can be
hot, and is expected to get hotter with growing larger order pressure.

The contig allocator doesn't care about ordering, but it should be
possible to gate the sorting reasonably on !cc->alloc_contig.

An optimization down the line could be to skip the sorted list
assembly for the compaction case entirely, have compact_zone() work
directly on struct free_list, starting with the highest order and
checking compact_finished() in between orders.