xnu-6153.61.1.tar.gz

[apple/xnu.git] / osfmk / kern / zcache.h

/*
 * Copyright (c) 2017 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
/*
 *      Below is a diagram of the caching system. This design is based of the
 * paper "Magazines and Vmem: Extending the Slab Allocator to Many CPUs and
 * Arbitrary Resources" by Jeff Bonwick and Jonathan Adams. It is divided into 3
 * layers: the Per-cpu Layer, the Depot Layer, and the Zone Allocator. The
 * Per-CPU and Depot layers store elements using arrays we call magazines.
 *
 *      Magazines function like a stack (we push and pop elements) and can be
 *  moved around for bulk operations.
 *  _________         _________         _________
 * |  CPU 1  |       |  CPU 2  |       |  CPU 3  |
 * |  _   _  |       |  _   _  |       |  _   _  |
 * | |#| | | |       | | | |#| |       | |#| |#| |        Per-CPU Layer
 * | |#| |_| |       | |_| |#| |       | |#| |#| |
 * |_________|       |_________|       |_________|
 *
 *  ______________________________________________
 * |            _   _   _   _   _   _             |
 * |           |#| |#| |#| | | | | | |            |     Depot Layer
 * |           |#| |#| |#| |_| |_| |_|            |
 * |______________________________________________|
 *
 *  _______________________________________________
 * | # | # | # | # | # | # | # | # | # | # | # | # |   Zone Allocator
 * |_______________________________________________|
 *
 *	The top layer is the per-cpu cache and consists of a current and
 * previous magazine for each CPU. The current magazine is the one we always try
 * to allocate from and free to first. Only if we are unable, do we check the
 * previous magazine. If the previous magazine can satisfy the allocate or free,
 * then we switch the two and allocate from the new current magazine. This layer
 * requires no locking, so we can access multiple CPU's caches concurrently.
 * This is the main source of the speedup.
 *
 *      We have two magazines here to prevent thrashing when swapping magazines
 * with the depot layer. If a certain pattern of alloc and free are called we
 * can waste a lot of time swapping magazines to and from the depot layer. We
 * prevent this by dividing the per-cpu cache into two separate magazines.
 *
 *	The middle layer is the magazine depot. This layer consists of a
 * collection of full and empty magazines. These are used to reload the per-cpu
 * caches when needed. This is implemented as an array of magazines which are
 * initially all empty and as we fill up magazines we increment the index to
 * point at the first empty magazine. Since this layer is per-zone, it allows us
 *  to balance the cache between cpus, but does require taking a lock.
 *
 *      When neither the current nor previous magazine for a given CPU can
 * satisfy the free or allocation, we look to the depot layer. If there are
 * magazines in the depot that can satisfy the free or allocation we swap
 * that magazine into the current position. In the example below, to allocate on
 * the given CPU we must lock the depot layer and swap magazine A with magazine
 * B and decrement the depot index.
 *
 *      _____________________       _______________________________________
 *     |    Per-CPU Cache    |     |              Depot Layer              |
 *     |                     |     |                                       |
 *     |   A___      ____    |     |   ____      B___      ____      ____  |
 *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
 *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
 *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
 *     |  |    |    |    |   |     |  | ## |    | ## |    |    |    |    | |
 *     |  |____|    |____|   |     |  |_##_|    |_##_|    |____|    |____| |
 *     | Current   Previous  |     |                                       |
 *     |_____________________|     |_______________________________________|
 *
 *	The bottom layer is the Zone Allocator. This is already implemented in
 *  XNU and will remain mostly unchanged. Implementation for this can be found
 * in zalloc.c and zalloc.h. We will only use the zone if all other layers are
 * unable to satisfy the allocation or free. When we do use the zone, we will
 * try to allocate an entire magazine of elements or free an entire magazine of
 * elements at once.
 *
 *      Caching must be enabled explicitly, by calling zone_change() with the
 * Z_CACHING_ENABLED flag, for every zone you want to cache elements for. Zones
 * which are good candidates for this are ones with highly contended zone locks.
 *
 * Some good potential candidates are kalloc.16, kalloc.48, Vm objects, VM map
 * entries, ipc vouchers, and ipc ports.
 *
 *
 * Some factors can be tuned by boot-arg:
 *  zcc_enable_for_zone_name    name of a single zone to enable caching for
 *				(replace space characters with '.')
 *
 *  zcc_magazine_element_count	integer value for magazine size used for all
 *				zones (default 8 is used if not specified)
 *
 *  zcc_depot_element_count	integer value for how many full and empty
 *				magazines to store in the depot, if N specified
 *				depot will have N full and N empty magazines
 *				(default 16 used if not specified)
 */
#include <kern/kern_types.h>
#include <vm/vm_kern.h>


/*
 * zcache_ready
 *
 * Description: returns whether or not the zone caches are ready to use
 *
 */
bool            zcache_ready(void);


/*
 * zcache_bootstrap
 *
 * Description: initializes zone to allocate magazines from
 *
 */
void            zcache_bootstrap(void);


/*
 * zcache_init
 *
 * Description: Initializes all parts of the per-cpu caches for a given zone
 *
 * Parameters:	zone	pointer to zone on which to iniitalize caching
 *
 */
void            zcache_init(zone_t zone);


/*
 * zcache_free_to_cpu_cache
 *
 * Description: Checks per-cpu caches to free element there if possible
 *
 * Parameters:	zone	pointer to zone for which element comes from
 *		addr	pointer to element to free
 *
 * Returns: TRUE if successfull, FALSE otherwise
 *
 * Precondition: check that caching is enabled for zone
 */
bool            zcache_free_to_cpu_cache(zone_t zone, void *addr);


/*
 * zcache_alloc_from_cpu_cache
 *
 * Description: Checks per-cpu caches to allocate element from there if possible
 *
 * Parameters:	zone	pointer to zone for which element will come from
 *
 * Returns: pointer to usable element
 *
 * Precondition: check that caching is enabled for zone
 */
vm_offset_t     zcache_alloc_from_cpu_cache(zone_t zone);

/*
 * zcache_drain_depot
 *
 * Description: Frees all the full magazines from the depot layer to the zone allocator
 *              Invoked by zone_gc()
 *
 * Parameters:  zone    pointer to zone for which the depot layer needs to be drained
 *
 * Returns: None
 *
 */
void            zcache_drain_depot(zone_t zone);