背景
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 构成一个链表, 维护多段映射.
关系如下图:
2.2 红黑树
红黑树, 本质上是一种二叉查找树, 它在二叉查找树的基础上增加了着色相关的性质, 提升了红黑树在查找, 插入, 删除时的效率. 在红黑树中, 节点已经进行排序, 对于每个节点, 左侧的的元素都在节点之前, 右侧的元素都在节点之后.
红黑树必须满足以下四条规则:
每个节点不是红就是黑;
红黑树的根必须是黑;
红节点的子节点必须为黑;
从节点到子节点的每个路径都包含相同数量的黑节点, 统计黑节点个数时, 空指针也算黑节点;
定义如下:
- 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 vmap
vmap 函数, 完成的工作是, 在 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
vunmap 执行的是跟 vmap 相反的过程: 从 vmap_area_root/vmap_area_list 中查找 vmap_area 区域, 取消页表映射, 再从 vmap_area_root/vmap_area_list 中删除掉 vmap_area, 页面返还给伙伴系统等. 由于映射关系有改动, 因此还需要进行 TLB 的刷新, 频繁的 TLB 刷新会降低性能, 因此将其延迟进行处理, 因此称为 lazy tlb.
来看看逆过程的流程:
4. vmalloc/vfree 分析
4.1 vmalloc
vmalloc 用于分配一个大的连续虚拟地址空间, 该空间在物理上不连续的, 因此也就不能用作 DMA 缓冲区. vmalloc 分配的线性地址区域, 在文章开头的图片中也描述了: VMALLOC_START ~ VMALLOC_END.
直接分析调用流程:
从过程中可以看出, vmalloc 和 vmap 的操作, 大部分的逻辑操作是一样的, 比如从 VMALLOC_START ~ VMALLOC_END 区域之间查找并分配 vmap_area, 比如对虚拟地址和物理页框进行映射关系的建立. 不同之处, 在于 vmap 建立映射时, page 是函数传入进来的, 而 vmalloc 是通过调用 alloc_page 接口向 Buddy System 申请分配的.
vmalloc VS kmalloc
到现在, 我们应该能清楚 vmalloc 和 kmalloc 的差异了吧, kmalloc 会根据申请的大小来选择基于 slub 分配器或者基于 Buddy System 来申请连续的物理内存. 而 vmalloc 则是通过 alloc_page 申请 order = 0 的页面, 再映射到连续的虚拟空间中, 物理地址不连续, 此外 vmalloc 可以休眠, 不应在中断处理程序中使用.
与 vmalloc 相比, kmalloc 使用
ZONE_DMA 和 ZONE_NORMAL
空间, 性能更快, 缺点是连续物理内存空间的分配容易带来碎片问题, 让碎片的管理变得困难.
4.2 vfree
直接上代码:
- void vfree(const void *addr)
- {
- BUG_ON(in_nmi());
- kmemleak_free(addr);
- if (!addr)
- return;
- if (unlikely(in_interrupt()))
- __vfree_deferred(addr);
- else
- __vunmap(addr, 1);
- }
如果在中断上下文中, 则推迟释放, 否则直接调用__vunmap, 所以它的逻辑基本和 vunmap 一致, 不再赘述了.
来源: https://www.cnblogs.com/LoyenWang/p/11965787.html