Revert "ARM: tegra: tegratab: dummy change"
[linux-2.6.git] / drivers / edp / edp_bestfit.c
1 /*
2  * Copyright (c) 2012-2013, NVIDIA CORPORATION.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or modify it
5  * under the terms and conditions of the GNU General Public License,
6  * version 2, as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope it will be useful, but WITHOUT
9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
11  * more details.
12  *
13  * You should have received a copy of the GNU General Public License
14  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
15  */
16
17 #include <linux/kernel.h>
18 #include <linux/module.h>
19 #include <linux/edp.h>
20 #include "edp_internal.h"
21
22 static struct list_head hilist;
23 static struct list_head lolist_hash[10];
24
25 static void init_hash(void)
26 {
27         int i;
28         INIT_LIST_HEAD(&hilist);
29         for (i = 0; i < ARRAY_SIZE(lolist_hash); i++)
30                 INIT_LIST_HEAD(lolist_hash + i);
31 }
32
33 /* Return the minimum state that we must approve */
34 static unsigned int min_ai(struct edp_client *c)
35 {
36         unsigned int ri = req_index(c);
37         if (ri >= c->e0_index)
38                 return ri;
39         return min(cur_index(c), c->e0_index);
40 }
41
42 static struct edp_client *lolist_hi_entry(int hash)
43 {
44         int i;
45
46         for (i = hash; i < ARRAY_SIZE(lolist_hash); i++) {
47                 if (!list_empty(lolist_hash + i))
48                         return list_first_entry(lolist_hash + i,
49                                         struct edp_client, glnk);
50         }
51
52         return NULL;
53 }
54
55 static struct edp_client *lolist_li_entry(int hash)
56 {
57         int i;
58
59         for (i = hash; i >= 0; i--) {
60                 if (!list_empty(lolist_hash + i))
61                         return list_first_entry(lolist_hash + i,
62                                         struct edp_client, glnk);
63         }
64
65         return NULL;
66 }
67
68 static struct edp_client *lolist_entry(int hash, bool hifirst)
69 {
70         struct edp_client *c;
71
72         if (hifirst)
73                 c = lolist_hi_entry(hash) ?: lolist_li_entry(hash - 1);
74         else
75                 c = lolist_li_entry(hash) ?: lolist_hi_entry(hash + 1);
76
77         return c;
78 }
79
80 /*
81  * Use hashing to fasten up the lookup for bestfit (we might have to do
82  * multiple passes). If a single client can supply the minimum
83  * requirement, put them into hilist. Otherwise, compute a simple hash
84  * from the ratio of (cur - E0) to the minimum requirement and add to
85  * the corresponding lolist queue. Entries are added to the list head
86  * so that lower priority clients are throttled first.
87  */
88 static void prep_throttle_hash(struct edp_client *client, unsigned int mn)
89 {
90         struct edp_manager *m = client->manager;
91         struct edp_client *c;
92         unsigned int i;
93         unsigned int more;
94
95         init_hash();
96
97         list_for_each_entry(c, &m->clients, link) {
98                 if (c == client || cur_level(c) <= e0_level(c))
99                         continue;
100
101                 more = cur_level(c) - e0_level(c);
102
103                 if (more + m->remaining < mn) {
104                         i = more * ARRAY_SIZE(lolist_hash) / mn;
105                         list_add(&c->glnk, lolist_hash + i);
106                 } else {
107                         list_add(&c->glnk, &hilist);
108                 }
109         }
110 }
111
112 /*
113  * Find the bestfit point between the requesting client and a potential
114  * throttle-victim. Choose the one with lowest remaining current.
115  */
116 static unsigned int bestfit_point(struct edp_client *rc, struct edp_client *c,
117                 unsigned int mn, unsigned int *opt_bal)
118 {
119         unsigned int ai = cur_index(rc);
120         unsigned int ri = req_index(rc);
121         unsigned int cl = cur_level(rc);
122         unsigned int step;
123         unsigned int bal;
124         unsigned int i;
125         unsigned int j;
126
127         *opt_bal = rc->manager->max;
128
129         for (i = cur_index(c) + 1; i <= c->e0_index && ai > ri; i++) {
130                 step = rc->manager->remaining + *c->cur - c->states[i];
131                 if (step < mn)
132                         continue;
133
134                 j = edp_promotion_point(rc, step);
135                 bal = step - (rc->states[j] - cl);
136                 if (bal < *opt_bal) {
137                         *opt_bal = bal;
138                         c->gwt = i;
139                         ai = j;
140                 }
141         }
142
143         return ai;
144 }
145
146 static struct edp_client *throttle_bestfit_hi(struct edp_client *rc,
147                 unsigned int mn, unsigned int *bfi, unsigned int *opt_bal)
148 {
149         struct edp_client *c;
150         struct edp_client *opt_c;
151         unsigned int bal;
152         unsigned int i;
153
154         if (list_empty(&hilist))
155                 return NULL;
156
157         opt_c = NULL;
158         *opt_bal = rc->manager->max;
159
160         list_for_each_entry(c, &hilist, glnk) {
161                 i = bestfit_point(rc, c, mn, &bal);
162                 if (bal < *opt_bal) {
163                         *bfi = i;
164                         *opt_bal = bal;
165                         opt_c = c;
166                 }
167         }
168
169         WARN_ON(!opt_c);
170         return opt_c;
171 }
172
173 static unsigned int throttle_recover(struct edp_manager *m, unsigned int mn)
174 {
175         struct edp_client *c;
176         unsigned int i;
177         unsigned int tp;
178         unsigned int step;
179         unsigned int rsum = m->remaining;
180
181         while (rsum < mn) {
182                 i = ((mn - rsum) * ARRAY_SIZE(lolist_hash) + mn - 1) / mn;
183                 c = lolist_entry(i, true);
184                 if (!c)
185                         break;
186
187                 list_del(&c->glnk);
188                 step = min(cur_level(c) - e0_level(c), mn - rsum);
189                 tp = edp_throttling_point(c, step);
190                 if (tp == cur_index(c))
191                         continue;
192
193                 rsum += cur_level(c) - c->states[tp];
194                 c->throttle(tp, c->private_data);
195                 if (c->cur == c->req)
196                         m->num_denied++;
197                 c->cur = c->states + tp;
198         }
199
200         WARN_ON(rsum < mn);
201         return rsum;
202 }
203
204 static void throttle(struct edp_client *client)
205 {
206         struct edp_manager *m = client->manager;
207         unsigned int ai;
208         unsigned int mn;
209         struct edp_client *c;
210         unsigned int balance;
211
212         ai = min_ai(client);
213         mn = client->states[ai] - cur_level(client);
214
215         if (mn <= m->remaining) {
216                 ai = edp_promotion_point(client, m->remaining);
217                 m->remaining -= client->states[ai] - cur_level(client);
218                 client->cur = client->states + ai;
219                 return;
220         }
221
222         prep_throttle_hash(client, mn);
223         c = throttle_bestfit_hi(client, mn, &ai, &balance);
224
225         if (c) {
226                 c->throttle(c->gwt, c->private_data);
227                 if (c->cur == c->req)
228                         m->num_denied++;
229                 m->remaining = balance;
230                 c->cur = c->states + c->gwt;
231                 client->cur = client->states + ai;
232                 return;
233         }
234
235         balance = throttle_recover(m, mn);
236         WARN_ON(balance < mn);
237         ai = edp_promotion_point(client, balance);
238         m->remaining = balance - (client->states[ai] - cur_level(client));
239         client->cur = client->states + ai;
240 }
241
242 static void bestfit_update_request(struct edp_client *client,
243                 const unsigned int *req)
244 {
245         edp_default_update_request(client, req, throttle);
246 }
247
248 static void prep_promotion_hash(struct edp_manager *m)
249 {
250         unsigned int balance = m->remaining;
251         struct edp_client *c;
252         unsigned int step;
253         unsigned int i;
254
255         init_hash();
256
257         list_for_each_entry(c, &m->clients, link) {
258                 if (req_level(c) <= cur_level(c) || !c->notify_promotion)
259                         continue;
260
261                 step = req_level(c) - cur_level(c);
262
263                 /*
264                  * Add to the list tail so that higher priority clients
265                  * are promoted first
266                  */
267                 if (step < balance) {
268                         i = step * ARRAY_SIZE(lolist_hash) / balance;
269                         list_add_tail(&c->glnk, lolist_hash + i);
270                 } else {
271                         list_add_tail(&c->glnk, &hilist);
272                 }
273         }
274 }
275
276 static struct edp_client *promotion_bestfit_hi(unsigned int balance)
277 {
278         struct edp_client *c;
279         unsigned int i;
280         unsigned int step;
281         struct edp_client *opt_c = NULL;
282         unsigned int opt_bal = balance;
283
284         list_for_each_entry(c, &hilist, glnk) {
285                 i = edp_promotion_point(c, balance);
286                 step = c->states[i] - cur_level(c);
287                 if (balance - step < opt_bal) {
288                         c->gwt = i;
289                         opt_c = c;
290                 }
291         }
292
293         return opt_c;
294 }
295
296 static void bestfit_promote(struct edp_manager *mgr)
297 {
298         unsigned int balance = mgr->remaining;
299         struct edp_client *c;
300         unsigned int i;
301
302         prep_promotion_hash(mgr);
303         c = promotion_bestfit_hi(balance);
304
305         if (c) {
306                 balance -= c->states[c->gwt] - cur_level(c);
307                 c->cur = c->states + c->gwt;
308                 if (c->cur == c->req)
309                         mgr->num_denied--;
310                 c->notify_promotion(c->gwt, c->private_data);
311         }
312
313         while (balance && mgr->num_denied) {
314                 i = balance * ARRAY_SIZE(lolist_hash) / mgr->remaining;
315                 if (i)
316                         i--;
317                 c = lolist_entry(i, false);
318                 if (!c)
319                         break;
320
321                 list_del(&c->glnk);
322                 c->gwt = edp_promotion_point(c, balance);
323                 if (c->gwt == cur_index(c))
324                         continue;
325
326                 balance -= c->states[c->gwt] - cur_level(c);
327                 c->cur = c->states + c->gwt;
328                 if (c->cur == c->req)
329                         mgr->num_denied--;
330                 c->notify_promotion(c->gwt, c->private_data);
331         }
332
333         mgr->remaining = balance;
334 }
335
336 static struct edp_governor bestfit_governor = {
337         .name = "bestfit",
338         .owner = THIS_MODULE,
339         .update_request = bestfit_update_request,
340         .update_loans = edp_default_update_loans,
341         .promote = bestfit_promote
342 };
343
344 static int __init bestfit_init(void)
345 {
346         return edp_register_governor(&bestfit_governor);
347 }
348 postcore_initcall(bestfit_init);