4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
27 /* #pragma ident "@(#)vmem.c 1.10 05/06/08 SMI" */
30 * For a more complete description of the main ideas, see:
32 * Jeff Bonwick and Jonathan Adams,
34 * Magazines and vmem: Extending the Slab Allocator to Many CPUs and
35 * Arbitrary Resources.
37 * Proceedings of the 2001 Usenix Conference.
38 * Available as /shared/sac/PSARC/2000/550/materials/vmem.pdf.
40 * For the "Big Theory Statement", see usr/src/common/os/vmem.c
42 * 1. Overview of changes
43 * ------------------------------
44 * There have been a few changes to vmem in order to support umem. The
47 * * VM_SLEEP unsupported
51 * * initialization changes
53 * * _vmem_extend_alloc
58 * Since VM_SLEEP allocations can hold locks (in vmem_populate()) for
59 * possibly infinite amounts of time, they are not supported in this
60 * version of vmem. Sleep-like behavior can be achieved through
61 * UMEM_NOFAIL umem allocations.
66 * Unlike kmem_reap(), which just asynchronously schedules work, umem_reap()
67 * can do allocations and frees synchronously. This is a problem if it
68 * occurs during a vmem_populate() allocation.
70 * Instead, we delay reaps while populates are active.
73 * 4. Initialization changes
74 * -------------------------
75 * In the kernel, vmem_init() allows you to create a single, top-level arena,
76 * which has vmem_internal_arena as a child. For umem, we want to be able
77 * to extend arenas dynamically. It is much easier to support this if we
78 * allow a two-level "heap" arena:
88 * | +-+-- ... <other children>
96 * The new vmem_init() allows you to specify a "parent" of the heap, along
97 * with allocation functions.
100 * 5. _vmem_extend_alloc
101 * ---------------------
102 * The other part of extending is _vmem_extend_alloc. This function allows
103 * you to extend (expand current spans, if possible) an arena and allocate
104 * a chunk of the newly extened span atomically. This is needed to support
105 * extending the heap while vmem_populate()ing it.
107 * In order to increase the usefulness of extending, non-imported spans are
108 * sorted in address order.
112 /* #include "mtlib.h" */
113 #include <sys/vmem_impl_user.h>
117 #ifdef HAVE_SYS_SYSMACROS_H
118 #include <sys/sysmacros.h>
128 #include "vmem_base.h"
129 #include "umem_base.h"
131 #define VMEM_INITIAL 6 /* early vmem arenas */
132 #define VMEM_SEG_INITIAL 100 /* early segments */
135 * Adding a new span to an arena requires two segment structures: one to
136 * represent the span, and one to represent the free segment it contains.
138 #define VMEM_SEGS_PER_SPAN_CREATE 2
141 * Allocating a piece of an existing segment requires 0-2 segment structures
142 * depending on how much of the segment we're allocating.
144 * To allocate the entire segment, no new segment structures are needed; we
145 * simply move the existing segment structure from the freelist to the
146 * allocation hash table.
148 * To allocate a piece from the left or right end of the segment, we must
149 * split the segment into two pieces (allocated part and remainder), so we
150 * need one new segment structure to represent the remainder.
152 * To allocate from the middle of a segment, we need two new segment strucures
153 * to represent the remainders on either side of the allocated part.
155 #define VMEM_SEGS_PER_EXACT_ALLOC 0
156 #define VMEM_SEGS_PER_LEFT_ALLOC 1
157 #define VMEM_SEGS_PER_RIGHT_ALLOC 1
158 #define VMEM_SEGS_PER_MIDDLE_ALLOC 2
161 * vmem_populate() preallocates segment structures for vmem to do its work.
162 * It must preallocate enough for the worst case, which is when we must import
163 * a new span and then allocate from the middle of it.
165 #define VMEM_SEGS_PER_ALLOC_MAX \
166 (VMEM_SEGS_PER_SPAN_CREATE + VMEM_SEGS_PER_MIDDLE_ALLOC)
169 * The segment structures themselves are allocated from vmem_seg_arena, so
170 * we have a recursion problem when vmem_seg_arena needs to populate itself.
171 * We address this by working out the maximum number of segment structures
172 * this act will require, and multiplying by the maximum number of threads
173 * that we'll allow to do it simultaneously.
175 * The worst-case segment consumption to populate vmem_seg_arena is as
176 * follows (depicted as a stack trace to indicate why events are occurring):
178 * vmem_alloc(vmem_seg_arena) -> 2 segs (span create + exact alloc)
179 * vmem_alloc(vmem_internal_arena) -> 2 segs (span create + exact alloc)
180 * heap_alloc(heap_arena)
181 * vmem_alloc(heap_arena) -> 4 seg (span create + alloc)
182 * parent_alloc(parent_arena)
183 * _vmem_extend_alloc(parent_arena) -> 3 seg (span create + left alloc)
185 * Note: The reservation for heap_arena must be 4, since vmem_xalloc()
186 * is overly pessimistic on allocations where parent_arena has a stricter
187 * alignment than heap_arena.
189 * The worst-case consumption for any arena is 4 segment structures.
190 * For now, we only support VM_NOSLEEP allocations, so as long as we
191 * serialize all vmem_populates, a 4-seg reserve is sufficient.
193 #define VMEM_POPULATE_SEGS_PER_ARENA 4
194 #define VMEM_POPULATE_LOCKS 1
196 #define VMEM_POPULATE_RESERVE \
197 (VMEM_POPULATE_SEGS_PER_ARENA * VMEM_POPULATE_LOCKS)
200 * vmem_populate() ensures that each arena has VMEM_MINFREE seg structures
201 * so that it can satisfy the worst-case allocation *and* participate in
202 * worst-case allocation from vmem_seg_arena.
204 #define VMEM_MINFREE (VMEM_POPULATE_RESERVE + VMEM_SEGS_PER_ALLOC_MAX)
206 /* Don't assume new statics are zeroed - see vmem_startup() */
207 static vmem_t vmem0[VMEM_INITIAL];
208 static vmem_t *vmem_populator[VMEM_INITIAL];
209 static uint32_t vmem_id;
210 static uint32_t vmem_populators;
211 static vmem_seg_t vmem_seg0[VMEM_SEG_INITIAL];
212 static vmem_seg_t *vmem_segfree;
213 static mutex_t vmem_list_lock = DEFAULTMUTEX;
214 static mutex_t vmem_segfree_lock = DEFAULTMUTEX;
215 static vmem_populate_lock_t vmem_nosleep_lock = {
219 #define IN_POPULATE() (vmem_nosleep_lock.vmpl_thr == thr_self())
220 static vmem_t *vmem_list;
221 static vmem_t *vmem_internal_arena;
222 static vmem_t *vmem_seg_arena;
223 static vmem_t *vmem_hash_arena;
224 static vmem_t *vmem_vmem_arena;
227 vmem_alloc_t *vmem_heap_alloc;
228 vmem_free_t *vmem_heap_free;
230 uint32_t vmem_mtbf; /* mean time between failures [default: off] */
231 size_t vmem_seg_size = sizeof (vmem_seg_t);
234 * we use the _ version, since we don't want to be cancelled.
235 * Actually, this is automatically taken care of by including "mtlib.h".
237 extern int _cond_wait(cond_t *cv, mutex_t *mutex);
240 * Insert/delete from arena list (type 'a') or next-of-kin list (type 'k').
242 #define VMEM_INSERT(vprev, vsp, type) \
244 vmem_seg_t *vnext = (vprev)->vs_##type##next; \
245 (vsp)->vs_##type##next = (vnext); \
246 (vsp)->vs_##type##prev = (vprev); \
247 (vprev)->vs_##type##next = (vsp); \
248 (vnext)->vs_##type##prev = (vsp); \
251 #define VMEM_DELETE(vsp, type) \
253 vmem_seg_t *vprev = (vsp)->vs_##type##prev; \
254 vmem_seg_t *vnext = (vsp)->vs_##type##next; \
255 (vprev)->vs_##type##next = (vnext); \
256 (vnext)->vs_##type##prev = (vprev); \
260 * Get a vmem_seg_t from the global segfree list.
263 vmem_getseg_global(void)
267 (void) mutex_lock(&vmem_segfree_lock);
268 if ((vsp = vmem_segfree) != NULL)
269 vmem_segfree = vsp->vs_knext;
270 (void) mutex_unlock(&vmem_segfree_lock);
276 * Put a vmem_seg_t on the global segfree list.
279 vmem_putseg_global(vmem_seg_t *vsp)
281 (void) mutex_lock(&vmem_segfree_lock);
282 vsp->vs_knext = vmem_segfree;
284 (void) mutex_unlock(&vmem_segfree_lock);
288 * Get a vmem_seg_t from vmp's segfree list.
291 vmem_getseg(vmem_t *vmp)
295 ASSERT(vmp->vm_nsegfree > 0);
297 vsp = vmp->vm_segfree;
298 vmp->vm_segfree = vsp->vs_knext;
305 * Put a vmem_seg_t on vmp's segfree list.
308 vmem_putseg(vmem_t *vmp, vmem_seg_t *vsp)
310 vsp->vs_knext = vmp->vm_segfree;
311 vmp->vm_segfree = vsp;
316 * Add vsp to the appropriate freelist.
319 vmem_freelist_insert(vmem_t *vmp, vmem_seg_t *vsp)
323 ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);
325 vprev = (vmem_seg_t *)&vmp->vm_freelist[highbit(VS_SIZE(vsp)) - 1];
326 vsp->vs_type = VMEM_FREE;
327 vmp->vm_freemap |= VS_SIZE(vprev);
328 VMEM_INSERT(vprev, vsp, k);
330 (void) cond_broadcast(&vmp->vm_cv);
334 * Take vsp from the freelist.
337 vmem_freelist_delete(vmem_t *vmp, vmem_seg_t *vsp)
339 ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);
340 ASSERT(vsp->vs_type == VMEM_FREE);
342 if (vsp->vs_knext->vs_start == 0 && vsp->vs_kprev->vs_start == 0) {
344 * The segments on both sides of 'vsp' are freelist heads,
345 * so taking vsp leaves the freelist at vsp->vs_kprev empty.
347 ASSERT(vmp->vm_freemap & VS_SIZE(vsp->vs_kprev));
348 vmp->vm_freemap ^= VS_SIZE(vsp->vs_kprev);
354 * Add vsp to the allocated-segment hash table and update kstats.
357 vmem_hash_insert(vmem_t *vmp, vmem_seg_t *vsp)
361 vsp->vs_type = VMEM_ALLOC;
362 bucket = VMEM_HASH(vmp, vsp->vs_start);
363 vsp->vs_knext = *bucket;
366 if (vmem_seg_size == sizeof (vmem_seg_t)) {
367 vsp->vs_depth = (uint8_t)getpcstack(vsp->vs_stack,
368 VMEM_STACK_DEPTH, 0);
369 vsp->vs_thread = thr_self();
370 vsp->vs_timestamp = gethrtime();
375 vmp->vm_kstat.vk_alloc++;
376 vmp->vm_kstat.vk_mem_inuse += VS_SIZE(vsp);
380 * Remove vsp from the allocated-segment hash table and update kstats.
383 vmem_hash_delete(vmem_t *vmp, uintptr_t addr, size_t size)
385 vmem_seg_t *vsp, **prev_vspp;
387 prev_vspp = VMEM_HASH(vmp, addr);
388 while ((vsp = *prev_vspp) != NULL) {
389 if (vsp->vs_start == addr) {
390 *prev_vspp = vsp->vs_knext;
393 vmp->vm_kstat.vk_lookup++;
394 prev_vspp = &vsp->vs_knext;
398 umem_panic("vmem_hash_delete(%p, %lx, %lu): bad free",
401 if (VS_SIZE(vsp) != size) {
402 umem_panic("vmem_hash_delete(%p, %lx, %lu): wrong size "
403 "(expect %lu)", vmp, addr, size, VS_SIZE(vsp));
406 vmp->vm_kstat.vk_free++;
407 vmp->vm_kstat.vk_mem_inuse -= size;
413 * Create a segment spanning the range [start, end) and add it to the arena.
416 vmem_seg_create(vmem_t *vmp, vmem_seg_t *vprev, uintptr_t start, uintptr_t end)
418 vmem_seg_t *newseg = vmem_getseg(vmp);
420 newseg->vs_start = start;
421 newseg->vs_end = end;
423 newseg->vs_import = 0;
425 VMEM_INSERT(vprev, newseg, a);
431 * Remove segment vsp from the arena.
434 vmem_seg_destroy(vmem_t *vmp, vmem_seg_t *vsp)
436 ASSERT(vsp->vs_type != VMEM_ROTOR);
439 vmem_putseg(vmp, vsp);
443 * Add the span [vaddr, vaddr + size) to vmp and update kstats.
446 vmem_span_create(vmem_t *vmp, void *vaddr, size_t size, uint8_t import)
449 vmem_seg_t *newseg, *span;
450 uintptr_t start = (uintptr_t)vaddr;
451 uintptr_t end = start + size;
453 knext = &vmp->vm_seg0;
454 if (!import && vmp->vm_source_alloc == NULL) {
455 vmem_seg_t *kend, *kprev;
457 * non-imported spans are sorted in address order. This
458 * makes vmem_extend_unlocked() much more effective.
460 * We search in reverse order, since new spans are
461 * generally at higher addresses.
463 kend = &vmp->vm_seg0;
464 for (kprev = kend->vs_kprev; kprev != kend;
465 kprev = kprev->vs_kprev) {
466 if (!kprev->vs_import && (kprev->vs_end - 1) < start)
469 knext = kprev->vs_knext;
472 ASSERT(MUTEX_HELD(&vmp->vm_lock));
474 if ((start | end) & (vmp->vm_quantum - 1)) {
475 umem_panic("vmem_span_create(%p, %p, %lu): misaligned",
479 span = vmem_seg_create(vmp, knext->vs_aprev, start, end);
480 span->vs_type = VMEM_SPAN;
481 VMEM_INSERT(knext->vs_kprev, span, k);
483 newseg = vmem_seg_create(vmp, span, start, end);
484 vmem_freelist_insert(vmp, newseg);
486 newseg->vs_import = import;
488 vmp->vm_kstat.vk_mem_import += size;
489 vmp->vm_kstat.vk_mem_total += size;
495 * Remove span vsp from vmp and update kstats.
498 vmem_span_destroy(vmem_t *vmp, vmem_seg_t *vsp)
500 vmem_seg_t *span = vsp->vs_aprev;
501 size_t size = VS_SIZE(vsp);
503 ASSERT(MUTEX_HELD(&vmp->vm_lock));
504 ASSERT(span->vs_type == VMEM_SPAN);
507 vmp->vm_kstat.vk_mem_import -= size;
508 vmp->vm_kstat.vk_mem_total -= size;
510 VMEM_DELETE(span, k);
512 vmem_seg_destroy(vmp, vsp);
513 vmem_seg_destroy(vmp, span);
517 * Allocate the subrange [addr, addr + size) from segment vsp.
518 * If there are leftovers on either side, place them on the freelist.
519 * Returns a pointer to the segment representing [addr, addr + size).
522 vmem_seg_alloc(vmem_t *vmp, vmem_seg_t *vsp, uintptr_t addr, size_t size)
524 uintptr_t vs_start = vsp->vs_start;
525 uintptr_t vs_end = vsp->vs_end;
526 size_t vs_size = vs_end - vs_start;
527 size_t realsize = P2ROUNDUP(size, vmp->vm_quantum);
528 uintptr_t addr_end = addr + realsize;
530 ASSERT(P2PHASE(vs_start, vmp->vm_quantum) == 0);
531 ASSERT(P2PHASE(addr, vmp->vm_quantum) == 0);
532 ASSERT(vsp->vs_type == VMEM_FREE);
533 ASSERT(addr >= vs_start && addr_end - 1 <= vs_end - 1);
534 ASSERT(addr - 1 <= addr_end - 1);
537 * If we're allocating from the start of the segment, and the
538 * remainder will be on the same freelist, we can save quite
541 if (P2SAMEHIGHBIT(vs_size, vs_size - realsize) && addr == vs_start) {
542 ASSERT(highbit(vs_size) == highbit(vs_size - realsize));
543 vsp->vs_start = addr_end;
544 vsp = vmem_seg_create(vmp, vsp->vs_aprev, addr, addr + size);
545 vmem_hash_insert(vmp, vsp);
549 vmem_freelist_delete(vmp, vsp);
551 if (vs_end != addr_end)
552 vmem_freelist_insert(vmp,
553 vmem_seg_create(vmp, vsp, addr_end, vs_end));
555 if (vs_start != addr)
556 vmem_freelist_insert(vmp,
557 vmem_seg_create(vmp, vsp->vs_aprev, vs_start, addr));
559 vsp->vs_start = addr;
560 vsp->vs_end = addr + size;
562 vmem_hash_insert(vmp, vsp);
567 * We cannot reap if we are in the middle of a vmem_populate().
577 * Populate vmp's segfree list with VMEM_MINFREE vmem_seg_t structures.
580 vmem_populate(vmem_t *vmp, int vmflag)
586 vmem_populate_lock_t *lp;
589 while (vmp->vm_nsegfree < VMEM_MINFREE &&
590 (vsp = vmem_getseg_global()) != NULL)
591 vmem_putseg(vmp, vsp);
593 if (vmp->vm_nsegfree >= VMEM_MINFREE)
597 * If we're already populating, tap the reserve.
599 if (vmem_nosleep_lock.vmpl_thr == thr_self()) {
600 ASSERT(vmp->vm_cflags & VMC_POPULATOR);
604 (void) mutex_unlock(&vmp->vm_lock);
606 ASSERT(vmflag & VM_NOSLEEP); /* we do not allow sleep allocations */
607 lp = &vmem_nosleep_lock;
610 * Cannot be just a mutex_lock(), since that has no effect if
611 * libthread is not linked.
613 (void) mutex_lock(&lp->vmpl_mutex);
614 ASSERT(lp->vmpl_thr == 0);
615 lp->vmpl_thr = thr_self();
617 nseg = VMEM_MINFREE + vmem_populators * VMEM_POPULATE_RESERVE;
618 size = P2ROUNDUP(nseg * vmem_seg_size, vmem_seg_arena->vm_quantum);
619 nseg = size / vmem_seg_size;
622 * The following vmem_alloc() may need to populate vmem_seg_arena
623 * and all the things it imports from. When doing so, it will tap
624 * each arena's reserve to prevent recursion (see the block comment
625 * above the definition of VMEM_POPULATE_RESERVE).
627 * During this allocation, vmem_reap() is a no-op. If the allocation
628 * fails, we call vmem_reap() after dropping the population lock.
630 p = vmem_alloc(vmem_seg_arena, size, vmflag & VM_UMFLAGS);
633 (void) mutex_unlock(&lp->vmpl_mutex);
636 (void) mutex_lock(&vmp->vm_lock);
637 vmp->vm_kstat.vk_populate_fail++;
641 * Restock the arenas that may have been depleted during population.
643 for (i = 0; i < vmem_populators; i++) {
644 (void) mutex_lock(&vmem_populator[i]->vm_lock);
645 while (vmem_populator[i]->vm_nsegfree < VMEM_POPULATE_RESERVE)
646 vmem_putseg(vmem_populator[i],
647 (vmem_seg_t *)(p + --nseg * vmem_seg_size));
648 (void) mutex_unlock(&vmem_populator[i]->vm_lock);
652 (void) mutex_unlock(&lp->vmpl_mutex);
653 (void) mutex_lock(&vmp->vm_lock);
656 * Now take our own segments.
658 ASSERT(nseg >= VMEM_MINFREE);
659 while (vmp->vm_nsegfree < VMEM_MINFREE)
660 vmem_putseg(vmp, (vmem_seg_t *)(p + --nseg * vmem_seg_size));
663 * Give the remainder to charity.
666 vmem_putseg_global((vmem_seg_t *)(p + --nseg * vmem_seg_size));
672 * Advance a walker from its previous position to 'afterme'.
673 * Note: may drop and reacquire vmp->vm_lock.
676 vmem_advance(vmem_t *vmp, vmem_seg_t *walker, vmem_seg_t *afterme)
678 vmem_seg_t *vprev = walker->vs_aprev;
679 vmem_seg_t *vnext = walker->vs_anext;
680 vmem_seg_t *vsp = NULL;
682 VMEM_DELETE(walker, a);
685 VMEM_INSERT(afterme, walker, a);
688 * The walker segment's presence may have prevented its neighbors
689 * from coalescing. If so, coalesce them now.
691 if (vprev->vs_type == VMEM_FREE) {
692 if (vnext->vs_type == VMEM_FREE) {
693 ASSERT(vprev->vs_end == vnext->vs_start);
694 vmem_freelist_delete(vmp, vnext);
695 vmem_freelist_delete(vmp, vprev);
696 vprev->vs_end = vnext->vs_end;
697 vmem_freelist_insert(vmp, vprev);
698 vmem_seg_destroy(vmp, vnext);
701 } else if (vnext->vs_type == VMEM_FREE) {
706 * vsp could represent a complete imported span,
707 * in which case we must return it to the source.
709 if (vsp != NULL && vsp->vs_import && vmp->vm_source_free != NULL &&
710 vsp->vs_aprev->vs_type == VMEM_SPAN &&
711 vsp->vs_anext->vs_type == VMEM_SPAN) {
712 void *vaddr = (void *)vsp->vs_start;
713 size_t size = VS_SIZE(vsp);
714 ASSERT(size == VS_SIZE(vsp->vs_aprev));
715 vmem_freelist_delete(vmp, vsp);
716 vmem_span_destroy(vmp, vsp);
717 (void) mutex_unlock(&vmp->vm_lock);
718 vmp->vm_source_free(vmp->vm_source, vaddr, size);
719 (void) mutex_lock(&vmp->vm_lock);
724 * VM_NEXTFIT allocations deliberately cycle through all virtual addresses
725 * in an arena, so that we avoid reusing addresses for as long as possible.
726 * This helps to catch used-after-freed bugs. It's also the perfect policy
727 * for allocating things like process IDs, where we want to cycle through
728 * all values in order.
731 vmem_nextfit_alloc(vmem_t *vmp, size_t size, int vmflag)
733 vmem_seg_t *vsp, *rotor;
735 size_t realsize = P2ROUNDUP(size, vmp->vm_quantum);
738 (void) mutex_lock(&vmp->vm_lock);
740 if (vmp->vm_nsegfree < VMEM_MINFREE && !vmem_populate(vmp, vmflag)) {
741 (void) mutex_unlock(&vmp->vm_lock);
746 * The common case is that the segment right after the rotor is free,
747 * and large enough that extracting 'size' bytes won't change which
748 * freelist it's on. In this case we can avoid a *lot* of work.
749 * Instead of the normal vmem_seg_alloc(), we just advance the start
750 * address of the victim segment. Instead of moving the rotor, we
751 * create the new segment structure *behind the rotor*, which has
752 * the same effect. And finally, we know we don't have to coalesce
753 * the rotor's neighbors because the new segment lies between them.
755 rotor = &vmp->vm_rotor;
756 vsp = rotor->vs_anext;
757 if (vsp->vs_type == VMEM_FREE && (vs_size = VS_SIZE(vsp)) > realsize &&
758 P2SAMEHIGHBIT(vs_size, vs_size - realsize)) {
759 ASSERT(highbit(vs_size) == highbit(vs_size - realsize));
760 addr = vsp->vs_start;
761 vsp->vs_start = addr + realsize;
762 vmem_hash_insert(vmp,
763 vmem_seg_create(vmp, rotor->vs_aprev, addr, addr + size));
764 (void) mutex_unlock(&vmp->vm_lock);
765 return ((void *)addr);
769 * Starting at the rotor, look for a segment large enough to
770 * satisfy the allocation.
773 vmp->vm_kstat.vk_search++;
774 if (vsp->vs_type == VMEM_FREE && VS_SIZE(vsp) >= size)
779 * We've come full circle. One possibility is that the
780 * there's actually enough space, but the rotor itself
781 * is preventing the allocation from succeeding because
782 * it's sitting between two free segments. Therefore,
783 * we advance the rotor and see if that liberates a
786 vmem_advance(vmp, rotor, rotor->vs_anext);
787 vsp = rotor->vs_aprev;
788 if (vsp->vs_type == VMEM_FREE && VS_SIZE(vsp) >= size)
791 * If there's a lower arena we can import from, or it's
792 * a VM_NOSLEEP allocation, let vmem_xalloc() handle it.
793 * Otherwise, wait until another thread frees something.
795 if (vmp->vm_source_alloc != NULL ||
796 (vmflag & VM_NOSLEEP)) {
797 (void) mutex_unlock(&vmp->vm_lock);
798 return (vmem_xalloc(vmp, size, vmp->vm_quantum,
799 0, 0, NULL, NULL, vmflag & VM_UMFLAGS));
801 vmp->vm_kstat.vk_wait++;
802 (void) _cond_wait(&vmp->vm_cv, &vmp->vm_lock);
803 vsp = rotor->vs_anext;
808 * We found a segment. Extract enough space to satisfy the allocation.
810 addr = vsp->vs_start;
811 vsp = vmem_seg_alloc(vmp, vsp, addr, size);
812 ASSERT(vsp->vs_type == VMEM_ALLOC &&
813 vsp->vs_start == addr && vsp->vs_end == addr + size);
816 * Advance the rotor to right after the newly-allocated segment.
817 * That's where the next VM_NEXTFIT allocation will begin searching.
819 vmem_advance(vmp, rotor, vsp);
820 (void) mutex_unlock(&vmp->vm_lock);
821 return ((void *)addr);
825 * Allocate size bytes at offset phase from an align boundary such that the
826 * resulting segment [addr, addr + size) is a subset of [minaddr, maxaddr)
827 * that does not straddle a nocross-aligned boundary.
830 vmem_xalloc(vmem_t *vmp, size_t size, size_t align, size_t phase,
831 size_t nocross, void *minaddr, void *maxaddr, int vmflag)
834 vmem_seg_t *vbest = NULL;
835 uintptr_t addr, taddr, start, end;
840 if (phase > 0 && phase >= align)
841 umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
843 (void *)vmp, size, align, phase, nocross,
844 minaddr, maxaddr, vmflag);
847 align = vmp->vm_quantum;
849 if ((align | phase | nocross) & (vmp->vm_quantum - 1)) {
850 umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
851 "parameters not vm_quantum aligned",
852 (void *)vmp, size, align, phase, nocross,
853 minaddr, maxaddr, vmflag);
857 (align > nocross || P2ROUNDUP(phase + size, align) > nocross)) {
858 umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
859 "overconstrained allocation",
860 (void *)vmp, size, align, phase, nocross,
861 minaddr, maxaddr, vmflag);
864 if ((mtbf = vmem_mtbf | vmp->vm_mtbf) != 0 && gethrtime() % mtbf == 0 &&
865 (vmflag & (VM_NOSLEEP | VM_PANIC)) == VM_NOSLEEP)
868 (void) mutex_lock(&vmp->vm_lock);
870 if (vmp->vm_nsegfree < VMEM_MINFREE &&
871 !vmem_populate(vmp, vmflag))
875 * highbit() returns the highest bit + 1, which is exactly
876 * what we want: we want to search the first freelist whose
877 * members are *definitely* large enough to satisfy our
878 * allocation. However, there are certain cases in which we
879 * want to look at the next-smallest freelist (which *might*
880 * be able to satisfy the allocation):
882 * (1) The size is exactly a power of 2, in which case
883 * the smaller freelist is always big enough;
885 * (2) All other freelists are empty;
887 * (3) We're in the highest possible freelist, which is
888 * always empty (e.g. the 4GB freelist on 32-bit systems);
890 * (4) We're doing a best-fit or first-fit allocation.
892 if ((size & (size - 1)) == 0) {
893 flist = lowbit(P2ALIGN(vmp->vm_freemap, size));
896 if ((vmp->vm_freemap >> hb) == 0 ||
897 hb == VMEM_FREELISTS ||
898 (vmflag & (VM_BESTFIT | VM_FIRSTFIT)))
900 flist = lowbit(P2ALIGN(vmp->vm_freemap, 1UL << hb));
903 for (vbest = NULL, vsp = (flist == 0) ? NULL :
904 vmp->vm_freelist[flist - 1].vs_knext;
905 vsp != NULL; vsp = vsp->vs_knext) {
906 vmp->vm_kstat.vk_search++;
907 if (vsp->vs_start == 0) {
909 * We're moving up to a larger freelist,
910 * so if we've already found a candidate,
911 * the fit can't possibly get any better.
916 * Find the next non-empty freelist.
918 flist = lowbit(P2ALIGN(vmp->vm_freemap,
922 vsp = (vmem_seg_t *)&vmp->vm_freelist[flist];
923 ASSERT(vsp->vs_knext->vs_type == VMEM_FREE);
926 if (vsp->vs_end - 1 < (uintptr_t)minaddr)
928 if (vsp->vs_start > (uintptr_t)maxaddr - 1)
930 start = MAX(vsp->vs_start, (uintptr_t)minaddr);
931 end = MIN(vsp->vs_end - 1, (uintptr_t)maxaddr - 1) + 1;
932 taddr = P2PHASEUP(start, align, phase);
933 if (P2CROSS(taddr, taddr + size - 1, nocross))
935 P2ROUNDUP(P2NPHASE(taddr, nocross), align);
936 if ((taddr - start) + size > end - start ||
937 (vbest != NULL && VS_SIZE(vsp) >= VS_SIZE(vbest)))
941 if (!(vmflag & VM_BESTFIT) || VS_SIZE(vbest) == size)
947 umem_panic("vmem_xalloc(): size == 0");
948 if (vmp->vm_source_alloc != NULL && nocross == 0 &&
949 minaddr == NULL && maxaddr == NULL) {
950 size_t asize = P2ROUNDUP(size + phase,
951 MAX(align, vmp->vm_source->vm_quantum));
952 if (asize < size) { /* overflow */
953 (void) mutex_unlock(&vmp->vm_lock);
954 if (vmflag & VM_NOSLEEP)
957 umem_panic("vmem_xalloc(): "
958 "overflow on VM_SLEEP allocation");
961 * Determine how many segment structures we'll consume.
962 * The calculation must be presise because if we're
963 * here on behalf of vmem_populate(), we are taking
964 * segments from a very limited reserve.
966 resv = (size == asize) ?
967 VMEM_SEGS_PER_SPAN_CREATE +
968 VMEM_SEGS_PER_EXACT_ALLOC :
969 VMEM_SEGS_PER_ALLOC_MAX;
970 ASSERT(vmp->vm_nsegfree >= resv);
971 vmp->vm_nsegfree -= resv; /* reserve our segs */
972 (void) mutex_unlock(&vmp->vm_lock);
973 vaddr = vmp->vm_source_alloc(vmp->vm_source, asize,
974 vmflag & VM_UMFLAGS);
975 (void) mutex_lock(&vmp->vm_lock);
976 vmp->vm_nsegfree += resv; /* claim reservation */
978 vbest = vmem_span_create(vmp, vaddr, asize, 1);
979 addr = P2PHASEUP(vbest->vs_start, align, phase);
983 (void) mutex_unlock(&vmp->vm_lock);
985 (void) mutex_lock(&vmp->vm_lock);
986 if (vmflag & VM_NOSLEEP)
988 vmp->vm_kstat.vk_wait++;
989 (void) _cond_wait(&vmp->vm_cv, &vmp->vm_lock);
992 ASSERT(vbest->vs_type == VMEM_FREE);
993 ASSERT(vbest->vs_knext != vbest);
994 (void) vmem_seg_alloc(vmp, vbest, addr, size);
995 (void) mutex_unlock(&vmp->vm_lock);
996 ASSERT(P2PHASE(addr, align) == phase);
997 ASSERT(!P2CROSS(addr, addr + size - 1, nocross));
998 ASSERT(addr >= (uintptr_t)minaddr);
999 ASSERT(addr + size - 1 <= (uintptr_t)maxaddr - 1);
1000 return ((void *)addr);
1002 vmp->vm_kstat.vk_fail++;
1003 (void) mutex_unlock(&vmp->vm_lock);
1004 if (vmflag & VM_PANIC)
1005 umem_panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
1006 "cannot satisfy mandatory allocation",
1007 (void *)vmp, size, align, phase, nocross,
1008 minaddr, maxaddr, vmflag);
1013 * Free the segment [vaddr, vaddr + size), where vaddr was a constrained
1014 * allocation. vmem_xalloc() and vmem_xfree() must always be paired because
1015 * both routines bypass the quantum caches.
1018 vmem_xfree(vmem_t *vmp, void *vaddr, size_t size)
1020 vmem_seg_t *vsp, *vnext, *vprev;
1022 (void) mutex_lock(&vmp->vm_lock);
1024 vsp = vmem_hash_delete(vmp, (uintptr_t)vaddr, size);
1025 vsp->vs_end = P2ROUNDUP(vsp->vs_end, vmp->vm_quantum);
1028 * Attempt to coalesce with the next segment.
1030 vnext = vsp->vs_anext;
1031 if (vnext->vs_type == VMEM_FREE) {
1032 ASSERT(vsp->vs_end == vnext->vs_start);
1033 vmem_freelist_delete(vmp, vnext);
1034 vsp->vs_end = vnext->vs_end;
1035 vmem_seg_destroy(vmp, vnext);
1039 * Attempt to coalesce with the previous segment.
1041 vprev = vsp->vs_aprev;
1042 if (vprev->vs_type == VMEM_FREE) {
1043 ASSERT(vprev->vs_end == vsp->vs_start);
1044 vmem_freelist_delete(vmp, vprev);
1045 vprev->vs_end = vsp->vs_end;
1046 vmem_seg_destroy(vmp, vsp);
1051 * If the entire span is free, return it to the source.
1053 if (vsp->vs_import && vmp->vm_source_free != NULL &&
1054 vsp->vs_aprev->vs_type == VMEM_SPAN &&
1055 vsp->vs_anext->vs_type == VMEM_SPAN) {
1056 vaddr = (void *)vsp->vs_start;
1057 size = VS_SIZE(vsp);
1058 ASSERT(size == VS_SIZE(vsp->vs_aprev));
1059 vmem_span_destroy(vmp, vsp);
1060 (void) mutex_unlock(&vmp->vm_lock);
1061 vmp->vm_source_free(vmp->vm_source, vaddr, size);
1063 vmem_freelist_insert(vmp, vsp);
1064 (void) mutex_unlock(&vmp->vm_lock);
1069 * Allocate size bytes from arena vmp. Returns the allocated address
1070 * on success, NULL on failure. vmflag specifies VM_SLEEP or VM_NOSLEEP,
1071 * and may also specify best-fit, first-fit, or next-fit allocation policy
1072 * instead of the default instant-fit policy. VM_SLEEP allocations are
1073 * guaranteed to succeed.
1076 vmem_alloc(vmem_t *vmp, size_t size, int vmflag)
1084 if (size - 1 < vmp->vm_qcache_max) {
1085 ASSERT(vmflag & VM_NOSLEEP);
1086 return (_umem_cache_alloc(vmp->vm_qcache[(size - 1) >>
1087 vmp->vm_qshift], UMEM_DEFAULT));
1090 if ((mtbf = vmem_mtbf | vmp->vm_mtbf) != 0 && gethrtime() % mtbf == 0 &&
1091 (vmflag & (VM_NOSLEEP | VM_PANIC)) == VM_NOSLEEP)
1094 if (vmflag & VM_NEXTFIT)
1095 return (vmem_nextfit_alloc(vmp, size, vmflag));
1097 if (vmflag & (VM_BESTFIT | VM_FIRSTFIT))
1098 return (vmem_xalloc(vmp, size, vmp->vm_quantum, 0, 0,
1099 NULL, NULL, vmflag));
1102 * Unconstrained instant-fit allocation from the segment list.
1104 (void) mutex_lock(&vmp->vm_lock);
1106 if (vmp->vm_nsegfree >= VMEM_MINFREE || vmem_populate(vmp, vmflag)) {
1107 if ((size & (size - 1)) == 0)
1108 flist = lowbit(P2ALIGN(vmp->vm_freemap, size));
1109 else if ((hb = highbit(size)) < VMEM_FREELISTS)
1110 flist = lowbit(P2ALIGN(vmp->vm_freemap, 1UL << hb));
1114 (void) mutex_unlock(&vmp->vm_lock);
1115 return (vmem_xalloc(vmp, size, vmp->vm_quantum,
1116 0, 0, NULL, NULL, vmflag));
1119 ASSERT(size <= (1UL << flist));
1120 vsp = vmp->vm_freelist[flist].vs_knext;
1121 addr = vsp->vs_start;
1122 (void) vmem_seg_alloc(vmp, vsp, addr, size);
1123 (void) mutex_unlock(&vmp->vm_lock);
1124 return ((void *)addr);
1128 * Free the segment [vaddr, vaddr + size).
1131 vmem_free(vmem_t *vmp, void *vaddr, size_t size)
1133 if (size - 1 < vmp->vm_qcache_max)
1134 _umem_cache_free(vmp->vm_qcache[(size - 1) >> vmp->vm_qshift],
1137 vmem_xfree(vmp, vaddr, size);
1141 * Determine whether arena vmp contains the segment [vaddr, vaddr + size).
1144 vmem_contains(vmem_t *vmp, void *vaddr, size_t size)
1146 uintptr_t start = (uintptr_t)vaddr;
1147 uintptr_t end = start + size;
1149 vmem_seg_t *seg0 = &vmp->vm_seg0;
1151 (void) mutex_lock(&vmp->vm_lock);
1152 vmp->vm_kstat.vk_contains++;
1153 for (vsp = seg0->vs_knext; vsp != seg0; vsp = vsp->vs_knext) {
1154 vmp->vm_kstat.vk_contains_search++;
1155 ASSERT(vsp->vs_type == VMEM_SPAN);
1156 if (start >= vsp->vs_start && end - 1 <= vsp->vs_end - 1)
1159 (void) mutex_unlock(&vmp->vm_lock);
1160 return (vsp != seg0);
1164 * Add the span [vaddr, vaddr + size) to arena vmp.
1167 vmem_add(vmem_t *vmp, void *vaddr, size_t size, int vmflag)
1169 if (vaddr == NULL || size == 0) {
1170 umem_panic("vmem_add(%p, %p, %lu): bad arguments",
1174 ASSERT(!vmem_contains(vmp, vaddr, size));
1176 (void) mutex_lock(&vmp->vm_lock);
1177 if (vmem_populate(vmp, vmflag))
1178 (void) vmem_span_create(vmp, vaddr, size, 0);
1181 (void) cond_broadcast(&vmp->vm_cv);
1182 (void) mutex_unlock(&vmp->vm_lock);
1187 * Adds the address range [addr, endaddr) to arena vmp, by either:
1188 * 1. joining two existing spans, [x, addr), and [endaddr, y) (which
1189 * are in that order) into a single [x, y) span,
1190 * 2. expanding an existing [x, addr) span to [x, endaddr),
1191 * 3. expanding an existing [endaddr, x) span to [addr, x), or
1192 * 4. creating a new [addr, endaddr) span.
1194 * Called with vmp->vm_lock held, and a successful vmem_populate() completed.
1195 * Cannot fail. Returns the new segment.
1197 * NOTE: this algorithm is linear-time in the number of spans, but is
1198 * constant-time when you are extending the last (highest-addressed)
1202 vmem_extend_unlocked(vmem_t *vmp, uintptr_t addr, uintptr_t endaddr)
1207 vmem_seg_t *end = &vmp->vm_seg0;
1209 ASSERT(MUTEX_HELD(&vmp->vm_lock));
1212 * the second "if" clause below relies on the direction of this search
1214 for (span = end->vs_kprev; span != end; span = span->vs_kprev) {
1215 if (span->vs_end == addr || span->vs_start == endaddr)
1220 return (vmem_span_create(vmp, (void *)addr, endaddr - addr, 0));
1221 if (span->vs_kprev->vs_end == addr && span->vs_start == endaddr) {
1222 vmem_seg_t *prevspan = span->vs_kprev;
1223 vmem_seg_t *nextseg = span->vs_anext;
1224 vmem_seg_t *prevseg = span->vs_aprev;
1227 * prevspan becomes the span marker for the full range
1229 prevspan->vs_end = span->vs_end;
1232 * Notionally, span becomes a free segment representing
1235 * However, if either of its neighbors are free, we coalesce
1236 * by destroying span and changing the free segment.
1238 if (prevseg->vs_type == VMEM_FREE &&
1239 nextseg->vs_type == VMEM_FREE) {
1241 * coalesce both ways
1243 ASSERT(prevseg->vs_end == addr &&
1244 nextseg->vs_start == endaddr);
1246 vmem_freelist_delete(vmp, prevseg);
1247 prevseg->vs_end = nextseg->vs_end;
1249 vmem_freelist_delete(vmp, nextseg);
1250 VMEM_DELETE(span, k);
1251 vmem_seg_destroy(vmp, nextseg);
1252 vmem_seg_destroy(vmp, span);
1255 } else if (prevseg->vs_type == VMEM_FREE) {
1259 ASSERT(prevseg->vs_end == addr);
1261 VMEM_DELETE(span, k);
1262 vmem_seg_destroy(vmp, span);
1264 vmem_freelist_delete(vmp, prevseg);
1265 prevseg->vs_end = endaddr;
1268 } else if (nextseg->vs_type == VMEM_FREE) {
1272 ASSERT(nextseg->vs_start == endaddr);
1274 VMEM_DELETE(span, k);
1275 vmem_seg_destroy(vmp, span);
1277 vmem_freelist_delete(vmp, nextseg);
1278 nextseg->vs_start = addr;
1285 VMEM_DELETE(span, k);
1286 span->vs_start = addr;
1287 span->vs_end = endaddr;
1291 } else if (span->vs_end == addr) {
1292 vmem_seg_t *oldseg = span->vs_knext->vs_aprev;
1293 span->vs_end = endaddr;
1295 ASSERT(oldseg->vs_type != VMEM_SPAN);
1296 if (oldseg->vs_type == VMEM_FREE) {
1297 ASSERT(oldseg->vs_end == addr);
1298 vmem_freelist_delete(vmp, oldseg);
1299 oldseg->vs_end = endaddr;
1302 vsp = vmem_seg_create(vmp, oldseg, addr, endaddr);
1304 vmem_seg_t *oldseg = span->vs_anext;
1305 ASSERT(span->vs_start == endaddr);
1306 span->vs_start = addr;
1308 ASSERT(oldseg->vs_type != VMEM_SPAN);
1309 if (oldseg->vs_type == VMEM_FREE) {
1310 ASSERT(oldseg->vs_start == endaddr);
1311 vmem_freelist_delete(vmp, oldseg);
1312 oldseg->vs_start = addr;
1315 vsp = vmem_seg_create(vmp, span, addr, endaddr);
1317 vmem_freelist_insert(vmp, vsp);
1318 vmp->vm_kstat.vk_mem_total += (endaddr - addr);
1323 * Does some error checking, calls vmem_extend_unlocked to add
1324 * [vaddr, vaddr+size) to vmp, then allocates alloc bytes from the
1325 * newly merged segment.
1328 _vmem_extend_alloc(vmem_t *vmp, void *vaddr, size_t size, size_t alloc,
1331 uintptr_t addr = (uintptr_t)vaddr;
1332 uintptr_t endaddr = addr + size;
1335 ASSERT(vaddr != NULL && size != 0 && endaddr > addr);
1336 ASSERT(alloc <= size && alloc != 0);
1337 ASSERT(((addr | size | alloc) & (vmp->vm_quantum - 1)) == 0);
1339 ASSERT(!vmem_contains(vmp, vaddr, size));
1341 (void) mutex_lock(&vmp->vm_lock);
1342 if (!vmem_populate(vmp, vmflag)) {
1343 (void) mutex_unlock(&vmp->vm_lock);
1347 * if there is a source, we can't mess with the spans
1349 if (vmp->vm_source_alloc != NULL)
1350 vsp = vmem_span_create(vmp, vaddr, size, 0);
1352 vsp = vmem_extend_unlocked(vmp, addr, endaddr);
1354 ASSERT(VS_SIZE(vsp) >= alloc);
1356 addr = vsp->vs_start;
1357 (void) vmem_seg_alloc(vmp, vsp, addr, alloc);
1358 vaddr = (void *)addr;
1360 (void) cond_broadcast(&vmp->vm_cv);
1361 (void) mutex_unlock(&vmp->vm_lock);
1367 * Walk the vmp arena, applying func to each segment matching typemask.
1368 * If VMEM_REENTRANT is specified, the arena lock is dropped across each
1369 * call to func(); otherwise, it is held for the duration of vmem_walk()
1370 * to ensure a consistent snapshot. Note that VMEM_REENTRANT callbacks
1371 * are *not* necessarily consistent, so they may only be used when a hint
1375 vmem_walk(vmem_t *vmp, int typemask,
1376 void (*func)(void *, void *, size_t), void *arg)
1379 vmem_seg_t *seg0 = &vmp->vm_seg0;
1382 if (typemask & VMEM_WALKER)
1385 bzero(&walker, sizeof (walker));
1386 walker.vs_type = VMEM_WALKER;
1388 (void) mutex_lock(&vmp->vm_lock);
1389 VMEM_INSERT(seg0, &walker, a);
1390 for (vsp = seg0->vs_anext; vsp != seg0; vsp = vsp->vs_anext) {
1391 if (vsp->vs_type & typemask) {
1392 void *start = (void *)vsp->vs_start;
1393 size_t size = VS_SIZE(vsp);
1394 if (typemask & VMEM_REENTRANT) {
1395 vmem_advance(vmp, &walker, vsp);
1396 (void) mutex_unlock(&vmp->vm_lock);
1397 func(arg, start, size);
1398 (void) mutex_lock(&vmp->vm_lock);
1401 func(arg, start, size);
1405 vmem_advance(vmp, &walker, NULL);
1406 (void) mutex_unlock(&vmp->vm_lock);
1410 * Return the total amount of memory whose type matches typemask. Thus:
1412 * typemask VMEM_ALLOC yields total memory allocated (in use).
1413 * typemask VMEM_FREE yields total memory free (available).
1414 * typemask (VMEM_ALLOC | VMEM_FREE) yields total arena size.
1417 vmem_size(vmem_t *vmp, int typemask)
1421 if (typemask & VMEM_ALLOC)
1422 size += vmp->vm_kstat.vk_mem_inuse;
1423 if (typemask & VMEM_FREE)
1424 size += vmp->vm_kstat.vk_mem_total -
1425 vmp->vm_kstat.vk_mem_inuse;
1426 return ((size_t)size);
1430 * Create an arena called name whose initial span is [base, base + size).
1431 * The arena's natural unit of currency is quantum, so vmem_alloc()
1432 * guarantees quantum-aligned results. The arena may import new spans
1433 * by invoking afunc() on source, and may return those spans by invoking
1434 * ffunc() on source. To make small allocations fast and scalable,
1435 * the arena offers high-performance caching for each integer multiple
1436 * of quantum up to qcache_max.
1439 vmem_create(const char *name, void *base, size_t size, size_t quantum,
1440 vmem_alloc_t *afunc, vmem_free_t *ffunc, vmem_t *source,
1441 size_t qcache_max, int vmflag)
1445 vmem_t *vmp, *cur, **vmpp;
1447 vmem_freelist_t *vfp;
1448 uint32_t id = atomic_add_32_nv(&vmem_id, 1);
1450 if (vmem_vmem_arena != NULL) {
1451 vmp = vmem_alloc(vmem_vmem_arena, sizeof (vmem_t),
1452 vmflag & VM_UMFLAGS);
1454 ASSERT(id <= VMEM_INITIAL);
1455 vmp = &vmem0[id - 1];
1460 bzero(vmp, sizeof (vmem_t));
1462 (void) snprintf(vmp->vm_name, VMEM_NAMELEN, "%s", name);
1463 (void) mutex_init(&vmp->vm_lock, USYNC_THREAD, NULL);
1464 (void) cond_init(&vmp->vm_cv, USYNC_THREAD, NULL);
1465 vmp->vm_cflags = vmflag;
1466 vmflag &= VM_UMFLAGS;
1468 vmp->vm_quantum = quantum;
1469 vmp->vm_qshift = highbit(quantum) - 1;
1470 nqcache = MIN(qcache_max >> vmp->vm_qshift, VMEM_NQCACHE_MAX);
1472 for (i = 0; i <= VMEM_FREELISTS; i++) {
1473 vfp = &vmp->vm_freelist[i];
1474 vfp->vs_end = 1UL << i;
1475 vfp->vs_knext = (vmem_seg_t *)(vfp + 1);
1476 vfp->vs_kprev = (vmem_seg_t *)(vfp - 1);
1479 vmp->vm_freelist[0].vs_kprev = NULL;
1480 vmp->vm_freelist[VMEM_FREELISTS].vs_knext = NULL;
1481 vmp->vm_freelist[VMEM_FREELISTS].vs_end = 0;
1482 vmp->vm_hash_table = vmp->vm_hash0;
1483 vmp->vm_hash_mask = VMEM_HASH_INITIAL - 1;
1484 vmp->vm_hash_shift = highbit(vmp->vm_hash_mask);
1486 vsp = &vmp->vm_seg0;
1487 vsp->vs_anext = vsp;
1488 vsp->vs_aprev = vsp;
1489 vsp->vs_knext = vsp;
1490 vsp->vs_kprev = vsp;
1491 vsp->vs_type = VMEM_SPAN;
1493 vsp = &vmp->vm_rotor;
1494 vsp->vs_type = VMEM_ROTOR;
1495 VMEM_INSERT(&vmp->vm_seg0, vsp, a);
1499 vmp->vm_kstat.vk_source_id = source->vm_id;
1500 vmp->vm_source = source;
1501 vmp->vm_source_alloc = afunc;
1502 vmp->vm_source_free = ffunc;
1505 vmp->vm_qcache_max = nqcache << vmp->vm_qshift;
1506 for (i = 0; i < nqcache; i++) {
1507 char buf[VMEM_NAMELEN + 21];
1508 (void) snprintf(buf, sizeof (buf), "%s_%lu",
1509 vmp->vm_name, (long)((i + 1) * quantum));
1510 vmp->vm_qcache[i] = umem_cache_create(buf,
1511 (i + 1) * quantum, quantum, NULL, NULL, NULL,
1512 NULL, vmp, UMC_QCACHE | UMC_NOTOUCH);
1513 if (vmp->vm_qcache[i] == NULL) {
1514 vmp->vm_qcache_max = i * quantum;
1520 (void) mutex_lock(&vmem_list_lock);
1522 while ((cur = *vmpp) != NULL)
1523 vmpp = &cur->vm_next;
1525 (void) mutex_unlock(&vmem_list_lock);
1527 if (vmp->vm_cflags & VMC_POPULATOR) {
1528 uint_t pop_id = atomic_add_32_nv(&vmem_populators, 1);
1529 ASSERT(pop_id <= VMEM_INITIAL);
1530 vmem_populator[pop_id - 1] = vmp;
1531 (void) mutex_lock(&vmp->vm_lock);
1532 (void) vmem_populate(vmp, vmflag | VM_PANIC);
1533 (void) mutex_unlock(&vmp->vm_lock);
1536 if ((base || size) && vmem_add(vmp, base, size, vmflag) == NULL) {
1545 * Destroy arena vmp.
1548 vmem_destroy(vmem_t *vmp)
1550 vmem_t *cur, **vmpp;
1551 vmem_seg_t *seg0 = &vmp->vm_seg0;
1556 (void) mutex_lock(&vmem_list_lock);
1558 while ((cur = *vmpp) != vmp)
1559 vmpp = &cur->vm_next;
1560 *vmpp = vmp->vm_next;
1561 (void) mutex_unlock(&vmem_list_lock);
1563 for (i = 0; i < VMEM_NQCACHE_MAX; i++)
1564 if (vmp->vm_qcache[i])
1565 umem_cache_destroy(vmp->vm_qcache[i]);
1567 leaked = vmem_size(vmp, VMEM_ALLOC);
1569 umem_printf("vmem_destroy('%s'): leaked %lu bytes",
1570 vmp->vm_name, leaked);
1572 if (vmp->vm_hash_table != vmp->vm_hash0)
1573 vmem_free(vmem_hash_arena, vmp->vm_hash_table,
1574 (vmp->vm_hash_mask + 1) * sizeof (void *));
1577 * Give back the segment structures for anything that's left in the
1578 * arena, e.g. the primary spans and their free segments.
1580 VMEM_DELETE(&vmp->vm_rotor, a);
1581 for (vsp = seg0->vs_anext; vsp != seg0; vsp = vsp->vs_anext)
1582 vmem_putseg_global(vsp);
1584 while (vmp->vm_nsegfree > 0)
1585 vmem_putseg_global(vmem_getseg(vmp));
1587 (void) mutex_destroy(&vmp->vm_lock);
1588 (void) cond_destroy(&vmp->vm_cv);
1589 vmem_free(vmem_vmem_arena, vmp, sizeof (vmem_t));
1593 * Resize vmp's hash table to keep the average lookup depth near 1.0.
1596 vmem_hash_rescale(vmem_t *vmp)
1598 vmem_seg_t **old_table, **new_table, *vsp;
1599 size_t old_size, new_size, h, nseg;
1601 nseg = (size_t)(vmp->vm_kstat.vk_alloc - vmp->vm_kstat.vk_free);
1603 new_size = MAX(VMEM_HASH_INITIAL, 1 << (highbit(3 * nseg + 4) - 2));
1604 old_size = vmp->vm_hash_mask + 1;
1606 if ((old_size >> 1) <= new_size && new_size <= (old_size << 1))
1609 new_table = vmem_alloc(vmem_hash_arena, new_size * sizeof (void *),
1611 if (new_table == NULL)
1613 bzero(new_table, new_size * sizeof (void *));
1615 (void) mutex_lock(&vmp->vm_lock);
1617 old_size = vmp->vm_hash_mask + 1;
1618 old_table = vmp->vm_hash_table;
1620 vmp->vm_hash_mask = new_size - 1;
1621 vmp->vm_hash_table = new_table;
1622 vmp->vm_hash_shift = highbit(vmp->vm_hash_mask);
1624 for (h = 0; h < old_size; h++) {
1626 while (vsp != NULL) {
1627 uintptr_t addr = vsp->vs_start;
1628 vmem_seg_t *next_vsp = vsp->vs_knext;
1629 vmem_seg_t **hash_bucket = VMEM_HASH(vmp, addr);
1630 vsp->vs_knext = *hash_bucket;
1636 (void) mutex_unlock(&vmp->vm_lock);
1638 if (old_table != vmp->vm_hash0)
1639 vmem_free(vmem_hash_arena, old_table,
1640 old_size * sizeof (void *));
1644 * Perform periodic maintenance on all vmem arenas.
1648 vmem_update(void *dummy)
1652 (void) mutex_lock(&vmem_list_lock);
1653 for (vmp = vmem_list; vmp != NULL; vmp = vmp->vm_next) {
1655 * If threads are waiting for resources, wake them up
1656 * periodically so they can issue another vmem_reap()
1657 * to reclaim resources cached by the slab allocator.
1659 (void) cond_broadcast(&vmp->vm_cv);
1662 * Rescale the hash table to keep the hash chains short.
1664 vmem_hash_rescale(vmp);
1666 (void) mutex_unlock(&vmem_list_lock);
1670 * If vmem_init is called again, we need to be able to reset the world.
1671 * That includes resetting the statics back to their original values.
1676 #ifdef UMEM_STANDALONE
1678 vmem_populators = 0;
1679 vmem_segfree = NULL;
1681 vmem_internal_arena = NULL;
1682 vmem_seg_arena = NULL;
1683 vmem_hash_arena = NULL;
1684 vmem_vmem_arena = NULL;
1686 vmem_heap_alloc = NULL;
1687 vmem_heap_free = NULL;
1689 bzero(vmem0, sizeof (vmem0));
1690 bzero(vmem_populator, sizeof (vmem_populator));
1691 bzero(vmem_seg0, sizeof (vmem_seg0));
1696 * Prepare vmem for use.
1699 vmem_init(const char *parent_name, size_t parent_quantum,
1700 vmem_alloc_t *parent_alloc, vmem_free_t *parent_free,
1701 const char *heap_name, void *heap_start, size_t heap_size,
1702 size_t heap_quantum, vmem_alloc_t *heap_alloc, vmem_free_t *heap_free)
1705 int nseg = VMEM_SEG_INITIAL;
1706 vmem_t *parent, *heap;
1708 ASSERT(vmem_internal_arena == NULL);
1711 vmem_putseg_global(&vmem_seg0[nseg]);
1713 if (parent_name != NULL) {
1714 parent = vmem_create(parent_name,
1715 heap_start, heap_size, parent_quantum,
1716 NULL, NULL, NULL, 0,
1717 VM_SLEEP | VMC_POPULATOR);
1721 ASSERT(parent_alloc == NULL && parent_free == NULL);
1725 heap = vmem_create(heap_name,
1726 heap_start, heap_size, heap_quantum,
1727 parent_alloc, parent_free, parent, 0,
1728 VM_SLEEP | VMC_POPULATOR);
1731 vmem_heap_alloc = heap_alloc;
1732 vmem_heap_free = heap_free;
1734 vmem_internal_arena = vmem_create("vmem_internal",
1735 NULL, 0, heap_quantum,
1736 heap_alloc, heap_free, heap, 0,
1737 VM_SLEEP | VMC_POPULATOR);
1739 vmem_seg_arena = vmem_create("vmem_seg",
1740 NULL, 0, heap_quantum,
1741 vmem_alloc, vmem_free, vmem_internal_arena, 0,
1742 VM_SLEEP | VMC_POPULATOR);
1744 vmem_hash_arena = vmem_create("vmem_hash",
1746 vmem_alloc, vmem_free, vmem_internal_arena, 0,
1749 vmem_vmem_arena = vmem_create("vmem_vmem",
1750 vmem0, sizeof (vmem0), 1,
1751 vmem_alloc, vmem_free, vmem_internal_arena, 0,
1754 for (id = 0; id < vmem_id; id++)
1755 (void) vmem_xalloc(vmem_vmem_arena, sizeof (vmem_t),
1756 1, 0, 0, &vmem0[id], &vmem0[id + 1],
1757 VM_NOSLEEP | VM_BESTFIT | VM_PANIC);
1766 * This size must be a multiple of the minimum required alignment,
1767 * since vmem_populate allocates them compactly.
1769 vmem_seg_size = P2ROUNDUP(offsetof(vmem_seg_t, vs_thread),
1774 * Lockup and release, for fork1(2) handling.
1781 (void) mutex_lock(&vmem_list_lock);
1782 (void) mutex_lock(&vmem_nosleep_lock.vmpl_mutex);
1785 * Lock up and broadcast all arenas.
1787 for (cur = vmem_list; cur != NULL; cur = cur->vm_next) {
1788 (void) mutex_lock(&cur->vm_lock);
1789 (void) cond_broadcast(&cur->vm_cv);
1792 (void) mutex_lock(&vmem_segfree_lock);
1800 (void) mutex_unlock(&vmem_nosleep_lock.vmpl_mutex);
1802 for (cur = vmem_list; cur != NULL; cur = cur->vm_next)
1803 (void) mutex_unlock(&cur->vm_lock);
1805 (void) mutex_unlock(&vmem_segfree_lock);
1806 (void) mutex_unlock(&vmem_list_lock);