tick/nohz updates

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 9 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

Quoted 5 lines

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

Quoted 16 lines · Peter Zijlstra

Quoted 14 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 2 lines

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

There are already two callers and potentially two return values to check for each because the function returns two values.

I'd rather make the API more robust instead of fixing each callers and worrying about future ones.

Quoted 17 lines · Frederic Weisbecker

Quoted 16 lines · Peter Zijlstra

Quoted 14 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 8 lines

Quoted 2 lines

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

There are already two callers and potentially two return values to check for each because the function returns two values.

I'd rather make the API more robust instead of fixing each callers and worrying about future ones.

But what's the actual problem? The Changelog doesn't say why returning a negative value is a problem, and in fact the return value is explicitly signed.

Anyway, I don't terribly mind the patch, I was just confused by the lack of actual justification.

Quoted 28 lines · Peter Zijlstra

Quoted 16 lines · Frederic Weisbecker

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 7 lines

Quoted 2 lines

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

There are already two callers and potentially two return values to check for each because the function returns two values.

I'd rather make the API more robust instead of fixing each callers and worrying about future ones.

But what's the actual problem? The Changelog doesn't say why returning a negative value is a problem, and in fact the return value is explicitly signed.

Quoted 2 lines

Anyway, I don't terribly mind the patch, I was just confused by the lack of actual justification.

And you're right, the motivation is pure FUD: I don't know exactly how the cpuidle governors may react to such negative values and so this is just to prevent from potential accident.

Rafael, does that look harmless to you?

Quoted 28 lines · Peter Zijlstra

Quoted 16 lines · Frederic Weisbecker

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 7 lines

Quoted 2 lines

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

There are already two callers and potentially two return values to check for each because the function returns two values.

I'd rather make the API more robust instead of fixing each callers and worrying about future ones.

But what's the actual problem? The Changelog doesn't say why returning a negative value is a problem, and in fact the return value is explicitly signed.

Quoted 2 lines

Anyway, I don't terribly mind the patch, I was just confused by the lack of actual justification.

And you're right, the motivation is pure FUD: I don't know exactly how the cpuidle governors may react to such negative values and so this is just to prevent from potential accident.

Rafael, does that look harmless to you?

Quoted 28 lines · Peter Zijlstra

Quoted 16 lines · Frederic Weisbecker

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Frederic Weisbecker

From: "Zhou Ti (x2019cwm)" <[email protected]>

If the hardware clock happens to fire its interrupts late, two possible issues can happen while calling tick_nohz_get_sleep_length(). Either:

1) The next clockevent device event is due past the last idle entry time.

or:

2) The last timekeeping update happened before the last idle entry time and the next timer callback expires before the last idle entry time.

Make sure that both cases are handled to avoid returning a negative duration to the cpuidle governors.

Quoted 7 lines

Quoted 2 lines

Why? ... and wouldn't it be cheaper the fix the caller to check negative once, instead of adding two branches here?

There are already two callers and potentially two return values to check for each because the function returns two values.

I'd rather make the API more robust instead of fixing each callers and worrying about future ones.

But what's the actual problem? The Changelog doesn't say why returning a negative value is a problem, and in fact the return value is explicitly signed.

Quoted 2 lines

Anyway, I don't terribly mind the patch, I was just confused by the lack of actual justification.

And you're right, the motivation is pure FUD: I don't know exactly how the cpuidle governors may react to such negative values and so this is just to prevent from potential accident.

Rafael, does that look harmless to you?

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Quoted 4 lines · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing in e-mail?

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

---
 drivers/cpuidle/governors/teo.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================

drivers/cpuidle/governors/teo.c +4 -4

@@ -100,8 +100,8 @@ struct teo_idle_state {
  * @intervals: Saved idle duration values.
  */
 struct teo_cpu {
-       u64 time_span_ns;
-       u64 sleep_length_ns;
+       s64 time_span_ns;
+       s64 sleep_length_ns;
        struct teo_idle_state states[CPUIDLE_STATE_MAX];
        int interval_idx;
        u64 intervals[INTERVALS];

@@ -216,7 +216,7 @@ static bool teo_time_ok(u64 interval_ns)
  */
 static int teo_find_shallower_state(struct cpuidle_driver *drv,
                                    struct cpuidle_device *dev, int state_idx,
-                                   u64 duration_ns)
+                                   s64 duration_ns)
 {
        int i;
 

@@ -242,7 +242,7 @@ static int teo_select(struct cpuidle_dri
 {
        struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
        s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
-       u64 duration_ns;
+       s64 duration_ns;
        unsigned int hits, misses, early_hits;
        int max_early_idx, prev_max_early_idx, constraint_idx, idx, i;
        ktime_t delta_tick;

Quoted 16 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

So at least in this case there is no need to add any new branches anywhere.

Quoted 2 lines

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 38 lines

---
 drivers/cpuidle/governors/teo.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================

drivers/cpuidle/governors/teo.c +4 -4

@@ -100,8 +100,8 @@ struct teo_idle_state {
  * @intervals: Saved idle duration values.
  */
 struct teo_cpu {
-       u64 time_span_ns;
-       u64 sleep_length_ns;
+       s64 time_span_ns;
+       s64 sleep_length_ns;
        struct teo_idle_state states[CPUIDLE_STATE_MAX];
        int interval_idx;
        u64 intervals[INTERVALS];

@@ -216,7 +216,7 @@ static bool teo_time_ok(u64 interval_ns)
  */
 static int teo_find_shallower_state(struct cpuidle_driver *drv,
                                    struct cpuidle_device *dev, int state_idx,
-                                   u64 duration_ns)
+                                   s64 duration_ns)
 {
        int i;
 

@@ -242,7 +242,7 @@ static int teo_select(struct cpuidle_dri
 {
        struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
        s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
-       u64 duration_ns;
+       s64 duration_ns;
        unsigned int hits, misses, early_hits;
        int max_early_idx, prev_max_early_idx, constraint_idx, idx, i;
        ktime_t delta_tick;

Quoted 24 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

Quoted 2 lines

1. This function is called multiple times in menu governor and TEO governor.

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

Quoted 4 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

Quoted 30 lines · On Thu, Mar 25, 2021 at 9:37 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 7 lines

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

That obviously depends on the governor, but both teo and menu call it once per cycle.

Quoted 20 lines

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 7 lines

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

Of course this depends on the governor.

Quoted 2 lines

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

You need to remember that the governor code runs in the idle loop context which is expected to be reasonably fast.

That's why we are worrying about individual branches here.

Quoted 3 lines

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

So I'm not sure what the problem with adding an upfront negative value check to the governor is.

Quoted 5 lines

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

It ultimately depends on the governor, which is why I think that the negative value check should be done by the governor, if needed, and not by the function called by it, because in the latter case the check may be redundant and we end up with an extra branch (or two branches in this particular case) for no good reason whatsoever.

Yes, there are governors which simply can do the negative value check upfront right after calling that function and ensure that they will not deal with negative values going forward. This is probably what I'll do in the menu case.

However, if the governor is simple enough and it can avoid doing the explicit negative value check, I don't see a reason to do that check elsewhere "just in case".

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

Quoted 104 lines · Rafael J. Wysocki

Quoted 30 lines · On Thu, Mar 25, 2021 at 9:37 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 7 lines

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

That obviously depends on the governor, but both teo and menu call it once per cycle.

Quoted 20 lines

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 7 lines

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

Of course this depends on the governor.

Quoted 2 lines

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

You need to remember that the governor code runs in the idle loop context which is expected to be reasonably fast.

That's why we are worrying about individual branches here.

Quoted 3 lines

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

So I'm not sure what the problem with adding an upfront negative value check to the governor is.

Quoted 5 lines

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

It ultimately depends on the governor, which is why I think that the negative value check should be done by the governor, if needed, and not by the function called by it, because in the latter case the check may be redundant and we end up with an extra branch (or two branches in this particular case) for no good reason whatsoever.

Yes, there are governors which simply can do the negative value check upfront right after calling that function and ensure that they will not deal with negative values going forward. This is probably what I'll do in the menu case.

Quoted 3 lines

However, if the governor is simple enough and it can avoid doing the explicit negative value check, I don't see a reason to do that check elsewhere "just in case".

Makes sense. I will submit my patch to fix this issue in menu and TEO.

Quoted 110 lines · On Fri, Mar 26, 2021 at 6:53 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 107 lines · Rafael J. Wysocki

Quoted 30 lines · On Thu, Mar 25, 2021 at 9:37 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 7 lines

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

That obviously depends on the governor, but both teo and menu call it once per cycle.

Quoted 20 lines

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 7 lines

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

Of course this depends on the governor.

Quoted 2 lines

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

You need to remember that the governor code runs in the idle loop context which is expected to be reasonably fast.

That's why we are worrying about individual branches here.

Quoted 3 lines

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

So I'm not sure what the problem with adding an upfront negative value check to the governor is.

Quoted 5 lines

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

It ultimately depends on the governor, which is why I think that the negative value check should be done by the governor, if needed, and not by the function called by it, because in the latter case the check may be redundant and we end up with an extra branch (or two branches in this particular case) for no good reason whatsoever.

Yes, there are governors which simply can do the negative value check upfront right after calling that function and ensure that they will not deal with negative values going forward. This is probably what I'll do in the menu case.

However, if the governor is simple enough and it can avoid doing the explicit negative value check, I don't see a reason to do that check elsewhere "just in case".

Quoted 1 line

Makes sense. I will submit my patch to fix this issue in menu and TEO.

Well, I have patches for that already and they are not super-straightforward. Though If you want to try to fix this yourself, I'll wait for your submission.

Quoted 111 lines · Rafael J. Wysocki

Quoted 110 lines · On Fri, Mar 26, 2021 at 6:53 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 107 lines · Rafael J. Wysocki

Quoted 30 lines · On Thu, Mar 25, 2021 at 9:37 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 7 lines

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

That obviously depends on the governor, but both teo and menu call it once per cycle.

Quoted 20 lines

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 7 lines

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

Of course this depends on the governor.

Quoted 2 lines

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

You need to remember that the governor code runs in the idle loop context which is expected to be reasonably fast.

That's why we are worrying about individual branches here.

Quoted 3 lines

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

So I'm not sure what the problem with adding an upfront negative value check to the governor is.

Quoted 5 lines

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

It ultimately depends on the governor, which is why I think that the negative value check should be done by the governor, if needed, and not by the function called by it, because in the latter case the check may be redundant and we end up with an extra branch (or two branches in this particular case) for no good reason whatsoever.

Yes, there are governors which simply can do the negative value check upfront right after calling that function and ensure that they will not deal with negative values going forward. This is probably what I'll do in the menu case.

However, if the governor is simple enough and it can avoid doing the explicit negative value check, I don't see a reason to do that check elsewhere "just in case".

Quoted 5 lines

Quoted 1 line

Makes sense. I will submit my patch to fix this issue in menu and TEO.

Well, I have patches for that already and they are not super-straightforward. Though If you want to try to fix this yourself, I'll wait for your submission.

Thanks! I really like this subsystem, so I hope to contribute a little. I still have some questions.

For TEO governor:
Even if we change some datatypes as your patch did before, some explicit type conversions still need to be added to prevent wrong results.

For example:
line 276 (because 1u > -1 will be false)
line 329
line 422

Since some of them are in a loop, does the overhead caused by the type conversions worth it? or do I need to do some pre-processing to avoid duplicate conversions (which may cause additional space overhead) ?

For menu governor:
If we simply change the datatypes, the conversions required are even more.

    For example:
        lines 133-142
        line 202
        line 289
        lines 302-309
        line 320
        lines 327-328
        line 347

    If we just do exception handling on next_timer_ns and delta_next,
    that still requires two additional branches.

Quoted 119 lines · On Fri, Mar 26, 2021 at 11:53 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 111 lines · Rafael J. Wysocki

Quoted 110 lines · On Fri, Mar 26, 2021 at 6:53 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 107 lines · Rafael J. Wysocki

Quoted 30 lines · On Thu, Mar 25, 2021 at 9:37 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 28 lines · Rafael J. Wysocki

Quoted 26 lines · On Thu, Mar 25, 2021 at 8:18 PM Zhou Ti (x2019cwm) <[email protected]> wrote:

Quoted 14 lines · Rafael J. Wysocki

Quoted 5 lines · CET Frederic Weisbecker

Quoted 1 line · On Tue, Mar 16, 2021 at 04:08:08PM +0000, Zhou Ti (x2019cwm) wrote:

But I don't think it's a good idea to handle this in callers, because logically the function shouldn't return negative values. Returning 0 directly would allow idle governors to get another chance to select again.

Hmm, I'm going to leave the last word to Rafael since cpuidle are the only callers of this. In any case we need to fix it.

Yes, we do.

So I said that I preferred to address this in the callers and the reason why is because, for example, for the teo governor it would be a matter of using a different data type to store the tick_nohz_get_sleep_length() return value, like in the (untested) patch below.

Quoted 4 lines

So at least in this case there is no need to add any new branches anywhere.

I'm still not sure about menu, because it is more complicated, but even if that one needs an extra branch, that is a win already.

I would like to point out the potential trouble that fixing this issue in the callers could cause.

1. This function is called multiple times in menu governor and TEO governor.

Quoted 7 lines

Quoted 4 lines

What do you mean by "multiple times"?

Each of the governors calls it once per cycle and its previous return value is not used in the next cycle at least in teo.

I remember a governor called this function twice in a cycle, I guess I remember wrong.

That obviously depends on the governor, but both teo and menu call it once per cycle.

Quoted 20 lines

Quoted 20 lines

Quoted 3 lines

I'm not sure that receiving results using signed integers is enough to solve all the problems, in the worst case it may require increasing the logical complexity of the code.

That is a valid concern, so it is a tradeoff between increasing the logical complexity of the code and adding branches to it.

Quoted 3 lines

2. This function is important for developing idle governor. If the problem is not fixed in the function itself, then this potential pitfall should be explicitly stated in the documentation.

That I can agree with.

Quoted 6 lines

This is because
it is difficult to predict from the definition and naming of the function that it might return a negative number. I actually discovered this anomaly when I was doing data analysis on my own idle governor. For some idle control algorithms, this exception return could lead to serious consequences, because negative return logically won't happen.

Quoted 7 lines

Quoted 2 lines

Well, it's a matter of how to take the possible negative return value into account so it does not affect the result of the computations.

I think it is challenging for some algorithms to take negative return values into account properly. For TEO (and even menu), it is possible to solve the problem by just changing the way the data is received is because the learning mechanism for both algorithms is simple.

Of course this depends on the governor.

Quoted 2 lines

One of the interesting things about the CPUIdle subsystem is that it is well suited to introduce machine learning and probabilistic statistical methods.

You need to remember that the governor code runs in the idle loop context which is expected to be reasonably fast.

That's why we are worrying about individual branches here.

Quoted 3 lines

This means that many of the more complex and data-sensitive algorithms can potentially be explored. In the best case we will still need to add additional code complexity to a new algorithm.

So I'm not sure what the problem with adding an upfront negative value check to the governor is.

Quoted 5 lines

It would reduce a lot of unnecessary considerations (for example, highlight this shortcoming in the documentation) if we could ensure that this function would work as it is logically defined. But I don't really understand how much of a burden adding an extra branch would impose, so I don't know if this tradeoff is worth it.

It ultimately depends on the governor, which is why I think that the negative value check should be done by the governor, if needed, and not by the function called by it, because in the latter case the check may be redundant and we end up with an extra branch (or two branches in this particular case) for no good reason whatsoever.

Yes, there are governors which simply can do the negative value check upfront right after calling that function and ensure that they will not deal with negative values going forward. This is probably what I'll do in the menu case.

However, if the governor is simple enough and it can avoid doing the explicit negative value check, I don't see a reason to do that check elsewhere "just in case".

Quoted 5 lines

Quoted 1 line

Makes sense. I will submit my patch to fix this issue in menu and TEO.

Well, I have patches for that already and they are not super-straightforward. Though If you want to try to fix this yourself, I'll wait for your submission.

Quoted 6 lines

Thanks! I really like this subsystem, so I hope to contribute a little. I still have some questions.

For TEO governor:
Even if we change some datatypes as your patch did before, some explicit type conversions still need to be added to prevent wrong results.

That's true. That patch was way incomplete and I would start with changing the data type of exit_latency_ns and target_residency_ns in struct cpuidle_state to s64 for this reason.

Quoted 8 lines

For example:
line 276 (because 1u > -1 will be false)
line 329
line 422

Since some of them are in a loop, does the overhead caused by the type conversions worth it? or do I need to do some pre-processing to avoid duplicate conversions (which may cause additional space overhead) ?

Well, it looks like it may be better if I send my patches after all, because it will take less time overall than me explaining here what I would do. Let me do that.

Quoted 2 lines

For menu governor:
If we simply change the datatypes, the conversions required are even more.

I would add a negative return value check to menu as I said before.

Not really AFAICS, but again let me send a patch to illustrate my point.

Optimize further the check for local full dynticks CPU. Testing directly tick_nohz_full_cpu(smp_processor_id()) is suboptimal because the compiler first fetches the CPU number and only then processes the static key.

It's best to evaluate the static branch before anything.

Quoted 6 lines · Frederic Weisbecker

Optimize further the check for local full dynticks CPU. Testing directly tick_nohz_full_cpu(smp_processor_id()) is suboptimal because the compiler first fetches the CPU number and only then processes the static key.

It's best to evaluate the static branch before anything.

Or you do tricky things like this ;-)

include/linux/tick.h +6 -7

index 7340613c7eff..bd4a6b055b80 100644
@@ -185,13 +185,12 @@ static inline bool tick_nohz_full_enabled(void)
 	return tick_nohz_full_running;
 }
 
-static inline bool tick_nohz_full_cpu(int cpu)
-{
-	if (!tick_nohz_full_enabled())
-		return false;
-
-	return cpumask_test_cpu(cpu, tick_nohz_full_mask);
-}
+#define tick_nohz_full_cpu(_cpu) ({					\
+	bool __ret = false;						\
+	if (tick_nohz_full_enabled())					\
+		__ret = cpumask_test_cpu((_cpu), tick_nohz_full_mask);	\
+	__ret;								\
+})
 
 static inline void tick_nohz_full_add_cpus_to(struct cpumask *mask)
 {

Enqueuing a local timer after the tick has been stopped will result in the timer being ignored until the next random interrupt.

Perform sanity checks to report these situations.

Reviewed-by Rafael J. Wysocki <[email protected]>

Signed-off-by Frederic Weisbecker <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Paul E. McKenney <[email protected]>

---
 kernel/sched/core.c | 20 +++++++++++++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

kernel/sched/core.c +16 -0

index ca2bb629595f..24552911f92b 100644
@@ -674,6 +674,22 @@ int get_nohz_timer_target(void)
 	return cpu;
 }
 
+/* Make sure the timer won't be ignored in dynticks-idle case */
+static void wake_idle_assert_possible(void)
+{
+#ifdef CONFIG_SCHED_DEBUG
+	/*
+	 * Timers are re-evaluated after idle IRQs. In case of softirq,
+	 * we assume IRQ tail. Ksoftirqd shouldn't reach here as the
+	 * timer base wouldn't be idle. And inline softirq processing
+	 * after a call to local_bh_enable() within idle loop sound too
+	 * fun to be considered here.
+	 */
+	WARN_ONCE(in_task(),
+		  "Late timer enqueue may be ignored\n");
+#endif
+}
+
 /*
  * When add_timer_on() enqueues a timer into the timer wheel of an
  * idle CPU then this timer might expire before the next timer event

@@ -688,8 +704,10 @@ static void wake_up_idle_cpu(int cpu)
 {

Quoted 52 lines · Frederic Weisbecker

Enqueuing a local timer after the tick has been stopped will result in the timer being ignored until the next random interrupt.

Perform sanity checks to report these situations.

Reviewed-by Rafael J. Wysocki <[email protected]>

Signed-off-by Frederic Weisbecker <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Paul E. McKenney <[email protected]>

---
 kernel/sched/core.c | 20 +++++++++++++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

kernel/sched/core.c +19 -1

index ca2bb629595f..24552911f92b 100644
@@ -674,6 +674,22 @@ int get_nohz_timer_target(void)
 	return cpu;
 }
 
+/* Make sure the timer won't be ignored in dynticks-idle case */
+static void wake_idle_assert_possible(void)
+{
+#ifdef CONFIG_SCHED_DEBUG
+	/*
+	 * Timers are re-evaluated after idle IRQs. In case of softirq,
+	 * we assume IRQ tail. Ksoftirqd shouldn't reach here as the
+	 * timer base wouldn't be idle. And inline softirq processing
+	 * after a call to local_bh_enable() within idle loop sound too
+	 * fun to be considered here.
+	 */
+	WARN_ONCE(in_task(),
+		  "Late timer enqueue may be ignored\n");
+#endif
+}
+
 /*
  * When add_timer_on() enqueues a timer into the timer wheel of an
  * idle CPU then this timer might expire before the next timer event

@@ -688,8 +704,10 @@ static void wake_up_idle_cpu(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
 
-	if (cpu == smp_processor_id())
+	if (cpu == smp_processor_id()) {
+		wake_idle_assert_possible();
 		return;
+	}
 

kernel/sched/core.c static void wake_up_idle_cpu(int cpu) · line 713

Quoted 2 lines

kernel/sched/core.c +0 -0

 	if (set_nr_and_not_polling(rq->idle))
 		smp_send_reschedule(cpu);

I'm not entirely sure I understand this one. What's the callchain that leads to this?