1 /* $NetBSD: subr_extent.c,v 1.10 1997/10/09 07:46:07 jtc Exp $ */ 2 3 /*- 4 * Copyright (c) 1996 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe and Matthias Drochner. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 /* 40 * General purpose extent manager. 41 */ 42 43 #ifdef _KERNEL 44 #include <sys/param.h> 45 #include <sys/extent.h> 46 #include <sys/malloc.h> 47 #include <sys/time.h> 48 #include <sys/systm.h> 49 #include <sys/proc.h> 50 #else 51 /* 52 * user-land definitions, so it can fit into a testing harness. 53 */ 54 #include <sys/param.h> 55 #include <sys/extent.h> 56 #include <errno.h> 57 #include <stdlib.h> 58 #include <stdio.h> 59 60 #define malloc(s, t, flags) malloc(s) 61 #define free(p, t) free(p) 62 #define tsleep(chan, pri, str, timo) (EWOULDBLOCK) 63 #define wakeup(chan) ((void)0) 64 #endif 65 66 static void extent_insert_and_optimize __P((struct extent *, u_long, u_long, 67 int, struct extent_region *, struct extent_region *)); 68 static struct extent_region *extent_alloc_region_descriptor 69 __P((struct extent *, int)); 70 static void extent_free_region_descriptor __P((struct extent *, 71 struct extent_region *)); 72 73 /* 74 * Macro to align to an arbitrary power-of-two boundary. 75 */ 76 #define EXTENT_ALIGN(_start, _align) \ 77 (((_start) + ((_align) - 1)) & (-(_align))) 78 79 /* 80 * Allocate and initialize an extent map. 81 */ 82 struct extent * 83 extent_create(name, start, end, mtype, storage, storagesize, flags) 84 char *name; 85 u_long start, end; 86 int mtype; 87 caddr_t storage; 88 size_t storagesize; 89 int flags; 90 { 91 struct extent *ex; 92 caddr_t cp = storage; 93 size_t sz = storagesize; 94 struct extent_region *rp; 95 int fixed_extent = (storage != NULL); 96 97 #ifdef DIAGNOSTIC 98 /* Check arguments. */ 99 if (name == NULL) 100 panic("extent_create: name == NULL"); 101 if (end < start) { 102 printf("extent_create: extent `%s', start 0x%lx, end 0x%lx\n", 103 name, start, end); 104 panic("extent_create: end < start"); 105 } 106 if (fixed_extent && (storagesize < sizeof(struct extent_fixed))) 107 panic("extent_create: fixed extent, bad storagesize 0x%x", 108 storagesize); 109 if (fixed_extent == 0 && (storagesize != 0 || storage != NULL)) 110 panic("extent_create: storage provided for non-fixed"); 111 #endif 112 113 /* Allocate extent descriptor. */ 114 if (fixed_extent) { 115 struct extent_fixed *fex; 116 117 bzero(storage, storagesize); 118 119 /* 120 * Align all descriptors on "long" boundaries. 121 */ 122 fex = (struct extent_fixed *)cp; 123 ex = (struct extent *)fex; 124 cp += ALIGN(sizeof(struct extent_fixed)); 125 sz -= ALIGN(sizeof(struct extent_fixed)); 126 fex->fex_storage = storage; 127 fex->fex_storagesize = storagesize; 128 129 /* 130 * In a fixed extent, we have to pre-allocate region 131 * descriptors and place them in the extent's freelist. 132 */ 133 LIST_INIT(&fex->fex_freelist); 134 while (sz >= ALIGN(sizeof(struct extent_region))) { 135 rp = (struct extent_region *)cp; 136 cp += ALIGN(sizeof(struct extent_region)); 137 sz -= ALIGN(sizeof(struct extent_region)); 138 LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link); 139 } 140 } else { 141 ex = (struct extent *)malloc(sizeof(struct extent), 142 mtype, (flags & EX_WAITOK) ? M_WAITOK : M_NOWAIT); 143 if (ex == NULL) 144 return (NULL); 145 } 146 147 /* Fill in the extent descriptor and return it to the caller. */ 148 LIST_INIT(&ex->ex_regions); 149 ex->ex_name = name; 150 ex->ex_start = start; 151 ex->ex_end = end; 152 ex->ex_mtype = mtype; 153 ex->ex_flags = 0; 154 if (fixed_extent) 155 ex->ex_flags |= EXF_FIXED; 156 if (flags & EX_NOCOALESCE) 157 ex->ex_flags |= EXF_NOCOALESCE; 158 return (ex); 159 } 160 161 /* 162 * Destroy an extent map. 163 */ 164 void 165 extent_destroy(ex) 166 struct extent *ex; 167 { 168 struct extent_region *rp, *orp; 169 170 #ifdef DIAGNOSTIC 171 /* Check arguments. */ 172 if (ex == NULL) 173 panic("extent_destroy: NULL extent"); 174 #endif 175 176 /* Free all region descriptors in extent. */ 177 for (rp = ex->ex_regions.lh_first; rp != NULL; ) { 178 orp = rp; 179 rp = rp->er_link.le_next; 180 LIST_REMOVE(orp, er_link); 181 extent_free_region_descriptor(ex, orp); 182 } 183 184 /* If we're not a fixed extent, free the extent descriptor itself. */ 185 if ((ex->ex_flags & EXF_FIXED) == 0) 186 free(ex, ex->ex_mtype); 187 } 188 189 /* 190 * Insert a region descriptor into the sorted region list after the 191 * entry "after" or at the head of the list (if "after" is NULL). 192 * The region descriptor we insert is passed in "rp". We must 193 * allocate the region descriptor before calling this function! 194 * If we don't need the region descriptor, it will be freed here. 195 */ 196 static void 197 extent_insert_and_optimize(ex, start, size, flags, after, rp) 198 struct extent *ex; 199 u_long start, size; 200 int flags; 201 struct extent_region *after, *rp; 202 { 203 struct extent_region *nextr; 204 int appended = 0; 205 206 if (after == NULL) { 207 /* 208 * We're the first in the region list. If there's 209 * a region after us, attempt to coalesce to save 210 * descriptor overhead. 211 */ 212 if (((ex->ex_flags & EXF_NOCOALESCE) == 0) && 213 (ex->ex_regions.lh_first != NULL) && 214 ((start + size) == ex->ex_regions.lh_first->er_start)) { 215 /* 216 * We can coalesce. Prepend us to the first region. 217 */ 218 ex->ex_regions.lh_first->er_start = start; 219 extent_free_region_descriptor(ex, rp); 220 return; 221 } 222 223 /* 224 * Can't coalesce. Fill in the region descriptor 225 * in, and insert us at the head of the region list. 226 */ 227 rp->er_start = start; 228 rp->er_end = start + (size - 1); 229 LIST_INSERT_HEAD(&ex->ex_regions, rp, er_link); 230 return; 231 } 232 233 /* 234 * If EXF_NOCOALESCE is set, coalescing is disallowed. 235 */ 236 if (ex->ex_flags & EXF_NOCOALESCE) 237 goto cant_coalesce; 238 239 /* 240 * Attempt to coalesce with the region before us. 241 */ 242 if ((after->er_end + 1) == start) { 243 /* 244 * We can coalesce. Append ourselves and make 245 * note of it. 246 */ 247 after->er_end = start + (size - 1); 248 appended = 1; 249 } 250 251 /* 252 * Attempt to coalesce with the region after us. 253 */ 254 if ((after->er_link.le_next != NULL) && 255 ((start + size) == after->er_link.le_next->er_start)) { 256 /* 257 * We can coalesce. Note that if we appended ourselves 258 * to the previous region, we exactly fit the gap, and 259 * can free the "next" region descriptor. 260 */ 261 if (appended) { 262 /* 263 * Yup, we can free it up. 264 */ 265 after->er_end = after->er_link.le_next->er_end; 266 nextr = after->er_link.le_next; 267 LIST_REMOVE(nextr, er_link); 268 extent_free_region_descriptor(ex, nextr); 269 } else { 270 /* 271 * Nope, just prepend us to the next region. 272 */ 273 after->er_link.le_next->er_start = start; 274 } 275 276 extent_free_region_descriptor(ex, rp); 277 return; 278 } 279 280 /* 281 * We weren't able to coalesce with the next region, but 282 * we don't need to allocate a region descriptor if we 283 * appended ourselves to the previous region. 284 */ 285 if (appended) { 286 extent_free_region_descriptor(ex, rp); 287 return; 288 } 289 290 cant_coalesce: 291 292 /* 293 * Fill in the region descriptor and insert ourselves 294 * into the region list. 295 */ 296 rp->er_start = start; 297 rp->er_end = start + (size - 1); 298 LIST_INSERT_AFTER(after, rp, er_link); 299 } 300 301 /* 302 * Allocate a specific region in an extent map. 303 */ 304 int 305 extent_alloc_region(ex, start, size, flags) 306 struct extent *ex; 307 u_long start, size; 308 int flags; 309 { 310 struct extent_region *rp, *last, *myrp; 311 u_long end = start + (size - 1); 312 int error; 313 314 #ifdef DIAGNOSTIC 315 /* Check arguments. */ 316 if (ex == NULL) 317 panic("extent_alloc_region: NULL extent"); 318 if (size < 1) { 319 printf("extent_alloc_region: extent `%s', size 0x%lx\n", 320 ex->ex_name, size); 321 panic("extent_alloc_region: bad size"); 322 } 323 if (end < start) { 324 printf( 325 "extent_alloc_region: extent `%s', start 0x%lx, size 0x%lx\n", 326 ex->ex_name, start, size); 327 panic("extent_alloc_region: overflow"); 328 } 329 #endif 330 331 /* 332 * Make sure the requested region lies within the 333 * extent. 334 */ 335 if ((start < ex->ex_start) || (end > ex->ex_end)) { 336 #ifdef DIAGNOSTIC 337 printf("extent_alloc_region: extent `%s' (0x%lx - 0x%lx)\n", 338 ex->ex_name, ex->ex_start, ex->ex_end); 339 printf("extent_alloc_region: start 0x%lx, end 0x%lx\n", 340 start, end); 341 panic("extent_alloc_region: region lies outside extent"); 342 #else 343 return (EINVAL); 344 #endif 345 } 346 347 /* 348 * Allocate the region descriptor. It will be freed later 349 * if we can coalesce with another region. 350 */ 351 myrp = extent_alloc_region_descriptor(ex, flags); 352 if (myrp == NULL) { 353 #ifdef DIAGNOSTIC 354 printf( 355 "extent_alloc_region: can't allocate region descriptor\n"); 356 #endif 357 return (ENOMEM); 358 } 359 360 alloc_start: 361 /* 362 * Attempt to place ourselves in the desired area of the 363 * extent. We save ourselves some work by keeping the list sorted. 364 * In other words, if the start of the current region is greater 365 * than the end of our region, we don't have to search any further. 366 */ 367 368 /* 369 * Keep a pointer to the last region we looked at so 370 * that we don't have to traverse the list again when 371 * we insert ourselves. If "last" is NULL when we 372 * finally insert ourselves, we go at the head of the 373 * list. See extent_insert_and_optimize() for details. 374 */ 375 last = NULL; 376 377 for (rp = ex->ex_regions.lh_first; rp != NULL; 378 rp = rp->er_link.le_next) { 379 if (rp->er_start > end) { 380 /* 381 * We lie before this region and don't 382 * conflict. 383 */ 384 break; 385 } 386 387 /* 388 * The current region begins before we end. 389 * Check for a conflict. 390 */ 391 if (rp->er_end >= start) { 392 /* 393 * We conflict. If we can (and want to) wait, 394 * do so. 395 */ 396 if (flags & EX_WAITSPACE) { 397 ex->ex_flags |= EXF_WANTED; 398 error = tsleep(ex, 399 PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), 400 "extnt", 0); 401 if (error) 402 return (error); 403 goto alloc_start; 404 } 405 extent_free_region_descriptor(ex, myrp); 406 return (EAGAIN); 407 } 408 /* 409 * We don't conflict, but this region lies before 410 * us. Keep a pointer to this region, and keep 411 * trying. 412 */ 413 last = rp; 414 } 415 416 /* 417 * We don't conflict with any regions. "last" points 418 * to the region we fall after, or is NULL if we belong 419 * at the beginning of the region list. Insert ourselves. 420 */ 421 extent_insert_and_optimize(ex, start, size, flags, last, myrp); 422 return (0); 423 } 424 425 /* 426 * Macro to check (x + y) <= z. This check is designed to fail 427 * if an overflow occurs. 428 */ 429 #define LE_OV(x, y, z) ((((x) + (y)) >= (x)) && (((x) + (y)) <= (z))) 430 431 /* 432 * Allocate a region in an extent map subregion. 433 * 434 * If EX_FAST is specified, we return the first fit in the map. 435 * Otherwise, we try to minimize fragmentation by finding the 436 * smallest gap that will hold the request. 437 * 438 * The allocated region is aligned to "alignment", which must be 439 * a power of 2. 440 */ 441 int 442 extent_alloc_subregion(ex, substart, subend, size, alignment, boundary, 443 flags, result) 444 struct extent *ex; 445 u_long substart, subend, size, alignment, boundary; 446 int flags; 447 u_long *result; 448 { 449 struct extent_region *rp, *myrp, *last, *bestlast; 450 u_long newstart, newend, beststart, bestovh, ovh; 451 u_long dontcross, odontcross; 452 int error; 453 454 #ifdef DIAGNOSTIC 455 /* Check arguments. */ 456 if (ex == NULL) 457 panic("extent_alloc_subregion: NULL extent"); 458 if (result == NULL) 459 panic("extent_alloc_subregion: NULL result pointer"); 460 if ((substart < ex->ex_start) || (substart > ex->ex_end) || 461 (subend > ex->ex_end) || (subend < ex->ex_start)) { 462 printf("extent_alloc_subregion: extent `%s', ex_start 0x%lx, ex_end 0x%lx\n", 463 ex->ex_name, ex->ex_start, ex->ex_end); 464 printf("extent_alloc_subregion: substart 0x%lx, subend 0x%lx\n", 465 substart, subend); 466 panic("extent_alloc_subregion: bad subregion"); 467 } 468 if ((size < 1) || ((size - 1) > (subend - substart))) { 469 printf("extent_alloc_subregion: extent `%s', size 0x%lx\n", 470 ex->ex_name, size); 471 panic("extent_alloc_subregion: bad size"); 472 } 473 if (alignment == 0) 474 panic("extent_alloc_subregion: bad alignment"); 475 if (boundary && (boundary < size)) { 476 printf( 477 "extent_alloc_subregion: extent `%s', size 0x%lx, 478 boundary 0x%lx\n", ex->ex_name, size, boundary); 479 panic("extent_alloc_subregion: bad boundary"); 480 } 481 #endif 482 483 /* 484 * Allocate the region descriptor. It will be freed later 485 * if we can coalesce with another region. 486 */ 487 myrp = extent_alloc_region_descriptor(ex, flags); 488 if (myrp == NULL) { 489 #ifdef DIAGNOSTIC 490 printf( 491 "extent_alloc_subregion: can't allocate region descriptor\n"); 492 #endif 493 return (ENOMEM); 494 } 495 496 alloc_start: 497 /* 498 * Keep a pointer to the last region we looked at so 499 * that we don't have to traverse the list again when 500 * we insert ourselves. If "last" is NULL when we 501 * finally insert ourselves, we go at the head of the 502 * list. See extent_insert_and_optimize() for deatails. 503 */ 504 last = NULL; 505 506 /* 507 * Initialize the "don't cross" boundary, a.k.a a line 508 * that a region should not cross. If the boundary lies 509 * before the region starts, we add the "boundary" argument 510 * until we get a meaningful comparison. 511 * 512 * Start the boundary lines at 0 if the caller requests it. 513 */ 514 dontcross = 0; 515 if (boundary) { 516 dontcross = 517 ((flags & EX_BOUNDZERO) ? 0 : ex->ex_start) + boundary; 518 while (dontcross < substart) 519 dontcross += boundary; 520 } 521 522 /* 523 * Keep track of size and location of the smallest 524 * chunk we fit in. 525 * 526 * Since the extent can be as large as the numeric range 527 * of the CPU (0 - 0xffffffff for 32-bit systems), the 528 * best overhead value can be the maximum unsigned integer. 529 * Thus, we initialize "bestovh" to 0, since we insert ourselves 530 * into the region list immediately on an exact match (which 531 * is the only case where "bestovh" would be set to 0). 532 */ 533 bestovh = 0; 534 beststart = 0; 535 bestlast = NULL; 536 537 /* 538 * For N allocated regions, we must make (N + 1) 539 * checks for unallocated space. The first chunk we 540 * check is the area from the beginning of the subregion 541 * to the first allocated region after that point. 542 */ 543 newstart = EXTENT_ALIGN(substart, alignment); 544 if (newstart < ex->ex_start) { 545 #ifdef DIAGNOSTIC 546 printf( 547 "extent_alloc_subregion: extent `%s' (0x%lx - 0x%lx), alignment 0x%lx\n", 548 ex->ex_name, ex->ex_start, ex->ex_end, alignment); 549 panic("extent_alloc_subregion: overflow after alignment"); 550 #else 551 extent_free_region_descriptor(ex, myrp); 552 return (EINVAL); 553 #endif 554 } 555 556 /* 557 * Find the first allocated region that begins on or after 558 * the subregion start, advancing the "last" pointer along 559 * the way. 560 */ 561 for (rp = ex->ex_regions.lh_first; rp != NULL; 562 rp = rp->er_link.le_next) { 563 if (rp->er_start >= newstart) 564 break; 565 last = rp; 566 } 567 568 for (; rp != NULL; rp = rp->er_link.le_next) { 569 /* 570 * Check the chunk before "rp". Note that our 571 * comparison is safe from overflow conditions. 572 */ 573 if (LE_OV(newstart, size, rp->er_start)) { 574 /* 575 * Do a boundary check, if necessary. Note 576 * that a region may *begin* on the boundary, 577 * but it must end before the boundary. 578 */ 579 if (boundary) { 580 newend = newstart + (size - 1); 581 582 /* 583 * Adjust boundary for a meaningful 584 * comparison. 585 */ 586 while (dontcross <= newstart) { 587 odontcross = dontcross; 588 dontcross += boundary; 589 590 /* 591 * If we run past the end of 592 * the extent or the boundary 593 * overflows, then the request 594 * can't fit. 595 */ 596 if ((dontcross > ex->ex_end) || 597 (dontcross < odontcross)) 598 goto fail; 599 } 600 601 /* Do the boundary check. */ 602 if (newend >= dontcross) { 603 /* 604 * Candidate region crosses 605 * boundary. Try again. 606 */ 607 continue; 608 } 609 } 610 611 /* 612 * We would fit into this space. Calculate 613 * the overhead (wasted space). If we exactly 614 * fit, or we're taking the first fit, insert 615 * ourselves into the region list. 616 */ 617 ovh = rp->er_start - newstart - size; 618 if ((flags & EX_FAST) || (ovh == 0)) 619 goto found; 620 621 /* 622 * Don't exactly fit, but check to see 623 * if we're better than any current choice. 624 */ 625 if ((bestovh == 0) || (ovh < bestovh)) { 626 bestovh = ovh; 627 beststart = newstart; 628 bestlast = last; 629 } 630 } 631 632 /* 633 * Skip past the current region and check again. 634 */ 635 newstart = EXTENT_ALIGN((rp->er_end + 1), alignment); 636 if (newstart < rp->er_end) { 637 /* 638 * Overflow condition. Don't error out, since 639 * we might have a chunk of space that we can 640 * use. 641 */ 642 goto fail; 643 } 644 645 last = rp; 646 } 647 648 /* 649 * The final check is from the current starting point to the 650 * end of the subregion. If there were no allocated regions, 651 * "newstart" is set to the beginning of the subregion, or 652 * just past the end of the last allocated region, adjusted 653 * for alignment in either case. 654 */ 655 if (LE_OV(newstart, (size - 1), subend)) { 656 /* 657 * We would fit into this space. Calculate 658 * the overhead (wasted space). If we exactly 659 * fit, or we're taking the first fit, insert 660 * ourselves into the region list. 661 */ 662 ovh = ex->ex_end - newstart - (size - 1); 663 if ((flags & EX_FAST) || (ovh == 0)) 664 goto found; 665 666 /* 667 * Don't exactly fit, but check to see 668 * if we're better than any current choice. 669 */ 670 if ((bestovh == 0) || (ovh < bestovh)) { 671 bestovh = ovh; 672 beststart = newstart; 673 bestlast = last; 674 } 675 } 676 677 fail: 678 /* 679 * One of the following two conditions have 680 * occurred: 681 * 682 * There is no chunk large enough to hold the request. 683 * 684 * If EX_FAST was not specified, there is not an 685 * exact match for the request. 686 * 687 * Note that if we reach this point and EX_FAST is 688 * set, then we know there is no space in the extent for 689 * the request. 690 */ 691 if (((flags & EX_FAST) == 0) && (bestovh != 0)) { 692 /* 693 * We have a match that's "good enough". 694 */ 695 newstart = beststart; 696 last = bestlast; 697 goto found; 698 } 699 700 /* 701 * No space currently available. Wait for it to free up, 702 * if possible. 703 */ 704 if (flags & EX_WAITSPACE) { 705 ex->ex_flags |= EXF_WANTED; 706 error = tsleep(ex, 707 PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), "extnt", 0); 708 if (error) 709 return (error); 710 goto alloc_start; 711 } 712 713 extent_free_region_descriptor(ex, myrp); 714 return (EAGAIN); 715 716 found: 717 /* 718 * Insert ourselves into the region list. 719 */ 720 extent_insert_and_optimize(ex, newstart, size, flags, last, myrp); 721 *result = newstart; 722 return (0); 723 } 724 725 int 726 extent_free(ex, start, size, flags) 727 struct extent *ex; 728 u_long start, size; 729 int flags; 730 { 731 struct extent_region *rp; 732 u_long end = start + (size - 1); 733 734 #ifdef DIAGNOSTIC 735 /* Check arguments. */ 736 if (ex == NULL) 737 panic("extent_free: NULL extent"); 738 if ((start < ex->ex_start) || (start > ex->ex_end)) { 739 extent_print(ex); 740 printf("extent_free: extent `%s', start 0x%lx, size 0x%lx\n", 741 ex->ex_name, start, size); 742 panic("extent_free: extent `%s', region not within extent", 743 ex->ex_name); 744 } 745 /* Check for an overflow. */ 746 if (end < start) { 747 extent_print(ex); 748 printf("extent_free: extent `%s', start 0x%lx, size 0x%lx\n", 749 ex->ex_name, start, size); 750 panic("extent_free: overflow"); 751 } 752 #endif 753 754 /* 755 * Find region and deallocate. Several possibilities: 756 * 757 * 1. (start == er_start) && (end == er_end): 758 * Free descriptor. 759 * 760 * 2. (start == er_start) && (end < er_end): 761 * Adjust er_start. 762 * 763 * 3. (start > er_start) && (end == er_end): 764 * Adjust er_end. 765 * 766 * 4. (start > er_start) && (end < er_end): 767 * Fragment region. Requires descriptor alloc. 768 * 769 * Cases 2, 3, and 4 require that the EXF_NOCOALESCE flag 770 * is not set. 771 */ 772 for (rp = ex->ex_regions.lh_first; rp != NULL; 773 rp = rp->er_link.le_next) { 774 /* 775 * Save ourselves some comparisons; does the current 776 * region end before chunk to be freed begins? If so, 777 * then we haven't found the appropriate region descriptor. 778 */ 779 if (rp->er_end < start) 780 continue; 781 782 /* 783 * Save ourselves some traversal; does the current 784 * region begin after the chunk to be freed ends? If so, 785 * then we've already passed any possible region descriptors 786 * that might have contained the chunk to be freed. 787 */ 788 if (rp->er_start > end) 789 break; 790 791 /* Case 1. */ 792 if ((start == rp->er_start) && (end == rp->er_end)) { 793 LIST_REMOVE(rp, er_link); 794 extent_free_region_descriptor(ex, rp); 795 goto done; 796 } 797 798 /* 799 * The following cases all require that EXF_NOCOALESCE 800 * is not set. 801 */ 802 if (ex->ex_flags & EXF_NOCOALESCE) 803 continue; 804 805 /* Case 2. */ 806 if ((start == rp->er_start) && (end < rp->er_end)) { 807 rp->er_start = (end + 1); 808 goto done; 809 } 810 811 /* Case 3. */ 812 if ((start > rp->er_start) && (end == rp->er_end)) { 813 rp->er_end = (start - 1); 814 goto done; 815 } 816 817 /* Case 4. */ 818 if ((start > rp->er_start) && (end < rp->er_end)) { 819 struct extent_region *nrp; 820 821 /* Allocate a region descriptor. */ 822 nrp = extent_alloc_region_descriptor(ex, flags); 823 if (nrp == NULL) 824 return (ENOMEM); 825 826 /* Fill in new descriptor. */ 827 nrp->er_start = end + 1; 828 nrp->er_end = rp->er_end; 829 830 /* Adjust current descriptor. */ 831 rp->er_end = start - 1; 832 833 /* Instert new descriptor after current. */ 834 LIST_INSERT_AFTER(rp, nrp, er_link); 835 goto done; 836 } 837 } 838 839 /* Region not found, or request otherwise invalid. */ 840 extent_print(ex); 841 printf("extent_free: start 0x%lx, end 0x%lx\n", start, end); 842 panic("extent_free: region not found"); 843 844 done: 845 if (ex->ex_flags & EXF_WANTED) { 846 ex->ex_flags &= ~EXF_WANTED; 847 wakeup(ex); 848 } 849 return (0); 850 } 851 852 static struct extent_region * 853 extent_alloc_region_descriptor(ex, flags) 854 struct extent *ex; 855 int flags; 856 { 857 struct extent_region *rp; 858 859 if (ex->ex_flags & EXF_FIXED) { 860 struct extent_fixed *fex = (struct extent_fixed *)ex; 861 862 while (fex->fex_freelist.lh_first == NULL) { 863 if (flags & EX_MALLOCOK) 864 goto alloc; 865 866 if ((flags & EX_WAITOK) == 0) 867 return (NULL); 868 ex->ex_flags |= EXF_FLWANTED; 869 if (tsleep(&fex->fex_freelist, 870 PRIBIO | ((flags & EX_CATCH) ? PCATCH : 0), 871 "extnt", 0)) 872 return (NULL); 873 } 874 rp = fex->fex_freelist.lh_first; 875 LIST_REMOVE(rp, er_link); 876 877 /* 878 * Don't muck with flags after pulling it off the 879 * freelist; it may be a dynamiclly allocated 880 * region pointer that was kindly given to us, 881 * and we need to preserve that information. 882 */ 883 884 return (rp); 885 } 886 887 alloc: 888 rp = (struct extent_region *) 889 malloc(sizeof(struct extent_region), ex->ex_mtype, 890 (flags & EX_WAITOK) ? M_WAITOK : M_NOWAIT); 891 892 if (rp != NULL) 893 rp->er_flags = ER_ALLOC; 894 895 return (rp); 896 } 897 898 static void 899 extent_free_region_descriptor(ex, rp) 900 struct extent *ex; 901 struct extent_region *rp; 902 { 903 904 if (ex->ex_flags & EXF_FIXED) { 905 struct extent_fixed *fex = (struct extent_fixed *)ex; 906 907 /* 908 * If someone's waiting for a region descriptor, 909 * be nice and give them this one, rather than 910 * just free'ing it back to the system. 911 */ 912 if (rp->er_flags & ER_ALLOC) { 913 if (ex->ex_flags & EXF_FLWANTED) { 914 /* Clear all but ER_ALLOC flag. */ 915 rp->er_flags = ER_ALLOC; 916 LIST_INSERT_HEAD(&fex->fex_freelist, rp, 917 er_link); 918 goto wake_em_up; 919 } else { 920 free(rp, ex->ex_mtype); 921 } 922 } else { 923 /* Clear all flags. */ 924 rp->er_flags = 0; 925 LIST_INSERT_HEAD(&fex->fex_freelist, rp, er_link); 926 } 927 928 if (ex->ex_flags & EXF_FLWANTED) { 929 wake_em_up: 930 ex->ex_flags &= ~EXF_FLWANTED; 931 wakeup(&fex->fex_freelist); 932 } 933 return; 934 } 935 936 /* 937 * We know it's dynamically allocated if we get here. 938 */ 939 free(rp, ex->ex_mtype); 940 } 941 942 void 943 extent_print(ex) 944 struct extent *ex; 945 { 946 struct extent_region *rp; 947 948 if (ex == NULL) 949 panic("extent_print: NULL extent"); 950 951 printf("extent `%s' (0x%lx - 0x%lx), flags = 0x%x\n", ex->ex_name, 952 ex->ex_start, ex->ex_end, ex->ex_flags); 953 954 for (rp = ex->ex_regions.lh_first; rp != NULL; 955 rp = rp->er_link.le_next) 956 printf(" 0x%lx - 0x%lx\n", rp->er_start, rp->er_end); 957 } 958