自己动手写操作系统（三）

    这篇文章先乱入一下，这几天一直在写内存分配器（coalition，姑且这么叫吧）。参考的主要还kernel的伙伴内存分配方式。

    这里先 一下为什么要用参考伙伴分配方式重新写内存分配器吧。

    原先的内存分配设计是采用一个bitmap来记录所有的free page，每次分配都从bitmap里面找4k的页。例如我申请一个16K的内存，我直接找2个4K的页，然后更新PGD表和TLB表，这样的确内存碎片会比较少（基本就没有碎片），但是每次更新TLB表会导致MMU会变慢。而且如果需要的是连续内存，那需要先找到连续的虚拟内存，然后再找连续的物理内存，最后一一映射，速度会变得非常慢。所以这里还是参照kernel的做法，先分了Normal／High两个zone，其中normal zone采用的是平坦映射，即物理地址和虚拟地址一一对应。这块zone上的内存分配就采用了coalition。

    目前代码比较简单，主要函数如下：        

void coalition_allocator_init()
{
    int index = 0;

    //pre-init
    for(;index < ZONE_FREE_MAX_ORDER;index++)
    {
       INIT_LIST_HEAD(&normal_zone.nr_area[index].free_page_list);
       INIT_LIST_HEAD(&normal_zone.nr_area[index].used_page_list);
       //normal_zone.nr_area[index].nr_free_pages = 0;
    }
    
    align_result ret;
    GET_ALIGN_PAGE(_coalition_all_alloc_pages->size,&ret);

    list_add(&_coalition_all_alloc_pages->ll,&normal_zone.nr_area[ret.order].free_page_list);
}

    初始化4K，16K，32K。。。的队列，由于当前内存还没有被分配过，所以将这块总的内存放入到队列中。

    接下来就是内存分配函数，参考buddy的思路，没有找到合适的内存，就需要从更大块分裂出一块。

void* _coalition_malloc(int size) 
{   
    align_result align_ret;
    GET_ALIGN_PAGE((size + sizeof(mm_page)),&align_ret);
    int alignsize = align_ret.page_size;
    int order = align_ret.order;
    
    list_head *p;
    //we should first find whether there is unused memory
    list_for_each(p,&normal_zone.nr_area[order].free_page_list) { //优先查找free list，看一下是否有可用的内存
        mm_page *page = list_entry(p,mm_page,ll);
        //we get free page
        list_del(p);
        _coalition_list_add(p,&normal_zone.nr_area[order].used_page_list);
        return page->start_pa + sizeof(mm_page);
    }
    //如果没有找到可用的page，那就需要向更大内存的队列查找
    //else we should divide a memory from Larger order memory
    order++;
    while(order < ZONE_FREE_MAX_ORDER)
    {
       int current_order = order;

       //if(normal_zone.nr_area[order].nr_free_pages >  0)
       if(!list_empty(&normal_zone.nr_area[order].free_page_list))
       {
           //hit we find a free page,split the page 
           list_for_each(p,&normal_zone.nr_area[order].free_page_list) {
               mm_page *page = list_entry(p,mm_page,ll);
               if(page->size < alignsize) 
               {
                   continue;
               } 

               list_del(p);
               if(page->size > alignsize) 
               {
                   current_order--;
                   //divide to 2 part,one is used ,another is free.
                   //uint32_t start_pa = get_workable_pa(page);
                   //找到大块可用内存后需要做一次分裂，其中一部分作为free page，放入到free list中
                   mm_page *another = page->start_pa + alignsize;
                   another->start_pa = another;
                   another->size = page->size - alignsize;
                   align_result another_align_ret;
                   GET_ALIGN_PAGE(another->size,&another_align_ret); //todo
                   int move_order = another_align_ret.order;
                   _coalition_list_add(&another->ll,&normal_zone.nr_area[move_order].free_page_list);
                   _coalition_free_list_adjust(&another->ll,&normal_zone.nr_area[move_order].free_page_list);

                   page->size = alignsize;
                   current_order = align_ret.order;//GET_FREE_ORDER(alignsize);
                   //list_add(p,&normal_zone.nr_area[order - 1].used_page_list);
               }
               //另外的一部分就作为used page放入队列中。
               //list_add(p,&normal_zone.nr_area[current_order].used_page_list);
               _coalition_list_add(p,&normal_zone.nr_area[current_order].used_page_list);

               return page->start_pa + sizeof(mm_page);
           }      
       } 
       order++;
    }

    return NULL;
}

    内存释放的思路如下：我这里used_page_list/free_page_list是按照地址从小到达排列。所以每次free的时候，只需要确认free page的左右是否有可以合并的即可。合并代码如下：

void _coalition_free_list_adjust(list_head *pos,list_head *head) 
{

    align_result align_ret;
    mm_page *page = list_entry(pos,mm_page,ll);
    
    //check prev,we should check whether prev_page is the header?
    mm_page *prev_page = list_entry(pos->prev,mm_page,ll);
    
    if(&prev_page->ll != head) //dnot head
    {
        if((page->start_pa - prev_page->start_pa) == page->size) //如果发现前面的page和当前page的地址相差就是page的大小
        {
            list_del(&page->ll); //删除page
            list_del(&prev_page->ll);
            prev_page->size += page->size;//合并page，起始就是将前面的page大小放大即可
            GET_ALIGN_PAGE(prev_page->size,&align_ret);
            _coalition_list_add(&prev_page->ll,&normal_zone.nr_area[align_ret.order].free_page_list);//合并好的page插入列表
            _coalition_free_list_adjust(&prev_page->ll,&normal_zone.nr_area[align_ret.order].free_page_list);//递归调整
            return;
        }    
    }

    //check next
    
    mm_page *next_page = list_entry(pos->next,mm_page,ll);
    //printf("adjust next_page is %x size is %x \n",next_page,next_page->size);
    if(&next_page->ll != head) {
        if(next_page->start_pa - page->start_pa == page->size) 
        {
            list_del(&page->ll);
            list_del(&next_page->ll);
            page->size += page->size;
            GET_ALIGN_PAGE(page->size,&align_ret);
            _coalition_list_add(&page->ll,&normal_zone.nr_area[align_ret.order].free_page_list);
            _coalition_free_list_adjust(&page->ll,&normal_zone.nr_area[align_ret.order].free_page_list);
            return;
        }
    }
}

最后奉上代码的url

https://github.com/wangsun1983/arale/blob/master/core/mm/coalition_alloctor.c

PS：

目前这个内存分配器还没有在arale系统上用，只是本地linux在调试。等测试验证没有问题后，再开启。

谢谢。