Re: [RFC PATCH 07/13] sched: Add core wide task selection and scheduling.

[Peter Zijlstra]

On Wed, Mar 04, 2020 at 04:59:57PM +0000, vpillai wrote:
> +static struct task_struct *
> +pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> +{
> +	struct task_struct *next, *max = NULL;
> +	const struct sched_class *class;
> +	const struct cpumask *smt_mask;
> +	int i, j, cpu;
> +	bool need_sync = false;

AFAICT that assignment is superfluous. Also, you violated the inverse
x-mas tree.

> +
> +	cpu = cpu_of(rq);
> +	if (cpu_is_offline(cpu))
> +		return idle_sched_class.pick_next_task(rq);

Are we actually hitting this one?

> +	if (!sched_core_enabled(rq))
> +		return __pick_next_task(rq, prev, rf);
> +
> +	/*
> +	 * If there were no {en,de}queues since we picked (IOW, the task
> +	 * pointers are all still valid), and we haven't scheduled the last
> +	 * pick yet, do so now.
> +	 */
> +	if (rq->core->core_pick_seq == rq->core->core_task_seq &&
> +	    rq->core->core_pick_seq != rq->core_sched_seq) {
> +		WRITE_ONCE(rq->core_sched_seq, rq->core->core_pick_seq);
> +
> +		next = rq->core_pick;
> +		if (next != prev) {
> +			put_prev_task(rq, prev);
> +			set_next_task(rq, next);
> +		}
> +		return next;
> +	}
> +
> +	prev->sched_class->put_prev_task(rq, prev);
> +	if (!rq->nr_running)
> +		newidle_balance(rq, rf);

This is wrong per commit:

  6e2df0581f56 ("sched: Fix pick_next_task() vs 'change' pattern race")

> +	smt_mask = cpu_smt_mask(cpu);
> +
> +	/*
> +	 * core->core_task_seq, core->core_pick_seq, rq->core_sched_seq
> +	 *
> +	 * @task_seq guards the task state ({en,de}queues)
> +	 * @pick_seq is the @task_seq we did a selection on
> +	 * @sched_seq is the @pick_seq we scheduled
> +	 *
> +	 * However, preemptions can cause multiple picks on the same task set.
> +	 * 'Fix' this by also increasing @task_seq for every pick.
> +	 */
> +	rq->core->core_task_seq++;
> +	need_sync = !!rq->core->core_cookie;
> +
> +	/* reset state */
> +	rq->core->core_cookie = 0UL;
> +	for_each_cpu(i, smt_mask) {
> +		struct rq *rq_i = cpu_rq(i);
> +
> +		rq_i->core_pick = NULL;
> +
> +		if (rq_i->core_forceidle) {
> +			need_sync = true;
> +			rq_i->core_forceidle = false;
> +		}
> +
> +		if (i != cpu)
> +			update_rq_clock(rq_i);
> +	}
> +
> +	/*
> +	 * Try and select tasks for each sibling in decending sched_class
> +	 * order.
> +	 */
> +	for_each_class(class) {
> +again:
> +		for_each_cpu_wrap(i, smt_mask, cpu) {
> +			struct rq *rq_i = cpu_rq(i);
> +			struct task_struct *p;
> +
> +			if (cpu_is_offline(i)) {
> +				rq_i->core_pick = rq_i->idle;
> +				continue;
> +			}

Why are we polluting the 'fast' path with offline crud? Why isn't this
the natural result of running pick_task() on an empty runqueue?

> +
> +			if (rq_i->core_pick)
> +				continue;
> +
> +			/*
> +			 * If this sibling doesn't yet have a suitable task to
> +			 * run; ask for the most elegible task, given the
> +			 * highest priority task already selected for this
> +			 * core.
> +			 */
> +			p = pick_task(rq_i, class, max);
> +			if (!p) {
> +				/*
> +				 * If there weren't no cookies; we don't need
> +				 * to bother with the other siblings.
> +				 */
> +				if (i == cpu && !need_sync)
> +					goto next_class;
> +
> +				continue;
> +			}
> +
> +			/*
> +			 * Optimize the 'normal' case where there aren't any
> +			 * cookies and we don't need to sync up.
> +			 */
> +			if (i == cpu && !need_sync && !p->core_cookie) {
> +				next = p;
> +				goto done;
> +			}
> +
> +			rq_i->core_pick = p;
> +
> +			/*
> +			 * If this new candidate is of higher priority than the
> +			 * previous; and they're incompatible; we need to wipe
> +			 * the slate and start over. pick_task makes sure that
> +			 * p's priority is more than max if it doesn't match
> +			 * max's cookie.
> +			 *
> +			 * NOTE: this is a linear max-filter and is thus bounded
> +			 * in execution time.
> +			 */
> +			if (!max || !cookie_match(max, p)) {
> +				struct task_struct *old_max = max;
> +
> +				rq->core->core_cookie = p->core_cookie;
> +				max = p;
> +
> +				if (old_max) {
> +					for_each_cpu(j, smt_mask) {
> +						if (j == i)
> +							continue;
> +
> +						cpu_rq(j)->core_pick = NULL;
> +					}
> +					goto again;
> +				} else {
> +					/*
> +					 * Once we select a task for a cpu, we
> +					 * should not be doing an unconstrained
> +					 * pick because it might starve a task
> +					 * on a forced idle cpu.
> +					 */
> +					need_sync = true;
> +				}
> +
> +			}
> +		}
> +next_class:;
> +	}
> +
> +	rq->core->core_pick_seq = rq->core->core_task_seq;
> +	next = rq->core_pick;
> +	rq->core_sched_seq = rq->core->core_pick_seq;
> +
> +	/*
> +	 * Reschedule siblings
> +	 *
> +	 * NOTE: L1TF -- at this point we're no longer running the old task and
> +	 * sending an IPI (below) ensures the sibling will no longer be running
> +	 * their task. This ensures there is no inter-sibling overlap between
> +	 * non-matching user state.
> +	 */
> +	for_each_cpu(i, smt_mask) {
> +		struct rq *rq_i = cpu_rq(i);
> +
> +		if (cpu_is_offline(i))
> +			continue;

Another one; please explain how an offline cpu can be part of the
smt_mask. Last time I checked it got cleared in stop-machine.

> +
> +		WARN_ON_ONCE(!rq_i->core_pick);
> +
> +		if (is_idle_task(rq_i->core_pick) && rq_i->nr_running)
> +			rq_i->core_forceidle = true;
> +
> +		if (i == cpu)
> +			continue;
> +
> +		if (rq_i->curr != rq_i->core_pick)
> +			resched_curr(rq_i);
> +
> +		/* Did we break L1TF mitigation requirements? */
> +		WARN_ON_ONCE(!cookie_match(next, rq_i->core_pick));

That comment is misleading...

> +	}
> +
> +done:
> +	set_next_task(rq, next);
> +	return next;
> +}

----8<----

> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index a9eeef896c78..8432de767730 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -4080,6 +4080,13 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  		update_min_vruntime(cfs_rq);
>  }
>  
> +static inline bool
> +__entity_slice_used(struct sched_entity *se)
> +{
> +	return (se->sum_exec_runtime - se->prev_sum_exec_runtime) >
> +		sched_slice(cfs_rq_of(se), se);
> +}
> +
>  /*
>   * Preempt the current task with a newly woken task if needed:
>   */
> @@ -10285,6 +10292,34 @@ static void core_sched_deactivate_fair(struct rq *rq)
>  #endif
>  #endif /* CONFIG_SMP */
>  
> +#ifdef CONFIG_SCHED_CORE
> +/*
> + * If runqueue has only one task which used up its slice and
> + * if the sibling is forced idle, then trigger schedule
> + * to give forced idle task a chance.
> + */
> +static void resched_forceidle_sibling(struct rq *rq, struct sched_entity *se)
> +{
> +	int cpu = cpu_of(rq), sibling_cpu;
> +	if (rq->cfs.nr_running > 1 || !__entity_slice_used(se))
> +		return;
> +
> +	for_each_cpu(sibling_cpu, cpu_smt_mask(cpu)) {
> +		struct rq *sibling_rq;
> +		if (sibling_cpu == cpu)
> +			continue;
> +		if (cpu_is_offline(sibling_cpu))
> +			continue;
> +
> +		sibling_rq = cpu_rq(sibling_cpu);
> +		if (sibling_rq->core_forceidle) {
> +			resched_curr(sibling_rq);
> +		}
> +	}
> +}
> +#endif
> +
> +
>  /*
>   * scheduler tick hitting a task of our scheduling class.
>   *
> @@ -10308,6 +10343,11 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
>  
>  	update_misfit_status(curr, rq);
>  	update_overutilized_status(task_rq(curr));
> +
> +#ifdef CONFIG_SCHED_CORE
> +	if (sched_core_enabled(rq))
> +		resched_forceidle_sibling(rq, &curr->se);
> +#endif
>  }
>  
>  /*

This ^ seems like it should be in it's own patch.

> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 03d502357599..a829e26fa43a 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1003,11 +1003,16 @@ struct rq {
>  #ifdef CONFIG_SCHED_CORE
>  	/* per rq */
>  	struct rq		*core;
> +	struct task_struct	*core_pick;
>  	unsigned int		core_enabled;
> +	unsigned int		core_sched_seq;
>  	struct rb_root		core_tree;
> +	bool			core_forceidle;

Someone forgot that _Bool shouldn't be part of composite types?

>  	/* shared state */
>  	unsigned int		core_task_seq;
> +	unsigned int		core_pick_seq;
> +	unsigned long		core_cookie;
>  #endif
>  };