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