内存.txt

讲解linux内核 内存管理 部分经典讲义

                    |pte_alloc
                       |pte_alloc_one
                          |__get_free_page = __get_free_pages
                             |alloc_pages
                                |alloc_pages_pgdat
                                   |__alloc_pages
                                      |wakeup_kswapd // We wake up kernel thread 
kswapd

·do_page_fault [arch/i386/mm/fault.c]
·handle_mm_fault [mm/memory.c]
·pte_alloc
·pte_alloc_one [include/asm/pgalloc.h]
·__get_free_page [include/linux/mm.h]
·__get_free_pages [mm/page_alloc.c]
·alloc_pages [mm/numa.c]
·alloc_pages_pgdat
·__alloc_pages
·wakeup_kswapd [mm/vmscan.c] 
[目录]




内存管理子系统导读from aka

    
我的目标是‘导读’，提供linux内存管理子系统的整体概念，同时给出进一步深入研究某个部分时的辅助信息(包括代码组织,文件和主要函数的意义和一些参考文档)。之所以采取这种方式，是因为我本人在阅读代码的过程中，深感“读懂一段代码容易，把握整体思想却极不容易”。而且，在我写一些内核代码时，也觉得很多情况下，不一定非得很具体地理解所有内核代码，往往了解它的接口和整体工作原理就够了。当然，我个人的能力有限，时间也很不够，很多东西也是近期迫于讲座压力临时学的：），内容难免偏颇甚至错误，欢迎大家指正。
存储层次结构和x86存储管理硬件（MMU）
    这里假定大家对虚拟存储，段页机制有一定的了解。主要强调一些很重要的或者容易误解的概念。
存储层次
    高速缓存(cache) --〉 主存(main memory) ---〉 磁盘(disk)
    理解存储层次结构的根源：CPU速度和存储器速度的差距。
    层次结构可行的原因：局部性原理。
LINUX的任务:
    减小footprint，提高cache命中率，充分利用局部性。
    实现虚拟存储以满足进程的需求，有效地管理内存分配，力求最合理地利用有限的资源。
参考文档：
    《too little,too small》by Rik Van Riel, Nov. 27,2000.
    以及所有的体系结构教材：）

MMU的作用
    辅助操作系统进行内存管理，提供虚实地址转换等硬件支持。

x86的地址
    逻辑地址： 出现在机器指令中，用来制定操作数的地址。段：偏移
    线性地址：逻辑地址经过分段单元处理后得到线性地址，这是一个32位的无符号整数，可用于定位4G个存储单元。
    物理地址：线性地址经过页表查找后得出物理地址，这个地址将被送到地址总线上指示所要访问的物理内存单元。
LINUX: 尽量避免使用段功能以提高可移植性。如通过使用基址为0的段，使逻辑地址==线性地址。

x86的段
    
保护模式下的段：选择子+描述符。不仅仅是一个基地址的原因是为了提供更多的信息：保护、长度限制、类型等。描述符存放在一张表中(GDT或LDT)，选择子可以认为是表的索引。段寄存器中存放的是选择子，在段寄存器装入的同时，描述符中的数据被装入一个不可见的寄存器以便cpu快速访问。（图）P40
    专用寄存器：GDTR(包含全局描述附表的首地址),LDTR（当前进程的段描述附表首地址）,TSR（指向当前进程的任务状态段）

LINUX使用的段：
    __KERNEL_CS： 内核代码段。范围 0-4G。可读、执行。DPL=0。
    __KERNEL_DS：内核代码段。范围 0-4G。可读、写。DPL=0。
    __USER_CS：内核代码段。范围 0-4G。可读、执行。DPL=3。
    __USER_DS：内核代码段。范围 0-4G。可读、写。DPL=3。
    TSS(任务状态段)：存储进程的硬件上下文，进程切换时使用。（因为x86硬件对TSS有一定支持，所有有这个特殊的段和相应的专用寄存器。）
    
default_ldt：理论上每个进程都可以同时使用很多段，这些段可以存储在自己的ldt段中，但实际linux极少利用x86的这些功能，多数情况下所有进程共享这个段，它只包含一个空描述符。
    还有一些特殊的段用在电源管理等代码中。
    
（在2.2以前，每个进程的ldt和TSS段都存在GDT中，而GDT最多只能有8192项，因此整个系统的进程总数被限制在4090左右。2。4里不再把它们存在GDT中，从而取消了这个限制。）
    
__USER_CS和__USER_DS段都是被所有在用户态下的进程共享的。注意不要把这个共享和进程空间的共享混淆：虽然大家使用同一个段，但通过使用不同的页表由分页机制保证了进程空间仍然是独立的。

x86的分页机制
    x86硬件支持两级页表，奔腾pro以上的型号还支持Physical address Extension 
Mode和三级页表。所谓的硬件支持包括一些特殊寄存器(cr0-cr4)、以及CPU能够识别页表项中的一些标志位并根据访问情况做出反应等等。如读写Present位为0的页或者写Read/Write位为0的页将引起CPU发出page 
fault异常，访问完页面后自动设置accessed位等。
    
linux采用的是一个体系结构无关的三级页表模型（如图），使用一系列的宏来掩盖各种平台的细节。例如，通过把PMD看作只有一项的表并存储在pgd表项中（通常pgd表项中存放的应该是pmd表的首地址），页表的中间目录(pmd)被巧妙地‘折叠’到页表的全局目录(pgd)，从而适应了二级页表硬件。
TLB
    TLB全称是Translation Look-aside 
Buffer,用来加速页表查找。这里关键的一点是：如果操作系统更改了页表内容，它必须相应的刷新TLB以使CPU不误用过时的表项。

Cache
    Cache 
基本上是对程序员透明的，但是不同的使用方法可以导致大不相同的性能。linux有许多关键的地方对代码做了精心优化，其中很多就是为了减少对cache不必要的污染。如把只有出错情况下用到的代码放到.fixup 
section，把频繁同时使用的数据集中到一个cache行（如struct 
task_struct），减少一些函数的footprint，在slab分配器里头的slab coloring等。
    
另外，我们也必须知道什么时候cache要无效：新map/remap一页到某个地址、页面换出、页保护改变、进程切换等，也即当cache对应的那个地址的内容或含义有所变化时。当然，很多情况下不需要无效整个cache，只需要无效某个地址或地址范围即可。实际上，
    intel在这方面做得非常好用，cache的一致性完全由硬件维护。
    关于x86处理器更多信息，请参照其手册：Volume 3: Architecture and Programming Manual

8． Linux 相关实现
    
这一部分的代码和体系结构紧密相关，因此大多位于arch子目录下，而且大量以宏定义和inline函数形式存在于头文件中。以i386平台为例，主要的文件包括：
page.h
    页大小、页掩码定义。PAGE_SIZE,PAGE_SHIFT和PAGE_MASK。
    对页的操作，如清除页内容clear_page、拷贝页copy_page、页对齐page_align
    还有内核虚地址的起始点：著名的PAGE_OFFSET:)和相关的内核中虚实地址转换的宏__pa和__va.。
    virt_to_page从一个内核虚地址得到该页的描述结构struct page 
*.我们知道，所有物理内存都由一个memmap数组来描述。这个宏就是计算给定地址的物理页在这个数组中的位置。另外这个文件也定义了一个简单的宏检查一个页是不是合法：VALID_PAGE(page)。如果page离memmap数组的开始太远以至于超过了最大物理页面应有的距离则是不合法的。
    比较奇怪的是页表项的定义也放在这里。pgd_t,pmd_t,pte_t和存取它们值的宏xxx_val

pgtable.h pgtable-2level.h pgtable-3level.h
    
顾名思义，这些文件就是处理页表的，它们提供了一系列的宏来操作页表。pgtable-2level.h和pgtable-2level.h则分别对应x86二级、三级页表的需求。首先当然是表示每级页表有多少项的定义不同了。而且在PAE模式下，地址超过32位，页表项pte_t用64位来表示(pmd_t,pgd_t不需要变)，一些对整个页表项的操作也就不同。共有如下几类：
    ·[pte/pmd/pgd]_ERROR 出措时要打印项的取值，64位和32位当然不一样。
    ·set_[pte/pmd/pgd] 设置表项值
    ·pte_same 比较 pte_page 从pte得出所在的memmap位置
    ·pte_none 是否为空。
    ·__mk_pte 构造pte
    
pgtable.h的宏太多，不再一一解释。实际上也比较直观，通常从名字就可以看出宏的意义来了。pte_xxx宏的参数是pte_t,而ptep_xxx的参数是pte_t 
*。2.4 kernel在代码的clean up方面还是作了一些努力，不少地方含糊的名字变明确了，有些函数的可读性页变好了。
    
pgtable.h里除了页表操作的宏外，还有cache和tlb刷新操作，这也比较合理，因为他们常常是在页表操作时使用。这里的tlb操作是以__开始的，也就是说，内部使用的，真正对外接口在pgalloc.h中（这样分开可能是因为在SMP版本中，tlb的刷新函数和单机版本区别较大，有些不再是内嵌函数和宏了）。
pgalloc.h
    包括页表项的分配和释放宏/函数,值得注意的是表项高速缓存的使用：
    pgd/pmd/pte_quicklist
    内核中有许多地方使用类似的技巧来减少对内存分配函数的调用，加速频繁使用的分配。如buffer 
cache中buffer_head和buffer，vm区域中最近使用的区域。
    还有上面提到的tlb刷新的接口
segment.h
    定义 __KERNEL_CS[DS] __USER_CS[DS]
参考：
    《Understanding the Linux Kernel》的第二章给了一个对linux 的相关实现的简要描述，
物理内存的管理。
    2.4中内存管理有很大的变化。在物理页面管理上实现了基于区的伙伴系统（zone based buddy 
system）。区(zone)的是根据内存的不同使用类型划分的。对不同区的内存使用单独的伙伴系统(buddy system)管理,而且独立地监控空闲页等。
    (实际上更高一层还有numa支持。Numa(None Uniformed Memory 
Access)是一种体系结构，其中对系统里的每个处理器来说,不同的内存区域可能有不同的存取时间(一般是由内存和处理器的距离决定)。而一般的机器中内存叫做DRAM，即动态随机存取存储器，对每个单元，CPU用起来是一样快的。NUMA中访问速度相同的一个内存区域称为一个Node，支持这种结构的主要任务就是要尽量减少Node之间的通信，使得每个处理器要用到的数据尽可能放在对它来说最快的Node中。2.4内核中node�相应的数据结构是pg_data_t，每个node拥有自己的memmap数组，把自己的内存分成几个zone，每个zone再用独立的伙伴系统管理物理页面。Numa要对付的问题还有很多，也远没有完善，就不多说了)
基于区的伙伴系统的设计�物理页面的管理
    
内存分配的两大问题是：分配效率、碎片问题。一个好的分配器应该能够快速的满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。伙伴系统是一个常用的比较好的算法。(解释：TODO)
引入区的概念是为了区分内存的不同使用类型（方法？），以便更有效地利用它们。
    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代码交互(分配时根据空闲页面的情况，内核可能从伙伴系统里分配页面，也可能直接把已经分配的页收回�reclaim等)，代码比2.2复杂了不少，要全面地理解它得熟悉整个VM工作的机理。
整个分配器的主要接口是如下函数(mm.h page_alloc.c)：
struct page * alloc_pages(int gfp_mask, unsigned long order) 
根据gftp_mask的要求，从适当的区分配2^order个页面，返回第一个页的描述符。
#define alloc_page(gfp_mask) alloc_pages(gfp_mask,0)
unsigned long __get_free_pages((int gfp_mask, unsigned long order) 
工作同alloc_pages,但返回首地址。
#define __get_free_page(gfp_mask) __get_free_pages(gfp_mask,0)
get_free_page 分配一个已清零的页面。
__free_page(s) 和free_page(s)释放页面（一个/多个）前者以页面描述符为参数，后者以页面地址为参数。
    关于Buddy算法，许多教科书上有详细的描述，第六章对linux的实现有一个很好的介绍。关于zone base buddy更多的信息，可以参见Rik 
Van Riel 写的" design for a zone based memory 
allocator"。这个人是目前linuxmm的维护者，权威啦。这篇文章有一点过时了，98年写的，当时还没有HighMem，但思想还是有效的。还有，下面这篇文章分析2.4的实现代码：
http://home.earthlink.net/~jknapka/linux-mm/zonealloc.html。

Slab--连续物理区域管理
    
单单分配页面的分配器肯定是不能满足要求的。内核中大量使用各种数据结构，大小从几个字节到几十上百k不等，都取整到2的幂次个页面那是完全不现实的。2.0的内核的解决方法是提供大小为2,4,8,16,...,131056字节的内存区域。需要新的内存区域时，内核从伙伴系统申请页面，把它们划分成一个个区域，取一个来满足需求；如果某个页面中的内存区域都释放了，页面就交回到伙伴系统。这样做的效率不高。有许多地方可以改进：
    不同的数据类型用不同的方法分配内存可能提高效率。比如需要初始化的数据结构，释放后可以暂存着，再分配时就不必初始化了。
    内核的函数常常重复地使用同一类型的内存区，缓存最近释放的对象可以加速分配和释放。
    对内存的请求可以按照请求频率来分类，频繁使用的类型使用专门的缓存，很少使用的可以使用类似2.0中的取整到2的幂次的通用缓存。
    使用2的幂次大小的内存区域时高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少高速缓存冲突。
    缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的高速缓存污染。
2.2实现的slab分配器体现了这些改进思想。
主要数据结构
接口：
kmem_cache_create/kmem_cache_destory
kmem_cache_grow/kmem_cache_reap 增长/缩减某类缓存的大小
kmem_cache_alloc/kmem_cache_free 从某类缓存分配/释放一个对象
kmalloc/kfree 通用缓存的分配、释放函数。
相关代码(slab.c)。
相关参考：
http://www.lisoleg.net/lisoleg/memory/slab.pdf ：Slab发明者的论文，必读经典。
第六章，具体实现的详细清晰的描述。
AKA2000年的讲座也有一些大虾讲过这个主题，请访问aka主页：www.aka.org.cn

vmalloc/vfree �物理地址不连续，虚地址连续的内存管理
    使用kernel页表。文件vmalloc.c，相对简单。

2.4内核的VM(完善中。。。)