3.html

介绍linux下文件和设备编程

&nbsp;&nbsp;&nbsp; default_ldt：理论上每个进程都可以同时使用很多段，这些段可以存储在自己的ldt段中，但实际linux极少利用x86的这些功能，多数情况下所有进程共享这个段，它只包含一个空描述符。<p>
&nbsp;&nbsp;&nbsp; 还有一些特殊的段用在电源管理等代码中。<p>
&nbsp;&nbsp;&nbsp; （在2.2以前，每个进程的ldt和TSS段都存在GDT中，而GDT最多只能有8192项，因此整个系统的进程总数被限制在4090左右。2。4里不再把它们存在GDT中，从而取消了这个限制。）<p>
&nbsp;&nbsp;&nbsp; __USER_CS和__USER_DS段都是被所有在用户态下的进程共享的。注意不要把这个共享和进程空间的共享混淆：虽然大家使用同一个段，但通过使用不同的页表由分页机制保证了进程空间仍然是独立的。<p>
<br>
x86的分页机制<p>
&nbsp;&nbsp;&nbsp; x86硬件支持两级页表，奔腾pro以上的型号还支持Physical address Extension Mode和三级页表。所谓的硬件支持包括一些特殊寄存器(cr0-cr4)、以及CPU能够识别页表项中的一些标志位并根据访问情况做出反应等等。如读写Present位为0的页或者写Read/Write位为0的页将引起CPU发出page fault异常，访问完页面后自动设置accessed位等。<p>
&nbsp;&nbsp;&nbsp; linux采用的是一个体系结构无关的三级页表模型（如图），使用一系列的宏来掩盖各种平台的细节。例如，通过把PMD看作只有一项的表并存储在pgd表项中（通常pgd表项中存放的应该是pmd表的首地址），页表的中间目录(pmd)被巧妙地‘折叠’到页表的全局目录(pgd)，从而适应了二级页表硬件。<p>
TLB<p>
&nbsp;&nbsp;&nbsp; TLB全称是Translation Look-aside Buffer,用来加速页表查找。这里关键的一点是：如果操作系统更改了页表内容，它必须相应的刷新TLB以使CPU不误用过时的表项。<p>
<br>
Cache<p>
&nbsp;&nbsp;&nbsp; Cache 基本上是对程序员透明的，但是不同的使用方法可以导致大不相同的性能。linux有许多关键的地方对代码做了精心优化，其中很多就是为了减少对cache不必要的污染。如把只有出错情况下用到的代码放到.fixup section，把频繁同时使用的数据集中到一个cache行（如struct task_struct），减少一些函数的footprint，在slab分配器里头的slab coloring等。<p>
&nbsp;&nbsp;&nbsp; 另外，我们也必须知道什么时候cache要无效：新map/remap一页到某个地址、页面换出、页保护改变、进程切换等，也即当cache对应的那个地址的内容或含义有所变化时。当然，很多情况下不需要无效整个cache，只需要无效某个地址或地址范围即可。实际上，<p>
&nbsp;&nbsp;&nbsp; intel在这方面做得非常好用，cache的一致性完全由硬件维护。<p>
&nbsp;&nbsp;&nbsp; 关于x86处理器更多信息，请参照其手册：Volume 3: Architecture and Programming Manual<p>
<br>
8． Linux 相关实现<p>
&nbsp;&nbsp;&nbsp; 这一部分的代码和体系结构紧密相关，因此大多位于arch子目录下，而且大量以宏定义和inline函数形式存在于头文件中。以i386平台为例，主要的文件包括：<p>
page.h<p>
&nbsp;&nbsp;&nbsp; 页大小、页掩码定义。PAGE_SIZE,PAGE_SHIFT和PAGE_MASK。<p>
&nbsp;&nbsp;&nbsp; 对页的操作，如清除页内容clear_page、拷贝页copy_page、页对齐page_align<p>
&nbsp;&nbsp;&nbsp; 还有内核虚地址的起始点：著名的PAGE_OFFSET:)和相关的内核中虚实地址转换的宏__pa和__va.。<p>
&nbsp;&nbsp;&nbsp; virt_to_page从一个内核虚地址得到该页的描述结构struct page *.我们知道，所有物理内存都由一个memmap数组来描述。这个宏就是计算给定地址的物理页在这个数组中的位置。另外这个文件也定义了一个简单的宏检查一个页是不是合法：VALID_PAGE(page)。如果page离memmap数组的开始太远以至于超过了最大物理页面应有的距离则是不合法的。<p>
&nbsp;&nbsp;&nbsp; 比较奇怪的是页表项的定义也放在这里。pgd_t,pmd_t,pte_t和存取它们值的宏xxx_val<p>
<br>
pgtable.h pgtable-2level.h pgtable-3level.h<p>
&nbsp;&nbsp;&nbsp; 顾名思义，这些文件就是处理页表的，它们提供了一系列的宏来操作页表。pgtable-2level.h和pgtable-2level.h则分别对应x86二级、三级页表的需求。首先当然是表示每级页表有多少项的定义不同了。而且在PAE模式下，地址超过32位，页表项pte_t用64位来表示(pmd_t,pgd_t不需要变)，一些对整个页表项的操作也就不同。共有如下几类：<p>
&nbsp;&nbsp;&nbsp; &middot;[pte/pmd/pgd]_ERROR 出措时要打印项的取值，64位和32位当然不一样。<br>
&nbsp;&nbsp;&nbsp; &middot;set_[pte/pmd/pgd] 设置表项值<br>
&nbsp;&nbsp;&nbsp; &middot;pte_same 比较 pte_page 从pte得出所在的memmap位置<br>
&nbsp;&nbsp;&nbsp; &middot;pte_none 是否为空。<br>
&nbsp;&nbsp;&nbsp; &middot;__mk_pte 构造pte<p>
&nbsp;&nbsp;&nbsp; pgtable.h的宏太多，不再一一解释。实际上也比较直观，通常从名字就可以看出宏的意义来了。pte_xxx宏的参数是pte_t,而ptep_xxx的参数是pte_t *。2.4 kernel在代码的clean up方面还是作了一些努力，不少地方含糊的名字变明确了，有些函数的可读性页变好了。<p>
&nbsp;&nbsp;&nbsp; pgtable.h里除了页表操作的宏外，还有cache和tlb刷新操作，这也比较合理，因为他们常常是在页表操作时使用。这里的tlb操作是以__开始的，也就是说，内部使用的，真正对外接口在pgalloc.h中（这样分开可能是因为在SMP版本中，tlb的刷新函数和单机版本区别较大，有些不再是内嵌函数和宏了）。<p>
pgalloc.h<p>
&nbsp;&nbsp;&nbsp; 包括页表项的分配和释放宏/函数,值得注意的是表项高速缓存的使用：<p>
&nbsp;&nbsp;&nbsp; pgd/pmd/pte_quicklist<p>
&nbsp;&nbsp;&nbsp; 内核中有许多地方使用类似的技巧来减少对内存分配函数的调用，加速频繁使用的分配。如buffer cache中buffer_head和buffer，vm区域中最近使用的区域。<p>
&nbsp;&nbsp;&nbsp; 还有上面提到的tlb刷新的接口<p>
segment.h<p>
&nbsp;&nbsp;&nbsp; 定义 __KERNEL_CS[DS] __USER_CS[DS]<p>
参考：<p>
&nbsp;&nbsp;&nbsp; 《Understanding the Linux Kernel》的第二章给了一个对linux 的相关实现的简要描述，<p>
<p>
物理内存的管理。<p>
&nbsp;&nbsp;&nbsp; 2.4中内存管理有很大的变化。在物理页面管理上实现了基于区的伙伴系统（zone based buddy system）。区(zone)的是根据内存的不同使用类型划分的。对不同区的内存使用单独的伙伴系统(buddy system)管理,而且独立地监控空闲页等。<p>
&nbsp;&nbsp;&nbsp; (实际上更高一层还有numa支持。Numa(None Uniformed Memory Access)是一种体系结构，其中对系统里的每个处理器来说,不同的内存区域可能有不同的存取时间(一般是由内存和处理器的距离决定)。而一般的机器中内存叫做DRAM，即动态随机存取存储器，对每个单元，CPU用起来是一样快的。NUMA中访问速度相同的一个内存区域称为一个Node，支持这种结构的主要任务就是要尽量减少Node之间的通信，使得每个处理器要用到的数据尽可能放在对它来说最快的Node中。2.4内核中node&amp;#0;相应的数据结构是pg_data_t，每个node拥有自己的memmap数组，把自己的内存分成几个zone，每个zone再用独立的伙伴系统管理物理页面。Numa要对付的问题还有很多，也远没有完善，就不多说了)<p>
基于区的伙伴系统的设计&amp;#0;物理页面的管理<p>
&nbsp;&nbsp;&nbsp; 内存分配的两大问题是：分配效率、碎片问题。一个好的分配器应该能够快速的满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。伙伴系统是一个常用的比较好的算法。(解释：TODO)<p>
引入区的概念是为了区分内存的不同使用类型（方法？），以便更有效地利用它们。<p>
&nbsp;&nbsp;&nbsp; 2.4有三个区：DMA, Normal, HighMem。前两个在2.2实际上也是由独立的buddy system管理的，但2.2中还没有明确的zone的概念。DMA区在x86体系结构中通常是小于16兆的物理内存区，因为DMA控制器只能使用这一段的内存。而HighMem是物理地址超过某个值(通常是约900M)的高端内存。其他的是Normal区内存。由于linux实现的原因，高地址的内存不能直接被内核使用，如果选择了CONFIG_HIGHMEM选项，内核会使用一种特殊的办法来使用它们。（解释：TODO）。HighMem只用于page cache和用户进程。这样分开之后，我们将可以更有针对性地使用内存，而不至于出现把DMA可用的内存大量给无关的用户进程使用导致驱动程序没法得到足够的DMA内存等情况。此外，每个区都独立地监控本区内存的使用情况，分配时系统会判断从哪个区分配比较合算，综合考虑用户的要求和系统现状。2.4里分配页面时可能会和高层的VM代码交互(分配时根据空闲页面的情况，内核可能从伙伴系统里分配页面，也可能直接把已经分配的页收回&amp;#0;reclaim等)，代码比2.2复杂了不少，要全面地理解它得熟悉整个VM工作的机理。<p>
整个分配器的主要接口是如下函数(mm.h page_alloc.c)：<p>
struct page * alloc_pages(int gfp_mask, unsigned long order) 根据gftp_mask的要求，从适当的区分配2^order个页面，返回第一个页的描述符。<p>
#define alloc_page(gfp_mask) alloc_pages(gfp_mask,0)<p>
unsigned long __get_free_pages((int gfp_mask, unsigned long order) 工作同alloc_pages,但返回首地址。<p>
#define __get_free_page(gfp_mask) __get_free_pages(gfp_mask,0)<p>
get_free_page 分配一个已清零的页面。<p>
__free_page(s) 和free_page(s)释放页面（一个/多个）前者以页面描述符为参数，后者以页面地址为参数。<p>
&nbsp;&nbsp;&nbsp; 关于Buddy算法，许多教科书上有详细的描述，第六章对linux的实现有一个很好的介绍。关于zone base buddy更多的信息，可以参见Rik Van Riel 写的&quot; design for a zone based memory allocator&quot;。这个人是目前linuxmm的维护者，权威啦。这篇文章有一点过时了，98年写的，当时还没有HighMem，但思想还是有效的。还有，下面这篇文章分析2.4的实现代码：<p>
http://home.earthlink.net/~jknapka/linux-mm/zonealloc.html。<p>
<br>
Slab--连续物理区域管理<p>
&nbsp;&nbsp;&nbsp; 单单分配页面的分配器肯定是不能满足要求的。内核中大量使用各种数据结构，大小从几个字节到几十上百k不等，都取整到2的幂次个页面那是完全不现实的。2.0的内核的解决方法是提供大小为2,4,8,16,...,131056字节的内存区域。需要新的内存区域时，内核从伙伴系统申请页面，把它们划分成一个个区域，取一个来满足需求；如果某个页面中的内存区域都释放了，页面就交回到伙伴系统。这样做的效率不高。有许多地方可以改进：<p>
&nbsp;&nbsp;&nbsp; 不同的数据类型用不同的方法分配内存可能提高效率。比如需要初始化的数据结构，释放后可以暂存着，再分配时就不必初始化了。<br>
&nbsp;&nbsp;&nbsp; 内核的函数常常重复地使用同一类型的内存区，缓存最近释放的对象可以加速分配和释放。<br>
&nbsp;&nbsp;&nbsp; 对内存的请求可以按照请求频率来分类，频繁使用的类型使用专门的缓存，很少使用的可以使用类似2.0中的取整到2的幂次的通用缓存。<br>
&nbsp;&nbsp;&nbsp; 使用2的幂次大小的内存区域时高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少高速缓存冲突。<br>
&nbsp;&nbsp;&nbsp; 缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的高速缓存污染。<p>
2.2实现的slab分配器体现了这些改进思想。<p>
主要数据结构<p>
接口：<p>
kmem_cache_create/kmem_cache_destory<p>
kmem_cache_grow/kmem_cache_reap 增长/缩减某类缓存的大小<p>
kmem_cache_alloc/kmem_cache_free 从某类缓存分配/释放一个对象<p>
kmalloc/kfree 通用缓存的分配、释放函数。<p>
相关代码(slab.c)。<p>
相关参考：<p>
http://www.lisoleg.net/lisoleg/memory/slab.pdf ：Slab发明者的论文，必读经典。<p>
第六章，具体实现的详细清晰的描述。<p>
AKA2000年的讲座也有一些大虾讲过这个主题，请访问aka主页：www.aka.org.cn<p>
<br>
vmalloc/vfree &amp;#0;物理地址不连续，虚地址连续的内存管理<p>
&nbsp;&nbsp;&nbsp; 使用kernel页表。文件vmalloc.c，相对简单。<p>
<br>
2.4内核的VM(完善中。。。)<p>
进程地址空间管理<p>
&nbsp;&nbsp;&nbsp; 创建，销毁。<p>
mm_struct, vm_area_struct, mmap/mprotect/munmap<p>
page fault处理，demand page, copy on write<p>
<br>
相关文件：<p>
include/linux/mm.h：struct page结构的定义，page的标志位定义以及存取操作宏定义。struct vm_area_struct定义。mm子系统的函数原型说明。<p>
include/linux/mman.h:和vm_area_struct的操作mmap/mprotect/munmap相关的常量宏定义。<p>
memory.c：page fault处理，包括COW和demand page等。<p>
对一个区域的页表相关操作:<p>
zeromap_page_range: 把一个范围内的页全部映射到zero_page<p>
remap_page_range：给定范围的页重新映射到另一块地址空间。<p>
zap_page_range：把给定范围内的用户页释放掉，页表清零。<p>
mlock.c： mlock/munlock系统调用。mlock把页面锁定在物理内存中。<p>
mmap.c:：mmap/munmap/brk系统调用。<p>
mprotect.c： mprotect系统调用。<p>
&nbsp;&nbsp;&nbsp; 前面三个文件都大量涉及vm_area_struct的操作，有很多相似的xxx_fixup的代码，它们的任务是修补受到影响的区域，保证vm_area_struct 链表正确。<p>
<br>
交换<p>
目的：<p>
&nbsp;&nbsp;&nbsp; 使得进程可以使用更大的地址空间。同时容纳更多的进程。<p>
任务：<p>
&nbsp;&nbsp;&nbsp; 选择要换出的页<p>
&nbsp;&nbsp;&nbsp; 决定怎样在交换区中存储页面<p>
&nbsp;&nbsp;&nbsp; 决定什么时候换出<p>
kswapd内核线程：每10秒激活一次<p>
&nbsp;&nbsp;&nbsp; 任务：当空闲页面低于一定值时，从进程的地址空间、各类cache回收页面<p>
&nbsp;&nbsp;&nbsp; 为什么不能等到内存分配失败再用try_to_free_pages回收页面？原因：<p>
&nbsp;&nbsp;&nbsp; 有些内存分配时在中断或异常处理调用，他们不能阻塞<p>
&nbsp;&nbsp;&nbsp; 有时候分配发生在某个关键路径已经获得了一些关键资源的时候，因此它不能启动IO。如果不巧这时所有的路径上的内存分配都是这样，内存就无法释放。<p>
kreclaimd 从inactive_clean_list回收页面，由__alloc_pages唤醒。<p>
相关文件：<p>
mm/swap.c kswapd使用的各种参数以及操作页面年龄的函数。<p>