课程网址：https://pdos.csail.mit.edu/6.S081/2020/index.html

我的lab实现的github repo：https://github.com/tommyfan34/MIT_6S081

Lecture 1 Introduction

操作系统应该提供的功能：1. 多进程支持 2. 进程间隔离 3. 受控制的进程间通信

• xv6：一种在本课程中使用的类UNIX的教学操作系统，运行在RISC-V指令集处理器上，本课程中将使用QEMU模拟器代替

• kernel(内核)：为运行的程序提供服务的一种特殊程序。每个运行着的程序叫做进程，每个进程的内存中存储指令、数据和堆栈。一个计算机可以拥有多个进程，但是只能有一个内核

  每当进程需要调用内核时，它会触发一个system call（系统调用），system call进入内核执行相应的服务然后返回。

  

• shell：一个普通的程序，其功能是让用户输入命令并执行它们，shell不是内核的一部分

1.1 Processes and memory

每个进程拥有自己的用户空间内存以及内核空间状态，当进程不再执行时xv6将存储和这些进程相关的CPU寄存器直到下一次运行这些进程。kernel将每一个进程用一个PID(process identifier)指代。

常用syscall

• fork：形式：int fork()。其作用是让一个进程生成另外一个和这个进程的内存内容相同的子进程。在父进程中，fork的返回值是这个子进程的PID，在子进程中，返回值是0

• exit：形式：int exit(int status)。让调用它的进程停止执行并且将内存等占用的资源全部释放。需要一个整数形式的状态参数，0代表以正常状态退出，1代表以非正常状态退出

• wait：形式：int wait(int *status)。等待子进程退出，返回子进程PID，子进程的退出状态存储到int *status这个地址中。如果调用者没有子进程，wait将返回-1

  int pid = fork();
  if (pid > 0) {
      printf("parent: child=%d\n", pid);
      pid = wait((int *) 0);
      printf("child %d is done\n", pid);
  } else if (pid == 0) {
      printf("child: exiting\n");
      exit(0);
  } else {
      printf("fork error\n");
  }
  

  前两行输出可能是

  parent: child=1234
  child: exiting
  

  也可能是

  child: exiting
  parent: child=1234
  

  这是因为在fork了之后，父进程和子进程将同时开始判断PID的值，在父进程中，PID为1234，而在子进程中，PID为0。看哪个进程先判断好PID的值，以上输出顺序才会被决定。

  最后一行输出为

  parent: child 1234 is done
  

  子进程在判断完pid == 0之后将exit，父进程发现子进程exit之后，wait执行完毕，打印输出

  尽管fork了之后子进程和父进程有相同的内存内容，但是内存地址和寄存器是不一样的，也就是说在一个进程中改变变量并不会影响另一个进程。

• exec：形式：int exec(char *file, char *argv[])。加载一个文件，获取执行它的参数，执行。如果执行错误返回-1，执行成功则不会返回，而是开始从文件入口位置开始执行命令。文件必须是ELF格式。

  xv6 shell使用以上四个system call来为用户执行程序。在shell进程的main中主循环先通过getcmd来从用户获取命令，然后调用fork来运行一个和当前shell进程完全相同的子进程。父进程调用wait等待子进程exec执行完（在runcmd中调用exec）

  /* sh.c */
  int
  main(void)
  {
    static char buf[100];
    int fd;
  
    // Ensure that three file descriptors are open.
    while((fd = open("console", O_RDWR)) >= 0){
      if(fd >= 3){
        close(fd);
        break;
      }
    }
  
    // Read and run input commands.
    while(getcmd(buf, sizeof(buf)) >= 0){
      if(buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' '){
        // Chdir must be called by the parent, not the child.
        buf[strlen(buf)-1] = 0;  // chop \n
        if(chdir(buf+3) < 0)
          fprintf(2, "cannot cd %s\n", buf+3);
        continue;
      }
      if(fork1() == 0)
        runcmd(parsecmd(buf));
      wait(0);
    }
    exit(0);
  }
  

1.2 I/O and File descriptors

• file descriptor：文件描述符，用来表示一个被内核管理的、可以被进程读/写的对象的一个整数，表现形式类似于字节流，通过打开文件、目录、设备等方式获得。一个文件被打开得越早，文件描述符就越小。

  每个进程都拥有自己独立的文件描述符列表，其中0是标准输入，1是标准输出，2是标准错误。shell将保证总是有3个文件描述符是可用的

  while((fd = open("console", O_RDWR)) >= 0){
      if(fd >= 3){
          close(fd);
          break;
      }
  }
  

• read和write：形式int write(int fd, char *buf, int n)和int read(int fd, char *bf, int n)。从/向文件描述符fd读/写n字节bf的内容，返回值是成功读取/写入的字节数。每个文件描述符有一个offset，read会从这个offset开始读取内容，读完n个字节之后将这个offset后移n个字节，下一个read将从新的offset开始读取字节。write也有类似的offset

  /* essence of cat program */
  char buf[512];
  int n;
  
  for (;;) {
      n = read(0, buf, sizeof buf);
      if (n == 0)
          break;
      if (n < 0){
          fprintf(2, "read errot\n");
          exit(1);
      }
      if (write(1, buf, n) != n){
          fprintf(2, "write error\n");
          exit(1);
      }
  }
  

• close。形式是int close(int fd)，将打开的文件fd释放，使该文件描述符可以被后面的open、pipe等其他system call使用。

  使用close来修改file descriptor table能够实现I/O重定向

  /* implementation of I/O redirection,
   * more specifically, cat < input.txt
   */
  char *argv[2];
  argv[0] = "cat";
  argv[1] = 0;
  
  if (fork() == 0) {
      // in the child process
      close(0);  // this step is to release the stdin file descriptor
      open("input.txt", O_RDONLY); // the newly allocated fd for input.txt is 0, since the previous fd 0 is released
      exec("cat", argv); // execute the cat program, by default takes in the fd 0 as input, which is input.txt
  }
  

  父进程的fd table将不会被子进程fd table的变化影响，但是文件中的offset将被共享。

• dup。形式是int dup(int fd)，复制一个新的fd指向的I/O对象，返回这个新fd值，两个I/O对象(文件)的offset相同

  e.g.

  fd = dup(1);
  write(1, "hello ", 6);
  write(fd, "world\n", 6);
  // outputs hello world
  

  除了dup和fork之外，其他方式不能使两个I/O对象的offset相同，比如同时open相同的文件

1.3 Pipes

• pipe：管道，暴露给进程的一对文件描述符，一个文件描述符用来读，另一个文件描述符用来写，将数据从管道的一端写入，将使其能够被从管道的另一端读出

  pipe是一个system call，形式为int pipe(int p[])，p[0]为读取的文件描述符，p[1]为写入的文件描述符

  /* run the program wc with stdin connected to the read end of pipe, parent process able to communicate with child process */
  int p[2];
  char *argv[2];
  
  argv[0] = "wc";
  argv[1] = 0;
  
  pipe(p); // read fd put into p[0], write fd put into p[1]
  if (fork() == 0) {
      close(0);
      dup(p[0]); // make the fd 0 refer to the read end of pipe
      close(p[0]); // original read end of pipe is closed
      close(p[1]); // fd p[1] is closed in child process, but not closed in the parent process. 注意这里关闭p[1]非常重要，因为如果不关闭p[1]，管道的读取端会一直等待读取，wc就永远也无法等到EOF
      exec("/bin/wc", argv); // by default wc will take fd 0 as the input, which is the read end of pipe in this case
  } else {
      close(p[0]); // close the read end of pipe in parent process will not affect child process
      write(p[1], "hello world\n", 12); 
      close(p[1]); // write end of pipe closed, the pipe shuts down
  }
  

  xv6中的实现和上述的类似

  case PIPE:
  pcmd = (struct pipecmd*)cmd;
  if(pipe(p) < 0)
      panic("pipe");
  if(fork1() == 0){
      // in child process
      close(1); // close stdout
      dup(p[1]); // make the fd 1 as the write end of pipe
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->left); // run command in the left side of pipe |, output redirected to the write end of pipe
  }
  if(fork1() == 0){
      // in child process
      close(0); // close stdin
      dup(p[0]); // make the fd 0 as the read end of pipe
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->right); //  run command in the right side of pipe |, input redirected to the read end of pipe
  }
  close(p[0]);
  close(p[1]);
  wait(0); // wait for child process to finish
  wait(0); // wait for child process to finish
  break;
  

1.4 File system

xv6文件系统包含了文件(byte arrays)和目录(对其他文件和目录的引用)。目录生成了一个树，树从根目录/开始。对于不以/开头的路径，认为是是相对路径

• mknod：创建设备文件，一个设备文件有一个major device #和一个minor device #用来唯一确定这个设备。当一个进程打开了这个设备文件时，内核会将read和write的system call重新定向到设备上。

• 一个文件的名称和文件本身是不一样的，文件本身，也叫inode，可以有多个名字，也叫link，每个link包括了一个文件名和一个对inode的引用。一个inode存储了文件的元数据，包括该文件的类型(file, directory or device)、大小、文件在硬盘中的存储位置以及指向这个inode的link的个数

• fstat。一个system call，形式为int fstat(int fd, struct stat *st)，将inode中的相关信息存储到st中。

• link。一个system call，将创建一个指向同一个inode的文件名。unlink则是将一个文件名从文件系统中移除，只有当指向这个inode的文件名的数量为0时这个inode以及其存储的文件内容才会被从硬盘上移除

注意：Unix提供了许多在用户层面的程序来执行文件系统相关的操作，比如mkdir、ln、rm等，而不是将其放在shell或kernel内，这样可以使用户比较方便地在这些程序上进行扩展。但是cd是一个例外，它是在shell程序内构建的，因为它必须要改变这个calling shell本身指向的路径位置，如果是一个和shell平行的程序，那么它必须要调用一个子进程，在子进程里起一个新的shell，再进行cd，这是不符合常理的。

1.5 xv6环境构建

按照https://pdos.csail.mit.edu/6.828/2020/tools.html编译

注意需要follow other linux distributions的教程，因为直接使用ubuntu/debian的教程在调试的时候使用linux自带的gdb会无法远程连接到xv6，必须使用riscv64-unknown-elf-gdb，因此需要自己编译工具链。

debugging步骤：

可参考https://www.cnblogs.com/KatyuMarisaBlog/p/13727565.html

1. 在xv6文件夹下make qemu-gdb
2. 另外开一个终端，在相同的xv6文件夹下riscv64-unknown-elf-gdb。进入gdb后输入file user/_[execname]加载可执行文件
3. 通过b [linenum]设置断点 c继续
4. 在make qemu-gdb的终端中执行该可执行文件，进入debugging

可以输入tui enable来边debug边显示source code

可以输入layout asm显示汇编程序，输入layout reg显示寄存器

info breakpoints来显示关于断点的信息

也可以使用VSCode来进行debug，参考https://www.cnblogs.com/KatyuMarisaBlog/p/13727565.html

1.6 Lab 1: Unix Utilities

1. Sleep

   调用system call sleep来实现休眠一定时间，注意如果没有传入参数，程序需要打印错误信息

   #include "kernel/types.h"
   #include "user/user.h"
   
   int main(int argc, char *argv[]) {
   	if (argc == 1) {
   		fprintf(2, "ERROR: sleep time required\n");
   		exit(1);
   	}
   	sleep(atoi(argv[1])); // atoi把字符串转化为int
   	exit(0);
   }
   

2. pingpong

   Write a program that uses UNIX system calls to ‘‘ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “: received ping”, where is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “: received pong”, and exit. Your solution should be in the file user/pingpong.c.

   解决思路：开两个pipe，一个pipe负责子进程写父进程读，另一个pipe负责父进程写子进程读。注意最后要把所有的pipe fd关闭掉。

   #include "kernel/types.h"
   #include "user/user.h"
   
   #define READEND 0
   #define WRITEEND 1
   
   int
   main(int argc, char *argv[]){
   	int p1[2];
   	int p2[2];
   	int pid;
   	char buf[1];
   
   	pipe(p1);
   	pipe(p2);
   
   	pid = fork();
   
   	if (pid < 0)
   		exit(1);
   	else if (pid == 0) {
   	// child process
   		close(p1[WRITEEND]);
   		close(p2[READEND]);
   		read(p1[READEND], buf, 1);
   		printf("%d: received ping\n", getpid());
   		write(p2[WRITEEND], " ", 1);
   		close(p1[READEND]);
   		close(p2[WRITEEND]);
   		exit(0);
   	} else {
   	// parent process
   		close(p1[READEND]);
   		close(p2[WRITEEND]);
   		write(p1[WRITEEND], " ", 1);
   		read(p2[READEND], buf, 1);
   		printf("%d: received pong\n", getpid());
   		close(p1[WRITEEND]);
   		close(p2[READEND]);
   		exit(0);
   	}
   }
   

3. primes

   素数筛法：将一组数feed到一个进程里，先print出最小的一个数，这是一个素数，然后用其他剩下的数依次尝试整除这个素数，如果可以整除，则将其drop，不能整除则将其feed到下一个进程中，直到最后打印出所有的素数。

   

   注意最开始的父进程要等待所有子进程exit才能exit

   解决思路：采用递归，每次先尝试从左pipe中读取一个数，如果读不到说明已经到达终点，exit，否则再创建一个右pipe并fork一个子进程，将筛选后的数feed进这个右pipe。

   #include "kernel/types.h"
   #include "user/user.h"
   #define PRIME_NUM 35
   #define READEND 0
   #define WRITEEND 1
   
   void child(int* pl);
   
   int main(int argc, char *argv[]) {
   	int p[2];
   	pipe(p);
   	if (fork() == 0) {
   		child(p);	
   	} else {
   		close(p[READEND]);
   		// feed the int array
   		for (int i=2; i<PRIME_NUM+1; i++) {
   			write(p[WRITEEND], &i, sizeof(int));
   		}
   		close(p[WRITEEND]);
   		wait((int *) 0);
   	}
   	exit(0);
   }
   
   void child(int* pl) {
   	int pr[2];
   	int n;
   
   	close(pl[WRITEEND]);
   	// tries to read the first number
   	int read_result = read(pl[READEND], &n, sizeof(int));
   	if (read_result == 0)
   		exit(0);
   	// right side pipe
   	pipe(pr);
   
   	if (fork() == 0) {
   		child(pr);
   	} else {
   		close(pr[READEND]);
   		printf("prime %d\n", n);
   		int prime = n;
   		while (read(pl[READEND], &n, sizeof(int)) != 0) {
   			if (n%prime != 0) {
   				write(pr[WRITEEND], &n, sizeof(int));
   			}
   		}
   		close(pr[WRITEEND]);
   		wait((int *) 0);
   		exit(0);
   	}
   }
   

4. find

   要求用递归方式找到指定的文件夹下符合某个名字的文件，参考user/ls.c的实现方法

   #include "kernel/types.h"
   #include "user/user.h"
   #include "kernel/fs.h"
   #include "kernel/stat.h"
   #include "kernel/fcntl.h"
   
   void find(char *path, char *target_file);
   
   int main(int argc, char *argv[]) {
   	if (argc != 3) {
   		fprintf(2, "ERROR: You need pass in only 2 arguments\n");
   		exit(1);
   	}
   	char *target_path = argv[1];
   	char *target_file = argv[2];
   	find(target_path, target_file);
   	exit(0);
   }
   
   void find(char *path, char *target_file) {
   	int fd;
   	struct stat st;
   	struct dirent de;
   	char buf[512], *p;
   
   	if ((fd = open(path, 0)) < 0) {
   		fprintf(2, "ERROR: cannot open %s\n", path);
   		return;
   	}
   
   	if (fstat(fd, &st) < 0) {
   		fprintf(2, "ERROR: cannot stat %s\n", path);
   		close(fd);
   		return;
   	}
   
   	// read the name of each file/folder under the folder specified by fd, which is $path, name is de.name
   	while (read(fd, &de, sizeof(de)) == sizeof(de)) {
   		strcpy(buf, path);
   		p = buf+strlen(buf);
   		*p++ = '/';
   		if (de.inum == 0)
   			continue;
           // get the full path name of the current file/directory selected
   		memmove(p, de.name, DIRSIZ);
   		p[DIRSIZ] = 0;
   
   		if (stat(buf, &st) < 0) {
   			fprintf(2, "ERROR: cannot stat %s\n", buf);
   		}
   
   		switch (st.type) {
   		case T_FILE:
   			if (strcmp(target_file, de.name) == 0) {
   				printf("%s\n", buf);
   			}
   			break;
   		case T_DIR:
   			if ((strcmp(de.name, ".") != 0) && (strcmp(de.name, "..") != 0)) {
   				find(buf, target_file);
   }
   		}	
   	}
   	close(fd);
   	return;
   }
   

5. xargs

   实现将标准输入作为参数一起输入到xargs后面跟的命令中，比如

   $ echo hello too | xargs echo bye
   bye hello too
   

   如果标准输入有多行，那么也要执行多次命令

   使用fork起一个子进程，在子进程中用exec执行相应的命令。父进程wait。对标准输入每次读一个char，若读到\n需要执行命令。注意在执行xargs这个命令行的时候，最后肯定要按一个回车，这时标准输入最后会有一个回车，所以在EOF前是会有一个回车的！！！

   
   #include "kernel/types.h"
   #include "user/user.h"
   #include "kernel/param.h"
   #define MAX_LEN 100
   
   int main(int argc, char *argv[]) {
   	char *command = argv[1];
   	char bf;
   	char paramv[MAXARG][MAX_LEN]; // arguments
   	char *m[MAXARG];
   
   	while (1) {
   		int count = argc-1;  // # of current arguments
   		memset(paramv, 0, MAXARG * MAX_LEN);
   		// copy the parameter of command
   		for (int i=1; i<argc; i++) {
   			strcpy(paramv[i-1], argv[i]);
   		}
   
   		int cursor = 0; // cursor pointing the char position in single_arg
   		int flag = 0; // flag indicating whether thers is argument preceding space
   		int read_result;
   
   		while (((read_result = read(0, &bf, 1))) > 0 && bf != '\n') {
   			if (bf == ' ' && flag == 1) {
   				count++;
   				// reset flag and p
   				cursor = 0;
   				flag = 0;
   			}
   			else if (bf != ' ') {
   				paramv[count][cursor++] = bf;
   				flag = 1;
   			}
   		}
   		// encounters EOF of input or \n
   		if (read_result <= 0) {
   			break;
   		}
   		for (int i=0; i<MAXARG-1; i++) {
   			m[i] = paramv[i];
   		}
   		m[MAXARG-1] = 0;
   		if (fork() == 0) {
   			exec(command, m);
   			exit(0);
   		} else {
   			wait((int *) 0);
   		}
   	}
   	exit(0);
   }
   

Lecture 2 Operating System Organization

2.0 C pointer

补充资料： K&R《C Programming》

指针：a group of cells (bytes, often two or four) that can hold an address

指针的声明： int *p， 意思是*p是一个int

double *dp, atof(char *)意为声明一个dp，是指向double类型的指针，声明一个函数atof，需要一个指向char变量的指针作为参数，返回值类型为double

*ip += 1是将ip指向的变量加1，相当于++*ip或(*ip)++。注意：一元操作符从右向左结合，所以*ip++相当于*(ip++)

指针和数组名的区别：指针是变量，而数组名不是变量，因此pointer = arrayname是合法的，而arrayname = pointer或者arrayname++;是不合法的

指针的大小比较：只有在两个指针指向同一个数组的元素时比较才合法。指针只有相减是合法的

char*和char []的区别：前者是指针，并不会管到字符串，后者是数组，需要一个足够大的容量来容纳整个字符串

char amessage[] = "now is the time"; /* an array */
char *message = "now is the time"; /* a pointer, points to the string constant, could not modify the string content */

C程序的内存分配：

1. 堆(heap)：由程序员通过malloc()和free()使用和释放，如果忘记释放可能造成内存泄漏。地址从低到高增长
2. 栈(stack)：编译器自动分配释放，存放函数的参数值、局部变量的值等。在退出函数后自动释放销毁。地址从高到低增长
3. 全局区(static)：通过static声明，全局都可以访问，不会在函数退出后释放

2.1 User mode and supervisor mode

为了实现进程隔离，RISC-V CPU在硬件上提供3种执行命令的模式：machine mode, supervisor mode, user mode。

1. machine mode的权限最高，CPU以machine mode启动，machine mode的主要目的是为了配置电脑，之后立即切换到supervisor mode。

2. supervisor mode运行CPU执行privileged instructions，比如中断管理、对存储页表地址的寄存器进行读写操作、执行system call。运行在supervisor mode也称为在kernel space中运行。

3. 应用程序只能执行user mode指令，比如改变变量、执行util function。运行在user mode也称为在user space中运行。要想让CPU从user mode切换到supervisor mode，RISC-V提供了一个特殊的ecall指令，要想从supervisor mode切换到user mode，调用sret指令

2.2 Kernel organization

monolithic kernel：整个操作系统在kernel中，所有system call都在supervisor mode下运行。xv6是一个monolithic kernel

micro kernel：将需要运行在supervisor mode下的操作系统代码压到最小，保证kernel内系统的安全性，将大部分的操作系统代码执行在user mode下。

如2.1所示，文件系统是一个user-level的进程，为其他进程提供服务，因此也叫做server

xv6 kernel source file如下所示

2.3 Process

隔离的单元叫做进程，一个进程不能够破坏或者监听另外一个进程的内存、CPU、文件描述符，也不能破坏kernel本身。

为了实现进程隔离，xv6提供了一种机制让程序认为自己拥有一个独立的机器。一个进程为一个程序提供了一个私有的内存系统，或address space，其他的进程不能够读/写这个内存。xv6使用page table(页表)来给每个进程分配自己的address space，页表再将这些address space，也就是进程自己认为的虚拟地址(virtual address)映射到RISC-V实际操作的物理地址(physical address)

虚拟地址从0开始，往上依次是指令、全局变量、栈、堆。RISC-V上的指针是64位的，xv6使用低38位，因此最大的地址是$2^{38}-1$=0x3fffffffff=MAXVA

进程最重要的内核状态：1. 页表 p->pagetable 2. 内核堆栈p->kstack 3. 运行状态p->state，显示进程是否已经被分配、准备运行/正在运行/等待IO或退出

每个进程中都有线程(thread)，是执行进程命令的最小单元，可以被暂停和继续

每个进程有两个堆栈：用户堆栈(user stack)和内核堆栈(kernel stack)。当进程在user space中进行时只使用用户堆栈，当进程进入了内核(比如进行了system call)使用内核堆栈

2.4 Starting the first process

RISC-V启动时，先运行一个存储于ROM中的bootloader程序kernel.ld来加载xv6 kernel到内存中，然后在machine模式下从_entry开始运行xv6。bootloader将xv6 kernel加载到0x80000000的物理地址中，因为前面的地址中有I/O设备

在_entry中设置了一个初始stack，stack0来让xv6执行kernel/start.c。在start函数先在machine模式下做一些配置，然后通过RISC-V提供的mret指令切换到supervisor mode，使program counter切换到kernel/main.c

main先对一些设备和子系统进行初始化，然后调用kernel/proc.c中定义的userinit来创建第一个用户进程。这个进程执行了一个initcode.S的汇编程序，这个汇编程序调用了exec这个system call来执行/init，重新进入kernel。exec将当前进程的内存和寄存器替换为一个新的程序(/init)，当kernel执行完毕exec指定的程序后，回到/init进程。/init(user/init.c)创建了一个新的console device以文件描述符0,1,2打开，然后在console device中开启了一个shell进程，至此整个系统启动了

2.5 Lab 2: System calls

1. System call tracing

   要求：trace [tracing_mask] [command] 要求当调用了给定的tracing mask所对应的system call时，打印输出调用该system call的进程PID、system call的名称、system call的返回值。已经给出了user space下的user/trace.c，需要注册并实现trace这一system call

   在user/user.h中先注册trace这一user function：int trace(int)

   在user/usys.pl注册一个ecall到kernel的kernel态的trace的入口：entry("trace");

   在kernel/sys_trace.c中实现一个sys_trace()，将system call的传入参数，也就是tracing mask保存到kernel/proc.h中的proc结构体中新注册的int变量中，tracing mask的获取方式为argint(int, int *)

   // trace the sys call from the user space
   uint64
   sys_trace(void)
   {
     int n; // n is the tracing mask
   
     if(argint(0, &n) < 0)  // get the tracing mask
       return -1;
     myproc()->syscallnum = n;  // put the tracing mask into structure
     return 0;  
   }
   

   修改kernel/proc.c中的fork()来把trace mask从父进程复制到子进程

   np->syscallnum = p->syscallnum;
   

   修改kernel/syscall.c中的syscall()来打印输出，注意需要注册一个extern uint 64 sys_trace(void)和[SYS_ trace] sys_trace。注意sys call的返回值是保存在进程的trapframe中的a0寄存器的

   void
   syscall(void)
   {
     int num;
     struct proc *p = myproc();
     char* syscall_name[22] = {"fork", "exit", "wait", "pipe", "read", "kill", "exec", "fstat", "chdir", "dup", "getpid", "sbrk", "sleep", "uptime", "open", "write", "mknod", "unlink", "link", "mkdir", "close", "trace"};
   
     num = p->trapframe->a7;
     if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
       p->trapframe->a0 = syscalls[num]();
       if((1<<num)&(p->syscallnum))
         printf("%d: syscall %s -> %d\n", p->pid, syscall_name[num-1], p->trapframe->a0);
     } else {
       printf("%d %s: unknown sys call %d\n",
               p->pid, p->name, num);
       p->trapframe->a0 = -1;
     }
   }
   

2. Sysinfo

   要求：写一个sysinfo这个system call，需要获取当前空闲的内存大小填入struct sysinfo.freemem中，获取当前所有不是UNUSED的进程数量填入struct sysinfo.nproc中

   和前面一样先要在user/user.h中声明system callint sysinfo(struct sysinfo *)以及struct sysinfo，在user/usys.pl中注册entry，在kernel/syscall.h中注册一个syscall number，在kernel/sysproc.c中对uint64 sys_sysinfo(void)进行实现，注意要在sysproc.c中添加头文件sysinfo.h

   uint64
   sys_sysinfo(void)
   {
     uint64 sysinfop; // address of the sys info structure pointer
     struct sysinfo si;
   
     if(argaddr(0, &sysinfop) < 0)
       return -1;
     si.freemem = freememsize(); // collect the free memory size
     si.nproc = nproc_active(); // collect the number of processes not in use
     if(copyout(myproc()->pagetable, sysinfop, (char *)&si, sizeof(si)) < 0) // copy out the sysinfo struct si from kernel space to user space
       return -1;
     return 0;
   }
   

   在kernel/kalloc.c中实现freememsize()

   // get the size of free memory size
   uint64
   freememsize(void)
   {
     uint64 size = 0;
     struct run *r = kmem.freelist;
     uint64 i = 0;
     while(r){
       ++i;
       r = r->next;
     }
     size = i*PGSIZE;
     return size;
   }
   

   在kernel/proc.c中实现nproc_active()

   int
   nproc_active()
   {
     int i;
     int num = 0;
     for (i=0; i<NPROC; i++) {
       if (proc[i].state != UNUSED)
         num++;
     }
     return num;
   }
   

Lecture 3 Page Tables

页表让每个进程都拥有自己独立的虚拟内存地址，从而实现内存隔离。

3.1 Paging Hardware

xv6运行于Sv39 RISC-V，即在64位地址中只有最下面的39位被使用作为虚拟地址，其中底12位是页内偏移，高27位是页表索引，即4096字节($2^{12}$)作为一个page，一个进程的虚拟内存可以有 $2^{27}$个page，对应到页表中就是$2^{27}$个page table entry (PTE)。每个PTE有一个44位的physical page number (PPN)用来映射到物理地址上和10位flag，总共需要54位，也就是一个PTE需要8字节存储。即每个物理地址的高44位是页表中存储的PPN，低12位是页内偏移，一个物理地址总共由56位构成。

在实际中，页表并不是作为一个包含了$2^{27}$个PTE的大列表存储在物理内存中的，而是采用了三级树状的形式进行存储，这样可以让页表分散存储。每个页表就是一页。第一级页表是一个4096字节的页，包含了512个PTE（因为每个PTE需要8字节），每个PTE存储了下级页表的页物理地址，第二级列表由512个页构成，第三级列表由512*512个页构成。因为每个进程虚拟地址的高27位用来确定PTE，对应到3级页表就是最高的9位确定一级页表PTE的位置，中间9位确定二级页表PTE的位置，最低9位确定三级页表PTE的位置。如下图所示。第一级根页表的物理页地址存储在satp寄存器中，每个CPU拥有自己独立的satp

PTE flag可以告诉硬件这些相应的虚拟地址怎样被使用，比如PTE_V表明这个PTE是否存在，PTE_R、PTE_W、PTE_X控制这个页是否允许被读取、写入和执行，PTE_U控制user mode是否有权访问这个页，如果PTE_U=0，则只有supervisor mode有权访问这个页。

3.2 Kernel address space

每个进程有一个页表，用于描述进程的用户地址空间，还有一个内核地址空间（所有进程共享这一个描述内核地址空间的页表）。为了让内核使用物理内存和硬件资源，内核需要按照一定的规则排布内核地址空间，以能够确定哪个虚拟地址对应自己需要的硬件资源地址。用户地址空间不需要也不能够知道这个规则，因为用户空间不允许直接访问这些硬件资源。

QEMU会模拟一个从0x80000000开始的RAM，一直到0x86400000。QEMU会将设备接口以控制寄存器的形式暴露给内核，这些控制寄存器在0x80000000以下。kernel对这些设备接口控制寄存器的访问是直接和这些设备而不是RAM进行交互的。

左边和右边分别是kernel virtual address和physical address的映射关系。在虚拟地址和物理地址中，kernel都位于KERNBASE=0x80000000的位置，这叫做直接映射。

用户空间的地址分配在free memory中

有一些不是直接映射的内核虚拟地址：

• trampoline page（和user pagetable在同一个虚拟地址，以便在user space和kernel space之间跳转时切换进程仍然能够使用相同的映射，真实的物理地址位于kernel text中的trampoline.S）
• kernel stack page：每个进程有一个自己的内核栈kstack，每个kstack下面有一个没有被映射的guard page，guard page的作用是防止kstack溢出影响其他kstack。当进程运行在内核态时使用内核栈，运行在用户态时使用用户栈。注意：还有一个内核线程，这个线程只运行在内核态，不会使用其他进程的kstack，内核线程没有独立的地址空间。

3.3 Code: creating an address space

xv6中和页表相关的代码在kernel/vm.c中。最主要的结构体是pagetable_t，这是一个指向页表的指针。kvm开头的函数都是和kernel virtual address相关的，uvm开头的函数都是和user virtual address相关的，其他的函数可以用于这两者

几个比较重要的函数：

• walk：给定一个虚拟地址和一个页表，返回一个PTE指针

• mappages：给定一个页表、一个虚拟地址和物理地址，创建一个PTE以实现相应的映射

• kvminit用于创建kernel的页表，使用kvmmap来设置映射

• kvminithart将kernel的页表的物理地址写入CPU的寄存器satp中，然后CPU就可以用这个kernel页表来翻译地址了

• procinit(kernel/proc.c)为每一个进程分配(kalloc)kstack。KSTACK会为每个进程生成一个虚拟地址（同时也预留了guard pages)，kvmmap将这些虚拟地址对应的PTE映射到物理地址中，然后调用kvminithart来重新把kernel页表加载到satp中去。

每个RISC-V CPU会把PTE缓存到*Translation Look-aside Buffer (TLB)*中，当xv6更改了页表时，必须通知CPU来取消掉当前的TLB，取消当前TLB的函数是sfence.vma()，在kvminithart中被调用

3.4 Physical memory allocation for kernel

xv6对kernel space和PHYSTOP之间的物理空间在运行时进行分配，分配以页(4096 bytes)为单位。分配和释放是通过对空闲页链表进行追踪完成的，分配空间就是将一个页从链表中移除，释放空间就是将一页增加到链表中

kernel的物理空间的分配函数在kernel/kalloc.c中，每个页在链表中的元素是struct run，每个run存储在空闲页本身中。这个空闲页的链表freelist由spin lock保护，包装在struct kmem中。

• kinit()：对分配函数进行初始化，将kernel结尾到PHYSTOP之间的所有空闲空间都添加到kmem链表中，这是通过调用freerange(end, PHYSTOP)实现的
• freerange()对这个范围内所有页都调用一次kfree来将这个范围内的页添加到freelist链表中

3.5 User space memory

每个进程有自己的用户空间下的虚拟地址，这些虚拟地址由每个进程自己的页表维护，用户空间下的虚拟地址从0到MAXVA

当进程向xv6索要更多用户内存时，xv6先用kalloc来分配物理页，然后向这个进程的页表增加指向这个新的物理页的PTE，同时设置这些PTE的flag

图3.4是一个进程在刚刚被exec调用时的用户空间下的内存地址，stack只有一页，包含了exec调用的命令的参数从而使main(argc, argv)可以被执行。stack下方是一个guard page来检测stack溢出，一旦溢出将会产生一个page fault exception

sbrk是一个可以让进程增加或者缩小用户空间内存的system call。sbrk调用了growproc(kernel/proc.c)来改变p->sz从而改变heap中的program break，growproc调用了uvmalloc和uvmdealloc，前者调用了kalloc来分配物理内存并且通过mappages向用户页表添加PTE，后者调用了kfree来释放物理内存

3.6 Code: exec

exec是一个system call，为以ELF格式定义的文件系统中的可执行文件创建用户空间。

exec先检查头文件中是否有ELF_MAGIC来判断这个文件是否是一个ELF格式定义的二进制文件，用proc_pagetable来为当前进程创建一个还没有映射的页表，然后用uvmalloc来为每个ELF segment分配物理空间并在页表中建立映射，然后用loadseg来把ELF segment加载到物理空间当中。注意uvmalloc分配的物理内存空间可以比文件本身要大。

接下来exec分配user stack，它仅仅分配一页给stack，通过copyout将传入参数的string放在stack的顶端，在ustack的下方分配一个guard page

如果exec检测到错误，将跳转到bad标签，释放新创建的pagetable并返回-1。exec必须确定新的执行能够成功才会释放进程旧的页表(proc_freepagetable(oldpagetable, oldsz))，否则如果system call不成功，就无法向旧的页表返回-1

3.7 Real world

xv6将kernel加载到0x8000000这一RAM物理地址中，但是实际上很多RAM的物理地址都是随机的，并不一定存在0x8000000这个地址

实际的处理器并不一定以4096bytes为一页，而可能使用各种不同大小的页

3.8 Lab 3: pgtbl

1. print a page table

   实验要求：在程序刚刚启动(pid==1)时打印输出当前进程的pagetable。在exec.c中添加

   if(p->pid==1) vmprint(p->pagetable);
   

   vmprint()函数放在kernel/vm.c中

   void
   _helper_vmprint(pagetable_t pagetable, int level)
   {
     for(int i = 0; i < 512; i++){
       pte_t pte = pagetable[i];
       if ((pte & PTE_V) && (pte & (PTE_R | PTE_W | PTE_X)) == 0) {
         // this pte points to a valid lower level page table
         uint64 child = PTE2PA(pte);
         for (int j=0; j <= level; j++) {
           printf("..");
           if ((j+1) <= level) {
             printf(" ");
           }
         }
         printf("%d: pte %p pa %p\n", i, pte, child);
         _helper_vmprint((pagetable_t)child, level+1);
       }
       else if (pte & PTE_V) {
         uint64 child = PTE2PA(pte);
         // the lowest valid page table
         printf(".. .. ..%d: pte %p pa %p\n", i, pte, child);
       }
     }
   }
   
   // print the page table
   void vmprint(pagetable_t pagetable)
   {
     printf("page table %p\n", pagetable);
     _helper_vmprint(pagetable, 0);
   }
   

2. A kernel page table per process

   实验要求：为每个进程添加一个kernel pagetable来取代之前的global page table

   在kernel/proc.h中的struct proc添加一个每个进程的kernel pagetable

   pagetable_t kernelpt;        // per process kernel pagetable
   

   仿照kvminit，在vm.c中实现一个proc_kpt_init()函数来为每个进程初始化kernel page table，其中uvmmap类似于kvmmap，只不过kvmmap是直接对全局的kernel_pagetable进行mappage，而uvmmap并没有指定page table

   pagetable_t
   proc_kpt_init()
   {
     pagetable_t kpt;
     kpt = uvmcreate();
     if (kpt == 0) return 0;
     uvmmap(kpt, UART0, UART0, PGSIZE, PTE_R | PTE_W);
     uvmmap(kpt, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
     uvmmap(kpt, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
     uvmmap(kpt, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
     uvmmap(kpt, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
     uvmmap(kpt, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
     uvmmap(kpt, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
     return kpt;
   }
   void 
   uvmmap(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm)
   {
     if(mappages(pagetable, va, sz, pa, perm) != 0)
       panic("kvmmap");
   }
   

   在allocproc()中调用初始化进程内核页表的函数

   p->kernelpt = proc_kpt_init();
   

   注意要让每个procees kernel pagetable拥有这个进程的kernel stack，因此在allocproc中分配kstack并将其map到p->kernelpt上

   // Allocate a page for the process's kernel stack.
   // Map it high in memory, followed by an invalid
   // guard page.
   char *pa = kalloc();
   if(pa == 0)
       panic("kalloc");
   uint64 va = KSTACK((int) (p - proc));
   uvmmap(p->kernelpt, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
   p->kstack = va;
   

   修改scheduler()以将进程的kernel page table加载到satp寄存器中，如果CPU空闲，就使用global kernel page table

           w_satp(MAKE_SATP(p->kernelpt));
           sfence_vma();
   
           swtch(&c->context, &p->context);
   
           // Process is done running for now.
           // It should have changed its p->state before coming back.
           c->proc = 0;
   
         	w_satp(MAKE_SATP(kernel_pagetable));
         	sfence_vma();
           found = 1;
         }
   

   在freeproc中释放掉process kernel page table，注意对于KERNBASE以下的部分，这个process kernel page table只能unmap这些PTE，而不能真的释放这些物理资源，因为KERNBASE以下的部分其他进程是共享的，因此要先释放掉进程的kstack物理资源，然后用freewalk_kproc这个函数将pagetable unmap和释放的同时也保留叶节点指向的物理资源

   // free the kernel stack in the RAM
   if (p->kstack)
   {
       pte_t* pte = walk(p->kernelpt, p->kstack, 0);
       if (pte == 0)
           panic("freeproc: walk");
       kfree((void*)PTE2PA(*pte));
   }
   p->kstack = 0;
   
   // ...
   if (p->kernelpt)
       freewalk_kproc(p->kernelpt);
   // ...
   
   // Recursively free page-table pages
   // but retain leaf physical addresses
   void
   freewalk_kproc(pagetable_t pagetable) {
     for(int i = 0; i < 512; i++){
       pte_t pte = pagetable[i];
       if((pte & PTE_V)){
         pagetable[i] = 0;
         if ((pte & (PTE_R|PTE_W|PTE_X)) == 0)
         {
           uint64 child = PTE2PA(pte);
           freewalk_kproc((pagetable_t)child);
         }
       }
     }
     kfree((void*)pagetable);
   }
   

3. Simplify copyin/copyinstr

   实验要求：将每个进程的user page table复制到进程kernel page table上，从而让每个进程在copyin的时候不需要再利用process user page table来翻译传入的参数指针，而可以直接利用process kernel page table来dereference

   先实现一个复制page table的函数u2kvmcopy来将user page table复制到process kernel page table，注意在复制的过程中需要清除原先PTE中的PTE_U标志位，否则kernel无法访问

   // copy the user page table to kernel page table
   void
   u2kvmcopy(pagetable_t pagetable, pagetable_t kpagetable, uint64 oldsz, uint64 newsz)
   {
     pte_t *pte_from, *pte_to;
     uint64 a, pa;
     uint flags;
   
     if (newsz < oldsz)
       return;
     oldsz = PGROUNDUP(oldsz);
     for (a = oldsz; a < newsz; a += PGSIZE)
     {
       if ((pte_from = walk(pagetable, a, 0)) == 0)
         panic("u2kvmcopy: pte should exist");
       if ((pte_to = walk(kpagetable, a, 1)) == 0)  // copy the pte to the same address at kernel page table
         panic("u2kvmcopy: walk fails");
       pa = PTE2PA(*pte_from);
       flags = (PTE_FLAGS(*pte_from) & (~PTE_U));
       *pte_to = PA2PTE(pa) | flags;
     }
   }
   

   在每个改变了user page table的地方要调用u2kvmcopy()使得process kernel page table跟上这个变化。这些地方出现在fork()、exec()和sbrk()需要调用的growproc()。注意要防止user process过大导致virtual address超过PLIC

   // fork
   // increment reference counts on open file descriptors.
   for(i = 0; i < NOFILE; i++)
       if(p->ofile[i])
           np->ofile[i] = filedup(p->ofile[i]);
   np->cwd = idup(p->cwd);
   
   u2kvmcopy(np->pagetable, np->kernelpt, 0, np->sz);
   
   safestrcpy(np->name, p->name, sizeof(p->name));
   
   // exec
   // call u2kvmvcopy after user stack is set up
   stackbase = sp - PGSIZE;
   
   u2kvmcopy(pagetable, p->kernelpt, 0, sz);
   // Push argument strings, prepare rest of stack in ustack.
   for(argc = 0; argv[argc]; argc++) {
   
   // growproc
   int
   growproc(int n)
   {
     uint sz;
     struct proc *p = myproc();
   
     sz = p->sz;
   
     if(n > 0){
       //   return -1;
       if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
         return -1;
       }
       u2kvmcopy(p->pagetable, p->kernelpt, sz-n, sz);
     } else if(n < 0){
       sz = uvmdealloc(p->pagetable, sz, sz + n);
     }
     p->sz = sz;
     return 0;
   }
   
   // prevent virtual address exceeding PLIC
   // in exec.c when loading the program
   uint64 sz1;
   if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz)) == 0)
       goto bad;
   if(sz1 >= PLIC)
       goto bad;
   sz = sz1;
   

   在userinit中复制process kernel page

   uvminit(p->pagetable, initcode, sizeof(initcode));
   p->sz = PGSIZE;
   u2kvmcopy(p->pagetable, p->kernelpt, 0, p->sz);
   // prepare for the very first "return" from kernel to user.
   p->trapframe->epc = 0;      // user program counter
   

   最后将copyin()和copyinstr()替换为copyin_new()和copyinstr_new()

Lecture 4 RISC-V calling convention

4.1 ISA & Assembly Language

ISA: Instruction Set

C -> Assembly(.S/.asm) -> binary (object.o)

汇编语言没有明确的workflow，只是一行行指令

汇编语言是基于寄存器进行操作的，而不是基于内存操作

RISC-V vs x86：

• RISC-V：精简指令集，指令更少，更加简单，唯一开源的ISA。ARM也是RISC(Reduced Instruction Set Chip)
• x86：复杂指令集，指令很多并且可以实现复杂功能

RISC-V assembly常用指令:

https://web.eecs.utk.edu/~smarz1/courses/ece356/notes/assembly/

• ld/lb/lw rd, 8(rs)：将*(rs+8)的值写入到rd寄存器，lb=load byte, ld=load double word, lw=load word
• sd/sb/sw rd, 8(rs)：将*(rd)`的值写入到rs+8地址上
• add rd, rs1, rs2：*(rd) = *(rs1) + *(rs2)
• addi rd, rs1, int: *(rd) = *(rs1) + int

4.2 Calling convention

调用约定(calling convention)是规定子过程如何获取参数以及如何返回的方案，调用约定一般规定了

• 参数、返回值、返回地址等放置的位置（寄存器、栈或存储器）

  RISC-V寄存器通过寄存器而非栈来传递函数参数，a0-a7是int参数，fa0-fa7是float参数

• 如何将调用子过程的准备工作与恢复现场的工作划分到调用者(caller)与被调用者(callee)身上

小于一个指针字(RISCV64中是8字节，RISCV32是4字节)的参数传入时将参数放在寄存器的最低位，因为RISC-V是小端系统，当2个指针字的参数传入时，低位的1个指针字放在偶数寄存器，比如a0上，高位的1个指针字放在奇数寄存器，比如a1上。当高于2个指针字的参数传入时以引用的方式传入。struct参数没有传到寄存器的部分将以栈的方式传入，sp栈指针将指向第一个没有传入到寄存器的参数。

从函数返回的值，如果是整数将放在a0和a1中，如果是小数将放置在fa0和fa1寄存器中。对于更大的返回值，将放置在内存中，caller开辟这个内存，并且把指向这个内存的指针作为第一个参数传递给callee

由caller保存的寄存器不会在函数调用之间被保存，又名易失性寄存器，如果要在过程调用后恢复该值，则调用方有责任将这些寄存器压入堆栈或复制到其他位置，而callee保存的寄存器会被保存，称为非易失性寄存器，可以期望这些寄存器在被调用者返回后保持相同的值。比如函数A调用了函数B，所有函数A保存的寄存器在函数B被调用后可以被B重写覆盖

4.3 Stack

栈从高地址向低地址增长，每个大的box叫一个stack frame（栈帧），栈帧由函数调用来分配，每个栈帧大小不一定一样，但是栈帧的最高处一定是return address

sp是stack pointer，用于指向栈顶（低地址），保存在寄存器中

fp是frame pointer，用于指向当前帧底部（高地址），保存在寄存器中，同时每个函数栈帧中保存了调用当前函数的函数（父函数）的fp（保存在to prev frame那一栏中）

这些栈帧都是由编译器编译生成的汇编文件生成的

Lecture 5 Traps

5.0 trap

3种可能的情况使得CPU暂停对正常指令的执行：1. syscall，移交给kernel 2. exception，指令执行了非法操作 3. 设备中断。以上情况合并称为trap。

trap应该对于被打断的指令是透明的，也就是说被打断的指令不应该知道这个地方产生了trap，产生trap之后现场应该得以恢复并继续执行被打断的指令。

xv6对trap的处理分为四个阶段：1. RISC-V CPU的硬件的一些动作 2. 汇编文件为了kernel C文件进行的一些准备 3. 用C实现的trap handler 4. system call / device-driver service routine

通常对于user space的trap、kernel space的trap和计时器中断会有不同的trap handler

5.1 RISC-V trap machinery

RISC-V CPU有一系列的控制寄存器可以通知kernel发生了trap，也可以由kernel写入来告诉CPU怎样处理trap

• stvec：trap handler的地址，由kernel写入

• sepc：保存trap发生时的现场program counter，因为接下来pc要被取代为stvec。sret是从trap回到现场的指令，将sepc写回到pc

• scause：一个trap产生的原因代码，由CPU写入

• sscratch：放在trap handler的最开始处

• sstatus：控制设备中断是否被开启，如果sstatus中的SIE位被清除，则RISC-V将推迟设备中断。SPP位指示这个trap是在user space中产生的还是在kernel space产生的，并将控制sret回到什么模式

  以上寄存器只在supervisor模式下发生的trap被使用

当发生除了计时器中断以外的其他类型的trap时，RISC-V将执行以下步骤：

1. 如果trap是一个设备产生的中断，而SIE又被清除的情况下，不做下方的任何动作
2. 清除SIE来disable一切中断
3. 把pc复制到sepc
4. 把当前的模式(user / supervisor)保存到SPP
5. 设置scause寄存器来指示产生trap的原因
6. 将当前的模式设置为supervisor
7. 将stvec的值复制到pc
8. 开始执行pc指向的trap handler的代码

注意CPU并没有切换到kernel页表，也没有切换到kernel栈

5.2 Traps from user space

当user space中发生trap时，会将stvec的值复制到pc，而此时stvec的值是trampoline.S中的uservec，因此跳转到uservec，先保存一些现场的寄存器，恢复kernel栈指针、kernel page table到satp寄存器，再跳转到usertrap(kernel/trap.c)trap handler，然后返回usertrapret(kernel/trap.c)，跳回到kernel/trampoline.S，最后用userret(kernel/trampoline.S)通过sret跳回到user space

RISC-V在trap中不会改变页表，因此user page table必须有对uservec的mapping，uservec是stvec指向的trap vector instruction。uservec要切换satp到kernel页表，同时kernel页表中也要有和user页表中对uservec相同的映射。RISC-V将uservec保存在trampoline页中，并将TRAMPOLINE放在kernel页表和user页表的相同位置处（MAXVA)

当uservec开始时所有的32个寄存器都是trap前代码的值，但是uservec需要对某些寄存器进行修改来设置satp，可以用sscratch和a0的值进行交换，交换之前的sscratch中是指向user process的trapframe的地址，trapframe中预留了保存所有32个寄存器的空间。p->trapframe保存了每个进程的TRAPFRAME的物理空间从而让kernel页表也可以访问该进程的trapframe

当交换完a0和sscratch之后，uservec可以通过a0把所有当前寄存器的值保存到trapframe中。由于当前进程的trapframe已经保存了当前进程的kernel stack、当前CPU的hartid、usertrap的地址、kernel page table的地址等，uservec需要获取这些值，然后切换到kernel pagetable，调用usertrap

usertrap主要是判断trap产生的原因并进行处理，然后返回。因为当前已经在kernel里了，所以这时候如果再发生trap，应该交给kernelvec处理，因此要把stvec切换为kernelvec。如果trap是一个system call，那么syscall将被调用，如果是设备中断，调用devintr，否则就是一个exception，kernel将杀死这个出现错误的进程

回到user space的第一步是调用usertrapret()，这个函数将把stvec指向uservec，从而当回到user space再出现trap的时候可以跳转到uservec，同时设置p->trapframe的一些值为下一次trap作准备，比如设置p->trapframe->kernel_sp = p->kstack + PGSIZE。清除SPP为从而使得调用sret后能够回到user mode。设置回到user space后的program counter为p->trapframe->epc，最后调用跳转到TRAMPOLINE页上的userret回到trampoline.S，加载user page table。userret被userrapret调用返回时a0寄存器中保存了TRAPFRAME，因此可以通过这个TRAPFRAME地址来恢复之前所有寄存器的值(包括a0)，最后把TRAPFRAME保存在sscratch中，用sret回到user space

5.3 Calling system calls

user调用exec执行system call的过程：把给exec使用的参数放到a0和a1寄存器中，把system call的代码(SYS_exec)放到a7寄存器中，ecall指令将陷入内核中（通过usys.pl中的entry)。ecall的效果有三个，包括将CPU从user mode切换到supervisor mode、将pc保存到epc以供后续恢复、将uservec设置为stvec，并执行uservec、usertrap，然后执行syscall。kernel trap code将把寄存器的值保存在当前进程的trapframe中。syscall将把trapframe中的a7寄存器保存的值提取出来，索引到syscalls这个函数数列中查找对应的syscall种类，并进行调用，然后把返回值放置在p->trapframe->a0中，如果执行失败，就返回-1。

syscall的argument可以用argint、argaddr、argfd等函数从内存中取出

5.4 Traps from kernel space

当执行kernel code发生CPU trap的时候，stvec是指向kernelvec的汇编代码的。kernelvec将寄存器的值保存在被中断的kernel thread的栈里而不是trapframe里，这样当trap需要切换kernel thread时，再切回来之后还可以从原先的thread栈里找到之前的寄存器值。

保存完寄存器之后，跳转到kerneltrap这个trap handler。kerneltrap可以对设备中断和exception这两种trap进行处理。如果是设备中断，调用devintr进行处理，如果是exception就panic，如果是因为计时器中断，就调用yield让其他kernel thread运行

最后返回到kernelvec中，kernelvec将保存的寄存器值从堆栈中弹出，执行sret，将sepc复制到pc来执行之前被打断的kernel code

5.5 Lab 4: Traps

1. Backtrace

   实验要求：当调用sys_sleep时打印出函数调用关系的backtrace，即递归地打印每一个函数以及调用这个函数及其父函数的return address，比如

   backtrace:
   0x0000000080002cda
   0x0000000080002bb6
   0x0000000080002898
   

   gcc将当前执行的函数的frame pointer存储在s0寄存器中，可以在kernel/riscv.h中声明以下函数来获取s0

   static inline uint64
   r_fp()
   {
     uint64 x;
     asm volatile("mv %0, s0" : "=r" (x) );
     return x;
   }
   

   当前函数的return address位于fp-8的位置，previous frame pointer位于fp-16的位置。

   每个kernel stack都是一页，因此可以通过计算PGROUNDDOWN(fp)和PGROUNDUP(fp)来确定当前的fp地址是否还位于这一页内，从而可以是否已经完成了所有嵌套的函数调用的backtrace。

   在kernel/printf.c中

   void
   backtrace(void)
   {
     uint64 fp, ra, top, bottom;
     printf("backtrace:\n");
     fp = r_fp();  // frame pointer of currently executing function
     top = PGROUNDUP(fp);
     bottom = PGROUNDDOWN(fp);
     while (fp < top && fp > bottom)
     {
       ra = *(uint64 *)(fp-8);
       printf("%p\n", ra);
       fp = *(uint64 *)(fp-16); // saved previous frame pointer
     }
   }
   

2. Alarm

   实验要求：添加一个新的system callsigalarm(interval, handler)，interval是一个计时器的tick的间隔大小，handler是指向一个函数的指针，这个函数是当计时器tick到达interval时触发的函数。

   首先修改Makefile使得alarmtest.c能够被编译，在user/user.h中添加函数声明

   int sigalarm(int ticks, void (*handler)());
   int sigreturn(void);
   

   在user/user.pl、kernel/syscall.h、kernel/syscall.c等添加sys_sigalarm和sys_sigreturn这两个syscall的注册

   在kernel/proc.h的proc结构体中添加几个成员。int interval是保存的定时器触发的周期，void (*handler)()是指向handler函数的指针，这两个成员变量在sys_sigalarm中被保存。ticks用来记录从上一次定时器被触发之后到目前的ticks，in_handler用来记录当前是否在handler函数中，用来防止在handler函数的过程中定时被触发再次进入handler函数。下面的所有寄存器都是用来保护和恢复现场的。

     int interval;                // interval of alarm
     void (*handler)();           // pointer to the handler function
     int ticks;                   // how many ticks have passed since last call
     int in_handler;              // to prevent from reentering into handler when in handler
     uint64 saved_epc;
     uint64 saved_ra;
     uint64 saved_sp;
     uint64 saved_gp;
     uint64 saved_tp;
     uint64 saved_t0;
     uint64 saved_t1; 
     uint64 saved_t2;
     uint64 saved_s0;
     uint64 saved_s1;
     uint64 saved_s2;
     uint64 saved_s3;
     uint64 saved_s4;
     uint64 saved_s5;
     uint64 saved_s6;
     uint64 saved_s7;
     uint64 saved_s8;
     uint64 saved_s9;
     uint64 saved_s10;
     uint64 saved_s11;
     uint64 saved_a0;
     uint64 saved_a1;
     uint64 saved_a2;
     uint64 saved_a3;
     uint64 saved_a4;
     uint64 saved_a5;
     uint64 saved_a6;
     uint64 saved_a7;
     uint64 saved_t3;
     uint64 saved_t4;
     uint64 saved_t5;
     uint64 saved_t6;
   

   在kernel/sysfile.c中分别添加uint64 sys_sigreturn(void)和uint64 sys_sigalarm(void)的实现

   对于sys_sigalarm，需要将从userfunction传入的两个参数分别保存到p结构体相应的成员变量中

   uint64
   sys_sigalarm(void)
   {
     int ticks;
     uint64 funaddr; // pointer to function
     if ((argint(0, &ticks) < 0) || (argaddr(1, &funaddr) < 0)) {
       return -1;
     }
     struct proc *p = myproc();
     p->interval = ticks;
     p->handler = (void(*)())funaddr;
     return 0;
   }
   

   对于sys_sigreturn，这个函数会在handler函数完成之后被调用，它的主要工作是恢复现场的寄存器，并且将in_handler这个flag置0

   uint64
   sys_sigreturn(void)
   {
     struct proc *p = myproc();
     p->trapframe->epc = p->saved_epc;
     p->trapframe->ra = p->saved_ra;
     p->trapframe->sp = p->saved_sp;
     p->trapframe->gp = p->saved_gp;
     p->trapframe->tp = p->saved_tp;
     p->trapframe->t0 = p->saved_t0;
     p->trapframe->t1 = p->saved_t1;
     p->trapframe->t2 = p->saved_t2;
     p->trapframe->t3 = p->saved_t3;
     p->trapframe->t4 = p->saved_t4;
     p->trapframe->t5 = p->saved_t5;
     p->trapframe->t6 = p->saved_t6;
     p->trapframe->s0 = p->saved_s0;
     p->trapframe->s1 = p->saved_s1;
     p->trapframe->s2 = p->saved_s2;
     p->trapframe->s3 = p->saved_s3;
     p->trapframe->s4 = p->saved_s4;
     p->trapframe->s5 = p->saved_s5;
     p->trapframe->s6 = p->saved_s6;
     p->trapframe->s7 = p->saved_s7;
     p->trapframe->s8 = p->saved_s8;
     p->trapframe->s9 = p->saved_s9;
     p->trapframe->s10 = p->saved_s10;
     p->trapframe->s11 = p->saved_s11;
     p->trapframe->a0 = p->saved_a0;
     p->trapframe->a1 = p->saved_a1;
     p->trapframe->a2 = p->saved_a2;
     p->trapframe->a3 = p->saved_a3;
     p->trapframe->a4 = p->saved_a4;
     p->trapframe->a5 = p->saved_a5;
     p->trapframe->a6 = p->saved_a6;
     p->trapframe->a7 = p->saved_a7;
     p->in_handler = 0;
     return 0;
   }
   

   kernel/trap.c中的usertrap()是对陷入定时器中断的处理，需要判断which_dev==2才是定时器中断，当p->ticks到达预设值p->interval时，将调用p->handler，这是通过向p->trapframe->epc加载handler地址实现的，这样当从usertrap()中返回时，pc在恢复现场时会加载p->trapframe->epc，这样就会跳转到handler地址。在跳转到handler之前先要保存p->trapframe的寄存器，因为执行handler函数会导致这些寄存器被覆盖。

    syscall();
     } else if((which_dev = devintr()) != 0){
       // ok
       if (which_dev == 2 && p->in_handler == 0) {
         p->ticks += 1;
         if ((p->ticks == p->interval) && (p->interval != 0)) {
           p->in_handler = 1;
           p->ticks = 0;
           p->saved_epc = p->trapframe->epc;
           p->saved_ra = p->trapframe->ra;
           p->saved_sp = p->trapframe->sp;
           p->saved_gp = p->trapframe->gp;
           p->saved_tp = p->trapframe->tp;
           p->saved_t0 = p->trapframe->t0;
           p->saved_t1 = p->trapframe->t1;
           p->saved_t2 = p->trapframe->t2;
           p->saved_t3 = p->trapframe->t3;
           p->saved_t4 = p->trapframe->t4;
           p->saved_t5 = p->trapframe->t5;
           p->saved_t6 = p->trapframe->t6;
           p->saved_s0 = p->trapframe->s0;
           p->saved_s1 = p->trapframe->s1;
           p->saved_s2 = p->trapframe->s2;
           p->saved_s3 = p->trapframe->s3;
           p->saved_s4 = p->trapframe->s4;
           p->saved_s5 = p->trapframe->s5;
           p->saved_s6 = p->trapframe->s6;
           p->saved_s7 = p->trapframe->s7;
           p->saved_s8 = p->trapframe->s8;
           p->saved_s9 = p->trapframe->s9;
           p->saved_s10 = p->trapframe->s10;
           p->saved_s11 = p->trapframe->s11;
           p->saved_a0 = p->trapframe->a0;
           p->saved_a1 = p->trapframe->a1;
           p->saved_a2 = p->trapframe->a2;
           p->saved_a3 = p->trapframe->a3;
           p->saved_a4 = p->trapframe->a4;
           p->saved_a5 = p->trapframe->a5;
           p->saved_a6 = p->trapframe->a6;
           p->saved_a7 = p->trapframe->a7;
           p->trapframe->epc = (uint64)p->handler;
         }
       }
     } else {
   

Lecture 6 Page Faults

当试图访问PTE_V为0的虚拟地址或user访问PTE_U为0/kernel访问PTE_U为1以及其他违反PTE_W/PTE_R等flag的情况下会出现page faults。Page faults是一个exception，总共有3种page faults：

1. load page faults：当load instruction无法翻译虚拟地址时发生
2. store page faults：当store instruction无法翻译虚拟地址时发生
3. instruction page faults：当一个instruction的地址无法翻译时发生

page faults种类的代码存放在scause寄存器中，无法翻译的地址存放在stval寄存器中。

在xv6中对于exception一律都会将这个进程kill掉，但是实际上可以结合page faults实现一些功能。

1. 可以实现copy-on-write fork。在fork时，一般都是将父进程的所有user memory复制到子进程中，但是fork之后一般会直接进行exec，这就会导致复制过来的user memory又被放弃掉。因此改进的思路是：子进程和父进程共享一个物理内存，但是mapping时将PTE_W置零，只有当子进程或者父进程的其中一个进程需要向这个地址写入时产生page fault，此时才会进行copy
2. 可以实现lazy allocation。旧的sbrk()申请分配内存，但是申请的这些内存进程很可能不会全部用到，因此改进方案为：当进程调用sbrk()时，将修改p->sz，但是并不实际分配内存，并且将PTE_V置0。当在试图访问这些新的地址时发生page fault再进行物理内存的分配
3. paging from disk：当内存没有足够的物理空间时，可以先将数据存储在其他的存储介质（比如硬盘）上，，将该地址的PTE设置为invalid，使其成为一个evicted page。当需要读或者写这个PTE时，产生Page fault，然后在内存上分配一个物理地址，将这个硬盘上的evicted page的内容写入到该内存上，设置PTE为valid并且引用到这个内存物理地址

6.1 Lab 5: lazy allocation

1. 实验要求：在sbrk()时只增长进程的myproc()->sz而不实际分配内存。在kernel/trap.c中修改从而在产生page fault时分配物理内存给相应的虚拟地址。相应的虚拟地址可以通过r_stval()获得。r_scause()为13或15表明trap的原因是page fault

   kernel/sysproc.c中修改sys_sbrk()

   uint64
   sys_sbrk(void)
   {
     int addr;
     int n;
     if(argint(0, &n) < 0)
       return -1;
     addr = myproc()->sz;
     myproc()->sz += n;
     // if(growproc(n) < 0)
     //   return -1;
     return addr;
   }
   

   kernel/trap.c中，在usertrap()函数中

    } else if((which_dev = devintr()) != 0){
       // ok
     } else {
       if (r_scause() == 13 || r_scause() == 15) {
         // page fault
         uint64 va = r_stval();
         char *mem;
         va = PGROUNDDOWN(va);
         if ((mem = kalloc()) == 0) {
   		panic("cannot allocate for lazy alloc\n");
           exit(-1);
         } 
         if (mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
           kfree(mem);
   		panic("cannot map for lazy alloc\n");
   		exit(-1);
         }
       }
       else {
         printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
         printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
         p->killed = 1;
       }
     }
   

   修改kernel/vm.c中的uvmunmap，因为lazy allocation可能会造成myproc()-sz以下的内容没有被分配的情况，因此在unmap的过程中可能会出现panic，这是正常情况，需要continue

   if((pte = walk(pagetable, a, 0)) == 0)
       continue;
   // panic("uvmunmap: walk");
   if((*pte & PTE_V) == 0)
       continue;	    
   // panic("uvmunmap: not mapped");
   if(PTE_FLAGS(*pte) == PTE_V)
       panic("uvmunmap: not a leaf");
   if(do_free){
   

2. 实验要求： 在第一部分的基础上，要求处理

• sbrk()的参数为负的情况，deallocate即可

  if (n < 0) {
      // deallocate the memory
      if ((myproc()->sz + n) < 0) {
          return -1;
      } else {
          if (uvmdealloc(myproc()->pagetable, addr, addr+n) != (addr+n)) {
              return -1;
          }
      }
  }
  

• fork()中将父进程的内存复制给子进程的过程中用到了uvmcopy，uvmcopy原本在发现缺失相应的PTE等情况下会panic，这里也要continue掉。在kernel/proc.c的uvmcopy中

  if((pte = walk(old, i, 0)) == 0)
      continue;
  // panic("uvmcopy: pte should exist");
  if((*pte & PTE_V) == 0)
      continue;
  // panic("uvmcopy: page not present");
  

• 当造成的page fault在进程的user stack以下（栈底）或者在p->sz以上（堆顶）时，kill这个进程。在kernel/trap.c的usertrap中增加以下判断条件

  if ((va < p->sz) && (va > PGROUNDDOWN(p->trapframe->sp)))
  

• 在exec中，loadseg调用了walkaddr，可能会找不到相应虚拟地址的PTE，此时需要分配物理地址。在kernel/vm.c中

  if((pte == 0) || ((*pte & PTE_V) == 0)) {
      if (va > myproc()->sz || va < PGROUNDDOWN(myproc()->trapframe->sp)) {
          return 0;
      } 
      if ((mem = (uint64)kalloc()) == 0) return 0;
      va = PGROUNDDOWN(va);
      if (mappages(myproc()->pagetable, va, PGSIZE, mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
          kfree((void*)mem);
          return 0;
      }
      return mem;
  }
  

Lecture 7 Interrupts

设备会产生中断，xv6处理设备中断的代码位于kernel/trap.c中的devintr。

进程的内核态中执行top half，中断时间中执行bottom half。top half是通过read或write这样的system call来进行调用的，从而能让这个设备执行I/O操作。当设备执行完I/O操作之后，将产生一个设备中断，这个设备驱动的interrupt handler作为bottom half执行相应的操作。interrupt handler中没有任何用户进程的上下文，因此无法进行copyin或copyout，只有top half才能和用户进程进行交互。

• PLIC: Platform-Level Interrupt Controller，负责对从外部设备产生的中断进行管理
• CLINT: Core-Local Interrupter，负责定时器相关的中断

7.1 Console input

console driver(kernel/console.c)是一个设备驱动，通过UART串口接受输入的符号。用户进程通过read system call来从console中一行行读取输入

xv6中使用的UART是QEMU模拟的16550芯片。UART硬件对于进程来说是一组memory-mapped寄存器，即RISC-V上有一些物理地址是直接和UART设备相连的。UART的地址从0x10000000或UART0开始，每个UART控制寄存器的大小为1字节，其位置定义在kernel/uart.c中。

• LSR寄存器：line status register，用来指示输入的字节是否准备好被用户进程读取

• RHR寄存器：receive holding register，用来放置可以被用户进程读取的字节。当RHR中的一个字节被读取时，UART硬件将其从内部的FIFO硬盘中删除，当FIFO中为空时，LSR寄存器被置0

• THR寄存器：transmit holding register，当用户进程向THR写入一个字节时，UART将传输这个字节

xv6的main函数将调用consoleinit来初始化UART硬件，使得UART硬件在接收到字节或传输完成一个字节时发出中断

xv6 shell程序通过user/init.c开启的文件描述符来从console读取字节（在while循环中调用getcmd，在其中调用gets，再调用readsystem call）。在kernel中调用consoleread，等待输入完毕之后的中断，然后将输入缓存在cons.buf中，将输入either_copyout到user space后返回用户进程。如果用户没有输入完整的一行，则读取进程将在sleepsystem call中等待。

当用户输入了一个字符后，UART硬件将产生一个中断，这个终端将触发xv6进入trap。trap handler将调用devintr来通过scause寄存器判断是外部设备触发了这个中断，然后硬件将调用PLIC来判断是哪个外部设备触发的这个中断，如果是UART触发的，devintr将调用uartintr。uartintr将读取从UART硬件中写入的字符然后将其传送给consoleintr，consoleintr将积累这些字符直到整行都已经被读取，然后将唤醒仍在sleep的consoleread。当consoleread被唤醒后，将这一行命令复制给user space然后返回。

RISC-V对中断的支持：

SIE(supervisor interrupt enable) 寄存器用来控制中断，其中有一位是控制外部设备的中断（SEIE），一位控制suffer interrupt(一个CPU向另外一个CPU发出中断)(SSIE)，一位控制定时器中断(STIE)

SSTATUS(supervisor status)寄存器，对某一个特定的CPU核控制是否接收寄存器，在kernel/riscv.h中的intr_on被设置

SIP(supervisor interrupt pending)寄存器，可以观察这个寄存器来判断有哪些中断在pending

case study:

用户在键盘上输入了一个字符l，这个l通过键盘被发送到UART，然后通过PLIC发送到CPU的一个核，这个核产生中断，跑到devintr，devintr发现是来自UART的，调用uartintr，调用uartgetc()通过RHR寄存器来获取这个字符，然后调用consoleintr，判断这个字符是否是特殊字符(backspace等)，如果不是则将这个字符通过consputc(c)echo回给user，然后将其存储在cons.buf中，当发现整行已经输入完成后(c=='\n' || c ==C('D')))，唤醒consoleread()

7.2 Console output

对console上的文件描述符进行writesystem call，最终到达kernel/uart.c的uartputc函数。输出的字节将缓存在uart_tx_buf中，这样写入进程就不需要等待UART硬件完成字节的发送，只要当这个缓存区满了的情况下uartputc才会等待。当UART完成了一个字符的发送之后，将产生一个中断，uartintr将调用uartstart来判断设备是否确实已经完成发送，然后将下一个需要发送的字符发送给UART。因此让UART传送多个字符时，第一个字符由uartputc对uartstart的调用传送，后面的字符由uartintr对uartstart的调用进行传送

I/O concurrency：设备缓冲和中断的解耦，从而让设备能够在没有进程等待读入的时候也能让console driver处理输入，等后面有进程需要读入的时候可以不需要等待。同时进程也可以不需要等待设备而直接写入字符到缓冲区。

在consoleread和consoleintr中调用了acquire来获取一个锁，从而保护当前的console driver，防止同时期其他进程对其的访问造成的干扰。

7.3 Timer interrupts

xv6用计时器中断来在线程间切换，usertrap和kerneltrap中的yield也会导致这种进程切换。RISC-V要求定时器中断的handler放在machine mode而不是supervisor mode中，而machine mode下是没有paging的，同时有另外一套完全独立的控制寄存器，因此不能将计时器中断的handler放在trap机制中执行。

kernel/start.c（在main之前）运行在machine mode下，timerinit()在start.c中被调用，用来配置CLINT(core-local interruptor)从而能够在一定延迟之后发送一个中断，并设置一个类似于trapframe的scratch area来帮助定时器中断handler将寄存器和CLINT寄存器的地址保存到里面，最终start设置timervec到mtvec(machine-mode trap handler)中使得在machine mode下发生中断后跳转到timervec然后enable定时器中断。

由于定时器中断可能在任意时间点发生，包括kernel在执行关键的操作时，无法强制关闭定时器中断，因此定时器中断的发生不能够影响这些被中断的操作。解决这个问题的方法是定时器中断handler让RISC-V CPU产生一个"software interrupt"然后立即返回，software interrupt以正常的trap机制被送到kernel中，可以被kernel禁用。

timervec是一组汇编指令，将一些寄存器保存在scratch area中，告知CLINT产生下一次定时器中断的时间，让RISC-V产生一个software interrupt，恢复寄存器并返回到trap.c中，判断which_dev==2为定时器中断后调用yield()

7.4 Real world

计时器中断将会通过调用yield进行强制的线程切换从而使CPU能够在各个内核线程之间均匀分配时间。

UART是通过对UART控制寄存器一个字节一个字节读取来获取数据的，这种方式叫做programmed I/O，因为是软件控制了数据的I/O，缺点是速度比较慢。DMA(Directed Memory Access)直接向RAM写入和读取数据，速度很快。现代的硬盘和网卡驱动使用DMA。

由于中断非常耗时，因此可以用一些技巧来减少中断。1. 用一个中断来处理很多一段时间内的事件。 2. 彻底禁止设备的中断，让CPU定时去检查这些设备是否有任务需要处理，这种技巧叫做polling

Lecture 8 Locking

多核CPU同时对某个共享的数据结构进行读写操作可能会发生冲突，因此需要concurrency control，即锁。锁提供了一种互斥机制，一段时间内只有一个CPU才能拥有这个锁，如果一个锁和一个被共享的数据结构联系起来，那么这个数据结构一次只能被一个CPU使用

8.1 Race conditions

kernel allocator中有一个free链表用来指示当前空闲待分配的内存，kalloc()将一页内存从free中弹出，kfree()将一页内存压入free。这个free链表被两个CPU的两个不同进程共享，如下图所示

race condition：一个内存地址同时被至少一个写入操作访问，会造成bug

struct element *list = 0;
struct lock listlock;

void push (int data) {
    struct element *l;
    l = malloc(sizeof *l);
    l->data = data;
    acquire(&listlock);
    // critical section
    l->next = list;
    list = l;
    release(&listlock);
}

在acquire和release之间的代码叫做critical section。

当两个进程同时要求一个相同的锁时，这两个进程发生冲突，xv6对进程锁冲突没有做预防举措，但是更复杂的其他的kernel对此有实现。

注意acquire和release的位置很重要，不要包围不必要的代码，否则会降低程序运行效率。

8.2 Code: Locks

xv6有两种锁：spinlock和sleep-lock。spinlock的代码位于kernel/spinlock.h的struct spinlock中

struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

locked为0时说明这个锁是可以acquire的。

acquire中需要让类似于

if (lk->locked == 0)
    lk->locked = 1;

这样的逻辑原子化，否则当两个不同的进程同时执行到上面的判断条件时，可能会同时获取这个锁。RISC-V是通过amoswap r, a来实现的，它将a内存地址中的内容和r寄存器中的内容互换。在acquire中，通过一个对amoswap的包装函数__sync_lock_test_and_set(&lk->locked, 1)来实现这个原子操作，这个函数的返回值是lk->locked的旧的值(被换下来的值)

while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

通过while不断尝试将1和&lk->locked互换(spinning)，当原先的lk->locked是0时跳出循环，这个锁被取得，否则当原先的lk->locked是1时不会跳出循环，并且lk->locked和1互换还是1，不会改变它的状态。

release是acquire的反向操作，先将lk->cpu清零。然后调用

__sync_lock_release(&lk->locked);
// 相当于
// s1 = &lk->locked
// amoswap.w zero, zero, (s1)

将lk->locked置0，这也是一个原子操作。

由于编译器有时候为了性能优化会重新排列代码的执行顺序，对于顺序执行的代码来说，这种重新排列顺序并不会改变代码执行的结果，但是对于并发执行的代码，则可能改变结果，因此需要在acquire和release中用__sync_synchronize()来保证CPU和编译器不进行重新排列顺序。__sync_synchronize()是一个barrier，任何在这一行代码之前的代码都不能reorder到这一行代码的后面。

8.3 Deadlocks and lock ordering

如果一块代码需要同时拥有多个锁，那么应该让其他需要相同锁的进程按照相同的顺序acquire这些锁，否则可能出现死锁。比如进程1和2都需要锁A和锁B，如果进程1先acquire了锁A，进程2acquire了锁B，那么接下来进程1需要acquire锁B，进程2需要acquire锁A，但是这两个都不能acquire到也无法release各自的锁，就会出现死锁。

由于sleep在xv6中的机制，xv6中有很多长度为2的lock-order。比如consoleintr中要求先获得cons.lock，当整行输入完毕之后再唤醒等待输入的进程，这需要获得睡眠进程的锁。xv6的文件系统中有一个很长的lock chain，如果要创建一个文件需要同时拥有文件夹的锁、新文件的inode的锁、磁盘块缓冲区的锁、磁盘驱动器的vdisk_lock的锁以及调用进程的p->lock的锁

除了lock ordering之外，锁和中断的交互也可能造成死锁。比如当sys_sleep拥有tickslock时，发生定时器中断，定时器中断的handler也需要acquiretickslock，就会等待sys_sleep释放，但是因为在中断里面，只要不从中断返回sys_sleep就永远无法释放，因此造成了死锁。对这种死锁的解决方法是：如果一个中断中需要获取某个特定的spinlock，那么当CPU获得了这个spinlock之后，该中断必须被禁用。xv6的机制则更加保守：当CPU获取了任意一个lock之后，将disable掉这个CPU上的所有中断（其他CPU的中断保持原样）。当CPU不再拥有spinlock时，将通过pop_off重新使能中断

8.4 Sleep locks

spinlock的两个缺点：1. 如果一个进程拥有一个锁很长时间，另外一个企图acquire的进程将一直等待。2. 当一个进程拥有锁的时候，不允许把当前使用的CPU资源切换给其他线程，否则可能导致第二个线程也acquire这个线程，然后一直无法切回到原来的线程，无法release锁，从而导致死锁。

xv6提供了一种sleep-locks，可以在试图acquire一个被拥有的锁时yield CPU。spin-lock适合短时间的关键步骤，sleep-lock适合长时间的锁。

8.5 RCU

RCU(Read-Copy Update)是一种能让多个读进程对链表进行同时读取，并让一个写进程同时对链表进行写入修改操作的机制，这种机制避免了进程进行读/写操作都需要获取锁而造成的锁竞争问题，适用于大量进程同时对链表结构进行读取的操作。

基本原理是：写进程在写入某一个链表中的节点时，比如

head->E1->E2->E3->nil

试图修改E2->content，则不直接修改E2->content，因为在修改E2->content的过程中可能会有别的进程在读，此时可能读入写了一半的内容，我们希望一个读进程读取的内容要么是修改之前的，要么是修改之后的，而不是修改一半的内容。读进程的操作是

1. lock，防止其他写进程同时进行写入
2. e = alloc()，新分配一个element
3. e->next = E2->next，此时同时有2个element指向E3，但是其他读进程在读的时候还是读取的是旧的E2
4. e->content = new_content
5. E1->next = E，此时其他读进程在读的时候是新的E2，这是一个原子操作
6. unlock

由于编译器有时候为了优化会将2 3 4 5等步骤打乱，因此需要在第5步之前设置memory barrier，即只有在2 3 4均完成的情况下才能执行第5步

同时需要释放原先的E2，但是由于可能很多读进程已经获取了对原先E2的指针，必须等待这些读进程读取完毕不再使用E2才能将原先的E2释放掉，这是通过以下规则实现的：

1. 所有的读进程不能够在进行context switch时拥有着对RCU-protected data的指针，也就是说在读进程读完E2之前，不能yield CPU
2. 写进程需要等到所有的CPU都进行了一次context switch才能释放掉原先的数据，也就是E2(通过synchronize_rcu()实现)

// list reader using RCU interface
rcu_read_lock(); // 设置flag防止context switch
e = head;
while (p) {
    e = rcu_dereference(e); // 获取对e的指针
    a = e->content;
    e = e->next;
}
rcu_read_unlock(); // 可以开始context switch

// list writer using RCU interface, replacing head
acquire(lock);  // normal spin lock
old = head;     
e = alloc();
e->content = new_content;
e->next = head->next;
rcu_assign_pointer(&head, e); // commit the writes
release(lock);

synchronize_rcu(); // wait untill all cpus have context switched, meaning that no reader can hold the pointer to old head
free(old);