sys/kern/subr_unit.c

   1 /*-
   2  * Copyright (c) 2004 Poul-Henning Kamp
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  *
  28  *
  29  * Unit number allocation functions.
  30  *
  31  * These functions implement a mixed run-length/bitmap management of unit
  32  * number spaces in a very memory efficient manner.
  33  *
  34  * Allocation policy is always lowest free number first.
  35  *
  36  * A return value of -1 signals that no more unit numbers are available.
  37  *
  38  * There is no cost associated with the range of unitnumbers, so unless
  39  * the resource really is finite, specify INT_MAX to new_unrhdr() and
  40  * forget about checking the return value.
  41  *
  42  * If a mutex is not provided when the unit number space is created, a
  43  * default global mutex is used.  The advantage to passing a mutex in, is
  44  * that the the alloc_unrl() function can be called with the mutex already
  45  * held (it will not be released by alloc_unrl()).
  46  *
  47  * The allocation function alloc_unr{l}() never sleeps (but it may block on
  48  * the mutex of course).
  49  *
  50  * Freeing a unit number may require allocating memory, and can therefore
  51  * sleep so the free_unr() function does not come in a pre-locked variant.
  52  *
  53  * A userland test program is included.
  54  *
  55  * Memory usage is a very complex function of the the exact allocation
  56  * pattern, but always very compact:
  57  *    * For the very typical case where a single unbroken run of unit
  58  *      numbers are allocated 44 bytes are used on i386.
  59  *    * For a unit number space of 1000 units and the random pattern
  60  *      in the usermode test program included, the worst case usage
  61  *      was 252 bytes on i386 for 500 allocated and 500 free units.
  62  *    * For a unit number space of 10000 units and the random pattern
  63  *      in the usermode test program included, the worst case usage
  64  *      was 798 bytes on i386 for 5000 allocated and 5000 free units.
  65  *    * The worst case is where every other unit number is allocated and
  66  *      the the rest are free.  In that case 44 + N/4 bytes are used where
  67  *      N is the number of the highest unit allocated.
  68  */
  69
  70 #include <sys/types.h>
  71 #include <sys/queue.h>
  72 #include <sys/bitstring.h>
  73
  74 #ifdef _KERNEL
  75
  76 #include <sys/param.h>
  77 #include <sys/malloc.h>
  78 #include <sys/kernel.h>
  79 #include <sys/systm.h>
  80 #include <sys/limits.h>
  81 #include <sys/lock.h>
  82 #include <sys/mutex.h>
  83
  84 /*
  85  * In theory it would be smarter to allocate the individual blocks
  86  * with the zone allocator, but at this time the expectation is that
  87  * there will typically not even be enough allocations to fill a single
  88  * page, so we stick with malloc for now.
  89  */
  90 static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
  91
  92 #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
  93 #define Free(foo) free(foo, M_UNIT)
  94
  95 static struct mtx unitmtx;
  96
  97 MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF);
  98
  99 #else /* ...USERLAND */
 100
 101 #include <stdio.h>
 102 #include <stdlib.h>
 103 #include <string.h>
 104
 105 #define KASSERT(cond, arg) \
 106         do { \
 107                 if (!(cond)) { \
 108                         printf arg; \
 109                         abort(); \
 110                 } \
 111         } while (0)
 112
 113 static int no_alloc;
 114 #define Malloc(foo) _Malloc(foo, __LINE__)
 115 static void *
 116 _Malloc(size_t foo, int line)
 117 {
 118
 119         KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
 120         return (calloc(foo, 1));
 121 }
 122 #define Free(foo) free(foo)
 123
 124 struct unrhdr;
 125
 126
 127 struct mtx {
 128         int     state;
 129 } unitmtx;
 130
 131 static void
 132 mtx_lock(struct mtx *mp)
 133 {
 134         KASSERT(mp->state == 0, ("mutex already locked"));
 135         mp->state = 1;
 136 }
 137
 138 static void
 139 mtx_unlock(struct mtx *mp)
 140 {
 141         KASSERT(mp->state == 1, ("mutex not locked"));
 142         mp->state = 0;
 143 }
 144
 145 #define MA_OWNED        9
 146
 147 static void
 148 mtx_assert(struct mtx *mp, int flag)
 149 {
 150         if (flag == MA_OWNED) {
 151                 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
 152         }
 153 }
 154
 155 #define CTASSERT(foo)
 156
 157 #endif /* USERLAND */
 158
 159 /*
 160  * This is our basic building block.
 161  *
 162  * It can be used in three different ways depending on the value of the ptr
 163  * element:
 164  *     If ptr is NULL, it represents a run of free items.
 165  *     If ptr points to the unrhdr it represents a run of allocated items.
 166  *     Otherwise it points to an bitstring of allocated items.
 167  *
 168  * For runs the len field is the length of the run.
 169  * For bitmaps the len field represents the number of allocated items.
 170  *
 171  * The bitmap is the same size as struct unr to optimize memory management.
 172  */
 173 struct unr {
 174         TAILQ_ENTRY(unr)        list;
 175         u_int                   len;
 176         void                    *ptr;
 177 };
 178
 179 struct unrb {
 180         u_char                  busy;
 181         bitstr_t                map[sizeof(struct unr) - 1];
 182 };
 183
 184 CTASSERT(sizeof(struct unr) == sizeof(struct unrb));
 185
 186 /* Number of bits in the bitmap */
 187 #define NBITS   ((int)sizeof(((struct unrb *)NULL)->map) * 8)
 188
 189 /* Header element for a unr number space. */
 190
 191 struct unrhdr {
 192         TAILQ_HEAD(unrhd,unr)   head;
 193         u_int                   low;    /* Lowest item */
 194         u_int                   high;   /* Highest item */
 195         u_int                   busy;   /* Count of allocated items */
 196         u_int                   alloc;  /* Count of memory allocations */
 197         u_int                   first;  /* items in allocated from start */
 198         u_int                   last;   /* items free at end */
 199         struct mtx              *mtx;
 200         TAILQ_HEAD(unrfr,unr)   ppfree; /* Items to be freed after mtx
 201                                            lock dropped */
 202 };
 203
 204
 205 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
 206 /*
 207  * Consistency check function.
 208  *
 209  * Checks the internal consistency as well as we can.
 210  *
 211  * Called at all boundaries of this API.
 212  */
 213 static void
 214 check_unrhdr(struct unrhdr *uh, int line)
 215 {
 216         struct unr *up;
 217         struct unrb *ub;
 218         u_int x, y, z, w;
 219
 220         y = uh->first;
 221         z = 0;
 222         TAILQ_FOREACH(up, &uh->head, list) {
 223                 z++;
 224                 if (up->ptr != uh && up->ptr != NULL) {
 225                         ub = up->ptr;
 226                         KASSERT (up->len <= NBITS,
 227                             ("UNR inconsistency: len %u max %d (line %d)\n",
 228                             up->len, NBITS, line));
 229                         z++;
 230                         w = 0;
 231                         for (x = 0; x < up->len; x++)
 232                                 if (bit_test(ub->map, x))
 233                                         w++;
 234                         KASSERT (w == ub->busy,
 235                             ("UNR inconsistency: busy %u found %u (line %d)\n",
 236                             ub->busy, w, line));
 237                         y += w;
 238                 } else if (up->ptr != NULL)
 239                         y += up->len;
 240         }
 241         KASSERT (y == uh->busy,
 242             ("UNR inconsistency: items %u found %u (line %d)\n",
 243             uh->busy, y, line));
 244         KASSERT (z == uh->alloc,
 245             ("UNR inconsistency: chunks %u found %u (line %d)\n",
 246             uh->alloc, z, line));
 247 }
 248
 249 #else
 250
 251 static __inline void
 252 check_unrhdr(struct unrhdr *uh, int line)
 253 {
 254
 255 }
 256
 257 #endif
 258
 259
 260 /*
 261  * Userland memory management.  Just use calloc and keep track of how
 262  * many elements we have allocated for check_unrhdr().
 263  */
 264
 265 static __inline void *
 266 new_unr(struct unrhdr *uh, void **p1, void **p2)
 267 {
 268         void *p;
 269
 270         uh->alloc++;
 271         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
 272         if (*p1 != NULL) {
 273                 p = *p1;
 274                 *p1 = NULL;
 275                 return (p);
 276         } else {
 277                 p = *p2;
 278                 *p2 = NULL;
 279                 return (p);
 280         }
 281 }
 282
 283 static __inline void
 284 delete_unr(struct unrhdr *uh, void *ptr)
 285 {
 286         struct unr *up;
 287
 288         uh->alloc--;
 289         up = ptr;
 290         TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
 291 }
 292
 293 void
 294 clean_unrhdrl(struct unrhdr *uh)
 295 {
 296         struct unr *up;
 297
 298         mtx_assert(uh->mtx, MA_OWNED);
 299         while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
 300                 TAILQ_REMOVE(&uh->ppfree, up, list);
 301                 mtx_unlock(uh->mtx);
 302                 Free(up);
 303                 mtx_lock(uh->mtx);
 304         }
 305
 306 }
 307
 308 void
 309 clean_unrhdr(struct unrhdr *uh)
 310 {
 311
 312         mtx_lock(uh->mtx);
 313         clean_unrhdrl(uh);
 314         mtx_unlock(uh->mtx);
 315 }
 316
 317 /*
 318  * Allocate a new unrheader set.
 319  *
 320  * Highest and lowest valid values given as paramters.
 321  */
 322
 323 struct unrhdr *
 324 new_unrhdr(int low, int high, struct mtx *mutex)
 325 {
 326         struct unrhdr *uh;
 327
 328         KASSERT(low <= high,
 329             ("UNR: use error: new_unrhdr(%u, %u)", low, high));
 330         uh = Malloc(sizeof *uh);
 331         if (mutex != NULL)
 332                 uh->mtx = mutex;
 333         else
 334                 uh->mtx = &unitmtx;
 335         TAILQ_INIT(&uh->head);
 336         TAILQ_INIT(&uh->ppfree);
 337         uh->low = low;
 338         uh->high = high;
 339         uh->first = 0;
 340         uh->last = 1 + (high - low);
 341         check_unrhdr(uh, __LINE__);
 342         return (uh);
 343 }
 344
 345 void
 346 delete_unrhdr(struct unrhdr *uh)
 347 {
 348
 349         check_unrhdr(uh, __LINE__);
 350         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
 351         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
 352         KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
 353             ("unrhdr has postponed item for free"));
 354         Free(uh);
 355 }
 356
 357 static __inline int
 358 is_bitmap(struct unrhdr *uh, struct unr *up)
 359 {
 360         return (up->ptr != uh && up->ptr != NULL);
 361 }
 362
 363 /*
 364  * Look for sequence of items which can be combined into a bitmap, if
 365  * multiple are present, take the one which saves most memory.
 366  *
 367  * Return (1) if a sequence was found to indicate that another call
 368  * might be able to do more.  Return (0) if we found no suitable sequence.
 369  *
 370  * NB: called from alloc_unr(), no new memory allocation allowed.
 371  */
 372 static int
 373 optimize_unr(struct unrhdr *uh)
 374 {
 375         struct unr *up, *uf, *us;
 376         struct unrb *ub, *ubf;
 377         u_int a, l, ba;
 378
 379         /*
 380          * Look for the run of items (if any) which when collapsed into
 381          * a bitmap would save most memory.
 382          */
 383         us = NULL;
 384         ba = 0;
 385         TAILQ_FOREACH(uf, &uh->head, list) {
 386                 if (uf->len >= NBITS)
 387                         continue;
 388                 a = 1;
 389                 if (is_bitmap(uh, uf))
 390                         a++;
 391                 l = uf->len;
 392                 up = uf;
 393                 while (1) {
 394                         up = TAILQ_NEXT(up, list);
 395                         if (up == NULL)
 396                                 break;
 397                         if ((up->len + l) > NBITS)
 398                                 break;
 399                         a++;
 400                         if (is_bitmap(uh, up))
 401                                 a++;
 402                         l += up->len;
 403                 }
 404                 if (a > ba) {
 405                         ba = a;
 406                         us = uf;
 407                 }
 408         }
 409         if (ba < 3)
 410                 return (0);
 411
 412         /*
 413          * If the first element is not a bitmap, make it one.
 414          * Trying to do so without allocating more memory complicates things
 415          * a bit
 416          */
 417         if (!is_bitmap(uh, us)) {
 418                 uf = TAILQ_NEXT(us, list);
 419                 TAILQ_REMOVE(&uh->head, us, list);
 420                 a = us->len;
 421                 l = us->ptr == uh ? 1 : 0;
 422                 ub = (void *)us;
 423                 ub->busy = 0;
 424                 if (l) {
 425                         bit_nset(ub->map, 0, a);
 426                         ub->busy += a;
 427                 } else {
 428                         bit_nclear(ub->map, 0, a);
 429                 }
 430                 if (!is_bitmap(uh, uf)) {
 431                         if (uf->ptr == NULL) {
 432                                 bit_nclear(ub->map, a, a + uf->len - 1);
 433                         } else {
 434                                 bit_nset(ub->map, a, a + uf->len - 1);
 435                                 ub->busy += uf->len;
 436                         }
 437                         uf->ptr = ub;
 438                         uf->len += a;
 439                         us = uf;
 440                 } else {
 441                         ubf = uf->ptr;
 442                         for (l = 0; l < uf->len; l++, a++) {
 443                                 if (bit_test(ubf->map, l)) {
 444                                         bit_set(ub->map, a);
 445                                         ub->busy++;
 446                                 } else {
 447                                         bit_clear(ub->map, a);
 448                                 }
 449                         }
 450                         uf->len = a;
 451                         delete_unr(uh, uf->ptr);
 452                         uf->ptr = ub;
 453                         us = uf;
 454                 }
 455         }
 456         ub = us->ptr;
 457         while (1) {
 458                 uf = TAILQ_NEXT(us, list);
 459                 if (uf == NULL)
 460                         return (1);
 461                 if (uf->len + us->len > NBITS)
 462                         return (1);
 463                 if (uf->ptr == NULL) {
 464                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
 465                         us->len += uf->len;
 466                         TAILQ_REMOVE(&uh->head, uf, list);
 467                         delete_unr(uh, uf);
 468                 } else if (uf->ptr == uh) {
 469                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
 470                         ub->busy += uf->len;
 471                         us->len += uf->len;
 472                         TAILQ_REMOVE(&uh->head, uf, list);
 473                         delete_unr(uh, uf);
 474                 } else {
 475                         ubf = uf->ptr;
 476                         for (l = 0; l < uf->len; l++, us->len++) {
 477                                 if (bit_test(ubf->map, l)) {
 478                                         bit_set(ub->map, us->len);
 479                                         ub->busy++;
 480                                 } else {
 481                                         bit_clear(ub->map, us->len);
 482                                 }
 483                         }
 484                         TAILQ_REMOVE(&uh->head, uf, list);
 485                         delete_unr(uh, ubf);
 486                         delete_unr(uh, uf);
 487                 }
 488         }
 489 }
 490
 491 /*
 492  * See if a given unr should be collapsed with a neighbor.
 493  *
 494  * NB: called from alloc_unr(), no new memory allocation allowed.
 495  */
 496 static void
 497 collapse_unr(struct unrhdr *uh, struct unr *up)
 498 {
 499         struct unr *upp;
 500         struct unrb *ub;
 501
 502         /* If bitmap is all set or clear, change it to runlength */
 503         if (is_bitmap(uh, up)) {
 504                 ub = up->ptr;
 505                 if (ub->busy == up->len) {
 506                         delete_unr(uh, up->ptr);
 507                         up->ptr = uh;
 508                 } else if (ub->busy == 0) {
 509                         delete_unr(uh, up->ptr);
 510                         up->ptr = NULL;
 511                 }
 512         }
 513
 514         /* If nothing left in runlength, delete it */
 515         if (up->len == 0) {
 516                 upp = TAILQ_PREV(up, unrhd, list);
 517                 if (upp == NULL)
 518                         upp = TAILQ_NEXT(up, list);
 519                 TAILQ_REMOVE(&uh->head, up, list);
 520                 delete_unr(uh, up);
 521                 up = upp;
 522         }
 523
 524         /* If we have "hot-spot" still, merge with neighbor if possible */
 525         if (up != NULL) {
 526                 upp = TAILQ_PREV(up, unrhd, list);
 527                 if (upp != NULL && up->ptr == upp->ptr) {
 528                         up->len += upp->len;
 529                         TAILQ_REMOVE(&uh->head, upp, list);
 530                         delete_unr(uh, upp);
 531                         }
 532                 upp = TAILQ_NEXT(up, list);
 533                 if (upp != NULL && up->ptr == upp->ptr) {
 534                         up->len += upp->len;
 535                         TAILQ_REMOVE(&uh->head, upp, list);
 536                         delete_unr(uh, upp);
 537                 }
 538         }
 539
 540         /* Merge into ->first if possible */
 541         upp = TAILQ_FIRST(&uh->head);
 542         if (upp != NULL && upp->ptr == uh) {
 543                 uh->first += upp->len;
 544                 TAILQ_REMOVE(&uh->head, upp, list);
 545                 delete_unr(uh, upp);
 546                 if (up == upp)
 547                         up = NULL;
 548         }
 549
 550         /* Merge into ->last if possible */
 551         upp = TAILQ_LAST(&uh->head, unrhd);
 552         if (upp != NULL && upp->ptr == NULL) {
 553                 uh->last += upp->len;
 554                 TAILQ_REMOVE(&uh->head, upp, list);
 555                 delete_unr(uh, upp);
 556                 if (up == upp)
 557                         up = NULL;
 558         }
 559
 560         /* Try to make bitmaps */
 561         while (optimize_unr(uh))
 562                 continue;
 563 }
 564
 565 /*
 566  * Allocate a free unr.
 567  */
 568 int
 569 alloc_unrl(struct unrhdr *uh)
 570 {
 571         struct unr *up;
 572         struct unrb *ub;
 573         u_int x;
 574         int y;
 575
 576         mtx_assert(uh->mtx, MA_OWNED);
 577         check_unrhdr(uh, __LINE__);
 578         x = uh->low + uh->first;
 579
 580         up = TAILQ_FIRST(&uh->head);
 581
 582         /*
 583          * If we have an ideal split, just adjust the first+last
 584          */
 585         if (up == NULL && uh->last > 0) {
 586                 uh->first++;
 587                 uh->last--;
 588                 uh->busy++;
 589                 return (x);
 590         }
 591
 592         /*
 593          * We can always allocate from the first list element, so if we have
 594          * nothing on the list, we must have run out of unit numbers.
 595          */
 596         if (up == NULL)
 597                 return (-1);
 598
 599         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
 600
 601         if (up->ptr == NULL) {  /* free run */
 602                 uh->first++;
 603                 up->len--;
 604         } else {                /* bitmap */
 605                 ub = up->ptr;
 606                 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
 607                 bit_ffc(ub->map, up->len, &y);
 608                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
 609                 bit_set(ub->map, y);
 610                 ub->busy++;
 611                 x += y;
 612         }
 613         uh->busy++;
 614         collapse_unr(uh, up);
 615         return (x);
 616 }
 617
 618 int
 619 alloc_unr(struct unrhdr *uh)
 620 {
 621         int i;
 622
 623         mtx_lock(uh->mtx);
 624         i = alloc_unrl(uh);
 625         clean_unrhdrl(uh);
 626         mtx_unlock(uh->mtx);
 627         return (i);
 628 }
 629
 630 /*
 631  * Free a unr.
 632  *
 633  * If we can save unrs by using a bitmap, do so.
 634  */
 635 static void
 636 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 637 {
 638         struct unr *up, *upp, *upn;
 639         struct unrb *ub;
 640         u_int pl;
 641
 642         KASSERT(item >= uh->low && item <= uh->high,
 643             ("UNR: free_unr(%u) out of range [%u...%u]",
 644              item, uh->low, uh->high));
 645         check_unrhdr(uh, __LINE__);
 646         item -= uh->low;
 647         upp = TAILQ_FIRST(&uh->head);
 648         /*
 649          * Freeing in the ideal split case
 650          */
 651         if (item + 1 == uh->first && upp == NULL) {
 652                 uh->last++;
 653                 uh->first--;
 654                 uh->busy--;
 655                 check_unrhdr(uh, __LINE__);
 656                 return;
 657         }
 658         /*
 659          * Freeing in the ->first section.  Create a run starting at the
 660          * freed item.  The code below will subdivide it.
 661          */
 662         if (item < uh->first) {
 663                 up = new_unr(uh, p1, p2);
 664                 up->ptr = uh;
 665                 up->len = uh->first - item;
 666                 TAILQ_INSERT_HEAD(&uh->head, up, list);
 667                 uh->first -= up->len;
 668         }
 669
 670         item -= uh->first;
 671
 672         /* Find the item which contains the unit we want to free */
 673         TAILQ_FOREACH(up, &uh->head, list) {
 674                 if (up->len > item)
 675                         break;
 676                 item -= up->len;
 677         }
 678
 679         /* Handle bitmap items */
 680         if (is_bitmap(uh, up)) {
 681                 ub = up->ptr;
 682
 683                 KASSERT(bit_test(ub->map, item) != 0,
 684                     ("UNR: Freeing free item %d (bitmap)\n", item));
 685                 bit_clear(ub->map, item);
 686                 uh->busy--;
 687                 ub->busy--;
 688                 collapse_unr(uh, up);
 689                 return;
 690         }
 691
 692         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
 693
 694         /* Just this one left, reap it */
 695         if (up->len == 1) {
 696                 up->ptr = NULL;
 697                 uh->busy--;
 698                 collapse_unr(uh, up);
 699                 return;
 700         }
 701
 702         /* Check if we can shift the item into the previous 'free' run */
 703         upp = TAILQ_PREV(up, unrhd, list);
 704         if (item == 0 && upp != NULL && upp->ptr == NULL) {
 705                 upp->len++;
 706                 up->len--;
 707                 uh->busy--;
 708                 collapse_unr(uh, up);
 709                 return;
 710         }
 711
 712         /* Check if we can shift the item to the next 'free' run */
 713         upn = TAILQ_NEXT(up, list);
 714         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
 715                 upn->len++;
 716                 up->len--;
 717                 uh->busy--;
 718                 collapse_unr(uh, up);
 719                 return;
 720         }
 721
 722         /* Split off the tail end, if any. */
 723         pl = up->len - (1 + item);
 724         if (pl > 0) {
 725                 upp = new_unr(uh, p1, p2);
 726                 upp->ptr = uh;
 727                 upp->len = pl;
 728                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
 729         }
 730
 731         /* Split off head end, if any */
 732         if (item > 0) {
 733                 upp = new_unr(uh, p1, p2);
 734                 upp->len = item;
 735                 upp->ptr = uh;
 736                 TAILQ_INSERT_BEFORE(up, upp, list);
 737         }
 738         up->len = 1;
 739         up->ptr = NULL;
 740         uh->busy--;
 741         collapse_unr(uh, up);
 742 }
 743
 744 void
 745 free_unr(struct unrhdr *uh, u_int item)
 746 {
 747         void *p1, *p2;
 748
 749         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
 750         p1 = Malloc(sizeof(struct unr));
 751         p2 = Malloc(sizeof(struct unr));
 752         mtx_lock(uh->mtx);
 753         free_unrl(uh, item, &p1, &p2);
 754         clean_unrhdrl(uh);
 755         mtx_unlock(uh->mtx);
 756         if (p1 != NULL)
 757                 Free(p1);
 758         if (p2 != NULL)
 759                 Free(p2);
 760 }
 761
 762 #ifndef _KERNEL /* USERLAND test driver */
 763
 764 /*
 765  * Simple stochastic test driver for the above functions
 766  */
 767
 768 static void
 769 print_unr(struct unrhdr *uh, struct unr *up)
 770 {
 771         u_int x;
 772         struct unrb *ub;
 773
 774         printf("  %p len = %5u ", up, up->len);
 775         if (up->ptr == NULL)
 776                 printf("free\n");
 777         else if (up->ptr == uh)
 778                 printf("alloc\n");
 779         else {
 780                 ub = up->ptr;
 781                 printf("bitmap(%d) [", ub->busy);
 782                 for (x = 0; x < up->len; x++) {
 783                         if (bit_test(ub->map, x))
 784                                 printf("#");
 785                         else
 786                                 printf(" ");
 787                 }
 788                 printf("]\n");
 789         }
 790 }
 791
 792 static void
 793 print_unrhdr(struct unrhdr *uh)
 794 {
 795         struct unr *up;
 796         u_int x;
 797
 798         printf(
 799             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
 800             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
 801         x = uh->low + uh->first;
 802         TAILQ_FOREACH(up, &uh->head, list) {
 803                 printf("  from = %5u", x);
 804                 print_unr(uh, up);
 805                 if (up->ptr == NULL || up->ptr == uh)
 806                         x += up->len;
 807                 else
 808                         x += NBITS;
 809         }
 810 }
 811
 812 /* Number of unrs to test */
 813 #define NN      10000
 814
 815 int
 816 main(int argc __unused, const char **argv __unused)
 817 {
 818         struct unrhdr *uh;
 819         u_int i, x, m, j;
 820         char a[NN];
 821
 822         setbuf(stdout, NULL);
 823         uh = new_unrhdr(0, NN - 1, NULL);
 824         print_unrhdr(uh);
 825
 826         memset(a, 0, sizeof a);
 827
 828         fprintf(stderr, "sizeof(struct unr) %d\n", sizeof (struct unr));
 829         fprintf(stderr, "sizeof(struct unrb) %d\n", sizeof (struct unrb));
 830         fprintf(stderr, "sizeof(struct unrhdr) %d\n", sizeof (struct unrhdr));
 831         fprintf(stderr, "NBITS %d\n", NBITS);
 832         x = 1;
 833         for (m = 0; m < NN * 100; m++) {
 834                 j = random();
 835                 i = (j >> 1) % NN;
 836 #if 0
 837                 if (a[i] && (j & 1))
 838                         continue;
 839 #endif
 840                 if (a[i]) {
 841                         printf("F %u\n", i);
 842                         free_unr(uh, i);
 843                         a[i] = 0;
 844                 } else {
 845                         no_alloc = 1;
 846                         i = alloc_unr(uh);
 847                         if (i != -1) {
 848                                 a[i] = 1;
 849                                 printf("A %u\n", i);
 850                         }
 851                         no_alloc = 0;
 852                 }
 853                 if (1)  /* XXX: change this for detailed debug printout */
 854                         print_unrhdr(uh);
 855                 check_unrhdr(uh, __LINE__);
 856         }
 857         for (i = 0; i < NN; i++) {
 858                 if (a[i]) {
 859                         printf("C %u\n", i);
 860                         free_unr(uh, i);
 861                         print_unrhdr(uh);
 862                 }
 863         }
 864         print_unrhdr(uh);
 865         delete_unrhdr(uh);
 866         return (0);
 867 }
 868 #endif