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