1 /* $NetBSD: subr_vmem.c,v 1.52 2008/12/15 10:26:10 ad Exp $ */ 2 3 /*- 4 * Copyright (c)2006 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 * todo: 36 * - decide how to import segments for vmem_xalloc. 37 * - don't rely on malloc(9). 38 */ 39 40 #include <sys/cdefs.h> 41 __KERNEL_RCSID(0, "$NetBSD: subr_vmem.c,v 1.52 2008/12/15 10:26:10 ad Exp $"); 42 43 #if defined(_KERNEL) 44 #include "opt_ddb.h" 45 #define QCACHE 46 #endif /* defined(_KERNEL) */ 47 48 #include <sys/param.h> 49 #include <sys/hash.h> 50 #include <sys/queue.h> 51 52 #if defined(_KERNEL) 53 #include <sys/systm.h> 54 #include <sys/kernel.h> /* hz */ 55 #include <sys/callout.h> 56 #include <sys/malloc.h> 57 #include <sys/once.h> 58 #include <sys/pool.h> 59 #include <sys/vmem.h> 60 #include <sys/workqueue.h> 61 #else /* defined(_KERNEL) */ 62 #include "../sys/vmem.h" 63 #endif /* defined(_KERNEL) */ 64 65 #if defined(_KERNEL) 66 #define LOCK_DECL(name) \ 67 kmutex_t name; char lockpad[COHERENCY_UNIT - sizeof(kmutex_t)] 68 #else /* defined(_KERNEL) */ 69 #include <errno.h> 70 #include <assert.h> 71 #include <stdlib.h> 72 73 #define KASSERT(a) assert(a) 74 #define LOCK_DECL(name) /* nothing */ 75 #define mutex_init(a, b, c) /* nothing */ 76 #define mutex_destroy(a) /* nothing */ 77 #define mutex_enter(a) /* nothing */ 78 #define mutex_exit(a) /* nothing */ 79 #define mutex_owned(a) /* nothing */ 80 #define ASSERT_SLEEPABLE() /* nothing */ 81 #define IPL_VM 0 82 #endif /* defined(_KERNEL) */ 83 84 struct vmem; 85 struct vmem_btag; 86 87 #if defined(VMEM_DEBUG) 88 void vmem_dump(const vmem_t *); 89 #endif /* defined(VMEM_DEBUG) */ 90 91 #define VMEM_MAXORDER (sizeof(vmem_size_t) * CHAR_BIT) 92 93 #define VMEM_HASHSIZE_MIN 1 /* XXX */ 94 #define VMEM_HASHSIZE_MAX 8192 /* XXX */ 95 #define VMEM_HASHSIZE_INIT VMEM_HASHSIZE_MIN 96 97 #define VM_FITMASK (VM_BESTFIT | VM_INSTANTFIT) 98 99 CIRCLEQ_HEAD(vmem_seglist, vmem_btag); 100 LIST_HEAD(vmem_freelist, vmem_btag); 101 LIST_HEAD(vmem_hashlist, vmem_btag); 102 103 #if defined(QCACHE) 104 #define VMEM_QCACHE_IDX_MAX 32 105 106 #define QC_NAME_MAX 16 107 108 struct qcache { 109 pool_cache_t qc_cache; 110 vmem_t *qc_vmem; 111 char qc_name[QC_NAME_MAX]; 112 }; 113 typedef struct qcache qcache_t; 114 #define QC_POOL_TO_QCACHE(pool) ((qcache_t *)(pool->pr_qcache)) 115 #endif /* defined(QCACHE) */ 116 117 /* vmem arena */ 118 struct vmem { 119 LOCK_DECL(vm_lock); 120 vmem_addr_t (*vm_allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, 121 vm_flag_t); 122 void (*vm_freefn)(vmem_t *, vmem_addr_t, vmem_size_t); 123 vmem_t *vm_source; 124 struct vmem_seglist vm_seglist; 125 struct vmem_freelist vm_freelist[VMEM_MAXORDER]; 126 size_t vm_hashsize; 127 size_t vm_nbusytag; 128 struct vmem_hashlist *vm_hashlist; 129 size_t vm_quantum_mask; 130 int vm_quantum_shift; 131 const char *vm_name; 132 LIST_ENTRY(vmem) vm_alllist; 133 134 #if defined(QCACHE) 135 /* quantum cache */ 136 size_t vm_qcache_max; 137 struct pool_allocator vm_qcache_allocator; 138 qcache_t vm_qcache_store[VMEM_QCACHE_IDX_MAX]; 139 qcache_t *vm_qcache[VMEM_QCACHE_IDX_MAX]; 140 #endif /* defined(QCACHE) */ 141 }; 142 143 #define VMEM_LOCK(vm) mutex_enter(&vm->vm_lock) 144 #define VMEM_TRYLOCK(vm) mutex_tryenter(&vm->vm_lock) 145 #define VMEM_UNLOCK(vm) mutex_exit(&vm->vm_lock) 146 #define VMEM_LOCK_INIT(vm, ipl) mutex_init(&vm->vm_lock, MUTEX_DEFAULT, ipl) 147 #define VMEM_LOCK_DESTROY(vm) mutex_destroy(&vm->vm_lock) 148 #define VMEM_ASSERT_LOCKED(vm) KASSERT(mutex_owned(&vm->vm_lock)) 149 150 /* boundary tag */ 151 struct vmem_btag { 152 CIRCLEQ_ENTRY(vmem_btag) bt_seglist; 153 union { 154 LIST_ENTRY(vmem_btag) u_freelist; /* BT_TYPE_FREE */ 155 LIST_ENTRY(vmem_btag) u_hashlist; /* BT_TYPE_BUSY */ 156 } bt_u; 157 #define bt_hashlist bt_u.u_hashlist 158 #define bt_freelist bt_u.u_freelist 159 vmem_addr_t bt_start; 160 vmem_size_t bt_size; 161 int bt_type; 162 }; 163 164 #define BT_TYPE_SPAN 1 165 #define BT_TYPE_SPAN_STATIC 2 166 #define BT_TYPE_FREE 3 167 #define BT_TYPE_BUSY 4 168 #define BT_ISSPAN_P(bt) ((bt)->bt_type <= BT_TYPE_SPAN_STATIC) 169 170 #define BT_END(bt) ((bt)->bt_start + (bt)->bt_size) 171 172 typedef struct vmem_btag bt_t; 173 174 /* ---- misc */ 175 176 #define VMEM_ALIGNUP(addr, align) \ 177 (-(-(addr) & -(align))) 178 #define VMEM_CROSS_P(addr1, addr2, boundary) \ 179 ((((addr1) ^ (addr2)) & -(boundary)) != 0) 180 181 #define ORDER2SIZE(order) ((vmem_size_t)1 << (order)) 182 183 static int 184 calc_order(vmem_size_t size) 185 { 186 vmem_size_t target; 187 int i; 188 189 KASSERT(size != 0); 190 191 i = 0; 192 target = size >> 1; 193 while (ORDER2SIZE(i) <= target) { 194 i++; 195 } 196 197 KASSERT(ORDER2SIZE(i) <= size); 198 KASSERT(size < ORDER2SIZE(i + 1) || ORDER2SIZE(i + 1) < ORDER2SIZE(i)); 199 200 return i; 201 } 202 203 #if defined(_KERNEL) 204 static MALLOC_DEFINE(M_VMEM, "vmem", "vmem"); 205 #endif /* defined(_KERNEL) */ 206 207 static void * 208 xmalloc(size_t sz, vm_flag_t flags) 209 { 210 211 #if defined(_KERNEL) 212 return malloc(sz, M_VMEM, 213 M_CANFAIL | ((flags & VM_SLEEP) ? M_WAITOK : M_NOWAIT)); 214 #else /* defined(_KERNEL) */ 215 return malloc(sz); 216 #endif /* defined(_KERNEL) */ 217 } 218 219 static void 220 xfree(void *p) 221 { 222 223 #if defined(_KERNEL) 224 return free(p, M_VMEM); 225 #else /* defined(_KERNEL) */ 226 return free(p); 227 #endif /* defined(_KERNEL) */ 228 } 229 230 /* ---- boundary tag */ 231 232 #if defined(_KERNEL) 233 static struct pool_cache bt_cache; 234 #endif /* defined(_KERNEL) */ 235 236 static bt_t * 237 bt_alloc(vmem_t *vm, vm_flag_t flags) 238 { 239 bt_t *bt; 240 241 #if defined(_KERNEL) 242 bt = pool_cache_get(&bt_cache, 243 (flags & VM_SLEEP) != 0 ? PR_WAITOK : PR_NOWAIT); 244 #else /* defined(_KERNEL) */ 245 bt = malloc(sizeof *bt); 246 #endif /* defined(_KERNEL) */ 247 248 return bt; 249 } 250 251 static void 252 bt_free(vmem_t *vm, bt_t *bt) 253 { 254 255 #if defined(_KERNEL) 256 pool_cache_put(&bt_cache, bt); 257 #else /* defined(_KERNEL) */ 258 free(bt); 259 #endif /* defined(_KERNEL) */ 260 } 261 262 /* 263 * freelist[0] ... [1, 1] 264 * freelist[1] ... [2, 3] 265 * freelist[2] ... [4, 7] 266 * freelist[3] ... [8, 15] 267 * : 268 * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1] 269 * : 270 */ 271 272 static struct vmem_freelist * 273 bt_freehead_tofree(vmem_t *vm, vmem_size_t size) 274 { 275 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 276 int idx; 277 278 KASSERT((size & vm->vm_quantum_mask) == 0); 279 KASSERT(size != 0); 280 281 idx = calc_order(qsize); 282 KASSERT(idx >= 0); 283 KASSERT(idx < VMEM_MAXORDER); 284 285 return &vm->vm_freelist[idx]; 286 } 287 288 static struct vmem_freelist * 289 bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, vm_flag_t strat) 290 { 291 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 292 int idx; 293 294 KASSERT((size & vm->vm_quantum_mask) == 0); 295 KASSERT(size != 0); 296 297 idx = calc_order(qsize); 298 if (strat == VM_INSTANTFIT && ORDER2SIZE(idx) != qsize) { 299 idx++; 300 /* check too large request? */ 301 } 302 KASSERT(idx >= 0); 303 KASSERT(idx < VMEM_MAXORDER); 304 305 return &vm->vm_freelist[idx]; 306 } 307 308 /* ---- boundary tag hash */ 309 310 static struct vmem_hashlist * 311 bt_hashhead(vmem_t *vm, vmem_addr_t addr) 312 { 313 struct vmem_hashlist *list; 314 unsigned int hash; 315 316 hash = hash32_buf(&addr, sizeof(addr), HASH32_BUF_INIT); 317 list = &vm->vm_hashlist[hash % vm->vm_hashsize]; 318 319 return list; 320 } 321 322 static bt_t * 323 bt_lookupbusy(vmem_t *vm, vmem_addr_t addr) 324 { 325 struct vmem_hashlist *list; 326 bt_t *bt; 327 328 list = bt_hashhead(vm, addr); 329 LIST_FOREACH(bt, list, bt_hashlist) { 330 if (bt->bt_start == addr) { 331 break; 332 } 333 } 334 335 return bt; 336 } 337 338 static void 339 bt_rembusy(vmem_t *vm, bt_t *bt) 340 { 341 342 KASSERT(vm->vm_nbusytag > 0); 343 vm->vm_nbusytag--; 344 LIST_REMOVE(bt, bt_hashlist); 345 } 346 347 static void 348 bt_insbusy(vmem_t *vm, bt_t *bt) 349 { 350 struct vmem_hashlist *list; 351 352 KASSERT(bt->bt_type == BT_TYPE_BUSY); 353 354 list = bt_hashhead(vm, bt->bt_start); 355 LIST_INSERT_HEAD(list, bt, bt_hashlist); 356 vm->vm_nbusytag++; 357 } 358 359 /* ---- boundary tag list */ 360 361 static void 362 bt_remseg(vmem_t *vm, bt_t *bt) 363 { 364 365 CIRCLEQ_REMOVE(&vm->vm_seglist, bt, bt_seglist); 366 } 367 368 static void 369 bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev) 370 { 371 372 CIRCLEQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist); 373 } 374 375 static void 376 bt_insseg_tail(vmem_t *vm, bt_t *bt) 377 { 378 379 CIRCLEQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist); 380 } 381 382 static void 383 bt_remfree(vmem_t *vm, bt_t *bt) 384 { 385 386 KASSERT(bt->bt_type == BT_TYPE_FREE); 387 388 LIST_REMOVE(bt, bt_freelist); 389 } 390 391 static void 392 bt_insfree(vmem_t *vm, bt_t *bt) 393 { 394 struct vmem_freelist *list; 395 396 list = bt_freehead_tofree(vm, bt->bt_size); 397 LIST_INSERT_HEAD(list, bt, bt_freelist); 398 } 399 400 /* ---- vmem internal functions */ 401 402 #if defined(_KERNEL) 403 static kmutex_t vmem_list_lock; 404 static LIST_HEAD(, vmem) vmem_list = LIST_HEAD_INITIALIZER(vmem_list); 405 #endif /* defined(_KERNEL) */ 406 407 #if defined(QCACHE) 408 static inline vm_flag_t 409 prf_to_vmf(int prflags) 410 { 411 vm_flag_t vmflags; 412 413 KASSERT((prflags & ~(PR_LIMITFAIL | PR_WAITOK | PR_NOWAIT)) == 0); 414 if ((prflags & PR_WAITOK) != 0) { 415 vmflags = VM_SLEEP; 416 } else { 417 vmflags = VM_NOSLEEP; 418 } 419 return vmflags; 420 } 421 422 static inline int 423 vmf_to_prf(vm_flag_t vmflags) 424 { 425 int prflags; 426 427 if ((vmflags & VM_SLEEP) != 0) { 428 prflags = PR_WAITOK; 429 } else { 430 prflags = PR_NOWAIT; 431 } 432 return prflags; 433 } 434 435 static size_t 436 qc_poolpage_size(size_t qcache_max) 437 { 438 int i; 439 440 for (i = 0; ORDER2SIZE(i) <= qcache_max * 3; i++) { 441 /* nothing */ 442 } 443 return ORDER2SIZE(i); 444 } 445 446 static void * 447 qc_poolpage_alloc(struct pool *pool, int prflags) 448 { 449 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 450 vmem_t *vm = qc->qc_vmem; 451 452 return (void *)vmem_alloc(vm, pool->pr_alloc->pa_pagesz, 453 prf_to_vmf(prflags) | VM_INSTANTFIT); 454 } 455 456 static void 457 qc_poolpage_free(struct pool *pool, void *addr) 458 { 459 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 460 vmem_t *vm = qc->qc_vmem; 461 462 vmem_free(vm, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz); 463 } 464 465 static void 466 qc_init(vmem_t *vm, size_t qcache_max, int ipl) 467 { 468 qcache_t *prevqc; 469 struct pool_allocator *pa; 470 int qcache_idx_max; 471 int i; 472 473 KASSERT((qcache_max & vm->vm_quantum_mask) == 0); 474 if (qcache_max > (VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift)) { 475 qcache_max = VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift; 476 } 477 vm->vm_qcache_max = qcache_max; 478 pa = &vm->vm_qcache_allocator; 479 memset(pa, 0, sizeof(*pa)); 480 pa->pa_alloc = qc_poolpage_alloc; 481 pa->pa_free = qc_poolpage_free; 482 pa->pa_pagesz = qc_poolpage_size(qcache_max); 483 484 qcache_idx_max = qcache_max >> vm->vm_quantum_shift; 485 prevqc = NULL; 486 for (i = qcache_idx_max; i > 0; i--) { 487 qcache_t *qc = &vm->vm_qcache_store[i - 1]; 488 size_t size = i << vm->vm_quantum_shift; 489 490 qc->qc_vmem = vm; 491 snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%zu", 492 vm->vm_name, size); 493 qc->qc_cache = pool_cache_init(size, 494 ORDER2SIZE(vm->vm_quantum_shift), 0, 495 PR_NOALIGN | PR_NOTOUCH /* XXX */, 496 qc->qc_name, pa, ipl, NULL, NULL, NULL); 497 KASSERT(qc->qc_cache != NULL); /* XXX */ 498 if (prevqc != NULL && 499 qc->qc_cache->pc_pool.pr_itemsperpage == 500 prevqc->qc_cache->pc_pool.pr_itemsperpage) { 501 pool_cache_destroy(qc->qc_cache); 502 vm->vm_qcache[i - 1] = prevqc; 503 continue; 504 } 505 qc->qc_cache->pc_pool.pr_qcache = qc; 506 vm->vm_qcache[i - 1] = qc; 507 prevqc = qc; 508 } 509 } 510 511 static void 512 qc_destroy(vmem_t *vm) 513 { 514 const qcache_t *prevqc; 515 int i; 516 int qcache_idx_max; 517 518 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 519 prevqc = NULL; 520 for (i = 0; i < qcache_idx_max; i++) { 521 qcache_t *qc = vm->vm_qcache[i]; 522 523 if (prevqc == qc) { 524 continue; 525 } 526 pool_cache_destroy(qc->qc_cache); 527 prevqc = qc; 528 } 529 } 530 531 static bool 532 qc_reap(vmem_t *vm) 533 { 534 const qcache_t *prevqc; 535 int i; 536 int qcache_idx_max; 537 bool didsomething = false; 538 539 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 540 prevqc = NULL; 541 for (i = 0; i < qcache_idx_max; i++) { 542 qcache_t *qc = vm->vm_qcache[i]; 543 544 if (prevqc == qc) { 545 continue; 546 } 547 if (pool_cache_reclaim(qc->qc_cache) != 0) { 548 didsomething = true; 549 } 550 prevqc = qc; 551 } 552 553 return didsomething; 554 } 555 #endif /* defined(QCACHE) */ 556 557 #if defined(_KERNEL) 558 static int 559 vmem_init(void) 560 { 561 562 mutex_init(&vmem_list_lock, MUTEX_DEFAULT, IPL_NONE); 563 pool_cache_bootstrap(&bt_cache, sizeof(bt_t), 0, 0, 0, "vmembt", 564 NULL, IPL_VM, NULL, NULL, NULL); 565 return 0; 566 } 567 #endif /* defined(_KERNEL) */ 568 569 static vmem_addr_t 570 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 571 int spanbttype) 572 { 573 bt_t *btspan; 574 bt_t *btfree; 575 576 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 577 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 578 KASSERT(spanbttype == BT_TYPE_SPAN || spanbttype == BT_TYPE_SPAN_STATIC); 579 580 btspan = bt_alloc(vm, flags); 581 if (btspan == NULL) { 582 return VMEM_ADDR_NULL; 583 } 584 btfree = bt_alloc(vm, flags); 585 if (btfree == NULL) { 586 bt_free(vm, btspan); 587 return VMEM_ADDR_NULL; 588 } 589 590 btspan->bt_type = spanbttype; 591 btspan->bt_start = addr; 592 btspan->bt_size = size; 593 594 btfree->bt_type = BT_TYPE_FREE; 595 btfree->bt_start = addr; 596 btfree->bt_size = size; 597 598 VMEM_LOCK(vm); 599 bt_insseg_tail(vm, btspan); 600 bt_insseg(vm, btfree, btspan); 601 bt_insfree(vm, btfree); 602 VMEM_UNLOCK(vm); 603 604 return addr; 605 } 606 607 static void 608 vmem_destroy1(vmem_t *vm) 609 { 610 611 #if defined(QCACHE) 612 qc_destroy(vm); 613 #endif /* defined(QCACHE) */ 614 if (vm->vm_hashlist != NULL) { 615 int i; 616 617 for (i = 0; i < vm->vm_hashsize; i++) { 618 bt_t *bt; 619 620 while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) { 621 KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC); 622 bt_free(vm, bt); 623 } 624 } 625 xfree(vm->vm_hashlist); 626 } 627 VMEM_LOCK_DESTROY(vm); 628 xfree(vm); 629 } 630 631 static int 632 vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 633 { 634 vmem_addr_t addr; 635 636 if (vm->vm_allocfn == NULL) { 637 return EINVAL; 638 } 639 640 addr = (*vm->vm_allocfn)(vm->vm_source, size, &size, flags); 641 if (addr == VMEM_ADDR_NULL) { 642 return ENOMEM; 643 } 644 645 if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) == VMEM_ADDR_NULL) { 646 (*vm->vm_freefn)(vm->vm_source, addr, size); 647 return ENOMEM; 648 } 649 650 return 0; 651 } 652 653 static int 654 vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags) 655 { 656 bt_t *bt; 657 int i; 658 struct vmem_hashlist *newhashlist; 659 struct vmem_hashlist *oldhashlist; 660 size_t oldhashsize; 661 662 KASSERT(newhashsize > 0); 663 664 newhashlist = 665 xmalloc(sizeof(struct vmem_hashlist *) * newhashsize, flags); 666 if (newhashlist == NULL) { 667 return ENOMEM; 668 } 669 for (i = 0; i < newhashsize; i++) { 670 LIST_INIT(&newhashlist[i]); 671 } 672 673 if (!VMEM_TRYLOCK(vm)) { 674 xfree(newhashlist); 675 return EBUSY; 676 } 677 oldhashlist = vm->vm_hashlist; 678 oldhashsize = vm->vm_hashsize; 679 vm->vm_hashlist = newhashlist; 680 vm->vm_hashsize = newhashsize; 681 if (oldhashlist == NULL) { 682 VMEM_UNLOCK(vm); 683 return 0; 684 } 685 for (i = 0; i < oldhashsize; i++) { 686 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 687 bt_rembusy(vm, bt); /* XXX */ 688 bt_insbusy(vm, bt); 689 } 690 } 691 VMEM_UNLOCK(vm); 692 693 xfree(oldhashlist); 694 695 return 0; 696 } 697 698 /* 699 * vmem_fit: check if a bt can satisfy the given restrictions. 700 */ 701 702 static vmem_addr_t 703 vmem_fit(const bt_t *bt, vmem_size_t size, vmem_size_t align, vmem_size_t phase, 704 vmem_size_t nocross, vmem_addr_t minaddr, vmem_addr_t maxaddr) 705 { 706 vmem_addr_t start; 707 vmem_addr_t end; 708 709 KASSERT(bt->bt_size >= size); 710 711 /* 712 * XXX assumption: vmem_addr_t and vmem_size_t are 713 * unsigned integer of the same size. 714 */ 715 716 start = bt->bt_start; 717 if (start < minaddr) { 718 start = minaddr; 719 } 720 end = BT_END(bt); 721 if (end > maxaddr - 1) { 722 end = maxaddr - 1; 723 } 724 if (start >= end) { 725 return VMEM_ADDR_NULL; 726 } 727 728 start = VMEM_ALIGNUP(start - phase, align) + phase; 729 if (start < bt->bt_start) { 730 start += align; 731 } 732 if (VMEM_CROSS_P(start, start + size - 1, nocross)) { 733 KASSERT(align < nocross); 734 start = VMEM_ALIGNUP(start - phase, nocross) + phase; 735 } 736 if (start < end && end - start >= size) { 737 KASSERT((start & (align - 1)) == phase); 738 KASSERT(!VMEM_CROSS_P(start, start + size - 1, nocross)); 739 KASSERT(minaddr <= start); 740 KASSERT(maxaddr == 0 || start + size <= maxaddr); 741 KASSERT(bt->bt_start <= start); 742 KASSERT(start + size <= BT_END(bt)); 743 return start; 744 } 745 return VMEM_ADDR_NULL; 746 } 747 748 #if !defined(VMEM_DEBUG) 749 #define vmem_check_sanity(vm) true 750 #else 751 752 static bool 753 vmem_check_spanoverlap(const char *func, const vmem_t *vm, 754 const bt_t *bt, const bt_t *bt2) 755 { 756 switch (bt->bt_type) { 757 case BT_TYPE_BUSY: 758 case BT_TYPE_FREE: 759 if (BT_ISSPAN_P(bt2)) 760 return true; 761 break; 762 case BT_TYPE_SPAN: 763 case BT_TYPE_SPAN_STATIC: 764 if (bt2->bt_type == BT_TYPE_BUSY 765 || bt2->bt_type == BT_TYPE_FREE) 766 return true; 767 break; 768 } 769 770 if (bt->bt_start > bt2->bt_start) { 771 if (bt->bt_start >= BT_END(bt2)) 772 return true; 773 774 printf("%s: overlapping VMEM '%s' span 0x%" 775 PRIx64" - 0x%"PRIx64" %s\n", 776 func, vm->vm_name, 777 (uint64_t)bt->bt_start, 778 (uint64_t)BT_END(bt), 779 (bt->bt_type == BT_TYPE_BUSY) ? 780 "allocated" : 781 (bt->bt_type == BT_TYPE_FREE) ? 782 "free" : 783 (bt->bt_type == BT_TYPE_SPAN) ? 784 "span" : "static span"); 785 printf("%s: overlapping VMEM '%s' span 0x%" 786 PRIx64" - 0x%"PRIx64" %s\n", 787 func, vm->vm_name, 788 (uint64_t)bt2->bt_start, 789 (uint64_t)BT_END(bt2), 790 (bt2->bt_type == BT_TYPE_BUSY) ? 791 "allocated" : 792 (bt2->bt_type == BT_TYPE_FREE) ? 793 "free" : 794 (bt2->bt_type == BT_TYPE_SPAN) ? 795 "span" : "static span"); 796 return false; 797 } 798 if (BT_END(bt) > bt2->bt_start) { 799 printf("%s: overlapping VMEM '%s' span 0x%" 800 PRIx64" - 0x%"PRIx64" %s\n", 801 func, vm->vm_name, 802 (uint64_t)bt->bt_start, 803 (uint64_t)BT_END(bt), 804 (bt->bt_type == BT_TYPE_BUSY) ? 805 "allocated" : 806 (bt->bt_type == BT_TYPE_FREE) ? 807 "free" : 808 (bt->bt_type == BT_TYPE_SPAN) ? 809 "span" : "static span"); 810 printf("%s: overlapping VMEM '%s' span 0x%" 811 PRIx64" - 0x%"PRIx64" %s\n", 812 func, vm->vm_name, 813 (uint64_t)bt2->bt_start, 814 (uint64_t)BT_END(bt2), 815 (bt2->bt_type == BT_TYPE_BUSY) ? 816 "allocated" : 817 (bt2->bt_type == BT_TYPE_FREE) ? 818 "free" : 819 (bt2->bt_type == BT_TYPE_SPAN) ? 820 "span" : "static span"); 821 return false; 822 } 823 824 return true; 825 } 826 827 static bool 828 vmem_check_sanity(vmem_t *vm) 829 { 830 const bt_t *bt, *bt2; 831 832 KASSERT(vm != NULL); 833 834 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 835 if (bt->bt_start >= BT_END(bt)) { 836 printf("%s: bogus VMEM '%s' span 0x%"PRIx64 837 " - 0x%"PRIx64" %s\n", 838 __func__, vm->vm_name, 839 (uint64_t)bt->bt_start, (uint64_t)BT_END(bt), 840 (bt->bt_type == BT_TYPE_BUSY) ? 841 "allocated" : 842 (bt->bt_type == BT_TYPE_FREE) ? 843 "free" : 844 (bt->bt_type == BT_TYPE_SPAN) ? 845 "span" : "static span"); 846 return false; 847 } 848 849 CIRCLEQ_FOREACH(bt2, &vm->vm_seglist, bt_seglist) { 850 if (bt2->bt_start >= BT_END(bt2)) { 851 printf("%s: bogus VMEM '%s' span 0x%"PRIx64 852 " - 0x%"PRIx64" %s\n", 853 __func__, vm->vm_name, 854 (uint64_t)bt2->bt_start, 855 (uint64_t)BT_END(bt2), 856 (bt2->bt_type == BT_TYPE_BUSY) ? 857 "allocated" : 858 (bt2->bt_type == BT_TYPE_FREE) ? 859 "free" : 860 (bt2->bt_type == BT_TYPE_SPAN) ? 861 "span" : "static span"); 862 return false; 863 } 864 if (bt == bt2) 865 continue; 866 867 if (vmem_check_spanoverlap(__func__, vm, bt, bt2) 868 == false) 869 return false; 870 } 871 } 872 873 return true; 874 } 875 #endif /* VMEM_DEBUG */ 876 877 /* ---- vmem API */ 878 879 /* 880 * vmem_create: create an arena. 881 * 882 * => must not be called from interrupt context. 883 */ 884 885 vmem_t * 886 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 887 vmem_size_t quantum, 888 vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t), 889 void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t), 890 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags, 891 int ipl) 892 { 893 vmem_t *vm; 894 int i; 895 #if defined(_KERNEL) 896 static ONCE_DECL(control); 897 #endif /* defined(_KERNEL) */ 898 899 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 900 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 901 902 #if defined(_KERNEL) 903 if (RUN_ONCE(&control, vmem_init)) { 904 return NULL; 905 } 906 #endif /* defined(_KERNEL) */ 907 vm = xmalloc(sizeof(*vm), flags); 908 if (vm == NULL) { 909 return NULL; 910 } 911 912 VMEM_LOCK_INIT(vm, ipl); 913 vm->vm_name = name; 914 vm->vm_quantum_mask = quantum - 1; 915 vm->vm_quantum_shift = calc_order(quantum); 916 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 917 vm->vm_allocfn = allocfn; 918 vm->vm_freefn = freefn; 919 vm->vm_source = source; 920 vm->vm_nbusytag = 0; 921 #if defined(QCACHE) 922 qc_init(vm, qcache_max, ipl); 923 #endif /* defined(QCACHE) */ 924 925 CIRCLEQ_INIT(&vm->vm_seglist); 926 for (i = 0; i < VMEM_MAXORDER; i++) { 927 LIST_INIT(&vm->vm_freelist[i]); 928 } 929 vm->vm_hashlist = NULL; 930 if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) { 931 vmem_destroy1(vm); 932 return NULL; 933 } 934 935 if (size != 0) { 936 if (vmem_add(vm, base, size, flags) == 0) { 937 vmem_destroy1(vm); 938 return NULL; 939 } 940 } 941 942 #if defined(_KERNEL) 943 mutex_enter(&vmem_list_lock); 944 LIST_INSERT_HEAD(&vmem_list, vm, vm_alllist); 945 mutex_exit(&vmem_list_lock); 946 #endif /* defined(_KERNEL) */ 947 948 return vm; 949 } 950 951 void 952 vmem_destroy(vmem_t *vm) 953 { 954 955 #if defined(_KERNEL) 956 mutex_enter(&vmem_list_lock); 957 LIST_REMOVE(vm, vm_alllist); 958 mutex_exit(&vmem_list_lock); 959 #endif /* defined(_KERNEL) */ 960 961 vmem_destroy1(vm); 962 } 963 964 vmem_size_t 965 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 966 { 967 968 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 969 } 970 971 /* 972 * vmem_alloc: 973 * 974 * => caller must ensure appropriate spl, 975 * if the arena can be accessed from interrupt context. 976 */ 977 978 vmem_addr_t 979 vmem_alloc(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 980 { 981 const vm_flag_t strat __unused = flags & VM_FITMASK; 982 983 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 984 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 985 986 KASSERT(size > 0); 987 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 988 if ((flags & VM_SLEEP) != 0) { 989 ASSERT_SLEEPABLE(); 990 } 991 992 #if defined(QCACHE) 993 if (size <= vm->vm_qcache_max) { 994 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 995 qcache_t *qc = vm->vm_qcache[qidx - 1]; 996 997 return (vmem_addr_t)pool_cache_get(qc->qc_cache, 998 vmf_to_prf(flags)); 999 } 1000 #endif /* defined(QCACHE) */ 1001 1002 return vmem_xalloc(vm, size, 0, 0, 0, 0, 0, flags); 1003 } 1004 1005 vmem_addr_t 1006 vmem_xalloc(vmem_t *vm, vmem_size_t size0, vmem_size_t align, vmem_size_t phase, 1007 vmem_size_t nocross, vmem_addr_t minaddr, vmem_addr_t maxaddr, 1008 vm_flag_t flags) 1009 { 1010 struct vmem_freelist *list; 1011 struct vmem_freelist *first; 1012 struct vmem_freelist *end; 1013 bt_t *bt; 1014 bt_t *btnew; 1015 bt_t *btnew2; 1016 const vmem_size_t size = vmem_roundup_size(vm, size0); 1017 vm_flag_t strat = flags & VM_FITMASK; 1018 vmem_addr_t start; 1019 1020 KASSERT(size0 > 0); 1021 KASSERT(size > 0); 1022 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 1023 if ((flags & VM_SLEEP) != 0) { 1024 ASSERT_SLEEPABLE(); 1025 } 1026 KASSERT((align & vm->vm_quantum_mask) == 0); 1027 KASSERT((align & (align - 1)) == 0); 1028 KASSERT((phase & vm->vm_quantum_mask) == 0); 1029 KASSERT((nocross & vm->vm_quantum_mask) == 0); 1030 KASSERT((nocross & (nocross - 1)) == 0); 1031 KASSERT((align == 0 && phase == 0) || phase < align); 1032 KASSERT(nocross == 0 || nocross >= size); 1033 KASSERT(maxaddr == 0 || minaddr < maxaddr); 1034 KASSERT(!VMEM_CROSS_P(phase, phase + size - 1, nocross)); 1035 1036 if (align == 0) { 1037 align = vm->vm_quantum_mask + 1; 1038 } 1039 btnew = bt_alloc(vm, flags); 1040 if (btnew == NULL) { 1041 return VMEM_ADDR_NULL; 1042 } 1043 btnew2 = bt_alloc(vm, flags); /* XXX not necessary if no restrictions */ 1044 if (btnew2 == NULL) { 1045 bt_free(vm, btnew); 1046 return VMEM_ADDR_NULL; 1047 } 1048 1049 retry_strat: 1050 first = bt_freehead_toalloc(vm, size, strat); 1051 end = &vm->vm_freelist[VMEM_MAXORDER]; 1052 retry: 1053 bt = NULL; 1054 VMEM_LOCK(vm); 1055 KASSERT(vmem_check_sanity(vm)); 1056 if (strat == VM_INSTANTFIT) { 1057 for (list = first; list < end; list++) { 1058 bt = LIST_FIRST(list); 1059 if (bt != NULL) { 1060 start = vmem_fit(bt, size, align, phase, 1061 nocross, minaddr, maxaddr); 1062 if (start != VMEM_ADDR_NULL) { 1063 goto gotit; 1064 } 1065 } 1066 } 1067 } else { /* VM_BESTFIT */ 1068 for (list = first; list < end; list++) { 1069 LIST_FOREACH(bt, list, bt_freelist) { 1070 if (bt->bt_size >= size) { 1071 start = vmem_fit(bt, size, align, phase, 1072 nocross, minaddr, maxaddr); 1073 if (start != VMEM_ADDR_NULL) { 1074 goto gotit; 1075 } 1076 } 1077 } 1078 } 1079 } 1080 VMEM_UNLOCK(vm); 1081 #if 1 1082 if (strat == VM_INSTANTFIT) { 1083 strat = VM_BESTFIT; 1084 goto retry_strat; 1085 } 1086 #endif 1087 if (align != vm->vm_quantum_mask + 1 || phase != 0 || 1088 nocross != 0 || minaddr != 0 || maxaddr != 0) { 1089 1090 /* 1091 * XXX should try to import a region large enough to 1092 * satisfy restrictions? 1093 */ 1094 1095 goto fail; 1096 } 1097 if (vmem_import(vm, size, flags) == 0) { 1098 goto retry; 1099 } 1100 /* XXX */ 1101 fail: 1102 bt_free(vm, btnew); 1103 bt_free(vm, btnew2); 1104 return VMEM_ADDR_NULL; 1105 1106 gotit: 1107 KASSERT(bt->bt_type == BT_TYPE_FREE); 1108 KASSERT(bt->bt_size >= size); 1109 bt_remfree(vm, bt); 1110 KASSERT(vmem_check_sanity(vm)); 1111 if (bt->bt_start != start) { 1112 btnew2->bt_type = BT_TYPE_FREE; 1113 btnew2->bt_start = bt->bt_start; 1114 btnew2->bt_size = start - bt->bt_start; 1115 bt->bt_start = start; 1116 bt->bt_size -= btnew2->bt_size; 1117 bt_insfree(vm, btnew2); 1118 bt_insseg(vm, btnew2, CIRCLEQ_PREV(bt, bt_seglist)); 1119 btnew2 = NULL; 1120 KASSERT(vmem_check_sanity(vm)); 1121 } 1122 KASSERT(bt->bt_start == start); 1123 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 1124 /* split */ 1125 btnew->bt_type = BT_TYPE_BUSY; 1126 btnew->bt_start = bt->bt_start; 1127 btnew->bt_size = size; 1128 bt->bt_start = bt->bt_start + size; 1129 bt->bt_size -= size; 1130 bt_insfree(vm, bt); 1131 bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist)); 1132 bt_insbusy(vm, btnew); 1133 KASSERT(vmem_check_sanity(vm)); 1134 VMEM_UNLOCK(vm); 1135 } else { 1136 bt->bt_type = BT_TYPE_BUSY; 1137 bt_insbusy(vm, bt); 1138 KASSERT(vmem_check_sanity(vm)); 1139 VMEM_UNLOCK(vm); 1140 bt_free(vm, btnew); 1141 btnew = bt; 1142 } 1143 if (btnew2 != NULL) { 1144 bt_free(vm, btnew2); 1145 } 1146 KASSERT(btnew->bt_size >= size); 1147 btnew->bt_type = BT_TYPE_BUSY; 1148 1149 KASSERT(vmem_check_sanity(vm)); 1150 return btnew->bt_start; 1151 } 1152 1153 /* 1154 * vmem_free: 1155 * 1156 * => caller must ensure appropriate spl, 1157 * if the arena can be accessed from interrupt context. 1158 */ 1159 1160 void 1161 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1162 { 1163 1164 KASSERT(addr != VMEM_ADDR_NULL); 1165 KASSERT(size > 0); 1166 1167 #if defined(QCACHE) 1168 if (size <= vm->vm_qcache_max) { 1169 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 1170 qcache_t *qc = vm->vm_qcache[qidx - 1]; 1171 1172 return pool_cache_put(qc->qc_cache, (void *)addr); 1173 } 1174 #endif /* defined(QCACHE) */ 1175 1176 vmem_xfree(vm, addr, size); 1177 } 1178 1179 void 1180 vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1181 { 1182 bt_t *bt; 1183 bt_t *t; 1184 1185 KASSERT(addr != VMEM_ADDR_NULL); 1186 KASSERT(size > 0); 1187 1188 VMEM_LOCK(vm); 1189 1190 bt = bt_lookupbusy(vm, addr); 1191 KASSERT(bt != NULL); 1192 KASSERT(bt->bt_start == addr); 1193 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 1194 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 1195 KASSERT(bt->bt_type == BT_TYPE_BUSY); 1196 bt_rembusy(vm, bt); 1197 bt->bt_type = BT_TYPE_FREE; 1198 1199 /* coalesce */ 1200 t = CIRCLEQ_NEXT(bt, bt_seglist); 1201 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1202 KASSERT(BT_END(bt) == t->bt_start); 1203 bt_remfree(vm, t); 1204 bt_remseg(vm, t); 1205 bt->bt_size += t->bt_size; 1206 bt_free(vm, t); 1207 } 1208 t = CIRCLEQ_PREV(bt, bt_seglist); 1209 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1210 KASSERT(BT_END(t) == bt->bt_start); 1211 bt_remfree(vm, t); 1212 bt_remseg(vm, t); 1213 bt->bt_size += t->bt_size; 1214 bt->bt_start = t->bt_start; 1215 bt_free(vm, t); 1216 } 1217 1218 t = CIRCLEQ_PREV(bt, bt_seglist); 1219 KASSERT(t != NULL); 1220 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 1221 if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN && 1222 t->bt_size == bt->bt_size) { 1223 vmem_addr_t spanaddr; 1224 vmem_size_t spansize; 1225 1226 KASSERT(t->bt_start == bt->bt_start); 1227 spanaddr = bt->bt_start; 1228 spansize = bt->bt_size; 1229 bt_remseg(vm, bt); 1230 bt_free(vm, bt); 1231 bt_remseg(vm, t); 1232 bt_free(vm, t); 1233 VMEM_UNLOCK(vm); 1234 (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize); 1235 } else { 1236 bt_insfree(vm, bt); 1237 VMEM_UNLOCK(vm); 1238 } 1239 } 1240 1241 /* 1242 * vmem_add: 1243 * 1244 * => caller must ensure appropriate spl, 1245 * if the arena can be accessed from interrupt context. 1246 */ 1247 1248 vmem_addr_t 1249 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 1250 { 1251 1252 return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 1253 } 1254 1255 /* 1256 * vmem_reap: reap unused resources. 1257 * 1258 * => return true if we successfully reaped something. 1259 */ 1260 1261 bool 1262 vmem_reap(vmem_t *vm) 1263 { 1264 bool didsomething = false; 1265 1266 #if defined(QCACHE) 1267 didsomething = qc_reap(vm); 1268 #endif /* defined(QCACHE) */ 1269 return didsomething; 1270 } 1271 1272 /* ---- rehash */ 1273 1274 #if defined(_KERNEL) 1275 static struct callout vmem_rehash_ch; 1276 static int vmem_rehash_interval; 1277 static struct workqueue *vmem_rehash_wq; 1278 static struct work vmem_rehash_wk; 1279 1280 static void 1281 vmem_rehash_all(struct work *wk, void *dummy) 1282 { 1283 vmem_t *vm; 1284 1285 KASSERT(wk == &vmem_rehash_wk); 1286 mutex_enter(&vmem_list_lock); 1287 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1288 size_t desired; 1289 size_t current; 1290 1291 if (!VMEM_TRYLOCK(vm)) { 1292 continue; 1293 } 1294 desired = vm->vm_nbusytag; 1295 current = vm->vm_hashsize; 1296 VMEM_UNLOCK(vm); 1297 1298 if (desired > VMEM_HASHSIZE_MAX) { 1299 desired = VMEM_HASHSIZE_MAX; 1300 } else if (desired < VMEM_HASHSIZE_MIN) { 1301 desired = VMEM_HASHSIZE_MIN; 1302 } 1303 if (desired > current * 2 || desired * 2 < current) { 1304 vmem_rehash(vm, desired, VM_NOSLEEP); 1305 } 1306 } 1307 mutex_exit(&vmem_list_lock); 1308 1309 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1310 } 1311 1312 static void 1313 vmem_rehash_all_kick(void *dummy) 1314 { 1315 1316 workqueue_enqueue(vmem_rehash_wq, &vmem_rehash_wk, NULL); 1317 } 1318 1319 void 1320 vmem_rehash_start(void) 1321 { 1322 int error; 1323 1324 error = workqueue_create(&vmem_rehash_wq, "vmem_rehash", 1325 vmem_rehash_all, NULL, PRI_VM, IPL_SOFTCLOCK, WQ_MPSAFE); 1326 if (error) { 1327 panic("%s: workqueue_create %d\n", __func__, error); 1328 } 1329 callout_init(&vmem_rehash_ch, CALLOUT_MPSAFE); 1330 callout_setfunc(&vmem_rehash_ch, vmem_rehash_all_kick, NULL); 1331 1332 vmem_rehash_interval = hz * 10; 1333 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1334 } 1335 #endif /* defined(_KERNEL) */ 1336 1337 /* ---- debug */ 1338 1339 #if defined(DDB) 1340 static bt_t * 1341 vmem_whatis_lookup(vmem_t *vm, uintptr_t addr) 1342 { 1343 bt_t *bt; 1344 1345 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1346 if (BT_ISSPAN_P(bt)) { 1347 continue; 1348 } 1349 if (bt->bt_start <= addr && addr < BT_END(bt)) { 1350 return bt; 1351 } 1352 } 1353 1354 return NULL; 1355 } 1356 1357 void 1358 vmem_whatis(uintptr_t addr, void (*pr)(const char *, ...)) 1359 { 1360 vmem_t *vm; 1361 1362 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1363 bt_t *bt; 1364 1365 bt = vmem_whatis_lookup(vm, addr); 1366 if (bt == NULL) { 1367 continue; 1368 } 1369 (*pr)("%p is %p+%zu in VMEM '%s' (%s)\n", 1370 (void *)addr, (void *)bt->bt_start, 1371 (size_t)(addr - bt->bt_start), vm->vm_name, 1372 (bt->bt_type == BT_TYPE_BUSY) ? "allocated" : "free"); 1373 } 1374 } 1375 1376 static void 1377 vmem_showall(void (*pr)(const char *, ...)) 1378 { 1379 vmem_t *vm; 1380 1381 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1382 (*pr)("VMEM '%s' at %p\n", vm->vm_name, vm); 1383 if (vm->vm_source) 1384 (*pr)(" VMEM backend '%s' at %p\n", 1385 vm->vm_source->vm_name, vm->vm_source); 1386 } 1387 } 1388 1389 static void 1390 vmem_show(uintptr_t addr, void (*pr)(const char *, ...)) 1391 { 1392 vmem_t *vm; 1393 bt_t *bt = NULL; 1394 1395 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1396 if ((uintptr_t)vm == addr) 1397 goto found; 1398 } 1399 1400 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1401 bt = vmem_whatis_lookup(vm, addr); 1402 if (bt != NULL) 1403 goto found; 1404 } 1405 1406 return; 1407 found: 1408 1409 (*pr)("VMEM '%s' spans\n", vm->vm_name); 1410 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1411 (*pr)(" 0x%"PRIx64" - 0x%"PRIx64" %s\n", 1412 bt->bt_start, BT_END(bt), 1413 (bt->bt_type == BT_TYPE_BUSY) ? 1414 "allocated" : 1415 (bt->bt_type == BT_TYPE_FREE) ? 1416 "free" : 1417 (bt->bt_type == BT_TYPE_SPAN) ? 1418 "span" : "static span"); 1419 } 1420 } 1421 1422 void 1423 vmem_print(uintptr_t addr, const char *modif, void (*pr)(const char *, ...)) 1424 { 1425 if (modif[0] == 'a') { 1426 vmem_showall(pr); 1427 return; 1428 } 1429 1430 vmem_show(addr, pr); 1431 } 1432 #endif /* defined(DDB) */ 1433 1434 #if defined(VMEM_DEBUG) 1435 1436 #if !defined(_KERNEL) 1437 #include <stdio.h> 1438 #endif /* !defined(_KERNEL) */ 1439 1440 void bt_dump(const bt_t *); 1441 1442 void 1443 bt_dump(const bt_t *bt) 1444 { 1445 1446 printf("\t%p: %" PRIu64 ", %" PRIu64 ", %d\n", 1447 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 1448 bt->bt_type); 1449 } 1450 1451 void 1452 vmem_dump(const vmem_t *vm) 1453 { 1454 const bt_t *bt; 1455 int i; 1456 1457 printf("vmem %p '%s'\n", vm, vm->vm_name); 1458 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1459 bt_dump(bt); 1460 } 1461 1462 for (i = 0; i < VMEM_MAXORDER; i++) { 1463 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 1464 1465 if (LIST_EMPTY(fl)) { 1466 continue; 1467 } 1468 1469 printf("freelist[%d]\n", i); 1470 LIST_FOREACH(bt, fl, bt_freelist) { 1471 bt_dump(bt); 1472 if (bt->bt_size) { 1473 } 1474 } 1475 } 1476 } 1477 1478 #if !defined(_KERNEL) 1479 1480 int 1481 main() 1482 { 1483 vmem_t *vm; 1484 vmem_addr_t p; 1485 struct reg { 1486 vmem_addr_t p; 1487 vmem_size_t sz; 1488 bool x; 1489 } *reg = NULL; 1490 int nreg = 0; 1491 int nalloc = 0; 1492 int nfree = 0; 1493 vmem_size_t total = 0; 1494 #if 1 1495 vm_flag_t strat = VM_INSTANTFIT; 1496 #else 1497 vm_flag_t strat = VM_BESTFIT; 1498 #endif 1499 1500 vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1, 1501 NULL, NULL, NULL, 0, VM_SLEEP); 1502 if (vm == NULL) { 1503 printf("vmem_create\n"); 1504 exit(EXIT_FAILURE); 1505 } 1506 vmem_dump(vm); 1507 1508 p = vmem_add(vm, 100, 200, VM_SLEEP); 1509 p = vmem_add(vm, 2000, 1, VM_SLEEP); 1510 p = vmem_add(vm, 40000, 0x10000000>>12, VM_SLEEP); 1511 p = vmem_add(vm, 10000, 10000, VM_SLEEP); 1512 p = vmem_add(vm, 500, 1000, VM_SLEEP); 1513 vmem_dump(vm); 1514 for (;;) { 1515 struct reg *r; 1516 int t = rand() % 100; 1517 1518 if (t > 45) { 1519 /* alloc */ 1520 vmem_size_t sz = rand() % 500 + 1; 1521 bool x; 1522 vmem_size_t align, phase, nocross; 1523 vmem_addr_t minaddr, maxaddr; 1524 1525 if (t > 70) { 1526 x = true; 1527 /* XXX */ 1528 align = 1 << (rand() % 15); 1529 phase = rand() % 65536; 1530 nocross = 1 << (rand() % 15); 1531 if (align <= phase) { 1532 phase = 0; 1533 } 1534 if (VMEM_CROSS_P(phase, phase + sz - 1, 1535 nocross)) { 1536 nocross = 0; 1537 } 1538 minaddr = rand() % 50000; 1539 maxaddr = rand() % 70000; 1540 if (minaddr > maxaddr) { 1541 minaddr = 0; 1542 maxaddr = 0; 1543 } 1544 printf("=== xalloc %" PRIu64 1545 " align=%" PRIu64 ", phase=%" PRIu64 1546 ", nocross=%" PRIu64 ", min=%" PRIu64 1547 ", max=%" PRIu64 "\n", 1548 (uint64_t)sz, 1549 (uint64_t)align, 1550 (uint64_t)phase, 1551 (uint64_t)nocross, 1552 (uint64_t)minaddr, 1553 (uint64_t)maxaddr); 1554 p = vmem_xalloc(vm, sz, align, phase, nocross, 1555 minaddr, maxaddr, strat|VM_SLEEP); 1556 } else { 1557 x = false; 1558 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 1559 p = vmem_alloc(vm, sz, strat|VM_SLEEP); 1560 } 1561 printf("-> %" PRIu64 "\n", (uint64_t)p); 1562 vmem_dump(vm); 1563 if (p == VMEM_ADDR_NULL) { 1564 if (x) { 1565 continue; 1566 } 1567 break; 1568 } 1569 nreg++; 1570 reg = realloc(reg, sizeof(*reg) * nreg); 1571 r = ®[nreg - 1]; 1572 r->p = p; 1573 r->sz = sz; 1574 r->x = x; 1575 total += sz; 1576 nalloc++; 1577 } else if (nreg != 0) { 1578 /* free */ 1579 r = ®[rand() % nreg]; 1580 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1581 (uint64_t)r->p, (uint64_t)r->sz); 1582 if (r->x) { 1583 vmem_xfree(vm, r->p, r->sz); 1584 } else { 1585 vmem_free(vm, r->p, r->sz); 1586 } 1587 total -= r->sz; 1588 vmem_dump(vm); 1589 *r = reg[nreg - 1]; 1590 nreg--; 1591 nfree++; 1592 } 1593 printf("total=%" PRIu64 "\n", (uint64_t)total); 1594 } 1595 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1596 (uint64_t)total, nalloc, nfree); 1597 exit(EXIT_SUCCESS); 1598 } 1599 #endif /* !defined(_KERNEL) */ 1600 #endif /* defined(VMEM_DEBUG) */ 1601