| /* |
| * Copyright (c) 2012-2013, 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 struct list_head hilist; |
| static struct list_head lolist_hash[10]; |
| |
| static void init_hash(void) |
| { |
| int i; |
| INIT_LIST_HEAD(&hilist); |
| for (i = 0; i < ARRAY_SIZE(lolist_hash); i++) |
| INIT_LIST_HEAD(lolist_hash + i); |
| } |
| |
| /* Return the minimum state that we must approve */ |
| static unsigned int min_ai(struct edp_client *c) |
| { |
| unsigned int ri = req_index(c); |
| if (ri >= c->e0_index) |
| return ri; |
| return min(cur_index(c), c->e0_index); |
| } |
| |
| static struct edp_client *lolist_hi_entry(int hash) |
| { |
| int i; |
| |
| for (i = hash; i < ARRAY_SIZE(lolist_hash); i++) { |
| if (!list_empty(lolist_hash + i)) |
| return list_first_entry(lolist_hash + i, |
| struct edp_client, glnk); |
| } |
| |
| return NULL; |
| } |
| |
| static struct edp_client *lolist_li_entry(int hash) |
| { |
| int i; |
| |
| for (i = hash; i >= 0; i--) { |
| if (!list_empty(lolist_hash + i)) |
| return list_first_entry(lolist_hash + i, |
| struct edp_client, glnk); |
| } |
| |
| return NULL; |
| } |
| |
| static struct edp_client *lolist_entry(int hash, bool hifirst) |
| { |
| struct edp_client *c; |
| |
| if (hifirst) |
| c = lolist_hi_entry(hash) ?: lolist_li_entry(hash - 1); |
| else |
| c = lolist_li_entry(hash) ?: lolist_hi_entry(hash + 1); |
| |
| return c; |
| } |
| |
| /* |
| * Use hashing to fasten up the lookup for bestfit (we might have to do |
| * multiple passes). If a single client can supply the minimum |
| * requirement, put them into hilist. Otherwise, compute a simple hash |
| * from the ratio of (cur - E0) to the minimum requirement and add to |
| * the corresponding lolist queue. Entries are added to the list head |
| * so that lower priority clients are throttled first. |
| */ |
| static void prep_throttle_hash(struct edp_client *client, unsigned int mn) |
| { |
| struct edp_manager *m = client->manager; |
| struct edp_client *c; |
| unsigned int i; |
| unsigned int more; |
| |
| init_hash(); |
| |
| list_for_each_entry(c, &m->clients, link) { |
| if (c == client || cur_level(c) <= e0_level(c)) |
| continue; |
| |
| more = cur_level(c) - e0_level(c); |
| |
| if (more + m->remaining < mn) { |
| i = more * ARRAY_SIZE(lolist_hash) / mn; |
| list_add(&c->glnk, lolist_hash + i); |
| } else { |
| list_add(&c->glnk, &hilist); |
| } |
| } |
| } |
| |
| /* |
| * Find the bestfit point between the requesting client and a potential |
| * throttle-victim. Choose the one with lowest remaining current. |
| */ |
| static unsigned int bestfit_point(struct edp_client *rc, struct edp_client *c, |
| unsigned int mn, unsigned int *opt_bal) |
| { |
| unsigned int ai = cur_index(rc); |
| unsigned int ri = req_index(rc); |
| unsigned int cl = cur_level(rc); |
| unsigned int step; |
| unsigned int bal; |
| unsigned int i; |
| unsigned int j; |
| |
| *opt_bal = rc->manager->max; |
| |
| for (i = cur_index(c) + 1; i <= c->e0_index && ai > ri; i++) { |
| step = rc->manager->remaining + *c->cur - c->states[i]; |
| if (step < mn) |
| continue; |
| |
| j = edp_promotion_point(rc, step); |
| bal = step - (rc->states[j] - cl); |
| if (bal < *opt_bal) { |
| *opt_bal = bal; |
| c->gwt = i; |
| ai = j; |
| } |
| } |
| |
| return ai; |
| } |
| |
| static struct edp_client *throttle_bestfit_hi(struct edp_client *rc, |
| unsigned int mn, unsigned int *bfi, unsigned int *opt_bal) |
| { |
| struct edp_client *c; |
| struct edp_client *opt_c; |
| unsigned int bal; |
| unsigned int i; |
| |
| if (list_empty(&hilist)) |
| return NULL; |
| |
| opt_c = NULL; |
| *opt_bal = rc->manager->max; |
| |
| list_for_each_entry(c, &hilist, glnk) { |
| i = bestfit_point(rc, c, mn, &bal); |
| if (bal < *opt_bal) { |
| *bfi = i; |
| *opt_bal = bal; |
| opt_c = c; |
| } |
| } |
| |
| WARN_ON(!opt_c); |
| return opt_c; |
| } |
| |
| static unsigned int throttle_recover(struct edp_manager *m, unsigned int mn) |
| { |
| struct edp_client *c; |
| unsigned int i; |
| unsigned int tp; |
| unsigned int step; |
| unsigned int rsum = m->remaining; |
| |
| while (rsum < mn) { |
| i = ((mn - rsum) * ARRAY_SIZE(lolist_hash) + mn - 1) / mn; |
| c = lolist_entry(i, true); |
| if (!c) |
| break; |
| |
| list_del(&c->glnk); |
| step = min(cur_level(c) - e0_level(c), mn - rsum); |
| tp = edp_throttling_point(c, step); |
| if (tp == cur_index(c)) |
| continue; |
| |
| rsum += cur_level(c) - c->states[tp]; |
| c->throttle(tp, c->private_data); |
| if (c->cur == c->req) |
| m->num_denied++; |
| c->cur = c->states + tp; |
| } |
| |
| WARN_ON(rsum < mn); |
| return rsum; |
| } |
| |
| static void throttle(struct edp_client *client) |
| { |
| struct edp_manager *m = client->manager; |
| unsigned int ai; |
| unsigned int mn; |
| struct edp_client *c; |
| unsigned int balance; |
| |
| ai = min_ai(client); |
| mn = client->states[ai] - cur_level(client); |
| |
| if (mn <= m->remaining) { |
| ai = edp_promotion_point(client, m->remaining); |
| m->remaining -= client->states[ai] - cur_level(client); |
| client->cur = client->states + ai; |
| return; |
| } |
| |
| prep_throttle_hash(client, mn); |
| c = throttle_bestfit_hi(client, mn, &ai, &balance); |
| |
| if (c) { |
| c->throttle(c->gwt, c->private_data); |
| if (c->cur == c->req) |
| m->num_denied++; |
| m->remaining = balance; |
| c->cur = c->states + c->gwt; |
| client->cur = client->states + ai; |
| return; |
| } |
| |
| balance = throttle_recover(m, mn); |
| WARN_ON(balance < mn); |
| ai = edp_promotion_point(client, balance); |
| m->remaining = balance - (client->states[ai] - cur_level(client)); |
| client->cur = client->states + ai; |
| } |
| |
| static void bestfit_update_request(struct edp_client *client, |
| const unsigned int *req) |
| { |
| edp_default_update_request(client, req, throttle); |
| } |
| |
| static void prep_promotion_hash(struct edp_manager *m) |
| { |
| unsigned int balance = m->remaining; |
| struct edp_client *c; |
| unsigned int step; |
| unsigned int i; |
| |
| init_hash(); |
| |
| list_for_each_entry(c, &m->clients, link) { |
| if (req_level(c) <= cur_level(c) || !c->notify_promotion) |
| continue; |
| |
| step = req_level(c) - cur_level(c); |
| |
| /* |
| * Add to the list tail so that higher priority clients |
| * are promoted first |
| */ |
| if (step < balance) { |
| i = step * ARRAY_SIZE(lolist_hash) / balance; |
| list_add_tail(&c->glnk, lolist_hash + i); |
| } else { |
| list_add_tail(&c->glnk, &hilist); |
| } |
| } |
| } |
| |
| static struct edp_client *promotion_bestfit_hi(unsigned int balance) |
| { |
| struct edp_client *c; |
| unsigned int i; |
| unsigned int step; |
| struct edp_client *opt_c = NULL; |
| unsigned int opt_bal = balance; |
| |
| list_for_each_entry(c, &hilist, glnk) { |
| i = edp_promotion_point(c, balance); |
| step = c->states[i] - cur_level(c); |
| if (balance - step < opt_bal) { |
| c->gwt = i; |
| opt_c = c; |
| } |
| } |
| |
| return opt_c; |
| } |
| |
| static void bestfit_promote(struct edp_manager *mgr) |
| { |
| unsigned int balance = mgr->remaining; |
| struct edp_client *c; |
| unsigned int i; |
| |
| prep_promotion_hash(mgr); |
| c = promotion_bestfit_hi(balance); |
| |
| if (c) { |
| balance -= c->states[c->gwt] - cur_level(c); |
| c->cur = c->states + c->gwt; |
| if (c->cur == c->req) |
| mgr->num_denied--; |
| c->notify_promotion(c->gwt, c->private_data); |
| } |
| |
| while (balance && mgr->num_denied) { |
| i = balance * ARRAY_SIZE(lolist_hash) / mgr->remaining; |
| if (i) |
| i--; |
| c = lolist_entry(i, false); |
| if (!c) |
| break; |
| |
| list_del(&c->glnk); |
| c->gwt = edp_promotion_point(c, balance); |
| if (c->gwt == cur_index(c)) |
| continue; |
| |
| balance -= c->states[c->gwt] - cur_level(c); |
| c->cur = c->states + c->gwt; |
| if (c->cur == c->req) |
| mgr->num_denied--; |
| c->notify_promotion(c->gwt, c->private_data); |
| } |
| |
| mgr->remaining = balance; |
| } |
| |
| static struct edp_governor bestfit_governor = { |
| .name = "bestfit", |
| .owner = THIS_MODULE, |
| .update_request = bestfit_update_request, |
| .update_loans = edp_default_update_loans, |
| .promote = bestfit_promote |
| }; |
| |
| static int __init bestfit_init(void) |
| { |
| return edp_register_governor(&bestfit_governor); |
| } |
| postcore_initcall(bestfit_init); |