pm: EDP: adding temporal governors

Following time based governors are added.
	(1) LRR - least recently requested
	(2) MRR - most recently requested
	(3) RR - round robin

Change-Id: I4432a10f724c772f60ccb89914cd6d14c1114681
Signed-off-by: Sivaram Nair <sivaramn@nvidia.com>
Reviewed-on: http://git-master/r/140846
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Juha Tukkinen <jtukkinen@nvidia.com>

5 files changed, 253 insertions, 0 deletions

diff --git a/Documentation/edp/governors b/Documentation/edp/governors
index 005e7a537ded..5dc7b7107d35 100644
--- a/Documentation/edp/governors
+++ b/Documentation/edp/governors
@@ -60,3 +60,17 @@ be approved (subject to the general EDP rules).
 Since the perfect solution would involve several passes across all
 clients, a trade-off is made to approximate the optimum so that the
 algorithm complexity remains linear.
+
+6. Least Recently Requested (LRR)
+
+An arrival-queue based policy where the least recently requested client
+is throttled first.
+
+7. Most Recently Requested (MRR)
+
+Another arrival-queue based policy where the most recently requested
+client is throttled first.
+
+8. Round Robin (RR)
+
+In this policy, clients are throttled in a round-robin fashion.
diff --git a/drivers/edp/Makefile b/drivers/edp/Makefile
index cf41d737b07f..224a90641583 100644
--- a/drivers/edp/Makefile
+++ b/drivers/edp/Makefile
@@ -6,3 +6,4 @@ obj-$(CONFIG_EDP_FRAMEWORK)	+= sysfs.o
 obj-$(CONFIG_EDP_FRAMEWORK)	+= edp_overage.o
 obj-$(CONFIG_EDP_FRAMEWORK)	+= edp_fair.o
 obj-$(CONFIG_EDP_FRAMEWORK)	+= edp_bestfit.o
+obj-$(CONFIG_EDP_FRAMEWORK)	+= edp_temporal.o
diff --git a/drivers/edp/edp.c b/drivers/edp/edp.c
index 4010c7857954..b82375be6fcd 100644
--- a/drivers/edp/edp.c
+++ b/drivers/edp/edp.c
@@ -65,6 +65,7 @@ int edp_register_manager(struct edp_manager *mgr)
 		mgr->registered = true;
 		mgr->remaining = mgr->imax;
 		mgr->gov = NULL;
+		mgr->gov_data = NULL;
 		INIT_LIST_HEAD(&mgr->clients);
 		INIT_WORK(&mgr->work, promote);
 		mgr->kobj = NULL;
diff --git a/drivers/edp/edp_temporal.c b/drivers/edp/edp_temporal.c
new file mode 100644
index 000000000000..89fc0739367c
--- /dev/null
+++ b/drivers/edp/edp_temporal.c
@@ -0,0 +1,234 @@
+/*
+ * 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 <linux/slab.h>
+#include "edp_internal.h"
+
+/*
+ * This file implements the (1) LRR: least recently requested (2) MRR:
+ * most recently requested and (3) RR: round robin governors.
+ *
+ * Since they are all based on some timestamps, we use a simple list
+ * (the 'temporal list') for ordering the clients according to the main
+ * selection criteria. This list is maintained in such a way that
+ * throttle-victims appear at the tail and promotions are done from the
+ * head.
+ */
+
+static void throttle(struct edp_client *client);
+
+/*  Temporal list is manager specific */
+static int temporal_start(struct edp_manager *m)
+{
+	struct list_head *head;
+	struct edp_client *c;
+
+	head = kzalloc(sizeof(*head), GFP_KERNEL);
+	if (!head)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD(head);
+	m->gov_data = head;
+
+	list_for_each_entry(c, &m->clients, link) {
+		if (req_index(c) < c->e0_index)
+			list_add(&c->glnk, head);
+	}
+
+	return 0;
+}
+
+static void temporal_stop(struct edp_manager *m)
+{
+	kfree(m->gov_data);
+	m->gov_data = NULL;
+}
+
+/*
+ * We need to remember only those clients that can either be throttled
+ * or promoted - this way, we have a smaller list.
+ */
+static void lrr_update_request(struct edp_client *client,
+		const unsigned int *req)
+{
+	struct list_head *head;
+
+	if (req_index(client) < client->e0_index)
+		list_del(&client->glnk);
+
+	edp_default_update_request(client, req, throttle);
+
+	if (req_index(client) < client->e0_index) {
+		head = client->manager->gov_data;
+		list_add(&client->glnk, head);
+	}
+}
+
+/*
+ * We need to remember only those clients that can either be throttled
+ * or promoted - this way, we have a smaller list.
+ */
+static void mrr_update_request(struct edp_client *client,
+		const unsigned int *req)
+{
+	struct list_head *head;
+
+	if (req_index(client) < client->e0_index)
+		list_del(&client->glnk);
+
+	edp_default_update_request(client, req, throttle);
+
+	if (req_index(client) < client->e0_index) {
+		head = client->manager->gov_data;
+		list_add_tail(&client->glnk, head);
+	}
+}
+
+static void rr_update_request(struct edp_client *client,
+		const unsigned int *req)
+{
+	struct list_head *head;
+
+	/* new entry */
+	if (!client->req) {
+		head = client->manager->gov_data;
+		list_add(&client->glnk, head);
+	}
+
+	edp_default_update_request(client, req, throttle);
+}
+
+static void temporal_promote(struct edp_manager *m)
+{
+	struct list_head *head = m->gov_data;
+	struct edp_client *c;
+	unsigned int i;
+
+	list_for_each_entry(c, head, glnk) {
+		if (req_level(c) <= cur_level(c) || !c->notify_promotion)
+			continue;
+
+		i = edp_promotion_point(c, m->remaining);
+		if (i == cur_index(c))
+			continue;
+
+		m->remaining -= c->states[i] - cur_level(c);
+		c->cur = c->states + i;
+		if (c->cur == c->req)
+			m->num_denied--;
+
+		c->notify_promotion(i);
+		if (!m->remaining || !m->num_denied)
+			return;
+	}
+}
+
+#define DEFINE_TEMPORAL_GOV(_gov, _name, _func)	\
+	struct edp_governor _gov = {	\
+		.name = _name,	\
+		.owner = THIS_MODULE,	\
+		.start = temporal_start,	\
+		.stop = temporal_stop,	\
+		.update_request = _func,	\
+		.update_loans = edp_default_update_loans,	\
+		.promote = temporal_promote	\
+	};
+
+static DEFINE_TEMPORAL_GOV(lrr_governor, "least_recent", lrr_update_request);
+static DEFINE_TEMPORAL_GOV(mrr_governor, "most_recent", mrr_update_request);
+static DEFINE_TEMPORAL_GOV(rr_governor, "round_robin", rr_update_request);
+
+static void throttle(struct edp_client *client)
+{
+	struct edp_manager *m = client->manager;
+	unsigned int required = req_level(client) - cur_level(client);
+	struct list_head *head = m->gov_data;
+	struct edp_client *n;
+	struct edp_client *c;
+	unsigned int bal;
+
+	bal = m->remaining;
+	n = NULL;
+
+	list_for_each_entry_reverse(c, head, glnk) {
+		if (cur_level(c) > e0_level(c) && c != client) {
+			c->gwt = edp_throttling_point(c, required - bal);
+			bal += cur_level(c) - c->states[c->gwt];
+			n = c;
+			if (bal >= required)
+				break;
+		}
+	}
+
+	c = n;
+	bal = m->remaining;
+	if (!c)
+		goto finish;
+
+	/* use the safe version as we might be re-arraging the list */
+	list_for_each_entry_safe_from(c, n, head, glnk) {
+		if (cur_level(c) <= e0_level(c) || c == client ||
+				c->gwt == cur_index(c))
+			continue;
+
+		c->throttle(c->gwt);
+		bal += cur_level(c) - c->states[c->gwt];
+		if (c->cur == c->req)
+			m->num_denied++;
+		c->cur = c->states + c->gwt;
+
+		/* for RR, move this client to the head */
+		if (m->gov == &rr_governor)
+			list_move(&c->glnk, head);
+		if (bal >= required)
+			break;
+	}
+
+finish:
+	m->remaining = bal + cur_level(client);
+	client->cur = client->states + edp_promotion_point(client, bal);
+	m->remaining -= cur_level(client);
+}
+
+static int __init temporal_init(void)
+{
+	int ret = 0;
+	int r;
+
+	r = edp_register_governor(&lrr_governor);
+	if (r) {
+		pr_err("least_recent governor registration failed: %d\n", r);
+		ret = r;
+	}
+
+	r = edp_register_governor(&mrr_governor);
+	if (r) {
+		pr_err("most_recent governor registration failed: %d\n", r);
+		ret = r;
+	}
+
+	r = edp_register_governor(&rr_governor);
+	if (r) {
+		pr_err("round_robin governor registration failed: %d\n", r);
+		ret = r;
+	}
+
+	return ret;
+}
+postcore_initcall(temporal_init);
diff --git a/include/linux/edp.h b/include/linux/edp.h
index f792fd014c76..e5982f8c5a08 100644
--- a/include/linux/edp.h
+++ b/include/linux/edp.h
@@ -38,6 +38,9 @@ struct edp_manager {
 	struct work_struct work;
 	unsigned int num_denied;
 	struct kobject *kobj;
+
+	/* governor internal */
+	void *gov_data;
 };
 
 /*