/* * 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);