Linux内存管理之页面回收 .

凝望长空

Linux内存管理之页面回收 .

       请求调页机制，只要用户态进程继续执行，他们就能获得页框，然而，请求调页没有办法强制进程释放不再使用的页框。因此，迟早所有空闲内存将被分配给进程和高速缓存，Linux内核的页面回收算法（PFRA）采取从用户进程和内核高速缓存“窃取”页框的办法不从伙伴系统的空闲块列表。

       实际上，在用完所有空闲内存之前，就必须执行页框回收算法。否则，内核很可能陷入一种内存请求的僵局中，并导致系统崩溃。也就是说，要释放一个页框，内核就必须把页框的数据写入磁盘；但是，为了完成这一操作，内核却要请求另一个页框（例如，为I/O数据传送分配缓冲区首部）。因为不存在空闲页框，因此，不可能释放页框。

       页框算法的目标之一就是保存最少的空闲页框并使内核可以安全地从“内存紧缺”的情形中恢复过来。

选择目标页

       PFRA的目标就是获得页框并使之空闲。PFRA按照页框所含内容，以不同的方式处理页框。我们将他们区分成：不可回收页、可交换页、可同步页和可丢弃页：

页类型
说明
回收操作

不可回收页
空闲页（包含子伙伴系统列表中）

保留页（PG_reserved标志置位）

内核动态分配页

进程内核态堆栈页

临时锁定页（PG_locked标志置位）

内存锁定页（在先行区中且VM_LOCKED标志置位）
不允许也无需回收

可回收页
用户太地址空间的匿名页

Tmpfs文件系统的映射页（如IPC共享内存的页）


将页的内容保存在交换区

可同步页
用户态地址空间的映射页

存有磁盘文件数据且在页高速缓存中的页

块设备缓冲区页

某些磁盘高速缓存的页（如索引节点高速缓存）
必要时，与磁盘镜像同步这些页

可丢弃页
内存高速缓存中的未使用页（如slab分配器高速缓存）

目录想高速缓存的未使用页
无需操作




进行页面回收的时机

        Linux 操作系统使用如下这两种机制检查系统内存的使用情况，从而确定可用的内存是否太少从而需要进行页面回收。

◦周期性的检查：这是由后台运行的守护进程 kswapd 完成的。该进程定期检查当前系统的内存使用情况，当发现系统内空闲的物理页面数目少于特定的阈值时，该进程就会发起页面回收的操作。
◦“内存严重不足”事件的触发：在某些情况下，比如，操作系统忽然需要通过伙伴系统为用户进程分配一大块内存，或者需要创建一个很大的缓冲区，而当时系统中的内存没有办法提供足够多的物理内存以满足这种内存请求，这时候，操作系统就必须尽快进行页面回收操作，以便释放出一些内存空间从而满足上述的内存请求。这种页面回收方式也被称作“直接页面回收”。
◦睡眠回收，在进入suspend-to-disk状态时，内核必须释放内存。
       如果操作系统在进行了内存回收操作之后仍然无法回收到足够多的页面以满足上述内存要求，那么操作系统只有最后一个选择，那就是使用 OOM( out of memory )killer，它从系统中挑选一个最合适的进程杀死它，并释放该进程所占用的所有页面。

       上面介绍的内存回收机制主要依赖于三个字段：pages_min，pages_low 以及 pages_high。每个内存区域（ zone ）都在其区域描述符中定义了这样三个字段，这三个字段的具体含义如下表 所示。

字段含义

名称
字段描述

pages_min
区域的预留页面数目，如果空闲物理页面的数目低于 pages_min，那么系统的压力会比较大，此时，内存区域中急需空闲的物理页面，页面回收的需求非常紧迫。

pages_low
控制进行页面回收的最小阈值，如果空闲物理页面的数目低于 pages_low，那么操作系统内核会开始进行页面回收。

pages_high
控制进行页面回收的最大阈值，如果空闲物理页面的数目多于 pages_high，则内存区域的状态是理想的。




PFRA设计

设计总则

1.       首先释放“无害”页，即必须线回收没有被任何进程使用的磁盘与内存高速缓存中的页；

2.       将用户态进程和所有页定为可回首页，FPRA必须能够窃得人任何用户态进程页，包括匿名页。这样，睡眠较长时间的进程将逐渐失去所有页；

3.       同时取消引用一个共享页的所有页表项的映射，就可以回收该共享页；

4.       只回收“未用”页，使用LRU算法。Linux使用每个页表项中的访问标志位，在页被访问时，该标志位由银奖自动置位；而且，页年龄由页描述符在链表（两个不同的链表之一）中的位置来表示。

因此，页框回收算法是集中启发式方法的混合：

1．  谨慎选择检查高速缓存的顺序；

2．  基于页年龄的变化排序；

3．  区别对待不同状态的页；

反向映射

        PFRA的目标之一是能释放共享页框。为达到这个目地。Linux内核能够快速定为指向同一页框的所有页表项。这个过程就叫做反向映射。Linux 操作系统为物理页面建立一个链表，用于指向引用了该物理页面的所有页表项。

基本思想如下图：



       Linux采用“面向对象的反向映射”技术。实际上，对任何可回收的用户态页，内核保留系统中该页所在所有现行区（“对象”）的反向链接，每个线性区描述符（ vm_area_struct 结构）存放一个指针指向一个内存描述符（ mm_struct 结构），而该内存描述符又包含一个指针指向一个页全局目录（PGD）。因此，这些反向链接使得PFRA能够检索引用某页的所有页表项。因为线性区描述符比页描述符少，所以更新共享页的反向链接就比较省时间。下面是具体的实现：

基于对象的反向映射的实现

数据结构

       首先，PFRA必须要确定待回收页是共享的还是非共享的，以及是映射页或是匿名页。为做到这一点，内核要查看页描述符的两个字段：_mapcount和mapping。_mapcount字段存放引用页框的页表项数目，确定其是否共享；mapping字段用于确定页是映射的或是匿名的：为空表示该页属于交换高速缓存；非空，且最低位是1，表示该页为匿名页，同时mapping字段中存放的是指向anon_vma描述符的指针；如果mapping字段非空，且最低位是0，表示该页为映射页；同时mapping字段指向对应文件的address_space对象。

[cpp] view plaincopyprint?

1. 01.struct page   
   
2. 02.{   
   
3. 03.     atomic_t _mapcount;         
   
4. 04.                  
   
5. 05.     union {   
   
6. 06.        ……  
   
7. 07.        struct {   
   
8. 08.        ……        
   
9. 09.         struct address_space *mapping;      
   
10. 10.        };   
    
11. 11.        ……  
    
12. 12. };   
    
13. struct page
    
14. {
    
15.          atomic_t _mapcount;                
    
16.                                
    
17.          union {
    
18.         ……
    
19.             struct {
    
20.                 ……               
    
21.                  struct address_space *mapping;        
    
22.             };
    
23.         ……
    
24. };  

复制代码

Linux的address_space对象在RAMA中是对其的，所以其起始地址是4的倍数。因此其mapping字段的最低位可以用作一个标志位来表示该字段的指针是指向address_space对象还是anon_vma描述符。PageAnon检查mapping最低位。

[cpp] view plaincopyprint?

1. 01./*检查页是否为匿名页，低位为1时为匿名页*/  
   
2. 02.static inline int PageAnon(struct page *page)  
   
3. 03.{  
   
4. 04.    return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;  
   
5. 05.}  
   
6. /*检查页是否为匿名页，低位为1时为匿名页*/
   
7. static inline int PageAnon(struct page *page)
   
8. {
   
9.         return ((unsigned long)page->mapping & PAGE_MAPPING_ANON) != 0;
   
10. }

复制代码

匿名页面和文件映射页面分别采用了不同的底层数据结构去存放与页面相关的虚拟内存区域。对于匿名页面来说，与该页面相关的虚拟内存区域存放在结构 anon_vma 中定义的双向链表中。结构 anon_vma 定义很简单，如下所示：

[cpp] view plaincopyprint?

1. 01.struct anon_vma   
   
2. 02.{   
   
3. 03.     spinlock_t lock;     
   
4. 04.     struct list_head head;      
   
5. 05.};  
   
6. struct anon_vma
   
7. {
   
8.          spinlock_t lock;        
   
9.          struct list_head head;        
   
10. };

复制代码

匿名页的面向对象反向映射如下图：



       可以通过页面的mapping找到anon_vma然后找到映射该页面的所有线性区域（vm_area_struct结构）。

而对于基于文件映射的页面来说，与匿名页面不同的是，与该页面相关的虚拟内存区域的存放是利用了优先级搜索树这种数据结构的。这是因为对于匿名页面来说，页面虽然可以是共享的，但是一般情况下，共享匿名页面的使用者的数目不会很多；而对于基于文件映射的页面来说，共享页面的使用者的数目可能会非常多，使用优先级搜索树这种结构可以更加快速地定位那些引用了该页面的虚拟内存区域。操作系统会为每一个文件都建立一个优先级搜索树，其根节点可以通过结构 address_space 中的 i_mmap 字段获取。

[cpp] view plaincopyprint?

1. 01.struct address_space {   
   
2. 02.  ……  
   
3. 03. struct prio_tree_root   i_mmap;         
   
4. 04.……  
   
5. 05. }   
   
6. struct address_space {
   
7.    ……
   
8.          struct prio_tree_root          i_mmap;                
   
9.         ……
   
10.          }

复制代码

Linux中使用 (radix,size,heap) 来表示优先级搜索树中的节点。其中，radix 表示内存区域的起始位置，heap 表示内存区域的结束位置，size 与内存区域的大小成正比。在优先级搜索树中，父节点的 heap 值一定不会小于子节点的 heap 值。在树中进行查找时，根据节点的 radix 值进行。程序可以根据 size 值区分那些具有相同 radix 值的节点。

      在用于表示虚拟内存区域的结构 vm_area_struct 中，与上边介绍的双向链表和优先级搜索树相关的字段如下所示：

[cpp] view plaincopyprint?

1. 01.struct vm_area_struct {   
   
2. 02. struct mm_struct * vm_mm;   
   
3. 03.……  
   
4. 04. union {   
   
5. 05.     struct {   
   
6. 06.         struct list_head list;   
   
7. 07.         void *parent;   
   
8. 08.         struct vm_area_struct *head;   
   
9. 09.     } vm_set;   
   
10. 10.  
    
11. 11.     struct raw_prio_tree_node prio_tree_node;   
    
12. 12. } shared;   
    
13. 13.  
    
14. 14.  
    
15. 15. struct list_head anon_vma_node;      
    
16. 16. struct anon_vma *anon_vma;      
    
17. 17.};   
    
18. struct vm_area_struct {
    
19.          struct mm_struct * vm_mm;        
    
20.         ……
    
21.          union {
    
22.                  struct {
    
23.                          struct list_head list;
    
24.                          void *parent;        
    
25.                          struct vm_area_struct *head;
    
26.                  } vm_set;
    
27. 
    
28.                  struct raw_prio_tree_node prio_tree_node;
    
29.          } shared;
    
30. 
    
31.        
    
32.          struct list_head anon_vma_node;        
    
33.          struct anon_vma *anon_vma;        
    
34. };
    

复制代码

与匿名页面的双向链表相关的字段是 anon_vma_node 和 anon_vma。union shared 则与文件映射页面使用的优先级搜索树相关。字段 anon_vma 指向 anon_vma 表；字段 anon_vma_node 将映射该页面的所有虚拟内存区域链接起来；union shared 中的 prio_tree_node 结构用于表示优先级搜索树的一个节点；在某些情况下，比如不同的进程的内存区域可能映射到了同一个文件的相同部分，也就是说这些内存区域具有相同的（radix,size,heap）值，这个时候 Linux 就会在树上相应的节点（树上原来那个具有相同（radix,size,heap） 值的内存区域）上接一个双向链表用来存放这些内存区域，这个链表用 vm_set.list 来表示；树上那个节点指向的链表中的第一个节点是表头，用 vm_set.head 表示；vm_set.parent 用于表示是否是树结点。下边给出一个小图示简单说明一下 vm_set.list 和 vm_set.head。

vm_set.list 和 vm_set.head



       通过结构 vm_area_struct 中的 vm_mm 字段可以找到对应的 mm_struct 结构，在该结构中找到页全局目录，从而定位所有相关的页表项。

反向映射实现

       在进行页面回收的时候，Linux的 shrink_page_list() 函数中调用 try_to_unmap() 函数去更新所有引用了回收页面的页表项。其代码流程如下所示：
实现函数 try_to_unmap() 的关键代码流程图


       函数 try_to_unmap() 分别调用了两个函数 try_to_unmap_anon() 和 try_to_unmap_file()，其目的都是检查并确定都有哪些页表项引用了同一个物理页面，但是，由于匿名页面和文件映射页面分别采用了不同的数据结构，所以二者采用了不同的方法。

       函数 try_to_unmap_anon() 用于匿名页面，该函数扫描相应的 anon_vma 表中包含的所有内存区域，并对这些内存区域分别调用 try_to_unmap_one() 函数。

       函数 try_to_unmap_file() 用于文件映射页面，该函数会在优先级搜索树中进行搜索，并为每一个搜索到的内存区域调用 try_to_unmap_one() 函数。

       两条代码路径最终汇合到 try_to_unmap_one() 函数中，更新引用特定物理页面的所有页表项的操作都是在这个函数中实现的。

清风鸟儿

谢谢分享