pm: EDP: add fair governor
Sivaram Nair [Mon, 17 Sep 2012 12:04:40 +0000 (15:04 +0300)]
This patch adds the fair governor to EDP framework. This governor
allocates the available current budget proportional to the E0 state
level of clients.

Change-Id: I6bfac59e3c64ffe0917171af9246d0b287f5da66
Signed-off-by: Sivaram Nair <sivaramn@nvidia.com>
Reviewed-on: http://git-master/r/140844
Reviewed-by: Automatic_Commit_Validation_User
GVS: Gerrit_Virtual_Submit
Reviewed-by: Diwakar Tundlam <dtundlam@nvidia.com>

Rebase-Id: R199b1d61b5aee77dbb53792d0035d844dee3734a

Documentation/edp/governors
drivers/edp/Makefile
drivers/edp/edp_fair.c [new file with mode: 0644]

index 95eda92..ea00be2 100644 (file)
@@ -39,8 +39,13 @@ minimum guarantee E-state.
 
 3. Overage
 
-Overage governor uses a propotional allocation based on the difference
+Overage governor uses a proportional allocation based on the difference
 between the current E-state level and E0 (named the 'overage'). This
 causes all clients to increase or decrease in their E-state some what
 simultaneously. Hence this is fare allocation policy and ensures that no
 client is throttled too much.
+
+4. Fair
+
+Fair governor policy is similar to overage policy, but the proportion is
+based on E0-state level of clients.
index 7d2ddc2..5b26adc 100644 (file)
@@ -1,4 +1,7 @@
+GCOV_PROFILE := y
+
 obj-$(CONFIG_EDP_FRAMEWORK)    += edp.o
 obj-$(CONFIG_EDP_FRAMEWORK)    += edp_priority.o
 obj-$(CONFIG_EDP_FRAMEWORK)    += sysfs.o
 obj-$(CONFIG_EDP_FRAMEWORK)    += edp_overage.o
+obj-$(CONFIG_EDP_FRAMEWORK)    += edp_fair.o
diff --git a/drivers/edp/edp_fair.c b/drivers/edp/edp_fair.c
new file mode 100644 (file)
index 0000000..830876f
--- /dev/null
@@ -0,0 +1,243 @@
+/*
+ * Copyright (c) 2012, NVIDIA CORPORATION.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/edp.h>
+#include "edp_internal.h"
+
+static unsigned int approvable_req(struct edp_client *c, unsigned int net)
+{
+       unsigned int fair_level;
+       unsigned int step;
+       unsigned int cl;
+
+       if (req_index(c) >= c->e0_index)
+               return req_index(c);
+
+       cl = cur_level(c);
+       fair_level = c->manager->imax * e0_level(c) / net;
+       step = max(fair_level, cl + c->manager->remaining) - cl;
+       return edp_promotion_point(c, step);
+}
+
+static unsigned int net_e0(struct edp_client *client)
+{
+       struct edp_client *c;
+       unsigned int net = 0;
+
+       list_for_each_entry(c, &client->manager->clients, link)
+               net += e0_level(c);
+
+       return net;
+}
+
+static struct edp_client *throttle_pledge(struct edp_client *client,
+               unsigned int required, unsigned int net,
+               unsigned int *pledged)
+{
+       struct edp_manager *m = client->manager;
+       unsigned int deficit = required - m->remaining;
+       struct edp_client *c;
+       unsigned int step;
+
+       *pledged = m->remaining;
+
+       list_for_each_entry_reverse(c, &m->clients, link) {
+               if (c == client || cur_level(c) <= e0_level(c))
+                       continue;
+
+               step = (deficit * e0_level(c) + net - 1) / net;
+               c->gwt = edp_throttling_point(c, step ?: 1);
+               *pledged += cur_level(c) - c->states[c->gwt];
+               if (*pledged >= required)
+                       break;
+       }
+
+       WARN_ON(*pledged < required);
+       return c;
+}
+
+static void throttle_recover(struct edp_client *client, struct edp_client *tp,
+               unsigned int required)
+{
+       struct edp_manager *m = client->manager;
+       unsigned int recovered = m->remaining;
+
+       list_for_each_entry_from(tp, &m->clients, link) {
+               if (tp == client || cur_level(tp) <= e0_level(tp) ||
+                               tp->gwt == cur_index(tp))
+                       continue;
+
+               WARN_ON(!tp->throttle);
+               tp->throttle(tp->gwt);
+               recovered += cur_level(tp) - tp->states[tp->gwt];
+               if (tp->cur == tp->req)
+                       m->num_denied++;
+
+               tp->cur = tp->states + tp->gwt;
+               if (recovered >= required)
+                       return;
+       }
+}
+
+static void throttle(struct edp_client *client)
+{
+       struct edp_manager *m = client->manager;
+       struct edp_client *tp;
+       unsigned int ar;
+       unsigned int pledged;
+       unsigned int required;
+       unsigned int net;
+
+       net = net_e0(client);
+       if (!net) {
+               WARN_ON(1);
+               return;
+       }
+
+       ar = approvable_req(client, net);
+       required = client->states[ar] - cur_level(client);
+
+       if (required <= m->remaining) {
+               client->cur = client->states + ar;
+               m->remaining -= required;
+               return;
+       }
+
+       tp = throttle_pledge(client, required, net, &pledged);
+
+       /* E-states are discrete - we may get more than we asked for */
+       if (pledged > required && ar != req_index(client)) {
+               ar = edp_promotion_point(client, pledged);
+               required = client->states[ar] - cur_level(client);
+       }
+
+       throttle_recover(client, tp, required);
+       client->cur = client->states + ar;
+       m->remaining = pledged - required;
+}
+
+static void fair_update_request(struct edp_client *client,
+               const unsigned int *req)
+{
+       edp_default_update_request(client, req, throttle);
+}
+
+static unsigned int fair_promotion_point(struct edp_client *c,
+               unsigned int step, unsigned int max)
+{
+       unsigned int lim = cur_level(c) + step;
+       unsigned int ci = cur_index(c);
+       unsigned int i = req_index(c);
+
+       while (i < ci && c->states[i] > lim)
+               i++;
+
+       /*
+        * While being throttled, we probably contributed more than our
+        * fare share - so take the ceiling E-state here
+        */
+       if (c->states[i] < lim && i > req_index(c)) {
+               if (c->states[i - 1] <= cur_level(c) + max)
+                       i--;
+       }
+
+       return i;
+}
+
+static unsigned int promotion_pledge(struct edp_manager *m, unsigned int net)
+{
+       unsigned int budget = m->remaining;
+       unsigned int unpledged = m->remaining;
+       unsigned int denied = m->num_denied;
+       struct edp_client *c;
+       unsigned int step;
+
+       list_for_each_entry(c, &m->clients, link) {
+               if (req_level(c) <= cur_level(c) || !c->notify_promotion)
+                       continue;
+
+               step = (e0_level(c) * budget + net - 1) / net;
+               step = min(step, unpledged);
+
+               c->gwt = fair_promotion_point(c, step, unpledged);
+               unpledged -= c->states[c->gwt] - cur_level(c);
+               if (req_index(c) == c->gwt)
+                       denied--;
+               if (!unpledged || !denied)
+                       break;
+       }
+
+       return unpledged;
+}
+
+static void fair_promote(struct edp_manager *mgr)
+{
+       unsigned int net = 0;
+       struct edp_client *c;
+       unsigned int step;
+       unsigned int pp;
+       unsigned int unpledged;
+
+       list_for_each_entry(c, &mgr->clients, link) {
+               if (req_level(c) > cur_level(c) && c->notify_promotion) {
+                       net += e0_level(c);
+                       c->gwt = cur_index(c);
+               }
+       }
+
+       /* if the net is 0, fall back on priority */
+       unpledged = net ? promotion_pledge(mgr, net) : mgr->remaining;
+
+       list_for_each_entry(c, &mgr->clients, link) {
+               if (req_level(c) <= cur_level(c) || !c->notify_promotion ||
+                               c->gwt == cur_index(c))
+                       continue;
+
+               pp = c->gwt;
+
+               /* make sure that the unpledged current is not  wasted */
+               if (unpledged && req_index(c) != pp) {
+                       step = c->states[pp] - cur_level(c) + unpledged;
+                       pp = edp_promotion_point(c, step);
+                       unpledged -= c->states[pp] - c->states[c->gwt];
+               }
+
+               mgr->remaining -= c->states[pp] - cur_level(c);
+               c->cur = c->states + pp;
+               if (c->cur == c->req)
+                       mgr->num_denied--;
+
+               c->notify_promotion(pp);
+               if (!mgr->remaining || !mgr->num_denied)
+                       return;
+       }
+}
+
+static struct edp_governor fair_governor = {
+       .name = "fair",
+       .owner = THIS_MODULE,
+       .update_request = fair_update_request,
+       .update_loans = edp_default_update_loans,
+       .promote = fair_promote
+};
+
+static int __init fair_init(void)
+{
+       return edp_register_governor(&fair_governor);
+}
+postcore_initcall(fair_init);