伙伴算法的實(shí)現(xiàn)-分配頁框
內(nèi)核中alloc_pages系列頁框分配函數(shù)都是基于伙伴算法實(shí)現(xiàn)的，這些函數(shù)最終都會(huì)調(diào)用伙伴算法的入口函數(shù)buffered_rmqueue()。
Linux內(nèi)核管理物理內(nèi)存有三種方式，其一就是經(jīng)典的伙伴算法。但是伙伴算法分配物理內(nèi)存的基本單位是頁框，因此內(nèi)核又引入了slab機(jī)制，基于此機(jī)制實(shí)現(xiàn)的物理內(nèi)存分配器可以快速有效的分配小于頁框的物理內(nèi)存，并且可以有效避免內(nèi)部碎片。另外，內(nèi)核常常會(huì)申請(qǐng)單個(gè)頁框大小的物理內(nèi)存，因此內(nèi)核又引入了per-CPU機(jī)制，該機(jī)制專門用于快速分配單個(gè)頁框。
1.__rmqueue()
其實(shí)buffered_rmqueue()函數(shù)仍然沒有進(jìn)行真正的頁框分配，該函數(shù)首先判斷分配階是否為0，如果是則啟用per-CPU機(jī)制來分配物理內(nèi)存，否則調(diào)用__rmqueue（）。
static struct page *__rmqueue(struct zone *zone, unsigned int order,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int migratetype)
? ?{
? ? ? ? ? ?struct page *page;
? ? ? ? ? ?retry_reserve:
? ? ? ? ? ?page = __rmqueue_smallest(zone, order, migratetype);
?
? ? ? ? ? ?if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
? ? ? ? ? ? ? ? ? ?page = __rmqueue_fallback(zone, order, migratetype);
?
? ? ? ? ? ? ? ? ? ?if (!page) {
? ? ? ? ? ? ? ? ? ? ? ? ? ?migratetype = MIGRATE_RESERVE;
? ? ? ? ? ? ? ? ? ? ? ? ? ?goto retry_reserve;
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
?
? ? ? ? ? ?trace_mm_page_alloc_zone_locked(page, order, migratetype);
? ? ? ? ? ?return page;
? ?}傳遞到此函數(shù)中的zone表示伙伴算法將從該內(nèi)存管理區(qū)中分配頁框，order即分配階，migratetype表示遷移類型。該函數(shù)首選__rmqueue_smallest()進(jìn)行內(nèi)存分配，如果在指定的遷移類型上分配失敗后，再選用其他備用的遷移列表進(jìn)行內(nèi)存分配，該過程通過__rmqueue_fallback()完成?？傊畠?nèi)核總是在竭盡全力保證滿足分配內(nèi)存的請(qǐng)求。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ?
2.__rmqueue_smallest()
該函數(shù)的實(shí)現(xiàn)比較簡(jiǎn)單，從當(dāng)前指定的分配階到最高分配階依次進(jìn)行遍歷。在每次遍歷的分配階鏈表中，根據(jù)參數(shù)migratetype選擇正確的遷移隊(duì)列。根據(jù)以上的限定條件，當(dāng)選定一個(gè)頁框塊鏈表后，只要該鏈表不為空，就說明可以分配該分配階對(duì)應(yīng)的頁框塊。
一旦選定在當(dāng)前遍歷的分配階鏈表上分配頁框，那么就通過list_entry（）將該頁框塊從鏈表上移除。然后將頁框塊首頁框的PG_buddy標(biāo)志刪除，刪除該標(biāo)志說明當(dāng)前頁框塊已經(jīng)不屬于伙伴鏈表。并且將該首頁框描述符中的priveate置0，該字段中本來保存的是其所處頁框塊的分配階。以上這個(gè)過程通過rmv_page_order()完成。此外，還要更新頁框塊鏈表nr_free的值。
static inline
? ?struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int migratetype)
? ?{
? ? ? ? ? ?unsigned int current_order;
? ? ? ? ? ?struct free_area * area;
? ? ? ? ? ?struct page *page;
?
? ? ? ? ? ?for (current_order = order; current_order < MAX_ORDER; ++current_order) {
? ? ? ? ? ? ? ? ? ?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--;
? ? ? ? ? ? ? ? ? ?expand(zone, page, order, current_order, area, migratetype);
? ? ? ? ? ? ? ? ? ?return page;
? ? ? ? ? ?}
?
? ? ? ? ? ?return NULL;
? ?}
?
? ?static inline void rmv_page_order(struct page *page)
? ?{
? ? ? ? ? ?__ClearPageBuddy(page);
? ? ? ? ? ?set_page_private(page, 0);
? ?}__rmqueue_smallest()內(nèi)部還有一個(gè)重要的函數(shù)expand()。進(jìn)入該函數(shù)的條件是當(dāng)所申請(qǐng)的分配階order小于當(dāng)前選中的分配階current_order，也就是說指定的分配階鏈表中沒有空閑的頁框塊，只能選用較大的頁框塊。因此，expand()必須按照伙伴算法的分裂原理將比較大的頁框塊分割成較小的塊。
3.expand()
分裂函數(shù)的實(shí)現(xiàn)也是顯而易見的，它完全遵照伙伴算法的分裂原理。這里有兩個(gè)分配階，一個(gè)是申請(qǐng)頁框時(shí)指定的low，一個(gè)是在上級(jí)函數(shù)中遍歷時(shí)所選定的high。該函數(shù)從high分配階開始遞減向low遍歷，也就是從較大的頁框塊開始依次分裂。
比如high為4，而low為2。那么第一遍歷時(shí)，將大小為16（分配階為4）的頁框塊一份為2。通過list_add()將后面的8個(gè)連續(xù)頁框塊加入下級(jí)鏈表（分配階為3），下級(jí)鏈表通過將area指針自減即可得到，后8個(gè)頁框塊的指針也通過page+size獲得，而page仍然指向最初的頁框塊首頁框。此時(shí)還要對(duì)分配階為3的鏈表更新nr_free，以及通過set_page_order()對(duì)后8個(gè)頁框塊設(shè)置一些標(biāo)志。
第二次遍歷將前面8個(gè)頁框塊繼續(xù)一分為二，將后4個(gè)頁框塊加入area所指向的下級(jí)鏈表（分配階為2）。第三次遍歷時(shí)，循環(huán)條件已經(jīng)不再滿足，因此返回前4個(gè)頁框塊首頁框的描述符地址page。
static inline void expand(struct zone *zone, struct page *page,
? ? ? ? ? ?int low, int high, struct free_area *area,
? ? ? ? ? ?int migratetype)
? ?{
? ? ? ? ? ?unsigned long size = 1 << high;
? ? ? ? ? ? while (high > low) {
? ? ? ? ? ? ? ? ? ?area--;
? ? ? ? ? ? ? ? ? ?high--;
? ? ? ? ? ? ? ? ? ?size >>= 1;
? ? ? ? ? ? ? ? ? ?VM_BUG_ON(bad_range(zone, &page[size]));
? ? ? ? ? ? ? ? ? ?list_add(&page[size].lru, &area->free_list[migratetype]);
? ? ? ? ? ? ? ? ? ?area->nr_free++;
? ? ? ? ? ? ? ? ? ?set_page_order(&page[size], high);
? ? ? ? ? ?}
? ?}
?
? ?static inline void set_page_order(struct page *page, int order)
? ?{
? ? ? ? ? ?set_page_private(page, order);
? ? ? ? ? ?__SetPageBuddy(page);
? ?}
