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