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