malloc.c

os arm os arm os arm os arm os arm os arm os arm os arm os arm os arm os arm os arm os arm os arm

/*
 *	ApOS (Another Project software for s3c2410)
 *	
 *	This program is free software; you can redistribute it and/or modify
 *	it under the terms of the GNU General Public License version 2 as
 *	published by the Free Software Foundation.
 *			
 *						Copyright caiyuqing
 *
 *	kmalloc和kfree_s两个函数参考了 Theodore Ts'o为linux0.11
 *	编制的malloc和free_s函数，可以看到其中绝大多数的代码是一
 *	样的。 : )
 *				
 *							
 */
#include "../include/mm/mm.h"

#define _MALLOC_DEBUG

#define NULL ((unsigned int *)0);

struct bucket_desc 
{
	void			*page;
	struct bucket_desc	*next;
	void			*freeptr;
	unsigned short		refcnt;
	unsigned short		bucket_size;
};

struct _bucket_dir 
{
	int			size;
	struct bucket_desc	*chain;
};

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}
};

static struct bucket_desc *free_bucket_desc;

void init_kmalloc()
{
	int i;
	int mul;
	
	free_bucket_desc = (struct bucket_desc *)0;

	for(mul=1,i=0;i<10;mul*=2,i++)
	{
		 bucket_dir[i].chain=(struct bucket_desc *)0;
		 bucket_dir[i].size=mul*16;
	}

	bucket_dir[9].size=0;

}

int init_bucket_desc()
{
	struct bucket_desc *bdesc, *first;
	int i;

	first = bdesc = (struct bucket_desc *)get_free_physical_page();
	if (!bdesc)
	{
		return 1;
	}
	
	for(i=0;i<PAGE_SIZE/sizeof(struct bucket_desc);i++)
	{
		bdesc->next = bdesc+1;
		bdesc++;
	}

	bdesc->next = free_bucket_desc;
	free_bucket_desc = first;

#ifdef _MALLOC_DEBUG
	printk("free_bucket_desc address: 0x%0x\n",free_bucket_desc);
#endif
	return 0;
}

void *kmalloc(unsigned int len)
{
	struct _bucket_dir	*bdir;
	struct bucket_desc	*bdesc;
	void			*retval;
	
	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);
		return NULL;
	}
	
	irq_disable();
	
	for(bdesc=bdir->chain;bdesc;bdesc=bdesc->next)
	{
		if(bdesc->freeptr)
			break;
	}
	
	if(!bdesc)
	{
		char *cp;
		int i;
		unsigned int tmp;
		unsigned int *dir_entry;
		unsigned int *page_entry;
		
		if(!free_bucket_desc)
		{
			init_bucket_desc();
		}
		bdesc=free_bucket_desc;
		free_bucket_desc=bdesc->next;
		
		bdesc->refcnt=0;
		bdesc->bucket_size=bdir->size;
		cp=(void *)get_free_physical_page();
		
		//将该页的访问属性设置为用户状态可读写
		tmp=(unsigned int *)cp;
		
		dir_entry=(unsigned int *)DIRECTORY_BASE+(tmp>>20);
		page_entry=(unsigned int *)(*dir_entry&0xFFFFFC00)+((tmp>>12)&0xff);
		
		*page_entry=*page_entry&(0xfffff000);
		*page_entry=*page_entry|USER_SMALL_PAGE_DESC_RW|CACHEABLE;
	
		
		bdesc->page=bdesc->freeptr=(void *)cp;
		
		if(!cp)
			panic("error:kmalloc() out of memory.\n");

		for(i=0;i<PAGE_SIZE/bdir->size-1;i++)
		{

			*((char **)cp)=cp+bdir->size;
			cp+=bdir->size;
		}
		*((char **)cp)=0;
		bdesc->next=bdir->chain;
		bdir->chain=bdesc;
	}

	retval=(void *)bdesc->freeptr;
	bdesc->freeptr=*((void **)retval);
	bdesc->refcnt++;
	
	irq_enable() ;
	
	//刷新 TLB
	invalidate_TLBs();

	return retval;
}

void kfree_s(void *obj,int size)
{
	void *page;
	struct _bucket_dir	*bdir;
	struct bucket_desc	*bdesc,*prev;
	
	//计算出obj所属的页面
	page=(void *)((unsigned int)obj&0xfffff000);
#ifdef _MALLOC_DEBUG
		printk("obj on page: 0x%0x\n",page);
#endif	
	//搜索存储桶目录项所连接的描述符，寻找该页面
	for(bdir=bucket_dir;bdir->size;bdir++)
	{
		prev=0;
		
		if(bdir->size<size)
			continue;
		
		for(bdesc=bdir->chain;bdesc;bdesc=bdesc->next)
		{
			if(bdesc->page==page)
			{
				goto found;
				prev=bdesc;
			}
		}		
	}
	panic("error: kfree_s(void *obj,int size): \
		Bad address.\n");

found:
		
	irq_disable();
	
	*((void **)obj)=bdesc->freeptr;
	bdesc->freeptr=obj;
	bdesc->refcnt--;
	
	if(bdesc->refcnt==0)
	{
		
#ifdef _MALLOC_DEBUG
		printk("free_page: 0x%0x\n",bdesc->page);
#endif

		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("error: kfree_s(void *obj,int size): \
					bucket chains corrupted.\n");
			bdir->chain=bdesc->next;
		}
		
		free_physical_page(bdesc->page);
		bdesc->next=free_bucket_desc;
		free_bucket_desc=bdesc;
	
	}
	
	irq_enable();
	
	return;
}