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/vm/uma_core.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 /*-
    2  * Copyright (c) 2002-2005, 2009 Jeffrey Roberson <jeff@FreeBSD.org>
    3  * Copyright (c) 2004, 2005 Bosko Milekic <bmilekic@FreeBSD.org>
    4  * Copyright (c) 2004-2006 Robert N. M. Watson
    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 unmodified, this list of conditions, and the following
   12  *    disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in the
   15  *    documentation and/or other materials provided with the distribution.
   16  *
   17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   27  */
   28 
   29 /*
   30  * uma_core.c  Implementation of the Universal Memory allocator
   31  *
   32  * This allocator is intended to replace the multitude of similar object caches
   33  * in the standard FreeBSD kernel.  The intent is to be flexible as well as
   34  * effecient.  A primary design goal is to return unused memory to the rest of
   35  * the system.  This will make the system as a whole more flexible due to the
   36  * ability to move memory to subsystems which most need it instead of leaving
   37  * pools of reserved memory unused.
   38  *
   39  * The basic ideas stem from similar slab/zone based allocators whose algorithms
   40  * are well known.
   41  *
   42  */
   43 
   44 /*
   45  * TODO:
   46  *      - Improve memory usage for large allocations
   47  *      - Investigate cache size adjustments
   48  */
   49 
   50 #include <sys/cdefs.h>
   51 __FBSDID("$FreeBSD: releng/8.3/sys/vm/uma_core.c 217500 2011-01-17 05:45:55Z lstewart $");
   52 
   53 /* I should really use ktr.. */
   54 /*
   55 #define UMA_DEBUG 1
   56 #define UMA_DEBUG_ALLOC 1
   57 #define UMA_DEBUG_ALLOC_1 1
   58 */
   59 
   60 #include "opt_ddb.h"
   61 #include "opt_param.h"
   62 
   63 #include <sys/param.h>
   64 #include <sys/systm.h>
   65 #include <sys/kernel.h>
   66 #include <sys/types.h>
   67 #include <sys/queue.h>
   68 #include <sys/malloc.h>
   69 #include <sys/ktr.h>
   70 #include <sys/lock.h>
   71 #include <sys/sysctl.h>
   72 #include <sys/mutex.h>
   73 #include <sys/proc.h>
   74 #include <sys/sbuf.h>
   75 #include <sys/smp.h>
   76 #include <sys/vmmeter.h>
   77 
   78 #include <vm/vm.h>
   79 #include <vm/vm_object.h>
   80 #include <vm/vm_page.h>
   81 #include <vm/vm_param.h>
   82 #include <vm/vm_map.h>
   83 #include <vm/vm_kern.h>
   84 #include <vm/vm_extern.h>
   85 #include <vm/uma.h>
   86 #include <vm/uma_int.h>
   87 #include <vm/uma_dbg.h>
   88 
   89 #include <machine/vmparam.h>
   90 
   91 #include <ddb/ddb.h>
   92 
   93 /*
   94  * This is the zone and keg from which all zones are spawned.  The idea is that
   95  * even the zone & keg heads are allocated from the allocator, so we use the
   96  * bss section to bootstrap us.
   97  */
   98 static struct uma_keg masterkeg;
   99 static struct uma_zone masterzone_k;
  100 static struct uma_zone masterzone_z;
  101 static uma_zone_t kegs = &masterzone_k;
  102 static uma_zone_t zones = &masterzone_z;
  103 
  104 /* This is the zone from which all of uma_slab_t's are allocated. */
  105 static uma_zone_t slabzone;
  106 static uma_zone_t slabrefzone;  /* With refcounters (for UMA_ZONE_REFCNT) */
  107 
  108 /*
  109  * The initial hash tables come out of this zone so they can be allocated
  110  * prior to malloc coming up.
  111  */
  112 static uma_zone_t hashzone;
  113 
  114 /* The boot-time adjusted value for cache line alignment. */
  115 static int uma_align_cache = 64 - 1;
  116 
  117 static MALLOC_DEFINE(M_UMAHASH, "UMAHash", "UMA Hash Buckets");
  118 
  119 /*
  120  * Are we allowed to allocate buckets?
  121  */
  122 static int bucketdisable = 1;
  123 
  124 /* Linked list of all kegs in the system */
  125 static LIST_HEAD(,uma_keg) uma_kegs = LIST_HEAD_INITIALIZER(uma_kegs);
  126 
  127 /* This mutex protects the keg list */
  128 static struct mtx uma_mtx;
  129 
  130 /* Linked list of boot time pages */
  131 static LIST_HEAD(,uma_slab) uma_boot_pages =
  132     LIST_HEAD_INITIALIZER(uma_boot_pages);
  133 
  134 /* This mutex protects the boot time pages list */
  135 static struct mtx uma_boot_pages_mtx;
  136 
  137 /* Is the VM done starting up? */
  138 static int booted = 0;
  139 
  140 /* Maximum number of allowed items-per-slab if the slab header is OFFPAGE */
  141 static u_int uma_max_ipers;
  142 static u_int uma_max_ipers_ref;
  143 
  144 /*
  145  * This is the handle used to schedule events that need to happen
  146  * outside of the allocation fast path.
  147  */
  148 static struct callout uma_callout;
  149 #define UMA_TIMEOUT     20              /* Seconds for callout interval. */
  150 
  151 /*
  152  * This structure is passed as the zone ctor arg so that I don't have to create
  153  * a special allocation function just for zones.
  154  */
  155 struct uma_zctor_args {
  156         char *name;
  157         size_t size;
  158         uma_ctor ctor;
  159         uma_dtor dtor;
  160         uma_init uminit;
  161         uma_fini fini;
  162         uma_keg_t keg;
  163         int align;
  164         u_int32_t flags;
  165 };
  166 
  167 struct uma_kctor_args {
  168         uma_zone_t zone;
  169         size_t size;
  170         uma_init uminit;
  171         uma_fini fini;
  172         int align;
  173         u_int32_t flags;
  174 };
  175 
  176 struct uma_bucket_zone {
  177         uma_zone_t      ubz_zone;
  178         char            *ubz_name;
  179         int             ubz_entries;
  180 };
  181 
  182 #define BUCKET_MAX      128
  183 
  184 struct uma_bucket_zone bucket_zones[] = {
  185         { NULL, "16 Bucket", 16 },
  186         { NULL, "32 Bucket", 32 },
  187         { NULL, "64 Bucket", 64 },
  188         { NULL, "128 Bucket", 128 },
  189         { NULL, NULL, 0}
  190 };
  191 
  192 #define BUCKET_SHIFT    4
  193 #define BUCKET_ZONES    ((BUCKET_MAX >> BUCKET_SHIFT) + 1)
  194 
  195 /*
  196  * bucket_size[] maps requested bucket sizes to zones that allocate a bucket
  197  * of approximately the right size.
  198  */
  199 static uint8_t bucket_size[BUCKET_ZONES];
  200 
  201 /*
  202  * Flags and enumerations to be passed to internal functions.
  203  */
  204 enum zfreeskip { SKIP_NONE, SKIP_DTOR, SKIP_FINI };
  205 
  206 #define ZFREE_STATFAIL  0x00000001      /* Update zone failure statistic. */
  207 #define ZFREE_STATFREE  0x00000002      /* Update zone free statistic. */
  208 
  209 /* Prototypes.. */
  210 
  211 static void *obj_alloc(uma_zone_t, int, u_int8_t *, int);
  212 static void *page_alloc(uma_zone_t, int, u_int8_t *, int);
  213 static void *startup_alloc(uma_zone_t, int, u_int8_t *, int);
  214 static void page_free(void *, int, u_int8_t);
  215 static uma_slab_t keg_alloc_slab(uma_keg_t, uma_zone_t, int);
  216 static void cache_drain(uma_zone_t);
  217 static void bucket_drain(uma_zone_t, uma_bucket_t);
  218 static void bucket_cache_drain(uma_zone_t zone);
  219 static int keg_ctor(void *, int, void *, int);
  220 static void keg_dtor(void *, int, void *);
  221 static int zone_ctor(void *, int, void *, int);
  222 static void zone_dtor(void *, int, void *);
  223 static int zero_init(void *, int, int);
  224 static void keg_small_init(uma_keg_t keg);
  225 static void keg_large_init(uma_keg_t keg);
  226 static void zone_foreach(void (*zfunc)(uma_zone_t));
  227 static void zone_timeout(uma_zone_t zone);
  228 static int hash_alloc(struct uma_hash *);
  229 static int hash_expand(struct uma_hash *, struct uma_hash *);
  230 static void hash_free(struct uma_hash *hash);
  231 static void uma_timeout(void *);
  232 static void uma_startup3(void);
  233 static void *zone_alloc_item(uma_zone_t, void *, int);
  234 static void zone_free_item(uma_zone_t, void *, void *, enum zfreeskip,
  235     int);
  236 static void bucket_enable(void);
  237 static void bucket_init(void);
  238 static uma_bucket_t bucket_alloc(int, int);
  239 static void bucket_free(uma_bucket_t);
  240 static void bucket_zone_drain(void);
  241 static int zone_alloc_bucket(uma_zone_t zone, int flags);
  242 static uma_slab_t zone_fetch_slab(uma_zone_t zone, uma_keg_t last, int flags);
  243 static uma_slab_t zone_fetch_slab_multi(uma_zone_t zone, uma_keg_t last, int flags);
  244 static void *slab_alloc_item(uma_zone_t zone, uma_slab_t slab);
  245 static uma_keg_t uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit,
  246     uma_fini fini, int align, u_int32_t flags);
  247 static inline void zone_relock(uma_zone_t zone, uma_keg_t keg);
  248 static inline void keg_relock(uma_keg_t keg, uma_zone_t zone);
  249 
  250 void uma_print_zone(uma_zone_t);
  251 void uma_print_stats(void);
  252 static int sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS);
  253 static int sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS);
  254 
  255 SYSINIT(uma_startup3, SI_SUB_VM_CONF, SI_ORDER_SECOND, uma_startup3, NULL);
  256 
  257 SYSCTL_PROC(_vm, OID_AUTO, zone_count, CTLFLAG_RD|CTLTYPE_INT,
  258     0, 0, sysctl_vm_zone_count, "I", "Number of UMA zones");
  259 
  260 SYSCTL_PROC(_vm, OID_AUTO, zone_stats, CTLFLAG_RD|CTLTYPE_STRUCT,
  261     0, 0, sysctl_vm_zone_stats, "s,struct uma_type_header", "Zone Stats");
  262 
  263 /*
  264  * This routine checks to see whether or not it's safe to enable buckets.
  265  */
  266 
  267 static void
  268 bucket_enable(void)
  269 {
  270         if (cnt.v_free_count < cnt.v_free_min)
  271                 bucketdisable = 1;
  272         else
  273                 bucketdisable = 0;
  274 }
  275 
  276 /*
  277  * Initialize bucket_zones, the array of zones of buckets of various sizes.
  278  *
  279  * For each zone, calculate the memory required for each bucket, consisting
  280  * of the header and an array of pointers.  Initialize bucket_size[] to point
  281  * the range of appropriate bucket sizes at the zone.
  282  */
  283 static void
  284 bucket_init(void)
  285 {
  286         struct uma_bucket_zone *ubz;
  287         int i;
  288         int j;
  289 
  290         for (i = 0, j = 0; bucket_zones[j].ubz_entries != 0; j++) {
  291                 int size;
  292 
  293                 ubz = &bucket_zones[j];
  294                 size = roundup(sizeof(struct uma_bucket), sizeof(void *));
  295                 size += sizeof(void *) * ubz->ubz_entries;
  296                 ubz->ubz_zone = uma_zcreate(ubz->ubz_name, size,
  297                     NULL, NULL, NULL, NULL, UMA_ALIGN_PTR,
  298                     UMA_ZFLAG_INTERNAL | UMA_ZFLAG_BUCKET);
  299                 for (; i <= ubz->ubz_entries; i += (1 << BUCKET_SHIFT))
  300                         bucket_size[i >> BUCKET_SHIFT] = j;
  301         }
  302 }
  303 
  304 /*
  305  * Given a desired number of entries for a bucket, return the zone from which
  306  * to allocate the bucket.
  307  */
  308 static struct uma_bucket_zone *
  309 bucket_zone_lookup(int entries)
  310 {
  311         int idx;
  312 
  313         idx = howmany(entries, 1 << BUCKET_SHIFT);
  314         return (&bucket_zones[bucket_size[idx]]);
  315 }
  316 
  317 static uma_bucket_t
  318 bucket_alloc(int entries, int bflags)
  319 {
  320         struct uma_bucket_zone *ubz;
  321         uma_bucket_t bucket;
  322 
  323         /*
  324          * This is to stop us from allocating per cpu buckets while we're
  325          * running out of vm.boot_pages.  Otherwise, we would exhaust the
  326          * boot pages.  This also prevents us from allocating buckets in
  327          * low memory situations.
  328          */
  329         if (bucketdisable)
  330                 return (NULL);
  331 
  332         ubz = bucket_zone_lookup(entries);
  333         bucket = zone_alloc_item(ubz->ubz_zone, NULL, bflags);
  334         if (bucket) {
  335 #ifdef INVARIANTS
  336                 bzero(bucket->ub_bucket, sizeof(void *) * ubz->ubz_entries);
  337 #endif
  338                 bucket->ub_cnt = 0;
  339                 bucket->ub_entries = ubz->ubz_entries;
  340         }
  341 
  342         return (bucket);
  343 }
  344 
  345 static void
  346 bucket_free(uma_bucket_t bucket)
  347 {
  348         struct uma_bucket_zone *ubz;
  349 
  350         ubz = bucket_zone_lookup(bucket->ub_entries);
  351         zone_free_item(ubz->ubz_zone, bucket, NULL, SKIP_NONE,
  352             ZFREE_STATFREE);
  353 }
  354 
  355 static void
  356 bucket_zone_drain(void)
  357 {
  358         struct uma_bucket_zone *ubz;
  359 
  360         for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
  361                 zone_drain(ubz->ubz_zone);
  362 }
  363 
  364 static inline uma_keg_t
  365 zone_first_keg(uma_zone_t zone)
  366 {
  367 
  368         return (LIST_FIRST(&zone->uz_kegs)->kl_keg);
  369 }
  370 
  371 static void
  372 zone_foreach_keg(uma_zone_t zone, void (*kegfn)(uma_keg_t))
  373 {
  374         uma_klink_t klink;
  375 
  376         LIST_FOREACH(klink, &zone->uz_kegs, kl_link)
  377                 kegfn(klink->kl_keg);
  378 }
  379 
  380 /*
  381  * Routine called by timeout which is used to fire off some time interval
  382  * based calculations.  (stats, hash size, etc.)
  383  *
  384  * Arguments:
  385  *      arg   Unused
  386  *
  387  * Returns:
  388  *      Nothing
  389  */
  390 static void
  391 uma_timeout(void *unused)
  392 {
  393         bucket_enable();
  394         zone_foreach(zone_timeout);
  395 
  396         /* Reschedule this event */
  397         callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
  398 }
  399 
  400 /*
  401  * Routine to perform timeout driven calculations.  This expands the
  402  * hashes and does per cpu statistics aggregation.
  403  *
  404  *  Returns nothing.
  405  */
  406 static void
  407 keg_timeout(uma_keg_t keg)
  408 {
  409 
  410         KEG_LOCK(keg);
  411         /*
  412          * Expand the keg hash table.
  413          *
  414          * This is done if the number of slabs is larger than the hash size.
  415          * What I'm trying to do here is completely reduce collisions.  This
  416          * may be a little aggressive.  Should I allow for two collisions max?
  417          */
  418         if (keg->uk_flags & UMA_ZONE_HASH &&
  419             keg->uk_pages / keg->uk_ppera >= keg->uk_hash.uh_hashsize) {
  420                 struct uma_hash newhash;
  421                 struct uma_hash oldhash;
  422                 int ret;
  423 
  424                 /*
  425                  * This is so involved because allocating and freeing
  426                  * while the keg lock is held will lead to deadlock.
  427                  * I have to do everything in stages and check for
  428                  * races.
  429                  */
  430                 newhash = keg->uk_hash;
  431                 KEG_UNLOCK(keg);
  432                 ret = hash_alloc(&newhash);
  433                 KEG_LOCK(keg);
  434                 if (ret) {
  435                         if (hash_expand(&keg->uk_hash, &newhash)) {
  436                                 oldhash = keg->uk_hash;
  437                                 keg->uk_hash = newhash;
  438                         } else
  439                                 oldhash = newhash;
  440 
  441                         KEG_UNLOCK(keg);
  442                         hash_free(&oldhash);
  443                         KEG_LOCK(keg);
  444                 }
  445         }
  446         KEG_UNLOCK(keg);
  447 }
  448 
  449 static void
  450 zone_timeout(uma_zone_t zone)
  451 {
  452 
  453         zone_foreach_keg(zone, &keg_timeout);
  454 }
  455 
  456 /*
  457  * Allocate and zero fill the next sized hash table from the appropriate
  458  * backing store.
  459  *
  460  * Arguments:
  461  *      hash  A new hash structure with the old hash size in uh_hashsize
  462  *
  463  * Returns:
  464  *      1 on sucess and 0 on failure.
  465  */
  466 static int
  467 hash_alloc(struct uma_hash *hash)
  468 {
  469         int oldsize;
  470         int alloc;
  471 
  472         oldsize = hash->uh_hashsize;
  473 
  474         /* We're just going to go to a power of two greater */
  475         if (oldsize)  {
  476                 hash->uh_hashsize = oldsize * 2;
  477                 alloc = sizeof(hash->uh_slab_hash[0]) * hash->uh_hashsize;
  478                 hash->uh_slab_hash = (struct slabhead *)malloc(alloc,
  479                     M_UMAHASH, M_NOWAIT);
  480         } else {
  481                 alloc = sizeof(hash->uh_slab_hash[0]) * UMA_HASH_SIZE_INIT;
  482                 hash->uh_slab_hash = zone_alloc_item(hashzone, NULL,
  483                     M_WAITOK);
  484                 hash->uh_hashsize = UMA_HASH_SIZE_INIT;
  485         }
  486         if (hash->uh_slab_hash) {
  487                 bzero(hash->uh_slab_hash, alloc);
  488                 hash->uh_hashmask = hash->uh_hashsize - 1;
  489                 return (1);
  490         }
  491 
  492         return (0);
  493 }
  494 
  495 /*
  496  * Expands the hash table for HASH zones.  This is done from zone_timeout
  497  * to reduce collisions.  This must not be done in the regular allocation
  498  * path, otherwise, we can recurse on the vm while allocating pages.
  499  *
  500  * Arguments:
  501  *      oldhash  The hash you want to expand
  502  *      newhash  The hash structure for the new table
  503  *
  504  * Returns:
  505  *      Nothing
  506  *
  507  * Discussion:
  508  */
  509 static int
  510 hash_expand(struct uma_hash *oldhash, struct uma_hash *newhash)
  511 {
  512         uma_slab_t slab;
  513         int hval;
  514         int i;
  515 
  516         if (!newhash->uh_slab_hash)
  517                 return (0);
  518 
  519         if (oldhash->uh_hashsize >= newhash->uh_hashsize)
  520                 return (0);
  521 
  522         /*
  523          * I need to investigate hash algorithms for resizing without a
  524          * full rehash.
  525          */
  526 
  527         for (i = 0; i < oldhash->uh_hashsize; i++)
  528                 while (!SLIST_EMPTY(&oldhash->uh_slab_hash[i])) {
  529                         slab = SLIST_FIRST(&oldhash->uh_slab_hash[i]);
  530                         SLIST_REMOVE_HEAD(&oldhash->uh_slab_hash[i], us_hlink);
  531                         hval = UMA_HASH(newhash, slab->us_data);
  532                         SLIST_INSERT_HEAD(&newhash->uh_slab_hash[hval],
  533                             slab, us_hlink);
  534                 }
  535 
  536         return (1);
  537 }
  538 
  539 /*
  540  * Free the hash bucket to the appropriate backing store.
  541  *
  542  * Arguments:
  543  *      slab_hash  The hash bucket we're freeing
  544  *      hashsize   The number of entries in that hash bucket
  545  *
  546  * Returns:
  547  *      Nothing
  548  */
  549 static void
  550 hash_free(struct uma_hash *hash)
  551 {
  552         if (hash->uh_slab_hash == NULL)
  553                 return;
  554         if (hash->uh_hashsize == UMA_HASH_SIZE_INIT)
  555                 zone_free_item(hashzone,
  556                     hash->uh_slab_hash, NULL, SKIP_NONE, ZFREE_STATFREE);
  557         else
  558                 free(hash->uh_slab_hash, M_UMAHASH);
  559 }
  560 
  561 /*
  562  * Frees all outstanding items in a bucket
  563  *
  564  * Arguments:
  565  *      zone   The zone to free to, must be unlocked.
  566  *      bucket The free/alloc bucket with items, cpu queue must be locked.
  567  *
  568  * Returns:
  569  *      Nothing
  570  */
  571 
  572 static void
  573 bucket_drain(uma_zone_t zone, uma_bucket_t bucket)
  574 {
  575         void *item;
  576 
  577         if (bucket == NULL)
  578                 return;
  579 
  580         while (bucket->ub_cnt > 0)  {
  581                 bucket->ub_cnt--;
  582                 item = bucket->ub_bucket[bucket->ub_cnt];
  583 #ifdef INVARIANTS
  584                 bucket->ub_bucket[bucket->ub_cnt] = NULL;
  585                 KASSERT(item != NULL,
  586                     ("bucket_drain: botched ptr, item is NULL"));
  587 #endif
  588                 zone_free_item(zone, item, NULL, SKIP_DTOR, 0);
  589         }
  590 }
  591 
  592 /*
  593  * Drains the per cpu caches for a zone.
  594  *
  595  * NOTE: This may only be called while the zone is being turn down, and not
  596  * during normal operation.  This is necessary in order that we do not have
  597  * to migrate CPUs to drain the per-CPU caches.
  598  *
  599  * Arguments:
  600  *      zone     The zone to drain, must be unlocked.
  601  *
  602  * Returns:
  603  *      Nothing
  604  */
  605 static void
  606 cache_drain(uma_zone_t zone)
  607 {
  608         uma_cache_t cache;
  609         int cpu;
  610 
  611         /*
  612          * XXX: It is safe to not lock the per-CPU caches, because we're
  613          * tearing down the zone anyway.  I.e., there will be no further use
  614          * of the caches at this point.
  615          *
  616          * XXX: It would good to be able to assert that the zone is being
  617          * torn down to prevent improper use of cache_drain().
  618          *
  619          * XXX: We lock the zone before passing into bucket_cache_drain() as
  620          * it is used elsewhere.  Should the tear-down path be made special
  621          * there in some form?
  622          */
  623         CPU_FOREACH(cpu) {
  624                 cache = &zone->uz_cpu[cpu];
  625                 bucket_drain(zone, cache->uc_allocbucket);
  626                 bucket_drain(zone, cache->uc_freebucket);
  627                 if (cache->uc_allocbucket != NULL)
  628                         bucket_free(cache->uc_allocbucket);
  629                 if (cache->uc_freebucket != NULL)
  630                         bucket_free(cache->uc_freebucket);
  631                 cache->uc_allocbucket = cache->uc_freebucket = NULL;
  632         }
  633         ZONE_LOCK(zone);
  634         bucket_cache_drain(zone);
  635         ZONE_UNLOCK(zone);
  636 }
  637 
  638 /*
  639  * Drain the cached buckets from a zone.  Expects a locked zone on entry.
  640  */
  641 static void
  642 bucket_cache_drain(uma_zone_t zone)
  643 {
  644         uma_bucket_t bucket;
  645 
  646         /*
  647          * Drain the bucket queues and free the buckets, we just keep two per
  648          * cpu (alloc/free).
  649          */
  650         while ((bucket = LIST_FIRST(&zone->uz_full_bucket)) != NULL) {
  651                 LIST_REMOVE(bucket, ub_link);
  652                 ZONE_UNLOCK(zone);
  653                 bucket_drain(zone, bucket);
  654                 bucket_free(bucket);
  655                 ZONE_LOCK(zone);
  656         }
  657 
  658         /* Now we do the free queue.. */
  659         while ((bucket = LIST_FIRST(&zone->uz_free_bucket)) != NULL) {
  660                 LIST_REMOVE(bucket, ub_link);
  661                 bucket_free(bucket);
  662         }
  663 }
  664 
  665 /*
  666  * Frees pages from a keg back to the system.  This is done on demand from
  667  * the pageout daemon.
  668  *
  669  * Returns nothing.
  670  */
  671 static void
  672 keg_drain(uma_keg_t keg)
  673 {
  674         struct slabhead freeslabs = { 0 };
  675         uma_slab_t slab;
  676         uma_slab_t n;
  677         u_int8_t flags;
  678         u_int8_t *mem;
  679         int i;
  680 
  681         /*
  682          * We don't want to take pages from statically allocated kegs at this
  683          * time
  684          */
  685         if (keg->uk_flags & UMA_ZONE_NOFREE || keg->uk_freef == NULL)
  686                 return;
  687 
  688 #ifdef UMA_DEBUG
  689         printf("%s free items: %u\n", keg->uk_name, keg->uk_free);
  690 #endif
  691         KEG_LOCK(keg);
  692         if (keg->uk_free == 0)
  693                 goto finished;
  694 
  695         slab = LIST_FIRST(&keg->uk_free_slab);
  696         while (slab) {
  697                 n = LIST_NEXT(slab, us_link);
  698 
  699                 /* We have no where to free these to */
  700                 if (slab->us_flags & UMA_SLAB_BOOT) {
  701                         slab = n;
  702                         continue;
  703                 }
  704 
  705                 LIST_REMOVE(slab, us_link);
  706                 keg->uk_pages -= keg->uk_ppera;
  707                 keg->uk_free -= keg->uk_ipers;
  708 
  709                 if (keg->uk_flags & UMA_ZONE_HASH)
  710                         UMA_HASH_REMOVE(&keg->uk_hash, slab, slab->us_data);
  711 
  712                 SLIST_INSERT_HEAD(&freeslabs, slab, us_hlink);
  713 
  714                 slab = n;
  715         }
  716 finished:
  717         KEG_UNLOCK(keg);
  718 
  719         while ((slab = SLIST_FIRST(&freeslabs)) != NULL) {
  720                 SLIST_REMOVE(&freeslabs, slab, uma_slab, us_hlink);
  721                 if (keg->uk_fini)
  722                         for (i = 0; i < keg->uk_ipers; i++)
  723                                 keg->uk_fini(
  724                                     slab->us_data + (keg->uk_rsize * i),
  725                                     keg->uk_size);
  726                 flags = slab->us_flags;
  727                 mem = slab->us_data;
  728 
  729                 if (keg->uk_flags & UMA_ZONE_VTOSLAB) {
  730                         vm_object_t obj;
  731 
  732                         if (flags & UMA_SLAB_KMEM)
  733                                 obj = kmem_object;
  734                         else if (flags & UMA_SLAB_KERNEL)
  735                                 obj = kernel_object;
  736                         else
  737                                 obj = NULL;
  738                         for (i = 0; i < keg->uk_ppera; i++)
  739                                 vsetobj((vm_offset_t)mem + (i * PAGE_SIZE),
  740                                     obj);
  741                 }
  742                 if (keg->uk_flags & UMA_ZONE_OFFPAGE)
  743                         zone_free_item(keg->uk_slabzone, slab, NULL,
  744                             SKIP_NONE, ZFREE_STATFREE);
  745 #ifdef UMA_DEBUG
  746                 printf("%s: Returning %d bytes.\n",
  747                     keg->uk_name, UMA_SLAB_SIZE * keg->uk_ppera);
  748 #endif
  749                 keg->uk_freef(mem, UMA_SLAB_SIZE * keg->uk_ppera, flags);
  750         }
  751 }
  752 
  753 static void
  754 zone_drain_wait(uma_zone_t zone, int waitok)
  755 {
  756 
  757         /*
  758          * Set draining to interlock with zone_dtor() so we can release our
  759          * locks as we go.  Only dtor() should do a WAITOK call since it
  760          * is the only call that knows the structure will still be available
  761          * when it wakes up.
  762          */
  763         ZONE_LOCK(zone);
  764         while (zone->uz_flags & UMA_ZFLAG_DRAINING) {
  765                 if (waitok == M_NOWAIT)
  766                         goto out;
  767                 mtx_unlock(&uma_mtx);
  768                 msleep(zone, zone->uz_lock, PVM, "zonedrain", 1);
  769                 mtx_lock(&uma_mtx);
  770         }
  771         zone->uz_flags |= UMA_ZFLAG_DRAINING;
  772         bucket_cache_drain(zone);
  773         ZONE_UNLOCK(zone);
  774         /*
  775          * The DRAINING flag protects us from being freed while
  776          * we're running.  Normally the uma_mtx would protect us but we
  777          * must be able to release and acquire the right lock for each keg.
  778          */
  779         zone_foreach_keg(zone, &keg_drain);
  780         ZONE_LOCK(zone);
  781         zone->uz_flags &= ~UMA_ZFLAG_DRAINING;
  782         wakeup(zone);
  783 out:
  784         ZONE_UNLOCK(zone);
  785 }
  786 
  787 void
  788 zone_drain(uma_zone_t zone)
  789 {
  790 
  791         zone_drain_wait(zone, M_NOWAIT);
  792 }
  793 
  794 /*
  795  * Allocate a new slab for a keg.  This does not insert the slab onto a list.
  796  *
  797  * Arguments:
  798  *      wait  Shall we wait?
  799  *
  800  * Returns:
  801  *      The slab that was allocated or NULL if there is no memory and the
  802  *      caller specified M_NOWAIT.
  803  */
  804 static uma_slab_t
  805 keg_alloc_slab(uma_keg_t keg, uma_zone_t zone, int wait)
  806 {
  807         uma_slabrefcnt_t slabref;
  808         uma_alloc allocf;
  809         uma_slab_t slab;
  810         u_int8_t *mem;
  811         u_int8_t flags;
  812         int i;
  813 
  814         mtx_assert(&keg->uk_lock, MA_OWNED);
  815         slab = NULL;
  816 
  817 #ifdef UMA_DEBUG
  818         printf("slab_zalloc:  Allocating a new slab for %s\n", keg->uk_name);
  819 #endif
  820         allocf = keg->uk_allocf;
  821         KEG_UNLOCK(keg);
  822 
  823         if (keg->uk_flags & UMA_ZONE_OFFPAGE) {
  824                 slab = zone_alloc_item(keg->uk_slabzone, NULL, wait);
  825                 if (slab == NULL) {
  826                         KEG_LOCK(keg);
  827                         return NULL;
  828                 }
  829         }
  830 
  831         /*
  832          * This reproduces the old vm_zone behavior of zero filling pages the
  833          * first time they are added to a zone.
  834          *
  835          * Malloced items are zeroed in uma_zalloc.
  836          */
  837 
  838         if ((keg->uk_flags & UMA_ZONE_MALLOC) == 0)
  839                 wait |= M_ZERO;
  840         else
  841                 wait &= ~M_ZERO;
  842 
  843         /* zone is passed for legacy reasons. */
  844         mem = allocf(zone, keg->uk_ppera * UMA_SLAB_SIZE, &flags, wait);
  845         if (mem == NULL) {
  846                 if (keg->uk_flags & UMA_ZONE_OFFPAGE)
  847                         zone_free_item(keg->uk_slabzone, slab, NULL,
  848                             SKIP_NONE, ZFREE_STATFREE);
  849                 KEG_LOCK(keg);
  850                 return (NULL);
  851         }
  852 
  853         /* Point the slab into the allocated memory */
  854         if (!(keg->uk_flags & UMA_ZONE_OFFPAGE))
  855                 slab = (uma_slab_t )(mem + keg->uk_pgoff);
  856 
  857         if (keg->uk_flags & UMA_ZONE_VTOSLAB)
  858                 for (i = 0; i < keg->uk_ppera; i++)
  859                         vsetslab((vm_offset_t)mem + (i * PAGE_SIZE), slab);
  860 
  861         slab->us_keg = keg;
  862         slab->us_data = mem;
  863         slab->us_freecount = keg->uk_ipers;
  864         slab->us_firstfree = 0;
  865         slab->us_flags = flags;
  866 
  867         if (keg->uk_flags & UMA_ZONE_REFCNT) {
  868                 slabref = (uma_slabrefcnt_t)slab;
  869                 for (i = 0; i < keg->uk_ipers; i++) {
  870                         slabref->us_freelist[i].us_refcnt = 0;
  871                         slabref->us_freelist[i].us_item = i+1;
  872                 }
  873         } else {
  874                 for (i = 0; i < keg->uk_ipers; i++)
  875                         slab->us_freelist[i].us_item = i+1;
  876         }
  877 
  878         if (keg->uk_init != NULL) {
  879                 for (i = 0; i < keg->uk_ipers; i++)
  880                         if (keg->uk_init(slab->us_data + (keg->uk_rsize * i),
  881                             keg->uk_size, wait) != 0)
  882                                 break;
  883                 if (i != keg->uk_ipers) {
  884                         if (keg->uk_fini != NULL) {
  885                                 for (i--; i > -1; i--)
  886                                         keg->uk_fini(slab->us_data +
  887                                             (keg->uk_rsize * i),
  888                                             keg->uk_size);
  889                         }
  890                         if (keg->uk_flags & UMA_ZONE_VTOSLAB) {
  891                                 vm_object_t obj;
  892 
  893                                 if (flags & UMA_SLAB_KMEM)
  894                                         obj = kmem_object;
  895                                 else if (flags & UMA_SLAB_KERNEL)
  896                                         obj = kernel_object;
  897                                 else
  898                                         obj = NULL;
  899                                 for (i = 0; i < keg->uk_ppera; i++)
  900                                         vsetobj((vm_offset_t)mem +
  901                                             (i * PAGE_SIZE), obj);
  902                         }
  903                         if (keg->uk_flags & UMA_ZONE_OFFPAGE)
  904                                 zone_free_item(keg->uk_slabzone, slab,
  905                                     NULL, SKIP_NONE, ZFREE_STATFREE);
  906                         keg->uk_freef(mem, UMA_SLAB_SIZE * keg->uk_ppera,
  907                             flags);
  908                         KEG_LOCK(keg);
  909                         return (NULL);
  910                 }
  911         }
  912         KEG_LOCK(keg);
  913 
  914         if (keg->uk_flags & UMA_ZONE_HASH)
  915                 UMA_HASH_INSERT(&keg->uk_hash, slab, mem);
  916 
  917         keg->uk_pages += keg->uk_ppera;
  918         keg->uk_free += keg->uk_ipers;
  919 
  920         return (slab);
  921 }
  922 
  923 /*
  924  * This function is intended to be used early on in place of page_alloc() so
  925  * that we may use the boot time page cache to satisfy allocations before
  926  * the VM is ready.
  927  */
  928 static void *
  929 startup_alloc(uma_zone_t zone, int bytes, u_int8_t *pflag, int wait)
  930 {
  931         uma_keg_t keg;
  932         uma_slab_t tmps;
  933         int pages, check_pages;
  934 
  935         keg = zone_first_keg(zone);
  936         pages = howmany(bytes, PAGE_SIZE);
  937         check_pages = pages - 1;
  938         KASSERT(pages > 0, ("startup_alloc can't reserve 0 pages\n"));
  939 
  940         /*
  941          * Check our small startup cache to see if it has pages remaining.
  942          */
  943         mtx_lock(&uma_boot_pages_mtx);
  944 
  945         /* First check if we have enough room. */
  946         tmps = LIST_FIRST(&uma_boot_pages);
  947         while (tmps != NULL && check_pages-- > 0)
  948                 tmps = LIST_NEXT(tmps, us_link);
  949         if (tmps != NULL) {
  950                 /*
  951                  * It's ok to lose tmps references.  The last one will
  952                  * have tmps->us_data pointing to the start address of
  953                  * "pages" contiguous pages of memory.
  954                  */
  955                 while (pages-- > 0) {
  956                         tmps = LIST_FIRST(&uma_boot_pages);
  957                         LIST_REMOVE(tmps, us_link);
  958                 }
  959                 mtx_unlock(&uma_boot_pages_mtx);
  960                 *pflag = tmps->us_flags;
  961                 return (tmps->us_data);
  962         }
  963         mtx_unlock(&uma_boot_pages_mtx);
  964         if (booted == 0)
  965                 panic("UMA: Increase vm.boot_pages");
  966         /*
  967          * Now that we've booted reset these users to their real allocator.
  968          */
  969 #ifdef UMA_MD_SMALL_ALLOC
  970         keg->uk_allocf = (keg->uk_ppera > 1) ? page_alloc : uma_small_alloc;
  971 #else
  972         keg->uk_allocf = page_alloc;
  973 #endif
  974         return keg->uk_allocf(zone, bytes, pflag, wait);
  975 }
  976 
  977 /*
  978  * Allocates a number of pages from the system
  979  *
  980  * Arguments:
  981  *      bytes  The number of bytes requested
  982  *      wait  Shall we wait?
  983  *
  984  * Returns:
  985  *      A pointer to the alloced memory or possibly
  986  *      NULL if M_NOWAIT is set.
  987  */
  988 static void *
  989 page_alloc(uma_zone_t zone, int bytes, u_int8_t *pflag, int wait)
  990 {
  991         void *p;        /* Returned page */
  992 
  993         *pflag = UMA_SLAB_KMEM;
  994         p = (void *) kmem_malloc(kmem_map, bytes, wait);
  995 
  996         return (p);
  997 }
  998 
  999 /*
 1000  * Allocates a number of pages from within an object
 1001  *
 1002  * Arguments:
 1003  *      bytes  The number of bytes requested
 1004  *      wait   Shall we wait?
 1005  *
 1006  * Returns:
 1007  *      A pointer to the alloced memory or possibly
 1008  *      NULL if M_NOWAIT is set.
 1009  */
 1010 static void *
 1011 obj_alloc(uma_zone_t zone, int bytes, u_int8_t *flags, int wait)
 1012 {
 1013         vm_object_t object;
 1014         vm_offset_t retkva, zkva;
 1015         vm_page_t p;
 1016         int pages, startpages;
 1017         uma_keg_t keg;
 1018 
 1019         keg = zone_first_keg(zone);
 1020         object = keg->uk_obj;
 1021         retkva = 0;
 1022 
 1023         /*
 1024          * This looks a little weird since we're getting one page at a time.
 1025          */
 1026         VM_OBJECT_LOCK(object);
 1027         p = TAILQ_LAST(&object->memq, pglist);
 1028         pages = p != NULL ? p->pindex + 1 : 0;
 1029         startpages = pages;
 1030         zkva = keg->uk_kva + pages * PAGE_SIZE;
 1031         for (; bytes > 0; bytes -= PAGE_SIZE) {
 1032                 p = vm_page_alloc(object, pages,
 1033                     VM_ALLOC_INTERRUPT | VM_ALLOC_WIRED);
 1034                 if (p == NULL) {
 1035                         if (pages != startpages)
 1036                                 pmap_qremove(retkva, pages - startpages);
 1037                         while (pages != startpages) {
 1038                                 pages--;
 1039                                 p = TAILQ_LAST(&object->memq, pglist);
 1040                                 vm_page_lock_queues();
 1041                                 vm_page_unwire(p, 0);
 1042                                 vm_page_free(p);
 1043                                 vm_page_unlock_queues();
 1044                         }
 1045                         retkva = 0;
 1046                         goto done;
 1047                 }
 1048                 pmap_qenter(zkva, &p, 1);
 1049                 if (retkva == 0)
 1050                         retkva = zkva;
 1051                 zkva += PAGE_SIZE;
 1052                 pages += 1;
 1053         }
 1054 done:
 1055         VM_OBJECT_UNLOCK(object);
 1056         *flags = UMA_SLAB_PRIV;
 1057 
 1058         return ((void *)retkva);
 1059 }
 1060 
 1061 /*
 1062  * Frees a number of pages to the system
 1063  *
 1064  * Arguments:
 1065  *      mem   A pointer to the memory to be freed
 1066  *      size  The size of the memory being freed
 1067  *      flags The original p->us_flags field
 1068  *
 1069  * Returns:
 1070  *      Nothing
 1071  */
 1072 static void
 1073 page_free(void *mem, int size, u_int8_t flags)
 1074 {
 1075         vm_map_t map;
 1076 
 1077         if (flags & UMA_SLAB_KMEM)
 1078                 map = kmem_map;
 1079         else if (flags & UMA_SLAB_KERNEL)
 1080                 map = kernel_map;
 1081         else
 1082                 panic("UMA: page_free used with invalid flags %d", flags);
 1083 
 1084         kmem_free(map, (vm_offset_t)mem, size);
 1085 }
 1086 
 1087 /*
 1088  * Zero fill initializer
 1089  *
 1090  * Arguments/Returns follow uma_init specifications
 1091  */
 1092 static int
 1093 zero_init(void *mem, int size, int flags)
 1094 {
 1095         bzero(mem, size);
 1096         return (0);
 1097 }
 1098 
 1099 /*
 1100  * Finish creating a small uma keg.  This calculates ipers, and the keg size.
 1101  *
 1102  * Arguments
 1103  *      keg  The zone we should initialize
 1104  *
 1105  * Returns
 1106  *      Nothing
 1107  */
 1108 static void
 1109 keg_small_init(uma_keg_t keg)
 1110 {
 1111         u_int rsize;
 1112         u_int memused;
 1113         u_int wastedspace;
 1114         u_int shsize;
 1115 
 1116         KASSERT(keg != NULL, ("Keg is null in keg_small_init"));
 1117         rsize = keg->uk_size;
 1118 
 1119         if (rsize < UMA_SMALLEST_UNIT)
 1120                 rsize = UMA_SMALLEST_UNIT;
 1121         if (rsize & keg->uk_align)
 1122                 rsize = (rsize & ~keg->uk_align) + (keg->uk_align + 1);
 1123 
 1124         keg->uk_rsize = rsize;
 1125         keg->uk_ppera = 1;
 1126 
 1127         if (keg->uk_flags & UMA_ZONE_REFCNT) {
 1128                 rsize += UMA_FRITMREF_SZ;       /* linkage & refcnt */
 1129                 shsize = sizeof(struct uma_slab_refcnt);
 1130         } else {
 1131                 rsize += UMA_FRITM_SZ;  /* Account for linkage */
 1132                 shsize = sizeof(struct uma_slab);
 1133         }
 1134 
 1135         keg->uk_ipers = (UMA_SLAB_SIZE - shsize) / rsize;
 1136         KASSERT(keg->uk_ipers != 0, ("keg_small_init: ipers is 0"));
 1137         memused = keg->uk_ipers * rsize + shsize;
 1138         wastedspace = UMA_SLAB_SIZE - memused;
 1139 
 1140         /*
 1141          * We can't do OFFPAGE if we're internal or if we've been
 1142          * asked to not go to the VM for buckets.  If we do this we
 1143          * may end up going to the VM (kmem_map) for slabs which we
 1144          * do not want to do if we're UMA_ZFLAG_CACHEONLY as a
 1145          * result of UMA_ZONE_VM, which clearly forbids it.
 1146          */
 1147         if ((keg->uk_flags & UMA_ZFLAG_INTERNAL) ||
 1148             (keg->uk_flags & UMA_ZFLAG_CACHEONLY))
 1149                 return;
 1150 
 1151         if ((wastedspace >= UMA_MAX_WASTE) &&
 1152             (keg->uk_ipers < (UMA_SLAB_SIZE / keg->uk_rsize))) {
 1153                 keg->uk_ipers = UMA_SLAB_SIZE / keg->uk_rsize;
 1154                 KASSERT(keg->uk_ipers <= 255,
 1155                     ("keg_small_init: keg->uk_ipers too high!"));
 1156 #ifdef UMA_DEBUG
 1157                 printf("UMA decided we need offpage slab headers for "
 1158                     "keg: %s, calculated wastedspace = %d, "
 1159                     "maximum wasted space allowed = %d, "
 1160                     "calculated ipers = %d, "
 1161                     "new wasted space = %d\n", keg->uk_name, wastedspace,
 1162                     UMA_MAX_WASTE, keg->uk_ipers,
 1163                     UMA_SLAB_SIZE - keg->uk_ipers * keg->uk_rsize);
 1164 #endif
 1165                 keg->uk_flags |= UMA_ZONE_OFFPAGE;
 1166                 if ((keg->uk_flags & UMA_ZONE_VTOSLAB) == 0)
 1167                         keg->uk_flags |= UMA_ZONE_HASH;
 1168         }
 1169 }
 1170 
 1171 /*
 1172  * Finish creating a large (> UMA_SLAB_SIZE) uma kegs.  Just give in and do
 1173  * OFFPAGE for now.  When I can allow for more dynamic slab sizes this will be
 1174  * more complicated.
 1175  *
 1176  * Arguments
 1177  *      keg  The keg we should initialize
 1178  *
 1179  * Returns
 1180  *      Nothing
 1181  */
 1182 static void
 1183 keg_large_init(uma_keg_t keg)
 1184 {
 1185         int pages;
 1186 
 1187         KASSERT(keg != NULL, ("Keg is null in keg_large_init"));
 1188         KASSERT((keg->uk_flags & UMA_ZFLAG_CACHEONLY) == 0,
 1189             ("keg_large_init: Cannot large-init a UMA_ZFLAG_CACHEONLY keg"));
 1190 
 1191         pages = keg->uk_size / UMA_SLAB_SIZE;
 1192 
 1193         /* Account for remainder */
 1194         if ((pages * UMA_SLAB_SIZE) < keg->uk_size)
 1195                 pages++;
 1196 
 1197         keg->uk_ppera = pages;
 1198         keg->uk_ipers = 1;
 1199         keg->uk_rsize = keg->uk_size;
 1200 
 1201         /* We can't do OFFPAGE if we're internal, bail out here. */
 1202         if (keg->uk_flags & UMA_ZFLAG_INTERNAL)
 1203                 return;
 1204 
 1205         keg->uk_flags |= UMA_ZONE_OFFPAGE;
 1206         if ((keg->uk_flags & UMA_ZONE_VTOSLAB) == 0)
 1207                 keg->uk_flags |= UMA_ZONE_HASH;
 1208 }
 1209 
 1210 static void
 1211 keg_cachespread_init(uma_keg_t keg)
 1212 {
 1213         int alignsize;
 1214         int trailer;
 1215         int pages;
 1216         int rsize;
 1217 
 1218         alignsize = keg->uk_align + 1;
 1219         rsize = keg->uk_size;
 1220         /*
 1221          * We want one item to start on every align boundary in a page.  To
 1222          * do this we will span pages.  We will also extend the item by the
 1223          * size of align if it is an even multiple of align.  Otherwise, it
 1224          * would fall on the same boundary every time.
 1225          */
 1226         if (rsize & keg->uk_align)
 1227                 rsize = (rsize & ~keg->uk_align) + alignsize;
 1228         if ((rsize & alignsize) == 0)
 1229                 rsize += alignsize;
 1230         trailer = rsize - keg->uk_size;
 1231         pages = (rsize * (PAGE_SIZE / alignsize)) / PAGE_SIZE;
 1232         pages = MIN(pages, (128 * 1024) / PAGE_SIZE);
 1233         keg->uk_rsize = rsize;
 1234         keg->uk_ppera = pages;
 1235         keg->uk_ipers = ((pages * PAGE_SIZE) + trailer) / rsize;
 1236         keg->uk_flags |= UMA_ZONE_OFFPAGE | UMA_ZONE_VTOSLAB;
 1237         KASSERT(keg->uk_ipers <= uma_max_ipers,
 1238             ("keg_small_init: keg->uk_ipers too high(%d) increase max_ipers",
 1239             keg->uk_ipers));
 1240 }
 1241 
 1242 /*
 1243  * Keg header ctor.  This initializes all fields, locks, etc.  And inserts
 1244  * the keg onto the global keg list.
 1245  *
 1246  * Arguments/Returns follow uma_ctor specifications
 1247  *      udata  Actually uma_kctor_args
 1248  */
 1249 static int
 1250 keg_ctor(void *mem, int size, void *udata, int flags)
 1251 {
 1252         struct uma_kctor_args *arg = udata;
 1253         uma_keg_t keg = mem;
 1254         uma_zone_t zone;
 1255 
 1256         bzero(keg, size);
 1257         keg->uk_size = arg->size;
 1258         keg->uk_init = arg->uminit;
 1259         keg->uk_fini = arg->fini;
 1260         keg->uk_align = arg->align;
 1261         keg->uk_free = 0;
 1262         keg->uk_pages = 0;
 1263         keg->uk_flags = arg->flags;
 1264         keg->uk_allocf = page_alloc;
 1265         keg->uk_freef = page_free;
 1266         keg->uk_recurse = 0;
 1267         keg->uk_slabzone = NULL;
 1268 
 1269         /*
 1270          * The master zone is passed to us at keg-creation time.
 1271          */
 1272         zone = arg->zone;
 1273         keg->uk_name = zone->uz_name;
 1274 
 1275         if (arg->flags & UMA_ZONE_VM)
 1276                 keg->uk_flags |= UMA_ZFLAG_CACHEONLY;
 1277 
 1278         if (arg->flags & UMA_ZONE_ZINIT)
 1279                 keg->uk_init = zero_init;
 1280 
 1281         if (arg->flags & UMA_ZONE_REFCNT || arg->flags & UMA_ZONE_MALLOC)
 1282                 keg->uk_flags |= UMA_ZONE_VTOSLAB;
 1283 
 1284         /*
 1285          * The +UMA_FRITM_SZ added to uk_size is to account for the
 1286          * linkage that is added to the size in keg_small_init().  If
 1287          * we don't account for this here then we may end up in
 1288          * keg_small_init() with a calculated 'ipers' of 0.
 1289          */
 1290         if (keg->uk_flags & UMA_ZONE_REFCNT) {
 1291                 if (keg->uk_flags & UMA_ZONE_CACHESPREAD)
 1292                         keg_cachespread_init(keg);
 1293                 else if ((keg->uk_size+UMA_FRITMREF_SZ) >
 1294                     (UMA_SLAB_SIZE - sizeof(struct uma_slab_refcnt)))
 1295                         keg_large_init(keg);
 1296                 else
 1297                         keg_small_init(keg);
 1298         } else {
 1299                 if (keg->uk_flags & UMA_ZONE_CACHESPREAD)
 1300                         keg_cachespread_init(keg);
 1301                 else if ((keg->uk_size+UMA_FRITM_SZ) >
 1302                     (UMA_SLAB_SIZE - sizeof(struct uma_slab)))
 1303                         keg_large_init(keg);
 1304                 else
 1305                         keg_small_init(keg);
 1306         }
 1307 
 1308         if (keg->uk_flags & UMA_ZONE_OFFPAGE) {
 1309                 if (keg->uk_flags & UMA_ZONE_REFCNT)
 1310                         keg->uk_slabzone = slabrefzone;
 1311                 else
 1312                         keg->uk_slabzone = slabzone;
 1313         }
 1314 
 1315         /*
 1316          * If we haven't booted yet we need allocations to go through the
 1317          * startup cache until the vm is ready.
 1318          */
 1319         if (keg->uk_ppera == 1) {
 1320 #ifdef UMA_MD_SMALL_ALLOC
 1321                 keg->uk_allocf = uma_small_alloc;
 1322                 keg->uk_freef = uma_small_free;
 1323 #endif
 1324                 if (booted == 0)
 1325                         keg->uk_allocf = startup_alloc;
 1326         } else if (booted == 0 && (keg->uk_flags & UMA_ZFLAG_INTERNAL))
 1327                 keg->uk_allocf = startup_alloc;
 1328 
 1329         /*
 1330          * Initialize keg's lock (shared among zones).
 1331          */
 1332         if (arg->flags & UMA_ZONE_MTXCLASS)
 1333                 KEG_LOCK_INIT(keg, 1);
 1334         else
 1335                 KEG_LOCK_INIT(keg, 0);
 1336 
 1337         /*
 1338          * If we're putting the slab header in the actual page we need to
 1339          * figure out where in each page it goes.  This calculates a right
 1340          * justified offset into the memory on an ALIGN_PTR boundary.
 1341          */
 1342         if (!(keg->uk_flags & UMA_ZONE_OFFPAGE)) {
 1343                 u_int totsize;
 1344 
 1345                 /* Size of the slab struct and free list */
 1346                 if (keg->uk_flags & UMA_ZONE_REFCNT)
 1347                         totsize = sizeof(struct uma_slab_refcnt) +
 1348                             keg->uk_ipers * UMA_FRITMREF_SZ;
 1349                 else
 1350                         totsize = sizeof(struct uma_slab) +
 1351                             keg->uk_ipers * UMA_FRITM_SZ;
 1352 
 1353                 if (totsize & UMA_ALIGN_PTR)
 1354                         totsize = (totsize & ~UMA_ALIGN_PTR) +
 1355                             (UMA_ALIGN_PTR + 1);
 1356                 keg->uk_pgoff = (UMA_SLAB_SIZE * keg->uk_ppera) - totsize;
 1357 
 1358                 if (keg->uk_flags & UMA_ZONE_REFCNT)
 1359                         totsize = keg->uk_pgoff + sizeof(struct uma_slab_refcnt)
 1360                             + keg->uk_ipers * UMA_FRITMREF_SZ;
 1361                 else
 1362                         totsize = keg->uk_pgoff + sizeof(struct uma_slab)
 1363                             + keg->uk_ipers * UMA_FRITM_SZ;
 1364 
 1365                 /*
 1366                  * The only way the following is possible is if with our
 1367                  * UMA_ALIGN_PTR adjustments we are now bigger than
 1368                  * UMA_SLAB_SIZE.  I haven't checked whether this is
 1369                  * mathematically possible for all cases, so we make
 1370                  * sure here anyway.
 1371                  */
 1372                 if (totsize > UMA_SLAB_SIZE * keg->uk_ppera) {
 1373                         printf("zone %s ipers %d rsize %d size %d\n",
 1374                             zone->uz_name, keg->uk_ipers, keg->uk_rsize,
 1375                             keg->uk_size);
 1376                         panic("UMA slab won't fit.");
 1377                 }
 1378         }
 1379 
 1380         if (keg->uk_flags & UMA_ZONE_HASH)
 1381                 hash_alloc(&keg->uk_hash);
 1382 
 1383 #ifdef UMA_DEBUG
 1384         printf("UMA: %s(%p) size %d(%d) flags %d ipers %d ppera %d out %d free %d\n",
 1385             zone->uz_name, zone, keg->uk_size, keg->uk_rsize, keg->uk_flags,
 1386             keg->uk_ipers, keg->uk_ppera,
 1387             (keg->uk_ipers * keg->uk_pages) - keg->uk_free, keg->uk_free);
 1388 #endif
 1389 
 1390         LIST_INSERT_HEAD(&keg->uk_zones, zone, uz_link);
 1391 
 1392         mtx_lock(&uma_mtx);
 1393         LIST_INSERT_HEAD(&uma_kegs, keg, uk_link);
 1394         mtx_unlock(&uma_mtx);
 1395         return (0);
 1396 }
 1397 
 1398 /*
 1399  * Zone header ctor.  This initializes all fields, locks, etc.
 1400  *
 1401  * Arguments/Returns follow uma_ctor specifications
 1402  *      udata  Actually uma_zctor_args
 1403  */
 1404 static int
 1405 zone_ctor(void *mem, int size, void *udata, int flags)
 1406 {
 1407         struct uma_zctor_args *arg = udata;
 1408         uma_zone_t zone = mem;
 1409         uma_zone_t z;
 1410         uma_keg_t keg;
 1411 
 1412         bzero(zone, size);
 1413         zone->uz_name = arg->name;
 1414         zone->uz_ctor = arg->ctor;
 1415         zone->uz_dtor = arg->dtor;
 1416         zone->uz_slab = zone_fetch_slab;
 1417         zone->uz_init = NULL;
 1418         zone->uz_fini = NULL;
 1419         zone->uz_allocs = 0;
 1420         zone->uz_frees = 0;
 1421         zone->uz_fails = 0;
 1422         zone->uz_fills = zone->uz_count = 0;
 1423         zone->uz_flags = 0;
 1424         keg = arg->keg;
 1425 
 1426         if (arg->flags & UMA_ZONE_SECONDARY) {
 1427                 KASSERT(arg->keg != NULL, ("Secondary zone on zero'd keg"));
 1428                 zone->uz_init = arg->uminit;
 1429                 zone->uz_fini = arg->fini;
 1430                 zone->uz_lock = &keg->uk_lock;
 1431                 zone->uz_flags |= UMA_ZONE_SECONDARY;
 1432                 mtx_lock(&uma_mtx);
 1433                 ZONE_LOCK(zone);
 1434                 LIST_FOREACH(z, &keg->uk_zones, uz_link) {
 1435                         if (LIST_NEXT(z, uz_link) == NULL) {
 1436                                 LIST_INSERT_AFTER(z, zone, uz_link);
 1437                                 break;
 1438                         }
 1439                 }
 1440                 ZONE_UNLOCK(zone);
 1441                 mtx_unlock(&uma_mtx);
 1442         } else if (keg == NULL) {
 1443                 if ((keg = uma_kcreate(zone, arg->size, arg->uminit, arg->fini,
 1444                     arg->align, arg->flags)) == NULL)
 1445                         return (ENOMEM);
 1446         } else {
 1447                 struct uma_kctor_args karg;
 1448                 int error;
 1449 
 1450                 /* We should only be here from uma_startup() */
 1451                 karg.size = arg->size;
 1452                 karg.uminit = arg->uminit;
 1453                 karg.fini = arg->fini;
 1454                 karg.align = arg->align;
 1455                 karg.flags = arg->flags;
 1456                 karg.zone = zone;
 1457                 error = keg_ctor(arg->keg, sizeof(struct uma_keg), &karg,
 1458                     flags);
 1459                 if (error)
 1460                         return (error);
 1461         }
 1462         /*
 1463          * Link in the first keg.
 1464          */
 1465         zone->uz_klink.kl_keg = keg;
 1466         LIST_INSERT_HEAD(&zone->uz_kegs, &zone->uz_klink, kl_link);
 1467         zone->uz_lock = &keg->uk_lock;
 1468         zone->uz_size = keg->uk_size;
 1469         zone->uz_flags |= (keg->uk_flags &
 1470             (UMA_ZONE_INHERIT | UMA_ZFLAG_INHERIT));
 1471 
 1472         /*
 1473          * Some internal zones don't have room allocated for the per cpu
 1474          * caches.  If we're internal, bail out here.
 1475          */
 1476         if (keg->uk_flags & UMA_ZFLAG_INTERNAL) {
 1477                 KASSERT((zone->uz_flags & UMA_ZONE_SECONDARY) == 0,
 1478                     ("Secondary zone requested UMA_ZFLAG_INTERNAL"));
 1479                 return (0);
 1480         }
 1481 
 1482         if (keg->uk_flags & UMA_ZONE_MAXBUCKET)
 1483                 zone->uz_count = BUCKET_MAX;
 1484         else if (keg->uk_ipers <= BUCKET_MAX)
 1485                 zone->uz_count = keg->uk_ipers;
 1486         else
 1487                 zone->uz_count = BUCKET_MAX;
 1488         return (0);
 1489 }
 1490 
 1491 /*
 1492  * Keg header dtor.  This frees all data, destroys locks, frees the hash
 1493  * table and removes the keg from the global list.
 1494  *
 1495  * Arguments/Returns follow uma_dtor specifications
 1496  *      udata  unused
 1497  */
 1498 static void
 1499 keg_dtor(void *arg, int size, void *udata)
 1500 {
 1501         uma_keg_t keg;
 1502 
 1503         keg = (uma_keg_t)arg;
 1504         KEG_LOCK(keg);
 1505         if (keg->uk_free != 0) {
 1506                 printf("Freed UMA keg was not empty (%d items). "
 1507                     " Lost %d pages of memory.\n",
 1508                     keg->uk_free, keg->uk_pages);
 1509         }
 1510         KEG_UNLOCK(keg);
 1511 
 1512         hash_free(&keg->uk_hash);
 1513 
 1514         KEG_LOCK_FINI(keg);
 1515 }
 1516 
 1517 /*
 1518  * Zone header dtor.
 1519  *
 1520  * Arguments/Returns follow uma_dtor specifications
 1521  *      udata  unused
 1522  */
 1523 static void
 1524 zone_dtor(void *arg, int size, void *udata)
 1525 {
 1526         uma_klink_t klink;
 1527         uma_zone_t zone;
 1528         uma_keg_t keg;
 1529 
 1530         zone = (uma_zone_t)arg;
 1531         keg = zone_first_keg(zone);
 1532 
 1533         if (!(zone->uz_flags & UMA_ZFLAG_INTERNAL))
 1534                 cache_drain(zone);
 1535 
 1536         mtx_lock(&uma_mtx);
 1537         LIST_REMOVE(zone, uz_link);
 1538         mtx_unlock(&uma_mtx);
 1539         /*
 1540          * XXX there are some races here where
 1541          * the zone can be drained but zone lock
 1542          * released and then refilled before we
 1543          * remove it... we dont care for now
 1544          */
 1545         zone_drain_wait(zone, M_WAITOK);
 1546         /*
 1547          * Unlink all of our kegs.
 1548          */
 1549         while ((klink = LIST_FIRST(&zone->uz_kegs)) != NULL) {
 1550                 klink->kl_keg = NULL;
 1551                 LIST_REMOVE(klink, kl_link);
 1552                 if (klink == &zone->uz_klink)
 1553                         continue;
 1554                 free(klink, M_TEMP);
 1555         }
 1556         /*
 1557          * We only destroy kegs from non secondary zones.
 1558          */
 1559         if ((zone->uz_flags & UMA_ZONE_SECONDARY) == 0)  {
 1560                 mtx_lock(&uma_mtx);
 1561                 LIST_REMOVE(keg, uk_link);
 1562                 mtx_unlock(&uma_mtx);
 1563                 zone_free_item(kegs, keg, NULL, SKIP_NONE,
 1564                     ZFREE_STATFREE);
 1565         }
 1566 }
 1567 
 1568 /*
 1569  * Traverses every zone in the system and calls a callback
 1570  *
 1571  * Arguments:
 1572  *      zfunc  A pointer to a function which accepts a zone
 1573  *              as an argument.
 1574  *
 1575  * Returns:
 1576  *      Nothing
 1577  */
 1578 static void
 1579 zone_foreach(void (*zfunc)(uma_zone_t))
 1580 {
 1581         uma_keg_t keg;
 1582         uma_zone_t zone;
 1583 
 1584         mtx_lock(&uma_mtx);
 1585         LIST_FOREACH(keg, &uma_kegs, uk_link) {
 1586                 LIST_FOREACH(zone, &keg->uk_zones, uz_link)
 1587                         zfunc(zone);
 1588         }
 1589         mtx_unlock(&uma_mtx);
 1590 }
 1591 
 1592 /* Public functions */
 1593 /* See uma.h */
 1594 void
 1595 uma_startup(void *bootmem, int boot_pages)
 1596 {
 1597         struct uma_zctor_args args;
 1598         uma_slab_t slab;
 1599         u_int slabsize;
 1600         u_int objsize, totsize, wsize;
 1601         int i;
 1602 
 1603 #ifdef UMA_DEBUG
 1604         printf("Creating uma keg headers zone and keg.\n");
 1605 #endif
 1606         mtx_init(&uma_mtx, "UMA lock", NULL, MTX_DEF);
 1607 
 1608         /*
 1609          * Figure out the maximum number of items-per-slab we'll have if
 1610          * we're using the OFFPAGE slab header to track free items, given
 1611          * all possible object sizes and the maximum desired wastage
 1612          * (UMA_MAX_WASTE).
 1613          *
 1614          * We iterate until we find an object size for
 1615          * which the calculated wastage in keg_small_init() will be
 1616          * enough to warrant OFFPAGE.  Since wastedspace versus objsize
 1617          * is an overall increasing see-saw function, we find the smallest
 1618          * objsize such that the wastage is always acceptable for objects
 1619          * with that objsize or smaller.  Since a smaller objsize always
 1620          * generates a larger possible uma_max_ipers, we use this computed
 1621          * objsize to calculate the largest ipers possible.  Since the
 1622          * ipers calculated for OFFPAGE slab headers is always larger than
 1623          * the ipers initially calculated in keg_small_init(), we use
 1624          * the former's equation (UMA_SLAB_SIZE / keg->uk_rsize) to
 1625          * obtain the maximum ipers possible for offpage slab headers.
 1626          *
 1627          * It should be noted that ipers versus objsize is an inversly
 1628          * proportional function which drops off rather quickly so as
 1629          * long as our UMA_MAX_WASTE is such that the objsize we calculate
 1630          * falls into the portion of the inverse relation AFTER the steep
 1631          * falloff, then uma_max_ipers shouldn't be too high (~10 on i386).
 1632          *
 1633          * Note that we have 8-bits (1 byte) to use as a freelist index
 1634          * inside the actual slab header itself and this is enough to
 1635          * accomodate us.  In the worst case, a UMA_SMALLEST_UNIT sized
 1636          * object with offpage slab header would have ipers =
 1637          * UMA_SLAB_SIZE / UMA_SMALLEST_UNIT (currently = 256), which is
 1638          * 1 greater than what our byte-integer freelist index can
 1639          * accomodate, but we know that this situation never occurs as
 1640          * for UMA_SMALLEST_UNIT-sized objects, we will never calculate
 1641          * that we need to go to offpage slab headers.  Or, if we do,
 1642          * then we trap that condition below and panic in the INVARIANTS case.
 1643          */
 1644         wsize = UMA_SLAB_SIZE - sizeof(struct uma_slab) - UMA_MAX_WASTE;
 1645         totsize = wsize;
 1646         objsize = UMA_SMALLEST_UNIT;
 1647         while (totsize >= wsize) {
 1648                 totsize = (UMA_SLAB_SIZE - sizeof(struct uma_slab)) /
 1649                     (objsize + UMA_FRITM_SZ);
 1650                 totsize *= (UMA_FRITM_SZ + objsize);
 1651                 objsize++;
 1652         }
 1653         if (objsize > UMA_SMALLEST_UNIT)
 1654                 objsize--;
 1655         uma_max_ipers = MAX(UMA_SLAB_SIZE / objsize, 64);
 1656 
 1657         wsize = UMA_SLAB_SIZE - sizeof(struct uma_slab_refcnt) - UMA_MAX_WASTE;
 1658         totsize = wsize;
 1659         objsize = UMA_SMALLEST_UNIT;
 1660         while (totsize >= wsize) {
 1661                 totsize = (UMA_SLAB_SIZE - sizeof(struct uma_slab_refcnt)) /
 1662                     (objsize + UMA_FRITMREF_SZ);
 1663                 totsize *= (UMA_FRITMREF_SZ + objsize);
 1664                 objsize++;
 1665         }
 1666         if (objsize > UMA_SMALLEST_UNIT)
 1667                 objsize--;
 1668         uma_max_ipers_ref = MAX(UMA_SLAB_SIZE / objsize, 64);
 1669 
 1670         KASSERT((uma_max_ipers_ref <= 255) && (uma_max_ipers <= 255),
 1671             ("uma_startup: calculated uma_max_ipers values too large!"));
 1672 
 1673 #ifdef UMA_DEBUG
 1674         printf("Calculated uma_max_ipers (for OFFPAGE) is %d\n", uma_max_ipers);
 1675         printf("Calculated uma_max_ipers_slab (for OFFPAGE) is %d\n",
 1676             uma_max_ipers_ref);
 1677 #endif
 1678 
 1679         /* "manually" create the initial zone */
 1680         args.name = "UMA Kegs";
 1681         args.size = sizeof(struct uma_keg);
 1682         args.ctor = keg_ctor;
 1683         args.dtor = keg_dtor;
 1684         args.uminit = zero_init;
 1685         args.fini = NULL;
 1686         args.keg = &masterkeg;
 1687         args.align = 32 - 1;
 1688         args.flags = UMA_ZFLAG_INTERNAL;
 1689         /* The initial zone has no Per cpu queues so it's smaller */
 1690         zone_ctor(kegs, sizeof(struct uma_zone), &args, M_WAITOK);
 1691 
 1692 #ifdef UMA_DEBUG
 1693         printf("Filling boot free list.\n");
 1694 #endif
 1695         for (i = 0; i < boot_pages; i++) {
 1696                 slab = (uma_slab_t)((u_int8_t *)bootmem + (i * UMA_SLAB_SIZE));
 1697                 slab->us_data = (u_int8_t *)slab;
 1698                 slab->us_flags = UMA_SLAB_BOOT;
 1699                 LIST_INSERT_HEAD(&uma_boot_pages, slab, us_link);
 1700         }
 1701         mtx_init(&uma_boot_pages_mtx, "UMA boot pages", NULL, MTX_DEF);
 1702 
 1703 #ifdef UMA_DEBUG
 1704         printf("Creating uma zone headers zone and keg.\n");
 1705 #endif
 1706         args.name = "UMA Zones";
 1707         args.size = sizeof(struct uma_zone) +
 1708             (sizeof(struct uma_cache) * (mp_maxid + 1));
 1709         args.ctor = zone_ctor;
 1710         args.dtor = zone_dtor;
 1711         args.uminit = zero_init;
 1712         args.fini = NULL;
 1713         args.keg = NULL;
 1714         args.align = 32 - 1;
 1715         args.flags = UMA_ZFLAG_INTERNAL;
 1716         /* The initial zone has no Per cpu queues so it's smaller */
 1717         zone_ctor(zones, sizeof(struct uma_zone), &args, M_WAITOK);
 1718 
 1719 #ifdef UMA_DEBUG
 1720         printf("Initializing pcpu cache locks.\n");
 1721 #endif
 1722 #ifdef UMA_DEBUG
 1723         printf("Creating slab and hash zones.\n");
 1724 #endif
 1725 
 1726         /*
 1727          * This is the max number of free list items we'll have with
 1728          * offpage slabs.
 1729          */
 1730         slabsize = uma_max_ipers * UMA_FRITM_SZ;
 1731         slabsize += sizeof(struct uma_slab);
 1732 
 1733         /* Now make a zone for slab headers */
 1734         slabzone = uma_zcreate("UMA Slabs",
 1735                                 slabsize,
 1736                                 NULL, NULL, NULL, NULL,
 1737                                 UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
 1738 
 1739         /*
 1740          * We also create a zone for the bigger slabs with reference
 1741          * counts in them, to accomodate UMA_ZONE_REFCNT zones.
 1742          */
 1743         slabsize = uma_max_ipers_ref * UMA_FRITMREF_SZ;
 1744         slabsize += sizeof(struct uma_slab_refcnt);
 1745         slabrefzone = uma_zcreate("UMA RCntSlabs",
 1746                                   slabsize,
 1747                                   NULL, NULL, NULL, NULL,
 1748                                   UMA_ALIGN_PTR,
 1749                                   UMA_ZFLAG_INTERNAL);
 1750 
 1751         hashzone = uma_zcreate("UMA Hash",
 1752             sizeof(struct slabhead *) * UMA_HASH_SIZE_INIT,
 1753             NULL, NULL, NULL, NULL,
 1754             UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
 1755 
 1756         bucket_init();
 1757 
 1758 #if defined(UMA_MD_SMALL_ALLOC) && !defined(UMA_MD_SMALL_ALLOC_NEEDS_VM)
 1759         booted = 1;
 1760 #endif
 1761 
 1762 #ifdef UMA_DEBUG
 1763         printf("UMA startup complete.\n");
 1764 #endif
 1765 }
 1766 
 1767 /* see uma.h */
 1768 void
 1769 uma_startup2(void)
 1770 {
 1771         booted = 1;
 1772         bucket_enable();
 1773 #ifdef UMA_DEBUG
 1774         printf("UMA startup2 complete.\n");
 1775 #endif
 1776 }
 1777 
 1778 /*
 1779  * Initialize our callout handle
 1780  *
 1781  */
 1782 
 1783 static void
 1784 uma_startup3(void)
 1785 {
 1786 #ifdef UMA_DEBUG
 1787         printf("Starting callout.\n");
 1788 #endif
 1789         callout_init(&uma_callout, CALLOUT_MPSAFE);
 1790         callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
 1791 #ifdef UMA_DEBUG
 1792         printf("UMA startup3 complete.\n");
 1793 #endif
 1794 }
 1795 
 1796 static uma_keg_t
 1797 uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit, uma_fini fini,
 1798                 int align, u_int32_t flags)
 1799 {
 1800         struct uma_kctor_args args;
 1801 
 1802         args.size = size;
 1803         args.uminit = uminit;
 1804         args.fini = fini;
 1805         args.align = (align == UMA_ALIGN_CACHE) ? uma_align_cache : align;
 1806         args.flags = flags;
 1807         args.zone = zone;
 1808         return (zone_alloc_item(kegs, &args, M_WAITOK));
 1809 }
 1810 
 1811 /* See uma.h */
 1812 void
 1813 uma_set_align(int align)
 1814 {
 1815 
 1816         if (align != UMA_ALIGN_CACHE)
 1817                 uma_align_cache = align;
 1818 }
 1819 
 1820 /* See uma.h */
 1821 uma_zone_t
 1822 uma_zcreate(char *name, size_t size, uma_ctor ctor, uma_dtor dtor,
 1823                 uma_init uminit, uma_fini fini, int align, u_int32_t flags)
 1824 
 1825 {
 1826         struct uma_zctor_args args;
 1827 
 1828         /* This stuff is essential for the zone ctor */
 1829         args.name = name;
 1830         args.size = size;
 1831         args.ctor = ctor;
 1832         args.dtor = dtor;
 1833         args.uminit = uminit;
 1834         args.fini = fini;
 1835         args.align = align;
 1836         args.flags = flags;
 1837         args.keg = NULL;
 1838 
 1839         return (zone_alloc_item(zones, &args, M_WAITOK));
 1840 }
 1841 
 1842 /* See uma.h */
 1843 uma_zone_t
 1844 uma_zsecond_create(char *name, uma_ctor ctor, uma_dtor dtor,
 1845                     uma_init zinit, uma_fini zfini, uma_zone_t master)
 1846 {
 1847         struct uma_zctor_args args;
 1848         uma_keg_t keg;
 1849 
 1850         keg = zone_first_keg(master);
 1851         args.name = name;
 1852         args.size = keg->uk_size;
 1853         args.ctor = ctor;
 1854         args.dtor = dtor;
 1855         args.uminit = zinit;
 1856         args.fini = zfini;
 1857         args.align = keg->uk_align;
 1858         args.flags = keg->uk_flags | UMA_ZONE_SECONDARY;
 1859         args.keg = keg;
 1860 
 1861         /* XXX Attaches only one keg of potentially many. */
 1862         return (zone_alloc_item(zones, &args, M_WAITOK));
 1863 }
 1864 
 1865 static void
 1866 zone_lock_pair(uma_zone_t a, uma_zone_t b)
 1867 {
 1868         if (a < b) {
 1869                 ZONE_LOCK(a);
 1870                 mtx_lock_flags(b->uz_lock, MTX_DUPOK);
 1871         } else {
 1872                 ZONE_LOCK(b);
 1873                 mtx_lock_flags(a->uz_lock, MTX_DUPOK);
 1874         }
 1875 }
 1876 
 1877 static void
 1878 zone_unlock_pair(uma_zone_t a, uma_zone_t b)
 1879 {
 1880 
 1881         ZONE_UNLOCK(a);
 1882         ZONE_UNLOCK(b);
 1883 }
 1884 
 1885 int
 1886 uma_zsecond_add(uma_zone_t zone, uma_zone_t master)
 1887 {
 1888         uma_klink_t klink;
 1889         uma_klink_t kl;
 1890         int error;
 1891 
 1892         error = 0;
 1893         klink = malloc(sizeof(*klink), M_TEMP, M_WAITOK | M_ZERO);
 1894 
 1895         zone_lock_pair(zone, master);
 1896         /*
 1897          * zone must use vtoslab() to resolve objects and must already be
 1898          * a secondary.
 1899          */
 1900         if ((zone->uz_flags & (UMA_ZONE_VTOSLAB | UMA_ZONE_SECONDARY))
 1901             != (UMA_ZONE_VTOSLAB | UMA_ZONE_SECONDARY)) {
 1902                 error = EINVAL;
 1903                 goto out;
 1904         }
 1905         /*
 1906          * The new master must also use vtoslab().
 1907          */
 1908         if ((zone->uz_flags & UMA_ZONE_VTOSLAB) != UMA_ZONE_VTOSLAB) {
 1909                 error = EINVAL;
 1910                 goto out;
 1911         }
 1912         /*
 1913          * Both must either be refcnt, or not be refcnt.
 1914          */
 1915         if ((zone->uz_flags & UMA_ZONE_REFCNT) !=
 1916             (master->uz_flags & UMA_ZONE_REFCNT)) {
 1917                 error = EINVAL;
 1918                 goto out;
 1919         }
 1920         /*
 1921          * The underlying object must be the same size.  rsize
 1922          * may be different.
 1923          */
 1924         if (master->uz_size != zone->uz_size) {
 1925                 error = E2BIG;
 1926                 goto out;
 1927         }
 1928         /*
 1929          * Put it at the end of the list.
 1930          */
 1931         klink->kl_keg = zone_first_keg(master);
 1932         LIST_FOREACH(kl, &zone->uz_kegs, kl_link) {
 1933                 if (LIST_NEXT(kl, kl_link) == NULL) {
 1934                         LIST_INSERT_AFTER(kl, klink, kl_link);
 1935                         break;
 1936                 }
 1937         }
 1938         klink = NULL;
 1939         zone->uz_flags |= UMA_ZFLAG_MULTI;
 1940         zone->uz_slab = zone_fetch_slab_multi;
 1941 
 1942 out:
 1943         zone_unlock_pair(zone, master);
 1944         if (klink != NULL)
 1945                 free(klink, M_TEMP);
 1946 
 1947         return (error);
 1948 }
 1949 
 1950 
 1951 /* See uma.h */
 1952 void
 1953 uma_zdestroy(uma_zone_t zone)
 1954 {
 1955 
 1956         zone_free_item(zones, zone, NULL, SKIP_NONE, ZFREE_STATFREE);
 1957 }
 1958 
 1959 /* See uma.h */
 1960 void *
 1961 uma_zalloc_arg(uma_zone_t zone, void *udata, int flags)
 1962 {
 1963         void *item;
 1964         uma_cache_t cache;
 1965         uma_bucket_t bucket;
 1966         int cpu;
 1967 
 1968         /* This is the fast path allocation */
 1969 #ifdef UMA_DEBUG_ALLOC_1
 1970         printf("Allocating one item from %s(%p)\n", zone->uz_name, zone);
 1971 #endif
 1972         CTR3(KTR_UMA, "uma_zalloc_arg thread %x zone %s flags %d", curthread,
 1973             zone->uz_name, flags);
 1974 
 1975         if (flags & M_WAITOK) {
 1976                 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
 1977                     "uma_zalloc_arg: zone \"%s\"", zone->uz_name);
 1978         }
 1979 
 1980         /*
 1981          * If possible, allocate from the per-CPU cache.  There are two
 1982          * requirements for safe access to the per-CPU cache: (1) the thread
 1983          * accessing the cache must not be preempted or yield during access,
 1984          * and (2) the thread must not migrate CPUs without switching which
 1985          * cache it accesses.  We rely on a critical section to prevent
 1986          * preemption and migration.  We release the critical section in
 1987          * order to acquire the zone mutex if we are unable to allocate from
 1988          * the current cache; when we re-acquire the critical section, we
 1989          * must detect and handle migration if it has occurred.
 1990          */
 1991 zalloc_restart:
 1992         critical_enter();
 1993         cpu = curcpu;
 1994         cache = &zone->uz_cpu[cpu];
 1995 
 1996 zalloc_start:
 1997         bucket = cache->uc_allocbucket;
 1998 
 1999         if (bucket) {
 2000                 if (bucket->ub_cnt > 0) {
 2001                         bucket->ub_cnt--;
 2002                         item = bucket->ub_bucket[bucket->ub_cnt];
 2003 #ifdef INVARIANTS
 2004                         bucket->ub_bucket[bucket->ub_cnt] = NULL;
 2005 #endif
 2006                         KASSERT(item != NULL,
 2007                             ("uma_zalloc: Bucket pointer mangled."));
 2008                         cache->uc_allocs++;
 2009                         critical_exit();
 2010 #ifdef INVARIANTS
 2011                         ZONE_LOCK(zone);
 2012                         uma_dbg_alloc(zone, NULL, item);
 2013                         ZONE_UNLOCK(zone);
 2014 #endif
 2015                         if (zone->uz_ctor != NULL) {
 2016                                 if (zone->uz_ctor(item, zone->uz_size,
 2017                                     udata, flags) != 0) {
 2018                                         zone_free_item(zone, item, udata,
 2019                                             SKIP_DTOR, ZFREE_STATFAIL |
 2020                                             ZFREE_STATFREE);
 2021                                         return (NULL);
 2022                                 }
 2023                         }
 2024                         if (flags & M_ZERO)
 2025                                 bzero(item, zone->uz_size);
 2026                         return (item);
 2027                 } else if (cache->uc_freebucket) {
 2028                         /*
 2029                          * We have run out of items in our allocbucket.
 2030                          * See if we can switch with our free bucket.
 2031                          */
 2032                         if (cache->uc_freebucket->ub_cnt > 0) {
 2033 #ifdef UMA_DEBUG_ALLOC
 2034                                 printf("uma_zalloc: Swapping empty with"
 2035                                     " alloc.\n");
 2036 #endif
 2037                                 bucket = cache->uc_freebucket;
 2038                                 cache->uc_freebucket = cache->uc_allocbucket;
 2039                                 cache->uc_allocbucket = bucket;
 2040 
 2041                                 goto zalloc_start;
 2042                         }
 2043                 }
 2044         }
 2045         /*
 2046          * Attempt to retrieve the item from the per-CPU cache has failed, so
 2047          * we must go back to the zone.  This requires the zone lock, so we
 2048          * must drop the critical section, then re-acquire it when we go back
 2049          * to the cache.  Since the critical section is released, we may be
 2050          * preempted or migrate.  As such, make sure not to maintain any
 2051          * thread-local state specific to the cache from prior to releasing
 2052          * the critical section.
 2053          */
 2054         critical_exit();
 2055         ZONE_LOCK(zone);
 2056         critical_enter();
 2057         cpu = curcpu;
 2058         cache = &zone->uz_cpu[cpu];
 2059         bucket = cache->uc_allocbucket;
 2060         if (bucket != NULL) {
 2061                 if (bucket->ub_cnt > 0) {
 2062                         ZONE_UNLOCK(zone);
 2063                         goto zalloc_start;
 2064                 }
 2065                 bucket = cache->uc_freebucket;
 2066                 if (bucket != NULL && bucket->ub_cnt > 0) {
 2067                         ZONE_UNLOCK(zone);
 2068                         goto zalloc_start;
 2069                 }
 2070         }
 2071 
 2072         /* Since we have locked the zone we may as well send back our stats */
 2073         zone->uz_allocs += cache->uc_allocs;
 2074         cache->uc_allocs = 0;
 2075         zone->uz_frees += cache->uc_frees;
 2076         cache->uc_frees = 0;
 2077 
 2078         /* Our old one is now a free bucket */
 2079         if (cache->uc_allocbucket) {
 2080                 KASSERT(cache->uc_allocbucket->ub_cnt == 0,
 2081                     ("uma_zalloc_arg: Freeing a non free bucket."));
 2082                 LIST_INSERT_HEAD(&zone->uz_free_bucket,
 2083                     cache->uc_allocbucket, ub_link);
 2084                 cache->uc_allocbucket = NULL;
 2085         }
 2086 
 2087         /* Check the free list for a new alloc bucket */
 2088         if ((bucket = LIST_FIRST(&zone->uz_full_bucket)) != NULL) {
 2089                 KASSERT(bucket->ub_cnt != 0,
 2090                     ("uma_zalloc_arg: Returning an empty bucket."));
 2091 
 2092                 LIST_REMOVE(bucket, ub_link);
 2093                 cache->uc_allocbucket = bucket;
 2094                 ZONE_UNLOCK(zone);
 2095                 goto zalloc_start;
 2096         }
 2097         /* We are no longer associated with this CPU. */
 2098         critical_exit();
 2099 
 2100         /* Bump up our uz_count so we get here less */
 2101         if (zone->uz_count < BUCKET_MAX)
 2102                 zone->uz_count++;
 2103 
 2104         /*
 2105          * Now lets just fill a bucket and put it on the free list.  If that
 2106          * works we'll restart the allocation from the begining.
 2107          */
 2108         if (zone_alloc_bucket(zone, flags)) {
 2109                 ZONE_UNLOCK(zone);
 2110                 goto zalloc_restart;
 2111         }
 2112         ZONE_UNLOCK(zone);
 2113         /*
 2114          * We may not be able to get a bucket so return an actual item.
 2115          */
 2116 #ifdef UMA_DEBUG
 2117         printf("uma_zalloc_arg: Bucketzone returned NULL\n");
 2118 #endif
 2119 
 2120         item = zone_alloc_item(zone, udata, flags);
 2121         return (item);
 2122 }
 2123 
 2124 static uma_slab_t
 2125 keg_fetch_slab(uma_keg_t keg, uma_zone_t zone, int flags)
 2126 {
 2127         uma_slab_t slab;
 2128 
 2129         mtx_assert(&keg->uk_lock, MA_OWNED);
 2130         slab = NULL;
 2131 
 2132         for (;;) {
 2133                 /*
 2134                  * Find a slab with some space.  Prefer slabs that are partially
 2135                  * used over those that are totally full.  This helps to reduce
 2136                  * fragmentation.
 2137                  */
 2138                 if (keg->uk_free != 0) {
 2139                         if (!LIST_EMPTY(&keg->uk_part_slab)) {
 2140                                 slab = LIST_FIRST(&keg->uk_part_slab);
 2141                         } else {
 2142                                 slab = LIST_FIRST(&keg->uk_free_slab);
 2143                                 LIST_REMOVE(slab, us_link);
 2144                                 LIST_INSERT_HEAD(&keg->uk_part_slab, slab,
 2145                                     us_link);
 2146                         }
 2147                         MPASS(slab->us_keg == keg);
 2148                         return (slab);
 2149                 }
 2150 
 2151                 /*
 2152                  * M_NOVM means don't ask at all!
 2153                  */
 2154                 if (flags & M_NOVM)
 2155                         break;
 2156 
 2157                 if (keg->uk_maxpages && keg->uk_pages >= keg->uk_maxpages) {
 2158                         keg->uk_flags |= UMA_ZFLAG_FULL;
 2159                         /*
 2160                          * If this is not a multi-zone, set the FULL bit.
 2161                          * Otherwise slab_multi() takes care of it.
 2162                          */
 2163                         if ((zone->uz_flags & UMA_ZFLAG_MULTI) == 0)
 2164                                 zone->uz_flags |= UMA_ZFLAG_FULL;
 2165                         if (flags & M_NOWAIT)
 2166                                 break;
 2167                         msleep(keg, &keg->uk_lock, PVM, "keglimit", 0);
 2168                         continue;
 2169                 }
 2170                 keg->uk_recurse++;
 2171                 slab = keg_alloc_slab(keg, zone, flags);
 2172                 keg->uk_recurse--;
 2173                 /*
 2174                  * If we got a slab here it's safe to mark it partially used
 2175                  * and return.  We assume that the caller is going to remove
 2176                  * at least one item.
 2177                  */
 2178                 if (slab) {
 2179                         MPASS(slab->us_keg == keg);
 2180                         LIST_INSERT_HEAD(&keg->uk_part_slab, slab, us_link);
 2181                         return (slab);
 2182                 }
 2183                 /*
 2184                  * We might not have been able to get a slab but another cpu
 2185                  * could have while we were unlocked.  Check again before we
 2186                  * fail.
 2187                  */
 2188                 flags |= M_NOVM;
 2189         }
 2190         return (slab);
 2191 }
 2192 
 2193 static inline void
 2194 zone_relock(uma_zone_t zone, uma_keg_t keg)
 2195 {
 2196         if (zone->uz_lock != &keg->uk_lock) {
 2197                 KEG_UNLOCK(keg);
 2198                 ZONE_LOCK(zone);
 2199         }
 2200 }
 2201 
 2202 static inline void
 2203 keg_relock(uma_keg_t keg, uma_zone_t zone)
 2204 {
 2205         if (zone->uz_lock != &keg->uk_lock) {
 2206                 ZONE_UNLOCK(zone);
 2207                 KEG_LOCK(keg);
 2208         }
 2209 }
 2210 
 2211 static uma_slab_t
 2212 zone_fetch_slab(uma_zone_t zone, uma_keg_t keg, int flags)
 2213 {
 2214         uma_slab_t slab;
 2215 
 2216         if (keg == NULL)
 2217                 keg = zone_first_keg(zone);
 2218         /*
 2219          * This is to prevent us from recursively trying to allocate
 2220          * buckets.  The problem is that if an allocation forces us to
 2221          * grab a new bucket we will call page_alloc, which will go off
 2222          * and cause the vm to allocate vm_map_entries.  If we need new
 2223          * buckets there too we will recurse in kmem_alloc and bad
 2224          * things happen.  So instead we return a NULL bucket, and make
 2225          * the code that allocates buckets smart enough to deal with it
 2226          */
 2227         if (keg->uk_flags & UMA_ZFLAG_BUCKET && keg->uk_recurse != 0)
 2228                 return (NULL);
 2229 
 2230         for (;;) {
 2231                 slab = keg_fetch_slab(keg, zone, flags);
 2232                 if (slab)
 2233                         return (slab);
 2234                 if (flags & (M_NOWAIT | M_NOVM))
 2235                         break;
 2236         }
 2237         return (NULL);
 2238 }
 2239 
 2240 /*
 2241  * uma_zone_fetch_slab_multi:  Fetches a slab from one available keg.  Returns
 2242  * with the keg locked.  Caller must call zone_relock() afterwards if the
 2243  * zone lock is required.  On NULL the zone lock is held.
 2244  *
 2245  * The last pointer is used to seed the search.  It is not required.
 2246  */
 2247 static uma_slab_t
 2248 zone_fetch_slab_multi(uma_zone_t zone, uma_keg_t last, int rflags)
 2249 {
 2250         uma_klink_t klink;
 2251         uma_slab_t slab;
 2252         uma_keg_t keg;
 2253         int flags;
 2254         int empty;
 2255         int full;
 2256 
 2257         /*
 2258          * Don't wait on the first pass.  This will skip limit tests
 2259          * as well.  We don't want to block if we can find a provider
 2260          * without blocking.
 2261          */
 2262         flags = (rflags & ~M_WAITOK) | M_NOWAIT;
 2263         /*
 2264          * Use the last slab allocated as a hint for where to start
 2265          * the search.
 2266          */
 2267         if (last) {
 2268                 slab = keg_fetch_slab(last, zone, flags);
 2269                 if (slab)
 2270                         return (slab);
 2271                 zone_relock(zone, last);
 2272                 last = NULL;
 2273         }
 2274         /*
 2275          * Loop until we have a slab incase of transient failures
 2276          * while M_WAITOK is specified.  I'm not sure this is 100%
 2277          * required but we've done it for so long now.
 2278          */
 2279         for (;;) {
 2280                 empty = 0;
 2281                 full = 0;
 2282                 /*
 2283                  * Search the available kegs for slabs.  Be careful to hold the
 2284                  * correct lock while calling into the keg layer.
 2285                  */
 2286                 LIST_FOREACH(klink, &zone->uz_kegs, kl_link) {
 2287                         keg = klink->kl_keg;
 2288                         keg_relock(keg, zone);
 2289                         if ((keg->uk_flags & UMA_ZFLAG_FULL) == 0) {
 2290                                 slab = keg_fetch_slab(keg, zone, flags);
 2291                                 if (slab)
 2292                                         return (slab);
 2293                         }
 2294                         if (keg->uk_flags & UMA_ZFLAG_FULL)
 2295                                 full++;
 2296                         else
 2297                                 empty++;
 2298                         zone_relock(zone, keg);
 2299                 }
 2300                 if (rflags & (M_NOWAIT | M_NOVM))
 2301                         break;
 2302                 flags = rflags;
 2303                 /*
 2304                  * All kegs are full.  XXX We can't atomically check all kegs
 2305                  * and sleep so just sleep for a short period and retry.
 2306                  */
 2307                 if (full && !empty) {
 2308                         zone->uz_flags |= UMA_ZFLAG_FULL;
 2309                         msleep(zone, zone->uz_lock, PVM, "zonelimit", hz/100);
 2310                         zone->uz_flags &= ~UMA_ZFLAG_FULL;
 2311                         continue;
 2312                 }
 2313         }
 2314         return (NULL);
 2315 }
 2316 
 2317 static void *
 2318 slab_alloc_item(uma_zone_t zone, uma_slab_t slab)
 2319 {
 2320         uma_keg_t keg;
 2321         uma_slabrefcnt_t slabref;
 2322         void *item;
 2323         u_int8_t freei;
 2324 
 2325         keg = slab->us_keg;
 2326         mtx_assert(&keg->uk_lock, MA_OWNED);
 2327 
 2328         freei = slab->us_firstfree;
 2329         if (keg->uk_flags & UMA_ZONE_REFCNT) {
 2330                 slabref = (uma_slabrefcnt_t)slab;
 2331                 slab->us_firstfree = slabref->us_freelist[freei].us_item;
 2332         } else {
 2333                 slab->us_firstfree = slab->us_freelist[freei].us_item;
 2334         }
 2335         item = slab->us_data + (keg->uk_rsize * freei);
 2336 
 2337         slab->us_freecount--;
 2338         keg->uk_free--;
 2339 #ifdef INVARIANTS
 2340         uma_dbg_alloc(zone, slab, item);
 2341 #endif
 2342         /* Move this slab to the full list */
 2343         if (slab->us_freecount == 0) {
 2344                 LIST_REMOVE(slab, us_link);
 2345                 LIST_INSERT_HEAD(&keg->uk_full_slab, slab, us_link);
 2346         }
 2347 
 2348         return (item);
 2349 }
 2350 
 2351 static int
 2352 zone_alloc_bucket(uma_zone_t zone, int flags)
 2353 {
 2354         uma_bucket_t bucket;
 2355         uma_slab_t slab;
 2356         uma_keg_t keg;
 2357         int16_t saved;
 2358         int max, origflags = flags;
 2359 
 2360         /*
 2361          * Try this zone's free list first so we don't allocate extra buckets.
 2362          */
 2363         if ((bucket = LIST_FIRST(&zone->uz_free_bucket)) != NULL) {
 2364                 KASSERT(bucket->ub_cnt == 0,
 2365                     ("zone_alloc_bucket: Bucket on free list is not empty."));
 2366                 LIST_REMOVE(bucket, ub_link);
 2367         } else {
 2368                 int bflags;
 2369 
 2370                 bflags = (flags & ~M_ZERO);
 2371                 if (zone->uz_flags & UMA_ZFLAG_CACHEONLY)
 2372                         bflags |= M_NOVM;
 2373 
 2374                 ZONE_UNLOCK(zone);
 2375                 bucket = bucket_alloc(zone->uz_count, bflags);
 2376                 ZONE_LOCK(zone);
 2377         }
 2378 
 2379         if (bucket == NULL) {
 2380                 return (0);
 2381         }
 2382 
 2383 #ifdef SMP
 2384         /*
 2385          * This code is here to limit the number of simultaneous bucket fills
 2386          * for any given zone to the number of per cpu caches in this zone. This
 2387          * is done so that we don't allocate more memory than we really need.
 2388          */
 2389         if (zone->uz_fills >= mp_ncpus)
 2390                 goto done;
 2391 
 2392 #endif
 2393         zone->uz_fills++;
 2394 
 2395         max = MIN(bucket->ub_entries, zone->uz_count);
 2396         /* Try to keep the buckets totally full */
 2397         saved = bucket->ub_cnt;
 2398         slab = NULL;
 2399         keg = NULL;
 2400         while (bucket->ub_cnt < max &&
 2401             (slab = zone->uz_slab(zone, keg, flags)) != NULL) {
 2402                 keg = slab->us_keg;
 2403                 while (slab->us_freecount && bucket->ub_cnt < max) {
 2404                         bucket->ub_bucket[bucket->ub_cnt++] =
 2405                             slab_alloc_item(zone, slab);
 2406                 }
 2407 
 2408                 /* Don't block on the next fill */
 2409                 flags |= M_NOWAIT;
 2410         }
 2411         if (slab)
 2412                 zone_relock(zone, keg);
 2413 
 2414         /*
 2415          * We unlock here because we need to call the zone's init.
 2416          * It should be safe to unlock because the slab dealt with
 2417          * above is already on the appropriate list within the keg
 2418          * and the bucket we filled is not yet on any list, so we
 2419          * own it.
 2420          */
 2421         if (zone->uz_init != NULL) {
 2422                 int i;
 2423 
 2424                 ZONE_UNLOCK(zone);
 2425                 for (i = saved; i < bucket->ub_cnt; i++)
 2426                         if (zone->uz_init(bucket->ub_bucket[i], zone->uz_size,
 2427                             origflags) != 0)
 2428                                 break;
 2429                 /*
 2430                  * If we couldn't initialize the whole bucket, put the
 2431                  * rest back onto the freelist.
 2432                  */
 2433                 if (i != bucket->ub_cnt) {
 2434                         int j;
 2435 
 2436                         for (j = i; j < bucket->ub_cnt; j++) {
 2437                                 zone_free_item(zone, bucket->ub_bucket[j],
 2438                                     NULL, SKIP_FINI, 0);
 2439 #ifdef INVARIANTS
 2440                                 bucket->ub_bucket[j] = NULL;
 2441 #endif
 2442                         }
 2443                         bucket->ub_cnt = i;
 2444                 }
 2445                 ZONE_LOCK(zone);
 2446         }
 2447 
 2448         zone->uz_fills--;
 2449         if (bucket->ub_cnt != 0) {
 2450                 LIST_INSERT_HEAD(&zone->uz_full_bucket,
 2451                     bucket, ub_link);
 2452                 return (1);
 2453         }
 2454 #ifdef SMP
 2455 done:
 2456 #endif
 2457         bucket_free(bucket);
 2458 
 2459         return (0);
 2460 }
 2461 /*
 2462  * Allocates an item for an internal zone
 2463  *
 2464  * Arguments
 2465  *      zone   The zone to alloc for.
 2466  *      udata  The data to be passed to the constructor.
 2467  *      flags  M_WAITOK, M_NOWAIT, M_ZERO.
 2468  *
 2469  * Returns
 2470  *      NULL if there is no memory and M_NOWAIT is set
 2471  *      An item if successful
 2472  */
 2473 
 2474 static void *
 2475 zone_alloc_item(uma_zone_t zone, void *udata, int flags)
 2476 {
 2477         uma_slab_t slab;
 2478         void *item;
 2479 
 2480         item = NULL;
 2481 
 2482 #ifdef UMA_DEBUG_ALLOC
 2483         printf("INTERNAL: Allocating one item from %s(%p)\n", zone->uz_name, zone);
 2484 #endif
 2485         ZONE_LOCK(zone);
 2486 
 2487         slab = zone->uz_slab(zone, NULL, flags);
 2488         if (slab == NULL) {
 2489                 zone->uz_fails++;
 2490                 ZONE_UNLOCK(zone);
 2491                 return (NULL);
 2492         }
 2493 
 2494         item = slab_alloc_item(zone, slab);
 2495 
 2496         zone_relock(zone, slab->us_keg);
 2497         zone->uz_allocs++;
 2498         ZONE_UNLOCK(zone);
 2499 
 2500         /*
 2501          * We have to call both the zone's init (not the keg's init)
 2502          * and the zone's ctor.  This is because the item is going from
 2503          * a keg slab directly to the user, and the user is expecting it
 2504          * to be both zone-init'd as well as zone-ctor'd.
 2505          */
 2506         if (zone->uz_init != NULL) {
 2507                 if (zone->uz_init(item, zone->uz_size, flags) != 0) {
 2508                         zone_free_item(zone, item, udata, SKIP_FINI,
 2509                             ZFREE_STATFAIL | ZFREE_STATFREE);
 2510                         return (NULL);
 2511                 }
 2512         }
 2513         if (zone->uz_ctor != NULL) {
 2514                 if (zone->uz_ctor(item, zone->uz_size, udata, flags) != 0) {
 2515                         zone_free_item(zone, item, udata, SKIP_DTOR,
 2516                             ZFREE_STATFAIL | ZFREE_STATFREE);
 2517                         return (NULL);
 2518                 }
 2519         }
 2520         if (flags & M_ZERO)
 2521                 bzero(item, zone->uz_size);
 2522 
 2523         return (item);
 2524 }
 2525 
 2526 /* See uma.h */
 2527 void
 2528 uma_zfree_arg(uma_zone_t zone, void *item, void *udata)
 2529 {
 2530         uma_cache_t cache;
 2531         uma_bucket_t bucket;
 2532         int bflags;
 2533         int cpu;
 2534 
 2535 #ifdef UMA_DEBUG_ALLOC_1
 2536         printf("Freeing item %p to %s(%p)\n", item, zone->uz_name, zone);
 2537 #endif
 2538         CTR2(KTR_UMA, "uma_zfree_arg thread %x zone %s", curthread,
 2539             zone->uz_name);
 2540 
 2541         /* uma_zfree(..., NULL) does nothing, to match free(9). */
 2542         if (item == NULL)
 2543                 return;
 2544 
 2545         if (zone->uz_dtor)
 2546                 zone->uz_dtor(item, zone->uz_size, udata);
 2547 
 2548 #ifdef INVARIANTS
 2549         ZONE_LOCK(zone);
 2550         if (zone->uz_flags & UMA_ZONE_MALLOC)
 2551                 uma_dbg_free(zone, udata, item);
 2552         else
 2553                 uma_dbg_free(zone, NULL, item);
 2554         ZONE_UNLOCK(zone);
 2555 #endif
 2556         /*
 2557          * The race here is acceptable.  If we miss it we'll just have to wait
 2558          * a little longer for the limits to be reset.
 2559          */
 2560         if (zone->uz_flags & UMA_ZFLAG_FULL)
 2561                 goto zfree_internal;
 2562 
 2563         /*
 2564          * If possible, free to the per-CPU cache.  There are two
 2565          * requirements for safe access to the per-CPU cache: (1) the thread
 2566          * accessing the cache must not be preempted or yield during access,
 2567          * and (2) the thread must not migrate CPUs without switching which
 2568          * cache it accesses.  We rely on a critical section to prevent
 2569          * preemption and migration.  We release the critical section in
 2570          * order to acquire the zone mutex if we are unable to free to the
 2571          * current cache; when we re-acquire the critical section, we must
 2572          * detect and handle migration if it has occurred.
 2573          */
 2574 zfree_restart:
 2575         critical_enter();
 2576         cpu = curcpu;
 2577         cache = &zone->uz_cpu[cpu];
 2578 
 2579 zfree_start:
 2580         bucket = cache->uc_freebucket;
 2581 
 2582         if (bucket) {
 2583                 /*
 2584                  * Do we have room in our bucket? It is OK for this uz count
 2585                  * check to be slightly out of sync.
 2586                  */
 2587 
 2588                 if (bucket->ub_cnt < bucket->ub_entries) {
 2589                         KASSERT(bucket->ub_bucket[bucket->ub_cnt] == NULL,
 2590                             ("uma_zfree: Freeing to non free bucket index."));
 2591                         bucket->ub_bucket[bucket->ub_cnt] = item;
 2592                         bucket->ub_cnt++;
 2593                         cache->uc_frees++;
 2594                         critical_exit();
 2595                         return;
 2596                 } else if (cache->uc_allocbucket) {
 2597 #ifdef UMA_DEBUG_ALLOC
 2598                         printf("uma_zfree: Swapping buckets.\n");
 2599 #endif
 2600                         /*
 2601                          * We have run out of space in our freebucket.
 2602                          * See if we can switch with our alloc bucket.
 2603                          */
 2604                         if (cache->uc_allocbucket->ub_cnt <
 2605                             cache->uc_freebucket->ub_cnt) {
 2606                                 bucket = cache->uc_freebucket;
 2607                                 cache->uc_freebucket = cache->uc_allocbucket;
 2608                                 cache->uc_allocbucket = bucket;
 2609                                 goto zfree_start;
 2610                         }
 2611                 }
 2612         }
 2613         /*
 2614          * We can get here for two reasons:
 2615          *
 2616          * 1) The buckets are NULL
 2617          * 2) The alloc and free buckets are both somewhat full.
 2618          *
 2619          * We must go back the zone, which requires acquiring the zone lock,
 2620          * which in turn means we must release and re-acquire the critical
 2621          * section.  Since the critical section is released, we may be
 2622          * preempted or migrate.  As such, make sure not to maintain any
 2623          * thread-local state specific to the cache from prior to releasing
 2624          * the critical section.
 2625          */
 2626         critical_exit();
 2627         ZONE_LOCK(zone);
 2628         critical_enter();
 2629         cpu = curcpu;
 2630         cache = &zone->uz_cpu[cpu];
 2631         if (cache->uc_freebucket != NULL) {
 2632                 if (cache->uc_freebucket->ub_cnt <
 2633                     cache->uc_freebucket->ub_entries) {
 2634                         ZONE_UNLOCK(zone);
 2635                         goto zfree_start;
 2636                 }
 2637                 if (cache->uc_allocbucket != NULL &&
 2638                     (cache->uc_allocbucket->ub_cnt <
 2639                     cache->uc_freebucket->ub_cnt)) {
 2640                         ZONE_UNLOCK(zone);
 2641                         goto zfree_start;
 2642                 }
 2643         }
 2644 
 2645         /* Since we have locked the zone we may as well send back our stats */
 2646         zone->uz_allocs += cache->uc_allocs;
 2647         cache->uc_allocs = 0;
 2648         zone->uz_frees += cache->uc_frees;
 2649         cache->uc_frees = 0;
 2650 
 2651         bucket = cache->uc_freebucket;
 2652         cache->uc_freebucket = NULL;
 2653 
 2654         /* Can we throw this on the zone full list? */
 2655         if (bucket != NULL) {
 2656 #ifdef UMA_DEBUG_ALLOC
 2657                 printf("uma_zfree: Putting old bucket on the free list.\n");
 2658 #endif
 2659                 /* ub_cnt is pointing to the last free item */
 2660                 KASSERT(bucket->ub_cnt != 0,
 2661                     ("uma_zfree: Attempting to insert an empty bucket onto the full list.\n"));
 2662                 LIST_INSERT_HEAD(&zone->uz_full_bucket,
 2663                     bucket, ub_link);
 2664         }
 2665         if ((bucket = LIST_FIRST(&zone->uz_free_bucket)) != NULL) {
 2666                 LIST_REMOVE(bucket, ub_link);
 2667                 ZONE_UNLOCK(zone);
 2668                 cache->uc_freebucket = bucket;
 2669                 goto zfree_start;
 2670         }
 2671         /* We are no longer associated with this CPU. */
 2672         critical_exit();
 2673 
 2674         /* And the zone.. */
 2675         ZONE_UNLOCK(zone);
 2676 
 2677 #ifdef UMA_DEBUG_ALLOC
 2678         printf("uma_zfree: Allocating new free bucket.\n");
 2679 #endif
 2680         bflags = M_NOWAIT;
 2681 
 2682         if (zone->uz_flags & UMA_ZFLAG_CACHEONLY)
 2683                 bflags |= M_NOVM;
 2684         bucket = bucket_alloc(zone->uz_count, bflags);
 2685         if (bucket) {
 2686                 ZONE_LOCK(zone);
 2687                 LIST_INSERT_HEAD(&zone->uz_free_bucket,
 2688                     bucket, ub_link);
 2689                 ZONE_UNLOCK(zone);
 2690                 goto zfree_restart;
 2691         }
 2692 
 2693         /*
 2694          * If nothing else caught this, we'll just do an internal free.
 2695          */
 2696 zfree_internal:
 2697         zone_free_item(zone, item, udata, SKIP_DTOR, ZFREE_STATFREE);
 2698 
 2699         return;
 2700 }
 2701 
 2702 /*
 2703  * Frees an item to an INTERNAL zone or allocates a free bucket
 2704  *
 2705  * Arguments:
 2706  *      zone   The zone to free to
 2707  *      item   The item we're freeing
 2708  *      udata  User supplied data for the dtor
 2709  *      skip   Skip dtors and finis
 2710  */
 2711 static void
 2712 zone_free_item(uma_zone_t zone, void *item, void *udata,
 2713     enum zfreeskip skip, int flags)
 2714 {
 2715         uma_slab_t slab;
 2716         uma_slabrefcnt_t slabref;
 2717         uma_keg_t keg;
 2718         u_int8_t *mem;
 2719         u_int8_t freei;
 2720         int clearfull;
 2721 
 2722         if (skip < SKIP_DTOR && zone->uz_dtor)
 2723                 zone->uz_dtor(item, zone->uz_size, udata);
 2724 
 2725         if (skip < SKIP_FINI && zone->uz_fini)
 2726                 zone->uz_fini(item, zone->uz_size);
 2727 
 2728         ZONE_LOCK(zone);
 2729 
 2730         if (flags & ZFREE_STATFAIL)
 2731                 zone->uz_fails++;
 2732         if (flags & ZFREE_STATFREE)
 2733                 zone->uz_frees++;
 2734 
 2735         if (!(zone->uz_flags & UMA_ZONE_VTOSLAB)) {
 2736                 mem = (u_int8_t *)((unsigned long)item & (~UMA_SLAB_MASK));
 2737                 keg = zone_first_keg(zone); /* Must only be one. */
 2738                 if (zone->uz_flags & UMA_ZONE_HASH) {
 2739                         slab = hash_sfind(&keg->uk_hash, mem);
 2740                 } else {
 2741                         mem += keg->uk_pgoff;
 2742                         slab = (uma_slab_t)mem;
 2743                 }
 2744         } else {
 2745                 /* This prevents redundant lookups via free(). */
 2746                 if ((zone->uz_flags & UMA_ZONE_MALLOC) && udata != NULL)
 2747                         slab = (uma_slab_t)udata;
 2748                 else
 2749                         slab = vtoslab((vm_offset_t)item);
 2750                 keg = slab->us_keg;
 2751                 keg_relock(keg, zone);
 2752         }
 2753         MPASS(keg == slab->us_keg);
 2754 
 2755         /* Do we need to remove from any lists? */
 2756         if (slab->us_freecount+1 == keg->uk_ipers) {
 2757                 LIST_REMOVE(slab, us_link);
 2758                 LIST_INSERT_HEAD(&keg->uk_free_slab, slab, us_link);
 2759         } else if (slab->us_freecount == 0) {
 2760                 LIST_REMOVE(slab, us_link);
 2761                 LIST_INSERT_HEAD(&keg->uk_part_slab, slab, us_link);
 2762         }
 2763 
 2764         /* Slab management stuff */
 2765         freei = ((unsigned long)item - (unsigned long)slab->us_data)
 2766                 / keg->uk_rsize;
 2767 
 2768 #ifdef INVARIANTS
 2769         if (!skip)
 2770                 uma_dbg_free(zone, slab, item);
 2771 #endif
 2772 
 2773         if (keg->uk_flags & UMA_ZONE_REFCNT) {
 2774                 slabref = (uma_slabrefcnt_t)slab;
 2775                 slabref->us_freelist[freei].us_item = slab->us_firstfree;
 2776         } else {
 2777                 slab->us_freelist[freei].us_item = slab->us_firstfree;
 2778         }
 2779         slab->us_firstfree = freei;
 2780         slab->us_freecount++;
 2781 
 2782         /* Zone statistics */
 2783         keg->uk_free++;
 2784 
 2785         clearfull = 0;
 2786         if (keg->uk_flags & UMA_ZFLAG_FULL) {
 2787                 if (keg->uk_pages < keg->uk_maxpages) {
 2788                         keg->uk_flags &= ~UMA_ZFLAG_FULL;
 2789                         clearfull = 1;
 2790                 }
 2791 
 2792                 /* 
 2793                  * We can handle one more allocation. Since we're clearing ZFLAG_FULL,
 2794                  * wake up all procs blocked on pages. This should be uncommon, so 
 2795                  * keeping this simple for now (rather than adding count of blocked 
 2796                  * threads etc).
 2797                  */
 2798                 wakeup(keg);
 2799         }
 2800         if (clearfull) {
 2801                 zone_relock(zone, keg);
 2802                 zone->uz_flags &= ~UMA_ZFLAG_FULL;
 2803                 wakeup(zone);
 2804                 ZONE_UNLOCK(zone);
 2805         } else
 2806                 KEG_UNLOCK(keg);
 2807 }
 2808 
 2809 /* See uma.h */
 2810 void
 2811 uma_zone_set_max(uma_zone_t zone, int nitems)
 2812 {
 2813         uma_keg_t keg;
 2814 
 2815         ZONE_LOCK(zone);
 2816         keg = zone_first_keg(zone);
 2817         keg->uk_maxpages = (nitems / keg->uk_ipers) * keg->uk_ppera;
 2818         if (keg->uk_maxpages * keg->uk_ipers < nitems)
 2819                 keg->uk_maxpages += keg->uk_ppera;
 2820 
 2821         ZONE_UNLOCK(zone);
 2822 }
 2823 
 2824 /* See uma.h */
 2825 int
 2826 uma_zone_get_max(uma_zone_t zone)
 2827 {
 2828         int nitems;
 2829         uma_keg_t keg;
 2830 
 2831         ZONE_LOCK(zone);
 2832         keg = zone_first_keg(zone);
 2833         nitems = keg->uk_maxpages * keg->uk_ipers;
 2834         ZONE_UNLOCK(zone);
 2835 
 2836         return (nitems);
 2837 }
 2838 
 2839 /* See uma.h */
 2840 int
 2841 uma_zone_get_cur(uma_zone_t zone)
 2842 {
 2843         int64_t nitems;
 2844         u_int i;
 2845 
 2846         ZONE_LOCK(zone);
 2847         nitems = zone->uz_allocs - zone->uz_frees;
 2848         CPU_FOREACH(i) {
 2849                 /*
 2850                  * See the comment in sysctl_vm_zone_stats() regarding the
 2851                  * safety of accessing the per-cpu caches. With the zone lock
 2852                  * held, it is safe, but can potentially result in stale data.
 2853                  */
 2854                 nitems += zone->uz_cpu[i].uc_allocs -
 2855                     zone->uz_cpu[i].uc_frees;
 2856         }
 2857         ZONE_UNLOCK(zone);
 2858 
 2859         return (nitems < 0 ? 0 : nitems);
 2860 }
 2861 
 2862 /* See uma.h */
 2863 void
 2864 uma_zone_set_init(uma_zone_t zone, uma_init uminit)
 2865 {
 2866         uma_keg_t keg;
 2867 
 2868         ZONE_LOCK(zone);
 2869         keg = zone_first_keg(zone);
 2870         KASSERT(keg->uk_pages == 0,
 2871             ("uma_zone_set_init on non-empty keg"));
 2872         keg->uk_init = uminit;
 2873         ZONE_UNLOCK(zone);
 2874 }
 2875 
 2876 /* See uma.h */
 2877 void
 2878 uma_zone_set_fini(uma_zone_t zone, uma_fini fini)
 2879 {
 2880         uma_keg_t keg;
 2881 
 2882         ZONE_LOCK(zone);
 2883         keg = zone_first_keg(zone);
 2884         KASSERT(keg->uk_pages == 0,
 2885             ("uma_zone_set_fini on non-empty keg"));
 2886         keg->uk_fini = fini;
 2887         ZONE_UNLOCK(zone);
 2888 }
 2889 
 2890 /* See uma.h */
 2891 void
 2892 uma_zone_set_zinit(uma_zone_t zone, uma_init zinit)
 2893 {
 2894         ZONE_LOCK(zone);
 2895         KASSERT(zone_first_keg(zone)->uk_pages == 0,
 2896             ("uma_zone_set_zinit on non-empty keg"));
 2897         zone->uz_init = zinit;
 2898         ZONE_UNLOCK(zone);
 2899 }
 2900 
 2901 /* See uma.h */
 2902 void
 2903 uma_zone_set_zfini(uma_zone_t zone, uma_fini zfini)
 2904 {
 2905         ZONE_LOCK(zone);
 2906         KASSERT(zone_first_keg(zone)->uk_pages == 0,
 2907             ("uma_zone_set_zfini on non-empty keg"));
 2908         zone->uz_fini = zfini;
 2909         ZONE_UNLOCK(zone);
 2910 }
 2911 
 2912 /* See uma.h */
 2913 /* XXX uk_freef is not actually used with the zone locked */
 2914 void
 2915 uma_zone_set_freef(uma_zone_t zone, uma_free freef)
 2916 {
 2917 
 2918         ZONE_LOCK(zone);
 2919         zone_first_keg(zone)->uk_freef = freef;
 2920         ZONE_UNLOCK(zone);
 2921 }
 2922 
 2923 /* See uma.h */
 2924 /* XXX uk_allocf is not actually used with the zone locked */
 2925 void
 2926 uma_zone_set_allocf(uma_zone_t zone, uma_alloc allocf)
 2927 {
 2928         uma_keg_t keg;
 2929 
 2930         ZONE_LOCK(zone);
 2931         keg = zone_first_keg(zone);
 2932         keg->uk_flags |= UMA_ZFLAG_PRIVALLOC;
 2933         keg->uk_allocf = allocf;
 2934         ZONE_UNLOCK(zone);
 2935 }
 2936 
 2937 /* See uma.h */
 2938 int
 2939 uma_zone_set_obj(uma_zone_t zone, struct vm_object *obj, int count)
 2940 {
 2941         uma_keg_t keg;
 2942         vm_offset_t kva;
 2943         int pages;
 2944 
 2945         keg = zone_first_keg(zone);
 2946         pages = count / keg->uk_ipers;
 2947 
 2948         if (pages * keg->uk_ipers < count)
 2949                 pages++;
 2950 
 2951         kva = kmem_alloc_nofault(kernel_map, pages * UMA_SLAB_SIZE);
 2952 
 2953         if (kva == 0)
 2954                 return (0);
 2955         if (obj == NULL) {
 2956                 obj = vm_object_allocate(OBJT_DEFAULT,
 2957                     pages);
 2958         } else {
 2959                 VM_OBJECT_LOCK_INIT(obj, "uma object");
 2960                 _vm_object_allocate(OBJT_DEFAULT,
 2961                     pages, obj);
 2962         }
 2963         ZONE_LOCK(zone);
 2964         keg->uk_kva = kva;
 2965         keg->uk_obj = obj;
 2966         keg->uk_maxpages = pages;
 2967         keg->uk_allocf = obj_alloc;
 2968         keg->uk_flags |= UMA_ZONE_NOFREE | UMA_ZFLAG_PRIVALLOC;
 2969         ZONE_UNLOCK(zone);
 2970         return (1);
 2971 }
 2972 
 2973 /* See uma.h */
 2974 void
 2975 uma_prealloc(uma_zone_t zone, int items)
 2976 {
 2977         int slabs;
 2978         uma_slab_t slab;
 2979         uma_keg_t keg;
 2980 
 2981         keg = zone_first_keg(zone);
 2982         ZONE_LOCK(zone);
 2983         slabs = items / keg->uk_ipers;
 2984         if (slabs * keg->uk_ipers < items)
 2985                 slabs++;
 2986         while (slabs > 0) {
 2987                 slab = keg_alloc_slab(keg, zone, M_WAITOK);
 2988                 if (slab == NULL)
 2989                         break;
 2990                 MPASS(slab->us_keg == keg);
 2991                 LIST_INSERT_HEAD(&keg->uk_free_slab, slab, us_link);
 2992                 slabs--;
 2993         }
 2994         ZONE_UNLOCK(zone);
 2995 }
 2996 
 2997 /* See uma.h */
 2998 u_int32_t *
 2999 uma_find_refcnt(uma_zone_t zone, void *item)
 3000 {
 3001         uma_slabrefcnt_t slabref;
 3002         uma_keg_t keg;
 3003         u_int32_t *refcnt;
 3004         int idx;
 3005 
 3006         slabref = (uma_slabrefcnt_t)vtoslab((vm_offset_t)item &
 3007             (~UMA_SLAB_MASK));
 3008         keg = slabref->us_keg;
 3009         KASSERT(slabref != NULL && slabref->us_keg->uk_flags & UMA_ZONE_REFCNT,
 3010             ("uma_find_refcnt(): zone possibly not UMA_ZONE_REFCNT"));
 3011         idx = ((unsigned long)item - (unsigned long)slabref->us_data)
 3012             / keg->uk_rsize;
 3013         refcnt = &slabref->us_freelist[idx].us_refcnt;
 3014         return refcnt;
 3015 }
 3016 
 3017 /* See uma.h */
 3018 void
 3019 uma_reclaim(void)
 3020 {
 3021 #ifdef UMA_DEBUG
 3022         printf("UMA: vm asked us to release pages!\n");
 3023 #endif
 3024         bucket_enable();
 3025         zone_foreach(zone_drain);
 3026         /*
 3027          * Some slabs may have been freed but this zone will be visited early
 3028          * we visit again so that we can free pages that are empty once other
 3029          * zones are drained.  We have to do the same for buckets.
 3030          */
 3031         zone_drain(slabzone);
 3032         zone_drain(slabrefzone);
 3033         bucket_zone_drain();
 3034 }
 3035 
 3036 /* See uma.h */
 3037 int
 3038 uma_zone_exhausted(uma_zone_t zone)
 3039 {
 3040         int full;
 3041 
 3042         ZONE_LOCK(zone);
 3043         full = (zone->uz_flags & UMA_ZFLAG_FULL);
 3044         ZONE_UNLOCK(zone);
 3045         return (full);  
 3046 }
 3047 
 3048 int
 3049 uma_zone_exhausted_nolock(uma_zone_t zone)
 3050 {
 3051         return (zone->uz_flags & UMA_ZFLAG_FULL);
 3052 }
 3053 
 3054 void *
 3055 uma_large_malloc(int size, int wait)
 3056 {
 3057         void *mem;
 3058         uma_slab_t slab;
 3059         u_int8_t flags;
 3060 
 3061         slab = zone_alloc_item(slabzone, NULL, wait);
 3062         if (slab == NULL)
 3063                 return (NULL);
 3064         mem = page_alloc(NULL, size, &flags, wait);
 3065         if (mem) {
 3066                 vsetslab((vm_offset_t)mem, slab);
 3067                 slab->us_data = mem;
 3068                 slab->us_flags = flags | UMA_SLAB_MALLOC;
 3069                 slab->us_size = size;
 3070         } else {
 3071                 zone_free_item(slabzone, slab, NULL, SKIP_NONE,
 3072                     ZFREE_STATFAIL | ZFREE_STATFREE);
 3073         }
 3074 
 3075         return (mem);
 3076 }
 3077 
 3078 void
 3079 uma_large_free(uma_slab_t slab)
 3080 {
 3081         vsetobj((vm_offset_t)slab->us_data, kmem_object);
 3082         page_free(slab->us_data, slab->us_size, slab->us_flags);
 3083         zone_free_item(slabzone, slab, NULL, SKIP_NONE, ZFREE_STATFREE);
 3084 }
 3085 
 3086 void
 3087 uma_print_stats(void)
 3088 {
 3089         zone_foreach(uma_print_zone);
 3090 }
 3091 
 3092 static void
 3093 slab_print(uma_slab_t slab)
 3094 {
 3095         printf("slab: keg %p, data %p, freecount %d, firstfree %d\n",
 3096                 slab->us_keg, slab->us_data, slab->us_freecount,
 3097                 slab->us_firstfree);
 3098 }
 3099 
 3100 static void
 3101 cache_print(uma_cache_t cache)
 3102 {
 3103         printf("alloc: %p(%d), free: %p(%d)\n",
 3104                 cache->uc_allocbucket,
 3105                 cache->uc_allocbucket?cache->uc_allocbucket->ub_cnt:0,
 3106                 cache->uc_freebucket,
 3107                 cache->uc_freebucket?cache->uc_freebucket->ub_cnt:0);
 3108 }
 3109 
 3110 static void
 3111 uma_print_keg(uma_keg_t keg)
 3112 {
 3113         uma_slab_t slab;
 3114 
 3115         printf("keg: %s(%p) size %d(%d) flags %d ipers %d ppera %d "
 3116             "out %d free %d limit %d\n",
 3117             keg->uk_name, keg, keg->uk_size, keg->uk_rsize, keg->uk_flags,
 3118             keg->uk_ipers, keg->uk_ppera,
 3119             (keg->uk_ipers * keg->uk_pages) - keg->uk_free, keg->uk_free,
 3120             (keg->uk_maxpages / keg->uk_ppera) * keg->uk_ipers);
 3121         printf("Part slabs:\n");
 3122         LIST_FOREACH(slab, &keg->uk_part_slab, us_link)
 3123                 slab_print(slab);
 3124         printf("Free slabs:\n");
 3125         LIST_FOREACH(slab, &keg->uk_free_slab, us_link)
 3126                 slab_print(slab);
 3127         printf("Full slabs:\n");
 3128         LIST_FOREACH(slab, &keg->uk_full_slab, us_link)
 3129                 slab_print(slab);
 3130 }
 3131 
 3132 void
 3133 uma_print_zone(uma_zone_t zone)
 3134 {
 3135         uma_cache_t cache;
 3136         uma_klink_t kl;
 3137         int i;
 3138 
 3139         printf("zone: %s(%p) size %d flags %d\n",
 3140             zone->uz_name, zone, zone->uz_size, zone->uz_flags);
 3141         LIST_FOREACH(kl, &zone->uz_kegs, kl_link)
 3142                 uma_print_keg(kl->kl_keg);
 3143         CPU_FOREACH(i) {
 3144                 cache = &zone->uz_cpu[i];
 3145                 printf("CPU %d Cache:\n", i);
 3146                 cache_print(cache);
 3147         }
 3148 }
 3149 
 3150 #ifdef DDB
 3151 /*
 3152  * Generate statistics across both the zone and its per-cpu cache's.  Return
 3153  * desired statistics if the pointer is non-NULL for that statistic.
 3154  *
 3155  * Note: does not update the zone statistics, as it can't safely clear the
 3156  * per-CPU cache statistic.
 3157  *
 3158  * XXXRW: Following the uc_allocbucket and uc_freebucket pointers here isn't
 3159  * safe from off-CPU; we should modify the caches to track this information
 3160  * directly so that we don't have to.
 3161  */
 3162 static void
 3163 uma_zone_sumstat(uma_zone_t z, int *cachefreep, u_int64_t *allocsp,
 3164     u_int64_t *freesp)
 3165 {
 3166         uma_cache_t cache;
 3167         u_int64_t allocs, frees;
 3168         int cachefree, cpu;
 3169 
 3170         allocs = frees = 0;
 3171         cachefree = 0;
 3172         CPU_FOREACH(cpu) {
 3173                 cache = &z->uz_cpu[cpu];
 3174                 if (cache->uc_allocbucket != NULL)
 3175                         cachefree += cache->uc_allocbucket->ub_cnt;
 3176                 if (cache->uc_freebucket != NULL)
 3177                         cachefree += cache->uc_freebucket->ub_cnt;
 3178                 allocs += cache->uc_allocs;
 3179                 frees += cache->uc_frees;
 3180         }
 3181         allocs += z->uz_allocs;
 3182         frees += z->uz_frees;
 3183         if (cachefreep != NULL)
 3184                 *cachefreep = cachefree;
 3185         if (allocsp != NULL)
 3186                 *allocsp = allocs;
 3187         if (freesp != NULL)
 3188                 *freesp = frees;
 3189 }
 3190 #endif /* DDB */
 3191 
 3192 static int
 3193 sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS)
 3194 {
 3195         uma_keg_t kz;
 3196         uma_zone_t z;
 3197         int count;
 3198 
 3199         count = 0;
 3200         mtx_lock(&uma_mtx);
 3201         LIST_FOREACH(kz, &uma_kegs, uk_link) {
 3202                 LIST_FOREACH(z, &kz->uk_zones, uz_link)
 3203                         count++;
 3204         }
 3205         mtx_unlock(&uma_mtx);
 3206         return (sysctl_handle_int(oidp, &count, 0, req));
 3207 }
 3208 
 3209 static int
 3210 sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS)
 3211 {
 3212         struct uma_stream_header ush;
 3213         struct uma_type_header uth;
 3214         struct uma_percpu_stat ups;
 3215         uma_bucket_t bucket;
 3216         struct sbuf sbuf;
 3217         uma_cache_t cache;
 3218         uma_klink_t kl;
 3219         uma_keg_t kz;
 3220         uma_zone_t z;
 3221         uma_keg_t k;
 3222         char *buffer;
 3223         int buflen, count, error, i;
 3224 
 3225         mtx_lock(&uma_mtx);
 3226 restart:
 3227         mtx_assert(&uma_mtx, MA_OWNED);
 3228         count = 0;
 3229         LIST_FOREACH(kz, &uma_kegs, uk_link) {
 3230                 LIST_FOREACH(z, &kz->uk_zones, uz_link)
 3231                         count++;
 3232         }
 3233         mtx_unlock(&uma_mtx);
 3234 
 3235         buflen = sizeof(ush) + count * (sizeof(uth) + sizeof(ups) *
 3236             (mp_maxid + 1)) + 1;
 3237         buffer = malloc(buflen, M_TEMP, M_WAITOK | M_ZERO);
 3238 
 3239         mtx_lock(&uma_mtx);
 3240         i = 0;
 3241         LIST_FOREACH(kz, &uma_kegs, uk_link) {
 3242                 LIST_FOREACH(z, &kz->uk_zones, uz_link)
 3243                         i++;
 3244         }
 3245         if (i > count) {
 3246                 free(buffer, M_TEMP);
 3247                 goto restart;
 3248         }
 3249         count =  i;
 3250 
 3251         sbuf_new(&sbuf, buffer, buflen, SBUF_FIXEDLEN);
 3252 
 3253         /*
 3254          * Insert stream header.
 3255          */
 3256         bzero(&ush, sizeof(ush));
 3257         ush.ush_version = UMA_STREAM_VERSION;
 3258         ush.ush_maxcpus = (mp_maxid + 1);
 3259         ush.ush_count = count;
 3260         if (sbuf_bcat(&sbuf, &ush, sizeof(ush)) < 0) {
 3261                 mtx_unlock(&uma_mtx);
 3262                 error = ENOMEM;
 3263                 goto out;
 3264         }
 3265 
 3266         LIST_FOREACH(kz, &uma_kegs, uk_link) {
 3267                 LIST_FOREACH(z, &kz->uk_zones, uz_link) {
 3268                         bzero(&uth, sizeof(uth));
 3269                         ZONE_LOCK(z);
 3270                         strlcpy(uth.uth_name, z->uz_name, UTH_MAX_NAME);
 3271                         uth.uth_align = kz->uk_align;
 3272                         uth.uth_size = kz->uk_size;
 3273                         uth.uth_rsize = kz->uk_rsize;
 3274                         LIST_FOREACH(kl, &z->uz_kegs, kl_link) {
 3275                                 k = kl->kl_keg;
 3276                                 uth.uth_maxpages += k->uk_maxpages;
 3277                                 uth.uth_pages += k->uk_pages;
 3278                                 uth.uth_keg_free += k->uk_free;
 3279                                 uth.uth_limit = (k->uk_maxpages / k->uk_ppera)
 3280                                     * k->uk_ipers;
 3281                         }
 3282 
 3283                         /*
 3284                          * A zone is secondary is it is not the first entry
 3285                          * on the keg's zone list.
 3286                          */
 3287                         if ((z->uz_flags & UMA_ZONE_SECONDARY) &&
 3288                             (LIST_FIRST(&kz->uk_zones) != z))
 3289                                 uth.uth_zone_flags = UTH_ZONE_SECONDARY;
 3290 
 3291                         LIST_FOREACH(bucket, &z->uz_full_bucket, ub_link)
 3292                                 uth.uth_zone_free += bucket->ub_cnt;
 3293                         uth.uth_allocs = z->uz_allocs;
 3294                         uth.uth_frees = z->uz_frees;
 3295                         uth.uth_fails = z->uz_fails;
 3296                         if (sbuf_bcat(&sbuf, &uth, sizeof(uth)) < 0) {
 3297                                 ZONE_UNLOCK(z);
 3298                                 mtx_unlock(&uma_mtx);
 3299                                 error = ENOMEM;
 3300                                 goto out;
 3301                         }
 3302                         /*
 3303                          * While it is not normally safe to access the cache
 3304                          * bucket pointers while not on the CPU that owns the
 3305                          * cache, we only allow the pointers to be exchanged
 3306                          * without the zone lock held, not invalidated, so
 3307                          * accept the possible race associated with bucket
 3308                          * exchange during monitoring.
 3309                          */
 3310                         for (i = 0; i < (mp_maxid + 1); i++) {
 3311                                 bzero(&ups, sizeof(ups));
 3312                                 if (kz->uk_flags & UMA_ZFLAG_INTERNAL)
 3313                                         goto skip;
 3314                                 if (CPU_ABSENT(i))
 3315                                         goto skip;
 3316                                 cache = &z->uz_cpu[i];
 3317                                 if (cache->uc_allocbucket != NULL)
 3318                                         ups.ups_cache_free +=
 3319                                             cache->uc_allocbucket->ub_cnt;
 3320                                 if (cache->uc_freebucket != NULL)
 3321                                         ups.ups_cache_free +=
 3322                                             cache->uc_freebucket->ub_cnt;
 3323                                 ups.ups_allocs = cache->uc_allocs;
 3324                                 ups.ups_frees = cache->uc_frees;
 3325 skip:
 3326                                 if (sbuf_bcat(&sbuf, &ups, sizeof(ups)) < 0) {
 3327                                         ZONE_UNLOCK(z);
 3328                                         mtx_unlock(&uma_mtx);
 3329                                         error = ENOMEM;
 3330                                         goto out;
 3331                                 }
 3332                         }
 3333                         ZONE_UNLOCK(z);
 3334                 }
 3335         }
 3336         mtx_unlock(&uma_mtx);
 3337         sbuf_finish(&sbuf);
 3338         error = SYSCTL_OUT(req, sbuf_data(&sbuf), sbuf_len(&sbuf));
 3339 out:
 3340         free(buffer, M_TEMP);
 3341         return (error);
 3342 }
 3343 
 3344 #ifdef DDB
 3345 DB_SHOW_COMMAND(uma, db_show_uma)
 3346 {
 3347         u_int64_t allocs, frees;
 3348         uma_bucket_t bucket;
 3349         uma_keg_t kz;
 3350         uma_zone_t z;
 3351         int cachefree;
 3352 
 3353         db_printf("%18s %8s %8s %8s %12s\n", "Zone", "Size", "Used", "Free",
 3354             "Requests");
 3355         LIST_FOREACH(kz, &uma_kegs, uk_link) {
 3356                 LIST_FOREACH(z, &kz->uk_zones, uz_link) {
 3357                         if (kz->uk_flags & UMA_ZFLAG_INTERNAL) {
 3358                                 allocs = z->uz_allocs;
 3359                                 frees = z->uz_frees;
 3360                                 cachefree = 0;
 3361                         } else
 3362                                 uma_zone_sumstat(z, &cachefree, &allocs,
 3363                                     &frees);
 3364                         if (!((z->uz_flags & UMA_ZONE_SECONDARY) &&
 3365                             (LIST_FIRST(&kz->uk_zones) != z)))
 3366                                 cachefree += kz->uk_free;
 3367                         LIST_FOREACH(bucket, &z->uz_full_bucket, ub_link)
 3368                                 cachefree += bucket->ub_cnt;
 3369                         db_printf("%18s %8ju %8jd %8d %12ju\n", z->uz_name,
 3370                             (uintmax_t)kz->uk_size,
 3371                             (intmax_t)(allocs - frees), cachefree,
 3372                             (uintmax_t)allocs);
 3373                 }
 3374         }
 3375 }
 3376 #endif

Cache object: c9bbc89f28f7f1be212bb6f452764f5e


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