pm: EDP: add fair governor

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

2 files changed, 246 insertions, 0 deletions

diff --git a/drivers/edp/Makefile b/drivers/edp/Makefile
index 7d2ddc2fe4a0..5b26adc3b584 100644
--- a/drivers/edp/Makefile
+++ b/drivers/edp/Makefile
@@ -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
index 000000000000..830876f396dc
--- /dev/null
+++ b/drivers/edp/edp_fair.c
@@ -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);