Skip to contentSkip to conversation

move calc_load to softirq

PATCH In review Thomas Gleixner 3 participants 8 messages May 2, 2009 – May 7, 2009

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover move calc_load to softirq

calc_load() calculates the load average, which is a rough estimate at best. Right now calc_load() is called from do_timer() under the xtime lock write locked and with interrupts disabled. Dimitri Sivanich noticed 55us xtime lock hold times on a 64 cpu system. He suggested to split calc_load() out of do_timer() and move it out of the xtime locked section of each caller of do_timer():
http://lkml.org/lkml/2009/4/10/318

The following patch series moves the load average calculation to the timer softirq and removes the xtime lock dependency in the generic code. This reduces also the interrupt off section of the timer interrupt.

Thanks,

tglx

#1 lore raw

PATCH 1/3 timers: use function instead of macro for calc_load

Replace the CALC_LOAD macro by a static function.

---
 include/linux/sched.h |    5 -----
 kernel/timer.c        |   29 ++++++++++++++---------------
 2 files changed, 14 insertions(+), 20 deletions(-)
include/linux/sched.h +0 -5
Index: linux-2.6/include/linux/sched.h
===================================================================
@@ -124,11 +124,6 @@ extern unsigned long avenrun[];		/* Load
 #define EXP_5		2014		/* 1/exp(5sec/5min) */
 #define EXP_15		2037		/* 1/exp(5sec/15min) */
 
-#define CALC_LOAD(load,exp,n) \
-	load *= exp; \
-	load += n*(FIXED_1-exp); \
-	load >>= FSHIFT;
-
 extern unsigned long total_forks;
 extern int nr_threads;
 DECLARE_PER_CPU(unsigned long, process_counts);
kernel/timer.c +14 -15
Index: linux-2.6/kernel/timer.c
===================================================================
@@ -1123,14 +1123,6 @@ void update_process_times(int user_tick)
 }
 
 /*
- * Nr of active tasks - counted in fixed-point numbers
- */
-static unsigned long count_active_tasks(void)
-{
-	return nr_active() * FIXED_1;
-}
-
-/*
  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
  * imply that avenrun[] is the standard name for this kind of thing.
  * Nothing else seems to be standardized: the fractional size etc
@@ -1139,25 +1131,32 @@ static unsigned long count_active_tasks(
  * Requires xtime_lock to access.
  */
 unsigned long avenrun[3];
-
 EXPORT_SYMBOL(avenrun);
 
+static unsigned long
+calc_load(unsigned long load, unsigned long exp, unsigned long active)
+{
+	load *= exp;
+	load += active * (FIXED_1 - exp);
+	return load >> FSHIFT;
+}
+
 /*
  * calc_load - given tick count, update the avenrun load estimates.
  * This is called while holding a write_lock on xtime_lock.
  */
-static inline void calc_load(unsigned long ticks)
+static void calc_global_load(unsigned long ticks)
 {
 	unsigned long active_tasks; /* fixed-point */
 	static int count = LOAD_FREQ;
 
 	count -= ticks;
 	if (unlikely(count < 0)) {
-		active_tasks = count_active_tasks();
+		active_tasks = nr_active() * FIXED_1;
 		do {
-			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
-			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
-			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
+			avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
+			avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
+			avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
 			count += LOAD_FREQ;
 		} while (count < 0);
 	}
@@ -1193,7 +1192,7 @@ void run_local_timers(void)
 static inline void update_times(unsigned long ticks)
 {
 	update_wall_time();
-	calc_load(ticks);
+	calc_global_load(ticks);
 }
 
 /*
Acked-by on v1 1/3
#2 lore raw

Re: [patch 1/3] timers: use function instead of macro for calc_load

Quoted 3 lines · Thomas Gleixner

Replace the CALC_LOAD macro by a static function.

Quoted 89 lines
---
 include/linux/sched.h |    5 -----
 kernel/timer.c        |   29 ++++++++++++++---------------
 2 files changed, 14 insertions(+), 20 deletions(-)

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

include/linux/sched.h +0 -5
@@ -124,11 +124,6 @@ extern unsigned long avenrun[];		/* Load
 #define EXP_5		2014		/* 1/exp(5sec/5min) */
 #define EXP_15		2037		/* 1/exp(5sec/15min) */
 
-#define CALC_LOAD(load,exp,n) \
-	load *= exp; \
-	load += n*(FIXED_1-exp); \
-	load >>= FSHIFT;
-
 extern unsigned long total_forks;
 extern int nr_threads;
 DECLARE_PER_CPU(unsigned long, process_counts);

Index: linux-2.6/kernel/timer.c
===================================================================

kernel/timer.c +14 -15
@@ -1123,14 +1123,6 @@ void update_process_times(int user_tick)
 }
 
 /*
- * Nr of active tasks - counted in fixed-point numbers
- */
-static unsigned long count_active_tasks(void)
-{
-	return nr_active() * FIXED_1;
-}
-
-/*
  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
  * imply that avenrun[] is the standard name for this kind of thing.
  * Nothing else seems to be standardized: the fractional size etc
@@ -1139,25 +1131,32 @@ static unsigned long count_active_tasks(
  * Requires xtime_lock to access.
  */
 unsigned long avenrun[3];
-
 EXPORT_SYMBOL(avenrun);
 
+static unsigned long
+calc_load(unsigned long load, unsigned long exp, unsigned long active)
+{
+	load *= exp;
+	load += active * (FIXED_1 - exp);
+	return load >> FSHIFT;
+}
+
 /*
  * calc_load - given tick count, update the avenrun load estimates.
  * This is called while holding a write_lock on xtime_lock.
  */
-static inline void calc_load(unsigned long ticks)
+static void calc_global_load(unsigned long ticks)
 {
 	unsigned long active_tasks; /* fixed-point */
 	static int count = LOAD_FREQ;
 
 	count -= ticks;
 	if (unlikely(count < 0)) {
-		active_tasks = count_active_tasks();
+		active_tasks = nr_active() * FIXED_1;
 		do {
-			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
-			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
-			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
+			avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
+			avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
+			avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
 			count += LOAD_FREQ;
 		} while (count < 0);
 	}
@@ -1193,7 +1192,7 @@ void run_local_timers(void)
 static inline void update_times(unsigned long ticks)
 {
 	update_wall_time();
-	calc_load(ticks);
+	calc_global_load(ticks);
 }
 
 /*
#3 lore raw

PATCH 2/3 timer: move calc_load to softirq

In reply to Thomas Gleixner

xtime_lock is held write locked across calc_load() which iterates over all online CPUs. That can cause long latencies for xtime_lock readers on large SMP systems. The load average calculation is an rough estimate anyway so there is no real need to protect the readers vs. the update. It's not a problem when the avenrun array is updated while a reader copies the values.

Move the calculation to the softirq and reduce the xtime_lock write locked section. This also reduces the interrupts off section.

Inspired by an inital patch from Dimitri Sivanich.

---
 kernel/time/timekeeping.c |    2 -
 kernel/timer.c            |   59 +++++++++++++++++++++++++++++++++-------------
 2 files changed, 44 insertions(+), 17 deletions(-)
kernel/time/timekeeping.c +1 -1
Index: linux-2.6/kernel/time/timekeeping.c
===================================================================
@@ -22,7 +22,7 @@
 
 /*
  * This read-write spinlock protects us from races in SMP while
- * playing with xtime and avenrun.
+ * playing with xtime.
  */
 __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
 
kernel/timer.c +43 -16

91 lines not on this page · raw message

#4 lore raw

Re: [patch 2/3] timer: move calc_load to softirq

Quoted 57 lines · On Sat, 02 May 2009 19:06:35 -0000 Thomas Gleixner <[email protected]> wrote:

xtime_lock is held write locked across calc_load() which iterates over all online CPUs. That can cause long latencies for xtime_lock readers on large SMP systems. The load average calculation is an rough estimate anyway so there is no real need to protect the readers vs. the update. It's not a problem when the avenrun array is updated while a reader copies the values.

Move the calculation to the softirq and reduce the xtime_lock write locked section. This also reduces the interrupts off section.

...

kernel/timer.c +22 -13
+static atomic_t avenrun_ticks;
+static DEFINE_SPINLOCK(avenrun_lock);
+static DEFINE_PER_CPU(int, avenrun_calculate);
+
 static unsigned long
 calc_load(unsigned long load, unsigned long exp, unsigned long active)
 {
@@ -1143,23 +1145,47 @@ calc_load(unsigned long load, unsigned l
 
 /*
  * calc_load - given tick count, update the avenrun load estimates.
- * This is called while holding a write_lock on xtime_lock.
  */
-static void calc_global_load(unsigned long ticks)
+static void calc_global_load(void)
 {
-	unsigned long active_tasks; /* fixed-point */
-	static int count = LOAD_FREQ;
+	unsigned long active_tasks = nr_active() * FIXED_1;
 
-	count -= ticks;
-	if (unlikely(count < 0)) {
-		active_tasks = nr_active() * FIXED_1;
-		do {
-			avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
-			avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
-			avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
-			count += LOAD_FREQ;
-		} while (count < 0);
+	avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
+	avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
+	avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
+}
+
+/*
+ * Check whether do_timer has set avenrun_calculate. The variable is
+ * cpu local so we avoid cache line bouncing of avenrun_lock and
+ * avenrun_ticks. avenrun_lock protects the avenrun calculation.
+ */
+static void check_calc_load(void)
+{
+	int ticks, *calc = &__get_cpu_var(avenrun_calculate);
+
+	if (!*calc)
+		return;

kernel/timer.c calc_load(unsigned long load, unsigned l · line 1178

Quoted 10 lines
kernel/timer.c +9 -0
+
+	spin_lock(&avenrun_lock);
+	ticks = atomic_read(&avenrun_ticks);
+	if (ticks >= LOAD_FREQ) {
+		atomic_sub(LOAD_FREQ, &avenrun_ticks);
+		calc_global_load();
 	}
+	spin_unlock(&avenrun_lock);
+	*calc = 0;
+}

I wonder if we really really need avenrun_lock. Various bits of code (eg net/sched/em_meta.c) cheerily read avenrun[] without locking.

avenrun_lock could be made static within check_calc_load().

#5 lore raw

Re: [patch 2/3] timer: move calc_load to softirq

Quoted 4 lines · Andrew Morton
Quoted 4 lines
(quoted diff) +4 -0
+	spin_lock(&avenrun_lock);
+	ticks = atomic_read(&avenrun_ticks);
+	if (ticks >= LOAD_FREQ) {
+		atomic_sub(LOAD_FREQ, &avenrun_ticks);
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +4 -0
+		calc_global_load();
 	}
+	spin_unlock(&avenrun_lock);
+	*calc = 0;
+}

I wonder if we really really need avenrun_lock. Various bits of code (eg net/sched/em_meta.c) cheerily read avenrun[] without locking.

I don't care about the reader side anyway, the lock is just there to protect the calc_load update from two cpus, but that's probably paranoia.

Though, there is a theoretical race between 2 cpus which might want to update avenrun_ticks in the NOHZ case, but thinking more about it we can just prevent this by clever usage of the atomic ops on avenrun_ticks.

Thanks,

tglx

----------->
Subject: timer: move calc_load to softirq
From: Thomas Gleixner <[email protected]>
Date: Sat, 2 May 2009 19:43:41 +0200

xtime_lock is held write locked across calc_load() which iterates over all online CPUs. That can cause long latencies for xtime_lock readers on large SMP systems. The load average calculation is an rough estimate anyway so there is no real need to protect the readers vs. the update. It's not a problem when the avenrun array is updated while a reader copies the values.

Move the calculation to the softirq and reduce the xtime_lock write locked section. This also reduces the interrupts off section.

Inspired by an inital patch from Dimitri Sivanich.

---
 kernel/time/timekeeping.c |    2 -
 kernel/timer.c            |   57 ++++++++++++++++++++++++++++++++--------------
 2 files changed, 41 insertions(+), 18 deletions(-)
kernel/time/timekeeping.c +1 -1
Index: linux-2.6/kernel/time/timekeeping.c
===================================================================
@@ -22,7 +22,7 @@
 
 /*
  * This read-write spinlock protects us from races in SMP while
- * playing with xtime and avenrun.
+ * playing with xtime.
  */
 __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
 
kernel/timer.c +40 -17

88 lines not on this page · raw message

#6 lore raw

Re: [patch 2/3] timer: move calc_load to softirq

Quoted 39 lines · Thomas Gleixner
Quoted 4 lines · Andrew Morton
Quoted 4 lines
(quoted diff) +4 -0
+	spin_lock(&avenrun_lock);
+	ticks = atomic_read(&avenrun_ticks);
+	if (ticks >= LOAD_FREQ) {
+		atomic_sub(LOAD_FREQ, &avenrun_ticks);
Quoted 8 lines

kernel/timer.c calc_load(unsigned long load, unsigned l · line 1174

Quoted 5 lines
kernel/timer.c +4 -0
+		calc_global_load();
 	}
+	spin_unlock(&avenrun_lock);
+	*calc = 0;
+}

I wonder if we really really need avenrun_lock. Various bits of code (eg net/sched/em_meta.c) cheerily read avenrun[] without locking.

I don't care about the reader side anyway, the lock is just there to protect the calc_load update from two cpus, but that's probably paranoia.

Though, there is a theoretical race between 2 cpus which might want to update avenrun_ticks in the NOHZ case, but thinking more about it we can just prevent this by clever usage of the atomic ops on avenrun_ticks.

Thanks,

tglx

----------->
Subject: timer: move calc_load to softirq
From: Thomas Gleixner <[email protected]>
Date: Sat, 2 May 2009 19:43:41 +0200

xtime_lock is held write locked across calc_load() which iterates over all online CPUs. That can cause long latencies for xtime_lock readers on large SMP systems. The load average calculation is an rough estimate anyway so there is no real need to protect the readers vs. the update. It's not a problem when the avenrun array is updated while a reader copies the values.

Quoted 6 lines

Move the calculation to the softirq and reduce the xtime_lock write locked section. This also reduces the interrupts off section.

Inspired by an inital patch from Dimitri Sivanich.

Quoted 115 lines
---
 kernel/time/timekeeping.c |    2 -
 kernel/timer.c            |   57 ++++++++++++++++++++++++++++++++--------------
 2 files changed, 41 insertions(+), 18 deletions(-)

Index: linux-2.6/kernel/time/timekeeping.c
===================================================================

kernel/time/timekeeping.c +1 -1
@@ -22,7 +22,7 @@
 
 /*
  * This read-write spinlock protects us from races in SMP while
- * playing with xtime and avenrun.
+ * playing with xtime.
  */
 __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
 

Index: linux-2.6/kernel/timer.c
===================================================================

kernel/timer.c +40 -17
@@ -1127,12 +1127,13 @@ void update_process_times(int user_tick)
  * imply that avenrun[] is the standard name for this kind of thing.
  * Nothing else seems to be standardized: the fractional size etc
  * all seem to differ on different machines.
- *
- * Requires xtime_lock to access.
  */
 unsigned long avenrun[3];
 EXPORT_SYMBOL(avenrun);
 
+static atomic_t avenrun_ticks;
+static DEFINE_PER_CPU(int, avenrun_calculate);
+
 static unsigned long
 calc_load(unsigned long load, unsigned long exp, unsigned long active)
 {
@@ -1143,23 +1144,44 @@ calc_load(unsigned long load, unsigned l
 
 /*
  * calc_load - given tick count, update the avenrun load estimates.
- * This is called while holding a write_lock on xtime_lock.
  */
-static void calc_global_load(unsigned long ticks)
+static void calc_global_load(void)
 {
-	unsigned long active_tasks; /* fixed-point */
-	static int count = LOAD_FREQ;
+	unsigned long active_tasks = nr_active() * FIXED_1;
 
-	count -= ticks;
-	if (unlikely(count < 0)) {
-		active_tasks = nr_active() * FIXED_1;
-		do {
-			avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
-			avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
-			avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
-			count += LOAD_FREQ;
-		} while (count < 0);
-	}
+	avenrun[0] = calc_load(avenrun[0], EXP_1, active_tasks);
+	avenrun[1] = calc_load(avenrun[1], EXP_5, active_tasks);
+	avenrun[2] = calc_load(avenrun[2], EXP_15, active_tasks);
+}
+
+/*
+ * Check whether do_timer has set avenrun_calculate. The variable is
+ * cpu local so we avoid cache line bouncing of avenrun_ticks.
+ */
+static void check_calc_load(void)
+{
+	int ticks, *calc = &__get_cpu_var(avenrun_calculate);
+
+	if (!*calc)
+		return;
+
+	ticks = atomic_sub_return(LOAD_FREQ, &avenrun_ticks);
+	if (ticks >= 0)
+		calc_global_load();
+	else
+		atomic_add(LOAD_FREQ, &avenrun_ticks);
+	*calc = 0;
+}
+
+/*
+ * Update avenrun_ticks and trigger the load calculation when the
+ * result is >= LOAD_FREQ.
+ */
+static void calc_load_update(unsigned long ticks)
+{
+	ticks = atomic_add_return(ticks, &avenrun_ticks);
+	if (ticks >= LOAD_FREQ)
+		__get_cpu_var(avenrun_calculate) = 1;
 }
 
 /*
@@ -1169,6 +1191,7 @@ static void run_timer_softirq(struct sof
 {
 	struct tvec_base *base = __get_cpu_var(tvec_bases);
 
+	check_calc_load();
 	hrtimer_run_pending();
 
 	if (time_after_eq(jiffies, base->timer_jiffies))
@@ -1192,7 +1215,7 @@ void run_local_timers(void)
 static inline void update_times(unsigned long ticks)
 {
 	update_wall_time();
-	calc_global_load(ticks);
+	calc_load_update(ticks);
 }
 
 /*
#7 lore raw

PATCH 3/3 tiemrs: cleanup avenrun users

In reply to Thomas Gleixner

avenrun is an rough estimate so we don't have to worry about consistency of the three avenrun values. Remove the xtime lock dependency and provide a function to scale the values. Cleanup the users.

---
 fs/proc/loadavg.c     |   16 +++++-----------
 include/linux/sched.h |    1 +
 kernel/timer.c        |   47 +++++++++++++++++++++--------------------------
 3 files changed, 27 insertions(+), 37 deletions(-)
fs/proc/loadavg.c +5 -11
Index: linux-2.6/fs/proc/loadavg.c
===================================================================
@@ -12,20 +12,14 @@
 
 static int loadavg_proc_show(struct seq_file *m, void *v)
 {
-	int a, b, c;
-	unsigned long seq;
+	int avnrun[3];
 
-	do {
-		seq = read_seqbegin(&xtime_lock);
-		a = avenrun[0] + (FIXED_1/200);
-		b = avenrun[1] + (FIXED_1/200);
-		c = avenrun[2] + (FIXED_1/200);
-	} while (read_seqretry(&xtime_lock, seq));
+	get_avenrun(avnrun, FIXED_1/200, 0);
 
 	seq_printf(m, "%d.%02d %d.%02d %d.%02d %ld/%d %d\n",
-		LOAD_INT(a), LOAD_FRAC(a),
-		LOAD_INT(b), LOAD_FRAC(b),
-		LOAD_INT(c), LOAD_FRAC(c),
+		LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
+		LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
+		LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
 		nr_running(), nr_threads,
 		task_active_pid_ns(current)->last_pid);
 	return 0;
include/linux/sched.h +1 -0
Index: linux-2.6/include/linux/sched.h
===================================================================
@@ -116,6 +116,7 @@ struct fs_struct;
  *    11 bit fractions.
  */
 extern unsigned long avenrun[];		/* Load averages */
+extern void get_avenrun(unsigned long *loads, unsigned long offset, int shift);
 
 #define FSHIFT		11		/* nr of bits of precision */
 #define FIXED_1		(1<<FSHIFT)	/* 1.0 as fixed-point */
kernel/timer.c +21 -26

64 lines not on this page · raw message