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