OSDev.org

Code: Select all

#define MALLOC_MAGIC	0x6D92  /* must be < 0x8000 */

typedef struct _malloc
{
 size_t size;			//4 bytes
 struct _malloc *next;		//4 bytes
 unsigned magic : 15 ;		//4 bytes
 unsigned used : 1 ;		
} malloc_t;

static malloc_t *_kheap_bot, *_kheap_top;

/**********************************************/
void *kbrk(int incr)
{
 static unsigned char *brk;
 void *ret;
 physaddr_t paddr;
 virtaddr_t vaddr;
 extern char end;
 if(brk==NULL)
  {
   brk=(unsigned char)&end;		//kernel end
   printf("Initializing the Heap...\n");
  }
 ret=brk;
 if(incr>0)
   incr+=(page_size-1);

 incr &=-page_size;

 if(incr<0)
    return brk;
  
 for(vaddr=(virtaddr_t)brk;vaddr<(virtaddr_t)brk+incr;vaddr+=page_size)
  {
   paddr=allocframe(0);//alloc physical page 4K
  
   //error no enough memory
   if(!paddr)
     return nomem;
  
   map(vaddr,paddr,write);   //map the page to a virtual address    
 
  }
 brk=brk+incr;
 return ret;

}

void *kmalloc(size_t size)
{
 size_t total_size;
 malloc_t *blk;
 if(size==0)
    return NULL;
 total_size=size+sizeof(malloc_t);
 
 /* heap does not exist yet*/
 
 if(_kheap_bot==NULL)
  {
    blk=kbrk(total_size);
    if(blk==-1)
       return NULL;
 
     _kheap_bot=_kheap_top=blk;
     blk->size=size;
     blk->next=NULL;
     blk->magic=MALLOC_MAGIC;
     blk->used=1;
     return (char *)blk + sizeof(malloc_t);
  }
 /* heap is already exist so...
    search the heap for free block
    first fit algorithem */
  
 for(blk=_kheap_bot;blk!=NULL;blk=blk->next)
  {
    if(!blk->used && total_size<=blk->size)
      break;
  }
 
 /* found a block */
 if(blk!=NULL)
  {
    malloc_t *new_blk;
    new_blk=(malloc_t *)((char *)blk+total_size);

 /* point to new empty block and down size it */
   
    new_blk->used=0;
    new_blk->size=blk->size-total_size;
    new_blk->next=blk->next;
    new_blk->magic=MALLOC_MAGIC;
 
 /* set _kheap_top if necessary */
   
    if(new_blk->next=NULL)
         _kheap_top=new_blk;
 /* point to new used block and set it */
    
    blk->used=1;
    blk->size=size;
    blk->next=new_blk;
    blk->magic=MALLOC_MAGIC;
    return (char *)blk+sizeof(malloc_t); 
   
  }

 /* not found any block so enlarge the heap */
  blk=kbrk(total_size);
  if((int)blk==-1)
     return NULL ;//no more memory
  blk->used=1;
  blk->size=size;
  blk->next=NULL;
  blk->magic=MALLOC_MAGIC;
 
/* this block is the new end of the heap */
  
 _kheap_top->next=blk;
 _kheap_top=blk;
 return (char *)blk+sizeof(malloc_t);

}

void kfree(void *blk)
{
  malloc_t *t_blk;
  
 /*get the actual address of the block*/
 
 blk=(char *)blk-sizeof(malloc_t);
 t_blk=(malloc_t *)blk;
 /* bad magic value */
 if(t_blk->magic!=MALLOC_MAGIC)
     return;
 
 /* search for the block */
  
  for(t_blk=_kheap_bot;t_blk!=NULL;t_blk=t_blk->next)
   {
      if(t_blk==blk)
         break;
   }
 
 /* not found the block */
  
  if(t_blk==NULL)
    return;

 /* found the block so free it */
  
  t_blk->used=0;
  
  for(t_blk= _kheap_bot;t_blk!=NULL;t_blk=t_blk->next)
   {
  
     while(!t_blk->used && (t_blk->next!=NULL) && !t_blk->next->used)
      {
        t_blk->size+=sizeof(malloc_t)+ t_blk->next->size;
        t_blk->next=t_blk->next->next;
      }  
  
   }//End for
  

}