简单内核实现笔记-part-3

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 64k | 阅读时长 ≈ 58 分钟

进程与线程

线程和进程的概念不用多说大家肯定都比较熟悉，线程是具有能动性、执行力、独立性的代码块。进程 = 线程+资源。那么下面代码中你能区别普通函数和线程函数的区别么？我们知道普通的函数之间发生函数调用的时候，要进行压栈的一系列操作，然后调用，它需要依赖程序上下文的环境。而线程函数则是自己提供一套上下文环境，使其更加具有独立性的在处理器上执行。二者的区别也主要是上下文环境。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void threadFunc(void *arg)
{
	printf("this is thread\n");
}

void func()
{
	printf("this is function\n");
}

int main()
{
	printf("this is main\n");
	
	_beginthread(threadFunc, 0, NULL);
	func();
	
	return 0;
}

我们再来说说进程，操作系统为每个进程提供了一个PCB，用于记录此进程相关的信息，所有进程的PCB形成了一张表，这就是进程表，我们自己写的操作系统中PCB的结构是不固定的，其大致内容有寄存器映像、栈、pid、进程状态、优先级、父进程等，为了实现它，我们先创建thread目录，然后创建thread.c和.h文件，下面是PCB的结构，位于.h文件中

1
2
3
4
5
6
7
8
/* 进程或线程的pcb,程序控制块 */
struct task_struct {
   uint32_t* self_kstack;	 // 各内核线程都用自己的内核栈
   enum task_status status;  // 记录线程状态
   uint8_t priority;		 // 线程优先级
   char name[16];
   uint32_t stack_magic;	 // 用这串数字做栈的边界标记,用于检测栈的溢出
};

我们的线程是在内核中实现的，所以申请PCB结构的时候是从内核池进行操作的，下面看看初始化的内容，主要内容是给PCB的各字段赋值

1
2
3
4
5
6
7
8
9
10
/* 初始化线程基本信息 */
void init_thread(struct task_struct* pthread, char* name, int prio) {
   memset(pthread, 0, sizeof(*pthread));
   strcpy(pthread->name, name);
   pthread->status = TASK_RUNNING; 
   pthread->priority = prio;
/* self_kstack是线程自己在内核态下使用的栈顶地址 */
   pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
   pthread->stack_magic = 0x19870916;	  // 自定义的魔数
}

然后用thread_create初始化栈thread_stack，其中减去的操作主要是为了以后预留保存现场的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 初始化线程栈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;
}

上面的function即使线程所执行的函数，这个函数并不是用call去调用，我们用的是ret指令进行调用，CPU执行哪条指令是通过EIP的指向来决定的，而ret指令在返回的时候，当前的栈顶就会被当做是返回地址。也就是说，我们可以把某个函数的地址放在栈顶，通过这个函数来执行线程函数。那么在ret返回的时候，就会进入我们指定的函数当中，这个函数就会来调用线程函数。下面就是启动线程的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 由kernel_thread去执行function(func_arg) */
static void kernel_thread(thread_func* function, void* func_arg) {
   function(func_arg); 
}

/* 创建一优先级为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);  // 申请一页内存用于放PCB

   init_thread(thread, name, prio);
   thread_create(thread, function, func_arg);
	
   // ret的时候栈顶为kernel_thread进而去执行该函数
   asm volatile ("movl %0, %%esp; pop %%ebp; pop %%ebx; pop %%edi; pop %%esi; ret" : : "g" (thread->self_kstack) : "memory");
   return thread;
}

为了实验我们还需要在main.c中对thread_start进行调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "print.h"
#include "init.h"
#include "thread.h"

void k_thread_a(void*);

int main(void) {
   put_str("Welcome to TJ's kernel!\n");
   init_all();

   thread_start("k_thread_a", 31, k_thread_a, "argA ");

   while(1);
   return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {     
/* 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用 */
   char* para = arg;
   while(1) {
      put_str(para);
   }
}

编译运行结果如下所示，测试成功

image-20200526104424200

多线程调度

为了提高效率，实现多线程调度，我们需要用数据结构对内核线程结构进行维护，首先我们需要在lib/kernel目录下增加队列结构

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
#include "list.h"
#include "interrupt.h"

/* 初始化双向链表list */
void list_init (struct list* list) {
   list->head.prev = NULL;
   list->head.next = &list->tail;
   list->tail.prev = &list->head;
   list->tail.next = NULL;
}

/* 把链表元素elem插入在元素before之前 */
void list_insert_before(struct list_elem* before, struct list_elem* elem) { 
   enum intr_status old_status = intr_disable(); // 对队列是原子操作，中断需要关闭

/* 将before前驱元素的后继元素更新为elem, 暂时使before脱离链表*/ 
   before->prev->next = elem; 

/* 更新elem自己的前驱结点为before的前驱,
 * 更新elem自己的后继结点为before, 于是before又回到链表 */
   elem->prev = before->prev;
   elem->next = before;

/* 更新before的前驱结点为elem */
   before->prev = elem;

   intr_set_status(old_status); // 恢复中断
}

/* 添加元素到列表队首,类似栈push操作 */
void list_push(struct list* plist, struct list_elem* elem) {
   list_insert_before(plist->head.next, elem); // 在队头插入elem
}

/* 追加元素到链表队尾,类似队列的先进先出操作 */
void list_append(struct list* plist, struct list_elem* elem) {
   list_insert_before(&plist->tail, elem);     // 在队尾的前面插入
}

/* 使元素pelem脱离链表 */
void list_remove(struct list_elem* pelem) {
   enum intr_status old_status = intr_disable();
   
   pelem->prev->next = pelem->next;
   pelem->next->prev = pelem->prev;

   intr_set_status(old_status);
}

/* 将链表第一个元素弹出并返回,类似栈的pop操作 */
struct list_elem* list_pop(struct list* plist) {
   struct list_elem* elem = plist->head.next;
   list_remove(elem);
   return elem;
} 

/* 从链表中查找元素obj_elem,成功时返回true,失败时返回false */
bool elem_find(struct list* plist, struct list_elem* obj_elem) {
   struct list_elem* elem = plist->head.next;
   while (elem != &plist->tail) {
      if (elem == obj_elem) {
	 return true;
      }
      elem = elem->next;
   }
   return false;
}

/* 把列表plist中的每个元素elem和arg传给回调函数func,
 * arg给func用来判断elem是否符合条件.
 * 本函数的功能是遍历列表内所有元素,逐个判断是否有符合条件的元素。
 * 找到符合条件的元素返回元素指针,否则返回NULL. */
struct list_elem* list_traversal(struct list* plist, function func, int arg) {
   struct list_elem* elem = plist->head.next;
/* 如果队列为空,就必然没有符合条件的结点,故直接返回NULL */
   if (list_empty(plist)) { 
      return NULL;
   }

   while (elem != &plist->tail) {
      if (func(elem, arg)) {		  // func返回ture则认为该元素在回调函数中符合条件,命中,故停止继续遍历
	 return elem;
      }					  // 若回调函数func返回true,则继续遍历
      elem = elem->next;	       
   }
   return NULL;
}

/* 返回链表长度 */
uint32_t list_len(struct list* plist) {
   struct list_elem* elem = plist->head.next;
   uint32_t length = 0;
   while (elem != &plist->tail) {
      length++; 
      elem = elem->next;
   }
   return length;
}

/* 判断链表是否为空,空时返回true,否则返回false */
bool list_empty(struct list* plist) {		// 判断队列是否为空
   return (plist->head.next == &plist->tail ? true : false);
}

多线程调度需要我们继续改进线程代码，我们用PCB中的general_tag字段作为节点链接所有PCB，其中还有一个ticks字段用于记录线程执行时间，ticks越大，优先级越高，时钟中断一次，ticks就会减一，当其为0的时候，调度器就会切换线程，选择另一个线程上处理器执行，然后打上TASK_RUNNING的标记，之后通过switch_to函数将新线程的寄存器环境恢复，这样新线程才得以执行，完整调度过程需要以下三步

  • 时钟中断处理函数
  • 调度器schedule
  • 任务切换函数switch_to

调度器主要实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 实现任务调度 */
void schedule() {

   ASSERT(intr_get_status() == INTR_OFF);

   struct task_struct* cur = running_thread(); // 获取线程PCB
   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;
   switch_to(cur, next);
}

接下来是切换函数的实现，在thread/目录下创建switch.S，由两部分组成第一部分负责保存任务进入中断前的全部寄存器，第二部分负责保存esi、edi、ebx、ebp四个寄存器。堆栈图压栈之后的如下所示

image-20200526104424200

代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[bits 32]
section .text
global switch_to
switch_to:
   ;栈中此处是返回地址
   push esi
   push edi
   push ebx
   push ebp

   mov eax, [esp + 20]		 ; 得到栈中的参数cur, cur = [esp+20]
   mov [eax], esp                ; 保存栈顶指针esp. task_struct的self_kstack字段,
				 ; self_kstack在task_struct中的偏移为0,
				 ; 所以直接往thread开头处存4字节便可。
;------------------  以上是备份当前线程的环境，下面是恢复下一个线程的环境  ----------------
   mov eax, [esp + 24]		 ; 得到栈中的参数next, next = [esp+24]
   mov esp, [eax]		 ; pcb的第一个成员是self_kstack成员,用来记录0级栈顶指针,
				 ; 用来上cpu时恢复0级栈,0级栈中保存了进程或线程所有信息,包括3级栈指针
   pop ebp
   pop ebx
   pop edi
   pop esi
   ret				 ; 返回到上面switch_to下面的那句注释的返回地址,
				 ; 未由中断进入,第一次执行时会返回到kernel_thread

修改makefie、printf等一些文件之后，最终能实现多线程的调度主函数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
#include "print.h"
#include "init.h"
#include "thread.h"
#include "interrupt.h"

void k_thread_a(void*);
void k_thread_b(void*);
int main(void) {
   put_str("Welcome to TJ's kernel!\n");
   init_all();

   thread_start("k_thread_a", 31, k_thread_a, "argA ");
   thread_start("k_thread_b", 8, k_thread_b, "argB ");

   intr_enable();	// 打开中断,使时钟中断起作用
   while(1) {
      put_str("Main ");
   };
   return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {     
/* 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用 */
   char* para = arg;
   while(1) {
      put_str(para);
   }
}

/* 在线程中运行的函数 */
void k_thread_b(void* arg) {     
/* 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用 */
   char* para = arg;
   while(1) {
      put_str(para);
   }
}

不过这里会引发GP异常，如下所示，可以用nm build/kernel.bin | grep thread_start查看线程函数地址，然后在线程函数下断点，再用show exitint打印中断信息，这样就可以观察异常处的寄存器信息，这里产生异常的原因是寄存器bx的值超过了段界限limit的值0x7fff

image-20200526104424200

输入输出系统

同步机制-锁

思考之前代码的问题，字符打印问题主要出现在交界处无法打印正确，回忆put_str函数打印有三个步骤

  • 获取光标值
  • 将光标值转换为字节地址，在该地址处写入字符
  • 更新光标值

在打印的时候，若线程A到了第二步，此时发生了时钟中断，那么线程B就会重新获取光标值，这样导致数据覆盖，所以我们需要保证公共资源显存只有一个线程访问，也就是需要保证原子性，我们需要在put_str函数中进行开关中断的操作，如下所示，后面对公共资源”光标寄存器”也需要这样进行原子操作避免GP异常，这样做可以正确的打印输出，但只能解决输出函数线程竞争的问题，如果其他地方也有这种竞争问题就需要我们用一种新的机制来解决，也就是锁的机制。

1
2
3
4
5
6
7
[...]
   while(1) {
      intr_disable(); // 关中断
      put_str("...");
      intr_enable(); // 开中断
   };
[...]

要进行线程同步，肯定要在需要同步的地方阻止线程的切换。这里主要通过信号量的机制对公共资源加锁，达到同步的目的。信号量的原理本身比较简单。通过P、V操作来表示信号量的增减，如下。

P操作，减少信号量：

  1. 判断信号量是否大于0
  2. 如果大于0， 将其减一
  3. 如果小于0，将当前线程阻塞

V操作，增加信号量：

  1. 将信号量的值加一
  2. 唤醒等待的线程

首先我们需要实现线程的阻塞与唤醒，阻塞通常是线程自己阻塞自己，唤醒通常是其他线程唤醒本线程。具体实现如下，在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
/* 当前线程将自己阻塞,标志其状态为stat. */
void thread_block(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();
    task_struct* cur_thread = running_thread();

    cur_thread->status = stat; // 置其状态为stat 
    schedule();            // 将当前线程换下处理器
    
    /* 待当前线程被解除阻塞后才继续运行下面的intr_set_status */
   intr_set_status(old_status);
}

/* 将线程pthread解除阻塞 */
void thread_unblock(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);
}

信号量锁的结构如下，实现在thread/sync.c和.h，信号量仅仅是一个编程理念，实现功能即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 信号量结构 */
struct semaphore 
{
   uint8_t  value;
   struct   list waiters;
};

/* 锁结构 */
struct lock 
{
   task_struct* holder; // 锁的持有者
   struct   semaphore semaphore; // 用二元信号量实现锁
   uint32_t holder_repeat_nr; // 锁的持有者重复申请锁的次数
};

初始化就是给各个字段赋值

1
2
3
4
5
6
7
8
9
10
11
12
/* 初始化信号量 */
void sema_init(struct semaphore* psema, uint8_t value) {
   psema->value = value;       // 为信号量赋初值
   list_init(&psema->waiters); //初始化信号量的等待队列
}

/* 初始化锁plock */
void lock_init(struct lock* plock) {
   plock->holder = NULL;
   plock->holder_repeat_nr = 0;
   sema_init(&plock->semaphore, 1);  // 信号量初值为1
}

P操作

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
/* 信号量down操作 */
void sema_down(struct semaphore *psema)
{
    /* 关中断来保证原子操作 */
    enum intr_status old_status = intr_disable();
    while (psema->value == 0)
    { 
        // 若value为0,表示已经被别人持有
        ASSERT(!elem_find(&psema->waiters, &running_thread()->general_tag));
        /* 当前线程不应该已在信号量的waiters队列中 */
        if (elem_find(&psema->waiters, &running_thread()->general_tag))
        {
            PANIC("sema_down: thread blocked has been in waiters_list\n");
        }

        /* 若信号量的值等于0,则当前线程把自己加入该锁的等待队列,然后阻塞自己 */
        list_append(&psema->waiters, &running_thread()->general_tag);
        thread_block(TASK_BLOCKED); // 阻塞线程,直到被唤醒
    }
    /* 若value为1或被唤醒后,会执行下面的代码,也就是获得了锁。*/
    psema->value--;
    ASSERT(psema->value == 0);
    /* 恢复之前的中断状态 */
    intr_set_status(old_status);
}

V操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 信号量的up操作 */
void sema_up(struct semaphore *psema)
{
    /* 关中断,保证原子操作 */
    enum intr_status old_status = intr_disable();
    ASSERT(psema->value == 0);

    if (!list_empty(&psema->waiters))
    {
        task_struct *thread_blocked = elem2entry(task_struct, general_tag, list_pop(&psema->waiters));
        thread_unblock(thread_blocked);
    }

    psema->value++;
    ASSERT(psema->value == 1);
    /* 恢复之前的中断状态 */
    intr_set_status(old_status);
}

获取锁和释放锁

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
/* 获取锁plock */
void lock_acquire(struct lock *plock)
{
    /* 排除曾经自己已经持有锁但还未将其释放的情况。*/
    if (plock->holder != running_thread()) // 排除死锁的情况
    {
        sema_down(&plock->semaphore); // 对信号量P操作,原子操作,信号量减一
        plock->holder = running_thread();
        ASSERT(plock->holder_repeat_nr == 0);
        plock->holder_repeat_nr = 1;
    }
    else
    {
        plock->holder_repeat_nr++;
    }
}

/* 释放锁plock */
void lock_release(struct lock *plock)
{
    ASSERT(plock->holder == running_thread());
    if (plock->holder_repeat_nr > 1)
    {
        plock->holder_repeat_nr--;
        return;
    }
    ASSERT(plock->holder_repeat_nr == 1);

    plock->holder = NULL; // 把锁的持有者置空放在V操作之前
    plock->holder_repeat_nr = 0;
    sema_up(&plock->semaphore); // 信号量的V操作,也是原子操作
}

接下来需要对锁进行测试，我们需要对终端输出进行封装，基本上都是对锁的使用，没什么好说的

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
#include "console.h"
#include "print.h"
#include "stdint.h"
#include "sync.h"
#include "thread.h"
static struct lock console_lock;    // 控制台锁

/* 初始化终端 */
void console_init() {
  lock_init(&console_lock); 
}

/* 获取终端 */
void console_acquire() {
   lock_acquire(&console_lock);
}

/* 释放终端 */
void console_release() {
   lock_release(&console_lock);
}

/* 终端中输出字符串 */
void console_put_str(char* str) {
   console_acquire(); 
   put_str(str); 
   console_release();
}

/* 终端中输出字符 */
void console_put_char(uint8_t char_asci) {
   console_acquire(); 
   put_char(char_asci); 
   console_release();
}

/* 终端中输出16进制整数 */
void console_put_int(uint32_t num) {
   console_acquire(); 
   put_int(num); 
   console_release();
}

然后在init文件添加初始化函数并在main文件进行测试，只需要将put_str("...")修改为console_put_str("...")，测试结果如下

image-20200526104424200

键盘获取输入输出

键盘的输入和输出主要是对8042和8048芯片的操作，这两芯片的数据在P456页开始有介绍，主要是对端口0x60的操作，其作为IO缓冲区，关系如下

image-20200526104424200

我们将键盘的输入根据键盘扫描码(P462)进行转换，最终需要将其转换为我们键盘按下字符对应的ASCII码。其本质就是，键盘中断处理程序负责接收按键信息，也就是扫描码，然后就是对扫描码的处理，我们将用驱动程序对其进行实现，需要分两个阶段完成

  • 如果是一些用于操作方面的控制键，比如shift，crtl等，就交给键盘驱动中完成
  • 如果是一些用于字符方面的键，就直接交给字符处理程序完成即可

我们在device/keyboard.c和.h中实现，其中对于操作控制键和其他键配合按下的情况，比如crtl+a这种就需要定义一个变量判断之前是否已经按下crtl键，对于shift组合字符我们用的是二维数组保存，如shift+1显示的是 ! 字符

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
/* 定义以下变量记录相应键是否按下的状态,
 * ext_scancode用于记录makecode是否以0xe0开头 */
static bool ctrl_status, shift_status, alt_status, caps_lock_status, ext_scancode;

/* 以通码make_code为索引的二维数组 */
static char keymap[][2] = {
/* 扫描码   未与shift组合  与shift组合*/
/* ---------------------------------- */
/* 0x00 */	{0,	0},		
/* 0x01 */	{esc,	esc},		
/* 0x02 */	{'1',	'!'},		
/* 0x03 */	{'2',	'@'},		
/* 0x04 */	{'3',	'#'},		
/* 0x05 */	{'4',	'$'},		
/* 0x06 */	{'5',	'%'},		
/* 0x07 */	{'6',	'^'},		
/* 0x08 */	{'7',	'&'},		
/* 0x09 */	{'8',	'*'},		
/* 0x0A */	{'9',	'('},		
/* 0x0B */	{'0',	')'},		
/* 0x0C */	{'-',	'_'},		
/* 0x0D */	{'=',	'+'},		
/* 0x0E */	{backspace, backspace},	
/* 0x0F */	{tab,	tab},		
/* 0x10 */	{'q',	'Q'},		
/* 0x11 */	{'w',	'W'},		
/* 0x12 */	{'e',	'E'},		
/* 0x13 */	{'r',	'R'},		
/* 0x14 */	{'t',	'T'},		
/* 0x15 */	{'y',	'Y'},		
/* 0x16 */	{'u',	'U'},		
/* 0x17 */	{'i',	'I'},		
/* 0x18 */	{'o',	'O'},		
/* 0x19 */	{'p',	'P'},		
/* 0x1A */	{'[',	'{'},		
/* 0x1B */	{']',	'}'},		
/* 0x1C */	{enter,  enter},
/* 0x1D */	{ctrl_l_char, ctrl_l_char},
/* 0x1E */	{'a',	'A'},		
/* 0x1F */	{'s',	'S'},		
/* 0x20 */	{'d',	'D'},		
/* 0x21 */	{'f',	'F'},		
/* 0x22 */	{'g',	'G'},		
/* 0x23 */	{'h',	'H'},		
/* 0x24 */	{'j',	'J'},		
/* 0x25 */	{'k',	'K'},		
/* 0x26 */	{'l',	'L'},		
/* 0x27 */	{';',	':'},		
/* 0x28 */	{'\'',	'"'},		
/* 0x29 */	{'`',	'~'},		
/* 0x2A */	{shift_l_char, shift_l_char},	
/* 0x2B */	{'\\',	'|'},		
/* 0x2C */	{'z',	'Z'},		
/* 0x2D */	{'x',	'X'},		
/* 0x2E */	{'c',	'C'},		
/* 0x2F */	{'v',	'V'},		
/* 0x30 */	{'b',	'B'},		
/* 0x31 */	{'n',	'N'},		
/* 0x32 */	{'m',	'M'},		
/* 0x33 */	{',',	'<'},		
/* 0x34 */	{'.',	'>'},		
/* 0x35 */	{'/',	'?'},
/* 0x36	*/	{shift_r_char, shift_r_char},	
/* 0x37 */	{'*',	'*'},    	
/* 0x38 */	{alt_l_char, alt_l_char},
/* 0x39 */	{' ',	' '},		
/* 0x3A */	{caps_lock_char, caps_lock_char}
/*其它按键暂不处理*/
};

后面的函数都是对通码、断码、组合键的一些处理

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
/* 键盘中断处理程序 */
static void intr_keyboard_handler(void) {

/* 这次中断发生前的上一次中断,以下任意三个键是否有按下 */
   bool ctrl_down_last = ctrl_status;	  
   bool shift_down_last = shift_status;
   bool caps_lock_last = caps_lock_status;

   bool break_code;
   uint16_t scancode = inb(KBD_BUF_PORT);

/* 若扫描码是e0开头的,表示此键的按下将产生多个扫描码,
 * 所以马上结束此次中断处理函数,等待下一个扫描码进来*/ 
   if (scancode == 0xe0) { 
      ext_scancode = true;    // 打开e0标记
      return;
   }

/* 如果上次是以0xe0开头,将扫描码合并 */
   if (ext_scancode) {
      scancode = ((0xe000) | scancode);
      ext_scancode = false;   // 关闭e0标记
   }   

   break_code = ((scancode & 0x0080) != 0);   // 获取break_code
   
   if (break_code) {   // 若是断码break_code(按键弹起时产生的扫描码)

   /* 由于ctrl_r 和alt_r的make_code和break_code都是两字节,
   所以可用下面的方法取make_code,多字节的扫描码暂不处理 */
      uint16_t make_code = (scancode &= 0xff7f);   // 得到其make_code(按键按下时产生的扫描码)

   /* 若是任意以下三个键弹起了,将状态置为false */
      if (make_code == ctrl_l_make || make_code == ctrl_r_make) { // crtl
	 ctrl_status = false;
      } else if (make_code == shift_l_make || make_code == shift_r_make) { // shift
	 shift_status = false;
      } else if (make_code == alt_l_make || make_code == alt_r_make) { // alt
	 alt_status = false;
      } /* 由于caps_lock不是弹起后关闭,所以需要单独处理 */

      return;   // 直接返回结束此次中断处理程序

   } 
   /* 若为通码,只处理数组中定义的键以及alt_right和ctrl键,全是make_code */
   else if ((scancode > 0x00 && scancode < 0x3b) || \
	       (scancode == alt_r_make) || \
	       (scancode == ctrl_r_make)) {
      bool shift = false;  // 判断是否与shift组合,用来在一维数组中索引对应的字符
      if ((scancode < 0x0e) || (scancode == 0x29) || \
	 (scancode == 0x1a) || (scancode == 0x1b) || \
	 (scancode == 0x2b) || (scancode == 0x27) || \
	 (scancode == 0x28) || (scancode == 0x33) || \
	 (scancode == 0x34) || (scancode == 0x35)) {  
	    /****** 代表两个字母的键 ********
		     0x0e 数字'0'~'9',字符'-',字符'='
		     0x29 字符'`'
		     0x1a 字符'['
		     0x1b 字符']'
		     0x2b 字符'\\'
		     0x27 字符';'
		     0x28 字符'\''
		     0x33 字符','
		     0x34 字符'.'
		     0x35 字符'/' 
	    *******************************/
	 if (shift_down_last) {  // 如果同时按下了shift键
	    shift = true;
	 }
      } else {	  // 默认为字母键
	 if (shift_down_last && caps_lock_last) {  // 如果shift和capslock同时按下
	    shift = false;
	 } else if (shift_down_last || caps_lock_last) { // 如果shift和capslock任意被按下
	    shift = true;
	 } else {
	    shift = false;
	 }
      }

      uint8_t index = (scancode &= 0x00ff);  // 将扫描码的高字节置0,主要是针对高字节是e0的扫描码.
      char cur_char = keymap[index][shift];  // 在数组中找到对应的字符
   
      /* 只处理ascii码不为0的键 */
      if (cur_char) {
	 put_char(cur_char);
	 return;
      }

      /* 记录本次是否按下了下面几类控制键之一,供下次键入时判断组合键 */
      if (scancode == ctrl_l_make || scancode == ctrl_r_make) {
	 ctrl_status = true;
      } else if (scancode == shift_l_make || scancode == shift_r_make) {
	 shift_status = true;
      } else if (scancode == alt_l_make || scancode == alt_r_make) {
	 alt_status = true;
      } else if (scancode == caps_lock_make) {
      /* 不管之前是否有按下caps_lock键,当再次按下时则状态取反,
       * 即:已经开启时,再按下同样的键是关闭。关闭时按下表示开启。*/
	 caps_lock_status = !caps_lock_status;
      }
   } else {
      put_str("unknown key\n");
   }
}

修改main函数对我们的输入进行测试

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
#include "print.h"
#include "init.h"
#include "thread.h"
#include "interrupt.h"
#include "console.h"

void k_thread_a(void*);
void k_thread_b(void*);

int main(void) {
   put_str("Welcome to TJ's kernel!\n");
   init_all();

//   thread_start("k_thread_a", 31, k_thread_a, "argA ");
//   thread_start("k_thread_b", 8, k_thread_b, "argB ");

   intr_enable();
   while(1); //{
      //console_put_str("Main ");
  // };
   return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {     
/* 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用 */
   char* para = arg;
   while(1) {
      console_put_str(para);
   }
}

/* 在线程中运行的函数 */
void k_thread_b(void* arg) {     
/* 用void*来通用表示参数,被调用的函数知道自己需要什么类型的参数,自己转换再用 */
   char* para = arg;
   while(1) {
      console_put_str(para);
   }
}

测试结果如下，可以实现大部分键盘的输入，但当使用小键盘中1~9的时候会显示未识别，不过这个问题不大

image-20200526104424200

为了构建交互式的shell，我们需要实现一个缓冲区用来保存我们输入的指令，这里我们使用的是一个环形的缓冲区，既然是环形，就涉及到它的设计思路，我们使用的是生产者-消费者模型，具体实现在device目录下的ioqueue.c和.h文件中，其中队列结构如下所示

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

/* 环形队列 */
struct ioqueue {
// 生产者消费者问题
    struct lock lock;
 /* 生产者,缓冲区不满时就继续往里面放数据,
  * 否则就睡眠,此项记录哪个生产者在此缓冲区上睡眠。*/
    struct task_struct* producer;

 /* 消费者,缓冲区不空时就继续从往里面拿数据,
  * 否则就睡眠,此项记录哪个消费者在此缓冲区上睡眠。*/
    struct task_struct* consumer;
    char buf[bufsize];			    // 缓冲区大小
    int32_t head;			    // 队首,数据往队首处写入
    int32_t tail;			    // 队尾,数据从队尾处读出
};

初始化io队列

1
2
3
4
5
6
/* 初始化io队列ioq */
void ioqueue_init(struct ioqueue* ioq) {
   lock_init(&ioq->lock);     // 初始化io队列的锁
   ioq->producer = ioq->consumer = NULL;  // 生产者和消费者置空
   ioq->head = ioq->tail = 0; // 队列的首尾指针指向缓冲区数组第0个位置
}

其他函数如下所示，其中比较关键的是ioq_getchar和ioq_putchar函数

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
/* 返回pos在缓冲区中的下一个位置值 */
static int32_t next_pos(int32_t pos) {
   return (pos + 1) % bufsize; 
}

/* 判断队列是否已满 */
bool ioq_full(struct ioqueue* ioq) {
   ASSERT(intr_get_status() == INTR_OFF);
   return next_pos(ioq->head) == ioq->tail;
}

/* 判断队列是否已空 */
static bool ioq_empty(struct ioqueue* ioq) {
   ASSERT(intr_get_status() == INTR_OFF);
   return ioq->head == ioq->tail;
}

/* 使当前生产者或消费者在此缓冲区上等待 */
static void ioq_wait(struct task_struct** waiter) {
   ASSERT(*waiter == NULL && waiter != NULL);
   *waiter = running_thread();
   thread_block(TASK_BLOCKED);
}

/* 唤醒waiter */
static void wakeup(struct task_struct** waiter) {
   ASSERT(*waiter != NULL);
   thread_unblock(*waiter); 
   *waiter = NULL;
}

/* 消费者从ioq队列中获取一个字符 */
char ioq_getchar(struct ioqueue* ioq) {
   ASSERT(intr_get_status() == INTR_OFF);

/* 若缓冲区(队列)为空,把消费者ioq->consumer记为当前线程自己,
 * 目的是将来生产者往缓冲区里装商品后,生产者知道唤醒哪个消费者,
 * 也就是唤醒当前线程自己*/
   while (ioq_empty(ioq)) {
      lock_acquire(&ioq->lock);	 
      ioq_wait(&ioq->consumer);
      lock_release(&ioq->lock);
   }

   char byte = ioq->buf[ioq->tail];	  // 从缓冲区中取出
   ioq->tail = next_pos(ioq->tail);	  // 把读游标移到下一位置

   if (ioq->producer != NULL) {
      wakeup(&ioq->producer);		  // 唤醒生产者
   }

   return byte; 
}

/* 生产者往ioq队列中写入一个字符byte */
void ioq_putchar(struct ioqueue* ioq, char byte) {
   ASSERT(intr_get_status() == INTR_OFF);

/* 若缓冲区(队列)已经满了,把生产者ioq->producer记为自己,
 * 为的是当缓冲区里的东西被消费者取完后让消费者知道唤醒哪个生产者,
 * 也就是唤醒当前线程自己*/
   while (ioq_full(ioq)) {
      lock_acquire(&ioq->lock);
      ioq_wait(&ioq->producer);
      lock_release(&ioq->lock);
   }
   ioq->buf[ioq->head] = byte;      // 把字节放入缓冲区中
   ioq->head = next_pos(ioq->head); // 把写游标移到下一位置

   if (ioq->consumer != NULL) {
      wakeup(&ioq->consumer);          // 唤醒消费者
   }
}

我们还需要修改interrupt.c文件，打开时钟中断和键盘中断，最后在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
[...]
int main(void) {
   put_str("Welcome to TJ's kernel\n");
   init_all();
   thread_start("consumer_a", 31, k_thread_a, " A_");
   thread_start("consumer_b", 31, k_thread_b, " B_");
   intr_enable();
   while(1); 
   return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {     
   while(1) {
      enum intr_status old_status = intr_disable();
      if (!ioq_empty(&kbd_buf)) {
	 console_put_str(arg);
	 char byte = ioq_getchar(&kbd_buf);
	 console_put_char(byte);
      }
      intr_set_status(old_status);
   }
}

/* 在线程中运行的函数 */
void k_thread_b(void* arg) {     
   while(1) {
      enum intr_status old_status = intr_disable();
      if (!ioq_empty(&kbd_buf)) {
	 console_put_str(arg);
	 char byte = ioq_getchar(&kbd_buf);
	 console_put_char(byte);
      }
      intr_set_status(old_status);
   }
}

这里我一直按下的 t 键，可以看到线程A和B交替执行

image-20200526104424200

用户进程

LDT

之前介绍GDT的时候提到过LDT，我们的操作系统本身不实现LDT，但其作用还是有必要了解的，LDT也叫局部描述符表。按照内存分段的方式，内存中的程序映像自然被分成了代码段、数据段等资源，这些资源属于程序私有部分，因此intel建议为每个程序单独赋予一个结构来存储其私有资源，这个结构就是LDT，因为是每个任务都有的，故其位置不固定，要找到它需要先像GDT那样注册，之后用选择子找到它。其格式如下，LDT中描述符的D位和L位固定为0，因为属于系统断描述符，因此S为0。描述符在S为0的前提下，若TYPE的值为0010，即表示描述符是LDT。与其配套的寄存器和指令即为LDTR和lldt "16位通用寄存器" 或 "16位内存单元"：

image-20200526104424200

TSS

单核CPU想要实现多任务，唯一的方案就是多个任务共享同一个CPU，也就是让CPU在多个任务间轮转。TSS就是给每个任务”关联”的一个任务状态段，用它来关联任务。TSS(任务状态段)是由程序员来提供，CPU进行维护。程序员提供是指需要我们定义一个结构体，里面存放任务要用的寄存器数据。CPU维护是指切换任务时，CPU会自动把旧任务的数据存放的结构体变量中，然后将新任务的TSS数据加载到相应的寄存器中。

TSS和之前所说的段一样，本质上也是一片存储数据的内存区域，CPU用这块内存区域保存任务的最新状态。所以也需要一个描述符结构来表示它，这个描述符就是TSS描述符，它的结构如下，因为属于系统断描述符，因此S为0。描述符在S为0的前提下，若TYPE的值为10B1，B位表示Busy，为1表示繁忙，0表示空闲

image-20200526104424200

其工作模式和LDT相似，由寄存器TR保存TSS的起始地址，使用前也需要进行注册，都是通过选择子来访问的，将TSS加载到TR的指令是ltr，格式如下

1
ltr "16位通用寄存器" 或 "16位内存单元"

任务切换的方式有”中断+任务门”、”call或jmp+任务门”、和iretd三种方式，这些方式都比较繁琐，对于Linux系统以及大部分x86系统而言，这样使用TSS效率太低，这一套标准需要我们在”应付”的前提下达到最高效率，我们这里主要效仿Linux系统的做法，Linux为了提高任务切换的速度，通过如下方式来进行任务切换：

一个CPU上的所有任务共享一个TSS，通过TR寄存器保存这个TSS，在使用ltr指令加载TSS之后，该TR寄存器永远指向同一个TSS，之后在进行任务切换的时候也不会重新加载TSS，只需要把TSS中的SS0和esp0更新为新任务的内核栈的段地址及栈指针。

接下来我们实现TSS，在kernel/global.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
// ----------------  GDT描述符属性  ----------------

#define	DESC_G_4K    1
#define	DESC_D_32    1
#define DESC_L	     0	// 64位代码标记，此处标记为0便可。
#define DESC_AVL     0	// cpu不用此位，暂置为0  
#define DESC_P	     1
#define DESC_DPL_0   0
#define DESC_DPL_1   1
#define DESC_DPL_2   2
#define DESC_DPL_3   3
/* 
   代码段和数据段属于存储段，tss和各种门描述符属于系统段
   s为1时表示存储段,为0时表示系统段.
*/
#define DESC_S_CODE	1
#define DESC_S_DATA	DESC_S_CODE
#define DESC_S_SYS	0
#define DESC_TYPE_CODE	8	// x=1,c=0,r=0,a=0 代码段是可执行的,非依从的,不可读的,已访问位a清0.  
#define DESC_TYPE_DATA  2	// x=0,e=0,w=1,a=0 数据段是不可执行的,向上扩展的,可写的,已访问位a清0.
#define DESC_TYPE_TSS   9	// B位为0,不忙

/* 第3个段描述符是显存,第4个是tss */
#define SELECTOR_U_CODE	   ((5 << 3) + (TI_GDT << 2) + RPL3)
#define SELECTOR_U_DATA	   ((6 << 3) + (TI_GDT << 2) + RPL3)
#define SELECTOR_U_STACK   SELECTOR_U_DATA

#define GDT_ATTR_HIGH		 ((DESC_G_4K << 7) + (DESC_D_32 << 6) + (DESC_L << 5) + (DESC_AVL << 4))
#define GDT_CODE_ATTR_LOW_DPL3	 ((DESC_P << 7) + (DESC_DPL_3 << 5) + (DESC_S_CODE << 4) + DESC_TYPE_CODE)
#define GDT_DATA_ATTR_LOW_DPL3	 ((DESC_P << 7) + (DESC_DPL_3 << 5) + (DESC_S_DATA << 4) + DESC_TYPE_DATA)


//---------------  TSS描述符属性  ------------
#define TSS_DESC_D  0 

#define TSS_ATTR_HIGH ((DESC_G_4K << 7) + (TSS_DESC_D << 6) + (DESC_L << 5) + (DESC_AVL << 4) + 0x0)
#define TSS_ATTR_LOW ((DESC_P << 7) + (DESC_DPL_0 << 5) + (DESC_S_SYS << 4) + DESC_TYPE_TSS)
#define SELECTOR_TSS ((4 << 3) + (TI_GDT << 2 ) + RPL0)

struct gdt_desc {
   uint16_t limit_low_word;
   uint16_t base_low_word;
   uint8_t  base_mid_byte;
   uint8_t  attr_low_byte;
   uint8_t  limit_high_attr_high;
   uint8_t  base_high_byte;
}; 

#define PG_SIZE 4096

关键代码我们在userprog/tss.c中实现，首先根据tss结构构造如下结构体

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
/* 任务状态段tss结构 */
struct tss 
{
    uint32_t backlink;
    uint32_t* esp0;
    uint32_t ss0;
    uint32_t* esp1;
    uint32_t ss1;
    uint32_t* esp2;
    uint32_t ss2;
    uint32_t cr3;
    uint32_t (*eip) (void);
    uint32_t eflags;
    uint32_t eax;
    uint32_t ecx;
    uint32_t edx;
    uint32_t ebx;
    uint32_t esp;
    uint32_t ebp;
    uint32_t esi;
    uint32_t edi;
    uint32_t es;
    uint32_t cs;
    uint32_t ss;
    uint32_t ds;
    uint32_t fs;
    uint32_t gs;
    uint32_t ldt;
    uint32_t trace;
    uint32_t io_base;
};

初始化主要是效仿Linux中初始化ss0和esp0，然后将TSS描述符加载到全局描述符表中，因为GDT中第0个描述符不可用，第1个为代码段，第2个为数据段和栈，第3个为显存段，第4个就是我们的tss，故地址为0xc0000900+0x20

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
#include "tss.h"
#include "stdint.h"
#include "global.h"
#include "string.h"
#include "print.h"

/* 任务状态段tss结构 */
struct tss {
    uint32_t backlink;
    uint32_t* esp0;
    uint32_t ss0;
    uint32_t* esp1;
    uint32_t ss1;
    uint32_t* esp2;
    uint32_t ss2;
    uint32_t cr3;
    uint32_t (*eip) (void);
    uint32_t eflags;
    uint32_t eax;
    uint32_t ecx;
    uint32_t edx;
    uint32_t ebx;
    uint32_t esp;
    uint32_t ebp;
    uint32_t esi;
    uint32_t edi;
    uint32_t es;
    uint32_t cs;
    uint32_t ss;
    uint32_t ds;
    uint32_t fs;
    uint32_t gs;
    uint32_t ldt;
    uint32_t trace;
    uint32_t io_base;
}; 
static struct tss tss;

/* 更新tss中esp0字段的值为pthread的0级线 */
void update_tss_esp(struct task_struct* pthread) {
   tss.esp0 = (uint32_t*)((uint32_t)pthread + PG_SIZE);
}

/* 创建gdt描述符 */
static struct gdt_desc make_gdt_desc(uint32_t* desc_addr, uint32_t limit, uint8_t attr_low, uint8_t attr_high) {
   uint32_t desc_base = (uint32_t)desc_addr;
   struct gdt_desc desc;
   desc.limit_low_word = limit & 0x0000ffff;
   desc.base_low_word = desc_base & 0x0000ffff;
   desc.base_mid_byte = ((desc_base & 0x00ff0000) >> 16);
   desc.attr_low_byte = (uint8_t)(attr_low);
   desc.limit_high_attr_high = (((limit & 0x000f0000) >> 16) + (uint8_t)(attr_high));
   desc.base_high_byte = desc_base >> 24;
   return desc;
}

/* 在gdt中创建tss并重新加载gdt */
void tss_init() {
   put_str("tss_init start\n");
   uint32_t tss_size = sizeof(tss);
   memset(&tss, 0, tss_size);
   tss.ss0 = SELECTOR_K_STACK;
   tss.io_base = tss_size;

/* gdt段基址为0x900,把tss放到第4个位置,也就是0x900+0x20的位置 */

  /* 在gdt中添加dpl为0的TSS描述符 */
  *((struct gdt_desc*)0xc0000920) = make_gdt_desc((uint32_t*)&tss, tss_size - 1, TSS_ATTR_LOW, TSS_ATTR_HIGH);

  /* 在gdt中添加dpl为3的数据段和代码段描述符 */
  *((struct gdt_desc*)0xc0000928) = make_gdt_desc((uint32_t*)0, 0xfffff, GDT_CODE_ATTR_LOW_DPL3, GDT_ATTR_HIGH);
  *((struct gdt_desc*)0xc0000930) = make_gdt_desc((uint32_t*)0, 0xfffff, GDT_DATA_ATTR_LOW_DPL3, GDT_ATTR_HIGH);
   
  /* gdt 16位的limit 32位的段基址 */
   uint64_t gdt_operand = ((8 * 7 - 1) | ((uint64_t)(uint32_t)0xc0000900 << 16));   // 7个描述符大小
   asm volatile ("lgdt %0" : : "m" (gdt_operand));  // 重新加载GDT
   asm volatile ("ltr %w0" : : "r" (SELECTOR_TSS)); // 加载tss到TR寄存器
   put_str("tss_init and ltr done\n");
}

修改初始化函数之后，测试一下，用info gdt命令查看gdt表，可以看到TSS正确加载到第四个描述符中。

image-20200526104424200

进程实现

实现进程的过程是在之前的线程基础上进行的，在创建线程的时候是将栈的返回地址指向了kernel_thread函数，通过该函数调用线程函数实现的，其执行流程如下，我们只需要把执行线程的函数换成创建进程的函数就可以了

image-20200526104424200

与线程不同的是，每个进程都单独有4GB虚拟地址空间，所以，需要单独为每个进程维护一个虚拟地址池，用来标记该进程中地址分配信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 进程或线程的pcb,程序控制块 */
struct task_struct {
   uint32_t* self_kstack;	 // 各内核线程都用自己的内核栈
   enum task_status status;
   char name[16];
   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;	 // 用这串数字做栈的边界标记,用于检测栈的溢出
};

用户进程创建页表的实现在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
// 在虚拟内存池中申请pg_cnt个虚拟页
static void *vaddr_get(enum pool_flags pf, uint32_t pg_cnt)
{
    int vaddr_start = 0;
    int bit_idx_start = -1;
    uint32_t cnt = 0;

    if(pf == PF_KERNEL)
    {
        //...内核内存池
    }
    else
    {
        // 用户内存池
        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;
}

/* 在用户空间中申请4k内存,并返回其虚拟地址 */
void *get_user_pages(uint32_t pg_cnt)
{
    lock_acquire(&user_pool.lock);
    void *vaddr = malloc_page(PF_USER, pg_cnt);
    memset(vaddr, 0, pg_cnt * PG_SIZE);
    lock_release(&user_pool.lock);
    return vaddr;
}

我们还需让用户进程工作在3环下，这就需要我们从高特权级跳到低特权级。一般情况下，CPU不允许从高特权级转向低特权级，只有从中断返回或者从调用门返回的情况下才可以。这里我们采用从中断返回的方式进入3特权级，需要制造从中断返回的条件，构造好栈的内容之后执行iretd指令，下面是添加的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//构建用户进程初始上下文信息
void start_process(void *filename_)
{
    void *function = filename_;
    task_struct *cur = running_thread();
    cur->self_kstack += sizeof(thread_stack);
    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");
}

激活页表，其参数可能是进程也可能是线程

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
/* 激活页表 */
void page_dir_activate(task_struct *p_thread)
{
    /* 若为内核线程,需要重新填充页表为0x100000 */
    uint32_t pagedir_phy_addr = 0x100000; // 默认为内核的页目录物理地址,也就是内核线程所用的页目录表
    if (p_thread->pgdir != NULL) // 用户态进程有页表，线程为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(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);
    }
}

创建用户进程的页目录表

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
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(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);
}

创建用户进程filename并将其添加到就绪队列中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 创建用户进程 */
void process_execute(void *filename, char *name)
{
    /* pcb内核的数据结构,由内核来维护进程信息,因此要在内核内存池中申请 */
    task_struct *thread = get_kernel_pages(1);
    init_thread(thread, name, default_prio);
    create_user_vaddr_bitmap(thread);
    thread_create(thread, start_process, filename);
    thread->pgdir = create_page_dir();

    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);
}

要执行用户进程，我们需要通过调度器将其调度，不过这里因为用户进程是ring3，内核线程是ring0，故我们需要修改调度器

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
/* 实现任务调度 */
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);
}

最后在main中添加测试代码，用内核线程帮进程打印数据

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
[...]
void k_thread_a(void*);
void k_thread_b(void*);
void u_prog_a(void);
void u_prog_b(void);
int test_var_a = 0, test_var_b = 0;

int main(void) {
   put_str("Welcome to TJ's kernel\n");
   init_all();

   thread_start("k_thread_a", 31, k_thread_a, "argA ");
   thread_start("k_thread_b", 31, k_thread_b, "argB ");
   process_execute(u_prog_a, "user_prog_a");
   process_execute(u_prog_b, "user_prog_b");

   intr_enable();
   while(1);
   return 0;
}

/* 在线程中运行的函数 */
void k_thread_a(void* arg) {     
   char* para = arg;
   while(1) {
      console_put_str(" v_a:0x");
      console_put_int(test_var_a);
   }
}

/* 在线程中运行的函数 */
void k_thread_b(void* arg) {     
   char* para = arg;
   while(1) {
      console_put_str(" v_b:0x");
      console_put_int(test_var_b);
   }
}

/* 测试用户进程 */
void u_prog_a(void) {
   while(1) {
      test_var_a++;
   }
}

/* 测试用户进程 */
void u_prog_b(void) {
   while(1) {
      test_var_b++;
   }
}

测试结果如下所示，在u_prog_a进程下断点观察cs为0x002b，和预期相符

image-20200526104424200

完善内核

系统调用

实现getpid

系统调用就是让用户进程调用了操作系统的功能，我们需要实现两部分，一部分属于用户空间，提供接口函数，另一部分作为内核具体实现。Linux中直接的系统调用是宏_syscall，不过现在已经废弃并被库函数syscall替代，为了内核实现更简单，我们参考_syscall来实现系统调用，其用法可以用man命令自行查询，实现思路大致如下：

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

我们就按照这个步骤一步步完成代码，首先实现获取任务自己的PID

增加0x80号中断描述符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define IDT_DESC_CNT 0x81 // 总支持的中断数

extern uint32_t syscall_handler(void);

/*初始化中断描述符表*/
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");
}

在lib/user/目录下新添加syscall文件，实现调用接口

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
/* 无参数的系统调用 */
#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;                                            \
})

增加0x80的处理例程

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
[bits 32]
extern syscall_table
section .text
global syscall_handler
syscall_handler:
    ; 保存上下文环境
    push 0
    push ds
    push es
    push fs
    push gs
    pushad

    push 0x80 ; 保持统一格式

    push edx ; 系统调用第三个参数
    push ecx ; 系统调用第二个参数
    push ebx ; 系统调用第一个参数

    // 调用相应的处理程序
    call [syscall_table + 4 * eax]
    add esp, 12 ; 跨过上面的三个参数

    ; 将 call 调用后的返回值存入当前内核栈中 eax 的位置
    mov [esp + 4 * 8], eax ; push 0x80 (4) + pushad (7*4) => (1+7)*4
    jmp intr_exit

初始化系统调用和实现sys_getpid，由userprog目录下新创建的syscall-init实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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");
}

线程初始化函数中分配pid值

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
struct lock pid_lock;		    // 分配pid锁

/* 分配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;
}

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

/* 初始化线程环境 */
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");
}

syscall文件中继续添加系统调用

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

最后在main函数中测试一下效果，其中用户接口函数为getpid()，内核实现为sys-getpid()，分别由用户进程和内核线程调用

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
int prog_a_pid = 0, prog_b_pid = 0;

int main(void) {
   put_str("Welcome to TJ's 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');
   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);
}

测试结果如下

image-20200611085701751

实现write和printf

因为我们还没有实现文件系统，故不能模仿Linux中write的系统调用，不过我们可以略去第一个参数，实现一个简单版的write，首先根据前面获取pid的基础，我们先实现提供用户调用接口，添加功能号，初始化等工作

1
2
3
4
uint32_t write(char *str)
{
    return _syscall1(SYS_WRITE, str);
}

添加处理程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint32_t sys_write(char *str)
{
    console_put_str(str); // 输出str
    return strlen(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");
}

printf原理是由write和vsprint组合，首先需要知道可变参数的原理，一般平时使用的函数，参数的个数都是已知的。函数占用的是静态内存，也就是说再编译期就要确定为其分配多大的空间。而对于可变参数则不一样，比如

1
int printf(const char *format, ...);

不过调用printf的时候我们指定了format，根据format的内容其实也就确定了参数内容，比如一个%d就多一个参数。这样我们就可以通过遍历format中的字符，筛选出%号后的数据进行单独处理即可

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
/* 将参数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;
   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的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

/* 格式化输出字符串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); 
}

我们在main中重新测试一下效果

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
int main(void) {
   put_str("Welcome to TJ's 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) {
   printf(" prog_a_pid:0x%x\n", getpid());
   while(1);
}

/* 测试用户进程 */
void u_prog_b(void) {
   printf(" prog_b_pid:0x%x\n", getpid());
   while(1);
}

测试结果如下

image-20200611085701751

完善堆内存

接下来我们需要重新实现malloc和free函数，虽然之前的内容中已经实现过内存分配的功能，但之前的内存管理模块中只是实现了内核空间的内存分配，而且每次分配的空间都是以页为单位，也就是只能分配页的整数倍的空间，我们需要优化使其能分配用户想要申请的大小。

malloc

首先引入arena的概念，arena是一大块的内存被划分的多个小的内存块的内存仓库。按照内存块的大小，可以划分成不同规格的arena。比如一种arena中全是32byte的内存块，它就只相应32byte以下内存空间的分配。这一整块arena的大小同样是页的整数倍，按照申请内存空间的大小，这个arena可能是1页或者多页。其结构由两部分组成，一是这块内存的元信息，用来描述这个arena中剩余的内存块，二是内存池区域，里面就是多个大小相同的内存块。

image-20200611085701751

当一块arena大小的内存分配完的时候，也就是该arena中的所有mem_block都分配出去了，就需要新增一个与之前arena规格相同的arena来满足内存的需求，那么这些相同规格arena之前同样需要一个结构来进行管理，这个结构用来记录arena的规格以及同规格arena中所有空闲内存块链表，也称为内存块描述符。

image-20200611085701751

当申请的内存大于1024byte时，arena中的元信息就为NULL，剩下的所有空间合为一个mem_block，也就是说只有一个为NULL的元信息和一块大内存。我们将arena划分为7种规格大小，分别为16byte, 32byte, 64byte, …. 1024byte。一个arena一般占用1页也就是4096byte，假设arena中的元信息在设计中它会占用12byte大小，对于规格为16byte的arena来说，它有(4096 - 12) / 16 = 255个内存块，有4byte的空间被浪费。

下面进行具体实现，修改memory.h文件

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 内存块 */
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链表
};

#define DESC_CNT 7	   // 内存块描述符个数

初始化在.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
/* 内存仓库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;	 // 此结构是用来给内核分配虚拟地址

/* 为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");
}

下面实现sys_malloc，该函数就是在堆上分配指定大小的空间。这也是malloc的底层实现

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
// 堆中申请size字节
void *sys_malloc(uint32_t size)
{
    enum pool_flags pf;
    struct pool *mem_pool;
    uint32_t pool_size;
    struct mem_block_desc *descs;
    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
    {
        pf = PF_USER;
        pool_size = user_pool.pool_size;
        mem_pool = &user_pool;
        descs = cur_thread->u_block_desc;
    }

    if(!(size > 0 && size < pool_size))
        return NULL;

    struct arena *a;
    struct mem_block *b;
    lock_acquire(&mem_pool->lock);

    // 处理大内存分配的情况，直接分配。
    // 分配的大小对4096向上取整
    if(size > 1024)
    {
        uint32_t page_cnt = DIV_ROUND_UP(size + sizeof(struct arena), PG_SIZE);

        a = malloc_page(pf, page_cnt); // 从堆中创建arena
        if (a != NULL)
        {
            memset(a, 0, page_cnt * PG_SIZE);

            a->desc = NULL;
            a->cnt = page_cnt;
            a->large = true;
            lock_release(&mem_pool->lock);
            return (void *)(a + 1);
        }
        else
        {
            lock_release(&mem_pool->lock);
            return NULL;
        }
    }

    // 小内存的分配情况
    else
    {
        int desc_idx = 0;

        // 找到使用哪种规格的内存描述符
        for (; desc_idx < DESC_CNT; ++desc_idx)
        {
            if(size <= descs[desc_idx].block_size)
                break;
        }

        // 该内存块描述符中的arena为空时，首先为其分配arena
        // 然后会将该arena根据其描述符中的规格大小进行内存块的划分
        // 划分的过程主要是通过arena2block这个函数对arena中的地址进行转换，使其指向下一个内存块所在的首地址，最后添加到链表中
        if (list_empty(&descs[desc_idx].free_list))
        {
            a = malloc_page(pf, 1); // 无合适大小，新创建arena
            if(a == NULL)
            {
                lock_release(&mem_pool->lock);
                return NULL;
            }
            // 初始化
            memset(a, 0, PG_SIZE);

            a->desc = &descs[desc_idx];
            a->cnt = descs[desc_idx].blocks_per_arena;
            a->large = false;

            enum intr_status old_status = intr_disable();

            uint32_t block_idx = 0;
            // arena拆分成内存块，并添加到内存块描述符的free_list中
            for (; 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);
        }

        // 有空闲的内存块之后找到该内存块相对于arena的偏移地址，该地址便为分配到的空间的首地址
        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); // 获取内存块所在的arena
        a->cnt--; // 将此arena中的空闲内存块数减一
        lock_release(&mem_pool->lock);
        return (void *)b;    
    } 
}

free

释放内存和分配内存过程相反，首先看一下申请的过程：

  1. 在虚拟地址池中分配虚拟地址
  2. 在物理内存池中分配物理地址
  3. 在页表中完成虚拟地址到物理地址的映射

与之相反的释放的过程如下：

  1. 在物理地址池中释放物理地址
  2. 在页表中去除虚拟地址的映射，原理是将pte中的P位置0
  3. 在虚拟地址池中释放虚拟地址

具体实现也在memory文件中

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
/* 将物理地址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);
      }
   }
}

释放虚拟地址中物理页框的步骤是，先调用pfree清空物理页地址，在调用page_table_pte_remove删除页表中此地址的pte，最后调用vaddr_remove清除虚拟地址位图中的相应位

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
/* 释放以虚拟地址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);
   }
}

下面实现sys_free，对释放的内存是否大于1024有不同的处理，大于则将页框在虚拟内存池和物理内存池的位图中将相应位置置0，小于则将arena中的内存块重新放回到内存块描述符中的空闲块链表free_list

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
/* 回收内存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); // 释放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); 
   }
}

最后我们在syscall文件中添加我们的系统调用

1
2
3
4
5
6
7
8
9
/* 申请size字节大小的内存,并返回结果 */
void* malloc(uint32_t size) {
   return (void*)_syscall1(SYS_MALLOC, size);
}

/* 释放ptr指向的内存 */
void free(void* ptr) {
   _syscall1(SYS_FREE, ptr);
}

更新系统调用号数组表

1
2
3
4
5
6
7
8
9
/* 初始化系统调用 */
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");
}

最后进行测试，下面是main中主要测试代码，申请内存大小对应规格均为256，所以会出现累加的情况

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
int main(void) {
   put_str("Welcome to TJ's 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, "I am thread_a");
   thread_start("k_thread_b", 31, k_thread_b, "I am thread_b");
   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);
}

测试结果如下，地址确实是连续的，和预期相符

image-20200612181835991