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