WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/mm/slab.c


/*
 * Copyright (C) 2006 Ondrej Palkovsky
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
 */
 
/*
 * The SLAB allocator is closely modelled after Opensolaris SLAB allocator
 * http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
 *
 * with the following exceptions:
 *   - empty SLABS are deallocated immediately
 *     (in Linux they are kept in linked list, in Solaris ???)
 *   - empty magazines are deallocated when not needed
 *     (in Solaris they are held in linked list in slab cache)
 *
 *   Following features are not currently supported but would be easy to do:
 *   - cache coloring
 *   - dynamic magazine growing (different magazine sizes are already
 *     supported, but we would need to adjust allocating strategy)
 *
 * The SLAB allocator supports per-CPU caches ('magazines') to facilitate
 * good SMP scaling.
 *
 * When a new object is being allocated, it is first checked, if it is
 * available in CPU-bound magazine. If it is not found there, it is
 * allocated from CPU-shared SLAB - if partial full is found, it is used,
 * otherwise a new one is allocated.
 *
 * When an object is being deallocated, it is put to CPU-bound magazine.
 * If there is no such magazine, new one is allocated (if it fails,
 * the object is deallocated into SLAB). If the magazine is full, it is
 * put into cpu-shared list of magazines and new one is allocated.
 *
 * The CPU-bound magazine is actually a pair of magazine to avoid
 * thrashing when somebody is allocating/deallocating 1 item at the magazine
 * size boundary. LIFO order is enforced, which should avoid fragmentation
 * as much as possible.
 *  
 * Every cache contains list of full slabs and list of partialy full slabs.
 * Empty SLABS are immediately freed (thrashing will be avoided because
 * of magazines).
 *
 * The SLAB information structure is kept inside the data area, if possible.
 * The cache can be marked that it should not use magazines. This is used
 * only for SLAB related caches to avoid deadlocks and infinite recursion
 * (the SLAB allocator uses itself for allocating all it's control structures).
 *
 * The SLAB allocator allocates lot of space and does not free it. When
 * frame allocator fails to allocate the frame, it calls slab_reclaim().
 * It tries 'light reclaim' first, then brutal reclaim. The light reclaim
 * releases slabs from cpu-shared magazine-list, until at least 1 slab
 * is deallocated in each cache (this algorithm should probably change).
 * The brutal reclaim removes all cached objects, even from CPU-bound
 * magazines.
 *
 * TODO: For better CPU-scaling the magazine allocation strategy should
 * be extended. Currently, if the cache does not have magazine, it asks
 * for non-cpu cached magazine cache to provide one. It might be feasible
 * to add cpu-cached magazine cache (which would allocate it's magazines
 * from non-cpu-cached mag. cache). This would provide a nice per-cpu
 * buffer. The other possibility is to use the per-cache
 * 'empty-magazine-list', which decreases competing for 1 per-system
 * magazine cache.
 *
 * - it might be good to add granularity of locks even to slab level,
 *   we could then try_spinlock over all partial slabs and thus improve
 *   scalability even on slab level
 */
 
 
#include <synch/spinlock.h>
#include <mm/slab.h>
#include <list.h>
#include <memstr.h>
#include <align.h>
#include <mm/heap.h>
#include <mm/frame.h>
#include <config.h>
#include <print.h>
#include <arch.h>
#include <panic.h>
#include <debug.h>
#include <bitops.h>
 
SPINLOCK_INITIALIZE(slab_cache_lock);
static LIST_INITIALIZE(slab_cache_list);
 
/** Magazine cache */
static slab_cache_t mag_cache;
/** Cache for cache descriptors */
static slab_cache_t slab_cache_cache;
 
/** Cache for external slab descriptors
 * This time we want per-cpu cache, so do not make it static
 * - using SLAB for internal SLAB structures will not deadlock,
 *   as all slab structures are 'small' - control structures of
 *   their caches do not require further allocation
 */
static slab_cache_t *slab_extern_cache;
/** Caches for malloc */
static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1];
char *malloc_names[] =  {
    "malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",
    "malloc-256","malloc-512","malloc-1K","malloc-2K",
    "malloc-4K","malloc-8K","malloc-16K","malloc-32K",
    "malloc-64K","malloc-128K"
};
 
/** Slab descriptor */
typedef struct {
    slab_cache_t *cache; /**< Pointer to parent cache */
    link_t link;       /* List of full/partial slabs */
    void *start;       /**< Start address of first available item */
    count_t available; /**< Count of available items in this slab */
    index_t nextavail; /**< The index of next available item */
}slab_t;
 
/**************************************/
/* SLAB allocation functions          */
 
/**
 * Allocate frames for slab space and initialize
 *
 */
static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)
{
    void *data;
    slab_t *slab;
    size_t fsize;
    int i;
    zone_t *zone = NULL;
    int status;
    frame_t *frame;
 
    data = (void *)frame_alloc(FRAME_KA | flags, cache->order, &status, &zone);
    if (status != FRAME_OK) {
        return NULL;
    }
    if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
        slab = slab_alloc(slab_extern_cache, flags);
        if (!slab) {
            frame_free((__address)data);
            return NULL;
        }
    } else {
        fsize = (PAGE_SIZE << cache->order);
        slab = data + fsize - sizeof(*slab);
    }
       
    /* Fill in slab structures */
    /* TODO: some better way of accessing the frame */
    for (i=0; i < (1 << cache->order); i++) {
        frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));
        frame->parent = slab;
    }
 
    slab->start = data;
    slab->available = cache->objects;
    slab->nextavail = 0;
    slab->cache = cache;
 
    for (i=0; i<cache->objects;i++)
        *((int *) (slab->start + i*cache->size)) = i+1;
 
    atomic_inc(&cache->allocated_slabs);
    return slab;
}
 
/**
 * Deallocate space associated with SLAB
 *
 * @return number of freed frames
 */
static count_t slab_space_free(slab_cache_t *cache, slab_t *slab)
{
    frame_free((__address)slab->start);
    if (! (cache->flags & SLAB_CACHE_SLINSIDE))
        slab_free(slab_extern_cache, slab);
 
    atomic_dec(&cache->allocated_slabs);
   
    return 1 << cache->order;
}
 
/** Map object to slab structure */
static slab_t * obj2slab(void *obj)
{
    frame_t *frame;
 
    frame = frame_addr2frame((__address)obj);
    return (slab_t *)frame->parent;
}
 
/**************************************/
/* SLAB functions */
 
 
/**
 * Return object to slab and call a destructor
 *
 * @param slab If the caller knows directly slab of the object, otherwise NULL
 *
 * @return Number of freed pages
 */
static count_t slab_obj_destroy(slab_cache_t *cache, void *obj,
                slab_t *slab)
{
    count_t frames = 0;
 
    if (!slab)
        slab = obj2slab(obj);
 
    ASSERT(slab->cache == cache);
    ASSERT(slab->available < cache->objects);
 
    spinlock_lock(&cache->slablock);
 
    *((int *)obj) = slab->nextavail;
    slab->nextavail = (obj - slab->start)/cache->size;
    slab->available++;
 
    /* Move it to correct list */
    if (slab->available == cache->objects) {
        /* Free associated memory */
        list_remove(&slab->link);
        /* This should not produce deadlock, as
         * magazine is always allocated with NO reclaim,
         * keep all locks */
        frames = slab_space_free(cache, slab);
    } else if (slab->available == 1) {
        /* It was in full, move to partial */
        list_remove(&slab->link);
        list_prepend(&slab->link, &cache->partial_slabs);
    }
 
    spinlock_unlock(&cache->slablock);
 
    return frames;
}
 
/**
 * Take new object from slab or create new if needed
 *
 * @return Object address or null
 */
static void * slab_obj_create(slab_cache_t *cache, int flags)
{
    slab_t *slab;
    void *obj;
 
    spinlock_lock(&cache->slablock);
 
    if (list_empty(&cache->partial_slabs)) {
        /* Allow recursion and reclaiming
         * - this should work, as the SLAB control structures
         *   are small and do not need to allocte with anything
         *   other ten frame_alloc when they are allocating,
         *   that's why we should get recursion at most 1-level deep
         */
        spinlock_unlock(&cache->slablock);
        slab = slab_space_alloc(cache, flags);
        if (!slab)
            return NULL;
        spinlock_lock(&cache->slablock);
    } else {
        slab = list_get_instance(cache->partial_slabs.next,
                     slab_t,
                     link);
        list_remove(&slab->link);
    }
    obj = slab->start + slab->nextavail * cache->size;
    slab->nextavail = *((int *)obj);
    slab->available--;
    if (! slab->available)
        list_prepend(&slab->link, &cache->full_slabs);
    else
        list_prepend(&slab->link, &cache->partial_slabs);
 
    spinlock_unlock(&cache->slablock);
    return obj;
}
 
/**************************************/
/* CPU-Cache slab functions */
 
/**
 * Finds a full magazine in cache, takes it from list
 * and returns it
 *
 * @param first If true, return first, else last mag
 */
static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache,
                        int first)
{
    slab_magazine_t *mag = NULL;
    link_t *cur;
 
    spinlock_lock(&cache->maglock);
    if (!list_empty(&cache->magazines)) {
        if (first)
            cur = cache->magazines.next;
        else
            cur = cache->magazines.prev;
        mag = list_get_instance(cur, slab_magazine_t, link);
        list_remove(&mag->link);
        atomic_dec(&cache->magazine_counter);
    }
    spinlock_unlock(&cache->maglock);
    return mag;
}
 
/** Prepend magazine to magazine list in cache */
static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag)
{
    spinlock_lock(&cache->maglock);
 
    list_prepend(&mag->link, &cache->magazines);
    atomic_inc(&cache->magazine_counter);
   
    spinlock_unlock(&cache->maglock);
}
 
/**
 * Free all objects in magazine and free memory associated with magazine
 *
 * @return Number of freed pages
 */
static count_t magazine_destroy(slab_cache_t *cache,
                slab_magazine_t *mag)
{
    int i;
    count_t frames = 0;
 
    for (i=0;i < mag->busy; i++) {
        frames += slab_obj_destroy(cache, mag->objs[i], NULL);
        atomic_dec(&cache->cached_objs);
    }
   
    slab_free(&mag_cache, mag);
 
    return frames;
}
 
/**
 * Find full magazine, set it as current and return it
 *
 * Assume cpu_magazine lock is held
 */
static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
{
    slab_magazine_t *cmag, *lastmag, *newmag;
 
    cmag = cache->mag_cache[CPU->id].current;
    lastmag = cache->mag_cache[CPU->id].last;
    if (cmag) { /* First try local CPU magazines */
        if (cmag->busy)
            return cmag;
 
        if (lastmag && lastmag->busy) {
            cache->mag_cache[CPU->id].current = lastmag;
            cache->mag_cache[CPU->id].last = cmag;
            return lastmag;
        }
    }
    /* Local magazines are empty, import one from magazine list */
    newmag = get_mag_from_cache(cache, 1);
    if (!newmag)
 
        return NULL;
 
 
 
 
 
 
 
    if (lastmag)
        magazine_destroy(cache, lastmag);
 
    cache->mag_cache[CPU->id].last = cmag;
    cache->mag_cache[CPU->id].current = newmag;
    return newmag;
}
 
/**
 * Try to find object in CPU-cache magazines
 *
 * @return Pointer to object or NULL if not available
 */
static void * magazine_obj_get(slab_cache_t *cache)
{
    slab_magazine_t *mag;
    void *obj;
 
    if (!CPU)
        return NULL;
 
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
 
    mag = get_full_current_mag(cache);
    if (!mag) {
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
        return NULL;
    }
    obj = mag->objs[--mag->busy];
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
    atomic_dec(&cache->cached_objs);
   
    return obj;
}
 
/**
 * Assure that the current magazine is empty, return pointer to it, or NULL if
 * no empty magazine is available and cannot be allocated
 *
 * Assume mag_cache[CPU->id].lock is held
 *
 * We have 2 magazines bound to processor.
 * First try the current.
 *  If full, try the last.
 *   If full, put to magazines list.
 *   allocate new, exchange last & current
 *
 */
static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
{
    slab_magazine_t *cmag,*lastmag,*newmag;
 
    cmag = cache->mag_cache[CPU->id].current;
    lastmag = cache->mag_cache[CPU->id].last;
 
    if (cmag) {
        if (cmag->busy < cmag->size)
            return cmag;
        if (lastmag && lastmag->busy < lastmag->size) {
            cache->mag_cache[CPU->id].last = cmag;
            cache->mag_cache[CPU->id].current = lastmag;
            return lastmag;
        }
    }
    /* current | last are full | nonexistent, allocate new */
    /* We do not want to sleep just because of caching */
    /* Especially we do not want reclaiming to start, as
     * this would deadlock */
    newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM);
    if (!newmag)
        return NULL;
    newmag->size = SLAB_MAG_SIZE;
    newmag->busy = 0;
 
    /* Flush last to magazine list */
    if (lastmag)
        put_mag_to_cache(cache, lastmag);
 
 
 
    /* Move current as last, save new as current */
    cache->mag_cache[CPU->id].last = cmag; 
    cache->mag_cache[CPU->id].current = newmag;
 
    return newmag;
}
 
/**
 * Put object into CPU-cache magazine
 *
 * @return 0 - success, -1 - could not get memory
 */
static int magazine_obj_put(slab_cache_t *cache, void *obj)
{
    slab_magazine_t *mag;
 
    if (!CPU)
        return -1;
 
    spinlock_lock(&cache->mag_cache[CPU->id].lock);
 
    mag = make_empty_current_mag(cache);
    if (!mag) {
        spinlock_unlock(&cache->mag_cache[CPU->id].lock);
        return -1;
    }
   
    mag->objs[mag->busy++] = obj;
 
    spinlock_unlock(&cache->mag_cache[CPU->id].lock);
    atomic_inc(&cache->cached_objs);
    return 0;
}
 
 
/**************************************/
/* SLAB CACHE functions */
 
/** Return number of objects that fit in certain cache size */
static int comp_objects(slab_cache_t *cache)
{
    if (cache->flags & SLAB_CACHE_SLINSIDE)
        return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;
    else
        return (PAGE_SIZE << cache->order) / cache->size;
}
 
/** Return wasted space in slab */
static int badness(slab_cache_t *cache)
{
    int objects;
    int ssize;
 
    objects = comp_objects(cache);
    ssize = PAGE_SIZE << cache->order;
    if (cache->flags & SLAB_CACHE_SLINSIDE)
        ssize -= sizeof(slab_t);
    return ssize - objects*cache->size;
}
 
/** Initialize allocated memory as a slab cache */
static void
_slab_cache_create(slab_cache_t *cache,
           char *name,
           size_t size,
           size_t align,
           int (*constructor)(void *obj, int kmflag),
           void (*destructor)(void *obj),
           int flags)
{
    int i;
    int pages;
 
    memsetb((__address)cache, sizeof(*cache), 0);
    cache->name = name;
 
    if (align < sizeof(__native))
        align = sizeof(__native);
    size = ALIGN_UP(size, align);
       
    cache->size = size;
 
    cache->constructor = constructor;
    cache->destructor = destructor;
    cache->flags = flags;
 
    list_initialize(&cache->full_slabs);
    list_initialize(&cache->partial_slabs);
    list_initialize(&cache->magazines);
    spinlock_initialize(&cache->slablock, "slab_lock");
    spinlock_initialize(&cache->maglock, "slab_maglock");
    if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) {
        for (i=0; i < config.cpu_count; i++) {
            memsetb((__address)&cache->mag_cache[i],
                sizeof(cache->mag_cache[i]), 0);
            spinlock_initialize(&cache->mag_cache[i].lock,
                        "slab_maglock_cpu");
        }
    }
 
    /* Compute slab sizes, object counts in slabs etc. */
    if (cache->size < SLAB_INSIDE_SIZE)
        cache->flags |= SLAB_CACHE_SLINSIDE;
 
    /* Minimum slab order */
    pages = ((cache->size-1) >> PAGE_WIDTH) + 1;
    cache->order = fnzb(pages);
 
    while (badness(cache) > SLAB_MAX_BADNESS(cache)) {
        cache->order += 1;
    }
    cache->objects = comp_objects(cache);
    /* If info fits in, put it inside */
    if (badness(cache) > sizeof(slab_t))
        cache->flags |= SLAB_CACHE_SLINSIDE;
 
    spinlock_lock(&slab_cache_lock);
 
    list_append(&cache->link, &slab_cache_list);
 
    spinlock_unlock(&slab_cache_lock);
}
 
/** Create slab cache  */
slab_cache_t * slab_cache_create(char *name,
                 size_t size,
                 size_t align,
                 int (*constructor)(void *obj, int kmflag),
                 void (*destructor)(void *obj),
                 int flags)
{
    slab_cache_t *cache;
 
    cache = slab_alloc(&slab_cache_cache, 0);
    _slab_cache_create(cache, name, size, align, constructor, destructor,
               flags);
    return cache;
}
 
/**
 * Reclaim space occupied by objects that are already free
 *
 * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing
 * @return Number of freed pages
 */
static count_t _slab_reclaim(slab_cache_t *cache, int flags)
{
    int i;
    slab_magazine_t *mag;
 
    count_t frames = 0;
    int magcount;
   
    if (cache->flags & SLAB_CACHE_NOMAGAZINE)
        return 0; /* Nothing to do */
 
    /* We count up to original magazine count to avoid
     * endless loop
     */
    magcount = atomic_get(&cache->magazine_counter);
    while (magcount-- && (mag=get_mag_from_cache(cache,0))) {
        frames += magazine_destroy(cache,mag);
        if (!(flags & SLAB_RECLAIM_ALL) && frames)
            break;
    }
 
   
    if (flags & SLAB_RECLAIM_ALL) {
        /* Free cpu-bound magazines */
        /* Destroy CPU magazines */
        for (i=0; i<config.cpu_count; i++) {
            spinlock_lock(&cache->mag_cache[i].lock);
 
            mag = cache->mag_cache[i].current;
            if (mag)
                frames += magazine_destroy(cache, mag);
            cache->mag_cache[i].current = NULL;
           
            mag = cache->mag_cache[i].last;
            if (mag)
                frames += magazine_destroy(cache, mag);
            cache->mag_cache[i].last = NULL;
 
 
 
 
 
            spinlock_unlock(&cache->mag_cache[i].lock);
        }
    }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    return frames;
}
 
/** Check that there are no slabs and remove cache from system  */
void slab_cache_destroy(slab_cache_t *cache)
{
    ipl_t ipl;
 
    /* First remove cache from link, so that we don't need
     * to disable interrupts later
     */
 
    ipl = interrupts_disable();
    spinlock_lock(&slab_cache_lock);
 
    list_remove(&cache->link);
 
    spinlock_unlock(&slab_cache_lock);
    interrupts_restore(ipl);
 
    /* Do not lock anything, we assume the software is correct and
     * does not touch the cache when it decides to destroy it */
   
    /* Destroy all magazines */
    _slab_reclaim(cache, SLAB_RECLAIM_ALL);
 
    /* All slabs must be empty */
    if (!list_empty(&cache->full_slabs) \
        || !list_empty(&cache->partial_slabs))
        panic("Destroying cache that is not empty.");
 
 
 
 
 
    slab_free(&slab_cache_cache, cache);
}
 
/** Allocate new object from cache - if no flags given, always returns
    memory */
void * slab_alloc(slab_cache_t *cache, int flags)
{
    ipl_t ipl;
    void *result = NULL;
   
    /* Disable interrupts to avoid deadlocks with interrupt handlers */
    ipl = interrupts_disable();
 
    if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
        result = magazine_obj_get(cache);
 
    if (!result)
        result = slab_obj_create(cache, flags);
 
    interrupts_restore(ipl);
 
    if (result)
        atomic_inc(&cache->allocated_objs);
 
    return result;
}
 
/** Return object to cache, use slab if known  */
static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab)
{
    ipl_t ipl;
 
    ipl = interrupts_disable();
 
    if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \
        || magazine_obj_put(cache, obj)) {
 
        slab_obj_destroy(cache, obj, slab);
 
    }
    interrupts_restore(ipl);
    atomic_dec(&cache->allocated_objs);
}
 
/** Return slab object to cache */
void slab_free(slab_cache_t *cache, void *obj)
{
    _slab_free(cache,obj,NULL);
}
 
/* Go through all caches and reclaim what is possible */
count_t slab_reclaim(int flags)
{
    slab_cache_t *cache;
    link_t *cur;
    count_t frames = 0;
 
    spinlock_lock(&slab_cache_lock);
 
    /* TODO: Add assert, that interrupts are disabled, otherwise
     * memory allocation from interrupts can deadlock.
     * - cache_destroy can call this with interrupts enabled :-/
     */
 
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
        cache = list_get_instance(cur, slab_cache_t, link);
        frames += _slab_reclaim(cache, flags);
    }
 
    spinlock_unlock(&slab_cache_lock);
 
    return frames;
}
 
 
/* Print list of slabs */
void slab_print_list(void)
{
    slab_cache_t *cache;
    link_t *cur;
 
    spinlock_lock(&slab_cache_lock);
    printf("SLAB name\tOsize\tPages\tObj/pg\tSlabs\tCached\tAllocobjs\tCtl\n");
    for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) {
        cache = list_get_instance(cur, slab_cache_t, link);
        printf("%s\t%d\t%d\t%d\t%d\t%d\t%d\t\t%s\n", cache->name, cache->size,
               (1 << cache->order), cache->objects,
               atomic_get(&cache->allocated_slabs),
               atomic_get(&cache->cached_objs),
               atomic_get(&cache->allocated_objs),
               cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out");
    }
    spinlock_unlock(&slab_cache_lock);
}
 
#ifdef CONFIG_DEBUG
static int _slab_initialized = 0;
#endif
 
void slab_cache_init(void)
{
    int i, size;
 
    /* Initialize magazine cache */
    _slab_cache_create(&mag_cache,
               "slab_magazine",
               sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*),
               sizeof(__address),
               NULL, NULL,
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
    /* Initialize slab_cache cache */
    _slab_cache_create(&slab_cache_cache,
               "slab_cache",
               sizeof(slab_cache_cache) + config.cpu_count*sizeof(slab_cache_cache.mag_cache[0]),
               sizeof(__address),
               NULL, NULL,
               SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
    /* Initialize external slab cache */
    slab_extern_cache = slab_cache_create("slab_extern",
                          sizeof(slab_t),
                          0, NULL, NULL,
                          SLAB_CACHE_SLINSIDE);
 
    /* Initialize structures for malloc */
    for (i=0, size=(1<<SLAB_MIN_MALLOC_W);
         i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1);
         i++, size <<= 1) {
        malloc_caches[i] = slab_cache_create(malloc_names[i],
                             size, 0,
                             NULL,NULL,0);
    }
#ifdef CONFIG_DEBUG       
    _slab_initialized = 1;
#endif
}
 
/**************************************/
/* kalloc/kfree functions             */
void * kalloc(unsigned int size, int flags)
{
    int idx;
 
    ASSERT(_slab_initialized);
    ASSERT( size && size <= (1 << SLAB_MAX_MALLOC_W));
   
    if (size < (1 << SLAB_MIN_MALLOC_W))
        size = (1 << SLAB_MIN_MALLOC_W);
 
    idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1;
 
    return slab_alloc(malloc_caches[idx], flags);
}
 
 
void kfree(void *obj)
{
    slab_t *slab;
 
    if (!obj) return;
 
    slab = obj2slab(obj);
    _slab_free(slab->cache, obj, slab);
}
 

Rev 780	Rev 781
1	/*	1	/*
2	* Copyright (C) 2006 Ondrej Palkovsky	2	* Copyright (C) 2006 Ondrej Palkovsky
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/*	29	/*
30	* The SLAB allocator is closely modelled after Opensolaris SLAB allocator	30	* The SLAB allocator is closely modelled after Opensolaris SLAB allocator
31	* http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/	31	* http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
32	*	32	*
33	* with the following exceptions:	33	* with the following exceptions:
34	* - empty SLABS are deallocated immediately	34	* - empty SLABS are deallocated immediately
35	* (in Linux they are kept in linked list, in Solaris ???)	35	* (in Linux they are kept in linked list, in Solaris ???)
36	* - empty magazines are deallocated when not needed	36	* - empty magazines are deallocated when not needed
37	* (in Solaris they are held in linked list in slab cache)	37	* (in Solaris they are held in linked list in slab cache)
38	*	38	*
39	* Following features are not currently supported but would be easy to do:	39	* Following features are not currently supported but would be easy to do:
40	* - cache coloring	40	* - cache coloring
41	* - dynamic magazine growing (different magazine sizes are already	41	* - dynamic magazine growing (different magazine sizes are already
42	* supported, but we would need to adjust allocating strategy)	42	* supported, but we would need to adjust allocating strategy)
43	*	43	*
44	* The SLAB allocator supports per-CPU caches ('magazines') to facilitate	44	* The SLAB allocator supports per-CPU caches ('magazines') to facilitate
45	* good SMP scaling.	45	* good SMP scaling.
46	*	46	*
47	* When a new object is being allocated, it is first checked, if it is	47	* When a new object is being allocated, it is first checked, if it is
48	* available in CPU-bound magazine. If it is not found there, it is	48	* available in CPU-bound magazine. If it is not found there, it is
49	* allocated from CPU-shared SLAB - if partial full is found, it is used,	49	* allocated from CPU-shared SLAB - if partial full is found, it is used,
50	* otherwise a new one is allocated.	50	* otherwise a new one is allocated.
51	*	51	*
52	* When an object is being deallocated, it is put to CPU-bound magazine.	52	* When an object is being deallocated, it is put to CPU-bound magazine.
53	* If there is no such magazine, new one is allocated (if it fails,	53	* If there is no such magazine, new one is allocated (if it fails,
54	* the object is deallocated into SLAB). If the magazine is full, it is	54	* the object is deallocated into SLAB). If the magazine is full, it is
55	* put into cpu-shared list of magazines and new one is allocated.	55	* put into cpu-shared list of magazines and new one is allocated.
56	*	56	*
57	* The CPU-bound magazine is actually a pair of magazine to avoid	57	* The CPU-bound magazine is actually a pair of magazine to avoid
58	* thrashing when somebody is allocating/deallocating 1 item at the magazine	58	* thrashing when somebody is allocating/deallocating 1 item at the magazine
59	* size boundary. LIFO order is enforced, which should avoid fragmentation	59	* size boundary. LIFO order is enforced, which should avoid fragmentation
60	* as much as possible.	60	* as much as possible.
61	*	61	*
62	* Every cache contains list of full slabs and list of partialy full slabs.	62	* Every cache contains list of full slabs and list of partialy full slabs.
63	* Empty SLABS are immediately freed (thrashing will be avoided because	63	* Empty SLABS are immediately freed (thrashing will be avoided because
64	* of magazines).	64	* of magazines).
65	*	65	*
66	* The SLAB information structure is kept inside the data area, if possible.	66	* The SLAB information structure is kept inside the data area, if possible.
67	* The cache can be marked that it should not use magazines. This is used	67	* The cache can be marked that it should not use magazines. This is used
68	* only for SLAB related caches to avoid deadlocks and infinite recursion	68	* only for SLAB related caches to avoid deadlocks and infinite recursion
69	* (the SLAB allocator uses itself for allocating all it's control structures).	69	* (the SLAB allocator uses itself for allocating all it's control structures).
70	*	70	*
71	* The SLAB allocator allocates lot of space and does not free it. When	71	* The SLAB allocator allocates lot of space and does not free it. When
72	* frame allocator fails to allocate the frame, it calls slab_reclaim().	72	* frame allocator fails to allocate the frame, it calls slab_reclaim().
73	* It tries 'light reclaim' first, then brutal reclaim. The light reclaim	73	* It tries 'light reclaim' first, then brutal reclaim. The light reclaim
74	* releases slabs from cpu-shared magazine-list, until at least 1 slab	74	* releases slabs from cpu-shared magazine-list, until at least 1 slab
75	* is deallocated in each cache (this algorithm should probably change).	75	* is deallocated in each cache (this algorithm should probably change).
76	* The brutal reclaim removes all cached objects, even from CPU-bound	76	* The brutal reclaim removes all cached objects, even from CPU-bound
77	* magazines.	77	* magazines.
78	*	78	*
79	* TODO: For better CPU-scaling the magazine allocation strategy should	79	* TODO: For better CPU-scaling the magazine allocation strategy should
80	* be extended. Currently, if the cache does not have magazine, it asks	80	* be extended. Currently, if the cache does not have magazine, it asks
81	* for non-cpu cached magazine cache to provide one. It might be feasible	81	* for non-cpu cached magazine cache to provide one. It might be feasible
82	* to add cpu-cached magazine cache (which would allocate it's magazines	82	* to add cpu-cached magazine cache (which would allocate it's magazines
83	* from non-cpu-cached mag. cache). This would provide a nice per-cpu	83	* from non-cpu-cached mag. cache). This would provide a nice per-cpu
84	* buffer. The other possibility is to use the per-cache	84	* buffer. The other possibility is to use the per-cache
85	* 'empty-magazine-list', which decreases competing for 1 per-system	85	* 'empty-magazine-list', which decreases competing for 1 per-system
86	* magazine cache.	86	* magazine cache.
87	*	87	*
88	* - it might be good to add granularity of locks even to slab level,	88	* - it might be good to add granularity of locks even to slab level,
89	* we could then try_spinlock over all partial slabs and thus improve	89	* we could then try_spinlock over all partial slabs and thus improve
90	* scalability even on slab level	90	* scalability even on slab level
91	*/	91	*/
92		92
93		93
94	#include <synch/spinlock.h>	94	#include <synch/spinlock.h>
95	#include <mm/slab.h>	95	#include <mm/slab.h>
96	#include <list.h>	96	#include <list.h>
97	#include <memstr.h>	97	#include <memstr.h>
98	#include <align.h>	98	#include <align.h>
99	#include <mm/heap.h>	99	#include <mm/heap.h>
100	#include <mm/frame.h>	100	#include <mm/frame.h>
101	#include <config.h>	101	#include <config.h>
102	#include <print.h>	102	#include <print.h>
103	#include <arch.h>	103	#include <arch.h>
104	#include <panic.h>	104	#include <panic.h>
105	#include <debug.h>	105	#include <debug.h>
106	#include <bitops.h>	106	#include <bitops.h>
107		107
108	SPINLOCK_INITIALIZE(slab_cache_lock);	108	SPINLOCK_INITIALIZE(slab_cache_lock);
109	static LIST_INITIALIZE(slab_cache_list);	109	static LIST_INITIALIZE(slab_cache_list);
110		110
111	/** Magazine cache */	111	/** Magazine cache */
112	static slab_cache_t mag_cache;	112	static slab_cache_t mag_cache;
113	/** Cache for cache descriptors */	113	/** Cache for cache descriptors */
114	static slab_cache_t slab_cache_cache;	114	static slab_cache_t slab_cache_cache;
115		115
116	/** Cache for external slab descriptors	116	/** Cache for external slab descriptors
117	* This time we want per-cpu cache, so do not make it static	117	* This time we want per-cpu cache, so do not make it static
118	* - using SLAB for internal SLAB structures will not deadlock,	118	* - using SLAB for internal SLAB structures will not deadlock,
119	* as all slab structures are 'small' - control structures of	119	* as all slab structures are 'small' - control structures of
120	* their caches do not require further allocation	120	* their caches do not require further allocation
121	*/	121	*/
122	static slab_cache_t *slab_extern_cache;	122	static slab_cache_t *slab_extern_cache;
123	/** Caches for malloc */	123	/** Caches for malloc */
124	static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1];	124	static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1];
125	char *malloc_names[] = {	125	char *malloc_names[] = {
126	"malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",	126	"malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",
127	"malloc-256","malloc-512","malloc-1K","malloc-2K",	127	"malloc-256","malloc-512","malloc-1K","malloc-2K",
128	"malloc-4K","malloc-8K","malloc-16K","malloc-32K",	128	"malloc-4K","malloc-8K","malloc-16K","malloc-32K",
129	"malloc-64K","malloc-128K"	129	"malloc-64K","malloc-128K"
130	};	130	};
131		131
132	/** Slab descriptor */	132	/** Slab descriptor */
133	typedef struct {	133	typedef struct {
134	slab_cache_t cache; /< Pointer to parent cache /	134	slab_cache_t cache; /< Pointer to parent cache /
135	link_t link; /* List of full/partial slabs */	135	link_t link; /* List of full/partial slabs */
136	void start; /< Start address of first available item /	136	void start; /< Start address of first available item /
137	count_t available; /*< Count of available items in this slab /	137	count_t available; /*< Count of available items in this slab /
138	index_t nextavail; /*< The index of next available item /	138	index_t nextavail; /*< The index of next available item /
139	}slab_t;	139	}slab_t;
140		140
141	/**************************************/	141	/**************************************/
142	/* SLAB allocation functions */	142	/* SLAB allocation functions */
143		143
144	/**	144	/**
145	* Allocate frames for slab space and initialize	145	* Allocate frames for slab space and initialize
146	*	146	*
147	*/	147	*/
148	static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)	148	static slab_t * slab_space_alloc(slab_cache_t *cache, int flags)
149	{	149	{
150	void *data;	150	void *data;
151	slab_t *slab;	151	slab_t *slab;
152	size_t fsize;	152	size_t fsize;
153	int i;	153	int i;
154	zone_t *zone = NULL;	154	zone_t *zone = NULL;
155	int status;	155	int status;
156	frame_t *frame;	156	frame_t *frame;
157		157
158	data = (void *)frame_alloc(FRAME_KA \| flags, cache->order, &status, &zone);	158	data = (void *)frame_alloc(FRAME_KA \| flags, cache->order, &status, &zone);
159	if (status != FRAME_OK) {	159	if (status != FRAME_OK) {
160	return NULL;	160	return NULL;
161	}	161	}
162	if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {	162	if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
163	slab = slab_alloc(slab_extern_cache, flags);	163	slab = slab_alloc(slab_extern_cache, flags);
164	if (!slab) {	164	if (!slab) {
165	frame_free((__address)data);	165	frame_free((__address)data);
166	return NULL;	166	return NULL;
167	}	167	}
168	} else {	168	} else {
169	fsize = (PAGE_SIZE << cache->order);	169	fsize = (PAGE_SIZE << cache->order);
170	slab = data + fsize - sizeof(*slab);	170	slab = data + fsize - sizeof(*slab);
171	}	171	}
172		172
173	/* Fill in slab structures */	173	/* Fill in slab structures */
174	/* TODO: some better way of accessing the frame */	174	/* TODO: some better way of accessing the frame */
175	for (i=0; i < (1 << cache->order); i++) {	175	for (i=0; i < (1 << cache->order); i++) {
176	frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));	176	frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));
177	frame->parent = slab;	177	frame->parent = slab;
178	}	178	}
179		179
180	slab->start = data;	180	slab->start = data;
181	slab->available = cache->objects;	181	slab->available = cache->objects;
182	slab->nextavail = 0;	182	slab->nextavail = 0;
183	slab->cache = cache;	183	slab->cache = cache;
184		184
185	for (i=0; i<cache->objects;i++)	185	for (i=0; i<cache->objects;i++)
186	((int ) (slab->start + i*cache->size)) = i+1;	186	((int ) (slab->start + i*cache->size)) = i+1;
187		187
188	atomic_inc(&cache->allocated_slabs);	188	atomic_inc(&cache->allocated_slabs);
189	return slab;	189	return slab;
190	}	190	}
191		191
192	/**	192	/**
193	* Deallocate space associated with SLAB	193	* Deallocate space associated with SLAB
194	*	194	*
195	* @return number of freed frames	195	* @return number of freed frames
196	*/	196	*/
197	static count_t slab_space_free(slab_cache_t cache, slab_t slab)	197	static count_t slab_space_free(slab_cache_t cache, slab_t slab)
198	{	198	{
199	frame_free((__address)slab->start);	199	frame_free((__address)slab->start);
200	if (! (cache->flags & SLAB_CACHE_SLINSIDE))	200	if (! (cache->flags & SLAB_CACHE_SLINSIDE))
201	slab_free(slab_extern_cache, slab);	201	slab_free(slab_extern_cache, slab);
202		202
203	atomic_dec(&cache->allocated_slabs);	203	atomic_dec(&cache->allocated_slabs);
204		204
205	return 1 << cache->order;	205	return 1 << cache->order;
206	}	206	}
207		207
208	/** Map object to slab structure */	208	/** Map object to slab structure */
209	static slab_t * obj2slab(void *obj)	209	static slab_t * obj2slab(void *obj)
210	{	210	{
211	frame_t *frame;	211	frame_t *frame;
212		212
213	frame = frame_addr2frame((__address)obj);	213	frame = frame_addr2frame((__address)obj);
214	return (slab_t *)frame->parent;	214	return (slab_t *)frame->parent;
215	}	215	}
216		216
217	/**************************************/	217	/**************************************/
218	/* SLAB functions */	218	/* SLAB functions */
219		219
220		220
221	/**	221	/**
222	* Return object to slab and call a destructor	222	* Return object to slab and call a destructor
223	*	223	*
224	* @param slab If the caller knows directly slab of the object, otherwise NULL	224	* @param slab If the caller knows directly slab of the object, otherwise NULL
225	*	225	*
226	* @return Number of freed pages	226	* @return Number of freed pages
227	*/	227	*/
228	static count_t slab_obj_destroy(slab_cache_t cache, void obj,	228	static count_t slab_obj_destroy(slab_cache_t cache, void obj,
229	slab_t *slab)	229	slab_t *slab)
230	{	230	{
231	count_t frames = 0;	231	count_t frames = 0;
232		232
233	if (!slab)	233	if (!slab)
234	slab = obj2slab(obj);	234	slab = obj2slab(obj);
235		235
236	ASSERT(slab->cache == cache);	236	ASSERT(slab->cache == cache);
237	ASSERT(slab->available < cache->objects);	237	ASSERT(slab->available < cache->objects);
238		238
239	spinlock_lock(&cache->slablock);	239	spinlock_lock(&cache->slablock);
240		240
241	((int )obj) = slab->nextavail;	241	((int )obj) = slab->nextavail;
242	slab->nextavail = (obj - slab->start)/cache->size;	242	slab->nextavail = (obj - slab->start)/cache->size;
243	slab->available++;	243	slab->available++;
244		244
245	/* Move it to correct list */	245	/* Move it to correct list */
246	if (slab->available == cache->objects) {	246	if (slab->available == cache->objects) {
247	/* Free associated memory */	247	/* Free associated memory */
248	list_remove(&slab->link);	248	list_remove(&slab->link);
249	/* This should not produce deadlock, as	249	/* This should not produce deadlock, as
250	* magazine is always allocated with NO reclaim,	250	* magazine is always allocated with NO reclaim,
251	* keep all locks */	251	* keep all locks */
252	frames = slab_space_free(cache, slab);	252	frames = slab_space_free(cache, slab);
253	} else if (slab->available == 1) {	253	} else if (slab->available == 1) {
254	/* It was in full, move to partial */	254	/* It was in full, move to partial */
255	list_remove(&slab->link);	255	list_remove(&slab->link);
256	list_prepend(&slab->link, &cache->partial_slabs);	256	list_prepend(&slab->link, &cache->partial_slabs);
257	}	257	}
258		258
259	spinlock_unlock(&cache->slablock);	259	spinlock_unlock(&cache->slablock);
260		260
261	return frames;	261	return frames;
262	}	262	}
263		263
264	/**	264	/**
265	* Take new object from slab or create new if needed	265	* Take new object from slab or create new if needed
266	*	266	*
267	* @return Object address or null	267	* @return Object address or null
268	*/	268	*/
269	static void * slab_obj_create(slab_cache_t *cache, int flags)	269	static void * slab_obj_create(slab_cache_t *cache, int flags)
270	{	270	{
271	slab_t *slab;	271	slab_t *slab;
272	void *obj;	272	void *obj;
273		273
274	spinlock_lock(&cache->slablock);	274	spinlock_lock(&cache->slablock);
275		275
276	if (list_empty(&cache->partial_slabs)) {	276	if (list_empty(&cache->partial_slabs)) {
277	/* Allow recursion and reclaiming	277	/* Allow recursion and reclaiming
278	* - this should work, as the SLAB control structures	278	* - this should work, as the SLAB control structures
279	* are small and do not need to allocte with anything	279	* are small and do not need to allocte with anything
280	* other ten frame_alloc when they are allocating,	280	* other ten frame_alloc when they are allocating,
281	* that's why we should get recursion at most 1-level deep	281	* that's why we should get recursion at most 1-level deep
282	*/	282	*/
283	spinlock_unlock(&cache->slablock);	283	spinlock_unlock(&cache->slablock);
284	slab = slab_space_alloc(cache, flags);	284	slab = slab_space_alloc(cache, flags);
285	if (!slab)	285	if (!slab)
286	return NULL;	286	return NULL;
287	spinlock_lock(&cache->slablock);	287	spinlock_lock(&cache->slablock);
288	} else {	288	} else {
289	slab = list_get_instance(cache->partial_slabs.next,	289	slab = list_get_instance(cache->partial_slabs.next,
290	slab_t,	290	slab_t,
291	link);	291	link);
292	list_remove(&slab->link);	292	list_remove(&slab->link);
293	}	293	}
294	obj = slab->start + slab->nextavail * cache->size;	294	obj = slab->start + slab->nextavail * cache->size;
295	slab->nextavail = ((int )obj);	295	slab->nextavail = ((int )obj);
296	slab->available--;	296	slab->available--;
297	if (! slab->available)	297	if (! slab->available)
298	list_prepend(&slab->link, &cache->full_slabs);	298	list_prepend(&slab->link, &cache->full_slabs);
299	else	299	else
300	list_prepend(&slab->link, &cache->partial_slabs);	300	list_prepend(&slab->link, &cache->partial_slabs);
301		301
302	spinlock_unlock(&cache->slablock);	302	spinlock_unlock(&cache->slablock);
303	return obj;	303	return obj;
304	}	304	}
305		305
306	/**************************************/	306	/**************************************/
307	/* CPU-Cache slab functions */	307	/* CPU-Cache slab functions */
308		308
309	/**	309	/**
-		310	* Finds a full magazine in cache, takes it from list
-		311	* and returns it
-		312	*
-		313	* @param first If true, return first, else last mag
-		314	*/
-		315	static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache,
-		316	int first)
-		317	{
-		318	slab_magazine_t *mag = NULL;
-		319	link_t *cur;
-		320
-		321	spinlock_lock(&cache->maglock);
-		322	if (!list_empty(&cache->magazines)) {
-		323	if (first)
-		324	cur = cache->magazines.next;
-		325	else
-		326	cur = cache->magazines.prev;
-		327	mag = list_get_instance(cur, slab_magazine_t, link);
-		328	list_remove(&mag->link);
-		329	atomic_dec(&cache->magazine_counter);
-		330	}
-		331	spinlock_unlock(&cache->maglock);
-		332	return mag;
-		333	}
-		334
-		335	/** Prepend magazine to magazine list in cache */
-		336	static void put_mag_to_cache(slab_cache_t cache, slab_magazine_t mag)
-		337	{
-		338	spinlock_lock(&cache->maglock);
-		339
-		340	list_prepend(&mag->link, &cache->magazines);
-		341	atomic_inc(&cache->magazine_counter);
-		342
-		343	spinlock_unlock(&cache->maglock);
-		344	}
-		345
-		346	/**
310	* Free all objects in magazine and free memory associated with magazine	347	* Free all objects in magazine and free memory associated with magazine
311	*	348	*
312	* @return Number of freed pages	349	* @return Number of freed pages
313	*/	350	*/
314	static count_t magazine_destroy(slab_cache_t *cache,	351	static count_t magazine_destroy(slab_cache_t *cache,
315	slab_magazine_t *mag)	352	slab_magazine_t *mag)
316	{	353	{
317	int i;	354	int i;
318	count_t frames = 0;	355	count_t frames = 0;
319		356
320	for (i=0;i < mag->busy; i++) {	357	for (i=0;i < mag->busy; i++) {
321	frames += slab_obj_destroy(cache, mag->objs[i], NULL);	358	frames += slab_obj_destroy(cache, mag->objs[i], NULL);
322	atomic_dec(&cache->cached_objs);	359	atomic_dec(&cache->cached_objs);
323	}	360	}
324		361
325	slab_free(&mag_cache, mag);	362	slab_free(&mag_cache, mag);
326		363
327	return frames;	364	return frames;
328	}	365	}
329		366
330	/**	367	/**
331	* Find full magazine, set it as current and return it	368	* Find full magazine, set it as current and return it
332	*	369	*
333	* Assume cpu_magazine lock is held	370	* Assume cpu_magazine lock is held
334	*/	371	*/
335	static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)	372	static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
336	{	373	{
337	slab_magazine_t cmag, lastmag, *newmag;	374	slab_magazine_t cmag, lastmag, *newmag;
338		375
339	cmag = cache->mag_cache[CPU->id].current;	376	cmag = cache->mag_cache[CPU->id].current;
340	lastmag = cache->mag_cache[CPU->id].last;	377	lastmag = cache->mag_cache[CPU->id].last;
341	if (cmag) { /* First try local CPU magazines */	378	if (cmag) { /* First try local CPU magazines */
342	if (cmag->busy)	379	if (cmag->busy)
343	return cmag;	380	return cmag;
344		381
345	if (lastmag && lastmag->busy) {	382	if (lastmag && lastmag->busy) {
346	cache->mag_cache[CPU->id].current = lastmag;	383	cache->mag_cache[CPU->id].current = lastmag;
347	cache->mag_cache[CPU->id].last = cmag;	384	cache->mag_cache[CPU->id].last = cmag;
348	return lastmag;	385	return lastmag;
349	}	386	}
350	}	387	}
351	/* Local magazines are empty, import one from magazine list */	388	/* Local magazines are empty, import one from magazine list */
352	spinlock_lock(&cache->maglock);	389	newmag = get_mag_from_cache(cache, 1);
353	if (list_empty(&cache->magazines)) {	390	if (!newmag)
354	spinlock_unlock(&cache->maglock);	-
355	return NULL;	391	return NULL;
356	}	-
357	newmag = list_get_instance(cache->magazines.next,	-
358	slab_magazine_t,	-
359	link);	-
360	list_remove(&newmag->link);	-
361	spinlock_unlock(&cache->maglock);	-
362		392
363	if (lastmag)	393	if (lastmag)
364	slab_free(&mag_cache, lastmag);	394	magazine_destroy(cache, lastmag);
-		395
365	cache->mag_cache[CPU->id].last = cmag;	396	cache->mag_cache[CPU->id].last = cmag;
366	cache->mag_cache[CPU->id].current = newmag;	397	cache->mag_cache[CPU->id].current = newmag;
367	return newmag;	398	return newmag;
368	}	399	}
369		400
370	/**	401	/**
371	* Try to find object in CPU-cache magazines	402	* Try to find object in CPU-cache magazines
372	*	403	*
373	* @return Pointer to object or NULL if not available	404	* @return Pointer to object or NULL if not available
374	*/	405	*/
375	static void * magazine_obj_get(slab_cache_t *cache)	406	static void * magazine_obj_get(slab_cache_t *cache)
376	{	407	{
377	slab_magazine_t *mag;	408	slab_magazine_t *mag;
378	void *obj;	409	void *obj;
379		410
380	if (!CPU)	411	if (!CPU)
381	return NULL;	412	return NULL;
382		413
383	spinlock_lock(&cache->mag_cache[CPU->id].lock);	414	spinlock_lock(&cache->mag_cache[CPU->id].lock);
384		415
385	mag = get_full_current_mag(cache);	416	mag = get_full_current_mag(cache);
386	if (!mag) {	417	if (!mag) {
387	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	418	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
388	return NULL;	419	return NULL;
389	}	420	}
390	obj = mag->objs[--mag->busy];	421	obj = mag->objs[--mag->busy];
391	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	422	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
392	atomic_dec(&cache->cached_objs);	423	atomic_dec(&cache->cached_objs);
393		424
394	return obj;	425	return obj;
395	}	426	}
396		427
397	/**	428	/**
398	* Assure that the current magazine is empty, return pointer to it, or NULL if	429	* Assure that the current magazine is empty, return pointer to it, or NULL if
399	* no empty magazine is available and cannot be allocated	430	* no empty magazine is available and cannot be allocated
400	*	431	*
401	* Assume mag_cache[CPU->id].lock is held	432	* Assume mag_cache[CPU->id].lock is held
402	*	433	*
403	* We have 2 magazines bound to processor.	434	* We have 2 magazines bound to processor.
404	* First try the current.	435	* First try the current.
405	* If full, try the last.	436	* If full, try the last.
406	* If full, put to magazines list.	437	* If full, put to magazines list.
407	* allocate new, exchange last & current	438	* allocate new, exchange last & current
408	*	439	*
409	*/	440	*/
410	static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)	441	static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
411	{	442	{
412	slab_magazine_t cmag,lastmag,*newmag;	443	slab_magazine_t cmag,lastmag,*newmag;
413		444
414	cmag = cache->mag_cache[CPU->id].current;	445	cmag = cache->mag_cache[CPU->id].current;
415	lastmag = cache->mag_cache[CPU->id].last;	446	lastmag = cache->mag_cache[CPU->id].last;
416		447
417	if (cmag) {	448	if (cmag) {
418	if (cmag->busy < cmag->size)	449	if (cmag->busy < cmag->size)
419	return cmag;	450	return cmag;
420	if (lastmag && lastmag->busy < lastmag->size) {	451	if (lastmag && lastmag->busy < lastmag->size) {
421	cache->mag_cache[CPU->id].last = cmag;	452	cache->mag_cache[CPU->id].last = cmag;
422	cache->mag_cache[CPU->id].current = lastmag;	453	cache->mag_cache[CPU->id].current = lastmag;
423	return lastmag;	454	return lastmag;
424	}	455	}
425	}	456	}
426	/* current \| last are full \| nonexistent, allocate new */	457	/* current \| last are full \| nonexistent, allocate new */
427	/* We do not want to sleep just because of caching */	458	/* We do not want to sleep just because of caching */
428	/* Especially we do not want reclaiming to start, as	459	/* Especially we do not want reclaiming to start, as
429	* this would deadlock */	460	* this would deadlock */
430	newmag = slab_alloc(&mag_cache, FRAME_ATOMIC \| FRAME_NO_RECLAIM);	461	newmag = slab_alloc(&mag_cache, FRAME_ATOMIC \| FRAME_NO_RECLAIM);
431	if (!newmag)	462	if (!newmag)
432	return NULL;	463	return NULL;
433	newmag->size = SLAB_MAG_SIZE;	464	newmag->size = SLAB_MAG_SIZE;
434	newmag->busy = 0;	465	newmag->busy = 0;
435		466
436	/* Flush last to magazine list */	467	/* Flush last to magazine list */
437	if (lastmag) {	468	if (lastmag)
438	spinlock_lock(&cache->maglock);	469	put_mag_to_cache(cache, lastmag);
439	list_prepend(&lastmag->link, &cache->magazines);	-
440	spinlock_unlock(&cache->maglock);	-
441	}	470
442	/* Move current as last, save new as current */	471	/* Move current as last, save new as current */
443	cache->mag_cache[CPU->id].last = cmag;	472	cache->mag_cache[CPU->id].last = cmag;
444	cache->mag_cache[CPU->id].current = newmag;	473	cache->mag_cache[CPU->id].current = newmag;
445		474
446	return newmag;	475	return newmag;
447	}	476	}
448		477
449	/**	478	/**
450	* Put object into CPU-cache magazine	479	* Put object into CPU-cache magazine
451	*	480	*
452	* @return 0 - success, -1 - could not get memory	481	* @return 0 - success, -1 - could not get memory
453	*/	482	*/
454	static int magazine_obj_put(slab_cache_t cache, void obj)	483	static int magazine_obj_put(slab_cache_t cache, void obj)
455	{	484	{
456	slab_magazine_t *mag;	485	slab_magazine_t *mag;
457		486
458	if (!CPU)	487	if (!CPU)
459	return -1;	488	return -1;
460		489
461	spinlock_lock(&cache->mag_cache[CPU->id].lock);	490	spinlock_lock(&cache->mag_cache[CPU->id].lock);
462		491

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/slab.c – Rev 780 → 781