第5 章 内存管理 从功能角度可以将内存管理代码分成两大部分,一部分是对内存子系统初始化的支 持,另一部分是对xv6操作系统正常运行时的内存进行管理。另外,根据物理页帧和虚拟 存储空间的不同,又分成物理页帧的分配、回收管理和虚存空间分配、回收以及映射管理。 其中虚存空间又根据保护级的不同,分成内核空间和用户空间两部分。从上面的分析可 知,xv6的内存管理将分成图5-1的6个部分。图中对物理页帧管理标示为P,虚存空间 管理分成两类,内核空间标示为K,用户空间表示为U,再加上初始化标示为I和运行时 标示为R,分别有P-I、P-R、K-I、K-R、U-I、U-R六种组合,并且在图5-1中还给出了各部 分所在的章节。 图5-1 内存管理子系统功能划分(以及所在的章节) 注意:初学者需要理清以下知识脉络:在共享的物理页帧基础之上,通过段页机制 实现虚-实地址转换,进而形成各个进程独立的虚存空间(编程空间、程序空间)。关于 x86分段的细节我们不深入讨论,读者可以参考Intel的数据手册。本章内容将着重于通 用的分页机制。这样一来我们在xv6内核讨论中就不用区分逻辑地址和线性地址,统一 第5 章 内存管理1 19 用虚地址和虚存空间来指代它们。 虽然xv6启动了分页机制并采用虚地址这个术语,但并没有实现页帧与磁盘的交换 功能,因此并不具备完整意义上的虚存管理,只是具备了分页管理能力。 在后续讨论中,为了方便区分,将虚拟空间的页称为虚页,物理空间的页称为页帧。 对于未加以说明的“页”,读者可以根据具体情况自行判断。 5.1 物理内存初始化(P-I) 物理内存的初始化(P-I),分成大页模式的早期布局和启动4KB分页后的空闲物理 页帧初始化。初始化的目的是为了摸清物理内存资源总量,并通过链表管理所有空闲页 帧,这是物理内存分配和管理的依据。 5.1.1 早期布局 此时内存布局仍如图4-5所示。在kernelmain()函数最开始处,xv6启用大页模式 并具有以下的内存布局:内核代码存在于物理地址低地址的0x100000处,而虚存空间的 (0~0x0040-0000)和(0x8000-0000~0x8040-0000)地址开始的两段4MB都映射了内核 代码。此时的早期页表为main.c文件中的entrypgdir数组,其中只有两项有效:虚拟地 址[0,4MB]映射到物理地址[0,4MB];虚拟地址[KERNBASE,KERNBASE+4MB] 映射到物理地址[0,4MB]。此时只使用了一个物理页(4MB的大页)并映射到两个不同 的虚存空间。 各CPU 的GDT 在kernel的main()执行seginit()更新自己的全局段描述符GDT 之前,主CPU 使 用的是前章代码4-7的第80行定义的三个段,当时各个段选择子和GDT 表项的对应关 系如图4-3所示。 seginit()定义于代码5-4的第15行。每个处理器都要执行这个初始化,最终各个处 理器核上的段表内容几乎相同:在每CPU 变量cpus[].gdt[]中设置4项,分别对应内核 代码段SEG_KCODE、内核数据段SEG_KDATA、用户代码段SEG_UCODE、用户数据 段SEG_UDATA。新装载的GDT表内容如图5-2所示(对比图4-3旧的GDT)。各处理 器不同的地方是SEG_KCPU 段,由段寄存器GS使用,对应于“每CPU”变量或CPU 私 有变量。 当main()执行seginit()之后将重新设置段,此时使用的GDT表是每CPU 变量c-> gdt,在执行代码5-4的第25~31行后进行设置,第33行seginit()->lgdt()之后开始使 操作系统原型———xv6分析与实验120 图5-2 main()重新对GDT初始化后的内容 用该GDT,如图5-2所示。可以看出在地址映射方面,内核代码段SEG_KCODE 、内核数 据段SEG_KDATA 、用户代码段SEG_UCODE和用户数据段SEG_UDATA都是从0地 址到0xf (4GB)的范围,也就是说从地址映射方面基本放弃了段式管理。但是各段 的特权级是不同的,内核代码和数据特权级最高为0,用户代码和数据最低为DPL_ USER(级别3)。 此时的段和原来相比,多了用户空间的两个段和每CPU变量所在的段。由于内核 相关的段并没有变化,因此lgdt()并不影响seginit()的继续执行,将正常返回到main() 函数继续运行。main()后续还会执行kinit2()结束全部内存的初始化工作。 其中,SEG_KCPU为“每CPU”变量所在的段,由附加段寄存器GS管理。该段是唯 一不从0地址开始且长度仅有8字节,各个CPU上取值不相同的特殊段。由于每CPU 变量不在多个CPU间共享,因此不需要用加锁方法进行保护,所以访问速度比加锁方式 的变量更快。xv6系统中每CPU变量只有cpu和proc两个,因此一共才8字节。 SEG_TSS是任务状态段,每次从scheduler切换到某个进程时,将在switchuvm()函 数内设置含有该进程的内核栈指针。 5.2 物理页帧的初始化 1. 此时,kernel实际能用的虚拟地址空间显然不足以完成正常的工作,所以初始化过程 中需要获得更多可用物理页帧并重新设置页表。 空闲页帧链表 在启用4KB分页之后,将物理内存划分成4KB大小的页帧来管理,空闲的物理页帧 构成一个链表,页帧开头的4个字节用作指针,形成如图5-3所示的空闲物理页帧链表。 由于xv6没有实现对x86内存总量的测定,只是简单地使用总量为240MB (PHYSTOP)的物理内存,因此在内核刚启动时,从kernel结束地址一直到240MB的空 第5 章 内存管理1 21 图5-3 空闲物理页帧的组织管理 间都是空闲的。 xv6在main()函数中调用kinit1()和kinit2()来初始化物理内存,将空闲物理页帧构成 链表。需要注意的是,除了启动时短暂使用了4MB的大页模式外,xv6正常运行时使用的 是4KB页。其中kinit1()初始化第一个4MB的物理范围,其中从kernel结束处到4MB边 界的物理内存空间组织为空闲未使用①,kinit2初始化剩余内核空间到PHYSTOP为未使 用②,如图5-4所示。相关的具体代码分析请见代码5-1的第30行和第38行。 图5-4 kinit1()/kinit2()函数调用层次 上述两个函数的核心是代码5-1的第45行的freerange(),该函数将传入的地址范围 (vstart,vend)之间的所有页,逐个通过kfree()登记为空闲页。代码5-1的第59行的 kfree()将一个页插入到空闲页帧链表kmem.freelist链表头部。 因此当main()->kinit1(end,P2V(4*1024*1024))执行结束时,(end,4MB)区间 的物理页帧将构成一个单向链表,表头为kmem.freelist,如图5-5所示。而kinit2()则把 (4MB,PHYSTOP)范围内的物理页帧插入到空闲链表中。 读者需要注意,虽然我们这里管理的是[0~4MB]的物理空闲页帧,但是程序使用的 是虚地址,即kinit1()中的指针p*位于[0x8000-0000~0x8040-0000]区间。此时的页表 ①②虽然此时为4MB页,但是按照4KB页帧进行组织。 kinit2()在4KB页的环境下工作,前面的main()->kmalloc()完成4KB页表的建立。 操作系统原型———xv6 分析1 22 与实验 仍如图4-5所示。在kinit1()执行的时候,页表其实只映射了4MB的一个页帧,因此当前 也不可能通过程序地址访问其他物理内存空间,这就是为什么kinit1()只初始化4MB物 理内存的原因。而后面kvmalloc()之后建立了内核页表且映射了240MB的物理内存之 后,才能用kinit2()对后续的物理页帧进行组织管理,才能访问到对应页帧并填写链接信 息到页帧中。 图5-5 kinit1()对(end,4MB)以及kinit2()对(4MB,PHYSTOP)区间构建的空闲页帧链表 5.1.3 kalloc.c和mmu.h kalloc.c中有刚讨论过的用于物理内存初始化的kinit1()和kinit2(),页帧分配kalloc() 和回收kfree()等函数。mmu.h中则有大量关于页表映射相关的常量、宏和函数。 1.kalloc.c 代码5-1的第15行定义了run结构体,用于形成页帧链表,第19行定义了kmem 结 构体,用于管理链表。如前面图5-3所示,kmem 成员变量包括空闲页帧链表指针freelist 以及互斥锁lock。 代码5-1 kalloc.c 1. //Physical memory allocator, intended to allocate 2. //memory for user processes, kernel stacks, page table pages, 3. //and pipe buffers. Allocates 4096-byte pages 4. 5. #include "types.h" 6. #include "defs.h" 7. #include "param.h" 8. #include "memlayout.h" 9. #include "mmu.h" 10. #include "spinlock.h" 11. 第5 章 内存管理1 23 12. void freerange(void *vstart, void *vend); 13. extern char end[]; //first address after kernel loaded from ELF file 14. 15. struct run { 16. struct run *next; 17. }; 18. 19. struct { 20. struct spinlock lock; 21. int use_lock; 22. struct run *freelist; //就是一个next 指针,见第15 行定义 23. } kmem; 24. 25. //Initialization happens in two phases 26. //1. main() calls kinit1() while still using entrypgdir to place just 27. //the pages mapped by entrypgdir on free list 28. //2. main() calls kinit2() with the rest of the physical pages 29. //after installing a full page table that maps them on all cores 30. void 31. kinit1(void *vstart, void *vend) 32. { 33. initlock(&kmem.lock, "kmem"); //创建一个用于管理空闲页帧链表的锁 34. kmem.use_lock = 0; 35. freerange(vstart, vend); //[vstart~vend]都挂入到空闲页帧链(见第46 行) 36. } 37. 38. void 39. kinit2(void *vstart, void *vend) 40. { 41. freerange(vstart, vend); 42. kmem.use_lock = 1; 43. } 44. 45. void 46. freerange(void *vstart, void *vend) 47. { 48. char *p; // 注 意 ,这 里 用的是虚地址指针 操作系统原型———xv6 分析1 24 与实验 49. p = (char*)PGROUNDUP((uint)vstart); // 将 地 址 转换成页边界 50. for(; p + PGSIZE <= (char*)vend; p += PGSIZE) 51. kfree(p); / /回收一个页帧 52. } 53. 54. //PAGEBREAK: 21 55. //Free the page of physical memory pointed at by v, 56. //which normally should have been returned by a 57. //call to kalloc(). (The exception is when 58. //initializing the allocator; see kinit above.) 59. void 60. kfree(char *v) //释放虚地址v 指向的物理页帧 61. { 62. struct run *r; 63. 64. if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP) //页边界对齐且不越界 65. panic("kfree"); 66. 67. //Fill with junk to catch dangling refs 68. memset(v, 1, PGSIZE); //用数字“1”填充该页 69. 70. if(kmem.use_lock) 71. acquire(&kmem.lock); 72. r = (struct run*)v; //将页帧v 插入到链表头部 73. r->next = kmem.freelist; 74. kmem.freelist = r; 75. if(kmem.use_lock) 76. release(&kmem.lock); 77. } 78. 79. //Allocate one 4096-byte page of physical memory 80. //Returns a pointer that the kernel can use 81. //Returns 0 if the memory cannot be allocated 82. char* 83. kalloc(void) 84. { 85. struct run *r; 第5 章 内存管理1 25 86. 87. if(kmem.use_lock) 88. acquire(&kmem.lock); 89. r = kmem.freelist; //从链表头部取一个空闲页帧 90. if(r) 91. kmem.freelist = r->next; //链表头后移到下一个空闲页帧 92. if(kmem.use_lock) 93. release(&kmem.lock); 94. return (char*)r; 95. } kinit1()和kinit2()也定义在这里,两者的实现非常相似,差别在于kinit1()对互斥锁 进行初始化,以及两者处理的地址范围不同。kinit1()和kinit2()都利用freerange()将 vstart~vend地址范围内的页帧添加到freelist链表中。当初始化完成之后,freerange() 用于回收页帧(当然,也可以将初始化看成某种意义上的回收操作)。freerange()对 vstart~vend所覆盖的物理页帧,逐个调用kfree()进行回收,每次一个页帧。 在系统正常运行需要分配页帧时,将调用kalloc(),它扫描kmem.freelist链表,从中 摘除一个页帧并返回。反之将kfree()释放的页帧重新加入kmem.freelist。 由于这些函数只是涉及简单的链表操作,读者可以自行详细阅读和分析。 2.memlayout.h 代码5-2给出了内存布局的信息,通过宏定义给出了若干个常量。物理地址相关的有: 1M(0x100000)以上的地址为扩展内存EXTMEM,物理内存上限为PHYSTOP,设备使用的 物理内存起始地址为DEVSPACE。虚地址相关的有:内核起点KERNBASE,内核的链接地 址KERNLINK,以及用于虚地址和物理地址转换的宏,V2P/V2P_WO和P2V/P2V_WO。 代码5-2 memlayout.h 1. //Memory layout 2. 3. #define EXTMEM 0x100000 //Start of extended memory 4. #define PHYSTOP 0xE000000 //Top physical memory 5. #define DEVSPACE 0xFE000000 //Other devices are at high addresses 6. 7. //Key addresses for address space layout (see kmap in vm.c for layout) 8. #define KERNBASE 0x80000000 //First kernel virtual address 操作系统原型———xv6 分析1 26 与实验 9. #define KERNLINK (KERNBASE+EXTMEM) //Address where kernel is linked 10. 11. #define V2P(a) (((uint) (a)) - KERNBASE) 12. #define P2V(a) (((void *) (a)) + KERNBASE) 13. 14. #define V2P_WO(x) ((x) - KERNBASE) //same as V2P, but without casts 15. #define P2V_WO(x) ((x) + KERNBASE) //same as P2V, but without casts 5.2 页帧的分配与回收(P-R) 前面讨论中提到:kalloc.c中的代码一部分参与物理内存管理子系统的初始化,属于 物理内存初始化(P-I)部分;另一部分则是用于物理页帧分配与回收操作,主要涉及分配 函数kalloc()和回收kfree(),属于内存管理的运行时(P-R)部分。我们现在着重分析分 配与回收,这两个函数都定义于代码5-1。 kfree()先对地址进行合法性检查,再执行第72~74行代码将该页插入到队列头部。 kalloc()则是在空闲链表头部取下一个页帧来完成分配操作。 kalloc()返回虚拟地址空间的地址,kfree()以虚拟地址为参数,通过kalloc()和kfree (),系统能够有效管理物理内存,让上层只需要考虑虚拟地址空间。 由此可见,xv6对物理页帧的管理非常简单,并没有像Linux那样考虑系统中的众多 其他因素,也不需要支持虚拟内存的换出操作。 5.3 内核空间 内核启动后则进入进程调度器scheduler()的无限循环,因此scheduler()使用页表所 表示的虚存空间就称为内核空间。在xv6kernel的main()中调用kvmalloc()来创建 scheduler内核执行流所使用的页表kpgdir(替换entry.S所使用的entrypgdir早期页 表),从而建立起xv6的内核态虚存空间。 这个页表内容也用来构建每个进程的内核空间,每个进程页表对应内核的部分(高地 址部分)将复制kpgdir内容(与scheduler执行流相同),而对应用户空间的部分页表将根 据应用程序的ELF文件而创建。 第5 章 内存管理1 27 也就是说每个进程所用的内核空间是一样的,一旦进入内核(例如系统调用或中断) 将可以访问整个系统的所有资源。 5.3.1 内核页表(K-I) xv6的内核执行流scheduler,只使用内核空间的页表,在用户空间没有映射任何内 容,即0x8000-0000以下地址所对应的页表项都没有映射到物理页帧。 1.scheduler内核页表 xv6kernel在main()->kinit1()之后紧接着执行main()->kvmalloc()建立内核空 间。kvmalloc()定义于代码5-4的第147行,具体是通过setupkvm()创建页表(4KB的 小页)并记录在全局变量kpgdir中,然后switchkvm()切换使用该页表(不再使用 bootblock建立的只有两项的、4MB的大页的entrypgdir页表)。 图5-6 内核页表的初始化过程 代码5-4的第128行的setupkvm()用于建立内核空间所对应的页表项,该函数先用 kalloc()分配一个页帧作为页表,然后依据kmap[]数组来填写kpgdir页表,其中kmap[] 数组的声明在代码5-4的第114~124行,它指出了内核中多个不同属性的区间。kmap[]所 描述的地址映射关系及相应的访问模式,如图5-7所示。kmap[0]映射了物理内存低 1MB的空间,kmap[1]是内核代码(及只读数据),kmap[2]是内核数据,kmap[3]映射了 用于设备的空间。xv6内核空间采用的映射方式和Linux内核映射相似,称为直接映射 或一致映射,虚地址和物理地址之间恒定相差一个常数偏移,这样很容易在物理地址和内 核虚地址之间进行转换。 mappages()定义于代码5-4的第69行,它依次为当前kmap[x]涉及的每个页帧建立 映射:通过walkpgdir()定位其PTE项,并按照kmap[]给出的映射要求填写该PTE,从