Linux內存管理之伙伴系統（內存分配）

伙伴系統分配器大體上分為兩類。__get_free_pages()類函數返回分配的第一個頁面的線性地址；alloc_pages()類函數返回頁面描述符地址。不管以哪種函數進行分配，最終會調用alloc_pages()進行分配頁面。

為清楚了解其分配制度，先給個伙伴系統數據的存儲框圖

也就是每個order對應一個free_area結構，free_area以不同的類型以鏈表的方式存儲這些內存塊。

二、主分配函數

下面我們來看這個函數（在UMA模式下）

1. #define alloc_pages(gfp_mask, order) \   
2.         alloc_pages_node(numa_node_id(), gfp_mask, order)  
3.    

1. static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,  
2.                         unsigned int order)  
3. {  
4.     /* Unknown node is current node */  
5.     if (nid < 0)  
6.         nid = numa_node_id();  
7.   
8.     return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));  
9. }  

1. static inline struct page *  
2. __alloc_pages(gfp_t gfp_mask, unsigned int order,  
3.         struct zonelist *zonelist)  
4. {  
5.     return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);  
6. }  

上層分配函數__alloc_pages_nodemask()

1. /* 
2.  * This is the 'heart' of the zoned buddy allocator. 
3.  */  
4.  /*上層分配器運用了各種方式進行*/  
5. struct page *  
6. __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,  
7.             struct zonelist *zonelist, nodemask_t *nodemask)  
8. {  
9.     enum zone_type high_zoneidx = gfp_zone(gfp_mask);  
10.     struct zone *preferred_zone;  
11.     struct page *page;  
12.       
13.     /* Convert GFP flags to their corresponding migrate type */  
14.     int migratetype = allocflags_to_migratetype(gfp_mask);  
15.   
16.     gfp_mask &= gfp_allowed_mask;  
17.     /*調試用*/  
18.     lockdep_trace_alloc(gfp_mask);  
19.     /*如果__GFP_WAIT標志設置了，需要等待和重新調度*/  
20.     might_sleep_if(gfp_mask & __GFP_WAIT);  
21.     /*沒有設置對應的宏*/  
22.     if (should_fail_alloc_page(gfp_mask, order))  
23.         return NULL;  
24.   
25.     /* 
26.      * Check the zones suitable for the gfp_mask contain at least one 
27.      * valid zone. It's possible to have an empty zonelist as a result 
28.      * of GFP_THISNODE and a memoryless node 
29.      */  
30.     if (unlikely(!zonelist->_zonerefs->zone))  
31.         return NULL;  
32.   
33.     /* The preferred zone is used for statistics later */  
34.     /* 英文注釋所說*/  
35.     first_zones_zonelist(zonelist, high_zoneidx, nodemask, &preferred_zone);  
36.     if (!preferred_zone)  
37.         return NULL;  
38.   
39.     /* First allocation attempt */  
40.     /*從pcp和伙伴系統中正常的分配內存空間*/  
41.     page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,  
42.             zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET,  
43.             preferred_zone, migratetype);  
44.     if (unlikely(!page))/*如果上面沒有分配到空間，調用下面函數慢速分配，允許等待和回收*/  
45.         page = __alloc_pages_slowpath(gfp_mask, order,  
46.                 zonelist, high_zoneidx, nodemask,  
47.                 preferred_zone, migratetype);  
48.     /*調試用*/  
49.     trace_mm_page_alloc(page, order, gfp_mask, migratetype);  
50.     return page;  
51. }  

三、從pcp和伙伴系統中正常的分配內存空間

函數get_page_from_freelist()

1. /* 
2.  * get_page_from_freelist goes through the zonelist trying to allocate 
3.  * a page. 
4.  */  
5. /*為分配制定內存空間，遍歷每個zone*/  
6. static struct page *  
7. get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,  
8.         struct zonelist *zonelist, int high_zoneidx, int alloc_flags,  
9.         struct zone *preferred_zone, int migratetype)  
10. {  
11.     struct zoneref *z;  
12.     struct page *page = NULL;  
13.     int classzone_idx;  
14.     struct zone *zone;  
15.     nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */  
16.     int zlc_active = 0;     /* set if using zonelist_cache */  
17.     int did_zlc_setup = 0;      /* just call zlc_setup() one time */  
18.     /*zone對應的下標*/  
19.     classzone_idx = zone_idx(preferred_zone);  
20. zonelist_scan:  
21.     /* 
22.      * Scan zonelist, looking for a zone with enough free. 
23.      * See also cpuset_zone_allowed() comment in kernel/cpuset.c. 
24.      */  
25.      /*遍歷每個zone，進行分配*/  
26.     for_each_zone_zonelist_nodemask(zone, z, zonelist,  
27.         /*在UMA模式下不成立*/              high_zoneidx, nodemask) {  
28.         if (NUMA_BUILD && zlc_active &&  
29.             !zlc_zone_worth_trying(zonelist, z, allowednodes))  
30.                 continue;  
31.         if ((alloc_flags & ALLOC_CPUSET) &&  
32.             !cpuset_zone_allowed_softwall(zone, gfp_mask))  
33.                 goto try_next_zone;  
34.   
35.         BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);  
36.         /*需要關注水位*/  
37.         if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {  
38.             unsigned long mark;  
39.             int ret;  
40.             /*從flags中取的mark*/  
41.             mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];  
42.             /*如果水位正常，從本zone中分配*/  
43.             if (zone_watermark_ok(zone, order, mark,  
44.                     classzone_idx, alloc_flags))  
45.                 goto try_this_zone;  
46.   
47.             if (zone_reclaim_mode == 0)/*如果上面檢查的水位低於正常值，且沒有設置頁面回收值*/  
48.                 goto this_zone_full;  
49.             /*在UMA模式下下面函數直接返回0*/  
50.             ret = zone_reclaim(zone, gfp_mask, order);  
51.             switch (ret) {  
52.             case ZONE_RECLAIM_NOSCAN:  
53.                 /* did not scan */  
54.                 goto try_next_zone;  
55.             case ZONE_RECLAIM_FULL:  
56.                 /* scanned but unreclaimable */  
57.                 goto this_zone_full;  
58.             default:  
59.                 /* did we reclaim enough */  
60.                 if (!zone_watermark_ok(zone, order, mark,  
61.                         classzone_idx, alloc_flags))  
62.                     goto this_zone_full;  
63.             }  
64.         }  
65.   
66. try_this_zone:/*本zone正常水位*/  
67.     /*先從pcp中分配，然後不行的話再從伙伴系統中分配*/  
68.         page = buffered_rmqueue(preferred_zone, zone, order,  
69.                         gfp_mask, migratetype);  
70.         if (page)  
71.             break;  
72. this_zone_full:  
73.         if (NUMA_BUILD)/*UMA模式為0*/  
74.             zlc_mark_zone_full(zonelist, z);  
75. try_next_zone:  
76.         if (NUMA_BUILD && !did_zlc_setup && nr_online_nodes > 1) {  
77.             /* 
78.              * we do zlc_setup after the first zone is tried but only 
79.              * if there are multiple nodes make it worthwhile 
80.              */  
81.             allowednodes = zlc_setup(zonelist, alloc_flags);  
82.             zlc_active = 1;  
83.             did_zlc_setup = 1;  
84.         }  
85.     }  
86.   
87.     if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {  
88.         /* Disable zlc cache for second zonelist scan */  
89.         zlc_active = 0;  
90.         goto zonelist_scan;  
91.     }  
92.     return page;/*返回頁面*/  
93. }  

主分配函數

1. /* 
2.  * Really, prep_compound_page() should be called from __rmqueue_bulk().  But 
3.  * we cheat by calling it from here, in the order > 0 path.  Saves a branch 
4.  * or two. 
5.  */  
6.  /*先考慮從pcp中分配空間，當order大於0時再考慮從伙伴系統中分配*/  
7. static inline  
8. struct page *buffered_rmqueue(struct zone *preferred_zone,  
9.             struct zone *zone, int order, gfp_t gfp_flags,  
10.             int migratetype)  
11. {  
12.     unsigned long flags;  
13.     struct page *page;  
14.     int cold = !!(gfp_flags & __GFP_COLD);/*如果分配參數指定了__GFP_COLD標志，則設置cold標志*/  
15.     int cpu;  
16.   
17. again:  
18.     cpu  = get_cpu();  
19.     if (likely(order == 0)) {/*分配一個頁面時，使用pcp*/  
20.         struct per_cpu_pages *pcp;  
21.         struct list_head *list;  
22.         /*找到zone對應的pcp*/  
23.         pcp = &zone_pcp(zone, cpu)->pcp;  
24.         list = &pcp->lists[migratetype];/*pcp中對應類型的list*/  
25.           
26.         /* 這裡需要關中斷，因為內存回收過程可能發送核間中斷，強制每個核從每CPU 
27.         緩存中釋放頁面。而且中斷處理函數也會分配單頁。 */  
28.         local_irq_save(flags);  
29.         if (list_empty(list)) {/*如果pcp中沒有頁面,需要補充*/  
30.             /*從伙伴系統中獲得batch個頁面 
31.             batch為一次分配的頁面數*/  
32.             pcp->count += rmqueue_bulk(zone, 0,  
33.                     pcp->batch, list,  
34.                     migratetype, cold);  
35.             /*如果鏈表仍然為空，申請失敗返回*/  
36.             if (unlikely(list_empty(list)))  
37.                 goto failed;  
38.         }  
39.         /* 如果分配的頁面不需要考慮硬件緩存(注意不是每CPU頁面緩存) 
40.         ，則取出鏈表的最後一個節點返回給上層*/  
41.         if (cold)  
42.             page = list_entry(list->prev, struct page, lru);  
43.         else/* 如果要考慮硬件緩存，則取出鏈表的第一個頁面，這個頁面是最近剛釋放到每CPU 
44.             緩存的，緩存熱度更高 */  
45.             page = list_entry(list->next, struct page, lru);  
46.   
47.         list_del(&page->lru);/*從pcp中脫離*/  
48.         pcp->count--;/*pcp計數減一*/  
49.     }   
50.     else {/*當order為大於1時，不從pcp中分配，直接考慮從伙伴系統中分配*/  
51.         if (unlikely(gfp_flags & __GFP_NOFAIL)) {  
52.             /* 
53.              * __GFP_NOFAIL is not to be used in new code. 
54.              * 
55.              * All __GFP_NOFAIL callers should be fixed so that they 
56.              * properly detect and handle allocation failures. 
57.              * 
58.              * We most definitely don't want callers attempting to 
59.              * allocate greater than order-1 page units with 
60.              * __GFP_NOFAIL. 
61.              */  
62.             WARN_ON_ONCE(order > 1);  
63.         }  
64.         /* 關中斷，並獲得管理區的鎖*/  
65.         spin_lock_irqsave(&zone->lock, flags);  
66.         /*從伙伴系統中相應類型的相應鏈表中分配空間*/  
67.         page = __rmqueue(zone, order, migratetype);  
68.         /* 已經分配了1 << order個頁面，這裡進行管理區空閒頁面統計計數*/  
69.         __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));  
70.         spin_unlock(&zone->lock);/* 這裡僅僅打開自旋鎖，待後面統計計數設置完畢後再開中斷*/  
71.         if (!page)  
72.             goto failed;  
73.     }  
74.     /*事件統計計數，調試*/  
75.     __count_zone_vm_events(PGALLOC, zone, 1 << order);  
76.     zone_statistics(preferred_zone, zone);  
77.     local_irq_restore(flags);/*恢復中斷*/  
78.     put_cpu();  
79.   
80.     VM_BUG_ON(bad_range(zone, page));  
81.       
82.      /* 這裡進行安全性檢查，並進行一些善後工作。 
83.       如果頁面標志破壞，返回的頁面出現了問題，則返回試圖分配其他頁面*/  
84.     if (prep_new_page(page, order, gfp_flags))  
85.         goto again;  
86.     return page;  
87.   
88. failed:  
89.     local_irq_restore(flags);  
90.     put_cpu();  
91.     return NULL;  
92. }