Linux桌面环境下内存去重技术的研究与实现
第二章 相关理论与技术
2.1 内存管理
内存管理是操作系统内核中极为重要的部分，它涉及物理地址、虚拟地址、分段、分页等诸多概念。
2.1.1 内存地址
程序使用地址来访问内存单元。对于x86架构的中央处理器，使用逻辑地址，虚拟地址，物理地址三种不同的地址[15]。
逻辑地址包括段和偏移地址两部分，它们共同用来指定机器指令或者操作数在内存中的位置。逻辑地址对应下文提到的分段式内存管理。
虚拟地址也被称作线性地址，它表示一个寻址空间。在Linux操作系统中，使用一个无符号长整型存储虚拟地址。如果是针对32位x86处理器的内核，这是一个32位的无符号长整型，可以寻址至多232，即4GB空间。而Linux在x86_64处理器上，一个无符号长整型有64位，但实际上只使用了48位，即可寻址到248 ，即256TB的内存空间。引入虚拟地址使得用户空间的进程都独自拥有一个地址空间，方便操作系统在硬件的协助下隔离进程访问内存的操作，从而实现更高的安全性和便捷性。在32位处理器架构下，4G虚拟地址空间划分成两部分，高端的1G空间被称之为内核空间，低端的3G空间称之为用户空间。内核的代码和数据存在内核空间，用户空间的进程通过系统调用陷入内核空间执行内核空间的代码。对于64位处理器，虚拟地址同样分为内核空间和用户空间，只是针对64位处理器的内核拥有大得多的寻址范围，对内核空间和用户空间的地址划分有多种实现。
物理地址被中央处理器用来寻址内存芯片上的实际的物理单元。它对应了送往处理器的针脚上的高低电平信号。
Linux中的内存管理单元 (Memory Management Unit, MMU)在硬件电路的帮助下把逻辑地址译成线性地址；而另一个硬件电路则帮助把线性地址翻译成物理地址。
2.1.2 段页式内存管理
内存分段是由80×86处理器引入的概念，它鼓励程序员在设计程序时把程序使用的内存按照逻辑上的意义相关性分成若干个部分，比如有些段存放全局数据，有些段存放程序代码[16]。
内存管理单元的分页单元协助把虚拟地址译为物理地址，为了提高翻译的效率，虚拟地址被按照固定长度切分成一个个小单元，它们则被称之为页面。页面可以看成是MMU管理内存的最小单位。
分段和分页都用来划分内存，在某种程度上，它们的功能有一定重合。实际上，Linux内核的内存管理机制倾向于使用分页技术。Linux进程运行在用户空间时使用的标志代码段的代码段选择子(segmentation selector)和数据段选择子是相等的；进程运行在内核空间时使用的代码段选择子和数据段选择子也是相等的。而且这四个段选择子的段基址都设置为0。这意味着在Linux操作系统中，无论寻址数据和还是寻址指令，无论在用户空间还是内核空间，逻辑地址的段基址部分为0，偏移地址部分刚好等于虚拟地址。
在Linux所支持的大多数硬件平台上，默认的页面大小是4K。但Linux同时也支持大于4K的页面的内存管理。运行在用户空间的代码可以使用glibc库中的getpagesize()函数得到当前使用的页面大小。本论文只针对在x86_64架构上页面大小是4K的Linux内核。实际上从内核2.6.38开始，内核中开始支持透明巨页(Transparent Huge Page)[17]，内核中有些页面的大小实际上是2M，但这不影响按照4K的页面大小展开讨论。
Linux使用分级页表的方式把虚拟地址映射到页面。在32位处理器上使用二级页表，在x86_64架构的处理器上则使用四级页表。
图2-1 四级页表
如图2-1所示，以针对x86_64架构处理器的Linux内核为例，64位虚拟地址的高16位不被使用，低48位被平均分为5段，offset段占12位，其它四个段各占9位。这个划分在源代码文件arch/x86/include/asm/pgtable_64_types.h中定义。cr3寄存器存储了页全局目录的物理地址。在把虚拟地址翻译到物理地址的过程中，MMU先从cr3寄存器中取出全局目录的物理地址，再加上GLOBALDIR段算出的偏移量，从而在页全局目录中得到页上级目录的物理地址。与此类似，从页上级目录中得到页中间目录的地址，然后得到页表的地址，再得到页面的地址，最后的OFFSET字段则定位到页面中的一个字节。至此，虚拟地址被翻译到了物理地址。
页全局目录，页上级目录，页中间目录，以及页表中的每一项都由相同的数据结构表示。它记载了一些重要的信息，与本论文相关的信息有：该项指向的下一级表或者页面是否存在的标志，如果访问时不存在则产生缺页中断，由do_page_fault函数负责把页面调入内存[18]；下一级表或页面的物理地址；下一级表或页面是否可读可写的标志，利用该标志位可以写保护一个页面。
Linux内核用一个struct page结构体描述一个页面的信息。这个结构体定义在include/linux/mm_types.h文件中[19]。图2-2列出这个结构体中与本论文直接相关的字段。
图2-2 struct page的部分字段
其中的flags字段存储了页面的状态信息，例如：表示页面刚被写了数据的脏位；该页面是否被锁定在内存中不充许置换到交换分区的标志。_count字段和_mapcount字段都是引用计数，它们用来共同维护page页面的生命期。_mapcount表示一个页面拥有多少页表项指向它，_count被称为page的使用计数，所有的_mapcount计数只相当于_count计数中的一次计数。如果内核代码中某执行序列在访问某个页面时需要确保该页面存在，则在访问前给_count计数加一，访问结束后_count计数减一。当_count计数减到负数时表示没有任何内核需要使用该页面，则表示该页面没被使用。内核代码不应该直接访问_count计数，而应该使用page_count函数。该函数用一个struct page的指针做为参数，当该页空闲时函数返回0，否则返回一个正数表示参数指向的页面正被使用。当页面被页高速缓冲使用时，mapping域指向一个address_space对象，该对象与Linux文件系统中的文件是一对一映射的关系，描述了一个文件分配到的物理页面及相关数据结构。如果页面并不被页高速缓冲使用时，mapping则有其它的意义，比如mapping字段的最低位记载这是否是一个匿名页面。virtual字段是映射到该页面的内核空间的虚拟地址，如果该页面是属于高端内存区域则virtual字段为NULL。对于x86_64架构上的Linux内核，已经没有高端内存，因此该字段不会为NULL。
2.1.3 内核中的巨页
现代处理器的内存管理单元几乎都能处理除4KB大小外的多种页面尺寸。然而，Linux内核在几乎所以平台上的实现都选用最小的页面大小，即4KB，比4KB更大的页面，都被称之为巨页(huge page)。在某些工作环境下，巨页可以给操作系统带来性能上的提高。巨页能提高操作系统的性能主要是因为两点。第一，使用巨页可以减少发生页面出错处理的频率，因为在每次页面出错处理时内核调入比使用小页面更多的内存。第二，使用巨页减少翻译虚拟地址的时间。在x86_64加构的处理器上，从虚拟地址翻译到物理地理需要依次访问四级页表，非常耗时。而使用巨页可以减少页表的级数。实际上更大的性能提高源自使用巨页后提高了旁路转换缓冲区(Translation Lookaside Buffer，TLB)的命中效率[20]。
在内核2.6.38版本之前，唯一使用巨页的方式是通过非常复杂的hugetlbfs文件系统。应用程序开发者和系统管理员都需要注意一些特别事项才能够开启巨页功能。因此只有极少数真正需要巨页带来性能提高的用户，如专用数据库系统，才使用巨页。
情况从内核版本2.6.38以后发生了变化，一个被称之为透明巨页的功能被合并进了内核主干代码。之前内核在VMA（Virtual Memory Area，虚拟内存区域）中的所有页面大小都是一样大的，而加入透明巨页后，VMA中的页面的大小可能不只一种。透明巨页的实现代码改写了页面出错处理函数，当一个出错发生时，内核尽力分配一个巨页，如果成功的话，其它相应的在巨页地址范围内的小页面就会被释放，巨页被插入到VMA中。如果不能分配到一个巨页，则仍然按照以前的方式分配一个小页面。当巨页需要被置换到交换分区时，透明巨页机制简单地把巨页切割成小页面，其它逻辑和处理小页面时一样。实际上不仅在置换到交换分区时需要切割巨页，很多其它的操作，如mprotect()和mlock()页面时也需要。本论文将详述的KSM在合并页面时同样需要把巨页切割成小页面。
透明巨页这种轻便地利用巨页的方式使得很多内核代码并没有感知到巨页的存在，对于应用程序则更没有感知到巨页，因此被称之为透明巨页。
2.1.4 内存描述符
Linux内核使用一个叫内存描述符(Memory Descriptor)的结构体描述每一个进程的地址空间[21]。这个结构体包括了所有和进程地址空间相关的信息。内存描述符和struct page一样在文件include/linux/mm_types.h中定义。图2-3列出这个结构体中与本论文直接相关的字段。
图2-3 struct mm_struct的部分字段
其中，mmap字段是用来实现一个链表。这个链表链接了属于这个内存描述符的所有vm_area_struct结构体。vm_area_struct结构体描述了一个内存区域。由于属于一个内存描述符的内存区域可能非常多，为了加快内存区域的查找以及添加删除等操作的速度，内核用mm_rb表示一棵链接了所有内存区域的红黑树。红黑树是一种二叉树，它被广泛地应用在Linux内核代码中。mmap和mm_rb是用两种不同的数据结构表示同一批数据。mm_users和mm_count是内存描述符的引用计数，它的实现原理和struct page的引用计数的原理一样。每一个进程如果拥有一个内存描述符，则会增加mm_users的计数，所有mm_users的计数只相当于mm_count的一个计数。比如n个Linux线程共享同一个内存描述符，那么对应的内存描述符的mm_users计数则为n，而mm_count则可能只是1。如果有内核执行序列想要访问一个内存描述符，则该执行序列先增加mm_count的计数，使用结束后减少mm_count的计数。一但mm_count减为0，表示该内存描述符没有任何引用，则它会被内核销毁。mmap_sem是一个读写锁，凡是需要操作内存描述符中的内存区域时，则需要先得到相应的读锁或者写锁，使用结束后释放该锁。mm_list字段是一个循环双链表。它链接了系统中所有的内存描述符。flags字段定义了内存描述符的标志，这些标志标记了内存描述符的一些状态和属性，内核代码需要使用原子操作访问该字段。
2.1.5 虚拟内存区域
同样被定义在inlude/linux/mm_types.h中的结构体vm_area_struct用来描述一个内存区域。在Linux内核中，内存区域经常被称之为虚拟内存区域(Virtual Memory Areas,VMA)。VMA描述的内存区域是一个地址空间中的地址连续的部分。而且该部分拥有一些特定的属性，比如访问权限和相关联的操作等。不同的VMA可以用来描述不同的内存区域。比如，映射到内存的文件，用户空间的栈，特别是本论文重点关注的匿名内存区域(Anonymous VMA)。下面讨论本论文关心的vm_area_struct的一些重要字段，这些字段如图2-4所示。
图2-4 struct vm_area_struct的部分字段
vm_mm字段指向该VMA属于的内存描述符。vm_start和vm_end字段表示该VMA描述的内存区域的起始和终点虚拟地址，但不包括vm_end指向的地址，即vm_end是虚拟内存区域的最后一个有效字节的后一个字节。vm_next和vm_rb分别把内存描述符拥有的内存区域用链表，和红黑树链接起来。vm_flags表示内存区域的属性。anon_vma与内核的页面回收机制回收匿名页时用到的页面反射表有关。vm_file是该内存区域对应的文件，如果内存区域是匿名的，则该字段被置为NULL。
2.1.6 Slab层
频繁地申请和回收同一类型的数据结构是内核中极为常见的操作。为了提高申请和回收某种特定数据结构的效率。Linux内核中引入了slab层的概念，通过slab层来管理某种数据结构的频繁申请和回收[22]。
Slab层把不同的数据结构划分到不同的高速缓存(cache)中，每个缓存都用来维护某种数据结构的申请的回收。比如，从维护进程描述符的缓存中申请进程描述符时，缓存把一个标记为可用的进程描述符返回给调用者，同时把该描述符标记为已用；释放进程描述符则使得这个进程描述符在存放它的缓存中又被标记为可用。
每个缓存被划分为好几个slab，这就是这个子系统被称之为slab层的原因。每个slab是一页或几页连续的内存。缓存维护的某种数据结构，称之为对象，就全部放在slab中。每个slab处于满，部分满或空三种状态。当slab 处于满状态时，表示该slab中维护的对象已经全部被分配。当slab处于空状态时，和半满状态时，slab可以有空闲的对象可供分配。当内核需要申请一个新对象时，就向对应的缓存申请。缓存找到自己维护的slab，从slab中拿出预先分配好的空闲对象返回给申请者。当内核使用完了该对象，这个对象就被缓存回收，一般情况下并不真正释放，而是在对应的slab上做空闲标记。缓存通过灵活的策略维护slab的大小和数量。使用slab，能够加速常用数据结构的分配和释放，并减少分配内存产生的碎片。
2.2 内核开发
操作系统内核的开发和普通用户空间的程序开发有非常大的差异。本节将介绍理解KSM和在内核空间进行开发所需熟知的一些内容。
2.2.1 Linux内核简介
Linux由1991诞生开始就受到开源社区的热烈欢迎，并且一直处于极为活跃的持续开发状态。Linux的代码以GNU计划倡导的GPL协议自由分发，全世界的操作系统爱好者，硬件驱动编写者都非常活跃地为Linux贡献代码。Linux的开发如此成功，以至GNU计划中自己的操作系统内核GNU Hurd都未得到足够多的关注，Linux成为事实上GNU计划的操作系统内核。
Linux内核沿用Unix的单内核设计。单内核设计把整个内核设计成运行在同一个地址空间的一个“大”进程。所有的内核执行序列存在于同一个地址空间中，并在同一个地址空间内运行。因此，内核的不同执行序列之间的通信是极为快速的，基本不需要额外的开销，但由此也带来内核代码的复杂度过高的问题。较之单内核，另一个设计操作系统的思路是微内核，它的很多设计理念和单内核的设计相反，如windows XP, Vista 还有 windows 7等等。Linux内核在发展过程中引入了内核模块的概念，这使得Linux内核既保持了单内核设计性能快速的特点，又使得内核代码相对纯粹的单内核简洁和易于维护。
本论文选定的内核版本是2013年2月发布的3.0.66稳定版，在它的基础上研究开发。
2.2.2 内核线程
Linux的内核线程实际上是只存在于内核空间的一个进程。内核通常创建内核线程让它在后台周期性的处理一些事务。内核线程和普通进程一样可调度，可被抢先。他们的最显著的区别是内核线程的进程描述结构体task_struct的mm字段为NULL。而一般进程的进程描述结构体的mm字段指向该进程的地址空间。因为内核线程永远只运行在内核态，永远不必切换至用户空间，并且所有用户态进程的地址空间的内核虚拟地址部分都是一样的，所以当处理器调度到内核进程时，内核进程可以随便使用某个用户态进程的地址空间的内核虚拟地址部分。Linux内核线程的作法是借用上一个普通用户态进程的用户空间[23]。
内核线程由内核API函数kthread_create()创建，也可由kthread_run()创建。他们的区别是前者创建的是一个处于非运行状态的内核线程，需要使用wake_up_process()把它转换为可运行状态；而kthread_run()创建的内核线程立即处于可运行状态，随时可能被调度而获得运行的机会。内核线程开始后会一直运行，直到它显式地调用do_exit()或者其它内核代码调用kthread_stop()。kthread_stop()函数需要传入先前创建内核线程函数返回的task_struct作为参数。该函数在调用后会一直阻塞，直到等待的内核线程完全退出了才返回。
2.2.3 内核的同步机制
竞争条件指的是程序设计中的一种缺陷，这种缺陷使得程序的输出会因为不受控制的事件出现的顺序或发生时间而发生改变。Linux内核提供了一套同步方法，正确地使用同步方法可以消除竞争条件[24]。
atomic_t是内核中的特殊整型数，应用在该整型数上的方法使得对该整数的操作是原子操作，从而对该整数的操作不会被其它执行序列中断。如atomic_inc()和atomic_dec()分别是原子地给一个整型数加一或减一。
Linux内核中最常用的锁是自旋锁。对于一个自旋锁，内核在任何时候只能有一个执行序列持有该锁。如果在该自旋锁被其它执行序列持有时，当前执行序列也申请持有该锁，则这个执行序列就会使得处理器一直忙等该锁被持有者释放。为遵循迅速占有，迅速释放的原则，一个内核执行序列一但持有某自旋锁，则内核在该内核序列运行的当前处理器上被禁止抢先。另外，持有自旋锁的内核执行序列应该运行完简短的代码后迅速释放该自旋锁，而不应该在释放持有的自旋锁前执行可能造成睡眠的代码，也不能显式地调用放弃处理器而申请调度其它进程的代码，因为这样会使得其它申请该自旋锁的执行序列等待非常长的时间而大大损害了整个系统的性能。自旋锁的基本有法是：用DEFINE_SPINLOCK在编译期定义一个未被占用的自旋锁变量，用函数spin_lock()得到自旋锁，用spin_unlock()函数释放自旋锁。与普通自旋锁类似的还有读写自旋锁。当对自旋锁保护的资源的访问多数是读访问，少部分是写访问时，使用读写自旋锁比使用普通自旋锁的效率更高。
Linux内核中另一种常见的锁是信号量。信号量只能在进程上下文中才能使用，当一个进程或内核线程尝试获取一个不可用的信号量时，该进程或者该内核线程会被置于一个等待队列中，然后进入睡眠状态，处理器转而执行其它的代码。当该信号量被某持有者释放，信号量变为可用时，等待队队中的一个进程或内核线程会被唤醒而获得该信号量。因为未能立即获得锁时会使得执行序列进入睡眠，所以在不能被调度的中断上下文中不能使用信号量。同样因为未能立即获得信号量则被置于睡眠状态的原因，信号量非常适合需要长时间持有锁的情况。信号量的另一个显著的特点是它充许同时有若干个持有者，这个数量在声明信号量时指点。但大多数情况下信号量被设置为只能有一个持有者，这种情况下，信号量被称为二值信号量或者互斥锁。互斥锁常见的使用方法是：用DECLARE_MUTEX宏在编译期定义一个未被占用的互斥锁变量，或者用init_MUTEX在运行时初始化互斥锁，用down()函数获得信号量，用up()函数释放信号量。与读写自旋锁类似，Linux内核也有针对读多写少的情况做优化的读写信号量，它的特征和普通信号量基本相同。
2.2.4 内核的调试技术
调试内核代码是内核开发技术中非常困难的一部分，这是因为内核代码运行在软件栈的最底层，不像用户空间的进程可以轻易地被调试器跟踪。另外，因为很多情况下的内核错误会让整个操作系统崩溃或者运行在不可预测的不稳定状态，让开发者几乎没有机会收集到足够多的错误是如何出现的线索，所以内核错误在很多情况下也不能轻易地被重现。
用printk()函数打印出程序的相关信息到日志文件或控制台是最古老也最常用且有效的调试方法[25]。printk()函数与用户空间的printf()库函数相似，其中的差别之一是printk()函数可以让用户指定打印信息的级别。目前printk()函数有八个信息级别，它们被定义在linux/kernel.h头文件中。级别的数字越小则表示级别越高。基于信息级别，内核可能把信息打印到当前的控制台。它可能是一个字符终端，可能是一个串口连接的设备，也可能是一个并口打印机。内核中的整型变量console_loglevel表示能被发往控制台的信息的最小级别。可以用sys_syslog系统调用改变它的值，用可以通过写文件/proc/sys/kernel/printk改变它。所有信息，包括信息级别的值大于console_loglevel而没能被发往控制台的信息都被添加到文件/var/log/messages的末尾。
除了最为常用的打印函数printk()是调试内核必备之外。内核开发者使用的内核在编译前通常都会打开一些方便调试的内核选项[26]。比如CONFIG_KALLSYMS选项使得内核代码的符号信息被编译进内核，这样当内核崩溃时，系统会用符号打印出出错时栈回溯信息，否则只有二进制的地址信息。还有一些特定的编译选项帮助开发者排查特定的错误，比如CONFIG_DEBUG_SLAB可以帮助排查忘记初始化内存和内存越界访问的错误；而CONFIG_DEBUG_SPINLOCK 可以排查非法使用自旋锁的错误。
KGDB是常用的调试Linux内核的调试器。最开始，它只是作为一个内核补丁发布，从内核2.6.26开始，它被合并到了内核的主干代码。用KGDB调试时，需要两台用串口连接的Linux机器，被调试的机器运行KGDB，另一台(调试机)则运行普通的GDB。GDB远程协议被用于它们之间的通讯[27]。配置KGDB比较麻烦，但目前桌面虚拟化技术非常成熟，开发者可以用两台Linux虚拟机使用KGDB，用虚拟的串口硬件连接两台机器。仅管如此，使用内核调试器还是相当之麻烦。被调试的内核在编译后输出的vmlinux文件是未压缩的linux内核，需要被拷贝到调试机；对应的源代码需要被拷贝到调试机调试时的当前目录；另外，调试时并不能在所有代码语句设置断点，因为内核代码的编译依赖于GCC的编译优化选项，开启相应的优化选项内核代码才能通过编译，而很多语句的变量经过GCC优化后会被去掉，调试者从源代码上看到的执行路径经常并非内核实际的执行路径。
2.3 本章小结
本章首先介绍了Linux内核的内存管理的一些理论和技术，然后介绍了进行内核开发所必须掌握的基础知识。本章的内容是理解以后章节的基础。