linux-kernel - Re: [PATCH 4/5] mm: have order > 0 compaction start near a pageblock with free 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] [day] [month] [year] [list]

Message-ID: <50520156.4010508@redhat.com>
Date:	Thu, 13 Sep 2012 11:52:54 -0400
From:	Rik van Riel <riel@...hat.com>
To:	Mel Gorman <mgorman@...e.de>
CC:	Andrew Morton <akpm@...ux-foundation.org>,
	Minchan Kim <minchan@...nel.org>,
	Jim Schutt <jaschut@...dia.gov>, Linux-MM <linux-mm@...ck.org>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 4/5] mm: have order > 0 compaction start near a pageblock
 with free pages

On 08/14/2012 12:41 PM, Mel Gorman wrote:
> commit [7db8889a: mm: have order > 0 compaction start off where it left]
> introduced a caching mechanism to reduce the amount work the free page
> scanner does in compaction. However, it has a problem. Consider two process
> simultaneously scanning free pages
>
> 				    			C
> Process A		M     S     			F
> 		|---------------------------------------|
> Process B		M 	FS
>
> C is zone->compact_cached_free_pfn
> S is cc->start_pfree_pfn
> M is cc->migrate_pfn
> F is cc->free_pfn

> There is not an obvious way around this problem without introducing new
> locking and state so this patch takes a different approach.

... actually, unless I am mistaken there may be a simple
approach to keep my "skip ahead" logic but make it proof
against the above scenario.

> First, it gets rid of the skip logic because it's not clear that it matters
> if two free scanners happen to be in the same block

It is not so much about being in the same block, as it is
about multiple invocations starting at the same block over
and over again.

> but with racing updates
> it's too easy for it to skip over blocks it should not.

If one thread stops compaction free page scanning in one
block, the next invocation will start by scanning that
block again, until it is exhausted.

We just need to make the code proof against the race you
described.

> @@ -475,17 +489,6 @@ static void isolate_freepages(struct zone *zone,
>   					pfn -= pageblock_nr_pages) {
>   		unsigned long isolated;
>
> -		/*
> -		 * Skip ahead if another thread is compacting in the area
> -		 * simultaneously. If we wrapped around, we can only skip
> -		 * ahead if zone->compact_cached_free_pfn also wrapped to
> -		 * above our starting point.
> -		 */
> -		if (cc->order > 0 && (!cc->wrapped ||
> -				      zone->compact_cached_free_pfn >
> -				      cc->start_free_pfn))
> -			pfn = min(pfn, zone->compact_cached_free_pfn);
> -
>   		if (!pfn_valid(pfn))
>   			continue;

I think the skipping logic should look something like this:

static bool compaction_may_skip(struct zone *zone,
                         struct compaction_control *cc)
{
	/* If we have not wrapped, we can only skip downwards. */
	if (!cc->wrapped && zone->compact_cached_free_pfn < cc->start_free_pfn)
		return true;

	/* If we have wrapped, we can skip ahead to our start point. */
	if (cc->wrapped && zone->compact_cached_free_pfn > cc->start_free_pfn)
		return true;

	return false;
}

		if (cc->order > 0 && compaction_may_skip(zone, cc))
			pfn = min(pfn, zone->compact_cached_free_pfn);


I believe that would close the hole you described, while
not re-introducing the quadratic "start at the same block
every invocation, until we wrap" behaviour.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/