Doubt about push_dl_task() / find_lock_later_rq()

Doubt about push_dl_task() / find_lock_later_rq()

[luca abeni]

Hi all,

trying to debug a reclaiming issue discovered by Daniel, I find myself
confused by the push logic... Maybe I am misunderstanding something
very obvious, so I ask here:

- push_dl_task() selects a task to be pushed, and then searches for a
  runqueue to push the task to by calling find_lock_later_rq()
- if I understand well, find_lock_later_rq() checks all the candidate
  runqueues for pushing, and then compares the deadline of the task
  with "dl.earliest_dl.curr" of the candidate runqueue, to check if
  pushing the task there makes sense or not
- now, my understanding is that in order to implement gEDF task T must
  be pushed on CPU C if the deadline of T is smaller than the earliest
  deadline of tasks on C... That is to say, the deadline of T must be
  smaller than the deadline of the task that is currently executing on
  C... No?
- But as far as I understand "dl.earliest_dl.curr" is the earliest
  deadline of _pushable_ tasks that are on the remote runqueue... That
  is to say, "earliest_dl.curr" does not consider the deadline of the
  task currently executing on the remote runqueue
- So, it seems to me that tasks are sometimes pushed to other runqueues
  even if they have a deadline that is not smaller than the deadline of
  the task executing on the "target" runqueue (so, a task is pushed but
  not immediately scheduled for execution). Is this correct? What is
  the logic behind this behaviour?
I would be tempted to say that the correct check is not
	dl_time_before(task->dl.deadline, later_rq->dl.earliest_dl.curr)
  (as it is now in find_lock_later_rq()), but
	dl_time_before(task->dl.deadline, later_rq->curr->dl.deadline)
This, in my view, would migrate a task only when it is going to preempt
the current of the remote runqueue. What am I missing?


			Thanks,
				Luca

Re: Doubt about push_dl_task() / find_lock_later_rq()

[luca abeni]

On Wed, 4 Jan 2017 15:49:35 +0100
luca abeni <luca.abeni@unitn.it> wrote:

> Hi all,
> 
> trying to debug a reclaiming issue discovered by Daniel, I find myself
> confused by the push logic... Maybe I am misunderstanding something
> very obvious, so I ask here:
> 
> - push_dl_task() selects a task to be pushed, and then searches for a
>   runqueue to push the task to by calling find_lock_later_rq()
> - if I understand well, find_lock_later_rq() checks all the candidate
>   runqueues for pushing, and then compares the deadline of the task
>   with "dl.earliest_dl.curr" of the candidate runqueue, to check if
>   pushing the task there makes sense or not
> - now, my understanding is that in order to implement gEDF task T must
>   be pushed on CPU C if the deadline of T is smaller than the earliest
>   deadline of tasks on C... That is to say, the deadline of T must be
>   smaller than the deadline of the task that is currently executing on
>   C... No?
> - But as far as I understand "dl.earliest_dl.curr" is the earliest
>   deadline of _pushable_ tasks that are on the remote runqueue...

So, after re-reading the code I now see that my understanding here was
wrong: "dl.earliest_dl.curr" is really supposed to be the deadline of
the earliest deadline task on the runqueue... So, if I do not play
with affinities it should be the deadline of the task that is currently
executing on that CPU.
So, everything is fine.


I was confused by the fact that in some cases I saw
rq->dl.earliest_dl.curr != rq->curr->dl.deadline

I still do not understand how this can happen (I am not changing tasks
affinities), and I am investigating this.


			Thanks,
				Luca

> That
>   is to say, "earliest_dl.curr" does not consider the deadline of the
>   task currently executing on the remote runqueue
> - So, it seems to me that tasks are sometimes pushed to other
> runqueues even if they have a deadline that is not smaller than the
> deadline of the task executing on the "target" runqueue (so, a task
> is pushed but not immediately scheduled for execution). Is this
> correct? What is the logic behind this behaviour?
> I would be tempted to say that the correct check is not
> 	dl_time_before(task->dl.deadline,
> later_rq->dl.earliest_dl.curr) (as it is now in
> find_lock_later_rq()), but dl_time_before(task->dl.deadline,
> later_rq->curr->dl.deadline) This, in my view, would migrate a task
> only when it is going to preempt the current of the remote runqueue.
> What am I missing?
> 
> 
> 			Thanks,
> 				Luca

Re: Doubt about push_dl_task() / find_lock_later_rq()

[Peter Zijlstra]

On Thu, Jan 05, 2017 at 08:29:23AM +0100, luca abeni wrote:
> On Wed, 4 Jan 2017 15:49:35 +0100
> luca abeni <luca.abeni@unitn.it> wrote:
> 
> > Hi all,
> > 
> > trying to debug a reclaiming issue discovered by Daniel, I find myself
> > confused by the push logic... Maybe I am misunderstanding something
> > very obvious, so I ask here:
> > 
> > - push_dl_task() selects a task to be pushed, and then searches for a
> >   runqueue to push the task to by calling find_lock_later_rq()
> > - if I understand well, find_lock_later_rq() checks all the candidate
> >   runqueues for pushing, and then compares the deadline of the task
> >   with "dl.earliest_dl.curr" of the candidate runqueue, to check if
> >   pushing the task there makes sense or not
> > - now, my understanding is that in order to implement gEDF task T must
> >   be pushed on CPU C if the deadline of T is smaller than the earliest
> >   deadline of tasks on C... That is to say, the deadline of T must be
> >   smaller than the deadline of the task that is currently executing on
> >   C... No?
> > - But as far as I understand "dl.earliest_dl.curr" is the earliest
> >   deadline of _pushable_ tasks that are on the remote runqueue...
> 
> So, after re-reading the code I now see that my understanding here was
> wrong: "dl.earliest_dl.curr" is really supposed to be the deadline of
> the earliest deadline task on the runqueue... So, if I do not play
> with affinities it should be the deadline of the task that is currently
> executing on that CPU.
> So, everything is fine.

Right, that's what I remember.

> 
> I was confused by the fact that in some cases I saw
> rq->dl.earliest_dl.curr != rq->curr->dl.deadline
> 
> I still do not understand how this can happen (I am not changing tasks
> affinities), and I am investigating this.


I'm having trouble spotting code that does that...

Re: Doubt about push_dl_task() / find_lock_later_rq()

[luca abeni]

On Thu, 5 Jan 2017 12:48:38 +0100
Peter Zijlstra <peterz@infradead.org> wrote:

> On Thu, Jan 05, 2017 at 08:29:23AM +0100, luca abeni wrote:
[...]
> > I was confused by the fact that in some cases I saw
> > rq->dl.earliest_dl.curr != rq->curr->dl.deadline
> > 
> > I still do not understand how this can happen (I am not changing
> > tasks affinities), and I am investigating this.  
> 
> 
> I'm having trouble spotting code that does that...

I think I might have found the issue (switched_to_dl() adjusting the
task's deadline without dequeueing/re-enqueueing it)... I am working on
a patch, and I'll send it this afternoon.


			Thanks,
				Luca