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