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

From: Rafael J. Wysocki
Date: Wed Jun 22 2016 - 20:24:51 EST

Next message: Rafael J. Wysocki: "Re: [PATCH] acpi: pci_slot: Use more common logging style"
Previous message: Andy Lutomirski: "Re: [RFC PATCH v2 05/18] sched: add task flag for preempt IRQ tracking"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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@xxxxxxxxxx>
> ---
> 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

Next message: Rafael J. Wysocki: "Re: [PATCH] acpi: pci_slot: Use more common logging style"
Previous message: Andy Lutomirski: "Re: [RFC PATCH v2 05/18] sched: add task flag for preempt IRQ tracking"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]