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$"); 60 61 #define __RMAN_RESOURCE_VISIBLE 62 #include <sys/param.h> 63 #include <sys/systm.h> 64 #include <sys/kernel.h> 65 #include <sys/lock.h> 66 #include <sys/malloc.h> 67 #include <sys/mutex.h> 68 #include <sys/bus.h> /* XXX debugging */ 69 #include <machine/bus.h> 70 #include <sys/rman.h> 71 #include <sys/sysctl.h> 72 73 int rman_debug = 0; 74 TUNABLE_INT("debug.rman_debug", &rman_debug); 75 SYSCTL_INT(_debug, OID_AUTO, rman_debug, CTLFLAG_RW, 76 &rman_debug, 0, "rman debug"); 77 78 #define DPRINTF(params) if (rman_debug) printf params 79 80 static MALLOC_DEFINE(M_RMAN, "rman", "Resource manager"); 81 82 struct rman_head rman_head; 83 static struct mtx rman_mtx; /* mutex to protect rman_head */ 84 static int int_rman_activate_resource(struct rman *rm, struct resource *r, 85 struct resource **whohas); 86 static int int_rman_deactivate_resource(struct resource *r); 87 static int int_rman_release_resource(struct rman *rm, struct resource *r); 88 89 int 90 rman_init(struct rman *rm) 91 { 92 static int once; 93 94 if (once == 0) { 95 once = 1; 96 TAILQ_INIT(&rman_head); 97 mtx_init(&rman_mtx, "rman head", NULL, MTX_DEF); 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 TAILQ_INIT(&rm->rm_list); 106 rm->rm_mtx = malloc(sizeof *rm->rm_mtx, M_RMAN, M_NOWAIT | M_ZERO); 107 if (rm->rm_mtx == 0) 108 return ENOMEM; 109 mtx_init(rm->rm_mtx, "rman", NULL, MTX_DEF); 110 111 mtx_lock(&rman_mtx); 112 TAILQ_INSERT_TAIL(&rman_head, rm, rm_link); 113 mtx_unlock(&rman_mtx); 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 126 DPRINTF(("rman_manage_region: <%s> request: start %#lx, end %#lx\n", 127 rm->rm_descr, start, end)); 128 r = malloc(sizeof *r, M_RMAN, M_NOWAIT | M_ZERO); 129 if (r == 0) 130 return ENOMEM; 131 r->r_start = start; 132 r->r_end = end; 133 r->r_rm = rm; 134 135 mtx_lock(rm->rm_mtx); 136 for (s = TAILQ_FIRST(&rm->rm_list); 137 s && s->r_end < r->r_start; 138 s = TAILQ_NEXT(s, r_link)) 139 ; 140 141 if (s == NULL) { 142 TAILQ_INSERT_TAIL(&rm->rm_list, r, r_link); 143 } else { 144 TAILQ_INSERT_BEFORE(s, r, r_link); 145 } 146 147 mtx_unlock(rm->rm_mtx); 148 return 0; 149 } 150 151 int 152 rman_fini(struct rman *rm) 153 { 154 struct resource *r; 155 156 mtx_lock(rm->rm_mtx); 157 TAILQ_FOREACH(r, &rm->rm_list, r_link) { 158 if (r->r_flags & RF_ALLOCATED) { 159 mtx_unlock(rm->rm_mtx); 160 return EBUSY; 161 } 162 } 163 164 /* 165 * There really should only be one of these if we are in this 166 * state and the code is working properly, but it can't hurt. 167 */ 168 while (!TAILQ_EMPTY(&rm->rm_list)) { 169 r = TAILQ_FIRST(&rm->rm_list); 170 TAILQ_REMOVE(&rm->rm_list, r, r_link); 171 free(r, M_RMAN); 172 } 173 mtx_unlock(rm->rm_mtx); 174 mtx_lock(&rman_mtx); 175 TAILQ_REMOVE(&rman_head, rm, rm_link); 176 mtx_unlock(&rman_mtx); 177 mtx_destroy(rm->rm_mtx); 178 free(rm->rm_mtx, M_RMAN); 179 180 return 0; 181 } 182 183 struct resource * 184 rman_reserve_resource_bound(struct rman *rm, u_long start, u_long end, 185 u_long count, u_long bound, u_int flags, 186 struct device *dev) 187 { 188 u_int want_activate; 189 struct resource *r, *s, *rv; 190 u_long rstart, rend, amask, bmask; 191 192 rv = 0; 193 194 DPRINTF(("rman_reserve_resource: <%s> request: [%#lx, %#lx], length " 195 "%#lx, flags %u, device %s\n", rm->rm_descr, start, end, count, 196 flags, dev == NULL ? "<null>" : device_get_nameunit(dev))); 197 want_activate = (flags & RF_ACTIVE); 198 flags &= ~RF_ACTIVE; 199 200 mtx_lock(rm->rm_mtx); 201 202 for (r = TAILQ_FIRST(&rm->rm_list); 203 r && r->r_end < start; 204 r = TAILQ_NEXT(r, r_link)) 205 ; 206 207 if (r == NULL) { 208 DPRINTF(("could not find a region\n")); 209 goto out; 210 } 211 212 amask = (1ul << RF_ALIGNMENT(flags)) - 1; 213 /* If bound is 0, bmask will also be 0 */ 214 bmask = ~(bound - 1); 215 /* 216 * First try to find an acceptable totally-unshared region. 217 */ 218 for (s = r; s; s = TAILQ_NEXT(s, r_link)) { 219 DPRINTF(("considering [%#lx, %#lx]\n", s->r_start, s->r_end)); 220 if (s->r_start > end) { 221 DPRINTF(("s->r_start (%#lx) > end (%#lx)\n", s->r_start, end)); 222 break; 223 } 224 if (s->r_flags & RF_ALLOCATED) { 225 DPRINTF(("region is allocated\n")); 226 continue; 227 } 228 rstart = ulmax(s->r_start, start); 229 /* 230 * Try to find a region by adjusting to boundary and alignment 231 * until both conditions are satisfied. This is not an optimal 232 * algorithm, but in most cases it isn't really bad, either. 233 */ 234 do { 235 rstart = (rstart + amask) & ~amask; 236 if (((rstart ^ (rstart + count - 1)) & bmask) != 0) 237 rstart += bound - (rstart & ~bmask); 238 } while ((rstart & amask) != 0 && rstart < end && 239 rstart < s->r_end); 240 rend = ulmin(s->r_end, ulmax(rstart + count - 1, end)); 241 if (rstart > rend) { 242 DPRINTF(("adjusted start exceeds end\n")); 243 continue; 244 } 245 DPRINTF(("truncated region: [%#lx, %#lx]; size %#lx (requested %#lx)\n", 246 rstart, rend, (rend - rstart + 1), count)); 247 248 if ((rend - rstart + 1) >= count) { 249 DPRINTF(("candidate region: [%#lx, %#lx], size %#lx\n", 250 rend, rstart, (rend - rstart + 1))); 251 if ((s->r_end - s->r_start + 1) == count) { 252 DPRINTF(("candidate region is entire chunk\n")); 253 rv = s; 254 rv->r_flags |= RF_ALLOCATED | flags; 255 rv->r_dev = dev; 256 goto out; 257 } 258 259 /* 260 * If s->r_start < rstart and 261 * s->r_end > rstart + count - 1, then 262 * we need to split the region into three pieces 263 * (the middle one will get returned to the user). 264 * Otherwise, we are allocating at either the 265 * beginning or the end of s, so we only need to 266 * split it in two. The first case requires 267 * two new allocations; the second requires but one. 268 */ 269 rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO); 270 if (rv == 0) 271 goto out; 272 rv->r_start = rstart; 273 rv->r_end = rstart + count - 1; 274 rv->r_flags = flags | RF_ALLOCATED; 275 rv->r_dev = dev; 276 rv->r_rm = rm; 277 278 if (s->r_start < rv->r_start && s->r_end > rv->r_end) { 279 DPRINTF(("splitting region in three parts: " 280 "[%#lx, %#lx]; [%#lx, %#lx]; [%#lx, %#lx]\n", 281 s->r_start, rv->r_start - 1, 282 rv->r_start, rv->r_end, 283 rv->r_end + 1, s->r_end)); 284 /* 285 * We are allocating in the middle. 286 */ 287 r = malloc(sizeof *r, M_RMAN, M_NOWAIT|M_ZERO); 288 if (r == 0) { 289 free(rv, M_RMAN); 290 rv = 0; 291 goto out; 292 } 293 r->r_start = rv->r_end + 1; 294 r->r_end = s->r_end; 295 r->r_flags = s->r_flags; 296 r->r_rm = rm; 297 s->r_end = rv->r_start - 1; 298 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv, 299 r_link); 300 TAILQ_INSERT_AFTER(&rm->rm_list, rv, r, 301 r_link); 302 } else if (s->r_start == rv->r_start) { 303 DPRINTF(("allocating from the beginning\n")); 304 /* 305 * We are allocating at the beginning. 306 */ 307 s->r_start = rv->r_end + 1; 308 TAILQ_INSERT_BEFORE(s, rv, r_link); 309 } else { 310 DPRINTF(("allocating at the end\n")); 311 /* 312 * We are allocating at the end. 313 */ 314 s->r_end = rv->r_start - 1; 315 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv, 316 r_link); 317 } 318 goto out; 319 } 320 } 321 322 /* 323 * Now find an acceptable shared region, if the client's requirements 324 * allow sharing. By our implementation restriction, a candidate 325 * region must match exactly by both size and sharing type in order 326 * to be considered compatible with the client's request. (The 327 * former restriction could probably be lifted without too much 328 * additional work, but this does not seem warranted.) 329 */ 330 DPRINTF(("no unshared regions found\n")); 331 if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0) 332 goto out; 333 334 for (s = r; s; s = TAILQ_NEXT(s, r_link)) { 335 if (s->r_start > end) 336 break; 337 if ((s->r_flags & flags) != flags) 338 continue; 339 rstart = ulmax(s->r_start, start); 340 rend = ulmin(s->r_end, ulmax(start + count - 1, end)); 341 if (s->r_start >= start && s->r_end <= end 342 && (s->r_end - s->r_start + 1) == count && 343 (s->r_start & amask) == 0 && 344 ((s->r_start ^ s->r_end) & bmask) == 0) { 345 rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO); 346 if (rv == 0) 347 goto out; 348 rv->r_start = s->r_start; 349 rv->r_end = s->r_end; 350 rv->r_flags = s->r_flags & 351 (RF_ALLOCATED | RF_SHAREABLE | RF_TIMESHARE); 352 rv->r_dev = dev; 353 rv->r_rm = rm; 354 if (s->r_sharehead == 0) { 355 s->r_sharehead = malloc(sizeof *s->r_sharehead, 356 M_RMAN, M_NOWAIT | M_ZERO); 357 if (s->r_sharehead == 0) { 358 free(rv, M_RMAN); 359 rv = 0; 360 goto out; 361 } 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 392 mtx_unlock(rm->rm_mtx); 393 return (rv); 394 } 395 396 struct resource * 397 rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count, 398 u_int flags, struct device *dev) 399 { 400 401 return (rman_reserve_resource_bound(rm, start, end, count, 0, flags, 402 dev)); 403 } 404 405 static int 406 int_rman_activate_resource(struct rman *rm, struct resource *r, 407 struct resource **whohas) 408 { 409 struct resource *s; 410 int ok; 411 412 /* 413 * If we are not timesharing, then there is nothing much to do. 414 * If we already have the resource, then there is nothing at all to do. 415 * If we are not on a sharing list with anybody else, then there is 416 * little to do. 417 */ 418 if ((r->r_flags & RF_TIMESHARE) == 0 419 || (r->r_flags & RF_ACTIVE) != 0 420 || r->r_sharehead == 0) { 421 r->r_flags |= RF_ACTIVE; 422 return 0; 423 } 424 425 ok = 1; 426 for (s = LIST_FIRST(r->r_sharehead); s && ok; 427 s = LIST_NEXT(s, r_sharelink)) { 428 if ((s->r_flags & RF_ACTIVE) != 0) { 429 ok = 0; 430 *whohas = s; 431 } 432 } 433 if (ok) { 434 r->r_flags |= RF_ACTIVE; 435 return 0; 436 } 437 return EBUSY; 438 } 439 440 int 441 rman_activate_resource(struct resource *r) 442 { 443 int rv; 444 struct resource *whohas; 445 struct rman *rm; 446 447 rm = r->r_rm; 448 mtx_lock(rm->rm_mtx); 449 rv = int_rman_activate_resource(rm, r, &whohas); 450 mtx_unlock(rm->rm_mtx); 451 return rv; 452 } 453 454 int 455 rman_await_resource(struct resource *r, int pri, int timo) 456 { 457 int rv; 458 struct resource *whohas; 459 struct rman *rm; 460 461 rm = r->r_rm; 462 mtx_lock(rm->rm_mtx); 463 for (;;) { 464 rv = int_rman_activate_resource(rm, r, &whohas); 465 if (rv != EBUSY) 466 return (rv); /* returns with mutex held */ 467 468 if (r->r_sharehead == 0) 469 panic("rman_await_resource"); 470 whohas->r_flags |= RF_WANTED; 471 rv = msleep(r->r_sharehead, rm->rm_mtx, pri, "rmwait", timo); 472 if (rv) { 473 mtx_unlock(rm->rm_mtx); 474 return (rv); 475 } 476 } 477 } 478 479 static int 480 int_rman_deactivate_resource(struct resource *r) 481 { 482 483 r->r_flags &= ~RF_ACTIVE; 484 if (r->r_flags & RF_WANTED) { 485 r->r_flags &= ~RF_WANTED; 486 wakeup(r->r_sharehead); 487 } 488 return 0; 489 } 490 491 int 492 rman_deactivate_resource(struct resource *r) 493 { 494 struct rman *rm; 495 496 rm = r->r_rm; 497 mtx_lock(rm->rm_mtx); 498 int_rman_deactivate_resource(r); 499 mtx_unlock(rm->rm_mtx); 500 return 0; 501 } 502 503 static int 504 int_rman_release_resource(struct rman *rm, struct resource *r) 505 { 506 struct resource *s, *t; 507 508 if (r->r_flags & RF_ACTIVE) 509 int_rman_deactivate_resource(r); 510 511 /* 512 * Check for a sharing list first. If there is one, then we don't 513 * have to think as hard. 514 */ 515 if (r->r_sharehead) { 516 /* 517 * If a sharing list exists, then we know there are at 518 * least two sharers. 519 * 520 * If we are in the main circleq, appoint someone else. 521 */ 522 LIST_REMOVE(r, r_sharelink); 523 s = LIST_FIRST(r->r_sharehead); 524 if (r->r_flags & RF_FIRSTSHARE) { 525 s->r_flags |= RF_FIRSTSHARE; 526 TAILQ_INSERT_BEFORE(r, s, r_link); 527 TAILQ_REMOVE(&rm->rm_list, r, r_link); 528 } 529 530 /* 531 * Make sure that the sharing list goes away completely 532 * if the resource is no longer being shared at all. 533 */ 534 if (LIST_NEXT(s, r_sharelink) == 0) { 535 free(s->r_sharehead, M_RMAN); 536 s->r_sharehead = 0; 537 s->r_flags &= ~RF_FIRSTSHARE; 538 } 539 goto out; 540 } 541 542 /* 543 * Look at the adjacent resources in the list and see if our 544 * segment can be merged with any of them. If either of the 545 * resources is allocated or is not exactly adjacent then they 546 * cannot be merged with our segment. 547 */ 548 s = TAILQ_PREV(r, resource_head, r_link); 549 if (s != NULL && ((s->r_flags & RF_ALLOCATED) != 0 || 550 s->r_end + 1 != r->r_start)) 551 s = NULL; 552 t = TAILQ_NEXT(r, r_link); 553 if (t != NULL && ((t->r_flags & RF_ALLOCATED) != 0 || 554 r->r_end + 1 != t->r_start)) 555 t = NULL; 556 557 if (s != NULL && t != NULL) { 558 /* 559 * Merge all three segments. 560 */ 561 s->r_end = t->r_end; 562 TAILQ_REMOVE(&rm->rm_list, r, r_link); 563 TAILQ_REMOVE(&rm->rm_list, t, r_link); 564 free(t, M_RMAN); 565 } else if (s != NULL) { 566 /* 567 * Merge previous segment with ours. 568 */ 569 s->r_end = r->r_end; 570 TAILQ_REMOVE(&rm->rm_list, r, r_link); 571 } else if (t != NULL) { 572 /* 573 * Merge next segment with ours. 574 */ 575 t->r_start = r->r_start; 576 TAILQ_REMOVE(&rm->rm_list, r, r_link); 577 } else { 578 /* 579 * At this point, we know there is nothing we 580 * can potentially merge with, because on each 581 * side, there is either nothing there or what is 582 * there is still allocated. In that case, we don't 583 * want to remove r from the list; we simply want to 584 * change it to an unallocated region and return 585 * without freeing anything. 586 */ 587 r->r_flags &= ~RF_ALLOCATED; 588 return 0; 589 } 590 591 out: 592 free(r, M_RMAN); 593 return 0; 594 } 595 596 int 597 rman_release_resource(struct resource *r) 598 { 599 int rv; 600 struct rman *rm = r->r_rm; 601 602 mtx_lock(rm->rm_mtx); 603 rv = int_rman_release_resource(rm, r); 604 mtx_unlock(rm->rm_mtx); 605 return (rv); 606 } 607 608 uint32_t 609 rman_make_alignment_flags(uint32_t size) 610 { 611 int i; 612 613 /* 614 * Find the hightest bit set, and add one if more than one bit 615 * set. We're effectively computing the ceil(log2(size)) here. 616 */ 617 for (i = 31; i > 0; i--) 618 if ((1 << i) & size) 619 break; 620 if (~(1 << i) & size) 621 i++; 622 623 return(RF_ALIGNMENT_LOG2(i)); 624 } 625 626 u_long 627 rman_get_start(struct resource *r) 628 { 629 return (r->r_start); 630 } 631 632 u_long 633 rman_get_end(struct resource *r) 634 { 635 return (r->r_end); 636 } 637 638 u_long 639 rman_get_size(struct resource *r) 640 { 641 return (r->r_end - r->r_start + 1); 642 } 643 644 u_int 645 rman_get_flags(struct resource *r) 646 { 647 return (r->r_flags); 648 } 649 650 void 651 rman_set_virtual(struct resource *r, void *v) 652 { 653 r->r_virtual = v; 654 } 655 656 void * 657 rman_get_virtual(struct resource *r) 658 { 659 return (r->r_virtual); 660 } 661 662 void 663 rman_set_bustag(struct resource *r, bus_space_tag_t t) 664 { 665 r->r_bustag = t; 666 } 667 668 bus_space_tag_t 669 rman_get_bustag(struct resource *r) 670 { 671 return (r->r_bustag); 672 } 673 674 void 675 rman_set_bushandle(struct resource *r, bus_space_handle_t h) 676 { 677 r->r_bushandle = h; 678 } 679 680 bus_space_handle_t 681 rman_get_bushandle(struct resource *r) 682 { 683 return (r->r_bushandle); 684 } 685 686 void 687 rman_set_rid(struct resource *r, int rid) 688 { 689 r->r_rid = rid; 690 } 691 692 void 693 rman_set_start(struct resource *r, u_long start) 694 { 695 r->r_start = start; 696 } 697 698 void 699 rman_set_end(struct resource *r, u_long end) 700 { 701 r->r_end = end; 702 } 703 704 int 705 rman_get_rid(struct resource *r) 706 { 707 return (r->r_rid); 708 } 709 710 struct device * 711 rman_get_device(struct resource *r) 712 { 713 return (r->r_dev); 714 } 715