作业地址

Preliminaries

根据提示在 Makefile 做对应的修改

 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
UPROGS=\
  _alarmtest\
  _cat\
  _echo\
  _forktest\
  _grep\
  _init\
  _kill\
  _ln\
  _ls\
  _mkdir\
  _rm\
  _sh\
  _stressfs\
  _usertests\
  _wc\
  _zombie\
  _date\
  _uthread\
  _big

ifndef CPUS
CPUS := 1
endif

QEMUEXTRA = -snapshot
QEMUOPTS = -drive file=fs.img,index=1,media=disk,format=raw -drive file=xv6.img,index=0,media=disk,format=raw -smp $(CPUS) -m 512 $(QEMUEXTRA)

同时修改 param.h 中 FSSIZE

1
#define FSSIZE       20000  // size of file system in blocks

What to Look At

xv6 中每一个文件均有对应的 inode,如下图

Figure 1: inode 结构图

Figure 1: inode 结构图

对应代码如下

1
2
3
4
5
6
7
8
9
// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

一个 inode 有 12 个 直接指向硬盘文件块的 direct 指针,还有一个指向另一个包含 128 个指向其他文件块的 indirect 指针,所以一个 inode 可以指向 12+128=140 个文件

Your Job

根据要求把 bmap() 修改成支持 double-indirec blocks

 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
55
56
57
58
59
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a, *b;
  uint indirect_idx, indirect_idx2;
  struct buf *bp, *bp2;

  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 ifnecessary.
    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;
  }
  bn -= NINDIRECT;

  // double-indirect blocks
  if (bn < NINDIRECT*NINDIRECT) {
    if((addr = ip->addrs[NDIRECT + 1]) == 0)
      ip->addrs[NDIRECT + 1] = addr = balloc(ip->dev);

    bp = bread(ip->dev, addr);
    a = (uint *) bp->data;
    indirect_idx = bn / NINDIRECT;

    if ((addr = a[indirect_idx]) == 0) {
      a[indirect_idx] = addr = balloc(ip->dev);
      log_write(bp);
    }

    bp2 = bread(ip->dev, addr);
    b = (uint *) bp2->data;
    indirect_idx2 = bn % NINDIRECT;

    if((addr = b[indirect_idx2]) == 0) {
      b[indirect_idx2] = addr = balloc(ip->dev);
      log_write(bp2);
    }

    brelse(bp2);
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}

同时对 fs.h 中的一些参数进行修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define MAXFILE (NDIRECT + NINDIRECT + NINDIRECT * NINDIRECT)

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEV only)
  short minor;          // Minor device number (T_DEV 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
$ big
.....................................................................................................................................................................
wrote 16523 sectors
done; ok