sys/vm/uma_core.c

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