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