核心代碼閱讀(7) - 實體頁面的配置設定alloc_pages

實體頁面的配置設定

核心代碼中申請實體頁面的函數是 alloc_pages

頁面配置設定需要解決的問題

NUMA
buddy和位圖
記憶體不夠時如何處理

NUMA結構的處理邏輯

NUMA的處理是功過宏 CONFIG_NUMA走不同的分支

struct page * alloc_pages(int gfp_mask, unsigned long order)
{
    struct page *ret = 0;
    pg_data_t *start, *temp;
#ifndef CONFIG_NUMA
    unsigned long flags;
    static pg_data_t *next = 0;
#endif
    if (order >= MAX_ORDER)
    return NULL;
#ifdef CONFIG_NUMA
    temp = NODE_DATA(numa_node_id());
#else
    spin_lock_irqsave(&node_lock, flags);
    if (!next) next = pgdat_list;
    temp = next;
    next = next->node_next;
    spin_unlock_irqrestore(&node_lock, flags);
#endif
    start = temp;
    while (temp) {
    if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))
        return(ret);
    temp = temp->node_next;
    }
    temp = pgdat_list;
    while (temp != start) {
    if ((ret = alloc_pages_pgdat(temp, gfp_mask, order)))
        return(ret);
    temp = temp->node_next;
    }
    return(0);
}

0）參數: gfp_mask 是一個整數代表使用哪中配置設定政策；order是配置設定實體頁的大小。

1）若果定義了CONFIG_NUMA 就用 NODE_DATA(numa_node_id()) 擷取目前node對應的pg_data_t，否則就用全局的pgdata_list。

2） pgdata_list是node的一個數組。

3）然後，循環周遊所有的pg_data，也就是循環所有的配置設定政策，從每一個配置設定政策中調用 alloc_pages_pgdat配置設定。

alloc_pages_pgdat

static struct page * alloc_pages_pgdat(pg_data_t *pgdat, int gfp_mask,
                       unsigned long order)
{
return __alloc_pages(pgdat->node_zonelists + gfp_mask, order);
}
1） gfp_mask就是在一個node中的配置設定政策數組的下标 pgdat->node_zonelists + gfp_mask

開始配置設定記憶體__alloc_pages

struct page * __alloc_pages(zonelist_t *zonelist, unsigned long order)
{
    zone_t **zone;
    int direct_reclaim = 0;
    unsigned int gfp_mask = zonelist->gfp_mask;
    struct page * page;
    memory_pressure++;
    if (order == 0 && (gfp_mask & __GFP_WAIT) &&
    !(current->flags & PF_MEMALLOC))
    direct_reclaim = 1;
    if (inactive_shortage() > inactive_target / 2 && free_shortage())
    wakeup_kswapd(0);
    else if (free_shortage() && nr_inactive_dirty_pages > free_shortage()
         && nr_inactive_dirty_pages >= freepages.high)
    wakeup_bdflush(0);

1） memory_pressure 統計VM子系統的壓力

2） gfp_mask 這個 gfp_mask不同于上面那個，代表一個具體的配置設定政策的控制位

#define __GFP_WAIT    0x01
#define __GFP_HIGH    0x02
#define __GFP_IO    0x04
#define __GFP_DMA    0x08
#ifdef CONFIG_HIGHMEM
#define __GFP_HIGHMEM    0x10
#else
#define __GFP_HIGHMEM    0x0 /* noop */
#endif

_GFP_WAIT 表示要等待配置設定完成。
order==0 表示配置設定的是單個頁面
!(current->falgs & PF_MEMALLOC) 表示目前程序不是‘記憶體配置設定的管理程序’
滿足上3個條件就允許從相應管理區“不活躍幹淨頁面”的緩沖隊列中回收， 設定标記direct_reclaim=1。

3）當核心缺少頁面，并且 inactive_shortage 不活躍的頁面的缺口也不多時候，啟動 wakeup_kswapd，幫助交換一些頁面出去。

4）當核心缺少頁面，并且 nr_inactive_dirty_pages 髒頁很多時候，啟動 wakeup_bdflush，幫助刷頁面。

從free pages較多的zone中配置設定

zone = zonelist->zones;
for (;;) {
    zone_t *z = *(zone++);
    if (!z)
    break;
    if (!z->size)
    BUG();
    if (z->free_pages >= z->pages_low) {
    page = rmqueue(z, order);
    if (page)
        return page;
    } else if (z->free_pages < z->pages_min &&
           waitqueue_active(&kreclaimd_wait)) {
    wake_up_interruptible(&kreclaimd_wait);
    }
}

1）周遊目前配置設定測率中的zone。

2）如果zone的 free_pages 高于pages_low水位線就從這個zone中配置設定。

但是不一定保證配置設定成功，因為申請的是連續的2^order實體頁。 free_pages高于low水位線不代表就一定有這麼多的連續的實體頁。

3）如果 free_pages 低于pages_min水位線，而且有程序在 kreclaimd_wait隊列上等待回收頁面，就喚醒這個程序，讓它開始幹活。

從一個zone中配置設定連續的實體頁面rmqueue

static struct page * rmqueue(zone_t *zone, unsigned long order)
{
    free_area_t * area = zone->free_area + order;
    unsigned long curr_order = order;
    struct list_head *head, *curr;
    unsigned long flags;
    struct page *page;
    spin_lock_irqsave(&zone->lock, flags);
    do {
    head = &area->free_list;
    curr = memlist_next(head);
    if (curr != head) {
        unsigned int index;
        page = memlist_entry(curr, struct page, list);
        if (BAD_RANGE(zone,page))
        BUG();
        memlist_del(curr);
        index = (page - mem_map) - zone->offset;
        MARK_USED(index, curr_order, area);
        zone->free_pages -= 1 << order;
        page = expand(zone, page, index, order, curr_order, area);
        spin_unlock_irqrestore(&zone->lock, flags);
        set_page_count(page, 1);
        if (BAD_RANGE(zone,page))
        BUG();
        DEBUG_ADD_PAGE
        return page;    
    }
    curr_order++;
    area++;
    } while (curr_order < MAX_ORDER);
    spin_unlock_irqrestore(&zone->lock, flags);
    return NULL;
}

1）這個函數很重要，是buddy算法和位圖的實作。

2） zone->free_area + order是從order的連結清單開始尋找空閑頁面。

3）進入循環之前對zone->lock上鎖，因為别的程序有可能也正在這個zone上配置設定記憶體。

4） head = &area->free_list;

free_list 是一個雙向隊列，把2^order大小的頁面串了起來，現在從頭部取出一個。

5） page = memlist_entry(curr, struct page, list);

memlist_entry 是在從cur指針，page結構體，以及list在page結構體中的偏移，找到 *page

6） index = (page - mem_map) - zone->offset;

計算出這個空閑的page在mem_map中的偏移量。設定pgd，pte使用的是一個頁面在mem_map的偏移量。

mem_map是指向全局的page大數組的起始位址，而從free_list雙向連結清單通過memlist_entry擷取的是指向一個page的指針。這個指針的值就是在mem_map數組中的。

為什麼要減去zone->offset？ zone->offset 是zone所管理的記憶體區域在mem_map起始偏移量，是以，這個index是在zone的偏移量。

MARK_USED更新位圖，位圖是為了在整理buddy時友善把連續的記憶體結合從更大order時用。參考ULK。

7） zone->free_pages -= 1 << order;

更新目前zone下的空閑記憶體。

8） expand 整理高order記憶體。比如，申請4個頁面，而隻有16個頁面的話，就這個16頁面拆開。

free_pages不夠

page = __alloc_pages_limit(zonelist, order, PAGES_HIGH, direct_reclaim);
page = __alloc_pages_limit(zonelist, order, PAGES_LOW, direct_reclaim);
    
wakeup_kswapd(0);
if (gfp_mask & __GFP_WAIT) {
    __set_current_state(TASK_RUNNING);
    current->policy |= SCHED_YIELD;
    schedule();
}
page = __alloc_pages_limit(zonelist, order, PAGES_MIN, direct_reclaim);

1）若果free_pages不夠多，則把目前zone裡面的inactive_clean_page也算上。

2）嘗試3詢，每次都到一個zone裡，看看這個zone的free_pages+inactive_clean_pages是否高于3個級别的水位線。

3）第3次查詢，說明記憶體已經很吃緊，喚醒kswapd。把目前程序放棄執行權，讓給kswapd。好處有4個。

主動沖洗髒頁

if (!(current->flags & PF_MEMALLOC)) {
    if (order > 0 && (gfp_mask & __GFP_WAIT)) {
    zone = zonelist->zones;
    current->flags |= PF_MEMALLOC;
    page_launder(gfp_mask, 1);
    current->flags &= ~PF_MEMALLOC;
    for (;;) {
        zone_t *z = *(zone++);
        if (!z)
        break;
        if (!z->size)
        continue;
        while (z->inactive_clean_pages) {
        struct page * page;
        page = reclaim_page(z);
        if (!page)
            break;
        __free_page(page);
        page = rmqueue(z, order);
        if (page)
            return page;
        }
    }
    }
    if ((gfp_mask & (__GFP_WAIT|__GFP_IO)) == (__GFP_WAIT|__GFP_IO)) {
    wakeup_kswapd(1);
    memory_pressure++;
    if (!order)
        goto try_again;
    } else if (gfp_mask & __GFP_WAIT) {
    try_to_free_pages(gfp_mask);
    memory_pressure++;
    if (!order)
        goto try_again;
    }
}

0）首先要看目前程序是不是一個‘記憶體的管理者。防止進入死遞歸。

1）不是，如果仍然找不到，并且是大頁面(order>0)，而且設定了__GFP_WAIT，就開始調用page_launder，刷洗髒頁面，從inactive_clean_list回收

2）是，不能再次調用kswapd，因為目前這個程序是記憶體的管理者，就是因為某個時機記憶體不夠用被喚醒了。說明這個程序在管理記憶體（比如kswapd，flushd）時候出現了記憶體吃緊。不能再調用kswapd。

解決方法是：直接調用kswapd對應的邏輯函數。

最後一招放寬水位線

zone = zonelist->zones;
for (;;) {
    zone_t *z = *(zone++);
    struct page * page = NULL;
    if (!z)
    break;
    if (!z->size)
    BUG();
    if (direct_reclaim) {
    page = reclaim_page(z);
    if (page)
        return page;
    }
    if (z->free_pages < z->pages_min / 4 &&
    !(current->flags & PF_MEMALLOC))
    continue;
    page = rmqueue(z, order);
    if (page)
    return page;
}
printk(KERN_ERR "__alloc_pages: %lu-order allocation failed.\n", order);
return NULL;

0）如果 direct_reclaim

1） if (z->free_pages < z->pages_min / 4 && !(current->flags & PF_MEMALLOC)) continue;

如果程序不是 PF_MEMALLOC程序，直接continue。

隻有管理程序才會使用最後一點‘血本’。

核心代碼閱讀(7) - 實體頁面的配置設定alloc_pages

實體頁面的配置設定

頁面配置設定需要解決的問題

NUMA結構的處理邏輯

alloc_pages_pgdat

開始配置設定記憶體__alloc_pages

從free pages較多的zone中配置設定

從一個zone中配置設定連續的實體頁面rmqueue

free_pages不夠

主動沖洗髒頁

最後一招放寬水位線

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希