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