操作系统真象还原<第六部分>

操作系统
Word count: 9k   |   Reading time≈ 42 min

(｡･∀･)ﾉﾞ嗨起来！！！

内存管理系统

Makefile

make 命令可以自动找出变更的文件，并根据依赖关系，找出受变更文件影响的其它相关文件，然后对这些文件按照规则进行单独处理。

makefile 文件是 make 程序的搭档，它们发现某个文件更新后，只编译该文件和受该文件影响的相关文件，其它不受影响的文件不重新编译，从而提高了编译效率。

伪目标

make 规定，当规则中不存在依赖文件时，这个目标文件名就称为伪目标。

为了避免伪目标和真实目标文件同名的情况，可以用关键字“.PHONY”来修饰伪目标，格式为”.PHONY:伪目标名”。这样不管与伪目标同名的文件是否存在，make 照样执行伪目标处的命令。

image-20210225094704080

image-20210225094734587

自定义变量与系统变量

makefile 中定义变量的格式是: 变量名 = 值(字符串)。

变量引用的格式: $(变量名)。

image-20210225094832713

隐含规则

在编写规则时，若一行写不下，可以在行尾添加反斜杠字符 ‘\’，这样下一行的内容便被认为是同一行。

makefile 中用 # 来单行注释。

隐含规则：对于一些使用频率非常高的规则，make 把它们当成是默认的，不需要显式地写出来，当用户未在 makefile 中显式定义规则时，将默认使用隐含规则进行推导。

隐含规则只限于那些编译过程中基本固定的依赖关系，比如 C 语言代码文件扩展名为 .c，编译生成的目标文件扩展名是 .o。

常见的部分语言程序的隐含规则：

  • C 程序

    x.o 的生成依赖于 x.c

  • C++ 程序

    x.o 的生成依赖于 x.cc 或者 x.C

  • Pascal 程序

    x.o 的生成依赖于 x.p

自动化变量

@，表示规则中的目标文件名集合，如果存在多个目标文件，@ 则表示其中每一个文件名。

$<，表示规则中依赖文件的第 1 个文件。

$^，表示规则中所有依赖文件的集合，如果集合中有重复的文件，会自动去重。

$?，表示规则中，所有比目标文件 mtime 更新的依赖文件集合。

模式规则

% 用来匹配任意多个非空字符。比如 %.o 代表所有以 .o 为结尾的文件，g%.o 是以字符 g 开头的所有以 .o 为结尾的文件，make 会拿这个字符串模式去文件系统上查找文件，默认为当前路径下。

之后我们都用 makefile 来编译程序了

新增了一些编译选项并且把ubantu的终端修改为了bash，具体如下

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
BUILD_DIR = ./build
ENTRY_POINT = 0xc0001500
AS = nasm
CC = gcc
LD = ld
LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/
ASFLAGS = -f elf
CFLAGS = -m32 -fno-stack-protector -Wall $(LIB) -c -fno-builtin -W -Wstrict-prototypes \
         -Wmissing-prototypes 
LDFLAGS = -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
      $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
      $(BUILD_DIR)/debug.o

##############     c代码编译     ###############
$(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
        lib/stdint.h kernel/init.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
        lib/stdint.h kernel/interrupt.h device/timer.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
        lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/stdint.h\
         lib/kernel/io.h lib/kernel/print.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
        lib/kernel/print.h lib/stdint.h kernel/interrupt.h
	$(CC) $(CFLAGS) $< -o $@

##############    汇编代码编译    ###############
$(BUILD_DIR)/kernel.o: kernel/kernel.S
	$(AS) $(ASFLAGS) $< -o $@
$(BUILD_DIR)/print.o: lib/kernel/print.S
	$(AS) $(ASFLAGS) $< -o $@

##############    链接所有目标文件    #############
$(BUILD_DIR)/kernel.bin: $(OBJS)
	$(LD) $(LDFLAGS) $^ -o $@

.PHONY : mk_dir hd clean all

# ubantu中需要将dash修改为bash运行
# ls -al /bin/sh若结果为/bin/sh -> dash
# 执行sudo dpkg-reconfigure dash选择No即可
mk_dir:
	if [[ ! -d $(BUILD_DIR) ]];then mkdir $(BUILD_DIR);fi

hd:
	dd if=$(BUILD_DIR)/kernel.bin \
           of=/home/fyz/sc/bochs-2.6.2/hd60M.img \
           bs=512 count=200 seek=9 conv=notrunc

clean:
	cd $(BUILD_DIR) && rm -f ./*

build: $(BUILD_DIR)/kernel.bin

all: mk_dir build hd

断言

我们需要更新 interrupt.c和 interrupt.h 来实现开、关中断的函数

interrupt.c

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
# include "stdint.h"
# include "global.h"
# include "io.h"
# include "interrupt.h"

# define IDT_DESC_CNT 0x21  //支持的中断数
# define PIC_M_CTRL 0x20
# define PIC_M_DATA 0x21
# define PIC_S_CTRL 0xa0
# define PIC_S_DATA 0xa1
# define EFLAGS_IF 0x00000200
# define GET_EFLAGS(EFLAG_VAR) asm volatile ("pushfl; popl %0" : "=g" (EFLAG_VAR))


/*中断门描述符结构体*/
struct gate_desc {
    uint16_t func_offset_low_word;
    uint16_t selector;
    uint8_t dcount; //此项为双字计数字段，是门描述符中的第 4 字节
                    //此项固定值，不用考虑
    uint8_t attribute;
    uint16_t func_offset_high_word;
};

/**
 * 中断的名称.
 */ 
char* intr_name[IDT_DESC_CNT];   //用于保存异常的名字
intr_handler idt_table[IDT_DESC_CNT];
//定义中断处理程序数组，在 kernel.S 中定义的 intrXXentry 
//只是中断处理程序的入口，最终调用的是 ide_table 中的处理程序
extern intr_handler intr_entry_table[IDT_DESC_CNT];
//声明引用定义在 kernel.S 中的中断处理函数入口数组

static void init_custom_handler_name();
static void make_idt_desc(struct gate_desc* p_gdesc, uint8_t attr, intr_handler function);
static struct gate_desc idt[IDT_DESC_CNT];  // idt 是中断描述符表
                                            //本质上就是个中断门描述符数组

/**
 * 开中断并返回之前的状态.
 */ 
enum intr_status intr_enable() {
    enum intr_status old_status;
    if (INTR_ON == intr_get_status()) {
        old_status = INTR_ON;
	return old_status;
    }

    old_status = INTR_OFF;
    asm volatile ("sti");  // 开中断，sti 指令将 IF 位置 1
    return old_status;
}

/**
 * 关中断并返回之前的状态.
 */
enum intr_status intr_disable() {
    enum intr_status old_status;
    if (INTR_OFF == intr_get_status()) {
        old_status = INTR_OFF;
        return old_status;
    }

    old_status = INTR_ON;
    asm volatile ("cli" : : : "memory");  // 关中断，cli 指令将 IF 位置 0
    return old_status;
}

/** 
 * 将中断状态设置为 status 
 */

enum intr_status intr_set_status(enum intr_status status) {
    return status & INTR_ON ? intr_enable() : intr_disable();
}

/**
 * 获取中断状态.
 */ 
enum intr_status intr_get_status() {
    uint32_t eflags = 0;
    GET_EFLAGS(eflags);
    return (EFLAGS_IF & eflags) ? INTR_ON : INTR_OFF;
}


/**
 * 通用的中断处理函数.
 */ 
static void general_intr_handler(uint8_t vec_nr) {
    if (vec_nr == 0x27 || vec_nr == 0x2f) {
        // 伪中断，无需处理
        return;
    }
    put_str("int vector: 0x");
    put_int(vec_nr);
    put_char('\n');
}

/**
 * 通用(默认)的异常/中断处理器注册.
 */
static void exception_handler_init(void) {
    int i;
    for (i = 0; i < IDT_DESC_CNT; i++) {
        idt_table[i] = general_intr_handler; 
        //idt_table 数组中的函数是在进入中断后根据中断向量号调用的
        intr_name[i] = "unknown";
    }

    init_custom_handler_name();
}

/**
 * 设置需要自定义的中断名称.
 */ 
static void init_custom_handler_name() {
    intr_name[0] = "#DE Divide Error";
    intr_name[1] = "#DB Debug Exception";
    intr_name[2] = "NMI Interrupt";
    intr_name[3] = "#BP Breakpoint Exception";
    intr_name[4] = "#OF Overflow Exception";
    intr_name[5] = "#BR BOUND Range Exceeded Exception";
    intr_name[6] = "#UD Invalid Opcode Exception";
    intr_name[7] = "#NM Device Not Available Exception";
    intr_name[8] = "#DF Double Fault Exception";
    intr_name[9] = "Coprocessor Segment Overrun";
    intr_name[10] = "#TS Invalid TSS Exception";
    intr_name[11] = "#NP Segment Not Present";
    intr_name[12] = "#SS Stack Fault Exception";
    intr_name[13] = "#GP General Protection Exception";
    intr_name[14] = "#PF Page-Fault Exception";
    intr_name[16] = "#MF 0x87 FPU Floating-Point Error";
    intr_name[17] = "#AC Alignment Check Exception";
    intr_name[18] = "#MC Machine-Check Exception";
    intr_name[19] = "#XF SIMD Floating-Point Exception";
}

/**
 * 创建中断门描述符.
 */ 
static void make_idt_desc(struct gate_desc* p_gdesc, uint8_t attr, intr_handler function) {
    p_gdesc->func_offset_low_word = (uint32_t) function & 0x0000FFFF;
    p_gdesc->selector = SELECTOR_K_CODE;
    p_gdesc->dcount = 0;
    p_gdesc->attribute = attr;
    p_gdesc->func_offset_high_word = ((uint32_t) function & 0xFFFF0000) >> 16;
}

/**
 * 初始化中断描述符表.
 */ 
static void idt_desc_init(void) {
    int i;
    for (i = 0; i < IDT_DESC_CNT; i++) {
        make_idt_desc(&idt[i], IDT_DESC_ATTR_DPL0, intr_entry_table[i]);
    }
    put_str("idt_desc_init done.\n");
}

static void pic_init(void) {
    // 初始化主片
    outb(PIC_M_CTRL, 0x11); // ICW1: 边沿触发,级联 8259, 需要 ICW4
    outb(PIC_M_DATA, 0x20); // ICW2: 起始中断向量号为 0x20
                            // 也就是 IR[0-7] 为 0x20 ～ 0x27
    outb(PIC_M_DATA, 0x04); // ICW3: IR2 接从片
    outb(PIC_M_DATA, 0x01); // ICW4: 8086 模式, 正常 EOI

    outb(PIC_S_CTRL, 0x11); // ICW1: 边沿触发,级联 8259, 需要 ICW4
    outb(PIC_S_DATA, 0x28); // ICW2: 起始中断向量号为 0x28
                            // 也就是 IR[8-15]为 0x28 ～ 0x2F
    outb(PIC_S_DATA, 0x02); // ICW3: 设置从片连接到主片的 IR2 引脚
    outb(PIC_S_DATA, 0x01); // ICW4: 8086 模式, 正常 EOI
    /*打开主片上 IR0,也就是目前只接受时钟产生的中断 */
    outb(PIC_M_DATA, 0xfe);
    outb(PIC_S_DATA, 0xff);

    put_str("pic_init done.\n");
}

/*完成有关中断的所有初始化工作*/
void idt_init() {
    put_str("idt_init start.\n");
    idt_desc_init();  // 初始化中断描述符表
    exception_handler_init();
    pic_init();       // 初始化 8259A

    // 加载idt
    uint64_t idt_operand = ((sizeof(idt) - 1) | ((uint64_t) ((uint32_t) idt << 16)));
    asm volatile ("lidt %0" : : "m" (idt_operand));
    put_str("idt_init done.\n");
}

interrupt.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ifndef _KERNEL_INTERRUPT_H
# define _KERNEL_INTERRUPT_H

# include "stdint.h"

typedef void* intr_handler;

void idt_init(void);

/**
 * 中断状态.
 */ 
enum intr_status {  
    INTR_OFF,       
    INTR_ON
};

enum intr_status intr_get_status(void);
enum intr_status intr_set_status(enum intr_status);
enum intr_status intr_enable(void);
enum intr_status intr_disable(void);

# endif

为了调试方便我们新增加了断言(ASSERT)，其核心思想是若断言通过则什么都不做，若不通过则用循环实现等待，打印错误信息，见debug.c和debug.h

debug.c

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
# include "debug.h"
# include "kernel/print.h"
# include "interrupt.h"

void panic_spin(char* filename, int line, const char* func, const char* condition) {
    intr_disable();

    put_str("Something wrong...");
    
    put_str("FileName: ");
    put_str(filename);
    put_char('\n');

    put_str("Line: ");
    put_int(line);
    put_char('\n');

    put_str("Function: ");
    put_str(func);
    put_char('\n');

    put_str("Condition: ");
    put_str(condition);
    put_char('\n');

    while (1);
}

debug.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# ifndef _KERNEL_DEBUG_H
# define _KERNEL_DEBUG_H

void panic_spin(char* filename, int line, const char* func, const char* condition);

/**
 * 当断言被触发时调用.
 * _FILE_: 内置宏,表示调用的文件名
 * _LINE_: 内置宏,被编译文件的行号
 * _func_: 内置宏: 被编译的函数名
 * _VA_ARGS_: 函数调用参数
 */ 
# define PANIC(...) panic_spin (__FILE__, __LINE__, __func__, __VA_ARGS__)

# ifdef NDEBUG
    # define ASSERT(CONDITION) ((void) 0)
# else
    # define ASSERT(CONDITION) \
    if (CONDITION) { \
    } else { \
        PANIC(#CONDITION); \
    }
# endif
# endif

当前目录

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
.
├── boot
│   ├── include
│   │   └── boot.inc
│   ├── loader.bin
│   ├── loader.S
│   ├── mbr.bin
│   └── mbr.S
├── build
│   ├── init.o
│   ├── interrupt.o
│   ├── kernel.bin
│   ├── kernel.o
│   ├── main.o
│   ├── print.o
│   └── timer.o
│   └── debug.o
├── device
│   ├── timer.c
│   └── timer.h
├── kernel
│   ├── global.h
│   ├── init.c
│   ├── init.h
│   ├── interrupt.c
│   ├── interrupt.h
│   ├── kernel.S
│   └── main.c
│   └── debug.c
│   └── debug.h
└── lib
    ├── kernel
    │   ├── io.h
    │   ├── print.h
    │   ├── print.o
    │   └── print.S
    ├── stdint.h
    └── user

main.c中对其进行测试

1
2
3
4
5
6
7
8
9
10
#include "print.h"
#include "init.h"
#include "debug.h"

void main(void) {
   put_str("Welcome to TJ's kernel\n");
   init_all();
   ASSERT(1==2); // 测试断言
   while(1);
}

命令

1
2
--sudo make all
--sudo bin/bochs -f bochsrc.disk

运行结果

image-20210225102247898

实现字符串操作函数

在lib目录下用string.c实现对字符串的一些操作函数，比较好理解就不多解释了，代码如下

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
# include "global.h"
# include "debug.h"

/**
 * 同C类库同名函数.
 */ 
void memset(void* address, uint8_t value, uint32_t size) {
    ASSERT(address != NULL);
    
    uint8_t* addr = (uint8_t*) address;
    while (size-- > 0) {
        *addr++ = value;
    }
}

/**
 * 内存拷贝.
 */ 
void memcpy(void* dst, const void* src, uint32_t size) {
    ASSERT(dst != NULL && src != NULL);
    
    uint8_t* _dst = (uint8_t*) dst;
    const uint8_t* _src = (uint8_t*) src;
    while (size-- > 0) {
        *_dst++ = _src++;
    }
}

/**
 * 字符串比较,如果左边大于右边,返回1,相等返回0,否则-1.
 */ 
int memcmp(const void* left, const void* right, uint32_t size) {
    ASSERT(left != NULL && right != NULL);

    const uint8_t* _left = (uint8_t*) left;
    const uint8_t* _right = (uint8_t*) right;
    while (size-- > 0 && *_left++ == *_right);
    if (size == 0); 
        return 0;
    return (*_left > *_right ? 1 : -1);
}

char* strcpy(char* dst, const char* src) {
    ASSERT(dst != NULL && src != NULL);

    char* head = dst;
    while ((*dst++ = *src++));
    return head;
}

uint32_t strlen(const char* str) {
    ASSERT(str != NULL);

    uint32_t count = 0;
    while (*str++) {
        ++count;
    }

    return count;
}

/**
 * 如果左边大于右边返回1.
 */ 
int8_t strcmp(const char* left, const char* right) {
    ASSERT(left != NULL && right != NULL);

    while (*left != 0 && *left == *right) {
        ++left;
        ++right;
    }
    return (*left < *right ? -1 : *left > *right);
}

char* strchr(const char* str, const uint8_t c) {
    ASSERT(str != NULL);

    uint8_t item;
    while ((item = *str) != 0) {
        if (item == c) {
            return (char*) str;
        }
        ++str;
    }
    return NULL;
}

/**
 * 倒序查找.
 */ 
char* strrchr(const char* str, const uint8_t c) {
    ASSERT(str != NULL);
    const char* last_pos = NULL;
    char item;
    while ((item = *str) != 0) {
        if (item == c) {
            last_pos = str;
        }
    }
    return last_pos;
}

/**
 * 字符串拼接.
 */ 
char* strcat(char* dst, const char* src) {
    ASSERT(dst != NULL && src != NULL);

    const char* head = dst;
    while (*dst++);
    --dst;
    while ((*dst++ = *src++));
    return head;
}

/**
 * 统计制定的字符在字符串中出现的次数.
 */ 
uint32_t strchrs(const char* str, const uint8_t c) {
    ASSERT(str != NULL);

    uint32_t result = 0;
    char item;
    while ((item = *str) != 0) {
        if (item == c) {
            ++result;
        }
        ++str;
    }
    return result;
}

string.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# ifndef _LIB_STRING_H
# define _LIB_STRING_H

# include "global.h"
# include "debug.h"

void memset(void* address, uint8_t value, uint32_t size);
void memcpy(void* dst, const void* src, uint32_t size);
int memcmp(const void* left, const void* right, uint32_t size);
char* strcpy(char* dst, const char* src);
uint32_t strlen(const char* str);
int8_t strcmp(const char* left, const char* right);
char* strchr(const char* str, const uint8_t c);
char* strrchr(const char* str, const uint8_t c);
char* strcat(char* dst, const char* src);
uint32_t strchrs(const char* str, const uint8_t c);

# endif

位图 bitmap

位图简介

位图包含两个概念：位和图。

位是指 bit，即字节中的位，1 字节中有 8 个位。图是指 map，就是映射的意思，映射。

image-20210225110016024

总结一下，位图相当于一组资源的映射。位图中的每一位和被管理的单位资源都是一对一的关系，故位图主要用于管理容量较大的资源。

位图用于实现资源管理，相当于一张表，表中为1表示占用，为0表示空闲，之后我们将其用来管理内存

位图的实现

在lib/kernel目录下新增bitmap.h与bitmap.c，代码如下，bitmap结构比较简单，只有两个成员：指针bits 和 位图的字节长度btmp_bytes_len

bitmap.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef _LIB_KERNEL_BITMAP_H
#define _LIB_KERNEL_BITMAP_H

# include "global.h"
# define BITMAP_MASK 1

struct bitmap {
    uint32_t btmp_bytes_len;
    uint8_t* bits;
};

void bitmap_init(struct bitmap* btmap);
int bitmap_scan_test(struct bitmap* btmap, uint32_t bit_idx);
int bitmap_scan(struct bitmap* btmap, uint32_t cnt);
void bitmap_set(struct bitmap* btmap, uint32_t index, int8_t value);

#endif

bitmap.c

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# include "bitmap.h"
# include "stdint.h"
# include "string.h"
# include "kernel/print.h"
# include "interrupt.h"
# include "debug.h"

void bitmap_init(struct bitmap* btmap) {
    memset(btmap->bits, 0, btmap->btmp_bytes_len);
}

/**
 * 检测指定位是否为1,如果是,返回1.
 */
int bitmap_scan_test(struct bitmap* btmap, uint32_t index) {
    uint32_t byte_index = (index / 8);
    uint32_t bit_odd = byte_index % 8;

    return (btmap->bits[byte_index] & BITMAP_MASK << bit_odd);
}

/**
 * 在位图中申请连续的cnt个位.
 */
int bitmap_scan(struct bitmap* btmap, uint32_t cnt) {
    uint32_t idx_byte = 0;

    // 以字节为单位进行查找
    while ((0xff == btmap->bits[idx_byte]) && idx_byte < btmap->btmp_bytes_len) {
        ++idx_byte;
    }

    // 没有找到
    if (idx_byte == btmap->btmp_bytes_len) {
        return -1;
    }

    // 找到了一个字节不全为1,那么在字节内部再次进行查找具体的起使位
    int idx_bit = 0;
    while ((uint8_t) BITMAP_MASK << idx_bit & btmap->bits[idx_byte]) {
        ++idx_bit;
    }

    // 起始位
    int bit_idx_start = (idx_byte * 8 + idx_bit);
    if (cnt == 1) {
        return bit_idx_start;
    }

    uint32_t bit_left = (btmap->btmp_bytes_len * 8 - bit_idx_start);
    uint32_t count = 1;s
    uint32_t next_bit = bit_idx_start + 1;

    bit_idx_start = -1;
    while (bit_left-- > 0) {
        if (!(bitmap_scan_test(btmap, next_bit))) {
            ++count;
        } else {
            count = 0;
        }
        if (count == cnt) {
            bit_idx_start = (next_bit - cnt + 1);
            break;
        }
        next_bit++;
    }

    return bit_idx_start;
}

void bitmap_set(struct bitmap* btmap, uint32_t index, int8_t value) {
    ASSERT(value == 0 || value == 1);

    uint32_t byte_index = index / 8;
    uint32_t bit_odd = index % 8;

    if (value) {
        btmap->bits[byte_index] |= (BITMAP_MASK << bit_odd);
    } else {
        btmap->bits[byte_index] &= ~(BITMAP_MASK << bit_odd);
    }
}

内存管理

内存池规划

根据之前的铺垫，为了实现内存中用户和内核的区分，我们用位图实现对内存使用情况的记录，我们将物理内存划分为用户内存池和内核内存池，一页为4KB大小。

内核在申请空间的时候，先从内核自己的虚拟地址池中分配好虚拟地址再从内核物理地址池中分配物理内存，最后在内核自己的页表中将这两种地址建立好映射关系，内存就分配完成。

对用户进程来说，它向操作系统申请内存时，操作系统先从用户进程自己的虚拟地址分配虚拟地址，在从用户物理内存池中分配空闲的物理内存，用户物理内存池是被所有用户进程所共享的。最后在用户进程自己的页表中将这两种地址建立好映射关系。

image-20210225111603847

实现在kernel目录下新建memory.c和memory.h，虚拟内存池结构和物理内存池结构如下，物理内存多了一个记录大小的pool_size，因为虚拟地址是连续的4GB空间，相对而言空间非常大，而物理地址是有限的，所以不存在对虚拟地址大小的记录。

memory.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef __KERNEL_MEMORY_H 
#define __KERNEL_MEMORY_H 
#include "stdint.h" 
#include "bitmap.h" 

/* 虚拟地址池，用于虚拟地址管理 */ 
struct virtual_addr { 
	struct bitmap vaddr_bitmap; // 虚拟地址用到的位图结构
	uint32_t vaddr_start; // 虚拟地址起始地址
}; 

extern struct pool kernel_pool, user_pool; 
void mem_init(void); 
#endif

memory.c

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "memory.h" 
#include "stdint.h" 
#include "print.h" 

#define PG_SIZE 4096 

/************************ 位图地址 ***************************** 
* 因为 0xc009f000 是内核主线程栈顶，0xc009e000 是内核主线程的 pcb。
* 一个页框大小的位图可表示 128MB 内存，位图位置安排在地址 0xc009a000，
* 这样本系统最大支持 4 个页框的位图，即 512MB */ 
#define MEM_BITMAP_BASE 0xc009a000 
/******************************************************************/ 

/* 0xc0000000 是内核从虚拟地址 3G 起。
   0x100000 意指跨过低端 1MB 内存，使虚拟地址在逻辑上连续 */ 
#define K_HEAP_START 0xc0100000 

/* 内存池结构，生成两个实例用于管理内核内存池和用户内存池 */ 
struct pool { 
	struct bitmap pool_bitmap; //本内存池用到的位图结构，用于管理物理内存
	uint32_t phy_addr_start; // 本内存池所管理物理内存的起始地址
	uint32_t pool_size; // 本内存池字节容量
}; 

struct pool kernel_pool, user_pool; // 生成内核内存池和用户内存池
struct virtual_addr kernel_vaddr; // 此结构用来给内核分配虚拟地址

/* 初始化内存池 */ 
static void mem_pool_init(uint32_t all_mem) { 
    put_str(" mem_pool_init start\n"); 
    uint32_t page_table_size = PG_SIZE * 256;

    // 页表大小 = 1 页的页目录表 + 第 0 和第 768 个页目录项指向同一个页表 + 
    // 第 769～1022 个页目录项共指向 254 个页表，共 256 个页框
    uint32_t used_mem = page_table_size + 0x100000; 
    // 0x100000 为低端 1MB 内存
    uint32_t free_mem = all_mem - used_mem; 
    uint16_t all_free_pages = free_mem / PG_SIZE; 
    // 1 页为 4KB，不管总内存是不是 4k 的倍数
    // 对于以页为单位的内存分配策略，不足 1 页的内存不用考虑了

    uint16_t kernel_free_pages = all_free_pages / 2; 
    uint16_t user_free_pages = all_free_pages - kernel_free_pages; 

    /* 为简化位图操作，余数不处理，坏处是这样做会丢内存。
    好处是不用做内存的越界检查，因为位图表示的内存少于实际物理内存*/ 
    uint32_t kbm_length = kernel_free_pages / 8; 
    // Kernel BitMap 的长度，位图中的一位表示一页，以字节为单位
    uint32_t ubm_length = user_free_pages / 8; 
    // User BitMap 的长度

    uint32_t kp_start = used_mem; 
    // Kernel Pool start，内核内存池的起始地址
    uint32_t up_start = kp_start + kernel_free_pages * PG_SIZE; 
    // User Pool start，用户内存池的起始地址

    kernel_pool.phy_addr_start = kp_start; 
    user_pool.phy_addr_start = up_start; 

    kernel_pool.pool_size = kernel_free_pages * PG_SIZE; 
    user_pool.pool_size = user_free_pages * PG_SIZE; 

    kernel_pool.pool_bitmap.btmp_bytes_len = kbm_length; 
    user_pool.pool_bitmap.btmp_bytes_len = ubm_length; 

    /********* 内核内存池和用户内存池位图 *********** 
    * 位图是全局的数据，长度不固定。
    * 全局或静态的数组需要在编译时知道其长度，
    * 而我们需要根据总内存大小算出需要多少字节，
    * 所以改为指定一块内存来生成位图。
    * ************************************************/ 
    // 内核使用的最高地址是 0xc009f000，这是主线程的栈地址
    //（内核的大小预计为 70KB 左右）
    // 32MB 内存占用的位图是 2KB 
    //内核内存池的位图先定在 MEM_BITMAP_BASE(0xc009a000)处
    kernel_pool.pool_bitmap.bits = (void*)MEM_BITMAP_BASE; 

    /* 用户内存池的位图紧跟在内核内存池位图之后 */ 
    user_pool.pool_bitmap.bits = (void*)(MEM_BITMAP_BASE + kbm_length);

    /********************输出内存池信息**********************/ 
    put_str(" kernel_pool_bitmap_start:"); 
    put_int((int)kernel_pool.pool_bitmap.bits); 
    put_str(" kernel_pool_phy_addr_start:"); 
    put_int(kernel_pool.phy_addr_start); 
    put_str("\n"); 
    put_str("user_pool_bitmap_start:"); 
    put_int((int)user_pool.pool_bitmap.bits); 
    put_str(" user_pool_phy_addr_start:"); 
    put_int(user_pool.phy_addr_start); 
    put_str("\n"); 

    /* 将位图置 0*/ 
    bitmap_init(&kernel_pool.pool_bitmap); 
    bitmap_init(&user_pool.pool_bitmap); 

    /* 下面初始化内核虚拟地址的位图，按实际物理内存大小生成数组。*/ 
    kernel_vaddr.vaddr_bitmap.btmp_bytes_len = kbm_length; 
    // 用于维护内核堆的虚拟地址，所以要和内核内存池大小一致

    /* 位图的数组指向一块未使用的内存，
    目前定位在内核内存池和用户内存池之外*/ 
    kernel_vaddr.vaddr_bitmap.bits = (void*)(MEM_BITMAP_BASE + kbm_length + ubm_length); 

    kernel_vaddr.vaddr_start = K_HEAP_START; 
    bitmap_init(&kernel_vaddr.vaddr_bitmap); 
    put_str(" mem_pool_init done\n"); 
} 

/* 内存管理部分初始化入口 */ 
void mem_init() { 
	put_str("mem_init start\n"); 
	uint32_t mem_bytes_total = (*(uint32_t*)(0xb00)); 
	mem_pool_init(mem_bytes_total); // 初始化内存池
	put_str("mem_init done\n"); 
}

在前面创建页目录和页表的时候，我们将虚拟地址 0xc0000000~0xc00fffff 映射到了物理地址 0x0~0xfffff，0xc0000000 是内核空间的起始虚拟地址，这 1MB 空间做的对等映射。为了看起来使内存连续，所以这里内核堆空间的开始地址从 0xc0100000 开始，在之前的设计中，0xc009f000 为内核主线程的栈顶，0xc009e000 将作为主线程的 PCB 使用，那么在低端1MB的空间中，就只剩下0xc009a000~0xc009dfff这4 * 4KB的空间未使用，所以位图的地址就安排在 0xc009a000 处，这里还剩下四个页框的大小，所能表示的内存大小为512MB。

init.c 需要添加 mem_init()

1
2
3
4
5
6
7
8
9
10
11
# include "init.h"
# include "print.h"
# include "timer.h"
# include "memory.h"

void init_all() {
    put_str("init_all.\n");
    idt_init();
    timer_init();
    mem_init();
}

global.h 需要加个 NULL 的定义

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
#ifndef _KERNEL_GLOBAL_H
#define _KERNEL_GLOBAL_H

# include "stdint.h"

# define RPL0 0
# define RPL1 1
# define RPL2 2
# define RPL3 3

# define TI_GDT 0
# define TI_LDT 1

# define SELECTOR_K_CODE ((1 << 3) + (TI_GDT << 2) + RPL0)
# define SELECTOR_K_DATA ((2 << 3) + (TI_GDT << 2) + RPL0)
# define SELECTOR_K_STACK SELECTOR_K_DATA
# define SELECTOR_K_GS ((3 << 3) + (TI_GDT << 2) + RPL0)

/* IDT描述符属性 */
# define IDT_DESC_P 1
# define IDT_DESC_DPL0 0
# define IDT_DESC_DPL3 3
# define IDT_DESC_32_TYPE 0xE   // 32 位的门
# define IDT_DESC_16_TYPE 0x6   // 16 位的门

# define IDT_DESC_ATTR_DPL0 \
    ((IDT_DESC_P << 7) + (IDT_DESC_DPL0 << 5) + IDT_DESC_32_TYPE)

# define IDT_DESC_ATTR_DPL3 \
    ((IDT_DESC_P << 7) + (IDT_DESC_DPL3 << 5) + IDT_DESC_32_TYPE)

# define NULL 0

#endif

main.c 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
# include "print.h"
# include "init.h"
# include "debug.h"
# include "memory.h"

int main(void) {
    put_str("I am kernel.\n");
    init_all();
    put_str("Init done.\n");

    while (1);
    return 0;
}

需要修改 makefile 

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
BUILD_DIR = ./build
ENTRY_POINT = 0xc0001500
AS = nasm
CC = gcc
LD = ld
LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/
ASFLAGS = -f elf
CFLAGS = -m32 -fno-stack-protector -Wall $(LIB) -c -fno-builtin -W -Wstrict-prototypes \
         -Wmissing-prototypes
LDFLAGS = -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
      $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/string.o

##############     c代码编译     ###############
$(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
        lib/stdint.h kernel/init.h kernel/memory.h kernel/debug.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
        lib/stdint.h kernel/interrupt.h device/timer.h kernel/memory.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
        lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/stdint.h\
        lib/kernel/io.h lib/kernel/print.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
        lib/kernel/print.h lib/stdint.h kernel/interrupt.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/string.o: lib/string.c lib/string.h \
        kernel/global.h kernel/debug.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/bitmap.o: lib/bitmap.c lib/bitmap.h \
        kernel/debug.h kernel/interrupt.h lib/stdint.h
        $(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h lib/bitmap.h \
        lib/stdint.h lib/kernel/print.h kernel/debug.h lib/string.h
        $(CC) $(CFLAGS) $< -o $@


##############    汇编代码编译    ###############
$(BUILD_DIR)/kernel.o: kernel/kernel.S
        $(AS) $(ASFLAGS) $< -o $@
$(BUILD_DIR)/print.o: lib/kernel/print.S
        $(AS) $(ASFLAGS) $< -o $@

##############    链接所有目标文件    #############
$(BUILD_DIR)/kernel.bin: $(OBJS)
        $(LD) $(LDFLAGS) $^ -o $@

.PHONY : mk_dir hd clean all

# ubantu中需要将dash修改为bash运行
# ls -al /bin/sh若结果为/bin/sh -> dash
# 执行sudo dpkg-reconfigure dash选择No即可
mk_dir:
        if [[ ! -d $(BUILD_DIR) ]];then mkdir $(BUILD_DIR);fi

hd:
        dd if=$(BUILD_DIR)/kernel.bin \
           of=/home/fyz/sc/bochs-2.6.2/hd60M.img \
           bs=512 count=200 seek=9 conv=notrunc

clean:
        cd $(BUILD_DIR) && rm -f ./*

build: $(BUILD_DIR)/kernel.bin

all: mk_dir build hd
1
2
--sudo make all
--sudo bin/bochs -f bochsrc.disk

运行结果

image-20210225143014643

分配页内存

接下来就是实现对内存的分配，首先复习一下32位虚拟地址的转换过程：

  1. 高 10 位是页目录项 pde 的索引，用于在页目录表中定位 pde ，细节是处理器获取高 10 位后自动将其乘以 4，再加上页目录表的物理地址，这样便得到了 pde 索引对应的 pde 所在的物理地址，然后自动在该物理地址中，即该 pde 中，获取保存的页表物理地址。
  2. 中间 10 位是页表项 pte 索引，用于在页表中定位 pte 。细节是处理器获取中间 10 位后自动将其乘以 4，再加上第一步中得到的页表的物理地址，这样便得到了 pte 索引对应的 pte 所在的物理地址，然后自动在该物理地址 (该 pte) 中获取保存的普通物理页的物理地址。
  3. 低 12 位是物理页内的偏移 ，页大小是 4KB, 12 位可寻址的范围正好是 4KB，因此处理器便直接把低 12 位作为第二步中获取的物理页的偏移量，无需乘以 4。用物理页的物理地址加上这低 12 位的和便是这 32 位虚拟地址最终落向的物理地址。

比如访问虚拟地址0x00c03123，拆分步骤如下

1
2
3
4
0x00c03123 => 16进制
0000 0000 1100 0000 0011 0001 0010 0011 => 2进制
0000000011 0000000011 000100100011      => 重新组合为 10+10+12
pde 3      pte 3      偏移 123

整个过程如下图所示

image-20210225144142146

32位地址在上面转换之后则落向物理地址，内存分配的过程：

  1. 在虚拟内存池中申请n个虚拟页
  2. 在物理内存池中分配物理页
  3. 在页表中添加虚拟地址与物理地址的映射关系

接下来就是一步一步在memory文件中增加函数

在虚拟内存池中申请n个虚拟页

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 在pf表示的虚拟内存池中申请pg_cnt个虚拟页,
 * 成功则返回虚拟页的起始地址, 失败则返回NULL */
static void* vaddr_get(enum pool_flags pf, uint32_t pg_cnt) {
   int vaddr_start = 0, bit_idx_start = -1;
   uint32_t cnt = 0;
   if (pf == PF_KERNEL) { //若为内核内存池
       bit_idx_start  = bitmap_scan(&kernel_vaddr.vaddr_bitmap, pg_cnt); // 扫描虚拟地址池
       if (bit_idx_start == -1) { // 返回-1则退出
           return NULL;
      }
      while(cnt < pg_cnt) {
		  bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 1); // 循环逐位置一
      }
      vaddr_start = kernel_vaddr.vaddr_start + bit_idx_start * PG_SIZE; // 将bit_idx_start转换为虚拟地址
   } else {	
   // 用户内存池,将来实现用户进程再补充
   }
   return (void*)vaddr_start; // 返回指针
}

在物理内存池中分配物理页

这个函数比较关键，主要是对位图的扫描和记录，然后根据位图索引返回分配的物理地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 在m_pool指向的物理内存池中分配一个物理页
static void *palloc(struct pool *m_pool)
{
    int bit_idx = bitmap_scan(&m_pool->pool_bitmap, 1);
    if(bit_idx == -1)
    {
        return NULL;
    }

    bitmap_set(&m_pool->pool_bitmap, bit_idx, 1);
    uint32_t page_phyaddr = bit_idx * PG_SIZE + m_pool->phy_addr_start;

    return (void*)page_phyaddr;
}

在页表中添加虚拟地址与物理地址的映射关系

再次复习一下32位虚拟地址到物理地址的转换，我们后面实现pde和pte访问就是用的这个原理

  1. 首先通过高10位的pde索引，找到页表的物理地址
  2. 其次通过中间10位的pte索引，得到物理页的物理地址
  3. 最后把低12位作为物理页的页内偏移，加上物理页的物理地址，即为最终的物理地址

下面是通过虚拟地址访问pte和pde的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 得到虚拟地址vaddr对应的pte指针*/
uint32_t* pte_ptr(uint32_t vaddr) {
   /* 先访问到页表自己 + \
    * 再用页目录项pde(页目录内页表的索引)做为pte的索引访问到页表 + \
    * 再用pte的索引做为页内偏移*/
   	uint32_t* pte = (uint32_t*)(0xffc00000 + \ // 最后一个页目录项保存的是页目录表物理地址，高十位指向最后一个页目录表项
                                              // 也就是第1023个pde，换算成十进制就是0x3ff再移到高10位就是0xffc00000
	 ((vaddr & 0xffc00000) >> 10) + \        
	 PTE_IDX(vaddr) * 4);
   return pte;
}

/* 得到虚拟地址vaddr对应的pde的指针 */
uint32_t* pde_ptr(uint32_t vaddr) {
   /* 0xfffff是用来访问到页表本身所在的地址 */
   uint32_t* pde = (uint32_t*)((0xfffff000) + PDE_IDX(vaddr) * 4);
   return pde;
}

在m_pool处申请物理页的函数

1
2
3
4
5
6
7
8
9
10
11
12
/* 在m_pool指向的物理内存池中分配1个物理页,
 * 成功则返回页框的物理地址,失败则返回NULL */
static void* palloc(struct pool* m_pool) {
   /* 扫描或设置位图要保证原子操作 */
   int bit_idx = bitmap_scan(&m_pool->pool_bitmap, 1);    // 找一个物理页面
   if (bit_idx == -1 ) {
      return NULL;
   }
   bitmap_set(&m_pool->pool_bitmap, bit_idx, 1);	// 将此位bit_idx置1
   uint32_t page_phyaddr = ((bit_idx * PG_SIZE) + m_pool->phy_addr_start); // page_phyaddr用于保存分配的物理页地址
   return (void*)page_phyaddr;
}

添加虚拟地址与物理地址的映射函数

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
/* 页表中添加虚拟地址_vaddr与物理地址_page_phyaddr的映射 */
static void page_table_add(void* _vaddr, void* _page_phyaddr) {
   uint32_t vaddr = (uint32_t)_vaddr, page_phyaddr = (uint32_t)_page_phyaddr;
   uint32_t* pde = pde_ptr(vaddr);
   uint32_t* pte = pte_ptr(vaddr);

/************************   注意   *************************
 * 执行*pte,会访问到空的pde。所以确保pde创建完成后才能执行*pte,
 * 否则会引发page_fault。因此在*pde为0时,*pte只能出现在下面else语句块中的*pde后面。
 * *********************************************************/
   /* 先在页目录内判断目录项的P位，若为1,则表示该表已存在 */
   if (*pde & 0x00000001) {	 // 页目录项和页表项的第0位为P,此处判断目录项是否存在
      ASSERT(!(*pte & 0x00000001));

      if (!(*pte & 0x00000001)) {   // 只要是创建页表,pte就应该不存在,多判断一下放心
		 *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);    // US=1,RW=1,P=1
      } else {			    //应该不会执行到这，因为上面的ASSERT会先执行。
	 	 PANIC("pte repeat");
	 	 *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);      // US=1,RW=1,P=1
      }
   } else {			    // 页目录项不存在,所以要先创建页目录再创建页表项.
      /* 页表中用到的页框一律从内核空间分配 */
      uint32_t pde_phyaddr = (uint32_t)palloc(&kernel_pool);

      *pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);

      /* 分配到的物理页地址pde_phyaddr对应的物理内存清0,
       * 避免里面的陈旧数据变成了页表项,从而让页表混乱.
       * 访问到pde对应的物理地址,用pte取高20位便可.
       * 因为pte是基于该pde对应的物理地址内再寻址,
       * 把低12位置0便是该pde对应的物理页的起始*/
      memset((void*)((int)pte & 0xfffff000), 0, PG_SIZE);
         
      ASSERT(!(*pte & 0x00000001));
      *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);      // US=1,RW=1,P=1
   }
}

malloc_page函数负责申请虚拟地址并分配物理地址、建立映射，大致步骤如下

  1. 通过vaddr_get在虚拟内存池中申请虚拟地址
  2. 通过palloc在物理内存池中申请物理页
  3. 通过page_table_add将以上两步得到的结果在页表中映射
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
/* 分配pg_cnt个页空间,成功则返回起始虚拟地址,失败时返回NULL */
void* malloc_page(enum pool_flags pf, uint32_t pg_cnt) {
	ASSERT(pg_cnt > 0 && pg_cnt < 3840); //15MB来限制，pg_cnt < 15*1024*1024/4096 = 3840页
/***********   malloc_page的原理是三个动作的合成:   ***********
      1通过vaddr_get在虚拟内存池中申请虚拟地址
      2通过palloc在物理内存池中申请物理页
      3通过page_table_add将以上得到的虚拟地址和物理地址在页表中完成映射
***************************************************************/
    void* vaddr_start = vaddr_get(pf, pg_cnt);
    if (vaddr_start == NULL) {
        return NULL;
    }

    uint32_t vaddr = (uint32_t)vaddr_start, cnt = pg_cnt;
    struct pool* mem_pool = pf & PF_KERNEL ? &kernel_pool : &user_pool; // 内核池还是用户池

    /* 因为虚拟地址是连续的,但物理地址可以是不连续的,所以逐个做映射*/
    while (cnt-- > 0) {
        void* page_phyaddr = palloc(mem_pool);
        if (page_phyaddr == NULL) {  // 失败时要将曾经已申请的虚拟地址和物理页全部回滚，在将来完成内存回收时再补充
            return NULL;
        }
        page_table_add((void*)vaddr, page_phyaddr); // 在页表中做映射 
        vaddr += PG_SIZE;		 // 下一个虚拟页
    }
    return vaddr_start;
}

最后一个函数负责在物理内存池中申请 pg_cnt 页内存

1
2
3
4
5
6
7
8
/* 从内核物理内存池中申请pg_cnt页内存,成功则返回其虚拟地址,失败则返回NULL */
void* get_kernel_pages(uint32_t pg_cnt) {
   void* vaddr =  malloc_page(PF_KERNEL, pg_cnt);
   if (vaddr != NULL) {	   // 若分配的地址不为空,将页框清0后返回
      memset(vaddr, 0, pg_cnt * PG_SIZE);
   }
   return vaddr;
}

memery.h

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
# ifndef _KERNEL_MEMORY_H
# define _KERNEL_MEMORY_H

# include "stdint.h"
# include "bitmap.h"

// 存在标志
# define PG_P_1 1
# define PG_P_0 0
// 只读
# define PG_RW_R 0
// 可写
# define PG_RW_W 2
// 系统级
# define PG_US_S 0
# define PG_US_U 4

/**
 * 内存池类型标志.
 */ 
enum pool_flags {
    // 内核类型
    PF_KERNEL = 1,
    PF_USER = 2
};

struct virtual_addr {
    struct bitmap vaddr_bitmap;
    // 虚拟内存的起始地址
    uint32_t vaddr_start;
};

extern struct pool kernel_pool, user_pool;
void mem_init(void);
void* get_kernel_pages(uint32_t page_count);
void* malloc_page(enum pool_flags pf, uint32_t page_count);

# endif

memery.c

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
# include "memory.h"
# include "stdint.h"
# include "kernel/print.h"
# include "string.h"
# include "debug.h"

# define PAGE_SIZE 4096

// 位图地址
# define MEM_BITMAP_BASE 0xc009a000

// 内核使用的起始虚拟地址
// 跳过低端1MB内存，中间10为代表页表项偏移，即0x100，即256 * 4KB = 1MB
# define K_HEAD_START 0xc0100000

// 获取高10位页目录项标记
# define PDE_INDEX(addr) ((addr & 0xffc00000) >> 22)
// 获取中间10位页表标记 
# define PTE_INDEX(addr) ((addr & 0x003ff000) >> 12) 

// static functions declarations
static void printKernelPoolInfo(struct pool p);
static void printUserPoolInfo(struct pool p);
static void* vaddr_get(enum pool_flags pf, uint32_t pg_count);
static uint32_t* pte_ptr(uint32_t vaddr);
static uint32_t* pde_ptr(uint32_t vaddr);
static void* palloc(struct pool* m_pool);
static void page_table_add(void* _vaddr, void* _page_phyaddr);

struct pool {
    struct bitmap pool_bitmap;
    uint32_t phy_addr_start;
    uint32_t pool_size;
};

struct pool kernel_pool, user_pool;
struct virtual_addr kernel_addr;

/**
 * 初始化内存池.
 */ 
static void mem_pool_init(uint32_t all_memory) {
    put_str("Start init Memory pool...\n");

    // 页表(一级和二级)占用的内存大小，256的由来:
    // 一页的页目录，页目录的第0和第768项指向一个页表，此页表分配了低端1MB内存(其实此页表中也只是使用了256个表项)，
    // 剩余的254个页目录项实际没有分配对应的真实页表，但是需要为内核预留分配的空间
    uint32_t page_table_size = PAGE_SIZE * 256;

    // 已经使用的内存为: 低端1MB内存 + 现有的页表和页目录占据的空间
    uint32_t used_mem = (page_table_size + 0x100000);

    uint32_t free_mem = (all_memory - used_mem);
    uint16_t free_pages = free_mem / PAGE_SIZE;

    uint16_t kernel_free_pages = (free_pages >> 1);
    uint16_t user_free_pages = (free_pages - kernel_free_pages);

    // 内核空间bitmap长度(字节)，每一位代表一页
    uint32_t kernel_bitmap_length = kernel_free_pages / 8;
    uint32_t user_bitmap_length = user_free_pages / 8;

    // 内核内存池起始物理地址，注意内核的虚拟地址占据地址空间的顶端，但是实际映射的物理地址是在这里
    uint32_t kernel_pool_start = used_mem;
    uint32_t user_pool_start = (kernel_pool_start + kernel_free_pages * PAGE_SIZE);

    kernel_pool.phy_addr_start = kernel_pool_start;
    user_pool.phy_addr_start = user_pool_start;

    kernel_pool.pool_size = kernel_free_pages * PAGE_SIZE;
    user_pool.pool_size = user_free_pages * PAGE_SIZE;

    kernel_pool.pool_bitmap.btmp_bytes_len = kernel_bitmap_length;
    user_pool.pool_bitmap.btmp_bytes_len = user_bitmap_length;

    // 内核bitmap和user bitmap bit数组的起始地址
    kernel_pool.pool_bitmap.bits = (void*) MEM_BITMAP_BASE;
    user_pool.pool_bitmap.bits = (void*) (MEM_BITMAP_BASE + kernel_bitmap_length);

    printKernelPoolInfo(kernel_pool);
    printUserPoolInfo(user_pool);

    bitmap_init(&kernel_pool.pool_bitmap);
    bitmap_init(&user_pool.pool_bitmap);

    kernel_addr.vaddr_bitmap.btmp_bytes_len = kernel_bitmap_length;
    // 内核虚拟地址池仍然保存在低端内存以内
    kernel_addr.vaddr_bitmap.bits = (void*) (MEM_BITMAP_BASE + kernel_bitmap_length + user_bitmap_length);
    kernel_addr.vaddr_start = K_HEAD_START;

    bitmap_init(&kernel_addr.vaddr_bitmap);
    put_str("Init memory pool done.\n");
}

static void printKernelPoolInfo(struct pool p) {
    put_str("Kernel pool bitmap address: ");
    put_int(p.pool_bitmap.bits);
    put_str("; Kernel pool physical address: ");
    put_int(p.phy_addr_start);
    put_char('\n');
}

static void printUserPoolInfo(struct pool p) {
    put_str("User pool bitmap address: ");
    put_int(p.pool_bitmap.bits);
    put_str("; User pool physical address: ");
    put_int(p.phy_addr_start);
    put_char('\n');
}

/**
 * 申请指定个数的虚拟页.返回虚拟页的起始地址，失败返回NULL.
 */ 
static void* vaddr_get(enum pool_flags pf, uint32_t pg_count) {
    int vaddr_start = 0, bit_idx_start = -1;
    uint32_t count = 0;

    if (pf == PF_KERNEL) {
        bit_idx_start = bitmap_scan(&kernel_addr.vaddr_bitmap, pg_count);
        if (bit_idx_start == -1) {
            // 申请失败，虚拟内存不足
            return NULL;
        }

        // 修改bitmap，占用虚拟内存
        while (count < pg_count) {
            bitmap_set(&kernel_addr.vaddr_bitmap, (bit_idx_start + count), 1);
            ++count;
        }

        vaddr_start = (kernel_addr.vaddr_start + bit_idx_start * PAGE_SIZE); 
    } else {
        // 用户内存分配暂不支持
    }
    return (void*) vaddr_start;
}

/**
 * 得到虚拟地址对应的PTE的指针.
 */ 
static uint32_t* pte_ptr(uint32_t vaddr) {
    return (uint32_t*) (0xffc00000 + ((vaddr & 0xffc00000) >> 10) + (PTE_INDEX(vaddr) << 2));
}

/**
 * 得到虚拟地址对应的PDE指针.
 */ 
static uint32_t* pde_ptr(uint32_t vaddr) {
    return (uint32_t*) ((0xfffff000) + (PDE_INDEX(vaddr) << 2));
}

/**
 * 在给定的物理内存池中分配一个物理页，返回其物理地址.
 */ 
static void* palloc(struct pool* m_pool) {
    int bit_index = bitmap_scan(&m_pool->pool_bitmap, 1);
    if (bit_index == -1) {
        return NULL;
    }

    bitmap_set(&m_pool->pool_bitmap, bit_index, 1);
    uint32_t page_phyaddr = ((bit_index * PAGE_SIZE) + m_pool->phy_addr_start);
    return (void*) page_phyaddr;
}

/**
 * 通过页表建立虚拟页与物理页的映射关系.
 */ 
static void page_table_add(void* _vaddr, void* _page_phyaddr) {
    uint32_t vaddr = (uint32_t) _vaddr, page_phyaddr = (uint32_t) _page_phyaddr;
    uint32_t* pde = pde_ptr(vaddr); uint32_t* pte = pte_ptr(vaddr);

    if (*pde & 0x00000001) {
        // 页目录项已经存在
        if (!(*pte & 0x00000001)) {
            // 物理页必定不存在，使页表项指向我们新分配的物理页
            *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);
        }
    } else {
        // 新分配一个物理页作为页表
        uint32_t pde_phyaddr = (uint32_t) palloc(&kernel_pool);
        *pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);
        // 清理物理页
        memset((void*) ((int) pte & 0xfffff000), 0, PAGE_SIZE);
        *pte = (page_phyaddr | PG_US_U | PG_RW_W | PG_P_1);
    }
}

/**
 * 分配page_count个页空间，自动建立虚拟页与物理页的映射.
 */ 
void* malloc_page(enum pool_flags pf, uint32_t page_count) {
    ASSERT(page_count > 0 && page_count < 3840);

    // 在虚拟地址池中申请虚拟内存
    void* vaddr_start = vaddr_get(pf, page_count);
    if (vaddr_start == NULL) {
        return NULL;
    }

    uint32_t vaddr = (uint32_t) vaddr_start, count = page_count;
    struct pool* mem_pool = (pf & PF_KERNEL) ? &kernel_pool : &user_pool;

    // 物理页不必连续，逐个与虚拟页做映射
    while (count > 0) {
        void* page_phyaddr = palloc(mem_pool);
        if (page_phyaddr == NULL) {
            return NULL;
        }

        page_table_add((void*) vaddr, page_phyaddr);
        vaddr += PAGE_SIZE;
        --count;
    }
    return vaddr_start;
}

/**
 * 在内核内存池中申请page_count个页.
 */ 
void* get_kernel_pages(uint32_t page_count) {
    void* vaddr = malloc_page(PF_KERNEL, page_count);
    if (vaddr != NULL) {
        memset(vaddr, 0, page_count * PAGE_SIZE);
    }
    return vaddr;
}

void mem_init(void) {
    put_str("Init memory start.\n");
    uint32_t total_memory = (*(uint32_t*) (0xb00));
    mem_pool_init(total_memory);
    put_str("Init memory done.\n");
}

最后我们在main.c中添加测试代码，申请三个页并打印其虚拟地址

1
2
3
4
5
6
7
8
9
10
11
12
13
#include "print.h"
#include "init.h"
#include "memory.h"
int main(void) {
   put_str("Welcome to TJ's kernel\n");
   init_all();
   void* addr = get_kernel_pages(3);
   put_str("\n get_kernel_page start vaddr is ");
   put_int((uint32_t)addr);
   put_str("\n");
   while(1);
   return 0;
}

运行结果

image-20210226101349686

Reward
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • © 2015-2021 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信