mem.c

基于三星４４Ｂ０芯片的移植操作系统

#include <string.h>
#include "mem.h"

#define HEADLINE_MAX 8 // 32/64/128/256/512/1024/2048/MEM_SIZE
#define MEM_ALIGNMENT 4
#define MEM_SIZE 20000

struct mem h[HEADLINE_MAX];
int lens[HEADLINE_MAX] = {32,64,128,256,512,1024,2048,MEM_SIZE};

static struct mem *ram_begin, *ram_end;

static char ram[MEM_SIZE + sizeof(struct mem)];

#if 0 /* this one does not align correctly for some, resulting in crashes */
#define SIZEOF_STRUCT_MEM (unsigned int)MEM_ALIGN_SIZE(sizeof(struct mem))
#else
#define SIZEOF_STRUCT_MEM (sizeof(struct mem) + \
                          (((sizeof(struct mem) % MEM_ALIGNMENT) == 0)? 0 : \
                          (4 - (sizeof(struct mem) % MEM_ALIGNMENT))))
#endif

static void plug_holes(struct mem *mem)
{
  struct mem *nmem;
  struct mem *pmem;
  
  /* plug hole forward */
  nmem = (struct mem *)&ram[mem->next];
  if (mem != nmem && nmem->used == 0 && (char *)nmem != (char *)ram_end) {
     /*if (lfree == nmem) {
      lfree = mem;
    }*/
    mem->next = nmem->next;
    ((struct mem *)&ram[nmem->next])->prev = (char *)mem - ram;
    delete_listnode(nmem);
  }

  /* plug hole backward */
  pmem = (struct mem *)&ram[mem->prev];
  if (pmem != mem && pmem->used == 0) {
    /*if (lfree == mem) {
      lfree = pmem;
    }*/
    pmem->next = mem->next;
    ((struct mem *)&ram[mem->next])->prev = (char *)pmem - ram;
    delete_listnode(pmem);
  }

  insert_listnode(mem);
}

static int find_header(int size )
{
	int i,j,cursor;
	i=0;
	j=HEADLINE_MAX-1;
	while(i!=j-1)
	{
		cursor = (i+j)/2;
		if(size<=h[cursor].length)
		{
			if(size==h[cursor].length)
			{
				return cursor;
			}
			j=cursor;
		}
		else
		{
			i=cursor;
		}
	}
	return j;
}

static struct mem * find_listnode(int size )//最佳适应算法
{
	int header;
	int best_size,new_size;
	struct mem *best_node;
	struct mem *pheader,*pcursor;
	header = find_header(size);
	pheader = &h[header];
	pcursor = pheader->pnext;
	best_node = (struct mem *)0;
	best_size = 0;
	while(pcursor != (struct mem *)0)
	{
		new_size = pcursor->next - ((char *)pcursor - ram) - 2*SIZEOF_STRUCT_MEM;
		if(new_size >= size)//used一定为0
		{
			if(best_size==0)
			{
				best_size = new_size;
				best_node = pcursor;
			}
			else
			{
				if(best_size > new_size)
				{
					best_size = new_size;
					best_node = pcursor;
				}
			}
		}
	}
	return best_node;
}

static void delete_listnode(struct mem *mem)
{
	if(mem->pnext==(struct mem *)0)//尾节点
	{
		mem->pprev->pnext=(struct mem *)0;
	}
	else
	{
		//if(mem->pprev->next==0)//头节点
		//{
		mem->pprev->pnext=mem->pnext;
		mem->pnext->pprev=mem->pprev;
		/*}
		else
		{
		}*/
	}
}

static void insert_listnode(struct mem *mem)
{
	int header;
	struct mem *pheader;
	header = find_header(mem->next-((char *)mem-ram)-SIZEOF_STRUCT_MEM);
	pheader = &h[header];
	if(pheader->pnext != (struct mem*)0)
	{
		pheader->pnext->pprev=mem;
	}
	mem->pnext=pheader->pnext;
	pheader->pnext=mem;
	mem->pprev=pheader;
}

void mem_init(void)
{
  int i;

  memset(ram, 0, MEM_SIZE);
  
  ram_begin = (struct mem *)ram;
  ram_begin->next = MEM_SIZE;
  ram_begin->prev = 0;
  ram_begin->used = 0;
  ram_end = (struct mem *)&ram[MEM_SIZE];
  ram_end->used = 1;
  ram_end->next = MEM_SIZE;
  ram_end->prev = MEM_SIZE;

  //初始化查找链表
  for(i=0;i< HEADLINE_MAX;i++)
  {
	h[i].pnext=h[i].pprev=(struct mem*)0;
	h[i].length=lens[i];
  }

  insert_listnode(ram_begin);
}

void mem_free(void *rmem)
{
  struct mem *mem;

  if (rmem == (struct mem *)0) {
    return;
  }
  
  //sys_sem_wait(mem_sem);
  
  if ((char *)rmem < (char *)ram || (char *)rmem >= (char *)ram_end) {
    //sys_sem_signal(mem_sem);
    return;
  }
  mem = (struct mem *)((char *)rmem - SIZEOF_STRUCT_MEM);
  
  mem->used = 0;

  /*if (mem < lfree) {
    lfree = mem;
  }*/
  
  plug_holes(mem);//聚合，查找链表的修改放在聚合函数中
  //sys_sem_signal(mem_sem);
}
void * mem_reallocm(void *rmem, int newsize)
{
  void *nmem;
  nmem = mem_malloc(newsize);
  if (nmem == (struct mem *)0) {
    return mem_realloc(rmem, newsize);
  }
  memcpy(nmem, rmem, newsize);
  mem_free(rmem);
  return nmem;
}

void * mem_realloc(void *rmem, int newsize)
{
  int size;
  int ptr, ptr2;
  struct mem *mem, *mem2;

  /* Expand the size of the allocated memory region so that we can
     adjust for alignment. */
  if ((newsize % MEM_ALIGNMENT) != 0) {
   newsize += MEM_ALIGNMENT - ((newsize + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
  }
  
  if (newsize > MEM_SIZE) {
    return (struct mem *)0;
  }
  
  //sys_sem_wait(mem_sem);
    
  if ((char *)rmem < (char *)ram || (char *)rmem >= (char *)ram_end) {
    return rmem;
  }
  mem = (struct mem *)((char *)rmem - SIZEOF_STRUCT_MEM);

  ptr = (char *)mem - ram;

  size = mem->next - ptr - SIZEOF_STRUCT_MEM;
  
  if (newsize + SIZEOF_STRUCT_MEM < size) {//+ MIN_SIZE
    ptr2 = ptr + SIZEOF_STRUCT_MEM + newsize;
    mem2 = (struct mem *)&ram[ptr2];
    mem2->used = 0;
    mem2->next = mem->next;
    mem2->prev = ptr;
    mem->next = ptr2;
    if (mem2->next != MEM_SIZE) {
      ((struct mem *)&ram[mem2->next])->prev = ptr2;
    }

    plug_holes(mem2);
  }
  //sys_sem_signal(mem_sem);  
  return rmem;
}

void * mem_malloc(int size)
{
  int ptr, ptr2;
  struct mem *mem, *mem2;

  if (size == 0) {
    return (struct mem *)0;
  }

  /* Expand the size of the allocated memory region so that we can
     adjust for alignment. */
  if ((size % MEM_ALIGNMENT) != 0) {
    size += MEM_ALIGNMENT - ((size + SIZEOF_STRUCT_MEM) % MEM_ALIGNMENT);
  }
  
  if (size > MEM_SIZE) {
    return (struct mem *)0;
  }
  
  //sys_sem_wait(mem_sem);

  //不再需要线性查找地址顺序排序的链表
  mem = find_listnode(size);//使用最佳适应算法
  if(!mem)
  {
  	return (struct mem *)0;
  }
  ptr = (char *)mem - ram;
  ptr2 = ptr + SIZEOF_STRUCT_MEM + size;
  mem2 = (struct mem *)&ram[ptr2];

  mem2->prev = ptr;      
  mem2->next = mem->next;
  mem->next = ptr2;      
  if (mem2->next != MEM_SIZE) {
    ((struct mem *)&ram[mem2->next])->prev = ptr2;
  }
      
  mem2->used = 0;      
  mem->used = 1;

  //从查找链表中移除mem，再插入mem2
  delete_listnode(mem);
  insert_listnode(mem2);
      
  return (char *)mem + SIZEOF_STRUCT_MEM;
  //sys_sem_signal(mem_sem);  
}