xref: /titanic_50/usr/src/uts/common/os/vmem.c (revision 8b87c15576a5138f88a969448b43561bf5968c09)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2010 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*
27  * Copyright (c) 2012 by Delphix. All rights reserved.
28  * Copyright (c) 2012, Joyent, Inc. All rights reserved.
29  */
30 
31 /*
32  * Big Theory Statement for the virtual memory allocator.
33  *
34  * For a more complete description of the main ideas, see:
35  *
36  *	Jeff Bonwick and Jonathan Adams,
37  *
38  *	Magazines and vmem: Extending the Slab Allocator to Many CPUs and
39  *	Arbitrary Resources.
40  *
41  *	Proceedings of the 2001 Usenix Conference.
42  *	Available as http://www.usenix.org/event/usenix01/bonwick.html
43  *
44  *
45  * 1. General Concepts
46  * -------------------
47  *
48  * 1.1 Overview
49  * ------------
50  * We divide the kernel address space into a number of logically distinct
51  * pieces, or *arenas*: text, data, heap, stack, and so on.  Within these
52  * arenas we often subdivide further; for example, we use heap addresses
53  * not only for the kernel heap (kmem_alloc() space), but also for DVMA,
54  * bp_mapin(), /dev/kmem, and even some device mappings like the TOD chip.
55  * The kernel address space, therefore, is most accurately described as
56  * a tree of arenas in which each node of the tree *imports* some subset
57  * of its parent.  The virtual memory allocator manages these arenas and
58  * supports their natural hierarchical structure.
59  *
60  * 1.2 Arenas
61  * ----------
62  * An arena is nothing more than a set of integers.  These integers most
63  * commonly represent virtual addresses, but in fact they can represent
64  * anything at all.  For example, we could use an arena containing the
65  * integers minpid through maxpid to allocate process IDs.  vmem_create()
66  * and vmem_destroy() create and destroy vmem arenas.  In order to
67  * differentiate between arenas used for adresses and arenas used for
68  * identifiers, the VMC_IDENTIFIER flag is passed to vmem_create().  This
69  * prevents identifier exhaustion from being diagnosed as general memory
70  * failure.
71  *
72  * 1.3 Spans
73  * ---------
74  * We represent the integers in an arena as a collection of *spans*, or
75  * contiguous ranges of integers.  For example, the kernel heap consists
76  * of just one span: [kernelheap, ekernelheap).  Spans can be added to an
77  * arena in two ways: explicitly, by vmem_add(), or implicitly, by
78  * importing, as described in Section 1.5 below.
79  *
80  * 1.4 Segments
81  * ------------
82  * Spans are subdivided into *segments*, each of which is either allocated
83  * or free.  A segment, like a span, is a contiguous range of integers.
84  * Each allocated segment [addr, addr + size) represents exactly one
85  * vmem_alloc(size) that returned addr.  Free segments represent the space
86  * between allocated segments.  If two free segments are adjacent, we
87  * coalesce them into one larger segment; that is, if segments [a, b) and
88  * [b, c) are both free, we merge them into a single segment [a, c).
89  * The segments within a span are linked together in increasing-address order
90  * so we can easily determine whether coalescing is possible.
91  *
92  * Segments never cross span boundaries.  When all segments within
93  * an imported span become free, we return the span to its source.
94  *
95  * 1.5 Imported Memory
96  * -------------------
97  * As mentioned in the overview, some arenas are logical subsets of
98  * other arenas.  For example, kmem_va_arena (a virtual address cache
99  * that satisfies most kmem_slab_create() requests) is just a subset
100  * of heap_arena (the kernel heap) that provides caching for the most
101  * common slab sizes.  When kmem_va_arena runs out of virtual memory,
102  * it *imports* more from the heap; we say that heap_arena is the
103  * *vmem source* for kmem_va_arena.  vmem_create() allows you to
104  * specify any existing vmem arena as the source for your new arena.
105  * Topologically, since every arena is a child of at most one source,
106  * the set of all arenas forms a collection of trees.
107  *
108  * 1.6 Constrained Allocations
109  * ---------------------------
110  * Some vmem clients are quite picky about the kind of address they want.
111  * For example, the DVMA code may need an address that is at a particular
112  * phase with respect to some alignment (to get good cache coloring), or
113  * that lies within certain limits (the addressable range of a device),
114  * or that doesn't cross some boundary (a DMA counter restriction) --
115  * or all of the above.  vmem_xalloc() allows the client to specify any
116  * or all of these constraints.
117  *
118  * 1.7 The Vmem Quantum
119  * --------------------
120  * Every arena has a notion of 'quantum', specified at vmem_create() time,
121  * that defines the arena's minimum unit of currency.  Most commonly the
122  * quantum is either 1 or PAGESIZE, but any power of 2 is legal.
123  * All vmem allocations are guaranteed to be quantum-aligned.
124  *
125  * 1.8 Quantum Caching
126  * -------------------
127  * A vmem arena may be so hot (frequently used) that the scalability of vmem
128  * allocation is a significant concern.  We address this by allowing the most
129  * common allocation sizes to be serviced by the kernel memory allocator,
130  * which provides low-latency per-cpu caching.  The qcache_max argument to
131  * vmem_create() specifies the largest allocation size to cache.
132  *
133  * 1.9 Relationship to Kernel Memory Allocator
134  * -------------------------------------------
135  * Every kmem cache has a vmem arena as its slab supplier.  The kernel memory
136  * allocator uses vmem_alloc() and vmem_free() to create and destroy slabs.
137  *
138  *
139  * 2. Implementation
140  * -----------------
141  *
142  * 2.1 Segment lists and markers
143  * -----------------------------
144  * The segment structure (vmem_seg_t) contains two doubly-linked lists.
145  *
146  * The arena list (vs_anext/vs_aprev) links all segments in the arena.
147  * In addition to the allocated and free segments, the arena contains
148  * special marker segments at span boundaries.  Span markers simplify
149  * coalescing and importing logic by making it easy to tell both when
150  * we're at a span boundary (so we don't coalesce across it), and when
151  * a span is completely free (its neighbors will both be span markers).
152  *
153  * Imported spans will have vs_import set.
154  *
155  * The next-of-kin list (vs_knext/vs_kprev) links segments of the same type:
156  * (1) for allocated segments, vs_knext is the hash chain linkage;
157  * (2) for free segments, vs_knext is the freelist linkage;
158  * (3) for span marker segments, vs_knext is the next span marker.
159  *
160  * 2.2 Allocation hashing
161  * ----------------------
162  * We maintain a hash table of all allocated segments, hashed by address.
163  * This allows vmem_free() to discover the target segment in constant time.
164  * vmem_update() periodically resizes hash tables to keep hash chains short.
165  *
166  * 2.3 Freelist management
167  * -----------------------
168  * We maintain power-of-2 freelists for free segments, i.e. free segments
169  * of size >= 2^n reside in vmp->vm_freelist[n].  To ensure constant-time
170  * allocation, vmem_xalloc() looks not in the first freelist that *might*
171  * satisfy the allocation, but in the first freelist that *definitely*
172  * satisfies the allocation (unless VM_BESTFIT is specified, or all larger
173  * freelists are empty).  For example, a 1000-byte allocation will be
174  * satisfied not from the 512..1023-byte freelist, whose members *might*
175  * contains a 1000-byte segment, but from a 1024-byte or larger freelist,
176  * the first member of which will *definitely* satisfy the allocation.
177  * This ensures that vmem_xalloc() works in constant time.
178  *
179  * We maintain a bit map to determine quickly which freelists are non-empty.
180  * vmp->vm_freemap & (1 << n) is non-zero iff vmp->vm_freelist[n] is non-empty.
181  *
182  * The different freelists are linked together into one large freelist,
183  * with the freelist heads serving as markers.  Freelist markers simplify
184  * the maintenance of vm_freemap by making it easy to tell when we're taking
185  * the last member of a freelist (both of its neighbors will be markers).
186  *
187  * 2.4 Vmem Locking
188  * ----------------
189  * For simplicity, all arena state is protected by a per-arena lock.
190  * For very hot arenas, use quantum caching for scalability.
191  *
192  * 2.5 Vmem Population
193  * -------------------
194  * Any internal vmem routine that might need to allocate new segment
195  * structures must prepare in advance by calling vmem_populate(), which
196  * will preallocate enough vmem_seg_t's to get is through the entire
197  * operation without dropping the arena lock.
198  *
199  * 2.6 Auditing
200  * ------------
201  * If KMF_AUDIT is set in kmem_flags, we audit vmem allocations as well.
202  * Since virtual addresses cannot be scribbled on, there is no equivalent
203  * in vmem to redzone checking, deadbeef, or other kmem debugging features.
204  * Moreover, we do not audit frees because segment coalescing destroys the
205  * association between an address and its segment structure.  Auditing is
206  * thus intended primarily to keep track of who's consuming the arena.
207  * Debugging support could certainly be extended in the future if it proves
208  * necessary, but we do so much live checking via the allocation hash table
209  * that even non-DEBUG systems get quite a bit of sanity checking already.
210  */
211 
212 #include <sys/vmem_impl.h>
213 #include <sys/kmem.h>
214 #include <sys/kstat.h>
215 #include <sys/param.h>
216 #include <sys/systm.h>
217 #include <sys/atomic.h>
218 #include <sys/bitmap.h>
219 #include <sys/sysmacros.h>
220 #include <sys/cmn_err.h>
221 #include <sys/debug.h>
222 #include <sys/panic.h>
223 
224 #define	VMEM_INITIAL		10	/* early vmem arenas */
225 #define	VMEM_SEG_INITIAL	200	/* early segments */
226 
227 /*
228  * Adding a new span to an arena requires two segment structures: one to
229  * represent the span, and one to represent the free segment it contains.
230  */
231 #define	VMEM_SEGS_PER_SPAN_CREATE	2
232 
233 /*
234  * Allocating a piece of an existing segment requires 0-2 segment structures
235  * depending on how much of the segment we're allocating.
236  *
237  * To allocate the entire segment, no new segment structures are needed; we
238  * simply move the existing segment structure from the freelist to the
239  * allocation hash table.
240  *
241  * To allocate a piece from the left or right end of the segment, we must
242  * split the segment into two pieces (allocated part and remainder), so we
243  * need one new segment structure to represent the remainder.
244  *
245  * To allocate from the middle of a segment, we need two new segment strucures
246  * to represent the remainders on either side of the allocated part.
247  */
248 #define	VMEM_SEGS_PER_EXACT_ALLOC	0
249 #define	VMEM_SEGS_PER_LEFT_ALLOC	1
250 #define	VMEM_SEGS_PER_RIGHT_ALLOC	1
251 #define	VMEM_SEGS_PER_MIDDLE_ALLOC	2
252 
253 /*
254  * vmem_populate() preallocates segment structures for vmem to do its work.
255  * It must preallocate enough for the worst case, which is when we must import
256  * a new span and then allocate from the middle of it.
257  */
258 #define	VMEM_SEGS_PER_ALLOC_MAX		\
259 	(VMEM_SEGS_PER_SPAN_CREATE + VMEM_SEGS_PER_MIDDLE_ALLOC)
260 
261 /*
262  * The segment structures themselves are allocated from vmem_seg_arena, so
263  * we have a recursion problem when vmem_seg_arena needs to populate itself.
264  * We address this by working out the maximum number of segment structures
265  * this act will require, and multiplying by the maximum number of threads
266  * that we'll allow to do it simultaneously.
267  *
268  * The worst-case segment consumption to populate vmem_seg_arena is as
269  * follows (depicted as a stack trace to indicate why events are occurring):
270  *
271  * (In order to lower the fragmentation in the heap_arena, we specify a
272  * minimum import size for the vmem_metadata_arena which is the same size
273  * as the kmem_va quantum cache allocations.  This causes the worst-case
274  * allocation from the vmem_metadata_arena to be 3 segments.)
275  *
276  * vmem_alloc(vmem_seg_arena)		-> 2 segs (span create + exact alloc)
277  *  segkmem_alloc(vmem_metadata_arena)
278  *   vmem_alloc(vmem_metadata_arena)	-> 3 segs (span create + left alloc)
279  *    vmem_alloc(heap_arena)		-> 1 seg (left alloc)
280  *   page_create()
281  *   hat_memload()
282  *    kmem_cache_alloc()
283  *     kmem_slab_create()
284  *	vmem_alloc(hat_memload_arena)	-> 2 segs (span create + exact alloc)
285  *	 segkmem_alloc(heap_arena)
286  *	  vmem_alloc(heap_arena)	-> 1 seg (left alloc)
287  *	  page_create()
288  *	  hat_memload()		-> (hat layer won't recurse further)
289  *
290  * The worst-case consumption for each arena is 3 segment structures.
291  * Of course, a 3-seg reserve could easily be blown by multiple threads.
292  * Therefore, we serialize all allocations from vmem_seg_arena (which is OK
293  * because they're rare).  We cannot allow a non-blocking allocation to get
294  * tied up behind a blocking allocation, however, so we use separate locks
295  * for VM_SLEEP and VM_NOSLEEP allocations.  Similarly, VM_PUSHPAGE allocations
296  * must not block behind ordinary VM_SLEEPs.  In addition, if the system is
297  * panicking then we must keep enough resources for panic_thread to do its
298  * work.  Thus we have at most four threads trying to allocate from
299  * vmem_seg_arena, and each thread consumes at most three segment structures,
300  * so we must maintain a 12-seg reserve.
301  */
302 #define	VMEM_POPULATE_RESERVE	12
303 
304 /*
305  * vmem_populate() ensures that each arena has VMEM_MINFREE seg structures
306  * so that it can satisfy the worst-case allocation *and* participate in
307  * worst-case allocation from vmem_seg_arena.
308  */
309 #define	VMEM_MINFREE	(VMEM_POPULATE_RESERVE + VMEM_SEGS_PER_ALLOC_MAX)
310 
311 static vmem_t vmem0[VMEM_INITIAL];
312 static vmem_t *vmem_populator[VMEM_INITIAL];
313 static uint32_t vmem_id;
314 static uint32_t vmem_populators;
315 static vmem_seg_t vmem_seg0[VMEM_SEG_INITIAL];
316 static vmem_seg_t *vmem_segfree;
317 static kmutex_t vmem_list_lock;
318 static kmutex_t vmem_segfree_lock;
319 static kmutex_t vmem_sleep_lock;
320 static kmutex_t vmem_nosleep_lock;
321 static kmutex_t vmem_pushpage_lock;
322 static kmutex_t vmem_panic_lock;
323 static vmem_t *vmem_list;
324 static vmem_t *vmem_metadata_arena;
325 static vmem_t *vmem_seg_arena;
326 static vmem_t *vmem_hash_arena;
327 static vmem_t *vmem_vmem_arena;
328 static long vmem_update_interval = 15;	/* vmem_update() every 15 seconds */
329 uint32_t vmem_mtbf;		/* mean time between failures [default: off] */
330 size_t vmem_seg_size = sizeof (vmem_seg_t);
331 
332 static vmem_kstat_t vmem_kstat_template = {
333 	{ "mem_inuse",		KSTAT_DATA_UINT64 },
334 	{ "mem_import",		KSTAT_DATA_UINT64 },
335 	{ "mem_total",		KSTAT_DATA_UINT64 },
336 	{ "vmem_source",	KSTAT_DATA_UINT32 },
337 	{ "alloc",		KSTAT_DATA_UINT64 },
338 	{ "free",		KSTAT_DATA_UINT64 },
339 	{ "wait",		KSTAT_DATA_UINT64 },
340 	{ "fail",		KSTAT_DATA_UINT64 },
341 	{ "lookup",		KSTAT_DATA_UINT64 },
342 	{ "search",		KSTAT_DATA_UINT64 },
343 	{ "populate_wait",	KSTAT_DATA_UINT64 },
344 	{ "populate_fail",	KSTAT_DATA_UINT64 },
345 	{ "contains",		KSTAT_DATA_UINT64 },
346 	{ "contains_search",	KSTAT_DATA_UINT64 },
347 };
348 
349 /*
350  * Insert/delete from arena list (type 'a') or next-of-kin list (type 'k').
351  */
352 #define	VMEM_INSERT(vprev, vsp, type)					\
353 {									\
354 	vmem_seg_t *vnext = (vprev)->vs_##type##next;			\
355 	(vsp)->vs_##type##next = (vnext);				\
356 	(vsp)->vs_##type##prev = (vprev);				\
357 	(vprev)->vs_##type##next = (vsp);				\
358 	(vnext)->vs_##type##prev = (vsp);				\
359 }
360 
361 #define	VMEM_DELETE(vsp, type)						\
362 {									\
363 	vmem_seg_t *vprev = (vsp)->vs_##type##prev;			\
364 	vmem_seg_t *vnext = (vsp)->vs_##type##next;			\
365 	(vprev)->vs_##type##next = (vnext);				\
366 	(vnext)->vs_##type##prev = (vprev);				\
367 }
368 
369 /*
370  * Get a vmem_seg_t from the global segfree list.
371  */
372 static vmem_seg_t *
373 vmem_getseg_global(void)
374 {
375 	vmem_seg_t *vsp;
376 
377 	mutex_enter(&vmem_segfree_lock);
378 	if ((vsp = vmem_segfree) != NULL)
379 		vmem_segfree = vsp->vs_knext;
380 	mutex_exit(&vmem_segfree_lock);
381 
382 	return (vsp);
383 }
384 
385 /*
386  * Put a vmem_seg_t on the global segfree list.
387  */
388 static void
389 vmem_putseg_global(vmem_seg_t *vsp)
390 {
391 	mutex_enter(&vmem_segfree_lock);
392 	vsp->vs_knext = vmem_segfree;
393 	vmem_segfree = vsp;
394 	mutex_exit(&vmem_segfree_lock);
395 }
396 
397 /*
398  * Get a vmem_seg_t from vmp's segfree list.
399  */
400 static vmem_seg_t *
401 vmem_getseg(vmem_t *vmp)
402 {
403 	vmem_seg_t *vsp;
404 
405 	ASSERT(vmp->vm_nsegfree > 0);
406 
407 	vsp = vmp->vm_segfree;
408 	vmp->vm_segfree = vsp->vs_knext;
409 	vmp->vm_nsegfree--;
410 
411 	return (vsp);
412 }
413 
414 /*
415  * Put a vmem_seg_t on vmp's segfree list.
416  */
417 static void
418 vmem_putseg(vmem_t *vmp, vmem_seg_t *vsp)
419 {
420 	vsp->vs_knext = vmp->vm_segfree;
421 	vmp->vm_segfree = vsp;
422 	vmp->vm_nsegfree++;
423 }
424 
425 /*
426  * Add vsp to the appropriate freelist.
427  */
428 static void
429 vmem_freelist_insert(vmem_t *vmp, vmem_seg_t *vsp)
430 {
431 	vmem_seg_t *vprev;
432 
433 	ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);
434 
435 	vprev = (vmem_seg_t *)&vmp->vm_freelist[highbit(VS_SIZE(vsp)) - 1];
436 	vsp->vs_type = VMEM_FREE;
437 	vmp->vm_freemap |= VS_SIZE(vprev);
438 	VMEM_INSERT(vprev, vsp, k);
439 
440 	cv_broadcast(&vmp->vm_cv);
441 }
442 
443 /*
444  * Take vsp from the freelist.
445  */
446 static void
447 vmem_freelist_delete(vmem_t *vmp, vmem_seg_t *vsp)
448 {
449 	ASSERT(*VMEM_HASH(vmp, vsp->vs_start) != vsp);
450 	ASSERT(vsp->vs_type == VMEM_FREE);
451 
452 	if (vsp->vs_knext->vs_start == 0 && vsp->vs_kprev->vs_start == 0) {
453 		/*
454 		 * The segments on both sides of 'vsp' are freelist heads,
455 		 * so taking vsp leaves the freelist at vsp->vs_kprev empty.
456 		 */
457 		ASSERT(vmp->vm_freemap & VS_SIZE(vsp->vs_kprev));
458 		vmp->vm_freemap ^= VS_SIZE(vsp->vs_kprev);
459 	}
460 	VMEM_DELETE(vsp, k);
461 }
462 
463 /*
464  * Add vsp to the allocated-segment hash table and update kstats.
465  */
466 static void
467 vmem_hash_insert(vmem_t *vmp, vmem_seg_t *vsp)
468 {
469 	vmem_seg_t **bucket;
470 
471 	vsp->vs_type = VMEM_ALLOC;
472 	bucket = VMEM_HASH(vmp, vsp->vs_start);
473 	vsp->vs_knext = *bucket;
474 	*bucket = vsp;
475 
476 	if (vmem_seg_size == sizeof (vmem_seg_t)) {
477 		vsp->vs_depth = (uint8_t)getpcstack(vsp->vs_stack,
478 		    VMEM_STACK_DEPTH);
479 		vsp->vs_thread = curthread;
480 		vsp->vs_timestamp = gethrtime();
481 	} else {
482 		vsp->vs_depth = 0;
483 	}
484 
485 	vmp->vm_kstat.vk_alloc.value.ui64++;
486 	vmp->vm_kstat.vk_mem_inuse.value.ui64 += VS_SIZE(vsp);
487 }
488 
489 /*
490  * Remove vsp from the allocated-segment hash table and update kstats.
491  */
492 static vmem_seg_t *
493 vmem_hash_delete(vmem_t *vmp, uintptr_t addr, size_t size)
494 {
495 	vmem_seg_t *vsp, **prev_vspp;
496 
497 	prev_vspp = VMEM_HASH(vmp, addr);
498 	while ((vsp = *prev_vspp) != NULL) {
499 		if (vsp->vs_start == addr) {
500 			*prev_vspp = vsp->vs_knext;
501 			break;
502 		}
503 		vmp->vm_kstat.vk_lookup.value.ui64++;
504 		prev_vspp = &vsp->vs_knext;
505 	}
506 
507 	if (vsp == NULL)
508 		panic("vmem_hash_delete(%p, %lx, %lu): bad free",
509 		    (void *)vmp, addr, size);
510 	if (VS_SIZE(vsp) != size)
511 		panic("vmem_hash_delete(%p, %lx, %lu): wrong size (expect %lu)",
512 		    (void *)vmp, addr, size, VS_SIZE(vsp));
513 
514 	vmp->vm_kstat.vk_free.value.ui64++;
515 	vmp->vm_kstat.vk_mem_inuse.value.ui64 -= size;
516 
517 	return (vsp);
518 }
519 
520 /*
521  * Create a segment spanning the range [start, end) and add it to the arena.
522  */
523 static vmem_seg_t *
524 vmem_seg_create(vmem_t *vmp, vmem_seg_t *vprev, uintptr_t start, uintptr_t end)
525 {
526 	vmem_seg_t *newseg = vmem_getseg(vmp);
527 
528 	newseg->vs_start = start;
529 	newseg->vs_end = end;
530 	newseg->vs_type = 0;
531 	newseg->vs_import = 0;
532 
533 	VMEM_INSERT(vprev, newseg, a);
534 
535 	return (newseg);
536 }
537 
538 /*
539  * Remove segment vsp from the arena.
540  */
541 static void
542 vmem_seg_destroy(vmem_t *vmp, vmem_seg_t *vsp)
543 {
544 	ASSERT(vsp->vs_type != VMEM_ROTOR);
545 	VMEM_DELETE(vsp, a);
546 
547 	vmem_putseg(vmp, vsp);
548 }
549 
550 /*
551  * Add the span [vaddr, vaddr + size) to vmp and update kstats.
552  */
553 static vmem_seg_t *
554 vmem_span_create(vmem_t *vmp, void *vaddr, size_t size, uint8_t import)
555 {
556 	vmem_seg_t *newseg, *span;
557 	uintptr_t start = (uintptr_t)vaddr;
558 	uintptr_t end = start + size;
559 
560 	ASSERT(MUTEX_HELD(&vmp->vm_lock));
561 
562 	if ((start | end) & (vmp->vm_quantum - 1))
563 		panic("vmem_span_create(%p, %p, %lu): misaligned",
564 		    (void *)vmp, vaddr, size);
565 
566 	span = vmem_seg_create(vmp, vmp->vm_seg0.vs_aprev, start, end);
567 	span->vs_type = VMEM_SPAN;
568 	span->vs_import = import;
569 	VMEM_INSERT(vmp->vm_seg0.vs_kprev, span, k);
570 
571 	newseg = vmem_seg_create(vmp, span, start, end);
572 	vmem_freelist_insert(vmp, newseg);
573 
574 	if (import)
575 		vmp->vm_kstat.vk_mem_import.value.ui64 += size;
576 	vmp->vm_kstat.vk_mem_total.value.ui64 += size;
577 
578 	return (newseg);
579 }
580 
581 /*
582  * Remove span vsp from vmp and update kstats.
583  */
584 static void
585 vmem_span_destroy(vmem_t *vmp, vmem_seg_t *vsp)
586 {
587 	vmem_seg_t *span = vsp->vs_aprev;
588 	size_t size = VS_SIZE(vsp);
589 
590 	ASSERT(MUTEX_HELD(&vmp->vm_lock));
591 	ASSERT(span->vs_type == VMEM_SPAN);
592 
593 	if (span->vs_import)
594 		vmp->vm_kstat.vk_mem_import.value.ui64 -= size;
595 	vmp->vm_kstat.vk_mem_total.value.ui64 -= size;
596 
597 	VMEM_DELETE(span, k);
598 
599 	vmem_seg_destroy(vmp, vsp);
600 	vmem_seg_destroy(vmp, span);
601 }
602 
603 /*
604  * Allocate the subrange [addr, addr + size) from segment vsp.
605  * If there are leftovers on either side, place them on the freelist.
606  * Returns a pointer to the segment representing [addr, addr + size).
607  */
608 static vmem_seg_t *
609 vmem_seg_alloc(vmem_t *vmp, vmem_seg_t *vsp, uintptr_t addr, size_t size)
610 {
611 	uintptr_t vs_start = vsp->vs_start;
612 	uintptr_t vs_end = vsp->vs_end;
613 	size_t vs_size = vs_end - vs_start;
614 	size_t realsize = P2ROUNDUP(size, vmp->vm_quantum);
615 	uintptr_t addr_end = addr + realsize;
616 
617 	ASSERT(P2PHASE(vs_start, vmp->vm_quantum) == 0);
618 	ASSERT(P2PHASE(addr, vmp->vm_quantum) == 0);
619 	ASSERT(vsp->vs_type == VMEM_FREE);
620 	ASSERT(addr >= vs_start && addr_end - 1 <= vs_end - 1);
621 	ASSERT(addr - 1 <= addr_end - 1);
622 
623 	/*
624 	 * If we're allocating from the start of the segment, and the
625 	 * remainder will be on the same freelist, we can save quite
626 	 * a bit of work.
627 	 */
628 	if (P2SAMEHIGHBIT(vs_size, vs_size - realsize) && addr == vs_start) {
629 		ASSERT(highbit(vs_size) == highbit(vs_size - realsize));
630 		vsp->vs_start = addr_end;
631 		vsp = vmem_seg_create(vmp, vsp->vs_aprev, addr, addr + size);
632 		vmem_hash_insert(vmp, vsp);
633 		return (vsp);
634 	}
635 
636 	vmem_freelist_delete(vmp, vsp);
637 
638 	if (vs_end != addr_end)
639 		vmem_freelist_insert(vmp,
640 		    vmem_seg_create(vmp, vsp, addr_end, vs_end));
641 
642 	if (vs_start != addr)
643 		vmem_freelist_insert(vmp,
644 		    vmem_seg_create(vmp, vsp->vs_aprev, vs_start, addr));
645 
646 	vsp->vs_start = addr;
647 	vsp->vs_end = addr + size;
648 
649 	vmem_hash_insert(vmp, vsp);
650 	return (vsp);
651 }
652 
653 /*
654  * Returns 1 if we are populating, 0 otherwise.
655  * Call it if we want to prevent recursion from HAT.
656  */
657 int
658 vmem_is_populator()
659 {
660 	return (mutex_owner(&vmem_sleep_lock) == curthread ||
661 	    mutex_owner(&vmem_nosleep_lock) == curthread ||
662 	    mutex_owner(&vmem_pushpage_lock) == curthread ||
663 	    mutex_owner(&vmem_panic_lock) == curthread);
664 }
665 
666 /*
667  * Populate vmp's segfree list with VMEM_MINFREE vmem_seg_t structures.
668  */
669 static int
670 vmem_populate(vmem_t *vmp, int vmflag)
671 {
672 	char *p;
673 	vmem_seg_t *vsp;
674 	ssize_t nseg;
675 	size_t size;
676 	kmutex_t *lp;
677 	int i;
678 
679 	while (vmp->vm_nsegfree < VMEM_MINFREE &&
680 	    (vsp = vmem_getseg_global()) != NULL)
681 		vmem_putseg(vmp, vsp);
682 
683 	if (vmp->vm_nsegfree >= VMEM_MINFREE)
684 		return (1);
685 
686 	/*
687 	 * If we're already populating, tap the reserve.
688 	 */
689 	if (vmem_is_populator()) {
690 		ASSERT(vmp->vm_cflags & VMC_POPULATOR);
691 		return (1);
692 	}
693 
694 	mutex_exit(&vmp->vm_lock);
695 
696 	if (panic_thread == curthread)
697 		lp = &vmem_panic_lock;
698 	else if (vmflag & VM_NOSLEEP)
699 		lp = &vmem_nosleep_lock;
700 	else if (vmflag & VM_PUSHPAGE)
701 		lp = &vmem_pushpage_lock;
702 	else
703 		lp = &vmem_sleep_lock;
704 
705 	mutex_enter(lp);
706 
707 	nseg = VMEM_MINFREE + vmem_populators * VMEM_POPULATE_RESERVE;
708 	size = P2ROUNDUP(nseg * vmem_seg_size, vmem_seg_arena->vm_quantum);
709 	nseg = size / vmem_seg_size;
710 
711 	/*
712 	 * The following vmem_alloc() may need to populate vmem_seg_arena
713 	 * and all the things it imports from.  When doing so, it will tap
714 	 * each arena's reserve to prevent recursion (see the block comment
715 	 * above the definition of VMEM_POPULATE_RESERVE).
716 	 */
717 	p = vmem_alloc(vmem_seg_arena, size, vmflag & VM_KMFLAGS);
718 	if (p == NULL) {
719 		mutex_exit(lp);
720 		mutex_enter(&vmp->vm_lock);
721 		vmp->vm_kstat.vk_populate_fail.value.ui64++;
722 		return (0);
723 	}
724 
725 	/*
726 	 * Restock the arenas that may have been depleted during population.
727 	 */
728 	for (i = 0; i < vmem_populators; i++) {
729 		mutex_enter(&vmem_populator[i]->vm_lock);
730 		while (vmem_populator[i]->vm_nsegfree < VMEM_POPULATE_RESERVE)
731 			vmem_putseg(vmem_populator[i],
732 			    (vmem_seg_t *)(p + --nseg * vmem_seg_size));
733 		mutex_exit(&vmem_populator[i]->vm_lock);
734 	}
735 
736 	mutex_exit(lp);
737 	mutex_enter(&vmp->vm_lock);
738 
739 	/*
740 	 * Now take our own segments.
741 	 */
742 	ASSERT(nseg >= VMEM_MINFREE);
743 	while (vmp->vm_nsegfree < VMEM_MINFREE)
744 		vmem_putseg(vmp, (vmem_seg_t *)(p + --nseg * vmem_seg_size));
745 
746 	/*
747 	 * Give the remainder to charity.
748 	 */
749 	while (nseg > 0)
750 		vmem_putseg_global((vmem_seg_t *)(p + --nseg * vmem_seg_size));
751 
752 	return (1);
753 }
754 
755 /*
756  * Advance a walker from its previous position to 'afterme'.
757  * Note: may drop and reacquire vmp->vm_lock.
758  */
759 static void
760 vmem_advance(vmem_t *vmp, vmem_seg_t *walker, vmem_seg_t *afterme)
761 {
762 	vmem_seg_t *vprev = walker->vs_aprev;
763 	vmem_seg_t *vnext = walker->vs_anext;
764 	vmem_seg_t *vsp = NULL;
765 
766 	VMEM_DELETE(walker, a);
767 
768 	if (afterme != NULL)
769 		VMEM_INSERT(afterme, walker, a);
770 
771 	/*
772 	 * The walker segment's presence may have prevented its neighbors
773 	 * from coalescing.  If so, coalesce them now.
774 	 */
775 	if (vprev->vs_type == VMEM_FREE) {
776 		if (vnext->vs_type == VMEM_FREE) {
777 			ASSERT(vprev->vs_end == vnext->vs_start);
778 			vmem_freelist_delete(vmp, vnext);
779 			vmem_freelist_delete(vmp, vprev);
780 			vprev->vs_end = vnext->vs_end;
781 			vmem_freelist_insert(vmp, vprev);
782 			vmem_seg_destroy(vmp, vnext);
783 		}
784 		vsp = vprev;
785 	} else if (vnext->vs_type == VMEM_FREE) {
786 		vsp = vnext;
787 	}
788 
789 	/*
790 	 * vsp could represent a complete imported span,
791 	 * in which case we must return it to the source.
792 	 */
793 	if (vsp != NULL && vsp->vs_aprev->vs_import &&
794 	    vmp->vm_source_free != NULL &&
795 	    vsp->vs_aprev->vs_type == VMEM_SPAN &&
796 	    vsp->vs_anext->vs_type == VMEM_SPAN) {
797 		void *vaddr = (void *)vsp->vs_start;
798 		size_t size = VS_SIZE(vsp);
799 		ASSERT(size == VS_SIZE(vsp->vs_aprev));
800 		vmem_freelist_delete(vmp, vsp);
801 		vmem_span_destroy(vmp, vsp);
802 		mutex_exit(&vmp->vm_lock);
803 		vmp->vm_source_free(vmp->vm_source, vaddr, size);
804 		mutex_enter(&vmp->vm_lock);
805 	}
806 }
807 
808 /*
809  * VM_NEXTFIT allocations deliberately cycle through all virtual addresses
810  * in an arena, so that we avoid reusing addresses for as long as possible.
811  * This helps to catch used-after-freed bugs.  It's also the perfect policy
812  * for allocating things like process IDs, where we want to cycle through
813  * all values in order.
814  */
815 static void *
816 vmem_nextfit_alloc(vmem_t *vmp, size_t size, int vmflag)
817 {
818 	vmem_seg_t *vsp, *rotor;
819 	uintptr_t addr;
820 	size_t realsize = P2ROUNDUP(size, vmp->vm_quantum);
821 	size_t vs_size;
822 
823 	mutex_enter(&vmp->vm_lock);
824 
825 	if (vmp->vm_nsegfree < VMEM_MINFREE && !vmem_populate(vmp, vmflag)) {
826 		mutex_exit(&vmp->vm_lock);
827 		return (NULL);
828 	}
829 
830 	/*
831 	 * The common case is that the segment right after the rotor is free,
832 	 * and large enough that extracting 'size' bytes won't change which
833 	 * freelist it's on.  In this case we can avoid a *lot* of work.
834 	 * Instead of the normal vmem_seg_alloc(), we just advance the start
835 	 * address of the victim segment.  Instead of moving the rotor, we
836 	 * create the new segment structure *behind the rotor*, which has
837 	 * the same effect.  And finally, we know we don't have to coalesce
838 	 * the rotor's neighbors because the new segment lies between them.
839 	 */
840 	rotor = &vmp->vm_rotor;
841 	vsp = rotor->vs_anext;
842 	if (vsp->vs_type == VMEM_FREE && (vs_size = VS_SIZE(vsp)) > realsize &&
843 	    P2SAMEHIGHBIT(vs_size, vs_size - realsize)) {
844 		ASSERT(highbit(vs_size) == highbit(vs_size - realsize));
845 		addr = vsp->vs_start;
846 		vsp->vs_start = addr + realsize;
847 		vmem_hash_insert(vmp,
848 		    vmem_seg_create(vmp, rotor->vs_aprev, addr, addr + size));
849 		mutex_exit(&vmp->vm_lock);
850 		return ((void *)addr);
851 	}
852 
853 	/*
854 	 * Starting at the rotor, look for a segment large enough to
855 	 * satisfy the allocation.
856 	 */
857 	for (;;) {
858 		vmp->vm_kstat.vk_search.value.ui64++;
859 		if (vsp->vs_type == VMEM_FREE && VS_SIZE(vsp) >= size)
860 			break;
861 		vsp = vsp->vs_anext;
862 		if (vsp == rotor) {
863 			/*
864 			 * We've come full circle.  One possibility is that the
865 			 * there's actually enough space, but the rotor itself
866 			 * is preventing the allocation from succeeding because
867 			 * it's sitting between two free segments.  Therefore,
868 			 * we advance the rotor and see if that liberates a
869 			 * suitable segment.
870 			 */
871 			vmem_advance(vmp, rotor, rotor->vs_anext);
872 			vsp = rotor->vs_aprev;
873 			if (vsp->vs_type == VMEM_FREE && VS_SIZE(vsp) >= size)
874 				break;
875 			/*
876 			 * If there's a lower arena we can import from, or it's
877 			 * a VM_NOSLEEP allocation, let vmem_xalloc() handle it.
878 			 * Otherwise, wait until another thread frees something.
879 			 */
880 			if (vmp->vm_source_alloc != NULL ||
881 			    (vmflag & VM_NOSLEEP)) {
882 				mutex_exit(&vmp->vm_lock);
883 				return (vmem_xalloc(vmp, size, vmp->vm_quantum,
884 				    0, 0, NULL, NULL, vmflag & VM_KMFLAGS));
885 			}
886 			vmp->vm_kstat.vk_wait.value.ui64++;
887 			cv_wait(&vmp->vm_cv, &vmp->vm_lock);
888 			vsp = rotor->vs_anext;
889 		}
890 	}
891 
892 	/*
893 	 * We found a segment.  Extract enough space to satisfy the allocation.
894 	 */
895 	addr = vsp->vs_start;
896 	vsp = vmem_seg_alloc(vmp, vsp, addr, size);
897 	ASSERT(vsp->vs_type == VMEM_ALLOC &&
898 	    vsp->vs_start == addr && vsp->vs_end == addr + size);
899 
900 	/*
901 	 * Advance the rotor to right after the newly-allocated segment.
902 	 * That's where the next VM_NEXTFIT allocation will begin searching.
903 	 */
904 	vmem_advance(vmp, rotor, vsp);
905 	mutex_exit(&vmp->vm_lock);
906 	return ((void *)addr);
907 }
908 
909 /*
910  * Checks if vmp is guaranteed to have a size-byte buffer somewhere on its
911  * freelist.  If size is not a power-of-2, it can return a false-negative.
912  *
913  * Used to decide if a newly imported span is superfluous after re-acquiring
914  * the arena lock.
915  */
916 static int
917 vmem_canalloc(vmem_t *vmp, size_t size)
918 {
919 	int hb;
920 	int flist = 0;
921 	ASSERT(MUTEX_HELD(&vmp->vm_lock));
922 
923 	if (ISP2(size))
924 		flist = lowbit(P2ALIGN(vmp->vm_freemap, size));
925 	else if ((hb = highbit(size)) < VMEM_FREELISTS)
926 		flist = lowbit(P2ALIGN(vmp->vm_freemap, 1UL << hb));
927 
928 	return (flist);
929 }
930 
931 /*
932  * Allocate size bytes at offset phase from an align boundary such that the
933  * resulting segment [addr, addr + size) is a subset of [minaddr, maxaddr)
934  * that does not straddle a nocross-aligned boundary.
935  */
936 void *
937 vmem_xalloc(vmem_t *vmp, size_t size, size_t align_arg, size_t phase,
938 	size_t nocross, void *minaddr, void *maxaddr, int vmflag)
939 {
940 	vmem_seg_t *vsp;
941 	vmem_seg_t *vbest = NULL;
942 	uintptr_t addr, taddr, start, end;
943 	uintptr_t align = (align_arg != 0) ? align_arg : vmp->vm_quantum;
944 	void *vaddr, *xvaddr = NULL;
945 	size_t xsize;
946 	int hb, flist, resv;
947 	uint32_t mtbf;
948 
949 	if ((align | phase | nocross) & (vmp->vm_quantum - 1))
950 		panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
951 		    "parameters not vm_quantum aligned",
952 		    (void *)vmp, size, align_arg, phase, nocross,
953 		    minaddr, maxaddr, vmflag);
954 
955 	if (nocross != 0 &&
956 	    (align > nocross || P2ROUNDUP(phase + size, align) > nocross))
957 		panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
958 		    "overconstrained allocation",
959 		    (void *)vmp, size, align_arg, phase, nocross,
960 		    minaddr, maxaddr, vmflag);
961 
962 	if (phase >= align || !ISP2(align) || !ISP2(nocross))
963 		panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
964 		    "parameters inconsistent or invalid",
965 		    (void *)vmp, size, align_arg, phase, nocross,
966 		    minaddr, maxaddr, vmflag);
967 
968 	if ((mtbf = vmem_mtbf | vmp->vm_mtbf) != 0 && gethrtime() % mtbf == 0 &&
969 	    (vmflag & (VM_NOSLEEP | VM_PANIC)) == VM_NOSLEEP)
970 		return (NULL);
971 
972 	mutex_enter(&vmp->vm_lock);
973 	for (;;) {
974 		if (vmp->vm_nsegfree < VMEM_MINFREE &&
975 		    !vmem_populate(vmp, vmflag))
976 			break;
977 do_alloc:
978 		/*
979 		 * highbit() returns the highest bit + 1, which is exactly
980 		 * what we want: we want to search the first freelist whose
981 		 * members are *definitely* large enough to satisfy our
982 		 * allocation.  However, there are certain cases in which we
983 		 * want to look at the next-smallest freelist (which *might*
984 		 * be able to satisfy the allocation):
985 		 *
986 		 * (1)	The size is exactly a power of 2, in which case
987 		 *	the smaller freelist is always big enough;
988 		 *
989 		 * (2)	All other freelists are empty;
990 		 *
991 		 * (3)	We're in the highest possible freelist, which is
992 		 *	always empty (e.g. the 4GB freelist on 32-bit systems);
993 		 *
994 		 * (4)	We're doing a best-fit or first-fit allocation.
995 		 */
996 		if (ISP2(size)) {
997 			flist = lowbit(P2ALIGN(vmp->vm_freemap, size));
998 		} else {
999 			hb = highbit(size);
1000 			if ((vmp->vm_freemap >> hb) == 0 ||
1001 			    hb == VMEM_FREELISTS ||
1002 			    (vmflag & (VM_BESTFIT | VM_FIRSTFIT)))
1003 				hb--;
1004 			flist = lowbit(P2ALIGN(vmp->vm_freemap, 1UL << hb));
1005 		}
1006 
1007 		for (vbest = NULL, vsp = (flist == 0) ? NULL :
1008 		    vmp->vm_freelist[flist - 1].vs_knext;
1009 		    vsp != NULL; vsp = vsp->vs_knext) {
1010 			vmp->vm_kstat.vk_search.value.ui64++;
1011 			if (vsp->vs_start == 0) {
1012 				/*
1013 				 * We're moving up to a larger freelist,
1014 				 * so if we've already found a candidate,
1015 				 * the fit can't possibly get any better.
1016 				 */
1017 				if (vbest != NULL)
1018 					break;
1019 				/*
1020 				 * Find the next non-empty freelist.
1021 				 */
1022 				flist = lowbit(P2ALIGN(vmp->vm_freemap,
1023 				    VS_SIZE(vsp)));
1024 				if (flist-- == 0)
1025 					break;
1026 				vsp = (vmem_seg_t *)&vmp->vm_freelist[flist];
1027 				ASSERT(vsp->vs_knext->vs_type == VMEM_FREE);
1028 				continue;
1029 			}
1030 			if (vsp->vs_end - 1 < (uintptr_t)minaddr)
1031 				continue;
1032 			if (vsp->vs_start > (uintptr_t)maxaddr - 1)
1033 				continue;
1034 			start = MAX(vsp->vs_start, (uintptr_t)minaddr);
1035 			end = MIN(vsp->vs_end - 1, (uintptr_t)maxaddr - 1) + 1;
1036 			taddr = P2PHASEUP(start, align, phase);
1037 			if (P2BOUNDARY(taddr, size, nocross))
1038 				taddr +=
1039 				    P2ROUNDUP(P2NPHASE(taddr, nocross), align);
1040 			if ((taddr - start) + size > end - start ||
1041 			    (vbest != NULL && VS_SIZE(vsp) >= VS_SIZE(vbest)))
1042 				continue;
1043 			vbest = vsp;
1044 			addr = taddr;
1045 			if (!(vmflag & VM_BESTFIT) || VS_SIZE(vbest) == size)
1046 				break;
1047 		}
1048 		if (vbest != NULL)
1049 			break;
1050 		ASSERT(xvaddr == NULL);
1051 		if (size == 0)
1052 			panic("vmem_xalloc(): size == 0");
1053 		if (vmp->vm_source_alloc != NULL && nocross == 0 &&
1054 		    minaddr == NULL && maxaddr == NULL) {
1055 			size_t aneeded, asize;
1056 			size_t aquantum = MAX(vmp->vm_quantum,
1057 			    vmp->vm_source->vm_quantum);
1058 			size_t aphase = phase;
1059 			if ((align > aquantum) &&
1060 			    !(vmp->vm_cflags & VMC_XALIGN)) {
1061 				aphase = (P2PHASE(phase, aquantum) != 0) ?
1062 				    align - vmp->vm_quantum : align - aquantum;
1063 				ASSERT(aphase >= phase);
1064 			}
1065 			aneeded = MAX(size + aphase, vmp->vm_min_import);
1066 			asize = P2ROUNDUP(aneeded, aquantum);
1067 
1068 			if (asize < size) {
1069 				/*
1070 				 * The rounding induced overflow; return NULL
1071 				 * if we are permitted to fail the allocation
1072 				 * (and explicitly panic if we aren't).
1073 				 */
1074 				if ((vmflag & VM_NOSLEEP) &&
1075 				    !(vmflag & VM_PANIC)) {
1076 					mutex_exit(&vmp->vm_lock);
1077 					return (NULL);
1078 				}
1079 
1080 				panic("vmem_xalloc(): size overflow");
1081 			}
1082 
1083 			/*
1084 			 * Determine how many segment structures we'll consume.
1085 			 * The calculation must be precise because if we're
1086 			 * here on behalf of vmem_populate(), we are taking
1087 			 * segments from a very limited reserve.
1088 			 */
1089 			if (size == asize && !(vmp->vm_cflags & VMC_XALLOC))
1090 				resv = VMEM_SEGS_PER_SPAN_CREATE +
1091 				    VMEM_SEGS_PER_EXACT_ALLOC;
1092 			else if (phase == 0 &&
1093 			    align <= vmp->vm_source->vm_quantum)
1094 				resv = VMEM_SEGS_PER_SPAN_CREATE +
1095 				    VMEM_SEGS_PER_LEFT_ALLOC;
1096 			else
1097 				resv = VMEM_SEGS_PER_ALLOC_MAX;
1098 
1099 			ASSERT(vmp->vm_nsegfree >= resv);
1100 			vmp->vm_nsegfree -= resv;	/* reserve our segs */
1101 			mutex_exit(&vmp->vm_lock);
1102 			if (vmp->vm_cflags & VMC_XALLOC) {
1103 				size_t oasize = asize;
1104 				vaddr = ((vmem_ximport_t *)
1105 				    vmp->vm_source_alloc)(vmp->vm_source,
1106 				    &asize, align, vmflag & VM_KMFLAGS);
1107 				ASSERT(asize >= oasize);
1108 				ASSERT(P2PHASE(asize,
1109 				    vmp->vm_source->vm_quantum) == 0);
1110 				ASSERT(!(vmp->vm_cflags & VMC_XALIGN) ||
1111 				    IS_P2ALIGNED(vaddr, align));
1112 			} else {
1113 				vaddr = vmp->vm_source_alloc(vmp->vm_source,
1114 				    asize, vmflag & VM_KMFLAGS);
1115 			}
1116 			mutex_enter(&vmp->vm_lock);
1117 			vmp->vm_nsegfree += resv;	/* claim reservation */
1118 			aneeded = size + align - vmp->vm_quantum;
1119 			aneeded = P2ROUNDUP(aneeded, vmp->vm_quantum);
1120 			if (vaddr != NULL) {
1121 				/*
1122 				 * Since we dropped the vmem lock while
1123 				 * calling the import function, other
1124 				 * threads could have imported space
1125 				 * and made our import unnecessary.  In
1126 				 * order to save space, we return
1127 				 * excess imports immediately.
1128 				 */
1129 				if (asize > aneeded &&
1130 				    vmp->vm_source_free != NULL &&
1131 				    vmem_canalloc(vmp, aneeded)) {
1132 					ASSERT(resv >=
1133 					    VMEM_SEGS_PER_MIDDLE_ALLOC);
1134 					xvaddr = vaddr;
1135 					xsize = asize;
1136 					goto do_alloc;
1137 				}
1138 				vbest = vmem_span_create(vmp, vaddr, asize, 1);
1139 				addr = P2PHASEUP(vbest->vs_start, align, phase);
1140 				break;
1141 			} else if (vmem_canalloc(vmp, aneeded)) {
1142 				/*
1143 				 * Our import failed, but another thread
1144 				 * added sufficient free memory to the arena
1145 				 * to satisfy our request.  Go back and
1146 				 * grab it.
1147 				 */
1148 				ASSERT(resv >= VMEM_SEGS_PER_MIDDLE_ALLOC);
1149 				goto do_alloc;
1150 			}
1151 		}
1152 
1153 		/*
1154 		 * If the requestor chooses to fail the allocation attempt
1155 		 * rather than reap wait and retry - get out of the loop.
1156 		 */
1157 		if (vmflag & VM_ABORT)
1158 			break;
1159 		mutex_exit(&vmp->vm_lock);
1160 		if (vmp->vm_cflags & VMC_IDENTIFIER)
1161 			kmem_reap_idspace();
1162 		else
1163 			kmem_reap();
1164 		mutex_enter(&vmp->vm_lock);
1165 		if (vmflag & VM_NOSLEEP)
1166 			break;
1167 		vmp->vm_kstat.vk_wait.value.ui64++;
1168 		cv_wait(&vmp->vm_cv, &vmp->vm_lock);
1169 	}
1170 	if (vbest != NULL) {
1171 		ASSERT(vbest->vs_type == VMEM_FREE);
1172 		ASSERT(vbest->vs_knext != vbest);
1173 		/* re-position to end of buffer */
1174 		if (vmflag & VM_ENDALLOC) {
1175 			addr += ((vbest->vs_end - (addr + size)) / align) *
1176 			    align;
1177 		}
1178 		(void) vmem_seg_alloc(vmp, vbest, addr, size);
1179 		mutex_exit(&vmp->vm_lock);
1180 		if (xvaddr)
1181 			vmp->vm_source_free(vmp->vm_source, xvaddr, xsize);
1182 		ASSERT(P2PHASE(addr, align) == phase);
1183 		ASSERT(!P2BOUNDARY(addr, size, nocross));
1184 		ASSERT(addr >= (uintptr_t)minaddr);
1185 		ASSERT(addr + size - 1 <= (uintptr_t)maxaddr - 1);
1186 		return ((void *)addr);
1187 	}
1188 	vmp->vm_kstat.vk_fail.value.ui64++;
1189 	mutex_exit(&vmp->vm_lock);
1190 	if (vmflag & VM_PANIC)
1191 		panic("vmem_xalloc(%p, %lu, %lu, %lu, %lu, %p, %p, %x): "
1192 		    "cannot satisfy mandatory allocation",
1193 		    (void *)vmp, size, align_arg, phase, nocross,
1194 		    minaddr, maxaddr, vmflag);
1195 	ASSERT(xvaddr == NULL);
1196 	return (NULL);
1197 }
1198 
1199 /*
1200  * Free the segment [vaddr, vaddr + size), where vaddr was a constrained
1201  * allocation.  vmem_xalloc() and vmem_xfree() must always be paired because
1202  * both routines bypass the quantum caches.
1203  */
1204 void
1205 vmem_xfree(vmem_t *vmp, void *vaddr, size_t size)
1206 {
1207 	vmem_seg_t *vsp, *vnext, *vprev;
1208 
1209 	mutex_enter(&vmp->vm_lock);
1210 
1211 	vsp = vmem_hash_delete(vmp, (uintptr_t)vaddr, size);
1212 	vsp->vs_end = P2ROUNDUP(vsp->vs_end, vmp->vm_quantum);
1213 
1214 	/*
1215 	 * Attempt to coalesce with the next segment.
1216 	 */
1217 	vnext = vsp->vs_anext;
1218 	if (vnext->vs_type == VMEM_FREE) {
1219 		ASSERT(vsp->vs_end == vnext->vs_start);
1220 		vmem_freelist_delete(vmp, vnext);
1221 		vsp->vs_end = vnext->vs_end;
1222 		vmem_seg_destroy(vmp, vnext);
1223 	}
1224 
1225 	/*
1226 	 * Attempt to coalesce with the previous segment.
1227 	 */
1228 	vprev = vsp->vs_aprev;
1229 	if (vprev->vs_type == VMEM_FREE) {
1230 		ASSERT(vprev->vs_end == vsp->vs_start);
1231 		vmem_freelist_delete(vmp, vprev);
1232 		vprev->vs_end = vsp->vs_end;
1233 		vmem_seg_destroy(vmp, vsp);
1234 		vsp = vprev;
1235 	}
1236 
1237 	/*
1238 	 * If the entire span is free, return it to the source.
1239 	 */
1240 	if (vsp->vs_aprev->vs_import && vmp->vm_source_free != NULL &&
1241 	    vsp->vs_aprev->vs_type == VMEM_SPAN &&
1242 	    vsp->vs_anext->vs_type == VMEM_SPAN) {
1243 		vaddr = (void *)vsp->vs_start;
1244 		size = VS_SIZE(vsp);
1245 		ASSERT(size == VS_SIZE(vsp->vs_aprev));
1246 		vmem_span_destroy(vmp, vsp);
1247 		mutex_exit(&vmp->vm_lock);
1248 		vmp->vm_source_free(vmp->vm_source, vaddr, size);
1249 	} else {
1250 		vmem_freelist_insert(vmp, vsp);
1251 		mutex_exit(&vmp->vm_lock);
1252 	}
1253 }
1254 
1255 /*
1256  * Allocate size bytes from arena vmp.  Returns the allocated address
1257  * on success, NULL on failure.  vmflag specifies VM_SLEEP or VM_NOSLEEP,
1258  * and may also specify best-fit, first-fit, or next-fit allocation policy
1259  * instead of the default instant-fit policy.  VM_SLEEP allocations are
1260  * guaranteed to succeed.
1261  */
1262 void *
1263 vmem_alloc(vmem_t *vmp, size_t size, int vmflag)
1264 {
1265 	vmem_seg_t *vsp;
1266 	uintptr_t addr;
1267 	int hb;
1268 	int flist = 0;
1269 	uint32_t mtbf;
1270 
1271 	if (size - 1 < vmp->vm_qcache_max)
1272 		return (kmem_cache_alloc(vmp->vm_qcache[(size - 1) >>
1273 		    vmp->vm_qshift], vmflag & VM_KMFLAGS));
1274 
1275 	if ((mtbf = vmem_mtbf | vmp->vm_mtbf) != 0 && gethrtime() % mtbf == 0 &&
1276 	    (vmflag & (VM_NOSLEEP | VM_PANIC)) == VM_NOSLEEP)
1277 		return (NULL);
1278 
1279 	if (vmflag & VM_NEXTFIT)
1280 		return (vmem_nextfit_alloc(vmp, size, vmflag));
1281 
1282 	if (vmflag & (VM_BESTFIT | VM_FIRSTFIT))
1283 		return (vmem_xalloc(vmp, size, vmp->vm_quantum, 0, 0,
1284 		    NULL, NULL, vmflag));
1285 
1286 	/*
1287 	 * Unconstrained instant-fit allocation from the segment list.
1288 	 */
1289 	mutex_enter(&vmp->vm_lock);
1290 
1291 	if (vmp->vm_nsegfree >= VMEM_MINFREE || vmem_populate(vmp, vmflag)) {
1292 		if (ISP2(size))
1293 			flist = lowbit(P2ALIGN(vmp->vm_freemap, size));
1294 		else if ((hb = highbit(size)) < VMEM_FREELISTS)
1295 			flist = lowbit(P2ALIGN(vmp->vm_freemap, 1UL << hb));
1296 	}
1297 
1298 	if (flist-- == 0) {
1299 		mutex_exit(&vmp->vm_lock);
1300 		return (vmem_xalloc(vmp, size, vmp->vm_quantum,
1301 		    0, 0, NULL, NULL, vmflag));
1302 	}
1303 
1304 	ASSERT(size <= (1UL << flist));
1305 	vsp = vmp->vm_freelist[flist].vs_knext;
1306 	addr = vsp->vs_start;
1307 	if (vmflag & VM_ENDALLOC) {
1308 		addr += vsp->vs_end - (addr + size);
1309 	}
1310 	(void) vmem_seg_alloc(vmp, vsp, addr, size);
1311 	mutex_exit(&vmp->vm_lock);
1312 	return ((void *)addr);
1313 }
1314 
1315 /*
1316  * Free the segment [vaddr, vaddr + size).
1317  */
1318 void
1319 vmem_free(vmem_t *vmp, void *vaddr, size_t size)
1320 {
1321 	if (size - 1 < vmp->vm_qcache_max)
1322 		kmem_cache_free(vmp->vm_qcache[(size - 1) >> vmp->vm_qshift],
1323 		    vaddr);
1324 	else
1325 		vmem_xfree(vmp, vaddr, size);
1326 }
1327 
1328 /*
1329  * Determine whether arena vmp contains the segment [vaddr, vaddr + size).
1330  */
1331 int
1332 vmem_contains(vmem_t *vmp, void *vaddr, size_t size)
1333 {
1334 	uintptr_t start = (uintptr_t)vaddr;
1335 	uintptr_t end = start + size;
1336 	vmem_seg_t *vsp;
1337 	vmem_seg_t *seg0 = &vmp->vm_seg0;
1338 
1339 	mutex_enter(&vmp->vm_lock);
1340 	vmp->vm_kstat.vk_contains.value.ui64++;
1341 	for (vsp = seg0->vs_knext; vsp != seg0; vsp = vsp->vs_knext) {
1342 		vmp->vm_kstat.vk_contains_search.value.ui64++;
1343 		ASSERT(vsp->vs_type == VMEM_SPAN);
1344 		if (start >= vsp->vs_start && end - 1 <= vsp->vs_end - 1)
1345 			break;
1346 	}
1347 	mutex_exit(&vmp->vm_lock);
1348 	return (vsp != seg0);
1349 }
1350 
1351 /*
1352  * Add the span [vaddr, vaddr + size) to arena vmp.
1353  */
1354 void *
1355 vmem_add(vmem_t *vmp, void *vaddr, size_t size, int vmflag)
1356 {
1357 	if (vaddr == NULL || size == 0)
1358 		panic("vmem_add(%p, %p, %lu): bad arguments",
1359 		    (void *)vmp, vaddr, size);
1360 
1361 	ASSERT(!vmem_contains(vmp, vaddr, size));
1362 
1363 	mutex_enter(&vmp->vm_lock);
1364 	if (vmem_populate(vmp, vmflag))
1365 		(void) vmem_span_create(vmp, vaddr, size, 0);
1366 	else
1367 		vaddr = NULL;
1368 	mutex_exit(&vmp->vm_lock);
1369 	return (vaddr);
1370 }
1371 
1372 /*
1373  * Walk the vmp arena, applying func to each segment matching typemask.
1374  * If VMEM_REENTRANT is specified, the arena lock is dropped across each
1375  * call to func(); otherwise, it is held for the duration of vmem_walk()
1376  * to ensure a consistent snapshot.  Note that VMEM_REENTRANT callbacks
1377  * are *not* necessarily consistent, so they may only be used when a hint
1378  * is adequate.
1379  */
1380 void
1381 vmem_walk(vmem_t *vmp, int typemask,
1382 	void (*func)(void *, void *, size_t), void *arg)
1383 {
1384 	vmem_seg_t *vsp;
1385 	vmem_seg_t *seg0 = &vmp->vm_seg0;
1386 	vmem_seg_t walker;
1387 
1388 	if (typemask & VMEM_WALKER)
1389 		return;
1390 
1391 	bzero(&walker, sizeof (walker));
1392 	walker.vs_type = VMEM_WALKER;
1393 
1394 	mutex_enter(&vmp->vm_lock);
1395 	VMEM_INSERT(seg0, &walker, a);
1396 	for (vsp = seg0->vs_anext; vsp != seg0; vsp = vsp->vs_anext) {
1397 		if (vsp->vs_type & typemask) {
1398 			void *start = (void *)vsp->vs_start;
1399 			size_t size = VS_SIZE(vsp);
1400 			if (typemask & VMEM_REENTRANT) {
1401 				vmem_advance(vmp, &walker, vsp);
1402 				mutex_exit(&vmp->vm_lock);
1403 				func(arg, start, size);
1404 				mutex_enter(&vmp->vm_lock);
1405 				vsp = &walker;
1406 			} else {
1407 				func(arg, start, size);
1408 			}
1409 		}
1410 	}
1411 	vmem_advance(vmp, &walker, NULL);
1412 	mutex_exit(&vmp->vm_lock);
1413 }
1414 
1415 /*
1416  * Return the total amount of memory whose type matches typemask.  Thus:
1417  *
1418  *	typemask VMEM_ALLOC yields total memory allocated (in use).
1419  *	typemask VMEM_FREE yields total memory free (available).
1420  *	typemask (VMEM_ALLOC | VMEM_FREE) yields total arena size.
1421  */
1422 size_t
1423 vmem_size(vmem_t *vmp, int typemask)
1424 {
1425 	uint64_t size = 0;
1426 
1427 	if (typemask & VMEM_ALLOC)
1428 		size += vmp->vm_kstat.vk_mem_inuse.value.ui64;
1429 	if (typemask & VMEM_FREE)
1430 		size += vmp->vm_kstat.vk_mem_total.value.ui64 -
1431 		    vmp->vm_kstat.vk_mem_inuse.value.ui64;
1432 	return ((size_t)size);
1433 }
1434 
1435 /*
1436  * Create an arena called name whose initial span is [base, base + size).
1437  * The arena's natural unit of currency is quantum, so vmem_alloc()
1438  * guarantees quantum-aligned results.  The arena may import new spans
1439  * by invoking afunc() on source, and may return those spans by invoking
1440  * ffunc() on source.  To make small allocations fast and scalable,
1441  * the arena offers high-performance caching for each integer multiple
1442  * of quantum up to qcache_max.
1443  */
1444 static vmem_t *
1445 vmem_create_common(const char *name, void *base, size_t size, size_t quantum,
1446 	void *(*afunc)(vmem_t *, size_t, int),
1447 	void (*ffunc)(vmem_t *, void *, size_t),
1448 	vmem_t *source, size_t qcache_max, int vmflag)
1449 {
1450 	int i;
1451 	size_t nqcache;
1452 	vmem_t *vmp, *cur, **vmpp;
1453 	vmem_seg_t *vsp;
1454 	vmem_freelist_t *vfp;
1455 	uint32_t id = atomic_inc_32_nv(&vmem_id);
1456 
1457 	if (vmem_vmem_arena != NULL) {
1458 		vmp = vmem_alloc(vmem_vmem_arena, sizeof (vmem_t),
1459 		    vmflag & VM_KMFLAGS);
1460 	} else {
1461 		ASSERT(id <= VMEM_INITIAL);
1462 		vmp = &vmem0[id - 1];
1463 	}
1464 
1465 	/* An identifier arena must inherit from another identifier arena */
1466 	ASSERT(source == NULL || ((source->vm_cflags & VMC_IDENTIFIER) ==
1467 	    (vmflag & VMC_IDENTIFIER)));
1468 
1469 	if (vmp == NULL)
1470 		return (NULL);
1471 	bzero(vmp, sizeof (vmem_t));
1472 
1473 	(void) snprintf(vmp->vm_name, VMEM_NAMELEN, "%s", name);
1474 	mutex_init(&vmp->vm_lock, NULL, MUTEX_DEFAULT, NULL);
1475 	cv_init(&vmp->vm_cv, NULL, CV_DEFAULT, NULL);
1476 	vmp->vm_cflags = vmflag;
1477 	vmflag &= VM_KMFLAGS;
1478 
1479 	vmp->vm_quantum = quantum;
1480 	vmp->vm_qshift = highbit(quantum) - 1;
1481 	nqcache = MIN(qcache_max >> vmp->vm_qshift, VMEM_NQCACHE_MAX);
1482 
1483 	for (i = 0; i <= VMEM_FREELISTS; i++) {
1484 		vfp = &vmp->vm_freelist[i];
1485 		vfp->vs_end = 1UL << i;
1486 		vfp->vs_knext = (vmem_seg_t *)(vfp + 1);
1487 		vfp->vs_kprev = (vmem_seg_t *)(vfp - 1);
1488 	}
1489 
1490 	vmp->vm_freelist[0].vs_kprev = NULL;
1491 	vmp->vm_freelist[VMEM_FREELISTS].vs_knext = NULL;
1492 	vmp->vm_freelist[VMEM_FREELISTS].vs_end = 0;
1493 	vmp->vm_hash_table = vmp->vm_hash0;
1494 	vmp->vm_hash_mask = VMEM_HASH_INITIAL - 1;
1495 	vmp->vm_hash_shift = highbit(vmp->vm_hash_mask);
1496 
1497 	vsp = &vmp->vm_seg0;
1498 	vsp->vs_anext = vsp;
1499 	vsp->vs_aprev = vsp;
1500 	vsp->vs_knext = vsp;
1501 	vsp->vs_kprev = vsp;
1502 	vsp->vs_type = VMEM_SPAN;
1503 
1504 	vsp = &vmp->vm_rotor;
1505 	vsp->vs_type = VMEM_ROTOR;
1506 	VMEM_INSERT(&vmp->vm_seg0, vsp, a);
1507 
1508 	bcopy(&vmem_kstat_template, &vmp->vm_kstat, sizeof (vmem_kstat_t));
1509 
1510 	vmp->vm_id = id;
1511 	if (source != NULL)
1512 		vmp->vm_kstat.vk_source_id.value.ui32 = source->vm_id;
1513 	vmp->vm_source = source;
1514 	vmp->vm_source_alloc = afunc;
1515 	vmp->vm_source_free = ffunc;
1516 
1517 	/*
1518 	 * Some arenas (like vmem_metadata and kmem_metadata) cannot
1519 	 * use quantum caching to lower fragmentation.  Instead, we
1520 	 * increase their imports, giving a similar effect.
1521 	 */
1522 	if (vmp->vm_cflags & VMC_NO_QCACHE) {
1523 		vmp->vm_min_import =
1524 		    VMEM_QCACHE_SLABSIZE(nqcache << vmp->vm_qshift);
1525 		nqcache = 0;
1526 	}
1527 
1528 	if (nqcache != 0) {
1529 		ASSERT(!(vmflag & VM_NOSLEEP));
1530 		vmp->vm_qcache_max = nqcache << vmp->vm_qshift;
1531 		for (i = 0; i < nqcache; i++) {
1532 			char buf[VMEM_NAMELEN + 21];
1533 			(void) sprintf(buf, "%s_%lu", vmp->vm_name,
1534 			    (i + 1) * quantum);
1535 			vmp->vm_qcache[i] = kmem_cache_create(buf,
1536 			    (i + 1) * quantum, quantum, NULL, NULL, NULL,
1537 			    NULL, vmp, KMC_QCACHE | KMC_NOTOUCH);
1538 		}
1539 	}
1540 
1541 	if ((vmp->vm_ksp = kstat_create("vmem", vmp->vm_id, vmp->vm_name,
1542 	    "vmem", KSTAT_TYPE_NAMED, sizeof (vmem_kstat_t) /
1543 	    sizeof (kstat_named_t), KSTAT_FLAG_VIRTUAL)) != NULL) {
1544 		vmp->vm_ksp->ks_data = &vmp->vm_kstat;
1545 		kstat_install(vmp->vm_ksp);
1546 	}
1547 
1548 	mutex_enter(&vmem_list_lock);
1549 	vmpp = &vmem_list;
1550 	while ((cur = *vmpp) != NULL)
1551 		vmpp = &cur->vm_next;
1552 	*vmpp = vmp;
1553 	mutex_exit(&vmem_list_lock);
1554 
1555 	if (vmp->vm_cflags & VMC_POPULATOR) {
1556 		ASSERT(vmem_populators < VMEM_INITIAL);
1557 		vmem_populator[atomic_inc_32_nv(&vmem_populators) - 1] = vmp;
1558 		mutex_enter(&vmp->vm_lock);
1559 		(void) vmem_populate(vmp, vmflag | VM_PANIC);
1560 		mutex_exit(&vmp->vm_lock);
1561 	}
1562 
1563 	if ((base || size) && vmem_add(vmp, base, size, vmflag) == NULL) {
1564 		vmem_destroy(vmp);
1565 		return (NULL);
1566 	}
1567 
1568 	return (vmp);
1569 }
1570 
1571 vmem_t *
1572 vmem_xcreate(const char *name, void *base, size_t size, size_t quantum,
1573     vmem_ximport_t *afunc, vmem_free_t *ffunc, vmem_t *source,
1574     size_t qcache_max, int vmflag)
1575 {
1576 	ASSERT(!(vmflag & (VMC_POPULATOR | VMC_XALLOC)));
1577 	vmflag &= ~(VMC_POPULATOR | VMC_XALLOC);
1578 
1579 	return (vmem_create_common(name, base, size, quantum,
1580 	    (vmem_alloc_t *)afunc, ffunc, source, qcache_max,
1581 	    vmflag | VMC_XALLOC));
1582 }
1583 
1584 vmem_t *
1585 vmem_create(const char *name, void *base, size_t size, size_t quantum,
1586     vmem_alloc_t *afunc, vmem_free_t *ffunc, vmem_t *source,
1587     size_t qcache_max, int vmflag)
1588 {
1589 	ASSERT(!(vmflag & (VMC_XALLOC | VMC_XALIGN)));
1590 	vmflag &= ~(VMC_XALLOC | VMC_XALIGN);
1591 
1592 	return (vmem_create_common(name, base, size, quantum,
1593 	    afunc, ffunc, source, qcache_max, vmflag));
1594 }
1595 
1596 /*
1597  * Destroy arena vmp.
1598  */
1599 void
1600 vmem_destroy(vmem_t *vmp)
1601 {
1602 	vmem_t *cur, **vmpp;
1603 	vmem_seg_t *seg0 = &vmp->vm_seg0;
1604 	vmem_seg_t *vsp, *anext;
1605 	size_t leaked;
1606 	int i;
1607 
1608 	mutex_enter(&vmem_list_lock);
1609 	vmpp = &vmem_list;
1610 	while ((cur = *vmpp) != vmp)
1611 		vmpp = &cur->vm_next;
1612 	*vmpp = vmp->vm_next;
1613 	mutex_exit(&vmem_list_lock);
1614 
1615 	for (i = 0; i < VMEM_NQCACHE_MAX; i++)
1616 		if (vmp->vm_qcache[i])
1617 			kmem_cache_destroy(vmp->vm_qcache[i]);
1618 
1619 	leaked = vmem_size(vmp, VMEM_ALLOC);
1620 	if (leaked != 0)
1621 		cmn_err(CE_WARN, "vmem_destroy('%s'): leaked %lu %s",
1622 		    vmp->vm_name, leaked, (vmp->vm_cflags & VMC_IDENTIFIER) ?
1623 		    "identifiers" : "bytes");
1624 
1625 	if (vmp->vm_hash_table != vmp->vm_hash0)
1626 		vmem_free(vmem_hash_arena, vmp->vm_hash_table,
1627 		    (vmp->vm_hash_mask + 1) * sizeof (void *));
1628 
1629 	/*
1630 	 * Give back the segment structures for anything that's left in the
1631 	 * arena, e.g. the primary spans and their free segments.
1632 	 */
1633 	VMEM_DELETE(&vmp->vm_rotor, a);
1634 	for (vsp = seg0->vs_anext; vsp != seg0; vsp = anext) {
1635 		anext = vsp->vs_anext;
1636 		vmem_putseg_global(vsp);
1637 	}
1638 
1639 	while (vmp->vm_nsegfree > 0)
1640 		vmem_putseg_global(vmem_getseg(vmp));
1641 
1642 	kstat_delete(vmp->vm_ksp);
1643 
1644 	mutex_destroy(&vmp->vm_lock);
1645 	cv_destroy(&vmp->vm_cv);
1646 	vmem_free(vmem_vmem_arena, vmp, sizeof (vmem_t));
1647 }
1648 
1649 /*
1650  * Resize vmp's hash table to keep the average lookup depth near 1.0.
1651  */
1652 static void
1653 vmem_hash_rescale(vmem_t *vmp)
1654 {
1655 	vmem_seg_t **old_table, **new_table, *vsp;
1656 	size_t old_size, new_size, h, nseg;
1657 
1658 	nseg = (size_t)(vmp->vm_kstat.vk_alloc.value.ui64 -
1659 	    vmp->vm_kstat.vk_free.value.ui64);
1660 
1661 	new_size = MAX(VMEM_HASH_INITIAL, 1 << (highbit(3 * nseg + 4) - 2));
1662 	old_size = vmp->vm_hash_mask + 1;
1663 
1664 	if ((old_size >> 1) <= new_size && new_size <= (old_size << 1))
1665 		return;
1666 
1667 	new_table = vmem_alloc(vmem_hash_arena, new_size * sizeof (void *),
1668 	    VM_NOSLEEP);
1669 	if (new_table == NULL)
1670 		return;
1671 	bzero(new_table, new_size * sizeof (void *));
1672 
1673 	mutex_enter(&vmp->vm_lock);
1674 
1675 	old_size = vmp->vm_hash_mask + 1;
1676 	old_table = vmp->vm_hash_table;
1677 
1678 	vmp->vm_hash_mask = new_size - 1;
1679 	vmp->vm_hash_table = new_table;
1680 	vmp->vm_hash_shift = highbit(vmp->vm_hash_mask);
1681 
1682 	for (h = 0; h < old_size; h++) {
1683 		vsp = old_table[h];
1684 		while (vsp != NULL) {
1685 			uintptr_t addr = vsp->vs_start;
1686 			vmem_seg_t *next_vsp = vsp->vs_knext;
1687 			vmem_seg_t **hash_bucket = VMEM_HASH(vmp, addr);
1688 			vsp->vs_knext = *hash_bucket;
1689 			*hash_bucket = vsp;
1690 			vsp = next_vsp;
1691 		}
1692 	}
1693 
1694 	mutex_exit(&vmp->vm_lock);
1695 
1696 	if (old_table != vmp->vm_hash0)
1697 		vmem_free(vmem_hash_arena, old_table,
1698 		    old_size * sizeof (void *));
1699 }
1700 
1701 /*
1702  * Perform periodic maintenance on all vmem arenas.
1703  */
1704 void
1705 vmem_update(void *dummy)
1706 {
1707 	vmem_t *vmp;
1708 
1709 	mutex_enter(&vmem_list_lock);
1710 	for (vmp = vmem_list; vmp != NULL; vmp = vmp->vm_next) {
1711 		/*
1712 		 * If threads are waiting for resources, wake them up
1713 		 * periodically so they can issue another kmem_reap()
1714 		 * to reclaim resources cached by the slab allocator.
1715 		 */
1716 		cv_broadcast(&vmp->vm_cv);
1717 
1718 		/*
1719 		 * Rescale the hash table to keep the hash chains short.
1720 		 */
1721 		vmem_hash_rescale(vmp);
1722 	}
1723 	mutex_exit(&vmem_list_lock);
1724 
1725 	(void) timeout(vmem_update, dummy, vmem_update_interval * hz);
1726 }
1727 
1728 void
1729 vmem_qcache_reap(vmem_t *vmp)
1730 {
1731 	int i;
1732 
1733 	/*
1734 	 * Reap any quantum caches that may be part of this vmem.
1735 	 */
1736 	for (i = 0; i < VMEM_NQCACHE_MAX; i++)
1737 		if (vmp->vm_qcache[i])
1738 			kmem_cache_reap_now(vmp->vm_qcache[i]);
1739 }
1740 
1741 /*
1742  * Prepare vmem for use.
1743  */
1744 vmem_t *
1745 vmem_init(const char *heap_name,
1746 	void *heap_start, size_t heap_size, size_t heap_quantum,
1747 	void *(*heap_alloc)(vmem_t *, size_t, int),
1748 	void (*heap_free)(vmem_t *, void *, size_t))
1749 {
1750 	uint32_t id;
1751 	int nseg = VMEM_SEG_INITIAL;
1752 	vmem_t *heap;
1753 
1754 	while (--nseg >= 0)
1755 		vmem_putseg_global(&vmem_seg0[nseg]);
1756 
1757 	heap = vmem_create(heap_name,
1758 	    heap_start, heap_size, heap_quantum,
1759 	    NULL, NULL, NULL, 0,
1760 	    VM_SLEEP | VMC_POPULATOR);
1761 
1762 	vmem_metadata_arena = vmem_create("vmem_metadata",
1763 	    NULL, 0, heap_quantum,
1764 	    vmem_alloc, vmem_free, heap, 8 * heap_quantum,
1765 	    VM_SLEEP | VMC_POPULATOR | VMC_NO_QCACHE);
1766 
1767 	vmem_seg_arena = vmem_create("vmem_seg",
1768 	    NULL, 0, heap_quantum,
1769 	    heap_alloc, heap_free, vmem_metadata_arena, 0,
1770 	    VM_SLEEP | VMC_POPULATOR);
1771 
1772 	vmem_hash_arena = vmem_create("vmem_hash",
1773 	    NULL, 0, 8,
1774 	    heap_alloc, heap_free, vmem_metadata_arena, 0,
1775 	    VM_SLEEP);
1776 
1777 	vmem_vmem_arena = vmem_create("vmem_vmem",
1778 	    vmem0, sizeof (vmem0), 1,
1779 	    heap_alloc, heap_free, vmem_metadata_arena, 0,
1780 	    VM_SLEEP);
1781 
1782 	for (id = 0; id < vmem_id; id++)
1783 		(void) vmem_xalloc(vmem_vmem_arena, sizeof (vmem_t),
1784 		    1, 0, 0, &vmem0[id], &vmem0[id + 1],
1785 		    VM_NOSLEEP | VM_BESTFIT | VM_PANIC);
1786 
1787 	return (heap);
1788 }
1789