boot memory allocator——自举内存分配器(三：内存分配)

内核提供了各种函数，用于在初始化期间分配内存。在UMA系统上有下列函数可用。

alloc_bootmem(size)和alloc_boormem_pages(sizes)按指定大小在ZONE_NORMAL内存域分配内存。数据是对齐的，这使得内存或者从可适用于L1高速缓存的理想位置开始，或者从也边界开始。尽管alloc_boormem_pages(sizes)的名字暗示所需内存长度是以页为单位，但实际上_pages只是指数据的对齐方式。

alloc_bootmem_low和alloc_bootmem_low_pages的工作方式类似于上述函数，只是从ZONE_DMA内存域分配内存。因此，只有需要DMA时，才能使用上述函数。低端DMA内存与普通内存的区别在于其起始地址。搜索适用于DMA的内存从地址0开始，而请求普通内存时则从MAX_DMA_ADDRESS向上(__pa将内存地址转换为页号)，也就是DMA内存区之后的地址。

基本上NUMA系统的API是相同的，但函数名增加了_node后缀。与UMA系统的函数相比，还需要一个额外的参数，指定用于内存分配的结点。

#define alloc_bootmem(x)  __alloc_bootmem(x, SMP_CACHE_BYTES, __pa(MAX_DMA_ADDRESS))
#define alloc_bootmem_low(x)  __alloc_bootmem_low(x, SMP_CACHE_BYTES, 0)
#define alloc_bootmem_pages(x)  __alloc_bootmem(x, PAGE_SIZE, __pa(MAX_DMA_ADDRESS))
#define alloc_bootmem_low_pages(x)  __alloc_bootmem_low(x, PAGE_SIZE, 0)

这些函数都是_alloc_bootmem的前端，所需分配内存的长度(x)未作改变直接传递给_alloc_bootmem，但内存对齐方式有两个选项：

SMP_CACHE_BYTES会对齐数据，使之在大多数体系结构上能够理想的置于L1高速缓存中(尽管名字带有SMP字样，但单处理器系统也会定义该常数)

PAGE_SIZE将数据对齐到页边界。

后一种对齐方式适用于分配一个或多个整页，但前者在分配设计部分页时能够产生更好的效果。_alloc_bootmem如下：

void * __init __alloc_bootmem(unsigned long size, unsigned long align,unsigned long goal)
{
	void *mem = __alloc_bootmem_nopanic(size,align,goal);

	if (mem)
		return mem;
	printk(KERN_ALERT "bootmem alloc of %lu bytes failed!\n", size);
	panic("Out of memory");
	return NULL;
}

_alloc_bootmem需要3个参数来描述内存分配请求：size是所需内存区的长度，align表示数据的对齐方式，而goal指定了开始搜索适当空闲内存区的起始地址。可以看到_alloc_bootmem将实际工作委托给_alloc_bootmem_nopanic，_alloc_bootmem_nopanic函数如下：

void * __init __alloc_bootmem_nopanic(unsigned long size, unsigned long align,unsigned long goal)
{
	bootmem_data_t *bdata;
	void *ptr;

	list_for_each_entry(bdata, &bdata_list, list) {
		ptr = __alloc_bootmem_core(bdata, size, align, goal, 0);
		if (ptr)
			return ptr;
	}
	return NULL;
}

由于可以注册多个bootmem分配器(这些分配器都保存在一个全局链表bdata_list中)，_alloc_bootmem_core会遍历所有的分配器，直到分配成功为止。_alloc_bootmem_core函数的功能相对而言很广泛(在启动期间不需要太高的效率)，后文会详细讨论其源代码。该函数主要实现了最先适配算法，但该分配器功能已经增强，不仅能够分配整个内存页，还能分配页的一部分。该函数主要完成如下功能：

(1)从goal开始，扫描位图，查找满足分配请求的空闲内存区

(2)如果目标页紧接着上一次分配的页，即bootmem_data->last_pos，内核会检查bootmem_data->last_offset，判断所需的内存(包括对齐数据所需的空间)是否能够在上一页分配或从上一页开始分配。

(3)新分配的页在位图对应的比特位置1。最后一页的数目也保存在bootmem_data->last_pos。如果该页未完全分配，则相应的偏移量保存在bootmem_data->last_offset；否则该值置0。
分析_alloc_bootmem_core源代码如下：

void * __init __alloc_bootmem_core(struct bootmem_data *bdata, unsigned long size,unsigned long align, unsigned long goal, unsigned long limit)
{
	unsigned long offset, remaining_size, areasize, preferred;
	unsigned long i, start = 0, incr, eidx, end_pfn;
	void *ret;

	if (!size) {
		printk("__alloc_bootmem_core(): zero-sized request\n");
		BUG();
	}//如果要申请的内存是0的话，系统就会崩溃。
	BUG_ON(align & (align-1));//如果不按2exp(n)对齐，则系统崩溃

	if (limit && bdata->node_boot_start >= limit)
		return NULL;//如果limit非0，并且该结点的起始页都已经超过了limit，则分配失败

	/* on nodes without memory - bootmem_map is NULL */
	if (!bdata->node_bootmem_map)
		return NULL;//如果存放位图的地址都没有分配成功，则初始化就没有成功，分配肯定就更不可能成功了

	end_pfn = bdata->node_low_pfn;//该结点可以直接管理的物理地址空间中最后一页的编号
	limit = PFN_DOWN(limit);//向下取整，获取limit对应的物理页号
	if (limit && end_pfn > limit)
		end_pfn = limit;//确保该结点可以直接管理的物理地址空间中最后一页的编号<=limit

	eidx = end_pfn - PFN_DOWN(bdata->node_boot_start);//计算包括内存孔洞在内的，内存节点的内存空间的总页数
	offset = 0;
	if (align && (bdata->node_boot_start & (align - 1UL)) != 0)//如果align>0并且内存node的物理起始基址又不是按align对齐
		offset = align - (bdata->node_boot_start & (align - 1UL));//求出内存node的物理起始基址到首个align的偏移字节数
	offset = PFN_DOWN(offset);//求出偏移页数

	/*
	 * We try to allocate bootmem pages above 'goal'
	 * first, then we try to allocate lower pages.
	 */
	if (goal && goal >= bdata->node_boot_start && PFN_DOWN(goal) < end_pfn) {//如果分配的起始地址不在0开头处的话，但是在本内存node的物理地址范围内
		preferred = goal - bdata->node_boot_start;//计算这个偏移值

		if (bdata->last_success >= preferred)//如果上次成功分配的内存起始位置，大于这次申请的地址
			if (!limit || (limit && limit > bdata->last_success))//如果limit为0，或limit非0时上次成功分配的内存起始位置在limit之内
				preferred = bdata->last_success;
	} else
		preferred = 0;

	preferred = PFN_DOWN(ALIGN(preferred, align)) + offset;//把分配起始位置相对于本内存node起始位置的偏移量转换成相对于本内存node的偏移页数
	areasize = (size + PAGE_SIZE-1) / PAGE_SIZE;//计算要分配的页数，不足一页按一页计算
	incr = align >> PAGE_SHIFT ? : 1;//这里是求出一个对齐所占的页数，并保证对齐页数至少为一页的大小

restart_scan:
	for (i = preferred; i < eidx; i += incr) {//查看本内存node的所有内存页
		unsigned long j;
		i = find_next_zero_bit(bdata->node_bootmem_map, eidx, i);//在本内存node的页帧位码表的第i位开始到第eidx位之间，寻找第一位为0的位号
		i = ALIGN(i, incr);//#define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))由宏定义可以看出，又是把位号进行对齐。是按页数进行对齐，可以看到这位是属于哪个对齐内存页的。其实这一部是非常重要的。我在这里举个例子：假设，我们是从0页开始进行检测的，我们这里分两种情况。第一：当我们一上来就发现0号页是空闲的，我们可以拿来分配，这个是靠上条语句得来的。接着我们在这里对齐的时候，我们的‘i’还是0，这样我们就初步定下来在这个内存页内分配空间。如果我们的incr是4的话，我们就会通过下面的for来为我们对后面的1，2，3页进行测试是否空闲。第二种情况：如果我们等到1，2，3三者其中一页才检测到时空闲的话，我们来到这条语句的时候，会发现'i'会增加一个档位，如果对于incr=4时，i=4，这样我们就发现，如果发现连续4个页的第一个页并非空闲的话，我们就放弃这个档位（4页）
		if (i >= eidx)
			break;
		if (test_bit(i, bdata->node_bootmem_map))
			continue;
		for (j = i + 1; j < i + areasize; ++j) {//这里就是我上面提到的for循环，就是为了确保整个档位（4页）是空闲的，只要有一点瑕疵，就马上进行档位调整，如果顺利的话，我们就可以申请到我们需要的空间
			if (j >= eidx)
				goto fail_block;
			if (test_bit(j, bdata->node_bootmem_map))
				goto fail_block;
		}
		start = i;//修改一下巡查页号，进行下一轮修改
		goto found;
	fail_block:
		i = ALIGN(j, incr);
	}

	if (preferred > offset) {
		preferred = offset;
		goto restart_scan;
	}//这个if肯定会被执行的，peferred+=offset这条语句可以看出，我们不是从偏移首align开始检测是否有空闲空间的，这里我们从新scan时，是从offset的页号开始的，对于是PAGE_SIZE对齐格式，我们就会从0号开始！
	return NULL;

found:
	bdata->last_success = PFN_PHYS(start);//把这次成功分配的空闲空间的起始虚拟地址，这是地址是按页对齐的。
	BUG_ON(start >= eidx);//超过了指定的低端内存页数，这样系统会崩溃的

	/*
	 * Is the next page of the previous allocation-end the start
	 * of this allocation's buffer? If yes then we can 'merge'
	 * the previous partial page with this allocation.
	 */
	if (align < PAGE_SIZE &&
	    bdata->last_offset && bdata->last_pos+1 == start) {//先要清楚bdata->last_offset是上次分配成功空间的结束地址相对于其页的页内偏移量，如果结束地址刚好是按页对齐的话，last_offset=0。可以看出if里面的判断是说明对于小于PAGE_SIZE对齐方式的，如果上次成功分配空间的结束位置的所在页正好在start的上一页。
		offset = ALIGN(bdata->last_offset, align);//按align格式来对齐偏移量，对于对齐后是一页的大小时，就不能用这些剩余空间来为本次分配内存，只能用上面找到的本内存node的第start页开始。
		BUG_ON(offset > PAGE_SIZE);
		remaining_size = PAGE_SIZE - offset;//计算上次分配的内存最后页中能用于本次分配的空闲内存大小。
		if (size < remaining_size) {//如果本次分配size小于剩余空间的话，就执行以下语句。
			areasize = 0;//由于剩余的空间够本次的分配，则这次分配不用新的一页来分配了。
			/* last_pos unchanged */
			bdata->last_offset = offset + size;//重新更新最后地址相对于本页的偏移量。
			ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
					   offset +
					   bdata->node_boot_start);//bdata->last_pos是上次内存申请结束地址所在的页号（由于页号是从0号开始的），这样很明显括号里面求得的就是本次申请内存的起始物理地址，最后通过phys_to_virt宏定义求出虚拟地址。
		} else {//如果上次分配剩下的空间足以为本次分配所用。
			remaining_size = size - remaining_size;//计算还要多大的新的空闲内存空间。
			areasize = (remaining_size + PAGE_SIZE-1) / PAGE_SIZE;//看看需要多少页，不够一页也要算用一页。
			ret = phys_to_virt(bdata->last_pos * PAGE_SIZE +
					   offset +
					   bdata->node_boot_start);
			bdata->last_pos = start + areasize - 1;//重新统计本次申请空闲空间结束位置的所在页号。
			bdata->last_offset = remaining_size;
		}
		bdata->last_offset &= ~PAGE_MASK;//把last_offset转换成页内偏移量。
	} else {//如果对其值大于等于页大小，或者上次分配的内存的物理结束地址是按页对齐的，或是上次分配的内存的结束地址不在本次分配的起始空闲内存页start的前一页内。
		bdata->last_pos = start + areasize - 1;
		bdata->last_offset = size & ~PAGE_MASK;
		ret = phys_to_virt(start * PAGE_SIZE + bdata->node_boot_start);
	}

	/*
	 * Reserve the area now:
	 */
	for (i = start; i < start + areasize; i++)
		if (unlikely(test_and_set_bit(i, bdata->node_bootmem_map)))
			BUG();//对本次的申请的空间的每页对应的页帧位码表中的每一位都置1，如果本身就是1的话，系统崩溃。
	memset(ret, 0, size);//对申请的这段空间进行清零。
	return ret;
}