Reduce vm_stat cacheline contention in __vm_enough_memory

Tmpfs I/O throughput testing on UV systems has shown writeback contention between multiple writer threads (even when each thread writes to a separate tmpfs mount point).

A large part of this is caused by cacheline contention reading the vm_stat array in the __vm_enough_memory check.

The attached test patch illustrates a possible avenue for improvement in this area. By locally caching the values read from vm_stat (and refreshing the values after 2 seconds), I was able to improve tmpfs writeback performance from ~300 MB/sec to ~700 MB/sec with 120 threads writing data simultaneously to files on separate tmpfs mount points (tested on 3.1.0-rc9).

Note that this patch is simply to illustrate the gains that can be made here. What I'm looking for is some guidance on an acceptable way to accomplish the task of reducing contention in this area, either by caching these values in a way similar to the attached patch, or by some other mechanism if this is unacceptable.

Quoted 5 lines

Note that this patch is simply to illustrate the gains that can be made here. What I'm looking for is some guidance on an acceptable way to accomplish the task of reducing contention in this area, either by caching these values in a way similar to the attached patch, or by some other mechanism if this is unacceptable.

Yes, the global vm_stat[] array is a problem - I'm surprised it's hung around for this long. Altering the sysctl_overcommit_memory mode will hide the problem, but that's no good.

I think we've discussed switching vm_stat[] to a contention-avoiding counter scheme. Simply using <percpu_counter.h> would be the simplest approach. They'll introduce inaccuracies but hopefully any problems from that will be minor for the global page counters.

otoh, I think we've been round this loop before and I don't recall why nothing happened.

Quoted 4 lines

I think we've discussed switching vm_stat[] to a contention-avoiding counter scheme. Simply using <percpu_counter.h> would be the simplest approach. They'll introduce inaccuracies but hopefully any problems from that will be minor for the global page counters.

We already have a contention avoiding scheme for counter updates in vmstat.c. The problem here is that vm_stat is frequently read. Updates from other cpus that fold counter updates in a deferred way into the global statistics cause cacheline eviction. The updates occur too frequent in this load.

Quoted 2 lines

otoh, I think we've been round this loop before and I don't recall why nothing happened.

The update behavior can be tuned using /proc/sys/vm/stat_interval. Increase the interval to reduce the folding into the global counter (set maybe to 10?). This will reduce contention.

The other approach is to
increase the allowed delta per zone if frequent updates occur via the overflow checks in vmstat.c. See calculate_*_threshold there.

Note that the deltas are current reduced for memory pressure situations (after recent patches by Mel). This will cause a significant increase in vm_stat cacheline contention compared to earlier kernels.

If vm_enough_memory is being heavily hit as well, it implies that this workload is mmap-intensive which is pretty inefficient in itself. I

guess it would also apply to workloads that are malloc-intensive for large buffers but I'd expect the cache line bounces to only dominate if there was little or no computation on the resulting buffers.

As a result, I wonder how realistic is this test workload and who useful fixing this problem is in general?

Quoted 9 lines · Andrew Morton

Quoted 5 lines

Note that this patch is simply to illustrate the gains that can be made here. What I'm looking for is some guidance on an acceptable way to accomplish the task of reducing contention in this area, either by caching these values in a way similar to the attached patch, or by some other mechanism if this is unacceptable.

Yes, the global vm_stat[] array is a problem - I'm surprised it's hung around for this long. Altering the sysctl_overcommit_memory mode will hide the problem, but that's no good.

The global vm_stat array is keeping the state for the zone. It would be even more expensive to calculate this at every point where we need such data.

Quoted 4 lines

I think we've discussed switching vm_stat[] to a contention-avoiding counter scheme. Simply using <percpu_counter.h> would be the simplest approach. They'll introduce inaccuracies but hopefully any problems from that will be minor for the global page counters.

We already have a contention avoiding scheme for counter updates in vmstat.c. The problem here is that vm_stat is frequently read. Updates from other cpus that fold counter updates in a deferred way into the global statistics cause cacheline eviction. The updates occur too frequent in this load.

Quoted 3 lines

otoh, I think we've been round this loop before and I don't recall why nothing happened.

The update behavior can be tuned using /proc/sys/vm/stat_interval. Increase the interval to reduce the folding into the global counter (set maybe to 10?). This will reduce contention. The other approach is to

increase the allowed delta per zone if frequent updates occur via the overflow checks in vmstat.c. See calculate_*_threshold there.

Note that the deltas are current reduced for memory pressure situations (after recent patches by Mel). This will cause a significant increase in vm_stat cacheline contention compared to earlier kernels.

Quoted 2 lines

increase the allowed delta per zone if frequent updates occur via the overflow checks in vmstat.c. See calculate_*_threshold there.

I tried changing the threshold in both directions, with slower throughput in both cases.

Quoted 5 lines · Dimitri Sivanich

Quoted 2 lines

increase the allowed delta per zone if frequent updates occur via the overflow checks in vmstat.c. See calculate_*_threshold there.

I tried changing the threshold in both directions, with slower throughput in both cases.

If that is the case check for the vm_stat cacheline being shared with another hot kernel variable variable. Maybe that causes cacheline eviction.

If there are no updates occurring for a while (due to increased deltas and/or vmstat updates) then the vm_stat cacheline should be able to stay in shared mode in multiple processors and the performance should increase.

Quoted 4 lines

If there are no updates occurring for a while (due to increased deltas and/or vmstat updates) then the vm_stat cacheline should be able to stay in shared mode in multiple processors and the performance should increase.

We could cacheline align vm_stat[]. But the thing is pretty small - we couild put each entry in its own cacheline.

Quoted 5 lines · Andrew Morton

Quoted 4 lines

If there are no updates occurring for a while (due to increased deltas and/or vmstat updates) then the vm_stat cacheline should be able to stay in shared mode in multiple processors and the performance should increase.

Quoted 2 lines

We could cacheline align vm_stat[]. But the thing is pretty small - we couild put each entry in its own cacheline.

Which in turn would increase the cache footprint of some key kernel functions (because they need multiple vm_stat entries) and cause eviction of other cachelines that then reduce overall system performance again.

Quoted 10 lines · On Thu, 13 Oct 2011 16:02:58 -0500 (CDT) Christoph Lameter <[email protected]>…

Quoted 7 lines · Andrew Morton

Quoted 4 lines

If there are no updates occurring for a while (due to increased deltas and/or vmstat updates) then the vm_stat cacheline should be able to stay in shared mode in multiple processors and the performance should increase.

We could cacheline align vm_stat[]. But the thing is pretty small - we couild put each entry in its own cacheline.

Quoted 3 lines

Which in turn would increase the cache footprint of some key kernel functions (because they need multiple vm_stat entries) and cause eviction of other cachelines that then reduce overall system performance again.

Sure, but we gain performance by not having different CPUs treading on each other when they update different vmstat fields. Sometimes one effect will win and other times the other effect will win. Some engineering is needed..

Quoted 17 lines · Andrew Morton

Quoted 13 lines · On Thu, 13 Oct 2011 16:02:58 -0500 (CDT) Christoph Lameter <[email protected]>…

Quoted 7 lines · Andrew Morton

Quoted 4 lines

If there are no updates occurring for a while (due to increased deltas and/or vmstat updates) then the vm_stat cacheline should be able to stay in shared mode in multiple processors and the performance should increase.

We could cacheline align vm_stat[]. But the thing is pretty small - we couild put each entry in its own cacheline.

Which in turn would increase the cache footprint of some key kernel functions (because they need multiple vm_stat entries) and cause eviction of other cachelines that then reduce overall system performance again.

Quoted 4 lines

Sure, but we gain performance by not having different CPUs treading on each other when they update different vmstat fields. Sometimes one effect will win and other times the other effect will win. Some engineering is needed..

I think the first step is to determine the role (if any) that false sharing may be playing in this, since that's a simpler fix (cacheline align and pad the array).

Testing on a smaller machine with 46 writer threads in parallel (my original test used 120).

Looks as though cache-aligning and padding the end of the vm_stat array results in a ~150 MB/sec speedup. This is a nice improvement for only 46 writer threads, though it's not the full ~250 MB/sec speedup I get from setting OVERCOMMIT_NEVER.

Quoted 3 lines · Dimitri Sivanich

Testing on a smaller machine with 46 writer threads in parallel (my original test used 120).

Quoted 4 lines

Looks as though cache-aligning and padding the end of the vm_stat array results in a ~150 MB/sec speedup. This is a nice improvement for only 46 writer threads, though it's not the full ~250 MB/sec speedup I get from setting OVERCOMMIT_NEVER.

Add to this the increase in the deltas for the ZVCs and change the stat interval to 10 sec?

Increasing the ZVC deltas (threshold value in calculate*threshold == 125) does -seem- to give a small speedup in this case (maybe as much as 50 MB/sec?).

Also the whole thing could be optimized by concentrating updates to the vm_stat array at one point in time. If any local per cpu differential overflows then update all the counters in the same cacheline for which we have per cpu differentials.

That will defer another acquisition of the cacheline for the next delta overflowing. After an update all the per cpu differentials would be zero.

This could be added to zone_page_state_add....

Something like this patch? (Restriction of the updates to the same cacheline missing. Just does everything and the zone_page_state may need uninlining now)

---
 include/linux/vmstat.h |   19 ++++++++++++++++---
 mm/vmstat.c            |   10 ++++------
 2 files changed, 20 insertions(+), 9 deletions(-)

Index: linux-2.6/include/linux/vmstat.h
===================================================================

include/linux/vmstat.h +16 -3

@@ -90,10 +90,23 @@ static inline void vm_events_fold_cpu(in
 extern atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
 
 static inline void zone_page_state_add(long x, struct zone *zone,
-				 enum zone_stat_item item)
+				 enum zone_stat_item item, s8 new_value)
 {
-	atomic_long_add(x, &zone->vm_stat[item]);
-	atomic_long_add(x, &vm_stat[item]);
+	enum zone_stat_item i;
+
+	for (i = 0; i < NR_VM_EVENT_ITEMS; i++) {
+		long y;
+
+		if (i == item)
+			y = this_cpu_xchg(zone->pageset->vm_stat_diff[i], new_value) + x;
+		else
+			y = this_cpu_xchg(zone->pageset->vm_stat_diff[i], 0);
+
+		if (y) {
+			atomic_long_add(y, &zone->vm_stat[item]);
+			atomic_long_add(y, &vm_stat[item]);
+		}
+	}
 }
 
 static inline unsigned long global_page_state(enum zone_stat_item item)

Index: linux-2.6/mm/vmstat.c
===================================================================

mm/vmstat.c +3 -5

@@ -221,7 +221,7 @@ void __mod_zone_page_state(struct zone *
 	t = __this_cpu_read(pcp->stat_threshold);
 
 	if (unlikely(x > t || x < -t)) {
-		zone_page_state_add(x, zone, item);
+		zone_page_state_add(x, zone, item, 0);
 		x = 0;
 	}
 	__this_cpu_write(*p, x);

@@ -262,8 +262,7 @@ void __inc_zone_state(struct zone *zone,
 	if (unlikely(v > t)) {
 		s8 overstep = t >> 1;
 
-		zone_page_state_add(v + overstep, zone, item);
-		__this_cpu_write(*p, -overstep);
+		zone_page_state_add(v + overstep, zone, item, -overstep);
 	}
 }
 

@@ -284,8 +283,7 @@ void __dec_zone_state(struct zone *zone,
 	if (unlikely(v < - t)) {
 		s8 overstep = t >> 1;
 
-		zone_page_state_add(v - overstep, zone, item);
-		__this_cpu_write(*p, overstep);
+		zone_page_state_add(v - overstep, zone, item, overstep);
 	}
 }
 

Quoted 8 lines · Christoph Lameter

Also the whole thing could be optimized by concentrating updates to the vm_stat array at one point in time. If any local per cpu differential overflows then update all the counters in the same cacheline for which we have per cpu differentials.

That will defer another acquisition of the cacheline for the next delta overflowing. After an update all the per cpu differentials would be zero.

Quoted 6 lines

This could be added to zone_page_state_add....

Something like this patch? (Restriction of the updates to the same cacheline missing. Just does everything and the zone_page_state may need uninlining now)

This patch doesn't have much, if any, effect, at least in the 46 writer thread case (NR_VM_EVENT_ITEMS-->NR_VM_ZONE_STAT_ITEMS allowed it to boot :) ). I applied this with the change to align vm_stat.

So far cache alignment of vm_data and increasing ZVC delta has the greatest effect.

Quoted 74 lines

---
 include/linux/vmstat.h |   19 ++++++++++++++++---
 mm/vmstat.c            |   10 ++++------
 2 files changed, 20 insertions(+), 9 deletions(-)

Index: linux-2.6/include/linux/vmstat.h
===================================================================

include/linux/vmstat.h +16 -3

@@ -90,10 +90,23 @@ static inline void vm_events_fold_cpu(in
 extern atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
 
 static inline void zone_page_state_add(long x, struct zone *zone,
-				 enum zone_stat_item item)
+				 enum zone_stat_item item, s8 new_value)
 {
-	atomic_long_add(x, &zone->vm_stat[item]);
-	atomic_long_add(x, &vm_stat[item]);
+	enum zone_stat_item i;
+
+	for (i = 0; i < NR_VM_EVENT_ITEMS; i++) {
+		long y;
+
+		if (i == item)
+			y = this_cpu_xchg(zone->pageset->vm_stat_diff[i], new_value) + x;
+		else
+			y = this_cpu_xchg(zone->pageset->vm_stat_diff[i], 0);
+
+		if (y) {
+			atomic_long_add(y, &zone->vm_stat[item]);
+			atomic_long_add(y, &vm_stat[item]);
+		}
+	}
 }
 
 static inline unsigned long global_page_state(enum zone_stat_item item)

Index: linux-2.6/mm/vmstat.c
===================================================================

mm/vmstat.c +3 -5

@@ -221,7 +221,7 @@ void __mod_zone_page_state(struct zone *
 	t = __this_cpu_read(pcp->stat_threshold);
 
 	if (unlikely(x > t || x < -t)) {
-		zone_page_state_add(x, zone, item);
+		zone_page_state_add(x, zone, item, 0);
 		x = 0;
 	}
 	__this_cpu_write(*p, x);

@@ -262,8 +262,7 @@ void __inc_zone_state(struct zone *zone,
 	if (unlikely(v > t)) {
 		s8 overstep = t >> 1;
 
-		zone_page_state_add(v + overstep, zone, item);
-		__this_cpu_write(*p, -overstep);
+		zone_page_state_add(v + overstep, zone, item, -overstep);
 	}
 }
 

@@ -284,8 +283,7 @@ void __dec_zone_state(struct zone *zone,
 	if (unlikely(v < - t)) {
 		s8 overstep = t >> 1;
 
-		zone_page_state_add(v - overstep, zone, item);
-		__this_cpu_write(*p, overstep);
+		zone_page_state_add(v - overstep, zone, item, overstep);
 	}
 }
 

@@ -343,7 +341,7 @@ static inline void mod_state(struct zone
 	} while (this_cpu_cmpxchg(*p, o, n) != o);
 

mm/vmstat.c static inline void mod_state(struct zone · line 347

Quoted 6 lines

mm/vmstat.c +1 -1

 	if (z)
-		zone_page_state_add(z, zone, item);
+		zone_page_state_add(z, zone, item, 0);
 }
 
 void mod_zone_page_state(struct zone *zone, enum zone_stat_item item,

After further testing, substantial increases in ZVC delta along with cache alignment of the vm_stat array bring the tmpfs writeback throughput numbers to about where they are with vm.overcommit_memory==OVERCOMMIT_NEVER. I still need to determine how high the ZVC delta needs to be to achieve this performance, but it is greater than 125.

Would it make sense to have the ZVC delta be tuneable (via /proc/sys/vm?), keeping the same default behavior as what we currently have?

If the thresholds get set higher, it could be that some values that don't normally have as big a delta may not get updated frequently enough. Should we maybe update all values everytime a threshold is hit, as the patch below was intending?

Note that having each counter in a separate cacheline does not have much, if any, effect.

Would it make sense to have the ZVC delta be tuneable (via /proc/sys/vm?), keeping the same default behavior as what we currently have?

Quoted 2 lines

Would it make sense to have the ZVC delta be tuneable (via /proc/sys/vm?), keeping the same default behavior as what we currently have?

Tunable is bad. We don't really want a "hundreds of lines magic shell script to make large systems perform". Please find a way to auto tune.

Quoted 6 lines · Andi Kleen

Quoted 2 lines

Would it make sense to have the ZVC delta be tuneable (via /proc/sys/vm?), keeping the same default behavior as what we currently have?

Tunable is bad. We don't really want a "hundreds of lines magic shell script to make large systems perform". Please find a way to auto tune.

Agreed, and I think even if we had a tunable that it would result in potentially erradic VM performance because some areas depend on "fairly accurate" ZVCs and it wouldn't be clear that you're trading other unknown VM issues that will affect your workload because you've increased the deltas. Let's try to avoid having to ask "what is your ZVC delta tunable set at?" when someone reports a bug about reclaim stopping preemptively.

That said, perhaps we need higher deltas by default and then hints in key areas in the form of sync_stats_if_delta_above(x) calls that would do zone_page_state_add() only when that kind of precision is actually needed. For public interfaces, that would be very easy to audit to see what the level of precision is when parsing the data.

For 120 threads writing in parallel (each to it's own mountpoint), the threshold needs to be on the order of 1000. At a threshold of 750, I start to see a slowdown of 50-60 MB/sec.

For 400 threads writing in parallel, the threshold needs to be on the order of 2000 (although we're off by about 40 MB/sec at that point).

The necessary deltas in these cases are quite a bit higher than the current 125 maximum (see calculate*threshold in mm/vmstat.c).

I like the idea of having certain areas triggering vm_stat sync, as long as we know what those key areas are and how often they might be called.

Quoted 10 lines · Dimitri Sivanich

For 120 threads writing in parallel (each to it's own mountpoint), the threshold needs to be on the order of 1000. At a threshold of 750, I start to see a slowdown of 50-60 MB/sec.

For 400 threads writing in parallel, the threshold needs to be on the order of 2000 (although we're off by about 40 MB/sec at that point).

The necessary deltas in these cases are quite a bit higher than the current 125 maximum (see calculate*threshold in mm/vmstat.c).

Quoted 2 lines

I like the idea of having certain areas triggering vm_stat sync, as long as we know what those key areas are and how often they might be called.

You could potentially reduce the maximum necessary by applying my earlier patch (but please reduce the counters touched to the current cacheline). That should reduce the number of updates in the global cacheline and allow you to reduce the very high deltas that you have to deal with now.

Yes, the global vm_stat[] array is a problem - I'm surprised it's hung around for this long. Altering the sysctl_overcommit_memory mode will hide the problem, but that's no good.

I think we've discussed switching vm_stat[] to a contention-avoiding counter scheme. Simply using <percpu_counter.h> would be the simplest approach. They'll introduce inaccuracies but hopefully any problems from that will be minor for the global page counters.

otoh, I think we've been round this loop before and I don't recall why nothing happened.

Yeah, we have had this discussion on vm_enough_memory before.

https://lkml.org/lkml/2011/1/26/473

The current version of per cpu counter was not really suitable because the batch size is not appropriate. I've tried to use per cpu counter with batch size adjusted in my attempt. Andrew has suggested having an elastic batch size that's proportional to the size of the central counter but I haven't gotten around to try that out.