前言

最近太忙了，以至于操作系统-设计与实现和博客都没怎么更新过了…趁着国庆假期，把其他杂事都干完了，终于有时间来填坑了！

首先总结一下最近的课程内容，然后实现L2。

Manual

对于计算机科学来说，其实际上就是一个由各种手册(标准)组成的学科。因此学习的最好方法就是RTFM, Read The Friendly Manual。
如果想要对于Linux下的各种文件格式约定、内存布局等有更深入的了解，可以阅读System V ABI手册

加载

这里复现一下jyy老师在课程中给出的加载器demo

静态链接程序的加载

对于静态链接的程序，其加载起来非常简单：由于二进制文件中已经包含了程序运行所需要的全部代码和数据，因此理论上，只需要通过mmap，将其映射入内存中，然后将执行流转交给程序入口即可。
虽然如此，静态链接程序的加载器实际上坑也不少

要进行一些额外的设置(栈的初始化，部分寄存器初始化等)，从而使其符合Linux进程初始化的约定——具体可以查看System V ABI手册的Process Initialization章节。
Auxiliary Vector必须初始化，并且其必须包含AT_RANDOM类型的数据——因为glibc库的__libc_start_main会访问_dl_random所指向的地址，而这依赖Auxiliary Vector的AT_RANDOM类型的数据。另一方面，也不要将当前加载器的Auxiliary Vector直接当做待加载程序的Auxiliary Vector，部分加载器的Auxiliary Vector设置的值会导致待加载程序崩溃。具体的Auxiliary Vector在System V ABI手册中有较为详细的说明。~~这个坑藏的太深了~~
将可执行文件映射入内存时，实际上只需要将Program Header的类型为PT_LOAD的segment载入内存即可
通过mmap将可执行文件映射入内存的时候
- 如果flags参数没有设置MAP_FIXED，则addr参数仅仅被当做参考
- addr参数、offset参数应该对齐到sysconf(_SC_PAGE_SIZE)
将每个segment通过mmap映射的时候，mmap函数的prot参数根据segment的p_flags字段判定；mmap函数的flags参数设置为MAP_PRIVATE | MAP_FIXED，从而确保mmap的地址为指定的虚拟地址；mmap函数的addr参数和offset参数，是根据segment的p_vaddr字段和p_offset字段对齐p_align字段产生的:这里如果segment的p_vaddr字段和p_offset字段如果对齐p_align字段的话，其也自动对齐了sysconf(_SC_PAGE_SIZE)
将segment通过mmap映射入内存时，映射的长度选择segment的p_memsz字段，其包含p_filesz大小的实际文件内容，以及部分bss数据。因此通过mmap映射完后，还需要将偏移从p_filesz到p_memsz的内存空间清零，作为bss部分的数据空间

将进程的栈空间稍微开大点，否则会爆栈~~一开始我以为4KB就足够了，结果还是太年轻~~

最后，复现的、不那么优雅的静态链接程序的加载器的demo如下所示

#include <stdio.h>
#include <stdlib.h>
#include <elf.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <string.h>

#define KB * (1024ll)
#define MB * (1024ll KB)
/*
 * 传入的环境变量数组
 */
extern char **environ;
/*
 * 载入64位的静态链接程序exec，其参数个数为argc，其参数指针数组为argv，环境变量数组为environ */
void static_load_elf(char *exec, int exec_argc, char *exec_argv[], char **exec_environ); /* 载入64位的静态链接程序exec的各个segment */
void static_load_segments(int exec_fd, Elf64_Ehdr *elf64_ehdr);
/*
 * 根据System V api文档
 * 初始化程序的堆栈结构，即设置argc，argv和envp即可
 */
void *static_init_stack(int exec_argc, char *exec_argv[], char **exec_environ);
/*
 * 根据System V api文档
 * 初始化相关的寄存器，自然包括控制流的跳转
 */
void static_init_registers(Elf64_Ehdr *elf64_ehdr, void *stack);





/*
 * 载入64位的静态链接程序exec，其参数个数为argc，其参数指针数组为argv，环境变量数组为environ
 */
void static_load_elf(char *exec, int exec_argc, char *exec_argv[], char **exec_environ) {
	//以只读模式打开exec文件
	int exec_fd = open(exec, O_RDONLY);

	if(exec_fd < 0) { exit(EXIT_FAILURE); }

	/*
	 * 由于这里只展示原理性的东西
	 * 因此不会进行特别多的检查
	 */


	//载入静态链接的起始部分(头部、Program Header)，默认4KB以内
	Elf64_Ehdr *elf64_ehdr = (Elf64_Ehdr*)mmap(
			NULL,		//addr，即映射的虚拟地址
			4 KB, 		//length，映射的字节长度
			PROT_READ,	//prot，映射内存的属性
			MAP_SHARED,	//flags，映射内存的标志
			exec_fd,	//fd，映射内存的文件描述符
			0		//offset，文件描述符的起始偏移
	);
	if(elf64_ehdr == MAP_FAILED) { exit(EXIT_FAILURE); }

#ifdef DEBUG
	printf("elf64_ehdr address => %p\n", elf64_ehdr);
	printf("elf64_ehdr->e_phentsize => %d\n", elf64_ehdr->e_phentsize);
	printf("elf64_ehdr->e_phnum => %d\n", elf64_ehdr->e_phnum);
	printf("elf64_ehdr->e_phoff => %ld\n", elf64_ehdr->e_phoff);
#endif



	// 载入64位的静态链接程序exec的各个segment即可
	static_load_segments(exec_fd, elf64_ehdr);


	// 初始化堆栈结构，即设置argc，argv和envp即可
	void *stack = static_init_stack(exec_argc, exec_argv, exec_environ);


	// 完成寄存器初始化并进行跳转
	static_init_registers(elf64_ehdr, stack);
}




/*
 * 载入64位的静态链接程序exec的各个segment
 */
void static_load_segments(int exec_fd, Elf64_Ehdr *elf64_ehdr) {

	//首先读取segments描述符数组，即Program header数组
	Elf64_Phdr *elf64_phdrs = (Elf64_Phdr*)(((uintptr_t)(elf64_ehdr)) + elf64_ehdr->e_phoff);
#ifdef DEBUG
	printf("elf64_phdrs address => %p\n", elf64_phdrs);
	printf("prot: PROT_READ => %#x PROT_WRITE => %#x PROT_EXEC => %#x\n", PROT_READ, PROT_WRITE, PROT_EXEC);
	printf("Elf64_Phdr->p_flags: PF_R => %#x PF_W => %#x PF_X => %#x\n", PF_R, PF_W, PF_X);
#endif


	//依次遍历segments，将其载入内存
	for(int i = 0; i < elf64_ehdr->e_phnum; ++i) {
		Elf64_Phdr *elf64_phdr = &elf64_phdrs[i];
		//如果对应的p_type字段是PT_LOAD，则直接将其载入至内存中即可
		if(elf64_phdr->p_type == PT_LOAD) {
			uint64_t prot = 0;

			//根据elf64_phdr->p_flags来判断映射权限
			if(elf64_phdr->p_flags & PF_R) { prot |= PROT_READ; }
			if(elf64_phdr->p_flags & PF_W) { prot |= PROT_WRITE; }
			if(elf64_phdr->p_flags & PF_X) { prot |= PROT_EXEC; }


			/*
			 * segments的大小和虚拟地址根据p_align字段进行对齐即可
			 */
			void *elf64_phdr_vaddr_align = (void*)((uintptr_t)elf64_phdr->p_vaddr & (~((uintptr_t)elf64_phdr->p_align - 1)));
			size_t elf64_phdr_length_align = elf64_phdr->p_memsz + ((uintptr_t)elf64_phdr->p_vaddr - (uintptr_t)elf64_phdr_vaddr_align);
			off_t elf64_phdr_offset_align = elf64_phdr->p_offset & (~((uintptr_t)elf64_phdr->p_align - 1));

#ifdef DEBUG
			printf("elf64_phdrs[%d] elf64_phdr_vaddr_align => %p, elf64_phdr_length_align => %#lx, elf64_phdr_offset_align => %#lx prots => %#lx\n", i, elf64_phdr_vaddr_align, elf64_phdr_length_align, elf64_phdr_offset_align, prot);
#endif
			void *address = mmap(
					elf64_phdr_vaddr_align,		//addr，即映射的虚拟地址
					elf64_phdr_length_align, 	//length，映射的字节长度
					prot,				//prot，映射内存的属性
					MAP_PRIVATE | MAP_FIXED,	//flags，映射内存的标志
					exec_fd,			//fd，映射内存的文件描述符
					elf64_phdr_offset_align		//offset，文件描述符的起始偏移
			);

			//由于可能存在bss段等，因此需要将多余的空间置为0，否则执行会错误
			memset(((char*)elf64_phdr->p_vaddr) + elf64_phdr->p_filesz, 0, elf64_phdr->p_memsz - elf64_phdr->p_filesz);

			//测试，用来输出载入的segment的相关地址信息
#ifdef DEBUG
			printf("elf64_phdrs[%d] address => %p p_vaddr => %#lx; p_memsz => %#lx; p_flags => %#x p_filesz => %#lx p_align => %#lx\n\n", i, address, elf64_phdr->p_vaddr, elf64_phdr->p_memsz, elf64_phdr->p_flags, elf64_phdr->p_filesz, elf64_phdr->p_align);
#endif
		}
	}
}


/*
 * 根据System V api文档
 * 初始化程序的堆栈结构，即设置argc，argv和envp即可
 */
void *static_init_stack(int exec_argc, char *exec_argv[], char **exec_environ) {
	/*
	 * 申请堆栈所需要的地址
	 */
	void *stack = mmap(
			NULL,				//addr，即映射的虚拟地址
			1 MB, 				//length，映射的字节长度
			PROT_READ | PROT_WRITE,		//prot，映射内存的属性
			MAP_PRIVATE | MAP_ANONYMOUS,	//flags，映射内存的标志
			-1,				//fd，映射内存的文件描述符
			0				//offset，文件描述符的起始偏移
	);


	//这里栈空间的起始位置
	uintptr_t *sp = (uintptr_t*)((uintptr_t)(stack) + 1 MB - 4 KB);

	//这里设置当前栈帧的顶部
	void *res = (void*)sp;


	//压入exec_argc
	*sp++ = exec_argc;

	//压入exec_argv
	for(int i = 0; exec_argv[i]; ++i) {*sp++ = (uintptr_t)exec_argv[i];}
	//压入exec_argv结束的0
	*sp++ = 0;

	//压入exec_environ
	int environ_idx = 0;
	for(; exec_environ[environ_idx]; ++environ_idx) {
		if(strchr(exec_environ[environ_idx], '_') != exec_environ[environ_idx]) { *sp++ = (uintptr_t)exec_environ[environ_idx]; }
		else {
			char *environ = (char*)malloc(strlen(exec_argv[0] + 3));
			sprintf(environ, "_=%s", exec_argv[0]);
			*sp++ = (uintptr_t)environ;
		}
	}
	//压入exec_environ结束的0
	*sp++ = 0;


	//压入auxiliary vector entries，这些是内核提供给用户空间的一些设置参数，否则glibc无法正常运行。不能直接复制加载器的，否则待加载程序会崩溃
	//for(Elf64_auxv_t *elf64_auxv_t = (Elf64_auxv_t*)&exec_environ[environ_idx + 1]; elf64_auxv_t->a_type != AT_NULL; ++elf64_auxv_t) {
	//	*((Elf64_auxv_t*)sp) = *elf64_auxv_t;
	//	sp = (uintptr_t*)((Elf64_auxv_t*)sp + 1);
	//}
	*((Elf64_auxv_t*)sp) = (Elf64_auxv_t){ .a_type = AT_RANDOM, .a_un.a_val = (uintptr_t)(stack) + 1 MB - 16};
	sp = (uintptr_t*)((Elf64_auxv_t*)sp + 1);
	*((Elf64_auxv_t*)sp) = (Elf64_auxv_t){ .a_type = AT_NULL};
	


#ifdef DEBUG
	printf("stack => %p\n", res);
	int argc = *(int*)res, i;
	printf("argc => %d\n", argc);

	char **argv = ((char**)res) + 1;
	for(i = 0; i < argc; ++i) { printf("argv[%d] = %s\n", i, argv[i]); }

	char **environ = argv + argc + 1;
	for(i = 0; environ[i]; ++i) { printf("environ[%d] = %s\n", i, environ[i]); }

	Elf64_auxv_t *elf64_auxv_t = (Elf64_auxv_t*)(environ + i + 1);
	for(i = 0; elf64_auxv_t[i].a_type != AT_NULL; ++i) { printf("auxiliary[%d].a_type = %#lx, auxiliary[%d].a_un.a_val = %#lx\n", i, elf64_auxv_t[i].a_type, i, elf64_auxv_t[i].a_un.a_val); }

#endif

	return res;
}




/*
 * 根据System V api文档
 * 初始化相关的寄存器，自然包括控制流的跳转
 */
void static_init_registers(Elf64_Ehdr *elf64_ehdr, void *stack){

	//通过内联汇编，初始化寄存器，并完成跳转
	__asm__ volatile(
			"mov %0, %%rsp;"	//将rsp设置为之前初始化的栈的位置
			"xor %%rdx, %%rdx;"	//将rdx设置为atexit部分
			"jmp *%1"		//将待跳转的目标地址存到寄存器中，然后间接跳转
			:
			: "r"(stack), "r"(elf64_ehdr->e_entry)
			: "rdx");
}


int main(int argc, char *argv[]) {

	if(argc == 1) {
		printf("Usage: static-loader file [args...]\n");
		exit(EXIT_SUCCESS);
	}

	/*
	 * argv[0] = "./static-loader"
	 * argv[1] = 待载入程序路径
	 * argv[2 : argc] = 待载入程序参数
	 * argv[argc] = 0
	 */
	static_load_elf(argv[1], argc - 1, argv + 1, environ);


	//理论上，完成跳转后，程序通过hlt退出，永远不会执行到该处
	exit(EXIT_FAILURE);
}

代码的注释已经非常详细了，下面直接给出静态链接程序的加载器demo

动态链接程序的加载

当前标准下的动态链接程序加载十分繁琐，但是其整体原理还是较为简单的。因此这里保留动态链接程序加载的主要原理，实现一个自定义的动态链接的标准，并实现一个基于该自定义标准的动态链接程序的加载器，从而帮助理解动态链接程序的加载过程及其原理

为什么需要动态链接

程序之间往往会包含一部分重复的代码(极端情况就是一个shell程序可能运行多份)。如果程序都采取静态链接，则作为进程加载的时候，需要将整个程序二进制文件都载入到内存中，这是十分浪费的。
因此，我们希望采用某种技术(实际上就是动态链接)，从而将程序可能重复的部分仅仅加载一次

为什么静态链接不行

简单来说，是由于程序的编译链接和程序的载入不是同时进行的

静态链接要求在编译链接时一次性生成程序运行所需要的所有数据，但是其必定无法确定在将来被载入时的重复代码部分的内存地址
而动态链接在编译时仅仅按照相关标准生成重复代码调用的相关标记，则可以正常完成编译；在载入时再通过编译留下的标记信息和系统调用，载入重复代码或获取已经被载入的重复代码的内存地址，从而正确执行。

如何实现动态链接

实际上，根据前面的分析，我们知道。采用动态链接的程序，其在载入的时候，会动态的载入重复部分的代码，并执行这部分代码。这部分代码就是动态加载库。

动态加载库的代码格式
因此，实际上要实现动态链接，起码需要产生可以不依赖加载地址进行执行的代码形式，从而将其作为动态加载库的代码格式。而这就是位置无关代码格式，其访问变量或代码时，都通过相对rip寄存器的偏移进行访问，从而避免了对于载入地址的依赖性。
程序的编译
根据前面的分析，采用动态链接载入的程序，在编译的时候需要按照相关标准生成动态链接库的调用标记。最简单的方式，就是将所有待解析的符号地址及其特征(如符号名)存储在一个数组中。这样，当编译的时候，只需要生成该数组即可,然后调用的地址为该数组中的待解析符号地址即可。这个数组即GOT(Global Offset Table)
而为了方便最终的符号解析，动态链接库中应该包含一个动态链接库的符号导出表，其包含符号在当前动态链接库的相对偏移以及符号的特征。
载入程序时，根据依赖顺序首先载入所有的动态链接库，然后根据载入符号表中的导出表，从而根据其符号特征重新解析导入表中符号对应的地址即可。

动态链接实现细节

由于是一个小的演示demo，所以这里定义了自己的一个非常简单的动态链接库标准

该动态链接库需要程序员自己手动加载，而非类似ld.so的自动递归的加载动态链接库。并且动态链接库的查找目录是固定的，和可执行程序处于同一个目录
动态链接库的符号表必须位于固定位置(这里实现的就是位于动态链接库的起始位置)
动态链接库需要编译成位置无关代码

首先，我们规定一个符号的数据结构，从而生成前面分析事提到的符号表，如下所示

#define SYMBOL_SIZE (64)
#define SYMBOL_TYPE_TERMINATE	(0)
#define SYMBOL_TYPE_IMPORT	(1)
#define SYMBOL_TYPE_EXPORT	(2)

typedef struct SYMBOL {
	uint64_t offset;
	uint64_t type;
	char name[SYMBOL_SIZE - sizeof(uint64_t) - sizeof(uint64_t)];
} Symbol;

实际上，其包括符号的地址以及符号特征(符号名称)等信息。而为了导入符号和导出符号公用一个数据结构，我们添加了type字段用来进行区分。
自定义的标准中要求将符号表放置在动态链接库的起始位置。为了使生成的动态链接库满足上述的标准，我们可以通过汇编代码，以及objcopy命令，生成raw文件，而非ELF格式的文件。为了方便汇编代码的操作，我们定义了如下的一些宏

#ifdef __ASSEMBLER__
/*
 * 这里主要定义一些汇编指令下的宏，方便编写汇编源代码
 */

//定义一个符号表的起始
#define DYNLIB_SYMS	symbols_start:

/*
 * 定义一个符号表的终结
 * .align ALIGN GAP;		按ALIGN对齐下一个符号，中间使用GAP填充
 * .fill REPEAT, SIZE, VALUE;	将SIZE大小的VALUE值拷贝REPEAT次
 */
#define DYNLIB_SYMS_END	.align SYMBOL_SIZE, 0; \
	.fill SYMBOL_SIZE, 1, 0; 

/*
 * 在汇编源代码中，定义导出表
 * 其中包含相对载入基址的相对偏移，以及符号特征
 * .quad VALUE			定义了一个QUAD类型的数据，其值为VALUE
 * .asciz VALUE			使用ASCII字符声明VALUE文本字符串，并在结尾自动添加结束符\0
 * #VAR				将宏参数转换为字符常量
 */
#define EXPORT(name) .align SYMBOL_SIZE, 0; \
	.quad (name - symbols_start); \
	.quad SYMBOL_TYPE_EXPORT; \
	.asciz #name;


/*
 * 在汇编源代码中，定义导入表
 * 其中包含符号待解析地址，以及符号特征
 * .quad VALUE			定义了一个QUAD类型的数据，其值为VALUE
 * .ascii VALUE			使用ASCII字符声明VALUE文本字符串，结尾没有结束符\0
 * str1##str2			将两个token连接为字符常量
 */
#define IMPORT(name) .align SYMBOL_SIZE, 0; \
	name##_dyn: \
	.quad 0; \
	.quad SYMBOL_TYPE_IMPORT; \
	.asciz #name; \

#else
/*
 * 前面汇编源代码中仅仅实现了相关动态链接库的符号标记
 * 这里是上述动态链接库的具体符号标记的含义
 */

#include <stdint.h>
typedef struct SYMBOL {
	uint64_t offset;
	uint64_t type;
	char name[SYMBOL_SIZE - sizeof(uint64_t) - sizeof(uint64_t)];
} Symbol;

#endif		//__ASSEMBLER__

可以看到，其主要实现了汇编文件中定义struct SYMBOL结构体的操作，即IMPORT(NAME)和EXPORT(NAME)。对于导入符号来说，其最终的符号地址需要在载入的时候进行解析，因此将offset字段填充为0即可，在载入的时候，导入的符号已经加载进内存了，则将该符号的地址覆盖到符号的offset字段即可，其余按照标准和结构体字段的含义进行填充即可；而对于导出符号来说，其最终的符号地址虽然不知道，但是其相对动态链接库加载地址的偏移始终是不变的，则先将该值填充为相对偏移值即可，等载入的时候，在offset字段添加动态链接库的载入地址即可

下面是一个动态链接库的具体样例，如下所示

#include "dynamic.h"

// 将导入导出表放置在最开始
DYNLIB_SYMS

// 导出libb_fun导出
EXPORT(libb_func)

// 导入liba.S中的liba_var导出
IMPORT(liba_func)


// 这里导入导出表结束
DYNLIB_SYMS_END

libb_func:
	call *liba_func_dyn(%rip)
	addq $1, %rax
	ret

这里唯一需要说明的就是动态链接库中，对于导入符号的调用。虽然在编译的时候，并不知道导入符号的最终地址，但是在该动态链接库载入的时候，该动态链接库的导入符号一定已经被载入内存中。则在动态链接库载入的过程中，将导入符号的地址写入导入符号表的offset中即可。也就是虽然在编译的时候，并不知道导入符号的最终地址，但是可以确定导入符号的地址是在导入符号表的offset字段的，而导入符号表的地址在编译时可以通过相对偏移进行访问，从而也就保证了动态链接库在载入完后可以通过导入符号表正确调用导入的符号。

最后，则是程序调用动态链接库的相关说明。根据前面的说明，实际上程序在加载动态链接库的时候，唯一的工作就是处理动态链接库的符号表

对于导出符号类型，将其struct SYMBOL的offset字段添加上动态链接库的载入地址，从而获得符号的真实地址。除此之外，还需要保存一份struct SYMBOL，方便之后动态链接库的导入符号的解析以及程序调用该导入符号

对于导入符号类型，根据标准，其依赖的动态链接库已经完成加载，则所调用的导入符号也已经完成了解析。则遍历前面1.步骤中保存的符号表，找到该符号，并且覆盖该动态链接库导入符号的offset字段，从而确保该动态链接库调用导入符号的正常执行。

演示代码如下所示

#include "dynamic.h"
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>
#include <assert.h>


/*
 * 当前程序加载的动态链接库中所有的程序
 */
static Symbol *symbols[128] = {NULL};
static int symbols_size = 0;


/*
 * 处理动态链接库中导入符号类型的符号
 */
void
do_type_import_symol(Symbol *symbol)
{
	assert(symbol->type == SYMBOL_TYPE_IMPORT);
	if(symbol == NULL) { return; }

	printf("[*] try to resolve the import symbol:%s\n", symbol->name);

	// 遍历程序的符号表，如果找到符号特征(符号名称)相同的，则解析符号即可
	for(int i = 0; i < symbols_size; ++i) {
		if(!strcmp(symbol->name, symbols[i]->name)) {
			printf("[*] succeed to resolve the import symbol:%s\n", symbol->name);
			symbol->offset = (uint64_t)symbols[i]->offset;
			return;
		}
	}

	printf("[*] failed to resolve the import symbol:%s\n", symbol->name);
}



/*
 * 处理动态链接库中导出符号类型的符号
 */
void
do_type_export_symbol(Symbol *symbol, void *base_addr)
{
	assert(symbol->type == SYMBOL_TYPE_EXPORT);
	if(symbol == NULL) { return; }

	printf("[*] try to resolve the export symbol:%s\n", symbol->name);

	symbols[symbols_size] = symbol;
	symbols[symbols_size]->offset += (uint64_t)base_addr;
	++symbols_size;
	
	printf("[*] succeed to resolve the export symbol:%s\n", symbol->name);
}



/*
 * 这里根据库的名称
 * 加载当前目录下的.o文件即可
 */
void
load(const char *lib_name)
{
	if(lib_name == NULL) { return; }

	printf("[*] try to load the %s\n", lib_name);

	int lib_name_len = strlen(lib_name);
	char *lib_path = (char*)malloc(sizeof(char) * (lib_name_len + 2 + 7));
	assert(lib_path != NULL);
	sprintf(lib_path, "./%s.dynlib", lib_name);

#ifdef DEBUG
	printf("[*] try to load the %s with path:%s\n", lib_name, lib_path);
#endif

	int fd = -1;
	if((fd = open(lib_path, O_RDONLY)) < 0) {
		printf("[*] fail to open the %s\n", lib_name);
		free(lib_path);
		return;
	}

	//通过mmap映射
	void *base_addr = NULL;
	if((base_addr = mmap(NULL, 4096, PROT_EXEC | PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0)) == NULL) {
		printf("[*] fail to load the %s\n", lib_name);
		free(lib_path);
		return;
	}


	/*
	 * 由于每一个动态链接的符号表在其首部
	 * 则依次遍历即可
	 *
	 * 如果是导出表，则向全局符号表中添加符号即可
	 * 如果是导入表，则遍历全局符号表，查找对应的符号即可
	 */
	for(Symbol *symbol = (Symbol*)base_addr; symbol->type != SYMBOL_TYPE_TERMINATE; ++symbol) {
#ifdef DEBUG
		printf("[*] symbol address => %p\n", symbol);
		printf("[*] try to load the symbol: %s\n", symbol->name);
#endif
		switch(symbol->type) {
			case SYMBOL_TYPE_IMPORT:
				do_type_import_symol(symbol);
				break;
			case SYMBOL_TYPE_EXPORT:
				do_type_export_symbol(symbol, base_addr);
				break;
		}
	}

	printf("[*] succeed to load the %s\n", lib_name);
	free(lib_path);
}


/*
 * 调用动态链接库中的符号表
 * 即遍历程序所有的符号表，找出给定的符号特征并且执行即可
 */
void
do_execute_symbol(const char *name)
{
	if(name == NULL) { return; }

	printf("[*] try to execute the symbol:%s\n", name);

	// 遍历程序的符号表，如果找到符号特征(符号名称)相同的，则执行符号即可
	for(int i = 0; i < symbols_size; ++i) {
		if(!strcmp(name, symbols[i]->name)) {
#ifdef DEBUG
			printf("[*] the address of the symbol:%s is %lx\n", name, symbols[i]->offset);
#endif
			printf("[*] %s() = %ld\n", name, ((uint64_t (*)())symbols[i]->offset)());
			return;
		}
	}

	printf("[*] failed to execute the symbol:%s\n", name);
}

int main(void) {
	setbuf(stdin, NULL);
	setbuf(stdout, NULL);
	setbuf(stderr, NULL);

	load("liba");
	do_execute_symbol("liba_func");
	load("libb");
	do_execute_symbol("libb_func");
	return 0;
}

这里给出动态链接程序的加载器demo

L2多处理器内核上的线程管理(kmt)

实验背景

实际上，借助AbstractMachine提供的机制(C Runtime、物理内存、中断/异常等)，可以很容易地实现CPU地虚拟化，并对进程/线程进行模拟。

目前，我们已经知道操作系统的虚拟化是由中断机制实现的，在进程/线程执行时，当中断到来时，操作系统代码开始执行并保存处理器运行的寄存器现场；在中断返回时，其会选择任何一个进程/线程已经保存的寄存器现场进行恢复，从而实现上下文的切换。

在此实验中，我们需要实现多处理器操作系统内核中的内核线程API。在完成这个实验后，就可以得到一个真正的嵌入式操作系统。

实验描述

实验总览
这个实验在L1的基础上，进一步实现内核线程相关的操作系统内核API：
相比Lab1，os模块中新增了trap和on_irq两个函数，分别是系统中唯一中断/系统调用的入口和中断处理程序的回调注册；

pmm模块保持不变，可以沿用Lab1的实现，但因为这个实验中多了中断，需要进行一些小的修改；
新增了kmt模块，需要完成struct task、struct spinlock和struct semaphore的定义，并实现其中全部的API
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
typedef Context *(*handler_t)(Event, Context *);
MODULE(os) {
 void (*init)();
 void (*run)();
 Context *(*trap)(Event ev, Context *context);
 void (*on_irq)(int seq, int event, handler_t handler);
};

MODULE(pmm) {
 void  (*init)();
 void *(*alloc)(size_t size);
 void  (*free)(void *ptr);
};

typedef struct task task_t;
typedef struct spinlock spinlock_t;
typedef struct semaphore sem_t;
MODULE(kmt) {
 void (*init)();
 int  (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
 void (*teardown)(task_t *task);
 void (*spin_init)(spinlock_t *lk, const char *name);
 void (*spin_lock)(spinlock_t *lk);
 void (*spin_unlock)(spinlock_t *lk);
 void (*sem_init)(sem_t *sem, const char *name, int value);
 void (*sem_wait)(sem_t *sem);
 void (*sem_signal)(sem_t *sem);
};
OS(Operating Systems)模块
操作系统的主循环
os模块是操作系统主循环的代码，主要负责系统的初始化和中断响应。在Lab1的框架代码中，已经包含如下函数：

os->init()会在系统启动时被第一个处理器调用，其是在单处理器状态下完成必要的初始化——因此无需担心数据竞争等麻烦；

os->run()是操作系统启动后，每一个处理器必须执行的一些代码。在执行os->run时，操作系统已经完成了所有的初始化工作，每个处理器都会调用同一个os->run

理解os模块，要从程序执行的入口开始，以下是框架代码执行的流程：
1
2
3
4
5
6
7
int main() {
  ioe_init();
  cte_init(os->trap);
  os->init();
  mpe_init(os->run);
  return 1;
}
在每个处理器调用os->run执行后，操作系统就成为了中断处理程序。因此，当调用mpe_init()之后，所有处理器都开始执行os->run()，操作系统即正式启动，而该启动代码就成为了当前处理器上的第一个线程——这个线程是该处理器上的idle线程；而当系统中没有任何线程可以被调度时，处理器仍然需要执行点什么，直到下一个中断来临，因此该idle中断可以是一个死循环，如下所示
1
2
3
4
static void os_run() {
 iset(true);
 while(1);
}
主循环的另一部分是本次试验新增的中断处理程序的入口

os->trap(ev, context)：中断/异常处理程序的唯一入口。中断后，AbstractMachine会将所有寄存器保存到堆栈上，然后调用os->trap，并且在函数返回后，将os->trap返回的寄存器现场恢复到CPU上

直到mpe_init()之前，都只有一个处理器在执行。在上述的代码中，cte_init(os->trap)指定了os->trap()是唯一的中断处理程序，所有的处理器发生中断都会统一调用os->trap()，这也就需要小心并发编程

中断处理程序
os模块的另一个重要功能是管理系统中的中断处理程序——我们并不希望大家在每当有一个新的功能以后，都直接去更改os->trap的代码，因此这里提供了另一个API:

os->on_irq(seq, event, handler)：注册一个在中断时调用的callback

on_irq的含义是在os->trap(ev, ctx)执行时，当ev.event(事件编号)和event匹配时，调用handler(event, ctx)。其中：

seq决定了handler被调用的顺序，seq小的handler先被调用。seq相同的，按照任意顺序调用

当event == EVENT_NULL时，在任何中断/异常时都调用handler

我们允许一个，且仅允许一个handler返回一个Context，在中断返回时，恢复到这个Context。当多个handler都返回context时，是undefined behavior

通过os->on_irq，我们可以注册若干中断处理程序，在适当的时机做适当的事情——这类似于面向切面编程的设计。此时，我们的os模块并不知道，也无需知道系统中有多少中断、多少设备驱动程序可能会处理终端。

PMM(Physical Memory Management)模块
pmm与之前行为一致，但因为其被调用的场景增加了，我们需要将pmm->alloc和pmm->free更改为线程/中断安全的

具体来说，我们要求：

可以再中断里调用pmm->alloc()和pmm->free()；

内存分配/回收时，简单起见，不允许被中断

KMT(Kernel Multi-Threading)模块
模块初始化
kmt->init()负责初始化必要的数据，例如分配一些重要的数据结构。一般来说，要在os->init()时调用kmt->init()。整个系统启动只调用一次kmt->init()

线程管理
1
2
int  (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
void (*teardown)(task_t *task);
其中create在系统中创建一个线程，该线程立即就可以被调度执行。这里可以认为通过create创建的线程永不返回——但其有可能在永远不会被调度执行的情况下被kmt->teardown函数回收
teardown回收相应的为线程分配的资源——例如为task_t动态分配的内存。需要注意的是，线程只有永远不会被调度到处理器上执行的前提下，才能被回收，即可以认为回收的线程不再持有任何自旋锁或在信号量上等待

自旋锁
1
2
3
void (*spin_init)(spinlock_t *lk, const char *name);
void (*spin_lock)(spinlock_t *lk);
void (*spin_unlock)(spinlock_t *lk);
上述代码用来保护一段强原子性的代码(任何其他线程、中断处理程序、其他处理器都不能同时得到同一把锁)
允许在中断处理程序中调用自旋锁

允许任意在任意处理器的任意线程中调用自旋锁

spin_lock将会关闭处理器的中断，因此对一个处理器而言，持有任何一个自旋锁之后就不会再发生线程切换
spin_unlock在解除最后一个当前处理器持有的自旋锁之后，需要将处理器的中断状态恢复。例如在中断处理程序中，中断是关闭的，则spin_unlock不应该打开中断
信号量
1
2
3
void (*sem_init)(sem_t *sem, const char *name, int value);
void (*sem_wait)(sem_t *sem);
void (*sem_signal)(sem_t *sem);
在信号量初始化时，value指定了其初始化的数值。如果value==1,可以把信号量当做互斥锁；如果value==0，可以把信号量当做生产者-消费者缓冲区管理实现。而sem_wait和sem_signal分别对应的P/V操作

允许在线程中执行信号量的sem_wait操作。在P操作执行没有相应资源时，线程将被阻塞(不再被调度执行)。中断没有对应的线程、不能阻塞，因此不能在中断时调用 sem_wait

允许在任意状态下任意执行sem_signal，包括任何处理器中的任何线程和任何处理器的任何中断。

正确性标准
Safety和Liveness
在任意时刻，操作系统中都可能有多个线程，你需要设计调度的策略，在多个处理器中调度这些线程，使操作系统能够被执行的线程尽可能不发生饥饿

官方测试用例
官方测试用例使该程序看起来更像一个操作系统，虽然其并不能作为”压力测试”来帮助检查kmt实现的正确性。
其提供了dev模块及其实现，并包含了以下设备的驱动：
input，支持读取键盘的输入

fb，支持一个软件模拟的2D显示加速器的写入

tty1，tty2，两个支持读写的虚拟终端，使用Alt-1，Alt-2在虚拟终端之间切换
sda，支持读写的物理磁盘。
在代码合并后，需要在os->init()中手工添加设备模块的初始化dev->init()。如果实现正确，即可完成中断处理程序和相关线程的初始化。
此后，就可以创建若干访问设备的线程，样例如下所示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void tty_reader(void *arg) {
 device_t *tty = dev->lookup(arg);
 char cmd[128], resp[128], ps[16];
 snprintf(ps, 16, "(%s) $ ", arg);
 while (1) {
   tty->ops->write(tty, 0, ps, strlen(ps));
   int nread = tty->ops->read(tty, 0, cmd, sizeof(cmd) - 1);
   cmd[nread] = '\0';
   sprintf(resp, "tty reader task: got %d character(s).\n", strlen(cmd));
   tty->ops->write(tty, 0, resp, strlen(resp));
 }
}


static void os_init() {
 ...
 kmt->create(task_alloc(), "tty_reader", tty_reader, "tty1");
 kmt->create(task_alloc(), "tty_reader", tty_reader, "tty2");
}

实验指南

在Bug中活下来

实际上，Lab2希望可以在多处理器、中断都存在的情况下，仍然能保持正确。或许，只有在做完实验以后，才能对下面这些话产生真正的理解：

代码可以再多个处理器上被同时调用。因此需要小心地保证原子性、顺序性以及可见性。千万小心kmt->create()、kmt->sem_signal()等所有函数可能同时在多个处理器上被调用
在中断处理程序中，可以调用自旋锁。实际上，一个CPU的中断处理程序可以和另一个CPU访问同一个共享数据结构。因此自旋锁是保证正确性的重要手段
小心数据竞争。一切共享的数据都可能产生数据竞争——如果没有保护好的话。有些内存访问悄悄在意向不到的时候发生，例如对堆栈的访问

为此，实验中反复强调，通过一些手段，可以非常方便的帮助我们调试程序

通过预编译选项，控制log的输出，如下所示

#ifdef TRACE_F
  #define TRACE_ENTRY printf("[trace] %s:entry\n", __func__)
  #define TRACE_EXIT printf("[trace] %s:exit\n", __func__)
#else
  #define TRACE_ENTRY ((void)0)
  #define TRACE_EXIT ((void)0)
#endif

void f() {
  TRACE_ENTRY;
  printf("This is f.\n");
  TRACE_EXIT;
}

使用gdb进行调试。qemu提供了非常丰富的命令行选项
- -gdb，启动调试模式
- -S，让虚拟机在收到调试命令前不执行
- 在gdb中使用target命令连接远程调试
- 使用.gdbinit/-x/-ex，实现gdb脚本的预先执行
防御式编程。通过类似于fences、canaries、assert等，帮助我们更快的定义bug

实验环境

切换到master分支，然后从github上拉取L2实验即可

1	git remote add jyy https://hub.fastgit.org/NJU-ProjectN/os-workbench.git && git checkout master && git pull jyy L2

实验实现

下面式个人的思路及其实现，实验实现

自旋锁

实验指南中要求可以在任意处理器中调用自旋锁，这样可能就会导致一个问题
如果一个进程持有自旋锁lock。此时发生中断，而在中断处理程序中，同样请求了该自旋锁lock，则CPU就会阻塞在这里。

为了避免这种情况，实验指南要求，在获取自旋锁时，还需要同时关闭中断；在释放自旋锁时，恢复中断情况。

也就是说，申请或释放自旋锁时的时候，还需要保存和恢复中断情况。而这里有一个细节——即保存和恢复中断操作，与原子交换锁的操作的先后顺序。

由于自旋锁是可以并行的，如果我们首先保存状态，再原子交换，此时可能所有程序都执行了保存状态操作，从而互相覆盖掉状态；如果先原子交换，再关闭和保存状态，则刚刚执行完原子交换操作，在关闭中断前发生了中断，从而可能导致前面所说的中断处理程序的死锁。

下面是实现的自旋锁部分的逻辑

void
kmt_spin_init(spinlock_t *lk, const char *name)
{
    panic_on(lk == NULL, "error lk");

    lk->name = name;
    lk->lock = KMT_UNLOCK;
}

/*
 * 实现自旋锁
 * 
 * 根据实验指南说明，可以在任意位置调用自旋锁
 * 
 * 因此，考虑到如果在一个进程在占用了自旋锁，然后切换到中断处理程序中，该中断处理程序同样会可能也会该调用自旋锁
 * 从而导致了死锁
 * 
 * 因此，其应该首先关闭中断，然后在占用自旋锁。并且在占用自旋锁期间，不能调用yield进行切换
 * 
 * 考虑到可能多个cpu同是调用相同的自旋锁，因此其保存当前中断状态应该在获取锁之后，否则状态可能被覆盖掉 
 */
void
kmt_spin_lock(spinlock_t *lk)
{
    panic_on(lk == NULL, "error lk");


    /*
     * 关闭中断
     * 避免死锁产生
     */
    bool saved_ienabled_status = ienabled();
    iset(false);

    while(atomic_xchg(&(lk->lock), KMT_LOCKED) == KMT_LOCKED) {;}

    /*
     * 在这里保存关闭中断之前的状态
     * 否则可能中断状态可能会被覆盖掉
     */
    lk->saved_ienabled_status = saved_ienabled_status;
}

/*
 * 只需要反向spin_lock中的操作即可
 *
 * 首先保存之前的中断状态，然后释放锁
 * 此时，其他进程可以任意修改锁锁的状态，并不影响当前进程的状态
 * 
 * 最后，回复中断状况，这样子确保不会死锁
 */
void
kmt_spin_unlock(spinlock_t *lk)
{
    panic_on(ienabled() != false, "error ienabled()");

    bool saved_ienabled_status = lk->saved_ienabled_status;
    panic_on(atomic_xchg(&(lk->lock), KMT_UNLOCK) != KMT_LOCKED, "did not locked the lock");

    iset(saved_ienabled_status);
}

可以看到，虽然代码部分是并行的，但是栈空间不共享。因此首先通过变量保存其中断状态，然后关闭中断。此时在执行原子交换，由于已经关闭了中断，不可能发生死锁。最后，由于已经获取了锁，再保存中断状态就不会被覆盖掉了

安全内存分配

在L1中，我们的预期场景中，并没有开启CPU的中断响应。而在L2中，我们会开启中断响应，这可能会给L1中实现的代码带来一些麻烦——例如一个进程可能由多个cpu分段执行，从而导致cpu_current不一致。

根据实验指南所属，为了方便起见，直接在内存分配/回收时，关闭中断响应即可，包装如下所示

/*
 * 由于CPU可能被中断(主要是时钟中断、外设等中断)
 *
 * 这就给原本的内存分配和释放带来严重的问题
 * 其一个进程可能会由多个cpu执行，则cpu_current()并不能表示当前执行的cpu，从而产生意外
 * 
 * 为了解决该问题，在执行内存分配或释放的时候，直接关闭中断即可。这样子不会有时钟中断、外设中断等
 * 而内存分配或释放自己本身不会去调用中断等，从而确保了和L1中是一样的
 */
static void *
kalloc_safe(size_t size) {

  bool saved_ienabled_status = ienabled();
  iset(false);

  void *res = kalloc(size);

  panic_on(ienabled() != false, "error ienbled");
  iset(saved_ienabled_status);

  return res;
}


/*
 * 类似于前面的kalloc_safe
 *
 * 为了确保不会被中断
 */
static void
kfree_safe(void *chunk) {

  bool saved_ienabled_status = ienabled();
  iset(false);

  kfree(chunk);

  panic_on(ienabled() != false, "error ienbled");
  iset(saved_ienabled_status);
}

中断处理程序

根据实验指南，要求可以任意的注册若干中断处理程序。对于这种动态结构，自然可以通过链表进行管理，中断处理程序的相关结构体如下所示

//	kernel/include/os.h
    typedef struct IRQ {
        int seq;
        int event;
        handler_t handler;
        struct IRQ *next;
    } Irq;

//	kernel/src/os.c
/*
 * 用来注册中断处理程序
 * 这里按照实验指南中的提示
 * 使用单向链表进行管理即可
 * 
 * 由于其不需要线程/中断安全的，就非常简单的链表操作即可
 */
static Irq irqs = {
  .seq = MAGIC_SEQ,
  .event = MAGIC_EVENT,
  .handler = MAGIC_HANDLER,
  .next = NULL,
};

注册中断处理程序

注册中断处理程序很简单，就是在链表尾部添加节点即可，逻辑如下所示

static void
os_irq(int seq, int event, handler_t handler) {

  panic_on(handler == NULL, "error handler");

  Irq *iter = &irqs;
  panic_on(iter->seq != MAGIC_SEQ, "error seq");
  panic_on(iter->event != MAGIC_EVENT, "error event");
  panic_on(iter->handler != MAGIC_HANDLER, "error handler");

  /*
   * 由于中断处理程序按照seq从小到大排序
   * 因此下面开始从头遍历即可，插入到第一个节点的seq大于等于带插入的seq,
   * 插入该节点前面即可
   */
  while(iter->next && iter->next->seq < seq) { iter = iter->next; }

  Irq *irq = (Irq*)pmm->alloc(sizeof(Irq));
  panic_on(irq == NULL, "not enough space");

  irq->seq = seq;
  irq->event = event;
  irq->handler = handler;
  irq->next = iter->next;

  iter->next = irq;
}

调用中断处理程序

对于中断的响应，实验指南中也给了比较明确的框架，就是简单的遍历一遍上述的链表，并根据注册的中断事件和传入的中断事件进行匹配，并根据匹配结构来进行执行与否即可，代码如下所示

/*
 * 操作系统的中断处理程序
 * 
 * 根据实验指南的说明，其每一次能且仅能返回一个Context
 * 
 * 流程就是遍历一遍前面注册的中断处理程序即可，当event符合事，进行调用即可
 * 
 * 在中断处理程序中，其已经是关闭中断的，因此无需考虑执行时被其他程序打断(因为中断处理程序不会主动让出cpu)
 */
static Context *
os_trap(Event ev, Context *ctx)
{
  panic_on(ienabled() != false, "error ienabled");
  panic_on(ctx == NULL, "error ctx");

  debug_irq("%s", ev.msg);

  Context *next = NULL;


  /*
   * 下面尝试遍历中断处理程序的链表
   */
  panic_on(irqs.seq != MAGIC_SEQ, "error seq");
  panic_on(irqs.event != MAGIC_EVENT, "error event");
  panic_on(irqs.handler != MAGIC_HANDLER, "error handler");
  Irq *iter = irqs.next;
  while(iter) {
    if(iter->event == EVENT_NULL || iter->event == ev.event) {
      Context *temp = iter->handler(ev, ctx);
      panic_on(temp && next, "multiple context");

      if(temp) { next = temp; }
    }
    iter = iter->next;
  }

  panic_on(next == NULL, "no context");

  return next;
}

进程调度

有一说一，进程调度是本次试验我认为最有趣的地方，疯狂的debug，极大地加深了我对于panic_on和测试样例的认识。💀

进程结构体

这里实现的进程的结构体如下所示

/*
 * kmt中进程的数据结构
 */
#define KMT_FENCE             (0x17377199)
#define KMT_FENCE_SIZE        (2)
#define KMT_STACK_SIZE        (8192)
#define KMT_INIT_ROUND        (10)

struct task {
  const char *name;
  enum {
    READY,                             //可以被调度
    RUNNING,                           //正在被CPU执行
    WAIT_TO_SCHEDULE,                  //等待被调度进程调度
    WAIT_TO_LOAD,                      //被调度进程选中，但是还没有完成上下文加载
    WAIT_TO_AWAKE_AND_SCHEDULE,        //当前进程缺乏资源，需要等待其他进程唤醒，并且没有经过调度进程调度，会有栈数据竞争风险
    WAIT_TO_AWAKE,                      //当前进程缺乏资源，需要等待其他进程唤醒
    DEAD,                              //即其永远不会在被调度，可以释放其资源
  } status;
  int round;                           //剩余的时间片
  Context *context;
  task_t *fd, *bk;
  sem_t *fake_sem_fd, *fake_sem_bk;     //等待队列的链表结构
  uint32_t fence1[KMT_FENCE_SIZE];
  uint8_t stack[KMT_STACK_SIZE];
  uint32_t fence2[KMT_FENCE_SIZE];
};

除了fake_sem_fd和fake_sem_bk字段，其余字段都是其他进程结构中非常常见的字段。
而对于fake_sem_fd和fake_sem_bk字段，其是后面信号量中由双向循环链表抽象的等待队列的相关结构

进程调度

进程调度是通过中断实现的——一般是由时间中断或yield中断的响应，引起进程调度

因此，首先需要弄明白中断的过程(这里有大坑)

中断过程

实际上，其中断过程如下所示

这里有进程A，正在执行，其上下文如下所示
此时，进程A触发中断。则CPU会自动压入此时的上下文，然后执行trap逻辑(实际上还包含了其他的一些函数，这里就都抽象为trap)，最后跳转到前面实现的中断处理程序os->trap执行，如下所示
执行os->trap执行后，其返回了新的上下文(可能还是进程A保存的上下文)。但注意，此时仍然在进程A的栈上，因此其会继续执行trap后面的指令。如下所示
此时，后续的trap指令，会恢复前面返回的新的上下文，从而可能更换了栈结构，完成了一次中断

实际上，进程调度就可以在os->trap中完成。如果我们注册了一个如下的中断处理程序，其会在每次中断时，将当前传入的context保存到进程的结构体中；然后在所有进程中选择一个可以调度的进行调度，即可完成进程调度。看起来貌似很美好，实际上这里就隐藏了数据竞争，如下图所示

由于是多核CPU，当其中一个CPU将context保存到被中断进程A时，并且此时进程A可以被调度时，则产生了数据竞争——则很可能另一个CPU就调度了进程A，从而与前面的CPU共享一个栈，产生严重的数据竞争。

实际上，为了解决这个问题，这里参考了一个非常机智的方法——分析上面产生数据竞争的原因，就是中断处理程序和被中断处理程序共用一个栈导致的；如果对于每一个CPU，其每一次中断后，都首先转移到一个不同于被中断进程的中断处理栈，然后在进行相关的中断处理(比如调度)，最后在中断处理栈中继续后续操作，则完全不可能产生如下的数据竞争。

中断逻辑

基于上面的中断过程及相关的分析，这里结合L2给出的框架代码，给出实验中实现的中断逻辑

首先，为每一个CPU保存一个current_task指针，并且同时保存一个该CPU对应的调度上下文schedule_context。

每一次中断处理的时候，如果处理非调度类型的中断，则按照上述流程执行即可——虽然被中断进程和中断进程共用一个栈，但是被中断进程不会被其他进程调度，并且中断进程返回的也仍是该被中断进程的上下文，因此不会数据竞争。其相关流程如下所示
非调度的中断逻辑

如果处理的是调度类型的中断，则与上面的逻辑大不相同。根据分析，为了避免栈数据竞争，则首先需要返回提前准备好的调度上下文schedule_context；然后在调度上下文中，通过current_task指针更改被中断的进程的状态，并且选择待调度的进程，覆盖掉current_task。之后，主动在调用yield（）中断，触发中断处理程序，最终恢复current_task指针中的上下文，也就是调度时被选中的进程上下文。相关流程如下逻辑所示
调度的中断逻辑

最终，其相关的代码实现如下所示

//kernel/src/kmt.c
/*
 * 这里提前实现一些对于列表的操作
 * 在列表的操作中，都没有申请锁
 * 仅仅确认一下获取锁了
 * 
 * 遍历的时候沿着fd方向遍历，则插入沿着bk方向插入即可
 */
static void
list_insert(task_t *head, task_t *task)
{
    panic_on(head == NULL, "error task");
    panic_on(task == NULL, "error task");

    panic_on(atomic_xchg(&(tasks_lock.lock), KMT_LOCKED) != KMT_LOCKED, "did not locked the lock");
    CHECK_TASK_LIST(head);
    CHECK_TASK_FENCE(head);

    task_t *fwd = head, *bck = fwd->bk;


    task->fd = fwd;
    task->bk = bck;
    fwd->bk = bck->fd = task;

    CHECK_TASK_FENCE(task);
    CHECK_TASK_LIST(task);
}


/*
 * 对于列表删除操作来说，
 * 和列表插入操作十分相似
 * 
 * 同样不会申请锁，仅仅确认一下锁而已
 */
static void
list_remove(task_t *task)
{
    panic_on(task == NULL, "error task");

    panic_on(atomic_xchg(&(tasks_lock.lock), KMT_LOCKED) != KMT_LOCKED, "did not locked the lock");
    CHECK_TASK_FENCE(task);
    CHECK_TASK_LIST(task);

    task_t *fwd = task->fd, *bck = task->bk;

    fwd->bk = bck;
    bck->fd = fwd;
}



/*
 * 下面就是中断处理程序
 * 根据实验指南，每一次中断处理程序，都通过注册中断处理程序进行
 * 
 * 中断处理程序包含最基本的两部分——上下文保存和上下文恢复
 * 
 * 当前任务上下文保存：即保存中断处理程序中传入的Context即可
 * 恢复任务上下文：   根据状态信息，则返回对应的context即可
 * 
 * 在中断处理程序中，由于current_tasks的状态要么是RUNNING，要么是WAIT_TO_LOAD，因此不可能被其他cpu访问，访问除了fd、bk字段时无需上锁
 * 
 */

/*
 * 当前任务上下文保存，注册为最小的seq，从而确保每次中断第一个执行
 *
 * 当第一次进入os_trap的时候，其保存到被中断的进程即可，即currents_task中，此时其进程状态是RUNNING
 * 当第二次进入os_trap的时候，其保存到调度进程即可，即switchs_task中，此时其进程状态是WAIT_TO_LOAD
 */
static Context *
save_context(Event ev, Context *context)
{
    panic_on(context == NULL, "error context");
    int cpu = cpu_current();
    task_t *task = current_tasks[cpu];


    switch(task->status) {
        case RUNNING:
            /*
             * 说明是非主动进行中断
             * 则简单保存上下文即可
             */
        
        case WAIT_TO_AWAKE_AND_SCHEDULE:
            /*
             * 当前进程被阻塞，
             * 则其保存上下文，然后等待调度即可
             */

            task->context = context;
            break;
        

        case WAIT_TO_LOAD:
            /*
             * 刚刚被调度进程选中，准备恢复该进程
             * 此时context是调度进程的上下文，则保存级即可
             */
            schedule_contexts[cpu] = context;
            break;

        default:
            panic("error status");
    }

    CHECK_TASK_CONTEXT(task);
    CHECK_TASK_FENCE(task);
    return NULL;
}


/*
 * 恢复任务的上下文，注册为最大的seq，从而确保每次中断最后一个执行
 *
 * 其根据task的状态，分别设置相关的状态，返回相关的上下文即可
 */
static Context *
load_context(Event ev, Context *context)
{
    int cpu = cpu_current();
    task_t *task = current_tasks[cpu];
    Context *next = NULL;

    switch(task->status) {
        case RUNNING:
            /*
             * 中断已经处理完毕
             * 可以继续运行
             * 则直接返回其上下文即可
             */
            next = task->context;
            break;


        case WAIT_TO_AWAKE_AND_SCHEDULE:
            /*
             * 当前进程被阻塞，
             * 则其保存上下文，然后等待调度即可
             */
        
        case WAIT_TO_SCHEDULE:
            /*
             * 说明当前进程需要被调度，
             * 则需要切换到调度进程上
             */
            next = schedule_contexts[cpu];
            break;

        default:
            panic("error status");

    }

    return next;
}


/*
 * 时间中断处理程序
 * 这里就是简单的让进程进行调度即可
 * 因此这里设置进程状态即可
 */
static Context *
irq_time_handle(Event ev, Context *context)
{
    /*
     * 经过了save_context后，其task的状态只有当前cpu可以更改，无需上锁
     * 将其状态标注为等待调度即可
     * 
     * 只有RUNNING状态的进程，才会发生TIME的中断，需要确认一下
     */
    panic_on(ev.event != EVENT_IRQ_TIMER, "error ev");
    int cpu = cpu_current();
    task_t *task = current_tasks[cpu];

    switch (task->status)
    {
        case RUNNING:
            /*
             * 如果进程是正常的RUNNING状态
             * 判断剩余的时间片，并且根据时间片状态，进行相关的切换
             */
            if(--task->round <= 0) { task->status = WAIT_TO_SCHEDULE;}
            break;

        case WAIT_TO_AWAKE_AND_SCHEDULE:
            /*
             * 当前进程被阻塞,调用yield之前，
             * 然后被时间中断了
             * 前面已经保存过了状态，则什么都不需要做
             */
            break;
        
        default:
            panic("error status");
    }

    return NULL;
}



/*
 * yield中断处理程序
 * 这里就是简单的让进程进行调度即可
 * 因此这里设置进程状态即可
 */
static Context *
irq_yield_handle(Event ev, Context *context)
{
    /*
     * 经过了save_context后，其task的状态只有当前cpu可以更改，无需上锁
     * 将其状态标注为等待调度即可
     * 
     * 如果是WAIT_TO_SCHEDULE，则是调度程序执行的yield，不用做任何更改
     * 其余，只可能是RUNNING状态的进程，发生yield
     */
    panic_on(ev.event != EVENT_YIELD, "error ev");
    int cpu = cpu_current();
    task_t *task = current_tasks[cpu];

    switch(task->status) {
        case RUNNING:
            /*
             * 说明此时程序主动放弃cpu
             * 想切换到其他进程，设置为调度即可
             */
            task->status = WAIT_TO_SCHEDULE;
            break;
        
        case WAIT_TO_LOAD:
            /*
             * 说明是调度进程完成了调度
             * 要将该进程恢复
             * 设置其状态即可
             */
            task->status = RUNNING;
            break;

        case WAIT_TO_AWAKE_AND_SCHEDULE:
            /*
             * 当前进程被阻塞，
             * 然后调用了yield了
             * 前面已经保存过了状态，则什么都不需要做
             */
            break;

        default:
            panic("error status");
    }

    return NULL;
}

/*
 * 这里用来最终完成进程的调度工作
 * 即os_run最后执行的逻辑
 * 
 * os_trap在处理完成任何一个进程的中断处理程序后，如果需要进行进程切换
 * 都会切换到该上下文中，此时被中断的程序还不可被调度，从而避免栈竞争
 * 
 * 
 */
void
kmt_schedule(){

    int cpu = cpu_current();
    while(1) {
        yield();



        task_t *task = current_tasks[cpu];

        kmt_spin_lock(&tasks_lock);
        /*
         * 现在已经和被中断进程的栈分开了，从而避免了栈竞争
         * 首先根据被中断的进程的状态，更改其对应的状态
         */
        switch (task->status)
        {
            case WAIT_TO_SCHEDULE:
                task->status = READY;
                break;

            case WAIT_TO_AWAKE_AND_SCHEDULE:
            /*
             * 则其完成调度
             * 将其状态更改为WAIT_TO_AWAKE即可
             */
                task->status = WAIT_TO_AWAKE;
                break;

            default:
                panic("error status");
        }
        kmt_spin_unlock(&tasks_lock);



        /*
         * 然后开始调度可用的进程
         * 由于初始时已经添加了和cpu相同个数的idle进程，因此最多遍历一轮即可获取进程
         */
        kmt_spin_lock(&tasks_lock);
        task = task->fd;
        while(task->status != READY) { task = task->fd; }

        task->status = WAIT_TO_LOAD;
        task->round = KMT_INIT_ROUND;
        kmt_spin_unlock(&tasks_lock);


        //然后调用yield，将其载入即可
        current_tasks[cpu] = task;
    }
}

创建进程

创建进程就相对来说很简单了，就是将task_t结构体填充，然后插入进程链表中即可。这里要将新创建的进程状态设置为READY，因为其应该是可以被调用的

/*
 * 创建新进程
 * 主要包括两个方面
 * 
 * 一方面是填充传入的task指针
 * 
 * 另一个方面是将当前task指针插入到所有的进程链表中
 * 这部分访问共享资源，需要申请锁结构
 */
static int
kmt_create(task_t *task, const char *name, void (*entry)(void *arg), void *arg)
{
    panic_on(task == NULL, "error task");

    task->name = name;
    task->status = READY;
    task->round = KMT_INIT_ROUND;
    task->context = kcontext((Area){
        .start = task->stack,
        .end = task->stack + KMT_STACK_SIZE,
    }, entry, arg);
    for(int i = 0; i < KMT_FENCE_SIZE; ++i) {
        task->fence1[i] = KMT_FENCE;
        task->fence2[i] = KMT_FENCE;
    }


    kmt_spin_lock(&tasks_lock);
    list_insert(current_tasks[cpu_current()], task);
    kmt_spin_unlock(&tasks_lock);

    return 0;
}

进程初始化

这里稍微复杂一点，因为要基于上面的逻辑，分别实现相关的机制。下面是需要解决的几个问题

schedule_task指针不能为空，也就是我们需要一个调度上下文，并且不同于任何的进程的栈。
currrent_task指针不能为空，也就是我们需要自举每一个cpu的第一个进程

这里采用了一个非常巧妙的方法，同时优雅的解决了这些问题。

即给current_task指针赋值一个idle进程，作为自举的初始进程，但是将其状态设置为WAIT_TO_LOAD，也就是前面刚刚从调度进程返回的状态。

这里解释一下，每一个CPU在第一个进程创建之前，实际上已经有了相关的栈空间，则将其当做调度上下文是再好不过了。那么，从该调度上下文切换到真正的第一个进程，就相当于一次进程调度。
那么，我们只需要将当前的状态，伪造成刚刚完成一次调度，即可同时解决上述两个问题，并且非常优雅。

且思路如下所示
进程初始化

这里实现的相关代码如下所示

//kernel/src/kmt.c
/*
 * 需要自举每一个CPU第一个进程
 *
 * 也就是将当前正在运行的执行流，手动设置task结构体参数，作为第一个进程
 * 即需要设置好task结构体的相关字段，同样需要设置好链接关系
 * 
 * 
 * 除此之外，初始化还需要完成锁的初始化以及其他数组的初始化
 */
/*
 * 为了自举每个cpu的第一个进程
 * 将idle_entry当做其要执行的初始化函数
 */
static void
idle_entry(void *arg)
{
    while(1) {;}
    panic("error return");
}


static void
kmt_init(void)
{
    //初始化进程链表的锁
    kmt_spin_init(&tasks_lock, "tasks_lock");

    current_tasks = (task_t**)pmm->alloc(sizeof(task_t*) * cpu_count());
    panic_on(current_tasks == NULL, "not enough space");

    schedule_contexts = (Context**)pmm->alloc(sizeof(Context*) * cpu_count());
    panic_on(schedule_contexts == NULL, "not enough space");

    /*
     * 初始化cpu的第一个进程，也是IDLE进程
     */
    for(int cpu = 0; cpu < cpu_count(); ++cpu) {
        task_t *task = (task_t*)pmm->alloc(sizeof(task_t));
        panic_on(task == NULL, "not enough space");

        char *name = (char*)pmm->alloc(strlen("idle") + 3);
        sprintf(name, "idle%d", cpu);

        task->name = name;
        task->status = WAIT_TO_LOAD;
        task->round = KMT_INIT_ROUND;
        task->context = kcontext((Area){
            .start = task->stack,
            .end = task->stack + KMT_STACK_SIZE,
        }, idle_entry, NULL);
        task->fd = task->bk = task;
        for(int i = 0; i < KMT_FENCE_SIZE; ++i) {
            task->fence1[i] = task->fence2[i] = KMT_FENCE;
        }
        current_tasks[cpu] = task;

        printf("currents_task[%d]: %X\n", cpu, (uint64_t)(uintptr_t)task);
    }


    //初始化链表关系，也就是插入链表
    for(int cpu = 1; cpu < cpu_count(); ++cpu) {
        kmt_spin_lock(&tasks_lock);
        list_insert(current_tasks[0], current_tasks[cpu]);
        kmt_spin_unlock(&tasks_lock);
    }


    os->on_irq(sizeof(int) == 4 ? INT32_MIN : INT64_MIN, EVENT_NULL, save_context);
    os->on_irq(sizeof(int) == 4 ? INT32_MAX : INT64_MAX, EVENT_NULL, load_context);
    os->on_irq(TIME, EVENT_IRQ_TIMER, irq_time_handle);
    os->on_irq(YIELD, EVENT_YIELD, irq_yield_handle);

    printf("kmt_init\n");
}


//kernel/src/os.c
  static void os_run() {
    kmt_schedule();
  }

信号量

对于信号量来说，当期申请的资源不够时，则将其插入到该信号量的等待队列中，并且将其状态设置为不可调度，然后主动触发yield中断切换即可
而如果有进程释放了资源，岂会将该信号量中的等待队列队首进程唤醒即可，也就是从队列中摘下来，并且将其状态设置为可调度

这里需要提醒的是，还是需要特别小心栈数据竞争。因为如果将其设置为不可调度，然后触发yield后，并且还没进入到调度上下文时，中断处理程序和被中断程序又处于同一个栈空间中。
如果此时有进程释放了资源，从而直接更改了前面等待进程的状态为可调度，则可能导致前面分析过的数据竞争

因此，解决的方法和思路和前面是一样的。确保当中断程序进入到调度上下文时，才可以更改等待进程的状态为可调度

其实现代码如下所示

//kernel/include/common.h
    //信号量锁结构
    struct semaphore {
      /*
       * 这里实际上是task_t类型指针
       * 但是为了统一操作，因此类型仍然是sem_t
       */
      sem_t *fd, *bk;

      spinlock_t lock;
      int value;
    };

//kernel/src/kmt.c
/*
 * 如果当前缺乏资源，则更改进程的状态，然后插入到等待队列中，方便再次更改状态
 * 
 * 然后如果有进程释放资源，则再次更改状态即可
 */
void
kmt_sem_init(sem_t *sem, const char *name, int value)
{
    panic_on(sem == NULL, "error sem");

    kmt_spin_init(&(sem->lock), name);
    sem->value = value;
    sem->fd = sem->bk = sem;
}



/*
 * 执行wait操作时
 *
 * 如果资源不足的时候，将其设置为WAIT_TO_AWAKE即可，然后插入到等待队列中
 * 然后调用yield即可。如果其从yield返回，则说明有进程唤醒了，此时必定有可用资源 
 * 插入队列的fd方向
 */
static void
kmt_sem_wait(sem_t *sem)
{
    panic_on(sem == NULL, "error sem");
    kmt_spin_lock(&(sem->lock));
    if(--sem->value >= 0) { kmt_spin_unlock(&(sem->lock));}
    else {
        task_t *task = current_tasks[cpu_current()]; 

        kmt_spin_lock(&tasks_lock);
        task->status = WAIT_TO_AWAKE_AND_SCHEDULE;
        kmt_spin_unlock(&tasks_lock);

        //插入等待队列中，插入fd方向
        panic_on(sem->fd->bk != sem, "sem list is corrupted"); 
        sem_t *fake_sem = (sem_t*)field2address(task_t, fake_sem_fd, task), *bck = sem, *fwd = sem->fd;

        fake_sem->fd = fwd;
        fake_sem->bk = bck;
        fwd->bk = bck->fd = fake_sem;

        kmt_spin_unlock(&(sem->lock));
        yield();
    }
}


/*
 * 执行signal操作时
 * 从队列中释放的时候，沿着bk的方向进行释放即可 
 */
static void
kmt_sem_signal(sem_t *sem)
{
    panic_on(sem == NULL, "error sem");

    kmt_spin_lock(&(sem->lock));
    //sem->value如果是负值，表明此时等待的进程个数
    if(sem->value++ < 0) {
        panic_on(sem->bk == sem, "sem list is corrupted");
        sem_t *fake_sem = sem->bk, *bck = fake_sem->bk, *fwd = sem;
        bck->fd = fwd;
        fwd->bk = bck;
        kmt_spin_unlock(&(sem->lock));

        task_t *task = field2container(task_t, fake_sem_fd, fake_sem);
        while(true) {

            /*
             * 等到被更改为WAIT_TO_AWAKE后，再唤醒
             * 避免阻塞进程在完成第一部分的调用时，发生数据竞争
             */
            kmt_spin_lock(&tasks_lock);
            if(task->status == WAIT_TO_AWAKE) {
                task->status = READY;
                kmt_spin_unlock(&tasks_lock);
                break;
            }

            panic_on(task->status != WAIT_TO_AWAKE_AND_SCHEDULE, "error status");
            kmt_spin_unlock(&tasks_lock);

            /*
             * 这里不要调用yield
             *
             * 一方面，被阻塞进程从WAIT_TO_AWAKE状态转换到WAIT_TO_AWAKE，时间很短，没有必要
             * 
             * 另一方面，kmt_sem_signal可能在中断处理程序中调用。这样子相当于在中断处理程序中触发中断
             * 而在中断处理程序中触发中断，相当于连续保存两次context指针，则第一次的会被覆盖掉，从而导致严重的问题
             */
        }
    }else {kmt_spin_unlock(&(sem->lock));}
}

实验结果

这里执行如下命令，测试实验指南中给出的测试样例

1	make test=kmt run

最终结果如下图所示
实验结果