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

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

[Qais Yousef]

Changes since v2:
	* Fix missing check target != -1 (patch 2)
	* Drop the logic to check for fit cpu in wakeup and switched_to_rt()
	  (patch 5)
	* Added the patch that fixes pushing unfit cpu in select_task_rq_rt
	  That was patch 3 in v1[1] (patch 6)

Link to v2:
	https://lore.kernel.org/lkml/20200223184001.14248-1-qais.yousef@arm.com/#t


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

Please consider applying as fixes for 5.6.

Except for patch 6 which I'm not sure if the discussion around it has settled,
patches 1-5 should be good to go.

Thanks!

--
Qais Yousef

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


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: Remove unnecessary push for unfit tasks
  sched/rt: Fix pushing unfit tasks to a better CPU

 kernel/sched/cpupri.c | 167 +++++++++++++++++++++++++++---------------
 kernel/sched/cpupri.h |   6 +-
 kernel/sched/rt.c     |  71 +++++++++++++-----
 3 files changed, 166 insertions(+), 78 deletions(-)

-- 
2.17.1

[PATCH v3 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

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Qais Yousef]

Hi Tao

On 03/04/20 22:51, Tao Zhou wrote:

[...]

> >  /**
> >   * 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;
> 
> How about using cpumask to store CPUs when the "best unfit"
> happened. So, no need to call __cpupri_find() again.

I considered the CPU mask but it's expensive.

I either have to create a percpu variable, or allocate something at every call
here. Neither of which seemed acceptable to me.

Recording the idx is simple and cheap IMO.

[...]

> > +	/*
> > +	 * 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);
> > +
> 
> Even use a loop again here, i don't know.

I don't see if going through the loop twice will help here. The proces is racy,
and I think by the time we reached here we would have tried hard enough to find
the best cpu to run on?

Thanks

--
Qais Yousef

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Steven Rostedt]

On Mon,  2 Mar 2020 13:27:16 +0000
Qais Yousef <qais.yousef@arm.com> wrote:


>  /**
>   * 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;

Nit, but if you moved idx, might as well remove the unnecessary
initialization of it as well ;-)

>  
>  	BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);
>  
>  	for (idx = 0; idx < task_pri; idx++) {

It's initialized here.

> -		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);

Hmm, this only checks the one index, which can change and then we miss
everything. I think we can do better. What about this:


        for (idx = 0; idx < task_pri; idx++) {
		int found = -1;

                if (!__cpupri_find(cp, p, lowest_mask, idx))
                        continue;

                if (!lowest_mask || !fitness_fn)
                        return 1;

		/* Make sure we have one fit CPU before clearing */
		for_each_cpu(cpu, lowest_mask) {
			if (fitness_fn(p, cpu)) {
				found = cpu;
				break;
			}
		}

		if (found == -1)
			continue;

                /* Ensure the capacity of the CPUs fit the task */
                for_each_cpu(cpu, lowest_mask) {
                        if (cpu < found || !fitness_fn(p, cpu))
                                cpumask_clear_cpu(cpu, lowest_mask);
                }

                return 1;
        }

This way, if nothing fits we return the untouched lowest_mask, and only
clear the lowest_mask bits if we found a fitness cpu.

-- Steve

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Qais Yousef]

On 03/04/20 11:27, Steven Rostedt wrote:
> On Mon,  2 Mar 2020 13:27:16 +0000
> Qais Yousef <qais.yousef@arm.com> wrote:
> 
> 
> >  /**
> >   * 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;
> 
> Nit, but if you moved idx, might as well remove the unnecessary
> initialization of it as well ;-)

Sure :)

> 
> >  
> >  	BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);
> >  
> >  	for (idx = 0; idx < task_pri; idx++) {
> 
> It's initialized here.
> 
> > -		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);
> 
> Hmm, this only checks the one index, which can change and then we miss
> everything. I think we can do better. What about this:

Hmm. I see 2 issues with this approach:

> 
> 
>         for (idx = 0; idx < task_pri; idx++) {
> 		int found = -1;
> 
>                 if (!__cpupri_find(cp, p, lowest_mask, idx))
>                         continue;

1.

__cpupri_find() could update the lowest_mask at the next iteration, so the
fallback wouldn't be the lowest level, right?

> 
>                 if (!lowest_mask || !fitness_fn)
>                         return 1;
> 
> 		/* Make sure we have one fit CPU before clearing */
> 		for_each_cpu(cpu, lowest_mask) {
> 			if (fitness_fn(p, cpu)) {
> 				found = cpu;
> 				break;
> 			}
> 		}
> 
> 		if (found == -1)
> 			continue;

2.

If we fix 1, then assuming found == -1 for all level, we'll still have the
problem that the mask is stale.

We can do a full scan again as Tao was suggestion, the 2nd one without any
fitness check that is. But isn't this expensive?

We risk the mask being stale anyway directly after selecting it. Or a priority
level might become the lowest level just after we dismissed it.

So our best effort could end up lying even if we do the right thing (TM).

> 
>                 /* Ensure the capacity of the CPUs fit the task */
>                 for_each_cpu(cpu, lowest_mask) {
>                         if (cpu < found || !fitness_fn(p, cpu))
>                                 cpumask_clear_cpu(cpu, lowest_mask);
>                 }
> 
>                 return 1;
>         }
> 
> This way, if nothing fits we return the untouched lowest_mask, and only
> clear the lowest_mask bits if we found a fitness cpu.

Because of 1, I think the lowest mask will not be the true lowest mask, no?
Please correct me if I missed something.

There's another 'major' problem that I need to bring your attention to,
find_lowest_rq() always returns the first CPU in the mask.

See discussion below for more details

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

In my test because multiple tasks wakeup together they all end up going to CPU1
(the first fitting CPU in the mask), then just to be pushed back again. Not
necessarily to where they were running before.

Not sure if there are other situations where this could happen.

If we fix this problem then we can help reduce the effect of this raciness in
find_lowest_rq(), and end up with less ping-ponging if tasks happen to
wakeup/sleep at the wrong time during the scan.

Or maybe there is a way to eliminate all these races with the current design?

Thanks

--
Qais Yousef

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Steven Rostedt]

On Wed, 4 Mar 2020 17:39:26 +0000
Qais Yousef <qais.yousef@arm.com> wrote:

> > > +	/*
> > > +	 * 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);  
> > 
> > Hmm, this only checks the one index, which can change and then we miss
> > everything. I think we can do better. What about this:  
> 
> Hmm. I see 2 issues with this approach:
> 
> > 
> > 
> >         for (idx = 0; idx < task_pri; idx++) {
> > 		int found = -1;
> > 
> >                 if (!__cpupri_find(cp, p, lowest_mask, idx))
> >                         continue;  
> 
> 1.
> 
> __cpupri_find() could update the lowest_mask at the next iteration, so the
> fallback wouldn't be the lowest level, right?

Hmm, you may be right.

> 
> > 
> >                 if (!lowest_mask || !fitness_fn)
> >                         return 1;
> > 
> > 		/* Make sure we have one fit CPU before clearing */
> > 		for_each_cpu(cpu, lowest_mask) {
> > 			if (fitness_fn(p, cpu)) {
> > 				found = cpu;
> > 				break;
> > 			}
> > 		}
> > 
> > 		if (found == -1)
> > 			continue;  
> 
> 2.
> 
> If we fix 1, then assuming found == -1 for all level, we'll still have the
> problem that the mask is stale.
> 
> We can do a full scan again as Tao was suggestion, the 2nd one without any
> fitness check that is. But isn't this expensive?

I was hoping to try to avoid that, but it's not that expensive and will
probably seldom happen. Perhaps we should run some test cases and trace the
results to see how often that can happen.

> 
> We risk the mask being stale anyway directly after selecting it. Or a priority
> level might become the lowest level just after we dismissed it.

Sure, but that's still a better effort.

> 
> So our best effort could end up lying even if we do the right thing (TM).
> 
> > 
> >                 /* Ensure the capacity of the CPUs fit the task */
> >                 for_each_cpu(cpu, lowest_mask) {
> >                         if (cpu < found || !fitness_fn(p, cpu))
> >                                 cpumask_clear_cpu(cpu, lowest_mask);
> >                 }
> > 
> >                 return 1;
> >         }
> > 
> > This way, if nothing fits we return the untouched lowest_mask, and only
> > clear the lowest_mask bits if we found a fitness cpu.  
> 
> Because of 1, I think the lowest mask will not be the true lowest mask, no?
> Please correct me if I missed something.

No, I think you are correct.

> 
> There's another 'major' problem that I need to bring your attention to,
> find_lowest_rq() always returns the first CPU in the mask.
> 
> See discussion below for more details
> 
> 	https://lore.kernel.org/lkml/20200219140243.wfljmupcrwm2jelo@e107158-lin/
> 
> In my test because multiple tasks wakeup together they all end up going to CPU1
> (the first fitting CPU in the mask), then just to be pushed back again. Not
> necessarily to where they were running before.
> 
> Not sure if there are other situations where this could happen.
> 
> If we fix this problem then we can help reduce the effect of this raciness in
> find_lowest_rq(), and end up with less ping-ponging if tasks happen to
> wakeup/sleep at the wrong time during the scan.

Hmm, I wonder if there's a fast way of getting the next CPU from the
current cpu the task is on. Perhaps that will help in the ping ponging.

-- Steve

> 
> Or maybe there is a way to eliminate all these races with the current design?
> 
> Thanks
> 
> --
> Qais Yousef

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Qais Yousef]

On 03/04/20 13:54, Steven Rostedt wrote:
> > If we fix 1, then assuming found == -1 for all level, we'll still have the
> > problem that the mask is stale.
> > 
> > We can do a full scan again as Tao was suggestion, the 2nd one without any
> > fitness check that is. But isn't this expensive?
> 
> I was hoping to try to avoid that, but it's not that expensive and will
> probably seldom happen. Perhaps we should run some test cases and trace the
> results to see how often that can happen.
> 
> > 
> > We risk the mask being stale anyway directly after selecting it. Or a priority
> > level might become the lowest level just after we dismissed it.
> 
> Sure, but that's still a better effort.

Okay let me run some quick tests and send an updated series if it doesn't
return something suspicious.

Are you happy with the rest of the series then?

> > There's another 'major' problem that I need to bring your attention to,
> > find_lowest_rq() always returns the first CPU in the mask.
> > 
> > See discussion below for more details
> > 
> > 	https://lore.kernel.org/lkml/20200219140243.wfljmupcrwm2jelo@e107158-lin/
> > 
> > In my test because multiple tasks wakeup together they all end up going to CPU1
> > (the first fitting CPU in the mask), then just to be pushed back again. Not
> > necessarily to where they were running before.
> > 
> > Not sure if there are other situations where this could happen.
> > 
> > If we fix this problem then we can help reduce the effect of this raciness in
> > find_lowest_rq(), and end up with less ping-ponging if tasks happen to
> > wakeup/sleep at the wrong time during the scan.
> 
> Hmm, I wonder if there's a fast way of getting the next CPU from the
> current cpu the task is on. Perhaps that will help in the ping ponging.

I think there's for_each_cpu_wrap() or some variant of it that allows to start
from a random place.

This won't help if there's a single cpu in the mask. Or when
nr_waking_tasks > nr_cpus_in_lowest_rq. Still an improvement over the current
behavior nonetheless.

The other option is maybe to mark that cpu unavailable once selected so the
next search can't return it. But when do you mark it available back again?

Thanks

--
Qais Yousef

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Qais Yousef]

On 03/04/20 20:01, Qais Yousef wrote:
> On 03/04/20 13:54, Steven Rostedt wrote:
> > > If we fix 1, then assuming found == -1 for all level, we'll still have the
> > > problem that the mask is stale.
> > > 
> > > We can do a full scan again as Tao was suggestion, the 2nd one without any
> > > fitness check that is. But isn't this expensive?
> > 
> > I was hoping to try to avoid that, but it's not that expensive and will
> > probably seldom happen. Perhaps we should run some test cases and trace the
> > results to see how often that can happen.
> > 
> > > 
> > > We risk the mask being stale anyway directly after selecting it. Or a priority
> > > level might become the lowest level just after we dismissed it.
> > 
> > Sure, but that's still a better effort.
> 
> Okay let me run some quick tests and send an updated series if it doesn't
> return something suspicious.

I ran my 6 tasks test which spawns 6 big tasks on 4 little + 2 big system.
I verified that the 2nd fallback search happens during this scenario.

The duration of the run was 10 seconds.

Using tace-cmd record --profile -l select_task_rq_rt I got the following
results for

	A) Falling back to searching the last unfit_priority_idx only
	B) Falling back to a full search with fitness check disabled

A)
  Event: func: select_task_rq_rt() (600) Total: 2486002 Avg: 4143 Max: 11400(ts:1084.358268) Min:1(ts:1080.258259)
  Event: func: select_task_rq_rt() (2) Total: 11900 Avg: 5950 Max: 8680(ts:1079.659145) Min:3220(ts:1079.659288)
  Event: func: select_task_rq_rt() (4) Total: 13080 Avg: 3270 Max: 3580(ts:1079.659815) Min:3080(ts:1079.659475)
  Event: func: select_task_rq_rt() (3) Total: 15240 Avg: 5080 Max: 6260(ts:1079.659222) Min:4180(ts:1079.659591)
  Event: func: select_task_rq_rt() (1) Total: 5500 Avg: 5500 Max: 5500(ts:1079.659344) Min:5500(ts:1079.659344)
  Event: func: select_task_rq_rt() (2) Total: 8440 Avg: 4220 Max: 4600(ts:1079.659380) Min:3840(ts:1079.659786)
  Event: func: select_task_rq_rt() (3) Total: 22920 Avg: 7640 Max: 11100(ts:1079.659672) Min:3620(ts:1079.659891)

B)
  Event: func: select_task_rq_rt() (600) Total: 2468873 Avg: 4114 Max: 12580(ts:510.268625) Min:1(ts:516.868611)
  Event: func: select_task_rq_rt() (4) Total: 19260 Avg: 4815 Max: 7920(ts:507.369259) Min:3340(ts:507.369669)
  Event: func: select_task_rq_rt() (1) Total: 4700 Avg: 4700 Max: 4700(ts:507.369583) Min:4700(ts:507.369583)
  Event: func: select_task_rq_rt() (3) Total: 7640 Avg: 2546 Max: 3320(ts:507.369403) Min:1300(ts:507.369428)
  Event: func: select_task_rq_rt() (2) Total: 8760 Avg: 4380 Max: 5100(ts:507.369497) Min:3660(ts:507.369338)
  Event: func: select_task_rq_rt() (1) Total: 3240 Avg: 3240 Max: 3240(ts:507.369450) Min:3240(ts:507.369450)

So for both the max seems to be ~12us, which I think is fine.

In the profile report I got something like this which I didn't know how to
interpret. The max value is high; ~72ms.

Did I use and look at the profile output correctly? I still have the trace.dat
for the 2 runs.


                |     + 0x266cb00000000
                |     |   1% (1) time:72836320 max:72836320(ts:1079.785460) min:72836320(ts:1079.785460) avg:72836320
                |     |    0x309000a
                |     |    select_task_rq_rt (0xffff800010152c74)
                |     |    0x0
                |     |    0xe885dcc56c
                |     |    0xe885dcdb24
                |     |    0x2788400000000
                |     |    0x1090047




		...



		                + select_task_rq_rt (0xffff800010152c74)
                |   88% (1) time:72100 max:72100(ts:507.369339) min:72100(ts:507.369339) avg:72100
                |    0x24e4b00000000
                |    0x309000a
                |    select_task_rq_rt (0xffff800010152c74)
                |    0x0
                |    0x53be002898
                |    0x53be003b6c
                |    0x26bc400000000
                |


Thanks

--
Qais Yousef

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Qais Yousef]

On 03/05/20 12:43, Qais Yousef wrote:
> On 03/04/20 20:01, Qais Yousef wrote:
> > On 03/04/20 13:54, Steven Rostedt wrote:
> > > > If we fix 1, then assuming found == -1 for all level, we'll still have the
> > > > problem that the mask is stale.
> > > > 
> > > > We can do a full scan again as Tao was suggestion, the 2nd one without any
> > > > fitness check that is. But isn't this expensive?
> > > 
> > > I was hoping to try to avoid that, but it's not that expensive and will
> > > probably seldom happen. Perhaps we should run some test cases and trace the
> > > results to see how often that can happen.
> > > 
> > > > 
> > > > We risk the mask being stale anyway directly after selecting it. Or a priority
> > > > level might become the lowest level just after we dismissed it.
> > > 
> > > Sure, but that's still a better effort.
> > 
> > Okay let me run some quick tests and send an updated series if it doesn't
> > return something suspicious.
> 
> I ran my 6 tasks test which spawns 6 big tasks on 4 little + 2 big system.
> I verified that the 2nd fallback search happens during this scenario.
> 
> The duration of the run was 10 seconds.
> 
> Using tace-cmd record --profile -l select_task_rq_rt I got the following
> results for
> 
> 	A) Falling back to searching the last unfit_priority_idx only
> 	B) Falling back to a full search with fitness check disabled
> 
> A)
>   Event: func: select_task_rq_rt() (600) Total: 2486002 Avg: 4143 Max: 11400(ts:1084.358268) Min:1(ts:1080.258259)
>   Event: func: select_task_rq_rt() (2) Total: 11900 Avg: 5950 Max: 8680(ts:1079.659145) Min:3220(ts:1079.659288)
>   Event: func: select_task_rq_rt() (4) Total: 13080 Avg: 3270 Max: 3580(ts:1079.659815) Min:3080(ts:1079.659475)
>   Event: func: select_task_rq_rt() (3) Total: 15240 Avg: 5080 Max: 6260(ts:1079.659222) Min:4180(ts:1079.659591)
>   Event: func: select_task_rq_rt() (1) Total: 5500 Avg: 5500 Max: 5500(ts:1079.659344) Min:5500(ts:1079.659344)
>   Event: func: select_task_rq_rt() (2) Total: 8440 Avg: 4220 Max: 4600(ts:1079.659380) Min:3840(ts:1079.659786)
>   Event: func: select_task_rq_rt() (3) Total: 22920 Avg: 7640 Max: 11100(ts:1079.659672) Min:3620(ts:1079.659891)
> 
> B)
>   Event: func: select_task_rq_rt() (600) Total: 2468873 Avg: 4114 Max: 12580(ts:510.268625) Min:1(ts:516.868611)
>   Event: func: select_task_rq_rt() (4) Total: 19260 Avg: 4815 Max: 7920(ts:507.369259) Min:3340(ts:507.369669)
>   Event: func: select_task_rq_rt() (1) Total: 4700 Avg: 4700 Max: 4700(ts:507.369583) Min:4700(ts:507.369583)
>   Event: func: select_task_rq_rt() (3) Total: 7640 Avg: 2546 Max: 3320(ts:507.369403) Min:1300(ts:507.369428)
>   Event: func: select_task_rq_rt() (2) Total: 8760 Avg: 4380 Max: 5100(ts:507.369497) Min:3660(ts:507.369338)
>   Event: func: select_task_rq_rt() (1) Total: 3240 Avg: 3240 Max: 3240(ts:507.369450) Min:3240(ts:507.369450)
> 
> So for both the max seems to be ~12us, which I think is fine.
> 
> In the profile report I got something like this which I didn't know how to
> interpret. The max value is high; ~72ms.
> 
> Did I use and look at the profile output correctly? I still have the trace.dat
> for the 2 runs.
> 
> 
>                 |     + 0x266cb00000000
>                 |     |   1% (1) time:72836320 max:72836320(ts:1079.785460) min:72836320(ts:1079.785460) avg:72836320
>                 |     |    0x309000a
>                 |     |    select_task_rq_rt (0xffff800010152c74)
>                 |     |    0x0
>                 |     |    0xe885dcc56c
>                 |     |    0xe885dcdb24
>                 |     |    0x2788400000000
>                 |     |    0x1090047
> 
> 
> 
> 
> 		...
> 
> 
> 
> 		                + select_task_rq_rt (0xffff800010152c74)
>                 |   88% (1) time:72100 max:72100(ts:507.369339) min:72100(ts:507.369339) avg:72100
>                 |    0x24e4b00000000
>                 |    0x309000a
>                 |    select_task_rq_rt (0xffff800010152c74)
>                 |    0x0
>                 |    0x53be002898
>                 |    0x53be003b6c
>                 |    0x26bc400000000
>                 |

This patch was already picked by Ingo, which I'm fine (and slightly prefer) the
current version. But for the sake of completeness here's patch that falls back
to a full 2nd scan.

Steve, can you please ping Peter/Ingo if you prefer the below version to be
picked up instead? It is based on tip/sched/core and should apply on top of the
picked up series.

Thanks!

--
Qais Yousef

-->8--


From 35d135a629cdd1390ed290648a23975475c9aa95 Mon Sep 17 00:00:00 2001
From: Qais Yousef <qais.yousef@arm.com>
Date: Thu, 5 Mar 2020 10:24:50 +0000
Subject: [PATCH] sched/rt: cpupri_find: Trigger a full search as fallback

If we failed to find a fitting CPU, in cpupri_find(), we only fallback
to the level we found a hit at.

But Steve suggested to fallback to a second full scan instead as this
could be a better effort.

	https://lore.kernel.org/lkml/20200304135404.146c56eb@gandalf.local.home/

We trigger the 2nd search unconditionally since the argument about
triggering a full search is that the recorded fall back level might have
become empty by then. Which means storing any data about what happened
would be meaningless and stale.

I had a humble try at timing it and it seemed okay for the small 6 CPUs
system I was running on

	https://lore.kernel.org/lkml/20200305124324.42x6ehjxbnjkklnh@e107158-lin.cambridge.arm.com/

On large system this second full scan could be expensive. But there are
no users outside capacity awareness for this fitness function at the
moment. Heterogeneous systems tend to be small with 8cores in total.

Suggested-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/cpupri.c | 29 ++++++-----------------------
 1 file changed, 6 insertions(+), 23 deletions(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index dd3f16d1a04a..0033731a0797 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -122,8 +122,7 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 		bool (*fitness_fn)(struct task_struct *p, int cpu))
 {
 	int task_pri = convert_prio(p->prio);
-	int best_unfit_idx = -1;
-	int idx = 0, cpu;
+	int idx, cpu;
 
 	BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);
 
@@ -145,31 +144,15 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 		 * If no CPU at the current priority can fit the task
 		 * continue looking
 		 */
-		if (cpumask_empty(lowest_mask)) {
-			/*
-			 * Store our fallback priority in case we
-			 * didn't find a fitting CPU
-			 */
-			if (best_unfit_idx == -1)
-				best_unfit_idx = idx;
-
+		if (cpumask_empty(lowest_mask))
 			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.
+	 * If we failed to find a fitting lowest_mask, kick off a new search
+	 * but without taking into account any fitness criteria this time.
 	 *
 	 * This rule favours honouring priority over fitting the task in the
 	 * correct CPU (Capacity Awareness being the only user now).
@@ -184,8 +167,8 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 	 * 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);
+	if (fitness_fn)
+		return cpupri_find(cp, p, lowest_mask);
 
 	return 0;
 }
-- 
2.17.1

Re: [PATCH v3 1/6] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[Steven Rostedt]

On Tue, 10 Mar 2020 14:22:20 +0000
Qais Yousef <qais.yousef@arm.com> wrote:

> This patch was already picked by Ingo, which I'm fine (and slightly prefer) the
> current version. But for the sake of completeness here's patch that falls back
> to a full 2nd scan.
> 
> Steve, can you please ping Peter/Ingo if you prefer the below version to be
> picked up instead? It is based on tip/sched/core and should apply on top of the
> picked up series.

Yeah, after looking at it for a bit, I think this is probably the best
"best effort" we can have without getting too complex or allocating more
memory.

Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

Peter or Ingo, want to pick this patch up too?

-- Steve

[tip: sched/core] sched/rt: cpupri_find: Trigger a full search as fallback

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     e94f80f6c49020008e6fa0f3d4b806b8595d17d8
Gitweb:        https://git.kernel.org/tip/e94f80f6c49020008e6fa0f3d4b806b8595d17d8
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Thu, 05 Mar 2020 10:24:50 
Committer:     Peter Zijlstra <peterz@infradead.org>
CommitterDate: Fri, 20 Mar 2020 13:06:20 +01:00

sched/rt: cpupri_find: Trigger a full search as fallback

If we failed to find a fitting CPU, in cpupri_find(), we only fallback
to the level we found a hit at.

But Steve suggested to fallback to a second full scan instead as this
could be a better effort.

	https://lore.kernel.org/lkml/20200304135404.146c56eb@gandalf.local.home/

We trigger the 2nd search unconditionally since the argument about
triggering a full search is that the recorded fall back level might have
become empty by then. Which means storing any data about what happened
would be meaningless and stale.

I had a humble try at timing it and it seemed okay for the small 6 CPUs
system I was running on

	https://lore.kernel.org/lkml/20200305124324.42x6ehjxbnjkklnh@e107158-lin.cambridge.arm.com/

On large system this second full scan could be expensive. But there are
no users outside capacity awareness for this fitness function at the
moment. Heterogeneous systems tend to be small with 8cores in total.

Suggested-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Link: https://lkml.kernel.org/r/20200310142219.syxzn5ljpdxqtbgx@e107158-lin.cambridge.arm.com
---
 kernel/sched/cpupri.c | 29 ++++++-----------------------
 1 file changed, 6 insertions(+), 23 deletions(-)

diff --git a/kernel/sched/cpupri.c b/kernel/sched/cpupri.c
index dd3f16d..0033731 100644
--- a/kernel/sched/cpupri.c
+++ b/kernel/sched/cpupri.c
@@ -122,8 +122,7 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 		bool (*fitness_fn)(struct task_struct *p, int cpu))
 {
 	int task_pri = convert_prio(p->prio);
-	int best_unfit_idx = -1;
-	int idx = 0, cpu;
+	int idx, cpu;
 
 	BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);
 
@@ -145,31 +144,15 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 		 * If no CPU at the current priority can fit the task
 		 * continue looking
 		 */
-		if (cpumask_empty(lowest_mask)) {
-			/*
-			 * Store our fallback priority in case we
-			 * didn't find a fitting CPU
-			 */
-			if (best_unfit_idx == -1)
-				best_unfit_idx = idx;
-
+		if (cpumask_empty(lowest_mask))
 			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.
+	 * If we failed to find a fitting lowest_mask, kick off a new search
+	 * but without taking into account any fitness criteria this time.
 	 *
 	 * This rule favours honouring priority over fitting the task in the
 	 * correct CPU (Capacity Awareness being the only user now).
@@ -184,8 +167,8 @@ int cpupri_find_fitness(struct cpupri *cp, struct task_struct *p,
 	 * 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);
+	if (fitness_fn)
+		return cpupri_find(cp, p, lowest_mask);
 
 	return 0;
 }

[tip: sched/core] sched/rt: cpupri_find: Implement fallback mechanism for !fit case

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     d9cb236b9429044dc694ea70a50163ddd283cea6
Gitweb:        https://git.kernel.org/tip/d9cb236b9429044dc694ea70a50163ddd283cea6
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Mon, 02 Mar 2020 13:27:16 
Committer:     Ingo Molnar <mingo@kernel.org>
CommitterDate: Fri, 06 Mar 2020 12:57:26 +01:00

sched/rt: cpupri_find: Implement fallback mechanism for !fit case

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>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Link: https://lkml.kernel.org/r/20200302132721.8353-2-qais.yousef@arm.com
Link: https://lore.kernel.org/lkml/20200203142712.a7yvlyo2y3le5cpn@e107158-lin/
---
 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 1a2719e..1bcfa19 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;
 }
 

[PATCH v3 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>
---

Notes:
    Changes since v2:
    	* Check that target != -1 (thanks Dietmar)

 kernel/sched/rt.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 4043abe45459..0afc70c9b68b 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 && target != -1 && !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

[tip: sched/core] sched/rt: Re-instate old behavior in select_task_rq_rt()

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     b28bc1e002c23ff8a4999c4a2fb1d4d412bc6f5e
Gitweb:        https://git.kernel.org/tip/b28bc1e002c23ff8a4999c4a2fb1d4d412bc6f5e
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Mon, 02 Mar 2020 13:27:17 
Committer:     Ingo Molnar <mingo@kernel.org>
CommitterDate: Fri, 06 Mar 2020 12:57:27 +01:00

sched/rt: Re-instate old behavior in select_task_rq_rt()

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.

LINK: https://lore.kernel.org/lkml/20200218041620.GD28029@codeaurora.org/
Reported-by: Pavan Kondeti <pkondeti@codeaurora.org>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Link: https://lkml.kernel.org/r/20200302132721.8353-3-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 55a4a50..f0071fa 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1475,6 +1475,13 @@ select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
 		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 && target != -1 && !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:

[PATCH v3 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 0afc70c9b68b..3071c8612c03 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

[tip: sched/core] sched/rt: Optimize cpupri_find() on non-heterogenous systems

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     a1bd02e1f28b1939cac8c64072a0e578c3cbc345
Gitweb:        https://git.kernel.org/tip/a1bd02e1f28b1939cac8c64072a0e578c3cbc345
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Mon, 02 Mar 2020 13:27:18 
Committer:     Ingo Molnar <mingo@kernel.org>
CommitterDate: Fri, 06 Mar 2020 12:57:27 +01:00

sched/rt: Optimize cpupri_find() on non-heterogenous systems

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.

LINK: https://lore.kernel.org/lkml/c0772fca-0a4b-c88d-fdf2-5715fcf8447b@arm.com/
Reported-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Link: https://lkml.kernel.org/r/20200302132721.8353-4-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 1bcfa19..dd3f16d 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 32dd520..efbb492 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 f0071fa..29a8695 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 */
 
 	/*

[PATCH v3 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 3071c8612c03..e79a23ad4a93 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

Re: [PATCH v3 4/6] sched/rt: Allow pulling unfitting task

[Qais Yousef]

On 03/04/20 22:52, Tao Zhou wrote:
> Hi Qais,
> 
> On Mon, Mar 02, 2020 at 01:27:19PM +0000, Qais Yousef wrote:
> > 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 3071c8612c03..e79a23ad4a93 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
> > 
> 
> How about using a rt_cap_overloaded(like rt_overloaded) to indicate the
> cpu is overloaded because a RT task is on unfit CPU. And use stop_one_cpu
> to do in this case.

We have explored a variation of this (without using the stop_one_cpu) in v2

https://lore.kernel.org/lkml/20200223184001.14248-6-qais.yousef@arm.com/

I might still consider this in the future. But I think I need to do better
analysis of the cost-benefit here before pushing further for that.

I'm not keen on stopping a running task as well, not yet at least.

> 
> IIRC, HAVE_RT_PUSH_IPI do not select the specific cpu to do the
> push because the complex there. When RT cap join in, i don't know it
> is need to select the specific unfit CPU or rt overloaded CPU in what
> order is a choice.

I'm not sure I understood you completely here.

I think the patch above dealt with the complexity I think you're talking about.

Thanks

--
Qais Yousef

[tip: sched/core] sched/rt: Allow pulling unfitting task

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     98ca645f824301bde72e0a51cdc8bdbbea6774a5
Gitweb:        https://git.kernel.org/tip/98ca645f824301bde72e0a51cdc8bdbbea6774a5
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Mon, 02 Mar 2020 13:27:19 
Committer:     Ingo Molnar <mingo@kernel.org>
CommitterDate: Fri, 06 Mar 2020 12:57:28 +01:00

sched/rt: Allow pulling unfitting task

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.

LINK: https://lore.kernel.org/lkml/20200203111451.0d1da58f@oasis.local.home/
Suggested-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Link: https://lkml.kernel.org/r/20200302132721.8353-5-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 29a8695..bcb1436 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;

[PATCH v3 5/6] sched/rt: Remove unnecessary push for unfit tasks

[Qais Yousef]

In task_woken_rt() and switched_to_rto() we try trigger push-pull if the
task is unfit.

But the logic is found lacking because if the task was the only one
running on the CPU, then rt_rq is not in overloaded state and won't
trigger a push.

The necessity of this logic was under a debate as well, a summary of
the discussion can be found in the following thread.

https://lore.kernel.org/lkml/20200226160247.iqvdakiqbakk2llz@e107158-lin.cambridge.arm.com/

Remove the logic for now until a better approach is agreed upon.

Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index e79a23ad4a93..ce230bec6847 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -2225,7 +2225,7 @@ static void task_woken_rt(struct rq *rq, struct task_struct *p)
 			    (rq->curr->nr_cpus_allowed < 2 ||
 			     rq->curr->prio <= p->prio);
 
-	if (need_to_push || !rt_task_fits_capacity(p, cpu_of(rq)))
+	if (need_to_push)
 		push_rt_tasks(rq);
 }
 
@@ -2297,10 +2297,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)))
-- 
2.17.1

[tip: sched/core] sched/rt: Remove unnecessary push for unfit tasks

[tip-bot2 for Qais Yousef]

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     d94a9df49069ba8ff7c4aaeca1229e6471a01a15
Gitweb:        https://git.kernel.org/tip/d94a9df49069ba8ff7c4aaeca1229e6471a01a15
Author:        Qais Yousef <qais.yousef@arm.com>
AuthorDate:    Mon, 02 Mar 2020 13:27:20 
Committer:     Ingo Molnar <mingo@kernel.org>
CommitterDate: Fri, 06 Mar 2020 12:57:29 +01:00

sched/rt: Remove unnecessary push for unfit tasks

In task_woken_rt() and switched_to_rto() we try trigger push-pull if the
task is unfit.

But the logic is found lacking because if the task was the only one
running on the CPU, then rt_rq is not in overloaded state and won't
trigger a push.

The necessity of this logic was under a debate as well, a summary of
the discussion can be found in the following thread:

  https://lore.kernel.org/lkml/20200226160247.iqvdakiqbakk2llz@e107158-lin.cambridge.arm.com/

Remove the logic for now until a better approach is agreed upon.

Signed-off-by: Qais Yousef <qais.yousef@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Link: https://lkml.kernel.org/r/20200302132721.8353-6-qais.yousef@arm.com
---
 kernel/sched/rt.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index bcb1436..df11d88 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -2225,7 +2225,7 @@ static void task_woken_rt(struct rq *rq, struct task_struct *p)
 			    (rq->curr->nr_cpus_allowed < 2 ||
 			     rq->curr->prio <= p->prio);
 
-	if (need_to_push || !rt_task_fits_capacity(p, cpu_of(rq)))
+	if (need_to_push)
 		push_rt_tasks(rq);
 }
 
@@ -2297,10 +2297,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)))

[PATCH v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Qais Yousef]

If a task was running on unfit CPU we could ignore migrating if the
priority level of the new fitting CPU is the *same* as the unfit one.

Add an extra check to select_task_rq_rt() to allow the push in case:

	* p->prio == new_cpu.highest_priority
	* task_fits(p, new_cpu)

Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
Signed-off-by: Qais Yousef <qais.yousef@arm.com>
---
 kernel/sched/rt.c | 41 ++++++++++++++++++++++++++++-------------
 1 file changed, 28 insertions(+), 13 deletions(-)

diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index ce230bec6847..8aaa442e4867 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1474,20 +1474,35 @@ 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 && target != -1 && !rt_task_fits_capacity(p, target))
-			goto out_unlock;
+		if (target != -1) {
+			bool fit_target = rt_task_fits_capacity(p, target);
 
-		/*
-		 * Don't bother moving it if the destination CPU is
-		 * not running a lower priority task.
-		 */
-		if (target != -1 &&
-		    p->prio < cpu_rq(target)->rt.highest_prio.curr)
-			cpu = target;
+			/*
+			 * Bail out if we were forcing a migration to find a
+			 * better fitting CPU but our search failed.
+			 */
+			if (!test && !fit_target)
+				goto out_unlock;
+
+			/*
+			 * Don't bother moving it if the destination CPU is
+			 * not running a lower priority task.
+			 */
+			if (p->prio < cpu_rq(target)->rt.highest_prio.curr) {
+
+				cpu = target;
+
+			} else if (p->prio == cpu_rq(target)->rt.highest_prio.curr) {
+
+				/*
+				 * If the priority is the same and the new CPU
+				 * is a better fit, then move, otherwise don't
+				 * bother here either.
+				 */
+				if (fit_target)
+					cpu = target;
+			}
+		}
 	}
 
 out_unlock:
-- 
2.17.1

Re: [PATCH v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Qais Yousef]

Hi Pavan

On 03/02/20 13:27, Qais Yousef wrote:
> If a task was running on unfit CPU we could ignore migrating if the
> priority level of the new fitting CPU is the *same* as the unfit one.
> 
> Add an extra check to select_task_rq_rt() to allow the push in case:
> 
> 	* p->prio == new_cpu.highest_priority
> 	* task_fits(p, new_cpu)
> 
> Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> ---

Can you please confirm if you have any objection to this patch? Without it
I see large delays in the 2 tasks test like I outlined in [1]. It wasn't clear
from [2] whether you are in agreement now or not.

[1] https://lore.kernel.org/lkml/20200217135306.cjc2225wdlwqiicu@e107158-lin.cambridge.arm.com/
[2] https://lore.kernel.org/lkml/20200227033608.GN28029@codeaurora.org/

Thanks

--
Qais Yousef

>  kernel/sched/rt.c | 41 ++++++++++++++++++++++++++++-------------
>  1 file changed, 28 insertions(+), 13 deletions(-)
> 
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index ce230bec6847..8aaa442e4867 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -1474,20 +1474,35 @@ 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 && target != -1 && !rt_task_fits_capacity(p, target))
> -			goto out_unlock;
> +		if (target != -1) {
> +			bool fit_target = rt_task_fits_capacity(p, target);
>  
> -		/*
> -		 * Don't bother moving it if the destination CPU is
> -		 * not running a lower priority task.
> -		 */
> -		if (target != -1 &&
> -		    p->prio < cpu_rq(target)->rt.highest_prio.curr)
> -			cpu = target;
> +			/*
> +			 * Bail out if we were forcing a migration to find a
> +			 * better fitting CPU but our search failed.
> +			 */
> +			if (!test && !fit_target)
> +				goto out_unlock;
> +
> +			/*
> +			 * Don't bother moving it if the destination CPU is
> +			 * not running a lower priority task.
> +			 */
> +			if (p->prio < cpu_rq(target)->rt.highest_prio.curr) {
> +
> +				cpu = target;
> +
> +			} else if (p->prio == cpu_rq(target)->rt.highest_prio.curr) {
> +
> +				/*
> +				 * If the priority is the same and the new CPU
> +				 * is a better fit, then move, otherwise don't
> +				 * bother here either.
> +				 */
> +				if (fit_target)
> +					cpu = target;
> +			}
> +		}
>  	}
>  
>  out_unlock:
> -- 
> 2.17.1
> 

Re: [PATCH v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Pavan Kondeti]

On Fri, Mar 06, 2020 at 05:51:13PM +0000, Qais Yousef wrote:
> Hi Pavan
> 
> On 03/02/20 13:27, Qais Yousef wrote:
> > If a task was running on unfit CPU we could ignore migrating if the
> > priority level of the new fitting CPU is the *same* as the unfit one.
> > 
> > Add an extra check to select_task_rq_rt() to allow the push in case:
> > 
> > 	* p->prio == new_cpu.highest_priority
> > 	* task_fits(p, new_cpu)
> > 
> > Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> > Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> > ---
> 
> Can you please confirm if you have any objection to this patch? Without it
> I see large delays in the 2 tasks test like I outlined in [1]. It wasn't clear
> from [2] whether you are in agreement now or not.
> 
> [1] https://lore.kernel.org/lkml/20200217135306.cjc2225wdlwqiicu@e107158-lin.cambridge.arm.com/
> [2] https://lore.kernel.org/lkml/20200227033608.GN28029@codeaurora.org/
> 

I am not very sure about this. Like we discussed, this patch is addressing a
specific scenario i.e two equal prio tasks waking at the same time. We allow
the packing so that task_woken_rt() spread the tasks. The enqueue operation
is waste here.

At the same time, I can't think of a better alternative. Retrying
find_lowest_rq() may still give the same result until the previous task
is fully woken on the CPU.

btw, the commit description does not talk about the race at all. If there is
no race, we won't even end up in this scenario i.e find_lowest_rq() may simply
return -1.

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 v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Qais Yousef]

On 03/11/20 16:23, Pavan Kondeti wrote:
> On Fri, Mar 06, 2020 at 05:51:13PM +0000, Qais Yousef wrote:
> > Hi Pavan
> > 
> > On 03/02/20 13:27, Qais Yousef wrote:
> > > If a task was running on unfit CPU we could ignore migrating if the
> > > priority level of the new fitting CPU is the *same* as the unfit one.
> > > 
> > > Add an extra check to select_task_rq_rt() to allow the push in case:
> > > 
> > > 	* p->prio == new_cpu.highest_priority
> > > 	* task_fits(p, new_cpu)
> > > 
> > > Fixes: 804d402fb6f6 ("sched/rt: Make RT capacity-aware")
> > > Signed-off-by: Qais Yousef <qais.yousef@arm.com>
> > > ---
> > 
> > Can you please confirm if you have any objection to this patch? Without it
> > I see large delays in the 2 tasks test like I outlined in [1]. It wasn't clear
> > from [2] whether you are in agreement now or not.
> > 
> > [1] https://lore.kernel.org/lkml/20200217135306.cjc2225wdlwqiicu@e107158-lin.cambridge.arm.com/
> > [2] https://lore.kernel.org/lkml/20200227033608.GN28029@codeaurora.org/
> > 
> 
> I am not very sure about this. Like we discussed, this patch is addressing a
> specific scenario i.e two equal prio tasks waking at the same time. We allow
> the packing so that task_woken_rt() spread the tasks. The enqueue operation
> is waste here.
> 
> At the same time, I can't think of a better alternative. Retrying
> find_lowest_rq() may still give the same result until the previous task
> is fully woken on the CPU.
> 
> btw, the commit description does not talk about the race at all. If there is
> no race, we won't even end up in this scenario i.e find_lowest_rq() may simply
> return -1.

Josh has a new API that can help fix both the thundering herd issue and this
one too.

https://lore.kernel.org/lkml/20200311010113.136465-1-joshdon@google.com/

I did try to have a stab at it but my implementation wasn't as good as Josh.

I think if we get this function in and make find_lowest_rq() use it then we
should be okay when multiple tasks wakeup simultaneously. It's not bullet
proof, but good enough, me thinks.

Thoughts?

Thanks

--
Qais Yousef

Re: [PATCH v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Steven Rostedt]

On Mon,  2 Mar 2020 13:27:21 +0000
Qais Yousef <qais.yousef@arm.com> wrote:

> +			 * Don't bother moving it if the destination CPU is
> +			 * not running a lower priority task.
> +			 */
> +			if (p->prio < cpu_rq(target)->rt.highest_prio.curr) {
> +
> +				cpu = target;
> +
> +			} else if (p->prio == cpu_rq(target)->rt.highest_prio.curr) {
> +
> +				/*
> +				 * If the priority is the same and the new CPU
> +				 * is a better fit, then move, otherwise don't
> +				 * bother here either.
> +				 */
> +				if (fit_target)
> +					cpu = target;
> +			}

BTW, A little better algorithm would be to test fit_target first:

	target_prio = cpu_rq(target)->rt.hightest_prio.curr;
	if (p->prio < target_prio) {
		cpu = target;

	} else if (fit_target && p->prio == target_prio) {
		cpu = target;
	}

Which can also just be a single if statement:

	if (p->prio < target_prio ||
	    (fit_target && p->prio == target_prio)
		cpu = target;

-- Steve

Re: [PATCH v3 6/6] sched/rt: Fix pushing unfit tasks to a better CPU

[Qais Yousef]

On 03/11/20 10:00, Steven Rostedt wrote:
> On Mon,  2 Mar 2020 13:27:21 +0000
> Qais Yousef <qais.yousef@arm.com> wrote:
> 
> > +			 * Don't bother moving it if the destination CPU is
> > +			 * not running a lower priority task.
> > +			 */
> > +			if (p->prio < cpu_rq(target)->rt.highest_prio.curr) {
> > +
> > +				cpu = target;
> > +
> > +			} else if (p->prio == cpu_rq(target)->rt.highest_prio.curr) {
> > +
> > +				/*
> > +				 * If the priority is the same and the new CPU
> > +				 * is a better fit, then move, otherwise don't
> > +				 * bother here either.
> > +				 */
> > +				if (fit_target)
> > +					cpu = target;
> > +			}
> 
> BTW, A little better algorithm would be to test fit_target first:
> 
> 	target_prio = cpu_rq(target)->rt.hightest_prio.curr;
> 	if (p->prio < target_prio) {
> 		cpu = target;
> 
> 	} else if (fit_target && p->prio == target_prio) {
> 		cpu = target;
> 	}
> 
> Which can also just be a single if statement:
> 
> 	if (p->prio < target_prio ||
> 	    (fit_target && p->prio == target_prio)
> 		cpu = target;

Indeed.

We might have a better fix now if [1] goes in.

It'd fix the 'thundering herd' issue I mentioned before.
cpumask_any_and_distribute() should teach find_lowest_rq() to distribute tasks
that wakeup at the same time better. Hence fix the need to do the above.
It won't be bullet proof still, but neither the above is.

I'm sure there will be other places that can benefit from this distribution
function too.

Thanks!

--
Qais Yousef

[1] https://lore.kernel.org/lkml/20200311010113.136465-1-joshdon@google.com/