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/mutex.h>
  66 #include <sys/bus.h>            /* XXX debugging */
  67 #include <machine/bus.h>
  68 #include <sys/rman.h>
  69
  70 #ifdef RMAN_DEBUG
  71 #define DPRINTF(params) printf##params
  72 #else
  73 #define DPRINTF(params)
  74 #endif
  75
  76 static MALLOC_DEFINE(M_RMAN, "rman", "Resource manager");
  77
  78 struct  rman_head rman_head;
  79 static  struct mtx rman_mtx; /* mutex to protect rman_head */
  80 static  int int_rman_activate_resource(struct rman *rm, struct resource *r,
  81                                        struct resource **whohas);
  82 static  int int_rman_deactivate_resource(struct resource *r);
  83 static  int int_rman_release_resource(struct rman *rm, struct resource *r);
  84
  85 int
  86 rman_init(struct rman *rm)
  87 {
  88         static int once;
  89
  90         if (once == 0) {
  91                 once = 1;
  92                 TAILQ_INIT(&rman_head);
  93                 mtx_init(&rman_mtx, "rman head", MTX_DEF);
  94         }
  95
  96         if (rm->rm_type == RMAN_UNINIT)
  97                 panic("rman_init");
  98         if (rm->rm_type == RMAN_GAUGE)
  99                 panic("implement RMAN_GAUGE");
 100
 101         TAILQ_INIT(&rm->rm_list);
 102         rm->rm_mtx = malloc(sizeof *rm->rm_mtx, M_RMAN, M_NOWAIT | M_ZERO);
 103         if (rm->rm_mtx == 0)
 104                 return ENOMEM;
 105         mtx_init(rm->rm_mtx, "rman", MTX_DEF);
 106
 107         mtx_lock(&rman_mtx);
 108         TAILQ_INSERT_TAIL(&rman_head, rm, rm_link);
 109         mtx_unlock(&rman_mtx);
 110         return 0;
 111 }
 112
 113 /*
 114  * NB: this interface is not robust against programming errors which
 115  * add multiple copies of the same region.
 116  */
 117 int
 118 rman_manage_region(struct rman *rm, u_long start, u_long end)
 119 {
 120         struct resource *r, *s;
 121
 122         r = malloc(sizeof *r, M_RMAN, M_NOWAIT | M_ZERO);
 123         if (r == 0)
 124                 return ENOMEM;
 125         r->r_start = start;
 126         r->r_end = end;
 127         r->r_rm = rm;
 128
 129         mtx_lock(rm->rm_mtx);
 130         for (s = TAILQ_FIRST(&rm->rm_list);
 131              s && s->r_end < r->r_start;
 132              s = TAILQ_NEXT(s, r_link))
 133                 ;
 134
 135         if (s == NULL) {
 136                 TAILQ_INSERT_TAIL(&rm->rm_list, r, r_link);
 137         } else {
 138                 TAILQ_INSERT_BEFORE(s, r, r_link);
 139         }
 140
 141         mtx_unlock(rm->rm_mtx);
 142         return 0;
 143 }
 144
 145 int
 146 rman_fini(struct rman *rm)
 147 {
 148         struct resource *r;
 149
 150         mtx_lock(rm->rm_mtx);
 151         TAILQ_FOREACH(r, &rm->rm_list, r_link) {
 152                 if (r->r_flags & RF_ALLOCATED) {
 153                         mtx_unlock(rm->rm_mtx);
 154                         return EBUSY;
 155                 }
 156         }
 157
 158         /*
 159          * There really should only be one of these if we are in this
 160          * state and the code is working properly, but it can't hurt.
 161          */
 162         while (!TAILQ_EMPTY(&rm->rm_list)) {
 163                 r = TAILQ_FIRST(&rm->rm_list);
 164                 TAILQ_REMOVE(&rm->rm_list, r, r_link);
 165                 free(r, M_RMAN);
 166         }
 167         mtx_unlock(rm->rm_mtx);
 168         mtx_lock(&rman_mtx);
 169         TAILQ_REMOVE(&rman_head, rm, rm_link);
 170         mtx_unlock(&rman_mtx);
 171         mtx_destroy(rm->rm_mtx);
 172         free(rm->rm_mtx, M_RMAN);
 173
 174         return 0;
 175 }
 176
 177 struct resource *
 178 rman_reserve_resource_bound(struct rman *rm, u_long start, u_long end,
 179                       u_long count, u_long bound,  u_int flags,
 180                       struct device *dev)
 181 {
 182         u_int   want_activate;
 183         struct  resource *r, *s, *rv;
 184         u_long  rstart, rend, amask, bmask;
 185
 186         rv = 0;
 187
 188         DPRINTF(("rman_reserve_resource: <%s> request: [%#lx, %#lx], length "
 189                "%#lx, flags %u, device %s\n", rm->rm_descr, start, end, count,
 190                flags, dev == NULL ? "<null>" : device_get_nameunit(dev)));
 191         want_activate = (flags & RF_ACTIVE);
 192         flags &= ~RF_ACTIVE;
 193
 194         mtx_lock(rm->rm_mtx);
 195
 196         for (r = TAILQ_FIRST(&rm->rm_list);
 197              r && r->r_end < start;
 198              r = TAILQ_NEXT(r, r_link))
 199                 ;
 200
 201         if (r == NULL) {
 202                 DPRINTF(("could not find a region\n"));
 203                 goto out;
 204         }
 205
 206         amask = (1ul << RF_ALIGNMENT(flags)) - 1;
 207         /* If bound is 0, bmask will also be 0 */
 208         bmask = ~(bound - 1);
 209         /*
 210          * First try to find an acceptable totally-unshared region.
 211          */
 212         for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
 213                 DPRINTF(("considering [%#lx, %#lx]\n", s->r_start, s->r_end));
 214                 if (s->r_start > end) {
 215                         DPRINTF(("s->r_start (%#lx) > end (%#lx)\n", s->r_start, end));
 216                         break;
 217                 }
 218                 if (s->r_flags & RF_ALLOCATED) {
 219                         DPRINTF(("region is allocated\n"));
 220                         continue;
 221                 }
 222                 rstart = ulmax(s->r_start, start);
 223                 /*
 224                  * Try to find a region by adjusting to boundary and alignment
 225                  * until both conditions are satisfied. This is not an optimal
 226                  * algorithm, but in most cases it isn't really bad, either.
 227                  */
 228                 do {
 229                         rstart = (rstart + amask) & ~amask;
 230                         if (((rstart ^ (rstart + count)) & bmask) != 0)
 231                                 rstart += bound - (rstart & ~bmask);
 232                 } while ((rstart & amask) != 0 && rstart < end &&
 233                     rstart < s->r_end);
 234                 rend = ulmin(s->r_end, ulmax(rstart + count, end));
 235                 DPRINTF(("truncated region: [%#lx, %#lx]; size %#lx (requested %#lx)\n",
 236                        rstart, rend, (rend - rstart + 1), count));
 237
 238                 if ((rend - rstart + 1) >= count) {
 239                         DPRINTF(("candidate region: [%#lx, %#lx], size %#lx\n",
 240                                rend, rstart, (rend - rstart + 1)));
 241                         if ((s->r_end - s->r_start + 1) == count) {
 242                                 DPRINTF(("candidate region is entire chunk\n"));
 243                                 rv = s;
 244                                 rv->r_flags |= RF_ALLOCATED | flags;
 245                                 rv->r_dev = dev;
 246                                 goto out;
 247                         }
 248
 249                         /*
 250                          * If s->r_start < rstart and
 251                          *    s->r_end > rstart + count - 1, then
 252                          * we need to split the region into three pieces
 253                          * (the middle one will get returned to the user).
 254                          * Otherwise, we are allocating at either the
 255                          * beginning or the end of s, so we only need to
 256                          * split it in two.  The first case requires
 257                          * two new allocations; the second requires but one.
 258                          */
 259                         rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO);
 260                         if (rv == 0)
 261                                 goto out;
 262                         rv->r_start = rstart;
 263                         rv->r_end = rstart + count - 1;
 264                         rv->r_flags = flags | RF_ALLOCATED;
 265                         rv->r_dev = dev;
 266                         rv->r_rm = rm;
 267
 268                         if (s->r_start < rv->r_start && s->r_end > rv->r_end) {
 269                                 DPRINTF(("splitting region in three parts: "
 270                                        "[%#lx, %#lx]; [%#lx, %#lx]; [%#lx, %#lx]\n",
 271                                        s->r_start, rv->r_start - 1,
 272                                        rv->r_start, rv->r_end,
 273                                        rv->r_end + 1, s->r_end));
 274                                 /*
 275                                  * We are allocating in the middle.
 276                                  */
 277                                 r = malloc(sizeof *r, M_RMAN, M_NOWAIT|M_ZERO);
 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_rm = rm;
 287                                 s->r_end = rv->r_start - 1;
 288                                 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
 289                                                      r_link);
 290                                 TAILQ_INSERT_AFTER(&rm->rm_list, rv, r,
 291                                                      r_link);
 292                         } else if (s->r_start == rv->r_start) {
 293                                 DPRINTF(("allocating from the beginning\n"));
 294                                 /*
 295                                  * We are allocating at the beginning.
 296                                  */
 297                                 s->r_start = rv->r_end + 1;
 298                                 TAILQ_INSERT_BEFORE(s, rv, r_link);
 299                         } else {
 300                                 DPRINTF(("allocating at the end\n"));
 301                                 /*
 302                                  * We are allocating at the end.
 303                                  */
 304                                 s->r_end = rv->r_start - 1;
 305                                 TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
 306                                                      r_link);
 307                         }
 308                         goto out;
 309                 }
 310         }
 311
 312         /*
 313          * Now find an acceptable shared region, if the client's requirements
 314          * allow sharing.  By our implementation restriction, a candidate
 315          * region must match exactly by both size and sharing type in order
 316          * to be considered compatible with the client's request.  (The
 317          * former restriction could probably be lifted without too much
 318          * additional work, but this does not seem warranted.)
 319          */
 320         DPRINTF(("no unshared regions found\n"));
 321         if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0)
 322                 goto out;
 323
 324         for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
 325                 if (s->r_start > end)
 326                         break;
 327                 if ((s->r_flags & flags) != flags)
 328                         continue;
 329                 rstart = ulmax(s->r_start, start);
 330                 rend = ulmin(s->r_end, ulmax(start + count, end));
 331                 if (s->r_start >= start && s->r_end <= end
 332                     && (s->r_end - s->r_start + 1) == count &&
 333                     (s->r_start & amask) == 0 &&
 334                     ((s->r_start ^ s->r_end) & bmask) == 0) {
 335                         rv = malloc(sizeof *rv, M_RMAN, M_NOWAIT | M_ZERO);
 336                         if (rv == 0)
 337                                 goto out;
 338                         rv->r_start = s->r_start;
 339                         rv->r_end = s->r_end;
 340                         rv->r_flags = s->r_flags &
 341                                 (RF_ALLOCATED | RF_SHAREABLE | RF_TIMESHARE);
 342                         rv->r_dev = dev;
 343                         rv->r_rm = rm;
 344                         if (s->r_sharehead == 0) {
 345                                 s->r_sharehead = malloc(sizeof *s->r_sharehead,
 346                                                 M_RMAN, M_NOWAIT | M_ZERO);
 347                                 if (s->r_sharehead == 0) {
 348                                         free(rv, M_RMAN);
 349                                         rv = 0;
 350                                         goto out;
 351                                 }
 352                                 LIST_INIT(s->r_sharehead);
 353                                 LIST_INSERT_HEAD(s->r_sharehead, s,
 354                                                  r_sharelink);
 355                                 s->r_flags |= RF_FIRSTSHARE;
 356                         }
 357                         rv->r_sharehead = s->r_sharehead;
 358                         LIST_INSERT_HEAD(s->r_sharehead, rv, r_sharelink);
 359                         goto out;
 360                 }
 361         }
 362
 363         /*
 364          * We couldn't find anything.
 365          */
 366 out:
 367         /*
 368          * If the user specified RF_ACTIVE in the initial flags,
 369          * which is reflected in `want_activate', we attempt to atomically
 370          * activate the resource.  If this fails, we release the resource
 371          * and indicate overall failure.  (This behavior probably doesn't
 372          * make sense for RF_TIMESHARE-type resources.)
 373          */
 374         if (rv && want_activate) {
 375                 struct resource *whohas;
 376                 if (int_rman_activate_resource(rm, rv, &whohas)) {
 377                         int_rman_release_resource(rm, rv);
 378                         rv = 0;
 379                 }
 380         }
 381
 382         mtx_unlock(rm->rm_mtx);
 383         return (rv);
 384 }
 385
 386 struct resource *
 387 rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
 388                       u_int flags, struct device *dev)
 389 {
 390
 391         return (rman_reserve_resource_bound(rm, start, end, count, 0, flags,
 392             dev));
 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         struct rman *rm;
 436
 437         rm = r->r_rm;
 438         mtx_lock(rm->rm_mtx);
 439         rv = int_rman_activate_resource(rm, r, &whohas);
 440         mtx_unlock(rm->rm_mtx);
 441         return rv;
 442 }
 443
 444 int
 445 rman_await_resource(struct resource *r, int pri, int timo)
 446 {
 447         int     rv;
 448         struct  resource *whohas;
 449         struct  rman *rm;
 450
 451         rm = r->r_rm;
 452         mtx_lock(rm->rm_mtx);
 453         for (;;) {
 454                 rv = int_rman_activate_resource(rm, r, &whohas);
 455                 if (rv != EBUSY)
 456                         return (rv);    /* returns with mutex held */
 457
 458                 if (r->r_sharehead == 0)
 459                         panic("rman_await_resource");
 460                 whohas->r_flags |= RF_WANTED;
 461                 rv = msleep(r->r_sharehead, rm->rm_mtx, pri, "rmwait", timo);
 462                 if (rv) {
 463                         mtx_unlock(rm->rm_mtx);
 464                         return (rv);
 465                 }
 466         }
 467 }
 468
 469 static int
 470 int_rman_deactivate_resource(struct resource *r)
 471 {
 472         struct  rman *rm;
 473
 474         rm = r->r_rm;
 475         r->r_flags &= ~RF_ACTIVE;
 476         if (r->r_flags & RF_WANTED) {
 477                 r->r_flags &= ~RF_WANTED;
 478                 wakeup(r->r_sharehead);
 479         }
 480         return 0;
 481 }
 482
 483 int
 484 rman_deactivate_resource(struct resource *r)
 485 {
 486         struct  rman *rm;
 487
 488         rm = r->r_rm;
 489         mtx_lock(rm->rm_mtx);
 490         int_rman_deactivate_resource(r);
 491         mtx_unlock(rm->rm_mtx);
 492         return 0;
 493 }
 494
 495 static int
 496 int_rman_release_resource(struct rman *rm, struct resource *r)
 497 {
 498         struct  resource *s, *t;
 499
 500         if (r->r_flags & RF_ACTIVE)
 501                 int_rman_deactivate_resource(r);
 502
 503         /*
 504          * Check for a sharing list first.  If there is one, then we don't
 505          * have to think as hard.
 506          */
 507         if (r->r_sharehead) {
 508                 /*
 509                  * If a sharing list exists, then we know there are at
 510                  * least two sharers.
 511                  *
 512                  * If we are in the main circleq, appoint someone else.
 513                  */
 514                 LIST_REMOVE(r, r_sharelink);
 515                 s = LIST_FIRST(r->r_sharehead);
 516                 if (r->r_flags & RF_FIRSTSHARE) {
 517                         s->r_flags |= RF_FIRSTSHARE;
 518                         TAILQ_INSERT_BEFORE(r, s, r_link);
 519                         TAILQ_REMOVE(&rm->rm_list, r, r_link);
 520                 }
 521
 522                 /*
 523                  * Make sure that the sharing list goes away completely
 524                  * if the resource is no longer being shared at all.
 525                  */
 526                 if (LIST_NEXT(s, r_sharelink) == 0) {
 527                         free(s->r_sharehead, M_RMAN);
 528                         s->r_sharehead = 0;
 529                         s->r_flags &= ~RF_FIRSTSHARE;
 530                 }
 531                 goto out;
 532         }
 533
 534         /*
 535          * Look at the adjacent resources in the list and see if our
 536          * segment can be merged with any of them.
 537          */
 538         s = TAILQ_PREV(r, resource_head, r_link);
 539         t = TAILQ_NEXT(r, r_link);
 540
 541         if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0
 542             && t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
 543                 /*
 544                  * Merge all three segments.
 545                  */
 546                 s->r_end = t->r_end;
 547                 TAILQ_REMOVE(&rm->rm_list, r, r_link);
 548                 TAILQ_REMOVE(&rm->rm_list, t, r_link);
 549                 free(t, M_RMAN);
 550         } else if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0) {
 551                 /*
 552                  * Merge previous segment with ours.
 553                  */
 554                 s->r_end = r->r_end;
 555                 TAILQ_REMOVE(&rm->rm_list, r, r_link);
 556         } else if (t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
 557                 /*
 558                  * Merge next segment with ours.
 559                  */
 560                 t->r_start = r->r_start;
 561                 TAILQ_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         mtx_lock(rm->rm_mtx);
 588         rv = int_rman_release_resource(rm, r);
 589         mtx_unlock(rm->rm_mtx);
 590         return (rv);
 591 }
 592
 593 uint32_t
 594 rman_make_alignment_flags(uint32_t size)
 595 {
 596         int     i;
 597
 598         /*
 599          * Find the hightest bit set, and add one if more than one bit
 600          * set.  We're effectively computing the ceil(log2(size)) here.
 601          */
 602         for (i = 31; i > 0; i--)
 603                 if ((1 << i) & size)
 604                         break;
 605         if (~(1 << i) & size)
 606                 i++;
 607
 608         return(RF_ALIGNMENT_LOG2(i));
 609 }