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