/* * 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; 	size = max(size, 1 << ALLOC_MIN_SHIFT);	i = fls(size - 1);	s = 1 << i;	j = i -= ALLOC_MIN_SHIFT; 	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; 	size = max(size, 1 << ALLOC_MIN_SHIFT);	i = fls(size - 1);	s = 1 << i;	i -= ALLOC_MIN_SHIFT; 	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);