subr_vmem.c revision 1.29
1 /* $NetBSD: subr_vmem.c,v 1.29 2007/03/26 22:52:44 hubertf 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.29 2007/03/26 22:52:44 hubertf 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, IPL_VM); 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 IPL_NONE); 496 if (prevqc != NULL && 497 qc->qc_pool.pr_itemsperpage == 498 prevqc->qc_pool.pr_itemsperpage) { 499 pool_destroy(&qc->qc_pool); 500 vm->vm_qcache[i - 1] = prevqc; 501 continue; 502 } 503 pool_cache_init(&qc->qc_cache, &qc->qc_pool, NULL, NULL, NULL); 504 vm->vm_qcache[i - 1] = qc; 505 prevqc = qc; 506 } 507 } 508 509 static void 510 qc_destroy(vmem_t *vm) 511 { 512 const qcache_t *prevqc; 513 int i; 514 int qcache_idx_max; 515 516 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 517 prevqc = NULL; 518 for (i = 0; i < qcache_idx_max; i++) { 519 qcache_t *qc = vm->vm_qcache[i]; 520 521 if (prevqc == qc) { 522 continue; 523 } 524 pool_cache_destroy(&qc->qc_cache); 525 pool_destroy(&qc->qc_pool); 526 prevqc = qc; 527 } 528 } 529 530 static bool 531 qc_reap(vmem_t *vm) 532 { 533 const qcache_t *prevqc; 534 int i; 535 int qcache_idx_max; 536 bool didsomething = false; 537 538 qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift; 539 prevqc = NULL; 540 for (i = 0; i < qcache_idx_max; i++) { 541 qcache_t *qc = vm->vm_qcache[i]; 542 543 if (prevqc == qc) { 544 continue; 545 } 546 if (pool_reclaim(&qc->qc_pool) != 0) { 547 didsomething = true; 548 } 549 prevqc = qc; 550 } 551 552 return didsomething; 553 } 554 #endif /* defined(QCACHE) */ 555 556 #if defined(_KERNEL) 557 static int 558 vmem_init(void) 559 { 560 561 pool_cache_init(&bt_poolcache, &bt_pool, NULL, NULL, NULL); 562 return 0; 563 } 564 #endif /* defined(_KERNEL) */ 565 566 static vmem_addr_t 567 vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags, 568 int spanbttype) 569 { 570 bt_t *btspan; 571 bt_t *btfree; 572 573 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 574 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 575 VMEM_ASSERT_UNLOCKED(vm); 576 577 btspan = bt_alloc(vm, flags); 578 if (btspan == NULL) { 579 return VMEM_ADDR_NULL; 580 } 581 btfree = bt_alloc(vm, flags); 582 if (btfree == NULL) { 583 bt_free(vm, btspan); 584 return VMEM_ADDR_NULL; 585 } 586 587 btspan->bt_type = spanbttype; 588 btspan->bt_start = addr; 589 btspan->bt_size = size; 590 591 btfree->bt_type = BT_TYPE_FREE; 592 btfree->bt_start = addr; 593 btfree->bt_size = size; 594 595 VMEM_LOCK(vm); 596 bt_insseg_tail(vm, btspan); 597 bt_insseg(vm, btfree, btspan); 598 bt_insfree(vm, btfree); 599 VMEM_UNLOCK(vm); 600 601 return addr; 602 } 603 604 static int 605 vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags) 606 { 607 vmem_addr_t addr; 608 609 VMEM_ASSERT_UNLOCKED(vm); 610 611 if (vm->vm_allocfn == NULL) { 612 return EINVAL; 613 } 614 615 addr = (*vm->vm_allocfn)(vm->vm_source, size, &size, flags); 616 if (addr == VMEM_ADDR_NULL) { 617 return ENOMEM; 618 } 619 620 if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) == VMEM_ADDR_NULL) { 621 (*vm->vm_freefn)(vm->vm_source, addr, size); 622 return ENOMEM; 623 } 624 625 return 0; 626 } 627 628 static int 629 vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags) 630 { 631 bt_t *bt; 632 int i; 633 struct vmem_hashlist *newhashlist; 634 struct vmem_hashlist *oldhashlist; 635 size_t oldhashsize; 636 637 KASSERT(newhashsize > 0); 638 VMEM_ASSERT_UNLOCKED(vm); 639 640 newhashlist = 641 xmalloc(sizeof(struct vmem_hashlist *) * newhashsize, flags); 642 if (newhashlist == NULL) { 643 return ENOMEM; 644 } 645 for (i = 0; i < newhashsize; i++) { 646 LIST_INIT(&newhashlist[i]); 647 } 648 649 VMEM_LOCK(vm); 650 oldhashlist = vm->vm_hashlist; 651 oldhashsize = vm->vm_hashsize; 652 vm->vm_hashlist = newhashlist; 653 vm->vm_hashsize = newhashsize; 654 if (oldhashlist == NULL) { 655 VMEM_UNLOCK(vm); 656 return 0; 657 } 658 for (i = 0; i < oldhashsize; i++) { 659 while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) { 660 bt_rembusy(vm, bt); /* XXX */ 661 bt_insbusy(vm, bt); 662 } 663 } 664 VMEM_UNLOCK(vm); 665 666 xfree(oldhashlist); 667 668 return 0; 669 } 670 671 /* 672 * vmem_fit: check if a bt can satisfy the given restrictions. 673 */ 674 675 static vmem_addr_t 676 vmem_fit(const bt_t *bt, vmem_size_t size, vmem_size_t align, vmem_size_t phase, 677 vmem_size_t nocross, vmem_addr_t minaddr, vmem_addr_t maxaddr) 678 { 679 vmem_addr_t start; 680 vmem_addr_t end; 681 682 KASSERT(bt->bt_size >= size); 683 684 /* 685 * XXX assumption: vmem_addr_t and vmem_size_t are 686 * unsigned integer of the same size. 687 */ 688 689 start = bt->bt_start; 690 if (start < minaddr) { 691 start = minaddr; 692 } 693 end = BT_END(bt); 694 if (end > maxaddr - 1) { 695 end = maxaddr - 1; 696 } 697 if (start >= end) { 698 return VMEM_ADDR_NULL; 699 } 700 701 start = VMEM_ALIGNUP(start - phase, align) + phase; 702 if (start < bt->bt_start) { 703 start += align; 704 } 705 if (VMEM_CROSS_P(start, start + size - 1, nocross)) { 706 KASSERT(align < nocross); 707 start = VMEM_ALIGNUP(start - phase, nocross) + phase; 708 } 709 if (start < end && end - start >= size) { 710 KASSERT((start & (align - 1)) == phase); 711 KASSERT(!VMEM_CROSS_P(start, start + size - 1, nocross)); 712 KASSERT(minaddr <= start); 713 KASSERT(maxaddr == 0 || start + size <= maxaddr); 714 KASSERT(bt->bt_start <= start); 715 KASSERT(start + size <= BT_END(bt)); 716 return start; 717 } 718 return VMEM_ADDR_NULL; 719 } 720 721 /* ---- vmem API */ 722 723 /* 724 * vmem_create: create an arena. 725 * 726 * => must not be called from interrupt context. 727 */ 728 729 vmem_t * 730 vmem_create(const char *name, vmem_addr_t base, vmem_size_t size, 731 vmem_size_t quantum, 732 vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t), 733 void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t), 734 vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags) 735 { 736 vmem_t *vm; 737 int i; 738 #if defined(_KERNEL) 739 static ONCE_DECL(control); 740 #endif /* defined(_KERNEL) */ 741 742 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 743 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 744 745 #if defined(_KERNEL) 746 if (RUN_ONCE(&control, vmem_init)) { 747 return NULL; 748 } 749 #endif /* defined(_KERNEL) */ 750 vm = xmalloc(sizeof(*vm), flags); 751 if (vm == NULL) { 752 return NULL; 753 } 754 755 VMEM_LOCK_INIT(vm); 756 vm->vm_name = name; 757 vm->vm_quantum_mask = quantum - 1; 758 vm->vm_quantum_shift = calc_order(quantum); 759 KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum); 760 vm->vm_allocfn = allocfn; 761 vm->vm_freefn = freefn; 762 vm->vm_source = source; 763 vm->vm_nbusytag = 0; 764 #if defined(QCACHE) 765 qc_init(vm, qcache_max); 766 #endif /* defined(QCACHE) */ 767 768 CIRCLEQ_INIT(&vm->vm_seglist); 769 for (i = 0; i < VMEM_MAXORDER; i++) { 770 LIST_INIT(&vm->vm_freelist[i]); 771 } 772 vm->vm_hashlist = NULL; 773 if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) { 774 vmem_destroy(vm); 775 return NULL; 776 } 777 778 if (size != 0) { 779 if (vmem_add(vm, base, size, flags) == 0) { 780 vmem_destroy(vm); 781 return NULL; 782 } 783 } 784 785 return vm; 786 } 787 788 void 789 vmem_destroy(vmem_t *vm) 790 { 791 792 VMEM_ASSERT_UNLOCKED(vm); 793 794 #if defined(QCACHE) 795 qc_destroy(vm); 796 #endif /* defined(QCACHE) */ 797 if (vm->vm_hashlist != NULL) { 798 int i; 799 800 for (i = 0; i < vm->vm_hashsize; i++) { 801 bt_t *bt; 802 803 while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) { 804 KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC); 805 bt_free(vm, bt); 806 } 807 } 808 xfree(vm->vm_hashlist); 809 } 810 xfree(vm); 811 } 812 813 vmem_size_t 814 vmem_roundup_size(vmem_t *vm, vmem_size_t size) 815 { 816 817 return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask; 818 } 819 820 /* 821 * vmem_alloc: 822 * 823 * => caller must ensure appropriate spl, 824 * if the arena can be accessed from interrupt context. 825 */ 826 827 vmem_addr_t 828 vmem_alloc(vmem_t *vm, vmem_size_t size0, vm_flag_t flags) 829 { 830 const vmem_size_t size __unused = vmem_roundup_size(vm, size0); 831 const vm_flag_t strat __unused = flags & VM_FITMASK; 832 833 KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 834 KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0); 835 VMEM_ASSERT_UNLOCKED(vm); 836 837 KASSERT(size0 > 0); 838 KASSERT(size > 0); 839 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 840 if ((flags & VM_SLEEP) != 0) { 841 ASSERT_SLEEPABLE(NULL, __func__); 842 } 843 844 #if defined(QCACHE) 845 if (size <= vm->vm_qcache_max) { 846 int qidx = size >> vm->vm_quantum_shift; 847 qcache_t *qc = vm->vm_qcache[qidx - 1]; 848 849 return (vmem_addr_t)pool_cache_get(&qc->qc_cache, 850 vmf_to_prf(flags)); 851 } 852 #endif /* defined(QCACHE) */ 853 854 return vmem_xalloc(vm, size0, 0, 0, 0, 0, 0, flags); 855 } 856 857 vmem_addr_t 858 vmem_xalloc(vmem_t *vm, vmem_size_t size0, vmem_size_t align, vmem_size_t phase, 859 vmem_size_t nocross, vmem_addr_t minaddr, vmem_addr_t maxaddr, 860 vm_flag_t flags) 861 { 862 struct vmem_freelist *list; 863 struct vmem_freelist *first; 864 struct vmem_freelist *end; 865 bt_t *bt; 866 bt_t *btnew; 867 bt_t *btnew2; 868 const vmem_size_t size = vmem_roundup_size(vm, size0); 869 vm_flag_t strat = flags & VM_FITMASK; 870 vmem_addr_t start; 871 872 KASSERT(size0 > 0); 873 KASSERT(size > 0); 874 KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT); 875 if ((flags & VM_SLEEP) != 0) { 876 ASSERT_SLEEPABLE(NULL, __func__); 877 } 878 KASSERT((align & vm->vm_quantum_mask) == 0); 879 KASSERT((align & (align - 1)) == 0); 880 KASSERT((phase & vm->vm_quantum_mask) == 0); 881 KASSERT((nocross & vm->vm_quantum_mask) == 0); 882 KASSERT((nocross & (nocross - 1)) == 0); 883 KASSERT((align == 0 && phase == 0) || phase < align); 884 KASSERT(nocross == 0 || nocross >= size); 885 KASSERT(maxaddr == 0 || minaddr < maxaddr); 886 KASSERT(!VMEM_CROSS_P(phase, phase + size - 1, nocross)); 887 888 if (align == 0) { 889 align = vm->vm_quantum_mask + 1; 890 } 891 btnew = bt_alloc(vm, flags); 892 if (btnew == NULL) { 893 return VMEM_ADDR_NULL; 894 } 895 btnew2 = bt_alloc(vm, flags); /* XXX not necessary if no restrictions */ 896 if (btnew2 == NULL) { 897 bt_free(vm, btnew); 898 return VMEM_ADDR_NULL; 899 } 900 901 retry_strat: 902 first = bt_freehead_toalloc(vm, size, strat); 903 end = &vm->vm_freelist[VMEM_MAXORDER]; 904 retry: 905 bt = NULL; 906 VMEM_LOCK(vm); 907 if (strat == VM_INSTANTFIT) { 908 for (list = first; list < end; list++) { 909 bt = LIST_FIRST(list); 910 if (bt != NULL) { 911 start = vmem_fit(bt, size, align, phase, 912 nocross, minaddr, maxaddr); 913 if (start != VMEM_ADDR_NULL) { 914 goto gotit; 915 } 916 } 917 } 918 } else { /* VM_BESTFIT */ 919 for (list = first; list < end; list++) { 920 LIST_FOREACH(bt, list, bt_freelist) { 921 if (bt->bt_size >= size) { 922 start = vmem_fit(bt, size, align, phase, 923 nocross, minaddr, maxaddr); 924 if (start != VMEM_ADDR_NULL) { 925 goto gotit; 926 } 927 } 928 } 929 } 930 } 931 VMEM_UNLOCK(vm); 932 #if 1 933 if (strat == VM_INSTANTFIT) { 934 strat = VM_BESTFIT; 935 goto retry_strat; 936 } 937 #endif 938 if (align != vm->vm_quantum_mask + 1 || phase != 0 || 939 nocross != 0 || minaddr != 0 || maxaddr != 0) { 940 941 /* 942 * XXX should try to import a region large enough to 943 * satisfy restrictions? 944 */ 945 946 goto fail; 947 } 948 if (vmem_import(vm, size, flags) == 0) { 949 goto retry; 950 } 951 /* XXX */ 952 fail: 953 bt_free(vm, btnew); 954 bt_free(vm, btnew2); 955 return VMEM_ADDR_NULL; 956 957 gotit: 958 KASSERT(bt->bt_type == BT_TYPE_FREE); 959 KASSERT(bt->bt_size >= size); 960 bt_remfree(vm, bt); 961 if (bt->bt_start != start) { 962 btnew2->bt_type = BT_TYPE_FREE; 963 btnew2->bt_start = bt->bt_start; 964 btnew2->bt_size = start - bt->bt_start; 965 bt->bt_start = start; 966 bt->bt_size -= btnew2->bt_size; 967 bt_insfree(vm, btnew2); 968 bt_insseg(vm, btnew2, CIRCLEQ_PREV(bt, bt_seglist)); 969 btnew2 = NULL; 970 } 971 KASSERT(bt->bt_start == start); 972 if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) { 973 /* split */ 974 btnew->bt_type = BT_TYPE_BUSY; 975 btnew->bt_start = bt->bt_start; 976 btnew->bt_size = size; 977 bt->bt_start = bt->bt_start + size; 978 bt->bt_size -= size; 979 bt_insfree(vm, bt); 980 bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist)); 981 bt_insbusy(vm, btnew); 982 VMEM_UNLOCK(vm); 983 } else { 984 bt->bt_type = BT_TYPE_BUSY; 985 bt_insbusy(vm, bt); 986 VMEM_UNLOCK(vm); 987 bt_free(vm, btnew); 988 btnew = bt; 989 } 990 if (btnew2 != NULL) { 991 bt_free(vm, btnew2); 992 } 993 KASSERT(btnew->bt_size >= size); 994 btnew->bt_type = BT_TYPE_BUSY; 995 996 return btnew->bt_start; 997 } 998 999 /* 1000 * vmem_free: 1001 * 1002 * => caller must ensure appropriate spl, 1003 * if the arena can be accessed from interrupt context. 1004 */ 1005 1006 void 1007 vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1008 { 1009 1010 VMEM_ASSERT_UNLOCKED(vm); 1011 KASSERT(addr != VMEM_ADDR_NULL); 1012 KASSERT(size > 0); 1013 1014 #if defined(QCACHE) 1015 if (size <= vm->vm_qcache_max) { 1016 int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift; 1017 qcache_t *qc = vm->vm_qcache[qidx - 1]; 1018 1019 return pool_cache_put(&qc->qc_cache, (void *)addr); 1020 } 1021 #endif /* defined(QCACHE) */ 1022 1023 vmem_xfree(vm, addr, size); 1024 } 1025 1026 void 1027 vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size) 1028 { 1029 bt_t *bt; 1030 bt_t *t; 1031 1032 VMEM_ASSERT_UNLOCKED(vm); 1033 KASSERT(addr != VMEM_ADDR_NULL); 1034 KASSERT(size > 0); 1035 1036 VMEM_LOCK(vm); 1037 1038 bt = bt_lookupbusy(vm, addr); 1039 KASSERT(bt != NULL); 1040 KASSERT(bt->bt_start == addr); 1041 KASSERT(bt->bt_size == vmem_roundup_size(vm, size) || 1042 bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask); 1043 KASSERT(bt->bt_type == BT_TYPE_BUSY); 1044 bt_rembusy(vm, bt); 1045 bt->bt_type = BT_TYPE_FREE; 1046 1047 /* coalesce */ 1048 t = CIRCLEQ_NEXT(bt, bt_seglist); 1049 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1050 KASSERT(BT_END(bt) == t->bt_start); 1051 bt_remfree(vm, t); 1052 bt_remseg(vm, t); 1053 bt->bt_size += t->bt_size; 1054 bt_free(vm, t); 1055 } 1056 t = CIRCLEQ_PREV(bt, bt_seglist); 1057 if (t != NULL && t->bt_type == BT_TYPE_FREE) { 1058 KASSERT(BT_END(t) == bt->bt_start); 1059 bt_remfree(vm, t); 1060 bt_remseg(vm, t); 1061 bt->bt_size += t->bt_size; 1062 bt->bt_start = t->bt_start; 1063 bt_free(vm, t); 1064 } 1065 1066 t = CIRCLEQ_PREV(bt, bt_seglist); 1067 KASSERT(t != NULL); 1068 KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY); 1069 if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN && 1070 t->bt_size == bt->bt_size) { 1071 vmem_addr_t spanaddr; 1072 vmem_size_t spansize; 1073 1074 KASSERT(t->bt_start == bt->bt_start); 1075 spanaddr = bt->bt_start; 1076 spansize = bt->bt_size; 1077 bt_remseg(vm, bt); 1078 bt_free(vm, bt); 1079 bt_remseg(vm, t); 1080 bt_free(vm, t); 1081 VMEM_UNLOCK(vm); 1082 (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize); 1083 } else { 1084 bt_insfree(vm, bt); 1085 VMEM_UNLOCK(vm); 1086 } 1087 } 1088 1089 /* 1090 * vmem_add: 1091 * 1092 * => caller must ensure appropriate spl, 1093 * if the arena can be accessed from interrupt context. 1094 */ 1095 1096 vmem_addr_t 1097 vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags) 1098 { 1099 1100 return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC); 1101 } 1102 1103 /* 1104 * vmem_reap: reap unused resources. 1105 * 1106 * => return true if we successfully reaped something. 1107 */ 1108 1109 bool 1110 vmem_reap(vmem_t *vm) 1111 { 1112 bool didsomething = false; 1113 1114 VMEM_ASSERT_UNLOCKED(vm); 1115 1116 #if defined(QCACHE) 1117 didsomething = qc_reap(vm); 1118 #endif /* defined(QCACHE) */ 1119 return didsomething; 1120 } 1121 1122 /* ---- debug */ 1123 1124 #if defined(VMEM_DEBUG) 1125 1126 #if !defined(_KERNEL) 1127 #include <stdio.h> 1128 #endif /* !defined(_KERNEL) */ 1129 1130 void bt_dump(const bt_t *); 1131 1132 void 1133 bt_dump(const bt_t *bt) 1134 { 1135 1136 printf("\t%p: %" PRIu64 ", %" PRIu64 ", %d\n", 1137 bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size, 1138 bt->bt_type); 1139 } 1140 1141 void 1142 vmem_dump(const vmem_t *vm) 1143 { 1144 const bt_t *bt; 1145 int i; 1146 1147 printf("vmem %p '%s'\n", vm, vm->vm_name); 1148 CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) { 1149 bt_dump(bt); 1150 } 1151 1152 for (i = 0; i < VMEM_MAXORDER; i++) { 1153 const struct vmem_freelist *fl = &vm->vm_freelist[i]; 1154 1155 if (LIST_EMPTY(fl)) { 1156 continue; 1157 } 1158 1159 printf("freelist[%d]\n", i); 1160 LIST_FOREACH(bt, fl, bt_freelist) { 1161 bt_dump(bt); 1162 if (bt->bt_size) { 1163 } 1164 } 1165 } 1166 } 1167 1168 #if !defined(_KERNEL) 1169 1170 int 1171 main() 1172 { 1173 vmem_t *vm; 1174 vmem_addr_t p; 1175 struct reg { 1176 vmem_addr_t p; 1177 vmem_size_t sz; 1178 bool x; 1179 } *reg = NULL; 1180 int nreg = 0; 1181 int nalloc = 0; 1182 int nfree = 0; 1183 vmem_size_t total = 0; 1184 #if 1 1185 vm_flag_t strat = VM_INSTANTFIT; 1186 #else 1187 vm_flag_t strat = VM_BESTFIT; 1188 #endif 1189 1190 vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1, 1191 NULL, NULL, NULL, 0, VM_NOSLEEP); 1192 if (vm == NULL) { 1193 printf("vmem_create\n"); 1194 exit(EXIT_FAILURE); 1195 } 1196 vmem_dump(vm); 1197 1198 p = vmem_add(vm, 100, 200, VM_SLEEP); 1199 p = vmem_add(vm, 2000, 1, VM_SLEEP); 1200 p = vmem_add(vm, 40000, 0x10000000>>12, VM_SLEEP); 1201 p = vmem_add(vm, 10000, 10000, VM_SLEEP); 1202 p = vmem_add(vm, 500, 1000, VM_SLEEP); 1203 vmem_dump(vm); 1204 for (;;) { 1205 struct reg *r; 1206 int t = rand() % 100; 1207 1208 if (t > 45) { 1209 /* alloc */ 1210 vmem_size_t sz = rand() % 500 + 1; 1211 bool x; 1212 vmem_size_t align, phase, nocross; 1213 vmem_addr_t minaddr, maxaddr; 1214 1215 if (t > 70) { 1216 x = true; 1217 /* XXX */ 1218 align = 1 << (rand() % 15); 1219 phase = rand() % 65536; 1220 nocross = 1 << (rand() % 15); 1221 if (align <= phase) { 1222 phase = 0; 1223 } 1224 if (VMEM_CROSS_P(phase, phase + sz - 1, 1225 nocross)) { 1226 nocross = 0; 1227 } 1228 minaddr = rand() % 50000; 1229 maxaddr = rand() % 70000; 1230 if (minaddr > maxaddr) { 1231 minaddr = 0; 1232 maxaddr = 0; 1233 } 1234 printf("=== xalloc %" PRIu64 1235 " align=%" PRIu64 ", phase=%" PRIu64 1236 ", nocross=%" PRIu64 ", min=%" PRIu64 1237 ", max=%" PRIu64 "\n", 1238 (uint64_t)sz, 1239 (uint64_t)align, 1240 (uint64_t)phase, 1241 (uint64_t)nocross, 1242 (uint64_t)minaddr, 1243 (uint64_t)maxaddr); 1244 p = vmem_xalloc(vm, sz, align, phase, nocross, 1245 minaddr, maxaddr, strat|VM_SLEEP); 1246 } else { 1247 x = false; 1248 printf("=== alloc %" PRIu64 "\n", (uint64_t)sz); 1249 p = vmem_alloc(vm, sz, strat|VM_SLEEP); 1250 } 1251 printf("-> %" PRIu64 "\n", (uint64_t)p); 1252 vmem_dump(vm); 1253 if (p == VMEM_ADDR_NULL) { 1254 if (x) { 1255 continue; 1256 } 1257 break; 1258 } 1259 nreg++; 1260 reg = realloc(reg, sizeof(*reg) * nreg); 1261 r = ®[nreg - 1]; 1262 r->p = p; 1263 r->sz = sz; 1264 r->x = x; 1265 total += sz; 1266 nalloc++; 1267 } else if (nreg != 0) { 1268 /* free */ 1269 r = ®[rand() % nreg]; 1270 printf("=== free %" PRIu64 ", %" PRIu64 "\n", 1271 (uint64_t)r->p, (uint64_t)r->sz); 1272 if (r->x) { 1273 vmem_xfree(vm, r->p, r->sz); 1274 } else { 1275 vmem_free(vm, r->p, r->sz); 1276 } 1277 total -= r->sz; 1278 vmem_dump(vm); 1279 *r = reg[nreg - 1]; 1280 nreg--; 1281 nfree++; 1282 } 1283 printf("total=%" PRIu64 "\n", (uint64_t)total); 1284 } 1285 fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n", 1286 (uint64_t)total, nalloc, nfree); 1287 exit(EXIT_SUCCESS); 1288 } 1289 #endif /* !defined(_KERNEL) */ 1290 #endif /* defined(VMEM_DEBUG) */ 1291
Indexes created Mon Sep 29 21:09:56 GMT 2025