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 * $FreeBSD$
30 */
31
32 /*
33 * The kernel resource manager. This code is responsible for keeping track
34 * of hardware resources which are apportioned out to various drivers.
35 * It does not actually assign those resources, and it is not expected
36 * that end-device drivers will call into this code directly. Rather,
37 * the code which implements the buses that those devices are attached to,
38 * and the code which manages CPU resources, will call this code, and the
39 * end-device drivers will make upcalls to that code to actually perform
40 * the allocation.
41 *
42 * There are two sorts of resources managed by this code. The first is
43 * the more familiar array (RMAN_ARRAY) type; resources in this class
44 * consist of a sequence of individually-allocatable objects which have
45 * been numbered in some well-defined order. Most of the resources
46 * are of this type, as it is the most familiar. The second type is
47 * called a gauge (RMAN_GAUGE), and models fungible resources (i.e.,
48 * resources in which each instance is indistinguishable from every
49 * other instance). The principal anticipated application of gauges
50 * is in the context of power consumption, where a bus may have a specific
51 * power budget which all attached devices share. RMAN_GAUGE is not
52 * implemented yet.
53 *
54 * For array resources, we make one simplifying assumption: two clients
55 * sharing the same resource must use the same range of indices. That
56 * is to say, sharing of overlapping-but-not-identical regions is not
57 * permitted.
58 */
59
60 #include <sys/param.h>
61 #include <sys/systm.h>
62 #include <sys/kernel.h>
63 #include <sys/lock.h>
64 #include <sys/malloc.h>
65 #include <sys/rman.h>
66 #include <sys/bus.h> /* XXX debugging */
67
68 MALLOC_DEFINE(M_RMAN, "rman", "Resource manager");
69
70 struct rman_head rman_head;
71 #ifndef NULL_SIMPLELOCKS
72 static struct simplelock rman_lock; /* mutex to protect rman_head */
73 #endif
74 static int int_rman_activate_resource(struct rman *rm, struct resource *r,
75 struct resource **whohas);
76 static int int_rman_release_resource(struct rman *rm, struct resource *r);
77
78 #define CIRCLEQ_TERMCOND(var, head) (var == (void *)&(head))
79
80 int
81 rman_init(struct rman *rm)
82 {
83 static int once;
84
85 if (once == 0) {
86 once = 1;
87 TAILQ_INIT(&rman_head);
88 simple_lock_init(&rman_lock);
89 }
90
91 if (rm->rm_type == RMAN_UNINIT)
92 panic("rman_init");
93 if (rm->rm_type == RMAN_GAUGE)
94 panic("implement RMAN_GAUGE");
95
96 CIRCLEQ_INIT(&rm->rm_list);
97 rm->rm_slock = malloc(sizeof *rm->rm_slock, M_RMAN, M_NOWAIT);
98 if (rm->rm_slock == 0)
99 return ENOMEM;
100 simple_lock_init(rm->rm_slock);
101
102 simple_lock(&rman_lock);
103 TAILQ_INSERT_TAIL(&rman_head, rm, rm_link);
104 simple_unlock(&rman_lock);
105 return 0;
106 }
107
108 /*
109 * NB: this interface is not robust against programming errors which
110 * add multiple copies of the same region.
111 */
112 int
113 rman_manage_region(struct rman *rm, u_long start, u_long end)
114 {
115 struct resource *r, *s;
116
117 r = malloc(sizeof *r, M_RMAN, M_NOWAIT);
118 if (r == 0)
119 return ENOMEM;
120 r->r_sharehead = 0;
121 r->r_start = start;
122 r->r_end = end;
123 r->r_flags = 0;
124 r->r_dev = 0;
125 r->r_rm = rm;
126
127 simple_lock(rm->rm_slock);
128 for (s = rm->rm_list.cqh_first;
129 !CIRCLEQ_TERMCOND(s, rm->rm_list) && s->r_end < r->r_start;
130 s = s->r_link.cqe_next)
131 ;
132
133 if (CIRCLEQ_TERMCOND(s, rm->rm_list)) {
134 CIRCLEQ_INSERT_TAIL(&rm->rm_list, r, r_link);
135 } else {
136 CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, r, r_link);
137 }
138
139 simple_unlock(rm->rm_slock);
140 return 0;
141 }
142
143 int
144 rman_fini(struct rman *rm)
145 {
146 struct resource *r;
147
148 simple_lock(rm->rm_slock);
149 for (r = rm->rm_list.cqh_first; !CIRCLEQ_TERMCOND(r, rm->rm_list);
150 r = r->r_link.cqe_next) {
151 if (r->r_flags & RF_ALLOCATED)
152 return EBUSY;
153 }
154
155 /*
156 * There really should only be one of these if we are in this
157 * state and the code is working properly, but it can't hurt.
158 */
159 for (r = rm->rm_list.cqh_first; !CIRCLEQ_TERMCOND(r, rm->rm_list);
160 r = rm->rm_list.cqh_first) {
161 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
162 free(r, M_RMAN);
163 }
164 simple_unlock(rm->rm_slock);
165 simple_lock(&rman_lock);
166 TAILQ_REMOVE(&rman_head, rm, rm_link);
167 simple_unlock(&rman_lock);
168 free(rm->rm_slock, M_RMAN);
169
170 return 0;
171 }
172
173 struct resource *
174 rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
175 u_int flags, struct device *dev)
176 {
177 u_int want_activate;
178 struct resource *r, *s, *rv;
179 u_long rstart, rend;
180
181 rv = 0;
182
183 #ifdef RMAN_DEBUG
184 printf("rman_reserve_resource: <%s> request: [%#lx, %#lx], length "
185 "%#lx, flags %u, device %s%d\n", rm->rm_descr, start, end,
186 count, flags, device_get_name(dev), device_get_unit(dev));
187 #endif /* RMAN_DEBUG */
188 want_activate = (flags & RF_ACTIVE);
189 flags &= ~RF_ACTIVE;
190
191 simple_lock(rm->rm_slock);
192
193 for (r = rm->rm_list.cqh_first;
194 !CIRCLEQ_TERMCOND(r, rm->rm_list) && r->r_end < start;
195 r = r->r_link.cqe_next)
196 ;
197
198 if (CIRCLEQ_TERMCOND(r, rm->rm_list)) {
199 #ifdef RMAN_DEBUG
200 printf("could not find a region\n");
201 #endif RMAN_DEBUG
202 goto out;
203 }
204
205 /*
206 * First try to find an acceptable totally-unshared region.
207 */
208 for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
209 s = s->r_link.cqe_next) {
210 #ifdef RMAN_DEBUG
211 printf("considering [%#lx, %#lx]\n", s->r_start, s->r_end);
212 #endif /* RMAN_DEBUG */
213 if (s->r_start > end) {
214 #ifdef RMAN_DEBUG
215 printf("s->r_start (%#lx) > end (%#lx)\n", s->r_start, end);
216 #endif /* RMAN_DEBUG */
217 break;
218 }
219 if (s->r_flags & RF_ALLOCATED) {
220 #ifdef RMAN_DEBUG
221 printf("region is allocated\n");
222 #endif /* RMAN_DEBUG */
223 continue;
224 }
225 rstart = max(s->r_start, start);
226 rend = min(s->r_end, max(start + count, end));
227 #ifdef RMAN_DEBUG
228 printf("truncated region: [%#lx, %#lx]; size %#lx (requested %#lx)\n",
229 rstart, rend, (rend - rstart + 1), count);
230 #endif /* RMAN_DEBUG */
231
232 if ((rend - rstart + 1) >= count) {
233 #ifdef RMAN_DEBUG
234 printf("candidate region: [%#lx, %#lx], size %#lx\n",
235 rend, rstart, (rend - rstart + 1));
236 #endif /* RMAN_DEBUG */
237 if ((s->r_end - s->r_start + 1) == count) {
238 #ifdef RMAN_DEBUG
239 printf("candidate region is entire chunk\n");
240 #endif /* RMAN_DEBUG */
241 rv = s;
242 rv->r_flags |= RF_ALLOCATED;
243 rv->r_dev = dev;
244 goto out;
245 }
246
247 /*
248 * If s->r_start < rstart and
249 * s->r_end > rstart + count - 1, then
250 * we need to split the region into three pieces
251 * (the middle one will get returned to the user).
252 * Otherwise, we are allocating at either the
253 * beginning or the end of s, so we only need to
254 * split it in two. The first case requires
255 * two new allocations; the second requires but one.
256 */
257 rv = malloc(sizeof *r, M_RMAN, M_NOWAIT);
258 if (rv == 0)
259 goto out;
260 rv->r_start = rstart;
261 rv->r_end = rstart + count - 1;
262 rv->r_flags = flags | RF_ALLOCATED;
263 rv->r_dev = dev;
264 rv->r_sharehead = 0;
265
266 if (s->r_start < rv->r_start && s->r_end > rv->r_end) {
267 #ifdef RMAN_DEBUG
268 printf("splitting region in three parts: "
269 "[%#lx, %#lx]; [%#lx, %#lx]; [%#lx, %#lx]\n",
270 s->r_start, rv->r_start - 1,
271 rv->r_start, rv->r_end,
272 rv->r_end + 1, s->r_end);
273 #endif /* RMAN_DEBUG */
274 /*
275 * We are allocating in the middle.
276 */
277 r = malloc(sizeof *r, M_RMAN, M_NOWAIT);
278 if (r == 0) {
279 free(rv, M_RMAN);
280 rv = 0;
281 goto out;
282 }
283 r->r_start = rv->r_end + 1;
284 r->r_end = s->r_end;
285 r->r_flags = s->r_flags;
286 r->r_dev = 0;
287 r->r_sharehead = 0;
288 s->r_end = rv->r_start - 1;
289 CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
290 r_link);
291 CIRCLEQ_INSERT_AFTER(&rm->rm_list, rv, r,
292 r_link);
293 } else if (s->r_start == rv->r_start) {
294 #ifdef RMAN_DEBUG
295 printf("allocating from the beginning\n");
296 #endif /* RMAN_DEBUG */
297 /*
298 * We are allocating at the beginning.
299 */
300 s->r_start = rv->r_end + 1;
301 CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, rv,
302 r_link);
303 } else {
304 #ifdef RMAN_DEBUG
305 printf("allocating at the end\n");
306 #endif /* RMAN_DEBUG */
307 /*
308 * We are allocating at the end.
309 */
310 s->r_end = rv->r_start - 1;
311 CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
312 r_link);
313 }
314 goto out;
315 }
316 }
317
318 /*
319 * Now find an acceptable shared region, if the client's requirements
320 * allow sharing. By our implementation restriction, a candidate
321 * region must match exactly by both size and sharing type in order
322 * to be considered compatible with the client's request. (The
323 * former restriction could probably be lifted without too much
324 * additional work, but this does not seem warranted.)
325 */
326 #ifdef RMAN_DEBUG
327 printf("no unshared regions found\n");
328 #endif /* RMAN_DEBUG */
329 if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0)
330 goto out;
331
332 for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
333 s = s->r_link.cqe_next) {
334 if (s->r_start > end)
335 break;
336 if ((s->r_flags & flags) != flags)
337 continue;
338 rstart = max(s->r_start, start);
339 rend = min(s->r_end, max(start + count, end));
340 if (s->r_start >= start && s->r_end <= end
341 && (s->r_end - s->r_start + 1) == count) {
342 rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT);
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);
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 simple_unlock(rm->rm_slock);
390 return (rv);
391 }
392
393 static int
394 int_rman_activate_resource(struct rman *rm, struct resource *r,
395 struct resource **whohas)
396 {
397 struct resource *s;
398 int ok;
399
400 /*
401 * If we are not timesharing, then there is nothing much to do.
402 * If we already have the resource, then there is nothing at all to do.
403 * If we are not on a sharing list with anybody else, then there is
404 * little to do.
405 */
406 if ((r->r_flags & RF_TIMESHARE) == 0
407 || (r->r_flags & RF_ACTIVE) != 0
408 || r->r_sharehead == 0) {
409 r->r_flags |= RF_ACTIVE;
410 return 0;
411 }
412
413 ok = 1;
414 for (s = r->r_sharehead->lh_first; s && ok;
415 s = s->r_sharelink.le_next) {
416 if ((s->r_flags & RF_ACTIVE) != 0) {
417 ok = 0;
418 *whohas = s;
419 }
420 }
421 if (ok) {
422 r->r_flags |= RF_ACTIVE;
423 return 0;
424 }
425 return EBUSY;
426 }
427
428 int
429 rman_activate_resource(struct resource *r)
430 {
431 int rv;
432 struct resource *whohas;
433 struct rman *rm;
434
435 rm = r->r_rm;
436 simple_lock(rm->rm_slock);
437 rv = int_rman_activate_resource(rm, r, &whohas);
438 simple_unlock(rm->rm_slock);
439 return rv;
440 }
441
442 int
443 rman_await_resource(struct resource *r, int pri, int timo)
444 {
445 int rv, s;
446 struct resource *whohas;
447 struct rman *rm;
448
449 rm = r->r_rm;
450 for (;;) {
451 simple_lock(rm->rm_slock);
452 rv = int_rman_activate_resource(rm, r, &whohas);
453 if (rv != EBUSY)
454 return (rv);
455
456 if (r->r_sharehead == 0)
457 panic("rman_await_resource");
458 /*
459 * splhigh hopefully will prevent a race between
460 * simple_unlock and tsleep where a process
461 * could conceivably get in and release the resource
462 * before we have a chance to sleep on it.
463 */
464 s = splhigh();
465 whohas->r_flags |= RF_WANTED;
466 simple_unlock(rm->rm_slock);
467 rv = tsleep(r->r_sharehead, pri, "rmwait", timo);
468 if (rv) {
469 splx(s);
470 return rv;
471 }
472 simple_lock(rm->rm_slock);
473 splx(s);
474 }
475 }
476
477 int
478 rman_deactivate_resource(struct resource *r)
479 {
480 struct rman *rm;
481
482 rm = r->r_rm;
483 simple_lock(rm->rm_slock);
484 r->r_flags &= ~RF_ACTIVE;
485 if (r->r_flags & RF_WANTED) {
486 r->r_flags &= ~RF_WANTED;
487 wakeup(r->r_sharehead);
488 }
489 simple_unlock(rm->rm_slock);
490 return 0;
491 }
492
493 static int
494 int_rman_release_resource(struct rman *rm, struct resource *r)
495 {
496 struct resource *s, *t;
497
498 if (r->r_flags & RF_ACTIVE)
499 return EBUSY;
500
501 /*
502 * Check for a sharing list first. If there is one, then we don't
503 * have to think as hard.
504 */
505 if (r->r_sharehead) {
506 /*
507 * If a sharing list exists, then we know there are at
508 * least two sharers.
509 *
510 * If we are in the main circleq, appoint someone else.
511 */
512 LIST_REMOVE(r, r_sharelink);
513 s = r->r_sharehead->lh_first;
514 if (r->r_flags & RF_FIRSTSHARE) {
515 s->r_flags |= RF_FIRSTSHARE;
516 CIRCLEQ_INSERT_BEFORE(&rm->rm_list, r, s, r_link);
517 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
518 }
519
520 /*
521 * Make sure that the sharing list goes away completely
522 * if the resource is no longer being shared at all.
523 */
524 if (s->r_sharelink.le_next == 0) {
525 free(s->r_sharehead, M_RMAN);
526 s->r_sharehead = 0;
527 s->r_flags &= ~RF_FIRSTSHARE;
528 }
529 goto out;
530 }
531
532 /*
533 * Look at the adjacent resources in the list and see if our
534 * segment can be merged with any of them.
535 */
536 s = r->r_link.cqe_prev;
537 t = r->r_link.cqe_next;
538
539 if (s != (void *)&rm->rm_list && (s->r_flags & RF_ALLOCATED) == 0
540 && t != (void *)&rm->rm_list && (t->r_flags & RF_ALLOCATED) == 0) {
541 /*
542 * Merge all three segments.
543 */
544 s->r_end = t->r_end;
545 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
546 CIRCLEQ_REMOVE(&rm->rm_list, t, r_link);
547 free(t, M_RMAN);
548 } else if (s != (void *)&rm->rm_list
549 && (s->r_flags & RF_ALLOCATED) == 0) {
550 /*
551 * Merge previous segment with ours.
552 */
553 s->r_end = r->r_end;
554 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
555 } else if (t != (void *)&rm->rm_list
556 && (t->r_flags & RF_ALLOCATED) == 0) {
557 /*
558 * Merge next segment with ours.
559 */
560 t->r_start = r->r_start;
561 CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
562 } else {
563 /*
564 * At this point, we know there is nothing we
565 * can potentially merge with, because on each
566 * side, there is either nothing there or what is
567 * there is still allocated. In that case, we don't
568 * want to remove r from the list; we simply want to
569 * change it to an unallocated region and return
570 * without freeing anything.
571 */
572 r->r_flags &= ~RF_ALLOCATED;
573 return 0;
574 }
575
576 out:
577 free(r, M_RMAN);
578 return 0;
579 }
580
581 int
582 rman_release_resource(struct resource *r)
583 {
584 int rv;
585 struct rman *rm = r->r_rm;
586
587 simple_lock(rm->rm_slock);
588 rv = int_rman_release_resource(rm, r);
589 simple_unlock(rm->rm_slock);
590 return (rv);
591 }
Cache object: 9b4bd19324840117b020853fbdc363ed
|