On Wed, Mar 21, 2018 at 7:48 AM, Rafael J. Wysocki <[email protected]> wrote:
> From: Rafael J. Wysocki <[email protected]>
>
> Add a new pointer argument to cpuidle_select() and to the ->select
> cpuidle governor callback to allow a boolean value indicating
> whether or not the tick should be stopped before entering the
> selected state to be returned from there.
>
> Make the ladder governor ignore that pointer (to preserve its
> current behavior) and make the menu governor return 'false" through
> it if:
> (1) the idle exit latency is constrained at 0, or
> (2) the selected state is a polling one, or
> (3) the expected idle period duration is within the tick period
> range.
>
> In addition to that, the correction factor computations in the menu
> governor need to take the possibility that the tick may not be
> stopped into account to avoid artificially small correction factor
> values. To that end, add a mechanism to record tick wakeups, as
> suggested by Peter Zijlstra, and use it to modify the menu_reflect()
> behavior when tick wakeup occurs. Namely, if the CPU is woken up by
> the tick, the predicted idle duration is likely too short, so make
> menu_reflect() try to compensate by bumping up the correction factor
> with a (sufficiently large) constant value.
>
> Since the value returned through the new argument pointer of
> cpuidle_select() is not used by its caller yet, this change by
> itself is not expected to alter the functionality of the code.
>
> Signed-off-by: Rafael J. Wysocki <[email protected]>
> ---
>
> Another variant of patch [5/8] to test.
>
> This one doesn't run menu_update() at all on tick wakeups, but simply
> bumps up the correction factor alone then.

I have overlooked one thing in this patch and in the original v7 of it.

Namely, tick wakeups occurring when the return value of
tick_nohz_get_sleep_length() is within the tick boundary should be
treated as normal wakeups, because the nohz code itself doesn't stop
the tick then even without this patch series.

I'll rework this patch for that and will send an update shortly.

Thanks!

2018-03-21 12:33:10

On 2018-03-28 12:56, Rafael J. Wysocki wrote:
> On Wed, Mar 28, 2018 at 12:37 PM, Rafael J. Wysocki <[email protected]> wrote:
>> On Wed, Mar 28, 2018 at 10:38 AM, Thomas Ilsche
>> <[email protected]> wrote:
>>> On 2018-03-28 10:13, Rafael J. Wysocki wrote:
>>>>
>
> [cut]
>
>>
>> So I do
>>
>> $ for cpu in 0 1 2 3; do taskset -c $cpu sh -c 'while true; do usleep
>> 500; done' & done
>>
>> which is a shell kind of imitation of the above and I cannot see this
>> issue at all.
>>
>> I count the number of times data->next_timer_us in menu_select() is
>> greater than TICK_USEC and while this "workload" is running, that
>> number is exactly 0.
>>
>> I'll try with a C program still.
>
> And with a C program I see data->next_timer_us greater than TICK_USEC
> while it is running, so let me dig deeper.
>

I can confirm that a shell-loop behaves differently like you describe.
Even if it's just a shell-loop calling "main{usleep(500);}" binary.

Attachments:

smime.p7s (5.09 kB)
S/MIME Cryptographic Signature

2018-03-28 20:42:46

by Doug Smythies

[permalink] [raw]

Subject: RE: [RFT][PATCH v7 6/8] sched: idle: Select idle state before stopping the tick

On 2018.03.28 08:15 Thomas Ilsche wrote:
> On 2018-03-28 12:56, Rafael J. Wysocki wrote:
>> On Wed, Mar 28, 2018 at 12:37 PM, Rafael J. Wysocki <[email protected]> wrote:
>>> On Wed, Mar 28, 2018 at 10:38 AM, Thomas Ilsche
>>> <[email protected]> wrote:
>>>> On 2018-03-28 10:13, Rafael J. Wysocki wrote:
>>>>>
>>
>> [cut]
>>
>>>
>>> So I do
>>>
>>> $ for cpu in 0 1 2 3; do taskset -c $cpu sh -c 'while true; do usleep
>>> 500; done' & done
>>>
>>> which is a shell kind of imitation of the above and I cannot see this
>>> issue at all.
>>>
>>> I count the number of times data->next_timer_us in menu_select() is
>>> greater than TICK_USEC and while this "workload" is running, that
>>> number is exactly 0.
>>>
>>> I'll try with a C program still.
>>
>> And with a C program I see data->next_timer_us greater than TICK_USEC
>> while it is running, so let me dig deeper.
>>
>
> I can confirm that a shell-loop behaves differently like you describe.
> Even if it's just a shell-loop calling "main{usleep(500);}" binary.

I normally use the C program method.
The timer there returns with the need_sched() flag set.

I do not seem to have usleep on my system, but when using sleep in a
shell loop, the timer returns without the need_resched() flag set.

Most of my test results involving varying the value of
POLL_IDLE_COUNT are total garbage, because I was using the
C program method, and thus exiting the poll_idle loop based
on the need_resched() flag and not the POLL_IDLE_COUNT
setting.

I don't know if I can re-do the work, because I
do not have a good way to get my system to use Idle
State 0 with any real workflow, and I seem to get into
side effect issues when I disable other idle states to
force more use of idle state 0.

... Doug

2018-03-28 23:12:21

by Rafael J. Wysocki

[permalink] [raw]

Subject: Re: [RFT][PATCH v7 6/8] sched: idle: Select idle state before stopping the tick

On Wed, Mar 28, 2018 at 10:41 PM, Doug Smythies <[email protected]> wrote:
> On 2018.03.28 08:15 Thomas Ilsche wrote:
>> On 2018-03-28 12:56, Rafael J. Wysocki wrote:
>>> On Wed, Mar 28, 2018 at 12:37 PM, Rafael J. Wysocki <[email protected]> wrote:
>>>> On Wed, Mar 28, 2018 at 10:38 AM, Thomas Ilsche
>>>> <[email protected]> wrote:
>>>>> On 2018-03-28 10:13, Rafael J. Wysocki wrote:
>>>>>>
>>>
>>> [cut]
>>>
>>>>
>>>> So I do
>>>>
>>>> $ for cpu in 0 1 2 3; do taskset -c $cpu sh -c 'while true; do usleep
>>>> 500; done' & done
>>>>
>>>> which is a shell kind of imitation of the above and I cannot see this
>>>> issue at all.
>>>>
>>>> I count the number of times data->next_timer_us in menu_select() is
>>>> greater than TICK_USEC and while this "workload" is running, that
>>>> number is exactly 0.
>>>>
>>>> I'll try with a C program still.
>>>
>>> And with a C program I see data->next_timer_us greater than TICK_USEC
>>> while it is running, so let me dig deeper.
>>>
>>
>> I can confirm that a shell-loop behaves differently like you describe.
>> Even if it's just a shell-loop calling "main{usleep(500);}" binary.
>
> I normally use the C program method.
> The timer there returns with the need_sched() flag set.

I found the problem, but addressing it will not be straightforward,
which is kind of unfortunate.

Namely, get_next_timer_interrupt() doesn't take high resolution timers
into account if they are enabled (which I overlooked), but they
obviously need to be taken into account in
tick_nohz_get_sleep_length(), so calling tick_nohz_next_event() in
there is not sufficient.

Moreover, it needs to know the next highres timer not including the
tick and that's not so easy to get. It is doable, though, AFAICS.

2018-03-30 09:41:53

by Rafael J. Wysocki

[permalink] [raw]

Subject: Re: [RFT][PATCH v7.3 5/8] cpuidle: Return nohz hint from cpuidle_select()

On Wednesday, March 28, 2018 11:14:36 AM CEST Thomas Ilsche wrote:
> On 2018-03-22 18:40, Rafael J. Wysocki wrote:
> > From: Rafael J. Wysocki <[email protected]>
> >
> > Add a new pointer argument to cpuidle_select() and to the ->select
> > cpuidle governor callback to allow a boolean value indicating
> > whether or not the tick should be stopped before entering the
> > selected state to be returned from there.
> >
> > Make the ladder governor ignore that pointer (to preserve its
> > current behavior) and make the menu governor return 'false" through
> > it if:
> > (1) the idle exit latency is constrained at 0, or
> > (2) the selected state is a polling one, or
> > (3) the expected idle period duration is within the tick period
> > range.
> >
> > In addition to that, the correction factor computations in the menu
> > governor need to take the possibility that the tick may not be
> > stopped into account to avoid artificially small correction factor
> > values. To that end, add a mechanism to record tick wakeups, as
> > suggested by Peter Zijlstra, and use it to modify the menu_update()
> > behavior when tick wakeup occurs. Namely, if the CPU is woken up by
> > the tick and the return value of tick_nohz_get_sleep_length() is not
> > within the tick boundary, the predicted idle duration is likely too
> > short, so make menu_update() try to compensate for that by updating
> > the governor statistics as though the CPU was idle for a long time.
> >
> > Since the value returned through the new argument pointer of
> > cpuidle_select() is not used by its caller yet, this change by
> > itself is not expected to alter the functionality of the code.
> >
> > Signed-off-by: Rafael J. Wysocki <[email protected]>
> > ---
> >
> > One more revision here.
> >
> > From the Thomas Ilsche's testing on the Skylake server it looks like
> > data->intervals[] need to be updated along with the correction factor
> > on tick wakeups that occur when next_timer_us is above the tick boundary.
> >
> > The difference between this and the original v7 (of patch [5/8]) is
> > what happens in menu_update(). This time next_timer_us is checked
> > properly and if that is above the tick boundary and a tick wakeup occurs,
> > the function simply sets mesured_us to a large constant and uses that to
> > update both the correction factor and data->intervals[] (the particular
> > value used in this patch was found through a bit of experimentation).
> >
> > Let's see how this works for Thomas and Doug.
> >
> > For easier testing there is a git branch containing this patch (and the
> > rest of the series) at:
> >
> > git://git.kernel.org/pub/scm/linux/kernel/git/rafael/linux-pm.git \
> > idle-loop-v7.3
> >
> > Thanks!
>
> Besides the other issue with tick_nohz_get_sleep_length, v7.3
> generally works well in idle.

Great, thanks!

> So far I don't see anything
> statistically noticeable, but I saw one peculiar anomaly. After all
> cores woke up simultaneously to schedule some kworker task, some of
> them kept the sched tick up, even stayed in shallow sleep state for a
> while, without having any tasks scheduled. Gradually they chose deeper
> sleep states and stopped their sched ticks. After 23 ms (1000 Hz
> kernel), they all went back to deep sleep.
>
> https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v7_3_skl_sp_anomaly.png
>
> I have only seen this once so far and can't reproduce it yet, so this
> particular instance may not be an issue in practice.

OK

> However my fundamental concerns about the policy whether to disable the sched
> tick remain:
>
> Mixing the precise timer and vague heuristic for the decision is
> dangerous. The timer should not be wrong, heuristic may be.

Well, I wouldn't say "dangerous". It may be suboptimal, but even that is not
a given. Besides ->

> Decisions should use actual time points rather than the generic tick
> duration and residency time. e.g.
> expected_interval < delta_next_us
> vs
> expected_interval < TICK_USEC

-> the role of this check is to justify taking the overhead of stopping the
tick and it certainly is justifiable if the governor doesn't anticipate any
wakeups (timer or not) in the TICK_USEC range. It may be justifiable in
other cases too, but that's a matter of some more complex checks and may not
be worth the extra complexity at all.

> For some cases the unmodified sched tick is not efficient as fallback.
> Is it feasible to
> 1) enable the sched tick when it's currently disabled instead of
> blindly choosing a different C state?

It is not "blindly" if you will. It is very much "consciously". :-)

Restarting the tick from within menu_select() wouldn't work IMO and
restarting it from cpuidle_idle_call() every time it was stopped might
be wasteful.

It could be done, but AFAICS if the CPU in deep idle is woken up by an
occasional interrupt that doesn't set need_resched, it is more likely
to go into deep idle again than to go into shallow idle at that point.

> 2) modify the next upcoming sched tick to be better suitable as
> fallback timer?

Im not sure what you mean.

> I think with the infrastructure changes it should be possible to
> implement the policy I envisioned previously
> (https://marc.info/?l=linux-pm&m=151384941425947&w=2), which is based
> on the ordering of timers and the heuristically predicted idle time.
> If the sleep_length issue is fixed and I have some mechanism for a
> modifiable fallback timer, I'll try to demonstrate that on top of your
> changes.

Sure. I'm not against adding more complexity to this in principle, but there
needs to be a good enough justification for it.

As I said in one of the previous messages, if simple code gets the job done,
the extra complexity may just not be worth it. That's why I went for very
simple code here. Still, if there is a clear case for making it more complex,
that can be done.

Thanks!

2018-04-10 15:28:03

by Thomas Ilsche

[permalink] [raw]

Subject: Re: [RFT][PATCH v7.3 5/8] cpuidle: Return nohz hint from cpuidle_select()

>> However my fundamental concerns about the policy whether to disable the sched
>> tick remain:
>>
>> Mixing the precise timer and vague heuristic for the decision is
>> dangerous. The timer should not be wrong, heuristic may be.
>
> Well, I wouldn't say "dangerous". It may be suboptimal, but even that is not
> a given. Besides ->
>
>> Decisions should use actual time points rather than the generic tick
>> duration and residency time. e.g.
>> expected_interval < delta_next_us
>> vs
>> expected_interval < TICK_USEC
>
> -> the role of this check is to justify taking the overhead of stopping the
> tick and it certainly is justifiable if the governor doesn't anticipate any
> wakeups (timer or not) in the TICK_USEC range. It may be justifiable in
> other cases too, but that's a matter of some more complex checks and may not
> be worth the extra complexity at all.

I tried that change. It's just just a bit bulky because I
cache the result of ktime_to_us(delta_next) early.

diff --git a/drivers/cpuidle/governors/menu.c b/drivers/cpuidle/governors/menu.c
index a6eca02..cad87bf 100644
--- a/drivers/cpuidle/governors/menu.c
+++ b/drivers/cpuidle/governors/menu.c
@@ -296,6 +296,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
unsigned long nr_iowaiters, cpu_load;
int resume_latency = dev_pm_qos_raw_read_value(device);
ktime_t delta_next;
+ unsigned long delta_next_us;

if (data->needs_update) {
menu_update(drv, dev);
@@ -314,6 +315,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,

/* determine the expected residency time, round up */
data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length(&delta_next));
+ delta_next_us = ktime_to_us(delta_next);

get_iowait_load(&nr_iowaiters, &cpu_load);
data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
@@ -364,7 +366,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
*/
if (data->predicted_us < TICK_USEC)
data->predicted_us = min_t(unsigned int, TICK_USEC,
- ktime_to_us(delta_next));
+ delta_next_us);
} else {
/*
* Use the performance multiplier and the user-configurable
@@ -412,9 +414,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
* expected idle duration is shorter than the tick period length.
*/
if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||
- expected_interval < TICK_USEC) {
- unsigned int delta_next_us = ktime_to_us(delta_next);
-
+ expected_interval < delta_next_us) {
*stop_tick = false;

if (!tick_nohz_tick_stopped() && idx > 0 &&

This works as a I expect in the sense of stopping the tick more often
and allowing deeper sleep states in some cases. However, it
drastically *increases* the power consumption for some affected
workloads test system (SKL-SP).

So while I believe this generally improves the behavior - I can't
recommend it based on the practical implications. Below are some
details for the curious:

power consumption for various workload configurations with 250 Hz
kernels 4.16.0, v9, v9+delta_next patch:
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v9_250_Hz_power.png

Practically v9 has the best power consumption in most cases.

The following detailed looks are with 1000 Hz kernels.
v9 with a synchronized 950 us sleep workload:
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v9_poll_sync.png
v9 with a staggered 950 us sleep workload:
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v9_poll_stagger.png

Both show that the sched tick is kept on and this causes more requests
to C1E than C6

v9+delta_next with a synchronized 950 us sleep workload:
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v9_delta_poll_sync.png
v9+delta_next with a staggered 950 us sleep workload:
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v9_delta_poll_stagger.png

No more sched tick, no more C1E requests, but increased power.

Besides:
- the hardware reports 0 residency in C6 (both core and PKG) for
both v9 and v9+delta_next_us.
- the increased power consumption comes after a ramp-up of ~200 ms
for the staggered and ~2 s for the synchronized workload.

For reference traces from an unmodified 4.16.0:

https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v4.16.0_poll_sync.png
https://wwwpub.zih.tu-dresden.de/~tilsche/powernightmares/v4.16.0_poll_stagger.png

It behaves similar to the delta_next patch but does not show the
increased power consumption in this exact workload configuration.

I couldn't help to dig into the effect a bit more and am able to
reproduce it even under unmodified kernels with staggered sleep cycles
between ~1.2 ms and ~2.5 ms where power is increased by > 40 W.

Anyway, this effect seems to be beyond what the governor should
consider. It is an example where it doesn't seem possible to decide
for the optimal C state without considering the state of other cores
and such unexpected hardware behavior.
And these are only the results from one system and a limited set of
workload configurations.

>> For some cases the unmodified sched tick is not efficient as fallback.
>> Is it feasible to
>> 1) enable the sched tick when it's currently disabled instead of
>> blindly choosing a different C state?
>
> It is not "blindly" if you will. It is very much "consciously". :-)
>
> Restarting the tick from within menu_select() wouldn't work IMO and
> restarting it from cpuidle_idle_call() every time it was stopped might
> be wasteful.
>
> It could be done, but AFAICS if the CPU in deep idle is woken up by an
> occasional interrupt that doesn't set need_resched, it is more likely
> to go into deep idle again than to go into shallow idle at that point.
>
>> 2) modify the next upcoming sched tick to be better suitable as
>> fallback timer?
>
> Im not sure what you mean.
>
>> I think with the infrastructure changes it should be possible to
>> implement the policy I envisioned previously
>> (https://marc.info/?l=linux-pm&m=151384941425947&w=2), which is based
>> on the ordering of timers and the heuristically predicted idle time.
>> If the sleep_length issue is fixed and I have some mechanism for a
>> modifiable fallback timer, I'll try to demonstrate that on top of your
>> changes.
>
> Sure. I'm not against adding more complexity to this in principle, but there
> needs to be a good enough justification for it.
>
> As I said in one of the previous messages, if simple code gets the job done,
> the extra complexity may just not be worth it. That's why I went for very
> simple code here. Still, if there is a clear case for making it more complex,
> that can be done.
>
> Thanks!
>