[开发工具]6.s081笔记（上）

环境配置

虚拟机环境为ubuntu20.04。
基本的git clone等参考官方网站即可，也参考了环境配置1。c debug采用了gdb-multiarch，参考环境配置2。参考了环境配置3实现了vscode中调试。

关于在vscode中打断点的问题，在kernel文件下打断点直接打就可以使用，但是在user文件下则需要先加载该文件的符号表：

这样可以在该文件下打断点，否则会出现can not access memory问题。

一个未解决的问题是，如果我在.gdbinit中没有注释掉

target remote 127.0.0.1:26000

则如环境配置4所言，由于在vscode中已经设置了target-remote模式，则会导致建立重复连接，但注释掉该行代码后则导致在ubuntu虚拟机中无法在终端进行gdb调试。

有时，由于编译出现bug（一个比较坑的点是，定义未被使用的变量也会导致error），导致运行未能正常退出，则会报错资源正被占用，write lock~~（没有截图）。根据环境配置5使用了fuser -k指令消除相关进程。此外，还遇到过环境配置6等各种小问题，不过都顺利解决了。

每次使用git checkout切换分支时需要重新配置launch.json，见环境配置7

实验要求见官网实验要求。

由于本人水平有限，基本是跟着大神博客做的，自己想很难从头弄清楚该咋整，只能跟着做完后记录一下反向推导为啥这么做~~。如果有我理解的不对的地方请大佬们不吝赐教。

LAB 1 utils

sleep&pingpong

两个实验都比较简单，sleep.c调用了syscall的sleep，具体系统调用过程见lab2。
pingpong.c建立一对管道，值得注意的是pipe§会自动给数组的两个元素赋值（3和4），从p[1]写向p[0]。

primes

这个实验一开始完全不知道想让我们干啥，看了官网链接后知道想让我们实现这个东西：

在大神博客中，他是对上图每个矩形建立了两个子进程，也利用了管道读端必须等到写端退出才会结束读（也是官方要求）。但我觉得没有必要创建子进程

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

void func(int *input, int num)
{
    if(num==1)
    {
        printf("prime %d\n", *input);
		return;
    }
    int i;
    int p[2];
    int tp=*input;
    int tmp;
    printf("prime %d\n", *input);
    int cnt=0;
    char buffer[4];
    pipe(p);//关闭写端，不可少
   for(i = 0; i < num; i++){
        tmp = *(input + i);
		write(p[1], (char *)(&tmp), 4);
   }
   close(p[1]);
    while(read(p[0],buffer,4)!=0)
    {
        tmp=*((int *)buffer);
        if(tmp%tp)
        {
            *input=tmp;
            cnt++;
            input+=1;
        }
    }
    func(input-cnt,cnt);
    exit(0);
}

int main()
{
    int i;
    int nums[36];
    for(i=2;i<=35;i++)
    {
        nums[i-2]=i;
    }
    func(nums,34);
    return 0;
}

不过，上面的代码就和没用管道没啥本质区别了。

这题似乎和指导书上第16页底部所说的那个sh的例子有点相似，但指导书的意思是，如果不fork而是直接执行runcmd(p->left)（写端），由于runcmd(p->left)会调用exec指令，导致父进程直接exit退出。尽管可以限制runcmd调用exec时不执行exit来解决这个问题，但那样会导致编码变得复杂。
如果右端不fork的话，则会导致sleep 10|echo hi这样的指令直接执行右端，但是我无法理解的是，首先，即使左右进程都创建fork，我们是无法控制他们执行的先后顺序的，如果说写端要等待读端关闭的话，那应该也适用于不为右端创建子进程的情况。当然，我并不知道优化一个fork的价值有多大，原文的代码应该是最不容易出错的一种。

find

就是ls.c的递归版，值得注意的是dirent结构体的用法。

先看看它的定义：

// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

虽然我目前还没看到文件系统，但也可以猜到每个dirent代表一个文件描述结构体。

while(read(fd, &de, sizeof(de)) == sizeof(de)){
	//printf("de.name:%s, de.inum:%d\n", de.name, de.inum);
	if(de.inum <= 1 || strcmp(de.name, ".")==0 || strcmp(de.name, "..")==0)
		continue;				
	//memmove(p, de.name, strlen(de.name));
    strcpy(p, de.name);
    p[strlen(de.name)] = 0;
    find(buf, findName);
}

所以，每次读入一个sizeof(dirent)即可。

最后不得不说一下grep.c，写的太优美了。虽然只是linux的grep的简化版（没有实现在子目录中查找），但是match部分写的很好：

int matchhere(char*, char*);
int matchstar(int, char*, char*);

int
match(char *re, char *text)//re是范式，返回1则匹配成功
{
  if(re[0] == '^')//"^xxx"表示以xxx开始的行
    return matchhere(re+1, text);
  do{  // must look at empty string
    if(matchhere(re, text))
      return 1;
  }while(*text++ != '\0');
  return 0;
}

// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)//
{
  if(re[0] == '\0')
    return 1;
  if(re[1] == '*')
    return matchstar(re[0], re+2, text);
  if(re[0] == '$' && re[1] == '\0')//“xxx$”代表以xxx结尾的行
    return *text == '\0';
  if(*text!='\0' && (re[0]=='.' || re[0]==*text))
    return matchhere(re+1, text+1);
  return 0;
}

// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)//专门处理*，"c*"代表0个或多个连续c
{
  do{  // a * matches zero or more instances
    if(matchhere(re, text))
      return 1;
  }while(*text!='\0' && (*text++==c || c=='.'));//避免c*cxxx这种情况
  return 0;
}

grep的表达范式见grep表达式。
虽然时间复杂度很爆炸，但代码风格很值得学习。

xargs

在大神博客的基础上做了一些小小的改进

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

int main(int argc, char *argv[]){
    int i;
    int j=0;
    int len;
    char *lin[32];
    char block[33];
    char *p;
    for(i=1;i<argc;i++)
    {
        lin[j++]=argv[i];
    }
    while((len=read(0,block,sizeof(block)-1))>0)
    {
        p=block;
        for(i=0;i<len;i++)
        {
            if(block[i]==' ')
            {
                block[i]=0;
                lin[j++]=p;
                p=&block[i+1];
            }
            else if(block[i]=='\n')
            {
                block[i]=0;
                lin[j++]=p;
                p=&block[i+1];
                lin[j]=0; //示意参数结束
                j=argc-1; //去除argv[0]
                if(fork()==0)
                {
                    exec(argv[1],lin);
                }
                wait(0);
            }
        }
    }
    exit(0);
}

这里值得注意的是指针的使用：

忘了从哪篇博客截的图了，侵删。

LAB 2

继续跟着大神博客做。

这里其实如果先看了trap可能做起来更得心应手一些。

trap的过程是，首先执行上图用户虚地址空间中的trampoline，这是一段代码，主要是把31个用户寄存器的值保存到trapframe，然后切换页表，调到kernel/trap.c里的usertrap函数，这个函数里会判断是哪种trap，若果是syscall则调用kernel/syscall.c里的syscall()函数。

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(strlen(p->mask)>0&&p->mask[num]=='1')
    {
      printf("%d: syscall %s -> %d\n",p->pid,syscall_names[num],p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

可以看到，实质上就是先调用指定的中断处理函数，然后把p->trapframe->a0修改为中断处理函数的地址。

这里的一个问题是，trace 32 grep hello README虽然看起来是一条指令，但实际上我认为它是先进行了trace 32，之后在进行了grep。后来，查看user/trace.c也也证实了我的猜想。

关于输出结果的解释：

$ trace 32 grep hello README
3: syscall read -> 1023
3: syscall read -> 966
3: syscall read -> 70
3: syscall read -> 0

我们要知道，是在grep.c里面调用了read：

 while((n = read(fd, buf+m, sizeof(buf)-m-1)) > 0)

所以每次的返回值就是读了多少字节。

我很想去思考一下trace 2 usertests forkforkfork的输出结果，但是看到usertests.c有2000多行代码，于是只好放弃了。

System call sysinfo没啥好说的，正常添加一个系统调用就行了。比较有意思的反而是sysinfotest.c。如何检测系统内还有多少空闲块？一个方法是统计freelist链表里面的元素数量，另一种就是直接while(sbrk(PGSIZE))，看看能最多申请到多少空间。

LAB 3

继续跟着大神博客

这个实验困扰我的地方在于，它到底要实现一个什么东西。做完后我才弄明白，是要给每个进程实现一个内核页表，这个页表的0~PLIC（0xc000000）为该进程的虚地址空间，其他地址为内核的虚地址（就是物理地址）。所以这里在用户内核空间不能映射CLINT，一个虚拟块不能同时映射两个物理块（panic(remap)）。

关于为什么内核虚地址就是物理地址，因为是先调用kvminit()建立的内核页表，然后再调用kvminithart()设置satp寄存器，开启虚拟页表。

这样的好处是什么呢，原先想从用户空间拷贝数据到内核空间，因为传进来的指针是用户空间下的虚拟地址，需要用walk函数模仿MMU将其转化为内核空间地址。但是直接使用用户内核空间（我自己起的名字）的话，则是在同一个空间（及satp相同）里copy数据了，把全部的地址转换工作交给MMU就好了。

既然明确了要做什么，下一步就是怎么做的问题。首先，一个进程的用户内核空间里只要有自己的内核栈就行了，内核栈的工作原理是，用户态切换进内核态时向里面压栈，切换回用户态时出栈，所以在用户态时栈是空的，所以这里不能有其他用户进程的内核栈。

然后就是修改scheduler，需要先弄明白scheduler是怎么工作的，这里参考参考博客，简而言之，就是context存放11个特权寄存器，每个进程有一个context，每个cpu核也有一个context，swtch修改了ra寄存器，那么ret就会返回对应的进程。

添加的这三行代码如下：

w_satp(MAKE_SATP(p->kerneltbl));
sfence_vma();
swtch(&c->context, &p->context);//原来就有
kvminithart();

首先将空间切换到用户内核空间，然后清空tlb（这是切换satp后的必要步骤），值得注意的是，从用户内核空间返回scheduler的入口是在swtch处，也就是再次调用scheduler时执行的第一行代码就是调用kvminithart()将空间切换到内核空间。

A kernel page table per process这个实验之后，我们成功建立了用户内核空间。但是我们并没有把用户进程虚地址里面的内容加进来，这需要在fork()时就将用户虚地址空间里的内容复制一份。此时进入系统调用后，实质已经是在用户内核空间里运行了，所以只需要在fork()、exec()和userinit()里把虚地址空间里面的页表复制一份即可。

这次实验的usertests我倒看了看，本质是在main里面定义一个函数指针数组，在for循环里面循环检测。

LAB 4

前面几个小问题的详细解答见参考博客Q4由于没学过riscv汇编，这个知识缺陷困扰了我很久。Q5则体现了小端存储的特性。

第一个实验没啥，记住函数调用栈就行了：

test0: invoke handler本身没有什么难度，跟着实验指导做就行了。需要弄明白的是各函数的调用过程。首先要搞明白控制寄存器：

sepc控制sret的返回地址，我们在usertrap里将p->trapframe->epc指向periodic函数，然后在usertrapret里将其赋值给sepc（这里值得注意的是，p->trapframe->epc实质相当于sepc的一个备份，避免在trap里发生trap修改sepc）。在periodic函数里调用了sigreturn系统调用，目前它里面只有return 0，也就是啥都没干，又返回了periodic。这时，periodic会返回ra指向的地址。
但是ra里面依然保存着之前test0()中的值,这个值是多少呢？

查看alarmtest.asm，发现正好是

下面做一个小测试，如果把write(2,’.’,1)改成i=i（因为write修改了ra）会发生什么？

这应证了一些猜想，另外这个编译器生成的中间代码也很神奇。

关于如何在user目录下的文件打断点，首先参考参考博客调整文件夹，然后参考博客加载符号表。

为什么sigalarm(0, 0)就啥也不干了? 因为这个时候，p->internal ==0， p->spend 永远不会等于p->internal，上面p->trapframe那句永远不会执行。（来自参考博客）

那么这样还有什么问题呢？首先是如果中断处理函数执行时间过长，也会被中断（毕竟它是运行在用户空间），所以加了个waitReturn。
，这就是test2测试的东西。另外从上面的小测试可以看到，ra的值是固定的，关于test1，想象一个场景：在执行i++之后到*j += 1之前，如果发生时钟中断，那么中断处理程序必定会返回0x234，即foo调用结束后的地址，导致j没加上1。

此外，由于periodic修改了一大堆寄存器的值，我们有没有将他们压栈进行保护，所以可能导致一些寄存器的值在periodic之后被改动。

在sys_sigreturn里面加入switchtrapframe(myProc->trapframe,myProc->transave)的意义在于，不仅还原了发生时钟中断以前的寄存器，而且在usertrapret时，会把之前的epc寄存器的值赋给sepc（这里的一个问题是，要不要像if(r_scause() == 8)那样对p->trapframe->epc+4，但观察到原先which_dev==2的时候就没有+4），这样在sret时，不再返回periodic函数，而是直接跳到时钟中断前的位置，这样就保证了i与j相等。

进行验证：

运行alarmtest，没有执行最后一行printf。

LAB 5

这个算是比较简单的一个实验，继续跟着大神博客做。

mappage并不分配页，walk分配页但它只分配三级页表的页。

另外，xv6把heap放在上面或许是为了更方便地用p->sz表示虚拟空间大小？

被坑的一个点是，在trap.c的usertrap()里面，我以为p->trapframe->sp应该是p->trapframe->kernel_sp，规范上界不得与内核栈冲突，但实际上xv6已经规定好了上界：MAXVA。这个判断只是因为sbrk(n)在n为负数的时候与用户栈重合，如果没有这条判断则会在usertests里的stacktest里报panic(“remap”)。

另外，这个实验不要想的太复杂，它就是一个在heap上的操作。之前我还考虑在copyin()里面page全为0是否合理，但实际上在没写入数据之前，就是全为0的，如果已经写入数据了，这个页早就在copyout的时候分配好了。

其他的一些细节参考博客

LAB 6

这个实验是跟着这篇大佬博客做的，当然，大神博客也写的很好。

当时犯迷糊的一个点：r_scause() == 15不仅仅可以在PTE_V不存在时触发，也可以在PTE_W没有权限的时候触发。另外采取COW的块并不妨碍copyin（内核从块中读），只需要修改copout（写入块），而trap和copyout里面对内存空间不够的处理方式是不同的。

此外，trap里面是处理用户空间没有写权限，而copyout是在内核空间，它不可能调用usertrap()。

此外，如果是在mappage的时候对计数数组+1，则初始的时候计数数组的元素全为1，因为在kvminit()里面就已经遍历一遍所有内存块了。在kalloc里面+1则初始全为0。

LAB 7

还是跟着大神博客。

第一次自己动手上锁。 首先，需要弄明白P生产者消费者模型中的sleep and wakeup问题（实验指导书7.5）。这里不少地方参考了大佬博客

需要弄明白scheduler是怎么工作的。进程在sched()前需要先确保获取自身进程锁，然后release掉除了进程锁以外的其他锁（避免造成死锁），acquire锁时需要关中断（这里应该是整个os关中断，因为sched里面会传递mycpu()->interna），然后从sched()里面的swtch跳转到scheduler()里的swtch（通过更改ra实现，同时也通过更换sp切换了栈），然后在scheduler里面很快释放进程锁，开始调度。

上面加粗的那句话也解释了为什么进程状态为sleep时不可以持有任何锁，因为wakeup会请求相同的锁造成死锁（实验指导书P73）。

acquire关中断的意义在于避免在中断处理程序里申请锁造成死锁（见10.8）。为什么中断处理程序里要加锁？因为要解决实验指导书5.3里面提到的那些并发问题。在scheduler里面swtch之后，会返回到之前进程在sched里调用swtch的地方。可以看到在yiled里也立刻释放进程锁。

自旋锁是xv6里面最简单的一种锁，弄明白__sync_lock_test_and_set(&lk->locked, 1) 是原子操作，__sync_synchronize()可以避免编译器将store或load指令跨过它移动，其它的看注释就很好懂。

关于锁的粒度：个人认为就是限制了多少指令，粗粒度锁更安全，但也导致了性能损失，无法利用多核CPU的优势。多核CPU是并行编程复杂的根源。

但自旋锁的问题是，对于一个长等待，我们不希望使用自旋锁，因为它会阻塞中断，然后持续占用cpu直到获取锁（阻塞中断意味着不能进行上下文切换让出cpu）。所以我们希望一个进程如果发现它等待的条件不满足时陷入睡眠，让出cpu，而让使得等待条件满足的进程唤醒睡眠进程。

进程锁的作用见：

关于lostwakeup的原因，@passenger12234 的博客写的很清楚了，这里直接搬运一下：

关于如何修复：

另外值得注意的是，获取两个锁时的获取顺序需要控制，这样也可以避免死锁。

回到实验。

switching between threads如果看明白了进程的调度过程，其实很好理解。

Using threads这个实质上就是一个多链表插入的模型（类似多个freelist），为每个链表弄一个线程锁：

for(int i=0;i<NBUCKET;i++)
  {
    pthread_mutex_init(&lk[i],NULL);
  }

加锁也只要对插入的代码段加锁就行：

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;
  }
  if(e){
    // update the existing key.
    e->value = value;
  } else {
    // the new is new.
    pthread_mutex_lock(&lk[i]);//加锁
    insert(key, value, &table[i], table[i]);
    pthread_mutex_unlock(&lk[i]);//解锁
  }
}

Barrier实验很好理解。

一些废话

个人以为，智商、勤奋、有人带，三者得其二则可以较快上手一门课程，只可惜我只有勤奋指标能勉强及格。在我比较熟的人中，zxy应该是唯一一个智商和勤奋都达标的人，他要是来学6.s081的话，大概能领悟到比我更深一层的东西吧。也有人悟性绰绰有余，不过得哄着去深入研究一个东西。

有人带，至少可以在前期不至于想我这样拿头去砸坑。lab4我为了弄明白那几个函数到底跳转到哪，做的时候花了一天，写这篇总结的时候又花了一天。如果是悟性高一个层次或者有人点拨的人，大抵是不会这么费劲的吧。