每个进程都拥有一段连续的虚拟地址空间，内核实际的使用情况并不是以整个地址空间为单位，而是将整个连续的空间划分为若干个内存区域，内核中使用vm_area_struct数据结构来表示，简称vma。当进程需要使用内存时，内核先为该进程分配一个合适大小的虚拟内存区域，此时并不立刻为此内存区域映射物理页框，而是一直延迟到进程不得不访问物理内存为止。

使用虚拟内存区域的另外一个好处便是可以将进程的所有信息按照类型进行区域划分。比如，进程二进制形式的代码对应一个内存区域，这个内存区域被特定的称为text段。进程包含的数据划分的更为细致，全局变量存储在被称为数据段的内存区域中，局部变量存储在栈所对应的内存区域，动态申请的数据存放在堆所对应的内存区域。另外，进程所需的库以及映射到进程地址空间中的文件也都对应着一个内存区域。

可以看出进程对内存区域的操作是十分频繁的，据此内核提供了各种对内存区域操作的函数，比如在一个进程的地址空间中删除一个区域或创建一个区域等。本文将分析几个常见的对虚拟内存区域操作的函数。

1.通过线性地址查找最临近的区域

内核中通常会有这样的操作需求：给定一个虚拟地址，查找该地址最临近的内存区域,find_vma()用来完成这样的操作。通常情况下，我们希望恰好找到该线性地址所属的内存区域。但是这种结果不会每次都发生，该线性地址有可能不属于当前已存在的任何内存区域，此时只需返回第一个终止地址大于该虚拟地址的内存区。如果没有符合上述要求的内存区，则直接返回空。因此，find_vma()找到的区域和线性地址addr的关系如下图：

一个进程的所有内存区域通过两种方式进行组织：双联表和红黑树。双联表易于遍历每个区域，红黑树则易于查找所需区域。find_vma()就是基于红黑树进行查找的，它传入两个参数，mm为进程的内存描述符，addr即为所查找的线性地址。该函数首先检查addr是否就在mmap_cache所指向的那个内存区域中，mmap_cache保存了进程最后一次所使用的虚拟内存区域描述符地址。根据程序的局部性原理，当前所查找的线性地址很可能就在刚刚所使用的那个内存区中，这样做可以避免由于查找而带来的系统开销。

如果addr没有在mmap_cache所指的内存区域中，接下来就开始从红黑树的根节点进行查找。内存区所对应的红黑树是以线性地址为键值的，既一个节点左孩子的线性地址均比该节点的线性地址小，而右节点都比该节点大。整体的查找过程是通过一个循环完成的，rb_node保存了每个内存区在红黑树中对应的节点，而vma_tmp则暂存当前红黑树节点对应的内存区描述符。红黑树的根节点通过内存描述符中rb_root字段获得，在接下来的查找过程中，如何根据红黑树节点得到对应的内存区描述符？这里通过rb_entry()获得。该函数类似list_entry()，既利用vm_area_struct结构中vm_rb字段的指针获取整个结构体的指针。

根据红黑树的特点，如果当前的vma的终止地址大于addr，再进一步检查vma的起始地址是否小于addr。如果起始地址小于addr则说明查找成功，退出循环，否则继续向左查找。如果vma的终止地址小于addr，则向右搜索。最后，将找到的vma再次保存到mmap_cache中。

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
        struct vm_area_struct *vma = NULL;

        if (mm) {
                vma = mm->mmap_cache;
                if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
                        struct rb_node * rb_node;

                        rb_node = mm->mm_rb.rb_node;
                        vma = NULL;

                        while (rb_node) {
                                struct vm_area_struct * vma_tmp;

                                vma_tmp = rb_entry(rb_node,
                                                struct vm_area_struct, vm_rb);

                                if (vma_tmp->vm_end > addr) {
                                        vma = vma_tmp;
                                        if (vma_tmp->vm_start <= addr)
                                                break;
                                        rb_node = rb_node->rb_left;
                                } else
                                        rb_node = rb_node->rb_right;
                        }
                        if (vma)
                                mm->mmap_cache = vma;
                }
        }
        return vma;
}

2.获取一个空闲的内存区域

每个进程都将已使用的内存区域通过双联表链接在一起，该链表的头指针为mmap。如果进程要申请一个新的内存区域，则必须先查找一个空闲的内存区间，此时就会用到get_unmapped_area()函数。该函数实现的思想很简单，通过遍历内存区域双联表查找一个符合指定大小的空闲区间，如果指定了起始地址，则从该起始地址开始查找。

该函数首先要检查len的合法性，如果它超过了TASK_SIZE的大小，则直接返回内存不足的错误信息。如果flags设置了MAP_FIXED标志，则表示以固定的地址开始创建线性区，因此立即返回该线性地址。

上述两种情况都不满足时，该函数对addr再做进一步判断。它先将addr调整成页大小的倍数，再通过addr查找临近的内存区vma。如果addr是空闲区首地址并且返回给调用函数，那么它首先必须满足addr+len不会超过进程用户空间的上限TASK_SIZE（其值为3GB）。在此条件成立的基础上有两种情况，第一，如果通过addr查找临近的vma为空，则查找成功。也就是说addr之后并不存在任何的内存区域，则addr到addr+len之间的地址空间都是空闲可用的。第二，当addr+len并没有超过vma的起始地址时，也是指定起始地址查找成功的一种情况。这种情况表示所查找到的内存区间位于vma之前的空洞中。

unsigned long
arch_get_unmapped_area(struct file *filp, unsigned long addr,
                unsigned long len, unsigned long pgoff, unsigned long flags)
{
        struct mm_struct *mm = current->mm;
        struct vm_area_struct *vma;
        unsigned long start_addr;

        if (len > TASK_SIZE)
                return -ENOMEM;

        if (flags & MAP_FIXED)
                return addr;

        if (addr) {
                addr = PAGE_ALIGN(addr);
                vma = find_vma(mm, addr);
                if (TASK_SIZE - len >= addr &&
                    (!vma || addr + len <= vm_start))
                        return addr;
        }

上述两种情况的实例图如下：

如果没有指定起始地址，则接下来通过链表查找空闲区间。虽然我们上面说过通过遍历内存区域双联表可以查找一个指定大小的空闲区间，但实际的操作并不是每次都从头遍历到尾，该函数采用缓存机制节约搜索时间。这里首先要介绍一下进程地址空间中的空洞，mmap链表中相邻两个内存区之间的空闲区域就形成一个空洞。free_area_cache和cached_hole_size都是内存描述符中的字段，它们共同描述进程地址空间中的一个空洞，该空洞比较特殊，它位于最近刚分配的内存区之后，以free_area_cache为起始地址，以cached_hole_size为长度。

如果len大于当前空洞大小，也就是说free_area_cache所缓存的空洞太小，那么就从当前这个空洞开始继续查找更大范围的空洞；反之，当len大于当前空洞大小时，并不是立刻就从此空洞中分配所需大小的空闲区，而是从TASK_UNMAPPED_BASE开始重新查找。这种机制是为了防止产生越来越多更小范围的空洞，这种小空洞很难被再次利用。

        if (len > mm->cached_hole_size) {
                start_addr = addr = mm->free_area_cache;
        } else {
                start_addr = addr = TASK_UNMAPPED_BASE;
                mm->cached_hole_size = 0;
        }

下面开始进行完全搜索，如果addr+len已经超出进程用户空间的上限并且此次搜索并不是从TASK_UNMAPPED_BASE开始的，那么从TASK_UNMAPPED_BASE处重新进行新一轮的搜索，并且相应的更新start_addr和cached_hole_size的值。如果此次搜索的确是从TASK_UNMAPPED_BASE开始的，那么说明搜索失败，没有指定大小的空闲区间。

full_search:
        for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
                if (TASK_SIZE - len < addr) {
                        if (start_addr != TASK_UNMAPPED_BASE) {
                                addr = TASK_UNMAPPED_BASE;
                                start_addr = addr;
                                mm->cached_hole_size = 0;
                                goto full_search;
                        }
                        return -ENOMEM;
                }

如果addr+len在进程的用户空间范围内，那么有两种情况是可以成功搜索到空闲区间的。第一，当vma为空时，则搜索成功；第二，vma之前的空洞可以满足len大小，则搜索成功。不管那种情况，此时都要更新free_area_cache以便后续查找操作的使用，即下一次的查找就是从addr+len之后的空洞开始。最后返回空闲区的起始地址addr。

                if (!vma || addr + len vm_start) {
                        mm->free_area_cache = addr + len;
                        return addr;
                }

上述情况不满足时，也就是当前vma前的空洞太小时，就从当前vma的终止地址开始继续查找。不错在这之前，还要更新cached_hole_size。

                if (addr + mm->cached_hole_size < vma->vm_start)
                        mm->cached_hole_size = vma->vm_start - addr;
                addr = vma->vm_end;
        }
}