subr_unit.c revision 209710
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: head/sys/kern/subr_unit.c 209710 2010-07-05 16:23:55Z jh $ 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 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 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 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 */ 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/* Header element for a unr number space. */ 191 192struct 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 */ 214static void 215check_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 252static __inline void 253check_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 266static __inline void * 267new_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 284static __inline void 285delete_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 294void 295clean_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 309void 310clean_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 324struct unrhdr * 325new_unrhdr(int low, int high, struct mtx *mutex) 326{ 327 struct unrhdr *uh; 328 329 KASSERT(low <= high, 330 ("UNR: use error: new_unrhdr(%u, %u)", 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 346void 347delete_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 358static __inline int 359is_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 */ 373static int 374optimize_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 */ 497static void 498collapse_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 */ 569int 570alloc_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 619int 620alloc_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 631static int 632alloc_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 724done: 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 734int 735alloc_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 */ 762static void 763free_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 871void 872free_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 895static void 896print_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 919static void 920print_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 939static void 940test_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 959static void 960test_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 978int 979main(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 1025