[PATCH 1/2] sched/dl: Implement cancel_dl_timer() to use in switched_from_dl()

[PATCH 1/2] sched/dl: Implement cancel_dl_timer() to use in switched_from_dl()

[Kirill Tkhai]

From: Kirill Tkhai <ktkhai@parallels.com>

hrtimer_try_to_cancel() may bring a suprise, and even two its calls
may fail.

So, let's implement 100% guaranteed way to cancel the timer and let's
be sure we are safe even in very unlikely situations.

We do not create any problem with rq unlocking, because it already
may happed below in pull_dl_task(). No problem with deadline tasks
balancing too.

Signed-off-by: Kirill Tkhai <ktkhai@parallels.com>
---
 kernel/sched/deadline.c |   33 ++++++++++++++++++++++++++-------
 1 file changed, 26 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index abfaf3d..63f8b4a 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -555,11 +555,6 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 {
 	struct hrtimer *timer = &dl_se->dl_timer;
 
-	if (hrtimer_active(timer)) {
-		hrtimer_try_to_cancel(timer);
-		return;
-	}
-
 	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 	timer->function = dl_task_timer;
 }
@@ -1567,10 +1562,34 @@ void init_sched_dl_class(void)
 
 #endif /* CONFIG_SMP */
 
+/*
+ *  Surely cancel task's dl_timer. May drop rq->lock.
+ */
+static void cancel_dl_timer(struct rq *rq, struct task_struct *p)
+{
+	struct hrtimer *dl_timer = &p->dl.dl_timer;
+
+	/* Nobody will change task's class if pi_lock is held */
+	lockdep_assert_held(&p->pi_lock);
+
+	if (hrtimer_active(dl_timer)) {
+		int ret = hrtimer_try_to_cancel(dl_timer);
+
+		if (unlikely(ret == -1)) {
+			/*
+			 * Note, p may migrate OR new deadline tasks
+			 * may appear in rq when we are unlocking it.
+			 */
+			raw_spin_unlock(&rq->lock);
+			hrtimer_cancel(dl_timer);
+			raw_spin_lock(&rq->lock);
+		}
+	}
+}
+
 static void switched_from_dl(struct rq *rq, struct task_struct *p)
 {
-	if (hrtimer_active(&p->dl.dl_timer) && !dl_policy(p->policy))
-		hrtimer_try_to_cancel(&p->dl.dl_timer);
+	cancel_dl_timer(rq, p);
 
 	__dl_clear_params(p);
 

[PATCH 2/2] sched/dl: Cleanup prio_changed_dl()

[Kirill Tkhai]

From: Kirill Tkhai <ktkhai@parallels.com>

Now rq->curr task can't be dequeued in this function
(it's possible only in __schedule()).

Also, delete "else" branch which is dead code.

Signed-off-by: Kirill Tkhai <ktkhai@parallels.com>
---
 kernel/sched/deadline.c |   50 +++++++++++++++++++++++------------------------
 1 file changed, 24 insertions(+), 26 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 63f8b4a..38b4f19 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1638,35 +1638,33 @@ static void switched_to_dl(struct rq *rq, struct task_struct *p)
 static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 			    int oldprio)
 {
-	if (task_on_rq_queued(p) || rq->curr == p) {
+	if (!task_on_rq_queued(p))
+		return;
 #ifdef CONFIG_SMP
-		/*
-		 * This might be too much, but unfortunately
-		 * we don't have the old deadline value, and
-		 * we can't argue if the task is increasing
-		 * or lowering its prio, so...
-		 */
-		if (!rq->dl.overloaded)
-			pull_dl_task(rq);
-
-		/*
-		 * If we now have a earlier deadline task than p,
-		 * then reschedule, provided p is still on this
-		 * runqueue.
-		 */
-		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
-		    rq->curr == p)
-			resched_curr(rq);
-#else
-		/*
-		 * Again, we don't know if p has a earlier
-		 * or later deadline, so let's blindly set a
-		 * (maybe not needed) rescheduling point.
-		 */
+	/*
+	 * This might be too much, but unfortunately
+	 * we don't have the old deadline value, and
+	 * we can't argue if the task is increasing
+	 * or lowering its prio, so...
+	 */
+	if (!rq->dl.overloaded)
+		pull_dl_task(rq);
+	/*
+	 * If we now have a earlier deadline task than p,
+	 * then reschedule, provided p is still on this
+	 * runqueue.
+	 */
+	if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
+	    rq->curr == p)
 		resched_curr(rq);
+#else
+	/*
+	 * Again, we don't know if p has a earlier
+	 * or later deadline, so let's blindly set a
+	 * (maybe not needed) rescheduling point.
+	 */
+	resched_curr(rq);
 #endif /* CONFIG_SMP */
-	} else
-		switched_to_dl(rq, p);
 }
 
 const struct sched_class dl_sched_class = {

Re: [PATCH 1/2] sched/dl: Implement cancel_dl_timer() to use in switched_from_dl()

[Juri Lelli]

Hi Kirill,

On 27/09/14 09:40, Kirill Tkhai wrote:
> From: Kirill Tkhai <ktkhai@parallels.com>
> 
> hrtimer_try_to_cancel() may bring a suprise, and even two its calls
> may fail.
> 
> So, let's implement 100% guaranteed way to cancel the timer and let's
> be sure we are safe even in very unlikely situations.
> 

Could you give more details about the unlikely situations in the
changelog? It would be nice to have some more information for future
reference.

Thanks,

- Juri

> We do not create any problem with rq unlocking, because it already
> may happed below in pull_dl_task(). No problem with deadline tasks
> balancing too.
> 
> Signed-off-by: Kirill Tkhai <ktkhai@parallels.com>
> ---
>  kernel/sched/deadline.c |   33 ++++++++++++++++++++++++++-------
>  1 file changed, 26 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index abfaf3d..63f8b4a 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -555,11 +555,6 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
>  {
>  	struct hrtimer *timer = &dl_se->dl_timer;
>  
> -	if (hrtimer_active(timer)) {
> -		hrtimer_try_to_cancel(timer);
> -		return;
> -	}
> -
>  	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
>  	timer->function = dl_task_timer;
>  }
> @@ -1567,10 +1562,34 @@ void init_sched_dl_class(void)
>  
>  #endif /* CONFIG_SMP */
>  
> +/*
> + *  Surely cancel task's dl_timer. May drop rq->lock.
> + */
> +static void cancel_dl_timer(struct rq *rq, struct task_struct *p)
> +{
> +	struct hrtimer *dl_timer = &p->dl.dl_timer;
> +
> +	/* Nobody will change task's class if pi_lock is held */
> +	lockdep_assert_held(&p->pi_lock);
> +
> +	if (hrtimer_active(dl_timer)) {
> +		int ret = hrtimer_try_to_cancel(dl_timer);
> +
> +		if (unlikely(ret == -1)) {
> +			/*
> +			 * Note, p may migrate OR new deadline tasks
> +			 * may appear in rq when we are unlocking it.
> +			 */
> +			raw_spin_unlock(&rq->lock);
> +			hrtimer_cancel(dl_timer);
> +			raw_spin_lock(&rq->lock);
> +		}
> +	}
> +}
> +
>  static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  {
> -	if (hrtimer_active(&p->dl.dl_timer) && !dl_policy(p->policy))
> -		hrtimer_try_to_cancel(&p->dl.dl_timer);
> +	cancel_dl_timer(rq, p);
>  
>  	__dl_clear_params(p);
>  
> 
> 

Re: [PATCH 2/2] sched/dl: Cleanup prio_changed_dl()

[Juri Lelli]

Hi Kirill,

On 27/09/14 09:41, Kirill Tkhai wrote:
> From: Kirill Tkhai <ktkhai@parallels.com>
> 
> Now rq->curr task can't be dequeued in this function
> (it's possible only in __schedule()).
> 

Could you please detail about "before", with a reference to the commit
that made this further change necessary?

Thanks a lot,

- Juri

> Also, delete "else" branch which is dead code.
> 
> Signed-off-by: Kirill Tkhai <ktkhai@parallels.com>
> ---
>  kernel/sched/deadline.c |   50 +++++++++++++++++++++++------------------------
>  1 file changed, 24 insertions(+), 26 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 63f8b4a..38b4f19 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1638,35 +1638,33 @@ static void switched_to_dl(struct rq *rq, struct task_struct *p)
>  static void prio_changed_dl(struct rq *rq, struct task_struct *p,
>  			    int oldprio)
>  {
> -	if (task_on_rq_queued(p) || rq->curr == p) {
> +	if (!task_on_rq_queued(p))
> +		return;
>  #ifdef CONFIG_SMP
> -		/*
> -		 * This might be too much, but unfortunately
> -		 * we don't have the old deadline value, and
> -		 * we can't argue if the task is increasing
> -		 * or lowering its prio, so...
> -		 */
> -		if (!rq->dl.overloaded)
> -			pull_dl_task(rq);
> -
> -		/*
> -		 * If we now have a earlier deadline task than p,
> -		 * then reschedule, provided p is still on this
> -		 * runqueue.
> -		 */
> -		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
> -		    rq->curr == p)
> -			resched_curr(rq);
> -#else
> -		/*
> -		 * Again, we don't know if p has a earlier
> -		 * or later deadline, so let's blindly set a
> -		 * (maybe not needed) rescheduling point.
> -		 */
> +	/*
> +	 * This might be too much, but unfortunately
> +	 * we don't have the old deadline value, and
> +	 * we can't argue if the task is increasing
> +	 * or lowering its prio, so...
> +	 */
> +	if (!rq->dl.overloaded)
> +		pull_dl_task(rq);
> +	/*
> +	 * If we now have a earlier deadline task than p,
> +	 * then reschedule, provided p is still on this
> +	 * runqueue.
> +	 */
> +	if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
> +	    rq->curr == p)
>  		resched_curr(rq);
> +#else
> +	/*
> +	 * Again, we don't know if p has a earlier
> +	 * or later deadline, so let's blindly set a
> +	 * (maybe not needed) rescheduling point.
> +	 */
> +	resched_curr(rq);
>  #endif /* CONFIG_SMP */
> -	} else
> -		switched_to_dl(rq, p);
>  }
>  
>  const struct sched_class dl_sched_class = {
> 
> 

Re: [PATCH 2/2] sched/dl: Cleanup prio_changed_dl()

[Kirill Tkhai]

29.09.2014, 19:03, "Juri Lelli" <juri.lelli@arm.com>:
> Hi Kirill,
>
> On 27/09/14 09:41, Kirill Tkhai wrote:
>>  From: Kirill Tkhai <ktkhai@parallels.com>
>>
>>  Now rq->curr task can't be dequeued in this function
>>  (it's possible only in __schedule()).
>
> Could you please detail about "before", with a reference to the commit
> that made this further change necessary?

I wrote about unlocked context switching, but I've looked one more time
and found that it used to be impossible before too.

We set "rq->curr = next" before prepare_lock_switch(),
so dequeued task wasn't able to be curr.

I'll update both descriptions in v2.

Thanks,
Kirill

>
> Thanks a lot,
>
> - Juri
>>  Also, delete "else" branch which is dead code.
>>
>>  Signed-off-by: Kirill Tkhai <ktkhai@parallels.com>
>>  ---
>>   kernel/sched/deadline.c |   50 +++++++++++++++++++++++------------------------
>>   1 file changed, 24 insertions(+), 26 deletions(-)
>>
>>  diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>>  index 63f8b4a..38b4f19 100644
>>  --- a/kernel/sched/deadline.c
>>  +++ b/kernel/sched/deadline.c
>>  @@ -1638,35 +1638,33 @@ static void switched_to_dl(struct rq *rq, struct task_struct *p)
>>   static void prio_changed_dl(struct rq *rq, struct task_struct *p,
>>                               int oldprio)
>>   {
>>  - if (task_on_rq_queued(p) || rq->curr == p) {
>>  + if (!task_on_rq_queued(p))
>>  + return;
>>   #ifdef CONFIG_SMP
>>  - /*
>>  - * This might be too much, but unfortunately
>>  - * we don't have the old deadline value, and
>>  - * we can't argue if the task is increasing
>>  - * or lowering its prio, so...
>>  - */
>>  - if (!rq->dl.overloaded)
>>  - pull_dl_task(rq);
>>  -
>>  - /*
>>  - * If we now have a earlier deadline task than p,
>>  - * then reschedule, provided p is still on this
>>  - * runqueue.
>>  - */
>>  - if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
>>  -    rq->curr == p)
>>  - resched_curr(rq);
>>  -#else
>>  - /*
>>  - * Again, we don't know if p has a earlier
>>  - * or later deadline, so let's blindly set a
>>  - * (maybe not needed) rescheduling point.
>>  - */
>>  + /*
>>  + * This might be too much, but unfortunately
>>  + * we don't have the old deadline value, and
>>  + * we can't argue if the task is increasing
>>  + * or lowering its prio, so...
>>  + */
>>  + if (!rq->dl.overloaded)
>>  + pull_dl_task(rq);
>>  + /*
>>  + * If we now have a earlier deadline task than p,
>>  + * then reschedule, provided p is still on this
>>  + * runqueue.
>>  + */
>>  + if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
>>  +    rq->curr == p)
>>                   resched_curr(rq);
>>  +#else
>>  + /*
>>  + * Again, we don't know if p has a earlier
>>  + * or later deadline, so let's blindly set a
>>  + * (maybe not needed) rescheduling point.
>>  + */
>>  + resched_curr(rq);
>>   #endif /* CONFIG_SMP */
>>  - } else
>>  - switched_to_dl(rq, p);
>>   }
>>
>>   const struct sched_class dl_sched_class = {