Hi Guys,
This work in inspired by some of the concerns raised by Steve in one of his patchset.
Currently, the cpufreq drivers aren't required to provide a sorted list of frequencies to the cpufreq-core and so traversing that list match a target frequency is very inefficient.
This is not bearable by, for example, the fast-switch path of schedutil governor and so we have moved the traversing logic local to the acpi-cpufreq driver for now. That is better handled in the core, but it has to be efficient.
OTOH, even for traditional governors without a fast-switch path, it would be much better to be able to traverse this table quickly.
The ideal solution would be to keep a single freq-table in struct cpufreq_policy, that will be sorted as well. But there are few dependencies due to which it can't be done today (Hint: cpufreq drivers are abusing the 'index' passed to them, to refer to multiple arrays).
And so for now, lets create a separate table local to the cpufreq-core only.
To use that, another API cpufreq_find_target_index() is created as well and few users are migrated to it.
Lightly tested on Exynos board, frequencies were getting selected as expected.
-- viresh
Viresh Kumar (2): cpufreq: Store sorted frequency table cpufreq: Implement cpufreq_find_target_index() to traverse sorted list
drivers/cpufreq/acpi-cpufreq.c | 18 ++-- drivers/cpufreq/cpufreq.c | 48 ++++++----- drivers/cpufreq/freq_table.c | 191 +++++++++++++++++++++++++++++++++++++++++ include/linux/cpufreq.h | 7 ++ 4 files changed, 231 insertions(+), 33 deletions(-)
The drivers aren't required to provide a sorted frequency table today, and its not optimal to work on an unsorted freq table.
To simplify and improve code performance, create a frequency table within core and keep it sorted in ascending order.
Note that this should eventually replace policy->freq_table itself, which isn't done currently as few drivers will break due to that.
Signed-off-by: Viresh Kumar viresh.kumar@linaro.org --- drivers/cpufreq/cpufreq.c | 23 ++++++++++----- drivers/cpufreq/freq_table.c | 67 ++++++++++++++++++++++++++++++++++++++++++++ include/linux/cpufreq.h | 3 ++ 3 files changed, 86 insertions(+), 7 deletions(-)
diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index c6a14ba239a2..a6bdb55350f4 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -1146,6 +1146,16 @@ static void cpufreq_policy_free(struct cpufreq_policy *policy, bool notify) kfree(policy); }
+static void cpufreq_policy_exit(struct cpufreq_policy *policy) +{ + if (!cpufreq_driver->exit) + return; + + cpufreq_driver->exit(policy); + free_sorted_freq_table(policy); + policy->freq_table = NULL; +} + static int cpufreq_online(unsigned int cpu) { struct cpufreq_policy *policy; @@ -1187,6 +1197,10 @@ static int cpufreq_online(unsigned int cpu) goto out_free_policy; }
+ ret = create_sorted_freq_table(policy); + if (ret) + goto out_exit_policy; + down_write(&policy->rwsem);
if (new_policy) { @@ -1300,9 +1314,7 @@ static int cpufreq_online(unsigned int cpu)
out_exit_policy: up_write(&policy->rwsem); - - if (cpufreq_driver->exit) - cpufreq_driver->exit(policy); + cpufreq_policy_exit(policy); out_free_policy: cpufreq_policy_free(policy, !new_policy); return ret; @@ -1387,10 +1399,7 @@ static void cpufreq_offline(unsigned int cpu) * since this is a core component, and is essential for the * subsequent light-weight ->init() to succeed. */ - if (cpufreq_driver->exit) { - cpufreq_driver->exit(policy); - policy->freq_table = NULL; - } + cpufreq_policy_exit(policy);
unlock: up_write(&policy->rwsem); diff --git a/drivers/cpufreq/freq_table.c b/drivers/cpufreq/freq_table.c index 4e5c5dbfed7a..ba97912973c4 100644 --- a/drivers/cpufreq/freq_table.c +++ b/drivers/cpufreq/freq_table.c @@ -13,6 +13,7 @@
#include <linux/cpufreq.h> #include <linux/module.h> +#include <linux/slab.h>
/********************************************************************* * FREQUENCY TABLE HELPERS * @@ -298,6 +299,72 @@ struct freq_attr *cpufreq_generic_attr[] = { }; EXPORT_SYMBOL_GPL(cpufreq_generic_attr);
+static int next_larger(struct cpufreq_policy *policy, unsigned int freq, + struct cpufreq_frequency_table *table) +{ + struct cpufreq_frequency_table *pos; + unsigned int next_freq = ~0; + int index = -EINVAL; + + cpufreq_for_each_valid_entry(pos, table) { + if (pos->frequency <= freq) + continue; + + if (next_freq > pos->frequency) { + next_freq = pos->frequency; + index = pos - table; + } + } + + return index; +} + +void free_sorted_freq_table(struct cpufreq_policy *policy) +{ + kfree(policy->sorted_freq_table); + policy->sorted_freq_table = NULL; +} + +int create_sorted_freq_table(struct cpufreq_policy *policy) +{ + struct cpufreq_frequency_table *pos, *new_table; + unsigned int freq, index, i, count = 0; + struct cpufreq_frequency_table *table = policy->freq_table; + + if (!table) + return 0; + + cpufreq_for_each_valid_entry(pos, table) + count++; + + /* Extra entry for CPUFREQ_TABLE_END */ + count++; + + new_table = kmalloc_array(count, sizeof(*new_table), GFP_KERNEL); + if (!new_table) + return -ENOMEM; + + for (i = 0, freq = 0; i < count - 1; i++) { + index = next_larger(policy, freq, table); + if (index == -EINVAL) + break; + + /* + * driver_data of the sorted table points to the index of the + * unsorted table. + */ + new_table[i].driver_data = index; + new_table[i].frequency = table[index].frequency; + + freq = table[index].frequency; + } + + new_table[i].frequency = CPUFREQ_TABLE_END; + policy->sorted_freq_table = new_table; + + return 0; +} + int cpufreq_table_validate_and_show(struct cpufreq_policy *policy, struct cpufreq_frequency_table *table) { diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 7ed93c310c08..08cf508948dd 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -87,6 +87,7 @@ struct cpufreq_policy {
struct cpufreq_user_policy user_policy; struct cpufreq_frequency_table *freq_table; + struct cpufreq_frequency_table *sorted_freq_table;
struct list_head policy_list; struct kobject kobj; @@ -592,6 +593,8 @@ static inline void dev_pm_opp_free_cpufreq_table(struct device *dev,
int cpufreq_frequency_table_cpuinfo(struct cpufreq_policy *policy, struct cpufreq_frequency_table *table); +int create_sorted_freq_table(struct cpufreq_policy *policy); +void free_sorted_freq_table(struct cpufreq_policy *policy);
int cpufreq_frequency_table_verify(struct cpufreq_policy *policy, struct cpufreq_frequency_table *table);
cpufreq core keeps another table of sorted frequencies and that can be used to find a match quickly, instead of relying on cpufreq_frequency_table_target() which will be very inefficient comparatively.
The new routine(s) traverse the table of sorted frequencies and return an index into the policy->freq_table which is used everywhere else in the code.
Few important users of cpufreq_frequency_table_target() are also migrated to use it.
Tested on Exynos board with both ondemand schedutil governor and confirmed with help of various print messages that we are eventually switching to the desired frequency based on a target frequency.
Note that migrating all other users of cpufreq_frequency_table_target() will require some cleanups first and so that will be done separately.
Signed-off-by: Viresh Kumar viresh.kumar@linaro.org --- drivers/cpufreq/acpi-cpufreq.c | 18 +++--- drivers/cpufreq/cpufreq.c | 25 +++------ drivers/cpufreq/freq_table.c | 124 +++++++++++++++++++++++++++++++++++++++++ include/linux/cpufreq.h | 4 ++ 4 files changed, 145 insertions(+), 26 deletions(-)
diff --git a/drivers/cpufreq/acpi-cpufreq.c b/drivers/cpufreq/acpi-cpufreq.c index 32a15052f363..0b47a4ed7130 100644 --- a/drivers/cpufreq/acpi-cpufreq.c +++ b/drivers/cpufreq/acpi-cpufreq.c @@ -468,20 +468,18 @@ 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; + int ret;
/* * 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--; + ret = cpufreq_find_target_index(policy, target_freq, CPUFREQ_RELATION_L, + &index); + if (WARN_ON(ret)) + return 0; + + entry = &policy->freq_table[index]; next_freq = entry->frequency; next_perf_state = entry->driver_data;
diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index a6bdb55350f4..712a4564c59b 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -1870,14 +1870,17 @@ static int __target_intermediate(struct cpufreq_policy *policy, return ret; }
-static int __target_index(struct cpufreq_policy *policy, - struct cpufreq_frequency_table *freq_table, int index) +static int __target_index(struct cpufreq_policy *policy, int index) { struct cpufreq_freqs freqs = {.old = policy->cur, .flags = 0}; + unsigned int new_freq = policy->freq_table[index].frequency; unsigned int intermediate_freq = 0; int retval = -EINVAL; bool notify;
+ if (new_freq == policy->cur) + return 0; + notify = !(cpufreq_driver->flags & CPUFREQ_ASYNC_NOTIFICATION); if (notify) { /* Handle switching to intermediate frequency */ @@ -1892,7 +1895,7 @@ static int __target_index(struct cpufreq_policy *policy, freqs.old = freqs.new; }
- freqs.new = freq_table[index].frequency; + freqs.new = new_freq; pr_debug("%s: cpu: %d, oldfreq: %u, new freq: %u\n", __func__, policy->cpu, freqs.old, freqs.new);
@@ -1929,7 +1932,6 @@ int __cpufreq_driver_target(struct cpufreq_policy *policy, unsigned int relation) { unsigned int old_target_freq = target_freq; - struct cpufreq_frequency_table *freq_table; int index, retval;
if (cpufreq_disabled()) @@ -1959,23 +1961,14 @@ int __cpufreq_driver_target(struct cpufreq_policy *policy, if (!cpufreq_driver->target_index) return -EINVAL;
- freq_table = cpufreq_frequency_get_table(policy->cpu); - if (unlikely(!freq_table)) { - pr_err("%s: Unable to find freq_table\n", __func__); - return -EINVAL; - } - - retval = cpufreq_frequency_table_target(policy, freq_table, target_freq, - relation, &index); + retval = cpufreq_find_target_index(policy, target_freq, relation, + &index); if (unlikely(retval)) { pr_err("%s: Unable to find matching freq\n", __func__); return retval; }
- if (freq_table[index].frequency == policy->cur) - return 0; - - return __target_index(policy, freq_table, index); + return __target_index(policy, index); } EXPORT_SYMBOL_GPL(__cpufreq_driver_target);
diff --git a/drivers/cpufreq/freq_table.c b/drivers/cpufreq/freq_table.c index ba97912973c4..5217d93f1ab8 100644 --- a/drivers/cpufreq/freq_table.c +++ b/drivers/cpufreq/freq_table.c @@ -116,6 +116,130 @@ int cpufreq_generic_frequency_table_verify(struct cpufreq_policy *policy) } EXPORT_SYMBOL_GPL(cpufreq_generic_frequency_table_verify);
+static int cpufreq_find_target_index_l(struct cpufreq_policy *policy, + unsigned int target_freq) +{ + struct cpufreq_frequency_table *pos, *best = NULL; + unsigned int freq; + + cpufreq_for_each_valid_entry(pos, policy->sorted_freq_table) { + freq = pos->frequency; + + if ((freq < policy->min) || (freq > policy->max)) + continue; + + if (freq >= target_freq) + return pos->driver_data; + + best = pos; + } + + if (best) + return best->driver_data; + + return -EINVAL; +} + +static int cpufreq_find_target_index_h(struct cpufreq_policy *policy, + unsigned int target_freq) +{ + struct cpufreq_frequency_table *pos, *best = NULL; + unsigned int freq; + + cpufreq_for_each_valid_entry(pos, policy->sorted_freq_table) { + freq = pos->frequency; + + if ((freq < policy->min) || (freq > policy->max)) + continue; + + if (freq == target_freq) + return pos->driver_data; + + if (freq < target_freq) { + best = pos; + continue; + } + + /* No freq found below target_freq */ + if (!best) + best = pos; + break; + } + + if (best) + return best->driver_data; + + return -EINVAL; +} + +static int cpufreq_find_target_index_c(struct cpufreq_policy *policy, + unsigned int target_freq) +{ + struct cpufreq_frequency_table *pos, *best = NULL; + unsigned int freq; + + cpufreq_for_each_valid_entry(pos, policy->sorted_freq_table) { + freq = pos->frequency; + + if ((freq < policy->min) || (freq > policy->max)) + continue; + + if (freq == target_freq) + return pos->driver_data; + + if (freq < target_freq) { + best = pos; + continue; + } + + /* No freq found below target_freq */ + if (!best) { + best = pos; + break; + } + + /* Choose the closest freq */ + if (target_freq - best->frequency > freq - target_freq) + best = pos; + + break; + } + + if (best) + return best->driver_data; + + return -EINVAL; +} + +int cpufreq_find_target_index(struct cpufreq_policy *policy, + unsigned int target_freq, unsigned int relation, + unsigned int *index) +{ + int new_index; + + switch (relation) { + case CPUFREQ_RELATION_L: + new_index = cpufreq_find_target_index_l(policy, target_freq); + break; + case CPUFREQ_RELATION_H: + new_index = cpufreq_find_target_index_h(policy, target_freq); + break; + case CPUFREQ_RELATION_C: + new_index = cpufreq_find_target_index_c(policy, target_freq); + break; + default: + return -EINVAL; + } + + if (new_index == -EINVAL) + return new_index; + + *index = new_index; + return 0; +} +EXPORT_SYMBOL_GPL(cpufreq_find_target_index); + +/* Deprecated */ int cpufreq_frequency_table_target(struct cpufreq_policy *policy, struct cpufreq_frequency_table *table, unsigned int target_freq, diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 08cf508948dd..03e88fb3d2c0 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -600,6 +600,10 @@ 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_find_target_index(struct cpufreq_policy *policy, + unsigned int target_freq, unsigned int relation, + unsigned int *index); +/* Deprecated */ int cpufreq_frequency_table_target(struct cpufreq_policy *policy, struct cpufreq_frequency_table *table, unsigned int target_freq,
On Tue, May 31, 2016 at 1:36 PM, Viresh Kumar viresh.kumar@linaro.org wrote:
I'm not particularly liking this due to the possible confusion that may result from it.
Perhaps we can require drivers implementing ->fast_switch to sort their frequency tables to start with? Or maybe make the core check whether or not the table is sorted and in what order and handle it accordingly?
Let's just think about the design here for a while, OK?
On Wed, Jun 01, 2016 at 12:50:41AM +0200, Rafael J. Wysocki wrote:
This would be required beyond drivers implementing fast_switch - cpufreq_driver_resolve_freq() (which started this discussion) is called for slow path transitions as well.
Checking the table type and performing the associated lookup seems workable to me though it adds a bit of complexity.
Also what about leaving it as is? I didn't fully catch the concern with abuse in the series I posted, and it pushes this complexity of dealing with the freq table efficiently down into the driver, which is best suited for that IMO.
Another thought is that it'd be nice to eventually reduce cpufreq_driver_{fast_switch,resolve_freq} into simple inline functions so that we could jump to the driver directly from schedutil, eliminating a function call.
thanks, Steve
On 31-05-16, 18:08, Steve Muckle wrote:
Checking the table type
I hope you are talking about my patch here and in that case its not table-type, but relation-type.
So, your series kind of just triggered this thing, but freq matching should always be really fast. And I feel that we should attempt to making it fast.
Not really. Its a single driver today, it will be 20 drivers tomorrow. We really want to do such common stuff in core whenever it is possible.
That's kind of orthogonal to this :)
On Wed, Jun 01, 2016 at 04:16:12PM +0530, Viresh Kumar wrote:
I was referring to Rafael's comment about having the core check how the table was sorted and process it accordingly. It doesn't apply to the approach in your patches.
I agree with that goal.
Handling freq table walking exclusively in cpufreq core will add to the size of stuff to be inlined in schedutil to avoid extra function calls.
thanks, Steve
On Tuesday, May 31, 2016 06:08:56 PM Steve Muckle wrote:
The concern is that all drivers using frequency tables would probably implement the callbacks in question in a very similar way, leading to quite a bit of code duplication. That's rarely a good thing.
Well, let's do one thing at a time. :-)
Thanks, Rafael
On 01-06-16, 00:50, Rafael J. Wysocki wrote:
I'm not particularly liking this due to the possible confusion that may result from it.
I have gotten rid of most of it now in V2.
Perhaps we can require drivers implementing ->fast_switch to sort their frequency tables to start with?
I wasn't *only* concerned about the fast-switch case, but the case of normal governors that we use today. After all that's what everybody is using right now.
And I feel (Maybe you as well), that we are better off using a single optimized path for all cases. Otherwise things start getting too messy too soon.
Or maybe make the core check whether or not the table is sorted
Platforms are already broken for this, and so wouldn't be possible to check for existing governors.
and in what order and handle it accordingly?
We should really be handling a single order to avoid complications in it :)
Let's just think about the design here for a while, OK?
Sure. Lets see how bad is V2.
On Wednesday, June 01, 2016 04:12:43 PM Viresh Kumar wrote:
Sure, but the "to start with" part of my question was essential.
The ordering didn't matter before, so drivers may do silly things related to it and those may break if we try to change the rules wholesale.
In turn, if the (prospective) ->fast_switch users are required to clean up their stuff while working on implementig it, we could avoid that breakage, or at least some of it.
I really don't know what you wanted to say here.
I'm not sure how complicated it would be to be honest. The sorted cases are both very similar and it should be possible to handle them both in the same code regardless of the direction. The unsorted case is special, but that's a matter of an extra branch per function.
Anyway, I agree that using one ordering would be cleaner, but I'm sort of concerned about how painful the switch-over may be to the users.
Thanks, Rafael
On 01-06-16, 18:37, Rafael J. Wysocki wrote:
We can make that a requirement, but I am not sure if that will help us much. I want to use the same routines for the target_index() callbacks and the fast_switch() ones.
And that's what I have done in V2 of this series.
The ordering didn't matter before, so drivers may do silly things related to it
Yes they do and that's why I couldn't get rid of policy->freq_table for now. Though I have plans to sort that out.
and those may break if we try to change the rules wholesale.
Yes. But the V2 of this series isn't making any such change. Just that we are keeping a backup sorted table (which drivers wouldn't know about) to find the right match. We will still keep passing the index to their *unsorted* tables in target_index() for example.
I understand your point of view, but I think V2 is sorting all that out without breaking anything at all.
Oh, I was saying that existing drivers of course don't guarantee that today, and if we want to make the search fast for existing governors, we wouldn't be able to do it for all.
Anyway, I agree that using one ordering would be cleaner, but I'm sort of concerned about how painful the switch-over may be to the users.
They wouldn't notice at all. V2 handles that properly.
linaro-kernel@lists.linaro.org
-
Rafael J. Wysocki -
Rafael J. Wysocki -
Steve Muckle -
Viresh Kumar