论坛 › 内核源码 › 两个测试用例看懂伙伴系统核心算法

Buddy_Zhang1 发表于 2016-03-08 10:18

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

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

Buddy_Zhang1 发表于 2016-03-08 10:27

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

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;
         if(list_empty(&area->free_list))
                      continue;
   
         page = list_entry(area->free_list.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,lru,
                              &area->free_list);
                set_page_order(&page,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 发表于 2016-03-08 10:38

释放一个 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.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.free_list);
                   goto out;
          }
    }
    list_add(&page->lru,
                   &zone->free_area.free_list);
out:
    zone->free_area.nr_free++;
}

查看完整版本: 两个测试用例看懂伙伴系统核心算法