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