FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_vmem.c
1 /* $NetBSD: subr_vmem.c,v 1.42.14.1 2009/02/02 02:40:27 snj 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.42.14.1 2009/02/02 02:40:27 snj 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/vmem.h>
61 #include <sys/workqueue.h>
62 #else /* defined(_KERNEL) */
63 #include "../sys/vmem.h"
64 #endif /* defined(_KERNEL) */
65
66 #if defined(_KERNEL)
67 #define LOCK_DECL(name) \
68 kmutex_t name; char lockpad[COHERENCY_UNIT - sizeof(kmutex_t)]
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() /* 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();
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();
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 = ®[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 = ®[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) */
Cache object: acf0e1efdc3e5ace8cbf8c929e5c3c7b
|