Linux内核Buddy系统源码分析

作者

Buddy系统概述

Buddy系统是Linux内核中最重要的物理内存管理算法，它解决了外部碎片问题，能够高效地分配和释放连续的物理页面， 本文章中的源码基于 内核 5.15.180 版本

基本原理

  1. 二进制分割：将内存按2的幂次方大小进行分割
  2. Buddy配对：每个内存块都有一个”伙伴”块，地址相邻且大小相同
  3. 合并机制：释放时自动与空闲的buddy合并成更大的块

核心数据结构

1. free_area结构

// include/linux/mmzone.h
struct free_area {
    struct list_head free_list[MIGRATE_TYPES];  // 每种迁移类型的空闲列表
    unsigned long nr_free;                       // 空闲页面数
};

2. zone结构中的free_area数组

// include/linux/mmzone.h
struct zone {
    // ... 其他字段 ...

    /* 不同大小的空闲区域 */
    struct free_area free_area[MAX_ORDER];  // MAX_ORDER通常为11

    // ... 其他字段 ...
};

3. 页面标记

// mm/page_alloc.c
static inline void set_buddy_order(struct page *page, unsigned int order)
{
    set_page_private(page, order);
    __SetPageBuddy(page);
}

static inline bool page_is_buddy(struct page *page, struct page *buddy,
                                 unsigned int order)
{
    if (!PageBuddy(buddy))
        return false;

    if (buddy_order(buddy) != order)
        return false;

    /*
     * zone check is done late to avoid uselessly
     * calculating zone/node ids for pages that could
     * never merge.
     */
    if (page_zone_id(page) != page_zone_id(buddy))
        return false;

    VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

    return true;
}

页面分配实现

1. 主要分配函数：__rmqueue_smallest

// mm/page_alloc.c:2448
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                                int migratetype)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;

    /* 从请求的order开始查找合适大小的页面 */
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {
        area = &(zone->free_area[current_order]);
        page = get_page_from_free_area(area, migratetype);
        if (!page)
            continue;

        /* 从空闲列表中移除页面 */
        del_page_from_free_list(page, zone, current_order);

        /* 分割更大的块 */
        expand(zone, page, order, current_order, migratetype);

        /* 设置页面迁移类型 */
        set_pcppage_migratetype(page, migratetype);

        trace_mm_page_alloc_zone_locked(page, order, migratetype,
                pcp_allowed_order(order) &&
                migratetype < MIGRATE_PCPTYPES);
        return page;
    }

    return NULL;
}

2. 页面分割函数：expand

// mm/page_alloc.c:2289
static inline void expand(struct zone *zone, struct page *page,
                         int low, int high, int migratetype)
{
    unsigned long size = 1 << high;

    while (high > low) {
        high--;
        size >>= 1;
        VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);

        /*
         * 标记为guard页面（如果启用），允许在buddy释放时
         * 合并回分配器。相应的页表项不会被触及，
         * 页面在虚拟地址空间中保持不存在状态
         */
        if (set_page_guard(zone, &page[size], high, migratetype))
            continue;

        /* 将分割出的页面加入对应order的空闲列表 */
        add_to_free_list(&page[size], zone, high, migratetype);
        set_buddy_order(&page[size], high);
    }
}

3. 分配流程图解

请求order=2的页面（4个连续页面）
         ↓
检查free_area[2]是否有空闲块？
         ↓ 无
检查free_area[3]是否有空闲块？
         ↓ 有（8页块）
调用expand()分割：
  - 保留前4页给请求者
  - 后4页加入free_area[2]
         ↓
返回分配的页面

页面释放实现

1. 主要释放函数：__free_one_page

// mm/page_alloc.c:1058
static inline void __free_one_page(struct page *page,
                                  unsigned long pfn,
                                  struct zone *zone, unsigned int order,
                                  int migratetype, fpi_t fpi_flags)
{
    struct capture_control *capc = task_capc(zone);
    unsigned long buddy_pfn;
    unsigned long combined_pfn;
    unsigned int max_order;
    struct page *buddy;
    bool to_tail;

    max_order = min_t(unsigned int, MAX_ORDER - 1, pageblock_order);

    VM_BUG_ON(!zone_is_initialized(zone));
    VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

    VM_BUG_ON(migratetype == -1);
    if (likely(!is_migrate_isolate(migratetype)))
        __mod_zone_freepage_state(zone, 1 << order, migratetype);

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

continue_merging:
    while (order < max_order) {
        if (compaction_capture(capc, page, order, migratetype)) {
            __mod_zone_freepage_state(zone, -(1 << order), migratetype);
            return;
        }

        /* 计算buddy的PFN */
        buddy_pfn = __find_buddy_pfn(pfn, order);
        buddy = page + (buddy_pfn - pfn);

        /* 检查buddy是否可以合并 */
        if (!page_is_buddy(page, buddy, order))
            goto done_merging;

        /*
         * 我们的buddy是空闲的或者是CONFIG_DEBUG_PAGEALLOC guard页面，
         * 与它合并并提升一个order
         */
        if (page_is_guard(buddy))
            clear_page_guard(zone, buddy, order, migratetype);
        else
            del_page_from_free_list(buddy, zone, order);

        /* 合并页面 */
        combined_pfn = buddy_pfn & pfn;
        page = page + (combined_pfn - pfn);
        pfn = combined_pfn;
        order++;
    }

    /* 处理更高order的合并 */
    if (order < MAX_ORDER - 1) {
        /* 检查是否有隔离的pageblock */
        if (unlikely(has_isolate_pageblock(zone))) {
            int buddy_mt;

            buddy_pfn = __find_buddy_pfn(pfn, order);
            buddy = page + (buddy_pfn - pfn);
            buddy_mt = get_pageblock_migratetype(buddy);

            if (migratetype != buddy_mt
                    && (is_migrate_isolate(migratetype) ||
                        is_migrate_isolate(buddy_mt)))
                goto done_merging;
        }
        max_order = order + 1;
        goto continue_merging;
    }

done_merging:
    set_buddy_order(page, order);

    /* 决定是否加入列表尾部 */
    if (fpi_flags & FPI_TO_TAIL)
        to_tail = true;
    else if (is_shuffle_order(order))
        to_tail = shuffle_pick_tail();
    else
        to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);

    if (to_tail)
        add_to_free_list_tail(page, zone, order, migratetype);
    else
        add_to_free_list(page, zone, order, migratetype);

    /* 通知页面报告子系统 */
    if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))
        page_reporting_notify_free(order);
}

2. Buddy查找算法

// mm/internal.h:195
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
    return page_pfn ^ (1 << order);
}

这个简单的异或操作实现了buddy查找：

  • 对于order=0：buddy_pfn = pfn ^ 1（相邻页面）
  • 对于order=1：buddy_pfn = pfn ^ 2（相邻的2页块）
  • 对于order=n：buddy_pfn = pfn ^ (1 << n)

Buddy合并算法

1. 合并条件检查

static inline bool page_is_buddy(struct page *page, struct page *buddy,
                                 unsigned int order)
{
    /* buddy必须标记为PageBuddy */
    if (!PageBuddy(buddy))
        return false;

    /* buddy的order必须匹配 */
    if (buddy_order(buddy) != order)
        return false;

    /* 必须在同一个zone */
    if (page_zone_id(page) != page_zone_id(buddy))
        return false;

    /* buddy必须是空闲的 */
    VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

    return true;
}

2. 合并优化：buddy_merge_likely

// mm/page_alloc.c:1016
static inline bool
buddy_merge_likely(unsigned long pfn, unsigned long buddy_pfn,
                   struct page *page, unsigned int order)
{
    struct page *higher_page, *higher_buddy;
    unsigned long combined_pfn;

    if (order >= MAX_ORDER - 2)
        return false;

    /* 检查更高order的buddy是否也可能合并 */
    combined_pfn = buddy_pfn & pfn;
    higher_page = page + (combined_pfn - pfn);
    buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
    higher_buddy = higher_page + (buddy_pfn - combined_pfn);

    return page_is_buddy(higher_page, higher_buddy, order + 1);
}

实际应用场景

1. 内核模块分配大块内存

/* 分配连续的物理页面 */
struct page *pages;
int order = 3;  /* 分配8个连续页面 */

pages = alloc_pages(GFP_KERNEL, order);
if (pages) {
    void *vaddr = page_address(pages);
    /* 使用内存... */

    /* 释放内存 */
    __free_pages(pages, order);
}

2. DMA缓冲区分配

/* 为DMA分配连续物理内存 */
struct page *dma_pages;
dma_addr_t dma_handle;

dma_pages = alloc_pages(GFP_DMA | GFP_KERNEL, 2);  /* 4页 */
if (dma_pages) {
    dma_handle = page_to_phys(dma_pages);
    /* 配置DMA... */
}

3. 大页内存分配

/* 分配透明大页 */
struct page *hugepage;

hugepage = alloc_pages(GFP_TRANSHUGE, HPAGE_PMD_ORDER);
if (hugepage) {
    /* 设置为复合页 */
    prep_compound_page(hugepage, HPAGE_PMD_ORDER);
}

性能优化机制

1. Per-CPU页面缓存（PCP）

// mm/page_alloc.c:3689
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
                                   struct zone *zone, unsigned int order,
                                   gfp_t gfp_flags, int migratetype,
                                   unsigned int alloc_flags)
{
    struct per_cpu_pages *pcp;
    struct list_head *list;
    struct page *page;
    unsigned long flags;

    local_lock_irqsave(&pagesets.lock, flags);

    /*
     * 在分配时，减少批量释放的页面数量。
     * 参见nr_pcp_free()，其中free_factor在后续释放时增加。
     */
    pcp = this_cpu_ptr(zone->per_cpu_pageset);
    pcp->free_factor >>= 1;
    list = &pcp->lists[order_to_pindex(migratetype, order)];
    page = __rmqueue_pcplist(zone, order, migratetype, alloc_flags, pcp, list);
    local_unlock_irqrestore(&pagesets.lock, flags);

    if (page) {
        __count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
        zone_statistics(preferred_zone, zone, 1);
    }
    return page;
}

2. 批量分配优化

// mm/page_alloc.c:3015
static int rmqueue_bulk(struct zone *zone, unsigned int order,
                       unsigned long count, struct list_head *list,
                       int migratetype, unsigned int alloc_flags)
{
    int i, allocated = 0;

    spin_lock(&zone->lock);
    for (i = 0; i < count; ++i) {
        struct page *page = __rmqueue(zone, order, migratetype, alloc_flags);
        if (unlikely(page == NULL))
            break;

        if (unlikely(check_pcp_refill(page)))
            continue;

        /*
         * 通过expand()返回的分割buddy页面按物理页面顺序接收。
         * 页面被添加到调用者列表的尾部。从调用者的角度来看，
         * 在某些条件下链表按页面号排序。这对于可以从头部
         * 转发方向的IO设备很有用，因此也按物理页面顺序。
         */
        list_add_tail(&page->lru, list);
        allocated++;
        if (is_migrate_cma(get_pcppage_migratetype(page)))
            __mod_zone_page_state(zone, NR_FREE_CMA_PAGES, -(1 << order));
    }

    /*
     * 即使某些页面由于check_pcp_refill失败而泄漏，
     * 也有i个页面从buddy列表中移除，所以根据i调整NR_FREE_PAGES。
     * 不要与'allocated'混淆，后者是添加到pcp列表的页面数。
     */
    __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
    spin_unlock(&zone->lock);
    return allocated;
}

3. 迁移类型优化

// mm/page_alloc.c:2472
static int fallbacks[MIGRATE_TYPES][3] = {
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
#ifdef CONFIG_CMA
    [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

调试和监控

1. 查看Buddy系统状态

# 查看内存碎片信息
cat /proc/buddyinfo

# 查看各zone的详细信息
cat /proc/zoneinfo

# 查看页面分配统计
cat /proc/vmstat | grep pgalloc

2. 内核调试接口

// mm/page_alloc.c:9487
bool is_free_buddy_page(struct page *page)
{
    struct zone *zone = page_zone(page);
    unsigned long pfn = page_to_pfn(page);
    unsigned long flags;
    unsigned int order;

    spin_lock_irqsave(&zone->lock, flags);
    for (order = 0; order < MAX_ORDER; order++) {
        struct page *page_head = page - (pfn & ((1 << order) - 1));

        if (PageBuddy(page_head) && buddy_order(page_head) >= order)
            break;
    }
    spin_unlock_irqrestore(&zone->lock, flags);

    return order < MAX_ORDER;
}

3. 内存分配跟踪

// 启用内存分配跟踪
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc/enable
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_free/enable

# 查看跟踪结果
cat /sys/kernel/debug/tracing/trace

高级特性

1. 内存压缩支持

// mm/page_alloc.c:913
static inline struct capture_control *task_capc(struct zone *zone)
{
    struct capture_control *capc = current->capture_control;

    return unlikely(capc) &&
        !(current->flags & PF_KTHREAD) &&
        !capc->page &&
        capc->cc->zone == zone ? capc : NULL;
}

2. 页面隔离机制

// mm/page_alloc.c:3503
int __isolate_free_page(struct page *page, unsigned int order)
{
    struct zone *zone;
    unsigned long watermark;
    int mt;

    zone = page_zone(page);
    mt = get_pageblock_migratetype(page);

    if (!is_migrate_isolate(mt)) {
        /*
         * 遵守水位标记，除非是MIGRATE_MOVABLE页面块或
         * CMA页面块，因为隔离的目的是为了迁移。
         */
        watermark = low_wmark_pages(zone);

        if (!zone_watermark_ok(zone, 0, watermark, 0, ALLOC_CMA))
            return 0;

        __mod_zone_freepage_state(zone, -(1UL << order), mt);
    }

    /* 从空闲列表中移除页面 */
    del_page_from_free_list(page, zone, order);

    /*
     * 设置迁移类型为MIGRATE_ISOLATE，以防止
     * 页面被分配出去。
     */
    if (order >= pageblock_order - 1) {
        struct page *endpage = page + (1 << order) - 1;
        for (; page < endpage; page += pageblock_nr_pages) {
            int mt = get_pageblock_migratetype(page);
            if (!is_migrate_isolate(mt) && !is_migrate_cma(mt)
                && !is_migrate_highatomic(mt))
                set_pageblock_migratetype(page, MIGRATE_ISOLATE);
        }
    }

    return 1UL << order;
}

总结

Buddy系统是Linux内核内存管理的核心，通过以下机制实现高效的内存分配：

关键优势

  1. 消除外部碎片：通过2的幂次方分配和自动合并
  2. 快速分配：O(log n)时间复杂度
  3. 自动合并：释放时自动与buddy合并
  4. 多种优化：PCP缓存、批量操作、迁移类型等

实现要点

  1. 数据结构简洁：free_area数组管理不同大小的空闲块
  2. 算法高效：异或运算快速找到buddy
  3. 内存对齐：确保buddy关系的正确性
  4. 并发安全：适当的锁机制保护数据结构

应用场景

  1. 内核内存分配：kmalloc、vmalloc的底层支持
  2. 用户空间内存：页面错误处理时的页面分配
  3. 设备驱动：DMA缓冲区等连续内存需求
  4. 文件系统：页面缓存的物理页面管理
本文版权归原作者zhaofujian所有，采用 CC BY-NC-ND 4.0 协议进行许可，转载请注明出处。

发表评论