Linux内存管理之伙伴系统（内存释放）

Linux内核伙伴系统中页面释放，主函数为free_pages()

一、上层操作

1. /*用虚拟地址进行释放*/  
   
2. void free_pages(unsigned long addr, unsigned int order)  
   
3. {  
   
4.     if (addr != 0) {  
   
5.         VM_BUG_ON(!virt_addr_valid((void *)addr));  
   
6.         __free_pages(virt_to_page((void *)addr), order);/*具体的释放函数*/  
   
7.     }  
   
8. }  

1. /*释放页面*/  
   
2. void __free_pages(struct page *page, unsigned int order)  
   
3. {  
   
4.     if (put_page_testzero(page)) {/*count值减一为0时释放*/  
   
5.         /*调试*/  
   
6.         trace_mm_page_free_direct(page, order);  
   
7.         if (order == 0)  
   
8.             free_hot_page(page);/*释放单个页面*/  
   
9.         else  
   
10.             __free_pages_ok(page, order);  
    
11.     }  
    
12. }  

二、释放单个页面

释放单个页面free_hot_page()调用free_hot_cold_page()函数

1. static void free_hot_cold_page(struct page *page, int cold)  
   
2. {  
   
3.     struct zone *zone = page_zone(page);  
   
4.     struct per_cpu_pages *pcp;  
   
5.     unsigned long flags;  
   
6.     int migratetype;  
   
7.     int wasMlocked = __TestClearPageMlocked(page);  
   
8.     /*调试代码*/  
   
9.     kmemcheck_free_shadow(page, 0);  
   
10.   
    
11.     if (PageAnon(page))  
    
12.         page->mapping = NULL;  
    
13.     if (free_pages_check(page))  
    
14.         return;  
    
15.   
    
16.     if (!PageHighMem(page)) {  
    
17.         debug_check_no_locks_freed(page_address(page), PAGE_SIZE);  
    
18.         debug_check_no_obj_freed(page_address(page), PAGE_SIZE);  
    
19.     }  
    
20.     /*x86下为空*/  
    
21.     arch_free_page(page, 0);  
    
22.     /*调试用*/  
    
23.     kernel_map_pages(page, 1, 0);  
    
24.     /*获得zone对应cpu的pcp*/  
    
25.     pcp = &zone_pcp(zone, get_cpu())->pcp;  
    
26.     /*获得页面的migratetype*/  
    
27.     migratetype = get_pageblock_migratetype(page);  
    
28.     set_page_private(page, migratetype);/*设置私有位为参数*/  
    
29.     local_irq_save(flags);/*保存中断*/  
    
30.     if (unlikely(wasMlocked))  
    
31.         free_page_mlock(page);  
    
32.     __count_vm_event(PGFREE);  
    
33.   
    
34.     /* 
    
35.      * We only track unmovable, reclaimable and movable on pcp lists. 
    
36.      * Free ISOLATE pages back to the allocator because they are being 
    
37.      * offlined but treat RESERVE as movable pages so we can get those 
    
38.      * areas back if necessary. Otherwise, we may have to free 
    
39.      * excessively into the page allocator 
    
40.      */  
    
41.     if (migratetype >= MIGRATE_PCPTYPES) {  
    
42.         if (unlikely(migratetype == MIGRATE_ISOLATE)) {  
    
43.             /*释放到伙伴系统 */  
    
44.             free_one_page(zone, page, 0, migratetype);  
    
45.             goto out;  
    
46.         }  
    
47.         migratetype = MIGRATE_MOVABLE;  
    
48.     }  
    
49.   
    
50.     if (cold)/*加入到pcp链表尾部*/  
    
51.         list_add_tail(&page->lru, &pcp->lists[migratetype]);  
    
52.     else/*加入到pcp链表头部*/  
    
53.         list_add(&page->lru, &pcp->lists[migratetype]);  
    
54.     pcp->count++;/*pcp计数加一*/  
    
55.     if (pcp->count >= pcp->high) {/*当pcp中页面数量超过他的最高值时， 
    
56.         释放pcp->batch个页面到伙伴系统中*/  
    
57.         free_pcppages_bulk(zone, pcp->batch, pcp);  
    
58.         pcp->count -= pcp->batch;/*页面数减去释放的页面数量*/  
    
59.     }  
    
60.   
    
61. out:  
    
62.     local_irq_restore(flags);/*回复中断*/  
    
63.     put_cpu();  
    
64. }  

从pcp中释放页面到伙伴系统中

free_pcppages_bulk()

1. are in same zone, and of same order.  
   
2.  * count is the number of pages to free.  
   
3.  *  
   
4.  * If the zone was previously in an “all pages pinned” state then look to  
   
5.  * see if this freeing clears that state.  
   
6.  *  
   
7.  * And clear the zone’s pages_scanned counter, to hold off the “all pages are  
   
8.  * pinned” detection logic.  
   
9.  */  
   
10.  /*从PCP中释放count个页面到伙伴系统中*/  
    
11. static void free_pcppages_bulk(struct zone *zone, int count,  
    
12.                     struct per_cpu_pages *pcp)  
    
13. {  
    
14.     int migratetype = 0;  
    
15.     int batch_free = 0;  
    
16.     /* 
    
17.      * 虽然管理区可以按照CPU节点分类，但是也可以跨CPU节点进行内存分配， 
    
18.      * 因此这里需要用自旋锁保护管理区  
    
19.      * 使用每CPU缓存的目的，也是为了减少使用这把锁。 
    
20.      */  
    
21.     spin_lock(&zone->lock);  
    
22.     /* all_unreclaimable代表了内存紧张程度，释放内存后，将此标志清除 */  
    
23.     zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);  
    
24.     zone->pages_scanned = 0;/* pages_scanned代表最后一次内存紧张以来，页面回收过程已经扫描的页数。 
    
25.     目前正在释放内存，将此清0，待回收过程随后回收时重新计数 */  
    
26.   
    
27.     /*增加管理区空闲页数*/  
    
28.     __mod_zone_page_state(zone, NR_FREE_PAGES, count);  
    
29.     while (count) {  
    
30.         struct page *page;  
    
31.         struct list_head *list;  
    
32.   
    
33.         /* 
    
34.          * Remove pages from lists in a round-robin fashion. A 
    
35.          * batch_free count is maintained that is incremented when an 
    
36.          * empty list is encountered.  This is so more pages are freed 
    
37.          * off fuller lists instead of spinning excessively around empty 
    
38.          * lists 
    
39.          */  
    
40.         do {/*从pcp的三类链表中找出不空的一个，释放*/  
    
41.             batch_free++;/*参看英文注释*/  
    
42.             if (++migratetype == MIGRATE_PCPTYPES)  
    
43.                 migratetype = 0;  
    
44.             list = &pcp->lists[migratetype];  
    
45.         } while (list_empty(list));  
    
46.   
    
47.         do {  
    
48.             page = list_entry(list->prev, struct page, lru);  
    
49.             /* must delete as __free_one_page list manipulates */  
    
50.             list_del(&page->lru);  
    
51.             /*释放单个页面到伙伴系统，注意这里的分类回收*/  
    
52.             __free_one_page(page, zone, 0, migratetype);  
    
53.             trace_mm_page_pcpu_drain(page, 0, migratetype);  
    
54.         } while (–count && –batch_free && !list_empty(list));  
    
55.     }  
    
56.     spin_unlock(&zone->lock);  
    
57. }  

三、释放多个页面

释放多个页面__free_pages_ok()函数

1. int i;  


2. int bad = 0;  


3. int wasMlocked = __TestClearPageMlocked(page);  


4. /*调试用，和相关宏有关*/  


5. kmemcheck_free_shadow(page, order);  


6.   


7. for (i = 0 ; i < (1 << order) ; ++i)/*页面相关检查*/  


8.     bad += free_pages_check(page + i);  


9. if (bad)  


10.     return;  


11.   


12. if (!PageHighMem(page)) {  


13.     debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);  


14.     debug_check_no_obj_freed(page_address(page),  


15.                    PAGE_SIZE << order);  


16. }  


17. /*X86体系下为空*/  


18. arch_free_page(page, order);  


19. /*调试，相关宏定义*/  


20. kernel_map_pages(page, 1 << order, 0);  


21.   


22. local_irq_save(flags);/*flags的暂存，关中断*/  


23. if (unlikely(wasMlocked))  


24.     free_page_mlock(page);  


25. __count_vm_events(PGFREE, 1 << order);  


26. /*传入参数，进行具体的释放工作，将1<<order的页面释放 


27. 到伙伴系统中*/  


28. free_one_page(page_zone(page), page, order,  


29.                 get_pageblock_migratetype(page));/*获得内存块的类型*/  


30. local_irq_restore(flags);/*恢复中断*/  

1. static void free_one_page(struct zone *zone, struct page *page, int order,  


2.                 int migratetype)  


3. {  


4.     spin_lock(&zone->lock);/*获得管理区的自旋锁*/  


5.     zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);/* 只要是释放了页面，都需要将此两个标志清0，表明内存不再紧张的事实*/  


6.     zone->pages_scanned = 0;  


7.     /*管理区空闲页面计数*/  


8.     __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);  


9.     /*释放到指定的伙伴系统类型链表*/  


10.     __free_one_page(page, zone, order, migratetype);  


11.     spin_unlock(&zone->lock);/*释放锁*/  


12. }  

1. etype)  


2. {  


3.     unsigned long page_idx;  


4.   


5.     if (unlikely(PageCompound(page)))/*要释放的页是巨页的一部分*/  


6.         /* 解决巨页标志，如果巨页标志有问题，则退出 */  


7.         if (unlikely(destroy_compound_page(page, order)))  


8.             return;  


9.   


10.     VM_BUG_ON(migratetype == -1);  


11.     /*将页面转化为全局页面数组的下标*/  


12.     page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) – 1);  


13.     /* 如果被释放的页不是所释放阶的第一个页，则说明参数有误 */  


14.     VM_BUG_ON(page_idx & ((1 << order) – 1));  


15.     /* 校验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中 */  


16.     VM_BUG_ON(bad_range(zone, page));  


17.   


18.     while (order < MAX_ORDER-1) {  


19.         unsigned long combined_idx;  


20.         struct page *buddy;  


21.         /*找出page页面的伙伴 


22.          查找待释放页块的伙伴 ,其中伙伴系统中每个块 


23.          都有一个对应同样大小的”伙伴块”(由2的指数原理知)*/  


24.         buddy = __page_find_buddy(page, page_idx, order);  


25.         if (!page_is_buddy(page, buddy, order))/*检查页面是否为伙伴*/  


26.             break;  


27.   


28.         /* Our buddy is free, merge with it and move up one order. */  


29.         list_del(&buddy->lru);  


30.         zone->free_area[order].nr_free–;  


31.          /* 为下面的合并做准备，清除伙伴的PG_buddy标志位，并设置伙伴的private成员为 


32.             0 */  


33.         rmv_page_order(buddy);  


34.         /* 利用伙伴算法公式计算合并后父节点的页块索引 */  


35.         /*实际上是这样的，这个要配合上面的找buddy 


36.         *算法一起看，找出的buddy时在原来的下标中往上或向下走 


37.         *(1<<order个位置 


38.         *而这里的函数是找出合并后的新块的首地址 


39.         *也就是说如果上面是加，这里的基地址不变 


40.         *而如果上面是减，这里往下减1<<order 


41.         *其中这里的标号不是物理地址，也不是和mem_map 


42.         *直接关联，而是运用于buddy算法，也就是这里的 


43.         *构造出来的特定的表示，他使得这里的伙伴的寻找 


44.         *和伙伴的合并实现的很巧妙 


45.         */  


46.         combined_idx = __find_combined_index(page_idx, order);  


47.         page = page + (combined_idx – page_idx);  


48.         page_idx = combined_idx;  


49.         order++;  


50.     }  


51.     set_page_order(page, order);/*设置page的私有属性，伙伴系统通过这个值来 


52.                             确定页面所属的order*/  


53.     list_add(&page->lru,  


54.         &zone->free_area[order].free_list[migratetype]);/*伙伴系统中每一种order有5中空闲链表*/  


55.     zone->free_area[order].nr_free++;/*对应order的空闲块加一*/  


56. }  

四、关于伙伴的操作

4.1，查找伙伴

1. static inline struct page *  


2. __page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)  


3. {  


4.     /*伙伴的计算原理， 


5.     *实际上，使用(1<<order)掩码的异或(XOR)转换page_idx第order位 


6.     *的值。因此，如果这个位原来是0，buddy_idx就等于page_idx+order 


7.     *相反，如果这个位原先是1，buddy_idx就等于page_idx-order 


8.     *此计算出来的伙伴为在mem_map中的下标 


9.     */    


10.     unsigned long buddy_idx = page_idx ^ (1 << order);  


11.     /*返回伙伴块的页面基址*/  


12.     return page + (buddy_idx – page_idx);  


13. }  

4.2，检查是否为伙伴

1. static inline int page_is_buddy(struct page *page, struct page *buddy,  


2.                                 int order)  


3. {  


4.     if (!pfn_valid_within(page_to_pfn(buddy)))/*验证此buddy的有效性*/  


5.         return 0;  


6.   


7.     if (page_zone_id(page) != page_zone_id(buddy))/*验证page和他的buddy是否在同一个zone中*/  


8.         return 0;  


9.     /*验证相关位和buddy的order值*/  


10.     /* 通过检查PG_buddy 标志位判断buddy是否在伙伴系统中，并且buddy是否在order级的 


11.      链表中，page的private成员存放页块所在链表的order。*/  


12.     if (PageBuddy(buddy) && page_order(buddy) == order) {  


13.         VM_BUG_ON(page_count(buddy) != 0);  


14.         return 1;  


15.     }  


16.     return 0;  


17. }  

总结：伙伴系统内存释放或称主要流程

1，如果释放的是单个页面，需要根据页面类型考虑是否释放到伙伴系统中，同时，将其加入到pcp链表中。如果pcp链表中内存过多，调用free_pcppages_bulk()函数将大块内存放回伙伴系统中；

2，如果释放的是多个页面，直接调用__free_one_page()释放到伙伴系统中。

3，释放到伙伴系统中时，需要考虑和伙伴的合并情况。