5be5d1579361826b77e0eada40393b9d0f9f3e2e
[dragonfly.git] / sys / kern / subr_rman.c
1 /*
2  * Copyright 1998 Massachusetts Institute of Technology
3  *
4  * Permission to use, copy, modify, and distribute this software and
5  * its documentation for any purpose and without fee is hereby
6  * granted, provided that both the above copyright notice and this
7  * permission notice appear in all copies, that both the above
8  * copyright notice and this permission notice appear in all
9  * supporting documentation, and that the name of M.I.T. not be used
10  * in advertising or publicity pertaining to distribution of the
11  * software without specific, written prior permission.  M.I.T. makes
12  * no representations about the suitability of this software for any
13  * purpose.  It is provided "as is" without express or implied
14  * warranty.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY M.I.T. ``AS IS''.  M.I.T. DISCLAIMS
17  * ALL EXPRESS OR IMPLIED WARRANTIES WITH REGARD TO THIS SOFTWARE,
18  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT
20  * SHALL M.I.T. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * $FreeBSD: src/sys/kern/subr_rman.c,v 1.10.2.1 2001/06/05 08:06:08 imp Exp $
30  * $DragonFly: src/sys/kern/subr_rman.c,v 1.13 2007/09/21 02:28:00 y0netan1 Exp $
31  */
32
33 /*
34  * The kernel resource manager.  This code is responsible for keeping track
35  * of hardware resources which are apportioned out to various drivers.
36  * It does not actually assign those resources, and it is not expected
37  * that end-device drivers will call into this code directly.  Rather,
38  * the code which implements the buses that those devices are attached to,
39  * and the code which manages CPU resources, will call this code, and the
40  * end-device drivers will make upcalls to that code to actually perform
41  * the allocation.
42  *
43  * There are two sorts of resources managed by this code.  The first is
44  * the more familiar array (RMAN_ARRAY) type; resources in this class
45  * consist of a sequence of individually-allocatable objects which have
46  * been numbered in some well-defined order.  Most of the resources
47  * are of this type, as it is the most familiar.  The second type is
48  * called a gauge (RMAN_GAUGE), and models fungible resources (i.e.,
49  * resources in which each instance is indistinguishable from every
50  * other instance).  The principal anticipated application of gauges
51  * is in the context of power consumption, where a bus may have a specific
52  * power budget which all attached devices share.  RMAN_GAUGE is not
53  * implemented yet.
54  *
55  * For array resources, we make one simplifying assumption: two clients
56  * sharing the same resource must use the same range of indices.  That
57  * is to say, sharing of overlapping-but-not-identical regions is not
58  * permitted.
59  */
60
61 #include <sys/param.h>
62 #include <sys/systm.h>
63 #include <sys/kernel.h>
64 #include <sys/lock.h>
65 #include <sys/malloc.h>
66 #include <sys/bus.h>            /* XXX debugging */
67 #include <sys/rman.h>
68 #include <sys/sysctl.h>
69
70 int     rman_debug = 0;
71 TUNABLE_INT("debug.rman_debug", &rman_debug);
72 SYSCTL_INT(_debug, OID_AUTO, rman_debug, CTLFLAG_RW,
73     &rman_debug, 0, "rman debug");
74
75 #define DPRINTF(params) if (rman_debug) kprintf params
76
77 static MALLOC_DEFINE(M_RMAN, "rman", "Resource manager");
78
79 struct  rman_head rman_head;
80 static  struct lwkt_token rman_tok; /* mutex to protect rman_head */
81 static  int int_rman_activate_resource(struct rman *rm, struct resource *r,
82                                        struct resource **whohas);
83 static  int int_rman_deactivate_resource(struct resource *r);
84 static  int int_rman_release_resource(struct rman *rm, struct resource *r);
85
86 #define CIRCLEQ_TERMCOND(var, head)     (var == (void *)&(head))
87
88 int
89 rman_init(struct rman *rm)
90 {
91         static int once;
92         lwkt_tokref ilock;
93
94         if (once == 0) {
95                 once = 1;
96                 TAILQ_INIT(&rman_head);
97                 lwkt_token_init(&rman_tok);
98         }
99
100         if (rm->rm_type == RMAN_UNINIT)
101                 panic("rman_init");
102         if (rm->rm_type == RMAN_GAUGE)
103                 panic("implement RMAN_GAUGE");
104
105         CIRCLEQ_INIT(&rm->rm_list);
106         rm->rm_slock = kmalloc(sizeof *rm->rm_slock, M_RMAN, M_NOWAIT);
107         if (rm->rm_slock == NULL)
108                 return ENOMEM;
109         lwkt_token_init(rm->rm_slock);
110
111         lwkt_gettoken(&ilock, &rman_tok);
112         TAILQ_INSERT_TAIL(&rman_head, rm, rm_link);
113         lwkt_reltoken(&ilock);
114         return 0;
115 }
116
117 /*
118  * NB: this interface is not robust against programming errors which
119  * add multiple copies of the same region.
120  */
121 int
122 rman_manage_region(struct rman *rm, u_long start, u_long end)
123 {
124         struct resource *r, *s;
125         lwkt_tokref ilock;
126
127         DPRINTF(("rman_manage_region: <%s> request: start %#lx, end %#lx\n",
128             rm->rm_descr, start, end));
129         r = kmalloc(sizeof *r, M_RMAN, M_NOWAIT);
130         if (r == 0)
131                 return ENOMEM;
132         bzero(r, sizeof *r);
133         r->r_sharehead = 0;
134         r->r_start = start;
135         r->r_end = end;
136         r->r_flags = 0;
137         r->r_dev = 0;
138         r->r_rm = rm;
139
140         lwkt_gettoken(&ilock, rm->rm_slock);
141         for (s = CIRCLEQ_FIRST(&rm->rm_list);   
142              !CIRCLEQ_TERMCOND(s, rm->rm_list) && s->r_end < r->r_start;
143              s = CIRCLEQ_NEXT(s, r_link))
144                 ;
145
146         if (CIRCLEQ_TERMCOND(s, rm->rm_list)) {
147                 CIRCLEQ_INSERT_TAIL(&rm->rm_list, r, r_link);
148         } else {
149                 CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, r, r_link);
150         }
151
152         lwkt_reltoken(&ilock);
153         return 0;
154 }
155
156 int
157 rman_fini(struct rman *rm)
158 {
159         struct resource *r;
160         lwkt_tokref ilock;
161
162         lwkt_gettoken(&ilock, rm->rm_slock);
163         CIRCLEQ_FOREACH(r, &rm->rm_list, r_link) {
164                 if (r->r_flags & RF_ALLOCATED) {
165                         lwkt_reltoken(&ilock);
166                         return EBUSY;
167                 }
168         }
169
170         /*
171          * There really should only be one of these if we are in this
172          * state and the code is working properly, but it can't hurt.
173          */
174         while (!CIRCLEQ_EMPTY(&rm->rm_list)) {
175                 r = CIRCLEQ_FIRST(&rm->rm_list);
176                 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
177                 kfree(r, M_RMAN);
178         }
179         lwkt_reltoken(&ilock);
180         /* XXX what's the point of this if we are going to free the struct? */
181         lwkt_gettoken(&ilock, &rman_tok);
182         TAILQ_REMOVE(&rman_head, rm, rm_link);
183         lwkt_reltoken(&ilock);
184         kfree(rm->rm_slock, M_RMAN);
185
186         return 0;
187 }
188
189 struct resource *
190 rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
191                       u_int flags, struct device *dev)
192 {
193         u_int   want_activate;
194         struct  resource *r, *s, *rv;
195         u_long  rstart, rend;
196         lwkt_tokref ilock;
197
198         rv = 0;
199
200         DPRINTF(("rman_reserve_resource: <%s> request: [%#lx, %#lx], length "
201                "%#lx, flags %u, device %s\n", rm->rm_descr, start, end,
202                count, flags,
203                dev == NULL ? "<null>" : device_get_nameunit(dev)));
204         want_activate = (flags & RF_ACTIVE);
205         flags &= ~RF_ACTIVE;
206
207         lwkt_gettoken(&ilock, rm->rm_slock);
208
209         for (r = CIRCLEQ_FIRST(&rm->rm_list); 
210              !CIRCLEQ_TERMCOND(r, rm->rm_list) && r->r_end < start;
211              r = CIRCLEQ_NEXT(r, r_link))
212                 ;
213
214         if (CIRCLEQ_TERMCOND(r, rm->rm_list)) {
215                 DPRINTF(("could not find a region\n"));
216                 goto out;
217         }
218
219         /*
220          * First try to find an acceptable totally-unshared region.
221          */
222         for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
223              s = CIRCLEQ_NEXT(s, r_link)) {
224                 DPRINTF(("considering [%#lx, %#lx]\n", s->r_start, s->r_end));
225                 if (s->r_start > end) {
226                         DPRINTF(("s->r_start (%#lx) > end (%#lx)\n",
227                             s->r_start, end));
228                         break;
229                 }
230                 if (s->r_flags & RF_ALLOCATED) {
231                         DPRINTF(("region is allocated\n"));
232                         continue;
233                 }
234                 rstart = max(s->r_start, start);
235                 rstart = (rstart + ((1ul << RF_ALIGNMENT(flags))) - 1) &
236                     ~((1ul << RF_ALIGNMENT(flags)) - 1);
237                 rend = min(s->r_end, max(start + count, end));
238                 DPRINTF(("truncated region: [%#lx, %#lx]; size %#lx (requested %#lx)\n",
239                        rstart, rend, (rend - rstart + 1), count));
240
241                 if ((rend - rstart + 1) >= count) {
242                         DPRINTF(("candidate region: [%#lx, %#lx], size %#lx\n",
243                                rstart, rend, (rend - rstart + 1)));
244                         if ((s->r_end - s->r_start + 1) == count) {
245                                 DPRINTF(("candidate region is entire chunk\n"));
246                                 rv = s;
247                                 rv->r_flags |= RF_ALLOCATED | flags;
248                                 rv->r_dev = dev;
249                                 goto out;
250                         }
251
252                         /*
253                          * If s->r_start < rstart and
254                          *    s->r_end > rstart + count - 1, then
255                          * we need to split the region into three pieces
256                          * (the middle one will get returned to the user).
257                          * Otherwise, we are allocating at either the
258                          * beginning or the end of s, so we only need to
259                          * split it in two.  The first case requires
260                          * two new allocations; the second requires but one.
261                          */
262                         rv = kmalloc(sizeof *rv, M_RMAN, M_NOWAIT);
263                         if (rv == 0)
264                                 goto out;
265                         bzero(rv, sizeof *rv);
266                         rv->r_start = rstart;
267                         rv->r_end = rstart + count - 1;
268                         rv->r_flags = flags | RF_ALLOCATED;
269                         rv->r_dev = dev;
270                         rv->r_sharehead = 0;
271                         rv->r_rm = rm;
272                         
273                         if (s->r_start < rv->r_start && s->r_end > rv->r_end) {
274                                 DPRINTF(("splitting region in three parts: "
275                                        "[%#lx, %#lx]; [%#lx, %#lx]; [%#lx, %#lx]\n",
276                                        s->r_start, rv->r_start - 1,
277                                        rv->r_start, rv->r_end,
278                                        rv->r_end + 1, s->r_end));
279                                 /*
280                                  * We are allocating in the middle.
281                                  */
282                                 r = kmalloc(sizeof *r, M_RMAN, M_NOWAIT);
283                                 if (r == 0) {
284                                         kfree(rv, M_RMAN);
285                                         rv = 0;
286                                         goto out;
287                                 }
288                                 bzero(r, sizeof *r);
289                                 r->r_start = rv->r_end + 1;
290                                 r->r_end = s->r_end;
291                                 r->r_flags = s->r_flags;
292                                 r->r_dev = 0;
293                                 r->r_sharehead = 0;
294                                 r->r_rm = rm;
295                                 s->r_end = rv->r_start - 1;
296                                 CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
297                                                      r_link);
298                                 CIRCLEQ_INSERT_AFTER(&rm->rm_list, rv, r,
299                                                      r_link);
300                         } else if (s->r_start == rv->r_start) {
301                                 DPRINTF(("allocating from the beginning\n"));
302                                 /*
303                                  * We are allocating at the beginning.
304                                  */
305                                 s->r_start = rv->r_end + 1;
306                                 CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, rv,
307                                                       r_link);
308                         } else {
309                                 DPRINTF(("allocating at the end\n"));
310                                 /*
311                                  * We are allocating at the end.
312                                  */
313                                 s->r_end = rv->r_start - 1;
314                                 CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
315                                                      r_link);
316                         }
317                         goto out;
318                 }
319         }
320
321         /*
322          * Now find an acceptable shared region, if the client's requirements
323          * allow sharing.  By our implementation restriction, a candidate
324          * region must match exactly by both size and sharing type in order
325          * to be considered compatible with the client's request.  (The
326          * former restriction could probably be lifted without too much
327          * additional work, but this does not seem warranted.)
328          */
329         DPRINTF(("no unshared regions found\n"));
330         if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0)
331                 goto out;
332
333         for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
334              s = CIRCLEQ_NEXT(s, r_link)) {
335                 if (s->r_start > end)
336                         break;
337                 if ((s->r_flags & flags) != flags)
338                         continue;
339                 rstart = max(s->r_start, start);
340                 rend = min(s->r_end, max(start + count, end));
341                 if (s->r_start >= start && s->r_end <= end
342                     && (s->r_end - s->r_start + 1) == count) {
343                         rv = kmalloc(sizeof *rv, M_RMAN, M_NOWAIT);
344                         if (rv == 0)
345                                 goto out;
346                         bzero(rv, sizeof *rv);
347                         rv->r_start = s->r_start;
348                         rv->r_end = s->r_end;
349                         rv->r_flags = s->r_flags & 
350                                 (RF_ALLOCATED | RF_SHAREABLE | RF_TIMESHARE);
351                         rv->r_dev = dev;
352                         rv->r_rm = rm;
353                         if (s->r_sharehead == 0) {
354                                 s->r_sharehead = kmalloc(sizeof *s->r_sharehead,
355                                                         M_RMAN, M_NOWAIT);
356                                 if (s->r_sharehead == 0) {
357                                         kfree(rv, M_RMAN);
358                                         rv = 0;
359                                         goto out;
360                                 }
361                                 bzero(s->r_sharehead, sizeof *s->r_sharehead);
362                                 LIST_INIT(s->r_sharehead);
363                                 LIST_INSERT_HEAD(s->r_sharehead, s, 
364                                                  r_sharelink);
365                                 s->r_flags |= RF_FIRSTSHARE;
366                         }
367                         rv->r_sharehead = s->r_sharehead;
368                         LIST_INSERT_HEAD(s->r_sharehead, rv, r_sharelink);
369                         goto out;
370                 }
371         }
372
373         /*
374          * We couldn't find anything.
375          */
376 out:
377         /*
378          * If the user specified RF_ACTIVE in the initial flags,
379          * which is reflected in `want_activate', we attempt to atomically
380          * activate the resource.  If this fails, we release the resource
381          * and indicate overall failure.  (This behavior probably doesn't
382          * make sense for RF_TIMESHARE-type resources.)
383          */
384         if (rv && want_activate) {
385                 struct resource *whohas;
386                 if (int_rman_activate_resource(rm, rv, &whohas)) {
387                         int_rman_release_resource(rm, rv);
388                         rv = 0;
389                 }
390         }
391         lwkt_reltoken(&ilock);
392         return (rv);
393 }
394
395 static int
396 int_rman_activate_resource(struct rman *rm, struct resource *r,
397                            struct resource **whohas)
398 {
399         struct resource *s;
400         int ok;
401
402         /*
403          * If we are not timesharing, then there is nothing much to do.
404          * If we already have the resource, then there is nothing at all to do.
405          * If we are not on a sharing list with anybody else, then there is
406          * little to do.
407          */
408         if ((r->r_flags & RF_TIMESHARE) == 0
409             || (r->r_flags & RF_ACTIVE) != 0
410             || r->r_sharehead == 0) {
411                 r->r_flags |= RF_ACTIVE;
412                 return 0;
413         }
414
415         ok = 1;
416         for (s = LIST_FIRST(r->r_sharehead); s && ok;
417              s = LIST_NEXT(s, r_sharelink)) {
418                 if ((s->r_flags & RF_ACTIVE) != 0) {
419                         ok = 0;
420                         *whohas = s;
421                 }
422         }
423         if (ok) {
424                 r->r_flags |= RF_ACTIVE;
425                 return 0;
426         }
427         return EBUSY;
428 }
429
430 int
431 rman_activate_resource(struct resource *r)
432 {
433         int rv;
434         struct resource *whohas;
435         lwkt_tokref ilock;
436         struct rman *rm;
437
438         rm = r->r_rm;
439         lwkt_gettoken(&ilock, rm->rm_slock);
440         rv = int_rman_activate_resource(rm, r, &whohas);
441         lwkt_reltoken(&ilock);
442         return rv;
443 }
444
445 #if 0
446
447 /* XXX */
448 int
449 rman_await_resource(struct resource *r, lwkt_tokref_t ilock, int slpflags, int timo)
450 {
451         int     rv;
452         struct  resource *whohas;
453         struct  rman *rm;
454
455         rm = r->r_rm;
456         for (;;) {
457                 lwkt_gettoken(ilock, rm->rm_slock);
458                 rv = int_rman_activate_resource(rm, r, &whohas);
459                 if (rv != EBUSY)
460                         return (rv);    /* returns with ilock held */
461
462                 if (r->r_sharehead == 0)
463                         panic("rman_await_resource");
464                 /*
465                  * A critical section will hopefully will prevent a race 
466                  * between lwkt_reltoken and tsleep where a process
467                  * could conceivably get in and release the resource
468                  * before we have a chance to sleep on it. YYY
469                  */
470                 crit_enter();
471                 whohas->r_flags |= RF_WANTED;
472                 rv = tsleep(r->r_sharehead, slpflags, "rmwait", timo);
473                 if (rv) {
474                         lwkt_reltoken(ilock);
475                         crit_exit();
476                         return rv;
477                 }
478                 crit_exit();
479         }
480 }
481
482 #endif
483
484 static int
485 int_rman_deactivate_resource(struct resource *r)
486 {
487         struct  rman *rm;
488
489         rm = r->r_rm;
490         r->r_flags &= ~RF_ACTIVE;
491         if (r->r_flags & RF_WANTED) {
492                 r->r_flags &= ~RF_WANTED;
493                 wakeup(r->r_sharehead);
494         }
495         return 0;
496 }
497
498 int
499 rman_deactivate_resource(struct resource *r)
500 {
501         lwkt_tokref ilock;
502         struct rman *rm;
503
504         rm = r->r_rm;
505         lwkt_gettoken(&ilock, rm->rm_slock);
506         int_rman_deactivate_resource(r);
507         lwkt_reltoken(&ilock);
508         return 0;
509 }
510
511 static int
512 int_rman_release_resource(struct rman *rm, struct resource *r)
513 {
514         struct  resource *s, *t;
515
516         if (r->r_flags & RF_ACTIVE)
517                 int_rman_deactivate_resource(r);
518
519         /*
520          * Check for a sharing list first.  If there is one, then we don't
521          * have to think as hard.
522          */
523         if (r->r_sharehead) {
524                 /*
525                  * If a sharing list exists, then we know there are at
526                  * least two sharers.
527                  *
528                  * If we are in the main circleq, appoint someone else.
529                  */
530                 LIST_REMOVE(r, r_sharelink);
531                 s = LIST_FIRST(r->r_sharehead);
532                 if (r->r_flags & RF_FIRSTSHARE) {
533                         s->r_flags |= RF_FIRSTSHARE;
534                         CIRCLEQ_INSERT_BEFORE(&rm->rm_list, r, s, r_link);
535                         CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
536                 }
537
538                 /*
539                  * Make sure that the sharing list goes away completely
540                  * if the resource is no longer being shared at all.
541                  */
542                 if (LIST_NEXT(s, r_sharelink) == 0) {
543                         kfree(s->r_sharehead, M_RMAN);
544                         s->r_sharehead = 0;
545                         s->r_flags &= ~RF_FIRSTSHARE;
546                 }
547                 goto out;
548         }
549
550         /*
551          * Look at the adjacent resources in the list and see if our
552          * segment can be merged with any of them.
553          */
554         s = CIRCLEQ_PREV(r, r_link);
555         t = CIRCLEQ_NEXT(r, r_link);
556
557         if (s != (void *)&rm->rm_list && (s->r_flags & RF_ALLOCATED) == 0
558             && t != (void *)&rm->rm_list && (t->r_flags & RF_ALLOCATED) == 0) {
559                 /*
560                  * Merge all three segments.
561                  */
562                 s->r_end = t->r_end;
563                 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
564                 CIRCLEQ_REMOVE(&rm->rm_list, t, r_link);
565                 kfree(t, M_RMAN);
566         } else if (s != (void *)&rm->rm_list
567                    && (s->r_flags & RF_ALLOCATED) == 0) {
568                 /*
569                  * Merge previous segment with ours.
570                  */
571                 s->r_end = r->r_end;
572                 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
573         } else if (t != (void *)&rm->rm_list
574                    && (t->r_flags & RF_ALLOCATED) == 0) {
575                 /*
576                  * Merge next segment with ours.
577                  */
578                 t->r_start = r->r_start;
579                 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
580         } else {
581                 /*
582                  * At this point, we know there is nothing we
583                  * can potentially merge with, because on each
584                  * side, there is either nothing there or what is
585                  * there is still allocated.  In that case, we don't
586                  * want to remove r from the list; we simply want to
587                  * change it to an unallocated region and return
588                  * without freeing anything.
589                  */
590                 r->r_flags &= ~RF_ALLOCATED;
591                 return 0;
592         }
593
594 out:
595         kfree(r, M_RMAN);
596         return 0;
597 }
598
599 int
600 rman_release_resource(struct resource *r)
601 {
602         struct  rman *rm = r->r_rm;
603         lwkt_tokref ilock;
604         int     rv;
605
606         lwkt_gettoken(&ilock, rm->rm_slock);
607         rv = int_rman_release_resource(rm, r);
608         lwkt_reltoken(&ilock);
609         return (rv);
610 }
611
612 uint32_t
613 rman_make_alignment_flags(uint32_t size)
614 {
615         int     i;
616
617         /*
618          * Find the hightest bit set, and add one if more than one bit
619          * set.  We're effectively computing the ceil(log2(size)) here.
620          */
621         for (i = 32; i > 0; i--)
622                 if ((1 << i) & size)
623                         break;
624         if (~(1 << i) & size)
625                 i++;
626
627         return(RF_ALIGNMENT_LOG2(i));
628 }