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