Skip to contentSkip to conversation

sched, timers: simplify calc_load and avoid cpu iteration loop

PATCH In review Thomas Gleixner 3 participants 9 messages May 14, 2009 – May 15, 2009

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

cover sched, timers: simplify calc_load and avoid cpu iteration loop

Dimitri Sivanich pointed out that calc_load iterates over all online CPUs under xtime lock which can cause long latencies on large SMP systems.

The following patch series removes the iteration loop and lets scheduler_tick() on each CPU update the number of active tasks. The calc_load() function just uses this variable and updates avenrun from do_timer().

Dimitri, can you please test run this on one of your large machines ?

Thanks,

tglx

#1 lore raw

PATCH 1/2 sched, timers: move calc_load() to scheduler

Dimitri Sivanich noticed that 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 a 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.

Instead of iterating over all online CPUs let the scheduler_tick code update the number of active tasks shortly before the avenrun update happens. The avenrun update itself is handled by the CPU which calls do_timer().

[ Impact: reduce xtime_lock write locked section ]

---
 include/linux/sched.h     |    2 -
 kernel/sched.c            |   84 ++++++++++++++++++++++++++++++++++++++++------
 kernel/sched_idletask.c   |    3 +
 kernel/time/timekeeping.c |    2 -
 kernel/timer.c            |   54 +----------------------------
 5 files changed, 80 insertions(+), 65 deletions(-)
include/linux/sched.h +1 -1
Index: linux-2.6-tip/include/linux/sched.h
===================================================================
@@ -137,9 +137,9 @@ DECLARE_PER_CPU(unsigned long, process_c
 extern int nr_processes(void);
 extern unsigned long nr_running(void);
 extern unsigned long nr_uninterruptible(void);
-extern unsigned long nr_active(void);
 extern unsigned long nr_iowait(void);
 extern u64 cpu_nr_migrations(int cpu);
+extern void calc_global_load(void);
 
 extern unsigned long get_parent_ip(unsigned long addr);
 
kernel/sched.c +74 -10

142 lines not on this page · raw message

kernel/sched_idletask.c +2 -1
Index: linux-2.6-tip/kernel/sched_idletask.c
===================================================================
@@ -22,7 +22,8 @@ static void check_preempt_curr_idle(stru
 static struct task_struct *pick_next_task_idle(struct rq *rq)
 {
 	schedstat_inc(rq, sched_goidle);
-
+	/* adjust the active tasks as we might go into a long sleep */
+	calc_load_account_active(rq);
 	return rq->idle;
 }
 
kernel/time/timekeeping.c +1 -1
Index: linux-2.6-tip/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 +2 -52

72 lines not on this page · raw message

maintainer
#2 lore raw

Re: [patch 1/2] sched, timers: move calc_load() to scheduler

Quoted 25 lines · Thomas Gleixner

plain text document attachment (move-calc-load-to-scheduler-v1.patch)

kernel/sched.c +19 -0
+/*
+ * calc_load - update the avenrun load estimates 10 ticks after the
+ * CPUs have updated calc_load_tasks.
+ */
+void calc_global_load(void)
+{
+	unsigned long upd = calc_load_update + 10;
+	long active;
+
+	if (time_before(jiffies, upd))
+		return;
 
+	active = atomic_long_read(&calc_load_tasks);
+	active = active > 0 ? active * FIXED_1 : 0;
 
+	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
+	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
+	avenrun[2] = calc_load(avenrun[2], EXP_15, active);
+
+	calc_load_update += LOAD_FREQ;
+}

kernel/sched.c static inline void update_times(unsigned · line 1165

Quoted 7 lines
kernel/sched.c +2 -1
@@ -1211,7 +1160,8 @@ static inline void update_times(unsigned
 void do_timer(unsigned long ticks)
 {
 	jiffies_64 += ticks;
-	update_times(ticks);
+	update_wall_time();
+	calc_global_load();
 }

I can see multiple cpus fall into calc_global_load() concurrently, which would 'age' the load faster than expected.

Should we plug that hole?

#3 lore raw

Re: [patch 1/2] sched, timers: move calc_load() to scheduler

Quoted 37 lines · Peter Zijlstra
Quoted 25 lines · Thomas Gleixner

plain text document attachment (move-calc-load-to-scheduler-v1.patch)

kernel/sched.c +19 -0
+/*
+ * calc_load - update the avenrun load estimates 10 ticks after the
+ * CPUs have updated calc_load_tasks.
+ */
+void calc_global_load(void)
+{
+	unsigned long upd = calc_load_update + 10;
+	long active;
+
+	if (time_before(jiffies, upd))
+		return;
 
+	active = atomic_long_read(&calc_load_tasks);
+	active = active > 0 ? active * FIXED_1 : 0;
 
+	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
+	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
+	avenrun[2] = calc_load(avenrun[2], EXP_15, active);
+
+	calc_load_update += LOAD_FREQ;
+}

kernel/sched.c static inline void update_times(unsigned · line 1165

Quoted 7 lines
kernel/sched.c +2 -1
@@ -1211,7 +1160,8 @@ static inline void update_times(unsigned
 void do_timer(unsigned long ticks)
 {
 	jiffies_64 += ticks;
-	update_times(ticks);
+	update_wall_time();
+	calc_global_load();
 }

I can see multiple cpus fall into calc_global_load() concurrently, which would 'age' the load faster than expected.

Quoted 1 line

Should we plug that hole?

They can't. do_timer() is called by exactly one CPU under xtime lock. What we removed is the loop over all online CPUs to retrieve the number of active tasks.

Thanks,

tglx

maintainer Acked-by
#4 lore raw

Re: [patch 1/2] sched, timers: move calc_load() to scheduler

Quoted 38 lines · Thomas Gleixner
Quoted 37 lines · Peter Zijlstra
Quoted 25 lines · Thomas Gleixner

plain text document attachment (move-calc-load-to-scheduler-v1.patch)

kernel/sched.c +19 -0
+/*
+ * calc_load - update the avenrun load estimates 10 ticks after the
+ * CPUs have updated calc_load_tasks.
+ */
+void calc_global_load(void)
+{
+	unsigned long upd = calc_load_update + 10;
+	long active;
+
+	if (time_before(jiffies, upd))
+		return;
 
+	active = atomic_long_read(&calc_load_tasks);
+	active = active > 0 ? active * FIXED_1 : 0;
 
+	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
+	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
+	avenrun[2] = calc_load(avenrun[2], EXP_15, active);
+
+	calc_load_update += LOAD_FREQ;
+}

kernel/sched.c static inline void update_times(unsigned · line 1165

Quoted 7 lines
kernel/sched.c +2 -1
@@ -1211,7 +1160,8 @@ static inline void update_times(unsigned
 void do_timer(unsigned long ticks)
 {
 	jiffies_64 += ticks;
-	update_times(ticks);
+	update_wall_time();
+	calc_global_load();
 }

I can see multiple cpus fall into calc_global_load() concurrently, which would 'age' the load faster than expected.

Quoted 5 lines
Quoted 1 line

Should we plug that hole?

They can't. do_timer() is called by exactly one CPU under xtime lock. What we removed is the loop over all online CPUs to retrieve the number of active tasks.

Ah, D'0h, yes.

Patches look good then.

#5 lore raw

PATCH 2/2 sched, timers: cleanup avenrun users

In reply to Thomas Gleixner

avenrun is a 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.

[ Impact: cleanup ]

---
 fs/proc/loadavg.c     |   20 +++++++-------------
 include/linux/sched.h |    1 +
 kernel/sched.c        |   15 +++++++++++++++
 kernel/timer.c        |   32 ++++++--------------------------
 4 files changed, 29 insertions(+), 39 deletions(-)
fs/proc/loadavg.c +7 -13
Index: linux-2.6-tip/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;
+	unsigned long 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));
-
-	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),
+	get_avenrun(avnrun, FIXED_1/200, 0);
+
+	seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
+		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-tip/include/linux/sched.h
===================================================================
@@ -118,6 +118,7 @@ struct bts_context;
  *    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/sched.c +15 -0
Index: linux-2.6-tip/kernel/sched.c
===================================================================
@@ -2946,6 +2946,21 @@ static unsigned long calc_load_update;
 unsigned long avenrun[3];
 EXPORT_SYMBOL(avenrun);
 
+/**
+ * get_avenrun - get the load average array
+ * @loads:	pointer to dest load array
+ * @offset:	offset to add
+ * @shift:	shift count to shift the result left
+ *
+ * These values are estimates at best, so no need for locking.
+ */
+void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
+{
+	loads[0] = (avenrun[0] + offset) << shift;
+	loads[1] = (avenrun[1] + offset) << shift;
+	loads[2] = (avenrun[2] + offset) << shift;
+}
+
 static unsigned long
 calc_load(unsigned long load, unsigned long exp, unsigned long active)
 {
kernel/timer.c +6 -26
Index: linux-2.6-tip/kernel/timer.c
===================================================================
@@ -1362,37 +1362,17 @@ int do_sysinfo(struct sysinfo *info)
 {
 	unsigned long mem_total, sav_total;
 	unsigned int mem_unit, bitcount;
-	unsigned long seq;
+	struct timespec tp;
 
 	memset(info, 0, sizeof(struct sysinfo));
 
-	do {
-		struct timespec tp;
-		seq = read_seqbegin(&xtime_lock);
-
-		/*
-		 * This is annoying.  The below is the same thing
-		 * posix_get_clock_monotonic() does, but it wants to
-		 * take the lock which we want to cover the loads stuff
-		 * too.
-		 */
-
-		getnstimeofday(&tp);
-		tp.tv_sec += wall_to_monotonic.tv_sec;
-		tp.tv_nsec += wall_to_monotonic.tv_nsec;
-		monotonic_to_bootbased(&tp);
-		if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
-			tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
-			tp.tv_sec++;
-		}
-		info->uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
+	ktime_get_ts(&tp);
+	monotonic_to_bootbased(&tp);
+	info->uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
 
-		info->loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
-		info->loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
-		info->loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
+	get_avenrun(info->loads, 0, SI_LOAD_SHIFT - FSHIFT);
 
-		info->procs = nr_threads;
-	} while (read_seqretry(&xtime_lock, seq));
+	info->procs = nr_threads;
 
 	si_meminfo(info);
 	si_swapinfo(info);
#6 lore raw
In reply to Thomas Gleixner

I ran this patchset on a 64p ia64 machine and latency-wise it looks good. I can't really speak for the loadavg calculation.

Quoted 15 lines · Thomas Gleixner

Dimitri Sivanich pointed out that calc_load iterates over all online CPUs under xtime lock which can cause long latencies on large SMP systems.

The following patch series removes the iteration loop and lets scheduler_tick() on each CPU update the number of active tasks. The calc_load() function just uses this variable and updates avenrun from do_timer().

Dimitri, can you please test run this on one of your large machines ?

Thanks,

tglx

#7 lore raw
Quoted 1 line · Dimitri Sivanich

I ran this patchset on a 64p ia64 machine and latency-wise it looks good. I can't really speak for the loadavg calculation.

I did some comparisons vs. the old implementation and it looks pretty much the same. Thanks for testing,

tglx

Acked-by on the v1 series
#8 lore raw
In reply to Thomas Gleixner
Quoted 15 lines · Thomas Gleixner

Dimitri Sivanich pointed out that calc_load iterates over all online CPUs under xtime lock which can cause long latencies on large SMP systems.

The following patch series removes the iteration loop and lets scheduler_tick() on each CPU update the number of active tasks. The calc_load() function just uses this variable and updates avenrun from do_timer().

Dimitri, can you please test run this on one of your large machines ?

Thanks,

tglx