sys/vm/uma_core.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2002-2019 Jeffrey Roberson <jeff@FreeBSD.org>
   5  * Copyright (c) 2004, 2005 Bosko Milekic <bmilekic@FreeBSD.org>
   6  * Copyright (c) 2004-2006 Robert N. M. Watson
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice unmodified, this list of conditions, and the following
  14  *    disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * uma_core.c  Implementation of the Universal Memory allocator
  33  *
  34  * This allocator is intended to replace the multitude of similar object caches
  35  * in the standard FreeBSD kernel.  The intent is to be flexible as well as
  36  * efficient.  A primary design goal is to return unused memory to the rest of
  37  * the system.  This will make the system as a whole more flexible due to the
  38  * ability to move memory to subsystems which most need it instead of leaving
  39  * pools of reserved memory unused.
  40  *
  41  * The basic ideas stem from similar slab/zone based allocators whose algorithms
  42  * are well known.
  43  *
  44  */
  45
  46 /*
  47  * TODO:
  48  *      - Improve memory usage for large allocations
  49  *      - Investigate cache size adjustments
  50  */
  51
  52 #include <sys/cdefs.h>
  53 __FBSDID("$FreeBSD$");
  54
  55 #include "opt_ddb.h"
  56 #include "opt_param.h"
  57 #include "opt_vm.h"
  58
  59 #include <sys/param.h>
  60 #include <sys/systm.h>
  61 #include <sys/bitset.h>
  62 #include <sys/domainset.h>
  63 #include <sys/eventhandler.h>
  64 #include <sys/kernel.h>
  65 #include <sys/types.h>
  66 #include <sys/limits.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/random.h>
  75 #include <sys/rwlock.h>
  76 #include <sys/sbuf.h>
  77 #include <sys/sched.h>
  78 #include <sys/sleepqueue.h>
  79 #include <sys/smp.h>
  80 #include <sys/taskqueue.h>
  81 #include <sys/vmmeter.h>
  82
  83 #include <vm/vm.h>
  84 #include <vm/vm_domainset.h>
  85 #include <vm/vm_object.h>
  86 #include <vm/vm_page.h>
  87 #include <vm/vm_pageout.h>
  88 #include <vm/vm_param.h>
  89 #include <vm/vm_phys.h>
  90 #include <vm/vm_pagequeue.h>
  91 #include <vm/vm_map.h>
  92 #include <vm/vm_kern.h>
  93 #include <vm/vm_extern.h>
  94 #include <vm/uma.h>
  95 #include <vm/uma_int.h>
  96 #include <vm/uma_dbg.h>
  97
  98 #include <ddb/ddb.h>
  99
 100 #ifdef DEBUG_MEMGUARD
 101 #include <vm/memguard.h>
 102 #endif
 103
 104 #include <machine/md_var.h>
 105
 106 /*
 107  * This is the zone and keg from which all zones are spawned.
 108  */
 109 static uma_zone_t kegs;
 110 static uma_zone_t zones;
 111
 112 /*
 113  * These are the two zones from which all offpage uma_slab_ts are allocated.
 114  *
 115  * One zone is for slab headers that can represent a larger number of items,
 116  * making the slabs themselves more efficient, and the other zone is for
 117  * headers that are smaller and represent fewer items, making the headers more
 118  * efficient.
 119  */
 120 #define SLABZONE_SIZE(setsize)                                  \
 121     (sizeof(struct uma_hash_slab) + BITSET_SIZE(setsize) * SLAB_BITSETS)
 122 #define SLABZONE0_SETSIZE       (PAGE_SIZE / 16)
 123 #define SLABZONE1_SETSIZE       SLAB_MAX_SETSIZE
 124 #define SLABZONE0_SIZE  SLABZONE_SIZE(SLABZONE0_SETSIZE)
 125 #define SLABZONE1_SIZE  SLABZONE_SIZE(SLABZONE1_SETSIZE)
 126 static uma_zone_t slabzones[2];
 127
 128 /*
 129  * The initial hash tables come out of this zone so they can be allocated
 130  * prior to malloc coming up.
 131  */
 132 static uma_zone_t hashzone;
 133
 134 /* The boot-time adjusted value for cache line alignment. */
 135 int uma_align_cache = 64 - 1;
 136
 137 static MALLOC_DEFINE(M_UMAHASH, "UMAHash", "UMA Hash Buckets");
 138 static MALLOC_DEFINE(M_UMA, "UMA", "UMA Misc");
 139
 140 /*
 141  * Are we allowed to allocate buckets?
 142  */
 143 static int bucketdisable = 1;
 144
 145 /* Linked list of all kegs in the system */
 146 static LIST_HEAD(,uma_keg) uma_kegs = LIST_HEAD_INITIALIZER(uma_kegs);
 147
 148 /* Linked list of all cache-only zones in the system */
 149 static LIST_HEAD(,uma_zone) uma_cachezones =
 150     LIST_HEAD_INITIALIZER(uma_cachezones);
 151
 152 /* This RW lock protects the keg list */
 153 static struct rwlock_padalign __exclusive_cache_line uma_rwlock;
 154
 155 /*
 156  * First available virual address for boot time allocations.
 157  */
 158 static vm_offset_t bootstart;
 159 static vm_offset_t bootmem;
 160
 161 static struct sx uma_reclaim_lock;
 162
 163 /*
 164  * kmem soft limit, initialized by uma_set_limit().  Ensure that early
 165  * allocations don't trigger a wakeup of the reclaim thread.
 166  */
 167 unsigned long uma_kmem_limit = LONG_MAX;
 168 SYSCTL_ULONG(_vm, OID_AUTO, uma_kmem_limit, CTLFLAG_RD, &uma_kmem_limit, 0,
 169     "UMA kernel memory soft limit");
 170 unsigned long uma_kmem_total;
 171 SYSCTL_ULONG(_vm, OID_AUTO, uma_kmem_total, CTLFLAG_RD, &uma_kmem_total, 0,
 172     "UMA kernel memory usage");
 173
 174 /* Is the VM done starting up? */
 175 static enum {
 176         BOOT_COLD,
 177         BOOT_KVA,
 178         BOOT_RUNNING,
 179         BOOT_SHUTDOWN,
 180 } booted = BOOT_COLD;
 181
 182 /*
 183  * This is the handle used to schedule events that need to happen
 184  * outside of the allocation fast path.
 185  */
 186 static struct callout uma_callout;
 187 #define UMA_TIMEOUT     20              /* Seconds for callout interval. */
 188
 189 /*
 190  * This structure is passed as the zone ctor arg so that I don't have to create
 191  * a special allocation function just for zones.
 192  */
 193 struct uma_zctor_args {
 194         const char *name;
 195         size_t size;
 196         uma_ctor ctor;
 197         uma_dtor dtor;
 198         uma_init uminit;
 199         uma_fini fini;
 200         uma_import import;
 201         uma_release release;
 202         void *arg;
 203         uma_keg_t keg;
 204         int align;
 205         uint32_t flags;
 206 };
 207
 208 struct uma_kctor_args {
 209         uma_zone_t zone;
 210         size_t size;
 211         uma_init uminit;
 212         uma_fini fini;
 213         int align;
 214         uint32_t flags;
 215 };
 216
 217 struct uma_bucket_zone {
 218         uma_zone_t      ubz_zone;
 219         char            *ubz_name;
 220         int             ubz_entries;    /* Number of items it can hold. */
 221         int             ubz_maxsize;    /* Maximum allocation size per-item. */
 222 };
 223
 224 /*
 225  * Compute the actual number of bucket entries to pack them in power
 226  * of two sizes for more efficient space utilization.
 227  */
 228 #define BUCKET_SIZE(n)                                          \
 229     (((sizeof(void *) * (n)) - sizeof(struct uma_bucket)) / sizeof(void *))
 230
 231 #define BUCKET_MAX      BUCKET_SIZE(256)
 232 #define BUCKET_MIN      BUCKET_SIZE(4)
 233
 234 struct uma_bucket_zone bucket_zones[] = {
 235         { NULL, "4 Bucket", BUCKET_SIZE(4), 4096 },
 236         { NULL, "6 Bucket", BUCKET_SIZE(6), 3072 },
 237         { NULL, "8 Bucket", BUCKET_SIZE(8), 2048 },
 238         { NULL, "12 Bucket", BUCKET_SIZE(12), 1536 },
 239         { NULL, "16 Bucket", BUCKET_SIZE(16), 1024 },
 240         { NULL, "32 Bucket", BUCKET_SIZE(32), 512 },
 241         { NULL, "64 Bucket", BUCKET_SIZE(64), 256 },
 242         { NULL, "128 Bucket", BUCKET_SIZE(128), 128 },
 243         { NULL, "256 Bucket", BUCKET_SIZE(256), 64 },
 244         { NULL, NULL, 0}
 245 };
 246
 247 /*
 248  * Flags and enumerations to be passed to internal functions.
 249  */
 250 enum zfreeskip {
 251         SKIP_NONE =     0,
 252         SKIP_CNT =      0x00000001,
 253         SKIP_DTOR =     0x00010000,
 254         SKIP_FINI =     0x00020000,
 255 };
 256
 257 /* Prototypes.. */
 258
 259 void    uma_startup1(vm_offset_t);
 260 void    uma_startup2(void);
 261
 262 static void *noobj_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
 263 static void *page_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
 264 static void *pcpu_page_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
 265 static void *startup_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
 266 static void page_free(void *, vm_size_t, uint8_t);
 267 static void pcpu_page_free(void *, vm_size_t, uint8_t);
 268 static uma_slab_t keg_alloc_slab(uma_keg_t, uma_zone_t, int, int, int);
 269 static void cache_drain(uma_zone_t);
 270 static void bucket_drain(uma_zone_t, uma_bucket_t);
 271 static void bucket_cache_reclaim(uma_zone_t zone, bool);
 272 static int keg_ctor(void *, int, void *, int);
 273 static void keg_dtor(void *, int, void *);
 274 static int zone_ctor(void *, int, void *, int);
 275 static void zone_dtor(void *, int, void *);
 276 static int zero_init(void *, int, int);
 277 static void zone_foreach(void (*zfunc)(uma_zone_t, void *), void *);
 278 static void zone_foreach_unlocked(void (*zfunc)(uma_zone_t, void *), void *);
 279 static void zone_timeout(uma_zone_t zone, void *);
 280 static int hash_alloc(struct uma_hash *, u_int);
 281 static int hash_expand(struct uma_hash *, struct uma_hash *);
 282 static void hash_free(struct uma_hash *hash);
 283 static void uma_timeout(void *);
 284 static void uma_startup3(void);
 285 static void uma_shutdown(void);
 286 static void *zone_alloc_item(uma_zone_t, void *, int, int);
 287 static void zone_free_item(uma_zone_t, void *, void *, enum zfreeskip);
 288 static int zone_alloc_limit(uma_zone_t zone, int count, int flags);
 289 static void zone_free_limit(uma_zone_t zone, int count);
 290 static void bucket_enable(void);
 291 static void bucket_init(void);
 292 static uma_bucket_t bucket_alloc(uma_zone_t zone, void *, int);
 293 static void bucket_free(uma_zone_t zone, uma_bucket_t, void *);
 294 static void bucket_zone_drain(void);
 295 static uma_bucket_t zone_alloc_bucket(uma_zone_t, void *, int, int);
 296 static void *slab_alloc_item(uma_keg_t keg, uma_slab_t slab);
 297 static void slab_free_item(uma_zone_t zone, uma_slab_t slab, void *item);
 298 static uma_keg_t uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit,
 299     uma_fini fini, int align, uint32_t flags);
 300 static int zone_import(void *, void **, int, int, int);
 301 static void zone_release(void *, void **, int);
 302 static bool cache_alloc(uma_zone_t, uma_cache_t, void *, int);
 303 static bool cache_free(uma_zone_t, uma_cache_t, void *, void *, int);
 304
 305 static int sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS);
 306 static int sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS);
 307 static int sysctl_handle_uma_zone_allocs(SYSCTL_HANDLER_ARGS);
 308 static int sysctl_handle_uma_zone_frees(SYSCTL_HANDLER_ARGS);
 309 static int sysctl_handle_uma_zone_flags(SYSCTL_HANDLER_ARGS);
 310 static int sysctl_handle_uma_slab_efficiency(SYSCTL_HANDLER_ARGS);
 311 static int sysctl_handle_uma_zone_items(SYSCTL_HANDLER_ARGS);
 312
 313 static uint64_t uma_zone_get_allocs(uma_zone_t zone);
 314
 315 #ifdef INVARIANTS
 316 static uint64_t uma_keg_get_allocs(uma_keg_t zone);
 317 static inline struct noslabbits *slab_dbg_bits(uma_slab_t slab, uma_keg_t keg);
 318
 319 static bool uma_dbg_kskip(uma_keg_t keg, void *mem);
 320 static bool uma_dbg_zskip(uma_zone_t zone, void *mem);
 321 static void uma_dbg_free(uma_zone_t zone, uma_slab_t slab, void *item);
 322 static void uma_dbg_alloc(uma_zone_t zone, uma_slab_t slab, void *item);
 323
 324 static SYSCTL_NODE(_vm, OID_AUTO, debug, CTLFLAG_RD, 0,
 325     "Memory allocation debugging");
 326
 327 static u_int dbg_divisor = 1;
 328 SYSCTL_UINT(_vm_debug, OID_AUTO, divisor,
 329     CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &dbg_divisor, 0,
 330     "Debug & thrash every this item in memory allocator");
 331
 332 static counter_u64_t uma_dbg_cnt = EARLY_COUNTER;
 333 static counter_u64_t uma_skip_cnt = EARLY_COUNTER;
 334 SYSCTL_COUNTER_U64(_vm_debug, OID_AUTO, trashed, CTLFLAG_RD,
 335     &uma_dbg_cnt, "memory items debugged");
 336 SYSCTL_COUNTER_U64(_vm_debug, OID_AUTO, skipped, CTLFLAG_RD,
 337     &uma_skip_cnt, "memory items skipped, not debugged");
 338 #endif
 339
 340 SYSINIT(uma_startup3, SI_SUB_VM_CONF, SI_ORDER_SECOND, uma_startup3, NULL);
 341
 342 SYSCTL_NODE(_vm, OID_AUTO, uma, CTLFLAG_RW, 0, "Universal Memory Allocator");
 343
 344 SYSCTL_PROC(_vm, OID_AUTO, zone_count, CTLFLAG_RD|CTLFLAG_MPSAFE|CTLTYPE_INT,
 345     0, 0, sysctl_vm_zone_count, "I", "Number of UMA zones");
 346
 347 SYSCTL_PROC(_vm, OID_AUTO, zone_stats, CTLFLAG_RD|CTLFLAG_MPSAFE|CTLTYPE_STRUCT,
 348     0, 0, sysctl_vm_zone_stats, "s,struct uma_type_header", "Zone Stats");
 349
 350 static int zone_warnings = 1;
 351 SYSCTL_INT(_vm, OID_AUTO, zone_warnings, CTLFLAG_RWTUN, &zone_warnings, 0,
 352     "Warn when UMA zones becomes full");
 353
 354 /*
 355  * Select the slab zone for an offpage slab with the given maximum item count.
 356  */
 357 static inline uma_zone_t
 358 slabzone(int ipers)
 359 {
 360
 361         return (slabzones[ipers > SLABZONE0_SETSIZE]);
 362 }
 363
 364 /*
 365  * This routine checks to see whether or not it's safe to enable buckets.
 366  */
 367 static void
 368 bucket_enable(void)
 369 {
 370
 371         KASSERT(booted >= BOOT_KVA, ("Bucket enable before init"));
 372         bucketdisable = vm_page_count_min();
 373 }
 374
 375 /*
 376  * Initialize bucket_zones, the array of zones of buckets of various sizes.
 377  *
 378  * For each zone, calculate the memory required for each bucket, consisting
 379  * of the header and an array of pointers.
 380  */
 381 static void
 382 bucket_init(void)
 383 {
 384         struct uma_bucket_zone *ubz;
 385         int size;
 386
 387         for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++) {
 388                 size = roundup(sizeof(struct uma_bucket), sizeof(void *));
 389                 size += sizeof(void *) * ubz->ubz_entries;
 390                 ubz->ubz_zone = uma_zcreate(ubz->ubz_name, size,
 391                     NULL, NULL, NULL, NULL, UMA_ALIGN_PTR,
 392                     UMA_ZONE_MTXCLASS | UMA_ZFLAG_BUCKET |
 393                     UMA_ZONE_FIRSTTOUCH);
 394         }
 395 }
 396
 397 /*
 398  * Given a desired number of entries for a bucket, return the zone from which
 399  * to allocate the bucket.
 400  */
 401 static struct uma_bucket_zone *
 402 bucket_zone_lookup(int entries)
 403 {
 404         struct uma_bucket_zone *ubz;
 405
 406         for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
 407                 if (ubz->ubz_entries >= entries)
 408                         return (ubz);
 409         ubz--;
 410         return (ubz);
 411 }
 412
 413 static struct uma_bucket_zone *
 414 bucket_zone_max(uma_zone_t zone, int nitems)
 415 {
 416         struct uma_bucket_zone *ubz;
 417         int bpcpu;
 418
 419         bpcpu = 2;
 420         if ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) != 0)
 421                 /* Count the cross-domain bucket. */
 422                 bpcpu++;
 423
 424         for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
 425                 if (ubz->ubz_entries * bpcpu * mp_ncpus > nitems)
 426                         break;
 427         if (ubz == &bucket_zones[0])
 428                 ubz = NULL;
 429         else
 430                 ubz--;
 431         return (ubz);
 432 }
 433
 434 static int
 435 bucket_select(int size)
 436 {
 437         struct uma_bucket_zone *ubz;
 438
 439         ubz = &bucket_zones[0];
 440         if (size > ubz->ubz_maxsize)
 441                 return MAX((ubz->ubz_maxsize * ubz->ubz_entries) / size, 1);
 442
 443         for (; ubz->ubz_entries != 0; ubz++)
 444                 if (ubz->ubz_maxsize < size)
 445                         break;
 446         ubz--;
 447         return (ubz->ubz_entries);
 448 }
 449
 450 static uma_bucket_t
 451 bucket_alloc(uma_zone_t zone, void *udata, int flags)
 452 {
 453         struct uma_bucket_zone *ubz;
 454         uma_bucket_t bucket;
 455
 456         /*
 457          * Don't allocate buckets in low memory situations.
 458          */
 459         if (bucketdisable)
 460                 return (NULL);
 461
 462         /*
 463          * To limit bucket recursion we store the original zone flags
 464          * in a cookie passed via zalloc_arg/zfree_arg.  This allows the
 465          * NOVM flag to persist even through deep recursions.  We also
 466          * store ZFLAG_BUCKET once we have recursed attempting to allocate
 467          * a bucket for a bucket zone so we do not allow infinite bucket
 468          * recursion.  This cookie will even persist to frees of unused
 469          * buckets via the allocation path or bucket allocations in the
 470          * free path.
 471          */
 472         if ((zone->uz_flags & UMA_ZFLAG_BUCKET) == 0)
 473                 udata = (void *)(uintptr_t)zone->uz_flags;
 474         else {
 475                 if ((uintptr_t)udata & UMA_ZFLAG_BUCKET)
 476                         return (NULL);
 477                 udata = (void *)((uintptr_t)udata | UMA_ZFLAG_BUCKET);
 478         }
 479         if ((uintptr_t)udata & UMA_ZFLAG_CACHEONLY)
 480                 flags |= M_NOVM;
 481         ubz = bucket_zone_lookup(zone->uz_bucket_size);
 482         if (ubz->ubz_zone == zone && (ubz + 1)->ubz_entries != 0)
 483                 ubz++;
 484         bucket = uma_zalloc_arg(ubz->ubz_zone, udata, flags);
 485         if (bucket) {
 486 #ifdef INVARIANTS
 487                 bzero(bucket->ub_bucket, sizeof(void *) * ubz->ubz_entries);
 488 #endif
 489                 bucket->ub_cnt = 0;
 490                 bucket->ub_entries = ubz->ubz_entries;
 491         }
 492
 493         return (bucket);
 494 }
 495
 496 static void
 497 bucket_free(uma_zone_t zone, uma_bucket_t bucket, void *udata)
 498 {
 499         struct uma_bucket_zone *ubz;
 500
 501         KASSERT(bucket->ub_cnt == 0,
 502             ("bucket_free: Freeing a non free bucket."));
 503         if ((zone->uz_flags & UMA_ZFLAG_BUCKET) == 0)
 504                 udata = (void *)(uintptr_t)zone->uz_flags;
 505         ubz = bucket_zone_lookup(bucket->ub_entries);
 506         uma_zfree_arg(ubz->ubz_zone, bucket, udata);
 507 }
 508
 509 static void
 510 bucket_zone_drain(void)
 511 {
 512         struct uma_bucket_zone *ubz;
 513
 514         for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
 515                 uma_zone_reclaim(ubz->ubz_zone, UMA_RECLAIM_DRAIN);
 516 }
 517
 518 /*
 519  * Attempt to satisfy an allocation by retrieving a full bucket from one of the
 520  * zone's caches.
 521  */
 522 static uma_bucket_t
 523 zone_fetch_bucket(uma_zone_t zone, uma_zone_domain_t zdom)
 524 {
 525         uma_bucket_t bucket;
 526
 527         ZONE_LOCK_ASSERT(zone);
 528
 529         if ((bucket = TAILQ_FIRST(&zdom->uzd_buckets)) != NULL) {
 530                 MPASS(zdom->uzd_nitems >= bucket->ub_cnt);
 531                 TAILQ_REMOVE(&zdom->uzd_buckets, bucket, ub_link);
 532                 zdom->uzd_nitems -= bucket->ub_cnt;
 533                 if (zdom->uzd_imin > zdom->uzd_nitems)
 534                         zdom->uzd_imin = zdom->uzd_nitems;
 535                 zone->uz_bkt_count -= bucket->ub_cnt;
 536         }
 537         return (bucket);
 538 }
 539
 540 /*
 541  * Insert a full bucket into the specified cache.  The "ws" parameter indicates
 542  * whether the bucket's contents should be counted as part of the zone's working
 543  * set.
 544  */
 545 static void
 546 zone_put_bucket(uma_zone_t zone, uma_zone_domain_t zdom, uma_bucket_t bucket,
 547     const bool ws)
 548 {
 549
 550         ZONE_LOCK_ASSERT(zone);
 551         KASSERT(!ws || zone->uz_bkt_count < zone->uz_bkt_max,
 552             ("%s: zone %p overflow", __func__, zone));
 553
 554         if (ws)
 555                 TAILQ_INSERT_HEAD(&zdom->uzd_buckets, bucket, ub_link);
 556         else
 557                 TAILQ_INSERT_TAIL(&zdom->uzd_buckets, bucket, ub_link);
 558         zdom->uzd_nitems += bucket->ub_cnt;
 559         if (ws && zdom->uzd_imax < zdom->uzd_nitems)
 560                 zdom->uzd_imax = zdom->uzd_nitems;
 561         zone->uz_bkt_count += bucket->ub_cnt;
 562 }
 563
 564 /* Pops an item out of a per-cpu cache bucket. */
 565 static inline void *
 566 cache_bucket_pop(uma_cache_t cache, uma_cache_bucket_t bucket)
 567 {
 568         void *item;
 569
 570         CRITICAL_ASSERT(curthread);
 571
 572         bucket->ucb_cnt--;
 573         item = bucket->ucb_bucket->ub_bucket[bucket->ucb_cnt];
 574 #ifdef INVARIANTS
 575         bucket->ucb_bucket->ub_bucket[bucket->ucb_cnt] = NULL;
 576         KASSERT(item != NULL, ("uma_zalloc: Bucket pointer mangled."));
 577 #endif
 578         cache->uc_allocs++;
 579
 580         return (item);
 581 }
 582
 583 /* Pushes an item into a per-cpu cache bucket. */
 584 static inline void
 585 cache_bucket_push(uma_cache_t cache, uma_cache_bucket_t bucket, void *item)
 586 {
 587
 588         CRITICAL_ASSERT(curthread);
 589         KASSERT(bucket->ucb_bucket->ub_bucket[bucket->ucb_cnt] == NULL,
 590             ("uma_zfree: Freeing to non free bucket index."));
 591
 592         bucket->ucb_bucket->ub_bucket[bucket->ucb_cnt] = item;
 593         bucket->ucb_cnt++;
 594         cache->uc_frees++;
 595 }
 596
 597 /*
 598  * Unload a UMA bucket from a per-cpu cache.
 599  */
 600 static inline uma_bucket_t
 601 cache_bucket_unload(uma_cache_bucket_t bucket)
 602 {
 603         uma_bucket_t b;
 604
 605         b = bucket->ucb_bucket;
 606         if (b != NULL) {
 607                 MPASS(b->ub_entries == bucket->ucb_entries);
 608                 b->ub_cnt = bucket->ucb_cnt;
 609                 bucket->ucb_bucket = NULL;
 610                 bucket->ucb_entries = bucket->ucb_cnt = 0;
 611         }
 612
 613         return (b);
 614 }
 615
 616 static inline uma_bucket_t
 617 cache_bucket_unload_alloc(uma_cache_t cache)
 618 {
 619
 620         return (cache_bucket_unload(&cache->uc_allocbucket));
 621 }
 622
 623 static inline uma_bucket_t
 624 cache_bucket_unload_free(uma_cache_t cache)
 625 {
 626
 627         return (cache_bucket_unload(&cache->uc_freebucket));
 628 }
 629
 630 static inline uma_bucket_t
 631 cache_bucket_unload_cross(uma_cache_t cache)
 632 {
 633
 634         return (cache_bucket_unload(&cache->uc_crossbucket));
 635 }
 636
 637 /*
 638  * Load a bucket into a per-cpu cache bucket.
 639  */
 640 static inline void
 641 cache_bucket_load(uma_cache_bucket_t bucket, uma_bucket_t b)
 642 {
 643
 644         CRITICAL_ASSERT(curthread);
 645         MPASS(bucket->ucb_bucket == NULL);
 646
 647         bucket->ucb_bucket = b;
 648         bucket->ucb_cnt = b->ub_cnt;
 649         bucket->ucb_entries = b->ub_entries;
 650 }
 651
 652 static inline void
 653 cache_bucket_load_alloc(uma_cache_t cache, uma_bucket_t b)
 654 {
 655
 656         cache_bucket_load(&cache->uc_allocbucket, b);
 657 }
 658
 659 static inline void
 660 cache_bucket_load_free(uma_cache_t cache, uma_bucket_t b)
 661 {
 662
 663         cache_bucket_load(&cache->uc_freebucket, b);
 664 }
 665
 666 #ifdef NUMA
 667 static inline void
 668 cache_bucket_load_cross(uma_cache_t cache, uma_bucket_t b)
 669 {
 670
 671         cache_bucket_load(&cache->uc_crossbucket, b);
 672 }
 673 #endif
 674
 675 /*
 676  * Copy and preserve ucb_spare.
 677  */
 678 static inline void
 679 cache_bucket_copy(uma_cache_bucket_t b1, uma_cache_bucket_t b2)
 680 {
 681
 682         b1->ucb_bucket = b2->ucb_bucket;
 683         b1->ucb_entries = b2->ucb_entries;
 684         b1->ucb_cnt = b2->ucb_cnt;
 685 }
 686
 687 /*
 688  * Swap two cache buckets.
 689  */
 690 static inline void
 691 cache_bucket_swap(uma_cache_bucket_t b1, uma_cache_bucket_t b2)
 692 {
 693         struct uma_cache_bucket b3;
 694
 695         CRITICAL_ASSERT(curthread);
 696
 697         cache_bucket_copy(&b3, b1);
 698         cache_bucket_copy(b1, b2);
 699         cache_bucket_copy(b2, &b3);
 700 }
 701
 702 static void
 703 zone_log_warning(uma_zone_t zone)
 704 {
 705         static const struct timeval warninterval = { 300, 0 };
 706
 707         if (!zone_warnings || zone->uz_warning == NULL)
 708                 return;
 709
 710         if (ratecheck(&zone->uz_ratecheck, &warninterval))
 711                 printf("[zone: %s] %s\n", zone->uz_name, zone->uz_warning);
 712 }
 713
 714 static inline void
 715 zone_maxaction(uma_zone_t zone)
 716 {
 717
 718         if (zone->uz_maxaction.ta_func != NULL)
 719                 taskqueue_enqueue(taskqueue_thread, &zone->uz_maxaction);
 720 }
 721
 722 /*
 723  * Routine called by timeout which is used to fire off some time interval
 724  * based calculations.  (stats, hash size, etc.)
 725  *
 726  * Arguments:
 727  *      arg   Unused
 728  *
 729  * Returns:
 730  *      Nothing
 731  */
 732 static void
 733 uma_timeout(void *unused)
 734 {
 735         bucket_enable();
 736         zone_foreach(zone_timeout, NULL);
 737
 738         /* Reschedule this event */
 739         callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
 740 }
 741
 742 /*
 743  * Update the working set size estimate for the zone's bucket cache.
 744  * The constants chosen here are somewhat arbitrary.  With an update period of
 745  * 20s (UMA_TIMEOUT), this estimate is dominated by zone activity over the
 746  * last 100s.
 747  */
 748 static void
 749 zone_domain_update_wss(uma_zone_domain_t zdom)
 750 {
 751         long wss;
 752
 753         MPASS(zdom->uzd_imax >= zdom->uzd_imin);
 754         wss = zdom->uzd_imax - zdom->uzd_imin;
 755         zdom->uzd_imax = zdom->uzd_imin = zdom->uzd_nitems;
 756         zdom->uzd_wss = (4 * wss + zdom->uzd_wss) / 5;
 757 }
 758
 759 /*
 760  * Routine to perform timeout driven calculations.  This expands the
 761  * hashes and does per cpu statistics aggregation.
 762  *
 763  *  Returns nothing.
 764  */
 765 static void
 766 zone_timeout(uma_zone_t zone, void *unused)
 767 {
 768         uma_keg_t keg;
 769         u_int slabs, pages;
 770
 771         if ((zone->uz_flags & UMA_ZFLAG_HASH) == 0)
 772                 goto update_wss;
 773
 774         keg = zone->uz_keg;
 775
 776         /*
 777          * Hash zones are non-numa by definition so the first domain
 778          * is the only one present.
 779          */
 780         KEG_LOCK(keg, 0);
 781         pages = keg->uk_domain[0].ud_pages;
 782
 783         /*
 784          * Expand the keg hash table.
 785          *
 786          * This is done if the number of slabs is larger than the hash size.
 787          * What I'm trying to do here is completely reduce collisions.  This
 788          * may be a little aggressive.  Should I allow for two collisions max?
 789          */
 790         if ((slabs = pages / keg->uk_ppera) > keg->uk_hash.uh_hashsize) {
 791                 struct uma_hash newhash;
 792                 struct uma_hash oldhash;
 793                 int ret;
 794
 795                 /*
 796                  * This is so involved because allocating and freeing
 797                  * while the keg lock is held will lead to deadlock.
 798                  * I have to do everything in stages and check for
 799                  * races.
 800                  */
 801                 KEG_UNLOCK(keg, 0);
 802                 ret = hash_alloc(&newhash, 1 << fls(slabs));
 803                 KEG_LOCK(keg, 0);
 804                 if (ret) {
 805                         if (hash_expand(&keg->uk_hash, &newhash)) {
 806                                 oldhash = keg->uk_hash;
 807                                 keg->uk_hash = newhash;
 808                         } else
 809                                 oldhash = newhash;
 810
 811                         KEG_UNLOCK(keg, 0);
 812                         hash_free(&oldhash);
 813                         goto update_wss;
 814                 }
 815         }
 816         KEG_UNLOCK(keg, 0);
 817
 818 update_wss:
 819         ZONE_LOCK(zone);
 820         for (int i = 0; i < vm_ndomains; i++)
 821                 zone_domain_update_wss(&zone->uz_domain[i]);
 822         ZONE_UNLOCK(zone);
 823 }
 824
 825 /*
 826  * Allocate and zero fill the next sized hash table from the appropriate
 827  * backing store.
 828  *
 829  * Arguments:
 830  *      hash  A new hash structure with the old hash size in uh_hashsize
 831  *
 832  * Returns:
 833  *      1 on success and 0 on failure.
 834  */
 835 static int
 836 hash_alloc(struct uma_hash *hash, u_int size)
 837 {
 838         size_t alloc;
 839
 840         KASSERT(powerof2(size), ("hash size must be power of 2"));
 841         if (size > UMA_HASH_SIZE_INIT)  {
 842                 hash->uh_hashsize = size;
 843                 alloc = sizeof(hash->uh_slab_hash[0]) * hash->uh_hashsize;
 844                 hash->uh_slab_hash = malloc(alloc, M_UMAHASH, M_NOWAIT);
 845         } else {
 846                 alloc = sizeof(hash->uh_slab_hash[0]) * UMA_HASH_SIZE_INIT;
 847                 hash->uh_slab_hash = zone_alloc_item(hashzone, NULL,
 848                     UMA_ANYDOMAIN, M_WAITOK);
 849                 hash->uh_hashsize = UMA_HASH_SIZE_INIT;
 850         }
 851         if (hash->uh_slab_hash) {
 852                 bzero(hash->uh_slab_hash, alloc);
 853                 hash->uh_hashmask = hash->uh_hashsize - 1;
 854                 return (1);
 855         }
 856
 857         return (0);
 858 }
 859
 860 /*
 861  * Expands the hash table for HASH zones.  This is done from zone_timeout
 862  * to reduce collisions.  This must not be done in the regular allocation
 863  * path, otherwise, we can recurse on the vm while allocating pages.
 864  *
 865  * Arguments:
 866  *      oldhash  The hash you want to expand
 867  *      newhash  The hash structure for the new table
 868  *
 869  * Returns:
 870  *      Nothing
 871  *
 872  * Discussion:
 873  */
 874 static int
 875 hash_expand(struct uma_hash *oldhash, struct uma_hash *newhash)
 876 {
 877         uma_hash_slab_t slab;
 878         u_int hval;
 879         u_int idx;
 880
 881         if (!newhash->uh_slab_hash)
 882                 return (0);
 883
 884         if (oldhash->uh_hashsize >= newhash->uh_hashsize)
 885                 return (0);
 886
 887         /*
 888          * I need to investigate hash algorithms for resizing without a
 889          * full rehash.
 890          */
 891
 892         for (idx = 0; idx < oldhash->uh_hashsize; idx++)
 893                 while (!LIST_EMPTY(&oldhash->uh_slab_hash[idx])) {
 894                         slab = LIST_FIRST(&oldhash->uh_slab_hash[idx]);
 895                         LIST_REMOVE(slab, uhs_hlink);
 896                         hval = UMA_HASH(newhash, slab->uhs_data);
 897                         LIST_INSERT_HEAD(&newhash->uh_slab_hash[hval],
 898                             slab, uhs_hlink);
 899                 }
 900
 901         return (1);
 902 }
 903
 904 /*
 905  * Free the hash bucket to the appropriate backing store.
 906  *
 907  * Arguments:
 908  *      slab_hash  The hash bucket we're freeing
 909  *      hashsize   The number of entries in that hash bucket
 910  *
 911  * Returns:
 912  *      Nothing
 913  */
 914 static void
 915 hash_free(struct uma_hash *hash)
 916 {
 917         if (hash->uh_slab_hash == NULL)
 918                 return;
 919         if (hash->uh_hashsize == UMA_HASH_SIZE_INIT)
 920                 zone_free_item(hashzone, hash->uh_slab_hash, NULL, SKIP_NONE);
 921         else
 922                 free(hash->uh_slab_hash, M_UMAHASH);
 923 }
 924
 925 /*
 926  * Frees all outstanding items in a bucket
 927  *
 928  * Arguments:
 929  *      zone   The zone to free to, must be unlocked.
 930  *      bucket The free/alloc bucket with items.
 931  *
 932  * Returns:
 933  *      Nothing
 934  */
 935
 936 static void
 937 bucket_drain(uma_zone_t zone, uma_bucket_t bucket)
 938 {
 939         int i;
 940
 941         if (bucket == NULL || bucket->ub_cnt == 0)
 942                 return;
 943
 944         if (zone->uz_fini)
 945                 for (i = 0; i < bucket->ub_cnt; i++)
 946                         zone->uz_fini(bucket->ub_bucket[i], zone->uz_size);
 947         zone->uz_release(zone->uz_arg, bucket->ub_bucket, bucket->ub_cnt);
 948         if (zone->uz_max_items > 0)
 949                 zone_free_limit(zone, bucket->ub_cnt);
 950         bucket->ub_cnt = 0;
 951 }
 952
 953 /*
 954  * Drains the per cpu caches for a zone.
 955  *
 956  * NOTE: This may only be called while the zone is being torn down, and not
 957  * during normal operation.  This is necessary in order that we do not have
 958  * to migrate CPUs to drain the per-CPU caches.
 959  *
 960  * Arguments:
 961  *      zone     The zone to drain, must be unlocked.
 962  *
 963  * Returns:
 964  *      Nothing
 965  */
 966 static void
 967 cache_drain(uma_zone_t zone)
 968 {
 969         uma_cache_t cache;
 970         uma_bucket_t bucket;
 971         int cpu;
 972
 973         /*
 974          * XXX: It is safe to not lock the per-CPU caches, because we're
 975          * tearing down the zone anyway.  I.e., there will be no further use
 976          * of the caches at this point.
 977          *
 978          * XXX: It would good to be able to assert that the zone is being
 979          * torn down to prevent improper use of cache_drain().
 980          */
 981         CPU_FOREACH(cpu) {
 982                 cache = &zone->uz_cpu[cpu];
 983                 bucket = cache_bucket_unload_alloc(cache);
 984                 if (bucket != NULL) {
 985                         bucket_drain(zone, bucket);
 986                         bucket_free(zone, bucket, NULL);
 987                 }
 988                 bucket = cache_bucket_unload_free(cache);
 989                 if (bucket != NULL) {
 990                         bucket_drain(zone, bucket);
 991                         bucket_free(zone, bucket, NULL);
 992                 }
 993                 bucket = cache_bucket_unload_cross(cache);
 994                 if (bucket != NULL) {
 995                         bucket_drain(zone, bucket);
 996                         bucket_free(zone, bucket, NULL);
 997                 }
 998         }
 999         bucket_cache_reclaim(zone, true);
1000 }
1001
1002 static void
1003 cache_shrink(uma_zone_t zone, void *unused)
1004 {
1005
1006         if (zone->uz_flags & UMA_ZFLAG_INTERNAL)
1007                 return;
1008
1009         ZONE_LOCK(zone);
1010         zone->uz_bucket_size =
1011             (zone->uz_bucket_size_min + zone->uz_bucket_size) / 2;
1012         ZONE_UNLOCK(zone);
1013 }
1014
1015 static void
1016 cache_drain_safe_cpu(uma_zone_t zone, void *unused)
1017 {
1018         uma_cache_t cache;
1019         uma_bucket_t b1, b2, b3;
1020         int domain;
1021
1022         if (zone->uz_flags & UMA_ZFLAG_INTERNAL)
1023                 return;
1024
1025         b1 = b2 = b3 = NULL;
1026         ZONE_LOCK(zone);
1027         critical_enter();
1028         if (zone->uz_flags & UMA_ZONE_FIRSTTOUCH)
1029                 domain = PCPU_GET(domain);
1030         else
1031                 domain = 0;
1032         cache = &zone->uz_cpu[curcpu];
1033         b1 = cache_bucket_unload_alloc(cache);
1034         if (b1 != NULL && b1->ub_cnt != 0) {
1035                 zone_put_bucket(zone, &zone->uz_domain[domain], b1, false);
1036                 b1 = NULL;
1037         }
1038         b2 = cache_bucket_unload_free(cache);
1039         if (b2 != NULL && b2->ub_cnt != 0) {
1040                 zone_put_bucket(zone, &zone->uz_domain[domain], b2, false);
1041                 b2 = NULL;
1042         }
1043         b3 = cache_bucket_unload_cross(cache);
1044         critical_exit();
1045         ZONE_UNLOCK(zone);
1046         if (b1)
1047                 bucket_free(zone, b1, NULL);
1048         if (b2)
1049                 bucket_free(zone, b2, NULL);
1050         if (b3) {
1051                 bucket_drain(zone, b3);
1052                 bucket_free(zone, b3, NULL);
1053         }
1054 }
1055
1056 /*
1057  * Safely drain per-CPU caches of a zone(s) to alloc bucket.
1058  * This is an expensive call because it needs to bind to all CPUs
1059  * one by one and enter a critical section on each of them in order
1060  * to safely access their cache buckets.
1061  * Zone lock must not be held on call this function.
1062  */
1063 static void
1064 pcpu_cache_drain_safe(uma_zone_t zone)
1065 {
1066         int cpu;
1067
1068         /*
1069          * Polite bucket sizes shrinking was not enough, shrink aggressively.
1070          */
1071         if (zone)
1072                 cache_shrink(zone, NULL);
1073         else
1074                 zone_foreach(cache_shrink, NULL);
1075
1076         CPU_FOREACH(cpu) {
1077                 thread_lock(curthread);
1078                 sched_bind(curthread, cpu);
1079                 thread_unlock(curthread);
1080
1081                 if (zone)
1082                         cache_drain_safe_cpu(zone, NULL);
1083                 else
1084                         zone_foreach(cache_drain_safe_cpu, NULL);
1085         }
1086         thread_lock(curthread);
1087         sched_unbind(curthread);
1088         thread_unlock(curthread);
1089 }
1090
1091 /*
1092  * Reclaim cached buckets from a zone.  All buckets are reclaimed if the caller
1093  * requested a drain, otherwise the per-domain caches are trimmed to either
1094  * estimated working set size.
1095  */
1096 static void
1097 bucket_cache_reclaim(uma_zone_t zone, bool drain)
1098 {
1099         uma_zone_domain_t zdom;
1100         uma_bucket_t bucket;
1101         long target, tofree;
1102         int i;
1103
1104         for (i = 0; i < vm_ndomains; i++) {
1105                 /*
1106                  * The cross bucket is partially filled and not part of
1107                  * the item count.  Reclaim it individually here.
1108                  */
1109                 zdom = &zone->uz_domain[i];
1110                 ZONE_CROSS_LOCK(zone);
1111                 bucket = zdom->uzd_cross;
1112                 zdom->uzd_cross = NULL;
1113                 ZONE_CROSS_UNLOCK(zone);
1114                 if (bucket != NULL) {
1115                         bucket_drain(zone, bucket);
1116                         bucket_free(zone, bucket, NULL);
1117                 }
1118
1119                 /*
1120                  * Shrink the zone bucket size to ensure that the per-CPU caches
1121                  * don't grow too large.
1122                  */
1123                 ZONE_LOCK(zone);
1124                 if (i == 0 && zone->uz_bucket_size > zone->uz_bucket_size_min)
1125                         zone->uz_bucket_size--;
1126
1127                 /*
1128                  * If we were asked to drain the zone, we are done only once
1129                  * this bucket cache is empty.  Otherwise, we reclaim items in
1130                  * excess of the zone's estimated working set size.  If the
1131                  * difference nitems - imin is larger than the WSS estimate,
1132                  * then the estimate will grow at the end of this interval and
1133                  * we ignore the historical average.
1134                  */
1135                 target = drain ? 0 : lmax(zdom->uzd_wss, zdom->uzd_nitems -
1136                     zdom->uzd_imin);
1137                 while (zdom->uzd_nitems > target) {
1138                         bucket = TAILQ_LAST(&zdom->uzd_buckets, uma_bucketlist);
1139                         if (bucket == NULL)
1140                                 break;
1141                         tofree = bucket->ub_cnt;
1142                         TAILQ_REMOVE(&zdom->uzd_buckets, bucket, ub_link);
1143                         zdom->uzd_nitems -= tofree;
1144
1145                         /*
1146                          * Shift the bounds of the current WSS interval to avoid
1147                          * perturbing the estimate.
1148                          */
1149                         zdom->uzd_imax -= lmin(zdom->uzd_imax, tofree);
1150                         zdom->uzd_imin -= lmin(zdom->uzd_imin, tofree);
1151
1152                         ZONE_UNLOCK(zone);
1153                         bucket_drain(zone, bucket);
1154                         bucket_free(zone, bucket, NULL);
1155                         ZONE_LOCK(zone);
1156                 }
1157                 ZONE_UNLOCK(zone);
1158         }
1159 }
1160
1161 static void
1162 keg_free_slab(uma_keg_t keg, uma_slab_t slab, int start)
1163 {
1164         uint8_t *mem;
1165         int i;
1166         uint8_t flags;
1167
1168         CTR4(KTR_UMA, "keg_free_slab keg %s(%p) slab %p, returning %d bytes",
1169             keg->uk_name, keg, slab, PAGE_SIZE * keg->uk_ppera);
1170
1171         mem = slab_data(slab, keg);
1172         flags = slab->us_flags;
1173         i = start;
1174         if (keg->uk_fini != NULL) {
1175                 for (i--; i > -1; i--)
1176 #ifdef INVARIANTS
1177                 /*
1178                  * trash_fini implies that dtor was trash_dtor. trash_fini
1179                  * would check that memory hasn't been modified since free,
1180                  * which executed trash_dtor.
1181                  * That's why we need to run uma_dbg_kskip() check here,
1182                  * albeit we don't make skip check for other init/fini
1183                  * invocations.
1184                  */
1185                 if (!uma_dbg_kskip(keg, slab_item(slab, keg, i)) ||
1186                     keg->uk_fini != trash_fini)
1187 #endif
1188                         keg->uk_fini(slab_item(slab, keg, i), keg->uk_size);
1189         }
1190         if (keg->uk_flags & UMA_ZFLAG_OFFPAGE)
1191                 zone_free_item(slabzone(keg->uk_ipers), slab_tohashslab(slab),
1192                     NULL, SKIP_NONE);
1193         keg->uk_freef(mem, PAGE_SIZE * keg->uk_ppera, flags);
1194         uma_total_dec(PAGE_SIZE * keg->uk_ppera);
1195 }
1196
1197 /*
1198  * Frees pages from a keg back to the system.  This is done on demand from
1199  * the pageout daemon.
1200  *
1201  * Returns nothing.
1202  */
1203 static void
1204 keg_drain(uma_keg_t keg)
1205 {
1206         struct slabhead freeslabs = { 0 };
1207         uma_domain_t dom;
1208         uma_slab_t slab, tmp;
1209         int i, n;
1210
1211         /*
1212          * We don't want to take pages from statically allocated kegs at this
1213          * time
1214          */
1215         if (keg->uk_flags & UMA_ZONE_NOFREE || keg->uk_freef == NULL)
1216                 return;
1217
1218         for (i = 0; i < vm_ndomains; i++) {
1219                 CTR4(KTR_UMA, "keg_drain %s(%p) domain %d free items: %u",
1220                     keg->uk_name, keg, i, dom->ud_free);
1221                 n = 0;
1222                 dom = &keg->uk_domain[i];
1223                 KEG_LOCK(keg, i);
1224                 LIST_FOREACH_SAFE(slab, &dom->ud_free_slab, us_link, tmp) {
1225                         if (keg->uk_flags & UMA_ZFLAG_HASH)
1226                                 UMA_HASH_REMOVE(&keg->uk_hash, slab);
1227                         n++;
1228                         LIST_REMOVE(slab, us_link);
1229                         LIST_INSERT_HEAD(&freeslabs, slab, us_link);
1230                 }
1231                 dom->ud_pages -= n * keg->uk_ppera;
1232                 dom->ud_free -= n * keg->uk_ipers;
1233                 KEG_UNLOCK(keg, i);
1234         }
1235
1236         while ((slab = LIST_FIRST(&freeslabs)) != NULL) {
1237                 LIST_REMOVE(slab, us_link);
1238                 keg_free_slab(keg, slab, keg->uk_ipers);
1239         }
1240 }
1241
1242 static void
1243 zone_reclaim(uma_zone_t zone, int waitok, bool drain)
1244 {
1245
1246         /*
1247          * Set draining to interlock with zone_dtor() so we can release our
1248          * locks as we go.  Only dtor() should do a WAITOK call since it
1249          * is the only call that knows the structure will still be available
1250          * when it wakes up.
1251          */
1252         ZONE_LOCK(zone);
1253         while (zone->uz_flags & UMA_ZFLAG_RECLAIMING) {
1254                 if (waitok == M_NOWAIT)
1255                         goto out;
1256                 msleep(zone, &zone->uz_lock, PVM, "zonedrain", 1);
1257         }
1258         zone->uz_flags |= UMA_ZFLAG_RECLAIMING;
1259         ZONE_UNLOCK(zone);
1260         bucket_cache_reclaim(zone, drain);
1261
1262         /*
1263          * The DRAINING flag protects us from being freed while
1264          * we're running.  Normally the uma_rwlock would protect us but we
1265          * must be able to release and acquire the right lock for each keg.
1266          */
1267         if ((zone->uz_flags & UMA_ZFLAG_CACHE) == 0)
1268                 keg_drain(zone->uz_keg);
1269         ZONE_LOCK(zone);
1270         zone->uz_flags &= ~UMA_ZFLAG_RECLAIMING;
1271         wakeup(zone);
1272 out:
1273         ZONE_UNLOCK(zone);
1274 }
1275
1276 static void
1277 zone_drain(uma_zone_t zone, void *unused)
1278 {
1279
1280         zone_reclaim(zone, M_NOWAIT, true);
1281 }
1282
1283 static void
1284 zone_trim(uma_zone_t zone, void *unused)
1285 {
1286
1287         zone_reclaim(zone, M_NOWAIT, false);
1288 }
1289
1290 /*
1291  * Allocate a new slab for a keg and inserts it into the partial slab list.
1292  * The keg should be unlocked on entry.  If the allocation succeeds it will
1293  * be locked on return.
1294  *
1295  * Arguments:
1296  *      flags   Wait flags for the item initialization routine
1297  *      aflags  Wait flags for the slab allocation
1298  *
1299  * Returns:
1300  *      The slab that was allocated or NULL if there is no memory and the
1301  *      caller specified M_NOWAIT.
1302  */
1303 static uma_slab_t
1304 keg_alloc_slab(uma_keg_t keg, uma_zone_t zone, int domain, int flags,
1305     int aflags)
1306 {
1307         uma_domain_t dom;
1308         uma_alloc allocf;
1309         uma_slab_t slab;
1310         unsigned long size;
1311         uint8_t *mem;
1312         uint8_t sflags;
1313         int i;
1314
1315         KASSERT(domain >= 0 && domain < vm_ndomains,
1316             ("keg_alloc_slab: domain %d out of range", domain));
1317
1318         allocf = keg->uk_allocf;
1319         slab = NULL;
1320         mem = NULL;
1321         if (keg->uk_flags & UMA_ZFLAG_OFFPAGE) {
1322                 uma_hash_slab_t hslab;
1323                 hslab = zone_alloc_item(slabzone(keg->uk_ipers), NULL,
1324                     domain, aflags);
1325                 if (hslab == NULL)
1326                         goto fail;
1327                 slab = &hslab->uhs_slab;
1328         }
1329
1330         /*
1331          * This reproduces the old vm_zone behavior of zero filling pages the
1332          * first time they are added to a zone.
1333          *
1334          * Malloced items are zeroed in uma_zalloc.
1335          */
1336
1337         if ((keg->uk_flags & UMA_ZONE_MALLOC) == 0)
1338                 aflags |= M_ZERO;
1339         else
1340                 aflags &= ~M_ZERO;
1341
1342         if (keg->uk_flags & UMA_ZONE_NODUMP)
1343                 aflags |= M_NODUMP;
1344
1345         /* zone is passed for legacy reasons. */
1346         size = keg->uk_ppera * PAGE_SIZE;
1347         mem = allocf(zone, size, domain, &sflags, aflags);
1348         if (mem == NULL) {
1349                 if (keg->uk_flags & UMA_ZFLAG_OFFPAGE)
1350                         zone_free_item(slabzone(keg->uk_ipers),
1351                             slab_tohashslab(slab), NULL, SKIP_NONE);
1352                 goto fail;
1353         }
1354         uma_total_inc(size);
1355
1356         /* For HASH zones all pages go to the same uma_domain. */
1357         if ((keg->uk_flags & UMA_ZFLAG_HASH) != 0)
1358                 domain = 0;
1359
1360         /* Point the slab into the allocated memory */
1361         if (!(keg->uk_flags & UMA_ZFLAG_OFFPAGE))
1362                 slab = (uma_slab_t )(mem + keg->uk_pgoff);
1363         else
1364                 slab_tohashslab(slab)->uhs_data = mem;
1365
1366         if (keg->uk_flags & UMA_ZFLAG_VTOSLAB)
1367                 for (i = 0; i < keg->uk_ppera; i++)
1368                         vsetzoneslab((vm_offset_t)mem + (i * PAGE_SIZE),
1369                             zone, slab);
1370
1371         slab->us_freecount = keg->uk_ipers;
1372         slab->us_flags = sflags;
1373         slab->us_domain = domain;
1374
1375         BIT_FILL(keg->uk_ipers, &slab->us_free);
1376 #ifdef INVARIANTS
1377         BIT_ZERO(keg->uk_ipers, slab_dbg_bits(slab, keg));
1378 #endif
1379
1380         if (keg->uk_init != NULL) {
1381                 for (i = 0; i < keg->uk_ipers; i++)
1382                         if (keg->uk_init(slab_item(slab, keg, i),
1383                             keg->uk_size, flags) != 0)
1384                                 break;
1385                 if (i != keg->uk_ipers) {
1386                         keg_free_slab(keg, slab, i);
1387                         goto fail;
1388                 }
1389         }
1390         KEG_LOCK(keg, domain);
1391
1392         CTR3(KTR_UMA, "keg_alloc_slab: allocated slab %p for %s(%p)",
1393             slab, keg->uk_name, keg);
1394
1395         if (keg->uk_flags & UMA_ZFLAG_HASH)
1396                 UMA_HASH_INSERT(&keg->uk_hash, slab, mem);
1397
1398         /*
1399          * If we got a slab here it's safe to mark it partially used
1400          * and return.  We assume that the caller is going to remove
1401          * at least one item.
1402          */
1403         dom = &keg->uk_domain[domain];
1404         LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
1405         dom->ud_pages += keg->uk_ppera;
1406         dom->ud_free += keg->uk_ipers;
1407
1408         return (slab);
1409
1410 fail:
1411         return (NULL);
1412 }
1413
1414 /*
1415  * This function is intended to be used early on in place of page_alloc() so
1416  * that we may use the boot time page cache to satisfy allocations before
1417  * the VM is ready.
1418  */
1419 static void *
1420 startup_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
1421     int wait)
1422 {
1423         vm_paddr_t pa;
1424         vm_page_t m;
1425         void *mem;
1426         int pages;
1427         int i;
1428
1429         pages = howmany(bytes, PAGE_SIZE);
1430         KASSERT(pages > 0, ("%s can't reserve 0 pages", __func__));
1431
1432         *pflag = UMA_SLAB_BOOT;
1433         m = vm_page_alloc_contig_domain(NULL, 0, domain,
1434             malloc2vm_flags(wait) | VM_ALLOC_NOOBJ | VM_ALLOC_WIRED, pages,
1435             (vm_paddr_t)0, ~(vm_paddr_t)0, 1, 0, VM_MEMATTR_DEFAULT);
1436         if (m == NULL)
1437                 return (NULL);
1438
1439         pa = VM_PAGE_TO_PHYS(m);
1440         for (i = 0; i < pages; i++, pa += PAGE_SIZE) {
1441 #if defined(__aarch64__) || defined(__amd64__) || defined(__mips__) || \
1442     defined(__riscv) || defined(__powerpc64__)
1443                 if ((wait & M_NODUMP) == 0)
1444                         dump_add_page(pa);
1445 #endif
1446         }
1447         /* Allocate KVA and indirectly advance bootmem. */
1448         mem = (void *)pmap_map(&bootmem, m->phys_addr,
1449             m->phys_addr + (pages * PAGE_SIZE), VM_PROT_READ | VM_PROT_WRITE);
1450         if ((wait & M_ZERO) != 0)
1451                 bzero(mem, pages * PAGE_SIZE);
1452
1453         return (mem);
1454 }
1455
1456 static void
1457 startup_free(void *mem, vm_size_t bytes)
1458 {
1459         vm_offset_t va;
1460         vm_page_t m;
1461
1462         va = (vm_offset_t)mem;
1463         m = PHYS_TO_VM_PAGE(pmap_kextract(va));
1464         pmap_remove(kernel_pmap, va, va + bytes);
1465         for (; bytes != 0; bytes -= PAGE_SIZE, m++) {
1466 #if defined(__aarch64__) || defined(__amd64__) || defined(__mips__) || \
1467     defined(__riscv) || defined(__powerpc64__)
1468                 dump_drop_page(VM_PAGE_TO_PHYS(m));
1469 #endif
1470                 vm_page_unwire_noq(m);
1471                 vm_page_free(m);
1472         }
1473 }
1474
1475 /*
1476  * Allocates a number of pages from the system
1477  *
1478  * Arguments:
1479  *      bytes  The number of bytes requested
1480  *      wait  Shall we wait?
1481  *
1482  * Returns:
1483  *      A pointer to the alloced memory or possibly
1484  *      NULL if M_NOWAIT is set.
1485  */
1486 static void *
1487 page_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
1488     int wait)
1489 {
1490         void *p;        /* Returned page */
1491
1492         *pflag = UMA_SLAB_KERNEL;
1493         p = (void *)kmem_malloc_domainset(DOMAINSET_FIXED(domain), bytes, wait);
1494
1495         return (p);
1496 }
1497
1498 static void *
1499 pcpu_page_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
1500     int wait)
1501 {
1502         struct pglist alloctail;
1503         vm_offset_t addr, zkva;
1504         int cpu, flags;
1505         vm_page_t p, p_next;
1506 #ifdef NUMA
1507         struct pcpu *pc;
1508 #endif
1509
1510         MPASS(bytes == (mp_maxid + 1) * PAGE_SIZE);
1511
1512         TAILQ_INIT(&alloctail);
1513         flags = VM_ALLOC_SYSTEM | VM_ALLOC_WIRED | VM_ALLOC_NOOBJ |
1514             malloc2vm_flags(wait);
1515         *pflag = UMA_SLAB_KERNEL;
1516         for (cpu = 0; cpu <= mp_maxid; cpu++) {
1517                 if (CPU_ABSENT(cpu)) {
1518                         p = vm_page_alloc(NULL, 0, flags);
1519                 } else {
1520 #ifndef NUMA
1521                         p = vm_page_alloc(NULL, 0, flags);
1522 #else
1523                         pc = pcpu_find(cpu);
1524                         if (__predict_false(VM_DOMAIN_EMPTY(pc->pc_domain)))
1525                                 p = NULL;
1526                         else
1527                                 p = vm_page_alloc_domain(NULL, 0,
1528                                     pc->pc_domain, flags);
1529                         if (__predict_false(p == NULL))
1530                                 p = vm_page_alloc(NULL, 0, flags);
1531 #endif
1532                 }
1533                 if (__predict_false(p == NULL))
1534                         goto fail;
1535                 TAILQ_INSERT_TAIL(&alloctail, p, listq);
1536         }
1537         if ((addr = kva_alloc(bytes)) == 0)
1538                 goto fail;
1539         zkva = addr;
1540         TAILQ_FOREACH(p, &alloctail, listq) {
1541                 pmap_qenter(zkva, &p, 1);
1542                 zkva += PAGE_SIZE;
1543         }
1544         return ((void*)addr);
1545 fail:
1546         TAILQ_FOREACH_SAFE(p, &alloctail, listq, p_next) {
1547                 vm_page_unwire_noq(p);
1548                 vm_page_free(p);
1549         }
1550         return (NULL);
1551 }
1552
1553 /*
1554  * Allocates a number of pages from within an object
1555  *
1556  * Arguments:
1557  *      bytes  The number of bytes requested
1558  *      wait   Shall we wait?
1559  *
1560  * Returns:
1561  *      A pointer to the alloced memory or possibly
1562  *      NULL if M_NOWAIT is set.
1563  */
1564 static void *
1565 noobj_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *flags,
1566     int wait)
1567 {
1568         TAILQ_HEAD(, vm_page) alloctail;
1569         u_long npages;
1570         vm_offset_t retkva, zkva;
1571         vm_page_t p, p_next;
1572         uma_keg_t keg;
1573
1574         TAILQ_INIT(&alloctail);
1575         keg = zone->uz_keg;
1576
1577         npages = howmany(bytes, PAGE_SIZE);
1578         while (npages > 0) {
1579                 p = vm_page_alloc_domain(NULL, 0, domain, VM_ALLOC_INTERRUPT |
1580                     VM_ALLOC_WIRED | VM_ALLOC_NOOBJ |
1581                     ((wait & M_WAITOK) != 0 ? VM_ALLOC_WAITOK :
1582                     VM_ALLOC_NOWAIT));
1583                 if (p != NULL) {
1584                         /*
1585                          * Since the page does not belong to an object, its
1586                          * listq is unused.
1587                          */
1588                         TAILQ_INSERT_TAIL(&alloctail, p, listq);
1589                         npages--;
1590                         continue;
1591                 }
1592                 /*
1593                  * Page allocation failed, free intermediate pages and
1594                  * exit.
1595                  */
1596                 TAILQ_FOREACH_SAFE(p, &alloctail, listq, p_next) {
1597                         vm_page_unwire_noq(p);
1598                         vm_page_free(p);
1599                 }
1600                 return (NULL);
1601         }
1602         *flags = UMA_SLAB_PRIV;
1603         zkva = keg->uk_kva +
1604             atomic_fetchadd_long(&keg->uk_offset, round_page(bytes));
1605         retkva = zkva;
1606         TAILQ_FOREACH(p, &alloctail, listq) {
1607                 pmap_qenter(zkva, &p, 1);
1608                 zkva += PAGE_SIZE;
1609         }
1610
1611         return ((void *)retkva);
1612 }
1613
1614 /*
1615  * Frees a number of pages to the system
1616  *
1617  * Arguments:
1618  *      mem   A pointer to the memory to be freed
1619  *      size  The size of the memory being freed
1620  *      flags The original p->us_flags field
1621  *
1622  * Returns:
1623  *      Nothing
1624  */
1625 static void
1626 page_free(void *mem, vm_size_t size, uint8_t flags)
1627 {
1628
1629         if ((flags & UMA_SLAB_BOOT) != 0) {
1630                 startup_free(mem, size);
1631                 return;
1632         }
1633
1634         if ((flags & UMA_SLAB_KERNEL) == 0)
1635                 panic("UMA: page_free used with invalid flags %x", flags);
1636
1637         kmem_free((vm_offset_t)mem, size);
1638 }
1639
1640 /*
1641  * Frees pcpu zone allocations
1642  *
1643  * Arguments:
1644  *      mem   A pointer to the memory to be freed
1645  *      size  The size of the memory being freed
1646  *      flags The original p->us_flags field
1647  *
1648  * Returns:
1649  *      Nothing
1650  */
1651 static void
1652 pcpu_page_free(void *mem, vm_size_t size, uint8_t flags)
1653 {
1654         vm_offset_t sva, curva;
1655         vm_paddr_t paddr;
1656         vm_page_t m;
1657
1658         MPASS(size == (mp_maxid+1)*PAGE_SIZE);
1659         sva = (vm_offset_t)mem;
1660         for (curva = sva; curva < sva + size; curva += PAGE_SIZE) {
1661                 paddr = pmap_kextract(curva);
1662                 m = PHYS_TO_VM_PAGE(paddr);
1663                 vm_page_unwire_noq(m);
1664                 vm_page_free(m);
1665         }
1666         pmap_qremove(sva, size >> PAGE_SHIFT);
1667         kva_free(sva, size);
1668 }
1669
1670
1671 /*
1672  * Zero fill initializer
1673  *
1674  * Arguments/Returns follow uma_init specifications
1675  */
1676 static int
1677 zero_init(void *mem, int size, int flags)
1678 {
1679         bzero(mem, size);
1680         return (0);
1681 }
1682
1683 #ifdef INVARIANTS
1684 struct noslabbits *
1685 slab_dbg_bits(uma_slab_t slab, uma_keg_t keg)
1686 {
1687
1688         return ((void *)((char *)&slab->us_free + BITSET_SIZE(keg->uk_ipers)));
1689 }
1690 #endif
1691
1692 /*
1693  * Actual size of embedded struct slab (!OFFPAGE).
1694  */
1695 size_t
1696 slab_sizeof(int nitems)
1697 {
1698         size_t s;
1699
1700         s = sizeof(struct uma_slab) + BITSET_SIZE(nitems) * SLAB_BITSETS;
1701         return (roundup(s, UMA_ALIGN_PTR + 1));
1702 }
1703
1704 /*
1705  * Size of memory for embedded slabs (!OFFPAGE).
1706  */
1707 size_t
1708 slab_space(int nitems)
1709 {
1710         return (UMA_SLAB_SIZE - slab_sizeof(nitems));
1711 }
1712
1713 #define UMA_FIXPT_SHIFT 31
1714 #define UMA_FRAC_FIXPT(n, d)                                            \
1715         ((uint32_t)(((uint64_t)(n) << UMA_FIXPT_SHIFT) / (d)))
1716 #define UMA_FIXPT_PCT(f)                                                \
1717         ((u_int)(((uint64_t)100 * (f)) >> UMA_FIXPT_SHIFT))
1718 #define UMA_PCT_FIXPT(pct)      UMA_FRAC_FIXPT((pct), 100)
1719 #define UMA_MIN_EFF     UMA_PCT_FIXPT(100 - UMA_MAX_WASTE)
1720
1721 /*
1722  * Compute the number of items that will fit in a slab.  If hdr is true, the
1723  * item count may be limited to provide space in the slab for an inline slab
1724  * header.  Otherwise, all slab space will be provided for item storage.
1725  */
1726 static u_int
1727 slab_ipers_hdr(u_int size, u_int rsize, u_int slabsize, bool hdr)
1728 {
1729         u_int ipers;
1730         u_int padpi;
1731
1732         /* The padding between items is not needed after the last item. */
1733         padpi = rsize - size;
1734
1735         if (hdr) {
1736                 /*
1737                  * Start with the maximum item count and remove items until
1738                  * the slab header first alongside the allocatable memory.
1739                  */
1740                 for (ipers = MIN(SLAB_MAX_SETSIZE,
1741                     (slabsize + padpi - slab_sizeof(1)) / rsize);
1742                     ipers > 0 &&
1743                     ipers * rsize - padpi + slab_sizeof(ipers) > slabsize;
1744                     ipers--)
1745                         continue;
1746         } else {
1747                 ipers = MIN((slabsize + padpi) / rsize, SLAB_MAX_SETSIZE);
1748         }
1749
1750         return (ipers);
1751 }
1752
1753 /*
1754  * Compute the number of items that will fit in a slab for a startup zone.
1755  */
1756 int
1757 slab_ipers(size_t size, int align)
1758 {
1759         int rsize;
1760
1761         rsize = roundup(size, align + 1); /* Assume no CACHESPREAD */
1762         return (slab_ipers_hdr(size, rsize, UMA_SLAB_SIZE, true));
1763 }
1764
1765 /*
1766  * Determine the format of a uma keg.  This determines where the slab header
1767  * will be placed (inline or offpage) and calculates ipers, rsize, and ppera.
1768  *
1769  * Arguments
1770  *      keg  The zone we should initialize
1771  *
1772  * Returns
1773  *      Nothing
1774  */
1775 static void
1776 keg_layout(uma_keg_t keg)
1777 {
1778         u_int alignsize;
1779         u_int eff;
1780         u_int eff_offpage;
1781         u_int format;
1782         u_int ipers;
1783         u_int ipers_offpage;
1784         u_int pages;
1785         u_int rsize;
1786         u_int slabsize;
1787
1788         KASSERT((keg->uk_flags & UMA_ZONE_PCPU) == 0 ||
1789             (keg->uk_size <= UMA_PCPU_ALLOC_SIZE &&
1790              (keg->uk_flags & UMA_ZONE_CACHESPREAD) == 0),
1791             ("%s: cannot configure for PCPU: keg=%s, size=%u, flags=0x%b",
1792              __func__, keg->uk_name, keg->uk_size, keg->uk_flags,
1793              PRINT_UMA_ZFLAGS));
1794         KASSERT((keg->uk_flags &
1795             (UMA_ZFLAG_INTERNAL | UMA_ZFLAG_CACHEONLY)) == 0 ||
1796             (keg->uk_flags & (UMA_ZONE_NOTOUCH | UMA_ZONE_PCPU)) == 0,
1797             ("%s: incompatible flags 0x%b", __func__, keg->uk_flags,
1798              PRINT_UMA_ZFLAGS));
1799
1800         alignsize = keg->uk_align + 1;
1801         format = 0;
1802         ipers = 0;
1803
1804         /*
1805          * Calculate the size of each allocation (rsize) according to
1806          * alignment.  If the requested size is smaller than we have
1807          * allocation bits for we round it up.
1808          */
1809         rsize = MAX(keg->uk_size, UMA_SMALLEST_UNIT);
1810         rsize = roundup2(rsize, alignsize);
1811
1812         if ((keg->uk_flags & UMA_ZONE_PCPU) != 0) {
1813                 slabsize = UMA_PCPU_ALLOC_SIZE;
1814                 pages = mp_maxid + 1;
1815         } else if ((keg->uk_flags & UMA_ZONE_CACHESPREAD) != 0) {
1816                 /*
1817                  * We want one item to start on every align boundary in a page.
1818                  * To do this we will span pages.  We will also extend the item
1819                  * by the size of align if it is an even multiple of align.
1820                  * Otherwise, it would fall on the same boundary every time.
1821                  */
1822                 if ((rsize & alignsize) == 0)
1823                         rsize += alignsize;
1824                 slabsize = rsize * (PAGE_SIZE / alignsize);
1825                 slabsize = MIN(slabsize, rsize * SLAB_MAX_SETSIZE);
1826                 slabsize = MIN(slabsize, UMA_CACHESPREAD_MAX_SIZE);
1827                 pages = howmany(slabsize, PAGE_SIZE);
1828                 slabsize = ptoa(pages);
1829         } else {
1830                 /*
1831                  * Choose a slab size of as many pages as it takes to represent
1832                  * a single item.  We will then try to fit as many additional
1833                  * items into the slab as possible.  At some point, we may want
1834                  * to increase the slab size for awkward item sizes in order to
1835                  * increase efficiency.
1836                  */
1837                 pages = howmany(keg->uk_size, PAGE_SIZE);
1838                 slabsize = ptoa(pages);
1839         }
1840
1841         /* Evaluate an inline slab layout. */
1842         if ((keg->uk_flags & (UMA_ZONE_NOTOUCH | UMA_ZONE_PCPU)) == 0)
1843                 ipers = slab_ipers_hdr(keg->uk_size, rsize, slabsize, true);
1844
1845         /* TODO: vm_page-embedded slab. */
1846
1847         /*
1848          * We can't do OFFPAGE if we're internal or if we've been
1849          * asked to not go to the VM for buckets.  If we do this we
1850          * may end up going to the VM  for slabs which we do not
1851          * want to do if we're UMA_ZFLAG_CACHEONLY as a result
1852          * of UMA_ZONE_VM, which clearly forbids it.
1853          */
1854         if ((keg->uk_flags &
1855             (UMA_ZFLAG_INTERNAL | UMA_ZFLAG_CACHEONLY)) != 0) {
1856                 if (ipers == 0) {
1857                         /* We need an extra page for the slab header. */
1858                         pages++;
1859                         slabsize = ptoa(pages);
1860                         ipers = slab_ipers_hdr(keg->uk_size, rsize, slabsize,
1861                             true);
1862                 }
1863                 goto out;
1864         }
1865
1866         /*
1867          * See if using an OFFPAGE slab will improve our efficiency.
1868          * Only do this if we are below our efficiency threshold.
1869          *
1870          * XXX We could try growing slabsize to limit max waste as well.
1871          * Historically this was not done because the VM could not
1872          * efficiently handle contiguous allocations.
1873          */
1874         eff = UMA_FRAC_FIXPT(ipers * rsize, slabsize);
1875         ipers_offpage = slab_ipers_hdr(keg->uk_size, rsize, slabsize, false);
1876         eff_offpage = UMA_FRAC_FIXPT(ipers_offpage * rsize,
1877             slabsize + slabzone(ipers_offpage)->uz_keg->uk_rsize);
1878         if (ipers == 0 || (eff < UMA_MIN_EFF && eff < eff_offpage)) {
1879                 CTR5(KTR_UMA, "UMA decided we need offpage slab headers for "
1880                     "keg: %s(%p), minimum efficiency allowed = %u%%, "
1881                     "old efficiency = %u%%, offpage efficiency = %u%%",
1882                     keg->uk_name, keg, UMA_FIXPT_PCT(UMA_MIN_EFF),
1883                     UMA_FIXPT_PCT(eff), UMA_FIXPT_PCT(eff_offpage));
1884                 format = UMA_ZFLAG_OFFPAGE;
1885                 ipers = ipers_offpage;
1886         }
1887
1888 out:
1889         /*
1890          * How do we find the slab header if it is offpage or if not all item
1891          * start addresses are in the same page?  We could solve the latter
1892          * case with vaddr alignment, but we don't.
1893          */
1894         if ((format & UMA_ZFLAG_OFFPAGE) != 0 ||
1895             (ipers - 1) * rsize >= PAGE_SIZE) {
1896                 if ((keg->uk_flags & UMA_ZONE_NOTPAGE) != 0)
1897                         format |= UMA_ZFLAG_HASH;
1898                 else
1899                         format |= UMA_ZFLAG_VTOSLAB;
1900         }
1901         keg->uk_ipers = ipers;
1902         keg->uk_rsize = rsize;
1903         keg->uk_flags |= format;
1904         keg->uk_ppera = pages;
1905         CTR6(KTR_UMA, "%s: keg=%s, flags=%#x, rsize=%u, ipers=%u, ppera=%u",
1906             __func__, keg->uk_name, keg->uk_flags, rsize, ipers, pages);
1907         KASSERT(keg->uk_ipers > 0 && keg->uk_ipers <= SLAB_MAX_SETSIZE,
1908             ("%s: keg=%s, flags=0x%b, rsize=%u, ipers=%u, ppera=%u", __func__,
1909              keg->uk_name, keg->uk_flags, PRINT_UMA_ZFLAGS, rsize, ipers,
1910              pages));
1911 }
1912
1913 /*
1914  * Keg header ctor.  This initializes all fields, locks, etc.  And inserts
1915  * the keg onto the global keg list.
1916  *
1917  * Arguments/Returns follow uma_ctor specifications
1918  *      udata  Actually uma_kctor_args
1919  */
1920 static int
1921 keg_ctor(void *mem, int size, void *udata, int flags)
1922 {
1923         struct uma_kctor_args *arg = udata;
1924         uma_keg_t keg = mem;
1925         uma_zone_t zone;
1926         int i;
1927
1928         bzero(keg, size);
1929         keg->uk_size = arg->size;
1930         keg->uk_init = arg->uminit;
1931         keg->uk_fini = arg->fini;
1932         keg->uk_align = arg->align;
1933         keg->uk_reserve = 0;
1934         keg->uk_flags = arg->flags;
1935
1936         /*
1937          * We use a global round-robin policy by default.  Zones with
1938          * UMA_ZONE_FIRSTTOUCH set will use first-touch instead, in which
1939          * case the iterator is never run.
1940          */
1941         keg->uk_dr.dr_policy = DOMAINSET_RR();
1942         keg->uk_dr.dr_iter = 0;
1943
1944         /*
1945          * The master zone is passed to us at keg-creation time.
1946          */
1947         zone = arg->zone;
1948         keg->uk_name = zone->uz_name;
1949
1950         if (arg->flags & UMA_ZONE_VM)
1951                 keg->uk_flags |= UMA_ZFLAG_CACHEONLY;
1952
1953         if (arg->flags & UMA_ZONE_ZINIT)
1954                 keg->uk_init = zero_init;
1955
1956         if (arg->flags & UMA_ZONE_MALLOC)
1957                 keg->uk_flags |= UMA_ZFLAG_VTOSLAB;
1958
1959 #ifndef SMP
1960         keg->uk_flags &= ~UMA_ZONE_PCPU;
1961 #endif
1962
1963         keg_layout(keg);
1964
1965         /*
1966          * Use a first-touch NUMA policy for all kegs that pmap_extract()
1967          * will work on with the exception of critical VM structures
1968          * necessary for paging.
1969          *
1970          * Zones may override the default by specifying either.
1971          */
1972 #ifdef NUMA
1973         if ((keg->uk_flags &
1974             (UMA_ZFLAG_HASH | UMA_ZONE_VM | UMA_ZONE_ROUNDROBIN)) == 0)
1975                 keg->uk_flags |= UMA_ZONE_FIRSTTOUCH;
1976         else if ((keg->uk_flags & UMA_ZONE_FIRSTTOUCH) == 0)
1977                 keg->uk_flags |= UMA_ZONE_ROUNDROBIN;
1978 #endif
1979
1980         /*
1981          * If we haven't booted yet we need allocations to go through the
1982          * startup cache until the vm is ready.
1983          */
1984 #ifdef UMA_MD_SMALL_ALLOC
1985         if (keg->uk_ppera == 1)
1986                 keg->uk_allocf = uma_small_alloc;
1987         else
1988 #endif
1989         if (booted < BOOT_KVA)
1990                 keg->uk_allocf = startup_alloc;
1991         else if (keg->uk_flags & UMA_ZONE_PCPU)
1992                 keg->uk_allocf = pcpu_page_alloc;
1993         else
1994                 keg->uk_allocf = page_alloc;
1995 #ifdef UMA_MD_SMALL_ALLOC
1996         if (keg->uk_ppera == 1)
1997                 keg->uk_freef = uma_small_free;
1998         else
1999 #endif
2000         if (keg->uk_flags & UMA_ZONE_PCPU)
2001                 keg->uk_freef = pcpu_page_free;
2002         else
2003                 keg->uk_freef = page_free;
2004
2005         /*
2006          * Initialize keg's locks.
2007          */
2008         for (i = 0; i < vm_ndomains; i++)
2009                 KEG_LOCK_INIT(keg, i, (arg->flags & UMA_ZONE_MTXCLASS));
2010
2011         /*
2012          * If we're putting the slab header in the actual page we need to
2013          * figure out where in each page it goes.  See slab_sizeof
2014          * definition.
2015          */
2016         if (!(keg->uk_flags & UMA_ZFLAG_OFFPAGE)) {
2017                 size_t shsize;
2018
2019                 shsize = slab_sizeof(keg->uk_ipers);
2020                 keg->uk_pgoff = (PAGE_SIZE * keg->uk_ppera) - shsize;
2021                 /*
2022                  * The only way the following is possible is if with our
2023                  * UMA_ALIGN_PTR adjustments we are now bigger than
2024                  * UMA_SLAB_SIZE.  I haven't checked whether this is
2025                  * mathematically possible for all cases, so we make
2026                  * sure here anyway.
2027                  */
2028                 KASSERT(keg->uk_pgoff + shsize <= PAGE_SIZE * keg->uk_ppera,
2029                     ("zone %s ipers %d rsize %d size %d slab won't fit",
2030                     zone->uz_name, keg->uk_ipers, keg->uk_rsize, keg->uk_size));
2031         }
2032
2033         if (keg->uk_flags & UMA_ZFLAG_HASH)
2034                 hash_alloc(&keg->uk_hash, 0);
2035
2036         CTR3(KTR_UMA, "keg_ctor %p zone %s(%p)", keg, zone->uz_name, zone);
2037
2038         LIST_INSERT_HEAD(&keg->uk_zones, zone, uz_link);
2039
2040         rw_wlock(&uma_rwlock);
2041         LIST_INSERT_HEAD(&uma_kegs, keg, uk_link);
2042         rw_wunlock(&uma_rwlock);
2043         return (0);
2044 }
2045
2046 static void
2047 zone_kva_available(uma_zone_t zone, void *unused)
2048 {
2049         uma_keg_t keg;
2050
2051         if ((zone->uz_flags & UMA_ZFLAG_CACHE) != 0)
2052                 return;
2053         KEG_GET(zone, keg);
2054         if (keg->uk_allocf == startup_alloc)
2055                 keg->uk_allocf = page_alloc;
2056 }
2057
2058 static void
2059 zone_alloc_counters(uma_zone_t zone, void *unused)
2060 {
2061
2062         zone->uz_allocs = counter_u64_alloc(M_WAITOK);
2063         zone->uz_frees = counter_u64_alloc(M_WAITOK);
2064         zone->uz_fails = counter_u64_alloc(M_WAITOK);
2065 }
2066
2067 static void
2068 zone_alloc_sysctl(uma_zone_t zone, void *unused)
2069 {
2070         uma_zone_domain_t zdom;
2071         uma_domain_t dom;
2072         uma_keg_t keg;
2073         struct sysctl_oid *oid, *domainoid;
2074         int domains, i, cnt;
2075         static const char *nokeg = "cache zone";
2076         char *c;
2077
2078         /*
2079          * Make a sysctl safe copy of the zone name by removing
2080          * any special characters and handling dups by appending
2081          * an index.
2082          */
2083         if (zone->uz_namecnt != 0) {
2084                 /* Count the number of decimal digits and '_' separator. */
2085                 for (i = 1, cnt = zone->uz_namecnt; cnt != 0; i++)
2086                         cnt /= 10;
2087                 zone->uz_ctlname = malloc(strlen(zone->uz_name) + i + 1,
2088                     M_UMA, M_WAITOK);
2089                 sprintf(zone->uz_ctlname, "%s_%d", zone->uz_name,
2090                     zone->uz_namecnt);
2091         } else
2092                 zone->uz_ctlname = strdup(zone->uz_name, M_UMA);
2093         for (c = zone->uz_ctlname; *c != '\0'; c++)
2094                 if (strchr("./\\ -", *c) != NULL)
2095                         *c = '_';
2096
2097         /*
2098          * Basic parameters at the root.
2099          */
2100         zone->uz_oid = SYSCTL_ADD_NODE(NULL, SYSCTL_STATIC_CHILDREN(_vm_uma),
2101             OID_AUTO, zone->uz_ctlname, CTLFLAG_RD, NULL, "");
2102         oid = zone->uz_oid;
2103         SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2104             "size", CTLFLAG_RD, &zone->uz_size, 0, "Allocation size");
2105         SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2106             "flags", CTLFLAG_RD | CTLTYPE_STRING | CTLFLAG_MPSAFE,
2107             zone, 0, sysctl_handle_uma_zone_flags, "A",
2108             "Allocator configuration flags");
2109         SYSCTL_ADD_U16(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2110             "bucket_size", CTLFLAG_RD, &zone->uz_bucket_size, 0,
2111             "Desired per-cpu cache size");
2112         SYSCTL_ADD_U16(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2113             "bucket_size_max", CTLFLAG_RD, &zone->uz_bucket_size_max, 0,
2114             "Maximum allowed per-cpu cache size");
2115
2116         /*
2117          * keg if present.
2118          */
2119         if ((zone->uz_flags & UMA_ZFLAG_HASH) == 0)
2120                 domains = vm_ndomains;
2121         else
2122                 domains = 1;
2123         oid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(zone->uz_oid), OID_AUTO,
2124             "keg", CTLFLAG_RD, NULL, "");
2125         keg = zone->uz_keg;
2126         if ((zone->uz_flags & UMA_ZFLAG_CACHE) == 0) {
2127                 SYSCTL_ADD_CONST_STRING(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2128                     "name", CTLFLAG_RD, keg->uk_name, "Keg name");
2129                 SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2130                     "rsize", CTLFLAG_RD, &keg->uk_rsize, 0,
2131                     "Real object size with alignment");
2132                 SYSCTL_ADD_U16(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2133                     "ppera", CTLFLAG_RD, &keg->uk_ppera, 0,
2134                     "pages per-slab allocation");
2135                 SYSCTL_ADD_U16(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2136                     "ipers", CTLFLAG_RD, &keg->uk_ipers, 0,
2137                     "items available per-slab");
2138                 SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2139                     "align", CTLFLAG_RD, &keg->uk_align, 0,
2140                     "item alignment mask");
2141                 SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2142                     "efficiency", CTLFLAG_RD | CTLTYPE_INT | CTLFLAG_MPSAFE,
2143                     keg, 0, sysctl_handle_uma_slab_efficiency, "I",
2144                     "Slab utilization (100 - internal fragmentation %)");
2145                 domainoid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(oid),
2146                     OID_AUTO, "domain", CTLFLAG_RD, NULL, "");
2147                 for (i = 0; i < domains; i++) {
2148                         dom = &keg->uk_domain[i];
2149                         oid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(domainoid),
2150                             OID_AUTO, VM_DOMAIN(i)->vmd_name, CTLFLAG_RD,
2151                             NULL, "");
2152                         SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2153                             "pages", CTLFLAG_RD, &dom->ud_pages, 0,
2154                             "Total pages currently allocated from VM");
2155                         SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2156                             "free", CTLFLAG_RD, &dom->ud_free, 0,
2157                             "items free in the slab layer");
2158                 }
2159         } else
2160                 SYSCTL_ADD_CONST_STRING(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2161                     "name", CTLFLAG_RD, nokeg, "Keg name");
2162
2163         /*
2164          * Information about zone limits.
2165          */
2166         oid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(zone->uz_oid), OID_AUTO,
2167             "limit", CTLFLAG_RD, NULL, "");
2168         SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2169             "items", CTLFLAG_RD | CTLTYPE_U64 | CTLFLAG_MPSAFE,
2170             zone, 0, sysctl_handle_uma_zone_items, "QU",
2171             "current number of allocated items if limit is set");
2172         SYSCTL_ADD_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2173             "max_items", CTLFLAG_RD, &zone->uz_max_items, 0,
2174             "Maximum number of cached items");
2175         SYSCTL_ADD_U32(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2176             "sleepers", CTLFLAG_RD, &zone->uz_sleepers, 0,
2177             "Number of threads sleeping at limit");
2178         SYSCTL_ADD_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2179             "sleeps", CTLFLAG_RD, &zone->uz_sleeps, 0,
2180             "Total zone limit sleeps");
2181         SYSCTL_ADD_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2182             "bucket_max", CTLFLAG_RD, &zone->uz_bkt_max, 0,
2183             "Maximum number of items in the bucket cache");
2184         SYSCTL_ADD_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2185             "bucket_cnt", CTLFLAG_RD, &zone->uz_bkt_count, 0,
2186             "Number of items in the bucket cache");
2187
2188         /*
2189          * Per-domain zone information.
2190          */
2191         domainoid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(zone->uz_oid),
2192             OID_AUTO, "domain", CTLFLAG_RD, NULL, "");
2193         if ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) == 0)
2194                 domains = 1;
2195         for (i = 0; i < domains; i++) {
2196                 zdom = &zone->uz_domain[i];
2197                 oid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(domainoid),
2198                     OID_AUTO, VM_DOMAIN(i)->vmd_name, CTLFLAG_RD, NULL, "");
2199                 SYSCTL_ADD_LONG(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2200                     "nitems", CTLFLAG_RD, &zdom->uzd_nitems,
2201                     "number of items in this domain");
2202                 SYSCTL_ADD_LONG(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2203                     "imax", CTLFLAG_RD, &zdom->uzd_imax,
2204                     "maximum item count in this period");
2205                 SYSCTL_ADD_LONG(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2206                     "imin", CTLFLAG_RD, &zdom->uzd_imin,
2207                     "minimum item count in this period");
2208                 SYSCTL_ADD_LONG(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2209                     "wss", CTLFLAG_RD, &zdom->uzd_wss,
2210                     "Working set size");
2211         }
2212
2213         /*
2214          * General statistics.
2215          */
2216         oid = SYSCTL_ADD_NODE(NULL, SYSCTL_CHILDREN(zone->uz_oid), OID_AUTO,
2217             "stats", CTLFLAG_RD, NULL, "");
2218         SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2219             "current", CTLFLAG_RD | CTLTYPE_INT | CTLFLAG_MPSAFE,
2220             zone, 1, sysctl_handle_uma_zone_cur, "I",
2221             "Current number of allocated items");
2222         SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2223             "allocs", CTLFLAG_RD | CTLTYPE_U64 | CTLFLAG_MPSAFE,
2224             zone, 0, sysctl_handle_uma_zone_allocs, "QU",
2225             "Total allocation calls");
2226         SYSCTL_ADD_PROC(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2227             "frees", CTLFLAG_RD | CTLTYPE_U64 | CTLFLAG_MPSAFE,
2228             zone, 0, sysctl_handle_uma_zone_frees, "QU",
2229             "Total free calls");
2230         SYSCTL_ADD_COUNTER_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2231             "fails", CTLFLAG_RD, &zone->uz_fails,
2232             "Number of allocation failures");
2233         SYSCTL_ADD_U64(NULL, SYSCTL_CHILDREN(oid), OID_AUTO,
2234             "xdomain", CTLFLAG_RD, &zone->uz_xdomain, 0,
2235             "Free calls from the wrong domain");
2236 }
2237
2238 struct uma_zone_count {
2239         const char      *name;
2240         int             count;
2241 };
2242
2243 static void
2244 zone_count(uma_zone_t zone, void *arg)
2245 {
2246         struct uma_zone_count *cnt;
2247
2248         cnt = arg;
2249         /*
2250          * Some zones are rapidly created with identical names and
2251          * destroyed out of order.  This can lead to gaps in the count.
2252          * Use one greater than the maximum observed for this name.
2253          */
2254         if (strcmp(zone->uz_name, cnt->name) == 0)
2255                 cnt->count = MAX(cnt->count,
2256                     zone->uz_namecnt + 1);
2257 }
2258
2259 static void
2260 zone_update_caches(uma_zone_t zone)
2261 {
2262         int i;
2263
2264         for (i = 0; i <= mp_maxid; i++) {
2265                 cache_set_uz_size(&zone->uz_cpu[i], zone->uz_size);
2266                 cache_set_uz_flags(&zone->uz_cpu[i], zone->uz_flags);
2267         }
2268 }
2269
2270 /*
2271  * Zone header ctor.  This initializes all fields, locks, etc.
2272  *
2273  * Arguments/Returns follow uma_ctor specifications
2274  *      udata  Actually uma_zctor_args
2275  */
2276 static int
2277 zone_ctor(void *mem, int size, void *udata, int flags)
2278 {
2279         struct uma_zone_count cnt;
2280         struct uma_zctor_args *arg = udata;
2281         uma_zone_t zone = mem;
2282         uma_zone_t z;
2283         uma_keg_t keg;
2284         int i;
2285
2286         bzero(zone, size);
2287         zone->uz_name = arg->name;
2288         zone->uz_ctor = arg->ctor;
2289         zone->uz_dtor = arg->dtor;
2290         zone->uz_init = NULL;
2291         zone->uz_fini = NULL;
2292         zone->uz_sleeps = 0;
2293         zone->uz_xdomain = 0;
2294         zone->uz_bucket_size = 0;
2295         zone->uz_bucket_size_min = 0;
2296         zone->uz_bucket_size_max = BUCKET_MAX;
2297         zone->uz_flags = 0;
2298         zone->uz_warning = NULL;
2299         /* The domain structures follow the cpu structures. */
2300         zone->uz_domain = (struct uma_zone_domain *)&zone->uz_cpu[mp_ncpus];
2301         zone->uz_bkt_max = ULONG_MAX;
2302         timevalclear(&zone->uz_ratecheck);
2303
2304         /* Count the number of duplicate names. */
2305         cnt.name = arg->name;
2306         cnt.count = 0;
2307         zone_foreach(zone_count, &cnt);
2308         zone->uz_namecnt = cnt.count;
2309         ZONE_LOCK_INIT(zone, (arg->flags & UMA_ZONE_MTXCLASS));
2310         ZONE_CROSS_LOCK_INIT(zone);
2311
2312         for (i = 0; i < vm_ndomains; i++)
2313                 TAILQ_INIT(&zone->uz_domain[i].uzd_buckets);
2314
2315 #ifdef INVARIANTS
2316         if (arg->uminit == trash_init && arg->fini == trash_fini)
2317                 zone->uz_flags |= UMA_ZFLAG_TRASH | UMA_ZFLAG_CTORDTOR;
2318 #endif
2319
2320         /*
2321          * This is a pure cache zone, no kegs.
2322          */
2323         if (arg->import) {
2324                 KASSERT((arg->flags & UMA_ZFLAG_CACHE) != 0,
2325                     ("zone_ctor: Import specified for non-cache zone."));
2326                 if (arg->flags & UMA_ZONE_VM)
2327                         arg->flags |= UMA_ZFLAG_CACHEONLY;
2328                 zone->uz_flags = arg->flags;
2329                 zone->uz_size = arg->size;
2330                 zone->uz_import = arg->import;
2331                 zone->uz_release = arg->release;
2332                 zone->uz_arg = arg->arg;
2333                 rw_wlock(&uma_rwlock);
2334                 LIST_INSERT_HEAD(&uma_cachezones, zone, uz_link);
2335                 rw_wunlock(&uma_rwlock);
2336                 goto out;
2337         }
2338
2339         /*
2340          * Use the regular zone/keg/slab allocator.
2341          */
2342         zone->uz_import = zone_import;
2343         zone->uz_release = zone_release;
2344         zone->uz_arg = zone;
2345         keg = arg->keg;
2346
2347         if (arg->flags & UMA_ZONE_SECONDARY) {
2348                 KASSERT((zone->uz_flags & UMA_ZONE_SECONDARY) == 0,
2349                     ("Secondary zone requested UMA_ZFLAG_INTERNAL"));
2350                 KASSERT(arg->keg != NULL, ("Secondary zone on zero'd keg"));
2351                 zone->uz_init = arg->uminit;
2352                 zone->uz_fini = arg->fini;
2353                 zone->uz_flags |= UMA_ZONE_SECONDARY;
2354                 rw_wlock(&uma_rwlock);
2355                 ZONE_LOCK(zone);
2356                 LIST_FOREACH(z, &keg->uk_zones, uz_link) {
2357                         if (LIST_NEXT(z, uz_link) == NULL) {
2358                                 LIST_INSERT_AFTER(z, zone, uz_link);
2359                                 break;
2360                         }
2361                 }
2362                 ZONE_UNLOCK(zone);
2363                 rw_wunlock(&uma_rwlock);
2364         } else if (keg == NULL) {
2365                 if ((keg = uma_kcreate(zone, arg->size, arg->uminit, arg->fini,
2366                     arg->align, arg->flags)) == NULL)
2367                         return (ENOMEM);
2368         } else {
2369                 struct uma_kctor_args karg;
2370                 int error;
2371
2372                 /* We should only be here from uma_startup() */
2373                 karg.size = arg->size;
2374                 karg.uminit = arg->uminit;
2375                 karg.fini = arg->fini;
2376                 karg.align = arg->align;
2377                 karg.flags = arg->flags;
2378                 karg.zone = zone;
2379                 error = keg_ctor(arg->keg, sizeof(struct uma_keg), &karg,
2380                     flags);
2381                 if (error)
2382                         return (error);
2383         }
2384
2385         /* Inherit properties from the keg. */
2386         zone->uz_keg = keg;
2387         zone->uz_size = keg->uk_size;
2388         zone->uz_flags |= (keg->uk_flags &
2389             (UMA_ZONE_INHERIT | UMA_ZFLAG_INHERIT));
2390
2391 out:
2392         if (__predict_true(booted >= BOOT_RUNNING)) {
2393                 zone_alloc_counters(zone, NULL);
2394                 zone_alloc_sysctl(zone, NULL);
2395         } else {
2396                 zone->uz_allocs = EARLY_COUNTER;
2397                 zone->uz_frees = EARLY_COUNTER;
2398                 zone->uz_fails = EARLY_COUNTER;
2399         }
2400
2401         KASSERT((arg->flags & (UMA_ZONE_MAXBUCKET | UMA_ZONE_NOBUCKET)) !=
2402             (UMA_ZONE_MAXBUCKET | UMA_ZONE_NOBUCKET),
2403             ("Invalid zone flag combination"));
2404         if (arg->flags & UMA_ZFLAG_INTERNAL)
2405                 zone->uz_bucket_size_max = zone->uz_bucket_size = 0;
2406         if ((arg->flags & UMA_ZONE_MAXBUCKET) != 0)
2407                 zone->uz_bucket_size = BUCKET_MAX;
2408         else if ((arg->flags & UMA_ZONE_MINBUCKET) != 0)
2409                 zone->uz_bucket_size_max = zone->uz_bucket_size = BUCKET_MIN;
2410         else if ((arg->flags & UMA_ZONE_NOBUCKET) != 0)
2411                 zone->uz_bucket_size = 0;
2412         else
2413                 zone->uz_bucket_size = bucket_select(zone->uz_size);
2414         zone->uz_bucket_size_min = zone->uz_bucket_size;
2415         if (zone->uz_dtor != NULL || zone->uz_ctor != NULL)
2416                 zone->uz_flags |= UMA_ZFLAG_CTORDTOR;
2417         zone_update_caches(zone);
2418
2419         return (0);
2420 }
2421
2422 /*
2423  * Keg header dtor.  This frees all data, destroys locks, frees the hash
2424  * table and removes the keg from the global list.
2425  *
2426  * Arguments/Returns follow uma_dtor specifications
2427  *      udata  unused
2428  */
2429 static void
2430 keg_dtor(void *arg, int size, void *udata)
2431 {
2432         uma_keg_t keg;
2433         uint32_t free, pages;
2434         int i;
2435
2436         keg = (uma_keg_t)arg;
2437         free = pages = 0;
2438         for (i = 0; i < vm_ndomains; i++) {
2439                 free += keg->uk_domain[i].ud_free;
2440                 pages += keg->uk_domain[i].ud_pages;
2441                 KEG_LOCK_FINI(keg, i);
2442         }
2443         if (free != 0)
2444                 printf("Freed UMA keg (%s) was not empty (%u items). "
2445                     " Lost %u pages of memory.\n",
2446                     keg->uk_name ? keg->uk_name : "",
2447                     free, pages);
2448
2449         hash_free(&keg->uk_hash);
2450 }
2451
2452 /*
2453  * Zone header dtor.
2454  *
2455  * Arguments/Returns follow uma_dtor specifications
2456  *      udata  unused
2457  */
2458 static void
2459 zone_dtor(void *arg, int size, void *udata)
2460 {
2461         uma_zone_t zone;
2462         uma_keg_t keg;
2463
2464         zone = (uma_zone_t)arg;
2465
2466         sysctl_remove_oid(zone->uz_oid, 1, 1);
2467
2468         if (!(zone->uz_flags & UMA_ZFLAG_INTERNAL))
2469                 cache_drain(zone);
2470
2471         rw_wlock(&uma_rwlock);
2472         LIST_REMOVE(zone, uz_link);
2473         rw_wunlock(&uma_rwlock);
2474         /*
2475          * XXX there are some races here where
2476          * the zone can be drained but zone lock
2477          * released and then refilled before we
2478          * remove it... we dont care for now
2479          */
2480         zone_reclaim(zone, M_WAITOK, true);
2481         /*
2482          * We only destroy kegs from non secondary/non cache zones.
2483          */
2484         if ((zone->uz_flags & (UMA_ZONE_SECONDARY | UMA_ZFLAG_CACHE)) == 0) {
2485                 keg = zone->uz_keg;
2486                 rw_wlock(&uma_rwlock);
2487                 LIST_REMOVE(keg, uk_link);
2488                 rw_wunlock(&uma_rwlock);
2489                 zone_free_item(kegs, keg, NULL, SKIP_NONE);
2490         }
2491         counter_u64_free(zone->uz_allocs);
2492         counter_u64_free(zone->uz_frees);
2493         counter_u64_free(zone->uz_fails);
2494         free(zone->uz_ctlname, M_UMA);
2495         ZONE_LOCK_FINI(zone);
2496         ZONE_CROSS_LOCK_FINI(zone);
2497 }
2498
2499 static void
2500 zone_foreach_unlocked(void (*zfunc)(uma_zone_t, void *arg), void *arg)
2501 {
2502         uma_keg_t keg;
2503         uma_zone_t zone;
2504
2505         LIST_FOREACH(keg, &uma_kegs, uk_link) {
2506                 LIST_FOREACH(zone, &keg->uk_zones, uz_link)
2507                         zfunc(zone, arg);
2508         }
2509         LIST_FOREACH(zone, &uma_cachezones, uz_link)
2510                 zfunc(zone, arg);
2511 }
2512
2513 /*
2514  * Traverses every zone in the system and calls a callback
2515  *
2516  * Arguments:
2517  *      zfunc  A pointer to a function which accepts a zone
2518  *              as an argument.
2519  *
2520  * Returns:
2521  *      Nothing
2522  */
2523 static void
2524 zone_foreach(void (*zfunc)(uma_zone_t, void *arg), void *arg)
2525 {
2526
2527         rw_rlock(&uma_rwlock);
2528         zone_foreach_unlocked(zfunc, arg);
2529         rw_runlock(&uma_rwlock);
2530 }
2531
2532 /*
2533  * Initialize the kernel memory allocator.  This is done after pages can be
2534  * allocated but before general KVA is available.
2535  */
2536 void
2537 uma_startup1(vm_offset_t virtual_avail)
2538 {
2539         struct uma_zctor_args args;
2540         size_t ksize, zsize, size;
2541         uma_keg_t masterkeg;
2542         uintptr_t m;
2543         uint8_t pflag;
2544
2545         bootstart = bootmem = virtual_avail;
2546
2547         rw_init(&uma_rwlock, "UMA lock");
2548         sx_init(&uma_reclaim_lock, "umareclaim");
2549
2550         ksize = sizeof(struct uma_keg) +
2551             (sizeof(struct uma_domain) * vm_ndomains);
2552         ksize = roundup(ksize, UMA_SUPER_ALIGN);
2553         zsize = sizeof(struct uma_zone) +
2554             (sizeof(struct uma_cache) * (mp_maxid + 1)) +
2555             (sizeof(struct uma_zone_domain) * vm_ndomains);
2556         zsize = roundup(zsize, UMA_SUPER_ALIGN);
2557
2558         /* Allocate the zone of zones, zone of kegs, and zone of zones keg. */
2559         size = (zsize * 2) + ksize;
2560         m = (uintptr_t)startup_alloc(NULL, size, 0, &pflag, M_NOWAIT | M_ZERO);
2561         zones = (uma_zone_t)m;
2562         m += zsize;
2563         kegs = (uma_zone_t)m;
2564         m += zsize;
2565         masterkeg = (uma_keg_t)m;
2566
2567         /* "manually" create the initial zone */
2568         memset(&args, 0, sizeof(args));
2569         args.name = "UMA Kegs";
2570         args.size = ksize;
2571         args.ctor = keg_ctor;
2572         args.dtor = keg_dtor;
2573         args.uminit = zero_init;
2574         args.fini = NULL;
2575         args.keg = masterkeg;
2576         args.align = UMA_SUPER_ALIGN - 1;
2577         args.flags = UMA_ZFLAG_INTERNAL;
2578         zone_ctor(kegs, zsize, &args, M_WAITOK);
2579
2580         args.name = "UMA Zones";
2581         args.size = zsize;
2582         args.ctor = zone_ctor;
2583         args.dtor = zone_dtor;
2584         args.uminit = zero_init;
2585         args.fini = NULL;
2586         args.keg = NULL;
2587         args.align = UMA_SUPER_ALIGN - 1;
2588         args.flags = UMA_ZFLAG_INTERNAL;
2589         zone_ctor(zones, zsize, &args, M_WAITOK);
2590
2591         /* Now make zones for slab headers */
2592         slabzones[0] = uma_zcreate("UMA Slabs 0", SLABZONE0_SIZE,
2593             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
2594         slabzones[1] = uma_zcreate("UMA Slabs 1", SLABZONE1_SIZE,
2595             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
2596
2597         hashzone = uma_zcreate("UMA Hash",
2598             sizeof(struct slabhead *) * UMA_HASH_SIZE_INIT,
2599             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
2600
2601         bucket_init();
2602 }
2603
2604 #ifndef UMA_MD_SMALL_ALLOC
2605 extern void vm_radix_reserve_kva(void);
2606 #endif
2607
2608 /*
2609  * Advertise the availability of normal kva allocations and switch to
2610  * the default back-end allocator.  Marks the KVA we consumed on startup
2611  * as used in the map.
2612  */
2613 void
2614 uma_startup2(void)
2615 {
2616
2617         if (!PMAP_HAS_DMAP) {
2618                 vm_map_lock(kernel_map);
2619                 (void)vm_map_insert(kernel_map, NULL, 0, bootstart, bootmem,
2620                     VM_PROT_RW, VM_PROT_RW, MAP_NOFAULT);
2621                 vm_map_unlock(kernel_map);
2622         }
2623
2624 #ifndef UMA_MD_SMALL_ALLOC
2625         /* Set up radix zone to use noobj_alloc. */
2626         vm_radix_reserve_kva();
2627 #endif
2628
2629         booted = BOOT_KVA;
2630         zone_foreach_unlocked(zone_kva_available, NULL);
2631         bucket_enable();
2632 }
2633
2634 /*
2635  * Finish our initialization steps.
2636  */
2637 static void
2638 uma_startup3(void)
2639 {
2640
2641 #ifdef INVARIANTS
2642         TUNABLE_INT_FETCH("vm.debug.divisor", &dbg_divisor);
2643         uma_dbg_cnt = counter_u64_alloc(M_WAITOK);
2644         uma_skip_cnt = counter_u64_alloc(M_WAITOK);
2645 #endif
2646         zone_foreach_unlocked(zone_alloc_counters, NULL);
2647         zone_foreach_unlocked(zone_alloc_sysctl, NULL);
2648         callout_init(&uma_callout, 1);
2649         callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
2650         booted = BOOT_RUNNING;
2651
2652         EVENTHANDLER_REGISTER(shutdown_post_sync, uma_shutdown, NULL,
2653             EVENTHANDLER_PRI_FIRST);
2654 }
2655
2656 static void
2657 uma_shutdown(void)
2658 {
2659
2660         booted = BOOT_SHUTDOWN;
2661 }
2662
2663 static uma_keg_t
2664 uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit, uma_fini fini,
2665                 int align, uint32_t flags)
2666 {
2667         struct uma_kctor_args args;
2668
2669         args.size = size;
2670         args.uminit = uminit;
2671         args.fini = fini;
2672         args.align = (align == UMA_ALIGN_CACHE) ? uma_align_cache : align;
2673         args.flags = flags;
2674         args.zone = zone;
2675         return (zone_alloc_item(kegs, &args, UMA_ANYDOMAIN, M_WAITOK));
2676 }
2677
2678 /* Public functions */
2679 /* See uma.h */
2680 void
2681 uma_set_align(int align)
2682 {
2683
2684         if (align != UMA_ALIGN_CACHE)
2685                 uma_align_cache = align;
2686 }
2687
2688 /* See uma.h */
2689 uma_zone_t
2690 uma_zcreate(const char *name, size_t size, uma_ctor ctor, uma_dtor dtor,
2691                 uma_init uminit, uma_fini fini, int align, uint32_t flags)
2692
2693 {
2694         struct uma_zctor_args args;
2695         uma_zone_t res;
2696
2697         KASSERT(powerof2(align + 1), ("invalid zone alignment %d for \"%s\"",
2698             align, name));
2699
2700         /* This stuff is essential for the zone ctor */
2701         memset(&args, 0, sizeof(args));
2702         args.name = name;
2703         args.size = size;
2704         args.ctor = ctor;
2705         args.dtor = dtor;
2706         args.uminit = uminit;
2707         args.fini = fini;
2708 #ifdef  INVARIANTS
2709         /*
2710          * Inject procedures which check for memory use after free if we are
2711          * allowed to scramble the memory while it is not allocated.  This
2712          * requires that: UMA is actually able to access the memory, no init
2713          * or fini procedures, no dependency on the initial value of the
2714          * memory, and no (legitimate) use of the memory after free.  Note,
2715          * the ctor and dtor do not need to be empty.
2716          */
2717         if ((!(flags & (UMA_ZONE_ZINIT | UMA_ZONE_NOTOUCH |
2718             UMA_ZONE_NOFREE))) && uminit == NULL && fini == NULL) {
2719                 args.uminit = trash_init;
2720                 args.fini = trash_fini;
2721         }
2722 #endif
2723         args.align = align;
2724         args.flags = flags;
2725         args.keg = NULL;
2726
2727         sx_slock(&uma_reclaim_lock);
2728         res = zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK);
2729         sx_sunlock(&uma_reclaim_lock);
2730
2731         return (res);
2732 }
2733
2734 /* See uma.h */
2735 uma_zone_t
2736 uma_zsecond_create(char *name, uma_ctor ctor, uma_dtor dtor,
2737                     uma_init zinit, uma_fini zfini, uma_zone_t master)
2738 {
2739         struct uma_zctor_args args;
2740         uma_keg_t keg;
2741         uma_zone_t res;
2742
2743         keg = master->uz_keg;
2744         memset(&args, 0, sizeof(args));
2745         args.name = name;
2746         args.size = keg->uk_size;
2747         args.ctor = ctor;
2748         args.dtor = dtor;
2749         args.uminit = zinit;
2750         args.fini = zfini;
2751         args.align = keg->uk_align;
2752         args.flags = keg->uk_flags | UMA_ZONE_SECONDARY;
2753         args.keg = keg;
2754
2755         sx_slock(&uma_reclaim_lock);
2756         res = zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK);
2757         sx_sunlock(&uma_reclaim_lock);
2758
2759         return (res);
2760 }
2761
2762 /* See uma.h */
2763 uma_zone_t
2764 uma_zcache_create(char *name, int size, uma_ctor ctor, uma_dtor dtor,
2765                     uma_init zinit, uma_fini zfini, uma_import zimport,
2766                     uma_release zrelease, void *arg, int flags)
2767 {
2768         struct uma_zctor_args args;
2769
2770         memset(&args, 0, sizeof(args));
2771         args.name = name;
2772         args.size = size;
2773         args.ctor = ctor;
2774         args.dtor = dtor;
2775         args.uminit = zinit;
2776         args.fini = zfini;
2777         args.import = zimport;
2778         args.release = zrelease;
2779         args.arg = arg;
2780         args.align = 0;
2781         args.flags = flags | UMA_ZFLAG_CACHE;
2782
2783         return (zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK));
2784 }
2785
2786 /* See uma.h */
2787 void
2788 uma_zdestroy(uma_zone_t zone)
2789 {
2790
2791         /*
2792          * Large slabs are expensive to reclaim, so don't bother doing
2793          * unnecessary work if we're shutting down.
2794          */
2795         if (booted == BOOT_SHUTDOWN &&
2796             zone->uz_fini == NULL && zone->uz_release == zone_release)
2797                 return;
2798         sx_slock(&uma_reclaim_lock);
2799         zone_free_item(zones, zone, NULL, SKIP_NONE);
2800         sx_sunlock(&uma_reclaim_lock);
2801 }
2802
2803 void
2804 uma_zwait(uma_zone_t zone)
2805 {
2806         void *item;
2807
2808         item = uma_zalloc_arg(zone, NULL, M_WAITOK);
2809         uma_zfree(zone, item);
2810 }
2811
2812 void *
2813 uma_zalloc_pcpu_arg(uma_zone_t zone, void *udata, int flags)
2814 {
2815         void *item;
2816 #ifdef SMP
2817         int i;
2818
2819         MPASS(zone->uz_flags & UMA_ZONE_PCPU);
2820 #endif
2821         item = uma_zalloc_arg(zone, udata, flags & ~M_ZERO);
2822         if (item != NULL && (flags & M_ZERO)) {
2823 #ifdef SMP
2824                 for (i = 0; i <= mp_maxid; i++)
2825                         bzero(zpcpu_get_cpu(item, i), zone->uz_size);
2826 #else
2827                 bzero(item, zone->uz_size);
2828 #endif
2829         }
2830         return (item);
2831 }
2832
2833 /*
2834  * A stub while both regular and pcpu cases are identical.
2835  */
2836 void
2837 uma_zfree_pcpu_arg(uma_zone_t zone, void *item, void *udata)
2838 {
2839
2840 #ifdef SMP
2841         MPASS(zone->uz_flags & UMA_ZONE_PCPU);
2842 #endif
2843         uma_zfree_arg(zone, item, udata);
2844 }
2845
2846 #ifdef INVARIANTS
2847 #define UMA_ALWAYS_CTORDTOR     1
2848 #else
2849 #define UMA_ALWAYS_CTORDTOR     0
2850 #endif
2851
2852 static void *
2853 item_ctor(uma_zone_t zone, int size, void *udata, int flags, void *item)
2854 {
2855 #ifdef INVARIANTS
2856         bool skipdbg;
2857
2858         skipdbg = uma_dbg_zskip(zone, item);
2859         if (!skipdbg && (zone->uz_flags & UMA_ZFLAG_TRASH) != 0 &&
2860             zone->uz_ctor != trash_ctor)
2861                 trash_ctor(item, size, udata, flags);
2862 #endif
2863         if (__predict_false(zone->uz_ctor != NULL) &&
2864             zone->uz_ctor(item, size, udata, flags) != 0) {
2865                 counter_u64_add(zone->uz_fails, 1);
2866                 zone_free_item(zone, item, udata, SKIP_DTOR | SKIP_CNT);
2867                 return (NULL);
2868         }
2869 #ifdef INVARIANTS
2870         if (!skipdbg)
2871                 uma_dbg_alloc(zone, NULL, item);
2872 #endif
2873         if (flags & M_ZERO)
2874                 bzero(item, size);
2875
2876         return (item);
2877 }
2878
2879 static inline void
2880 item_dtor(uma_zone_t zone, void *item, int size, void *udata,
2881     enum zfreeskip skip)
2882 {
2883 #ifdef INVARIANTS
2884         bool skipdbg;
2885
2886         skipdbg = uma_dbg_zskip(zone, item);
2887         if (skip == SKIP_NONE && !skipdbg) {
2888                 if ((zone->uz_flags & UMA_ZONE_MALLOC) != 0)
2889                         uma_dbg_free(zone, udata, item);
2890                 else
2891                         uma_dbg_free(zone, NULL, item);
2892         }
2893 #endif
2894         if (__predict_true(skip < SKIP_DTOR)) {
2895                 if (zone->uz_dtor != NULL)
2896                         zone->uz_dtor(item, size, udata);
2897 #ifdef INVARIANTS
2898                 if (!skipdbg && (zone->uz_flags & UMA_ZFLAG_TRASH) != 0 &&
2899                     zone->uz_dtor != trash_dtor)
2900                         trash_dtor(item, size, udata);
2901 #endif
2902         }
2903 }
2904
2905 /* See uma.h */
2906 void *
2907 uma_zalloc_arg(uma_zone_t zone, void *udata, int flags)
2908 {
2909         uma_cache_bucket_t bucket;
2910         uma_cache_t cache;
2911         void *item;
2912         int domain, size, uz_flags;
2913
2914         /* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
2915         random_harvest_fast_uma(&zone, sizeof(zone), RANDOM_UMA);
2916
2917         /* This is the fast path allocation */
2918         CTR3(KTR_UMA, "uma_zalloc_arg zone %s(%p) flags %d", zone->uz_name,
2919             zone, flags);
2920
2921 #ifdef WITNESS
2922         if (flags & M_WAITOK) {
2923                 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2924                     "uma_zalloc_arg: zone \"%s\"", zone->uz_name);
2925         }
2926 #endif
2927
2928 #ifdef INVARIANTS
2929         KASSERT((flags & M_EXEC) == 0, ("uma_zalloc_arg: called with M_EXEC"));
2930         KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
2931             ("uma_zalloc_arg: called with spinlock or critical section held"));
2932         if (zone->uz_flags & UMA_ZONE_PCPU)
2933                 KASSERT((flags & M_ZERO) == 0, ("allocating from a pcpu zone "
2934                     "with M_ZERO passed"));
2935 #endif
2936
2937 #ifdef DEBUG_MEMGUARD
2938         if (memguard_cmp_zone(zone)) {
2939                 item = memguard_alloc(zone->uz_size, flags);
2940                 if (item != NULL) {
2941                         if (zone->uz_init != NULL &&
2942                             zone->uz_init(item, zone->uz_size, flags) != 0)
2943                                 return (NULL);
2944                         if (zone->uz_ctor != NULL &&
2945                             zone->uz_ctor(item, zone->uz_size, udata,
2946                             flags) != 0) {
2947                                 counter_u64_add(zone->uz_fails, 1);
2948                                 zone->uz_fini(item, zone->uz_size);
2949                                 return (NULL);
2950                         }
2951                         return (item);
2952                 }
2953                 /* This is unfortunate but should not be fatal. */
2954         }
2955 #endif
2956         /*
2957          * If possible, allocate from the per-CPU cache.  There are two
2958          * requirements for safe access to the per-CPU cache: (1) the thread
2959          * accessing the cache must not be preempted or yield during access,
2960          * and (2) the thread must not migrate CPUs without switching which
2961          * cache it accesses.  We rely on a critical section to prevent
2962          * preemption and migration.  We release the critical section in
2963          * order to acquire the zone mutex if we are unable to allocate from
2964          * the current cache; when we re-acquire the critical section, we
2965          * must detect and handle migration if it has occurred.
2966          */
2967         critical_enter();
2968         do {
2969                 cache = &zone->uz_cpu[curcpu];
2970                 bucket = &cache->uc_allocbucket;
2971                 size = cache_uz_size(cache);
2972                 uz_flags = cache_uz_flags(cache);
2973                 if (__predict_true(bucket->ucb_cnt != 0)) {
2974                         item = cache_bucket_pop(cache, bucket);
2975                         critical_exit();
2976                         if (__predict_false((uz_flags & UMA_ZFLAG_CTORDTOR) != 0 ||
2977                             UMA_ALWAYS_CTORDTOR))
2978                                 return (item_ctor(zone, size, udata, flags, item));
2979                         if (flags & M_ZERO)
2980                                 bzero(item, size);
2981                         return (item);
2982                 }
2983         } while (cache_alloc(zone, cache, udata, flags));
2984         critical_exit();
2985
2986         /*
2987          * We can not get a bucket so try to return a single item.
2988          */
2989         if (uz_flags & UMA_ZONE_FIRSTTOUCH)
2990                 domain = PCPU_GET(domain);
2991         else
2992                 domain = UMA_ANYDOMAIN;
2993         return (zone_alloc_item(zone, udata, domain, flags));
2994 }
2995
2996 /*
2997  * Replenish an alloc bucket and possibly restore an old one.  Called in
2998  * a critical section.  Returns in a critical section.
2999  *
3000  * A false return value indicates an allocation failure.
3001  * A true return value indicates success and the caller should retry.
3002  */
3003 static __noinline bool
3004 cache_alloc(uma_zone_t zone, uma_cache_t cache, void *udata, int flags)
3005 {
3006         uma_zone_domain_t zdom;
3007         uma_bucket_t bucket;
3008         int domain;
3009         bool lockfail;
3010
3011         CRITICAL_ASSERT(curthread);
3012
3013         /*
3014          * If we have run out of items in our alloc bucket see
3015          * if we can switch with the free bucket.
3016          */
3017         if (cache->uc_freebucket.ucb_cnt != 0) {
3018                 cache_bucket_swap(&cache->uc_freebucket, &cache->uc_allocbucket);
3019                 return (true);
3020         }
3021
3022         /*
3023          * Discard any empty allocation bucket while we hold no locks.
3024          */
3025         bucket = cache_bucket_unload_alloc(cache);
3026         critical_exit();
3027         if (bucket != NULL)
3028                 bucket_free(zone, bucket, udata);
3029
3030         /* Short-circuit for zones without buckets and low memory. */
3031         if (zone->uz_bucket_size == 0 || bucketdisable) {
3032                 critical_enter();
3033                 return (false);
3034         }
3035
3036         /*
3037          * Attempt to retrieve the item from the per-CPU cache has failed, so
3038          * we must go back to the zone.  This requires the zone lock, so we
3039          * must drop the critical section, then re-acquire it when we go back
3040          * to the cache.  Since the critical section is released, we may be
3041          * preempted or migrate.  As such, make sure not to maintain any
3042          * thread-local state specific to the cache from prior to releasing
3043          * the critical section.
3044          */
3045         lockfail = 0;
3046         if (ZONE_TRYLOCK(zone) == 0) {
3047                 /* Record contention to size the buckets. */
3048                 ZONE_LOCK(zone);
3049                 lockfail = 1;
3050         }
3051
3052         /* See if we lost the race to fill the cache. */
3053         critical_enter();
3054         cache = &zone->uz_cpu[curcpu];
3055         if (cache->uc_allocbucket.ucb_bucket != NULL) {
3056                 ZONE_UNLOCK(zone);
3057                 return (true);
3058         }
3059
3060         /*
3061          * Check the zone's cache of buckets.
3062          */
3063         if (zone->uz_flags & UMA_ZONE_FIRSTTOUCH) {
3064                 domain = PCPU_GET(domain);
3065                 zdom = &zone->uz_domain[domain];
3066         } else {
3067                 domain = UMA_ANYDOMAIN;
3068                 zdom = &zone->uz_domain[0];
3069         }
3070
3071         if ((bucket = zone_fetch_bucket(zone, zdom)) != NULL) {
3072                 ZONE_UNLOCK(zone);
3073                 KASSERT(bucket->ub_cnt != 0,
3074                     ("uma_zalloc_arg: Returning an empty bucket."));
3075                 cache_bucket_load_alloc(cache, bucket);
3076                 return (true);
3077         }
3078         /* We are no longer associated with this CPU. */
3079         critical_exit();
3080
3081         /*
3082          * We bump the uz count when the cache size is insufficient to
3083          * handle the working set.
3084          */
3085         if (lockfail && zone->uz_bucket_size < zone->uz_bucket_size_max)
3086                 zone->uz_bucket_size++;
3087         ZONE_UNLOCK(zone);
3088
3089         /*
3090          * Fill a bucket and attempt to use it as the alloc bucket.
3091          */
3092         bucket = zone_alloc_bucket(zone, udata, domain, flags);
3093         CTR3(KTR_UMA, "uma_zalloc: zone %s(%p) bucket zone returned %p",
3094             zone->uz_name, zone, bucket);
3095         if (bucket == NULL) {
3096                 critical_enter();
3097                 return (false);
3098         }
3099
3100         /*
3101          * See if we lost the race or were migrated.  Cache the
3102          * initialized bucket to make this less likely or claim
3103          * the memory directly.
3104          */
3105         ZONE_LOCK(zone);
3106         critical_enter();
3107         cache = &zone->uz_cpu[curcpu];
3108         if (cache->uc_allocbucket.ucb_bucket == NULL &&
3109             ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) == 0 ||
3110             domain == PCPU_GET(domain))) {
3111                 cache_bucket_load_alloc(cache, bucket);
3112                 zdom->uzd_imax += bucket->ub_cnt;
3113         } else if (zone->uz_bkt_count >= zone->uz_bkt_max) {
3114                 critical_exit();
3115                 ZONE_UNLOCK(zone);
3116                 bucket_drain(zone, bucket);
3117                 bucket_free(zone, bucket, udata);
3118                 critical_enter();
3119                 return (true);
3120         } else
3121                 zone_put_bucket(zone, zdom, bucket, false);
3122         ZONE_UNLOCK(zone);
3123         return (true);
3124 }
3125
3126 void *
3127 uma_zalloc_domain(uma_zone_t zone, void *udata, int domain, int flags)
3128 {
3129
3130         /* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
3131         random_harvest_fast_uma(&zone, sizeof(zone), RANDOM_UMA);
3132
3133         /* This is the fast path allocation */
3134         CTR4(KTR_UMA, "uma_zalloc_domain zone %s(%p) domain %d flags %d",
3135             zone->uz_name, zone, domain, flags);
3136
3137         if (flags & M_WAITOK) {
3138                 WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
3139                     "uma_zalloc_domain: zone \"%s\"", zone->uz_name);
3140         }
3141         KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
3142             ("uma_zalloc_domain: called with spinlock or critical section held"));
3143
3144         return (zone_alloc_item(zone, udata, domain, flags));
3145 }
3146
3147 /*
3148  * Find a slab with some space.  Prefer slabs that are partially used over those
3149  * that are totally full.  This helps to reduce fragmentation.
3150  *
3151  * If 'rr' is 1, search all domains starting from 'domain'.  Otherwise check
3152  * only 'domain'.
3153  */
3154 static uma_slab_t
3155 keg_first_slab(uma_keg_t keg, int domain, bool rr)
3156 {
3157         uma_domain_t dom;
3158         uma_slab_t slab;
3159         int start;
3160
3161         KASSERT(domain >= 0 && domain < vm_ndomains,
3162             ("keg_first_slab: domain %d out of range", domain));
3163         KEG_LOCK_ASSERT(keg, domain);
3164
3165         slab = NULL;
3166         start = domain;
3167         do {
3168                 dom = &keg->uk_domain[domain];
3169                 if (!LIST_EMPTY(&dom->ud_part_slab))
3170                         return (LIST_FIRST(&dom->ud_part_slab));
3171                 if (!LIST_EMPTY(&dom->ud_free_slab)) {
3172                         slab = LIST_FIRST(&dom->ud_free_slab);
3173                         LIST_REMOVE(slab, us_link);
3174                         LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
3175                         return (slab);
3176                 }
3177                 if (rr)
3178                         domain = (domain + 1) % vm_ndomains;
3179         } while (domain != start);
3180
3181         return (NULL);
3182 }
3183
3184 /*
3185  * Fetch an existing slab from a free or partial list.  Returns with the
3186  * keg domain lock held if a slab was found or unlocked if not.
3187  */
3188 static uma_slab_t
3189 keg_fetch_free_slab(uma_keg_t keg, int domain, bool rr, int flags)
3190 {
3191         uma_slab_t slab;
3192         uint32_t reserve;
3193
3194         /* HASH has a single free list. */
3195         if ((keg->uk_flags & UMA_ZFLAG_HASH) != 0)
3196                 domain = 0;
3197
3198         KEG_LOCK(keg, domain);
3199         reserve = (flags & M_USE_RESERVE) != 0 ? 0 : keg->uk_reserve;
3200         if (keg->uk_domain[domain].ud_free <= reserve ||
3201             (slab = keg_first_slab(keg, domain, rr)) == NULL) {
3202                 KEG_UNLOCK(keg, domain);
3203                 return (NULL);
3204         }
3205         return (slab);
3206 }
3207
3208 static uma_slab_t
3209 keg_fetch_slab(uma_keg_t keg, uma_zone_t zone, int rdomain, const int flags)
3210 {
3211         struct vm_domainset_iter di;
3212         uma_slab_t slab;
3213         int aflags, domain;
3214         bool rr;
3215
3216 restart:
3217         /*
3218          * Use the keg's policy if upper layers haven't already specified a
3219          * domain (as happens with first-touch zones).
3220          *
3221          * To avoid races we run the iterator with the keg lock held, but that
3222          * means that we cannot allow the vm_domainset layer to sleep.  Thus,
3223          * clear M_WAITOK and handle low memory conditions locally.
3224          */
3225         rr = rdomain == UMA_ANYDOMAIN;
3226         if (rr) {
3227                 aflags = (flags & ~M_WAITOK) | M_NOWAIT;
3228                 vm_domainset_iter_policy_ref_init(&di, &keg->uk_dr, &domain,
3229                     &aflags);
3230         } else {
3231                 aflags = flags;
3232                 domain = rdomain;
3233         }
3234
3235         for (;;) {
3236                 slab = keg_fetch_free_slab(keg, domain, rr, flags);
3237                 if (slab != NULL)
3238                         return (slab);
3239
3240                 /*
3241                  * M_NOVM means don't ask at all!
3242                  */
3243                 if (flags & M_NOVM)
3244                         break;
3245
3246                 slab = keg_alloc_slab(keg, zone, domain, flags, aflags);
3247                 if (slab != NULL)
3248                         return (slab);
3249                 if (!rr && (flags & M_WAITOK) == 0)
3250                         break;
3251                 if (rr && vm_domainset_iter_policy(&di, &domain) != 0) {
3252                         if ((flags & M_WAITOK) != 0) {
3253                                 vm_wait_doms(&keg->uk_dr.dr_policy->ds_mask);
3254                                 goto restart;
3255                         }
3256                         break;
3257                 }
3258         }
3259
3260         /*
3261          * We might not have been able to get a slab but another cpu
3262          * could have while we were unlocked.  Check again before we
3263          * fail.
3264          */
3265         if ((slab = keg_fetch_free_slab(keg, domain, rr, flags)) != NULL)
3266                 return (slab);
3267
3268         return (NULL);
3269 }
3270
3271 static void *
3272 slab_alloc_item(uma_keg_t keg, uma_slab_t slab)
3273 {
3274         uma_domain_t dom;
3275         void *item;
3276         int freei;
3277
3278         KEG_LOCK_ASSERT(keg, slab->us_domain);
3279
3280         dom = &keg->uk_domain[slab->us_domain];
3281         freei = BIT_FFS(keg->uk_ipers, &slab->us_free) - 1;
3282         BIT_CLR(keg->uk_ipers, freei, &slab->us_free);
3283         item = slab_item(slab, keg, freei);
3284         slab->us_freecount--;
3285         dom->ud_free--;
3286
3287         /* Move this slab to the full list */
3288         if (slab->us_freecount == 0) {
3289                 LIST_REMOVE(slab, us_link);
3290                 LIST_INSERT_HEAD(&dom->ud_full_slab, slab, us_link);
3291         }
3292
3293         return (item);
3294 }
3295
3296 static int
3297 zone_import(void *arg, void **bucket, int max, int domain, int flags)
3298 {
3299         uma_domain_t dom;
3300         uma_zone_t zone;
3301         uma_slab_t slab;
3302         uma_keg_t keg;
3303 #ifdef NUMA
3304         int stripe;
3305 #endif
3306         int i;
3307
3308         zone = arg;
3309         slab = NULL;
3310         keg = zone->uz_keg;
3311         /* Try to keep the buckets totally full */
3312         for (i = 0; i < max; ) {
3313                 if ((slab = keg_fetch_slab(keg, zone, domain, flags)) == NULL)
3314                         break;
3315 #ifdef NUMA
3316                 stripe = howmany(max, vm_ndomains);
3317 #endif
3318                 dom = &keg->uk_domain[slab->us_domain];
3319                 while (slab->us_freecount && i < max) {
3320                         bucket[i++] = slab_alloc_item(keg, slab);
3321                         if (dom->ud_free <= keg->uk_reserve)
3322                                 break;
3323 #ifdef NUMA
3324                         /*
3325                          * If the zone is striped we pick a new slab for every
3326                          * N allocations.  Eliminating this conditional will
3327                          * instead pick a new domain for each bucket rather
3328                          * than stripe within each bucket.  The current option
3329                          * produces more fragmentation and requires more cpu
3330                          * time but yields better distribution.
3331                          */
3332                         if ((zone->uz_flags & UMA_ZONE_ROUNDROBIN) != 0 &&
3333                             vm_ndomains > 1 && --stripe == 0)
3334                                 break;
3335 #endif
3336                 }
3337                 KEG_UNLOCK(keg, slab->us_domain);
3338                 /* Don't block if we allocated any successfully. */
3339                 flags &= ~M_WAITOK;
3340                 flags |= M_NOWAIT;
3341         }
3342
3343         return i;
3344 }
3345
3346 static int
3347 zone_alloc_limit_hard(uma_zone_t zone, int count, int flags)
3348 {
3349         uint64_t old, new, total, max;
3350
3351         /*
3352          * The hard case.  We're going to sleep because there were existing
3353          * sleepers or because we ran out of items.  This routine enforces
3354          * fairness by keeping fifo order.
3355          *
3356          * First release our ill gotten gains and make some noise.
3357          */
3358         for (;;) {
3359                 zone_free_limit(zone, count);
3360                 zone_log_warning(zone);
3361                 zone_maxaction(zone);
3362                 if (flags & M_NOWAIT)
3363                         return (0);
3364
3365                 /*
3366                  * We need to allocate an item or set ourself as a sleeper
3367                  * while the sleepq lock is held to avoid wakeup races.  This
3368                  * is essentially a home rolled semaphore.
3369                  */
3370                 sleepq_lock(&zone->uz_max_items);
3371                 old = zone->uz_items;
3372                 do {
3373                         MPASS(UZ_ITEMS_SLEEPERS(old) < UZ_ITEMS_SLEEPERS_MAX);
3374                         /* Cache the max since we will evaluate twice. */
3375                         max = zone->uz_max_items;
3376                         if (UZ_ITEMS_SLEEPERS(old) != 0 ||
3377                             UZ_ITEMS_COUNT(old) >= max)
3378                                 new = old + UZ_ITEMS_SLEEPER;
3379                         else
3380                                 new = old + MIN(count, max - old);
3381                 } while (atomic_fcmpset_64(&zone->uz_items, &old, new) == 0);
3382
3383                 /* We may have successfully allocated under the sleepq lock. */
3384                 if (UZ_ITEMS_SLEEPERS(new) == 0) {
3385                         sleepq_release(&zone->uz_max_items);
3386                         return (new - old);
3387                 }
3388
3389                 /*
3390                  * This is in a different cacheline from uz_items so that we
3391                  * don't constantly invalidate the fastpath cacheline when we
3392                  * adjust item counts.  This could be limited to toggling on
3393                  * transitions.
3394                  */
3395                 atomic_add_32(&zone->uz_sleepers, 1);
3396                 atomic_add_64(&zone->uz_sleeps, 1);
3397
3398                 /*
3399                  * We have added ourselves as a sleeper.  The sleepq lock
3400                  * protects us from wakeup races.  Sleep now and then retry.
3401                  */
3402                 sleepq_add(&zone->uz_max_items, NULL, "zonelimit", 0, 0);
3403                 sleepq_wait(&zone->uz_max_items, PVM);
3404
3405                 /*
3406                  * After wakeup, remove ourselves as a sleeper and try
3407                  * again.  We no longer have the sleepq lock for protection.
3408                  *
3409                  * Subract ourselves as a sleeper while attempting to add
3410                  * our count.
3411                  */
3412                 atomic_subtract_32(&zone->uz_sleepers, 1);
3413                 old = atomic_fetchadd_64(&zone->uz_items,
3414                     -(UZ_ITEMS_SLEEPER - count));
3415                 /* We're no longer a sleeper. */
3416                 old -= UZ_ITEMS_SLEEPER;
3417
3418                 /*
3419                  * If we're still at the limit, restart.  Notably do not
3420                  * block on other sleepers.  Cache the max value to protect
3421                  * against changes via sysctl.
3422                  */
3423                 total = UZ_ITEMS_COUNT(old);
3424                 max = zone->uz_max_items;
3425                 if (total >= max)
3426                         continue;
3427                 /* Truncate if necessary, otherwise wake other sleepers. */
3428                 if (total + count > max) {
3429                         zone_free_limit(zone, total + count - max);
3430                         count = max - total;
3431                 } else if (total + count < max && UZ_ITEMS_SLEEPERS(old) != 0)
3432                         wakeup_one(&zone->uz_max_items);
3433
3434                 return (count);
3435         }
3436 }
3437
3438 /*
3439  * Allocate 'count' items from our max_items limit.  Returns the number
3440  * available.  If M_NOWAIT is not specified it will sleep until at least
3441  * one item can be allocated.
3442  */
3443 static int
3444 zone_alloc_limit(uma_zone_t zone, int count, int flags)
3445 {
3446         uint64_t old;
3447         uint64_t max;
3448
3449         max = zone->uz_max_items;
3450         MPASS(max > 0);
3451
3452         /*
3453          * We expect normal allocations to succeed with a simple
3454          * fetchadd.
3455          */
3456         old = atomic_fetchadd_64(&zone->uz_items, count);
3457         if (__predict_true(old + count <= max))
3458                 return (count);
3459
3460         /*
3461          * If we had some items and no sleepers just return the
3462          * truncated value.  We have to release the excess space
3463          * though because that may wake sleepers who weren't woken
3464          * because we were temporarily over the limit.
3465          */
3466         if (old < max) {
3467                 zone_free_limit(zone, (old + count) - max);
3468                 return (max - old);
3469         }
3470         return (zone_alloc_limit_hard(zone, count, flags));
3471 }
3472
3473 /*
3474  * Free a number of items back to the limit.
3475  */
3476 static void
3477 zone_free_limit(uma_zone_t zone, int count)
3478 {
3479         uint64_t old;
3480
3481         MPASS(count > 0);
3482
3483         /*
3484          * In the common case we either have no sleepers or
3485          * are still over the limit and can just return.
3486          */
3487         old = atomic_fetchadd_64(&zone->uz_items, -count);
3488         if (__predict_true(UZ_ITEMS_SLEEPERS(old) == 0 ||
3489            UZ_ITEMS_COUNT(old) - count >= zone->uz_max_items))
3490                 return;
3491
3492         /*
3493          * Moderate the rate of wakeups.  Sleepers will continue
3494          * to generate wakeups if necessary.
3495          */
3496         wakeup_one(&zone->uz_max_items);
3497 }
3498
3499 static uma_bucket_t
3500 zone_alloc_bucket(uma_zone_t zone, void *udata, int domain, int flags)
3501 {
3502         uma_bucket_t bucket;
3503         int maxbucket, cnt;
3504
3505         CTR3(KTR_UMA, "zone_alloc_bucket zone %s(%p) domain %d", zone->uz_name,
3506             zone, domain);
3507
3508         /* Avoid allocs targeting empty domains. */
3509         if (domain != UMA_ANYDOMAIN && VM_DOMAIN_EMPTY(domain))
3510                 domain = UMA_ANYDOMAIN;
3511
3512         if (zone->uz_max_items > 0)
3513                 maxbucket = zone_alloc_limit(zone, zone->uz_bucket_size,
3514                     M_NOWAIT);
3515         else
3516                 maxbucket = zone->uz_bucket_size;
3517         if (maxbucket == 0)
3518                 return (false);
3519
3520         /* Don't wait for buckets, preserve caller's NOVM setting. */
3521         bucket = bucket_alloc(zone, udata, M_NOWAIT | (flags & M_NOVM));
3522         if (bucket == NULL) {
3523                 cnt = 0;
3524                 goto out;
3525         }
3526
3527         bucket->ub_cnt = zone->uz_import(zone->uz_arg, bucket->ub_bucket,
3528             MIN(maxbucket, bucket->ub_entries), domain, flags);
3529
3530         /*
3531          * Initialize the memory if necessary.
3532          */
3533         if (bucket->ub_cnt != 0 && zone->uz_init != NULL) {
3534                 int i;
3535
3536                 for (i = 0; i < bucket->ub_cnt; i++)
3537                         if (zone->uz_init(bucket->ub_bucket[i], zone->uz_size,
3538                             flags) != 0)
3539                                 break;
3540                 /*
3541                  * If we couldn't initialize the whole bucket, put the
3542                  * rest back onto the freelist.
3543                  */
3544                 if (i != bucket->ub_cnt) {
3545                         zone->uz_release(zone->uz_arg, &bucket->ub_bucket[i],
3546                             bucket->ub_cnt - i);
3547 #ifdef INVARIANTS
3548                         bzero(&bucket->ub_bucket[i],
3549                             sizeof(void *) * (bucket->ub_cnt - i));
3550 #endif
3551                         bucket->ub_cnt = i;
3552                 }
3553         }
3554
3555         cnt = bucket->ub_cnt;
3556         if (bucket->ub_cnt == 0) {
3557                 bucket_free(zone, bucket, udata);
3558                 counter_u64_add(zone->uz_fails, 1);
3559                 bucket = NULL;
3560         }
3561 out:
3562         if (zone->uz_max_items > 0 && cnt < maxbucket)
3563                 zone_free_limit(zone, maxbucket - cnt);
3564
3565         return (bucket);
3566 }
3567
3568 /*
3569  * Allocates a single item from a zone.
3570  *
3571  * Arguments
3572  *      zone   The zone to alloc for.
3573  *      udata  The data to be passed to the constructor.
3574  *      domain The domain to allocate from or UMA_ANYDOMAIN.
3575  *      flags  M_WAITOK, M_NOWAIT, M_ZERO.
3576  *
3577  * Returns
3578  *      NULL if there is no memory and M_NOWAIT is set
3579  *      An item if successful
3580  */
3581
3582 static void *
3583 zone_alloc_item(uma_zone_t zone, void *udata, int domain, int flags)
3584 {
3585         void *item;
3586
3587         if (zone->uz_max_items > 0 && zone_alloc_limit(zone, 1, flags) == 0)
3588                 return (NULL);
3589
3590         /* Avoid allocs targeting empty domains. */
3591         if (domain != UMA_ANYDOMAIN && VM_DOMAIN_EMPTY(domain))
3592                 domain = UMA_ANYDOMAIN;
3593
3594         if (zone->uz_import(zone->uz_arg, &item, 1, domain, flags) != 1)
3595                 goto fail_cnt;
3596
3597         /*
3598          * We have to call both the zone's init (not the keg's init)
3599          * and the zone's ctor.  This is because the item is going from
3600          * a keg slab directly to the user, and the user is expecting it
3601          * to be both zone-init'd as well as zone-ctor'd.
3602          */
3603         if (zone->uz_init != NULL) {
3604                 if (zone->uz_init(item, zone->uz_size, flags) != 0) {
3605                         zone_free_item(zone, item, udata, SKIP_FINI | SKIP_CNT);
3606                         goto fail_cnt;
3607                 }
3608         }
3609         item = item_ctor(zone, zone->uz_size, udata, flags, item);
3610         if (item == NULL)
3611                 goto fail;
3612
3613         counter_u64_add(zone->uz_allocs, 1);
3614         CTR3(KTR_UMA, "zone_alloc_item item %p from %s(%p)", item,
3615             zone->uz_name, zone);
3616
3617         return (item);
3618
3619 fail_cnt:
3620         counter_u64_add(zone->uz_fails, 1);
3621 fail:
3622         if (zone->uz_max_items > 0)
3623                 zone_free_limit(zone, 1);
3624         CTR2(KTR_UMA, "zone_alloc_item failed from %s(%p)",
3625             zone->uz_name, zone);
3626
3627         return (NULL);
3628 }
3629
3630 /* See uma.h */
3631 void
3632 uma_zfree_arg(uma_zone_t zone, void *item, void *udata)
3633 {
3634         uma_cache_t cache;
3635         uma_cache_bucket_t bucket;
3636         int domain, itemdomain, uz_flags;
3637
3638         /* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
3639         random_harvest_fast_uma(&zone, sizeof(zone), RANDOM_UMA);
3640
3641         CTR2(KTR_UMA, "uma_zfree_arg zone %s(%p)", zone->uz_name, zone);
3642
3643         KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
3644             ("uma_zfree_arg: called with spinlock or critical section held"));
3645
3646         /* uma_zfree(..., NULL) does nothing, to match free(9). */
3647         if (item == NULL)
3648                 return;
3649 #ifdef DEBUG_MEMGUARD
3650         if (is_memguard_addr(item)) {
3651                 if (zone->uz_dtor != NULL)
3652                         zone->uz_dtor(item, zone->uz_size, udata);
3653                 if (zone->uz_fini != NULL)
3654                         zone->uz_fini(item, zone->uz_size);
3655                 memguard_free(item);
3656                 return;
3657         }
3658 #endif
3659
3660         /*
3661          * We are accessing the per-cpu cache without a critical section to
3662          * fetch size and flags.  This is acceptable, if we are preempted we
3663          * will simply read another cpu's line.
3664          */
3665         cache = &zone->uz_cpu[curcpu];
3666         uz_flags = cache_uz_flags(cache);
3667         if (__predict_false((uz_flags & UMA_ZFLAG_CTORDTOR) != 0 ||
3668             UMA_ALWAYS_CTORDTOR))
3669                 item_dtor(zone, item, cache_uz_size(cache), udata, SKIP_NONE);
3670
3671         /*
3672          * The race here is acceptable.  If we miss it we'll just have to wait
3673          * a little longer for the limits to be reset.
3674          */
3675         if (__predict_false(uz_flags & UMA_ZFLAG_LIMIT)) {
3676                 if (zone->uz_sleepers > 0)
3677                         goto zfree_item;
3678         }
3679
3680         /*
3681          * If possible, free to the per-CPU cache.  There are two
3682          * requirements for safe access to the per-CPU cache: (1) the thread
3683          * accessing the cache must not be preempted or yield during access,
3684          * and (2) the thread must not migrate CPUs without switching which
3685          * cache it accesses.  We rely on a critical section to prevent
3686          * preemption and migration.  We release the critical section in
3687          * order to acquire the zone mutex if we are unable to free to the
3688          * current cache; when we re-acquire the critical section, we must
3689          * detect and handle migration if it has occurred.
3690          */
3691         domain = itemdomain = 0;
3692 #ifdef NUMA
3693         if ((uz_flags & UMA_ZONE_FIRSTTOUCH) != 0)
3694                 itemdomain = _vm_phys_domain(pmap_kextract((vm_offset_t)item));
3695 #endif
3696         critical_enter();
3697         do {
3698                 cache = &zone->uz_cpu[curcpu];
3699 #ifdef NUMA
3700                 domain = PCPU_GET(domain);
3701                 if ((uz_flags & UMA_ZONE_FIRSTTOUCH) != 0 &&
3702                     domain != itemdomain) {
3703                         bucket = &cache->uc_crossbucket;
3704                 } else
3705 #endif
3706                 {
3707                         /*
3708                          * Try to free into the allocbucket first to give LIFO
3709                          * ordering for cache-hot datastructures.  Spill over
3710                          * into the freebucket if necessary.  Alloc will swap
3711                          * them if one runs dry.
3712                          */
3713                         bucket = &cache->uc_allocbucket;
3714                         if (__predict_false(bucket->ucb_cnt >=
3715                             bucket->ucb_entries))
3716                                 bucket = &cache->uc_freebucket;
3717                 }
3718                 if (__predict_true(bucket->ucb_cnt < bucket->ucb_entries)) {
3719                         cache_bucket_push(cache, bucket, item);
3720                         critical_exit();
3721                         return;
3722                 }
3723         } while (cache_free(zone, cache, udata, item, itemdomain));
3724         critical_exit();
3725
3726         /*
3727          * If nothing else caught this, we'll just do an internal free.
3728          */
3729 zfree_item:
3730         zone_free_item(zone, item, udata, SKIP_DTOR);
3731 }
3732
3733 #ifdef NUMA
3734 /*
3735  * sort crossdomain free buckets to domain correct buckets and cache
3736  * them.
3737  */
3738 static void
3739 zone_free_cross(uma_zone_t zone, uma_bucket_t bucket, void *udata)
3740 {
3741         struct uma_bucketlist fullbuckets;
3742         uma_zone_domain_t zdom;
3743         uma_bucket_t b;
3744         void *item;
3745         int domain;
3746
3747         CTR3(KTR_UMA,
3748             "uma_zfree: zone %s(%p) draining cross bucket %p",
3749             zone->uz_name, zone, bucket);
3750
3751         TAILQ_INIT(&fullbuckets);
3752
3753         /*
3754          * To avoid having ndomain * ndomain buckets for sorting we have a
3755          * lock on the current crossfree bucket.  A full matrix with
3756          * per-domain locking could be used if necessary.
3757          */
3758         ZONE_CROSS_LOCK(zone);
3759         while (bucket->ub_cnt > 0) {
3760                 item = bucket->ub_bucket[bucket->ub_cnt - 1];
3761                 domain = _vm_phys_domain(pmap_kextract((vm_offset_t)item));
3762                 zdom = &zone->uz_domain[domain];
3763                 if (zdom->uzd_cross == NULL) {
3764                         zdom->uzd_cross = bucket_alloc(zone, udata, M_NOWAIT);
3765                         if (zdom->uzd_cross == NULL)
3766                                 break;
3767                 }
3768                 zdom->uzd_cross->ub_bucket[zdom->uzd_cross->ub_cnt++] = item;
3769                 if (zdom->uzd_cross->ub_cnt == zdom->uzd_cross->ub_entries) {
3770                         TAILQ_INSERT_HEAD(&fullbuckets, zdom->uzd_cross,
3771                             ub_link);
3772                         zdom->uzd_cross = NULL;
3773                 }
3774                 bucket->ub_cnt--;
3775         }
3776         ZONE_CROSS_UNLOCK(zone);
3777         if (!TAILQ_EMPTY(&fullbuckets)) {
3778                 ZONE_LOCK(zone);
3779                 while ((b = TAILQ_FIRST(&fullbuckets)) != NULL) {
3780                         TAILQ_REMOVE(&fullbuckets, b, ub_link);
3781                         if (zone->uz_bkt_count >= zone->uz_bkt_max) {
3782                                 ZONE_UNLOCK(zone);
3783                                 bucket_drain(zone, b);
3784                                 bucket_free(zone, b, udata);
3785                                 ZONE_LOCK(zone);
3786                         } else {
3787                                 domain = _vm_phys_domain(
3788                                     pmap_kextract(
3789                                     (vm_offset_t)b->ub_bucket[0]));
3790                                 zdom = &zone->uz_domain[domain];
3791                                 zone_put_bucket(zone, zdom, b, true);
3792                         }
3793                 }
3794                 ZONE_UNLOCK(zone);
3795         }
3796         if (bucket->ub_cnt != 0)
3797                 bucket_drain(zone, bucket);
3798         bucket_free(zone, bucket, udata);
3799 }
3800 #endif
3801
3802 static void
3803 zone_free_bucket(uma_zone_t zone, uma_bucket_t bucket, void *udata,
3804     int domain, int itemdomain)
3805 {
3806         uma_zone_domain_t zdom;
3807
3808 #ifdef NUMA
3809         /*
3810          * Buckets coming from the wrong domain will be entirely for the
3811          * only other domain on two domain systems.  In this case we can
3812          * simply cache them.  Otherwise we need to sort them back to
3813          * correct domains.
3814          */
3815         if (domain != itemdomain && vm_ndomains > 2) {
3816                 zone_free_cross(zone, bucket, udata);
3817                 return;
3818         }
3819 #endif
3820
3821         /*
3822          * Attempt to save the bucket in the zone's domain bucket cache.
3823          *
3824          * We bump the uz count when the cache size is insufficient to
3825          * handle the working set.
3826          */
3827         if (ZONE_TRYLOCK(zone) == 0) {
3828                 /* Record contention to size the buckets. */
3829                 ZONE_LOCK(zone);
3830                 if (zone->uz_bucket_size < zone->uz_bucket_size_max)
3831                         zone->uz_bucket_size++;
3832         }
3833
3834         CTR3(KTR_UMA,
3835             "uma_zfree: zone %s(%p) putting bucket %p on free list",
3836             zone->uz_name, zone, bucket);
3837         /* ub_cnt is pointing to the last free item */
3838         KASSERT(bucket->ub_cnt == bucket->ub_entries,
3839             ("uma_zfree: Attempting to insert partial  bucket onto the full list.\n"));
3840         if (zone->uz_bkt_count >= zone->uz_bkt_max) {
3841                 ZONE_UNLOCK(zone);
3842                 bucket_drain(zone, bucket);
3843                 bucket_free(zone, bucket, udata);
3844         } else {
3845                 zdom = &zone->uz_domain[itemdomain];
3846                 zone_put_bucket(zone, zdom, bucket, true);
3847                 ZONE_UNLOCK(zone);
3848         }
3849 }
3850
3851 /*
3852  * Populate a free or cross bucket for the current cpu cache.  Free any
3853  * existing full bucket either to the zone cache or back to the slab layer.
3854  *
3855  * Enters and returns in a critical section.  false return indicates that
3856  * we can not satisfy this free in the cache layer.  true indicates that
3857  * the caller should retry.
3858  */
3859 static __noinline bool
3860 cache_free(uma_zone_t zone, uma_cache_t cache, void *udata, void *item,
3861     int itemdomain)
3862 {
3863         uma_cache_bucket_t cbucket;
3864         uma_bucket_t bucket;
3865         int domain;
3866
3867         CRITICAL_ASSERT(curthread);
3868
3869         if (zone->uz_bucket_size == 0 || bucketdisable)
3870                 return false;
3871
3872         cache = &zone->uz_cpu[curcpu];
3873
3874         /*
3875          * FIRSTTOUCH domains need to free to the correct zdom.  When
3876          * enabled this is the zdom of the item.   The bucket is the
3877          * cross bucket if the current domain and itemdomain do not match.
3878          */
3879         cbucket = &cache->uc_freebucket;
3880 #ifdef NUMA
3881         if ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) != 0) {
3882                 domain = PCPU_GET(domain);
3883                 if (domain != itemdomain) {
3884                         cbucket = &cache->uc_crossbucket;
3885                         if (cbucket->ucb_cnt != 0)
3886                                 atomic_add_64(&zone->uz_xdomain,
3887                                     cbucket->ucb_cnt);
3888                 }
3889         } else
3890 #endif
3891                 itemdomain = domain = 0;
3892         bucket = cache_bucket_unload(cbucket);
3893
3894         /* We are no longer associated with this CPU. */
3895         critical_exit();
3896
3897         if (bucket != NULL)
3898                 zone_free_bucket(zone, bucket, udata, domain, itemdomain);
3899
3900         bucket = bucket_alloc(zone, udata, M_NOWAIT);
3901         CTR3(KTR_UMA, "uma_zfree: zone %s(%p) allocated bucket %p",
3902             zone->uz_name, zone, bucket);
3903         critical_enter();
3904         if (bucket == NULL)
3905                 return (false);
3906         cache = &zone->uz_cpu[curcpu];
3907 #ifdef NUMA
3908         /*
3909          * Check to see if we should be populating the cross bucket.  If it
3910          * is already populated we will fall through and attempt to populate
3911          * the free bucket.
3912          */
3913         if ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) != 0) {
3914                 domain = PCPU_GET(domain);
3915                 if (domain != itemdomain &&
3916                     cache->uc_crossbucket.ucb_bucket == NULL) {
3917                         cache_bucket_load_cross(cache, bucket);
3918                         return (true);
3919                 }
3920         }
3921 #endif
3922         /*
3923          * We may have lost the race to fill the bucket or switched CPUs.
3924          */
3925         if (cache->uc_freebucket.ucb_bucket != NULL) {
3926                 critical_exit();
3927                 bucket_free(zone, bucket, udata);
3928                 critical_enter();
3929         } else
3930                 cache_bucket_load_free(cache, bucket);
3931
3932         return (true);
3933 }
3934
3935 void
3936 uma_zfree_domain(uma_zone_t zone, void *item, void *udata)
3937 {
3938
3939         /* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
3940         random_harvest_fast_uma(&zone, sizeof(zone), RANDOM_UMA);
3941
3942         CTR2(KTR_UMA, "uma_zfree_domain zone %s(%p)", zone->uz_name, zone);
3943
3944         KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
3945             ("uma_zfree_domain: called with spinlock or critical section held"));
3946
3947         /* uma_zfree(..., NULL) does nothing, to match free(9). */
3948         if (item == NULL)
3949                 return;
3950         zone_free_item(zone, item, udata, SKIP_NONE);
3951 }
3952
3953 static void
3954 slab_free_item(uma_zone_t zone, uma_slab_t slab, void *item)
3955 {
3956         uma_keg_t keg;
3957         uma_domain_t dom;
3958         int freei;
3959
3960         keg = zone->uz_keg;
3961         KEG_LOCK_ASSERT(keg, slab->us_domain);
3962
3963         /* Do we need to remove from any lists? */
3964         dom = &keg->uk_domain[slab->us_domain];
3965         if (slab->us_freecount+1 == keg->uk_ipers) {
3966                 LIST_REMOVE(slab, us_link);
3967                 LIST_INSERT_HEAD(&dom->ud_free_slab, slab, us_link);
3968         } else if (slab->us_freecount == 0) {
3969                 LIST_REMOVE(slab, us_link);
3970                 LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
3971         }
3972
3973         /* Slab management. */
3974         freei = slab_item_index(slab, keg, item);
3975         BIT_SET(keg->uk_ipers, freei, &slab->us_free);
3976         slab->us_freecount++;
3977
3978         /* Keg statistics. */
3979         dom->ud_free++;
3980 }
3981
3982 static void
3983 zone_release(void *arg, void **bucket, int cnt)
3984 {
3985         struct mtx *lock;
3986         uma_zone_t zone;
3987         uma_slab_t slab;
3988         uma_keg_t keg;
3989         uint8_t *mem;
3990         void *item;
3991         int i;
3992
3993         zone = arg;
3994         keg = zone->uz_keg;
3995         lock = NULL;
3996         if (__predict_false((zone->uz_flags & UMA_ZFLAG_HASH) != 0))
3997                 lock = KEG_LOCK(keg, 0);
3998         for (i = 0; i < cnt; i++) {
3999                 item = bucket[i];
4000                 if (__predict_true((zone->uz_flags & UMA_ZFLAG_VTOSLAB) != 0)) {
4001                         slab = vtoslab((vm_offset_t)item);
4002                 } else {
4003                         mem = (uint8_t *)((uintptr_t)item & (~UMA_SLAB_MASK));
4004                         if ((zone->uz_flags & UMA_ZFLAG_HASH) != 0)
4005                                 slab = hash_sfind(&keg->uk_hash, mem);
4006                         else
4007                                 slab = (uma_slab_t)(mem + keg->uk_pgoff);
4008                 }
4009                 if (lock != KEG_LOCKPTR(keg, slab->us_domain)) {
4010                         if (lock != NULL)
4011                                 mtx_unlock(lock);
4012                         lock = KEG_LOCK(keg, slab->us_domain);
4013                 }
4014                 slab_free_item(zone, slab, item);
4015         }
4016         if (lock != NULL)
4017                 mtx_unlock(lock);
4018 }
4019
4020 /*
4021  * Frees a single item to any zone.
4022  *
4023  * Arguments:
4024  *      zone   The zone to free to
4025  *      item   The item we're freeing
4026  *      udata  User supplied data for the dtor
4027  *      skip   Skip dtors and finis
4028  */
4029 static void
4030 zone_free_item(uma_zone_t zone, void *item, void *udata, enum zfreeskip skip)
4031 {
4032
4033         item_dtor(zone, item, zone->uz_size, udata, skip);
4034
4035         if (skip < SKIP_FINI && zone->uz_fini)
4036                 zone->uz_fini(item, zone->uz_size);
4037
4038         zone->uz_release(zone->uz_arg, &item, 1);
4039
4040         if (skip & SKIP_CNT)
4041                 return;
4042
4043         counter_u64_add(zone->uz_frees, 1);
4044
4045         if (zone->uz_max_items > 0)
4046                 zone_free_limit(zone, 1);
4047 }
4048
4049 /* See uma.h */
4050 int
4051 uma_zone_set_max(uma_zone_t zone, int nitems)
4052 {
4053         struct uma_bucket_zone *ubz;
4054         int count;
4055
4056         /*
4057          * XXX This can misbehave if the zone has any allocations with
4058          * no limit and a limit is imposed.  There is currently no
4059          * way to clear a limit.
4060          */
4061         ZONE_LOCK(zone);
4062         ubz = bucket_zone_max(zone, nitems);
4063         count = ubz != NULL ? ubz->ubz_entries : 0;
4064         zone->uz_bucket_size_max = zone->uz_bucket_size = count;
4065         if (zone->uz_bucket_size_min > zone->uz_bucket_size_max)
4066                 zone->uz_bucket_size_min = zone->uz_bucket_size_max;
4067         zone->uz_max_items = nitems;
4068         zone->uz_flags |= UMA_ZFLAG_LIMIT;
4069         zone_update_caches(zone);
4070         /* We may need to wake waiters. */
4071         wakeup(&zone->uz_max_items);
4072         ZONE_UNLOCK(zone);
4073
4074         return (nitems);
4075 }
4076
4077 /* See uma.h */
4078 void
4079 uma_zone_set_maxcache(uma_zone_t zone, int nitems)
4080 {
4081         struct uma_bucket_zone *ubz;
4082         int bpcpu;
4083
4084         ZONE_LOCK(zone);
4085         ubz = bucket_zone_max(zone, nitems);
4086         if (ubz != NULL) {
4087                 bpcpu = 2;
4088                 if ((zone->uz_flags & UMA_ZONE_FIRSTTOUCH) != 0)
4089                         /* Count the cross-domain bucket. */
4090                         bpcpu++;
4091                 nitems -= ubz->ubz_entries * bpcpu * mp_ncpus;
4092                 zone->uz_bucket_size_max = ubz->ubz_entries;
4093         } else {
4094                 zone->uz_bucket_size_max = zone->uz_bucket_size = 0;
4095         }
4096         if (zone->uz_bucket_size_min > zone->uz_bucket_size_max)
4097                 zone->uz_bucket_size_min = zone->uz_bucket_size_max;
4098         zone->uz_bkt_max = nitems;
4099         ZONE_UNLOCK(zone);
4100 }
4101
4102 /* See uma.h */
4103 int
4104 uma_zone_get_max(uma_zone_t zone)
4105 {
4106         int nitems;
4107
4108         nitems = atomic_load_64(&zone->uz_max_items);
4109
4110         return (nitems);
4111 }
4112
4113 /* See uma.h */
4114 void
4115 uma_zone_set_warning(uma_zone_t zone, const char *warning)
4116 {
4117
4118         ZONE_ASSERT_COLD(zone);
4119         zone->uz_warning = warning;
4120 }
4121
4122 /* See uma.h */
4123 void
4124 uma_zone_set_maxaction(uma_zone_t zone, uma_maxaction_t maxaction)
4125 {
4126
4127         ZONE_ASSERT_COLD(zone);
4128         TASK_INIT(&zone->uz_maxaction, 0, (task_fn_t *)maxaction, zone);
4129 }
4130
4131 /* See uma.h */
4132 int
4133 uma_zone_get_cur(uma_zone_t zone)
4134 {
4135         int64_t nitems;
4136         u_int i;
4137
4138         nitems = 0;
4139         if (zone->uz_allocs != EARLY_COUNTER && zone->uz_frees != EARLY_COUNTER)
4140                 nitems = counter_u64_fetch(zone->uz_allocs) -
4141                     counter_u64_fetch(zone->uz_frees);
4142         CPU_FOREACH(i)
4143                 nitems += atomic_load_64(&zone->uz_cpu[i].uc_allocs) -
4144                     atomic_load_64(&zone->uz_cpu[i].uc_frees);
4145
4146         return (nitems < 0 ? 0 : nitems);
4147 }
4148
4149 static uint64_t
4150 uma_zone_get_allocs(uma_zone_t zone)
4151 {
4152         uint64_t nitems;
4153         u_int i;
4154
4155         nitems = 0;
4156         if (zone->uz_allocs != EARLY_COUNTER)
4157                 nitems = counter_u64_fetch(zone->uz_allocs);
4158         CPU_FOREACH(i)
4159                 nitems += atomic_load_64(&zone->uz_cpu[i].uc_allocs);
4160
4161         return (nitems);
4162 }
4163
4164 static uint64_t
4165 uma_zone_get_frees(uma_zone_t zone)
4166 {
4167         uint64_t nitems;
4168         u_int i;
4169
4170         nitems = 0;
4171         if (zone->uz_frees != EARLY_COUNTER)
4172                 nitems = counter_u64_fetch(zone->uz_frees);
4173         CPU_FOREACH(i)
4174                 nitems += atomic_load_64(&zone->uz_cpu[i].uc_frees);
4175
4176         return (nitems);
4177 }
4178
4179 #ifdef INVARIANTS
4180 /* Used only for KEG_ASSERT_COLD(). */
4181 static uint64_t
4182 uma_keg_get_allocs(uma_keg_t keg)
4183 {
4184         uma_zone_t z;
4185         uint64_t nitems;
4186
4187         nitems = 0;
4188         LIST_FOREACH(z, &keg->uk_zones, uz_link)
4189                 nitems += uma_zone_get_allocs(z);
4190
4191         return (nitems);
4192 }
4193 #endif
4194
4195 /* See uma.h */
4196 void
4197 uma_zone_set_init(uma_zone_t zone, uma_init uminit)
4198 {
4199         uma_keg_t keg;
4200
4201         KEG_GET(zone, keg);
4202         KEG_ASSERT_COLD(keg);
4203         keg->uk_init = uminit;
4204 }
4205
4206 /* See uma.h */
4207 void
4208 uma_zone_set_fini(uma_zone_t zone, uma_fini fini)
4209 {
4210         uma_keg_t keg;
4211
4212         KEG_GET(zone, keg);
4213         KEG_ASSERT_COLD(keg);
4214         keg->uk_fini = fini;
4215 }
4216
4217 /* See uma.h */
4218 void
4219 uma_zone_set_zinit(uma_zone_t zone, uma_init zinit)
4220 {
4221
4222         ZONE_ASSERT_COLD(zone);
4223         zone->uz_init = zinit;
4224 }
4225
4226 /* See uma.h */
4227 void
4228 uma_zone_set_zfini(uma_zone_t zone, uma_fini zfini)
4229 {
4230
4231         ZONE_ASSERT_COLD(zone);
4232         zone->uz_fini = zfini;
4233 }
4234
4235 /* See uma.h */
4236 void
4237 uma_zone_set_freef(uma_zone_t zone, uma_free freef)
4238 {
4239         uma_keg_t keg;
4240
4241         KEG_GET(zone, keg);
4242         KEG_ASSERT_COLD(keg);
4243         keg->uk_freef = freef;
4244 }
4245
4246 /* See uma.h */
4247 void
4248 uma_zone_set_allocf(uma_zone_t zone, uma_alloc allocf)
4249 {
4250         uma_keg_t keg;
4251
4252         KEG_GET(zone, keg);
4253         KEG_ASSERT_COLD(keg);
4254         keg->uk_allocf = allocf;
4255 }
4256
4257 /* See uma.h */
4258 void
4259 uma_zone_reserve(uma_zone_t zone, int items)
4260 {
4261         uma_keg_t keg;
4262
4263         KEG_GET(zone, keg);
4264         KEG_ASSERT_COLD(keg);
4265         keg->uk_reserve = items;
4266 }
4267
4268 /* See uma.h */
4269 int
4270 uma_zone_reserve_kva(uma_zone_t zone, int count)
4271 {
4272         uma_keg_t keg;
4273         vm_offset_t kva;
4274         u_int pages;
4275
4276         KEG_GET(zone, keg);
4277         KEG_ASSERT_COLD(keg);
4278         ZONE_ASSERT_COLD(zone);
4279
4280         pages = howmany(count, keg->uk_ipers) * keg->uk_ppera;
4281
4282 #ifdef UMA_MD_SMALL_ALLOC
4283         if (keg->uk_ppera > 1) {
4284 #else
4285         if (1) {
4286 #endif
4287                 kva = kva_alloc((vm_size_t)pages * PAGE_SIZE);
4288                 if (kva == 0)
4289                         return (0);
4290         } else
4291                 kva = 0;
4292
4293         ZONE_LOCK(zone);
4294         MPASS(keg->uk_kva == 0);
4295         keg->uk_kva = kva;
4296         keg->uk_offset = 0;
4297         zone->uz_max_items = pages * keg->uk_ipers;
4298 #ifdef UMA_MD_SMALL_ALLOC
4299         keg->uk_allocf = (keg->uk_ppera > 1) ? noobj_alloc : uma_small_alloc;
4300 #else
4301         keg->uk_allocf = noobj_alloc;
4302 #endif
4303         keg->uk_flags |= UMA_ZFLAG_LIMIT | UMA_ZONE_NOFREE;
4304         zone->uz_flags |= UMA_ZFLAG_LIMIT | UMA_ZONE_NOFREE;
4305         zone_update_caches(zone);
4306         ZONE_UNLOCK(zone);
4307
4308         return (1);
4309 }
4310
4311 /* See uma.h */
4312 void
4313 uma_prealloc(uma_zone_t zone, int items)
4314 {
4315         struct vm_domainset_iter di;
4316         uma_domain_t dom;
4317         uma_slab_t slab;
4318         uma_keg_t keg;
4319         int aflags, domain, slabs;
4320
4321         KEG_GET(zone, keg);
4322         slabs = howmany(items, keg->uk_ipers);
4323         while (slabs-- > 0) {
4324                 aflags = M_NOWAIT;
4325                 vm_domainset_iter_policy_ref_init(&di, &keg->uk_dr, &domain,
4326                     &aflags);
4327                 for (;;) {
4328                         slab = keg_alloc_slab(keg, zone, domain, M_WAITOK,
4329                             aflags);
4330                         if (slab != NULL) {
4331                                 dom = &keg->uk_domain[slab->us_domain];
4332                                 LIST_REMOVE(slab, us_link);
4333                                 LIST_INSERT_HEAD(&dom->ud_free_slab, slab,
4334                                     us_link);
4335                                 KEG_UNLOCK(keg, slab->us_domain);
4336                                 break;
4337                         }
4338                         if (vm_domainset_iter_policy(&di, &domain) != 0)
4339                                 vm_wait_doms(&keg->uk_dr.dr_policy->ds_mask);
4340                 }
4341         }
4342 }
4343
4344 /* See uma.h */
4345 void
4346 uma_reclaim(int req)
4347 {
4348
4349         CTR0(KTR_UMA, "UMA: vm asked us to release pages!");
4350         sx_xlock(&uma_reclaim_lock);
4351         bucket_enable();
4352
4353         switch (req) {
4354         case UMA_RECLAIM_TRIM:
4355                 zone_foreach(zone_trim, NULL);
4356                 break;
4357         case UMA_RECLAIM_DRAIN:
4358         case UMA_RECLAIM_DRAIN_CPU:
4359                 zone_foreach(zone_drain, NULL);
4360                 if (req == UMA_RECLAIM_DRAIN_CPU) {
4361                         pcpu_cache_drain_safe(NULL);
4362                         zone_foreach(zone_drain, NULL);
4363                 }
4364                 break;
4365         default:
4366                 panic("unhandled reclamation request %d", req);
4367         }
4368
4369         /*
4370          * Some slabs may have been freed but this zone will be visited early
4371          * we visit again so that we can free pages that are empty once other
4372          * zones are drained.  We have to do the same for buckets.
4373          */
4374         zone_drain(slabzones[0], NULL);
4375         zone_drain(slabzones[1], NULL);
4376         bucket_zone_drain();
4377         sx_xunlock(&uma_reclaim_lock);
4378 }
4379
4380 static volatile int uma_reclaim_needed;
4381
4382 void
4383 uma_reclaim_wakeup(void)
4384 {
4385
4386         if (atomic_fetchadd_int(&uma_reclaim_needed, 1) == 0)
4387                 wakeup(uma_reclaim);
4388 }
4389
4390 void
4391 uma_reclaim_worker(void *arg __unused)
4392 {
4393
4394         for (;;) {
4395                 sx_xlock(&uma_reclaim_lock);
4396                 while (atomic_load_int(&uma_reclaim_needed) == 0)
4397                         sx_sleep(uma_reclaim, &uma_reclaim_lock, PVM, "umarcl",
4398                             hz);
4399                 sx_xunlock(&uma_reclaim_lock);
4400                 EVENTHANDLER_INVOKE(vm_lowmem, VM_LOW_KMEM);
4401                 uma_reclaim(UMA_RECLAIM_DRAIN_CPU);
4402                 atomic_store_int(&uma_reclaim_needed, 0);
4403                 /* Don't fire more than once per-second. */
4404                 pause("umarclslp", hz);
4405         }
4406 }
4407
4408 /* See uma.h */
4409 void
4410 uma_zone_reclaim(uma_zone_t zone, int req)
4411 {
4412
4413         switch (req) {
4414         case UMA_RECLAIM_TRIM:
4415                 zone_trim(zone, NULL);
4416                 break;
4417         case UMA_RECLAIM_DRAIN:
4418                 zone_drain(zone, NULL);
4419                 break;
4420         case UMA_RECLAIM_DRAIN_CPU:
4421                 pcpu_cache_drain_safe(zone);
4422                 zone_drain(zone, NULL);
4423                 break;
4424         default:
4425                 panic("unhandled reclamation request %d", req);
4426         }
4427 }
4428
4429 /* See uma.h */
4430 int
4431 uma_zone_exhausted(uma_zone_t zone)
4432 {
4433
4434         return (atomic_load_32(&zone->uz_sleepers) > 0);
4435 }
4436
4437 unsigned long
4438 uma_limit(void)
4439 {
4440
4441         return (uma_kmem_limit);
4442 }
4443
4444 void
4445 uma_set_limit(unsigned long limit)
4446 {
4447
4448         uma_kmem_limit = limit;
4449 }
4450
4451 unsigned long
4452 uma_size(void)
4453 {
4454
4455         return (atomic_load_long(&uma_kmem_total));
4456 }
4457
4458 long
4459 uma_avail(void)
4460 {
4461
4462         return (uma_kmem_limit - uma_size());
4463 }
4464
4465 #ifdef DDB
4466 /*
4467  * Generate statistics across both the zone and its per-cpu cache's.  Return
4468  * desired statistics if the pointer is non-NULL for that statistic.
4469  *
4470  * Note: does not update the zone statistics, as it can't safely clear the
4471  * per-CPU cache statistic.
4472  *
4473  */
4474 static void
4475 uma_zone_sumstat(uma_zone_t z, long *cachefreep, uint64_t *allocsp,
4476     uint64_t *freesp, uint64_t *sleepsp, uint64_t *xdomainp)
4477 {
4478         uma_cache_t cache;
4479         uint64_t allocs, frees, sleeps, xdomain;
4480         int cachefree, cpu;
4481
4482         allocs = frees = sleeps = xdomain = 0;
4483         cachefree = 0;
4484         CPU_FOREACH(cpu) {
4485                 cache = &z->uz_cpu[cpu];
4486                 cachefree += cache->uc_allocbucket.ucb_cnt;
4487                 cachefree += cache->uc_freebucket.ucb_cnt;
4488                 xdomain += cache->uc_crossbucket.ucb_cnt;
4489                 cachefree += cache->uc_crossbucket.ucb_cnt;
4490                 allocs += cache->uc_allocs;
4491                 frees += cache->uc_frees;
4492         }
4493         allocs += counter_u64_fetch(z->uz_allocs);
4494         frees += counter_u64_fetch(z->uz_frees);
4495         sleeps += z->uz_sleeps;
4496         xdomain += z->uz_xdomain;
4497         if (cachefreep != NULL)
4498                 *cachefreep = cachefree;
4499         if (allocsp != NULL)
4500                 *allocsp = allocs;
4501         if (freesp != NULL)
4502                 *freesp = frees;
4503         if (sleepsp != NULL)
4504                 *sleepsp = sleeps;
4505         if (xdomainp != NULL)
4506                 *xdomainp = xdomain;
4507 }
4508 #endif /* DDB */
4509
4510 static int
4511 sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS)
4512 {
4513         uma_keg_t kz;
4514         uma_zone_t z;
4515         int count;
4516
4517         count = 0;
4518         rw_rlock(&uma_rwlock);
4519         LIST_FOREACH(kz, &uma_kegs, uk_link) {
4520                 LIST_FOREACH(z, &kz->uk_zones, uz_link)
4521                         count++;
4522         }
4523         LIST_FOREACH(z, &uma_cachezones, uz_link)
4524                 count++;
4525
4526         rw_runlock(&uma_rwlock);
4527         return (sysctl_handle_int(oidp, &count, 0, req));
4528 }
4529
4530 static void
4531 uma_vm_zone_stats(struct uma_type_header *uth, uma_zone_t z, struct sbuf *sbuf,
4532     struct uma_percpu_stat *ups, bool internal)
4533 {
4534         uma_zone_domain_t zdom;
4535         uma_cache_t cache;
4536         int i;
4537
4538
4539         for (i = 0; i < vm_ndomains; i++) {
4540                 zdom = &z->uz_domain[i];
4541                 uth->uth_zone_free += zdom->uzd_nitems;
4542         }
4543         uth->uth_allocs = counter_u64_fetch(z->uz_allocs);
4544         uth->uth_frees = counter_u64_fetch(z->uz_frees);
4545         uth->uth_fails = counter_u64_fetch(z->uz_fails);
4546         uth->uth_sleeps = z->uz_sleeps;
4547         uth->uth_xdomain = z->uz_xdomain;
4548
4549         /*
4550          * While it is not normally safe to access the cache bucket pointers
4551          * while not on the CPU that owns the cache, we only allow the pointers
4552          * to be exchanged without the zone lock held, not invalidated, so
4553          * accept the possible race associated with bucket exchange during
4554          * monitoring.  Use atomic_load_ptr() to ensure that the bucket pointers
4555          * are loaded only once.
4556          */
4557         for (i = 0; i < mp_maxid + 1; i++) {
4558                 bzero(&ups[i], sizeof(*ups));
4559                 if (internal || CPU_ABSENT(i))
4560                         continue;
4561                 cache = &z->uz_cpu[i];
4562                 ups[i].ups_cache_free += cache->uc_allocbucket.ucb_cnt;
4563                 ups[i].ups_cache_free += cache->uc_freebucket.ucb_cnt;
4564                 ups[i].ups_cache_free += cache->uc_crossbucket.ucb_cnt;
4565                 ups[i].ups_allocs = cache->uc_allocs;
4566                 ups[i].ups_frees = cache->uc_frees;
4567         }
4568 }
4569
4570 static int
4571 sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS)
4572 {
4573         struct uma_stream_header ush;
4574         struct uma_type_header uth;
4575         struct uma_percpu_stat *ups;
4576         struct sbuf sbuf;
4577         uma_keg_t kz;
4578         uma_zone_t z;
4579         uint64_t items;
4580         uint32_t kfree, pages;
4581         int count, error, i;
4582
4583         error = sysctl_wire_old_buffer(req, 0);
4584         if (error != 0)
4585                 return (error);
4586         sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
4587         sbuf_clear_flags(&sbuf, SBUF_INCLUDENUL);
4588         ups = malloc((mp_maxid + 1) * sizeof(*ups), M_TEMP, M_WAITOK);
4589
4590         count = 0;
4591         rw_rlock(&uma_rwlock);
4592         LIST_FOREACH(kz, &uma_kegs, uk_link) {
4593                 LIST_FOREACH(z, &kz->uk_zones, uz_link)
4594                         count++;
4595         }
4596
4597         LIST_FOREACH(z, &uma_cachezones, uz_link)
4598                 count++;
4599
4600         /*
4601          * Insert stream header.
4602          */
4603         bzero(&ush, sizeof(ush));
4604         ush.ush_version = UMA_STREAM_VERSION;
4605         ush.ush_maxcpus = (mp_maxid + 1);
4606         ush.ush_count = count;
4607         (void)sbuf_bcat(&sbuf, &ush, sizeof(ush));
4608
4609         LIST_FOREACH(kz, &uma_kegs, uk_link) {
4610                 kfree = pages = 0;
4611                 for (i = 0; i < vm_ndomains; i++) {
4612                         kfree += kz->uk_domain[i].ud_free;
4613                         pages += kz->uk_domain[i].ud_pages;
4614                 }
4615                 LIST_FOREACH(z, &kz->uk_zones, uz_link) {
4616                         bzero(&uth, sizeof(uth));
4617                         ZONE_LOCK(z);
4618                         strlcpy(uth.uth_name, z->uz_name, UTH_MAX_NAME);
4619                         uth.uth_align = kz->uk_align;
4620                         uth.uth_size = kz->uk_size;
4621                         uth.uth_rsize = kz->uk_rsize;
4622                         if (z->uz_max_items > 0) {
4623                                 items = UZ_ITEMS_COUNT(z->uz_items);
4624                                 uth.uth_pages = (items / kz->uk_ipers) *
4625                                         kz->uk_ppera;
4626                         } else
4627                                 uth.uth_pages = pages;
4628                         uth.uth_maxpages = (z->uz_max_items / kz->uk_ipers) *
4629                             kz->uk_ppera;
4630                         uth.uth_limit = z->uz_max_items;
4631                         uth.uth_keg_free = kfree;
4632
4633                         /*
4634                          * A zone is secondary is it is not the first entry
4635                          * on the keg's zone list.
4636                          */
4637                         if ((z->uz_flags & UMA_ZONE_SECONDARY) &&
4638                             (LIST_FIRST(&kz->uk_zones) != z))
4639                                 uth.uth_zone_flags = UTH_ZONE_SECONDARY;
4640                         uma_vm_zone_stats(&uth, z, &sbuf, ups,
4641                             kz->uk_flags & UMA_ZFLAG_INTERNAL);
4642                         ZONE_UNLOCK(z);
4643                         (void)sbuf_bcat(&sbuf, &uth, sizeof(uth));
4644                         for (i = 0; i < mp_maxid + 1; i++)
4645                                 (void)sbuf_bcat(&sbuf, &ups[i], sizeof(ups[i]));
4646                 }
4647         }
4648         LIST_FOREACH(z, &uma_cachezones, uz_link) {
4649                 bzero(&uth, sizeof(uth));
4650                 ZONE_LOCK(z);
4651                 strlcpy(uth.uth_name, z->uz_name, UTH_MAX_NAME);
4652                 uth.uth_size = z->uz_size;
4653                 uma_vm_zone_stats(&uth, z, &sbuf, ups, false);
4654                 ZONE_UNLOCK(z);
4655                 (void)sbuf_bcat(&sbuf, &uth, sizeof(uth));
4656                 for (i = 0; i < mp_maxid + 1; i++)
4657                         (void)sbuf_bcat(&sbuf, &ups[i], sizeof(ups[i]));
4658         }
4659
4660         rw_runlock(&uma_rwlock);
4661         error = sbuf_finish(&sbuf);
4662         sbuf_delete(&sbuf);
4663         free(ups, M_TEMP);
4664         return (error);
4665 }
4666
4667 int
4668 sysctl_handle_uma_zone_max(SYSCTL_HANDLER_ARGS)
4669 {
4670         uma_zone_t zone = *(uma_zone_t *)arg1;
4671         int error, max;
4672
4673         max = uma_zone_get_max(zone);
4674         error = sysctl_handle_int(oidp, &max, 0, req);
4675         if (error || !req->newptr)
4676                 return (error);
4677
4678         uma_zone_set_max(zone, max);
4679
4680         return (0);
4681 }
4682
4683 int
4684 sysctl_handle_uma_zone_cur(SYSCTL_HANDLER_ARGS)
4685 {
4686         uma_zone_t zone;
4687         int cur;
4688
4689         /*
4690          * Some callers want to add sysctls for global zones that
4691          * may not yet exist so they pass a pointer to a pointer.
4692          */
4693         if (arg2 == 0)
4694                 zone = *(uma_zone_t *)arg1;
4695         else
4696                 zone = arg1;
4697         cur = uma_zone_get_cur(zone);
4698         return (sysctl_handle_int(oidp, &cur, 0, req));
4699 }
4700
4701 static int
4702 sysctl_handle_uma_zone_allocs(SYSCTL_HANDLER_ARGS)
4703 {
4704         uma_zone_t zone = arg1;
4705         uint64_t cur;
4706
4707         cur = uma_zone_get_allocs(zone);
4708         return (sysctl_handle_64(oidp, &cur, 0, req));
4709 }
4710
4711 static int
4712 sysctl_handle_uma_zone_frees(SYSCTL_HANDLER_ARGS)
4713 {
4714         uma_zone_t zone = arg1;
4715         uint64_t cur;
4716
4717         cur = uma_zone_get_frees(zone);
4718         return (sysctl_handle_64(oidp, &cur, 0, req));
4719 }
4720
4721 static int
4722 sysctl_handle_uma_zone_flags(SYSCTL_HANDLER_ARGS)
4723 {
4724         struct sbuf sbuf;
4725         uma_zone_t zone = arg1;
4726         int error;
4727
4728         sbuf_new_for_sysctl(&sbuf, NULL, 0, req);
4729         if (zone->uz_flags != 0)
4730                 sbuf_printf(&sbuf, "0x%b", zone->uz_flags, PRINT_UMA_ZFLAGS);
4731         else
4732                 sbuf_printf(&sbuf, "0");
4733         error = sbuf_finish(&sbuf);
4734         sbuf_delete(&sbuf);
4735
4736         return (error);
4737 }
4738
4739 static int
4740 sysctl_handle_uma_slab_efficiency(SYSCTL_HANDLER_ARGS)
4741 {
4742         uma_keg_t keg = arg1;
4743         int avail, effpct, total;
4744
4745         total = keg->uk_ppera * PAGE_SIZE;
4746         if ((keg->uk_flags & UMA_ZFLAG_OFFPAGE) != 0)
4747                 total += slabzone(keg->uk_ipers)->uz_keg->uk_rsize;
4748         /*
4749          * We consider the client's requested size and alignment here, not the
4750          * real size determination uk_rsize, because we also adjust the real
4751          * size for internal implementation reasons (max bitset size).
4752          */
4753         avail = keg->uk_ipers * roundup2(keg->uk_size, keg->uk_align + 1);
4754         if ((keg->uk_flags & UMA_ZONE_PCPU) != 0)
4755                 avail *= mp_maxid + 1;
4756         effpct = 100 * avail / total;
4757         return (sysctl_handle_int(oidp, &effpct, 0, req));
4758 }
4759
4760 static int
4761 sysctl_handle_uma_zone_items(SYSCTL_HANDLER_ARGS)
4762 {
4763         uma_zone_t zone = arg1;
4764         uint64_t cur;
4765
4766         cur = UZ_ITEMS_COUNT(atomic_load_64(&zone->uz_items));
4767         return (sysctl_handle_64(oidp, &cur, 0, req));
4768 }
4769
4770 #ifdef INVARIANTS
4771 static uma_slab_t
4772 uma_dbg_getslab(uma_zone_t zone, void *item)
4773 {
4774         uma_slab_t slab;
4775         uma_keg_t keg;
4776         uint8_t *mem;
4777
4778         /*
4779          * It is safe to return the slab here even though the
4780          * zone is unlocked because the item's allocation state
4781          * essentially holds a reference.
4782          */
4783         mem = (uint8_t *)((uintptr_t)item & (~UMA_SLAB_MASK));
4784         if ((zone->uz_flags & UMA_ZFLAG_CACHE) != 0)
4785                 return (NULL);
4786         if (zone->uz_flags & UMA_ZFLAG_VTOSLAB)
4787                 return (vtoslab((vm_offset_t)mem));
4788         keg = zone->uz_keg;
4789         if ((keg->uk_flags & UMA_ZFLAG_HASH) == 0)
4790                 return ((uma_slab_t)(mem + keg->uk_pgoff));
4791         KEG_LOCK(keg, 0);
4792         slab = hash_sfind(&keg->uk_hash, mem);
4793         KEG_UNLOCK(keg, 0);
4794
4795         return (slab);
4796 }
4797
4798 static bool
4799 uma_dbg_zskip(uma_zone_t zone, void *mem)
4800 {
4801
4802         if ((zone->uz_flags & UMA_ZFLAG_CACHE) != 0)
4803                 return (true);
4804
4805         return (uma_dbg_kskip(zone->uz_keg, mem));
4806 }
4807
4808 static bool
4809 uma_dbg_kskip(uma_keg_t keg, void *mem)
4810 {
4811         uintptr_t idx;
4812
4813         if (dbg_divisor == 0)
4814                 return (true);
4815
4816         if (dbg_divisor == 1)
4817                 return (false);
4818
4819         idx = (uintptr_t)mem >> PAGE_SHIFT;
4820         if (keg->uk_ipers > 1) {
4821                 idx *= keg->uk_ipers;
4822                 idx += ((uintptr_t)mem & PAGE_MASK) / keg->uk_rsize;
4823         }
4824
4825         if ((idx / dbg_divisor) * dbg_divisor != idx) {
4826                 counter_u64_add(uma_skip_cnt, 1);
4827                 return (true);
4828         }
4829         counter_u64_add(uma_dbg_cnt, 1);
4830
4831         return (false);
4832 }
4833
4834 /*
4835  * Set up the slab's freei data such that uma_dbg_free can function.
4836  *
4837  */
4838 static void
4839 uma_dbg_alloc(uma_zone_t zone, uma_slab_t slab, void *item)
4840 {
4841         uma_keg_t keg;
4842         int freei;
4843
4844         if (slab == NULL) {
4845                 slab = uma_dbg_getslab(zone, item);
4846                 if (slab == NULL)
4847                         panic("uma: item %p did not belong to zone %s\n",
4848                             item, zone->uz_name);
4849         }
4850         keg = zone->uz_keg;
4851         freei = slab_item_index(slab, keg, item);
4852
4853         if (BIT_ISSET(keg->uk_ipers, freei, slab_dbg_bits(slab, keg)))
4854                 panic("Duplicate alloc of %p from zone %p(%s) slab %p(%d)\n",
4855                     item, zone, zone->uz_name, slab, freei);
4856         BIT_SET_ATOMIC(keg->uk_ipers, freei, slab_dbg_bits(slab, keg));
4857 }
4858
4859 /*
4860  * Verifies freed addresses.  Checks for alignment, valid slab membership
4861  * and duplicate frees.
4862  *
4863  */
4864 static void
4865 uma_dbg_free(uma_zone_t zone, uma_slab_t slab, void *item)
4866 {
4867         uma_keg_t keg;
4868         int freei;
4869
4870         if (slab == NULL) {
4871                 slab = uma_dbg_getslab(zone, item);
4872                 if (slab == NULL)
4873                         panic("uma: Freed item %p did not belong to zone %s\n",
4874                             item, zone->uz_name);
4875         }
4876         keg = zone->uz_keg;
4877         freei = slab_item_index(slab, keg, item);
4878
4879         if (freei >= keg->uk_ipers)
4880                 panic("Invalid free of %p from zone %p(%s) slab %p(%d)\n",
4881                     item, zone, zone->uz_name, slab, freei);
4882
4883         if (slab_item(slab, keg, freei) != item)
4884                 panic("Unaligned free of %p from zone %p(%s) slab %p(%d)\n",
4885                     item, zone, zone->uz_name, slab, freei);
4886
4887         if (!BIT_ISSET(keg->uk_ipers, freei, slab_dbg_bits(slab, keg)))
4888                 panic("Duplicate free of %p from zone %p(%s) slab %p(%d)\n",
4889                     item, zone, zone->uz_name, slab, freei);
4890
4891         BIT_CLR_ATOMIC(keg->uk_ipers, freei, slab_dbg_bits(slab, keg));
4892 }
4893 #endif /* INVARIANTS */
4894
4895 #ifdef DDB
4896 static int64_t
4897 get_uma_stats(uma_keg_t kz, uma_zone_t z, uint64_t *allocs, uint64_t *used,
4898     uint64_t *sleeps, long *cachefree, uint64_t *xdomain)
4899 {
4900         uint64_t frees;
4901         int i;
4902
4903         if (kz->uk_flags & UMA_ZFLAG_INTERNAL) {
4904                 *allocs = counter_u64_fetch(z->uz_allocs);
4905                 frees = counter_u64_fetch(z->uz_frees);
4906                 *sleeps = z->uz_sleeps;
4907                 *cachefree = 0;
4908                 *xdomain = 0;
4909         } else
4910                 uma_zone_sumstat(z, cachefree, allocs, &frees, sleeps,
4911                     xdomain);
4912         for (i = 0; i < vm_ndomains; i++) {
4913                 *cachefree += z->uz_domain[i].uzd_nitems;
4914                 if (!((z->uz_flags & UMA_ZONE_SECONDARY) &&
4915                     (LIST_FIRST(&kz->uk_zones) != z)))
4916                         *cachefree += kz->uk_domain[i].ud_free;
4917         }
4918         *used = *allocs - frees;
4919         return (((int64_t)*used + *cachefree) * kz->uk_size);
4920 }
4921
4922 DB_SHOW_COMMAND(uma, db_show_uma)
4923 {
4924         const char *fmt_hdr, *fmt_entry;
4925         uma_keg_t kz;
4926         uma_zone_t z;
4927         uint64_t allocs, used, sleeps, xdomain;
4928         long cachefree;
4929         /* variables for sorting */
4930         uma_keg_t cur_keg;
4931         uma_zone_t cur_zone, last_zone;
4932         int64_t cur_size, last_size, size;
4933         int ties;
4934
4935         /* /i option produces machine-parseable CSV output */
4936         if (modif[0] == 'i') {
4937                 fmt_hdr = "%s,%s,%s,%s,%s,%s,%s,%s,%s\n";
4938                 fmt_entry = "\"%s\",%ju,%jd,%ld,%ju,%ju,%u,%jd,%ju\n";
4939         } else {
4940                 fmt_hdr = "%18s %6s %7s %7s %11s %7s %7s %10s %8s\n";
4941                 fmt_entry = "%18s %6ju %7jd %7ld %11ju %7ju %7u %10jd %8ju\n";
4942         }
4943
4944         db_printf(fmt_hdr, "Zone", "Size", "Used", "Free", "Requests",
4945             "Sleeps", "Bucket", "Total Mem", "XFree");
4946
4947         /* Sort the zones with largest size first. */
4948         last_zone = NULL;
4949         last_size = INT64_MAX;
4950         for (;;) {
4951                 cur_zone = NULL;
4952                 cur_size = -1;
4953                 ties = 0;
4954                 LIST_FOREACH(kz, &uma_kegs, uk_link) {
4955                         LIST_FOREACH(z, &kz->uk_zones, uz_link) {
4956                                 /*
4957                                  * In the case of size ties, print out zones
4958                                  * in the order they are encountered.  That is,
4959                                  * when we encounter the most recently output
4960                                  * zone, we have already printed all preceding
4961                                  * ties, and we must print all following ties.
4962                                  */
4963                                 if (z == last_zone) {
4964                                         ties = 1;
4965                                         continue;
4966                                 }
4967                                 size = get_uma_stats(kz, z, &allocs, &used,
4968                                     &sleeps, &cachefree, &xdomain);
4969                                 if (size > cur_size && size < last_size + ties)
4970                                 {
4971                                         cur_size = size;
4972                                         cur_zone = z;
4973                                         cur_keg = kz;
4974                                 }
4975                         }
4976                 }
4977                 if (cur_zone == NULL)
4978                         break;
4979
4980                 size = get_uma_stats(cur_keg, cur_zone, &allocs, &used,
4981                     &sleeps, &cachefree, &xdomain);
4982                 db_printf(fmt_entry, cur_zone->uz_name,
4983                     (uintmax_t)cur_keg->uk_size, (intmax_t)used, cachefree,
4984                     (uintmax_t)allocs, (uintmax_t)sleeps,
4985                     (unsigned)cur_zone->uz_bucket_size, (intmax_t)size,
4986                     xdomain);
4987
4988                 if (db_pager_quit)
4989                         return;
4990                 last_zone = cur_zone;
4991                 last_size = cur_size;
4992         }
4993 }
4994
4995 DB_SHOW_COMMAND(umacache, db_show_umacache)
4996 {
4997         uma_zone_t z;
4998         uint64_t allocs, frees;
4999         long cachefree;
5000         int i;
5001
5002         db_printf("%18s %8s %8s %8s %12s %8s\n", "Zone", "Size", "Used", "Free",
5003             "Requests", "Bucket");
5004         LIST_FOREACH(z, &uma_cachezones, uz_link) {
5005                 uma_zone_sumstat(z, &cachefree, &allocs, &frees, NULL, NULL);
5006                 for (i = 0; i < vm_ndomains; i++)
5007                         cachefree += z->uz_domain[i].uzd_nitems;
5008                 db_printf("%18s %8ju %8jd %8ld %12ju %8u\n",
5009                     z->uz_name, (uintmax_t)z->uz_size,
5010                     (intmax_t)(allocs - frees), cachefree,
5011                     (uintmax_t)allocs, z->uz_bucket_size);
5012                 if (db_pager_quit)
5013                         return;
5014         }
5015 }
5016 #endif  /* DDB */