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