内存自举分配器

linux内核内存管理子系统分析之二

分析内存子系统初始化前段杂谈

上面首先介绍了内存节点和内存域的概念，这一节本来想接着分析一下page数据结构。但是这个page数据结构的作用实在是太大了，应用也十分广泛，贯穿了整个内存管理系统，所以干说是不能把它说清楚的。我们首先建立一个page的概念：内存管理系统（最低层的伙伴系统）是以页为单位分配管理内存的，所以系统内存中的每一个页用一个page数据结构来管理。

先介绍了一下内存管理系统中最重要的数据结构，我们接下来分析内存管理系统的初始化。在分析之前我们必须把一些概念和模型了解一下，算是为后面的分析铺平道路，这部分内容就叫它杂谈吧。

一些重要的宏定义

我们以arm架构为例子，arm的物理地址空间被分为很多的bank，有些bank映射了片上系统的一些IO，有些bank映射了内存。所以arm系统的内存物理地址起始位置往往不是0。内核中定义了一些地址划分如下

1. TEXT_OFFSET  内核在RAM中的起始位置相对于RAM起始地址偏移。

2. PAGE_OFFSE   内核镜像起始虚拟地址

3. PHYS_OFFSET  RAM启始物理地址，对应于DDR的物理地址

4. KERNEL_RAM_VADDR  内核在RAM中的虚拟地址

5. KERNEL_RAM_PADDR  内核在RAM中的物理地址

6. swapper_pg_dir 初始页目录表虚拟地址，

7. VMALLOC_START 0xc4800000

8. VMALLOC_END   0xe0000000

9. MODULES_VADDR 0xbf000000

10. MODULES_END   0xc0000000

根据下图，我们可以对照理解上面宏的意义。需要说明的是，内核镜像并不是放在内存的最开始部分，它和内存起始位置有一个TEXT_OFFSET的空间。其次，需要注意一下swapper_pg_dir的位置，它是系统的初始页目录表，位置放在kernel代码起始位置之前。VMALLOC_START和直接映射末尾之间会有一个8M的越界保护空间。另外，有兴趣的同学会注意到MODULES_VADDR正好在3G内核空间之前的一段空间中，这个空间是用来映射载入模块的代码和数据的。

#ifndef VMALLOC_START
#define VMALLOC_OFFSET        (8*1024*1024)
#define VMALLOC_START        (((unsigned long)high_memory + VMALLOC_OFFSET) & ~(VMALLOC_OFFSET-1))
#endif 

OK,上面介绍了linux内核中内存的分布情况。我自己在上面画了一个图，一张图的信息量比较大，也省去了敲很多文字还不一定能说清楚。图片画的比较详细，定是理解内核内存管理系统的一句绝妙的心法！

下面我开始介绍一下内存系统的初始化过程。这部分举ARM架构的例子，说明一下内存系统的初始化过程，主要包括了页目录初始化、内存节点和内存域的初始化、自举内存系统的初始化、伙伴系统的初始化。

在分析初始化之前，还需做一些铺垫！呵呵，哪里有这么多的铺垫？linux就是这样无穷无尽！这里要说的就是内核怎么知道板子上有多少内存内，怎么知道内存的物理地址从什么地方开始呢？台式机可能还有BIOS做内存检测，嵌入式系统可没有这玩意儿，那就要靠我们的UBOOT了，UBOOT就要靠我们自己来配置参数来告诉内核，系统上有多少的内存和物理内存的其实地址。这种传递参数的机制叫做tag参数，之后我们会专门搞一个专题来讨论一下。这里不再赘述

#define CONFIG_NR_DRAM_BANKS    1       /* we have 1 bank of DRAM */ 
#define PHYS_SDRAM_1        0x30000000 /* SDRAM Bank #1 */ 
#define PHYS_SDRAM_1_SIZE    0x04000000 /* 64 MB */ 
 
int dram_init (void)
{
    gd->bd->bi_dram[0].start = PHYS_SDRAM_1;
    gd->bd->bi_dram[0].size = PHYS_SDRAM_1_SIZE;
 
    return 0;
}
 
static struct tag *setup_memory_tags(struct tag *params)
{
    bd_t *bd = gd->bd;
    int i;
 
    for (i = 0; i < CONFIG_NR_DRAM_BANKS; i++)
    {
        params->hdr.tag = ATAG_MEM;
        params->hdr.size = tag_size(tag_mem_range);
 
        params->u.mem_range.addr = bd->bi_dram[i].start;
        params->u.mem_range.size = bd->bi_dram[i].size;
 
        params = tag_next(params);
    }
 
    return params;
}
 
/*涉及到的文件有*/ 
armlinux.c

UBOOT中会将板子上的内存物理地址和内存大小通过tag参数传递到内核中，内核将这个参数保存到meminfo这边全局的变量中。

struct membank
{
    unsigned long start;
    unsigned long size;
    int           node;
};
 
struct meminfo
{
    int nr_banks;
    struct membank bank[NR_BANKS];
};

内存管理初始化从paging_init开始

build_mem_type_table可以不用详细分析，这个函数只是判定芯片是属于arm什么系列的做一些记录，方便之后构造页表项等。

sanity_check_meminfo 主要对meminfo结构体中的各个bank做一些检查，主要避免一个bank的地址跨越了normal内存域和高端内粗域，方便之后做处理。

/*
* paging_init() sets up the page tables, initialises the zone memory
* maps, and sets up the zero page, bad page and bad page tables.
*/ 
void __init paging_init(struct machine_desc *mdesc)
{
    void *zero_page;
 
    build_mem_type_table();
    sanity_check_meminfo();
    prepare_page_table();
    bootmem_init();
    devicemaps_init(mdesc);
 
    top_pmd = pmd_off_k(0xffff0000);
 
    /*
     * allocate the zero page.  Note that this always succeeds and
     * returns a zeroed result.
     */ 
    zero_page = alloc_bootmem_low_pages(PAGE_SIZE);
    empty_zero_page = virt_to_page(zero_page);
    flush_dcache_page(empty_zero_page);
}

prepare_page_table可以理解为将处理内核所在的bank之外的其它内存区域的页目录项目全部清零。具体清除了那些区域，可以自己研读。

之后系统调用了bootmem_init函数，这个函数是初始化bootmen系统，bootmen系统是在内核初始化初期，由于伙伴系统并没有初始化好，所以建立了一个简单的动态内存分配系统供给各个模块初始化时期分配内存用。等到伙伴系统建立完毕了，bootmem系统会被废置使用。

实际上bootmem的原理很简单，就是记录一下一个内存节点上起始地址的帧页号和结束地址的帧页号（node_min_pfn和node_low_pfn）。另外bootmem系统中保存了一个bit map，这个bitmap以页帧为单位，一个页帧用一个bit表示，当bit置1表示对应的这个页帧被分配了，如果这个bit是0表示对应的这个叶帧还没有被分配掉。

Bootmem系统的初始化，整个按照内存节点来初始化的。一个内存几点会存在一个bootmem这样一个小系统。初始化过程中首先要对这个内存节点中的内存进行映射，然后计算这个节点中有多少个内存页面，为这些页面分配bitmap所需要的内存。之后调用reserver_bootmem_node将内核已经使用的一些内存区标记为已经使用（这些区域有bitmap、内核的代码段数据段等等）。

Bootmem系统中动态获取和释放内存过程

这里不再文字介绍获取内存和释放内存的过程，而是将主要的代码流程贴出来，在代码中增加了相应的注释

首先必须说一下这个函数的输入参数，bdata就是bootmem的管理数据结构
size就是申请的内存大小、align就是对齐的大小、
goal希望从何处开始申请内存、limit就是希望申请内存地址的最高地址
 
static void *__init alloc_bootmem_core(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;
 
    /*根据这个区域地址的范围和goal，limit的值调整搜索空闲内存的范围*/ 
    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);
 
    /*调整后得到搜索到开始id和结束id*/ 
    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;
            }
 
        /*如果是小于一个页面的情况设置last_end_off和hit_idx等变量*/ 
        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);
        return region;
    }
 
    if (fallback)
    {
        sidx = align_idx(bdata, fallback - 1, step);
        fallback = 0;
        goto find_block;
    }
 
    return NULL;
}
 

Bootmem系统中内存释放过程就相对很简单了，直接将释放页对应的page对应的bitmap中的bit清0就可以了

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

andy yixin deng

mail:andy.yx.deng#gmail.com

2013.3.15 南京