伙伴系统

 glo597wb.zip   

Linux的内存管理由最初启动时的bootmem进行管理，到后来才转化为Buddy system（伙伴系统）的。
下面是伙伴系统最为常用的两个操作。
1）分配块
2）释放块
 580 static struct page *__rmqueue(struct zone *zone, unsigned int order)
 581 {
 582         struct free_area * area;
 583         unsigned int current_order;
 584         struct page *page;
 585
 586         for (current_order = order; current_order < MAX_ORDER; ++current_order) {
 587                 area = zone->free_area + current_order;
 588                 if (list_empty(&area->free_list))
 589                         continue;
 590
 591                 page = list_entry(area->free_list.next, struct page, lru);
 592                 list_del(&page->lru);
 593                 rmv_page_order(page);
 594                 area->nr_free--;
 595                 zone->free_pages -= 1UL << order;
 596                 expand(zone, page, order, current_order, area);
 597                 return page;
 598         }
 599
 600         return NULL;
 601 }
这段代码还是很简单的，首先函数接受二个参数：
1）zone：指向要分配的块所在的管理区。确切的说是指向管理区描述符地址的指针；
2）order：要分配的块的阶数。e.g：order=2 就是分配连续内存数为4页的内存。order=3 8页。
内核定义了一系列的宏：
 #ifndef CONFIG_FORCE_MAX_ZONEORDER
  #define MAX_ORDER 11
  #else
  #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  #endif
这段宏给我们提供了一个可以自己配置MAX_ORDER大小的选项，如果没有定义，MAX_ORDER=11
也就是说order的最大取值为11，更进一步的讲：内核可以分配的最大的连续内存页为2^10=1024页
1024*4K=4M。
函数体内执行了一个for循环，从给定order的链表开始向上查询。
如果这个链表为空list_empty(&area->free_list)那么继续下一次循环continue
如果这个链表不为空，也就是说此链表中具有空闲的2^order个连续页面，则执行下面的操作:
1) page = list_entry(area->free_list.next, struct page, lru);
获取这个链表的第一个实例，使page指向满足要求的连续内存页（这些页组成了块）的第一页
2） list_del(&page->lru);
从当前链表中删除这些页
3）rmv_page_order(page);
这个函数其实很简单：
 250 static inline void rmv_page_order(struct page *page)
     /*  */
 251 {
 252         __ClearPageBuddy(page);
 253         set_page_private(page, 0);
 254 }
清楚这个页的PG_buddy标志并设置这个页的private字段为0；
4） 594                 area->nr_free--;
    595                 zone->free_pages -= 1UL << order;
空闲块数减1，管理区所有空闲页面数减去1<5） expand(zone, page, order, current_order, area);这个函数负责完成空闲区域链表的重组
 515 static inline void expand(struct zone *zone, struct page *page,
 516         int low, int high, struct free_area *area)
 517 {
 518         unsigned long size = 1 << high;
 519
 520         while (high > low) {
 521                 area--;
 522                 high--;
 523                 size >>= 1;
 524                 BUG_ON(bad_range(zone, &page[size]));
 525                 list_add(&page[size].lru, &area->free_list);
 526                 area->nr_free++;
 527                 set_page_order(&page[size], high);
 528         }
 529 }
current order 大于order时，也就是说没有在请求块大小的链表中找到空闲块，而是在上一级的链表中找到
举个例子会更好的理解：
你请求的块大小为4个页面也就是说order=2 可是这时操作系统发现 4个连续页的块都用完了，这个就让你去order=3
（连续页面数为8的块）中去找，找到了，要进行拆分，把剩下的6个连续页面分为4个和2个，连入到对应的空闲区链表
中去。