pm: EDP: adding temporal governors
Sivaram Nair [Fri, 28 Sep 2012 06:34:50 +0000 (09:34 +0300)]
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>

Rebase-Id: R9de163f0bb4ea376273c4093aaaf73269b4e121a

Documentation/edp/governors
drivers/edp/Makefile
drivers/edp/edp.c
drivers/edp/edp_temporal.c [new file with mode: 0644]
include/linux/edp.h

index 005e7a5..5dc7b71 100644 (file)
@@ -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.
index cf41d73..224a906 100644 (file)
@@ -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
index 4010c78..b82375b 100644 (file)
@@ -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 (file)
index 0000000..89fc073
--- /dev/null
@@ -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);
index f792fd0..e5982f8 100644 (file)
@@ -38,6 +38,9 @@ struct edp_manager {
        struct work_struct work;
        unsigned int num_denied;
        struct kobject *kobj;
+
+       /* governor internal */
+       void *gov_data;
 };
 
 /*