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