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