Linux内存管理

一些概念

虚拟地址、物理地址、逻辑地址、线性地址

虚拟地址又叫线性地址，Linux没有采用分段机制，所以逻辑地址和虚拟地址（线性地址）是一个概念，物理地址自不必提。内核的虚拟地址和物理地址，大部分只差一个线性偏移量，用户空间的虚拟地址和物理地址则采用了多级页表进行映射，但仍称之为线性地址。

UMA和NUMA两种模型

共享存储多处理机有两种模型

均匀存储器存取（Uniform-Memory-Access，简称UMA）模型
非均匀存储器存取（Nonuniform-Memory-Access，简称NUMA）模型

UMA模型

物理存储器被所有处理机均匀共享，所有处理机对所有存储字节具有相同的存取时间，这就是为什么称它为均匀存储器存取的原因，每台处理机可以有私用高速缓存，外围设备也以一定形式共享。

NUMA模型

NUMA模式下，处理器被划分为多个节点（node）,每个节点被分配有的本地存储器空间，所有节点中的处理器都可以访问全部的系统物理存储器，但是访问本节点内的存储器需要的时间，比访问某些远程节点内的存储器所花的时间要少得多。

Linux内存结构

Linux把物理内存划分为三个层次来管理

存储节点Node

CPU被划分为多个节点(node), 内存则被分簇, 每个CPU对应一个本地物理内存, 即一个CPU-node对应一个内存簇bank，即每个内存簇被认为是一个节点。

内存被划分为结点. 每个节点关联到系统中的一个处理器, 内核中表示为pg_data_t的实例. 系统中每个节点被链接到一个以NULL结尾的pgdat_list链表中<而其中的每个节点利用pg_data_tnode_next字段链接到下一节．而对于PC这种UMA结构的机器来说, 只使用了一个成为contig_page_data的静态pg_data_t结构.

管理区Zone

每个物理内存结点node被划分为多个内存管理区域，用于表示不同范围的内存，内核可以使用不同的映射方式映射物理内存，那为什么要把Node分成Zone呢

ISA总线的直接内存存储DMA处理器有一个严格的限制 :他们只能对RAM的前16MB进行寻址。
在具有大容量RAM的现代32位计算机中, CPU不能直接访问所有的物理地址, 因为线性地址空间太小, 内核不可能直接映射所有物理内存到线性地址空间。

在x86结构中，Linux内核虚拟地址空间划分0-3G为用户空间，3-4G为内核空间(注意，内核可以使用的线性地址只有1G)。内核虚拟空间（3G - 4G）又划分为三种类型的区：
ZONE_DMA 3G之后起始的16MB
ZONE_NORMAL 16MB-896MB
ZONE_HIGHMEM 896MB-1G

页面Page

内存被细分为多个页面帧，页面是最基本的分配单位，页是用来存储数据的基本单位，内存中的数据都是以页为单位来存储的。

分段机制

在8086处理器诞生之前，内存寻址的方式就是直接访问物理地址的方式，8086处理器为了寻址1M的内存空间，把地址总线扩展到了20位，但是，一个尴尬的问题就出现了，ALU的宽度只有16位，也就是说，ALU不能计算20位的地址，为了解决这个问题，分段机制被引入，登上了历史的舞台。

为了支持分段，8086处理器设置了四个分段寄存器，CS,DS,SS,ES每个段寄存器都是16的，同时访问内存的指令中的地址也是16位的。但是，再送入地址总线之前，CPU先把它与某个段寄存器内的值相加，这里要注意，段寄存器的值对应20位地址总线的中的高16位，所以相加时实际上是16位内存地址的高12位和段寄存器中的16位相加，而低4位保持不变，这样就形成了一个20位的实际地址，也就实现了从16位内存地址到20位实际地址的转换，或者叫“映射”。

分页机制

分页机制是Linux的内存管理机制，分页的节本方法是将地址空间人为的等分为一个个固定大小的页，每一页的大小由硬件来决定，或者是由操作系统来决定，目前，以大小为4KB的分页是绝大多数PC操作系统的选择。

页

为了更高效和更经济的实现内存管理，线性地址被分为以固定长度为单位的组，成为页，页内部连续的线性地址空间被映射到连续的物理地址中，这样，内核可以指定一个页的物理地址和对应的存取权限，而不用指定全部线性地址的存取权限，这里说页，同时指一组线性地址以及这组地址包含的数据。

struct page {
page_flags_t flags; 页标志符
atomic_t _count; 页引用计数
atomic_t _mapcount; 页映射计数
unsigned long private; 私有数据指针
struct address_space *mapping; 该页所在地址空间描述结构指针，用于内容为文件的页帧
pgoff_t index; 该页描述结构在地址空间radix树page_tree中的对象索引号即页号
struct list_head lru; 最近最久未使用struct slab结构指针链表头变量
void *virtual; 页虚拟地址
};

页框

分页单元把所有的RAM分成固定长度的页框。每一个页框包含一个页，也就是说一个页框的长度与一个页的长度一致。页框是主存的一部分，因此也是一个存储区域，区分一页和一个页框是很重要的，前者只是一个数据块，可以存放在任何页框或磁盘中。

页表

页表：把线性地址映射到物理地址的数据结构成为页表（Page table）

内存页分配接口

页分配函数	描述
alloc_pages(gfp_mask, order)	分配2^order个页，返回指向第一页的指针
alloc_pages(gfp_mask)	分配一页，返回指向页的指针
__get_free_pages(gfp_mask, order)	分配2^order个页，返回指向其逻辑地址的指针
__get_free_pages(gfp_mask)	分配一页，返回指向其逻辑地址的指针
__get_zeroed_page(gfp_mask)	分配一页，并填充内容为0；返回指向其逻辑地址指针

页释放函数	描述
__free_pages(page, order)	从page开始，释放2^order个页
free_pages(addr, order)	从地址addr开始，释放2^order个页
free_page(addr)	释放addr所在的那一页

内存字节分配接口

分配函数	区域	连续性	大小	释放函数	优势
kmalloc	内核空间	物理地址连续	最大值128K-16	kfree	性能更佳
vmalloc	内核空间	虚拟地址连续	更大	vfree	更易分配大内存
malloc	用户空间	虚拟地址连续	更大	free

伙伴算法（试着实现过）

如果频繁的申请释放内存，那么内存空间必定会出现许许多多零碎的内存块，造成内存上的浪费，我们怎么解决这个问题呢？

为了避免出现这种情况，Linux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4MB大小的连续内存。

假设要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。

从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。

slab

在Linux中，伙伴系统（buddy system）是以页为单位管理和分配内存。但是现实的需求却以字节为单位，假如我们需要申请20Bytes，总不能分配一页吧！那岂不是严重浪费内存。那么该如何分配呢？slab分配器就应运而生了，专为小内存分配而生。

slab作用

频繁使用的数据结构也会频繁分配和释放，因此应当缓存它们。
解决小内存分配的问题
对存放的对象进行着色( color),以防止多个对象映射到相同的高速缓存行( cache line )。

页面回收/侧重机制

关于页面的使用

内核代码可能调用alloc_pages之类的函数，从管理物理页面的伙伴系统（管理zone上的free_area空闲链表）上直接分配页面。例如：驱动程序可能用这种方式来分配缓存，创建进程时，内核也是通过这种方式分配连续的两个页面，作为进程的thread_info结构和内核栈；等等，从伙伴系统分配页面是最基本的页面分配方式，其他的内存分配都是基于这种方式的；
内核中的很多对象都是用slab机制来管理的，slab就相当于对象池，它将页面格式化成对象，存放在池中供人使用，当slab中的对象不足，slab机制会自动从伙伴系统中分配页面，并格式化成新的对象；
磁盘告诉存储，读写文件时，页面被从伙伴系统分配并用以磁盘告诉缓存，然后磁盘上的文件数据被载入到对应的磁盘高速缓存页面中；
内存映射。这里所谓的内存映射实际上是指将内存页面映射到用户空间，供用户进程使用，进程task_struct->mm结构中的每一个vma就代表着一个映射，而映射的真正实现则是在用户程序访问到对应的内存地址之后，由缺页异常引起的页面被分配和页表被更新；

页面回收简述

有页面分配，就会有页面回收，页面回收的方法大体上可分为两种：

一是主动释放，就是用户程序通过free函数释放曾经通过malloc函数分配的内存一样，页面的使用者明确知道页面是什么时候要被使用，什么时候又不再需要了。上面提到的前两种分配方式，一般都是由内核程序主动释放的，对于直接从伙伴系统分配的页面，这是由使用者使用free_pages之类的函数主动释放的，页面释放后被直接放归伙伴系统，从slab中分配对象，(使用kmem_cache_alloc函数)，也是有使用者主动释放的（使用kmem_cache_free函数）

另一种页面回收方式是通过linux内核提供的页框回收算法（PFRA）进行回收，页面的使用者一般将页面当做某种缓存，以提高系统的运行效率，缓存一直存在固然好，但是如果缓存没有了也不会造成什么错误，仅仅是效率受影响而已，页面的使用者不明确知道这些缓存页面什么时候最好被保留，什么时候最好被回收，这些都交由PFRA来关心。简单来说，PFRA要做的事就是回收这些可以被回收的页面，为了避免系统陷入页面紧缺的困境，PFRA会在内核线程中周期性的被调用执行。或者由于系统以及页面紧缺，试图分配页面的内核执行流程因为得不到需要的页面，而同步地调用PFRA。上面提到的后两种分配方式，一般是由PFRA来进行回收（或者由类似删除文件、进程退出、这样的过程来同步回收）

关于内存映射

前面说到，磁盘高速缓存和内存映射一般由PFRA来进行回收。PFRA对这两者的回收是很类似的，实际上，磁盘高速缓存很可能就被映射到了用户空间。下面简单对内存映射做一些介绍：

内存映射分为文件映射和匿名映射。
文件映射是指代表这个映射的vma对应到一个文件中的某个区域。这种映射方式相对较少被用户态程序显式地使用，用户态程序一般习惯于open一个文件、然后read/write去读写文件。
而实际上，用户程序也可以使用mmap系统调用将一个文件的某个部分映射到内存上（对应到一个vma），然后以访存的方式去读写文件。尽管用户程序较少这样使用，但是用户进程中却充斥着这样的映射：进程正在执行的可执行代码（包括可执行文件、lib库文件）就是以这样的方式被映射的。
实际上，文件映射是将文件的磁盘高速缓存中的页面直接映射到了用户空间（可见，文件映射的页面是磁盘高速缓存页面的子集），用户可以0拷贝地对其进行读写。而使用read/write的话，则会在用户空间的内存和磁盘高速缓存间发生一次拷贝。
匿名映射相对于文件映射，代表这个映射的vma没有对应到文件。对于用户空间普通的内存分配（堆空间、栈空间），都属于匿名映射。
显然，多个进程可能通过各自的文件映射来映射到同一个文件上（比如大多数进程都映射了libc库的so文件）；那匿名映射呢？实际上，多个进程也可能通过各自的匿名映射来映射到同一段物理内存上，这种情况是由于fork之后父子进程共享原来的物理内存（copy-on-write）而引起的。

文件映射又分为共享映射和私有映射。私有映射时，如果进程对映射的地址空间进行写操作，则映射对应的磁盘高速缓存并不会直接被写。而是将原有内容复制一份，然后再写这个复制品，并且当前进程的对应页面映射将切换到这个复制品上去（写时复制）。也就是说，写操作是只有自己可见的。而对于共享映射，写操作则会影响到磁盘高速缓存，是大家都可见的。

确定最近最少使用

现在就有一个问题了，怎么确定active/inactive链表中哪些页面是最近最少使用的呢？
一种方法是排序，当页面被访问时，将其移动到链表的尾部（假设回收从头部开始）。但是这就意味着页面在链表中的位置可能频繁移动，并且移动之前还必须先上锁（可能有多个CPU在同时访问），这样做对效率影响很大。
linux内核采用的是标记加顺序的办法。当页面在active和inactive两个链表之间移动时，总是将其放到链表的尾部（同上，假设回收从头部开始）。
页面没有在链表间移动时，并不会调整它们的顺序。而是通过访问标记来表示页面是否刚被访问过。如果inactive链表中已设置访问标记的页面再被访问，则将其移动到active链表中，并且清除访问标记。（实际上，为了避免访问冲突，页面并不会直接从inactive链表移动到active链表，而是有一个pagevec中间结构用作缓冲，以避免锁链表。）

页面的访问标记有两种情况，一是放在page->flags中的PG_referenced标记，在页面被访问时该标记置位。对于磁盘高速缓存中（未被映射）的页面，用户进程通过read、write之类的系统调用去访问它们，系统调用代码中会将对应页面的PG_referenced标记置位。
而对于内存映射的页面，用户进程可以直接访问它们（不经过内核），所以这种情况下的访问标记不是由内核来设置的，而是由mmu。在将虚拟地址映射成物理地址后，mmu会在对应的页表项上置一个accessed标志位，表示页面被访问。（同样的道理，mmu会在被写的页面所对应的页表项上置一个dirty标志，表示页面是脏页面。）
页面的访问标记（包括上面两种标记）将在PFRA处理页面回收的过程中被清除，因为访问标记显然是应该有有效期的，而PFRA的运行周期就代表这个有效期。page->flags中的PG_referenced标记可以直接清除，而页表项中的accessed位则需要通过页面找到其对应的页表项后才能清除（见下文的“反向映射”）。

那么，回收过程又是怎样扫描LRU链表的呢？
由于存在多组LRU（系统中有多个zone，每个zone又有多组LRU），如果PFRA每次回收都扫描所有的LRU找出其中最值得回收的若干个页面的话，回收算法的效率显然不够理想。
linux内核PFRA使用的扫描方法是：定义一个扫描优先级，通过这个优先级换算出在每个LRU上应该扫描的页面数。整个回收算法以最低的优先级开始，先扫描每个LRU中最近最少使用的几个页面，然后试图回收它们。如果一遍扫描下来，已经回收了足够数量的页面，则本次回收过程结束。否则，增大优先级，再重新扫描，直到足够数量的页面被回收。而如果始终不能回收足够数量的页面，则优先级将增加到最大，也就是所有页面将被扫描。这时，就算回收的页面数量还是不足，回收过程都会结束。

每次扫描一个LRU时，都从active链表和inactive链表获取当前优先级对应数目的页面，然后再对这些页面做处理：如果页面不能被回收（如被保留或被上锁），则放回对应链表头部（同上，假设回收从头部开始）；否则如果页面的访问标记置位，则清除该标记，并将页面放回对应链表尾部（同上，假设回收从头部开始）；否则页面将从active链表被移动到inactive链表、或从inactive链表被回收。

被扫描到的页面根据访问标记是否置位来决定其去留。那么这个访问标记是如何设置的呢？有两个途径，一是用户通过read/write之类的系统调用访问文件时，内核操作磁盘高速缓存中的页面，会设置这些页面的访问标记（设置在page结构中）；二是进程直接访问已映射的页面时，mmu会自动给对应的页表项加上访问标记（设置在页表的pte中）。关于访问标记的判断就基于这两个信息。（给定一个页面，可能有多个pte引用到它。如何知道这些pte是否被设置了访问标记呢？那就需要通过反向映射找到这些pte。下面会讲到。）
PFRA不倾向于从active链表回收匿名映射的页面，因为用户进程使用的内存一般相对较少，且回收的话需要进行交换，代价较大。所以在内存剩余较多、匿名映射所占比例较少的情况下，都不会去回收匿名映射对应的active链表中的页面。（而如果页面已经被放到inactive链表中，就不再去管那么多了。）

反向映射

像这样，在PFRA处理页面回收的过程中，LRU的inactive链表中的某些页面可能就要被回收了。
如果页面没有被映射，直接回收到伙伴系统即可（对于脏页，先写回、再回收）。否则，还有一件麻烦的事情要处理。因为用户进程的某个页表项正引用着这个页面呢，在回收页面之前，还必须给引用它的页表项一个交待。
于是，问题就来了，内核怎么知道这个页面被哪些页表项所引用呢？为了做到这一点，内核建立了从页面到页表项的反向映射。
通过反向映射可以找到一个被映射的页面对应的vma，通过vma->vm_mm->pgd就能找到对应的页表。然后通过page->index得到页面的虚拟地址。再通过虚拟地址从页表中找到对应的页表项。（前面说到的获取页表项中的accessed标记，就是通过反向映射实现的。）

页面对应的page结构中，page->mapping如果最低位置位，则这是一个匿名映射页面，page->mapping指向一个anon_vma结构；否则是文件映射页面，page->mapping文件对应的address_space结构。（显然，anon_vma结构和address_space结构在分配时，地址必须要对齐，至少保证最低位为0。）
对于匿名映射的页面，anon_vma结构作为一个链表头，将映射这个页面的所有vma通过vma->anon_vma_node链表指针连接起来。每当一个页面被（匿名）映射到一个用户空间时，对应的vma就被加入这个链表。
对于文件映射的页面，address_space结构除了维护了一棵用于存放磁盘高速缓存页面的radix树，还为该文件映射到的所有vma维护了一棵优先搜索树。因为这些被文件映射到的vma并不一定都是映射整个文件，很可能只映射了文件的一部分。所以，这棵优先搜索树除了索引到所有被映射的vma，还要能知道文件的哪些区域是映射到哪些vma上的。每当一个页面被（文件）映射到一个用户空间时，对应的vma就被加入这个优先搜索树。于是，给定磁盘高速缓存上的一个页面，就能通过page->index得到页面在文件中的位置，就能通过优先搜索树找出这个页面映射到的所有vma。

上面两步中，神奇的page->index做了两件事，得到页面的虚拟地址、得到页面在文件磁盘高速缓存中的位置。
vma->vm_start记录了vma的首虚拟地址，vma->vm_pgoff记录了该vma在对应的映射文件（或共享内存）中的偏移，而page->index记录了页面在文件（或共享内存）中的偏移。
通过vma->vm_pgoff和page->index能得到页面在vma中的偏移，加上vma->vm_start就能得到页面的虚拟地址；而通过page->index就能得到页面在文件磁盘高速缓存中的位置。

页面换入换出

在找到了引用待回收页面的页表项后，对于文件映射，可以直接把引用该页面的页表项清空。等用户再访问这个地址的时候触发缺页异常，异常处理代码再重新分配一个页面，并去磁盘里面把对应的数据读出来就行了（说不定，页面在对应的磁盘高速缓存里面已经有了，因为其他进程先访问过）。这就跟页面映射以后，第一次被访问的情形一样；
对于匿名映射，先将页面写回到交换文件，然后还得在页表项中记录该页面在交换文件中的index。
页表项中有一个present位，如果该位被清除，则mmu认为页表项无效。在页表项无效的情况下，其他位不被mmu关心，可以用来存储其他信息。这里就用它们来存储页面在交换文件中的index了（实际上是交换文件号+交换文件内的索引号）。

将匿名映射的页面交换到交换文件的过程（换出过程）与将磁盘高速缓存中的脏页写回文件的过程很相似。
交换文件也有其对应的address_space结构，匿名映射的页面在换出时先被放到这个address_space对应磁盘高速缓存中，然后跟脏页写回一样，被写回到交换文件中。写回完成后，这个页面才被释放（记住，我们的目的是要释放这个页面）。
那么为什么不直接把页面写回到交换文件，而要经过磁盘高速缓存呢？因为，这个页面可能被映射了多次，不可能一次性把所有用户进程的页表中对应的页表项都修改好（修改成页面在交换文件中的索引），所以在页面被释放的过程中，页面被暂时放在磁盘高速缓存上。
而并不是所有页表项的修改过程都是能成功的（比如在修改之前页面又被访问了，于是现在又不需要回收这个页面了），所以页面放到磁盘高速缓存的时间也可能会很长。

同样，将匿名映射的页面从交换文件读出的过程（换入过程）也与将文件数据读出的过程很相似。
先去对应的磁盘高速缓存上看看页面在不在，不在的话再去交换文件里面读。文件里的数据也是被读到磁盘高速缓存中的，然后用户进程的页表中对应的页表项将被改写，直接指向这个页面。
这个页面可能不会马上从磁盘高速缓存中拿下来，因为如果还有其他用户进程也映射到这个页面（它们的对应页表项已经被修改成了交换文件的索引），他们也可以引用到这里。直到没有其他的页表项再引用这个交换文件索引时，页面才可以从磁盘高速缓存中被取下来。

最后的必杀

前面说到，PFRA可能扫描了所有的LRU还没办法回收需要的页面。同样，在slab、dentry cache、inode cache、等地方，可能也无法回收到页面。
这时，如果某段内核代码一定要获得页面呢（没有页面，系统可能就要崩溃了）？PFRA只好使出最后的必杀技——OOM（out of memory）。所谓的OOM就是寻找一个最不重要的进程，然后将其杀死。通过释放这个进程所占有的内存页面，以缓解系统压力。

参考：
Linux内存管理原理
 史上最全linux内存管理