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