Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1376155 > unrolled thread

Re: [PATCH net-next 2/2] net: exit busy loop when another process is runnable

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH net-next 2/2] net: exit busy loop when another process is  runnable "Michael S. Tsirkin" <mst@redhat.com> - 2016-04-11 18:40 +0200
    Re: [PATCH net-next 2/2] net: exit busy loop when another process is  runnable Ingo Molnar <mingo@kernel.org> - 2016-04-13 09:30 +0200
    Re: [PATCH net-next 2/2] net: exit busy loop when another process is  runnable Peter Zijlstra <peterz@infradead.org> - 2016-04-13 15:30 +0200
      Re: [PATCH net-next 2/2] net: exit busy loop when another process is  runnable "Michael S. Tsirkin" <mst@redhat.com> - 2016-04-13 16:00 +0200
        Re: [PATCH net-next 2/2] net: exit busy loop when another process is  runnable Peter Zijlstra <peterz@infradead.org> - 2016-04-14 17:30 +0200

#1376155 — Re: [PATCH net-next 2/2] net: exit busy loop when another process is runnable

On Fri, Aug 22, 2014 at 09:36:53AM +0200, Ingo Molnar wrote:
> 
> > > diff --git a/include/net/busy_poll.h b/include/net/busy_poll.h
> > > index 1d67fb6..8a33fb2 100644
> > > --- a/include/net/busy_poll.h
> > > +++ b/include/net/busy_poll.h
> > > @@ -109,7 +109,8 @@ static inline bool sk_busy_loop(struct sock *sk, int nonblock)
> > >  		cpu_relax();
> > >  
> > >  	} while (!nonblock && skb_queue_empty(&sk->sk_receive_queue) &&
> > > -		 !need_resched() && !busy_loop_timeout(end_time));
> > > +		 !need_resched() && !busy_loop_timeout(end_time) &&
> > > +		 nr_running_this_cpu() < 2);
> 
> So it's generally a bad idea to couple to the scheduler through 
> such a low level, implementation dependent value like 
> 'nr_running', causing various problems:
> 
>  - It misses important work that might be pending on this CPU,
>    like RCU callbacks.
> 
>  - It will also over-credit task contexts that might be
>    runnable, but which are less important than the currently
>    running one: such as a SCHED_IDLE task
> 
>  - It will also over-credit even regular SCHED_NORMAL tasks, if
>    this current task is more important than them: say
>    SCHED_FIFO. A SCHED_FIFO workload should run just as fast 
>    with SCHED_NORMAL tasks around, as a SCHED_NORMAL workload 
>    on an otherwise idle system.
> 
> So what you want is a more sophisticated query to the 
> scheduler, a sched_expected_runtime() method that returns the 
> number of nsecs this task is expected to run in the future, 
> which returns 0 if you will be scheduled away on the next 
> schedule(), and returns infinity for a high prio SCHED_FIFO 
> task, or if this SCHED_NORMAL task is on an otherwise idle CPU.
> 
> It will return a regular time slice value in other cases, when 
> there's some load on the CPU.
> 
> The polling logic can then do its decision based on that time 
> value.
> 
> All this can be done reasonably fast and lockless in most 
> cases, so that it can be called from busy-polling code.
>
> An added advantage would be that this approach consolidates the 
> somewhat random need_resched() checks into this method as well.
> 
> In any case I don't agree with the nr_running_this_cpu() 
> method.
> 
> (Please Cc: me and lkml to future iterations of this patchset.)
> 
> Thanks,
> 
> 	Ingo

I tried to look into this: it might be even nicer to add
sched_expected_to_run(time) which tells us whether we expect the current
task to keep running for the next XX nsecs.

For the fair scheduler, it seems that it could be as simple as

+static bool expected_to_run_fair(struct cfs_rq *cfs_rq, s64 t)
+{
+       struct sched_entity *left;
+       struct sched_entity *curr = cfs_rq->curr;
+
+       if (!curr || !curr->on_rq)
+               return false;
+
+       left = __pick_first_entity(cfs_rq);
+       if (!left)
+               return true;
+
+       return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
+                    left->vruntime) < 0;
+}

The reason it seems easier is because that way we can reuse
calc_delta_fair and don't have to do the reverse translation
from vruntime to nsec.

And I guess if we do this with interrupts disabled, and only poke
at the current CPU's rq, we know first entity
won't go away so we don't need locks? 

Is this close to what you had in mind?

Thanks,

-- 
MST

[toc] | [next] | [standalone]

#1377595

* Michael S. Tsirkin <mst@redhat.com> wrote:

> On Fri, Aug 22, 2014 at 09:36:53AM +0200, Ingo Molnar wrote:
> > 
> > > > diff --git a/include/net/busy_poll.h b/include/net/busy_poll.h
> > > > index 1d67fb6..8a33fb2 100644
> > > > --- a/include/net/busy_poll.h
> > > > +++ b/include/net/busy_poll.h
> > > > @@ -109,7 +109,8 @@ static inline bool sk_busy_loop(struct sock *sk, int nonblock)
> > > >  		cpu_relax();
> > > >  
> > > >  	} while (!nonblock && skb_queue_empty(&sk->sk_receive_queue) &&
> > > > -		 !need_resched() && !busy_loop_timeout(end_time));
> > > > +		 !need_resched() && !busy_loop_timeout(end_time) &&
> > > > +		 nr_running_this_cpu() < 2);
> > 
> > So it's generally a bad idea to couple to the scheduler through 
> > such a low level, implementation dependent value like 
> > 'nr_running', causing various problems:
> > 
> >  - It misses important work that might be pending on this CPU,
> >    like RCU callbacks.
> > 
> >  - It will also over-credit task contexts that might be
> >    runnable, but which are less important than the currently
> >    running one: such as a SCHED_IDLE task
> > 
> >  - It will also over-credit even regular SCHED_NORMAL tasks, if
> >    this current task is more important than them: say
> >    SCHED_FIFO. A SCHED_FIFO workload should run just as fast 
> >    with SCHED_NORMAL tasks around, as a SCHED_NORMAL workload 
> >    on an otherwise idle system.
> > 
> > So what you want is a more sophisticated query to the 
> > scheduler, a sched_expected_runtime() method that returns the 
> > number of nsecs this task is expected to run in the future, 
> > which returns 0 if you will be scheduled away on the next 
> > schedule(), and returns infinity for a high prio SCHED_FIFO 
> > task, or if this SCHED_NORMAL task is on an otherwise idle CPU.
> > 
> > It will return a regular time slice value in other cases, when 
> > there's some load on the CPU.
> > 
> > The polling logic can then do its decision based on that time 
> > value.
> > 
> > All this can be done reasonably fast and lockless in most 
> > cases, so that it can be called from busy-polling code.
> >
> > An added advantage would be that this approach consolidates the 
> > somewhat random need_resched() checks into this method as well.
> > 
> > In any case I don't agree with the nr_running_this_cpu() 
> > method.
> > 
> > (Please Cc: me and lkml to future iterations of this patchset.)
> > 
> > Thanks,
> > 
> > 	Ingo
> 
> I tried to look into this: it might be even nicer to add
> sched_expected_to_run(time) which tells us whether we expect the current
> task to keep running for the next XX nsecs.
> 
> For the fair scheduler, it seems that it could be as simple as
> 
> +static bool expected_to_run_fair(struct cfs_rq *cfs_rq, s64 t)
> +{
> +       struct sched_entity *left;
> +       struct sched_entity *curr = cfs_rq->curr;
> +
> +       if (!curr || !curr->on_rq)
> +               return false;
> +
> +       left = __pick_first_entity(cfs_rq);
> +       if (!left)
> +               return true;
> +
> +       return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
> +                    left->vruntime) < 0;
> +}
> 
> The reason it seems easier is because that way we can reuse
> calc_delta_fair and don't have to do the reverse translation
> from vruntime to nsec.
> 
> And I guess if we do this with interrupts disabled, and only poke
> at the current CPU's rq, we know first entity
> won't go away so we don't need locks? 
> 
> Is this close to what you had in mind?

Yeah, fair enough ;-)

I'm not 100% convinced about the interface, but the model looks good to me.
Let's try it - I don't have fundamental objections anymore.

I also agree that it could be done lockless - although I'd suggest two steps: 
first do the dumb thing with the proper scheduler lock(s) held, then another patch 
which removes the locks for a bit more performance. That will make any subtle 
crashes/races bisectable.

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1377926

On Mon, Apr 11, 2016 at 07:31:57PM +0300, Michael S. Tsirkin wrote:
> +static bool expected_to_run_fair(struct cfs_rq *cfs_rq, s64 t)
> +{
> +       struct sched_entity *left;
> +       struct sched_entity *curr = cfs_rq->curr;
> +
> +       if (!curr || !curr->on_rq)
> +               return false;
> +
> +       left = __pick_first_entity(cfs_rq);
> +       if (!left)
> +               return true;
> +
> +       return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
> +                    left->vruntime) < 0;
> +}
> 
> The reason it seems easier is because that way we can reuse
> calc_delta_fair and don't have to do the reverse translation
> from vruntime to nsec.
> 
> And I guess if we do this with interrupts disabled, and only poke
> at the current CPU's rq, we know first entity
> won't go away so we don't need locks? 

Nope, not true. Current isn't actually in the tree, and any other task
is subject to being moved at any time.

Even if current was in the tree, there is no guarantee it is
->rb_leftmost; imagine a task being migrated in that has a smaller
vruntime.

So this really cannot work without locks :/

I've not thought about the actual problem you're trying to solve; but I
figured I'd let you know this before you continue down this path.

[toc] | [prev] | [next] | [standalone]

#1377969

On Wed, Apr 13, 2016 at 03:28:03PM +0200, Peter Zijlstra wrote:
> On Mon, Apr 11, 2016 at 07:31:57PM +0300, Michael S. Tsirkin wrote:
> > +static bool expected_to_run_fair(struct cfs_rq *cfs_rq, s64 t)
> > +{
> > +       struct sched_entity *left;
> > +       struct sched_entity *curr = cfs_rq->curr;
> > +
> > +       if (!curr || !curr->on_rq)
> > +               return false;
> > +
> > +       left = __pick_first_entity(cfs_rq);
> > +       if (!left)
> > +               return true;
> > +
> > +       return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
> > +                    left->vruntime) < 0;
> > +}
> > 
> > The reason it seems easier is because that way we can reuse
> > calc_delta_fair and don't have to do the reverse translation
> > from vruntime to nsec.
> > 
> > And I guess if we do this with interrupts disabled, and only poke
> > at the current CPU's rq, we know first entity
> > won't go away so we don't need locks? 
> 
> Nope, not true. Current isn't actually in the tree, and any other task
> is subject to being moved at any time.
> Even if current was in the tree, there is no guarantee it is
> ->rb_leftmost; imagine a task being migrated in that has a smaller
> vruntime.
> 
> So this really cannot work without locks :/
> 
> I've not thought about the actual problem you're trying to solve; but I
> figured I'd let you know this before you continue down this path.

Hmm. This is in fact called in the context of a given task,
so maybe I should just change the API and use
	&task->se
instead of 
	cfs_rq->current

:

static bool expected_to_run_fair(struct cfs_rq *cfs_rq, struct task_struct *task, s64 t)
{
       struct sched_entity *left;
       struct sched_entity *curr = &task->se;
       if (!curr || !curr->on_rq)
              return false;

       left = __pick_first_entity(cfs_rq);
       if (!left)
               return true;

       return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
                    left->vruntime) < 0;
}

This way it is caller's respinsibility to make sure task
is not going away.
Left here is on tree so it's not going away, right?

-- 
MST

[toc] | [prev] | [next] | [standalone]

#1379020

On Wed, Apr 13, 2016 at 04:51:36PM +0300, Michael S. Tsirkin wrote:
> On Wed, Apr 13, 2016 at 03:28:03PM +0200, Peter Zijlstra wrote:

> > Nope, not true. Current isn't actually in the tree, and any other task
> > is subject to being moved at any time.
> > Even if current was in the tree, there is no guarantee it is
> > ->rb_leftmost; imagine a task being migrated in that has a smaller
> > vruntime.
> > 
> > So this really cannot work without locks :/
> > 
> > I've not thought about the actual problem you're trying to solve; but I
> > figured I'd let you know this before you continue down this path.

> static bool expected_to_run_fair(struct cfs_rq *cfs_rq, struct task_struct *task, s64 t)
> {
>        struct sched_entity *left;
>        struct sched_entity *curr = &task->se;
>        if (!curr || !curr->on_rq)
>               return false;
> 
>        left = __pick_first_entity(cfs_rq);
>        if (!left)
>                return true;
> 
>        return (s64)(curr->vruntime + calc_delta_fair(t, curr) -
>                     left->vruntime) < 0;
> }
> 
> Left here is on tree so it's not going away, right?

No, left is the leftmost entry on the tree, it can go away at any time.
You cannot touch the tree without locks.

Someone can come an migrate the task to another CPU, start executing it
and it can die between you finding the left pointer and dereferencing
it.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web