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 };
 201
 202
 203 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
 204 /*
 205  * Consistency check function.
 206  *
 207  * Checks the internal consistency as well as we can.
 208  *
 209  * Called at all boundaries of this API.
 210  */
 211 static void
 212 check_unrhdr(struct unrhdr *uh, int line)
 213 {
 214         struct unr *up;
 215         struct unrb *ub;
 216         u_int x, y, z, w;
 217
 218         y = uh->first;
 219         z = 0;
 220         TAILQ_FOREACH(up, &uh->head, list) {
 221                 z++;
 222                 if (up->ptr != uh && up->ptr != NULL) {
 223                         ub = up->ptr;
 224                         KASSERT (up->len <= NBITS,
 225                             ("UNR inconsistency: len %u max %d (line %d)\n",
 226                             up->len, NBITS, line));
 227                         z++;
 228                         w = 0;
 229                         for (x = 0; x < up->len; x++)
 230                                 if (bit_test(ub->map, x))
 231                                         w++;
 232                         KASSERT (w == ub->busy,
 233                             ("UNR inconsistency: busy %u found %u (line %d)\n",
 234                             ub->busy, w, line));
 235                         y += w;
 236                 } else if (up->ptr != NULL)
 237                         y += up->len;
 238         }
 239         KASSERT (y == uh->busy,
 240             ("UNR inconsistency: items %u found %u (line %d)\n",
 241             uh->busy, y, line));
 242         KASSERT (z == uh->alloc,
 243             ("UNR inconsistency: chunks %u found %u (line %d)\n",
 244             uh->alloc, z, line));
 245 }
 246
 247 #else
 248
 249 static __inline void
 250 check_unrhdr(struct unrhdr *uh, int line)
 251 {
 252
 253 }
 254
 255 #endif
 256
 257
 258 /*
 259  * Userland memory management.  Just use calloc and keep track of how
 260  * many elements we have allocated for check_unrhdr().
 261  */
 262
 263 static __inline void *
 264 new_unr(struct unrhdr *uh, void **p1, void **p2)
 265 {
 266         void *p;
 267
 268         uh->alloc++;
 269         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
 270         if (*p1 != NULL) {
 271                 p = *p1;
 272                 *p1 = NULL;
 273                 return (p);
 274         } else {
 275                 p = *p2;
 276                 *p2 = NULL;
 277                 return (p);
 278         }
 279 }
 280
 281 static __inline void
 282 delete_unr(struct unrhdr *uh, void *ptr)
 283 {
 284
 285         uh->alloc--;
 286         Free(ptr);
 287 }
 288
 289 /*
 290  * Allocate a new unrheader set.
 291  *
 292  * Highest and lowest valid values given as paramters.
 293  */
 294
 295 struct unrhdr *
 296 new_unrhdr(int low, int high, struct mtx *mutex)
 297 {
 298         struct unrhdr *uh;
 299
 300         KASSERT(low <= high,
 301             ("UNR: use error: new_unrhdr(%u, %u)", low, high));
 302         uh = Malloc(sizeof *uh);
 303         if (mutex != NULL)
 304                 uh->mtx = mutex;
 305         else
 306                 uh->mtx = &unitmtx;
 307         TAILQ_INIT(&uh->head);
 308         uh->low = low;
 309         uh->high = high;
 310         uh->first = 0;
 311         uh->last = 1 + (high - low);
 312         check_unrhdr(uh, __LINE__);
 313         return (uh);
 314 }
 315
 316 void
 317 delete_unrhdr(struct unrhdr *uh)
 318 {
 319
 320         check_unrhdr(uh, __LINE__);
 321         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
 322         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
 323         Free(uh);
 324 }
 325
 326 static __inline int
 327 is_bitmap(struct unrhdr *uh, struct unr *up)
 328 {
 329         return (up->ptr != uh && up->ptr != NULL);
 330 }
 331
 332 /*
 333  * Look for sequence of items which can be combined into a bitmap, if
 334  * multiple are present, take the one which saves most memory.
 335  *
 336  * Return (1) if a sequence was found to indicate that another call
 337  * might be able to do more.  Return (0) if we found no suitable sequence.
 338  *
 339  * NB: called from alloc_unr(), no new memory allocation allowed.
 340  */
 341 static int
 342 optimize_unr(struct unrhdr *uh)
 343 {
 344         struct unr *up, *uf, *us;
 345         struct unrb *ub, *ubf;
 346         u_int a, l, ba;
 347
 348         /*
 349          * Look for the run of items (if any) which when collapsed into
 350          * a bitmap would save most memory.
 351          */
 352         us = NULL;
 353         ba = 0;
 354         TAILQ_FOREACH(uf, &uh->head, list) {
 355                 if (uf->len >= NBITS)
 356                         continue;
 357                 a = 1;
 358                 if (is_bitmap(uh, uf))
 359                         a++;
 360                 l = uf->len;
 361                 up = uf;
 362                 while (1) {
 363                         up = TAILQ_NEXT(up, list);
 364                         if (up == NULL)
 365                                 break;
 366                         if ((up->len + l) > NBITS)
 367                                 break;
 368                         a++;
 369                         if (is_bitmap(uh, up))
 370                                 a++;
 371                         l += up->len;
 372                 }
 373                 if (a > ba) {
 374                         ba = a;
 375                         us = uf;
 376                 }
 377         }
 378         if (ba < 3)
 379                 return (0);
 380
 381         /*
 382          * If the first element is not a bitmap, make it one.
 383          * Trying to do so without allocating more memory complicates things
 384          * a bit
 385          */
 386         if (!is_bitmap(uh, us)) {
 387                 uf = TAILQ_NEXT(us, list);
 388                 TAILQ_REMOVE(&uh->head, us, list);
 389                 a = us->len;
 390                 l = us->ptr == uh ? 1 : 0;
 391                 ub = (void *)us;
 392                 ub->busy = 0;
 393                 if (l) {
 394                         bit_nset(ub->map, 0, a);
 395                         ub->busy += a;
 396                 } else {
 397                         bit_nclear(ub->map, 0, a);
 398                 }
 399                 if (!is_bitmap(uh, uf)) {
 400                         if (uf->ptr == NULL) {
 401                                 bit_nclear(ub->map, a, a + uf->len - 1);
 402                         } else {
 403                                 bit_nset(ub->map, a, a + uf->len - 1);
 404                                 ub->busy += uf->len;
 405                         }
 406                         uf->ptr = ub;
 407                         uf->len += a;
 408                         us = uf;
 409                 } else {
 410                         ubf = uf->ptr;
 411                         for (l = 0; l < uf->len; l++, a++) {
 412                                 if (bit_test(ubf->map, l)) {
 413                                         bit_set(ub->map, a);
 414                                         ub->busy++;
 415                                 } else {
 416                                         bit_clear(ub->map, a);
 417                                 }
 418                         }
 419                         uf->len = a;
 420                         delete_unr(uh, uf->ptr);
 421                         uf->ptr = ub;
 422                         us = uf;
 423                 }
 424         }
 425         ub = us->ptr;
 426         while (1) {
 427                 uf = TAILQ_NEXT(us, list);
 428                 if (uf == NULL)
 429                         return (1);
 430                 if (uf->len + us->len > NBITS)
 431                         return (1);
 432                 if (uf->ptr == NULL) {
 433                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
 434                         us->len += uf->len;
 435                         TAILQ_REMOVE(&uh->head, uf, list);
 436                         delete_unr(uh, uf);
 437                 } else if (uf->ptr == uh) {
 438                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
 439                         ub->busy += uf->len;
 440                         us->len += uf->len;
 441                         TAILQ_REMOVE(&uh->head, uf, list);
 442                         delete_unr(uh, uf);
 443                 } else {
 444                         ubf = uf->ptr;
 445                         for (l = 0; l < uf->len; l++, us->len++) {
 446                                 if (bit_test(ubf->map, l)) {
 447                                         bit_set(ub->map, us->len);
 448                                         ub->busy++;
 449                                 } else {
 450                                         bit_clear(ub->map, us->len);
 451                                 }
 452                         }
 453                         TAILQ_REMOVE(&uh->head, uf, list);
 454                         delete_unr(uh, ubf);
 455                         delete_unr(uh, uf);
 456                 }
 457         }
 458 }
 459
 460 /*
 461  * See if a given unr should be collapsed with a neighbor.
 462  *
 463  * NB: called from alloc_unr(), no new memory allocation allowed.
 464  */
 465 static void
 466 collapse_unr(struct unrhdr *uh, struct unr *up)
 467 {
 468         struct unr *upp;
 469         struct unrb *ub;
 470
 471         /* If bitmap is all set or clear, change it to runlength */
 472         if (is_bitmap(uh, up)) {
 473                 ub = up->ptr;
 474                 if (ub->busy == up->len) {
 475                         delete_unr(uh, up->ptr);
 476                         up->ptr = uh;
 477                 } else if (ub->busy == 0) {
 478                         delete_unr(uh, up->ptr);
 479                         up->ptr = NULL;
 480                 }
 481         }
 482
 483         /* If nothing left in runlength, delete it */
 484         if (up->len == 0) {
 485                 upp = TAILQ_PREV(up, unrhd, list);
 486                 if (upp == NULL)
 487                         upp = TAILQ_NEXT(up, list);
 488                 TAILQ_REMOVE(&uh->head, up, list);
 489                 delete_unr(uh, up);
 490                 up = upp;
 491         }
 492
 493         /* If we have "hot-spot" still, merge with neighbor if possible */
 494         if (up != NULL) {
 495                 upp = TAILQ_PREV(up, unrhd, list);
 496                 if (upp != NULL && up->ptr == upp->ptr) {
 497                         up->len += upp->len;
 498                         TAILQ_REMOVE(&uh->head, upp, list);
 499                         delete_unr(uh, upp);
 500                         }
 501                 upp = TAILQ_NEXT(up, list);
 502                 if (upp != NULL && up->ptr == upp->ptr) {
 503                         up->len += upp->len;
 504                         TAILQ_REMOVE(&uh->head, upp, list);
 505                         delete_unr(uh, upp);
 506                 }
 507         }
 508
 509         /* Merge into ->first if possible */
 510         upp = TAILQ_FIRST(&uh->head);
 511         if (upp != NULL && upp->ptr == uh) {
 512                 uh->first += upp->len;
 513                 TAILQ_REMOVE(&uh->head, upp, list);
 514                 delete_unr(uh, upp);
 515                 if (up == upp)
 516                         up = NULL;
 517         }
 518
 519         /* Merge into ->last if possible */
 520         upp = TAILQ_LAST(&uh->head, unrhd);
 521         if (upp != NULL && upp->ptr == NULL) {
 522                 uh->last += upp->len;
 523                 TAILQ_REMOVE(&uh->head, upp, list);
 524                 delete_unr(uh, upp);
 525                 if (up == upp)
 526                         up = NULL;
 527         }
 528
 529         /* Try to make bitmaps */
 530         while (optimize_unr(uh))
 531                 continue;
 532 }
 533
 534 /*
 535  * Allocate a free unr.
 536  */
 537 int
 538 alloc_unrl(struct unrhdr *uh)
 539 {
 540         struct unr *up;
 541         struct unrb *ub;
 542         u_int x;
 543         int y;
 544
 545         mtx_assert(uh->mtx, MA_OWNED);
 546         check_unrhdr(uh, __LINE__);
 547         x = uh->low + uh->first;
 548
 549         up = TAILQ_FIRST(&uh->head);
 550
 551         /*
 552          * If we have an ideal split, just adjust the first+last
 553          */
 554         if (up == NULL && uh->last > 0) {
 555                 uh->first++;
 556                 uh->last--;
 557                 uh->busy++;
 558                 return (x);
 559         }
 560
 561         /*
 562          * We can always allocate from the first list element, so if we have
 563          * nothing on the list, we must have run out of unit numbers.
 564          */
 565         if (up == NULL)
 566                 return (-1);
 567
 568         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
 569
 570         if (up->ptr == NULL) {  /* free run */
 571                 uh->first++;
 572                 up->len--;
 573         } else {                /* bitmap */
 574                 ub = up->ptr;
 575                 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
 576                 bit_ffc(ub->map, up->len, &y);
 577                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
 578                 bit_set(ub->map, y);
 579                 ub->busy++;
 580                 x += y;
 581         }
 582         uh->busy++;
 583         collapse_unr(uh, up);
 584         return (x);
 585 }
 586
 587 int
 588 alloc_unr(struct unrhdr *uh)
 589 {
 590         int i;
 591
 592         mtx_lock(uh->mtx);
 593         i = alloc_unrl(uh);
 594         mtx_unlock(uh->mtx);
 595         return (i);
 596 }
 597
 598 /*
 599  * Free a unr.
 600  *
 601  * If we can save unrs by using a bitmap, do so.
 602  */
 603 static void
 604 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 605 {
 606         struct unr *up, *upp, *upn;
 607         struct unrb *ub;
 608         u_int pl;
 609
 610         KASSERT(item >= uh->low && item <= uh->high,
 611             ("UNR: free_unr(%u) out of range [%u...%u]",
 612              item, uh->low, uh->high));
 613         check_unrhdr(uh, __LINE__);
 614         item -= uh->low;
 615         upp = TAILQ_FIRST(&uh->head);
 616         /*
 617          * Freeing in the ideal split case
 618          */
 619         if (item + 1 == uh->first && upp == NULL) {
 620                 uh->last++;
 621                 uh->first--;
 622                 uh->busy--;
 623                 check_unrhdr(uh, __LINE__);
 624                 return;
 625         }
 626         /*
 627          * Freeing in the ->first section.  Create a run starting at the
 628          * freed item.  The code below will subdivide it.
 629          */
 630         if (item < uh->first) {
 631                 up = new_unr(uh, p1, p2);
 632                 up->ptr = uh;
 633                 up->len = uh->first - item;
 634                 TAILQ_INSERT_HEAD(&uh->head, up, list);
 635                 uh->first -= up->len;
 636         }
 637
 638         item -= uh->first;
 639
 640         /* Find the item which contains the unit we want to free */
 641         TAILQ_FOREACH(up, &uh->head, list) {
 642                 if (up->len > item)
 643                         break;
 644                 item -= up->len;
 645         }
 646
 647         /* Handle bitmap items */
 648         if (is_bitmap(uh, up)) {
 649                 ub = up->ptr;
 650
 651                 KASSERT(bit_test(ub->map, item) != 0,
 652                     ("UNR: Freeing free item %d (bitmap)\n", item));
 653                 bit_clear(ub->map, item);
 654                 uh->busy--;
 655                 ub->busy--;
 656                 collapse_unr(uh, up);
 657                 return;
 658         }
 659
 660         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
 661
 662         /* Just this one left, reap it */
 663         if (up->len == 1) {
 664                 up->ptr = NULL;
 665                 uh->busy--;
 666                 collapse_unr(uh, up);
 667                 return;
 668         }
 669
 670         /* Check if we can shift the item into the previous 'free' run */
 671         upp = TAILQ_PREV(up, unrhd, list);
 672         if (item == 0 && upp != NULL && upp->ptr == NULL) {
 673                 upp->len++;
 674                 up->len--;
 675                 uh->busy--;
 676                 collapse_unr(uh, up);
 677                 return;
 678         }
 679
 680         /* Check if we can shift the item to the next 'free' run */
 681         upn = TAILQ_NEXT(up, list);
 682         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
 683                 upn->len++;
 684                 up->len--;
 685                 uh->busy--;
 686                 collapse_unr(uh, up);
 687                 return;
 688         }
 689
 690         /* Split off the tail end, if any. */
 691         pl = up->len - (1 + item);
 692         if (pl > 0) {
 693                 upp = new_unr(uh, p1, p2);
 694                 upp->ptr = uh;
 695                 upp->len = pl;
 696                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
 697         }
 698
 699         /* Split off head end, if any */
 700         if (item > 0) {
 701                 upp = new_unr(uh, p1, p2);
 702                 upp->len = item;
 703                 upp->ptr = uh;
 704                 TAILQ_INSERT_BEFORE(up, upp, list);
 705         }
 706         up->len = 1;
 707         up->ptr = NULL;
 708         uh->busy--;
 709         collapse_unr(uh, up);
 710 }
 711
 712 void
 713 free_unr(struct unrhdr *uh, u_int item)
 714 {
 715         void *p1, *p2;
 716
 717         p1 = Malloc(sizeof(struct unr));
 718         p2 = Malloc(sizeof(struct unr));
 719         mtx_lock(uh->mtx);
 720         free_unrl(uh, item, &p1, &p2);
 721         mtx_unlock(uh->mtx);
 722         if (p1 != NULL)
 723                 Free(p1);
 724         if (p2 != NULL)
 725                 Free(p2);
 726 }
 727
 728 #ifndef _KERNEL /* USERLAND test driver */
 729
 730 /*
 731  * Simple stochastic test driver for the above functions
 732  */
 733
 734 static void
 735 print_unr(struct unrhdr *uh, struct unr *up)
 736 {
 737         u_int x;
 738         struct unrb *ub;
 739
 740         printf("  %p len = %5u ", up, up->len);
 741         if (up->ptr == NULL)
 742                 printf("free\n");
 743         else if (up->ptr == uh)
 744                 printf("alloc\n");
 745         else {
 746                 ub = up->ptr;
 747                 printf("bitmap(%d) [", ub->busy);
 748                 for (x = 0; x < up->len; x++) {
 749                         if (bit_test(ub->map, x))
 750                                 printf("#");
 751                         else
 752                                 printf(" ");
 753                 }
 754                 printf("]\n");
 755         }
 756 }
 757
 758 static void
 759 print_unrhdr(struct unrhdr *uh)
 760 {
 761         struct unr *up;
 762         u_int x;
 763
 764         printf(
 765             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
 766             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
 767         x = uh->low + uh->first;
 768         TAILQ_FOREACH(up, &uh->head, list) {
 769                 printf("  from = %5u", x);
 770                 print_unr(uh, up);
 771                 if (up->ptr == NULL || up->ptr == uh)
 772                         x += up->len;
 773                 else
 774                         x += NBITS;
 775         }
 776 }
 777
 778 /* Number of unrs to test */
 779 #define NN      10000
 780
 781 int
 782 main(int argc __unused, const char **argv __unused)
 783 {
 784         struct unrhdr *uh;
 785         u_int i, x, m, j;
 786         char a[NN];
 787
 788         setbuf(stdout, NULL);
 789         uh = new_unrhdr(0, NN - 1, NULL);
 790         print_unrhdr(uh);
 791
 792         memset(a, 0, sizeof a);
 793
 794         fprintf(stderr, "sizeof(struct unr) %d\n", sizeof (struct unr));
 795         fprintf(stderr, "sizeof(struct unrb) %d\n", sizeof (struct unrb));
 796         fprintf(stderr, "sizeof(struct unrhdr) %d\n", sizeof (struct unrhdr));
 797         fprintf(stderr, "NBITS %d\n", NBITS);
 798         x = 1;
 799         for (m = 0; m < NN * 100; m++) {
 800                 j = random();
 801                 i = (j >> 1) % NN;
 802 #if 0
 803                 if (a[i] && (j & 1))
 804                         continue;
 805 #endif
 806                 if (a[i]) {
 807                         printf("F %u\n", i);
 808                         free_unr(uh, i);
 809                         a[i] = 0;
 810                 } else {
 811                         no_alloc = 1;
 812                         i = alloc_unr(uh);
 813                         if (i != -1) {
 814                                 a[i] = 1;
 815                                 printf("A %u\n", i);
 816                         }
 817                         no_alloc = 0;
 818                 }
 819                 if (1)  /* XXX: change this for detailed debug printout */
 820                         print_unrhdr(uh);
 821                 check_unrhdr(uh, __LINE__);
 822         }
 823         for (i = 0; i < NN; i++) {
 824                 if (a[i]) {
 825                         printf("C %u\n", i);
 826                         free_unr(uh, i);
 827                         print_unrhdr(uh);
 828                 }
 829         }
 830         print_unrhdr(uh);
 831         delete_unrhdr(uh);
 832         return (0);
 833 }
 834 #endif