图解|Linux内存碎片整理

Linux内核那些事

共 7795字,需浏览 16分钟

 ·

2022-12-05 07:40

我们知道物理内存是以页为单位进行管理的,每个内存页大小默认是4K(大页除外)。申请物理内存时,一般都是按顺序分配的,但释放内存的行为是随机的。随着系统运行时间变长后,将会出现以下情况:

7628e0f6a37caa650317a6b160d067a6.webp

如上图所示,当用户需要申请地址连续的 3 个内存页时,虽然系统中空闲的内存页数量足够,但由于空闲的内存页相对分散,从而导致分配失败。这些地址不连续的内存页被称为:内存碎片

要解决这个问题也比较简单,只需要把空闲的内存块移动到一起即可。如下图所示:

384a53b5b15981d58994c9bbc2178952.webp

网络上有句很有名的话:理想很美好,现实很骨感

内存整理也是这样,看起来很简单,但实现起来就不那么简单了。因为在内存整理后,需要修正进程的虚拟内存与物理内存之间的映射关系。如下图所示:

477610d1aa0a45a3a16ff7929679a6fc.webp

但由于 Linux 内核有个名为 内存页反向映射 的功能,所以内存整理就变得简单起来。

接下来,我们将会分析内存碎片整理的原理与实现。

内存碎片整理原理

内存碎片整理的原理比较简单:在内存碎片整理开始前,会在内存区的头和尾各设置一个指针,头指针从头向尾扫描可移动的页,而尾指针从尾向头扫描空闲的页,当他们相遇时终止整理。下面说说内存随便整理的过程(原理参考了内核文档):

  1. 初始时内存状态:

0199c93ab62231314e301ef30fdc0bb3.webp

在上图中,白色块表示空闲的内存页,而红色块表示已分配出去的内存页。在初始状态时,内存中存在多个碎片。如果此时要申请 3 个地址连续的内存页,那么将会申请失败。

  1. 内存碎片整理扫描开始:

    5bfb264cc81f787b716cf49b08b0eb16.webp

头部指针从头扫描可移动页,而尾部指针从从尾扫描空闲页。在整理时,将可移动页的内容复制到空闲页中。复制完成后,将可移动内存页释放即可。

  1. 最后结果:

3be5852aeebafbdfc91abfbb240bc2b0.webp

经过内存碎片整理后,如果现在要申请 3 个地址连续的内存页,就能申请成功了。

内存碎片整理实现

接下来,我们将会分析内存碎片整理的实现过程。

注:本文使用的是 Linux-2.6.36 版本的内存

1. 内存碎片整理时机

当要申请多个地址联系的内存页时,如果申请失败,将会进行内存碎片整理。其调用链如下:

    alloc_pages_node()
└→ __alloc_pages()
   └→ __alloc_pages_nodemask()
      └→ __alloc_pages_slowpath()
         └→ __alloc_pages_direct_compact()

当调用 alloc_pages_node() 函数申请多个地址连续的内存页失败时,将会触发调用 __alloc_pages_direct_compact() 函数来进行内存碎片整理。我们来看看 __alloc_pages_direct_compact() 函数的实现:

    static struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask
                             unsigned int order
                             struct zonelist *zonelist
                             enum zone_type high_zoneidx
                             nodemask_t *nodemask
                             int alloc_flags,
                             struct zone *preferred_zone,
                             int migratetype
                             unsigned long *did_some_progress)
{

    struct page *page;

    // 1. 如果申请一个内存页,那么就没有整理碎片的必要(这说明是内存不足,而不是内存碎片导致)
    if (!order || compaction_deferred(preferred_zone))
        return NULL;

    // 2. 开始进行内存碎片整理
    *did_some_progress = try_to_compact_pages(zonelist, order, gfp_mask, nodemask);

    if (*did_some_progress != COMPACT_SKIPPED) {
        ...
        // 3. 整理完内存碎片后,继续尝试申请内存块
        page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist, 
                                      high_zoneidx, alloc_flags, preferred_zone, 
                                      migratetype);
        if (page) {
            ...
            return page;
        }
        ...
    }

    return NULL;
}

__alloc_pages_direct_compact() 函数是内存碎片整理的入口,其主要完成 3 个步骤:

  • 先判断申请的内存块是否只有一个内存页,如果是,那么就没有整理碎片的必要(这说明是内存不足,而不是内存碎片导致)。
  • 如果需要进行内存碎片整理,那么调用 try_to_compact_pages() 函数进行内存碎片整理。
  • 整理完内存碎片后,调用 get_page_from_freelist() 函数继续尝试申请内存块。

2. 内存碎片整理过程

由于内存碎片整理的具体实现在 try_to_compact_pages() 函数中进行,所以我们继续来看看 try_to_compact_pages() 函数的实现:

    unsigned long
try_to_compact_pages(struct zonelist *zonelist, int order, gfp_t gfp_mask,
                     nodemask_t *nodemask)

{
    ...
    // 1. 遍历所有内存区(由于内核会把物理内存分成多个内存区进行管理)
    for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx, nodemask) {
        ...
        // 2. 对内存区进行内存碎片整理
        status = compact_zone_order(zone, order, gfp_mask);
        ...
    }

    return rc;
}

可以看出,try_to_compact_pages() 函数最终会调用 compact_zone_order() 函数来进行内存碎片整理。我们只能进行来分析 compact_zone_order() 函数:

    static unsigned long
compact_zone_order(struct zone *zone, int order, gfp_t gfp_mask)
{
    struct compact_control cc = {
        .nr_freepages = 0,
        .nr_migratepages = 0,
        .order = order,
        .migratetype = allocflags_to_migratetype(gfp_mask),
        .zone = zone,
    };
    INIT_LIST_HEAD(&cc.freepages);
    INIT_LIST_HEAD(&cc.migratepages);

    return compact_zone(zone, &cc);
}

到这里,我们还没有看到内存碎片整理的具体实现(调用链可真深啊 ^_^!),compact_zone_order() 函数也是构造了一些参数,然后继续调用 compact_zone() 来进行内存碎片整理:

    static int compact_zone(struct zone *zone, struct compact_control *cc)
{
    ...
    while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
        ...
        // 1. 收集可移动的内存页列表
        if (!isolate_migratepages(zone, cc))
            continue;
        ...
        // 2. 将可移动的内存页列表迁移到空闲列表中
        migrate_pages(&cc->migratepages, compaction_alloc, (unsigned long)cc, 0);
        ...
    }
    ...
    return ret;
}

在 compact_zone() 函数里,我们终于看到内存碎片整理的逻辑了。compact_zone() 函数主要完成 2 个步骤:

  • 调用 isolate_migratepages() 函数收集可移动的内存页列表。
  • 调用 migrate_pages() 函数将可移动的内存页列表迁移到空闲列表中。

这两个函数非常重要,我们分别来分析它们是怎么实现的。

isolate_migratepages() 函数

isolate_migratepages() 函数用于收集可移动的内存页列表,我们来看看其实现:

    static unsigned long
isolate_migratepages(struct zone *zone, struct compact_control *cc)
{
    unsigned long low_pfn, end_pfn;
    struct list_head *migratelist = &cc->migratepages;
    ...

    // 1. 扫描内存区所有的内存页
    for (; low_pfn < end_pfn; low_pfn++) {
        struct page *page;
        ...

        // 2. 通过内存页的编号获取内存页对象
        page = pfn_to_page(low_pfn);
       ...

        // 3. 判断内存页是否可移动内存页,如果不是可移动内存页,那么就跳过
        if (__isolate_lru_page(page, ISOLATE_BOTH, 0) != 0)
            continue;

        // 4. 将内存页从 LRU 队列中删除
        del_page_from_lru_list(zone, page, page_lru(page));

        // 5. 添加到可移动内存页列表中
        list_add(&page->lru, migratelist); 
        ...
        cc->nr_migratepages++;
        ...
    }
    ...
    return cc->nr_migratepages;
}

isolate_migratepages() 函数主要完成 5 个步骤,分别是:

  • 扫描内存区所有的内存页(与内存碎片整理原理一致)。
  • 通过内存页的编号获取内存页对象。
  • 判断内存页是否可移动内存页,如果不是可移动内存页,那么就跳过。
  • 将内存页从 LRU 队列中删除,这样可避免被其他进程回收这个内存页。
  • 添加到可移动内存页列表中。

当完成这 5 个步骤后,内核就收集到可移动的内存页列表。

migrate_pages() 函数

migrate_pages() 函数负责将可移动的内存页列表迁移到空闲列表中,我们来分析一下其实现过程:

    int migrate_pages(struct list_head *from, new_page_t get_new_page,
                  unsigned long privateint offlining)

{
    ...

    for (pass = 0; pass < 10 && retry; pass++) {
        retry = 0;

        // 1. 遍历可移动内存页列表
        list_for_each_entry_safe(page, page2, from, lru) {
            ...
            // 2. 将可移动内存页迁移到空闲内存页中
            rc = unmap_and_move(get_new_page, private, page, pass > 2, offlining);
            switch(rc) {
            case -ENOMEM:
                goto out;
            case -EAGAIN:
                retry++;
                break;
            case 0:
                break;
            default:
                nr_failed++;
                break;
            }
        }
    }
    ...
    return nr_failed + retry;
}

migrate_pages() 函数的逻辑很简单,主要完成 2 个步骤:

  • 遍历可移动内存页列表,这个列表就是通过 isolate_migratepages() 函数收集的可移动内存页列表。
  • 调用 unmap_and_move() 函数将可移动内存页迁移到空闲内存页中。

可以看出,具体的内存迁移过程在 unmap_and_move() 函数中实现。我们来看看 unmap_and_move() 函数的实现:

    static int
unmap_and_move(new_page_t get_new_page, unsigned long private,
               struct page *page, int force, int offlining)

{
    ...
    // 1. 从内存区中找到一个空闲的内存页
    struct page *newpage = get_new_page(pageprivate, &result);
    ...

    // 2. 解开所有使用了当前可移动内存页的进程的虚拟内存映射(涉及到内存页反向映射)
    try_to_unmap(page, TTU_MIGRATION|TTU_IGNORE_MLOCK|TTU_IGNORE_ACCESS);

skip_unmap:
    // 3. 将可移动内存页的数据复制到空闲内存页中
    if (!page_mapped(page))
        rc = move_to_new_page(newpage, page, remap_swapcache);
    ...
    return rc;
}

由于 unmap_and_move() 函数的实现比较复杂,所以我们对其进行了简化。可以看出,unmap_and_move() 函数主要完成 3 个工作:

  • 从内存区中找到一个空闲的内存页。根据内存碎片整理算法,会从内存区最后开始扫描,找到合适的空闲内存页。
  • 由于将可移动内存页迁移到空闲内存页后,进程的虚拟内存映射将会发生变化。所以,这里要调用 try_to_unmap() 函数来解开所有使用了当前可移动内存页的映射。
  • 调用 move_to_new_page() 函数将可移动内存页的数据复制到空闲内存页中。在 move_to_new_page() 函数中,还会重新建立进程的虚拟内存映射,这样使用了当前可移动内存页的进程就能够正常运行。

至此,内存碎片整理的过程已经分析完毕。

不过细心的读者可能发现,在文中并没有分析重新构建虚拟内存映射的过程。是的,因为重新构建虚拟内存映射要涉及到 内存页反向映射 的知识点,后续的文章会介绍这个知识点,所以这里就不作详细分析了。

总结

从上面的分析可知,内存碎片整理 是为了解决:在申请多个地址连续的内存页时,空闲内存页数量充足,但还是分配失败的情况。

但由于内存碎片整理需要消耗大量的 CPU 时间,所以我们在申请内存时,可以通过指定 __GFP_WAIT 标志位(不等待)来避免内存碎片整理过程。



浏览 43
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报