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