struct page

_nosay

    Linux内核中，物理页面管理的设计思路非常值得学习，它的巧妙以及复杂性都主要源自对效率的考虑。即使重要的接口设计清晰，但由于对效率的极致追求，很多接口内部包含一些细致入微的考虑，引入很多状态后，使得整体逻辑显得极其复杂，我很清楚这篇文章根本没有总结到位，甚至还有一些错误的地方，所以希望你见谅。

    通过之前介绍的Linux对于物理页面的调度策略，可以概括为：未雨绸缪、留退路、不添乱。
    ① 未雨绸缪：不是非要等到真的需要将某些物理页面换出时，才执行换出操作，而是在空闲时就“猜测”将来可能需要被换出的页面，并为换出做好准备工作；
    ② 留退路：准备工作既然是在猜测的前提下做的，所以就不仅要考虑“猜对”时，页面可以快速被换出，还考虑“猜错”时，页面可以快速被恢复（进可攻，退可守），具体的做法就是：先只将页面的内容复制到磁盘，并不马上释放页面（还回空闲区域），而是挂到swapper_space，这样就保证进退只是在不同链表之间的一些转移，或映射关系的变化；
    ③ 不添乱：保证在系统空闲时会以及才会进行换出的准备工作，即不“好心做坏事”，具体做法是：Linux进程调度也是有策略的，将进行准备工作的进程（比如kswaped）优先级设置的低一些，就可以保证它在“系统空闲”时才工作，而不是在系统很忙时去添乱（除非紧急需要内存时被huàn醒）。

• struct page
  

   

    图中基本可以看出page结构在各种状态下，与一些变量或其它结构之间的联系：
    ① 分配
        @ 如果分配页面是用于换入的，则list从空闲区脱链的，要链入全局变量swapper_space（address_space结构）的clean_pages（注意区分address_space与swap_info_struct：address_space管理与磁盘有联系的物理页面，swap_info_struct管理交换设备）；如果不是因为换入而分配的页面，list从空闲区脱链变成空结点即可。
        
        @ 按照分配策略数组指向的zone，依次从中分配，直到成功，或依次降低要求再分配，直到成功或失败
        alloc_pages()
          |--> alloc_pages_pgdat()
          |      |--> __alloc_pages()
          |      |      |--> wakeup_bdflush()       // short ??
          |      |      |--> rmqueue()                  // 从管理区取指定数量的页面
          |      |      |      |--> memlist_entry()
          |      |      |      |--> memlist_del()
          |      |      |      |--> expand()             // 分配时，buddy算法的执行
          |      |      |--> __alloc_pages_limit()  // 如果以上过程没有分配成功，降低要求再次分配
          |      |      |--> wakeup_kswapd()       // 如果还是失败，huàn醒回收内存的内核线程
          |      |      |--> schedule()                  // 并且如果gfp_mask表示“遇到失败愿意等待”，则调度其它进程执行，切换回来后再次尝试
          |      |      |      // kswapd进程在执行过程中也需要分配内存，当然也会遇到分配失败，这样又会尝试通过kswapd得到更多的物理页面，所以将kswapd进程的PF_MEMALLOC标志设为1，防止这种情况出现递归
          |      |      |      |--> page_launder()         // 将脏页面“洗净”，看是否可以满足要分配的量或要分配的块大小
          |      |      |      |--> try_to_free_pages()  // 如果还是不满足，直接调用try_to_free_pages()（kswapd进程也会定时执行该函数，等不及的情况下当然自己调）


    ② 页面换出（swap_out()函数）：
        @ 扫描所有进程虚拟内存区间（mm_struct管理结构），根据rss值[1]，找一个“最好”的虚拟区间，再通过swap_out_mm()→swap_out_vma()→swap_out_pgd()→swap_out_pmd()→try_to_swap_out()→page_cache_release()，找到映射到该虚拟区间的某个符合换出条件[2]的物理页面并转移到不活跃链表[3]。
        [1] 有时虽然虚拟区间很大，但与其建立映射的物理页面却很少。一方面由于“延迟技术”（非不得以时才做），比如malloc(1G)，虚拟页面确实一开始就分配了1G，而物理页面只是在某个虚拟页面被访问时才由缺页异常“补上”；另一方面也可能由于这个虚拟区间映射的很多物理页面被换出了。
        [2] 根据page的reference、active、age等状态（稍后见详细分析）。
        [3] 从找到的“最好”虚拟区间，不一定就能找到满足换出条件的物理页面，比如映射到该区间的页面，都在刚刚受到访问了，所以可能需要进行多次这样的扫描，扫描多少次由swap_out()参数priority值决定（换出意愿的程度）。敏锐的人可能又会产生疑问：
              + 这一步没有有换出，即所选的“最好”虚拟区间，映射的物理页面数量不变，下次不仍然会认为它“最好”？
                 映射的物理页面数量只是在swap_out()之前初始化到rss，后面每扫描一次，rss也会减1。
              + 极端的情况会出现扫描所有进程的虚拟区间，都找不到可以换出的页面，那如何解决系统页面缺乏的问题？
                 kswapd()一直“马不停蹄”巡查页面短缺情况，一旦短缺就通过refill_inactive_scan()将“偷懒”页面“老化”一点，而时间是只进不退的，当前找不到可换出的页面，尽早也能找到。

        @ try_to_swap_out()
              |
              |--> PageActive() ??                          // 如果不在active_list，就一定在inactive_dirty_list或inactive_clean_list[1]
              |      -> age_page_down_ageonly()     // 在不活跃页面的话，“额外”再“老化”一下？
              |--> ptep_test_and_clear_young() ??  // 硬件每次访问某个物理页面时，必须“经过”pte，同时会将pte中A标志（“accessed”）置为1，而在这里由软件test并clear该位[2]
              |      -> age_page_up()                      // 如果A标志为1，给点“奖赏”并返回
              |
              |      // 到这里如果已经被完全“老化”，就可以确定页面是可以被换出的了
              |--> PageSwapCache()                      // 物理页面主要在三种情况下会和文件产生联系：换出换入[3]、文件缓存、mmap()
              |      -> pte_dirty() -> set_page_dirty()       // 硬件每次对页面进行写访问，“经过”pte时将D标志（“dirty”）置为1，而这里由软件调用set_page_dirty()将“脏”标志从pte转移到page->flag（因为pte即将变成swp_entry_t，就没有D标志了）
              |      -> set_pte()                              // 断开映射
              |      -> deactivate_page()                 // 转换到不活跃链表，将来由page_launder()进行真正的换出操作（复制页面内容到磁盘[4]+归还到空闲区）
              |      -> page_cache_release() -> __free_page() -> .. -> __free_pages_ok()  // “洗净→释放”不是要等到page_launder()执行时才做么，为什么这里直接释放了？[5]
              |
              |      // 到这里，就是要释放非换入页面了
              |--> page->mapping ??                    // 上述说过，物理页面在三种情况会与磁盘产生联系，page->mapping也会指向相应的address_space结构，而如果指向的是swapper_space，在上一步就返回了，这里就只可能是由于文件缓存或mmap，如果页面脏的话，标记一下，页面释放前会由文件驱动将内容刷新到磁盘
              |
              |      // 否则就是之前与文件没有联系的页面
              |--> get_swap_page()                      // 在交换文件为页面分配一块地盘
              |--> add_to_swap_cache()               // 加到swapper_space（如下[3]说明的那样）
            
        [1] 尝试换出的物理页面，都是从进程的映射关系中扫描得到的，那就必然活跃，为什么try_to_swap_out()还要考虑它有可能在不活跃链表？
              情形一：后面分析do_swap_page()时就可以看到，一个页面被转移到不活跃链表不久又受到访问时，只是恢复映射关系，但并不马上从不活跃链表转移到active_list，而是系统在空闲时调用page_launder()处理。
              情形二：A、B进程虚拟页面映射到同一个物理页面（mmap()），swap_out()根据扫描rss，恰好认为A进程的该物理页面是要被换出的，从而断开它与进程A的映射关系，并转移到inactive_dirty_list后，显然B进程这时还映射着该物理页面。
              那么，do_swap_page()中为什么只对在不活跃链表中的页面进行“老化”？
              真正对每个页面起“老化”作用的是refill_inactive_scan()函数，和swap_out()一样，都是被kswaped()函数调用（稍后详细分析），这里应该是为了让在不活跃链表但实际还活跃的页面，比通常的活跃页面“老化”更快一点吧。
        [2] 由于上次扫描到该页面时，将A标志clear了，所以如果现在发现它为1，则表示上次扫描到本次扫描这段时间至少被访问过一次，至少很确定该页面近期“活跃”了一下，不旦不能企图换出它，还要给它一点“奖赏”。其中“奖赏”的目的在于，抵消refill_inactive_scan()对页面的一直“老化”，保证活跃的页面一直不被换出，否则可能刚换出又要换入。
        [3] 如果页面是可换入/换出的，即交换分区已经有一块地盘和它对应，都会被加入swapper_space（address_space结构），PG_swap_cache标志被置为1，比如换入时新分配的页（即使后来脏了）、inactive_clean_list中的页、inactive_dirty_list中被page_launder()洗净的页。如果页面在swapper_space，首先不再需要再在交换文件中为它分配地盘，其次如果自从上次换入，页面内容从来都没遇到过写操作，那么换出时就可以免去写磁盘操作，只需要修改一个pte，将虚拟页面映射指向从物理页面修改为磁盘。
        [4] 页面脏时（D标志），才需要往磁盘写。不同目的文件提供的一套文件操作函数也一般不相同，比如用于管理可交换页面的swapper_space，它的a_ops指向交换文件的操作函数，而每个文件也有一个address_space结构，用于管理该文件自己的缓存页，该结构成员a_ops就指向属于该文件的操作函数列表。最终都由文件驱动完成，比如这里就调用swapper_space->a_ops->writepage()，将页面内容复制到磁盘。
        [5] __free_pages_ok()入口有很多判断条件，由于上一步执行了deactivate_page()，如果该页面被成功加入不活跃链表，__free_pages_ok()就不可能释放得掉它。
              另外，通过__free_pages_ok()代码，可以学习伙伴算法，是如何尽量将当前释放页面与已经空闲页面快速合并成块的。


    ③ 页面换出（kswapd()函数）
        @ 该函数由kswapd内核进程在系统比较闲时执行，在比较不顺利的情况下，才会调用上述的swap_out()扫描进程映射表，不过顺利的前提，又是它之前将足够多的页面转移到了不活跃链表。
        

        @ kswapd()  // for( ;; )
              |
              |--> do_try_to_free_pages()
              |        |
              |        |--> page_launder()                     // inactive_dirty_list
              |        |        |
              |        |        |--> PageInactiveDirty() ??  // 如果PG_inactive_dirty标志不为1，却被加到inactive_dirty_list，基本可以说明内核有bug，这里将该页面移到active_list，有点“规避”问题的味道，但还好记了日志[1]
              |        |        |      // 以下三个条件任何一个成立，表示页面还在使用中（加入inactive_dirty_list不久就又受到访问），或由于某种原因，误加了进来，所以都转移到active_list
              |        |        |--> PageTestandClearReferenced() ??   // 根据pte的A标志
              |        |         --> page->age ??
              |        |         --> page_count() ??                            // 空闲：count=0；分配+没映射：count=1；分配+没映射+文件缓存（纯粹内核自己用于文件缓存）：buffers!=NULL,count=2[2]
              |        |
              |        |        |--> TryLockPage() ??                          // 之前加锁了：返回；之前没加锁：加锁并继续往下执行
              |        |        |--> PageDirty() ??                              // 如下[1]说明
              |        |        |        |--> writepage()                         // 根据交换文件的操作函数，将内容复制到磁盘
              |        |        |        |--> try_to_free_buffers()           // 文件缓存页（根据buffers（buffer_head结构）链表，将内容刷新到对应的文件，并释放buffers）
              |        |        |        |        |--> refill_inactive()
              |        |        |        |        |        |--> swap_out()      // 虽名为“换出”，但并不真的“出”，只是找出可以“出”的页面
              |        |        |        |--> 调整在各链表中的位置
              |        |
              |        |--> shrink_dcache_memory(),shrink_icache_memory() / kmem_cache_reap()
              |
              |--> refill_inactive_scan()                                      // “时光机”，不停的将页面“老化”
              |--> interruptible_sleep_on_timeout() / oom_kill()  // 如果不再短缺了，就可以休息一把了（等休息完，继续回到死循环开始处），如果回收了还短缺，根据oom策略挑选进程并杀掉

        [1] PG_inactive_dirty标志为1，只表示页面是否在inactive_dirty_list（位置），而PG_dirty才表示页面是否脏，上述已经说明过，还有映射的页面可能出现在不活跃链表，其实干净页面也会出现在inactive_dirty_list，也正是page_launder()分两遍扫描的原因。第一遍只回收干净页面，因为inactive_dirty_list里面都是些“未雨绸缪”的页面，所以即使了好大劲，可能也只是做了一件对最终结果没有意义的事，因此就优先用最低的代价去完成。
              那么，干净页面为什么会出现在inactive_dirty_list呢？
        [2] 只要没有进程映射到该物理页面了，就可以换出。
              另外，用于文件缓存的情况（假设“文件F”），为什么不将“文件F”本身当作交换文件？
              因为swp_entry_t没办法表示页面到非交换文件的去向，do_page_fault()检测页表项P标志为0时，只会将type,offset理解为交换文件的一个位置，如果当前换出时不往交换文件复制一份，换入时又怎么可能从交换文件还原到内容呢。