基于分页 (paging) 机制，完成线性地址（linear address）到物理地址（physical address）的转换。
分页的功能有两个：
页地址转换机制是可选的，由硬件（MMU：Memory Manager Unit）来进行转换，可由程序来配置转换规则，如映射关系、异常(page fault)处理
线性地址也称虚拟地址，当 CR0 寄存器 PG 位为 1 时，指令访问虚拟地址，由 MMU 转换成实际的物理地址。
线性地址和物理地址被分为 4KByte 大小的最小单元，前者称为 Page，后者称为 Frame。
机制的关键在于控制 Page 到 Frame 的映射关系和映射过程：
page 结构体包含两部分内容：
对于 4G 内存，若完全记录 page 与 frame 的对应关系，需要 4MByte 空间（ 4 字节的 page 结构共 1M 个）
事实上，一般不会全部要用到 1M 个 page，设计额外的两层指针结构，减少对内存的占用
最终形成三级结构：
线性地址(32bit)被分为三部分看待
page 异常编号为 14，分为两类异常：
操作系统的异常处理会加载不存在的页，并重试指令
page 以 4k 为基本大小，因此在分配内存时应以 4k 对齐
对 dc5c38 版本 core/mem.c 和 include/system.h 进行分析
// page 中有 20bit 来映射 1K 的 frame
87 typedef struct page {
88 uint32_t present : 1;
89 uint32_t rw : 1;
90 uint32_t user : 1;
91 uint32_t accessed: 1;
92 uint32_t dirty : 1;
93 uint32_t unused : 7;
94 uint32_t frame : 20;
95 } page_t;
96
// page table 包含 1024 个 page ( entry )
97 typedef struct page_table {
98 page_t pages[1024];
99 } page_table_t;
100
// page directory 包含 1024 个 page table
//
// 此外在任务切换中需要保存分页相关内容，需要对内存进行拷贝
// 但切换分页配置后内存映射也将发生变化
// 保存额外的 page directory 和 1024 个 page table 的物理地址，以方便拷贝操作
101 typedef struct page_directory {
102 page_table_t *tables[1024]; /* 1024 pointers to page tables... */
103 uintptr_t physical_tables[1024]; /* Physical addresses of the tables */
104 uintptr_t physical_address; /* The physical address of physical_tables */
105 } page_directory_t;
11 /*
12 * kmalloc() is the kernel's dumb placement allocator
13 */
// uintptr_t 为 unsigned long 整形，表示物理地址
// align 是否按 4k 对齐
// phys 不为空时，返回对应的物理地址。这里与 return 一样？
14 uintptr_t
15 kmalloc_real(
16 size_t size,
17 int align,
18 uintptr_t * phys
19 ) {
// 内存对齐
20 if (align && (placement_pointer & 0xFFFFF000)) {
21 placement_pointer &= 0xFFFFF000;
22 placement_pointer += 0x1000;
23 }
24 if (phys) {
25 *phys = placement_pointer;
26 }
27 uintptr_t address = placement_pointer;
28 placement_pointer += size;
29 return address;
30 }
代码中 kmalloc* 为不对齐版本， kvmalloc* 为对齐版本。
// frames 为 128k 字节的 bitset，表示 frame 是否被占用
// nframe 为总的 frame 个数（因为是 int 型，所以是总内存除以 4）
74 uint32_t *frames;
75 uint32_t nframes;
76
77 #define INDEX_FROM_BIT(b) (b / 0x20)
78 #define OFFSET_FROM_BIT(b) (b % 0x20)
79
80 static void
81 set_frame(
82 uintptr_t frame_addr
83 ) {
84 uint32_t frame = frame_addr / 0x1000;
85 uint32_t index = INDEX_FROM_BIT(frame);
86 uint32_t offset = OFFSET_FROM_BIT(frame);
87 frames[index] |= (0x1 << offset);
88 }
89
90 static void
91 clear_frame(
92 uintptr_t frame_addr
93 ) {
94 uint32_t frame = frame_addr / 0x1000;
95 uint32_t index = INDEX_FROM_BIT(frame);
96 uint32_t offset = OFFSET_FROM_BIT(frame);
97 frames[index] &= ~(0x1 << offset);
98 }
99
100 static uint32_t
101 test_frame(
102 uintptr_t frame_addr
103 ) {
104 uint32_t frame = frame_addr / 0x1000;
105 uint32_t index = INDEX_FROM_BIT(frame);
106 uint32_t offset = OFFSET_FROM_BIT(frame);
107 return (frames[index] & (0x1 << offset));
108 }
109
// 找到第一个未被占用的 frame
110 static uint32_t
111 first_frame() {
112 uint32_t i, j;
113 for (i = 0; i < INDEX_FROM_BIT(nframes); ++i) {
114 if (frames[i] != 0xFFFFFFFF) {
115 for (j = 0; j < 32; ++j) {
116 uint32_t test_frame = 0x1 << j;
117 if (!(frames[i] & test_frame)) {
118 return i * 0x20 + j;
119 }
120 }
121 }
122 }
123 return -1;
124 }
160 void
161 paging_install(uint32_t memsize) {
// 物理内存开头存放 frame bitset，4G 内存共 128KB，未对齐（不需要对齐？）
162 nframes = memsize / 4;
163 frames = (uint32_t *)kmalloc(INDEX_FROM_BIT(nframes));
164 memset(frames, 0, INDEX_FROM_BIT(nframes));
// 接下来是系统 page directory，初始没有可用的 page table
165 kernel_directory = (page_directory_t *)kvmalloc(sizeof(page_directory_t));
166 memset(kernel_directory, 0, sizeof(page_directory_t));
167 current_directory = kernel_directory;
168
// 对于已经占用的 128KB + sizeof( page_directory_t )
// 建立相同地址的虚拟地址到物理地址的映射关系
//
// 注意！！
// 因为需要建立新的 page table 来存储，这部分 page table 也需要被上映射
// while 循环直到生成足够多的 page 来保存 bitset + page directory + page tables
169 uint32_t i = 0;
170 while (i < placement_pointer) {
171 alloc_frame(get_page(i, 1, kernel_directory), 0, 0);
172 i += 0x1000;
173 }
174 isrs_install_handler(14, page_fault);
175 switch_page_directory(kernel_directory);
176 }
189
190 page_t *
191 get_page(
192 uintptr_t address,
193 int make,
194 page_directory_t * dir
195 ) {
// 物理地址 / 4k 得到对应的 page index
196 address /= 0x1000;
// page index / 1024 得到对应的 page table index
197 uint32_t table_index = address / 1024;
// 若 page table index 未被创建，则创建之（会占用更多的物理空间，增大 placement_pointer）
198 if (dir->tables[table_index]) {
199 return &dir->tables[table_index]->pages[address % 1024];
200 } else if(make) {
201 uint32_t temp;
202 dir->tables[table_index] = (page_table_t *)kvmalloc_p(sizeof(page_table_t), (uintptr_t *)(&temp));
203 memset(dir->tables[table_index], 0, 0x1000);
204 dir->physical_tables[table_index] = temp | 0x7; /* Present, R/w, User */
205 return &dir->tables[table_index]->pages[address % 1024];
206 } else {
207 return 0;
208 }
209 }
物理或虚拟寻址的关键在于 CR0.PG 是否启用。
在 toaruos 中，默认的 page directory 和 page table 的线性地址与物理地址一致。设置完成后才打开 CR0.PG 开关。
此后操作 page directory 和 page table 时将使用虚拟地址。