欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

自己动手写操作系统(三)

程序员文章站 2024-03-24 11:46:34
...

    这篇文章先乱入一下,这几天一直在写内存分配器(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在调试。等测试验证没有问题后,再开启。


谢谢。    

相关标签: 操作系统