[PATCH 0/6] cpuidle: menu: Fixes, optimizations and cleanups

[PATCH 0/6] cpuidle: menu: Fixes, optimizations and cleanups

[Rafael J. Wysocki]

Hi All,

This series fixes a couple of issues with the menu governor, optimizes it
somewhat and makes a couple of cleanups in it.  Please refer to the
patch changelogs for details.

All of the changes in the series are straightforward in my view.  The
first two patches are fixes, the rest is optimizations and cleanups.

Thanks,
Rafael

[PATCH 1/6] cpuidle: menu: Fix wakeup statistics updates for polling state

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

If the CPU exits the "polling" state due to the time limit in the
loop in poll_idle(), this is not a real wakeup and it just means
that the "polling" state selection was not adequate.  The governor
mispredicted short idle duration, but had a more suitable state been
selected, the CPU might have spent more time in it.  In fact, there
is no reason to expect that there would have been a wakeup event
earlier than the next timer in that case.

Handling such cases as regular wakeups in menu_update() may cause the
menu governor to make suboptimal decisions going forward, but ignoring
them altogether would not be correct either, because every time
menu_select() is invoked, it makes a separate new attempt to predict
the idle duration taking distinct time to the closest timer event as
input and the outcomes of all those attempts should be recorded.

For this reason, make menu_update() always assume that if the
"polling" state was exited due to the time limit, the next proper
wakeup event for the CPU would be the next timer event (not
including the tick).

Fixes: a37b969a61c1 "cpuidle: poll_state: Add time limit to poll_idle()"
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |   10 ++++++++++
 drivers/cpuidle/poll_state.c     |    6 +++++-
 include/linux/cpuidle.h          |    1 +
 3 files changed, 16 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -511,6 +511,16 @@ static void menu_update(struct cpuidle_d
 		 * duration predictor do a better job next time.
 		 */
 		measured_us = 9 * MAX_INTERESTING / 10;
+	} else if ((drv->states[last_idx].flags & CPUIDLE_FLAG_POLLING) &&
+		   dev->poll_time_limit) {
+		/*
+		 * The CPU exited the "polling" state due to a time limit, so
+		 * the idle duration prediction leading to the selection of that
+		 * state was inaccurate.  If a better prediction had been made,
+		 * the CPU might have been woken up from idle by the next timer.
+		 * Assume that to be the case.
+		 */
+		measured_us = data->next_timer_us;
 	} else {
 		/* measured value */
 		measured_us = dev->last_residency;
Index: linux-pm/include/linux/cpuidle.h
===================================================================
--- linux-pm.orig/include/linux/cpuidle.h
+++ linux-pm/include/linux/cpuidle.h
@@ -81,6 +81,7 @@ struct cpuidle_device {
 	unsigned int		registered:1;
 	unsigned int		enabled:1;
 	unsigned int		use_deepest_state:1;
+	unsigned int		poll_time_limit:1;
 	unsigned int		cpu;
 
 	int			last_residency;
Index: linux-pm/drivers/cpuidle/poll_state.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/poll_state.c
+++ linux-pm/drivers/cpuidle/poll_state.c
@@ -17,6 +17,8 @@ static int __cpuidle poll_idle(struct cp
 {
 	u64 time_start = local_clock();
 
+	dev->poll_time_limit = false;
+
 	local_irq_enable();
 	if (!current_set_polling_and_test()) {
 		unsigned int loop_count = 0;
@@ -27,8 +29,10 @@ static int __cpuidle poll_idle(struct cp
 				continue;
 
 			loop_count = 0;
-			if (local_clock() - time_start > POLL_IDLE_TIME_LIMIT)
+			if (local_clock() - time_start > POLL_IDLE_TIME_LIMIT) {
+				dev->poll_time_limit = true;
 				break;
+			}
 		}
 	}
 	current_clr_polling();

Re: [PATCH 1/6] cpuidle: menu: Fix wakeup statistics updates for polling state

[Daniel Lezcano]

On 02/10/2018 23:42, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> If the CPU exits the "polling" state due to the time limit in the
> loop in poll_idle(), this is not a real wakeup and it just means
> that the "polling" state selection was not adequate.  The governor
> mispredicted short idle duration, but had a more suitable state been
> selected, the CPU might have spent more time in it.  In fact, there
> is no reason to expect that there would have been a wakeup event
> earlier than the next timer in that case.
> 
> Handling such cases as regular wakeups in menu_update() may cause the
> menu governor to make suboptimal decisions going forward, but ignoring
> them altogether would not be correct either, because every time
> menu_select() is invoked, it makes a separate new attempt to predict
> the idle duration taking distinct time to the closest timer event as
> input and the outcomes of all those attempts should be recorded.
> 
> For this reason, make menu_update() always assume that if the
> "polling" state was exited due to the time limit, the next proper
> wakeup event for the CPU would be the next timer event (not
> including the tick).
> 
> Fixes: a37b969a61c1 "cpuidle: poll_state: Add time limit to poll_idle()"
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---

Reviewed-by: Daniel Lezcano <daniel.lezcano@linaro.org>


>  drivers/cpuidle/governors/menu.c |   10 ++++++++++
>  drivers/cpuidle/poll_state.c     |    6 +++++-
>  include/linux/cpuidle.h          |    1 +
>  3 files changed, 16 insertions(+), 1 deletion(-)
> 
> Index: linux-pm/drivers/cpuidle/governors/menu.c
> ===================================================================
> --- linux-pm.orig/drivers/cpuidle/governors/menu.c
> +++ linux-pm/drivers/cpuidle/governors/menu.c
> @@ -511,6 +511,16 @@ static void menu_update(struct cpuidle_d
>  		 * duration predictor do a better job next time.
>  		 */
>  		measured_us = 9 * MAX_INTERESTING / 10;
> +	} else if ((drv->states[last_idx].flags & CPUIDLE_FLAG_POLLING) &&
> +		   dev->poll_time_limit) {
> +		/*
> +		 * The CPU exited the "polling" state due to a time limit, so
> +		 * the idle duration prediction leading to the selection of that
> +		 * state was inaccurate.  If a better prediction had been made,
> +		 * the CPU might have been woken up from idle by the next timer.
> +		 * Assume that to be the case.
> +		 */
> +		measured_us = data->next_timer_us;
>  	} else {
>  		/* measured value */
>  		measured_us = dev->last_residency;
> Index: linux-pm/include/linux/cpuidle.h
> ===================================================================
> --- linux-pm.orig/include/linux/cpuidle.h
> +++ linux-pm/include/linux/cpuidle.h
> @@ -81,6 +81,7 @@ struct cpuidle_device {
>  	unsigned int		registered:1;
>  	unsigned int		enabled:1;
>  	unsigned int		use_deepest_state:1;
> +	unsigned int		poll_time_limit:1;
>  	unsigned int		cpu;
>  
>  	int			last_residency;
> Index: linux-pm/drivers/cpuidle/poll_state.c
> ===================================================================
> --- linux-pm.orig/drivers/cpuidle/poll_state.c
> +++ linux-pm/drivers/cpuidle/poll_state.c
> @@ -17,6 +17,8 @@ static int __cpuidle poll_idle(struct cp
>  {
>  	u64 time_start = local_clock();
>  
> +	dev->poll_time_limit = false;
> +
>  	local_irq_enable();
>  	if (!current_set_polling_and_test()) {
>  		unsigned int loop_count = 0;
> @@ -27,8 +29,10 @@ static int __cpuidle poll_idle(struct cp
>  				continue;
>  
>  			loop_count = 0;
> -			if (local_clock() - time_start > POLL_IDLE_TIME_LIMIT)
> +			if (local_clock() - time_start > POLL_IDLE_TIME_LIMIT) {
> +				dev->poll_time_limit = true;
>  				break;
> +			}
>  		}
>  	}
>  	current_clr_polling();
> 


-- 
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

[PATCH 2/6] cpuidle: menu: Compute first_idx when latency_req is known

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

Since menu_select() can only set first_idx to 1 if the exit latency
of the second state is not greater than the latency limit, it should
first determine that limit.  Thus first_idx should be computed after
the "interactivity" factor has been taken into account.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |   32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -322,22 +322,6 @@ static int menu_select(struct cpuidle_dr
 	expected_interval = get_typical_interval(data);
 	expected_interval = min(expected_interval, data->next_timer_us);
 
-	first_idx = 0;
-	if (drv->states[0].flags & CPUIDLE_FLAG_POLLING) {
-		struct cpuidle_state *s = &drv->states[1];
-		unsigned int polling_threshold;
-
-		/*
-		 * Default to a physical idle state, not to busy polling, unless
-		 * a timer is going to trigger really really soon.
-		 */
-		polling_threshold = max_t(unsigned int, 20, s->target_residency);
-		if (data->next_timer_us > polling_threshold &&
-		    latency_req > s->exit_latency && !s->disabled &&
-		    !dev->states_usage[1].disable)
-			first_idx = 1;
-	}
-
 	/*
 	 * Use the lowest expected idle interval to pick the idle state.
 	 */
@@ -364,6 +348,22 @@ static int menu_select(struct cpuidle_dr
 			latency_req = interactivity_req;
 	}
 
+	first_idx = 0;
+	if (drv->states[0].flags & CPUIDLE_FLAG_POLLING) {
+		struct cpuidle_state *s = &drv->states[1];
+		unsigned int polling_threshold;
+
+		/*
+		 * Default to a physical idle state, not to busy polling, unless
+		 * a timer is going to trigger really really soon.
+		 */
+		polling_threshold = max_t(unsigned int, 20, s->target_residency);
+		if (data->next_timer_us > polling_threshold &&
+		    latency_req > s->exit_latency && !s->disabled &&
+		    !dev->states_usage[1].disable)
+			first_idx = 1;
+	}
+
 	/*
 	 * Find the idle state with the lowest power while satisfying
 	 * our constraints.

Re: [PATCH 2/6] cpuidle: menu: Compute first_idx when latency_req is known

[Daniel Lezcano]

On Tue, Oct 02, 2018 at 11:42:56PM +0200, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> Since menu_select() can only set first_idx to 1 if the exit latency
> of the second state is not greater than the latency limit, it should
> first determine that limit.  Thus first_idx should be computed after
> the "interactivity" factor has been taken into account.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

Reviewedy-by: Daniel Lezcano <daniel.lezcano@linaro.org>


-- 

 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

[PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

Rearrange the code in menu_select() so that the loop over idle states
always starts from 0 and get rid of the first_idx variable.

While at it, add two empty lines to separate conditional statements
one another.

No intentional behavior changes.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |   32 ++++++++++++++------------------
 1 file changed, 14 insertions(+), 18 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -285,7 +285,6 @@ static int menu_select(struct cpuidle_dr
 	struct menu_device *data = this_cpu_ptr(&menu_devices);
 	int latency_req = cpuidle_governor_latency_req(dev->cpu);
 	int i;
-	int first_idx;
 	int idx;
 	unsigned int interactivity_req;
 	unsigned int expected_interval;
@@ -348,36 +347,33 @@ static int menu_select(struct cpuidle_dr
 			latency_req = interactivity_req;
 	}
 
-	first_idx = 0;
-	if (drv->states[0].flags & CPUIDLE_FLAG_POLLING) {
-		struct cpuidle_state *s = &drv->states[1];
-		unsigned int polling_threshold;
-
-		/*
-		 * Default to a physical idle state, not to busy polling, unless
-		 * a timer is going to trigger really really soon.
-		 */
-		polling_threshold = max_t(unsigned int, 20, s->target_residency);
-		if (data->next_timer_us > polling_threshold &&
-		    latency_req > s->exit_latency && !s->disabled &&
-		    !dev->states_usage[1].disable)
-			first_idx = 1;
-	}
-
 	/*
 	 * Find the idle state with the lowest power while satisfying
 	 * our constraints.
 	 */
 	idx = -1;
-	for (i = first_idx; i < drv->state_count; i++) {
+	for (i = 0; i < drv->state_count; i++) {
 		struct cpuidle_state *s = &drv->states[i];
 		struct cpuidle_state_usage *su = &dev->states_usage[i];
 
 		if (s->disabled || su->disable)
 			continue;
+
 		if (idx == -1)
 			idx = i; /* first enabled state */
+
 		if (s->target_residency > predicted_us) {
+			/*
+			 * Use a physical idle state, not busy polling, unless
+			 * a timer is going to trigger really really soon.
+			 */
+			if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
+			    i == idx + 1 && latency_req > s->exit_latency &&
+			    data->next_timer_us > max_t(unsigned int, 20,
+							s->target_residency)) {
+				idx = i;
+				break;
+			}
 			if (predicted_us < TICK_USEC)
 				break;
 

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Peter Zijlstra]

On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
>  	idx = -1;
> -	for (i = first_idx; i < drv->state_count; i++) {
> +	for (i = 0; i < drv->state_count; i++) {
>  		struct cpuidle_state *s = &drv->states[i];
>  		struct cpuidle_state_usage *su = &dev->states_usage[i];
>  
>  		if (s->disabled || su->disable)
>  			continue;
> +
>  		if (idx == -1)
>  			idx = i; /* first enabled state */
> +
>  		if (s->target_residency > predicted_us) {
> +			/*
> +			 * Use a physical idle state, not busy polling, unless
> +			 * a timer is going to trigger really really soon.
> +			 */
> +			if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
> +			    i == idx + 1 && latency_req > s->exit_latency &&
> +			    data->next_timer_us > max_t(unsigned int, 20,
> +							s->target_residency)) {

Not new in this patch, but this is where I really noticed it; that 20,
should that not be something like: POLL_IDLE_TIME_LIMIT / NSEC_PER_USEC
?

> +				idx = i;
> +				break;
> +			}
>  			if (predicted_us < TICK_USEC)
>  				break;
>  
> 

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Rafael J. Wysocki]

On Thu, Oct 4, 2018 at 9:46 AM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
> >       idx = -1;
> > -     for (i = first_idx; i < drv->state_count; i++) {
> > +     for (i = 0; i < drv->state_count; i++) {
> >               struct cpuidle_state *s = &drv->states[i];
> >               struct cpuidle_state_usage *su = &dev->states_usage[i];
> >
> >               if (s->disabled || su->disable)
> >                       continue;
> > +
> >               if (idx == -1)
> >                       idx = i; /* first enabled state */
> > +
> >               if (s->target_residency > predicted_us) {
> > +                     /*
> > +                      * Use a physical idle state, not busy polling, unless
> > +                      * a timer is going to trigger really really soon.
> > +                      */
> > +                     if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
> > +                         i == idx + 1 && latency_req > s->exit_latency &&
> > +                         data->next_timer_us > max_t(unsigned int, 20,
> > +                                                     s->target_residency)) {
>
> Not new in this patch, but this is where I really noticed it; that 20,
> should that not be something like: POLL_IDLE_TIME_LIMIT / NSEC_PER_USEC
> ?

The POLL_IDLE_TIME_LIMIT is how much time we allow it to spin in
idle_poll() and I'm not sure it is related.  Besides, I want it to go
away actually (https://patchwork.kernel.org/patch/10624117/).

I could use a separate symbol for this particular magic number, but it
has been magic forever and it is used just in this one place, so ...

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Peter Zijlstra]

On Thu, Oct 04, 2018 at 09:53:39AM +0200, Rafael J. Wysocki wrote:
> On Thu, Oct 4, 2018 at 9:46 AM Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
> > >       idx = -1;
> > > -     for (i = first_idx; i < drv->state_count; i++) {
> > > +     for (i = 0; i < drv->state_count; i++) {
> > >               struct cpuidle_state *s = &drv->states[i];
> > >               struct cpuidle_state_usage *su = &dev->states_usage[i];
> > >
> > >               if (s->disabled || su->disable)
> > >                       continue;
> > > +
> > >               if (idx == -1)
> > >                       idx = i; /* first enabled state */
> > > +
> > >               if (s->target_residency > predicted_us) {
> > > +                     /*
> > > +                      * Use a physical idle state, not busy polling, unless
> > > +                      * a timer is going to trigger really really soon.
> > > +                      */
> > > +                     if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
> > > +                         i == idx + 1 && latency_req > s->exit_latency &&
> > > +                         data->next_timer_us > max_t(unsigned int, 20,
> > > +                                                     s->target_residency)) {
> >
> > Not new in this patch, but this is where I really noticed it; that 20,
> > should that not be something like: POLL_IDLE_TIME_LIMIT / NSEC_PER_USEC
> > ?
> 
> The POLL_IDLE_TIME_LIMIT is how much time we allow it to spin in
> idle_poll() and I'm not sure it is related.  Besides, I want it to go
> away actually (https://patchwork.kernel.org/patch/10624117/).

Ah, ok. Making it go away is better still!

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Daniel Lezcano]

On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> Rearrange the code in menu_select() so that the loop over idle states
> always starts from 0 and get rid of the first_idx variable.
> 
> While at it, add two empty lines to separate conditional statements
> one another.
> 
> No intentional behavior changes.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---

This code is becoming a bit complex to follow :/

May be I missed something, but it is not possible to enter the condition without
idx != 0, no ? (I meant the condition if ((drv->states[idx].flags &
FLAG_POLLING))

Reviewed-by: Daniel Lezcano <daniel.lezcano@linaro.org>

>  drivers/cpuidle/governors/menu.c |   32 ++++++++++++++------------------
>  1 file changed, 14 insertions(+), 18 deletions(-)
> 
> Index: linux-pm/drivers/cpuidle/governors/menu.c
> ===================================================================
> --- linux-pm.orig/drivers/cpuidle/governors/menu.c
> +++ linux-pm/drivers/cpuidle/governors/menu.c
> @@ -285,7 +285,6 @@ static int menu_select(struct cpuidle_dr
>  	struct menu_device *data = this_cpu_ptr(&menu_devices);
>  	int latency_req = cpuidle_governor_latency_req(dev->cpu);
>  	int i;
> -	int first_idx;
>  	int idx;
>  	unsigned int interactivity_req;
>  	unsigned int expected_interval;
> @@ -348,36 +347,33 @@ static int menu_select(struct cpuidle_dr
>  			latency_req = interactivity_req;
>  	}
>  
> -	first_idx = 0;
> -	if (drv->states[0].flags & CPUIDLE_FLAG_POLLING) {
> -		struct cpuidle_state *s = &drv->states[1];
> -		unsigned int polling_threshold;
> -
> -		/*
> -		 * Default to a physical idle state, not to busy polling, unless
> -		 * a timer is going to trigger really really soon.
> -		 */
> -		polling_threshold = max_t(unsigned int, 20, s->target_residency);
> -		if (data->next_timer_us > polling_threshold &&
> -		    latency_req > s->exit_latency && !s->disabled &&
> -		    !dev->states_usage[1].disable)
> -			first_idx = 1;
> -	}
> -
>  	/*
>  	 * Find the idle state with the lowest power while satisfying
>  	 * our constraints.
>  	 */
>  	idx = -1;
> -	for (i = first_idx; i < drv->state_count; i++) {
> +	for (i = 0; i < drv->state_count; i++) {
>  		struct cpuidle_state *s = &drv->states[i];
>  		struct cpuidle_state_usage *su = &dev->states_usage[i];
>  
>  		if (s->disabled || su->disable)
>  			continue;
> +
>  		if (idx == -1)
>  			idx = i; /* first enabled state */
> +
>  		if (s->target_residency > predicted_us) {
> +			/*
> +			 * Use a physical idle state, not busy polling, unless
> +			 * a timer is going to trigger really really soon.
> +			 */
> +			if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
> +			    i == idx + 1 && latency_req > s->exit_latency &&
> +			    data->next_timer_us > max_t(unsigned int, 20,
> +							s->target_residency)) {
> +				idx = i;
> +				break;
> +			}
>  			if (predicted_us < TICK_USEC)
>  				break;
>  
> 

-- 

 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Rafael J. Wysocki]

On Thu, Oct 4, 2018 at 4:51 PM Daniel Lezcano <daniel.lezcano@linaro.org> wrote:
>
> On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
> > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >
> > Rearrange the code in menu_select() so that the loop over idle states
> > always starts from 0 and get rid of the first_idx variable.
> >
> > While at it, add two empty lines to separate conditional statements
> > one another.
> >
> > No intentional behavior changes.
> >
> > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > ---
>
> This code is becoming a bit complex to follow :/
>
> May be I missed something, but it is not possible to enter the condition without
> idx != 0, no ? (I meant the condition if ((drv->states[idx].flags &
> FLAG_POLLING))

Not sure what you mean.

We start with idx = -1, i = 0.  If state[0] is enabled, idx becomes 0.

If the target residency or exit latency of state[0] are already beyond
the limits, we just bail out and state[0] will be returned.

If not, we go to i = 1, but idx is still 0.  If the target residency
of state[1] is beyond predicted_us (which is the interesting case), we
check (drv->states[0].flags & FLAG_POLLING) and so on.

Currently, the polling state must be state[0] (if used at all) anyway.

> Reviewed-by: Daniel Lezcano <daniel.lezcano@linaro.org>
>

Thanks!

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Daniel Lezcano]

On 04/10/2018 19:19, Rafael J. Wysocki wrote:
> On Thu, Oct 4, 2018 at 4:51 PM Daniel Lezcano <daniel.lezcano@linaro.org> wrote:
>>
>> On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
>>> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>>>
>>> Rearrange the code in menu_select() so that the loop over idle states
>>> always starts from 0 and get rid of the first_idx variable.
>>>
>>> While at it, add two empty lines to separate conditional statements
>>> one another.
>>>
>>> No intentional behavior changes.
>>>
>>> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>>> ---
>>
>> This code is becoming a bit complex to follow :/
>>
>> May be I missed something, but it is not possible to enter the condition without
>> idx != 0, no ? (I meant the condition if ((drv->states[idx].flags &
>> FLAG_POLLING))
> 
> Not sure what you mean.

Yes, sorry let me clarify.

I meant the flag polling is always on state[0], so if the flag is set
then idx == 0.

We have the conditions:

  drv->states[idx].flags & CPUIDLE_FLAG_POLLING

If it is true then idx is zero.


Then comes the second condition:

  i == idx + 1

because of the above, idx is zero, then it can become i == 1.

Then the variable assignation:

 idx = i can be replaced by idx = 1





> We start with idx = -1, i = 0.  If state[0] is enabled, idx becomes 0.
> 
> If the target residency or exit latency of state[0] are already beyond
> the limits, we just bail out and state[0] will be returned.
> 
> If not, we go to i = 1, but idx is still 0.  If the target residency
> of state[1] is beyond predicted_us (which is the interesting case), we
> check (drv->states[0].flags & FLAG_POLLING) and so on.
> 
> Currently, the polling state must be state[0] (if used at all) anyway.
> 
>> Reviewed-by: Daniel Lezcano <daniel.lezcano@linaro.org>
>>
> 
> Thanks!
> 


-- 
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

Re: [PATCH 3/6] cpuidle: menu: Get rid of first_idx from menu_select()

[Rafael J. Wysocki]

On Fri, Oct 5, 2018 at 10:35 AM Daniel Lezcano
<daniel.lezcano@linaro.org> wrote:
>
> On 04/10/2018 19:19, Rafael J. Wysocki wrote:
> > On Thu, Oct 4, 2018 at 4:51 PM Daniel Lezcano <daniel.lezcano@linaro.org> wrote:
> >>
> >> On Tue, Oct 02, 2018 at 11:44:06PM +0200, Rafael J. Wysocki wrote:
> >>> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >>>
> >>> Rearrange the code in menu_select() so that the loop over idle states
> >>> always starts from 0 and get rid of the first_idx variable.
> >>>
> >>> While at it, add two empty lines to separate conditional statements
> >>> one another.
> >>>
> >>> No intentional behavior changes.
> >>>
> >>> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >>> ---
> >>
> >> This code is becoming a bit complex to follow :/
> >>
> >> May be I missed something, but it is not possible to enter the condition without
> >> idx != 0, no ? (I meant the condition if ((drv->states[idx].flags &
> >> FLAG_POLLING))
> >
> > Not sure what you mean.
>
> Yes, sorry let me clarify.
>
> I meant the flag polling is always on state[0], so if the flag is set
> then idx == 0.
>
> We have the conditions:
>
>   drv->states[idx].flags & CPUIDLE_FLAG_POLLING
>
> If it is true then idx is zero.
>
>
> Then comes the second condition:
>
>   i == idx + 1
>
> because of the above, idx is zero, then it can become i == 1.
>
> Then the variable assignation:
>
>  idx = i can be replaced by idx = 1

Yes, but the former works too. :-)

[PATCH 4/6] cpuidle: menu: Do not update last_state_idx in menu_select()

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

It is not necessary to update data->last_state_idx in menu_select()
as it only is used in menu_update() which only runs when
data->needs_update is set and that is set only when updating
data->last_state_idx in menu_reflect().

Accordingly, drop the update of data->last_state_idx from
menu_select() and get rid of the (now redundant) "out" label
from it.

No intentional behavior changes.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |    7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -398,7 +398,7 @@ static int menu_select(struct cpuidle_dr
 			    s->target_residency <= ktime_to_us(delta_next))
 				idx = i;
 
-			goto out;
+			return idx;
 		}
 		if (s->exit_latency > latency_req) {
 			/*
@@ -445,10 +445,7 @@ static int menu_select(struct cpuidle_dr
 		}
 	}
 
-out:
-	data->last_state_idx = idx;
-
-	return data->last_state_idx;
+	return idx;
 }
 
 /**

Re: [PATCH 4/6] cpuidle: menu: Do not update last_state_idx in menu_select()

[Daniel Lezcano]

On Tue, Oct 02, 2018 at 11:45:07PM +0200, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> It is not necessary to update data->last_state_idx in menu_select()
> as it only is used in menu_update() which only runs when
> data->needs_update is set and that is set only when updating
> data->last_state_idx in menu_reflect().
> 
> Accordingly, drop the update of data->last_state_idx from
> menu_select() and get rid of the (now redundant) "out" label
> from it.
> 
> No intentional behavior changes.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---

Reviewed-by: Daniel Lezcano <daniel.lezcano@linaro.org>

-- 

 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

[PATCH 5/6] cpuidle: menu: Avoid computations for very close timers

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

If the next timer event (with the tick excluded) is closer than the
target residency of the second state or the PM QoS latency constraint
is below its exit latency, state[0] will be used regardless of any
other factors, so skip the computations in menu_select() then and
return 0 straight away from it.

Still, do that after the bucket has been determined to avoid
disturbing the wakeup statistics in general.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |   12 ++++++++++++
 1 file changed, 12 insertions(+)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -309,6 +309,18 @@ static int menu_select(struct cpuidle_dr
 	get_iowait_load(&nr_iowaiters, &cpu_load);
 	data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
 
+	if (unlikely(drv->state_count <= 1) ||
+	    ((data->next_timer_us < drv->states[1].target_residency ||
+	      latency_req < drv->states[1].exit_latency) &&
+	     !drv->states[0].disabled && !dev->states_usage[0].disable)) {
+		/*
+		 * In this case state[0] will be used no matter what, so return
+		 * it right away and keep the tick running.
+		 */
+		*stop_tick = false;
+		return 0;
+	}
+
 	/*
 	 * Force the result of multiplication to be 64 bits even if both
 	 * operands are 32 bits.

Re: [PATCH 5/6] cpuidle: menu: Avoid computations for very close timers

[Daniel Lezcano]

On Tue, Oct 02, 2018 at 11:46:28PM +0200, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> If the next timer event (with the tick excluded) is closer than the
> target residency of the second state or the PM QoS latency constraint
> is below its exit latency, state[0] will be used regardless of any
> other factors, so skip the computations in menu_select() then and
> return 0 straight away from it.
> 
> Still, do that after the bucket has been determined to avoid
> disturbing the wakeup statistics in general.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---
>  drivers/cpuidle/governors/menu.c |   12 ++++++++++++
>  1 file changed, 12 insertions(+)
> 
> Index: linux-pm/drivers/cpuidle/governors/menu.c
> ===================================================================
> --- linux-pm.orig/drivers/cpuidle/governors/menu.c
> +++ linux-pm/drivers/cpuidle/governors/menu.c
> @@ -309,6 +309,18 @@ static int menu_select(struct cpuidle_dr
>  	get_iowait_load(&nr_iowaiters, &cpu_load);
>  	data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
>  
> +	if (unlikely(drv->state_count <= 1) ||

I'm not sure this test is necessary.

If state_count == 0, we don't have to select anything as the cpuidle can't register because of:

static int __cpuidle_register_driver(struct cpuidle_driver *drv)
{
        int ret;

        if (!drv || !drv->state_count)
                return -EINVAL;

	[ ... ]
}

If state_count == 1, then there is nothing to select, it is always the state 0.

> +	    ((data->next_timer_us < drv->states[1].target_residency ||
> +	      latency_req < drv->states[1].exit_latency) &&
> +	     !drv->states[0].disabled && !dev->states_usage[0].disable)) {
> +		/*
> +		 * In this case state[0] will be used no matter what, so return
> +		 * it right away and keep the tick running.
> +		 */
> +		*stop_tick = false;
> +		return 0;
> +	}
> +
>  	/*
>  	 * Force the result of multiplication to be 64 bits even if both
>  	 * operands are 32 bits.
> 

-- 

 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog

Re: [PATCH 5/6] cpuidle: menu: Avoid computations for very close timers

[Rafael J. Wysocki]

On Thu, Oct 4, 2018 at 5:50 PM Daniel Lezcano <daniel.lezcano@linaro.org> wrote:
>
> On Tue, Oct 02, 2018 at 11:46:28PM +0200, Rafael J. Wysocki wrote:
> > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >
> > If the next timer event (with the tick excluded) is closer than the
> > target residency of the second state or the PM QoS latency constraint
> > is below its exit latency, state[0] will be used regardless of any
> > other factors, so skip the computations in menu_select() then and
> > return 0 straight away from it.
> >
> > Still, do that after the bucket has been determined to avoid
> > disturbing the wakeup statistics in general.
> >
> > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> > ---
> >  drivers/cpuidle/governors/menu.c |   12 ++++++++++++
> >  1 file changed, 12 insertions(+)
> >
> > Index: linux-pm/drivers/cpuidle/governors/menu.c
> > ===================================================================
> > --- linux-pm.orig/drivers/cpuidle/governors/menu.c
> > +++ linux-pm/drivers/cpuidle/governors/menu.c
> > @@ -309,6 +309,18 @@ static int menu_select(struct cpuidle_dr
> >       get_iowait_load(&nr_iowaiters, &cpu_load);
> >       data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
> >
> > +     if (unlikely(drv->state_count <= 1) ||
>
> I'm not sure this test is necessary.

Yes, it is IMO.

Strictly speaking it prevents state[1] from being accessed if the
count is not 2 at least.

> If state_count == 0, we don't have to select anything as the cpuidle can't register because of:
>
> static int __cpuidle_register_driver(struct cpuidle_driver *drv)
> {
>         int ret;
>
>         if (!drv || !drv->state_count)
>                 return -EINVAL;
>
>         [ ... ]
> }
>
> If state_count == 1, then there is nothing to select, it is always the state 0.

Which is why it is better to simply return 0 right away in this case. :-)

I guess I could compare state_count just to 1, but <= 1 works too.

[PATCH 6/6] cpuidle: menu: Move the latency_req == 0 special case check

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

It is better to always update data->bucket before returning from
menu_select() so as to prevent disturbing the wakeup statistics
collected by the governor, so combine the latency_req == 0 special
check with the more general check below.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |    8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/menu.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/menu.c
+++ linux-pm/drivers/cpuidle/governors/menu.c
@@ -297,19 +297,13 @@ static int menu_select(struct cpuidle_dr
 		data->needs_update = 0;
 	}
 
-	/* Special case when user has set very strict latency requirement */
-	if (unlikely(latency_req == 0)) {
-		*stop_tick = false;
-		return 0;
-	}
-
 	/* determine the expected residency time, round up */
 	data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length(&delta_next));
 
 	get_iowait_load(&nr_iowaiters, &cpu_load);
 	data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
 
-	if (unlikely(drv->state_count <= 1) ||
+	if (unlikely(drv->state_count <= 1 || latency_req == 0) ||
 	    ((data->next_timer_us < drv->states[1].target_residency ||
 	      latency_req < drv->states[1].exit_latency) &&
 	     !drv->states[0].disabled && !dev->states_usage[0].disable)) {

Re: [PATCH 0/6] cpuidle: menu: Fixes, optimizations and cleanups

[Rafael J. Wysocki]

On Tue, Oct 2, 2018 at 11:51 PM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
>
> Hi All,
>
> This series fixes a couple of issues with the menu governor, optimizes it
> somewhat and makes a couple of cleanups in it.  Please refer to the
> patch changelogs for details.
>
> All of the changes in the series are straightforward in my view.  The
> first two patches are fixes, the rest is optimizations and cleanups.

I'm inclined to take this stuff in for 4.20 if nobody has problems
with it, so please have a look if you care (and you should, because
the code in question is run on all tickless systems out there).

Thanks,
Rafael

Re: [PATCH 0/6] cpuidle: menu: Fixes, optimizations and cleanups

[Peter Zijlstra]

On Thu, Oct 04, 2018 at 08:55:45AM +0200, Rafael J. Wysocki wrote:
> On Tue, Oct 2, 2018 at 11:51 PM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> >
> > Hi All,
> >
> > This series fixes a couple of issues with the menu governor, optimizes it
> > somewhat and makes a couple of cleanups in it.  Please refer to the
> > patch changelogs for details.
> >
> > All of the changes in the series are straightforward in my view.  The
> > first two patches are fixes, the rest is optimizations and cleanups.
> 
> I'm inclined to take this stuff in for 4.20 if nobody has problems
> with it, so please have a look if you care (and you should, because
> the code in question is run on all tickless systems out there).

Looks ok to me,

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>