sys/vm/uma_core.c

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