kk Blog —— 通用基础

http://blog.csdn.net/ustc_dylan/article/details/7079876

1. 从源安装systemtap

1

$ sudo apt-get install systemtap

2. 安装kernel-debug-info

由于ubuntu 桌面版默认没有安装kernel-debug-info，所以安装了systemtap后仍然不能够追踪内核信息，因此需要手动安装kernel-debug-info包。

（1）查看当前内核版本

1
2

$ uname -a
Linux kk-desktop 2.6.32-73-generic #141-Ubuntu SMP Tue Mar 10 17:15:10 UTC 2015 x86_64 GNU/Linux

（2）下载对应内核版本的debug-info package

http://ddebs.ubuntu.com/pool/main/l/linux/

http://ddebs.ubuntu.com/pool/main/l/linux/linux-image-2.6.32-73-generic-dbgsym_2.6.32-73.141_amd64.ddeb

3. 安装kernel-debug-info

1

$ sudo dpkg -i linux-image-2.6.32-73-generic-dbgsym_2.6.32-73.141_amd64.ddeb

经过以上安装配置后，就可以跟踪监控内核信息了，但是现在还不能跟踪linux内核模块的信息，因为，systemtap对linux内核模块的跟踪是通过libelf库来查找 /usr/lib/debug目录下以.ko.dedug结尾的模块，但是linux发行版通常将linux模块的扩展名修改为.ko。

4. 安装elfutils并进行相应配置

1

$ sudo apt-get install elfutils

1
2
3
4
5
6
7
8
9
10
11

# 这些似乎不用
for file in `find /usr/lib/debug-name'*.ko' -print`
do
	buildid=`eu-readelf-n $file| grep Build.ID:| awk '{print $3}'`
	dir=`echo $buildid| cut-c1-2`
	fn=`echo $buildid| cut-c3-`
	rm -fr /usr/lib/debug/.build-id
	mkdir -p/usr/lib/debug/.build-id/$dir
	ln -s $file/usr/lib/debug/.build-id/$dir/$fn
	ln -s $file/usr/lib/debug/.build-id/$dir/${fn}.debug
done

5. 写个例子测试下

1

$ sudo stap -ve 'probe begin { log("hello world") exit() }'

如果能够打印出hello world，说明安装配置成功!

blog.tek-life.com/认识linux物理内存回收机制/

Introduction

本文所讲的物理页面回收是指动态的回收：即，空闲的内存不够用的时候，系统采取相应的方法将正在使用的内存释放，补充空闲内存，以满足内存的分配。

Text

1.All channels for page freeing。首先先简单看一下系统中的内存释放的三种渠道。

1-1>. 在用户进程退出的时候，释放内存。当用户进程退出的时候，会调用do_exit. do_exit最终会调用free_pagetables函数。该函数的作用是：遍历vma，根据vma中的虚拟地址找到实际的物理页，将其释放。在之前讲过，对于用户进程的虚拟地址区间，是以红黑树组织的。

1-2>. 手动的释放。在驱动中，分配内存使用alloc_pages()，释放内存用free_pages(这一点，类似于c语言中的malloc和free)。必须配对使用。否则会造成内存泄漏。

1-3>. 按需求调用内存回收例程来释放内存。这个区别于前两种的最大不同：它是动态的，按需的。当内存不够的时候，系统会自动按照一定的方式，将某些正在使用的内存释放掉，放进buddy system中再利用。

2. Overview for page frame reclaiming。

2-1>. 先来看一下内存将会回收哪些页面
用户进程的页面都是通过page fault进行分配的。通过page fault进行分配的页面都是可以进行回收的。 这些页面总体可以划分为两种，分别是文件页(file cache)和匿名页(anonymous cache). 文件页，顾名思义，它是和外部存储设备上的某个文件相对应。匿名页，其内容不来自于外部存储设备，例如用户进程中的堆栈。这两种页面是内存回收的目标页面。

2-2>. 内存回收采用的主要算法是近似于LRU的算法。位于LRU链表前面的页是活跃的，位于LRU链表后面的页是不活跃的。为什么说是近似呢？
1. 页面在链表上排序并不是严格依据LRU不断移动的。他们挂上去后是不移动的。除非在进行页面回收的时候，有些页面从后面，可能会插入到前面；
2. Linux在LRU的基础上又引入了一个Referrenced标志。这种带Referenced标志的近似LRU的算法被有些人称之为Second-Chance Algorithm.

简单看一下Second-Chance Algorithm. 当一个页从一个LRU链表上除去的时候，需要再看一下Referenced标志。如果该标志设置了，就将其置为0，不能将该页移出。

图1

以图一为例，当某个页面被访问后，Referenced标志被设置。当需要从该list上面回收某些页时，从后向前扫描该list上的页面。对于那些设置为1(Referenced标志被设置)，reset为0，不被移出链表。对于那些设置为0的页面，移出链表。

2-3>. Linux为了实现该算法，给每个zone都提供了5个LRU链表。这5个LRU链表分为3类，一类是活跃链表(active list)，活跃链表有两个：一个是链接file page cache的LRU list, 另一个是链接anonymous page cache的LRU list. 另一类是非活跃链表(inactive list)，非活跃链表也有两个：一个是链接file page cache 的LRU list, 另一个是链接anonymous page cache的LRU list. 内存回收例程从inactive list链表上获取页进行回收。第三类是unevictable链表，这个链表上挂载的是那些被mlock()或者locked的页面。Mlock(),是一个系统调用，用户程序通过该系统调用锁定某些页阻止系统将其换出。被Locked的页面通常是文件系统防止其他进程touch的页面。被锁定的页面都挂载unevictable链表上。

加入到active list链表上的页其page->flags上都要设置PG_active标志。凡是设置了PG_unevictable标志的都要挂载unevictable LRU list上。没有设置PG_active/PG_unevictable标志的都处于inactive状态。处于相关状态的页面通过page->lru 链接到对应的链表上。

当某个页被访问后，提高该页面的活跃度。提高活跃度的方法是:或者对page->flags设置PG_referenced标志，或者对page->flags设置PG_active(同时该物理页面从inactive_list链表上转移到active_list链表上). 有PG_referenced和PG_active标志，可以得到页面的状态，该活跃度由低到高依次为：00->01->10->11

2-4>. 对于一个可回收页面，按照LRU的算法，只有处于inactive状态的页并且没有设置PG_referenced标志位的页才能被回收。但实际上Linux在实现的时候并没有严格按照这中算法，PG_referenced位只是用来参考的。从下面的状态转换图中可以看出这一点。状态转换图一共有4种状态。

图2

当页面通过page fault被分配的时候，file page cache 被加入到非活动链表中(inactive list)， 匿名页(anonymous page cache)被加入到活动链表中(active list)。该状态迁移图所涉及的函数主要有以下几个：shrink_active_list，make_page_accessed，page_check_references。

1)当inactive链表上的页数不够的时候，会调用shrink_active_list，该函数会将active链表上的页move到inactive链表上。对应于上图标号为1的转移；

2). make_page_accessed().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

355 /*
356  * Mark a page as having seen activity.
357  *
358  * inactive,unreferenced        ->      inactive,referenced
359  * inactive,referenced          ->      active,unreferenced
360  * active,unreferenced         ->      active,referenced
361  */
362 void mark_page_accessed(struct page *page)
363 {
364         if (!PageActive(page) && !PageUnevictable(page) &&
365                         PageReferenced(page) && PageLRU(page)) {
366                 activate_page(page);
367                 ClearPageReferenced(page);
368         } else if (!PageReferenced(page)) {
369                 SetPageReferenced(page);
370         }
371 }
372 EXPORT_SYMBOL(mark_page_accessed);

当通过read()系统调用或者读已经在cache中的页面时，会提高页面的活跃度。对应于上图标号为2的转移(00->01->10->11)； 3) shrink_page_list->page_check_references()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

704 static enum page_references page_check_references(struct page *page,
705                                                   struct mem_cgroup_zone *mz,
706                                                   struct scan_control *sc)
707 {
708         int referenced_ptes, referenced_page;
709         unsigned long vm_flags;
710
711         referenced_ptes = page_referenced(page, 1, mz->mem_cgroup, &vm_flags);
712         referenced_page = TestClearPageReferenced(page);
713
714         /* Lumpy reclaim – ignore references */
715         if (sc->reclaim_mode & RECLAIM_MODE_LUMPYRECLAIM)
716                 return PAGEREF_RECLAIM;
717
718         /*
719          * Mlock lost the isolation race with us.  Let try_to_unmap()
720          * move the page to the unevictable list.
721          */
722         if (vm_flags & VM_LOCKED)
723                 return PAGEREF_RECLAIM;
724
725         if (referenced_ptes) {
726                 if (PageAnon(page))
727                         return PAGEREF_ACTIVATE;
728                 /*
729                  * All mapped pages start out with page table
730                  * references from the instantiating fault, so we need
731                  * to look twice if a mapped file page is used more
732                  * than once.
733                  *
734                  * Mark it and spare it for another trip around the
735                  * inactive list.  Another page table reference will
736                  * lead to its activation.
737                  *
738                  * Note: the mark is set for activated pages as well
739                  * so that recently deactivated but used pages are
740                  * quickly recovered.
741                  */
742                 SetPageReferenced(page);
743
744                 if (referenced_page || referenced_ptes > 1)
745                         return PAGEREF_ACTIVATE;
746
747                 /*
748                  * Activate file-backed executable pages after first usage.
749                  */
750                 if (vm_flags & VM_EXEC)
751                         return PAGEREF_ACTIVATE;
752
753                 return PAGEREF_KEEP;
754         }
755
756         /* Reclaim if clean, defer dirty pages to writeback */
757         if (referenced_page && !PageSwapBacked(page))
758                 return PAGEREF_RECLAIM_CLEAN;
759
760         return PAGEREF_RECLAIM;
761 }

该函数被真正的页面回收函数shrink_page_list调用。所处理的对象是处于inactive状态的页面。分以下几种情况：

3-a). 如果是匿名页，并且最近被访问过(PTE_young置位)，对应3-a的转移(Line 726)。即(inactive+PG_referenced)->active，inactive->active. (01->10或者00->10).

3-b). 如果是已经映射的文件页,最近被访问过(PTE_young置位)，如果PG_referenced置位或者被两个进程最近访问过(这一点不知道理解的对否)(Line 744~745)，对应于3-b的转移(01->11)。

3-c). 如果是已经映射的文件页,最近被访问过(PTE_young置位), 并且该page cache中的内容是可执行的(例如，用户进程的代码段)，则inactive->(active+PG_referenced).(00->11, 01->11)

3-d). 如果是已经映射的文件页,最近被访问过(PTE_young置位), 则，设置PG_referenced标志，仍旧保留inactive状态，不进行回收。(00->01,01-01)

3-e). 除了以上情况，均进行回收。即：最近没有被访问过(PTE_YOUNG没有设置)的匿名页和文件页。

对于page_check_references()中的返回值，简单介绍一下：
PAGEREF_RECLAIM：进行回收；
PAGEREF_RECLAIM_CLEAN：若该页是干净的(clean)，则进行回收；
PAGEREF_KEEP：仍然保持在inactive LRU list上，不进行回收。
PAGEREF_ACTIVATE：不进行回收，并将该页转移到active LRU list上。

2-5>. 由以上的状态转换图，简单了解一下一个可回收的物理页面可能的生命周期。

Free->inactive->[active]<–>inactive->reclaimable->free

对于一个文件页，其在buddy system中未被分配时，处于free状态。当被分配后，首先挂载在inactive LRU list上。若被进程访问，便会被active。当一段时间没有被访问后，就处于inactive状态，挂载在inactive 链表上等待回收。被回收例程回收后，就进入buddy system中，回归到free状态。

Free->Active<–>[inactive]->reclaimable->free

对于一个匿名页，通过page fault被分配后，挂载在active链表上，然后经过deactive变为inactive然后被回收进buddy system中。

对于匿名页和文件页，刚被分配后所设置的状态，可以得出：系统总是想尽快老化文件页面。在系统的眼中，文件页的换出成本要低于匿名页。

3. Synchronization Reclaiming

当内存分配不足的时候，内存回收例程就会被调用了。相关的代码在__alloc_pages中。

图3

若分配失败，就会进入到__alloc_pages_slowpath中。

图4

该函数功能正如其名字所属，属于slow path。首先会唤醒各个node上的kswapd例程。kswapd是一个kernel thread,每一个node都有一个例程。该例程的函数体是kswapd().该例程会在第4节中降到。唤醒kwspad后，尝试重新调用get_page_from_freelist，分配内存。若失败，继续往下，如果需要分配内存的主儿在系统中的地位比较重要的话，会调用__alloc_pages_high_priority(). 该函数不会顾及系统设置的安全警告线(min water mark. 对于1GB左右的内存是min water mark是16MB)，分配内存。如果仍然失败；则会调用__alloc_pages_direct_compat来migrate内存来达到compat的目的。这个内存的compat类似于磁盘的压缩整理，把在物理内存中正在使用的分散内存，给迁移整合，以便腾出大的连续的物理内存，满足某些进程大页面的需求。需要注意的是，压缩内存需要在build kernel的时候enable CONFIG_COMPACTION。若仍然失败，就调用__alloc_pages_direct_reclaim来回收内存了。回收内存后，会继续调用get_page_from_freelist,尝试看是否能否分配成功。如果仍然失败，并且分配内存的时候要求不允许失败，那么就进入OOM中。OOM主要的功能是选择一个占用内存量比较大的用户进程，杀掉以释放内存。释放结束后，跳到__alloc_pages_slowpath函数的开头，重新执行一遍，以满足内存分配。如果，允许内存分配失败，则就不会OOM了。以分配失败返回给调用者。

__alloc_pages_direct_reclaim函数主要调用try_to_free_pages.

图5

try_to_free_pages()做的事情是，按照自定义的优先级从12开始，递减循环（优先级越小代表级别越高，回收的程度越剧烈）从要分配内存的zone以及其fall-back zone list中回收可用内存释放到buddy system中。它通过调用shrink_zones来达到依次扫描zone以及fall-back zone list的目的。对各个zone进行回收结束后，对slab也进行回收（本文不对slab的回收做分析）。如果至此，已经回收了足够多的内存（32个页），那么就返回。如果没有回收到32个页，则是否需要唤醒pdflush进程，该进程的作用是唤醒块设备的读写进程将脏页写到块设备上。唤醒pdflush的条件是看是否扫描了超过48个页。之后，如果这是的扫描优先级已经小于10了，那么睡眠1/10HZ，即1S.然后递减优先级，进行下一遍的循环。

图6

图7

图8

关于swap cache的作用，请看下图（图9）。

图9

有关对swap cache 作用的描述，最靠谱的分析是来自Understanding Linux Kernel. 摘录如下：
Consider a page P that is shared among two processes, A and B. Initially, the Page Table entries of both processes contain a reference to the page frame, and the page has two owners; this case is illustrated in Figure 17-8(a). When the PFRA selects the page for reclaiming, shrink_list( ) inserts the page frame in the swap cache. As illustrated in Figure 17-8(b), now the page frame has three owners, while the page slot in the swap area is referenced only by the swap cache. Next, the PFRA invokes try_to_unmap( ) to remove the references to the page frame from the Page Table of the processes; once this function terminates, the page frame is referenced only by the swap cache, while the page slot is referenced by the two processes and the swap cache, as illustrated in Figure 17-8©. Let’s suppose that, while the page’s contents are being written to disk, process B accesses the pagethat is, it tries to access a memory cell using a linear address inside the page. Then, the page fault handler finds the page frame in the swap cache and puts back its physical address in the Page Table entry of process B, as illustrated in Figure 17-8(d). Conversely, if the swap-out operation terminates without concurrent swap-in operations,the shrink_list( ) function removes the page frame from the swap cache and releases the page frame to the Buddy system, as illustrated in Figure 17-8(e).

Remark:

1. Figure 17-8 请对照图9.
2. 上图的函数都是来自于2.6.11内核。本文所参考的内核是3.4.因此引用中的函数可能和本文所述的函数不匹配。

4. Asynchronization reclaiming.

References

1. Understanding Linux Kernel (3rd).
2. Understanding virtual memory manager (2nd).
3. Professional Linux Kernel Architecture.

blog.csdn.net/dlutbrucezhang/article/details/9058583

虚拟内存

一

1. 每个进程都有自己独立的4G内存空间，各个进程的内存空间具有类似的结构
2. 一个新进程建立的时候，将会建立起自己的内存空间，此进程的数据，代码等从磁盘拷贝到自己的进程空间，哪些数据在哪里，都由进程控制表中的task_struct记录，task_struct中记录中一条链表，记录中内存空间的分配情况，哪些地址有数据，哪些地址无数据，哪些可读，哪些可写，都可以通过这个链表记录
3. 每个进程已经分配的内存空间，都与对应的磁盘空间映射

二

1. 每个进程的4G内存空间只是虚拟内存空间，每次访问内存空间的某个地址，都需要把地址翻译为实际物理内存地址
2. 所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。
3. 进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，需要用页表来记录
4. 页表的每一个表项分两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存页的地址（如果在的话）
5. 当进程访问某个虚拟地址，去看页表，如果发现对应的数据不在物理内存中，则缺页异常
6. 缺页异常的处理过程，就是把进程需要的数据从磁盘上拷贝到物理内存中，如果内存已经满了，没有空地方了，那就找一个页覆盖，当然如果被覆盖的页曾经被修改过，需要将此页写回磁盘

总结

优点：
1.既然每个进程的内存空间都是一致而且固定的，所以链接器在链接可执行文件时，可以设定内存地址，而不用去管这些数据最终实际的内存地址，这是有独立内存空间的好处
2.当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存
3.在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片。

另外，事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

补充理解

虚拟存储器涉及三个概念： 虚拟存储空间，磁盘空间，内存空间

可以认为虚拟空间都被映射到了磁盘空间中，（事实上也是按需要映射到磁盘空间上，通过mmap），并且由页表记录映射位置，当访问到某个地址的时候，通过页表中的有效位，可以得知此数据是否在内存中，如果不是，则通过缺页异常，将磁盘对应的数据拷贝到内存中，如果没有空闲内存，则选择牺牲页面，替换其他页面。

mmap是用来建立从虚拟空间到磁盘空间的映射的，可以将一个虚拟空间地址映射到一个磁盘文件上，当不设置这个地址时，则由系统自动设置，函数返回对应的内存地址（虚拟地址），当访问这个地址的时候，就需要把磁盘上的内容拷贝到内存了，然后就可以读或者写，最后通过manmap可以将内存上的数据换回到磁盘，也就是解除虚拟空间和内存空间的映射，这也是一种读写磁盘文件的方法，也是一种进程共享数据的方法 共享内存

物理内存

在内核态申请内存比在用户态申请内存要更为直接，它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存，那么就必须立刻满足该申请内存的请求，并且这个请求一定是正确合理的。相反，对于用户态申请内存的请求，内核总是尽量延后分配物理内存，用户进程总是先获得一个虚拟内存区的使用权，最终通过缺页异常获得一块真正的物理内存。

一、物理内存的内核映射

IA32架构中内核虚拟地址空间只有1GB大小（从3GB到4GB），因此可以直接将1GB大小的物理内存（即常规内存）映射到内核地址空间，但超出1GB大小的物理内存（即高端内存）就不能映射到内核空间。为此，内核采取了下面的方法使得内核可以使用所有的物理内存。

1). 高端内存不能全部映射到内核空间，也就是说这些物理内存没有对应的线性地址。不过，内核为每个物理页框都分配了对应的页框描述符，所有的页框描述符都保存在mem_map数组中，因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存，因为这些函数返回页框描述符的线性地址。

2). 内核地址空间的后128MB专门用于映射高端内存，否则，没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的，否则也只能映射128MB的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射，使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射，因此直接能够映射的物理内存大小只有896MB，该值保存在high_memory中。内核地址空间的线性地址区间如下图所示：

从图中可以看出，内核采用了三种机制将高端内存映射到内核空间：永久内核映射，固定映射和vmalloc机制。

二、物理内存管理机制

基于物理内存在内核空间中的映射原理，物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法，slab高速缓存和vmalloc机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存，而vmalloc机制则在高端内存映射区分配物理内存。

伙伴算法
伙伴算法负责大块连续物理内存的分配和释放，以页框为基本单位。该机制可以避免外部碎片。

per-CPU页框高速缓存
内核经常请求和释放单个页框，该缓存包含预先分配的页框，用于满足本地CPU发出的单一页框请求。

slab缓存
slab缓存负责小块物理内存的分配，并且它也作为高速缓存，主要针对内核中经常分配并释放的对象。

vmalloc机制
vmalloc机制使得内核通过连续的线性地址来访问非连续的物理页框，这样可以最大限度的使用高端物理内存。

三、物理内存的分配

内核发出内存申请的请求时，根据内核函数调用接口将启用不同的内存分配器。

3.1 分区页框分配器

分区页框分配器 (zoned page frame allocator) ,处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统，如下图：

管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过per-CPU页框高速缓存完成。

该分配器通过几个函数和宏来请求页框,它们之间的封装关系如下图所示。

这些函数和宏将核心的分配函数__alloc_pages_nodemask()封装,形成满足不同分配需求的分配函数。其中，alloc_pages()系列函数返回物理内存首页框描述符，__get_free_pages()系列函数返回内存的线性地址。

3.2 slab分配器

slab 分配器最初是为了解决物理内存的内部碎片而提出的，它将内核中常用的数据结构看做对象。slab分配器为每一种对象建立高速缓存。内核对该对象的分配和释放均是在这块高速缓存中操作。一种对象的slab分配器结构图如下：

可以看到每种对象的高速缓存是由若干个slab组成，每个slab是由若干个页框组成的。虽然slab分配器可以分配比单个页框更小的内存块，但它所需的所有内存都是通过伙伴算法分配的。

slab高速缓存分专用缓存和通用缓存。专用缓存是对特定的对象，比如为内存描述符创建高速缓存。通用缓存则是针对一般情况，适合分配任意大小的物理内存，其接口即为kmalloc()。

3.3 非连续内存区内存的分配

内核通过vmalloc()来申请非连续的物理内存，若申请成功，该函数返回连续内存区的起始地址，否则，返回NULL。vmalloc()和kmalloc()申请的内存有所不同，kmalloc()所申请内存的线性地址与物理地址都是连续的，而vmalloc()所申请的内存线性地址连续而物理地址则是离散的，两个地址之间通过内核页表进行映射。 vmalloc()的工作方式理解起来很简单：
1). 寻找一个新的连续线性地址空间；
2). 依次分配一组非连续的页框；
3). 为线性地址空间和非连续页框建立映射关系，即修改内核页表；

vmalloc()的内存分配原理与用户态的内存分配相似，都是通过连续的虚拟内存来访问离散的物理内存，并且虚拟地址和物理地址之间是通过页表进行连接的，通过这种方式可以有效的使用物理内存。但是应该注意的是，vmalloc()申请物理内存时是立即分配的，因为内核认为这种内存分配请求是正当而且紧急的；相反，用户态有内存请求时，内核总是尽可能的延后，毕竟用户态跟内核态不在一个特权级。

os.51cto.com/art/201310/412758_all.htm

内存的回收在Linux内存管理中占据非常重要的地位，系统的内存毕竟是有限的，跑的进程成百上千，系统内存越来越小，我们必须选择一些内存进行回收，以满足别的任务的需求。在内存回收过程中，有哪些内存可以回收，什么时候进行回收，回收内存时如何尽可能的减少对系统性能的影响，回收内存的策略，这些是我们着重要关注的问题，也是本文主要阐述的重点。

1.1 内存回收的目标

不是所有的物理内存都可以参与回收的，比如要是把内核代码段的内存给回收了，系统就无法正常运行了，一般内核代码段，数据段，内核kmalloc()出来的内存，内核线程占用的内存等都是不可以回收的，除此之外的内存都是我们要回收的目标。

回收的内存主要是由用户态进程占用的内存和内核自己在运行时所使用的一些内存组成。用户态进程占用的内存主要是我们常见的进程代码段，数据段，堆栈等，内核运行使用的内存主要是磁盘高速缓存(如索引节点，目录项高速缓存），页面高速缓存(访问文件时系统生成的页面cache)，mmap()文件时所用的有名映射所使用的物理内存。后面的这些内才能虽然也是内核管理使用的内存，但对其进行回收的时候，顶多影响内核的性能，而不会导致系统无法运行。

1.2 内存回收的时机

1、内存紧缺回收：grow_buffers()无法获取缓冲区页，alloc_page_buffers()无法获取页临时缓冲区首部，__alloc_pages()无法再给定的内存区分配一组连续页框。

2、周期回收：必要时，激活相应内核线程执行内存回收算法：kswapd()内核线程，检查某个内存管理区的空闲页框数是否已低于pages_high值的标高。events内核线程，一个工作者线程，回收位于高速内存缓存中的所有空闲的slab。

1.3 内存回收的策略

1.3.1 内存回收的分类

内存回收主要是要回收两类内存：最近最少使用的内存以及高速内存缓存中空闲的slab。前者主要包括用户态进程的代码段，数据段，堆栈，文件映射内存，页高速内存，后者主要包括磁盘高速缓存及一些其他的空闲内存高速缓存。

最近最少使用内存存放在一个lru链表上，每个内存管理区zone都有一个lru结构，里面含有active和inactive两个链表头，active链表上记录当前的活跃的报文，inactive用来记录当前不活跃的报文。一般我们回首lru上的inactive链表上的内存页。同时，在内存回收的过程中，会从active链表向inactive链表上补充对应的最近最少使用内存页。每个内存页的内核数据结构page上有一个标记位PG_referenced,该标记位使得一个页从"不活动“状态转为”活动“状态的时间加倍，反之亦然。比如:一个页面可能1个小时内没人反应，不能因为偶然的一次访问就认为它是活跃的，得两次才认为它是一个活跃的页面。下面是页面在inactive和active链表上转移的变化图。

Slab内存高速缓存中经常会有一些完全空闲的slab，这些是我们回收的另一个目标。

1.3.2 反向映射

对于可以通过用户态线性地址空间可以直接访问到的物理页来说，可以分为匿名页和文件映射页两类，匿名页指的是不与具体文件对应映射的物理页，比如代码段，堆栈等使用的物理页，映射页指的是映射到文件某一部分的物理页，通常使用mmap()来进行相关的映射。

对于匿名映射和文件映射来说，可能一段物理内存会在多个进程的页表中使用，比如对于匿名映射，fork()一个进程，一开始会共用父进程的物理内存，对于文件映射，多个进程可能同时映射到一个文件的同一部分文件。所以在页面回收时，需要将该页面在所有的页表引用中给去除掉。这种手段称为反向映射。想要找到使用这些物理页的页表项的话，需要先找到引用他们的页表，而页表的地址记录在每个进程的内存描述符里面，同时用来描述进程用户态地址空间的每个vm_area_struct都记录了一个指针，指向所属的内存描述符。因此只要通过物理页找到引用他们的vm_area_struct,就能找到内存描述符，从而找到页表，找到对应的页表项。

匿名页的反向映射：

对于匿名页来说，每个页面的mapping字段指向一个anon_vma描述符，anon_vma描述符中存在一个链表头，所有引用该页面的vm_area_struct都存放在里面。page,anon_vma,vm_area_struct这些数据结构的关系如下图所示：

对于匿名页来说，其被别的地址空间引用，基本上都是因为fork（）进程时，子进程复制父进程的地址空间，从而被引用的。各个vm_area_struct加入anon_vma的链表的过程如下：

假设当前一个进程p，后来fork出一个子进程c。

1、当进程P为某个vm_area_struct加入第一个物理页时，比如说发生了缺页异常，动态分配一个anon_vma的数据结构，将vm_area_struct加入该anon_vma所管理的链表，vm_area_struct结构中的anon_vma字段指向该anon_vma,同时把该页面中的mapping字段赋值为该anon_vma.对于后续为该vm_area_struct申请的物理页面，其mapping字段都赋值为该anon_vma。

2、当该进程p执行fork()时，在fork的处理过程中，会调用dup_mmap()来复制进程p的线性地址空间，在dup_mmap()会复制进程p的每一个vm_area_struct，加入到自己的地址空间中，并将vm_area_struct加入到anon_vma所管理的链表中，参看anon_vma_link()。此时为进程p申请的页面被进程c共享，通过页面的mapping字段可以找到anon_vma，从anon_vma可以遍历进程p,c。

3、考虑一个问题，在进程c中才触发缺页异常被申请的内存页，其mmapping被赋值为所属vm_area_struct的vma_anon，但进程p并没有使用到该页，所以一个物理页mapping字段指向的vma_anon所下挂的vm_area_struct可能并不包含该物理页。

文件映射页的反向映射：

对于每个文件映射页，其page mapping字段指向的是对应文件的address_space数据结构，address_space中有个 struct prio_tree_root i_mmap 字段，指向一个优先树，优先树里面会把所有映射该文件内容的vm_area_struct 给组织起来。在该树中，其树的节点基地址和堆地址分别是映射的文件内容的起始地址和结束地址，要是多个进程同时映射该地址段，会用链表在该节点上将vm_area_struct串起来。

1.3.3 内存回收流程介绍

睡眠回收我们不关注，主要介绍内存紧缺回收及周期回收：

1、内存紧缺回收主要函数是try_to_free_pages()，该函数会执行一个循环，按照优先级从12到0，依次调用shrink_caches()，shrink_slab()来回收页面，直到回收至少32个内存页面。

依次调用以下辅助函数：

shrink_caches()：调用shrink_zone()对传入的zone链表中的每个zone，进行lru上面的页面回收。

shrink_slab()：对磁盘索引节点cache和目录项索引节点等磁盘高速缓存进行回收，由于磁盘索引节点和目录项索引节点都是从slab高速缓存中分配的，这样就会导致空闲slab的产生，空闲slab后续会在周期性回收的cache_reap工作队列中被回收。估计也就是因为最终会清零空闲slab，才会起这么一个函数名。^_^

shrink_zone()：对内存管理区上的lru链表中的非活跃页面进行回收，在非活跃页面不足的时候，调用refill_inactive_zone()对lru上的inactive链表补充非活跃页面,同时shrink_zone()调用shrink_cache()来进行页面的回收，该函数的具体解析可以参照下面的源码浅析。

shrink_list()：该辅助函数在shrink_cache()中被调用，该函数对在shrink_cache（）中传入的非活跃page列表进行遍历，对每个页面进行回收工作，该函数的具体解析可以参考下面的源码解析。

refill_inactie_zone()：该辅助函数根据一定的规则将处于lru active链表上的活跃页面移动到inactive链表上，以补充可以回收的页面，在lru链表里有两类页，一类是属于用户态空间的页，比如用户态进程的代码段，数据段，一类是在页高速缓存中的页，系统为了降低对应用程序的影响，将要优先将页高速缓存页进行回收，同时为了系统整体性能也会适当回收用户态进程页。按照如下经验公式进行选择：

交换倾向值=映射比率/2+负荷值+交换值

2、kswapd进程一般会在系统中睡眠，但当__alloc_page()发现各个管理区的剩余页面都低于警告值(由内存管理描述符的pages_low字段和protection字段推算出来)时，会激活kswapd进程进行页面回收，直到回收的页面使得管理区的剩余页面高于zone->pages_high时才停止回收，本质上也是调用了shrink_zone（）和shrink_slab()。

3、cache_reap工作队列定期运行来回收slab高速缓存中空闲的slab占用的页。

1.4 相关源代码的浅析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

static void 
shrink_zone(struct zone *zone, struct scan_control *sc) 
{ 
	unsigned long nr_active; 
	unsigned long nr_inactive; 

	//根据优先级，得到可以扫描的页面数，优先级越高， 
	//代表越不急迫，可以扫描的页面数也最少 
	zone->nr_scan_active += (zone->nr_active >> sc->priority) + 1; 
	nr_active = zone->nr_scan_active; 
	if (nr_active >= SWAP_CLUSTER_MAX) 
		zone->nr_scan_active = 0; 
	else 
		nr_active = 0; 

	zone->nr_scan_inactive += (zone->nr_inactive >> sc->priority) + 1; 
	nr_inactive = zone->nr_scan_inactive; 
	//非活动页比较少的话，可以先忽略过去，将跳过的页面记录到nr_scan_inactive中 
	//留待下一次再处理 
	if (nr_inactive >= SWAP_CLUSTER_MAX) 
		zone->nr_scan_inactive = 0; 
	else 
		nr_inactive = 0; 

	//设置需要回收的页面数为32个 
	sc->nr_to_reclaim = SWAP_CLUSTER_MAX; 

	//开始回收页面，每次扫描32个页面，多了不干噢!!! 
	while (nr_active || nr_inactive) { 
		if (nr_active) { 
			//设置每次要扫描的非活动页面数，需要将其放 
			//入到inactive list里面 
			sc->nr_to_scan = min(nr_active, 
			(unsigned long)SWAP_CLUSTER_MAX); 
			nr_active -= sc->nr_to_scan; 
			//补充inactive list中的页面 
			refill_inactive_zone(zone, sc); 
		} 

		if (nr_inactive) { 
			//设置每次将要扫描的页面，最多也就32个页面 
			sc->nr_to_scan = min(nr_inactive, 
			(unsigned long)SWAP_CLUSTER_MAX); 

			nr_inactive -= sc->nr_to_scan; 
			//开始正式回收inactive list中的页面 
			shrink_cache(zone, sc); 
			//32个页面被回收完毕，大功告成了!!! 
			if (sc->nr_to_reclaim <= 0) 
				break; 
		}
	} 
} 

static int shrink_list(struct list_head *page_list, struct scan_control *sc) 
{ 
	LIST_HEAD(ret_pages);
	struct pagevec freed_pvec;
	int pgactivate = 0;
	int reclaimed = 0;
	//有进程需要调度，先进行调度 
	cond_resched();

	pagevec_init(&freed_pvec, 1); 
	//对于page_list 链表上的每一个页面试图进行回收 
	while (!list_empty(page_list)) { 
		struct address_space *mapping; 
		struct page *page; 
		int may_enter_fs; 
		int referenced; 

		//获取一个页面 
		page = lru_to_page(page_list); 
		//从lru上摘除 
		list_del(&page->lru); 
		//page被锁定，不能回收 
		if (TestSetPageLocked(page))//page is locked? 
			goto keep; 

		BUG_ON(PageActive(page)); 
		//page正在被writeback，不能回收 
		if (PageWriteback(page))//page is writeback? 
			goto keep_locked; 

		sc->nr_scanned++; 
		/* Double the slab pressure for mapped and swapcache pages */ 

		if (page_mapped(page) || PageSwapCache(page)) 
			sc->nr_scanned++; 
		//查看最近该页面有无被访问过 
		referenced = page_referenced(page, 1, sc->priority <= 0); 
		/* In active use or really unfreeable?  Activate it. */ 
		//1页面被访问过，2页面在用户态空间，页面是文件映射页面， 
		//页面在交换高速缓存中，同时满足这两个条件的话，页面不被回收 
		if (referenced && page_mapping_inuse(page)) 
			goto activate_locked; 

		#ifdef CONFIG_SWAP
		//page is anon and page has not been add to swapcache 
		//该页面是匿名映射的页面，且该页面不在swapcache中 
		if (PageAnon(page) && !PageSwapCache(page)) { 
			//将页面加入到swap cache中 
			if (!add_to_swap(page)) 
				goto activate_locked; 
		}
		#endif /* CONFIG_SWAP */ 
		//得到对应的address_space，有可能是对应文件的address_space,或者是 
		//swap cache的address_space 
		mapping = page_mapping(page); 
		may_enter_fs = (sc->gfp_mask & __GFP_FS) || 
				(PageSwapCache(page) && (sc->gfp_mask & __GFP_IO)); 

		//该页面被映射到某个用户页表中 
		if (page_mapped(page) && mapping) { 
			//将该页面在用户页表中的页表项通通清除 
			switch (try_to_unmap(page)) { 
				case SWAP_FAIL: 
				goto activate_locked; 
				case SWAP_AGAIN: 
				goto keep_locked; 
				case SWAP_SUCCESS: 
				; /* try to free the page below */ 
			} 
		} 
		//页面是脏的，哈哈，准备往文件或swapcache里面写硬盘吧 
		if (PageDirty(page)) { 
			if (referenced) 
				goto keep_locked; 
			if (!may_enter_fs) 
				goto keep_locked; 
			if (laptop_mode && !sc->may_writepage) 
				goto keep_locked; 

			/* Page is dirty, try to write it out here */ 
			//往磁盘上写页面 
			switch(pageout(page, mapping)) { 
				case PAGE_KEEP: 
					goto keep_locked; 
				case PAGE_ACTIVATE: 
					goto activate_locked; 
				case PAGE_SUCCESS: 
					if (PageWriteback(page) || PageDirty(page)) 
						goto keep; 

					if (TestSetPageLocked(page)) 
						goto keep; 
					if (PageDirty(page) || PageWriteback(page)) 
						goto keep_locked; 
					mapping = page_mapping(page); 
				case PAGE_CLEAN: 
					; /* try to free the page below */ 
			} 
		}

		//若页面是缓冲区页面，将对应的buffer_head给释放掉 
		if (PagePrivate(page)) { 
			if (!try_to_release_page(page, sc->gfp_mask)) 
				goto activate_locked; 
			if (!mapping && page_count(page) == 1) 
				goto free_it; 
		} 

		if (!mapping) 
			goto keep_locked; 
		/* truncate got there first */ 

		spin_lock_irq(&mapping->tree_lock); 

		//页面为脏页面或者page的引用计数为2，都是不可以回收的  
		if (page_count(page) != 2 || PageDirty(page)) { 
			spin_unlock_irq(&mapping->tree_lock); 
			goto keep_locked; 
		}

		#ifdef CONFIG_SWAP 
			//到达这里，说明该page只被swap cache或者页高速缓存及 
			//fpra所共有，需要将其从swap cache上或者页高速缓存上删除。 
		if (PageSwapCache(page)) { 
			swp_entry_t swap = { .val = page->private }; 
			//从swap cache上进行删除 
			__delete_from_swap_cache(page); 
			spin_unlock_irq(&mapping->tree_lock); 
			swap_free(swap); 
			__put_page(page); 
			/* The pagecache ref */ 
			goto free_it; 
		} 
		#endif /* CONFIG_SWAP */ 

		//从页面高速缓存中将该页面删除 
		__remove_from_page_cache(page); 
		spin_unlock_irq(&mapping->tree_lock); 
		__put_page(page); 

		free_it: 
			unlock_page(page); 
			reclaimed++; 
			if (!pagevec_add(&freed_pvec, page)) 
				__pagevec_release_nonlru(&freed_pvec); 
			continue; 

		activate_locked: 
			//将页面设为active页面，等回去将其放入lru的active链表 
			SetPageActive(page); 
			pgactivate++; 
		keep_locked: 
			//保持页面的状态不变，放入对应的lru active或inactive链表中 
			unlock_page(page); 
		keep: 
			//将该无法回收的页面，放入到ret_pages链表中 
			list_add(&page->lru, &ret_pages); 
			BUG_ON(PageLRU(page)); 
	} 
	//此处将无法回收的页面放入page_list中，在函数返回后，去其进行处理 
	list_splice(&ret_pages, page_list); 
	//此处将可以释放的页面通通给释放掉，回收了^_^ 

	if (pagevec_count(&freed_pvec)) 
		__pagevec_release_nonlru(&freed_pvec); 
	mod_page_state(pgactivate, pgactivate); 
	sc->nr_reclaimed += reclaimed; 
	return reclaimed; 
}

Linux_Physical_Memory_Page_Allocation.pdf

转自 http://www.jtben.com/document/1266382