摘要：本文主要講述linux如何處理ARM cortex A9多核處理器的記憶體管理部分。主要包括對夥伴系統算法流程的介紹。
1.1.1 夥伴系統 1.1.1.1 從緩存中釋放單個頁面到夥伴系統
當釋放單個頁面時，頁面首先放回到每CPU的頁面緩存中，以減少自旋鎖的使用。當頁面緩存中的頁面數量超過閥值時，再将頁面放回到夥伴系統中。相應的函數是free_pcppages_bulk：
/**
* 從每CPU緩存中釋放一定數量的頁面到夥伴系統中。
*/
static void free_pcppages_bulk(struct zone *zone, int count,
struct per_cpu_pages *pcp)
{
int migratetype = 0;
int batch_free = 0;
int to_free = count;
/**
* 雖然管理區可以按照CPU節點分類，但是也可以跨CPU節點進行記憶體配置設定，是以這裡需要用自旋鎖保護管理區
* 使用每CPU緩存的目的，也是為了減少使用這把鎖。
*/
spin_lock(&zone->lock);
/* all_unreclaimable代表了記憶體緊張程度，釋放記憶體後，将此标志清除 */
zone->all_unreclaimable = 0;
zone->pages_scanned = 0;/* pages_scanned代表最後一次記憶體緊張以來，頁面回收過程已經掃描的頁數。目前正在釋放記憶體，将此清0，待回收過程随後回收時重新計數 */
while (to_free) {/* 連續釋放指定數量的頁面到夥伴系統 */
struct page *page;
struct list_head *list;
/* 這裡是從MIGRATE_UNMOVABLE到MIGRATE_MOVABLE三個每CPU緩存連結清單中依次搜尋一個可釋放的頁面，直到找到一個可以回收的緩存連結清單。 */
do {
batch_free++;/* batch_free是最後掃描的連結清單索引 */
if (++migratetype == MIGRATE_PCPTYPES)/* 隻從MIGRATE_UNMOVABLE..MIGRATE_MOVABLE三個連結清單中選擇頁面。從這三個連結清單中循環選擇回收的頁面 */
migratetype = 0;
list = &pcp->lists[migratetype];
} while (list_empty(list));/* 如果目前連結清單為空，則從下一個緩存連結清單中釋放頁面 */
/* This is the only non-empty list. Free them all. */
if (batch_free == MIGRATE_PCPTYPES)/* 隻有一個緩存連結清單中有可回收頁面，則從該連結清單中釋放所有頁面 */
batch_free = to_free;
do {/* 本循環從最後一個頁面緩存連結清單中釋放多個頁面到夥伴系統，越靠後的緩存連結清單，釋放的頁面數量越多 */
page = list_entry(list->prev, struct page, lru);/* 取緩存連結清單的最後一個元素，要麼是最早放到緩存中的頁面(其硬體緩存的熱度也最低)，要麼就是"冷"頁，不需要考慮硬體緩存 */
/* must delete as __free_one_page list manipulates */
list_del(&page->lru);/* 将頁面從連結清單中摘除 */
/* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
/* 将頁面釋放回夥伴系統。注意這裡沒有用migratetype變量，而是用頁面屬性中的migratetype。原因請參見英文注釋 */
__free_one_page(page, zone, 0, page_private(page));
trace_mm_page_pcpu_drain(page, 0, page_private(page));/* 調試代碼 */
} while (--to_free && --batch_free && !list_empty(list));
}
/* 空閑頁面計數 */
__mod_zone_page_state(zone, NR_FREE_PAGES, count);
spin_unlock(&zone->lock);
}
1.1.1.2 釋放多個頁面到夥伴系統
一次性配置設定和釋放多個頁面，都不經過每CPU緩存，而是直接從夥伴系統中配置設定、直接傳回給夥伴系統。
向夥伴系統釋放頁面的函數是free_one_page，這個函數有點名不副實。它并不是指釋放一個頁面，而是釋放多個頁面，不知道核心為何取如此奇怪的名字。
* 将多個頁面釋放到夥伴系統。
static void free_one_page(struct zone *zone, struct page *page, int order,
int migratetype)
spin_lock(&zone->lock);/* 獲得管理區的自旋鎖 */
zone->all_unreclaimable = 0;/* 隻要是釋放了頁面，都需要将此兩個标志清0，表明記憶體不再緊張的事實 */
zone->pages_scanned = 0;
/* 在鎖的保護下，調用__free_one_page操作夥伴系統，将頁面釋放回夥伴系統 */
__free_one_page(page, zone, order, migratetype);
/* 管理區空閑頁面計數 */
__mod_zone_page_state(zone, NR_FREE_PAGES, 1 order);
spin_unlock(&zone->lock);/* 釋放管理區自旋鎖 */
在獲得管理區鎖的情況下，不管是釋放一個頁還是多個頁到夥伴系統，均使用函數__free_one_page：
* 在獲得管理區自旋鎖的情況下，将頁面歸還給夥伴系統。
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order,
int migratetype)
unsigned long page_idx;
unsigned long combined_idx;
unsigned long uninitialized_var(buddy_idx);
struct page *buddy;
if (unlikely(PageCompound(page)))/* 要釋放的頁是巨頁的一部分 */
if (unlikely(destroy_compound_page(page, order)))/* 解決巨頁标志，如果巨頁标志有問題，則退出 */
return;
VM_BUG_ON(migratetype == -1);
page_idx = page_to_pfn(page) & ((1 MAX_ORDER) - 1);
VM_BUG_ON(page_idx & ((1 order) - 1));/* 如果被釋放的頁不是所釋放階的第一個頁，則說明參數有誤 */
VM_BUG_ON(bad_range(zone, page));/* 檢查頁面是否處于zone之中 */
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;
/* Our buddy is free, merge with it and move up one order. */
list_del(&buddy->lru);/* 如果能夠合并，則将夥伴頁從夥伴系統中摘除 */
zone->free_area[order].nr_free--;/* 同時減少目前階中的空閑頁計數 */
rmv_page_order(buddy);/* 清除夥伴頁的夥伴标志，因為該頁會被合并 */
combined_idx = buddy_idx & page_idx;
/* 将目前頁與夥伴頁合并後，新的頁面起始位址 */
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
/* 設定夥伴頁中第一個空閑頁的階 */
set_page_order(page, order);
* 如果目前合并後的頁不是最大階的，那麼将目前空閑頁放到夥伴連結清單的最後。
* 這樣，它将不會被很快被配置設定，更有可能與更高階頁面進行合并。
*/
if ((order MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
struct page *higher_page, *higher_buddy;
/* 計算更高階的頁面索引及頁面位址 */
higher_page = page + (combined_idx - page_idx);
buddy_idx = __find_buddy_index(combined_idx, order + 1);
higher_buddy = page + (buddy_idx - combined_idx);
if (page_is_buddy(higher_page, higher_buddy, order + 1)) {/* 更高階的頁面是空閑的，屬于夥伴系統 */
list_add_tail(&page->lru,
&zone->free_area[order].free_list[migratetype]);/* 将目前頁面合并到空閑連結清單的最後，盡量避免将它配置設定出去 */
goto out;
}
/* 更高階的頁面已經配置設定出去，那麼将目前頁面放到連結清單前面 */
list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
/* 将目前階的空閑計數加1 */
zone->free_area[order].nr_free++;
1.1.1.3 從夥伴系統中獲得頁面
從夥伴系統中配置設定頁面的函數是buffered_rmqueue：
* 從夥伴系統中配置設定頁面
static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
struct zone *zone, int order, gfp_t gfp_flags,
int migratetype)
unsigned long flags;
struct page *page;
int cold = !!(gfp_flags & __GFP_COLD);/* 如果配置設定參數指定了__GFP_COLD标志，則設定cold标志 */
again:
if (likely(order == 0)) {/* 配置設定單頁，需要管理每CPU頁面緩存 */
struct per_cpu_pages *pcp;
/* 這裡需要關中斷，因為記憶體回收過程可能發送核間中斷，強制每個核從每CPU緩存中釋放頁面。而且中斷處理函數也會配置設定單頁。 */
local_irq_save(flags);
/* 取得本CPU的頁面緩存對象 */
pcp = &this_cpu_ptr(zone->pageset)->pcp;
/* 根據使用者指定的遷移類型，從指定的遷移緩存連結清單中配置設定 */
list = &pcp->lists[migratetype];
if (list_empty(list)) {/* 緩存為空，需要擴大緩存的大小 */
/* 從夥伴系統中摘除一批頁面到緩存中，補充的頁面個數由每CPU緩存的batch字段指定 */
pcp->count += rmqueue_bulk(zone, 0,
pcp->batch, list,
migratetype, cold);
/* 如果連結清單仍然為空，那麼說明夥伴系統中頁面也沒有了，配置設定失敗。 */
if (unlikely(list_empty(list)))
goto failed;
if (cold)
/* 如果配置設定的頁面不需要考慮硬體緩存(注意不是每CPU頁面緩存)，則取對外連結表的最後一個節點傳回給上層 */
page = list_entry(list->prev, struct page, lru);
else
/* 如果要考慮硬體緩存，則取對外連結表的第一個頁面，這個頁面是最近剛釋放到每CPU緩存的，緩存熱度更高 */
page = list_entry(list->next, struct page, lru);
/* 将頁面從每CPU緩存連結清單中取出，并将每CPU緩存計數減1 */
list_del(&page->lru);
pcp->count--;
} else {/* 配置設定的是多個頁面，不需要考慮每CPU頁面緩存，直接從系統中配置設定 */
if (unlikely(gfp_flags & __GFP_NOFAIL)) {/* __GFP_NOFAIL已經不推薦使用，不再分析 */
/*
* __GFP_NOFAIL is not to be used in new code.
*
* All __GFP_NOFAIL callers should be fixed so that they
* properly detect and handle allocation failures.
* We most definitely don't want callers attempting to
* allocate greater than order-1 page units with
* __GFP_NOFAIL.
*/
WARN_ON_ONCE(order > 1);
/* 關中斷，并獲得管理區的鎖 */
spin_lock_irqsave(&zone->lock, flags);
/* 調用__rmqueue從夥伴系統中配置設定頁面 */
page = __rmqueue(zone, order, migratetype);
/* 這裡僅僅打開自旋鎖，待後面統計計數設定完畢後再開中斷 */
spin_unlock(&zone->lock);
if (!page)
goto failed;
/* 已經配置設定了1
__mod_zone_page_state(zone, NR_FREE_PAGES, -(1 order));
/* 事件統計計數，調試用 */
__count_zone_vm_events(PGALLOC, zone, 1 order);
zone_statistics(preferred_zone, zone, gfp_flags);
local_irq_restore(flags);/* 恢複中斷 */
VM_BUG_ON(bad_range(zone, page));
* 這裡進行安全性檢查，并進行一些善後工作。
* 如果頁面标志破壞，傳回的頁面出現了問題，則傳回試圖配置設定其他頁面。
* 核心會有這樣的BUG存在嗎?除了驅動或者子產品有問題外?
if (prep_new_page(page, order, gfp_flags))
goto again;
return page;
failed:
local_irq_restore(flags);
return NULL;
這裡使用了一個輔助函數rmqueue_bulk：
* 從夥伴系統中批量取出多個頁面。
* 用于從夥伴系統中批量取出頁面放到每CPU頁面緩存中
static int rmqueue_bulk(struct zone *zone, unsigned int order,
unsigned long count, struct list_head *list,
int migratetype, int cold)
int i;
spin_lock(&zone->lock);/* 上層函數已經關了中斷，這裡需要操作管理區，擷取管理區的自旋鎖 */
for (i = 0; i count; ++i) {/* 重複指定的次數，從夥伴系統中配置設定頁面 */
/* 從夥伴系統中取出頁面 */
struct page *page = __rmqueue(zone, order, migratetype);
/* 夥伴系統中沒有空閑頁了，退出 */
if (unlikely(page == NULL))
/*
* Split buddy pages returned by expand() are received here
* in physical page order. The page is added to the callers and
* list and the list head then moves forward. From the callers
* perspective, the linked list is ordered by page number in
* some conditions. This is useful for IO devices that can
* merge IO requests if the physical pages are ordered
* properly.
*/
if (likely(cold == 0))/* 根據調用者的要求，将頁面放到每CPU緩存連結清單的頭部或者尾部 */
list_add(&page->lru, list);
list_add_tail(&page->lru, list);
/* 設定頁面的遷移類型 */
set_page_private(page, migratetype);
list = &page->lru;
/* 遞減管理區的空閑頁面計數。 */
__mod_zone_page_state(zone, NR_FREE_PAGES, -(i order));
spin_unlock(&zone->lock);/* 釋放管理區的自旋鎖 */
return i;
1.1.1.4 __rmqueue函數
夥伴系統配置設定頁面的總入口是__rmqueue函數:
* 從管理區的夥伴系統中取出頁面。該函數是配置設定夥伴頁的真正入口。
* zone: 從該管理區的夥伴系統中配置設定頁面.
* order: 要配置設定的頁面階數.即配置設定的頁面數是2^order
* migratetype: 優先從本參數指定的遷移類型中配置設定頁面.如果失敗,再從備用遷移清單中配置設定.
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
retry_reserve:
/* 優先從指定的遷移類型連結清單中配置設定頁面 */
page = __rmqueue_smallest(zone, order, migratetype);
* 如果滿足以下兩個條件,就從備用連結清單中配置設定頁面:
* 快速流程沒有配置設定到頁面,需要從備用遷移連結清單中配置設定.
* 目前不是從保留的連結清單中配置設定.因為保留的連結清單是最後可用的連結清單,不能從該連結清單配置設定的話,說明本管理區真的沒有可用記憶體了.
if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
/* 從備用連結清單中配置設定頁面. */
page = __rmqueue_fallback(zone, order, migratetype);
* Use MIGRATE_RESERVE rather than fail an allocation. goto
* is used because __rmqueue_smallest is an inline function
* and we want just one call site
if (!page) {/* 備用連結清單中沒有配置設定到頁面,看來得吃老本,從保留連結清單中配置設定頁面了 */
migratetype = MIGRATE_RESERVE;
goto retry_reserve;/* 跳轉到retry_reserve,從保留的連結清單中配置設定頁面 */
/* 調試代碼,很高興可以飄過 */
trace_mm_page_alloc_zone_locked(page, order, migratetype);
快速流程的處理函數是__rmqueue_smallest:
* 周遊指定遷移類型的夥伴系統連結清單,從連結清單中移動最小數量的頁面傳回給調用者.這是夥伴系統的快速處理流程.
* zone: 在該管理區的夥伴系統中配置設定頁面
* order: 要配置設定的頁面數量階.
* migratetype: 在該遷移類型的連結清單中擷取頁面
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
unsigned int current_order;
struct free_area * area;
/* Find a page of the appropriate size in the preferred list */
/* 從指定的階到最大階進行周遊,直到找到一個可以配置設定的連結清單 */
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);
/* 将第一個元素從連結清單中摘除 */
/* rmv_page_order将頁面的夥伴标志位清0,表示該頁不再屬于夥伴系統.同時将Private标志清0 */
rmv_page_order(page);
/* 目前階的空閑計數減1 */
area->nr_free--;
/**
* 如果目前階沒有可用的空閑頁,而必須将高階的空閑頁面分割,則expand将高階的頁面分割後放回夥伴系統
* 如:我們将階為4的頁面分割,并向上層傳回階為2的頁面,那麼,我們需要将其中階為3,2的頁面放回夥伴系統.
expand(zone, page, order, current_order, area, migratetype);
return page;
輔助函數expand:
* 将高階的頁面分割成低階的頁面,并放回夥伴系統.
* low: 配置設定出去的低階
* high: 被分割的高階
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;/* 要被分割的高階頁面數量 */
* 我們假設将階為4的頁面組分割,并配置設定出去階為2的頁
* 那麼我們需要向夥伴系統中分别加入階為2,3的頁面組.
* 這種情況下,high=4,low=2
while (high > low) {
area--;/* area,high,size分别表示本次要放回夥伴系統的連結清單指針,階,目前階的頁面數量 */
high--;
size >>= 1;
/* 檢查要加入夥伴系統的第一頁是否在管理區的範圍内 */
VM_BUG_ON(bad_range(zone, &page[size]));
/* 将第一頁鍊入相應的遷移類型連結清單中 */
list_add(&page[size].lru, &area->free_list[migratetype]);
/* 該階的空閑頁面計數值加1 */
area->nr_free++;
/* 标記頁面的階 */
set_page_order(&page[size], high);
夥伴系統的慢速處理流程是:
* 如果管理區的目前遷移連結清單中沒有可配置設定的頁面時,則從備用遷移連結清單中配置設定
static inline struct page *
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
int current_order;
int migratetype, i;
/* Find the largest possible block of pages in the other list */
/* 從最高階搜尋,這樣可以盡量的将其他遷移清單中的大塊分割,避免形成過多的碎片 */
for (current_order = MAX_ORDER-1; current_order >= order;
--current_order) {
for (i = 0; i MIGRATE_TYPES - 1; i++) {/* 周遊備用的遷移連結清單 */
migratetype = fallbacks[start_migratetype][i];
/* MIGRATE_RESERVE handled later if necessary */
/* 本函數不處理MIGRATE_RESERVE類型的遷移連結清單,如果本函數傳回NULL,則上層函數直接從MIGRATE_RESERVE中配置設定 */
if (migratetype == MIGRATE_RESERVE)
continue;
area = &(zone->free_area[current_order]);
/* 備用連結清單沒有可用的頁面,繼續搜尋下一連結清單 */
if (list_empty(&area->free_list[migratetype]))
/* 取備用連結清單的第一個元素 */
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
/* 備用連結清單的目前階計數減1 */
area->nr_free--;
* If breaking a large block of pages, move all free
* pages to the preferred allocation list. If falling
* back for a reclaimable kernel allocation, be more
* aggressive about taking ownership of free pages
if (unlikely(current_order >= (pageblock_order >> 1)) ||/* 要分割的頁面是一個大頁面,則将整個頁面全部遷移到目前遷移類型的連結清單中,這樣可以避免過多的碎片 */
start_migratetype == MIGRATE_RECLAIMABLE ||/* 目前配置設定的是可回收頁面,這類頁面有突發的特點,将頁面全部遷移到可回收連結清單中,可以避免将其他遷移連結清單分割成太多的碎片 */
page_group_by_mobility_disabled) {/* 指定了遷移政策,總是将被分割的頁面遷移 */
unsigned long pages;
/* 将頁面從目前遷移連結清單轉換到start_migratetype指定的遷移連結清單中 */
pages = move_freepages_block(zone, page,
start_migratetype);
/* Claim the whole block if over half of it is free */
/* pages是移動的頁面數,如果可移動的頁面數量較多,則将整個大記憶體塊的遷移類型修改 */
if (pages >= (1 (pageblock_order-1)) ||
page_group_by_mobility_disabled)
set_pageblock_migratetype(page,
migratetype = start_migratetype;
}
/* Remove the page from the freelists */
/* 将頁面從夥伴夥伴系統連結清單中移除 */
list_del(&page->lru);
rmv_page_order(page);
/* Take ownership for orders >= pageblock_order */
if (current_order >= pageblock_order)
change_pageblock_range(page, current_order,
start_migratetype);
/* 将大階的頁面塊中未用的部分還回夥伴系統 */
expand(zone, page, order, current_order, area, migratetype);
trace_mm_page_alloc_extfrag(page, order, current_order,
start_migratetype, migratetype);
return page;
![MySQL - order by排序優化[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)