: Free pages from local pcp lists under tight memory conditions

Andrew, Linus,

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

This should help fix some of the earlier failures seen with order 1 allocations.

I will send separate patches for:

1- Reducing the remote cpus pcp
2- Clean up page_alloc.c for CONFIG_HOTPLUG_CPU to use this code appropiately

(quoted diff) +18 -0

+static int
+reduce_cpu_pcp(void )
+{
+	struct zone *zone;
+	unsigned long flags;
+	unsigned int cpu = get_cpu();
+	int i, ret=0;
+
+	local_irq_save(flags);
+	for_each_zone(zone) {
+		struct per_cpu_pageset *pset;
+
+		pset = zone_pcp(zone, cpu);
+		for (i = 0; i < ARRAY_SIZE(pset->pcp); i++) {
+			struct per_cpu_pages *pcp;
+
+			pcp = &pset->pcp[i];
+			if (pcp->count == 0)

The `while' loop worries me for some reason, so I wimped out and just tried
the remote drain once.

Quoted 3 lines · Andrew Morton

The `while' loop worries me for some reason, so I wimped out and just tried
the remote drain once.

Even the `goto restart' which is in this patch worries me from a livelock POV. Perhaps we should only ever run drain_all_local_pages() once per __alloc_pages() invokation.
And perhaps we should run drain_all_local_pages() for GFP_ATOMIC or PF_MEMALLOC attempts too.

Quoted 9 lines

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

This should help fix some of the earlier failures seen with order 1 allocations.

I will send separate patches for:

1- Reducing the remote cpus pcp

This significantly duplicates the existing drain_local_pages().

+extern int drain_local_pages(void);

+static int drain_all_local_pages(void)

Quoted 1 line · Andrew Morton

+extern int drain_local_pages(void);

drain_cpu_pcps?

Quoted 3 lines · Christoph Lameter

Quoted 1 line · Andrew Morton

+extern int drain_local_pages(void);

drain_cpu_pcps?

Please no.

If there is something I _hate_ it's bad naming. And "pcps" is a totally unintelligible name.

Write it out. If a function is so trivial that you can't be bothered to write out what the name means, that function shouldn't exist at all. Conversely, if it's worth doing, it's worth writing out a name.

Quoted 11 lines · Rohit Seth

Andrew, Linus,

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

This should help fix some of the earlier failures seen with order 1 allocations.

I will send separate patches for:

Review

Quoted 6 lines

1- Reducing the remote cpus pcp
2- Clean up page_alloc.c for CONFIG_HOTPLUG_CPU to use this code appropiately

(quoted diff) +2 -0

+static int
+reduce_cpu_pcp(void )

This significantly duplicates the existing drain_local_pages().

Review

Quoted 5 lines

(quoted diff) +3 -0

+	if (order > 0) 
+		while (reduce_cpu_pcp()) {
+			if (get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags))

This forgot to assign to local variable `page'! It'll return NULL and will leak memory.

The `while' loop worries me for some reason, so I wimped out and just tried the remote drain once.

mm/page_alloc.c rebalance:

Quoted 3 lines

mm/page_alloc.c renamed from mm/page_alloc.c~mm-free-pages-from-local-pcp-lists-under-tight-memory-conditions +3 -0

+				goto got_pg;
+		}
+	/* FIXME: Add the support for reducing/draining the remote pcps.

This is easy enough to do.

We need to verify that this patch actually does something useful.

Quoted 12 lines · Andrew Morton

Quoted 11 lines · Rohit Seth

Andrew, Linus,

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

This should help fix some of the earlier failures seen with order 1 allocations.

I will send separate patches for:

Quoted 7 lines

Review

Quoted 6 lines

1- Reducing the remote cpus pcp
2- Clean up page_alloc.c for CONFIG_HOTPLUG_CPU to use this code appropiately

(quoted diff) +2 -0

+static int
+reduce_cpu_pcp(void )

This significantly duplicates the existing drain_local_pages().

Yes. The main change in this new function is I'm only freeing batch number of pages from each pcp rather than draining out all of them (even under a little memory pressure). IMO, we should be more opportunistic here in alloc_pages in moving pages back to global page pool list. Thoughts?

As said earlier, I will be cleaning up the existing drain_local_pages in next follow up patch.

Quoted 9 lines

Review

Quoted 5 lines

(quoted diff) +3 -0

+	if (order > 0)
+		while (reduce_cpu_pcp()) {
+			if (get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags))

This forgot to assign to local variable `page'! It'll return NULL and will leak memory.

My bad. Will fix it.

Quoted 3 lines

The `while' loop worries me for some reason, so I wimped out and just tried the remote drain once.

Even after direct reclaim it probably does make sense to see how minimally we can service a higher order request.

Quoted 6 lines

mm/page_alloc.c rebalance:

Quoted 3 lines

mm/page_alloc.c renamed from mm/page_alloc.c~mm-free-pages-from-local-pcp-lists-under-tight-memory-conditions +3 -0

+				goto got_pg;
+		}
+	/* FIXME: Add the support for reducing/draining the remote pcps.

This is easy enough to do.

The couple of options that I wanted to think little more were (before attempting to do this part):

1- Whether use the IPI to get the remote CPUs to free pages from pcp or do it lazily (using work_pending or such). As at this point in execution we can definitely afford to get scheduled out.

2- Do we drain the whole pcp on remote processors or again follow the stepped approach (but may be with a steeper slope).

Quoted 4 lines

We need to verify that this patch actually does something useful.

I'm working on this. Will let you know later today if I can come with some workload easily hitting this additional logic.

Quoted 1 line · Rohit Seth

I doubt you gain a whole lot by releasing them in batches. There is no way to determine if freeing a few will result in contiguous blocks or not and the overhead of been cautious will likely exceed the cost of simply refilling them on the next order-0 allocation.

Your worst case is where
the buddies you need are in different per-cpu caches.

As it's easy to refill a per-cpu cache, it would be easier, clearer and probably faster to just purge the per-cpu cache and have it refilled on the next order-0 allocation. The release-in-batch approach would only be worthwhile if you expect an order-1 allocation to be very rare.

In 005_drainpercpu.patch from the last version of the anti-defrag, I used the smp_call_function() and it did not seem to slow up the system. Certainly, by the time it was called, the system was already low on memory and trashing a bit so it just wasn't noticable.

Quoted 3 lines

2- Do we drain the whole pcp on remote processors or again follow the stepped approach (but may be with a steeper slope).

I would say do the same on the remote case as you do locally to keep things consistent.

Quoted 4 lines

Quoted 4 lines

We need to verify that this patch actually does something useful.

Quoted 3 lines

I'm working on this. Will let you know later today if I can come with some workload easily hitting this additional logic.

I found it hard to generate reliable workloads which hit these sort of situations although a fork-heavy workload with 8k stacks will put pressure on order-1 allocations. You can artifically force high order allocations using vmregress by doing something like this;

Quoted 3 lines · Mel Gorman

Quoted 1 line · Rohit Seth

Quoted 4 lines

I doubt you gain a whole lot by releasing them in batches. There is no way to determine if freeing a few will result in contiguous blocks or not and the overhead of been cautious will likely exceed the cost of simply refilling them on the next order-0 allocation.

It depends. If most of the higher order allocations are only order 1 (and may be order 2) then it is possible that we may gain in freeing in batches.

Quoted 3 lines

Your worst case is where
the buddies you need are in different per-cpu caches.

That is why we need another patch that tries to allocate physically contiguous pages in each per_cpu_pagelist.

Actually this patch used to
be there in Andrew's tree for some time (2.6.14) before couple of corner cases came up failing where order 1 allocations were unsuccessful.

Quoted 5 lines

As it's easy to refill a per-cpu cache, it would be easier, clearer and probably faster to just purge the per-cpu cache and have it refilled on the next order-0 allocation. The release-in-batch approach would only be worthwhile if you expect an order-1 allocation to be very rare.

Well, my only fear is if this shunting happens too often...

Quoted 5 lines

In 005_drainpercpu.patch from the last version of the anti-defrag, I used the smp_call_function() and it did not seem to slow up the system. Certainly, by the time it was called, the system was already low on memory and trashing a bit so it just wasn't noticable.

I agree at this point in alloaction, speed probably does not matter too much. I definitely want to first see for simple workloads how much (and how deep we have to go into deallocations) this extra logic helps.

Quoted 4 lines

Quoted 3 lines

2- Do we drain the whole pcp on remote processors or again follow the stepped approach (but may be with a steeper slope).

Quoted 3 lines

I would say do the same on the remote case as you do locally to keep things consistent.

Well, I think in bigger scope these allocations/deallocations will get automatically balanced.

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

We need to verify that this patch actually does something useful.

I'm working on this. Will let you know later today if I can come with some workload easily hitting this additional logic.

Quoted 4 lines

I found it hard to generate reliable workloads which hit these sort of situations although a fork-heavy workload with 8k stacks will put pressure on order-1 allocations. You can artifically force high order allocations using vmregress by doing something like this;

Need something more benign/stupid to kick into this logic.

Quoted 9 lines · Andrew Morton

Quoted 4 lines

We need to verify that this patch actually does something useful.

I'm working on this. Will let you know later today if I can come with some workload easily hitting this additional logic.

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

Quoted 3 lines · Rohit Seth

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

Ummm.. One controversial idea: How about removing the complete pcp subsystem? Last time we disabled pcps we saw that the effect that it had was within noise ratio on AIM7. The lru lock taken without pcp is in the local zone and thus rarely contended.

Quoted 10 lines · Christoph Lameter

Quoted 3 lines · Rohit Seth

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

Ummm.. One controversial idea: How about removing the complete pcp subsystem? Last time we disabled pcps we saw that the effect that it had was within noise ratio on AIM7. The lru lock taken without pcp is in the local zone and thus rarely contended.

Oh please stop.

This per_cpu_pagelist is one great logic that has got added in allocator. Besides providing pages without the need to acquire the zone lock, it is one single main reason the coloring effect is drastically reduced in 2.6 (over 2.4) based kernels.

Quoted 15 lines · Rohit Seth

Quoted 10 lines · Christoph Lameter

Quoted 3 lines · Rohit Seth

[PATCH]: This patch free pages (pcp->batch from each list at a time) from local pcp lists when a higher order allocation request is not able to get serviced from global free_list.

Ummm.. One controversial idea: How about removing the complete pcp subsystem? Last time we disabled pcps we saw that the effect that it had was within noise ratio on AIM7. The lru lock taken without pcp is in the local zone and thus rarely contended.

Oh please stop.

Quoted 5 lines

This per_cpu_pagelist is one great logic that has got added in allocator. Besides providing pages without the need to acquire the zone lock, it is one single main reason the coloring effect is drastically reduced in 2.6 (over 2.4) based kernels.

hm. Before it was merged in 2.5.x, the feature was very marginal from a performance POV in my testing on 4-way.

I was able to demonstrate a large (~60%?) speedup in one microbenckmark which consisted of four processes writing 16k to a file and truncating it back to zero again. That gain came from the cache warmth effect, which is the other benefit which these cpu-local pages are supposed to provide.

I don't think Martin was able to demonstrate much benefit from the lock contention reduction on 16-way NUMAQ either.

So I dithered for months and it was a marginal merge, so it's appropriate to justify the continued presence of the code.

We didn't measure for any coloring effects though. In fact, I didn't know that this feature actually provided any benefit in that area.

I thought Nick et.al came up with some of the constant values like batch size to tackle the page coloring issue specifically. In any case, I think one of the key difference between 2.4 and 2.6 allocators is the pcp list. And even with the minuscule batch and high watermarks this is helping ordinary benchmarks (by reducing the variation from run to run).

Quoted 5 lines · Rohit Seth

I thought Nick et.al came up with some of the constant values like batch size to tackle the page coloring issue specifically. In any case, I think one of the key difference between 2.4 and 2.6 allocators is the pcp list. And even with the minuscule batch and high watermarks this is helping ordinary benchmarks (by reducing the variation from run to run).

Could you share some benchmark results?

Quoted 4 lines

I don't think Martin was able to demonstrate much benefit from the lock contention reduction on 16-way NUMAQ either.

Quoted 3 lines

So I dithered for months and it was a marginal merge, so it's appropriate to justify the continued presence of the code.

May be the limits on the number of pages hanging on the per_cpu_pagelist was (or even now is) too small (for them to give any meaningful gain). May be we should have more physical contiguity in each of these pcps to give better cache spread.

Quoted 2 lines

We didn't measure for any coloring effects though. In fact, I didn't know that this feature actually provided any benefit in that area.

I thought Nick et.al came up with some of the constant values like batch size to tackle the page coloring issue specifically. In any case, I think one of the key difference between 2.4 and 2.6 allocators is the pcp list. And even with the minuscule batch and high watermarks this is helping ordinary benchmarks (by reducing the variation from run to run).

Quoted 4 lines · Rohit Seth

Quoted 4 lines

I don't think Martin was able to demonstrate much benefit from the lock contention reduction on 16-way NUMAQ either.

Quoted 8 lines

Quoted 3 lines

So I dithered for months and it was a marginal merge, so it's appropriate to justify the continued presence of the code.

May be the limits on the number of pages hanging on the per_cpu_pagelist was (or even now is) too small (for them to give any meaningful gain). May be we should have more physical contiguity in each of these pcps to give better cache spread.

Could be. The initial settings were pretty arbitrary - I assumed that someone would get in and tune them up, but nothing much happened. Perhaps we should expose the thresholds in /proc/sys/vm so they're easier to play with.

I thought Nick et.al came up with some of the constant values like batch size to tackle the page coloring issue specifically.

Quoted 2 lines · Rohit

I thought Nick et.al came up with some of the constant values like batch size to tackle the page coloring issue specifically.

I think this came about on a linux-ia64 thread started by Jack Steiner:

http://www.gelato.unsw.edu.au/archives/linux-ia64/0504/13668.html
Subject: per_cpu_pagesets degrades MPI performance
From: Jack Steiner <steiner_at_sgi.com>
Date: 2005-04-05 05:28:27

Jack reported that per_cpu_pagesets were degrading some MPI benchmarks due to adverse page coloring. Nick responded, recommending a non-power of two batch size. Jack found that this helped nicely. This thread trails off, but seems to be the origins of the 2**n-1 batch size in:

	mm/page_alloc.c:zone_batchsize()
	 * Clamp the batch to a 2^n - 1 value. Having a power ...
        batch = (1 << fls(batch + batch/2)) - 1;

I don't see here evidence that "per_cpu_pagelist is ... one single main reason the coloring effect is drastically reduced in 2.6 (over 2.4) based kernels." Rather in this case anyway a batch size not a power of two was apparently needed to keep per_cpu_pagesets from hurting performance due to page coloring affects on some workloads.

Can you please comment on the performance delta on the MPI workload because of this change in batch values.

Quoted 2 lines · Rohit

Can you please comment on the performance delta on the MPI workload because of this change in batch values.

I can't -- all I know is what I read in Jack Steiner's posts of April 5, 2005, referenced earlier in this thread.

I was able to demonstrate a large (~60%?) speedup in one microbenckmark which consisted of four processes writing 16k to a file and truncating it back to zero again. That gain came from the cache warmth effect, which is the other benefit which these cpu-local pages are supposed to provide.