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