1 files changed, 188 insertions, 0 deletions
diff --git a/lib/genalloc.c b/lib/genalloc.c
new file mode 100644
index 000000000000..d6d30d2e7166
--- /dev/null
+++ b/lib/genalloc.c
@@ -0,0 +1,188 @@
+/*
+ * Basic general purpose allocator for managing special purpose memory
+ * not managed by the regular kmalloc/kfree interface.
+ * Uses for this includes on-device special memory, uncached memory
+ * etc.
+ *
+ * This code is based on the buddy allocator found in the sym53c8xx_2
+ * driver Copyright (C) 1999-2001  Gerard Roudier <groudier@free.fr>,
+ * and adapted for general purpose use.
+ *
+ * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
+#include <linux/module.h>
+#include <linux/stddef.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/slab.h>
+#include <linux/init.h>
+#include <linux/mm.h>
+#include <linux/spinlock.h>
+#include <linux/genalloc.h>
+#include <asm/page.h>
+struct gen_pool *gen_pool_create(int nr_chunks, int max_chunk_shift,
+                                 unsigned long (*fp)(struct gen_pool *),
+                                 unsigned long data)
+{
+        struct gen_pool *poolp;
+        unsigned long tmp;
+        int i;
+        /*
+         * This is really an arbitrary limit, +10 is enough for
+         * IA64_GRANULE_SHIFT, aka 16MB. If anyone needs a large limit
+         * this can be increased without problems.
+         */
+        if ((max_chunk_shift > (PAGE_SHIFT + 10)) ||
+            ((max_chunk_shift < ALLOC_MIN_SHIFT) && max_chunk_shift))
+                return NULL;
+        if (!max_chunk_shift)
+                max_chunk_shift = PAGE_SHIFT;
+        poolp = kmalloc(sizeof(struct gen_pool), GFP_KERNEL);
+        if (!poolp)
+                return NULL;
+        memset(poolp, 0, sizeof(struct gen_pool));
+        poolp->h = kmalloc(sizeof(struct gen_pool_link) *
+                           (max_chunk_shift - ALLOC_MIN_SHIFT + 1),
+                           GFP_KERNEL);
+        if (!poolp->h) {
+                printk(KERN_WARNING "gen_pool_alloc() failed to allocate\n");
+                kfree(poolp);
+                return NULL;
+        }
+        memset(poolp->h, 0, sizeof(struct gen_pool_link) *
+               (max_chunk_shift - ALLOC_MIN_SHIFT + 1));
+        spin_lock_init(&poolp->lock);
+        poolp->get_new_chunk = fp;
+        poolp->max_chunk_shift = max_chunk_shift;
+        poolp->private = data;
+        for (i = 0; i < nr_chunks; i++) {
+                tmp = poolp->get_new_chunk(poolp);
+                printk(KERN_INFO "allocated %lx\n", tmp);
+                if (!tmp)
+                        break;
+                gen_pool_free(poolp, tmp, (1 << poolp->max_chunk_shift));
+        }
+        return poolp;
+}
+EXPORT_SYMBOL(gen_pool_create);
+/*
+ *  Simple power of two buddy-like generic allocator.
+ *  Provides naturally aligned memory chunks.
+ */
+unsigned long gen_pool_alloc(struct gen_pool *poolp, int size)
+{
+        int j, i, s, max_chunk_size;
+        unsigned long a, flags;
+        struct gen_pool_link *h = poolp->h;
+        max_chunk_size = 1 << poolp->max_chunk_shift;
+        if (size > max_chunk_size)
+                return 0;
+        i = 0;
+        size = max(size, 1 << ALLOC_MIN_SHIFT);
+        s = roundup_pow_of_two(size);
+        j = i;
+        spin_lock_irqsave(&poolp->lock, flags);
+        while (!h[j].next) {
+                if (s == max_chunk_size) {
+                        struct gen_pool_link *ptr;
+                        spin_unlock_irqrestore(&poolp->lock, flags);
+                        ptr = (struct gen_pool_link *)poolp->get_new_chunk(poolp);
+                        spin_lock_irqsave(&poolp->lock, flags);
+                        h[j].next = ptr;
+                        if (h[j].next)
+                                h[j].next->next = NULL;
+                        break;
+                }
+                j++;
+                s <<= 1;
+        }
+        a = (unsigned long) h[j].next;
+        if (a) {
+                h[j].next = h[j].next->next;
+                /*
+                 * This should be split into a seperate function doing
+                 * the chunk split in order to support custom
+                 * handling memory not physically accessible by host
+                 */
+                while (j > i) {
+                        j -= 1;
+                        s >>= 1;
+                        h[j].next = (struct gen_pool_link *) (a + s);
+                        h[j].next->next = NULL;
+                }
+        }
+        spin_unlock_irqrestore(&poolp->lock, flags);
+        return a;
+}
+EXPORT_SYMBOL(gen_pool_alloc);
+/*
+ *  Counter-part of the generic allocator.
+ */
+void gen_pool_free(struct gen_pool *poolp, unsigned long ptr, int size)
+{
+        struct gen_pool_link *q;
+        struct gen_pool_link *h = poolp->h;
+        unsigned long a, b, flags;
+        int i, s, max_chunk_size;
+        max_chunk_size = 1 << poolp->max_chunk_shift;
+        if (size > max_chunk_size)
+                return;
+        i = 0;
+        size = max(size, 1 << ALLOC_MIN_SHIFT);
+        s = roundup_pow_of_two(size);
+        a = ptr;
+        spin_lock_irqsave(&poolp->lock, flags);
+        while (1) {
+                if (s == max_chunk_size) {
+                        ((struct gen_pool_link *)a)->next = h[i].next;
+                        h[i].next = (struct gen_pool_link *)a;
+                        break;
+                }
+                b = a ^ s;
+                q = &h[i];
+                while (q->next && q->next != (struct gen_pool_link *)b)
+                        q = q->next;
+                if (!q->next) {
+                        ((struct gen_pool_link *)a)->next = h[i].next;
+                        h[i].next = (struct gen_pool_link *)a;
+                        break;
+                }
+                q->next = q->next->next;
+                a = a & b;
+                s <<= 1;
+                i++;
+        }
+        spin_unlock_irqrestore(&poolp->lock, flags);
+}
+EXPORT_SYMBOL(gen_pool_free);

diff --git a/lib/genalloc.c b/lib/genalloc.c new file mode 100644 index 000000000000..d6d30d2e7166 --- /dev/null +++ b/lib/genalloc.c
@@ -0,0 +1,188 @@
	1	/*
	2	* Basic general purpose allocator for managing special purpose memory
	3	* not managed by the regular kmalloc/kfree interface.
	4	* Uses for this includes on-device special memory, uncached memory
	5	* etc.
	6	*
	7	* This code is based on the buddy allocator found in the sym53c8xx_2
	8	* driver Copyright (C) 1999-2001 Gerard Roudier <groudier@free.fr>,
	9	* and adapted for general purpose use.
	10	*
	11	* Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
	12	*
	13	* This source code is licensed under the GNU General Public License,
	14	* Version 2. See the file COPYING for more details.
	15	*/
	16
	17	#include <linux/module.h>
	18	#include <linux/stddef.h>
	19	#include <linux/kernel.h>
	20	#include <linux/string.h>
	21	#include <linux/slab.h>
	22	#include <linux/init.h>
	23	#include <linux/mm.h>
	24	#include <linux/spinlock.h>
	25	#include <linux/genalloc.h>
	26
	27	#include <asm/page.h>
	28
	29
	30	struct gen_pool *gen_pool_create(int nr_chunks, int max_chunk_shift,
	31	unsigned long (fp)(struct gen_pool ),
	32	unsigned long data)
	33	{
	34	struct gen_pool *poolp;
	35	unsigned long tmp;
	36	int i;
	37
	38	/*
	39	* This is really an arbitrary limit, +10 is enough for
	40	* IA64_GRANULE_SHIFT, aka 16MB. If anyone needs a large limit
	41	* this can be increased without problems.
	42	*/
	43	if ((max_chunk_shift > (PAGE_SHIFT + 10)) \|\|
	44	((max_chunk_shift < ALLOC_MIN_SHIFT) && max_chunk_shift))
	45	return NULL;
	46
	47	if (!max_chunk_shift)
	48	max_chunk_shift = PAGE_SHIFT;
	49
	50	poolp = kmalloc(sizeof(struct gen_pool), GFP_KERNEL);
	51	if (!poolp)
	52	return NULL;
	53	memset(poolp, 0, sizeof(struct gen_pool));
	54	poolp->h = kmalloc(sizeof(struct gen_pool_link) *
	55	(max_chunk_shift - ALLOC_MIN_SHIFT + 1),
	56	GFP_KERNEL);
	57	if (!poolp->h) {
	58	printk(KERN_WARNING "gen_pool_alloc() failed to allocate\n");
	59	kfree(poolp);
	60	return NULL;
	61	}
	62	memset(poolp->h, 0, sizeof(struct gen_pool_link) *
	63	(max_chunk_shift - ALLOC_MIN_SHIFT + 1));
	64
	65	spin_lock_init(&poolp->lock);
	66	poolp->get_new_chunk = fp;
	67	poolp->max_chunk_shift = max_chunk_shift;
	68	poolp->private = data;
	69
	70	for (i = 0; i < nr_chunks; i++) {
	71	tmp = poolp->get_new_chunk(poolp);
	72	printk(KERN_INFO "allocated %lx\n", tmp);
	73	if (!tmp)
	74	break;
	75	gen_pool_free(poolp, tmp, (1 << poolp->max_chunk_shift));
	76	}
	77
	78	return poolp;
	79	}
	80	EXPORT_SYMBOL(gen_pool_create);
	81
	82
	83	/*
	84	* Simple power of two buddy-like generic allocator.
	85	* Provides naturally aligned memory chunks.
	86	*/
	87	unsigned long gen_pool_alloc(struct gen_pool *poolp, int size)
	88	{
	89	int j, i, s, max_chunk_size;
	90	unsigned long a, flags;
	91	struct gen_pool_link *h = poolp->h;
	92
	93	max_chunk_size = 1 << poolp->max_chunk_shift;
	94
	95	if (size > max_chunk_size)
	96	return 0;
	97
	98	i = 0;
	99
	100	size = max(size, 1 << ALLOC_MIN_SHIFT);
	101	s = roundup_pow_of_two(size);
	102
	103	j = i;
	104
	105	spin_lock_irqsave(&poolp->lock, flags);
	106	while (!h[j].next) {
	107	if (s == max_chunk_size) {
	108	struct gen_pool_link *ptr;
	109	spin_unlock_irqrestore(&poolp->lock, flags);
	110	ptr = (struct gen_pool_link *)poolp->get_new_chunk(poolp);
	111	spin_lock_irqsave(&poolp->lock, flags);
	112	h[j].next = ptr;
	113	if (h[j].next)
	114	h[j].next->next = NULL;
	115	break;
	116	}
	117	j++;
	118	s <<= 1;
	119	}
	120	a = (unsigned long) h[j].next;
	121	if (a) {
	122	h[j].next = h[j].next->next;
	123	/*
	124	* This should be split into a seperate function doing
	125	* the chunk split in order to support custom
	126	* handling memory not physically accessible by host
	127	*/
	128	while (j > i) {
	129	j -= 1;
	130	s >>= 1;
	131	h[j].next = (struct gen_pool_link *) (a + s);
	132	h[j].next->next = NULL;
	133	}
	134	}
	135	spin_unlock_irqrestore(&poolp->lock, flags);
	136	return a;
	137	}
	138	EXPORT_SYMBOL(gen_pool_alloc);
	139
	140
	141	/*
	142	* Counter-part of the generic allocator.
	143	*/
	144	void gen_pool_free(struct gen_pool *poolp, unsigned long ptr, int size)
	145	{
	146	struct gen_pool_link *q;
	147	struct gen_pool_link *h = poolp->h;
	148	unsigned long a, b, flags;
	149	int i, s, max_chunk_size;
	150
	151	max_chunk_size = 1 << poolp->max_chunk_shift;
	152
	153	if (size > max_chunk_size)
	154	return;
	155
	156	i = 0;
	157
	158	size = max(size, 1 << ALLOC_MIN_SHIFT);
	159	s = roundup_pow_of_two(size);
	160
	161	a = ptr;
	162
	163	spin_lock_irqsave(&poolp->lock, flags);
	164	while (1) {
	165	if (s == max_chunk_size) {
	166	((struct gen_pool_link *)a)->next = h[i].next;
	167	h[i].next = (struct gen_pool_link *)a;
	168	break;
	169	}
	170	b = a ^ s;
	171	q = &h[i];
	172
	173	while (q->next && q->next != (struct gen_pool_link *)b)
	174	q = q->next;
	175
	176	if (!q->next) {
	177	((struct gen_pool_link *)a)->next = h[i].next;
	178	h[i].next = (struct gen_pool_link *)a;
	179	break;
	180	}
	181	q->next = q->next->next;
	182	a = a & b;
	183	s <<= 1;
	184	i++;
	185	}
	186	spin_unlock_irqrestore(&poolp->lock, flags);
	187	}
	188	EXPORT_SYMBOL(gen_pool_free);