sys/kern/subr_unit.c

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