Linux-31.14.12メモリ管理ノート【パートナー管理アルゴリズム(5)】-コアアルゴリズムの実現

前にパートナー管理アルゴリズムのリリースを分析しましたが、パートナー管理アルゴリズムのメモリ申請を分析して実現します.
パートナー管理アルゴリズムのメモリ申請は釈放の入り口と同じですが、この関数は入り口であり、それは入り口ではないので、少し上の場所から入り口として分析されています.そこでalloc_を選びました.パージ()マクロ定義を分析の切り口として使用します.

【file:/include/linux/gfp.h】
#define alloc_pages(gfp_mask, order) \
        alloc_pages_node(numa_node_id(), gfp_mask, order)

alloc_pages_node()の実現:

【file:/include/linux/gfp.h】
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
                        unsigned int order)
{
    /* Unknown node is current node */
    if (nid < 0)
        nid = numa_node_id();
 
    return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
}

メモリ出願のnodeノードが明確にされていない場合は、デフォルトでは現在のnodeノードを出願ノードとして選択します.下に続けて__u u uを呼び出します.alloc_Pages()は具体的なメモリを申請しにきて、その中はnode_に参加します.zonelist()は、nodeノードを取得するためのzone管理エリアリストである.次に下を見てください.alloc_Pages()の実装:

【file:/include/linux/gfp.h】
static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order,
        struct zonelist *zonelist)
{
    return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}

実はパッケージになっていますalloc_pages_nodemask().そうしてまたalloc_pages_nodemask()の実現:

【file:/mm/page_alloc.c】
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
            struct zonelist *zonelist, nodemask_t *nodemask)
{
    enum zone_type high_zoneidx = gfp_zone(gfp_mask);
    struct zone *preferred_zone;
    struct page *page = NULL;
    int migratetype = allocflags_to_migratetype(gfp_mask);
    unsigned int cpuset_mems_cookie;
    int alloc_flags = ALLOC_WMARK_LOW|ALLOC_CPUSET|ALLOC_FAIR;
    struct mem_cgroup *memcg = NULL;
 
    gfp_mask &= gfp_allowed_mask;
 
    lockdep_trace_alloc(gfp_mask);
 
    might_sleep_if(gfp_mask & __GFP_WAIT);
 
    if (should_fail_alloc_page(gfp_mask, order))
        return NULL;
 
    /*
     * Check the zones suitable for the gfp_mask contain at least one
     * valid zone. It's possible to have an empty zonelist as a result
     * of GFP_THISNODE and a memoryless node
     */
    if (unlikely(!zonelist->_zonerefs->zone))
        return NULL;
 
    /*
     * Will only have any effect when __GFP_KMEMCG is set. This is
     * verified in the (always inline) callee
     */
    if (!memcg_kmem_newpage_charge(gfp_mask, &memcg, order))
        return NULL;
 
retry_cpuset:
    cpuset_mems_cookie = get_mems_allowed();
 
    /* The preferred zone is used for statistics later */
    first_zones_zonelist(zonelist, high_zoneidx,
                nodemask ? : &cpuset_current_mems_allowed,
                &preferred_zone);
    if (!preferred_zone)
        goto out;
 
#ifdef CONFIG_CMA
    if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
        alloc_flags |= ALLOC_CMA;
#endif
retry:
    /* First allocation attempt */
    page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
            zonelist, high_zoneidx, alloc_flags,
            preferred_zone, migratetype);
    if (unlikely(!page)) {
        /*
         * The first pass makes sure allocations are spread
         * fairly within the local node. However, the local
         * node might have free pages left after the fairness
         * batches are exhausted, and remote zones haven't
         * even been considered yet. Try once more without
         * fairness, and include remote zones now, before
         * entering the slowpath and waking kswapd: prefer
         * spilling to a remote zone over swapping locally.
         */
        if (alloc_flags & ALLOC_FAIR) {
            reset_alloc_batches(zonelist, high_zoneidx,
                        preferred_zone);
            alloc_flags &= ~ALLOC_FAIR;
            goto retry;
        }
        /*
         * Runtime PM, block IO and its error handling path
         * can deadlock because I/O on the device might not
         * complete.
         */
        gfp_mask = memalloc_noio_flags(gfp_mask);
        page = __alloc_pages_slowpath(gfp_mask, order,
                zonelist, high_zoneidx, nodemask,
                preferred_zone, migratetype);
    }
 
    trace_mm_page_alloc(page, order, gfp_mask, migratetype);
 
out:
    /*
     * When updating a task's mems_allowed, it is possible to race with
     * parallel threads in such a way that an allocation can fail while
     * the mask is being updated. If a page allocation is about to fail,
     * check if the cpuset changed during allocation and if so, retry.
     */
    if (unlikely(!put_mems_allowed(cpuset_mems_cookie) && !page))
        goto retry_cpuset;
 
    memcg_kmem_commit_charge(page, memcg, order);
 
    return page;
}

そのうちlockdep_トレイalloc()はCONFIG_が必要ですTRACE_IQFLAGSとCONFIG_PROVE_LOCKINGが同時に定義されている時に、機能します.さもなければ、空の関数です.申請ページが入ってきたらgfp_maskマスクを携帯しますGFP_WAITマークは、ページ申請時に休止するとmight_に入るという意味です.sleep_if()スリープ待ち時間および再スケジュールが必要かどうかを確認する.CONFIG_は設置されていないためFAIL_PAGE_ALLOCではショルダード(u)fail_alloc_page()はfalseに一定に戻ります.if(unlikely(!zonelist->_zonenenesefs->zone)は、現在の申請ページのメモリ管理エリアzoneが空かどうかを確認するために使用されます.memcg_kmem_newpage_charge()とmemcg_kmem_comitcharge()は制御グループグループCgroupに関連している.ゲットするmems_allowed()はread_を封入しました.seqcount_begin()は、現在の順序カウントされた保護された共有リソースを取得して読み出しアクセスするためのシーケンス番号であり、合併を回避するための失敗であり、その組み合わせの操作関数はput(u)である.mems_allowed();first_zones.zonelist()はnodemaskによるもので、適当なものを見つけたら高揚しないようにします.zoneidxのメモリ管理エリアpreferred uzoneまたallocflags_to_migratype()は、GFPを変換して正しい移動タイプとして識別するためのものです.
最後に_alloc_pages_nodemask()メモリページを割り当てる鍵関数は、get_です.page_fromfreelist()と_ualloc_pages_slowpath()の中でget_page_fromfreelist()は最初にページの割り当てを試します.もし割り当てが失敗したら、さらに呼び出します.alloc_pages_slowpath()alloc_pages_slowpath()はスローページの割り当てで、待ち時間とメモリの回収を許可します._によるalloc_pages_slowpath()は他のメモリ管理機構に関連しており、ここでは分析をしばらく見合わせている.
だから最後にget_を分析します.page_fromfreelist()の実現:

【file:/mm/page_alloc.c】
/*
 * get_page_from_freelist goes through the zonelist trying to allocate
 * a page.
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
        struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
        struct zone *preferred_zone, int migratetype)
{
    struct zoneref *z;
    struct page *page = NULL;
    int classzone_idx;
    struct zone *zone;
    nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
    int zlc_active = 0; /* set if using zonelist_cache */
    int did_zlc_setup = 0; /* just call zlc_setup() one time */
 
    classzone_idx = zone_idx(preferred_zone);
zonelist_scan:
    /*
     * Scan zonelist, looking for a zone with enough free.
     * See also __cpuset_node_allowed_softwall() comment in kernel/cpuset.c.
     */
    for_each_zone_zonelist_nodemask(zone, z, zonelist,
                        high_zoneidx, nodemask) {
        unsigned long mark;
 
        if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
            !zlc_zone_worth_trying(zonelist, z, allowednodes))
                continue;
        if ((alloc_flags & ALLOC_CPUSET) &&
            !cpuset_zone_allowed_softwall(zone, gfp_mask))
                continue;
        BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
        if (unlikely(alloc_flags & ALLOC_NO_WATERMARKS))
            goto try_this_zone;
        /*
         * Distribute pages in proportion to the individual
         * zone size to ensure fair page aging. The zone a
         * page was allocated in should have no effect on the
         * time the page has in memory before being reclaimed.
         */
        if (alloc_flags & ALLOC_FAIR) {
            if (!zone_local(preferred_zone, zone))
                continue;
            if (zone_page_state(zone, NR_ALLOC_BATCH) <= 0)
                continue;
        }
        /*
         * When allocating a page cache page for writing, we
         * want to get it from a zone that is within its dirty
         * limit, such that no single zone holds more than its
         * proportional share of globally allowed dirty pages.
         * The dirty limits take into account the zone's
         * lowmem reserves and high watermark so that kswapd
         * should be able to balance it without having to
         * write pages from its LRU list.
         *
         * This may look like it could increase pressure on
         * lower zones by failing allocations in higher zones
         * before they are full. But the pages that do spill
         * over are limited as the lower zones are protected
         * by this very same mechanism. It should not become
         * a practical burden to them.
         *
         * XXX: For now, allow allocations to potentially
         * exceed the per-zone dirty limit in the slowpath
         * (ALLOC_WMARK_LOW unset) before going into reclaim,
         * which is important when on a NUMA setup the allowed
         * zones are together not big enough to reach the
         * global limit. The proper fix for these situations
         * will require awareness of zones in the
         * dirty-throttling and the flusher threads.
         */
        if ((alloc_flags & ALLOC_WMARK_LOW) &&
            (gfp_mask & __GFP_WRITE) && !zone_dirty_ok(zone))
            goto this_zone_full;
 
        mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];
        if (!zone_watermark_ok(zone, order, mark,
                       classzone_idx, alloc_flags)) {
            int ret;
 
            if (IS_ENABLED(CONFIG_NUMA) &&
                    !did_zlc_setup && nr_online_nodes > 1) {
                /*
                 * we do zlc_setup if there are multiple nodes
                 * and before considering the first zone allowed
                 * by the cpuset.
                 */
                allowednodes = zlc_setup(zonelist, alloc_flags);
                zlc_active = 1;
                did_zlc_setup = 1;
            }
 
            if (zone_reclaim_mode == 0 ||
                !zone_allows_reclaim(preferred_zone, zone))
                goto this_zone_full;
 
            /*
             * As we may have just activated ZLC, check if the first
             * eligible zone has failed zone_reclaim recently.
             */
            if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
                !zlc_zone_worth_trying(zonelist, z, allowednodes))
                continue;
 
            ret = zone_reclaim(zone, gfp_mask, order);
            switch (ret) {
            case ZONE_RECLAIM_NOSCAN:
                /* did not scan */
                continue;
            case ZONE_RECLAIM_FULL:
                /* scanned but unreclaimable */
                continue;
            default:
                /* did we reclaim enough */
                if (zone_watermark_ok(zone, order, mark,
                        classzone_idx, alloc_flags))
                    goto try_this_zone;
 
                /*
                 * Failed to reclaim enough to meet watermark.
                 * Only mark the zone full if checking the min
                 * watermark or if we failed to reclaim just
                 * 1<pfmemalloc is set when ALLOC_NO_WATERMARKS was
         * necessary to allocate the page. The expectation is
         * that the caller is taking steps that will free more
         * memory. The caller should avoid the page being used
         * for !PFMEMALLOC purposes.
         */
        page->pfmemalloc = !!(alloc_flags & ALLOC_NO_WATERMARKS);
 
    return page;
}

この関数は主に、各メモリ管理エリアのリストを巡回して、ページアプリケーションを試しています.そのうちfor_each_zoneゾネリストnodemask()はzonelistを巡回するためのもので、各メモリ管理エリアは申請を試みる前に、メモリ管理エリアに割り当て可能なメモリ空間があるかどうかを確認し、alloc_によるとflagsは、現在のCPUが当該メモリ管理エリアzoneに申請及びウォーターマークのチェックを許可しているかどうかを判断し、zoneのメモリが十分かなどを判断します.この部分の機能的実現は,パートナー管理アルゴリズムの実現に向けて現在主に焦点を合わせて,後に詳細に分析されるであろう.
メモリページを割り当てるために本当に使われている関数が見つかりにくくないです.rmqueue()、その実現:

【file:/mm/page_alloc.c】
/*
 * Really, prep_compound_page() should be called from __rmqueue_bulk(). But
 * we cheat by calling it from here, in the order > 0 path. Saves a branch
 * or two.
 */
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);
 
again:
    if (likely(order == 0)) {
        struct per_cpu_pages *pcp;
        struct list_head *list;
 
        local_irq_save(flags);
        pcp = &this_cpu_ptr(zone->pageset)->pcp;
        list = &pcp->lists[migratetype];
        if (list_empty(list)) {
            pcp->count += rmqueue_bulk(zone, 0,
                    pcp->batch, list,
                    migratetype, cold);
            if (unlikely(list_empty(list)))
                goto failed;
        }
 
        if (cold)
            page = list_entry(list->prev, struct page, lru);
        else
            page = list_entry(list->next, struct page, lru);
 
        list_del(&page->lru);
        pcp->count--;
    } else {
        if (unlikely(gfp_flags & __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);
        page = __rmqueue(zone, order, migratetype);
        spin_unlock(&zone->lock);
        if (!page)
            goto failed;
        __mod_zone_freepage_state(zone, -(1 << order),
                      get_pageblock_migratetype(page));
    }
 
    __mod_zone_page_state(zone, NR_ALLOC_BATCH, -(1 << order));
 
    __count_zone_vm_events(PGALLOC, zone, 1 << order);
    zone_statistics(preferred_zone, zone, gfp_flags);
    local_irq_restore(flags);
 
    VM_BUG_ON_PAGE(bad_range(zone, page), page);
    if (prep_new_page(page, order, gfp_flags))
        goto again;
    return page;
 
failed:
    local_irq_restore(flags);
    return NULL;
}

if(likely(order==0)は、アプリケーションのメモリページがパートナー管理アルゴリズムの0階である場合、メモリページのみを申請する場合は、まずコールドページからの申請を試みます.もし失敗したら、次にrmqueue_を呼び出します.bulk()は申請ページから冷熱ページ管理リストに行き、続いて冷熱ページリストから取得する.複数のページを申請すれば、__uを通過します.rmqueue()は直接にパートナー管理から申請します.
同前rmqueue()の実現:

【file:/mm/page_alloc.c】
/*
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
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);
 
        /*
         * 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;
        }
    }
 
    trace_mm_page_alloc_zone_locked(page, order, migratetype);
    return page;
}
            ：__rmqueue_smallest() __rmqueue_fallback()。

      __rmqueue_fallback()：

【file:/mm/page_alloc.c】
/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
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;
 
    /* 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);
        list_del(&page->lru);
        rmv_page_order(page);
        area->nr_free--;
        expand(zone, page, order, current_order, area, migratetype);
        return page;
    }
 
    return NULL;
}

この関数は、割り当てアルゴリズムのコア機能を実現し、まずfor()サイクルは、指定されたパートナー管理アルゴリズムチェーンorder次数から開始され、この次数のチェーンテーブルが空でない場合、直接にlist_を通過する.del()は、このチェーンから空きページを取得して、申請の必要を満たす.もしこの階のチェーンが空だったら、もっと高い階のチェーンを調べて、チェーンが空ではない一階を見つけたら、一番高い階を見つけたら、まだ空チェーン表になっていたら、申請は失敗しました.チェーンが空ではない1階を見つけたら、空きページのブロックをリストに通します.del()は、チェーンから取り除かれ、expand()によってピアを取り分け、分割された半分の空き部分を、下位の階のチェーンテーブルに連結し、申請に必要なorder階に分割するまで、最後に要求に満足したページを返す.これでページが割り当てられました.
ひいてはrmqueuefallback():

【file:/mm/page_alloc.c】
/* Remove an element from the buddy allocator from the fallback list */
static inline struct page *
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
{
    struct free_area *area;
    int current_order;
    struct page *page;
    int migratetype, new_type, 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++) {
            migratetype = fallbacks[start_migratetype][i];
 
            /* MIGRATE_RESERVE handled later if necessary */
            if (migratetype == MIGRATE_RESERVE)
                break;
 
            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);
            area->nr_free--;
 
            new_type = try_to_steal_freepages(zone, page,
                              start_migratetype,
                              migratetype);
 
            /* Remove the page from the freelists */
            list_del(&page->lru);
            rmv_page_order(page);
 
            expand(zone, page, order, current_order, area,
                   new_type);
 
            trace_mm_page_alloc_extfrag(page, order, current_order,
                start_migratetype, migratetype, new_type);
 
            return page;
        }
    }
 
    return NULL;
}

主に他の移動タイプにメモリを取得します.通常のパートナーアルゴリズムとは異なり、移行型のメモリにメモリページを申請する際には、一番高い段階から検索を開始し、主に大きなメモリからより少ない破片を避けることができます.すべての手段を試してもメモリページを取得できない場合、MIGRATE_からRESERVEリストから取得します.この部分はしばらく中に入らないで、後で詳しく分析します.
完了しました.これでパートナー管理アルゴリズムの割当部分を一時的に分析しました.