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