Annotation of src/sys/kern/subr_vmem.c, Revision 1.60
1.60 ! dyoung 1: /* $NetBSD: subr_vmem.c,v 1.59 2011/07/26 13:09:11 yamt Exp $ */
1.1 yamt 2:
3: /*-
1.55 yamt 4: * Copyright (c)2006,2007,2008,2009 YAMAMOTO Takashi,
1.1 yamt 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
1.18 yamt 34: *
35: * todo:
36: * - decide how to import segments for vmem_xalloc.
37: * - don't rely on malloc(9).
1.1 yamt 38: */
39:
40: #include <sys/cdefs.h>
1.60 ! dyoung 41: __KERNEL_RCSID(0, "$NetBSD: subr_vmem.c,v 1.59 2011/07/26 13:09:11 yamt Exp $");
1.1 yamt 42:
1.5 yamt 43: #if defined(_KERNEL)
1.37 yamt 44: #include "opt_ddb.h"
1.5 yamt 45: #define QCACHE
46: #endif /* defined(_KERNEL) */
1.1 yamt 47:
48: #include <sys/param.h>
49: #include <sys/hash.h>
50: #include <sys/queue.h>
51:
52: #if defined(_KERNEL)
53: #include <sys/systm.h>
1.30 yamt 54: #include <sys/kernel.h> /* hz */
55: #include <sys/callout.h>
1.1 yamt 56: #include <sys/malloc.h>
57: #include <sys/once.h>
58: #include <sys/pool.h>
59: #include <sys/vmem.h>
1.30 yamt 60: #include <sys/workqueue.h>
1.1 yamt 61: #else /* defined(_KERNEL) */
62: #include "../sys/vmem.h"
63: #endif /* defined(_KERNEL) */
64:
65: #if defined(_KERNEL)
1.52 ad 66: #define LOCK_DECL(name) \
67: kmutex_t name; char lockpad[COHERENCY_UNIT - sizeof(kmutex_t)]
1.1 yamt 68: #else /* defined(_KERNEL) */
69: #include <errno.h>
70: #include <assert.h>
71: #include <stdlib.h>
72:
1.55 yamt 73: #define UNITTEST
1.1 yamt 74: #define KASSERT(a) assert(a)
1.31 ad 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 */
1.55 yamt 79: #define mutex_tryenter(a) true
1.31 ad 80: #define mutex_exit(a) /* nothing */
81: #define mutex_owned(a) /* nothing */
1.55 yamt 82: #define ASSERT_SLEEPABLE() /* nothing */
83: #define panic(...) printf(__VA_ARGS__); abort()
1.1 yamt 84: #endif /* defined(_KERNEL) */
85:
86: struct vmem;
87: struct vmem_btag;
88:
1.55 yamt 89: #if defined(VMEM_SANITY)
90: static void vmem_check(vmem_t *);
91: #else /* defined(VMEM_SANITY) */
92: #define vmem_check(vm) /* nothing */
93: #endif /* defined(VMEM_SANITY) */
1.1 yamt 94:
1.4 yamt 95: #define VMEM_MAXORDER (sizeof(vmem_size_t) * CHAR_BIT)
1.30 yamt 96:
97: #define VMEM_HASHSIZE_MIN 1 /* XXX */
1.54 yamt 98: #define VMEM_HASHSIZE_MAX 65536 /* XXX */
1.53 pooka 99: #define VMEM_HASHSIZE_INIT 128
1.1 yamt 100:
101: #define VM_FITMASK (VM_BESTFIT | VM_INSTANTFIT)
102:
103: CIRCLEQ_HEAD(vmem_seglist, vmem_btag);
104: LIST_HEAD(vmem_freelist, vmem_btag);
105: LIST_HEAD(vmem_hashlist, vmem_btag);
106:
1.5 yamt 107: #if defined(QCACHE)
108: #define VMEM_QCACHE_IDX_MAX 32
109:
110: #define QC_NAME_MAX 16
111:
112: struct qcache {
1.35 ad 113: pool_cache_t qc_cache;
1.5 yamt 114: vmem_t *qc_vmem;
115: char qc_name[QC_NAME_MAX];
116: };
117: typedef struct qcache qcache_t;
1.35 ad 118: #define QC_POOL_TO_QCACHE(pool) ((qcache_t *)(pool->pr_qcache))
1.5 yamt 119: #endif /* defined(QCACHE) */
120:
1.1 yamt 121: /* vmem arena */
122: struct vmem {
1.31 ad 123: LOCK_DECL(vm_lock);
1.1 yamt 124: vmem_addr_t (*vm_allocfn)(vmem_t *, vmem_size_t, vmem_size_t *,
125: vm_flag_t);
126: void (*vm_freefn)(vmem_t *, vmem_addr_t, vmem_size_t);
127: vmem_t *vm_source;
128: struct vmem_seglist vm_seglist;
129: struct vmem_freelist vm_freelist[VMEM_MAXORDER];
130: size_t vm_hashsize;
131: size_t vm_nbusytag;
132: struct vmem_hashlist *vm_hashlist;
133: size_t vm_quantum_mask;
134: int vm_quantum_shift;
135: const char *vm_name;
1.30 yamt 136: LIST_ENTRY(vmem) vm_alllist;
1.5 yamt 137:
138: #if defined(QCACHE)
139: /* quantum cache */
140: size_t vm_qcache_max;
141: struct pool_allocator vm_qcache_allocator;
1.22 yamt 142: qcache_t vm_qcache_store[VMEM_QCACHE_IDX_MAX];
143: qcache_t *vm_qcache[VMEM_QCACHE_IDX_MAX];
1.5 yamt 144: #endif /* defined(QCACHE) */
1.1 yamt 145: };
146:
1.31 ad 147: #define VMEM_LOCK(vm) mutex_enter(&vm->vm_lock)
148: #define VMEM_TRYLOCK(vm) mutex_tryenter(&vm->vm_lock)
149: #define VMEM_UNLOCK(vm) mutex_exit(&vm->vm_lock)
1.36 ad 150: #define VMEM_LOCK_INIT(vm, ipl) mutex_init(&vm->vm_lock, MUTEX_DEFAULT, ipl)
1.31 ad 151: #define VMEM_LOCK_DESTROY(vm) mutex_destroy(&vm->vm_lock)
152: #define VMEM_ASSERT_LOCKED(vm) KASSERT(mutex_owned(&vm->vm_lock))
1.1 yamt 153:
154: /* boundary tag */
155: struct vmem_btag {
156: CIRCLEQ_ENTRY(vmem_btag) bt_seglist;
157: union {
158: LIST_ENTRY(vmem_btag) u_freelist; /* BT_TYPE_FREE */
159: LIST_ENTRY(vmem_btag) u_hashlist; /* BT_TYPE_BUSY */
160: } bt_u;
161: #define bt_hashlist bt_u.u_hashlist
162: #define bt_freelist bt_u.u_freelist
163: vmem_addr_t bt_start;
164: vmem_size_t bt_size;
165: int bt_type;
166: };
167:
168: #define BT_TYPE_SPAN 1
169: #define BT_TYPE_SPAN_STATIC 2
170: #define BT_TYPE_FREE 3
171: #define BT_TYPE_BUSY 4
172: #define BT_ISSPAN_P(bt) ((bt)->bt_type <= BT_TYPE_SPAN_STATIC)
173:
1.60 ! dyoung 174: #define BT_END(bt) ((bt)->bt_start + (bt)->bt_size - 1)
1.1 yamt 175:
176: typedef struct vmem_btag bt_t;
177:
178: /* ---- misc */
179:
1.19 yamt 180: #define VMEM_ALIGNUP(addr, align) \
181: (-(-(addr) & -(align)))
182: #define VMEM_CROSS_P(addr1, addr2, boundary) \
183: ((((addr1) ^ (addr2)) & -(boundary)) != 0)
184:
1.4 yamt 185: #define ORDER2SIZE(order) ((vmem_size_t)1 << (order))
186:
1.1 yamt 187: static int
188: calc_order(vmem_size_t size)
189: {
1.4 yamt 190: vmem_size_t target;
1.1 yamt 191: int i;
192:
193: KASSERT(size != 0);
194:
195: i = 0;
1.4 yamt 196: target = size >> 1;
197: while (ORDER2SIZE(i) <= target) {
1.1 yamt 198: i++;
199: }
200:
1.4 yamt 201: KASSERT(ORDER2SIZE(i) <= size);
202: KASSERT(size < ORDER2SIZE(i + 1) || ORDER2SIZE(i + 1) < ORDER2SIZE(i));
1.1 yamt 203:
204: return i;
205: }
206:
207: #if defined(_KERNEL)
208: static MALLOC_DEFINE(M_VMEM, "vmem", "vmem");
209: #endif /* defined(_KERNEL) */
210:
211: static void *
212: xmalloc(size_t sz, vm_flag_t flags)
213: {
214:
215: #if defined(_KERNEL)
216: return malloc(sz, M_VMEM,
217: M_CANFAIL | ((flags & VM_SLEEP) ? M_WAITOK : M_NOWAIT));
218: #else /* defined(_KERNEL) */
219: return malloc(sz);
220: #endif /* defined(_KERNEL) */
221: }
222:
223: static void
224: xfree(void *p)
225: {
226:
227: #if defined(_KERNEL)
228: return free(p, M_VMEM);
229: #else /* defined(_KERNEL) */
230: return free(p);
231: #endif /* defined(_KERNEL) */
232: }
233:
234: /* ---- boundary tag */
235:
236: #if defined(_KERNEL)
1.35 ad 237: static struct pool_cache bt_cache;
1.1 yamt 238: #endif /* defined(_KERNEL) */
239:
240: static bt_t *
1.17 yamt 241: bt_alloc(vmem_t *vm, vm_flag_t flags)
1.1 yamt 242: {
243: bt_t *bt;
244:
245: #if defined(_KERNEL)
1.35 ad 246: bt = pool_cache_get(&bt_cache,
1.1 yamt 247: (flags & VM_SLEEP) != 0 ? PR_WAITOK : PR_NOWAIT);
248: #else /* defined(_KERNEL) */
249: bt = malloc(sizeof *bt);
250: #endif /* defined(_KERNEL) */
251:
252: return bt;
253: }
254:
255: static void
1.17 yamt 256: bt_free(vmem_t *vm, bt_t *bt)
1.1 yamt 257: {
258:
259: #if defined(_KERNEL)
1.35 ad 260: pool_cache_put(&bt_cache, bt);
1.1 yamt 261: #else /* defined(_KERNEL) */
262: free(bt);
263: #endif /* defined(_KERNEL) */
264: }
265:
266: /*
267: * freelist[0] ... [1, 1]
268: * freelist[1] ... [2, 3]
269: * freelist[2] ... [4, 7]
270: * freelist[3] ... [8, 15]
271: * :
272: * freelist[n] ... [(1 << n), (1 << (n + 1)) - 1]
273: * :
274: */
275:
276: static struct vmem_freelist *
277: bt_freehead_tofree(vmem_t *vm, vmem_size_t size)
278: {
279: const vmem_size_t qsize = size >> vm->vm_quantum_shift;
280: int idx;
281:
282: KASSERT((size & vm->vm_quantum_mask) == 0);
283: KASSERT(size != 0);
284:
285: idx = calc_order(qsize);
286: KASSERT(idx >= 0);
287: KASSERT(idx < VMEM_MAXORDER);
288:
289: return &vm->vm_freelist[idx];
290: }
291:
1.59 yamt 292: /*
293: * bt_freehead_toalloc: return the freelist for the given size and allocation
294: * strategy.
295: *
296: * for VM_INSTANTFIT, return the list in which any blocks are large enough
297: * for the requested size. otherwise, return the list which can have blocks
298: * large enough for the requested size.
299: */
300:
1.1 yamt 301: static struct vmem_freelist *
302: bt_freehead_toalloc(vmem_t *vm, vmem_size_t size, vm_flag_t strat)
303: {
304: const vmem_size_t qsize = size >> vm->vm_quantum_shift;
305: int idx;
306:
307: KASSERT((size & vm->vm_quantum_mask) == 0);
308: KASSERT(size != 0);
309:
310: idx = calc_order(qsize);
1.4 yamt 311: if (strat == VM_INSTANTFIT && ORDER2SIZE(idx) != qsize) {
1.1 yamt 312: idx++;
313: /* check too large request? */
314: }
315: KASSERT(idx >= 0);
316: KASSERT(idx < VMEM_MAXORDER);
317:
318: return &vm->vm_freelist[idx];
319: }
320:
321: /* ---- boundary tag hash */
322:
323: static struct vmem_hashlist *
324: bt_hashhead(vmem_t *vm, vmem_addr_t addr)
325: {
326: struct vmem_hashlist *list;
327: unsigned int hash;
328:
329: hash = hash32_buf(&addr, sizeof(addr), HASH32_BUF_INIT);
330: list = &vm->vm_hashlist[hash % vm->vm_hashsize];
331:
332: return list;
333: }
334:
335: static bt_t *
336: bt_lookupbusy(vmem_t *vm, vmem_addr_t addr)
337: {
338: struct vmem_hashlist *list;
339: bt_t *bt;
340:
341: list = bt_hashhead(vm, addr);
342: LIST_FOREACH(bt, list, bt_hashlist) {
343: if (bt->bt_start == addr) {
344: break;
345: }
346: }
347:
348: return bt;
349: }
350:
351: static void
352: bt_rembusy(vmem_t *vm, bt_t *bt)
353: {
354:
355: KASSERT(vm->vm_nbusytag > 0);
356: vm->vm_nbusytag--;
357: LIST_REMOVE(bt, bt_hashlist);
358: }
359:
360: static void
361: bt_insbusy(vmem_t *vm, bt_t *bt)
362: {
363: struct vmem_hashlist *list;
364:
365: KASSERT(bt->bt_type == BT_TYPE_BUSY);
366:
367: list = bt_hashhead(vm, bt->bt_start);
368: LIST_INSERT_HEAD(list, bt, bt_hashlist);
369: vm->vm_nbusytag++;
370: }
371:
372: /* ---- boundary tag list */
373:
374: static void
375: bt_remseg(vmem_t *vm, bt_t *bt)
376: {
377:
378: CIRCLEQ_REMOVE(&vm->vm_seglist, bt, bt_seglist);
379: }
380:
381: static void
382: bt_insseg(vmem_t *vm, bt_t *bt, bt_t *prev)
383: {
384:
385: CIRCLEQ_INSERT_AFTER(&vm->vm_seglist, prev, bt, bt_seglist);
386: }
387:
388: static void
389: bt_insseg_tail(vmem_t *vm, bt_t *bt)
390: {
391:
392: CIRCLEQ_INSERT_TAIL(&vm->vm_seglist, bt, bt_seglist);
393: }
394:
395: static void
1.17 yamt 396: bt_remfree(vmem_t *vm, bt_t *bt)
1.1 yamt 397: {
398:
399: KASSERT(bt->bt_type == BT_TYPE_FREE);
400:
401: LIST_REMOVE(bt, bt_freelist);
402: }
403:
404: static void
405: bt_insfree(vmem_t *vm, bt_t *bt)
406: {
407: struct vmem_freelist *list;
408:
409: list = bt_freehead_tofree(vm, bt->bt_size);
410: LIST_INSERT_HEAD(list, bt, bt_freelist);
411: }
412:
413: /* ---- vmem internal functions */
414:
1.30 yamt 415: #if defined(_KERNEL)
416: static kmutex_t vmem_list_lock;
417: static LIST_HEAD(, vmem) vmem_list = LIST_HEAD_INITIALIZER(vmem_list);
418: #endif /* defined(_KERNEL) */
419:
1.5 yamt 420: #if defined(QCACHE)
421: static inline vm_flag_t
422: prf_to_vmf(int prflags)
423: {
424: vm_flag_t vmflags;
425:
426: KASSERT((prflags & ~(PR_LIMITFAIL | PR_WAITOK | PR_NOWAIT)) == 0);
427: if ((prflags & PR_WAITOK) != 0) {
428: vmflags = VM_SLEEP;
429: } else {
430: vmflags = VM_NOSLEEP;
431: }
432: return vmflags;
433: }
434:
435: static inline int
436: vmf_to_prf(vm_flag_t vmflags)
437: {
438: int prflags;
439:
1.7 yamt 440: if ((vmflags & VM_SLEEP) != 0) {
1.5 yamt 441: prflags = PR_WAITOK;
1.7 yamt 442: } else {
1.5 yamt 443: prflags = PR_NOWAIT;
444: }
445: return prflags;
446: }
447:
448: static size_t
449: qc_poolpage_size(size_t qcache_max)
450: {
451: int i;
452:
453: for (i = 0; ORDER2SIZE(i) <= qcache_max * 3; i++) {
454: /* nothing */
455: }
456: return ORDER2SIZE(i);
457: }
458:
459: static void *
460: qc_poolpage_alloc(struct pool *pool, int prflags)
461: {
462: qcache_t *qc = QC_POOL_TO_QCACHE(pool);
463: vmem_t *vm = qc->qc_vmem;
464:
465: return (void *)vmem_alloc(vm, pool->pr_alloc->pa_pagesz,
466: prf_to_vmf(prflags) | VM_INSTANTFIT);
467: }
468:
469: static void
470: qc_poolpage_free(struct pool *pool, void *addr)
471: {
472: qcache_t *qc = QC_POOL_TO_QCACHE(pool);
473: vmem_t *vm = qc->qc_vmem;
474:
475: vmem_free(vm, (vmem_addr_t)addr, pool->pr_alloc->pa_pagesz);
476: }
477:
478: static void
1.31 ad 479: qc_init(vmem_t *vm, size_t qcache_max, int ipl)
1.5 yamt 480: {
1.22 yamt 481: qcache_t *prevqc;
1.5 yamt 482: struct pool_allocator *pa;
483: int qcache_idx_max;
484: int i;
485:
486: KASSERT((qcache_max & vm->vm_quantum_mask) == 0);
487: if (qcache_max > (VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift)) {
488: qcache_max = VMEM_QCACHE_IDX_MAX << vm->vm_quantum_shift;
489: }
490: vm->vm_qcache_max = qcache_max;
491: pa = &vm->vm_qcache_allocator;
492: memset(pa, 0, sizeof(*pa));
493: pa->pa_alloc = qc_poolpage_alloc;
494: pa->pa_free = qc_poolpage_free;
495: pa->pa_pagesz = qc_poolpage_size(qcache_max);
496:
497: qcache_idx_max = qcache_max >> vm->vm_quantum_shift;
1.22 yamt 498: prevqc = NULL;
499: for (i = qcache_idx_max; i > 0; i--) {
500: qcache_t *qc = &vm->vm_qcache_store[i - 1];
1.5 yamt 501: size_t size = i << vm->vm_quantum_shift;
502:
503: qc->qc_vmem = vm;
1.8 martin 504: snprintf(qc->qc_name, sizeof(qc->qc_name), "%s-%zu",
1.5 yamt 505: vm->vm_name, size);
1.35 ad 506: qc->qc_cache = pool_cache_init(size,
507: ORDER2SIZE(vm->vm_quantum_shift), 0,
508: PR_NOALIGN | PR_NOTOUCH /* XXX */,
509: qc->qc_name, pa, ipl, NULL, NULL, NULL);
510: KASSERT(qc->qc_cache != NULL); /* XXX */
1.22 yamt 511: if (prevqc != NULL &&
1.35 ad 512: qc->qc_cache->pc_pool.pr_itemsperpage ==
513: prevqc->qc_cache->pc_pool.pr_itemsperpage) {
514: pool_cache_destroy(qc->qc_cache);
1.22 yamt 515: vm->vm_qcache[i - 1] = prevqc;
1.27 ad 516: continue;
1.22 yamt 517: }
1.35 ad 518: qc->qc_cache->pc_pool.pr_qcache = qc;
1.22 yamt 519: vm->vm_qcache[i - 1] = qc;
520: prevqc = qc;
1.5 yamt 521: }
522: }
1.6 yamt 523:
1.23 yamt 524: static void
525: qc_destroy(vmem_t *vm)
526: {
527: const qcache_t *prevqc;
528: int i;
529: int qcache_idx_max;
530:
531: qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift;
532: prevqc = NULL;
1.24 yamt 533: for (i = 0; i < qcache_idx_max; i++) {
534: qcache_t *qc = vm->vm_qcache[i];
1.23 yamt 535:
536: if (prevqc == qc) {
537: continue;
538: }
1.35 ad 539: pool_cache_destroy(qc->qc_cache);
1.23 yamt 540: prevqc = qc;
541: }
542: }
543:
1.25 thorpej 544: static bool
1.6 yamt 545: qc_reap(vmem_t *vm)
546: {
1.22 yamt 547: const qcache_t *prevqc;
1.6 yamt 548: int i;
549: int qcache_idx_max;
1.26 thorpej 550: bool didsomething = false;
1.6 yamt 551:
552: qcache_idx_max = vm->vm_qcache_max >> vm->vm_quantum_shift;
1.22 yamt 553: prevqc = NULL;
1.24 yamt 554: for (i = 0; i < qcache_idx_max; i++) {
555: qcache_t *qc = vm->vm_qcache[i];
1.6 yamt 556:
1.22 yamt 557: if (prevqc == qc) {
558: continue;
559: }
1.35 ad 560: if (pool_cache_reclaim(qc->qc_cache) != 0) {
1.26 thorpej 561: didsomething = true;
1.6 yamt 562: }
1.22 yamt 563: prevqc = qc;
1.6 yamt 564: }
565:
566: return didsomething;
567: }
1.5 yamt 568: #endif /* defined(QCACHE) */
569:
1.1 yamt 570: #if defined(_KERNEL)
571: static int
572: vmem_init(void)
573: {
574:
1.30 yamt 575: mutex_init(&vmem_list_lock, MUTEX_DEFAULT, IPL_NONE);
1.35 ad 576: pool_cache_bootstrap(&bt_cache, sizeof(bt_t), 0, 0, 0, "vmembt",
577: NULL, IPL_VM, NULL, NULL, NULL);
1.1 yamt 578: return 0;
579: }
580: #endif /* defined(_KERNEL) */
581:
582: static vmem_addr_t
583: vmem_add1(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags,
584: int spanbttype)
585: {
586: bt_t *btspan;
587: bt_t *btfree;
588:
589: KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
590: KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
1.58 yamt 591: KASSERT(spanbttype == BT_TYPE_SPAN ||
592: spanbttype == BT_TYPE_SPAN_STATIC);
1.1 yamt 593:
594: btspan = bt_alloc(vm, flags);
595: if (btspan == NULL) {
596: return VMEM_ADDR_NULL;
597: }
598: btfree = bt_alloc(vm, flags);
599: if (btfree == NULL) {
600: bt_free(vm, btspan);
601: return VMEM_ADDR_NULL;
602: }
603:
604: btspan->bt_type = spanbttype;
605: btspan->bt_start = addr;
606: btspan->bt_size = size;
607:
608: btfree->bt_type = BT_TYPE_FREE;
609: btfree->bt_start = addr;
610: btfree->bt_size = size;
611:
612: VMEM_LOCK(vm);
613: bt_insseg_tail(vm, btspan);
614: bt_insseg(vm, btfree, btspan);
615: bt_insfree(vm, btfree);
616: VMEM_UNLOCK(vm);
617:
618: return addr;
619: }
620:
1.30 yamt 621: static void
622: vmem_destroy1(vmem_t *vm)
623: {
624:
625: #if defined(QCACHE)
626: qc_destroy(vm);
627: #endif /* defined(QCACHE) */
628: if (vm->vm_hashlist != NULL) {
629: int i;
630:
631: for (i = 0; i < vm->vm_hashsize; i++) {
632: bt_t *bt;
633:
634: while ((bt = LIST_FIRST(&vm->vm_hashlist[i])) != NULL) {
635: KASSERT(bt->bt_type == BT_TYPE_SPAN_STATIC);
636: bt_free(vm, bt);
637: }
638: }
639: xfree(vm->vm_hashlist);
640: }
1.31 ad 641: VMEM_LOCK_DESTROY(vm);
1.30 yamt 642: xfree(vm);
643: }
644:
1.1 yamt 645: static int
646: vmem_import(vmem_t *vm, vmem_size_t size, vm_flag_t flags)
647: {
648: vmem_addr_t addr;
649:
650: if (vm->vm_allocfn == NULL) {
651: return EINVAL;
652: }
653:
654: addr = (*vm->vm_allocfn)(vm->vm_source, size, &size, flags);
655: if (addr == VMEM_ADDR_NULL) {
656: return ENOMEM;
657: }
658:
659: if (vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN) == VMEM_ADDR_NULL) {
660: (*vm->vm_freefn)(vm->vm_source, addr, size);
661: return ENOMEM;
662: }
663:
664: return 0;
665: }
666:
667: static int
668: vmem_rehash(vmem_t *vm, size_t newhashsize, vm_flag_t flags)
669: {
670: bt_t *bt;
671: int i;
672: struct vmem_hashlist *newhashlist;
673: struct vmem_hashlist *oldhashlist;
674: size_t oldhashsize;
675:
676: KASSERT(newhashsize > 0);
677:
678: newhashlist =
679: xmalloc(sizeof(struct vmem_hashlist *) * newhashsize, flags);
680: if (newhashlist == NULL) {
681: return ENOMEM;
682: }
683: for (i = 0; i < newhashsize; i++) {
684: LIST_INIT(&newhashlist[i]);
685: }
686:
1.30 yamt 687: if (!VMEM_TRYLOCK(vm)) {
688: xfree(newhashlist);
689: return EBUSY;
690: }
1.1 yamt 691: oldhashlist = vm->vm_hashlist;
692: oldhashsize = vm->vm_hashsize;
693: vm->vm_hashlist = newhashlist;
694: vm->vm_hashsize = newhashsize;
695: if (oldhashlist == NULL) {
696: VMEM_UNLOCK(vm);
697: return 0;
698: }
699: for (i = 0; i < oldhashsize; i++) {
700: while ((bt = LIST_FIRST(&oldhashlist[i])) != NULL) {
701: bt_rembusy(vm, bt); /* XXX */
702: bt_insbusy(vm, bt);
703: }
704: }
705: VMEM_UNLOCK(vm);
706:
707: xfree(oldhashlist);
708:
709: return 0;
710: }
711:
1.10 yamt 712: /*
713: * vmem_fit: check if a bt can satisfy the given restrictions.
1.59 yamt 714: *
715: * it's a caller's responsibility to ensure the region is big enough
716: * before calling us.
1.10 yamt 717: */
718:
719: static vmem_addr_t
1.60 ! dyoung 720: vmem_fit(const bt_t const *bt, vmem_size_t size, vmem_size_t align,
! 721: vmem_size_t phase, vmem_size_t nocross,
! 722: vmem_addr_t minaddr, vmem_addr_t maxaddr)
1.10 yamt 723: {
724: vmem_addr_t start;
725: vmem_addr_t end;
726:
1.60 ! dyoung 727: KASSERT(size > 0);
1.59 yamt 728: KASSERT(bt->bt_size >= size); /* caller's responsibility */
1.10 yamt 729:
730: /*
731: * XXX assumption: vmem_addr_t and vmem_size_t are
732: * unsigned integer of the same size.
733: */
734:
735: start = bt->bt_start;
736: if (start < minaddr) {
737: start = minaddr;
738: }
739: end = BT_END(bt);
1.60 ! dyoung 740: if (end > maxaddr) {
! 741: end = maxaddr;
1.10 yamt 742: }
1.60 ! dyoung 743: if (start > end) {
1.10 yamt 744: return VMEM_ADDR_NULL;
745: }
1.19 yamt 746:
747: start = VMEM_ALIGNUP(start - phase, align) + phase;
1.10 yamt 748: if (start < bt->bt_start) {
749: start += align;
750: }
1.19 yamt 751: if (VMEM_CROSS_P(start, start + size - 1, nocross)) {
1.10 yamt 752: KASSERT(align < nocross);
1.19 yamt 753: start = VMEM_ALIGNUP(start - phase, nocross) + phase;
1.10 yamt 754: }
1.60 ! dyoung 755: if (start <= end && end - start >= size - 1) {
1.10 yamt 756: KASSERT((start & (align - 1)) == phase);
1.19 yamt 757: KASSERT(!VMEM_CROSS_P(start, start + size - 1, nocross));
1.10 yamt 758: KASSERT(minaddr <= start);
1.60 ! dyoung 759: KASSERT(maxaddr == 0 || start + size - 1 <= maxaddr);
1.10 yamt 760: KASSERT(bt->bt_start <= start);
1.60 ! dyoung 761: KASSERT(BT_END(bt) - start >= size - 1);
1.10 yamt 762: return start;
763: }
764: return VMEM_ADDR_NULL;
765: }
766:
1.1 yamt 767: /* ---- vmem API */
768:
769: /*
770: * vmem_create: create an arena.
771: *
772: * => must not be called from interrupt context.
773: */
774:
775: vmem_t *
776: vmem_create(const char *name, vmem_addr_t base, vmem_size_t size,
777: vmem_size_t quantum,
778: vmem_addr_t (*allocfn)(vmem_t *, vmem_size_t, vmem_size_t *, vm_flag_t),
779: void (*freefn)(vmem_t *, vmem_addr_t, vmem_size_t),
1.31 ad 780: vmem_t *source, vmem_size_t qcache_max, vm_flag_t flags,
781: int ipl)
1.1 yamt 782: {
783: vmem_t *vm;
784: int i;
785: #if defined(_KERNEL)
786: static ONCE_DECL(control);
787: #endif /* defined(_KERNEL) */
788:
789: KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
790: KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
791:
792: #if defined(_KERNEL)
793: if (RUN_ONCE(&control, vmem_init)) {
794: return NULL;
795: }
796: #endif /* defined(_KERNEL) */
797: vm = xmalloc(sizeof(*vm), flags);
798: if (vm == NULL) {
799: return NULL;
800: }
801:
1.31 ad 802: VMEM_LOCK_INIT(vm, ipl);
1.1 yamt 803: vm->vm_name = name;
804: vm->vm_quantum_mask = quantum - 1;
805: vm->vm_quantum_shift = calc_order(quantum);
1.4 yamt 806: KASSERT(ORDER2SIZE(vm->vm_quantum_shift) == quantum);
1.1 yamt 807: vm->vm_allocfn = allocfn;
808: vm->vm_freefn = freefn;
809: vm->vm_source = source;
810: vm->vm_nbusytag = 0;
1.5 yamt 811: #if defined(QCACHE)
1.31 ad 812: qc_init(vm, qcache_max, ipl);
1.5 yamt 813: #endif /* defined(QCACHE) */
1.1 yamt 814:
815: CIRCLEQ_INIT(&vm->vm_seglist);
816: for (i = 0; i < VMEM_MAXORDER; i++) {
817: LIST_INIT(&vm->vm_freelist[i]);
818: }
819: vm->vm_hashlist = NULL;
820: if (vmem_rehash(vm, VMEM_HASHSIZE_INIT, flags)) {
1.30 yamt 821: vmem_destroy1(vm);
1.1 yamt 822: return NULL;
823: }
824:
825: if (size != 0) {
826: if (vmem_add(vm, base, size, flags) == 0) {
1.30 yamt 827: vmem_destroy1(vm);
1.1 yamt 828: return NULL;
829: }
830: }
831:
1.30 yamt 832: #if defined(_KERNEL)
833: mutex_enter(&vmem_list_lock);
834: LIST_INSERT_HEAD(&vmem_list, vm, vm_alllist);
835: mutex_exit(&vmem_list_lock);
836: #endif /* defined(_KERNEL) */
837:
1.1 yamt 838: return vm;
839: }
840:
841: void
842: vmem_destroy(vmem_t *vm)
843: {
844:
1.30 yamt 845: #if defined(_KERNEL)
846: mutex_enter(&vmem_list_lock);
847: LIST_REMOVE(vm, vm_alllist);
848: mutex_exit(&vmem_list_lock);
849: #endif /* defined(_KERNEL) */
1.1 yamt 850:
1.30 yamt 851: vmem_destroy1(vm);
1.1 yamt 852: }
853:
854: vmem_size_t
855: vmem_roundup_size(vmem_t *vm, vmem_size_t size)
856: {
857:
858: return (size + vm->vm_quantum_mask) & ~vm->vm_quantum_mask;
859: }
860:
861: /*
862: * vmem_alloc:
863: *
864: * => caller must ensure appropriate spl,
865: * if the arena can be accessed from interrupt context.
866: */
867:
868: vmem_addr_t
1.38 yamt 869: vmem_alloc(vmem_t *vm, vmem_size_t size, vm_flag_t flags)
1.1 yamt 870: {
1.12 yamt 871: const vm_flag_t strat __unused = flags & VM_FITMASK;
1.1 yamt 872:
873: KASSERT((flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
874: KASSERT((~flags & (VM_SLEEP|VM_NOSLEEP)) != 0);
875:
876: KASSERT(size > 0);
877: KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT);
1.3 yamt 878: if ((flags & VM_SLEEP) != 0) {
1.42 yamt 879: ASSERT_SLEEPABLE();
1.3 yamt 880: }
1.1 yamt 881:
1.5 yamt 882: #if defined(QCACHE)
883: if (size <= vm->vm_qcache_max) {
1.38 yamt 884: int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift;
1.22 yamt 885: qcache_t *qc = vm->vm_qcache[qidx - 1];
1.5 yamt 886:
1.35 ad 887: return (vmem_addr_t)pool_cache_get(qc->qc_cache,
1.5 yamt 888: vmf_to_prf(flags));
889: }
890: #endif /* defined(QCACHE) */
891:
1.60 ! dyoung 892: return vmem_xalloc(vm, size, 0, 0, 0, VMEM_ADDR_MIN, VMEM_ADDR_MAX,
! 893: flags);
1.10 yamt 894: }
895:
896: vmem_addr_t
1.60 ! dyoung 897: vmem_xalloc(vmem_t *vm, const vmem_size_t size0, vmem_size_t align,
! 898: const vmem_size_t phase, const vmem_size_t nocross,
! 899: const vmem_addr_t minaddr, const vmem_addr_t maxaddr, const vm_flag_t flags)
1.10 yamt 900: {
901: struct vmem_freelist *list;
902: struct vmem_freelist *first;
903: struct vmem_freelist *end;
904: bt_t *bt;
905: bt_t *btnew;
906: bt_t *btnew2;
907: const vmem_size_t size = vmem_roundup_size(vm, size0);
908: vm_flag_t strat = flags & VM_FITMASK;
909: vmem_addr_t start;
910:
911: KASSERT(size0 > 0);
912: KASSERT(size > 0);
913: KASSERT(strat == VM_BESTFIT || strat == VM_INSTANTFIT);
914: if ((flags & VM_SLEEP) != 0) {
1.42 yamt 915: ASSERT_SLEEPABLE();
1.10 yamt 916: }
917: KASSERT((align & vm->vm_quantum_mask) == 0);
918: KASSERT((align & (align - 1)) == 0);
919: KASSERT((phase & vm->vm_quantum_mask) == 0);
920: KASSERT((nocross & vm->vm_quantum_mask) == 0);
921: KASSERT((nocross & (nocross - 1)) == 0);
922: KASSERT((align == 0 && phase == 0) || phase < align);
923: KASSERT(nocross == 0 || nocross >= size);
1.60 ! dyoung 924: KASSERT(minaddr <= maxaddr);
1.19 yamt 925: KASSERT(!VMEM_CROSS_P(phase, phase + size - 1, nocross));
1.10 yamt 926:
927: if (align == 0) {
928: align = vm->vm_quantum_mask + 1;
929: }
1.59 yamt 930:
931: /*
932: * allocate boundary tags before acquiring the vmem lock.
933: */
1.1 yamt 934: btnew = bt_alloc(vm, flags);
935: if (btnew == NULL) {
936: return VMEM_ADDR_NULL;
937: }
1.10 yamt 938: btnew2 = bt_alloc(vm, flags); /* XXX not necessary if no restrictions */
939: if (btnew2 == NULL) {
940: bt_free(vm, btnew);
941: return VMEM_ADDR_NULL;
942: }
1.1 yamt 943:
1.59 yamt 944: /*
945: * choose a free block from which we allocate.
946: */
1.1 yamt 947: retry_strat:
948: first = bt_freehead_toalloc(vm, size, strat);
949: end = &vm->vm_freelist[VMEM_MAXORDER];
950: retry:
951: bt = NULL;
952: VMEM_LOCK(vm);
1.55 yamt 953: vmem_check(vm);
1.2 yamt 954: if (strat == VM_INSTANTFIT) {
1.59 yamt 955: /*
956: * just choose the first block which satisfies our restrictions.
957: *
958: * note that we don't need to check the size of the blocks
959: * because any blocks found on these list should be larger than
960: * the given size.
961: */
1.2 yamt 962: for (list = first; list < end; list++) {
963: bt = LIST_FIRST(list);
964: if (bt != NULL) {
1.10 yamt 965: start = vmem_fit(bt, size, align, phase,
966: nocross, minaddr, maxaddr);
967: if (start != VMEM_ADDR_NULL) {
968: goto gotit;
969: }
1.59 yamt 970: /*
971: * don't bother to follow the bt_freelist link
972: * here. the list can be very long and we are
973: * told to run fast. blocks from the later free
974: * lists are larger and have better chances to
975: * satisfy our restrictions.
976: */
1.2 yamt 977: }
978: }
979: } else { /* VM_BESTFIT */
1.59 yamt 980: /*
981: * we assume that, for space efficiency, it's better to
982: * allocate from a smaller block. thus we will start searching
983: * from the lower-order list than VM_INSTANTFIT.
984: * however, don't bother to find the smallest block in a free
985: * list because the list can be very long. we can revisit it
986: * if/when it turns out to be a problem.
987: *
988: * note that the 'first' list can contain blocks smaller than
989: * the requested size. thus we need to check bt_size.
990: */
1.2 yamt 991: for (list = first; list < end; list++) {
992: LIST_FOREACH(bt, list, bt_freelist) {
993: if (bt->bt_size >= size) {
1.10 yamt 994: start = vmem_fit(bt, size, align, phase,
995: nocross, minaddr, maxaddr);
996: if (start != VMEM_ADDR_NULL) {
997: goto gotit;
998: }
1.2 yamt 999: }
1.1 yamt 1000: }
1001: }
1002: }
1.2 yamt 1003: VMEM_UNLOCK(vm);
1.1 yamt 1004: #if 1
1.2 yamt 1005: if (strat == VM_INSTANTFIT) {
1006: strat = VM_BESTFIT;
1007: goto retry_strat;
1008: }
1.1 yamt 1009: #endif
1.10 yamt 1010: if (align != vm->vm_quantum_mask + 1 || phase != 0 ||
1.60 ! dyoung 1011: nocross != 0) {
1.10 yamt 1012:
1013: /*
1014: * XXX should try to import a region large enough to
1015: * satisfy restrictions?
1016: */
1017:
1.20 yamt 1018: goto fail;
1.10 yamt 1019: }
1.60 ! dyoung 1020: /* XXX eeek, minaddr & maxaddr not respected */
1.2 yamt 1021: if (vmem_import(vm, size, flags) == 0) {
1022: goto retry;
1.1 yamt 1023: }
1.2 yamt 1024: /* XXX */
1.20 yamt 1025: fail:
1026: bt_free(vm, btnew);
1027: bt_free(vm, btnew2);
1.2 yamt 1028: return VMEM_ADDR_NULL;
1029:
1030: gotit:
1.1 yamt 1031: KASSERT(bt->bt_type == BT_TYPE_FREE);
1032: KASSERT(bt->bt_size >= size);
1033: bt_remfree(vm, bt);
1.55 yamt 1034: vmem_check(vm);
1.10 yamt 1035: if (bt->bt_start != start) {
1036: btnew2->bt_type = BT_TYPE_FREE;
1037: btnew2->bt_start = bt->bt_start;
1038: btnew2->bt_size = start - bt->bt_start;
1039: bt->bt_start = start;
1040: bt->bt_size -= btnew2->bt_size;
1041: bt_insfree(vm, btnew2);
1042: bt_insseg(vm, btnew2, CIRCLEQ_PREV(bt, bt_seglist));
1043: btnew2 = NULL;
1.55 yamt 1044: vmem_check(vm);
1.10 yamt 1045: }
1046: KASSERT(bt->bt_start == start);
1.1 yamt 1047: if (bt->bt_size != size && bt->bt_size - size > vm->vm_quantum_mask) {
1048: /* split */
1049: btnew->bt_type = BT_TYPE_BUSY;
1050: btnew->bt_start = bt->bt_start;
1051: btnew->bt_size = size;
1052: bt->bt_start = bt->bt_start + size;
1053: bt->bt_size -= size;
1054: bt_insfree(vm, bt);
1055: bt_insseg(vm, btnew, CIRCLEQ_PREV(bt, bt_seglist));
1056: bt_insbusy(vm, btnew);
1.55 yamt 1057: vmem_check(vm);
1.1 yamt 1058: VMEM_UNLOCK(vm);
1059: } else {
1060: bt->bt_type = BT_TYPE_BUSY;
1061: bt_insbusy(vm, bt);
1.55 yamt 1062: vmem_check(vm);
1.1 yamt 1063: VMEM_UNLOCK(vm);
1064: bt_free(vm, btnew);
1065: btnew = bt;
1066: }
1.10 yamt 1067: if (btnew2 != NULL) {
1068: bt_free(vm, btnew2);
1069: }
1.1 yamt 1070: KASSERT(btnew->bt_size >= size);
1071: btnew->bt_type = BT_TYPE_BUSY;
1072:
1073: return btnew->bt_start;
1074: }
1075:
1076: /*
1077: * vmem_free:
1078: *
1079: * => caller must ensure appropriate spl,
1080: * if the arena can be accessed from interrupt context.
1081: */
1082:
1083: void
1084: vmem_free(vmem_t *vm, vmem_addr_t addr, vmem_size_t size)
1085: {
1086:
1087: KASSERT(addr != VMEM_ADDR_NULL);
1088: KASSERT(size > 0);
1089:
1.5 yamt 1090: #if defined(QCACHE)
1091: if (size <= vm->vm_qcache_max) {
1092: int qidx = (size + vm->vm_quantum_mask) >> vm->vm_quantum_shift;
1.22 yamt 1093: qcache_t *qc = vm->vm_qcache[qidx - 1];
1.5 yamt 1094:
1.35 ad 1095: return pool_cache_put(qc->qc_cache, (void *)addr);
1.5 yamt 1096: }
1097: #endif /* defined(QCACHE) */
1098:
1.10 yamt 1099: vmem_xfree(vm, addr, size);
1100: }
1101:
1102: void
1.17 yamt 1103: vmem_xfree(vmem_t *vm, vmem_addr_t addr, vmem_size_t size)
1.10 yamt 1104: {
1105: bt_t *bt;
1106: bt_t *t;
1107:
1108: KASSERT(addr != VMEM_ADDR_NULL);
1109: KASSERT(size > 0);
1110:
1.1 yamt 1111: VMEM_LOCK(vm);
1112:
1113: bt = bt_lookupbusy(vm, addr);
1114: KASSERT(bt != NULL);
1115: KASSERT(bt->bt_start == addr);
1116: KASSERT(bt->bt_size == vmem_roundup_size(vm, size) ||
1117: bt->bt_size - vmem_roundup_size(vm, size) <= vm->vm_quantum_mask);
1118: KASSERT(bt->bt_type == BT_TYPE_BUSY);
1119: bt_rembusy(vm, bt);
1120: bt->bt_type = BT_TYPE_FREE;
1121:
1122: /* coalesce */
1123: t = CIRCLEQ_NEXT(bt, bt_seglist);
1124: if (t != NULL && t->bt_type == BT_TYPE_FREE) {
1.60 ! dyoung 1125: KASSERT(BT_END(bt) < t->bt_start); /* YYY */
1.1 yamt 1126: bt_remfree(vm, t);
1127: bt_remseg(vm, t);
1128: bt->bt_size += t->bt_size;
1129: bt_free(vm, t);
1130: }
1131: t = CIRCLEQ_PREV(bt, bt_seglist);
1132: if (t != NULL && t->bt_type == BT_TYPE_FREE) {
1.60 ! dyoung 1133: KASSERT(BT_END(t) < bt->bt_start); /* YYY */
1.1 yamt 1134: bt_remfree(vm, t);
1135: bt_remseg(vm, t);
1136: bt->bt_size += t->bt_size;
1137: bt->bt_start = t->bt_start;
1138: bt_free(vm, t);
1139: }
1140:
1141: t = CIRCLEQ_PREV(bt, bt_seglist);
1142: KASSERT(t != NULL);
1143: KASSERT(BT_ISSPAN_P(t) || t->bt_type == BT_TYPE_BUSY);
1144: if (vm->vm_freefn != NULL && t->bt_type == BT_TYPE_SPAN &&
1145: t->bt_size == bt->bt_size) {
1146: vmem_addr_t spanaddr;
1147: vmem_size_t spansize;
1148:
1149: KASSERT(t->bt_start == bt->bt_start);
1150: spanaddr = bt->bt_start;
1151: spansize = bt->bt_size;
1152: bt_remseg(vm, bt);
1153: bt_free(vm, bt);
1154: bt_remseg(vm, t);
1155: bt_free(vm, t);
1156: VMEM_UNLOCK(vm);
1157: (*vm->vm_freefn)(vm->vm_source, spanaddr, spansize);
1158: } else {
1159: bt_insfree(vm, bt);
1160: VMEM_UNLOCK(vm);
1161: }
1162: }
1163:
1164: /*
1165: * vmem_add:
1166: *
1167: * => caller must ensure appropriate spl,
1168: * if the arena can be accessed from interrupt context.
1169: */
1170:
1171: vmem_addr_t
1172: vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, vm_flag_t flags)
1173: {
1174:
1175: return vmem_add1(vm, addr, size, flags, BT_TYPE_SPAN_STATIC);
1176: }
1177:
1.6 yamt 1178: /*
1179: * vmem_reap: reap unused resources.
1180: *
1.26 thorpej 1181: * => return true if we successfully reaped something.
1.6 yamt 1182: */
1183:
1.25 thorpej 1184: bool
1.6 yamt 1185: vmem_reap(vmem_t *vm)
1186: {
1.26 thorpej 1187: bool didsomething = false;
1.6 yamt 1188:
1189: #if defined(QCACHE)
1190: didsomething = qc_reap(vm);
1191: #endif /* defined(QCACHE) */
1192: return didsomething;
1193: }
1194:
1.30 yamt 1195: /* ---- rehash */
1196:
1197: #if defined(_KERNEL)
1198: static struct callout vmem_rehash_ch;
1199: static int vmem_rehash_interval;
1200: static struct workqueue *vmem_rehash_wq;
1201: static struct work vmem_rehash_wk;
1202:
1203: static void
1204: vmem_rehash_all(struct work *wk, void *dummy)
1205: {
1206: vmem_t *vm;
1207:
1208: KASSERT(wk == &vmem_rehash_wk);
1209: mutex_enter(&vmem_list_lock);
1210: LIST_FOREACH(vm, &vmem_list, vm_alllist) {
1211: size_t desired;
1212: size_t current;
1213:
1214: if (!VMEM_TRYLOCK(vm)) {
1215: continue;
1216: }
1217: desired = vm->vm_nbusytag;
1218: current = vm->vm_hashsize;
1219: VMEM_UNLOCK(vm);
1220:
1221: if (desired > VMEM_HASHSIZE_MAX) {
1222: desired = VMEM_HASHSIZE_MAX;
1223: } else if (desired < VMEM_HASHSIZE_MIN) {
1224: desired = VMEM_HASHSIZE_MIN;
1225: }
1226: if (desired > current * 2 || desired * 2 < current) {
1227: vmem_rehash(vm, desired, VM_NOSLEEP);
1228: }
1229: }
1230: mutex_exit(&vmem_list_lock);
1231:
1232: callout_schedule(&vmem_rehash_ch, vmem_rehash_interval);
1233: }
1234:
1235: static void
1236: vmem_rehash_all_kick(void *dummy)
1237: {
1238:
1.32 rmind 1239: workqueue_enqueue(vmem_rehash_wq, &vmem_rehash_wk, NULL);
1.30 yamt 1240: }
1241:
1242: void
1243: vmem_rehash_start(void)
1244: {
1245: int error;
1246:
1247: error = workqueue_create(&vmem_rehash_wq, "vmem_rehash",
1.41 ad 1248: vmem_rehash_all, NULL, PRI_VM, IPL_SOFTCLOCK, WQ_MPSAFE);
1.30 yamt 1249: if (error) {
1250: panic("%s: workqueue_create %d\n", __func__, error);
1251: }
1.41 ad 1252: callout_init(&vmem_rehash_ch, CALLOUT_MPSAFE);
1.30 yamt 1253: callout_setfunc(&vmem_rehash_ch, vmem_rehash_all_kick, NULL);
1254:
1255: vmem_rehash_interval = hz * 10;
1256: callout_schedule(&vmem_rehash_ch, vmem_rehash_interval);
1257: }
1258: #endif /* defined(_KERNEL) */
1259:
1.1 yamt 1260: /* ---- debug */
1261:
1.55 yamt 1262: #if defined(DDB) || defined(UNITTEST) || defined(VMEM_SANITY)
1263:
1264: static void bt_dump(const bt_t *, void (*)(const char *, ...));
1265:
1266: static const char *
1267: bt_type_string(int type)
1268: {
1269: static const char * const table[] = {
1270: [BT_TYPE_BUSY] = "busy",
1271: [BT_TYPE_FREE] = "free",
1272: [BT_TYPE_SPAN] = "span",
1273: [BT_TYPE_SPAN_STATIC] = "static span",
1274: };
1275:
1276: if (type >= __arraycount(table)) {
1277: return "BOGUS";
1278: }
1279: return table[type];
1280: }
1281:
1282: static void
1283: bt_dump(const bt_t *bt, void (*pr)(const char *, ...))
1284: {
1285:
1286: (*pr)("\t%p: %" PRIu64 ", %" PRIu64 ", %d(%s)\n",
1287: bt, (uint64_t)bt->bt_start, (uint64_t)bt->bt_size,
1288: bt->bt_type, bt_type_string(bt->bt_type));
1289: }
1290:
1291: static void
1292: vmem_dump(const vmem_t *vm , void (*pr)(const char *, ...))
1293: {
1294: const bt_t *bt;
1295: int i;
1296:
1297: (*pr)("vmem %p '%s'\n", vm, vm->vm_name);
1298: CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) {
1299: bt_dump(bt, pr);
1300: }
1301:
1302: for (i = 0; i < VMEM_MAXORDER; i++) {
1303: const struct vmem_freelist *fl = &vm->vm_freelist[i];
1304:
1305: if (LIST_EMPTY(fl)) {
1306: continue;
1307: }
1308:
1309: (*pr)("freelist[%d]\n", i);
1310: LIST_FOREACH(bt, fl, bt_freelist) {
1311: bt_dump(bt, pr);
1312: }
1313: }
1314: }
1315:
1316: #endif /* defined(DDB) || defined(UNITTEST) || defined(VMEM_SANITY) */
1317:
1.37 yamt 1318: #if defined(DDB)
1319: static bt_t *
1320: vmem_whatis_lookup(vmem_t *vm, uintptr_t addr)
1321: {
1.39 yamt 1322: bt_t *bt;
1.37 yamt 1323:
1.39 yamt 1324: CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) {
1325: if (BT_ISSPAN_P(bt)) {
1326: continue;
1327: }
1.60 ! dyoung 1328: if (bt->bt_start <= addr && addr <= BT_END(bt)) {
1.39 yamt 1329: return bt;
1.37 yamt 1330: }
1331: }
1332:
1333: return NULL;
1334: }
1335:
1336: void
1337: vmem_whatis(uintptr_t addr, void (*pr)(const char *, ...))
1338: {
1339: vmem_t *vm;
1340:
1341: LIST_FOREACH(vm, &vmem_list, vm_alllist) {
1342: bt_t *bt;
1343:
1344: bt = vmem_whatis_lookup(vm, addr);
1345: if (bt == NULL) {
1346: continue;
1347: }
1.39 yamt 1348: (*pr)("%p is %p+%zu in VMEM '%s' (%s)\n",
1.37 yamt 1349: (void *)addr, (void *)bt->bt_start,
1.39 yamt 1350: (size_t)(addr - bt->bt_start), vm->vm_name,
1351: (bt->bt_type == BT_TYPE_BUSY) ? "allocated" : "free");
1.37 yamt 1352: }
1353: }
1.43 cegger 1354:
1.55 yamt 1355: void
1356: vmem_printall(const char *modif, void (*pr)(const char *, ...))
1.43 cegger 1357: {
1.55 yamt 1358: const vmem_t *vm;
1.43 cegger 1359:
1.47 cegger 1360: LIST_FOREACH(vm, &vmem_list, vm_alllist) {
1.55 yamt 1361: vmem_dump(vm, pr);
1.43 cegger 1362: }
1363: }
1364:
1365: void
1366: vmem_print(uintptr_t addr, const char *modif, void (*pr)(const char *, ...))
1367: {
1.55 yamt 1368: const vmem_t *vm = (const void *)addr;
1.43 cegger 1369:
1.55 yamt 1370: vmem_dump(vm, pr);
1.43 cegger 1371: }
1.37 yamt 1372: #endif /* defined(DDB) */
1373:
1.60 ! dyoung 1374: #if defined(_KERNEL)
! 1375: #define vmem_printf printf
! 1376: #else
1.1 yamt 1377: #include <stdio.h>
1.60 ! dyoung 1378: #include <stdarg.h>
! 1379:
! 1380: static void
! 1381: vmem_printf(const char *fmt, ...)
! 1382: {
! 1383: va_list ap;
! 1384: va_start(ap, fmt);
! 1385: vprintf(fmt, ap);
! 1386: va_end(ap);
! 1387: }
! 1388: #endif
1.1 yamt 1389:
1.55 yamt 1390: #if defined(VMEM_SANITY)
1.1 yamt 1391:
1.55 yamt 1392: static bool
1393: vmem_check_sanity(vmem_t *vm)
1.1 yamt 1394: {
1.55 yamt 1395: const bt_t *bt, *bt2;
1.1 yamt 1396:
1.55 yamt 1397: KASSERT(vm != NULL);
1.1 yamt 1398:
1399: CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) {
1.60 ! dyoung 1400: if (bt->bt_start > BT_END(bt)) {
1.55 yamt 1401: printf("corrupted tag\n");
1.60 ! dyoung 1402: bt_dump(bt, vmem_printf);
1.55 yamt 1403: return false;
1404: }
1405: }
1406: CIRCLEQ_FOREACH(bt, &vm->vm_seglist, bt_seglist) {
1407: CIRCLEQ_FOREACH(bt2, &vm->vm_seglist, bt_seglist) {
1408: if (bt == bt2) {
1409: continue;
1410: }
1411: if (BT_ISSPAN_P(bt) != BT_ISSPAN_P(bt2)) {
1412: continue;
1413: }
1.60 ! dyoung 1414: if (bt->bt_start <= BT_END(bt2) &&
! 1415: bt2->bt_start <= BT_END(bt)) {
1.55 yamt 1416: printf("overwrapped tags\n");
1.60 ! dyoung 1417: bt_dump(bt, vmem_printf);
! 1418: bt_dump(bt2, vmem_printf);
1.55 yamt 1419: return false;
1420: }
1421: }
1.1 yamt 1422: }
1423:
1.55 yamt 1424: return true;
1425: }
1.1 yamt 1426:
1.55 yamt 1427: static void
1428: vmem_check(vmem_t *vm)
1429: {
1.1 yamt 1430:
1.55 yamt 1431: if (!vmem_check_sanity(vm)) {
1432: panic("insanity vmem %p", vm);
1.1 yamt 1433: }
1434: }
1435:
1.55 yamt 1436: #endif /* defined(VMEM_SANITY) */
1.1 yamt 1437:
1.55 yamt 1438: #if defined(UNITTEST)
1.1 yamt 1439: int
1.57 cegger 1440: main(void)
1.1 yamt 1441: {
1442: vmem_t *vm;
1443: vmem_addr_t p;
1444: struct reg {
1445: vmem_addr_t p;
1446: vmem_size_t sz;
1.25 thorpej 1447: bool x;
1.1 yamt 1448: } *reg = NULL;
1449: int nreg = 0;
1450: int nalloc = 0;
1451: int nfree = 0;
1452: vmem_size_t total = 0;
1453: #if 1
1454: vm_flag_t strat = VM_INSTANTFIT;
1455: #else
1456: vm_flag_t strat = VM_BESTFIT;
1457: #endif
1458:
1459: vm = vmem_create("test", VMEM_ADDR_NULL, 0, 1,
1.55 yamt 1460: NULL, NULL, NULL, 0, VM_SLEEP, 0/*XXX*/);
1.1 yamt 1461: if (vm == NULL) {
1462: printf("vmem_create\n");
1463: exit(EXIT_FAILURE);
1464: }
1.60 ! dyoung 1465: vmem_dump(vm, vmem_printf);
1.1 yamt 1466:
1467: p = vmem_add(vm, 100, 200, VM_SLEEP);
1.60 ! dyoung 1468: assert(p != VMEM_ADDR_NULL);
1.1 yamt 1469: p = vmem_add(vm, 2000, 1, VM_SLEEP);
1.60 ! dyoung 1470: assert(p != VMEM_ADDR_NULL);
! 1471: p = vmem_add(vm, 40000, 65536, VM_SLEEP);
! 1472: assert(p != VMEM_ADDR_NULL);
1.1 yamt 1473: p = vmem_add(vm, 10000, 10000, VM_SLEEP);
1.60 ! dyoung 1474: assert(p != VMEM_ADDR_NULL);
1.1 yamt 1475: p = vmem_add(vm, 500, 1000, VM_SLEEP);
1.60 ! dyoung 1476: assert(p != VMEM_ADDR_NULL);
! 1477: p = vmem_add(vm, 0xffffff00, 0x100, VM_SLEEP);
! 1478: assert(p != VMEM_ADDR_NULL);
! 1479: p = vmem_xalloc(vm, 0x101, 0, 0, 0,
! 1480: 0xffffff00, 0xffffffff, strat|VM_SLEEP);
! 1481: assert(p == VMEM_ADDR_NULL);
! 1482: p = vmem_xalloc(vm, 0x100, 0, 0, 0,
! 1483: 0xffffff01, 0xffffffff, strat|VM_SLEEP);
! 1484: assert(p == VMEM_ADDR_NULL);
! 1485: p = vmem_xalloc(vm, 0x100, 0, 0, 0,
! 1486: 0xffffff00, 0xfffffffe, strat|VM_SLEEP);
! 1487: assert(p == VMEM_ADDR_NULL);
! 1488: p = vmem_xalloc(vm, 0x100, 0, 0, 0,
! 1489: 0xffffff00, 0xffffffff, strat|VM_SLEEP);
! 1490: assert(p != VMEM_ADDR_NULL);
! 1491: vmem_dump(vm, vmem_printf);
1.1 yamt 1492: for (;;) {
1493: struct reg *r;
1.10 yamt 1494: int t = rand() % 100;
1.1 yamt 1495:
1.10 yamt 1496: if (t > 45) {
1497: /* alloc */
1.1 yamt 1498: vmem_size_t sz = rand() % 500 + 1;
1.25 thorpej 1499: bool x;
1.10 yamt 1500: vmem_size_t align, phase, nocross;
1501: vmem_addr_t minaddr, maxaddr;
1502:
1503: if (t > 70) {
1.26 thorpej 1504: x = true;
1.10 yamt 1505: /* XXX */
1506: align = 1 << (rand() % 15);
1507: phase = rand() % 65536;
1508: nocross = 1 << (rand() % 15);
1509: if (align <= phase) {
1510: phase = 0;
1511: }
1.19 yamt 1512: if (VMEM_CROSS_P(phase, phase + sz - 1,
1513: nocross)) {
1.10 yamt 1514: nocross = 0;
1515: }
1.60 ! dyoung 1516: do {
! 1517: minaddr = rand() % 50000;
! 1518: maxaddr = rand() % 70000;
! 1519: } while (minaddr > maxaddr);
1.10 yamt 1520: printf("=== xalloc %" PRIu64
1521: " align=%" PRIu64 ", phase=%" PRIu64
1522: ", nocross=%" PRIu64 ", min=%" PRIu64
1523: ", max=%" PRIu64 "\n",
1524: (uint64_t)sz,
1525: (uint64_t)align,
1526: (uint64_t)phase,
1527: (uint64_t)nocross,
1528: (uint64_t)minaddr,
1529: (uint64_t)maxaddr);
1530: p = vmem_xalloc(vm, sz, align, phase, nocross,
1531: minaddr, maxaddr, strat|VM_SLEEP);
1532: } else {
1.26 thorpej 1533: x = false;
1.10 yamt 1534: printf("=== alloc %" PRIu64 "\n", (uint64_t)sz);
1535: p = vmem_alloc(vm, sz, strat|VM_SLEEP);
1536: }
1.1 yamt 1537: printf("-> %" PRIu64 "\n", (uint64_t)p);
1.60 ! dyoung 1538: vmem_dump(vm, vmem_printf);
1.1 yamt 1539: if (p == VMEM_ADDR_NULL) {
1.10 yamt 1540: if (x) {
1541: continue;
1542: }
1.1 yamt 1543: break;
1544: }
1545: nreg++;
1546: reg = realloc(reg, sizeof(*reg) * nreg);
1547: r = ®[nreg - 1];
1548: r->p = p;
1549: r->sz = sz;
1.10 yamt 1550: r->x = x;
1.1 yamt 1551: total += sz;
1552: nalloc++;
1553: } else if (nreg != 0) {
1.10 yamt 1554: /* free */
1.1 yamt 1555: r = ®[rand() % nreg];
1556: printf("=== free %" PRIu64 ", %" PRIu64 "\n",
1557: (uint64_t)r->p, (uint64_t)r->sz);
1.10 yamt 1558: if (r->x) {
1559: vmem_xfree(vm, r->p, r->sz);
1560: } else {
1561: vmem_free(vm, r->p, r->sz);
1562: }
1.1 yamt 1563: total -= r->sz;
1.60 ! dyoung 1564: vmem_dump(vm, vmem_printf);
1.1 yamt 1565: *r = reg[nreg - 1];
1566: nreg--;
1567: nfree++;
1568: }
1569: printf("total=%" PRIu64 "\n", (uint64_t)total);
1570: }
1571: fprintf(stderr, "total=%" PRIu64 ", nalloc=%d, nfree=%d\n",
1572: (uint64_t)total, nalloc, nfree);
1573: exit(EXIT_SUCCESS);
1574: }
1.55 yamt 1575: #endif /* defined(UNITTEST) */
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to subr_vmem.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / sys / kern