2017-07-09
今天周末，闲来无事聊聊linux内核内存分配那点事……重点在于分析vmalloc的执行 流程
以传统x86架构为例，内核空间内存（3G-4G）主要分为三大部分：DMA映射区，一致映射区、高端内存区。其中前两者占据低端892M，而剩下的128M作为高端内存区。DMA映射区涉及到外部设备，咱们暂且不讨论，那么就剩下一致映射区和高端内存区。一致映射区的虚拟地址均一一对应了物理页框，因此此区间虚拟地址的访问可以直接通过偏移量得到物理内存而不需进行页表的转换。但是1G内核地址空间说实话有些捉襟见肘，如果都用作一致映射，那么当物理内存大于4G时，内核仍然无法利用。鉴于此，留下128M的地址空间作为高端内存，扮演着临时映射的作用。回想下PAE模式的原理，是不是有些相似呢？一致映射区既然都已经关联了物理内存就可以通过slab缓存来管理，以加速分配。而高端内存这点有些类似于用户进程的内存分配，但又并不完全相同，后面咱们会讲到。在这里咱们先回忆下用户空间内存分配流程，一个普通的进程调用malloc函数分配一段地址空间，有可能在 堆中，如果内存过大海有可能在mmap映射区，同时会由一个vm_area_struct记录下本次分配出去的地址空间信息，如大小，起始地址等由于进程独享虚拟地址空间，所以这些vm_area_struct都是按照进程为单位进行管理的。这也没毛病。此时仅仅是在进程管理虚拟内存的数据结构中记录了下这块虚拟地址空间被分配出去了，然而此时和物理内存还没管理，在真正发生读写的时候就会分配物理内存、填充页表。然而在内核中，所有进程共享唯一的内核地址空间，所以内核地址空间需要统一管理。
下面我们根据源码分析下vmalloc的具体流程
void *vmalloc(unsigned long size)
{
return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL);
}
该函数直接封装了__vmalloc_node，而__vmalloc_node又封装了__vmalloc_node_range，我们直接从__vmalloc_node_range函数看起
void *__vmalloc_node_range(unsigned long size, unsigned long align,
unsigned long start, unsigned long end, gfp_t gfp_mask,
pgprot_t prot, int node, const void *caller)
{
struct vm_struct *area;
void *addr;
unsigned long real_size = size; size = PAGE_ALIGN(size);
if (!size || (size >> PAGE_SHIFT) > totalram_pages)
goto fail;
/*在高端内存区分配一个vm_struct并初始化*/
area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNLIST,
start, end, node, gfp_mask, caller);
if (!area)
goto fail;
/*为area分配管理page的数组，并通过伙伴系统分配物理页面*/
addr = __vmalloc_area_node(area, gfp_mask, prot, node, caller);
if (!addr)
return NULL; /*
* In this function, newly allocated vm_struct has VM_UNLIST flag.
* It means that vm_struct is not fully initialized.
* Now, it is fully initialized, so remove this flag here.
*/
clear_vm_unlist(area); /*
* A ref_count = 3 is needed because the vm_struct and vmap_area
* structures allocated in the __get_vm_area_node() function contain
* references to the virtual address of the vmalloc'ed block.
*/
kmemleak_alloc(addr, real_size, , gfp_mask); return addr; fail:
warn_alloc_failed(gfp_mask, ,
"vmalloc: allocation failure: %lu bytes\n",
real_size);
return NULL;
}
前面说和用户空间进程分配内存类似的点就在于高端内存区的管理同样需要数据结构，和用户空间对应，内核使用vm_struct。只是内核所有的vm_struct放在一起，与单个进程无关。该函数中首先对size进行了页面对齐设置，然后检测size的合法性。这都不需多说。接着调用__get_vm_area_node分配一个vm_struct结构，然后调用__vmalloc_area_node分配一个管理page结构的数组，并通过伙伴系统，分配物理页面并填充该数组。由此可见，高端内存区的分配和用户空间进程的不同之处，就是这里并不是等待访问的时候分配物理内存，而是在分配的时候就进行了填充。
__get_vm_area_node
static struct vm_struct *__get_vm_area_node(unsigned long size,
unsigned long align, unsigned long flags, unsigned long start,
unsigned long end, int node, gfp_t gfp_mask, const void *caller)
{
struct vmap_area *va;
struct vm_struct *area;
/*不能处于中断上下文*/
BUG_ON(in_interrupt());
if (flags & VM_IOREMAP) {
int bit = fls(size);
if (bit > IOREMAP_MAX_ORDER)
bit = IOREMAP_MAX_ORDER;
else if (bit < PAGE_SHIFT)
bit = PAGE_SHIFT;
align = 1ul << bit;
}
size = PAGE_ALIGN(size);
if (unlikely(!size))
return NULL;
/*分配一个vm_struct结构*/
area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
if (unlikely(!area))
return NULL；
/*
* We always allocate a guard page.
*/
size += PAGE_SIZE;
/*分配一块虚拟地址空间*/
va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
if (IS_ERR(va)) {
kfree(area);
return NULL;
}
/*
* When this function is called from __vmalloc_node_range,
* we add VM_UNLIST flag to avoid accessing uninitialized
* members of vm_struct such as pages and nr_pages fields.
* They will be set later.
*/
if (flags & VM_UNLIST)
/*初始化area*/
setup_vmalloc_vm(area, va, flags, caller);
else
insert_vmalloc_vm(area, va, flags, caller); return area;
}
该函数完成vm_struct结构的分配并初始化，开始便判断是否处于中断上下文，在中断上下文有可能会出问题，因为物理页面的获取并不能保证一定可以立刻得到，如果物理页面不足会造成睡眠，而中断上下文是不能睡眠的。IOREMAP的情况我们不考虑先，再次对size进行页面对齐，实际上前面已经设置过了，然后调用了kzalloc_node函数得到一个结构，这里为何不用slab缓存？？有可能是vmalloc并不会频繁的执行（猜想）。然后size加了一个page的大小主要做各个区间之间的隔离。接着调用alloc_vmap_area函数在虚拟地址空间分配一段空间，这点就类似于我们在用户空间通过malloc函数分配了，仅仅分配虚拟地址空间。内核中一段虚拟地址空间通过vmap_area管理，分配完成后通过setup_vmalloc_vm利用vmap_area对vm_struct进行初始化。
__vmalloc_area_node
static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
pgprot_t prot, int node, const void *caller)
{
const int order = ;
struct page **pages;
unsigned int nr_pages, array_size, i;
gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
/*需要分配的页面数量*/
nr_pages = (area->size - PAGE_SIZE) >> PAGE_SHIFT;
/*需要一个数组管理涉及到的物理页面地址即page指针，这个数组的大小*/
array_size = (nr_pages * sizeof(struct page *)); area->nr_pages = nr_pages;
/* Please note that the recursion is strictly bounded. */
/*如果数组的大小大于一个页面*/
if (array_size > PAGE_SIZE) {
pages = __vmalloc_node(array_size, , nested_gfp|__GFP_HIGHMEM,
PAGE_KERNEL, node, caller);
area->flags |= VM_VPAGES;
} else {
pages = kmalloc_node(array_size, nested_gfp, node);
}
area->pages = pages;
area->caller = caller;
if (!area->pages) {
remove_vm_area(area->addr);
kfree(area);
return NULL;
} for (i = ; i < area->nr_pages; i++) {
struct page *page;
gfp_t tmp_mask = gfp_mask | __GFP_NOWARN; if (node < )
page = alloc_page(tmp_mask);
else
page = alloc_pages_node(node, tmp_mask, order); if (unlikely(!page)) {
/* Successfully allocated i pages, free them in __vunmap() */
area->nr_pages = i;
goto fail;
}
area->pages[i] = page;
}
if (map_vm_area(area, prot, &pages))
goto fail;
return area->addr;
fail:
warn_alloc_failed(gfp_mask, order,
"vmalloc: allocation failure, allocated %ld of %ld bytes\n",
(area->nr_pages*PAGE_SIZE), area->size);
vfree(area->addr);
return NULL;
}
这段代码倒没有什么难度，首先根据实际的虚拟地址空间大小计算页面数量，然后计算page指针数组的大小，如果在一个页面以内，就在一致映射区直接分配，这样更快。如果大于一个page，就 还在高端内存区分配。之后在vm_struct和pages数组建立关联，当然如果page指针数组没分配好则及时返回。如果一切OK，则进入一个循环，为每个虚拟页框分配物理页面，这里只是分配了和虚拟页面数组相等的物理页面，并没有建立关联，如果指定了分配节点（ＮＵＭＡ下），则从指定的节点分配，否则默认从当前节点分配。到这里我们又可以发现高端内存区的内存分配和一致映射区内存分配不同之处，就是高端内存区虚拟地址空间连续的，而对应的物理地址空间却是离散的。一致映射区都是连续的。在分配好物理页面后就调用map_vm_area为页面建立映射，这个过程就是填充页表的过程，我们就不深入看了。
内核中高端内存的管理
如前所述，内核地址空间的分配通过vm_struct结构管理，该结构类似于进程地址空间的vm_area_struct结构。不同的是由于所有进程共享内核地址空间，内核中所有vm_struct放在一起管理，构成一条链表。同时，内核把负责具体映射的j信息抽离成一个结构vmap_area，该结构在内核通过红黑树和双向链表管理,在此之前我们先看下vm_struct和vmap_area结构，
struct vm_struct {
struct vm_struct *next;
void *addr;
unsigned long size;
unsigned long flags;
struct page **pages;
unsigned int nr_pages;
phys_addr_t phys_addr;
const void *caller;
};
所有的vm_struct通过next链接，addr为该区间的地址地址，size为该区间的大小，flags是一些标志位，page是一个page指针数组，记录该区间映射的所有物理页面，nr_pages记录该区间包含的页面数量，caller是一个函数指针__builtin_return_address(0)，这个玩意暂时不太了解。
struct vmap_area {
unsigned long va_start;//区间的起始地址
unsigned long va_end;//区间的结束地址
unsigned long flags;//标志位
struct rb_node rb_node; /*红黑树节点*/ /* address sorted rbtree */
struct list_head list; /*链表节点*/ /* address sorted list */
struct list_head purge_list; /* "lazy purge" list */
struct vm_struct *vm;
struct rcu_head rcu_head;
};
具体地址空间的管理是通过vmap_area管理的，该结构记录整个区间的起始和结束，相关字段上面已经解释的比较清楚，这里就不多说。管理vmap_area结构的红黑树根节点为全局变量vmap_area_root，双链表头结点为vmap_area_list。下面我们看一下分配具体空间的函数alloc_vmap_area，还是分段分析
struct vmap_area *va;
struct rb_node *n;
unsigned long addr;
int purged = ;
struct vmap_area *first; BUG_ON(!size);
BUG_ON(size & ~PAGE_MASK);
BUG_ON(!is_power_of_2(align)); va = kmalloc_node(sizeof(struct vmap_area),
gfp_mask & GFP_RECLAIM_MASK, node);
if (unlikely(!va))
return ERR_PTR(-ENOMEM);
开头是一些验证，size不能为0，必须是页面对齐的，而且必须是2的指数。满足条件就通过kmalloc_node分配一个vmap_area结构，基于内核地址空间共享特性，vmap_area需要加锁操作。为了加速查找可用的空间，这里涉及到两个静态变量cached_hole_size和free_vmap_cache。从代码来看free_vmap_cache是上次分配出去的vmap_area的红黑树节点，而cached_hole_size是free_vmap_cache最大的空洞。在红黑树和链表中，vmap_area都是有序排列的。
if (!free_vmap_cache ||
size < cached_hole_size ||
vstart < cached_vstart ||
align < cached_align) {
nocache:
cached_hole_size = ;
free_vmap_cache = NULL;
}
/* record if we encounter less permissive parameters */
cached_vstart = vstart;
cached_align = align;
如果free_vmap_cache为空，或者在free_vmap_cache存在size大于请求分配空间的大小，又或者请求分配的起始地址小于cached_vstart，或者要求的对齐大小小于cached_align，则就不利用cache，这时设置cached_hole_size=0，free_vmap_cache=NULL，然后更新cached_vstart和cached_align
if (free_vmap_cache) {
first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
addr = ALIGN(first->va_end, align);
if (addr < vstart)
goto nocache;
if (addr + size - < addr)
goto overflow;
} else {
addr = ALIGN(vstart, align);
if (addr + size - < addr)
goto overflow;
n = vmap_area_root.rb_node;
first = NULL;
/*遍历红黑树*/
while (n) {
struct vmap_area *tmp;
tmp = rb_entry(n, struct vmap_area, rb_node);
/**/
if (tmp->va_end >= addr) {
first = tmp;
if (tmp->va_start <= addr)
break;
n = n->rb_left;
} else
n = n->rb_right;
}
if (!first)
goto found;
}
如果free_vmap_cache存在，则设置first节点为free_vmap_cache代表的vmap_area，该vmap_area代表区间的结束地址要大于等于vstart才可以称作是first。不满足条件只能设置no_cache，然后从头遍历了。而如果free_vmap_cache不存在，则从vstart设置对齐后的地址为起始地址开始遍历红黑树，有可能得到两种结果1、找到一个vmap_area，其代表区间的结束地址要大于等于vstart并且起始地址小于等于vstart，就找到了first节点。2、vstart地址大于红黑树中所有节点的结束地址，起始就是vstart在已经分配的最大的地址后面，那这样就不用遍历了，直接满足条件。
如果是第一种情况，则需要从first节点往后遍历，这个过程会更新cached_hole_size，从代码看是一直遍历到链表最后，如果剩余的空间足够分配，则成功，否则失败。不太明白的是从头开始遍历并没有想到利用最大空洞，而是总是遍历到最后，这点着实不解。
找到之后就设置vmap_area的相关记录信息，并调用__insert_vmap_area插入到红黑树和链表中。
以马内利！
参考资料：
linux内核源码