subr_vmem.c revision 1.6
1 /* $NetBSD: subr_vmem.c,v 1.6 2006/08/20 09:45:59 yamt 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 * - implement vmem_xalloc/vmem_xfree 37 */ 38 39 #include <sys/cdefs.h> 40 __KERNEL_RCSID(0, "$NetBSD: subr_vmem.c,v 1.6 2006/08/20 09:45:59 yamt Exp $"); 41 42 #define VMEM_DEBUG 43 #if defined(_KERNEL) 44 #define QCACHE 45 #endif /* defined(_KERNEL) */ 46 47 #include <sys/param.h> 48 #include <sys/hash.h> 49 #include <sys/queue.h> 50 51 #if defined(_KERNEL) 52 #include <sys/systm.h> 53 #include <sys/lock.h> 54 #include <sys/malloc.h> 55 #include <sys/once.h> 56 #include <sys/pool.h> 57 #include <sys/proc.h> 58 #include <sys/vmem.h> 59 #else /* defined(_KERNEL) */ 60 #include "../sys/vmem.h" 61 #endif /* defined(_KERNEL) */ 62 63 #if defined(_KERNEL) 64 #define SIMPLELOCK_DECL(name) struct simplelock name 65 #else /* defined(_KERNEL) */ 66 #include <errno.h> 67 #include <assert.h> 68 #include <stdlib.h> 69 70 #define KASSERT(a) assert(a) 71 #define SIMPLELOCK_DECL(name) /* nothing */ 72 #define LOCK_ASSERT(a) /* nothing */ 73 #define simple_lock_init(a) /* nothing */ 74 #define simple_lock(a) /* nothing */ 75 #define simple_unlock(a) /* nothing */ 76 #define ASSERT_SLEEPABLE(lk, msg) /* nothing */ 77 #endif /* defined(_KERNEL) */ 78 79 struct vmem; 80 struct vmem_btag; 81 82 #if defined(VMEM_DEBUG) 83 void vmem_dump(const vmem_t *); 84 #endif /* defined(VMEM_DEBUG) */ 85 86 #define VMEM_MAXORDER (sizeof(vmem_size_t) * CHAR_BIT) 87 #define VMEM_HASHSIZE_INIT 4096 /* XXX */ 88 89 #define VM_FITMASK (VM_BESTFIT | VM_INSTANTFIT) 90 91 CIRCLEQ_HEAD(vmem_seglist, vmem_btag); 92 LIST_HEAD(vmem_freelist, vmem_btag); 93 LIST_HEAD(vmem_hashlist, vmem_btag); 94 95 #if defined(QCACHE) 96 #define VMEM_QCACHE_IDX_MAX 32 97 98 #define QC_NAME_MAX 16 99 100 struct qcache { 101 struct pool qc_pool; 102 struct pool_cache qc_cache; 103 vmem_t *qc_vmem; 104 char qc_name[QC_NAME_MAX]; 105 }; 106 typedef struct qcache qcache_t; 107 #define QC_POOL_TO_QCACHE(pool) ((qcache_t *)(pool)) 108 #endif /* defined(QCACHE) */ 109 110 /* vmem arena */ 111 struct vmem { 112 SIMPLELOCK_DECL(vm_lock); 113 vmem_addr_t (*vm_allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, 114 vm_flag_t); 115 void (*vm_freefn)(vmem_t *, vmem_addr_t, vmem_size_t); 116 vmem_t *vm_source; 117 struct vmem_seglist vm_seglist; 118 struct vmem_freelist vm_freelist[VMEM_MAXORDER]; 119 size_t vm_hashsize; 120 size_t vm_nbusytag; 121 struct vmem_hashlist *vm_hashlist; 122 size_t vm_quantum_mask; 123 int vm_quantum_shift; 124 const char *vm_name; 125 126 #if defined(QCACHE) 127 /* quantum cache */ 128 size_t vm_qcache_max; 129 struct pool_allocator vm_qcache_allocator; 130 qcache_t vm_qcache[VMEM_QCACHE_IDX_MAX]; 131 #endif /* defined(QCACHE) */ 132 }; 133 134 #define VMEM_LOCK(vm) simple_lock(&vm->vm_lock) 135 #define VMEM_UNLOCK(vm) simple_unlock(&vm->vm_lock) 136 #define VMEM_LOCK_INIT(vm) simple_lock_init(&vm->vm_lock); 137 #define VMEM_ASSERT_LOCKED(vm) \ 138 LOCK_ASSERT(simple_lock_held(&vm->vm_lock)) 139 #define VMEM_ASSERT_UNLOCKED(vm) \ 140 LOCK_ASSERT(!simple_lock_held(&vm->vm_lock)) 141 142 /* boundary tag */ 143 struct vmem_btag { 144 CIRCLEQ_ENTRY(vmem_btag) bt_seglist; 145 union { 146 LIST_ENTRY(vmem_btag) u_freelist; /* BT_TYPE_FREE */ 147 LIST_ENTRY(vmem_btag) u_hashlist; /* BT_TYPE_BUSY */ 148 } bt_u; 149 #define bt_hashlist bt_u.u_hashlist 150 #define bt_freelist bt_u.u_freelist 151 vmem_addr_t bt_start; 152 vmem_size_t bt_size; 153 int bt_type; 154 }; 155 156 #define BT_TYPE_SPAN 1 157 #define BT_TYPE_SPAN_STATIC 2 158 #define BT_TYPE_FREE 3 159 #define BT_TYPE_BUSY 4 160 #define BT_ISSPAN_P(bt) ((bt)->bt_type <= BT_TYPE_SPAN_STATIC) 161 162 #define BT_END(bt) ((bt)->bt_start + (bt)->bt_size) 163 164 typedef struct vmem_btag bt_t; 165 166 /* ---- misc */ 167 168 #define ORDER2SIZE(order) ((vmem_size_t)1 << (order)) 169 170 static int 171 calc_order(vmem_size_t size) 172 { 173 vmem_size_t target; 174 int i; 175 176 KASSERT(size != 0); 177 178 i = 0; 179 target = size >> 1; 180 while (ORDER2SIZE(i) <= target) { 181 i++; 182 } 183 184 KASSERT(ORDER2SIZE(i) <= size); 185 KASSERT(size < ORDER2SIZE(i + 1) || ORDER2SIZE(i + 1) < ORDER2SIZE(i)); 186 187 return i; 188 } 189 190 #if defined(_KERNEL) 191 static MALLOC_DEFINE(M_VMEM, "vmem", "vmem"); 192 #endif /* defined(_KERNEL) */ 193 194 static void * 195 xmalloc(size_t sz, vm_flag_t flags) 196 { 197 198 #if defined(_KERNEL) 199 return malloc(sz, M_VMEM, 200 M_CANFAIL | ((flags & VM_SLEEP) ? M_WAITOK : M_NOWAIT)); 201 #else /* defined(_KERNEL) */ 202 return malloc(sz); 203 #endif /* defined(_KERNEL) */ 204 } 205 206 static void 207 xfree(void *p) 208 { 209 210 #if defined(_KERNEL) 211 return free(p, M_VMEM); 212 #else /* defined(_KERNEL) */ 213 return free(p); 214 #endif /* defined(_KERNEL) */ 215 } 216 217 /* ---- boundary tag */ 218 219 #if defined(_KERNEL) 220 static struct pool_cache bt_poolcache; 221 static POOL_INIT(bt_pool, sizeof(bt_t), 0, 0, 0, "vmembtpl", NULL); 222 #endif /* defined(_KERNEL) */ 223 224 static bt_t * 225 bt_alloc(vmem_t *vm, vm_flag_t flags) 226 { 227 bt_t *bt; 228 229 #if defined(_KERNEL) 230 /* XXX bootstrap */ 231 bt = pool_cache_get(&bt_poolcache, 232 (flags & VM_SLEEP) != 0 ? PR_WAITOK : PR_NOWAIT); 233 #else /* defined(_KERNEL) */ 234 bt = malloc(sizeof *bt); 235 #endif /* defined(_KERNEL) */ 236 237 return bt; 238 } 239 240 static void 241 bt_free(vmem_t *vm, bt_t *bt) 242 { 243 244 #if defined(_KERNEL) 245 /* XXX bootstrap */ 246 pool_cache_put(&bt_poolcache, bt); 247 #else /* defined(_KERNEL) */ 248 free(bt); 249 #endif /* defined(_KERNEL) */ 250 } 251 252 /* 253 * freelist[0] ... [1, 1] 254 * freelist[1] ... [2, 3] 255 * freelist[2] ... [4, 7] 256 * freelist[3] ... [8, 15] 257 * : 258 * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1] 259 * : 260 */ 261 262 static struct vmem_freelist * 263 bt_freehead_tofree(vmem_t *vm, vmem_size_t size) 264 { 265 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 266 int idx; 267 268 KASSERT((size & vm->vm_quantum_mask) == 0); 269 KASSERT(size != 0); 270 271 idx = calc_order(qsize); 272 KASSERT(idx >= 0); 273 KASSERT(idx < VMEM_MAXORDER); 274 275 return &vm->vm_freelist[idx]; 276 } 277 278 static struct vmem_freelist * 279 bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, vm_flag_t strat) 280 { 281 const vmem_size_t qsize = size >> vm->vm_quantum_shift; 282 int idx; 283 284 KASSERT((size & vm->vm_quantum_mask) == 0); 285 KASSERT(size != 0); 286 287 idx = calc_order(qsize); 288 if (strat == VM_INSTANTFIT && ORDER2SIZE(idx) != qsize) { 289 idx++; 290 /* check too large request? */ 291 } 292 KASSERT(idx >= 0); 293 KASSERT(idx < VMEM_MAXORDER); 294 295 return &vm->vm_freelist[idx]; 296 } 297 298 /* ---- boundary tag hash */ 299 300 static struct vmem_hashlist * 301 bt_hashhead(vmem_t *vm, vmem_addr_t addr) 302 { 303 struct vmem_hashlist *list; 304 unsigned int hash; 305 306 hash = hash32_buf(&addr, sizeof(addr), HASH32_BUF_INIT); 307 list = &vm->vm_hashlist[hash % vm->vm_hashsize]; 308 309 return list; 310 } 311 312 static bt_t * 313 bt_lookupbusy(vmem_t *vm, vmem_addr_t addr) 314 { 315 struct vmem_hashlist *list; 316 bt_t *bt; 317 318 list = bt_hashhead(vm, addr); 319 LIST_FOREACH(bt, list, bt_hashlist) { 320 if (bt->bt_start == addr) { 321 break; 322 } 323 } 324 325 return bt; 326 } 327 328 static void 329 bt_rembusy(vmem_t *vm, bt_t *bt) 330 { 331 332 KASSERT(vm->vm_nbusytag > 0); 333 vm->vm_nbusytag--; 334 LIST_REMOVE(bt, bt_hashlist); 335 } 336 337 static void 338 bt_insbusy(vmem_t *vm, bt_t *bt) 339 { 340 struct vmem_hashlist *list; 341 342 KASSERT(bt->bt_type == BT_TYPE_BUSY); 343 344 list = bt_hashhead(vm, bt->bt_start); 345 LIST_INSERT_HEAD(list, bt, bt_hashlist); 346 vm->vm_nbusytag++; 347 } 348 349 /* ---- boundary tag list */ 350 351 static void 352 bt_remseg(vmem_t *vm, bt_t *bt) 353 { 354 355 CIRCLEQ_REMOVE(&vm->vm_seglist, bt, bt_seglist); 356 } 357 358 static void 359 bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev) 360 { 361 362 CIRCLEQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist); 363 } 364 365 static void 366 bt_insseg_tail(vmem_t *vm, bt_t *bt) 367 { 368 369 CIRCLEQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist); 370 } 371 372 static void 373 bt_remfree(vmem_t *vm, bt_t *bt) 374 { 375 376 KASSERT(bt->bt_type == BT_TYPE_FREE); 377 378 LIST_REMOVE(bt, bt_freelist); 379 } 380 381 static void 382 bt_insfree(vmem_t *vm, bt_t *bt) 383 { 384 struct vmem_freelist *list; 385 386 list = bt_freehead_tofree(vm, bt->bt_size); 387 LIST_INSERT_HEAD(list, bt, bt_freelist); 388 } 389 390 /* ---- vmem internal functions */ 391 392 #if defined(QCACHE) 393 static inline vm_flag_t 394 prf_to_vmf(int prflags) 395 { 396 vm_flag_t vmflags; 397 398 KASSERT((prflags & ~(PR_LIMITFAIL | PR_WAITOK | PR_NOWAIT)) == 0); 399 if ((prflags & PR_WAITOK) != 0) { 400 vmflags = VM_SLEEP; 401 } else { 402 vmflags = VM_NOSLEEP; 403 } 404 return vmflags; 405 } 406 407 static inline int 408 vmf_to_prf(vm_flag_t vmflags) 409 { 410 int prflags; 411 412 switch ((vmflags & (VM_SLEEP | VM_NOSLEEP))) { 413 case VM_SLEEP: 414 prflags = PR_WAITOK; 415 break; 416 417 case VM_NOSLEEP: 418 prflags = PR_NOWAIT; 419 break; 420 421 #if defined(DIAGNOSTIC) 422 default: 423 panic("vmf_to_prf: unknown flag 0x%x\n", vmflags); 424 #endif /* defined(DIAGNOSTIC) */ 425 } 426 return prflags; 427 } 428 429 static size_t 430 qc_poolpage_size(size_t qcache_max) 431 { 432 int i; 433 434 for (i = 0; ORDER2SIZE(i) <= qcache_max * 3; i++) { 435 /* nothing */ 436 } 437 return ORDER2SIZE(i); 438 } 439 440 static void * 441 qc_poolpage_alloc(struct pool *pool, int prflags) 442 { 443 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 444 vmem_t *vm = qc->qc_vmem; 445 446 return (void *)vmem_alloc(vm, pool->pr_alloc->pa_pagesz, 447 prf_to_vmf(prflags) | VM_INSTANTFIT); 448 } 449 450 static void 451 qc_poolpage_free(struct pool *pool, void *addr) 452 { 453 qcache_t *qc = QC_POOL_TO_QCACHE(pool); 454 vmem_t *vm = qc->qc_vmem; 455 456 vmem_free(vm, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz); 457 } 458 459 static void 460 qc_init(vmem_t *vm, size_t qcache_max) 461 { 462 struct pool_allocator *pa; 463 int qcache_idx_max; 464 int i; 465 466 KASSERT((qcache_max & vm->vm_quantum_mask) == 0); 467 if (qcache_max > (VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift)) { 468 qcache_max = VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift; 469 } 470 vm->vm_qcache_max = qcache_max; 471 pa = &vm->vm_qcache_allocator; 472 memset(pa, 0, sizeof(*pa)); 473 pa->pa_alloc = qc_poolpage_alloc; 474 pa->pa_free = qc_poolpage_free; 475 pa->pa_pagesz = qc_poolpage_size(qcache_max); 476 477 qcache_idx_max = qcache_max >> vm->vm_quantum_shift; 478 for (i = 1; i <= qcache_idx_max; i++) { 479 qcache_t *qc = &vm->vm_qcache[i - 1]; 480 size_t size = i << vm->vm_quantum_shift; 481 482 qc->qc_vmem = vm; 483 snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%d", 484 vm->vm_name, size); 485 pool_init(&qc->qc_pool, size, 0, 0, 486 PR_NOALIGN | PR_NOTOUCH /* XXX */, qc->qc_name, pa); 487 pool_cache_init(&qc->qc_cache, &qc->qc_pool, NULL, NULL, NULL); 488 } 489 } 490 491 static boolean_t 492 qc_reap(vmem_t *vm) 493 { 494 int i; 495 int qcache_idx_max; 496 boolean_t didsomething = FALSE; 497 498 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 499 for (i = 1; i <= qcache_idx_max; i++) { 500 qcache_t *qc = &vm->vm_qcache[i - 1]; 501 502 if (pool_reclaim(&qc->qc_pool) != 0) { 503 didsomething = TRUE; 504 } 505 } 506 507 return didsomething; 508 } 509 #endif /* defined(QCACHE) */ 510 511 #if defined(_KERNEL) 512 static int 513 vmem_init(void) 514 { 515 516 pool_cache_init(&bt_poolcache, &bt_pool, NULL, NULL, NULL); 517 return 0; 518 } 519 #endif /* defined(_KERNEL) */ 520 521 static vmem_addr_t 522 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 523 int spanbttype) 524 { 525 bt_t *btspan; 526 bt_t *btfree; 527 528 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 529 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 530 VMEM_ASSERT_UNLOCKED(vm); 531 532 btspan = bt_alloc(vm, flags); 533 if (btspan == NULL) { 534 return VMEM_ADDR_NULL; 535 } 536 btfree = bt_alloc(vm, flags); 537 if (btfree == NULL) { 538 bt_free(vm, btspan); 539 return VMEM_ADDR_NULL; 540 } 541 542 btspan->bt_type = spanbttype; 543 btspan->bt_start = addr; 544 btspan->bt_size = size; 545 546 btfree->bt_type = BT_TYPE_FREE; 547 btfree->bt_start = addr; 548 btfree->bt_size = size; 549 550 VMEM_LOCK(vm); 551 bt_insseg_tail(vm, btspan); 552 bt_insseg(vm, btfree, btspan); 553 bt_insfree(vm, btfree); 554 VMEM_UNLOCK(vm); 555 556 return addr; 557 } 558 559 static int 560 vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 561 { 562 vmem_addr_t addr; 563 564 VMEM_ASSERT_UNLOCKED(vm); 565 566 if (vm->vm_allocfn == NULL) { 567 return EINVAL; 568 } 569 570 addr = (*vm->vm_allocfn)(vm->vm_source, size, &size, flags); 571 if (addr == VMEM_ADDR_NULL) { 572 return ENOMEM; 573 } 574 575 if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) == VMEM_ADDR_NULL) { 576 (*vm->vm_freefn)(vm->vm_source, addr, size); 577 return ENOMEM; 578 } 579 580 return 0; 581 } 582 583 static int 584 vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags) 585 { 586 bt_t *bt; 587 int i; 588 struct vmem_hashlist *newhashlist; 589 struct vmem_hashlist *oldhashlist; 590 size_t oldhashsize; 591 592 KASSERT(newhashsize > 0); 593 VMEM_ASSERT_UNLOCKED(vm); 594 595 newhashlist = 596 xmalloc(sizeof(struct vmem_hashlist *) * newhashsize, flags); 597 if (newhashlist == NULL) { 598 return ENOMEM; 599 } 600 for (i = 0; i < newhashsize; i++) { 601 LIST_INIT(&newhashlist[i]); 602 } 603 604 VMEM_LOCK(vm); 605 oldhashlist = vm->vm_hashlist; 606 oldhashsize = vm->vm_hashsize; 607 vm->vm_hashlist = newhashlist; 608 vm->vm_hashsize = newhashsize; 609 if (oldhashlist == NULL) { 610 VMEM_UNLOCK(vm); 611 return 0; 612 } 613 for (i = 0; i < oldhashsize; i++) { 614 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 615 bt_rembusy(vm, bt); /* XXX */ 616 bt_insbusy(vm, bt); 617 } 618 } 619 VMEM_UNLOCK(vm); 620 621 xfree(oldhashlist); 622 623 return 0; 624 } 625 626 /* ---- vmem API */ 627 628 /* 629 * vmem_create: create an arena. 630 * 631 * => must not be called from interrupt context. 632 */ 633 634 vmem_t * 635 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 636 vmem_size_t quantum, 637 vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t), 638 void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t), 639 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags) 640 { 641 vmem_t *vm; 642 int i; 643 #if defined(_KERNEL) 644 static ONCE_DECL(control); 645 #endif /* defined(_KERNEL) */ 646 647 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 648 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 649 650 #if defined(_KERNEL) 651 if (RUN_ONCE(&control, vmem_init)) { 652 return NULL; 653 } 654 #endif /* defined(_KERNEL) */ 655 vm = xmalloc(sizeof(*vm), flags); 656 if (vm == NULL) { 657 return NULL; 658 } 659 660 VMEM_LOCK_INIT(vm); 661 vm->vm_name = name; 662 vm->vm_quantum_mask = quantum - 1; 663 vm->vm_quantum_shift = calc_order(quantum); 664 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 665 vm->vm_allocfn = allocfn; 666 vm->vm_freefn = freefn; 667 vm->vm_source = source; 668 vm->vm_nbusytag = 0; 669 #if defined(QCACHE) 670 qc_init(vm, qcache_max); 671 #endif /* defined(QCACHE) */ 672 673 CIRCLEQ_INIT(&vm->vm_seglist); 674 for (i = 0; i < VMEM_MAXORDER; i++) { 675 LIST_INIT(&vm->vm_freelist[i]); 676 } 677 vm->vm_hashlist = NULL; 678 if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) { 679 vmem_destroy(vm); 680 return NULL; 681 } 682 683 if (size != 0) { 684 if (vmem_add(vm, base, size, flags) == 0) { 685 vmem_destroy(vm); 686 return NULL; 687 } 688 } 689 690 return vm; 691 } 692 693 void 694 vmem_destroy(vmem_t *vm) 695 { 696 697 VMEM_ASSERT_UNLOCKED(vm); 698 699 if (vm->vm_hashlist != NULL) { 700 int i; 701 702 for (i = 0; i < vm->vm_hashsize; i++) { 703 bt_t *bt; 704 705 while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) { 706 KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC); 707 bt_free(vm, bt); 708 } 709 } 710 xfree(vm->vm_hashlist); 711 } 712 xfree(vm); 713 } 714 715 vmem_size_t 716 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 717 { 718 719 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 720 } 721 722 /* 723 * vmem_alloc: 724 * 725 * => caller must ensure appropriate spl, 726 * if the arena can be accessed from interrupt context. 727 */ 728 729 vmem_addr_t 730 vmem_alloc(vmem_t *vm, vmem_size_t size0, vm_flag_t flags) 731 { 732 struct vmem_freelist *list; 733 struct vmem_freelist *first; 734 struct vmem_freelist *end; 735 bt_t *bt; 736 bt_t *btnew; 737 const vmem_size_t size = vmem_roundup_size(vm, size0); 738 vm_flag_t strat = flags & VM_FITMASK; 739 740 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 741 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 742 VMEM_ASSERT_UNLOCKED(vm); 743 744 KASSERT(size0 > 0); 745 KASSERT(size > 0); 746 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 747 if ((flags & VM_SLEEP) != 0) { 748 ASSERT_SLEEPABLE(NULL, "vmem_alloc"); 749 } 750 751 #if defined(QCACHE) 752 if (size <= vm->vm_qcache_max) { 753 int qidx = size >> vm->vm_quantum_shift; 754 qcache_t *qc = &vm->vm_qcache[qidx - 1]; 755 756 return (vmem_addr_t)pool_cache_get(&qc->qc_cache, 757 vmf_to_prf(flags)); 758 } 759 #endif /* defined(QCACHE) */ 760 761 btnew = bt_alloc(vm, flags); 762 if (btnew == NULL) { 763 return VMEM_ADDR_NULL; 764 } 765 766 retry_strat: 767 first = bt_freehead_toalloc(vm, size, strat); 768 end = &vm->vm_freelist[VMEM_MAXORDER]; 769 retry: 770 bt = NULL; 771 VMEM_LOCK(vm); 772 if (strat == VM_INSTANTFIT) { 773 for (list = first; list < end; list++) { 774 bt = LIST_FIRST(list); 775 if (bt != NULL) { 776 goto gotit; 777 } 778 } 779 } else { /* VM_BESTFIT */ 780 for (list = first; list < end; list++) { 781 LIST_FOREACH(bt, list, bt_freelist) { 782 if (bt->bt_size >= size) { 783 goto gotit; 784 } 785 } 786 } 787 } 788 VMEM_UNLOCK(vm); 789 #if 1 790 if (strat == VM_INSTANTFIT) { 791 strat = VM_BESTFIT; 792 goto retry_strat; 793 } 794 #endif 795 if (vmem_import(vm, size, flags) == 0) { 796 goto retry; 797 } 798 /* XXX */ 799 return VMEM_ADDR_NULL; 800 801 gotit: 802 KASSERT(bt->bt_type == BT_TYPE_FREE); 803 KASSERT(bt->bt_size >= size); 804 bt_remfree(vm, bt); 805 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 806 /* split */ 807 btnew->bt_type = BT_TYPE_BUSY; 808 btnew->bt_start = bt->bt_start; 809 btnew->bt_size = size; 810 bt->bt_start = bt->bt_start + size; 811 bt->bt_size -= size; 812 bt_insfree(vm, bt); 813 bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist)); 814 bt_insbusy(vm, btnew); 815 VMEM_UNLOCK(vm); 816 } else { 817 bt->bt_type = BT_TYPE_BUSY; 818 bt_insbusy(vm, bt); 819 VMEM_UNLOCK(vm); 820 bt_free(vm, btnew); 821 btnew = bt; 822 } 823 KASSERT(btnew->bt_size >= size); 824 btnew->bt_type = BT_TYPE_BUSY; 825 826 return btnew->bt_start; 827 } 828 829 /* 830 * vmem_free: 831 * 832 * => caller must ensure appropriate spl, 833 * if the arena can be accessed from interrupt context. 834 */ 835 836 void 837 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 838 { 839 bt_t *bt; 840 bt_t *t; 841 842 VMEM_ASSERT_UNLOCKED(vm); 843 844 KASSERT(addr != VMEM_ADDR_NULL); 845 KASSERT(size > 0); 846 847 #if defined(QCACHE) 848 if (size <= vm->vm_qcache_max) { 849 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 850 qcache_t *qc = &vm->vm_qcache[qidx - 1]; 851 852 return pool_cache_put(&qc->qc_cache, (void *)addr); 853 } 854 #endif /* defined(QCACHE) */ 855 856 VMEM_LOCK(vm); 857 858 bt = bt_lookupbusy(vm, addr); 859 KASSERT(bt != NULL); 860 KASSERT(bt->bt_start == addr); 861 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 862 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 863 KASSERT(bt->bt_type == BT_TYPE_BUSY); 864 bt_rembusy(vm, bt); 865 bt->bt_type = BT_TYPE_FREE; 866 867 /* coalesce */ 868 t = CIRCLEQ_NEXT(bt, bt_seglist); 869 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 870 KASSERT(BT_END(bt) == t->bt_start); 871 bt_remfree(vm, t); 872 bt_remseg(vm, t); 873 bt->bt_size += t->bt_size; 874 bt_free(vm, t); 875 } 876 t = CIRCLEQ_PREV(bt, bt_seglist); 877 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 878 KASSERT(BT_END(t) == bt->bt_start); 879 bt_remfree(vm, t); 880 bt_remseg(vm, t); 881 bt->bt_size += t->bt_size; 882 bt->bt_start = t->bt_start; 883 bt_free(vm, t); 884 } 885 886 t = CIRCLEQ_PREV(bt, bt_seglist); 887 KASSERT(t != NULL); 888 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 889 if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN && 890 t->bt_size == bt->bt_size) { 891 vmem_addr_t spanaddr; 892 vmem_size_t spansize; 893 894 KASSERT(t->bt_start == bt->bt_start); 895 spanaddr = bt->bt_start; 896 spansize = bt->bt_size; 897 bt_remseg(vm, bt); 898 bt_free(vm, bt); 899 bt_remseg(vm, t); 900 bt_free(vm, t); 901 VMEM_UNLOCK(vm); 902 (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize); 903 } else { 904 bt_insfree(vm, bt); 905 VMEM_UNLOCK(vm); 906 } 907 } 908 909 /* 910 * vmem_add: 911 * 912 * => caller must ensure appropriate spl, 913 * if the arena can be accessed from interrupt context. 914 */ 915 916 vmem_addr_t 917 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 918 { 919 920 return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 921 } 922 923 /* 924 * vmem_reap: reap unused resources. 925 * 926 * => return TRUE if we successfully reaped something. 927 */ 928 929 boolean_t 930 vmem_reap(vmem_t *vm) 931 { 932 boolean_t didsomething = FALSE; 933 934 VMEM_ASSERT_UNLOCKED(vm); 935 936 #if defined(QCACHE) 937 didsomething = qc_reap(vm); 938 #endif /* defined(QCACHE) */ 939 return didsomething; 940 } 941 942 /* ---- debug */ 943 944 #if defined(VMEM_DEBUG) 945 946 #if !defined(_KERNEL) 947 #include <stdio.h> 948 #endif /* !defined(_KERNEL) */ 949 950 void bt_dump(const bt_t *); 951 952 void 953 bt_dump(const bt_t *bt) 954 { 955 956 printf("\t%p: %" PRIu64 ", %" PRIu64 ", %d\n", 957 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 958 bt->bt_type); 959 } 960 961 void 962 vmem_dump(const vmem_t *vm) 963 { 964 const bt_t *bt; 965 int i; 966 967 printf("vmem %p '%s'\n", vm, vm->vm_name); 968 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 969 bt_dump(bt); 970 } 971 972 for (i = 0; i < VMEM_MAXORDER; i++) { 973 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 974 975 if (LIST_EMPTY(fl)) { 976 continue; 977 } 978 979 printf("freelist[%d]\n", i); 980 LIST_FOREACH(bt, fl, bt_freelist) { 981 bt_dump(bt); 982 if (bt->bt_size) { 983 } 984 } 985 } 986 } 987 988 #if !defined(_KERNEL) 989 990 #include <stdlib.h> 991 992 int 993 main() 994 { 995 vmem_t *vm; 996 vmem_addr_t p; 997 struct reg { 998 vmem_addr_t p; 999 vmem_size_t sz; 1000 } *reg = NULL; 1001 int nreg = 0; 1002 int nalloc = 0; 1003 int nfree = 0; 1004 vmem_size_t total = 0; 1005 #if 1 1006 vm_flag_t strat = VM_INSTANTFIT; 1007 #else 1008 vm_flag_t strat = VM_BESTFIT; 1009 #endif 1010 1011 vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1, 1012 NULL, NULL, NULL, 0, VM_NOSLEEP); 1013 if (vm == NULL) { 1014 printf("vmem_create\n"); 1015 exit(EXIT_FAILURE); 1016 } 1017 vmem_dump(vm); 1018 1019 p = vmem_add(vm, 100, 200, VM_SLEEP); 1020 p = vmem_add(vm, 2000, 1, VM_SLEEP); 1021 p = vmem_add(vm, 40000, 0x10000000>>12, VM_SLEEP); 1022 p = vmem_add(vm, 10000, 10000, VM_SLEEP); 1023 p = vmem_add(vm, 500, 1000, VM_SLEEP); 1024 vmem_dump(vm); 1025 for (;;) { 1026 struct reg *r; 1027 1028 if (rand() % 100 > 40) { 1029 vmem_size_t sz = rand() % 500 + 1; 1030 1031 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 1032 p = vmem_alloc(vm, sz, strat|VM_SLEEP); 1033 printf("-> %" PRIu64 "\n", (uint64_t)p); 1034 vmem_dump(vm); 1035 if (p == VMEM_ADDR_NULL) { 1036 break; 1037 } 1038 nreg++; 1039 reg = realloc(reg, sizeof(*reg) * nreg); 1040 r = ®[nreg - 1]; 1041 r->p = p; 1042 r->sz = sz; 1043 total += sz; 1044 nalloc++; 1045 } else if (nreg != 0) { 1046 r = ®[rand() % nreg]; 1047 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1048 (uint64_t)r->p, (uint64_t)r->sz); 1049 vmem_free(vm, r->p, r->sz); 1050 total -= r->sz; 1051 vmem_dump(vm); 1052 *r = reg[nreg - 1]; 1053 nreg--; 1054 nfree++; 1055 } 1056 printf("total=%" PRIu64 "\n", (uint64_t)total); 1057 } 1058 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1059 (uint64_t)total, nalloc, nfree); 1060 exit(EXIT_SUCCESS); 1061 } 1062 #endif /* !defined(_KERNEL) */ 1063 #endif /* defined(VMEM_DEBUG) */ 1064
Indexes created Wed Sep 24 05:09:52 GMT 2025