subr_unit.c revision 170949
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 170949 2007-06-19 13:13:17Z kib $ 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 157#endif /* USERLAND */ 158 159/* 160 * This is our basic building block. 161 * 162 * It can be used in three different ways depending on the value of the ptr 163 * element: 164 * If ptr is NULL, it represents a run of free items. 165 * If ptr points to the unrhdr it represents a run of allocated items. 166 * Otherwise it points to an bitstring of allocated items. 167 * 168 * For runs the len field is the length of the run. 169 * For bitmaps the len field represents the number of allocated items. 170 * 171 * The bitmap is the same size as struct unr to optimize memory management. 172 */ 173struct unr { 174 TAILQ_ENTRY(unr) list; 175 u_int len; 176 void *ptr; 177}; 178 179struct unrb { 180 u_char busy; 181 bitstr_t map[sizeof(struct unr) - 1]; 182}; 183 184CTASSERT(sizeof(struct unr) == sizeof(struct unrb)); 185 186/* Number of bits in the bitmap */ 187#define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8) 188 189/* Header element for a unr number space. */ 190 191struct unrhdr { 192 TAILQ_HEAD(unrhd,unr) head; 193 u_int low; /* Lowest item */ 194 u_int high; /* Highest item */ 195 u_int busy; /* Count of allocated items */ 196 u_int alloc; /* Count of memory allocations */ 197 u_int first; /* items in allocated from start */ 198 u_int last; /* items free at end */ 199 struct mtx *mtx; 200}; 201 202 203#if defined(DIAGNOSTIC) || !defined(_KERNEL) 204/* 205 * Consistency check function. 206 * 207 * Checks the internal consistency as well as we can. 208 * 209 * Called at all boundaries of this API. 210 */ 211static void 212check_unrhdr(struct unrhdr *uh, int line) 213{ 214 struct unr *up; 215 struct unrb *ub; 216 u_int x, y, z, w; 217 218 y = uh->first; 219 z = 0; 220 TAILQ_FOREACH(up, &uh->head, list) { 221 z++; 222 if (up->ptr != uh && up->ptr != NULL) { 223 ub = up->ptr; 224 KASSERT (up->len <= NBITS, 225 ("UNR inconsistency: len %u max %d (line %d)\n", 226 up->len, NBITS, line)); 227 z++; 228 w = 0; 229 for (x = 0; x < up->len; x++) 230 if (bit_test(ub->map, x)) 231 w++; 232 KASSERT (w == ub->busy, 233 ("UNR inconsistency: busy %u found %u (line %d)\n", 234 ub->busy, w, line)); 235 y += w; 236 } else if (up->ptr != NULL) 237 y += up->len; 238 } 239 KASSERT (y == uh->busy, 240 ("UNR inconsistency: items %u found %u (line %d)\n", 241 uh->busy, y, line)); 242 KASSERT (z == uh->alloc, 243 ("UNR inconsistency: chunks %u found %u (line %d)\n", 244 uh->alloc, z, line)); 245} 246 247#else 248 249static __inline void 250check_unrhdr(struct unrhdr *uh, int line) 251{ 252 253} 254 255#endif 256 257 258/* 259 * Userland memory management. Just use calloc and keep track of how 260 * many elements we have allocated for check_unrhdr(). 261 */ 262 263static __inline void * 264new_unr(struct unrhdr *uh, void **p1, void **p2) 265{ 266 void *p; 267 268 uh->alloc++; 269 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory")); 270 if (*p1 != NULL) { 271 p = *p1; 272 *p1 = NULL; 273 return (p); 274 } else { 275 p = *p2; 276 *p2 = NULL; 277 return (p); 278 } 279} 280 281static __inline void 282delete_unr(struct unrhdr *uh, void *ptr) 283{ 284 285 uh->alloc--; 286 Free(ptr); 287} 288 289/* 290 * Allocate a new unrheader set. 291 * 292 * Highest and lowest valid values given as paramters. 293 */ 294 295struct unrhdr * 296new_unrhdr(int low, int high, struct mtx *mutex) 297{ 298 struct unrhdr *uh; 299 300 KASSERT(low <= high, 301 ("UNR: use error: new_unrhdr(%u, %u)", low, high)); 302 uh = Malloc(sizeof *uh); 303 if (mutex != NULL) 304 uh->mtx = mutex; 305 else 306 uh->mtx = &unitmtx; 307 TAILQ_INIT(&uh->head); 308 uh->low = low; 309 uh->high = high; 310 uh->first = 0; 311 uh->last = 1 + (high - low); 312 check_unrhdr(uh, __LINE__); 313 return (uh); 314} 315 316void 317delete_unrhdr(struct unrhdr *uh) 318{ 319 320 check_unrhdr(uh, __LINE__); 321 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy)); 322 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr")); 323 Free(uh); 324} 325 326static __inline int 327is_bitmap(struct unrhdr *uh, struct unr *up) 328{ 329 return (up->ptr != uh && up->ptr != NULL); 330} 331 332/* 333 * Look for sequence of items which can be combined into a bitmap, if 334 * multiple are present, take the one which saves most memory. 335 * 336 * Return (1) if a sequence was found to indicate that another call 337 * might be able to do more. Return (0) if we found no suitable sequence. 338 * 339 * NB: called from alloc_unr(), no new memory allocation allowed. 340 */ 341static int 342optimize_unr(struct unrhdr *uh) 343{ 344 struct unr *up, *uf, *us; 345 struct unrb *ub, *ubf; 346 u_int a, l, ba; 347 348 /* 349 * Look for the run of items (if any) which when collapsed into 350 * a bitmap would save most memory. 351 */ 352 us = NULL; 353 ba = 0; 354 TAILQ_FOREACH(uf, &uh->head, list) { 355 if (uf->len >= NBITS) 356 continue; 357 a = 1; 358 if (is_bitmap(uh, uf)) 359 a++; 360 l = uf->len; 361 up = uf; 362 while (1) { 363 up = TAILQ_NEXT(up, list); 364 if (up == NULL) 365 break; 366 if ((up->len + l) > NBITS) 367 break; 368 a++; 369 if (is_bitmap(uh, up)) 370 a++; 371 l += up->len; 372 } 373 if (a > ba) { 374 ba = a; 375 us = uf; 376 } 377 } 378 if (ba < 3) 379 return (0); 380 381 /* 382 * If the first element is not a bitmap, make it one. 383 * Trying to do so without allocating more memory complicates things 384 * a bit 385 */ 386 if (!is_bitmap(uh, us)) { 387 uf = TAILQ_NEXT(us, list); 388 TAILQ_REMOVE(&uh->head, us, list); 389 a = us->len; 390 l = us->ptr == uh ? 1 : 0; 391 ub = (void *)us; 392 ub->busy = 0; 393 if (l) { 394 bit_nset(ub->map, 0, a); 395 ub->busy += a; 396 } else { 397 bit_nclear(ub->map, 0, a); 398 } 399 if (!is_bitmap(uh, uf)) { 400 if (uf->ptr == NULL) { 401 bit_nclear(ub->map, a, a + uf->len - 1); 402 } else { 403 bit_nset(ub->map, a, a + uf->len - 1); 404 ub->busy += uf->len; 405 } 406 uf->ptr = ub; 407 uf->len += a; 408 us = uf; 409 } else { 410 ubf = uf->ptr; 411 for (l = 0; l < uf->len; l++, a++) { 412 if (bit_test(ubf->map, l)) { 413 bit_set(ub->map, a); 414 ub->busy++; 415 } else { 416 bit_clear(ub->map, a); 417 } 418 } 419 uf->len = a; 420 delete_unr(uh, uf->ptr); 421 uf->ptr = ub; 422 us = uf; 423 } 424 } 425 ub = us->ptr; 426 while (1) { 427 uf = TAILQ_NEXT(us, list); 428 if (uf == NULL) 429 return (1); 430 if (uf->len + us->len > NBITS) 431 return (1); 432 if (uf->ptr == NULL) { 433 bit_nclear(ub->map, us->len, us->len + uf->len - 1); 434 us->len += uf->len; 435 TAILQ_REMOVE(&uh->head, uf, list); 436 delete_unr(uh, uf); 437 } else if (uf->ptr == uh) { 438 bit_nset(ub->map, us->len, us->len + uf->len - 1); 439 ub->busy += uf->len; 440 us->len += uf->len; 441 TAILQ_REMOVE(&uh->head, uf, list); 442 delete_unr(uh, uf); 443 } else { 444 ubf = uf->ptr; 445 for (l = 0; l < uf->len; l++, us->len++) { 446 if (bit_test(ubf->map, l)) { 447 bit_set(ub->map, us->len); 448 ub->busy++; 449 } else { 450 bit_clear(ub->map, us->len); 451 } 452 } 453 TAILQ_REMOVE(&uh->head, uf, list); 454 delete_unr(uh, ubf); 455 delete_unr(uh, uf); 456 } 457 } 458} 459 460/* 461 * See if a given unr should be collapsed with a neighbor. 462 * 463 * NB: called from alloc_unr(), no new memory allocation allowed. 464 */ 465static void 466collapse_unr(struct unrhdr *uh, struct unr *up) 467{ 468 struct unr *upp; 469 struct unrb *ub; 470 471 /* If bitmap is all set or clear, change it to runlength */ 472 if (is_bitmap(uh, up)) { 473 ub = up->ptr; 474 if (ub->busy == up->len) { 475 delete_unr(uh, up->ptr); 476 up->ptr = uh; 477 } else if (ub->busy == 0) { 478 delete_unr(uh, up->ptr); 479 up->ptr = NULL; 480 } 481 } 482 483 /* If nothing left in runlength, delete it */ 484 if (up->len == 0) { 485 upp = TAILQ_PREV(up, unrhd, list); 486 if (upp == NULL) 487 upp = TAILQ_NEXT(up, list); 488 TAILQ_REMOVE(&uh->head, up, list); 489 delete_unr(uh, up); 490 up = upp; 491 } 492 493 /* If we have "hot-spot" still, merge with neighbor if possible */ 494 if (up != NULL) { 495 upp = TAILQ_PREV(up, unrhd, list); 496 if (upp != NULL && up->ptr == upp->ptr) { 497 up->len += upp->len; 498 TAILQ_REMOVE(&uh->head, upp, list); 499 delete_unr(uh, upp); 500 } 501 upp = TAILQ_NEXT(up, list); 502 if (upp != NULL && up->ptr == upp->ptr) { 503 up->len += upp->len; 504 TAILQ_REMOVE(&uh->head, upp, list); 505 delete_unr(uh, upp); 506 } 507 } 508 509 /* Merge into ->first if possible */ 510 upp = TAILQ_FIRST(&uh->head); 511 if (upp != NULL && upp->ptr == uh) { 512 uh->first += upp->len; 513 TAILQ_REMOVE(&uh->head, upp, list); 514 delete_unr(uh, upp); 515 if (up == upp) 516 up = NULL; 517 } 518 519 /* Merge into ->last if possible */ 520 upp = TAILQ_LAST(&uh->head, unrhd); 521 if (upp != NULL && upp->ptr == NULL) { 522 uh->last += upp->len; 523 TAILQ_REMOVE(&uh->head, upp, list); 524 delete_unr(uh, upp); 525 if (up == upp) 526 up = NULL; 527 } 528 529 /* Try to make bitmaps */ 530 while (optimize_unr(uh)) 531 continue; 532} 533 534/* 535 * Allocate a free unr. 536 */ 537int 538alloc_unrl(struct unrhdr *uh) 539{ 540 struct unr *up; 541 struct unrb *ub; 542 u_int x; 543 int y; 544 545 mtx_assert(uh->mtx, MA_OWNED); 546 check_unrhdr(uh, __LINE__); 547 x = uh->low + uh->first; 548 549 up = TAILQ_FIRST(&uh->head); 550 551 /* 552 * If we have an ideal split, just adjust the first+last 553 */ 554 if (up == NULL && uh->last > 0) { 555 uh->first++; 556 uh->last--; 557 uh->busy++; 558 return (x); 559 } 560 561 /* 562 * We can always allocate from the first list element, so if we have 563 * nothing on the list, we must have run out of unit numbers. 564 */ 565 if (up == NULL) 566 return (-1); 567 568 KASSERT(up->ptr != uh, ("UNR first element is allocated")); 569 570 if (up->ptr == NULL) { /* free run */ 571 uh->first++; 572 up->len--; 573 } else { /* bitmap */ 574 ub = up->ptr; 575 KASSERT(ub->busy < up->len, ("UNR bitmap confusion")); 576 bit_ffc(ub->map, up->len, &y); 577 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap.")); 578 bit_set(ub->map, y); 579 ub->busy++; 580 x += y; 581 } 582 uh->busy++; 583 collapse_unr(uh, up); 584 return (x); 585} 586 587int 588alloc_unr(struct unrhdr *uh) 589{ 590 int i; 591 592 mtx_lock(uh->mtx); 593 i = alloc_unrl(uh); 594 mtx_unlock(uh->mtx); 595 return (i); 596} 597 598/* 599 * Free a unr. 600 * 601 * If we can save unrs by using a bitmap, do so. 602 */ 603static void 604free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2) 605{ 606 struct unr *up, *upp, *upn; 607 struct unrb *ub; 608 u_int pl; 609 610 KASSERT(item >= uh->low && item <= uh->high, 611 ("UNR: free_unr(%u) out of range [%u...%u]", 612 item, uh->low, uh->high)); 613 check_unrhdr(uh, __LINE__); 614 item -= uh->low; 615 upp = TAILQ_FIRST(&uh->head); 616 /* 617 * Freeing in the ideal split case 618 */ 619 if (item + 1 == uh->first && upp == NULL) { 620 uh->last++; 621 uh->first--; 622 uh->busy--; 623 check_unrhdr(uh, __LINE__); 624 return; 625 } 626 /* 627 * Freeing in the ->first section. Create a run starting at the 628 * freed item. The code below will subdivide it. 629 */ 630 if (item < uh->first) { 631 up = new_unr(uh, p1, p2); 632 up->ptr = uh; 633 up->len = uh->first - item; 634 TAILQ_INSERT_HEAD(&uh->head, up, list); 635 uh->first -= up->len; 636 } 637 638 item -= uh->first; 639 640 /* Find the item which contains the unit we want to free */ 641 TAILQ_FOREACH(up, &uh->head, list) { 642 if (up->len > item) 643 break; 644 item -= up->len; 645 } 646 647 /* Handle bitmap items */ 648 if (is_bitmap(uh, up)) { 649 ub = up->ptr; 650 651 KASSERT(bit_test(ub->map, item) != 0, 652 ("UNR: Freeing free item %d (bitmap)\n", item)); 653 bit_clear(ub->map, item); 654 uh->busy--; 655 ub->busy--; 656 collapse_unr(uh, up); 657 return; 658 } 659 660 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item)); 661 662 /* Just this one left, reap it */ 663 if (up->len == 1) { 664 up->ptr = NULL; 665 uh->busy--; 666 collapse_unr(uh, up); 667 return; 668 } 669 670 /* Check if we can shift the item into the previous 'free' run */ 671 upp = TAILQ_PREV(up, unrhd, list); 672 if (item == 0 && upp != NULL && upp->ptr == NULL) { 673 upp->len++; 674 up->len--; 675 uh->busy--; 676 collapse_unr(uh, up); 677 return; 678 } 679 680 /* Check if we can shift the item to the next 'free' run */ 681 upn = TAILQ_NEXT(up, list); 682 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) { 683 upn->len++; 684 up->len--; 685 uh->busy--; 686 collapse_unr(uh, up); 687 return; 688 } 689 690 /* Split off the tail end, if any. */ 691 pl = up->len - (1 + item); 692 if (pl > 0) { 693 upp = new_unr(uh, p1, p2); 694 upp->ptr = uh; 695 upp->len = pl; 696 TAILQ_INSERT_AFTER(&uh->head, up, upp, list); 697 } 698 699 /* Split off head end, if any */ 700 if (item > 0) { 701 upp = new_unr(uh, p1, p2); 702 upp->len = item; 703 upp->ptr = uh; 704 TAILQ_INSERT_BEFORE(up, upp, list); 705 } 706 up->len = 1; 707 up->ptr = NULL; 708 uh->busy--; 709 collapse_unr(uh, up); 710} 711 712void 713free_unr(struct unrhdr *uh, u_int item) 714{ 715 void *p1, *p2; 716 717 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr"); 718 p1 = Malloc(sizeof(struct unr)); 719 p2 = Malloc(sizeof(struct unr)); 720 mtx_lock(uh->mtx); 721 free_unrl(uh, item, &p1, &p2); 722 mtx_unlock(uh->mtx); 723 if (p1 != NULL) 724 Free(p1); 725 if (p2 != NULL) 726 Free(p2); 727} 728 729#ifndef _KERNEL /* USERLAND test driver */ 730 731/* 732 * Simple stochastic test driver for the above functions 733 */ 734 735static void 736print_unr(struct unrhdr *uh, struct unr *up) 737{ 738 u_int x; 739 struct unrb *ub; 740 741 printf(" %p len = %5u ", up, up->len); 742 if (up->ptr == NULL) 743 printf("free\n"); 744 else if (up->ptr == uh) 745 printf("alloc\n"); 746 else { 747 ub = up->ptr; 748 printf("bitmap(%d) [", ub->busy); 749 for (x = 0; x < up->len; x++) { 750 if (bit_test(ub->map, x)) 751 printf("#"); 752 else 753 printf(" "); 754 } 755 printf("]\n"); 756 } 757} 758 759static void 760print_unrhdr(struct unrhdr *uh) 761{ 762 struct unr *up; 763 u_int x; 764 765 printf( 766 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n", 767 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc); 768 x = uh->low + uh->first; 769 TAILQ_FOREACH(up, &uh->head, list) { 770 printf(" from = %5u", x); 771 print_unr(uh, up); 772 if (up->ptr == NULL || up->ptr == uh) 773 x += up->len; 774 else 775 x += NBITS; 776 } 777} 778 779/* Number of unrs to test */ 780#define NN 10000 781 782int 783main(int argc __unused, const char **argv __unused) 784{ 785 struct unrhdr *uh; 786 u_int i, x, m, j; 787 char a[NN]; 788 789 setbuf(stdout, NULL); 790 uh = new_unrhdr(0, NN - 1, NULL); 791 print_unrhdr(uh); 792 793 memset(a, 0, sizeof a); 794 795 fprintf(stderr, "sizeof(struct unr) %d\n", sizeof (struct unr)); 796 fprintf(stderr, "sizeof(struct unrb) %d\n", sizeof (struct unrb)); 797 fprintf(stderr, "sizeof(struct unrhdr) %d\n", sizeof (struct unrhdr)); 798 fprintf(stderr, "NBITS %d\n", NBITS); 799 x = 1; 800 for (m = 0; m < NN * 100; m++) { 801 j = random(); 802 i = (j >> 1) % NN; 803#if 0 804 if (a[i] && (j & 1)) 805 continue; 806#endif 807 if (a[i]) { 808 printf("F %u\n", i); 809 free_unr(uh, i); 810 a[i] = 0; 811 } else { 812 no_alloc = 1; 813 i = alloc_unr(uh); 814 if (i != -1) { 815 a[i] = 1; 816 printf("A %u\n", i); 817 } 818 no_alloc = 0; 819 } 820 if (1) /* XXX: change this for detailed debug printout */ 821 print_unrhdr(uh); 822 check_unrhdr(uh, __LINE__); 823 } 824 for (i = 0; i < NN; i++) { 825 if (a[i]) { 826 printf("C %u\n", i); 827 free_unr(uh, i); 828 print_unrhdr(uh); 829 } 830 } 831 print_unrhdr(uh); 832 delete_unrhdr(uh); 833 return (0); 834} 835#endif 836