From patchwork Tue Jun 7 10:25:14 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Viresh Kumar X-Patchwork-Id: 69486 Delivered-To: patch@linaro.org Received: by 10.140.106.246 with SMTP id e109csp1900243qgf; Tue, 7 Jun 2016 03:25:53 -0700 (PDT) X-Received: by 10.107.138.6 with SMTP id m6mr7290607iod.181.1465295153380; Tue, 07 Jun 2016 03:25:53 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id t10si32567336paw.5.2016.06.07.03.25.52; Tue, 07 Jun 2016 03:25:53 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-pm-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@linaro.org; spf=pass (google.com: best guess record for domain of linux-pm-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-pm-owner@vger.kernel.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754890AbcFGKZa (ORCPT + 14 others); Tue, 7 Jun 2016 06:25:30 -0400 Received: from mail-pf0-f181.google.com ([209.85.192.181]:32855 "EHLO mail-pf0-f181.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754888AbcFGKZ0 (ORCPT ); Tue, 7 Jun 2016 06:25:26 -0400 Received: by mail-pf0-f181.google.com with SMTP id y124so17139593pfy.0 for ; Tue, 07 Jun 2016 03:25:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :in-reply-to:references; bh=v1AJaOwtYZcru/0NBCag/GtcygGS4K8MThIYi2P57G0=; b=CGsDXYnUml6CPDUTcdGCvwJ/XH0Fp1uS8HHGmzXkSdTmokcJHn02DnQa1C0WMdjsFf EbPNhYAcU6eN/vg1TU7BDUVofjKsz0B9smA5r9Vgh/vvVV0XoVHUyt6bYtBf2+lMpzjJ HBF17zJqfZrlUKdnuDK3c7cTfleZIkBNy5qQw= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:in-reply-to:references; bh=v1AJaOwtYZcru/0NBCag/GtcygGS4K8MThIYi2P57G0=; b=KS6qKe8oqX2P13Yl1huwRuhO/qH07k2e0o5Z9hwoHjWuDBgvK3caPAxI6G0oSBzws8 5WwvurS/nheFMl6u116FN4te6coxoreFtAdwl3p1HRWFpHB5z9g3p699sezL6mtlE0XI fLYEALWMvoiXJZHAshnX0fEXb2uFFchwEY1j9uKBn2vqH3z9W9cCekFQQHe/aY6RH9Uo vgt13EFLEKgY5zdRydiao6oPhMZr53yvUGIRTzeChcf6oPA3uB0/AjBXhQKaCcOyzo5E RS+W58N4kmQbzsb1XbSpDLC4UCK9vi86Hx5Z+/lUi2ppkq2wmt+7vt1uOQAfGqn6lRci sTpg== X-Gm-Message-State: ALyK8tLxxxhRup6eKTcGxv2oA2z8DJ1uBGwZLVlCp2Er8jtUy9t1vsbZQ4yRLMYRU/v985ls X-Received: by 10.98.193.5 with SMTP id i5mr31108252pfg.64.1465295125171; Tue, 07 Jun 2016 03:25:25 -0700 (PDT) Received: from localhost ([122.167.17.193]) by smtp.gmail.com with ESMTPSA id m68sm34167924pfb.27.2016.06.07.03.25.23 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 07 Jun 2016 03:25:24 -0700 (PDT) From: Viresh Kumar To: Rafael Wysocki , Viresh Kumar Cc: linaro-kernel@lists.linaro.org, linux-pm@vger.kernel.org, linux-kernel@vger.kernel.org, steve.muckle@linaro.org Subject: [PATCH V4 1/2] cpufreq: Handle sorted frequency tables more efficiently Date: Tue, 7 Jun 2016 15:55:14 +0530 Message-Id: X-Mailer: git-send-email 2.7.1.410.g6faf27b In-Reply-To: References: In-Reply-To: References: Sender: linux-pm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-pm@vger.kernel.org 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 --- drivers/cpufreq/freq_table.c | 67 +++++++++- include/linux/cpufreq.h | 284 ++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 343 insertions(+), 8 deletions(-) -- 2.7.1.410.g6faf27b -- To unsubscribe from this list: send the line "unsubscribe linux-pm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html 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) {