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