Posts

几天前和同事吃饭，谈论到一个问题：linux从什么时候开始支持线程。他说linux中的线程出现的很晚，直到2.2.x才有。 我觉得不对啊，怎么会那么晚。然后它用手机搜索了一下，linux对POSIX线程库的支持确实很晚，直到2.6.x才有。 但我觉得POSIX线程库只不过是用户空间用来创建线程的接口，并不能证明那么晚linux才支持线程。 后来用PC的时候搜索了一下，在The Linux Document Project的官方网站找到了答案： http://www.tldp.org/FAQ/Threads-FAQ/Support.html Does Linux support threads? Yes. As of 1.3.56, Linux has supported kernel-space multithreading. There also have been user-space thread libraries around as early as 1.0.9. There is on-going effort to refine and make the kernel more reentrant. With the introduction of 2.1.x, the memory space is being revised so that the kernel can access the user memory more quickly. ...

测试结果介绍：   tcpcopy在编译期配置成使用NFQueue模式，用Raw Socket抓包。线上机的流量被成功复制并导向测试机。经改动的tcpd初期工作正常。 改动版的tcpd(实际上是一个echo服务器)。测试机上的tcpd把收到的报文被打印到日志文件。但日志文件到6M+大小的时候，就停止打印。目前还没有查到原因，可能是改动后的tcpd的Bug。此时，tcpdump仍然抓到大量从线上机复制来的真实流量到达测试机。tcpcopy应该是工作正常的。   tcpcopy被编译成使用libpcap抓包时不能在线上机上正常工作。tcpdump没有抓到预期从线上机复制到测试机的报文。原因是：线上机10.130.68.100上的真实流量从网络接口tunl0:0进入，从网络接口eth1发出。分析tcpd的日志发现，tcpd使用libpcap只拿到tunl0的IP，没有发现tunl0:0的IP。需要了解IP隧道，和libpcap库的相关知识，有可能解决这个问题。   编译成使用Raw Socket抓包，和Advanced模式时，tcpcopy启动失败，错误日志显示Advanced模式只能使用libpcap库抓包。因此，只有在解决libpcap正确识别tunl0:0网络接口后，才能在线上机上运行tcpcopy。   预备知识： Tcpcopy可以编译成用libpcap抓包或者使用Raw Socket抓包。Libpcap库是tcpdump使用的抓包库，Raw Socket是操作系统内建的功能。 官方文档建议用libpcap抓包，以获得更高性能和较低丢包率。   Tcpcopy在编译期指定工作模式。tcpcopy目前有两种工作模式，一种使用IPQueue技术或者NFQueue技术。NFQueue技术是用来替代IPQueue技术的。我们目前使用的tlinux，内建了NFQueue内核模块，没有开启IPQueue模块。因为NFQueue是内建的即CONF_XXXXXX = y，而不是编译成模块，即CONF_XXXXX = m, 所以我们在环境中不需要使用modprobe 加载IPQueue或者NFQueue模块。忽略官方文档中提到的modprobe ip_queue。   测试步骤：   使用NFQueue模式： 线上机：10.130.68.100 编译tcpcopy时指定使用NFQueue。不要指定 –enable-pcap，则默认使用raw socket抓包。用pcap抓包时识别不到网络接口tunl0:0，而tunl0:0是真实流量的入口。 # ./configure –enable-nfqueue #./make 生成的tcpcopy在 src/tcpcopy 目录下。 运行tcpcopy命令，把流量复制到测试机： # ./tcpcopy -x 80-10.213.243.156 测试机：10.213.243.156 编译tcpcopy时同样指定–enable-nfqueue，不要指定–enable-pcap。然后运行intercept # ./intercept   使用Advanced模式： 因为暂时未能解决用libpcap识别到网络设备tunel0:0的问题，实际上Advanced模式暂时不能工作。根据以前的使用经验，用Advanced模式时需要注意两点： 1. 在./configure时指定 –enable-advaned 和 –enable-pcap。 2. Advanced模式需要两台测试机，需要设成一条路由把复制后的真实流量导向测试机。需要更改默认路由：删掉当前的默认路由，新的默认路由从正确的网卡指向测试机2的IP。 # route del default # route add default gw 10.213.243.156 dev eth1 copyright ykyi.net

Tcpcopy 初体验 Tcpcopy是一个模拟真实流量的测试工具。它的工作基本思想是，从已经上线的服务器复制一份真实流量到测试服务器。Tcpcopy的代码开源，代码仓库放在https://github.com/wangbin579/tcpcopy。 经过初步学习，已成功在公司的测试机器上部署tcpcopy，并用简单的DEMO程序测试达到预期目的。 **1.**安装 因为作者写的安装介绍只提到最基本的信息，而测试环境各不一样，在我用的测试机的实际安装过程中碰到一些问题。这时问题在这里列出，以供后来者参考，以节省时间。测试机：10.12.194.199 ； 10.12.194.212 ； 10.12.194.214 。 1.1 需要额外安装的库： 需要在网站 www.netfilter.org 下载 libmnl， libnfnetlink， libnetfilter_queue 三个工程并安装。 安装顺序为 libmnl， libnfnetlink, libnetfilter_queue，因为第三个依赖第二个，第二个依赖第一个。安装方法是GNU工具的传统三板斧方式： ./configure ; make; make install。这三个工程生成三个.so库放置到/usr/local/lib，而我们用的操作系统环境并没有把该目录列在默认查找库文件的目录列表中，因此要编辑 /etc/ld.so.conf 文件，把目录/usr/local/lib 加入，再运行 ldconfig 更新ld链接程序使用的cache。 1.2 IP_Queue****和NFQueue内核模块： 这两个内核模块给在用户空间编写处理内核空间中传递网络数据包提供接口。它们的区别是IP_Queue是旧的实现，仅支持IPv4，NFQueue是新的实现。Tcpcopy工程依赖这两个模块之一。 Tcpcopy官方文档中多次提到tcpcopy在内核版本小于3.5时默认使用IP_Queue，并在使用例子中有一步操作： # modprobe ip_queue 这个操作是确保加载ip_queue模块到内核。 我们的测试环境的内核版本号是2.6.32，按照官方文档介绍，内核版本小于3.5，于是使用#modprobe ip_queue命令，结果报错显示我们使用的内核没有启用动态模块加载。 于是再用 # zcat /proc/config.gz 检查当前内核的配置，发现CONFIG_IP_NF_QUEUE is not set, 说明IP_Queue模块没有被buit-in，再查找NFQueue的配置项发现 CONFIG_NETFILTER_NETLINK_QUEUE=y。 所以，在我们的环境中，应该忽略官方文档中# modprobe ip_queue，我们的内核已经内建了比IPQueue更新的NFQueue****。 1.3 编译安装tcpcopy**：** 官方文档中把已经正常运行业务的服务器称为在线服务器(online server)，把运行待测试用的服务器称为目标服务器(target server)。 在在线服务器端运行配置命令时务必指定 –enable-nfqueue，这是因为我们用的内核中只有NFQueue，如果不指定这个选项，编译出的tcpcopy不会运行成功，会在日志文件中报错：please make sure ip queue is running. # ./configure –enable-nfqueue –enable-pcap ...

virtualBox开机挂载windows分区，并把光盘镜源设为源。 设置fstab文件。把windows的d,e,f盘分别开机挂载到了/misc/d /misc/e /misc/f 。/misc是自建的目录，是miscellany的缩写。 # cat /etc/fstab # /etc/fstab: static file system information. # Use ‘blkid’ to print the universally unique identifier for a # device; this may be used with UUID= as a more robust way to name devices # that works even if disks are added and removed. See fstab(5). # # / was on /dev/sda1 during installation UUID=590c2b64-87b7-4f92-b32f-7133139be772 / ext4 errors=remount-ro 0 1 # swap was on /dev/sda5 during installation UUID=1e4e1188-d057-4210-99e7-6f2d1529db80 none swap sw 0 0 /dev/sr0 /media/cdrom0 udf,iso9660 user,noauto 0 0 D_DRIVE /misc/d vboxsf rw,auto 0 0 0 E_DRIVE /misc/e vboxsf rw,auto 0 0 0 F_DRIVE /misc/f vboxsf rw,auto 0 0 0 /misc/d/debian_ios/debian-7.1.0-amd64-DVD-1.iso /misc/a_iso udf,iso9660 user,loop,auto 0 0 /misc/d/debian_ios/debian-7.1.0-amd64-DVD-2.iso /misc/b_iso udf,iso9660 user,loop,auto 0 0 /misc/d/debian_ios/debian-7.1.0-amd64-DVD-3.iso /misc/c_iso udf,iso9660 user,loop,auto 0 0 ...

把我的毕业论文放上来，直接从word复制，所以图片会丢失。 在这里可以下载原稿 www.ykyi.net/upload/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf 中山大学硕士学位论文 Linux桌面环境下内存去重技术的. based on KSM 研究与实现 Research and Implementation of Memory Deduplication in The Linux Desktop Environment 学位申请人： <td style="width:160px;"> <p> 周霄 </p> </td> 导师姓名及职称： <td style="width:160px;"> <p> 王常吉副教授 </p> </td>         论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。   学位论文作者签名： 日期： 年  月  日       学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索；可以采用复印、缩印或其他方法保存学位论文；可以为存在馆际合作关系的兄弟高校用户提供文献传递服务和交换服务。 保密论文保密期满后，适用本声明。   学位论文作者签名：                       导师签名： 日期：  年  月  日                       日期：  年  月  日         论文题目： Linux桌面环境下内存去重技术的研究与实现 专业：软件工程  硕士生：周霄 指导教师：王常吉  摘  要 内存管理是操作系统中至关重要的部分。优秀的操作系统高效地管理有限的内存资源。Linux内核的内核同页合并（KSM）模块是在虚拟化兴起后为节省虚拟机使用的内存而发展的一种节约内存的技术。KSM通过合并相同内容页面的方式显著地降低了多个基于内核虚拟机（KVM）技术的虚拟机同时运行时系统使用的内存。实际上，KSM也能合并一般应用程序中的相同内容页面。但一般应用程序为了使用KSM技术合并内存，需要在源代码级别显式地调用相应的系统调用来告知KSM需要扫描的内存区域。对于一般用户来说，需要修改应用程序的源代码显然是一个太高的门槛。 本论文在认真研究了KSM模块的实现的基础上，增强了KSM的功能。新设计实现的KSM+使得用户可以不必修改应用程序的源代码就能利用KSM+合并相同内容的内存页面。另外原来的KSM算法依赖程序指定的内存区域有大量的重复内存页面，而实际上，一般应用程序并没有大量的重复内存。在重复内存非常少的情况下，对这些程序应用KSM技术非但不能降低内存使用，而且因为运行KSM本身所需内存而增加了内存开销。本论文针对这一点在KSM的算法上做了改进，减少了运行KSM+算法本身所消耗的内存。然后论文用Linux桌面下的常用应用程序验证了KSM+的实际效果，并构造了一个实验比较了KSM和KSM+。最后，为了了解应用程序的重复内存页面的特点，还编写了专门统计重复页面的内核模块，发现应用程序的重复页面的一些规律，为持续改进KSM+提供了依据。   关键词：KSM，重复内存合并 ，内存管理   Title: Research and Implementation of Memory Deduplication in The Linux Desktop Environment Major: Software Engineering Name: Zhou Xiao Supervisor: Wang Changji Abstract Memory management is one of the most important parts of the operating system. KSM (Kernel Samepage Merging) in Linux kernel is a kind of memory saving technology developed after the emerging of virtual machine. KSM can dramatically decrease the memory usage of the hypervisor running several virtual machines. Actually, KSM can also be applied to normal applications. But in order to use the KSM, application must explicitly evoke a system call in source code level to tell KSM the memory area where the KSM will scan. To normal users, modifying the source code is impossible at most of the time. Base on the full grasp of the implementation of KSM, a new implementation named KSM+ is created, which allows users to merge same-content pages on the specified applications without modifying corresponding source code. Moreover, the original KSM algorithm relies heavily on the specified area is rich in same-content pages, while normal applications have much less same-content pages compared to virtual machines. So, when KSM is applied to those applications, it is possible that memory usage will rise rather than decrease. To combat with this situation, KSM+ employs a new algorithm to decrease the memory usage for running itself. Several experiments prove that the KSM+ can be easily applied to specified applications and memory usage can be reduced. And a case is designed to compare the effect between KSM and KSM+, which shows KSM+ behaves better in deduplication when the same-content pages’ density is very low. At last, in order to inspect the characteristics of same-content pages from normal desktop applications, an ad-hoc kernel module is developed to do the statistics which supplies significant data for the further development of KSM+. Key Words： KSM, Deduplication, Memory Management   ...

 epoll学习报告                              kamuszhou 周霄 Jul/26/2013   这几天通读了内核中对epoll I/O模型的实现代码，结合网络上很多介绍epoll的文章，对epoll的实现原理已经很熟悉，下面谈谈我的几点体会。下文引用的内核代码来自3.9.6版本的内核，见URL：http://lxr.oss.org.cn/source/fs/eventpoll.c。   一. epoll的边沿触发(ET)的效率高于电平(LT)触发的效率     首先简单介绍一个背景：epoll实现中，把已经有事件发生的文件用一个双链表链接一起，这个双链表是在struct eventpoll结构中的rdllist域。用户空间调用epoll_wait()，陷入内核后就会立即检查这个双链表，如果链表中非空，就通过文件的poll()函数询问文件有无事件发生。如果有事件发生且是用户关心的，就会向用户空间报告，否则就睡眠。     epoll的实现代码中实际上只有两行代码与触发方式有关，如下图所示。  上图所示的代码运行的上下文情况是：用户加入到epoll中的某个文件，只要支持poll()，(可以是socket，FIFO，裸设备，whatever)有关心的事件到达(或可读，或可写，或报错)，内核空间已经把发生的事件复制到了用户空间，但还没有从内核态返回用户空间。在返回用户空间之前代码检查用被epoll监视的这个文件是否是ET触发，如果不是(那就是LT),就把监视的文件重新放回就绪队列，下次epoll_wait()调用的时候会立即重新检查这个文件有否有事件到达。如果这文件的确有事件发生，则epoll_wait()报告给调用者。如果没有，而且其它被监视的文件也没有事件发生，则调用epoll_wait()的task就让出处理器，开始睡觉(TASK_INTERRUPTIBLE)。这段逻辑在static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, int maxevents, long timeout)中，第1494行。 如果监听的文件开启的是边沿触发(默认)，则不会执行上图中的list_add_tail()逻辑。这就是边沿触发只会向用户报告一次，直到下一个关心事件发生才向用户空间报告的原因。 那么为什么ET触发效率高于LT触发呢？看一个例子，假如客户端监视一个TCP的Socket，服务端这时发来1M数据，客户端的主机网卡驱动缓存足够大，一次性接收到了所有1M数据。下面看两段客户端的接收伪代码(没有写read调用返回时socket被关闭的情况；另socket描述符fd被设为非阻塞)。    上图的代码使用了LT触发，这段代码依赖epoll_wait()通知还有数据可供读取。所以共调用了1024次epoll_wait()，1024次read()，共2048次系统调用才读完1M数据。   上图使用ET触发，epoll_wait()只报告一次，然后代码循环调用1024次read()读完数据，直到第1025次read()返回-1，出错码为EAGAIN(EAGAIN等于EWOULDBLOCK)，于是代码知道已经接收完数据。一共只使用了1026次系统调用就读完了数据。 总结：即使使用电平触发也不要依赖epoll_wait()通知调用者到达事件，需要循环调用IO函数直到被通知EAGAIN，这样就把epoll_wait()的调用次数降到最低，仅管有可能在下次epoll_wait()时会有可能浪费一次文件的poll()调用，但这个很小的开销可以忽略。   二. 为什么epoll支持嵌套调用 读epoll的实现代码发现，一个epoll的文件描述符epfd可以嵌套的加入另一个epoll。这样有什么用呢？ epoll的实现中“平等的”对待每个被监视的文件，它们维护在一棵红黑树之中，假如有十万个文件被监视，那么查找某个文件时就要在这十万个文件中查找。即使红黑树的查找效率是log(n)，文件非常大时也是比较消耗时间的。 那么假如有这样一种情况，如果这十万个文件中只有1000个是活跃的，或者说这1000个文件优先级最高。那么则有一种优化方案是，创建两个epoll，第一个epoll（epfd0）监控100000 – 1000 个文件，第二个epoll (epfd1) 监控1000个高优先级文件以及epfd0。这样的好处是，大多数情况下epoll实现只在1001个元素的红黑树中查找，自然效率提高了。 总结：epoll的嵌套调用给开发者提供了一个在高并发环境下的优化方案。   三. epoll的效率一定比select/poll高吗。     答案是不一定。 Select的缺点大致有： 1. 内核中写死了最多只能监视1024个文件. 2. 每次调用select都要把关心的文件描述符和关心的文件件从一个用户空间的长长的数组拷贝到内核空间. 3. select若使得caller进程进入睡眠后，某个文件有事件到达此进程被唤醒，那么所有被监视的文件全部会被调用poll()询问“你有没有事件到达”，这是一个线性的时间复杂度。 epoll针对select的三个缺点的改进： 1. 监视的文件数由取决于系统中有多少低端内存(x86_64架构中的所有内存都是低端内存)。3.9.6版本的内核实现中，对于每个登录用户，最多使用系统中低端内存的4%用来创建监视用的数据结构。见第1951行代码。max_user_watches = (((si.totalram – si.totalhigh) / 25) << PAGE_SHIFT) / EP_ITEM_COST; 2. 用户只需要把关心的文件对应的数据结构在调用epoll_wait()前用epoll_ctl()一次性传入内存，以后调用epoll_wait()时不需要像select一样拷贝大量数据。 3. 当调用epoll_wait()的caller进程睡眠时，突然有事件到达，caller进程被唤醒，epoll_wait()返回用户空间，内核并不遍历没有监视的文件，而只报告在一个即短时间内发生的事件。下面更详细的描述这个场景，以监视tcp socket举例，大致是：某进程调用epoll_wait()，此时没有任何它关心的事件发生，于是caller进程进入睡眠。处理器调度了其它进程。数据到达时，当前进程被硬件中断，网卡驱动收到数据包，数据包在中断处理函数中被拷入内核，中断处理函数设置中断下半部(Half Bottom)。下半部被处理器调度，调用epoll实现代码注册的回调函数ep_poll_callback()。ep_poll_callback()函数唤醒之前的caller进程，caller进程重新获得CPU，从epoll实现的ep_poll()函数中恢复执行，在3.9.6内核中的第1564行： if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS))。然后，内核代码开始收集已经就绪的文件和发生的事件，发回用户空间。只有从第一次回调函数ep_poll_callback()被驱动的代码调用（caller进程还在睡眠时执行的ep_poll_callback()算第一次）到epoll实现代码走到第586行关闭中断关闭中断的代码 spin_lock_irqsave(&ep->lock, flags);之间发生的事件才会被收集。     对于第3点，这是epoll的优点，但在某种情况下却会是epoll的缺点。网上很多比较poll, select, epoll性能的文章，没来得及仔细看，我个人认为结论是可靠的。结论引入了一个概念active-to-total ratio，设所有被监控的文件数是n，活跃的文件数是m，active-to-total比则是m/n，如果这个比非常高，比如大于0.7，则poll或select的性能要高过epoll，反之则epoll胜出。     对比前文对select的第3个缺点和epoll的改进点3的叙述可以解释这个原因。因为select在返回用户空间前又轮循了所有关心的文件，而这些文件又大部分是有事件发生的，所以select所做的工作并没有浪费，但epoll只收集了一小段时间中发生的事件，于是select较之epoll减少了用户空间和内核空间的频繁切换，从而让select的性能反超epoll。 那么如何改进呢？明白了以上的原因，那么就可以对epoll做出改进，理论上对于active-to-total比较高的应用环境下，可以在epoll的实现中加入与select做法相同逻辑，即退出前询问所有的监控文件，反正active-to-total比很高。或者更好的方案，用一个链表链接活跃的文件，在epoll返回用户空间前遍历这个链表，争取每一个epoll_wait()调用返回尽可能多的事件。   附：epoll的主要数据结构简介. epoll接口的主要数据结构有struct eventpoll，struct epitem，struct eppoll_entry。     在讲述这三个数据结构前先提一下struct file。Unix设计初期希望它的设计遵从“一切皆文件”的理念。在Linux内核中，每个抽象的文件对应一个内核struct file结构体。Struct file结构体中有一个void *private_data域。不同的文件类型会在private_data域中存放特定的信息。Struct file中另一个域f_op是函数指针的列表，它记录了对应该文件的操作。所有epoll文件的f_op都指向static const struct file_operations eventpoll_fops，因此可以代码判断一个文件是不是epoll如下： static inline int is_file_epoll(struct file *f) {          return f->f_op == &eventpoll_fops; }       每次成功调用epoll_create时就会创建一个struct file的结构体，和一个struct eventpoll。Struct file中的private_data指向struct eventpoll。eventpoll维护了这个epoll的重要信息。其中比较重要的几个字段有：一个循环列表struct list_head  rdllist链接了该epll中已经可以读写或者有出错的文件描述符。一个红黑树的根结点struct rb_root  rbr，eventpoll维护了一棵红黑树，树中的结点是struct epitem。 每个被加入到epoll中被关注的文件描述符都对应一个struct epitem结构体。所有加入到同一个epoll中对应的所有epitem都挂在红黑树上。该红黑树的根结构保存在struct eventpoll中。epitem中记录了对应的文件的文件描述符和文件指针。 struct eppoll_entry是用来挂接到设备文件中的结构体。设备驱动在得知自己可读或可写或有错误时通过这个结构体通知有事件发生。每个eppoll_entry都指向一个epitem，一个epitem可能对应多个eppoll_entry。eppoll_entry中的域wait_queue_t  wait就是被用来挂接到设备文件中的等待队列。设备文件通过wait可以拿到eppoll_entry，再通过eppoll_entry拿到epitem，再拿到eventpoll。    

读代码时发现目前工程中的makefile文件中有一个问题或bug，.即cpp文件没有和该.cpp文件include的头文件建立依赖性。这个危害是，当头文件被修改后，受影响的.cpp文件对应的.o文件不会被重新创建。 而目前的代码中大量使用C++模板，模板的实现全部写在.h文件中. 我做了个实验，修改了单件模板的实现文件 SingletonHolder.h。虽然这个修改影响了大量include了SingletonHolder.h的.cpp文件，但它们对应的.o全被没有被重新编译。 解决方法是用g++编译器提供的 -MM 选项。这个选项会让g++在把.cpp依赖的头文件(除系统头文件)全部列出来。具体的使用方法可以查阅手册。思路是，把cpp文件和头文件的依赖性写入到.d文件，在主makefile文件中include所有的.d文件。 以tcpd工程为列，修改后的makefile如下(亦见附件)，该makefile可以检查到.cpp依赖的头文件被修改，使得重新生成目标文件。 include ./makefile.def SRCS = $(wildcard *.cpp) OBJS = $(patsubst %.cpp,%.o,$(SRCS)) # 每个.cpp都对应一个.d文件，.d文件由g++ -MM生成，列出了.cpp依赖的头文件. DEPENDENCIES = $(subst .cpp,.d,$(SRCS)) TARGET = tcpd OK = [\e[1m\e32m OK [\em FAILURE = [\e[1m\e31m FAILURE [\em all:$(TARGET) # 使包含.d文件，.d文件指定了.o文件依赖哪些头文件。 # 如果不是make clean 就include所有的.d文件。 ifneq “$(MAKECMDGOALS)” “clean” -include $(DEPENDENCIES) endif # 此函数生成.d文件，参考g++的 -MM -MF -MT选项 #$(call make-depend,source-file,object-file,depend-file) define make-depend g++ -MM -MF $3 -MT $2 $(CXXFLAGS) $(CPPFLAGS) $(TARGET_ARCH) $1 ...

Linux桌面环境下内存去重技术的研究与实现 在这里可以下载原稿 www.ykyi.net/upload/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf 第二章 相关理论与技术 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所示。 ...

Linux桌面环境下内存去重技术的研究与实现 在这里可以下载原稿 https://as.goodas.gold/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf 第一章 绪论 1.1 课题背景 内存是操作系统中最为重要的资源之一。为了最有效地利用好有限的内存资源，现代操作系统使用了很多技术以节省内存的使用。在Linux程序的内存布局中，代码段具有只读属性，永远是共享的。具体地说，即使一个程序被实例化了多个进程，但是在物理内存中对于该程序的代码只有一份拷贝，同一个程序的不同进程之间共享这份拷贝。而且，所有共享库（Windows下被称之为动态链接库）的代码段在物理内存中也只有一份拷贝[1]，所有加载了该共享库的进程虽然把共享库加载到了不同的虚拟地址中，但实际上都映射到相同的物理地址上以实现对共享库代码区的共享。除了共享只读的代码区外，可写的页面也可能在进程之间被共享，Linux在创建进程时的fork操作使用写时拷贝技术在父子进程之间共享内存。当父进程调用fork()函数后，所有的可写页面转成写时拷贝页面。只要父子进程都不写入某页面，则该页面一直被共享。 近年来，Linux操作系统中出现了一种新的节省内存的技术，它的出现源于云计算的发展。云计算能够通过互联网按需分发计算机的软硬件资源，被称之为IT产业的又一次革命[2]。虚拟机技术是云计算的基础，Xen和KVM(Kernel Virtual Machine，内核虚拟机)是开源社区最流行的两种虚拟化技术[3]。通过运用虚拟化技术，越来越多的Linux主机上同时运行着多个虚拟机，而虚拟机使用了相同的操作系统，操作系统中运行着相同的大型程序，如数据库服务器，邮件服务器，Web服务器等。在运行多个虚拟机的环境下，人们发现虚拟机之间存在着大量的相同内存页面，但Linux主机没有办法共享这些内存页面。为了解决虚拟机之间大量重复内存的问题，Linux社区诞生了KSM(Kernel Samepage Merging，内核相同页面合并)技术。KSM技术通过扫描内存区域，找到相同的内存页面，并把它们合并。该技术使得运行虚拟机的主机使用的内存明显下降，从而让同样的Linux主机在使用KSM技术后能运行更多的虚拟机。 KSM技术虽然是为基于KVM技术的虚拟机设计，但也能运用到普通的桌面应用程序。随着软硬件技术的不断进步，Linux桌面应用程序占用的内存也越来越多。普通的Linux桌面应用程序中存在多少重复页面，重复页面的分布有些什么特点，把KSM技术运用在桌面应用程序上存在什么问题，这些是本论文将要探讨的内容。针对桌面应用程序的重复内存，本文在KSM的基础上开发了KSM+，能方便有效地合并桌面应用程序的重复内存。 1.2 国内外研究现状 对于传统的节约内存技术，如共享只读代码区，fork的写时拷贝技术。这些技术非常成熟，现代操作系统中已经普通采用。 另外，文献[4]研究了一种比较特殊的节省内存技术。它针对的是科学计算中的特殊程序，通过用注释驱动的工具把源代码转译到更高效的代码，于是编译出节省内存的程序。 近年来研究较多的是基于合并相同内存页面的内存去重技术：通过查找系统中的相同内存页面，把这些页面合并从而节省系统内存。但国内外的研究基本集中在运行虚拟机的场景中。如VMware公司较早进行了虚拟机内存去重技术的研究工作，文献[5]研究了VMware公司的Hypervisor(虚拟机管理器)使用的基于合并相同内容内存页面的去重技术，以减少虚拟机之间的内存冗余。文献[6]详细论述了此类技术对于基于Xen的虚拟机的实现。Linux社区的类似技术称之为KSM。文献[7]以实证研究的方式通过大量实验研究了KSM用于合并虚拟机之间冗余内存的性能。文献[8]研究的是在数据中心中如何提高在虚拟机之间合并相同内存的效率。它实现了通过把虚拟机在各物理机中动态迁移到最适合的位置从而提高合并效率。文献[9]使用KSM技术解决了主机和虚拟机都需要维护自己的缓存的问题，提高了缓存的效率。KSM技术并不是总能高效地去除虚拟机之间的冗余内存，也存在一些问题。内存地址的ASLR(Address Space Layout Randomization，空间布局随机化技术)是为了提高程序安全性的一种技术。该技术提高了程序的安全性，却影响了页面对齐，从而影响了KSM的合并效率[10]。另外，KSM的运用也暴露了安全问题。运行在某台虚拟机上的程序可以通过构造特定的页面尝试让主机的KSM合并它，再计算写该页面所用的时间。因为写被KSM合并的页面的时候会发生写时拷贝，所以这个时间会比正常情况下延迟。通过利用这个时间差，运行在一台虚拟机上的程序可能会发现其它虚拟机上运行的程序[11]，甚至让虚拟机之间秘密通信[12]。 KSM技术应用在非虚拟机的场景下的研究则比较少。欧洲核子研究组织(CERN)的核子实验模拟程序产生海量的数据，并且并行工作的科学程序同时载入这些数据，使得内存中有大量的相同内容页面。CERN通过使用钩子技术修改C运行库的malloc()从而运行KSM，解决了内存中的大量重复页面的问题，节省了8%-48%的内存[13]。 本论文将在一般桌面应用环境下研究并增强新的内存节省技术KSM，使之更适合运用在桌面应用环境下，更有效地减少应用程序的内存使用量。 1.3 研究意义 内存资源总是操作系统中稀缺的资源，研究节省内存的技术具有普遍的意义。另外，随着基于Linux内核的操作系统如Android在消费电子终端上的迅速普及[14]，以及可预见到基于Linux的Chrome OS在PC桌面市场也将占有一定市场，而目前的应用程序普遍占用越来越多的内存，研究Linux平台下新的节省内存的技术KSM，对于开发Android平台等基于Linux内核的平台下的商用优化管理软件具有重要的技术指导作用。 1.4 论文的主要工作 本论文重点研究了Linux内核的KSM模块的设计与实现，并在原来的基础上做了针对桌面应用环境的增强与改进，同时认真研究了Linux内核代码的组织方式，配置与编译方式，内核开发及调试的技术，以及Linux的内存管理单元的实现。增强后的KSM命名为KSM+,它比原来的KSM更方便地自动采集到应用程序的相同内容页面并合并这些页面，以达到节省应用程序消耗的内存的目的。论文用多个实验展示了KSM+的功能，并与修改前的KSM做了比较。此外，本论文还编写了内核模块用于统计Linux桌面应用程序的重复内存页面的特点，同时可以用来应证KSM+运行的效果。 1.5 论文的整体结构布局 本论文的第二章介绍了x86体系的段页式内存管理方式，以及Linux的内存管理的实现，还介绍了编写Linux内核代码的一些基本理论。 第三章介绍了如何使用KSM以及KSM的设计和实现原理。 第四章讲述KSM+的设计与实现。KSM+是在KSM的基础上的增强与改进。 第五章用多个实验展示了KSM+合并程序的重复内存页面的效果，并设计了一个实验比较了KSM和KSM+的差别。最后编写了用于统计应用程序重复内存页面的内核模块，并用统计数据应证了KSM+的实验结果。这些统计数据反映了Linux桌面应用程序中重复内存页面的一些基本特点，对进一步改进KSM+的算法提供了依据。 1.6 本章小结 本章首先介绍了Linux操作系统中传统的节省内存技术，然后引入了因为虚拟化兴起而发展的新的内存节省技术，它通过合并内容相同的内存页面从而减少系统的内存使用，也被称之为内存去重技术，接着叙述了国内外在该技术方面的相关研究。目前对该技术的研究多针对虚拟机环境，而本论文则是在Linux桌面环境中研究内存去重技术。

Linux桌面环境下内存去重技术的研究与实现 在这里可以下载原稿 www.ykyi.net/upload/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf 论文题目： Linux桌面环境下内存去重技术的研究与实现 专业：软件工程 硕士生：周霄 指导教师：王常吉 摘  要 内存管理是操作系统中至关重要的部分。优秀的操作系统高效地管理有限的内存资源。Linux内核的内核同页合并（KSM）模块是在虚拟化兴起后为节省虚拟机使用的内存而发展的一种节约内存的技术。KSM通过合并相同内容页面的方式显著地降低了多个基于内核虚拟机（KVM）技术的虚拟机同时运行时系统使用的内存。实际上，KSM也能合并一般应用程序中的相同内容页面。但一般应用程序为了使用KSM技术合并内存，需要在源代码级别显式地调用相应的系统调用来告知KSM需要扫描的内存区域。对于一般用户来说，需要修改应用程序的源代码显然是一个太高的门槛。 本论文在认真研究了KSM模块的实现的基础上，增强了KSM的功能。新设计实现的KSM+使得用户可以不必修改应用程序的源代码就能利用KSM+合并相同内容的内存页面。另外原来的KSM算法依赖程序指定的内存区域有大量的重复内存页面，而实际上，一般应用程序并没有大量的重复内存。在重复内存非常少的情况下，对这些程序应用KSM技术非但不能降低内存使用，而且因为运行KSM本身所需内存而增加了内存开销。本论文针对这一点在KSM的算法上做了改进，减少了运行KSM+算法本身所消耗的内存。然后论文用Linux桌面下的常用应用程序验证了KSM+的实际效果，并构造了一个实验比较了KSM和KSM+。最后，为了了解应用程序的重复内存页面的特点，还编写了专门统计重复页面的内核模块，发现应用程序的重复页面的一些规律，为持续改进KSM+提供了依据。 **关键词：**KSM，重复内存合并 ，内存管理 Title: Research and Implementation of Memory Deduplication in The Linux Desktop Environment Major: Software Engineering Name: Zhou Xiao Supervisor: Wang Changji Abstract Memory management is one of the most important parts of the operating system. KSM (Kernel Samepage Merging) in Linux kernel is a kind of memory saving technology developed after the emerging of virtual machine. KSM can dramatically decrease the memory usage of the hypervisor running several virtual machines. Actually, KSM can also be applied to normal applications. But in order to use the KSM, application must explicitly evoke a system call in source code level to tell KSM the memory area where the KSM will scan. To normal users, modifying the source code is impossible at most of the time. ...