MIT6.1810 Lab简记

1
2
3

高地址 -> | 调用者栈帧 | 
          | 当前栈帧   | <- 栈顶（esp/sp）
低地址

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

User Program           Kernel/Handler
↓
1. 准备参数：
   - 系统调用号写入 a7
   - 参数写入 a0, a1, ...
2. 执行 ecall
   ↓
→ 3. CPU 切换到更高特权级
   ↓
→ 4. 保存上下文：
     - PC（程序计数器）存入 sepc
     - 异常原因存入 scause
     - 当前状态存入 sstatus
   ↓
→ 5. 跳转到 stvec 寄存器指向的陷阱处理程序
   ↓
6. 内核处理系统调用
   ↓
7. 执行 sret 返回用户程序

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

#include <unistd.h>
int main() {
    char msg[] = "Hello\n";
    // 等价于汇编中的 li a7, 64
    syscall(SYS_write, 1, msg, 6);  // SYS_write=64
    return 0;
}
long syscall(long num, ...) {
    register long a7 asm("a7") = num;  // 强制将 num 存入 a7
    register long a0 asm("a0");        // 返回值通过 a0 接收
    asm volatile (
        "ecall"
        : "=r"(a0)
        : "r"(a7), "r"(a0), "r"(a1), "r"(a2)  // 参数依次存入 a0-a2
        : "memory"
    );
    return a0;
}

1
2

$ addr2line -e my_program 0x401152
> /path/to/my_program.c:123

1
2
3

$ script qemu_output.log  # 指定日志文件名（默认是 typescript）
$ make qemu 所有输出（包括内核日志、调试信息）将被实时记录到 qemu_output.log
$ exit

1
2
3
4
5
6

// enable device interrupts
static inline void
intr_on()
{
  w_sstatus(r_sstatus() | SSTATUS_SIE);
}

1
2

#define BUCKETS_NUM 13
#define HASH_SEATCH(blockno) (blockno % BUCKETS_NUM)  // find the bucket

1
2
3
4
5
6
7
8

struct {
  // new buffer cache
  struct spinlock lock;                     // global lock for move buf
  struct buf buf[NBUF];                     // buffer cache less than NBUF

  struct buf buckets[BUCKETS_NUM];          // use buckets to store and get cache
  struct spinlock bucketlock[BUCKETS_NUM];  // bucket lock instead of the global lock
} bcache;

 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

void
binit(void)
{
  struct buf *b;

  // init global lock
  initlock(&bcache.lock, "bcache");

  // Each bucket starts with a double-ended circular linked list
  // Set head'refcnt to 1 to indicate that it cannot be moved.
  for (int i = 0; i < BUCKETS_NUM; i++) {
    initlock(&bcache.bucketlock[i], "bcachelock");
    bcache.buckets[i].next = &bcache.buckets[i];
    bcache.buckets[i].prev = &bcache.buckets[i];
    bcache.buckets[i].refcnt = 1;
  }

  // Initialize each buffer cache and store in buckets
  for (b = bcache.buf; b < bcache.buf + NBUF; b++) {
    initsleeplock(&b->lock, "buffer");
    b->next = bcache.buckets[0].next;
    b->prev = &bcache.buckets[0];
    bcache.buckets[0].next->prev = b;
    bcache.buckets[0].next = b;
  }
}

 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
52
53
54

static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  // search the bucket without global lock
  if ((b = bucketsearch(dev, blockno)) != 0)
    return b;

  acquire(&bcache.lock);
  // search the bucket with global lock
  if ((b = bucketsearch(dev, blockno)) != 0) {
    release(&bcache.lock);
    return b;
  }

  // find a buffer to move
  int new = HASH_SEATCH(blockno);
  for (int i = 0; i < BUCKETS_NUM; i++) {
    // start from the key
    int old = (new + i) % BUCKETS_NUM;
    b = bcache.buckets[old].prev;

    // search current bucket for buf
    while (b != &bcache.buckets[old]) {
      if (b->refcnt == 0) {
        // get both the old and the new bucket lock to move
        acquire(&bcache.bucketlock[old]);
        if (old != new) acquire(&bcache.bucketlock[new]);
        if ((b = bufmove(b, old, new)) != 0) {
          b->dev = dev;
          b->blockno = blockno;
          b->valid = 0;
          b->refcnt = 1;
          if (old != new) release(&bcache.bucketlock[new]); 
          acquiresleep(&b->lock);
          release(&bcache.bucketlock[old]);
          release(&bcache.lock);
          return b;
        }

        // can't reach here
        if (old != new) release(&bcache.bucketlock[new]); 
        release(&bcache.bucketlock[old]);
        release(&bcache.lock);
        panic("bget error");
      }
      b = b->prev;
    }
  }

  // can't reach here
  release(&bcache.lock);
  panic("bget: no buffers");
}

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

// Find the cache in the bucket corresponding to blockno
static struct buf*
bucketsearch(uint dev, uint blockno)
{
  struct buf *b;
  int key = HASH_SEATCH(blockno);

  // Accessing the bucket requires the corresponding lock
  acquire(&bcache.bucketlock[key]);
  for (b = bcache.buckets[key].next; b != &bcache.buckets[key]; b = b->next) {
    if (b->dev == dev && b->blockno == blockno) {
      b->refcnt++;
      release(&bcache.bucketlock[key]);
      acquiresleep(&b->lock);
      return b;
    }
  }
  release(&bcache.bucketlock[key]);
  return 0;
}

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

// move the buf from the old bucket to the new bucket
static struct buf*
bufmove(struct buf *b, int old, int new) {
  if (old == new) return b;

  // Put the buffer in the prev of new bucket head
  b->prev->next = b->next;
  b->next->prev = b->prev;
  b->next = &bcache.buckets[new];
  b->prev = bcache.buckets[new].prev;
  bcache.buckets[new].prev->next = b;
  bcache.buckets[new].prev = b;
  return b;
}

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

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  int key = HASH_SEATCH(b->blockno);
  acquire(&bcache.bucketlock[key]);
  b->refcnt--;
  if (b->refcnt == 0) {
    // Put the buffer in the next of new bucket head for quicker search
    struct buf *head = &bcache.buckets[key];
    b->prev->next = b->next;
    b->next->prev = b->prev;
    b->next = head->next;
    head->next->prev = b;
    head->next = b;
    b->prev = head;
  }
  release(&bcache.bucketlock[key]);
}

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

void
bpin(struct buf *b) {
  int key = HASH_SEATCH(b->blockno);
  acquire(&bcache.bucketlock[key]);
  b->refcnt++;
  release(&bcache.bucketlock[key]);
}

void
bunpin(struct buf *b) {
  int key = HASH_SEATCH(b->blockno);
  acquire(&bcache.bucketlock[key]);
  b->refcnt--;
  release(&bcache.bucketlock[key]);
}

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

#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDBINDIRECT ((BSIZE / sizeof(uint)) * (BSIZE / sizeof(uint)))
#define MAXFILE (NDIRECT + NINDIRECT + NDBINDIRECT)
// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+2];   // Data block addresses
};

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

bn -= NINDIRECT;

if (bn < NDBINDIRECT) {
    if ((addr = ip->addrs[NDIRECT+1]) == 0) {
      addr = balloc(ip->dev);
      if (addr == 0) return 0;
      ip->addrs[NDIRECT+1] = addr;
    }
    for (int level = 2; level > 0; level--) {
      int n = (level == 2 ? bn / NINDIRECT : bn % NINDIRECT);
      bp = bread(ip->dev, addr);
      a = (uint *)bp->data;
      if ((addr = a[n]) == 0) {
        addr = balloc(ip->dev);
        if (addr) {
          a[n] = addr;
          log_write(bp);
        } else return 0;
      }
      brelse(bp);
    }
    return addr;
}
panic("bmap: out of range");

 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

uint64
sys_symlink(void)
{
  char path[MAXPATH];
  char target[MAXPATH];
  struct inode *ip;
  int n, r;

  if ((n = argstr(0, target, MAXPATH)) < 0)
    return -1;
  if ((n = argstr(1, path, MAXPATH)) < 0)
    return -1;

  begin_op();

  ip = create(path, T_SYMLINK, 0, 0);

  if (ip == 0) {
    end_op();
    return -1;
  }

  if ((r = writei(ip, 0, (uint64)target, 0, strlen(target)+1)) < strlen(target)+1) {
    iunlockput(ip);
    end_op();
    return -1;
  }
  
  iunlockput(ip);
  end_op();
  return 0;
}

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

int depth = 0;
while (ip->type == T_SYMLINK && !(omode & O_NOFOLLOW)) {
    int r = 0;
    char addr[MAXPATH];
    if ((r = readi(ip, 0, (uint64)addr, 0, MAXPATH)) <= 0) {
      iunlockput(ip);
      end_op();
      return -1; 
    }
    iunlockput(ip);
    if ((ip = namei(addr)) == 0) {
      end_op();
      return -1;
    }
    ilock(ip);
    if (++depth > 9) {
      iunlockput(ip);
      end_op();
      return -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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

uint64
sys_mmap(void)
{
  int index;
  int fd;
  uint64 va;
  struct VMA vma;
  struct proc *p = myproc();

  // get args
  argaddr(0, &vma.addr);
  argint(1, &vma.len);
  vma.len = PGROUNDUP(vma.len);
  argint(2, &vma.prot);
  argint(3, &vma.flags);
  if (argfd(4, &fd, &vma.f) < 0)
    return -1;
  argint(5, &vma.offset);

  // check prot and flags
  // 如果设置为MAP_SHARED需要检查该文件是否能够读入
  if (!(vma.flags & MAP_PRIVATE) && ((!vma.f->readable && (vma.prot & PROT_READ)) 
    || (!vma.f->writable && (vma.prot & PROT_WRITE))))
    return -1;

  // find a vma to store
  for (index = 0; index < NVMA; index++)
    if (!p->vmas[index].len) break;
  if (index == NVMA) panic("sys_mmap: no VMA to free");
  p->vmas[index] = vma;
  // 增加文件的ref计数
  filedup(p->vmas[index].f);

  // find a va space to map
  for (va = VMABASE; va > 0; va -= PGSIZE) {
    if ((walkaddr(p->pagetable, va)) != 0) continue;

    // 检查再往下的内存是否被map
    uint64 vaend = va;
    for (; va > vaend - vma.len; va -= PGSIZE)
      if ((walkaddr(p->pagetable, va)) != 0) break;

    // 检查这里的内存是否是未被加载的vma
    if (va == vaend - vma.len && conflictdet(p->vmas, va + PGSIZE, vma.len)) {
      p->vmas[index].addr = va + PGSIZE;
      p->vmas[index].base = va + PGSIZE;    // base需要用于之后写入文件
      break;
    }
  }

  if (p->vmas[index].addr) return p->vmas[index].addr;
  else return -1;
}

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

int
conflictdet(struct VMA *vmas, uint64 va, int len)
{
  for (int i = 0; i < NVMA; i++) {
    if (vmas[i].len) {
      uint64 left = vmas[i].addr;
      uint64 right = vmas[i].addr + vmas[i].len;
      if (va < right && va+len >= left)
        return i;
    }
  }
  return -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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

int
pagefaulthandler(uint64 fault_addr)
{
  int n;
  uint64 va;
  uint64 pa;
  char *mem;
  struct VMA *vma;
  struct proc *p = myproc();

  // 检查fault_addr是否位于vma内存区域
  int index;
  if ((index = conflictdet(p->vmas, fault_addr, 0)) == -1) {
    printf("page fault: addr not assigned\n");
    return -1;
  }
  vma = &p->vmas[index];
  va = PGROUNDDOWN(fault_addr);
  
  // 如果已被映射但仍触发page fault可能是尝试写入不可写页面
  if ((pa = walkaddr(p->pagetable, fault_addr)) != 0) 
    if (!(PA2PTE(pa) & PTE_W))
      return -1;

  if ((mem = kalloc()) == 0) {
    printf("page fault: Page Fault: no free memory\n");
    return -1;
  }
  memset(mem, 0, PGSIZE);

  // 进行file的操作需要持有锁
  // 将file的内存读入物理内存
  ilock(vma->f->ip);
  if ((n = readi(vma->f->ip, 0, (uint64)mem, vma->offset + va - vma->addr, PGSIZE)) < 0) {
    printf("page fault: read file fail\n");
    iunlock(vma->f->ip);
    return -1;
  }
  iunlock(vma->f->ip);
  
  // 将va映射到pa
  // prot与PTE的权限存在`<<1`的关系
  if (mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_U | (vma->prot << 1)) != 0) {
    kfree(mem);
    printf("Page Fault: mmap map fault\n");
    return -1;
  }
  return 0;
}

 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

uint64 
sys_munmap(void)
{
  int length;
  int writelen;
  int index;
  uint64 addr;
  uint64 writeaddr;
  struct VMA *vma;
  struct inode *ip;
  struct proc *p = myproc();

  argaddr(0, &addr);
  argint(1, &length);
  if ((index = conflictdet(p->vmas, addr, 0)) == -1)
    panic("munmap: not assigned addr");
  vma = &p->vmas[index];
  ip = vma->f->ip;

  // 检查写入的长度和地址是否会导致写入多余内存(分配时向上PGROUNDUP，存在部分内存不应被使用)
  writelen = addr - vma->base + vma->offset + length > ip->size ?
  (ip->size - (addr - vma->base + vma->offset)) : length;
  if (writelen < 0) writelen = 0;
  writeaddr = vma->offset + addr - vma->base > ip->size ? 
  (vma->offset) : vma->offset + addr - vma->base;

  if (vma->flags & MAP_SHARED) {
    // 在fs_system call 前调用begin_op
    begin_op();
    ilock(ip);
    if ((writei(ip, 1, addr, writeaddr, writelen)) < 0) {
      iunlock(ip);
      end_op();
      printf("writelen:%d\n", writelen);
      panic("mumap: write back error");
    }
    iunlock(ip);
    end_op();
  }

  vmaunmap(p->pagetable, addr, PGROUNDUP(length) / PGSIZE, 1);
  vma->len -= PGROUNDUP(length);
  if (vma->len) {
    if (addr == vma->addr)
      vma->addr += PGROUNDUP(length);
  } else
    fileclose(vma->f);
  return 0;
}

1
2
3
4
5
6
7

for (i = 0; i < NVMA; i++) {
    vma = &p->vmas[i];
    if (vma->len) {
      np->vmas[i] = *vma;
      filedup(vma->f);
    }
}

1
2
3
4
5
6
7

for (; vma <= &p->vmas[NVMA-1]; vma++) {
    if (vma->len) {
      vmaunmap(p->pagetable, vma->addr, PGROUNDUP(vma->len) / PGSIZE, 1);
      fileclose(vma->f);
      vma->len = 0;
    }
}