1:Xv6 and Unix utilities

运行环境:Ubuntu 20.04 qemu

在做6.s081的实验之前我们首先要先下载Xv6操作系统以及qemu虚拟机:

1	sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu

Lab1_1:Boot xv6

运行并安全退出xv6系统:

运行的方法很简单:cd进xv6的文件夹里面,然后输入`make qemu`即可,输入完之后就是进入了xv6的系统里面了

退出的方法就是,先Ctrl+A,再输入x即可.

Lab1_2 sleep

本实验要为 xv6 实现 UNIX 程序 sleep；您的睡眠应暂停用户指定的滴答数。滴答是 xv6 内核定义的时间概念，即来自定时器芯片的两次中断之间的时间。

一些提示：

在开始编码之前，请阅读xv6 书籍第 1 章。（中文版xv6 书籍)
查看user/中的其他一些程序（例如，user/echo.c、user/grep.c和user/rm.c）以了解如何获取传递给程序的命令行参数。
如果用户忘记传递参数， sleep 应该打印错误消息。
命令行参数作为字符串传递；您可以使用atoi将其转换为整数（请参阅 user/ulib.c）。
使用系统调用sleep。
确保main调用exit()以退出您的程序。
将你的睡眠程序添加到Makefile 中的UPROGS；完成后，make qemu将编译您的程序，您将能够从 xv6 shell 运行它。

查看 Kernighan 和 Ritchie 的书*The C programming language (second edition)*（K&R）以了解 C。

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc,char \*argv[]){
  for(int i=0;!argv[i];i++){
    if(argv[1][i]>'9'argv[1][i]<'0'){
      write(1, "error\\n", 6);
      exit(-1);
    }
  }
  int times=atoi(argv[1]);
  sleep(times);
  exit(0);
}

首先我们知道在C语言中argc代表传入的参数数,argv是传入的参数.

第一个for循环就是判断这个是不是一个正常的数字(什么时候结束循环呢?),第二步用atoi函数转化成数字,最后执行系统调用sleep.

Lab1_3 pingpong

编写一个程序，使用 UNIX 系统调用在两个进程之间通过一对管道“乒乓”一个字节，每个管道一个。父母应该向孩子发送一个字节；子进程应该打印“: received ping”，其中是它的进程 ID，将管道上的字节写入父进程，然后退出；父母应该从孩子那里读取字节，打印“: received pong”，然后退出。

一些提示：

使用管道创建管道。
使用 fork 创建一个孩子。
使用 read 从管道读取，并使用 write 写入管道。
使用 getpid 查找调用进程的进程 ID。
将程序添加到 Makefile 中的 UPROGS。
xv6 上的用户程序有一组有限的库函数可供它们使用。可以在 user/user.h 中看到列表；源（系统调用除外）位于 user/ulib.c、user/printf.c 和 user/umalloc.c。

我们可以认为pipe是一个Linux进程间通讯的一种方式,一个管道以一个两位的int类型数组构成,其中第一个元素是读端的接口编号,第二个元素是写端的接口编号.然后可以使用read和write来进行读取,注意管道的端口有读端口和写端口之分,读的时候只能从读端口读数据,写的时候只能从写的端口写数据.

有点像我们之前操作系统课上面学到的缓冲区的结构,缓冲区有两端,一端读一端写.

系统调用:
可以使用pipe(一个二位的数组)来初始化一个管道.经过pipe了之后,第一个元素就是一个读取的端口,第二个元素就是对应写入的端口,
可以使用read(读端口,读出来的元素写在哪里,长度)来从一个读的端口读出元素
可以使用write(写端口,写出来的元素写在哪里,长度)来把元素写进一个端口.

fork函数就是一次调用,两次返回,调用之后父进程和子进程都从获得函数的返回值开始继续往下运行,就像一条河流,遇到了一个分叉口,河流分成了两叉,这两叉都从分叉口开始继续往下流.在这里分叉口就像fork()调用,调用生成了两个分叉,两个分叉都从fork()调用结束后继续往下走.

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(){
  int p_filedes[2],s_filedes[2];
  pipe(p_filedes);
  pipe(s_filedes);
  char buf[4];
  if(fork()==0){
    read(p_filedes[0],buf,4);
    printf("%d: received %s\\n",getpid(),buf);
    write(s_filedes[1],"pong",4);
  }else{
    write(p_filedes[1],"ping",4);
    read(s_filedes[0],buf,4);
    printf("%d: received %s\\n",getpid(),buf);
  }
  exit(0);
}

函数的思路就是先初始化两根管道,接着父进程先read再写,子进程先写再read.

Lab1_4 prime

编写一个程序,完成一个并发版本的prime初筛,第一个进程负责把2-35范围内的素数输入进管道,对于每一个素数,我们都需要fork一个进程来接受管道的数字然后输出出来.

关闭进程不需要的文件描述符，否则你的程序将在第一个进程达到 35 之前耗尽 xv6 的资源。
一旦第一个进程达到 35，它应该等到整个管道终止，包括所有子、孙等。因此，主素数进程应该只在所有输出都被打印出来，并且在所有其他素数进程都退出之后才退出。
当管道的写端关闭时，read 返回零。
将 32 位（4 字节）整数直接写入管道是最简单的，而不是使用格式化的 ASCII I/O。
您应该仅在需要时在管道中创建流程。
将程序添加到 Makefile 中的 UPROGS。

基本的思路在下面,每一个进程对应一个素数,主进程负责传输2-34的数据给子进程们,每个进程对应一个素数,如果这个数%这个素数不为0的话就可以传给下一级的进程,如果没有下一级的进程那么fork一个新的进程,这个数一定是素数,这个进程就会接着处理来自左边邻居的数据,处理的方式.这样子每一个进程就像一个筛子,筛选不可能是素数的数.

总的来说主进程的数据首先从左到右到第一个子进程,判断能不能被2除,不可以就继续从左到右交给下一个子进程,判断能不能被3除…,如果下一个子进程是不存在的,那么新建一个进程,这个进程就代表对应数.

Lab1_5 find

编写一个简单版本的 UNIX 查找程序：查找目录树中具有特定名称的所有文件。给定对应的文件名以及文件名在目录,找到文件名的位置.

查看 user/ls.c 以了解如何读取目录。
使用递归允许 find 访问到子目录。
不要递归到“.” 和 ”..”。
对文件系统的更改在 qemu 运行中持续存在；要获得一个干净的文件系统，请运行 make clean 然后 make qemu。
1
2
3
4
struct dirent {
ushort inum;
char name[DIRSIZ];
};
上面是文件系统中关于目录文件内容的说明,inum说明这个文件占用了几个inode.该操作系统类似于Linux系统,磁盘分成磁盘块,磁盘块的一些相关控制信息就储存在存放在内存中的inode.文件系统获得文件,先找到文件的file结构,根据file结构找到inode,再根据inode找到磁盘块.

说白了目录文件存储的就是一堆dirent类型的结构体.

下面就是stat信息,stat信息存放了文件的一些控制信息,比如说链接信息,大小和类型之类的.在我们利用open打开文件后,open函数会返回一个数字,我们再利用fstat这个调用找到stat控制块.

struct stat {
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};

我们先来看看xv6是如何完成对ls指令的支持的?

首先第一个函数:根据文件的的路径名提取出文件的名字,就是从后往前遍历,找到第一个‘/’,这之间的那一部分就是文件的名字.

接着就是ls函数,ls函数中只需要提供当前的path,找到path里面的所有文件即可.首先先打开当前path对应的文件(Linux内部目录文件和普通的文件都是文件),再利用fstat系统调用找到stat的值.由于目录文件里面就是连续地存储了一堆dirent类型的结构体,那我们可以把目录文件的内容当成一个struct direntMAX

最后就是main函数,就是看看输入的指令罢了

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

char\* fmtname(char \*path)
{
  static char buf[DIRSIZ+1];
  char \*p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && \*p != '/'; p--)
    ;
  p++;

  // Return blank-padded name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
  return buf;
}

void ls(char \*path)
{
  char buf[512], \*p;
  int fd;
  struct dirent de;
  struct stat st;

  if((fd = open(path, 0)) < 0){
    fprintf(2, "ls: cannot open %s\\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){
    fprintf(2, "ls: cannot stat %s\\n", path);
    close(fd);
    return;
  }

  switch(st.type){
  case T_FILE:
    printf("%s %d %d %l\\n", fmtname(path), st.type, st.ino, st.size);
    break;

  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("ls: path too long\\n");
      break;
    }
    strcpy(buf, path);
    p = buf+strlen(buf);
    \*p++ = '/';
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        printf("ls: cannot stat %s\\n", buf);
        continue;
      }
      printf("%s %d %d %d\\n", fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}

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

  if(argc < 2){
    ls(".");
    exit(0);
  }
  for(i=1; i<argc; i++)
    ls(argv[i]);
  exit(0);

}

这个时候我们就可以对ls指令稍微修改修改,ls只用找当前目录第一层的所有文件,那么我们也是找当前目录的所有文件,对于目录文件,我们继续往下搜索这个目录,对于普通文件,我们只用看名字是否匹配即可.

Lab1_6 xargs

这个指令就是我们要把若干条指令合并在一块进行执行.其中前面指令的standard out会作为下一条的指令一个输入来进行执行.

举个例子:前面指令的hello too作为standard out作为下一条指令的输入.

1 2	$ echo hello too xargs echo bye $ bye hello too

使用 fork 和 exec 对每一行输入调用命令。在父级中使用 wait 等待子级完成命令。
要读取单行输入，请一次读取一个字符，直到出现换行符 (‘\n’)。
kernel/param.h 声明了 MAXARG，如果您需要声明 argv 数组，这可能很有用。
对文件系统的更改在 qemu 运行中持续存在；要获得一个干净的文件系统，请运行 make clean 然后 make qemu。
将程序添加到 Makefile 中的 UPROGS。

首先第一步把指令xargs给删除掉:然后把标准输出(来源:0)获取下来,放入最后一个参数中进行执行.

#include "kernel/types.h"
#include "kernel/param.h"
#include "user/user.h"

int main(int argc, char \*argv[]){
    char\* argvs[MAXARG];
    for(int i=1;i<argc;i++){
        argvs[i-1]=argv[i];
    }
    char buf[512];
    int index;
    int read_len;
    while(1){
        index = -1;
        do{
            index++;
            read_len=read(0,&buf[index],sizeof(char));
        }while(read_len>0&&buf[index]!='\\n');
        if(read_len==0&&index==0){
            break;
        }
        buf[index]='\\0';
        argvs[argc-1]=buf;
         if (fork() == 0) {
            exec(argvs[0], argvs);
            exit(0);
        } else {
            wait(0);
        }

    }
    exit(0);
}

2:Xv6 and Syscall

Lab2_1 Trace.

实验2_1主要是完成一个新的系统调用,这个系统调用主要的功能就是追踪,主要就是创建一个新的跟踪系统调用来控制跟踪,它应该采用一个参数,一个整数“掩码”,其位指定要跟踪的系统调用.比如说跟踪fork系统调用就会调用trace(1<<SYS_USER_FORK).我们需要修改 xv6 内核以在每个系统调用即将返回时打印出一行.该行应包含进程id、系统调用的名称和返回值,我们还必须对这个进程以及所有子进程进行跟踪.

//trace.c
int main(int argc, char \*argv[])
{
  int i;
  char \*nargv[MAXARG];

  if(argc < 3  (argv[1][0] < '0'  argv[1][0] > '9')){
    fprintf(2, "Usage: %s mask command\\n", argv[0]);
    exit(1);
  }

  if (trace(atoi(argv[1])) < 0) {
    fprintf(2, "%s: trace failed\\n", argv[0]);
    exit(1);
  }
  
  for(i = 2; i < argc && i < MAXARG; i++){
    nargv[i-2] = argv[i];
  }
  exec(nargv[0], nargv);
  exit(0);
}

我们发现在调用trace的时候,首先判断输入参数的合法性,然后再进行trace操作,接着再执行剩下的操作.这个时候trace就是一个系统调用,我们需要完成系统调用.

现在我们开始实验:

1) 在user.h中添加对于trace函数的支持.

这里面存储了所有user函数会调用的系统调用.

2) 添加一个entry在user.pl里面

#!/usr/bin/perl -w

# Generate usys.S, the stubs for syscalls.

print "# generated by usys.pl - do not edit\\n";

print "#include \\"kernel/syscall.h\\"\\n";

sub entry {
    my $name = shift;
    print ".global $name\\n";
    print "${name}:\\n";
    print " li a7, SYS_${name}\\n";
    print " ecall\\n";
    print " ret\\n";
}

entry("fork");
entry("exit");
entry("wait");
entry("pipe");
entry("read");
entry("write");
entry("close");
entry("kill");
entry("exec");
entry("open");
entry("mknod");
entry("unlink");
entry("fstat");
entry("link");
entry("mkdir");
entry("chdir");
entry("dup");
entry("getpid");
entry("sbrk");
entry("sleep");
entry("uptime");
entry("trace");

这个user.pl负责输出汇编代码,这个汇编代码就是user文件夹里面的代码调用系统调用之后由U态进入到S态的过渡代码,主要是构建参数的代码和ecall组成.

执行顺序:调用系统调用->user.pl生成的代码(U态进入到S态)->S态的系统调用.

3) 在syscall.h添加系统调用号

// System call numbers
#define SYS_fork    1
#define SYS_exit    2
#define SYS_wait    3
#define SYS_pipe    4
#define SYS_read    5
#define SYS_kill    6
#define SYS_exec    7
#define SYS_fstat   8
#define SYS_chdir   9
#define SYS_dup    10
#define SYS_getpid 11
#define SYS_sbrk   12
#define SYS_sleep  13
#define SYS_uptime 14
#define SYS_open   15
#define SYS_write  16
#define SYS_mknod  17
#define SYS_unlink 18
#define SYS_link   19
#define SYS_mkdir  20
#define SYS_close  21
#define SYS_trace  22

这个文件里面存储了系统调用的调用调用号,在后面这些宏就负责替换为编号.

4) 在proc结构体里面添加一个mask成员,用来记录要trace哪种系统调用.

5) 在kernel/sysproc.c里面实现具体的系统调用,在这里你会发现系统调用的实现会保存在这里.

uint64
sys_trace(void)
{
  int n;
  if (argint(0, &n) < 0) // get the number of argv[1].
    return -1;
  myproc()->mask = n;    // save in the mask.
  return 0;
}

这个时候可以通过argint系统调用来获得栈帧中保存的寄存器值.然后把寄存器的值保存到mask元素中.

6) 更改fork函数,添加mask的复制.`np->mask = p->mask;`

这一步的目的就是为了让子进程执行系统调用也可以完成.

7) 添加syscall.c中关于trace函数的支持.

//在syscall的函数数组中添加即可.
......
[SYS_close]   sys_close,
[SYS_trace]   sys_trace,
};
//添加函数声明.
extern uint64 sys_trace(void);

8) 更改syscall.c的syscall函数

void
syscall(void)
{
  int num;
  struct proc \*p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
    if (p->mask & (1 << num))
    {
      printf("%d: syscall %s -> %d\\n",p->pid, syscalls_name[num], p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

添加关于追踪的函数,追踪的方法很简单,因为要追踪的mask是处于第几位的,只需要求一个与看看是不是0即可.

全部过关

Lab2_2 sys info

我们需要完成一个系统调用,给定一个struct sysinfo的指针,然后可以输出当前系统的可用进程数和可用内存数.

1) 在makefile,user.pl和user.h添加对于sysinfo系统调用的支持.(不懂的请翻阅上面)

2) 统计当前正在使用进程数.定义新函数proc_size(),在proc.h中

//return: the proc that are occupied.
int
proc_size()
{
  int i;
  int n = 0;
  for (i = 0; i < NPROC; i++)
  {
    if (proc[i].state != UNUSED) n++;
  }
  return n;
}

方法就是对于所有进程(NPROC)进行一遍遍历,如果不是UNUSED,就代表已经使用了

3) 统计当前的内存数,定义新函数freememory(),在kalloc.h中.

uint64 
freememory()
{
  struct run\* p = kmem.freelist;
  uint64 num = 0;
  while (p)
  {
    num ++;
    p = p->next;
  }
  return num \* PGSIZE;
}

获得freelist(物理内存中没有分配的块),然后对链表进行一遍遍历,找到有几个块没有分配,乘以一个块的数量即可.

4) 完成sysinfo的操作.注意2)和3)定义的函数要声明在`def.h`中

uint64
sys_sysinfo(void)
{
  struct sysinfo info;
  uint64 addr;
  // get the the address of the sysinfo structure.
  if (argaddr(0, &addr) < 0) 
    return -1;
  struct proc\* p = myproc();
  //get freemem
  info.freemem = freememory();
  //get the proc
  info.nproc = proc_size();
  // copyto the structure.
  if (copyout(p->pagetable, addr, (char\*)&info, sizeof(info)) < 0)
    return -1;
  return 0;
}

这个操作主要是,用户会传递指针来,这个指针就指向了sysinfo的结构体,所以说我们需要在内核态获得信息构造一个新的结构体传回去就可以了.

5) 像上个实验一样完成syscall.h,syscall.c的支持即可.

3:Xv6 and PageTable

Lab3_1 Speed Up the system calls

一些操作系统（例如 Linux）通过在用户空间和内核之间共享只读区域中的数据来加速某些系统调用。这消除了在执行这些系统调用时对内核交叉的需要。

创建每个进程时，在 USYSCALL（memlayout.h 中定义的 VA）映射一个只读页面。在这个页面的开始，存储一个struct ussyscall（也在memlayout.h中定义），并初始化它来存储当前进程的PID。

可以在 kernel/proc.c 中的 proc_pagetable() 中执行映射。
只读的权限位要确保正确
mappages() 是一个有用的实用程序。
不要忘记在 allocproc() 中分配和初始化页面。
确保在 freeproc() 中释放页面。

1) 确认usyscall的结构体是什么,其实存储的就是pid.

1
2
3

struct usyscall {
  int pid;  // Process ID
};

2) 为每个进程结构添加usyscall的元素,这个结构存储在一个新的页里面.

3) 打开proc.c,依葫芦画瓢给usyscall结构体申请一个页面.

// alloc a page that store usyscall proc
  if((p->usyss = (struct usyscall \*)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

4) 依据提示,我们在proc_pagetable中依葫芦画瓢来进行地址的映射,注意,如果映射失败是要把之前俩都给取消掉

if (mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall),
             PTE_R  PTE_U) < 0) {
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
}

其中mappages(表,虚拟地址,页大小,物理地址,权限)

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access

权限的编码有几种方式,分别用五位0-1表示,从左到右都是可运行,可读,可写,只可以内核用,用户可以用.

5) 在进程初始化的时候添加初始化的代码.初始化usyscall的结构.

p->usyscall->pid = p->pid;

6) 进程结束的时候,free掉进程的时候把这一页也free掉

if (p->usyss) kfree((void *)p->usyss);
p->usyss = 0;

7) 进程结束的时候,依葫芦画瓢把映射关系给取消掉.

uvmunmap(pagetable, USYSCALL, 1, 0);

Lab3_2 Print a page table

在这部分实验中，您将向 xv6 添加一个新功能，该功能通过检查 RISC-V 页表中的访问位来检测并向用户空间报告此信息。定义一个名为 vmprint() 的函数。它应该接受一个 pagetable_t 参数，并以下面描述的格式打印该页表。

page table 0x0000000087f6e000//二级页表
 ..0: pte 0x0000000021fda801 pa 0x0000000087f6a000//二级页表的表项,进入一级页表
 .. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000//一级页表的表项,进入页表
 .. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
 .. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
 .. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
 ..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
 .. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
 .. .. ..509: pte 0x0000000021fdd813 pa 0x0000000087f76000
 .. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
 .. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

在exec.c中的_return argc;之前插入_if(p->pid==1) vmprint(p->pagetable) 语句来输出第一个进程的页表.

首先要确定的第一点就是,这个页表其实实际上是一种多级页表的结构,就是二级页表存储的表项(PPN)其实是一级页表的第一个PTE的地址,一级页表的表项才是pa.具体的多级页表的解释可以参考我其他的博客或者翻阅操作系统或者组员书.

首先我们知道,PTE是一个长度为64的整数而已.其中存储了各种各样的信息,这些信息可以通过调用宏来实现:

1
2
3

#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)

其实本质上来说,就是xv6系统的PTE除去后10位和前12位就是pa.

所以说这个东西就可以转化为基本的递归.对于二级页表,对于每一个表项就进入到一级页表再遍历.所以说本质上这就是一个树,二级页表作为根,有若干个儿子,也就是一级页表,一级页表也有若干个儿子…那遍历树怎么遍历,一般来说就是用递归的手段

● 可以将vmprint( )放在kernel/vm.c中。
● 使用kernel/riscv.h文件末尾的宏。
● 函数freewalk可能是鼓舞人心的（可以仿照该函数来写vmprint）。
● 在kernel/defs.h中定义vmprint的原型，以便可以从exec.c调用它。
● 在printf调用中使用%p输出完整的64位十六进制PTE和地址，如示例所示。

1) 根据提示,在exec的return argc之前添加一段:

1
2
3

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

2) 在def.h中添加对于vmprint的定义

3) 修改vm.c,仿照freewalk改造函数.

void vmprintlevel(pagetable_t pt, int level) {
    char \*delim = 0;
    if (level == 2) delim = "..";
    if (level == 1) delim = ".. ..";
    if (level == 0) delim = ".. .. ..";
    for (int i = 0; i < 512; i++) {
        pte_t pte = pt[i];
        if ((pte & PTE_V)) {
            //  this PTE points to a lower level page table.
            printf("%s%d: pte %p pa %p\\n", delim, i, pte, PTE2PA(pte));
            uint64 child = PTE2PA(pte);
            if ((pte & (PTE_RPTE_WPTE_X)) == 0) {
                vmprintlevel((pagetable_t)child, level - 1);
            }
        }
    }
}

void vmprint(pagetable_t pt) {
    printf("page table %p\\n", pt);
    vmprintlevel(pt, 2);
}

思想就是递归,递归获得下一级的地址,本质上是一个DFS.有下一级的页表就进入下一级进行遍历.

Lab3_3 Detecting which pages have been accessed

在本部分的实验中，你将向xv6添加一个新特性，通过检查RISC-V页表中的访问位来获取信息并向用户空间报告这些信息。

实现pgaccess()函数，它是一个系统调用,会返回哪些页面已经被访问.其中第一个参数就是从哪个虚拟地址开始检查,第二个参数就是检查几个页面,结果传递给第三个参数,第三个参数是位掩码,其中第几位为1表示第几个页面已经被访问了.

● 首先在kernel/sysproc.c中实现sys_pgaccess( )。
● 你需要使用argaddr()和argint()解析参数。
● 对于输出位掩码，在内核中存储一个临时缓冲区并在填充正确的位后将其复制给用户（通过copyout()）更容易。
● 可以设置可扫描页数的上限。
● kernel/vm.c中的walk()对于查找正确的PTE非常有用。
● 你需要在kernel/riscv.h中定义PTE_A，即访问位。请参阅RISC-V手册以确定其值。
● 如果PTE_A已设置，在检查后务必清除它。否则，将无法确定自上次调用pgaccess()以来是否访问了页面（即，该位将被永久设置）。
● 利用vmprint()可方便地调试页表。

1) 参阅RISC-V手册,确定PTE_A是什么.

1	#define PTE_A (1L << 6)

2) 完成sys_pgaccess,在这里主要是处理参数.利用argaddr和argint处理参数.

uint64 sys_pgaccess(void) {
    // lab pgtbl: your code here.
    // get argument
    uint64 buf;
    int number;
    uint64 ans;
    if (argaddr(0, &buf) < 0) return -1;
    if (argint(1, &number) < 0) return -1;
    if (argaddr(2, &ans) < 0) return -1;
    return pgaccess((void\*)buf, number, (void\*)ans);
}

3) 读取当前虚拟地址,找到对应的页表项目的函数找到:walk

使用方法:te = (pte_t*)walk(pagetable, ((uint64)pg) + (uint64)PGSIZE * i, 0);

4) 读取接着根据pte表项,找到PTE_A位.

uint64 pgaccess(void \*pg, int number, void \*store) {
    struct proc \*p = myproc();
    if (p == 0) {
        return 1;
    }
    pagetable_t pagetable = p->pagetable;
    int ans = 0;
    for (int i = 0; i < number; i++) {
        pte_t\* pte;
        pte = (pte_t\*)walk(pagetable, ((uint64)pg) + (uint64)PGSIZE \* i, 0);
        if (pte != 0 && ((\*pte) & PTE_A)) {
            ans = 1 << i;
            \*pte ^= PTE_A;  // clear PTE_A
        }
    }
    // copyout
    return copyout(pagetable, (uint64)store, (char \*)&ans, sizeof(int));
}

4:Xv6 and Trap

Lab4_1 RISC-V Assembly

我们需要运行对call.c这份代码的编译,然后回答一些问题

make fs.img编译之后我们可以找到下面的

int g(int x) {
   0:1141                addisp,sp,-16
   2:e422                sds0,8(sp)
   4:0800                addis0,sp,16
  return x+3;
}
   6:250d                addiwa0,a0,3
   8:6422                lds0,8(sp)
   a:0141                addisp,sp,16
   c:8082                ret

000000000000000e <f>:

int f(int x) {
   e:1141                addisp,sp,-16
  10:e422                sds0,8(sp)
  12:0800                addis0,sp,16
  return g(x);
}
  14:250d                addiwa0,a0,3
  16:6422                lds0,8(sp)
  18:0141                addisp,sp,16
  1a:8082                ret

000000000000001c <main>:

void main(void) {
  1c:1141                addisp,sp,-16
  1e:e406                sdra,8(sp)
  20:e022                sds0,0(sp)
  22:0800                addis0,sp,16
  printf("%d %d\\n", f(8)+1, 13);
  24:4635                lia2,13
  26:45b1                lia1,12
  28:00000517          auipca0,0x0
  2c:7b050513          addia0,a0,1968 # 7d8 <malloc+0xea>
  30:00000097          auipcra,0x0
  34:600080e7          jalr1536(ra) # 630 <printf>
  exit(0);
  38:4501                lia0,0
  3a:00000097          auipcra,0x0
  3e:27e080e7          jalr638(ra) # 2b8 <exit>
}

1.Q:Which registers contain arguments to functions? For example, which register holds 13 in main’s call to printf?
哪些寄存器存储了函数的参数?比如说调用printf的时候13存在哪个寄存器里面?

A:a0~a7共8个参数,其中调用printf的时候13就存在a2这个寄存器里面

2.Q:Where is the call to function f in the assembly code for main? Where is the call to g? (Hint: the compiler may inline functions.)
汇编代码中哪一部分出现了对函数f的调用,函数g呢?

A:其实并没有,编译器把g函数内联到f函数里面,再把f函数内联到main里面

3.Q:At what address is the function printf located?
printf的入口地址在哪里?

A:根据jalr 1536(ra)可以知道printf的地址在0x630这个里面

4.Q:What value is in the register ra just after the jalr to printf in main?
printf执行完返回到main的时候ra寄存器的值是多少?

显然ra中应是jalr下一条指令的地址，即0x38。

5.Q:Run the following code.

unsigned int i = 0x00646c72;
printf(“H%x Wo%s”, 57616, &i);

What is the output? Here’s an ASCII table that maps bytes to characters.

The output depends on that fact that the RISC-V is little-endian. If the RISC-V were instead big-endian what would you set i to in order to yield the same output? Would you need to change57616 to a different value?
输出是什么?RISC-V是小端存储的.如果是大端存储的呢?

Here’s a description of little- and big-endian and a more whimsical description.

输出”HE110 World”. 57616=0xe110。RISC-V 是 little-endian，&i处存储的字节依次为0x72:r, 0x6c:l, 0x64:d，0x00:Null char (空字符)。

如果 RISC-V 是 big-endian，则i = 0x726c6400;. 57616不需改变，因为不管怎样它的十六进制形式都不会变。

6.Q:In the following code, what is going to be printed after 'y='? (note: the answer is not a specific value.) Why does this happen?
执行下一条语句,会输出y=多少呢?

printf(“x=%d y=%d”, 3);

因为函数a0~a7都存着参数,所以说对应的输出第二个参数的内容,也就是a1寄存器的内容.

Lab4_2 BackTrace

添加一个新的功能,打印函数调用栈.在这个机器中,我们知道有一个结构叫做栈帧,可以保存当前函数调用某个函数之前的一些寄存器,返回地址和一些局部变量的信息,比如说C语言的main函数,main函数调用一个函数f1(),在进入f1()函数的执行之前,编译器会帮我们把main函数的一些寄存器、局部变量的信息保存在栈帧中放入堆栈.其中栈帧中有一个特别的元素就是上一个栈帧的地址.

本实验的要求就是在kernel/printf.c 中实现backtrace()函数。在sys_sleep中插入对该函数的调用。然后运行bttest，它调用sys_sleep。输出应如下：

1) 在def.h添加backtrace()函数的声明.

2) GCC 编译器将当前执行的函数的帧指针存储在寄存器s0中,s0就对应上面的fp指针.

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

3) 完成backtrace()

我们知道fp指针往下走两个字节就存储的上一个函数的栈帧的最高地址,所以说我们可以循环一下,每一次循环就取上一个函数的栈帧最高地址,输出返回地址即可.

void
backtrace(void){
  uint64 fp = r_fp(), top = PGROUNDUP(fp);
  printf("backtrace:\\n");
  for(;fp<top;fp=\*(uint64\*)(fp-16)){
    printf("%p\\n", \*((uint64\*)(fp-8)));
  }
}

Lab4_3 Alarm

在本练习中，您将向xv6添加一项功能，该功能会在使用CPU时间的情况下定期向进程发出警报。这对于想要限制消耗多少CPU时间的计算密集型进程，或者对于想要进行计算但还希望采取一些定期操作的进程很有用。

您应该添加一个新的sigalarm(interval,handler)系统调用。如果应用程序调用sigalarm(n,fn)，则在程序每消耗n个“ tick” CPU时间之后，内核应导致调用应用程序函数fn。当fn返回时，应用程序应从中断处恢复。滴答是xv6中相当随意的时间单位，由硬件计时器产生中断的频率决定。如果应用程序调用sigalarm(0,0)，则内核应停止生成定期警报调用。

test0：调用处理程序

1.修改Makefile，为sigalarm和sigreturn系统调用添加桩代码。
2.现在，sys_sigreturn应该只返回零。
3.sys_sigalarm()应该将nl和handler存储在proc结构的新字段中（在kernel/proc.h 中）。
4.您需要跟踪该进程自上次调用alarm handler以来已经过去了多少ticks。为此，您还需要struct proc中的一个新字段。您可以在proc.c的allocproc() 中初始化这个字段。
5.每当tick时，硬件时钟都会强制中断，该中断在kernel/trap.c的usertrap()中处理。
6.时钟中断是：if(which_dev == 2) …
7.您需要修改usertrap()以在进程的警报间隔到期时，用户进程执行handler。

test1/test2(): 恢复中断的代码

8.handler完成后，控制权返回到用户程序最初被中断的指令。必须确保寄存器内容恢复，以及重置警报计数器。以便定期调用handler。
9.user alarm handler需要在完成后调用sigreturn系统调用。这意味着您可以将代码添加到usertrap和sys_sigreturn中，它们会协同工作以使用户进程在处理完警报后正确恢复。
10.确保正确地保存和恢复寄存器。
11.当计时器到期时，让 usertrap 在 struct proc 中保存足够的状态，以便sigreturn可以正确返回到被中断的用户代码。
12.防止对处理程序的重入调用——如果处理程序尚未返回，内核不应再次调用它。

首先就是把添加系统调用的路子走一遍.

1) 在user.h中添加声明:

1 2	int sigalarm(int ticks, void (\*handler)()); int sigreturn(void);

2) 在user.pl添加函数入口以生成汇编代码.

1 2	entry("sigalarm"); entry("sigreturn");

3) 在syscall.h添加系统调用号.

1 2	#define SYS_sigalarm 22 #define SYS_sigreturn 23

4) 在syscall.c中添加关于这两个系统调用的声明.

......
extern uint64 sys_sigalarm(void);
extern uint64 sys_sigreturn(void);
......
[SYS_sigalarm]  sys_sigalarm,
[SYS_sigreturn] sys_sigreturn,

5) 在proc的进程结构体中添加成员,保存什么时候中断,中断执行什么,过多久就进行一次中断,还保存中断的时候栈顶指针和保存的栈帧.

int interval;// interupt count
void (\*handler)(); //handle programme
int count; //tick interupt count
uint64 interrupt_ra; //trapframe pointer.
struct trapframe \*saved_trapframe;//saved_trapframe
int isworking;

6) 在allocproc函数中初始化这些成员.

p->interval = 0;
p->handler = 0;
p->count = 0;
p->is working = 0;

7) 完成sigalarm的系统调用,做法就是从寄存器获得参数然后赋值给proc的元素中.

uint64
sys_sigalarm(void){
  struct proc\* p = myproc();
  int in;
  uint ft;
  int interval;
    uint64 pt;
    if(argint(0, &in) < 0)
      return -1;
    if(argaddr(1, &ft) < 0)
      return -1;

    p->interval=in;
    p->handler=(void\*)ft;
    return 0;
}

8) 完成时钟

if(which_dev == 2){
    //the proc no call the sysalaram.
    if(p->interval==0p->working)
    {
      yield();
      usertrapret();
    }
    else{
      p->count++; 
      if(p->count==p->interval)
      {
        //save the trapframe.
        p->saved_trapframe=(struct trapframe\*)kalloc();
        memmove(p->saved_trapframe,p->trapframe,PGSIZE);
        
        //save the trapped address
        p->interrupt_ra=p->trapframe->epc;
        //the programme will start at handler.
        p->trapframe->epc=(uint64)p->handler;
        usertrapret();
        yield();
      }
    }
  }

处理的方式是分类,如果之前没有调用过sigalarm的话,interval为0,就和原来一样,如果不是的话就代表调用过.接着count++,如果count和interval一样的话就代表要跳转了,保存当前的trapframe以及当前被中断的指令的地址,修改epc进行跳转.还有就是要记录working,如果这个函数已经被打断了就不要再重新打断一次.

9) 完成返回的操作.

uint64 sys_sigreturn(void)
{
  struct proc\* p = myproc();
  p->count=0;
  p->trapframe->epc=p->interrupt_ra;
  memmove(p->trapframe,p->saved_trapframe,PGSIZE);
  p->isworking = 0;
  return 0;
}

把之前保存的断点地址和栈帧读出来,清空时钟即可.

6:Xv6 and MultiThread

Lab6_1 Uthread: switching between threads

在本实验中，您将为用户级线程系统设计上下文切换机制，然后实现它。你的 xv6 有两个文件 user/uthread.c 和 user/uthread_switch.S，以及 Makefile 中的一个规则来构建一个 uthread 程序。uthread.c 包含大部分用户级线程包，以及三个测试线程的代码。但线程包中缺少一些用于创建线程和线程间切换的代码。

您需要创建一个函数,这个函数可以创建一个进程,在切换进程的时候保存和恢复寄存器.

您需要在 user/uthread.c 中的thread_create()和thread_schedule()以及user/uthread_switch.S中的thread_switch中添加代码。

一个目标是确保当thread_schedule()第一次运行给定线程时，该线程在自己的堆栈上执行传递给thread_create()的函数(这个函数作为一个参数传递给thread_create()函数调用)。换句话说,就是创建线程的时候,有一个参数就是一个地址,这个地址指向一个函数,当这个线程第一次启动的时候就从这个地址对应的指令开始执行.

另一个目标是确保thread_switch保存被切换的线程的寄存器，恢复被切换到的线程的寄存器，并返回到后一个线程的指令中上次停止的点。您必须决定在哪里保存/恢复寄存器；修改struct thread以保存寄存器是一个不错的计划。

您需要在thread_schedule中添加对thread_switch的调用；您可以将所需的任何参数传递给thread_switch，但目的是从线程t切换到next_thread。

thread_switch 只需要保存/恢复callee-save registers。

要测试您的代码，使用riscv64-linux-gnu-gdb单步执行thread_switch可能会有所帮助。您可以通过以下方式开始：

1
2
3

(gdb) file user/_uthread
Reading symbols from user/_uthread...
(gdb) b uthread.c:60

这将在uthread.c的第60行设置一个断点。甚至在运行uthread之前，可能会（或可能不会）触发断点。一旦您的xv6 shell运行，键入“ uthread”，gdb将在第60行中断。现在，您可以键入以下命令来检查uthread的状态：

1	(gdb) p/x \*next_thread

使用“ x”，您可以检查存储位置的内容：

1	(gdb) x/x next_thread->stack

您可以跳到thread_switch的开头，这样：

1 2	(gdb) b thread_switch (gdb) c

您可以使用以下步骤进行单步组装说明：

(gdb) si

ni是下一条汇编语句,n是下一条C语言语句.

1) 修改thread_switch的代码,添加上关于thread_switch 的代码,只需要保存/恢复callee-save register:

sd ra, 0(a0)
sd sp, 8(a0)
sd s0, 16(a0)
sd s1, 24(a0)
sd s2, 32(a0)
sd s3, 40(a0)
sd s4, 48(a0)
sd s5, 56(a0)
sd s6, 64(a0)
sd s7, 72(a0)
sd s8, 80(a0)
sd s9, 88(a0)
sd s10, 96(a0)
sd s11, 104(a0)

ld ra, 0(a1)
ld sp, 8(a1)
ld s0, 16(a1)
ld s1, 24(a1)
ld s2, 32(a1)
ld s3, 40(a1)
ld s4, 48(a1)
ld s5, 56(a1)
ld s6, 64(a1)
ld s7, 72(a1)
ld s8, 80(a1)
ld s9, 88(a1)
ld s10, 96(a1)
ld s11, 104(a1)

其中a0代表了被打断的线程的栈帧,a1代表了要切换到的线程的栈帧.其中栈帧就是相对于thread的结构体的偏移.

2) 在Thread的数据结构中添加寄存器信息.

  uint64 ra;
  uint64 sp;
  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
//修改后
thread{
  栈帧
  栈
  状态
}

3) 修改创建进程的代码.对ra和sp寄存器进行初始化.其中ra本质上就是断点寄存器.有一个参数就是一个地址,这个地址指向一个函数,当这个线程第一次启动的时候就从这个地址对应的指令开始执行.把这个参数传递给ra

1 2	t->ra=(uint64)func; t->sp=(uint64)&t->stack[STACK_SIZE-1];

其中栈是从高到低的,所以说初始的栈顶指针是指向最高的地址的.

4) 调用switch函数,切换.其中t是当前进程,next_thread是下一个进程.

1	thread_switch((uint64)t,(uint64)next_thread);

Lab6_2 Using Thread.

文件notxv6 / ph.c包含一个简单的哈希表，该哈希表从单个线程使用时是正确的，但从多个线程使用时则是错误的。在您的主要xv6目录（可能是〜/ xv6-labs-2020）中，键入以下命令：

1 2	$ make ph $ ./ph 1

请注意，要生成ph，Makefile使用操作系统的gcc，而不是6.S081工具。 ph的参数指定在哈希表上执行放置和获取操作的线程数。

ph运行两个基准。首先，它通过调用put（）向哈希表添加很多键，并输出每秒达到的puts速率。它使用get（）从哈希表中获取密钥。它打印由于puts而应在哈希表中但丢失的数字键（在这种情况下为零），并打印每秒获得的获取次数。

您可以通过给它一个大于1的参数来告诉ph同时使用多个线程的哈希表。尝试ph 2：

$ ./ph 2
100000 puts, 1.885 seconds, 53044 puts/second
1: 16579 keys missing
0: 16579 keys missing
200000 gets, 4.322 seconds, 46274 gets/second

此ph 2输出的第一行表明，当两个线程同时向哈希表添加条目时，它们每秒的总插入率为53,044。这大约是运行ph 1时单线程的速度的两倍。这是大约2倍的出色“并行加速”，这是人们可能希望的（即两倍的内核，每单位时间产生两倍的工作量）。

但是，两行说缺少16579键，表明哈希表中不应该存在大量键。就是说，puts应该将这些键添加到哈希表中，但是出了点问题。看一下notxv6 / ph.c，尤其是put（）和insert（）。

为什么缺少2个线程而不是1个线程的键？用2个线程标识一系列事件，这些事件可能导致键丢失。提交您的序列，并在answer-thread.txt中提供简短解释。为避免发生此序列的事件，请在putx和get.not.v6 / ph.c中插入lock和unlock语句，以便两个线程始终缺少0的键数。相关的pthread调用为：

pthread_mutex_t lock;            // declare a lock
pthread_mutex_init(&lock, NULL); // initialize the lock
pthread_mutex_lock(&lock);       // acquire lock
pthread_mutex_unlock(&lock);     // release lock

其实本质上,线程之间也会有互斥的关系,两个线程不能同时访问同一个缓冲区,如果同时当文同一个缓冲区的同一个位置就导致了写重复的问题,就需要对访问缓冲区的代码块上锁,只允许一个线程访问缓冲区.也就是只允许一个进程访问数组的某一个位置.

pthread_mutex_t locks[NBUCKET];

static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  // is the key already present?
  struct entry \*e = 0;
  for (e = table[i]; e != 0; e = e->next) {
    if (e->key == key)
      break;
  }
  pthread_mutex_lock(&locks[i]);
  if(e){
    // update the existing key.
    e->value = value;
  } else {
    // the new is new.
    insert(key, value, &table[i], table[i]);
  }
  pthread_mutex_unlock(&locks[i]);
}

跟我们学过的操作系统一样,线程在进入访问缓冲区的代码之前上锁,线程离开访问缓冲区的代码后解锁.

Lab6_3 Barrier

在此分配中，您将实现一个障碍：应用程序中的一个点，所有参与线程必须在该点等待，直到所有其他参与线程也都到达该点。您将使用pthread条件变量，这是一种类似于xv6的睡眠和唤醒的序列协调技术。

文件notxv6 / barrier.c。

1
2
3

$ make barrier
$ ./barrier 2
barrier: notxv6/barrier.c:42: thread: Assertion \`i == t' failed.

2指定在屏障上同步的线程数（barrier.c中的nthread）。每个线程执行一个循环。在每个循环迭代中，线程都会调用barrier（），然后睡眠随机数微秒。断言触发，因为一个线程在另一线程到达屏障之前就离开了屏障。理想的行为是每个线程都在barrier（）中阻塞，直到它们的所有nthread都调用了barrier（）。

pthread_cond_wait(&cond, &mutex);  // go to sleep on cond, releasing lock mutex, acquiring upon wake up
pthread_cond_broadcast(&cond);     // wake up every thread sleeping on cond

  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread+=1;pthread_mutex_unlock(&bstate.barrier_mutex);
  if(bstate.nthread<nthread)
  {
    pthread_cond_wait(&bstate.barrier_cond,&bstate.barrier_mutex);//go to sleep on cond,releasing lock mutes acquirint upon wake up
  }
  else{
    bstate.round+=1;//next round
    bstate.nthread=0;//the thread that have entered the barrier() function -> 0 
    pthread_cond_broadcast(&bstate.barrier_cond);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);

因为要修改临界量nthread,所以说进入之前所以要加上锁.如果没到就停止,释放锁,如果到了的话就nthread=0,round+1,调用broadcast函数即可.

7:Xv6 and Networking

背景

您将使用称为 E1000 的网络设备来处理网络通信。对于 xv6（以及您编写的驱动程序），E1000 看起来像是连接到真实以太网局域网 (LAN) 的真实硬件。实际上，您的驱动程序将与之通信的 E1000 是由 qemu 提供的仿真，连接到同样由 qemu 仿真的 LAN。在这个模拟 LAN 上，xv6（“guest”）的 IP 地址为 10.0.2.15。 Qemu 还安排运行 qemu 的计算机出现在 IP 地址为 10.0.2.2 的 LAN 上。当 xv6 使用 E1000 向 10.0.2.2 发送数据包时，qemu 会将数据包传送到您正在运行 qemu（“主机”）的（真实）计算机上的适当应用程序。(就是qemu模拟器传递数据到真实的计算机中)

你将会用到QEMU的 “用户态网络栈”。QEMU的文档中由很多关于用户态栈的描述。我们已经更新了 Makefile，打开了QEMU的用户态网络栈以及E1000网卡。

Makefile 设置了 QEMU记录所有的进出数据包到文件 packets.pcap。这可能对于检查接收发送的数据包是有用的。展现记录的数据包：

tcpdump -XXnr packets.pcap

你的工作.

我们已经添加了一些文件到xv6上了。文件kernel/e1000.c包含了E1000的初始化代码以及空的传输和接收数据包的函数，这些是需要你去完成的。kernel/e1000_dev.h包含了寄存器和标志位的定义，这些在Intel E1000的文档有描述。kernel/net.c和kernel/net.h包含了一个简单的包含IP、UDP、ARP协议的网络栈。这些文件页包含了一个灵活的数据结构来持有数据包，叫做mbuf。最后，kernel/pci.c包含了在xv6启动时，在PCI总线上查找一个E1000网卡的代码.

我们在 e1000.c 中为您提供的 e1000_init() 函数将 E1000 配置为读取要从 RAM 传输的数据包，并将接收到的数据包写入 RAM。这种技术称为 DMA，用于直接内存访问，指的是 E1000 硬件直接从 RAM 写入和读取数据包这一事实。

因为数据包的爆发可能比驱动程序处理它们的速度更快，所以 e1000_init() 为 E1000 提供了多个缓冲区，E1000 可以将数据包写入其中。 E1000 要求这些缓冲区由 RAM 中的“描述符”数组描述；每个描述符都包含 RAM 中的一个地址，E1000 可以在其中写入接收到的数据包。 struct rx_desc 描述描述符格式。描述符数组称为接收环或接收队列。从某种意义上说，它是一个圆环，当卡或驱动程序到达阵列的末端时，它会回到起点。 e1000_init() 使用 mbufalloc() 将 E1000 的 mbuf 数据包缓冲区分配给 DMA 。还有一个传输环，驱动程序将它希望 E1000 发送的数据包放入其中。 e1000_init() 将两个环配置为具有大小 RX_RING_SIZE 和 TX_RING_SIZE。

struct tx_desc
{
  uint64 addr;
  uint16 length;
  uint8 cso;
  uint8 cmd;
  uint8 status;
  uint8 css;
  uint16 special;
};
#define TX_RING_SIZE 16
static struct tx_desc tx_ring[TX_RING_SIZE] __attribute__((aligned(16)));
static struct mbuf \*tx_mbufs[TX_RING_SIZE];

// [E1000 3.2.3]
struct rx_desc
{
  uint64 addr;       /\* Address of the descriptor's data buffer \*/
  uint16 length;     /\* Length of data DMAed into data buffer \*/
  uint16 csum;       /\* Packet checksum \*/
  uint8 status;      /\* Descriptor status \*/
  uint8 errors;      /\* Descriptor Errors \*/
  uint16 special;
};

#define RX_RING_SIZE 16
static struct rx_desc rx_ring[RX_RING_SIZE] __attribute__((aligned(16)));
static struct mbuf \*rx_mbufs[RX_RING_SIZE];

struct mbuf {
  struct mbuf  \*next; // the next mbuf in the chain
  char         \*head; // the current start position of the buffer
  unsigned int len;   // the length of the buffer
  char         buf[MBUF_SIZE]; // the backing store
};

其中,tx_ring和tx_mbufs是一一对应的.

当 net.c 中的网络堆栈需要发送数据包时，它会调用 e1000_transmit() 并使用 mbuf 保存要发送的数据包。您的传输代码必须在 TX（传输）环的描述符中放置一个指向数据包数据的指针。 struct tx_desc 描述描述符格式。您需要确保每个 mbuf 最终都被释放，但只有在 E1000 完成数据包传输之后（E1000 设置描述符中的 E1000_TXD_STAT_DD 位来指示这一点）。

当 E1000 从以太网接收到每个数据包时，它首先将数据包 DMA 到下一个 RX（接收）环描述符指向的 mbuf，然后产生中断。您的 e1000_recv() 代码必须扫描 RX 环并通过调用 net_rx() 将每个新数据包的 mbuf 传送到网络堆栈（在 net.c 中）。然后，您需要分配一个新的 mbuf 并将其放入描述符中，以便当 E1000 再次到达 RX 环中的那个点时，它会找到一个新的缓冲区来 DMA 一个新的数据包。

除了在 RAM 中读取和写入描述符环之外，您的驱动程序还需要通过其内存映射控制寄存器与 E1000 交互，以检测接收到的数据包何时可用，并通知 E1000 驱动程序已填写一些 TX 描述符与要发送的数据包。全局变量 regs 持有指向 E1000 的第一个控制寄存器的指针；您的驱动程序可以通过将 regs 索引为数组来获取其他寄存器。您需要特别使用索引 E1000_RDT 和 E1000_TDT。

要测试您的驱动程序，请在一个窗口中运行 make server，在另一个窗口中运行 make qemu，然后在 xv6 中运行 nettests。 nettests 中的第一个测试尝试向主机操作系统发送一个 UDP 数据包，地址是使服务器运行的程序。如果您还没有完成实验，E1000 驱动程序实际上不会发送数据包，也不会发生任何事情。

完成实验后，E1000 驱动程序会发送数据包，qemu 会将数据包传送到您的主机，make server 会看到它，它会发送响应数据包，然后 E1000 驱动程序和 nettests 会看到响应数据包.然而，在主机发送回复之前，它会向 xv6 发送一个“ARP”请求包以查找其 48 位以太网地址，并期望 xv6 以 ARP 回复进行响应。一旦你完成了 E1000 驱动程序的工作，kernel/net.c 就会处理这个问题。如果一切顺利，nettests 将打印 testing ping: OK，并且 make server 将打印一条来自 xv6! 的消息。

提示

首先将打印语句添加到 e1000_transmit() 和 e1000_recv()，然后运行 make server 和（在 xv6 中）nettests。您应该从您的打印语句中看到 nettests 生成了对 e1000_transmit 的调用。

实现 e1000_transmit 的一些提示：

首先通过读取 E1000_TDT 控制寄存器向 E1000 询问它期待下一个数据包的 TX 环索引。
然后检查环是否溢出。如果 E1000_TDT 索引的描述符中没有设置 E1000_TXD_STAT_DD，则说明 E1000 还没有完成对应的上一个传输请求，因此返回错误。
否则，使用 mbuffree() 释放从该描述符传输的最后一个 mbuf（如果有的话）。
然后填写描述符。 m->head 指向包在内存中的内容，m->len 是包的长度。设置必要的 cmd 标志（查看 E1000 手册中的第 3.3 节）并隐藏指向 mbuf 的指针以供以后释放。
最后，通过将 E1000_TDT 模 TX_RING_SIZE 加一来更新环位置。
如果 e1000_transmit() 成功地将 mbuf 添加到环中，则返回 0。失败时（例如，没有可用于传输 mbuf 的描述符），返回 -1 以便调用者知道释放 mbuf。

实现 e1000_recv 的一些提示：

首先通过获取 E1000_RDT 控制寄存器并加一个模 RX_RING_SIZE，向 E1000 询问下一个等待接收的数据包（如果有）所在的环索引。
然后通过检查描述符状态部分中的 E1000_RXD_STAT_DD 位来检查新数据包是否可用。如果没有，请停止。
否则，将 mbuf 的 m->len 更新为描述符中报告的长度。使用 net_rx() 将 mbuf 传送到网络堆栈。
然后使用 mbufalloc() 分配一个新的 mbuf 来替换刚刚给 net_rx() 的那个。将其数据指针（m->head）编程到描述符中。将描述符的状态位清零。
最后，将 E1000_RDT 寄存器更新为最后处理的环描述符的索引。
e1000_init() 用 mbufs 初始化 RX 环，你会想看看它是如何做到的，也许还需要借用代码。
在某些时候，已经到达的数据包总数将超过环大小（16）；确保您的代码可以处理。
您将需要锁来应对 xv6 可能从多个进程使用 E1000 的可能性，或者当中断到达时可能在内核线程中使用 E1000。

int
e1000_transmit(struct mbuf \*m)
{
  //
  // Your code here.
  //
  // the mbuf contains an ethernet frame; program it into
  // the TX descriptor ring so that the e1000 sends it. Stash
  // a pointer so that it can be freed after sending.
  //
  acquire(&e1000_lock);
  //首先通过读取 E1000_TDT 控制寄存器向 E1000 询问它期待下一个数据包的 TX 环索引。
  uint reg_tdt = regs[E1000_TDT];
  //然后检查环是否溢出。如果 E1000_TDT 索引的描述符中没有设置 E1000_TXD_STAT_DD，则说明 E1000 还没有完成对应的上一个传输请求，因此返回错误。
  if((tx_ring[reg_tdt].status & E1000_TXD_STAT_DD) == 0){
      return -1;
  }
  //否则，使用 mbuffree() 释放从该描述符传输的最后一个 mbuf（如果有的话）。
  if(tx_mbufs[reg_tdt] != 0)
    mbuffree(tx_mbufs[reg_tdt]);

  //然后填写描述符。 m->head 指向包在内存中的内容，m->len 是包的长度。设置必要的 cmd 标志
  tx_mbufs[reg_tdt] = m;
  tx_ring[reg_tdt].length = m->len;
  tx_ring[reg_tdt].addr = (uint64)(m->head);
  tx_ring[reg_tdt].cmd = 9;

  //最后，通过将 E1000_TDT 模 TX_RING_SIZE 加一来更新环位置。
  regs[E1000_TDT] = (regs[E1000_TDT] + 1) % TX_RING_SIZE;
  release(&e1000_lock);
  return 0;
}

static void
e1000_recv(void)
{
  //
  // Your code here.
  //
  // Check for packets that have arrived from the e1000
  // Create and deliver an mbuf for each packet (using net_rx()).
  //首先通过获取 E1000_RDT 控制寄存器并加一个模 RX_RING_SIZE，向 E1000 询问下一个等待接收的数据包（如果有）所在的环索引。
  uint reg_rdt = regs[E1000_RDT];
  int i = (reg_rdt + 1)%RX_RING_SIZE;

  //然后通过检查描述符状态部分中的 E1000_RXD_STAT_DD 位来检查新数据包是否可用。如果没有，请停止。
  //否则，将 mbuf 的 m->len 更新为描述符中报告的长度。使用 net_rx() 将 mbuf 传送到网络堆栈。
   while(rx_ring[i].status & E1000_RXD_STAT_DD){
      rx_mbufs[i]->len = rx_ring[i].length;
      net_rx(rx_mbufs[i]);
      //然后使用 mbufalloc() 分配一个新的 mbuf 来替换刚刚给 net_rx() 的那个。将其数据指针（m->head）编程到描述符中。将描述符的状态位清零。
      if((rx_mbufs[i] = mbufalloc(0)) == 0)
          panic("e1000");
      rx_ring[i].addr = (uint64)rx_mbufs[i]->head;
      rx_ring[i].status = 0;
      i = (i + 1) % RX_RING_SIZE;
  }
  //最后，将 E1000_RDT 寄存器更新为最后处理的环描述符的索引。
  regs[E1000_RDT] = (i - 1) % RX_RING_SIZE;
}

8:Xv6 and Lock

Lab8_1 Memory Access.

在这个部分的测试中,三个进程频繁地调度kalloc和kfree.

对于每个锁，acquire 维护对该锁的调用计数，以及获取中的循环尝试但未能设置锁的次数。 kalloctest 调用一个系统调用，使内核打印 kmem 和 bcache 锁（这是本实验的重点）和 5 个最争用次数最多锁的计数。如果存在锁争用，获取循环迭代的次数将会很大。系统调用返回 kmem 和 bcache 锁的循环迭代次数的总和。

对于本实验，您必须使用具有多核的专用机器。如果您使用一台正在做其他事情的机器，那么 kalloctest 打印的计数将是无稽之谈。

kalloctest 中锁争用的根本原因是 kalloc() 有一个空闲列表，由一个锁保护。要消除锁争用，您必须重新设计内存分配器以不使用一个锁和列表。基本思想是为每个 CPU 维护一个空闲列表，每个列表都有自己的锁。不同 CPU 上的分配和释放可以并行运行，因为每个 CPU 将在不同的列表上运行。主要挑战将是处理一个 CPU 的空闲列表为空，但另一个 CPU 的列表有空闲内存的情况；在这种情况下，一个 CPU 必须“窃取”另一个 CPU 的空闲列表的一部分。窃取可能会引入锁争用，但希望这种情况很少见。(这个叫“负载均衡”)

你的工作是实现每个 CPU 的空闲列表(就是对于每个CPU的核维护一个空闲列表,这个列表就是kmem)，并在 CPU 的空闲列表为空时进行读取。您必须为所有以“kmem”开头的锁命名。也就是说，您应该为每个锁调用 initlock，并传递一个以“kmem”开头的名称。运行 kalloctest 以查看您的实现是否减少了锁争用。要检查它是否仍然可以分配所有内存，请运行 usertests sbrkmuch。您的输出将类似于下图所示，kmem 锁的争用总量大大减少，尽管具体数字会有所不同。确保 usertests 中的所有测试都通过。 make Grade 应该说 kalloctests 通过了。

1) 按照提示,更改内存块的结构.不是所有内存块都共享一个锁,是每个CPU都有一个独立的锁.

struct {
  struct spinlock lock;
  struct run \*freelist;
} kmem[NCPU];

2) 改为初始化所有锁.

void
kinit()
{
  for (int i = 0; i < NCPU; i++)
    initlock(&kmem[i].lock, "kmem");
  freerange(end, (void\*)PHYSTOP);
}

3) 获取CPU的id,在这个地方获取id的时候要关中断,防止因为中断分配给其他CPU来进行处理了.

1
2
3

push_off();
int id = cpuid();
pop_off();

4) 对于kalloc和kfree的锁获取和进入改成对于CPU为id的那个锁

acquire(&kmem.lock)->acquire(&kmem[id].lock)

5) 在if(r)的后面添加else,代表如果寻找失败,就到其他的核中获取.

else{
  for (int i = 0; i < NCPU; i++) {
    if (i == id) continue;
    acquire(&kmem[i].lock);
    r = kmem[i].freelist;
    if(r)
      kmem[i].freelist = r->next;
    release(&kmem[i].lock);
    if(r) break;
  }
}

9:Xv6 & File System

Lab 9_1 Large files

在这个实验中,你会拓展文件系统中文件的最大大小,其中一开始文件是12个直接连接块,1个一级索引块,一共16*16+12=268个块,这个时候我们要修改一下改成11个直接相连,1个一级索引块,1个二级索引块,一共256*256+256+11=65536+256+11个块.

其中xv6把文件系统映射到fs.img中,这个一共有二十万个块,其中70个保存块信息的meta块,剩下的都是数据.完成这个实验你需要关注磁盘 inode 的格式,这个由 fs.h 中的 struct dinode 定义。您对 NDIRECT、NINDIRECT、MAXFILE 和结构 dinode 的 addrs[] 元素特别感兴趣。查看 xv6 文本中的图 8.3 以了解标准 xv6 inode 的图表。
在磁盘上查找文件数据的代码在 fs.c 的 bmap() 中。看看它，确保你明白它在做什么。 bmap() 在读取和写入文件时都会被调用。写入时，bmap() 会根据需要分配新块来保存文件内容，并在需要时分配间接块来保存块地址。
bmap() 处理两种块号。 bn 参数是一个“逻辑块号”——文件中的块号，相对于文件的开头。 ip->addrs[] 中的块号和 bread() 的参数是磁盘块号。您可以将 bmap() 视为将文件的逻辑块号映射到磁盘块号。

修改 bmap() ，使其除了直接块和单间接块外，还实现双重间接块。你只需要 11 个直接块，而不是 12 个，就可以为新的双重间接块腾出空间；您不能更改磁盘 inode 的大小。 ip->addrs[] 的前 11 个元素应该是直接块；第 12 个应该是一个单独的间接块（就像现在的块一样）；第 13 个应该是你新的双重间接块。

1) 修改直接映射的数量.

1
2
3

#define NDIRECT 11#define NDIRECT 11
uint addrs[NDIRECT+2];
#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLE)//文件最大值也要改变

其中直接映射的数量由原来的12个改为11个.

2) 对应的file.h的inode结构体也要进行更改

struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+2];
};

3) 阅读bmap的代码: 0-NDIRECT-1 :直接 ,NDIRECT,NDIRECT+NINDIRECT-1:一级间接

//bn:the number the blocks.
  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;

  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    if((addr = ip->addrs[NDIRECT]) == 0)
      ip->addrs[NDIRECT] = addr = balloc(ip->dev);
    bp = bread(ip->dev, addr);
    a = (uint\*)bp->data;
    if((addr = a[bn]) == 0){
      a[bn] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

有个大前提,就是如果索引为0就代表这个磁盘为空,需要申请一个返回一个磁盘块号

首先第一部分,就是直接映射的部分,如果寻找的逻辑地址是在NDIRECT以内的,就可以直接访问磁盘块.

第二部分就是一级间接映射,首先先把一级映射的映射表找到,读出来,如果没有映射表就新建一个.映射表我们之前在操作系统学过就是一个int类型数组,这个时候我们就可以把映射表解释称int类型数组,然后根据索引值,也就是bn-NDIRECT来寻找,寻找就是寻找数组里面的东西.

4) 依葫芦画瓢作出二级索引.

bn -= NINDIRECT;

if(bn < NDOUBLE){
  if((addr = ip->addrs[NDIRECT+1]) == 0)
    ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
  bp = bread(ip->dev, addr);
  a = (uint\*)bp->data;
  int bn1 = bn / NINDIRECT,bn2 = bn % NINDIRECT;
  //first suoyin
  if((addr = a[bn1]) == 0){
   a[bn1] = addr = balloc(ip->dev);
   log_write(bp);
  }
  //second suoyin
  brelse(bp);
  bp=bread(ip->dev,addr);
  a=(uint\*)bp->data;
  if((addr=a[bn2])==0)
  {
      a[bn2]=addr=balloc(ip->dev);
      log_write(bp);
  }
  brelse(bp);
  return addr;
}

二级索引需要两个索引值,一个是除得来的结果,一个是%得来的结果,首先先读一次,获得一级索引表,做法和上面是一样的,接着再读,根据一级索引表得来的结果就是对应二级索引表的位置,所以说根据一级索引表的结果打开二级索引表,找到最后属于我们的索引值.

5) 完成索引的释放.

if(ip->addrs[NDIRECT+1]) {
  bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
  a = (uint\*)bp->data;
  for(j = 0; j < NINDIRECT; j++) {
    if(a[j]) {
      bp2 = bread(ip->dev, a[j]);
      a2 = (uint\*)bp2->data;
      for(i = 0; i < NINDIRECT; i++) {
        if(a2[i]) bfree(ip->dev, a2[i]);
      }
      brelse(bp2);
      bfree(ip->dev, a[j]);
      a[j] = 0;
    }
  }
  brelse(bp);
  bfree(ip->dev, ip->addrs[NDIRECT+1]);
  ip->addrs[NDIRECT] = 0;
}

就是先读取数组的第13项,构造一个二重循环,先进入到第一个一级索引的第一个二级索引陆续地释放所有的块.再进入到第一个一级索引的第二个二级索引…第一个一级索引的第256个二级索引….第256个二级索引的第256个一级索引…

Lab9_2 Symbolic links

您将实现 symlink(char *target, char *path) 系统调用，它会在 path 处创建一个新的符号链接，该链接引用由 target 命名的文件。

首先，为symlink创建一个新的系统调用号，在user/usys.pl，user/user.h中添加一个入口，在kernel/sysfile.c中实现一个空的sys_symlink。
将新文件类型 (T_SYMLINK) 添加到 kernel/stat.h 以表示符号链接。
向 kernel/fcntl.h 添加一个新标志 (O_NOFOLLOW)，可与 open 系统调用一起使用。请注意，传递给 open 的标志是使用按位 OR 运算符组合的，因此您的新标志不应与任何现有标志重叠。这将让您在将 user/symlinktest.c 添加到 Makefile 后编译它。
实现 symlink(target, path) 系统调用以在指向目标的路径上创建一个新的符号链接。请注意，系统调用成功时不需要存在目标。您将需要选择某个位置来存储符号链接的目标路径，例如，在 inode 的数据块中。 symlink 应该返回一个表示成功 (0) 或失败 (-1) 的整数，类似于链接和取消链接。
修改 open 系统调用以处理路径引用符号链接的情况。如果文件不存在，则打开必须失败。当进程在要打开的标志中指定 O_NOFOLLOW 时， open 应该打开符号链接（而不是跟随符号链接）。
如果链接文件也是符号链接，则必须递归地跟随它，直到到达非链接文件。如果链接形成循环，则必须返回错误代码。如果链接的深度达到某个阈值（例如，10），您可以通过返回错误代码来近似此值。
其他系统调用（例如，链接和取消链接）不得遵循符号链接；这些系统调用对符号链接本身进行操作。
对于本实验，您不必处理指向目录的符号链接。

1) 添加系统调用.(略)

2) 按照实验提示的信息,添加两个新的宏.(略)

3) 完成symlink系统调用.

首先第一点,我们发现,在sysfile.c的系统调用是需要提交事务的,我们也模仿这一点进行更改,处理的思路就是获取参数,创建一个新的inode,把符号连接的文件路径写进inode里面,然后提交即可.

uint64
sys_symlink(void)
{  
  char path[MAXPATH], target[MAXPATH];
  struct inode \*ip;
  // get parameter
  if(argstr(0, target, MAXPATH) < 0)
    return -1;
  if(argstr(1, path, MAXPATH) < 0)
    return -1;
  begin_op();
  // create a inode
  if((ip = create(path, T_SYMLINK, 0, 0)) == 0) {
    end_op();
    return -1;
  }
  // write the path of the file to the inode.
  if(writei(ip, 0, (uint64)target, 0, MAXPATH) < MAXPATH) {
    iunlockput(ip);
    end_op();
    return -1;
  }
  iunlockput(ip);
  end_op();
  return 0;
}