[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.94

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

CVSweb <webmaster@jp.NetBSD.org>