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