我老早就理解了分页的原理，不过真正落实到具体代码的时候，仍然花了好大一番功夫。我发现试图从代码中理解思路是非常困难的。因为正常的流程是先有思路，后有代码，假如一个完全不理解分页的人，试图通过阅读代码学会它，这几乎是找罪受。

即使我理解了分页，在我学习James的这篇[Paging]教程时，仍然花了好大的劲，最后不得不逼我用出GDB + IDA进行调试，这才搞懂了它的代码思路。

这篇文章是我个人的笔记，所以不会去从头讲原理，只讲解实现分页代码的主要部分，想学原理可以看James的教程。
alloc_address

内存管理

placement_address 指向 SECTIONS 的最后，也就是bss段的后面，该位置属于未分配的内存。
假如placement_address 现在指向0x180000，我们现在需要获得一个0x80大小的内存，那么alloc_address_int就会返回0x180000，之后把placement_address 加上0x80，变成0x180080，等待下一次分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
heap/kheap.c
*/
u32 alloc_address_int(u32 size,int align,u32 *phys){
	if(align == 1 && (placement_address & 0xFFFFF000)){
		placement_address &= 0xFFFFF000;
		placement_address += 0x1000;

	}
	if(phys){
		*phys = placement_address;
	}
	u32 tmp = placement_address;
	placement_address += size;
	return tmp;
}

页表和页目录

page 就是页目录项和页表项的结构，其中涉及到各种位，我保留了英文的注释，想具体了解也可看文档。
page_table 是页表，里面可以存储1024个页表项，每个页表项4字节。
page_directory 是页目录，保存了页表的地址，还有页目录本身的物理地址。

代码里需要说明的位置我加上了中文注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
include/paging.h
*/
typedef struct page
{
    u32 present    : 1;   // Page present in memory
    u32 rw         : 1;   // Read-only if clear, readwrite if set
    u32 user       : 1;   // Supervisor level only if clear
    u32 accessed   : 1;   // Has the page been accessed since last refresh?
    u32 dirty      : 1;   // Has the page been written to since last refresh?
    u32 unused     : 7;   // Amalgamation of unused and reserved bits
    u32 frame      : 20;  // Frame address (shifted right 12 bits)
} page_t;

typedef struct page_table
{
    page_t pages[1024];
} page_table_t;

typedef struct page_directory
{
    /**
       页表指针数组，只是为了方便操作。
    **/
    page_table_t *tables[1024];
    /**
        tablesPhysical就是页目录项，指向页表的物理地址，最后会将tablesPhysical放到CR3寄存器，表示页目录的起始地址。
    **/
    u32 tablesPhysical[1024];

    /**
    保存了当前页目录的物理地址。
    当真正开启分页机制后，一切的地址都会被视为虚拟地址，那么此时要新增页表的时候，我们必须得知道页目录的物理地址，故将其保存在自己的页目录内。
    **/
    u32 physicalAddr;
} page_directory_t;

Frame分配

页帧的分配，采用了一种数据结构叫bitset，就是用一连串的bit位，比如01011110，每一个位对应一个页帧，如果是1表示该页帧已被分配，如果是0表示未分配。bit串的第1位，对应物理地址0x0000，第2位对应0x1000，以此类推。

下面只贴出主要代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
page/paging.c
*/
static void set_frame(u32 frame_addr){
	u32 frame = frame_addr / 0x1000;
	u32 idx = INDEX_FROM_BIT(frame);
	u32 off = OFFSET_FROM_BIT(frame);
	frames[idx] |= (0x1 << off);
}

······

static u32 first_frame(){
	u32 i, j;
	for(i=0; i < INDEX_FROM_BIT(nframes);i++){
		
		if(frames[i] != 0xFFFFFFFF){
			for(j = 0; j < 32; j++)	{
				u32 toTest = 0x1 << j;
				if( !(frames[i]&toTest)){
					return i *4*8+j;
				}
			}
		}
	}
}

void alloc_frame(page_t *page, int is_kernel, int is_writeable)
{
    if (page->frame != 0)
    {
        return;
    }
    else
    {
        u32 idx = first_frame();
        if (idx == (u32)-1)
        {
            printk("No free frames!")
            return;
        }
        set_frame(idx*0x1000);
        page->present = 1;
        page->rw = (is_writeable)?1:0;
        page->user = (is_kernel)?0:1;
        page->frame = idx;
    }
}

set_frame 表示将指向的bit位置1。
first_frame 用于从bit串中寻找第一个能用的页帧。
alloc_frame 用于将可用的页帧地址写入到页表项中。

初始化分页

初始化函数，展示了开启分页从头到尾的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
page/paging.c
*/
void initialise_paging(){

// 表示物理内存最大是0x1000000。
	u32 mem_end_page = 0x1000000;
	
	// 计算一共有多少个页帧，每个页帧4kb大小，所以除以0x1000。
	// INDEX_FROM_BIT 计算需要多少个bit位。
	nframes = mem_end_page / 0x1000;
	frames = (u32*)alloc_address(INDEX_FROM_BIT(nframes));
	memset(frames,0,INDEX_FROM_BIT(nframes));

     //分配页目录。
	kernel_directory = (page_directory_t*)alloc_address_a(sizeof(page_directory_t));
	memset(kernel_directory, 0, sizeof(page_directory_t));
	current_directory = kernel_directory;


    // placement_address始终指向已使用内存的最后，所以要将已经使用的这些内存，在页目录和页表中分配好。
	int i = 0;
	while(i < placement_address){
		alloc_frame(get_page(i,1,kernel_directory),0,0);
		i += 0x1000;
	}
	
	//当出现页故障的时候，会发起14号中断，然后调用page_fault函数。
	register_interrupt_handler(14,page_fault);


    //开启分页。
	switch_page_directory(kernel_directory);

}

最后一个比较重要的函数get_page，它用来分配一个页表，并将这个页表的指针写进页目录项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
page/paging.c
*/
page_t *get_page(u32 address, int make, page_directory_t *dir)
{
    // Turn the address into an index.
    address /= 0x1000;
    
    // Find the page table containing this address.
    // 计算页表在页目录中的索引。
    u32 table_idx = address / 1024;
    
    if (dir->tables[table_idx]) // 如果该页表已经分配。
    {
        return &dir->tables[table_idx]->pages[address%1024];
    }
    else if(make)
    {
        u32 tmp;
        dir->tables[table_idx] = (page_table_t*)alloc_address_ap(sizeof(page_table_t), &tmp);
		memset(dir->tables[table_idx], 0, 1024*4);
        dir->tablesPhysical[table_idx] = tmp | 0x7; // PRESENT, RW, US.
        return &dir->tables[table_idx]->pages[address%1024];
    }
    else
    {
        return 0;
    }
}

测试

最后检验一下，功能的可靠性，我们先初始化并开启分页机制，然后尝试访问未分配的虚拟地址0xA0000000，造成页故障。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
init/kernel.c
*/
int kmain(void){
	
	console_clear();

	init_gdt();
	init_idt();

	printk("Hello,kernel;\n");

	init_timer(200);
	//asm volatile ("sti");
	initialise_paging();
	u32 *ptr = (u32*)0xA0000000;
	u32 do_page_fault = *ptr;

	return 0;

	
}

成功触发页故障，并调用了我们写好的page_fault函数。

参考资料：
JamesM’s kernel development tutorials