数据结构

1．虚拟内存

1-虚拟内存区域的主要成员

区域虚拟内存区域是分配给进程的一个虚拟地址范围，内核使用结构体vm_area_struct描述虚拟内存区域，虚拟内存区域的主要成员如表所示。

2-文件映射的虚拟内存区域

文件映射的虚拟内存区域如图所示。

• （1）成员vm_file指向文件的一个打开实例（file）。索引节点代表一个文件，描述文件的属性。

• （2）成员vm_pgoff存放文件的以页为单位的偏移。

• （3）成员vm_ops指向虚拟内存操作集合，创建文件映射的时候调用文件操作集合中的mmap方法（file->f_op->mmap）以注册虚拟内存操作集合。
  例如：假设文件属于EXT4文件系统，文件操作集合中的mmap方法是函数ext4_file_mmap，该函数把虚拟内存区域的成员vm_ops设置为ext4_file_vm_ops。

3-共享匿名映射的虚拟内存区域

共享匿名映射的虚拟内存区域如图所示，共享匿名映射的实现原理和文件映射相同，区别是共享匿名映射关联的文件是内核创建的内部文件。

在内存文件系统tmpfs中创建一个名为“/dev/zero”的文件，名字没有意义，创建两个共享匿名映射就会创建两个名为“/dev/zero”的文件，两个文件是独立的，毫无关系。

• （1）成员vm_file指向文件的一个打开实例（file）。
• （2）成员vm_pgoff存放文件的以页为单位的偏移。
• （3）成员vm_ops指向共享内存的虚拟内存操作集合shmem_vm_ops。

4-私有匿名映射的虚拟内存区域

私有匿名映射的虚拟内存区域如图所示。

• ❑ 成员vm_file没有意义，是空指针。

• ❑ 成员vm_pgoff没有意义。

• ❑ 成员vm_ops是空指针。

1、页保护位（vm_area_struct.vm_page_prot）

（1）页保护位（vm_area_struct.vm_page_prot）：描述虚拟内存区域的访问权限。内核定义了一个保护位映射数组，把VM_READ、VM_WRITE、VM_EXEC和VM_SHARED这4个标志转换成保护位组合。

每种处理器架构需要定义__P000到__S111的宏，P代表私有（Private）, S代表共享（Shared），后面的3个数字分别表示可读、可写和可执行，例如__P000表示私有、不可读、不可写和不可执行，__S111表示共享、可读、可写和可执行。

    mm/mmap.c
    pgprot_t protection_map[16] = {
        __P000, __P001, __P010, __P011, __P100, __P101, __P110, __P111,
        __S000, __S001, __S010, __S011, __S100, __S101, __S110, __S111
    };
    pgprot_t vm_get_page_prot(unsigned long vm_flags)
    {
        return __pgprot(pgprot_val(protection_map[vm_flags &
                    (VM_READ|VM_WRITE|VM_EXEC|VM_SHARED)]) |
                  pgprot_val(arch_vm_get_page_prot(vm_flags)));
    }

函数arch_vm_get_page_prot由每种处理器架构自定义，默认的实现如下：

    include/linux/mman.h
    #ifndef arch_vm_get_page_prot
    #define arch_vm_get_page_prot(vm_flags) __pgprot(0)
    #endif

2、虚拟内存区域标志

（2）虚拟内存区域标志：结构体vm_area_struct的成员vm_flags存放虚拟内存区域的标志，头文件“include/linux/mm.h”定义了各种标志，常用的标志如下。

• 1）VM_READ、VM_WRITE、VM_EXEC和VM_SHARED分别表示可读、可写、可执行和可以被多个进程共享。

• 2）VM_MAYREAD表示允许设置VM_READ, VM_MAYWRITE表示允许设置VM_WRITE, VM_MAYEXEC表示允许设置VM_EXEC, VM_MAYSHARE表示允许设置VM_SHARED。这4个标志用来限制系统调用mprotect可以设置的访问权限。

• 3）VM_GROWSDOWN表示虚拟内存区域可以向下（低的虚拟地址）扩展，VM_GROWSUP表示虚拟内存区域可以向上（高的虚拟地址）扩展。VM_STACK表示虚拟内存区域是栈，绝大多数处理器的栈是向下扩展，VM_STACK等价于VM_GROWSDOWN；少数处理器（例如PA-RISC处理器）的栈是向上扩展，VM_STACK等价于VM_GROWSUP。

• 4）VM_PFNMAP表示页帧号（Page Frame Number, PFN）映射，特殊映射不希望关联页描述符，直接使用页帧号，可能是因为页描述符不存在，也可能是因为不想使用页描述符。

• 5）VM_MIXEDMAP表示映射混合使用页帧号和页描述符。

• 6）VM_LOCKED表示页被锁定在内存中，不允许换出到交换区。

• 7）VM_SEQ_READ表示进程从头到尾按顺序读一个文件，VM_RAND_READ表示进程随机读一个文件。这两个标志用来提示文件系统，如果进程按顺序读一个文件，文件系统可以预读文件，提高性能。

• 8）VM_DONTCOPY表示调用fork以创建子进程时不把虚拟内存区域复制给子进程。

• 9）VM_DONTEXPAND表示不允许使用mremap()扩大虚拟内存区域。

• 10）VM_ACCOUNT表示虚拟内存区域需要记账，判断所有进程申请的虚拟内存的总和是否超过物理内存容量。

• 11）VM_NORESERVE表示不需要预留物理内存。

• 12）VM_HUGETLB表示虚拟内存区域使用标准巨型页。

• 13）VM_ARCH_1和VM_ARCH_2由各种处理器架构自定义。

• 14）VM_HUGEPAGE表示虚拟内存区域允许使用透明巨型页，VM_NOHUGEPAGE表示虚拟内存区域不允许使用透明巨型页。

• 15）VM_MERGEABLE表示KSM（内核相同页合并，Kernel Samepage Merging）可以合并数据相同的页。

3、虚拟内存操作集合

（3）虚拟内存操作集合（vm_operations_struct）：定义了虚拟内存区域的各种操作方法，其代码如下。

    include/linux/mm.h
    struct vm_operations_struct {
          void (*open)(struct vm_area_struct * area);
          void (*close)(struct vm_area_struct * area);
          int (*mremap)(struct vm_area_struct * area);
          int (*fault)(struct vm_fault *vmf);
          int (*huge_fault)(struct vm_fault *vmf, enum page_entry_size pe_size);
          void (*map_pages)(struct vm_fault *vmf,
                  pgoff_t start_pgoff, pgoff_t end_pgoff);
         /* 通知以前的只读页即将变成可写，
          * 如果返回一个错误，将会发送信号SIGBUS给进程*/
          int (*page_mkwrite)(struct vm_fault *vmf);
         /* 使用VM_PFNMAP或者VM_MIXEDMAP时调用，功能和page_mkwrite相同*/
          int (*pfn_mkwrite)(struct vm_fault *vmf);
          …
    }

• 1）open方法：在创建虚拟内存区域时调用open方法，通常不使用，设置为空指针。
• 2）close方法：在删除虚拟内存区域时调用close方法，通常不使用，设置为空指针。
• 3）mremap方法：使用系统调用mremap移动虚拟内存区域时调用mremap方法。
• 4）fault方法：访问文件映射的虚拟页时，如果没有映射到物理页，生成缺页异常，异常处理程序调用fault方法来把文件的数据读到文件的页缓存中。
• 5）huge_fault方法：和fault方法类似，区别是huge_fault方法针对使用透明巨型页的文件映射。
• 6）map_pages方法：读文件映射的虚拟页时，如果没有映射到物理页，生成缺页异常，异常处理程序除了读入正在访问的文件页，还会预读后续的文件页，调用map_pages方法在文件的页缓存中分配物理页。
• 7）page_mkwrite方法：第一次写私有的文件映射时，生成页错误异常，异常处理程序执行写时复制，调用page_mkwrite方法以通知文件系统页即将变成可写，以便文件系统检查是否允许写，或者等待页进入合适的状态。
• 8）pfn_mkwrite方法：和page_mkwrite方法类似，区别是pfn_mkwrite方法针对页帧号映射和混合映射。

2．链表和树

如图所示，进程的虚拟内存区域按两种方法排序。

• （1）双向链表，mm_struct.mmap指向第一个vm_area_struct实例。

• （2）红黑树，mm_struct.mm_rb指向红黑树的根。

虚拟内存区域使用起始地址和结束地址描述，链表按起始地址递增排序。红黑树是平衡的二叉查找树，按起始地址排序，使用红黑树有以下好处。

• （1）在红黑树中查找一个虚拟内存区域的速度快。

• （2）增加一个新的区域时，先在红黑树中找到刚好在新区域前面的区域，然后向链表和树中插入新区域，可以避免扫描链表。

内容来自前辈书籍：《Linux内核深度解析》