《LINUX3.0内核源代码分析》第四章：内存管理(5)

摘要：本文主要讲述linux如何处理ARM cortex A9多核处理器的内存管理部分。主要包括对伙伴系统算法流程的介绍。

法律声明：《LINUX3.0内核源代码分析》系列文章由谢宝友（）发表于http://xiebaoyou.blog.chinaunix.net，文章中的LINUX3.0源代码遵循GPL协议。除此以外，文档中的其他内容由作者保留所有版权。谢绝转载。

 

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;
        /* 计算更高阶的页面索引及页面地址 */
        combined_idx = buddy_idx & page_idx;
        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;
        struct list_head *list;

        /* 这里需要关中断，因为内存回收过程可能发送核间中断，强制每个核从每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 << order个页面，这里进行管理区空闲页面统计计数 */
        __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))
            break;

        /*
         * 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);
        else
            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)
{
    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;/* 跳转到retry_reserve,从保留的链表中分配页面 */
        }
    }

    /* 调试代码,很高兴可以飘过 */
    trace_mm_page_alloc_zone_locked(page, order, migratetype);
    return page;
}

快速流程的处理函数是__rmqueue_smallest:

 

/**
 * 遍历指定迁移类型的伙伴系统链表,从链表中移动最小数量的页面返回给调用者.这是伙伴系统的快速处理流程.
 *        zone:        在该管理区的伙伴系统中分配页面
 *        order:        要分配的页面数量阶.
 *        migratetype:    在该迁移类型的链表中获取页面
 */
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将页面的伙伴标志位清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;
    }

    return NULL;
}

辅助函数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)
{
    struct free_area * area;
    int current_order;
    struct page *page;
    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]))
                continue;

            /* 取备用链表的第一个元素 */
            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,
                                start_migratetype);

                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;
        }
    }

    return NULL;
}