深入解析 Linux 内存管理：三大分配器原理

深入解析 Linux 内存管理：三大分配器原理

Linux 内存管理是指操作系统对于计算机系统中的内存资源进行有效利用和管理的过程。它包括了内存分配、页面置换、内存映射等方面。Linux 内存管理的核心在于三大分配器：引导内存分配器（Bootmem/Memblock）、伙伴分配器（Buddy Allocator）和 Slab 分配器。

一、引导内存分配器

Linux 系统中使用伙伴系统对物理页面进行分配管理，但是伙伴分配系统需要内核完成初始化以及建立相关内核数据结构后才能够正常工作。因此，在内核初始化相关数据结构时需要另一种内存分配器。早期 Linux 没有较为完善的引导内存分配器，随着硬件的发展和日趋复杂，处理不同体系的内存分配代码也渐渐复杂起来，随之就需要引导内存分配器来初始化系统主要内存分配器的数据结构以确保其正常工作。

在内核 2.3.23 版本中 bootmem 引导内存分配器补丁被加入，使用位图来表示页面使用状况。然后在内核 2.3.48 版本时，Linux 内核移植到 IA64 时正式使用 bootmem 作为引导内存分配器。随着时间的流逝，内存检测已经从简单地向 BIOS 询问扩展内存块的大小演变为处理复杂的表、块、库和群集。这时开始使用 memblock 作为引导内存分配器。

在 bootmem 向 memblock 过渡时，出现 nobootmem 作为兼容层，提供与 bootmem 类似 API。在内核版本 4.17 时，在 Linux 所支持的 24 种架构中，只有 5 种仍在使用 bootmem 作为唯一的早期内存分配器，14 中将 memblock 与 nobootmem 一起使用，其余同时使用 memblock 和 bootmem 作为引导内存分配器。

1.1 引导内存分配器 bootmem

首先查看 bootmem_data 数据结构，表示每个节点物理内存以及其页面使用情况。

typedef struct bootmem_data {
    unsigned long node_min_pfn;
    unsigned long node_low_pfn;
    void *node_bootmem_map;
    unsigned long last_end_off;
    unsigned long hint_idx;
    struct list_head list;
} bootmem_data_t;

• node_min_pfn 和 node_low_pfn：表示该节点内存物理页面范围：node_min_pfn 为起始页面，node_low_pfn 则为结束页面；
• node_bootmem_map：指向位图，每位表示内存页面使用情况，当页面可以被使用时，所对应的位图设为 0，相反则设为 1；
• last_end_off：表示上次所分配内存的物理地址相对 bootmem 起始页面偏移 (以字节计算)；
• hint_idx：记录上次设置位图的索引；
• list：加入 bootmem_data 全局链表 bdata_list；除了全局链表外，还存在 bootmem_node_data 所指向的 bootmem_data 全局数组，索引为内存对应节点号。

(1) 初始化 bootmem_data

static unsigned long __init init_bootmem_core(bootmem_data_t *bdata,
    unsigned long mapstart, unsigned long start, unsigned long end)
{
    unsigned long mapsize;

    mminit_validate_memmodel_limits(&start, &end);
    bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
    bdata->node_min_pfn = start;
    bdata->node_low_pfn = end;
    link_bootmem(bdata);

    /*
     * Initially all pages are reserved - setup_arch() has to
     * register free RAM areas explicitly.
     */
    mapsize = bootmap_bytes(end - start);
    memset(bdata->node_bootmem_map, 0xff, mapsize);

    bdebug("nid=%td start=%lx map=%lx end=%lx mapsize=%lx\n",
        bdata - bootmem_node_data, start, mapstart, end, mapsize);

    return mapsize;
}

首先调用 mminit_validate_memmodel_limits() 函数检查指定范围物理页面是否有效，然后初始化 bootmem_data 结构，其中 mapstart 指向所分配位图页面。link_bootmem() 函数是将 bootmem_data 加入 bdata_list 链表中。最后将所有位图设为 1，即页面目前不可用。

(2) 释放 bootmem 所保留的页面

static void __init __free(bootmem_data_t *bdata,
            unsigned long sidx, unsigned long eidx)
{
    unsigned long idx;

    bdebug("nid=%td start=%lx end=%lx\n", bdata - bootmem_node_data,
        sidx + bdata->node_min_pfn,
        eidx + bdata->node_min_pfn);

    if (WARN_ON(bdata->node_bootmem_map == NULL))
        return;

    if (bdata->hint_idx > sidx)
        bdata->hint_idx = sidx;

    for (idx = sidx; idx < eidx; idx++)
        if (!test_and_clear_bit(idx, bdata->node_bootmem_map))
            BUG();
}

该函数中 sidx 表示所释放起始页面偏移，eidx 表示结束页面偏移，循环遍历相应位图将其设为 0，则该页面可用。

(3) 保留 bootmem 中页面

static int __init __reserve(bootmem_data_t *bdata, unsigned long sidx,
            unsigned long eidx, int flags)
{
    unsigned long idx;
    int exclusive = flags & BOOTMEM_EXCLUSIVE;

    bdebug("nid=%td start=%lx end=%lx flags=%x\n",
        bdata - bootmem_node_data,
        sidx + bdata->node_min_pfn,
        eidx + bdata->node_min_pfn,
        flags);

    if (WARN_ON(bdata->node_bootmem_map == NULL))
        return 0;

    for (idx = sidx; idx < eidx; idx++)
        if (test_and_set_bit(idx, bdata->node_bootmem_map)) {
            if (exclusive) {
                __free(bdata, sidx, idx);
                return -EBUSY;
            }
            bdebug("silent double reserve of PFN %lx\n",
                idx + bdata->node_min_pfn);
        }
    return 0;
}

该函数 sidx 和 eidx 表示锁保留页面的范围，如果 flags 设置 BOOTMEM_EXCLUSIVE 标志位则表示将指定范围内页面从 bootmem 中释放。

(4) 从 bootmem 中分配内存

static void * __init alloc_bootmem_bdata(struct bootmem_data *bdata,
                    unsigned long size, unsigned long align,
                    unsigned long goal, unsigned long limit)
{
    unsigned long fallback = 0;
    unsigned long min, max, start, sidx, midx, step;

    bdebug("nid=%td size=%lx [%lu pages] align=%lx goal=%lx limit=%lx\n",
        bdata - bootmem_node_data, size, PAGE_ALIGN(size) >> PAGE_SHIFT,
        align, goal, limit);

    BUG_ON(!size);
    BUG_ON(align & (align - 1));
    BUG_ON(limit && goal + size > limit);

    if (!bdata->node_bootmem_map)
        return NULL;

    min = bdata->node_min_pfn;
    max = bdata->node_low_pfn;

    goal >>= PAGE_SHIFT;
    limit >>= PAGE_SHIFT;

    if (limit && max > limit)
        max = limit;
    if (max <= min)
        return NULL;

    step = max(align >> PAGE_SHIFT, 1UL);

    if (goal && min < goal && goal < max)
        start = ALIGN(goal, step);
    else
        start = ALIGN(min, step);

    sidx = start - bdata->node_min_pfn;
    midx = max - bdata->node_min_pfn;

    if (bdata->hint_idx > sidx) {
        /*
         * Handle the valid case of sidx being zero and still
         * catch the fallback below.
         */
        fallback = sidx + 1;
        sidx = align_idx(bdata, bdata->hint_idx, step);
    }

    while (1) {
        int merge;
        void *region;
        unsigned long eidx, i, start_off, end_off;
find_block:
        sidx = find_next_zero_bit(bdata->node_bootmem_map, midx, sidx);
        sidx = align_idx(bdata, sidx, step);
        eidx = sidx + PFN_UP(size);

        if (sidx >= midx || eidx > midx)
            break;

        for (i = sidx; i < eidx; i++)
            if (test_bit(i, bdata->node_bootmem_map)) {
                sidx = align_idx(bdata, i, step);
                if (sidx == i)
                    sidx += step;
                goto find_block;
            }

        if (bdata->last_end_off & (PAGE_SIZE - 1) &&
                PFN_DOWN(bdata->last_end_off) + 1 == sidx)
            start_off = align_off(bdata, bdata->last_end_off, align);
        else
            start_off = PFN_PHYS(sidx);

        merge = PFN_DOWN(start_off) < sidx;
        end_off = start_off + size;

        bdata->last_end_off = end_off;
        bdata->hint_idx = PFN_UP(end_off);

        /*
         * Reserve the area now:
         */
        if (__reserve(bdata, PFN_DOWN(start_off) + merge,
                PFN_UP(end_off), BOOTMEM_EXCLUSIVE))
            BUG();

        region = phys_to_virt(PFN_PHYS(bdata->node_min_pfn) +
                start_off);
        memset(region, 0, size);
        /*
         * The min_count is set to 0 so that bootmem allocated blocks
         * are never reported as leaks.
         */
        kmemleak_alloc(region, size, 0, 0);
        return region;
    }

    if (fallback) {
        sidx = align_idx(bdata, fallback - 1, step);
        fallback = 0;
        goto find_block;
    }
}

首先获取 bootmem 位图在 sidx 和 eidx 范围数个为 0 的索引，然后在进行对齐获取起始索引并重新计算结束索引，验证是否超出 bootmem 所拥有页面范围，超出则退出循环分配失败。否则进入 for 循环在 sidx 和 eidx 遍历查看是否存在页面被 bootmem 保留，如果存在则以此索引为新 sidx 进行设置，重新遍历，相反则继续进行分配。根据 bootmem 上次分配内存的偏移设置所分配内存起始物理地址以及结束地址，最后设置这些页面的位图为 1，即保留页面。

(5) 释放 bootmem 中页面

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
{
    struct page *page;
    unsigned long *map, start, end, pages, cur, count = 0;

    if (!bdata->node_bootmem_map)
        return 0;

    map = bdata->node_bootmem_map;
    start = bdata->node_min_pfn;
    end = bdata->node_low_pfn;

    bdebug("nid=%td start=%lx end=%lx\n",
        bdata - bootmem_node_data, start, end);

    while (start < end) {
        unsigned long idx, vec;
        unsigned shift;

        idx = start - bdata->node_min_pfn;
        shift = idx & (BITS_PER_LONG - 1);
        /*
         * vec holds at most BITS_PER_LONG map bits,
         * bit 0 corresponds to start.
         */
        vec = ~map[idx / BITS_PER_LONG];

        if (shift) {
            vec >>= shift;
            if (end - start >= BITS_PER_LONG)
                vec |= ~map[idx / BITS_PER_LONG + 1] <<
                    (BITS_PER_LONG - shift);
        }
        /*
         * If we have a properly aligned and fully unreserved
         * BITS_PER_LONG block of pages in front of us, free
         * it in one go.
         */
        if (IS_ALIGNED(start, BITS_PER_LONG) && vec == ~0UL) {
            int order = ilog2(BITS_PER_LONG);

            __free_pages_bootmem(pfn_to_page(start), start, order);
            count += BITS_PER_LONG;
            start += BITS_PER_LONG;
        } else {
            cur = start;

            start = ALIGN(start + 1, BITS_PER_LONG);
            while (vec && cur != start) {
                if (vec & 1) {
                    page = pfn_to_page(cur);
                    __free_pages_bootmem(page, cur, 0);
                    count++;
                }
                vec >>= 1;
                ++cur;
            }
        }
    }
}

循环遍历位图释放 bootmem 未进行保留的页面，即相应位图设为 0 的页面。

1.2 引导内存分配器 memblock

随着硬件的发展以及复杂化，内存检测已经从简单地向 BIOS 询问扩展内存块的大小演变为处理复杂的表、块、库和群集。在 x86 架构上，内核启动初期首先使用 early_res 机制接替 BIOS e820 的工作，然后再交给架构独立的 bootmem 分配器，最后转由伙伴分配系统进行页面管理。然后有人认为可以去掉 bootmem 以此简化该过程并提交 patch，最终人们提议使用 PowerPC, SuperH 和 SPARC 架构上的 LMB 内存分配器作为系统启动初期的内存分配器。

内核数据结构

struct memblock_type {
    unsigned long cnt;    /* number of regions */
    unsigned long max;    /* size of the allocated array */
    phys_addr_t total_size;    /* size of all regions */
    struct memblock_region *regions;
    char *name;
};

memblock 数据结构是 LMB 内存分配器核心；

• bottom_up：表示内存分配方向；
• current_limit：表示 memblock 所管理页面最大物理地址；
• memory：表示 memblock 所管理全部内存；
• reserved：表示已经分配出去的内存；
• phymem：表示进行物理地址映射的内存；

struct memblock_region {
    phys_addr_t base;
    phys_addr_t size;
    unsigned long flags;
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
    int nid;
#endif
};

• base：表示 memblock_region 所具有内存起始物理地址；
• size：表示 memblock_region 所具有内存大小；
• flags：标志位；
• nid：表示 memblock_region 所具有内存的节点号；

(1) 获取 memblock_region

void __init_memblock __next_mem_range(u64 *idx, int nid, ulong flags,
                      struct memblock_type *type_a,
                      struct memblock_type *type_b,
                      phys_addr_t *out_start,
                      phys_addr_t *out_end, int *out_nid)
{
    int idx_a = *idx & 0xffffffff;
    int idx_b = *idx >> 32;

    if (WARN_ONCE(nid == MAX_NUMNODES,
    "Usage of MAX_NUMNODES is deprecated. Use NUMA_NO_NODE instead\n"))
        nid = NUMA_NO_NODE;

    for (; idx_a < type_a->cnt; idx_a++) {
        struct memblock_region *m = &type_a->regions[idx_a];

        phys_addr_t m_start = m->base;
        phys_addr_t m_end = m->base + m->size;
        int        m_nid = memblock_get_region_node(m);

        /* only memory regions are associated with nodes, check it */
        if (nid != NUMA_NO_NODE && nid != m_nid)
            continue;

        /* skip hotpluggable memory regions if needed */
        if (movable_node_is_enabled() && memblock_is_hotpluggable(m))
            continue;

        /* if we want mirror memory skip non-mirror memory regions */
        if ((flags & MEMBLOCK_MIRROR) && !memblock_is_mirror(m))
            continue;

        /* skip nomap memory unless we were asked for it explicitly */
        if (!(flags & MEMBLOCK_NOMAP) && memblock_is_nomap(m))
            continue;

        if (!type_b) {
            if (out_start)
                *out_start = m_start;
            if (out_end)
                *out_end = m_end;
            if (out_nid)
                *out_nid = m_nid;
            idx_a++;
            *idx = (u32)idx_a | (u64)idx_b << 32;
            return;
        }

        /* scan areas before each reservation */
        for (; idx_b < type_b->cnt + 1; idx_b++) {
            struct memblock_region *r;
            phys_addr_t r_start;
            phys_addr_t r_end;

            r = &type_b->regions[idx_b];
            r_start = idx_b ? r[-1].base + r[-1].size : 0;
            r_end = idx_b < type_b->cnt ?
                r->base : ULLONG_MAX;

            /*
             * if idx_b advanced past idx_a,
             * break out to advance idx_a
             */
            if (r_start >= m_end)
                break;
            /* if the two regions intersect, we're done */
            if (m_start < r_end) {
                if (out_start)
                    *out_start =
                        max(m_start, r_start);
                if (out_end)
                    *out_end = min(m_end, r_end);
                if (out_nid)
                    *out_nid = m_nid;
                /*
                 * The region which ends first is
                 * advanced for the next iteration.
                 */
                if (m_end <= r_end)
                    idx_a++;
                else
                    idx_b++;
                *idx = (u32)idx_a | (u64)idx_b << 32;
                return;
            }
        }
    }

    /* signal end of iteration */
    *idx = ULLONG_MAX;
}

该函数 idx 为 type_a 和 type_b 中起始索引组合，nid 为寻找内存区域所在节点号，flags 为标志位，out_start、out_end 和 out_nid 为输出符合调节的内存区域物理地址范围及所在节点号，type_a 为寻找内存区域必须处于其拥有内存范围内，type_b 为寻找目标内存不在其拥有内存范围内。函数首先获取 type_a 和 type_b 中 region 数组起始索引，然后循环遍历寻找属于 type_a 但不属于 type_b 的首个内存区域。

(2) 寻找空闲内存区域

phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t size,
                    phys_addr_t align, phys_addr_t start,
                    phys_addr_t end, int nid, ulong flags)
{
    phys_addr_t kernel_end, ret;

    /* pump up @end */
    if (end == MEMBLOCK_ALLOC_ACCESSIBLE)
        end = memblock.current_limit;

    /* avoid allocating the first page */
    start = max_t(phys_addr_t, start, PAGE_SIZE);
    end = max(start, end);
    kernel_end = __pa_symbol(_end);

    /*
     * try bottom-up allocation only when bottom-up mode
     * is set and @end is above the kernel image.
     */
    if (memblock_bottom_up() && end > kernel_end) {
        phys_addr_t bottom_up_start;

        /* make sure we will allocate above the kernel */
        bottom_up_start = max(start, kernel_end);

        /* ok, try bottom-up allocation first */
        ret = __memblock_find_range_bottom_up(bottom_up_start, end,
                              size, align, nid, flags);
        if (ret)
            return ret;

        /*
         * we always limit bottom-up allocation above the kernel,
         * but top-down allocation doesn't have the limit, so
         * retrying top-down allocation may succeed when bottom-up
         * allocation failed.
         *
         * bottom-up allocation is expected to be fail very rarely,
         * so we use WARN_ONCE() here to see the stack trace if
         * fail happens.
         */
        WARN_ONCE(1, "memblock: bottom-up allocation failed, memory hotunplug may be affected\n");
    }

    return __memblock_find_range_top_down(start, end, size, align, nid, flags);
}

该函数中 size 表示寻找物理内存大小 (字节)，align 为物理内存对齐，start 表示所寻找内存区域最小物理地址，end 为最大物理地址，nid 为节点号，flags 为标志位。检查 end 是否等于 MEMBLOCK_ALLOC_ACCESSIBLE，相等则设置 end 为 memblock.current_limit，重新计算所查询物理地址范围。

检查 memblock.bottom_up 和 end>kernel_end 是否均为真，即内存查询是否为从低地址项高地址且 end 高于内核最大虚拟地址所对应的物理地址，重新获取查询范围并进行查询。

最后进行从高地址到低地址进行查询。

(3) 向 memblock_type 添加 memblock_region

int __init_memblock memblock_add_range(struct memblock_type *type,
                phys_addr_t base, phys_addr_t size,
                int nid, unsigned long flags)
{
    bool insert = false;
    phys_addr_t obase = base;
    phys_addr_t end = base + memblock_cap_size(base, &size);
    int idx, nr_new;
    struct memblock_region *rgn;

    if (!size)
        return 0;

    /* special case for empty array */
    if (type->regions[0].size == 0) {
        WARN_ON(type->cnt != 1 || type->total_size);
        type->regions[0].base = base;
        type->regions[0].size = size;
        type->regions[0].flags = flags;
        memblock_set_region_node(&type->regions[0], nid);
        type->total_size = size;
        return 0;
    }

repeat:
    /*
     * The following is executed twice.  Once with %false @insert and
     * then with %true.  The first counts the number of regions needed
     * to accommodate the new area.  The second actually inserts them.
     */
    base = obase;
    nr_new = 0;

    for_each_memblock_type(idx, type, rgn) {
        phys_addr_t rbase = rgn->base;
        phys_addr_t rend = rbase + rgn->size;

        if (rbase >= end)
            break;
        if (rend <= base)
            continue;
        /*
         * @rgn overlaps.  If it separates the lower part of new
         * area, insert that portion.
         */
        if (rbase > base) {
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
            WARN_ON(nid != memblock_get_region_node(rgn));
#endif
            WARN_ON(flags != rgn->flags);
            nr_new++;
            if (insert)
                memblock_insert_region(type, idx++, base,
                               rbase - base, nid,
                               flags);
        }
        /* area below @rend is dealt with, forget about it */
        base = min(rend, end);
    }

    /* insert the remaining portion */
    if (base < end) {
        nr_new++;
        if (insert)
            memblock_insert_region(type, idx, base, end - base,
                           nid, flags);
    }

    if (!nr_new)
        return 0;

    /*
     * If this was the first round, resize array and repeat for actual
     * insertions; otherwise, merge and return.
     */
    if (!insert) {
        while (type->cnt + nr_new > type->max)
            if (memblock_double_array(type, obase, size) < 0)
                return -ENOMEM;
        insert = true;
        goto repeat;
    } else {
        memblock_merge_regions(type);
        return 0;
    }
}

该函数 base 为添加内存起始物理地址，size 为添加的物理内存大小 (字节数目)，nid 为添加内存所在节点号，flags 为添加 region 标志位。首先计算获取所添加物理内存所在物理地址范围，然后检查 memblock_type 中 region 数组是否为空。如果为空则初始化 region 数组首个元素并返回。

遍历 memblock_type 所具有的 region 数组，获取数组中基地址处于 base-end 之间的元素，如果寻找到并且 insert 为真则将处于 base-rbase 之间的内存插入数组中，nr_new 表示新插入的元素会增加 1，继续遍历。

经过遍历后，检查内存区域是否完全插入，如果有部分区域并未插入则检查 insert 是否为真，为真则将剩余部分也插入 region 数组中，否则继续运行。

检查 insert 是否为真，若为真则将 memblock_type 中的 region 数组进行合并，否则检查 nr_new+type->cnt 是否超出 type 中 region 数组最大数，超出则对 type 中 region 数组进行扩充，设置 insert 为真继续重复以上操作。

(4) 扩充 memblock_type 中 region 数组空间

static int __init_memblock memblock_double_array(struct memblock_type *type,
                        phys_addr_t new_area_start,
                        phys_addr_t new_area_size)
{
    struct memblock_region *new_array, *old_array;
    phys_addr_t old_alloc_size, new_alloc_size;
    phys_addr_t old_size, new_size, addr;
    int use_slab = slab_is_available();
    int *in_slab;

    /* We don't allow resizing until we know about the reserved regions
     * of memory that aren't suitable for allocation
     */
    if (!memblock_can_resize)
        return -1;

    /* Calculate new doubled size */
    old_size = type->max * sizeof(struct memblock_region);
    new_size = old_size << 1;
    /*
     * We need to allocated new one align to PAGE_SIZE,
     *   so we can free them completely later.
     */
    old_alloc_size = PAGE_ALIGN(old_size);
    new_alloc_size = PAGE_ALIGN(new_size);

    /* Retrieve the slab flag */
    if (type == &memblock.memory)
        in_slab = &memblock_memory_in_slab;
    else
        in_slab = &memblock_reserved_in_slab;

    if (use_slab) {
        new_array = kmalloc(new_size, GFP_KERNEL);
        addr = new_array ? __pa(new_array) : 0;
    } else {
        /* only exclude range when trying to double reserved.regions */
        if (type != &memblock.reserved)
            new_area_start = new_area_size = 0;

        addr = memblock_find_in_range(new_area_start + new_area_size,
                        memblock.current_limit,
                        new_alloc_size, PAGE_SIZE);
        if (!addr && new_area_size)
            addr = memblock_find_in_range(0,
                min(new_area_start, memblock.current_limit),
                new_alloc_size, PAGE_SIZE);

        new_array = addr ? __va(addr) : NULL;
    }
    if (!addr) {
        pr_err("memblock: Failed to double %s array from %ld to %ld entries !\n",
               type->name, type->max, type->max * 2);
        return -1;
    }

    memcpy(new_array, type->regions, old_size);
    memset(new_array + type->max, 0, old_size);
    old_array = type->regions;
    type->regions = new_array;
    type->max <<= 1;

    /* Free old array. We needn't free it if the array is the static one */
    if (*in_slab)
        kfree(old_array);
    else if (old_array != memblock_memory_init_regions &&
         old_array != memblock_reserved_init_regions)
        memblock_free(__pa(old_array), old_alloc_size);

    /*
     * Reserve the new array if that comes from the memblock.  Otherwise, we
     * needn't do it
     */
    if (!use_slab)
        BUG_ON(memblock_reserve(addr, new_alloc_size));

    /* Update slab flag */
    *in_slab = use_slab;

    return 0;
}

该函数中 new_area_start 表示向 type 中添加物理内存区域起始物理地址，new_area_size 表示内存区域大小。收件检查是否使用 slab 缓存以及是否可以扩充 type 中 region 数组大小。

获取原 region 数组大小并将其乘以 2 作为将要分配 region 数组大小，按页面对齐并根据 type 类型获取相应 slab 缓存使用标志位。

开始分配新 region 数组内存空间，如果使用 slab，则从 slab 缓存中分配，否则从 memblock 中分配。

最后复制原来 region 数组并将剩余空间设为 0 并释放原数组所在内存空间。

(5) 移除 memblock_type 中相应内存区域

static int __init_memblock memblock_isolate_range(struct memblock_type *type,
                    phys_addr_t base, phys_addr_t size,
                    int *start_rgn, int *end_rgn)
{
    phys_addr_t end = base + memblock_cap_size(base, &size);
    int idx;
    struct memblock_region *rgn;

    *start_rgn = *end_rgn = 0;

    if (!size)
        return 0;

    /* we'll create at most two more regions */
    while (type->cnt + 2 > type->max)
        if (memblock_double_array(type, base, size) < 0)
            return -ENOMEM;

    for_each_memblock_type(idx, type, rgn) {
        phys_addr_t rbase = rgn->base;
        phys_addr_t rend = rbase + rgn->size;

        if (rbase >= end)
            break;
        if (rend <= base)
            continue;

        if (rbase < base) {
            /*
             * @rgn intersects from below.  Split and continue
             * to process the next region - the new top half.
             */
            rgn->base = base;
            rgn->size -= base - rbase;
            type->total_size -= base - rbase;
            memblock_insert_region(type, idx, rbase, base - rbase,
                           memblock_get_region_node(rgn),
                           rgn->flags);
        } else if (rend > end) {
            /*
             * @rgn intersects from above.  Split and redo the
             * current region - the new bottom half.
             */
            rgn->base = end;
            rgn->size -= end - rbase;
            type->total_size -= end - rbase;
            memblock_insert_region(type, idx--, rbase, end - rbase,
                           memblock_get_region_node(rgn),
                           rgn->flags);
        } else {
            /* @rgn is fully contained, record it */
            if (!*end_rgn)
                *start_rgn = idx;
            *end_rgn = idx + 1;
        }
    }

    return 0;
}

该函数从 type 中 region 数组分离指定范围物理内存，base 表示分离内存区域起始物理地址，size 为分离物理内存大小，start_rgn 为输出分离后的内存区域起始 region，end_rgn 为结束 region。如果 type 中 region 数组空间不足则扩充 region 数组。

循环遍历 type 中 region 数组，对于处于分离内存区域的 region 进行分割并重新插入到数组中，最后返回索引。

static void __init_memblock memblock_remove_region(struct memblock_type *type, unsigned long r)
{
    type->total_size -= type->regions[r].size;
    memmove(&type->regions[r], &type->regions[r + 1],
        (type->cnt - (r + 1)) * sizeof(type->regions[r]));
    type->cnt--;

    /* Special case for empty arrays */
    if (type->cnt == 0) {
        WARN_ON(type->total_size != 0);
        type->cnt = 1;
        type->regions[0].base = 0;
        type->regions[0].size = 0;
        type->regions[0].flags = 0;
        memblock_set_region_node(&type->regions[0], MAX_NUMNODES);
    }
}

将 type 中指定索引 region 移除数组。

static int __init_memblock memblock_remove_range(struct memblock_type *type,
                      phys_addr_t base, phys_addr_t size)
{
    int start_rgn, end_rgn;
    int i, ret;

    ret = memblock_isolate_range(type, base, size, &start_rgn, &end_rgn);
    if (ret)
        return ret;

    for (i = end_rgn - 1; i >= start_rgn; i--)
        memblock_remove_region(type, i);
    return 0;
}

从 type 移除处于给定范围内物理内存区域。

二、伙伴分配器

当系统内核初始化完毕后，使用页分配器管理物理页，当使用的页分配器是伙伴分配器，伙伴分配器的特点是算法简单且高效。连续的物理页称为页块（page block）。阶（order）是伙伴分配器的一个专业术语，是页的数量单位，2^n 个连续页称为 n 阶页块。物理内存被分成多个 order:0 ~ 10，每个 order 中连续 page 的个数是 2^order，如果一个 order 中可用的 memory size 小于期望分配的 size，那么更大 order 的内存块会被对半切分，切分之后的两个小块互为 buddies。其中一个子块用于分配，另一个空闲的。这些块在必要时会连续减半，直到达到所需大小的 memory 块为止，当一个 block 被释放之后，会检查它的 buddies 是否也是空闲的，如果是，那么这对 buddies 将会被合并。

满足以下条件的两个 n 阶页块称为伙伴：

1. 两个页块是相邻的，即物理地址是连续的；
2. 页块的第一页的物理页号必须是 2^n 的整数倍；
3. 如果合并成（n+1）阶页块，第一页的物理页号必须是 2^(n+1) 的整数倍。

2.1 伙伴分配器原理

伙伴分配器分配和释放物理页的数量单位为阶。分配 n 阶页块的过程如下：

1. 查看是否有空闲的 n 阶页块，如果有直接分配；否则，继续执行下一步；
2. 查看是否存在空闲的（n+1）阶页块，如果有，把（n+1）阶页块分裂为两个 n 阶页块，一个插入空闲 n 阶页块链表，另一个分配出去；否则继续执行下一步。
3. 查看是否存在空闲的（n+2）阶页块，如果有把（n+2）阶页块分裂为两个（n+1）阶页块，一个插入空闲（n+1）阶页块链表，另一个分裂为两个 n 阶页块，一个插入空闲 n 阶页块链表，另一个分配出去；如果没有，继续查看更高阶是否存在空闲页块。

上图的 buddy 分配和回收可以简单叙述成： 需要分配内存时如果没有合适的内存块，会对半切分内存块直到分离出合适大小的内存块为止，最后再将其返回。需要释放内存时，会寻找相邻的块，如果其已经释放了，就将这俩合并，再递归这个过程，直到无法再合并为止。

2.2 数据结构

分区的伙伴分配器专注于某个内存节点的某个区域。内存区域的结构体成员 free_area 用来维护空闲页块，数组下标对应页块的阶数。系统内存中的每个物理内存页（页帧），都对应于一个 struct page 实例，每个内存域都关联了一个 struct zone 的实例，其中保存了用于管理伙伴数据的主要数数组，内核源码结构：

#include/linux/mmzone.h
struct zone
{
     /* free areas of different sizes */
    struct free_area        free_area[MAX_ORDER];
};
......
/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

struct free_area 是一个伙伴系统的辅助数据结构：

struct free_area {
    struct list_head        free_list[MIGRATE_TYPES];//是用于连接空闲页的链表。页链表包含大小相同的连续内存区
    unsigned long           nr_free;//指定了当前内存区中空闲页块的数目（对 0 阶内存区逐页计算，对 1 阶内存区计算 2 页的数目，对 2 阶内存区计算 4 页集合的数目，依次类推
};

伙伴系统的明显缺点是：由于圆整到下一个 2 的幂，很可能造成分配段内的碎片。例如，33KB 的内存请求只能使用 64KB 段来满足。事实上，我们不能保证因内部碎片而浪费的单元一定少于 50%。

2.3 伙伴分配器的优缺点

优点： 由于将物理内存按照 PFN 将不同的 page 放入到不同 order 中，根据需要分配内存的大小，计算当前这次分配应该在哪个 order 中去找空闲的内存块，如果当前 order 中没有空闲，则到更高阶的 order 中去查找，因此分配的效率比 boot memory 的线性扫描 bitmap 要快很多。

缺点：

1. 释放 page 的时候调用方必须记住之前该 page 分配的 order，然后释放从该 page 开始的 2^order 个 page，这对于调用者来说有点不方便。
2. 因为 buddy allocator 每次分配必须是 2^order 个 page 同时分配，这样当实际需要内存大小小于 2^order 时，就会造成内存浪费，所以 Linux 为了解决 buddy allocator 造成的内部碎片问题，后面会引入 slab 分配器。

2.4 伙伴分配器的结构

内核源码如下：

typedef struct pglist_data {
	struct zone node_zones[MAX_NR_ZONES];//内存区域数组
	struct zonelist node_zonelists[MAX_ZONELISTS];//MAX_ZONELISTS 个备用区域数组

	int nr_zones;//该节点包含的内存区域数量
......
}
//struct zone 在 linux 内存管理（一）中
struct zonelist {
	struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};
struct zoneref {
	struct zone *zone;//指向内存区域数据结构
	int zone_idx;//成员 zone 指向内存区域的类型
};
enum {
	ZONELIST_FALLBACK,//包含所有内存节点的的备用区域列表
#ifdef CONFIG_NUMA
	/*
	 * The NUMA zonelists are doubled because we need zonelists that
	 * restrict the allocations to a single node for __GFP_THISNODE.
	 */
	ZONELIST_NOFALLBACK,//只包含当前节点的备用区域列表（NUMA 专用）
#endif
	MAX_ZONELISTS//表示备用区域列表数量
};

UMA 系统只有一个备用区域的列表，按照区域类型从高到低顺序排列。假设 UMA 系统中包含普通区域和 DMA 区域，则备用区域列表为：(普通区域、DMA 区域)。NUMA 系统中每个内存节点有两个备用区域列表：一个包含所有节点的内存区域，另一个仅包含当前节点的内存区域。

ZONELIST_FALLBACK（包含所有内存节点的备用区域）列表有两种排序方法： a. 节点优先顺序：先根据节点距离从小到大排序，然后在每个节点里面根据区域类型从高到低排序。优点是优先选择距离近的内存，缺点是在高区域耗尽以前使用低区域。 b. 区域优先顺序：先根据区域类型从高到低排序，然后在每个区域类型里面根据节点距离从小到大排序。优点是减少低区域耗尽的概率，缺点是不能保证优先选择距离近的内存。

默认的排序方法就是自动选择最优的排序方法：比如是 64 位系统，因为需要 DMA 和 DMA32 区域的备用相对少，所以选择节点优先顺序；如果是 32 位系统，选择区域优先顺序。

内存区域水线

首选的内存区域什么情况下从备用区域借用物理页呢？每个内存区域有 3 个水线： a. 高水线（high）：如果内存区域的空闲页数大于高水线，说明内存区域的内存非常充足； b. 低水线（low）：如果内存区域的空闲页数小于低水线，说明内存区域的内存轻微不足； c. 最低水线（min）：如果内存区域的空闲页数小于最低水线，说明内存区域的内存严重不足。

而且每个区域的水位线是初始化的时候通过每个区域的物理页情况计算出来的。计算后存到 struct zone 的 watermark 数组中，使用的时候直接通过下面的宏定义获取：

#define min_wmark_pages(z) (z->watermark[WMARK_MIN])
#define low_wmark_pages(z) (z->watermark[WMARK_LOW])
#define high_wmark_pages(z) (z->watermark[WMARK_HIGH])

可以通过/proc/zoneinfo 看到系统 zone 的水位线和物理页情况：

jian@ubuntu:~/share/linux-4.19.40-note$ cat /proc/zoneinfo
Node 0, zone      DMA
  pages free     3912
        min      7
        low      8
        high     10
        scanned  0
        spanned  4095
        present  3997
        managed  3976
...
Node 0, zone    DMA32
  pages free     6515
        min      1497
        low      1871
        high     2245
        scanned  0
        spanned  1044480
        present  782288
        managed  762172
  ...
Node 0, zone   Normal
  pages free     2964
        min      474
        low      592
        high     711
        scanned  0
        spanned  262144
        present  262144
        managed  241089
  ...

2.5 伙伴分配器分配过程分析

当向内核请求分配 (2^(i-1), 2^i] 数目的页块时，按照 2^i 页块请求处理。如果对应的页块链表中没有空闲页块，那我们就在更大的页块链表中去找。当分配的页块中有多余的页时，伙伴系统会根据多余的页块大小插入到对应的空闲页块链表中。

例如，要请求一个 128 个页的页块时，先检查 128 个页的页块链表是否有空闲块。如果没有，则查 256 个页的页块链表；如果有空闲块的话，则将 256 个页的页块分成两份，一份使用，一份插入 128 个页的页块链表中。如果还是没有，就查 512 个页的页块链表；如果有的话，就分裂为 128、128、256 三个页块，一个 128 的使用，剩余两个插入对应页块链表。

伙伴分配器进行页分配的时候首先调用 alloc_pages，alloc_pages 会调用 alloc_pages_current，alloc_pages_current 会调用__alloc_pages_nodemask 函数，他是伙伴分配器的核心函数：

/* The ALLOC_WMARK bits are used as an index to zone->watermark */
#define ALLOC_WMARK_MIN		WMARK_MIN	//使用最低水线
#define ALLOC_WMARK_LOW		WMARK_LOW	//使用低水线
#define ALLOC_WMARK_HIGH	WMARK_HIGH	//使用高水线
#define ALLOC_NO_WATERMARKS	0x04 		//完全不检查水线
#define ALLOC_WMARK_MASK	(ALLOC_NO_WATERMARKS-1)//得到水位线的掩码
#ifdef CONFIG_MMU
#define ALLOC_OOM		0x08	//允许内存耗尽
#else
#define ALLOC_OOM		ALLOC_NO_WATERMARKS//允许内存耗尽
#endif
#define ALLOC_HARDER		0x10 //试图更努力分配
#define ALLOC_HIGH			0x20 //调用者是高优先级
#define ALLOC_CPUSET		0x40 //检查 cpuset 是否允许进程从某个内存节点分配页
#define ALLOC_CMA			0x80 //允许从 CMA（连续内存分配器）迁移类型分配

上面是 alloc_pages 的第一个参数分配标志位，表示分配的允许情况，alloc_pages 的第二个参数表示分配的阶数：

static inline struct page *
alloc_pages(gfp_t gfp_mask, unsigned int order)
{
	return alloc_pages_current(gfp_mask, order);
}

struct page *alloc_pages_current(gfp_t gfp, unsigned order)
{
	struct mempolicy *pol = &default_policy;
	struct page *page;

	if (!in_interrupt() && !(gfp & __GFP_THISNODE))
		pol = get_task_policy(current);

	if (pol->mode == MPOL_INTERLEAVE)
		page = alloc_page_interleave(gfp, order, interleave_nodes(pol));
	else
		page = __alloc_pages_nodemask(gfp, order,
				policy_node(gfp, pol, numa_node_id()),
				policy_nodemask(gfp, pol));

	return page;
}

struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
						nodemask_t *nodemask)
{
	...
	/* First allocation attempt */ //快速路径分配函数
	page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
	if (likely(page))
		goto out;
	...
	//快速路径分配失败，会调用下面的慢速分配函数
	page = __alloc_pages_slowpath(alloc_mask, order, &ac);

out:
	if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
		unlikely(memcg_kmem_charge(page, gfp_mask, order) != 0)) {
		__free_pages(page, order);
		page = NULL;
	}

	trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);

	return page;
}

从伙伴分配器的核心函数__alloc_pages_nodemask 可以看到函数主要两部分，一是执行快速分配函数 get_page_from_freelist，二是执行慢速分配函数__alloc_pages_slowpath。现在先看快速分配函数 get_page_from_freelist：

static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
{
	struct zoneref *z = ac->preferred_zoneref;
	struct zone *zone;
	struct pglist_data *last_pgdat_dirty_limit = NULL;

	//扫描备用区域列表中每一个满足条件的区域：区域类型小于等于首选区域类型
	for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
									ac->nodemask) {
		struct page *page;
		unsigned long mark;

		if (cpusets_enabled() &&			//如果编译了 cpuset 功能		
			(alloc_flags & ALLOC_CPUSET) &&	//如果设置了 ALLOC_CPUSET		
			!__cpuset_zone_allowed(zone, gfp_mask))	//如果 cpu 设置了不允许从当前区域分配内存		
			continue;						//那么不允许从这个区域分配，进入下个循环

		if (ac->spread_dirty_pages) {//如果设置了写标志位，表示要分配写缓存		
			//那么要检查内存脏页数量是否超出限制，超过限制就不能从这个区域分配		
			if (last_pgdat_dirty_limit == zone->zone_pgdat)
				continue;

			if (!node_dirty_ok(zone->zone_pgdat)) {
				last_pgdat_dirty_limit = zone->zone_pgdat;
				continue;
			}
		}

		mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];//检查允许分配水线
		//判断（区域空闲页 - 申请页数）是否小于水线
		if (!zone_watermark_fast(zone, order, mark,
				       ac_classzone_idx(ac), alloc_flags)) {
			int ret;

			/* Checked here to keep the fast path fast */
			BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
			//如果没有水线要求，直接选择该区域
			if (alloc_flags & ALLOC_NO_WATERMARKS)
				goto try_this_zone;

			//如果没有开启节点回收功能或者当前节点和首选节点距离大于回收距离
			if (node_reclaim_mode == 0 ||
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
				continue;

			//从节点回收'没有映射到进程虚拟地址空间的内存页'，然后检查水线
			ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
			switch (ret) {
			case NODE_RECLAIM_NOSCAN:
				/* did not scan */
				continue;
			case NODE_RECLAIM_FULL:
				/* scanned but unreclaimable */
				continue;
			default:
				/* did we reclaim enough */
				if (zone_watermark_ok(zone, order, mark,
						ac_classzone_idx(ac), alloc_flags))
					goto try_this_zone;

				continue;
			}
		}

try_this_zone://满足上面的条件了，开始分配		
		//从当前区域分配页
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
				gfp_mask, alloc_flags, ac->migratetype);
		if (page) {
			//分配成功，初始化页
			prep_new_page(page, order, gfp_mask, alloc_flags);

			/*
			 * If this is a high-order atomic allocation then check
			 * if the pageblock should be reserved for the future
			 */
			//如果这是一个高阶的内存并且是 ALLOC_HARDER，需要检查以后是否需要保留
			if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
				reserve_highatomic_pageblock(page, zone, order);

			return page;
		} else {
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/* Try again if zone has deferred pages */
			//如果分配失败，延迟分配
			if (static_branch_unlikely(&deferred_pages)) {
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
		}
	}

	return NULL;
}

每一个 zone，都有伙伴系统维护的各种大小的队列，就像上面伙伴系统原理里讲的那样。这里调用 rmqueue 就很好理解了，就是找到合适大小的那个队列，把页面取下来。接下来的调用链是 rmqueue->__rmqueue->__rmqueue_smallest。在这里，我们能清楚看到伙伴系统的逻辑。

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]);
    page = list_first_entry_or_null(&area->free_list[migratetype],
              struct page, lru);
    if (!page)
      continue;
    list_del(&page->lru);
    rmv_page_order(page);
    area->nr_free--;
    expand(zone, page, order, current_order, area, migratetype);
    set_pcppage_migratetype(page, migratetype);
    return page;
  }
  return NULL;
}

从当前的 order，也即指数开始，在伙伴系统的 free_area 找 2^order 大小的页块。如果链表的第一个不为空，就找到了；如果为空，就到更大的 order 的页块链表里面去找。找到以后，除了将页块从链表中取下来，我们还要把多余部分放到其他页块链表里面。expand 就是干这个事情的。area--就是伙伴系统那个表里面的前一项，前一项里面的页块大小是当前项的页块大小除以 2，size 右移一位也就是除以 2，list_add 就是加到链表上，nr_free++ 就是计数加 1。

然后看看慢速分配函数__alloc_pages_slowpath：

static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
					struct alloc_context *ac)
{
	bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
	const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
	struct page *page = NULL;
	unsigned int alloc_flags;
	unsigned long did_some_progress;
	enum compact_priority compact_priority;
	enum compact_result compact_result;
	int compaction_retries;
	int no_progress_loops;
	unsigned int cpuset_mems_cookie;
	int reserve_flags;

	/*
	 * We also sanity check to catch abuse of atomic reserves being used by
	 * callers that are not in atomic context.
	 */
	if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==
				(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
		gfp_mask &= ~__GFP_ATOMIC;

retry_cpuset:
	compaction_retries = 0;
	no_progress_loops = 0;
	compact_priority = DEF_COMPACT_PRIORITY;
	//后面可能会检查 cpuset 是否允许当前进程从哪些内存节点申请页
	cpuset_mems_cookie = read_mems_allowed_begin();

	/*
	 * The fast path uses conservative alloc_flags to succeed only until
	 * kswapd needs to be woken up, and to avoid the cost of setting up
	 * alloc_flags precisely. So we do that now.
	 */
	//把分配标志位转化为内部的分配标志位
	alloc_flags = gfp_to_alloc_flags(gfp_mask);

	/*
	 * We need to recalculate the starting point for the zonelist iterator
	 * because we might have used different nodemask in the fast path, or
	 * there was a cpuset modification and we are retrying - otherwise we
	 * could end up iterating over non-eligible zones endlessly.
	 */
	//获取首选的内存区域，因为在快速路径中使用了不同的节点掩码，避免再次遍历不合格的区域。
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->high_zoneidx, ac->nodemask);
	if (!ac->preferred_zoneref->zone)
		goto nopage;

	//异步回收页，唤醒 kswapd 内核线程进行页面回收
	if (gfp_mask & __GFP_KSWAPD_RECLAIM)
		wake_all_kswapds(order, gfp_mask, ac);

	/*
	 * The adjusted alloc_flags might result in immediate success, so try
	 * that first
	 */
	//调整 alloc_flags 后可能会立即申请成功，所以先尝试一下
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

	/*
	 * For costly allocations, try direct compaction first, as it's likely
	 * that we have enough base pages and don't need to reclaim. For non-
	 * movable high-order allocations, do that as well, as compaction will
	 * try prevent permanent fragmentation by migrating from blocks of the
	 * same migratetype.
	 * Don't try this for allocations that are allowed to ignore
	 * watermarks, as the ALLOC_NO_WATERMARKS attempt didn't yet happen.
	 */
	//申请阶数大于 0，不可移动的位于高阶的，忽略水位线的
	if (can_direct_reclaim &&
			(costly_order ||
			   (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
			&& !gfp_pfmemalloc_allowed(gfp_mask)) {
		//直接页面回收，然后进行页面分配
		page = __alloc_pages_direct_compact(gfp_mask, order,
							alloc_flags, ac,
							INIT_COMPACT_PRIORITY,
							&compact_result);
		if (page)
			goto got_pg;

		/*
		 * Checks for costly allocations with __GFP_NORETRY, which
		 * includes THP page fault allocations
		 */
		if (costly_order && (gfp_mask & __GFP_NORETRY)) {
			/*
			 * If compaction is deferred for high-order allocations,
			 * it is because sync compaction recently failed. If
			 * this is the case and the caller requested a THP
			 * allocation, we do not want to heavily disrupt the
			 * system, so we fail the allocation instead of entering
			 * direct reclaim.
			 */
			if (compact_result == COMPACT_DEFERRED)
				goto nopage;

			/*
			 * Looks like reclaim/compaction is worth trying, but
			 * sync compaction could be very expensive, so keep
			 * using async compaction.
			 */
			//同步压缩非常昂贵，所以继续使用异步压缩
			compact_priority = INIT_COMPACT_PRIORITY;
		}
	}

retry:
	/* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
	//如果页回收线程意外睡眠则再次唤醒
	if (gfp_mask & __GFP_KSWAPD_RECLAIM)
		wake_all_kswapds(order, gfp_mask, ac);

	//如果调用者承若给我们紧急内存使用，我们就忽略水线
	reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
	if (reserve_flags)
		alloc_flags = reserve_flags;

	/*
	 * Reset the nodemask and zonelist iterators if memory policies can be
	 * ignored. These allocations are high priority and system rather than
	 * user oriented.
	 */
	//如果可以忽略内存策略，则重置 nodemask 和 zonelist
	if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
		ac->nodemask = NULL;
		ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->high_zoneidx, ac->nodemask);
	}

	/* Attempt with potentially adjusted zonelist and alloc_flags */
	//尝试使用可能调整的区域备用列表和分配标志
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

	/* Caller is not willing to reclaim, we can't balance anything */
	//如果不可以直接回收，则申请失败
	if (!can_direct_reclaim)
		goto nopage;

	/* Avoid recursion of direct reclaim */
	if (current->flags & PF_MEMALLOC)
		goto nopage;

	/* Try direct reclaim and then allocating */
	//直接页面回收，然后进行页面分配
	page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
									&did_some_progress);
	if (page)
		goto got_pg;

	/* Try direct compaction and then allocating */
	//进行页面压缩，然后进行页面分配
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
							compact_priority, &compact_result);
	if (page)
		goto got_pg;

	/* Do not loop if specifically requested */
	//如果调用者要求不要重试，则放弃
	if (gfp_mask & __GFP_NORETRY)
		goto nopage;

	/*
	 * Do not retry costly high order allocations unless they are
	 * __GFP_RETRY_MAYFAIL
	 */
	//不要重试代价高昂的高阶分配，除非它们是__GFP_RETRY_MAYFAIL
	if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
		goto nopage;

	//重新尝试回收页
	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
					 did_some_progress > 0, &no_progress_loops))
		goto retry;

	/*
	 * It doesn't make any sense to retry for the compaction if the order-0
	 * reclaim is not able to make any progress because the current
	 * implementation of the compaction depends on the sufficient amount
	 * of free memory (see __compaction_suitable)
	 */
	//如果申请阶数大于 0，判断是否需要重新尝试压缩
	if (did_some_progress > 0 &&
			should_compact_retry(ac, order, alloc_flags,
				compact_result, &compact_priority,
				&compaction_retries))
		goto retry;


	/* Deal with possible cpuset update races before we start OOM killing */
	//如果 cpuset 允许修改内存节点申请就修改
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;

	/* Reclaim has failed us, start killing things */
	//使用 oom 选择一个进程杀死
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;

	/* Avoid allocations with no watermarks from looping endlessly */
	//如果当前进程是 oom 选择的进程，并且忽略了水线，则放弃申请
	if (tsk_is_oom_victim(current) &&
	    (alloc_flags == ALLOC_OOM ||
	     (gfp_mask & __GFP_NOMEMALLOC)))
		goto nopage;

	/* Retry as long as the OOM killer is making progress */
	//如果 OOM 杀手正在取得进展，再试一次
	if (did_some_progress) {
		no_progress_loops = 0;
		goto retry;
	}

nopage:
	/* Deal with possible cpuset update races before we fail */
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;

	/*
	 * Make sure that __GFP_NOFAIL request doesn't leak out and make sure
	 * we always retry
	 */
	if (gfp_mask & __GFP_NOFAIL) {
		/*
		 * All existing users of the __GFP_NOFAIL are blockable, so warn
		 * of any new users that actually require GFP_NOWAIT
		 */
		if (WARN_ON_ONCE(!can_direct_reclaim))
			goto fail;

		/*
		 * PF_MEMALLOC request from this context is rather bizarre
		 * because we cannot reclaim anything and only can loop waiting
		 * for somebody to do a work for us
		 */
		WARN_ON_ONCE(current->flags & PF_MEMALLOC);

		/*
		 * non failing costly orders are a hard requirement which we
		 * are not prepared for much so let's warn about these users
		 * so that we can identify them and convert them to something
		 * else.
		 */
		WARN_ON_ONCE(order > PAGE_ALLOC_COSTLY_ORDER);

		/*
		 * Help non-failing allocations by giving them access to memory
		 * reserves but do not use ALLOC_NO_WATERMARKS because this
		 * could deplete whole memory reserves which would just make
		 * the situation worse
		 */
		//允许它们访问内存备用列表
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);
		if (page)
			goto got_pg;

		cond_resched();
		goto retry;
	}
fail:
	warn_alloc(gfp_mask, ac->nodemask,
			"page allocation failure: order:%u", order);
got_pg:
	return page;
}

alloc_page 和__get_free_page 都是从 Buddy 分配页面，只是最终返回值类型不同而已，前者返回 page 指针，后者返回该 page 所在的虚拟地址。

两者最终都会调用到核心函数__alloc_pages_nodemask。

#define __GFP_WAIT  ((__force gfp_t)0x10u) /* 可以等待和重调度？ */
#define __GFP_HIGH  ((__force gfp_t)0x20u) /* 应该访问紧急分配池？ */
#define __GFP_IO ((__force gfp_t)0x40u) /* 可以启动物理 IO？ */
#define __GFP_FS ((__force gfp_t)0x80u) /* 可以调用底层文件系统？ */
#define __GFP_COLD  ((__force gfp_t)0x100u) /* 需要非缓存的冷页 */
#define __GFP_NOWARN  ((__force gfp_t)0x200u) /* 禁止分配失败警告 */
#define __GFP_REPEAT  ((__force gfp_t)0x400u) /* 重试分配，可能失败 */
#define __GFP_NOFAIL  ((__force gfp_t)0x800u) /* 一直重试，不会失败 */
#define __GFP_NORETRY  ((__force gfp_t)0x1000u)  /* 不重试，可能失败 */
#define __GFP_NO_GROW  ((__force gfp_t)0x2000u)  /* slab 内部使用 */
#define __GFP_COMP  ((__force gfp_t)0x4000u)  /* 增加复合页元数据 */
#define __GFP_ZERO  ((__force gfp_t)0x8000u)  /* 成功则返回填充字节 0 的页 */
#define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) /* 不使用紧急分配链表 */
#define __GFP_HARDWALL  ((__force gfp_t)0x20000u) /* 只允许在进程允许运行的 CPU 所关联的结点分配内存 */
#define __GFP_THISNODE  ((__force gfp_t)0x40000u) /* 没有备用结点，没有策略 */
#define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) /* 页是可回收的 */
#define __GFP_MOVABLE  ((__force gfp_t)0x100000u) /* 页是可移动的 */

__GFP_WAIT 表示分配内存的请求可以中断。也就是说，调度器在该请求期间可随意选择另一个过程执行，或者该请求可以被另一个更重要的事件中断。分配器还可以在返回内存之前，在队列上等待一个事件（相关进程会进入睡眠状态）。如果请求非常重要，则设置__GFP_HIGH，即内核急切地需要内存时。在分配内存失败可能给内核带来严重后果时（比如威胁到系统稳定性或系统崩溃），总是会使用该标志。

__GFP_IO 说明在查找空闲内存期间内核可以进行 I/O 操作。实际上，这意味着如果内核在内存分配期间换出页，那么仅当设置该标志时，才能将选择的页写入硬盘。

__GFP_FS 允许内核执行 VFS 操作。在与 VFS 层有联系的内核子系统中必须禁用，因为这可能引起循环递归调用。如果需要分配不在 CPU 高速缓存中的'冷'页时，则设置__GFP_COLD。

__GFP_NOWARN 在分配失败时禁止内核故障警告。在极少数场合该标志有用。

__GFP_REPEAT 在分配失败后自动重试，但在尝试若干次之后会停止。__GFP_NOFAIL 在分配失败后一直重试，直至成功。

__GFP_ZERO 在分配成功时，将返回填充字节 0 的页。

__GFP_HARDWALL 只在 NUMA 系统上有意义。它限制只在分配到当前进程的各个 CPU 所关联的结点分配内存。如果进程允许在所有 CPU 上运行（默认情况），该标志是无意义的。只有进程可以运行的 CPU 受限时，该标志才有效果。

__GFP_THISNODE 也只在 NUMA 系统上有意义。如果设置该比特位，则内存分配失败的情况下不允许使用其他结点作为备用，需要保证在当前结点或者明确指定的结点上成功分配内存。

__GFP_RECLAIMABLE 和__GFP_MOVABLE 是页迁移机制所需的标志。顾名思义，它们分别将分配的内存标记为可回收的或可移动的。这影响从空闲列表的哪个子表获取内存。

组合：

#define GFP_ATOMIC  (__GFP_HIGH)
#define GFP_NOIO  (__GFP_WAIT)
#define GFP_NOFS  (__GFP_WAIT | __GFP_IO)
#define GFP_KERNEL  (__GFP_WAIT | __GFP_IO | __GFP_FS)
#define GFP_USER  (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
#define GFP_HIGHUSER  (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \
__GFP_HIGHMEM)
#define GFP_HIGHUSER_MOVABLE (__GFP_WAIT | __GFP_IO | __GFP_FS | \
__GFP_HARDWALL | __GFP_HIGHMEM | \
__GFP_MOVABLE)
#define GFP_DMA __GFP_DMA
#define GFP_DMA32 __GFP_DMA32

GFP_ATOMIC 用于原子分配，在任何情况下都不能中断，可能使用紧急分配链表中的内存。

GFP_NOIO 和 GFP_NOFS 分别明确禁止 I/O 操作和访问 VFS 层，但同时设置了__GFP_WAIT，因此可以被中断。

GFP_KERNEL 和 GFP_USER 分别是内核和用户分配的默认设置。二者的失败不会立即威胁系统稳定性。GFP_KERNEL 绝对是内核源代码中最常使用的标志。

GFP_HIGHUSER 是 GFP_USER 的一个扩展，也用于用户空间。它允许分配无法直接映射的高端内存。使用高端内存页是没有坏处的，因为用户过程的地址空间总是通过非线性页表组织的。GFP_HIGHUSER_MOVABLE 用途类似于 GFP_HIGHUSER，但分配将从虚拟内存域 ZONE_MOVABLE 进行。

GFP_DMA 用于分配适用于 DMA 的内存，当前是__GFP_DMA 的同义词。GFP_DMA32 也是__GFP_GMA32 的同义词。

三、Slab 分配器

Linux 内核中基于伙伴算法实现的分区页框分配器适合大块内存的请求，它所分配的内存区是以页框为基本单位的。有时候，我们不需要一下子分配很大的内存，对于内核中小块连续内存的请求，例如分配一个 task_struct 结构，只需要分配小块的内存，去存储这个进程描述结构的对象。为了满足对这种小内存块的需要，Linux 系统采用了一种被称为 slab 分配器的技术，用于分配称为 slab 的一小块内存。它的基本原理是从内存管理模块申请一整块页，然后划分成多个小块的存储池，用复杂的队列来维护这些小块的状态（状态包括：被分配了 / 被放回池子 / 应该被回收）。

也正是因为 slab 分配器对于队列的维护过于复杂，后来就有了一种不使用队列的分配器 slub 分配器，后面我们会解析这个分配器。但是你会发现，它里面还是用了很多 slab 的字眼，因为它保留了 slab 的用户接口，可以看成 slab 分配器的另一种实现。还有一种小块内存的分配器称为 slob，非常简单，主要使用在小型的嵌入式系统。

图显示了 slab、cache 及 object 三者之间的关系。该图显示了 2 个大小为 3KB 的内核对象和 3 个大小为 7KB 的对象，它们位于各自的 cache 中。slab 分配算法采用 cache 来存储内核对象。在创建 cache 时，若干起初标记为 free 的对象被分配到 cache。cache 内的对象数量取决于相关 slab 的大小。例如，12KB slab（由 3 个连续的 4KB 页面组成）可以存储 6 个 2KB 对象。最初，cache 内的所有对象都标记为空闲。当需要内核数据结构的新对象时，分配器可以从 cache 上分配任何空闲对象以便满足请求。从 cache 上分配的对象标记为 used（使用）。

让我们考虑一个场景，这里内核为表示进程描述符的对象从 slab 分配器请求内存。在 Linux 系统中，进程描述符属于 struct task_struct 类型，它需要大约 1.7KB 的内存。当 Linux 内核创建一个新任务时，它从 cache 中请求 struct task_struct 对象的必要内存。cache 利用已经在 slab 中分配的并且标记为 free (空闲）的 struct task_struct 对象来满足请求。

3.1 Slab 核心思想

为每种对象类型创建一个内存缓存，每个内存缓存由多个大块组成，一个大块是一个或多个连续的物理页，每个大块包含多个对象。slab 采用面向对象的思想，基于对象类型管理内存，每种对象被划分为一个类，比如进程描述符（task_struct）是一个类，每个进程描述符实现是一个对象。内存缓存组成结构如下：

在 Linux 中，slab 可以处于三种可能状态之一：

• 满的：slab 的所有对象标记为使用。
• 空的：slab 上的所有对象标记为空闲。
• 部分：slab 上的对象有的标记为使用，有的标记为空闲。

slab 分配器首先尝试在部分为空的 slab 中用空闲对象来满足请求。如果不存在，则从空的 slab 中分配空闲对象。如果没有空的 slab 可用，则从连续物理页面分配新的 slab，并将其分配给 cache；从这个 slab 上，再分配对象内存。

3.2 Slab 分配器的作用

a. 能够分配更小块的内存，可以帮助消除伙伴分配器原本会造成的内部碎片问题 b. 缓存常用的 object，因此内核不会在分配，初始化和销毁 object 上浪费时间。 c. 作为一个高速缓存，它用来存储内核中那些经常分配并释放的对象。通过着色技术调整对象以更好的使用硬件高速缓存

Slab 分配器的原理

slab 分配器由 kmem_cache --> kmem_cache_node --> object 三个结构相结合地方式来描述，其中 cache 由 struct kmem_cache 来描述，struct kmem_cache.中的成员 struct kmem_cache_node，lists 数组包含三个 slab list:full,part,free，这三个 list 是有 struct slab 结构组成的链表。其中 struct slab 中的 s_mem 是第一个 object 的起始地址，因此就可以通过 kmem_cache --> kmem_cache_node --> object 找到空闲的 object。其中 slab 中的 page 的 prev 指向 cache，next 指向 slab。

而 slab 还分为 on-slab 和 off-slab，是指当 object 的 size 特别大的时候，slab 中新分配的 page 就全部放 object，而 struct slab 结构单独从通用 slab 中进行分配，如果 object 的 size 比较小，则可以将 struct slab 放置在新分配的 page 开头，然后再放置 object。

slab 分配器提供两个主要优点：

1. 没有因碎片而引起内存浪费。碎片不是问题，因为每个内核数据结构都有关联的 cache，每个 cache 都由一个或多个 slab 组成，而 slab 按所表示对象的大小来分块。因此，当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。
2. 可以快速满足内存请求。因此，当对象频繁地被分配和释放时，如来自内核请求的情况，slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而，由于对象已预先创建，因此可以从 cache 中快速分配。再者，当内核用完对象并释放它时，它被标记为空闲并返回到 cache，从而立即可用于后续的内核请求。

通过命令 sudo cat /proc/slabinfo 可查看系统当前 slab 使用情况。slab 分配器的实现源码： include/linux/slab_def.h include/linux/slab.h mm/slab.c

Slab 结构分析

我们来仔细看看，缓存区 struct kmem_cache 到底是什么样子。\include\linux\slab_def.h

struct kmem_cache {
  struct kmem_cache_cpu __percpu *cpu_slab;
  /* Used for retriving partial slabs etc */
  unsigned long flags;
  unsigned long min_partial;
  int size;    /* The size of an object including meta data */
  int object_size;  /* The size of an object without meta data */
  int offset;    /* Free pointer offset. */
#ifdef CONFIG_SLUB_CPU_PARTIAL
  int cpu_partial;  /* Number of per cpu partial objects to keep around */
#endif
  struct kmem_cache_order_objects oo;
  /* Allocation and freeing of slabs */
  struct kmem_cache_order_objects max;
  struct kmem_cache_order_objects min;
  gfp_t allocflags;  /* gfp flags to use on each alloc */
  int refcount;    /* Refcount for slab cache destroy */
  void (*ctor)(void *);
......
  const char *name;  /* Name (only for display!) */
  struct list_head list;  /* List of slab caches */
......
  struct kmem_cache_node *node[MAX_NUMNODES];
};

在 struct kmem_cache 里面，有个变量 struct list_head list，这个结构很重要。我们可以想象一下，对于操作系统来讲，要创建和管理的缓存绝对不止 task_struct，还有 mm_struct，fs_struct 都需要。因此，所有的缓存最后都会放在一个链表里面，也就是 LIST_HEAD(slab_caches)。对于缓存来讲，其实就是分配了连续几页的大内存块，然后根据缓存对象的大小，切成小内存块。

接下来就是最重要的两个成员变量出场的时候了。kmem_cache_cpu 和 kmem_cache_node，它们都是每个 NUMA 节点上有一个，我们只需要看一个节点里面的情况。

在分配缓存块的时候，要分两种路径，fast path 和 slow path，也就是快速通道和普通通道。其中 kmem_cache_cpu 就是快速通道，kmem_cache_node 是普通通道。每次分配的时候，要先从 kmem_cache_cpu 进行分配。如果 kmem_cache_cpu 里面没有空闲的块，那就到 kmem_cache_node 中进行分配；如果还是没有空闲的块，才去伙伴系统分配新的页。

我们来看一下，kmem_cache_cpu 里面是如何存放缓存块的:

struct kmem_cache_cpu {
  void **freelist;  /* Pointer to next available object */
  unsigned long tid;  /* Globally unique transaction id */
  struct page *page;  /* The slab from which we are allocating */
#ifdef CONFIG_SLUB_CPU_PARTIAL
  struct page *partial;  /* Partially allocated frozen slabs */
#endif
......
};

在这里，page 指向大内存块的第一个页，缓存块就是从里面分配的。freelist 指向大内存块里面第一个空闲的项。按照上面说的，这一项会有指针指向下一个空闲的项，最终所有空闲的项会形成一个链表。partial 指向的也是大内存块的第一个页，之所以名字叫 partial（部分），就是因为它里面部分被分配出去了，部分是空的。这是一个备用列表，当 page 满了，就会从这里找。

我们再来看 kmem_cache_node 的定义：

struct kmem_cache_node {
  spinlock_t list_lock;
......
#ifdef CONFIG_SLUB
  unsigned long nr_partial;
  struct list_head partial;
......
#endif
};

这里面也有一个 partial，是一个链表。这个链表里存放的是部分空闲的内存块。这是 kmem_cache_cpu 里面的 partial 的备用列表，如果那里没有，就到这里来找。

3.3 Slab 分配流程

下面我们就来看看这个分配过程。kmem_cache_alloc_node 会调用 slab_alloc_node。你还是先重点看这里面的注释，这里面说的就是快速通道和普通通道的概念。

/*
 * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
 * have the fastpath folded into their functions. So no function call
 * overhead for requests that can be satisfied on the fastpath.
 *
 * The fastpath works by first checking if the lockless freelist can be used.
 * If not then __slab_alloc is called for slow processing.
 *
 * Otherwise we can simply pick the next object from the lockless free list.
 */
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
    gfp_t gfpflags, int node, unsigned long addr)
{
  void *object;
  struct kmem_cache_cpu *c;
  struct page *page;
  unsigned long tid;
......
  tid = this_cpu_read(s->cpu_slab->tid);
  c = raw_cpu_ptr(s->cpu_slab);
......
  object = c->freelist;
  page = c->page;
  if (unlikely(!object || !node_match(page, node))) {
    object = __slab_alloc(s, gfpflags, node, addr, c);
    stat(s, ALLOC_SLOWPATH);
  }
......
  return object;
}

快速通道很简单，取出 cpu_slab 也即 kmem_cache_cpu 的 freelist，这就是第一个空闲的项，可以直接返回了。如果没有空闲的了，则只好进入普通通道，调用__slab_alloc。

static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
        unsigned long addr, struct kmem_cache_cpu *c)
{
  void *freelist;
  struct page *page;
......
redo:
......
  /* must check again c->freelist in case of cpu migration or IRQ */
  freelist = c->freelist;
  if (freelist)
    goto load_freelist;


  freelist = get_freelist(s, page);


  if (!freelist) {
    c->page = NULL;
    stat(s, DEACTIVATE_BYPASS);
    goto new_slab;
  }


load_freelist:
  c->freelist = get_freepointer(s, freelist);
  c->tid = next_tid(c->tid);
  return freelist;


new_slab:


  if (slub_percpu_partial(c)) {
    page = c->page = slub_percpu_partial(c);
    slub_set_percpu_partial(c, page);
    stat(s, CPU_PARTIAL_ALLOC);
    goto redo;
  }


  freelist = new_slab_objects(s, gfpflags, node, &c);
......
  return freelis

在这里，我们首先再次尝试一下 kmem_cache_cpu 的 freelist。为什么呢？万一当前进程被中断，等回来的时候，别人已经释放了一些缓存，说不定又有空间了呢。如果找到了，就跳到 load_freelist，在这里将 freelist 指向下一个空闲项，返回就可以了。如果 freelist 还是没有，则跳到 new_slab 里面去。这里面我们先去 kmem_cache_cpu 的 partial 里面看。如果 partial 不是空的，那就将 kmem_cache_cpu 的 page，也就是快速通道的那一大块内存，替换为 partial 里面的大块内存。然后 redo，重新试下。这次应该就可以成功了。如果真的还不行，那就要到 new_slab_objects 了。

static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags,
      int node, struct kmem_cache_cpu **pc)
{
  void *freelist;
  struct kmem_cache_cpu *c = *pc;
  struct page *page;


  freelist = get_partial(s, flags, node, c);


  if (freelist)
    return freelist;


  page = new_slab(s, flags, node);
  if (page) {
    c = raw_cpu_ptr(s->cpu_slab);
    if (c->page)
      flush_slab(s, c);


    freelist = page->freelist;
    page->freelist = NULL;


    stat(s, ALLOC_SLAB);
    c->page = page;
    *pc = c;
  } else
    freelist = NULL;


  return freelis

在这里面，get_partial 会根据 node id，找到相应的 kmem_cache_node，然后调用 get_partial_node，开始在这个节点进行分配。

/*
 * Try to allocate a partial slab from a specific node.
 */
static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
        struct kmem_cache_cpu *c, gfp_t flags)
{
  struct page *page, *page2;
  void *object = NULL;
  int available = 0;
  int objects;
......
  list_for_each_entry_safe(page, page2, &n->partial, lru) {
    void *t;


    t = acquire_slab(s, n, page, object == NULL, &objects);
    if (!t)
      break;


    available += objects;
    if (!object) {
      c->page = page;
      stat(s, ALLOC_FROM_PARTIAL);
      object = t;
    } else {
      put_cpu_partial(s, page, 0);
      stat(s, CPU_PARTIAL_NODE);
    }
    if (!kmem_cache_has_cpu_partial(s)
      || available > slub_cpu_partial(s) / 2)
      break;
  }
......
  return object;
}

acquire_slab 会从 kmem_cache_node 的 partial 链表中拿下一大块内存来，并且将 freelist，也就是第一块空闲的缓存块，赋值给 t。并且当第一轮循环的时候，将 kmem_cache_cpu 的 page 指向取下来的这一大块内存，返回的 object 就是这块内存里面的第一个缓存块 t。如果 kmem_cache_cpu 也有一个 partial，就会进行第二轮，再次取下一大块内存来，这次调用 put_cpu_partial，放到 kmem_cache_cpu 的 partial 里面。

如果 kmem_cache_node 里面也没有空闲的内存，这就说明原来分配的页里面都放满了，就要回到 new_slab_objects 函数，里面 new_slab 函数会调用 allocate_slab。

static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
{
  struct page *page;
  struct kmem_cache_order_objects oo = s->oo;
  gfp_t alloc_gfp;
  void *start, *p;
  int idx, order;
  bool shuffle;


  flags &= gfp_allowed_mask;
......
  page = alloc_slab_page(s, alloc_gfp, node, oo);
  if (unlikely(!page)) {
    oo = s->min;
    alloc_gfp = flags;
    /*
     * Allocation may have failed due to fragmentation.
     * Try a lower order alloc if possible
     */
    page = alloc_slab_page(s, alloc_gfp, node, oo);
    if (unlikely(!page))
      goto out;
    stat(s, ORDER_FALLBACK);
  }
......
  return page;
}

在这里，我们看到了 alloc_slab_page 分配页面。分配的时候，要按 kmem_cache_order_objects 里面的 order 来。如果第一次分配不成功，说明内存已经很紧张了，那就换成 min 版本的 kmem_cache_order_objects。

3.4 用户 API

与 libc 提供的内存申请 API（malloc 和 free）类似，Slab 分配器提供的 API 为 kmalloc() 和 kfree()。kmalloc() 函数定义在 include/linux/slab.h 文件中，接收两个参数，并调用__kmalloc() 函数。最终分配内存的实现是__do_kmalloc() 函数。

分配内存： void * kmalloc (size_t size,gfp_t flags);

重新分配内存： void *krealloc(const void *p, size_t new_size, gfp_t flags)

释放内存： void kfree ( const void * objp);

size：申请的内存大小

flags：参数使用 GFP_XXX 来指定分配内存的具体内存域，例如 GFP_DMA 指定分配适合于 DMA 的内存区。

//include/linux/slab.h
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
......
	return __kmalloc(size, flags);
}
// in mm/slab.c
void *__kmalloc(size_t size, gfp_t flags)
{
    return __do_kmalloc(size, flags, _RET_IP_);
}
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
                      unsigned long caller)
{
    ...
}
/*
 * Common kmalloc functions provided by all allocators
 */
void * __must_check __krealloc(const void *, size_t, gfp_t);
void * __must_check krealloc(const void *, size_t, gfp_t);
void kfree(const void *);
void kzfree(const void *);
size_t ksize(const void *);

创建内存缓存： struct kmem_cache *kmem_cache_create(const char , size_t,size_t,unsigned long, void ()(void *));

指定的内存缓存分配对象： void *kmem_cache_alloc(struct kmem_cache *, gfp_t);

释放对象： void kmem_cache_free(struct kmem_cache *, void *);

销毁内存缓存： void kmem_cache_destroy(struct kmem_cache *);

struct kmem_cache *kmem_cache_create(const char *name, size_t size, size_t align,
		  unsigned long flags, void (*ctor)(void *))
{
	struct kmem_cache *s = NULL;
	const char *cache_name;
	int err;

3.5 数据结构

每个内存缓存对应一个 kmem_cache 实例。

每个内存节点对应一个 kmem_cache_node 实例。

kmem_cache 实例的成员 cpu_slab 指向 array_cache 实例，每个处理器对应一个 array_cache 实例，称为数组缓存，用来缓存刚刚释放的对象，分配时首先从当前处理器的数据缓存分配，避免每次都要从 slab 分配，减少链表操作的锁操作，提高分配的速度。

由于 slab 的缓存特性，slab 分配器从 buddy 分配器中获取的物理内存称为 内存缓存使用结构体 struct kmem_cache（定义在 include/linux/slab_def.h 文件中）描述。一个高速缓存中可以含有多个 kmem_cache 对应的高速缓存，就拿 L1 高速缓存来举例，一个 L1 高速缓存对应一个 kmem_cache 链表，这个链表中的任何一个 kmem_cache 类型的结构体均描述一个高速缓存，而这些高速缓存在 L1 cache 中各自占用着不同的区域。

SLAB 分配器由可变数量的缓存组成，这些缓存由称为'缓存链'的双向循环链表链接在一起（如下图中的 kmem_cache 链表）。在 slab 分配器的上下文中，缓存是特定类型的多个对象的管理器，例如使用 cat /proc/slabinfo 命令输出的 mm_struct 或 fs_cache 缓存，其名字保存在 kmem_cache->name 中（Linux 支持单个最大的 slab 缓存大小为 32MB）。kmem_cache 中所有对象的大小是相同的 (object_size)，并且此 kmem_cache 中所有 SLAB 的大小也是相同的 (gfporder、num)。

每个缓存节点在内存中维护称为 slab 的连续页块，这些页面被切成小块，用于缓存数据结构和对象。kmem_cache 的 kmem_cache_node 成员记录了该 kmem_cache 下的所有 slabs 列表。形成的结构如下图所示。

struct kmem_cache {
    //为了提高效率，每个 CPU 都有一个 slab 空闲对象缓存
	struct array_cache __percpu *cpu_cache;

/* 1) Cache tunables. Protected by slab_mutex */
	unsigned int batchcount;//从本地高速缓存批量移入或移出对象的数量
	unsigned int limit;//本地高速缓存中空闲对象的最大数量
	unsigned int shared;

	unsigned int size;
	struct reciprocal_value reciprocal_buffer_size;
/* 2) touched by every alloc & free from the backend */

	unsigned int flags;		/* constant flags */
	unsigned int num;	//每个 slab 的 obj 对象个数

/* 3) cache_grow/shrink */
	/* order of pgs per slab (2^n) */
	unsigned int gfporder; //每个 slab 中连续页框的数量

	/* force GFP flags, e.g. GFP_DMA */
	gfp_t allocflags;

	size_t colour;			/* cache colouring range */
	unsigned int colour_off;	/* colour offset */
	struct kmem_cache *freelist_cache;
	unsigned int freelist_size;

	/* constructor func */
	void (*ctor)(void *obj);

/* 4) cache creation/removal */
	const char *name;
	struct list_head list;
	int refcount;
	int object_size;
	int align;

/* 5) statistics */
#ifdef CONFIG_DEBUG_SLAB
	unsigned long num_active;
	unsigned long num_allocations;
	unsigned long high_mark;
	unsigned long grown;
	unsigned long reaped;
	unsigned long errors;
	unsigned long max_freeable;
	unsigned long node_allocs;
	unsigned long node_frees;
	unsigned long node_overflow;
	atomic_t allochit;
	atomic_t allocmiss;
	atomic_t freehit;
	atomic_t freemiss;

	/*
	 * If debugging is enabled, then the allocator can add additional
	 * fields and/or padding to every object. size contains the total
	 * object size including these internal fields, the following two
	 * variables contain the offset to the user object and its size.
	 */
	int obj_offset;
#endif /* CONFIG_DEBUG_SLAB */
#ifdef CONFIG_MEMCG_KMEM
	struct memcg_cache_params memcg_params;
#endif

	struct kmem_cache_node *node[MAX_NUMNODES]; //内存节点实例个数
};

struct array_cache {
	unsigned int avail; //本地高速缓存中可用对象的个数，也是空闲数组位置的索引
	unsigned int limit; //本地高速缓存大小
	unsigned int batchcount; //本地高速缓存天长或者清空时是用到的对象个数
	unsigned int touched;//如果本地高速缓存最近被使用过，设置成 1
	void *entry[];	/* 对象的地址
				* Must have this definition in here for the proper
				* alignment of array_cache. Also simplifies accessing the entries.
				*
				* Entries should not be directly dereferenced as
				* entries belonging to slabs marked pfmemalloc will
				* have the lower bits set SLAB_OBJ_PFMEMALLOC
				*/
};

/*
 * The slab lists for all objects.
 */
struct kmem_cache_node {
	spinlock_t list_lock;

#ifdef CONFIG_SLAB
	struct list_head slabs_partial;	//部分分配的 slab
	struct list_head slabs_full; //已经完全分配的 slab
	struct list_head slabs_free; //空 slab，或者没有对象被分配
	unsigned long free_objects;
	unsigned int free_limit;
	unsigned int colour_next;	/* Per-node cache coloring */
	struct array_cache *shared;	/* shared per node */
	struct alien_cache **alien;	/* on other nodes */
	unsigned long next_reap;	/* updated without locking */
	int free_touched;		/* updated without locking */
#endif

#ifdef CONFIG_SLUB
	unsigned long nr_partial;
	struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs;
	atomic_long_t total_objects;
	struct list_head full;
#endif
#endif

};

以上 3 个链表保存的是 slab 描述符，Linux kernel 使用 struct page 来描述一个 slab。单个 slab 可以在 slab 链表之间移动，例如如果一个半满 slab 被分配了对象后变满了，就要从 slabs_partial 中被删除，同时插入到 slabs_full 中去。

page 结构体关于 slab 的部分。struct page 定义在 include/linux/mm_types.h 文件中，与 slab 相关的结构体成员如下所示：

struct page {
	/* First double word block */
	unsigned long flags;		/* Atomic flags, some possibly
								 * updated asynchronously */
	union {
		struct address_space *mapping;	/* If low bit clear, points to
										 * inode address_space, or NULL.
										 * If page mapped as anonymous
										 * memory, low bit is set, and
										 * it points to anon_vma object:
										 * see PAGE_MAPPING_ANON below.
										 */
		void *s_mem;			/* slab first object */
	};

	/* Second double word */
	struct {
		union {
			pgoff_t index;		/* Our offset within mapping. */
			void *freelist;		/* sl[aou]b first free object */
		};

void *s_mem: 指向该页框中第一个 object 的地址。

void *freelist: 用于指向页框中空闲对象链表。空闲对象链表包含页框中每个空闲对象的索引。

内存缓存为每个处理器创建一个数组缓存（结构体 array_cache）。释放对象时，把对象存放到当前处理器对应的数组缓存中；分配对象的时候，先从当前处理器的数组缓存分配对象，采用后进先出（LIFO）原则，可以提高性能。

对于所有对象空间的 slab，没有立即释放，而是放在空闲 slab 链表中。只有内存节点上空闲对象的数量超过限制，才开始回收空闲 slab，直到空闲对象的数量小于或等于限制。

综上所述，Linux 内存管理通过引导分配器完成初始化，伙伴分配器负责物理页的高效管理，Slab 分配器优化了小对象分配，三者协同工作以保障系统内存资源的有效利用。