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