第21章 内存管理的设计与实现

内存管理的目标是提供:

内核函数:void *sys_malloc(unsigned long size); void *sys_free(void *);

系统调用函数 void * malloc(unsigned long size); void * free(void *);

内存管理:

  1. 发现资源
  2. 监控资源–元数据记录资源的属性和标识
  3. 分配资源–修改元数据,返回资源的标识
  4. 回收资源–修改元数据

内存的元数据

  1. 怎么设计元数据

    • 多种格式

      • 数组 — 方便查找和分配(数组元素是链表,该链表中的内存大小都是一样的)
      • 链表 — 方便分配和回收
      • hash表
    • 多角度

      • 内存起始地址
      • 内存大小
    • 多维度

2、如何存取元数据

* 不同格式的元数据造成元数据的大小、元数据的访问方式、元数据的操作都不一样
* 元数据存放的位置
* 访问(共享、竞争)

设计思路:

内存结构如下所示(mem.h源代码)

#ifndef        _MEM_H_
#define     _MEM_H_

typedef struct mem{
    struct mem *next, *prev, *hnext, *hprev;    //在未分配内存链表上是双向链表,在HASH表上是双向链表
    unsigned long size;
    unsigned long flag; //flag=0表示未分配,flag=1表示已分配
}mem_t;

#define     MEM_FREE    0x0
#define     MEM_USED    0x1




void init_mem(void);

void *sys_malloc(unsigned long size);

void *sys_free(void *addr);

#endif

内存元数据和它所描述的内存放在一起。假设OS刚启动时有63M(1M~64M)的空闲内存,要初始化内存管理。

free_mem_head = (mem_t *)1024*1024;
free_mem_head->hnext = free_mem_head->next = free_mem_head->hprev = free_mem_head->prev = NULL;
free_mem_head->size = 63*1024*1024 - sizeof(mem_t);
free_mem_head->flag = MEM_FREE;

内存分配算法是:

  1. 查找合适大小的内存,并分配

内存回收算法是:

  1. 回收内存,合并相邻内存

具体算法可以查看

http://www.nondot.org/sabre/os/files/MemManagement/LEA.html

mem.c文件的源代码如下所示

#include "define.h"
#include "mem.h"
#include "kernel.h"
#include "video.h"
#include "mutex.h"

//地址方位描述符结构 Address Range Descriptor Structure
struct ARDS{
    unsigned long base_addr_low;
    unsigned long base_addr_high;
    unsigned long length_low;
    unsigned long length_high;
    unsigned long type;
}__attribute__((packed));

#define ADDRESS_RANGE_MEMORY    1
#define ADDRESS_RANGE_RESERVED    2

//可用内存起始地址和大小
static unsigned long mem_start = 0;
static unsigned long mem_size = 0;

//未分配内存链表,已分配内存链表
static mem_t * free_mem_head = NULL;
static mem_t * used_mem_head = NULL;

//未分配内存HASH表
#define MEM_HASH_NR    32
static mem_t * mem_hash[MEM_HASH_NR];



//初始化未分配内存链表
mem_t * init_free_mem_head(unsigned long mem_start, unsigned long mem_size)
{
    free_mem_head = (mem_t *)mem_start;
    free_mem_head->hnext = free_mem_head->next = free_mem_head->prev = NULL;
    free_mem_head->size = mem_size - sizeof(mem_t);
    free_mem_head->flag = MEM_FREE;
    return free_mem_head;
}

//给未分配内存链表添加内存节点
mem_t *add_free_mem_head(mem_t * p)
{
    if(!p)
    return NULL;


    //插入链表中
    if(!free_mem_head) //链表为空
    {
    free_mem_head = p;
    p->next = NULL;
    p->prev = NULL;
    }
    else if(p < free_mem_head) //插在链表头
    {
    p->next = free_mem_head;
    p->prev = NULL;
    free_mem_head->prev = p;
    free_mem_head = p;
    }
    else //插在链表中
    {
    mem_t * pt = free_mem_head;
    while(pt->next && p > pt->next)
    {
        pt = pt->next;
    }

    p->next = pt->next;
    if(p->next)
        p->next->prev = p;
    pt->next = p;
    p->prev = pt;
    }

    p->flag = MEM_FREE;    
    return p;
}

//从未分配内存链表中摘下内存节点
mem_t * get_free_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    if(free_mem_head == p)    //摘取链表头
    {
    if(p->next == NULL)        //链表只有一个节点
    { 
        free_mem_head = NULL;
    }
    else                //链表有多个节点
    {
        free_mem_head = p->next;
        free_mem_head->prev = NULL;
    }
    }
    else if(p->next == NULL)    //摘取链表尾
    {
    p->prev->next = NULL;
    }
    else            //摘取链表中的节点
    {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    }

    return p;
}

//把p内存空间分割成 size 和 (p->size - size - sizeof(mem_t))大小的两个内存空间,然后摘除内存节点p
//返回(p->size - size - sizeof(mem_t))大小内存空间节点的指针
mem_t * split_get_free_mem_head(mem_t *p, unsigned long size)
{
    if(!p || !size)
    return NULL;
    if(p->size <= (size + sizeof(mem_t)))
    return NULL;
    
    //分割
    mem_t * newp = (mem_t *)((void *)p + sizeof(mem_t) + size);
    newp->size = p->size - size -sizeof(mem_t);
    newp->flag = MEM_FREE;
    p->size = size;
    newp->next = p->next;
    if(p->next)
    p->next->prev = newp;
    newp->prev = p;
    p->next = newp;

    //从未分配内存链表上摘除p节点
    get_free_mem_head(p);

    //返回新分割出来的内存节点
    return newp;
}

//初始化已分配内存链表
void init_used_mem_head()
{
    used_mem_head = NULL;
}

//添加已分配内存节点到已分配内存链表中 TODO:以后再实现
mem_t *add_used_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    p->flag = MEM_USED;
    return p;
}



//从已分配内存链表中摘除已分配内存节点 TODO:以后再实现
mem_t *get_used_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    return p;
}

//初始化未分配内存HASH表
void init_mem_hash()
{
    int i = 0;
    for(i = 0; i < MEM_HASH_NR; i++)
    {
    mem_hash[i] = NULL;
    }    
}

//把未分配的内存插入HASH表中
mem_t * add_mem_to_hash(mem_t * mem)
{
    if(!mem)
    return NULL;
    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = mem->size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
        :"=r"(index)
        :"rm"(index)
        );
    if(mem_hash[index])
    {    //插到链表头
    mem->hnext = mem_hash[index];
    mem->hprev = NULL;
    mem_hash[index]->hprev = mem;
    mem_hash[index] = mem;
    }
    else
    {
    mem_hash[index] = mem;
    mem->hnext = NULL;
    mem->hprev = NULL;
    }

    return mem;
}

//从HASH表中获得未分配内存,只要未分配的内存大小大于size
//成功则从HASH表上摘除该内存!!!!!!!
//成功返回mem_t 指针,失败返回NULL
mem_t * get_mem_from_hash(unsigned long size)
{
    if(!size)
    return NULL;

    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
        :"=r"(index)
        :"rm"(index)
        );
    int i = 0;
    mem_t * p = NULL;
    for(i = index; i < MEM_HASH_NR; i++)
    {
    if(mem_hash[i])
    {
        //从链表头取
        p = mem_hash[i];
        mem_hash[i] = mem_hash[i]->hnext;
        if(mem_hash[i])
        mem_hash[i]->hprev = NULL;
        break; 
    }
    }

    return p;
}


mem_t * remove_mem_from_hash(mem_t *p)
{
    if(!p || p->flag != MEM_FREE)
    return NULL;

    //p在HASH表中的链表的位置有三种情况:链表头;链表尾;链表中间
    if(p->hprev == NULL)
    {
    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = p->size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
            :"=r"(index)
        :"rm"(index)
        );
    if(mem_hash[index] != p)
        return NULL;

    mem_hash[index] = mem_hash[index]->hnext;
    if(mem_hash[index])
        mem_hash[index]->hprev = NULL;
    }
    else if(p->hnext == NULL)
    {
    p->hprev->hnext = NULL;
    }
    else
    {
    p->hprev->hnext = p->hnext;
    p->hnext->hprev = p->hprev;
    }


    return p;
}

//合并未分配内存
//成功则返回 合并后的mem_t内存节点指针
//该函数操作未分配内存链表和内存HASH表
mem_t *join_free_mem(mem_t *p)
{
    if(!p)
    return NULL;

    //尝试合并相邻节点,合并条件是
    // p->prev + sizeof(mem_t) + p->prev->size == p
    // p + sizeof(mem_t) + p->size == p->next
    mem_t * tmp = NULL;
    if(p->prev && (p->prev + sizeof(mem_t) + p->prev->size) == p) //合并左边节点
    {
    tmp = p->prev;
    remove_mem_from_hash(p); //从hash表上摘除
    remove_mem_from_hash(tmp); //从hash表上摘除

    tmp->next = p->next;
    if(p->next)
        p->next->prev = tmp;
    tmp->size = tmp->size + sizeof(mem_t) + p->size;
    p = tmp;
    add_mem_to_hash(p);      //把新合并的内存节点添加到HASH表上
    }

    if(p->next && (p + sizeof(mem_t) + p->size) == p->next)    //合并右边节点
    {
    tmp = p->next;
    remove_mem_from_hash(p); //从hash表上摘除
    remove_mem_from_hash(tmp); //从hash表上摘除

    p->next = tmp->next;
    if(tmp->next)
        tmp->next->prev = p;
    p->size = p->size + sizeof(mem_t) + tmp->size;
    add_mem_to_hash(p);      //把新合并的内存节点添加到HASH表上
    }

   return p;

}
void init_mem()
{
    int i = 0;
    //查找内存大小
    unsigned long *nr = (unsigned long *)E820NR;
    struct ARDS *ptr = (struct ARDS *)E820MAP;
    //打印物理内存信息,并初始化内存起始地址和内存大小
    sys_kprint(char_attr(BLACK,WHITE),"BaseAddr\tLength\tType\n");    
    for(i = 0; i < *nr; i++)
    {
    
    print16base(char_attr(BLACK,WHITE),ptr[i].base_addr_low);
    sys_kprint(char_attr(BLACK,WHITE),"\t");
    print16base(char_attr(BLACK,WHITE),ptr[i].length_low);
    sys_kprint(char_attr(BLACK,WHITE),"\t");
    print16base(char_attr(BLACK,WHITE),ptr[i].type);
    sys_kprint(char_attr(BLACK,WHITE),"\n");
    
    if(ptr[i].type == ADDRESS_RANGE_MEMORY && ptr[i].length_low > mem_size)
    {
        mem_start = ptr[i].base_addr_low;    //得到可用内存的起始地址
        mem_size = ptr[i].length_low;    //得到可用内存的大小
    }
    }

    sys_kprint(char_attr(BLACK,WHITE),"\nMemory Start = ");
    print16base(char_attr(BLACK,WHITE),mem_start);
    sys_kprint(char_attr(BLACK,WHITE),"\nMemory Size = ");
    print16base(char_attr(BLACK,WHITE),mem_size);
    sys_kprint(char_attr(BLACK,WHITE),"\n\n");


    //初始化未分配内存链表和已分配内存链表
    mem_t *first_mem = NULL;
    first_mem = init_free_mem_head(mem_start, mem_size);
    init_used_mem_head();

    //初始化未分配内存HASH表
    init_mem_hash();
    
    //把第一块未分配的内存添加进HASH表中
    add_mem_to_hash(first_mem); 
}

//获取指定大小内存空间的地址,成功返回内存地址,失败返回NULL
void *kmalloc(unsigned long size)
{
    if(!size)
    return NULL;

    //把size变成4的倍数,防止碎片化
    size = ((size - 1)/4  + 1)*4;

    //从hash表中查找大于等于size的未分配空间
    mem_t *p = get_mem_from_hash(size);
    if(!p)
    return NULL;

    //在未分配内存链表中摘除该空间,有三种情况:
    //第一种情况:(p->size) == size                大小刚合适
    //第二种情况:size < (p->size)  < size + sizeof(mem_t) + 4    全分配,不至于分割出小于4的内存空间
    //第三种情况:size + sizeof(mem_t) + 4 <= (p->size)        分割内存

    if(p->size < size + sizeof(mem_t) + 4)   
    {
    p = get_free_mem_head(p);  //全分配
    }
    else
    {
    mem_t *newp = split_get_free_mem_head(p, size);  //分割内存
    add_mem_to_hash(newp);                 //把新分割出的内存添加到HASH表中
    }

    //添加到已分配内存链表中
    add_used_mem_head(p);

    //从内存节点转换成可用的内存指针
    return ((void *)p + sizeof(mem_t));    
}

//释放内存,成功则返回内存地址,失败则返回NULL
void *kfree(void *addr)
{
    if(!addr)
    return NULL;

    //从内存指针转换成可用的内存节点
    mem_t *p = (mem_t *)(addr - sizeof(mem_t));
    
    //从已分配内存链表中摘除
    p = get_used_mem_head(p);

    //添加到未分配内存链表中
    p = add_free_mem_head(p);

    //添加到内存HASH表中
    add_mem_to_hash(p);

    //尝试合并内存,减少内存碎片
    join_free_mem(p);

    return addr;
}

mutex_t mem_mutex = 0;

void * sys_malloc(unsigned long size)
{
    void *p = NULL;
    lock(&mem_mutex);
    p = kmalloc(size);
    unlock(&mem_mutex);

    return p;
}

void * sys_free(void *addr)
{
    void *p = NULL;
    lock(&mem_mutex);
    p = kfree(addr);
    unlock(&mem_mutex);

    return p;
}

Leave a Reply

Your email address will not be published. Required fields are marked *