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);
 
    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 == 1) {
        /* It was in full, move to partial */
        list_remove(&slab->link);
        list_prepend(&slab->link, &cache->partial_slabs);
    }
    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);
 
    }
 
    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);
        spinlock_lock(&cache->slablock);
        if (!slab)
            goto err;
 
    } 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;
err:
    spinlock_unlock(&cache->slablock);
    return NULL;
}
 
/**************************************/
/* CPU-Cache slab functions */
 
/**
 * 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 */
    spinlock_lock(&cache->maglock);
    if (list_empty(&cache->magazines)) {
        spinlock_unlock(&cache->maglock);
        return NULL;
    }
    newmag = list_get_instance(cache->magazines.next,
                   slab_magazine_t,
                   link);
    list_remove(&newmag->link);
    spinlock_unlock(&cache->maglock);
 
    if (lastmag)
        slab_free(&mag_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) {
        spinlock_lock(&cache->maglock);
        list_prepend(&lastmag->link, &cache->magazines);
        spinlock_unlock(&cache->maglock);
    }
    /* 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;
    link_t *cur;
    count_t frames = 0;
   
    if (cache->flags & SLAB_CACHE_NOMAGAZINE)
        return 0; /* Nothing to do */
   
    /* First lock all cpu caches, then the complete cache lock */
    if (flags & SLAB_RECLAIM_ALL) {
        for (i=0; i < config.cpu_count; i++)
            spinlock_lock(&cache->mag_cache[i].lock);
    }
    spinlock_lock(&cache->maglock);
   
    if (flags & SLAB_RECLAIM_ALL) {
        /* Aggressive memfree */
        /* Destroy CPU magazines */
        for (i=0; i<config.cpu_count; i++) {
            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;
        }
    }
    /* We can release the cache locks now */
    if (flags & SLAB_RECLAIM_ALL) {
        for (i=0; i < config.cpu_count; i++)
            spinlock_unlock(&cache->mag_cache[i].lock);
    }
    /* Destroy full magazines */
    cur=cache->magazines.prev;
 
    while (cur != &cache->magazines) {
        mag = list_get_instance(cur, slab_magazine_t, link);
       
        cur = cur->prev;
        list_remove(&mag->link);
        frames += magazine_destroy(cache,mag);
        /* If we do not do full reclaim, break
         * as soon as something is freed */
        if (!(flags & SLAB_RECLAIM_ALL) && frames)
            break;
    }
   
    spinlock_unlock(&cache->maglock);
 
 
 
 
 
   
    return frames;
}
 
/** Check that there are no slabs and remove cache from system  */
void slab_cache_destroy(slab_cache_t *cache)
{
    /* 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.");
 
    spinlock_lock(&slab_cache_lock);
    list_remove(&cache->link);
    spinlock_unlock(&slab_cache_lock);
 
    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.
     */
 
    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);
}
 
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);
    }
}
 
/**************************************/
/* kalloc/kfree functions             */
void * kalloc(unsigned int size, int flags)
{
    int idx;
   
    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 = obj2slab(obj);
   
    _slab_free(slab->cache, obj, slab);
}
 

Rev 775	Rev 776
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,
-		89	* we could then try_spinlock over all partial slabs and thus improve
-		90	* scalability even on slab level
88	*/	91	*/
89		92
90		93
91	#include <synch/spinlock.h>	94	#include <synch/spinlock.h>
92	#include <mm/slab.h>	95	#include <mm/slab.h>
93	#include <list.h>	96	#include <list.h>
94	#include <memstr.h>	97	#include <memstr.h>
95	#include <align.h>	98	#include <align.h>
96	#include <mm/heap.h>	99	#include <mm/heap.h>
97	#include <mm/frame.h>	100	#include <mm/frame.h>
98	#include <config.h>	101	#include <config.h>
99	#include <print.h>	102	#include <print.h>
100	#include <arch.h>	103	#include <arch.h>
101	#include <panic.h>	104	#include <panic.h>
102	#include <debug.h>	105	#include <debug.h>
103	#include <bitops.h>	106	#include <bitops.h>
104		107
105	SPINLOCK_INITIALIZE(slab_cache_lock);	108	SPINLOCK_INITIALIZE(slab_cache_lock);
106	static LIST_INITIALIZE(slab_cache_list);	109	static LIST_INITIALIZE(slab_cache_list);
107		110
108	/** Magazine cache */	111	/** Magazine cache */
109	static slab_cache_t mag_cache;	112	static slab_cache_t mag_cache;
110	/** Cache for cache descriptors */	113	/** Cache for cache descriptors */
111	static slab_cache_t slab_cache_cache;	114	static slab_cache_t slab_cache_cache;
112		115
113	/** Cache for external slab descriptors	116	/** Cache for external slab descriptors
114	* 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
115	* - using SLAB for internal SLAB structures will not deadlock,	118	* - using SLAB for internal SLAB structures will not deadlock,
116	* as all slab structures are 'small' - control structures of	119	* as all slab structures are 'small' - control structures of
117	* their caches do not require further allocation	120	* their caches do not require further allocation
118	*/	121	*/
119	static slab_cache_t *slab_extern_cache;	122	static slab_cache_t *slab_extern_cache;
120	/** Caches for malloc */	123	/** Caches for malloc */
121	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];
122	char *malloc_names[] = {	125	char *malloc_names[] = {
123	"malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",	126	"malloc-8","malloc-16","malloc-32","malloc-64","malloc-128",
124	"malloc-256","malloc-512","malloc-1K","malloc-2K",	127	"malloc-256","malloc-512","malloc-1K","malloc-2K",
125	"malloc-4K","malloc-8K","malloc-16K","malloc-32K",	128	"malloc-4K","malloc-8K","malloc-16K","malloc-32K",
126	"malloc-64K","malloc-128K"	129	"malloc-64K","malloc-128K"
127	};	130	};
128		131
129	/** Slab descriptor */	132	/** Slab descriptor */
130	typedef struct {	133	typedef struct {
131	slab_cache_t cache; /< Pointer to parent cache /	134	slab_cache_t cache; /< Pointer to parent cache /
132	link_t link; /* List of full/partial slabs */	135	link_t link; /* List of full/partial slabs */
133	void start; /< Start address of first available item /	136	void start; /< Start address of first available item /
134	count_t available; /*< Count of available items in this slab /	137	count_t available; /*< Count of available items in this slab /
135	index_t nextavail; /*< The index of next available item /	138	index_t nextavail; /*< The index of next available item /
136	}slab_t;	139	}slab_t;
137		140
138	/**************************************/	141	/**************************************/
139	/* SLAB allocation functions */	142	/* SLAB allocation functions */
140		143
141	/**	144	/**
142	* Allocate frames for slab space and initialize	145	* Allocate frames for slab space and initialize
143	*	146	*
144	*/	147	*/
145	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)
146	{	149	{
147	void *data;	150	void *data;
148	slab_t *slab;	151	slab_t *slab;
149	size_t fsize;	152	size_t fsize;
150	int i;	153	int i;
151	zone_t *zone = NULL;	154	zone_t *zone = NULL;
152	int status;	155	int status;
153	frame_t *frame;	156	frame_t *frame;
154		157
155	data = (void *)frame_alloc(FRAME_KA \| flags, cache->order, &status, &zone);	158	data = (void *)frame_alloc(FRAME_KA \| flags, cache->order, &status, &zone);
156	if (status != FRAME_OK) {	159	if (status != FRAME_OK) {
157	return NULL;	160	return NULL;
158	}	161	}
159	if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {	162	if (! (cache->flags & SLAB_CACHE_SLINSIDE)) {
160	slab = slab_alloc(slab_extern_cache, flags);	163	slab = slab_alloc(slab_extern_cache, flags);
161	if (!slab) {	164	if (!slab) {
162	frame_free((__address)data);	165	frame_free((__address)data);
163	return NULL;	166	return NULL;
164	}	167	}
165	} else {	168	} else {
166	fsize = (PAGE_SIZE << cache->order);	169	fsize = (PAGE_SIZE << cache->order);
167	slab = data + fsize - sizeof(*slab);	170	slab = data + fsize - sizeof(*slab);
168	}	171	}
169		172
170	/* Fill in slab structures */	173	/* Fill in slab structures */
171	/* TODO: some better way of accessing the frame */	174	/* TODO: some better way of accessing the frame */
172	for (i=0; i < (1 << cache->order); i++) {	175	for (i=0; i < (1 << cache->order); i++) {
173	frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));	176	frame = ADDR2FRAME(zone, KA2PA((__address)(data+i*PAGE_SIZE)));
174	frame->parent = slab;	177	frame->parent = slab;
175	}	178	}
176		179
177	slab->start = data;	180	slab->start = data;
178	slab->available = cache->objects;	181	slab->available = cache->objects;
179	slab->nextavail = 0;	182	slab->nextavail = 0;
180	slab->cache = cache;	183	slab->cache = cache;
181		184
182	for (i=0; i<cache->objects;i++)	185	for (i=0; i<cache->objects;i++)
183	((int ) (slab->start + i*cache->size)) = i+1;	186	((int ) (slab->start + i*cache->size)) = i+1;
184		187
185	atomic_inc(&cache->allocated_slabs);	188	atomic_inc(&cache->allocated_slabs);
186	return slab;	189	return slab;
187	}	190	}
188		191
189	/**	192	/**
190	* Deallocate space associated with SLAB	193	* Deallocate space associated with SLAB
191	*	194	*
192	* @return number of freed frames	195	* @return number of freed frames
193	*/	196	*/
194	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)
195	{	198	{
196	frame_free((__address)slab->start);	199	frame_free((__address)slab->start);
197	if (! (cache->flags & SLAB_CACHE_SLINSIDE))	200	if (! (cache->flags & SLAB_CACHE_SLINSIDE))
198	slab_free(slab_extern_cache, slab);	201	slab_free(slab_extern_cache, slab);
199		202
200	atomic_dec(&cache->allocated_slabs);	203	atomic_dec(&cache->allocated_slabs);
201		204
202	return 1 << cache->order;	205	return 1 << cache->order;
203	}	206	}
204		207
205	/** Map object to slab structure */	208	/** Map object to slab structure */
206	static slab_t * obj2slab(void *obj)	209	static slab_t * obj2slab(void *obj)
207	{	210	{
208	frame_t *frame;	211	frame_t *frame;
209		212
210	frame = frame_addr2frame((__address)obj);	213	frame = frame_addr2frame((__address)obj);
211	return (slab_t *)frame->parent;	214	return (slab_t *)frame->parent;
212	}	215	}
213		216
214	/**************************************/	217	/**************************************/
215	/* SLAB functions */	218	/* SLAB functions */
216		219
217		220
218	/**	221	/**
219	* Return object to slab and call a destructor	222	* Return object to slab and call a destructor
220	*	223	*
221	* Assume the cache->lock is held;	-
222	*	-
223	* @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
224	*	225	*
225	* @return Number of freed pages	226	* @return Number of freed pages
226	*/	227	*/
227	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,
228	slab_t *slab)	229	slab_t *slab)
229	{	230	{
230	count_t frames = 0;	231	count_t frames = 0;
231		232
232	if (!slab)	233	if (!slab)
233	slab = obj2slab(obj);	234	slab = obj2slab(obj);
234		235
235	ASSERT(slab->cache == cache);	236	ASSERT(slab->cache == cache);
236		237
-		238	spinlock_lock(&cache->slablock);
-		239
237	((int )obj) = slab->nextavail;	240	((int )obj) = slab->nextavail;
238	slab->nextavail = (obj - slab->start)/cache->size;	241	slab->nextavail = (obj - slab->start)/cache->size;
239	slab->available++;	242	slab->available++;
240		243
241	/* Move it to correct list */	244	/* Move it to correct list */
242	if (slab->available == 1) {	245	if (slab->available == 1) {
243	/* It was in full, move to partial */	246	/* It was in full, move to partial */
244	list_remove(&slab->link);	247	list_remove(&slab->link);
245	list_prepend(&slab->link, &cache->partial_slabs);	248	list_prepend(&slab->link, &cache->partial_slabs);
246	}	249	}
247	if (slab->available == cache->objects) {	250	if (slab->available == cache->objects) {
248	/* Free associated memory */	251	/* Free associated memory */
249	list_remove(&slab->link);	252	list_remove(&slab->link);
250	/* Avoid deadlock */	253	/* This should not produce deadlock, as
-		254	* magazine is always allocated with NO reclaim,
251	spinlock_unlock(&cache->lock);	255	* keep all locks */
252	frames = slab_space_free(cache, slab);	256	frames = slab_space_free(cache, slab);
253	spinlock_lock(&cache->lock);	-
254	}	257	}
255		258
-		259	spinlock_unlock(&cache->slablock);
-		260
256	return frames;	261	return frames;
257	}	262	}
258		263
259	/**	264	/**
260	* Take new object from slab or create new if needed	265	* Take new object from slab or create new if needed
261	*	266	*
262	* Assume cache->lock is held.	-
263	*	-
264	* @return Object address or null	267	* @return Object address or null
265	*/	268	*/
266	static void * slab_obj_create(slab_cache_t *cache, int flags)	269	static void * slab_obj_create(slab_cache_t *cache, int flags)
267	{	270	{
268	slab_t *slab;	271	slab_t *slab;
269	void *obj;	272	void *obj;
270		273
-		274	spinlock_lock(&cache->slablock);
-		275
271	if (list_empty(&cache->partial_slabs)) {	276	if (list_empty(&cache->partial_slabs)) {
272	/* Allow recursion and reclaiming	277	/* Allow recursion and reclaiming
273	* - this should work, as the SLAB control structures	278	* - this should work, as the SLAB control structures
274	* are small and do not need to allocte with anything	279	* are small and do not need to allocte with anything
275	* other ten frame_alloc when they are allocating,	280	* other ten frame_alloc when they are allocating,
276	* 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
277	*/	282	*/
278	spinlock_unlock(&cache->lock);	283	spinlock_unlock(&cache->slablock);
279	slab = slab_space_alloc(cache, flags);	284	slab = slab_space_alloc(cache, flags);
280	spinlock_lock(&cache->lock);	285	spinlock_lock(&cache->slablock);
281	if (!slab) {	286	if (!slab)
282	return NULL;	287	goto err;
283	}	-
284	} else {	288	} else {
285	slab = list_get_instance(cache->partial_slabs.next,	289	slab = list_get_instance(cache->partial_slabs.next,
286	slab_t,	290	slab_t,
287	link);	291	link);
288	list_remove(&slab->link);	292	list_remove(&slab->link);
289	}	293	}
290	obj = slab->start + slab->nextavail * cache->size;	294	obj = slab->start + slab->nextavail * cache->size;
291	slab->nextavail = ((int )obj);	295	slab->nextavail = ((int )obj);
292	slab->available--;	296	slab->available--;
293	if (! slab->available)	297	if (! slab->available)
294	list_prepend(&slab->link, &cache->full_slabs);	298	list_prepend(&slab->link, &cache->full_slabs);
295	else	299	else
296	list_prepend(&slab->link, &cache->partial_slabs);	300	list_prepend(&slab->link, &cache->partial_slabs);
-		301
-		302	spinlock_unlock(&cache->slablock);
297	return obj;	303	return obj;
-		304	err:
-		305	spinlock_unlock(&cache->slablock);
-		306	return NULL;
298	}	307	}
299		308
300	/**************************************/	309	/**************************************/
301	/* CPU-Cache slab functions */	310	/* CPU-Cache slab functions */
302		311
303	/**	312	/**
304	* Free all objects in magazine and free memory associated with magazine	313	* Free all objects in magazine and free memory associated with magazine
305	*	314	*
306	* Assume cache->lock is held	-
307	*	-
308	* @return Number of freed pages	315	* @return Number of freed pages
309	*/	316	*/
310	static count_t magazine_destroy(slab_cache_t *cache,	317	static count_t magazine_destroy(slab_cache_t *cache,
311	slab_magazine_t *mag)	318	slab_magazine_t *mag)
312	{	319	{
313	int i;	320	int i;
314	count_t frames = 0;	321	count_t frames = 0;
315		322
316	for (i=0;i < mag->busy; i++) {	323	for (i=0;i < mag->busy; i++) {
317	frames += slab_obj_destroy(cache, mag->objs[i], NULL);	324	frames += slab_obj_destroy(cache, mag->objs[i], NULL);
318	atomic_dec(&cache->cached_objs);	325	atomic_dec(&cache->cached_objs);
319	}	326	}
320		327
321	slab_free(&mag_cache, mag);	328	slab_free(&mag_cache, mag);
322		329
323	return frames;	330	return frames;
324	}	331	}
325		332
326	/**	333	/**
327	* Find full magazine, set it as current and return it	334	* Find full magazine, set it as current and return it
328	*	335	*
329	* Assume cpu_magazine lock is held	336	* Assume cpu_magazine lock is held
330	*/	337	*/
331	static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)	338	static slab_magazine_t * get_full_current_mag(slab_cache_t *cache)
332	{	339	{
333	slab_magazine_t cmag, lastmag, *newmag;	340	slab_magazine_t cmag, lastmag, *newmag;
334		341
335	cmag = cache->mag_cache[CPU->id].current;	342	cmag = cache->mag_cache[CPU->id].current;
336	lastmag = cache->mag_cache[CPU->id].last;	343	lastmag = cache->mag_cache[CPU->id].last;
337	if (cmag) { /* First try local CPU magazines */	344	if (cmag) { /* First try local CPU magazines */
338	if (cmag->busy)	345	if (cmag->busy)
339	return cmag;	346	return cmag;
340		347
341	if (lastmag && lastmag->busy) {	348	if (lastmag && lastmag->busy) {
342	cache->mag_cache[CPU->id].current = lastmag;	349	cache->mag_cache[CPU->id].current = lastmag;
343	cache->mag_cache[CPU->id].last = cmag;	350	cache->mag_cache[CPU->id].last = cmag;
344	return lastmag;	351	return lastmag;
345	}	352	}
346	}	353	}
347	/* Local magazines are empty, import one from magazine list */	354	/* Local magazines are empty, import one from magazine list */
348	spinlock_lock(&cache->lock);	355	spinlock_lock(&cache->maglock);
349	if (list_empty(&cache->magazines)) {	356	if (list_empty(&cache->magazines)) {
350	spinlock_unlock(&cache->lock);	357	spinlock_unlock(&cache->maglock);
351	return NULL;	358	return NULL;
352	}	359	}
353	newmag = list_get_instance(cache->magazines.next,	360	newmag = list_get_instance(cache->magazines.next,
354	slab_magazine_t,	361	slab_magazine_t,
355	link);	362	link);
356	list_remove(&newmag->link);	363	list_remove(&newmag->link);
357	spinlock_unlock(&cache->lock);	364	spinlock_unlock(&cache->maglock);
358		365
359	if (lastmag)	366	if (lastmag)
360	slab_free(&mag_cache, lastmag);	367	slab_free(&mag_cache, lastmag);
361	cache->mag_cache[CPU->id].last = cmag;	368	cache->mag_cache[CPU->id].last = cmag;
362	cache->mag_cache[CPU->id].current = newmag;	369	cache->mag_cache[CPU->id].current = newmag;
363	return newmag;	370	return newmag;
364	}	371	}
365		372
366	/**	373	/**
367	* Try to find object in CPU-cache magazines	374	* Try to find object in CPU-cache magazines
368	*	375	*
369	* @return Pointer to object or NULL if not available	376	* @return Pointer to object or NULL if not available
370	*/	377	*/
371	static void * magazine_obj_get(slab_cache_t *cache)	378	static void * magazine_obj_get(slab_cache_t *cache)
372	{	379	{
373	slab_magazine_t *mag;	380	slab_magazine_t *mag;
374	void *obj;	381	void *obj;
375		382
376	if (!CPU)	383	if (!CPU)
377	return NULL;	384	return NULL;
378		385
379	spinlock_lock(&cache->mag_cache[CPU->id].lock);	386	spinlock_lock(&cache->mag_cache[CPU->id].lock);
380		387
381	mag = get_full_current_mag(cache);	388	mag = get_full_current_mag(cache);
382	if (!mag) {	389	if (!mag) {
383	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	390	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
384	return NULL;	391	return NULL;
385	}	392	}
386	obj = mag->objs[--mag->busy];	393	obj = mag->objs[--mag->busy];
387	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	394	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
388	atomic_dec(&cache->cached_objs);	395	atomic_dec(&cache->cached_objs);
389		396
390	return obj;	397	return obj;
391	}	398	}
392		399
393	/**	400	/**
394	* Assure that the current magazine is empty, return pointer to it, or NULL if	401	* Assure that the current magazine is empty, return pointer to it, or NULL if
395	* no empty magazine is available and cannot be allocated	402	* no empty magazine is available and cannot be allocated
396	*	403	*
397	* Assume mag_cache[CPU->id].lock is held	404	* Assume mag_cache[CPU->id].lock is held
398	*	405	*
399	* We have 2 magazines bound to processor.	406	* We have 2 magazines bound to processor.
400	* First try the current.	407	* First try the current.
401	* If full, try the last.	408	* If full, try the last.
402	* If full, put to magazines list.	409	* If full, put to magazines list.
403	* allocate new, exchange last & current	410	* allocate new, exchange last & current
404	*	411	*
405	*/	412	*/
406	static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)	413	static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache)
407	{	414	{
408	slab_magazine_t cmag,lastmag,*newmag;	415	slab_magazine_t cmag,lastmag,*newmag;
409		416
410	cmag = cache->mag_cache[CPU->id].current;	417	cmag = cache->mag_cache[CPU->id].current;
411	lastmag = cache->mag_cache[CPU->id].last;	418	lastmag = cache->mag_cache[CPU->id].last;
412		419
413	if (cmag) {	420	if (cmag) {
414	if (cmag->busy < cmag->size)	421	if (cmag->busy < cmag->size)
415	return cmag;	422	return cmag;
416	if (lastmag && lastmag->busy < lastmag->size) {	423	if (lastmag && lastmag->busy < lastmag->size) {
417	cache->mag_cache[CPU->id].last = cmag;	424	cache->mag_cache[CPU->id].last = cmag;
418	cache->mag_cache[CPU->id].current = lastmag;	425	cache->mag_cache[CPU->id].current = lastmag;
419	return lastmag;	426	return lastmag;
420	}	427	}
421	}	428	}
422	/* current \| last are full \| nonexistent, allocate new */	429	/* current \| last are full \| nonexistent, allocate new */
423	/* We do not want to sleep just because of caching */	430	/* We do not want to sleep just because of caching */
424	/* Especially we do not want reclaiming to start, as	431	/* Especially we do not want reclaiming to start, as
425	* this would deadlock */	432	* this would deadlock */
426	newmag = slab_alloc(&mag_cache, FRAME_ATOMIC \| FRAME_NO_RECLAIM);	433	newmag = slab_alloc(&mag_cache, FRAME_ATOMIC \| FRAME_NO_RECLAIM);
427	if (!newmag)	434	if (!newmag)
428	return NULL;	435	return NULL;
429	newmag->size = SLAB_MAG_SIZE;	436	newmag->size = SLAB_MAG_SIZE;
430	newmag->busy = 0;	437	newmag->busy = 0;
431		438
432	/* Flush last to magazine list */	439	/* Flush last to magazine list */
433	if (lastmag) {	440	if (lastmag) {
434	spinlock_lock(&cache->lock);	441	spinlock_lock(&cache->maglock);
435	list_prepend(&lastmag->link, &cache->magazines);	442	list_prepend(&lastmag->link, &cache->magazines);
436	spinlock_unlock(&cache->lock);	443	spinlock_unlock(&cache->maglock);
437	}	444	}
438	/* Move current as last, save new as current */	445	/* Move current as last, save new as current */
439	cache->mag_cache[CPU->id].last = cmag;	446	cache->mag_cache[CPU->id].last = cmag;
440	cache->mag_cache[CPU->id].current = newmag;	447	cache->mag_cache[CPU->id].current = newmag;
441		448
442	return newmag;	449	return newmag;
443	}	450	}
444		451
445	/**	452	/**
446	* Put object into CPU-cache magazine	453	* Put object into CPU-cache magazine
447	*	454	*
448	* @return 0 - success, -1 - could not get memory	455	* @return 0 - success, -1 - could not get memory
449	*/	456	*/
450	static int magazine_obj_put(slab_cache_t cache, void obj)	457	static int magazine_obj_put(slab_cache_t cache, void obj)
451	{	458	{
452	slab_magazine_t *mag;	459	slab_magazine_t *mag;
453		460
454	if (!CPU)	461	if (!CPU)
455	return -1;	462	return -1;
456		463
457	spinlock_lock(&cache->mag_cache[CPU->id].lock);	464	spinlock_lock(&cache->mag_cache[CPU->id].lock);
458		465
459	mag = make_empty_current_mag(cache);	466	mag = make_empty_current_mag(cache);
460	if (!mag) {	467	if (!mag) {
461	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	468	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
462	return -1;	469	return -1;
463	}	470	}
464		471
465	mag->objs[mag->busy++] = obj;	472	mag->objs[mag->busy++] = obj;
466		473
467	spinlock_unlock(&cache->mag_cache[CPU->id].lock);	474	spinlock_unlock(&cache->mag_cache[CPU->id].lock);
468	atomic_inc(&cache->cached_objs);	475	atomic_inc(&cache->cached_objs);
469	return 0;	476	return 0;
470	}	477	}
471		478
472		479
473	/**************************************/	480	/**************************************/
474	/* SLAB CACHE functions */	481	/* SLAB CACHE functions */
475		482
476	/** Return number of objects that fit in certain cache size */	483	/** Return number of objects that fit in certain cache size */
477	static int comp_objects(slab_cache_t *cache)	484	static int comp_objects(slab_cache_t *cache)
478	{	485	{
479	if (cache->flags & SLAB_CACHE_SLINSIDE)	486	if (cache->flags & SLAB_CACHE_SLINSIDE)
480	return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;	487	return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size;
481	else	488	else
482	return (PAGE_SIZE << cache->order) / cache->size;	489	return (PAGE_SIZE << cache->order) / cache->size;
483	}	490	}
484		491
485	/** Return wasted space in slab */	492	/** Return wasted space in slab */

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/mm/slab.c @ 1780 – Rev 775 → 776