From: "pang.xunlei" <pang.xunlei@linaro.org>
To: linux-kernel@vger.kernel.org
Cc: Peter Zijlstra <peterz@infradead.org>,
Steven Rostedt <rostedt@goodmis.org>,
Juri Lelli <juri.lelli@gmail.com>,
"pang.xunlei" <pang.xunlei@linaro.org>
Subject: [PATCH v4 7/7] sched/deadline: Modify cpudl_find() for more cases of electing best_cpu
Date: Thu, 6 Nov 2014 15:52:07 +0800 [thread overview]
Message-ID: <1415260327-30465-7-git-send-email-pang.xunlei@linaro.org> (raw)
In-Reply-To: <1415260327-30465-1-git-send-email-pang.xunlei@linaro.org>
When a runqueue runs out of DL tasks, it may have RT tasks or non-RT
tasks or just idle. It'd be better to push the DL task to an idle cpu
or non-RT cpu if there is any.
Add idle_cpus and freert_cpus, change free_cpus to freedl_cpus in cpudl.
Add idle_enter_dl()/idle_exit_dl() to detect idle cases.
Add rt_enter_dl()/rt_exit_dl() to detect non-RT cases.
Add a set_flag parameter to cpudl_find().
Use the same thought as that in tackling RT in the former patch.
Signed-off-by: pang.xunlei <pang.xunlei@linaro.org>
---
kernel/sched/cpudeadline.c | 76 ++++++++++++++++++++++++++++++++++++--------
kernel/sched/cpudeadline.h | 15 +++++++--
kernel/sched/deadline.c | 38 +++++++++++++++++-----
kernel/sched/idle_task.c | 2 ++
kernel/sched/rt.c | 7 ++++
kernel/sched/sched.h | 11 +++++++
6 files changed, 124 insertions(+), 25 deletions(-)
diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index 1dd446a..cc78ebe 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -98,16 +98,31 @@ static inline int cpudl_maximum(struct cpudl *cp)
* @cp: the cpudl max-heap context
* @p: the task
* @later_mask: a mask to fill in with the selected CPUs (not NULL)
+ * @set_flag: a flag to determine if should set the later_mask.
*
* Returns: (int)bool - CPUs were found
*/
int cpudl_find(struct cpudl *cp, struct task_struct *p,
- struct cpumask *later_mask)
+ struct cpumask *later_mask, int set_flag)
{
const struct sched_dl_entity *dl_se = &p->dl;
cpumask_and(later_mask, cpu_active_mask, &p->cpus_allowed);
- if (cpumask_and(later_mask, later_mask, cp->free_cpus)) {
+ /* sync for idle_cpus, freert_cpus, freedl_cpus */
+ smp_rmb();
+
+ if (cpumask_any_and(later_mask, cp->idle_cpus) < nr_cpu_ids) {
+ if (set_flag)
+ cpumask_and(later_mask, &p->cpus_allowed,
+ cp->idle_cpus);
+ return 1;
+ } else if (cpumask_any_and(later_mask, cp->freert_cpus)
+ < nr_cpu_ids) {
+ if (set_flag)
+ cpumask_and(later_mask, &p->cpus_allowed,
+ cp->freert_cpus);
+ return 1;
+ } else if (cpumask_and(later_mask, later_mask, cp->freedl_cpus)) {
return 1;
} else if (cpumask_and(later_mask, cpumask_of(cpudl_maximum(cp)),
&p->cpus_allowed) &&
@@ -123,21 +138,39 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
* @cp: the cpudl max-heap context
* @cpu: the target cpu
* @dl: the new earliest deadline for this cpu
- *
+ * @set_flags: CPUDL_SET_XXX, CPUDL_CLEAR_XXX
* Notes: assumes cpu_rq(cpu)->lock is locked
*
* Returns: (void)
*/
-void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
+void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int set_flags)
{
int old_idx, new_cpu;
unsigned long flags;
WARN_ON(!cpu_present(cpu));
+ /* We can do this percpu operation without spinlock */
+ switch (set_flags) {
+ case CPUDL_SET_IDLE:
+ cpumask_set_cpu(cpu, cp->idle_cpus);
+ return;
+ case CPUDL_CLEAR_IDLE:
+ cpumask_clear_cpu(cpu, cp->idle_cpus);
+ return;
+ case CPUDL_SET_FREERT:
+ cpumask_set_cpu(cpu, cp->freert_cpus);
+ return;
+ case CPUDL_CLEAR_FREERT:
+ cpumask_clear_cpu(cpu, cp->freert_cpus);
+ return;
+ default:
+ break;
+ }
+
raw_spin_lock_irqsave(&cp->lock, flags);
old_idx = cp->elements[cpu].idx;
- if (!is_valid) {
+ if (set_flags == CPUDL_SET_FREEDL) {
/* remove item */
if (old_idx == IDX_INVALID) {
/*
@@ -159,7 +192,7 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
cpudl_exchange(cp, old_idx, parent(old_idx));
old_idx = parent(old_idx);
}
- cpumask_set_cpu(cpu, cp->free_cpus);
+ cpumask_set_cpu(cpu, cp->freedl_cpus);
cpudl_heapify(cp, old_idx);
goto out;
@@ -171,7 +204,7 @@ void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid)
cp->elements[cp->size - 1].cpu = cpu;
cp->elements[cpu].idx = cp->size - 1;
cpudl_change_key(cp, cp->size - 1, dl);
- cpumask_clear_cpu(cpu, cp->free_cpus);
+ cpumask_clear_cpu(cpu, cp->freedl_cpus);
} else {
cpudl_change_key(cp, old_idx, dl);
}
@@ -187,7 +220,7 @@ out:
*/
void cpudl_set_freecpu(int cpu, struct cpudl *cp)
{
- cpumask_set_cpu(cpu, cp->free_cpus);
+ cpumask_set_cpu(cpu, cp->freedl_cpus);
}
/*
@@ -206,17 +239,30 @@ int cpudl_init(struct cpudl *cp)
sizeof(struct cpudl_item),
GFP_KERNEL);
if (!cp->elements)
- return -ENOMEM;
+ goto out;
- if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
- kfree(cp->elements);
- return -ENOMEM;
- }
+ if (!zalloc_cpumask_var(&cp->freedl_cpus, GFP_KERNEL))
+ goto free_elements;
+
+ if (!zalloc_cpumask_var(&cp->freert_cpus, GFP_KERNEL))
+ goto free_freedl_cpus;
+
+ if (!zalloc_cpumask_var(&cp->idle_cpus, GFP_KERNEL))
+ goto free_freert_cpus;
for_each_possible_cpu(i)
cp->elements[i].idx = IDX_INVALID;
return 0;
+
+free_freert_cpus:
+ kfree(cp->freert_cpus);
+free_freedl_cpus:
+ kfree(cp->freedl_cpus);
+free_elements:
+ kfree(cp->elements);
+out:
+ return -ENOMEM;
}
/*
@@ -225,6 +271,8 @@ int cpudl_init(struct cpudl *cp)
*/
void cpudl_cleanup(struct cpudl *cp)
{
- free_cpumask_var(cp->free_cpus);
+ free_cpumask_var(cp->freedl_cpus);
+ free_cpumask_var(cp->freert_cpus);
+ free_cpumask_var(cp->idle_cpus);
kfree(cp->elements);
}
diff --git a/kernel/sched/cpudeadline.h b/kernel/sched/cpudeadline.h
index 71478fc..b2d4004 100644
--- a/kernel/sched/cpudeadline.h
+++ b/kernel/sched/cpudeadline.h
@@ -5,6 +5,13 @@
#define IDX_INVALID -1
+#define CPUDL_SET_DL 1 /* set deadline value, clear freedl_cpus */
+#define CPUDL_SET_FREEDL 2 /* set freedl_cpus */
+#define CPUDL_SET_FREERT 3 /* set freert_cpus */
+#define CPUDL_CLEAR_FREERT 4 /* clear freert_cpus */
+#define CPUDL_SET_IDLE 5 /* set idle_cpus */
+#define CPUDL_CLEAR_IDLE 6 /* clear idle_cpus */
+
struct cpudl_item {
u64 dl;
int cpu;
@@ -14,15 +21,17 @@ struct cpudl_item {
struct cpudl {
raw_spinlock_t lock;
int size;
- cpumask_var_t free_cpus;
+ cpumask_var_t idle_cpus;
+ cpumask_var_t freert_cpus;
+ cpumask_var_t freedl_cpus;
struct cpudl_item *elements;
};
#ifdef CONFIG_SMP
int cpudl_find(struct cpudl *cp, struct task_struct *p,
- struct cpumask *later_mask);
-void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int is_valid);
+ struct cpumask *later_mask, int set_flag);
+void cpudl_set(struct cpudl *cp, int cpu, u64 dl, int set_flags);
int cpudl_init(struct cpudl *cp);
void cpudl_cleanup(struct cpudl *cp);
void cpudl_set_freecpu(int cpu, struct cpudl *cp);
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 01d3aaab..1e9941a 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -673,6 +673,26 @@ static void update_curr_dl(struct rq *rq)
#ifdef CONFIG_SMP
+void idle_enter_dl(struct rq *this_rq)
+{
+ cpudl_set(&this_rq->rd->cpudl, this_rq->cpu, 0, CPUDL_SET_IDLE);
+}
+
+void idle_exit_dl(struct rq *this_rq)
+{
+ cpudl_set(&this_rq->rd->cpudl, this_rq->cpu, 0, CPUDL_CLEAR_IDLE);
+}
+
+void rt_enter_dl(struct rq *this_rq)
+{
+ cpudl_set(&this_rq->rd->cpudl, this_rq->cpu, 0, CPUDL_CLEAR_FREERT);
+}
+
+void rt_exit_dl(struct rq *this_rq)
+{
+ cpudl_set(&this_rq->rd->cpudl, this_rq->cpu, 0, CPUDL_SET_FREERT);
+}
+
static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu);
static inline u64 next_deadline(struct rq *rq)
@@ -699,7 +719,7 @@ static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
*/
dl_rq->earliest_dl.next = dl_rq->earliest_dl.curr;
dl_rq->earliest_dl.curr = deadline;
- cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, 1);
+ cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, CPUDL_SET_DL);
} else if (dl_rq->earliest_dl.next == 0 ||
dl_time_before(deadline, dl_rq->earliest_dl.next)) {
/*
@@ -723,7 +743,7 @@ static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
if (!dl_rq->dl_nr_running) {
dl_rq->earliest_dl.curr = 0;
dl_rq->earliest_dl.next = 0;
- cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
+ cpudl_set(&rq->rd->cpudl, rq->cpu, 0, CPUDL_SET_FREEDL);
} else {
struct rb_node *leftmost = dl_rq->rb_leftmost;
struct sched_dl_entity *entry;
@@ -731,7 +751,8 @@ static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
dl_rq->earliest_dl.curr = entry->deadline;
dl_rq->earliest_dl.next = next_deadline(rq);
- cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline, 1);
+ cpudl_set(&rq->rd->cpudl, rq->cpu,
+ entry->deadline, CPUDL_SET_DL);
}
}
@@ -976,7 +997,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
* let's hope p can move out.
*/
if (rq->curr->nr_cpus_allowed == 1 ||
- !cpudl_find(&rq->rd->cpudl, rq->curr, later_mask))
+ !cpudl_find(&rq->rd->cpudl, rq->curr, later_mask, 0))
return;
/*
@@ -984,7 +1005,7 @@ static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
* see if it is pushed or pulled somewhere else.
*/
if (p->nr_cpus_allowed != 1 &&
- cpudl_find(&rq->rd->cpudl, p, later_mask))
+ cpudl_find(&rq->rd->cpudl, p, later_mask, 0))
return;
resched_curr(rq);
@@ -1190,7 +1211,7 @@ static int find_later_rq(struct task_struct *task)
* We have to consider system topology and task affinity
* first, then we can look for a suitable cpu.
*/
- if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
+ if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask, 1))
return -1;
if (cpumask_weight(later_mask) == 1)
@@ -1570,7 +1591,8 @@ static void rq_online_dl(struct rq *rq)
dl_set_overload(rq);
if (rq->dl.dl_nr_running > 0)
- cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr, 1);
+ cpudl_set(&rq->rd->cpudl, rq->cpu,
+ rq->dl.earliest_dl.curr, CPUDL_SET_DL);
}
/* Assumes rq->lock is held */
@@ -1579,7 +1601,7 @@ static void rq_offline_dl(struct rq *rq)
if (rq->dl.overloaded)
dl_clear_overload(rq);
- cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
+ cpudl_set(&rq->rd->cpudl, rq->cpu, 0, CPUDL_SET_FREEDL);
}
void init_sched_dl_class(void)
diff --git a/kernel/sched/idle_task.c b/kernel/sched/idle_task.c
index e053347..7838e56 100644
--- a/kernel/sched/idle_task.c
+++ b/kernel/sched/idle_task.c
@@ -26,6 +26,7 @@ static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p, int fl
static struct task_struct *
pick_next_task_idle(struct rq *rq, struct task_struct *prev)
{
+ idle_enter_dl(rq);
idle_enter_rt(rq);
put_prev_task(rq, prev);
@@ -49,6 +50,7 @@ dequeue_task_idle(struct rq *rq, struct task_struct *p, int flags)
static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
{
+ idle_exit_dl(rq);
idle_exit_rt(rq);
idle_exit_fair(rq);
rq_last_tick_reset(rq);
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index 49164f1..ee49b94 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -1484,6 +1484,9 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev)
if (!rt_rq->rt_queued)
return NULL;
+ if (prev->sched_class != &rt_sched_class)
+ rt_enter_dl(rq);
+
put_prev_task(rq, prev);
p = _pick_next_task_rt(rq);
@@ -1498,6 +1501,10 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev)
static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
{
+ /* Neglect stop preempt. As for dl preempt, doesn't matter */
+ if (rq->curr->sched_class != &rt_sched_class)
+ rt_exit_dl(rq);
+
update_curr_rt(rq);
/*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index cc603fa..b76dfef 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1162,6 +1162,12 @@ extern void update_group_capacity(struct sched_domain *sd, int cpu);
extern void trigger_load_balance(struct rq *rq);
+extern void rt_enter_dl(struct rq *this_rq);
+extern void rt_exit_dl(struct rq *this_rq);
+
+extern void idle_enter_dl(struct rq *this_rq);
+extern void idle_exit_dl(struct rq *this_rq);
+
extern void idle_enter_rt(struct rq *this_rq);
extern void idle_exit_rt(struct rq *this_rq);
@@ -1169,6 +1175,11 @@ extern void idle_enter_fair(struct rq *this_rq);
extern void idle_exit_fair(struct rq *this_rq);
#else
+static inline void rt_enter_dl(struct rq *rq) { }
+static inline void rt_exit_dl(struct rq *rq) { }
+
+static inline void idle_enter_dl(struct rq *rq) { }
+static inline void idle_exit_dl(struct rq *rq) { }
static inline void idle_enter_rt(struct rq *rq) { }
static inline void idle_exit_rt(struct rq *rq) { }
--
1.7.9.5
next prev parent reply other threads:[~2014-11-06 7:53 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-11-06 7:52 [PATCH v4 1/7] sched/cpupri: Remove unnecessary definitions in cpupri.h pang.xunlei
2014-11-06 7:52 ` [PATCH v4 2/7] sched/rt: Deal with cpupri.pri_to_cpu[CPUPRI_IDLE] for idle cases pang.xunlei
2014-11-06 7:52 ` [PATCH v4 3/7] sched/rt: Optimize find_lowest_rq() to select a cache hot cpu pang.xunlei
2014-11-06 7:52 ` [PATCH v4 4/7] sched/deadline: Remove unnecessary definitions in cpudeadline.h pang.xunlei
2014-11-16 12:33 ` [tip:sched/core] " tip-bot for pang.xunlei
2014-11-06 7:52 ` [PATCH v4 5/7] sched/deadline: Fix several problems with cpudl_find() pang.xunlei
2014-11-06 7:52 ` [PATCH v4 6/7] sched/deadline: Optimize find_later_rq() to select a cache hot cpu pang.xunlei
2014-11-06 7:52 ` pang.xunlei [this message]
2014-11-16 12:33 ` [tip:sched/core] sched/cpupri: Remove unnecessary definitions in cpupri.h tip-bot for pang.xunlei
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1415260327-30465-7-git-send-email-pang.xunlei@linaro.org \
--to=pang.xunlei@linaro.org \
--cc=juri.lelli@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.