linux-kernel - Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency mask model

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20150803170911.GV25159@twins.programming.kicks-ass.net>
Date:	Mon, 3 Aug 2015 19:09:11 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Frederic Weisbecker <fweisbec@...il.com>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Preeti U Murthy <preeti@...ux.vnet.ibm.com>,
	Christoph Lameter <cl@...ux.com>,
	Ingo Molnar <mingo@...nel.org>,
	Viresh Kumar <viresh.kumar@...aro.org>,
	Rik van Riel <riel@...hat.com>
Subject: Re: [PATCH 07/10] sched: Migrate sched to use new tick dependency
 mask model

On Mon, Aug 03, 2015 at 04:50:33PM +0200, Frederic Weisbecker wrote:
> On Mon, Aug 03, 2015 at 04:00:46PM +0200, Peter Zijlstra wrote:
> > On Thu, Jul 23, 2015 at 06:42:12PM +0200, Frederic Weisbecker wrote:
> > > Instead of providing asynchronous checks for the nohz subsystem to verify
> > > sched tick dependency, migrate sched to the new mask.
> > > 
> > > The easiest is to recycle the current asynchronous tick dependency check
> > > which verifies the class of the current task and its requirements for
> > > periodic preemption checks.
> > > 
> > > We need to evaluate this tick dependency on three places:
> > > 
> > > 1) Task enqueue: One or more tasks have been enqueued, we must check
> > >    if those are competing with the current task.
> > > 
> > > 2) Task dequeue: A possibly competing task has been dequeued, clear the
> > >    tick dependency if needed.
> > > 
> > > 3) schedule(): we might be switching to a task of another scheduler
> > >    class. Each class has its preemption rules, we must re-evaluate it.
> > 
> > This is insane.. You add a whole bunch of work per wakeup/sleep/context
> > switch to avoid some work at tick time. That's a broken trade-off.
> > 
> > We can context switch _waaaay_ more than we have ticks.
> > 
> > Furthermore, you do tons of pointless work, we call add_nr_running()
> > from the individual classes, and then your routine goes and checks what
> > class we're in etc..
> 
> I think I could remove the context switch part. But then I need to find a
> way to perform these checks on enqueue and dequeue task time:

Uhm, but you already do!?

>   sched_update_dependency(cpu)
>   {
>       if (SCHED_FIFO task on the cpu runqueue) {
>           tick_nohz_clear_dep(cpu)
> 	  return;
>       }
> 
>       if (SCHED_RR task on the cpu runqueue) {
>           if (more than one such task) {
>               tick_nohz_set_dep(cpu)
> 	      return;
> 	  }
>       }
> 
>       if (SCHED_NORMAL task on the cpu runqueue) {
>           if (more than one such task) {
> 	      tick_nohz_set_dep(cpu)
> 	      return;
> 	  }
>       }
> 
>       tick_nohz_clear_dep();
>    }
> 
> That's still heavyweight because enqueue and dequeue can be very frequent
> but we get rid of the sched_switch hook because we don't care about the
> current task at all.
> 
> Now, consider that we could cut all this checks into parts and optimize
> that per sched class::enqueue/dequeue.

You can, seeing how {add,sub}_nr_running() is called from the individual
classes.

> So we can divide the dependency into:
> 
>          struct rq {
> 	     ...
> 	     int nr_fifo;
> 	     int nr_rr;

Those are currently summed together in: rq->rt.rt_nr_total, I suppose we
can split RR out.

> 	     int nr_normal;

That's called: rq->cfs.h_nr_running

But you've forgotten about SCHED_DEADLINE, we count those in:
rq->dl.dl_nr_running.

> 	}
> 
> 
> 	int rq_update_tick_dep(struct rq *rq)
> 	{
> 	     if (rq->nr_fifo && (rq->nr_rr > 1 || rq->nr_normal > 1))
> 	         tick_nohz_set_dep(SCHED_TICK_DEP);
>              else
> 	         tick_nohz_set_dep(SCHED_TICK_DEP)
>         }
> 
> Then we add or dec the relevant counter fields from the various
> sched_class::enqueue/dequeue.  I think I saw some of these counters
> already exist but perhaps not all of them. There are per class rqs but
> rt_nr_running counts tasks without distinction of policies.

Right. At which point you'll end up with:

	if (rq->dl.dl_nr_running > 1 || rq->rt.rr_nr_total > 1 || rq->cfs.h_nr_running > 1)
		tick_nohz_set_dep(SCHED_TICK_DEP)
	else
		tick_nohz_clear_dep(SCHED_TICK_DEP)

But I fear that'll still be rather expensive in some cases. Imagine a
case where we frequently flip between 1-2 tasks on the queue for any one
of those classes, then we'll do a whole bunch of dep flips, which is an
atomic op.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/