Skip to contentSkip to conversation

Better local_t implementation needed

DISCUSSION Andi Kleen 5 participants 11 messages Apr 20, 2007 – Apr 21, 2007

Subsystems (3)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

Right now local_t falls back to atomic.h on a lot of architectures:

% grep generic include/asm*/local.h include/asm-arm/local.h:#include <asm-generic/local.h> include/asm-arm26/local.h:#include <asm-generic/local.h> include/asm-avr32/local.h:#include <asm-generic/local.h> include/asm-cris/local.h:#include <asm-generic/local.h> include/asm-frv/local.h:#include <asm-generic/local.h> include/asm-h8300/local.h:#include <asm-generic/local.h> include/asm-m32r/local.h:#include <asm-generic/local.h> include/asm-m68k/local.h:#include <asm-generic/local.h> include/asm-m68knommu/local.h:#include <asm-generic/local.h> include/asm-powerpc/local.h:#include <asm-generic/local.h> include/asm-s390/local.h:#include <asm-generic/local.h> include/asm-sh/local.h:#include <asm-generic/local.h> include/asm-sh64/local.h:#include <asm-generic/local.h> include/asm-sparc/local.h:#include <asm-generic/local.h> include/asm-v850/local.h:#include <asm-generic/local.h> include/asm-xtensa/local.h:#include <asm-generic/local.h>

and asm-generic.h/local.h falls back to atomic_t

This is unfortunate because if one wants to use local_t for per CPU counters it will be a full atomic operation which is probably slow at least on all architectures that support MP.
Using local_t for per cpu counters is nice because then one can use cpu_local_add() etc. and that generates very good code at least on x86 and a few other architectures. That would then allow very cheap per CPU statistics, which are useful in a number of subsystems (like networking or MM code)

e.g. on x86 with some of the pending per cpu patches we could in the end implement cpu_local_add as a single non atomic instruction. This would compare very favourably to the complicated
code sequences that right now are generated for some of the statistics counters.

There used to be a portable implementation of local.h that instead defines local_t as a two value array indexed by in_interrupt(). I'm considering to add that back.

Drawback will be larger code.

Architectures that have cheap atomic_t can just use the atomic_t fallback. That should be all architectures that are not MP capable?

If you have cheap save_flags/cli/restore_flags that could be also used.

Or some other architecture specific implementation. For example x86 which has atomic on a CPU read/modify/write instructions can just use those.

I would urge you that if it's easy to do a better local_t to implement it.

Comments?

-Andi

#1 lore raw
Quoted 3 lines · Andi Kleen

This is unfortunate because if one wants to use local_t for per CPU counters it will be a full atomic operation which is probably slow at least on all architectures that support MP.

Right.

Quoted 5 lines

Using local_t for per cpu counters is nice because then one can use cpu_local_add() etc. and that generates very good code at least on x86 and a few other architectures. That would then allow very cheap per CPU statistics, which are useful in a number of subsystems (like networking or MM code)

Is the per cpu access fixed on x86? Last I checked it was not atomic.

i.e. inc(per_cpu_var) would

1. Calculate the per_cpu_var address by determining the processor id and then the address.

2. Increment that address.

This would mean that preemption needs to be disabled otherwise we can get into trouble between 1 and 2.

What should be happening is that per_cpu_var does not require the use of processor id but simply increments an address. Thus no preemption problems and less code.

I vaguely recall that there were issues with a segment register and the linker?

Quoted 5 lines

e.g. on x86 with some of the pending per cpu patches we could in the end implement cpu_local_add as a single non atomic instruction. This would compare very favourably to the complicated
code sequences that right now are generated for some of the statistics counters.

Right. I'd like to see that.

Quoted 3 lines

There used to be a portable implementation of local.h that instead defines local_t as a two value array indexed by in_interrupt(). I'm considering to add that back.

Uhhh.... Yuck.

Quoted 1 line

Drawback will be larger code.

Fix the per cpu area access instead?

Quoted 1 line

Comments?

Right now local_t is in many areas to complicated to handle and generates bad code. Fixing the per cpu area acces on x86_64 etc would make some progress here. I also do not think that atomic operations are that big an issue. We are writing a cacheline in any scenario which requires exclusive owernership. That is the major cost.

author
#2 lore raw
Quoted 8 lines · On Friday 20 April 2007 18:10:32 Christoph Lameter wrote:
Quoted 6 lines

Using local_t for per cpu counters is nice because then one can use cpu_local_add() etc. and that generates very good code at least on x86 and a few other architectures. That would then allow very cheap per CPU statistics, which are useful in a number of subsystems (like networking or MM code)

Is the per cpu access fixed on x86? Last I checked it was not atomic.

With upcomming patches per cpu can be directly referenced using %fs/%gs Then cpu_local_add() etc will be a single instruction that is atomic regarding interrupts.

Quoted 5 lines

Uhhh.... Yuck.

Quoted 1 line

Drawback will be larger code.

Fix the per cpu area access instead?

That doesn't help on architectures that don't have r-m-w instructions on memory (like all RISCSs)

-Andi

#3 lore raw
Quoted 5 lines · Andi Kleen
Quoted 1 line

Is the per cpu access fixed on x86? Last I checked it was not atomic.

With upcomming patches per cpu can be directly referenced using %fs/%gs Then cpu_local_add() etc will be a single instruction that is atomic regarding interrupts.

Ahh.. Great! When is that feature going to be available? 2.6.22?

#4 lore raw
In reply to Andi Kleen
Quoted 5 lines

Using local_t for per cpu counters is nice because then one can use cpu_local_add() etc. and that generates very good code at least on x86 and a few other architectures. That would then allow very cheap per CPU statistics, which are useful in a number of subsystems (like networking or MM code)

But be warned that aggregating the per-cpu counters can be very expensive on high cpu count ia64 systems. We've had issues with /proc files that provide system counts that do this in a cache hostile way.

-Tony

author
#5 lore raw
Quoted 10 lines · Tony
Quoted 5 lines

Using local_t for per cpu counters is nice because then one can use cpu_local_add() etc. and that generates very good code at least on x86 and a few other architectures. That would then allow very cheap per CPU statistics, which are useful in a number of subsystems (like networking or MM code)

But be warned that aggregating the per-cpu counters can be very expensive on high cpu count ia64 systems. We've had issues with /proc files that provide system counts that do this in a cache hostile way.

Can you expand? What cache hostile way?

-Andi

#6 lore raw
Quoted 6 lines · Andi Kleen
Quoted 4 lines

But be warned that aggregating the per-cpu counters can be very expensive on high cpu count ia64 systems. We've had issues with /proc files that provide system counts that do this in a cache hostile way.

Can you expand? What cache hostile way?

We have fixed these issues using the ZVCs AFAIK. The event counters still have the same scheme though. They are rarely ever aggregated.

Per cpu counters should not be in arrays indexed by cpu. Because that will place counters used by multiple processors in a cache line causing false aliasing. VM event counters are indexed by event item and placed in the per cpu areas for each counter.

Here is a patch that makes the VM use local_t. Patch is good for x86_64 (exploits atomicity of inc/dec effectively if Andy has fixed the atomicity issues) but bad for IA64 since we are going from regular integer operations to atomics. I would think that the patch is not acceptable as long as cpu_local causes a regression on IA64.

include/linux/vmstat.h +6 -11
Index: linux-2.6.21-rc6/include/linux/vmstat.h
===================================================================
@@ -6,6 +6,7 @@
 #include <linux/mm.h>
 #include <linux/mmzone.h>
 #include <asm/atomic.h>
+#include <asm/local.h>
 
 #ifdef CONFIG_ZONE_DMA
 #define DMA_ZONE(xx) xx##_DMA,
@@ -51,32 +52,26 @@ enum vm_event_item { PGPGIN, PGPGOUT, PS
  * generated will simply be the increment of a global address.
  */
 
-struct vm_event_state {
-	unsigned long event[NR_VM_EVENT_ITEMS];
-};
-
-DECLARE_PER_CPU(struct vm_event_state, vm_event_states);
+DECLARE_PER_CPU(local_t, vm_event_states)[NR_VM_EVENT_ITEMS];
 
 static inline void __count_vm_event(enum vm_event_item item)
 {
-	__get_cpu_var(vm_event_states).event[item]++;
+	__cpu_local_inc(vm_event_states[item]);
 }
 
 static inline void count_vm_event(enum vm_event_item item)
 {
-	get_cpu_var(vm_event_states).event[item]++;
-	put_cpu();
+	cpu_local_inc(vm_event_states[item]);
 }
 
 static inline void __count_vm_events(enum vm_event_item item, long delta)
 {
-	__get_cpu_var(vm_event_states).event[item] += delta;
+	__cpu_local_add(delta, vm_event_states[item]);
 }
 
 static inline void count_vm_events(enum vm_event_item item, long delta)
 {
-	get_cpu_var(vm_event_states).event[item] += delta;
-	put_cpu();
+	cpu_local_add(delta, vm_event_states[item]);
 }
 
 extern void all_vm_events(unsigned long *);
mm/vmstat.c +9 -7
Index: linux-2.6.21-rc6/mm/vmstat.c
===================================================================
@@ -14,7 +14,8 @@
 #include <linux/cpu.h>
 
 #ifdef CONFIG_VM_EVENT_COUNTERS
-DEFINE_PER_CPU(struct vm_event_state, vm_event_states) = {{0}};
+DEFINE_PER_CPU(local_t, vm_event_states)[NR_VM_EVENT_ITEMS] =
+						{ LOCAL_INIT(0) };
 EXPORT_PER_CPU_SYMBOL(vm_event_states);
 
 static void sum_vm_events(unsigned long *ret, cpumask_t *cpumask)
@@ -26,7 +27,7 @@ static void sum_vm_events(unsigned long 
 
 	cpu = first_cpu(*cpumask);
 	while (cpu < NR_CPUS) {
-		struct vm_event_state *this = &per_cpu(vm_event_states, cpu);
+		local_t *this = per_cpu(vm_event_states, cpu);
 
 		cpu = next_cpu(cpu, *cpumask);
 
@@ -35,7 +36,7 @@ static void sum_vm_events(unsigned long 
 
 
 		for (i = 0; i < NR_VM_EVENT_ITEMS; i++)
-			ret[i] += this->event[i];
+			ret[i] += local_read(&this[i]);
 	}
 }
 
@@ -59,12 +60,12 @@ EXPORT_SYMBOL_GPL(all_vm_events);
  */
 void vm_events_fold_cpu(int cpu)
 {
-	struct vm_event_state *fold_state = &per_cpu(vm_event_states, cpu);
+	local_t *fold_state = per_cpu(vm_event_states, cpu);
 	int i;
 
 	for (i = 0; i < NR_VM_EVENT_ITEMS; i++) {
-		count_vm_events(i, fold_state->event[i]);
-		fold_state->event[i] = 0;
+		count_vm_events(i, local_read(&fold_state[i]));
+		local_set(&fold_state[i], 0);
 	}
 }
 #endif /* CONFIG_HOTPLUG */
@@ -586,7 +587,8 @@ static void *vmstat_start(struct seq_fil
 
 #ifdef CONFIG_VM_EVENT_COUNTERS
 	v = kmalloc(NR_VM_ZONE_STAT_ITEMS * sizeof(unsigned long)
-			+ sizeof(struct vm_event_state), GFP_KERNEL);
+			+ sizeof(local_t) * NR_VM_EVENT_ITEMS,
+			GFP_KERNEL);
 #else
 	v = kmalloc(NR_VM_ZONE_STAT_ITEMS * sizeof(unsigned long),
 			GFP_KERNEL);
#7 lore raw
In reply to Andi Kleen

Hi,

Quoted 3 lines · Andi Kleen

There used to be a portable implementation of local.h that instead defines local_t as a two value array indexed by in_interrupt(). I'm considering to add that back.

That doesn't really work in general, interrupts can interrupt other interrupts.

bye, Roman

#8 lore raw

From: Roman Zippel <[email protected]>
Date: Fri, 20 Apr 2007 23:25:04 +0200

Quoted 8 lines · Andi Kleen
Quoted 4 lines

There used to be a portable implementation of local.h that instead defines local_t as a two value array indexed by in_interrupt(). I'm considering to add that back.

That doesn't really work in general, interrupts can interrupt other interrupts.

That's correct for hardware interrupts. It will, however, work for soft interrupts and similar contexts.

#9 lore raw
Quoted 2 lines · David Miller

That's correct for hardware interrupts. It will, however, work for soft interrupts and similar contexts.

Is there really a significant gain? It seems that such logic would be more expensive than an atomic operation.

local_t is saving atomic overhead right? It does no good for cacheline contention etc. Adding another int will increase cache footprint. Another rat hole?

#10 lore raw

From: Christoph Lameter <[email protected]>
Date: Fri, 20 Apr 2007 17:25:16 -0700 (PDT)

Quoted 11 lines · David Miller
Quoted 3 lines

That's correct for hardware interrupts. It will, however, work for soft interrupts and similar contexts.

Is there really a significant gain? It seems that such logic would be more expensive than an atomic operation.

local_t is saving atomic overhead right? It does no good for cacheline contention etc. Adding another int will increase cache footprint. Another rat hole?

We've been doing it for SNMP statistics in the networking for a long time and I'm pretty sure it's better than an atomic at least on sparc64 where the atomic is 40 cycles minimum on several processors.

I really don't want to start using local_t's all over the damn place if they are implemented as atomics until they are proven to be faster which I doubt they are on sparc64 for one.