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