第四章 内存管理 (lab2)

提纲 页面管理 页表管理

页面管理 页面管理链表的结构 现在我们来讨论用于页面管理的双向链表结构。首先，我们来看一下构成这个链表的结点的情况。该结点的结构是在memlayout.h中规定的： typedef LIST_ENTRY(Page) Page_LIST_entry_t; struct Page { Page_LIST_entry_t pp_link; /* free list link */ // pp_ref is the count of pointers (usually in page table entries) // to this page, for pages allocated using page_alloc. // Pages allocated at boot time using pmap.c's // boot_alloc do not have valid reference count fields. uint16_t pp_ref; }; 而LIST_ENTRY的定义则在queue.h中： #define LIST_ENTRY(type) struct { struct type *le_next; /* next element */ \ struct type **le_prev; /* ptr to ptr to this element */ \ }

页面管理（续） 通过分析，我们可以写出Page结构： struct Page { struct { struct Page *le_next; struct Page **le_prev; } pp_link; uint16_t pp_ref; };

页面管理（续） 链表头的定义 memlayout.h中的： 和queue.h中的： 通过分析，我们发现Page_list结构实际上可以写成： LIST_HEAD(Page_list, Page); 和queue.h中的： #define LIST_HEAD(name, type) struct name { struct type *lh_first; /* first element */ } 通过分析，我们发现Page_list结构实际上可以写成： struct Page_list{ struct Page *lh_first; }; 它只包含了一个指向Page结构的指针lh_first。同时，page_free_list这个全局变量实际上就是指向页面管理双向链表的头结构了，注意，它不是一个struct Page类型的指针或空结构！

页面管理（续） 系统还定义了一些宏来对这个链表头进行操作： 在queue.h中，还定义了很多用于操纵结点和对该双向链表进行操作的宏： #define LIST_FIRST(head) ((head)->lh_first) //取得头指针 #define LIST_INIT(head) //将链表重置 在queue.h中，还定义了很多用于操纵结点和对该双向链表进行操作的宏： #define LIST_NEXT(elm, field) ((elm)->field.le_next)) //该宏返回elm所的下一个页面管理结点的地址。elm应该为一个指向页面管理结点的指针，field=pp_link #define LIST_INSERT_HEAD(head, elm, field) //这个宏的功能，是将elm指向的页面管理结点成为整个页面管理双向链表的第一个元素，在实现上，是要求链表头结构（page_free_list）的lh_first指针指向该结构。这里需要考虑两种情况，一种是链表以前就是空的情况，另一种情况，是链表以前不为空的情况。

页面管理（续） #define LIST_INSERT_BEFORE(listelm, elm, field) #define LIST_INSERT_AFTER(listelm, elm, field) //这两个宏所要做的事情，是把新的结点（elm参数），插入到结点listelm之前或者之后。对于Page结构的pp_link.le_next指针的使用，应该比较容易理解，需要解释的是pp_link.le_prev的使用。在链表的结点中，这个域所指向的前一个结点的（(elm)->pp_link.le_next）的地址！ #define LIST_REMOVE(elm, field) //该宏所做的工作是将elm所指向的结点从页面管理链表中消除。这里要注意pp_link.prev的用法，它只是用来index前一个结点的le_next域，从而直接修改里面的内容，而不能索引整个前面的结点（比方说访问前一个结点的pp_ref域的内容），虽然，从链表构造的角度来说，这样设计就足够了。 #define LIST_FOREACH(var, head, field) // 这个宏实际上写的是一个for循环头，它的作用是在该循环中遍历页面管理链表。需要注意的是，这个循环是不能用pp_link.le_prev域来替代的！

页面管理（续） 页面管理链表结构 注：注意这里实线和虚线的含义

页面管理（续） 页面管理链表在内存中的存储和放置 Boot_alloc(); Page_init(); check_page_alloc();

页面管理（续） 页面管理的操作 page_alloc(); page_free();

页表管理 三类地址 逻辑地址（Virtual Address） 线性地址(Linear Address) 是指程序在编译连接后，变量名字等的符号地址，在JOS系统中的内核部分，该地址是以KERNBASE（默认等于0xF0000000，实际上可以根据具体的情况加以修改）开始的。 线性地址(Linear Address) 是指经过x86保护模式的段地址变换后的地址，该变换的过程是 逻辑地址+段首地址 物理地址(Physical Address) 是指内存存储单元的编址，如1GB的内存，它的物理编址是从0x00000000到0x40000000。

页表管理（续） 三类地址的关系

页表管理（续） 段式地址转换 过程为程序的逻辑地址＋段首地址 例如段首地址为－0xf000000时，一个逻辑地址为0xf0100000。经过转换后，得到线性地址0x00100000。 分页机制需要经过设置CR3和CR0后才打开。 在未打开分页机制的情况下，段式地址转换得到的线性地址就是物理地址。 在打开分页机制之后，线性地址需要再次经过页式地址变换才能得到物理地址。

页表管理（续） 页式地址转换

页表管理（续） 对页式地址转换的说明 当启用了x86页式内存管理后，当处理器碰到一个线性地址后，它会把这个地址分成3部分：它们分别是页目录索引（Directory）、页表索引（Table）和页内偏移（Offset），这3个部分把原本32位的线性地址分成了10位、10位和12位的3个片段。既然页内偏移地址占12位，页的大小就自然为4KB了。 Code walk Inc/mmu.h中，定义了宏PDX(la)，用于取得线性地址la的页目录索引 定义了PTX(la)，用于取得线性地址la中的页表索引 定义了PGOFF(la)，用于取得页内偏移 同时注意该头文件中的其他宏定义，如PTE_P、PTE_U、PTE_W，它们用于定义页表项的权限

页表管理（续） 页目录（表）项的格式 每个页目录或者页表都存储在单独的页面中 每个4KB的物理页面，实际上它在内部分成了1024个单元（10位有1024个可能的值），每个单元占4字节（32位，也就是保护模式下一个uint32_t类型所占的内存空间大小），它们称为页目录项（Page Directory Entry），这些单元与页表中包含的单元在格式上是一致的，不同的是页表中的单元称为页表项（Page Table Entry）。

页表管理（续） 页目录（表）项的格式（续） 高20位存储的是一个地址，但因为只有高20位（使用的时候低位会被全部清零），所以只能寻址4KB对齐的地址空间（这就是为什么我们在为页目录分配空间时要寻找内核代码后第一个4KB对齐的地址的原因），同时，由于x86把所有物理内存分成了4KB大小的页，每个页的首地址必然是4KB对齐的！所以这个表项中的高20位地址能够定位到内存中任何一个物理页面的首地址。 P —— Present，该位用来判断对应物理页面是否存在，如果存在，该位置1，否则为0； R/W —— Read/Write，该位用来判断对所指向的物理页面的访问权限，如果为1，表示页面可写，否则，是只读页面； U/S —— User/Supervisor，该位用来定义页面的访问者应该具备的权限。如果为1，表示该页面是User权限的，大家都可以访问，如果为0，表示只能是Ring0中的程序能访问； D —— Dirty，是否被修改； A —— Accessed，最近是否被访问； AVAIL —— Available，可以被系统程序所使用； 0 —— 保留位，不能使用。 这些位系统在访问一个页面时就会自动地去判断，如果访问不符合规矩（如页面根本就不存在，或者权限不对的情况），系统就会产生异常，让系统去处理。

页表管理（续） 页式地址转换的分析 该机制能够对0~4GB空间内的任何线性地址进行转换，这时，页目录的每个页目录项都将指向一个包含1024个页表项的页表（占用一个4KB的物理页面），整个页式转换机制将占用额外的1024+1=1025个4KB的物理页面，也就是大约4MB。然而，由于系统运行过程中可能不会用到这么大的地址空间，所以不会有那么多页表被创建。 为每个用户进程创建一个页目录，并将这个页目录保存到用户进程的上下文中，当该用户进程被切换过来执行的时候，就将该用户进程的页目录地址写入CR3，并重新启动一次页式内存管理。这样就能够实现每个用户进程的虚地址空间为4GB。当然如果采用这种方式，势必占用更多的内存用于页式地址变换。 对于老版本的Linux系统以及我们现在接触的JOS系统，为了避免太大的内存开销（另一个原因是因为还没有虚拟内存的支持），在整个系统中只使用一个页目录。这就意味着，整个系统的线性地址空间只有4GB，而且是所有（操作系统内核、各个用户程序）代码所公用的！这种情况下，就必须对线性地址进行合理的规划了。

页表管理（续） 页式地址转换的分析 对于页式地址管理，由于页目录以及页表都存放在物理内存的页面中，要进行地址变换就势必先要到内存中访问页目录和页表。由于CPU和内存速度的不匹配，这样将势必极大地降低系统的效率。为了提高地址翻译的速度，提高系统的效率，x86系统中设计了用于地址翻译的缓存来解决这一问题，这一缓存称为TLB（Translation Look-aside buffer，即旁路转换缓冲，或称为页表缓冲），在该缓存中存放了用于最近几次地址翻译的页表项，由于程序执行的局部性原理，下一次的地址转换往往跟上一次的地址转换采用的是同一个页目录表项和页表项），同时，由于TLB跟处理器的距离更近，这样就极大地提高了地址翻译的效率和速度。 但是，这样做可能存在一个潜在的问题：页目录（表）数据项的不一致性。以前系统里对应一个线性地址只有唯一的存放在内存中的页目录和页表，用于完成翻译的工作，但是，现在由于TLB的存在，系统可能在高速缓存中也存放了一份页表项数据，用于更快地对地址进行翻译，大多数时候，它们是一致的，但是也有例外的情形。因为TLB中的数据对于程序员来说，是不可见的，程序对于页表项或者页目录项的修改并不能马上反映到TLB中，这样就可能导致错误的地址翻译，因为为了提高翻译的速度，处理器总是尽量地采用TLB中的页表数据进行地址的翻译。所以，为了避免这种数据的不一致性所导致的地址翻译的错误情形的出现，系统程序员就必须在对页表进行修改后，使TLB中旧的页表数据失效。使其失效的办法有两个，一个是重载CR3，使整个TLB中的数据都失效，也可以采用invlpg指令。

页表管理（续） 页目录、页表和数据页的关联 Code walk and implementation pgdir_walk() page_lookup() page_remove() page_insert() boot_map_segment()

页表管理（续） pgdir_walk pte_t * pgdir_walk(pde_t *pgdir, const void *va, int create) 检查虚拟地址（应该是线性地址）va已经能够用页表（页目录+页表的体系）翻译，如果能够，则返回该地址对应的页表项的地址；如果不能，同时create=0的话，则返回空（NULL）；但是，如果create=1的话，为该地址创建对应的页表（因为没有实际物理页面相对应，即使创建，返回的页表项中的地址部分也为空！），并返回va所对应的页表项的地址。 注意：该函数返回的页表项地址为内核地址！

页表管理（续） page_lookup struct Page * page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) 在页式地址翻译机制中查找线性地址va所对应的物理页面，如果找到，则返回该物理页面，并将对应的页表项的地址放到pte_store中；如果找不到，或其他原因，则返回空（NULL）。

页表管理（续） page_remove void page_remove(pde_t *pgdir, void *va) 注意：在删除页面的时候，调用的是page_decref()，仅减低该页面的引用度，而不一定要将页面删除。同时，由于页表项发生了修改，删除操作完成后，应该调用tlb_invalidate()更新TLB。

页表管理（续） page_insert int page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm) 这是JOS在实现页面支持中最重要的一个函数，该函数的功能是将页面管理结构pp所对应的物理页面分配给线性地址va。同时，将对应的页表项的permission设置成PTE_P&perm。 注意：一定要考虑到线性地址va已经指向了另外一个物理页面或者干脆就是这个函数要指向的物理页面的情况。如果线性地址va已经指向了另外一个物理页面，则先要调用page_remove将该物理页从线性地址va处删除，再将va对应的页表项的地址赋值为pp对应的物理页面。如果va指向的本来就是参数pp所对应的物理页面，则将va对应的页表项中的物理地址赋值重新赋值为pp所对应的物理页面的首地址即可。

页表管理（续） boot_map_segment static void boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm) 在页表中，将线性地址[la, la+size]映射到物理地址[pa, pa+size]。 注意：size一定是PGSIZE(4KB)的整数倍。这个函数带来的疑问是：是否有可能有一个物理页面，它已经被分配作为存储页表的页面了，但由于在[pa, pa+size]范围内，所以又被用来成为某线性地址对应的物理页面了？！

页表管理（续） JOS的线性地址规划

页表管理（续） 按照JOS的要求，一共有三个线性地址到物理地址的映射是必须的： [UPAGES, sizeof(PAGES) ] => [pages, sizeof(PAGES)] 这里PAGES代表页面管理结构所占用的空间； [KSTACKTOP – KSTKSIZE, 8] => [bootstack, 8] 其中bootstack为内核编译时预先留下的8个页面（用做内核堆栈）； [KERNBASE, pages in the memory] => [0, pages in the memory] 这个地址映射范围比较广，含盖了所有物理内存。 其中，最后一个地址映射最重要，因为JOS其后启动新的段式地址，新的段base=0x0（见struct Segdesc gdt[]），如果没有这个地址映射，以前的内核地址（0xf0000000开始的地址是无法变换到实际的物理地址的）！

本章结束