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: stable/10/sys/kern/subr_unit.c 312325 2017-01-17 01:58:50Z ngie $ 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/bitstring.h> 72#include <sys/_unrhdr.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 */ 90static 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 95static struct mtx unitmtx; 96 97MTX_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 113static int no_alloc; 114#define Malloc(foo) _Malloc(foo, __LINE__) 115static 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 124struct unrhdr; 125 126 127struct mtx { 128 int state; 129} unitmtx; 130 131static void 132mtx_lock(struct mtx *mp) 133{ 134 KASSERT(mp->state == 0, ("mutex already locked")); 135 mp->state = 1; 136} 137 138static void 139mtx_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 147static void 148mtx_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 */ 174struct unr { 175 TAILQ_ENTRY(unr) list; 176 u_int len; 177 void *ptr; 178}; 179 180struct unrb { 181 u_char busy; 182 bitstr_t map[sizeof(struct unr) - 1]; 183}; 184 185CTASSERT(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#if defined(DIAGNOSTIC) || !defined(_KERNEL) 191/* 192 * Consistency check function. 193 * 194 * Checks the internal consistency as well as we can. 195 * 196 * Called at all boundaries of this API. 197 */ 198static void 199check_unrhdr(struct unrhdr *uh, int line) 200{ 201 struct unr *up; 202 struct unrb *ub; 203 u_int x, y, z, w; 204 205 y = uh->first; 206 z = 0; 207 TAILQ_FOREACH(up, &uh->head, list) { 208 z++; 209 if (up->ptr != uh && up->ptr != NULL) { 210 ub = up->ptr; 211 KASSERT (up->len <= NBITS, 212 ("UNR inconsistency: len %u max %d (line %d)\n", 213 up->len, NBITS, line)); 214 z++; 215 w = 0; 216 for (x = 0; x < up->len; x++) 217 if (bit_test(ub->map, x)) 218 w++; 219 KASSERT (w == ub->busy, 220 ("UNR inconsistency: busy %u found %u (line %d)\n", 221 ub->busy, w, line)); 222 y += w; 223 } else if (up->ptr != NULL) 224 y += up->len; 225 } 226 KASSERT (y == uh->busy, 227 ("UNR inconsistency: items %u found %u (line %d)\n", 228 uh->busy, y, line)); 229 KASSERT (z == uh->alloc, 230 ("UNR inconsistency: chunks %u found %u (line %d)\n", 231 uh->alloc, z, line)); 232} 233 234#else 235 236static __inline void 237check_unrhdr(struct unrhdr *uh, int line) 238{ 239 240} 241 242#endif 243 244 245/* 246 * Userland memory management. Just use calloc and keep track of how 247 * many elements we have allocated for check_unrhdr(). 248 */ 249 250static __inline void * 251new_unr(struct unrhdr *uh, void **p1, void **p2) 252{ 253 void *p; 254 255 uh->alloc++; 256 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory")); 257 if (*p1 != NULL) { 258 p = *p1; 259 *p1 = NULL; 260 return (p); 261 } else { 262 p = *p2; 263 *p2 = NULL; 264 return (p); 265 } 266} 267 268static __inline void 269delete_unr(struct unrhdr *uh, void *ptr) 270{ 271 struct unr *up; 272 273 uh->alloc--; 274 up = ptr; 275 TAILQ_INSERT_TAIL(&uh->ppfree, up, list); 276} 277 278void 279clean_unrhdrl(struct unrhdr *uh) 280{ 281 struct unr *up; 282 283 mtx_assert(uh->mtx, MA_OWNED); 284 while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) { 285 TAILQ_REMOVE(&uh->ppfree, up, list); 286 mtx_unlock(uh->mtx); 287 Free(up); 288 mtx_lock(uh->mtx); 289 } 290 291} 292 293void 294clean_unrhdr(struct unrhdr *uh) 295{ 296 297 mtx_lock(uh->mtx); 298 clean_unrhdrl(uh); 299 mtx_unlock(uh->mtx); 300} 301 302void 303init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex) 304{ 305 306 KASSERT(low >= 0 && low <= high, 307 ("UNR: use error: new_unrhdr(%d, %d)", low, high)); 308 if (mutex != NULL) 309 uh->mtx = mutex; 310 else 311 uh->mtx = &unitmtx; 312 TAILQ_INIT(&uh->head); 313 TAILQ_INIT(&uh->ppfree); 314 uh->low = low; 315 uh->high = high; 316 uh->first = 0; 317 uh->last = 1 + (high - low); 318 check_unrhdr(uh, __LINE__); 319} 320 321/* 322 * Allocate a new unrheader set. 323 * 324 * Highest and lowest valid values given as parameters. 325 */ 326 327struct unrhdr * 328new_unrhdr(int low, int high, struct mtx *mutex) 329{ 330 struct unrhdr *uh; 331 332 uh = Malloc(sizeof *uh); 333 init_unrhdr(uh, low, high, mutex); 334 return (uh); 335} 336 337void 338delete_unrhdr(struct unrhdr *uh) 339{ 340 341 check_unrhdr(uh, __LINE__); 342 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy)); 343 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr")); 344 KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL, 345 ("unrhdr has postponed item for free")); 346 Free(uh); 347} 348 349static __inline int 350is_bitmap(struct unrhdr *uh, struct unr *up) 351{ 352 return (up->ptr != uh && up->ptr != NULL); 353} 354 355/* 356 * Look for sequence of items which can be combined into a bitmap, if 357 * multiple are present, take the one which saves most memory. 358 * 359 * Return (1) if a sequence was found to indicate that another call 360 * might be able to do more. Return (0) if we found no suitable sequence. 361 * 362 * NB: called from alloc_unr(), no new memory allocation allowed. 363 */ 364static int 365optimize_unr(struct unrhdr *uh) 366{ 367 struct unr *up, *uf, *us; 368 struct unrb *ub, *ubf; 369 u_int a, l, ba; 370 371 /* 372 * Look for the run of items (if any) which when collapsed into 373 * a bitmap would save most memory. 374 */ 375 us = NULL; 376 ba = 0; 377 TAILQ_FOREACH(uf, &uh->head, list) { 378 if (uf->len >= NBITS) 379 continue; 380 a = 1; 381 if (is_bitmap(uh, uf)) 382 a++; 383 l = uf->len; 384 up = uf; 385 while (1) { 386 up = TAILQ_NEXT(up, list); 387 if (up == NULL) 388 break; 389 if ((up->len + l) > NBITS) 390 break; 391 a++; 392 if (is_bitmap(uh, up)) 393 a++; 394 l += up->len; 395 } 396 if (a > ba) { 397 ba = a; 398 us = uf; 399 } 400 } 401 if (ba < 3) 402 return (0); 403 404 /* 405 * If the first element is not a bitmap, make it one. 406 * Trying to do so without allocating more memory complicates things 407 * a bit 408 */ 409 if (!is_bitmap(uh, us)) { 410 uf = TAILQ_NEXT(us, list); 411 TAILQ_REMOVE(&uh->head, us, list); 412 a = us->len; 413 l = us->ptr == uh ? 1 : 0; 414 ub = (void *)us; 415 ub->busy = 0; 416 if (l) { 417 bit_nset(ub->map, 0, a); 418 ub->busy += a; 419 } else { 420 bit_nclear(ub->map, 0, a); 421 } 422 if (!is_bitmap(uh, uf)) { 423 if (uf->ptr == NULL) { 424 bit_nclear(ub->map, a, a + uf->len - 1); 425 } else { 426 bit_nset(ub->map, a, a + uf->len - 1); 427 ub->busy += uf->len; 428 } 429 uf->ptr = ub; 430 uf->len += a; 431 us = uf; 432 } else { 433 ubf = uf->ptr; 434 for (l = 0; l < uf->len; l++, a++) { 435 if (bit_test(ubf->map, l)) { 436 bit_set(ub->map, a); 437 ub->busy++; 438 } else { 439 bit_clear(ub->map, a); 440 } 441 } 442 uf->len = a; 443 delete_unr(uh, uf->ptr); 444 uf->ptr = ub; 445 us = uf; 446 } 447 } 448 ub = us->ptr; 449 while (1) { 450 uf = TAILQ_NEXT(us, list); 451 if (uf == NULL) 452 return (1); 453 if (uf->len + us->len > NBITS) 454 return (1); 455 if (uf->ptr == NULL) { 456 bit_nclear(ub->map, us->len, us->len + uf->len - 1); 457 us->len += uf->len; 458 TAILQ_REMOVE(&uh->head, uf, list); 459 delete_unr(uh, uf); 460 } else if (uf->ptr == uh) { 461 bit_nset(ub->map, us->len, us->len + uf->len - 1); 462 ub->busy += uf->len; 463 us->len += uf->len; 464 TAILQ_REMOVE(&uh->head, uf, list); 465 delete_unr(uh, uf); 466 } else { 467 ubf = uf->ptr; 468 for (l = 0; l < uf->len; l++, us->len++) { 469 if (bit_test(ubf->map, l)) { 470 bit_set(ub->map, us->len); 471 ub->busy++; 472 } else { 473 bit_clear(ub->map, us->len); 474 } 475 } 476 TAILQ_REMOVE(&uh->head, uf, list); 477 delete_unr(uh, ubf); 478 delete_unr(uh, uf); 479 } 480 } 481} 482 483/* 484 * See if a given unr should be collapsed with a neighbor. 485 * 486 * NB: called from alloc_unr(), no new memory allocation allowed. 487 */ 488static void 489collapse_unr(struct unrhdr *uh, struct unr *up) 490{ 491 struct unr *upp; 492 struct unrb *ub; 493 494 /* If bitmap is all set or clear, change it to runlength */ 495 if (is_bitmap(uh, up)) { 496 ub = up->ptr; 497 if (ub->busy == up->len) { 498 delete_unr(uh, up->ptr); 499 up->ptr = uh; 500 } else if (ub->busy == 0) { 501 delete_unr(uh, up->ptr); 502 up->ptr = NULL; 503 } 504 } 505 506 /* If nothing left in runlength, delete it */ 507 if (up->len == 0) { 508 upp = TAILQ_PREV(up, unrhd, list); 509 if (upp == NULL) 510 upp = TAILQ_NEXT(up, list); 511 TAILQ_REMOVE(&uh->head, up, list); 512 delete_unr(uh, up); 513 up = upp; 514 } 515 516 /* If we have "hot-spot" still, merge with neighbor if possible */ 517 if (up != NULL) { 518 upp = TAILQ_PREV(up, unrhd, list); 519 if (upp != NULL && up->ptr == upp->ptr) { 520 up->len += upp->len; 521 TAILQ_REMOVE(&uh->head, upp, list); 522 delete_unr(uh, upp); 523 } 524 upp = TAILQ_NEXT(up, list); 525 if (upp != NULL && up->ptr == upp->ptr) { 526 up->len += upp->len; 527 TAILQ_REMOVE(&uh->head, upp, list); 528 delete_unr(uh, upp); 529 } 530 } 531 532 /* Merge into ->first if possible */ 533 upp = TAILQ_FIRST(&uh->head); 534 if (upp != NULL && upp->ptr == uh) { 535 uh->first += upp->len; 536 TAILQ_REMOVE(&uh->head, upp, list); 537 delete_unr(uh, upp); 538 if (up == upp) 539 up = NULL; 540 } 541 542 /* Merge into ->last if possible */ 543 upp = TAILQ_LAST(&uh->head, unrhd); 544 if (upp != NULL && upp->ptr == NULL) { 545 uh->last += upp->len; 546 TAILQ_REMOVE(&uh->head, upp, list); 547 delete_unr(uh, upp); 548 if (up == upp) 549 up = NULL; 550 } 551 552 /* Try to make bitmaps */ 553 while (optimize_unr(uh)) 554 continue; 555} 556 557/* 558 * Allocate a free unr. 559 */ 560int 561alloc_unrl(struct unrhdr *uh) 562{ 563 struct unr *up; 564 struct unrb *ub; 565 u_int x; 566 int y; 567 568 mtx_assert(uh->mtx, MA_OWNED); 569 check_unrhdr(uh, __LINE__); 570 x = uh->low + uh->first; 571 572 up = TAILQ_FIRST(&uh->head); 573 574 /* 575 * If we have an ideal split, just adjust the first+last 576 */ 577 if (up == NULL && uh->last > 0) { 578 uh->first++; 579 uh->last--; 580 uh->busy++; 581 return (x); 582 } 583 584 /* 585 * We can always allocate from the first list element, so if we have 586 * nothing on the list, we must have run out of unit numbers. 587 */ 588 if (up == NULL) 589 return (-1); 590 591 KASSERT(up->ptr != uh, ("UNR first element is allocated")); 592 593 if (up->ptr == NULL) { /* free run */ 594 uh->first++; 595 up->len--; 596 } else { /* bitmap */ 597 ub = up->ptr; 598 KASSERT(ub->busy < up->len, ("UNR bitmap confusion")); 599 bit_ffc(ub->map, up->len, &y); 600 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap.")); 601 bit_set(ub->map, y); 602 ub->busy++; 603 x += y; 604 } 605 uh->busy++; 606 collapse_unr(uh, up); 607 return (x); 608} 609 610int 611alloc_unr(struct unrhdr *uh) 612{ 613 int i; 614 615 mtx_lock(uh->mtx); 616 i = alloc_unrl(uh); 617 clean_unrhdrl(uh); 618 mtx_unlock(uh->mtx); 619 return (i); 620} 621 622static int 623alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2) 624{ 625 struct unr *up, *upn; 626 struct unrb *ub; 627 u_int i, last, tl; 628 629 mtx_assert(uh->mtx, MA_OWNED); 630 631 if (item < uh->low + uh->first || item > uh->high) 632 return (-1); 633 634 up = TAILQ_FIRST(&uh->head); 635 /* Ideal split. */ 636 if (up == NULL && item - uh->low == uh->first) { 637 uh->first++; 638 uh->last--; 639 uh->busy++; 640 check_unrhdr(uh, __LINE__); 641 return (item); 642 } 643 644 i = item - uh->low - uh->first; 645 646 if (up == NULL) { 647 up = new_unr(uh, p1, p2); 648 up->ptr = NULL; 649 up->len = i; 650 TAILQ_INSERT_TAIL(&uh->head, up, list); 651 up = new_unr(uh, p1, p2); 652 up->ptr = uh; 653 up->len = 1; 654 TAILQ_INSERT_TAIL(&uh->head, up, list); 655 uh->last = uh->high - uh->low - i; 656 uh->busy++; 657 check_unrhdr(uh, __LINE__); 658 return (item); 659 } else { 660 /* Find the item which contains the unit we want to allocate. */ 661 TAILQ_FOREACH(up, &uh->head, list) { 662 if (up->len > i) 663 break; 664 i -= up->len; 665 } 666 } 667 668 if (up == NULL) { 669 if (i > 0) { 670 up = new_unr(uh, p1, p2); 671 up->ptr = NULL; 672 up->len = i; 673 TAILQ_INSERT_TAIL(&uh->head, up, list); 674 } 675 up = new_unr(uh, p1, p2); 676 up->ptr = uh; 677 up->len = 1; 678 TAILQ_INSERT_TAIL(&uh->head, up, list); 679 goto done; 680 } 681 682 if (is_bitmap(uh, up)) { 683 ub = up->ptr; 684 if (bit_test(ub->map, i) == 0) { 685 bit_set(ub->map, i); 686 ub->busy++; 687 goto done; 688 } else 689 return (-1); 690 } else if (up->ptr == uh) 691 return (-1); 692 693 KASSERT(up->ptr == NULL, 694 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up)); 695 696 /* Split off the tail end, if any. */ 697 tl = up->len - (1 + i); 698 if (tl > 0) { 699 upn = new_unr(uh, p1, p2); 700 upn->ptr = NULL; 701 upn->len = tl; 702 TAILQ_INSERT_AFTER(&uh->head, up, upn, list); 703 } 704 705 /* Split off head end, if any */ 706 if (i > 0) { 707 upn = new_unr(uh, p1, p2); 708 upn->len = i; 709 upn->ptr = NULL; 710 TAILQ_INSERT_BEFORE(up, upn, list); 711 } 712 up->len = 1; 713 up->ptr = uh; 714 715done: 716 last = uh->high - uh->low - (item - uh->low); 717 if (uh->last > last) 718 uh->last = last; 719 uh->busy++; 720 collapse_unr(uh, up); 721 check_unrhdr(uh, __LINE__); 722 return (item); 723} 724 725int 726alloc_unr_specific(struct unrhdr *uh, u_int item) 727{ 728 void *p1, *p2; 729 int i; 730 731 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific"); 732 733 p1 = Malloc(sizeof(struct unr)); 734 p2 = Malloc(sizeof(struct unr)); 735 736 mtx_lock(uh->mtx); 737 i = alloc_unr_specificl(uh, item, &p1, &p2); 738 mtx_unlock(uh->mtx); 739 740 if (p1 != NULL) 741 Free(p1); 742 if (p2 != NULL) 743 Free(p2); 744 745 return (i); 746} 747 748/* 749 * Free a unr. 750 * 751 * If we can save unrs by using a bitmap, do so. 752 */ 753static void 754free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2) 755{ 756 struct unr *up, *upp, *upn; 757 struct unrb *ub; 758 u_int pl; 759 760 KASSERT(item >= uh->low && item <= uh->high, 761 ("UNR: free_unr(%u) out of range [%u...%u]", 762 item, uh->low, uh->high)); 763 check_unrhdr(uh, __LINE__); 764 item -= uh->low; 765 upp = TAILQ_FIRST(&uh->head); 766 /* 767 * Freeing in the ideal split case 768 */ 769 if (item + 1 == uh->first && upp == NULL) { 770 uh->last++; 771 uh->first--; 772 uh->busy--; 773 check_unrhdr(uh, __LINE__); 774 return; 775 } 776 /* 777 * Freeing in the ->first section. Create a run starting at the 778 * freed item. The code below will subdivide it. 779 */ 780 if (item < uh->first) { 781 up = new_unr(uh, p1, p2); 782 up->ptr = uh; 783 up->len = uh->first - item; 784 TAILQ_INSERT_HEAD(&uh->head, up, list); 785 uh->first -= up->len; 786 } 787 788 item -= uh->first; 789 790 /* Find the item which contains the unit we want to free */ 791 TAILQ_FOREACH(up, &uh->head, list) { 792 if (up->len > item) 793 break; 794 item -= up->len; 795 } 796 797 /* Handle bitmap items */ 798 if (is_bitmap(uh, up)) { 799 ub = up->ptr; 800 801 KASSERT(bit_test(ub->map, item) != 0, 802 ("UNR: Freeing free item %d (bitmap)\n", item)); 803 bit_clear(ub->map, item); 804 uh->busy--; 805 ub->busy--; 806 collapse_unr(uh, up); 807 return; 808 } 809 810 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item)); 811 812 /* Just this one left, reap it */ 813 if (up->len == 1) { 814 up->ptr = NULL; 815 uh->busy--; 816 collapse_unr(uh, up); 817 return; 818 } 819 820 /* Check if we can shift the item into the previous 'free' run */ 821 upp = TAILQ_PREV(up, unrhd, list); 822 if (item == 0 && upp != NULL && upp->ptr == NULL) { 823 upp->len++; 824 up->len--; 825 uh->busy--; 826 collapse_unr(uh, up); 827 return; 828 } 829 830 /* Check if we can shift the item to the next 'free' run */ 831 upn = TAILQ_NEXT(up, list); 832 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) { 833 upn->len++; 834 up->len--; 835 uh->busy--; 836 collapse_unr(uh, up); 837 return; 838 } 839 840 /* Split off the tail end, if any. */ 841 pl = up->len - (1 + item); 842 if (pl > 0) { 843 upp = new_unr(uh, p1, p2); 844 upp->ptr = uh; 845 upp->len = pl; 846 TAILQ_INSERT_AFTER(&uh->head, up, upp, list); 847 } 848 849 /* Split off head end, if any */ 850 if (item > 0) { 851 upp = new_unr(uh, p1, p2); 852 upp->len = item; 853 upp->ptr = uh; 854 TAILQ_INSERT_BEFORE(up, upp, list); 855 } 856 up->len = 1; 857 up->ptr = NULL; 858 uh->busy--; 859 collapse_unr(uh, up); 860} 861 862void 863free_unr(struct unrhdr *uh, u_int item) 864{ 865 void *p1, *p2; 866 867 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr"); 868 p1 = Malloc(sizeof(struct unr)); 869 p2 = Malloc(sizeof(struct unr)); 870 mtx_lock(uh->mtx); 871 free_unrl(uh, item, &p1, &p2); 872 clean_unrhdrl(uh); 873 mtx_unlock(uh->mtx); 874 if (p1 != NULL) 875 Free(p1); 876 if (p2 != NULL) 877 Free(p2); 878} 879 880#ifndef _KERNEL /* USERLAND test driver */ 881 882/* 883 * Simple stochastic test driver for the above functions 884 */ 885 886static void 887print_unr(struct unrhdr *uh, struct unr *up) 888{ 889 u_int x; 890 struct unrb *ub; 891 892 printf(" %p len = %5u ", up, up->len); 893 if (up->ptr == NULL) 894 printf("free\n"); 895 else if (up->ptr == uh) 896 printf("alloc\n"); 897 else { 898 ub = up->ptr; 899 printf("bitmap(%d) [", ub->busy); 900 for (x = 0; x < up->len; x++) { 901 if (bit_test(ub->map, x)) 902 printf("#"); 903 else 904 printf(" "); 905 } 906 printf("]\n"); 907 } 908} 909 910static void 911print_unrhdr(struct unrhdr *uh) 912{ 913 struct unr *up; 914 u_int x; 915 916 printf( 917 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n", 918 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc); 919 x = uh->low + uh->first; 920 TAILQ_FOREACH(up, &uh->head, list) { 921 printf(" from = %5u", x); 922 print_unr(uh, up); 923 if (up->ptr == NULL || up->ptr == uh) 924 x += up->len; 925 else 926 x += NBITS; 927 } 928} 929 930static void 931test_alloc_unr(struct unrhdr *uh, u_int i, char a[]) 932{ 933 int j; 934 935 if (a[i]) { 936 printf("F %u\n", i); 937 free_unr(uh, i); 938 a[i] = 0; 939 } else { 940 no_alloc = 1; 941 j = alloc_unr(uh); 942 if (j != -1) { 943 a[j] = 1; 944 printf("A %d\n", j); 945 } 946 no_alloc = 0; 947 } 948} 949 950static void 951test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[]) 952{ 953 int j; 954 955 j = alloc_unr_specific(uh, i); 956 if (j == -1) { 957 printf("F %u\n", i); 958 a[i] = 0; 959 free_unr(uh, i); 960 } else { 961 a[i] = 1; 962 printf("A %d\n", j); 963 } 964} 965 966/* Number of unrs to test */ 967#define NN 10000 968 969int 970main(int argc __unused, const char **argv __unused) 971{ 972 struct unrhdr *uh; 973 u_int i, x, m, j; 974 char a[NN]; 975 976 setbuf(stdout, NULL); 977 uh = new_unrhdr(0, NN - 1, NULL); 978 print_unrhdr(uh); 979 980 memset(a, 0, sizeof a); 981 srandomdev(); 982 983 fprintf(stderr, "sizeof(struct unr) %zu\n", sizeof(struct unr)); 984 fprintf(stderr, "sizeof(struct unrb) %zu\n", sizeof(struct unrb)); 985 fprintf(stderr, "sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr)); 986 fprintf(stderr, "NBITS %d\n", NBITS); 987 x = 1; 988 for (m = 0; m < NN * 100; m++) { 989 j = random(); 990 i = (j >> 1) % NN; 991#if 0 992 if (a[i] && (j & 1)) 993 continue; 994#endif 995 if ((random() & 1) != 0) 996 test_alloc_unr(uh, i, a); 997 else 998 test_alloc_unr_specific(uh, i, a); 999 1000 if (1) /* XXX: change this for detailed debug printout */ 1001 print_unrhdr(uh); 1002 check_unrhdr(uh, __LINE__); 1003 } 1004 for (i = 0; i < NN; i++) { 1005 if (a[i]) { 1006 printf("C %u\n", i); 1007 free_unr(uh, i); 1008 print_unrhdr(uh); 1009 } 1010 } 1011 print_unrhdr(uh); 1012 delete_unrhdr(uh); 1013 return (0); 1014} 1015#endif 1016