sched: Use historical load for freq governor input

Historical load maintained per task can be used to influence cpu
frequency better. For example, when a heavy demand task wakes up after
prolonged sleep, we could use the historical load information to alert
cpufreq governor about the need to raise cpu frequency. This patch
changes CPU busy statistics to be aggregation of historical task
demand. Also task's historical load (as defined by
sysctl_sched_window_stats_policy) is add to cpu's busy statistics
(rq->curr_runnable_sum) whenever it executes on a cpu.

Change-Id: I2b66136f138b147ba19083b9b044c4feb20d9b57
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
[rameezmustafa@codeaurora.org]: Port to msm-3.18]
Signed-off-by: Syed Rameez Mustafa <rameezmustafa@codeaurora.org

4 files changed, 151 insertions, 63 deletions

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 2d2a94575eaa..f9e099e741e1 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1269,7 +1269,7 @@ struct ravg {
 	 * sum_history (empty windows are ignored in sum_history).
 	 */
 	u64 mark_start;
-	u32 sum, demand, prev_window;
+	u32 sum, demand, prev_window, partial_demand;
 	u32 sum_history[RAVG_HIST_SIZE];
 };
 
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 500e948dd43a..907dcea17905 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1072,6 +1072,12 @@ void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
 		rq_clock_skip_update(rq, true);
 }
 
+#define PUT_PREV_TASK  0
+#define PICK_NEXT_TASK 1
+#define TASK_WAKE      2
+#define TASK_MIGRATE   3
+#define TASK_UPDATE    4
+
 #if defined(CONFIG_SCHED_FREQ_INPUT) || defined(CONFIG_SCHED_HMP)
 
 /* Window size (in ns) */
@@ -1128,19 +1134,28 @@ int rq_freq_margin(struct rq *rq)
  * stretch.
  */
 static inline void
-update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples)
+update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples,
+		 int update_sum, int new_window, int event)
 {
 	u32 *hist = &p->ravg.sum_history[0];
 	int ridx, widx;
 	u32 max = 0, avg, demand;
 	u64 sum = 0;
 
-	p->ravg.prev_window = runtime;
+	if (new_window)
+		p->ravg.prev_window = runtime;
 
 	/* Ignore windows where task had no activity */
-	if (!runtime)
+	if (!runtime && !update_sum)
 		return;
 
+	if (!new_window) {
+		for (ridx = 0; ridx < RAVG_HIST_SIZE - 1; ++ridx)
+			sum += hist[ridx];
+		sum += runtime;
+		goto compute_demand;
+	}
+
 	/* Push new 'runtime' value onto stack */
 	widx = RAVG_HIST_SIZE - 1;
 	ridx = widx - samples;
@@ -1166,6 +1181,7 @@ update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples)
 			dec_nr_big_small_task(rq, p);
 	}
 
+compute_demand:
 	avg = div64_u64(sum, RAVG_HIST_SIZE);
 
 	if (sysctl_sched_window_stats_policy == WINDOW_STATS_USE_RECENT)
@@ -1175,7 +1191,21 @@ update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples)
 	else
 		demand = max(avg, runtime);
 
-	p->ravg.demand = demand;
+	if (new_window)
+		p->ravg.demand = demand;
+
+	if (update_sum) {
+		rq->curr_runnable_sum -= p->ravg.partial_demand;
+		BUG_ON((int)rq->curr_runnable_sum < 0);
+	}
+
+	p->ravg.partial_demand = demand;
+
+	if (update_sum)
+		rq->curr_runnable_sum += p->ravg.partial_demand;
+
+	if (!new_window)
+		return;
 
 	if (p->on_rq) {
 		rq->cumulative_runnable_avg += p->ravg.demand;
@@ -1196,7 +1226,9 @@ static int __init set_sched_ravg_window(char *str)
 
 early_param("sched_ravg_window", set_sched_ravg_window);
 
-static inline void move_window_start(struct rq *rq, u64 wallclock)
+static inline void
+move_window_start(struct rq *rq, u64 wallclock, int update_sum,
+						 struct task_struct *p)
 {
 	s64 delta;
 	int nr_windows;
@@ -1209,7 +1241,7 @@ static inline void move_window_start(struct rq *rq, u64 wallclock)
 	nr_windows = div64_u64(delta, sched_ravg_window);
 	rq->window_start += (u64)nr_windows * (u64)sched_ravg_window;
 
-	if (nr_windows) {
+	if (is_idle_task(rq->curr)) {
 		if (nr_windows == 1)
 			rq->prev_runnable_sum = rq->curr_runnable_sum;
 		else
@@ -1237,22 +1269,21 @@ static inline u64 scale_exec_time(u64 delta, struct rq *rq)
 	return delta;
 }
 
-void update_task_ravg(struct task_struct *p, struct rq *rq,
-				 int update_sum, u64 wallclock)
+static void update_task_ravg(struct task_struct *p, struct rq *rq,
+			     int event, u64 wallclock, int *long_sleep)
 {
 	u32 window_size = sched_ravg_window;
+	int update_sum = (event == PUT_PREV_TASK || event == TASK_UPDATE);
 	int new_window;
 	u64 mark_start = p->ravg.mark_start;
 	u64 window_start;
-	u32 prev_contrib = 0;
-	u32 curr_contrib = 0;
 
 	if (sched_use_pelt || !rq->window_start)
 		return;
 
 	lockdep_assert_held(&rq->lock);
 
-	move_window_start(rq, wallclock);
+	move_window_start(rq, wallclock, update_sum, p);
 	window_start = rq->window_start;
 
 	/*
@@ -1272,7 +1303,6 @@ void update_task_ravg(struct task_struct *p, struct rq *rq,
 
 		if (window_start > mark_start) {
 			delta = window_start - mark_start;
-
 			nr_full_windows = div64_u64(delta, window_size);
 			window_start -= nr_full_windows * window_size;
 			now = window_start;
@@ -1282,42 +1312,47 @@ void update_task_ravg(struct task_struct *p, struct rq *rq,
 		if (update_sum) {
 			delta = now - mark_start;
 			delta = scale_exec_time(delta, rq);
+			BUG_ON(delta < 0);
 
 			p->ravg.sum += delta;
 			if (unlikely(p->ravg.sum > window_size))
 				p->ravg.sum = window_size;
-
-			prev_contrib = curr_contrib;
-			curr_contrib = delta;
 		}
 
+		update_history(rq, p, p->ravg.sum, 1, update_sum,
+							new_window, event);
 		if (!new_window)
 			break;
 
-		update_history(rq, p, p->ravg.sum, 1);
-
 		if (nr_full_windows) {
 			window_start += nr_full_windows * window_size;
 			if (update_sum)
 				sum = window_size;
 			sum = scale_exec_time(sum, rq);
-			update_history(rq, p, sum, nr_full_windows);
+			update_history(rq, p, sum, nr_full_windows,
+					update_sum, new_window, event);
+		}
 
-			/*
-			 * We will always shift curr_contrib into
-			 * prev_contrib when tallying the remainder in
-			 * the current window on the next loop
-			 * iteration.
-			 */
-			curr_contrib = sum;
+		if (update_sum) {
+			rq->prev_runnable_sum = rq->curr_runnable_sum;
+			rq->curr_runnable_sum = p->ravg.partial_demand;
 		}
+
 		mark_start = window_start;
 	} while (new_window);
 
-	p->ravg.mark_start = wallclock;
+	if ((event == TASK_WAKE) && (rq->window_start > p->ravg.mark_start) &&
+		(rq->window_start - p->ravg.mark_start > window_size)) {
+			if (long_sleep)
+				*long_sleep = 1;
+			rq->prev_runnable_sum += p->ravg.demand;
+			p->ravg.prev_window = p->ravg.demand;
+	}
+
+	if (event == PICK_NEXT_TASK && !p->ravg.sum)
+		rq->curr_runnable_sum += p->ravg.partial_demand;
 
-	rq->curr_runnable_sum += curr_contrib;
-	rq->prev_runnable_sum += prev_contrib;
+	p->ravg.mark_start = wallclock;
 }
 
 unsigned long __weak arch_get_cpu_efficiency(int cpu)
@@ -1348,7 +1383,21 @@ static void init_cpu_efficiency(void)
 
 static inline void mark_task_starting(struct task_struct *p)
 {
-	p->ravg.mark_start = sched_clock();
+	struct rq *rq = task_rq(p);
+	u64 wallclock = sched_clock();
+
+	if (!rq->window_start) {
+		p->ravg.partial_demand = 0;
+		p->ravg.demand = 0;
+		p->ravg.prev_window = 0;
+		p->ravg.sum = 0;
+		return;
+	}
+
+	update_task_ravg(rq->curr, rq, TASK_UPDATE, wallclock, NULL);
+	p->ravg.mark_start = wallclock;
+	rq->prev_runnable_sum += p->ravg.demand;
+	p->ravg.prev_window = p->ravg.demand;
 }
 
 static unsigned int sync_cpu;
@@ -1371,6 +1420,7 @@ static inline void set_window_start(struct rq *rq)
 		raw_spin_unlock(&rq->lock);
 		double_rq_lock(rq, sync_rq);
 		rq->window_start = cpu_rq(sync_cpu)->window_start;
+		rq->curr_runnable_sum = rq->prev_runnable_sum = 0;
 		raw_spin_unlock(&sync_rq->lock);
 	}
 
@@ -1393,7 +1443,7 @@ unsigned long sched_get_busy(int cpu)
 	 * that the window stats are current by doing an update.
 	 */
 	raw_spin_lock(&rq->lock);
-	update_task_ravg(rq->curr, rq, 1, sched_clock());
+	update_task_ravg(rq->curr, rq, TASK_UPDATE, sched_clock(), NULL);
 	raw_spin_unlock(&rq->lock);
 
 	return div64_u64(scale_task_load(rq->prev_runnable_sum, cpu),
@@ -1407,6 +1457,8 @@ void sched_set_window(u64 window_start, unsigned int window_size)
 	u64 now = get_jiffies_64();
 	int delta;
 	unsigned long flags;
+	u64 wallclock;
+	struct task_struct *g, *p;
 
 	delta = window_start - now; /* how many jiffies ahead */
 
@@ -1432,9 +1484,23 @@ void sched_set_window(u64 window_start, unsigned int window_size)
 	sched_ravg_window = window_size * TICK_NSEC;
 	set_hmp_defaults();
 
+	wallclock = sched_clock();
+
+	read_lock(&tasklist_lock);
+	do_each_thread(g, p) {
+		p->ravg.sum = p->ravg.prev_window = 0;
+	}  while_each_thread(g, p);
+	read_unlock(&tasklist_lock);
+
 	for_each_online_cpu(cpu) {
 		struct rq *rq = cpu_rq(cpu);
+
 		rq->window_start = ws;
+		rq->curr_runnable_sum = rq->prev_runnable_sum = 0;
+		if (!is_idle_task(rq->curr)) {
+			rq->curr->ravg.mark_start = wallclock;
+			rq->curr_runnable_sum += rq->curr->ravg.partial_demand;
+		}
 		fixup_nr_big_small_task(cpu);
 	}
 
@@ -1448,6 +1514,12 @@ void sched_set_window(u64 window_start, unsigned int window_size)
 
 #else	/* CONFIG_SCHED_FREQ_INPUT || CONFIG_SCHED_HMP */
 
+static inline void
+update_task_ravg(struct task_struct *p, struct rq *rq,
+			 int event, u64 wallclock, int *long_sleep)
+{
+}
+
 static inline int rq_freq_margin(struct rq *rq)
 {
 	return INT_MAX;
@@ -1730,27 +1802,42 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
 		if (p->on_rq || p->state == TASK_WAKING) {
 			struct rq *src_rq = task_rq(p);
 			struct rq *dest_rq = cpu_rq(new_cpu);
-
-			/* In the wakeup case the task has already had
-			 * its statisics updated (and the RQ is not locked). */
-			if (p->state != TASK_WAKING) {
-				p->on_rq = 0;	/* todo */
-				update_task_ravg(p, task_rq(p), 0,
-						 sched_clock());
-				p->on_rq = 1;	/* todo */
-			}
+			int old_onrq;
+			u64 wallclock;
 
 			if (p->state == TASK_WAKING)
 				double_rq_lock(src_rq, dest_rq);
 
+			wallclock = sched_clock();
+
+			update_task_ravg(task_rq(p)->curr, task_rq(p),
+					 TASK_UPDATE,
+					 wallclock, NULL);
 			update_task_ravg(dest_rq->curr, dest_rq,
-					 1, sched_clock());
+					 TASK_UPDATE, wallclock, NULL);
+
+			/* In the wakeup case the task has already had
+			 * its statisics updated (and the RQ is not locked). */
+			old_onrq = p->on_rq;
+			p->on_rq = 0;   /* todo */
+			update_task_ravg(p, task_rq(p), TASK_MIGRATE,
+					 wallclock, NULL);
+			p->on_rq = old_onrq;    /* todo */
+
+			if (p->ravg.sum) {
+				src_rq->curr_runnable_sum -=
+					p->ravg.partial_demand;
+				dest_rq->curr_runnable_sum +=
+					p->ravg.partial_demand;
+			}
 
+			if (p->ravg.prev_window) {
+				src_rq->prev_runnable_sum -= p->ravg.demand;
+				dest_rq->prev_runnable_sum += p->ravg.demand;
+			}
 
-			src_rq->curr_runnable_sum -= p->ravg.sum;
-			src_rq->prev_runnable_sum -= p->ravg.prev_window;
-			dest_rq->curr_runnable_sum += p->ravg.sum;
-			dest_rq->prev_runnable_sum += p->ravg.prev_window;
+			BUG_ON((int)src_rq->prev_runnable_sum < 0);
+			BUG_ON((int)src_rq->curr_runnable_sum < 0);
 
 			if (p->state == TASK_WAKING)
 				double_rq_unlock(src_rq, dest_rq);
@@ -1775,7 +1862,6 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
 					(void *)(long)task_cpu(p));
 		}
 #endif
-
 	}
 
 #if defined(CONFIG_SCHED_FREQ_INPUT) || defined(CONFIG_SCHED_HMP)
@@ -2410,6 +2496,10 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	unsigned long flags;
 	int cpu, src_cpu, success = 0;
 	struct rq *rq;
+#ifdef CONFIG_SMP
+	int long_sleep = 0;
+	u64 wallclock;
+#endif
 
 	/*
 	 * If we are going to wake up a thread waiting for CONDITION we
@@ -2470,7 +2560,9 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 	smp_rmb();
 
 	raw_spin_lock(&rq->lock);
-	update_task_ravg(p, rq, 0, sched_clock());
+	wallclock = sched_clock();
+	update_task_ravg(rq->curr, rq, TASK_UPDATE, wallclock, NULL);
+	update_task_ravg(p, rq, TASK_WAKE, wallclock,  &long_sleep);
 	raw_spin_unlock(&rq->lock);
 
 	p->sched_contributes_to_load = !!task_contributes_to_load(p);
@@ -2522,6 +2614,7 @@ out:
 			atomic_notifier_call_chain(&migration_notifier_head,
 					   0, (void *)&mnd);
 	}
+
 	return success;
 }
 
@@ -2536,6 +2629,7 @@ out:
 static void try_to_wake_up_local(struct task_struct *p)
 {
 	struct rq *rq = task_rq(p);
+	int long_sleep = 0;
 
 	if (rq != this_rq() || p == current) {
 		printk_deferred("%s: Failed to wakeup task %d (%s), rq = %p,"
@@ -2567,7 +2661,10 @@ static void try_to_wake_up_local(struct task_struct *p)
 	trace_sched_waking(p);
 
 	if (!task_on_rq_queued(p)) {
-		update_task_ravg(p, rq, 0, sched_clock());
+		u64 wallclock = sched_clock();
+
+		update_task_ravg(rq->curr, rq, TASK_UPDATE, wallclock, NULL);
+		update_task_ravg(p, rq, TASK_WAKE, wallclock, &long_sleep);
 		ttwu_activate(rq, p, ENQUEUE_WAKEUP);
 	}
 
@@ -2575,6 +2672,7 @@ static void try_to_wake_up_local(struct task_struct *p)
 	ttwu_stat(p, smp_processor_id(), 0);
 out:
 	raw_spin_unlock(&p->pi_lock);
+	/* Todo : Send cpufreq notifier */
 }
 
 /**
@@ -3584,7 +3682,6 @@ pick_next_task(struct rq *rq, struct task_struct *prev)
 		if (unlikely(!p))
 			p = idle_sched_class.pick_next_task(rq, prev);
 
-		update_task_ravg(p, rq, 0, sched_clock());
 		return p;
 	}
 
@@ -3594,7 +3691,6 @@ again:
 		if (p) {
 			if (unlikely(p == RETRY_TASK))
 				goto again;
-			update_task_ravg(p, rq, 0, sched_clock());
 			return p;
 		}
 	}
@@ -3647,6 +3743,7 @@ static void __sched notrace __schedule(bool preempt)
 	unsigned long *switch_count;
 	struct rq *rq;
 	int cpu;
+	u64 wallclock;
 
 	cpu = smp_processor_id();
 	rq = cpu_rq(cpu);
@@ -3707,7 +3804,10 @@ static void __sched notrace __schedule(bool preempt)
 	if (task_on_rq_queued(prev))
 		update_rq_clock(rq);
 
+	wallclock = sched_clock();
 	next = pick_next_task(rq, prev);
+	update_task_ravg(prev, rq, PUT_PREV_TASK, wallclock, NULL);
+	update_task_ravg(next, rq, PICK_NEXT_TASK, wallclock, NULL);
 	clear_tsk_need_resched(prev);
 	clear_preempt_need_resched();
 	rq->clock_skip_update = 0;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f9157f604041..b2d70a8fb44a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3230,6 +3230,7 @@ void init_new_task_load(struct task_struct *p)
 		p->ravg.sum_history[i] = sched_init_task_load_windows;
 	p->se.avg.runnable_avg_sum_scaled = sched_init_task_load_pelt;
 	p->ravg.demand = sched_init_task_load_windows;
+	p->ravg.partial_demand = sched_init_task_load_windows;
 }
 
 #else /* CONFIG_SCHED_FREQ_INPUT || CONFIG_SCHED_HMP */
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 67e3de3b460d..aa7a2c59dd60 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1375,21 +1375,8 @@ struct sched_class {
 #endif
 };
 
-#if defined(CONFIG_SCHED_FREQ_INPUT) || defined(CONFIG_SCHED_HMP)
-extern void
-update_task_ravg(struct task_struct *p, struct rq *rq,
-				 int update_sum, u64 wallclock);
-#else	/* CONFIG_SCHED_FREQ_INPUT || CONFIG_SCHED_HMP */
-static inline void
-update_task_ravg(struct task_struct *p, struct rq *rq,
-				 int update_sum, u64 wallclock)
-{
-}
-#endif	/* CONFIG_SCHED_FREQ_INPUT || CONFIG_SCHED_HMP */
-
 static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
 {
-	update_task_ravg(prev, rq, 1, sched_clock());
 	prev->sched_class->put_prev_task(rq, prev);
 }