xnu-7195.101.1.tar.gz

[apple/xnu.git] / bsd / kern / mcache.c

/*
 * Copyright (c) 2006-2020 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@
 */

/*
 * Memory allocator with per-CPU caching, derived from the kmem magazine
 * concept and implementation as described in the following paper:
 * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick.pdf
 * That implementation is Copyright 2006 Sun Microsystems, Inc.  All rights
 * reserved.  Use is subject to license terms.
 *
 * There are several major differences between this and the original kmem
 * magazine: this derivative implementation allows for multiple objects to
 * be allocated and freed from/to the object cache in one call; in addition,
 * it provides for better flexibility where the user is allowed to define
 * its own slab allocator (instead of the default zone allocator).  Finally,
 * no object construction/destruction takes place at the moment, although
 * this could be added in future to improve efficiency.
 */

#include <sys/param.h>
#include <sys/types.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/queue.h>
#include <sys/kernel.h>
#include <sys/systm.h>

#include <kern/debug.h>
#include <kern/zalloc.h>
#include <kern/cpu_number.h>
#include <kern/locks.h>
#include <kern/thread_call.h>

#include <libkern/libkern.h>
#include <libkern/OSAtomic.h>
#include <libkern/OSDebug.h>

#include <mach/vm_param.h>
#include <machine/limits.h>
#include <machine/machine_routines.h>

#include <string.h>

#include <sys/mcache.h>

#define MCACHE_SIZE(n) \
        __builtin_offsetof(mcache_t, mc_cpu[n])

/* Allocate extra in case we need to manually align the pointer */
#define MCACHE_ALLOC_SIZE \
        (sizeof (void *) + MCACHE_SIZE(ncpu) + CPU_CACHE_LINE_SIZE)

#define MCACHE_CPU(c) \
        (mcache_cpu_t *)((void *)((char *)(c) + MCACHE_SIZE(cpu_number())))

/*
 * MCACHE_LIST_LOCK() and MCACHE_LIST_UNLOCK() are macros used
 * to serialize accesses to the global list of caches in the system.
 * They also record the thread currently running in the critical
 * section, so that we can avoid recursive requests to reap the
 * caches when memory runs low.
 */
#define MCACHE_LIST_LOCK() {                            \
        lck_mtx_lock(&mcache_llock);                     \
        mcache_llock_owner = current_thread();          \
}

#define MCACHE_LIST_UNLOCK() {                          \
        mcache_llock_owner = NULL;                      \
        lck_mtx_unlock(&mcache_llock);                   \
}

#define MCACHE_LOCK(l)          lck_mtx_lock(l)
#define MCACHE_UNLOCK(l)        lck_mtx_unlock(l)
#define MCACHE_LOCK_TRY(l)      lck_mtx_try_lock(l)

static unsigned int ncpu;
static unsigned int cache_line_size;
static struct thread *mcache_llock_owner;
static LCK_GRP_DECLARE(mcache_llock_grp, "mcache.list");
static LCK_MTX_DECLARE(mcache_llock, &mcache_llock_grp);
static struct zone *mcache_zone;
static const uint32_t mcache_reap_interval = 15;
static const uint32_t mcache_reap_interval_leeway = 2;
static UInt32 mcache_reaping;
static int mcache_ready;
static int mcache_updating;

static int mcache_bkt_contention = 3;
#if DEBUG
static unsigned int mcache_flags = MCF_DEBUG;
#else
static unsigned int mcache_flags = 0;
#endif

int mca_trn_max = MCA_TRN_MAX;

static mcache_bkttype_t mcache_bkttype[] = {
        { 1, 4096, 32768, NULL },
        { 3, 2048, 16384, NULL },
        { 7, 1024, 12288, NULL },
        { 15, 256, 8192, NULL },
        { 31, 64, 4096, NULL },
        { 47, 0, 2048, NULL },
        { 63, 0, 1024, NULL },
        { 95, 0, 512, NULL },
        { 143, 0, 256, NULL },
        { 165, 0, 0, NULL },
};

static mcache_t *mcache_create_common(const char *, size_t, size_t,
    mcache_allocfn_t, mcache_freefn_t, mcache_auditfn_t, mcache_logfn_t,
    mcache_notifyfn_t, void *, u_int32_t, int);
static unsigned int mcache_slab_alloc(void *, mcache_obj_t ***,
    unsigned int, int);
static void mcache_slab_free(void *, mcache_obj_t *, boolean_t);
static void mcache_slab_audit(void *, mcache_obj_t *, boolean_t);
static void mcache_cpu_refill(mcache_cpu_t *, mcache_bkt_t *, int);
static mcache_bkt_t *mcache_bkt_alloc(mcache_t *, mcache_bktlist_t *);
static void mcache_bkt_free(mcache_t *, mcache_bktlist_t *, mcache_bkt_t *);
static void mcache_cache_bkt_enable(mcache_t *);
static void mcache_bkt_purge(mcache_t *);
static void mcache_bkt_destroy(mcache_t *, mcache_bkt_t *, int);
static void mcache_bkt_ws_update(mcache_t *);
static void mcache_bkt_ws_zero(mcache_t *);
static void mcache_bkt_ws_reap(mcache_t *);
static void mcache_dispatch(void (*)(void *), void *);
static void mcache_cache_reap(mcache_t *);
static void mcache_cache_update(mcache_t *);
static void mcache_cache_bkt_resize(void *);
static void mcache_cache_enable(void *);
static void mcache_update(thread_call_param_t __unused, thread_call_param_t __unused);
static void mcache_update_timeout(void *);
static void mcache_applyall(void (*)(mcache_t *));
static void mcache_reap_start(void *);
static void mcache_reap_done(void *);
static void mcache_reap_timeout(thread_call_param_t __unused, thread_call_param_t);
static void mcache_notify(mcache_t *, u_int32_t);
static void mcache_purge(void *);

static LIST_HEAD(, mcache) mcache_head;
mcache_t *mcache_audit_cache;

static thread_call_t mcache_reap_tcall;
static thread_call_t mcache_update_tcall;

/*
 * Initialize the framework; this is currently called as part of BSD init.
 */
__private_extern__ void
mcache_init(void)
{
        mcache_bkttype_t *btp;
        unsigned int i;
        char name[32];

        VERIFY(mca_trn_max >= 2);

        ncpu = ml_wait_max_cpus();
        (void) mcache_cache_line_size();        /* prime it */

        mcache_reap_tcall = thread_call_allocate(mcache_reap_timeout, NULL);
        mcache_update_tcall = thread_call_allocate(mcache_update, NULL);
        if (mcache_reap_tcall == NULL || mcache_update_tcall == NULL) {
                panic("mcache_init: thread_call_allocate failed");
                /* NOTREACHED */
                __builtin_unreachable();
        }

        mcache_zone = zone_create("mcache", MCACHE_ALLOC_SIZE, ZC_DESTRUCTIBLE);

        LIST_INIT(&mcache_head);

        for (i = 0; i < sizeof(mcache_bkttype) / sizeof(*btp); i++) {
                btp = &mcache_bkttype[i];
                (void) snprintf(name, sizeof(name), "bkt_%d",
                    btp->bt_bktsize);
                btp->bt_cache = mcache_create(name,
                    (btp->bt_bktsize + 1) * sizeof(void *), 0, 0, MCR_SLEEP);
        }

        PE_parse_boot_argn("mcache_flags", &mcache_flags, sizeof(mcache_flags));
        mcache_flags &= MCF_FLAGS_MASK;

        mcache_audit_cache = mcache_create("audit", sizeof(mcache_audit_t),
            0, 0, MCR_SLEEP);

        mcache_applyall(mcache_cache_bkt_enable);
        mcache_ready = 1;

        printf("mcache: %d CPU(s), %d bytes CPU cache line size\n",
            ncpu, CPU_CACHE_LINE_SIZE);
}

/*
 * Return the global mcache flags.
 */
__private_extern__ unsigned int
mcache_getflags(void)
{
        return mcache_flags;
}

/*
 * Return the CPU cache line size.
 */
__private_extern__ unsigned int
mcache_cache_line_size(void)
{
        if (cache_line_size == 0) {
                ml_cpu_info_t cpu_info;
                ml_cpu_get_info(&cpu_info);
                cache_line_size = (unsigned int)cpu_info.cache_line_size;
        }
        return cache_line_size;
}

/*
 * Create a cache using the zone allocator as the backend slab allocator.
 * The caller may specify any alignment for the object; if it specifies 0
 * the default alignment (MCACHE_ALIGN) will be used.
 */
__private_extern__ mcache_t *
mcache_create(const char *name, size_t bufsize, size_t align,
    u_int32_t flags, int wait __unused)
{
        return mcache_create_common(name, bufsize, align, mcache_slab_alloc,
                   mcache_slab_free, mcache_slab_audit, NULL, NULL, NULL, flags, 1);
}

/*
 * Create a cache using a custom backend slab allocator.  Since the caller
 * is responsible for allocation, no alignment guarantee will be provided
 * by this framework.
 */
__private_extern__ mcache_t *
mcache_create_ext(const char *name, size_t bufsize,
    mcache_allocfn_t allocfn, mcache_freefn_t freefn, mcache_auditfn_t auditfn,
    mcache_logfn_t logfn, mcache_notifyfn_t notifyfn, void *arg,
    u_int32_t flags, int wait __unused)
{
        return mcache_create_common(name, bufsize, 0, allocfn,
                   freefn, auditfn, logfn, notifyfn, arg, flags, 0);
}

/*
 * Common cache creation routine.
 */
static mcache_t *
mcache_create_common(const char *name, size_t bufsize, size_t align,
    mcache_allocfn_t allocfn, mcache_freefn_t freefn, mcache_auditfn_t auditfn,
    mcache_logfn_t logfn, mcache_notifyfn_t notifyfn, void *arg,
    u_int32_t flags, int need_zone)
{
        mcache_bkttype_t *btp;
        mcache_t *cp = NULL;
        size_t chunksize;
        void *buf, **pbuf;
        unsigned int c;
        char lck_name[64];

        buf = zalloc_flags(mcache_zone, Z_WAITOK | Z_ZERO);
        if (buf == NULL) {
                goto fail;
        }

        /*
         * In case we didn't get a cache-aligned memory, round it up
         * accordingly.  This is needed in order to get the rest of
         * structure members aligned properly.  It also means that
         * the memory span gets shifted due to the round up, but it
         * is okay since we've allocated extra space for this.
         */
        cp = (mcache_t *)
            P2ROUNDUP((intptr_t)buf + sizeof(void *), CPU_CACHE_LINE_SIZE);
        pbuf = (void **)((intptr_t)cp - sizeof(void *));
        *pbuf = buf;

        /*
         * Guaranteed alignment is valid only when we use the internal
         * slab allocator (currently set to use the zone allocator).
         */
        if (!need_zone) {
                align = 1;
        } else {
                /* Enforce 64-bit minimum alignment for zone-based buffers */
                if (align == 0) {
                        align = MCACHE_ALIGN;
                }
                align = P2ROUNDUP(align, MCACHE_ALIGN);
        }

        if ((align & (align - 1)) != 0) {
                panic("mcache_create: bad alignment %lu", align);
                /* NOTREACHED */
                __builtin_unreachable();
        }

        cp->mc_align = align;
        cp->mc_slab_alloc = allocfn;
        cp->mc_slab_free = freefn;
        cp->mc_slab_audit = auditfn;
        cp->mc_slab_log = logfn;
        cp->mc_slab_notify = notifyfn;
        cp->mc_private = need_zone ? cp : arg;
        cp->mc_bufsize = bufsize;
        cp->mc_flags = (flags & MCF_FLAGS_MASK) | mcache_flags;

        (void) snprintf(cp->mc_name, sizeof(cp->mc_name), "mcache.%s", name);

        (void) snprintf(lck_name, sizeof(lck_name), "%s.cpu", cp->mc_name);
        cp->mc_cpu_lock_grp = lck_grp_alloc_init(lck_name, LCK_GRP_ATTR_NULL);

        /*
         * Allocation chunk size is the object's size plus any extra size
         * needed to satisfy the object's alignment.  It is enforced to be
         * at least the size of an LP64 pointer to simplify auditing and to
         * handle multiple-element allocation requests, where the elements
         * returned are linked together in a list.
         */
        chunksize = MAX(bufsize, sizeof(u_int64_t));
        if (need_zone) {
                VERIFY(align != 0 && (align % MCACHE_ALIGN) == 0);
                chunksize += sizeof(uint64_t) + align;
                chunksize = P2ROUNDUP(chunksize, align);
                cp->mc_slab_zone = zone_create(cp->mc_name, chunksize, ZC_DESTRUCTIBLE);
        }
        cp->mc_chunksize = chunksize;

        /*
         * Initialize the bucket layer.
         */
        (void) snprintf(lck_name, sizeof(lck_name), "%s.bkt", cp->mc_name);
        cp->mc_bkt_lock_grp = lck_grp_alloc_init(lck_name,
            LCK_GRP_ATTR_NULL);
        lck_mtx_init(&cp->mc_bkt_lock, cp->mc_bkt_lock_grp, LCK_ATTR_NULL);

        (void) snprintf(lck_name, sizeof(lck_name), "%s.sync", cp->mc_name);
        cp->mc_sync_lock_grp = lck_grp_alloc_init(lck_name,
            LCK_GRP_ATTR_NULL);
        lck_mtx_init(&cp->mc_sync_lock, cp->mc_sync_lock_grp, LCK_ATTR_NULL);

        for (btp = mcache_bkttype; chunksize <= btp->bt_minbuf; btp++) {
                continue;
        }

        cp->cache_bkttype = btp;

        /*
         * Initialize the CPU layer.  Each per-CPU structure is aligned
         * on the CPU cache line boundary to prevent false sharing.
         */
        for (c = 0; c < ncpu; c++) {
                mcache_cpu_t *ccp = &cp->mc_cpu[c];

                VERIFY(IS_P2ALIGNED(ccp, CPU_CACHE_LINE_SIZE));
                lck_mtx_init(&ccp->cc_lock, cp->mc_cpu_lock_grp, LCK_ATTR_NULL);
                ccp->cc_objs = -1;
                ccp->cc_pobjs = -1;
        }

        if (mcache_ready) {
                mcache_cache_bkt_enable(cp);
        }

        /* TODO: dynamically create sysctl for stats */

        MCACHE_LIST_LOCK();
        LIST_INSERT_HEAD(&mcache_head, cp, mc_list);
        MCACHE_LIST_UNLOCK();

        /*
         * If cache buckets are enabled and this is the first cache
         * created, start the periodic cache update.
         */
        if (!(mcache_flags & MCF_NOCPUCACHE) && !mcache_updating) {
                mcache_updating = 1;
                mcache_update_timeout(NULL);
        }
        if (cp->mc_flags & MCF_DEBUG) {
                printf("mcache_create: %s (%s) arg %p bufsize %lu align %lu "
                    "chunksize %lu bktsize %d\n", name, need_zone ? "i" : "e",
                    arg, bufsize, cp->mc_align, chunksize, btp->bt_bktsize);
        }
        return cp;

fail:
        if (buf != NULL) {
                zfree(mcache_zone, buf);
        }
        return NULL;
}

/*
 * Allocate one or more objects from a cache.
 */
__private_extern__ unsigned int
mcache_alloc_ext(mcache_t *cp, mcache_obj_t **list, unsigned int num, int wait)
{
        mcache_cpu_t *ccp;
        mcache_obj_t **top = &(*list);
        mcache_bkt_t *bkt;
        unsigned int need = num;
        boolean_t nwretry = FALSE;

        /* MCR_NOSLEEP and MCR_FAILOK are mutually exclusive */
        VERIFY((wait & (MCR_NOSLEEP | MCR_FAILOK)) != (MCR_NOSLEEP | MCR_FAILOK));

        ASSERT(list != NULL);
        *list = NULL;

        if (num == 0) {
                return 0;
        }

retry_alloc:
        /* We may not always be running in the same CPU in case of retries */
        ccp = MCACHE_CPU(cp);

        MCACHE_LOCK(&ccp->cc_lock);
        for (;;) {
                /*
                 * If we have an object in the current CPU's filled bucket,
                 * chain the object to any previous objects and return if
                 * we've satisfied the number of requested objects.
                 */
                if (ccp->cc_objs > 0) {
                        mcache_obj_t *tail;
                        int objs;

                        /*
                         * Objects in the bucket are already linked together
                         * with the most recently freed object at the head of
                         * the list; grab as many objects as we can.
                         */
                        objs = MIN((unsigned int)ccp->cc_objs, need);
                        *list = ccp->cc_filled->bkt_obj[ccp->cc_objs - 1];
                        ccp->cc_objs -= objs;
                        ccp->cc_alloc += objs;

                        tail = ccp->cc_filled->bkt_obj[ccp->cc_objs];
                        list = &tail->obj_next;
                        *list = NULL;

                        /* If we got them all, return to caller */
                        if ((need -= objs) == 0) {
                                MCACHE_UNLOCK(&ccp->cc_lock);

                                if (!(cp->mc_flags & MCF_NOLEAKLOG) &&
                                    cp->mc_slab_log != NULL) {
                                        (*cp->mc_slab_log)(num, *top, TRUE);
                                }

                                if (cp->mc_flags & MCF_DEBUG) {
                                        goto debug_alloc;
                                }

                                return num;
                        }
                }

                /*
                 * The CPU's filled bucket is empty.  If the previous filled
                 * bucket was full, exchange and try again.
                 */
                if (ccp->cc_pobjs > 0) {
                        mcache_cpu_refill(ccp, ccp->cc_pfilled, ccp->cc_pobjs);
                        continue;
                }

                /*
                 * If the bucket layer is disabled, allocate from slab.  This
                 * can happen either because MCF_NOCPUCACHE is set, or because
                 * the bucket layer is currently being resized.
                 */
                if (ccp->cc_bktsize == 0) {
                        break;
                }

                /*
                 * Both of the CPU's buckets are empty; try to get a full
                 * bucket from the bucket layer.  Upon success, refill this
                 * CPU and place any empty bucket into the empty list.
                 */
                bkt = mcache_bkt_alloc(cp, &cp->mc_full);
                if (bkt != NULL) {
                        if (ccp->cc_pfilled != NULL) {
                                mcache_bkt_free(cp, &cp->mc_empty,
                                    ccp->cc_pfilled);
                        }
                        mcache_cpu_refill(ccp, bkt, ccp->cc_bktsize);
                        continue;
                }

                /*
                 * The bucket layer has no full buckets; allocate the
                 * object(s) directly from the slab layer.
                 */
                break;
        }
        MCACHE_UNLOCK(&ccp->cc_lock);

        need -= (*cp->mc_slab_alloc)(cp->mc_private, &list, need, wait);

        /*
         * If this is a blocking allocation, or if it is non-blocking and
         * the cache's full bucket is non-empty, then retry the allocation.
         */
        if (need > 0) {
                if (!(wait & MCR_NONBLOCKING)) {
                        atomic_add_32(&cp->mc_wretry_cnt, 1);
                        goto retry_alloc;
                } else if ((wait & (MCR_NOSLEEP | MCR_TRYHARD)) &&
                    !mcache_bkt_isempty(cp)) {
                        if (!nwretry) {
                                nwretry = TRUE;
                        }
                        atomic_add_32(&cp->mc_nwretry_cnt, 1);
                        goto retry_alloc;
                } else if (nwretry) {
                        atomic_add_32(&cp->mc_nwfail_cnt, 1);
                }
        }

        if (!(cp->mc_flags & MCF_NOLEAKLOG) && cp->mc_slab_log != NULL) {
                (*cp->mc_slab_log)((num - need), *top, TRUE);
        }

        if (!(cp->mc_flags & MCF_DEBUG)) {
                return num - need;
        }

debug_alloc:
        if (cp->mc_flags & MCF_DEBUG) {
                mcache_obj_t **o = top;
                unsigned int n;

                n = 0;
                /*
                 * Verify that the chain of objects have the same count as
                 * what we are about to report to the caller.  Any mismatch
                 * here means that the object list is insanely broken and
                 * therefore we must panic.
                 */
                while (*o != NULL) {
                        o = &(*o)->obj_next;
                        ++n;
                }
                if (n != (num - need)) {
                        panic("mcache_alloc_ext: %s cp %p corrupted list "
                            "(got %d actual %d)\n", cp->mc_name,
                            (void *)cp, num - need, n);
                        /* NOTREACHED */
                        __builtin_unreachable();
                }
        }

        /* Invoke the slab layer audit callback if auditing is enabled */
        if ((cp->mc_flags & MCF_DEBUG) && cp->mc_slab_audit != NULL) {
                (*cp->mc_slab_audit)(cp->mc_private, *top, TRUE);
        }

        return num - need;
}

/*
 * Allocate a single object from a cache.
 */
__private_extern__ void *
mcache_alloc(mcache_t *cp, int wait)
{
        mcache_obj_t *buf;

        (void) mcache_alloc_ext(cp, &buf, 1, wait);
        return buf;
}

__private_extern__ void
mcache_waiter_inc(mcache_t *cp)
{
        atomic_add_32(&cp->mc_waiter_cnt, 1);
}

__private_extern__ void
mcache_waiter_dec(mcache_t *cp)
{
        atomic_add_32(&cp->mc_waiter_cnt, -1);
}

__private_extern__ boolean_t
mcache_bkt_isempty(mcache_t *cp)
{
        /*
         * This isn't meant to accurately tell whether there are
         * any full buckets in the cache; it is simply a way to
         * obtain "hints" about the state of the cache.
         */
        return cp->mc_full.bl_total == 0;
}

/*
 * Notify the slab layer about an event.
 */
static void
mcache_notify(mcache_t *cp, u_int32_t event)
{
        if (cp->mc_slab_notify != NULL) {
                (*cp->mc_slab_notify)(cp->mc_private, event);
        }
}

/*
 * Purge the cache and disable its buckets.
 */
static void
mcache_purge(void *arg)
{
        mcache_t *cp = arg;

        mcache_bkt_purge(cp);
        /*
         * We cannot simply call mcache_cache_bkt_enable() from here as
         * a bucket resize may be in flight and we would cause the CPU
         * layers of the cache to point to different sizes.  Therefore,
         * we simply increment the enable count so that during the next
         * periodic cache update the buckets can be reenabled.
         */
        lck_mtx_lock_spin(&cp->mc_sync_lock);
        cp->mc_enable_cnt++;
        lck_mtx_unlock(&cp->mc_sync_lock);
}

__private_extern__ boolean_t
mcache_purge_cache(mcache_t *cp, boolean_t async)
{
        /*
         * Purging a cache that has no per-CPU caches or is already
         * in the process of being purged is rather pointless.
         */
        if (cp->mc_flags & MCF_NOCPUCACHE) {
                return FALSE;
        }

        lck_mtx_lock_spin(&cp->mc_sync_lock);
        if (cp->mc_purge_cnt > 0) {
                lck_mtx_unlock(&cp->mc_sync_lock);
                return FALSE;
        }
        cp->mc_purge_cnt++;
        lck_mtx_unlock(&cp->mc_sync_lock);

        if (async) {
                mcache_dispatch(mcache_purge, cp);
        } else {
                mcache_purge(cp);
        }

        return TRUE;
}

/*
 * Free a single object to a cache.
 */
__private_extern__ void
mcache_free(mcache_t *cp, void *buf)
{
        ((mcache_obj_t *)buf)->obj_next = NULL;
        mcache_free_ext(cp, (mcache_obj_t *)buf);
}

/*
 * Free one or more objects to a cache.
 */
__private_extern__ void
mcache_free_ext(mcache_t *cp, mcache_obj_t *list)
{
        mcache_cpu_t *ccp = MCACHE_CPU(cp);
        mcache_bkttype_t *btp;
        mcache_obj_t *nlist;
        mcache_bkt_t *bkt;

        if (!(cp->mc_flags & MCF_NOLEAKLOG) && cp->mc_slab_log != NULL) {
                (*cp->mc_slab_log)(0, list, FALSE);
        }

        /* Invoke the slab layer audit callback if auditing is enabled */
        if ((cp->mc_flags & MCF_DEBUG) && cp->mc_slab_audit != NULL) {
                (*cp->mc_slab_audit)(cp->mc_private, list, FALSE);
        }

        MCACHE_LOCK(&ccp->cc_lock);
        for (;;) {
                /*
                 * If there is space in the current CPU's filled bucket, put
                 * the object there and return once all objects are freed.
                 * Note the cast to unsigned integer takes care of the case
                 * where the bucket layer is disabled (when cc_objs is -1).
                 */
                if ((unsigned int)ccp->cc_objs <
                    (unsigned int)ccp->cc_bktsize) {
                        /*
                         * Reverse the list while we place the object into the
                         * bucket; this effectively causes the most recently
                         * freed object(s) to be reused during allocation.
                         */
                        nlist = list->obj_next;
                        list->obj_next = (ccp->cc_objs == 0) ? NULL :
                            ccp->cc_filled->bkt_obj[ccp->cc_objs - 1];
                        ccp->cc_filled->bkt_obj[ccp->cc_objs++] = list;
                        ccp->cc_free++;

                        if ((list = nlist) != NULL) {
                                continue;
                        }

                        /* We are done; return to caller */
                        MCACHE_UNLOCK(&ccp->cc_lock);

                        /* If there is a waiter below, notify it */
                        if (cp->mc_waiter_cnt > 0) {
                                mcache_notify(cp, MCN_RETRYALLOC);
                        }
                        return;
                }

                /*
                 * The CPU's filled bucket is full.  If the previous filled
                 * bucket was empty, exchange and try again.
                 */
                if (ccp->cc_pobjs == 0) {
                        mcache_cpu_refill(ccp, ccp->cc_pfilled, ccp->cc_pobjs);
                        continue;
                }

                /*
                 * If the bucket layer is disabled, free to slab.  This can
                 * happen either because MCF_NOCPUCACHE is set, or because
                 * the bucket layer is currently being resized.
                 */
                if (ccp->cc_bktsize == 0) {
                        break;
                }

                /*
                 * Both of the CPU's buckets are full; try to get an empty
                 * bucket from the bucket layer.  Upon success, empty this
                 * CPU and place any full bucket into the full list.
                 */
                bkt = mcache_bkt_alloc(cp, &cp->mc_empty);
                if (bkt != NULL) {
                        if (ccp->cc_pfilled != NULL) {
                                mcache_bkt_free(cp, &cp->mc_full,
                                    ccp->cc_pfilled);
                        }
                        mcache_cpu_refill(ccp, bkt, 0);
                        continue;
                }
                btp = cp->cache_bkttype;

                /*
                 * We need an empty bucket to put our freed objects into
                 * but couldn't get an empty bucket from the bucket layer;
                 * attempt to allocate one.  We do not want to block for
                 * allocation here, and if the bucket allocation fails
                 * we will simply fall through to the slab layer.
                 */
                MCACHE_UNLOCK(&ccp->cc_lock);
                bkt = mcache_alloc(btp->bt_cache, MCR_NOSLEEP);
                MCACHE_LOCK(&ccp->cc_lock);

                if (bkt != NULL) {
                        /*
                         * We have an empty bucket, but since we drop the
                         * CPU lock above, the cache's bucket size may have
                         * changed.  If so, free the bucket and try again.
                         */
                        if (ccp->cc_bktsize != btp->bt_bktsize) {
                                MCACHE_UNLOCK(&ccp->cc_lock);
                                mcache_free(btp->bt_cache, bkt);
                                MCACHE_LOCK(&ccp->cc_lock);
                                continue;
                        }

                        /*
                         * Store it in the bucket object since we'll
                         * need to refer to it during bucket destroy;
                         * we can't safely refer to cache_bkttype as
                         * the bucket lock may not be acquired then.
                         */
                        bkt->bkt_type = btp;

                        /*
                         * We have an empty bucket of the right size;
                         * add it to the bucket layer and try again.
                         */
                        mcache_bkt_free(cp, &cp->mc_empty, bkt);
                        continue;
                }

                /*
                 * The bucket layer has no empty buckets; free the
                 * object(s) directly to the slab layer.
                 */
                break;
        }
        MCACHE_UNLOCK(&ccp->cc_lock);

        /* If there is a waiter below, notify it */
        if (cp->mc_waiter_cnt > 0) {
                mcache_notify(cp, MCN_RETRYALLOC);
        }

        /* Advise the slab layer to purge the object(s) */
        (*cp->mc_slab_free)(cp->mc_private, list,
            (cp->mc_flags & MCF_DEBUG) || cp->mc_purge_cnt);
}

/*
 * Cache destruction routine.
 */
__private_extern__ void
mcache_destroy(mcache_t *cp)
{
        void **pbuf;

        MCACHE_LIST_LOCK();
        LIST_REMOVE(cp, mc_list);
        MCACHE_LIST_UNLOCK();

        mcache_bkt_purge(cp);

        /*
         * This cache is dead; there should be no further transaction.
         * If it's still invoked, make sure that it induces a fault.
         */
        cp->mc_slab_alloc = NULL;
        cp->mc_slab_free = NULL;
        cp->mc_slab_audit = NULL;

        lck_grp_free(cp->mc_bkt_lock_grp);
        lck_grp_free(cp->mc_cpu_lock_grp);
        lck_grp_free(cp->mc_sync_lock_grp);

        /*
         * TODO: We need to destroy the zone here, but cannot do it
         * because there is no such way to achieve that.  Until then
         * the memory allocated for the zone structure is leaked.
         * Once it is achievable, uncomment these lines:
         *
         *      if (cp->mc_slab_zone != NULL) {
         *              zdestroy(cp->mc_slab_zone);
         *              cp->mc_slab_zone = NULL;
         *      }
         */

        /* Get the original address since we're about to free it */
        pbuf = (void **)((intptr_t)cp - sizeof(void *));

        zfree(mcache_zone, *pbuf);
}

/*
 * Internal slab allocator used as a backend for simple caches.  The current
 * implementation uses the zone allocator for simplicity reasons.
 */
static unsigned int
mcache_slab_alloc(void *arg, mcache_obj_t ***plist, unsigned int num,
    int wait)
{
#pragma unused(wait)
        mcache_t *cp = arg;
        unsigned int need = num;
        size_t rsize = P2ROUNDUP(cp->mc_bufsize, sizeof(u_int64_t));
        u_int32_t flags = cp->mc_flags;
        void *buf, *base, **pbuf;
        mcache_obj_t **list = *plist;

        *list = NULL;

        for (;;) {
                buf = zalloc(cp->mc_slab_zone);
                if (buf == NULL) {
                        break;
                }

                /* Get the aligned base address for this object */
                base = (void *)P2ROUNDUP((intptr_t)buf + sizeof(u_int64_t),
                    cp->mc_align);

                /*
                 * Wind back a pointer size from the aligned base and
                 * save the original address so we can free it later.
                 */
                pbuf = (void **)((intptr_t)base - sizeof(void *));
                *pbuf = buf;

                VERIFY(((intptr_t)base + cp->mc_bufsize) <=
                    ((intptr_t)buf + cp->mc_chunksize));

                /*
                 * If auditing is enabled, patternize the contents of
                 * the buffer starting from the 64-bit aligned base to
                 * the end of the buffer; the length is rounded up to
                 * the nearest 64-bit multiply; this is because we use
                 * 64-bit memory access to set/check the pattern.
                 */
                if (flags & MCF_DEBUG) {
                        VERIFY(((intptr_t)base + rsize) <=
                            ((intptr_t)buf + cp->mc_chunksize));
                        mcache_set_pattern(MCACHE_FREE_PATTERN, base, rsize);
                }

                VERIFY(IS_P2ALIGNED(base, cp->mc_align));
                *list = (mcache_obj_t *)base;

                (*list)->obj_next = NULL;
                list = *plist = &(*list)->obj_next;

                /* If we got them all, return to mcache */
                if (--need == 0) {
                        break;
                }
        }

        return num - need;
}

/*
 * Internal slab deallocator used as a backend for simple caches.
 */
static void
mcache_slab_free(void *arg, mcache_obj_t *list, __unused boolean_t purged)
{
        mcache_t *cp = arg;
        mcache_obj_t *nlist;
        size_t rsize = P2ROUNDUP(cp->mc_bufsize, sizeof(u_int64_t));
        u_int32_t flags = cp->mc_flags;
        void *base;
        void **pbuf;

        for (;;) {
                nlist = list->obj_next;
                list->obj_next = NULL;

                base = list;
                VERIFY(IS_P2ALIGNED(base, cp->mc_align));

                /* Get the original address since we're about to free it */
                pbuf = (void **)((intptr_t)base - sizeof(void *));

                VERIFY(((intptr_t)base + cp->mc_bufsize) <=
                    ((intptr_t)*pbuf + cp->mc_chunksize));

                if (flags & MCF_DEBUG) {
                        VERIFY(((intptr_t)base + rsize) <=
                            ((intptr_t)*pbuf + cp->mc_chunksize));
                        mcache_audit_free_verify(NULL, base, 0, rsize);
                }

                /* Free it to zone */
                zfree(cp->mc_slab_zone, *pbuf);

                /* No more objects to free; return to mcache */
                if ((list = nlist) == NULL) {
                        break;
                }
        }
}

/*
 * Internal slab auditor for simple caches.
 */
static void
mcache_slab_audit(void *arg, mcache_obj_t *list, boolean_t alloc)
{
        mcache_t *cp = arg;
        size_t rsize = P2ROUNDUP(cp->mc_bufsize, sizeof(u_int64_t));
        void *base, **pbuf;

        while (list != NULL) {
                mcache_obj_t *next = list->obj_next;

                base = list;
                VERIFY(IS_P2ALIGNED(base, cp->mc_align));

                /* Get the original address */
                pbuf = (void **)((intptr_t)base - sizeof(void *));

                VERIFY(((intptr_t)base + rsize) <=
                    ((intptr_t)*pbuf + cp->mc_chunksize));

                if (!alloc) {
                        mcache_set_pattern(MCACHE_FREE_PATTERN, base, rsize);
                } else {
                        mcache_audit_free_verify_set(NULL, base, 0, rsize);
                }

                list = list->obj_next = next;
        }
}

/*
 * Refill the CPU's filled bucket with bkt and save the previous one.
 */
static void
mcache_cpu_refill(mcache_cpu_t *ccp, mcache_bkt_t *bkt, int objs)
{
        ASSERT((ccp->cc_filled == NULL && ccp->cc_objs == -1) ||
            (ccp->cc_filled && ccp->cc_objs + objs == ccp->cc_bktsize));
        ASSERT(ccp->cc_bktsize > 0);

        ccp->cc_pfilled = ccp->cc_filled;
        ccp->cc_pobjs = ccp->cc_objs;
        ccp->cc_filled = bkt;
        ccp->cc_objs = objs;
}

/*
 * Allocate a bucket from the bucket layer.
 */
static mcache_bkt_t *
mcache_bkt_alloc(mcache_t *cp, mcache_bktlist_t *blp)
{
        mcache_bkt_t *bkt;

        if (!MCACHE_LOCK_TRY(&cp->mc_bkt_lock)) {
                /*
                 * The bucket layer lock is held by another CPU; increase
                 * the contention count so that we can later resize the
                 * bucket size accordingly.
                 */
                MCACHE_LOCK(&cp->mc_bkt_lock);
                cp->mc_bkt_contention++;
        }

        if ((bkt = blp->bl_list) != NULL) {
                blp->bl_list = bkt->bkt_next;
                if (--blp->bl_total < blp->bl_min) {
                        blp->bl_min = blp->bl_total;
                }
                blp->bl_alloc++;
        }

        MCACHE_UNLOCK(&cp->mc_bkt_lock);

        return bkt;
}

/*
 * Free a bucket to the bucket layer.
 */
static void
mcache_bkt_free(mcache_t *cp, mcache_bktlist_t *blp, mcache_bkt_t *bkt)
{
        MCACHE_LOCK(&cp->mc_bkt_lock);

        bkt->bkt_next = blp->bl_list;
        blp->bl_list = bkt;
        blp->bl_total++;

        MCACHE_UNLOCK(&cp->mc_bkt_lock);
}

/*
 * Enable the bucket layer of a cache.
 */
static void
mcache_cache_bkt_enable(mcache_t *cp)
{
        mcache_cpu_t *ccp;
        unsigned int cpu;

        if (cp->mc_flags & MCF_NOCPUCACHE) {
                return;
        }

        for (cpu = 0; cpu < ncpu; cpu++) {
                ccp = &cp->mc_cpu[cpu];
                MCACHE_LOCK(&ccp->cc_lock);
                ccp->cc_bktsize = cp->cache_bkttype->bt_bktsize;
                MCACHE_UNLOCK(&ccp->cc_lock);
        }
}

/*
 * Purge all buckets from a cache and disable its bucket layer.
 */
static void
mcache_bkt_purge(mcache_t *cp)
{
        mcache_cpu_t *ccp;
        mcache_bkt_t *bp, *pbp;
        int objs, pobjs;
        unsigned int cpu;

        for (cpu = 0; cpu < ncpu; cpu++) {
                ccp = &cp->mc_cpu[cpu];

                MCACHE_LOCK(&ccp->cc_lock);

                bp = ccp->cc_filled;
                pbp = ccp->cc_pfilled;
                objs = ccp->cc_objs;
                pobjs = ccp->cc_pobjs;
                ccp->cc_filled = NULL;
                ccp->cc_pfilled = NULL;
                ccp->cc_objs = -1;
                ccp->cc_pobjs = -1;
                ccp->cc_bktsize = 0;

                MCACHE_UNLOCK(&ccp->cc_lock);

                if (bp != NULL) {
                        mcache_bkt_destroy(cp, bp, objs);
                }
                if (pbp != NULL) {
                        mcache_bkt_destroy(cp, pbp, pobjs);
                }
        }

        mcache_bkt_ws_zero(cp);
        mcache_bkt_ws_reap(cp);
}

/*
 * Free one or more objects in the bucket to the slab layer,
 * and also free the bucket itself.
 */
static void
mcache_bkt_destroy(mcache_t *cp, mcache_bkt_t *bkt, int nobjs)
{
        if (nobjs > 0) {
                mcache_obj_t *top = bkt->bkt_obj[nobjs - 1];

                if (cp->mc_flags & MCF_DEBUG) {
                        mcache_obj_t *o = top;
                        int cnt = 0;

                        /*
                         * Verify that the chain of objects in the bucket is
                         * valid.  Any mismatch here means a mistake when the
                         * object(s) were freed to the CPU layer, so we panic.
                         */
                        while (o != NULL) {
                                o = o->obj_next;
                                ++cnt;
                        }
                        if (cnt != nobjs) {
                                panic("mcache_bkt_destroy: %s cp %p corrupted "
                                    "list in bkt %p (nobjs %d actual %d)\n",
                                    cp->mc_name, (void *)cp, (void *)bkt,
                                    nobjs, cnt);
                                /* NOTREACHED */
                                __builtin_unreachable();
                        }
                }

                /* Advise the slab layer to purge the object(s) */
                (*cp->mc_slab_free)(cp->mc_private, top,
                    (cp->mc_flags & MCF_DEBUG) || cp->mc_purge_cnt);
        }
        mcache_free(bkt->bkt_type->bt_cache, bkt);
}

/*
 * Update the bucket layer working set statistics.
 */
static void
mcache_bkt_ws_update(mcache_t *cp)
{
        MCACHE_LOCK(&cp->mc_bkt_lock);

        cp->mc_full.bl_reaplimit = cp->mc_full.bl_min;
        cp->mc_full.bl_min = cp->mc_full.bl_total;
        cp->mc_empty.bl_reaplimit = cp->mc_empty.bl_min;
        cp->mc_empty.bl_min = cp->mc_empty.bl_total;

        MCACHE_UNLOCK(&cp->mc_bkt_lock);
}

/*
 * Mark everything as eligible for reaping (working set is zero).
 */
static void
mcache_bkt_ws_zero(mcache_t *cp)
{
        MCACHE_LOCK(&cp->mc_bkt_lock);

        cp->mc_full.bl_reaplimit = cp->mc_full.bl_total;
        cp->mc_full.bl_min = cp->mc_full.bl_total;
        cp->mc_empty.bl_reaplimit = cp->mc_empty.bl_total;
        cp->mc_empty.bl_min = cp->mc_empty.bl_total;

        MCACHE_UNLOCK(&cp->mc_bkt_lock);
}

/*
 * Reap all buckets that are beyond the working set.
 */
static void
mcache_bkt_ws_reap(mcache_t *cp)
{
        long reap;
        mcache_bkt_t *bkt;

        reap = MIN(cp->mc_full.bl_reaplimit, cp->mc_full.bl_min);
        while (reap-- &&
            (bkt = mcache_bkt_alloc(cp, &cp->mc_full)) != NULL) {
                mcache_bkt_destroy(cp, bkt, bkt->bkt_type->bt_bktsize);
        }

        reap = MIN(cp->mc_empty.bl_reaplimit, cp->mc_empty.bl_min);
        while (reap-- &&
            (bkt = mcache_bkt_alloc(cp, &cp->mc_empty)) != NULL) {
                mcache_bkt_destroy(cp, bkt, 0);
        }
}

static void
mcache_reap_timeout(thread_call_param_t dummy __unused,
    thread_call_param_t arg)
{
        volatile UInt32 *flag = arg;

        ASSERT(flag == &mcache_reaping);

        *flag = 0;
}

static void
mcache_reap_done(void *flag)
{
        uint64_t deadline, leeway;

        clock_interval_to_deadline(mcache_reap_interval, NSEC_PER_SEC,
            &deadline);
        clock_interval_to_absolutetime_interval(mcache_reap_interval_leeway,
            NSEC_PER_SEC, &leeway);
        thread_call_enter_delayed_with_leeway(mcache_reap_tcall, flag,
            deadline, leeway, THREAD_CALL_DELAY_LEEWAY);
}

static void
mcache_reap_start(void *arg)
{
        UInt32 *flag = arg;

        ASSERT(flag == &mcache_reaping);

        mcache_applyall(mcache_cache_reap);
        mcache_dispatch(mcache_reap_done, flag);
}

__private_extern__ void
mcache_reap(void)
{
        UInt32 *flag = &mcache_reaping;

        if (mcache_llock_owner == current_thread() ||
            !OSCompareAndSwap(0, 1, flag)) {
                return;
        }

        mcache_dispatch(mcache_reap_start, flag);
}

__private_extern__ void
mcache_reap_now(mcache_t *cp, boolean_t purge)
{
        if (purge) {
                mcache_bkt_purge(cp);
                mcache_cache_bkt_enable(cp);
        } else {
                mcache_bkt_ws_zero(cp);
                mcache_bkt_ws_reap(cp);
        }
}

static void
mcache_cache_reap(mcache_t *cp)
{
        mcache_bkt_ws_reap(cp);
}

/*
 * Performs period maintenance on a cache.
 */
static void
mcache_cache_update(mcache_t *cp)
{
        int need_bkt_resize = 0;
        int need_bkt_reenable = 0;

        lck_mtx_assert(&mcache_llock, LCK_MTX_ASSERT_OWNED);

        mcache_bkt_ws_update(cp);

        /*
         * Cache resize and post-purge reenable are mutually exclusive.
         * If the cache was previously purged, there is no point of
         * increasing the bucket size as there was an indication of
         * memory pressure on the system.
         */
        lck_mtx_lock_spin(&cp->mc_sync_lock);
        if (!(cp->mc_flags & MCF_NOCPUCACHE) && cp->mc_enable_cnt) {
                need_bkt_reenable = 1;
        }
        lck_mtx_unlock(&cp->mc_sync_lock);

        MCACHE_LOCK(&cp->mc_bkt_lock);
        /*
         * If the contention count is greater than the threshold, and if
         * we are not already at the maximum bucket size, increase it.
         * Otherwise, if this cache was previously purged by the user
         * then we simply reenable it.
         */
        if ((unsigned int)cp->mc_chunksize < cp->cache_bkttype->bt_maxbuf &&
            (int)(cp->mc_bkt_contention - cp->mc_bkt_contention_prev) >
            mcache_bkt_contention && !need_bkt_reenable) {
                need_bkt_resize = 1;
        }

        cp->mc_bkt_contention_prev = cp->mc_bkt_contention;
        MCACHE_UNLOCK(&cp->mc_bkt_lock);

        if (need_bkt_resize) {
                mcache_dispatch(mcache_cache_bkt_resize, cp);
        } else if (need_bkt_reenable) {
                mcache_dispatch(mcache_cache_enable, cp);
        }
}

/*
 * Recompute a cache's bucket size.  This is an expensive operation
 * and should not be done frequently; larger buckets provide for a
 * higher transfer rate with the bucket while smaller buckets reduce
 * the memory consumption.
 */
static void
mcache_cache_bkt_resize(void *arg)
{
        mcache_t *cp = arg;
        mcache_bkttype_t *btp = cp->cache_bkttype;

        if ((unsigned int)cp->mc_chunksize < btp->bt_maxbuf) {
                mcache_bkt_purge(cp);

                /*
                 * Upgrade to the next bucket type with larger bucket size;
                 * temporarily set the previous contention snapshot to a
                 * negative number to prevent unnecessary resize request.
                 */
                MCACHE_LOCK(&cp->mc_bkt_lock);
                cp->cache_bkttype = ++btp;
                cp->mc_bkt_contention_prev = cp->mc_bkt_contention + INT_MAX;
                MCACHE_UNLOCK(&cp->mc_bkt_lock);

                mcache_cache_enable(cp);
        }
}

/*
 * Reenable a previously disabled cache due to purge.
 */
static void
mcache_cache_enable(void *arg)
{
        mcache_t *cp = arg;

        lck_mtx_lock_spin(&cp->mc_sync_lock);
        cp->mc_purge_cnt = 0;
        cp->mc_enable_cnt = 0;
        lck_mtx_unlock(&cp->mc_sync_lock);

        mcache_cache_bkt_enable(cp);
}

static void
mcache_update_timeout(__unused void *arg)
{
        uint64_t deadline, leeway;

        clock_interval_to_deadline(mcache_reap_interval, NSEC_PER_SEC,
            &deadline);
        clock_interval_to_absolutetime_interval(mcache_reap_interval_leeway,
            NSEC_PER_SEC, &leeway);
        thread_call_enter_delayed_with_leeway(mcache_update_tcall, NULL,
            deadline, leeway, THREAD_CALL_DELAY_LEEWAY);
}

static void
mcache_update(thread_call_param_t arg __unused,
    thread_call_param_t dummy __unused)
{
        mcache_applyall(mcache_cache_update);
        mcache_update_timeout(NULL);
}

static void
mcache_applyall(void (*func)(mcache_t *))
{
        mcache_t *cp;

        MCACHE_LIST_LOCK();
        LIST_FOREACH(cp, &mcache_head, mc_list) {
                func(cp);
        }
        MCACHE_LIST_UNLOCK();
}

static void
mcache_dispatch(void (*func)(void *), void *arg)
{
        ASSERT(func != NULL);
        timeout(func, arg, hz / 1000);
}

__private_extern__ void
mcache_buffer_log(mcache_audit_t *mca, void *addr, mcache_t *cp,
    struct timeval *base_ts)
{
        struct timeval now, base = { .tv_sec = 0, .tv_usec = 0 };
        void *stack[MCACHE_STACK_DEPTH + 1];
        struct mca_trn *transaction;

        transaction = &mca->mca_trns[mca->mca_next_trn];

        mca->mca_addr = addr;
        mca->mca_cache = cp;

        transaction->mca_thread = current_thread();

        bzero(stack, sizeof(stack));
        transaction->mca_depth = (uint16_t)OSBacktrace(stack, MCACHE_STACK_DEPTH + 1) - 1;
        bcopy(&stack[1], transaction->mca_stack,
            sizeof(transaction->mca_stack));

        microuptime(&now);
        if (base_ts != NULL) {
                base = *base_ts;
        }
        /* tstamp is in ms relative to base_ts */
        transaction->mca_tstamp = ((now.tv_usec - base.tv_usec) / 1000);
        if ((now.tv_sec - base.tv_sec) > 0) {
                transaction->mca_tstamp += ((now.tv_sec - base.tv_sec) * 1000);
        }

        mca->mca_next_trn =
            (mca->mca_next_trn + 1) % mca_trn_max;
}

/*
 * N.B.: mcache_set_pattern(), mcache_verify_pattern() and
 * mcache_verify_set_pattern() are marked as noinline to prevent the
 * compiler from aliasing pointers when they are inlined inside the callers
 * (e.g. mcache_audit_free_verify_set()) which would be undefined behavior.
 */
__private_extern__ OS_NOINLINE void
mcache_set_pattern(u_int64_t pattern, void *buf_arg, size_t size)
{
        u_int64_t *buf_end = (u_int64_t *)((void *)((char *)buf_arg + size));
        u_int64_t *buf = (u_int64_t *)buf_arg;

        VERIFY(IS_P2ALIGNED(buf_arg, sizeof(u_int64_t)));
        VERIFY(IS_P2ALIGNED(size, sizeof(u_int64_t)));

        while (buf < buf_end) {
                *buf++ = pattern;
        }
}

__private_extern__ OS_NOINLINE void *
mcache_verify_pattern(u_int64_t pattern, void *buf_arg, size_t size)
{
        u_int64_t *buf_end = (u_int64_t *)((void *)((char *)buf_arg + size));
        u_int64_t *buf;

        VERIFY(IS_P2ALIGNED(buf_arg, sizeof(u_int64_t)));
        VERIFY(IS_P2ALIGNED(size, sizeof(u_int64_t)));

        for (buf = buf_arg; buf < buf_end; buf++) {
                if (*buf != pattern) {
                        return buf;
                }
        }
        return NULL;
}

OS_NOINLINE static void *
mcache_verify_set_pattern(u_int64_t old, u_int64_t new, void *buf_arg,
    size_t size)
{
        u_int64_t *buf_end = (u_int64_t *)((void *)((char *)buf_arg + size));
        u_int64_t *buf;

        VERIFY(IS_P2ALIGNED(buf_arg, sizeof(u_int64_t)));
        VERIFY(IS_P2ALIGNED(size, sizeof(u_int64_t)));

        for (buf = buf_arg; buf < buf_end; buf++) {
                if (*buf != old) {
                        mcache_set_pattern(old, buf_arg,
                            (uintptr_t)buf - (uintptr_t)buf_arg);
                        return buf;
                }
                *buf = new;
        }
        return NULL;
}

__private_extern__ void
mcache_audit_free_verify(mcache_audit_t *mca, void *base, size_t offset,
    size_t size)
{
        void *addr;
        u_int64_t *oaddr64;
        mcache_obj_t *next;

        addr = (void *)((uintptr_t)base + offset);
        next = ((mcache_obj_t *)addr)->obj_next;

        /* For the "obj_next" pointer in the buffer */
        oaddr64 = (u_int64_t *)P2ROUNDDOWN(addr, sizeof(u_int64_t));
        *oaddr64 = MCACHE_FREE_PATTERN;

        if ((oaddr64 = mcache_verify_pattern(MCACHE_FREE_PATTERN,
            (caddr_t)base, size)) != NULL) {
                mcache_audit_panic(mca, addr, (caddr_t)oaddr64 - (caddr_t)base,
                    (int64_t)MCACHE_FREE_PATTERN, (int64_t)*oaddr64);
                /* NOTREACHED */
        }
        ((mcache_obj_t *)addr)->obj_next = next;
}

__private_extern__ void
mcache_audit_free_verify_set(mcache_audit_t *mca, void *base, size_t offset,
    size_t size)
{
        void *addr;
        u_int64_t *oaddr64;
        mcache_obj_t *next;

        addr = (void *)((uintptr_t)base + offset);
        next = ((mcache_obj_t *)addr)->obj_next;

        /* For the "obj_next" pointer in the buffer */
        oaddr64 = (u_int64_t *)P2ROUNDDOWN(addr, sizeof(u_int64_t));
        *oaddr64 = MCACHE_FREE_PATTERN;

        if ((oaddr64 = mcache_verify_set_pattern(MCACHE_FREE_PATTERN,
            MCACHE_UNINITIALIZED_PATTERN, (caddr_t)base, size)) != NULL) {
                mcache_audit_panic(mca, addr, (caddr_t)oaddr64 - (caddr_t)base,
                    (int64_t)MCACHE_FREE_PATTERN, (int64_t)*oaddr64);
                /* NOTREACHED */
        }
        ((mcache_obj_t *)addr)->obj_next = next;
}

#undef panic

#define DUMP_TRN_FMT() \
            "%s transaction thread %p saved PC stack (%d deep):\n" \
            "\t%p, %p, %p, %p, %p, %p, %p, %p\n" \
            "\t%p, %p, %p, %p, %p, %p, %p, %p\n"

#define DUMP_TRN_FIELDS(s, x) \
            s, \
            mca->mca_trns[x].mca_thread, mca->mca_trns[x].mca_depth, \
            mca->mca_trns[x].mca_stack[0], mca->mca_trns[x].mca_stack[1], \
            mca->mca_trns[x].mca_stack[2], mca->mca_trns[x].mca_stack[3], \
            mca->mca_trns[x].mca_stack[4], mca->mca_trns[x].mca_stack[5], \
            mca->mca_trns[x].mca_stack[6], mca->mca_trns[x].mca_stack[7], \
            mca->mca_trns[x].mca_stack[8], mca->mca_trns[x].mca_stack[9], \
            mca->mca_trns[x].mca_stack[10], mca->mca_trns[x].mca_stack[11], \
            mca->mca_trns[x].mca_stack[12], mca->mca_trns[x].mca_stack[13], \
            mca->mca_trns[x].mca_stack[14], mca->mca_trns[x].mca_stack[15]

#define MCA_TRN_LAST ((mca->mca_next_trn + mca_trn_max) % mca_trn_max)
#define MCA_TRN_PREV ((mca->mca_next_trn + mca_trn_max - 1) % mca_trn_max)

__private_extern__ char *
mcache_dump_mca(char buf[static DUMP_MCA_BUF_SIZE], mcache_audit_t *mca)
{
        snprintf(buf, DUMP_MCA_BUF_SIZE,
            "mca %p: addr %p, cache %p (%s) nxttrn %d\n"
            DUMP_TRN_FMT()
            DUMP_TRN_FMT(),

            mca, mca->mca_addr, mca->mca_cache,
            mca->mca_cache ? mca->mca_cache->mc_name : "?",
            mca->mca_next_trn,

            DUMP_TRN_FIELDS("last", MCA_TRN_LAST),
            DUMP_TRN_FIELDS("previous", MCA_TRN_PREV));

        return buf;
}

__private_extern__ void
mcache_audit_panic(mcache_audit_t *mca, void *addr, size_t offset,
    int64_t expected, int64_t got)
{
        char buf[DUMP_MCA_BUF_SIZE];

        if (mca == NULL) {
                panic("mcache_audit: buffer %p modified after free at "
                    "offset 0x%lx (0x%llx instead of 0x%llx)\n", addr,
                    offset, got, expected);
                /* NOTREACHED */
                __builtin_unreachable();
        }

        panic("mcache_audit: buffer %p modified after free at offset 0x%lx "
            "(0x%llx instead of 0x%llx)\n%s\n",
            addr, offset, got, expected, mcache_dump_mca(buf, mca));
        /* NOTREACHED */
        __builtin_unreachable();
}

__attribute__((noinline, cold, not_tail_called, noreturn))
__private_extern__ int
assfail(const char *a, const char *f, int l)
{
        panic("assertion failed: %s, file: %s, line: %d", a, f, l);
        /* NOTREACHED */
        __builtin_unreachable();
}