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_vmem.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 /*- 2 * Copyright (c)2006,2007,2008,2009 YAMAMOTO Takashi, 3 * Copyright (c) 2013 EMC Corp. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 /* 29 * From: 30 * $NetBSD: vmem_impl.h,v 1.2 2013/01/29 21:26:24 para Exp $ 31 * $NetBSD: subr_vmem.c,v 1.83 2013/03/06 11:20:10 yamt Exp $ 32 */ 33 34 /* 35 * reference: 36 * - Magazines and Vmem: Extending the Slab Allocator 37 * to Many CPUs and Arbitrary Resources 38 * http://www.usenix.org/event/usenix01/bonwick.html 39 */ 40 41 #include <sys/cdefs.h> 42 __FBSDID("$FreeBSD: releng/10.0/sys/kern/subr_vmem.c 254558 2013-08-20 11:06:56Z pho $"); 43 44 #include "opt_ddb.h" 45 46 #include <sys/param.h> 47 #include <sys/systm.h> 48 #include <sys/kernel.h> 49 #include <sys/queue.h> 50 #include <sys/callout.h> 51 #include <sys/hash.h> 52 #include <sys/lock.h> 53 #include <sys/malloc.h> 54 #include <sys/mutex.h> 55 #include <sys/smp.h> 56 #include <sys/condvar.h> 57 #include <sys/sysctl.h> 58 #include <sys/taskqueue.h> 59 #include <sys/vmem.h> 60 61 #include "opt_vm.h" 62 63 #include <vm/uma.h> 64 #include <vm/vm.h> 65 #include <vm/pmap.h> 66 #include <vm/vm_map.h> 67 #include <vm/vm_object.h> 68 #include <vm/vm_kern.h> 69 #include <vm/vm_extern.h> 70 #include <vm/vm_param.h> 71 #include <vm/vm_pageout.h> 72 73 #define VMEM_MAXORDER (sizeof(vmem_size_t) * NBBY) 74 75 #define VMEM_HASHSIZE_MIN 16 76 #define VMEM_HASHSIZE_MAX 131072 77 78 #define VMEM_QCACHE_IDX_MAX 16 79 80 #define VMEM_FITMASK (M_BESTFIT | M_FIRSTFIT) 81 82 #define VMEM_FLAGS \ 83 (M_NOWAIT | M_WAITOK | M_USE_RESERVE | M_NOVM | M_BESTFIT | M_FIRSTFIT) 84 85 #define BT_FLAGS (M_NOWAIT | M_WAITOK | M_USE_RESERVE | M_NOVM) 86 87 #define QC_NAME_MAX 16 88 89 /* 90 * Data structures private to vmem. 91 */ 92 MALLOC_DEFINE(M_VMEM, "vmem", "vmem internal structures"); 93 94 typedef struct vmem_btag bt_t; 95 96 TAILQ_HEAD(vmem_seglist, vmem_btag); 97 LIST_HEAD(vmem_freelist, vmem_btag); 98 LIST_HEAD(vmem_hashlist, vmem_btag); 99 100 struct qcache { 101 uma_zone_t qc_cache; 102 vmem_t *qc_vmem; 103 vmem_size_t qc_size; 104 char qc_name[QC_NAME_MAX]; 105 }; 106 typedef struct qcache qcache_t; 107 #define QC_POOL_TO_QCACHE(pool) ((qcache_t *)(pool->pr_qcache)) 108 109 #define VMEM_NAME_MAX 16 110 111 /* vmem arena */ 112 struct vmem { 113 struct mtx_padalign vm_lock; 114 struct cv vm_cv; 115 char vm_name[VMEM_NAME_MAX+1]; 116 LIST_ENTRY(vmem) vm_alllist; 117 struct vmem_hashlist vm_hash0[VMEM_HASHSIZE_MIN]; 118 struct vmem_freelist vm_freelist[VMEM_MAXORDER]; 119 struct vmem_seglist vm_seglist; 120 struct vmem_hashlist *vm_hashlist; 121 vmem_size_t vm_hashsize; 122 123 /* Constant after init */ 124 vmem_size_t vm_qcache_max; 125 vmem_size_t vm_quantum_mask; 126 vmem_size_t vm_import_quantum; 127 int vm_quantum_shift; 128 129 /* Written on alloc/free */ 130 LIST_HEAD(, vmem_btag) vm_freetags; 131 int vm_nfreetags; 132 int vm_nbusytag; 133 vmem_size_t vm_inuse; 134 vmem_size_t vm_size; 135 136 /* Used on import. */ 137 vmem_import_t *vm_importfn; 138 vmem_release_t *vm_releasefn; 139 void *vm_arg; 140 141 /* Space exhaustion callback. */ 142 vmem_reclaim_t *vm_reclaimfn; 143 144 /* quantum cache */ 145 qcache_t vm_qcache[VMEM_QCACHE_IDX_MAX]; 146 }; 147 148 /* boundary tag */ 149 struct vmem_btag { 150 TAILQ_ENTRY(vmem_btag) bt_seglist; 151 union { 152 LIST_ENTRY(vmem_btag) u_freelist; /* BT_TYPE_FREE */ 153 LIST_ENTRY(vmem_btag) u_hashlist; /* BT_TYPE_BUSY */ 154 } bt_u; 155 #define bt_hashlist bt_u.u_hashlist 156 #define bt_freelist bt_u.u_freelist 157 vmem_addr_t bt_start; 158 vmem_size_t bt_size; 159 int bt_type; 160 }; 161 162 #define BT_TYPE_SPAN 1 /* Allocated from importfn */ 163 #define BT_TYPE_SPAN_STATIC 2 /* vmem_add() or create. */ 164 #define BT_TYPE_FREE 3 /* Available space. */ 165 #define BT_TYPE_BUSY 4 /* Used space. */ 166 #define BT_ISSPAN_P(bt) ((bt)->bt_type <= BT_TYPE_SPAN_STATIC) 167 168 #define BT_END(bt) ((bt)->bt_start + (bt)->bt_size - 1) 169 170 #if defined(DIAGNOSTIC) 171 static int enable_vmem_check = 1; 172 SYSCTL_INT(_debug, OID_AUTO, vmem_check, CTLFLAG_RW, 173 &enable_vmem_check, 0, "Enable vmem check"); 174 static void vmem_check(vmem_t *); 175 #endif 176 177 static struct callout vmem_periodic_ch; 178 static int vmem_periodic_interval; 179 static struct task vmem_periodic_wk; 180 181 static struct mtx_padalign vmem_list_lock; 182 static LIST_HEAD(, vmem) vmem_list = LIST_HEAD_INITIALIZER(vmem_list); 183 184 /* ---- misc */ 185 #define VMEM_CONDVAR_INIT(vm, wchan) cv_init(&vm->vm_cv, wchan) 186 #define VMEM_CONDVAR_DESTROY(vm) cv_destroy(&vm->vm_cv) 187 #define VMEM_CONDVAR_WAIT(vm) cv_wait(&vm->vm_cv, &vm->vm_lock) 188 #define VMEM_CONDVAR_BROADCAST(vm) cv_broadcast(&vm->vm_cv) 189 190 191 #define VMEM_LOCK(vm) mtx_lock(&vm->vm_lock) 192 #define VMEM_TRYLOCK(vm) mtx_trylock(&vm->vm_lock) 193 #define VMEM_UNLOCK(vm) mtx_unlock(&vm->vm_lock) 194 #define VMEM_LOCK_INIT(vm, name) mtx_init(&vm->vm_lock, (name), NULL, MTX_DEF) 195 #define VMEM_LOCK_DESTROY(vm) mtx_destroy(&vm->vm_lock) 196 #define VMEM_ASSERT_LOCKED(vm) mtx_assert(&vm->vm_lock, MA_OWNED); 197 198 #define VMEM_ALIGNUP(addr, align) (-(-(addr) & -(align))) 199 200 #define VMEM_CROSS_P(addr1, addr2, boundary) \ 201 ((((addr1) ^ (addr2)) & -(boundary)) != 0) 202 203 #define ORDER2SIZE(order) ((vmem_size_t)1 << (order)) 204 #define SIZE2ORDER(size) ((int)flsl(size) - 1) 205 206 /* 207 * Maximum number of boundary tags that may be required to satisfy an 208 * allocation. Two may be required to import. Another two may be 209 * required to clip edges. 210 */ 211 #define BT_MAXALLOC 4 212 213 /* 214 * Max free limits the number of locally cached boundary tags. We 215 * just want to avoid hitting the zone allocator for every call. 216 */ 217 #define BT_MAXFREE (BT_MAXALLOC * 8) 218 219 /* Allocator for boundary tags. */ 220 static uma_zone_t vmem_bt_zone; 221 222 /* boot time arena storage. */ 223 static struct vmem kernel_arena_storage; 224 static struct vmem kmem_arena_storage; 225 static struct vmem buffer_arena_storage; 226 static struct vmem transient_arena_storage; 227 vmem_t *kernel_arena = &kernel_arena_storage; 228 vmem_t *kmem_arena = &kmem_arena_storage; 229 vmem_t *buffer_arena = &buffer_arena_storage; 230 vmem_t *transient_arena = &transient_arena_storage; 231 232 #ifdef DEBUG_MEMGUARD 233 static struct vmem memguard_arena_storage; 234 vmem_t *memguard_arena = &memguard_arena_storage; 235 #endif 236 237 /* 238 * Fill the vmem's boundary tag cache. We guarantee that boundary tag 239 * allocation will not fail once bt_fill() passes. To do so we cache 240 * at least the maximum possible tag allocations in the arena. 241 */ 242 static int 243 bt_fill(vmem_t *vm, int flags) 244 { 245 bt_t *bt; 246 247 VMEM_ASSERT_LOCKED(vm); 248 249 /* 250 * Only allow the kmem arena to dip into reserve tags. It is the 251 * vmem where new tags come from. 252 */ 253 flags &= BT_FLAGS; 254 if (vm != kmem_arena) 255 flags &= ~M_USE_RESERVE; 256 257 /* 258 * Loop until we meet the reserve. To minimize the lock shuffle 259 * and prevent simultaneous fills we first try a NOWAIT regardless 260 * of the caller's flags. Specify M_NOVM so we don't recurse while 261 * holding a vmem lock. 262 */ 263 while (vm->vm_nfreetags < BT_MAXALLOC) { 264 bt = uma_zalloc(vmem_bt_zone, 265 (flags & M_USE_RESERVE) | M_NOWAIT | M_NOVM); 266 if (bt == NULL) { 267 VMEM_UNLOCK(vm); 268 bt = uma_zalloc(vmem_bt_zone, flags); 269 VMEM_LOCK(vm); 270 if (bt == NULL && (flags & M_NOWAIT) != 0) 271 break; 272 } 273 LIST_INSERT_HEAD(&vm->vm_freetags, bt, bt_freelist); 274 vm->vm_nfreetags++; 275 } 276 277 if (vm->vm_nfreetags < BT_MAXALLOC) 278 return ENOMEM; 279 280 return 0; 281 } 282 283 /* 284 * Pop a tag off of the freetag stack. 285 */ 286 static bt_t * 287 bt_alloc(vmem_t *vm) 288 { 289 bt_t *bt; 290 291 VMEM_ASSERT_LOCKED(vm); 292 bt = LIST_FIRST(&vm->vm_freetags); 293 MPASS(bt != NULL); 294 LIST_REMOVE(bt, bt_freelist); 295 vm->vm_nfreetags--; 296 297 return bt; 298 } 299 300 /* 301 * Trim the per-vmem free list. Returns with the lock released to 302 * avoid allocator recursions. 303 */ 304 static void 305 bt_freetrim(vmem_t *vm, int freelimit) 306 { 307 LIST_HEAD(, vmem_btag) freetags; 308 bt_t *bt; 309 310 LIST_INIT(&freetags); 311 VMEM_ASSERT_LOCKED(vm); 312 while (vm->vm_nfreetags > freelimit) { 313 bt = LIST_FIRST(&vm->vm_freetags); 314 LIST_REMOVE(bt, bt_freelist); 315 vm->vm_nfreetags--; 316 LIST_INSERT_HEAD(&freetags, bt, bt_freelist); 317 } 318 VMEM_UNLOCK(vm); 319 while ((bt = LIST_FIRST(&freetags)) != NULL) { 320 LIST_REMOVE(bt, bt_freelist); 321 uma_zfree(vmem_bt_zone, bt); 322 } 323 } 324 325 static inline void 326 bt_free(vmem_t *vm, bt_t *bt) 327 { 328 329 VMEM_ASSERT_LOCKED(vm); 330 MPASS(LIST_FIRST(&vm->vm_freetags) != bt); 331 LIST_INSERT_HEAD(&vm->vm_freetags, bt, bt_freelist); 332 vm->vm_nfreetags++; 333 } 334 335 /* 336 * freelist[0] ... [1, 1] 337 * freelist[1] ... [2, 3] 338 * freelist[2] ... [4, 7] 339 * freelist[3] ... [8, 15] 340 * : 341 * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1] 342 * : 343 */ 344 345 static struct vmem_freelist * 346 bt_freehead_tofree(vmem_t *vm, vmem_size_t size) 347 { 348 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 349 const int idx = SIZE2ORDER(qsize); 350 351 MPASS(size != 0 && qsize != 0); 352 MPASS((size & vm->vm_quantum_mask) == 0); 353 MPASS(idx >= 0); 354 MPASS(idx < VMEM_MAXORDER); 355 356 return &vm->vm_freelist[idx]; 357 } 358 359 /* 360 * bt_freehead_toalloc: return the freelist for the given size and allocation 361 * strategy. 362 * 363 * For M_FIRSTFIT, return the list in which any blocks are large enough 364 * for the requested size. otherwise, return the list which can have blocks 365 * large enough for the requested size. 366 */ 367 static struct vmem_freelist * 368 bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, int strat) 369 { 370 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 371 int idx = SIZE2ORDER(qsize); 372 373 MPASS(size != 0 && qsize != 0); 374 MPASS((size & vm->vm_quantum_mask) == 0); 375 376 if (strat == M_FIRSTFIT && ORDER2SIZE(idx) != qsize) { 377 idx++; 378 /* check too large request? */ 379 } 380 MPASS(idx >= 0); 381 MPASS(idx < VMEM_MAXORDER); 382 383 return &vm->vm_freelist[idx]; 384 } 385 386 /* ---- boundary tag hash */ 387 388 static struct vmem_hashlist * 389 bt_hashhead(vmem_t *vm, vmem_addr_t addr) 390 { 391 struct vmem_hashlist *list; 392 unsigned int hash; 393 394 hash = hash32_buf(&addr, sizeof(addr), 0); 395 list = &vm->vm_hashlist[hash % vm->vm_hashsize]; 396 397 return list; 398 } 399 400 static bt_t * 401 bt_lookupbusy(vmem_t *vm, vmem_addr_t addr) 402 { 403 struct vmem_hashlist *list; 404 bt_t *bt; 405 406 VMEM_ASSERT_LOCKED(vm); 407 list = bt_hashhead(vm, addr); 408 LIST_FOREACH(bt, list, bt_hashlist) { 409 if (bt->bt_start == addr) { 410 break; 411 } 412 } 413 414 return bt; 415 } 416 417 static void 418 bt_rembusy(vmem_t *vm, bt_t *bt) 419 { 420 421 VMEM_ASSERT_LOCKED(vm); 422 MPASS(vm->vm_nbusytag > 0); 423 vm->vm_inuse -= bt->bt_size; 424 vm->vm_nbusytag--; 425 LIST_REMOVE(bt, bt_hashlist); 426 } 427 428 static void 429 bt_insbusy(vmem_t *vm, bt_t *bt) 430 { 431 struct vmem_hashlist *list; 432 433 VMEM_ASSERT_LOCKED(vm); 434 MPASS(bt->bt_type == BT_TYPE_BUSY); 435 436 list = bt_hashhead(vm, bt->bt_start); 437 LIST_INSERT_HEAD(list, bt, bt_hashlist); 438 vm->vm_nbusytag++; 439 vm->vm_inuse += bt->bt_size; 440 } 441 442 /* ---- boundary tag list */ 443 444 static void 445 bt_remseg(vmem_t *vm, bt_t *bt) 446 { 447 448 TAILQ_REMOVE(&vm->vm_seglist, bt, bt_seglist); 449 bt_free(vm, bt); 450 } 451 452 static void 453 bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev) 454 { 455 456 TAILQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist); 457 } 458 459 static void 460 bt_insseg_tail(vmem_t *vm, bt_t *bt) 461 { 462 463 TAILQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist); 464 } 465 466 static void 467 bt_remfree(vmem_t *vm, bt_t *bt) 468 { 469 470 MPASS(bt->bt_type == BT_TYPE_FREE); 471 472 LIST_REMOVE(bt, bt_freelist); 473 } 474 475 static void 476 bt_insfree(vmem_t *vm, bt_t *bt) 477 { 478 struct vmem_freelist *list; 479 480 list = bt_freehead_tofree(vm, bt->bt_size); 481 LIST_INSERT_HEAD(list, bt, bt_freelist); 482 } 483 484 /* ---- vmem internal functions */ 485 486 /* 487 * Import from the arena into the quantum cache in UMA. 488 */ 489 static int 490 qc_import(void *arg, void **store, int cnt, int flags) 491 { 492 qcache_t *qc; 493 vmem_addr_t addr; 494 int i; 495 496 qc = arg; 497 flags |= M_BESTFIT; 498 for (i = 0; i < cnt; i++) { 499 if (vmem_xalloc(qc->qc_vmem, qc->qc_size, 0, 0, 0, 500 VMEM_ADDR_MIN, VMEM_ADDR_MAX, flags, &addr) != 0) 501 break; 502 store[i] = (void *)addr; 503 /* Only guarantee one allocation. */ 504 flags &= ~M_WAITOK; 505 flags |= M_NOWAIT; 506 } 507 return i; 508 } 509 510 /* 511 * Release memory from the UMA cache to the arena. 512 */ 513 static void 514 qc_release(void *arg, void **store, int cnt) 515 { 516 qcache_t *qc; 517 int i; 518 519 qc = arg; 520 for (i = 0; i < cnt; i++) 521 vmem_xfree(qc->qc_vmem, (vmem_addr_t)store[i], qc->qc_size); 522 } 523 524 static void 525 qc_init(vmem_t *vm, vmem_size_t qcache_max) 526 { 527 qcache_t *qc; 528 vmem_size_t size; 529 int qcache_idx_max; 530 int i; 531 532 MPASS((qcache_max & vm->vm_quantum_mask) == 0); 533 qcache_idx_max = MIN(qcache_max >> vm->vm_quantum_shift, 534 VMEM_QCACHE_IDX_MAX); 535 vm->vm_qcache_max = qcache_idx_max << vm->vm_quantum_shift; 536 for (i = 0; i < qcache_idx_max; i++) { 537 qc = &vm->vm_qcache[i]; 538 size = (i + 1) << vm->vm_quantum_shift; 539 snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%zu", 540 vm->vm_name, size); 541 qc->qc_vmem = vm; 542 qc->qc_size = size; 543 qc->qc_cache = uma_zcache_create(qc->qc_name, size, 544 NULL, NULL, NULL, NULL, qc_import, qc_release, qc, 545 UMA_ZONE_VM); 546 MPASS(qc->qc_cache); 547 } 548 } 549 550 static void 551 qc_destroy(vmem_t *vm) 552 { 553 int qcache_idx_max; 554 int i; 555 556 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 557 for (i = 0; i < qcache_idx_max; i++) 558 uma_zdestroy(vm->vm_qcache[i].qc_cache); 559 } 560 561 static void 562 qc_drain(vmem_t *vm) 563 { 564 int qcache_idx_max; 565 int i; 566 567 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 568 for (i = 0; i < qcache_idx_max; i++) 569 zone_drain(vm->vm_qcache[i].qc_cache); 570 } 571 572 #ifndef UMA_MD_SMALL_ALLOC 573 574 static struct mtx_padalign vmem_bt_lock; 575 576 /* 577 * vmem_bt_alloc: Allocate a new page of boundary tags. 578 * 579 * On architectures with uma_small_alloc there is no recursion; no address 580 * space need be allocated to allocate boundary tags. For the others, we 581 * must handle recursion. Boundary tags are necessary to allocate new 582 * boundary tags. 583 * 584 * UMA guarantees that enough tags are held in reserve to allocate a new 585 * page of kva. We dip into this reserve by specifying M_USE_RESERVE only 586 * when allocating the page to hold new boundary tags. In this way the 587 * reserve is automatically filled by the allocation that uses the reserve. 588 * 589 * We still have to guarantee that the new tags are allocated atomically since 590 * many threads may try concurrently. The bt_lock provides this guarantee. 591 * We convert WAITOK allocations to NOWAIT and then handle the blocking here 592 * on failure. It's ok to return NULL for a WAITOK allocation as UMA will 593 * loop again after checking to see if we lost the race to allocate. 594 * 595 * There is a small race between vmem_bt_alloc() returning the page and the 596 * zone lock being acquired to add the page to the zone. For WAITOK 597 * allocations we just pause briefly. NOWAIT may experience a transient 598 * failure. To alleviate this we permit a small number of simultaneous 599 * fills to proceed concurrently so NOWAIT is less likely to fail unless 600 * we are really out of KVA. 601 */ 602 static void * 603 vmem_bt_alloc(uma_zone_t zone, int bytes, uint8_t *pflag, int wait) 604 { 605 vmem_addr_t addr; 606 607 *pflag = UMA_SLAB_KMEM; 608 609 /* 610 * Single thread boundary tag allocation so that the address space 611 * and memory are added in one atomic operation. 612 */ 613 mtx_lock(&vmem_bt_lock); 614 if (vmem_xalloc(kmem_arena, bytes, 0, 0, 0, VMEM_ADDR_MIN, 615 VMEM_ADDR_MAX, M_NOWAIT | M_NOVM | M_USE_RESERVE | M_BESTFIT, 616 &addr) == 0) { 617 if (kmem_back(kmem_object, addr, bytes, 618 M_NOWAIT | M_USE_RESERVE) == 0) { 619 mtx_unlock(&vmem_bt_lock); 620 return ((void *)addr); 621 } 622 vmem_xfree(kmem_arena, addr, bytes); 623 mtx_unlock(&vmem_bt_lock); 624 /* 625 * Out of memory, not address space. This may not even be 626 * possible due to M_USE_RESERVE page allocation. 627 */ 628 if (wait & M_WAITOK) 629 VM_WAIT; 630 return (NULL); 631 } 632 mtx_unlock(&vmem_bt_lock); 633 /* 634 * We're either out of address space or lost a fill race. 635 */ 636 if (wait & M_WAITOK) 637 pause("btalloc", 1); 638 639 return (NULL); 640 } 641 #endif 642 643 void 644 vmem_startup(void) 645 { 646 647 mtx_init(&vmem_list_lock, "vmem list lock", NULL, MTX_DEF); 648 vmem_bt_zone = uma_zcreate("vmem btag", 649 sizeof(struct vmem_btag), NULL, NULL, NULL, NULL, 650 UMA_ALIGN_PTR, UMA_ZONE_VM); 651 #ifndef UMA_MD_SMALL_ALLOC 652 mtx_init(&vmem_bt_lock, "btag lock", NULL, MTX_DEF); 653 uma_prealloc(vmem_bt_zone, BT_MAXALLOC); 654 /* 655 * Reserve enough tags to allocate new tags. We allow multiple 656 * CPUs to attempt to allocate new tags concurrently to limit 657 * false restarts in UMA. 658 */ 659 uma_zone_reserve(vmem_bt_zone, BT_MAXALLOC * (mp_ncpus + 1) / 2); 660 uma_zone_set_allocf(vmem_bt_zone, vmem_bt_alloc); 661 #endif 662 } 663 664 /* ---- rehash */ 665 666 static int 667 vmem_rehash(vmem_t *vm, vmem_size_t newhashsize) 668 { 669 bt_t *bt; 670 int i; 671 struct vmem_hashlist *newhashlist; 672 struct vmem_hashlist *oldhashlist; 673 vmem_size_t oldhashsize; 674 675 MPASS(newhashsize > 0); 676 677 newhashlist = malloc(sizeof(struct vmem_hashlist) * newhashsize, 678 M_VMEM, M_NOWAIT); 679 if (newhashlist == NULL) 680 return ENOMEM; 681 for (i = 0; i < newhashsize; i++) { 682 LIST_INIT(&newhashlist[i]); 683 } 684 685 VMEM_LOCK(vm); 686 oldhashlist = vm->vm_hashlist; 687 oldhashsize = vm->vm_hashsize; 688 vm->vm_hashlist = newhashlist; 689 vm->vm_hashsize = newhashsize; 690 if (oldhashlist == NULL) { 691 VMEM_UNLOCK(vm); 692 return 0; 693 } 694 for (i = 0; i < oldhashsize; i++) { 695 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 696 bt_rembusy(vm, bt); 697 bt_insbusy(vm, bt); 698 } 699 } 700 VMEM_UNLOCK(vm); 701 702 if (oldhashlist != vm->vm_hash0) { 703 free(oldhashlist, M_VMEM); 704 } 705 706 return 0; 707 } 708 709 static void 710 vmem_periodic_kick(void *dummy) 711 { 712 713 taskqueue_enqueue(taskqueue_thread, &vmem_periodic_wk); 714 } 715 716 static void 717 vmem_periodic(void *unused, int pending) 718 { 719 vmem_t *vm; 720 vmem_size_t desired; 721 vmem_size_t current; 722 723 mtx_lock(&vmem_list_lock); 724 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 725 #ifdef DIAGNOSTIC 726 /* Convenient time to verify vmem state. */ 727 if (enable_vmem_check == 1) { 728 VMEM_LOCK(vm); 729 vmem_check(vm); 730 VMEM_UNLOCK(vm); 731 } 732 #endif 733 desired = 1 << flsl(vm->vm_nbusytag); 734 desired = MIN(MAX(desired, VMEM_HASHSIZE_MIN), 735 VMEM_HASHSIZE_MAX); 736 current = vm->vm_hashsize; 737 738 /* Grow in powers of two. Shrink less aggressively. */ 739 if (desired >= current * 2 || desired * 4 <= current) 740 vmem_rehash(vm, desired); 741 } 742 mtx_unlock(&vmem_list_lock); 743 744 callout_reset(&vmem_periodic_ch, vmem_periodic_interval, 745 vmem_periodic_kick, NULL); 746 } 747 748 static void 749 vmem_start_callout(void *unused) 750 { 751 752 TASK_INIT(&vmem_periodic_wk, 0, vmem_periodic, NULL); 753 vmem_periodic_interval = hz * 10; 754 callout_init(&vmem_periodic_ch, CALLOUT_MPSAFE); 755 callout_reset(&vmem_periodic_ch, vmem_periodic_interval, 756 vmem_periodic_kick, NULL); 757 } 758 SYSINIT(vfs, SI_SUB_CONFIGURE, SI_ORDER_ANY, vmem_start_callout, NULL); 759 760 static void 761 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, int type) 762 { 763 bt_t *btspan; 764 bt_t *btfree; 765 766 MPASS(type == BT_TYPE_SPAN || type == BT_TYPE_SPAN_STATIC); 767 MPASS((size & vm->vm_quantum_mask) == 0); 768 769 btspan = bt_alloc(vm); 770 btspan->bt_type = type; 771 btspan->bt_start = addr; 772 btspan->bt_size = size; 773 bt_insseg_tail(vm, btspan); 774 775 btfree = bt_alloc(vm); 776 btfree->bt_type = BT_TYPE_FREE; 777 btfree->bt_start = addr; 778 btfree->bt_size = size; 779 bt_insseg(vm, btfree, btspan); 780 bt_insfree(vm, btfree); 781 782 vm->vm_size += size; 783 } 784 785 static void 786 vmem_destroy1(vmem_t *vm) 787 { 788 bt_t *bt; 789 790 /* 791 * Drain per-cpu quantum caches. 792 */ 793 qc_destroy(vm); 794 795 /* 796 * The vmem should now only contain empty segments. 797 */ 798 VMEM_LOCK(vm); 799 MPASS(vm->vm_nbusytag == 0); 800 801 while ((bt = TAILQ_FIRST(&vm->vm_seglist)) != NULL) 802 bt_remseg(vm, bt); 803 804 if (vm->vm_hashlist != NULL && vm->vm_hashlist != vm->vm_hash0) 805 free(vm->vm_hashlist, M_VMEM); 806 807 bt_freetrim(vm, 0); 808 809 VMEM_CONDVAR_DESTROY(vm); 810 VMEM_LOCK_DESTROY(vm); 811 free(vm, M_VMEM); 812 } 813 814 static int 815 vmem_import(vmem_t *vm, vmem_size_t size, vmem_size_t align, int flags) 816 { 817 vmem_addr_t addr; 818 int error; 819 820 if (vm->vm_importfn == NULL) 821 return EINVAL; 822 823 /* 824 * To make sure we get a span that meets the alignment we double it 825 * and add the size to the tail. This slightly overestimates. 826 */ 827 if (align != vm->vm_quantum_mask + 1) 828 size = (align * 2) + size; 829 size = roundup(size, vm->vm_import_quantum); 830 831 /* 832 * Hide MAXALLOC tags so we're guaranteed to be able to add this 833 * span and the tag we want to allocate from it. 834 */ 835 MPASS(vm->vm_nfreetags >= BT_MAXALLOC); 836 vm->vm_nfreetags -= BT_MAXALLOC; 837 VMEM_UNLOCK(vm); 838 error = (vm->vm_importfn)(vm->vm_arg, size, flags, &addr); 839 VMEM_LOCK(vm); 840 vm->vm_nfreetags += BT_MAXALLOC; 841 if (error) 842 return ENOMEM; 843 844 vmem_add1(vm, addr, size, BT_TYPE_SPAN); 845 846 return 0; 847 } 848 849 /* 850 * vmem_fit: check if a bt can satisfy the given restrictions. 851 * 852 * it's a caller's responsibility to ensure the region is big enough 853 * before calling us. 854 */ 855 static int 856 vmem_fit(const bt_t *bt, vmem_size_t size, vmem_size_t align, 857 vmem_size_t phase, vmem_size_t nocross, vmem_addr_t minaddr, 858 vmem_addr_t maxaddr, vmem_addr_t *addrp) 859 { 860 vmem_addr_t start; 861 vmem_addr_t end; 862 863 MPASS(size > 0); 864 MPASS(bt->bt_size >= size); /* caller's responsibility */ 865 866 /* 867 * XXX assumption: vmem_addr_t and vmem_size_t are 868 * unsigned integer of the same size. 869 */ 870 871 start = bt->bt_start; 872 if (start < minaddr) { 873 start = minaddr; 874 } 875 end = BT_END(bt); 876 if (end > maxaddr) 877 end = maxaddr; 878 if (start > end) 879 return (ENOMEM); 880 881 start = VMEM_ALIGNUP(start - phase, align) + phase; 882 if (start < bt->bt_start) 883 start += align; 884 if (VMEM_CROSS_P(start, start + size - 1, nocross)) { 885 MPASS(align < nocross); 886 start = VMEM_ALIGNUP(start - phase, nocross) + phase; 887 } 888 if (start <= end && end - start >= size - 1) { 889 MPASS((start & (align - 1)) == phase); 890 MPASS(!VMEM_CROSS_P(start, start + size - 1, nocross)); 891 MPASS(minaddr <= start); 892 MPASS(maxaddr == 0 || start + size - 1 <= maxaddr); 893 MPASS(bt->bt_start <= start); 894 MPASS(BT_END(bt) - start >= size - 1); 895 *addrp = start; 896 897 return (0); 898 } 899 return (ENOMEM); 900 } 901 902 /* 903 * vmem_clip: Trim the boundary tag edges to the requested start and size. 904 */ 905 static void 906 vmem_clip(vmem_t *vm, bt_t *bt, vmem_addr_t start, vmem_size_t size) 907 { 908 bt_t *btnew; 909 bt_t *btprev; 910 911 VMEM_ASSERT_LOCKED(vm); 912 MPASS(bt->bt_type == BT_TYPE_FREE); 913 MPASS(bt->bt_size >= size); 914 bt_remfree(vm, bt); 915 if (bt->bt_start != start) { 916 btprev = bt_alloc(vm); 917 btprev->bt_type = BT_TYPE_FREE; 918 btprev->bt_start = bt->bt_start; 919 btprev->bt_size = start - bt->bt_start; 920 bt->bt_start = start; 921 bt->bt_size -= btprev->bt_size; 922 bt_insfree(vm, btprev); 923 bt_insseg(vm, btprev, 924 TAILQ_PREV(bt, vmem_seglist, bt_seglist)); 925 } 926 MPASS(bt->bt_start == start); 927 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 928 /* split */ 929 btnew = bt_alloc(vm); 930 btnew->bt_type = BT_TYPE_BUSY; 931 btnew->bt_start = bt->bt_start; 932 btnew->bt_size = size; 933 bt->bt_start = bt->bt_start + size; 934 bt->bt_size -= size; 935 bt_insfree(vm, bt); 936 bt_insseg(vm, btnew, 937 TAILQ_PREV(bt, vmem_seglist, bt_seglist)); 938 bt_insbusy(vm, btnew); 939 bt = btnew; 940 } else { 941 bt->bt_type = BT_TYPE_BUSY; 942 bt_insbusy(vm, bt); 943 } 944 MPASS(bt->bt_size >= size); 945 bt->bt_type = BT_TYPE_BUSY; 946 } 947 948 /* ---- vmem API */ 949 950 void 951 vmem_set_import(vmem_t *vm, vmem_import_t *importfn, 952 vmem_release_t *releasefn, void *arg, vmem_size_t import_quantum) 953 { 954 955 VMEM_LOCK(vm); 956 vm->vm_importfn = importfn; 957 vm->vm_releasefn = releasefn; 958 vm->vm_arg = arg; 959 vm->vm_import_quantum = import_quantum; 960 VMEM_UNLOCK(vm); 961 } 962 963 void 964 vmem_set_reclaim(vmem_t *vm, vmem_reclaim_t *reclaimfn) 965 { 966 967 VMEM_LOCK(vm); 968 vm->vm_reclaimfn = reclaimfn; 969 VMEM_UNLOCK(vm); 970 } 971 972 /* 973 * vmem_init: Initializes vmem arena. 974 */ 975 vmem_t * 976 vmem_init(vmem_t *vm, const char *name, vmem_addr_t base, vmem_size_t size, 977 vmem_size_t quantum, vmem_size_t qcache_max, int flags) 978 { 979 int i; 980 981 MPASS(quantum > 0); 982 983 bzero(vm, sizeof(*vm)); 984 985 VMEM_CONDVAR_INIT(vm, name); 986 VMEM_LOCK_INIT(vm, name); 987 vm->vm_nfreetags = 0; 988 LIST_INIT(&vm->vm_freetags); 989 strlcpy(vm->vm_name, name, sizeof(vm->vm_name)); 990 vm->vm_quantum_mask = quantum - 1; 991 vm->vm_quantum_shift = SIZE2ORDER(quantum); 992 MPASS(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 993 vm->vm_nbusytag = 0; 994 vm->vm_size = 0; 995 vm->vm_inuse = 0; 996 qc_init(vm, qcache_max); 997 998 TAILQ_INIT(&vm->vm_seglist); 999 for (i = 0; i < VMEM_MAXORDER; i++) { 1000 LIST_INIT(&vm->vm_freelist[i]); 1001 } 1002 memset(&vm->vm_hash0, 0, sizeof(vm->vm_hash0)); 1003 vm->vm_hashsize = VMEM_HASHSIZE_MIN; 1004 vm->vm_hashlist = vm->vm_hash0; 1005 1006 if (size != 0) { 1007 if (vmem_add(vm, base, size, flags) != 0) { 1008 vmem_destroy1(vm); 1009 return NULL; 1010 } 1011 } 1012 1013 mtx_lock(&vmem_list_lock); 1014 LIST_INSERT_HEAD(&vmem_list, vm, vm_alllist); 1015 mtx_unlock(&vmem_list_lock); 1016 1017 return vm; 1018 } 1019 1020 /* 1021 * vmem_create: create an arena. 1022 */ 1023 vmem_t * 1024 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 1025 vmem_size_t quantum, vmem_size_t qcache_max, int flags) 1026 { 1027 1028 vmem_t *vm; 1029 1030 vm = malloc(sizeof(*vm), M_VMEM, flags & (M_WAITOK|M_NOWAIT)); 1031 if (vm == NULL) 1032 return (NULL); 1033 if (vmem_init(vm, name, base, size, quantum, qcache_max, 1034 flags) == NULL) { 1035 free(vm, M_VMEM); 1036 return (NULL); 1037 } 1038 return (vm); 1039 } 1040 1041 void 1042 vmem_destroy(vmem_t *vm) 1043 { 1044 1045 mtx_lock(&vmem_list_lock); 1046 LIST_REMOVE(vm, vm_alllist); 1047 mtx_unlock(&vmem_list_lock); 1048 1049 vmem_destroy1(vm); 1050 } 1051 1052 vmem_size_t 1053 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 1054 { 1055 1056 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 1057 } 1058 1059 /* 1060 * vmem_alloc: allocate resource from the arena. 1061 */ 1062 int 1063 vmem_alloc(vmem_t *vm, vmem_size_t size, int flags, vmem_addr_t *addrp) 1064 { 1065 const int strat __unused = flags & VMEM_FITMASK; 1066 qcache_t *qc; 1067 1068 flags &= VMEM_FLAGS; 1069 MPASS(size > 0); 1070 MPASS(strat == M_BESTFIT || strat == M_FIRSTFIT); 1071 if ((flags & M_NOWAIT) == 0) 1072 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "vmem_alloc"); 1073 1074 if (size <= vm->vm_qcache_max) { 1075 qc = &vm->vm_qcache[(size - 1) >> vm->vm_quantum_shift]; 1076 *addrp = (vmem_addr_t)uma_zalloc(qc->qc_cache, flags); 1077 if (*addrp == 0) 1078 return (ENOMEM); 1079 return (0); 1080 } 1081 1082 return vmem_xalloc(vm, size, 0, 0, 0, VMEM_ADDR_MIN, VMEM_ADDR_MAX, 1083 flags, addrp); 1084 } 1085 1086 int 1087 vmem_xalloc(vmem_t *vm, const vmem_size_t size0, vmem_size_t align, 1088 const vmem_size_t phase, const vmem_size_t nocross, 1089 const vmem_addr_t minaddr, const vmem_addr_t maxaddr, int flags, 1090 vmem_addr_t *addrp) 1091 { 1092 const vmem_size_t size = vmem_roundup_size(vm, size0); 1093 struct vmem_freelist *list; 1094 struct vmem_freelist *first; 1095 struct vmem_freelist *end; 1096 vmem_size_t avail; 1097 bt_t *bt; 1098 int error; 1099 int strat; 1100 1101 flags &= VMEM_FLAGS; 1102 strat = flags & VMEM_FITMASK; 1103 MPASS(size0 > 0); 1104 MPASS(size > 0); 1105 MPASS(strat == M_BESTFIT || strat == M_FIRSTFIT); 1106 MPASS((flags & (M_NOWAIT|M_WAITOK)) != (M_NOWAIT|M_WAITOK)); 1107 if ((flags & M_NOWAIT) == 0) 1108 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "vmem_xalloc"); 1109 MPASS((align & vm->vm_quantum_mask) == 0); 1110 MPASS((align & (align - 1)) == 0); 1111 MPASS((phase & vm->vm_quantum_mask) == 0); 1112 MPASS((nocross & vm->vm_quantum_mask) == 0); 1113 MPASS((nocross & (nocross - 1)) == 0); 1114 MPASS((align == 0 && phase == 0) || phase < align); 1115 MPASS(nocross == 0 || nocross >= size); 1116 MPASS(minaddr <= maxaddr); 1117 MPASS(!VMEM_CROSS_P(phase, phase + size - 1, nocross)); 1118 1119 if (align == 0) 1120 align = vm->vm_quantum_mask + 1; 1121 1122 *addrp = 0; 1123 end = &vm->vm_freelist[VMEM_MAXORDER]; 1124 /* 1125 * choose a free block from which we allocate. 1126 */ 1127 first = bt_freehead_toalloc(vm, size, strat); 1128 VMEM_LOCK(vm); 1129 for (;;) { 1130 /* 1131 * Make sure we have enough tags to complete the 1132 * operation. 1133 */ 1134 if (vm->vm_nfreetags < BT_MAXALLOC && 1135 bt_fill(vm, flags) != 0) { 1136 error = ENOMEM; 1137 break; 1138 } 1139 /* 1140 * Scan freelists looking for a tag that satisfies the 1141 * allocation. If we're doing BESTFIT we may encounter 1142 * sizes below the request. If we're doing FIRSTFIT we 1143 * inspect only the first element from each list. 1144 */ 1145 for (list = first; list < end; list++) { 1146 LIST_FOREACH(bt, list, bt_freelist) { 1147 if (bt->bt_size >= size) { 1148 error = vmem_fit(bt, size, align, phase, 1149 nocross, minaddr, maxaddr, addrp); 1150 if (error == 0) { 1151 vmem_clip(vm, bt, *addrp, size); 1152 goto out; 1153 } 1154 } 1155 /* FIRST skips to the next list. */ 1156 if (strat == M_FIRSTFIT) 1157 break; 1158 } 1159 } 1160 /* 1161 * Retry if the fast algorithm failed. 1162 */ 1163 if (strat == M_FIRSTFIT) { 1164 strat = M_BESTFIT; 1165 first = bt_freehead_toalloc(vm, size, strat); 1166 continue; 1167 } 1168 /* 1169 * XXX it is possible to fail to meet restrictions with the 1170 * imported region. It is up to the user to specify the 1171 * import quantum such that it can satisfy any allocation. 1172 */ 1173 if (vmem_import(vm, size, align, flags) == 0) 1174 continue; 1175 1176 /* 1177 * Try to free some space from the quantum cache or reclaim 1178 * functions if available. 1179 */ 1180 if (vm->vm_qcache_max != 0 || vm->vm_reclaimfn != NULL) { 1181 avail = vm->vm_size - vm->vm_inuse; 1182 VMEM_UNLOCK(vm); 1183 if (vm->vm_qcache_max != 0) 1184 qc_drain(vm); 1185 if (vm->vm_reclaimfn != NULL) 1186 vm->vm_reclaimfn(vm, flags); 1187 VMEM_LOCK(vm); 1188 /* If we were successful retry even NOWAIT. */ 1189 if (vm->vm_size - vm->vm_inuse > avail) 1190 continue; 1191 } 1192 if ((flags & M_NOWAIT) != 0) { 1193 error = ENOMEM; 1194 break; 1195 } 1196 VMEM_CONDVAR_WAIT(vm); 1197 } 1198 out: 1199 VMEM_UNLOCK(vm); 1200 if (error != 0 && (flags & M_NOWAIT) == 0) 1201 panic("failed to allocate waiting allocation\n"); 1202 1203 return (error); 1204 } 1205 1206 /* 1207 * vmem_free: free the resource to the arena. 1208 */ 1209 void 1210 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1211 { 1212 qcache_t *qc; 1213 MPASS(size > 0); 1214 1215 if (size <= vm->vm_qcache_max) { 1216 qc = &vm->vm_qcache[(size - 1) >> vm->vm_quantum_shift]; 1217 uma_zfree(qc->qc_cache, (void *)addr); 1218 } else 1219 vmem_xfree(vm, addr, size); 1220 } 1221 1222 void 1223 vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1224 { 1225 bt_t *bt; 1226 bt_t *t; 1227 1228 MPASS(size > 0); 1229 1230 VMEM_LOCK(vm); 1231 bt = bt_lookupbusy(vm, addr); 1232 MPASS(bt != NULL); 1233 MPASS(bt->bt_start == addr); 1234 MPASS(bt->bt_size == vmem_roundup_size(vm, size) || 1235 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 1236 MPASS(bt->bt_type == BT_TYPE_BUSY); 1237 bt_rembusy(vm, bt); 1238 bt->bt_type = BT_TYPE_FREE; 1239 1240 /* coalesce */ 1241 t = TAILQ_NEXT(bt, bt_seglist); 1242 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1243 MPASS(BT_END(bt) < t->bt_start); /* YYY */ 1244 bt->bt_size += t->bt_size; 1245 bt_remfree(vm, t); 1246 bt_remseg(vm, t); 1247 } 1248 t = TAILQ_PREV(bt, vmem_seglist, bt_seglist); 1249 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1250 MPASS(BT_END(t) < bt->bt_start); /* YYY */ 1251 bt->bt_size += t->bt_size; 1252 bt->bt_start = t->bt_start; 1253 bt_remfree(vm, t); 1254 bt_remseg(vm, t); 1255 } 1256 1257 t = TAILQ_PREV(bt, vmem_seglist, bt_seglist); 1258 MPASS(t != NULL); 1259 MPASS(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 1260 if (vm->vm_releasefn != NULL && t->bt_type == BT_TYPE_SPAN && 1261 t->bt_size == bt->bt_size) { 1262 vmem_addr_t spanaddr; 1263 vmem_size_t spansize; 1264 1265 MPASS(t->bt_start == bt->bt_start); 1266 spanaddr = bt->bt_start; 1267 spansize = bt->bt_size; 1268 bt_remseg(vm, bt); 1269 bt_remseg(vm, t); 1270 vm->vm_size -= spansize; 1271 VMEM_CONDVAR_BROADCAST(vm); 1272 bt_freetrim(vm, BT_MAXFREE); 1273 (*vm->vm_releasefn)(vm->vm_arg, spanaddr, spansize); 1274 } else { 1275 bt_insfree(vm, bt); 1276 VMEM_CONDVAR_BROADCAST(vm); 1277 bt_freetrim(vm, BT_MAXFREE); 1278 } 1279 } 1280 1281 /* 1282 * vmem_add: 1283 * 1284 */ 1285 int 1286 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, int flags) 1287 { 1288 int error; 1289 1290 error = 0; 1291 flags &= VMEM_FLAGS; 1292 VMEM_LOCK(vm); 1293 if (vm->vm_nfreetags >= BT_MAXALLOC || bt_fill(vm, flags) == 0) 1294 vmem_add1(vm, addr, size, BT_TYPE_SPAN_STATIC); 1295 else 1296 error = ENOMEM; 1297 VMEM_UNLOCK(vm); 1298 1299 return (error); 1300 } 1301 1302 /* 1303 * vmem_size: information about arenas size 1304 */ 1305 vmem_size_t 1306 vmem_size(vmem_t *vm, int typemask) 1307 { 1308 1309 switch (typemask) { 1310 case VMEM_ALLOC: 1311 return vm->vm_inuse; 1312 case VMEM_FREE: 1313 return vm->vm_size - vm->vm_inuse; 1314 case VMEM_FREE|VMEM_ALLOC: 1315 return vm->vm_size; 1316 default: 1317 panic("vmem_size"); 1318 } 1319 } 1320 1321 /* ---- debug */ 1322 1323 #if defined(DDB) || defined(DIAGNOSTIC) 1324 1325 static void bt_dump(const bt_t *, int (*)(const char *, ...) 1326 __printflike(1, 2)); 1327 1328 static const char * 1329 bt_type_string(int type) 1330 { 1331 1332 switch (type) { 1333 case BT_TYPE_BUSY: 1334 return "busy"; 1335 case BT_TYPE_FREE: 1336 return "free"; 1337 case BT_TYPE_SPAN: 1338 return "span"; 1339 case BT_TYPE_SPAN_STATIC: 1340 return "static span"; 1341 default: 1342 break; 1343 } 1344 return "BOGUS"; 1345 } 1346 1347 static void 1348 bt_dump(const bt_t *bt, int (*pr)(const char *, ...)) 1349 { 1350 1351 (*pr)("\t%p: %jx %jx, %d(%s)\n", 1352 bt, (intmax_t)bt->bt_start, (intmax_t)bt->bt_size, 1353 bt->bt_type, bt_type_string(bt->bt_type)); 1354 } 1355 1356 static void 1357 vmem_dump(const vmem_t *vm , int (*pr)(const char *, ...) __printflike(1, 2)) 1358 { 1359 const bt_t *bt; 1360 int i; 1361 1362 (*pr)("vmem %p '%s'\n", vm, vm->vm_name); 1363 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1364 bt_dump(bt, pr); 1365 } 1366 1367 for (i = 0; i < VMEM_MAXORDER; i++) { 1368 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 1369 1370 if (LIST_EMPTY(fl)) { 1371 continue; 1372 } 1373 1374 (*pr)("freelist[%d]\n", i); 1375 LIST_FOREACH(bt, fl, bt_freelist) { 1376 bt_dump(bt, pr); 1377 } 1378 } 1379 } 1380 1381 #endif /* defined(DDB) || defined(DIAGNOSTIC) */ 1382 1383 #if defined(DDB) 1384 static bt_t * 1385 vmem_whatis_lookup(vmem_t *vm, vmem_addr_t addr) 1386 { 1387 bt_t *bt; 1388 1389 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1390 if (BT_ISSPAN_P(bt)) { 1391 continue; 1392 } 1393 if (bt->bt_start <= addr && addr <= BT_END(bt)) { 1394 return bt; 1395 } 1396 } 1397 1398 return NULL; 1399 } 1400 1401 void 1402 vmem_whatis(vmem_addr_t addr, int (*pr)(const char *, ...)) 1403 { 1404 vmem_t *vm; 1405 1406 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1407 bt_t *bt; 1408 1409 bt = vmem_whatis_lookup(vm, addr); 1410 if (bt == NULL) { 1411 continue; 1412 } 1413 (*pr)("%p is %p+%zu in VMEM '%s' (%s)\n", 1414 (void *)addr, (void *)bt->bt_start, 1415 (vmem_size_t)(addr - bt->bt_start), vm->vm_name, 1416 (bt->bt_type == BT_TYPE_BUSY) ? "allocated" : "free"); 1417 } 1418 } 1419 1420 void 1421 vmem_printall(const char *modif, int (*pr)(const char *, ...)) 1422 { 1423 const vmem_t *vm; 1424 1425 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1426 vmem_dump(vm, pr); 1427 } 1428 } 1429 1430 void 1431 vmem_print(vmem_addr_t addr, const char *modif, int (*pr)(const char *, ...)) 1432 { 1433 const vmem_t *vm = (const void *)addr; 1434 1435 vmem_dump(vm, pr); 1436 } 1437 #endif /* defined(DDB) */ 1438 1439 #define vmem_printf printf 1440 1441 #if defined(DIAGNOSTIC) 1442 1443 static bool 1444 vmem_check_sanity(vmem_t *vm) 1445 { 1446 const bt_t *bt, *bt2; 1447 1448 MPASS(vm != NULL); 1449 1450 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1451 if (bt->bt_start > BT_END(bt)) { 1452 printf("corrupted tag\n"); 1453 bt_dump(bt, vmem_printf); 1454 return false; 1455 } 1456 } 1457 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1458 TAILQ_FOREACH(bt2, &vm->vm_seglist, bt_seglist) { 1459 if (bt == bt2) { 1460 continue; 1461 } 1462 if (BT_ISSPAN_P(bt) != BT_ISSPAN_P(bt2)) { 1463 continue; 1464 } 1465 if (bt->bt_start <= BT_END(bt2) && 1466 bt2->bt_start <= BT_END(bt)) { 1467 printf("overwrapped tags\n"); 1468 bt_dump(bt, vmem_printf); 1469 bt_dump(bt2, vmem_printf); 1470 return false; 1471 } 1472 } 1473 } 1474 1475 return true; 1476 } 1477 1478 static void 1479 vmem_check(vmem_t *vm) 1480 { 1481 1482 if (!vmem_check_sanity(vm)) { 1483 panic("insanity vmem %p", vm); 1484 } 1485 } 1486 1487 #endif /* defined(DIAGNOSTIC) */
Cache object: 9ab2b6b4b9e3a228b22f4bffa30a205e
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]