sys/kern/subr_unit.c

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