[BACK]Return to subr_vmem.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / kern

Annotation of src/sys/kern/subr_vmem.c, Revision 1.85

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

CVSweb <webmaster@jp.NetBSD.org>