Subversion Repositories c0or1k

/*

 * Bitmap-based linked-listable fixed-size memory cache.

 *

 * Copyright (C) 2007 Bahadir Balban

 */

#include <l4/lib/memcache.h>

#include <l4/lib/string.h>

#include <l4/lib/printk.h>

#include INC_GLUE(memory.h)

#include <l4/lib/bit.h>

#include <l4/api/errno.h>

/* Allocate, clear and return element */

void *mem_cache_zalloc(struct mem_cache *cache)

{

        void *elem = mem_cache_alloc(cache);

        memset(elem, 0, cache->struct_size);

        return elem;

}

/* Allocate another element from given @cache. Returns 0 when full. */

void *mem_cache_alloc(struct mem_cache *cache)

{

        int bit;

        int err;

        if (cache->free > 0) {

                if ((err = mutex_lock(&cache->mutex)) < 0)

                        return PTR_ERR(err);    /* Interruptible mutex */

                cache->free--;

                if ((bit = find_and_set_first_free_bit(cache->bitmap,

                                                       cache->total)) < 0) {

                        printk("Error: Anomaly in cache occupied state.\n"

                               "Bitmap full although cache->free > 0\n");

                        BUG();

                }

                mutex_unlock(&cache->mutex);

                return (void *)(cache->start + (cache->struct_size * bit));

        } else {

                /* Cache full */

                return 0;

        }

}

/* Free element at @addr in @cache. Return negative on error. */

int mem_cache_free(struct mem_cache *cache, void *addr)

{

        unsigned int struct_addr = (unsigned int)addr;

        unsigned int bit;

        int err = 0;

        /* Check boundary */

        if (struct_addr < cache->start || struct_addr > cache->end)

                return -1; /* Address doesn't belong to cache */

        bit = ((struct_addr - cache->start) / cache->struct_size);

        /*

         * Check alignment:

         * Find out if there was a lost remainder in last division.

         * There shouldn't have been, because addresses are allocated at

         * struct_size offsets from cache->start.

         */

        if (((bit * cache->struct_size) + cache->start) != struct_addr) {

                printk("Error: This address is not aligned on a predefined "

                       "structure address in this cache.\n");

                err = -1;

                return err;

        }

        if ((err = mutex_lock(&cache->mutex)) < 0)

                return err; /* Interruptible mutex */

        /* Check free/occupied state */

        if (check_and_clear_bit(cache->bitmap, bit) < 0) {

                printk("Error: Anomaly in cache occupied state:\n"

                       "Trying to free already free structure.\n");

                err = -1;

                goto out;

        }

        cache->free++;

        if (cache->free > cache->total) {

                printk("Error: Anomaly in cache occupied state:\n"

                       "More free elements than total.\n");

                err = -1;

                goto out;

        }

out:

        mutex_unlock(&cache->mutex);

        return err;

}

/*

 * Given a buffer start address, structure size, number of

 * structs and alignment requirements, determines how much

 * memory is needed from that starting address

 */

int mem_cache_bufsize(void *start, int struct_size, int nstructs, int aligned)

{

        unsigned long start_address = (unsigned long)start;

        int total_bytes, bwords, bitmap_size;

        /* Word alignment requirement */

        start_address = align_up(start_address, sizeof(int));

        /* Total bytes to contain structures */

        total_bytes = struct_size * nstructs;

        /* Total words to contain bitmap */

        bwords = nstructs >> 5;

        /* An extra word if not a multiple of one word's bits */

        if (nstructs & 0x1F)

                bwords++;

        /* Total bitmap bytes */

        bitmap_size = bwords * sizeof(int);

        /* Current would-be start address */

        start_address += bitmap_size + total_bytes + sizeof(struct mem_cache);

        /* Check alignment requirement */

        if (aligned)

                start_address = align_up(start_address, struct_size);

        return start_address - (unsigned long)start;

}

struct mem_cache *mem_cache_init(void *bufstart, int cache_size,

                                 int struct_size, unsigned int aligned)

{

        void *start;

        struct mem_cache *cache;

        unsigned int area_start;

        unsigned int *bitmap;

        int bwords, total, bsize;

        /* Align to nearest word boundary */

        start = (void *)align_up(bufstart, sizeof(int));

        cache_size -= (int)start - (int)bufstart;

        cache = start;

        if ((struct_size < 0) || (cache_size < 0) ||

            ((unsigned long)start == ~(0))) {

                printk("Invalid parameters.\n");

                return 0;

        }

        /*

         * The cache definition itself is at the beginning.

         * Skipping it to get to start of free memory. i.e. the cache.

         */

        area_start = (unsigned long)start + sizeof(struct mem_cache);

        cache_size -= sizeof(struct mem_cache);

        if (cache_size < struct_size) {

                printk("Cache too small for given struct_size\n");

                return 0;

        }

        /* Get how much bitmap words occupy */

        total = cache_size / struct_size;

        bwords = total >> 5;    /* Divide by 32 */

        if (total & 0x1F) {     /* Remainder? */

                bwords++;       /* Add one more word for remainder */

        }

        bsize = bwords * 4;

        /* Reduce bitmap bytes from cache size */

        cache_size -= bsize;

        /* Recalculate total - it may or may not have changed */

        total = cache_size / struct_size;

        /* This should always catch too small caches */

        if (total <= 0) {

                printk("Cache too small for given struct_size\n");

                return 0;

        }

        if (cache_size <= 0) {

                printk("Cache too small for given struct_size\n");

                return 0;

        }

        bitmap = (unsigned int *)area_start;

        area_start = (unsigned int)(bitmap + bwords);

        if (aligned) {

                unsigned int addr = area_start;

                unsigned int addr_aligned = align_up(area_start, struct_size);

                unsigned int diff = addr_aligned - addr;

                BUG_ON(diff >= struct_size);

                cache_size -= diff;

                /* Recalculate total */

                total = cache_size / struct_size;

                area_start = addr_aligned;

        }

        link_init(&cache->list);

        cache->start = area_start;

        cache->end = area_start + cache_size;

        cache->total = total;

        cache->free = cache->total;

        cache->struct_size = struct_size;

        cache->bitmap = bitmap;

        mutex_init(&cache->mutex);

        memset(cache->bitmap, 0, bwords*SZ_WORD);

        return cache;

}