traps

最近封闭在家，没事干，只能刷题图开心，感觉MIT的lab刷起来真心是有意思，有挑战，难度很高，非常有思维挑战性，代码量倒是不是特别大。
特别alarm这个功能，思维确实比较牛逼，不过最重要的还算要看textbook，而不是忙着刷题，先把textbook看熟之后，再来刷题。
git repo

RISC-V assembly

这个lab主要事熟悉risc-v汇编语言的基本语法，跟x86的语法很不同的是，函数的参数不是压入栈，而是存放在寄存器中，所以我们在调试时需要注意这个问题，典型的X86的栈如下：

..............
arg[n-1]
arg[n-2]
arg[n-3]
...
arg[0]
..............
return address----------->frame pointer
..............   |
prev  frame      |
..............   |
saved register   |
..............   |
Local variable   |
............<----|
..
..
..............

risc-v的栈帧最大的区别就是函数的参数可能并不在栈上存储，可能在寄存器中存储。所以我觉得还算是非常容易理解的lab，采用risck gdb调试即可。

Backtrace

backtrace这一个lab可以说是为了能够深刻理解stack machine机制的设计的，每当调用函数时，首先需要将返回地址，之前的栈帧地址入栈，由于risck-v存储是以Little-Endian存储的，而栈空间的地址也是从高地址往低地址增长的，所以当前的栈帧的偏移8个字节即为return address，我们需要每次打印出返回地址，同时偏移16个字节则为前一个栈帧的地址，我们依次往前寻找，直到当前的栈帧的起始地址为PGROUNDUP(fp)，我们直到risc-v中每个栈空间的大小为4096byte，所以我们可以快速计算出栈顶和栈底的地址：

uint64 bottom = PGROUNDUP(fp);

每次我们可以读寄存器fp即可得到当前栈的栈帧指向的地址，代码实现其实非常简单，但是需要仔细思考其中的原理。

// add by mike meng
void backtrace(){
    uint64 fp = r_fp();
	uint64 bottom = PGROUNDUP(fp);
	uint64 address;
	char path[128];
	int line;

	printf("backtrace:\n");
	while(1){
		//printf("%p\n",*((uint64 *)(fp-8)));
		address = *((uint64 *)(fp-8));
	    memset(path,0,sizeof(path));
		ltaddr2line(address,path,&line);
		printf("pc = %p, %s:%d\n",address,path,line);
		fp = *((uint64 *)(fp-16));
	    if(fp >= bottom) break;
	}	
}

Alarm

这个alarm的lab还真心很难，想了很长时间没有想出来，后来看了好多参考书才有了一点眉目。首先需要了解CPU对于trap的处理原理，刚开始确实没有仔细阅读材料，导致浪费了很多时间。不过这门课程的视频课程讲的真心很好，感觉还是不能单看textbook。首先我们需要仔细理解xv6系统的trap的处理流程：

上图为标准的syscall的处理流程。基本处理流程如下，stvec寄存器中设置的trap处理的入口地址处，一旦有trap需要处理时，首先CPU会把PC跳转到stvec寄存器设置的入口地址处,一般我们我们需要处理usertrap和kernel trap.trap的处理流程基本相似：

kernel trap：kernel trap主要处理设备的特殊中断请求。

usertrap：user trap主要处理用户进程的trap处理。流程稍微复杂一点。最重要的两个函数为usertrap和usertrapret。我们仔细查找一下usertrap的入口函数，发现很难找到。实际上入口都是用汇编来完成，我们首先看一下uservec的具体内容用汇编实现的：

uservec:    
	#
        # trap.c sets stvec to point here, so
        # traps from user space start here,
        # in supervisor mode, but with a
        # user page table.
        #
        # sscratch points to where the process's p->trapframe is
        # mapped into user space, at TRAPFRAME.
        #
        
	    # swap a0 and sscratch
        # so that a0 is TRAPFRAME
        csrrw a0, sscratch, a0

        # 保存寄存器内容到TRAPFRAME所指向的地址上
        # save the user registers in TRAPFRAME
        sd ra, 40(a0)
        sd sp, 48(a0)
        sd gp, 56(a0)
        sd tp, 64(a0)
        sd t0, 72(a0)
        sd t1, 80(a0)
        sd t2, 88(a0)
        sd s0, 96(a0)
        sd s1, 104(a0)
        sd a1, 120(a0)
        sd a2, 128(a0)
        sd a3, 136(a0)
        sd a4, 144(a0)
        sd a5, 152(a0)
        sd a6, 160(a0)
        sd a7, 168(a0)
        sd s2, 176(a0)
        sd s3, 184(a0)
        sd s4, 192(a0)
        sd s5, 200(a0)
        sd s6, 208(a0)
        sd s7, 216(a0)
        sd s8, 224(a0)
        sd s9, 232(a0)
        sd s10, 240(a0)
        sd s11, 248(a0)
        sd t3, 256(a0)
        sd t4, 264(a0)
        sd t5, 272(a0)
        sd t6, 280(a0)

	# save the user a0 in p->trapframe->a0
        # 将a0用户的寄存器保存到frame上
        csrr t0, sscratch
        sd t0, 112(a0)

        # restore kernel stack pointer from p->trapframe->kernel_sp
        ld sp, 8(a0)

        # make tp hold the current hartid, from p->trapframe->kernel_hartid
        ld tp, 32(a0)

        # 将usertrap的入口地址写给a0
        # load the address of usertrap(), p->trapframe->kernel_trap
        ld t0, 16(a0)

        # restore kernel page table from p->trapframe->kernel_satp
        # 将kernel的pagetable写入到satp寄存器，并刷新页表
        ld t1, 0(a0)
        csrw satp, t1
        sfence.vma zero, zero

        # a0 is no longer valid, since the kernel page
        # table does not specially map p->tf.

        # 跳转到usertrap()
        # jump to usertrap(), which does not return
        jr t0

大致就是保存寄存器到tramfram上,然后kstack的地址写入sp寄存器，将hartid标记位写入到寄存器中，将kernel的页表写入到satp寄存器中，然后跳转到usertrap中，usertrap函数以下：

void
usertrap(void)
{
  int which_dev = 0;
  // 获取当前模式，是否为 user trap
  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  // interrupts process will be set to kernelvec.
  // 将trap的入口设置为kernel trap
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  // 保存当前的pc值
  p->trapframe->epc = r_sepc();

  //if the interrupts is system call
  // 判断当前的trap类型
  if(r_scause() == 8){// 系统调用
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    // 如果为系统调用，则将恢复的PC指向它的下一个指令
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    //open interrrupt
    // 关闭 trap，打开中断处理
    intr_on();

	// system call
    // 处理系统调用
    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    // 异常trap,则直接关闭当前进程
    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;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2){
  	if(!p->alarmworking && p->alarminterval > 0){
	  p->alarmtick++;
	  if(p->alarmtick == p->alarminterval){
		//p->alarmhandler();
		//p->alarmretaddr = p->trapframe->epc;
		// we set the epc point  to the alarm handler
		// when we leave from the trap process,we will get to the alarm handler
		memmove(&p->alarmtrap,p->trapframe,sizeof(struct trapframe));
		p->trapframe->epc = (uint64)p->alarmhandler;
	    p->alarmtick = 0;
		p->alarmworking = 1;
	  }
    }
    yield();
  }
  
  // 恢复
  usertrapret();
}

userret：我们从userret的相关代码如下：

userret:
        # userret(TRAPFRAME, pagetable)
        # switch from kernel to user.
        # usertrapret() calls here.
        # a0: TRAPFRAME, in user page table.
        # a1: user page table, for satp.

        # switch to the user page table.
        csrw satp, a1
        sfence.vma zero, zero

        # put the saved user a0 in sscratch, so we
        # can swap it with our a0 (TRAPFRAME) in the last step.
        ld t0, 112(a0)
        csrw sscratch, t0

        # restore all but a0 from TRAPFRAME
        ld ra, 40(a0)
        ld sp, 48(a0)
        ld gp, 56(a0)
        ld tp, 64(a0)
        ld t0, 72(a0)
        ld t1, 80(a0)
        ld t2, 88(a0)
        ld s0, 96(a0)
        ld s1, 104(a0)
        ld a1, 120(a0)
        ld a2, 128(a0)
        ld a3, 136(a0)
        ld a4, 144(a0)
        ld a5, 152(a0)
        ld a6, 160(a0)
        ld a7, 168(a0)
        ld s2, 176(a0)
        ld s3, 184(a0)
        ld s4, 192(a0)
        ld s5, 200(a0)
        ld s6, 208(a0)
        ld s7, 216(a0)
        ld s8, 224(a0)
        ld s9, 232(a0)
        ld s10, 240(a0)
        ld s11, 248(a0)
        ld t3, 256(a0)
        ld t4, 264(a0)
        ld t5, 272(a0)
        ld t6, 280(a0)

	# restore user a0, and save TRAPFRAME in sscratch
        csrrw a0, sscratch, a0
        
        # return to user mode and user pc.
        # usertrapret() set up sstatus and sepc.
        sret

处理流程为首先将用户的页表切换到寄存器中，然后从trapframe中取出已经保存的值，将其恢复到寄存器中，然后将trapframe进行恢复到默认值，将PC的值恢复到之前的值，指令将会继续之前的PC的值进行执行。

我们实际在处理sigalarm时，首先需要将sigalarm和sigalarmret函数处理加入到system call中，然后在处理usertrap时，首先我们需要处理来自timer的trap,此时我们可以将trap恢复后的pc指向alarmhandler函数，我们运行时，即可发现可以运行handler函数，但是运行完成后，发现出了不少问题。我们仔细思考就可以发现，因为PC指向的指令地址改变后，我们可以仔细分析一下，函数执行时，我们看到当前栈帧返回时会返回正确的地址，因为此时RA寄存器存放的为正确的return address.但是periodic函数在执行过程中可能会将其中的寄存器污染，所以会出现alarm打印逻辑出错。所以我们在执行handler时，必须要将相关的寄存器进行保存，保存完成后再执行handler，执行完成handler后，我们再恢复寄存器，同时恢复pc.

periodic()
{
   0:	1141                	addi	sp,sp,-16
   2:	e406                	sd	ra,8(sp)
   4:	e022                	sd	s0,0(sp)
   6:	0800                	addi	s0,sp,16
  count = count + 1;
   8:	00001797          	auipc	a5,0x1
   c:	d407a783          	lw	a5,-704(a5) # d48 <count>
  10:	2785                	addiw	a5,a5,1
  12:	00001717          	auipc	a4,0x1
  16:	d2f72b23          	sw	a5,-714(a4) # d48 <count>
  printf("alarm!\n");
  1a:	00001517          	auipc	a0,0x1
  1e:	b6650513          	addi	a0,a0,-1178 # b80 <malloc+0xea>
  22:	00001097          	auipc	ra,0x1
  26:	9b6080e7          	jalr	-1610(ra) # 9d8 <printf>
  sigreturn();
  2a:	00000097          	auipc	ra,0x0
  2e:	6c6080e7          	jalr	1734(ra) # 6f0 <sigreturn>
}

刚开始我的想法是再申请一个物理页，然后用汇编将所有的寄存器的值，都保存到这个新申请的物理页中，待到函数执行完成后，我们再利用系统调用，将该物理页中保存的值再重新加载到寄存器中，刚开始想着是模仿userret和uservec的汇编代码来模仿实现。后来感觉太复杂了，看了提示之后，在进入alarm handler之前所有的寄存器其实都已经全部保存在tramp fram中，我们可以申请新的tramp fram结构，在usertrapret恢复寄存器时，暂时不恢复寄存器的值，只是将PC的值进行跳转。在alarmreturn时，此时我们再将已经保存的tramp fram中的寄存器和PC的值全部切换回去即可。

alarm时，我们将handler和interval进行指定保存。

uint64 sys_sigalarm(){
	int ticks;
    uint64 ptr;
    struct proc * p = myproc();	
	
	if(argint(0, &ticks) < 0)
    	return -1;
	if(argaddr(1,&ptr) < 0)
		return -1;
	
  
	acquire(&p->lock);
	p->alarmworking = 0;
	p->alarminterval = ticks;
	p->alarmhandler = (func)ptr;
	release(&p->lock);
	
	return 0;
}

执行trap时，如果当前的ticks达到alarminterval时，则我们首先将PC的返回值替换为handler的入口地址，同时将当前trap frame的值进行保存。

// give up the CPU if this is a timer interrupt.
  if(which_dev == 2){
  	if(!p->alarmworking && p->alarminterval > 0){
	  p->alarmtick++;
	  if(p->alarmtick == p->alarminterval){
		//p->alarmhandler();
		//p->alarmretaddr = p->trapframe->epc;
		// we set the epc point  to the alarm handler
		// when we leave from the trap process,we will get to the alarm handler
		memmove(&p->alarmtrap,p->trapframe,sizeof(struct trapframe));
		p->trapframe->epc = (uint64)p->alarmhandler;
	    p->alarmtick = 0;
		p->alarmworking = 1;
	  }
    }
	
    yield();
  }

执行sigreturn时，则我们将保存的tramfram切换回去即可。

uint64 sys_sigreturn(){
	struct proc * p = myproc();
	if(p->alarmworking){
		memmove(p->trapframe,&p->alarmtrap,sizeof(struct trapframe));
	    p->alarmworking = 0;
	}
    return 0;
}

Optional challenge

Print the names of the functions and line numbers in backtrace() instead of numerical addresses

按照要求对backtrace进行扩展，使得其能够打印出相应的文件和行号，刚开始拿到这个以为很简单，但是实际上实现起来还是挺复杂。主要查找的信息来源于addr2line的实现，在github上找了一堆实现addr2line的代码，后来发现一个c++还凑合，就拿过来读了一下，然后通过查找debug_line的具体参数定义，然后找到dwarf 3.0的标准，对战标准和代码把相关的功能全部重新移植到xv6上，虽然代码写的很烂，但是凑合还能用吧，其中debug的时间还挺长。具体实现原理如下：

改写makefile,把生成kernel的elf文件做到文件系统中，然后系统运行后，通过用户进程调用函数读取和解析elf文件，这里最大的坑是用户进程未初始化时，我直接用内核读取文件，发现会panic,后来仔细检查了很多遍，发现因为在内核文件的读取都会加载进程的文件锁，而这时用户进行还未初始化，这时如果去调用mypoc函数就会出现指针跑飞的问题。解决办法只有等待用户进行调度起来后，可以单独起一个用户进程读取和解析elf文件。
系统起来后，在内核空间中从文件系统读取elf文件，找到.debug_line这个section，然后按照dwarf 3.0的标准来解析header和opcode，具体可以Google相关的标准，标准本身还是挺复杂的，具体实现时参考这个github的代码：https://github.com/evmar/maddr ，里面解析opcode时有不少小bug，关键时刻还算看标准靠谱。
解析完成后，将解析生成的matrix放入到数组中，然后我们对line table按照地址从小到大进行排序，我们解析的line table中也可以看到每行代码可能会对应多个instruction，我们直到pc每次递增的。每次进行查询时，我们在line table表中查找小于等于等于给定地址p的第一个元素，然后返回查询结果即可，查询结果包含了文件名和行号，返回给trace即可。
熬了几天夜，终于把功能基本实现了，总体来说还算非常蛋疼的功能。

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 公开课学习

← 【MIT6.S081】 lab5 lazy alloaction 【MIT6.S081】 lab2 systemcalls →

扫描二维码，分享此文章

【MIT6.S081】 lab4 traps

traps

RISC-V assembly

Backtrace

Alarm

Optional challenge