sys/vm/uma_int.h

   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  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice unmodified, this list of conditions, and the following
  13  *    disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * $FreeBSD$
  30  *
  31  */
  32
  33 #include <sys/counter.h>
  34 #include <sys/_bitset.h>
  35 #include <sys/_domainset.h>
  36 #include <sys/_task.h>
  37
  38 /*
  39  * This file includes definitions, structures, prototypes, and inlines that
  40  * should not be used outside of the actual implementation of UMA.
  41  */
  42
  43 /*
  44  * The brief summary;  Zones describe unique allocation types.  Zones are
  45  * organized into per-CPU caches which are filled by buckets.  Buckets are
  46  * organized according to memory domains.  Buckets are filled from kegs which
  47  * are also organized according to memory domains.  Kegs describe a unique
  48  * allocation type, backend memory provider, and layout.  Kegs are associated
  49  * with one or more zones and zones reference one or more kegs.  Kegs provide
  50  * slabs which are virtually contiguous collections of pages.  Each slab is
  51  * broken down int one or more items that will satisfy an individual allocation.
  52  *
  53  * Allocation is satisfied in the following order:
  54  * 1) Per-CPU cache
  55  * 2) Per-domain cache of buckets
  56  * 3) Slab from any of N kegs
  57  * 4) Backend page provider
  58  *
  59  * More detail on individual objects is contained below:
  60  *
  61  * Kegs contain lists of slabs which are stored in either the full bin, empty
  62  * bin, or partially allocated bin, to reduce fragmentation.  They also contain
  63  * the user supplied value for size, which is adjusted for alignment purposes
  64  * and rsize is the result of that.  The Keg also stores information for
  65  * managing a hash of page addresses that maps pages to uma_slab_t structures
  66  * for pages that don't have embedded uma_slab_t's.
  67  *
  68  * Keg slab lists are organized by memory domain to support NUMA allocation
  69  * policies.  By default allocations are spread across domains to reduce the
  70  * potential for hotspots.  Special keg creation flags may be specified to
  71  * prefer location allocation.  However there is no strict enforcement as frees
  72  * may happen on any CPU and these are returned to the CPU-local cache
  73  * regardless of the originating domain.
  74  *
  75  * The uma_slab_t may be embedded in a UMA_SLAB_SIZE chunk of memory or it may
  76  * be allocated off the page from a special slab zone.  The free list within a
  77  * slab is managed with a bitmask.  For item sizes that would yield more than
  78  * 10% memory waste we potentially allocate a separate uma_slab_t if this will
  79  * improve the number of items per slab that will fit.
  80  *
  81  * The only really gross cases, with regards to memory waste, are for those
  82  * items that are just over half the page size.   You can get nearly 50% waste,
  83  * so you fall back to the memory footprint of the power of two allocator. I
  84  * have looked at memory allocation sizes on many of the machines available to
  85  * me, and there does not seem to be an abundance of allocations at this range
  86  * so at this time it may not make sense to optimize for it.  This can, of
  87  * course, be solved with dynamic slab sizes.
  88  *
  89  * Kegs may serve multiple Zones but by far most of the time they only serve
  90  * one.  When a Zone is created, a Keg is allocated and setup for it.  While
  91  * the backing Keg stores slabs, the Zone caches Buckets of items allocated
  92  * from the slabs.  Each Zone is equipped with an init/fini and ctor/dtor
  93  * pair, as well as with its own set of small per-CPU caches, layered above
  94  * the Zone's general Bucket cache.
  95  *
  96  * The PCPU caches are protected by critical sections, and may be accessed
  97  * safely only from their associated CPU, while the Zones backed by the same
  98  * Keg all share a common Keg lock (to coalesce contention on the backing
  99  * slabs).  The backing Keg typically only serves one Zone but in the case of
 100  * multiple Zones, one of the Zones is considered the Master Zone and all
 101  * Zone-related stats from the Keg are done in the Master Zone.  For an
 102  * example of a Multi-Zone setup, refer to the Mbuf allocation code.
 103  */
 104
 105 /*
 106  *      This is the representation for normal (Non OFFPAGE slab)
 107  *
 108  *      i == item
 109  *      s == slab pointer
 110  *
 111  *      <----------------  Page (UMA_SLAB_SIZE) ------------------>
 112  *      ___________________________________________________________
 113  *     | _  _  _  _  _  _  _  _  _  _  _  _  _  _  _   ___________ |
 114  *     ||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i| |slab header||
 115  *     ||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_| |___________||
 116  *     |___________________________________________________________|
 117  *
 118  *
 119  *      This is an OFFPAGE slab. These can be larger than UMA_SLAB_SIZE.
 120  *
 121  *      ___________________________________________________________
 122  *     | _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _   |
 123  *     ||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i||i|  |
 124  *     ||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_||_|  |
 125  *     |___________________________________________________________|
 126  *       ___________    ^
 127  *      |slab header|   |
 128  *      |___________|---*
 129  *
 130  */
 131
 132 #ifndef VM_UMA_INT_H
 133 #define VM_UMA_INT_H
 134
 135 #define UMA_SLAB_SIZE   PAGE_SIZE       /* How big are our slabs? */
 136 #define UMA_SLAB_MASK   (PAGE_SIZE - 1) /* Mask to get back to the page */
 137 #define UMA_SLAB_SHIFT  PAGE_SHIFT      /* Number of bits PAGE_MASK */
 138
 139 /* Max waste percentage before going to off page slab management */
 140 #define UMA_MAX_WASTE   10
 141
 142 /* Max size of a CACHESPREAD slab. */
 143 #define UMA_CACHESPREAD_MAX_SIZE        (128 * 1024)
 144
 145 /*
 146  * These flags must not overlap with the UMA_ZONE flags specified in uma.h.
 147  */
 148 #define UMA_ZFLAG_OFFPAGE       0x00200000      /*
 149                                                  * Force the slab structure
 150                                                  * allocation off of the real
 151                                                  * memory.
 152                                                  */
 153 #define UMA_ZFLAG_HASH          0x00400000      /*
 154                                                  * Use a hash table instead of
 155                                                  * caching information in the
 156                                                  * vm_page.
 157                                                  */
 158 #define UMA_ZFLAG_VTOSLAB       0x00800000      /*
 159                                                  * Zone uses vtoslab for
 160                                                  * lookup.
 161                                                  */
 162 #define UMA_ZFLAG_CTORDTOR      0x01000000      /* Zone has ctor/dtor set. */
 163 #define UMA_ZFLAG_LIMIT         0x02000000      /* Zone has limit set. */
 164 #define UMA_ZFLAG_CACHE         0x04000000      /* uma_zcache_create()d it */
 165 #define UMA_ZFLAG_RECLAIMING    0x08000000      /* Running zone_reclaim(). */
 166 #define UMA_ZFLAG_BUCKET        0x10000000      /* Bucket zone. */
 167 #define UMA_ZFLAG_INTERNAL      0x20000000      /* No offpage no PCPU. */
 168 #define UMA_ZFLAG_TRASH         0x40000000      /* Add trash ctor/dtor. */
 169
 170 #define UMA_ZFLAG_INHERIT                                               \
 171     (UMA_ZFLAG_OFFPAGE | UMA_ZFLAG_HASH | UMA_ZFLAG_VTOSLAB |           \
 172      UMA_ZFLAG_BUCKET | UMA_ZFLAG_INTERNAL)
 173
 174 #define PRINT_UMA_ZFLAGS        "\20"   \
 175     "\37TRASH"                          \
 176     "\36INTERNAL"                       \
 177     "\35BUCKET"                         \
 178     "\34RECLAIMING"                     \
 179     "\33CACHE"                          \
 180     "\32LIMIT"                          \
 181     "\31CTORDTOR"                       \
 182     "\30VTOSLAB"                        \
 183     "\27HASH"                           \
 184     "\26OFFPAGE"                        \
 185     "\23SMR"                            \
 186     "\22ROUNDROBIN"                     \
 187     "\21FIRSTTOUCH"                     \
 188     "\20PCPU"                           \
 189     "\17NODUMP"                         \
 190     "\16CACHESPREAD"                    \
 191     "\15MINBUCKET"                      \
 192     "\14MAXBUCKET"                      \
 193     "\13NOBUCKET"                       \
 194     "\12SECONDARY"                      \
 195     "\11NOTPAGE"                        \
 196     "\10VM"                             \
 197     "\7MTXCLASS"                        \
 198     "\6NOFREE"                          \
 199     "\5MALLOC"                          \
 200     "\4NOTOUCH"                         \
 201     "\3CONTIG"                          \
 202     "\2ZINIT"
 203
 204 /*
 205  * Hash table for freed address -> slab translation.
 206  *
 207  * Only zones with memory not touchable by the allocator use the
 208  * hash table.  Otherwise slabs are found with vtoslab().
 209  */
 210 #define UMA_HASH_SIZE_INIT      32
 211
 212 #define UMA_HASH(h, s) ((((uintptr_t)s) >> UMA_SLAB_SHIFT) & (h)->uh_hashmask)
 213
 214 #define UMA_HASH_INSERT(h, s, mem)                                      \
 215         LIST_INSERT_HEAD(&(h)->uh_slab_hash[UMA_HASH((h),               \
 216             (mem))], slab_tohashslab(s), uhs_hlink)
 217
 218 #define UMA_HASH_REMOVE(h, s)                                           \
 219         LIST_REMOVE(slab_tohashslab(s), uhs_hlink)
 220
 221 LIST_HEAD(slabhashhead, uma_hash_slab);
 222
 223 struct uma_hash {
 224         struct slabhashhead     *uh_slab_hash;  /* Hash table for slabs */
 225         u_int           uh_hashsize;    /* Current size of the hash table */
 226         u_int           uh_hashmask;    /* Mask used during hashing */
 227 };
 228
 229 /*
 230  * Align field or structure to cache 'sector' in intel terminology.  This
 231  * is more efficient with adjacent line prefetch.
 232  */
 233 #if defined(__amd64__) || defined(__powerpc64__)
 234 #define UMA_SUPER_ALIGN (CACHE_LINE_SIZE * 2)
 235 #else
 236 #define UMA_SUPER_ALIGN CACHE_LINE_SIZE
 237 #endif
 238
 239 #define UMA_ALIGN       __aligned(UMA_SUPER_ALIGN)
 240
 241 /*
 242  * The uma_bucket structure is used to queue and manage buckets divorced
 243  * from per-cpu caches.  They are loaded into uma_cache_bucket structures
 244  * for use.
 245  */
 246 struct uma_bucket {
 247         STAILQ_ENTRY(uma_bucket)        ub_link; /* Link into the zone */
 248         int16_t         ub_cnt;                 /* Count of items in bucket. */
 249         int16_t         ub_entries;             /* Max items. */
 250         smr_seq_t       ub_seq;                 /* SMR sequence number. */
 251         void            *ub_bucket[];           /* actual allocation storage */
 252 };
 253
 254 typedef struct uma_bucket * uma_bucket_t;
 255
 256 /*
 257  * The uma_cache_bucket structure is statically allocated on each per-cpu
 258  * cache.  Its use reduces branches and cache misses in the fast path.
 259  */
 260 struct uma_cache_bucket {
 261         uma_bucket_t    ucb_bucket;
 262         int16_t         ucb_cnt;
 263         int16_t         ucb_entries;
 264         uint32_t        ucb_spare;
 265 };
 266
 267 typedef struct uma_cache_bucket * uma_cache_bucket_t;
 268
 269 /*
 270  * The uma_cache structure is allocated for each cpu for every zone
 271  * type.  This optimizes synchronization out of the allocator fast path.
 272  */
 273 struct uma_cache {
 274         struct uma_cache_bucket uc_freebucket;  /* Bucket we're freeing to */
 275         struct uma_cache_bucket uc_allocbucket; /* Bucket to allocate from */
 276         struct uma_cache_bucket uc_crossbucket; /* cross domain bucket */
 277         uint64_t                uc_allocs;      /* Count of allocations */
 278         uint64_t                uc_frees;       /* Count of frees */
 279 } UMA_ALIGN;
 280
 281 typedef struct uma_cache * uma_cache_t;
 282
 283 LIST_HEAD(slabhead, uma_slab);
 284
 285 /*
 286  * The cache structure pads perfectly into 64 bytes so we use spare
 287  * bits from the embedded cache buckets to store information from the zone
 288  * and keep all fast-path allocations accessing a single per-cpu line.
 289  */
 290 static inline void
 291 cache_set_uz_flags(uma_cache_t cache, uint32_t flags)
 292 {
 293
 294         cache->uc_freebucket.ucb_spare = flags;
 295 }
 296
 297 static inline void
 298 cache_set_uz_size(uma_cache_t cache, uint32_t size)
 299 {
 300
 301         cache->uc_allocbucket.ucb_spare = size;
 302 }
 303
 304 static inline uint32_t
 305 cache_uz_flags(uma_cache_t cache)
 306 {
 307
 308         return (cache->uc_freebucket.ucb_spare);
 309 }
 310
 311 static inline uint32_t
 312 cache_uz_size(uma_cache_t cache)
 313 {
 314
 315         return (cache->uc_allocbucket.ucb_spare);
 316 }
 317
 318 /*
 319  * Per-domain slab lists.  Embedded in the kegs.
 320  */
 321 struct uma_domain {
 322         struct mtx_padalign ud_lock;    /* Lock for the domain lists. */
 323         struct slabhead ud_part_slab;   /* partially allocated slabs */
 324         struct slabhead ud_free_slab;   /* completely unallocated slabs */
 325         struct slabhead ud_full_slab;   /* fully allocated slabs */
 326         uint32_t        ud_pages;       /* Total page count */
 327         uint32_t        ud_free_items;  /* Count of items free in all slabs */
 328         uint32_t        ud_free_slabs;  /* Count of free slabs */
 329 } __aligned(CACHE_LINE_SIZE);
 330
 331 typedef struct uma_domain * uma_domain_t;
 332
 333 /*
 334  * Keg management structure
 335  *
 336  * TODO: Optimize for cache line size
 337  *
 338  */
 339 struct uma_keg {
 340         struct uma_hash uk_hash;
 341         LIST_HEAD(,uma_zone)    uk_zones;       /* Keg's zones */
 342
 343         struct domainset_ref uk_dr;     /* Domain selection policy. */
 344         uint32_t        uk_align;       /* Alignment mask */
 345         uint32_t        uk_reserve;     /* Number of reserved items. */
 346         uint32_t        uk_size;        /* Requested size of each item */
 347         uint32_t        uk_rsize;       /* Real size of each item */
 348
 349         uma_init        uk_init;        /* Keg's init routine */
 350         uma_fini        uk_fini;        /* Keg's fini routine */
 351         uma_alloc       uk_allocf;      /* Allocation function */
 352         uma_free        uk_freef;       /* Free routine */
 353
 354         u_long          uk_offset;      /* Next free offset from base KVA */
 355         vm_offset_t     uk_kva;         /* Zone base KVA */
 356
 357         uint32_t        uk_pgoff;       /* Offset to uma_slab struct */
 358         uint16_t        uk_ppera;       /* pages per allocation from backend */
 359         uint16_t        uk_ipers;       /* Items per slab */
 360         uint32_t        uk_flags;       /* Internal flags */
 361
 362         /* Least used fields go to the last cache line. */
 363         const char      *uk_name;               /* Name of creating zone. */
 364         LIST_ENTRY(uma_keg)     uk_link;        /* List of all kegs */
 365
 366         /* Must be last, variable sized. */
 367         struct uma_domain       uk_domain[];    /* Keg's slab lists. */
 368 };
 369 typedef struct uma_keg  * uma_keg_t;
 370
 371 #ifdef _KERNEL
 372 #define KEG_ASSERT_COLD(k)                                              \
 373         KASSERT(uma_keg_get_allocs((k)) == 0,                           \
 374             ("keg %s initialization after use.", (k)->uk_name))
 375
 376 /*
 377  * Free bits per-slab.
 378  */
 379 #define SLAB_MAX_SETSIZE        (PAGE_SIZE / UMA_SMALLEST_UNIT)
 380 #define SLAB_MIN_SETSIZE        _BITSET_BITS
 381 BITSET_DEFINE(noslabbits, 0);
 382
 383 /*
 384  * The slab structure manages a single contiguous allocation from backing
 385  * store and subdivides it into individually allocatable items.
 386  */
 387 struct uma_slab {
 388         LIST_ENTRY(uma_slab)    us_link;        /* slabs in zone */
 389         uint16_t        us_freecount;           /* How many are free? */
 390         uint8_t         us_flags;               /* Page flags see uma.h */
 391         uint8_t         us_domain;              /* Backing NUMA domain. */
 392         struct noslabbits us_free;              /* Free bitmask, flexible. */
 393 };
 394 _Static_assert(sizeof(struct uma_slab) == offsetof(struct uma_slab, us_free),
 395     "us_free field must be last");
 396 #if MAXMEMDOM >= 255
 397 #error "Slab domain type insufficient"
 398 #endif
 399
 400 typedef struct uma_slab * uma_slab_t;
 401
 402 /*
 403  * On INVARIANTS builds, the slab contains a second bitset of the same size,
 404  * "dbg_bits", which is laid out immediately after us_free.
 405  */
 406 #ifdef INVARIANTS
 407 #define SLAB_BITSETS    2
 408 #else
 409 #define SLAB_BITSETS    1
 410 #endif
 411
 412 /* These three functions are for embedded (!OFFPAGE) use only. */
 413 size_t slab_sizeof(int nitems);
 414 size_t slab_space(int nitems);
 415 int slab_ipers(size_t size, int align);
 416
 417 /*
 418  * Slab structure with a full sized bitset and hash link for both
 419  * HASH and OFFPAGE zones.
 420  */
 421 struct uma_hash_slab {
 422         LIST_ENTRY(uma_hash_slab) uhs_hlink;    /* Link for hash table */
 423         uint8_t                 *uhs_data;      /* First item */
 424         struct uma_slab         uhs_slab;       /* Must be last. */
 425 };
 426
 427 typedef struct uma_hash_slab * uma_hash_slab_t;
 428
 429 static inline uma_hash_slab_t
 430 slab_tohashslab(uma_slab_t slab)
 431 {
 432
 433         return (__containerof(slab, struct uma_hash_slab, uhs_slab));
 434 }
 435
 436 static inline void *
 437 slab_data(uma_slab_t slab, uma_keg_t keg)
 438 {
 439
 440         if ((keg->uk_flags & UMA_ZFLAG_OFFPAGE) == 0)
 441                 return ((void *)((uintptr_t)slab - keg->uk_pgoff));
 442         else
 443                 return (slab_tohashslab(slab)->uhs_data);
 444 }
 445
 446 static inline void *
 447 slab_item(uma_slab_t slab, uma_keg_t keg, int index)
 448 {
 449         uintptr_t data;
 450
 451         data = (uintptr_t)slab_data(slab, keg);
 452         return ((void *)(data + keg->uk_rsize * index));
 453 }
 454
 455 static inline int
 456 slab_item_index(uma_slab_t slab, uma_keg_t keg, void *item)
 457 {
 458         uintptr_t data;
 459
 460         data = (uintptr_t)slab_data(slab, keg);
 461         return (((uintptr_t)item - data) / keg->uk_rsize);
 462 }
 463 #endif /* _KERNEL */
 464
 465 STAILQ_HEAD(uma_bucketlist, uma_bucket);
 466
 467 struct uma_zone_domain {
 468         struct uma_bucketlist uzd_buckets; /* full buckets */
 469         uma_bucket_t    uzd_cross;      /* Fills from cross buckets. */
 470         long            uzd_nitems;     /* total item count */
 471         long            uzd_imax;       /* maximum item count this period */
 472         long            uzd_imin;       /* minimum item count this period */
 473         long            uzd_wss;        /* working set size estimate */
 474         smr_seq_t       uzd_seq;        /* Lowest queued seq. */
 475         struct mtx      uzd_lock;       /* Lock for the domain */
 476 } __aligned(CACHE_LINE_SIZE);
 477
 478 typedef struct uma_zone_domain * uma_zone_domain_t;
 479
 480 /*
 481  * Zone structure - per memory type.
 482  */
 483 struct uma_zone {
 484         /* Offset 0, used in alloc/free fast/medium fast path and const. */
 485         uint32_t        uz_flags;       /* Flags inherited from kegs */
 486         uint32_t        uz_size;        /* Size inherited from kegs */
 487         uma_ctor        uz_ctor;        /* Constructor for each allocation */
 488         uma_dtor        uz_dtor;        /* Destructor */
 489         smr_t           uz_smr;         /* Safe memory reclaim context. */
 490         uint64_t        uz_max_items;   /* Maximum number of items to alloc */
 491         uint64_t        uz_bucket_max;  /* Maximum bucket cache size */
 492         uint16_t        uz_bucket_size; /* Number of items in full bucket */
 493         uint16_t        uz_bucket_size_max; /* Maximum number of bucket items */
 494         uint32_t        uz_sleepers;    /* Threads sleeping on limit */
 495         counter_u64_t   uz_xdomain;     /* Total number of cross-domain frees */
 496
 497         /* Offset 64, used in bucket replenish. */
 498         uma_keg_t       uz_keg;         /* This zone's keg if !CACHE */
 499         uma_import      uz_import;      /* Import new memory to cache. */
 500         uma_release     uz_release;     /* Release memory from cache. */
 501         void            *uz_arg;        /* Import/release argument. */
 502         uma_init        uz_init;        /* Initializer for each item */
 503         uma_fini        uz_fini;        /* Finalizer for each item. */
 504         volatile uint64_t uz_items;     /* Total items count & sleepers */
 505         uint64_t        uz_sleeps;      /* Total number of alloc sleeps */
 506
 507         /* Offset 128 Rare stats, misc read-only. */
 508         LIST_ENTRY(uma_zone) uz_link;   /* List of all zones in keg */
 509         counter_u64_t   uz_allocs;      /* Total number of allocations */
 510         counter_u64_t   uz_frees;       /* Total number of frees */
 511         counter_u64_t   uz_fails;       /* Total number of alloc failures */
 512         const char      *uz_name;       /* Text name of the zone */
 513         char            *uz_ctlname;    /* sysctl safe name string. */
 514         int             uz_namecnt;     /* duplicate name count. */
 515         uint16_t        uz_bucket_size_min; /* Min number of items in bucket */
 516         uint16_t        uz_pad0;
 517
 518         /* Offset 192, rare read-only. */
 519         struct sysctl_oid *uz_oid;      /* sysctl oid pointer. */
 520         const char      *uz_warning;    /* Warning to print on failure */
 521         struct timeval  uz_ratecheck;   /* Warnings rate-limiting */
 522         struct task     uz_maxaction;   /* Task to run when at limit */
 523
 524         /* Offset 256. */
 525         struct mtx      uz_cross_lock;  /* Cross domain free lock */
 526
 527         /*
 528          * This HAS to be the last item because we adjust the zone size
 529          * based on NCPU and then allocate the space for the zones.
 530          */
 531         struct uma_cache        uz_cpu[]; /* Per cpu caches */
 532
 533         /* domains follow here. */
 534 };
 535
 536 /*
 537  * Macros for interpreting the uz_items field.  20 bits of sleeper count
 538  * and 44 bit of item count.
 539  */
 540 #define UZ_ITEMS_SLEEPER_SHIFT  44LL
 541 #define UZ_ITEMS_SLEEPERS_MAX   ((1 << (64 - UZ_ITEMS_SLEEPER_SHIFT)) - 1)
 542 #define UZ_ITEMS_COUNT_MASK     ((1LL << UZ_ITEMS_SLEEPER_SHIFT) - 1)
 543 #define UZ_ITEMS_COUNT(x)       ((x) & UZ_ITEMS_COUNT_MASK)
 544 #define UZ_ITEMS_SLEEPERS(x)    ((x) >> UZ_ITEMS_SLEEPER_SHIFT)
 545 #define UZ_ITEMS_SLEEPER        (1LL << UZ_ITEMS_SLEEPER_SHIFT)
 546
 547 #define ZONE_ASSERT_COLD(z)                                             \
 548         KASSERT(uma_zone_get_allocs((z)) == 0,                          \
 549             ("zone %s initialization after use.", (z)->uz_name))
 550
 551 #undef  UMA_ALIGN
 552
 553 #ifdef _KERNEL
 554 /* Internal prototypes */
 555 static __inline uma_slab_t hash_sfind(struct uma_hash *hash, uint8_t *data);
 556
 557 /* Lock Macros */
 558
 559 #define KEG_LOCKPTR(k, d)       (struct mtx *)&(k)->uk_domain[(d)].ud_lock
 560 #define KEG_LOCK_INIT(k, d, lc)                                         \
 561         do {                                                            \
 562                 if ((lc))                                               \
 563                         mtx_init(KEG_LOCKPTR(k, d), (k)->uk_name,       \
 564                             (k)->uk_name, MTX_DEF | MTX_DUPOK);         \
 565                 else                                                    \
 566                         mtx_init(KEG_LOCKPTR(k, d), (k)->uk_name,       \
 567                             "UMA zone", MTX_DEF | MTX_DUPOK);           \
 568         } while (0)
 569
 570 #define KEG_LOCK_FINI(k, d)     mtx_destroy(KEG_LOCKPTR(k, d))
 571 #define KEG_LOCK(k, d)                                                  \
 572         ({ mtx_lock(KEG_LOCKPTR(k, d)); KEG_LOCKPTR(k, d); })
 573 #define KEG_UNLOCK(k, d)        mtx_unlock(KEG_LOCKPTR(k, d))
 574 #define KEG_LOCK_ASSERT(k, d)   mtx_assert(KEG_LOCKPTR(k, d), MA_OWNED)
 575
 576 #define KEG_GET(zone, keg) do {                                 \
 577         (keg) = (zone)->uz_keg;                                 \
 578         KASSERT((void *)(keg) != NULL,                          \
 579             ("%s: Invalid zone %p type", __func__, (zone)));    \
 580         } while (0)
 581
 582 /* Domains are contiguous after the last CPU */
 583 #define ZDOM_GET(z, n)                                                  \
 584     (&((uma_zone_domain_t)&(z)->uz_cpu[mp_maxid + 1])[n])
 585
 586 #define ZDOM_LOCK_INIT(z, zdom, lc)                                     \
 587         do {                                                            \
 588                 if ((lc))                                               \
 589                         mtx_init(&(zdom)->uzd_lock, (z)->uz_name,       \
 590                             (z)->uz_name, MTX_DEF | MTX_DUPOK);         \
 591                 else                                                    \
 592                         mtx_init(&(zdom)->uzd_lock, (z)->uz_name,       \
 593                             "UMA zone", MTX_DEF | MTX_DUPOK);           \
 594         } while (0)
 595 #define ZDOM_LOCK_FINI(z)       mtx_destroy(&(z)->uzd_lock)
 596 #define ZDOM_LOCK_ASSERT(z)     mtx_assert(&(z)->uzd_lock, MA_OWNED)
 597
 598 #define ZDOM_LOCK(z)    mtx_lock(&(z)->uzd_lock)
 599 #define ZDOM_OWNED(z)   (mtx_owner(&(z)->uzd_lock) != NULL)
 600 #define ZDOM_UNLOCK(z)  mtx_unlock(&(z)->uzd_lock)
 601
 602 #define ZONE_LOCK(z)    ZDOM_LOCK(ZDOM_GET((z), 0))
 603 #define ZONE_UNLOCK(z)  ZDOM_UNLOCK(ZDOM_GET((z), 0))
 604
 605 #define ZONE_CROSS_LOCK_INIT(z)                                 \
 606         mtx_init(&(z)->uz_cross_lock, "UMA Cross", NULL, MTX_DEF)
 607 #define ZONE_CROSS_LOCK(z)      mtx_lock(&(z)->uz_cross_lock)
 608 #define ZONE_CROSS_UNLOCK(z)    mtx_unlock(&(z)->uz_cross_lock)
 609 #define ZONE_CROSS_LOCK_FINI(z) mtx_destroy(&(z)->uz_cross_lock)
 610
 611 /*
 612  * Find a slab within a hash table.  This is used for OFFPAGE zones to lookup
 613  * the slab structure.
 614  *
 615  * Arguments:
 616  *      hash  The hash table to search.
 617  *      data  The base page of the item.
 618  *
 619  * Returns:
 620  *      A pointer to a slab if successful, else NULL.
 621  */
 622 static __inline uma_slab_t
 623 hash_sfind(struct uma_hash *hash, uint8_t *data)
 624 {
 625         uma_hash_slab_t slab;
 626         u_int hval;
 627
 628         hval = UMA_HASH(hash, data);
 629
 630         LIST_FOREACH(slab, &hash->uh_slab_hash[hval], uhs_hlink) {
 631                 if ((uint8_t *)slab->uhs_data == data)
 632                         return (&slab->uhs_slab);
 633         }
 634         return (NULL);
 635 }
 636
 637 static __inline uma_slab_t
 638 vtoslab(vm_offset_t va)
 639 {
 640         vm_page_t p;
 641
 642         p = PHYS_TO_VM_PAGE(pmap_kextract(va));
 643         return (p->plinks.uma.slab);
 644 }
 645
 646 static __inline void
 647 vtozoneslab(vm_offset_t va, uma_zone_t *zone, uma_slab_t *slab)
 648 {
 649         vm_page_t p;
 650
 651         p = PHYS_TO_VM_PAGE(pmap_kextract(va));
 652         *slab = p->plinks.uma.slab;
 653         *zone = p->plinks.uma.zone;
 654 }
 655
 656 static __inline void
 657 vsetzoneslab(vm_offset_t va, uma_zone_t zone, uma_slab_t slab)
 658 {
 659         vm_page_t p;
 660
 661         p = PHYS_TO_VM_PAGE(pmap_kextract(va));
 662         p->plinks.uma.slab = slab;
 663         p->plinks.uma.zone = zone;
 664 }
 665
 666 extern unsigned long uma_kmem_limit;
 667 extern unsigned long uma_kmem_total;
 668
 669 /* Adjust bytes under management by UMA. */
 670 static inline void
 671 uma_total_dec(unsigned long size)
 672 {
 673
 674         atomic_subtract_long(&uma_kmem_total, size);
 675 }
 676
 677 static inline void
 678 uma_total_inc(unsigned long size)
 679 {
 680
 681         if (atomic_fetchadd_long(&uma_kmem_total, size) > uma_kmem_limit)
 682                 uma_reclaim_wakeup();
 683 }
 684
 685 /*
 686  * The following two functions may be defined by architecture specific code
 687  * if they can provide more efficient allocation functions.  This is useful
 688  * for using direct mapped addresses.
 689  */
 690 void *uma_small_alloc(uma_zone_t zone, vm_size_t bytes, int domain,
 691     uint8_t *pflag, int wait);
 692 void uma_small_free(void *mem, vm_size_t size, uint8_t flags);
 693
 694 /* Set a global soft limit on UMA managed memory. */
 695 void uma_set_limit(unsigned long limit);
 696
 697 #endif /* _KERNEL */
 698
 699 #endif /* VM_UMA_INT_H */