歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux基礎 >> Linux基礎知識

linux內存源碼分析 - 伙伴系統(釋放頁框)

  翻了一下之前的文章,發現竟然忘記寫內核是如何釋放頁框的,罪過。

  釋放頁框很簡單,其實只有幾步

  1. 檢查此頁是否被其他進程使用(檢查頁描述符的_count是否為0)。
  2. 如果是釋放單個頁框,則優先把它放回到該CPU的單頁框高速緩存鏈表中,如果該CPU的單頁框高速緩存的頁框過多,則把該CPU的頁框高速緩存中的pcp->batch個頁框放回伙伴系統鏈表中。
  3. 在放回伙伴系統的過程中,會與旁邊的空閒頁框合並,放入更高等級的order鏈表中,比如釋放的是兩個連續頁框,會檢查前後是否能合成為4個連續頁框,再檢查是否能合成為8個,直到不能合成位置,並將這些連續頁框放入對應的鏈表中。

  釋放頁框的操作最後都會調用到__free_pages()函數,我們主要從這個函數跟蹤下去,看看內核是怎麼執行的。

/* 釋放頁框 */
void __free_pages(struct page *page, unsigned int order)
{
    /* 檢查頁框是否還有進程在使用,就是檢查_count變量的值是否為0 */
    if (put_page_testzero(page)) {
        /* 如果是1個頁框,則放回每CPU高速緩存中,如果是多個頁框,則放回伙伴系統,放回CPU高速緩存中優先把其設置為熱頁,而不是冷頁 */
        if (order == 0)
            free_hot_cold_page(page, false);
        else
            __free_pages_ok(page, order);
    }
}

  熱頁冷頁的意思就是:當一個頁被釋放時,默認設置為熱頁,因為該頁可能有些地址還處於映射到CPUcache的情況,當該CPU上有進程申請單個頁框時,優先把這些熱頁分配出去,這樣能提高cache命中率,提高效率。而實現方法也很簡單,如果是熱頁,則把它加入到CPU頁框高速緩存鏈表的鏈表頭,如果是冷頁,則加入到鏈表尾,如下:

void free_hot_cold_page(struct page *page, bool cold)
{
    /* 頁框所處管理區 */
    struct zone *zone = page_zone(page);
    struct per_cpu_pages *pcp;
    unsigned long flags;
    /* 頁框號 */
    unsigned long pfn = page_to_pfn(page);
    int migratetype;

    /* 檢查 */
    if (!free_pages_prepare(page, 0))
        return;

    /* 獲取頁框類型 */
    migratetype = get_pfnblock_migratetype(page, pfn);
    /* 設置頁框類型 */
    set_freepage_migratetype(page, migratetype);
    local_irq_save(flags);
    __count_vm_event(PGFREE);

    if (migratetype >= MIGRATE_PCPTYPES) {
        /* 如果不是高速緩存類型,則放回伙伴系統 */
        if (unlikely(is_migrate_isolate(migratetype))) {
            free_one_page(zone, page, pfn, 0, migratetype);
            goto out;
        }
        migratetype = MIGRATE_MOVABLE;
    }

    /* 放入當前CPU高速緩存中 */
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
    if (!cold)
        list_add(&page->lru, &pcp->lists[migratetype]);
    else
        list_add_tail(&page->lru, &pcp->lists[migratetype]);
    pcp->count++;

    /* 當前CPU高速緩存中頁框數量高於最大值,將pcp->batch數量的頁框放回伙伴系統 */
    if (pcp->count >= pcp->high) {
        unsigned long batch = ACCESS_ONCE(pcp->batch);
        free_pcppages_bulk(zone, batch, pcp);
        pcp->count -= batch;
    }

out:
    local_irq_restore(flags);
}

   無論是單個頁框的釋放,還是連續多個頁框的釋放,最後都是調用到free_one_page()函數,這個函數的第四個參數指明了order值:

static void free_one_page(struct zone *zone,
                struct page *page, unsigned long pfn,
                unsigned int order,
                int migratetype)
{
    unsigned long nr_scanned;
    /* 管理區上鎖 */
    spin_lock(&zone->lock);
    
    /* 數據更新 */
    nr_scanned = zone_page_state(zone, NR_PAGES_SCANNED);
    if (nr_scanned)
        __mod_zone_page_state(zone, NR_PAGES_SCANNED, -nr_scanned);

    /* 內存隔離使用 */
    if (unlikely(has_isolate_pageblock(zone) ||
        is_migrate_isolate(migratetype))) {
        migratetype = get_pfnblock_migratetype(page, pfn);
    }
    /* 釋放page開始的order次方個頁框到伙伴系統,這些頁框的類型時migratetype */
    __free_one_page(page, pfn, zone, order, migratetype);
    /* 管理區解鎖 */
    spin_unlock(&zone->lock);
}

 

  整個釋放過程的核心函數就是__free_one_page(),裡面有個算法是分析是否能夠對此段頁框附近的頁框進行合並的,其實原理很簡單,往前檢查order次方個連續頁框是否為空閒頁框,再往後檢查order次方個連續頁框是否為空閒頁框,如果其中一者成立,則合並,並order++,繼續檢查,但是注意,這些頁框都必須為同一個管理區,因為伙伴系統是以管理區為單位的。如下:

static inline void __free_one_page(struct page *page,
        unsigned long pfn,
        struct zone *zone, unsigned int order,
        int migratetype)
{
    /* 保存塊中第一個頁框的下標,這個下標相對於管理區而言,而不是node */
    unsigned long page_idx;
    unsigned long combined_idx;
    unsigned long uninitialized_var(buddy_idx);
    struct page *buddy;
    int max_order = MAX_ORDER;

    VM_BUG_ON(!zone_is_initialized(zone));

    if (unlikely(PageCompound(page)))
        if (unlikely(destroy_compound_page(page, order)))
            return;

    VM_BUG_ON(migratetype == -1);
    if (is_migrate_isolate(migratetype)) {
        /*
         * We restrict max order of merging to prevent merge
         * between freepages on isolate pageblock and normal
         * pageblock. Without this, pageblock isolation
         * could cause incorrect freepage accounting.
         */
        /* 如果使用了內存隔離,則最大的order應該為MAX_ORDER與pageblock_order+1中最小那個,實際上在沒有大頁的情況下,這兩個值相等,如果有大頁的情況下,則不一定 */
        max_order = min(MAX_ORDER, pageblock_order + 1);
    } else {
        __mod_zone_freepage_state(zone, 1 << order, migratetype);
    }

    /* page的pfn號 */
    page_idx = pfn & ((1 << max_order) - 1);

    VM_BUG_ON_PAGE(page_idx & ((1 << order) - 1), page);
    VM_BUG_ON_PAGE(bad_range(zone, page), page);

    /* 主要,最多循環10次,每次都盡量把一個塊和它的伙伴進行合並,以最小塊開始 */
    while (order < max_order - 1) {
        /* buddy_idx = page_idx ^ (1 << order) */
        /* buddy_idx是page_idx的伙伴的頁框號 */
        /* 伙伴的頁框號就是page_idx的第(1 << order)位的相反數,比如(1<<order)是4,page_idx是01110,則buddy_idx是01010,由此可見伙伴並不一定是之後的區間 */
        /*
         *      對於000000 ~ 001000這個頁框號區間,假設order是3,左邊是第一種情況,右邊是另一種情況
         *
         *                            -----------
         *                           |           |
         *                           |           |
         *                           |           |
         * page_idx = 000100 ------> |-----------|    計算後buddy_idx = 000100
         *                           |           |
         *                           |           |
         *                           |           |
         * 計算後buddy_idx = 000000   -----------     page_idx = 000000
         */
        buddy_idx = __find_buddy_index(page_idx, order);
        /* 伙伴的頁描述符,就是buddy_idx對應的頁描述符 */
        buddy = page + (buddy_idx - page_idx);
        
        /* 檢查buddy是否描述了大小為order的空閒頁框塊的第一個頁 */
        if (!page_is_buddy(page, buddy, order))
            break;
        /*
         * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
         * merge with it and move up one order.
         */
        if (page_is_guard(buddy)) {
            /* 設置了PAGE_DEBUG_FLAG_GUARD */
            clear_page_guard_flag(buddy);
            set_page_private(buddy, 0);
            if (!is_migrate_isolate(migratetype)) {
                __mod_zone_freepage_state(zone, 1 << order,
                              migratetype);
            }
        } else {
            /* 將伙伴從當前空閒鏈表中移除出來 */
            list_del(&buddy->lru);
            zone->free_area[order].nr_free--;
            rmv_page_order(buddy);
        }
        /* combined_idx 是 buddy_idx 與 page_idx 中最小的那個idx */
        combined_idx = buddy_idx & page_idx;
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    set_page_order(page, order);
    /* 循環結束,標記了釋放的連續page已經和之後的連續頁形成了一個2的order次方的連續頁框塊 */
    
    /* 檢查能否再進一步合並 */
    if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
        struct page *higher_page, *higher_buddy;
        combined_idx = buddy_idx & page_idx;
        higher_page = page + (combined_idx - page_idx);
        buddy_idx = __find_buddy_index(combined_idx, order + 1);
        higher_buddy = higher_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++;
}

 

  整個頁框釋放過程就是這樣,也比較簡單,或許就最後那個合並算法會稍微復雜一些。

Copyright © Linux教程網 All Rights Reserved