1 /* $NetBSD: subr_vmem.c,v 1.116 2024/04/24 02:08:03 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c)2006,2007,2008,2009 YAMAMOTO Takashi, 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 /* 30 * reference: 31 * - Magazines and Vmem: Extending the Slab Allocator 32 * to Many CPUs and Arbitrary Resources 33 * http://www.usenix.org/event/usenix01/bonwick.html 34 * 35 * locking & the boundary tag pool: 36 * - A pool(9) is used for vmem boundary tags 37 * - During a pool get call the global vmem_btag_refill_lock is taken, 38 * to serialize access to the allocation reserve, but no other 39 * vmem arena locks. 40 * - During pool_put calls no vmem mutexes are locked. 41 * - pool_drain doesn't hold the pool's mutex while releasing memory to 42 * its backing therefore no interference with any vmem mutexes. 43 * - The boundary tag pool is forced to put page headers into pool pages 44 * (PR_PHINPAGE) and not off page to avoid pool recursion. 45 * (due to sizeof(bt_t) it should be the case anyway) 46 */ 47 48 #include <sys/cdefs.h> 49 __KERNEL_RCSID(0, "$NetBSD: subr_vmem.c,v 1.116 2024/04/24 02:08:03 thorpej Exp $"); 50 51 #if defined(_KERNEL) && defined(_KERNEL_OPT) 52 #include "opt_ddb.h" 53 #endif /* defined(_KERNEL) && defined(_KERNEL_OPT) */ 54 55 #include <sys/param.h> 56 #include <sys/hash.h> 57 #include <sys/queue.h> 58 #include <sys/bitops.h> 59 60 #if defined(_KERNEL) 61 #include <sys/systm.h> 62 #include <sys/kernel.h> /* hz */ 63 #include <sys/callout.h> 64 #include <sys/kmem.h> 65 #include <sys/pool.h> 66 #include <sys/vmem.h> 67 #include <sys/vmem_impl.h> 68 #include <sys/workqueue.h> 69 #include <sys/atomic.h> 70 #include <uvm/uvm.h> 71 #include <uvm/uvm_extern.h> 72 #include <uvm/uvm_km.h> 73 #include <uvm/uvm_page.h> 74 #include <uvm/uvm_pdaemon.h> 75 #else /* defined(_KERNEL) */ 76 #include <stdio.h> 77 #include <errno.h> 78 #include <assert.h> 79 #include <stdlib.h> 80 #include <string.h> 81 #include "../sys/vmem.h" 82 #include "../sys/vmem_impl.h" 83 #endif /* defined(_KERNEL) */ 84 85 86 #if defined(_KERNEL) 87 #include <sys/evcnt.h> 88 #define VMEM_EVCNT_DEFINE(name) \ 89 struct evcnt vmem_evcnt_##name = EVCNT_INITIALIZER(EVCNT_TYPE_MISC, NULL, \ 90 "vmem", #name); \ 91 EVCNT_ATTACH_STATIC(vmem_evcnt_##name); 92 #define VMEM_EVCNT_INCR(ev) vmem_evcnt_##ev.ev_count++ 93 #define VMEM_EVCNT_DECR(ev) vmem_evcnt_##ev.ev_count-- 94 95 VMEM_EVCNT_DEFINE(static_bt_count) 96 VMEM_EVCNT_DEFINE(static_bt_inuse) 97 98 #define VMEM_CONDVAR_INIT(vm, wchan) cv_init(&vm->vm_cv, wchan) 99 #define VMEM_CONDVAR_DESTROY(vm) cv_destroy(&vm->vm_cv) 100 #define VMEM_CONDVAR_WAIT(vm) cv_wait(&vm->vm_cv, &vm->vm_lock) 101 #define VMEM_CONDVAR_BROADCAST(vm) cv_broadcast(&vm->vm_cv) 102 103 #else /* defined(_KERNEL) */ 104 105 #define VMEM_EVCNT_INCR(ev) /* nothing */ 106 #define VMEM_EVCNT_DECR(ev) /* nothing */ 107 108 #define VMEM_CONDVAR_INIT(vm, wchan) /* nothing */ 109 #define VMEM_CONDVAR_DESTROY(vm) /* nothing */ 110 #define VMEM_CONDVAR_WAIT(vm) /* nothing */ 111 #define VMEM_CONDVAR_BROADCAST(vm) /* nothing */ 112 113 #define UNITTEST 114 #define KASSERT(a) assert(a) 115 #define KASSERTMSG(a, m, ...) assert(a) 116 #define mutex_init(a, b, c) /* nothing */ 117 #define mutex_destroy(a) /* nothing */ 118 #define mutex_enter(a) /* nothing */ 119 #define mutex_tryenter(a) true 120 #define mutex_exit(a) /* nothing */ 121 #define mutex_owned(a) true 122 #define ASSERT_SLEEPABLE() /* nothing */ 123 #define panic(...) printf(__VA_ARGS__); abort() 124 #endif /* defined(_KERNEL) */ 125 126 #if defined(VMEM_SANITY) 127 static void vmem_check(vmem_t *); 128 #else /* defined(VMEM_SANITY) */ 129 #define vmem_check(vm) /* nothing */ 130 #endif /* defined(VMEM_SANITY) */ 131 132 #define VMEM_HASHSIZE_MIN 1 /* XXX */ 133 #define VMEM_HASHSIZE_MAX 65536 /* XXX */ 134 #define VMEM_HASHSIZE_INIT 1 135 136 #define VM_FITMASK (VM_BESTFIT | VM_INSTANTFIT) 137 138 #if defined(_KERNEL) 139 static bool vmem_bootstrapped = false; 140 static kmutex_t vmem_list_lock; 141 static LIST_HEAD(, vmem) vmem_list = LIST_HEAD_INITIALIZER(vmem_list); 142 #endif /* defined(_KERNEL) */ 143 144 /* ---- misc */ 145 146 #define VMEM_LOCK(vm) mutex_enter(&(vm)->vm_lock) 147 #define VMEM_TRYLOCK(vm) mutex_tryenter(&(vm)->vm_lock) 148 #define VMEM_UNLOCK(vm) mutex_exit(&(vm)->vm_lock) 149 #define VMEM_LOCK_INIT(vm, ipl) mutex_init(&(vm)->vm_lock, MUTEX_DEFAULT, (ipl)) 150 #define VMEM_LOCK_DESTROY(vm) mutex_destroy(&(vm)->vm_lock) 151 #define VMEM_ASSERT_LOCKED(vm) KASSERT(mutex_owned(&(vm)->vm_lock)) 152 153 #define VMEM_ALIGNUP(addr, align) \ 154 (-(-(addr) & -(align))) 155 156 #define VMEM_CROSS_P(addr1, addr2, boundary) \ 157 ((((addr1) ^ (addr2)) & -(boundary)) != 0) 158 159 #define ORDER2SIZE(order) ((vmem_size_t)1 << (order)) 160 #define SIZE2ORDER(size) ((int)ilog2(size)) 161 162 static void 163 vmem_kick_pdaemon(void) 164 { 165 #if defined(_KERNEL) 166 uvm_kick_pdaemon(); 167 #endif 168 } 169 170 static void vmem_xfree_bt(vmem_t *, bt_t *); 171 172 #if !defined(_KERNEL) 173 #define xmalloc(sz, flags) malloc(sz) 174 #define xfree(p, sz) free(p) 175 #define bt_alloc(vm, flags) malloc(sizeof(bt_t)) 176 #define bt_free(vm, bt) free(bt) 177 #define bt_freetrim(vm, l) /* nothing */ 178 #else /* defined(_KERNEL) */ 179 180 #define xmalloc(sz, flags) \ 181 kmem_alloc(sz, ((flags) & VM_SLEEP) ? KM_SLEEP : KM_NOSLEEP); 182 #define xfree(p, sz) kmem_free(p, sz); 183 184 /* 185 * BT_RESERVE calculation: 186 * we allocate memory for boundary tags with vmem; therefore we have 187 * to keep a reserve of bts used to allocated memory for bts. 188 * This reserve is 4 for each arena involved in allocating vmems memory. 189 * BT_MAXFREE: don't cache excessive counts of bts in arenas 190 */ 191 #define STATIC_BT_COUNT 200 192 #define BT_MINRESERVE 4 193 #define BT_MAXFREE 64 194 195 static struct vmem_btag static_bts[STATIC_BT_COUNT]; 196 static int static_bt_count = STATIC_BT_COUNT; 197 198 static struct vmem kmem_va_meta_arena_store; 199 vmem_t *kmem_va_meta_arena; 200 static struct vmem kmem_meta_arena_store; 201 vmem_t *kmem_meta_arena = NULL; 202 203 static kmutex_t vmem_btag_refill_lock; 204 static kmutex_t vmem_btag_lock; 205 static LIST_HEAD(, vmem_btag) vmem_btag_freelist; 206 static size_t vmem_btag_freelist_count = 0; 207 static struct pool vmem_btag_pool; 208 static bool vmem_btag_pool_initialized __read_mostly; 209 210 /* ---- boundary tag */ 211 212 static int bt_refill(vmem_t *vm); 213 static int bt_refill_locked(vmem_t *vm); 214 215 static void * 216 pool_page_alloc_vmem_meta(struct pool *pp, int flags) 217 { 218 const vm_flag_t vflags = (flags & PR_WAITOK) ? VM_SLEEP: VM_NOSLEEP; 219 vmem_addr_t va; 220 int ret; 221 222 ret = vmem_alloc(kmem_meta_arena, pp->pr_alloc->pa_pagesz, 223 (vflags & ~VM_FITMASK) | VM_INSTANTFIT | VM_POPULATING, &va); 224 225 return ret ? NULL : (void *)va; 226 } 227 228 static void 229 pool_page_free_vmem_meta(struct pool *pp, void *v) 230 { 231 232 vmem_free(kmem_meta_arena, (vmem_addr_t)v, pp->pr_alloc->pa_pagesz); 233 } 234 235 /* allocator for vmem-pool metadata */ 236 struct pool_allocator pool_allocator_vmem_meta = { 237 .pa_alloc = pool_page_alloc_vmem_meta, 238 .pa_free = pool_page_free_vmem_meta, 239 .pa_pagesz = 0 240 }; 241 242 static int 243 bt_refill_locked(vmem_t *vm) 244 { 245 bt_t *bt; 246 247 VMEM_ASSERT_LOCKED(vm); 248 249 if (vm->vm_nfreetags > BT_MINRESERVE) { 250 return 0; 251 } 252 253 mutex_enter(&vmem_btag_lock); 254 while (!LIST_EMPTY(&vmem_btag_freelist) && 255 vm->vm_nfreetags <= BT_MINRESERVE && 256 (vm->vm_flags & VM_PRIVTAGS) == 0) { 257 bt = LIST_FIRST(&vmem_btag_freelist); 258 LIST_REMOVE(bt, bt_freelist); 259 bt->bt_flags = 0; 260 LIST_INSERT_HEAD(&vm->vm_freetags, bt, bt_freelist); 261 vm->vm_nfreetags++; 262 vmem_btag_freelist_count--; 263 VMEM_EVCNT_INCR(static_bt_inuse); 264 } 265 mutex_exit(&vmem_btag_lock); 266 267 while (vm->vm_nfreetags <= BT_MINRESERVE) { 268 VMEM_UNLOCK(vm); 269 KASSERT(vmem_btag_pool_initialized); 270 mutex_enter(&vmem_btag_refill_lock); 271 bt = pool_get(&vmem_btag_pool, PR_NOWAIT); 272 mutex_exit(&vmem_btag_refill_lock); 273 VMEM_LOCK(vm); 274 if (bt == NULL) 275 break; 276 bt->bt_flags = 0; 277 LIST_INSERT_HEAD(&vm->vm_freetags, bt, bt_freelist); 278 vm->vm_nfreetags++; 279 } 280 281 if (vm->vm_nfreetags <= BT_MINRESERVE) { 282 return ENOMEM; 283 } 284 285 if (kmem_meta_arena != NULL) { 286 VMEM_UNLOCK(vm); 287 (void)bt_refill(kmem_arena); 288 (void)bt_refill(kmem_va_meta_arena); 289 (void)bt_refill(kmem_meta_arena); 290 VMEM_LOCK(vm); 291 } 292 293 return 0; 294 } 295 296 static int 297 bt_refill(vmem_t *vm) 298 { 299 int rv; 300 301 VMEM_LOCK(vm); 302 rv = bt_refill_locked(vm); 303 VMEM_UNLOCK(vm); 304 return rv; 305 } 306 307 static bt_t * 308 bt_alloc(vmem_t *vm, vm_flag_t flags) 309 { 310 bt_t *bt; 311 312 VMEM_ASSERT_LOCKED(vm); 313 314 while (vm->vm_nfreetags <= BT_MINRESERVE && (flags & VM_POPULATING) == 0) { 315 if (bt_refill_locked(vm)) { 316 if ((flags & VM_NOSLEEP) != 0) { 317 return NULL; 318 } 319 320 /* 321 * It would be nice to wait for something specific here 322 * but there are multiple ways that a retry could 323 * succeed and we can't wait for multiple things 324 * simultaneously. So we'll just sleep for an arbitrary 325 * short period of time and retry regardless. 326 * This should be a very rare case. 327 */ 328 329 vmem_kick_pdaemon(); 330 kpause("btalloc", false, 1, &vm->vm_lock); 331 } 332 } 333 bt = LIST_FIRST(&vm->vm_freetags); 334 LIST_REMOVE(bt, bt_freelist); 335 vm->vm_nfreetags--; 336 337 return bt; 338 } 339 340 static void 341 bt_free(vmem_t *vm, bt_t *bt) 342 { 343 344 VMEM_ASSERT_LOCKED(vm); 345 346 LIST_INSERT_HEAD(&vm->vm_freetags, bt, bt_freelist); 347 vm->vm_nfreetags++; 348 } 349 350 static void 351 bt_freetrim(vmem_t *vm, int freelimit) 352 { 353 bt_t *bt, *next_bt; 354 LIST_HEAD(, vmem_btag) tofree; 355 356 VMEM_ASSERT_LOCKED(vm); 357 358 LIST_INIT(&tofree); 359 360 LIST_FOREACH_SAFE(bt, &vm->vm_freetags, bt_freelist, next_bt) { 361 if (vm->vm_nfreetags <= freelimit) { 362 break; 363 } 364 if (bt->bt_flags & BT_F_PRIVATE) { 365 continue; 366 } 367 LIST_REMOVE(bt, bt_freelist); 368 vm->vm_nfreetags--; 369 if (bt >= static_bts 370 && bt < &static_bts[STATIC_BT_COUNT]) { 371 mutex_enter(&vmem_btag_lock); 372 LIST_INSERT_HEAD(&vmem_btag_freelist, bt, bt_freelist); 373 vmem_btag_freelist_count++; 374 mutex_exit(&vmem_btag_lock); 375 VMEM_EVCNT_DECR(static_bt_inuse); 376 } else { 377 LIST_INSERT_HEAD(&tofree, bt, bt_freelist); 378 } 379 } 380 381 VMEM_UNLOCK(vm); 382 while (!LIST_EMPTY(&tofree)) { 383 bt = LIST_FIRST(&tofree); 384 LIST_REMOVE(bt, bt_freelist); 385 pool_put(&vmem_btag_pool, bt); 386 } 387 } 388 389 /* 390 * Add private boundary tags (statically-allocated by the caller) 391 * to a vmem arena's free tag list. 392 */ 393 void 394 vmem_add_bts(vmem_t *vm, struct vmem_btag *bts, unsigned int nbts) 395 { 396 VMEM_LOCK(vm); 397 while (nbts != 0) { 398 bts->bt_flags = BT_F_PRIVATE; 399 LIST_INSERT_HEAD(&vm->vm_freetags, bts, bt_freelist); 400 vm->vm_nfreetags++; 401 bts++; 402 nbts--; 403 } 404 VMEM_UNLOCK(vm); 405 } 406 #endif /* defined(_KERNEL) */ 407 408 /* 409 * freelist[0] ... [1, 1] 410 * freelist[1] ... [2, 3] 411 * freelist[2] ... [4, 7] 412 * freelist[3] ... [8, 15] 413 * : 414 * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1] 415 * : 416 */ 417 418 static struct vmem_freelist * 419 bt_freehead_tofree(vmem_t *vm, vmem_size_t size) 420 { 421 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 422 const int idx = SIZE2ORDER(qsize); 423 424 KASSERT(size != 0); 425 KASSERT(qsize != 0); 426 KASSERT((size & vm->vm_quantum_mask) == 0); 427 KASSERT(idx >= 0); 428 KASSERT(idx < VMEM_MAXORDER); 429 430 return &vm->vm_freelist[idx]; 431 } 432 433 /* 434 * bt_freehead_toalloc: return the freelist for the given size and allocation 435 * strategy. 436 * 437 * for VM_INSTANTFIT, return the list in which any blocks are large enough 438 * for the requested size. otherwise, return the list which can have blocks 439 * large enough for the requested size. 440 */ 441 442 static struct vmem_freelist * 443 bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, vm_flag_t strat) 444 { 445 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 446 int idx = SIZE2ORDER(qsize); 447 448 KASSERT(size != 0); 449 KASSERT(qsize != 0); 450 KASSERT((size & vm->vm_quantum_mask) == 0); 451 452 if (strat == VM_INSTANTFIT && ORDER2SIZE(idx) != qsize) { 453 idx++; 454 /* check too large request? */ 455 } 456 KASSERT(idx >= 0); 457 KASSERT(idx < VMEM_MAXORDER); 458 459 return &vm->vm_freelist[idx]; 460 } 461 462 /* ---- boundary tag hash */ 463 464 static struct vmem_hashlist * 465 bt_hashhead(vmem_t *vm, vmem_addr_t addr) 466 { 467 struct vmem_hashlist *list; 468 unsigned int hash; 469 470 hash = hash32_buf(&addr, sizeof(addr), HASH32_BUF_INIT); 471 list = &vm->vm_hashlist[hash & vm->vm_hashmask]; 472 473 return list; 474 } 475 476 static bt_t * 477 bt_lookupbusy(vmem_t *vm, vmem_addr_t addr) 478 { 479 struct vmem_hashlist *list; 480 bt_t *bt; 481 482 list = bt_hashhead(vm, addr); 483 LIST_FOREACH(bt, list, bt_hashlist) { 484 if (bt->bt_start == addr) { 485 break; 486 } 487 } 488 489 return bt; 490 } 491 492 static void 493 bt_rembusy(vmem_t *vm, bt_t *bt) 494 { 495 496 KASSERT(vm->vm_nbusytag > 0); 497 vm->vm_inuse -= bt->bt_size; 498 vm->vm_nbusytag--; 499 LIST_REMOVE(bt, bt_hashlist); 500 } 501 502 static void 503 bt_insbusy(vmem_t *vm, bt_t *bt) 504 { 505 struct vmem_hashlist *list; 506 507 KASSERT(bt->bt_type == BT_TYPE_BUSY); 508 509 list = bt_hashhead(vm, bt->bt_start); 510 LIST_INSERT_HEAD(list, bt, bt_hashlist); 511 if (++vm->vm_nbusytag > vm->vm_maxbusytag) { 512 vm->vm_maxbusytag = vm->vm_nbusytag; 513 } 514 vm->vm_inuse += bt->bt_size; 515 } 516 517 /* ---- boundary tag list */ 518 519 static void 520 bt_remseg(vmem_t *vm, bt_t *bt) 521 { 522 523 TAILQ_REMOVE(&vm->vm_seglist, bt, bt_seglist); 524 } 525 526 static void 527 bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev) 528 { 529 530 TAILQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist); 531 } 532 533 static void 534 bt_insseg_tail(vmem_t *vm, bt_t *bt) 535 { 536 537 TAILQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist); 538 } 539 540 static void 541 bt_remfree(vmem_t *vm, bt_t *bt) 542 { 543 544 KASSERT(bt->bt_type == BT_TYPE_FREE); 545 546 LIST_REMOVE(bt, bt_freelist); 547 } 548 549 static void 550 bt_insfree(vmem_t *vm, bt_t *bt) 551 { 552 struct vmem_freelist *list; 553 554 list = bt_freehead_tofree(vm, bt->bt_size); 555 LIST_INSERT_HEAD(list, bt, bt_freelist); 556 } 557 558 /* ---- vmem internal functions */ 559 560 #if defined(QCACHE) 561 static inline vm_flag_t 562 prf_to_vmf(int prflags) 563 { 564 vm_flag_t vmflags; 565 566 KASSERT((prflags & ~(PR_LIMITFAIL | PR_WAITOK | PR_NOWAIT)) == 0); 567 if ((prflags & PR_WAITOK) != 0) { 568 vmflags = VM_SLEEP; 569 } else { 570 vmflags = VM_NOSLEEP; 571 } 572 return vmflags; 573 } 574 575 static inline int 576 vmf_to_prf(vm_flag_t vmflags) 577 { 578 int prflags; 579 580 if ((vmflags & VM_SLEEP) != 0) { 581 prflags = PR_WAITOK; 582 } else { 583 prflags = PR_NOWAIT; 584 } 585 return prflags; 586 } 587 588 static size_t 589 qc_poolpage_size(size_t qcache_max) 590 { 591 int i; 592 593 for (i = 0; ORDER2SIZE(i) <= qcache_max * 3; i++) { 594 /* nothing */ 595 } 596 return ORDER2SIZE(i); 597 } 598 599 static void * 600 qc_poolpage_alloc(struct pool *pool, int prflags) 601 { 602 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 603 vmem_t *vm = qc->qc_vmem; 604 vmem_addr_t addr; 605 606 if (vmem_alloc(vm, pool->pr_alloc->pa_pagesz, 607 prf_to_vmf(prflags) | VM_INSTANTFIT, &addr) != 0) 608 return NULL; 609 return (void *)addr; 610 } 611 612 static void 613 qc_poolpage_free(struct pool *pool, void *addr) 614 { 615 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 616 vmem_t *vm = qc->qc_vmem; 617 618 vmem_free(vm, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz); 619 } 620 621 static void 622 qc_init(vmem_t *vm, size_t qcache_max, int ipl) 623 { 624 qcache_t *prevqc; 625 struct pool_allocator *pa; 626 int qcache_idx_max; 627 int i; 628 629 KASSERT((qcache_max & vm->vm_quantum_mask) == 0); 630 if (qcache_max > (VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift)) { 631 qcache_max = VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift; 632 } 633 vm->vm_qcache_max = qcache_max; 634 pa = &vm->vm_qcache_allocator; 635 memset(pa, 0, sizeof(*pa)); 636 pa->pa_alloc = qc_poolpage_alloc; 637 pa->pa_free = qc_poolpage_free; 638 pa->pa_pagesz = qc_poolpage_size(qcache_max); 639 640 qcache_idx_max = qcache_max >> vm->vm_quantum_shift; 641 prevqc = NULL; 642 for (i = qcache_idx_max; i > 0; i--) { 643 qcache_t *qc = &vm->vm_qcache_store[i - 1]; 644 size_t size = i << vm->vm_quantum_shift; 645 pool_cache_t pc; 646 647 qc->qc_vmem = vm; 648 snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%zu", 649 vm->vm_name, size); 650 651 pc = pool_cache_init(size, 652 ORDER2SIZE(vm->vm_quantum_shift), 0, 653 PR_NOALIGN | PR_NOTOUCH | PR_RECURSIVE /* XXX */, 654 qc->qc_name, pa, ipl, NULL, NULL, NULL); 655 656 KASSERT(pc); 657 658 qc->qc_cache = pc; 659 KASSERT(qc->qc_cache != NULL); /* XXX */ 660 if (prevqc != NULL && 661 qc->qc_cache->pc_pool.pr_itemsperpage == 662 prevqc->qc_cache->pc_pool.pr_itemsperpage) { 663 pool_cache_destroy(qc->qc_cache); 664 vm->vm_qcache[i - 1] = prevqc; 665 continue; 666 } 667 qc->qc_cache->pc_pool.pr_qcache = qc; 668 vm->vm_qcache[i - 1] = qc; 669 prevqc = qc; 670 } 671 } 672 673 static void 674 qc_destroy(vmem_t *vm) 675 { 676 const qcache_t *prevqc; 677 int i; 678 int qcache_idx_max; 679 680 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 681 prevqc = NULL; 682 for (i = 0; i < qcache_idx_max; i++) { 683 qcache_t *qc = vm->vm_qcache[i]; 684 685 if (prevqc == qc) { 686 continue; 687 } 688 pool_cache_destroy(qc->qc_cache); 689 prevqc = qc; 690 } 691 } 692 #endif 693 694 #if defined(_KERNEL) 695 static void 696 vmem_bootstrap(void) 697 { 698 699 mutex_init(&vmem_list_lock, MUTEX_DEFAULT, IPL_NONE); 700 mutex_init(&vmem_btag_lock, MUTEX_DEFAULT, IPL_VM); 701 mutex_init(&vmem_btag_refill_lock, MUTEX_DEFAULT, IPL_VM); 702 703 while (static_bt_count-- > 0) { 704 bt_t *bt = &static_bts[static_bt_count]; 705 LIST_INSERT_HEAD(&vmem_btag_freelist, bt, bt_freelist); 706 VMEM_EVCNT_INCR(static_bt_count); 707 vmem_btag_freelist_count++; 708 } 709 vmem_bootstrapped = TRUE; 710 } 711 712 void 713 vmem_subsystem_init(vmem_t *vm) 714 { 715 716 kmem_va_meta_arena = vmem_init(&kmem_va_meta_arena_store, "vmem-va", 717 0, 0, PAGE_SIZE, vmem_alloc, vmem_free, vm, 718 0, VM_NOSLEEP | VM_BOOTSTRAP | VM_LARGEIMPORT, 719 IPL_VM); 720 721 kmem_meta_arena = vmem_init(&kmem_meta_arena_store, "vmem-meta", 722 0, 0, PAGE_SIZE, 723 uvm_km_kmem_alloc, uvm_km_kmem_free, kmem_va_meta_arena, 724 0, VM_NOSLEEP | VM_BOOTSTRAP, IPL_VM); 725 726 pool_init(&vmem_btag_pool, sizeof(bt_t), coherency_unit, 0, 727 PR_PHINPAGE, "vmembt", &pool_allocator_vmem_meta, IPL_VM); 728 vmem_btag_pool_initialized = true; 729 } 730 #endif /* defined(_KERNEL) */ 731 732 static int 733 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 734 int spanbttype) 735 { 736 bt_t *btspan; 737 bt_t *btfree; 738 739 VMEM_ASSERT_LOCKED(vm); 740 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 741 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 742 KASSERT(spanbttype == BT_TYPE_SPAN || 743 spanbttype == BT_TYPE_SPAN_STATIC); 744 745 btspan = bt_alloc(vm, flags); 746 if (btspan == NULL) { 747 return ENOMEM; 748 } 749 btfree = bt_alloc(vm, flags); 750 if (btfree == NULL) { 751 bt_free(vm, btspan); 752 return ENOMEM; 753 } 754 755 btspan->bt_type = spanbttype; 756 btspan->bt_start = addr; 757 btspan->bt_size = size; 758 759 btfree->bt_type = BT_TYPE_FREE; 760 btfree->bt_start = addr; 761 btfree->bt_size = size; 762 763 bt_insseg_tail(vm, btspan); 764 bt_insseg(vm, btfree, btspan); 765 bt_insfree(vm, btfree); 766 vm->vm_size += size; 767 768 return 0; 769 } 770 771 static void 772 vmem_destroy1(vmem_t *vm) 773 { 774 775 #if defined(QCACHE) 776 qc_destroy(vm); 777 #endif /* defined(QCACHE) */ 778 VMEM_LOCK(vm); 779 780 for (int i = 0; i < vm->vm_hashsize; i++) { 781 bt_t *bt; 782 783 while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) { 784 KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC); 785 LIST_REMOVE(bt, bt_hashlist); 786 bt_free(vm, bt); 787 } 788 } 789 790 /* bt_freetrim() drops the lock. */ 791 bt_freetrim(vm, 0); 792 if (vm->vm_hashlist != &vm->vm_hash0) { 793 xfree(vm->vm_hashlist, 794 sizeof(struct vmem_hashlist) * vm->vm_hashsize); 795 } 796 797 VMEM_CONDVAR_DESTROY(vm); 798 VMEM_LOCK_DESTROY(vm); 799 xfree(vm, sizeof(*vm)); 800 } 801 802 static int 803 vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 804 { 805 vmem_addr_t addr; 806 int rc; 807 808 VMEM_ASSERT_LOCKED(vm); 809 810 if (vm->vm_importfn == NULL) { 811 return EINVAL; 812 } 813 814 if (vm->vm_flags & VM_LARGEIMPORT) { 815 size *= 16; 816 } 817 818 VMEM_UNLOCK(vm); 819 if (vm->vm_flags & VM_XIMPORT) { 820 rc = __FPTRCAST(vmem_ximport_t *, vm->vm_importfn)(vm->vm_arg, 821 size, &size, flags, &addr); 822 } else { 823 rc = (vm->vm_importfn)(vm->vm_arg, size, flags, &addr); 824 } 825 VMEM_LOCK(vm); 826 827 if (rc) { 828 return ENOMEM; 829 } 830 831 if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) != 0) { 832 VMEM_UNLOCK(vm); 833 (*vm->vm_releasefn)(vm->vm_arg, addr, size); 834 VMEM_LOCK(vm); 835 return ENOMEM; 836 } 837 838 return 0; 839 } 840 841 #if defined(_KERNEL) 842 static int 843 vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags) 844 { 845 bt_t *bt; 846 int i; 847 struct vmem_hashlist *newhashlist; 848 struct vmem_hashlist *oldhashlist; 849 size_t oldhashsize; 850 851 KASSERT(newhashsize > 0); 852 853 /* Round hash size up to a power of 2. */ 854 newhashsize = 1 << (ilog2(newhashsize) + 1); 855 856 newhashlist = 857 xmalloc(sizeof(struct vmem_hashlist) * newhashsize, flags); 858 if (newhashlist == NULL) { 859 return ENOMEM; 860 } 861 for (i = 0; i < newhashsize; i++) { 862 LIST_INIT(&newhashlist[i]); 863 } 864 865 VMEM_LOCK(vm); 866 /* Decay back to a small hash slowly. */ 867 if (vm->vm_maxbusytag >= 2) { 868 vm->vm_maxbusytag = vm->vm_maxbusytag / 2 - 1; 869 if (vm->vm_nbusytag > vm->vm_maxbusytag) { 870 vm->vm_maxbusytag = vm->vm_nbusytag; 871 } 872 } else { 873 vm->vm_maxbusytag = vm->vm_nbusytag; 874 } 875 oldhashlist = vm->vm_hashlist; 876 oldhashsize = vm->vm_hashsize; 877 vm->vm_hashlist = newhashlist; 878 vm->vm_hashsize = newhashsize; 879 vm->vm_hashmask = newhashsize - 1; 880 if (oldhashlist == NULL) { 881 VMEM_UNLOCK(vm); 882 return 0; 883 } 884 for (i = 0; i < oldhashsize; i++) { 885 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 886 bt_rembusy(vm, bt); /* XXX */ 887 bt_insbusy(vm, bt); 888 } 889 } 890 VMEM_UNLOCK(vm); 891 892 if (oldhashlist != &vm->vm_hash0) { 893 xfree(oldhashlist, 894 sizeof(struct vmem_hashlist) * oldhashsize); 895 } 896 897 return 0; 898 } 899 #endif /* _KERNEL */ 900 901 /* 902 * vmem_fit: check if a bt can satisfy the given restrictions. 903 * 904 * it's a caller's responsibility to ensure the region is big enough 905 * before calling us. 906 */ 907 908 static int 909 vmem_fit(const bt_t *bt, vmem_size_t size, vmem_size_t align, 910 vmem_size_t phase, vmem_size_t nocross, 911 vmem_addr_t minaddr, vmem_addr_t maxaddr, vmem_addr_t *addrp) 912 { 913 vmem_addr_t start; 914 vmem_addr_t end; 915 916 KASSERT(size > 0); 917 KASSERT(bt->bt_size >= size); /* caller's responsibility */ 918 919 /* 920 * XXX assumption: vmem_addr_t and vmem_size_t are 921 * unsigned integer of the same size. 922 */ 923 924 start = bt->bt_start; 925 if (start < minaddr) { 926 start = minaddr; 927 } 928 end = BT_END(bt); 929 if (end > maxaddr) { 930 end = maxaddr; 931 } 932 if (start > end) { 933 return ENOMEM; 934 } 935 936 start = VMEM_ALIGNUP(start - phase, align) + phase; 937 if (start < bt->bt_start) { 938 start += align; 939 } 940 if (VMEM_CROSS_P(start, start + size - 1, nocross)) { 941 KASSERT(align < nocross); 942 start = VMEM_ALIGNUP(start - phase, nocross) + phase; 943 } 944 if (start <= end && end - start >= size - 1) { 945 KASSERT((start & (align - 1)) == phase); 946 KASSERT(!VMEM_CROSS_P(start, start + size - 1, nocross)); 947 KASSERT(minaddr <= start); 948 KASSERT(maxaddr == 0 || start + size - 1 <= maxaddr); 949 KASSERT(bt->bt_start <= start); 950 KASSERT(BT_END(bt) - start >= size - 1); 951 *addrp = start; 952 return 0; 953 } 954 return ENOMEM; 955 } 956 957 /* ---- vmem API */ 958 959 /* 960 * vmem_init: creates a vmem arena. 961 */ 962 963 vmem_t * 964 vmem_init(vmem_t *vm, const char *name, 965 vmem_addr_t base, vmem_size_t size, vmem_size_t quantum, 966 vmem_import_t *importfn, vmem_release_t *releasefn, 967 vmem_t *arg, vmem_size_t qcache_max, vm_flag_t flags, int ipl) 968 { 969 int i; 970 971 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 972 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 973 KASSERT(quantum > 0); 974 KASSERT(powerof2(quantum)); 975 976 /* 977 * If private tags are going to be used, they must 978 * be added to the arena before the first span is 979 * added. 980 */ 981 KASSERT((flags & VM_PRIVTAGS) == 0 || size == 0); 982 983 #if defined(_KERNEL) 984 /* XXX: SMP, we get called early... */ 985 if (!vmem_bootstrapped) { 986 vmem_bootstrap(); 987 } 988 #endif /* defined(_KERNEL) */ 989 990 if (vm == NULL) { 991 vm = xmalloc(sizeof(*vm), flags); 992 } 993 if (vm == NULL) { 994 return NULL; 995 } 996 997 VMEM_CONDVAR_INIT(vm, "vmem"); 998 VMEM_LOCK_INIT(vm, ipl); 999 vm->vm_flags = flags; 1000 vm->vm_nfreetags = 0; 1001 LIST_INIT(&vm->vm_freetags); 1002 strlcpy(vm->vm_name, name, sizeof(vm->vm_name)); 1003 vm->vm_quantum_mask = quantum - 1; 1004 vm->vm_quantum_shift = SIZE2ORDER(quantum); 1005 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 1006 vm->vm_importfn = importfn; 1007 vm->vm_releasefn = releasefn; 1008 vm->vm_arg = arg; 1009 vm->vm_nbusytag = 0; 1010 vm->vm_maxbusytag = 0; 1011 vm->vm_size = 0; 1012 vm->vm_inuse = 0; 1013 #if defined(QCACHE) 1014 qc_init(vm, qcache_max, ipl); 1015 #endif /* defined(QCACHE) */ 1016 1017 TAILQ_INIT(&vm->vm_seglist); 1018 for (i = 0; i < VMEM_MAXORDER; i++) { 1019 LIST_INIT(&vm->vm_freelist[i]); 1020 } 1021 memset(&vm->vm_hash0, 0, sizeof(vm->vm_hash0)); 1022 vm->vm_hashsize = 1; 1023 vm->vm_hashmask = vm->vm_hashsize - 1; 1024 vm->vm_hashlist = &vm->vm_hash0; 1025 1026 if (size != 0) { 1027 if (vmem_add(vm, base, size, flags) != 0) { 1028 vmem_destroy1(vm); 1029 return NULL; 1030 } 1031 } 1032 1033 #if defined(_KERNEL) 1034 if (flags & VM_BOOTSTRAP) { 1035 bt_refill(vm); 1036 } 1037 1038 mutex_enter(&vmem_list_lock); 1039 LIST_INSERT_HEAD(&vmem_list, vm, vm_alllist); 1040 mutex_exit(&vmem_list_lock); 1041 #endif /* defined(_KERNEL) */ 1042 1043 return vm; 1044 } 1045 1046 1047 1048 /* 1049 * vmem_create: create an arena. 1050 * 1051 * => must not be called from interrupt context. 1052 */ 1053 1054 vmem_t * 1055 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 1056 vmem_size_t quantum, vmem_import_t *importfn, vmem_release_t *releasefn, 1057 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags, int ipl) 1058 { 1059 1060 KASSERT((flags & (VM_XIMPORT)) == 0); 1061 1062 return vmem_init(NULL, name, base, size, quantum, 1063 importfn, releasefn, source, qcache_max, flags, ipl); 1064 } 1065 1066 /* 1067 * vmem_xcreate: create an arena takes alternative import func. 1068 * 1069 * => must not be called from interrupt context. 1070 */ 1071 1072 vmem_t * 1073 vmem_xcreate(const char *name, vmem_addr_t base, vmem_size_t size, 1074 vmem_size_t quantum, vmem_ximport_t *importfn, vmem_release_t *releasefn, 1075 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags, int ipl) 1076 { 1077 1078 KASSERT((flags & (VM_XIMPORT)) == 0); 1079 1080 return vmem_init(NULL, name, base, size, quantum, 1081 __FPTRCAST(vmem_import_t *, importfn), releasefn, source, 1082 qcache_max, flags | VM_XIMPORT, ipl); 1083 } 1084 1085 void 1086 vmem_destroy(vmem_t *vm) 1087 { 1088 1089 #if defined(_KERNEL) 1090 mutex_enter(&vmem_list_lock); 1091 LIST_REMOVE(vm, vm_alllist); 1092 mutex_exit(&vmem_list_lock); 1093 #endif /* defined(_KERNEL) */ 1094 1095 vmem_destroy1(vm); 1096 } 1097 1098 vmem_size_t 1099 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 1100 { 1101 1102 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 1103 } 1104 1105 /* 1106 * vmem_alloc: allocate resource from the arena. 1107 */ 1108 1109 int 1110 vmem_alloc(vmem_t *vm, vmem_size_t size, vm_flag_t flags, vmem_addr_t *addrp) 1111 { 1112 const vm_flag_t strat __diagused = flags & VM_FITMASK; 1113 int error; 1114 1115 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 1116 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 1117 1118 KASSERT(size > 0); 1119 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 1120 if ((flags & VM_SLEEP) != 0) { 1121 ASSERT_SLEEPABLE(); 1122 } 1123 1124 #if defined(QCACHE) 1125 if (size <= vm->vm_qcache_max) { 1126 void *p; 1127 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 1128 qcache_t *qc = vm->vm_qcache[qidx - 1]; 1129 1130 p = pool_cache_get(qc->qc_cache, vmf_to_prf(flags)); 1131 if (addrp != NULL) 1132 *addrp = (vmem_addr_t)p; 1133 error = (p == NULL) ? ENOMEM : 0; 1134 goto out; 1135 } 1136 #endif /* defined(QCACHE) */ 1137 1138 error = vmem_xalloc(vm, size, 0, 0, 0, VMEM_ADDR_MIN, VMEM_ADDR_MAX, 1139 flags, addrp); 1140 #if defined(QCACHE) 1141 out: 1142 #endif /* defined(QCACHE) */ 1143 KASSERTMSG(error || addrp == NULL || 1144 (*addrp & vm->vm_quantum_mask) == 0, 1145 "vmem %s mask=0x%jx addr=0x%jx", 1146 vm->vm_name, (uintmax_t)vm->vm_quantum_mask, (uintmax_t)*addrp); 1147 KASSERT(error == 0 || (flags & VM_SLEEP) == 0); 1148 return error; 1149 } 1150 1151 int 1152 vmem_xalloc_addr(vmem_t *vm, const vmem_addr_t addr, const vmem_size_t size, 1153 vm_flag_t flags) 1154 { 1155 vmem_addr_t result; 1156 int error; 1157 1158 KASSERT((addr & vm->vm_quantum_mask) == 0); 1159 KASSERT(size != 0); 1160 1161 flags = (flags & ~VM_INSTANTFIT) | VM_BESTFIT; 1162 1163 error = vmem_xalloc(vm, size, 0, 0, 0, addr, addr + size - 1, 1164 flags, &result); 1165 1166 KASSERT(error || result == addr); 1167 KASSERT(error == 0 || (flags & VM_SLEEP) == 0); 1168 return error; 1169 } 1170 1171 int 1172 vmem_xalloc(vmem_t *vm, const vmem_size_t size0, vmem_size_t align, 1173 const vmem_size_t phase, const vmem_size_t nocross, 1174 const vmem_addr_t minaddr, const vmem_addr_t maxaddr, const vm_flag_t flags, 1175 vmem_addr_t *addrp) 1176 { 1177 struct vmem_freelist *list; 1178 struct vmem_freelist *first; 1179 struct vmem_freelist *end; 1180 bt_t *bt; 1181 bt_t *btnew; 1182 bt_t *btnew2; 1183 const vmem_size_t size = vmem_roundup_size(vm, size0); 1184 vm_flag_t strat = flags & VM_FITMASK; 1185 vmem_addr_t start; 1186 int rc; 1187 1188 KASSERT(size0 > 0); 1189 KASSERT(size > 0); 1190 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 1191 if ((flags & VM_SLEEP) != 0) { 1192 ASSERT_SLEEPABLE(); 1193 } 1194 KASSERT((align & vm->vm_quantum_mask) == 0); 1195 KASSERT((align & (align - 1)) == 0); 1196 KASSERT((phase & vm->vm_quantum_mask) == 0); 1197 KASSERT((nocross & vm->vm_quantum_mask) == 0); 1198 KASSERT((nocross & (nocross - 1)) == 0); 1199 KASSERT(align == 0 || phase < align); 1200 KASSERT(phase == 0 || phase < align); 1201 KASSERT(nocross == 0 || nocross >= size); 1202 KASSERT(minaddr <= maxaddr); 1203 KASSERT(!VMEM_CROSS_P(phase, phase + size - 1, nocross)); 1204 1205 if (align == 0) { 1206 align = vm->vm_quantum_mask + 1; 1207 } 1208 1209 /* 1210 * allocate boundary tags before acquiring the vmem lock. 1211 */ 1212 VMEM_LOCK(vm); 1213 btnew = bt_alloc(vm, flags); 1214 if (btnew == NULL) { 1215 VMEM_UNLOCK(vm); 1216 return ENOMEM; 1217 } 1218 btnew2 = bt_alloc(vm, flags); /* XXX not necessary if no restrictions */ 1219 if (btnew2 == NULL) { 1220 bt_free(vm, btnew); 1221 VMEM_UNLOCK(vm); 1222 return ENOMEM; 1223 } 1224 1225 /* 1226 * choose a free block from which we allocate. 1227 */ 1228 retry_strat: 1229 first = bt_freehead_toalloc(vm, size, strat); 1230 end = &vm->vm_freelist[VMEM_MAXORDER]; 1231 retry: 1232 bt = NULL; 1233 vmem_check(vm); 1234 if (strat == VM_INSTANTFIT) { 1235 /* 1236 * just choose the first block which satisfies our restrictions. 1237 * 1238 * note that we don't need to check the size of the blocks 1239 * because any blocks found on these list should be larger than 1240 * the given size. 1241 */ 1242 for (list = first; list < end; list++) { 1243 bt = LIST_FIRST(list); 1244 if (bt != NULL) { 1245 rc = vmem_fit(bt, size, align, phase, 1246 nocross, minaddr, maxaddr, &start); 1247 if (rc == 0) { 1248 goto gotit; 1249 } 1250 /* 1251 * don't bother to follow the bt_freelist link 1252 * here. the list can be very long and we are 1253 * told to run fast. blocks from the later free 1254 * lists are larger and have better chances to 1255 * satisfy our restrictions. 1256 */ 1257 } 1258 } 1259 } else { /* VM_BESTFIT */ 1260 /* 1261 * we assume that, for space efficiency, it's better to 1262 * allocate from a smaller block. thus we will start searching 1263 * from the lower-order list than VM_INSTANTFIT. 1264 * however, don't bother to find the smallest block in a free 1265 * list because the list can be very long. we can revisit it 1266 * if/when it turns out to be a problem. 1267 * 1268 * note that the 'first' list can contain blocks smaller than 1269 * the requested size. thus we need to check bt_size. 1270 */ 1271 for (list = first; list < end; list++) { 1272 LIST_FOREACH(bt, list, bt_freelist) { 1273 if (bt->bt_size >= size) { 1274 rc = vmem_fit(bt, size, align, phase, 1275 nocross, minaddr, maxaddr, &start); 1276 if (rc == 0) { 1277 goto gotit; 1278 } 1279 } 1280 } 1281 } 1282 } 1283 #if 1 1284 if (strat == VM_INSTANTFIT) { 1285 strat = VM_BESTFIT; 1286 goto retry_strat; 1287 } 1288 #endif 1289 if (align != vm->vm_quantum_mask + 1 || phase != 0 || nocross != 0) { 1290 1291 /* 1292 * XXX should try to import a region large enough to 1293 * satisfy restrictions? 1294 */ 1295 1296 goto fail; 1297 } 1298 /* XXX eeek, minaddr & maxaddr not respected */ 1299 if (vmem_import(vm, size, flags) == 0) { 1300 goto retry; 1301 } 1302 /* XXX */ 1303 1304 if ((flags & VM_SLEEP) != 0) { 1305 vmem_kick_pdaemon(); 1306 VMEM_CONDVAR_WAIT(vm); 1307 goto retry; 1308 } 1309 fail: 1310 bt_free(vm, btnew); 1311 bt_free(vm, btnew2); 1312 VMEM_UNLOCK(vm); 1313 return ENOMEM; 1314 1315 gotit: 1316 KASSERT(bt->bt_type == BT_TYPE_FREE); 1317 KASSERT(bt->bt_size >= size); 1318 bt_remfree(vm, bt); 1319 vmem_check(vm); 1320 if (bt->bt_start != start) { 1321 btnew2->bt_type = BT_TYPE_FREE; 1322 btnew2->bt_start = bt->bt_start; 1323 btnew2->bt_size = start - bt->bt_start; 1324 bt->bt_start = start; 1325 bt->bt_size -= btnew2->bt_size; 1326 bt_insfree(vm, btnew2); 1327 bt_insseg(vm, btnew2, TAILQ_PREV(bt, vmem_seglist, bt_seglist)); 1328 btnew2 = NULL; 1329 vmem_check(vm); 1330 } 1331 KASSERT(bt->bt_start == start); 1332 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 1333 /* split */ 1334 btnew->bt_type = BT_TYPE_BUSY; 1335 btnew->bt_start = bt->bt_start; 1336 btnew->bt_size = size; 1337 bt->bt_start = bt->bt_start + size; 1338 bt->bt_size -= size; 1339 bt_insfree(vm, bt); 1340 bt_insseg(vm, btnew, TAILQ_PREV(bt, vmem_seglist, bt_seglist)); 1341 bt_insbusy(vm, btnew); 1342 vmem_check(vm); 1343 } else { 1344 bt->bt_type = BT_TYPE_BUSY; 1345 bt_insbusy(vm, bt); 1346 vmem_check(vm); 1347 bt_free(vm, btnew); 1348 btnew = bt; 1349 } 1350 if (btnew2 != NULL) { 1351 bt_free(vm, btnew2); 1352 } 1353 KASSERT(btnew->bt_size >= size); 1354 btnew->bt_type = BT_TYPE_BUSY; 1355 if (addrp != NULL) 1356 *addrp = btnew->bt_start; 1357 VMEM_UNLOCK(vm); 1358 KASSERTMSG(addrp == NULL || 1359 (*addrp & vm->vm_quantum_mask) == 0, 1360 "vmem %s mask=0x%jx addr=0x%jx", 1361 vm->vm_name, (uintmax_t)vm->vm_quantum_mask, (uintmax_t)*addrp); 1362 return 0; 1363 } 1364 1365 /* 1366 * vmem_free: free the resource to the arena. 1367 */ 1368 1369 void 1370 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1371 { 1372 1373 KASSERT(size > 0); 1374 KASSERTMSG((addr & vm->vm_quantum_mask) == 0, 1375 "vmem %s mask=0x%jx addr=0x%jx", 1376 vm->vm_name, (uintmax_t)vm->vm_quantum_mask, (uintmax_t)addr); 1377 1378 #if defined(QCACHE) 1379 if (size <= vm->vm_qcache_max) { 1380 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 1381 qcache_t *qc = vm->vm_qcache[qidx - 1]; 1382 1383 pool_cache_put(qc->qc_cache, (void *)addr); 1384 return; 1385 } 1386 #endif /* defined(QCACHE) */ 1387 1388 vmem_xfree(vm, addr, size); 1389 } 1390 1391 void 1392 vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1393 { 1394 bt_t *bt; 1395 1396 KASSERT(size > 0); 1397 KASSERTMSG((addr & vm->vm_quantum_mask) == 0, 1398 "vmem %s mask=0x%jx addr=0x%jx", 1399 vm->vm_name, (uintmax_t)vm->vm_quantum_mask, (uintmax_t)addr); 1400 1401 VMEM_LOCK(vm); 1402 1403 bt = bt_lookupbusy(vm, addr); 1404 KASSERTMSG(bt != NULL, "vmem %s addr 0x%jx size 0x%jx", 1405 vm->vm_name, (uintmax_t)addr, (uintmax_t)size); 1406 KASSERT(bt->bt_start == addr); 1407 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 1408 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 1409 1410 /* vmem_xfree_bt() drops the lock. */ 1411 vmem_xfree_bt(vm, bt); 1412 } 1413 1414 void 1415 vmem_xfreeall(vmem_t *vm) 1416 { 1417 bt_t *bt; 1418 1419 #if defined(QCACHE) 1420 /* This can't be used if the arena has a quantum cache. */ 1421 KASSERT(vm->vm_qcache_max == 0); 1422 #endif /* defined(QCACHE) */ 1423 1424 for (;;) { 1425 VMEM_LOCK(vm); 1426 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1427 if (bt->bt_type == BT_TYPE_BUSY) 1428 break; 1429 } 1430 if (bt != NULL) { 1431 /* vmem_xfree_bt() drops the lock. */ 1432 vmem_xfree_bt(vm, bt); 1433 } else { 1434 VMEM_UNLOCK(vm); 1435 return; 1436 } 1437 } 1438 } 1439 1440 static void 1441 vmem_xfree_bt(vmem_t *vm, bt_t *bt) 1442 { 1443 bt_t *t; 1444 1445 VMEM_ASSERT_LOCKED(vm); 1446 1447 KASSERT(bt->bt_type == BT_TYPE_BUSY); 1448 bt_rembusy(vm, bt); 1449 bt->bt_type = BT_TYPE_FREE; 1450 1451 /* coalesce */ 1452 t = TAILQ_NEXT(bt, bt_seglist); 1453 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1454 KASSERT(BT_END(bt) < t->bt_start); /* YYY */ 1455 bt_remfree(vm, t); 1456 bt_remseg(vm, t); 1457 bt->bt_size += t->bt_size; 1458 bt_free(vm, t); 1459 } 1460 t = TAILQ_PREV(bt, vmem_seglist, bt_seglist); 1461 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1462 KASSERT(BT_END(t) < bt->bt_start); /* YYY */ 1463 bt_remfree(vm, t); 1464 bt_remseg(vm, t); 1465 bt->bt_size += t->bt_size; 1466 bt->bt_start = t->bt_start; 1467 bt_free(vm, t); 1468 } 1469 1470 t = TAILQ_PREV(bt, vmem_seglist, bt_seglist); 1471 KASSERT(t != NULL); 1472 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 1473 if (vm->vm_releasefn != NULL && t->bt_type == BT_TYPE_SPAN && 1474 t->bt_size == bt->bt_size) { 1475 vmem_addr_t spanaddr; 1476 vmem_size_t spansize; 1477 1478 KASSERT(t->bt_start == bt->bt_start); 1479 spanaddr = bt->bt_start; 1480 spansize = bt->bt_size; 1481 bt_remseg(vm, bt); 1482 bt_free(vm, bt); 1483 bt_remseg(vm, t); 1484 bt_free(vm, t); 1485 vm->vm_size -= spansize; 1486 VMEM_CONDVAR_BROADCAST(vm); 1487 /* bt_freetrim() drops the lock. */ 1488 bt_freetrim(vm, BT_MAXFREE); 1489 (*vm->vm_releasefn)(vm->vm_arg, spanaddr, spansize); 1490 } else { 1491 bt_insfree(vm, bt); 1492 VMEM_CONDVAR_BROADCAST(vm); 1493 /* bt_freetrim() drops the lock. */ 1494 bt_freetrim(vm, BT_MAXFREE); 1495 } 1496 } 1497 1498 /* 1499 * vmem_add: 1500 * 1501 * => caller must ensure appropriate spl, 1502 * if the arena can be accessed from interrupt context. 1503 */ 1504 1505 int 1506 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 1507 { 1508 int rv; 1509 1510 VMEM_LOCK(vm); 1511 rv = vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 1512 VMEM_UNLOCK(vm); 1513 1514 return rv; 1515 } 1516 1517 /* 1518 * vmem_size: information about arenas size 1519 * 1520 * => return free/allocated size in arena 1521 */ 1522 vmem_size_t 1523 vmem_size(vmem_t *vm, int typemask) 1524 { 1525 1526 switch (typemask) { 1527 case VMEM_ALLOC: 1528 return vm->vm_inuse; 1529 case VMEM_FREE: 1530 return vm->vm_size - vm->vm_inuse; 1531 case VMEM_FREE|VMEM_ALLOC: 1532 return vm->vm_size; 1533 default: 1534 panic("vmem_size"); 1535 } 1536 } 1537 1538 /* ---- rehash */ 1539 1540 #if defined(_KERNEL) 1541 static struct callout vmem_rehash_ch; 1542 static int vmem_rehash_interval; 1543 static struct workqueue *vmem_rehash_wq; 1544 static struct work vmem_rehash_wk; 1545 1546 static void 1547 vmem_rehash_all(struct work *wk, void *dummy) 1548 { 1549 vmem_t *vm; 1550 1551 KASSERT(wk == &vmem_rehash_wk); 1552 mutex_enter(&vmem_list_lock); 1553 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1554 size_t desired; 1555 size_t current; 1556 1557 desired = atomic_load_relaxed(&vm->vm_maxbusytag); 1558 current = atomic_load_relaxed(&vm->vm_hashsize); 1559 1560 if (desired > VMEM_HASHSIZE_MAX) { 1561 desired = VMEM_HASHSIZE_MAX; 1562 } else if (desired < VMEM_HASHSIZE_MIN) { 1563 desired = VMEM_HASHSIZE_MIN; 1564 } 1565 if (desired > current * 2 || desired * 2 < current) { 1566 vmem_rehash(vm, desired, VM_NOSLEEP); 1567 } 1568 } 1569 mutex_exit(&vmem_list_lock); 1570 1571 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1572 } 1573 1574 static void 1575 vmem_rehash_all_kick(void *dummy) 1576 { 1577 1578 workqueue_enqueue(vmem_rehash_wq, &vmem_rehash_wk, NULL); 1579 } 1580 1581 void 1582 vmem_rehash_start(void) 1583 { 1584 int error; 1585 1586 error = workqueue_create(&vmem_rehash_wq, "vmem_rehash", 1587 vmem_rehash_all, NULL, PRI_VM, IPL_SOFTCLOCK, WQ_MPSAFE); 1588 if (error) { 1589 panic("%s: workqueue_create %d\n", __func__, error); 1590 } 1591 callout_init(&vmem_rehash_ch, CALLOUT_MPSAFE); 1592 callout_setfunc(&vmem_rehash_ch, vmem_rehash_all_kick, NULL); 1593 1594 vmem_rehash_interval = hz * 10; 1595 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1596 } 1597 #endif /* defined(_KERNEL) */ 1598 1599 /* ---- debug */ 1600 1601 #if defined(DDB) || defined(UNITTEST) || defined(VMEM_SANITY) 1602 1603 static void bt_dump(const bt_t *, void (*)(const char *, ...) 1604 __printflike(1, 2)); 1605 1606 static const char * 1607 bt_type_string(int type) 1608 { 1609 static const char * const table[] = { 1610 [BT_TYPE_BUSY] = "busy", 1611 [BT_TYPE_FREE] = "free", 1612 [BT_TYPE_SPAN] = "span", 1613 [BT_TYPE_SPAN_STATIC] = "static span", 1614 }; 1615 1616 if (type >= __arraycount(table)) { 1617 return "BOGUS"; 1618 } 1619 return table[type]; 1620 } 1621 1622 static void 1623 bt_dump(const bt_t *bt, void (*pr)(const char *, ...)) 1624 { 1625 1626 (*pr)("\t%p: %" PRIu64 ", %" PRIu64 ", %d(%s)\n", 1627 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 1628 bt->bt_type, bt_type_string(bt->bt_type)); 1629 } 1630 1631 static void 1632 vmem_dump(const vmem_t *vm , void (*pr)(const char *, ...) __printflike(1, 2)) 1633 { 1634 const bt_t *bt; 1635 int i; 1636 1637 (*pr)("vmem %p '%s'\n", vm, vm->vm_name); 1638 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1639 bt_dump(bt, pr); 1640 } 1641 1642 for (i = 0; i < VMEM_MAXORDER; i++) { 1643 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 1644 1645 if (LIST_EMPTY(fl)) { 1646 continue; 1647 } 1648 1649 (*pr)("freelist[%d]\n", i); 1650 LIST_FOREACH(bt, fl, bt_freelist) { 1651 bt_dump(bt, pr); 1652 } 1653 } 1654 } 1655 1656 #endif /* defined(DDB) || defined(UNITTEST) || defined(VMEM_SANITY) */ 1657 1658 #if defined(DDB) 1659 static bt_t * 1660 vmem_whatis_lookup(vmem_t *vm, uintptr_t addr) 1661 { 1662 bt_t *bt; 1663 1664 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1665 if (BT_ISSPAN_P(bt)) { 1666 continue; 1667 } 1668 if (bt->bt_start <= addr && addr <= BT_END(bt)) { 1669 return bt; 1670 } 1671 } 1672 1673 return NULL; 1674 } 1675 1676 void 1677 vmem_whatis(uintptr_t addr, void (*pr)(const char *, ...)) 1678 { 1679 vmem_t *vm; 1680 1681 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1682 bt_t *bt; 1683 1684 bt = vmem_whatis_lookup(vm, addr); 1685 if (bt == NULL) { 1686 continue; 1687 } 1688 (*pr)("%p is %p+%zu in VMEM '%s' (%s)\n", 1689 (void *)addr, (void *)bt->bt_start, 1690 (size_t)(addr - bt->bt_start), vm->vm_name, 1691 (bt->bt_type == BT_TYPE_BUSY) ? "allocated" : "free"); 1692 } 1693 } 1694 1695 void 1696 vmem_printall(const char *modif, void (*pr)(const char *, ...)) 1697 { 1698 const vmem_t *vm; 1699 1700 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1701 vmem_dump(vm, pr); 1702 } 1703 } 1704 1705 void 1706 vmem_print(uintptr_t addr, const char *modif, void (*pr)(const char *, ...)) 1707 { 1708 const vmem_t *vm = (const void *)addr; 1709 1710 vmem_dump(vm, pr); 1711 } 1712 #endif /* defined(DDB) */ 1713 1714 #if defined(_KERNEL) 1715 #define vmem_printf printf 1716 #else 1717 #include <stdio.h> 1718 #include <stdarg.h> 1719 1720 static void 1721 vmem_printf(const char *fmt, ...) 1722 { 1723 va_list ap; 1724 va_start(ap, fmt); 1725 vprintf(fmt, ap); 1726 va_end(ap); 1727 } 1728 #endif 1729 1730 #if defined(VMEM_SANITY) 1731 1732 static bool 1733 vmem_check_sanity(vmem_t *vm) 1734 { 1735 const bt_t *bt, *bt2; 1736 1737 KASSERT(vm != NULL); 1738 1739 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1740 if (bt->bt_start > BT_END(bt)) { 1741 printf("corrupted tag\n"); 1742 bt_dump(bt, vmem_printf); 1743 return false; 1744 } 1745 } 1746 TAILQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1747 TAILQ_FOREACH(bt2, &vm->vm_seglist, bt_seglist) { 1748 if (bt == bt2) { 1749 continue; 1750 } 1751 if (BT_ISSPAN_P(bt) != BT_ISSPAN_P(bt2)) { 1752 continue; 1753 } 1754 if (bt->bt_start <= BT_END(bt2) && 1755 bt2->bt_start <= BT_END(bt)) { 1756 printf("overwrapped tags\n"); 1757 bt_dump(bt, vmem_printf); 1758 bt_dump(bt2, vmem_printf); 1759 return false; 1760 } 1761 } 1762 } 1763 1764 return true; 1765 } 1766 1767 static void 1768 vmem_check(vmem_t *vm) 1769 { 1770 1771 if (!vmem_check_sanity(vm)) { 1772 panic("insanity vmem %p", vm); 1773 } 1774 } 1775 1776 #endif /* defined(VMEM_SANITY) */ 1777 1778 #if defined(UNITTEST) 1779 int 1780 main(void) 1781 { 1782 int rc; 1783 vmem_t *vm; 1784 vmem_addr_t p; 1785 struct reg { 1786 vmem_addr_t p; 1787 vmem_size_t sz; 1788 bool x; 1789 } *reg = NULL; 1790 int nreg = 0; 1791 int nalloc = 0; 1792 int nfree = 0; 1793 vmem_size_t total = 0; 1794 #if 1 1795 vm_flag_t strat = VM_INSTANTFIT; 1796 #else 1797 vm_flag_t strat = VM_BESTFIT; 1798 #endif 1799 1800 vm = vmem_create("test", 0, 0, 1, NULL, NULL, NULL, 0, VM_SLEEP, 1801 #ifdef _KERNEL 1802 IPL_NONE 1803 #else 1804 0 1805 #endif 1806 ); 1807 if (vm == NULL) { 1808 printf("vmem_create\n"); 1809 exit(EXIT_FAILURE); 1810 } 1811 vmem_dump(vm, vmem_printf); 1812 1813 rc = vmem_add(vm, 0, 50, VM_SLEEP); 1814 assert(rc == 0); 1815 rc = vmem_add(vm, 100, 200, VM_SLEEP); 1816 assert(rc == 0); 1817 rc = vmem_add(vm, 2000, 1, VM_SLEEP); 1818 assert(rc == 0); 1819 rc = vmem_add(vm, 40000, 65536, VM_SLEEP); 1820 assert(rc == 0); 1821 rc = vmem_add(vm, 10000, 10000, VM_SLEEP); 1822 assert(rc == 0); 1823 rc = vmem_add(vm, 500, 1000, VM_SLEEP); 1824 assert(rc == 0); 1825 rc = vmem_add(vm, 0xffffff00, 0x100, VM_SLEEP); 1826 assert(rc == 0); 1827 rc = vmem_xalloc(vm, 0x101, 0, 0, 0, 1828 0xffffff00, 0xffffffff, strat|VM_SLEEP, &p); 1829 assert(rc != 0); 1830 rc = vmem_xalloc(vm, 50, 0, 0, 0, 0, 49, strat|VM_SLEEP, &p); 1831 assert(rc == 0 && p == 0); 1832 vmem_xfree(vm, p, 50); 1833 rc = vmem_xalloc(vm, 25, 0, 0, 0, 0, 24, strat|VM_SLEEP, &p); 1834 assert(rc == 0 && p == 0); 1835 rc = vmem_xalloc(vm, 0x100, 0, 0, 0, 1836 0xffffff01, 0xffffffff, strat|VM_SLEEP, &p); 1837 assert(rc != 0); 1838 rc = vmem_xalloc(vm, 0x100, 0, 0, 0, 1839 0xffffff00, 0xfffffffe, strat|VM_SLEEP, &p); 1840 assert(rc != 0); 1841 rc = vmem_xalloc(vm, 0x100, 0, 0, 0, 1842 0xffffff00, 0xffffffff, strat|VM_SLEEP, &p); 1843 assert(rc == 0); 1844 vmem_dump(vm, vmem_printf); 1845 for (;;) { 1846 struct reg *r; 1847 int t = rand() % 100; 1848 1849 if (t > 45) { 1850 /* alloc */ 1851 vmem_size_t sz = rand() % 500 + 1; 1852 bool x; 1853 vmem_size_t align, phase, nocross; 1854 vmem_addr_t minaddr, maxaddr; 1855 1856 if (t > 70) { 1857 x = true; 1858 /* XXX */ 1859 align = 1 << (rand() % 15); 1860 phase = rand() % 65536; 1861 nocross = 1 << (rand() % 15); 1862 if (align <= phase) { 1863 phase = 0; 1864 } 1865 if (VMEM_CROSS_P(phase, phase + sz - 1, 1866 nocross)) { 1867 nocross = 0; 1868 } 1869 do { 1870 minaddr = rand() % 50000; 1871 maxaddr = rand() % 70000; 1872 } while (minaddr > maxaddr); 1873 printf("=== xalloc %" PRIu64 1874 " align=%" PRIu64 ", phase=%" PRIu64 1875 ", nocross=%" PRIu64 ", min=%" PRIu64 1876 ", max=%" PRIu64 "\n", 1877 (uint64_t)sz, 1878 (uint64_t)align, 1879 (uint64_t)phase, 1880 (uint64_t)nocross, 1881 (uint64_t)minaddr, 1882 (uint64_t)maxaddr); 1883 rc = vmem_xalloc(vm, sz, align, phase, nocross, 1884 minaddr, maxaddr, strat|VM_SLEEP, &p); 1885 } else { 1886 x = false; 1887 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 1888 rc = vmem_alloc(vm, sz, strat|VM_SLEEP, &p); 1889 } 1890 printf("-> %" PRIu64 "\n", (uint64_t)p); 1891 vmem_dump(vm, vmem_printf); 1892 if (rc != 0) { 1893 if (x) { 1894 continue; 1895 } 1896 break; 1897 } 1898 nreg++; 1899 reg = realloc(reg, sizeof(*reg) * nreg); 1900 r = ®[nreg - 1]; 1901 r->p = p; 1902 r->sz = sz; 1903 r->x = x; 1904 total += sz; 1905 nalloc++; 1906 } else if (nreg != 0) { 1907 /* free */ 1908 r = ®[rand() % nreg]; 1909 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1910 (uint64_t)r->p, (uint64_t)r->sz); 1911 if (r->x) { 1912 vmem_xfree(vm, r->p, r->sz); 1913 } else { 1914 vmem_free(vm, r->p, r->sz); 1915 } 1916 total -= r->sz; 1917 vmem_dump(vm, vmem_printf); 1918 *r = reg[nreg - 1]; 1919 nreg--; 1920 nfree++; 1921 } 1922 printf("total=%" PRIu64 "\n", (uint64_t)total); 1923 } 1924 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1925 (uint64_t)total, nalloc, nfree); 1926 exit(EXIT_SUCCESS); 1927 } 1928 #endif /* defined(UNITTEST) */ 1929