两个测试用例看懂伙伴系统核心算法

Buddy_Zhang1

Buddy System (伙伴系统算法) 是 linux 用来管理物理内存的算法,其简单高效的特点一直沿用到现在.
本帖分享使用两个测试用例来了解伙伴系统在 Linux 的核心实现过程.

Buddy_Zhang1

从伙伴系统中获得一个物理页:

struct TestCase_get_free_page(void)
{
     struct pglist_data *pgdat;
     struct zonelist *zonelist;
     struct zone *zone;
     struct free_area *area;
     struct page *page;
     int migratetype;
     int order,current_order;

     pgdat = NODE_DATA(0);
     zonelist = pgdat->node_zonelists;
     first_zones_zonelist(zonelist,0,NULL,&zone);
     migratetype = MIGRATE_MOVABLE;
     int order = 0;

     for(current_order = 0 ; current_order < MAX_ORDER ; current_order++) {
           unsigned long size;

           area = &zone->free_area[current_order];
           if(list_empty(&area->free_list[migratetype]))
                      continue;
   
           page = list_entry(area->free_list[migratetype].next,
                                struct page,lru);
           list_del(&page->lru);
           rmv_page_order(page);
           area->nr_free--;
         
           size = 1 << current_order;
           while(order < current_order) {
                ara--;
                current_order--;
                size >>= 1;
                list_add(&page[size],lru,
                              &area->free_list[migratetype]);
                set_page_order(&page[size],current_order);
                area->nr_free++;
          }
          if(!PageBuddy(page))
                 goto out;
     }
     printk(KERN_INFO "Can't get free page\n");
     return;

out:
      printk(KERN_INFO "Get free page\n");
}

Buddy_Zhang1

释放一个 page 回伙伴系统

void TestCase_free_page(void)
{
      struct page *page = /* 已知*/;
      struct zone *zone;
      struct page *buddy;
      unsigned long page_idx,buddy_idx;
      unsigned long combine_idx;
      int order = 0;

     zone = page_zone(page);
     migratetype = get_pageblock_migratetype(page);
     page_idx = page_to_pfn(page);

     while(order < MAX_ORDER  -1) {
           buddy_idx = __find_buddy_index(page_idx,order);
           buddy = page + (buddy_idx - page_idx);
           if(!page_is_buddy(page,buddy,order))
                    break;

           list_del(&buddy.lru);
           rmv_page_order(buddy);
           zone->free_area[order].nr_free--;
           combine_idx = buddy_idx & page_idx;
           page = page + (combine_idx - page_idx);
           page_idx = combine_idx;
           order++;
    }
    set_page_order(page,order);

    if((order < MAX_ORDER - 2) && (pfn_valid_within(page_to_pfn(page)))) {
          struct page *higher_page,*higher_buddy;

          combine_idx = buddy_idx & page_idx;
          higher_page = page + (combine_idx - page_idx);
          buddy_idx = __find_buddy_index(combine_idx,order + 1);
          higher_buddy = higher_page + (buddy_idx - combine_idx);
          if(page_is_buddy(higher_page,higher_buddy,order + 1)) {
                   list_add_tail(&page->lru,
                      &zone->free_area[order].free_list[migratetype]);
                   goto out;
          }
    }
    list_add(&page->lru,
                   &zone->free_area[order].free_list[migratetype]);
out:
    zone->free_area[order].nr_free++;
}