2017-06-02 07:31:44

by Byungchul Park

[permalink] [raw]
Subject: [PATCH 1/2] sched/deadline: Add cpudl_maximum_dl()

Current code uses cpudl_maximum() to get the root node's cpu, while it
directly accesses the root node using 'cp->elements[0].dl' to get the
root node's dl. It would be better and more readible if a function to
get the dl is added. So add it.

Signed-off-by: Byungchul Park <[email protected]>
---
kernel/sched/cpudeadline.c | 13 +++++++++----
1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index fba235c..d4a6963 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -108,11 +108,16 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
cpudl_heapify_down(cp, idx);
}

-static inline int cpudl_maximum(struct cpudl *cp)
+static inline int cpudl_maximum_cpu(struct cpudl *cp)
{
return cp->elements[0].cpu;
}

+static inline u64 cpudl_maximum_dl(struct cpudl *cp)
+{
+ return cp->elements[0].dl;
+}
+
/*
* cpudl_find - find the best (later-dl) CPU in the system
* @cp: the cpudl max-heap context
@@ -131,9 +136,9 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
best_cpu = cpumask_any(later_mask);
goto out;
- } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
- dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
- best_cpu = cpudl_maximum(cp);
+ } else if (cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
+ dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
+ best_cpu = cpudl_maximum_cpu(cp);
if (later_mask)
cpumask_set_cpu(best_cpu, later_mask);
}
--
1.9.1


2017-06-02 07:32:13

by Byungchul Park

[permalink] [raw]
Subject: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

When the heap tree is empty, cp->elements[0].cpu has meaningless value.
We need to consider the case.

Signed-off-by: Byungchul Park <[email protected]>
---
kernel/sched/cpudeadline.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index d4a6963..9b314a9 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -110,7 +110,8 @@ static void cpudl_heapify(struct cpudl *cp, int idx)

static inline int cpudl_maximum_cpu(struct cpudl *cp)
{
- return cp->elements[0].cpu;
+ int cpu = cp->elements[0].cpu;
+ return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
}

static inline u64 cpudl_maximum_dl(struct cpudl *cp)
--
1.9.1

2017-06-06 15:12:30

by Juri Lelli

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

Hi,

On 02/06/17 16:31, Byungchul Park wrote:
> When the heap tree is empty, cp->elements[0].cpu has meaningless value.
> We need to consider the case.
>
> Signed-off-by: Byungchul Park <[email protected]>
> ---
> kernel/sched/cpudeadline.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> index d4a6963..9b314a9 100644
> --- a/kernel/sched/cpudeadline.c
> +++ b/kernel/sched/cpudeadline.c
> @@ -110,7 +110,8 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
>
> static inline int cpudl_maximum_cpu(struct cpudl *cp)
> {
> - return cp->elements[0].cpu;
> + int cpu = cp->elements[0].cpu;
> + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;

Mmm, don't we get a WARN from cpumask_check() if we return -1 here?

Thanks,

- Juri

2017-06-06 23:42:37

by Byungchul Park

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On Tue, Jun 06, 2017 at 04:12:25PM +0100, Juri Lelli wrote:
> Hi,
>
> On 02/06/17 16:31, Byungchul Park wrote:
> > When the heap tree is empty, cp->elements[0].cpu has meaningless value.

Hi,

The meaningless value is 0.

> > We need to consider the case.
> >
> > Signed-off-by: Byungchul Park <[email protected]>
> > ---
> > kernel/sched/cpudeadline.c | 3 ++-
> > 1 file changed, 2 insertions(+), 1 deletion(-)
> >
> > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > index d4a6963..9b314a9 100644
> > --- a/kernel/sched/cpudeadline.c
> > +++ b/kernel/sched/cpudeadline.c
> > @@ -110,7 +110,8 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
> >
> > static inline int cpudl_maximum_cpu(struct cpudl *cp)
> > {
> > - return cp->elements[0].cpu;
> > + int cpu = cp->elements[0].cpu;
> > + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
>
> Mmm, don't we get a WARN from cpumask_check() if we return -1 here?

The function does not return -1 without my patch.

Right?

>
> Thanks,
>
> - Juri

2017-06-07 00:15:08

by Byungchul Park

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On Wed, Jun 07, 2017 at 08:42:24AM +0900, Byungchul Park wrote:
> On Tue, Jun 06, 2017 at 04:12:25PM +0100, Juri Lelli wrote:
> > Hi,
> >
> > On 02/06/17 16:31, Byungchul Park wrote:
> > > When the heap tree is empty, cp->elements[0].cpu has meaningless value.
>
> Hi,
>
> The meaningless value is 0.
>
> > > We need to consider the case.
> > >
> > > Signed-off-by: Byungchul Park <[email protected]>
> > > ---
> > > kernel/sched/cpudeadline.c | 3 ++-
> > > 1 file changed, 2 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > > index d4a6963..9b314a9 100644
> > > --- a/kernel/sched/cpudeadline.c
> > > +++ b/kernel/sched/cpudeadline.c
> > > @@ -110,7 +110,8 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
> > >
> > > static inline int cpudl_maximum_cpu(struct cpudl *cp)
> > > {
> > > - return cp->elements[0].cpu;
> > > + int cpu = cp->elements[0].cpu;
> > > + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
> >
> > Mmm, don't we get a WARN from cpumask_check() if we return -1 here?
>
> The function does not return -1 without my patch.
>
> Right?

Or the following patch would be needed, instead.

----->8-----

>From cada1345bf0ff8e6b5743999509d2abcacd79a9e Mon Sep 17 00:00:00 2001
From: Byungchul Park <[email protected]>
Date: Wed, 7 Jun 2017 09:05:34 +0900
Subject: [PATCH 2/2] sched/deadline: Initialize cp->elements[].cpu to an
invalid value

Currently, when the heap tree is empty, cpudl_maximum_cpu() returns 0,
which causes unnecessary migration. It has to return an invalid value
e.g. -1 to prevent that.

Signed-off-by: Byungchul Park <[email protected]>
---
kernel/sched/cpudeadline.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index d4a6963..0f67cea 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -266,8 +266,10 @@ int cpudl_init(struct cpudl *cp)
return -ENOMEM;
}

- for_each_possible_cpu(i)
+ for_each_possible_cpu(i) {
+ cp->elements[i].cpu = -1;
cp->elements[i].idx = IDX_INVALID;
+ }

return 0;
}
--
1.9.1

2017-06-08 14:03:05

by Juri Lelli

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On 07/06/17 09:14, Byungchul Park wrote:
> On Wed, Jun 07, 2017 at 08:42:24AM +0900, Byungchul Park wrote:
> > On Tue, Jun 06, 2017 at 04:12:25PM +0100, Juri Lelli wrote:
> > > Hi,
> > >
> > > On 02/06/17 16:31, Byungchul Park wrote:

[...]

> > > >
> > > > static inline int cpudl_maximum_cpu(struct cpudl *cp)
> > > > {
> > > > - return cp->elements[0].cpu;
> > > > + int cpu = cp->elements[0].cpu;
> > > > + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
> > >
> > > Mmm, don't we get a WARN from cpumask_check() if we return -1 here?
> >
> > The function does not return -1 without my patch.
> >
> > Right?
>

That's actually my point: with the change you are proposing we will
start returning -1 and it looks to me that the WARN will start to fire.

What about the below instead (properly splitted in 2 patches I guess,
and I'm not sure at all the macro thing is pretty at all) ?

--->8---
kernel/sched/cpudeadline.c | 19 +++++++++++++------
1 file changed, 13 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index fba235c7d026..32e3dcef2b81 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -108,11 +108,17 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
cpudl_heapify_down(cp, idx);
}

-static inline int cpudl_maximum(struct cpudl *cp)
-{
- return cp->elements[0].cpu;
+#define cpudl_maximum(field) \
+static inline int cpudl_maximum_##field \
+(struct cpudl *cp) \
+{ \
+ return cp->elements[0].field; \
}

+cpudl_maximum(cpu);
+cpudl_maximum(dl);
+cpudl_maximum(idx);
+
/*
* cpudl_find - find the best (later-dl) CPU in the system
* @cp: the cpudl max-heap context
@@ -131,9 +137,10 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
best_cpu = cpumask_any(later_mask);
goto out;
- } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
- dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
- best_cpu = cpudl_maximum(cp);
+ } else if (cpudl_maximum_idx(cp) != IDX_INVALID &&
+ cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
+ dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
+ best_cpu = cpudl_maximum_cpu(cp);
if (later_mask)
cpumask_set_cpu(best_cpu, later_mask);
}

2017-06-09 02:43:40

by Byungchul Park

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On Thu, Jun 08, 2017 at 03:02:43PM +0100, Juri Lelli wrote:
> On 07/06/17 09:14, Byungchul Park wrote:
> > On Wed, Jun 07, 2017 at 08:42:24AM +0900, Byungchul Park wrote:
> > > On Tue, Jun 06, 2017 at 04:12:25PM +0100, Juri Lelli wrote:
> > > > Hi,
> > > >
> > > > On 02/06/17 16:31, Byungchul Park wrote:
>
> [...]
>
> > > > >
> > > > > static inline int cpudl_maximum_cpu(struct cpudl *cp)
> > > > > {
> > > > > - return cp->elements[0].cpu;
> > > > > + int cpu = cp->elements[0].cpu;
> > > > > + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
> > > >
> > > > Mmm, don't we get a WARN from cpumask_check() if we return -1 here?
> > >
> > > The function does not return -1 without my patch.
> > >
> > > Right?
> >
>
> That's actually my point: with the change you are proposing we will
> start returning -1 and it looks to me that the WARN will start to fire.

Hi,

I see what you talk about. You are talking about WARN in cpumask_check().
Sorry for missing your words.

> What about the below instead (properly splitted in 2 patches I guess,
> and I'm not sure at all the macro thing is pretty at all) ?
>
> --->8---
> kernel/sched/cpudeadline.c | 19 +++++++++++++------
> 1 file changed, 13 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> index fba235c7d026..32e3dcef2b81 100644
> --- a/kernel/sched/cpudeadline.c
> +++ b/kernel/sched/cpudeadline.c
> @@ -108,11 +108,17 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
> cpudl_heapify_down(cp, idx);
> }
>
> -static inline int cpudl_maximum(struct cpudl *cp)
> -{
> - return cp->elements[0].cpu;
> +#define cpudl_maximum(field) \
> +static inline int cpudl_maximum_##field \
> +(struct cpudl *cp) \
> +{ \
> + return cp->elements[0].field; \
> }
>
> +cpudl_maximum(cpu);
> +cpudl_maximum(dl);
> +cpudl_maximum(idx);
> +
> /*
> * cpudl_find - find the best (later-dl) CPU in the system
> * @cp: the cpudl max-heap context
> @@ -131,9 +137,10 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
> cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
> best_cpu = cpumask_any(later_mask);
> goto out;
> - } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
> - dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
> - best_cpu = cpudl_maximum(cp);
> + } else if (cpudl_maximum_idx(cp) != IDX_INVALID &&
> + cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
> + dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
> + best_cpu = cpudl_maximum_cpu(cp);

This would also work and avoid unnecessary warning. I missed the check
to avoid it. https://lkml.org/lkml/2017/3/23/175 was an original patch
doing it.

By the way, frankly speaking, I don't like accessing the cpudl instant
several times without protection. I rather prefer the following..

But whatever. I like both.

Thnaks,
Byungchul

----->8-----
diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
index 9b314a9..1d369cf 100644
--- a/kernel/sched/cpudeadline.c
+++ b/kernel/sched/cpudeadline.c
@@ -137,11 +137,17 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
best_cpu = cpumask_any(later_mask);
goto out;
- } else if (cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
- dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
- best_cpu = cpudl_maximum_cpu(cp);
- if (later_mask)
- cpumask_set_cpu(best_cpu, later_mask);
+ } else {
+ int max_cpu = cpudl_maximum_cpu(cp);
+ u64 max_dl = cpudl_maximum_dl(cp);
+
+ if (max_cpu != -1 &&
+ cpumask_test_cpu(max_cpu, &p->cpus_allowed) &&
+ dl_time_before(dl_se->deadline, max_dl)) {
+ best_cpu = max_cpu;
+ if (later_mask)
+ cpumask_set_cpu(best_cpu, later_mask);
+ }
}

out:


2017-06-09 11:42:23

by Juri Lelli

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On 09/06/17 11:43, Byungchul Park wrote:
> On Thu, Jun 08, 2017 at 03:02:43PM +0100, Juri Lelli wrote:
> > On 07/06/17 09:14, Byungchul Park wrote:
> > > On Wed, Jun 07, 2017 at 08:42:24AM +0900, Byungchul Park wrote:
> > > > On Tue, Jun 06, 2017 at 04:12:25PM +0100, Juri Lelli wrote:
> > > > > Hi,
> > > > >
> > > > > On 02/06/17 16:31, Byungchul Park wrote:
> >
> > [...]
> >
> > > > > >
> > > > > > static inline int cpudl_maximum_cpu(struct cpudl *cp)
> > > > > > {
> > > > > > - return cp->elements[0].cpu;
> > > > > > + int cpu = cp->elements[0].cpu;
> > > > > > + return cp->elements[cpu].idx == IDX_INVALID ? -1 : cpu;
> > > > >
> > > > > Mmm, don't we get a WARN from cpumask_check() if we return -1 here?
> > > >
> > > > The function does not return -1 without my patch.
> > > >
> > > > Right?
> > >
> >
> > That's actually my point: with the change you are proposing we will
> > start returning -1 and it looks to me that the WARN will start to fire.
>
> Hi,
>
> I see what you talk about. You are talking about WARN in cpumask_check().
> Sorry for missing your words.
>
> > What about the below instead (properly splitted in 2 patches I guess,
> > and I'm not sure at all the macro thing is pretty at all) ?
> >
> > --->8---
> > kernel/sched/cpudeadline.c | 19 +++++++++++++------
> > 1 file changed, 13 insertions(+), 6 deletions(-)
> >
> > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > index fba235c7d026..32e3dcef2b81 100644
> > --- a/kernel/sched/cpudeadline.c
> > +++ b/kernel/sched/cpudeadline.c
> > @@ -108,11 +108,17 @@ static void cpudl_heapify(struct cpudl *cp, int idx)
> > cpudl_heapify_down(cp, idx);
> > }
> >
> > -static inline int cpudl_maximum(struct cpudl *cp)
> > -{
> > - return cp->elements[0].cpu;
> > +#define cpudl_maximum(field) \
> > +static inline int cpudl_maximum_##field \
> > +(struct cpudl *cp) \
> > +{ \
> > + return cp->elements[0].field; \
> > }
> >
> > +cpudl_maximum(cpu);
> > +cpudl_maximum(dl);
> > +cpudl_maximum(idx);
> > +
> > /*
> > * cpudl_find - find the best (later-dl) CPU in the system
> > * @cp: the cpudl max-heap context
> > @@ -131,9 +137,10 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
> > cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
> > best_cpu = cpumask_any(later_mask);
> > goto out;
> > - } else if (cpumask_test_cpu(cpudl_maximum(cp), &p->cpus_allowed) &&
> > - dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
> > - best_cpu = cpudl_maximum(cp);
> > + } else if (cpudl_maximum_idx(cp) != IDX_INVALID &&
> > + cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
> > + dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
> > + best_cpu = cpudl_maximum_cpu(cp);
>
> This would also work and avoid unnecessary warning. I missed the check
> to avoid it. https://lkml.org/lkml/2017/3/23/175 was an original patch
> doing it.
>
> By the way, frankly speaking, I don't like accessing the cpudl instant
> several times without protection. I rather prefer the following..
>
> But whatever. I like both.
>
> Thnaks,
> Byungchul
>
> ----->8-----
> diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> index 9b314a9..1d369cf 100644
> --- a/kernel/sched/cpudeadline.c
> +++ b/kernel/sched/cpudeadline.c
> @@ -137,11 +137,17 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
> cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
> best_cpu = cpumask_any(later_mask);
> goto out;
> - } else if (cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
> - dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
> - best_cpu = cpudl_maximum_cpu(cp);
> - if (later_mask)
> - cpumask_set_cpu(best_cpu, later_mask);
> + } else {
> + int max_cpu = cpudl_maximum_cpu(cp);
> + u64 max_dl = cpudl_maximum_dl(cp);
> +
> + if (max_cpu != -1 &&
> + cpumask_test_cpu(max_cpu, &p->cpus_allowed) &&
> + dl_time_before(dl_se->deadline, max_dl)) {

Don't we access cp 3 times both ways?

2017-06-12 01:43:23

by Byungchul Park

[permalink] [raw]
Subject: Re: [PATCH 2/2] sched/deadline: Don't return invalid cpu in cpudl_maximum_cpu()

On Fri, Jun 09, 2017 at 12:42:06PM +0100, Juri Lelli wrote:
> >
> > This would also work and avoid unnecessary warning. I missed the check
> > to avoid it. https://lkml.org/lkml/2017/3/23/175 was an original patch
> > doing it.
> >
> > By the way, frankly speaking, I don't like accessing the cpudl instant
> > several times without protection. I rather prefer the following..
> >
> > But whatever. I like both.
> >
> > Thnaks,
> > Byungchul
> >
> > ----->8-----
> > diff --git a/kernel/sched/cpudeadline.c b/kernel/sched/cpudeadline.c
> > index 9b314a9..1d369cf 100644
> > --- a/kernel/sched/cpudeadline.c
> > +++ b/kernel/sched/cpudeadline.c
> > @@ -137,11 +137,17 @@ int cpudl_find(struct cpudl *cp, struct task_struct *p,
> > cpumask_and(later_mask, cp->free_cpus, &p->cpus_allowed)) {
> > best_cpu = cpumask_any(later_mask);
> > goto out;
> > - } else if (cpumask_test_cpu(cpudl_maximum_cpu(cp), &p->cpus_allowed) &&
> > - dl_time_before(dl_se->deadline, cpudl_maximum_dl(cp))) {
> > - best_cpu = cpudl_maximum_cpu(cp);
> > - if (later_mask)
> > - cpumask_set_cpu(best_cpu, later_mask);
> > + } else {
> > + int max_cpu = cpudl_maximum_cpu(cp);
> > + u64 max_dl = cpudl_maximum_dl(cp);
> > +
> > + if (max_cpu != -1 &&
> > + cpumask_test_cpu(max_cpu, &p->cpus_allowed) &&
> > + dl_time_before(dl_se->deadline, max_dl)) {
>
> Don't we access cp 3 times both ways?

I wonder if I miss something.. As you said, in most cases it will, but
I am not sure if we can guarentee that, regardless of arches or
compile optimization level. Sorry if I am wrong.