[PATCH 0/2] cpufreq: Use sorted frequency tables

[PATCH 0/2] cpufreq: Use sorted frequency tables

[Viresh Kumar]

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(-)

-- 
2.7.1.410.g6faf27b

[PATCH 1/2] cpufreq: Store sorted frequency table

[Viresh Kumar]

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);
-- 
2.7.1.410.g6faf27b

[PATCH 2/2] cpufreq: Implement cpufreq_find_target_index() to traverse sorted list

[Viresh Kumar]

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,
-- 
2.7.1.410.g6faf27b

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Rafael J. Wysocki]

On Tue, May 31, 2016 at 1:36 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:
> 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.

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?

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Steve Muckle]

On Wed, Jun 01, 2016 at 12:50:41AM +0200, Rafael J. Wysocki wrote:
> On Tue, May 31, 2016 at 1:36 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:
> > 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.
> 
> 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?

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

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Viresh Kumar]

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.

-- 
viresh

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Viresh Kumar]

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.

> and performing the associated lookup seems
> workable to me though it adds a bit of complexity.
> 
> Also what about leaving it as is?

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.

> 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.

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.

> 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.

That's kind of orthogonal to this :)

-- 
viresh

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Rafael J. Wysocki]

On Wednesday, June 01, 2016 04:12:43 PM Viresh Kumar wrote:
> 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.

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.

> 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.

I really don't know what you wanted to say here.

> > and in what order and handle it
> > accordingly?
> 
> We should really be handling a single order to avoid complications in
> it :)

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

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Rafael J. Wysocki]

On Tuesday, May 31, 2016 06:08:56 PM Steve Muckle wrote:
> On Wed, Jun 01, 2016 at 12:50:41AM +0200, Rafael J. Wysocki wrote:
> > On Tue, May 31, 2016 at 1:36 PM, Viresh Kumar <viresh.kumar@linaro.org> wrote:
> > > 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.
> > 
> > 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?
> 
> 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.

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.

> 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.

Well, let's do one thing at a time. :-)

Thanks,
Rafael

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Steve Muckle]

On Wed, Jun 01, 2016 at 04:16:12PM +0530, Viresh Kumar wrote:
> 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.

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.

> 
> > and performing the associated lookup seems
> > workable to me though it adds a bit of complexity.
> > 
> > Also what about leaving it as is?
> 
> 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.

I agree with that goal.

> 
> > 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.
> 
> 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.
> 
> > 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.
> 
> That's kind of orthogonal to this :)

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

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Steve Muckle]

On Wed, Jun 01, 2016 at 06:40:36PM +0200, Rafael J. Wysocki wrote:
> > 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.
> 
> 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.

Could this be assuaged with helper macros exported by cpufreq?

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Rafael J. Wysocki]

On Wednesday, June 01, 2016 12:37:09 PM Steve Muckle wrote:
> On Wed, Jun 01, 2016 at 06:40:36PM +0200, Rafael J. Wysocki wrote:
> > > 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.
> > 
> > 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.
> 
> Could this be assuaged with helper macros exported by cpufreq?

In principle, it could.

Another option might be to provide default implementations of those
callbacks for drivers using frequency tables.

Re: [PATCH 0/2] cpufreq: Use sorted frequency tables

[Viresh Kumar]

On 01-06-16, 18:37, Rafael J. Wysocki wrote:
> On Wednesday, June 01, 2016 04:12:43 PM Viresh Kumar wrote:
> > 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.
> 
> Sure, but the "to start with" part of my question was essential.

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.

> 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 understand your point of view, but I think V2 is sorting all that
out without breaking anything at all.

> > > 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.
> 
> I really don't know what you wanted to say here.

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.

-- 
viresh