mit6.1810 fall 2024 project2

引言

有关project2的实验，对应课程网址如下6.1810 / Fall 2024

system call tracing(moderate)

前置知识

本实验使用位图mask记录需要追踪的系统调用，如果对应位置为1，就会监听对应的系统调用

xv6下系统调用的流程（后续的每一个操作，几乎都可以在源码层面进行体现，需细心品读.c或者.S文件）

用户态下调用系统调用函数，系统调用参数会被放到a0 - a6的寄存器当中
执行user/usys.S中对应系统调用函数的汇编指令
- 将系统调用号放在寄存器a7当中
- 调用ecall指令，ecall会进行的硬件操作
  - 保存中断使能状态，
  - 关中断，
  - 切换到内核态，
  - 跳转执行执行kernel/trampoline.S中的uservec中（陷阱处理入口）的指令

kernel/trampoline.S中uservec的执行

先保存a0寄存器 (csrw sscratch, a0) ，让a0寄存器可以空出来保存TRAPFRAME
a0放TRAPFRAME (li a0, TRAPFRAME)，TRAPFRAME是proc中的一个结构体，保存用户寄存器状态
暂存用户态寄存器 (sd ra, 40(a0) ……)
将原来的a0也保存到TRAPFRAME当中

csrr t0, sscratch sd t0, 112(a0)

后续的一些过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# initialize 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)

# load the address of usertrap(), from p->trapframe->kernel_trap
ld t0, 16(a0)

# fetch the kernel page table address, from p->trapframe->kernel_satp.
ld t1, 0(a0)

再往后

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


# wait for any previous memory operations to complete, so that
# they use the user page table.

# 主要是刷新TLB
sfence.vma zero, zero  # 确保 CPU 已完成所有未完成的用户态访存操作，防止切换页表后丢失写入。

# install the kernel page table.
csrw satp, t1

# flush now-stale user entries from the TLB.
sfence.vma zero, zero  # 清除 TLB 中缓存的用户页表项，避免后续内核代码使用错误的地址翻译。

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

执行kernel/trap.c中的usertrap()函数
- 检查是否之前是用户态，陷阱向量更改为内核陷阱向量，(当前内核态，下次陷阱走内核陷阱向量)
- 保存用户的pc程序计数器
- 陷入原因是系统调用，将原来用户态pc值 + “1”
- 开中断
- 调用kernel/syscall.c中的syscall()
kernel/syscall.c中syscall()的调用过程
- 获取系统调用号执行对应操作，将结果放在a0寄存器当中
- p->trapframe->a0 = syscalls[num]()
kernel/syscall.c中syscalls[]数组成员执行，从a0等寄存器中获取系统调用的参数，参数传递到对应的操作当中
执行完成后调用usertrapret函数
- 关中断
- 陷阱向量改为用户的陷阱向量trampoline_uservec
- 初始化陷阱帧，保存内核相关信息
- 配置返回状态
- 挑战到trampoline.S中的userret

tramploline.S中的userret的执行

切换用户页表

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

恢复寄存器

1
2
3
4
5
6
7
8


li a0, TRAPFRAME

# restore all but a0 from TRAPFRAME
ld ra, 40(a0)
......

# restore user a0
ld a0, 112(a0)

返回用户态和复原用户pc

具体实现

了解了系统调用的过程，我们要做的就是根据trace_mask来追踪每一次的系统调用过程

首先需要在proc中定义trace_mask，用于之后的使用
调用trace系统调用的时候，将参数传递给trace_mask，这一步在kernel/sysproc.c中实现sys_trace()来完成
上面两步实现了通过trace系统调用在proc中添加trace_mask
下面还要实现通过系统调用号打印对应的系统调用
kernel/syscall.c中syscall可以获得系统调用号，与trace_mask判断本次系统调用是否被监听了，如果监听了，就进行打印。
注意对于fork的调用，也需要父进程的p->trace_mask传给子进程的p->trace_mask，否则子进程监听就不对了
最后实现trace程序
- trace程序接受trace_mask和监听命令作为参数
- 先调用trace系统调用初始化trace_mask
- 再通过exec执行后面的命令及看监听指定系统调用
kernel/proc.h中struct proc的修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


// Per-process state
struct proc {
  struct spinlock lock;

  int trace_mask;       // 用于记录程序需要追踪的系统调用

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

kernel/sysproc.c中的sys_trace()函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


uint64
sys_trace(void)
{
  int mask;
  argint(0, &mask); // 系统调用传参
  struct proc *p = myproc();
  p->trace_mask = mask;
  
  return 0;
}

kernel/proc.c中fork()的修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


int
fork(void)
{
  int i, pid;
  struct proc *np;
  struct proc *p = myproc();

  // Allocate process.
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  np->sz = p->sz;

  // copy saved user registers.
  *(np->trapframe) = *(p->trapframe);

  // copy trace_mask 用于实现trace
  np->trace_mask = p->trace_mask;

  // Cause fork to return 0 in the child.
  np->trapframe->a0 = 0;

  // 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);

  safestrcpy(np->name, p->name, sizeof(p->name));

  pid = np->pid;

  release(&np->lock);

  acquire(&wait_lock);
  np->parent = p;
  release(&wait_lock);

  acquire(&np->lock);
  np->state = RUNNABLE;
  release(&np->lock);

  return pid;
}

syscall.h添加trace系统调用号

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// 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

kernel/syscall.c中syscall的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


char* name_index[] = {		// 自定义的系统调用号和系统调用名的映射
  [SYS_fork]    "fork",
  [SYS_exit]    "exit",
  [SYS_wait]    "wait",
  [SYS_pipe]    "pipe",
  [SYS_read]    "read",
  [SYS_kill]    "kill",
  [SYS_exec]    "exec",
  [SYS_fstat]   "fstat",
  [SYS_chdir]   "chdir",
  [SYS_dup]     "dup",
  [SYS_getpid]  "getpid",
  [SYS_sbrk]    "sbrk",
  [SYS_sleep]   "sleep",
  [SYS_uptime]  "uptime",
  [SYS_open]    "open",
  [SYS_write]   "write",
  [SYS_mknod]   "mknod",
  [SYS_unlink]  "unlink",
  [SYS_link]    "link",
  [SYS_mkdir]   "mkdir",
  [SYS_close]   "close",
  [SYS_trace]   "trace",
};

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

  num = p->trapframe->a7;
  // num = * (int *) 0;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    // Use num to lookup the system call function for num, call it,
    // and store its return value in p->trapframe->a0
    p->trapframe->a0 = syscalls[num]();
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }

  if (((1u << num) & p->trace_mask) != 0) {
    printf("%d: syscall %s -> %ld\n", p->pid, name_index[num], p->trapframe->a0);
  }
}

user/trace.c的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

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];
  }
  nargv[argc-2] = 0;
  exec(nargv[0], nargv);
  printf("trace: exec failed\n");
  exit(0);
}

attack xv6(moderate)

前置知识(具体的分析，完成下一章project再来看可能会更清晰)

比较源码进行分析，效果更好，建议完成下一章再来看，需要对kfree，kalloc，mappages等函数有一定的理解

fork时分配物理页面的过程(当前没有写时复制，见kernel/proc.c中的fork())

np = allocproc()

(p->trapframe = (struct trapframe *)kalloc() 分配了一页作为trapframe，不同进程有各自独立的trapframe

p->pagetable = proc_pagetable(p) 创建第一个页表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// 创建第一个页表的时候，就要去映射TRAMPOLINE和TRAPFRAME
if(mappages(pagetable, TRAMPOLINE, PGSIZE,
  (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
}

// TRAMPOLINE存放了处理陷入的汇编代码，空间是内核启动时预先分配好的，物理地址是固定的TRAMPOLINE，这里将用户页表进行映射即可

// map the trapframe page just below the trampoline page, for
// trampoline.S.
if(mappages(pagetable, TRAPFRAME, PGSIZE,
  (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
}

// 这两个页面再虚拟地址最顶端相邻两个页，三级页表只需要1个就可以进行映射

xv6系统使用三级页表结构(可以看xv6book中的页表章节进行了解)，所以这里分配了3个页面

uvmcopy(p->pagetable, np->pagetable, p->sz)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) {
    ...

    for(i = 0; i < sz; i += szinc){	// sz是用户空间已经分配的空间大小，这里遍历整个用户空间进行复制
        szinc = PGSIZE;
        szinc = PGSIZE;
        if((pte = walk(old, i, 0)) == 0)	// 找到用户空间的页表项
            panic("uvmcopy: pte should exist");
        if((*pte & PTE_V) == 0)
            panic("uvmcopy: page not present");
        pa = PTE2PA(*pte);					// 获取对应的物理地址
        flags = PTE_FLAGS(*pte);
        if((mem = kalloc()) == 0)			// 分配新的物理地址
            goto err;
        memmove(mem, (char*)pa, PGSIZE);	// 将就地址内容拷贝到新地址
        if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){	// new为新页表，会创建新页表
              kfree(mem);
              goto err;
        }
    }    

	...
}

也就是说，原来父进程有多少用户空间的页面以及页表的页面，子进程就会创建多少页面

至此，fork分配内存的环节就结束了

exec调用执行物理页面的变化过程 (见kernel/exec.c)

(pagetable = proc_pagetable(p))，fork中分析过了，分配了三个页面映射TRAMPOLINE和TRAPFRAME
- exec执行一个新程序，不要分配新的TRAPFRAME吗？exec虽然是执行新程序，但是是在当前程序上执行，使用当前程序分配的TRAPFRAME即可，不需要新分配。换言之，exec不会改变struct proc *p = myproc()，其只会替换用户空间。
- 注: p以及里面相关地址不会改变，但是内容可能会因为运行新程序而改变。

加载elf中文件的load

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// Load program into memory.
for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
    if(readi(ip, 0, (uint64)&ph, off, sizeof(ph)) != sizeof(ph))
      goto bad;
    if(ph.type != ELF_PROG_LOAD)
      continue;
    if(ph.memsz < ph.filesz)
      goto bad;
    if(ph.vaddr + ph.memsz < ph.vaddr)
      goto bad;
    if(ph.vaddr % PGSIZE != 0)
      goto bad;
    uint64 sz1;
    if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz, flags2perm(ph.flags))) == 0)
      goto bad;
    sz = sz1;
    if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
      goto bad;
}

exec要执行什么程序，就去看对应程序elf文件中有多少个需要load的页面
uvmalloc创建用户页面的同时，还会进行映射，创建页表。所以elf文件里面需要load的页面少于512个就会再创建二级和三级页表，也就是2个页面
512是根据每个页表页表项个数得到的，看xv6book三级页表结构，为2^9

分配用户栈以及一个保护页面，总计USERSTACK+1个页面，在xv6中#define USERSTACK 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// Allocate some pages at the next page boundary.
  // Make the first inaccessible as a stack guard.
  // Use the rest as the user stack.
  sz = PGROUNDUP(sz);
  uint64 sz1;

	// 只要用户空间的页面没有超过512个，就不会增加新的页表
  if((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK+1)*PGSIZE, PTE_W)) == 0)
    goto bad;
  sz = sz1;
  uvmclear(pagetable, sz-(USERSTACK+1)*PGSIZE);
  sp = sz;
  stackbase = sp - USERSTACK*PGSIZE;

proc_freepagetable(oldpagetable, oldsz); 释放旧的页表和用户地址空间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);	// 这里不删除物理空间，只删除页表
  uvmunmap(pagetable, TRAPFRAME, 1, 0);		// 同上

  // 先解除了TRAMPOLINE和TRAPFRAME映射，这样下面就不会把上面两个物理地址一同删除
  // 因为上面两个物理地址是用户页表和内核页表共同使用的
  uvmfree(pagetable, sz);		// 里面uvmunmap最后一个参数是1,说明删除了物理地址空间（都是用户空间）
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;
  int sz;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

    // 根据页表遍历删除，说明用户空间的删除是虚拟地址从低到高依次删除
  for(a = va; a < va + npages*PGSIZE; a += sz){	
    sz = PGSIZE;
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0) {
      printf("va=%ld pte=%ld\n", a, *pte);
      panic("uvmunmap: not mapped");
    }
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

1
2
3
4
5
6
7


void
uvmfree(pagetable_t pagetable, uint64 sz)
{
  if(sz > 0)
    uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);		//这里删除了物理地址空间
  freewalk(pagetable);
}

至此exec页面变化过程就结束了

xv6底层的内存管理
- 通过链表来进行管理，分配的页表从链表头取出来
- 释放的页面放回到链表头

程序结束后何时回收用户地址空间

在exit函数中没有找到回收用户地址空间的代码，但是会p->state = ZOMBIE;通知父进程进行回收

在wait函数中有这样一段代码freeproc(pp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);		// 先删除trapframe的物理地址空间，这里不回收页表
  p->trapframe = 0;
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);	// 再删除用户地址空间和页表，这个函数在exec分析中有
  p->pagetable = 0;
  p->sz = 0;
  p->pid = 0;
  p->parent = 0;
  p->name[0] = 0;
  p->chan = 0;
  p->killed = 0;
  p->xstate = 0;
  p->state = UNUSED;
}

也就是说，如果由父进程，用户内存的回收是通过父进程的wait函数来完成的，先回收trapframe的物理内存(不会回收页表)，再从低地址到高地址依次进行回收用户空间页面和页表

具体实现

页面分配涉及elf文件load，attacktest, secret 和 attack的elf文件中都需要加载多少load展示出来
- 在xv6目录中执行readelf -l user/_attacktest
- readelf -l user/_secret
- readelf -l user/_attack
- 可以看出attacktest, secret, attack的elf文件需要加载的页面都是两个
attacktest分析（结合前置知识的分析）
- attacktest的用户页面是通过exec来分配出来的，总共有四个(两个load,一个用户栈，一个guard)，同时需要三级页表来映射
- fork为子进程分配空间
  - 三级页表映射到trapframe(一级页表，二级页表，三级页表，trapframe)总共4个页面
  - 复制attacktest的用户页面+二级页表+三级页表进行映射，总共6个页面
  - 前排提示，上面的三级页表和用户页面+两个页表，总共9个页面，后面执行exec会被释放。trapframe不会被释放
- 子进程执行exec(secret)
  - 新建页面映射trapframe(新一级页表，二级页表，三级页表)，总共3个页面
  - 加载secret的elf文件，总共2个页面，加载同时还要创建二级页表，三级页表映射用户空间(2个页面)
  - 用户栈和guard，总共2个页面
  - 释放上面旧的9个页面，释放9个页面
  - 分配32个页面，在第10个页面上写上secret，申请32个页面
- 子进程结束，父进程wait，依次释放trapframe页面(1页),用户页面(4 + 32页)，页表页面(5页)
- 此时空闲链表如下所示
  - （头，旧的页表页面5页）-> (用户页面32页，secret在第23页上) -> 用户页面(4页，elf的load,用户栈，guard) -> (trapframe) -> …….
  - secret在空闲链表从头开始数第28个页面上
- 执行pipe(fds)
  - 追踪pipe系统调用的执行流程kernel/sysfile.c中的uint64 sys_pipe(void)函数，我们可以发现pipe执行了pipealloc函数
  - pipealloc中执行了kalloc，又申请了一个页面。
  - secret在空闲链表从头开始数第27个页面上
- fork为子进程分配空间，和上面一样，总共10个页面
- exec(attack)分配空间，和上面一样，到guard页申请结束总共申请了9个
- 释放fork中的9个页面,与上面申请的9个页面相抵消
- 27-10 = 17，因此再分配17个页面就可以找到secret
attack.c代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

int
main(int argc, char *argv[])
{
  // your code here.  you should write the secret to fd 2 using write
  // (e.g., write(2, secret, 8)
  char secret[8] = {0};

  char* end = sbrk(PGSIZE*32);
  end = end + 16 * PGSIZE;
  memcpy(secret, end + 32, 8);

  write(2, secret, 8);
  
  exit(1);
}

至此，attack的分析就结束了