makefile使cpp文件依赖头文件

读代码时发现目前工程中的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\\e[32m OK \\e[m

FAILURE = \\e[1m\\e[31m FAILURE \\e[m

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

endef

 

 

$(TARGET):$(OBJS)

              @echo -ne Linking $(TARGET) …

              @$(CXX) $(C_FLAGS)  $(INC) -fPIC -o $@ $^ $(LIB) && echo  -e $(OK) || echo -e $(FAILURE)

 

%.o:%.cpp

#如果.cpp文件被修改,就重新生成.d文件.

              $(call make-depend, $<,$@,$(subst .o,.d,$@))

              @echo -ne Compiling $<  …

              @$(CXX) $(C_FLAGS)  $(INC) -fPIC -c -o $@ $< && echo  -e $(OK) || echo -e $(FAILURE)

             

clean:

       @rm -f *.o

       @rm -f ./$(TARGET)

 

install:clean all

#     strip $(TARGET)

 

 

 

Linux桌面环境下内存去重技术的研究与实现(第二章)

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所示。

 

图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内核的内存管理的一些理论和技术,然后介绍了进行内核开发所必须掌握的基础知识。本章的内容是理解以后章节的基础。

Linux桌面环境下内存去重技术的研究与实现(第一章)

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桌面环境中研究内存去重技术。

 

SAN和NAS有什么区别和相同

SAN(Storage Area Network存储区域网络)和NAS(Network Attached Storage不知中文点译)都是提供网络存储的解决方案。

其中NAS是*一个*存储设备,以文件为操作单位。

SAN用一个局域网把很多设备连接起来,以磁盘的块(block)为操作单位。

我的BUG大全。

在这里记下我的程序BUG

buff溢出后,把栈破坏了,这个线程也没崩溃,一直死循环在一小段不可知的代码里。

#调用getaddrinfo很多次以后,getaddrinfo报错:No address associated with NAME。非常地奇怪呀后来把同样的程序部署到比较旧的linux上,报错: Too many open files。才明白,原来fd被用光了。回头再检查相关代码,果然如此~补上close(fd)后,getaddrinfo的问题也解决了。启发是:1. 有些报错信息其实离真正的错误原因很远。2. 一个系统调用一开始正常,跑了很多次后失败,应该怀疑是不是有资源泄露。

#把uint_t类型赋值给std::string时,会崩溃在std::string里面。

#当一个预期统一的规则出现特例的时候容易出现BUG. 关联订单,关联片区,入货地址都指受YYYY-MM-DD HH:MM:SS的时间戳,但同机分析接受的时间戳却是YYYYMMDD某一天的时间戳。有一个组合需求是同时导出上述4个小需求时,由于传入的时间戳参数不一致导致了BUG.

vector::push_back可能会重新分配vector的内存,导致指向之前元素的引用和指针失效.一个std::function持有一个std::ref指向vector中的一个元素,当这个funcction被调用的时候,vector中的这个元素已经失效了。

# 用boost::optional记录一个信息。这个信息没及时在clear函数里做清理。于是,观察到的情况时,这个信息总是被打印。但一开始,我们却怀疑是另外的函数不稳定而重新生成了该信息。

在写一个匹配函数时,待匹配操作数是一个字符串,我没有考虑字符串是空串的情况。

在比较旧的gcc 4.1.2上把shared_ptr赋给 weak_ptr时,崩溃。溃在atomic_exchange_and_add。一开始怀疑是旧版gcc对boost的智能指针支持的不够好,后来发现是因为weak_ptr此时已经失效了。原因是用handler的参数持用shared_ptr的引用做生命期管理时,传错了参数,使得这个对象已经被销毁了。

现象:一个依赖某布尔变量的逻辑大多数时候正常,少部分时间异常。期望这个布尔变量是false,有时候陌名其妙变成了true。

原因是此布尔变量未被初始化,大多数时候它的值是false,但有时却不是。

#. 现象rmap_item泄露.

Fix it: 单链表插入新结点时指针操作出错。应该是new->rmap_list = item,被我写成 new->rmap_list = (item)->rmap_list.

#. 我意图注释掉某行代码,却鬼使神差注释错了一行代码。

#. 变量名 pkt 和ptr 很像,在用memcpy函数时用错了变量导致bug. 一块内存被莫名其妙的修改了,很有可能是因为像刚才这样写这块函数的参数填错了。

#. _sessions.erase(ite++);删除了_sessions维护的一个对象.对象的析构被调用,会有一连串对象的析构因此而被调用。这些对象中的指针很可能就失效了。但是,在代码的其它地方还能拿到这个指针。野指针啊!!!今天这个例子中是session维护的ip_pkt对象都被析构了,ip_pkt中的指针也都失效了。于是,一使用野指针,崩溃了。

#. 删除数据时,总是要注意其它代码中指向这些被删除数据的引用或指针。

#. 解引用container.end()返回的迭代器会崩溃。

#. 这是个腾讯视频广告投放组的bug. 一个线程负责开,关FD。另一个线程读写FD。两个线程的竞争条件造成了BUG.

#. 写代码时偷懒复制代码,然后忘记做相应更改,视觉上很难在第一时间察觉,却在后期花费了几倍时间调试程序。

#. 写判断语句时,判断表达示如 container.empty()之前是否要取反,经常搞错。

#. htonl 写成 htons

#. std::distance 计算两个迭代器之间距离时死循环,是因为迭代器没有初始化。而我之前想,作初始化工作的函数已经调用了,实际上并没有被调用。

#. 没注意函数的返回值. 有时函数返回0时表示成功,即true的含义。所以看到一些和预期刚好相反的现象时,应该考虑是不是出现了这样的错误。

#. 又是迭代器失效。erase(ite++), continue,但是for循环里有++ite。结果迭代器被加了两次。

#. 追踪到原因是野指针。野指针的特点是在调试器里会看到乱七八糟的值,如果只看一些标志变量会让人觉得颠覆了之前建立的逻辑,于是又去跟踪逻辑有没有问题。而这次bug,逻辑本身没错,而应该去找野指针是如何产生的。这次的野指针产生是因为负数取模后得到负数,又用这个负数作为索引去拿对象,结果拿到了无效的对象。这次的经验是,即使是超级简单的一些逻辑,觉得自己一定能保定索引是用效的,但一些不经意的代码给你生产了不合法的索引,于是花费大量时间追踪。对简单的判断多下诊断喔!

在实现一个clone函数时,new出了新的对象,想要引用新对象的数据的时候很容易忘用新对象的引用来引用新对象的数据,于是新对象的数据并没有正常赋值,又写坏了this的数据。

又是指针操作越界,因为各种length计算出错。

timer表示一个局部定时器, timer_是一个class的定时器。因为没看到下划线搞错了!!!

一个指向char 的 ite,解引用这个ite后赋给 int,因为char是有符号的,int也是有符号,所以当char是负数时int也是负数。

两个容器中存放了指针指向同一批对象。清理的时候,delete了A容器中的指针指向的堆空间向,给A调用了clear。但是,B容器忘记clear了。结果,B容器中的指针都变成了野指针。

两个嵌套的内外循环。外循环用 i, 内循环用 j,算法要用j 的时候写了 i。

如果没有初始化,算法的核心部分是没办法工作的,但又不报错。查了好久,原来旧代码写的一个类把做的最重的业务也写在构造函数里。而我的加速用的hash表的初始化放在构造函数的最后一行,结果hash表没初始化就开始跑最重的核心业务了。于是加速哈希表完全没起作用还导致了BUG,查了好久。

 

泪流满面,WARNING: modpost: Found 1 section mismatch(es).

看来编译时出现警告要非常重视,一定要对警告的意义非常清楚,这极可能是出现BUG的原因。

昨天调了一整个晚上,各种离奇的出错~~

其实编译内核模块时,已经提示我警告了,但我一直没注意:

  Building modules, stage 2.
  MODPOST 1 modules
WARNING: modpost: Found 1 section mismatch(es).
To see full details build your kernel with:
'make CONFIG_DEBUG_SECTION_MISMATCH=y'
  CC      /home/zausiu/linux-3.0.66/mm/sksm/sksm.mod.o
  LD [M]  /home/zausiu/linux-3.0.66/mm/sksm/sksm.ko

警告告诉我使用 'make CONFIG_DEBUG_SECTION_MISMATCH=y'

我以为要编译整棵kenel sourcecode tree时打开DEBUG_SECTION_MISMATCH编译选项,在我的虚机里编译一次要几个小时啊,果断拒绝了。其实在内核代码树外单独编译内核模块时也只用DEBUG_SECTION_MISMATCH=y这个选项。

# make DEBUG_SECTION_MISMATCH=y

  Building modules, stage 2.
  MODPOST 1 modules
WARNING: /home/zausiu/linux-3.0.66/mm/sksm/sksm.o(.init.text+0x193): Section mismatch in reference from the function init_module() to the function .exit.text:sksm_slab_free()
The function __init init_module() references
a function __exit sksm_slab_free().
This is often seen when error handling in the init function
uses functionality in the exit path.
The fix is often to remove the __exit annotation of
sksm_slab_free() so it may be used outside an exit section.

至此,真相大白于天下~~ .init段的函数内调用了 .exist段的函数,把被调用函数去掉__exit指示即可!

//////////

至此,当出现离奇错误时。要高度重视编译时的警告,另外一个就是极有可能是因为竞争条件,还有个是栈溢出。

dpkg的一些用法

Debian的dpkg的一些用法

 

1. 查看当前系统中的软件信息(dpkg -l)


"dpkg -l"命令用于查看当前系统中所有deb的软件包信息;通过"dpkg -l"命令与less和grep命令配合使用,可以实现更复杂的软件包信息查询功能。





debian:~/Desktop# dpkg -l


期望状态=未知(u)/安装(i)/删除(r )/清除(p)/保持(h)


| 当前状态=未(n)/已安装(i)/仅存配置(c )/仅解压缩(U)/配置失败(F)/不完全安装(H)


|/ 错误?=(无)/保持(?)/须重装(R )/两者兼有(#) (状态,错误:大写=故障)


||/ 名称 版本 简介







2 查询已安装的指定软件包的详细信息(dpkg -s)


使用"dpkg -s"命令查询ssh软件包的详细信息

3 查询系统中已安装的软件包所安装的文件(dpkg -L)





显示"ssh"软件包安装到系统的文件





debian:~# dpkg -L ssh


/.


/usr


/usr/share


/usr/share/doc


/usr/share/doc/openssh-client


/usr/share/doc/ssh






4 查询系统中的某个文件属于哪个软件包(dpkg -S)





debian:~# dpkg -S /etc/init.d/networking


netbase: /etc/init.d/networking



文件"/etc/init.d/networking"属于名为"netbase"的软件包。





debian:~# dpkg -S /etc/passwd


dpkg:没有找到 /etc/passwd。



系统中许多文件不属于任何软件包,它们可能是用户

GCC内联汇编写的memcmp函数 for x86-64

今天写内核代码时要写一个比较两个页框(Page Frame)的函数,想到用内联汇编来写这个功能。下面是代码:

long cmp_x64(void *s1, void *s2, size_t n)
{
    size_t num = n / 8;
    register long res;

    __asm__ __volatile__
    (
     "testq %3,%3\n\t"               ; 测试num是不是0
     "repe  cmpsq\n\t"                ; 不停地比较直到cx寄存器为0或比较到差别
     "je        1f\n\t"              ; 两块内存相等,跳出,返回0.
     "sbbq      %0,%0\n\t"    ; sbb是x86的减法指令,会额外地减去CF(借位)的值,这样%0就会是0或者-1
     "orq       $1,%0\n"         ; 把立即数1或到%0上,这样%0就会是1或者-1.
     "1:"
         : "=&a"(res)          ;  传入变量res放入寄存器ax,且这个变量是输出值(=),不要与其它输入输出共用寄存器(&)
     : "0"(res), "S"(s1), "D"(s2), "c"(num)  ; 输入列表
     : "cc");           // clobber list 告诉gcc在这段内联汇编中哪些寄存器被显式/隐式修改.If our instruction can alter the condition code register, we have to add "cc" to the list of clobbered registers.

    return res;
}

Linux内核中的宏可变参数(GCC的宏可变参数)

Linux内核中的宏可变参数(GCC的宏可变参数)。
写内核模块的时候为了调试方便,经常需要wrap一下printk函数。下面的宏定义非常有实用价值。
注意两个井号~~
记到博客里~~

#define seclvl_printk(verb, type, fmt, arg...)			\
	do {							\
		if (verbosity >= verb) {			\
			static unsigned long _prior;		\
			unsigned long _now = jiffies;		\
			if ((_now - _prior) > HZ) {		\
				printk(type "%s: %s: " fmt,	\
					MY_NAME, __FUNCTION__ ,	\
					## arg);		\
				_prior = _now;			\
			}					\
		}						\
	} while (0)

今天用Debian时总遇到locale的错误.

我的debian一般把LC_ALL设成en_US.UTF-8。这次dpkg-reconfigure locales时没有选美国英语,而是用了香港英语。于是就出错了。

解决方法的关键在于  /etc/environment 文件,  dpkg-reconfigure locales 命令用来配置local,以及locale命令列出当前期待的locale,还有 local-gen 命令可以生成local.

debian报得错误类似于:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = "en_US:en",
    LC_ALL = (unset),
    LANG = "en_US"
    are supported and installed on your system.

////////////

另外今天还解决了编译内核后,用新内核启动时报错:

kernel panic – not syncing VFS: unable to mount root fs on unknown block (0, 0)

// 通常这是因为对应文件系统被编译成模块,那么就应该生成initrd加载对应的文件驱动模块。在debian下,用update-initramfs 命令生成对应的initrd. 如: update-initramfs -c -k 3.0.63