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