hole.c

参照MINIX3写的操作系统 用GCC+NASM+BOCHS开发

#include "../include/toyos.h"
#include "hole.h"

/*This file include memory Memory Mamager.
ToyOS's(This OS)Memory Mamage use Minix's Algorithms.
When ToyOS start,the whole available memory looked as a hole.
When other task request memory ,the Memory Mamager will find a hole that it's size equale
the request's at first.If this failed ,Memory Mamager will find a hole that it's size 
bigger than request's but littlest in the hole link.
Now we find a right hole,Memory Mamager will cut the hole into two pieces and one of them
will be return the request task.The Other one will be link the hole link.
Edit by ToyOS
Date: 2007-9-19*/

/*Initialize，get memSize,memStart,memEnd from outside*/
PUBLIC void memInit(t32 start,t32 size)
{		
	int i=0;
	memStart=start;	
	memSize=size;
	printk("memStart %x ",memStart);
	printk("size %d ",size);
	/*初始化hole 结构体分配器*/
	if(mallocStructAlloc(STRUCT_HOLE,sizeof(hole),MEM_START+0x800,0xC00)== -1)
		printk("mallocStructAlloc Error!\n");
	/*when the ToyOS begin ,the while available memory be looked as a hole */
    	head=(hole*)mmalloc();
	printk("head %x",head);
	head->start=start;
	head->size=memSize;
	printk("memSize %d ",memSize);
	head->next=NULL;
	last=head;
}

/*
Find a hole that it's size equal to the retuest size,
if failed ,it will cut the hole .
*/

PRIVATE t32 findHole(t32 size)
{
	t32 mimSize=0;
	t32 addr;
	/*从上次搜索成功的地方开始*/
	hole *flag=last;
	hole *p=last,*mimP=NULL;
	if(!p)
		return ERROR;
	if(p->size>=size)
	{
		mimP=p;
		mimSize=p->size;
	}
	while(1)
	{
		if(p->size==size)
			return p->start;
		/*大于size并最接近size的hole*/
		if(p->size>size)
			if(p->size<mimSize)
			{
				mimSize=p->size;
				mimP=p;
			}
		p=p->next;
		if(p==NULL)
			p=head;
		if(p==last)
			break;
	}
	if(mimP==NULL)
		return ERROR;
	/*没找到合适的，只好分割了*/
	addr=mimP->start;
	mimP->start+=size;
	mimP->size-=size;
	last=mimP;
    return addr;
}

/*Interface,this function will return the begin address of the request memory */
PUBLIC t32 memAlloc(t32 size)
{
	if(size>memSize)
		return ERROR;
   	return findHole(size);
}

/*合并hole*/
PRIVATE t32  unitHole(t32 addr,t32 size)
{
	int i=0;
	int flag=0;
	int ret=0;
	hole *next=head,*prev=NULL;
	hole *New=NULL;
	while(next!=NULL)
	{
		if(next->start==addr)
			return ERROR;
		if(next->start>addr)
			break;
	    prev=next;
		next=next->next;
	}
	/*处理参数不合理的情况*/
	if(prev&&addr<(prev->start+prev->size))
		addr=prev->start+prev->size;
	if(next&&(addr+size)>next->start)
		size=next->start-addr;
	if(prev&&(prev->start+prev->size)==addr)						/*与前面一个hole合并*/
	{
		prev->size+=size;
		flag=1;
		ret=1;
	}
	if(next&&(addr+size==next->start))								/*与后面一个hole合并*/
	{
		if(flag)		/*与前后合并*/
		{
			prev->size+=next->size;
			prev->next=next->next;
			printk("free %x",mfree(next));
		}else			//只与后面一个hole合并
		{
			next->start-=size;
			next->size+=size;
		}
		ret=1;

	}
	if(ret)
		return addr;
	/*不能合并*/
	New=(hole *)mmalloc();
	printk("new %x\n",New);
	New->start=addr;
	New->size=size;
	if(!prev)
		head=New;
	else
		prev->next=New;
	New->next=next;
	return addr;
}

/*
Interface,Reclaim the memory 
*/
PUBLIC t32 memFree(t32 address,t32 size)
{	
	if(address>memStart+memSize)
		return ERROR;
	return unitHole(address,size);
}

PUBLIC void dumpHole()
{
	hole *next=head;
	while(next)
	{
		printk("start       size       next       \n");
		printk("%x           %x         %x        \n",next->start,next->size,next->next);
		next=next->next;
	}
}