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 #ifdef UNR64_LOCKED
 102 uint64_t
 103 alloc_unr64(struct unrhdr64 *unr64)
 104 {
 105         uint64_t item;
 106
 107         mtx_lock(&unitmtx);
 108         item = unr64->counter++;
 109         mtx_unlock(&unitmtx);
 110         return (item);
 111 }
 112 #endif
 113
 114 #else /* ...USERLAND */
 115
 116 #include <bitstring.h>
 117 #include <err.h>
 118 #include <errno.h>
 119 #include <getopt.h>
 120 #include <stdbool.h>
 121 #include <stdio.h>
 122 #include <stdlib.h>
 123 #include <string.h>
 124
 125 #define KASSERT(cond, arg) \
 126         do { \
 127                 if (!(cond)) { \
 128                         printf arg; \
 129                         abort(); \
 130                 } \
 131         } while (0)
 132
 133 static int no_alloc;
 134 #define Malloc(foo) _Malloc(foo, __LINE__)
 135 static void *
 136 _Malloc(size_t foo, int line)
 137 {
 138
 139         KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
 140         return (calloc(foo, 1));
 141 }
 142 #define Free(foo) free(foo)
 143
 144 struct unrhdr;
 145
 146 #define UNR_NO_MTX      ((void *)(uintptr_t)-1)
 147
 148 struct mtx {
 149         int     state;
 150 } unitmtx;
 151
 152 static void
 153 mtx_lock(struct mtx *mp)
 154 {
 155         KASSERT(mp->state == 0, ("mutex already locked"));
 156         mp->state = 1;
 157 }
 158
 159 static void
 160 mtx_unlock(struct mtx *mp)
 161 {
 162         KASSERT(mp->state == 1, ("mutex not locked"));
 163         mp->state = 0;
 164 }
 165
 166 #define MA_OWNED        9
 167
 168 static void
 169 mtx_assert(struct mtx *mp, int flag)
 170 {
 171         if (flag == MA_OWNED) {
 172                 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
 173         }
 174 }
 175
 176 #define CTASSERT(foo)
 177 #define WITNESS_WARN(flags, lock, fmt, ...)     (void)0
 178
 179 #endif /* USERLAND */
 180
 181 /*
 182  * This is our basic building block.
 183  *
 184  * It can be used in three different ways depending on the value of the ptr
 185  * element:
 186  *     If ptr is NULL, it represents a run of free items.
 187  *     If ptr points to the unrhdr it represents a run of allocated items.
 188  *     Otherwise it points to a bitstring of allocated items.
 189  *
 190  * For runs the len field is the length of the run.
 191  * For bitmaps the len field represents the number of allocated items.
 192  *
 193  * The bitmap is the same size as struct unr to optimize memory management.
 194  *
 195  * Two special ranges are not covered by unrs:
 196  * - at the start of the allocator space, all elements in [low, low + first)
 197  *   are allocated;
 198  * - at the end of the allocator space, all elements in [high - last, high]
 199  *   are free.
 200  */
 201 struct unr {
 202         TAILQ_ENTRY(unr)        list;
 203         u_int                   len;
 204         void                    *ptr;
 205 };
 206
 207 struct unrb {
 208         bitstr_t                map[sizeof(struct unr) / sizeof(bitstr_t)];
 209 };
 210
 211 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
 212
 213 /* Number of bits we can store in the bitmap */
 214 #define NBITS (NBBY * sizeof(((struct unrb *)NULL)->map))
 215
 216 static inline bool
 217 is_bitmap(struct unrhdr *uh, struct unr *up)
 218 {
 219         return (up->ptr != uh && up->ptr != NULL);
 220 }
 221
 222 /* Is the unrb empty in at least the first len bits? */
 223 static inline bool
 224 ub_empty(struct unrb *ub, int len) {
 225         int first_set;
 226
 227         bit_ffs(ub->map, len, &first_set);
 228         return (first_set == -1);
 229 }
 230
 231 /* Is the unrb full?  That is, is the number of set elements equal to len? */
 232 static inline bool
 233 ub_full(struct unrb *ub, int len)
 234 {
 235         int first_clear;
 236
 237         bit_ffc(ub->map, len, &first_clear);
 238         return (first_clear == -1);
 239 }
 240
 241 /*
 242  * start: ipos = -1, upos = NULL;
 243  * end:   ipos = -1, upos = uh
 244  */
 245 struct unrhdr_iter {
 246         struct unrhdr *uh;
 247         int ipos;
 248         int upos_first_item;
 249         void *upos;
 250 };
 251
 252 void *
 253 create_iter_unr(struct unrhdr *uh)
 254 {
 255         struct unrhdr_iter *iter;
 256
 257         iter = Malloc(sizeof(*iter));
 258         iter->ipos = -1;
 259         iter->uh = uh;
 260         iter->upos = NULL;
 261         iter->upos_first_item = -1;
 262         return (iter);
 263 }
 264
 265 static void
 266 next_iter_unrl(struct unrhdr *uh, struct unrhdr_iter *iter)
 267 {
 268         struct unr *up;
 269         struct unrb *ub;
 270         u_int y;
 271         int c;
 272
 273         if (iter->ipos == -1) {
 274                 if (iter->upos == uh)
 275                         return;
 276                 y = uh->low - 1;
 277                 if (uh->first == 0) {
 278                         up = TAILQ_FIRST(&uh->head);
 279                         if (up == NULL) {
 280                                 iter->upos = uh;
 281                                 return;
 282                         }
 283                         iter->upos = up;
 284                         if (up->ptr == NULL)
 285                                 iter->upos = NULL;
 286                         else
 287                                 iter->upos_first_item = uh->low;
 288                 }
 289         } else {
 290                 y = iter->ipos;
 291         }
 292
 293         up = iter->upos;
 294
 295         /* Special case for the compacted [low, first) run. */
 296         if (up == NULL) {
 297                 if (y + 1 < uh->low + uh->first) {
 298                         iter->ipos = y + 1;
 299                         return;
 300                 }
 301                 up = iter->upos = TAILQ_FIRST(&uh->head);
 302                 iter->upos_first_item = uh->low + uh->first;
 303         }
 304
 305         for (;;) {
 306                 if (y + 1 < iter->upos_first_item + up->len) {
 307                         if (up->ptr == uh) {
 308                                 iter->ipos = y + 1;
 309                                 return;
 310                         } else if (is_bitmap(uh, up)) {
 311                                 ub = up->ptr;
 312                                 bit_ffs_at(&ub->map[0],
 313                                     y + 1 - iter->upos_first_item,
 314                                     up->len, &c);
 315                                 if (c != -1) {
 316                                         iter->ipos = iter->upos_first_item + c;
 317                                         return;
 318                                 }
 319                         }
 320                 }
 321                 iter->upos_first_item += up->len;
 322                 y = iter->upos_first_item - 1;
 323                 up = iter->upos = TAILQ_NEXT((struct unr *)iter->upos, list);
 324                 if (iter->upos == NULL) {
 325                         iter->ipos = -1;
 326                         iter->upos = uh;
 327                         return;
 328                 }
 329         }
 330 }
 331
 332 /*
 333  * returns -1 on end, otherwise the next element
 334  */
 335 int
 336 next_iter_unr(void *handle)
 337 {
 338         struct unrhdr *uh;
 339         struct unrhdr_iter *iter;
 340
 341         iter = handle;
 342         uh = iter->uh;
 343         if (uh->mtx != NULL)
 344                 mtx_lock(uh->mtx);
 345         next_iter_unrl(uh, iter);
 346         if (uh->mtx != NULL)
 347                 mtx_unlock(uh->mtx);
 348         return (iter->ipos);
 349 }
 350
 351 void
 352 free_iter_unr(void *handle)
 353 {
 354         Free(handle);
 355 }
 356
 357 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
 358 /*
 359  * Consistency check function.
 360  *
 361  * Checks the internal consistency as well as we can.
 362  *
 363  * Called at all boundaries of this API.
 364  */
 365 static void
 366 check_unrhdr(struct unrhdr *uh, int line)
 367 {
 368         struct unr *up;
 369         struct unrb *ub;
 370         int w;
 371         u_int y, z;
 372
 373         y = uh->first;
 374         z = 0;
 375         TAILQ_FOREACH(up, &uh->head, list) {
 376                 z++;
 377                 if (is_bitmap(uh, up)) {
 378                         ub = up->ptr;
 379                         KASSERT (up->len <= NBITS,
 380                             ("UNR inconsistency: len %u max %zd (line %d)\n",
 381                             up->len, NBITS, line));
 382                         z++;
 383                         w = 0;
 384                         bit_count(ub->map, 0, up->len, &w);
 385                         y += w;
 386                 } else if (up->ptr != NULL)
 387                         y += up->len;
 388         }
 389         KASSERT (y == uh->busy,
 390             ("UNR inconsistency: items %u found %u (line %d)\n",
 391             uh->busy, y, line));
 392         KASSERT (z == uh->alloc,
 393             ("UNR inconsistency: chunks %u found %u (line %d)\n",
 394             uh->alloc, z, line));
 395 }
 396
 397 #else
 398
 399 static __inline void
 400 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
 401 {
 402
 403 }
 404
 405 #endif
 406
 407 /*
 408  * Userland memory management.  Just use calloc and keep track of how
 409  * many elements we have allocated for check_unrhdr().
 410  */
 411
 412 static __inline void *
 413 new_unr(struct unrhdr *uh, void **p1, void **p2)
 414 {
 415         void *p;
 416
 417         uh->alloc++;
 418         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
 419         if (*p1 != NULL) {
 420                 p = *p1;
 421                 *p1 = NULL;
 422                 return (p);
 423         } else {
 424                 p = *p2;
 425                 *p2 = NULL;
 426                 return (p);
 427         }
 428 }
 429
 430 static __inline void
 431 delete_unr(struct unrhdr *uh, void *ptr)
 432 {
 433         struct unr *up;
 434
 435         uh->alloc--;
 436         up = ptr;
 437         TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
 438 }
 439
 440 void
 441 clean_unrhdrl(struct unrhdr *uh)
 442 {
 443         struct unr *up;
 444
 445         if (uh->mtx != NULL)
 446                 mtx_assert(uh->mtx, MA_OWNED);
 447         while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
 448                 TAILQ_REMOVE(&uh->ppfree, up, list);
 449                 if (uh->mtx != NULL)
 450                         mtx_unlock(uh->mtx);
 451                 Free(up);
 452                 if (uh->mtx != NULL)
 453                         mtx_lock(uh->mtx);
 454         }
 455
 456 }
 457
 458 void
 459 clean_unrhdr(struct unrhdr *uh)
 460 {
 461
 462         if (uh->mtx != NULL)
 463                 mtx_lock(uh->mtx);
 464         clean_unrhdrl(uh);
 465         if (uh->mtx != NULL)
 466                 mtx_unlock(uh->mtx);
 467 }
 468
 469 void
 470 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
 471 {
 472
 473         KASSERT(low >= 0 && low <= high,
 474             ("UNR: use error: new_unrhdr(%d, %d)", low, high));
 475         if (mutex == UNR_NO_MTX)
 476                 uh->mtx = NULL;
 477         else if (mutex != NULL)
 478                 uh->mtx = mutex;
 479         else
 480                 uh->mtx = &unitmtx;
 481         TAILQ_INIT(&uh->head);
 482         TAILQ_INIT(&uh->ppfree);
 483         uh->low = low;
 484         uh->high = high;
 485         uh->first = 0;
 486         uh->last = 1 + (high - low);
 487         uh->busy = 0;
 488         uh->alloc = 0;
 489         check_unrhdr(uh, __LINE__);
 490 }
 491
 492 /*
 493  * Allocate a new unrheader set.
 494  *
 495  * Highest and lowest valid values given as parameters.
 496  */
 497
 498 struct unrhdr *
 499 new_unrhdr(int low, int high, struct mtx *mutex)
 500 {
 501         struct unrhdr *uh;
 502
 503         uh = Malloc(sizeof *uh);
 504         init_unrhdr(uh, low, high, mutex);
 505         return (uh);
 506 }
 507
 508 void
 509 delete_unrhdr(struct unrhdr *uh)
 510 {
 511
 512         check_unrhdr(uh, __LINE__);
 513         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
 514         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
 515         KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
 516             ("unrhdr has postponed item for free"));
 517         Free(uh);
 518 }
 519
 520 void
 521 clear_unrhdr(struct unrhdr *uh)
 522 {
 523         struct unr *up, *uq;
 524
 525         KASSERT(TAILQ_EMPTY(&uh->ppfree),
 526             ("unrhdr has postponed item for free"));
 527         TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
 528                 if (up->ptr != uh) {
 529                         Free(up->ptr);
 530                 }
 531                 Free(up);
 532         }
 533         uh->busy = 0;
 534         uh->alloc = 0;
 535         init_unrhdr(uh, uh->low, uh->high, uh->mtx);
 536
 537         check_unrhdr(uh, __LINE__);
 538 }
 539
 540 /*
 541  * Look for sequence of items which can be combined into a bitmap, if
 542  * multiple are present, take the one which saves most memory.
 543  *
 544  * Return (1) if a sequence was found to indicate that another call
 545  * might be able to do more.  Return (0) if we found no suitable sequence.
 546  *
 547  * NB: called from alloc_unr(), no new memory allocation allowed.
 548  */
 549 static int
 550 optimize_unr(struct unrhdr *uh)
 551 {
 552         struct unr *up, *uf, *us;
 553         struct unrb *ub, *ubf;
 554         u_int a, l, ba;
 555
 556         /*
 557          * Look for the run of items (if any) which when collapsed into
 558          * a bitmap would save most memory.
 559          */
 560         us = NULL;
 561         ba = 0;
 562         TAILQ_FOREACH(uf, &uh->head, list) {
 563                 if (uf->len >= NBITS)
 564                         continue;
 565                 a = 1;
 566                 if (is_bitmap(uh, uf))
 567                         a++;
 568                 l = uf->len;
 569                 up = uf;
 570                 while (1) {
 571                         up = TAILQ_NEXT(up, list);
 572                         if (up == NULL)
 573                                 break;
 574                         if ((up->len + l) > NBITS)
 575                                 break;
 576                         a++;
 577                         if (is_bitmap(uh, up))
 578                                 a++;
 579                         l += up->len;
 580                 }
 581                 if (a > ba) {
 582                         ba = a;
 583                         us = uf;
 584                 }
 585         }
 586         if (ba < 3)
 587                 return (0);
 588
 589         /*
 590          * If the first element is not a bitmap, make it one.
 591          * Trying to do so without allocating more memory complicates things
 592          * a bit
 593          */
 594         if (!is_bitmap(uh, us)) {
 595                 uf = TAILQ_NEXT(us, list);
 596                 TAILQ_REMOVE(&uh->head, us, list);
 597                 a = us->len;
 598                 l = us->ptr == uh ? 1 : 0;
 599                 ub = (void *)us;
 600                 bit_nclear(ub->map, 0, NBITS - 1);
 601                 if (l)
 602                         bit_nset(ub->map, 0, a);
 603                 if (!is_bitmap(uh, uf)) {
 604                         if (uf->ptr == NULL)
 605                                 bit_nclear(ub->map, a, a + uf->len - 1);
 606                         else
 607                                 bit_nset(ub->map, a, a + uf->len - 1);
 608                         uf->ptr = ub;
 609                         uf->len += a;
 610                         us = uf;
 611                 } else {
 612                         ubf = uf->ptr;
 613                         for (l = 0; l < uf->len; l++, a++) {
 614                                 if (bit_test(ubf->map, l))
 615                                         bit_set(ub->map, a);
 616                                 else
 617                                         bit_clear(ub->map, a);
 618                         }
 619                         uf->len = a;
 620                         delete_unr(uh, uf->ptr);
 621                         uf->ptr = ub;
 622                         us = uf;
 623                 }
 624         }
 625         ub = us->ptr;
 626         while (1) {
 627                 uf = TAILQ_NEXT(us, list);
 628                 if (uf == NULL)
 629                         return (1);
 630                 if (uf->len + us->len > NBITS)
 631                         return (1);
 632                 if (uf->ptr == NULL) {
 633                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
 634                         us->len += uf->len;
 635                         TAILQ_REMOVE(&uh->head, uf, list);
 636                         delete_unr(uh, uf);
 637                 } else if (uf->ptr == uh) {
 638                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
 639                         us->len += uf->len;
 640                         TAILQ_REMOVE(&uh->head, uf, list);
 641                         delete_unr(uh, uf);
 642                 } else {
 643                         ubf = uf->ptr;
 644                         for (l = 0; l < uf->len; l++, us->len++) {
 645                                 if (bit_test(ubf->map, l))
 646                                         bit_set(ub->map, us->len);
 647                                 else
 648                                         bit_clear(ub->map, us->len);
 649                         }
 650                         TAILQ_REMOVE(&uh->head, uf, list);
 651                         delete_unr(uh, ubf);
 652                         delete_unr(uh, uf);
 653                 }
 654         }
 655 }
 656
 657 /*
 658  * See if a given unr should be collapsed with a neighbor.
 659  *
 660  * NB: called from alloc_unr(), no new memory allocation allowed.
 661  */
 662 static void
 663 collapse_unr(struct unrhdr *uh, struct unr *up)
 664 {
 665         struct unr *upp;
 666         struct unrb *ub;
 667
 668         /* If bitmap is all set or clear, change it to runlength */
 669         if (is_bitmap(uh, up)) {
 670                 ub = up->ptr;
 671                 if (ub_full(ub, up->len)) {
 672                         delete_unr(uh, up->ptr);
 673                         up->ptr = uh;
 674                 } else if (ub_empty(ub, up->len)) {
 675                         delete_unr(uh, up->ptr);
 676                         up->ptr = NULL;
 677                 }
 678         }
 679
 680         /* If nothing left in runlength, delete it */
 681         if (up->len == 0) {
 682                 upp = TAILQ_PREV(up, unrhd, list);
 683                 if (upp == NULL)
 684                         upp = TAILQ_NEXT(up, list);
 685                 TAILQ_REMOVE(&uh->head, up, list);
 686                 delete_unr(uh, up);
 687                 up = upp;
 688         }
 689
 690         /* If we have "hot-spot" still, merge with neighbor if possible */
 691         if (up != NULL) {
 692                 upp = TAILQ_PREV(up, unrhd, list);
 693                 if (upp != NULL && up->ptr == upp->ptr) {
 694                         up->len += upp->len;
 695                         TAILQ_REMOVE(&uh->head, upp, list);
 696                         delete_unr(uh, upp);
 697                         }
 698                 upp = TAILQ_NEXT(up, list);
 699                 if (upp != NULL && up->ptr == upp->ptr) {
 700                         up->len += upp->len;
 701                         TAILQ_REMOVE(&uh->head, upp, list);
 702                         delete_unr(uh, upp);
 703                 }
 704         }
 705
 706         /* Merge into ->first if possible */
 707         upp = TAILQ_FIRST(&uh->head);
 708         if (upp != NULL && upp->ptr == uh) {
 709                 uh->first += upp->len;
 710                 TAILQ_REMOVE(&uh->head, upp, list);
 711                 delete_unr(uh, upp);
 712                 if (up == upp)
 713                         up = NULL;
 714         }
 715
 716         /* Merge into ->last if possible */
 717         upp = TAILQ_LAST(&uh->head, unrhd);
 718         if (upp != NULL && upp->ptr == NULL) {
 719                 uh->last += upp->len;
 720                 TAILQ_REMOVE(&uh->head, upp, list);
 721                 delete_unr(uh, upp);
 722                 if (up == upp)
 723                         up = NULL;
 724         }
 725
 726         /* Try to make bitmaps */
 727         while (optimize_unr(uh))
 728                 continue;
 729 }
 730
 731 /*
 732  * Allocate a free unr.
 733  */
 734 int
 735 alloc_unrl(struct unrhdr *uh)
 736 {
 737         struct unr *up;
 738         struct unrb *ub;
 739         u_int x;
 740         int y;
 741
 742         if (uh->mtx != NULL)
 743                 mtx_assert(uh->mtx, MA_OWNED);
 744         check_unrhdr(uh, __LINE__);
 745         x = uh->low + uh->first;
 746
 747         up = TAILQ_FIRST(&uh->head);
 748
 749         /*
 750          * If we have an ideal split, just adjust the first+last
 751          */
 752         if (up == NULL && uh->last > 0) {
 753                 uh->first++;
 754                 uh->last--;
 755                 uh->busy++;
 756                 return (x);
 757         }
 758
 759         /*
 760          * We can always allocate from the first list element, so if we have
 761          * nothing on the list, we must have run out of unit numbers.
 762          */
 763         if (up == NULL)
 764                 return (-1);
 765
 766         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
 767
 768         if (up->ptr == NULL) {  /* free run */
 769                 uh->first++;
 770                 up->len--;
 771         } else {                /* bitmap */
 772                 ub = up->ptr;
 773                 bit_ffc(ub->map, up->len, &y);
 774                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
 775                 bit_set(ub->map, y);
 776                 x += y;
 777         }
 778         uh->busy++;
 779         collapse_unr(uh, up);
 780         return (x);
 781 }
 782
 783 int
 784 alloc_unr(struct unrhdr *uh)
 785 {
 786         int i;
 787
 788         if (uh->mtx != NULL)
 789                 mtx_lock(uh->mtx);
 790         i = alloc_unrl(uh);
 791         clean_unrhdrl(uh);
 792         if (uh->mtx != NULL)
 793                 mtx_unlock(uh->mtx);
 794         return (i);
 795 }
 796
 797 static int
 798 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 799 {
 800         struct unr *up, *upn;
 801         struct unrb *ub;
 802         u_int i, last, tl;
 803
 804         if (uh->mtx != NULL)
 805                 mtx_assert(uh->mtx, MA_OWNED);
 806
 807         if (item < uh->low + uh->first || item > uh->high)
 808                 return (-1);
 809
 810         up = TAILQ_FIRST(&uh->head);
 811         /* Ideal split. */
 812         if (up == NULL && item - uh->low == uh->first) {
 813                 uh->first++;
 814                 uh->last--;
 815                 uh->busy++;
 816                 check_unrhdr(uh, __LINE__);
 817                 return (item);
 818         }
 819
 820         i = item - uh->low - uh->first;
 821
 822         if (up == NULL) {
 823                 up = new_unr(uh, p1, p2);
 824                 up->ptr = NULL;
 825                 up->len = i;
 826                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 827                 up = new_unr(uh, p1, p2);
 828                 up->ptr = uh;
 829                 up->len = 1;
 830                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 831                 uh->last = uh->high - uh->low - i;
 832                 uh->busy++;
 833                 check_unrhdr(uh, __LINE__);
 834                 return (item);
 835         } else {
 836                 /* Find the item which contains the unit we want to allocate. */
 837                 TAILQ_FOREACH(up, &uh->head, list) {
 838                         if (up->len > i)
 839                                 break;
 840                         i -= up->len;
 841                 }
 842         }
 843
 844         if (up == NULL) {
 845                 if (i > 0) {
 846                         up = new_unr(uh, p1, p2);
 847                         up->ptr = NULL;
 848                         up->len = i;
 849                         TAILQ_INSERT_TAIL(&uh->head, up, list);
 850                 }
 851                 up = new_unr(uh, p1, p2);
 852                 up->ptr = uh;
 853                 up->len = 1;
 854                 TAILQ_INSERT_TAIL(&uh->head, up, list);
 855                 goto done;
 856         }
 857
 858         if (is_bitmap(uh, up)) {
 859                 ub = up->ptr;
 860                 if (bit_test(ub->map, i) == 0) {
 861                         bit_set(ub->map, i);
 862                         goto done;
 863                 } else
 864                         return (-1);
 865         } else if (up->ptr == uh)
 866                 return (-1);
 867
 868         KASSERT(up->ptr == NULL,
 869             ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
 870
 871         /* Split off the tail end, if any. */
 872         tl = up->len - (1 + i);
 873         if (tl > 0) {
 874                 upn = new_unr(uh, p1, p2);
 875                 upn->ptr = NULL;
 876                 upn->len = tl;
 877                 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
 878         }
 879
 880         /* Split off head end, if any */
 881         if (i > 0) {
 882                 upn = new_unr(uh, p1, p2);
 883                 upn->len = i;
 884                 upn->ptr = NULL;
 885                 TAILQ_INSERT_BEFORE(up, upn, list);
 886         }
 887         up->len = 1;
 888         up->ptr = uh;
 889
 890 done:
 891         last = uh->high - uh->low - (item - uh->low);
 892         if (uh->last > last)
 893                 uh->last = last;
 894         uh->busy++;
 895         collapse_unr(uh, up);
 896         check_unrhdr(uh, __LINE__);
 897         return (item);
 898 }
 899
 900 int
 901 alloc_unr_specific(struct unrhdr *uh, u_int item)
 902 {
 903         void *p1, *p2;
 904         int i;
 905
 906         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
 907
 908         p1 = Malloc(sizeof(struct unr));
 909         p2 = Malloc(sizeof(struct unr));
 910
 911         if (uh->mtx != NULL)
 912                 mtx_lock(uh->mtx);
 913         i = alloc_unr_specificl(uh, item, &p1, &p2);
 914         if (uh->mtx != NULL)
 915                 mtx_unlock(uh->mtx);
 916
 917         if (p1 != NULL)
 918                 Free(p1);
 919         if (p2 != NULL)
 920                 Free(p2);
 921
 922         return (i);
 923 }
 924
 925 /*
 926  * Free a unr.
 927  *
 928  * If we can save unrs by using a bitmap, do so.
 929  */
 930 static void
 931 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
 932 {
 933         struct unr *up, *upp, *upn;
 934         struct unrb *ub;
 935         u_int pl;
 936
 937         KASSERT(item >= uh->low && item <= uh->high,
 938             ("UNR: free_unr(%u) out of range [%u...%u]",
 939              item, uh->low, uh->high));
 940         check_unrhdr(uh, __LINE__);
 941         item -= uh->low;
 942         upp = TAILQ_FIRST(&uh->head);
 943         /*
 944          * Freeing in the ideal split case
 945          */
 946         if (item + 1 == uh->first && upp == NULL) {
 947                 uh->last++;
 948                 uh->first--;
 949                 uh->busy--;
 950                 check_unrhdr(uh, __LINE__);
 951                 return;
 952         }
 953         /*
 954          * Freeing in the ->first section.  Create a run starting at the
 955          * freed item.  The code below will subdivide it.
 956          */
 957         if (item < uh->first) {
 958                 up = new_unr(uh, p1, p2);
 959                 up->ptr = uh;
 960                 up->len = uh->first - item;
 961                 TAILQ_INSERT_HEAD(&uh->head, up, list);
 962                 uh->first -= up->len;
 963         }
 964
 965         item -= uh->first;
 966
 967         /* Find the item which contains the unit we want to free */
 968         TAILQ_FOREACH(up, &uh->head, list) {
 969                 if (up->len > item)
 970                         break;
 971                 item -= up->len;
 972         }
 973
 974         /* Handle bitmap items */
 975         if (is_bitmap(uh, up)) {
 976                 ub = up->ptr;
 977
 978                 KASSERT(bit_test(ub->map, item) != 0,
 979                     ("UNR: Freeing free item %d (bitmap)\n", item));
 980                 bit_clear(ub->map, item);
 981                 uh->busy--;
 982                 collapse_unr(uh, up);
 983                 return;
 984         }
 985
 986         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
 987
 988         /* Just this one left, reap it */
 989         if (up->len == 1) {
 990                 up->ptr = NULL;
 991                 uh->busy--;
 992                 collapse_unr(uh, up);
 993                 return;
 994         }
 995
 996         /* Check if we can shift the item into the previous 'free' run */
 997         upp = TAILQ_PREV(up, unrhd, list);
 998         if (item == 0 && upp != NULL && upp->ptr == NULL) {
 999                 upp->len++;
1000                 up->len--;
1001                 uh->busy--;
1002                 collapse_unr(uh, up);
1003                 return;
1004         }
1005
1006         /* Check if we can shift the item to the next 'free' run */
1007         upn = TAILQ_NEXT(up, list);
1008         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
1009                 upn->len++;
1010                 up->len--;
1011                 uh->busy--;
1012                 collapse_unr(uh, up);
1013                 return;
1014         }
1015
1016         /* Split off the tail end, if any. */
1017         pl = up->len - (1 + item);
1018         if (pl > 0) {
1019                 upp = new_unr(uh, p1, p2);
1020                 upp->ptr = uh;
1021                 upp->len = pl;
1022                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
1023         }
1024
1025         /* Split off head end, if any */
1026         if (item > 0) {
1027                 upp = new_unr(uh, p1, p2);
1028                 upp->len = item;
1029                 upp->ptr = uh;
1030                 TAILQ_INSERT_BEFORE(up, upp, list);
1031         }
1032         up->len = 1;
1033         up->ptr = NULL;
1034         uh->busy--;
1035         collapse_unr(uh, up);
1036 }
1037
1038 void
1039 free_unr(struct unrhdr *uh, u_int item)
1040 {
1041         void *p1, *p2;
1042
1043         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
1044         p1 = Malloc(sizeof(struct unr));
1045         p2 = Malloc(sizeof(struct unr));
1046         if (uh->mtx != NULL)
1047                 mtx_lock(uh->mtx);
1048         free_unrl(uh, item, &p1, &p2);
1049         clean_unrhdrl(uh);
1050         if (uh->mtx != NULL)
1051                 mtx_unlock(uh->mtx);
1052         if (p1 != NULL)
1053                 Free(p1);
1054         if (p2 != NULL)
1055                 Free(p2);
1056 }
1057
1058 #ifdef _KERNEL
1059 #include "opt_ddb.h"
1060 #ifdef DDB
1061 #include <ddb/ddb.h>
1062 #endif
1063 #endif
1064
1065 #if (defined(_KERNEL) && defined(DDB)) || !defined(_KERNEL)
1066
1067 #if !defined(_KERNEL)
1068 #define db_printf printf
1069 #endif
1070
1071 static void
1072 print_unr(struct unrhdr *uh, struct unr *up)
1073 {
1074         u_int x;
1075         struct unrb *ub;
1076
1077         db_printf("  %p len = %5u ", up, up->len);
1078         if (up->ptr == NULL)
1079                 db_printf("free\n");
1080         else if (up->ptr == uh)
1081                 db_printf("alloc\n");
1082         else {
1083                 ub = up->ptr;
1084                 db_printf("bitmap [");
1085                 for (x = 0; x < up->len; x++) {
1086                         if (bit_test(ub->map, x))
1087                                 db_printf("#");
1088                         else
1089                                 db_printf(" ");
1090                 }
1091                 db_printf("]\n");
1092         }
1093 }
1094
1095 static void
1096 print_unrhdr(struct unrhdr *uh)
1097 {
1098         struct unr *up;
1099         u_int x;
1100
1101         db_printf(
1102             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
1103             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
1104         x = uh->low + uh->first;
1105         TAILQ_FOREACH(up, &uh->head, list) {
1106                 db_printf("  from = %5u", x);
1107                 print_unr(uh, up);
1108                 if (up->ptr == NULL || up->ptr == uh)
1109                         x += up->len;
1110                 else
1111                         x += NBITS;
1112         }
1113 }
1114
1115 #endif
1116
1117 #if defined(_KERNEL) && defined(DDB)
1118 DB_SHOW_COMMAND(unrhdr, unrhdr_print_unrhdr)
1119 {
1120         if (!have_addr) {
1121                 db_printf("show unrhdr addr\n");
1122                 return;
1123         }
1124
1125         print_unrhdr((struct unrhdr *)addr);
1126 }
1127
1128 static void
1129 print_unrhdr_iter(struct unrhdr_iter *iter)
1130 {
1131         db_printf("iter %p unrhdr %p ipos %d upos %p ufi %d\n",
1132             iter, iter->uh, iter->ipos, iter->upos, iter->upos_first_item);
1133 }
1134
1135 DB_SHOW_COMMAND(unrhdr_iter, unrhdr_print_iter)
1136 {
1137         if (!have_addr) {
1138                 db_printf("show unrhdr_iter addr\n");
1139                 return;
1140         }
1141
1142         print_unrhdr_iter((struct unrhdr_iter *)addr);
1143 }
1144 #endif
1145
1146 #ifndef _KERNEL /* USERLAND test driver */
1147
1148 /*
1149  * Simple stochastic test driver for the above functions.  The code resides
1150  * here so that it can access static functions and structures.
1151  */
1152
1153 static bool verbose;
1154 #define VPRINTF(...)    {if (verbose) printf(__VA_ARGS__);}
1155
1156 static void
1157 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
1158 {
1159         int j;
1160
1161         if (a[i]) {
1162                 VPRINTF("F %u\n", i);
1163                 free_unr(uh, i);
1164                 a[i] = 0;
1165         } else {
1166                 no_alloc = 1;
1167                 j = alloc_unr(uh);
1168                 if (j != -1) {
1169                         a[j] = 1;
1170                         VPRINTF("A %d\n", j);
1171                 }
1172                 no_alloc = 0;
1173         }
1174 }
1175
1176 static void
1177 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
1178 {
1179         int j;
1180
1181         j = alloc_unr_specific(uh, i);
1182         if (j == -1) {
1183                 VPRINTF("F %u\n", i);
1184                 a[i] = 0;
1185                 free_unr(uh, i);
1186         } else {
1187                 a[i] = 1;
1188                 VPRINTF("A %d\n", j);
1189         }
1190 }
1191
1192 #define TBASE   7
1193 #define XSIZE   10
1194 #define ISIZE   1000
1195
1196 static int
1197 test_iter_compar(const void *a, const void *b)
1198 {
1199         return (*(const int *)a - *(const int *)b);
1200 }
1201
1202 static void
1203 test_iter_fill(int *vals, struct unrhdr *uh, int i, int v, int *res)
1204 {
1205         int x;
1206
1207         vals[i] = v;
1208         x = alloc_unr_specific(uh, v);
1209         if (x != v) {
1210                 VPRINTF("alloc_unr_specific failed %d %d\n", x, v);
1211                 *res = 1;
1212         }
1213 }
1214
1215 static void
1216 test_iter(void)
1217 {
1218         struct unrhdr *uh;
1219         void *ihandle;
1220         int vals[ISIZE];
1221         int i, j, v, x, res;
1222
1223         res = 0;
1224         uh = new_unrhdr(TBASE, INT_MAX, NULL);
1225         for (i = 0; i < XSIZE; i++) {
1226                 vals[i] = i + TBASE;
1227                 x = alloc_unr_specific(uh, i + TBASE);
1228                 if (x != i + TBASE) {
1229                         VPRINTF("alloc_unr_specific failed %d %d\n", x,
1230                             i + TBASE);
1231                         res = 1;
1232                 }
1233         }
1234         for (; i < ISIZE; i++) {
1235                 for (;;) {
1236 again:
1237                         v = arc4random_uniform(INT_MAX);
1238                         if (v < TBASE)
1239                                 goto again;
1240                         for (j = 0; j < i; j++) {
1241                                 if (v == vals[j] || v + 1 == vals[j])
1242                                         goto again;
1243                         }
1244                         break;
1245                 }
1246                 test_iter_fill(vals, uh, i, v, &res);
1247                 i++, v++;
1248                 if (i < ISIZE)
1249                         test_iter_fill(vals, uh, i, v, &res);
1250         }
1251         qsort(vals, ISIZE, sizeof(vals[0]), test_iter_compar);
1252
1253         ihandle = create_iter_unr(uh);
1254         i = 0;
1255         while ((v = next_iter_unr(ihandle)) != -1) {
1256                 if (vals[i] != v) {
1257                         VPRINTF("iter %d: iter %d != val %d\n", i, v, vals[i]);
1258                         if (res == 0) {
1259                                 if (verbose)
1260                                         print_unrhdr(uh);
1261                                 res = 1;
1262                         }
1263                 } else {
1264                         VPRINTF("iter %d: val %d\n", i, v);
1265                 }
1266                 i++;
1267         }
1268         free_iter_unr(ihandle);
1269         clean_unrhdr(uh);
1270         clear_unrhdr(uh);
1271         delete_unrhdr(uh);
1272         exit(res);
1273 }
1274
1275 static void
1276 usage(char **argv)
1277 {
1278         printf("%s [-h] [-i] [-r REPETITIONS] [-v]\n", argv[0]);
1279 }
1280
1281 int
1282 main(int argc, char **argv)
1283 {
1284         struct unrhdr *uh;
1285         char *a;
1286         long count = 10000;     /* Number of unrs to test */
1287         long reps = 1, m;
1288         int ch;
1289         u_int i;
1290         bool testing_iter;
1291
1292         verbose = false;
1293         testing_iter = false;
1294
1295         while ((ch = getopt(argc, argv, "hir:v")) != -1) {
1296                 switch (ch) {
1297                 case 'i':
1298                         testing_iter = true;
1299                         break;
1300                 case 'r':
1301                         errno = 0;
1302                         reps = strtol(optarg, NULL, 0);
1303                         if (errno == ERANGE || errno == EINVAL) {
1304                                 usage(argv);
1305                                 exit(2);
1306                         }
1307
1308                         break;
1309                 case 'v':
1310                         verbose = true;
1311                         break;
1312                 case 'h':
1313                 default:
1314                         usage(argv);
1315                         exit(2);
1316                 }
1317         }
1318
1319         setbuf(stdout, NULL);
1320
1321         if (testing_iter)
1322                 test_iter();
1323
1324         uh = new_unrhdr(0, count - 1, NULL);
1325         print_unrhdr(uh);
1326
1327         a = calloc(count, sizeof(char));
1328         if (a == NULL)
1329                 err(1, "calloc failed");
1330
1331         printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
1332         printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
1333         printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
1334         printf("NBITS %lu\n", (unsigned long)NBITS);
1335         for (m = 0; m < count * reps; m++) {
1336                 i = arc4random_uniform(count);
1337 #if 0
1338                 if (a[i] && (j & 1))
1339                         continue;
1340 #endif
1341                 if ((arc4random() & 1) != 0)
1342                         test_alloc_unr(uh, i, a);
1343                 else
1344                         test_alloc_unr_specific(uh, i, a);
1345
1346                 if (verbose)
1347                         print_unrhdr(uh);
1348                 check_unrhdr(uh, __LINE__);
1349         }
1350         for (i = 0; i < (u_int)count; i++) {
1351                 if (a[i]) {
1352                         if (verbose) {
1353                                 printf("C %u\n", i);
1354                                 print_unrhdr(uh);
1355                         }
1356                         free_unr(uh, i);
1357                 }
1358         }
1359         print_unrhdr(uh);
1360         delete_unrhdr(uh);
1361         free(a);
1362         return (0);
1363 }
1364 #endif