[PATCH] cpuidle: teo: fix underflow of recent intercepts

[PATCH] cpuidle: teo: fix underflow of recent intercepts

[Christian Loehle]

The recent counter of each cpuidle state bin reflects the number of
recent intercepts. It's decremented and incremented accordingly.
The decrement was never checked for 0, therefore underflowing into a
value teo cannot easily recover from.

The underflow lead to deeper idle states being skipped because teo
assumed interception was likely and it preferring shallower states.

Fixes: 77577558f25d ("cpuidle: teo: Rework most recent idle duration values treatment")
Signed-off-by: Christian Loehle <christian.loehle@arm.com>
---
 drivers/cpuidle/governors/teo.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
index 7244f71c59c5..42fb2771e35d 100644
--- a/drivers/cpuidle/governors/teo.c
+++ b/drivers/cpuidle/governors/teo.c
@@ -290,7 +290,8 @@ static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	if (cpu_data->next_recent_idx >= NR_RECENT)
 		cpu_data->next_recent_idx = 0;
 
-	if (cpu_data->recent_idx[i] >= 0)
+	if (cpu_data->recent_idx[i] >= 0 &&
+			cpu_data->state_bins[cpu_data->recent_idx[i]].recent)
 		cpu_data->state_bins[cpu_data->recent_idx[i]].recent--;
 
 	/*
-- 
2.34.1

Re: [PATCH] cpuidle: teo: fix underflow of recent intercepts

[Christian Loehle]

On 5/19/24 22:03, Christian Loehle wrote:
> The recent counter of each cpuidle state bin reflects the number of
> recent intercepts. It's decremented and incremented accordingly.
> The decrement was never checked for 0, therefore underflowing into a
> value teo cannot easily recover from.
> 
> The underflow lead to deeper idle states being skipped because teo
> assumed interception was likely and it preferring shallower states.
> 
> Fixes: 77577558f25d ("cpuidle: teo: Rework most recent idle duration values treatment")
> Signed-off-by: Christian Loehle <christian.loehle@arm.com>
> ---
>  drivers/cpuidle/governors/teo.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
> index 7244f71c59c5..42fb2771e35d 100644
> --- a/drivers/cpuidle/governors/teo.c
> +++ b/drivers/cpuidle/governors/teo.c
> @@ -290,7 +290,8 @@ static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
>  	if (cpu_data->next_recent_idx >= NR_RECENT)
>  		cpu_data->next_recent_idx = 0;
>  
> -	if (cpu_data->recent_idx[i] >= 0)
> +	if (cpu_data->recent_idx[i] >= 0 &&
> +			cpu_data->state_bins[cpu_data->recent_idx[i]].recent)
>  		cpu_data->state_bins[cpu_data->recent_idx[i]].recent--;
>  
>  	/*

You should be able to observe the problematic underflow on any system.
Essentially these lines:
	alt_intercepts = 2 * idx_intercept_sum > cpu_data->total - idx_hit_sum;
	alt_recent = idx_recent_sum > NR_RECENT / 2; // CL: idx_recent_sum being the sum of a bunch of underflowed recent values, so expected to be big, too.
	if (alt_recent || alt_intercepts) {
become
	if (true) {

but the if block actually overriding the state should only be possible
for systems with >2 cpuidle states.
I'll follow up with a more detailed report though.

Re: [PATCH] cpuidle: teo: fix underflow of recent intercepts

[Christian Loehle]

On 5/19/24 22:03, Christian Loehle wrote:
> The recent counter of each cpuidle state bin reflects the number of
> recent intercepts. It's decremented and incremented accordingly.
> The decrement was never checked for 0, therefore underflowing into a
> value teo cannot easily recover from.
> 
> The underflow lead to deeper idle states being skipped because teo
> assumed interception was likely and it preferring shallower states.
> 
> Fixes: 77577558f25d ("cpuidle: teo: Rework most recent idle duration values treatment")
> Signed-off-by: Christian Loehle <christian.loehle@arm.com>
> ---
>  drivers/cpuidle/governors/teo.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
> index 7244f71c59c5..42fb2771e35d 100644
> --- a/drivers/cpuidle/governors/teo.c
> +++ b/drivers/cpuidle/governors/teo.c
> @@ -290,7 +290,8 @@ static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
>  	if (cpu_data->next_recent_idx >= NR_RECENT)
>  		cpu_data->next_recent_idx = 0;
>  
> -	if (cpu_data->recent_idx[i] >= 0)
> +	if (cpu_data->recent_idx[i] >= 0 &&
> +			cpu_data->state_bins[cpu_data->recent_idx[i]].recent)
>  		cpu_data->state_bins[cpu_data->recent_idx[i]].recent--;
>  
>  	/*

Anyway, since I'm not sure when I will get around to finishing up a
fully-detailed report.
Rafael, unless I'm missing something, recent is only ever cycled through
the bins and never actually reset to 0, is that missing somewhere?

Maybe like this if my suspicion is correct?
Haven't tested it yet.

[PATCH] cpuidle: teo: Reset recent when cycling bins

recent intercepts value was never actually reset, only
decremented. This patch resets the value when cycling
to a new recent intercept bin.

Fixes: 77577558f25d ("cpuidle: teo: Rework most recent idle duration values treatment")
Signed-off-by: Christian Loehle <christian.loehle@arm.com>
---
 drivers/cpuidle/governors/teo.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/cpuidle/governors/teo.c b/drivers/cpuidle/governors/teo.c
index 7244f71c59c5..a39bef603408 100644
--- a/drivers/cpuidle/governors/teo.c
+++ b/drivers/cpuidle/governors/teo.c
@@ -291,7 +291,7 @@ static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 		cpu_data->next_recent_idx = 0;
 
 	if (cpu_data->recent_idx[i] >= 0)
-		cpu_data->state_bins[cpu_data->recent_idx[i]].recent--;
+		cpu_data->state_bins[cpu_data->recent_idx[i]].recent = 0;
 
 	/*
 	 * If the deepest state's target residency is below the tick length,
-- 
2.34.1