subr_vmem.c revision 1.5
1 /* $NetBSD: subr_vmem.c,v 1.5 2006/08/20 09:43:08 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.5 2006/08/20 09:43:08 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 #endif /* defined(QCACHE) */ 491 492 #if defined(_KERNEL) 493 static int 494 vmem_init(void) 495 { 496 497 pool_cache_init(&bt_poolcache, &bt_pool, NULL, NULL, NULL); 498 return 0; 499 } 500 #endif /* defined(_KERNEL) */ 501 502 static vmem_addr_t 503 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 504 int spanbttype) 505 { 506 bt_t *btspan; 507 bt_t *btfree; 508 509 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 510 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 511 VMEM_ASSERT_UNLOCKED(vm); 512 513 btspan = bt_alloc(vm, flags); 514 if (btspan == NULL) { 515 return VMEM_ADDR_NULL; 516 } 517 btfree = bt_alloc(vm, flags); 518 if (btfree == NULL) { 519 bt_free(vm, btspan); 520 return VMEM_ADDR_NULL; 521 } 522 523 btspan->bt_type = spanbttype; 524 btspan->bt_start = addr; 525 btspan->bt_size = size; 526 527 btfree->bt_type = BT_TYPE_FREE; 528 btfree->bt_start = addr; 529 btfree->bt_size = size; 530 531 VMEM_LOCK(vm); 532 bt_insseg_tail(vm, btspan); 533 bt_insseg(vm, btfree, btspan); 534 bt_insfree(vm, btfree); 535 VMEM_UNLOCK(vm); 536 537 return addr; 538 } 539 540 static int 541 vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 542 { 543 vmem_addr_t addr; 544 545 VMEM_ASSERT_UNLOCKED(vm); 546 547 if (vm->vm_allocfn == NULL) { 548 return EINVAL; 549 } 550 551 addr = (*vm->vm_allocfn)(vm->vm_source, size, &size, flags); 552 if (addr == VMEM_ADDR_NULL) { 553 return ENOMEM; 554 } 555 556 if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) == VMEM_ADDR_NULL) { 557 (*vm->vm_freefn)(vm->vm_source, addr, size); 558 return ENOMEM; 559 } 560 561 return 0; 562 } 563 564 static int 565 vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags) 566 { 567 bt_t *bt; 568 int i; 569 struct vmem_hashlist *newhashlist; 570 struct vmem_hashlist *oldhashlist; 571 size_t oldhashsize; 572 573 KASSERT(newhashsize > 0); 574 VMEM_ASSERT_UNLOCKED(vm); 575 576 newhashlist = 577 xmalloc(sizeof(struct vmem_hashlist *) * newhashsize, flags); 578 if (newhashlist == NULL) { 579 return ENOMEM; 580 } 581 for (i = 0; i < newhashsize; i++) { 582 LIST_INIT(&newhashlist[i]); 583 } 584 585 VMEM_LOCK(vm); 586 oldhashlist = vm->vm_hashlist; 587 oldhashsize = vm->vm_hashsize; 588 vm->vm_hashlist = newhashlist; 589 vm->vm_hashsize = newhashsize; 590 if (oldhashlist == NULL) { 591 VMEM_UNLOCK(vm); 592 return 0; 593 } 594 for (i = 0; i < oldhashsize; i++) { 595 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 596 bt_rembusy(vm, bt); /* XXX */ 597 bt_insbusy(vm, bt); 598 } 599 } 600 VMEM_UNLOCK(vm); 601 602 xfree(oldhashlist); 603 604 return 0; 605 } 606 607 /* ---- vmem API */ 608 609 /* 610 * vmem_create: create an arena. 611 * 612 * => must not be called from interrupt context. 613 */ 614 615 vmem_t * 616 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 617 vmem_size_t quantum, 618 vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t), 619 void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t), 620 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags) 621 { 622 vmem_t *vm; 623 int i; 624 #if defined(_KERNEL) 625 static ONCE_DECL(control); 626 #endif /* defined(_KERNEL) */ 627 628 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 629 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 630 631 #if defined(_KERNEL) 632 if (RUN_ONCE(&control, vmem_init)) { 633 return NULL; 634 } 635 #endif /* defined(_KERNEL) */ 636 vm = xmalloc(sizeof(*vm), flags); 637 if (vm == NULL) { 638 return NULL; 639 } 640 641 VMEM_LOCK_INIT(vm); 642 vm->vm_name = name; 643 vm->vm_quantum_mask = quantum - 1; 644 vm->vm_quantum_shift = calc_order(quantum); 645 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 646 vm->vm_allocfn = allocfn; 647 vm->vm_freefn = freefn; 648 vm->vm_source = source; 649 vm->vm_nbusytag = 0; 650 #if defined(QCACHE) 651 qc_init(vm, qcache_max); 652 #endif /* defined(QCACHE) */ 653 654 CIRCLEQ_INIT(&vm->vm_seglist); 655 for (i = 0; i < VMEM_MAXORDER; i++) { 656 LIST_INIT(&vm->vm_freelist[i]); 657 } 658 vm->vm_hashlist = NULL; 659 if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) { 660 vmem_destroy(vm); 661 return NULL; 662 } 663 664 if (size != 0) { 665 if (vmem_add(vm, base, size, flags) == 0) { 666 vmem_destroy(vm); 667 return NULL; 668 } 669 } 670 671 return vm; 672 } 673 674 void 675 vmem_destroy(vmem_t *vm) 676 { 677 678 VMEM_ASSERT_UNLOCKED(vm); 679 680 if (vm->vm_hashlist != NULL) { 681 int i; 682 683 for (i = 0; i < vm->vm_hashsize; i++) { 684 bt_t *bt; 685 686 while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) { 687 KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC); 688 bt_free(vm, bt); 689 } 690 } 691 xfree(vm->vm_hashlist); 692 } 693 xfree(vm); 694 } 695 696 vmem_size_t 697 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 698 { 699 700 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 701 } 702 703 /* 704 * vmem_alloc: 705 * 706 * => caller must ensure appropriate spl, 707 * if the arena can be accessed from interrupt context. 708 */ 709 710 vmem_addr_t 711 vmem_alloc(vmem_t *vm, vmem_size_t size0, vm_flag_t flags) 712 { 713 struct vmem_freelist *list; 714 struct vmem_freelist *first; 715 struct vmem_freelist *end; 716 bt_t *bt; 717 bt_t *btnew; 718 const vmem_size_t size = vmem_roundup_size(vm, size0); 719 vm_flag_t strat = flags & VM_FITMASK; 720 721 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 722 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 723 VMEM_ASSERT_UNLOCKED(vm); 724 725 KASSERT(size0 > 0); 726 KASSERT(size > 0); 727 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 728 if ((flags & VM_SLEEP) != 0) { 729 ASSERT_SLEEPABLE(NULL, "vmem_alloc"); 730 } 731 732 #if defined(QCACHE) 733 if (size <= vm->vm_qcache_max) { 734 int qidx = size >> vm->vm_quantum_shift; 735 qcache_t *qc = &vm->vm_qcache[qidx - 1]; 736 737 return (vmem_addr_t)pool_cache_get(&qc->qc_cache, 738 vmf_to_prf(flags)); 739 } 740 #endif /* defined(QCACHE) */ 741 742 btnew = bt_alloc(vm, flags); 743 if (btnew == NULL) { 744 return VMEM_ADDR_NULL; 745 } 746 747 retry_strat: 748 first = bt_freehead_toalloc(vm, size, strat); 749 end = &vm->vm_freelist[VMEM_MAXORDER]; 750 retry: 751 bt = NULL; 752 VMEM_LOCK(vm); 753 if (strat == VM_INSTANTFIT) { 754 for (list = first; list < end; list++) { 755 bt = LIST_FIRST(list); 756 if (bt != NULL) { 757 goto gotit; 758 } 759 } 760 } else { /* VM_BESTFIT */ 761 for (list = first; list < end; list++) { 762 LIST_FOREACH(bt, list, bt_freelist) { 763 if (bt->bt_size >= size) { 764 goto gotit; 765 } 766 } 767 } 768 } 769 VMEM_UNLOCK(vm); 770 #if 1 771 if (strat == VM_INSTANTFIT) { 772 strat = VM_BESTFIT; 773 goto retry_strat; 774 } 775 #endif 776 if (vmem_import(vm, size, flags) == 0) { 777 goto retry; 778 } 779 /* XXX */ 780 return VMEM_ADDR_NULL; 781 782 gotit: 783 KASSERT(bt->bt_type == BT_TYPE_FREE); 784 KASSERT(bt->bt_size >= size); 785 bt_remfree(vm, bt); 786 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 787 /* split */ 788 btnew->bt_type = BT_TYPE_BUSY; 789 btnew->bt_start = bt->bt_start; 790 btnew->bt_size = size; 791 bt->bt_start = bt->bt_start + size; 792 bt->bt_size -= size; 793 bt_insfree(vm, bt); 794 bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist)); 795 bt_insbusy(vm, btnew); 796 VMEM_UNLOCK(vm); 797 } else { 798 bt->bt_type = BT_TYPE_BUSY; 799 bt_insbusy(vm, bt); 800 VMEM_UNLOCK(vm); 801 bt_free(vm, btnew); 802 btnew = bt; 803 } 804 KASSERT(btnew->bt_size >= size); 805 btnew->bt_type = BT_TYPE_BUSY; 806 807 return btnew->bt_start; 808 } 809 810 /* 811 * vmem_free: 812 * 813 * => caller must ensure appropriate spl, 814 * if the arena can be accessed from interrupt context. 815 */ 816 817 void 818 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 819 { 820 bt_t *bt; 821 bt_t *t; 822 823 VMEM_ASSERT_UNLOCKED(vm); 824 825 KASSERT(addr != VMEM_ADDR_NULL); 826 KASSERT(size > 0); 827 828 #if defined(QCACHE) 829 if (size <= vm->vm_qcache_max) { 830 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 831 qcache_t *qc = &vm->vm_qcache[qidx - 1]; 832 833 return pool_cache_put(&qc->qc_cache, (void *)addr); 834 } 835 #endif /* defined(QCACHE) */ 836 837 VMEM_LOCK(vm); 838 839 bt = bt_lookupbusy(vm, addr); 840 KASSERT(bt != NULL); 841 KASSERT(bt->bt_start == addr); 842 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 843 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 844 KASSERT(bt->bt_type == BT_TYPE_BUSY); 845 bt_rembusy(vm, bt); 846 bt->bt_type = BT_TYPE_FREE; 847 848 /* coalesce */ 849 t = CIRCLEQ_NEXT(bt, bt_seglist); 850 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 851 KASSERT(BT_END(bt) == t->bt_start); 852 bt_remfree(vm, t); 853 bt_remseg(vm, t); 854 bt->bt_size += t->bt_size; 855 bt_free(vm, t); 856 } 857 t = CIRCLEQ_PREV(bt, bt_seglist); 858 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 859 KASSERT(BT_END(t) == bt->bt_start); 860 bt_remfree(vm, t); 861 bt_remseg(vm, t); 862 bt->bt_size += t->bt_size; 863 bt->bt_start = t->bt_start; 864 bt_free(vm, t); 865 } 866 867 t = CIRCLEQ_PREV(bt, bt_seglist); 868 KASSERT(t != NULL); 869 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 870 if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN && 871 t->bt_size == bt->bt_size) { 872 vmem_addr_t spanaddr; 873 vmem_size_t spansize; 874 875 KASSERT(t->bt_start == bt->bt_start); 876 spanaddr = bt->bt_start; 877 spansize = bt->bt_size; 878 bt_remseg(vm, bt); 879 bt_free(vm, bt); 880 bt_remseg(vm, t); 881 bt_free(vm, t); 882 VMEM_UNLOCK(vm); 883 (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize); 884 } else { 885 bt_insfree(vm, bt); 886 VMEM_UNLOCK(vm); 887 } 888 } 889 890 /* 891 * vmem_add: 892 * 893 * => caller must ensure appropriate spl, 894 * if the arena can be accessed from interrupt context. 895 */ 896 897 vmem_addr_t 898 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 899 { 900 901 return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 902 } 903 904 /* ---- debug */ 905 906 #if defined(VMEM_DEBUG) 907 908 #if !defined(_KERNEL) 909 #include <stdio.h> 910 #endif /* !defined(_KERNEL) */ 911 912 void bt_dump(const bt_t *); 913 914 void 915 bt_dump(const bt_t *bt) 916 { 917 918 printf("\t%p: %" PRIu64 ", %" PRIu64 ", %d\n", 919 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 920 bt->bt_type); 921 } 922 923 void 924 vmem_dump(const vmem_t *vm) 925 { 926 const bt_t *bt; 927 int i; 928 929 printf("vmem %p '%s'\n", vm, vm->vm_name); 930 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 931 bt_dump(bt); 932 } 933 934 for (i = 0; i < VMEM_MAXORDER; i++) { 935 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 936 937 if (LIST_EMPTY(fl)) { 938 continue; 939 } 940 941 printf("freelist[%d]\n", i); 942 LIST_FOREACH(bt, fl, bt_freelist) { 943 bt_dump(bt); 944 if (bt->bt_size) { 945 } 946 } 947 } 948 } 949 950 #if !defined(_KERNEL) 951 952 #include <stdlib.h> 953 954 int 955 main() 956 { 957 vmem_t *vm; 958 vmem_addr_t p; 959 struct reg { 960 vmem_addr_t p; 961 vmem_size_t sz; 962 } *reg = NULL; 963 int nreg = 0; 964 int nalloc = 0; 965 int nfree = 0; 966 vmem_size_t total = 0; 967 #if 1 968 vm_flag_t strat = VM_INSTANTFIT; 969 #else 970 vm_flag_t strat = VM_BESTFIT; 971 #endif 972 973 vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1, 974 NULL, NULL, NULL, 0, VM_NOSLEEP); 975 if (vm == NULL) { 976 printf("vmem_create\n"); 977 exit(EXIT_FAILURE); 978 } 979 vmem_dump(vm); 980 981 p = vmem_add(vm, 100, 200, VM_SLEEP); 982 p = vmem_add(vm, 2000, 1, VM_SLEEP); 983 p = vmem_add(vm, 40000, 0x10000000>>12, VM_SLEEP); 984 p = vmem_add(vm, 10000, 10000, VM_SLEEP); 985 p = vmem_add(vm, 500, 1000, VM_SLEEP); 986 vmem_dump(vm); 987 for (;;) { 988 struct reg *r; 989 990 if (rand() % 100 > 40) { 991 vmem_size_t sz = rand() % 500 + 1; 992 993 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 994 p = vmem_alloc(vm, sz, strat|VM_SLEEP); 995 printf("-> %" PRIu64 "\n", (uint64_t)p); 996 vmem_dump(vm); 997 if (p == VMEM_ADDR_NULL) { 998 break; 999 } 1000 nreg++; 1001 reg = realloc(reg, sizeof(*reg) * nreg); 1002 r = ®[nreg - 1]; 1003 r->p = p; 1004 r->sz = sz; 1005 total += sz; 1006 nalloc++; 1007 } else if (nreg != 0) { 1008 r = ®[rand() % nreg]; 1009 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1010 (uint64_t)r->p, (uint64_t)r->sz); 1011 vmem_free(vm, r->p, r->sz); 1012 total -= r->sz; 1013 vmem_dump(vm); 1014 *r = reg[nreg - 1]; 1015 nreg--; 1016 nfree++; 1017 } 1018 printf("total=%" PRIu64 "\n", (uint64_t)total); 1019 } 1020 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1021 (uint64_t)total, nalloc, nfree); 1022 exit(EXIT_SUCCESS); 1023 } 1024 #endif /* !defined(_KERNEL) */ 1025 #endif /* defined(VMEM_DEBUG) */ 1026
Indexes created Sun Sep 21 20:09:37 GMT 2025