sched/deadline: fix try to pull pinned dl tasks in pull algorithm

It's a bootstrap function, make init_sched_dl_class() __init.

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

kernel/sched/deadline.c +1 -1

index b57ceba..3bd3158 100644
@@ -1686,7 +1686,7 @@ static void rq_offline_dl(struct rq *rq)
 	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
 }
 
-void init_sched_dl_class(void)
+void __init init_sched_dl_class(void)
 {
 	unsigned int i;
 

Hi,

Quoted 2 lines · Wanpeng Li

It's a bootstrap function, make init_sched_dl_class() __init.

Looks good, thanks!

Best,

- Juri

Quoted 19 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

kernel/sched/deadline.c +1 -1

index b57ceba..3bd3158 100644
@@ -1686,7 +1686,7 @@ static void rq_offline_dl(struct rq *rq)
 	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
 }
 
-void init_sched_dl_class(void)
+void __init init_sched_dl_class(void)
 {
 	unsigned int i;
 

This patch adds check that prevents futile attempts to move dl tasks to a CPU with active tasks of equal or earlier deadline. The same behavior as commit 80e3d87b2c55 ("sched/rt: Reduce rq lock contention by eliminating locking of non-feasible target") for rt class.

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +3 -1

index 3bd3158..b8b9355 100644
@@ -1012,7 +1012,9 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
 	    (p->nr_cpus_allowed > 1)) {
 		int target = find_later_rq(p);
 
-		if (target != -1)
+		if (target != -1 &&
+			dl_time_before(p->dl.deadline,
+				cpu_rq(target)->dl.earliest_dl.curr))
 			cpu = target;
 	}
 	rcu_read_unlock();

Hi,

Quoted 5 lines · Wanpeng Li

This patch adds check that prevents futile attempts to move dl tasks to a CPU with active tasks of equal or earlier deadline. The same behavior as commit 80e3d87b2c55 ("sched/rt: Reduce rq lock contention by eliminating locking of non-feasible target") for rt class.

This commit introduced also this kind of check in find_lock_lowest_rq(). Don't we need something like this in find_lock_later_rq() as well?

Thanks,

- Juri

Quoted 21 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +3 -1

index 3bd3158..b8b9355 100644
@@ -1012,7 +1012,9 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
 	    (p->nr_cpus_allowed > 1)) {
 		int target = find_later_rq(p);
 
-		if (target != -1)
+		if (target != -1 &&
+			dl_time_before(p->dl.deadline,
+				cpu_rq(target)->dl.earliest_dl.curr))
 			cpu = target;
 	}
 	rcu_read_unlock();

pull_dl_task can drop (and re-acquire) rq->lock, this means a stop task can slip in, in which case we need to reschedule. This patch add the reschedule when the scenario occurs.

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +15 -1

index b8b9355..844da0f 100644
@@ -1739,7 +1739,13 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
 		return;
 
-	if (pull_dl_task(rq))
+	/*
+	 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+	 * means a stop task can slip in, in which case we need to
+	 * reschedule.
+	 */
+	if (pull_dl_task(rq) ||
+		(rq->stop && task_on_rq_queued(rq->stop)))
 		resched_curr(rq);
 }
 

@@ -1786,6 +1792,14 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 			pull_dl_task(rq);
 
 		/*
+		 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+		 * means a stop task can slip in, in which case we need to
+		 * reschedule.
+		 */
+		if (rq->stop && task_on_rq_queued(rq->stop))
+			resched_curr(rq);
+
+		/*
 		 * If we now have a earlier deadline task than p,
 		 * then reschedule, provided p is still on this
 		 * runqueue.

Hi,

Quoted 4 lines · Wanpeng Li

pull_dl_task can drop (and re-acquire) rq->lock, this means a stop task can slip in, in which case we need to reschedule. This patch add the reschedule when the scenario occurs.

Ok, I guess it can happen. Doesn't RT have the same problem? It seems that it also has to deal with DL tasks slipping in, right?

Thanks,

- Juri

Quoted 40 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +15 -1

index b8b9355..844da0f 100644
@@ -1739,7 +1739,13 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
 		return;
 
-	if (pull_dl_task(rq))
+	/*
+	 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+	 * means a stop task can slip in, in which case we need to
+	 * reschedule.
+	 */
+	if (pull_dl_task(rq) ||
+		(rq->stop && task_on_rq_queued(rq->stop)))
 		resched_curr(rq);
 }
 

@@ -1786,6 +1792,14 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 			pull_dl_task(rq);
 
 		/*
+		 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+		 * means a stop task can slip in, in which case we need to
+		 * reschedule.
+		 */
+		if (rq->stop && task_on_rq_queued(rq->stop))
+			resched_curr(rq);
+
+		/*
 		 * If we now have a earlier deadline task than p,
 		 * then reschedule, provided p is still on this
 		 * runqueue.

Hi Juri,

Quoted 8 lines · Juri Lelli

Hi,

Quoted 4 lines · Wanpeng Li

pull_dl_task can drop (and re-acquire) rq->lock, this means a stop task can slip in, in which case we need to reschedule. This patch add the reschedule when the scenario occurs.

Quoted 2 lines

Ok, I guess it can happen. Doesn't RT have the same problem? It seems that it also has to deal with DL tasks slipping in, right?

Yeah, I will send another patch to handle RT class in the v2 patchset. :)

Regards,
Wanpeng Li

Quoted 45 lines

Thanks,

- Juri

Quoted 40 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +15 -1

index b8b9355..844da0f 100644
@@ -1739,7 +1739,13 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
 		return;
 
-	if (pull_dl_task(rq))
+	/*
+	 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+	 * means a stop task can slip in, in which case we need to
+	 * reschedule.
+	 */
+	if (pull_dl_task(rq) ||
+		(rq->stop && task_on_rq_queued(rq->stop)))
 		resched_curr(rq);
 }
 

@@ -1786,6 +1792,14 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 			pull_dl_task(rq);
 
 		/*
+		 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+		 * means a stop task can slip in, in which case we need to
+		 * reschedule.
+		 */
+		if (rq->stop && task_on_rq_queued(rq->stop))
+			resched_curr(rq);
+
+		/*
 		 * If we now have a earlier deadline task than p,
 		 * then reschedule, provided p is still on this
 		 * runqueue.

Quoted 10 lines · Wanpeng Li

Hi Juri,

Quoted 8 lines · Juri Lelli

Hi,

Quoted 4 lines · Wanpeng Li

pull_dl_task can drop (and re-acquire) rq->lock, this means a stop task can slip in, in which case we need to reschedule. This patch add the reschedule when the scenario occurs.

Quoted 4 lines

Quoted 2 lines

Ok, I guess it can happen. Doesn't RT have the same problem? It seems that it also has to deal with DL tasks slipping in, right?

Yeah, I will send another patch to handle RT class in the v2 patchset. :)

Oh, I just find I have already done them in patch 7/7.

Regards,
Wanpeng Li

Quoted 49 lines

Regards,
Wanpeng Li

Quoted 45 lines

Thanks,

- Juri

Quoted 40 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/deadline.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +15 -1

index b8b9355..844da0f 100644
@@ -1739,7 +1739,13 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
 		return;
 
-	if (pull_dl_task(rq))
+	/*
+	 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+	 * means a stop task can slip in, in which case we need to
+	 * reschedule.
+	 */
+	if (pull_dl_task(rq) ||
+		(rq->stop && task_on_rq_queued(rq->stop)))
 		resched_curr(rq);
 }
 

@@ -1786,6 +1792,14 @@ static void prio_changed_dl(struct rq *rq, struct task_struct *p,
 			pull_dl_task(rq);
 
 		/*
+		 * pull_dl_task() can drop (and re-acquire) rq->lock; this
+		 * means a stop task can slip in, in which case we need to
+		 * reschedule.
+		 */
+		if (rq->stop && task_on_rq_queued(rq->stop))
+			resched_curr(rq);
+
+		/*
 		 * If we now have a earlier deadline task than p,
 		 * then reschedule, provided p is still on this
 		 * runqueue.

There are two init_sched_dl_class declarations, this patch drop the duplicated one.

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/sched.h | 1 -
 1 file changed, 1 deletion(-)

kernel/sched/sched.h +0 -1

index e0e1299..c9b2689 100644
@@ -1284,7 +1284,6 @@ extern void update_max_interval(void);
 extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
-extern void init_sched_dl_class(void);
 
 extern void resched_curr(struct rq *rq);
 extern void resched_cpu(int cpu);

Hi,

Quoted 2 lines · Wanpeng Li

There are two init_sched_dl_class declarations, this patch drop the duplicated one.

I guess the changelog needs to be trimmed. Apart from this, the

patch looks of course good, thanks!

Best,

- Juri

Quoted 18 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/sched.h | 1 -
 1 file changed, 1 deletion(-)

kernel/sched/sched.h +0 -1

index e0e1299..c9b2689 100644
@@ -1284,7 +1284,6 @@ extern void update_max_interval(void);
 extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
-extern void init_sched_dl_class(void);
 
 extern void resched_curr(struct rq *rq);
 extern void resched_cpu(int cpu);

Since the natural place to clear ->dl_throttled is in replenish_dl_entity(), and the task which is adjusted the priority is the current, it will be dequeued and then enqueued w/ replenish which can guarantee ->dl_throttled can be cleared, this patch drop the clear throttled status in function rt_mutex_setprio.

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/core.c | 1 -
 1 file changed, 1 deletion(-)

kernel/sched/core.c +0 -1

index 28b0d75..f1b9222 100644
@@ -3037,7 +3037,6 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 		if (!dl_prio(p->normal_prio) ||
 		    (pi_task && dl_entity_preempt(&pi_task->dl, &p->dl))) {
 			p->dl.dl_boosted = 1;
-			p->dl.dl_throttled = 0;
 			enqueue_flag = ENQUEUE_REPLENISH;
 		} else
 			p->dl.dl_boosted = 0;

Hi,

Quoted 5 lines · Wanpeng Li

Since the natural place to clear ->dl_throttled is in replenish_dl_entity(), and the task which is adjusted the priority is the current, it will be dequeued and then enqueued w/ replenish which can guarantee ->dl_throttled can be cleared, this patch drop the clear throttled status in function rt_mutex_setprio.

Patch looks good. But, I'd slightly change subject and changelog. Something like this, maybe?

sched/core: remove superfluous resetting of dl_throttled flag

Resetting dl_throttled flag in rt_mutex_setprio (for a task that is going to be boosted) is superfluous, as the natural place to do so is in replenish_dl_entity(). If the task was on the runqueue and it is boosted by a DL task, it will be enqueued back with ENQUEUE_REPLENISH flag set, which can guarantee that dl_throttled is reset in replenish_dl_entity().

This patch drops the resetting of throttled status in function rt_mutex_setprio().

Thanks,

- Juri

Quoted 18 lines

Signed-off-by Wanpeng Li <[email protected]>

---
 kernel/sched/core.c | 1 -
 1 file changed, 1 deletion(-)

kernel/sched/core.c +0 -1

index 28b0d75..f1b9222 100644
@@ -3037,7 +3037,6 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 		if (!dl_prio(p->normal_prio) ||
 		    (pi_task && dl_entity_preempt(&pi_task->dl, &p->dl))) {
 			p->dl.dl_boosted = 1;
-			p->dl.dl_throttled = 0;
 			enqueue_flag = ENQUEUE_REPLENISH;
 		} else
 			p->dl.dl_boosted = 0;

Function pick_next_earliest_dl_task is used to pick earliest and pushable dl task from overloaded cpus in pull algorithm, however, it traverses runqueue rbtree instead of pushable task rbtree which is also ordered by tasks' deadlines. This will result in getting no candidates from overloaded cpus if all the dl tasks on the overloaded cpus are pinned. This patch fix it by traversing pushable task rbtree which is also ordered by tasks' deadlines.

Signed-off-by Wanpeng Li <[email protected]>

---
kernel/sched/deadline.c | 29 ++++++++++++++++++++++++++++-

1 file changed, 28 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +28 -1

index 5e95145..b57ceba 100644
@@ -1230,6 +1230,33 @@ next_node:
 	return NULL;
 }
 
+/*
+ * Return the earliest pushable rq's task, which is suitable to be executed
+ * on the cpu, NULL otherwse
+ */
+static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq,
+									int cpu)
+{
+	struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
+	struct task_struct *p = NULL;
+
+	if (!has_pushable_dl_tasks(rq))
+		return NULL;
+
+next_node:
+	if (next_node) {
+		p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
+
+		if (pick_dl_task(rq, p, cpu))
+			return p;
+
+		next_node = rb_next(next_node);
+		goto next_node;
+	}
+
+	return NULL;
+}
+
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
 
 static int find_later_rq(struct task_struct *task)

@@ -1514,7 +1541,7 @@ static int pull_dl_task(struct rq *this_rq)
 		if (src_rq->dl.dl_nr_running <= 1)
 			goto skip;
 
-		p = pick_next_earliest_dl_task(src_rq, this_cpu);
+		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
 
 		/*
 		 * We found a task to be pulled if:

Signature · 1 line

1.9.1

Function pick_next_earliest_dl_task is used to pick earliest and pushable dl task from overloaded cpus in pull algorithm, however, it traverses runqueue rbtree instead of pushable task rbtree which is also ordered by tasks' deadlines. This will result in getting no candidates from overloaded cpus if all the dl tasks on the overloaded cpus are pinned. This patch fix it by traversing pushable task rbtree which is also ordered by tasks' deadlines.

Signed-off-by Wanpeng Li <[email protected]>

---
kernel/sched/deadline.c | 29 ++++++++++++++++++++++++++++-

1 file changed, 28 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +28 -1

index 5e95145..b57ceba 100644
@@ -1230,6 +1230,33 @@ next_node:
 	return NULL;
 }
 
+/*
+ * Return the earliest pushable rq's task, which is suitable to be executed
+ * on the cpu, NULL otherwse
+ */
+static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq,
+									int cpu)
+{
+	struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
+	struct task_struct *p = NULL;
+
+	if (!has_pushable_dl_tasks(rq))
+		return NULL;
+
+next_node:
+	if (next_node) {
+		p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
+
+		if (pick_dl_task(rq, p, cpu))
+			return p;
+
+		next_node = rb_next(next_node);
+		goto next_node;
+	}
+
+	return NULL;
+}
+
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
 
 static int find_later_rq(struct task_struct *task)

@@ -1514,7 +1541,7 @@ static int pull_dl_task(struct rq *this_rq)
 		if (src_rq->dl.dl_nr_running <= 1)
 			goto skip;
 
-		p = pick_next_earliest_dl_task(src_rq, this_cpu);
+		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
 
 		/*
 		 * We found a task to be pulled if:

Signature · 1 line

1.9.1

How about patch 1/7? :)

Quoted 62 lines · Wanpeng Li

Function pick_next_earliest_dl_task is used to pick earliest and pushable dl task from overloaded cpus in pull algorithm, however, it traverses runqueue rbtree instead of pushable task rbtree which is also ordered by tasks' deadlines. This will result in getting no candidates from overloaded cpus if all the dl tasks on the overloaded cpus are pinned. This patch fix it by traversing pushable task rbtree which is also ordered by tasks' deadlines.

Signed-off-by Wanpeng Li <[email protected]>

---
kernel/sched/deadline.c | 29 ++++++++++++++++++++++++++++-

1 file changed, 28 insertions(+), 1 deletion(-)

kernel/sched/deadline.c +28 -1

index 5e95145..b57ceba 100644
@@ -1230,6 +1230,33 @@ next_node:
 	return NULL;
 }
 
+/*
+ * Return the earliest pushable rq's task, which is suitable to be executed
+ * on the cpu, NULL otherwse
+ */
+static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq,
+									int cpu)
+{
+	struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
+	struct task_struct *p = NULL;
+
+	if (!has_pushable_dl_tasks(rq))
+		return NULL;
+
+next_node:
+	if (next_node) {
+		p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
+
+		if (pick_dl_task(rq, p, cpu))
+			return p;
+
+		next_node = rb_next(next_node);
+		goto next_node;
+	}
+
+	return NULL;
+}
+
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
 
 static int find_later_rq(struct task_struct *task)

@@ -1514,7 +1541,7 @@ static int pull_dl_task(struct rq *this_rq)
 		if (src_rq->dl.dl_nr_running <= 1)
 			goto skip;
 
-		p = pick_next_earliest_dl_task(src_rq, this_cpu);
+		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
 
 		/*
 		 * We found a task to be pulled if:

Signature · 1 line

1.9.1