The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_vmem.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: acf0e1efdc3e5ace8cbf8c929e5c3c7b


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.