/*
 * Copyright (c) 2005 Jeffrey M. Hsu.  All rights reserved.
 *
 * This code is derived from software contributed to The DragonFly Project
 * by Jeffrey M. Hsu.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of The DragonFly Project nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific, prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/kernel.h>
#include <sys/systm.h>
#include <sys/callout.h>
#include <sys/globaldata.h>
#include <sys/malloc.h>
#include <sys/queue.h>
#include <sys/objcache.h>
#include <sys/spinlock.h>
#include <sys/thread.h>
#include <sys/thread2.h>
#include <sys/spinlock2.h>
#include <sys/sysctl.h>

static MALLOC_DEFINE(M_OBJCACHE, "objcache", "Object Cache");
static MALLOC_DEFINE(M_OBJMAG, "objcache mag", "Object Cache Magazine");

#define INITIAL_MAG_CAPACITY    64

struct magazine {
        int                      rounds;
        int                      capacity;
        SLIST_ENTRY(magazine)    nextmagazine;
        void                    *objects[];
};

SLIST_HEAD(magazinelist, magazine);

#define MAGAZINE_HDRSIZE        __offsetof(struct magazine, objects[0])
#define MAGAZINE_CAPACITY_MAX   4096
#define MAGAZINE_CAPACITY_MIN   4

/*
 * per-cluster cache of magazines
 *
 * All fields in this structure are protected by the spinlock.
 */
struct magazinedepot {
        /*
         * The per-cpu object caches only exchanges completely full or
         * completely empty magazines with the depot layer, so only have
         * to cache these two types of magazines.
         */
        struct magazinelist     fullmagazines;
        struct magazinelist     emptymagazines;
        int                     magcapacity;

        /* protect this structure */
        struct spinlock         spin;

        /* magazines not yet allocated towards limit */
        int                     unallocated_objects;
        int                     cluster_limit;  /* ref for adjustments */

        /* infrequently used fields */
        int                     waiting;        /* waiting for another cpu to
                                                 * return a full magazine to
                                                 * the depot */
        int                     contested;      /* depot contention count */
} __cachealign;

/*
 * per-cpu object cache
 * All fields in this structure are protected by crit_enter().
 */
struct percpu_objcache {
        struct magazine *loaded_magazine;       /* active magazine */
        struct magazine *previous_magazine;     /* backup magazine */

        /* statistics */
        u_long          gets_cumulative;        /* total calls to get */
        u_long          gets_null;              /* objcache_get returned NULL */
        u_long          allocs_cumulative;      /* total calls to alloc */
        u_long          puts_cumulative;        /* total calls to put */
        u_long          gets_exhausted;         /* # of gets hit exhaustion */
#ifdef notyet
        u_long          puts_othercluster;      /* returned to other cluster */
#endif

        /* infrequently used fields */
        int             waiting;                /* waiting for a thread on this
                                                 * cpu to return an obj to the
                                                 * per-cpu cache */
} __cachealign;

/* only until we have NUMA cluster topology information XXX */
#define MAXCLUSTERS 1
#define myclusterid 0
#define CLUSTER_OF(obj) 0

/*
 * Rarely accessed but useful bits of objcache.
 */
struct objcache_desc {
        LIST_ENTRY(objcache_desc)       next;
        struct objcache                 *objcache;
        int                             total_objects;
        int                             reserved;
        char                            name[OBJCACHE_NAMELEN];
};

/*
 * Two-level object cache consisting of NUMA cluster-level depots of
 * fully loaded or completely empty magazines and cpu-level caches of
 * individual objects.
 */
struct objcache {
        /* object constructor and destructor from blank storage */
        objcache_ctor_fn        *ctor;
        objcache_dtor_fn        *dtor;
        void                    *privdata;

        /* interface to underlying allocator */
        objcache_alloc_fn       *alloc;
        objcache_free_fn        *free;
        void                    *allocator_args;

        struct objcache_desc    *desc;

        /* NUMA-cluster level caches */
        struct magazinedepot    depot[MAXCLUSTERS];

        struct percpu_objcache  cache_percpu[]; /* per-cpu caches */
};

SYSCTL_NODE(_kern, OID_AUTO, objcache, CTLFLAG_RW, 0, "objcache");

static struct spinlock objcachelist_spin;
static LIST_HEAD(objcachelist, objcache_desc) allobjcaches;
static int magazine_capmin;
static int magazine_capmax;

static struct magazine *
mag_alloc(int capacity)
{
        struct magazine *mag;
        int size;

        size = __offsetof(struct magazine, objects[capacity]);
        KASSERT(size > 0 && (size & __VM_CACHELINE_MASK) == 0,
            ("magazine size is not multiple cache line size"));

        mag = kmalloc(size, M_OBJMAG, M_INTWAIT | M_ZERO | M_CACHEALIGN);
        mag->capacity = capacity;
        mag->rounds = 0;
        return (mag);
}

static int
mag_capacity_align(int mag_capacity)
{
        int mag_size;

        mag_size = __VM_CACHELINE_ALIGN(
            __offsetof(struct magazine, objects[mag_capacity]));
        mag_capacity = (mag_size - MAGAZINE_HDRSIZE) / sizeof(void *);

        return mag_capacity;
}

/*
 * Utility routine for objects that don't require any de-construction.
 */

static void
null_dtor(void *obj, void *privdata)
{
        /* do nothing */
}

static boolean_t
null_ctor(void *obj, void *privdata, int ocflags)
{
        return TRUE;
}

/*
 * Create an object cache.
 */
struct objcache *
objcache_create(const char *name, int cluster_limit, int nom_cache,
                objcache_ctor_fn *ctor, objcache_dtor_fn *dtor, void *privdata,
                objcache_alloc_fn *alloc, objcache_free_fn *free,
                void *allocator_args)
{
        struct objcache_desc *desc;
        struct objcache *oc;
        struct magazinedepot *depot;
        int cpuid;
        int nmagdepot;
        int mag_capacity;
        int i;

        /*
         * Allocate objcache descriptor.
         */
        desc = kmalloc(sizeof(*desc), M_OBJCACHE, M_WAITOK | M_ZERO);

        /*
         * Allocate object cache structure
         */
        oc = kmalloc(__offsetof(struct objcache, cache_percpu[ncpus]),
                     M_OBJCACHE,
                     M_WAITOK | M_ZERO | M_CACHEALIGN);
        oc->ctor = ctor ? ctor : null_ctor;
        oc->dtor = dtor ? dtor : null_dtor;
        oc->privdata = privdata;
        oc->alloc = alloc;
        oc->free = free;
        oc->allocator_args = allocator_args;

        /*
         * Link objcache and its descriptor.
         */
        oc->desc = desc;
        desc->objcache = oc;
        strlcpy(desc->name, name, sizeof(desc->name));

        /*
         * Initialize depot list(s).
         */
        depot = &oc->depot[0];

        spin_init(&depot->spin, "objcachedepot");
        SLIST_INIT(&depot->fullmagazines);
        SLIST_INIT(&depot->emptymagazines);

        /*
         * Figure out the nominal number of free objects to cache and
         * the magazine capacity.  By default we want to cache up to
         * half the cluster_limit.  If there is no cluster_limit then
         * we want to cache up to 128 objects.
         */
        if (nom_cache == 0)
                nom_cache = cluster_limit / 2;
        if (cluster_limit && nom_cache > cluster_limit)
                nom_cache = cluster_limit;
        if (nom_cache == 0)
                nom_cache = INITIAL_MAG_CAPACITY * 2;

        /*
         * Magazine capacity for 2 active magazines per cpu plus 2
         * magazines in the depot.
         */
        mag_capacity = mag_capacity_align(nom_cache / (ncpus + 1) / 2 + 1);
        if (mag_capacity > magazine_capmax)
                mag_capacity = magazine_capmax;
        else if (mag_capacity < magazine_capmin)
                mag_capacity = magazine_capmin;
        depot->magcapacity = mag_capacity;

        /*
         * The cluster_limit must be sufficient to have two magazines per
         * cpu plus at least two magazines in the depot.  However, because
         * partial magazines can stay on the cpus what we really need here
         * is to specify the number of extra magazines we allocate for the
         * depot.
         *
         * Use ~1B objects to mean 'unlimited'.  A negative unallocated
         * object count is possible due to dynamic adjustments so we can't
         * use a negative number to mean 'unlimited'.  We need some overflow
         * capacity too due to the preallocated mags.
         */
        if (cluster_limit == 0) {
                depot->unallocated_objects = OBJCACHE_UNLIMITED;
        } else {
                depot->unallocated_objects = ncpus * mag_capacity * 2 +
                                             cluster_limit;
        }

        /* Save # of total objects. */
        desc->total_objects = depot->unallocated_objects;

        /*
         * This is a dynamic adjustment aid initialized to the callers
         * expectations of the current limit.
         */
        depot->cluster_limit = cluster_limit;

        /*
         * Initialize per-cpu caches
         */
        for (cpuid = 0; cpuid < ncpus; cpuid++) {
                struct percpu_objcache *cache_percpu = &oc->cache_percpu[cpuid];

                cache_percpu->loaded_magazine = mag_alloc(mag_capacity);
                cache_percpu->previous_magazine = mag_alloc(mag_capacity);
        }

        /*
         * Compute how many empty magazines to place in the depot.  This
         * determines the retained cache size and is based on nom_cache.
         *
         * The actual cache size is larger because there are two magazines
         * for each cpu as well but those can be in any fill state so we
         * just can't count them.
         *
         * There is a minimum of two magazines in the depot.
         */
        nmagdepot = nom_cache / mag_capacity + 1;
        if (nmagdepot < 2)
                nmagdepot = 2;

        /*
         * Put empty magazines in depot
         */
        for (i = 0; i < nmagdepot; i++) {
                struct magazine *mag = mag_alloc(mag_capacity);
                SLIST_INSERT_HEAD(&depot->emptymagazines, mag, nextmagazine);
        }

        spin_lock(&objcachelist_spin);
        LIST_INSERT_HEAD(&allobjcaches, desc, next);
        spin_unlock(&objcachelist_spin);

        return (oc);
}

/*
 * Adjust the cluster limit.  This is allowed to cause unallocated_objects
 * to go negative.  Note that due to the magazine hysteresis there is a
 * limit to how much of the objcache can be reclaimed using this API to
 * reduce its size.
 */
void
objcache_set_cluster_limit(struct objcache *oc, int cluster_limit)
{
        struct magazinedepot *depot;

        depot = &oc->depot[myclusterid];
        if (depot->cluster_limit != cluster_limit) {
                int delta;

                spin_lock(&depot->spin);
                delta = cluster_limit - depot->cluster_limit;
                depot->unallocated_objects += delta;
                depot->cluster_limit = cluster_limit;
                spin_unlock(&depot->spin);
                wakeup(depot);

                oc->desc->total_objects += delta;
        }
}

struct objcache *
objcache_create_simple(malloc_type_t mtype, size_t objsize)
{
        struct objcache_malloc_args *margs;
        struct objcache *oc;

        margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
        margs->objsize = objsize;
        margs->mtype = mtype;
        oc = objcache_create(mtype->ks_shortdesc, 0, 0,
                             NULL, NULL, NULL,
                             objcache_malloc_alloc, objcache_malloc_free,
                             margs);
        return (oc);
}

struct objcache *
objcache_create_mbacked(malloc_type_t mtype, size_t objsize,
                        int cluster_limit, int nom_cache,
                        objcache_ctor_fn *ctor, objcache_dtor_fn *dtor,
                        void *privdata)
{
        struct objcache_malloc_args *margs;
        struct objcache *oc;

        margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
        margs->objsize = objsize;
        margs->mtype = mtype;
        oc = objcache_create(mtype->ks_shortdesc,
                             cluster_limit, nom_cache,
                             ctor, dtor, privdata,
                             objcache_malloc_alloc, objcache_malloc_free,
                             margs);
        return(oc);
}


#define MAGAZINE_EMPTY(mag)     (mag->rounds == 0)
#define MAGAZINE_NOTEMPTY(mag)  (mag->rounds != 0)
#define MAGAZINE_FULL(mag)      (mag->rounds == mag->capacity)

#define swap(x, y)      ({ struct magazine *t = x; x = y; y = t; })

/*
 * Get an object from the object cache.
 *
 * WARNING!  ocflags are only used when we have to go to the underlying
 * allocator, so we cannot depend on flags such as M_ZERO.
 */
void *
objcache_get(struct objcache *oc, int ocflags)
{
        struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
        struct magazine *loadedmag;
        struct magazine *emptymag;
        void *obj;
        struct magazinedepot *depot;

        KKASSERT((ocflags & M_ZERO) == 0);
        crit_enter();
        ++cpucache->gets_cumulative;

retry:
        /*
         * Loaded magazine has an object.  This is the hot path.
         * It is lock-free and uses a critical section to block
         * out interrupt handlers on the same processor.
         */
        loadedmag = cpucache->loaded_magazine;
        if (MAGAZINE_NOTEMPTY(loadedmag)) {
                obj = loadedmag->objects[--loadedmag->rounds];
                crit_exit();
                return (obj);
        }

        /* Previous magazine has an object. */
        if (MAGAZINE_NOTEMPTY(cpucache->previous_magazine)) {
                swap(cpucache->loaded_magazine, cpucache->previous_magazine);
                loadedmag = cpucache->loaded_magazine;
                obj = loadedmag->objects[--loadedmag->rounds];
                crit_exit();
                return (obj);
        }

        /*
         * Both magazines empty.  Get a full magazine from the depot and
         * move one of the empty ones to the depot.
         *
         * Obtain the depot spinlock.
         *
         * NOTE: Beyond this point, M_* flags are handled via oc->alloc()
         */
        depot = &oc->depot[myclusterid];
        spin_lock(&depot->spin);

        /*
         * Recheck the cpucache after obtaining the depot spinlock.  This
         * shouldn't be necessary now but don't take any chances.
         */
        if (MAGAZINE_NOTEMPTY(cpucache->loaded_magazine) ||
            MAGAZINE_NOTEMPTY(cpucache->previous_magazine)
        ) {
                spin_unlock(&depot->spin);
                goto retry;
        }

        /* Check if depot has a full magazine. */
        if (!SLIST_EMPTY(&depot->fullmagazines)) {
                emptymag = cpucache->previous_magazine;
                cpucache->previous_magazine = cpucache->loaded_magazine;
                cpucache->loaded_magazine = SLIST_FIRST(&depot->fullmagazines);
                SLIST_REMOVE_HEAD(&depot->fullmagazines, nextmagazine);

                /*
                 * Return emptymag to the depot.
                 */
                KKASSERT(MAGAZINE_EMPTY(emptymag));
                SLIST_INSERT_HEAD(&depot->emptymagazines,
                                  emptymag, nextmagazine);
                spin_unlock(&depot->spin);
                goto retry;
        }

        /*
         * The depot does not have any non-empty magazines.  If we have
         * not hit our object limit we can allocate a new object using
         * the back-end allocator.
         *
         * NOTE: unallocated_objects can wind up being negative due to
         *       objcache_set_cluster_limit() calls.
         */
        if (__predict_true(depot->unallocated_objects > 0)) {
                --depot->unallocated_objects;
                spin_unlock(&depot->spin);
                ++cpucache->allocs_cumulative;
                crit_exit();

                obj = oc->alloc(oc->allocator_args, ocflags);
                if (obj) {
                        if (oc->ctor(obj, oc->privdata, ocflags))
                                return (obj);
                        oc->free(obj, oc->allocator_args);
                        obj = NULL;
                }
                if (obj == NULL) {
                        spin_lock(&depot->spin);
                        ++depot->unallocated_objects;
                        spin_unlock(&depot->spin);
                        if (depot->waiting)
                                wakeup(depot);

                        crit_enter();
                        /*
                         * makes debugging easier when gets_cumulative does
                         * not include gets_null.
                         */
                        ++cpucache->gets_null;
                        --cpucache->gets_cumulative;
                        crit_exit();
                }
                return(obj);
        }
        if (__predict_false(cpucache->gets_exhausted++ == 0)) {
                kprintf("Warning: objcache(%s) exhausted on cpu%d!\n",
                    oc->desc->name, mycpuid);
        }

        /*
         * Otherwise block if allowed to.
         */
        if ((ocflags & (M_WAITOK|M_NULLOK)) == M_WAITOK) {
                ++cpucache->waiting;
                ++depot->waiting;
                ssleep(depot, &depot->spin, 0, "objcache_get", 0);
                --cpucache->waiting;
                --depot->waiting;
                spin_unlock(&depot->spin);
                goto retry;
        }

        /*
         * Otherwise fail
         */
        ++cpucache->gets_null;
        --cpucache->gets_cumulative;
        crit_exit();
        spin_unlock(&depot->spin);
        return (NULL);
}

/*
 * Wrapper for malloc allocation routines.
 */
void *
objcache_malloc_alloc(void *allocator_args, int ocflags)
{
        struct objcache_malloc_args *alloc_args = allocator_args;

        return (kmalloc(alloc_args->objsize, alloc_args->mtype,
                       ocflags & OC_MFLAGS));
}

/*
 * Wrapper for malloc allocation routines, with initial zeroing
 * (but objects are not zerod on reuse from cache).
 */
void *
objcache_malloc_alloc_zero(void *allocator_args, int ocflags)
{
        struct objcache_malloc_args *alloc_args = allocator_args;

        return (kmalloc(alloc_args->objsize, alloc_args->mtype,
                       (ocflags & OC_MFLAGS) | M_ZERO));
}


void
objcache_malloc_free(void *obj, void *allocator_args)
{
        struct objcache_malloc_args *alloc_args = allocator_args;

        kfree(obj, alloc_args->mtype);
}

/*
 * Wrapper for allocation policies that pre-allocate at initialization time
 * and don't do run-time allocation.
 */
void *
objcache_nop_alloc(void *allocator_args, int ocflags)
{
        return (NULL);
}

void
objcache_nop_free(void *obj, void *allocator_args)
{
}

/*
 * Return an object to the object cache.
 */
void
objcache_put(struct objcache *oc, void *obj)
{
        struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
        struct magazine *loadedmag;
        struct magazinedepot *depot;

        crit_enter();
        ++cpucache->puts_cumulative;

        if (CLUSTER_OF(obj) != myclusterid) {
#ifdef notyet
                /* use lazy IPI to send object to owning cluster XXX todo */
                ++cpucache->puts_othercluster;
                crit_exit();
                return;
#endif
        }

retry:
        /*
         * Free slot available in loaded magazine.  This is the hot path.
         * It is lock-free and uses a critical section to block out interrupt
         * handlers on the same processor.
         */
        loadedmag = cpucache->loaded_magazine;
        if (!MAGAZINE_FULL(loadedmag)) {
                loadedmag->objects[loadedmag->rounds++] = obj;
                if (cpucache->waiting)
                        wakeup_mycpu(&oc->depot[myclusterid]);
                crit_exit();
                return;
        }

        /*
         * Current magazine full, but previous magazine has room.  XXX
         */
        if (!MAGAZINE_FULL(cpucache->previous_magazine)) {
                swap(cpucache->loaded_magazine, cpucache->previous_magazine);
                loadedmag = cpucache->loaded_magazine;
                loadedmag->objects[loadedmag->rounds++] = obj;
                if (cpucache->waiting)
                        wakeup_mycpu(&oc->depot[myclusterid]);
                crit_exit();
                return;
        }

        /*
         * Both magazines full.  Get an empty magazine from the depot and
         * move a full loaded magazine to the depot.  Even though the
         * magazine may wind up with space available after we block on
         * the spinlock, we still cycle it through to avoid the non-optimal
         * corner-case.
         *
         * Obtain the depot spinlock.
         */
        depot = &oc->depot[myclusterid];
        spin_lock(&depot->spin);

        /*
         * If an empty magazine is available in the depot, cycle it
         * through and retry.
         */
        if (!SLIST_EMPTY(&depot->emptymagazines)) {
                loadedmag = cpucache->previous_magazine;
                cpucache->previous_magazine = cpucache->loaded_magazine;
                cpucache->loaded_magazine = SLIST_FIRST(&depot->emptymagazines);
                SLIST_REMOVE_HEAD(&depot->emptymagazines, nextmagazine);

                /*
                 * Return loadedmag to the depot.  Due to blocking it may
                 * not be entirely full and could even be empty.
                 */
                if (MAGAZINE_EMPTY(loadedmag)) {
                        SLIST_INSERT_HEAD(&depot->emptymagazines,
                                          loadedmag, nextmagazine);
                        spin_unlock(&depot->spin);
                } else {
                        SLIST_INSERT_HEAD(&depot->fullmagazines,
                                          loadedmag, nextmagazine);
                        spin_unlock(&depot->spin);
                        if (depot->waiting)
                                wakeup(depot);
                }
                goto retry;
        }

        /*
         * An empty mag is not available.  This is a corner case which can
         * occur due to cpus holding partially full magazines.  Do not try
         * to allocate a mag, just free the object.
         */
        ++depot->unallocated_objects;
        spin_unlock(&depot->spin);
        if (depot->waiting)
                wakeup(depot);
        crit_exit();
        oc->dtor(obj, oc->privdata);
        oc->free(obj, oc->allocator_args);
}

/*
 * The object is being put back into the cache, but the caller has
 * indicated that the object is not in any shape to be reused and should
 * be dtor'd immediately.
 */
void
objcache_dtor(struct objcache *oc, void *obj)
{
        struct magazinedepot *depot;

        depot = &oc->depot[myclusterid];
        spin_lock(&depot->spin);
        ++depot->unallocated_objects;
        spin_unlock(&depot->spin);
        if (depot->waiting)
                wakeup(depot);
        oc->dtor(obj, oc->privdata);
        oc->free(obj, oc->allocator_args);
}

/*
 * Deallocate all objects in a magazine and free the magazine if requested.
 * When freeit is TRUE the magazine must already be disassociated from the
 * depot.
 *
 * Must be called with a critical section held when called with a per-cpu
 * magazine.  The magazine may be indirectly modified during the loop.
 *
 * If the magazine moves during a dtor the operation is aborted.  This is
 * only allowed when freeit is FALSE.
 *
 * The number of objects freed is returned.
 */
static int
mag_purge(struct objcache *oc, struct magazine **magp, int freeit)
{
        struct magazine *mag = *magp;
        int count;
        void *obj;

        count = 0;
        while (mag->rounds) {
                obj = mag->objects[--mag->rounds];
                oc->dtor(obj, oc->privdata);            /* MAY BLOCK */
                oc->free(obj, oc->allocator_args);      /* MAY BLOCK */
                ++count;

                /*
                 * Cycle for interrupts.
                 */
                if ((count & 15) == 0) {
                        crit_exit();
                        crit_enter();
                }

                /*
                 * mag may have become invalid either due to dtor/free
                 * blocking or interrupt cycling, do not derefernce it
                 * until we check.
                 */
                if (*magp != mag) {
                        kprintf("mag_purge: mag ripped out\n");
                        break;
                }
        }
        if (freeit) {
                KKASSERT(*magp == mag);
                *magp = NULL;
                kfree(mag, M_OBJMAG);
        }
        return(count);
}

/*
 * Disassociate zero or more magazines from a magazine list associated with
 * the depot, update the depot, and move the magazines to a temporary
 * list.
 *
 * The caller must check the depot for waiters and wake it up, typically
 * after disposing of the magazines this function loads onto the temporary
 * list.
 */
static void
maglist_disassociate(struct magazinedepot *depot, struct magazinelist *maglist,
                     struct magazinelist *tmplist, boolean_t purgeall)
{
        struct magazine *mag;

        while ((mag = SLIST_FIRST(maglist)) != NULL) {
                SLIST_REMOVE_HEAD(maglist, nextmagazine);
                SLIST_INSERT_HEAD(tmplist, mag, nextmagazine);
                depot->unallocated_objects += mag->rounds;
        }
}

/*
 * Deallocate all magazines and their contents from the passed temporary
 * list.  The magazines have already been accounted for by their depots.
 *
 * The total number of rounds freed is returned.  This number is typically
 * only used to determine whether a wakeup on the depot is needed or not.
 */
static int
maglist_purge(struct objcache *oc, struct magazinelist *maglist)
{
        struct magazine *mag;
        int count = 0;

        /*
         * can't use SLIST_FOREACH because blocking releases the depot
         * spinlock
         */
        crit_enter();
        while ((mag = SLIST_FIRST(maglist)) != NULL) {
                SLIST_REMOVE_HEAD(maglist, nextmagazine);
                count += mag_purge(oc, &mag, TRUE);
        }
        crit_exit();
        return(count);
}

/*
 * De-allocates all magazines on the full and empty magazine lists.
 *
 * Because this routine is called with a spinlock held, the magazines
 * can only be disassociated and moved to a temporary list, not freed.
 *
 * The caller is responsible for freeing the magazines.
 */
static void
depot_disassociate(struct magazinedepot *depot, struct magazinelist *tmplist)
{
        maglist_disassociate(depot, &depot->fullmagazines, tmplist, TRUE);
        maglist_disassociate(depot, &depot->emptymagazines, tmplist, TRUE);
}

/*
 * Try to free up some memory.  Return as soon as some free memory is found.
 * For each object cache on the reclaim list, first try the current per-cpu
 * cache, then the full magazine depot.
 */
boolean_t
objcache_reclaimlist(struct objcache *oclist[], int nlist)
{
        struct objcache *oc;
        struct percpu_objcache *cpucache;
        struct magazinedepot *depot;
        struct magazinelist tmplist;
        int i, count;

        SLIST_INIT(&tmplist);

        for (i = 0; i < nlist; i++) {
                oc = oclist[i];
                cpucache = &oc->cache_percpu[mycpuid];
                depot = &oc->depot[myclusterid];

                crit_enter();
                count = mag_purge(oc, &cpucache->loaded_magazine, FALSE);
                if (count == 0)
                        count += mag_purge(oc, &cpucache->previous_magazine, FALSE);
                crit_exit();
                if (count > 0) {
                        spin_lock(&depot->spin);
                        depot->unallocated_objects += count;
                        spin_unlock(&depot->spin);
                        if (depot->waiting)
                                wakeup(depot);
                        return (TRUE);
                }
                spin_lock(&depot->spin);
                maglist_disassociate(depot, &depot->fullmagazines,
                                     &tmplist, FALSE);
                spin_unlock(&depot->spin);
                count = maglist_purge(oc, &tmplist);
                if (count > 0) {
                        if (depot->waiting)
                                wakeup(depot);
                        return (TRUE);
                }
        }
        return (FALSE);
}

/*
 * Destroy an object cache.  Must have no existing references.
 */
void
objcache_destroy(struct objcache *oc)
{
        struct objcache_desc *desc = oc->desc;
        struct percpu_objcache *cache_percpu;
        struct magazinedepot *depot;
        int clusterid, cpuid;
        struct magazinelist tmplist;

        spin_lock(&objcachelist_spin);
        LIST_REMOVE(desc, next);
        spin_unlock(&objcachelist_spin);

        SLIST_INIT(&tmplist);
        for (clusterid = 0; clusterid < MAXCLUSTERS; clusterid++) {
                depot = &oc->depot[clusterid];
                spin_lock(&depot->spin);
                depot_disassociate(depot, &tmplist);
                spin_unlock(&depot->spin);
        }
        maglist_purge(oc, &tmplist);

        for (cpuid = 0; cpuid < ncpus; cpuid++) {
                cache_percpu = &oc->cache_percpu[cpuid];

                crit_enter();
                mag_purge(oc, &cache_percpu->loaded_magazine, TRUE);
                mag_purge(oc, &cache_percpu->previous_magazine, TRUE);
                crit_exit();
                cache_percpu->loaded_magazine = NULL;
                cache_percpu->previous_magazine = NULL;
                /* don't bother adjusting depot->unallocated_objects */
        }

        kfree(desc, M_OBJCACHE);
        kfree(oc, M_OBJCACHE);
}

static int
sysctl_ocstats(SYSCTL_HANDLER_ARGS)
{
        struct objcache_stats stat;
        struct objcache_desc marker, *desc;
        int error;

        memset(&marker, 0, sizeof(marker));

        spin_lock(&objcachelist_spin);

        LIST_INSERT_HEAD(&allobjcaches, &marker, next);
        while ((desc = LIST_NEXT(&marker, next)) != NULL) {
                u_long puts, unalloc;
                int cpu;

                LIST_REMOVE(&marker, next);
                LIST_INSERT_AFTER(desc, &marker, next);

                if (desc->total_objects == 0) {
                        /* Marker inserted by another thread. */
                        continue;
                }

                memset(&stat, 0, sizeof(stat));
                strlcpy(stat.oc_name, desc->name, sizeof(stat.oc_name));
                stat.oc_limit = desc->total_objects;
                /* XXX domain aware */
                unalloc = desc->objcache->depot[0].unallocated_objects;

                puts = 0;
                for (cpu = 0; cpu < ncpus; ++cpu) {
                        const struct percpu_objcache *cache;

                        cache = &desc->objcache->cache_percpu[cpu];
                        puts += cache->puts_cumulative;

                        stat.oc_requested += cache->gets_cumulative;
                        stat.oc_exhausted += cache->gets_exhausted;
                        stat.oc_failed += cache->gets_null;
                        stat.oc_allocated += cache->allocs_cumulative;
                }
                spin_unlock(&objcachelist_spin);

                /*
                 * Apply fixup.
                 */
                if (stat.oc_requested > puts)
                        stat.oc_used = stat.oc_requested - puts;
                if (stat.oc_limit > unalloc + stat.oc_used) {
                        stat.oc_cached = stat.oc_limit -
                            (unalloc + stat.oc_used);
                }
                stat.oc_requested += stat.oc_failed;

                /* Send out. */
                error = SYSCTL_OUT(req, &stat, sizeof(stat));

                /* Hold the lock before we return. */
                spin_lock(&objcachelist_spin);

                if (error)
                        break;
        }
        LIST_REMOVE(&marker, next);

        spin_unlock(&objcachelist_spin);

        return error;
}
SYSCTL_PROC(_kern_objcache, OID_AUTO, stats, (CTLTYPE_OPAQUE | CTLFLAG_RD),
    0, 0, sysctl_ocstats, "S,objcache_stats", "objcache statistics");

static void
objcache_init(void)
{
        spin_init(&objcachelist_spin, "objcachelist");

        magazine_capmin = mag_capacity_align(MAGAZINE_CAPACITY_MIN);
        magazine_capmax = mag_capacity_align(MAGAZINE_CAPACITY_MAX);
        if (bootverbose) {
                kprintf("objcache: magazine cap [%d, %d]\n",
                    magazine_capmin, magazine_capmax);
        }
#if 0
        callout_init_mp(&objcache_callout);
        objcache_rebalance_period = 60 * hz;
        callout_reset(&objcache_callout, objcache_rebalance_period,
                      objcache_timer, NULL);
#endif
}
SYSINIT(objcache, SI_BOOT2_OBJCACHE, SI_ORDER_FIRST, objcache_init, 0);