第2章 内存管理

本章思考题

1．在系统启动时，ARM Linux内核如何知道系统中有多大的内存空间？

2．在32bit Linux内核中，用户空间和内核空间的比例通常是3:1，可以修改成2:2吗？

3．物理内存页面如何添加到伙伴系统中，是一页一页添加，还是以2的几次幂来加入呢？

4．内核的一级页表存放在什么地方？内核空间的二级页表又存放在什么地方？

5．用户进程的一级页表存放在什么地方？二级页表又存放在什么地方？

6．在ARM32系统中，页表是如何映射的？在ARM64系统中，页表又是如何映射的？

7．请简述Linux内核在理想情况下页面分配器（page allocator）是如何分配出连续物理页面的。

8．在页面分配器中，如何从分配掩码（gfp_mask）中确定可以从哪些zone中分配内存？

9．页面分配器是按照什么方向来扫描zone的？

10．为用户进程分配物理内存，分配掩码应该选用GFP_KERNEL，还是GFP_HIGHUSER_MOVABLE呢？

11．slab分配器是如何分配和释放小内存块的？

12．slab分配器中有一个着色的概念（cache color），着色有什么作用？

13．slab分配器中的slab对象有没有根据Per-CPU做一些优化？

14．slab增长并导致大量不用的空闲对象，该如何解决？

15．请问kmalloc、vmalloc和malloc之间有什么区别以及实现上的差异？

16．使用用户态的API函数malloc()分配内存时，会马上为其分配物理内存吗？

17．假设不考虑libc的因素，malloc分配100Byte，那么实际上内核是为其分配100Byte吗？

18．假设两个用户进程打印的malloc()分配的虚拟地址是一样的，那么在内核中这两块虚拟内存是否打架了呢？

19．vm_normal_page()函数返回的是什么样页面的struct page数据结构？为什么内存管理代码中需要这个函数？

20．请简述get_user_page()函数的作用和实现流程。

21．请简述follow_page()函数的作用的实现流程。

22．请简述私有映射和共享映射的区别。

23．为什么第二次调用mmap时，Linux内核没有捕捉到地址重叠并返回失败呢？

      #strace捕捉某个app调用mmap的情况
      mmap(0x20000000, 819200, PROT_READ|PROT_WRITE,
      MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20000000
      …
      mmap(0x20000000, 4096, PROT_READ|PROT_WRITE,
      MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x20000000

24．struct page数据结构中的_count和_mapcount有什么区别？

25．匿名页面和page cache页面有什么区别？

26．struct page数据结构中有一个锁，请问trylock_page()和lock_page()有什么区别？

27．在Linux 2.4.x内核中，如何从一个page找到所有映射该页面的VMA？反向映射可以带来哪些便利？

28．阅读Linux 4.0内核RMAP机制的代码，画出父子进程之间VMA、AVC、anon_vma和page等数据结构之间的关系图。

29．在Linux 2.6.34中，RMAP机制采用了新的实现，在Linux 2.6.33和之前的版本中称为旧版本RMAP机制。那么在旧版本RMAP机制中，如果父进程有1000个子进程，每个子进程都有一个VMA，这个VMA里面有1000个匿名页面，当所有的子进程的VMA同时发生写复制时会是什么情况呢？

30．当page加入lru链表中，被其他线程释放了这个page，那么lru链表如何知道这个page已经被释放了？

31．kswapd内核线程何时会被唤醒？

32．LRU链表如何知道page的活动频繁程度？

33．kswapd按照什么原则来换出页面？

34．kswapd按照什么方向来扫描zone？

35．kswapd以什么标准来退出扫描LRU？

36．手持设备例如Android系统，没有swap分区或者swap文件，kswapd会扫描匿名页面LRU吗？

37．swappiness的含义是什么？kswapd如何计算匿名页面和page cache之间的扫描比重？

38．当系统充斥着大量只访问一次的文件访问（use-one streaming IO）时，kswapd如何来规避这种风暴？

39．在回收page cache时，对于dirty的page cache, kswapd会马上回写吗？

40．内核有哪些页面会被kswapd写回交换分区？

41．ARM32 Linux如何模拟这个Linux版本的L_PTE_YOUNG比特位呢？

42．如何理解Refault Distance算法？

43．请简述匿名页面的生命周期。在什么情况下会产生匿名页面？在什么条件下会释放匿名页面？

44.KSM是基于什么原理来合并页面的？

45．在KSM机制里，合并过程中把page设置成写保护的函数write_protect_page()有这样一个判断：

      if (page_mapcount(page) + 1 + swapped ! = page_count(page)) {
              goto out_unlock;
        }

请问这个判断的依据是什么？

46．如果多个VMA的虚拟页面同时映射了同一个匿名页面，那么此时page->index应该等于多少？

47．为什么Dirty COW小程序可以修改一个只读文件的内容？

48．在Dirty COW内存漏洞中，如果Dirty COW程序没有madviseThread线程，即只有procselfmemThread线程，能否修改foo文件的内容呢？

49．假设在内核空间获取了某个文件对应的page cache页面的struct page数据结构，而对应的VMA属性是只读，那么内核空间是否可以成功修改该文件呢？

50．如果用户进程使用只读属性（PROT_READ）来mmap映射一个文件到用户空间，然后使用memcpy来写这段内存空间，会是什么样的情况？

51．请画出内存管理中常用的数据结构的关系图，如mm_struct、vma、vaddr、page、pfn、pte、zone、paddr和pg_data等，并思考如下转换关系。

❑ 如何由mm数据结构和虚拟地址vaddr找到对应的VMA？

❑ 如何由page和VMA找到虚拟地址vaddr？

❑ 如何由page找到所有映射的VMA？

❑ 如何由VMA和虚拟地址vaddr找出相应的page数据结构？

❑ page和pfn之间的互换。

❑ pfn和paddr之间的互换。

❑ page和pte之间的互换。

❑ zone和page之间的互换。

❑ zone和pg_data之间的互换。

52．请画出在最糟糕的情况下分配若干个连续物理页面的流程图。

53．在Android中新添加了LMK（Low Memory Killer），请描述LMK和OOM Killer之间的关系。

54．请描述一致性DMA映射dma_alloc_coherent()函数在ARM中是如何管理cache一致性的？

55．请描述流式DMA映射dma_map_single()函数在ARM中是如何管理cache一致性的？

56．为什么在Linux 4.8内核中要把基于zone的LRU链表机制迁移到基于Node呢？

很多同学接触Linux的内存管理是从malloc()这个C语言库函数开始的，也是从那时开始就知道了有虚拟内存这个概念，那虚拟内存究竟是什么呢？怎么虚拟？对于只关注上层应用程序编程的同学来说，可能不是太关心这些知识。可是如果不了解一些这方面知识，就很难设计出高效的应用程序。比较早期的操作系统是没有虚拟内存这个概念的，为什么现代操作系统都有虚拟内存这个概念，包括Windows和Linux？要弄明白虚拟内存，你可能需要了解什么是MMU、页表、物理内存、物理页面、建立映射关系、按需分配、缺页中断和写时复制等机制和概念。

当了解MMU时，除了要了解MMU工作原理外，还会接触到Linux内核如何建立页表映射，其中也包括用户空间页表的建立和内核空间页表的建立，以及内核是如何查询页表和修改页表的。

当了解物理内存和物理页面时，会接触到struct pg_data_t、struct zone和struct page等数据结构，这3个数据结构描述了系统中物理内存的组织架构。struct page数据结构除了描述一个4KB大小（或者其他大小）的物理页面外，还包含很多复杂而有趣的成员。

当了解怎么分配物理页面时，会接触到伙伴系统机制和页面分配器（page allocator），页面分配器是内存管理中最复杂的代码之一。

有了物理内存，那怎么和虚拟内存建立映射关系呢？在Linux内核中，描述进程的虚拟内存用struct vm_area_struct数据结构。虚拟内存和物理内存采用建立页表的方法来完成建立映射关系。为什么和进程地址空间建立映射的页面有的叫匿名页面，而有的叫page cache页面呢？

当了解malloc()怎么分配出物理内存时，会接触到缺页中断，缺页中断也是内存管理中最复杂的代码之一。

这时，虚拟内存和物理内存已经建立了映射关系，这是以页为基础的，可是有时内核需要小于一个页面大小的内存，那么slab机制就诞生了。

上面已经建立起虚拟内存和物理内存的基本框图，但是如果用户持续分配和使用内存导致物理内存不足了怎么办？此时页面回收机制和反向映射机制就应运而生了。

虚拟内存和物理内存的映射关系经常是建立后又被解除了，时间长了，系统物理页面布局变得凌乱不堪，碎片化严重，这时内核如果需要分配大块连续内存就会变得很困难，那么内存规整机制（Memory Compaction）就诞生了。

上述是一位笨叔叔学习Linux内核内存管理知识中痛并快乐着的心路历程。

本章主要介绍Linux内核管理中一些基本的知识，包括内存初始化、页表映射过程、内核内存布局图、伙伴系统、slab分配器、vmalloc、VMA操作、malloc、mmap、缺页中断、page引用计数、反向映射、页面回收、匿名页面的宿命、页面迁移、内存规整、KSM、Dirty COW等内容，内存管理包罗万象，本书不可能面面俱到。

本章大部分内容是以ARM Vexpress平台为例来讲述的，如何搭建该实验平台请参考第6.1节。建议读者先阅读第6.1节，并且在Ubuntu 16.04机器上先搭建这样一个简单好用的实验平台，本章列出的一些实验数据可能和读者的数据有些许不同。

除了依照本章列出来的思考题来阅读内存管理代码之外，从用户态的API来深入了解Linux内核的内存管理机制也是一个很好的方法，下面列出常见的用户态内存管理相关的API。

      void *malloc(size_t size);
      void free(void *ptr);

      void *mmap(void *addr, size_t length, int prot, int flags,
                  int fd, off_t offset);
      int munmap(void *addr, size_t length);

      int getpagesize(void);

      int mprotect(const void *addr, size_t len, int prot);

      int mlock(const void *addr, size_t len);
      int munlock(const void *addr, size_t len);

      int madvise(void *addr, size_t length, int advice);
      void *mremap(void *old_address, size_t old_size,
                size_t new_size, int flags, ... /* void *new_address */);

      int remap_file_pages(void *addr, size_t size, int prot,
                  ssize_t pgoff, int flags);

第2.8节讲述malloc()函数在Linux内核的实现，第2.9节讲述mmap()在Linux内核中的实现，第2.17节用到madvise()这个API，相信读者阅读完本章之后会更容易理解这些用户态API的实现。

第2.19节总结了Linux内核内存管理中常用的数据结构之间错综复杂的关系，同时也归纳了内核中常用的内存管理相关的API，相信读者在了解数据结构和API之后对内存管理会有更深刻的理解。

为了行文方便，本章有如下一些约定。

❑ 忽略了对大页面的处理，默认省略了CONFIG_TRANSPARENT_HUGEPAGE的支持。

❑ 默认省略了对锁的讨论，关于锁在内存管理中的应用详见第4.7节。

❑ 对page cache的讨论比较少。

❑ 由于本书的实验对象ARM Vexpress平台不支持NUMA架构，因此为了简化默认，本章忽略了对NUMA相关代码的讨论。

❑ 忽略了对memory cgroup的讨论。