[PATCH V4 0/2] cpufreq: Sort policy->freq_table

[PATCH V4 0/2] cpufreq: Sort policy->freq_table

[Viresh Kumar]

Hi Rafael,

I have spent some more time on this stuff and finally came out with a
very simple solution. I hope you will like it more than the previous
versions.

Instead of trying to sort the freq-table passed by the drivers, which
was complicated and would have broken some drivers for sure, this patch
just checks if the freq-table is sorted or not.

If it is sorted, then we just use a different set of helpers for it. The
table can be sorted in both ascending and descending orders now and
helpers are present for both the cases.

All the patches are pushed here for testing in case anyone wants to try:
git://git.kernel.org/pub/scm/linux/kernel/git/vireshk/pm.git cpufreq/sorted-freq-table

V3->V4:
- Written from scratch really, completely different approach.

Thanks

Viresh Kumar (2):
  cpufreq: Handle sorted frequency tables more efficiently
  cpufreq: Reuse new freq-table helpers

 drivers/cpufreq/acpi-cpufreq.c         |  14 +-
 drivers/cpufreq/amd_freq_sensitivity.c |   4 +-
 drivers/cpufreq/cpufreq_ondemand.c     |   6 +-
 drivers/cpufreq/freq_table.c           |  67 +++++++-
 drivers/cpufreq/powernv-cpufreq.c      |   3 +-
 drivers/cpufreq/s5pv210-cpufreq.c      |   3 +-
 include/linux/cpufreq.h                | 284 ++++++++++++++++++++++++++++++++-
 7 files changed, 353 insertions(+), 28 deletions(-)

-- 
2.7.1.410.g6faf27b

[PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently

[Viresh Kumar]

cpufreq drivers aren't required to provide a sorted frequency table
today, and even the ones which provide a sorted table aren't handled
efficiently by cpufreq core.

This patch adds infrastructure to verify if the freq-table provided by
the drivers is sorted or not, and use efficient helpers if they are
sorted.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
---
 drivers/cpufreq/freq_table.c |  67 +++++++++-
 include/linux/cpufreq.h      | 284 ++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 343 insertions(+), 8 deletions(-)

diff --git a/drivers/cpufreq/freq_table.c b/drivers/cpufreq/freq_table.c
index eac8bcbdaad1..0c1139a5f33a 100644
--- a/drivers/cpufreq/freq_table.c
+++ b/drivers/cpufreq/freq_table.c
@@ -113,9 +113,9 @@ int cpufreq_generic_frequency_table_verify(struct cpufreq_policy *policy)
 }
 EXPORT_SYMBOL_GPL(cpufreq_generic_frequency_table_verify);
 
-int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
-				    unsigned int target_freq,
-				    unsigned int relation)
+int cpufreq_table_find_index_unsorted(struct cpufreq_policy *policy,
+				      unsigned int target_freq,
+				      unsigned int relation)
 {
 	struct cpufreq_frequency_table optimal = {
 		.driver_data = ~0,
@@ -205,7 +205,7 @@ int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
 		 table[index].frequency);
 	return index;
 }
-EXPORT_SYMBOL_GPL(cpufreq_frequency_table_target);
+EXPORT_SYMBOL_GPL(cpufreq_table_find_index_unsorted);
 
 int cpufreq_frequency_table_get_index(struct cpufreq_policy *policy,
 		unsigned int freq)
@@ -297,13 +297,70 @@ struct freq_attr *cpufreq_generic_attr[] = {
 };
 EXPORT_SYMBOL_GPL(cpufreq_generic_attr);
 
+static void set_freq_table_sorted(struct cpufreq_policy *policy)
+{
+	struct cpufreq_frequency_table *pos, *table = policy->freq_table;
+	struct cpufreq_frequency_table *prev = NULL;
+	int ascending = 0;
+
+	cpufreq_for_each_valid_entry(pos, table) {
+		if (!prev) {
+			prev = pos;
+			continue;
+		}
+
+		if (pos->frequency == prev->frequency) {
+			pr_warn("Duplicate freq-table entries: %u\n",
+				pos->frequency);
+			continue;
+		}
+
+		/* Frequency increased from prev to pos */
+		if (pos->frequency > prev->frequency) {
+			/* But frequency was decreasing earlier */
+			if (ascending < 0) {
+				policy->freq_table_sorted = false;
+				pr_debug("Freq table is unsorted\n");
+				return;
+			}
+
+			ascending++;
+		} else {
+			/* Frequency decreased from prev to pos */
+
+			/* But frequency was increasing earlier */
+			if (ascending > 0) {
+				policy->freq_table_sorted = false;
+				pr_debug("Freq table is unsorted\n");
+				return;
+			}
+
+			ascending--;
+		}
+
+		prev = pos;
+	}
+
+	policy->freq_table_sorted = true;
+
+	if (ascending > 0)
+		policy->freq_table_sorted_ascending = true;
+	else
+		policy->freq_table_sorted_ascending = false;
+
+	pr_debug("Freq table is sorted in %s order\n",
+		 ascending > 0 ? "ascending" : "descending");
+}
+
 int cpufreq_table_validate_and_show(struct cpufreq_policy *policy,
 				      struct cpufreq_frequency_table *table)
 {
 	int ret = cpufreq_frequency_table_cpuinfo(policy, table);
 
-	if (!ret)
+	if (!ret) {
 		policy->freq_table = table;
+		set_freq_table_sorted(policy);
+	}
 
 	return ret;
 }
diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h
index c378776628b4..5133570e86f2 100644
--- a/include/linux/cpufreq.h
+++ b/include/linux/cpufreq.h
@@ -86,7 +86,11 @@ struct cpufreq_policy {
 					 * called, but you're in IRQ context */
 
 	struct cpufreq_user_policy user_policy;
+
+	/* Freq-table and its flags */
 	struct cpufreq_frequency_table	*freq_table;
+	bool			freq_table_sorted;
+	bool			freq_table_sorted_ascending;
 
 	struct list_head        policy_list;
 	struct kobject		kobj;
@@ -597,9 +601,9 @@ int cpufreq_frequency_table_verify(struct cpufreq_policy *policy,
 				   struct cpufreq_frequency_table *table);
 int cpufreq_generic_frequency_table_verify(struct cpufreq_policy *policy);
 
-int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
-				   unsigned int target_freq,
-				   unsigned int relation);
+int cpufreq_table_find_index_unsorted(struct cpufreq_policy *policy,
+				      unsigned int target_freq,
+				      unsigned int relation);
 int cpufreq_frequency_table_get_index(struct cpufreq_policy *policy,
 		unsigned int freq);
 
@@ -610,6 +614,280 @@ int cpufreq_boost_trigger_state(int state);
 int cpufreq_boost_enabled(void);
 int cpufreq_enable_boost_support(void);
 bool policy_has_boost_freq(struct cpufreq_policy *policy);
+
+static inline bool freq_is_invalid(struct cpufreq_policy *policy, unsigned int frequency)
+{
+	if (unlikely(frequency == CPUFREQ_ENTRY_INVALID))
+		return true;
+
+	if (unlikely((frequency < policy->min) || (frequency > policy->max)))
+		return true;
+
+	return false;
+}
+
+/* Find lowest freq at or above target in a table in ascending order */
+static inline int cpufreq_table_find_index_al(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq >= target_freq)
+			return i;
+
+		best = i;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Find lowest freq at or above target in a table in descending order */
+static inline int cpufreq_table_find_index_dl(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq == target_freq)
+			return i;
+
+		if (freq > target_freq) {
+			best = i;
+			continue;
+		}
+
+		/* No freq found below target_freq */
+		if (best == -1)
+			return i;
+
+		return best;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Works only on sorted freq-tables */
+static inline int cpufreq_table_find_index_l(struct cpufreq_policy *policy,
+					     unsigned int target_freq)
+{
+	if (policy->freq_table_sorted_ascending)
+		return cpufreq_table_find_index_al(policy, target_freq);
+	else
+		return cpufreq_table_find_index_dl(policy, target_freq);
+}
+
+/* Find highest freq at or below target in a table in ascending order */
+static inline int cpufreq_table_find_index_ah(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq == target_freq)
+			return i;
+
+		if (freq < target_freq) {
+			best = i;
+			continue;
+		}
+
+		/* No freq found below target_freq */
+		if (best == -1)
+			return i;
+
+		return best;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Find highest freq at or below target in a table in descending order */
+static inline int cpufreq_table_find_index_dh(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq <= target_freq)
+			return i;
+
+		best = i;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Works only on sorted freq-tables */
+static inline int cpufreq_table_find_index_h(struct cpufreq_policy *policy,
+					     unsigned int target_freq)
+{
+	if (policy->freq_table_sorted_ascending)
+		return cpufreq_table_find_index_ah(policy, target_freq);
+	else
+		return cpufreq_table_find_index_dh(policy, target_freq);
+}
+
+/* Find closest freq to target in a table in ascending order */
+static inline int cpufreq_table_find_index_ac(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq == target_freq)
+			return i;
+
+		if (freq < target_freq) {
+			best = i;
+			continue;
+		}
+
+		/* No freq found below target_freq */
+		if (best == -1)
+			return i;
+
+		/* Choose the closest freq */
+		if (target_freq - table[best].frequency > freq - target_freq)
+			return i;
+
+		return best;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Find closest freq to target in a table in descending order */
+static inline int cpufreq_table_find_index_dc(struct cpufreq_policy *policy,
+					      unsigned int target_freq)
+{
+	struct cpufreq_frequency_table *table = policy->freq_table;
+	unsigned int freq;
+	int i, best = -1;
+
+	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
+		freq = table[i].frequency;
+
+		if (freq_is_invalid(policy, freq))
+			continue;
+
+		if (freq == target_freq)
+			return i;
+
+		if (freq > target_freq) {
+			best = i;
+			continue;
+		}
+
+		/* No freq found below target_freq */
+		if (best == -1)
+			return i;
+
+		/* Choose the closest freq */
+		if (target_freq - table[best].frequency > freq - target_freq)
+			return i;
+
+		return best;
+	}
+
+	if (best == -1) {
+		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
+		return -EINVAL;
+	}
+
+	return best;
+}
+
+/* Works only on sorted freq-tables */
+static inline int cpufreq_table_find_index_c(struct cpufreq_policy *policy,
+					     unsigned int target_freq)
+{
+	if (policy->freq_table_sorted_ascending)
+		return cpufreq_table_find_index_ac(policy, target_freq);
+	else
+		return cpufreq_table_find_index_dc(policy, target_freq);
+}
+
+static inline int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
+						 unsigned int target_freq,
+						 unsigned int relation)
+{
+	if (unlikely(!policy->freq_table_sorted))
+		return cpufreq_table_find_index_unsorted(policy, target_freq,
+							 relation);
+
+	switch (relation) {
+	case CPUFREQ_RELATION_L:
+		return cpufreq_table_find_index_l(policy, target_freq);
+	case CPUFREQ_RELATION_H:
+		return cpufreq_table_find_index_h(policy, target_freq);
+	case CPUFREQ_RELATION_C:
+		return cpufreq_table_find_index_c(policy, target_freq);
+	default:
+		pr_err("%s: Invalid relation: %d\n", __func__, relation);
+		return -EINVAL;
+	}
+}
 #else
 static inline int cpufreq_boost_trigger_state(int state)
 {
-- 
2.7.1.410.g6faf27b

Re: [PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently

[Rafael J. Wysocki]

On Tuesday, June 07, 2016 03:55:14 PM Viresh Kumar wrote:
> cpufreq drivers aren't required to provide a sorted frequency table
> today, and even the ones which provide a sorted table aren't handled
> efficiently by cpufreq core.
> 
> This patch adds infrastructure to verify if the freq-table provided by
> the drivers is sorted or not, and use efficient helpers if they are
> sorted.
> 
> Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
> ---
>  drivers/cpufreq/freq_table.c |  67 +++++++++-
>  include/linux/cpufreq.h      | 284 ++++++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 343 insertions(+), 8 deletions(-)
> 
> diff --git a/drivers/cpufreq/freq_table.c b/drivers/cpufreq/freq_table.c
> index eac8bcbdaad1..0c1139a5f33a 100644
> --- a/drivers/cpufreq/freq_table.c
> +++ b/drivers/cpufreq/freq_table.c
> @@ -113,9 +113,9 @@ int cpufreq_generic_frequency_table_verify(struct cpufreq_policy *policy)
>  }
>  EXPORT_SYMBOL_GPL(cpufreq_generic_frequency_table_verify);
>  
> -int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
> -				    unsigned int target_freq,
> -				    unsigned int relation)
> +int cpufreq_table_find_index_unsorted(struct cpufreq_policy *policy,

Is the "find" part really necessary in this name?

> +				      unsigned int target_freq,
> +				      unsigned int relation)
>  {
>  	struct cpufreq_frequency_table optimal = {
>  		.driver_data = ~0,
> @@ -205,7 +205,7 @@ int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
>  		 table[index].frequency);
>  	return index;
>  }
> -EXPORT_SYMBOL_GPL(cpufreq_frequency_table_target);
> +EXPORT_SYMBOL_GPL(cpufreq_table_find_index_unsorted);
>  
>  int cpufreq_frequency_table_get_index(struct cpufreq_policy *policy,
>  		unsigned int freq)
> @@ -297,13 +297,70 @@ struct freq_attr *cpufreq_generic_attr[] = {
>  };
>  EXPORT_SYMBOL_GPL(cpufreq_generic_attr);
>  
> +static void set_freq_table_sorted(struct cpufreq_policy *policy)
> +{
> +	struct cpufreq_frequency_table *pos, *table = policy->freq_table;
> +	struct cpufreq_frequency_table *prev = NULL;
> +	int ascending = 0;
> +
> +	cpufreq_for_each_valid_entry(pos, table) {
> +		if (!prev) {
> +			prev = pos;
> +			continue;
> +		}
> +
> +		if (pos->frequency == prev->frequency) {
> +			pr_warn("Duplicate freq-table entries: %u\n",
> +				pos->frequency);

Shouldn't cpufreq_table_validate_and_show() simply return an error in this case?

Or do we know about any drivers having this problem potentially?

> +			continue;
> +		}
> +
> +		/* Frequency increased from prev to pos */
> +		if (pos->frequency > prev->frequency) {
> +			/* But frequency was decreasing earlier */
> +			if (ascending < 0) {
> +				policy->freq_table_sorted = false;
> +				pr_debug("Freq table is unsorted\n");
> +				return;
> +			}
> +
> +			ascending++;
> +		} else {
> +			/* Frequency decreased from prev to pos */
> +
> +			/* But frequency was increasing earlier */
> +			if (ascending > 0) {
> +				policy->freq_table_sorted = false;
> +				pr_debug("Freq table is unsorted\n");
> +				return;
> +			}
> +
> +			ascending--;
> +		}
> +
> +		prev = pos;
> +	}
> +
> +	policy->freq_table_sorted = true;
> +
> +	if (ascending > 0)
> +		policy->freq_table_sorted_ascending = true;

So what about making policy->freq_table_sorted an enum instead of using two
fields?

> +	else
> +		policy->freq_table_sorted_ascending = false;
> +
> +	pr_debug("Freq table is sorted in %s order\n",
> +		 ascending > 0 ? "ascending" : "descending");
> +}
> +
>  int cpufreq_table_validate_and_show(struct cpufreq_policy *policy,
>  				      struct cpufreq_frequency_table *table)
>  {
>  	int ret = cpufreq_frequency_table_cpuinfo(policy, table);
>  
> -	if (!ret)
> +	if (!ret) {
>  		policy->freq_table = table;
> +		set_freq_table_sorted(policy);
> +	}
>  
>  	return ret;
>  }
> diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h
> index c378776628b4..5133570e86f2 100644
> --- a/include/linux/cpufreq.h
> +++ b/include/linux/cpufreq.h
> @@ -86,7 +86,11 @@ struct cpufreq_policy {
>  					 * called, but you're in IRQ context */
>  
>  	struct cpufreq_user_policy user_policy;
> +
> +	/* Freq-table and its flags */
>  	struct cpufreq_frequency_table	*freq_table;
> +	bool			freq_table_sorted;
> +	bool			freq_table_sorted_ascending;
>  
>  	struct list_head        policy_list;
>  	struct kobject		kobj;
> @@ -597,9 +601,9 @@ int cpufreq_frequency_table_verify(struct cpufreq_policy *policy,
>  				   struct cpufreq_frequency_table *table);
>  int cpufreq_generic_frequency_table_verify(struct cpufreq_policy *policy);
>  
> -int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
> -				   unsigned int target_freq,
> -				   unsigned int relation);
> +int cpufreq_table_find_index_unsorted(struct cpufreq_policy *policy,
> +				      unsigned int target_freq,
> +				      unsigned int relation);
>  int cpufreq_frequency_table_get_index(struct cpufreq_policy *policy,
>  		unsigned int freq);
>  
> @@ -610,6 +614,280 @@ int cpufreq_boost_trigger_state(int state);
>  int cpufreq_boost_enabled(void);
>  int cpufreq_enable_boost_support(void);
>  bool policy_has_boost_freq(struct cpufreq_policy *policy);
> +
> +static inline bool freq_is_invalid(struct cpufreq_policy *policy, unsigned int frequency)
> +{
> +	if (unlikely(frequency == CPUFREQ_ENTRY_INVALID))
> +		return true;
> +
> +	if (unlikely((frequency < policy->min) || (frequency > policy->max)))
> +		return true;

This is confusing.  A frequency beyond min..max is not invalid, it is out of
bounds.

> +
> +	return false;
> +}
> +
> +/* Find lowest freq at or above target in a table in ascending order */
> +static inline int cpufreq_table_find_index_al(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq >= target_freq)
> +			return i;
> +
> +		best = i;
> +	}
> +
> +	if (best == -1) {
> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);

After a successful cpufreq_table_validate_and_show() that should be impossible,
shouldn't it?

> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}
> +
> +/* Find lowest freq at or above target in a table in descending order */
> +static inline int cpufreq_table_find_index_dl(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq == target_freq)
> +			return i;
> +
> +		if (freq > target_freq) {
> +			best = i;
> +			continue;
> +		}
> +
> +		/* No freq found below target_freq */
> +		if (best == -1)
> +			return i;
> +
> +		return best;
> +	}
> +
> +	if (best == -1) {
> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}
> +
> +/* Works only on sorted freq-tables */
> +static inline int cpufreq_table_find_index_l(struct cpufreq_policy *policy,
> +					     unsigned int target_freq)
> +{
> +	if (policy->freq_table_sorted_ascending)
> +		return cpufreq_table_find_index_al(policy, target_freq);
> +	else
> +		return cpufreq_table_find_index_dl(policy, target_freq);
> +}
> +
> +/* Find highest freq at or below target in a table in ascending order */
> +static inline int cpufreq_table_find_index_ah(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq == target_freq)
> +			return i;
> +
> +		if (freq < target_freq) {
> +			best = i;
> +			continue;
> +		}
> +
> +		/* No freq found below target_freq */
> +		if (best == -1)
> +			return i;
> +
> +		return best;
> +	}
> +
> +	if (best == -1) {
> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}
> +
> +/* Find highest freq at or below target in a table in descending order */
> +static inline int cpufreq_table_find_index_dh(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq <= target_freq)
> +			return i;
> +
> +		best = i;
> +	}
> +
> +	if (best == -1) {
> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}

I still don't see a reason for min/max checking in these routines.

So what is the reason?

> +
> +/* Works only on sorted freq-tables */
> +static inline int cpufreq_table_find_index_h(struct cpufreq_policy *policy,
> +					     unsigned int target_freq)
> +{
> +	if (policy->freq_table_sorted_ascending)
> +		return cpufreq_table_find_index_ah(policy, target_freq);
> +	else
> +		return cpufreq_table_find_index_dh(policy, target_freq);
> +}
> +
> +/* Find closest freq to target in a table in ascending order */
> +static inline int cpufreq_table_find_index_ac(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq == target_freq)
> +			return i;
> +
> +		if (freq < target_freq) {
> +			best = i;
> +			continue;
> +		}
> +
> +		/* No freq found below target_freq */
> +		if (best == -1)
> +			return i;
> +
> +		/* Choose the closest freq */
> +		if (target_freq - table[best].frequency > freq - target_freq)
> +			return i;
> +
> +		return best;
> +	}
> +
> +	if (best == -1) {

Can we actually get here?

> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}
> +
> +/* Find closest freq to target in a table in descending order */
> +static inline int cpufreq_table_find_index_dc(struct cpufreq_policy *policy,
> +					      unsigned int target_freq)
> +{
> +	struct cpufreq_frequency_table *table = policy->freq_table;
> +	unsigned int freq;
> +	int i, best = -1;
> +
> +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> +		freq = table[i].frequency;
> +
> +		if (freq_is_invalid(policy, freq))
> +			continue;
> +
> +		if (freq == target_freq)
> +			return i;
> +
> +		if (freq > target_freq) {
> +			best = i;
> +			continue;
> +		}
> +
> +		/* No freq found below target_freq */
> +		if (best == -1)
> +			return i;
> +
> +		/* Choose the closest freq */
> +		if (target_freq - table[best].frequency > freq - target_freq)
> +			return i;
> +
> +		return best;
> +	}
> +
> +	if (best == -1) {
> +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> +		return -EINVAL;
> +	}
> +
> +	return best;
> +}
> +
> +/* Works only on sorted freq-tables */
> +static inline int cpufreq_table_find_index_c(struct cpufreq_policy *policy,
> +					     unsigned int target_freq)
> +{
> +	if (policy->freq_table_sorted_ascending)
> +		return cpufreq_table_find_index_ac(policy, target_freq);
> +	else
> +		return cpufreq_table_find_index_dc(policy, target_freq);
> +}
> +
> +static inline int cpufreq_frequency_table_target(struct cpufreq_policy *policy,
> +						 unsigned int target_freq,
> +						 unsigned int relation)
> +{
> +	if (unlikely(!policy->freq_table_sorted))
> +		return cpufreq_table_find_index_unsorted(policy, target_freq,
> +							 relation);
> +
> +	switch (relation) {
> +	case CPUFREQ_RELATION_L:
> +		return cpufreq_table_find_index_l(policy, target_freq);
> +	case CPUFREQ_RELATION_H:
> +		return cpufreq_table_find_index_h(policy, target_freq);
> +	case CPUFREQ_RELATION_C:
> +		return cpufreq_table_find_index_c(policy, target_freq);
> +	default:
> +		pr_err("%s: Invalid relation: %d\n", __func__, relation);
> +		return -EINVAL;
> +	}
> +}
>  #else
>  static inline int cpufreq_boost_trigger_state(int state)
>  {

Thanks,
Rafael

Re: [PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently

[Viresh Kumar]

Hi Rafael,

Thanks for having a look at this..

On 23-06-16, 02:28, Rafael J. Wysocki wrote:
> On Tuesday, June 07, 2016 03:55:14 PM Viresh Kumar wrote:
> > +/* Find lowest freq at or above target in a table in ascending order */
> > +static inline int cpufreq_table_find_index_al(struct cpufreq_policy *policy,
> > +					      unsigned int target_freq)
> > +{
> > +	struct cpufreq_frequency_table *table = policy->freq_table;
> > +	unsigned int freq;
> > +	int i, best = -1;
> > +
> > +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> > +		freq = table[i].frequency;
> > +
> > +		if (freq_is_invalid(policy, freq))
> > +			continue;
> > +
> > +		if (freq >= target_freq)
> > +			return i;
> > +
> > +		best = i;
> > +	}
> > +
> > +	if (best == -1) {
> > +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> 
> After a successful cpufreq_table_validate_and_show() that should be impossible,
> shouldn't it?

This shouldn't be possible unless cpufreq_table_validate_and_show() has a bug,
or somehow that routine isn't called.

Though, to catch such bugs, what about WARN_ON(best == -1); ? The WARN() will
have an unlikely() statement as well to optimize it and we can catch the bugs as
well.

Or if you think we should just remove them..

> > +/* Find highest freq at or below target in a table in descending order */
> > +static inline int cpufreq_table_find_index_dh(struct cpufreq_policy *policy,
> > +					      unsigned int target_freq)
> > +{
> > +	struct cpufreq_frequency_table *table = policy->freq_table;
> > +	unsigned int freq;
> > +	int i, best = -1;
> > +
> > +	for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
> > +		freq = table[i].frequency;
> > +
> > +		if (freq_is_invalid(policy, freq))
> > +			continue;
> > +
> > +		if (freq <= target_freq)
> > +			return i;
> > +
> > +		best = i;
> > +	}
> > +
> > +	if (best == -1) {
> > +		WARN(1, "Invalid frequency table: %d\n", policy->cpu);
> > +		return -EINVAL;
> > +	}
> > +
> > +	return best;
> > +}
> 
> I still don't see a reason for min/max checking in these routines.
> 
> So what is the reason?

These routines are all part of the existing API cpufreq_frequency_table_target()
and that always had these checks. Over that, not all of its callers are ensuring
that the target-freq is clamped before this routine is called. And so we need to
make sure that these routines return a frequency between min/max only.

What do you say ?

-- 
viresh

Re: [PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently

[Rafael J. Wysocki]

On Sun, Jun 26, 2016 at 12:38 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:
> Hi Rafael,
>
> Thanks for having a look at this..
>
> On 23-06-16, 02:28, Rafael J. Wysocki wrote:
>> On Tuesday, June 07, 2016 03:55:14 PM Viresh Kumar wrote:
>> > +/* Find lowest freq at or above target in a table in ascending order */
>> > +static inline int cpufreq_table_find_index_al(struct cpufreq_policy *policy,
>> > +                                         unsigned int target_freq)
>> > +{
>> > +   struct cpufreq_frequency_table *table = policy->freq_table;
>> > +   unsigned int freq;
>> > +   int i, best = -1;
>> > +
>> > +   for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
>> > +           freq = table[i].frequency;
>> > +
>> > +           if (freq_is_invalid(policy, freq))
>> > +                   continue;
>> > +
>> > +           if (freq >= target_freq)
>> > +                   return i;
>> > +
>> > +           best = i;
>> > +   }
>> > +
>> > +   if (best == -1) {
>> > +           WARN(1, "Invalid frequency table: %d\n", policy->cpu);
>>
>> After a successful cpufreq_table_validate_and_show() that should be impossible,
>> shouldn't it?
>
> This shouldn't be possible unless cpufreq_table_validate_and_show() has a bug,
> or somehow that routine isn't called.

If it isn't called, the information on whether or not the table is
sorted may very well be bogus.

And it can double check the table right away to catch possible bugs
instead of running an additional if () every time a frequency is
selected.

> Though, to catch such bugs, what about WARN_ON(best == -1); ? The WARN() will
> have an unlikely() statement as well to optimize it and we can catch the bugs as
> well.
>
> Or if you think we should just remove them..

I would just drop those checks or do them once upfront.

>> > +/* Find highest freq at or below target in a table in descending order */
>> > +static inline int cpufreq_table_find_index_dh(struct cpufreq_policy *policy,
>> > +                                         unsigned int target_freq)
>> > +{
>> > +   struct cpufreq_frequency_table *table = policy->freq_table;
>> > +   unsigned int freq;
>> > +   int i, best = -1;
>> > +
>> > +   for (i = 0; table[i].frequency != CPUFREQ_TABLE_END; i++) {
>> > +           freq = table[i].frequency;
>> > +
>> > +           if (freq_is_invalid(policy, freq))
>> > +                   continue;
>> > +
>> > +           if (freq <= target_freq)
>> > +                   return i;
>> > +
>> > +           best = i;
>> > +   }
>> > +
>> > +   if (best == -1) {
>> > +           WARN(1, "Invalid frequency table: %d\n", policy->cpu);
>> > +           return -EINVAL;
>> > +   }
>> > +
>> > +   return best;
>> > +}
>>
>> I still don't see a reason for min/max checking in these routines.
>>
>> So what is the reason?
>
> These routines are all part of the existing API cpufreq_frequency_table_target()
> and that always had these checks.

Well, that's one of the reasons I've actively avoided that stuff in
the acpi-cpufreq's fast switch callback. :-)

> Over that, not all of its callers are ensuring
> that the target-freq is clamped before this routine is called. And so we need to
> make sure that these routines return a frequency between min/max only.
>
> What do you say ?

I think that the min/max checks at that level are just bogus, because
they are racy and that may lead to a situation where none of the
frequencies appears to be suitable while at least one of them must be.

So IMO all of the callers should be made clamp the target frequency
between min and max and those checks should be dropped from the
low-level helpers.

Thanks,
Rafael

Re: [PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently

[Viresh Kumar]

On Mon, Jun 27, 2016 at 5:58 AM, Rafael J. Wysocki <rafael@kernel.org> wrote:
> On Sun, Jun 26, 2016 at 12:38 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:

> So IMO all of the callers should be made clamp the target frequency
> between min and max and those checks should be dropped from the
> low-level helpers.

Okay, so doing this from all these very low level helpers can be avoided
by moving them to cpufreq_frequency_table_target() at least for now.

Later on we can see on how we can update the callers and see how
it works best.

Thanks for the review.

--
viresh

[PATCH V4 2/2] cpufreq: Reuse new freq-table helpers

[Viresh Kumar]

This patch migrates few users of cpufreq tables to the new helpers that
work on sorted freq-tables.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
---
 drivers/cpufreq/acpi-cpufreq.c         | 14 ++++----------
 drivers/cpufreq/amd_freq_sensitivity.c |  4 ++--
 drivers/cpufreq/cpufreq_ondemand.c     |  6 ++----
 drivers/cpufreq/powernv-cpufreq.c      |  3 +--
 drivers/cpufreq/s5pv210-cpufreq.c      |  3 +--
 5 files changed, 10 insertions(+), 20 deletions(-)

diff --git a/drivers/cpufreq/acpi-cpufreq.c b/drivers/cpufreq/acpi-cpufreq.c
index 32a15052f363..11c9a078e0fd 100644
--- a/drivers/cpufreq/acpi-cpufreq.c
+++ b/drivers/cpufreq/acpi-cpufreq.c
@@ -468,20 +468,14 @@ unsigned int acpi_cpufreq_fast_switch(struct cpufreq_policy *policy,
 	struct acpi_cpufreq_data *data = policy->driver_data;
 	struct acpi_processor_performance *perf;
 	struct cpufreq_frequency_table *entry;
-	unsigned int next_perf_state, next_freq, freq;
+	unsigned int next_perf_state, next_freq, index;
 
 	/*
 	 * Find the closest frequency above target_freq.
-	 *
-	 * The table is sorted in the reverse order with respect to the
-	 * frequency and all of the entries are valid (see the initialization).
 	 */
-	entry = policy->freq_table;
-	do {
-		entry++;
-		freq = entry->frequency;
-	} while (freq >= target_freq && freq != CPUFREQ_TABLE_END);
-	entry--;
+	index = cpufreq_table_find_index_dl(policy, target_freq);
+
+	entry = &policy->freq_table[index];
 	next_freq = entry->frequency;
 	next_perf_state = entry->driver_data;
 
diff --git a/drivers/cpufreq/amd_freq_sensitivity.c b/drivers/cpufreq/amd_freq_sensitivity.c
index 6d5dc04c3a37..042023bbbf62 100644
--- a/drivers/cpufreq/amd_freq_sensitivity.c
+++ b/drivers/cpufreq/amd_freq_sensitivity.c
@@ -91,8 +91,8 @@ static unsigned int amd_powersave_bias_target(struct cpufreq_policy *policy,
 		else {
 			unsigned int index;
 
-			index = cpufreq_frequency_table_target(policy,
-				policy->cur - 1, CPUFREQ_RELATION_H);
+			index = cpufreq_table_find_index_h(policy,
+							   policy->cur - 1);
 			freq_next = policy->freq_table[index].frequency;
 		}
 
diff --git a/drivers/cpufreq/cpufreq_ondemand.c b/drivers/cpufreq/cpufreq_ondemand.c
index 0c93cd9dee99..3a1f49f5f4c6 100644
--- a/drivers/cpufreq/cpufreq_ondemand.c
+++ b/drivers/cpufreq/cpufreq_ondemand.c
@@ -85,11 +85,9 @@ static unsigned int generic_powersave_bias_target(struct cpufreq_policy *policy,
 	freq_avg = freq_req - freq_reduc;
 
 	/* Find freq bounds for freq_avg in freq_table */
-	index = cpufreq_frequency_table_target(policy, freq_avg,
-					       CPUFREQ_RELATION_H);
+	index = cpufreq_table_find_index_h(policy, freq_avg);
 	freq_lo = freq_table[index].frequency;
-	index = cpufreq_frequency_table_target(policy, freq_avg,
-					       CPUFREQ_RELATION_L);
+	index = cpufreq_table_find_index_l(policy, freq_avg);
 	freq_hi = freq_table[index].frequency;
 
 	/* Find out how long we have to be in hi and lo freqs */
diff --git a/drivers/cpufreq/powernv-cpufreq.c b/drivers/cpufreq/powernv-cpufreq.c
index b29c5c20c3a1..2a2920c4fdf9 100644
--- a/drivers/cpufreq/powernv-cpufreq.c
+++ b/drivers/cpufreq/powernv-cpufreq.c
@@ -760,8 +760,7 @@ void powernv_cpufreq_work_fn(struct work_struct *work)
 		struct cpufreq_policy policy;
 
 		cpufreq_get_policy(&policy, cpu);
-		index = cpufreq_frequency_table_target(&policy, policy.cur,
-					       CPUFREQ_RELATION_C);
+		index = cpufreq_table_find_index_c(&policy, policy.cur);
 		powernv_cpufreq_target_index(&policy, index);
 		cpumask_andnot(&mask, &mask, policy.cpus);
 	}
diff --git a/drivers/cpufreq/s5pv210-cpufreq.c b/drivers/cpufreq/s5pv210-cpufreq.c
index 4f4e9df9b7fc..9e07588ea9f5 100644
--- a/drivers/cpufreq/s5pv210-cpufreq.c
+++ b/drivers/cpufreq/s5pv210-cpufreq.c
@@ -246,8 +246,7 @@ static int s5pv210_target(struct cpufreq_policy *policy, unsigned int index)
 	new_freq = s5pv210_freq_table[index].frequency;
 
 	/* Finding current running level index */
-	priv_index = cpufreq_frequency_table_target(policy, old_freq,
-						    CPUFREQ_RELATION_H);
+	priv_index = cpufreq_table_find_index_h(policy, old_freq);
 
 	arm_volt = dvs_conf[index].arm_volt;
 	int_volt = dvs_conf[index].int_volt;
-- 
2.7.1.410.g6faf27b

Re: [PATCH V4 0/2] cpufreq: Sort policy->freq_table

[Rafael J. Wysocki]

On Tuesday, June 07, 2016 03:55:13 PM Viresh Kumar wrote:
> Hi Rafael,
> 
> I have spent some more time on this stuff and finally came out with a
> very simple solution. I hope you will like it more than the previous
> versions.
> 
> Instead of trying to sort the freq-table passed by the drivers, which
> was complicated and would have broken some drivers for sure, this patch
> just checks if the freq-table is sorted or not.
> 
> If it is sorted, then we just use a different set of helpers for it. The
> table can be sorted in both ascending and descending orders now and
> helpers are present for both the cases.

Well, that's something I was thinking about from the start. :-)

> All the patches are pushed here for testing in case anyone wants to try:
> git://git.kernel.org/pub/scm/linux/kernel/git/vireshk/pm.git cpufreq/sorted-freq-table
> 
> V3->V4:
> - Written from scratch really, completely different approach.

I'll look at the code later this week.

Thanks,
Rafael

Re: [PATCH V4 0/2] cpufreq: Sort policy->freq_table

[Viresh Kumar]

On 08-06-16, 02:19, Rafael J. Wysocki wrote:
> On Tuesday, June 07, 2016 03:55:13 PM Viresh Kumar wrote:
> > Hi Rafael,
> > 
> > I have spent some more time on this stuff and finally came out with a
> > very simple solution. I hope you will like it more than the previous
> > versions.
> > 
> > Instead of trying to sort the freq-table passed by the drivers, which
> > was complicated and would have broken some drivers for sure, this patch
> > just checks if the freq-table is sorted or not.
> > 
> > If it is sorted, then we just use a different set of helpers for it. The
> > table can be sorted in both ascending and descending orders now and
> > helpers are present for both the cases.
> 
> Well, that's something I was thinking about from the start. :-)
> 
> > All the patches are pushed here for testing in case anyone wants to try:
> > git://git.kernel.org/pub/scm/linux/kernel/git/vireshk/pm.git cpufreq/sorted-freq-table
> > 
> > V3->V4:
> > - Written from scratch really, completely different approach.
> 
> I'll look at the code later this week.

Hi Rafael,

Did you get a chance to look at these? Steve may be blocked on this :)

-- 
viresh

Re: [PATCH V4 0/2] cpufreq: Sort policy->freq_table

[Rafael J. Wysocki]

On Thu, Jun 16, 2016 at 6:17 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:
> On 08-06-16, 02:19, Rafael J. Wysocki wrote:
>> On Tuesday, June 07, 2016 03:55:13 PM Viresh Kumar wrote:
>> > Hi Rafael,
>> >
>> > I have spent some more time on this stuff and finally came out with a
>> > very simple solution. I hope you will like it more than the previous
>> > versions.
>> >
>> > Instead of trying to sort the freq-table passed by the drivers, which
>> > was complicated and would have broken some drivers for sure, this patch
>> > just checks if the freq-table is sorted or not.
>> >
>> > If it is sorted, then we just use a different set of helpers for it. The
>> > table can be sorted in both ascending and descending orders now and
>> > helpers are present for both the cases.
>>
>> Well, that's something I was thinking about from the start. :-)
>>
>> > All the patches are pushed here for testing in case anyone wants to try:
>> > git://git.kernel.org/pub/scm/linux/kernel/git/vireshk/pm.git cpufreq/sorted-freq-table
>> >
>> > V3->V4:
>> > - Written from scratch really, completely different approach.
>>
>> I'll look at the code later this week.
>
> Hi Rafael,
>
> Did you get a chance to look at these? Steve may be blocked on this :)

I know, but I have stuff to do other than cpufreq.

And in particular regression fixes take precedence, of course.