[patch v3 0/3] percpu_counter: bug fix and enhancement

[patch v3 0/3] percpu_counter: bug fix and enhancement

[Shaohua Li]

The patch sets do two things.
1. fix bug for 32-bit system. percpu_counter uses s64 counter. Without any
locking reading s64 in 32-bit system isn't safe and can cause bad side effect.
2. improve scalability for __percpu_counter_add. In some cases, _add could
cause heavy lock contention (see patch 2 for detailed infomation and data).
The patches will remove the contention and speed up it a bit. Last post
(http://marc.info/?l=linux-kernel&m=130259547913607&w=2) simpliy uses
atomic64 for percpu_counter, but Tejun pointed out this could cause
deviation in __percpu_counter_sum.

In this impelmentation, we track _sum and _add state. When _sum starts, _add
will wait _sum to finish. This sounds scaring, since _add is fast path. But
since _sum is called rare, at most time _add doesn't need wait.

patch 1 fix s64 read bug for 32-bit system for UP
patch 2,3 fix s64 read bug for 32-bit system for MP. And it also improve the
scalability for __percpu_counter_add.

I did some benchmarks with the patches applied:
Test1:
24 CPUs do:
while {
mmap(32M);
munmap(32M);
}
Each CPU is about 7x faster to do the loop.

Test2:
One CPU does:
while {
__percpu_counter_add(+count)
__percpu_counter_add(-count)
}
the loop do 10000000 times.
in _add fast path (no locking hold):
before my patch:
real    0m0.133s
user    0m0.000s
sys     0m0.124s
after:
real    0m0.129s
user    0m0.000s
sys     0m0.120s
the difference is variation

in _add slow path (locking hold):
before my patch:
real    0m0.374s
user    0m0.000s
sys     0m0.372s
after:
real    0m0.245s
user    0m0.000s
sys     0m0.020s

Test3:
One CPU runs percpu_counter_sum, 23 CPUs run percpu_counter_add. In _add
fast path (don't hold) lock, _sum runs a little slow (about 20% slower).
In _add slow path (hold lock), _sum runs much faster (about 9x faster)

So overall my patches make percpu_counter API faster. The only exception
is _sum has a little slower in one case, but _sum is called rare, the 20%
slower doesn't matter.

Thanks,
Shaohua

[patch v3 1/3] percpu_counter: fix code for 32bit systems for UP

[Shaohua Li]

[-- Attachment #1: percpu-counter-32bits.patch --]
[-- Type: text/plain, Size: 1915 bytes --]

percpu_counter.counter is a 's64'. Accessing it in 32-bit system is racing.
we need some locking to protect it otherwise some very wrong value could be
accessed.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
---
 include/linux/percpu_counter.h |   31 +++++++++++++++++++++++--------
 1 file changed, 23 insertions(+), 8 deletions(-)

Index: linux/include/linux/percpu_counter.h
===================================================================
--- linux.orig/include/linux/percpu_counter.h	2011-05-05 10:33:12.000000000 +0800
+++ linux/include/linux/percpu_counter.h	2011-05-06 11:19:26.000000000 +0800
@@ -101,14 +101,34 @@ static inline void percpu_counter_destro
 
 static inline void percpu_counter_set(struct percpu_counter *fbc, s64 amount)
 {
+#if BITS_PER_LONG == 32
+	preempt_disable();
+	fbc->count = amount;
+	preempt_enable();
+#else
 	fbc->count = amount;
+#endif
+}
+
+static inline s64 percpu_counter_read(struct percpu_counter *fbc)
+{
+#if BITS_PER_LONG == 32
+	s64 count;
+	preempt_disable();
+	count = fbc->count;
+	preempt_enable();
+	return count;
+#else
+	return fbc->count;
+#endif
 }
 
 static inline int percpu_counter_compare(struct percpu_counter *fbc, s64 rhs)
 {
-	if (fbc->count > rhs)
+	s64 count = percpu_counter_read(fbc);
+	if (count > rhs)
 		return 1;
-	else if (fbc->count < rhs)
+	else if (count < rhs)
 		return -1;
 	else
 		return 0;
@@ -128,18 +148,13 @@ __percpu_counter_add(struct percpu_count
 	percpu_counter_add(fbc, amount);
 }
 
-static inline s64 percpu_counter_read(struct percpu_counter *fbc)
-{
-	return fbc->count;
-}
-
 /*
  * percpu_counter is intended to track positive number. In UP case, the number
  * should never be negative.
  */
 static inline s64 percpu_counter_read_positive(struct percpu_counter *fbc)
 {
-	return fbc->count;
+	return percpu_counter_read(fbc);
 }
 
 static inline s64 percpu_counter_sum_positive(struct percpu_counter *fbc)

[patch v3 2/3] percpu_counter: use atomic64 for counter in SMP

[Shaohua Li]

[-- Attachment #1: percpu-counter-atomic.patch --]
[-- Type: text/plain, Size: 5860 bytes --]

Uses atomic64 for percpu_counter, because it is cheaper than spinlock.
This doesn't slow fast path (percpu_counter_read). atomic64_read
equals to read fbc->count for 64-bit system, or equals to
spin_lock-read-spin_unlock for 32-bit system. Note, originally
the percpu_counter_read for 32-bit system doesn't hold spin_lock,
but that is buggy and might cause very wrong value accessed. This
patch fixes the issue.

We use sum_start and add_start to make sure _sum doesn't see deviation
when _add slow path is running. When _sum is running, _add will wait
_sum finish. This is scaring that _add is slow down, but actually not,
because _sum is called very rare. We could make _sum waits _add finish,
but since _add is called frequently, this will make _sum run very slow.

This can also improve some workloads with percpu_counter->lock heavily
contented. For example, vm_committed_as sometimes causes the contention.
We should tune the batch count, but if we can make percpu_counter better,
why not? In a 24 CPUs system and 24 processes, each runs:
while (1) {
	mmap(128M);
	munmap(128M);
}
we then measure how many loops each process can take:
The atomic method gives 4x faster.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
---
 include/linux/percpu_counter.h |   19 ++++-------------
 lib/percpu_counter.c           |   45 +++++++++++++++++++++++------------------
 2 files changed, 31 insertions(+), 33 deletions(-)

Index: linux/include/linux/percpu_counter.h
===================================================================
--- linux.orig/include/linux/percpu_counter.h	2011-05-13 11:13:25.000000000 +0800
+++ linux/include/linux/percpu_counter.h	2011-05-16 10:46:14.000000000 +0800
@@ -16,8 +16,8 @@
 #ifdef CONFIG_SMP
 
 struct percpu_counter {
-	spinlock_t lock;
-	s64 count;
+	atomic_t sum_start, add_start;
+	atomic64_t count;
 #ifdef CONFIG_HOTPLUG_CPU
 	struct list_head list;	/* All percpu_counters are on a list */
 #endif
@@ -26,16 +26,7 @@ struct percpu_counter {
 
 extern int percpu_counter_batch;
 
-int __percpu_counter_init(struct percpu_counter *fbc, s64 amount,
-			  struct lock_class_key *key);
-
-#define percpu_counter_init(fbc, value)					\
-	({								\
-		static struct lock_class_key __key;			\
-									\
-		__percpu_counter_init(fbc, value, &__key);		\
-	})
-
+int percpu_counter_init(struct percpu_counter *fbc, s64 amount);
 void percpu_counter_destroy(struct percpu_counter *fbc);
 void percpu_counter_set(struct percpu_counter *fbc, s64 amount);
 void __percpu_counter_add(struct percpu_counter *fbc, s64 amount, s32 batch);
@@ -60,7 +51,7 @@ static inline s64 percpu_counter_sum(str
 
 static inline s64 percpu_counter_read(struct percpu_counter *fbc)
 {
-	return fbc->count;
+	return atomic64_read(&fbc->count);
 }
 
 /*
@@ -70,7 +61,7 @@ static inline s64 percpu_counter_read(st
  */
 static inline s64 percpu_counter_read_positive(struct percpu_counter *fbc)
 {
-	s64 ret = fbc->count;
+	s64 ret = percpu_counter_read(fbc);
 
 	barrier();		/* Prevent reloads of fbc->count */
 	if (ret >= 0)
Index: linux/lib/percpu_counter.c
===================================================================
--- linux.orig/lib/percpu_counter.c	2011-05-13 10:29:04.000000000 +0800
+++ linux/lib/percpu_counter.c	2011-05-16 10:46:14.000000000 +0800
@@ -59,13 +59,11 @@ void percpu_counter_set(struct percpu_co
 {
 	int cpu;
 
-	spin_lock(&fbc->lock);
 	for_each_possible_cpu(cpu) {
 		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
 		*pcount = 0;
 	}
-	fbc->count = amount;
-	spin_unlock(&fbc->lock);
+	atomic64_set(&fbc->count, amount);
 }
 EXPORT_SYMBOL(percpu_counter_set);
 
@@ -76,10 +74,19 @@ void __percpu_counter_add(struct percpu_
 	preempt_disable();
 	count = __this_cpu_read(*fbc->counters) + amount;
 	if (count >= batch || count <= -batch) {
-		spin_lock(&fbc->lock);
-		fbc->count += count;
+		while (1) {
+			atomic_inc_return(&fbc->add_start);
+			if (atomic_read(&fbc->sum_start) == 0)
+				break;
+			atomic_dec(&fbc->add_start);
+			while (atomic_read(&fbc->sum_start) != 0)
+				cpu_relax();
+		}
+
+		atomic64_add(count, &fbc->count);
 		__this_cpu_write(*fbc->counters, 0);
-		spin_unlock(&fbc->lock);
+
+		atomic_dec(&fbc->add_start);
 	} else {
 		__this_cpu_write(*fbc->counters, count);
 	}
@@ -96,23 +103,26 @@ s64 __percpu_counter_sum(struct percpu_c
 	s64 ret;
 	int cpu;
 
-	spin_lock(&fbc->lock);
-	ret = fbc->count;
+	atomic_inc_return(&fbc->sum_start);
+	while (atomic_read(&fbc->add_start) != 0)
+		cpu_relax();
+
+	ret = atomic64_read(&fbc->count);
 	for_each_online_cpu(cpu) {
 		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
 		ret += *pcount;
 	}
-	spin_unlock(&fbc->lock);
+
+	atomic_dec(&fbc->sum_start);
 	return ret;
 }
 EXPORT_SYMBOL(__percpu_counter_sum);
 
-int __percpu_counter_init(struct percpu_counter *fbc, s64 amount,
-			  struct lock_class_key *key)
+int percpu_counter_init(struct percpu_counter *fbc, s64 amount)
 {
-	spin_lock_init(&fbc->lock);
-	lockdep_set_class(&fbc->lock, key);
-	fbc->count = amount;
+	atomic64_set(&fbc->count, amount);
+	atomic_set(&fbc->sum_start, 0);
+	atomic_set(&fbc->add_start, 0);
 	fbc->counters = alloc_percpu(s32);
 	if (!fbc->counters)
 		return -ENOMEM;
@@ -127,7 +137,7 @@ int __percpu_counter_init(struct percpu_
 #endif
 	return 0;
 }
-EXPORT_SYMBOL(__percpu_counter_init);
+EXPORT_SYMBOL(percpu_counter_init);
 
 void percpu_counter_destroy(struct percpu_counter *fbc)
 {
@@ -171,13 +181,10 @@ static int __cpuinit percpu_counter_hotc
 	mutex_lock(&percpu_counters_lock);
 	list_for_each_entry(fbc, &percpu_counters, list) {
 		s32 *pcount;
-		unsigned long flags;
 
-		spin_lock_irqsave(&fbc->lock, flags);
 		pcount = per_cpu_ptr(fbc->counters, cpu);
-		fbc->count += *pcount;
+		atomic64_add(*pcount, &fbc->count);
 		*pcount = 0;
-		spin_unlock_irqrestore(&fbc->lock, flags);
 	}
 	mutex_unlock(&percpu_counters_lock);
 #endif

[patch v3 3/3] percpu_counter: use percpu data to track add start

[Shaohua Li]

[-- Attachment #1: percpu-counter-percpustart.patch --]
[-- Type: text/plain, Size: 5253 bytes --]

add_start causes a lot of cache bouncing because it's updated by all
cpus. We can actually make it a percpu variable. This will completely
reduce the cache bouncing.
With the patch and last patch, I get about 7x faster running the
workload that last patch described. Only with last patch, the workload
is only about 4x faster.
This doesn't slow down _sum because we removed lock for _sum. I did
a stress test. 23 CPU run _add, one cpu runs _sum. In _add fast path
(don't hold) lock, _sum runs a little slow (about 20% slower). In
_add slow path (hold lock), _sum runs much faster (about 9x faster);

V2: uses one percpu data as Eric suggested.

Signed-off-by: Shaohua Li <shaohua.li@intel.com>
---
 include/linux/percpu_counter.h |   11 ++++++--
 lib/percpu_counter.c           |   51 ++++++++++++++++++++---------------------
 2 files changed, 33 insertions(+), 29 deletions(-)

Index: linux/include/linux/percpu_counter.h
===================================================================
--- linux.orig/include/linux/percpu_counter.h	2011-05-16 10:46:14.000000000 +0800
+++ linux/include/linux/percpu_counter.h	2011-05-17 14:06:23.000000000 +0800
@@ -15,13 +15,18 @@
 
 #ifdef CONFIG_SMP
 
+struct percpu_counter_data {
+	s32 counter;
+	char add_start;
+};
+
 struct percpu_counter {
-	atomic_t sum_start, add_start;
+	atomic_t sum_start;
 	atomic64_t count;
 #ifdef CONFIG_HOTPLUG_CPU
 	struct list_head list;	/* All percpu_counters are on a list */
 #endif
-	s32 __percpu *counters;
+	struct percpu_counter_data __percpu *cpu_data;
 };
 
 extern int percpu_counter_batch;
@@ -71,7 +76,7 @@ static inline s64 percpu_counter_read_po
 
 static inline int percpu_counter_initialized(struct percpu_counter *fbc)
 {
-	return (fbc->counters != NULL);
+	return (fbc->cpu_data != NULL);
 }
 
 #else
Index: linux/lib/percpu_counter.c
===================================================================
--- linux.orig/lib/percpu_counter.c	2011-05-16 10:46:14.000000000 +0800
+++ linux/lib/percpu_counter.c	2011-05-17 14:11:04.000000000 +0800
@@ -59,10 +59,8 @@ void percpu_counter_set(struct percpu_co
 {
 	int cpu;
 
-	for_each_possible_cpu(cpu) {
-		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
-		*pcount = 0;
-	}
+	for_each_possible_cpu(cpu)
+		per_cpu_ptr(fbc->cpu_data, cpu)->counter = 0;
 	atomic64_set(&fbc->count, amount);
 }
 EXPORT_SYMBOL(percpu_counter_set);
@@ -72,23 +70,25 @@ void __percpu_counter_add(struct percpu_
 	s64 count;
 
 	preempt_disable();
-	count = __this_cpu_read(*fbc->counters) + amount;
+	count = __this_cpu_ptr(fbc->cpu_data)->counter + amount;
 	if (count >= batch || count <= -batch) {
 		while (1) {
-			atomic_inc_return(&fbc->add_start);
+			__this_cpu_ptr(fbc->cpu_data)->add_start = 1;
+			/* Guarantee add_starts is seen by _sum */
+			smp_wmb();
 			if (atomic_read(&fbc->sum_start) == 0)
 				break;
-			atomic_dec(&fbc->add_start);
+			__this_cpu_ptr(fbc->cpu_data)->add_start = 0;
 			while (atomic_read(&fbc->sum_start) != 0)
 				cpu_relax();
 		}
 
 		atomic64_add(count, &fbc->count);
-		__this_cpu_write(*fbc->counters, 0);
+		__this_cpu_ptr(fbc->cpu_data)->counter = 0;
 
-		atomic_dec(&fbc->add_start);
+		__this_cpu_ptr(fbc->cpu_data)->add_start = 0;
 	} else {
-		__this_cpu_write(*fbc->counters, count);
+		__this_cpu_ptr(fbc->cpu_data)->counter = count;
 	}
 	preempt_enable();
 }
@@ -104,15 +104,15 @@ s64 __percpu_counter_sum(struct percpu_c
 	int cpu;
 
 	atomic_inc_return(&fbc->sum_start);
-	while (atomic_read(&fbc->add_start) != 0)
-		cpu_relax();
-
-	ret = atomic64_read(&fbc->count);
 	for_each_online_cpu(cpu) {
-		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
-		ret += *pcount;
+		while (per_cpu_ptr(fbc->cpu_data, cpu)->add_start != 0)
+			cpu_relax();
 	}
 
+	ret = atomic64_read(&fbc->count);
+	for_each_online_cpu(cpu)
+		ret += __this_cpu_ptr(fbc->cpu_data)->counter;
+
 	atomic_dec(&fbc->sum_start);
 	return ret;
 }
@@ -122,9 +122,8 @@ int percpu_counter_init(struct percpu_co
 {
 	atomic64_set(&fbc->count, amount);
 	atomic_set(&fbc->sum_start, 0);
-	atomic_set(&fbc->add_start, 0);
-	fbc->counters = alloc_percpu(s32);
-	if (!fbc->counters)
+	fbc->cpu_data = alloc_percpu(struct percpu_counter_data);
+	if (!fbc->cpu_data)
 		return -ENOMEM;
 
 	debug_percpu_counter_activate(fbc);
@@ -141,7 +140,7 @@ EXPORT_SYMBOL(percpu_counter_init);
 
 void percpu_counter_destroy(struct percpu_counter *fbc)
 {
-	if (!fbc->counters)
+	if (!fbc->cpu_data)
 		return;
 
 	debug_percpu_counter_deactivate(fbc);
@@ -151,8 +150,8 @@ void percpu_counter_destroy(struct percp
 	list_del(&fbc->list);
 	mutex_unlock(&percpu_counters_lock);
 #endif
-	free_percpu(fbc->counters);
-	fbc->counters = NULL;
+	free_percpu(fbc->cpu_data);
+	fbc->cpu_data = NULL;
 }
 EXPORT_SYMBOL(percpu_counter_destroy);
 
@@ -180,11 +179,11 @@ static int __cpuinit percpu_counter_hotc
 	cpu = (unsigned long)hcpu;
 	mutex_lock(&percpu_counters_lock);
 	list_for_each_entry(fbc, &percpu_counters, list) {
-		s32 *pcount;
+		struct percpu_counter_data *data =
+			per_cpu_ptr(fbc->cpu_data, cpu);
 
-		pcount = per_cpu_ptr(fbc->counters, cpu);
-		atomic64_add(*pcount, &fbc->count);
-		*pcount = 0;
+		atomic64_add(data->counter, &fbc->count);
+		data->counter = 0;
 	}
 	mutex_unlock(&percpu_counters_lock);
 #endif

Re: [patch v3 3/3] percpu_counter: use percpu data to track add start

[Eric Dumazet]

Le mardi 17 mai 2011 à 16:41 +0800, Shaohua Li a écrit :
> pièce jointe document texte brut (percpu-counter-percpustart.patch)
> add_start causes a lot of cache bouncing because it's updated by all
> cpus. We can actually make it a percpu variable. This will completely
> reduce the cache bouncing.
> With the patch and last patch, I get about 7x faster running the
> workload that last patch described. Only with last patch, the workload
> is only about 4x faster.
> This doesn't slow down _sum because we removed lock for _sum. I did
> a stress test. 23 CPU run _add, one cpu runs _sum. In _add fast path
> (don't hold) lock, _sum runs a little slow (about 20% slower). In
> _add slow path (hold lock), _sum runs much faster (about 9x faster);
> 
> V2: uses one percpu data as Eric suggested.

I NACK this patch very much.

Re: [patch v3 2/3] percpu_counter: use atomic64 for counter in SMP

[Eric Dumazet]

Le mardi 17 mai 2011 à 16:41 +0800, Shaohua Li a écrit :
> pièce jointe document texte brut (percpu-counter-atomic.patch)
> Uses atomic64 for percpu_counter, because it is cheaper than spinlock.
> This doesn't slow fast path (percpu_counter_read). atomic64_read
> equals to read fbc->count for 64-bit system, or equals to
> spin_lock-read-spin_unlock for 32-bit system. Note, originally
> the percpu_counter_read for 32-bit system doesn't hold spin_lock,
> but that is buggy and might cause very wrong value accessed. This
> patch fixes the issue.
> 
> We use sum_start and add_start to make sure _sum doesn't see deviation
> when _add slow path is running. When _sum is running, _add will wait
> _sum finish. This is scaring that _add is slow down, but actually not,
> because _sum is called very rare. We could make _sum waits _add finish,
> but since _add is called frequently, this will make _sum run very slow.
> 
> This can also improve some workloads with percpu_counter->lock heavily
> contented. For example, vm_committed_as sometimes causes the contention.
> We should tune the batch count, but if we can make percpu_counter better,
> why not? In a 24 CPUs system and 24 processes, each runs:
> while (1) {
> 	mmap(128M);
> 	munmap(128M);
> }
> we then measure how many loops each process can take:
> The atomic method gives 4x faster.
> 
> Signed-off-by: Shaohua Li <shaohua.li@intel.com>
> --

I NACK this patch, its not necessary, since percpu_counter doesnt
provide a precise count api anyway.

Please resubmit your original patches, without the bloat.

Thanks