114cf11afSPaul Mackerras /*
214cf11afSPaul Mackerras * A Remote Heap. Remote means that we don't touch the memory that the
314cf11afSPaul Mackerras * heap points to. Normal heap implementations use the memory they manage
414cf11afSPaul Mackerras * to place their list. We cannot do that because the memory we manage may
514cf11afSPaul Mackerras * have special properties, for example it is uncachable or of different
614cf11afSPaul Mackerras * endianess.
714cf11afSPaul Mackerras *
814cf11afSPaul Mackerras * Author: Pantelis Antoniou <panto@intracom.gr>
914cf11afSPaul Mackerras *
1014cf11afSPaul Mackerras * 2004 (c) INTRACOM S.A. Greece. This file is licensed under
1114cf11afSPaul Mackerras * the terms of the GNU General Public License version 2. This program
1214cf11afSPaul Mackerras * is licensed "as is" without any warranty of any kind, whether express
1314cf11afSPaul Mackerras * or implied.
1414cf11afSPaul Mackerras */
1514cf11afSPaul Mackerras #include <linux/types.h>
1614cf11afSPaul Mackerras #include <linux/errno.h>
173839a594SAhmed S. Darwish #include <linux/kernel.h>
184b16f8e2SPaul Gortmaker #include <linux/export.h>
1914cf11afSPaul Mackerras #include <linux/mm.h>
204e950f6fSAlexey Dobriyan #include <linux/err.h>
2114cf11afSPaul Mackerras #include <linux/slab.h>
2214cf11afSPaul Mackerras
2314cf11afSPaul Mackerras #include <asm/rheap.h>
2414cf11afSPaul Mackerras
2514cf11afSPaul Mackerras /*
2614cf11afSPaul Mackerras * Fixup a list_head, needed when copying lists. If the pointers fall
2714cf11afSPaul Mackerras * between s and e, apply the delta. This assumes that
2814cf11afSPaul Mackerras * sizeof(struct list_head *) == sizeof(unsigned long *).
2914cf11afSPaul Mackerras */
fixup(unsigned long s,unsigned long e,int d,struct list_head * l)3014cf11afSPaul Mackerras static inline void fixup(unsigned long s, unsigned long e, int d,
3114cf11afSPaul Mackerras struct list_head *l)
3214cf11afSPaul Mackerras {
3314cf11afSPaul Mackerras unsigned long *pp;
3414cf11afSPaul Mackerras
3514cf11afSPaul Mackerras pp = (unsigned long *)&l->next;
3614cf11afSPaul Mackerras if (*pp >= s && *pp < e)
3714cf11afSPaul Mackerras *pp += d;
3814cf11afSPaul Mackerras
3914cf11afSPaul Mackerras pp = (unsigned long *)&l->prev;
4014cf11afSPaul Mackerras if (*pp >= s && *pp < e)
4114cf11afSPaul Mackerras *pp += d;
4214cf11afSPaul Mackerras }
4314cf11afSPaul Mackerras
4414cf11afSPaul Mackerras /* Grow the allocated blocks */
grow(rh_info_t * info,int max_blocks)4514cf11afSPaul Mackerras static int grow(rh_info_t * info, int max_blocks)
4614cf11afSPaul Mackerras {
4714cf11afSPaul Mackerras rh_block_t *block, *blk;
4814cf11afSPaul Mackerras int i, new_blocks;
4914cf11afSPaul Mackerras int delta;
5014cf11afSPaul Mackerras unsigned long blks, blke;
5114cf11afSPaul Mackerras
5214cf11afSPaul Mackerras if (max_blocks <= info->max_blocks)
5314cf11afSPaul Mackerras return -EINVAL;
5414cf11afSPaul Mackerras
5514cf11afSPaul Mackerras new_blocks = max_blocks - info->max_blocks;
5614cf11afSPaul Mackerras
57*6da2ec56SKees Cook block = kmalloc_array(max_blocks, sizeof(rh_block_t), GFP_ATOMIC);
5814cf11afSPaul Mackerras if (block == NULL)
5914cf11afSPaul Mackerras return -ENOMEM;
6014cf11afSPaul Mackerras
6114cf11afSPaul Mackerras if (info->max_blocks > 0) {
6214cf11afSPaul Mackerras
6314cf11afSPaul Mackerras /* copy old block area */
6414cf11afSPaul Mackerras memcpy(block, info->block,
6514cf11afSPaul Mackerras sizeof(rh_block_t) * info->max_blocks);
6614cf11afSPaul Mackerras
6714cf11afSPaul Mackerras delta = (char *)block - (char *)info->block;
6814cf11afSPaul Mackerras
6914cf11afSPaul Mackerras /* and fixup list pointers */
7014cf11afSPaul Mackerras blks = (unsigned long)info->block;
7114cf11afSPaul Mackerras blke = (unsigned long)(info->block + info->max_blocks);
7214cf11afSPaul Mackerras
7314cf11afSPaul Mackerras for (i = 0, blk = block; i < info->max_blocks; i++, blk++)
7414cf11afSPaul Mackerras fixup(blks, blke, delta, &blk->list);
7514cf11afSPaul Mackerras
7614cf11afSPaul Mackerras fixup(blks, blke, delta, &info->empty_list);
7714cf11afSPaul Mackerras fixup(blks, blke, delta, &info->free_list);
7814cf11afSPaul Mackerras fixup(blks, blke, delta, &info->taken_list);
7914cf11afSPaul Mackerras
8014cf11afSPaul Mackerras /* free the old allocated memory */
8114cf11afSPaul Mackerras if ((info->flags & RHIF_STATIC_BLOCK) == 0)
8214cf11afSPaul Mackerras kfree(info->block);
8314cf11afSPaul Mackerras }
8414cf11afSPaul Mackerras
8514cf11afSPaul Mackerras info->block = block;
8614cf11afSPaul Mackerras info->empty_slots += new_blocks;
8714cf11afSPaul Mackerras info->max_blocks = max_blocks;
8814cf11afSPaul Mackerras info->flags &= ~RHIF_STATIC_BLOCK;
8914cf11afSPaul Mackerras
9014cf11afSPaul Mackerras /* add all new blocks to the free list */
914942bd80STimur Tabi blk = block + info->max_blocks - new_blocks;
924942bd80STimur Tabi for (i = 0; i < new_blocks; i++, blk++)
9314cf11afSPaul Mackerras list_add(&blk->list, &info->empty_list);
9414cf11afSPaul Mackerras
9514cf11afSPaul Mackerras return 0;
9614cf11afSPaul Mackerras }
9714cf11afSPaul Mackerras
9814cf11afSPaul Mackerras /*
9914cf11afSPaul Mackerras * Assure at least the required amount of empty slots. If this function
10014cf11afSPaul Mackerras * causes a grow in the block area then all pointers kept to the block
10114cf11afSPaul Mackerras * area are invalid!
10214cf11afSPaul Mackerras */
assure_empty(rh_info_t * info,int slots)10314cf11afSPaul Mackerras static int assure_empty(rh_info_t * info, int slots)
10414cf11afSPaul Mackerras {
10514cf11afSPaul Mackerras int max_blocks;
10614cf11afSPaul Mackerras
10714cf11afSPaul Mackerras /* This function is not meant to be used to grow uncontrollably */
10814cf11afSPaul Mackerras if (slots >= 4)
10914cf11afSPaul Mackerras return -EINVAL;
11014cf11afSPaul Mackerras
11114cf11afSPaul Mackerras /* Enough space */
11214cf11afSPaul Mackerras if (info->empty_slots >= slots)
11314cf11afSPaul Mackerras return 0;
11414cf11afSPaul Mackerras
11514cf11afSPaul Mackerras /* Next 16 sized block */
11614cf11afSPaul Mackerras max_blocks = ((info->max_blocks + slots) + 15) & ~15;
11714cf11afSPaul Mackerras
11814cf11afSPaul Mackerras return grow(info, max_blocks);
11914cf11afSPaul Mackerras }
12014cf11afSPaul Mackerras
get_slot(rh_info_t * info)12114cf11afSPaul Mackerras static rh_block_t *get_slot(rh_info_t * info)
12214cf11afSPaul Mackerras {
12314cf11afSPaul Mackerras rh_block_t *blk;
12414cf11afSPaul Mackerras
12514cf11afSPaul Mackerras /* If no more free slots, and failure to extend. */
12614cf11afSPaul Mackerras /* XXX: You should have called assure_empty before */
12714cf11afSPaul Mackerras if (info->empty_slots == 0) {
12814cf11afSPaul Mackerras printk(KERN_ERR "rh: out of slots; crash is imminent.\n");
12914cf11afSPaul Mackerras return NULL;
13014cf11afSPaul Mackerras }
13114cf11afSPaul Mackerras
13214cf11afSPaul Mackerras /* Get empty slot to use */
13314cf11afSPaul Mackerras blk = list_entry(info->empty_list.next, rh_block_t, list);
13414cf11afSPaul Mackerras list_del_init(&blk->list);
13514cf11afSPaul Mackerras info->empty_slots--;
13614cf11afSPaul Mackerras
13714cf11afSPaul Mackerras /* Initialize */
1384c35630cSTimur Tabi blk->start = 0;
13914cf11afSPaul Mackerras blk->size = 0;
14014cf11afSPaul Mackerras blk->owner = NULL;
14114cf11afSPaul Mackerras
14214cf11afSPaul Mackerras return blk;
14314cf11afSPaul Mackerras }
14414cf11afSPaul Mackerras
release_slot(rh_info_t * info,rh_block_t * blk)14514cf11afSPaul Mackerras static inline void release_slot(rh_info_t * info, rh_block_t * blk)
14614cf11afSPaul Mackerras {
14714cf11afSPaul Mackerras list_add(&blk->list, &info->empty_list);
14814cf11afSPaul Mackerras info->empty_slots++;
14914cf11afSPaul Mackerras }
15014cf11afSPaul Mackerras
attach_free_block(rh_info_t * info,rh_block_t * blkn)15114cf11afSPaul Mackerras static void attach_free_block(rh_info_t * info, rh_block_t * blkn)
15214cf11afSPaul Mackerras {
15314cf11afSPaul Mackerras rh_block_t *blk;
15414cf11afSPaul Mackerras rh_block_t *before;
15514cf11afSPaul Mackerras rh_block_t *after;
15614cf11afSPaul Mackerras rh_block_t *next;
15714cf11afSPaul Mackerras int size;
15814cf11afSPaul Mackerras unsigned long s, e, bs, be;
15914cf11afSPaul Mackerras struct list_head *l;
16014cf11afSPaul Mackerras
16114cf11afSPaul Mackerras /* We assume that they are aligned properly */
16214cf11afSPaul Mackerras size = blkn->size;
1634c35630cSTimur Tabi s = blkn->start;
16414cf11afSPaul Mackerras e = s + size;
16514cf11afSPaul Mackerras
16614cf11afSPaul Mackerras /* Find the blocks immediately before and after the given one
16714cf11afSPaul Mackerras * (if any) */
16814cf11afSPaul Mackerras before = NULL;
16914cf11afSPaul Mackerras after = NULL;
17014cf11afSPaul Mackerras next = NULL;
17114cf11afSPaul Mackerras
17214cf11afSPaul Mackerras list_for_each(l, &info->free_list) {
17314cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
17414cf11afSPaul Mackerras
1754c35630cSTimur Tabi bs = blk->start;
17614cf11afSPaul Mackerras be = bs + blk->size;
17714cf11afSPaul Mackerras
17814cf11afSPaul Mackerras if (next == NULL && s >= bs)
17914cf11afSPaul Mackerras next = blk;
18014cf11afSPaul Mackerras
18114cf11afSPaul Mackerras if (be == s)
18214cf11afSPaul Mackerras before = blk;
18314cf11afSPaul Mackerras
18414cf11afSPaul Mackerras if (e == bs)
18514cf11afSPaul Mackerras after = blk;
18614cf11afSPaul Mackerras
18714cf11afSPaul Mackerras /* If both are not null, break now */
18814cf11afSPaul Mackerras if (before != NULL && after != NULL)
18914cf11afSPaul Mackerras break;
19014cf11afSPaul Mackerras }
19114cf11afSPaul Mackerras
19214cf11afSPaul Mackerras /* Now check if they are really adjacent */
1934c35630cSTimur Tabi if (before && s != (before->start + before->size))
19414cf11afSPaul Mackerras before = NULL;
19514cf11afSPaul Mackerras
1964c35630cSTimur Tabi if (after && e != after->start)
19714cf11afSPaul Mackerras after = NULL;
19814cf11afSPaul Mackerras
19914cf11afSPaul Mackerras /* No coalescing; list insert and return */
20014cf11afSPaul Mackerras if (before == NULL && after == NULL) {
20114cf11afSPaul Mackerras
20214cf11afSPaul Mackerras if (next != NULL)
20314cf11afSPaul Mackerras list_add(&blkn->list, &next->list);
20414cf11afSPaul Mackerras else
20514cf11afSPaul Mackerras list_add(&blkn->list, &info->free_list);
20614cf11afSPaul Mackerras
20714cf11afSPaul Mackerras return;
20814cf11afSPaul Mackerras }
20914cf11afSPaul Mackerras
21014cf11afSPaul Mackerras /* We don't need it anymore */
21114cf11afSPaul Mackerras release_slot(info, blkn);
21214cf11afSPaul Mackerras
21314cf11afSPaul Mackerras /* Grow the before block */
21414cf11afSPaul Mackerras if (before != NULL && after == NULL) {
21514cf11afSPaul Mackerras before->size += size;
21614cf11afSPaul Mackerras return;
21714cf11afSPaul Mackerras }
21814cf11afSPaul Mackerras
21914cf11afSPaul Mackerras /* Grow the after block backwards */
22014cf11afSPaul Mackerras if (before == NULL && after != NULL) {
2214c35630cSTimur Tabi after->start -= size;
22214cf11afSPaul Mackerras after->size += size;
22314cf11afSPaul Mackerras return;
22414cf11afSPaul Mackerras }
22514cf11afSPaul Mackerras
22614cf11afSPaul Mackerras /* Grow the before block, and release the after block */
22714cf11afSPaul Mackerras before->size += size + after->size;
22814cf11afSPaul Mackerras list_del(&after->list);
22914cf11afSPaul Mackerras release_slot(info, after);
23014cf11afSPaul Mackerras }
23114cf11afSPaul Mackerras
attach_taken_block(rh_info_t * info,rh_block_t * blkn)23214cf11afSPaul Mackerras static void attach_taken_block(rh_info_t * info, rh_block_t * blkn)
23314cf11afSPaul Mackerras {
23414cf11afSPaul Mackerras rh_block_t *blk;
23514cf11afSPaul Mackerras struct list_head *l;
23614cf11afSPaul Mackerras
23714cf11afSPaul Mackerras /* Find the block immediately before the given one (if any) */
23814cf11afSPaul Mackerras list_for_each(l, &info->taken_list) {
23914cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
24014cf11afSPaul Mackerras if (blk->start > blkn->start) {
24114cf11afSPaul Mackerras list_add_tail(&blkn->list, &blk->list);
24214cf11afSPaul Mackerras return;
24314cf11afSPaul Mackerras }
24414cf11afSPaul Mackerras }
24514cf11afSPaul Mackerras
24614cf11afSPaul Mackerras list_add_tail(&blkn->list, &info->taken_list);
24714cf11afSPaul Mackerras }
24814cf11afSPaul Mackerras
24914cf11afSPaul Mackerras /*
25014cf11afSPaul Mackerras * Create a remote heap dynamically. Note that no memory for the blocks
25114cf11afSPaul Mackerras * are allocated. It will upon the first allocation
25214cf11afSPaul Mackerras */
rh_create(unsigned int alignment)25314cf11afSPaul Mackerras rh_info_t *rh_create(unsigned int alignment)
25414cf11afSPaul Mackerras {
25514cf11afSPaul Mackerras rh_info_t *info;
25614cf11afSPaul Mackerras
25714cf11afSPaul Mackerras /* Alignment must be a power of two */
25814cf11afSPaul Mackerras if ((alignment & (alignment - 1)) != 0)
25914cf11afSPaul Mackerras return ERR_PTR(-EINVAL);
26014cf11afSPaul Mackerras
2613a2f020cSTimur Tabi info = kmalloc(sizeof(*info), GFP_ATOMIC);
26214cf11afSPaul Mackerras if (info == NULL)
26314cf11afSPaul Mackerras return ERR_PTR(-ENOMEM);
26414cf11afSPaul Mackerras
26514cf11afSPaul Mackerras info->alignment = alignment;
26614cf11afSPaul Mackerras
26714cf11afSPaul Mackerras /* Initially everything as empty */
26814cf11afSPaul Mackerras info->block = NULL;
26914cf11afSPaul Mackerras info->max_blocks = 0;
27014cf11afSPaul Mackerras info->empty_slots = 0;
27114cf11afSPaul Mackerras info->flags = 0;
27214cf11afSPaul Mackerras
27314cf11afSPaul Mackerras INIT_LIST_HEAD(&info->empty_list);
27414cf11afSPaul Mackerras INIT_LIST_HEAD(&info->free_list);
27514cf11afSPaul Mackerras INIT_LIST_HEAD(&info->taken_list);
27614cf11afSPaul Mackerras
27714cf11afSPaul Mackerras return info;
27814cf11afSPaul Mackerras }
279d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_create);
28014cf11afSPaul Mackerras
28114cf11afSPaul Mackerras /*
28214cf11afSPaul Mackerras * Destroy a dynamically created remote heap. Deallocate only if the areas
28314cf11afSPaul Mackerras * are not static
28414cf11afSPaul Mackerras */
rh_destroy(rh_info_t * info)28514cf11afSPaul Mackerras void rh_destroy(rh_info_t * info)
28614cf11afSPaul Mackerras {
2877f4eec39SMarkus Elfring if ((info->flags & RHIF_STATIC_BLOCK) == 0)
28814cf11afSPaul Mackerras kfree(info->block);
28914cf11afSPaul Mackerras
29014cf11afSPaul Mackerras if ((info->flags & RHIF_STATIC_INFO) == 0)
29114cf11afSPaul Mackerras kfree(info);
29214cf11afSPaul Mackerras }
293d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_destroy);
29414cf11afSPaul Mackerras
29514cf11afSPaul Mackerras /*
29614cf11afSPaul Mackerras * Initialize in place a remote heap info block. This is needed to support
29714cf11afSPaul Mackerras * operation very early in the startup of the kernel, when it is not yet safe
29814cf11afSPaul Mackerras * to call kmalloc.
29914cf11afSPaul Mackerras */
rh_init(rh_info_t * info,unsigned int alignment,int max_blocks,rh_block_t * block)30014cf11afSPaul Mackerras void rh_init(rh_info_t * info, unsigned int alignment, int max_blocks,
30114cf11afSPaul Mackerras rh_block_t * block)
30214cf11afSPaul Mackerras {
30314cf11afSPaul Mackerras int i;
30414cf11afSPaul Mackerras rh_block_t *blk;
30514cf11afSPaul Mackerras
30614cf11afSPaul Mackerras /* Alignment must be a power of two */
30714cf11afSPaul Mackerras if ((alignment & (alignment - 1)) != 0)
30814cf11afSPaul Mackerras return;
30914cf11afSPaul Mackerras
31014cf11afSPaul Mackerras info->alignment = alignment;
31114cf11afSPaul Mackerras
31214cf11afSPaul Mackerras /* Initially everything as empty */
31314cf11afSPaul Mackerras info->block = block;
31414cf11afSPaul Mackerras info->max_blocks = max_blocks;
31514cf11afSPaul Mackerras info->empty_slots = max_blocks;
31614cf11afSPaul Mackerras info->flags = RHIF_STATIC_INFO | RHIF_STATIC_BLOCK;
31714cf11afSPaul Mackerras
31814cf11afSPaul Mackerras INIT_LIST_HEAD(&info->empty_list);
31914cf11afSPaul Mackerras INIT_LIST_HEAD(&info->free_list);
32014cf11afSPaul Mackerras INIT_LIST_HEAD(&info->taken_list);
32114cf11afSPaul Mackerras
32214cf11afSPaul Mackerras /* Add all new blocks to the free list */
32314cf11afSPaul Mackerras for (i = 0, blk = block; i < max_blocks; i++, blk++)
32414cf11afSPaul Mackerras list_add(&blk->list, &info->empty_list);
32514cf11afSPaul Mackerras }
326d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_init);
32714cf11afSPaul Mackerras
328027dfac6SMichael Ellerman /* Attach a free memory region, coalesces regions if adjacent */
rh_attach_region(rh_info_t * info,unsigned long start,int size)3294c35630cSTimur Tabi int rh_attach_region(rh_info_t * info, unsigned long start, int size)
33014cf11afSPaul Mackerras {
33114cf11afSPaul Mackerras rh_block_t *blk;
33214cf11afSPaul Mackerras unsigned long s, e, m;
33314cf11afSPaul Mackerras int r;
33414cf11afSPaul Mackerras
33514cf11afSPaul Mackerras /* The region must be aligned */
3364c35630cSTimur Tabi s = start;
33714cf11afSPaul Mackerras e = s + size;
33814cf11afSPaul Mackerras m = info->alignment - 1;
33914cf11afSPaul Mackerras
34014cf11afSPaul Mackerras /* Round start up */
34114cf11afSPaul Mackerras s = (s + m) & ~m;
34214cf11afSPaul Mackerras
34314cf11afSPaul Mackerras /* Round end down */
34414cf11afSPaul Mackerras e = e & ~m;
34514cf11afSPaul Mackerras
3464c35630cSTimur Tabi if (IS_ERR_VALUE(e) || (e < s))
3474c35630cSTimur Tabi return -ERANGE;
3484c35630cSTimur Tabi
34914cf11afSPaul Mackerras /* Take final values */
3504c35630cSTimur Tabi start = s;
3514c35630cSTimur Tabi size = e - s;
35214cf11afSPaul Mackerras
35314cf11afSPaul Mackerras /* Grow the blocks, if needed */
35414cf11afSPaul Mackerras r = assure_empty(info, 1);
35514cf11afSPaul Mackerras if (r < 0)
35614cf11afSPaul Mackerras return r;
35714cf11afSPaul Mackerras
35814cf11afSPaul Mackerras blk = get_slot(info);
35914cf11afSPaul Mackerras blk->start = start;
36014cf11afSPaul Mackerras blk->size = size;
36114cf11afSPaul Mackerras blk->owner = NULL;
36214cf11afSPaul Mackerras
36314cf11afSPaul Mackerras attach_free_block(info, blk);
36414cf11afSPaul Mackerras
36514cf11afSPaul Mackerras return 0;
36614cf11afSPaul Mackerras }
367d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_attach_region);
36814cf11afSPaul Mackerras
36914cf11afSPaul Mackerras /* Detatch given address range, splits free block if needed. */
rh_detach_region(rh_info_t * info,unsigned long start,int size)3704c35630cSTimur Tabi unsigned long rh_detach_region(rh_info_t * info, unsigned long start, int size)
37114cf11afSPaul Mackerras {
37214cf11afSPaul Mackerras struct list_head *l;
37314cf11afSPaul Mackerras rh_block_t *blk, *newblk;
37414cf11afSPaul Mackerras unsigned long s, e, m, bs, be;
37514cf11afSPaul Mackerras
37614cf11afSPaul Mackerras /* Validate size */
37714cf11afSPaul Mackerras if (size <= 0)
3784c35630cSTimur Tabi return (unsigned long) -EINVAL;
37914cf11afSPaul Mackerras
38014cf11afSPaul Mackerras /* The region must be aligned */
3814c35630cSTimur Tabi s = start;
38214cf11afSPaul Mackerras e = s + size;
38314cf11afSPaul Mackerras m = info->alignment - 1;
38414cf11afSPaul Mackerras
38514cf11afSPaul Mackerras /* Round start up */
38614cf11afSPaul Mackerras s = (s + m) & ~m;
38714cf11afSPaul Mackerras
38814cf11afSPaul Mackerras /* Round end down */
38914cf11afSPaul Mackerras e = e & ~m;
39014cf11afSPaul Mackerras
39114cf11afSPaul Mackerras if (assure_empty(info, 1) < 0)
3924c35630cSTimur Tabi return (unsigned long) -ENOMEM;
39314cf11afSPaul Mackerras
39414cf11afSPaul Mackerras blk = NULL;
39514cf11afSPaul Mackerras list_for_each(l, &info->free_list) {
39614cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
39714cf11afSPaul Mackerras /* The range must lie entirely inside one free block */
3984c35630cSTimur Tabi bs = blk->start;
3994c35630cSTimur Tabi be = blk->start + blk->size;
40014cf11afSPaul Mackerras if (s >= bs && e <= be)
40114cf11afSPaul Mackerras break;
40214cf11afSPaul Mackerras blk = NULL;
40314cf11afSPaul Mackerras }
40414cf11afSPaul Mackerras
40514cf11afSPaul Mackerras if (blk == NULL)
4064c35630cSTimur Tabi return (unsigned long) -ENOMEM;
40714cf11afSPaul Mackerras
40814cf11afSPaul Mackerras /* Perfect fit */
40914cf11afSPaul Mackerras if (bs == s && be == e) {
41014cf11afSPaul Mackerras /* Delete from free list, release slot */
41114cf11afSPaul Mackerras list_del(&blk->list);
41214cf11afSPaul Mackerras release_slot(info, blk);
4134c35630cSTimur Tabi return s;
41414cf11afSPaul Mackerras }
41514cf11afSPaul Mackerras
41614cf11afSPaul Mackerras /* blk still in free list, with updated start and/or size */
41714cf11afSPaul Mackerras if (bs == s || be == e) {
41814cf11afSPaul Mackerras if (bs == s)
4194c35630cSTimur Tabi blk->start += size;
42014cf11afSPaul Mackerras blk->size -= size;
42114cf11afSPaul Mackerras
42214cf11afSPaul Mackerras } else {
42314cf11afSPaul Mackerras /* The front free fragment */
42414cf11afSPaul Mackerras blk->size = s - bs;
42514cf11afSPaul Mackerras
42614cf11afSPaul Mackerras /* the back free fragment */
42714cf11afSPaul Mackerras newblk = get_slot(info);
4284c35630cSTimur Tabi newblk->start = e;
42914cf11afSPaul Mackerras newblk->size = be - e;
43014cf11afSPaul Mackerras
43114cf11afSPaul Mackerras list_add(&newblk->list, &blk->list);
43214cf11afSPaul Mackerras }
43314cf11afSPaul Mackerras
4344c35630cSTimur Tabi return s;
43514cf11afSPaul Mackerras }
436d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_detach_region);
43714cf11afSPaul Mackerras
4384c35630cSTimur Tabi /* Allocate a block of memory at the specified alignment. The value returned
4394c35630cSTimur Tabi * is an offset into the buffer initialized by rh_init(), or a negative number
4404c35630cSTimur Tabi * if there is an error.
4414c35630cSTimur Tabi */
rh_alloc_align(rh_info_t * info,int size,int alignment,const char * owner)4424c35630cSTimur Tabi unsigned long rh_alloc_align(rh_info_t * info, int size, int alignment, const char *owner)
44314cf11afSPaul Mackerras {
44414cf11afSPaul Mackerras struct list_head *l;
44514cf11afSPaul Mackerras rh_block_t *blk;
44614cf11afSPaul Mackerras rh_block_t *newblk;
4477c8545e9SLi Yang unsigned long start, sp_size;
44814cf11afSPaul Mackerras
4494c35630cSTimur Tabi /* Validate size, and alignment must be power of two */
4505e980823SLi Yang if (size <= 0 || (alignment & (alignment - 1)) != 0)
4514c35630cSTimur Tabi return (unsigned long) -EINVAL;
45214cf11afSPaul Mackerras
45314cf11afSPaul Mackerras /* Align to configured alignment */
45414cf11afSPaul Mackerras size = (size + (info->alignment - 1)) & ~(info->alignment - 1);
45514cf11afSPaul Mackerras
4567c8545e9SLi Yang if (assure_empty(info, 2) < 0)
4574c35630cSTimur Tabi return (unsigned long) -ENOMEM;
45814cf11afSPaul Mackerras
45914cf11afSPaul Mackerras blk = NULL;
46014cf11afSPaul Mackerras list_for_each(l, &info->free_list) {
46114cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
4627c8545e9SLi Yang if (size <= blk->size) {
4637c8545e9SLi Yang start = (blk->start + alignment - 1) & ~(alignment - 1);
4647c8545e9SLi Yang if (start + size <= blk->start + blk->size)
46514cf11afSPaul Mackerras break;
4667c8545e9SLi Yang }
46714cf11afSPaul Mackerras blk = NULL;
46814cf11afSPaul Mackerras }
46914cf11afSPaul Mackerras
47014cf11afSPaul Mackerras if (blk == NULL)
4714c35630cSTimur Tabi return (unsigned long) -ENOMEM;
47214cf11afSPaul Mackerras
47314cf11afSPaul Mackerras /* Just fits */
47414cf11afSPaul Mackerras if (blk->size == size) {
47514cf11afSPaul Mackerras /* Move from free list to taken list */
47614cf11afSPaul Mackerras list_del(&blk->list);
4771c2de47cSTimur Tabi newblk = blk;
4781c2de47cSTimur Tabi } else {
4797c8545e9SLi Yang /* Fragment caused, split if needed */
4807c8545e9SLi Yang /* Create block for fragment in the beginning */
4817c8545e9SLi Yang sp_size = start - blk->start;
4827c8545e9SLi Yang if (sp_size) {
4837c8545e9SLi Yang rh_block_t *spblk;
4847c8545e9SLi Yang
4857c8545e9SLi Yang spblk = get_slot(info);
4867c8545e9SLi Yang spblk->start = blk->start;
4877c8545e9SLi Yang spblk->size = sp_size;
4887c8545e9SLi Yang /* add before the blk */
4897c8545e9SLi Yang list_add(&spblk->list, blk->list.prev);
4907c8545e9SLi Yang }
49114cf11afSPaul Mackerras newblk = get_slot(info);
4927c8545e9SLi Yang newblk->start = start;
49314cf11afSPaul Mackerras newblk->size = size;
49414cf11afSPaul Mackerras
4957c8545e9SLi Yang /* blk still in free list, with updated start and size
4967c8545e9SLi Yang * for fragment in the end */
4977c8545e9SLi Yang blk->start = start + size;
4987c8545e9SLi Yang blk->size -= sp_size + size;
4997c8545e9SLi Yang /* No fragment in the end, remove blk */
5007c8545e9SLi Yang if (blk->size == 0) {
5017c8545e9SLi Yang list_del(&blk->list);
5027c8545e9SLi Yang release_slot(info, blk);
5037c8545e9SLi Yang }
5041c2de47cSTimur Tabi }
50514cf11afSPaul Mackerras
5061c2de47cSTimur Tabi newblk->owner = owner;
50714cf11afSPaul Mackerras attach_taken_block(info, newblk);
50814cf11afSPaul Mackerras
50914cf11afSPaul Mackerras return start;
51014cf11afSPaul Mackerras }
511d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_alloc_align);
51214cf11afSPaul Mackerras
5134c35630cSTimur Tabi /* Allocate a block of memory at the default alignment. The value returned is
5144c35630cSTimur Tabi * an offset into the buffer initialized by rh_init(), or a negative number if
5154c35630cSTimur Tabi * there is an error.
5164c35630cSTimur Tabi */
rh_alloc(rh_info_t * info,int size,const char * owner)5174c35630cSTimur Tabi unsigned long rh_alloc(rh_info_t * info, int size, const char *owner)
5185e980823SLi Yang {
5195e980823SLi Yang return rh_alloc_align(info, size, info->alignment, owner);
5205e980823SLi Yang }
521d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_alloc);
5225e980823SLi Yang
5234c35630cSTimur Tabi /* Allocate a block of memory at the given offset, rounded up to the default
5244c35630cSTimur Tabi * alignment. The value returned is an offset into the buffer initialized by
5254c35630cSTimur Tabi * rh_init(), or a negative number if there is an error.
5264c35630cSTimur Tabi */
rh_alloc_fixed(rh_info_t * info,unsigned long start,int size,const char * owner)5274c35630cSTimur Tabi unsigned long rh_alloc_fixed(rh_info_t * info, unsigned long start, int size, const char *owner)
52814cf11afSPaul Mackerras {
52914cf11afSPaul Mackerras struct list_head *l;
53014cf11afSPaul Mackerras rh_block_t *blk, *newblk1, *newblk2;
5315e980823SLi Yang unsigned long s, e, m, bs = 0, be = 0;
53214cf11afSPaul Mackerras
53314cf11afSPaul Mackerras /* Validate size */
53414cf11afSPaul Mackerras if (size <= 0)
5354c35630cSTimur Tabi return (unsigned long) -EINVAL;
53614cf11afSPaul Mackerras
53714cf11afSPaul Mackerras /* The region must be aligned */
5384c35630cSTimur Tabi s = start;
53914cf11afSPaul Mackerras e = s + size;
54014cf11afSPaul Mackerras m = info->alignment - 1;
54114cf11afSPaul Mackerras
54214cf11afSPaul Mackerras /* Round start up */
54314cf11afSPaul Mackerras s = (s + m) & ~m;
54414cf11afSPaul Mackerras
54514cf11afSPaul Mackerras /* Round end down */
54614cf11afSPaul Mackerras e = e & ~m;
54714cf11afSPaul Mackerras
54814cf11afSPaul Mackerras if (assure_empty(info, 2) < 0)
5494c35630cSTimur Tabi return (unsigned long) -ENOMEM;
55014cf11afSPaul Mackerras
55114cf11afSPaul Mackerras blk = NULL;
55214cf11afSPaul Mackerras list_for_each(l, &info->free_list) {
55314cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
55414cf11afSPaul Mackerras /* The range must lie entirely inside one free block */
5554c35630cSTimur Tabi bs = blk->start;
5564c35630cSTimur Tabi be = blk->start + blk->size;
55714cf11afSPaul Mackerras if (s >= bs && e <= be)
55814cf11afSPaul Mackerras break;
559af4d3643SGuillaume Knispel blk = NULL;
56014cf11afSPaul Mackerras }
56114cf11afSPaul Mackerras
56214cf11afSPaul Mackerras if (blk == NULL)
5634c35630cSTimur Tabi return (unsigned long) -ENOMEM;
56414cf11afSPaul Mackerras
56514cf11afSPaul Mackerras /* Perfect fit */
56614cf11afSPaul Mackerras if (bs == s && be == e) {
56714cf11afSPaul Mackerras /* Move from free list to taken list */
56814cf11afSPaul Mackerras list_del(&blk->list);
56914cf11afSPaul Mackerras blk->owner = owner;
57014cf11afSPaul Mackerras
57114cf11afSPaul Mackerras start = blk->start;
57214cf11afSPaul Mackerras attach_taken_block(info, blk);
57314cf11afSPaul Mackerras
57414cf11afSPaul Mackerras return start;
57514cf11afSPaul Mackerras
57614cf11afSPaul Mackerras }
57714cf11afSPaul Mackerras
57814cf11afSPaul Mackerras /* blk still in free list, with updated start and/or size */
57914cf11afSPaul Mackerras if (bs == s || be == e) {
58014cf11afSPaul Mackerras if (bs == s)
5814c35630cSTimur Tabi blk->start += size;
58214cf11afSPaul Mackerras blk->size -= size;
58314cf11afSPaul Mackerras
58414cf11afSPaul Mackerras } else {
58514cf11afSPaul Mackerras /* The front free fragment */
58614cf11afSPaul Mackerras blk->size = s - bs;
58714cf11afSPaul Mackerras
58814cf11afSPaul Mackerras /* The back free fragment */
58914cf11afSPaul Mackerras newblk2 = get_slot(info);
5904c35630cSTimur Tabi newblk2->start = e;
59114cf11afSPaul Mackerras newblk2->size = be - e;
59214cf11afSPaul Mackerras
59314cf11afSPaul Mackerras list_add(&newblk2->list, &blk->list);
59414cf11afSPaul Mackerras }
59514cf11afSPaul Mackerras
59614cf11afSPaul Mackerras newblk1 = get_slot(info);
5974c35630cSTimur Tabi newblk1->start = s;
59814cf11afSPaul Mackerras newblk1->size = e - s;
59914cf11afSPaul Mackerras newblk1->owner = owner;
60014cf11afSPaul Mackerras
60114cf11afSPaul Mackerras start = newblk1->start;
60214cf11afSPaul Mackerras attach_taken_block(info, newblk1);
60314cf11afSPaul Mackerras
60414cf11afSPaul Mackerras return start;
60514cf11afSPaul Mackerras }
606d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_alloc_fixed);
60714cf11afSPaul Mackerras
6084c35630cSTimur Tabi /* Deallocate the memory previously allocated by one of the rh_alloc functions.
6094c35630cSTimur Tabi * The return value is the size of the deallocated block, or a negative number
6104c35630cSTimur Tabi * if there is an error.
6114c35630cSTimur Tabi */
rh_free(rh_info_t * info,unsigned long start)6124c35630cSTimur Tabi int rh_free(rh_info_t * info, unsigned long start)
61314cf11afSPaul Mackerras {
61414cf11afSPaul Mackerras rh_block_t *blk, *blk2;
61514cf11afSPaul Mackerras struct list_head *l;
61614cf11afSPaul Mackerras int size;
61714cf11afSPaul Mackerras
61814cf11afSPaul Mackerras /* Linear search for block */
61914cf11afSPaul Mackerras blk = NULL;
62014cf11afSPaul Mackerras list_for_each(l, &info->taken_list) {
62114cf11afSPaul Mackerras blk2 = list_entry(l, rh_block_t, list);
62214cf11afSPaul Mackerras if (start < blk2->start)
62314cf11afSPaul Mackerras break;
62414cf11afSPaul Mackerras blk = blk2;
62514cf11afSPaul Mackerras }
62614cf11afSPaul Mackerras
62714cf11afSPaul Mackerras if (blk == NULL || start > (blk->start + blk->size))
62814cf11afSPaul Mackerras return -EINVAL;
62914cf11afSPaul Mackerras
63014cf11afSPaul Mackerras /* Remove from taken list */
63114cf11afSPaul Mackerras list_del(&blk->list);
63214cf11afSPaul Mackerras
63314cf11afSPaul Mackerras /* Get size of freed block */
63414cf11afSPaul Mackerras size = blk->size;
63514cf11afSPaul Mackerras attach_free_block(info, blk);
63614cf11afSPaul Mackerras
63714cf11afSPaul Mackerras return size;
63814cf11afSPaul Mackerras }
639d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_free);
64014cf11afSPaul Mackerras
rh_get_stats(rh_info_t * info,int what,int max_stats,rh_stats_t * stats)64114cf11afSPaul Mackerras int rh_get_stats(rh_info_t * info, int what, int max_stats, rh_stats_t * stats)
64214cf11afSPaul Mackerras {
64314cf11afSPaul Mackerras rh_block_t *blk;
64414cf11afSPaul Mackerras struct list_head *l;
64514cf11afSPaul Mackerras struct list_head *h;
64614cf11afSPaul Mackerras int nr;
64714cf11afSPaul Mackerras
64814cf11afSPaul Mackerras switch (what) {
64914cf11afSPaul Mackerras
65014cf11afSPaul Mackerras case RHGS_FREE:
65114cf11afSPaul Mackerras h = &info->free_list;
65214cf11afSPaul Mackerras break;
65314cf11afSPaul Mackerras
65414cf11afSPaul Mackerras case RHGS_TAKEN:
65514cf11afSPaul Mackerras h = &info->taken_list;
65614cf11afSPaul Mackerras break;
65714cf11afSPaul Mackerras
65814cf11afSPaul Mackerras default:
65914cf11afSPaul Mackerras return -EINVAL;
66014cf11afSPaul Mackerras }
66114cf11afSPaul Mackerras
66214cf11afSPaul Mackerras /* Linear search for block */
66314cf11afSPaul Mackerras nr = 0;
66414cf11afSPaul Mackerras list_for_each(l, h) {
66514cf11afSPaul Mackerras blk = list_entry(l, rh_block_t, list);
66614cf11afSPaul Mackerras if (stats != NULL && nr < max_stats) {
66714cf11afSPaul Mackerras stats->start = blk->start;
66814cf11afSPaul Mackerras stats->size = blk->size;
66914cf11afSPaul Mackerras stats->owner = blk->owner;
67014cf11afSPaul Mackerras stats++;
67114cf11afSPaul Mackerras }
67214cf11afSPaul Mackerras nr++;
67314cf11afSPaul Mackerras }
67414cf11afSPaul Mackerras
67514cf11afSPaul Mackerras return nr;
67614cf11afSPaul Mackerras }
677d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_get_stats);
67814cf11afSPaul Mackerras
rh_set_owner(rh_info_t * info,unsigned long start,const char * owner)6794c35630cSTimur Tabi int rh_set_owner(rh_info_t * info, unsigned long start, const char *owner)
68014cf11afSPaul Mackerras {
68114cf11afSPaul Mackerras rh_block_t *blk, *blk2;
68214cf11afSPaul Mackerras struct list_head *l;
68314cf11afSPaul Mackerras int size;
68414cf11afSPaul Mackerras
68514cf11afSPaul Mackerras /* Linear search for block */
68614cf11afSPaul Mackerras blk = NULL;
68714cf11afSPaul Mackerras list_for_each(l, &info->taken_list) {
68814cf11afSPaul Mackerras blk2 = list_entry(l, rh_block_t, list);
68914cf11afSPaul Mackerras if (start < blk2->start)
69014cf11afSPaul Mackerras break;
69114cf11afSPaul Mackerras blk = blk2;
69214cf11afSPaul Mackerras }
69314cf11afSPaul Mackerras
69414cf11afSPaul Mackerras if (blk == NULL || start > (blk->start + blk->size))
69514cf11afSPaul Mackerras return -EINVAL;
69614cf11afSPaul Mackerras
69714cf11afSPaul Mackerras blk->owner = owner;
69814cf11afSPaul Mackerras size = blk->size;
69914cf11afSPaul Mackerras
70014cf11afSPaul Mackerras return size;
70114cf11afSPaul Mackerras }
702d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_set_owner);
70314cf11afSPaul Mackerras
rh_dump(rh_info_t * info)70414cf11afSPaul Mackerras void rh_dump(rh_info_t * info)
70514cf11afSPaul Mackerras {
70614cf11afSPaul Mackerras static rh_stats_t st[32]; /* XXX maximum 32 blocks */
70714cf11afSPaul Mackerras int maxnr;
70814cf11afSPaul Mackerras int i, nr;
70914cf11afSPaul Mackerras
7103839a594SAhmed S. Darwish maxnr = ARRAY_SIZE(st);
71114cf11afSPaul Mackerras
71214cf11afSPaul Mackerras printk(KERN_INFO
71314cf11afSPaul Mackerras "info @0x%p (%d slots empty / %d max)\n",
71414cf11afSPaul Mackerras info, info->empty_slots, info->max_blocks);
71514cf11afSPaul Mackerras
71614cf11afSPaul Mackerras printk(KERN_INFO " Free:\n");
71714cf11afSPaul Mackerras nr = rh_get_stats(info, RHGS_FREE, maxnr, st);
71814cf11afSPaul Mackerras if (nr > maxnr)
71914cf11afSPaul Mackerras nr = maxnr;
72014cf11afSPaul Mackerras for (i = 0; i < nr; i++)
72114cf11afSPaul Mackerras printk(KERN_INFO
7224c35630cSTimur Tabi " 0x%lx-0x%lx (%u)\n",
7234c35630cSTimur Tabi st[i].start, st[i].start + st[i].size,
72414cf11afSPaul Mackerras st[i].size);
72514cf11afSPaul Mackerras printk(KERN_INFO "\n");
72614cf11afSPaul Mackerras
72714cf11afSPaul Mackerras printk(KERN_INFO " Taken:\n");
72814cf11afSPaul Mackerras nr = rh_get_stats(info, RHGS_TAKEN, maxnr, st);
72914cf11afSPaul Mackerras if (nr > maxnr)
73014cf11afSPaul Mackerras nr = maxnr;
73114cf11afSPaul Mackerras for (i = 0; i < nr; i++)
73214cf11afSPaul Mackerras printk(KERN_INFO
7334c35630cSTimur Tabi " 0x%lx-0x%lx (%u) %s\n",
7344c35630cSTimur Tabi st[i].start, st[i].start + st[i].size,
73514cf11afSPaul Mackerras st[i].size, st[i].owner != NULL ? st[i].owner : "");
73614cf11afSPaul Mackerras printk(KERN_INFO "\n");
73714cf11afSPaul Mackerras }
738d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_dump);
73914cf11afSPaul Mackerras
rh_dump_blk(rh_info_t * info,rh_block_t * blk)74014cf11afSPaul Mackerras void rh_dump_blk(rh_info_t * info, rh_block_t * blk)
74114cf11afSPaul Mackerras {
74214cf11afSPaul Mackerras printk(KERN_INFO
7434c35630cSTimur Tabi "blk @0x%p: 0x%lx-0x%lx (%u)\n",
7444c35630cSTimur Tabi blk, blk->start, blk->start + blk->size, blk->size);
74514cf11afSPaul Mackerras }
746d4697af4SSylvain Munaut EXPORT_SYMBOL_GPL(rh_dump_blk);
747d4697af4SSylvain Munaut
748