osfmk/kern/zcache.h

   1 /*
   2  * Copyright (c) 2017 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  *      Below is a diagram of the caching system. This design is based of the
  30  * paper "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and
  31  * Arbitrary Resources" by Jeff Bonwick and Jonathan Adams. It is divided into 3
  32  * layers: the Per-cpu Layer, the Depot Layer, and the Zone Allocator. The
  33  * Per-CPU and Depot layers store elements using arrays we call magazines.
  34  *
  35  *      Magazines function like a stack (we push and pop elements) and can be
  36  *  moved around for bulk operations.
  37  *  _________         _________         _________
  38  * |  CPU 1  |       |  CPU 2  |       |  CPU 3  |
  39  * |  _   _  |       |  _   _  |       |  _   _  |
  40  * | |#| | | |       | | | |#| |       | |#| |#| |        Per-CPU Layer
  41  * | |#| |_| |       | |_| |#| |       | |#| |#| |
  42  * |_________|       |_________|       |_________|
  43  *
  44  *  ______________________________________________
  45  * |            _   _   _   _   _   _             |
  46  * |           |#| |#| |#| | | | | | |            |     Depot Layer
  47  * |           |#| |#| |#| |_| |_| |_|            |
  48  * |______________________________________________|
  49  *
  50  *  _______________________________________________
  51  * | # | # | # | # | # | # | # | # | # | # | # | # |   Zone Allocator
  52  * |_______________________________________________|
  53  *
  54  *      The top layer is the per-cpu cache and consists of a current and
  55  * previous magazine for each CPU. The current magazine is the one we always try
  56  * to allocate from and free to first. Only if we are unable, do we check the
  57  * previous magazine. If the previous magazine can satisfy the allocate or free,
  58  * then we switch the two and allocate from the new current magazine. This layer
  59  * requires no locking, so we can access multiple CPU's caches concurrently.
  60  * This is the main source of the speedup.
  61  *
  62  *      We have two magazines here to prevent thrashing when swapping magazines
  63  * with the depot layer. If a certain pattern of alloc and free are called we
  64  * can waste a lot of time swapping magazines to and from the depot layer. We
  65  * prevent this by dividing the per-cpu cache into two separate magazines.
  66  *
  67  *      The middle layer is the magazine depot. This layer consists of a
  68  * collection of full and empty magazines. These are used to reload the per-cpu
  69  * caches when needed. This is implemented as an array of magazines which are
  70  * initially all empty and as we fill up magazines we increment the index to
  71  * point at the first empty magazine. Since this layer is per-zone, it allows us
  72  *  to balance the cache between cpus, but does require taking a lock.
  73  *
  74  *      When neither the current nor previous magazine for a given CPU can
  75  * satisfy the free or allocation, we look to the depot layer. If there are
  76  * magazines in the depot that can satisfy the free or allocation we swap
  77  * that magazine into the current position. In the example below, to allocate on
  78  * the given CPU we must lock the depot layer and swap magazine A with magazine
  79  * B and decrement the depot index.
  80  *
  81  *      _____________________       _______________________________________
  82  *     |    Per-CPU Cache    |     |              Depot Layer              |
  83  *     |                     |     |                                       |
  84  *     |   A___      ____    |     |   ____      B___      ____      ____  |
  85  *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
  86  *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
  87  *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
  88  *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
  89  *     |  |____|    |____|   |     |  |_##_|    |_##_|    |____|    |____| |
  90  *     | Current   Previous  |     |                                       |
  91  *     |_____________________|     |_______________________________________|
  92  *
  93  *      The bottom layer is the Zone Allocator. This is already implemented in
  94  *  XNU and will remain mostly unchanged. Implementation for this can be found
  95  * in zalloc.c and zalloc.h. We will only use the zone if all other layers are
  96  * unable to satisfy the allocation or free. When we do use the zone, we will
  97  * try to allocate an entire magazine of elements or free an entire magazine of
  98  * elements at once.
  99  *
 100  *      Caching must be enabled explicitly, by calling zone_change() with the
 101  * Z_CACHING_ENABLED flag, for every zone you want to cache elements for. Zones
 102  * which are good candidates for this are ones with highly contended zone locks.
 103  *
 104  * Some good potential candidates are kalloc.16, kalloc.48, Vm objects, VM map
 105  * entries, ipc vouchers, and ipc ports.
 106  *
 107  *
 108  * Some factors can be tuned by boot-arg:
 109  *  zcc_enable_for_zone_name    name of a single zone to enable caching for
 110  *                              (replace space characters with '.')
 111  *
 112  *  zcc_magazine_element_count  integer value for magazine size used for all
 113  *                              zones (default 8 is used if not specified)
 114  *
 115  *  zcc_depot_element_count     integer value for how many full and empty
 116  *                              magazines to store in the depot, if N specified
 117  *                              depot will have N full and N empty magazines
 118  *                              (default 16 used if not specified)
 119  */
 120 #include <kern/kern_types.h>
 121 #include <vm/vm_kern.h>
 122
 123
 124 /*
 125  * zcache_ready
 126  *
 127  * Description: returns whether or not the zone caches are ready to use
 128  *
 129  */
 130 bool            zcache_ready(void);
 131
 132
 133 /*
 134  * zcache_bootstrap
 135  *
 136  * Description: initializes zone to allocate magazines from
 137  *
 138  */
 139 void            zcache_bootstrap(void);
 140
 141
 142 /*
 143  * zcache_init
 144  *
 145  * Description: Initializes all parts of the per-cpu caches for a given zone
 146  *
 147  * Parameters:  zone    pointer to zone on which to iniitalize caching
 148  *
 149  */
 150 void            zcache_init(zone_t zone);
 151
 152
 153 /*
 154  * zcache_free_to_cpu_cache
 155  *
 156  * Description: Checks per-cpu caches to free element there if possible
 157  *
 158  * Parameters:  zone    pointer to zone for which element comes from
 159  *              addr    pointer to element to free
 160  *
 161  * Returns: TRUE if successfull, FALSE otherwise
 162  *
 163  * Precondition: check that caching is enabled for zone
 164  */
 165 bool            zcache_free_to_cpu_cache(zone_t zone, void *addr);
 166
 167
 168 /*
 169  * zcache_alloc_from_cpu_cache
 170  *
 171  * Description: Checks per-cpu caches to allocate element from there if possible
 172  *
 173  * Parameters:  zone    pointer to zone for which element will come from
 174  *
 175  * Returns: pointer to usable element
 176  *
 177  * Precondition: check that caching is enabled for zone
 178  */
 179 vm_offset_t     zcache_alloc_from_cpu_cache(zone_t zone);
 180
 181 /*
 182  * zcache_drain_depot
 183  *
 184  * Description: Frees all the full magazines from the depot layer to the zone allocator
 185  *              Invoked by zone_gc()
 186  *
 187  * Parameters:  zone    pointer to zone for which the depot layer needs to be drained
 188  *
 189  * Returns: None
 190  *
 191  */
 192 void            zcache_drain_depot(zone_t zone);