深入解析Linux内存管理.ppt

深入解析Linux内存管理,季丹,目录,预备知识页表管理内核页表物理内存高端内存地址映射虚拟内存地址空间高速缓存页框回收交换机制缺页异常共享内存文件映射程序执行,预备知识,微机原理内存芯片AT&T汇编保护模式脚本链接内核架构,页表管理,1.逻辑地址转线性地址2.线性地址转物理地址,逻辑地址转线性地址,机器语言指令中出现的内存地址，都是逻辑地址，需要转换成线性地址，再经过MMU(CPU中的内存管理单元)转换成物理地址才能够被访问到。我们写个最简单的hello world程序，用gccs编译，再反编译后会看到以下指令：mov 0 x80495b0,%eax这里的内存地址0 x80495b0 就是一个逻辑地址，必须加上隐含的DS 数据段的基地址，才能构成线性地址。也就是说 0 x80495b0 是当前任务的DS数据段内的偏移。在x86保护模式下，段的信息（段基线性地址、长度、权限等）即段描述符占8个字节，段信息无法直接存放在段寄存器中（段寄存器只有2字节）。Intel的设计是段描述符集中存放在GDT或LDT中，而段寄存器存放的是段描述符在GDT或LDT内的索引值(index)。Linux中逻辑地址等于线性地址。为什么这么说呢？因为Linux所有的段（用户代码段、用户数据段、内核代码段、内核数据段）的线性地址都是从 0 x00000000 开始，长度4G，这样 线性地址=逻辑地址+0 x00000000，也就是说逻辑地址等于线性地址了。,逻辑地址转线性地址,这样的情况下Linux只用到了GDT，不论是用户任务还是内核任务，都没有用到LDT。GDT的第12和13项段描述符是 _KERNEL_CS 和_KERNEL_DS，第14和15项段描述符是 _USER_CS 和_USER_DS。内核任务使用_KERNEL_CS 和_KERNEL_DS，所有的用户任务共用_USER_CS 和_USER_DS，也就是说不需要给每个任务再单独分配段描述符。内核段描述符和用户段描述符虽然起始线性地址和长度都一样，但DPL(描述符特权级)是不一样的。_KERNEL_CS 和_KERNEL_DS 的DPL值为0（最高特权），_USER_CS 和_USER_DS的DPL值为3。用gdb调试程序的时候，用info reg 显示当前寄存器的值：cs 0 x73 115ss 0 x7b 123ds 0 x7b 123es 0 x7b 123可以看到ds值为0 x7b,转换成二进制为 00000000 01111011，TI字段值为0,表示使用GDT，GDT索引值为 01111，即十进制15，对应的就是GDT内的_USER_DATA 用户数据段描述符。从上面可以看到，Linux在x86的分段机制上运行，却通过一个巧妙的方式绕开了分段。Linux主要以分页的方式实现内存管理。,线性地址转物理地址,前面说了Linux中逻辑地址等于线性地址，那么线性地址怎么对应到物理地址呢？这个大家都知道，那就是通过分页机制，具体的说，就是通过页表查找来对应物理地址。准确的说分页是CPU提供的一种机制，Linux只是根据这种机制的规则，利用它实现了内存管理。在保护模式下，控制寄存器CR0的最高位PG位控制着分页管理机制是否生效，如果PG=1，分页机制生效，需通过页表查找才能把线性地址转换物理地址。如果PG=0，则分页机制无效，线性地址就直接做为物理地址。分页的基本原理是把内存划分成大小固定的若干单元，每个单元称为一页（page），每页包含4k字节的地址空间（为简化分析，我们不考虑扩展分页的情况）。这样每一页的起始地址都是4k字节对齐的。为了能转换成物理地址，我们需要给CPU提供当前任务的线性地址转物理地址的查找表，即页表(page table)。注意，为了实现每个任务的平坦的虚拟内存，每个任务都有自己的页目录表和页表。为了节约页表占用的内存空间，x86将线性地址通过页目录表和页表两级查找转换成物理地址。,线性地址转物理地址,为了节约页表占用的内存空间，x86将线性地址通过页目录表和页表两级查找转换成物理地址。32位的线性地址被分成3个部分：最高10位 Directory 页目录表偏移量，中间10位 Table是页表偏移量，最低12位Offset是物理页内的字节偏移量。页目录表的大小为4k（刚好是一个页的大小），包含1024项，每个项4字节（32位），项目里存储的内容就是页表的物理地址。如果页目录表中的页表尚未分配，则物理地址填0。页表的大小也是4k，同样包含1024项，每个项4字节，内容为最终物理页的物理内存起始地址。每个活动的任务，必须要先分配给它一个页目录表，并把页目录表的物理地址存入cr3寄存器。页表可以提前分配好，也可以在用到的时候再分配。还是以 mov 0 x80495b0,%eax 中的地址为例分析一下线性地址转物理地址的过程。前面说到Linux中逻辑地址等于线性地址，那么我们要转换的线性地址就是0 x80495b0。转换的过程是由CPU自动完成的，Linux所要做的就是准备好转换所需的页目录表和页表（假设已经准备好，给页目录表和页表分配物理内存的过程很复杂，后面再分析）。,线性地址转物理地址,内核先将当前任务的页目录表的物理地址填入cr3寄存器。线性地址 0 x80495b0 转换成二进制后是 0000 1000 0000 0100 1001 0101 1011 0000，最高10位0000 1000 00的十进制是32，CPU查看页目录表第32项，里面存放的是页表的物理地址。线性地址中间10位00 0100 1001 的十进制是73，页表的第73项存储的是最终物理页的物理起始地址。物理页基地址加上线性地址中最低12位的偏移量，CPU就找到了线性地址最终对应的物理内存单元。我们知道Linux中用户进程线性地址能寻址的范围是0 3G，那么是不是需要提前先把这3G虚拟内存的页表都建立好呢？一般情况下，物理内存是远远小于3G的，加上同时有很多进程都在运行，根本无法给每个进程提前建立3G的线性地址页表。Linux利用CPU的一个机制解决了这个问题。进程创建后我们可以给页目录表的表项值都填0，CPU在查找页表时，如果表项的内容为0,则会引发一个缺页异常，进程暂停执行，Linux内核这时候可以通过一系列复杂的算法给分配一个物理页，并把物理页的地址填入表项中，进程再恢复执行。当然进程在这个过程中是被蒙蔽的，它自己的感觉还是正常访问到了物理内存。,线性地址转物理地址,内核页表,临时内核页表最终内核页表,临时内核页表,最终内核页表,物理内存,1.内核页表2.内存描述3.物理探测4.引导内存5.Pre-Cpu Cache6.伙伴机制7.Slab机制,1.内核页表,struct page unsigned long flags;atomic_t _count;union atomic_t _mapcount;unsigned int inuse;union struct unsigned long private;struct address_space*mapping;#if NR_CPUS=CONFIG_SPLIT_PTLOCK_CPUS spinlock_t ptl;#endif struct kmem_cache*slab;/*SLUB:Pointer to slab*/struct page*first_page;/*Compound tail pages*/;union pgoff_t index;/*Our offset within mapping.*/void*freelist;/*SLUB:freelist req.slab lock*/;struct list_head lru;#if defined(WANT_PAGE_VIRTUAL)void*virtual;#endif/*WANT_PAGE_VIRTUAL*/#ifdef CONFIG_CGROUP_MEM_RES_CTLRunsigned long page_cgroup;#endif;,2.内存描述-pglist_data,typedef struct pglist_data struct zone node_zonesMAX_NR_ZONES;struct zonelist node_zonelistsMAX_ZONELISTS;int nr_zones;#ifdef CONFIG_FLAT_NODE_MEM_MAPstruct page*node_mem_map;#endifstruct bootmem_data*bdata;#ifdef CONFIG_MEMORY_HOTPLUGspinlock_t node_size_lock;#endifunsigned long node_start_pfn;unsigned long node_present_pages;/*total number of physical pages*/unsigned long node_spanned_pages;/*total size of physical page range,including holes*/int node_id;wait_queue_head_t kswapd_wait;struct task_struct*kswapd;int kswapd_max_order;pg_data_t;,2.内存描述-zone,struct zone/*Fields commonly accessed by the page allocator*/unsigned longpages_min,pages_low,pages_high;unsigned longlowmem_reserveMAX_NR_ZONES;#ifdef CONFIG_NUMAint node;unsigned longmin_unmapped_pages;unsigned longmin_slab_pages;struct per_cpu_pageset*pagesetNR_CPUS;#elsestruct per_cpu_pagesetpagesetNR_CPUS;#endifspinlock_tlock;#ifdef CONFIG_MEMORY_HOTPLUG/*see spanned/present_pages for more description*/seqlock_tspan_seqlock;#endifstruct free_areafree_areaMAX_ORDER;#ifndef CONFIG_SPARSEMEMunsigned long*pageblock_flags;#endif/*CONFIG_SPARSEMEM*/ZONE_PADDING(_pad1_)/*Fields commonly accessed by the page reclaim scanner*/spinlock_tlru_lock;struct list_headactive_list;struct list_headinactive_list;,2.内存描述-zone,unsigned longnr_scan_inactive;unsigned longpages_scanned;/*since last reclaim*/unsigned longflags;/*zone flags,see below*/*Zone statistics*/atomic_long_tvm_statNR_VM_ZONE_STAT_ITEMS;int prev_priority;ZONE_PADDING(_pad2_)/*Rarely used or read-mostly fields*/wait_queue_head_t*wait_table;unsigned longwait_table_hash_nr_entries;unsigned longwait_table_bits;struct pglist_data*zone_pgdat;/*zone_start_pfn=zone_start_paddr PAGE_SHIFT*/unsigned longzone_start_pfn;unsigned longspanned_pages;/*total size,including holes*/unsigned longpresent_pages;/*amount of memory(excluding holes)*/*rarely used fields:*/const char*name;_cacheline_internodealigned_in_smp;,物理探测,在系统boot的时候，kernel通过0 x15中断获得机器内存容量。有三种参数88H(只能探测最大64MB的内存)，E801H(得到大小)，E820H(获得memory map)。这个memory map称为E820图，在kernel的初始化代码中会将这个memory map复制到一个kernel中的数据结构e820map里，kernel需要通过这个结构来计算可用的内存容量。调用print_memory_map打印出各个内存段的范围和类型，我的内存是2G的，打印结果如下：0.000000BIOS-providedphysicalRAMmap:0.000000BIOS-e820:0000000000000000-000000000009f000(usable)0.000000BIOS-e820:000000000009f000-00000000000a0000(reserved)0.000000BIOS-e820:00000000000f0000-0000000000100000(reserved)0.000000BIOS-e820:0000000000100000-0000000001e00000(usable)0.000000BIOS-e820:0000000001e00000-0000000001e80040(reserved)0.000000BIOS-e820:0000000001e80040-000000007bed0000(usable)0.000000BIOS-e820:000000007bed0000-000000007bed3000(ACPINVS)0.000000BIOS-e820:000000007bed3000-000000007bee0000(ACPIdata)0.000000BIOS-e820:000000007bee0000-000000007bf00000(reserved)0.000000BIOS-e820:000000007c000000-0000000080000000(reserved)0.000000BIOS-e820:00000000f0000000-00000000f4000000(reserved)0.000000BIOS-e820:00000000fec00000-0000000100000000(reserved),引导内存,Pre-Cpu Cache,管理区分配器,伙伴机制,整体结构,伙伴机制,Linux内核通过伙伴算法来管理物理内存。伙伴系统（Buddy System）在理论上是非常简单的内存分配算法。它的用途主要是尽可能减少外部碎片，同时允许快速分配与回收物理页面。为了减少外部碎片，连续的空闲页面，根据空闲块（由连续的空闲页面组成）大小，组织成不同的链表（或者orders）。这样所有的2个页面大小的空闲块在一个链表中，4个页面大小的空闲块在另外一个链表中，以此类推。,伙伴机制,注意，不同大小的块在空间上，不会有重叠。当一个需求为4个连续页面时，检查是否有4个页面的空闲块而快速满足请求。若该链表上（每个结点都是大小为4页面的块）有空闲的块，则分配给用户，否则向下一个级别（order）的链表中查找。若存在（8页面的）空闲块（现处于另外一个级别的链表上），则将该页面块分裂为两个4页面的块，一块分配给请求者，另外一块加入到4页面的块链表中。这样可以避免分裂大的空闲块，而此时有可以满足需求的小页面块，从而减少外面碎片。,Slab机制,Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为 SunOS 操作系统首次引入的一种算法。Jeff 的分配器是围绕对象缓存进行的。在内核中，会为有限的对象集（例如文件描述符和其他常见结构）分配大量内存。Jeff 发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目而初始化的状态。例如，如果内存被分配给了一个互斥锁，那么只需在为互斥锁首次分配内存时执行一次互斥锁初始化函数（mutex_init）即可。后续的内存分配不需要执行这个初始化函数，因为从上次释放和调用析构之后，它已经处于所需的状态中了。Linux slab 分配器使用了这种思想和其他一些思想来构建一个在空间和时间上都具有高效性的内存分配器。与传统的内存管理模式相比，slab 缓存分配器提供了很多优点。首先，内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。slab 分配器还支持通用对象的初始化，从而避免了为同一目而对一个对象重复进行初始化。最后，slab 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。,slab对象管理器,slab对象管理器,slab着色基本原理,CPU访问内存时使用哪个cache line是通过低地址的若干位确定的，比如cache line大小为32，那么是从bit5开始的若干位。因此相距很远的内存地址，如果这些位的地址相同，还是会被映射到同一个cache line。Slab cache中存放的是相同大小的对象，如果没有着色区，那么同一个cache内，不同slab中具有相同slab内部偏移的对象，其低地址的若干位是相同的，映射到同一个cache line。如图所示。,slab着色基本原理,如此一来，访问cache line冲突的对象时，就会出现cache miss，不停的在cache line和内存之间来回切换，与此同时，其他的cache line可能无所事事，严重影响了cache的效率。解决这一问题的方法是通过着色区使对象的slab内偏移各不相同，从而避免cache line冲突。如图所示：,slab着色基本原理,着色貌似很好的解决了问题，实质不然，当slab数目不多时，着色工作的很好，当slab数目很多时，着色发生了循环，仍然存在cache line冲突的问题。如图所示。第一与第四，第二与第五，第三与第六，这些slab的cache line是冲突的。,高端内存,非连续内存固定映射内存临时内存映射永久映射内存,地址映射,虚拟内存,进程虚拟地址空间数据结构区域操作,进程虚拟地址空间,struct mm_struct struct vm_area_struct*mmap;/*list of VMAs*/struct rb_root mm_rb;struct vm_area_struct*mmap_cache;/*last find_vma result*/.unsigned long(*get_unmapped_area)(struct file*filp,unsigned long addr,unsigned long len,unsigned long pgoff,unsigned long flags);.unsigned long mmap_base;/*base of mmap area*/unsigned long task_size;/*size of task vm space*/.unsigned long start_code,end_code,start_data,end_data;unsigned long start_brk,brk,start_stack;unsigned long arg_start,arg_end,env_start,env_end;.,地址映射,虚拟内存区域,struct vm_area_struct struct mm_struct*vm_mm;/*The address space we belong to.*/unsigned long vm_start;/*Our start address within vm_mm.*/unsigned long vm_end;/*The first byte after our end addresswithin vm_mm.*/*linked list of VM areas per task,sorted by address*/struct vm_area_struct*vm_next;pgprot_t vm_page_prot;/*Access permissions of this VMA.*/unsigned long vm_flags;/*Flags,listed below.*/struct rb_node vm_rb;/*For areas with an address space and backing store,*linkage into the address_space-i_mmap prio tree,or*linkage to the list of like vmas hanging off its node,or*linkage of vma in the address_space-i_mmap_nonlinear list.*/union struct struct list_head list;void*parent;/*aligns with prio_tree_node parent*/struct vm_area_struct*head;vm_set;,虚拟内存区域,struct raw_prio_tree_node prio_tree_node;shared;/*A files MAP_PRIVATE vma can be in both i_mmap tree and anon_vma*list,after a COW of one of the file pages.A MAP_SHARED vma*can only be in the i_mmap tree.An anonymous MAP_PRIVATE,stack*or brk vma(with NULL file)can only be in an anon_vma list.*/struct list_head anon_vma_node;/*Serialized by anon_vma-lock*/struct anon_vma*anon_vma;/*Serialized by page_table_lock*/*Function pointers to deal with this struct.*/struct vm_operations_struct*vm_ops;/*Information about our backing store:*/unsigned long vm_pgoff;/*Offset(within vm_file)in PAGE_SIZEunits,*not*PAGE_CACHE_SIZE*/struct file*vm_file;/*File we map to(can be NULL).*/void*vm_private_data;/*was vm_pte(shared mem)*/;,虚拟内存区域,虚拟内存区域,地址空间,线性地址空间分布,高速缓存,Linux使用的缓存页高速缓冲,Linux使用的缓存,不管在硬件设计还是软件设计中，高速缓存是获得高性能的常用手段。Linux使用了多种和内存管理相关的高速缓存。1缓冲区高速缓存：缓冲区高速缓存中包含了由块设备使用的数据缓冲区。这些缓冲区中包含了从设备中读取的数据块或写入设备的数据块。缓冲区高速缓存由设备标识号和块标号索引，因此可以快速找出数据块。如果数据能够在缓冲区高速缓存中找到，则系统就没有必要在物理块设备上进行实际的读操作。内核为每个缓冲区维护很多信息以有助于缓和写操作，这些信息包括一个“脏（dirty）”位，表示内存中的缓冲区已被修改，必须写到磁盘；还包括一个时间标志，表示缓冲区被刷新到磁盘之前已经在内存中停留了多长时间。因为缓冲区的有关信息被保存在缓冲区首部，所以，这些数据结构连同用户数据本身的缓冲区都需要维护。缓冲区高速缓存的大小可以变化。当需要新缓冲区而现在又没有可用的缓冲区时，就按需分配页面。当空闲内存变得不足时，例如上一节看到的情况，就释放缓冲区并反复使用相应的页面。,Linux使用的缓存,2页面高速缓存页面高速缓存是页面I/O操作访问数据所使用的磁盘高速缓存。我们在文件系统会看到，read()、write()和mmap()系统调用对常规文件的访问都是通过页面高速缓存来完成的。因为页面I/O操作要传输整页数据，因此高速缓存中所保留的信息单元是一个整页面。一个页面包含的数据未必是物理上相邻的磁盘块，因此就不能使用设备号和块号来标识页面。相反，页面高速缓存中一个页面的标识是通过文件的索引节点和文件中的偏移量达到的。与页面高速缓存有关的操作主要有三种：当访问的文件部分不在高速缓存中时增加一页面，当高速缓存变得太大时删除一页面，以及查找一个给定文件偏移量所在的页面。,Linux使用的缓存,3交换高速缓存只有修改后的（脏）页面才保存在交换文件中。修改后的页面写入交换文件后，如果该页面再次被交换但未被修改时，就没有必要写入交换文件，相反，只需丢弃该页面。交换高速缓存实际包含了一个页面表项链表，系统的每个物理页面对应一个页面表项。对交换出的页面，该页面表项包含保存该页面的交换文件信息，以及该页面在交换文件中的位置信息。如果某个交换页面表项非零，则表明保存在交换文件中的对应物理页面没有被修改。如果这一页面在后续的操作中被修改，则处于交换缓存中的页面表项被清零。Linux需要从物理内存中交换出某个页面时，它首先分析交换缓存中的信息，如果缓存中包含该物理页面的一个非零页面表项，则说明该页面交换出内存后还没有被修改过，这时，系统只需丢弃该页面。4.硬件高速缓存常见的硬件缓存是对页面表项的缓存，这一工作实际由处理器完成，其操作和具体的处理器硬件有关（但管理要由软件完成）。,页高速缓冲,页高速缓存缓存的是页面。缓存中的页来自对正规文件、块设备文件和内存映射文件的读写，如此一来，页高速缓存内就包含了最近被访问过的文件的全部页面。在执行I/O操作前，比如read()操作，内核会检查数据是否已经在页高速缓存中了，如果所需数据确实在高速缓存中，那么内核就可以马上从缓存中得到所需的页，而不需要从磁盘读取数据。,页框回收,PFRA设计反向映射匿名页的反向映射优先搜索树PFRA实现LRU链表内存紧缺回收,PFRA设计,页框回收算法（page frame reclaiming algorithm,PFRA）的目标就是获得页框并使之空闲。,反向映射,struct page unsigned long flags;atomic_t _count;/*Usage count,see below.*/union atomic_t _mapcount;unsigned int inuse;/*SLUB:Nr of objects*/;,union struct unsigned long private;struct address_space*mapping;struct kmem_cache*slab;/*SLUB:Pointer to slab*/struct page*first_page;/*Compound tail pages*/;union pgoff_t index;void*freelist;,反向映射,由于PFRA 的目标之一是能释放共享页框。为达到这个目的，Linux 2.6 内核能够快速定位指向同一页框的所有页表项。这个过程就叫做反向映射（reverse mapping）。反向映射方法的简单解决之道，就是在页描述符中引人附加字段，从而将某页描述符所确定的页框中对应的所有页表项联接起来。但是，保持更新这样的链表将会大大增加系统开销，因此，就有更成熟的方法设计出来了。Linux 2.6 就有叫做“面向对象的反向映射”的技术。_mapcount 字段存放引用页框的页表项数目。计数器的起始值为-1，这表示没有页表项（不包括内核页表）引用该页框；如果值为0，就表示页是非共享的；而如果值大于0（比如是n），则表示页是共享的，并且有n+1 个页表共享它。page_mapcount 函数接收页描述符地址，返回值为_mapcount+l（这样，如返回值为1，表明是某个进程的用户态地址空间中存放的一个非共享页）。页描述符的mapping 字段用于确定页是映射的或匿名的。说明如下：1).如果mapping 字段空，则该页属于交换高速缓存。2).如果mapping 字段非空，且最低位是1，表示该页为匿名页；同时mapping 字段中存放的是指向anon_vma 描述符的指针。3).如果mapping 字段非空，且最低位是0，表示该页为映射页；同时mapping 字段指向对应文件的address_space 对象。,匿名页的反向映射,struct anon_vma spinlock_t lock;/*Serialize access to vma list*/struct list_head head;/*List of private related vmas*/;,匿名页经常是由几个进程共享的。最为常见的情形是：创建新进程父进程的所有页面，包括匿名页，同时也以只读的形式让子进程的页表项指向。另外（但不常见），进程创建线性区时使用两个标志MAP_ANONYMOUS 和MAP_SHARED，表明这个线性区域内的页将由该进程后面的子进程共享。Linux 使用一个非常简单策略：将引用同一个页框的所有匿名线性区链接起来的，也就是说将该页框所在的匿名线性区存放在一个双向循环链表中。注意！一个匿名线性区有可能很大，会存有多个页，但因为这些页面是连续的，所以有且始终只有一个反向映射链表用于该区域中的所有页面。当为一个匿名线性区分配第一页时，内核创建一个新的anon_vma 数据结构,匿名页的反向映射,lock 字段是竞争条件下保护链表的自旋锁；head 字段是线性区描述符双向循环链表的头部。然后，内核将匿名线性区的vm_area_struct 描述符插入anon_vma 链表。为实现这个目的，vm_area_struct 数据结构中包含有对应该链表的两个字段：anon_vma_node 和anon_vma。anon_vma_node 字段存放指向链表中的前一个和后一个元素的指针，而anon_vma 字段指向anon_vma 数据结构。最后，按前面所述，内核将anon_vma 数据结构的地址存放在匿名页描述符的mapping 字段。如图所示,匿名页的反向映射,匿名页的反向映射,lock 字段是竞争条件下保护链表的自旋锁；head 字段是线性区描述符双向循环链表的头部。然后，内核将匿名线性区的vm_area_struct 描述符插入anon_vma 链表。为实现这个目的，vm_area_struct 数据结构中包含有对应该链表的两个字段：anon_vma_node 和anon_vma。anon_vma_node 字段存放指向链表中的前一个和后一个元素的指针，而anon_vma 字段指向anon_vma 数据结构。最后，按前面所述，内核将anon_vma 数据结构的地址存放在匿名页描述符的mapping 字段。如图所示,匿名页的反向映射,当已被一个进程引用的页面插入另一个进程的页表项时（例如调用fork()系统调用时），内核只是将第二个进程的匿名线性区插入anon_vma 数据结构的双向循环链表，而第一个进程线性区的anon_vma 字段指向该anon_vma 数据结构。因此每个anon_vma 链表通常包含不同进程的线性区。综上，借助anon_vma 链表，内核可以快速定位引用同一匿名页框的所有页表项。实际上，每个区域描述符在vm_mm字段中存放内存描述符地址，而该内存描述符又有一个pgd 字段，其中存有进程的页全局目录。这样，页表项就可以从匿名页的起始线性地址得到，而该匿名页线性地址可以由线性区描述符的vm_start 字段以及页描述符的index字段得到。,try_to_unmap_one,优先搜索树,映射页的面向对象反向映射所基于的思想要简单得多了：我们总是可以获得指向一个给定页框的页表项，方法就是访问相应映射页所在的线性区描述符。因此，反向映射的关键就是一个巧妙的数据结构，这个数据结构可以存放与给定页框有关的所有线性区描述符。匿名线性区描述符存放在双向循环链表中。获得引用给定页框的所有页表项，就是对该链表中的元素进行线性扫描。共享匿名页框的数量不是很大，因此这个方法工作得很好。与匿名页相反，映射页经常是共享的，这是因为不同的进程常会共享同一个程序代码。例如，几乎所有进程都会共享包含标准C 库代码的页面。因此，Linux 2.6 依靠叫做“优先搜索树（priority search tree）”的结构来快速定位引用同一页框的所有线性区。每个文件对应一个优先搜索树。它存放在address_space 对象的i_mmap 字段中，该address_space 对象包含在文件的索引节点对象中。因为映射页描述符的mapping 字段指向address_space 对象，所以总是能够快速检索搜索树的根：,优先搜索树,PST树是一个堆和对称搜索树的混合体,PST 中的每一个区间相当于一个树的节点，它由基索引（radix index）和堆索引（heap index)两个索引来标识。基索引表示区间的起始点而堆索引表示终点。每个线性区可以被看成是文件页的在物理内存中一个区间，并由在文件中的起始位置（基索引）和终点位置（堆索引）所确定。,struct address_space struct inode*host;/*owner:inode,block_device*/struct radix_tree_rootpage_tree;/*radix tree of all pages*/rwlock_ttree_lock;/*and rwlock protecting it*/unsigned inti_mmap_writable;/*count VM_SHARED mappings*/struct prio_tree_rooti_mmap;/*tree of private and shared mappings*/_attribute_(aligned(sizeof(long);,优先搜索树,struct file.struct address_space*f_mapping;.struct inode.struct address_space*i_mapping;.,优先搜索树,优先搜索树,子节点的堆索引都不大于相应父节点的堆索引。任意一个节点的左子节点基索引也都不大于右子节点基索引，如果基索引相等，则按照大小索引排序。,PFRA实现,页框回收算法必须处理多种属于用户态进程、磁盘高速缓存和内存高速缓存的页，而且必须遵照几条试探法准则。因此，PFRA 有很多函数也就不奇怪了。在ULK-3 中的一个图列出了P