/* * malloc.c --- a general purpose kernel memory allocator for Linux. *  * Written by Theodore Ts'o (tytso@mit.edu), 11/29/91 * * This routine is written to be as fast as possible, so that it * can be called from the interrupt level. * * Limitations: maximum size of memory we can allocate using this routine *	is 4k, the size of a page in Linux. * * The general game plan is that each page (called a bucket) will only hold * objects of a given size.  When all of the object on a page are released, * the page can be returned to the general free pool.  When malloc() is * called, it looks for the smallest bucket size which will fulfill its * request, and allocate a piece of memory from that bucket pool. * * Each bucket has as its control block a bucket descriptor which keeps  * track of how many objects are in use on that page, and the free list * for that page.  Like the buckets themselves, bucket descriptors are * stored on pages requested from get_free_page().  However, unlike buckets, * pages devoted to bucket descriptor pages are never released back to the * system.  Fortunately, a system should probably only need 1 or 2 bucket * descriptor pages, since a page can hold 256 bucket descriptors (which * corresponds to 1 megabyte worth of bucket pages.)  If the kernel is using  * that much allocated memory, it's probably doing something wrong.  :-) * * Note: malloc() and free() both call get_free_page() and free_page() *	in sections of code where interrupts are turned off, to allow *	malloc() and free() to be safely called from an interrupt routine. *	(We will probably need this functionality when networking code, *	particularily things like NFS, is added to Linux.)  However, this *	presumes that get_free_page() and free_page() are interrupt-level *	safe, which they may not be once paging is added.  If this is the *	case, we will need to modify malloc() to keep a few unused pages *	"pre-allocated" so that it can safely draw upon those pages if * 	it is called from an interrupt routine. * * 	Another concern is that get_free_page() should not sleep; if it  *	does, the code is carefully ordered so as to avoid any race  *	conditions.  The catch is that if malloc() is called re-entrantly,  *	there is a chance that unecessary pages will be grabbed from the  *	system.  Except for the pages for the bucket descriptor page, the  *	extra pages will eventually get released back to the system, though, *	so it isn't all that bad. */#include <linux/kernel.h>#include <linux/mm.h>#include <asm/system.h>struct bucket_desc {	/* 16 bytes */	void			*page;	struct bucket_desc	*next;	void			*freeptr;	unsigned short		refcnt;	unsigned short		bucket_size;};struct _bucket_dir {	/* 8 bytes */	int			size;	struct bucket_desc	*chain;};/* * The following is the where we store a pointer to the first bucket * descriptor for a given size.   * * If it turns out that the Linux kernel allocates a lot of objects of a * specific size, then we may want to add that specific size to this list, * since that will allow the memory to be allocated more efficiently. * However, since an entire page must be dedicated to each specific size * on this list, some amount of temperance must be exercised here. * * Note that this list *must* be kept in order. */struct _bucket_dir bucket_dir[] = {	{ 16,	(struct bucket_desc *) 0},	{ 32,	(struct bucket_desc *) 0},	{ 64,	(struct bucket_desc *) 0},	{ 128,	(struct bucket_desc *) 0},	{ 256,	(struct bucket_desc *) 0},	{ 512,	(struct bucket_desc *) 0},	{ 1024,	(struct bucket_desc *) 0},	{ 2048, (struct bucket_desc *) 0},	{ 4096, (struct bucket_desc *) 0},	{ 0,    (struct bucket_desc *) 0}};   /* End of list marker *//* * This contains a linked list of free bucket descriptor blocks */struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;/* * This routine initializes a bucket description page. */static inline void init_bucket_desc(){	struct bucket_desc *bdesc, *first;	int	i;		first = bdesc = (struct bucket_desc *) get_free_page();	if (!bdesc)		panic("Out of memory in init_bucket_desc()");	for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {		bdesc->next = bdesc+1;		bdesc++;	}	/*	 * This is done last, to avoid race conditions in case 	 * get_free_page() sleeps and this routine gets called again....	 */	bdesc->next = free_bucket_desc;	free_bucket_desc = first;}void *malloc(unsigned int len){	struct _bucket_dir	*bdir;	struct bucket_desc	*bdesc;	void			*retval;	/*	 * First we search the bucket_dir to find the right bucket change	 * for this request.	 */	for (bdir = bucket_dir; bdir->size; bdir++)		if (bdir->size >= len)			break;	if (!bdir->size) {		printk("malloc called with impossibly large argument (%d)\n",			len);		panic("malloc: bad arg");	}	/*	 * Now we search for a bucket descriptor which has free space	 */	cli();	/* Avoid race conditions */	for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) 		if (bdesc->freeptr)			break;	/*	 * If we didn't find a bucket with free space, then we'll 	 * allocate a new one.	 */	if (!bdesc) {		char		*cp;		int		i;		if (!free_bucket_desc)				init_bucket_desc();		bdesc = free_bucket_desc;		free_bucket_desc = bdesc->next;		bdesc->refcnt = 0;		bdesc->bucket_size = bdir->size;		bdesc->page = bdesc->freeptr = (void *) cp = get_free_page();		if (!cp)			panic("Out of memory in kernel malloc()");		/* Set up the chain of free objects */		for (i=PAGE_SIZE/bdir->size; i > 1; i--) {			*((char **) cp) = cp + bdir->size;			cp += bdir->size;		}		*((char **) cp) = 0;		bdesc->next = bdir->chain; /* OK, link it in! */		bdir->chain = bdesc;	}	retval = (void *) bdesc->freeptr;	bdesc->freeptr = *((void **) retval);	bdesc->refcnt++;	sti();	/* OK, we're safe again */	return(retval);}/* * Here is the free routine.  If you know the size of the object that you * are freeing, then free_s() will use that information to speed up the * search for the bucket descriptor. *  * We will #define a macro so that "free(x)" is becomes "free_s(x, 0)" */void free_s(void *obj, int size){	void		*page;	struct _bucket_dir	*bdir;	struct bucket_desc	*bdesc, *prev;	/* Calculate what page this object lives in */	page = (void *)  ((unsigned long) obj & 0xfffff000);	/* Now search the buckets looking for that page */	for (bdir = bucket_dir; bdir->size; bdir++) {		prev = 0;		/* If size is zero then this conditional is always false */		if (bdir->size < size)			continue;		for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {			if (bdesc->page == page) 				goto found;			prev = bdesc;		}	}	panic("Bad address passed to kernel free_s()");found:	cli(); /* To avoid race conditions */	*((void **)obj) = bdesc->freeptr;	bdesc->freeptr = obj;	bdesc->refcnt--;	if (bdesc->refcnt == 0) {		/*		 * We need to make sure that prev is still accurate.  It		 * may not be, if someone rudely interrupted us....		 */		if ((prev && (prev->next != bdesc)) ||		    (!prev && (bdir->chain != bdesc)))			for (prev = bdir->chain; prev; prev = prev->next)				if (prev->next == bdesc)					break;		if (prev)			prev->next = bdesc->next;		else {			if (bdir->chain != bdesc)				panic("malloc bucket chains corrupted");			bdir->chain = bdesc->next;		}		free_page((unsigned long) bdesc->page);		bdesc->next = free_bucket_desc;		free_bucket_desc = bdesc;	}	sti();	return;}