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