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