FreeBSD/Linux Kernel Cross Reference
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
30 /*
31 * The kernel resource manager. This code is responsible for keeping track
32 * of hardware resources which are apportioned out to various drivers.
33 * It does not actually assign those resources, and it is not expected
34 * that end-device drivers will call into this code directly. Rather,
35 * the code which implements the buses that those devices are attached to,
36 * and the code which manages CPU resources, will call this code, and the
37 * end-device drivers will make upcalls to that code to actually perform
38 * the allocation.
39 *
40 * There are two sorts of resources managed by this code. The first is
41 * the more familiar array (RMAN_ARRAY) type; resources in this class
42 * consist of a sequence of individually-allocatable objects which have
43 * been numbered in some well-defined order. Most of the resources
44 * are of this type, as it is the most familiar. The second type is
45 * called a gauge (RMAN_GAUGE), and models fungible resources (i.e.,
46 * resources in which each instance is indistinguishable from every
47 * other instance). The principal anticipated application of gauges
48 * is in the context of power consumption, where a bus may have a specific
49 * power budget which all attached devices share. RMAN_GAUGE is not
50 * implemented yet.
51 *
52 * For array resources, we make one simplifying assumption: two clients
53 * sharing the same resource must use the same range of indices. That
54 * is to say, sharing of overlapping-but-not-identical regions is not
55 * permitted.
56 */
57
58 #include <sys/cdefs.h>
59 __FBSDID("$FreeBSD: releng/5.2/sys/kern/subr_rman.c 116182 2003-06-11 00:56:59Z obrien $");
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/mutex.h>
67 #include <sys/bus.h> /* XXX debugging */
68 #include <machine/bus.h>
69 #include <sys/rman.h>
70 #include <sys/sysctl.h>
71
72 int rman_debug = 0;
73 TUNABLE_INT("debug.rman_debug", &rman_debug);
74 SYSCTL_INT(_debug, OID_AUTO, rman_debug, CTLFLAG_RW,
75 &rman_debug, 0, "rman debug");
76
77 #define DPRINTF(params) if (rman_debug) printf params
78
79 static MALLOC_DEFINE(M_RMAN, "rman", "Resource manager");
80
81 struct rman_head rman_head;
82 static struct mtx rman_mtx; /* mutex to protect rman_head */
83 static int int_rman_activate_resource(struct rman *rm, struct resource *r,
84 struct resource **whohas);
85 static int int_rman_deactivate_resource(struct resource *r);
86 static int int_rman_release_resource(struct rman *rm, struct resource *r);
87
88 int
89 rman_init(struct rman *rm)
90 {
91 static int once;
92
93 if (once == 0) {
94 once = 1;
95 TAILQ_INIT(&rman_head);
96 mtx_init(&rman_mtx, "rman head", NULL, MTX_DEF);
97 }
98
99 if (rm->rm_type == RMAN_UNINIT)
100 panic("rman_init");
101 if (rm->rm_type == RMAN_GAUGE)
102 panic("implement RMAN_GAUGE");
103
104 TAILQ_INIT(&rm->rm_list);
105 rm->rm_mtx = malloc(sizeof *rm->rm_mtx, M_RMAN, M_NOWAIT | M_ZERO);
106 if (rm->rm_mtx == 0)
107 return ENOMEM;
108 mtx_init(rm->rm_mtx, "rman", NULL, MTX_DEF);
109
110 mtx_lock(&rman_mtx);
111 TAILQ_INSERT_TAIL(&rman_head, rm, rm_link);
112 mtx_unlock(&rman_mtx);
113 return 0;
114 }
115
116 /*
117 * NB: this interface is not robust against programming errors which
118 * add multiple copies of the same region.
119 */
120 int
121 rman_manage_region(struct rman *rm, u_long start, u_long end)
122 {
123 struct resource *r, *s;
124
125 r = malloc(sizeof *r, M_RMAN, M_NOWAIT | M_ZERO);
126 if (r == 0)
127 return ENOMEM;
128 r->r_start = start;
129 r->r_end = end;
130 r->r_rm = rm;
131
132 mtx_lock(rm->rm_mtx);
133 for (s = TAILQ_FIRST(&rm->rm_list);
134 s && s->r_end < r->r_start;
135 s = TAILQ_NEXT(s, r_link))
136 ;
137
138 if (s == NULL) {
139 TAILQ_INSERT_TAIL(&rm->rm_list, r, r_link);
140 } else {
141 TAILQ_INSERT_BEFORE(s, r, r_link);
142 }
143
144 mtx_unlock(rm->rm_mtx);
145 return 0;
146 }
147
148 int
149 rman_fini(struct rman *rm)
150 {
151 struct resource *r;
152
153 mtx_lock(rm->rm_mtx);
154 TAILQ_FOREACH(r, &rm->rm_list, r_link) {
155 if (r->r_flags & RF_ALLOCATED) {
156 mtx_unlock(rm->rm_mtx);
157 return EBUSY;
158 }
159 }
160
161 /*
162 * There really should only be one of these if we are in this
163 * state and the code is working properly, but it can't hurt.
164 */
165 while (!TAILQ_EMPTY(&rm->rm_list)) {
166 r = TAILQ_FIRST(&rm->rm_list);
167 TAILQ_REMOVE(&rm->rm_list, r, r_link);
168 free(r, M_RMAN);
169 }
170 mtx_unlock(rm->rm_mtx);
171 mtx_lock(&rman_mtx);
172 TAILQ_REMOVE(&rman_head, rm, rm_link);
173 mtx_unlock(&rman_mtx);
174 mtx_destroy(rm->rm_mtx);
175 free(rm->rm_mtx, M_RMAN);
176
177 return 0;
178 }
179
180 struct resource *
181 rman_reserve_resource_bound(struct rman *rm, u_long start, u_long end,
182 u_long count, u_long bound, u_int flags,
183 struct device *dev)
184 {
185 u_int want_activate;
186 struct resource *r, *s, *rv;
187 u_long rstart, rend, amask, bmask;
188
189 rv = 0;
190
191 DPRINTF(("rman_reserve_resource: <%s> request: [%#lx, %#lx], length "
192 "%#lx, flags %u, device %s\n", rm->rm_descr, start, end, count,
193 flags, dev == NULL ? "<null>" : device_get_nameunit(dev)));
194 want_activate = (flags & RF_ACTIVE);
195 flags &= ~RF_ACTIVE;
196
197 mtx_lock(rm->rm_mtx);
198
199 for (r = TAILQ_FIRST(&rm->rm_list);
200 r && r->r_end < start;
201 r = TAILQ_NEXT(r, r_link))
202 ;
203
204 if (r == NULL) {
205 DPRINTF(("could not find a region\n"));
206 goto out;
207 }
208
209 amask = (1ul << RF_ALIGNMENT(flags)) - 1;
210 /* If bound is 0, bmask will also be 0 */
211 bmask = ~(bound - 1);
212 /*
213 * First try to find an acceptable totally-unshared region.
214 */
215 for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
216 DPRINTF(("considering [%#lx, %#lx]\n", s->r_start, s->r_end));
217 if (s->r_start > end) {
218 DPRINTF(("s->r_start (%#lx) > end (%#lx)\n", s->r_start, end));
219 break;
220 }
221 if (s->r_flags & RF_ALLOCATED) {
222 DPRINTF(("region is allocated\n"));
223 continue;
224 }
225 rstart = ulmax(s->r_start, start);
226 /*
227 * Try to find a region by adjusting to boundary and alignment
228 * until both conditions are satisfied. This is not an optimal
229 * algorithm, but in most cases it isn't really bad, either.
230 */
231 do {
232 rstart = (rstart + amask) & ~amask;
233 if (((rstart ^ (rstart + count - 1)) & bmask) != 0)
234 rstart += bound - (rstart & ~bmask);
235 } while ((rstart & amask) != 0 && rstart < end &&
236 rstart < s->r_end);
237 rend = ulmin(s->r_end, ulmax(rstart + count, end));
238 if (rstart > rend) {
239 DPRINTF(("adjusted start exceeds end\n"));
240 continue;
241 }
242 DPRINTF(("truncated region: [%#lx, %#lx]; size %#lx (requested %#lx)\n",
243 rstart, rend, (rend - rstart + 1), count));
244
245 if ((rend - rstart + 1) >= count) {
246 DPRINTF(("candidate region: [%#lx, %#lx], size %#lx\n",
247 rend, rstart, (rend - rstart + 1)));
248 if ((s->r_end - s->r_start + 1) == count) {
249 DPRINTF(("candidate region is entire chunk\n"));
250 rv = s;
251 rv->r_flags |= RF_ALLOCATED | flags;
252 rv->r_dev = dev;
253 goto out;
254 }
255
256 /*
257 * If s->r_start < rstart and
258 * s->r_end > rstart + count - 1, then
259 * we need to split the region into three pieces
260 * (the middle one will get returned to the user).
261 * Otherwise, we are allocating at either the
262 * beginning or the end of s, so we only need to
263 * split it in two. The first case requires
264 * two new allocations; the second requires but one.
265 */
266 rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO);
267 if (rv == 0)
268 goto out;
269 rv->r_start = rstart;
270 rv->r_end = rstart + count - 1;
271 rv->r_flags = flags | RF_ALLOCATED;
272 rv->r_dev = dev;
273 rv->r_rm = rm;
274
275 if (s->r_start < rv->r_start && s->r_end > rv->r_end) {
276 DPRINTF(("splitting region in three parts: "
277 "[%#lx, %#lx]; [%#lx, %#lx]; [%#lx, %#lx]\n",
278 s->r_start, rv->r_start - 1,
279 rv->r_start, rv->r_end,
280 rv->r_end + 1, s->r_end));
281 /*
282 * We are allocating in the middle.
283 */
284 r = malloc(sizeof *r, M_RMAN, M_NOWAIT|M_ZERO);
285 if (r == 0) {
286 free(rv, M_RMAN);
287 rv = 0;
288 goto out;
289 }
290 r->r_start = rv->r_end + 1;
291 r->r_end = s->r_end;
292 r->r_flags = s->r_flags;
293 r->r_rm = rm;
294 s->r_end = rv->r_start - 1;
295 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
296 r_link);
297 TAILQ_INSERT_AFTER(&rm->rm_list, rv, r,
298 r_link);
299 } else if (s->r_start == rv->r_start) {
300 DPRINTF(("allocating from the beginning\n"));
301 /*
302 * We are allocating at the beginning.
303 */
304 s->r_start = rv->r_end + 1;
305 TAILQ_INSERT_BEFORE(s, rv, r_link);
306 } else {
307 DPRINTF(("allocating at the end\n"));
308 /*
309 * We are allocating at the end.
310 */
311 s->r_end = rv->r_start - 1;
312 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
313 r_link);
314 }
315 goto out;
316 }
317 }
318
319 /*
320 * Now find an acceptable shared region, if the client's requirements
321 * allow sharing. By our implementation restriction, a candidate
322 * region must match exactly by both size and sharing type in order
323 * to be considered compatible with the client's request. (The
324 * former restriction could probably be lifted without too much
325 * additional work, but this does not seem warranted.)
326 */
327 DPRINTF(("no unshared regions found\n"));
328 if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0)
329 goto out;
330
331 for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
332 if (s->r_start > end)
333 break;
334 if ((s->r_flags & flags) != flags)
335 continue;
336 rstart = ulmax(s->r_start, start);
337 rend = ulmin(s->r_end, ulmax(start + count, end));
338 if (s->r_start >= start && s->r_end <= end
339 && (s->r_end - s->r_start + 1) == count &&
340 (s->r_start & amask) == 0 &&
341 ((s->r_start ^ s->r_end) & bmask) == 0) {
342 rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO);
343 if (rv == 0)
344 goto out;
345 rv->r_start = s->r_start;
346 rv->r_end = s->r_end;
347 rv->r_flags = s->r_flags &
348 (RF_ALLOCATED | RF_SHAREABLE | RF_TIMESHARE);
349 rv->r_dev = dev;
350 rv->r_rm = rm;
351 if (s->r_sharehead == 0) {
352 s->r_sharehead = malloc(sizeof *s->r_sharehead,
353 M_RMAN, M_NOWAIT | M_ZERO);
354 if (s->r_sharehead == 0) {
355 free(rv, M_RMAN);
356 rv = 0;
357 goto out;
358 }
359 LIST_INIT(s->r_sharehead);
360 LIST_INSERT_HEAD(s->r_sharehead, s,
361 r_sharelink);
362 s->r_flags |= RF_FIRSTSHARE;
363 }
364 rv->r_sharehead = s->r_sharehead;
365 LIST_INSERT_HEAD(s->r_sharehead, rv, r_sharelink);
366 goto out;
367 }
368 }
369
370 /*
371 * We couldn't find anything.
372 */
373 out:
374 /*
375 * If the user specified RF_ACTIVE in the initial flags,
376 * which is reflected in `want_activate', we attempt to atomically
377 * activate the resource. If this fails, we release the resource
378 * and indicate overall failure. (This behavior probably doesn't
379 * make sense for RF_TIMESHARE-type resources.)
380 */
381 if (rv && want_activate) {
382 struct resource *whohas;
383 if (int_rman_activate_resource(rm, rv, &whohas)) {
384 int_rman_release_resource(rm, rv);
385 rv = 0;
386 }
387 }
388
389 mtx_unlock(rm->rm_mtx);
390 return (rv);
391 }
392
393 struct resource *
394 rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
395 u_int flags, struct device *dev)
396 {
397
398 return (rman_reserve_resource_bound(rm, start, end, count, 0, flags,
399 dev));
400 }
401
402 static int
403 int_rman_activate_resource(struct rman *rm, struct resource *r,
404 struct resource **whohas)
405 {
406 struct resource *s;
407 int ok;
408
409 /*
410 * If we are not timesharing, then there is nothing much to do.
411 * If we already have the resource, then there is nothing at all to do.
412 * If we are not on a sharing list with anybody else, then there is
413 * little to do.
414 */
415 if ((r->r_flags & RF_TIMESHARE) == 0
416 || (r->r_flags & RF_ACTIVE) != 0
417 || r->r_sharehead == 0) {
418 r->r_flags |= RF_ACTIVE;
419 return 0;
420 }
421
422 ok = 1;
423 for (s = LIST_FIRST(r->r_sharehead); s && ok;
424 s = LIST_NEXT(s, r_sharelink)) {
425 if ((s->r_flags & RF_ACTIVE) != 0) {
426 ok = 0;
427 *whohas = s;
428 }
429 }
430 if (ok) {
431 r->r_flags |= RF_ACTIVE;
432 return 0;
433 }
434 return EBUSY;
435 }
436
437 int
438 rman_activate_resource(struct resource *r)
439 {
440 int rv;
441 struct resource *whohas;
442 struct rman *rm;
443
444 rm = r->r_rm;
445 mtx_lock(rm->rm_mtx);
446 rv = int_rman_activate_resource(rm, r, &whohas);
447 mtx_unlock(rm->rm_mtx);
448 return rv;
449 }
450
451 int
452 rman_await_resource(struct resource *r, int pri, int timo)
453 {
454 int rv;
455 struct resource *whohas;
456 struct rman *rm;
457
458 rm = r->r_rm;
459 mtx_lock(rm->rm_mtx);
460 for (;;) {
461 rv = int_rman_activate_resource(rm, r, &whohas);
462 if (rv != EBUSY)
463 return (rv); /* returns with mutex held */
464
465 if (r->r_sharehead == 0)
466 panic("rman_await_resource");
467 whohas->r_flags |= RF_WANTED;
468 rv = msleep(r->r_sharehead, rm->rm_mtx, pri, "rmwait", timo);
469 if (rv) {
470 mtx_unlock(rm->rm_mtx);
471 return (rv);
472 }
473 }
474 }
475
476 static int
477 int_rman_deactivate_resource(struct resource *r)
478 {
479
480 r->r_flags &= ~RF_ACTIVE;
481 if (r->r_flags & RF_WANTED) {
482 r->r_flags &= ~RF_WANTED;
483 wakeup(r->r_sharehead);
484 }
485 return 0;
486 }
487
488 int
489 rman_deactivate_resource(struct resource *r)
490 {
491 struct rman *rm;
492
493 rm = r->r_rm;
494 mtx_lock(rm->rm_mtx);
495 int_rman_deactivate_resource(r);
496 mtx_unlock(rm->rm_mtx);
497 return 0;
498 }
499
500 static int
501 int_rman_release_resource(struct rman *rm, struct resource *r)
502 {
503 struct resource *s, *t;
504
505 if (r->r_flags & RF_ACTIVE)
506 int_rman_deactivate_resource(r);
507
508 /*
509 * Check for a sharing list first. If there is one, then we don't
510 * have to think as hard.
511 */
512 if (r->r_sharehead) {
513 /*
514 * If a sharing list exists, then we know there are at
515 * least two sharers.
516 *
517 * If we are in the main circleq, appoint someone else.
518 */
519 LIST_REMOVE(r, r_sharelink);
520 s = LIST_FIRST(r->r_sharehead);
521 if (r->r_flags & RF_FIRSTSHARE) {
522 s->r_flags |= RF_FIRSTSHARE;
523 TAILQ_INSERT_BEFORE(r, s, r_link);
524 TAILQ_REMOVE(&rm->rm_list, r, r_link);
525 }
526
527 /*
528 * Make sure that the sharing list goes away completely
529 * if the resource is no longer being shared at all.
530 */
531 if (LIST_NEXT(s, r_sharelink) == 0) {
532 free(s->r_sharehead, M_RMAN);
533 s->r_sharehead = 0;
534 s->r_flags &= ~RF_FIRSTSHARE;
535 }
536 goto out;
537 }
538
539 /*
540 * Look at the adjacent resources in the list and see if our
541 * segment can be merged with any of them.
542 */
543 s = TAILQ_PREV(r, resource_head, r_link);
544 t = TAILQ_NEXT(r, r_link);
545
546 if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0
547 && t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
548 /*
549 * Merge all three segments.
550 */
551 s->r_end = t->r_end;
552 TAILQ_REMOVE(&rm->rm_list, r, r_link);
553 TAILQ_REMOVE(&rm->rm_list, t, r_link);
554 free(t, M_RMAN);
555 } else if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0) {
556 /*
557 * Merge previous segment with ours.
558 */
559 s->r_end = r->r_end;
560 TAILQ_REMOVE(&rm->rm_list, r, r_link);
561 } else if (t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
562 /*
563 * Merge next segment with ours.
564 */
565 t->r_start = r->r_start;
566 TAILQ_REMOVE(&rm->rm_list, r, r_link);
567 } else {
568 /*
569 * At this point, we know there is nothing we
570 * can potentially merge with, because on each
571 * side, there is either nothing there or what is
572 * there is still allocated. In that case, we don't
573 * want to remove r from the list; we simply want to
574 * change it to an unallocated region and return
575 * without freeing anything.
576 */
577 r->r_flags &= ~RF_ALLOCATED;
578 return 0;
579 }
580
581 out:
582 free(r, M_RMAN);
583 return 0;
584 }
585
586 int
587 rman_release_resource(struct resource *r)
588 {
589 int rv;
590 struct rman *rm = r->r_rm;
591
592 mtx_lock(rm->rm_mtx);
593 rv = int_rman_release_resource(rm, r);
594 mtx_unlock(rm->rm_mtx);
595 return (rv);
596 }
597
598 uint32_t
599 rman_make_alignment_flags(uint32_t size)
600 {
601 int i;
602
603 /*
604 * Find the hightest bit set, and add one if more than one bit
605 * set. We're effectively computing the ceil(log2(size)) here.
606 */
607 for (i = 31; i > 0; i--)
608 if ((1 << i) & size)
609 break;
610 if (~(1 << i) & size)
611 i++;
612
613 return(RF_ALIGNMENT_LOG2(i));
614 }
615
616 u_long
617 rman_get_start(struct resource *r)
618 {
619 return (r->r_start);
620 }
621
622 u_long
623 rman_get_end(struct resource *r)
624 {
625 return (r->r_end);
626 }
627
628 u_long
629 rman_get_size(struct resource *r)
630 {
631 return (r->r_end - r->r_start + 1);
632 }
633
634 u_int
635 rman_get_flags(struct resource *r)
636 {
637 return (r->r_flags);
638 }
639
640 void
641 rman_set_virtual(struct resource *r, void *v)
642 {
643 r->r_virtual = v;
644 }
645
646 void *
647 rman_get_virtual(struct resource *r)
648 {
649 return (r->r_virtual);
650 }
651
652 void
653 rman_set_bustag(struct resource *r, bus_space_tag_t t)
654 {
655 r->r_bustag = t;
656 }
657
658 bus_space_tag_t
659 rman_get_bustag(struct resource *r)
660 {
661 return (r->r_bustag);
662 }
663
664 void
665 rman_set_bushandle(struct resource *r, bus_space_handle_t h)
666 {
667 r->r_bushandle = h;
668 }
669
670 bus_space_handle_t
671 rman_get_bushandle(struct resource *r)
672 {
673 return (r->r_bushandle);
674 }
675
676 void
677 rman_set_rid(struct resource *r, int rid)
678 {
679 r->r_rid = rid;
680 }
681
682 int
683 rman_get_rid(struct resource *r)
684 {
685 return (r->r_rid);
686 }
687
688 struct device *
689 rman_get_device(struct resource *r)
690 {
691 return (r->r_dev);
692 }
Cache object: b0c4e40101b83b887947831af074aed9
|