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