| 内存 |
虚拟内存可以提供以下的功能：
*广阔的地址空间。
系统的虚拟内存可以比系统的实际内存大很多倍。
*进程的保护。
系统中的每一个进程都有自己的虚拟地址空间。这些虚拟地址空间是完全分开的，这样一个进程的运行不会影响其他进程。并且，硬件上的虚拟内存机制是被保护的，内存不能被写入，这样可以防止迷失的应用程序覆盖代码的数据。
*内存映射。
内存映射用来把文件映射到进程的地址空间。在内存映射中，文件的内容直接连接到进程的虚拟地址空间。
*公平的物理内存分配。
内存管理系统允许系统中每一个运行的进程都可以公平地得到系统的物理内存。
*共享虚拟内存。
虽然虚拟内存允许进程拥有自己单独的虚拟地址空间，但有时可能会希望进程共享内存。
linux仅仅使用四个段
两个代表 (code 和 data/stack)是内核空间从[0xC000 0000] (3 GB)到[0xFFFF FFFF] (4 GB)
两个代表 (code 和 data/stack)是用户空间从[0] (0 GB) 到 [0xBFFF FFFF] (3 GB)
__
4 GB--->| | |
| Kernel | | 内核空间 (Code + Data/Stack)
| | __|
3 GB--->|----------------| __
| | |
| | |
2 GB--->| | |
| Tasks | | 用户空间 (Code + Data/Stack)
| | |
1 GB--->| | |
| | |
|________________| __|
0x00000000
内核/用户 线性地址
linux可以使用3层页表映射，例如在高级的I64服务器上，但是i386体系结构下只有2层有实际意义:
------------------------------------------------------------------
线性地址
------------------------------------------------------------------
\___/ \___/ \_____/
PD 偏移 PF 偏移 Frame 偏移
[10 bits] [10 bits] [12 bits]
| | |
| | ----------- |
| | | Value |----------|---------
| | | | |---------| /|\ | |
| | | | | | | | |
| | | | | | | Frame 偏移 |
| | | | | | \|/ |
| | | | |---------|<------ |
| | | | | | | |
| | | | | | | x 4096 |
| | | PF 偏移 |_________|------- |
| | | /|\ | | |
PD 偏移 |_________|----- | | | _________|
/|\ | | | | | | |
| | | | \|/ | | \|/
_____ | | | ------>|_________| 物理地址
| | \|/ | | x 4096 | |
| CR3 |-------->| | | |
|_____| | ....... | | ....... |
| | | |
页目录表 页表
Linux i386 分页
注意内核(仅仅内核)线性空间就等于内核物理空间，所以如下:
________________ _____
| 其他内核数据 |___ | | |
|----------------| | |__| |
| 内核 |\ |____| 实际的其他 |
3 GB --->|----------------| \ | 内核数据 |
| |\ \ | |
| __|_\_\____|__ Real |
| Tasks | \ \ | Tasks |
| __|___\_\__|__ Space |
| | \ \ | |
| | \ \|----------------|
| | \ | 实际内核空间 |
|________________| \|________________|
逻辑地址 物理地址
[内存实时分配]
|copy_mm
|allocate_mm = kmem_cache_alloc
|__kmem_cache_alloc
|kmem_cache_alloc_one
|alloc_new_slab
|kmem_cache_grow
|kmem_getpages
|__get_free_pages
|alloc_pages
|alloc_pages_pgdat
|__alloc_pages
|rmqueue
|reclaim_pages
·copy_mm [kernel/fork.c]
·allocate_mm [kernel/fork.c]
·kmem_cache_alloc [mm/slab.c]
·__kmem_cache_alloc
·kmem_cache_alloc_one
·alloc_new_slab
·kmem_cache_grow
·kmem_getpages
·__get_free_pages [mm/page_alloc.c]
·alloc_pages [mm/numa.c]
·alloc_pages_pgdat
·__alloc_pages [mm/page_alloc.c]
·rm_queue
·reclaim_pages [mm/vmscan.c]
[内存交换线程kswapd]
|kswapd
|// initialization routines
|for (;;) { // Main loop
|do_try_to_free_pages
|recalculate_vm_stats
|refill_inactive_scan
|run_task_queue
|interruptible_sleep_on_timeout // we sleep for a new swap request
|}
·kswapd [mm/vmscan.c]
·do_try_to_free_pages
·recalculate_vm_stats [mm/swap.c]
·refill_inactive_scan [mm/vmswap.c]
·run_task_queue [kernel/softirq.c]
·interruptible_sleep_on_timeout [kernel/sched.c]
[内存交换机制：出现内存不足的Exception]
| Page Fault Exception
| cause by all these conditions:
| a-) User page
| b-) Read or write access
| c-) Page not present
|
|
-----------> |do_page_fault
|handle_mm_fault
|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]
存储层次结构和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(完善中。。。)
进程地址空间管理
创建，销毁。
mm_struct, vm_area_struct, mmap/mprotect/munmap
page fault处理，demand page, copy on write
相关文件：
include/linux/mm.h：struct page结构的定义，page的标志位定义以及存取操作宏定义。struct vm_area_struct定义。mm子系统的函数原型说明。
include/linux/mman.h:和vm_area_struct的操作mmap/mprotect/munmap相关的常量宏定义。
memory.c：page fault处理，包括COW和demand page等。
对一个区域的页表相关操作:
zeromap_page_range: 把一个范围内的页全部映射到zero_page
remap_page_range：给定范围的页重新映射到另一块地址空间。
zap_page_range：把给定范围内的用户页释放掉，页表清零。
mlock.c： mlock/munlock系统调用。mlock把页面锁定在物理内存中。
mmap.c:：mmap/munmap/brk系统调用。
mprotect.c： mprotect系统调用。
前面三个文件都大量涉及vm_area_struct的操作，有很多相似的xxx_fixup的代码，它们的任务是修补受到影响的区域，保证vm_area_struct 链表正确。
交换
目的：
使得进程可以使用更大的地址空间。同时容纳更多的进程。
任务：
选择要换出的页
决定怎样在交换区中存储页面
决定什么时候换出
kswapd内核线程：每10秒激活一次
任务：当空闲页面低于一定值时，从进程的地址空间、各类cache回收页面
为什么不能等到内存分配失败再用try_to_free_pages回收页面？原因：
有些内存分配时在中断或异常处理调用，他们不能阻塞
有时候分配发生在某个关键路径已经获得了一些关键资源的时候，因此它不能启动IO。如果不巧这时所有的路径上的内存分配都是这样，内存就无法释放。
kreclaimd 从inactive_clean_list回收页面，由__alloc_pages唤醒。
相关文件：
mm/swap.c kswapd使用的各种参数以及操作页面年龄的函数。
mm/swap_file.c 交换分区/文件的操作。
mm/page_io.c 读或写一个交换页。
mm/swap_state.c swap cache相关操作,加入/删除/查找一个swap cache等。
mm/vmscan.c 扫描进程的vm_area，试图换出一些页面（kswapd）。
reclaim_page：从inactive_clean_list回收一个页面，放到free_list
kclaimd被唤醒后重复调用reclaim_page直到每个区的
zone->free_pages>= zone->pages_low
page_lauder：由__alloc_pages和try_to_free_pages等调用。通常是由于freepages + inactive_clean_list的页太少了。功能：把inactive_dirty_list的页面转移到inactive_clean_list，首先把已经被写回文件或者交换区的页面(by bdflush)放到inactive_clean_list，如果freepages确实短缺，唤醒bdflush，再循环一遍把一定数量的dirty页写回。
关于这几个队列(active_list,inactive_dirty_list,inactive_clean_list)的逻辑，请参照：文档：RFC: design for new VM，可以从lisoleg的文档精华获得。
page cache、buffer cache和swap cache
page cache：读写文件时文件内容的cache，大小为一个页。不一定在磁盘上连续。
buffer cache：读写磁盘块的时候磁盘块内容的cache，buffer cache的内容对应磁盘上一个连续的区域，一个buffer cache大小可能从512(扇区大小)到一个页。
swap cache： 是page cache的子集。用于多个进程共享的页面被换出到交换区的情况。
page cache 和 buffer cache的关系
本质上是很不同的，buffer cache缓冲磁盘块内容，page cache缓冲文件的一页内容。page cache写回时会使用临时的buffer cache来写磁盘。
bdflush： 把dirty的buffer cache写回磁盘。通常只当dirty的buffer太多或者需要更多的buffer而内存开始不足时运行。page_lauder也可能唤醒它。
kupdate： 定时运行，把写回期限已经到了的dirty buffer写回磁盘。
2.4的改进：page cache和buffer cache耦合得更好了。在2.2里，磁盘文件的读使用page cache，而写绕过page cache，直接使用buffer cache，因此带来了同步的问题：写完之后必须使用update_vm_cache()更新可能有的page cache。2.4中page cache做了比较大的改进，文件可以通过page cache直接写了，page cache优先使用high memory。而且，2.4引入了新的对象：file address space，它包含用来读写一整页数据的方法。这些方法考虑到了inode的更新、page cache处理和临时buffer的使用。page cache和buffer cache的同步问题就消除了。原来使用inode+offset查找page cache变成通过file address space+offset；原来struct page 中的inode成员被address_space类型的mapping成员取代。这个改进还使得匿名内存的共享成为可能（这个在2.2很难实现，许多讨论过）。
虚存系统则从freeBSD借鉴了很多经验，针对2.2的问题作了巨大的调整。
文档：RFC: design for new VM不可不读。
由于时间仓促，新vm的很多细微之处我也还没来得及搞清楚。先大致罗列一下，以后我将进一步完善本文，争取把问题说清楚。另外，等这学期考试过后，我希望能为大家提供一些详细注释过的源代码。
一、Linux内存管理概述
这里说一下我的理解，主要从数据结构说。
1、物理内存都是按顺序分成一页一页的，每页用一个page结构来描述。系统所有的物理页 面的page结
构描述就组成了一个数组mem_map。
2、进程的虚拟地址空间用task_struct的域mm来描述,它是一个mm_struct结构，这个结构包包含了指向?
程页目录的指针（pgd_t * pgd）和指向进程虚拟内存区域的指针（struct vm_area_structt * mmap）
3、进程虚拟内存区域具有相同属性的段用结构vm_area_struct描述（简称为VMA）。进程所所有的VMA?
树组织。
4、每个VMA就是一个对象，定义了一组操作，可以通过这组操作来对不同类型的VMA进行不屯 的处理。
例如对vmalloc分配的内存的映射就是通过其中的nopage操作实现的。
二、mmap处理过程
当用户调用mmap的时候，内核进行如下的处理：
1、先在进程的虚拟空间查找一块VMA；
2、将这块VMA去映射
3、如果设备驱动程序或者文件系统的file_operations定义了mmap操作，则调用它
4、将这个VMA插入到进程的VMA链中
file_operations的中定义的mmap方法原型如下：
int (*mmap) (struct file *, struct vm_area_struct *);
其中file是虚拟空间映射到的文件结构，vm_area_struct就是步骤1中找到的VMA。
三、缺页故障处理过程
当访问一个无效的虚拟地址（可能是保护故障，也可能缺页故障等）的时候，就会产生一个个页故障，?
统的处理过程如下：
1、找到这个虚拟地址所在的VMA；
2、如果必要，分配中间页目录表和页表
3、如果页表项对应的物理页面不存在，则调用这个VMA的nopage方法，它返回物理页面的paage描述结构
（当然这只是其中的一种情况）
4、针对上面的情况，将物理页面的地址填充到页表中
当页故障处理完后，系统将重新启动引起故障的指令，然后就可以正常访问了
下面是VMA的方法：
struct vm_operations_struct {
void (*open)(struct vm_area_struct * area);
void (*close)(struct vm_area_struct * area);
struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, innt
write_access);
};
其中缺页函数nopage的address是引起缺页故障的虚拟地址，area是它所在的VMA，write_acccess是存取
属性。
三、具体实现
3.1、对kmalloc分配的内存的映射
对kmalloc分配的内存，因为是一段连续的物理内存，所以它可以简单的在mmap例程中设置汉 页表的物
理地址，方法是使用函数remap_page_range。它的原型如下：
int remap_page_range(unsigned long from, unsigned long phys_addr, unsigned long size,
pgprot_t prot)
其中from是映射开始的虚拟地址。这个函数为虚拟地址空间from和from+size之间的范围构栽 页表；
phys_addr是虚拟地址应该映射到的物理地址；size是被映射区域的大小；prot是保护标志?
remap_page_range的处理过程是对from到form+size之间的每一个页面，查找它所在的页目侣己 页表（
必要时建立页表），清除页表项旧的内容，重新填写它的物理地址与保护域。
remap_page_range可以对多个连续的物理页面进行处理。<<Linux设备驱动程序>>指出，
remap_page_range只能给予对保留的页和物理内存之上的物理地址的访问，当对非保留的页页使?
remap_page_range时，缺省的nopage处理控制映射被访问的虚地址处的零页。所以在分配内内存后，就?
对所分配的内存置保留位，它是通过函数mem_map_reserve实现的，它就是对相应物理页面?
PG_reserved标志位。（关于这一点，参见前面的主题为“关于remap_page_range的疑问”档奶致郏?
因为remap_page_range有上面的限制，所以可以用另外一种方式，就是采用和vmalloc分配档哪 存同样
的方法，对缺页故障进行处理。
3.2、对vmalloc分配的内存的映射
3.2.1、vmalloc分配内存的过程
（1）、进行预处理和合法性检查，例如将分配长度进行页面对齐，检查分配长度是否过大?
（2）、以GFP_KERNEL为优先级调用kmalloc分配（GFP_KERNEL用在进程上下文中，所以这里里就限制了?
中断处理程序中调用vmalloc）描述vmalloc分配的内存的vm_struct结构。
（3）、将size加一个页面的长度，使中间形成4K的隔离带，然后在VMALLOC_START和VMALLOOC_END之间
编历vmlist链表，寻找一段自由内存区间，将其地址填入vm_struct结构中
（4）、返回这个地址
vmalloc分配的物理内存并不连续
3.2.2、页目录与页表的定义
typedef struct { unsigned long pte_low; } pte_t;
typedef struct { unsigned long pmd; } pmd_t;
typedef struct { unsigned long pgd; } pgd_t;
#define pte_val(x) ((x).pte_low)
3.2.3、常见例程：
（1）、virt_to_phys()：内核虚拟地址转化为物理地址
#define __pa(x) ((unsigned long)(x)-PAGE_OFFSET)
extern inline unsigned long virt_to_phys(volatile void * address)
{
return __pa(address);
}
上面转换过程是将虚拟地址减去3G（PAGE_OFFSET=0XC000000）,因为内核空间从3G到3G＋实实际内存一?
映射到物理地址的0到实际内存
（2）、phys_to_virt()：内核物理地址转化为虚拟地址
#define __va(x) ((void *)((unsigned long)(x)+PAGE_OFFSET))
extern inline void * phys_to_virt(unsigned long address)
{
return __va(address);
}
virt_to_phys()和phys_to_virt()都定义在include\asm-i386\io.h中
（3）、#define virt_to_page(kaddr) (mem_map + (__pa(kaddr) >> PAGE_SHIFT))（内核核2.4?
#define VALID_PAGE(page) ((page - mem_map) < max_mapnr)（内核2.4）
第一个宏根据虚拟地址，将其转换为相应的物理页面的page描述结构，第二个宏判断页面是是不是在有?
的物理页面内。（这两个宏处理的虚拟地址必须是内核虚拟地址，例如kmalloc返回的地址＃杂?
vmalloc返回的地址并不能这样，因为vmalloc分配的并不是连续的物理内存，中间可能有空空洞?
3.2.4、vmalloc分配的内存的mmap的实现：
对vmalloc分配的内存需要通过设置相应VMA的nopage方法来实现，当产生缺页故障的时候，，会调用VM
的nopage方法，我们的目的就是在nopage方法中返回一个page结构的指针，为此，需要通过过如下步骤?
（1） pgd_offset_k或者 pgd_offset：查找虚拟地址所在的页目录表，前者对应内核空间档男 拟地址
，后者对应用户空间的虚拟地址
#define pgd_offset(mm, address) ((mm)->pgd+pgd_index(address))
#define pgd_offset_k(address) pgd_offset(&init_mm, address)
对于后者，init_mm是进程0（idle process）的虚拟内存mm_struct结构，所有进程的内核 页表都一样
。在vmalloc分配内存的时候，要刷新内核页目录表，2.4中为了节省开销，只更改了进程0档哪 核页目
录，而对其它进程则通过访问时产生页面异常来进行更新各自的内核页目录
（2）pmd_offset：找到虚拟地址所在的中间页目录项。在查找之前应该使用pgd_none判断适 否存在相
应的页目录项，这些函数如下：
extern inline int pgd_none(pgd_t pgd) { return 0; }
extern inline pmd_t * pmd_offset(pgd_t * dir, unsigned long address)
{
return (pmd_t *) dir;
}
（3）pte_offset：找到虚拟地址对应的页表项。同样应该使用pmd_none判断是否存在相应档 中间页目
录：
#define pmd_val(x) ((x).pmd)
#define pmd_none(x) (!pmd_val(x))
#define __pte_offset(address) \
((address >> PAGE_SHIFT) & (PTRS_PER_PTE - 1))
#define pmd_page(pmd) \
((unsigned long) __va(pmd_val(pmd) & PAGE_MASK))
#define pte_offset(dir, address) ((pte_t *) pmd_page(*(dir)) + \
__pte_offset(address))
（4）pte_present和pte_page：前者判断页表对应的物理地址是否有效，后者取出页表中物物理地址对?
的page描述结构
#define pte_present(x) ((x).pte_low & (_PAGE_PRESENT | _PAGE_PROTNONE))
#define pte_page(x) (mem_map+((unsigned long)(((x).pte_low >> PAGE_SHIFT))))
#define page_address(page) ((page)->virtual)
下面的一个DEMO与上面的关系不大，它是做这样一件事情，就是在启动的时候保留一段内存存，然后使?
ioremap将它映射到内核虚拟空间，同时又用remap_page_range映射到用户虚拟空间，这样亮 边都能访
问，通过内核虚拟地址将这段内存初始化串"abcd"，然后使用用户虚拟地址读出来。
/************mmap_ioremap.c**************/
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/mm.h>
#include <linux/wrapper.h> /* for mem_map_(un)reserve */
#include <asm/io.h> /* for virt_to_phys */
#include <linux/slab.h> /* for kmalloc and kfree */
MODULE_PARM(mem_start,"i");
MODULE_PARM(mem_size,"i");
static int mem_start=101,mem_size=10;
static char * reserve_virt_addr;
static int major;
int mmapdrv_open(struct inode *inode, struct file *file);
int mmapdrv_release(struct inode *inode, struct file *file);
int mmapdrv_mmap(struct file *file, struct vm_area_struct *vma);
static struct file_operations mmapdrv_fops =
{
owner: THIS_MODULE,
mmap: mmapdrv_mmap,
open: mmapdrv_open,
release: mmapdrv_release,
};
int init_module(void)
{
if ( ( major = register_chrdev(0, "mmapdrv", &mmapdrv_fops) ) < 0 )
{
printk("mmapdrv: unable to register character device\n");
return (-EIO);
}
printk("mmap device major = %d\n",major );
printk( "high memory physical address 0x%ldM\n",
virt_to_phys(high_memory)/1024/1024 );
reserve_virt_addr = ioremap( mem_start*1024*1024,mem_size*1024*1024);
printk( "reserve_virt_addr = 0x%lx\n", (unsigned long)reserve_virt_addr );
if ( reserve_virt_addr )
{
int i;
for ( i=0;i<mem_size*1024*1024;i+=4)
{
reserve_virt_addr[i] = 'a';
reserve_virt_addr[i+1] = 'b';
reserve_virt_addr[i+2] = 'c';
reserve_virt_addr[i+3] = 'd';
}
}
else
{
unregister_chrdev( major, "mmapdrv" );
return -ENODEV;
}
return 0;
}
/* remove the module */
void cleanup_module(void)
{
if ( reserve_virt_addr )
iounmap( reserve_virt_addr );
unregister_chrdev( major, "mmapdrv" );
return;
}
int mmapdrv_open(struct inode *inode, struct file *file)
{
MOD_INC_USE_COUNT;
return(0);
}
int mmapdrv_release(struct inode *inode, struct file *file)
{
MOD_DEC_USE_COUNT;
return(0);
}
int mmapdrv_mmap(struct file *file, struct vm_area_struct *vma)
{
unsigned long offset = vma->vm_pgoff<<PAGE_SHIFT;
unsigned long size = vma->vm_end - vma->vm_start;
if ( size > mem_size*1024*1024 )
{
printk("size too big\n");
return(-ENXIO);
}
offset = offset + mem_start*1024*1024;
/* we do not want to have this area swapped out, lock it */
vma->vm_flags |= VM_LOCKED;
if ( remap_page_range(vma->vm_start,offset,size,PAGE_SHARED))
{
printk("remap page range failed\n");
return -ENXIO;
}
return(0);
}
使用LDD2源码里面自带的工具mapper测试结果如下：
[root@localhost modprg]# insmod mmap_ioremap.mod
mmap device major = 254
high memory physical address 0x100M
reserve_virt_addr = 0xc7038000
[root@localhost modprg]# mknod mmapdrv c 254 0
[root@localhost modprg]# ./mapper mmapdrv 0 1024 | od -Ax -t x1
mapped "mmapdrv" from 0 to 1024
000000 61 62 63 64 61 62 63 64 61 62 63 64 61 62 63 64
*
000400
[root@localhost modprg]#
内核页目录的初始化
/* swapper_pg_dir is the main page directory, address 0x00101000*/
>>> 内核页目录，第0，1项和第768、767项均为映射到物理内存0-8M的页目录项
>>> 其页表的物理地址是0x00102000和0x00103000，即下面的pg0和pg1所在的位置
>>> （在启动的时候，将内核映像移到0x0010000处）。
>>> 之所以第0，1项与第768和767相同，是因为在开启分页前的线性地址0-8M和开启
>>> 分页之后的3G-3G+8M均映射到相同的物理地址0-8M
/*
* This is initialized to create an identity-mapping at 0-8M (for bootup
* purposes) and another mapping of the 0-8M area at virtual address
* PAGE_OFFSET.
*/
.org 0x1000
ENTRY(swapper_pg_dir)
.long 0x00102007
.long 0x00103007
.fill BOOT_USER_PGD_PTRS-2,4,0
/* default: 766 entries */
.long 0x00102007
.long 0x00103007
/* default: 254 entries */
.fill BOOT_KERNEL_PGD_PTRS-2,4,0
/*
* The page tables are initialized to only 8MB here - the final page
* tables are set up later depending on memory size.
*/
>>> 下面为物理地址0-8M的页表项
>>> 从0x4000到0x2000共2k个页表项，映射0-8M的物理内存
.org 0x2000
ENTRY(pg0)
.org 0x3000
ENTRY(pg1)
/*
* empty_zero_page must immediately follow the page tables ! (The
* initialization loop counts until empty_zero_page)
*/
.org 0x4000
ENTRY(empty_zero_page)
>>> 进程0的页目录指向swapper_pg_dir
#define INIT_MM(name) \
{ \
mmap: &init_mmap, \
mmap_avl: NULL, \
mmap_cache: NULL, \
pgd: swapper_pg_dir, \
mm_users: ATOMIC_INIT(2), \
mm_count: ATOMIC_INIT(1), \
map_count: 1, \
mmap_sem: __RWSEM_INITIALIZER(name.mmap_sem), \
page_table_lock: SPIN_LOCK_UNLOCKED, \
mmlist: LIST_HEAD_INIT(name.mmlist), \
}
/*
* paging_init() sets up the page tables - note that the first 8MB are
* already mapped by head.S.
*
* This routines also unmaps the page at virtual kernel address 0, so
* that we can trap those pesky NULL-reference errors in the kernel.
*/
void __init paging_init(void)
{
pagetable_init();
__asm__( "movl %%ecx,%%cr3\n" ::"c"(__pa(swapper_pg_dir)));
。。。。。。。。。。。
}
static void __init pagetable_init (void)
{
unsigned long vaddr, end;
pgd_t *pgd, *pgd_base;
int i, j, k;
pmd_t *pmd;
pte_t *pte, *pte_base;
>>> end虚拟空间的最大值（最大物理内存＋3G）
/*
* This can be zero as well - no problem, in that case we exit
* the loops anyway due to the PTRS_PER_* conditions.
*/
end = (unsigned long)__va(max_low_pfn*PAGE_SIZE);
pgd_base = swapper_pg_dir;
#if CONFIG_X86_PAE
for (i = 0; i < PTRS_PER_PGD; i++)
set_pgd(pgd_base + i, __pgd(1 + __pa(empty_zero_page)));
#endif
>>> 内核起始虚拟空间在内核页目录表中的索引
i = __pgd_offset(PAGE_OFFSET);
pgd = pgd_base + i;
>>> #define PTRS_PER_PGD 1024
>>> 对页目录的从768项开始的每一项
for (; i < PTRS_PER_PGD; pgd++, i++) {
>>> vaddr为第i项页目录项所映射的内核空间的起始虚拟地址，PGDIR_SIZE=4M
vaddr = i*PGDIR_SIZE;
if (end && (vaddr >= end))
break;
#if CONFIG_X86_PAE
pmd = (pmd_t *) alloc_bootmem_low_pages(PAGE_SIZE);
set_pgd(pgd, __pgd(__pa(pmd) + 0x1));
#else
>>> 对两级映射机制，pmd实际上是pgd
pmd = (pmd_t *)pgd;
#endif
if (pmd != pmd_offset(pgd, 0))
BUG();
for (j = 0; j < PTRS_PER_PMD; pmd++, j++) {
vaddr = i*PGDIR_SIZE + j*PMD_SIZE;
if (end && (vaddr >= end))
break;
>>> 假如内核不支持 Page Size Extensions
if (cpu_has_pse) {
。。。。。。。。。。
}
>>> 分配内核页表
pte_base = pte = (pte_t *) alloc_bootmem_low_pages(PAGE_SIZE);
>>> 对每一项页表项
for (k = 0; k < PTRS_PER_PTE; pte++, k++) {
vaddr = i*PGDIR_SIZE + j*PMD_SIZE + k*PAGE_SIZE;
if (end && (vaddr >= end))
break;
>>> 将页面的物理地址填入页表项中
*pte = mk_pte_phys(__pa(vaddr), PAGE_KERNEL);
}
>>> 将页表的物理地址填入到页目录项中
set_pmd(pmd, __pmd(_KERNPG_TABLE + __pa(pte_base)));
if (pte_base != pte_offset(pmd, 0))
BUG();
}
}
/*
* Fixed mappings, only the page table structure has to be
* created - mappings will be set by set_fixmap():
*/
vaddr = __fix_to_virt(__end_of_fixed_addresses - 1) & PMD_MASK;
fixrange_init(vaddr, 0, pgd_base);
#if CONFIG_HIGHMEM
。。。。。。。。。。。。
#endif
#if CONFIG_X86_PAE
。。。。。。。。。。。。
#endif
}
>>> kernel_thread以标志CLONE_VM调用clone系统调用
/*
* Create a kernel thread
*/
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
long retval, d0;
__asm__ __volatile__(
"movl %%esp,%%esi\n\t"
"int $0x80\n\t" /* Linux/i386 system call */
"cmpl %%esp,%%esi\n\t" /* child or parent? */
/* Load the argument into eax, and push it. That way, it does
* not matter whether the called function is compiled with
* -mregparm or not. */
"movl %4,%%eax\n\t"
"pushl %%eax\n\t"
"call *%5\n\t" /* call fn */
"movl %3,%0\n\t" /* exit */
"int $0x80\n"
"1:\t"
:"=&a" (retval), "=&S" (d0)
:"0" (__NR_clone), "i" (__NR_exit),
"r" (arg), "r" (fn),
"b" (flags | CLONE_VM)
: "memory");
return retval;
}
>>> sys_clone->do_fork->copy_mm：
static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
{
struct mm_struct * mm, *oldmm;
int retval;
。。。。。。。。
tsk->mm = NULL;
tsk->active_mm = NULL;
/*
* Are we cloning a kernel thread?
*
* We need to steal a active VM for that..
*/
>>> 如果是内核线程的子线程（mm=NULL），则直接退出，此时内核线程mm和active_mm均为为NULL
oldmm = current->mm;
if (!oldmm)
return 0;
>>> 内核线程，只是增加当前进程的虚拟空间的引用计数
if (clone_flags & CLONE_VM) {
atomic_inc(&oldmm->mm_users);
mm = oldmm;
goto good_mm;
}
。。。。。。。。。。
good_mm:
>>> 内核线程的mm和active_mm指向当前进程的mm_struct结构
tsk->mm = mm;
tsk->active_mm = mm;
return 0;
。。。。。。。
}
然后内核线程一般调用daemonize来释放对用户空间的引用：
>>> daemonize->exit_mm->_exit_mm：
/*
* Turn us into a lazy TLB process if we
* aren't already..
*/
static inline void __exit_mm(struct task_struct * tsk)
{
struct mm_struct * mm = tsk->mm;
mm_release();
if (mm) {
atomic_inc(&mm->mm_count);
if (mm != tsk->active_mm) BUG();
/* more a memory barrier than a real lock */
task_lock(tsk);
>>> 释放用户虚拟空间的数据结构
tsk->mm = NULL;
task_unlock(tsk);
enter_lazy_tlb(mm, current, smp_processor_id());
>>> 递减mm的引用计数并是否为0，是则释放mm所代表的映射
mmput(mm);
}
}
asmlinkage void schedule(void)
{
。。。。。。。。。
if (!current->active_mm) BUG();
。。。。。。。。。
prepare_to_switch();
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
>>> mm = NULL，选中的为内核线程
if (!mm) {
>>> 对内核线程,active_mm = NULL，否则一定是出错了
if (next->active_mm) BUG();
>>> 选中的内核线程active_mm借用老进程的active_mm
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next, this_cpu);
} else {
>>> mm != NULL 选中的为用户进程，active_mm必须与mm相等，否则一定是出错了
if (next->active_mm != mm) BUG();
switch_mm(oldmm, mm, next, this_cpu);
}
>>> prev = NULL ，切换出去的是内核线程
if (!prev->mm) {
>>> 设置其 active_mm = NULL 。
prev->active_mm = NULL;
mmdrop(oldmm);
}
}
}
对内核线程的虚拟空间总结一下：
１、创建的时候：
父进程是用户进程，则mm和active_mm均共享父进程的，然后内核线程一般调用daemonize适头舖m
父进程是内核线程，则mm和active_mm均为NULL
总之，内核线程的mm = NULL；进程调度的时候以此为依据判断是用户进程还是内核线程。
２、进程调度的时候
如果切换进来的是内核线程，则置active_mm为切换出去的进程的active_mm；
如果切换出去的是内核线程，则置active_mm为NULL。
在fork一个进程的时候，必须建立进程自己的内核页目录项（内核页目录项要
与用户空间的的页目录放在同一个物理地址连续的页面上，所以不能共享，但
所有进程的内核页表与进程0共享?
3G用户，页目录中一项映射4M的空间（一项页目录1024项页表，每项页表对应1个页面4K）＃ 即：
#define PGDIR_SHIFT 22
#define PGDIR_SIZE (1UL << PGDIR_SHIFT)
>>> sys_fork->do_fork->copy_mm->mm_init->pgd_alloc->get_pgd_slow
#if CONFIG_X86_PAE
。。。。。。。。。。。。。
#else
extern __inline__ pgd_t *get_pgd_slow(void)
{
>>> 分配页目录表（包含1024项页目录），即为一个进程分配的页目录可以映射的空间为10024*4M=4G
pgd_t *pgd = (pgd_t *)__get_free_page(GFP_KERNEL);
if (pgd) {
>>> #define USER_PTRS_PER_PGD (TASK_SIZE/PGDIR_SIZE)
>>> TASK_SIZE为3G大小，USER_PTRS_PER_PGD为用户空间对应的页目录项数目（3G/4M=768?
>>> 将用户空间的页目录项清空
memset(pgd, 0, USER_PTRS_PER_PGD * sizeof(pgd_t));
>>> 将内核页目录表（swapper_pg_dir）的第768项到1023项拷贝到进程的页目录表的第7688项到1023项中
memcpy(pgd + USER_PTRS_PER_PGD, swapper_pg_dir + USER_PTRS_PER_PGD, (PTRS_PER__PGD - USER_PTRS_PER_PGD) * sizeof(pgd_t));
}
return pgd;
}
#endif
当一个进程在内核空间发生缺页故障的时候，在其处理程序中，就要通过0号进程的页目录览 同步本进程的内核页目录，实际上就是拷贝0号进程的内核页目录到本进程中（内核页表与进程0共享，故不需要复制）。如下：
asmlinkage void do_page_fault(struct pt_regs *regs, unsigned long error_code)
{
。。。。。。。。
>>> 缺页故障产生的地址
/* get the address */
__asm__("movl %%cr2,%0":"=r" (address));
tsk = current;
/*
* We fault-in kernel-space virtual memory on-demand. The
* 'reference' page table is init_mm.pgd.
*/
>>> 如果缺页故障在内核空间
if (address >= TASK_SIZE)
goto vmalloc_fault;
。。。。。。。。。
vmalloc_fault:
{
/*
* Synchronize this task's top level page-table
* with the 'reference' page table.
*/
int offset = __pgd_offset(address);
pgd_t *pgd, *pgd_k;
pmd_t *pmd, *pmd_k;
pgd = tsk->active_mm->pgd + offset;
pgd_k = init_mm.pgd + offset;
>>> /*
>>> * (pmds are folded into pgds so this doesnt get actually called,
>>> * but the define is needed for a generic inline function.)
>>> */
>>> #define set_pmd(pmdptr, pmdval) (*(pmdptr) = pmdval)
>>> #define set_pgd(pgdptr, pgdval) (*(pgdptr) = pgdval)
>>> 如果本进程的该地址的内核页目录不存在
if (!pgd_present(*pgd)) {
>>> 如果进程0的该地址处的内核页目录也不存在，则出错
if (!pgd_present(*pgd_k))
goto bad_area_nosemaphore;
>>> 复制进程0的该地址的内核页目录到本进程的相应页目录中
set_pgd(pgd, *pgd_k);
return;
}
>>> extern inline pmd_t * pmd_offset(pgd_t * dir, unsigned long address)
>>> {
>>> return (pmd_t *) dir;
>>> }
pmd = pmd_offset(pgd, address);
pmd_k = pmd_offset(pgd_k, address);
>>> 对中间页目录，如果是两级页表，下面的几步操作与上面的重复
if (pmd_present(*pmd) || !pmd_present(*pmd_k))
goto bad_area_nosemaphore;
set_pmd(pmd, *pmd_k);
return;
}
/*
* Switch to real mode and then execute the code
* specified by the code and length parameters.
* We assume that length will aways be less that 100!
*/
void machine_real_restart(unsigned char *code, int length)
{
。。。。。。。。。。。。。
/* Remap the kernel at virtual address zero, as well as offset zero
from the kernel segment. This assumes the kernel segment starts at
virtual address PAGE_OFFSET. */
memcpy (swapper_pg_dir, swapper_pg_dir + USER_PGD_PTRS,
sizeof (swapper_pg_dir [0]) * KERNEL_PGD_PTRS);
/* Make sure the first page is mapped to the start of physical memory.
It is normally not mapped, to trap kernel NULL pointer dereferences. */
pg0[0] = _PAGE_RW | _PAGE_PRESENT;
/*
* Use `swapper_pg_dir' as our page directory.
*/
asm volatile("movl %0,%%cr3": :"r" (__pa(swapper_pg_dir)));
由mlock的参数可看出，mlock对由start所在页的起始地址开始，长度为len(注：len=(len+(start&~PAGE_MASK)+ ~PAGE_MASK)&PAGE_MASK)的内存区域的页进行加锁。
sys_mlock如果调用成功返回，这其中所有的包含具体内存区域的页必须是常驻内存的，或者说在调用munlock 或 munlockall之前这部分被锁住的页面必须保留在内存。当然，如果调用mlock的进程终止或者调用exec执行其他程序，则这部分被锁住的页面被释放。通过fork()调用所创建的子进程不能够继承由父进程调用mlock锁住的页面。
内存屏蔽主要有两个方面的应用：实时算法和高度机密数据的处理。实时应用要求严格的分时，比如调度，调度页面是程序执行延时的一个主要因素。保密安全软件经常处理关键字节，比如密码或者密钥等数据结构。页面调度的结果是有可能将这些重要字节写到外存（如硬盘）中去。这样一些黑客就有可能在这些安全软件删除这些在内存中的数据后还能访问部分在硬盘中的数据。 而对内存进行加锁完全可以解决上述难题。
内存加锁不使用压栈技术，即那些通过调用mlock或者mlockall被锁住多次的页面可以通过调用一次munlock或者munlockall释放相应的页面
mlock的返回值分析：若调用mlock成功，则返回０；若不成功，则返回-1，并且errno被置位，进程的地址空间保持原来的状态。返回错误代码分析如下：
ENOMEM：部分具体地址区域没有相应的进程地址空间与之对应或者超出了进程所允许的最大可锁页面。
EPERM：调用mlock的进程没有正确的优先权。只有root进程才允许锁住要求的页面。
EINVAL：输入参数len不是个合法的正数。
mlock所用到的主要数据结构和重要常量
１．mm_struct
struct mm_struct {
int count;
pgd_t * pgd; /* 进程页目录的起始地址，如图2-3所示 */
unsigned long context;
unsigned long start_code, end_code, start_data, end_data;
unsigned long start_brk, brk, start_stack, start_mmap;
unsigned long arg_start, arg_end, env_start, env_end;
unsigned long rss, total_vm, locked_vm;
unsigned long def_flags;
struct vm_area_struct * mmap; /* 指向vma双向链表的指针 */
struct vm_area_struct * mmap_avl; /* 指向vma AVL树的指针 */
struct semaphore mmap_sem;
}
start_code、end_code：进程代码段的起始地址和结束地址。
start_data、end_data：进程数据段的起始地址和结束地址。
arg_start、arg_end：调用参数区的起始地址和结束地址。
env_start、env_end：进程环境区的起始地址和结束地址。
rss：进程内容驻留在物理内存的页面总数。
2. 虚存段（vma）数据结构：vm_area_atruct
虚存段vma由数据结构vm_area_atruct(include/linux/mm.h)描述：
struct vm_area_struct {
struct mm_struct * vm_mm; /* VM area parameters */
unsigned long vm_start;
unsigned long vm_end;
pgprot_t vm_page_prot;
unsigned short vm_flags;
/* AVL tree of VM areas per task, sorted by address */
short vm_avl_height;
struct vm_area_struct * vm_avl_left;
struct vm_area_struct * vm_avl_right;
/* linked list of VM areas per task, sorted by address */
struct vm_area_struct * vm_next;
/* for areas with inode, the circular list inode->i_mmap */
/* for shm areas, the circular list of attaches */
/* otherwise unused */
struct vm_area_struct * vm_next_share;
struct vm_area_struct * vm_prev_share;
/* more */
struct vm_operations_struct * vm_ops;
unsigned long vm_offset;
struct inode * vm_inode;
unsigned long vm_pte; /* shared mem */
};
vm_start;//所对应内存区域的开始地址
vm_end; //所对应内存区域的结束地址
vm_flags; //进程对所对应内存区域的访问权限
vm_avl_height;//avl树的高度
vm_avl_left; //avl树的左儿子
vm_avl_right; //avl树的右儿子
vm_next;// 进程所使用的按地址排序的vm_area链表指针
vm_ops;//一组对内存的操作
这些对内存的操作是当对虚存进行操作的时候Linux系统必须使用的一组方法。比如说，当进程准备访问某一虚存区域但是发现此区域在物理内存不存在时（缺页中断），就激发某种对内存的操作执行正确的行为。这种操作是空页（nopage）操作。当Linux系统按需调度可执行的页面映象进入内存时就使用这种空页（nopage）操作。
当一个可执行的页面映象映射到进程的虚存地址时，一组vm_area_struct结构的数据结构（vma）就会生成。每一个vm_area_struct的数据结构（vma）代表可执行的页面映象的一部分：可执行代码，初始化数据（变量），非初始化数据等等。Linux系统可以支持大量的标准虚存操作，当vm_area_struct数据结构（vma）一被创建，它就对应于一组正确的虚存操作。
属于同一进程的vma段通过vm_next指针连接，组成链表。如图2-3所示，struct mm_struct结构的成员struct vm_area_struct * mmap 表示进程的vma链表的表头。
为了提高对vma段 查询、插入、删除操作的速度，LINUX同时维护了一个AVL（Adelson-Velskii and Landis）树。在树中，所有的vm_area_struct虚存段均有左指针vm_avl_left指向相邻的低地址虚存段，右指针vm_avl_right指向相邻的高地址虚存段，如图2-5。struct mm_struct结构的成员struct vm_area_struct * mmap_avl表示进程的AVL树的根，vm_avl_height表示AVL树的高度。
对平衡树mmap_avl的任何操作必须满足平衡树的一些规则：
Consistency and balancing rulesJ（一致性和平衡规则）：
tree->vm_avl_height==1+max(heightof(tree->vm_avl_left),heightof(
tree->vm_avl_right))
abs( heightof(tree->vm_avl_left) - heightof(tree->vm_avl_right) ) <= 1
foreach node in tree->vm_avl_left: node->vm_avl_key <= tree->vm_avl_key, foreach node in tree->vm_avl_right: node->vm_avl_key >= tree->vm_avl_key.
注：其中node->vm_avl_key= node->vm_end
对vma可以进行加锁、加保护、共享和动态扩展等操作。
3．重要常量
mlock系统调用所用到的重要常量有：PAGE_MASK、PAGE_SIZE、PAGE_SHIFT、RLIMIT_MEMLOCK、VM_LOCKED、 PF_SUPERPRIV等。它们的值分别如下：
PAGE_SHIFT １2 // PAGE_SHIFT determines the page size
PAGE_SIZE 0x1000 //1UL<<PAGE_SHIFT
PAGE_MASK ~(PAGE_SIZE-1) //a very useful constant variable
RLIMIT_MEMLOCK 8 //max locked-in-memory address space
VM_LOCKED 0x2000 //8*1024=8192, vm_flags的标志之一。
PF_SUPERPRIV 0x00000100 //512,
mlock系统调用代码函数功能分析
下面对各个函数的功能作详细的分析((1)和（2）在前面简介mlock时已介绍过，并在后面有详细的程序流程)：
suser()：如果用户有效（即current->euid == 0 ），则设置进程标志为root优先权（current->flags |= PF_SUPERPRIV），并返回1；否则返回0。
find_vma(struct mm_struct * mm, unsigned long addr)：输入参数为当前进程的mm、需要加锁的开始内存地址addr。find_vma的功能是在mm的mmap_avl树中寻找第一个满足mm->mmap_avl->vm_start<=addr< mm->mmap_avl->vm_end的vma，如果成功则返回此vma；否则返回空null。
mlock_fixup(struct vm_area_struct * vma, unsigned long start, unsigned long end, unsigned int newflags)：输入参数为vm_mmap链中的某个vma、需要加锁内存区域起始地址和结束地址、需要修改的标志（0：加锁，1：释放锁）。
merge_segments(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)：输入参数为当前进程的mm、需要加锁的开始内存地址start_addr和结束地址end_addr。merge_segments的功能的是尽最大可能归并相邻（即内存地址偏移量连续）并有相同属性（包括vm_inode,vm_pte,vm_ops,vm_flags）的内存段，在这过程中冗余的vm_area_structs被释放，这就要求vm_mmap链按地址大小排序（我们不需要遍历整个表，而只需要遍历那些交叉或者相隔一定连续区域的邻接vm_area_structs）。当然在缺省的情况下，merge_segments是对vm_mmap_avl树进行循环处理，有多少可以合并的段就合并多少。
mlock_fixup_all(struct vm_area_struct * vma, int newflags)：输入参数为vm_mmap链中的某个vma、需要修改的标志（0：加锁，1：释放锁）。mlock_fixup_all的功能是根据输入参数newflags修改此vma的vm_flags。
mlock_fixup_start(struct vm_area_struct * vma,unsigned long end, int newflags)：输入参数为vm_mmap链中的某个vma、需要加锁内存区域结束地址、需要修改的标志（0：加锁，1：释放锁）。mlock_fixup_start的功能是根据输入参数end，在内存中分配一个新的new_vma，把原来的vma分成两个部分： new_vma和vma，其中new_vma的vm_flags被设置成输入参数newflags；并且按地址（new_vma->start和new_vma->end）大小序列把新生成的new->vma插入到当前进程mm的mmap链或mmap_avl树中（缺省情况下是插入到mmap_avl树中）。
注：vma->vm_offset+= vma->vm_start-new_vma->vm_start;
mlock_fixup_end(struct vm_area_struct * vma,unsigned long start, int newflags)：输入参数为vm_mmap链中的某个vma、需要加锁内存区域起始地址、需要修改的标志（0：加锁，1：释放锁）。mlock_fixup_end的功能是根据输入参数start，在内存中分配一个新的new_vma，把原来的vma分成两个部分：vma和new_vma，其中new_vma的vm_flags被设置成输入参数newflags；并且按地址大小序列把new->vma插入到当前进程mm的mmap链或mmap_avl树中。
注：new_vma->vm_offset= vma->vm_offset+(new_vma->vm_start-vma->vm_start);
mlock_fixup_middle(struct vm_area_struct * vma,unsigned long start, unsigned long end, int newflags)：输入参数为vm_mmap链中的某个vma、需要加锁内存区域起始地址和结束地址、需要修改的标志（0：加锁，1：释放锁）。mlock_fixup_middle的功能是根据输入参数start、end，在内存中分配两个新vma，把原来的vma分成三个部分：left_vma、vma和right_vma，其中vma的vm_flags被设置成输入参数newflags；并且按地址大小序列把left->vma和right->vma插入到当前进程mm的mmap链或mmap_avl树中。
注：vma->vm_offset += vma->vm_start-left_vma->vm_start;
right_vma->vm_offset += right_vma->vm_start-left_vma->vm_start;
kmalloc()：将在后面3.3中有详细讨论。
insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vmp)：输入参数为当前进程的mm、需要插入的vmp。insert_vm_struct的功能是按地址大小序列把vmp插入到当前进程mm的mmap链或mmap_avl树中，并且把vmp插入到vmp->inode的i_mmap环（循环共享链）中。
avl_insert_neighbours(struct vm_area_struct * new_node,** ptree,** to_the_left,** to_the_right)：输入参数为当前需要插入的新vma结点new_node、目标mmap_avl树ptree、新结点插入ptree后它左边的结点以及它右边的结点（左右边结点按mmap_avl中各vma->vma_end大小排序）。avl_insert_neighbours的功能是插入新vma结点new_node到目标mmap_avl树ptree中，并且调用avl_rebalance以保持ptree的平衡树特性，最后返回new_node左边的结点以及它右边的结点。
avl_rebalance(struct vm_area_struct *** nodeplaces_ptr, int count)：输入参数为指向vm_area_struct指针结构的指针数据nodeplaces_ptr[]（每个元素表示需要平衡的mmap_avl子树）、数据元素个数count。avl_rebalance的功能是从nodeplaces_ptr[--count]开始直到nodeplaces_ptr[0]循环平衡各个mmap_avl子树，最终使整个mmap_avl树平衡。
down(struct semaphore * sem)：输入参数为同步（进入临界区）信号量sem。down的功能根据当前信号量的设置情况加锁（阻止别的进程进入临界区）并继续执行或进入等待状态（等待别的进程执行完成退出临界区并释放锁）。
down定义在/include/linux/sched.h中：
extern inline void down(struct semaphore * sem)
{
if (sem->count <= 0)
__down(sem);
sem->count--;
}
up(struct semaphore * sem)输入参数为同步（进入临界区）信号量sem。up的功能根据当前信号量的设置情况（当信号量的值为负数：表示有某个进程在等待使用此临界区 ）释放锁。
up定义在/include/linux/sched.h中：
extern inline void up(struct semaphore * sem)
{
sem->count++;
wake_up(&sem->wait);
}
kfree_s(a,b)：kfree_s定义在/include/linux/malloc.h中：#define kfree_s(a,b) kfree(a)。而kfree()将在后面3.3中详细讨论。
avl_neighbours(struct vm_area_struct * node,* tree,** to_the_left,** to_the_right)：输入参数为作为查找条件的vma结点node、目标mmap_avl树tree、node左边的结点以及它右边的结点（左右边结点按mmap_avl中各vma->vma_end大小排序）。avl_ neighbours的功能是根据查找条件node在目标mmap_avl树ptree中找到node左边的结点以及它右边的结点，并返回。
avl_remove(struct vm_area_struct * node_to_delete, ** ptree)：输入参数为需要删除的结点node_to_delete和目标mmap_avl树ptree。avl_remove的功能是在目标mmap_avl树ptree中找到结点node_to_delete并把它从平衡树中删除，并且调用avl_rebalance以保持ptree的平衡树特性。
remove_shared_vm_struct(struct vm_area_struct *mpnt)：输入参数为需要从inode->immap环中删除的vma结点mpnt。remove_shared_vm_struct的功能是从拥有vma结点mpnt 的inode->immap环中删除的该结点。
为了节约内存的使用，在系统中，各进程通常采用共享内存，即不同的进程可以共享同一段代码段或数据段。当某一进程发生对共享的内存发生写操作时，为了不影响其它进程的正常运行，系统将把该内存块复制一份，供需要写操作的进程使用，这就是所谓的copy-on-write机制。copy_page就是提供复制内存功能的函数，它调用C语言中标准的内存操作函数，将首地址为from的一块虚拟内存页复制到首地址为to的空间中。
有关avl树的一些操作：
1、static inline void avl_neighbours (struct vm_area_struct * node, struct vm_area_struct * tree, struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
寻找avl树tree中的节点node的前序节点和后序节点，将结果放在指针to_the_left和to_the_right中，即使得*to_the_left->next=node，node->next=*to_the_right。在实际搜索中，过程是找到node节点中的左节点的最右节点和右节点的最左节点，采用avl树搜索可以提高效率。
2、static inline void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count)
将由于插入操作或删除操作而造成不平衡的avl树恢复成平衡状态。nodeplaces_ptr是指向的是需要调整的子树的根节点，count是该子树的高度。
static inline void avl_insert (struct vm_area_struct * new_node,
struct vm_area_struct ** ptree)
将新节点new_node插入avl树ptree中，并将该树重新生成平衡avl树。在创建avl树时，将vma模块不断的插入avl树中，构建一个大的avl树。当进程创建时，复制父进程后需要将以双向链表拷贝过来的vma链生成avl树。
4、static inline void avl_insert_neighbours (struct vm_area_struct * new_node, struct vm_area_struct ** ptree, struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
将新节点new_node插入avl树ptree中，并将该树重新生成平衡avl树，同时返回该新节点的前序节点和后序节点。
5、static inline void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree)
将指定要删除的节点node_to_delete从avl树ptree中删除。并将该树重新生成平衡avl树。该函数在释放虚存空间和归并vma链表是使用。
7、static void printk_list (struct vm_area_struct * vma)
8、static void printk_avl (struct vm_area_struct * tree)
9、static void avl_checkheights (struct vm_area_struct * tree)
10、static void avl_checkleft (struct vm_area_struct * tree, vm_avl_key_t key)
11、static void avl_checkright (struct vm_area_struct * tree, vm_avl_key_t key)
12、static void avl_checkorder (struct vm_area_struct * tree)
13、static void avl_check (struct task_struct * task, char *caller)
这些函数都是系统调试时用以检测avl树结构的正确性
14、static inline int vm_enough_memory(long pages)
通过计算当前系统中所剩的空间判断是否足够调用。可使用的内存包括缓冲存储器、页缓存、主存中的空闲页、swap缓存等。
15、static inline unsigned long vm_flags(unsigned long prot, unsigned long flags)
提供宏功能将页的保护位和标志位合并起来。
16、unsigned long get_unmapped_area(unsigned long addr, unsigned long len)
从虚拟内存address开始找到未分配的连续空间大于len的虚拟空间块，并将该快的首地址返回。
17、unsigned long do_mmap(struct file * file, unsigned long addr, unsigned long len,
unsigned long prot, unsigned long flags, unsigned long off)
do_mmap在Linux虚拟内存管理中是一个很重要的函数，它的主要功能是将可执行文件的映象映射到虚拟内存中，或将别的进程中的内存信息映射到该进程的虚拟空间中。并将映射了的虚拟块的vma加入到该进程的vma avl树中。其运行的流程如下，更详细的分析请参阅林涛同学和徐玫峰同学的报告。
检验给定的映射长度len是大于1页，小于一个任务的最大长度3G且加上进程的加上偏移量off不会溢出。如不满足则退出。
如果当前任务的内存是上锁的，检验加上len后是否会超过当前进程上锁长度的界限。如是则退出。
如果从文件映射，检验文件是否有读的权限。如无在退出。
调用get_unmaped取得从地址address开始未映射的连续虚拟空间大于len的虚存块。
如从文件映射，保证该文件控制块有相应的映射操作。
为映射组织该区域申请vma结构。
调用vm_enough_memory有足够的内存。如无则释放6中申请的vma，退出。
如果是文件映射，调用file->f_op_mmap将该文件映射如vma中。
调用insert_vm_struct将vma插入该进程的avl树中。
归并该avl树。
18、void merge_segments (struct mm_struct * mm, unsigned long start_addr,
unsigned long end_addr)
经过对进程虚拟空间不断的映射，在进程中的vma块有许多是可以合并的，为了提高avl树查找的效率，减少avl树中不必要的vma块，通常需要将这些块和并，merge_segments的功能为合并虚拟空间中从start_addr到end_addr中类型相同，首尾相连的vma块。由于只有经过增加操作采有可能合并，所有merge_segments只在do_mmap和unmap_fixup中被调用。该函数的流程如下：
根据起始地址start_addr从找到第一块满足vm_end>start_addr的vma块mpnt。
调用avl_neighbours找到在vma双向链表上与mpnt前后相连的vma块prev和next。
如果prev和mpnt首尾相连，且有同样在swap file中的节点，同样的标志，同样的操作等则将其合并，反之转向6。
调用avl_remove将mpnt从avl树中删除，调整prev的结束地址和后序指针。
将结构mpnt所占的物理空间删除。
prev、mpnt、next依次下移，如未超过end_addr则返回3。
19、static void unmap_fixup(struct vm_area_struct *area, unsigned long addr, size_t len)
释放虚拟空间中的某些区域的时候，将会出现四种情况：
将整个vma释放掉
将vma的前半部分释放掉
将vma的后半部分释放掉
将vma的中间部分释放掉
为了正常维护vma树，当第一种情况是，将整个vma释放掉。同时释放vma结构所占的空间。第二种，释放后半部分，修改vma的相关信息。第二种，释放前半部分，修改vma的相关信息。第四种，由于在vma中出现了一个洞，则需增加一个vma结构描述新出现的vma块。unmap_fixup所执行的工作就是当释放空间时，修正对vma树的影响。
20、int do_munmap(unsigned long addr, size_t len)
do_munmap将释放落在从地址addr开始，长度为len空间内的vma所对应的虚拟空间。do_munmap被系统调用sys_munmap所调用（对sys_munmap如何工作的不甚了解）。下面是该函数的流程：
通过find_vma根据addr找到第一块vma->end>addr的vma块mpnt。
调用avl_neighbours找到mpnt在链表中的相邻指针prev和next。
将检查中所有与虚拟空间addr~addr+len相交的vma块放入free链表中。同时如果该vma链接在共享内存中，则将其从该环形链表中释放出来。
按序搜索free链表，调用unmap_fixup释放空间。
调用zap_page_range将指向释放掉的虚拟空间中的pte页表项清零。
调用kfree释放mpnt结构占用的空间。
remap.c
该文件提供了对虚拟内存重映射的若干函数。在下文中将介绍这些函数的功能，分析这些函数在虚拟内存管理中所起的作用。同时详细介绍其中主要函数的流程。
static inline pte_t *get_one_pte(struct mm_struct *mm, unsigned long addr)
根据输入的虚存地址返回其在虚拟内存中的对应的页表项pte。
static inline pte_t *alloc_one_pte(struct mm_struct *mm, unsigned long addr)
根据输入的虚存地址addr在pgd表中根据三级页表映射机制找pte，如果在pgd表中无对应的项，则分配给一个pgd（pmd）表项，在这个表项内分配根据addr分配pte，将pte返回。
static inline int copy_one_pte(pte_t * src, pte_t * dst)
将目的pte（dst）表项中的值赋成源pte（src）中的值，然后将源pte中的值清零，根据这函数的功能取move_one_pte更合适。
static int move_one_page(struct mm_struct *mm,
unsigned long old_addr, unsigned long new_addr)
根据输入的虚拟地址old_addr调用get_one_pte获取该地址在三级页表中的pte项，调用copy_one_pte将该pte对应的物理页指针移到根据new_addr对应的pte项上，即在虚拟空间内移动一虚拟内存页。
static int move_page_tables(struct mm_struct * mm,
unsigned long new_addr, unsigned long old_addr, unsigned long len)
将虚拟地址空间中从old_addr开始的长度为len的虚拟内存移动到以new_addr为起始地点的的虚拟空间中，以下为该函数的流程：
将所需移动的内存长度len赋值给偏移量offset如果offset＝0，结束。反之转向2。
将偏移量offset减去一个页的长度，调用move_one_page将从old_addr+offset开始的一页移到new_addr+offset。若发生错误则转到4。
如果offset不为0，则转向1，反之结束。
调用move_one_page将所有已移动到新地址的页移回源地址，调用zap_page_range将从new_addr开始的移动过的页pte清零，并返回出错信息－1。
static inline unsigned long move_vma(struct vm_area_struct * vma,
unsigned long addr, unsigned long old_len, unsigned long new_len)
将虚存中的vma块vma的起始地址为addr，长度为old_len的内存块扩展为长度为new_len的内存块，并在虚存中找到可容纳长度为new_len块的连续区域，返回首地址。其工作流程如下：
给新的vma结构块new_vma分配空间，如果不成功返回出错信息。
调用get_unmap_area从addr开始找到第一个未被利用的虚存空洞，空洞长度大于给定的新的虚拟内存块的长度len，将其首地址赋给new_addr。如果未招到,则转向9。
调用move_page_tables将从addr开始的长度为old_len的内存区域移动到以new_addr为起始地址的虚拟空间中。
修改new_vma块中关于起始地址，结束地址的值。
将新的new_vma块插入到当前进程的虚拟内存所链成的双向链表和avl树中。
调用merge_segment将虚拟空间中地址可能连结在一起的不同的vma段连结成一个vma块，同时删除冗于的vma块。
将原有空间中的从addr开始，长度为old_len的虚拟空间释放掉。
修改mm结构中的所有虚存的长度，返回新的起始虚拟地址new_addr。
将vma块new_vma释放掉并返回出错信息。
asmlinkage unsigned long sys_mremap(unsigned long addr, unsigned long old_len,
unsigned long new_len unsigned long flags)
sys_remap是一个系统调用，其主要功能是扩展或收缩现有的虚拟空间。它的主要工作流程如下：
检查addr地址是否小于4096，如小于，则非法，返回。
将原始长度old_len和需要扩展或收缩的长度new_len页对齐。
如果有old_len>new_len，则说明是收缩空间，调用do_munmap将虚存空间中从new_len到old_len的空间释放掉。返回收缩后的首地址addr。
根据addr找到第一块vma块满足vma->end > addr，检查addr是否落在虚存的空洞中，如是，则返回出错信息。
检查需要扩展的内存块是否落在该vma块中，越界则返回出错信息。
如果该vma是上锁的，则检测上锁的内存扩展后是否越界，如是，则7返回出错信息 。
检测当前进程的虚存空间经扩展后是否超过系统给该进程的最大空间。如是，则返回出错信息。
如果找到vma块从addr开始到块末尾的长度为old_len且(old_len的长度不等于new_len或该虚存是不可移动的)，则转向9，反之转向10。
检测从跟随找到的vma块的未分配的空间是否大于需要扩展空间。如果大于，则直接将扩展的空间挂在找到的vma块后，修改vma块中相关的信息，并返回扩展后虚拟块的首地址。如小于转向10。
如果当前虚拟块是是不可移动的，则返回错误信息。反之，调用move_vma将需要扩展的虚拟块移动可以容纳其长度new_len的虚拟空间中。
页区可以使页面分配更有目的性, 有利于减少内存碎片. 每个页区的页分配仍使用伙伴(buddy)算法.
伙伴算法将整个页区划分为以2为幂次的各级页块的集合, 相邻的同次页块称为伙伴, 一对伙伴可以合并到更高次页面集合中去.
下面分析一下伙伴算法的页面释放过程.
; mm/page_alloc.c:
#define BAD_RANGE(zone,x) (((zone) != (x)->zone) || (((x)-mem_map) offset) || (((x)-mem_map) >= (zone)->offset+(zone)->size))
#define virt_to_page(kaddr) (mem_map + (__pa(kaddr) >> PAGE_SHIFT))
#define put_page_testzero(p) atomic_dec_and_test(
void free_pages(unsigned long addr, unsigned long order)
{ order是页块尺寸指数, 即页块的尺寸有(2^order)页.
if (addr != 0)
__free_pages(virt_to_page(addr), order);
}
void __free_pages(struct page *page, unsigned long order)
{
if (!PageReserved(page) put_page_testzero(page))
__free_pages_ok(page, order);
}
static void FASTCALL(__free_pages_ok (struct page *page, unsigned long order));
static void __free_pages_ok (struct page *page, unsigned long order)
{
unsigned long index, page_idx, mask, flags;
free_area_t *area;
struct page *base;
zone_t *zone;
if (page->buffers)
BUG();
if (page->mapping)
BUG();
if (!VALID_PAGE(page))
BUG();
if (PageSwapCache(page))
BUG();
if (PageLocked(page))
BUG();
if (PageDecrAfter(page))
BUG();
if (PageActive(page))
BUG();
if (PageInactiveDirty(page))
BUG();
if (PageInactiveClean(page))
BUG();
page->flags ~((1 page->age = PAGE_AGE_START;
zone = page->zone; 取page所在的页区
mask = (~0UL) base = mem_map + zone->offset; 求页区的起始页
page_idx = page - base; 求page在页区内的起始页号
if (page_idx ~mask) 页号必须在页块尺寸边界上对齐
BUG();
index = page_idx >> (1 + order);
; 求页块在块位图中的索引, 每一索引位置代表相邻两个"伙伴"
area = zone->free_area + order; 取该指数页块的位图平面
spin_lock_irqsave( flags);
zone->free_pages -= mask; 页区的自由页数加上将释放的页数(掩码值为负)
while (mask + (1 struct page *buddy1, *buddy2;
if (area >= zone->free_area + MAX_ORDER) 如果超过了最高次平面
BUG();
if (!test_and_change_bit(index, area->map)) 测试并取反页块的索引位
/*
* the buddy page is still allocated.
*/
break; 如果原始位为0, 则说明该页块原来没有伙伴, 操作完成
/*
* Move the buddy up one level. 如果原始位为1, 则说明该页块存在一个伙伴
*/
buddy1 = base + (page_idx ^ -mask); 对页块号边界位取反,得到伙伴的起点
buddy2 = base + page_idx;
if (BAD_RANGE(zone,buddy1)) 伙伴有没有越过页区范围
BUG();
if (BAD_RANGE(zone,buddy2))
BUG();
memlist_del( 删除伙伴的自由链
mask area++; 求更高次位图平面
index >>= 1; 求更高次索引号
page_idx mask; 求更高次页块的起始页号
}
memlist_add_head( + page_idx)->list, 将求得的高次页块加入该指数的自由链
spin_unlock_irqrestore( flags);
/*
* We don't want to protect this variable from race conditions
* since it's nothing important, but we do want to make sure
* it never gets negative.
*/
if (memory_pressure > NR_CPUS)
memory_pressure--;
}
typedef struct { unsigned long pgd; } pgd_t; 一级页目录字结构
typedef struct { unsigned long pmd; } pmd_t; 中级页目录字结构
typedef struct { unsigned long pte_low; } pte_t; 末级页目录字结构
typedef struct { unsigned long pgprot; } pgprot_t; 页属性字结构
pgd_t *pgd = pgd_offset(mm_struct,addr);
取进程虚拟地址addr的一级页目录字指针,扩展为
((mm_struct)->pgd + ((address >> 22) 0x3FF))
pgd_t *pgd = pgd_offset_k(addr)
取内核地址addr的一级页目录字指针,扩展为
(init_mm.pgd + ((address >> 22) 0x3FF));
pmd_t *pmd = pmd_offset(pgd, addr) ;
从一级页目录字指针取addr的中级页录字指针,在2级分页系统中,它们的值是相同的,扩展为
(pmd_t *)(pgd);
pte_t *pte = pte_offset(pmd, addr)
从中级页目录字指针取addr的末级页目录字指针,扩展为
(pte_t *)((pmd->pmd 0xFFFFF000) + 0xC0000000) + ((addr >> 12) 0x3FF);
struct page *page = pte_page(pte_val));
取末级页目录字pte_val的页面映射指针,扩展为
(mem_map+(pte_val.pte_low >> 12))
pte_t pte_val = ptep_get_and_clear(pte);
取末级页目录字指针pte的值,并将该目录字清零,扩展为
(pte_t){xchg(...
pte_t pte_val = mk_pte(page,pgprot);
将页面映射指针page与页属性字pgprot组合成页目录字,扩展为
(pte_t) { (page - mem_map)
pte_t pte_val = mk_pte_phys(physpage, pgprot);
将物理地址physpage所在页面与页属性字组合成页目录字,扩展为
(pte_t) { physpage >> 12
unsigned long addr = pmd_page(pmd_val);
取中级页目录字所表示的页目录虚拟地址,扩展为
((unsigned long) (pmd_val.pmd 0xFFFFF000 + 0xC0000000));
set_pte(pte,pte_val);
设置末级页目录字,扩展为
*pte = pteval;
set_pmd(pmd,pmd_val)
设置中级页目录字,扩展为
*pmd = pmd_val;
set_pgd(pgd,pgd_val)
设置一级页目录字,扩展为
*pgd = pgd_val;
One of the biggest problems currently facing the Linux memory management subsystem is memory fragmentation. This is the result of several developments in other parts of the Linux kernel, most importantly the growth of each process'es kernel stack to 8 kB and the dynamic allocation of DMA and networking buffers. These factors, together with a general speedup of both peripheral hardware and the device drivers has lead to a situation where the currently used buddy allocator just can't cut it anymore. This white-paper is divided in 3 pieces, the problem, the solution and some actual code. I need a lot of comments and hints for possible improvement, so feel free to email them to me...
The problem
The problem is caused by the fact that memory is allocated in chunks of different sizes. For most types of usage we just allocate memory one page (4 kB on most machines) at a time, but sometimes we give out larger pieces of memory (2, 4, 8, 16 or 32 pages at once). Because of the fact that most UNIX (and Linux) machines have a completely full memory (free memory is wasted memory), it is next to impossible to free larger area's and the best we can do is be very careful not to hand out those large areas when we only need a small one.
There have been (and there are) several workarounds for this fragmentation issue; one of them (PTE chaining) even involves a physical to logical translating, almost reverse page table-like solution. With that project, we can swap out pages based on their physical address, thus force freeing that one page that blocked an entire 128 kB area. This would solve most of our problems, except when that last page is unswappable, for example a page table or a program's kernel stack. In that case, we're screwed regardlessly of what deallocation scheme we're using.
Because our inability to hand out larger chunks of memory has impact on system functionality and could even have impact on system stability it seems warranted to sacrifice a little bit of speed (the buddy system is fast!) in order to solve most of the above problems. The main problem with the current system is that it doesn't differentiate between swappable and unswappable memory, leading to a system where page tables and other cruft are scattered all over the system, making it impossible to free up one large contiguous area.
This problem is made even worse by the fact that on some architectures we can only do DMA to addresses under 16 MB and it will undoubtedly show up again in some years when we all have 16 GB of memory and try do do DMA to those oldie 32 bit PCI cards that don't support dual cycle address mode :-)
The solution
The solution is to hand out free zones of 128 kB large, and to use each zone for one type of usage only. Then we can be sure that no page tables interfere with the freeing of a zone of user memory, and we can always just free an area of memory.
In the current Linux kernel, we have the following uses for memory:
reserved memory, kernel code and statically allocated kernel structures: after system boot we never much with the layout of this memory so it's a non issue wrt. the allocator
user memory: this memory can be swapped out and/or relocated at will, it is allocated one page at a time and gives us no trouble, apart from the fact that we always need more than we have physically available; no special requirements
kernel stack: we allocate 8 kB (2 pages) of unswappable kernel stack for each process; each of those stacks needs to be physically contiguous and it needs to be in fast memory (not in uncached memory)
page tables: page directories are unswappable, page tables and (on some machines) page middle directories can be moved/swapped with great caution; the memory for these is given out one page at a time; we only look up the page tables every once in a while so speed is not very critical; when we have uncached memory, we'd rather use it for page tables than for user pages
small SLAB: SLAB memory is used for dynamic kernel data; it is allocated and freed at will, unfortunately this will is not ours but that of the (device) driver that requested the memory; speed is critical
large SLAB: the same as small SLAB, but sometimes the kernel wants large chunks (> 2 pages); we make the distinction between the two because we don't want to face hopeless fragmentation inside the SLAB zones...
DMA buffers: this memory needs to be physically below a certain boundary (16 MB for ISA DMA) and is often allocated in chunks of 32, 64 or 128 kB
For small (< 16 MB) machines, the above scheme is overkill and we treat several types of usage as one. We can, for instance, treat large SLAB and DMA the same, and small SLAB, kernel stack and page table can be allocated in the same zones too. Small slab and kernel stack will be treated the same on every machine; the distinction is only made because I want the documentation to be complete.
In addition to this, we can differentiate between 3 different kinds of memory:
DMA memory: this memory is located under the 16 MB limit and is cached by the L1 and L2 caches
'normal' memory: this memory is located above the DMA limit and is cached by the L1 and L2 caches, it can not be used for DMA buffers
slow memory: this memory is not cached or present on an add-on board, it can not be used for DMA buffers and using it for time critical kernel stack and SLAB would be disastrous for performance; we also don't want to use it for CPU intensive user applications
Since we don't want to waste the slow memory we might have, we can use that for page tables and user memory that isn't used very often. If we have user memory in slow memory and it turns out that it is used very often we can always use the swap code to relocate it to fast memory. DMA memory is scarce, so we want to allocate that only we specifically need it or when we don't have any other memory left.
This leads to the following zone allocation orders:
SLAB and kernel stack | user memory | page tables | DMA buffers
-----------------------+---------------+----------------+-------------
normal memory | normal memory | slow memory | DMA memory
DMA memory | slow memory | normal memory |
slow memory | DMA memory | DMA memory |
This means that when, for instance, we ran out of user memory and there is enough free memory available, we first try to grab a zone of 'normal memory', if that fails we look for a free area of slow memory and DMA memory is tried last.
Page allocation
For SLAB, page table and DMA memory we always try to allocate from the fullest zone available and we grab a free zone when we're out of our own memory. In order to grab the fullest zone, we keep these zones in a (partially?) sorted order. For large SLAB/DMA areas we will also want to keep in mind the sizes of the memory chunks previously allocated in this zone.
User pages are kept on a number of linked lists: active, inactive, clean and free. We allocate new pages in the inactive queue and perform allocations from the free queue first, moving to the clean queue when we're out of free pages. Inactive pages get either promoted to the active queue (when they're in heavy use) or demoted to the clean queue (when they're dirty, we have to clean them first). Pages in the clean queue are also unmapped from the page table and thus already 'halfway swapped out'. Pages only enter the free list when a program free()s pages or when we add a new zone to the user area.
In order to be able to free new zones (for when SLAB gets overly active), we need to be able to mark a relatively free zone force-freeable. Upon scanning such a page kswapd will free the page and make sure it isn't allocated again.When the PTE chaining system gets integrated into the kernel, we can just force-free a user zone with relatively few active pages when the system runs out of free zones. Until then we'll need to keep two free zones and walk the page tables to find and free the pages.
Actual code
There's not much of actual code yet but all the administrative details are ready. ALPHA status reached and the .h file is ready :)
/*
* The struct mem_zone is used to describe a 32 page memory area.
*/
struct mem_zone {
mem_zone * prev, next; /* The previous and next zone on this list */
unsigned long used; /* Used pages bitmap for SLAB, etc !!! count for user */
unsigned long flags;
};
/*
* Flags for struct_mem->flags
*/
#define ZONE_DMA 0x00000001 /* DMA memory */
#define ZONE_SLOW 0x00000002 /* uncached/slow memory */
#define ZONE_USER 0x00000004 /* usermode pages, these defines are for paranoia only */
#define ZONE_SLAB 0x00000008 /* large SLAB */
#define ZONE_STK 0x00000010 /* kernel stack and order-1 SLAB (and order-0 SLAB if there is slow memory) */
#define ZONE_PTBL 0x00000020 /* page tables and one-page SLAB (except when there is slow memory) */
#define ZONE_DMA 0x00000040 /* DMAbuffers */
#define ZONE_RECL 0x00000080 /* We are reclaiming this zone */
#define ZONE_0 0x00000100 /* loose pages allocated */
#define ZONE_1 0x00000200 /*order-1 (2^1 = 2 page)chunks allocated */
#define ZONE_2 0x00000400 /* etc... In order to help in buddy-like allocation for */
#define ZONE_3 0x00000800 /* large SLAB zones on small memory machines. */
#define ZONE_4 0x00001000
#define ZONE_5 0x00002000
/*
* Memory statistics
*/
typedef struct {
unsigned long used;
unsigned long free;
} zone_stats_t;
struct memstats {
struct zone_stats_t ptbl;
struct zone_stats_t stk;
struct zone_stats_t slab;
struct zone_stats_t dma;
/* Slightly different structs for these */
struct user {
unsigned long active;
unsigned long inactive;
unsigned long clean; /* we do lazy reclamation */
unsigned long free;
};
struct free {
unsigned long dma; /* different memory types */
unsigned long normal;
unsigned long slow;
};
struct misc {
unsigned long num_physpages;
unsigned long reserved; /* reserved pages */
unsigned long kernel; /* taken by static kernel stuff */
};
};
/* This is where we find the different zones */
struct memzones {
struct free {
struct mem_zone dma;
struct mem_zone normal;
struct mem_zone slow;
};
struct mem_zone dma;
struct mem_zone user;
struct mem_zone slab;
struct mem_zone stk;
struct mem_zone ptbl;
};