1 /* $NetBSD: subr_vmem.c,v 1.41 2008/01/24 13:57:52 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.41 2008/01/24 13:57:52 ad Exp $"); 42 43 #define VMEM_DEBUG 44 #if defined(_KERNEL) 45 #include "opt_ddb.h" 46 #define QCACHE 47 #endif /* defined(_KERNEL) */ 48 49 #include <sys/param.h> 50 #include <sys/hash.h> 51 #include <sys/queue.h> 52 53 #if defined(_KERNEL) 54 #include <sys/systm.h> 55 #include <sys/kernel.h> /* hz */ 56 #include <sys/callout.h> 57 #include <sys/malloc.h> 58 #include <sys/once.h> 59 #include <sys/pool.h> 60 #include <sys/proc.h> 61 #include <sys/vmem.h> 62 #include <sys/workqueue.h> 63 #else /* defined(_KERNEL) */ 64 #include "../sys/vmem.h" 65 #endif /* defined(_KERNEL) */ 66 67 #if defined(_KERNEL) 68 #define LOCK_DECL(name) kmutex_t name 69 #else /* defined(_KERNEL) */ 70 #include <errno.h> 71 #include <assert.h> 72 #include <stdlib.h> 73 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_exit(a) /* nothing */ 80 #define mutex_owned(a) /* nothing */ 81 #define ASSERT_SLEEPABLE(lk, msg) /* nothing */ 82 #define IPL_VM 0 83 #endif /* defined(_KERNEL) */ 84 85 struct vmem; 86 struct vmem_btag; 87 88 #if defined(VMEM_DEBUG) 89 void vmem_dump(const vmem_t *); 90 #endif /* defined(VMEM_DEBUG) */ 91 92 #define VMEM_MAXORDER (sizeof(vmem_size_t) * CHAR_BIT) 93 94 #define VMEM_HASHSIZE_MIN 1 /* XXX */ 95 #define VMEM_HASHSIZE_MAX 8192 /* XXX */ 96 #define VMEM_HASHSIZE_INIT VMEM_HASHSIZE_MIN 97 98 #define VM_FITMASK (VM_BESTFIT | VM_INSTANTFIT) 99 100 CIRCLEQ_HEAD(vmem_seglist, vmem_btag); 101 LIST_HEAD(vmem_freelist, vmem_btag); 102 LIST_HEAD(vmem_hashlist, vmem_btag); 103 104 #if defined(QCACHE) 105 #define VMEM_QCACHE_IDX_MAX 32 106 107 #define QC_NAME_MAX 16 108 109 struct qcache { 110 pool_cache_t qc_cache; 111 vmem_t *qc_vmem; 112 char qc_name[QC_NAME_MAX]; 113 }; 114 typedef struct qcache qcache_t; 115 #define QC_POOL_TO_QCACHE(pool) ((qcache_t *)(pool->pr_qcache)) 116 #endif /* defined(QCACHE) */ 117 118 /* vmem arena */ 119 struct vmem { 120 LOCK_DECL(vm_lock); 121 vmem_addr_t (*vm_allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, 122 vm_flag_t); 123 void (*vm_freefn)(vmem_t *, vmem_addr_t, vmem_size_t); 124 vmem_t *vm_source; 125 struct vmem_seglist vm_seglist; 126 struct vmem_freelist vm_freelist[VMEM_MAXORDER]; 127 size_t vm_hashsize; 128 size_t vm_nbusytag; 129 struct vmem_hashlist *vm_hashlist; 130 size_t vm_quantum_mask; 131 int vm_quantum_shift; 132 const char *vm_name; 133 LIST_ENTRY(vmem) vm_alllist; 134 135 #if defined(QCACHE) 136 /* quantum cache */ 137 size_t vm_qcache_max; 138 struct pool_allocator vm_qcache_allocator; 139 qcache_t vm_qcache_store[VMEM_QCACHE_IDX_MAX]; 140 qcache_t *vm_qcache[VMEM_QCACHE_IDX_MAX]; 141 #endif /* defined(QCACHE) */ 142 }; 143 144 #define VMEM_LOCK(vm) mutex_enter(&vm->vm_lock) 145 #define VMEM_TRYLOCK(vm) mutex_tryenter(&vm->vm_lock) 146 #define VMEM_UNLOCK(vm) mutex_exit(&vm->vm_lock) 147 #define VMEM_LOCK_INIT(vm, ipl) mutex_init(&vm->vm_lock, MUTEX_DEFAULT, ipl) 148 #define VMEM_LOCK_DESTROY(vm) mutex_destroy(&vm->vm_lock) 149 #define VMEM_ASSERT_LOCKED(vm) KASSERT(mutex_owned(&vm->vm_lock)) 150 151 /* boundary tag */ 152 struct vmem_btag { 153 CIRCLEQ_ENTRY(vmem_btag) bt_seglist; 154 union { 155 LIST_ENTRY(vmem_btag) u_freelist; /* BT_TYPE_FREE */ 156 LIST_ENTRY(vmem_btag) u_hashlist; /* BT_TYPE_BUSY */ 157 } bt_u; 158 #define bt_hashlist bt_u.u_hashlist 159 #define bt_freelist bt_u.u_freelist 160 vmem_addr_t bt_start; 161 vmem_size_t bt_size; 162 int bt_type; 163 }; 164 165 #define BT_TYPE_SPAN 1 166 #define BT_TYPE_SPAN_STATIC 2 167 #define BT_TYPE_FREE 3 168 #define BT_TYPE_BUSY 4 169 #define BT_ISSPAN_P(bt) ((bt)->bt_type <= BT_TYPE_SPAN_STATIC) 170 171 #define BT_END(bt) ((bt)->bt_start + (bt)->bt_size) 172 173 typedef struct vmem_btag bt_t; 174 175 /* ---- misc */ 176 177 #define VMEM_ALIGNUP(addr, align) \ 178 (-(-(addr) & -(align))) 179 #define VMEM_CROSS_P(addr1, addr2, boundary) \ 180 ((((addr1) ^ (addr2)) & -(boundary)) != 0) 181 182 #define ORDER2SIZE(order) ((vmem_size_t)1 << (order)) 183 184 static int 185 calc_order(vmem_size_t size) 186 { 187 vmem_size_t target; 188 int i; 189 190 KASSERT(size != 0); 191 192 i = 0; 193 target = size >> 1; 194 while (ORDER2SIZE(i) <= target) { 195 i++; 196 } 197 198 KASSERT(ORDER2SIZE(i) <= size); 199 KASSERT(size < ORDER2SIZE(i + 1) || ORDER2SIZE(i + 1) < ORDER2SIZE(i)); 200 201 return i; 202 } 203 204 #if defined(_KERNEL) 205 static MALLOC_DEFINE(M_VMEM, "vmem", "vmem"); 206 #endif /* defined(_KERNEL) */ 207 208 static void * 209 xmalloc(size_t sz, vm_flag_t flags) 210 { 211 212 #if defined(_KERNEL) 213 return malloc(sz, M_VMEM, 214 M_CANFAIL | ((flags & VM_SLEEP) ? M_WAITOK : M_NOWAIT)); 215 #else /* defined(_KERNEL) */ 216 return malloc(sz); 217 #endif /* defined(_KERNEL) */ 218 } 219 220 static void 221 xfree(void *p) 222 { 223 224 #if defined(_KERNEL) 225 return free(p, M_VMEM); 226 #else /* defined(_KERNEL) */ 227 return free(p); 228 #endif /* defined(_KERNEL) */ 229 } 230 231 /* ---- boundary tag */ 232 233 #if defined(_KERNEL) 234 static struct pool_cache bt_cache; 235 #endif /* defined(_KERNEL) */ 236 237 static bt_t * 238 bt_alloc(vmem_t *vm, vm_flag_t flags) 239 { 240 bt_t *bt; 241 242 #if defined(_KERNEL) 243 bt = pool_cache_get(&bt_cache, 244 (flags & VM_SLEEP) != 0 ? PR_WAITOK : PR_NOWAIT); 245 #else /* defined(_KERNEL) */ 246 bt = malloc(sizeof *bt); 247 #endif /* defined(_KERNEL) */ 248 249 return bt; 250 } 251 252 static void 253 bt_free(vmem_t *vm, bt_t *bt) 254 { 255 256 #if defined(_KERNEL) 257 pool_cache_put(&bt_cache, bt); 258 #else /* defined(_KERNEL) */ 259 free(bt); 260 #endif /* defined(_KERNEL) */ 261 } 262 263 /* 264 * freelist[0] ... [1, 1] 265 * freelist[1] ... [2, 3] 266 * freelist[2] ... [4, 7] 267 * freelist[3] ... [8, 15] 268 * : 269 * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1] 270 * : 271 */ 272 273 static struct vmem_freelist * 274 bt_freehead_tofree(vmem_t *vm, vmem_size_t size) 275 { 276 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 277 int idx; 278 279 KASSERT((size & vm->vm_quantum_mask) == 0); 280 KASSERT(size != 0); 281 282 idx = calc_order(qsize); 283 KASSERT(idx >= 0); 284 KASSERT(idx < VMEM_MAXORDER); 285 286 return &vm->vm_freelist[idx]; 287 } 288 289 static struct vmem_freelist * 290 bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, vm_flag_t strat) 291 { 292 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 293 int idx; 294 295 KASSERT((size & vm->vm_quantum_mask) == 0); 296 KASSERT(size != 0); 297 298 idx = calc_order(qsize); 299 if (strat == VM_INSTANTFIT && ORDER2SIZE(idx) != qsize) { 300 idx++; 301 /* check too large request? */ 302 } 303 KASSERT(idx >= 0); 304 KASSERT(idx < VMEM_MAXORDER); 305 306 return &vm->vm_freelist[idx]; 307 } 308 309 /* ---- boundary tag hash */ 310 311 static struct vmem_hashlist * 312 bt_hashhead(vmem_t *vm, vmem_addr_t addr) 313 { 314 struct vmem_hashlist *list; 315 unsigned int hash; 316 317 hash = hash32_buf(&addr, sizeof(addr), HASH32_BUF_INIT); 318 list = &vm->vm_hashlist[hash % vm->vm_hashsize]; 319 320 return list; 321 } 322 323 static bt_t * 324 bt_lookupbusy(vmem_t *vm, vmem_addr_t addr) 325 { 326 struct vmem_hashlist *list; 327 bt_t *bt; 328 329 list = bt_hashhead(vm, addr); 330 LIST_FOREACH(bt, list, bt_hashlist) { 331 if (bt->bt_start == addr) { 332 break; 333 } 334 } 335 336 return bt; 337 } 338 339 static void 340 bt_rembusy(vmem_t *vm, bt_t *bt) 341 { 342 343 KASSERT(vm->vm_nbusytag > 0); 344 vm->vm_nbusytag--; 345 LIST_REMOVE(bt, bt_hashlist); 346 } 347 348 static void 349 bt_insbusy(vmem_t *vm, bt_t *bt) 350 { 351 struct vmem_hashlist *list; 352 353 KASSERT(bt->bt_type == BT_TYPE_BUSY); 354 355 list = bt_hashhead(vm, bt->bt_start); 356 LIST_INSERT_HEAD(list, bt, bt_hashlist); 357 vm->vm_nbusytag++; 358 } 359 360 /* ---- boundary tag list */ 361 362 static void 363 bt_remseg(vmem_t *vm, bt_t *bt) 364 { 365 366 CIRCLEQ_REMOVE(&vm->vm_seglist, bt, bt_seglist); 367 } 368 369 static void 370 bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev) 371 { 372 373 CIRCLEQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist); 374 } 375 376 static void 377 bt_insseg_tail(vmem_t *vm, bt_t *bt) 378 { 379 380 CIRCLEQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist); 381 } 382 383 static void 384 bt_remfree(vmem_t *vm, bt_t *bt) 385 { 386 387 KASSERT(bt->bt_type == BT_TYPE_FREE); 388 389 LIST_REMOVE(bt, bt_freelist); 390 } 391 392 static void 393 bt_insfree(vmem_t *vm, bt_t *bt) 394 { 395 struct vmem_freelist *list; 396 397 list = bt_freehead_tofree(vm, bt->bt_size); 398 LIST_INSERT_HEAD(list, bt, bt_freelist); 399 } 400 401 /* ---- vmem internal functions */ 402 403 #if defined(_KERNEL) 404 static kmutex_t vmem_list_lock; 405 static LIST_HEAD(, vmem) vmem_list = LIST_HEAD_INITIALIZER(vmem_list); 406 #endif /* defined(_KERNEL) */ 407 408 #if defined(QCACHE) 409 static inline vm_flag_t 410 prf_to_vmf(int prflags) 411 { 412 vm_flag_t vmflags; 413 414 KASSERT((prflags & ~(PR_LIMITFAIL | PR_WAITOK | PR_NOWAIT)) == 0); 415 if ((prflags & PR_WAITOK) != 0) { 416 vmflags = VM_SLEEP; 417 } else { 418 vmflags = VM_NOSLEEP; 419 } 420 return vmflags; 421 } 422 423 static inline int 424 vmf_to_prf(vm_flag_t vmflags) 425 { 426 int prflags; 427 428 if ((vmflags & VM_SLEEP) != 0) { 429 prflags = PR_WAITOK; 430 } else { 431 prflags = PR_NOWAIT; 432 } 433 return prflags; 434 } 435 436 static size_t 437 qc_poolpage_size(size_t qcache_max) 438 { 439 int i; 440 441 for (i = 0; ORDER2SIZE(i) <= qcache_max * 3; i++) { 442 /* nothing */ 443 } 444 return ORDER2SIZE(i); 445 } 446 447 static void * 448 qc_poolpage_alloc(struct pool *pool, int prflags) 449 { 450 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 451 vmem_t *vm = qc->qc_vmem; 452 453 return (void *)vmem_alloc(vm, pool->pr_alloc->pa_pagesz, 454 prf_to_vmf(prflags) | VM_INSTANTFIT); 455 } 456 457 static void 458 qc_poolpage_free(struct pool *pool, void *addr) 459 { 460 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 461 vmem_t *vm = qc->qc_vmem; 462 463 vmem_free(vm, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz); 464 } 465 466 static void 467 qc_init(vmem_t *vm, size_t qcache_max, int ipl) 468 { 469 qcache_t *prevqc; 470 struct pool_allocator *pa; 471 int qcache_idx_max; 472 int i; 473 474 KASSERT((qcache_max & vm->vm_quantum_mask) == 0); 475 if (qcache_max > (VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift)) { 476 qcache_max = VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift; 477 } 478 vm->vm_qcache_max = qcache_max; 479 pa = &vm->vm_qcache_allocator; 480 memset(pa, 0, sizeof(*pa)); 481 pa->pa_alloc = qc_poolpage_alloc; 482 pa->pa_free = qc_poolpage_free; 483 pa->pa_pagesz = qc_poolpage_size(qcache_max); 484 485 qcache_idx_max = qcache_max >> vm->vm_quantum_shift; 486 prevqc = NULL; 487 for (i = qcache_idx_max; i > 0; i--) { 488 qcache_t *qc = &vm->vm_qcache_store[i - 1]; 489 size_t size = i << vm->vm_quantum_shift; 490 491 qc->qc_vmem = vm; 492 snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%zu", 493 vm->vm_name, size); 494 qc->qc_cache = pool_cache_init(size, 495 ORDER2SIZE(vm->vm_quantum_shift), 0, 496 PR_NOALIGN | PR_NOTOUCH /* XXX */, 497 qc->qc_name, pa, ipl, NULL, NULL, NULL); 498 KASSERT(qc->qc_cache != NULL); /* XXX */ 499 if (prevqc != NULL && 500 qc->qc_cache->pc_pool.pr_itemsperpage == 501 prevqc->qc_cache->pc_pool.pr_itemsperpage) { 502 pool_cache_destroy(qc->qc_cache); 503 vm->vm_qcache[i - 1] = prevqc; 504 continue; 505 } 506 qc->qc_cache->pc_pool.pr_qcache = qc; 507 vm->vm_qcache[i - 1] = qc; 508 prevqc = qc; 509 } 510 } 511 512 static void 513 qc_destroy(vmem_t *vm) 514 { 515 const qcache_t *prevqc; 516 int i; 517 int qcache_idx_max; 518 519 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 520 prevqc = NULL; 521 for (i = 0; i < qcache_idx_max; i++) { 522 qcache_t *qc = vm->vm_qcache[i]; 523 524 if (prevqc == qc) { 525 continue; 526 } 527 pool_cache_destroy(qc->qc_cache); 528 prevqc = qc; 529 } 530 } 531 532 static bool 533 qc_reap(vmem_t *vm) 534 { 535 const qcache_t *prevqc; 536 int i; 537 int qcache_idx_max; 538 bool didsomething = false; 539 540 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 541 prevqc = NULL; 542 for (i = 0; i < qcache_idx_max; i++) { 543 qcache_t *qc = vm->vm_qcache[i]; 544 545 if (prevqc == qc) { 546 continue; 547 } 548 if (pool_cache_reclaim(qc->qc_cache) != 0) { 549 didsomething = true; 550 } 551 prevqc = qc; 552 } 553 554 return didsomething; 555 } 556 #endif /* defined(QCACHE) */ 557 558 #if defined(_KERNEL) 559 static int 560 vmem_init(void) 561 { 562 563 mutex_init(&vmem_list_lock, MUTEX_DEFAULT, IPL_NONE); 564 pool_cache_bootstrap(&bt_cache, sizeof(bt_t), 0, 0, 0, "vmembt", 565 NULL, IPL_VM, NULL, NULL, NULL); 566 return 0; 567 } 568 #endif /* defined(_KERNEL) */ 569 570 static vmem_addr_t 571 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 572 int spanbttype) 573 { 574 bt_t *btspan; 575 bt_t *btfree; 576 577 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 578 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 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 /* ---- vmem API */ 749 750 /* 751 * vmem_create: create an arena. 752 * 753 * => must not be called from interrupt context. 754 */ 755 756 vmem_t * 757 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 758 vmem_size_t quantum, 759 vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t), 760 void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t), 761 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags, 762 int ipl) 763 { 764 vmem_t *vm; 765 int i; 766 #if defined(_KERNEL) 767 static ONCE_DECL(control); 768 #endif /* defined(_KERNEL) */ 769 770 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 771 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 772 773 #if defined(_KERNEL) 774 if (RUN_ONCE(&control, vmem_init)) { 775 return NULL; 776 } 777 #endif /* defined(_KERNEL) */ 778 vm = xmalloc(sizeof(*vm), flags); 779 if (vm == NULL) { 780 return NULL; 781 } 782 783 VMEM_LOCK_INIT(vm, ipl); 784 vm->vm_name = name; 785 vm->vm_quantum_mask = quantum - 1; 786 vm->vm_quantum_shift = calc_order(quantum); 787 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 788 vm->vm_allocfn = allocfn; 789 vm->vm_freefn = freefn; 790 vm->vm_source = source; 791 vm->vm_nbusytag = 0; 792 #if defined(QCACHE) 793 qc_init(vm, qcache_max, ipl); 794 #endif /* defined(QCACHE) */ 795 796 CIRCLEQ_INIT(&vm->vm_seglist); 797 for (i = 0; i < VMEM_MAXORDER; i++) { 798 LIST_INIT(&vm->vm_freelist[i]); 799 } 800 vm->vm_hashlist = NULL; 801 if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) { 802 vmem_destroy1(vm); 803 return NULL; 804 } 805 806 if (size != 0) { 807 if (vmem_add(vm, base, size, flags) == 0) { 808 vmem_destroy1(vm); 809 return NULL; 810 } 811 } 812 813 #if defined(_KERNEL) 814 mutex_enter(&vmem_list_lock); 815 LIST_INSERT_HEAD(&vmem_list, vm, vm_alllist); 816 mutex_exit(&vmem_list_lock); 817 #endif /* defined(_KERNEL) */ 818 819 return vm; 820 } 821 822 void 823 vmem_destroy(vmem_t *vm) 824 { 825 826 #if defined(_KERNEL) 827 mutex_enter(&vmem_list_lock); 828 LIST_REMOVE(vm, vm_alllist); 829 mutex_exit(&vmem_list_lock); 830 #endif /* defined(_KERNEL) */ 831 832 vmem_destroy1(vm); 833 } 834 835 vmem_size_t 836 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 837 { 838 839 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 840 } 841 842 /* 843 * vmem_alloc: 844 * 845 * => caller must ensure appropriate spl, 846 * if the arena can be accessed from interrupt context. 847 */ 848 849 vmem_addr_t 850 vmem_alloc(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 851 { 852 const vm_flag_t strat __unused = flags & VM_FITMASK; 853 854 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 855 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 856 857 KASSERT(size > 0); 858 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 859 if ((flags & VM_SLEEP) != 0) { 860 ASSERT_SLEEPABLE(NULL, __func__); 861 } 862 863 #if defined(QCACHE) 864 if (size <= vm->vm_qcache_max) { 865 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 866 qcache_t *qc = vm->vm_qcache[qidx - 1]; 867 868 return (vmem_addr_t)pool_cache_get(qc->qc_cache, 869 vmf_to_prf(flags)); 870 } 871 #endif /* defined(QCACHE) */ 872 873 return vmem_xalloc(vm, size, 0, 0, 0, 0, 0, flags); 874 } 875 876 vmem_addr_t 877 vmem_xalloc(vmem_t *vm, vmem_size_t size0, vmem_size_t align, vmem_size_t phase, 878 vmem_size_t nocross, vmem_addr_t minaddr, vmem_addr_t maxaddr, 879 vm_flag_t flags) 880 { 881 struct vmem_freelist *list; 882 struct vmem_freelist *first; 883 struct vmem_freelist *end; 884 bt_t *bt; 885 bt_t *btnew; 886 bt_t *btnew2; 887 const vmem_size_t size = vmem_roundup_size(vm, size0); 888 vm_flag_t strat = flags & VM_FITMASK; 889 vmem_addr_t start; 890 891 KASSERT(size0 > 0); 892 KASSERT(size > 0); 893 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 894 if ((flags & VM_SLEEP) != 0) { 895 ASSERT_SLEEPABLE(NULL, __func__); 896 } 897 KASSERT((align & vm->vm_quantum_mask) == 0); 898 KASSERT((align & (align - 1)) == 0); 899 KASSERT((phase & vm->vm_quantum_mask) == 0); 900 KASSERT((nocross & vm->vm_quantum_mask) == 0); 901 KASSERT((nocross & (nocross - 1)) == 0); 902 KASSERT((align == 0 && phase == 0) || phase < align); 903 KASSERT(nocross == 0 || nocross >= size); 904 KASSERT(maxaddr == 0 || minaddr < maxaddr); 905 KASSERT(!VMEM_CROSS_P(phase, phase + size - 1, nocross)); 906 907 if (align == 0) { 908 align = vm->vm_quantum_mask + 1; 909 } 910 btnew = bt_alloc(vm, flags); 911 if (btnew == NULL) { 912 return VMEM_ADDR_NULL; 913 } 914 btnew2 = bt_alloc(vm, flags); /* XXX not necessary if no restrictions */ 915 if (btnew2 == NULL) { 916 bt_free(vm, btnew); 917 return VMEM_ADDR_NULL; 918 } 919 920 retry_strat: 921 first = bt_freehead_toalloc(vm, size, strat); 922 end = &vm->vm_freelist[VMEM_MAXORDER]; 923 retry: 924 bt = NULL; 925 VMEM_LOCK(vm); 926 if (strat == VM_INSTANTFIT) { 927 for (list = first; list < end; list++) { 928 bt = LIST_FIRST(list); 929 if (bt != NULL) { 930 start = vmem_fit(bt, size, align, phase, 931 nocross, minaddr, maxaddr); 932 if (start != VMEM_ADDR_NULL) { 933 goto gotit; 934 } 935 } 936 } 937 } else { /* VM_BESTFIT */ 938 for (list = first; list < end; list++) { 939 LIST_FOREACH(bt, list, bt_freelist) { 940 if (bt->bt_size >= size) { 941 start = vmem_fit(bt, size, align, phase, 942 nocross, minaddr, maxaddr); 943 if (start != VMEM_ADDR_NULL) { 944 goto gotit; 945 } 946 } 947 } 948 } 949 } 950 VMEM_UNLOCK(vm); 951 #if 1 952 if (strat == VM_INSTANTFIT) { 953 strat = VM_BESTFIT; 954 goto retry_strat; 955 } 956 #endif 957 if (align != vm->vm_quantum_mask + 1 || phase != 0 || 958 nocross != 0 || minaddr != 0 || maxaddr != 0) { 959 960 /* 961 * XXX should try to import a region large enough to 962 * satisfy restrictions? 963 */ 964 965 goto fail; 966 } 967 if (vmem_import(vm, size, flags) == 0) { 968 goto retry; 969 } 970 /* XXX */ 971 fail: 972 bt_free(vm, btnew); 973 bt_free(vm, btnew2); 974 return VMEM_ADDR_NULL; 975 976 gotit: 977 KASSERT(bt->bt_type == BT_TYPE_FREE); 978 KASSERT(bt->bt_size >= size); 979 bt_remfree(vm, bt); 980 if (bt->bt_start != start) { 981 btnew2->bt_type = BT_TYPE_FREE; 982 btnew2->bt_start = bt->bt_start; 983 btnew2->bt_size = start - bt->bt_start; 984 bt->bt_start = start; 985 bt->bt_size -= btnew2->bt_size; 986 bt_insfree(vm, btnew2); 987 bt_insseg(vm, btnew2, CIRCLEQ_PREV(bt, bt_seglist)); 988 btnew2 = NULL; 989 } 990 KASSERT(bt->bt_start == start); 991 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 992 /* split */ 993 btnew->bt_type = BT_TYPE_BUSY; 994 btnew->bt_start = bt->bt_start; 995 btnew->bt_size = size; 996 bt->bt_start = bt->bt_start + size; 997 bt->bt_size -= size; 998 bt_insfree(vm, bt); 999 bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist)); 1000 bt_insbusy(vm, btnew); 1001 VMEM_UNLOCK(vm); 1002 } else { 1003 bt->bt_type = BT_TYPE_BUSY; 1004 bt_insbusy(vm, bt); 1005 VMEM_UNLOCK(vm); 1006 bt_free(vm, btnew); 1007 btnew = bt; 1008 } 1009 if (btnew2 != NULL) { 1010 bt_free(vm, btnew2); 1011 } 1012 KASSERT(btnew->bt_size >= size); 1013 btnew->bt_type = BT_TYPE_BUSY; 1014 1015 return btnew->bt_start; 1016 } 1017 1018 /* 1019 * vmem_free: 1020 * 1021 * => caller must ensure appropriate spl, 1022 * if the arena can be accessed from interrupt context. 1023 */ 1024 1025 void 1026 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1027 { 1028 1029 KASSERT(addr != VMEM_ADDR_NULL); 1030 KASSERT(size > 0); 1031 1032 #if defined(QCACHE) 1033 if (size <= vm->vm_qcache_max) { 1034 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 1035 qcache_t *qc = vm->vm_qcache[qidx - 1]; 1036 1037 return pool_cache_put(qc->qc_cache, (void *)addr); 1038 } 1039 #endif /* defined(QCACHE) */ 1040 1041 vmem_xfree(vm, addr, size); 1042 } 1043 1044 void 1045 vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1046 { 1047 bt_t *bt; 1048 bt_t *t; 1049 1050 KASSERT(addr != VMEM_ADDR_NULL); 1051 KASSERT(size > 0); 1052 1053 VMEM_LOCK(vm); 1054 1055 bt = bt_lookupbusy(vm, addr); 1056 KASSERT(bt != NULL); 1057 KASSERT(bt->bt_start == addr); 1058 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 1059 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 1060 KASSERT(bt->bt_type == BT_TYPE_BUSY); 1061 bt_rembusy(vm, bt); 1062 bt->bt_type = BT_TYPE_FREE; 1063 1064 /* coalesce */ 1065 t = CIRCLEQ_NEXT(bt, bt_seglist); 1066 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1067 KASSERT(BT_END(bt) == t->bt_start); 1068 bt_remfree(vm, t); 1069 bt_remseg(vm, t); 1070 bt->bt_size += t->bt_size; 1071 bt_free(vm, t); 1072 } 1073 t = CIRCLEQ_PREV(bt, bt_seglist); 1074 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1075 KASSERT(BT_END(t) == bt->bt_start); 1076 bt_remfree(vm, t); 1077 bt_remseg(vm, t); 1078 bt->bt_size += t->bt_size; 1079 bt->bt_start = t->bt_start; 1080 bt_free(vm, t); 1081 } 1082 1083 t = CIRCLEQ_PREV(bt, bt_seglist); 1084 KASSERT(t != NULL); 1085 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 1086 if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN && 1087 t->bt_size == bt->bt_size) { 1088 vmem_addr_t spanaddr; 1089 vmem_size_t spansize; 1090 1091 KASSERT(t->bt_start == bt->bt_start); 1092 spanaddr = bt->bt_start; 1093 spansize = bt->bt_size; 1094 bt_remseg(vm, bt); 1095 bt_free(vm, bt); 1096 bt_remseg(vm, t); 1097 bt_free(vm, t); 1098 VMEM_UNLOCK(vm); 1099 (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize); 1100 } else { 1101 bt_insfree(vm, bt); 1102 VMEM_UNLOCK(vm); 1103 } 1104 } 1105 1106 /* 1107 * vmem_add: 1108 * 1109 * => caller must ensure appropriate spl, 1110 * if the arena can be accessed from interrupt context. 1111 */ 1112 1113 vmem_addr_t 1114 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 1115 { 1116 1117 return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 1118 } 1119 1120 /* 1121 * vmem_reap: reap unused resources. 1122 * 1123 * => return true if we successfully reaped something. 1124 */ 1125 1126 bool 1127 vmem_reap(vmem_t *vm) 1128 { 1129 bool didsomething = false; 1130 1131 #if defined(QCACHE) 1132 didsomething = qc_reap(vm); 1133 #endif /* defined(QCACHE) */ 1134 return didsomething; 1135 } 1136 1137 /* ---- rehash */ 1138 1139 #if defined(_KERNEL) 1140 static struct callout vmem_rehash_ch; 1141 static int vmem_rehash_interval; 1142 static struct workqueue *vmem_rehash_wq; 1143 static struct work vmem_rehash_wk; 1144 1145 static void 1146 vmem_rehash_all(struct work *wk, void *dummy) 1147 { 1148 vmem_t *vm; 1149 1150 KASSERT(wk == &vmem_rehash_wk); 1151 mutex_enter(&vmem_list_lock); 1152 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1153 size_t desired; 1154 size_t current; 1155 1156 if (!VMEM_TRYLOCK(vm)) { 1157 continue; 1158 } 1159 desired = vm->vm_nbusytag; 1160 current = vm->vm_hashsize; 1161 VMEM_UNLOCK(vm); 1162 1163 if (desired > VMEM_HASHSIZE_MAX) { 1164 desired = VMEM_HASHSIZE_MAX; 1165 } else if (desired < VMEM_HASHSIZE_MIN) { 1166 desired = VMEM_HASHSIZE_MIN; 1167 } 1168 if (desired > current * 2 || desired * 2 < current) { 1169 vmem_rehash(vm, desired, VM_NOSLEEP); 1170 } 1171 } 1172 mutex_exit(&vmem_list_lock); 1173 1174 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1175 } 1176 1177 static void 1178 vmem_rehash_all_kick(void *dummy) 1179 { 1180 1181 workqueue_enqueue(vmem_rehash_wq, &vmem_rehash_wk, NULL); 1182 } 1183 1184 void 1185 vmem_rehash_start(void) 1186 { 1187 int error; 1188 1189 error = workqueue_create(&vmem_rehash_wq, "vmem_rehash", 1190 vmem_rehash_all, NULL, PRI_VM, IPL_SOFTCLOCK, WQ_MPSAFE); 1191 if (error) { 1192 panic("%s: workqueue_create %d\n", __func__, error); 1193 } 1194 callout_init(&vmem_rehash_ch, CALLOUT_MPSAFE); 1195 callout_setfunc(&vmem_rehash_ch, vmem_rehash_all_kick, NULL); 1196 1197 vmem_rehash_interval = hz * 10; 1198 callout_schedule(&vmem_rehash_ch, vmem_rehash_interval); 1199 } 1200 #endif /* defined(_KERNEL) */ 1201 1202 /* ---- debug */ 1203 1204 #if defined(DDB) 1205 static bt_t * 1206 vmem_whatis_lookup(vmem_t *vm, uintptr_t addr) 1207 { 1208 bt_t *bt; 1209 1210 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1211 if (BT_ISSPAN_P(bt)) { 1212 continue; 1213 } 1214 if (bt->bt_start <= addr && addr < BT_END(bt)) { 1215 return bt; 1216 } 1217 } 1218 1219 return NULL; 1220 } 1221 1222 void 1223 vmem_whatis(uintptr_t addr, void (*pr)(const char *, ...)) 1224 { 1225 vmem_t *vm; 1226 1227 LIST_FOREACH(vm, &vmem_list, vm_alllist) { 1228 bt_t *bt; 1229 1230 bt = vmem_whatis_lookup(vm, addr); 1231 if (bt == NULL) { 1232 continue; 1233 } 1234 (*pr)("%p is %p+%zu in VMEM '%s' (%s)\n", 1235 (void *)addr, (void *)bt->bt_start, 1236 (size_t)(addr - bt->bt_start), vm->vm_name, 1237 (bt->bt_type == BT_TYPE_BUSY) ? "allocated" : "free"); 1238 } 1239 } 1240 #endif /* defined(DDB) */ 1241 1242 #if defined(VMEM_DEBUG) 1243 1244 #if !defined(_KERNEL) 1245 #include <stdio.h> 1246 #endif /* !defined(_KERNEL) */ 1247 1248 void bt_dump(const bt_t *); 1249 1250 void 1251 bt_dump(const bt_t *bt) 1252 { 1253 1254 printf("\t%p: %" PRIu64 ", %" PRIu64 ", %d\n", 1255 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 1256 bt->bt_type); 1257 } 1258 1259 void 1260 vmem_dump(const vmem_t *vm) 1261 { 1262 const bt_t *bt; 1263 int i; 1264 1265 printf("vmem %p '%s'\n", vm, vm->vm_name); 1266 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1267 bt_dump(bt); 1268 } 1269 1270 for (i = 0; i < VMEM_MAXORDER; i++) { 1271 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 1272 1273 if (LIST_EMPTY(fl)) { 1274 continue; 1275 } 1276 1277 printf("freelist[%d]\n", i); 1278 LIST_FOREACH(bt, fl, bt_freelist) { 1279 bt_dump(bt); 1280 if (bt->bt_size) { 1281 } 1282 } 1283 } 1284 } 1285 1286 #if !defined(_KERNEL) 1287 1288 int 1289 main() 1290 { 1291 vmem_t *vm; 1292 vmem_addr_t p; 1293 struct reg { 1294 vmem_addr_t p; 1295 vmem_size_t sz; 1296 bool x; 1297 } *reg = NULL; 1298 int nreg = 0; 1299 int nalloc = 0; 1300 int nfree = 0; 1301 vmem_size_t total = 0; 1302 #if 1 1303 vm_flag_t strat = VM_INSTANTFIT; 1304 #else 1305 vm_flag_t strat = VM_BESTFIT; 1306 #endif 1307 1308 vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1, 1309 NULL, NULL, NULL, 0, VM_SLEEP); 1310 if (vm == NULL) { 1311 printf("vmem_create\n"); 1312 exit(EXIT_FAILURE); 1313 } 1314 vmem_dump(vm); 1315 1316 p = vmem_add(vm, 100, 200, VM_SLEEP); 1317 p = vmem_add(vm, 2000, 1, VM_SLEEP); 1318 p = vmem_add(vm, 40000, 0x10000000>>12, VM_SLEEP); 1319 p = vmem_add(vm, 10000, 10000, VM_SLEEP); 1320 p = vmem_add(vm, 500, 1000, VM_SLEEP); 1321 vmem_dump(vm); 1322 for (;;) { 1323 struct reg *r; 1324 int t = rand() % 100; 1325 1326 if (t > 45) { 1327 /* alloc */ 1328 vmem_size_t sz = rand() % 500 + 1; 1329 bool x; 1330 vmem_size_t align, phase, nocross; 1331 vmem_addr_t minaddr, maxaddr; 1332 1333 if (t > 70) { 1334 x = true; 1335 /* XXX */ 1336 align = 1 << (rand() % 15); 1337 phase = rand() % 65536; 1338 nocross = 1 << (rand() % 15); 1339 if (align <= phase) { 1340 phase = 0; 1341 } 1342 if (VMEM_CROSS_P(phase, phase + sz - 1, 1343 nocross)) { 1344 nocross = 0; 1345 } 1346 minaddr = rand() % 50000; 1347 maxaddr = rand() % 70000; 1348 if (minaddr > maxaddr) { 1349 minaddr = 0; 1350 maxaddr = 0; 1351 } 1352 printf("=== xalloc %" PRIu64 1353 " align=%" PRIu64 ", phase=%" PRIu64 1354 ", nocross=%" PRIu64 ", min=%" PRIu64 1355 ", max=%" PRIu64 "\n", 1356 (uint64_t)sz, 1357 (uint64_t)align, 1358 (uint64_t)phase, 1359 (uint64_t)nocross, 1360 (uint64_t)minaddr, 1361 (uint64_t)maxaddr); 1362 p = vmem_xalloc(vm, sz, align, phase, nocross, 1363 minaddr, maxaddr, strat|VM_SLEEP); 1364 } else { 1365 x = false; 1366 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 1367 p = vmem_alloc(vm, sz, strat|VM_SLEEP); 1368 } 1369 printf("-> %" PRIu64 "\n", (uint64_t)p); 1370 vmem_dump(vm); 1371 if (p == VMEM_ADDR_NULL) { 1372 if (x) { 1373 continue; 1374 } 1375 break; 1376 } 1377 nreg++; 1378 reg = realloc(reg, sizeof(*reg) * nreg); 1379 r = ®[nreg - 1]; 1380 r->p = p; 1381 r->sz = sz; 1382 r->x = x; 1383 total += sz; 1384 nalloc++; 1385 } else if (nreg != 0) { 1386 /* free */ 1387 r = ®[rand() % nreg]; 1388 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1389 (uint64_t)r->p, (uint64_t)r->sz); 1390 if (r->x) { 1391 vmem_xfree(vm, r->p, r->sz); 1392 } else { 1393 vmem_free(vm, r->p, r->sz); 1394 } 1395 total -= r->sz; 1396 vmem_dump(vm); 1397 *r = reg[nreg - 1]; 1398 nreg--; 1399 nfree++; 1400 } 1401 printf("total=%" PRIu64 "\n", (uint64_t)total); 1402 } 1403 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1404 (uint64_t)total, nalloc, nfree); 1405 exit(EXIT_SUCCESS); 1406 } 1407 #endif /* !defined(_KERNEL) */ 1408 #endif /* defined(VMEM_DEBUG) */ 1409