Read the fucking source code! --By 鲁迅
A picture is worth a thousand words. --By 高尔基
说明：
Kernel版本：4.14
ARM64处理器，Contex-A53，双核
使用工具：Source Insight 3.5， Visio
1. 概述在之前的系列文章中，分析到了Buddy System的页框分配，Slub分配器的小块内存对象分配，这些分配的地址都是物理内存连续的。当内存碎片后，连续物理内存的分配就会变得困难，可以使用vmap机制，将不连续的物理内存页框映射到连续的虚拟地址空间中。vmalloc的分配就是基于这个机制来实现的。
还记得下边这张图吗？
vmap/vmalloc的区域就是在VMALLOC_START ~ VMALLOC_END之间。
开启探索之旅吧。
2. 数据结构 2.1 vmap_area/vm_struct这两个数据结构比较简单，直接上代码：
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; }; 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 llist_node purge_list; /* "lazy purge" list */ struct vm_struct *vm; struct rcu_head rcu_head; };struct vmap_area用于描述一段虚拟地址的区域，从结构体中va_start/va_end也能看出来。同时该结构体会通过rb_node挂在红黑树上，通过list挂在链表上。
struct vmap_area中vm字段是struct vm_struct结构，用于管理虚拟地址和物理页之间的映射关系，可以将struct vm_struct构成一个链表，维护多段映射。
关系如下图：
红黑树，本质上是一种二叉查找树，它在二叉查找树的基础上增加了着色相关的性质，提升了红黑树在查找，插入，删除时的效率。在红黑树中，节点已经进行排序，对于每个节点，左侧的的元素都在节点之前，右侧的元素都在节点之后。
红黑树必须满足以下四条规则：
每个节点不是红就是黑；
红黑树的根必须是黑；
红节点的子节点必须为黑；
从节点到子节点的每个路径都包含相同数量的黑节点，统计黑节点个数时，空指针也算黑节点；
定义如下：
struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */由于内核会频繁的进行vmap_area的查找，红黑树的引入就是为了解决当查找数量非常多时效率低下的问题，在红黑树中，搜索元素，插入，删除等操作，都会变得非常高效。至于红黑树的算法操作，本文就不再深入分析，知道它的用途即可。
3. vmap/vunmap分析 3.1 vmapvmap函数，完成的工作是，在vmalloc虚拟地址空间中找到一个空闲区域，然后将page页面数组对应的物理内存映射到该区域，最终返回映射的虚拟起始地址。
整体流程如下：
操作流程比较简单，来一个样例分析，就清晰明了了：
vmap调用中，关键函数为alloc_vmap_area，它先通过vmap_area_root二叉树来查找第一个区域first vm_area，然后根据这个first vm_area去查找vmap_area_list链表中满足大小的空间区域。
在alloc_vmap_area函数中，有几个全局的变量：
static struct rb_node *free_vmap_cache; static unsigned long cached_hole_size; static unsigned long cached_vstart; static unsigned long cached_align;用于缓存上一次分配成功的vmap_area，其中cached_hole_size用于记录缓存vmap_area对应区域之前的空洞的大小。缓存机制当然也是为了提高分配的效率。
3.2 vunmap