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