boot memory allocator——自举内存分配器(二：在IA-32系统下的初始化)

bootmem分配器的初始化时一个特定于体系结构的过程，此外还取决于所述计算机的内存布局，在IA-32系统下使用setup_memory，该函数又调用setup_bootmem_allocator来初始化bootmem分配器，如下所示的代码流程图说明了IA-32系统上初始化bootmem分配器涉及的各个步骤。

static void __init setup_memory(void)
{
unsigned long start_pfn;
start_pfn = PFN_UP(__pa(_end));//确定可用的低端内存页帧，对于已经部分使用过的页我们就不能再使用了，所以要用PFN_UP()来获取下一个未使用的页
setup_bootmem_allocator(start_pfn);
}

其实主要的工作还是在setup_bootmem_allocator()里面

void __init setup_bootmem_allocator(void)
{
unsigned long bootmap_size;
bootmap_size = init_bootmem(min_low_pfn, max_low_pfn);//这个函数仅在初始化时用来建立bootmem分配器


register_bootmem_low_pages(max_low_pfn);//通过将位图中对应的比特位清零，释放所有潜在可用的内存页。在IA-32系统上BIOS对该任务提供了支持，BIOS向内核提供了可用内存页的列表，即初始化过程中更早一点提供的e820映射。

//由于bootmem分配器需要一些内存页管理分配位图，必须首先调用reserve_bootmem分配这些内存页，但还有一些其他的内存区已经在使用中，必须相应的标记出来。因此，还需要用reserve_bootmem注册相应的页。需要注册的内存页的确切数目，高度依赖于内核配置。例如，需要保留0页，因为在许多计算机上该页是一个特殊的BIOS页，有些特定于计算机的功能需要该页才能运行正常。其他的reserve_bootmem调用则分配与内核配置相关的内存区，例如用于ACPI数据或SMP启动时的配置。

reserve_bootmem(__pa_symbol(_text), (PFN_PHYS(min_low_pfn) +
bootmap_size + PAGE_SIZE-1) - __pa_symbol(_text));

reserve_bootmem(0, PAGE_SIZE);

reserve_ebda_region();

if (boot_cpu_data.x86_vendor == X86_VENDOR_AMD &&
   boot_cpu_data.x86 == 6)
    reserve_bootmem(0xa0000 - 4096, 4096);


#ifdef CONFIG_SMP
reserve_bootmem(PAGE_SIZE, PAGE_SIZE);
#endif

#ifdef CONFIG_ACPI_SLEEP
acpi_reserve_bootmem();
#endif

#ifdef CONFIG_X86_FIND_SMP_CONFIG
find_smp_config();
#endif

numa_kva_reserve();

#ifdef CONFIG_BLK_DEV_INITRD
if (boot_params.hdr.type_of_loader && boot_params.hdr.ramdisk_image) 
{
unsigned long ramdisk_image = boot_params.hdr.ramdisk_image;
unsigned long ramdisk_size  = boot_params.hdr.ramdisk_size;
unsigned long ramdisk_end   = ramdisk_image + ramdisk_size;
unsigned long end_of_lowmem = max_low_pfn << PAGE_SHIFT;


if (ramdisk_end <= end_of_lowmem) 
{
reserve_bootmem(ramdisk_image, ramdisk_size);
initrd_start = ramdisk_image + PAGE_OFFSET;
initrd_end = initrd_start+ramdisk_size;
} 
       else 
      {
printk(KERN_ERR "initrd extends beyond end of memory "
      "(0x%08lx > 0x%08lx)\ndisabling initrd\n",
      ramdisk_end, end_of_lowmem);
initrd_start = 0;
}
}
#endif
reserve_crashkernel();
}

下面我们来具体分析一下上面提到的主要函数：

(1)init_bootmem及其里面调用的函数分析

unsigned long __init init_bootmem(unsigned long start, unsigned long pages)
{
max_low_pfn = pages;
min_low_pfn = start;
return init_bootmem_core(NODE_DATA(0), start, 0, pages);
}

这个函数仅在初始化时用来建立bootmem分配器。这个函数实际上是init_bootmem_core()函数的封装函数。init_bootmem（）函数的参数start表示内核映象结束处的页面号，而pages表示物理内存顶点所在的页面号。而函数init_bootmem_core()就是对contig_page_data变量进行初始化。下面我们来看一下对该变量的定义：

static bootmem_data_t contig_bootmem_data;
struct pglist_data contig_page_data = {.bdata = &contig_bootmem_data};

变量contig_page_data的类型就是前面介绍过的pg_data_t数据结构。每个pg_data_t数据结构代表着一片均匀的、连续的内存空间。在连续空间UMA结构中，只有一个节点contig_page_data，而在NUMA结构或不连续空间UMA结构中，有多个这样的数据结构。系统中各个节点的pg_data_t数据结构通过node_next连接在一起成为一个链。有一个全局量pgdata_list则指向这个链。从上面的定义可以看出，contig_page_data是链中的第一个点。pg_data_t结构中有个指针bdata，contig_page_data被初始化为指向bootmem_data_t数据结构。注册新的自举分配器可使用init_bootmem_core，所有注册的分配器保存在一个链表中，表头就是前面所说的bdata_list。下面我们来看init_bootmem_core（）函数的具体代码：

static unsigned long __init init_bootmem_core(pg_data_t *pgdat,unsigned long mapstart, unsigned long start, unsigned long end)
{
bootmem_data_t *bdata = pgdat->bdata;
unsigned long mapsize;// 变量mapsize存放位图的大小


bdata->node_bootmem_map = phys_to_virt(PFN_PHYS(mapstart));//#difine PFN_PHYS(x) ((x) << PAGE_SHIFT),phys_to_virt(mapstart << PAGE_SHIFT)把给定的物理地址转换为虚地址。
bdata->node_boot_start = PFN_PHYS(start);//#define PFN_PHYS(x) ((x) << PAGE_SHIFT);用节点的起始物理地址初始化node_boot_start
bdata->node_low_pfn = end;//用物理内存节点的页面号初始化node_low_pfn
link_bootmem(bdata);//将新注册的bootmem_data_t结点插入到全局变量bdata_list中,具体分析见下文


/*
* Initially all pages are reserved - setup_arch() has to
* register free RAM areas explicitly.
*/
mapsize = get_mapsize(bdata);//获取需要分配给该bootmem_data_t结点中存放位图的大小，具体分析见下文
memset(bdata->node_bootmem_map, 0xff, mapsize);// 初始化所有被保留的页面，即通过把页面中的所有位都置为1来标记保留的页面


return mapsize;
}

上面那条语句18把存放位图页面的内存都置为1。置为1是什么意思呢，就是代表这些个页面都被占用掉了，一个都不剩了。我们会很困惑，到目前为止只有内核映像占用的页面和这个位图占用的页面被占用了，把这些被占用的页面都置为1才对啊。事实上内核的思想与我们正好相反，我们是想一开始都置为0，表示都空闲，哪个被分配了再置为1。可是这里有个问题位图指示的那些个页面中本来就有些是不能用的，他们是ROM而不是RAM，你一开始就应该把他置为1，而且还有其他一些复杂的情况，所以内核反过来，先全置为1表示全部占用，然后发现有空闲的再置为0就好了。

static void __init link_bootmem(bootmem_data_t *bdata)
{
bootmem_data_t *ent;


if (list_empty(&bdata_list)) 
{
list_add(&bdata->list, &bdata_list);
return;
}//如果bdata_list位空，那么只需将刚刚注册的结点插进链表即可
list_for_each_entry(ent, &bdata_list, list) //否则，从第一个结点开始一次遍历链表
{
if (bdata->node_boot_start < ent->node_boot_start) //按照在物理空间上分配给该bootmem_data_t结点的起始页帧号
{
list_add_tail(&bdata->list, &ent->list);//从小到大的顺序将该结点插入链表中
return;
}
}
list_add_tail(&bdata->list, &bdata_list);//如果分配给该结点的起始页帧号大于链表中所有其他结点的起始页帧号，就将该结点插入链表尾
}

static unsigned long __init get_mapsize(bootmem_data_t *bdata)
{
unsigned long mapsize;
unsigned long start = PFN_DOWN(bdata->node_boot_start);
unsigned long end = bdata->node_low_pfn;

mapsize = ((end - start) + 7) / 8;//(end - start)给出现有的页面数，再加个7是为了向上取整，除以8就获得了所需的字节数（因为每个字节映射8个页面）
return ALIGN(mapsize, sizeof(long));//#define ALIGN(val,align)(((val) + ((align) - 1)) & ~((align) - 1)),使mapsize成为下一个4的倍数（4为CPU的字长）。例如，假设有40个物理页面，因此，我们可以得出mapsize为5个字节。所以，上面的操作就变为（5＋（4－1））＆~(4-1)即(00001000&11111100)，其结果为8。这就有效地使mapsize变为4的倍数
}

(2)register_bootmem_low_pages及其里面调用的函数分析

void __init register_bootmem_low_pages(unsigned long max_low_pfn)
{
int i;
if (efi_enabled)
 {
efi_memmap_walk(free_available_memory, NULL);
return;
}//对于efi_enabled这一段暂时还不是太清楚，希望理解的人讲解一下。
for (i = 0; i < e820.nr_map; i++)
 {
unsigned long curr_pfn, last_pfn, size;

if (e820.map[i].type != E820_RAM)
continue;
curr_pfn = PFN_UP(e820.map[i].addr);
if (curr_pfn >= max_low_pfn)
continue;
last_pfn = PFN_DOWN(e820.map[i].addr + e820.map[i].size);

if (last_pfn > max_low_pfn)
last_pfn = max_low_pfn;

if (last_pfn <= curr_pfn)
continue;

size = last_pfn - curr_pfn;
free_bootmem(PFN_PHYS(curr_pfn), PFN_PHYS(size));//程序能运行到此处，说明内存区是属于RAM，并且符合那些边界检查，所以需要将他们的bit位置0
}
}

在函数register_bootmem_low_pages中开始把能用的RAM内存给空出来，这个函数根据bios提供的RAM分布状况，来进行置0. 由于RAM 可能分成好几个段，专门有一个结构来描述这个状况：

struct e820map
 {
  __u32 nr_map;
  struct e820entry map[E820MAX];
 };

struct e820entry
 {
 __u64 addr; /* start of memory segment */
 __u64 size; /* size of memory segment */
 __u32 type; /* type of memory segment */
 } __attribute__((packed));

addr为起始地址，size为大小，type为类型，例如这个数组中有一个成员的tpye是RAM,那就是我们把位图相应位置0的。假如addr这个物理地址换算成页面号为100，而size的值是108，那么从100~207这108个页面就是可用的页面，把这些页面在位图里对应的bit位置成0，表示这些页面空闲可用，对应这个结构数组中所有的RAM类型的都这么处理，这样就达到了把系统中所有的的可用RAM都标出来了的效果，而其他的ROM等不可用的内存仍然保留成1。具体的实现是在free_bootmem函数中:

void __init free_bootmem(unsigned long addr, unsigned long size)
{
free_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}

可知free_bootmem只是free_bootmem_core的封装,free_bootmem_core如下：

static void __init free_bootmem_core(bootmem_data_t *bdata, unsigned long addr,unsigned long size)
{
unsigned long sidx, eidx;
unsigned long i;
BUG_ON(!size);
BUG_ON(PFN_DOWN(addr + size) > bdata->node_low_pfn);
if (addr < bdata->last_success)
bdata->last_success = addr;//如果该块内存的起始地址要比最后一次成功分配的地址，则让最后一次成功分配的地址等于该块内存的起始地址， 这样一来，最后，last_success会指向第一个可用内存块的首地址。
sidx = PFN_UP(addr) - PFN_DOWN(bdata->node_boot_start);//对齐后的该块内存的首地址到物理内存起始地址的距离（以页为单位）；
eidx = PFN_DOWN(addr + size - bdata->node_boot_start);//某一个E820项代表的内存段的结束地址到物理内存起始地址的距离（以页为单位）
for (i = sidx; i < eidx; i++) 
{
if (unlikely(!test_and_clear_bit(i, bdata->node_bootmem_map)))
BUG();
}//清位图中从sidx到eidx的所有位，即把这些页面标记为可用。
}

(3)reserve_bootmem及其里面调用的函数分析

通过(2)中的讲解，有人可能要提出疑问，内核的映像和以上用于存放位图的页面无疑也是在RAM中的，而register_bootmem_low_pages函数不问青红皂白把所有的RAM都置为可用，也包括内核的映像所占页面和存放位图所占页面，说明这部分内存也可以分配，那不就出问题了吗。是的，你说的没错，所以内核马上要通过reserve_bootmem函数把这部分内存保留起来，reserve_bootmem函数如下：

void __init reserve_bootmem(unsigned long addr, unsigned long size)
{
reserve_bootmem_core(NODE_DATA(0)->bdata, addr, size);
}

与上面一样,reserve_bootmem只是reserve_bootmem_core的封装,reserve_bootmem_core如下：

static void __init reserve_bootmem_core(bootmem_data_t *bdata, unsigned long addr,unsigned long size)
{
unsigned long sidx, eidx;
unsigned long i;
BUG_ON(!size);
BUG_ON(PFN_DOWN(addr) >= bdata->node_low_pfn);
BUG_ON(PFN_UP(addr + size) > bdata->node_low_pfn);

sidx = PFN_DOWN(addr - bdata->node_boot_start);
eidx = PFN_UP(addr + size - bdata->node_boot_start);

for (i = sidx; i < eidx; i++)
if (test_and_set_bit(i, bdata->node_bootmem_map)) 
{
#ifdef CONFIG_DEBUG_BOOTMEM
printk("hm, page %08lx reserved twice.\n", i*PAGE_SIZE);
#endif
}
}

而reserve_bootmem_core()实现的内容，就是将制定内存节点内addr ~ addr+size范围内的内存标记成保留。

你会发现，它和free_bootmem_core()的实现方法如出一辙，但这里有一些细节问题需要分析一下：

eidx = PFN_UP(addr + size - bdata->node_boot_start);

对于这个结束位置的索引，free_bootmem_core()是向前保留，也就是说没有被完整释放的页将被认为是保留状态， 而reserve_bootmem_core()是向后保留，也就是说部分被占用的页将被认为是整页保留。