第十二章 实现系统调用 新增printf函数和堆内存管理

本文最后更新于：1 年前

第十二章 实现系统调用 新增printf函数和堆内存管理

写在前面

没什么好说的，抓紧出发。

实现系统调用

实现步骤

  1. 用中断门实现系统调用，效仿Linux用0x80号中断作为系统调用的入口。
  2. 在IDT中安装0x80号中断对应的描述符，在该描述符中注册系统调用对应的中断处理例程。
  3. 建立系统调用子功能表syscall_table，利用eax寄存器中的子功能号在该表中索引相应的处理函数。
  4. 用宏实现用户空间系统调用接口_syscall，最大支持3个参数的系统调用，故只需要完成_syscall[0-3]。寄存器传递参数。eax为子功能号，ebx保存第1个参数，ecx保存第2个参数，edx保存第3个参数。

kernel/kernel.h创建

1
2
3
4
5
6
#ifndef __KERNEL_KERNEL_H
#define __KERNEL_KERNEL_H

void syscall_handler(void);

#endif

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


#define PIC_M_CTRL 0x20	       // 这里用的可编程中断控制器是8259A,主片的控制端口是0x20
#define PIC_M_DATA 0x21	       // 主片的数据端口是0x21
#define PIC_S_CTRL 0xa0	       // 从片的控制端口是0xa0
#define PIC_S_DATA 0xa1	       // 从片的数据端口是0xa1
#define IDT_DESC_CNT 0x81      // 目前总共支持的中断数
#define EFLAGS_IF   0x00000200       // eflags寄存器中的if位为1
#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;
};

// 静态函数声明,非必须
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是中断描述符表,本质上就是个中断门描述符数组


char* intr_name[IDT_DESC_CNT];		     // 用于保存异常的名字


/********    定义中断处理程序数组    ********
 * 在kernel.S中定义的intrXXentry只是中断处理程序的入口,
 * 最终调用的是ide_table中的处理程序*/
intr_handler idt_table[IDT_DESC_CNT];

/********************************************/
extern intr_handler intr_entry_table[IDT_DESC_CNT];	    // 声明引用定义在kernel.S中的中断处理函数入口数组
extern uint32_t syscall_handler(void);




/* 初始化可编程中断控制器8259A */
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
   
   //outb (PIC_M_DATA, 0xfe);
   //outb (PIC_S_DATA, 0xff);

   //outb (PIC_M_DATA, 0xfd);
   //outb (PIC_S_DATA, 0xff);

   outb (PIC_M_DATA, 0xfc);
   outb (PIC_S_DATA, 0xff);

   put_str("   pic_init done\n");
}


/* 创建中断门描述符 */
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, lastindex = IDT_DESC_CNT - 1;
   for (i = 0; i < IDT_DESC_CNT; i++) 
   {
      make_idt_desc(&idt[i], IDT_DESC_ATTR_DPL0, intr_entry_table[i]); 
   }
/* 单独处理系统调用,系统调用对应的中断门dpl为3,
 * 中断处理程序为单独的syscall_handler */
   make_idt_desc(&idt[lastindex], IDT_DESC_ATTR_DPL3, syscall_handler);
   put_str("   idt_desc_init done\n");
}


/* 通用的中断处理函数,一般用在异常出现时的处理 */
static void general_intr_handler(uint8_t vec_nr) 
{
   if (vec_nr == 0x27 || vec_nr == 0x2f)     // 0x2f是从片8259A上的最后一个irq引脚，保留
   {
      return;		//IRQ7和IRQ15会产生伪中断(spurious interrupt),无须处理。
   }
   put_str("int vector : 0x");
   put_int(vec_nr);
   put_char('\n');	
}


/* 完成一般中断处理函数注册及异常名称注册 */
static void exception_init(void) {			    // 完成一般中断处理函数注册及异常名称注册
   int i;
   for (i = 0; i < IDT_DESC_CNT; i++) 
   {
/* idt_table数组中的函数是在进入中断后根据中断向量号调用的,
 * 见kernel/kernel.S的call [idt_table + %1*4] */
      idt_table[i] = general_intr_handler;		    // 默认为general_intr_handler。
							    // 以后会由register_handler来注册具体处理函数。
      intr_name[i] = "unknown";				    // 先统一赋值为unknown 
   }
   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[15] 第15项是intel保留项，未使用
   intr_name[16] = "#MF x87 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";

}


/*完成有关中断的所有初始化工作*/
void idt_init() 
{
   put_str("idt_init start\n");
   idt_desc_init();	   // 初始化中断描述符表
   exception_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");
}


/* 开中断并返回开中断前的状态*/
enum intr_status intr_enable() 
{
   enum intr_status old_status;
   if (INTR_ON == intr_get_status()) 
   {
      old_status = INTR_ON;
      return old_status;
   } 
   else 
   {
      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_ON == intr_get_status()) 
   {
      old_status = INTR_ON;
      asm volatile("cli" : : : "memory"); // 关中断,cli指令将IF位置0
      return old_status;
   } 
   else 
   {
      old_status = INTR_OFF;
      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;
}


void register_handler(uint8_t vector_no, intr_handler function);


/* 在中断处理程序数组第vector_no个元素中注册安装中断处理程序function */
void register_handler(uint8_t vector_no, intr_handler function) 
{
/* idt_table数组中的函数是在进入中断后根据中断向量号调用的,
 * 见kernel/kernel.S的call [idt_table + %1*4] */
   idt_table[vector_no] = function; 
}

lib/user/syscall.h创建

1
2
3
4
5
6
7
8
9
10
#ifndef __LIB_USER_SYSCALL_H
#define __LIB_USER_SYSCALL_H
#include "stdint.h"

enum SYSCALL_NR 
{
   SYS_GETPID,
};
uint32_t getpid(void);
#endif

lib/user/syscall.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
#include "syscall.h"

/* 无参数的系统调用 */
#define _syscall0(NUMBER) ({				       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER)					       \
   : "memory"						       \
   );							       \
   retval;						       \
})


/* 一个参数的系统调用 */
#define _syscall1(NUMBER, ARG1) ({			       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1)				       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 两个参数的系统调用 */
#define _syscall2(NUMBER, ARG1, ARG2) ({		       \
   int retval;						       \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1), "c" (ARG2)		       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 三个参数的系统调用 */
#define _syscall3(NUMBER, ARG1, ARG2, ARG3) ({		       \
   int retval;						       \
   asm volatile (					       \
      "int $0x80"					       \
      : "=a" (retval)					       \
      : "a" (NUMBER), "b" (ARG1), "c" (ARG2), "d" (ARG3)       \
      : "memory"					       \
   );							       \
   retval;						       \
})

/* 返回当前任务pid */
uint32_t getpid() {
   return _syscall0(SYS_GETPID);
}

kernel/kernel.S修改

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
[bits 32]
%define ERROR_CODE nop		 ; 若在相关的异常中cpu已经自动压入了错误码,为保持栈中格式统一,这里不做操作.
%define ZERO push 0		 ; 若在相关的异常中cpu没有压入错误码,为了统一栈中格式,就手工压入一个0

extern put_str;
extern idt_table;
extern syscall_table;

section .data
global intr_entry_table
intr_entry_table:

%macro VECTOR 2
section .text
intr%1entry:		 ; 每个中断处理程序都要压入中断向量号,所以一个中断类型一个中断处理程序，自己知道自己的中断向量号是多少

   %2				 ; 中断若有错误码会压在eip后面 
; 以下是保存上下文环境
   push ds
   push es
   push fs
   push gs
   pushad			 ; PUSHAD指令压入32位寄存器,其入栈顺序是: EAX,ECX,EDX,EBX,ESP,EBP,ESI,EDI

   ; 如果是从片上进入的中断,除了往从片上发送EOI外,还要往主片上发送EOI 
   mov al,0x20                   ; 中断结束命令EOI
   out 0xa0,al                   ; 向从片发送
   out 0x20,al                   ; 向主片发送

   push %1			 ; 不管idt_table中的目标程序是否需要参数,都一律压入中断向量号,调试时很方便
   call [idt_table + %1*4]       ; 调用idt_table中的C版本中断处理函数
   jmp intr_exit
	
section .data
   dd    intr%1entry	 ; 存储各个中断入口程序的地址，形成intr_entry_table数组
%endmacro

section .text
global intr_exit
intr_exit:	     
; 以下是恢复上下文环境
   add esp, 4			   ; 跳过中断号
   popad
   pop gs
   pop fs
   pop es
   pop ds
   add esp, 4			   ; 跳过error_code
   iretd

;;;;;;;;;;;;;;;;   0x80号中断   ;;;;;;;;;;;;;;;;
section .text
global syscall_handler
syscall_handler:
;1 保存上下文环境
   push 0			    ; 压入0, 使栈中格式统一

   push ds
   push es
   push fs
   push gs
   pushad			    ; PUSHAD指令压入32位寄存器，其入栈顺序是:
				    ; EAX,ECX,EDX,EBX,ESP,EBP,ESI,EDI 
				 
   push 0x80			    ; 此位置压入0x80也是为了保持统一的栈格式

;2 为系统调用子功能传入参数
   push edx			    ; 系统调用中第3个参数
   push ecx			    ; 系统调用中第2个参数
   push ebx			    ; 系统调用中第1个参数

;3 调用子功能处理函数
   call [syscall_table + eax*4]	    ; 编译器会在栈中根据C函数声明匹配正确数量的参数
   add esp, 12			    ; 跨过上面的三个参数

;4 将call调用后的返回值存入待当前内核栈中eax的位置
   mov [esp + 8*4], eax	
   jmp intr_exit		    ; intr_exit返回,恢复上下文


VECTOR 0x00,ZERO
VECTOR 0x01,ZERO
VECTOR 0x02,ZERO
VECTOR 0x03,ZERO 
VECTOR 0x04,ZERO
VECTOR 0x05,ZERO
VECTOR 0x06,ZERO
VECTOR 0x07,ZERO 
VECTOR 0x08,ERROR_CODE
VECTOR 0x09,ZERO
VECTOR 0x0a,ERROR_CODE
VECTOR 0x0b,ERROR_CODE 
VECTOR 0x0c,ZERO
VECTOR 0x0d,ERROR_CODE
VECTOR 0x0e,ERROR_CODE
VECTOR 0x0f,ZERO 
VECTOR 0x10,ZERO
VECTOR 0x11,ERROR_CODE
VECTOR 0x12,ZERO
VECTOR 0x13,ZERO 
VECTOR 0x14,ZERO
VECTOR 0x15,ZERO
VECTOR 0x16,ZERO
VECTOR 0x17,ZERO 
VECTOR 0x18,ERROR_CODE
VECTOR 0x19,ZERO
VECTOR 0x1a,ERROR_CODE
VECTOR 0x1b,ERROR_CODE 
VECTOR 0x1c,ZERO
VECTOR 0x1d,ERROR_CODE
VECTOR 0x1e,ERROR_CODE
VECTOR 0x1f,ZERO 
VECTOR 0x20,ZERO	;时钟中断对应的入口

VECTOR 0x21,ZERO	;键盘中断对应的入口
VECTOR 0x22,ZERO	;级联用的
VECTOR 0x23,ZERO	;串口2对应的入口
VECTOR 0x24,ZERO	;串口1对应的入口
VECTOR 0x25,ZERO	;并口2对应的入口
VECTOR 0x26,ZERO	;软盘对应的入口
VECTOR 0x27,ZERO	;并口1对应的入口
VECTOR 0x28,ZERO	;实时时钟对应的入口
VECTOR 0x29,ZERO	;重定向
VECTOR 0x2a,ZERO	;保留
VECTOR 0x2b,ZERO	;保留
VECTOR 0x2c,ZERO	;ps/2鼠标
VECTOR 0x2d,ZERO	;fpu浮点单元异常
VECTOR 0x2e,ZERO	;硬盘
VECTOR 0x2f,ZERO	;保留

VECTOR 0x30 ,ZERO
VECTOR 0x31 ,ZERO
VECTOR 0x32 ,ZERO
VECTOR 0x33 ,ZERO
VECTOR 0x34 ,ZERO
VECTOR 0x35 ,ZERO
VECTOR 0x36 ,ZERO
VECTOR 0x37 ,ZERO
VECTOR 0x38 ,ZERO
VECTOR 0x39 ,ZERO
VECTOR 0x3A ,ZERO
VECTOR 0x3B ,ZERO
VECTOR 0x3C ,ZERO
VECTOR 0x3D ,ZERO
VECTOR 0x3E ,ZERO
VECTOR 0x3F ,ZERO
VECTOR 0x40 ,ZERO
VECTOR 0x41 ,ZERO
VECTOR 0x42 ,ZERO
VECTOR 0x43 ,ZERO
VECTOR 0x44 ,ZERO
VECTOR 0x45 ,ZERO
VECTOR 0x46 ,ZERO
VECTOR 0x47 ,ZERO
VECTOR 0x48 ,ZERO
VECTOR 0x49 ,ZERO
VECTOR 0x4A ,ZERO
VECTOR 0x4B ,ZERO
VECTOR 0x4C ,ZERO
VECTOR 0x4D ,ZERO
VECTOR 0x4E ,ZERO
VECTOR 0x4F ,ZERO
VECTOR 0x50 ,ZERO
VECTOR 0x51 ,ZERO
VECTOR 0x52 ,ZERO
VECTOR 0x53 ,ZERO
VECTOR 0x54 ,ZERO
VECTOR 0x55 ,ZERO
VECTOR 0x56 ,ZERO
VECTOR 0x57 ,ZERO
VECTOR 0x58 ,ZERO
VECTOR 0x59 ,ZERO
VECTOR 0x5A ,ZERO
VECTOR 0x5B ,ZERO
VECTOR 0x5C ,ZERO
VECTOR 0x5D ,ZERO
VECTOR 0x5E ,ZERO
VECTOR 0x5F ,ZERO
VECTOR 0x61 ,ZERO
VECTOR 0x62 ,ZERO
VECTOR 0x63 ,ZERO
VECTOR 0x64 ,ZERO
VECTOR 0x65 ,ZERO
VECTOR 0x66 ,ZERO
VECTOR 0x67 ,ZERO
VECTOR 0x68 ,ZERO
VECTOR 0x69 ,ZERO
VECTOR 0x6A ,ZERO
VECTOR 0x6B ,ZERO
VECTOR 0x6C ,ZERO
VECTOR 0x6D ,ZERO
VECTOR 0x6E ,ZERO
VECTOR 0x6F ,ZERO
VECTOR 0x70 ,ZERO
VECTOR 0x71 ,ZERO
VECTOR 0x72 ,ZERO
VECTOR 0x73 ,ZERO
VECTOR 0x74 ,ZERO
VECTOR 0x75 ,ZERO
VECTOR 0x76 ,ZERO
VECTOR 0x77 ,ZERO
VECTOR 0x78 ,ZERO
VECTOR 0x79 ,ZERO
VECTOR 0x7A ,ZERO
VECTOR 0x7B ,ZERO
VECTOR 0x7C ,ZERO
VECTOR 0x7D ,ZERO
VECTOR 0x7E ,ZERO
VECTOR 0x7F ,ZERO
VECTOR 0x80 ,ZERO

userprog/syscall-init.h创建

1
2
3
4
5
6
#ifndef __USERPROG_SYSCALLINIT_H
#define __USERPROG_SYSCALLINIT_H
#include "stdint.h"
void syscall_init(void);
uint32_t sys_getpid(void);
#endif

userprog/syscall-init.c创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "syscall-init.h"
#include "../lib/user/syscall.h"
#include "stdint.h"
#include "print.h"
#include "interrupt.h"
#include "../thread/thread.h"


#define syscall_nr 32 
typedef void* syscall;
syscall syscall_table[syscall_nr];

/* 返回当前任务的pid */
uint32_t sys_getpid(void) {
   return running_thread()->pid;
}

/* 初始化系统调用 */
void syscall_init(void) {
   put_str("syscall_init start\n");
   syscall_table[SYS_GETPID]	    = sys_getpid;
   put_str("syscall_init done\n");
}

thread/thread.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
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
#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"
#include "list.h"
#include "bitmap.h"
#include "memory.h"

#define TASK_NAME_LEN 16
#define MAX_FILES_OPEN_PER_PROC 8
/* 自定义通用函数类型,它将在很多线程函数中做为形参类型 */
typedef void thread_func(void*);
typedef int16_t pid_t;

/* 进程或线程的状态 */
enum task_status 
{
   TASK_RUNNING,
   TASK_READY,
   TASK_BLOCKED,
   TASK_WAITING,
   TASK_HANGING,
   TASK_DIED
};

/***********   中断栈intr_stack   ***********
 * 此结构用于中断发生时保护程序(线程或进程)的上下文环境:
 * 进程或线程被外部中断或软中断打断时,会按照此结构压入上下文
 * 寄存器,  intr_exit中的出栈操作是此结构的逆操作
 * 此栈在线程自己的内核栈中位置固定,所在页的最顶端
********************************************/
struct intr_stack 
{
    uint32_t vec_no;	 // kernel.S 宏VECTOR中push %1压入的中断号
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp_dummy;	 // 虽然pushad把esp也压入,但esp是不断变化的,所以会被popad忽略
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;
    uint32_t gs;
    uint32_t fs;
    uint32_t es;
    uint32_t ds;

/* 以下由cpu从低特权级进入高特权级时压入 */
    uint32_t err_code;		 // err_code会被压入在eip之后
    void (*eip) (void);
    uint32_t cs;
    uint32_t eflags;
    void* esp;
    uint32_t ss;
};

/***********  线程栈thread_stack  ***********
 * 线程自己的栈,用于存储线程中待执行的函数
 * 此结构在线程自己的内核栈中位置不固定,
 * 用在switch_to时保存线程环境。
 * 实际位置取决于实际运行情况。
 ******************************************/
struct thread_stack 
{
   uint32_t ebp;
   uint32_t ebx;
   uint32_t edi;
   uint32_t esi;

/* 线程第一次执行时,eip指向待调用的函数kernel_thread 
其它时候,eip是指向switch_to的返回地址*/
   void (*eip) (thread_func* func, void* func_arg);

/*****   以下仅供第一次被调度上cpu时使用   ****/

/* 参数unused_ret只为占位置充数为返回地址 */
   void (*unused_retaddr);
   thread_func* function;   // 由Kernel_thread所调用的函数名
   void* func_arg;    // 由Kernel_thread所调用的函数所需的参数
};

/* 进程或线程的pcb,程序控制块 */
struct task_struct 
{
   uint32_t* self_kstack;	 // 各内核线程都用自己的内核栈
   pid_t pid;
   enum task_status status;
   char name[TASK_NAME_LEN];
   uint8_t priority;
   uint8_t ticks;	   // 每次在处理器上执行的时间嘀嗒数
/* 此任务自上cpu运行后至今占用了多少cpu嘀嗒数,
 * 也就是此任务执行了多久*/
   uint32_t elapsed_ticks;
/* general_tag的作用是用于线程在一般的队列中的结点 */
   struct list_elem general_tag;				    
/* all_list_tag的作用是用于线程队列thread_all_list中的结点 */
   struct list_elem all_list_tag;
   uint32_t* pgdir;              // 进程自己页表的虚拟地址
   struct virtual_addr userprog_vaddr;   // 用户进程的虚拟地址 
   uint32_t stack_magic;	 // 用这串数字做栈的边界标记,用于检测栈的溢出
};

extern struct list thread_ready_list;
extern struct list thread_all_list;

struct task_struct* running_thread(void);
static void kernel_thread(thread_func* function,void* func_arg);
void thread_create(struct task_struct* pthread,thread_func function,void* func_arg);
void init_thread(struct task_struct* pthread,char* name,int prio);
struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg);
static void make_main_thread(void);
void schedule(void);
void thread_init(void);
void thread_block(enum task_status stat);
void thread_unblock(struct task_struct* pthread);
static pid_t allocate_pid(void);

#endif

thread/thread.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
#include "thread.h"   //函数声明 各种结构体
#include "stdint.h"   //前缀
#include "string.h"   //memset
#include "global.h"   //不清楚
#include "memory.h"   //分配页需要
#include "debug.h"
#include "interrupt.h"
#include "print.h"
#include "../userprog/process.h"
#include "../thread/sync.h"


#define PG_SIZE 4096

struct task_struct* main_thread;    // 主线程PCB
struct list thread_ready_list;	    // 就绪队列
struct list thread_all_list;	    // 所有任务队列
static struct list_elem* thread_tag;// 用于保存队列中的线程结点
struct lock pid_lock;

/* 获取当前线程pcb指针 */
struct task_struct* running_thread() 
{
   	uint32_t esp; 
	asm ("mov %%esp, %0" : "=g" (esp));
	/* 取esp整数部分即pcb起始地址 */
	return (struct task_struct*)(esp & 0xfffff000);
}


/* 由kernel_thread去执行function(func_arg) */
static void kernel_thread(thread_func* function, void* func_arg) 
{
/* 执行function前要开中断,避免后面的时钟中断被屏蔽,而无法调度其它线程 */
	intr_enable();
	function(func_arg); 
}


/* 初始化线程栈thread_stack,将待执行的函数和参数放到thread_stack中相应的位置 */
void thread_create(struct task_struct* pthread, thread_func function, void* func_arg) 
{
	/* 先预留中断使用栈的空间,可见thread.h中定义的结构 */
	pthread->self_kstack -= sizeof(struct intr_stack);

	/* 再留出线程栈空间,可见thread.h中定义 */
	pthread->self_kstack -= sizeof(struct thread_stack);
	struct thread_stack* kthread_stack = (struct thread_stack*)pthread->self_kstack;
	kthread_stack->eip = kernel_thread;
	kthread_stack->function = function;
	kthread_stack->func_arg = func_arg;
	kthread_stack->ebp = kthread_stack->ebx = kthread_stack->esi = kthread_stack->edi = 0;
}


/* 初始化线程基本信息 */
void init_thread(struct task_struct* pthread, char* name, int prio) 
{
	memset(pthread, 0, sizeof(*pthread));
   	pthread->pid = allocate_pid();
   	strcpy(pthread->name, name);

	if (pthread == main_thread) 
	{
	/* 由于把main函数也封装成一个线程,并且它一直是运行的,故将其直接设为TASK_RUNNING */
		pthread->status = TASK_RUNNING;
	} 
	else 
	{
		pthread->status = TASK_READY;
	}

	/* self_kstack是线程自己在内核态下使用的栈顶地址 */
	pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
	pthread->priority = prio;
	pthread->ticks = prio;
	pthread->elapsed_ticks = 0;
	pthread->pgdir = NULL;
	pthread->stack_magic = 0x19870916;	  // 自定义的魔数
}


/* 创建一优先级为prio的线程,线程名为name,线程所执行的函数是function(func_arg) */
struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg) 
{
/* pcb都位于内核空间,包括用户进程的pcb也是在内核空间 */
	struct task_struct* thread = get_kernel_pages(1);
	init_thread(thread, name, prio);
	thread_create(thread, function, func_arg);

	/* 确保之前不在队列中 */
	ASSERT(!elem_find(&thread_ready_list, &thread->general_tag));
	/* 加入就绪线程队列 */
	list_append(&thread_ready_list, &thread->general_tag);

	/* 确保之前不在队列中 */
	ASSERT(!elem_find(&thread_all_list, &thread->all_list_tag));
	/* 加入全部线程队列 */
	list_append(&thread_all_list, &thread->all_list_tag);

	return thread;
}


/* 将kernel中的main函数完善为主线程 */
static void make_main_thread(void) 
{
/* 因为main线程早已运行,咱们在loader.S中进入内核时的mov esp,0xc009f000,
就是为其预留了tcb,地址为0xc009e000,因此不需要通过get_kernel_page另分配一页*/
	main_thread = running_thread();
	init_thread(main_thread, "main", 31);

/* main函数是当前线程,当前线程不在thread_ready_list中,
 * 所以只将其加在thread_all_list中. */
	ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag));
	list_append(&thread_all_list, &main_thread->all_list_tag);
}


/* 实现任务调度 */
void schedule() 
{
	ASSERT(intr_get_status() == INTR_OFF);

	struct task_struct* cur = running_thread(); 
	if (cur->status == TASK_RUNNING) 		// 若此线程只是cpu时间片到了,将其加入到就绪队列尾
	{ 
		ASSERT(!elem_find(&thread_ready_list, &cur->general_tag));
		list_append(&thread_ready_list, &cur->general_tag);
		cur->ticks = cur->priority;     // 重新将当前线程的ticks再重置为其priority;
		cur->status = TASK_READY;
	} 
	else 
	{ 
		/* 若此线程需要某事件发生后才能继续上cpu运行,
		不需要将其加入队列,因为当前线程不在就绪队列中。*/
	}


	ASSERT(!list_empty(&thread_ready_list));
	thread_tag = NULL;	  // thread_tag清空
	/* 将thread_ready_list队列中的第一个就绪线程弹出,准备将其调度上cpu. */
	thread_tag = list_pop(&thread_ready_list);   
	struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag);
	next->status = TASK_RUNNING;

	process_activate(next);
	switch_to(cur, next);
}


/* 初始化线程环境 */
void thread_init(void) 
{
	put_str("thread_init start\n");

	list_init(&thread_ready_list);
	list_init(&thread_all_list);
	lock_init(&pid_lock);
/* 将当前main函数创建为线程 */
	make_main_thread();
	put_str("thread_init done\n");
}


/* 当前线程将自己阻塞,标志其状态为stat. */
void thread_block(enum task_status stat) 
{
/* stat取值为TASK_BLOCKED,TASK_WAITING,TASK_HANGING,也就是只有这三种状态才不会被调度*/
	ASSERT(((stat == TASK_BLOCKED) || (stat == TASK_WAITING) || (stat == TASK_HANGING)));
	enum intr_status old_status = intr_disable();
	struct task_struct* cur_thread = running_thread();
	cur_thread->status = stat; // 置其状态为stat 
	schedule();		      // 将当前线程换下处理器
/* 待当前线程被解除阻塞后才继续运行下面的intr_set_status */
   	intr_set_status(old_status);
}


/* 将线程pthread解除阻塞 */
void thread_unblock(struct task_struct* pthread) 
{
	enum intr_status old_status = intr_disable();
	ASSERT(((pthread->status == TASK_BLOCKED) || (pthread->status == TASK_WAITING) || (pthread->status == TASK_HANGING)));
	if (pthread->status != TASK_READY) 
	{
		ASSERT(!elem_find(&thread_ready_list, &pthread->general_tag));
		if (elem_find(&thread_ready_list, &pthread->general_tag)) 
		{
			PANIC("thread_unblock: blocked thread in ready_list\n");
		}
		list_push(&thread_ready_list, &pthread->general_tag);    // 放到队列的最前面,使其尽快得到调度
		pthread->status = TASK_READY;
	} 
	intr_set_status(old_status);
}


/* 分配pid */
static pid_t allocate_pid(void) 
{
   static pid_t next_pid = 0;
   lock_acquire(&pid_lock);	
   next_pid++;
   lock_release(&pid_lock);
   return next_pid;
}

kernel/init.c修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "init.h"
#include "print.h"
#include "interrupt.h"
#include "../device/timer.h"
#include "memory.h"
#include "../thread/thread.h"
#include "../device/console.h"
#include "../device/keyboard.h"
#include "../userprog/tss.h"

/*负责初始化所有模块 */
void init_all() 
{
   	put_str("init_all\n");
	idt_init();	     // 初始化中断
	mem_init();
	timer_init();
	thread_init();
	console_init();
	keyboard_init();
	tss_init();
	syscall_init();
}

kernel/main.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
#include "print.h"
#include "init.h"
#include "debug.h"
#include "string.h"
#include "memory.h"
#include "../thread/thread.h"
#include "interrupt.h"
#include "../device/console.h"
#include "../device/ioqueue.h"
#include "../device/keyboard.h"
#include "../userprog/process.h"
#include "../lib/user/syscall.h"
#include "../userprog/syscall-init.h"


void k_thread_a(void* );
void k_thread_b(void* );
void u_prog_a (void);
void u_prog_b (void);

int prog_a_pid = 0, prog_b_pid=0;

int main(void) {
   put_str("I am kernel\n");
   init_all();
	
	process_execute(u_prog_a, "user_prog_a");
	process_execute(u_prog_b, "user_prog_b");
	
   intr_enable();
   console_put_str(" main_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
  
	thread_start("k_thread_a", 31, k_thread_a, "argA ");
	thread_start("k_thread_b", 8, k_thread_b, "argB ");
	while(1);
   return 0;
}

void k_thread_a(void* arg){
	char* para = arg;
	console_put_str(" thread_a_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
	console_put_str(" prog_a_pid:0x");
   console_put_int(prog_a_pid);
   console_put_char('\n');
	while(1);
}

void k_thread_b(void* arg){
	char* para = arg;
	console_put_str(" thread_b_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
	console_put_str(" prog_b_pid:0x");
   console_put_int(prog_b_pid);
   console_put_char('\n');
   while(1);
}

void u_prog_a(void) {
	prog_a_pid = getpid();
	while(1);
}

void u_prog_b(void) {
	prog_b_pid = getpid();
	while(1);
}

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
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
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 = -Wall -m32 -fno-stack-protector $(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)/switch.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/thread.o $(BUILD_DIR)/list.o \
      $(BUILD_DIR)/sync.o $(BUILD_DIR)/console.o $(BUILD_DIR)/keyboard.o \
      $(BUILD_DIR)/ioqueue.o $(BUILD_DIR)/tss.o $(BUILD_DIR)/process.o \
      $(BUILD_DIR)/syscall-init.o $(BUILD_DIR)/syscall.o
      
##############     c代码编译     ###############
$(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
        lib/stdint.h kernel/init.h lib/string.h kernel/memory.h \
        thread/thread.h kernel/interrupt.h device/console.h \
        device/keyboard.h device/ioqueue.h userprog/process.h \
        lib/user/syscall.h userprog/syscall-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 kernel/memory.h \
        thread/thread.h device/console.h device/keyboard.h userprog/tss.h \
        userprog/syscall-init.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 \
        kernel/kernel.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/kernel/io.h lib/kernel/print.h \
        kernel/interrupt.h thread/thread.h kernel/debug.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/debug.h kernel/global.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
	lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h \
	thread/sync.h thread/thread.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h kernel/global.h \
	lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/thread.o: thread/thread.c thread/thread.h \
	lib/stdint.h lib/string.h kernel/global.h kernel/memory.h \
	kernel/debug.h kernel/interrupt.h lib/kernel/print.h \
	userprog/process.h thread/sync.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/list.o: lib/kernel/list.c lib/kernel/list.h \
	kernel/interrupt.h lib/stdint.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/sync.o: thread/sync.c thread/sync.h \
	lib/stdint.h thread/thread.h kernel/debug.h kernel/interrupt.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/console.o: device/console.c device/console.h \
	lib/kernel/print.h thread/sync.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/keyboard.o: device/keyboard.c device/keyboard.h \
	lib/kernel/print.h lib/kernel/io.h kernel/interrupt.h \
	kernel/global.h lib/stdint.h device/ioqueue.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/ioqueue.o: device/ioqueue.c device/ioqueue.h \
	kernel/interrupt.h kernel/global.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/tss.o: userprog/tss.c userprog/tss.h \
	kernel/global.h thread/thread.h lib/kernel/print.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/process.o: userprog/process.c userprog/process.h \
	lib/string.h kernel/global.h kernel/memory.h lib/kernel/print.h \
	thread/thread.h kernel/interrupt.h kernel/debug.h device/console.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/syscall-init.o: userprog/syscall-init.c userprog/syscall-init.h \
	lib/user/syscall.h lib/stdint.h lib/kernel/print.h kernel/interrupt.h thread/thread.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/syscall.o: lib/user/syscall.c lib/user/syscall.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)/switch.o: thread/switch.S
	$(AS) $(ASFLAGS) $< -o $@

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

.PHONY : mk_dir hd clean all

mk_dir:
	if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

hd:
	dd if=$(BUILD_DIR)/kernel.bin \
           of=/home/podest/bochs/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

运行结果

图为bochs运行界面

实现printf函数

userprog/syscall-init.h修改

1
2
3
4
5
6
7
#ifndef __USERPROG_SYSCALLINIT_H
#define __USERPROG_SYSCALLINIT_H
#include "stdint.h"
void syscall_init(void);
void sys_write(char* str);
uint32_t sys_getpid(void);
#endif

userprog/syscall-init.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
#include "syscall-init.h"
#include "../lib/user/syscall.h"
#include "stdint.h"
#include "print.h"
#include "interrupt.h"
#include "../thread/thread.h"


#define syscall_nr 32 
typedef void* syscall;
syscall syscall_table[syscall_nr];

/* 返回当前任务的pid */
uint32_t sys_getpid(void) {
   return running_thread()->pid;
}

void sys_write(char* str)
{
    console_put_str(str);
}

/* 初始化系统调用 */
void syscall_init(void) {
   put_str("syscall_init start\n");
   syscall_table[SYS_GETPID] = sys_getpid;
   syscall_table[SYS_WRITE] = sys_write;
   put_str("syscall_init done\n");
}

lib/user/syscall.h修改

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

enum SYSCALL_NR 
{
   SYS_GETPID,
   SYS_WRITE
};
uint32_t getpid(void);
uint32_t write(char* str);
#endif

lib/user/syscall.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
#include "syscall.h"

/* 无参数的系统调用 */
#define _syscall0(NUMBER) ({				       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER)					       \
   : "memory"						       \
   );							       \
   retval;						       \
})


/* 一个参数的系统调用 */
#define _syscall1(NUMBER, ARG1) ({			       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1)				       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 两个参数的系统调用 */
#define _syscall2(NUMBER, ARG1, ARG2) ({		       \
   int retval;						       \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1), "c" (ARG2)		       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 三个参数的系统调用 */
#define _syscall3(NUMBER, ARG1, ARG2, ARG3) ({		       \
   int retval;						       \
   asm volatile (					       \
      "int $0x80"					       \
      : "=a" (retval)					       \
      : "a" (NUMBER), "b" (ARG1), "c" (ARG2), "d" (ARG3)       \
      : "memory"					       \
   );							       \
   retval;						       \
})

/* 返回当前任务pid */
uint32_t getpid() 
{
   return _syscall0(SYS_GETPID);
}

uint32_t write(char* str)
{
    return _syscall1(SYS_WRITE,str);
}

lib/stdio.h创建

1
2
3
4
5
6
7
8
#ifndef __LIB_STDIO_H
#define __LIB_STDIO_H
#include "stdint.h"
typedef char* va_list;
uint32_t printf(const char* str, ...);
uint32_t vsprintf(char* str, const char* format, va_list ap);
uint32_t sprintf(char* buf, const char* format, ...);
#endif

lib/stdio.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
#include "stdio.h"
#include "stdint.h"
#include "string.h"
#include "syscall.h"

#define va_start(ap, v) ap = (va_list)&v  // 把ap指向第一个固定参数v
#define va_arg(ap, t) *((t*)(ap += 4))	  // ap指向下一个参数并返回其值
#define va_end(ap) ap = NULL		  // 清除ap

/* 将整型转换成字符(integer to ascii) */
static void itoa(uint32_t value, char** buf_ptr_addr, uint8_t base) {
   uint32_t m = value % base;	    // 求模,最先掉下来的是最低位   
   uint32_t i = value / base;	    // 取整
   if (i) {			    // 如果倍数不为0则递归调用。
      itoa(i, buf_ptr_addr, base);
   }
   if (m < 10) {      // 如果余数是0~9
      *((*buf_ptr_addr)++) = m + '0';	  // 将数字0~9转换为字符'0'~'9'
   } else {	      // 否则余数是A~F
      *((*buf_ptr_addr)++) = m - 10 + 'A'; // 将数字A~F转换为字符'A'~'F'
   }
}

/* 将参数ap按照格式format输出到字符串str,并返回替换后str长度 */
uint32_t vsprintf(char* str, const char* format, va_list ap) {
   char* buf_ptr = str;
   const char* index_ptr = format;
   char index_char = *index_ptr;
   int32_t arg_int;
   char* arg_str;
   while(index_char) {
      if (index_char != '%') {
	 *(buf_ptr++) = index_char;
	 index_char = *(++index_ptr);
	 continue;
      }
      index_char = *(++index_ptr);	 // 得到%后面的字符
      switch(index_char) {
	 case 's':
	    arg_str = va_arg(ap, char*);
	    strcpy(buf_ptr, arg_str);
	    buf_ptr += strlen(arg_str);
	    index_char = *(++index_ptr);
	    break;

	 case 'c':
	    *(buf_ptr++) = va_arg(ap, char);
	    index_char = *(++index_ptr);
	    break;

	 case 'd':
	    arg_int = va_arg(ap, int);
      /* 若是负数, 将其转为正数后,再正数前面输出个负号'-'. */
	    if (arg_int < 0) {
	       arg_int = 0 - arg_int;
	       *buf_ptr++ = '-';
	    }
	    itoa(arg_int, &buf_ptr, 10); 
	    index_char = *(++index_ptr);
	    break;

	 case 'x':
	    arg_int = va_arg(ap, int);
	    itoa(arg_int, &buf_ptr, 16); 
	    index_char = *(++index_ptr); // 跳过格式字符并更新index_char
	    break;
      }
   }
   return strlen(str);
}

/* 同printf不同的地方就是字符串不是写到终端,而是写到buf中 */
uint32_t sprintf(char* buf, const char* format, ...) {
   va_list args;
   uint32_t retval;
   va_start(args, format);
   retval = vsprintf(buf, format, args);
   va_end(args);
   return retval;
}

/* 格式化输出字符串format */
uint32_t printf(const char* format, ...) {
   va_list args;
   va_start(args, format);	       // 使args指向format
   char buf[1024] = {0};	       // 用于存储拼接后的字符串
   vsprintf(buf, format, args);
   va_end(args);
   return write(buf); 
}

kernel/main.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
#include "print.h"
#include "init.h"
#include "debug.h"
#include "string.h"
#include "memory.h"
#include "../thread/thread.h"
#include "interrupt.h"
#include "../device/console.h"
#include "../device/ioqueue.h"
#include "../device/keyboard.h"
#include "../userprog/process.h"
#include "../lib/user/syscall.h"
#include "../userprog/syscall-init.h"
#include "../lib/stdio.h"


void k_thread_a(void* );
void k_thread_b(void* );
void u_prog_a (void);
void u_prog_b (void);

int prog_a_pid = 0, prog_b_pid=0;

int main(void) {
   put_str("I am kernel\n");
   init_all();
	
	process_execute(u_prog_a, "user_prog_a");
	process_execute(u_prog_b, "user_prog_b");
	
   intr_enable();
   console_put_str(" main_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
  
	thread_start("k_thread_a", 31, k_thread_a, "argA ");
	thread_start("k_thread_b", 31, k_thread_b, "argB ");
	while(1);
   return 0;
}

void k_thread_a(void* arg){
	char* para = arg;
	console_put_str(" thread_a_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
	while(1);
}

void k_thread_b(void* arg){
	char* para = arg;
	console_put_str(" thread_b_pid:0x");
   console_put_int(sys_getpid());
   console_put_char('\n');
   while(1);
}

void u_prog_a(void) {
char* name = "prog_a";
printf(" i am %s, my pid:%d%c",name ,getpid(), '\n');
	while(1);
}

void u_prog_b(void) {
char* name = "prog_b";
printf(" i am %s, my pid:%d%c",name ,getpid(), '\n');
	while(1);
}

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
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
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 = -Wall -m32 -fno-stack-protector $(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)/switch.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/thread.o $(BUILD_DIR)/list.o \
      $(BUILD_DIR)/sync.o $(BUILD_DIR)/console.o $(BUILD_DIR)/keyboard.o \
      $(BUILD_DIR)/ioqueue.o $(BUILD_DIR)/tss.o $(BUILD_DIR)/process.o \
      $(BUILD_DIR)/syscall-init.o $(BUILD_DIR)/syscall.o $(BUILD_DIR)/stdio.o
      
##############     c代码编译     ###############
$(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
        lib/stdint.h kernel/init.h lib/string.h kernel/memory.h \
        thread/thread.h kernel/interrupt.h device/console.h \
        device/keyboard.h device/ioqueue.h userprog/process.h \
        lib/user/syscall.h userprog/syscall-init.h lib/stdio.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 \
        thread/thread.h device/console.h device/keyboard.h userprog/tss.h \
        userprog/syscall-init.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 \
        kernel/kernel.h
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/kernel/io.h lib/kernel/print.h \
        kernel/interrupt.h thread/thread.h kernel/debug.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/debug.h kernel/global.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
	lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h \
	thread/sync.h thread/thread.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h kernel/global.h \
	lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/thread.o: thread/thread.c thread/thread.h \
	lib/stdint.h lib/string.h kernel/global.h kernel/memory.h \
	kernel/debug.h kernel/interrupt.h lib/kernel/print.h \
	userprog/process.h thread/sync.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/list.o: lib/kernel/list.c lib/kernel/list.h \
	kernel/interrupt.h lib/stdint.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/sync.o: thread/sync.c thread/sync.h \
	lib/stdint.h thread/thread.h kernel/debug.h kernel/interrupt.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/console.o: device/console.c device/console.h \
	lib/kernel/print.h thread/sync.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/keyboard.o: device/keyboard.c device/keyboard.h \
	lib/kernel/print.h lib/kernel/io.h kernel/interrupt.h \
	kernel/global.h lib/stdint.h device/ioqueue.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/ioqueue.o: device/ioqueue.c device/ioqueue.h \
	kernel/interrupt.h kernel/global.h kernel/debug.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/tss.o: userprog/tss.c userprog/tss.h \
	kernel/global.h thread/thread.h lib/kernel/print.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/process.o: userprog/process.c userprog/process.h \
	lib/string.h kernel/global.h kernel/memory.h lib/kernel/print.h \
	thread/thread.h kernel/interrupt.h kernel/debug.h device/console.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/syscall-init.o: userprog/syscall-init.c userprog/syscall-init.h \
	lib/user/syscall.h lib/stdint.h lib/kernel/print.h kernel/interrupt.h thread/thread.h
	$(CC) $(CFLAGS) $< -o $@
	
$(BUILD_DIR)/syscall.o: lib/user/syscall.c lib/user/syscall.h 
	$(CC) $(CFLAGS) $< -o $@

$(BUILD_DIR)/stdio.o: lib/stdio.c lib/stdio.h lib/stdint.h lib/string.h lib/user/syscall.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)/switch.o: thread/switch.S
	$(AS) $(ASFLAGS) $< -o $@

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

.PHONY : mk_dir hd clean all

mk_dir:
	if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

hd:
	dd if=$(BUILD_DIR)/kernel.bin \
           of=/home/podest/bochs/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

运行结果

图为bochs运行界面

完善堆内存管理

目的

我们在第八章实现了动态申请多页内存的函数，但是申请一页以下的内存并未实现，内存释放完全没有实现，所以这次实验就是动态申请内存的完善。

kernel/memory.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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#ifndef __KERNEL_MEMORY_H
#define __KERNEL_MEMORY_H
#include "stdint.h"
#include "bitmap.h"
#include "list.h"

/* 内存池标记,用于判断用哪个内存池 */
enum pool_flags {
	PF_KERNEL = 1,    // 内核内存池
	PF_USER = 2	     // 用户内存池
};

#define	 PG_P_1	  1	// 页表项或页目录项存在属性位
#define	 PG_P_0	  0	// 页表项或页目录项存在属性位
#define	 PG_RW_R  0	// R/W 属性位值, 读/执行
#define	 PG_RW_W  2	// R/W 属性位值, 读/写/执行
#define	 PG_US_S  0	// U/S 属性位值, 系统级
#define	 PG_US_U  4	// U/S 属性位值, 用户级
#define  DESC_CNT 7

/* 用于虚拟地址管理 */
struct virtual_addr {
/* 虚拟地址用到的位图结构，用于记录哪些虚拟地址被占用了。以页为单位。*/
  	struct bitmap vaddr_bitmap;
/* 管理的虚拟地址 */
  	uint32_t vaddr_start;
};


/* 内存块 */
struct mem_block {
   	struct list_elem free_elem;
};

/* 内存块描述符 */
struct mem_block_desc {
	uint32_t block_size;		 // 内存块大小
	uint32_t blocks_per_arena;	 // 本arena中可容纳此mem_block的数量.
	struct list free_list;	 // 目前可用的mem_block链表
};

extern struct pool kernel_pool,user_pool;
static void* vaddr_get(enum pool_flags pf,uint32_t pg_cnt);
uint32_t* pte_ptr(uint32_t vaddr);
uint32_t* pde_ptr(uint32_t vaddr);
static void* palloc(struct pool* m_pool);
static void page_table_add(void* _vaddr,void* _page_phyaddr);
void* malloc_page(enum pool_flags pf,uint32_t pg_cnt);
void* get_kernel_pages(uint32_t pg_cnt);
void* get_user_pages(uint32_t pg_cnt);
void* get_a_page(enum pool_flags pf,uint32_t vaddr);
uint32_t addr_v2p(uint32_t vaddr);
static void mem_pool_init(uint32_t all_mem);
void mem_init(void);

#endif

kernel/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
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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
#include "memory.h"
#include "bitmap.h"
#include "stdint.h"
#include "global.h"
#include "debug.h"
#include "print.h"
#include "string.h"
#include "interrupt.h"
#include "../thread/sync.h"
#include "../thread/thread.h"

#define PG_SIZE 4096

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

#define PDE_IDX(addr) ((addr & 0xffc00000) >> 22)
#define PTE_IDX(addr) ((addr & 0x003ff000) >> 12)

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

/* 内存池结构,生成两个实例用于管理内核内存池和用户内存池 */
struct pool 
{
	struct bitmap pool_bitmap;	 // 本内存池用到的位图结构,用于管理物理内存
  	uint32_t phy_addr_start;	 // 本内存池所管理物理内存的起始地址
  	uint32_t pool_size;		 // 本内存池字节容量
	struct lock lock;		 // 申请内存时互斥
};
/* 内存仓库arena元信息 */
struct arena 
{
   struct mem_block_desc* desc;	 // 此arena关联的mem_block_desc
/* large为ture时,cnt表示的是页框数。
 * 否则cnt表示空闲mem_block数量 */
   uint32_t cnt;
   bool large;		   
};
struct mem_block_desc k_block_descs[DESC_CNT];	// 内核内存块描述符数组
struct pool kernel_pool, user_pool;      // 生成内核内存池和用户内存池
struct virtual_addr kernel_vaddr;	 // 此结构是用来给内核分配虚拟地址


/* 在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) 
		{
	 		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;
   	} 
	else // 用户内存池
	{	     	
      	struct task_struct* cur = running_thread();
      	bit_idx_start  = bitmap_scan(&cur->userprog_vaddr.vaddr_bitmap, pg_cnt);
      	if (bit_idx_start == -1) 
		{
	 		return NULL;
      	}
      	while(cnt < pg_cnt) 
		{
	 		bitmap_set(&cur->userprog_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 1);
      	}
      	vaddr_start = cur->userprog_vaddr.vaddr_start + bit_idx_start * PG_SIZE;

   /* (0xc0000000 - PG_SIZE)做为用户3级栈已经在start_process被分配 */
      	ASSERT((uint32_t)vaddr_start < (0xc0000000 - PG_SIZE));
   	}
   	return (void*)vaddr_start;
}


/* 得到虚拟地址vaddr对应的pte指针*/
uint32_t* pte_ptr(uint32_t vaddr) 
{
  /* 先访问到页表自己 + \
   * 再用页目录项pde(页目录内页表的索引)做为pte的索引访问到页表 + \
   * 再用pte的索引做为页内偏移*/
  	uint32_t* pte = (uint32_t*)(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个物理页,
* 成功则返回页框的物理地址,失败则返回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);
  	return (void*)page_phyaddr;
}


/* 页表中添加虚拟地址_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未创建时,
* *pte只能出现在下面最外层else语句块中的*pde后面。
* *********************************************************/
  /* 先在页目录内判断目录项的P位，若为1,则表示该表已存在 */
  	if (*pde & 0x00000001) 
	{
     	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会起作用
		{	  
    		PANIC("pte repeat");
     	}
  	} 
	else 	// 页目录项不存在,所以要先创建页目录项再创建页表项.
	{	  
     	/* 页表中用到的页框一律从内核空间分配 */
     	uint32_t pde_phyaddr = (uint32_t)palloc(&kernel_pool);
     	*pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);

/*******************   必须将页表所在的页清0   *********************
* 必须把分配到的物理页地址pde_phyaddr对应的物理内存清0,
* 避免里面的陈旧数据变成了页表中的页表项,从而让页表混乱.
* pte的高20位会映射到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
  	}
}


/* 分配pg_cnt个页空间,成功则返回起始虚拟地址,失败时返回NULL */
void* malloc_page(enum pool_flags pf, uint32_t pg_cnt) 
{
  	ASSERT(pg_cnt > 0 && pg_cnt < 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页内存,
* 成功则返回其虚拟地址,失败则返回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;
}


/* 在用户空间中申请4k内存,并返回其虚拟地址 */
void* get_user_pages(uint32_t pg_cnt) 
{
   	lock_acquire(&user_pool.lock);
   	void* vaddr = malloc_page(PF_USER, pg_cnt);
   	if (vaddr != NULL) 		// 若分配的地址不为空,将页框清0后返回
	{	   
      	memset(vaddr, 0, pg_cnt * PG_SIZE);
   	}
   	lock_release(&user_pool.lock);
   	return vaddr;
}


/* 将地址vaddr与pf池中的物理地址关联,仅支持一页空间分配 */
void* get_a_page(enum pool_flags pf, uint32_t vaddr) 
{
   	struct pool* mem_pool = pf & PF_KERNEL ? &kernel_pool : &user_pool;
   	lock_acquire(&mem_pool->lock);

   	/* 先将虚拟地址对应的位图置1 */
   	struct task_struct* cur = running_thread();
   	int32_t bit_idx = -1;

/* 若当前是用户进程申请用户内存,就修改用户进程自己的虚拟地址位图 */
   	if (cur->pgdir != NULL && pf == PF_USER) 
	{
      	bit_idx = (vaddr - cur->userprog_vaddr.vaddr_start) / PG_SIZE;
      	ASSERT(bit_idx >= 0);
      	bitmap_set(&cur->userprog_vaddr.vaddr_bitmap, bit_idx, 1);
   	} 
	else if (cur->pgdir == NULL && pf == PF_KERNEL)
	{
/* 如果是内核线程申请内核内存,就修改kernel_vaddr. */
      	bit_idx = (vaddr - kernel_vaddr.vaddr_start) / PG_SIZE;
      	ASSERT(bit_idx > 0);
      	bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx, 1);
   	} 
	else 
	{
      	PANIC("get_a_page:not allow kernel alloc userspace or user alloc kernelspace by get_a_page");
   	}

   	void* page_phyaddr = palloc(mem_pool);
   	if (page_phyaddr == NULL) 
	{
      	lock_release(&mem_pool->lock);
      	return NULL;
   	}
   	page_table_add((void*)vaddr, page_phyaddr); 
   	lock_release(&mem_pool->lock);
   	return (void*)vaddr;
}


/* 得到虚拟地址映射到的物理地址 */
uint32_t addr_v2p(uint32_t vaddr) 
{
   	uint32_t* pte = pte_ptr(vaddr);
/* (*pte)的值是页表所在的物理页框地址,
 * 去掉其低12位的页表项属性+虚拟地址vaddr的低12位 */
   	return ((*pte & 0xfffff000) + (vaddr & 0x00000fff));
}


/* 初始化内存池 */
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为低端1M内存
  	uint32_t free_mem = all_mem - used_mem;
  	uint16_t all_free_pages = free_mem / PG_SIZE;		  // 1页为4k,不管总内存是不是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,这是主线程的栈地址.(内核的大小预计为70K左右)
// 32M内存占用的位图是2k.内核内存池的位图先定在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);
	lock_init(&kernel_pool.lock);
  	lock_init(&user_pool.lock);
  	put_str("   mem_pool_init done\n");
}


/* 为malloc做准备 */
void block_desc_init(struct mem_block_desc* desc_array) 
{				   
	uint16_t desc_idx, block_size = 16;
	/* 初始化每个mem_block_desc描述符 */
	for (desc_idx = 0; desc_idx < DESC_CNT; desc_idx++) 
	{
		desc_array[desc_idx].block_size = block_size;
		/* 初始化arena中的内存块数量 */
		desc_array[desc_idx].blocks_per_arena = (PG_SIZE - sizeof(struct arena)) / block_size;	  
		list_init(&desc_array[desc_idx].free_list);
		block_size *= 2;         // 更新为下一个规格内存块
	}
}


/* 内存管理部分初始化入口 */
void mem_init() 
{
	put_str("mem_init start\n");
	uint32_t mem_bytes_total = (*(uint32_t*)(0xb00));
	mem_pool_init(mem_bytes_total);	  // 初始化内存池
	/* 初始化mem_block_desc数组descs,为malloc做准备 */
	block_desc_init(k_block_descs);
	put_str("mem_init done\n");
}


/* 返回arena中第idx个内存块的地址 */
static struct mem_block* arena2block(struct arena* a, uint32_t idx) 
{
  	return (struct mem_block*)((uint32_t)a + sizeof(struct arena) + idx * a->desc->block_size);
}


/* 返回内存块b所在的arena地址 */
static struct arena* block2arena(struct mem_block* b) 
{
   	return (struct arena*)((uint32_t)b & 0xfffff000);
}


/* 在堆中申请size字节内存 */
void* sys_malloc(uint32_t size) 
{
	enum pool_flags PF;
	struct pool* mem_pool;
	uint32_t pool_size;
	struct mem_block_desc* descs;
	struct task_struct* cur_thread = running_thread();

	/* 判断用哪个内存池*/
	if (cur_thread->pgdir == NULL) 
	{     // 若为内核线程
		PF = PF_KERNEL; 
		pool_size = kernel_pool.pool_size;
		mem_pool = &kernel_pool;
		descs = k_block_descs;
	} 
	else 
	{				      // 用户进程pcb中的pgdir会在为其分配页表时创建
		PF = PF_USER;
		pool_size = user_pool.pool_size;
		mem_pool = &user_pool;
		descs = cur_thread->u_block_desc;
	}

	/* 若申请的内存不在内存池容量范围内则直接返回NULL */
	if (!(size > 0 && size < pool_size)) 
	{
		return NULL;
	}
	struct arena* a;
	struct mem_block* b;	
	lock_acquire(&mem_pool->lock);
	/* 超过最大内存块1024, 就分配页框 */
	if (size > 1024) 
	{
		uint32_t page_cnt = DIV_ROUND_UP(size + sizeof(struct arena), PG_SIZE);    // 向上取整需要的页框数

		a = malloc_page(PF, page_cnt);

		if (a != NULL) 
		{
			memset(a, 0, page_cnt * PG_SIZE);	 // 将分配的内存清0  

			/* 对于分配的大块页框,将desc置为NULL, cnt置为页框数,large置为true */
			a->desc = NULL;
			a->cnt = page_cnt;
			a->large = true;
			lock_release(&mem_pool->lock);
			return (void*)(a + 1);		 // 跨过arena大小，把剩下的内存返回
		} 
		else 
		{ 
			lock_release(&mem_pool->lock);
			return NULL; 
		}
	} 
	else 	// 若申请的内存小于等于1024,可在各种规格的mem_block_desc中去适配
	{    
		uint8_t desc_idx;
		
		/* 从内存块描述符中匹配合适的内存块规格 */
		for (desc_idx = 0; desc_idx < DESC_CNT; desc_idx++) 
		{
			if (size <= descs[desc_idx].block_size) 	// 从小往大后,找到后退出
			{  
				break;
			}
		}
			
		/* 若mem_block_desc的free_list中已经没有可用的mem_block,
		* 就创建新的arena提供mem_block */
		if (list_empty(&descs[desc_idx].free_list)) 
		{
			a = malloc_page(PF, 1);       // 分配1页框做为arena
			if (a == NULL) 
			{
				lock_release(&mem_pool->lock);
				return NULL;
			}
			memset(a, 0, PG_SIZE);

			/* 对于分配的小块内存,将desc置为相应内存块描述符, 
			* cnt置为此arena可用的内存块数,large置为false */
			a->desc = &descs[desc_idx];
			a->large = false;
			a->cnt = descs[desc_idx].blocks_per_arena;
			uint32_t block_idx;

			enum intr_status old_status = intr_disable();

			/* 开始将arena拆分成内存块,并添加到内存块描述符的free_list中 */
			for (block_idx = 0; block_idx < descs[desc_idx].blocks_per_arena; block_idx++) 
			{
				b = arena2block(a, block_idx);
				ASSERT(!elem_find(&a->desc->free_list, &b->free_elem));
				list_append(&a->desc->free_list, &b->free_elem);	
			}
			intr_set_status(old_status);
		}    
		/* 开始分配内存块 */
		b = elem2entry(struct mem_block, free_elem, list_pop(&(descs[desc_idx].free_list)));
		memset(b, 0, descs[desc_idx].block_size);

		a = block2arena(b);  // 获取内存块b所在的arena
		a->cnt--;		   // 将此arena中的空闲内存块数减1
		lock_release(&mem_pool->lock);
		return (void*)b;
   }
}

thread/thread.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
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
#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"
#include "list.h"
#include "bitmap.h"
#include "../kernel/memory.h"

#define TASK_NAME_LEN 16
#define MAX_FILES_OPEN_PER_PROC 8
/* 自定义通用函数类型,它将在很多线程函数中做为形参类型 */
typedef void thread_func(void*);
typedef int16_t pid_t;

/* 进程或线程的状态 */
enum task_status 
{
   TASK_RUNNING,
   TASK_READY,
   TASK_BLOCKED,
   TASK_WAITING,
   TASK_HANGING,
   TASK_DIED
};

/***********   中断栈intr_stack   ***********
 * 此结构用于中断发生时保护程序(线程或进程)的上下文环境:
 * 进程或线程被外部中断或软中断打断时,会按照此结构压入上下文
 * 寄存器,  intr_exit中的出栈操作是此结构的逆操作
 * 此栈在线程自己的内核栈中位置固定,所在页的最顶端
********************************************/
struct intr_stack 
{
    uint32_t vec_no;	 // kernel.S 宏VECTOR中push %1压入的中断号
    uint32_t edi;
    uint32_t esi;
    uint32_t ebp;
    uint32_t esp_dummy;	 // 虽然pushad把esp也压入,但esp是不断变化的,所以会被popad忽略
    uint32_t ebx;
    uint32_t edx;
    uint32_t ecx;
    uint32_t eax;
    uint32_t gs;
    uint32_t fs;
    uint32_t es;
    uint32_t ds;

/* 以下由cpu从低特权级进入高特权级时压入 */
    uint32_t err_code;		 // err_code会被压入在eip之后
    void (*eip) (void);
    uint32_t cs;
    uint32_t eflags;
    void* esp;
    uint32_t ss;
};

/***********  线程栈thread_stack  ***********
 * 线程自己的栈,用于存储线程中待执行的函数
 * 此结构在线程自己的内核栈中位置不固定,
 * 用在switch_to时保存线程环境。
 * 实际位置取决于实际运行情况。
 ******************************************/
struct thread_stack 
{
   uint32_t ebp;
   uint32_t ebx;
   uint32_t edi;
   uint32_t esi;

/* 线程第一次执行时,eip指向待调用的函数kernel_thread 
其它时候,eip是指向switch_to的返回地址*/
   void (*eip) (thread_func* func, void* func_arg);

/*****   以下仅供第一次被调度上cpu时使用   ****/

/* 参数unused_ret只为占位置充数为返回地址 */
   void (*unused_retaddr);
   thread_func* function;   // 由Kernel_thread所调用的函数名
   void* func_arg;    // 由Kernel_thread所调用的函数所需的参数
};

/* 进程或线程的pcb,程序控制块 */
struct task_struct 
{
   uint32_t* self_kstack;	 // 各内核线程都用自己的内核栈
   pid_t pid;
   enum task_status status;
   char name[TASK_NAME_LEN];
   uint8_t priority;
   uint8_t ticks;	   // 每次在处理器上执行的时间嘀嗒数
/* 此任务自上cpu运行后至今占用了多少cpu嘀嗒数,
 * 也就是此任务执行了多久*/
   uint32_t elapsed_ticks;
/* general_tag的作用是用于线程在一般的队列中的结点 */
   struct list_elem general_tag;				    
/* all_list_tag的作用是用于线程队列thread_all_list中的结点 */
   struct list_elem all_list_tag;
   uint32_t* pgdir;              // 进程自己页表的虚拟地址
   struct virtual_addr userprog_vaddr;   // 用户进程的虚拟地址 
   struct mem_block_desc u_block_desc[DESC_CNT];   // 用户进程内存块描述符
   uint32_t stack_magic;	 // 用这串数字做栈的边界标记,用于检测栈的溢出
};

extern struct list thread_ready_list;
extern struct list thread_all_list;

struct task_struct* running_thread(void);
static void kernel_thread(thread_func* function,void* func_arg);
void thread_create(struct task_struct* pthread,thread_func function,void* func_arg);
void init_thread(struct task_struct* pthread,char* name,int prio);
struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg);
static void make_main_thread(void);
void schedule(void);
void thread_init(void);
void thread_block(enum task_status stat);
void thread_unblock(struct task_struct* pthread);
static pid_t allocate_pid(void);

#endif

userprog/process.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
#include "tss.h"
#include "process.h"
#include "string.h"
#include "global.h"
#include "memory.h"
#include "print.h"
#include "../thread/thread.h"
#include "../kernel/interrupt.h"
#include "debug.h"
#include "../device/console.h"


extern void intr_exit(void);

/* 构建用户进程初始上下文信息 */
void start_process(void* filename_) 
{
	void* function = filename_;
	struct task_struct* cur = running_thread();
	cur->self_kstack += sizeof(struct thread_stack);
	struct intr_stack* proc_stack = (struct intr_stack*)cur->self_kstack;	 
	proc_stack->edi = proc_stack->esi = proc_stack->ebp = proc_stack->esp_dummy = 0;
	proc_stack->ebx = proc_stack->edx = proc_stack->ecx = proc_stack->eax = 0;
	proc_stack->gs = 0;		 // 用户态用不上,直接初始为0
	proc_stack->ds = proc_stack->es = proc_stack->fs = SELECTOR_U_DATA;
	proc_stack->eip = function;	 // 待执行的用户程序地址
	proc_stack->cs = SELECTOR_U_CODE;
	proc_stack->eflags = (EFLAGS_IOPL_0 | EFLAGS_MBS | EFLAGS_IF_1);
	proc_stack->esp = (void*)((uint32_t)get_a_page(PF_USER, USER_STACK3_VADDR) + PG_SIZE);
	proc_stack->ss = SELECTOR_U_DATA; 
	asm volatile ("movl %0, %%esp; jmp intr_exit" : : "g" (proc_stack) : "memory");
}

/* 击活页表 */
void page_dir_activate(struct task_struct* p_thread) 
{
/********************************************************
 * 执行此函数时,当前任务可能是线程。
 * 之所以对线程也要重新安装页表, 原因是上一次被调度的可能是进程,
 * 否则不恢复页表的话,线程就会使用进程的页表了。
 ********************************************************/

/* 若为内核线程,需要重新填充页表为0x100000 */
	uint32_t pagedir_phy_addr = 0x100000;  // 默认为内核的页目录物理地址,也就是内核线程所用的页目录表
	if (p_thread->pgdir != NULL)		 // 用户态进程有自己的页目录表	
	{   
		pagedir_phy_addr = addr_v2p((uint32_t)p_thread->pgdir);
	}

	/* 更新页目录寄存器cr3,使新页表生效 */
	asm volatile ("movl %0, %%cr3" : : "r" (pagedir_phy_addr) : "memory");
}

/* 击活线程或进程的页表,更新tss中的esp0为进程的特权级0的栈 */
void process_activate(struct task_struct* p_thread) 
{
	ASSERT(p_thread != NULL);
	/* 击活该进程或线程的页表 */
	page_dir_activate(p_thread);

	/* 内核线程特权级本身就是0,处理器进入中断时并不会从tss中获取0特权级栈地址,故不需要更新esp0 */
	if (p_thread->pgdir) 
	{
		/* 更新该进程的esp0,用于此进程被中断时保留上下文 */
		update_tss_esp(p_thread);
	}
}

/* 创建页目录表,将当前页表的表示内核空间的pde复制,
 * 成功则返回页目录的虚拟地址,否则返回-1 */
uint32_t* create_page_dir(void) 
{

   /* 用户进程的页表不能让用户直接访问到,所以在内核空间来申请 */
	uint32_t* page_dir_vaddr = get_kernel_pages(1);
	if (page_dir_vaddr == NULL) 
	{
		console_put_str("create_page_dir: get_kernel_page failed!");
		return NULL;
	}

/************************** 1  先复制页表  *************************************/
   /*  page_dir_vaddr + 0x300*4 是内核页目录的第768项 */
   	memcpy((uint32_t*)((uint32_t)page_dir_vaddr + 0x300*4), (uint32_t*)(0xfffff000+0x300*4), 1024);
/*****************************************************************************/

/************************** 2  更新页目录地址 **********************************/
   	uint32_t new_page_dir_phy_addr = addr_v2p((uint32_t)page_dir_vaddr);
   	/* 页目录地址是存入在页目录的最后一项,更新页目录地址为新页目录的物理地址 */
   	page_dir_vaddr[1023] = new_page_dir_phy_addr | PG_US_U | PG_RW_W | PG_P_1;
/*****************************************************************************/
   	return page_dir_vaddr;
}

/* 创建用户进程虚拟地址位图 */
void create_user_vaddr_bitmap(struct task_struct* user_prog) 
{
	user_prog->userprog_vaddr.vaddr_start = USER_VADDR_START;
	uint32_t bitmap_pg_cnt = DIV_ROUND_UP((0xc0000000 - USER_VADDR_START) / PG_SIZE / 8 , PG_SIZE);
	user_prog->userprog_vaddr.vaddr_bitmap.bits = get_kernel_pages(bitmap_pg_cnt);
	user_prog->userprog_vaddr.vaddr_bitmap.btmp_bytes_len = (0xc0000000 - USER_VADDR_START) / PG_SIZE / 8;
	bitmap_init(&user_prog->userprog_vaddr.vaddr_bitmap);
}

/* 创建用户进程 */
void process_execute(void* filename, char* name) 
{ 
	/* pcb内核的数据结构,由内核来维护进程信息,因此要在内核内存池中申请 */
	struct task_struct* thread = get_kernel_pages(1);
	init_thread(thread, name, default_prio); 
	create_user_vaddr_bitmap(thread);
	thread_create(thread, start_process, filename);
	/* pcb内核的数据结构,由内核来维护进程信息,因此要在内核内存池中申请 */
	thread->pgdir = create_page_dir();
	block_desc_init(thread->u_block_desc);

	enum intr_status old_status = intr_disable();
	ASSERT(!elem_find(&thread_ready_list, &thread->general_tag));
	list_append(&thread_ready_list, &thread->general_tag);

	ASSERT(!elem_find(&thread_all_list, &thread->all_list_tag));
	list_append(&thread_all_list, &thread->all_list_tag);
	intr_set_status(old_status);
}

kernel/main.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
#include "print.h"
#include "init.h"
#include "debug.h"
#include "string.h"
#include "memory.h"
#include "../thread/thread.h"
#include "interrupt.h"
#include "../device/console.h"
#include "../device/ioqueue.h"
#include "../device/keyboard.h"
#include "../userprog/process.h"
#include "../lib/user/syscall.h"
#include "../userprog/syscall-init.h"
#include "../lib/stdio.h"


void k_thread_a(void* );
void k_thread_b(void* );
int main(void) {
   put_str("I am kernel\n");
   init_all();

   intr_enable();
	thread_start("k_thread_a", 31, k_thread_a, "argA ");
	thread_start("k_thread_b", 31, k_thread_b, "argB ");
	while(1);
   return 0;
}

void k_thread_a(void* arg){
	char* para = arg;
	void* addr = sys_malloc(33);
	console_put_str("  I am thread_a, sys_malloc(33), addr is 0x");
   console_put_int((int)addr);
   console_put_char('\n');
	while(1);
}

void k_thread_b(void* arg){
	char* para = arg;
	void* addr = sys_malloc(63);
	console_put_str("  I am thread_b, sys_malloc(63), addr is 0x");
   console_put_int((int)addr);
   console_put_char('\n');
	while(1);
}

运行结果

图为bochs运行界面

kernel/memory.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
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
#ifndef __KERNEL_MEMORY_H
#define __KERNEL_MEMORY_H
#include "stdint.h"
#include "bitmap.h"
#include "list.h"

/* 内存池标记,用于判断用哪个内存池 */
enum pool_flags {
	PF_KERNEL = 1,    // 内核内存池
	PF_USER = 2	     // 用户内存池
};

#define	 PG_P_1	  1	// 页表项或页目录项存在属性位
#define	 PG_P_0	  0	// 页表项或页目录项存在属性位
#define	 PG_RW_R  0	// R/W 属性位值, 读/执行
#define	 PG_RW_W  2	// R/W 属性位值, 读/写/执行
#define	 PG_US_S  0	// U/S 属性位值, 系统级
#define	 PG_US_U  4	// U/S 属性位值, 用户级
#define  DESC_CNT 7

/* 用于虚拟地址管理 */
struct virtual_addr {
/* 虚拟地址用到的位图结构，用于记录哪些虚拟地址被占用了。以页为单位。*/
  	struct bitmap vaddr_bitmap;
/* 管理的虚拟地址 */
  	uint32_t vaddr_start;
};


/* 内存块 */
struct mem_block {
   	struct list_elem free_elem;
};

/* 内存块描述符 */
struct mem_block_desc {
	uint32_t block_size;		 // 内存块大小
	uint32_t blocks_per_arena;	 // 本arena中可容纳此mem_block的数量.
	struct list free_list;	 // 目前可用的mem_block链表
};

extern struct pool kernel_pool,user_pool;
static void* vaddr_get(enum pool_flags pf,uint32_t pg_cnt);
uint32_t* pte_ptr(uint32_t vaddr);
uint32_t* pde_ptr(uint32_t vaddr);
static void* palloc(struct pool* m_pool);
static void page_table_add(void* _vaddr,void* _page_phyaddr);
void* malloc_page(enum pool_flags pf,uint32_t pg_cnt);
void* get_kernel_pages(uint32_t pg_cnt);
void* get_user_pages(uint32_t pg_cnt);
void* get_a_page(enum pool_flags pf,uint32_t vaddr);
uint32_t addr_v2p(uint32_t vaddr);
static void mem_pool_init(uint32_t all_mem);
void mem_init(void);
void block_desc_init(struct mem_block_desc* desc_array);
//static struct mem_block* arena2block(struct arena* a, uint32_t idx);
//static struct arena* block2arena(struct mem_block* b);
void* sys_malloc(uint32_t size);
void pfree(uint32_t pg_phy_addr);
static void page_table_pte_remove(uint32_t vaddr);
static void vaddr_remove(enum pool_flags pf,void* _vaddr,uint32_t pg_cnt);
void mfree_page(enum pool_flags pf,void* _vaddr,uint32_t pg_cnt);
void sys_free(void* ptr);


#endif

kernel/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
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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
#include "memory.h"
#include "bitmap.h"
#include "stdint.h"
#include "global.h"
#include "debug.h"
#include "print.h"
#include "string.h"
#include "interrupt.h"
#include "../thread/sync.h"
#include "../thread/thread.h"

#define PG_SIZE 4096

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

#define PDE_IDX(addr) ((addr & 0xffc00000) >> 22)
#define PTE_IDX(addr) ((addr & 0x003ff000) >> 12)

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

/* 内存池结构,生成两个实例用于管理内核内存池和用户内存池 */
struct pool 
{
	struct bitmap pool_bitmap;	 // 本内存池用到的位图结构,用于管理物理内存
  	uint32_t phy_addr_start;	 // 本内存池所管理物理内存的起始地址
  	uint32_t pool_size;		 // 本内存池字节容量
	struct lock lock;		 // 申请内存时互斥
};
/* 内存仓库arena元信息 */
struct arena 
{
   struct mem_block_desc* desc;	 // 此arena关联的mem_block_desc
/* large为ture时,cnt表示的是页框数。
 * 否则cnt表示空闲mem_block数量 */
   uint32_t cnt;
   bool large;		   
};
struct mem_block_desc k_block_descs[DESC_CNT];	// 内核内存块描述符数组
struct pool kernel_pool, user_pool;      // 生成内核内存池和用户内存池
struct virtual_addr kernel_vaddr;	 // 此结构是用来给内核分配虚拟地址


/* 在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) 
		{
	 		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;
   	} 
	else // 用户内存池
	{	     	
      	struct task_struct* cur = running_thread();
      	bit_idx_start  = bitmap_scan(&cur->userprog_vaddr.vaddr_bitmap, pg_cnt);
      	if (bit_idx_start == -1) 
		{
	 		return NULL;
      	}
      	while(cnt < pg_cnt) 
		{
	 		bitmap_set(&cur->userprog_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 1);
      	}
      	vaddr_start = cur->userprog_vaddr.vaddr_start + bit_idx_start * PG_SIZE;

   /* (0xc0000000 - PG_SIZE)做为用户3级栈已经在start_process被分配 */
      	ASSERT((uint32_t)vaddr_start < (0xc0000000 - PG_SIZE));
   	}
   	return (void*)vaddr_start;
}


/* 得到虚拟地址vaddr对应的pte指针*/
uint32_t* pte_ptr(uint32_t vaddr) 
{
  /* 先访问到页表自己 + \
   * 再用页目录项pde(页目录内页表的索引)做为pte的索引访问到页表 + \
   * 再用pte的索引做为页内偏移*/
  	uint32_t* pte = (uint32_t*)(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个物理页,
* 成功则返回页框的物理地址,失败则返回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);
  	return (void*)page_phyaddr;
}


/* 页表中添加虚拟地址_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未创建时,
* *pte只能出现在下面最外层else语句块中的*pde后面。
* *********************************************************/
  /* 先在页目录内判断目录项的P位，若为1,则表示该表已存在 */
  	if (*pde & 0x00000001) 
	{
     	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会起作用
		{	  
    		PANIC("pte repeat");
     	}
  	} 
	else 	// 页目录项不存在,所以要先创建页目录项再创建页表项.
	{	  
     	/* 页表中用到的页框一律从内核空间分配 */
     	uint32_t pde_phyaddr = (uint32_t)palloc(&kernel_pool);
     	*pde = (pde_phyaddr | PG_US_U | PG_RW_W | PG_P_1);

/*******************   必须将页表所在的页清0   *********************
* 必须把分配到的物理页地址pde_phyaddr对应的物理内存清0,
* 避免里面的陈旧数据变成了页表中的页表项,从而让页表混乱.
* pte的高20位会映射到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
  	}
}


/* 分配pg_cnt个页空间,成功则返回起始虚拟地址,失败时返回NULL */
void* malloc_page(enum pool_flags pf, uint32_t pg_cnt) 
{
  	ASSERT(pg_cnt > 0 && pg_cnt < 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页内存,
* 成功则返回其虚拟地址,失败则返回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;
}


/* 在用户空间中申请4k内存,并返回其虚拟地址 */
void* get_user_pages(uint32_t pg_cnt) 
{
   	lock_acquire(&user_pool.lock);
   	void* vaddr = malloc_page(PF_USER, pg_cnt);
   	if (vaddr != NULL) 		// 若分配的地址不为空,将页框清0后返回
	{	   
      	memset(vaddr, 0, pg_cnt * PG_SIZE);
   	}
   	lock_release(&user_pool.lock);
   	return vaddr;
}


/* 将地址vaddr与pf池中的物理地址关联,仅支持一页空间分配 */
void* get_a_page(enum pool_flags pf, uint32_t vaddr) 
{
   	struct pool* mem_pool = pf & PF_KERNEL ? &kernel_pool : &user_pool;
   	lock_acquire(&mem_pool->lock);

   	/* 先将虚拟地址对应的位图置1 */
   	struct task_struct* cur = running_thread();
   	int32_t bit_idx = -1;

/* 若当前是用户进程申请用户内存,就修改用户进程自己的虚拟地址位图 */
   	if (cur->pgdir != NULL && pf == PF_USER) 
	{
      	bit_idx = (vaddr - cur->userprog_vaddr.vaddr_start) / PG_SIZE;
      	ASSERT(bit_idx >= 0);
      	bitmap_set(&cur->userprog_vaddr.vaddr_bitmap, bit_idx, 1);
   	} 
	else if (cur->pgdir == NULL && pf == PF_KERNEL)
	{
/* 如果是内核线程申请内核内存,就修改kernel_vaddr. */
      	bit_idx = (vaddr - kernel_vaddr.vaddr_start) / PG_SIZE;
      	ASSERT(bit_idx > 0);
      	bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx, 1);
   	} 
	else 
	{
      	PANIC("get_a_page:not allow kernel alloc userspace or user alloc kernelspace by get_a_page");
   	}

   	void* page_phyaddr = palloc(mem_pool);
   	if (page_phyaddr == NULL) 
	{
      	lock_release(&mem_pool->lock);
      	return NULL;
   	}
   	page_table_add((void*)vaddr, page_phyaddr); 
   	lock_release(&mem_pool->lock);
   	return (void*)vaddr;
}


/* 得到虚拟地址映射到的物理地址 */
uint32_t addr_v2p(uint32_t vaddr) 
{
   	uint32_t* pte = pte_ptr(vaddr);
/* (*pte)的值是页表所在的物理页框地址,
 * 去掉其低12位的页表项属性+虚拟地址vaddr的低12位 */
   	return ((*pte & 0xfffff000) + (vaddr & 0x00000fff));
}


/* 初始化内存池 */
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为低端1M内存
  	uint32_t free_mem = all_mem - used_mem;
  	uint16_t all_free_pages = free_mem / PG_SIZE;		  // 1页为4k,不管总内存是不是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,这是主线程的栈地址.(内核的大小预计为70K左右)
// 32M内存占用的位图是2k.内核内存池的位图先定在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);
	lock_init(&kernel_pool.lock);
  	lock_init(&user_pool.lock);
  	put_str("   mem_pool_init done\n");
}


/* 为malloc做准备 */
void block_desc_init(struct mem_block_desc* desc_array) 
{				   
	uint16_t desc_idx, block_size = 16;
	/* 初始化每个mem_block_desc描述符 */
	for (desc_idx = 0; desc_idx < DESC_CNT; desc_idx++) 
	{
		desc_array[desc_idx].block_size = block_size;
		/* 初始化arena中的内存块数量 */
		desc_array[desc_idx].blocks_per_arena = (PG_SIZE - sizeof(struct arena)) / block_size;	  
		list_init(&desc_array[desc_idx].free_list);
		block_size *= 2;         // 更新为下一个规格内存块
	}
}


/* 内存管理部分初始化入口 */
void mem_init() 
{
	put_str("mem_init start\n");
	uint32_t mem_bytes_total = (*(uint32_t*)(0xb00));
	mem_pool_init(mem_bytes_total);	  // 初始化内存池
	/* 初始化mem_block_desc数组descs,为malloc做准备 */
	block_desc_init(k_block_descs);
	put_str("mem_init done\n");
}


/* 返回arena中第idx个内存块的地址 */
static struct mem_block* arena2block(struct arena* a, uint32_t idx) 
{
  	return (struct mem_block*)((uint32_t)a + sizeof(struct arena) + idx * a->desc->block_size);
}


/* 返回内存块b所在的arena地址 */
static struct arena* block2arena(struct mem_block* b) 
{
   	return (struct arena*)((uint32_t)b & 0xfffff000);
}


/* 在堆中申请size字节内存 */
void* sys_malloc(uint32_t size) 
{
	enum pool_flags PF;
	struct pool* mem_pool;
	uint32_t pool_size;
	struct mem_block_desc* descs;
	struct task_struct* cur_thread = running_thread();

	/* 判断用哪个内存池*/
	if (cur_thread->pgdir == NULL) 
	{     // 若为内核线程
		PF = PF_KERNEL; 
		pool_size = kernel_pool.pool_size;
		mem_pool = &kernel_pool;
		descs = k_block_descs;
	} 
	else 
	{				      // 用户进程pcb中的pgdir会在为其分配页表时创建
		PF = PF_USER;
		pool_size = user_pool.pool_size;
		mem_pool = &user_pool;
		descs = cur_thread->u_block_desc;
	}

	/* 若申请的内存不在内存池容量范围内则直接返回NULL */
	if (!(size > 0 && size < pool_size)) 
	{
		return NULL;
	}
	struct arena* a;
	struct mem_block* b;	
	lock_acquire(&mem_pool->lock);
	/* 超过最大内存块1024, 就分配页框 */
	if (size > 1024) 
	{
		uint32_t page_cnt = DIV_ROUND_UP(size + sizeof(struct arena), PG_SIZE);    // 向上取整需要的页框数

		a = malloc_page(PF, page_cnt);

		if (a != NULL) 
		{
			memset(a, 0, page_cnt * PG_SIZE);	 // 将分配的内存清0  

			/* 对于分配的大块页框,将desc置为NULL, cnt置为页框数,large置为true */
			a->desc = NULL;
			a->cnt = page_cnt;
			a->large = true;
			lock_release(&mem_pool->lock);
			return (void*)(a + 1);		 // 跨过arena大小，把剩下的内存返回
		} 
		else 
		{ 
			lock_release(&mem_pool->lock);
			return NULL; 
		}
	} 
	else 	// 若申请的内存小于等于1024,可在各种规格的mem_block_desc中去适配
	{    
		uint8_t desc_idx;
		
		/* 从内存块描述符中匹配合适的内存块规格 */
		for (desc_idx = 0; desc_idx < DESC_CNT; desc_idx++) 
		{
			if (size <= descs[desc_idx].block_size) 	// 从小往大后,找到后退出
			{  
				break;
			}
		}
			
		/* 若mem_block_desc的free_list中已经没有可用的mem_block,
		* 就创建新的arena提供mem_block */
		if (list_empty(&descs[desc_idx].free_list)) 
		{
			a = malloc_page(PF, 1);       // 分配1页框做为arena
			if (a == NULL) 
			{
				lock_release(&mem_pool->lock);
				return NULL;
			}
			memset(a, 0, PG_SIZE);

			/* 对于分配的小块内存,将desc置为相应内存块描述符, 
			* cnt置为此arena可用的内存块数,large置为false */
			a->desc = &descs[desc_idx];
			a->large = false;
			a->cnt = descs[desc_idx].blocks_per_arena;
			uint32_t block_idx;

			enum intr_status old_status = intr_disable();

			/* 开始将arena拆分成内存块,并添加到内存块描述符的free_list中 */
			for (block_idx = 0; block_idx < descs[desc_idx].blocks_per_arena; block_idx++) 
			{
				b = arena2block(a, block_idx);
				ASSERT(!elem_find(&a->desc->free_list, &b->free_elem));
				list_append(&a->desc->free_list, &b->free_elem);	
			}
			intr_set_status(old_status);
		}    
		/* 开始分配内存块 */
		b = elem2entry(struct mem_block, free_elem, list_pop(&(descs[desc_idx].free_list)));
		memset(b, 0, descs[desc_idx].block_size);

		a = block2arena(b);  // 获取内存块b所在的arena
		a->cnt--;		   // 将此arena中的空闲内存块数减1
		lock_release(&mem_pool->lock);
		return (void*)b;
   }
}


/* 将物理地址pg_phy_addr回收到物理内存池 */
void pfree(uint32_t pg_phy_addr) 
{
	struct pool* mem_pool;
	uint32_t bit_idx = 0;
	if (pg_phy_addr >= user_pool.phy_addr_start) 	// 用户物理内存池
	{     
		mem_pool = &user_pool;
		bit_idx = (pg_phy_addr - user_pool.phy_addr_start) / PG_SIZE;
	} 
	else 			// 内核物理内存池
	{	  
		mem_pool = &kernel_pool;
		bit_idx = (pg_phy_addr - kernel_pool.phy_addr_start) / PG_SIZE;
	}
	bitmap_set(&mem_pool->pool_bitmap, bit_idx, 0);	 // 将位图中该位清0
}


/* 去掉页表中虚拟地址vaddr的映射,只去掉vaddr对应的pte */
static void page_table_pte_remove(uint32_t vaddr) 
{
	uint32_t* pte = pte_ptr(vaddr);
	*pte &= ~PG_P_1;	// 将页表项pte的P位置0
	asm volatile ("invlpg %0"::"m" (vaddr):"memory");    //更新tlb
}


/* 在虚拟地址池中释放以_vaddr起始的连续pg_cnt个虚拟页地址 */
static void vaddr_remove(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt) 
{
	uint32_t bit_idx_start = 0, vaddr = (uint32_t)_vaddr, cnt = 0;

	if (pf == PF_KERNEL) 		// 内核虚拟内存池
	{  
		bit_idx_start = (vaddr - kernel_vaddr.vaddr_start) / PG_SIZE;
		while(cnt < pg_cnt) 
		{
			bitmap_set(&kernel_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 0);
		}
	} 
	else 		// 用户虚拟内存池
	{  
		struct task_struct* cur_thread = running_thread();
		bit_idx_start = (vaddr - cur_thread->userprog_vaddr.vaddr_start) / PG_SIZE;
		while(cnt < pg_cnt) 
		{
			bitmap_set(&cur_thread->userprog_vaddr.vaddr_bitmap, bit_idx_start + cnt++, 0);
		}
	}
}


/* 释放以虚拟地址vaddr为起始的cnt个物理页框 */
void mfree_page(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt) 
{
	uint32_t pg_phy_addr;
	uint32_t vaddr = (int32_t)_vaddr, page_cnt = 0;
	ASSERT(pg_cnt >=1 && vaddr % PG_SIZE == 0); 
	pg_phy_addr = addr_v2p(vaddr);  // 获取虚拟地址vaddr对应的物理地址

/* 确保待释放的物理内存在低端1M+1k大小的页目录+1k大小的页表地址范围外 */
   	ASSERT((pg_phy_addr % PG_SIZE) == 0 && pg_phy_addr >= 0x102000);
   
/* 判断pg_phy_addr属于用户物理内存池还是内核物理内存池 */
   	if (pg_phy_addr >= user_pool.phy_addr_start) 			// 位于user_pool内存池
	{   
		vaddr -= PG_SIZE;
		while (page_cnt < pg_cnt) 
		{
			vaddr += PG_SIZE;
			pg_phy_addr = addr_v2p(vaddr);

			/* 确保物理地址属于用户物理内存池 */
			ASSERT((pg_phy_addr % PG_SIZE) == 0 && pg_phy_addr >= user_pool.phy_addr_start);

			/* 先将对应的物理页框归还到内存池 */
			pfree(pg_phy_addr);

			/* 再从页表中清除此虚拟地址所在的页表项pte */
			page_table_pte_remove(vaddr);

			page_cnt++;
		}
   		/* 清空虚拟地址的位图中的相应位 */
      	vaddr_remove(pf, _vaddr, pg_cnt);
	} 
	else 			// 位于kernel_pool内存池
	{	     
		vaddr -= PG_SIZE;	      
		while (page_cnt < pg_cnt) 
		{
			vaddr += PG_SIZE;
			pg_phy_addr = addr_v2p(vaddr);
			/* 确保待释放的物理内存只属于内核物理内存池 */
			ASSERT((pg_phy_addr % PG_SIZE) == 0 && \
				pg_phy_addr >= kernel_pool.phy_addr_start && \
				pg_phy_addr < user_pool.phy_addr_start);
			
			/* 先将对应的物理页框归还到内存池 */
			pfree(pg_phy_addr);

			/* 再从页表中清除此虚拟地址所在的页表项pte */
			page_table_pte_remove(vaddr);

			page_cnt++;
		}
		/* 清空虚拟地址的位图中的相应位 */
		vaddr_remove(pf, _vaddr, pg_cnt);
   }
}


/* 回收内存ptr */
void sys_free(void* ptr) 
{
	ASSERT(ptr != NULL);
	if (ptr != NULL) 
	{
		enum pool_flags PF;
		struct pool* mem_pool;

		/* 判断是线程还是进程 */
		if (running_thread()->pgdir == NULL) 
		{
			ASSERT((uint32_t)ptr >= K_HEAP_START);
			PF = PF_KERNEL; 
			mem_pool = &kernel_pool;
		} 
		else 
		{
			PF = PF_USER;
			mem_pool = &user_pool;
		}

		lock_acquire(&mem_pool->lock);   
		struct mem_block* b = ptr;
		struct arena* a = block2arena(b);	     // 把mem_block转换成arena,获取元信息
		ASSERT(a->large == 0 || a->large == 1);
		if (a->desc == NULL && a->large == true) 		// 大于1024的内存
		{ 
			mfree_page(PF, a, a->cnt); 
		} 
		else 		// 小于等于1024的内存块 
		{				 
			/* 先将内存块回收到free_list */
			list_append(&a->desc->free_list, &b->free_elem);

			/* 再判断此arena中的内存块是否都是空闲,如果是就释放arena */
			if (++a->cnt == a->desc->blocks_per_arena) 
			{
				uint32_t block_idx;
				for (block_idx = 0; block_idx < a->desc->blocks_per_arena; block_idx++) 
				{
					struct mem_block*  b = arena2block(a, block_idx);
					ASSERT(elem_find(&a->desc->free_list, &b->free_elem));
					list_remove(&b->free_elem);
				}
				mfree_page(PF, a, 1); 
			} 
		}   
		lock_release(&mem_pool->lock); 
   	}
}

lib/user/syscall.h修改

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

enum SYSCALL_NR 
{
   SYS_GETPID,
   SYS_WRITE,
   SYS_MALLOC,
   SYS_FREE
};
uint32_t getpid(void);
uint32_t write(char* str);
void* malloc(uint32_t size);
void free(void* ptr);
#endif

lib/user/syscall.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
#include "syscall.h"

/* 无参数的系统调用 */
#define _syscall0(NUMBER) ({				       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER)					       \
   : "memory"						       \
   );							       \
   retval;						       \
})


/* 一个参数的系统调用 */
#define _syscall1(NUMBER, ARG1) ({			       \
   int retval;					               \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1)				       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 两个参数的系统调用 */
#define _syscall2(NUMBER, ARG1, ARG2) ({		       \
   int retval;						       \
   asm volatile (					       \
   "int $0x80"						       \
   : "=a" (retval)					       \
   : "a" (NUMBER), "b" (ARG1), "c" (ARG2)		       \
   : "memory"						       \
   );							       \
   retval;						       \
})

/* 三个参数的系统调用 */
#define _syscall3(NUMBER, ARG1, ARG2, ARG3) ({		       \
   int retval;						       \
   asm volatile (					       \
      "int $0x80"					       \
      : "=a" (retval)					       \
      : "a" (NUMBER), "b" (ARG1), "c" (ARG2), "d" (ARG3)       \
      : "memory"					       \
   );							       \
   retval;						       \
})

/* 返回当前任务pid */
uint32_t getpid() 
{
   return _syscall0(SYS_GETPID);
}

uint32_t write(char* str)
{
    return _syscall1(SYS_WRITE,str);
}

void* malloc(uint32_t size)
{
   return (void*)_syscall1(SYS_MALLOC, size);
}

void free(void* ptr)
{
   _syscall1(SYS_FREE, ptr);
}

userprog/syscall-init.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
#include "syscall-init.h"
#include "../lib/user/syscall.h"
#include "stdint.h"
#include "print.h"
#include "interrupt.h"
#include "../thread/thread.h"
#include "../kernel/memory.h"


#define syscall_nr 32 
typedef void* syscall;
syscall syscall_table[syscall_nr];

/* 返回当前任务的pid */
uint32_t sys_getpid(void) 
{
   	return running_thread()->pid;
}

void sys_write(char* str)
{
   	console_put_str(str);
}

/* 初始化系统调用 */
void syscall_init(void) 
{
	put_str("syscall_init start\n");
	syscall_table[SYS_GETPID] = sys_getpid;
	syscall_table[SYS_WRITE] = sys_write;
	syscall_table[SYS_MALLOC] = sys_malloc;
	syscall_table[SYS_FREE] = sys_free;
	put_str("syscall_init done\n");
}

kernel/main.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
#include "print.h"
#include "init.h"
#include "debug.h"
#include "string.h"
#include "memory.h"
#include "../thread/thread.h"
#include "interrupt.h"
#include "../device/console.h"
#include "../device/ioqueue.h"
#include "../device/keyboard.h"
#include "../userprog/process.h"
#include "../lib/user/syscall.h"
#include "../userprog/syscall-init.h"
#include "../lib/stdio.h"


void k_thread_a(void* );
void k_thread_b(void* );
void u_prog_a (void);
void u_prog_b (void);

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

   intr_enable();
   process_execute(u_prog_a, "u_prog_a");
   process_execute(u_prog_b, "u_prog_b");   
	thread_start("k_thread_a", 31, k_thread_a, "argA ");
	thread_start("k_thread_b", 31, k_thread_b, "argB ");
	while(1);
   return 0;
}

void k_thread_a(void* arg){

	void* addr1 = sys_malloc(256);
	void* addr2 = sys_malloc(255);
	void* addr3 = sys_malloc(254);
	console_put_str(" thread_a malloc addr:0x");
	console_put_int((int)addr1);
	console_put_char(',');
	console_put_int((int)addr2);
	console_put_char(',');
	console_put_int((int)addr3);
	console_put_char('\n');
	int cpu_delay = 100000;
	while(cpu_delay-->0);
	sys_free(addr1);
	sys_free(addr2);
	sys_free(addr3);
	while(1);
}

void k_thread_b(void* arg){
	void* addr1 = sys_malloc(256);
	void* addr2 = sys_malloc(255);
	void* addr3 = sys_malloc(254);
	console_put_str(" thread_b malloc addr:0x");
	console_put_int((int)addr1);
	console_put_char(',');
	console_put_int((int)addr2);
	console_put_char(',');
	console_put_int((int)addr3);
	console_put_char('\n');
	int cpu_delay = 100000;
	while(cpu_delay-->0);
	sys_free(addr1);
	sys_free(addr2);
	sys_free(addr3);
	while(1);
}

void u_prog_a(void) {
	void* addr1 = malloc(256);
	void* addr2 = malloc(255);
	void* addr3 = malloc(254);
	printf(" prog_a malloc addr:0x%x, 0x%x, 0x%x\n", (int)addr1,(int)addr2,(int)addr3);
	int cpu_delay = 100000;
	while(cpu_delay-->0);
	free(addr1);
	free(addr2);
	free(addr3);
	while(1);
}

void u_prog_b(void) {
	void* addr1 = malloc(256);
	void* addr2 = malloc(255);
	void* addr3 = malloc(254);
	printf(" prog_b malloc addr:0x%x, 0x%x, 0x%x\n", (int)addr1,(int)addr2,(int)addr3);
	int cpu_delay = 100000;
	while(cpu_delay-->0);
	free(addr1);
	free(addr2);
	free(addr3);
	while(1);
}

运行结果

图为bochs运行界面

写在后面

这章内容也太多了，不过原理理解起来不是那么困难，还剩三章就一口气做完吧！