From: Xuewen Yan <[email protected]>
Last_enqueued_diff's meaning: "diff = util_est.enqueued(p) - task_util(p)".
When calculating last_enqueued_diff, we add UTIL_AVG_UNCHANGED flag, which
is the LSB, for task_util, but don't add the flag for util_est.enqueued.
However the enqueued's flag had been cleared when the task util changed.
As a result, we add +1 to the diff, this is therefore reducing slightly
UTIL_EST_MARGIN.
Add the flag for util_est.enqueued to have a accurate computation.
Fixes: b89997aa88f0b sched/pelt: Fix task util_est update filtering
Signed-off-by: Xuewen Yan <[email protected]>
---
kernel/sched/fair.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e5e457fa9dc8..94d77b4fa601 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3996,7 +3996,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
if (ue.enqueued & UTIL_AVG_UNCHANGED)
return;
- last_enqueued_diff = ue.enqueued;
+ last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED);
/*
* Reset EWMA on utilization increases, the moving average is used only
--
2.29.0
On Fri, May 07, 2021 at 07:20:31PM +0800, Xuewen Yan wrote:
> From: Xuewen Yan <[email protected]>
>
> Last_enqueued_diff's meaning: "diff = util_est.enqueued(p) - task_util(p)".
> When calculating last_enqueued_diff, we add UTIL_AVG_UNCHANGED flag, which
> is the LSB, for task_util, but don't add the flag for util_est.enqueued.
> However the enqueued's flag had been cleared when the task util changed.
> As a result, we add +1 to the diff, this is therefore reducing slightly
> UTIL_EST_MARGIN.
Unless I miss something it actually depends on the situation, doesn't it?
if ue.enqueued > task_util(), we remove 1 from the diff => UTIL_EST_MARGIN + 1
if ue.enqueued < task_util(), we add 1 to the diff => UTIL_EST_MARGIN -1
>
> Add the flag for util_est.enqueued to have a accurate computation.
>
> Fixes: b89997aa88f0b sched/pelt: Fix task util_est update filtering
>
> Signed-off-by: Xuewen Yan <[email protected]>
> ---
> kernel/sched/fair.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e5e457fa9dc8..94d77b4fa601 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3996,7 +3996,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> if (ue.enqueued & UTIL_AVG_UNCHANGED)
> return;
>
> - last_enqueued_diff = ue.enqueued;
> + last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED);
>
> /*
> * Reset EWMA on utilization increases, the moving average is used only
> --
> 2.29.0
>
On 07/05/2021 14:35, Vincent Donnefort wrote:
> On Fri, May 07, 2021 at 07:20:31PM +0800, Xuewen Yan wrote:
>> From: Xuewen Yan <[email protected]>
>>
>> Last_enqueued_diff's meaning: "diff = util_est.enqueued(p) - task_util(p)".
>> When calculating last_enqueued_diff, we add UTIL_AVG_UNCHANGED flag, which
>> is the LSB, for task_util, but don't add the flag for util_est.enqueued.
>> However the enqueued's flag had been cleared when the task util changed.
>> As a result, we add +1 to the diff, this is therefore reducing slightly
>> UTIL_EST_MARGIN.
>
> Unless I miss something it actually depends on the situation, doesn't it?
>
> if ue.enqueued > task_util(), we remove 1 from the diff => UTIL_EST_MARGIN + 1
>
> if ue.enqueued < task_util(), we add 1 to the diff => UTIL_EST_MARGIN -1
I get:
ue.enqueued & UTIL_AVG_UNCHANGED = 0
last_enqueued_diff = ue.enqueued_old - ue.enqueued_new
last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED) - (task_util(p) | UTIL_AVG_UNCHANGED)
^^^^^^^^^^^^^^^^^^^^
added by patch
ue.enqueued_old didn't have the flag, otherwise would return earlier
task_util(p) could have the LSB set but we just set it to make sure it's set
So last_enqueued_diff is 1 larger.
But UTIL_EST_MARGIN stays `SCHED_CAPACITY_SCALE / 100` ?
Did I miss something here?
>>
>> Add the flag for util_est.enqueued to have a accurate computation.
>>
>> Fixes: b89997aa88f0b sched/pelt: Fix task util_est update filtering
>>
>> Signed-off-by: Xuewen Yan <[email protected]>
>> ---
>> kernel/sched/fair.c | 2 +-
>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index e5e457fa9dc8..94d77b4fa601 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -3996,7 +3996,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
>> if (ue.enqueued & UTIL_AVG_UNCHANGED)
>> return;
>>
>> - last_enqueued_diff = ue.enqueued;
>> + last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED);
>>
>> /*
>> * Reset EWMA on utilization increases, the moving average is used only
>> --
>> 2.29.0
>>
On Fri, May 07, 2021 at 03:36:47PM +0200, Dietmar Eggemann wrote:
> On 07/05/2021 14:35, Vincent Donnefort wrote:
> > On Fri, May 07, 2021 at 07:20:31PM +0800, Xuewen Yan wrote:
> >> From: Xuewen Yan <[email protected]>
> >>
> >> Last_enqueued_diff's meaning: "diff = util_est.enqueued(p) - task_util(p)".
> >> When calculating last_enqueued_diff, we add UTIL_AVG_UNCHANGED flag, which
> >> is the LSB, for task_util, but don't add the flag for util_est.enqueued.
> >> However the enqueued's flag had been cleared when the task util changed.
> >> As a result, we add +1 to the diff, this is therefore reducing slightly
> >> UTIL_EST_MARGIN.
> >
> > Unless I miss something it actually depends on the situation, doesn't it?
> >
> > if ue.enqueued > task_util(), we remove 1 from the diff => UTIL_EST_MARGIN + 1
> >
> > if ue.enqueued < task_util(), we add 1 to the diff => UTIL_EST_MARGIN -1
>
> I get:
>
> ue.enqueued & UTIL_AVG_UNCHANGED = 0
>
> last_enqueued_diff = ue.enqueued_old - ue.enqueued_new
>
> last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED) - (task_util(p) | UTIL_AVG_UNCHANGED)
>
> ^^^^^^^^^^^^^^^^^^^^
> added by patch
>
>
> ue.enqueued_old didn't have the flag, otherwise would return earlier
>
> task_util(p) could have the LSB set but we just set it to make sure it's set
>
> So last_enqueued_diff is 1 larger.
But we take the abs() of last_enqueued_diff.
If we consider the following examples:
enqueued_old = 5, enqueued_new = 9
diff = 5 - (9 + 1) => 5 - 10 => -5
enqueued_old = 9, enqueued_new = 5
diff = 9 - (5 + 1) => 9 - 6 => 3
In both cases the delta is supposed to be 4. But in the first case we end-up
with 5. In the second, we end-up with 3. That's why I meant the effect on the
diff depends on who's greater, ue.enqueued or task_util().
>
> But UTIL_EST_MARGIN stays `SCHED_CAPACITY_SCALE / 100` ?
>
> Did I miss something here?
But the only purpose of the diff is the comparison against the margin. So
+/-1 in the diff ends-up being the same as doing the opposite for the margin.
All in all, the missing flag ends-up by modifying UTIL_EST_MARGIN by -1 or +1.
--
Vincent
On 07/05/2021 17:38, Vincent Donnefort wrote:
> On Fri, May 07, 2021 at 03:36:47PM +0200, Dietmar Eggemann wrote:
>> On 07/05/2021 14:35, Vincent Donnefort wrote:
>>> On Fri, May 07, 2021 at 07:20:31PM +0800, Xuewen Yan wrote:
>>>> From: Xuewen Yan <[email protected]>
>>>>
>>>> Last_enqueued_diff's meaning: "diff = util_est.enqueued(p) - task_util(p)".
>>>> When calculating last_enqueued_diff, we add UTIL_AVG_UNCHANGED flag, which
>>>> is the LSB, for task_util, but don't add the flag for util_est.enqueued.
>>>> However the enqueued's flag had been cleared when the task util changed.
>>>> As a result, we add +1 to the diff, this is therefore reducing slightly
>>>> UTIL_EST_MARGIN.
>>>
>>> Unless I miss something it actually depends on the situation, doesn't it?
>>>
>>> if ue.enqueued > task_util(), we remove 1 from the diff => UTIL_EST_MARGIN + 1
>>>
>>> if ue.enqueued < task_util(), we add 1 to the diff => UTIL_EST_MARGIN -1
>>
>> I get:
>>
>> ue.enqueued & UTIL_AVG_UNCHANGED = 0
>>
>> last_enqueued_diff = ue.enqueued_old - ue.enqueued_new
>>
>> last_enqueued_diff = (ue.enqueued | UTIL_AVG_UNCHANGED) - (task_util(p) | UTIL_AVG_UNCHANGED)
>>
>> ^^^^^^^^^^^^^^^^^^^^
>> added by patch
>>
>>
>> ue.enqueued_old didn't have the flag, otherwise would return earlier
>>
>> task_util(p) could have the LSB set but we just set it to make sure it's set
>>
>> So last_enqueued_diff is 1 larger.
>
> But we take the abs() of last_enqueued_diff.
>
> If we consider the following examples:
>
> enqueued_old = 5, enqueued_new = 9
> diff = 5 - (9 + 1) => 5 - 10 => -5
>
> enqueued_old = 9, enqueued_new = 5
> diff = 9 - (5 + 1) => 9 - 6 => 3
>
> In both cases the delta is supposed to be 4. But in the first case we end-up
> with 5. In the second, we end-up with 3. That's why I meant the effect on the
> diff depends on who's greater, ue.enqueued or task_util().
Ah, OK, due to the abs() in within_margin(). But util's LSB is lost due
to the flag anyway. Hence I assume e.g. enqueued_new = 9 should be
(task_util() = 8) + 1 (| flag) in the example.
OTHA, implementing UTIL_AVG_UNCHANGED as LSB and making this visible on
the util_est 'API' has other issues too. The condition
`!task_util_est(p)` can never be true in find_energy_efficient_cpu()
because of UTIL_AVG_UNCHANGED.
So why not use `UTIL_AVG_UNCHANGED = 0x80000000` and just keep its use
internal (between cfs_se_util_change() and util_est_update()), i.e. not
exporting it (via _task_util_est()) and not eclipsing util_est's LSB
value?
--->8---
From: Dietmar Eggemann <[email protected]>
Date: Fri, 5 Feb 2021 14:48:42 +0100
Subject: [PATCH] sched/fair: Fix util_est UTIL_AVG_UNCHANGED behaviour
The util_est internal UTIL_AVG_UNCHANGED flag which is used to prevent
unnecessary util_est updates uses the LSB of util_est.enqueued. It is
exposed via _task_util_est() (and task_util_est()).
Commit 92a801e5d5b7 ("sched/fair: Mask UTIL_AVG_UNCHANGED usages")
mentions that the LSB is lost for util_est resolution but
find_energy_efficient_cpu() checks if task_util_est() returns 0 to
return prev_cpu early.
Because of _task_util_est() returning the actual util est value or'ed w/
UTIL_AVG_UNCHANGED for a dequeued task this can never be true w/
SCHED_FEAT(UTIL_EST, true).
To fix this use the MSB of util_est.enqueued instead and keep the flag
util_est internal, i.e. don't export it via _task_util_est().
MSB of unsigned int util_est.enqueued shouldn't be used for a task
since the maximal possible util_avg value for a task is 1024.
As a caveat the code behind the util_est_se trace point has to filter
UTIL_AVG_UNCHANGED to see the real util_est.enqueued value which should
be easy to do.
Signed-off-by: Dietmar Eggemann <[email protected]>
---
kernel/sched/fair.c | 5 +++--
kernel/sched/pelt.h | 11 ++++++-----
2 files changed, 9 insertions(+), 7 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 1d75af1ecfb4..dd30e362c3cc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3902,7 +3902,7 @@ static inline unsigned long _task_util_est(struct task_struct *p)
{
struct util_est ue = READ_ONCE(p->se.avg.util_est);
- return (max(ue.ewma, ue.enqueued) | UTIL_AVG_UNCHANGED);
+ return max(ue.ewma, (ue.enqueued & ~UTIL_AVG_UNCHANGED));
}
static inline unsigned long task_util_est(struct task_struct *p)
@@ -4002,7 +4002,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
* Reset EWMA on utilization increases, the moving average is used only
* to smooth utilization decreases.
*/
- ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
+ ue.enqueued = task_util(p);
if (sched_feat(UTIL_EST_FASTUP)) {
if (ue.ewma < ue.enqueued) {
ue.ewma = ue.enqueued;
@@ -4051,6 +4051,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
ue.ewma += last_ewma_diff;
ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
done:
+ ue.enqueued |= UTIL_AVG_UNCHANGED;
WRITE_ONCE(p->se.avg.util_est, ue);
trace_sched_util_est_se_tp(&p->se);
diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
index 1462846d244e..476faf61f14a 100644
--- a/kernel/sched/pelt.h
+++ b/kernel/sched/pelt.h
@@ -43,13 +43,14 @@ static inline u32 get_pelt_divider(struct sched_avg *avg)
}
/*
- * When a task is dequeued, its estimated utilization should not be update if
- * its util_avg has not been updated at least once.
+ * When a task is dequeued, its estimated utilization should not be updated if
+ * its util_avg has not been updated in the meantime.
* This flag is used to synchronize util_avg updates with util_est updates.
- * We map this information into the LSB bit of the utilization saved at
- * dequeue time (i.e. util_est.dequeued).
+ * We map this information into the MSB bit of util_est.enqueued at dequeue
+ * time. Since max value of util_est.enqueued for a task is 1024 (PELT
+ * util_avg for a task) it is safe to use MSB here.
*/
-#define UTIL_AVG_UNCHANGED 0x1
+#define UTIL_AVG_UNCHANGED 0x80000000
static inline void cfs_se_util_change(struct sched_avg *avg)
{
--
2.25.1
[...]
> >
> > But we take the abs() of last_enqueued_diff.
> >
> > If we consider the following examples:
> >
> > enqueued_old = 5, enqueued_new = 9
> > diff = 5 - (9 + 1) => 5 - 10 => -5
> >
> > enqueued_old = 9, enqueued_new = 5
> > diff = 9 - (5 + 1) => 9 - 6 => 3
> >
> > In both cases the delta is supposed to be 4. But in the first case we end-up
> > with 5. In the second, we end-up with 3. That's why I meant the effect on the
> > diff depends on who's greater, ue.enqueued or task_util().
>
> Ah, OK, due to the abs() in within_margin(). But util's LSB is lost due
> to the flag anyway. Hence I assume e.g. enqueued_new = 9 should be
> (task_util() = 8) + 1 (| flag) in the example.
Yeah, I should have used an even number for the demonstration :-)
>
> OTHA, implementing UTIL_AVG_UNCHANGED as LSB and making this visible on
> the util_est 'API' has other issues too. The condition
> `!task_util_est(p)` can never be true in find_energy_efficient_cpu()
> because of UTIL_AVG_UNCHANGED.
>
> So why not use `UTIL_AVG_UNCHANGED = 0x80000000` and just keep its use
> internal (between cfs_se_util_change() and util_est_update()), i.e. not
> exporting it (via _task_util_est()) and not eclipsing util_est's LSB
> value?
As this would be fixing two issues at once, it's probably preferable.
[...]
> kernel/sched/fair.c | 5 +++--
> kernel/sched/pelt.h | 11 ++++++-----
> 2 files changed, 9 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 1d75af1ecfb4..dd30e362c3cc 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3902,7 +3902,7 @@ static inline unsigned long _task_util_est(struct task_struct *p)
> {
> struct util_est ue = READ_ONCE(p->se.avg.util_est);
>
> - return (max(ue.ewma, ue.enqueued) | UTIL_AVG_UNCHANGED);
> + return max(ue.ewma, (ue.enqueued & ~UTIL_AVG_UNCHANGED));
> }
>
> static inline unsigned long task_util_est(struct task_struct *p)
> @@ -4002,7 +4002,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> * Reset EWMA on utilization increases, the moving average is used only
> * to smooth utilization decreases.
> */
Needs to be updated to add:
last_enqueued_diff = ue.enqueued & ~UTIL_AVG_UNCHANGED;
> - ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
> + ue.enqueued = task_util(p);
> if (sched_feat(UTIL_EST_FASTUP)) {
> if (ue.ewma < ue.enqueued) {
> ue.ewma = ue.enqueued;
> @@ -4051,6 +4051,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> ue.ewma += last_ewma_diff;
> ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
> done:
> + ue.enqueued |= UTIL_AVG_UNCHANGED;
> WRITE_ONCE(p->se.avg.util_est, ue);
>
> trace_sched_util_est_se_tp(&p->se);
> diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
> index 1462846d244e..476faf61f14a 100644
On Sat, May 8, 2021 at 1:14 AM Vincent Donnefort
<[email protected]> wrote:
>
> [...]
>
> > >
> > > But we take the abs() of last_enqueued_diff.
> > >
> > > If we consider the following examples:
> > >
> > > enqueued_old = 5, enqueued_new = 9
> > > diff = 5 - (9 + 1) => 5 - 10 => -5
> > >
> > > enqueued_old = 9, enqueued_new = 5
> > > diff = 9 - (5 + 1) => 9 - 6 => 3
> > >
> > > In both cases the delta is supposed to be 4. But in the first case we end-up
> > > with 5. In the second, we end-up with 3. That's why I meant the effect on the
> > > diff depends on who's greater, ue.enqueued or task_util().
> >
> > Ah, OK, due to the abs() in within_margin(). But util's LSB is lost due
> > to the flag anyway. Hence I assume e.g. enqueued_new = 9 should be
> > (task_util() = 8) + 1 (| flag) in the example.
>
> Yeah, I should have used an even number for the demonstration :-)
>
> >
> > OTHA, implementing UTIL_AVG_UNCHANGED as LSB and making this visible on
> > the util_est 'API' has other issues too. The condition
> > `!task_util_est(p)` can never be true in find_energy_efficient_cpu()
> > because of UTIL_AVG_UNCHANGED.
> >
> > So why not use `UTIL_AVG_UNCHANGED = 0x80000000` and just keep its use
> > internal (between cfs_se_util_change() and util_est_update()), i.e. not
> > exporting it (via _task_util_est()) and not eclipsing util_est's LSB
> > value?
>
> As this would be fixing two issues at once, it's probably preferable.
>
> [...]
>
> > kernel/sched/fair.c | 5 +++--
> > kernel/sched/pelt.h | 11 ++++++-----
> > 2 files changed, 9 insertions(+), 7 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 1d75af1ecfb4..dd30e362c3cc 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -3902,7 +3902,7 @@ static inline unsigned long _task_util_est(struct task_struct *p)
> > {
> > struct util_est ue = READ_ONCE(p->se.avg.util_est);
> >
> > - return (max(ue.ewma, ue.enqueued) | UTIL_AVG_UNCHANGED);
> > + return max(ue.ewma, (ue.enqueued & ~UTIL_AVG_UNCHANGED));
> > }
> >
> > static inline unsigned long task_util_est(struct task_struct *p)
> > @@ -4002,7 +4002,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> > * Reset EWMA on utilization increases, the moving average is used only
> > * to smooth utilization decreases.
> > */
>
> Needs to be updated to add:
>
> last_enqueued_diff = ue.enqueued & ~UTIL_AVG_UNCHANGED;
The flag had been cleared before, otherwise would return earlier, so
there is no need to clear this flag again.
>
> > - ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED);
> > + ue.enqueued = task_util(p);
> > if (sched_feat(UTIL_EST_FASTUP)) {
> > if (ue.ewma < ue.enqueued) {
> > ue.ewma = ue.enqueued;
> > @@ -4051,6 +4051,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> > ue.ewma += last_ewma_diff;
> > ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
> > done:
> > + ue.enqueued |= UTIL_AVG_UNCHANGED;
> > WRITE_ONCE(p->se.avg.util_est, ue);
> >
> > trace_sched_util_est_se_tp(&p->se);
> > diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
> > index 1462846d244e..476faf61f14a 100644
> > >
> > > static inline unsigned long task_util_est(struct task_struct *p)
> > > @@ -4002,7 +4002,7 @@ static inline void util_est_update(struct cfs_rq *cfs_rq,
> > > * Reset EWMA on utilization increases, the moving average is used only
> > > * to smooth utilization decreases.
> > > */
> >
> > Needs to be updated to add:
> >
> > last_enqueued_diff = ue.enqueued & ~UTIL_AVG_UNCHANGED;
>
> The flag had been cleared before, otherwise would return earlier, so
> there is no need to clear this flag again.
Indeed, my bad. All good then.
--
Vincent