[PATCH v2 0/6] RT Capacity Awareness Fixes & Improvements

[PATCH v2 0/6] RT Capacity Awareness Fixes & Improvements

[Qais Yousef]

Pavan, Steve and Dietmar pointed out a few issues and improvements that could
be done to the logic of RT Capacity Awareness.

This series implements them. The main issue that triggered the discussion is
the missing fallback mechanism in cpupri_find() if we are running on unfitting
CPU and no fitting CPU was found. In this case we fallback to the best
lowest_rq, which means unfitting tasks can move freely in unfitting CPUs, which
better honours the priority of the task.

This is implemented in patch 1.

The 2nd major issue is on wakeup, the logic that forces a push was incomplete.
Steve suggested using the overload flag, but Pavan pointed out this could cause
unnecessary IPIs.

Patch 5 addresses that.

The discussion on patches 1-4 seemed to have reached a consensus. Patch 5 still
needs more eyes staring at it.

Pavan, if you can provide your Reviewed-by on the patches you're happy with
that'd be appreciated. A Tested-by would be ever better :)

Discussion on v1 can be found here:

	https://lore.kernel.org/lkml/20200214163949.27850-1-qais.yousef@arm.com/

Thanks


Qais Yousef (6):
  sched/rt: cpupri_find: implement fallback mechanism for !fit case
  sched/rt: Re-instate old behavior in select_task_rq_rt
  sched/rt: Optimize cpupri_find on non-heterogenous systems
  sched/rt: allow pulling unfitting task
  sched/rt: Better manage pushing unfit tasks on wakeup
  sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

 kernel/sched/cpupri.c | 167 +++++++++++++++++++++++++++---------------
 kernel/sched/cpupri.h |   6 +-
 kernel/sched/rt.c     | 137 ++++++++++++++++++++++++++++++----
 kernel/sched/sched.h  |   3 +
 4 files changed, 237 insertions(+), 76 deletions(-)

-- 
2.17.1

[PATCH v2 1/6] sched/rt: cpupri_find: implement fallback mechanism for !fit case

[Qais Yousef]

When searching for the best lowest_mask with a fitness_fn passed, make
sure we record the lowest_level that returns a valid lowest_mask so that
we can use that as a fallback in case we fail to find a fitting CPU at
all levels.

The intention in the original patch was not to allow a down migration to
unfitting CPU. But this missed the case where we are already running on
unfitting one.

With this change now RT tasks can still move between unfitting CPUs when
they're already running on such CPU.

And as Steve suggested; to adhere to the strict priority rules of RT, if
a task is already running on a fitting CPU but due to priority it can't
run on it, allow it to downmigrate to unfitting CPU so it can run.

Reported-by: Pavan Kondeti <pkondeti@codeaurora.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
LINK: https://lore.kernel.org/lkml/20200203142712.a7yvlyo2y3le5cpn@e107158-lin/
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/cpupri.c | 157 +++++++++++++++++++++++++++---------------
 1 file changed, 101 insertions(+), 56 deletions(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index 1a2719e1350a..1bcfa1995550 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -41,6 +41,59 @@ static int convert_prio(int prio)
 	return cpupri;
 }
 
+static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
+				struct cpumask *lowest_mask, int idx)
+{
+	struct cpupri_vec *vec  = &cp->pri_to_cpu[idx];
+	int skip = 0;
+
+	if (!atomic_read(&(vec)->count))
+		skip = 1;
+	/*
+	 * When looking at the vector, we need to read the counter,
+	 * do a memory barrier, then read the mask.
+	 *
+	 * Note: This is still all racey, but we can deal with it.
+	 *  Ideally, we only want to look at masks that are set.
+	 *
+	 *  If a mask is not set, then the only thing wrong is that we
+	 *  did a little more work than necessary.
+	 *
+	 *  If we read a zero count but the mask is set, because of the
+	 *  memory barriers, that can only happen when the highest prio
+	 *  task for a run queue has left the run queue, in which case,
+	 *  it will be followed by a pull. If the task we are processing
+	 *  fails to find a proper place to go, that pull request will
+	 *  pull this task if the run queue is running at a lower
+	 *  priority.
+	 */
+	smp_rmb();
+
+	/* Need to do the rmb for every iteration */
+	if (skip)
+		return 0;
+
+	if (cpumask_any_and(p->cpus_ptr, vec->mask) >= nr_cpu_ids)
+		return 0;
+
+	if (lowest_mask) {
+		cpumask_and(lowest_mask, p->cpus_ptr, vec->mask);
+
+		/*
+		 * We have to ensure that we have at least one bit
+		 * still set in the array, since the map could have
+		 * been concurrently emptied between the first and
+		 * second reads of vec->mask.  If we hit this
+		 * condition, simply act as though we never hit this
+		 * priority level and continue on.
+		 */
+		if (cpumask_empty(lowest_mask))
+			return 0;
+	}
+
+	return 1;
+}
+
 /**
  * cpupri_find - find the best (lowest-pri) CPU in the system
  * @cp: The cpupri context
@@ -62,80 +115,72 @@ int cpupri_find(struct cpupri *cp, struct task_struct *p,
 		struct cpumask *lowest_mask,
 		bool (*fitness_fn)(struct task_struct *p, int cpu))
 {
-	int idx = 0;
 	int task_pri = convert_prio(p->prio);
+	int best_unfit_idx = -1;
+	int idx = 0, cpu;
 
 	BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);
 
 	for (idx = 0; idx < task_pri; idx++) {
-		struct cpupri_vec *vec  = &cp->pri_to_cpu[idx];
-		int skip = 0;
 
-		if (!atomic_read(&(vec)->count))
-			skip = 1;
-		/*
-		 * When looking at the vector, we need to read the counter,
-		 * do a memory barrier, then read the mask.
-		 *
-		 * Note: This is still all racey, but we can deal with it.
-		 *  Ideally, we only want to look at masks that are set.
-		 *
-		 *  If a mask is not set, then the only thing wrong is that we
-		 *  did a little more work than necessary.
-		 *
-		 *  If we read a zero count but the mask is set, because of the
-		 *  memory barriers, that can only happen when the highest prio
-		 *  task for a run queue has left the run queue, in which case,
-		 *  it will be followed by a pull. If the task we are processing
-		 *  fails to find a proper place to go, that pull request will
-		 *  pull this task if the run queue is running at a lower
-		 *  priority.
-		 */
-		smp_rmb();
-
-		/* Need to do the rmb for every iteration */
-		if (skip)
-			continue;
-
-		if (cpumask_any_and(p->cpus_ptr, vec->mask) >= nr_cpu_ids)
+		if (!__cpupri_find(cp, p, lowest_mask, idx))
 			continue;
 
-		if (lowest_mask) {
-			int cpu;
+		if (!lowest_mask || !fitness_fn)
+			return 1;
 
-			cpumask_and(lowest_mask, p->cpus_ptr, vec->mask);
+		/* Ensure the capacity of the CPUs fit the task */
+		for_each_cpu(cpu, lowest_mask) {
+			if (!fitness_fn(p, cpu))
+				cpumask_clear_cpu(cpu, lowest_mask);
+		}
 
+		/*
+		 * If no CPU at the current priority can fit the task
+		 * continue looking
+		 */
+		if (cpumask_empty(lowest_mask)) {
 			/*
-			 * We have to ensure that we have at least one bit
-			 * still set in the array, since the map could have
-			 * been concurrently emptied between the first and
-			 * second reads of vec->mask.  If we hit this
-			 * condition, simply act as though we never hit this
-			 * priority level and continue on.
+			 * Store our fallback priority in case we
+			 * didn't find a fitting CPU
 			 */
-			if (cpumask_empty(lowest_mask))
-				continue;
+			if (best_unfit_idx == -1)
+				best_unfit_idx = idx;
 
-			if (!fitness_fn)
-				return 1;
-
-			/* Ensure the capacity of the CPUs fit the task */
-			for_each_cpu(cpu, lowest_mask) {
-				if (!fitness_fn(p, cpu))
-					cpumask_clear_cpu(cpu, lowest_mask);
-			}
-
-			/*
-			 * If no CPU at the current priority can fit the task
-			 * continue looking
-			 */
-			if (cpumask_empty(lowest_mask))
-				continue;
+			continue;
 		}
 
 		return 1;
 	}
 
+	/*
+	 * If we failed to find a fitting lowest_mask, make sure we fall back
+	 * to the last known unfitting lowest_mask.
+	 *
+	 * Note that the map of the recorded idx might have changed since then,
+	 * so we must ensure to do the full dance to make sure that level still
+	 * holds a valid lowest_mask.
+	 *
+	 * As per above, the map could have been concurrently emptied while we
+	 * were busy searching for a fitting lowest_mask at the other priority
+	 * levels.
+	 *
+	 * This rule favours honouring priority over fitting the task in the
+	 * correct CPU (Capacity Awareness being the only user now).
+	 * The idea is that if a higher priority task can run, then it should
+	 * run even if this ends up being on unfitting CPU.
+	 *
+	 * The cost of this trade-off is not entirely clear and will probably
+	 * be good for some workloads and bad for others.
+	 *
+	 * The main idea here is that if some CPUs were overcommitted, we try
+	 * to spread which is what the scheduler traditionally did. Sys admins
+	 * must do proper RT planning to avoid overloading the system if they
+	 * really care.
+	 */
+	if (best_unfit_idx != -1)
+		return __cpupri_find(cp, p, lowest_mask, best_unfit_idx);
+
 	return 0;
 }
 
-- 
2.17.1

[PATCH v2 2/6] sched/rt: Re-instate old behavior in select_task_rq_rt

[Qais Yousef]

When RT Capacity Aware support was added, the logic in select_task_rq_rt
was modified to force a search for a fitting CPU if the task currently
doesn't run on one.

But if the search failed, and the search was only triggered to fulfill
the fitness request; we could end up selecting a new CPU unnecessarily.

Fix this and re-instate the original behavior by ensuring we bail out
in that case.

This behavior change only affected asymmetric systems that are using
util_clamp to implement capacity aware. None asymmetric systems weren't
affected.

Reported-by: Pavan Kondeti <pkondeti@codeaurora.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
LINK: https://lore.kernel.org/lkml/20200218041620.GD28029@codeaurora.org/
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 4043abe45459..2c3fae637cef 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1474,6 +1474,13 @@ select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
 	if (test || !rt_task_fits_capacity(p, cpu)) {
 		int target = find_lowest_rq(p);
 
+		/*
+		 * Bail out if we were forcing a migration to find a better
+		 * fitting CPU but our search failed.
+		 */
+		if (!test && !rt_task_fits_capacity(p, target))
+			goto out_unlock;
+
 		/*
 		 * Don't bother moving it if the destination CPU is
 		 * not running a lower priority task.
@@ -1482,6 +1489,8 @@ select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
 		    p->prio < cpu_rq(target)->rt.highest_prio.curr)
 			cpu = target;
 	}
+
+out_unlock:
 	rcu_read_unlock();
 
 out:
-- 
2.17.1

[PATCH v2 3/6] sched/rt: Optimize cpupri_find on non-heterogenous systems

[Qais Yousef]

By introducing a new cpupri_find_fitness() function that takes the
fitness_fn as an argument and only called when asym_system static key is
enabled.

cpupri_find() is now a wrapper function that calls cpupri_find_fitness()
passing NULL as a fitness_fn, hence disabling the logic that handles
fitness by default.

Reported-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
LINK: https://lore.kernel.org/lkml/c0772fca-0a4b-c88d-fdf2-5715fcf8447b@arm.com/
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/cpupri.c | 10 ++++++++--
 kernel/sched/cpupri.h |  6 ++++--
 kernel/sched/rt.c     | 23 +++++++++++++++++++----
 3 files changed, 31 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index 1bcfa1995550..dd3f16d1a04a 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -94,8 +94,14 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
 	return 1;
 }
 
+int cpupri_find(struct cpupri *cp, struct task_struct *p,
+		struct cpumask *lowest_mask)
+{
+	return cpupri_find_fitness(cp, p, lowest_mask, NULL);
+}
+
 /**
- * cpupri_find - find the best (lowest-pri) CPU in the system
+ * cpupri_find_fitness - find the best (lowest-pri) CPU in the system
  * @cp: The cpupri context
  * @p: The task
  * @lowest_mask: A mask to fill in with selected CPUs (or NULL)
@@ -111,7 +117,7 @@ static inline int __cpupri_find(struct cpupri *cp, struct task_struct *p,
  *
  * Return: (int)bool - CPUs were found
  */
-int cpupri_find(struct cpupri *cp, struct task_struct *p,
+int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 		struct cpumask *lowest_mask,
 		bool (*fitness_fn)(struct task_struct *p, int cpu))
 {
diff --git a/kernel/sched/cpupri.h b/kernel/sched/cpupri.h
index 32dd520db11f..efbb492bb94c 100644
--- a/kernel/sched/cpupri.h
+++ b/kernel/sched/cpupri.h
@@ -19,8 +19,10 @@ struct cpupri {
 
 #ifdef CONFIG_SMP
 int  cpupri_find(struct cpupri *cp, struct task_struct *p,
-		 struct cpumask *lowest_mask,
-		 bool (*fitness_fn)(struct task_struct *p, int cpu));
+		 struct cpumask *lowest_mask);
+int  cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
+			 struct cpumask *lowest_mask,
+			 bool (*fitness_fn)(struct task_struct *p, int cpu));
 void cpupri_set(struct cpupri *cp, int cpu, int pri);
 int  cpupri_init(struct cpupri *cp);
 void cpupri_cleanup(struct cpupri *cp);
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 2c3fae637cef..e48d7c215aee 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1504,7 +1504,7 @@ static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
 	 * let's hope p can move out.
 	 */
 	if (rq->curr->nr_cpus_allowed == 1 ||
-	    !cpupri_find(&rq->rd->cpupri, rq->curr, NULL, NULL))
+	    !cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
 		return;
 
 	/*
@@ -1512,7 +1512,7 @@ static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
 	 * see if it is pushed or pulled somewhere else.
 	 */
 	if (p->nr_cpus_allowed != 1 &&
-	    cpupri_find(&rq->rd->cpupri, p, NULL, NULL))
+	    cpupri_find(&rq->rd->cpupri, p, NULL))
 		return;
 
 	/*
@@ -1691,6 +1691,7 @@ static int find_lowest_rq(struct task_struct *task)
 	struct cpumask *lowest_mask = this_cpu_cpumask_var_ptr(local_cpu_mask);
 	int this_cpu = smp_processor_id();
 	int cpu      = task_cpu(task);
+	int ret;
 
 	/* Make sure the mask is initialized first */
 	if (unlikely(!lowest_mask))
@@ -1699,8 +1700,22 @@ static int find_lowest_rq(struct task_struct *task)
 	if (task->nr_cpus_allowed == 1)
 		return -1; /* No other targets possible */
 
-	if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask,
-			 rt_task_fits_capacity))
+	/*
+	 * If we're on asym system ensure we consider the different capacities
+	 * of the CPUs when searching for the lowest_mask.
+	 */
+	if (static_branch_unlikely(&sched_asym_cpucapacity)) {
+
+		ret = cpupri_find_fitness(&task_rq(task)->rd->cpupri,
+					  task, lowest_mask,
+					  rt_task_fits_capacity);
+	} else {
+
+		ret = cpupri_find(&task_rq(task)->rd->cpupri,
+				  task, lowest_mask);
+	}
+
+	if (!ret)
 		return -1; /* No targets found */
 
 	/*
-- 
2.17.1

[PATCH v2 4/6] sched/rt: allow pulling unfitting task

[Qais Yousef]

When implemented RT Capacity Awareness; the logic was done such that if
a task was running on a fitting CPU, then it was sticky and we would try
our best to keep it there.

But as Steve suggested, to adhere to the strict priority rules of RT
class; allow pulling an RT task to unfitting CPU to ensure it gets a
chance to run ASAP.

Suggested-by: Steven Rostedt <rostedt@goodmis.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
LINK: https://lore.kernel.org/lkml/20200203111451.0d1da58f@oasis.local.home/
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index e48d7c215aee..9ae8a9fabe8b 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1656,8 +1656,7 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
 {
 	if (!task_running(rq, p) &&
-	    cpumask_test_cpu(cpu, p->cpus_ptr) &&
-	    rt_task_fits_capacity(p, cpu))
+	    cpumask_test_cpu(cpu, p->cpus_ptr))
 		return 1;
 
 	return 0;
-- 
2.17.1

[PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Qais Yousef]

On wakeup, if a task doesn't fit the CPU it is running on (due to its
uclamp_min value), then we trigger the push mechanism to try to find a
more suitable CPU.

But the logic introduced in commit 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
was incomplete. If the rq isn't overloaded, push_rt_task() will bail out
immediately.

Steve suggested using the overloaded flag to force the push, but as
Pavan pointed out this could cause a lot of unnecessary IPIs in case of
HAVE_RT_PUSH_IPI.

To still allow pushing unfitting task ASAP, but without causing a lot of
disturbance in case this is not possible (no available CPU that is
running at a lower priority level), introduce a new rt_nr_unfitting in
struct rt_rq and use that to manage how hard we try to push an unfitting
task in push_rt_task().

If the task is pinned to a single CPU, we won't inc rt_nr_unfitting,
hence skipping the push in this case.

Also there's no need to force a push on switched_to_rt(). On the next
wakeup we should handle it which should suffice.

Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
LINK: https://lore.kernel.org/lkml/20200221080701.GF28029@codeaurora.org/
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c    | 100 +++++++++++++++++++++++++++++++++++++++----
 kernel/sched/sched.h |   3 ++
 2 files changed, 95 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 9ae8a9fabe8b..b35e49cdafcc 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -11,6 +11,7 @@ int sched_rr_timeslice = RR_TIMESLICE;
 int sysctl_sched_rr_timeslice = (MSEC_PER_SEC / HZ) * RR_TIMESLICE;
 
 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
+static bool rt_task_fits_capacity(struct task_struct *p, int cpu);
 
 struct rt_bandwidth def_rt_bandwidth;
 
@@ -313,6 +314,27 @@ static void update_rt_migration(struct rt_rq *rt_rq)
 	}
 }
 
+#ifdef CONFIG_UCLAMP_TASK
+static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
+{
+	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
+
+	if (!rt_task_fits_capacity(p, cpu))
+		rt_rq->rt_nr_unfit++;
+}
+
+static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
+{
+	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
+
+	if (!rt_task_fits_capacity(p, cpu))
+		rt_rq->rt_nr_unfit--;
+}
+#else
+static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
+static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
+#endif
+
 static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 {
 	struct task_struct *p;
@@ -324,9 +346,17 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
 
 	rt_rq->rt_nr_total++;
-	if (p->nr_cpus_allowed > 1)
+	if (p->nr_cpus_allowed > 1) {
 		rt_rq->rt_nr_migratory++;
 
+		/*
+		 * The task is dequeued and queue again on set_cpus_allowed(),
+		 * so we can't end up with a unbalanced inc/dec if
+		 * p->nr_cpus_allowed has changed.
+		 */
+		inc_rt_unfit_tasks(p, rt_rq);
+	}
+
 	update_rt_migration(rt_rq);
 }
 
@@ -341,12 +371,29 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
 
 	rt_rq->rt_nr_total--;
-	if (p->nr_cpus_allowed > 1)
+	if (p->nr_cpus_allowed > 1) {
 		rt_rq->rt_nr_migratory--;
 
+		/*
+		 * The task is dequeued and queue again on set_cpus_allowed(),
+		 * so we can't end up with a unbalanced inc/dec if
+		 * p->nr_cpus_allowed has changed.
+		 */
+		dec_rt_unfit_tasks(p, rt_rq);
+	}
+
 	update_rt_migration(rt_rq);
 }
 
+static inline int has_unfit_tasks(struct rq *rq)
+{
+#ifdef CONFIG_UCLAMP_TASK
+	return rq->rt.rt_nr_unfit;
+#else
+	return 0;
+#endif
+}
+
 static inline int has_pushable_tasks(struct rq *rq)
 {
 	return !plist_head_empty(&rq->rt.pushable_tasks);
@@ -1862,8 +1909,9 @@ static int push_rt_task(struct rq *rq)
 	struct task_struct *next_task;
 	struct rq *lowest_rq;
 	int ret = 0;
+	bool fit;
 
-	if (!rq->rt.overloaded)
+	if (!rq->rt.overloaded && !has_unfit_tasks(rq))
 		return 0;
 
 	next_task = pick_next_pushable_task(rq);
@@ -1874,12 +1922,21 @@ static int push_rt_task(struct rq *rq)
 	if (WARN_ON(next_task == rq->curr))
 		return 0;
 
+	/*
+	 * The rq could be overloaded because it has unfitting task, if that's
+	 * the case then we need to try harder to find a better fitting CPU.
+	 */
+	fit = rt_task_fits_capacity(next_task, cpu_of(rq));
+
 	/*
 	 * It's possible that the next_task slipped in of
 	 * higher priority than current. If that's the case
 	 * just reschedule current.
+	 *
+	 * Unless next_task doesn't fit in this cpu, then continue with the
+	 * attempt to push it.
 	 */
-	if (unlikely(next_task->prio < rq->curr->prio)) {
+	if (unlikely(next_task->prio < rq->curr->prio && fit)) {
 		resched_curr(rq);
 		return 0;
 	}
@@ -1922,6 +1979,35 @@ static int push_rt_task(struct rq *rq)
 		goto retry;
 	}
 
+	/*
+	 * Bail out if the task doesn't fit on either CPUs.
+	 *
+	 * Unless..
+	 *
+	 * * The rq is already overloaded, then push anyway.
+	 *
+	 * * The priority of next_task is higher than current, then we
+	 *   resched_curr(). We forced skipping this condition above if the rq
+	 *   was overloaded but the task didn't fit.
+	 */
+	if (!fit && !rt_task_fits_capacity(next_task, cpu_of(lowest_rq))) {
+
+		/*
+		 * If the system wasn't overloaded, then pretend we didn't run.
+		 */
+		if (!rq->rt.overloaded)
+			goto out_unlock;
+
+		/*
+		 * If the system is overloaded, we forced skipping this
+		 * condition, so re-evaluate it.
+		 */
+		if (unlikely(next_task->prio < rq->curr->prio)) {
+			resched_curr(rq);
+			goto out_unlock;
+		}
+	}
+
 	deactivate_task(rq, next_task, 0);
 	set_task_cpu(next_task, lowest_rq->cpu);
 	activate_task(lowest_rq, next_task, 0);
@@ -1929,6 +2015,7 @@ static int push_rt_task(struct rq *rq)
 
 	resched_curr(lowest_rq);
 
+out_unlock:
 	double_unlock_balance(rq, lowest_rq);
 
 out:
@@ -2297,10 +2384,7 @@ static void switched_to_rt(struct rq *rq, struct task_struct *p)
 	 */
 	if (task_on_rq_queued(p) && rq->curr != p) {
 #ifdef CONFIG_SMP
-		bool need_to_push = rq->rt.overloaded ||
-				    !rt_task_fits_capacity(p, cpu_of(rq));
-
-		if (p->nr_cpus_allowed > 1 && need_to_push)
+		if (p->nr_cpus_allowed > 1 && rq->rt.overloaded)
 			rt_queue_push_tasks(rq);
 #endif /* CONFIG_SMP */
 		if (p->prio < rq->curr->prio && cpu_online(cpu_of(rq)))
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 1a88dc8ad11b..7dea81ccd49a 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -603,6 +603,9 @@ struct rt_rq {
 #ifdef CONFIG_SMP
 	unsigned long		rt_nr_migratory;
 	unsigned long		rt_nr_total;
+#ifdef CONFIG_UCLAMP_TASK
+	unsigned long		rt_nr_unfit;
+#endif
 	int			overloaded;
 	struct plist_head	pushable_tasks;
 
-- 
2.17.1

[PATCH v2 6/6] sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

[Qais Yousef]

The statement

	rt_rq = &rq_of_rt_rq(rt_rq)->rt

Was just dereferencing rt_rq to get a pointer to itself. Which is a NOP.
Remove it.

Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index b35e49cdafcc..520e84993fe7 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -343,7 +343,6 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 		return;
 
 	p = rt_task_of(rt_se);
-	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
 
 	rt_rq->rt_nr_total++;
 	if (p->nr_cpus_allowed > 1) {
@@ -368,7 +367,6 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 		return;
 
 	p = rt_task_of(rt_se);
-	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
 
 	rt_rq->rt_nr_total--;
 	if (p->nr_cpus_allowed > 1) {
-- 
2.17.1

Re: [PATCH v2 6/6] sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

[Dietmar Eggemann]

On 23.02.20 19:40, Qais Yousef wrote:
> The statement
> 
> 	rt_rq = &rq_of_rt_rq(rt_rq)->rt
> 
> Was just dereferencing rt_rq to get a pointer to itself. Which is a NOP.
> Remove it.
> 
> Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> ---
>  kernel/sched/rt.c | 2 --
>  1 file changed, 2 deletions(-)
> 
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index b35e49cdafcc..520e84993fe7 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -343,7 +343,6 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>  		return;
>  
>  	p = rt_task_of(rt_se);
> -	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

IMHO, this is here to get the root rt_rq from any rt_rq (task_groups).
Looks like that e.g rt_nr_total is only maintained on root rt_rq's.

Similar to CFS' &rq_of(cfs_rq)->cfs (cfs_rq_util_change()) to get root
cfs_rq.

Not sure where CONFIG_RT_GROUP_SCHED=y is used but it's part of the rt
class implementation.

[...]

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Pavan Kondeti]

Hi Qais,

On Sun, Feb 23, 2020 at 06:40:00PM +0000, Qais Yousef wrote:
> On wakeup, if a task doesn't fit the CPU it is running on (due to its
> uclamp_min value), then we trigger the push mechanism to try to find a
> more suitable CPU.
> 
> But the logic introduced in commit 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> was incomplete. If the rq isn't overloaded, push_rt_task() will bail out
> immediately.
> 
> Steve suggested using the overloaded flag to force the push, but as
> Pavan pointed out this could cause a lot of unnecessary IPIs in case of
> HAVE_RT_PUSH_IPI.
> 
> To still allow pushing unfitting task ASAP, but without causing a lot of
> disturbance in case this is not possible (no available CPU that is
> running at a lower priority level), introduce a new rt_nr_unfitting in
> struct rt_rq and use that to manage how hard we try to push an unfitting
> task in push_rt_task().
> 

The 1-4 patches in this series are looking good to me.

At this point (after applying 4 patches), removing rt_task_fits_capacity()
check from switched_to_rt() and task_woken_rt() would be sufficient, I think.
i.e no changes to push/pull logic and we have a fallback for wakeup time cpu
selection.

It is not clear what you meant by pushing the unfit task ASAP. A running
task on a little CPU can not be pushed to BIG CPU. That would require waking
a migration task to do the migration. The other problem is if CPU has more
than 2 tasks (excluding running task) which one to be pushed. Are you trying
to solve this problem?


> If the task is pinned to a single CPU, we won't inc rt_nr_unfitting,
> hence skipping the push in this case.
> 
> Also there's no need to force a push on switched_to_rt(). On the next
> wakeup we should handle it which should suffice.
> 
> Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> LINK: https://lore.kernel.org/lkml/20200221080701.GF28029@codeaurora.org/
> Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> ---
>  kernel/sched/rt.c    | 100 +++++++++++++++++++++++++++++++++++++++----
>  kernel/sched/sched.h |   3 ++
>  2 files changed, 95 insertions(+), 8 deletions(-)
> 
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index 9ae8a9fabe8b..b35e49cdafcc 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -11,6 +11,7 @@ int sched_rr_timeslice = RR_TIMESLICE;
>  int sysctl_sched_rr_timeslice = (MSEC_PER_SEC / HZ) * RR_TIMESLICE;
>  
>  static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
> +static bool rt_task_fits_capacity(struct task_struct *p, int cpu);
>  
>  struct rt_bandwidth def_rt_bandwidth;
>  
> @@ -313,6 +314,27 @@ static void update_rt_migration(struct rt_rq *rt_rq)
>  	}
>  }
>  
> +#ifdef CONFIG_UCLAMP_TASK
> +static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
> +{
> +	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
> +
> +	if (!rt_task_fits_capacity(p, cpu))
> +		rt_rq->rt_nr_unfit++;
> +}
> +
> +static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
> +{
> +	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
> +
> +	if (!rt_task_fits_capacity(p, cpu))
> +		rt_rq->rt_nr_unfit--;
> +}
> +#else
> +static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
> +static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
> +#endif
> +
>  static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>  {
>  	struct task_struct *p;
> @@ -324,9 +346,17 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>  	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
>  
>  	rt_rq->rt_nr_total++;
> -	if (p->nr_cpus_allowed > 1)
> +	if (p->nr_cpus_allowed > 1) {
>  		rt_rq->rt_nr_migratory++;
>  
> +		/*
> +		 * The task is dequeued and queue again on set_cpus_allowed(),
> +		 * so we can't end up with a unbalanced inc/dec if
> +		 * p->nr_cpus_allowed has changed.
> +		 */
> +		inc_rt_unfit_tasks(p, rt_rq);
> +	}
> +
>  	update_rt_migration(rt_rq);
>  }
>  
> @@ -341,12 +371,29 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>  	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
>  
>  	rt_rq->rt_nr_total--;
> -	if (p->nr_cpus_allowed > 1)
> +	if (p->nr_cpus_allowed > 1) {
>  		rt_rq->rt_nr_migratory--;
>  
> +		/*
> +		 * The task is dequeued and queue again on set_cpus_allowed(),
> +		 * so we can't end up with a unbalanced inc/dec if
> +		 * p->nr_cpus_allowed has changed.
> +		 */
> +		dec_rt_unfit_tasks(p, rt_rq);
> +	}
> +

When uclamp values are changed via cgroups or global sysctl knobs, we don't
enqueue/dequeue all tasks similar to sched_setattr. So a task that was fit
at enqueue time can become unfit if uclamp values are changed in between.

>  	update_rt_migration(rt_rq);
>  }
>  
> +static inline int has_unfit_tasks(struct rq *rq)
> +{
> +#ifdef CONFIG_UCLAMP_TASK
> +	return rq->rt.rt_nr_unfit;
> +#else
> +	return 0;
> +#endif
> +}
> +
>  static inline int has_pushable_tasks(struct rq *rq)
>  {
>  	return !plist_head_empty(&rq->rt.pushable_tasks);
> @@ -1862,8 +1909,9 @@ static int push_rt_task(struct rq *rq)
>  	struct task_struct *next_task;
>  	struct rq *lowest_rq;
>  	int ret = 0;
> +	bool fit;
>  
> -	if (!rq->rt.overloaded)
> +	if (!rq->rt.overloaded && !has_unfit_tasks(rq))
>  		return 0;
>  

When there is one unfit RT task, are we setting overloaded anywhere due
to fitness check? I don't see that in this patch.
Even if we set overload condition, we can't push the running task.

>  	next_task = pick_next_pushable_task(rq);
> @@ -1874,12 +1922,21 @@ static int push_rt_task(struct rq *rq)
>  	if (WARN_ON(next_task == rq->curr))
>  		return 0;
>  
> +	/*
> +	 * The rq could be overloaded because it has unfitting task, if that's
> +	 * the case then we need to try harder to find a better fitting CPU.
> +	 */
> +	fit = rt_task_fits_capacity(next_task, cpu_of(rq));
> +
>  	/*
>  	 * It's possible that the next_task slipped in of
>  	 * higher priority than current. If that's the case
>  	 * just reschedule current.
> +	 *
> +	 * Unless next_task doesn't fit in this cpu, then continue with the
> +	 * attempt to push it.
>  	 */
> -	if (unlikely(next_task->prio < rq->curr->prio)) {
> +	if (unlikely(next_task->prio < rq->curr->prio && fit)) {
>  		resched_curr(rq);
>  		return 0;
>  	}
> @@ -1922,6 +1979,35 @@ static int push_rt_task(struct rq *rq)
>  		goto retry;
>  	}
>  
> +	/*
> +	 * Bail out if the task doesn't fit on either CPUs.
> +	 *
> +	 * Unless..
> +	 *
> +	 * * The rq is already overloaded, then push anyway.
> +	 *
> +	 * * The priority of next_task is higher than current, then we
> +	 *   resched_curr(). We forced skipping this condition above if the rq
> +	 *   was overloaded but the task didn't fit.
> +	 */
> +	if (!fit && !rt_task_fits_capacity(next_task, cpu_of(lowest_rq))) {
> +
> +		/*
> +		 * If the system wasn't overloaded, then pretend we didn't run.
> +		 */
> +		if (!rq->rt.overloaded)
> +			goto out_unlock;
> +
> +		/*
> +		 * If the system is overloaded, we forced skipping this
> +		 * condition, so re-evaluate it.
> +		 */
> +		if (unlikely(next_task->prio < rq->curr->prio)) {
> +			resched_curr(rq);
> +			goto out_unlock;
> +		}
> +	}
> +
>  	deactivate_task(rq, next_task, 0);
>  	set_task_cpu(next_task, lowest_rq->cpu);
>  	activate_task(lowest_rq, next_task, 0);
> @@ -1929,6 +2015,7 @@ static int push_rt_task(struct rq *rq)
>  
>  	resched_curr(lowest_rq);
>  
> +out_unlock:
>  	double_unlock_balance(rq, lowest_rq);
>  
>  out:
> @@ -2297,10 +2384,7 @@ static void switched_to_rt(struct rq *rq, struct task_struct *p)
>  	 */
>  	if (task_on_rq_queued(p) && rq->curr != p) {
>  #ifdef CONFIG_SMP
> -		bool need_to_push = rq->rt.overloaded ||
> -				    !rt_task_fits_capacity(p, cpu_of(rq));
> -
> -		if (p->nr_cpus_allowed > 1 && need_to_push)
> +		if (p->nr_cpus_allowed > 1 && rq->rt.overloaded)
>  			rt_queue_push_tasks(rq);

Right. What about the check in task_woken_rt()? We should remove it
from there too.

>  #endif /* CONFIG_SMP */
>  		if (p->prio < rq->curr->prio && cpu_online(cpu_of(rq)))
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 1a88dc8ad11b..7dea81ccd49a 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -603,6 +603,9 @@ struct rt_rq {
>  #ifdef CONFIG_SMP
>  	unsigned long		rt_nr_migratory;
>  	unsigned long		rt_nr_total;
> +#ifdef CONFIG_UCLAMP_TASK
> +	unsigned long		rt_nr_unfit;
> +#endif
>  	int			overloaded;
>  	struct plist_head	pushable_tasks;
>  
> -- 
> 2.17.1
> 

-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Qais Yousef]

On 02/24/20 11:40, Pavan Kondeti wrote:
> Hi Qais,
> 
> On Sun, Feb 23, 2020 at 06:40:00PM +0000, Qais Yousef wrote:
> > On wakeup, if a task doesn't fit the CPU it is running on (due to its
> > uclamp_min value), then we trigger the push mechanism to try to find a
> > more suitable CPU.
> > 
> > But the logic introduced in commit 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> > was incomplete. If the rq isn't overloaded, push_rt_task() will bail out
> > immediately.
> > 
> > Steve suggested using the overloaded flag to force the push, but as
> > Pavan pointed out this could cause a lot of unnecessary IPIs in case of
> > HAVE_RT_PUSH_IPI.
> > 
> > To still allow pushing unfitting task ASAP, but without causing a lot of
> > disturbance in case this is not possible (no available CPU that is
> > running at a lower priority level), introduce a new rt_nr_unfitting in
> > struct rt_rq and use that to manage how hard we try to push an unfitting
> > task in push_rt_task().
> > 
> 
> The 1-4 patches in this series are looking good to me.
> 
> At this point (after applying 4 patches), removing rt_task_fits_capacity()
> check from switched_to_rt() and task_woken_rt() would be sufficient, I think.
> i.e no changes to push/pull logic and we have a fallback for wakeup time cpu
> selection.
> 
> It is not clear what you meant by pushing the unfit task ASAP. A running
> task on a little CPU can not be pushed to BIG CPU. That would require waking
> a migration task to do the migration. The other problem is if CPU has more
> than 2 tasks (excluding running task) which one to be pushed. Are you trying
> to solve this problem?

Not that's not the problem I'm trying to solve.

Without this patch, spawning 2 tasks in Juno, I see a delay in one of the tasks
to move to a big CPU, despite the CPU not having any tasks running on it.

> 
> 
> > If the task is pinned to a single CPU, we won't inc rt_nr_unfitting,
> > hence skipping the push in this case.
> > 
> > Also there's no need to force a push on switched_to_rt(). On the next
> > wakeup we should handle it which should suffice.
> > 
> > Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> > LINK: https://lore.kernel.org/lkml/20200221080701.GF28029@codeaurora.org/
> > Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> > ---
> >  kernel/sched/rt.c    | 100 +++++++++++++++++++++++++++++++++++++++----
> >  kernel/sched/sched.h |   3 ++
> >  2 files changed, 95 insertions(+), 8 deletions(-)
> > 
> > diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> > index 9ae8a9fabe8b..b35e49cdafcc 100644
> > --- a/kernel/sched/rt.c
> > +++ b/kernel/sched/rt.c
> > @@ -11,6 +11,7 @@ int sched_rr_timeslice = RR_TIMESLICE;
> >  int sysctl_sched_rr_timeslice = (MSEC_PER_SEC / HZ) * RR_TIMESLICE;
> >  
> >  static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
> > +static bool rt_task_fits_capacity(struct task_struct *p, int cpu);
> >  
> >  struct rt_bandwidth def_rt_bandwidth;
> >  
> > @@ -313,6 +314,27 @@ static void update_rt_migration(struct rt_rq *rt_rq)
> >  	}
> >  }
> >  
> > +#ifdef CONFIG_UCLAMP_TASK
> > +static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
> > +{
> > +	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
> > +
> > +	if (!rt_task_fits_capacity(p, cpu))
> > +		rt_rq->rt_nr_unfit++;
> > +}
> > +
> > +static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq)
> > +{
> > +	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
> > +
> > +	if (!rt_task_fits_capacity(p, cpu))
> > +		rt_rq->rt_nr_unfit--;
> > +}
> > +#else
> > +static void inc_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
> > +static void dec_rt_unfit_tasks(struct task_struct *p, struct rt_rq *rt_rq) {}
> > +#endif
> > +
> >  static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
> >  {
> >  	struct task_struct *p;
> > @@ -324,9 +346,17 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
> >  	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
> >  
> >  	rt_rq->rt_nr_total++;
> > -	if (p->nr_cpus_allowed > 1)
> > +	if (p->nr_cpus_allowed > 1) {
> >  		rt_rq->rt_nr_migratory++;
> >  
> > +		/*
> > +		 * The task is dequeued and queue again on set_cpus_allowed(),
> > +		 * so we can't end up with a unbalanced inc/dec if
> > +		 * p->nr_cpus_allowed has changed.
> > +		 */
> > +		inc_rt_unfit_tasks(p, rt_rq);
> > +	}
> > +
> >  	update_rt_migration(rt_rq);
> >  }
> >  
> > @@ -341,12 +371,29 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
> >  	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
> >  
> >  	rt_rq->rt_nr_total--;
> > -	if (p->nr_cpus_allowed > 1)
> > +	if (p->nr_cpus_allowed > 1) {
> >  		rt_rq->rt_nr_migratory--;
> >  
> > +		/*
> > +		 * The task is dequeued and queue again on set_cpus_allowed(),
> > +		 * so we can't end up with a unbalanced inc/dec if
> > +		 * p->nr_cpus_allowed has changed.
> > +		 */
> > +		dec_rt_unfit_tasks(p, rt_rq);
> > +	}
> > +
> 
> When uclamp values are changed via cgroups or global sysctl knobs, we don't
> enqueue/dequeue all tasks similar to sched_setattr. So a task that was fit
> at enqueue time can become unfit if uclamp values are changed in between.

Hmm good point.

> 
> >  	update_rt_migration(rt_rq);
> >  }
> >  
> > +static inline int has_unfit_tasks(struct rq *rq)
> > +{
> > +#ifdef CONFIG_UCLAMP_TASK
> > +	return rq->rt.rt_nr_unfit;
> > +#else
> > +	return 0;
> > +#endif
> > +}
> > +
> >  static inline int has_pushable_tasks(struct rq *rq)
> >  {
> >  	return !plist_head_empty(&rq->rt.pushable_tasks);
> > @@ -1862,8 +1909,9 @@ static int push_rt_task(struct rq *rq)
> >  	struct task_struct *next_task;
> >  	struct rq *lowest_rq;
> >  	int ret = 0;
> > +	bool fit;
> >  
> > -	if (!rq->rt.overloaded)
> > +	if (!rq->rt.overloaded && !has_unfit_tasks(rq))
> >  		return 0;
> >  
> 
> When there is one unfit RT task, are we setting overloaded anywhere due
> to fitness check? I don't see that in this patch.

No. I abandoned tinkering with the overloaded flag, it'd make things more
complex than I'd like them to.

> Even if we set overload condition, we can't push the running task.

This gives me the desired effect. I do see the task moving to the right CPU in
2 RT tasks test. Without it, if an RT task was spawned on little CPU I could
see a big delay for it to move to a big CPU although the big CPU is free.

> 
> >  	next_task = pick_next_pushable_task(rq);
> > @@ -1874,12 +1922,21 @@ static int push_rt_task(struct rq *rq)
> >  	if (WARN_ON(next_task == rq->curr))
> >  		return 0;
> >  
> > +	/*
> > +	 * The rq could be overloaded because it has unfitting task, if that's
> > +	 * the case then we need to try harder to find a better fitting CPU.
> > +	 */
> > +	fit = rt_task_fits_capacity(next_task, cpu_of(rq));
> > +
> >  	/*
> >  	 * It's possible that the next_task slipped in of
> >  	 * higher priority than current. If that's the case
> >  	 * just reschedule current.
> > +	 *
> > +	 * Unless next_task doesn't fit in this cpu, then continue with the
> > +	 * attempt to push it.
> >  	 */
> > -	if (unlikely(next_task->prio < rq->curr->prio)) {
> > +	if (unlikely(next_task->prio < rq->curr->prio && fit)) {
> >  		resched_curr(rq);
> >  		return 0;
> >  	}
> > @@ -1922,6 +1979,35 @@ static int push_rt_task(struct rq *rq)
> >  		goto retry;
> >  	}
> >  
> > +	/*
> > +	 * Bail out if the task doesn't fit on either CPUs.
> > +	 *
> > +	 * Unless..
> > +	 *
> > +	 * * The rq is already overloaded, then push anyway.
> > +	 *
> > +	 * * The priority of next_task is higher than current, then we
> > +	 *   resched_curr(). We forced skipping this condition above if the rq
> > +	 *   was overloaded but the task didn't fit.
> > +	 */
> > +	if (!fit && !rt_task_fits_capacity(next_task, cpu_of(lowest_rq))) {
> > +
> > +		/*
> > +		 * If the system wasn't overloaded, then pretend we didn't run.
> > +		 */
> > +		if (!rq->rt.overloaded)
> > +			goto out_unlock;
> > +
> > +		/*
> > +		 * If the system is overloaded, we forced skipping this
> > +		 * condition, so re-evaluate it.
> > +		 */
> > +		if (unlikely(next_task->prio < rq->curr->prio)) {
> > +			resched_curr(rq);
> > +			goto out_unlock;
> > +		}
> > +	}
> > +
> >  	deactivate_task(rq, next_task, 0);
> >  	set_task_cpu(next_task, lowest_rq->cpu);
> >  	activate_task(lowest_rq, next_task, 0);
> > @@ -1929,6 +2015,7 @@ static int push_rt_task(struct rq *rq)
> >  
> >  	resched_curr(lowest_rq);
> >  
> > +out_unlock:
> >  	double_unlock_balance(rq, lowest_rq);
> >  
> >  out:
> > @@ -2297,10 +2384,7 @@ static void switched_to_rt(struct rq *rq, struct task_struct *p)
> >  	 */
> >  	if (task_on_rq_queued(p) && rq->curr != p) {
> >  #ifdef CONFIG_SMP
> > -		bool need_to_push = rq->rt.overloaded ||
> > -				    !rt_task_fits_capacity(p, cpu_of(rq));
> > -
> > -		if (p->nr_cpus_allowed > 1 && need_to_push)
> > +		if (p->nr_cpus_allowed > 1 && rq->rt.overloaded)
> >  			rt_queue_push_tasks(rq);
> 
> Right. What about the check in task_woken_rt()? We should remove it
> from there too.

We could do, temporarily, to get these fixes into 5.6. But I do think
select_task_rq_rt() doesn't do a good enough job into pushing unfit tasks to
the right CPUs.

I don't understand the reasons behind your objection. It seems you think that
select_task_rq_rt() should be enough, but not AFAICS. Can you be a bit more
detailed please?

FWIW, here's a screenshot of what I see

	https://imgur.com/a/peV27nE

After the first activation, select_task_rq_rt() fails to find the right CPU
(due to the same move all tasks to the cpumask_fist()) - but when the task
wakes up on 4, the logic I put causes it to migrate to CPU2, which is the 2nd
big core. CPU1 and CPU2 are the big cores on Juno.

Now maybe we should fix select_task_rq_rt() to better balance tasks, but not
sure how easy is that.

Steve suggested the overload idea, so I assumed it's okay. But given the IPI
issue you highlighted, I thought better not make overloaded conditions more
complex and just a take a simpler approach which I think should be fine - bar
the uclamp caveat you highlighted. Which should be solvable..

Thanks

--
Qais Yousef

> 
> >  #endif /* CONFIG_SMP */
> >  		if (p->prio < rq->curr->prio && cpu_online(cpu_of(rq)))
> > diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> > index 1a88dc8ad11b..7dea81ccd49a 100644
> > --- a/kernel/sched/sched.h
> > +++ b/kernel/sched/sched.h
> > @@ -603,6 +603,9 @@ struct rt_rq {
> >  #ifdef CONFIG_SMP
> >  	unsigned long		rt_nr_migratory;
> >  	unsigned long		rt_nr_total;
> > +#ifdef CONFIG_UCLAMP_TASK
> > +	unsigned long		rt_nr_unfit;
> > +#endif
> >  	int			overloaded;
> >  	struct plist_head	pushable_tasks;
> >  
> > -- 
> > 2.17.1
> > 
> 
> -- 
> Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.

Re: [PATCH v2 6/6] sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

[Qais Yousef]

On 02/24/20 00:16, Dietmar Eggemann wrote:
> On 23.02.20 19:40, Qais Yousef wrote:
> > The statement
> > 
> > 	rt_rq = &rq_of_rt_rq(rt_rq)->rt
> > 
> > Was just dereferencing rt_rq to get a pointer to itself. Which is a NOP.
> > Remove it.
> > 
> > Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> > ---
> >  kernel/sched/rt.c | 2 --
> >  1 file changed, 2 deletions(-)
> > 
> > diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> > index b35e49cdafcc..520e84993fe7 100644
> > --- a/kernel/sched/rt.c
> > +++ b/kernel/sched/rt.c
> > @@ -343,7 +343,6 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
> >  		return;
> >  
> >  	p = rt_task_of(rt_se);
> > -	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
> 
> IMHO, this is here to get the root rt_rq from any rt_rq (task_groups).
> Looks like that e.g rt_nr_total is only maintained on root rt_rq's.
> 
> Similar to CFS' &rq_of(cfs_rq)->cfs (cfs_rq_util_change()) to get root
> cfs_rq.
> 
> Not sure where CONFIG_RT_GROUP_SCHED=y is used but it's part of the rt
> class implementation.

Ah I see. That was obvious.. How about the below comment?

This code is executed only if rt_entity_is_task(), I don't think this grantees
that the rt_rq isn't for a group?

I need to go and unravel the layers maybe.

Thanks!

--
Qais Yousef

-->8--

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index b35e49cdafcc..f929867215c4 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -343,6 +343,8 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
                return;

        p = rt_task_of(rt_se);
+
+       /* get the root rt_rq if this is the rt_rq of a group */
        rt_rq = &rq_of_rt_rq(rt_rq)->rt;

        rt_rq->rt_nr_total++;
@@ -368,6 +370,8 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
                return;

        p = rt_task_of(rt_se);
+
+       /* get the root rt_rq if this is the rt_rq of a group */
        rt_rq = &rq_of_rt_rq(rt_rq)->rt;

        rt_rq->rt_nr_total--;

Re: [PATCH v2 6/6] sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

[Dietmar Eggemann]

On 24.02.20 12:31, Qais Yousef wrote:
> On 02/24/20 00:16, Dietmar Eggemann wrote:
>> On 23.02.20 19:40, Qais Yousef wrote:

[...]

>>> -	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
>>
>> IMHO, this is here to get the root rt_rq from any rt_rq (task_groups).
>> Looks like that e.g rt_nr_total is only maintained on root rt_rq's.
>>
>> Similar to CFS' &rq_of(cfs_rq)->cfs (cfs_rq_util_change()) to get root
>> cfs_rq.
>>
>> Not sure where CONFIG_RT_GROUP_SCHED=y is used but it's part of the rt
>> class implementation.
> 
> Ah I see. That was obvious.. How about the below comment?
> 
> This code is executed only if rt_entity_is_task(), I don't think this grantees
> that the rt_rq isn't for a group?

No, an rt task can run in this taskgroup (e.g. "/tg/tg1"), i.e. in
tg1->rt_rq[cpu].

The taskgroup skeleton rt_se of e.g. "/tg/tg1/tg11" would also run in
tg1->rt_rq[cpu] but for those rt_se's we bail out of [inc/dec]_rt_migration.

> 
> I need to go and unravel the layers maybe.
> 
> Thanks!
> 
> --
> Qais Yousef
> 
> -->8--
> 
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index b35e49cdafcc..f929867215c4 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -343,6 +343,8 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
>                 return;
> 
>         p = rt_task_of(rt_se);
> +
> +       /* get the root rt_rq if this is the rt_rq of a group */

Not sure if a comment like this will help since:

(a) the definition of rq_of_rt_rq() for the !CONFIG_RT_GROUP_SCHED case

(b) rt_rq might already be the root rt_rq in case the task runs in "/"

[...]

Re: [PATCH v2 6/6] sched/rt: Remove unnecessary assignment in inc/dec_rt_migration

[Qais Yousef]

On 02/24/20 13:03, Dietmar Eggemann wrote:
> On 24.02.20 12:31, Qais Yousef wrote:
> > On 02/24/20 00:16, Dietmar Eggemann wrote:
> >> On 23.02.20 19:40, Qais Yousef wrote:
> 
> [...]
> 
> >>> -	rt_rq = &rq_of_rt_rq(rt_rq)->rt;
> >>
> >> IMHO, this is here to get the root rt_rq from any rt_rq (task_groups).
> >> Looks like that e.g rt_nr_total is only maintained on root rt_rq's.
> >>
> >> Similar to CFS' &rq_of(cfs_rq)->cfs (cfs_rq_util_change()) to get root
> >> cfs_rq.
> >>
> >> Not sure where CONFIG_RT_GROUP_SCHED=y is used but it's part of the rt
> >> class implementation.
> > 
> > Ah I see. That was obvious.. How about the below comment?
> > 
> > This code is executed only if rt_entity_is_task(), I don't think this grantees
> > that the rt_rq isn't for a group?
> 
> No, an rt task can run in this taskgroup (e.g. "/tg/tg1"), i.e. in
> tg1->rt_rq[cpu].
> 
> The taskgroup skeleton rt_se of e.g. "/tg/tg1/tg11" would also run in
> tg1->rt_rq[cpu] but for those rt_se's we bail out of [inc/dec]_rt_migration.
> 
> > 
> > I need to go and unravel the layers maybe.
> > 
> > Thanks!
> > 
> > --
> > Qais Yousef
> > 
> > -->8--
> > 
> > diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> > index b35e49cdafcc..f929867215c4 100644
> > --- a/kernel/sched/rt.c
> > +++ b/kernel/sched/rt.c
> > @@ -343,6 +343,8 @@ static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
> >                 return;
> > 
> >         p = rt_task_of(rt_se);
> > +
> > +       /* get the root rt_rq if this is the rt_rq of a group */
> 
> Not sure if a comment like this will help since:
> 
> (a) the definition of rq_of_rt_rq() for the !CONFIG_RT_GROUP_SCHED case
> 
> (b) rt_rq might already be the root rt_rq in case the task runs in "/"

I thought the comment explains that.

FWIW I don't think someone looking at the code need to look at rq_of_rt_rq() to
get the dependency, but if the above doesn't help I have no better suggestion.
So I'll drop it.

Thanks

--
Qais Yousef

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Pavan Kondeti]

Hi Qais,

On Mon, Feb 24, 2020 at 5:42 PM Qais Yousef <qais.yousef@arm.com> wrote:
[...]
> We could do, temporarily, to get these fixes into 5.6. But I do think
> select_task_rq_rt() doesn't do a good enough job into pushing unfit tasks to
> the right CPUs.
>
> I don't understand the reasons behind your objection. It seems you think that
> select_task_rq_rt() should be enough, but not AFAICS. Can you be a bit more
> detailed please?
>
> FWIW, here's a screenshot of what I see
>
>         https://imgur.com/a/peV27nE
>
> After the first activation, select_task_rq_rt() fails to find the right CPU
> (due to the same move all tasks to the cpumask_fist()) - but when the task
> wakes up on 4, the logic I put causes it to migrate to CPU2, which is the 2nd
> big core. CPU1 and CPU2 are the big cores on Juno.
>
> Now maybe we should fix select_task_rq_rt() to better balance tasks, but not
> sure how easy is that.
>

Thanks for the trace. Now things are clear to me. Two RT tasks woke up
simultaneously and the first task got its previous CPU i.e CPU#1. The next task
goes through find_lowest_rq() and got the same CPU#1. Since this task priority
is not more than the just queued task (already queued on CPU#1), it is sent
to its previous CPU i.e CPU#4 in your case.

From task_woken_rt() path, CPU#4 attempts push_rt_tasks(). CPU#4 is
not overloaded,
but we have rt_task_fits_capacity() check which forces the push. Since the CPU
is not overloaded, your has_unfit_tasks() comes to rescue and push the
task. Since
the task has not scheduled in yet, it is eligible for push. You added checks
to skip resched_curr() in push_rt_tasks() otherwise the push won't happen.

Finally, I understood your patch. Obviously this is not clear to me
before. I am not
sure if this patch is the right approach to solve this race. I will
think a bit more.

Thanks,
Pavan
-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
Linux Foundation Collaborative Project

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Qais Yousef]

On 02/24/20 21:34, Pavan Kondeti wrote:
> Hi Qais,
> 
> On Mon, Feb 24, 2020 at 5:42 PM Qais Yousef <qais.yousef@arm.com> wrote:
> [...]
> > We could do, temporarily, to get these fixes into 5.6. But I do think
> > select_task_rq_rt() doesn't do a good enough job into pushing unfit tasks to
> > the right CPUs.
> >
> > I don't understand the reasons behind your objection. It seems you think that
> > select_task_rq_rt() should be enough, but not AFAICS. Can you be a bit more
> > detailed please?
> >
> > FWIW, here's a screenshot of what I see
> >
> >         https://imgur.com/a/peV27nE
> >
> > After the first activation, select_task_rq_rt() fails to find the right CPU
> > (due to the same move all tasks to the cpumask_fist()) - but when the task
> > wakes up on 4, the logic I put causes it to migrate to CPU2, which is the 2nd
> > big core. CPU1 and CPU2 are the big cores on Juno.
> >
> > Now maybe we should fix select_task_rq_rt() to better balance tasks, but not
> > sure how easy is that.
> >
> 
> Thanks for the trace. Now things are clear to me. Two RT tasks woke up
> simultaneously and the first task got its previous CPU i.e CPU#1. The next task
> goes through find_lowest_rq() and got the same CPU#1. Since this task priority
> is not more than the just queued task (already queued on CPU#1), it is sent
> to its previous CPU i.e CPU#4 in your case.
> 
> From task_woken_rt() path, CPU#4 attempts push_rt_tasks(). CPU#4 is
> not overloaded,
> but we have rt_task_fits_capacity() check which forces the push. Since the CPU
> is not overloaded, your has_unfit_tasks() comes to rescue and push the
> task. Since
> the task has not scheduled in yet, it is eligible for push. You added checks
> to skip resched_curr() in push_rt_tasks() otherwise the push won't happen.

Nice summary, that's exactly what it is :)

> Finally, I understood your patch. Obviously this is not clear to me
> before. I am not
> sure if this patch is the right approach to solve this race. I will
> think a bit more.

I haven't been staring at this code for as long as you, but since we have
logic at wakeup to do a push, I think we need something here anyway for unfit
tasks.

Fixing select_task_rq_rt() to better balance tasks will help a lot in general,
but if that was enough already then why do we need to consider a push at the
wakeup at all then?

AFAIU, in SMP the whole push-pull mechanism is racy and we introduce redundancy
at taking the decision on various points to ensure we minimize this racy nature
of SMP systems. Anything could have happened between the time we called
select_task_rq_rt() and the wakeup, so we double check again before we finally
go and run. That's how I interpret it.

I am open to hear about other alternatives first anyway. Your help has been
much appreciated so far.

Thanks

--
Qais Yousef

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Pavan Kondeti]

On Mon, Feb 24, 2020 at 05:41:39PM +0000, Qais Yousef wrote:
> On 02/24/20 21:34, Pavan Kondeti wrote:
> > Hi Qais,
> > 
> > On Mon, Feb 24, 2020 at 5:42 PM Qais Yousef <qais.yousef@arm.com> wrote:
> > [...]
> > > We could do, temporarily, to get these fixes into 5.6. But I do think
> > > select_task_rq_rt() doesn't do a good enough job into pushing unfit tasks to
> > > the right CPUs.
> > >
> > > I don't understand the reasons behind your objection. It seems you think that
> > > select_task_rq_rt() should be enough, but not AFAICS. Can you be a bit more
> > > detailed please?
> > >
> > > FWIW, here's a screenshot of what I see
> > >
> > >         https://imgur.com/a/peV27nE
> > >
> > > After the first activation, select_task_rq_rt() fails to find the right CPU
> > > (due to the same move all tasks to the cpumask_fist()) - but when the task
> > > wakes up on 4, the logic I put causes it to migrate to CPU2, which is the 2nd
> > > big core. CPU1 and CPU2 are the big cores on Juno.
> > >
> > > Now maybe we should fix select_task_rq_rt() to better balance tasks, but not
> > > sure how easy is that.
> > >
> > 
> > Thanks for the trace. Now things are clear to me. Two RT tasks woke up
> > simultaneously and the first task got its previous CPU i.e CPU#1. The next task
> > goes through find_lowest_rq() and got the same CPU#1. Since this task priority
> > is not more than the just queued task (already queued on CPU#1), it is sent
> > to its previous CPU i.e CPU#4 in your case.
> > 
> > From task_woken_rt() path, CPU#4 attempts push_rt_tasks(). CPU#4 is
> > not overloaded,
> > but we have rt_task_fits_capacity() check which forces the push. Since the CPU
> > is not overloaded, your has_unfit_tasks() comes to rescue and push the
> > task. Since
> > the task has not scheduled in yet, it is eligible for push. You added checks
> > to skip resched_curr() in push_rt_tasks() otherwise the push won't happen.
> 
> Nice summary, that's exactly what it is :)
> 
> > Finally, I understood your patch. Obviously this is not clear to me
> > before. I am not
> > sure if this patch is the right approach to solve this race. I will
> > think a bit more.
> 
> I haven't been staring at this code for as long as you, but since we have
> logic at wakeup to do a push, I think we need something here anyway for unfit
> tasks.
> 
> Fixing select_task_rq_rt() to better balance tasks will help a lot in general,
> but if that was enough already then why do we need to consider a push at the
> wakeup at all then?
> 
> AFAIU, in SMP the whole push-pull mechanism is racy and we introduce redundancy
> at taking the decision on various points to ensure we minimize this racy nature
> of SMP systems. Anything could have happened between the time we called
> select_task_rq_rt() and the wakeup, so we double check again before we finally
> go and run. That's how I interpret it.
> 
> I am open to hear about other alternatives first anyway. Your help has been
> much appreciated so far.
> 

The search inside find_lowest_rq() happens without any locks so I believe it
is expected to have races like this. In fact there is a comment in the code
saying "This test is optimistic, if we get it wrong the load-balancer
will have to sort it out" in select_task_rq_rt(). However, the push logic
as of today works only for overloaded case. In that sense, your patch fixes
this race for b.L systems. At the same time, I feel like tracking nonfit tasks
just to fix this race seems to be too much. I will leave this to Steve and
others to take a decision.

I thought of suggesting to remove the below check from select_task_rq_rt()

p->prio < cpu_rq(target)->rt.highest_prio.curr

which would then make the target CPU overloaded and the push logic would
spread the tasks. That works for a b.L system too. However there seems to
be a very good reason for doing this. see
https://lore.kernel.org/patchwork/patch/539137/

The fact that a CPU is part of lowest_mask but running a higher prio RT
task means there is a race. Should we retry one more time to see if we find
another CPU?

Thanks,
Pavan

-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.

Re: [PATCH v2 2/6] sched/rt: Re-instate old behavior in select_task_rq_rt

[Dietmar Eggemann]

On 23.02.20 18:39, Qais Yousef wrote:

[...]

> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index 4043abe45459..2c3fae637cef 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -1474,6 +1474,13 @@ select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
>  	if (test || !rt_task_fits_capacity(p, cpu)) {
>  		int target = find_lowest_rq(p);
>  
> +		/*
> +		 * Bail out if we were forcing a migration to find a better
> +		 * fitting CPU but our search failed.
> +		 */
> +		if (!test && !rt_task_fits_capacity(p, target))
> +			goto out_unlock;

Didn't you loose the 'target != -1' condition from
https://lore.kernel.org/r/20200218041620.GD28029@codeaurora.org ?

A call to rt_task_fits_capacity(p, -1) would cause issues on a
heterogeneous system.

I tried to provoke this but wasn't able to do so. find_lowest_rq()
returns -1 in 4 places. (1) lowest_mask should be there (2) if
'task->nr_cpus_allowed == 1' select_task_rq_rt() wouldn't have been
called but maybe (3) or (4) can still return -1.

[...]

Re: [PATCH v2 2/6] sched/rt: Re-instate old behavior in select_task_rq_rt

[Qais Yousef]

On 02/25/20 15:21, Dietmar Eggemann wrote:
> On 23.02.20 18:39, Qais Yousef wrote:
> 
> [...]
> 
> > diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> > index 4043abe45459..2c3fae637cef 100644
> > --- a/kernel/sched/rt.c
> > +++ b/kernel/sched/rt.c
> > @@ -1474,6 +1474,13 @@ select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
> >  	if (test || !rt_task_fits_capacity(p, cpu)) {
> >  		int target = find_lowest_rq(p);
> >  
> > +		/*
> > +		 * Bail out if we were forcing a migration to find a better
> > +		 * fitting CPU but our search failed.
> > +		 */
> > +		if (!test && !rt_task_fits_capacity(p, target))
> > +			goto out_unlock;
> 
> Didn't you loose the 'target != -1' condition from
> https://lore.kernel.org/r/20200218041620.GD28029@codeaurora.org ?
> 
> A call to rt_task_fits_capacity(p, -1) would cause issues on a
> heterogeneous system.

Good catch! Right you are. I'll fix this and send v3, once it is clear what
would be right way forward to handle the wakeup-path.

Thanks!

--
Qais Yousef

> 
> I tried to provoke this but wasn't able to do so. find_lowest_rq()
> returns -1 in 4 places. (1) lowest_mask should be there (2) if
> 'task->nr_cpus_allowed == 1' select_task_rq_rt() wouldn't have been
> called but maybe (3) or (4) can still return -1.
> 
> [...]

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Qais Yousef]

On 02/25/20 09:25, Pavan Kondeti wrote:
> > I haven't been staring at this code for as long as you, but since we have
> > logic at wakeup to do a push, I think we need something here anyway for unfit
> > tasks.
> > 
> > Fixing select_task_rq_rt() to better balance tasks will help a lot in general,
> > but if that was enough already then why do we need to consider a push at the
> > wakeup at all then?
> > 
> > AFAIU, in SMP the whole push-pull mechanism is racy and we introduce redundancy
> > at taking the decision on various points to ensure we minimize this racy nature
> > of SMP systems. Anything could have happened between the time we called
> > select_task_rq_rt() and the wakeup, so we double check again before we finally
> > go and run. That's how I interpret it.
> > 
> > I am open to hear about other alternatives first anyway. Your help has been
> > much appreciated so far.
> > 
> 
> The search inside find_lowest_rq() happens without any locks so I believe it
> is expected to have races like this. In fact there is a comment in the code
> saying "This test is optimistic, if we get it wrong the load-balancer
> will have to sort it out" in select_task_rq_rt(). However, the push logic
> as of today works only for overloaded case. In that sense, your patch fixes
> this race for b.L systems. At the same time, I feel like tracking nonfit tasks
> just to fix this race seems to be too much. I will leave this to Steve and
> others to take a decision.

I do think without this tasks can end up on the wrong CPU longer than they
should. Keep in mind that if a task is boosted to run on a big core, it still
have to compete with non-boosted tasks who can run on a any cpu. So this
opportunistic push might be necessary.

For 5.6 though, I'll send an updated series that removes the fitness check from
task_woken_rt() && switched_to_rt() and carry on with this discussion for 5.7.

> 
> I thought of suggesting to remove the below check from select_task_rq_rt()
> 
> p->prio < cpu_rq(target)->rt.highest_prio.curr
> 
> which would then make the target CPU overloaded and the push logic would
> spread the tasks. That works for a b.L system too. However there seems to
> be a very good reason for doing this. see
> https://lore.kernel.org/patchwork/patch/539137/
> 
> The fact that a CPU is part of lowest_mask but running a higher prio RT
> task means there is a race. Should we retry one more time to see if we find
> another CPU?

Isn't this what I did in v1?

https://lore.kernel.org/lkml/20200214163949.27850-4-qais.yousef@arm.com/

Thanks

--
Qais Yousef

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Pavan Kondeti]

On Wed, Feb 26, 2020 at 04:02:48PM +0000, Qais Yousef wrote:
> On 02/25/20 09:25, Pavan Kondeti wrote:
> > > I haven't been staring at this code for as long as you, but since we have
> > > logic at wakeup to do a push, I think we need something here anyway for unfit
> > > tasks.
> > > 
> > > Fixing select_task_rq_rt() to better balance tasks will help a lot in general,
> > > but if that was enough already then why do we need to consider a push at the
> > > wakeup at all then?
> > > 
> > > AFAIU, in SMP the whole push-pull mechanism is racy and we introduce redundancy
> > > at taking the decision on various points to ensure we minimize this racy nature
> > > of SMP systems. Anything could have happened between the time we called
> > > select_task_rq_rt() and the wakeup, so we double check again before we finally
> > > go and run. That's how I interpret it.
> > > 
> > > I am open to hear about other alternatives first anyway. Your help has been
> > > much appreciated so far.
> > > 
> > 
> > The search inside find_lowest_rq() happens without any locks so I believe it
> > is expected to have races like this. In fact there is a comment in the code
> > saying "This test is optimistic, if we get it wrong the load-balancer
> > will have to sort it out" in select_task_rq_rt(). However, the push logic
> > as of today works only for overloaded case. In that sense, your patch fixes
> > this race for b.L systems. At the same time, I feel like tracking nonfit tasks
> > just to fix this race seems to be too much. I will leave this to Steve and
> > others to take a decision.
> 
> I do think without this tasks can end up on the wrong CPU longer than they
> should. Keep in mind that if a task is boosted to run on a big core, it still
> have to compete with non-boosted tasks who can run on a any cpu. So this
> opportunistic push might be necessary.
> 
> For 5.6 though, I'll send an updated series that removes the fitness check from
> task_woken_rt() && switched_to_rt() and carry on with this discussion for 5.7.
> 
> > 
> > I thought of suggesting to remove the below check from select_task_rq_rt()
> > 
> > p->prio < cpu_rq(target)->rt.highest_prio.curr
> > 
> > which would then make the target CPU overloaded and the push logic would
> > spread the tasks. That works for a b.L system too. However there seems to
> > be a very good reason for doing this. see
> > https://lore.kernel.org/patchwork/patch/539137/
> > 
> > The fact that a CPU is part of lowest_mask but running a higher prio RT
> > task means there is a race. Should we retry one more time to see if we find
> > another CPU?
> 
> Isn't this what I did in v1?
> 
> https://lore.kernel.org/lkml/20200214163949.27850-4-qais.yousef@arm.com/
> 

Yes, that patch allows overloading the CPU When the priorities are same.
I think, We should also consider when a low prio task and high prio task
are waking at the same time and high prio task winning the race.

Thanks,
Pavan

-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.

Re: [PATCH v2 5/6] sched/rt: Better manage pushing unfit tasks on wakeup

[Qais Yousef]

On 02/27/20 09:06, Pavan Kondeti wrote:
> On Wed, Feb 26, 2020 at 04:02:48PM +0000, Qais Yousef wrote:
> > On 02/25/20 09:25, Pavan Kondeti wrote:
> > > > I haven't been staring at this code for as long as you, but since we have
> > > > logic at wakeup to do a push, I think we need something here anyway for unfit
> > > > tasks.
> > > > 
> > > > Fixing select_task_rq_rt() to better balance tasks will help a lot in general,
> > > > but if that was enough already then why do we need to consider a push at the
> > > > wakeup at all then?
> > > > 
> > > > AFAIU, in SMP the whole push-pull mechanism is racy and we introduce redundancy
> > > > at taking the decision on various points to ensure we minimize this racy nature
> > > > of SMP systems. Anything could have happened between the time we called
> > > > select_task_rq_rt() and the wakeup, so we double check again before we finally
> > > > go and run. That's how I interpret it.
> > > > 
> > > > I am open to hear about other alternatives first anyway. Your help has been
> > > > much appreciated so far.
> > > > 
> > > 
> > > The search inside find_lowest_rq() happens without any locks so I believe it
> > > is expected to have races like this. In fact there is a comment in the code
> > > saying "This test is optimistic, if we get it wrong the load-balancer
> > > will have to sort it out" in select_task_rq_rt(). However, the push logic
> > > as of today works only for overloaded case. In that sense, your patch fixes
> > > this race for b.L systems. At the same time, I feel like tracking nonfit tasks
> > > just to fix this race seems to be too much. I will leave this to Steve and
> > > others to take a decision.
> > 
> > I do think without this tasks can end up on the wrong CPU longer than they
> > should. Keep in mind that if a task is boosted to run on a big core, it still
> > have to compete with non-boosted tasks who can run on a any cpu. So this
> > opportunistic push might be necessary.
> > 
> > For 5.6 though, I'll send an updated series that removes the fitness check from
> > task_woken_rt() && switched_to_rt() and carry on with this discussion for 5.7.
> > 
> > > 
> > > I thought of suggesting to remove the below check from select_task_rq_rt()
> > > 
> > > p->prio < cpu_rq(target)->rt.highest_prio.curr
> > > 
> > > which would then make the target CPU overloaded and the push logic would
> > > spread the tasks. That works for a b.L system too. However there seems to
> > > be a very good reason for doing this. see
> > > https://lore.kernel.org/patchwork/patch/539137/
> > > 
> > > The fact that a CPU is part of lowest_mask but running a higher prio RT
> > > task means there is a race. Should we retry one more time to see if we find
> > > another CPU?
> > 
> > Isn't this what I did in v1?
> > 
> > https://lore.kernel.org/lkml/20200214163949.27850-4-qais.yousef@arm.com/
> > 
> 
> Yes, that patch allows overloading the CPU When the priorities are same.

So I assume you're okay with this patch now?

> I think, We should also consider when a low prio task and high prio task
> are waking at the same time and high prio task winning the race.

You mean the bug I describe here?

https://lore.kernel.org/lkml/20200219140243.wfljmupcrwm2jelo@e107158-lin/

That needs more serious thinking.

Thanks

--
Qais Yousef