URL https://opencores.org/ocsvn/or1k_soc_on_altera_embedded_dev_kit/or1k_soc_on_altera_embedded_dev_kit/trunk

Subversion Repositories or1k_soc_on_altera_embedded_dev_kit

[/] [or1k_soc_on_altera_embedded_dev_kit/] [trunk/] [linux-2.6/] [linux-2.6.24/] [arch/] [powerpc/] [lib/] [rheap.c] - Blame information for rev 3

Details | Compare with Previous | View Log


/*
 * A Remote Heap.  Remote means that we don't touch the memory that the
 * heap points to. Normal heap implementations use the memory they manage
 * to place their list. We cannot do that because the memory we manage may
 * have special properties, for example it is uncachable or of different
 * endianess.
 *
 * Author: Pantelis Antoniou <panto@intracom.gr>
 *
 * 2004 (c) INTRACOM S.A. Greece. This file is licensed under
 * the terms of the GNU General Public License version 2. This program
 * is licensed "as is" without any warranty of any kind, whether express
 * or implied.
 */
#include <linux/types.h>
#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mm.h>
#include <linux/err.h>
#include <linux/slab.h>
 
#include <asm/rheap.h>
 
/*
 * Fixup a list_head, needed when copying lists.  If the pointers fall
 * between s and e, apply the delta.  This assumes that
 * sizeof(struct list_head *) == sizeof(unsigned long *).
 */
static inline void fixup(unsigned long s, unsigned long e, int d,
                         struct list_head *l)
{
        unsigned long *pp;
 
        pp = (unsigned long *)&l->next;
        if (*pp >= s && *pp < e)
                *pp += d;
 
        pp = (unsigned long *)&l->prev;
        if (*pp >= s && *pp < e)
                *pp += d;
}
 
/* Grow the allocated blocks */
static int grow(rh_info_t * info, int max_blocks)
{
        rh_block_t *block, *blk;
        int i, new_blocks;
        int delta;
        unsigned long blks, blke;
 
        if (max_blocks <= info->max_blocks)
                return -EINVAL;
 
        new_blocks = max_blocks - info->max_blocks;
 
        block = kmalloc(sizeof(rh_block_t) * max_blocks, GFP_KERNEL);
        if (block == NULL)
                return -ENOMEM;
 
        if (info->max_blocks > 0) {
 
                /* copy old block area */
                memcpy(block, info->block,
                       sizeof(rh_block_t) * info->max_blocks);
 
                delta = (char *)block - (char *)info->block;
 
                /* and fixup list pointers */
                blks = (unsigned long)info->block;
                blke = (unsigned long)(info->block + info->max_blocks);
 
                for (i = 0, blk = block; i < info->max_blocks; i++, blk++)
                        fixup(blks, blke, delta, &blk->list);
 
                fixup(blks, blke, delta, &info->empty_list);
                fixup(blks, blke, delta, &info->free_list);
                fixup(blks, blke, delta, &info->taken_list);
 
                /* free the old allocated memory */
                if ((info->flags & RHIF_STATIC_BLOCK) == 0)
                        kfree(info->block);
        }
 
        info->block = block;
        info->empty_slots += new_blocks;
        info->max_blocks = max_blocks;
        info->flags &= ~RHIF_STATIC_BLOCK;
 
        /* add all new blocks to the free list */
        blk = block + info->max_blocks - new_blocks;
        for (i = 0; i < new_blocks; i++, blk++)
                list_add(&blk->list, &info->empty_list);
 
        return 0;
}
 
/*
 * Assure at least the required amount of empty slots.  If this function
 * causes a grow in the block area then all pointers kept to the block
 * area are invalid!
 */
static int assure_empty(rh_info_t * info, int slots)
{
        int max_blocks;
 
        /* This function is not meant to be used to grow uncontrollably */
        if (slots >= 4)
                return -EINVAL;
 
        /* Enough space */
        if (info->empty_slots >= slots)
                return 0;
 
        /* Next 16 sized block */
        max_blocks = ((info->max_blocks + slots) + 15) & ~15;
 
        return grow(info, max_blocks);
}
 
static rh_block_t *get_slot(rh_info_t * info)
{
        rh_block_t *blk;
 
        /* If no more free slots, and failure to extend. */
        /* XXX: You should have called assure_empty before */
        if (info->empty_slots == 0) {
                printk(KERN_ERR "rh: out of slots; crash is imminent.\n");
                return NULL;
        }
 
        /* Get empty slot to use */
        blk = list_entry(info->empty_list.next, rh_block_t, list);
        list_del_init(&blk->list);
        info->empty_slots--;
 
        /* Initialize */
        blk->start = 0;
        blk->size = 0;
        blk->owner = NULL;
 
        return blk;
}
 
static inline void release_slot(rh_info_t * info, rh_block_t * blk)
{
        list_add(&blk->list, &info->empty_list);
        info->empty_slots++;
}
 
static void attach_free_block(rh_info_t * info, rh_block_t * blkn)
{
        rh_block_t *blk;
        rh_block_t *before;
        rh_block_t *after;
        rh_block_t *next;
        int size;
        unsigned long s, e, bs, be;
        struct list_head *l;
 
        /* We assume that they are aligned properly */
        size = blkn->size;
        s = blkn->start;
        e = s + size;
 
        /* Find the blocks immediately before and after the given one
         * (if any) */
        before = NULL;
        after = NULL;
        next = NULL;
 
        list_for_each(l, &info->free_list) {
                blk = list_entry(l, rh_block_t, list);
 
                bs = blk->start;
                be = bs + blk->size;
 
                if (next == NULL && s >= bs)
                        next = blk;
 
                if (be == s)
                        before = blk;
 
                if (e == bs)
                        after = blk;
 
                /* If both are not null, break now */
                if (before != NULL && after != NULL)
                        break;
        }
 
        /* Now check if they are really adjacent */
        if (before && s != (before->start + before->size))
                before = NULL;
 
        if (after && e != after->start)
                after = NULL;
 
        /* No coalescing; list insert and return */
        if (before == NULL && after == NULL) {
 
                if (next != NULL)
                        list_add(&blkn->list, &next->list);
                else
                        list_add(&blkn->list, &info->free_list);
 
                return;
        }
 
        /* We don't need it anymore */
        release_slot(info, blkn);
 
        /* Grow the before block */
        if (before != NULL && after == NULL) {
                before->size += size;
                return;
        }
 
        /* Grow the after block backwards */
        if (before == NULL && after != NULL) {
                after->start -= size;
                after->size += size;
                return;
        }
 
        /* Grow the before block, and release the after block */
        before->size += size + after->size;
        list_del(&after->list);
        release_slot(info, after);
}
 
static void attach_taken_block(rh_info_t * info, rh_block_t * blkn)
{
        rh_block_t *blk;
        struct list_head *l;
 
        /* Find the block immediately before the given one (if any) */
        list_for_each(l, &info->taken_list) {
                blk = list_entry(l, rh_block_t, list);
                if (blk->start > blkn->start) {
                        list_add_tail(&blkn->list, &blk->list);
                        return;
                }
        }
 
        list_add_tail(&blkn->list, &info->taken_list);
}
 
/*
 * Create a remote heap dynamically.  Note that no memory for the blocks
 * are allocated.  It will upon the first allocation
 */
rh_info_t *rh_create(unsigned int alignment)
{
        rh_info_t *info;
 
        /* Alignment must be a power of two */
        if ((alignment & (alignment - 1)) != 0)
                return ERR_PTR(-EINVAL);
 
        info = kmalloc(sizeof(*info), GFP_KERNEL);
        if (info == NULL)
                return ERR_PTR(-ENOMEM);
 
        info->alignment = alignment;
 
        /* Initially everything as empty */
        info->block = NULL;
        info->max_blocks = 0;
        info->empty_slots = 0;
        info->flags = 0;
 
        INIT_LIST_HEAD(&info->empty_list);
        INIT_LIST_HEAD(&info->free_list);
        INIT_LIST_HEAD(&info->taken_list);
 
        return info;
}
EXPORT_SYMBOL_GPL(rh_create);
 
/*
 * Destroy a dynamically created remote heap.  Deallocate only if the areas
 * are not static
 */
void rh_destroy(rh_info_t * info)
{
        if ((info->flags & RHIF_STATIC_BLOCK) == 0 && info->block != NULL)
                kfree(info->block);
 
        if ((info->flags & RHIF_STATIC_INFO) == 0)
                kfree(info);
}
EXPORT_SYMBOL_GPL(rh_destroy);
 
/*
 * Initialize in place a remote heap info block.  This is needed to support
 * operation very early in the startup of the kernel, when it is not yet safe
 * to call kmalloc.
 */
void rh_init(rh_info_t * info, unsigned int alignment, int max_blocks,
             rh_block_t * block)
{
        int i;
        rh_block_t *blk;
 
        /* Alignment must be a power of two */
        if ((alignment & (alignment - 1)) != 0)
                return;
 
        info->alignment = alignment;
 
        /* Initially everything as empty */
        info->block = block;
        info->max_blocks = max_blocks;
        info->empty_slots = max_blocks;
        info->flags = RHIF_STATIC_INFO | RHIF_STATIC_BLOCK;
 
        INIT_LIST_HEAD(&info->empty_list);
        INIT_LIST_HEAD(&info->free_list);
        INIT_LIST_HEAD(&info->taken_list);
 
        /* Add all new blocks to the free list */
        for (i = 0, blk = block; i < max_blocks; i++, blk++)
                list_add(&blk->list, &info->empty_list);
}
EXPORT_SYMBOL_GPL(rh_init);
 
/* Attach a free memory region, coalesces regions if adjuscent */
int rh_attach_region(rh_info_t * info, unsigned long start, int size)
{
        rh_block_t *blk;
        unsigned long s, e, m;
        int r;
 
        /* The region must be aligned */
        s = start;
        e = s + size;
        m = info->alignment - 1;
 
        /* Round start up */
        s = (s + m) & ~m;
 
        /* Round end down */
        e = e & ~m;
 
        if (IS_ERR_VALUE(e) || (e < s))
                return -ERANGE;
 
        /* Take final values */
        start = s;
        size = e - s;
 
        /* Grow the blocks, if needed */
        r = assure_empty(info, 1);
        if (r < 0)
                return r;
 
        blk = get_slot(info);
        blk->start = start;
        blk->size = size;
        blk->owner = NULL;
 
        attach_free_block(info, blk);
 
        return 0;
}
EXPORT_SYMBOL_GPL(rh_attach_region);
 
/* Detatch given address range, splits free block if needed. */
unsigned long rh_detach_region(rh_info_t * info, unsigned long start, int size)
{
        struct list_head *l;
        rh_block_t *blk, *newblk;
        unsigned long s, e, m, bs, be;
 
        /* Validate size */
        if (size <= 0)
                return (unsigned long) -EINVAL;
 
        /* The region must be aligned */
        s = start;
        e = s + size;
        m = info->alignment - 1;
 
        /* Round start up */
        s = (s + m) & ~m;
 
        /* Round end down */
        e = e & ~m;
 
        if (assure_empty(info, 1) < 0)
                return (unsigned long) -ENOMEM;
 
        blk = NULL;
        list_for_each(l, &info->free_list) {
                blk = list_entry(l, rh_block_t, list);
                /* The range must lie entirely inside one free block */
                bs = blk->start;
                be = blk->start + blk->size;
                if (s >= bs && e <= be)
                        break;
                blk = NULL;
        }
 
        if (blk == NULL)
                return (unsigned long) -ENOMEM;
 
        /* Perfect fit */
        if (bs == s && be == e) {
                /* Delete from free list, release slot */
                list_del(&blk->list);
                release_slot(info, blk);
                return s;
        }
 
        /* blk still in free list, with updated start and/or size */
        if (bs == s || be == e) {
                if (bs == s)
                        blk->start += size;
                blk->size -= size;
 
        } else {
                /* The front free fragment */
                blk->size = s - bs;
 
                /* the back free fragment */
                newblk = get_slot(info);
                newblk->start = e;
                newblk->size = be - e;
 
                list_add(&newblk->list, &blk->list);
        }
 
        return s;
}
EXPORT_SYMBOL_GPL(rh_detach_region);
 
/* Allocate a block of memory at the specified alignment.  The value returned
 * is an offset into the buffer initialized by rh_init(), or a negative number
 * if there is an error.
 */
unsigned long rh_alloc_align(rh_info_t * info, int size, int alignment, const char *owner)
{
        struct list_head *l;
        rh_block_t *blk;
        rh_block_t *newblk;
        unsigned long start, sp_size;
 
        /* Validate size, and alignment must be power of two */
        if (size <= 0 || (alignment & (alignment - 1)) != 0)
                return (unsigned long) -EINVAL;
 
        /* Align to configured alignment */
        size = (size + (info->alignment - 1)) & ~(info->alignment - 1);
 
        if (assure_empty(info, 2) < 0)
                return (unsigned long) -ENOMEM;
 
        blk = NULL;
        list_for_each(l, &info->free_list) {
                blk = list_entry(l, rh_block_t, list);
                if (size <= blk->size) {
                        start = (blk->start + alignment - 1) & ~(alignment - 1);
                        if (start + size <= blk->start + blk->size)
                                break;
                }
                blk = NULL;
        }
 
        if (blk == NULL)
                return (unsigned long) -ENOMEM;
 
        /* Just fits */
        if (blk->size == size) {
                /* Move from free list to taken list */
                list_del(&blk->list);
                newblk = blk;
        } else {
                /* Fragment caused, split if needed */
                /* Create block for fragment in the beginning */
                sp_size = start - blk->start;
                if (sp_size) {
                        rh_block_t *spblk;
 
                        spblk = get_slot(info);
                        spblk->start = blk->start;
                        spblk->size = sp_size;
                        /* add before the blk */
                        list_add(&spblk->list, blk->list.prev);
                }
                newblk = get_slot(info);
                newblk->start = start;
                newblk->size = size;
 
                /* blk still in free list, with updated start and size
                 * for fragment in the end */
                blk->start = start + size;
                blk->size -= sp_size + size;
                /* No fragment in the end, remove blk */
                if (blk->size == 0) {
                        list_del(&blk->list);
                        release_slot(info, blk);
                }
        }
 
        newblk->owner = owner;
        attach_taken_block(info, newblk);
 
        return start;
}
EXPORT_SYMBOL_GPL(rh_alloc_align);
 
/* Allocate a block of memory at the default alignment.  The value returned is
 * an offset into the buffer initialized by rh_init(), or a negative number if
 * there is an error.
 */
unsigned long rh_alloc(rh_info_t * info, int size, const char *owner)
{
        return rh_alloc_align(info, size, info->alignment, owner);
}
EXPORT_SYMBOL_GPL(rh_alloc);
 
/* Allocate a block of memory at the given offset, rounded up to the default
 * alignment.  The value returned is an offset into the buffer initialized by
 * rh_init(), or a negative number if there is an error.
 */
unsigned long rh_alloc_fixed(rh_info_t * info, unsigned long start, int size, const char *owner)
{
        struct list_head *l;
        rh_block_t *blk, *newblk1, *newblk2;
        unsigned long s, e, m, bs = 0, be = 0;
 
        /* Validate size */
        if (size <= 0)
                return (unsigned long) -EINVAL;
 
        /* The region must be aligned */
        s = start;
        e = s + size;
        m = info->alignment - 1;
 
        /* Round start up */
        s = (s + m) & ~m;
 
        /* Round end down */
        e = e & ~m;
 
        if (assure_empty(info, 2) < 0)
                return (unsigned long) -ENOMEM;
 
        blk = NULL;
        list_for_each(l, &info->free_list) {
                blk = list_entry(l, rh_block_t, list);
                /* The range must lie entirely inside one free block */
                bs = blk->start;
                be = blk->start + blk->size;
                if (s >= bs && e <= be)
                        break;
        }
 
        if (blk == NULL)
                return (unsigned long) -ENOMEM;
 
        /* Perfect fit */
        if (bs == s && be == e) {
                /* Move from free list to taken list */
                list_del(&blk->list);
                blk->owner = owner;
 
                start = blk->start;
                attach_taken_block(info, blk);
 
                return start;
 
        }
 
        /* blk still in free list, with updated start and/or size */
        if (bs == s || be == e) {
                if (bs == s)
                        blk->start += size;
                blk->size -= size;
 
        } else {
                /* The front free fragment */
                blk->size = s - bs;
 
                /* The back free fragment */
                newblk2 = get_slot(info);
                newblk2->start = e;
                newblk2->size = be - e;
 
                list_add(&newblk2->list, &blk->list);
        }
 
        newblk1 = get_slot(info);
        newblk1->start = s;
        newblk1->size = e - s;
        newblk1->owner = owner;
 
        start = newblk1->start;
        attach_taken_block(info, newblk1);
 
        return start;
}
EXPORT_SYMBOL_GPL(rh_alloc_fixed);
 
/* Deallocate the memory previously allocated by one of the rh_alloc functions.
 * The return value is the size of the deallocated block, or a negative number
 * if there is an error.
 */
int rh_free(rh_info_t * info, unsigned long start)
{
        rh_block_t *blk, *blk2;
        struct list_head *l;
        int size;
 
        /* Linear search for block */
        blk = NULL;
        list_for_each(l, &info->taken_list) {
                blk2 = list_entry(l, rh_block_t, list);
                if (start < blk2->start)
                        break;
                blk = blk2;
        }
 
        if (blk == NULL || start > (blk->start + blk->size))
                return -EINVAL;
 
        /* Remove from taken list */
        list_del(&blk->list);
 
        /* Get size of freed block */
        size = blk->size;
        attach_free_block(info, blk);
 
        return size;
}
EXPORT_SYMBOL_GPL(rh_free);
 
int rh_get_stats(rh_info_t * info, int what, int max_stats, rh_stats_t * stats)
{
        rh_block_t *blk;
        struct list_head *l;
        struct list_head *h;
        int nr;
 
        switch (what) {
 
        case RHGS_FREE:
                h = &info->free_list;
                break;
 
        case RHGS_TAKEN:
                h = &info->taken_list;
                break;
 
        default:
                return -EINVAL;
        }
 
        /* Linear search for block */
        nr = 0;
        list_for_each(l, h) {
                blk = list_entry(l, rh_block_t, list);
                if (stats != NULL && nr < max_stats) {
                        stats->start = blk->start;
                        stats->size = blk->size;
                        stats->owner = blk->owner;
                        stats++;
                }
                nr++;
        }
 
        return nr;
}
EXPORT_SYMBOL_GPL(rh_get_stats);
 
int rh_set_owner(rh_info_t * info, unsigned long start, const char *owner)
{
        rh_block_t *blk, *blk2;
        struct list_head *l;
        int size;
 
        /* Linear search for block */
        blk = NULL;
        list_for_each(l, &info->taken_list) {
                blk2 = list_entry(l, rh_block_t, list);
                if (start < blk2->start)
                        break;
                blk = blk2;
        }
 
        if (blk == NULL || start > (blk->start + blk->size))
                return -EINVAL;
 
        blk->owner = owner;
        size = blk->size;
 
        return size;
}
EXPORT_SYMBOL_GPL(rh_set_owner);
 
void rh_dump(rh_info_t * info)
{
        static rh_stats_t st[32];       /* XXX maximum 32 blocks */
        int maxnr;
        int i, nr;
 
        maxnr = ARRAY_SIZE(st);
 
        printk(KERN_INFO
               "info @0x%p (%d slots empty / %d max)\n",
               info, info->empty_slots, info->max_blocks);
 
        printk(KERN_INFO "  Free:\n");
        nr = rh_get_stats(info, RHGS_FREE, maxnr, st);
        if (nr > maxnr)
                nr = maxnr;
        for (i = 0; i < nr; i++)
                printk(KERN_INFO
                       "    0x%lx-0x%lx (%u)\n",
                       st[i].start, st[i].start + st[i].size,
                       st[i].size);
        printk(KERN_INFO "\n");
 
        printk(KERN_INFO "  Taken:\n");
        nr = rh_get_stats(info, RHGS_TAKEN, maxnr, st);
        if (nr > maxnr)
                nr = maxnr;
        for (i = 0; i < nr; i++)
                printk(KERN_INFO
                       "    0x%lx-0x%lx (%u) %s\n",
                       st[i].start, st[i].start + st[i].size,
                       st[i].size, st[i].owner != NULL ? st[i].owner : "");
        printk(KERN_INFO "\n");
}
EXPORT_SYMBOL_GPL(rh_dump);
 
void rh_dump_blk(rh_info_t * info, rh_block_t * blk)
{
        printk(KERN_INFO
               "blk @0x%p: 0x%lx-0x%lx (%u)\n",
               blk, blk->start, blk->start + blk->size, blk->size);
}
EXPORT_SYMBOL_GPL(rh_dump_blk);
 

Browse

Tools

Subversion Repositories or1k_soc_on_altera_embedded_dev_kit

[/] [or1k_soc_on_altera_embedded_dev_kit/] [trunk/] [linux-2.6/] [linux-2.6.24/] [arch/] [powerpc/] [lib/] [rheap.c] - Blame information for rev 3

Line No.	Rev	Author	Line
1	3	xianfeng	`/*`
2			`* A Remote Heap. Remote means that we don't touch the memory that the`
3			`* heap points to. Normal heap implementations use the memory they manage`
4			`* to place their list. We cannot do that because the memory we manage may`
5			`* have special properties, for example it is uncachable or of different`
6			`* endianess.`
7			`*`
8			`* Author: Pantelis Antoniou <panto@intracom.gr>`
9			`*`
10			`* 2004 (c) INTRACOM S.A. Greece. This file is licensed under`
11			`* the terms of the GNU General Public License version 2. This program`
12			`* is licensed "as is" without any warranty of any kind, whether express`
13			`* or implied.`
14			`*/`
15			`#include <linux/types.h>`
16			`#include <linux/errno.h>`
17			`#include <linux/kernel.h>`
18			`#include <linux/module.h>`
19			`#include <linux/mm.h>`
20			`#include <linux/err.h>`
21			`#include <linux/slab.h>`
22
23			`#include <asm/rheap.h>`
24
25			`/*`
26			`* Fixup a list_head, needed when copying lists. If the pointers fall`
27			`* between s and e, apply the delta. This assumes that`
28			`* sizeof(struct list_head ) == sizeof(unsigned long ).`
29			`*/`
30			`static inline void fixup(unsigned long s, unsigned long e, int d,`
31			`struct list_head *l)`
32			`{`
33			`unsigned long *pp;`
34
35			`pp = (unsigned long *)&l->next;`
36			`if (pp >= s && pp < e)`
37			`*pp += d;`
38
39			`pp = (unsigned long *)&l->prev;`
40			`if (pp >= s && pp < e)`
41			`*pp += d;`
42			`}`
43
44			`/* Grow the allocated blocks */`
45			`static int grow(rh_info_t * info, int max_blocks)`
46			`{`
47			`rh_block_t block, blk;`
48			`int i, new_blocks;`
49			`int delta;`
50			`unsigned long blks, blke;`
51
52			`if (max_blocks <= info->max_blocks)`
53			`return -EINVAL;`
54
55			`new_blocks = max_blocks - info->max_blocks;`
56
57			`block = kmalloc(sizeof(rh_block_t) * max_blocks, GFP_KERNEL);`
58			`if (block == NULL)`
59			`return -ENOMEM;`
60
61			`if (info->max_blocks > 0) {`
62
63			`/* copy old block area */`
64			`memcpy(block, info->block,`
65			`sizeof(rh_block_t) * info->max_blocks);`
66
67			`delta = (char )block - (char )info->block;`
68
69			`/* and fixup list pointers */`
70			`blks = (unsigned long)info->block;`
71			`blke = (unsigned long)(info->block + info->max_blocks);`
72
73			`for (i = 0, blk = block; i < info->max_blocks; i++, blk++)`
74			`fixup(blks, blke, delta, &blk->list);`
75
76			`fixup(blks, blke, delta, &info->empty_list);`
77			`fixup(blks, blke, delta, &info->free_list);`
78			`fixup(blks, blke, delta, &info->taken_list);`
79
80			`/* free the old allocated memory */`
81			`if ((info->flags & RHIF_STATIC_BLOCK) == 0)`
82			`kfree(info->block);`
83			`}`
84
85			`info->block = block;`
86			`info->empty_slots += new_blocks;`
87			`info->max_blocks = max_blocks;`
88			`info->flags &= ~RHIF_STATIC_BLOCK;`
89
90			`/* add all new blocks to the free list */`
91			`blk = block + info->max_blocks - new_blocks;`
92			`for (i = 0; i < new_blocks; i++, blk++)`
93			`list_add(&blk->list, &info->empty_list);`
94
95			`return 0;`
96			`}`
97
98			`/*`
99			`* Assure at least the required amount of empty slots. If this function`
100			`* causes a grow in the block area then all pointers kept to the block`
101			`* area are invalid!`
102			`*/`
103			`static int assure_empty(rh_info_t * info, int slots)`
104			`{`
105			`int max_blocks;`
106
107			`/* This function is not meant to be used to grow uncontrollably */`
108			`if (slots >= 4)`
109			`return -EINVAL;`
110
111			`/* Enough space */`
112			`if (info->empty_slots >= slots)`
113			`return 0;`
114
115			`/* Next 16 sized block */`
116			`max_blocks = ((info->max_blocks + slots) + 15) & ~15;`
117
118			`return grow(info, max_blocks);`
119			`}`
120
121			`static rh_block_t get_slot(rh_info_t info)`
122			`{`
123			`rh_block_t *blk;`
124
125			`/* If no more free slots, and failure to extend. */`
126			`/* XXX: You should have called assure_empty before */`
127			`if (info->empty_slots == 0) {`
128			`printk(KERN_ERR "rh: out of slots; crash is imminent.\n");`
129			`return NULL;`
130			`}`
131
132			`/* Get empty slot to use */`
133			`blk = list_entry(info->empty_list.next, rh_block_t, list);`
134			`list_del_init(&blk->list);`
135			`info->empty_slots--;`
136
137			`/* Initialize */`
138			`blk->start = 0;`
139			`blk->size = 0;`
140			`blk->owner = NULL;`
141
142			`return blk;`
143			`}`
144
145			`static inline void release_slot(rh_info_t * info, rh_block_t * blk)`
146			`{`
147			`list_add(&blk->list, &info->empty_list);`
148			`info->empty_slots++;`
149			`}`
150
151			`static void attach_free_block(rh_info_t * info, rh_block_t * blkn)`
152			`{`
153			`rh_block_t *blk;`
154			`rh_block_t *before;`
155			`rh_block_t *after;`
156			`rh_block_t *next;`
157			`int size;`
158			`unsigned long s, e, bs, be;`
159			`struct list_head *l;`
160
161			`/* We assume that they are aligned properly */`
162			`size = blkn->size;`
163			`s = blkn->start;`
164			`e = s + size;`
165
166			`/* Find the blocks immediately before and after the given one`
167			`* (if any) */`
168			`before = NULL;`
169			`after = NULL;`
170			`next = NULL;`
171
172			`list_for_each(l, &info->free_list) {`
173			`blk = list_entry(l, rh_block_t, list);`
174
175			`bs = blk->start;`
176			`be = bs + blk->size;`
177
178			`if (next == NULL && s >= bs)`
179			`next = blk;`
180
181			`if (be == s)`
182			`before = blk;`
183
184			`if (e == bs)`
185			`after = blk;`
186
187			`/* If both are not null, break now */`
188			`if (before != NULL && after != NULL)`
189			`break;`
190			`}`
191
192			`/* Now check if they are really adjacent */`
193			`if (before && s != (before->start + before->size))`
194			`before = NULL;`
195
196			`if (after && e != after->start)`
197			`after = NULL;`
198
199			`/* No coalescing; list insert and return */`
200			`if (before == NULL && after == NULL) {`
201
202			`if (next != NULL)`
203			`list_add(&blkn->list, &next->list);`
204			`else`
205			`list_add(&blkn->list, &info->free_list);`
206
207			`return;`
208			`}`
209
210			`/* We don't need it anymore */`
211			`release_slot(info, blkn);`
212
213			`/* Grow the before block */`
214			`if (before != NULL && after == NULL) {`
215			`before->size += size;`
216			`return;`
217			`}`
218
219			`/* Grow the after block backwards */`
220			`if (before == NULL && after != NULL) {`
221			`after->start -= size;`
222			`after->size += size;`
223			`return;`
224			`}`
225
226			`/* Grow the before block, and release the after block */`
227			`before->size += size + after->size;`
228			`list_del(&after->list);`
229			`release_slot(info, after);`
230			`}`
231
232			`static void attach_taken_block(rh_info_t * info, rh_block_t * blkn)`
233			`{`
234			`rh_block_t *blk;`
235			`struct list_head *l;`
236
237			`/* Find the block immediately before the given one (if any) */`
238			`list_for_each(l, &info->taken_list) {`
239			`blk = list_entry(l, rh_block_t, list);`
240			`if (blk->start > blkn->start) {`
241			`list_add_tail(&blkn->list, &blk->list);`
242			`return;`
243			`}`
244			`}`
245
246			`list_add_tail(&blkn->list, &info->taken_list);`
247			`}`
248
249			`/*`
250			`* Create a remote heap dynamically. Note that no memory for the blocks`
251			`* are allocated. It will upon the first allocation`
252			`*/`
253			`rh_info_t *rh_create(unsigned int alignment)`
254			`{`
255			`rh_info_t *info;`
256
257			`/* Alignment must be a power of two */`
258			`if ((alignment & (alignment - 1)) != 0)`
259			`return ERR_PTR(-EINVAL);`
260
261			`info = kmalloc(sizeof(*info), GFP_KERNEL);`
262			`if (info == NULL)`
263			`return ERR_PTR(-ENOMEM);`
264
265			`info->alignment = alignment;`
266
267			`/* Initially everything as empty */`
268			`info->block = NULL;`
269			`info->max_blocks = 0;`
270			`info->empty_slots = 0;`
271			`info->flags = 0;`
272
273			`INIT_LIST_HEAD(&info->empty_list);`
274			`INIT_LIST_HEAD(&info->free_list);`
275			`INIT_LIST_HEAD(&info->taken_list);`
276
277			`return info;`
278			`}`
279			`EXPORT_SYMBOL_GPL(rh_create);`
280
281			`/*`
282			`* Destroy a dynamically created remote heap. Deallocate only if the areas`
283			`* are not static`
284			`*/`
285			`void rh_destroy(rh_info_t * info)`
286			`{`
287			`if ((info->flags & RHIF_STATIC_BLOCK) == 0 && info->block != NULL)`
288			`kfree(info->block);`
289
290			`if ((info->flags & RHIF_STATIC_INFO) == 0)`
291			`kfree(info);`
292			`}`
293			`EXPORT_SYMBOL_GPL(rh_destroy);`
294
295			`/*`
296			`* Initialize in place a remote heap info block. This is needed to support`
297			`* operation very early in the startup of the kernel, when it is not yet safe`
298			`* to call kmalloc.`
299			`*/`
300			`void rh_init(rh_info_t * info, unsigned int alignment, int max_blocks,`
301			`rh_block_t * block)`
302			`{`
303			`int i;`
304			`rh_block_t *blk;`
305
306			`/* Alignment must be a power of two */`
307			`if ((alignment & (alignment - 1)) != 0)`
308			`return;`
309
310			`info->alignment = alignment;`
311
312			`/* Initially everything as empty */`
313			`info->block = block;`
314			`info->max_blocks = max_blocks;`
315			`info->empty_slots = max_blocks;`
316			`info->flags = RHIF_STATIC_INFO \| RHIF_STATIC_BLOCK;`
317
318			`INIT_LIST_HEAD(&info->empty_list);`
319			`INIT_LIST_HEAD(&info->free_list);`
320			`INIT_LIST_HEAD(&info->taken_list);`
321
322			`/* Add all new blocks to the free list */`
323			`for (i = 0, blk = block; i < max_blocks; i++, blk++)`
324			`list_add(&blk->list, &info->empty_list);`
325			`}`
326			`EXPORT_SYMBOL_GPL(rh_init);`
327
328			`/* Attach a free memory region, coalesces regions if adjuscent */`
329			`int rh_attach_region(rh_info_t * info, unsigned long start, int size)`
330			`{`
331			`rh_block_t *blk;`
332			`unsigned long s, e, m;`
333			`int r;`
334
335			`/* The region must be aligned */`
336			`s = start;`
337			`e = s + size;`
338			`m = info->alignment - 1;`
339
340			`/* Round start up */`
341			`s = (s + m) & ~m;`
342
343			`/* Round end down */`
344			`e = e & ~m;`
345
346			`if (IS_ERR_VALUE(e) \|\| (e < s))`
347			`return -ERANGE;`
348
349			`/* Take final values */`
350			`start = s;`
351			`size = e - s;`
352
353			`/* Grow the blocks, if needed */`
354			`r = assure_empty(info, 1);`
355			`if (r < 0)`
356			`return r;`
357
358			`blk = get_slot(info);`
359			`blk->start = start;`
360			`blk->size = size;`
361			`blk->owner = NULL;`
362
363			`attach_free_block(info, blk);`
364
365			`return 0;`
366			`}`
367			`EXPORT_SYMBOL_GPL(rh_attach_region);`
368
369			`/* Detatch given address range, splits free block if needed. */`
370			`unsigned long rh_detach_region(rh_info_t * info, unsigned long start, int size)`
371			`{`
372			`struct list_head *l;`
373			`rh_block_t blk, newblk;`
374			`unsigned long s, e, m, bs, be;`
375
376			`/* Validate size */`
377			`if (size <= 0)`
378			`return (unsigned long) -EINVAL;`
379
380			`/* The region must be aligned */`
381			`s = start;`
382			`e = s + size;`
383			`m = info->alignment - 1;`
384
385			`/* Round start up */`
386			`s = (s + m) & ~m;`
387
388			`/* Round end down */`
389			`e = e & ~m;`
390
391			`if (assure_empty(info, 1) < 0)`
392			`return (unsigned long) -ENOMEM;`
393
394			`blk = NULL;`
395			`list_for_each(l, &info->free_list) {`
396			`blk = list_entry(l, rh_block_t, list);`
397			`/* The range must lie entirely inside one free block */`
398			`bs = blk->start;`
399			`be = blk->start + blk->size;`
400			`if (s >= bs && e <= be)`
401			`break;`
402			`blk = NULL;`
403			`}`
404
405			`if (blk == NULL)`
406			`return (unsigned long) -ENOMEM;`
407
408			`/* Perfect fit */`
409			`if (bs == s && be == e) {`
410			`/* Delete from free list, release slot */`
411			`list_del(&blk->list);`
412			`release_slot(info, blk);`
413			`return s;`
414			`}`
415
416			`/* blk still in free list, with updated start and/or size */`
417			`if (bs == s \|\| be == e) {`
418			`if (bs == s)`
419			`blk->start += size;`
420			`blk->size -= size;`
421
422			`} else {`
423			`/* The front free fragment */`
424			`blk->size = s - bs;`
425
426			`/* the back free fragment */`
427			`newblk = get_slot(info);`
428			`newblk->start = e;`
429			`newblk->size = be - e;`
430
431			`list_add(&newblk->list, &blk->list);`
432			`}`
433
434			`return s;`
435			`}`
436			`EXPORT_SYMBOL_GPL(rh_detach_region);`
437
438			`/* Allocate a block of memory at the specified alignment. The value returned`
439			`* is an offset into the buffer initialized by rh_init(), or a negative number`
440			`* if there is an error.`
441			`*/`
442			`unsigned long rh_alloc_align(rh_info_t * info, int size, int alignment, const char *owner)`
443			`{`
444			`struct list_head *l;`
445			`rh_block_t *blk;`
446			`rh_block_t *newblk;`
447			`unsigned long start, sp_size;`
448
449			`/* Validate size, and alignment must be power of two */`
450			`if (size <= 0 \|\| (alignment & (alignment - 1)) != 0)`
451			`return (unsigned long) -EINVAL;`
452
453			`/* Align to configured alignment */`
454			`size = (size + (info->alignment - 1)) & ~(info->alignment - 1);`
455
456			`if (assure_empty(info, 2) < 0)`
457			`return (unsigned long) -ENOMEM;`
458
459			`blk = NULL;`
460			`list_for_each(l, &info->free_list) {`
461			`blk = list_entry(l, rh_block_t, list);`
462			`if (size <= blk->size) {`
463			`start = (blk->start + alignment - 1) & ~(alignment - 1);`
464			`if (start + size <= blk->start + blk->size)`
465			`break;`
466			`}`
467			`blk = NULL;`
468			`}`
469
470			`if (blk == NULL)`
471			`return (unsigned long) -ENOMEM;`
472
473			`/* Just fits */`
474			`if (blk->size == size) {`
475			`/* Move from free list to taken list */`
476			`list_del(&blk->list);`
477			`newblk = blk;`
478			`} else {`
479			`/* Fragment caused, split if needed */`
480			`/* Create block for fragment in the beginning */`
481			`sp_size = start - blk->start;`
482			`if (sp_size) {`
483			`rh_block_t *spblk;`
484
485			`spblk = get_slot(info);`
486			`spblk->start = blk->start;`
487			`spblk->size = sp_size;`
488			`/* add before the blk */`
489			`list_add(&spblk->list, blk->list.prev);`
490			`}`
491			`newblk = get_slot(info);`
492			`newblk->start = start;`
493			`newblk->size = size;`
494
495			`/* blk still in free list, with updated start and size`
496			`* for fragment in the end */`
497			`blk->start = start + size;`
498			`blk->size -= sp_size + size;`
499			`/* No fragment in the end, remove blk */`
500			`if (blk->size == 0) {`
501			`list_del(&blk->list);`
502			`release_slot(info, blk);`
503			`}`
504			`}`
505
506			`newblk->owner = owner;`
507			`attach_taken_block(info, newblk);`
508
509			`return start;`
510			`}`
511			`EXPORT_SYMBOL_GPL(rh_alloc_align);`
512
513			`/* Allocate a block of memory at the default alignment. The value returned is`
514			`* an offset into the buffer initialized by rh_init(), or a negative number if`
515			`* there is an error.`
516			`*/`
517			`unsigned long rh_alloc(rh_info_t * info, int size, const char *owner)`
518			`{`
519			`return rh_alloc_align(info, size, info->alignment, owner);`
520			`}`
521			`EXPORT_SYMBOL_GPL(rh_alloc);`
522
523			`/* Allocate a block of memory at the given offset, rounded up to the default`
524			`* alignment. The value returned is an offset into the buffer initialized by`
525			`* rh_init(), or a negative number if there is an error.`
526			`*/`
527			`unsigned long rh_alloc_fixed(rh_info_t * info, unsigned long start, int size, const char *owner)`
528			`{`
529			`struct list_head *l;`
530			`rh_block_t blk, newblk1, *newblk2;`
531			`unsigned long s, e, m, bs = 0, be = 0;`
532
533			`/* Validate size */`
534			`if (size <= 0)`
535			`return (unsigned long) -EINVAL;`
536
537			`/* The region must be aligned */`
538			`s = start;`
539			`e = s + size;`
540			`m = info->alignment - 1;`
541
542			`/* Round start up */`
543			`s = (s + m) & ~m;`
544
545			`/* Round end down */`
546			`e = e & ~m;`
547
548			`if (assure_empty(info, 2) < 0)`
549			`return (unsigned long) -ENOMEM;`
550
551			`blk = NULL;`
552			`list_for_each(l, &info->free_list) {`
553			`blk = list_entry(l, rh_block_t, list);`
554			`/* The range must lie entirely inside one free block */`
555			`bs = blk->start;`
556			`be = blk->start + blk->size;`
557			`if (s >= bs && e <= be)`
558			`break;`
559			`}`
560
561			`if (blk == NULL)`
562			`return (unsigned long) -ENOMEM;`
563
564			`/* Perfect fit */`
565			`if (bs == s && be == e) {`
566			`/* Move from free list to taken list */`
567			`list_del(&blk->list);`
568			`blk->owner = owner;`
569
570			`start = blk->start;`
571			`attach_taken_block(info, blk);`
572
573			`return start;`
574
575			`}`
576
577			`/* blk still in free list, with updated start and/or size */`
578			`if (bs == s \|\| be == e) {`
579			`if (bs == s)`
580			`blk->start += size;`
581			`blk->size -= size;`
582
583			`} else {`
584			`/* The front free fragment */`
585			`blk->size = s - bs;`
586
587			`/* The back free fragment */`
588			`newblk2 = get_slot(info);`
589			`newblk2->start = e;`
590			`newblk2->size = be - e;`
591
592			`list_add(&newblk2->list, &blk->list);`
593			`}`
594
595			`newblk1 = get_slot(info);`
596			`newblk1->start = s;`
597			`newblk1->size = e - s;`
598			`newblk1->owner = owner;`
599
600			`start = newblk1->start;`
601			`attach_taken_block(info, newblk1);`
602
603			`return start;`
604			`}`
605			`EXPORT_SYMBOL_GPL(rh_alloc_fixed);`
606
607			`/* Deallocate the memory previously allocated by one of the rh_alloc functions.`
608			`* The return value is the size of the deallocated block, or a negative number`
609			`* if there is an error.`
610			`*/`
611			`int rh_free(rh_info_t * info, unsigned long start)`
612			`{`
613			`rh_block_t blk, blk2;`
614			`struct list_head *l;`
615			`int size;`
616
617			`/* Linear search for block */`
618			`blk = NULL;`
619			`list_for_each(l, &info->taken_list) {`
620			`blk2 = list_entry(l, rh_block_t, list);`
621			`if (start < blk2->start)`
622			`break;`
623			`blk = blk2;`
624			`}`
625
626			`if (blk == NULL \|\| start > (blk->start + blk->size))`
627			`return -EINVAL;`
628
629			`/* Remove from taken list */`
630			`list_del(&blk->list);`
631
632			`/* Get size of freed block */`
633			`size = blk->size;`
634			`attach_free_block(info, blk);`
635
636			`return size;`
637			`}`
638			`EXPORT_SYMBOL_GPL(rh_free);`
639
640			`int rh_get_stats(rh_info_t * info, int what, int max_stats, rh_stats_t * stats)`
641			`{`
642			`rh_block_t *blk;`
643			`struct list_head *l;`
644			`struct list_head *h;`
645			`int nr;`
646
647			`switch (what) {`
648
649			`case RHGS_FREE:`
650			`h = &info->free_list;`
651			`break;`
652
653			`case RHGS_TAKEN:`
654			`h = &info->taken_list;`
655			`break;`
656
657			`default:`
658			`return -EINVAL;`
659			`}`
660
661			`/* Linear search for block */`
662			`nr = 0;`
663			`list_for_each(l, h) {`
664			`blk = list_entry(l, rh_block_t, list);`
665			`if (stats != NULL && nr < max_stats) {`
666			`stats->start = blk->start;`
667			`stats->size = blk->size;`
668			`stats->owner = blk->owner;`
669			`stats++;`
670			`}`
671			`nr++;`
672			`}`
673
674			`return nr;`
675			`}`
676			`EXPORT_SYMBOL_GPL(rh_get_stats);`
677
678			`int rh_set_owner(rh_info_t * info, unsigned long start, const char *owner)`
679			`{`
680			`rh_block_t blk, blk2;`
681			`struct list_head *l;`
682			`int size;`
683
684			`/* Linear search for block */`
685			`blk = NULL;`
686			`list_for_each(l, &info->taken_list) {`
687			`blk2 = list_entry(l, rh_block_t, list);`
688			`if (start < blk2->start)`
689			`break;`
690			`blk = blk2;`
691			`}`
692
693			`if (blk == NULL \|\| start > (blk->start + blk->size))`
694			`return -EINVAL;`
695
696			`blk->owner = owner;`
697			`size = blk->size;`
698
699			`return size;`
700			`}`
701			`EXPORT_SYMBOL_GPL(rh_set_owner);`
702
703			`void rh_dump(rh_info_t * info)`
704			`{`
705			`static rh_stats_t st[32]; /* XXX maximum 32 blocks */`
706			`int maxnr;`
707			`int i, nr;`
708
709			`maxnr = ARRAY_SIZE(st);`
710
711			`printk(KERN_INFO`
712			`"info @0x%p (%d slots empty / %d max)\n",`
713			`info, info->empty_slots, info->max_blocks);`
714
715			`printk(KERN_INFO " Free:\n");`
716			`nr = rh_get_stats(info, RHGS_FREE, maxnr, st);`
717			`if (nr > maxnr)`
718			`nr = maxnr;`
719			`for (i = 0; i < nr; i++)`
720			`printk(KERN_INFO`
721			`" 0x%lx-0x%lx (%u)\n",`
722			`st[i].start, st[i].start + st[i].size,`
723			`st[i].size);`
724			`printk(KERN_INFO "\n");`
725
726			`printk(KERN_INFO " Taken:\n");`
727			`nr = rh_get_stats(info, RHGS_TAKEN, maxnr, st);`
728			`if (nr > maxnr)`
729			`nr = maxnr;`
730			`for (i = 0; i < nr; i++)`
731			`printk(KERN_INFO`
732			`" 0x%lx-0x%lx (%u) %s\n",`
733			`st[i].start, st[i].start + st[i].size,`
734			`st[i].size, st[i].owner != NULL ? st[i].owner : "");`
735			`printk(KERN_INFO "\n");`
736			`}`
737			`EXPORT_SYMBOL_GPL(rh_dump);`
738
739			`void rh_dump_blk(rh_info_t * info, rh_block_t * blk)`
740			`{`
741			`printk(KERN_INFO`
742			`"blk @0x%p: 0x%lx-0x%lx (%u)\n",`
743			`blk, blk->start, blk->start + blk->size, blk->size);`
744			`}`
745			`EXPORT_SYMBOL_GPL(rh_dump_blk);`
746