sys/kern/subr_unit.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   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
 134 struct mtx {
 135         int     state;
 136 } unitmtx;
 137
 138 static void
 139 mtx_lock(struct mtx *mp)
 140 {
 141         KASSERT(mp->state == 0, ("mutex already locked"));
 142         mp->state = 1;
 143 }
 144
 145 static void
 146 mtx_unlock(struct mtx *mp)
 147 {
 148         KASSERT(mp->state == 1, ("mutex not locked"));
 149         mp->state = 0;
 150 }
 151
 152 #define MA_OWNED        9
 153
 154 static void
 155 mtx_assert(struct mtx *mp, int flag)
 156 {
 157         if (flag == MA_OWNED) {
 158                 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
 159         }
 160 }
 161
 162 #define CTASSERT(foo)
 163 #define WITNESS_WARN(flags, lock, fmt, ...)     (void)0
 164
 165 #endif /* USERLAND */
 166
 167 /*
 168  * This is our basic building block.
 169  *
 170  * It can be used in three different ways depending on the value of the ptr
 171  * element:
 172  *     If ptr is NULL, it represents a run of free items.
 173  *     If ptr points to the unrhdr it represents a run of allocated items.
 174  *     Otherwise it points to a bitstring of allocated items.
 175  *
 176  * For runs the len field is the length of the run.
 177  * For bitmaps the len field represents the number of allocated items.
 178  *
 179  * The bitmap is the same size as struct unr to optimize memory management.
 180  */
 181 struct unr {
 182         TAILQ_ENTRY(unr)        list;
 183         u_int                   len;
 184         void                    *ptr;
 185 };
 186
 187 struct unrb {
 188         bitstr_t                map[sizeof(struct unr) / sizeof(bitstr_t)];
 189 };
 190
 191 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
 192
 193 /* Number of bits we can store in the bitmap */
 194 #define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
 195
 196 /* Is the unrb empty in at least the first len bits? */
 197 static inline bool
 198 ub_empty(struct unrb *ub, int len) {
 199         int first_set;
 200
 201         bit_ffs(ub->map, len, &first_set);
 202         return (first_set == -1);
 203 }
 204
 205 /* Is the unrb full?  That is, is the number of set elements equal to len? */
 206 static inline bool
 207 ub_full(struct unrb *ub, int len)
 208 {
 209         int first_clear;
 210
 211         bit_ffc(ub->map, len, &first_clear);
 212         return (first_clear == -1);
 213 }
 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 /*
 268  * Userland memory management.  Just use calloc and keep track of how
 269  * many elements we have allocated for check_unrhdr().
 270  */
 271
 272 static __inline void *
 273 new_unr(struct unrhdr *uh, void **p1, void **p2)
 274 {
 275         void *p;
 276
 277         uh->alloc++;
 278         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
 279         if (*p1 != NULL) {
 280                 p = *p1;
 281                 *p1 = NULL;
 282                 return (p);
 283         } else {
 284                 p = *p2;
 285                 *p2 = NULL;
 286                 return (p);
 287         }
 288 }
 289
 290 static __inline void
 291 delete_unr(struct unrhdr *uh, void *ptr)
 292 {
 293         struct unr *up;
 294
 295         uh->alloc--;
 296         up = ptr;
 297         TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
 298 }
 299
 300 void
 301 clean_unrhdrl(struct unrhdr *uh)
 302 {
 303         struct unr *up;
 304
 305         mtx_assert(uh->mtx, MA_OWNED);
 306         while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
 307                 TAILQ_REMOVE(&uh->ppfree, up, list);
 308                 mtx_unlock(uh->mtx);
 309                 Free(up);
 310                 mtx_lock(uh->mtx);
 311         }
 312
 313 }
 314
 315 void
 316 clean_unrhdr(struct unrhdr *uh)
 317 {
 318
 319         mtx_lock(uh->mtx);
 320         clean_unrhdrl(uh);
 321         mtx_unlock(uh->mtx);
 322 }
 323
 324 void
 325 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
 326 {
 327
 328         KASSERT(low >= 0 && low <= high,
 329             ("UNR: use error: new_unrhdr(%d, %d)", low, high));
 330         if (mutex != NULL)
 331                 uh->mtx = mutex;
 332         else
 333                 uh->mtx = &unitmtx;
 334         TAILQ_INIT(&uh->head);
 335         TAILQ_INIT(&uh->ppfree);
 336         uh->low = low;
 337         uh->high = high;
 338         uh->first = 0;
 339         uh->last = 1 + (high - low);
 340         check_unrhdr(uh, __LINE__);
 341 }
 342
 343 /*
 344  * Allocate a new unrheader set.
 345  *
 346  * Highest and lowest valid values given as parameters.
 347  */
 348
 349 struct unrhdr *
 350 new_unrhdr(int low, int high, struct mtx *mutex)
 351 {
 352         struct unrhdr *uh;
 353
 354         uh = Malloc(sizeof *uh);
 355         init_unrhdr(uh, low, high, mutex);
 356         return (uh);
 357 }
 358
 359 void
 360 delete_unrhdr(struct unrhdr *uh)
 361 {
 362
 363         check_unrhdr(uh, __LINE__);
 364         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
 365         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
 366         KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
 367             ("unrhdr has postponed item for free"));
 368         Free(uh);
 369 }
 370
 371 void
 372 clear_unrhdr(struct unrhdr *uh)
 373 {
 374         struct unr *up, *uq;
 375
 376         KASSERT(TAILQ_EMPTY(&uh->ppfree),
 377             ("unrhdr has postponed item for free"));
 378         TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
 379                 if (up->ptr != uh) {
 380                         Free(up->ptr);
 381                 }
 382                 Free(up);
 383         }
 384         uh->busy = 0;
 385         uh->alloc = 0;
 386         init_unrhdr(uh, uh->low, uh->high, uh->mtx);
 387
 388         check_unrhdr(uh, __LINE__);
 389 }
 390
 391 static __inline int
 392 is_bitmap(struct unrhdr *uh, struct unr *up)
 393 {
 394         return (up->ptr != uh && up->ptr != NULL);
 395 }
 396
 397 /*
 398  * Look for sequence of items which can be combined into a bitmap, if
 399  * multiple are present, take the one which saves most memory.
 400  *
 401  * Return (1) if a sequence was found to indicate that another call
 402  * might be able to do more.  Return (0) if we found no suitable sequence.
 403  *
 404  * NB: called from alloc_unr(), no new memory allocation allowed.
 405  */
 406 static int
 407 optimize_unr(struct unrhdr *uh)
 408 {
 409         struct unr *up, *uf, *us;
 410         struct unrb *ub, *ubf;
 411         u_int a, l, ba;
 412
 413         /*
 414          * Look for the run of items (if any) which when collapsed into
 415          * a bitmap would save most memory.
 416          */
 417         us = NULL;
 418         ba = 0;
 419         TAILQ_FOREACH(uf, &uh->head, list) {
 420                 if (uf->len >= NBITS)
 421                         continue;
 422                 a = 1;
 423                 if (is_bitmap(uh, uf))
 424                         a++;
 425                 l = uf->len;
 426                 up = uf;
 427                 while (1) {
 428                         up = TAILQ_NEXT(up, list);
 429                         if (up == NULL)
 430                                 break;
 431                         if ((up->len + l) > NBITS)
 432                                 break;
 433                         a++;
 434                         if (is_bitmap(uh, up))
 435                                 a++;
 436                         l += up->len;
 437                 }
 438                 if (a > ba) {
 439                         ba = a;
 440                         us = uf;
 441                 }
 442         }
 443         if (ba < 3)
 444                 return (0);
 445
 446         /*
 447          * If the first element is not a bitmap, make it one.
 448          * Trying to do so without allocating more memory complicates things
 449          * a bit
 450          */
 451         if (!is_bitmap(uh, us)) {
 452                 uf = TAILQ_NEXT(us, list);
 453                 TAILQ_REMOVE(&uh->head, us, list);
 454                 a = us->len;
 455                 l = us->ptr == uh ? 1 : 0;
 456                 ub = (void *)us;
 457                 bit_nclear(ub->map, 0, NBITS - 1);
 458                 if (l)
 459                         bit_nset(ub->map, 0, a);
 460                 if (!is_bitmap(uh, uf)) {
 461                         if (uf->ptr == NULL)
 462                                 bit_nclear(ub->map, a, a + uf->len - 1);
 463                         else
 464                                 bit_nset(ub->map, a, a + uf->len - 1);
 465                         uf->ptr = ub;
 466                         uf->len += a;
 467                         us = uf;
 468                 } else {
 469                         ubf = uf->ptr;
 470                         for (l = 0; l < uf->len; l++, a++) {
 471                                 if (bit_test(ubf->map, l))
 472                                         bit_set(ub->map, a);
 473                                 else
 474                                         bit_clear(ub->map, a);
 475                         }
 476                         uf->len = a;
 477                         delete_unr(uh, uf->ptr);
 478                         uf->ptr = ub;
 479                         us = uf;
 480                 }
 481         }
 482         ub = us->ptr;
 483         while (1) {
 484                 uf = TAILQ_NEXT(us, list);
 485                 if (uf == NULL)
 486                         return (1);
 487                 if (uf->len + us->len > NBITS)
 488                         return (1);
 489                 if (uf->ptr == NULL) {
 490                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
 491                         us->len += uf->len;
 492                         TAILQ_REMOVE(&uh->head, uf, list);
 493                         delete_unr(uh, uf);
 494                 } else if (uf->ptr == uh) {
 495                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
 496                         us->len += uf->len;
 497                         TAILQ_REMOVE(&uh->head, uf, list);
 498                         delete_unr(uh, uf);
 499                 } else {
 500                         ubf = uf->ptr;
 501                         for (l = 0; l < uf->len; l++, us->len++) {
 502                                 if (bit_test(ubf->map, l))
 503                                         bit_set(ub->map, us->len);
 504                                 else
 505                                         bit_clear(ub->map, us->len);
 506                         }
 507                         TAILQ_REMOVE(&uh->head, uf, list);
 508                         delete_unr(uh, ubf);
 509                         delete_unr(uh, uf);
 510                 }
 511         }
 512 }
 513
 514 /*
 515  * See if a given unr should be collapsed with a neighbor.
 516  *
 517  * NB: called from alloc_unr(), no new memory allocation allowed.
 518  */
 519 static void
 520 collapse_unr(struct unrhdr *uh, struct unr *up)
 521 {
 522         struct unr *upp;
 523         struct unrb *ub;
 524
 525         /* If bitmap is all set or clear, change it to runlength */
 526         if (is_bitmap(uh, up)) {
 527                 ub = up->ptr;
 528                 if (ub_full(ub, up->len)) {
 529                         delete_unr(uh, up->ptr);
 530                         up->ptr = uh;
 531                 } else if (ub_empty(ub, up->len)) {
 532                         delete_unr(uh, up->ptr);
 533                         up->ptr = NULL;
 534                 }
 535         }
 536
 537         /* If nothing left in runlength, delete it */
 538         if (up->len == 0) {
 539                 upp = TAILQ_PREV(up, unrhd, list);
 540                 if (upp == NULL)
 541                         upp = TAILQ_NEXT(up, list);
 542                 TAILQ_REMOVE(&uh->head, up, list);
 543                 delete_unr(uh, up);
 544                 up = upp;
 545         }
 546
 547         /* If we have "hot-spot" still, merge with neighbor if possible */
 548         if (up != NULL) {
 549                 upp = TAILQ_PREV(up, unrhd, list);
 550                 if (upp != NULL && up->ptr == upp->ptr) {
 551                         up->len += upp->len;
 552                         TAILQ_REMOVE(&uh->head, upp, list);
 553                         delete_unr(uh, upp);
 554                         }
 555                 upp = TAILQ_NEXT(up, list);
 556                 if (upp != NULL && up->ptr == upp->ptr) {
 557                         up->len += upp->len;
 558                         TAILQ_REMOVE(&uh->head, upp, list);
 559                         delete_unr(uh, upp);
 560                 }
 561         }
 562
 563         /* Merge into ->first if possible */
 564         upp = TAILQ_FIRST(&uh->head);
 565         if (upp != NULL && upp->ptr == uh) {
 566                 uh->first += upp->len;
 567                 TAILQ_REMOVE(&uh->head, upp, list);
 568                 delete_unr(uh, upp);
 569                 if (up == upp)
 570                         up = NULL;
 571         }
 572
 573         /* Merge into ->last if possible */
 574         upp = TAILQ_LAST(&uh->head, unrhd);
 575         if (upp != NULL && upp->ptr == NULL) {
 576                 uh->last += upp->len;
 577                 TAILQ_REMOVE(&uh->head, upp, list);
 578                 delete_unr(uh, upp);
 579                 if (up == upp)
 580                         up = NULL;
 581         }
 582
 583         /* Try to make bitmaps */
 584         while (optimize_unr(uh))
 585                 continue;
 586 }
 587
 588 /*
 589  * Allocate a free unr.
 590  */
 591 int
 592 alloc_unrl(struct unrhdr *uh)
 593 {
 594         struct unr *up;
 595         struct unrb *ub;
 596         u_int x;
 597         int y;
 598
 599         mtx_assert(uh->mtx, MA_OWNED);
 600         check_unrhdr(uh, __LINE__);
 601         x = uh->low + uh->first;
 602
 603         up = TAILQ_FIRST(&uh->head);
 604
 605         /*
 606          * If we have an ideal split, just adjust the first+last
 607          */
 608         if (up == NULL && uh->last > 0) {
 609                 uh->first++;
 610                 uh->last--;
 611                 uh->busy++;
 612                 return (x);
 613         }
 614
 615         /*
 616          * We can always allocate from the first list element, so if we have
 617          * nothing on the list, we must have run out of unit numbers.
 618          */
 619         if (up == NULL)
 620                 return (-1);
 621
 622         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
 623
 624         if (up->ptr == NULL) {  /* free run */
 625                 uh->first++;
 626                 up->len--;
 627         } else {                /* bitmap */
 628                 ub = up->ptr;
 629                 bit_ffc(ub->map, up->len, &y);
 630                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
 631                 bit_set(ub->map, y);
 632                 x += y;
 633         }
 634         uh->busy++;
 635         collapse_unr(uh, up);
 636         return (x);
 637 }
 638
 639 int
 640 alloc_unr(struct unrhdr *uh)
 641 {
 642         int i;
 643
 644         mtx_lock(uh->mtx);
 645         i = alloc_unrl(uh);
 646         clean_unrhdrl(uh);
 647         mtx_unlock(uh->mtx);
 648         return (i);
 649 }
 650
 651 static int
 652 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 653 {
 654         struct unr *up, *upn;
 655         struct unrb *ub;
 656         u_int i, last, tl;
 657
 658         mtx_assert(uh->mtx, MA_OWNED);
 659
 660         if (item < uh->low + uh->first || item > uh->high)
 661                 return (-1);
 662
 663         up = TAILQ_FIRST(&uh->head);
 664         /* Ideal split. */
 665         if (up == NULL && item - uh->low == uh->first) {
 666                 uh->first++;
 667                 uh->last--;
 668                 uh->busy++;
 669                 check_unrhdr(uh, __LINE__);
 670                 return (item);
 671         }
 672
 673         i = item - uh->low - uh->first;
 674
 675         if (up == NULL) {
 676                 up = new_unr(uh, p1, p2);
 677                 up->ptr = NULL;
 678                 up->len = i;
 679                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 680                 up = new_unr(uh, p1, p2);
 681                 up->ptr = uh;
 682                 up->len = 1;
 683                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 684                 uh->last = uh->high - uh->low - i;
 685                 uh->busy++;
 686                 check_unrhdr(uh, __LINE__);
 687                 return (item);
 688         } else {
 689                 /* Find the item which contains the unit we want to allocate. */
 690                 TAILQ_FOREACH(up, &uh->head, list) {
 691                         if (up->len > i)
 692                                 break;
 693                         i -= up->len;
 694                 }
 695         }
 696
 697         if (up == NULL) {
 698                 if (i > 0) {
 699                         up = new_unr(uh, p1, p2);
 700                         up->ptr = NULL;
 701                         up->len = i;
 702                         TAILQ_INSERT_TAIL(&uh->head, up, list);
 703                 }
 704                 up = new_unr(uh, p1, p2);
 705                 up->ptr = uh;
 706                 up->len = 1;
 707                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 708                 goto done;
 709         }
 710
 711         if (is_bitmap(uh, up)) {
 712                 ub = up->ptr;
 713                 if (bit_test(ub->map, i) == 0) {
 714                         bit_set(ub->map, i);
 715                         goto done;
 716                 } else
 717                         return (-1);
 718         } else if (up->ptr == uh)
 719                 return (-1);
 720
 721         KASSERT(up->ptr == NULL,
 722             ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
 723
 724         /* Split off the tail end, if any. */
 725         tl = up->len - (1 + i);
 726         if (tl > 0) {
 727                 upn = new_unr(uh, p1, p2);
 728                 upn->ptr = NULL;
 729                 upn->len = tl;
 730                 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
 731         }
 732
 733         /* Split off head end, if any */
 734         if (i > 0) {
 735                 upn = new_unr(uh, p1, p2);
 736                 upn->len = i;
 737                 upn->ptr = NULL;
 738                 TAILQ_INSERT_BEFORE(up, upn, list);
 739         }
 740         up->len = 1;
 741         up->ptr = uh;
 742
 743 done:
 744         last = uh->high - uh->low - (item - uh->low);
 745         if (uh->last > last)
 746                 uh->last = last;
 747         uh->busy++;
 748         collapse_unr(uh, up);
 749         check_unrhdr(uh, __LINE__);
 750         return (item);
 751 }
 752
 753 int
 754 alloc_unr_specific(struct unrhdr *uh, u_int item)
 755 {
 756         void *p1, *p2;
 757         int i;
 758
 759         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
 760
 761         p1 = Malloc(sizeof(struct unr));
 762         p2 = Malloc(sizeof(struct unr));
 763
 764         mtx_lock(uh->mtx);
 765         i = alloc_unr_specificl(uh, item, &p1, &p2);
 766         mtx_unlock(uh->mtx);
 767
 768         if (p1 != NULL)
 769                 Free(p1);
 770         if (p2 != NULL)
 771                 Free(p2);
 772
 773         return (i);
 774 }
 775
 776 /*
 777  * Free a unr.
 778  *
 779  * If we can save unrs by using a bitmap, do so.
 780  */
 781 static void
 782 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 783 {
 784         struct unr *up, *upp, *upn;
 785         struct unrb *ub;
 786         u_int pl;
 787
 788         KASSERT(item >= uh->low && item <= uh->high,
 789             ("UNR: free_unr(%u) out of range [%u...%u]",
 790              item, uh->low, uh->high));
 791         check_unrhdr(uh, __LINE__);
 792         item -= uh->low;
 793         upp = TAILQ_FIRST(&uh->head);
 794         /*
 795          * Freeing in the ideal split case
 796          */
 797         if (item + 1 == uh->first && upp == NULL) {
 798                 uh->last++;
 799                 uh->first--;
 800                 uh->busy--;
 801                 check_unrhdr(uh, __LINE__);
 802                 return;
 803         }
 804         /*
 805          * Freeing in the ->first section.  Create a run starting at the
 806          * freed item.  The code below will subdivide it.
 807          */
 808         if (item < uh->first) {
 809                 up = new_unr(uh, p1, p2);
 810                 up->ptr = uh;
 811                 up->len = uh->first - item;
 812                 TAILQ_INSERT_HEAD(&uh->head, up, list);
 813                 uh->first -= up->len;
 814         }
 815
 816         item -= uh->first;
 817
 818         /* Find the item which contains the unit we want to free */
 819         TAILQ_FOREACH(up, &uh->head, list) {
 820                 if (up->len > item)
 821                         break;
 822                 item -= up->len;
 823         }
 824
 825         /* Handle bitmap items */
 826         if (is_bitmap(uh, up)) {
 827                 ub = up->ptr;
 828
 829                 KASSERT(bit_test(ub->map, item) != 0,
 830                     ("UNR: Freeing free item %d (bitmap)\n", item));
 831                 bit_clear(ub->map, item);
 832                 uh->busy--;
 833                 collapse_unr(uh, up);
 834                 return;
 835         }
 836
 837         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
 838
 839         /* Just this one left, reap it */
 840         if (up->len == 1) {
 841                 up->ptr = NULL;
 842                 uh->busy--;
 843                 collapse_unr(uh, up);
 844                 return;
 845         }
 846
 847         /* Check if we can shift the item into the previous 'free' run */
 848         upp = TAILQ_PREV(up, unrhd, list);
 849         if (item == 0 && upp != NULL && upp->ptr == NULL) {
 850                 upp->len++;
 851                 up->len--;
 852                 uh->busy--;
 853                 collapse_unr(uh, up);
 854                 return;
 855         }
 856
 857         /* Check if we can shift the item to the next 'free' run */
 858         upn = TAILQ_NEXT(up, list);
 859         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
 860                 upn->len++;
 861                 up->len--;
 862                 uh->busy--;
 863                 collapse_unr(uh, up);
 864                 return;
 865         }
 866
 867         /* Split off the tail end, if any. */
 868         pl = up->len - (1 + item);
 869         if (pl > 0) {
 870                 upp = new_unr(uh, p1, p2);
 871                 upp->ptr = uh;
 872                 upp->len = pl;
 873                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
 874         }
 875
 876         /* Split off head end, if any */
 877         if (item > 0) {
 878                 upp = new_unr(uh, p1, p2);
 879                 upp->len = item;
 880                 upp->ptr = uh;
 881                 TAILQ_INSERT_BEFORE(up, upp, list);
 882         }
 883         up->len = 1;
 884         up->ptr = NULL;
 885         uh->busy--;
 886         collapse_unr(uh, up);
 887 }
 888
 889 void
 890 free_unr(struct unrhdr *uh, u_int item)
 891 {
 892         void *p1, *p2;
 893
 894         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
 895         p1 = Malloc(sizeof(struct unr));
 896         p2 = Malloc(sizeof(struct unr));
 897         mtx_lock(uh->mtx);
 898         free_unrl(uh, item, &p1, &p2);
 899         clean_unrhdrl(uh);
 900         mtx_unlock(uh->mtx);
 901         if (p1 != NULL)
 902                 Free(p1);
 903         if (p2 != NULL)
 904                 Free(p2);
 905 }
 906
 907 #ifndef _KERNEL /* USERLAND test driver */
 908
 909 /*
 910  * Simple stochastic test driver for the above functions.  The code resides
 911  * here so that it can access static functions and structures.
 912  */
 913
 914 static bool verbose;
 915 #define VPRINTF(...)    {if (verbose) printf(__VA_ARGS__);}
 916
 917 static void
 918 print_unr(struct unrhdr *uh, struct unr *up)
 919 {
 920         u_int x;
 921         struct unrb *ub;
 922
 923         printf("  %p len = %5u ", up, up->len);
 924         if (up->ptr == NULL)
 925                 printf("free\n");
 926         else if (up->ptr == uh)
 927                 printf("alloc\n");
 928         else {
 929                 ub = up->ptr;
 930                 printf("bitmap [");
 931                 for (x = 0; x < up->len; x++) {
 932                         if (bit_test(ub->map, x))
 933                                 printf("#");
 934                         else
 935                                 printf(" ");
 936                 }
 937                 printf("]\n");
 938         }
 939 }
 940
 941 static void
 942 print_unrhdr(struct unrhdr *uh)
 943 {
 944         struct unr *up;
 945         u_int x;
 946
 947         printf(
 948             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
 949             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
 950         x = uh->low + uh->first;
 951         TAILQ_FOREACH(up, &uh->head, list) {
 952                 printf("  from = %5u", x);
 953                 print_unr(uh, up);
 954                 if (up->ptr == NULL || up->ptr == uh)
 955                         x += up->len;
 956                 else
 957                         x += NBITS;
 958         }
 959 }
 960
 961 static void
 962 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
 963 {
 964         int j;
 965
 966         if (a[i]) {
 967                 VPRINTF("F %u\n", i);
 968                 free_unr(uh, i);
 969                 a[i] = 0;
 970         } else {
 971                 no_alloc = 1;
 972                 j = alloc_unr(uh);
 973                 if (j != -1) {
 974                         a[j] = 1;
 975                         VPRINTF("A %d\n", j);
 976                 }
 977                 no_alloc = 0;
 978         }
 979 }
 980
 981 static void
 982 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
 983 {
 984         int j;
 985
 986         j = alloc_unr_specific(uh, i);
 987         if (j == -1) {
 988                 VPRINTF("F %u\n", i);
 989                 a[i] = 0;
 990                 free_unr(uh, i);
 991         } else {
 992                 a[i] = 1;
 993                 VPRINTF("A %d\n", j);
 994         }
 995 }
 996
 997 static void
 998 usage(char** argv)
 999 {
1000         printf("%s [-h] [-r REPETITIONS] [-v]\n", argv[0]);
1001 }
1002
1003 int
1004 main(int argc, char **argv)
1005 {
1006         struct unrhdr *uh;
1007         char *a;
1008         long count = 10000;     /* Number of unrs to test */
1009         long reps = 1, m;
1010         int ch;
1011         u_int i, j;
1012
1013         verbose = false;
1014
1015         while ((ch = getopt(argc, argv, "hr:v")) != -1) {
1016                 switch (ch) {
1017                 case 'r':
1018                         errno = 0;
1019                         reps = strtol(optarg, NULL, 0);
1020                         if (errno == ERANGE || errno == EINVAL) {
1021                                 usage(argv);
1022                                 exit(2);
1023                         }
1024
1025                         break;
1026                 case 'v':
1027                         verbose = true;
1028                         break;
1029                 case 'h':
1030                 default:
1031                         usage(argv);
1032                         exit(2);
1033                 }
1034
1035
1036         }
1037
1038         setbuf(stdout, NULL);
1039         uh = new_unrhdr(0, count - 1, NULL);
1040         print_unrhdr(uh);
1041
1042         a = calloc(count, sizeof(char));
1043         if (a == NULL)
1044                 err(1, "calloc failed");
1045         srandomdev();
1046
1047         printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1048         printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1049         printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1050         printf("NBITS %lu\n", (unsigned long)NBITS);
1051         for (m = 0; m < count * reps; m++) {
1052                 j = random();
1053                 i = (j >> 1) % count;
1054 #if 0
1055                 if (a[i] && (j & 1))
1056                         continue;
1057 #endif
1058                 if ((random() & 1) != 0)
1059                         test_alloc_unr(uh, i, a);
1060                 else
1061                         test_alloc_unr_specific(uh, i, a);
1062
1063                 if (verbose)
1064                         print_unrhdr(uh);
1065                 check_unrhdr(uh, __LINE__);
1066         }
1067         for (i = 0; i < (u_int)count; i++) {
1068                 if (a[i]) {
1069                         if (verbose) {
1070                                 printf("C %u\n", i);
1071                                 print_unrhdr(uh);
1072                         }
1073                         free_unr(uh, i);
1074                 }
1075         }
1076         print_unrhdr(uh);
1077         delete_unrhdr(uh);
1078         free(a);
1079         return (0);
1080 }
1081 #endif