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