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