File system

来到指导书最高点！太美丽了xv6。哎呀那不文件系统吗（

这里是自底向上讲起的。之后可以看看hit网课的自顶向下。

image-20230121160555370

Overview

image-20230121160641718

The disk layer reads and writes blocks on an virtio hard drive.

The buffer cache layer caches disk blocks and synchronizes access to them, making sure that only one kernel process at a time can modify the data stored in any particular block.

The logging layer allows higher layers to wrap updates to several blocks in a transaction, and ensures that the blocks are updated atomically in the face of crashes (i.e., all of them are updated or none). 【日志记录层允许更高层将更新包装到一个事务中的多个块，并确保在崩溃时以原子方式更新块（即，所有块都更新或不更新）。可以类比一下数据库的那个概念。】

The inode layer provides individual files, each represented as an inode with a unique i-number and some blocks holding the file’s data.

The directory layer implements each directory as a special kind of inode whose content is a sequence of directory entries, each of which contains a file’s name and i-number.

The pathname layer provides hierarchical path names like /usr/rtm/xv6/fs.c, and resolves them with recursive lookup.

The file descriptor layer abstracts many Unix resources (e.g., pipes, devices, fifiles, etc.) using the file system interface, simplifying the lives of application programmers.

image-20230121162324747

The file system must have a plan for where it stores inodes and content blocks on the disk. To do so, xv6 divides the disk into several sections, as Figure 8.2 shows.

The file system does not use block 0 (it holds the boot sector).

Block 1 is called the superblock; it contains metadata about the file system (the file system size in blocks, the number of data blocks, the number of inodes, and the number of blocks in the log). The superblock is filled in by a separate program, called mkfs, which builds an initial file system.

Blocks starting at 2 hold the log.

After the log are the inodes, with multiple inodes per block.

After those come bitmap blocks tracking which data blocks are in use. 【应该是用来标识每个块是否空闲的吧】

The remaining blocks are data blocks; each is either marked free in the bitmap block, or holds content for a file or directory【要么空闲要么是文件或目录】.

Buffer cache

The buffer cache has two jobs:

  1. synchronize access to disk blocks to ensure that only one copy of a block is in memory and that only one kernel thread at a time uses that copy;
  2. cache popular blocks so that they don’t need to be re-read from the slow disk.

The code is in bio.c.

Buffer cache中保存磁盘块的缓冲区数量固定，这意味着如果文件系统请求还未存放在缓存中的块，Buffer cache必须回收当前保存其他块内容的缓冲区。Buffer cache为新块回收最近使用最少的缓冲区。这样做的原因是认为最近使用最少的缓冲区是最不可能近期再次使用的缓冲区。

image-20230124151719288

数据结构定义

1
2
3
4
5
6
7
8
9
10
11
struct buf {
  int valid;   // has data been read from disk?缓冲区是否包含块的副本
  int disk;    // does disk "own" buf?缓冲区内容是否已交给磁盘
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  uchar data[BSIZE];
};

这应该代表着一个磁盘块。

1
2
3
4
5
6
7
8
9
struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;

大概buf数组里存储着所有buf的内容。buf本身通过最近使用排序的双向链表连接，head是链表的头。

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// called by main.c
void
binit(void)
{
  struct buf *b;

  initlock(&bcache.lock, "bcache");

  // Create linked list of buffers
  // 把b插在head之后
  bcache.head.prev = &bcache.head;
  bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    initsleeplock(&b->lock, "buffer");
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
}

上层接口

The main interface exported by the buffer cache consists of bread and bwrite.

The buffer cache uses a per-buffer sleep-lock to ensure concurrent security.

bread

bread obtains a buf containing a copy of a block which can be read or modified in memory.

依据给定设备号和给定扇区号寻找cache的buf。返回的buf是locked的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  // 获取buf块
  b = bget(dev, blockno);
  if(!b->valid) {
    // 说明cache未命中，需要从磁盘读入
    virtio_disk_rw(b, 0);
    b->valid = 1;
  }
  return b;
}

bwrite

writes a modified buffer to the appropriate block on the disk

1
2
3
4
5
6
7
8
9
10
// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  // 必须持有b的锁
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  // 写入磁盘
  virtio_disk_rw(b, 1);
}

brelse

A kernel thread must release a buffer by calling brelse when it is done with it.

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
// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&bcache.lock);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    // 移动到头结点和头结点的下一个结点之间的位置
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }

  release(&bcache.lock);
}

具体细节

bget

用于获取cache中是否存在block。如果不存在，则新申请一个buf，并把该buf以上锁状态返回

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
// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  acquire(&bcache.lock);

  // Is the block already cached?
  // 这个循环条件很有意思，充分用到了双向链表的特性
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      // 引用数增加
      b->refcnt++;
      release(&bcache.lock);
      // 锁定
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  // 从尾部开始遍历，确实就是最少使用的了
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    // 如果该buf空闲
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      // 仅是新建了一个buf，还未从磁盘读取对应磁盘块的副本，因而设valid为0以供上层函数调用处理
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.lock);
      // 锁定
      acquiresleep(&b->lock);
      return b;
    }
  }
  // cache不够用了
  panic("bget: no buffers");
}

Logging layer

简介

Xv6通过简单的日志记录形式解决了文件系统操作期间的崩溃问题。

xv6系统调用不会直接写入磁盘上的文件系统数据结构。相反，它会在磁盘上的log（日志）中放置它希望进行的所有磁盘写入的描述。一旦系统调用记录了它的所有写入操作，它就会向磁盘写入一条特殊的commit（提交）记录，表明日志包含一个完整的操作。此时，系统调用将写操作复制到磁盘上的文件系统数据结构。完成这些写入后，系统调用将擦除磁盘上的日志。

如果系统崩溃并重新启动，则在运行任何进程之前，文件系统代码将按如下方式从崩溃中恢复：

如果日志标记为包含完整操作，则恢复代码会将写操作复制到磁盘文件系统中它们所属的位置，然后擦除日志。如果日志没有标记为包含完整操作，则恢复代码将忽略该日志，然后擦除日志。

这就保证了原子性。

Log design

image-20230121162324747

superblock记录了log的存储位置。

它由一个头块（header block）和一系列更新块的副本（logged block）组成。

头块包含一个扇区号（sector）数组（每个logged block对应一个扇区号）以及日志块的计数。

磁盘上的头块中的计数为零表示日志中没有事务，为非零表示日志包含一个完整的已提交事务，并具有指定数量的logged block。

在事务提交（commit）时Xv6才向头块写入数据，在此之前不会写入。在将logged blocks复制到文件系统后，头块的计数将被设置为零。

因此，事务中途崩溃将导致日志头块中的计数为零；提交后的崩溃将导致非零计数。

为了允许不同进程并发执行文件系统操作，日志系统可以将多个系统调用的写入累积到一个事务中。因此，单个提交可能涉及多个完整系统调用的写入。为了避免在事务之间拆分系统调用，日志系统仅在没有文件系统调用进行时提交。

同时提交多个事务的想法称为组提交（group commit）。组提交减少了磁盘操作的数量，因为成本固定的一次提交分摊了多个操作。组提交还同时为磁盘系统提供更多并发写操作，可能允许磁盘在一个磁盘旋转时间内写入所有这些操作。Xv6的virtio驱动程序不支持这种批处理，但是Xv6的文件系统设计允许这样做。

【这感觉实现得也还挺简略的】

Xv6在磁盘上留出固定的空间来保存日志。事务中系统调用写入的块总数必须可容纳于该空间。这导致两个后果：

  1. 任何单个系统调用都不允许写入超过日志空间的不同块。

    【这段话我一个字没看懂】

    这对于大多数系统调用来说都不是问题，但其中两个可能会写入许多块：write和unlink。一个大文件的write可以写入多个数据块和多个位图块以及一个inode块；unlink大文件可能会写入许多位图块和inode。Xv6的write系统调用将大的写入分解为适合日志的多个较小的写入，unlink不会导致此问题，因为实际上Xv6文件系统只使用一个位图块。

  2. 日志空间有限的另一个后果是，除非确定系统调用的写入将可容纳于日志中剩余的空间，否则日志系统无法允许启动系统调用。

Code: logging

log的原理是这样的：

在每个系统调用的开始调用begin_op表示事务开始，然后之后新申请一块block，也即把该block的内容读入内存，并且把该block的blockno记录到log的header中。此后程序正常修改在内存中的block，磁盘中的block保持不变。最后commit的时候遍历log header中的blockno，一块块地把内存中的block写入日志和磁盘中。

如果程序在commit前崩溃，则内存消失，同时磁盘也不会写入；如果在commit后崩溃，那也无事发生。

在每次启动的时候，都会执行log的初始化，届时可以顺便恢复数据。

完美实现了日志的功能。

image-20230123212753931

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Contents of the header block, used for both the on-disk header block
// and to keep track in memory of logged block# before commit.
struct logheader {
  int n;
  // 扇区号也即blockno的数组
  int block[LOGSIZE];
};

// 代表log磁盘块
struct log {
  struct spinlock lock;
  int start;// log磁盘块的开始。start开始的第一块为log header，之后皆为写入的block
  int size;
  int outstanding; // how many FS sys calls are executing.
  int committing;  // in commit(), please wait.
  int dev;
  struct logheader lh;
};
struct log log;

关键函数

begin_op()

begin_op等待直到日志系统当前未处于提交中，并且直到有足够的未被占用的日志空间来保存此调用的写入。

log.outstanding统计预定了日志空间的系统调用数；为此保留的总空间为log.outstanding乘以MAXOPBLOCKS（10）。递增log.outstanding会预定空间并防止在此系统调用期间发生提交（if的第二个分支）。代码保守地假设每个系统调用最多可以写入MAXOPBLOCKS（10）个不同的块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// called at the start of each FS system call.
void
begin_op(void)
{
  acquire(&log.lock);
  while(1){
    // 正在提交则等待日志空闲
    if(log.committing){
      sleep(&log, &log.lock);
    // 日志空间不足则等待空间充足
    } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
      // this op might exhaust log space此操作可能会耗尽日志空间; wait for commit.
      sleep(&log, &log.lock);
    } else {
      log.outstanding += 1;
      release(&log.lock);
      break;
    }
  }
}
log_write

log_write充当bwrite的代理。它将块的扇区号记录在内存中，在磁盘上的日志中预定一个槽位，并调用bpin将缓存固定在block cache中，以防止block cache将其逐出【具体原理就是让refcnt++，这样就不会被当成空闲block用掉了】。

为啥要防止换出呢？换出不是就正好自动写入磁盘了吗？这里一是为了保障前面提到的原子性，防止换入换出导致的单一写入磁盘；二是换出自动写入的是磁盘对应位而不一定是日志所在的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
void
log_write(struct buf *b)
{
  int i;
  // #define LOGSIZE      (MAXOPBLOCKS*3)  // max data blocks in on-disk log
  // 30
  if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
    panic("too big a transaction");
  if (log.outstanding < 1)
    panic("log_write outside of trans");

  acquire(&log.lock);
  // log_write会注意到在单个事务中多次写入一个块的情况，并在日志中为该块分配相同的槽位。
  // 这种优化通常称为合并（absorption）
  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)   // log absorbtion
      break;
  }
  // 这里还是挺巧妙的。
  // 如果存在log.lh.block[i] == b->blockno的情况，执行此句话也无妨
  // 如果不存在，则给log新增一块，填入log.lh.block[log.lh.n]的位置，再++log.lh.n
  log.lh.block[i] = b->blockno;
  if (i == log.lh.n) {  // Add new block to log?
    bpin(b);
    log.lh.n++;
  }
  release(&log.lock);
}
end_op
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
// called at the end of each FS system call.
// 如果这是最后一层outstanding就会执行commit操作
// commits if this was the last outstanding operation.
void
end_op(void)
{
  int do_commit = 0;

  acquire(&log.lock);
  log.outstanding -= 1;
  if(log.committing)
    panic("log.committing");
  if(log.outstanding == 0){
    do_commit = 1;
    log.committing = 1;
  } else {
    // begin_op() may be waiting for log space,
    // and decrementing log.outstanding has decreased
    // the amount of reserved space.
    wakeup(&log);
  }
  release(&log.lock);

  if(do_commit){
    // call commit w/o holding locks, since not allowed
    // to sleep with locks.
    commit();
    acquire(&log.lock);
    log.committing = 0;
    wakeup(&log);
    release(&log.lock);
  }
}
commit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void
commit()
{
  if (log.lh.n > 0) {
    // cache -> log block
    write_log();     // Write modified blocks from cache to log
    // head(in stack/heap) -> log block
    // 此可以说为commit完成的标志。
    // 因为无论接下来是否崩溃，数据最终都会被写入disk，不同在于是在recover时还是接下来写入
    write_head();    // Write header to disk -- the real commit
    // log block -> real position
    install_trans(0); // Now install writes to home locations
    log.lh.n = 0;
    // 擦除
    write_head();    // Erase the transaction from the log
  }
}
write_log
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Copy modified blocks from cache to log.
static void
write_log(void)
{
  int tail;

  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *to = bread(log.dev, log.start+tail+1); // log block
    struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
    memmove(to->data, from->data, BSIZE);
    bwrite(to);  // write the log
    brelse(from);// 此处的brelse呼应了外界调用的bread
    brelse(to);
  }
}
write_head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Write in-memory log header to disk.
// 这是事务提交的标志
// This is the true point at which the
// current transaction commits.
static void
write_head(void)
{
  struct buf *buf = bread(log.dev, log.start);
  struct logheader *hb = (struct logheader *) (buf->data);
  int i;
  hb->n = log.lh.n;
  for (i = 0; i < log.lh.n; i++) {
    hb->block[i] = log.lh.block[i];
  }
  bwrite(buf);
  brelse(buf);
}
install_trans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Copy committed blocks from log to their home location
static void
install_trans(int recovering)
{
  int tail;

  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block
    struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst
    memmove(dbuf->data, lbuf->data, BSIZE);  // copy block to dst
    bwrite(dbuf);  // write dst to disk
    if(recovering == 0)
      bunpin(dbuf);// 如果不是在recover的过程中
    brelse(lbuf);
    brelse(dbuf);
  }
}

恢复与初始化

上面介绍了log的一次事务提交的流程。接下来介绍它是怎么恢复的。

recover_from_log是由initlog调用的，而它又是在第一个用户进程运行之前的引导期间由fsinit调用的。

第一个进程运行之前

由前面scheduler一章的知识可知，每个进程被初次调度的时候会先来执行forkret。这时候就做了log的恢复工作。

注释解释了为什么不选择在main.c中初始化，而选择在此处初始化。确实，它需要调用sleep，如果在main.c中调用sleep感觉会乱套（）毕竟那时候scheduler线程尚未被初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// A fork child's very first scheduling by scheduler()
// will swtch to forkret.
void
forkret(void)
{
  // static变量仅会被初始化一次
  static int first = 1;

  // Still holding p->lock from scheduler.
  release(&myproc()->lock);

  // 如果是第一个进程
  if (first) {
    // File system initialization must be run in the context of a
    // regular process (e.g., because it calls sleep), and thus cannot
    // be run from main().
    first = 0;
    fsinit(ROOTDEV);
  }

  usertrapret();
}
fsinit
1
2
3
4
5
6
// Init fs
void
fsinit(int dev) {
  // ...
  initlog(dev, &sb);
}
initlog
1
2
3
4
5
6
7
8
9
10
11
12
13
void
initlog(int dev, struct superblock *sb)
{
  if (sizeof(struct logheader) >= BSIZE)
    panic("initlog: too big logheader");

  initlock(&log.lock, "log");
  // 从super block中获取必要参数
  log.start = sb->logstart;
  log.size = sb->nlog;
  log.dev = dev;
  recover_from_log();
}
recover_from_log
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void
recover_from_log(void)
{
  // 读取head
  read_head();
  // 注意，commit中会把header写入log block，而这里从log block读出header
  // 也就是说，如果header的n不为零，那么说明已经commit了，但可能未写入，重复写入保障安全
  // 如果header的n为零，说明未commit，在install_trans的逻辑中会什么也不做
  // 两种情况完美满足
  install_trans(1); // if committed, copy from log to disk
  log.lh.n = 0;
  // 擦除
  write_head(); // clear the log
}

Code: Block allocator

个人理解

说实话没怎么懂，也不大清楚它有什么用，先大概推测一下：

之前的bread和bwrite这些，就是你给一个设备号和扇区号，它就帮你加载进内存cache。你如果要用的话，肯定还是使用地址方便。所以block allocator的作用之一就是给bread和bwrite加一层封装，将获取的block封装为地址返回，你可以直接操纵这个地址，而无需知道下层的细节。

这个过程要注意的有两点：

  1. 封装返回的地址具体是什么，怎么工作的

    封装返回的地址实质上是buffer cache中的buf的data字段的地址【差不多】。之后的上层应用在该地址上写入，也即写入了buf，最后会通过log层真正写入磁盘。

  2. 结合bcache的LRU，详细谈谈工作机制

    我们可以看到，在balloc中有这么一段逻辑：

    1
    2
    3
    4
    5
    bp = bread(dev, BBLOCK(b, sb));
    // ...
        log_write(bp);
        brelse(bp);
        return b + bi;

    看到的第一反应就是，我们需求的那块buf是bp，但是这里先是bread了一次，又是brelse了一次，这样bp的refcnt不就为0，很容易被替换掉了吗？

    会有这个反应，一定程度上是因为没有很好地理解LRU。事实上，正是它可能被替换掉，才满足了LRU的条件。因为它可能被替掉才能说明它可能是最近最少使用的。

bitmap

文件和目录内容存储在磁盘块中，磁盘块必须从空闲池中分配。xv6的块分配器在磁盘上维护一个空闲位图，每一位代表一个块。0表示对应的块是空闲的；1表示它正在使用中。

引导扇区、超级块、日志块、inode块和位图块的比特位是由程序mkfs初始化设置的：

image-20230123234919055

allocator

类似于memory allocator，块分配器也提供了两个函数：bfree和balloc。

balloc

Balloc从块0到sb.size（文件系统中的块数）遍历每个块。它查找位图中位为零的空闲块。如果balloc找到这样一个块，它将更新位图并返回该块。

为了提高效率，循环被分成两部分。外部循环读取位图中的每个块。内部循环检查单个位图块中的所有BPB位。由于任何一个位图块在buffer cache中一次只允许一个进程使用【 bread(dev, BBLOCK(b, sb))会返回一个上锁的block，bread和brelse隐含的独占使用避免了显式锁定的需要】，因此，如果两个进程同时尝试分配一个块也是并发安全的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Allocate a zeroed disk block.
static uint
balloc(uint dev)
{
  int b, bi, m;
  struct buf *bp;

  bp = 0;
  for(b = 0; b < sb.size; b += BPB){
    bp = bread(dev, BBLOCK(b, sb));
    for(bi = 0; bi < BPB && b + bi < sb.size; bi++){
      m = 1 << (bi % 8);
      if((bp->data[bi/8] & m) == 0){  // Is block free?
        bp->data[bi/8] |= m;  // Mark block in use.
        log_write(bp);
        brelse(bp);
        bzero(dev, b + bi);
        return b + bi;
      }
    }
    brelse(bp);
  }
  panic("balloc: out of blocks");
}

bfree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Free a disk block.
static void
bfree(int dev, uint b)
{
  struct buf *bp;
  int bi, m;

  bp = bread(dev, BBLOCK(b, sb));
  bi = b % BPB;
  m = 1 << (bi % 8);
  if((bp->data[bi/8] & m) == 0)
    panic("freeing free block");
  bp->data[bi/8] &= ~m;
  log_write(bp);
  brelse(bp);
}

Inode layer

inode

术语inode（即索引结点）可以具有两种相关含义之一。它可能是指包含文件大小和数据块编号列表的磁盘上的数据结构【on-disk inode】。或者“inode”可能指内存中的inode【in-memory inode】，它包含磁盘上inode的副本以及内核中所需的额外信息。

image-20230121162324747

on-disk inode

The on-disk inodes are packed into a contiguous area of disk called the inode blocks.

Every inode is the same size, so it is easy, given a number n, to find the nth inode on the disk. In fact, this number n, called the inode number or i-number, is how inodes are identifified in the implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
// in fs.h
// On-disk inode structure
struct dinode {
  // 为0表示free
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  //  The nlink field counts the number of directory entries that refer to this inode,
  //  in order to recognize when the on-disk inode and its data blocks should be freed.
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

in-memory inode

The kernel keeps the set of active inodes in memory.

The kernel stores an inode in memory only if there are C pointers referring to that inode.当且仅当ref==0才会从内核中释放。

如果nlinks==0就会从物理block中释放。

The iget and iput functions acquire and release pointers to an inode, modifying the reference count.【相当于buffer cache的balloc和bfree】Pointers to an inode can come from file descriptors, current working directories, and transient kernel code such as exec.

iget返回的struct inode可能没有任何有用的内容。为了确保它保存磁盘inode的副本，代码必须调用ilock。这将锁定inode（以便没有其他进程可以对其进行ilock），并从磁盘读取尚未读取的inode。iunlock释放inode上的锁。将inode指针的获取与锁定分离有助于在某些情况下避免死锁，例如在目录查找期间。多个进程可以持有指向iget返回的inode的C指针，但一次只能有一个进程锁定inode。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//in file.h
// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];// 存储着inode数据的blocks的地址，从balloc中获取
};

Code: inode

主要是在讲inode layer这一层的方法，以及给上层提供的接口。

Overview

image-20230124153309132

底层接口

iget iput

iget

逻辑还是跟buffer cache非常相似的，不过可以看出这个的数据结构简单许多，也不用实现LRU。

A struct inode pointer returned by iget() is guaranteed to be valid until the corresponding call to iput()： the inode won’t be deleted, and the memory referred to by the pointer won’t be re-used for a different inode. 【通过ref++实现。】

不同于buffer cache的bget，iget()提供对inode的非独占访问，因此可以有许多指向同一inode的指针。文件系统代码的许多部分都依赖于iget()的这种行为，既可以保存对inode的长期引用（如打开的文件和当前目录），也可以防止争用，同时避免操纵多个inode（如路径名查找）的代码产生死锁。

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
// Find the inode with number inum on device dev
// and return the in-memory copy. Does not lock
// the inode and does not read it from disk.
static struct inode*
iget(uint dev, uint inum)
{
  struct inode *ip, *empty;

  acquire(&icache.lock);

  // Is the inode already cached?
  empty = 0;
  for(ip = &icache.inode[0]; ip < &icache.inode[NINODE]; ip++){
    if(ip->ref > 0 && ip->dev == dev && ip->inum == inum){
      ip->ref++;
      release(&icache.lock);
      return ip;
    }
    // 由于不用实现LRU，所以只需一次循环记录即可。
    if(empty == 0 && ip->ref == 0)    // Remember empty slot.
      empty = ip;
  }

  // Recycle an inode cache entry.
  if(empty == 0)
    panic("iget: no inodes");

  ip = empty;
  ip->dev = dev;
  ip->inum = inum;
  ip->ref = 1;
  // does not read from disk
  ip->valid = 0;
  release(&icache.lock);

  return ip;
}
iput

iput()可以写入磁盘。这意味着任何使用文件系统的系统调用都可能写入磁盘，因为系统调用可能是最后一个引用该文件的系统调用。即使像read()这样看起来是只读的调用，也可能最终调用iput()。这反过来意味着，即使是只读系统调用，如果它们使用文件系统，也必须在事务中进行包装。

iput()和崩溃之间存在一种具有挑战性的交互。iput()不会在文件的链接计数降至零时立即截断文件，因为某些进程可能仍在内存中保留对inode的引用：进程可能仍在读取和写入该文件，因为它已成功打开该文件。但是，如果在最后一个进程关闭该文件的文件描述符之前发生崩溃，则该文件将被标记为已在磁盘上分配，但没有目录项指向它。如果不做任何处理措施的话，这块磁盘就再也用不了了。

文件系统以两种方式之一处理这种情况。简单的解决方案用于恢复时：重新启动后，文件系统会扫描整个文件系统，以查找标记为已分配但没有指向它们的目录项的文件。如果存在任何此类文件，接下来可以将其释放。

第二种解决方案不需要扫描文件系统。在此解决方案中，文件系统在磁盘（例如在超级块中）上记录链接计数降至零但引用计数不为零的文件的i-number。如果文件系统在其引用计数达到0时删除该文件，则会通过从列表中删除该inode来更新磁盘列表。重新启动时，文件系统将释放列表中的所有文件。

Xv6没有实现这两种解决方案，这意味着inode可能被标记为已在磁盘上分配，即使它们不再使用。这意味着随着时间的推移，xv6可能会面临磁盘空间不足的风险。

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
// Drop a reference to an in-memory inode.
// If that was the last reference, the inode cache entry can
// be recycled.【refvnt==0 可以回收】
// 注意这个回收过程无需特别处理，只需自然--refcnt就行，不用像buffer cache那么烦
// If that was the last reference and the inode has no links
// to it, free the inode (and its content) on disk.【nlinks==0 copy和本体都得扔掉】
// All calls to iput() must be inside a transaction in
// case it has to free the inode.任何需要iput的地方都需要包裹在事务内，因为它可能会释放inode
void
iput(struct inode *ip)
{
  acquire(&icache.lock);

  if(ip->ref == 1 && ip->valid && ip->nlink == 0){
    // inode has no links and no other references: truncate and free.

    // ip->ref == 1 means no other process can have ip locked,
    // so this acquiresleep() won't block (or deadlock).
    acquiresleep(&ip->lock);

    release(&icache.lock);

    // 最终调用bfree，会标记bitmap，完全释放block
    itrunc(ip);
    ip->type = 0;
      
    /*iupdate:
    // Copy a modified in-memory inode to disk.
    // Must be called after every change to an ip->xxx field
	// that lives on disk, since i-node cache is write-through.
	write-through:
	CPU向cache写入数据时，同时向memory(后端存储)也写一份，使cache和memory的数据保持一致。
    */
    // 这里修改的type是dinode也有的字段，所以需要update一下。
    // 下面的valid是dinode没有的字段，所以随便改，无需update
    iupdate(ip);
    ip->valid = 0;

    releasesleep(&ip->lock);

    acquire(&icache.lock);
  }

  ip->ref--;
  release(&icache.lock);
}

上层接口

获取和释放inode
ialloc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Allocate an inode on device dev.
// Mark it as allocated by  giving it type type.
// Returns an unlocked but allocated and referenced inode.
struct inode*
ialloc(uint dev, short type)
{
  int inum;
  struct buf *bp;
  struct dinode *dip;

  for(inum = 1; inum < sb.ninodes; inum++){
    bp = bread(dev, IBLOCK(inum, sb));
    dip = (struct dinode*)bp->data + inum%IPB;
    if(dip->type == 0){  // a free inode通过type判断是否free
      memset(dip, 0, sizeof(*dip));// zerod
      dip->type = type;
      log_write(bp);   // mark it allocated on the disk
      brelse(bp);
      return iget(dev, inum);
    }
    brelse(bp);
  }
  panic("ialloc: no inodes");
}
inode的锁保护

前面说到，inode的设计使得有多个指针同时指向一个inode成为了可能。因而，修改使用inode的时候就要对其进行独占访问。使用ialloc获取和用ifree释放的inode必须被保护在ilock和iunlock区域中。

ilock

ilock既可以实现对inode的独占访问，同时也可以给未初始化的inode进行初始化工作。

iget返回的struct inode可能没有任何有用的内容。为了确保它保存磁盘inode的副本，代码必须调用ilock。这将锁定inode（以便没有其他进程可以对其进行ilock），并从磁盘读取尚未读取的inode。

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
// Lock the given inode and reads the inode from disk if necessary.
void
ilock(struct inode *ip)
{
  struct buf *bp;
  struct dinode *dip;

  if(ip == 0 || ip->ref < 1)
    panic("ilock");

  acquiresleep(&ip->lock);

  if(ip->valid == 0){
    // 通过inode索引号和superblock算出扇区号
    bp = bread(ip->dev, IBLOCK(ip->inum, sb));
    dip = (struct dinode*)bp->data + ip->inum%IPB;
    // 填充ip
    ip->type = dip->type;
    ip->major = dip->major;
    ip->minor = dip->minor;
    ip->nlink = dip->nlink;
    ip->size = dip->size;
    memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
    brelse(bp);
    ip->valid = 1;
    if(ip->type == 0)
      panic("ilock: no type");
  }
}
iunlock

iunlock释放inode上的锁。

将inode指针的获取与锁定分离有助于在某些情况下避免死锁，例如在目录查找期间。多个进程可以持有指向iget返回的inode的C指针，但一次只能有一个进程锁定inode。

1
2
3
4
5
6
7
8
9
// Unlock the given inode.
void
iunlock(struct inode *ip)
{
  if(ip == 0 || !holdingsleep(&ip->lock) || ip->ref < 1)
    panic("iunlock");

  releasesleep(&ip->lock);
}

Code: inode content

Overview

主要讲的是inode本身存储数据的结构

磁盘上的inode结构体struct dinode包含一个size和一个块号数组（见图8.3），数组内罗列着存储着该inode数据的块号。

前面的NDIRECT个数据块被列在数组中的前NDIRECT个元素中；这些块称为直接块（direct blocks）。接下来的NINDIRECT个数据块不在inode中列出，而是在称为间接块（indirect block）的数据块中列出。addrs数组中的最后一个元素给出了间接块的地址。

因此，可以从inode中列出的块加载文件的前12 kB（NDIRECT x BSIZE）字节，而只有在查阅间接块后才能加载下一个256 kB（NINDIRECT x BSIZE）字节。

1
2
3
4
5
// On-disk inode structure
struct dinode {
  // ...
  uint addrs[NDIRECT+1];   // Data block addresses
};

image-20230124163025094

bmap

函数bmap负责封装这个寻找数据块的过程，以便实现我们将很快看到的如readi和writei这样的更高级例程。

bmap(struct inode *ip, uint bn)返回inodeip的第bn个数据块的磁盘块号。如果ip还没有这样的块，bmap会分配一个。

Bmap使readi和writei很容易获取inode的数据。

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
// Inode content
//
// The content (data) associated with each inode is stored
// in blocks on the disk. The first NDIRECT block numbers
// are listed in ip->addrs[].  The next NINDIRECT blocks are
// listed in block ip->addrs[NDIRECT].

// Return the disk block address of the nth block in inode ip.
// If there is no such block, bmap allocates one.
static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  // 如果为direct block
  if(bn < NDIRECT){
    if((addr = ip->addrs[bn]) == 0)
      ip->addrs[bn] = addr = balloc(ip->dev);
    return addr;
  }
  bn -= NDIRECT;
    
  // 如果为indirect block
  if(bn < NINDIRECT){
    // Load indirect block, allocating if necessary.
    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;
  }

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

itrunc

itrunc释放文件的块，将inode的size重置为零。

Itrunc首先释放直接块，然后释放间接块中列出的块，最后释放间接块本身。

readi

readi和writei都是从检查ip->type == T_DEV开始的。这种情况处理的是数据不在文件系统中的特殊设备；我们将在文件描述符层返回到这种情况。

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
// Read data from inode.数据大小为n，从off开始，读到dst处
// Caller must hold ip->lock.
// If user_dst==1, then dst is a user virtual address;
// otherwise, dst is a kernel address.
int
readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;

  if(off > ip->size || off + n < off)
    return 0;
  if(off + n > ip->size)
    n = ip->size - off;

  // 主循环处理文件的每个块，将数据从缓冲区复制到dst
  for(tot=0; tot<n; tot+=m, off+=m, dst+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    if(either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
      brelse(bp);
      tot = -1;
      break;
    }
    brelse(bp);
  }
  return tot;
}

writei

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
// Write data to inode.
// Caller must hold ip->lock.
// If user_src==1, then src is a user virtual address;
// otherwise, src is a kernel address.
int
writei(struct inode *ip, int user_src, uint64 src, uint off, uint n)
{
  uint tot, m;
  struct buf *bp;

  if(off > ip->size || off + n < off)
    return -1;
  // writei会自动增长文件，除非达到文件的最大大小
  if(off + n > MAXFILE*BSIZE)
    return -1;

  for(tot=0; tot<n; tot+=m, off+=m, src+=m){
    bp = bread(ip->dev, bmap(ip, off/BSIZE));
    m = min(n - tot, BSIZE - off%BSIZE);
    if(either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
      brelse(bp);
      n = -1;
      break;
    }
    log_write(bp);
    brelse(bp);
  }

  if(n > 0){
    if(off > ip->size)
      // 说明扩大了文件大小，需要修改
      ip->size = off;
    // write the i-node back to disk even if the size didn't change
    // because the loop above might have called bmap() and added a new
    // block to ip->addrs[].
    iupdate(ip);
  }

  return n;
}

stati

函数stati将inode元数据复制到stat结构体中，该结构通过stat系统调用向用户程序公开。

在defs.h中可看到inode结构体是private的，而stat是public的。

Directory layer

数据结构

目录的内部实现很像文件。其inode的type为T_DIR，其数据是directory entries的集合。

每个entry都是一个struct dirent。

也就是说这一层其实本质上是一个大小一定的map，该map自身也存放在inode中，大小为inode的大小，每个表项entry映射了目录名和文件inode。所以接下来介绍的函数我们完全可以从hashmap增删改查的角度去理解。

1
2
3
4
5
6
7
// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

struct dirent {
  ushort inum;// 如果为0，说明该entry free
  char name[DIRSIZ];
};

image-20230124173241241

相关函数

dirlookup

函数dirlookup在directory中搜索具有给定名称的entry。

它返回的指向enrty.inum相应的inode是非独占的【通过iget获取】，也即无锁状态。它还会把*poff设置为所需的entry的字节偏移量。

为什么要返回未锁定的inode？是因为调用者已锁定dp，因此，如果对.进行查找，则在返回之前尝试锁定inode将导致重新锁定dp并产生死锁【确实】(还有更复杂的死锁场景，涉及多个进程和..，父目录的别名。.不是唯一的问题。）

所以锁定交给caller来做。caller可以解锁dp，然后锁定该函数返回的ip，确保它一次只持有一个锁。

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
// Look for a directory entry in a directory.
// If found, set *poff to byte offset of entry.
struct inode*
dirlookup(struct inode *dp, char *name, uint *poff)
{
  uint off, inum;
  struct dirent de;

  if(dp->type != T_DIR)
    panic("dirlookup not DIR");
  // new level of abstraction,可以把directory的inode看作一个表文件，每个表项都是一个entry
  for(off = 0; off < dp->size; off += sizeof(de)){
    // 从directory中获取entry，也即从inode中获取数据
    if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlookup read");
    // free
    if(de.inum == 0)
      continue;
    if(namecmp(name, de.name) == 0){
      // entry matches path element
      if(poff)
        *poff = off;
      inum = de.inum;
      return iget(dp->dev, inum);
    }
  }

  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
// Write a new directory entry (name, inum) into the directory dp.
int
dirlink(struct inode *dp, char *name, uint inum)
{
  int off;
  struct dirent de;
  struct inode *ip;

  // Check that name is not present.
  if((ip = dirlookup(dp, name, 0)) != 0){
    iput(ip);
    return -1;
  }

  // Look for an empty dirent.
  for(off = 0; off < dp->size; off += sizeof(de)){
    if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
      panic("dirlink read");
    if(de.inum == 0)
      break;
  }

  // 如果没找到空闲的则调用writei自动增长inode，添加新表项
  strncpy(de.name, name, DIRSIZ);
  de.inum = inum;
  if(writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
    panic("dirlink");

  return 0;
}

Pathname layer

Path name lookup involves a succession of calls to dirlookup, one for each path component.

namei和nameiparent

Namei (kernel/fs.c:661) evaluates path and returns the corresponding inode.

函数nameiparent是一个变体：它在最后一个元素之前停止，返回父目录的inode并将最后一个元素复制到name中。两者都调用通用函数namex来完成实际工作。

1
2
3
4
5
6
struct inode*
namei(char *path)
{
  char name[DIRSIZ];
  return namex(path, 0, name);
}
1
2
3
4
5
struct inode*
nameiparent(char *path, char *name)
{
  return namex(path, 1, name);
}

namex

Namex首先决定路径解析的开始位置。

如果路径以“ / ”开始，则从根目录开始解析；否则，从当前目录开始。

然后，它使用skipelem依次考察路径的每个元素。循环的每次迭代都必须在当前索引结点ip中查找name。

迭代首先给ip上锁并检查它是否是一个目录。如果不是，则查找失败。

如果caller是nameiparent，并且这是最后一个路径元素，则根据nameiparent的定义，循环会提前停止；最后一个路径元素已经复制到name中【在上一轮循坏中做了这件事】，因此namex只需返回解锁的ip。

最后，循环将使用dirlookup查找路径元素，并通过设置ip = next为下一次迭代做准备。当循环用完路径元素时，它返回ip。

注：

  1. 在每次迭代中锁定ip是必要的，不是因为ip->type可以被更改，而是因为在ilock运行之前，ip->type不能保证已从磁盘加载，所以得用到ilock保证一定会被加载的这个性质。
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
// Look up and return the inode for a path name.
// If parent != 0, return the inode for the parent and copy the final
// path element into name, which must have room for DIRSIZ bytes.
// Must be called inside a transaction since it calls iput().
static struct inode*
namex(char *path, int nameiparent, char *name)
{
  struct inode *ip, *next;

  if(*path == '/')
    ip = iget(ROOTDEV, ROOTINO);
  else
    ip = idup(myproc()->cwd);

  // 使用skipelem依次考察路径的每个元素
  while((path = skipelem(path, name)) != 0){
    ilock(ip);
    if(ip->type != T_DIR){
      iunlockput(ip);
      return 0;
    }
    if(nameiparent && *path == '\0'){
      // Stop one level early.
      iunlock(ip);
      return ip;
    }
    if((next = dirlookup(ip, name, 0)) == 0){
      iunlockput(ip);
      return 0;
    }
    iunlockput(ip);
    ip = next;
  }
  if(nameiparent){
    iput(ip);
    return 0;
  }
  return ip;
}

namex过程可能需要很长时间才能完成：它可能涉及多个磁盘操作来读取路径名中所遍历目录的索引节点和目录块（如果它们不在buffer cache中）。

Xv6 is carefully designed，如果一个内核线程对namex的调用在磁盘I/O上阻塞，另一个查找不同路径名的内核线程可以同时进行。Namex locks each directory in the path separately so that lookups in different directories can proceed in parallel.锁细粒度化

This concurrency introduces some challenges. For example, while one kernel thread is looking up a pathname another kernel thread may be changing the directory tree by unlinking a directory. A potential risk is that a lookup may be searching a directory that has been deleted by another kernel thread and its blocks have been re-used for another directory or file.一个潜在的风险是，查找可能正在搜索已被另一个内核线程删除且其块已被重新用于另一个目录或文件的目录。

Xv6避免了这种竞争，也就是说，你查到的inode保证暂时不会被释放，里面的内容还是真的，而不会被重新利用从而导致里面的内容变样。

例如，在namex中执行dirlookup时，lookup线程持有目录上的锁，dirlookup返回使用iget获得的inode。Iget增加索引节点的引用计数。只有在从dirlookup接收inode之后，namex才会释放目录上的锁。现在，另一个线程可以从目录中取消inode的链接，但是xv6还不会删除inode，因为inode的引用计数仍然大于零。

另一个风险是死锁。例如，查找“.”时，next指向与ip相同的inode【确实】。在释放ip上的锁之前锁定next将导致死锁【为什么？？？难道不是会由于在acquire时已经持有锁，从而爆panic("acquire")吗？】。为了避免这种死锁，namex在获得下一个目录的锁之前解锁该目录。这里我们再次看到为什么iget和ilock之间的分离很重要。

File descriptor layer

Unix的一个很酷的方面是，Unix中的大多数资源都表示为文件，包括控制台、管道等设备，当然还有真实文件。文件描述符层是实现这种一致性的层。

数据结构

Xv6为每个进程提供了自己的打开文件表或文件描述符。每个打开的文件都由一个struct file表示，它是inode或管道的封装，加上一个I/O偏移量。

每次调用open都会创建一个新的打开文件（一个新的struct file）：如果多个进程独立地打开同一个文件，那么不同的实例将具有不同的I/O偏移量。

另一方面，单个打开的文件（同一个struct file）可以多次出现在一个进程的文件表中，也可以出现在多个进程的文件表中。如果一个进程使用open打开文件，然后使用dup创建别名，或使用fork与子进程共享，就会发生这种情况。

1
2
3
4
5
6
7
8
9
10
struct file {
  enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
  int ref; // reference count
  char readable;
  char writable;
  struct pipe *pipe; // FD_PIPE
  struct inode *ip;  // FD_INODE and FD_DEVICE
  uint off;          // FD_INODE
  short major;       // FD_DEVICE
};

ftable

所有在系统中打开的文件都会被放入global file tableftable中。

ftable具有分配文件（filealloc）、创建重复引用（filedup）、释放引用（fileclose）以及读取和写入数据（fileread和filewrite）的函数。

前三个都很常规，跟之前的xxalloc、xxfree的思路是一样的。

函数filestat、fileread和filewrite实现对文件的stat、read和write操作。

filealloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Allocate a file structure.
struct file*
filealloc(void)
{
  struct file *f;

  acquire(&ftable.lock);
  for(f = ftable.file; f < ftable.file + NFILE; f++){
    if(f->ref == 0){
      f->ref = 1;
      release(&ftable.lock);
      return f;
    }
  }
  release(&ftable.lock);
  return 0;
}

filedup

1
2
3
4
5
6
7
8
9
10
11
// Increment ref count for file f.
struct file*
filedup(struct file *f)
{
  acquire(&ftable.lock);
  if(f->ref < 1)
    panic("filedup");
  f->ref++;
  release(&ftable.lock);
  return f;
}

fileclose

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
// Close file f.  (Decrement ref count, close when reaches 0.)
void
fileclose(struct file *f)
{
  struct file ff;

  acquire(&ftable.lock);
  if(f->ref < 1)
    panic("fileclose");
  if(--f->ref > 0){
    release(&ftable.lock);
    return;
  }
  ff = *f;
  f->ref = 0;
  f->type = FD_NONE;
  release(&ftable.lock);

  if(ff.type == FD_PIPE){
    pipeclose(ff.pipe, ff.writable);
  } else if(ff.type == FD_INODE || ff.type == FD_DEVICE){
    begin_op();
    iput(ff.ip);
    end_op();
  }
}

filestat

Filestat只允许在inode上操作并且调用了stati

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Get metadata about file f.
// addr is a user virtual address, pointing to a struct stat.
int
filestat(struct file *f, uint64 addr)
{
  struct proc *p = myproc();
  struct stat st;

  // 仅允许文件/设备执行
  if(f->type == FD_INODE || f->type == FD_DEVICE){
    ilock(f->ip);
    stati(f->ip, &st);
    iunlock(f->ip);
    if(copyout(p->pagetable, addr, (char *)&st, sizeof(st)) < 0)
      return -1;
    return 0;
  }
  return -1;
}

fileread

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
// Read from file f.
// addr is a user virtual address.
int
fileread(struct file *f, uint64 addr, int n)
{
  int r = 0;
  
  // 首先检查是否可读
  if(f->readable == 0)
    return -1;

  if(f->type == FD_PIPE){
    r = piperead(f->pipe, addr, n);
  } else if(f->type == FD_DEVICE){
    if(f->major < 0 || f->major >= NDEV || !devsw[f->major].read)
      return -1;
    r = devsw[f->major].read(1, addr, n);
  } else if(f->type == FD_INODE){
    ilock(f->ip);
    if((r = readi(f->ip, 1, addr, f->off, n)) > 0)
      // 移动文件指针偏移量
      f->off += r;
    iunlock(f->ip);
  } else {
    panic("fileread");
  }

  return r;
}

Code: System calls

通过使用底层提供的函数，大多数系统调用的实现都很简单（请参阅***kernel/sysfile.c***）。有几个调用值得仔细看看。

以下介绍的函数都在kernel/sysfile.c中。

这个函数的功能是给文件old加上一个链接，这个链接存在于文件new的父目录。感觉也就相当于把文件从old复制到new处了。具体实现逻辑就是要给该文件所在目录添加一个entry，name=新名字，inode=该文件的inode。

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
// Create the path new as a link to the same inode as old.
uint64
sys_link(void)
{
  char name[DIRSIZ], new[MAXPATH], old[MAXPATH];
  struct inode *dp, *ip;

  if(argstr(0, old, MAXPATH) < 0 || argstr(1, new, MAXPATH) < 0)
    return -1;

  // 首先先增加nlink
  begin_op();
  // 通过path找到ip结点
  if((ip = namei(old)) == 0){
    end_op();
    return -1;
  }

  ilock(ip);
  // directory不能被link
  if(ip->type == T_DIR){
    iunlockput(ip);
    end_op();
    return -1;
  }

  ip->nlink++;
  // 修改一次字段就需要update一次
  iupdate(ip);
  iunlock(ip);

  // 然后再在目录中登记新的entry
  // 找到new的parent，也即new所在目录
  if((dp = nameiparent(new, name)) == 0)
    goto bad;
  ilock(dp);
  // 在目录中添加一个entry，名字为给定的新名字，inode依旧为原来的inode
  // new的父目录必须存在并且与现有inode位于同一设备上
  if(dp->dev != ip->dev || dirlink(dp, name, ip->inum) < 0){
    iunlockput(dp);
    goto bad;
  }
  iunlockput(dp);
  iput(ip);

  end_op();

  return 0;

bad:
  ilock(ip);
  ip->nlink--;
  iupdate(ip);
  iunlockput(ip);
  end_op();
  return -1;
}

create

它是三个文件创建系统调用的泛化：带有O_CREATE标志的open生成一个新的普通文件，mkdir生成一个新目录，mkdev生成一个新的设备文件。

创建一个新的inode结点，结点名包含在path内。返回一个锁定的inode。

由于使用了iupdate等，所以该函数只能在事务中被调用。

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
static struct inode*
create(char *path, short type, short major, short minor)
{
  struct inode *ip, *dp;
  char name[DIRSIZ];

  // 获取结点父目录
  if((dp = nameiparent(path, name)) == 0)
    return 0;

  ilock(dp);

  if((ip = dirlookup(dp, name, 0)) != 0){
    // 说明文件已存在
    iunlockput(dp);
    ilock(ip);
    if(type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE))
      // 说明此时caller为open（type == T_FILE），open调用create只能是用于创建文件
      return ip;
    iunlockput(ip);
    return 0;
  }

  if((ip = ialloc(dp->dev, type)) == 0)
    panic("create: ialloc");

  ilock(ip);
  ip->major = major;
  ip->minor = minor;
  ip->nlink = 1;
  iupdate(ip);

  if(type == T_DIR){  // Create . and .. entries.
    dp->nlink++;  // for ".."
    iupdate(dp);
    // No ip->nlink++ for ".": avoid cyclic ref count.
    // 所以其实.和..本质上是link
    if(dirlink(ip, ".", ip->inum) < 0 || dirlink(ip, "..", dp->inum) < 0)
      panic("create dots");
  }

  if(dirlink(dp, name, ip->inum) < 0)
    panic("create: dirlink");

  iunlockput(dp);

  return ip;
}

sys_mkdir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
uint64
sys_mkdir(void)
{
  char path[MAXPATH];
  struct inode *ip;

  begin_op();
  if(argstr(0, path, MAXPATH) < 0 || (ip = create(path, T_DIR, 0, 0)) == 0){
    end_op();
    return -1;
  }
  iunlockput(ip);
  end_op();
  return 0;
}

sys_open

Sys_open是最复杂的，因为创建一个新文件只是它能做的一小部分。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
uint64
sys_open(void)
{
  char path[MAXPATH];
  int fd, omode;
  struct file *f;
  struct inode *ip;
  int n;

  if((n = argstr(0, path, MAXPATH)) < 0 || argint(1, &omode) < 0)
    return -1;

  begin_op();

  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    // 创建失败
    if(ip == 0){
      end_op();
      return -1;
    }
  } else {
    // 文件不存在
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    // Create返回一个锁定的inode，但namei不锁定，因此sys_open必须锁定inode本身。
    ilock(ip);
    // 非文件，为目录并且非只读
    // 所以说想要open一个目录的话只能以只读模式打开
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }
  }

  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }

  // 获取file结构体和文件描述符。
  if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){
    if(f)
      fileclose(f);
    iunlockput(ip);
    end_op();
    return -1;
  }

  // 没有其他进程可以访问部分初始化的文件，因为它仅位于当前进程的表中，因而这里可以不用上锁
  if(ip->type == T_DEVICE){
    f->type = FD_DEVICE;
    f->major = ip->major;
  } else {
    f->type = FD_INODE;
    f->off = 0;
  }
  f->ip = ip;
  f->readable = !(omode & O_WRONLY);
  f->writable = (omode & O_WRONLY) || (omode & O_RDWR);

  // 如果使用了这个标志,调用 open 函数打开文件的时候会将文件原本的内容全部丢弃,文件大小变为 0。
  if((omode & O_TRUNC) && ip->type == T_FILE){
    itrunc(ip);
  }

  iunlock(ip);
  end_op();

  return fd;
}

sys_pipe

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
uint64
sys_pipe(void)
{
  uint64 fdarray; // user pointer to array of two integers用来接收pipe两端的文件描述符
  struct file *rf, *wf;
  int fd0, fd1;
  struct proc *p = myproc();

  if(argaddr(0, &fdarray) < 0)
    return -1;
  if(pipealloc(&rf, &wf) < 0)
    return -1;
  fd0 = -1;
  if((fd0 = fdalloc(rf)) < 0 || (fd1 = fdalloc(wf)) < 0){
    if(fd0 >= 0)
      p->ofile[fd0] = 0;
    fileclose(rf);
    fileclose(wf);
    return -1;
  }
  if(copyout(p->pagetable, fdarray, (char*)&fd0, sizeof(fd0)) < 0 ||
     copyout(p->pagetable, fdarray+sizeof(fd0), (char *)&fd1, sizeof(fd1)) < 0){
    p->ofile[fd0] = 0;
    p->ofile[fd1] = 0;
    fileclose(rf);
    fileclose(wf);
    return -1;
  }
  return 0;
}

Real world

实际操作系统中的buffer cache比xv6复杂得多，但它有两个相同的用途：缓存和同步对磁盘的访问。

与UNIX V6一样，Xv6的buffer cache使用简单的最近最少使用（LRU）替换策略；有许多更复杂的策略可以实现，每种策略都适用于某些工作场景，而不适用于其他工作场景。更高效的LRU缓存将消除链表，而改为使用哈希表进行查找，并使用堆进行LRU替换【跟我们在lock中实现的一样，再多个堆优化】。现代buffer cache通常与虚拟内存系统集成，以支持内存映射文件。

Xv6的日志系统效率低下。提交不能与文件系统调用同时发生。系统记录整个块，即使一个块中只有几个字节被更改。它执行同步日志写入，每次写入一个块，每个块可能需要整个磁盘旋转时间。真正的日志系统解决了所有这些问题。

文件系统布局中最低效的部分是目录，它要求在每次查找期间对所有磁盘块进行线性扫描【确实】。当目录只有几个磁盘块时，这是合理的，但对于包含许多文件的目录来说，开销巨大。Microsoft Windows的NTFS、Mac OS X的HFS和Solaris的ZFS（仅举几例）将目录实现为磁盘上块的平衡树。这很复杂，但可以保证目录查找在对数时间内完成（即时间复杂度为O(logn)）。

Xv6对于磁盘故障的解决很初级：如果磁盘操作失败，Xv6就会调用panic。这是否合理取决于硬件：如果操作系统位于使用冗余屏蔽磁盘故障的特殊硬件之上，那么操作系统可能很少看到故障，因此panic是可以的。另一方面，使用普通磁盘的操作系统应该预料到会出现故障，并能更优雅地处理它们，这样一个文件中的块丢失不会影响文件系统其余部分的使用。

Xv6要求文件系统安装在单个磁盘设备上，且大小不变。随着大型数据库和多媒体文件对存储的要求越来越高，操作系统正在开发各种方法来消除“每个文件系统一个磁盘”的瓶颈。基本方法是将多个物理磁盘组合成一个逻辑磁盘。RAID等硬件解决方案仍然是最流行的，但当前的趋势是在软件中尽可能多地实现这种逻辑。这些软件实现通常允许通过动态添加或删除磁盘来扩展或缩小逻辑设备等丰富功能。当然，一个能够动态增长或收缩的存储层需要一个能够做到这一点的文件系统：xv6使用的固定大小的inode块阵列在这样的环境中无法正常工作。将磁盘管理与文件系统分离可能是最干净的设计，但两者之间复杂的接口导致了一些系统（如Sun的ZFS）将它们结合起来。

Xv6的文件系统缺少现代文件系统的许多其他功能；例如，它缺乏对快照和增量备份的支持。

现代Unix系统允许使用与磁盘存储相同的系统调用访问多种资源：命名管道、网络连接、远程访问的网络文件系统以及监视和控制接口，如/proc。不同于xv6中fileread和filewrite的if语句，这些系统通常为每个打开的文件提供一个函数指针表【确实有印象】，每个操作一个，并通过函数指针来援引inode的调用实现。网络文件系统和用户级文件系统提供了将这些调用转换为网络RPC并在返回之前等待响应的函数。

（注：Linux 内核提供了一种通过/proc文件系统，在运行时访问内核内部数据结构、改变内核设置的机制。proc文件系统是一个伪文件系统，它只存在内存当中，而不占用外存空间。它以文件系统的方式为访问系统内核数据的操作提供接口。）

Lab: file system

In this lab you will add large files【大文件支持】 and symbolic links【软链接】 to the xv6 file system.

不过做完这个实验，给我的一种感觉就是磁盘管理和内存管理真的有很多相似之处，不过也许它们所代表的思想也很普遍。

Large files

实验内容

Overview

In this assignment you’ll increase the maximum size of an xv6 file.

Currently xv6 files are limited to 268 blocks, or 268*BSIZE bytes (BSIZE is 1024 in xv6). This limit comes from the fact that an xv6 inode contains 12 “direct” block numbers and one “singly-indirect” block number, which refers to a block that holds up to 256 more block numbers, for a total of 12+256=268 blocks.

You’ll change the xv6 file system code to support a “doubly-indirect” block in each inode, containing 256 addresses of singly-indirect blocks, each of which can contain up to 256 addresses of data blocks. The result will be that a file will be able to consist of up to 65803 blocks, or 256*256+256+11 blocks (11 instead of 12, because we will sacrifice one of the direct block numbers for the double-indirect block).

Preliminaries

If at any point during the lab you find yourself having to rebuild the file system from scratch, you can run make clean which forces make to rebuild fs.img.

What to Look At

意思就是要我们去看一眼fs.h，bmap，以及了解一下逻辑地址bn如何转化为blockno。这个我是知道的。

Your Job

Modify bmap() so that it implements a doubly-indirect block, in addition to direct blocks and a singly-indirect block.

You’ll have to have only 11 direct blocks, rather than 12, to make room for your new doubly-indirect block; you’re not allowed to change the size of an on-disk inode.

The first 11 elements of ip->addrs[] should be direct blocks; the 12th should be a singly-indirect block (just like the current one); the 13th should be your new doubly-indirect block. You are done with this exercise when bigfile writes 65803 blocks and usertests runs successfully.

感想

意外地很简单（）在此不多做赘述，直接上代码。

唯一要注意的一点就是记得在itrunc中free掉

image-20230124232433793

代码

修改定义
1
2
3
4
5
6
7
8
9
10
11
// in fs.h
#define NDIRECT 11
#define NINDIRECT (BSIZE / sizeof(uint))
#define NDOUBLEINDIRECT ((BSIZE/sizeof(uint))*(BSIZE/sizeof(uint)))
#define MAXFILE (NDIRECT + NINDIRECT + NDOUBLEINDIRECT)

// On-disk inode structure
struct dinode {
  // ...
  uint addrs[NDIRECT+2];   // Data block addresses
};
1
2
3
4
5
6
// in file.h
// in-memory copy of an inode
struct inode {
  // ...
  uint addrs[NDIRECT+2];
};
修改bmap()
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
60
61
62
63
// in fs.c
// 调试用
static int cnt = 0;

static uint
bmap(struct inode *ip, uint bn)
{
  uint addr, *a;
  struct buf *bp;

  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 if necessary.
    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;
  }
    
  // CODE HERE
  bn -= NINDIRECT;
  if(bn < NDOUBLEINDIRECT){
    // 调试用
    if(bn/10000 > cnt){
      cnt++;
      printf("double_indirect:%d\n",bn);
    }
    // 第一层
    if((addr = ip->addrs[NDIRECT+1]) == 0)
      ip->addrs[NDIRECT+1] = addr = balloc(ip->dev);
    // 第二层
    bp = bread(ip->dev,addr);
    a = (uint*)bp->data;
    if((addr = a[(bn >> 8)]) == 0){
      a[(bn >> 8)] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    // 第三层
    bp = bread(ip->dev,addr);
    a = (uint*)bp->data;
    if((addr = a[(bn & 0x00FF)]) == 0){
      a[(bn & 0x00FF)] = addr = balloc(ip->dev);
      log_write(bp);
    }
    brelse(bp);
    return addr;
  }

  panic("bmap: out of range");
}
修改itrunc
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
// Truncate inode (discard contents).
// Caller must hold ip->lock.
void
itrunc(struct inode *ip)
{
  int i, j;
  struct buf *bp;
  uint *a;

  for(i = 0; i < NDIRECT; i++){
    if(ip->addrs[i]){
      bfree(ip->dev, ip->addrs[i]);
      ip->addrs[i] = 0;
    }
  }

  if(ip->addrs[NDIRECT]){
    bp = bread(ip->dev, ip->addrs[NDIRECT]);
    a = (uint*)bp->data;
    for(j = 0; j < NINDIRECT; j++){
      if(a[j])
        bfree(ip->dev, a[j]);
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT]);
    ip->addrs[NDIRECT] = 0;
  }

  // CODE HERE
  if(ip->addrs[NDIRECT+1]){
    bp = bread(ip->dev, ip->addrs[NDIRECT+1]);
    a = (uint*)bp->data;
    // 双层循环
    for(j = 0; j < NINDIRECT; j++){
      if(a[j]){
        struct buf* tmp_bp = bread(ip->dev,a[j]);
        uint* tmp_a = (uint*)tmp_bp->data;
        for(int k = 0;k < NINDIRECT; k++){
          if(tmp_a[k])
            bfree(ip->dev,tmp_a[k]);
        }
        brelse(tmp_bp);
        bfree(ip->dev,a[j]);
      }
    }
    brelse(bp);
    bfree(ip->dev, ip->addrs[NDIRECT+1]);
    ip->addrs[NDIRECT+1] = 0;
  }

  ip->size = 0;
  iupdate(ip);
}

In this exercise you will add symbolic links to xv6.

Symbolic links (or soft links) refer to a linked file by pathname; when a symbolic link is opened, the kernel follows the link to the referred file.

Symbolic links resembles hard links, but hard links are restricted to pointing to file on the same disk, while symbolic links can cross disk devices.

Although xv6 doesn’t support multiple devices, implementing this system call is a good exercise to understand how pathname lookup works.

You will implement the symlink(char *target, char *path) system call, which creates a new symbolic link at path that refers to file named by target. For further information, see the man page symlink. To test, add symlinktest to the Makefile and run it.

linux：硬链接和软链接

硬链接不会创建新的物理文件，但是会使得当前物理文件的引用数加1。当硬链接产生的文件存在时，删除源文件，不会清除实际的物理文件，即对于硬链接“生成的新文件”不会产生任何影响。

软链接就更像一个指针，只是指向实际物理文件位置，当源文件移动或者删除时，软链接就会失效。

【所以说，意思就是软链接不会让inode->ulinks++的意思？】

感想

这个实验比上个实验稍难一些，但也确实只是moderate的水平，其复杂程度主要来源于对文件系统的理解，还有如何判断环，以及对锁的获取和释放的应用。我做这个实验居然是没看提示的【非常骄傲<-】，让我有一种自己水平上升了的感觉hhh

正确思路

本实验要求实现软链接。首先需要实现创建软链接：写一个系统调用 symlink(char *target, char *path) 用于创建一个指向target的在path的软链接；然后需要实现打开软链接进行自动的跳转：在sys_open中添加对文件类型为软链接的特殊处理。

初见思路

我的初见思路是觉得可以完全参照sys_link来写。但其实还是很不一样的。

sys_link的逻辑：

  1. 获取old的inode
  2. 获取new所在目录的inode，称为dp
  3. 在dp中添加一项entry指向old

sys_symlink的逻辑：

  1. 通过path创建一个新的inode，作为软链接的文件

    这里选择新建inode，而不是像link那样做，主要还是为了能遵从symlinktest给的接口使用方法（朴实无华的理由）。而且这么做也很方便，符合“一切皆文件”的思想，也能简单化对其在open中的处理。

  2. 在inode中填入target的地址

    我们可以把软链接视为文件，文件内容是其target的path。

可以说是毫不相干，所以还是直接自起炉灶比较好。

一些错误

其实没什么好说的，虽然debug过程挺久，但是靠常规的printf追踪就都可以看出来是哪里错了。下面我说说一个我印象比较深刻的吧。

symlinktest中有一个检测点是，软链接不能成环，也即b->a->b是非法的。于是，我就选择了用快慢指针来检测环形链表这个思想，用来看是否出现环。

在symlinktest的另一个检测点中：

image-20230125173143735

我出现了如下错误：

image-20230125162542807

此时的结构是1[27]->2[28]->3[29]->4，[]内为inode的inum。

快慢指针的实现方式是当cnt为奇数的时候，慢指针才会移动。而上图中，cnt==0时，两个指针的值都发生了变化，这就非常诡异。

这其实是因为slow指针所指向的那个inode被释放了，然后又被fast指针的下一个inode捡过来用了，从而导致值覆盖。

为什么会被释放呢？

1
2
3
4
5
6
7
8
9
      // 快指针移动
      readi(ip,0,(uint64)path,0,MAXPATH);
      iunlock(ip);
      if((ip = namei(path)) == 0){
        end_op();
        return -1;
      }
// 在这里！！！
      ilockput(ip);

在这里，我错误地调用了ilockput，从而使inode的ref–，使得它在下一次fast指针调用namei，namei调用iget时，该inode被当做free inode使用，于是就这么寄了。

所以我们需要把ilockput的调用换成ilock，这样一来就能防止inode被free。至于什么时候再iput？我想还是交给操作系统启动时的清理工作来做吧23333【开摆】

代码

image-20230125165612112

添加定义
fcntl.c

open参数

1
2
// 意为只用获取软链接文件本身，而不用顺着软链接去找它的target文件
#define O_NOFOLLOW 0x100
stat.h

文件类型

1
2
3
4
#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device
#define T_SYMLINK  4   // symbol links
添加sys_symlink系统调用
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
// in sysfile.c
uint64
sys_symlink(void)
{
  char target[MAXPATH], path[MAXPATH];
  struct inode *ip;

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

  begin_op();

  // 创建软链接结点
  ip = create(path,T_SYMLINK,0,0);
  //printf("symlink:before writei,inum = %d\n",ip->inum);
  // 此处可以防止住一些并发错误
  if(ip ==0){
    end_op();
    return 0;
  }
  // 向软链接结点文件内写入其所指向的路径
  writei(ip,0,(uint64)target,0,MAXPATH);
  //printf("symlink:after writei\n");
    
  // 软链接不需要让nlink++
    
  // 记得要释放在create()中申请的锁
  iunlockput(ip);

  end_op();

  return 0;
}
修改open
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
uint64
sys_open(void)
{
  // ...

  begin_op();

  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    if(ip == 0){
      end_op();
      return -1;
    }
  } else {
    // 软链接不可能是以O_CREATE的形式创建的
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ilock(ip);
    if(ip->type == T_DIR && omode != O_RDONLY){
      iunlockput(ip);
      end_op();
      return -1;
    }

    // 修改从这里开始
    // 快慢指针
    // ip为快指针，slow为慢指针
    uint cnt = 0;
    struct inode* slow = ip;
    // 可能有多重链接，因而需要持续跳转
    while(ip->type == T_SYMLINK){
      //printf("slow = %d,fast = %d,cnt = %d\n",slow->inum,ip->inum,cnt);
      // 其实这个只需要检测一次就够了。但为了编码方便，仍然把它保留在while循环中
      if(omode & O_NOFOLLOW){
        break;
      }else{
        // 检测到cycle
        if(slow == ip && cnt!=0){
          iunlockput(ip);
          end_op();
          return -1;
        }
        // 快指针移动
        readi(ip,0,(uint64)path,0,MAXPATH);
        // 此处不能用iunlockput()，具体原因见 感想-一些错误
        iunlock(ip);
        if((ip = namei(path)) == 0){
          end_op();
          return -1;
        }
        ilock(ip);
        // 慢指针移动
        // 注意，我慢指针移动的时候没有锁保护，因为用锁太麻烦了（）其实还是用锁比较合适
        if(cnt & 1){
          //printf("%d\n",cnt);
          readi(slow,0,(uint64)path,0,MAXPATH);
          if((slow = namei(path) )== 0){
            end_op();
            return -1;
          }
        }
        cnt++;
      }
    }
    // 当跳出循环时，此时的ip必定是锁住的
  }

  if(ip->type == T_DEVICE && (ip->major < 0 || ip->major >= NDEV)){
    iunlockput(ip);
    end_op();
    return -1;
  }
  // ...
}

Lab mmap

The mmap and munmap system calls allow UNIX programs to exert detailed control over their address spaces.

They can be used to:

  1. share memory among processes
  2. map files into process address spaces
  3. as part of user-level page fault schemes such as the garbage-collection algorithms discussed in lecture.

In this lab you’ll add mmap and munmap to xv6, focusing on memory-mapped files.

mmap是系统调用，在用户态被使用。我们这次实验仅实现mmap功能的子集，也即memory-mapped files。

declaration for mmap:

1
2
void *mmap(void *addr, size_t length, int prot, int flags,
     int fd, off_t offset);

  1. 参数

    1. addr is always zero.

      You can assume that addr will always be zero, meaning that the kernel should decide the virtual address at which to map the file.【addr由kernel决定，因而用户态只需传入0即可】

    2. length is the number of bytes to map

      Might not be the same as the file’s length.

    3. prot indicates whether the memory should be mapped readable, writeable, and/or executable.

      you can assume that prot is PROT_READ or PROT_WRITE or both.

    4. flags has two values.

      1. MAP_SHARED

        meaning that modifications to the mapped memory should be written back to the file,

        如果标记为此，则当且仅当file本身权限为RW或者WRITABLE的时候，prot才可以标记为PROT_WRITE

      2. MAP_PRIVATE

        meaning that they should not.

        如果标记为此，则无论file本身权限如何，prot都可以标记为PROT_WRITE

    5. You can assume offset is zero (it’s the starting point in the file at which to map)

  2. return

    mmap returns that kernel-decided address, or 0xffffffffffffffff if it fails.

如果两个进程同时对某个文件进行memory map，那么这两个进程可以不共享物理页面。

munmap(addr, length) should remove mmap mappings in the indicated address range.

If the process has modified the memory and has it mapped MAP_SHARED, the modifications should first be written to the file. 【如果两个进程的修改发生冲突了怎么办？】

An munmap call might cover only a portion of an mmap-ed region, but you can assume that it will either unmap at the start, or at the end, or the whole region (but not punch a hole in the middle of a region).

感想

这个实验做得我……怎么说，感觉非常地难受吧。虽然我认为我这次做得挺不错的，因为我没有怎么看hints，我的代码差不多全都是我自己想出来的，没有依赖保姆级教学，我认为是一个很好的进步。不过，正因为我没有看hints，导致我的想法比起答案来思路非常地奇诡，导致我第一次错误想法写了一天，看了hints后决心痛改前非，结果第二次错误想法又写了一天emmm

下面的第一个代码版本虽然可以过掉mmaptest，但确实还是有一个很致命的bug，并且lazy也没有lazy到位，最后的版本离正确思路还有偏差，也就是下面放的第一个代码版本是错误的，但我认为它也不是完全没有亮点。第二个版本才是经过改正的正确版本，但写得着实有点潦草。

笔记整理得也有点匆忙，毕竟我真的话比较多而且心里很烦。总之，先记录我的全部思路过程，至于价值如何，先不管了2333

初见思路

所以说，我们要做的，就是实现一个系统调用mmap，在mmap中，应该首先申请几页用来放file的内容，并且在页表中填入该项，然后再返回该项的虚拟地址。然后在munmap中，再将该file页内容写入file。

也就是说，直接在mmap把文件的全部内容写入内存，然后各进程读写自己的那块内容块，最后在munmap的时候把修改内容写入文件然后释放该内存块就行了

问题：在哪里放置file的内容

题目要求the kernel should decide the **virtual address** at which to map the file.也就是说，在我们的mmap中，需要决定我们要讲文件内容放在哪里。那要放在哪呢……

我第一反应很奇葩：扫描页表，找到空闲页。但我自己也知道这样不可行，文件内容不止一页，这种零零散散存储需要的数据结构实现起来太麻烦了。

那怎么办？可以在heap内分配。那么到底怎么样才能在heap里分配？你该怎么知道heap哪里开始是空闲的，哪里是用过的，不还是得扫描页表吗？【思维大僵化】

其实……道理很简单。我们之间把proc->sz作为mapped-file的起始地址就好了。相信看到这里，你也明白这是什么原理了。能想到这个，我感觉确实很不容易。

正确思路

初见思路虽然简单，但是很粗暴，如果文件很大，宝贵的内存空间就会被我们浪费。所以我们借用lazy allocation的思想，先建立memory-file的映射，再在缺页中断中通过文件读写申请内存空间，把文件内容读入内存。

问题就在于如何“先建立memory-file的映射”。在lazy allocation中，我们是先填好所有的对应页表项，仅是不申请对应的物理内存，也即占着XX不XX。在这次实验中，我们也是这么做，只不过新增了一个难点，那就是如何管理这些页。因为lazy allocation页与页之间没有比较紧密的关系，但是在mmap中页却可以被所属文件这个关键字划分。因而，我们需要一个数据结构，来给页分门别类地组织在一起，并且记录它们的meta data比如说所属文件之类的，这也就是hints里的VMA结构，也即我的filemap结构。

我们可以将这样的数据结构池化，并且存储在proc域中，以避免对象的重复创建。

我的lazy法与别人不大一样……我没有想得像他们那么完美。我的做法是，在需要读某个地址的文件内容时，直接确保这个地址前面的所有文件内容都读了进来。也即在filemap中维护一个okva，表明vaokva这段内存已经读入，之后就仅需再读入okvaneed_va这段地址就行。这样虽然lazy了，但没完全lazy。

我认为这不能体现lazy的思想……因为一读读一坨，还是很占空间啊。

因而，我们需要做的就是：

  1. 在mmap中将信息填入该数据结构

    1. 依据传入的长度扩容proc，原sz作为mapped-file起始地址va
    2. 从对象池中寻找到一个空闲的filemap，对其填写信息
    3. 返回1所得的va

    在我的代码中，还针对proc->sz不满足page-align做出了对策：先把文件的PGROUNDUP(sz)-sz这部分的信息读入，并且更新okva，这样一来，之后在usertrap中，就可以从okva开始一页页地分配地址，做到自然地page-align了。

    为什么要对不满足page-align的情况进行处理？

    这是因为，growproc的时候一次性扩充一页，但proc->sz却可以不满足page-align，也就是说，proc->sz所处的这一页已经被分配了。

    在我们的lazy思路中，我们如果不预先读入文件页，是只能等待用户陷入缺页中断的情况下才能读入文件内容。

    但是，proc->sz这一页已经被分配了。因而，在用户态读取这一页地址的时候，并不会发生缺页中断。因而，就会发生文件内容未读入，用户读到脏数据的情况。

    其实还有一种更简单的办法可以强制page-align，那就是，直接让起始地址为PGROUNDUP(proc->sz)……至于为什么我不用这个，而要写这么多麻烦的东西呢？答案是我没想到。（）

  2. 在usertrap增加对缺页中断的处理

    1. 依据va找到对应filemap
    2. 根据对应filemap的信息，使用readi（正确）fileread（错误）读取文件内容并存入物理内存

  3. 在munmap中进行释放

    1. 根据标记写入文件页，并且释放对应物理内存
    2. 修改filemap结构的参数，并且在其失效的时候放回对象池

  4. 修改fork和exit

    1. exit

      手动释放map-file域

      为什么不能把这些合并到wait中调用的freepagetable进行释放呢？

      因为freepagetable只会释放对应的物理页，没有达到munmap减少文件引用等功能。

    2. fork

      手动复制filemap池

我的错误思路们

第一次错误思路

上面说到：

问题就在于如何“先建立memory-file的映射”。在lazy allocation中，我们是先填好所有的对应页表项，仅是不申请对应的物理内存，也即占着XX不XX。在这次实验中，我们也是这么做，只不过新增了一个难点，那就是如何管理这些页。因为lazy allocation页与页之间没有比较紧密的关系，但是在mmap中页却可以被所属文件这个关键字划分。因而，我们需要一个数据结构，来给页分门别类地组织在一起，并且记录它们的meta data比如说所属文件之类的，这也就是hints里的VMA结构，也即我的filemap结构。

官方给出的答案是在proc域里的pool。我……额……是把这些信息，存入在页中（真是自找麻烦呀）

具体来说，就是，我在mmap的时候给每个文件申请一页，然后在页的开头填上和filemap结构相差无几的那些参数，再加上一个next指针，表示下一个文件页的地址。页的剩下部分就用来存储数据。总的就是一个链表结构。

这个思路其实很不错，比起上面的直接在proc内存的尾巴扩容，这个空间利用率应该更大，并且不仅能节省物理内存，还能节省虚拟地址空间，实现了lazy上加lazy。

但问题是……我为什么非要傻瓜式操纵内存，在页的开头填入参数数据，而不是把这种页抽象为一个个node，最终形成一个十字链表的形式（差不多的意思，鱼骨状），组织进proc域，这样不挺好的吗……唔，有时候我头脑昏迷程度让我自己都感到十分震惊。归根结底，还是想得太少就动手了，失策。

总之放上代码。我没有实现next指针，仅假设文件内容不超过一页。也就是这一页开头在mmap中填meta data，其余部分在usertrap中填入文件内容。【这个分开的点也让我迷惑至极……】

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
60
61
62
#define ERRORADDR 0xffffffffffffffff

void* mmap(void* address,size_t length,int prot,int flags,struct file* file,uint64 offset){
    struct proc* p = myproc();
    // 获取va,也即真正的address
    uint64 va = p->sz;
    if(growproc(PGSIZE) < 0)
            return (void*)ERRORADDR;
    char* mem = kalloc();
    if(mem == 0){
            return (void*)ERRORADDR;
    }
    memset(mem, 0, PGSIZE);
    // 保存信息：file指针、prot（这就是傻瓜式操纵内存的典范）
    uint64* pointer = (uint64*)mem;
    *pointer = (uint64)file;
    pointer++;
    *pointer = (uint64)prot;
    pointer++;
    *pointer = (uint64)length;
    pointer++;
    *pointer = (uint64)flags;
    pointer++;
    *pointer = (uint64)offset;
    pointer++;
    filedup(file);

    if(mappages(p->pagetable, va+PGSIZE, PGSIZE, (uint64)mem, PTE_M|PTE_X|PTE_U) != 0){
      kfree(mem);
            return (void*)ERRORADDR;
    }
    // return start of free memory
    return (void*)(va + (uint64)pointer - (uint64)mem);
}
int munmap(void* address,size_t length){
    struct proc* p = myproc();
    pte_t *pte;
    uint64* pa;

    if((pte = walk(p->pagetable, (uint64)address, 0)) == 0)
            return -1;
    if((*pte & PTE_V) == 0 ||(*pte & PTE_M) == 0)
            return -1;
    // the start is where the params save
    pa = (uint64*)(PGROUNDDOWN(PTE2PA(*pte)));
    struct file* file = (struct file*)(*pa);
    pa++;
    int prot = (int)(*pa);
    pa++;
    pa++;
    int flags = (int)(*pa);
    pa++;
    pa++;

    if(flags == MAP_SHARED&&(prot&PROT_WRITE) != 0){
        // 需要更新写内容
        filewrite(file,(uint64)address,length);
    }
    // 最后释放内存
    uvmunmap(p->pagetable, PGROUNDDOWN((uint64)address), 1, 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
} else if(r_scause() == 13 || r_scause() == 15){
  uint64 va = r_stval();
  pte_t *pte;
  uint64* pa;
  uint flags;

  if((pte = walk(p->pagetable, va, 0)) == 0)
    p->killed = 1;
  else if((*pte & PTE_V) == 0 ||(*pte & PTE_M) == 0)
    p->killed = 1;
  else {
    // the start is where the params save
    pa = (uint64*)(PGROUNDDOWN(PTE2PA(*pte)));
    flags = PTE_FLAGS(*pte);
    struct file* file = (struct file*)(*pa);
    pa++;
    int prot = (int)(*pa);
    pa++;
    size_t length = (size_t)(*pa);
    pa++;
    pa++;
    pa++;

    if((prot&PROT_READ) != 0){
      fileread(file,va,length);
      flags |= PTE_R;
      if((prot&PROT_WRITE) != 0)    flags |= PTE_W;
      else if(r_scause() == 15)     p->killed = 1;
      *pte = ((*pte) | flags);
    } else  p->killed = 1;
  }
}
为什么下面的代码是错的

正如开头所说的那样，我并没有完美做好这次实验，下面代码有一个致命的bug。

先说说致命bug是什么。

我的filemap结构体其实隐藏了两个具有“offset”这一含义的状态。一个是filemap里面的成员变量offset，另一个是filemap里面的成员变量file的成员变量off：

1
2
3
4
5
6
7
8
9
// in proc.h
struct filemap{
  struct file* file;//文件
  uint64 offset;//va相对于file开头的offset
};
// in file.h
struct file {
  uint off;          // FD_INODE
};

在我的代码里，它们被赋予了不同的含义。

filemap->file->off被用于trap.c中，表示的是当前未读入文件内容的起始位置（实际上也就是okva-va的值），用于自然地使用fileread进行文件读入。

比如说，这次读入PGSIZE，那么off就会在fileread中自增PGSIZE。下次调用fileread就可以直接从下一个位置读入了，这样使代码更加简洁

filemap->offset被用于munmap中。filewrite同fileread一样，都是从file->off处开始取数据。munmap所需要取数据的起始位置和trap.c中需要取数据的起始位置肯定不一样，

想想它们的功能。trap.c的off需要始终指向有效内存段的末尾，但munmap由于要对特定内存段进行写入文件操作，因而off要求可以随机指向。

因而，我们可以将当前va对应的文件位置记录在offset中。届时，我们只需要从p->filemaps[i].offset+va-p->filemaps[i].va取数据就行。

上述两个变量相辅相成，看上去似乎能够完美无缺地实现我们的功能。但是，实际上，不行。为什么呢？因为它们的file指针，filemap->file，如果被两个mmap区域同时使用的话，就会出问题。

可以来看看mmaptest.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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
  makefile(f);
  if ((fd = open(f, O_RDONLY)) == -1)
    err("open");

  unlink(f);
  char *p1 = mmap(0, PGSIZE*2, PROT_READ, MAP_SHARED, fd, 0);
  char *p2 = mmap(0, PGSIZE*2, PROT_READ, MAP_SHARED, fd, 0);

  // read just 2nd page.
  if(*(p1+PGSIZE) != 'A')
    err("fork mismatch (1)");
  if((pid = fork()) < 0)
    err("fork");

  if (pid == 0) {
    // v1是用来触发缺页中断的函数
    _v1(p1);
    munmap(p1, PGSIZE); // just the first page
    exit(0); // tell the parent that the mapping looks OK.
  }

  int status = -1;
  wait(&status);

  if(status != 0){
    printf("fork_test failed\n");
    exit(1);
  }

  // check that the parent's mappings are still there.
  printf("before v1,p1 = %d\n",(uint64)p1);
  _v1(p1);
  printf("after v1,p1 = %d\n",(uint64)p1);
  _v1(p2);


  printf("fork_test OK\n");

/*输出：
fork_test starting
trap:map a page at 53248,okva = 53248
trap:mem[0]=65,off = 4096,size = 6144
trap:map a page at 57344,okva = 53248
trap:mem[0]=65,off = 6144,size = 6144
before v1,p1 = 53248
after v1,p1 = 53248
trap:map a page at 61440,okva = 61440
trap:mem[0]=0,off = 6144,size = 6144
mismatch at 0, wanted 'A', got 0x0
mmaptest: fork_test failed: v1 mismatch (1), pid=3
*/
1
2
3
4
5
6
7
// in trap.c
printf("trap:map a page at %d,okva = %d\n",start_va,p->filemaps[i].okva);

fileread(p->filemaps[i].file,start_va,PGSIZE);

printf("trap:mem[0]=%d,off = %d,size = %d\n",
       mem[0],p->filemaps[i].file->off,p->filemaps[i].file->ip->size);

这段代码因为共用fd，导致file指针被两个mmap区域同时使用。

共用fd，为什么file指针也一起共用了？

可以追踪一下它们的生命周期：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// in sys_open()
// 获取file结构体和文件描述符。
if((f = filealloc()) == 0 || (fd = fdalloc(f)) < 0){

// in sysfile.c
// Allocate a file descriptor for the given file.
// Takes over file reference from caller on success.
static int
fdalloc(struct file *f)
{
int fd;
struct proc *p = myproc();

for(fd = 0; fd < NOFILE; fd++){
 if(p->ofile[fd] == 0){
   p->ofile[fd] = f;
   return fd;
 }
}
return -1;
}

可以看到，它实际上是有一个文件描述符表，key为fd，value为file指针。因而，同一张表，fd相同，file指针相同。

注：父子进程，同样的fd，file指针也是相同的

fork出来的父子进程同一个句柄对同一个文件的偏移量是相同的，这个原理应该是因为，父子进程共享的是文件句柄这个结构体对象本身，也就是拷贝的时候是浅拷贝而不是深拷贝。

1
2
3
4
5
// in fork()
// increment reference counts on open file descriptors.
for(i = 0; i < NOFILE; i++)
 if(p->ofile[i])
   np->ofile[i] = filedup(p->ofile[i]);

最后的check that the parent's mappings are still there.环节中，_v1(p1)执行时并没有陷入trap，这是正常的。不正常的是_v1(p2)的执行结果。它陷入了trap，但是却因file->off == file size，导致被判定为已全部读入文件，事实上却是并没有读入文件。

为什么会这样呢？

这是因为p1和p2共用同一个fd，也就共用了同一个file指针。共用了一个file指针，那么p1和p2面对的file->off相同。上面说到，file->off用于控制文件映射。那么，当p1完成了对文件的映射，p1的off指针如果不加重置，就会永远停留在file size处。这样一来，当p2想要使用同样的file指针进行文件映射时，就会出问题。

这个问题的一个解决方法是每次mmap都深拷贝一个船新file结构体。但是这样的话，file域里的ref变量就失去了它的意义，并且file对象池应该也很快就会爆满，非常不符合设计方案。

这个问题的完美解，是不要赋予file->off这个意义，而是使用readi替代fileread。

1
2
fileread(struct file *f, uint64 addr, int n)
readi(struct inode *ip, int user_dst, uint64 dst, uint off, uint n)

这样做的好处是，我们可以实时计算offset（前面提到，其恰恰等于okva-va），而不用把这个东西用file的off来表示。

也确实，我之所以弯弯绕绕那么曲折，是因为只想到了fileread这个函数，压根没注意到还有一个readi……

我在下面的代码仅做了一个能够通过测试，但是上面的bug依然存在的功利性折中代码。我是这么实现的：

1
2
3
4
// 在`mmap`的时候初始化`file->off`
p->filemaps[i].file->off = offset;
// 在`munmap`的时候清零`file->off`
p->filemaps[i].file->off = 0;

因而，结论是，一步错步步错，一个错误需要更多的错误来弥补，最后还是错的（悲）

如何把下面的错误思路改成正确思路

可以做以下几点：

  1. 正确地lazy

    每次trap仅分配一页。

  2. 改用readi函数，修改file->off的语义

这样一来，大概就可以完美地正确了。

其他的一些小细节

file指针的生命周期

在数据结构中存储file指针至关重要。但仔细想一想，file指针的生命周期似乎长到过分：从sys_mmap被调用，一直到usertrap处理缺页中断，最后到munmap释放，我们要求file指针的值需要保持稳定不变。

这么长的生命周期，它真的可以做到吗？毕竟file指针归根到底只是一个局部变量，在syscall mmap结束之后，它还有效吗？答案是有效的，这个有效性由mmap实现中对ref的增加来实现保障。

在用户态中关闭一个文件，需要使用syscallclose(int fd)。不妨来看看close的代码。

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
// in kernel/sysfile.c
uint64
sys_close(void)
{
int fd;
struct file *f;

if(argfd(0, &fd, &f) < 0)
 return -1;
// 一个进程打开的文件都会放入一个以fd为index的文件表里，
// 在xv6中，这个文件表便是`myproc()->ofile`。
// 可以看到，关闭一个文件首先需要把它移出文件表
myproc()->ofile[fd] = 0;
// 对file指针关闭的主要操作
fileclose(f);
return 0;
}

// in kernel/file.c
// Close file f.  (Decrement ref count, close when reaches 0.)
void
fileclose(struct file *f)
{
struct file ff;

acquire(&ftable.lock);
// 若ref数<0，就会直接return
if(--f->ref > 0){
 release(&ftable.lock);
 return;
}
// 释放file
// close不会显式地释放file指针，只会释放file指针所指向的文件，让file指针失效。
ff = *f;
f->ref = 0;
f->type = FD_NONE;
release(&ftable.lock);

if(ff.type == FD_PIPE){
 pipeclose(ff.pipe, ff.writable);
} else if(ff.type == FD_INODE || ff.type == FD_DEVICE){
 begin_op();
 iput(ff.ip);
 end_op();
}
}

可以看到，当ref数>1时，file指针就不会失效。

这就是为什么我们还需要在mmap中让file的ref数++。

缺页中断蕴含的设计思想

如果只存入file指针，用户态要如何对对应的文件进行读写呢？

我们可以自然想到也许需要设计一个函数，让用户在想要对这块内存读写的时候调用这个函数即可。但是，这样的方法使得用户对内存不能自然地读写，还需要使用我们新设计的这个函数，这显然十分地不美观。所以，我们需要找到一个方法，让上层的用户可以统一地读取任何的内存块，包括memory-mapped file内存块，而隐藏memory-mapped file与其他内存块读写方式不同的这些复杂细节。经历过前面几次实验的你看到这里一定能想到，有一个更加优美更加符合设计规范的方法，那就是：缺页中断！

没做这个实验之前就知道mmap需要借助缺页中断来实现了，但实际自己的第一印象是觉得并不需要缺页中断，直到分析到这里才恍然大悟。

“让上层的用户可以统一地读取任何的内存块，而隐藏不同类型的内存块读写方式不同的这些复杂细节”

仔细想想，前面几个关于缺页中断的实验，比如说cow fork，lazy allocation，事实上都是基于这个思想。它们并不是不能与缺页中断分离，只是有了缺页中断，它们的实现更加简洁，更加优美。

再次感慨os的博大精深。小小一个缺页中断，原理那么简单，居然集中了这么多设计思想，不禁叹服。

正确答案的munmap中如果遇到未映射的页怎么办

在正确答案的munmap中：

1
2
3
4
5
6
7
8
9
//释放已经申请的页表项、内存，并且看看是不是需要写回
while(start_va < bounder){
  if(p->filemaps[i].flags == MAP_SHARED){
    //写回
    filewrite(p->filemaps[i].file,start_va,PGSIZE);
  }
  uvmunmap(p->pagetable,start_va,1,1);
  start_va += PGSIZE;
}

如果map类型为MAP_SHARED，并且该页尚未映射，会怎么样呢？

追踪filewrite的路径

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
// in file.c
	  begin_op();
      ilock(f->ip);
      if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
        f->off += r;
      iunlock(f->ip);
      end_op();
// in fs.c
    if(either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
      brelse(bp);
      break;
    }
    log_write(bp);
// in vm.c copyin()
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
// ...

copyin最终会在 if(pa0 == 0) return -1;这里终结，但writei并不会在接收到-1的时候爆出panic或者是引发缺页中断，而只会把它当做文件结尾，默默地返回。

并且，在munmap中是一页一页地释放，而不是直接传参length全部释放，这一点也很重要。因为我们的lazy allocation很可能导致va~va+length这一区间内只是部分页被映射，部分页没有。如果直接传参length释放，那么在遇到第一页未被映射的时候，filewrite就会终止，该页之后的页就没有被写回文件的机会了。

所以结论是，在正确实现的munmap中遇到未映射的页会自动跳过，什么也不会发生。

代码

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// in param.h
#define NFILEMAP 32

// in proc.h
struct filemap{
  uint isused;//对象池思想。该filemap是否正在被使用
  uint64 va;//该文件的起始内存页地址
  uint64 okva;//该文件的起始未被读入部分对应的内存地址
  struct file* file;//文件
  size_t length;//需要映射到内存的长度
  int flags;//MAP_SHARED OR MAP_PRIVATE
  int prot;//PROT_READ OR PROT_WRITE
  uint64 offset;//va相对于file开头的offset
};

// Per-process state
struct proc {
  struct filemap filemaps[NFILEMAP];
};

mmap

具体系统调用注册过程略。

1
2
3
4
5
6
7
8
9
10
// in sysproc.c
uint64
sys_mmap(void){
  uint64 addr;
  int length,prot,flags,offset;
  struct file* file;
  if(argaddr(0,&addr) < 0 || argint(1,&length) < 0 || argint(2,&prot) < 0 || argint(3,&flags) < 0 || argfd(4,0,&file) ||argint(5,&offset) < 0)
    return -1;
  return (uint64)mmap((void*)addr,(size_t)length,prot,flags,file,(uint)offset);
}
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
#define ERRORADDR 0xffffffffffffffff

// 映射file从offset开始长度为length的内容到内存中，返回内存中的文件内容起始地址
void* mmap(void* address,size_t length,int prot,int flags,struct file* file,uint64 offset){
    // mmap的prot权限必须与file的权限对应，不能file只读但是mmap却可写且shared
    if((prot&PROT_WRITE) != 0&&flags == MAP_SHARED &&file->writable == 0)       
        return (void*)ERRORADDR;
    
    struct proc* p = myproc();
    uint64 va = 0;
    int i=0;
    
    //找到filemap池中第一个空闲的filemap
    for(i=0;i<NFILEMAP;i++){
      if(!p->filemaps[i].isused){
        // 获取va,也即真正的address
        va = p->sz;
        p->sz += length;
        // 其实这里用一个memcpy会更加优雅，可惜我忘记了（）
        p->filemaps[i].isused = 1;
        p->filemaps[i].va = va;
        p->filemaps[i].okva = va;
        p->filemaps[i].length = length;
        p->filemaps[i].prot = prot;
        p->filemaps[i].flags = flags;
        p->filemaps[i].file = file;
        p->filemaps[i].file->off = offset;
        p->filemaps[i].offset = offset;
        // 增加文件引用数
        filedup(file);
        break;
      }
    }
    if(va == 0)  return (void*)ERRORADDR;
    // return start of free memory
    uint64 start_va = PGROUNDUP(va);
    // 先读入处于proc已申请的内存页区域（也即没有内存对齐情况下）
    uint64 off = start_va - va;
    if(off < PGSIZE){
        fileread(file,va,off);
        file->off += off;
        p->filemaps[i].okva = va+off;
    }
    return (void*)va;
}

usertrap

错的
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
} else if(r_scause() == 13 || r_scause() == 15){
   uint64 va = r_stval();

   for(int i=0;i<NFILEMAP;i++){
       // 找到va对应的filemap
     if(p->filemaps[i].isused&&va>=p->filemaps[i].va 
        && va<p->filemaps[i].va+p->filemaps[i].length){
       // 说明本来就不应该写
       if(r_scause() == 15 && ((p->filemaps[i].prot)&PROT_WRITE) == 0){
         p->killed = 1;
         break;
       }
       //说明地址不在文件范围内
       if(p->filemaps[i].va+p->filemaps[i].file->ip->size <= va){
         p->killed = 1;
         break;
       }
       // 能进到这里来的都是产生了缺页中断，也就是说va对应文件数据不存在
       // 我们需要维护一个okva，表示从filemaps.va到okva这段地址已经加载了文件
       // 这样一来，我们这里就只需加载okva~va地址对应的文件了
       // file结构体自带的off成员会由于fileread而自动增长到对应位置，所以文件可以自然地读写
       uint64 start_va = p->filemaps[i].okva;// okva一定是page-align的
       // 加载文件内容
       while(start_va <= va){
         char* mem = kalloc();
         if(mem == 0){
           p->killed = 1;
           break;
         }
         memset(mem, 0, PGSIZE);
         int flag = PTE_X|PTE_R|PTE_U;
         if(((p->filemaps[i].prot)&PROT_WRITE) != 0){
           flag |= PTE_W;
         }
         if(mappages(p->pagetable, start_va, PGSIZE, (uint64)mem, flag) != 0){
           p->killed = 1;
           kfree(mem);
           break;
         }
         // 读入文件内容
         fileread(p->filemaps[i].file,start_va,PGSIZE);
         start_va += PGSIZE;
       }
       p->filemaps[i].okva = start_va;
       break;
     }
   }
 }
对的
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
} else if(r_scause() == 13 || r_scause() == 15){
  uint64 va = r_stval();
  for(int i=0;i<NFILEMAP;i++){
    if(p->filemaps[i].isused&&va>=p->filemaps[i].va && va<p->filemaps[i].va+p->filemaps[i].length){
      if(r_scause() == 15 && ((p->filemaps[i].prot)&PROT_WRITE) == 0){
        // 说明本来就不应该写
        p->killed = 1;
        break;
      }
      if(p->filemaps[i].va+p->filemaps[i].file->ip->size <= va){
        //说明地址不在文件范围内
        p->killed = 1;
        break;
      }
      uint64 start_va = PGROUNDDOWN(va);
        char* mem = kalloc();
        if(mem == 0){
          p->killed = 1;
          break;
        }
        memset(mem, 0, PGSIZE);
        int flag = PTE_X|PTE_R|PTE_U;
        if(((p->filemaps[i].prot)&PROT_WRITE) != 0){
         flag |= PTE_W;
        }
        if(mappages(p->pagetable, start_va, PGSIZE, (uint64)mem, flag) != 0){
          p->killed = 1;
          kfree(mem);
          break;
        }
        readi(p->filemaps[i].file->ip,0,(uint64)mem,va-p->filemaps[i].va+p->filemaps[i].offset,PGSIZE);
      break;
    }
  }
}

munmap

错的
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
uint64 min(uint64 a,uint64 b){return a>b?b:a;}

// 释放文件映射以address为起始地址，length为长度这个范围内的内存地址空间
int munmap(void* address,size_t length){
    struct proc* p = myproc();
    uint64 va = (uint64)address;
    
    // 找到对应的filemap
    for(int i=0;i<NFILEMAP;i++){
      if(p->filemaps[i].isused&&p->filemaps[i].va<=va&&p->filemaps[i].va+length>va){
        // 开始释放的内存地址
        uint64 start_va;
        if(va == p->filemaps[i].va)
            start_va = PGROUNDUP(p->filemaps[i].va);
        else
            start_va = PGROUNDDOWN(va);
        // 结束释放的内存地址
        uint64 bounder = p->filemaps[i].va + min(p->filemaps[i].file->ip->size,length);
          
        //file的off在trap中用于表示文件已加载的位置
        //在这里需要用off进行filewrite，所以需要对原本在usertrap用于记录加载位置的off进行手动保存
        uint64 tmp_off = p->filemaps[i].file->off;
        p->filemaps[i].file->off = p->filemaps[i].offset+va-p->filemaps[i].va;

        //释放已经申请的页表项、内存，并且看看是不是需要写回
        while(start_va < bounder && start_va < p->filemaps[i].okva){
          if(p->filemaps[i].flags == MAP_SHARED){
            //写回
            filewrite(p->filemaps[i].file,start_va,PGSIZE);
          }
          uvmunmap(p->pagetable,start_va,1,1);
          start_va += PGSIZE;
        }

        //修改filemap结构体的起始地址va和长度，offset也要变，因为他记录va对应的是文件哪个位置
        if(va == p->filemaps[i].va){
          //释放的是头几页
          p->filemaps[i].offset += length;
          p->filemaps[i].va = va+length;
          p->filemaps[i].length -= length;
        }else {
          //释放的是尾几页
          p->filemaps[i].length -= p->filemaps[i].length - va;
        }
        p->filemaps[i].file->off = tmp_off;
        // 检验map的合理性
        if(p->filemaps[i].length == 0 || p->filemaps[i].va >= p->filemaps[i].va+length
                        || p->filemaps[i].file->off > p->filemaps[i].file->ip->size){
          p->filemaps[i].isused = 0;//释放
          
          // 注意！！！！这句话对我的错误代码来说非常重要
          p->filemaps[i].file->off = 0;
          fileclose(p->filemaps[i].file);
        }
      }
    }
    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
uint64 min(uint64 a,uint64 b){return a>b?b:a;}

int munmap(void* address,size_t length){
    struct proc* p = myproc();
    uint64 va = (uint64)address;
    for(int i=0;i<NFILEMAP;i++){
      if(p->filemaps[i].isused&&p->filemaps[i].va<=va&&p->filemaps[i].va+length>va){
        uint64 start_va;
        if(va == p->filemaps[i].va)
                start_va = PGROUNDUP(p->filemaps[i].va);
        else
                start_va = PGROUNDDOWN(va);
        uint64 bounder = p->filemaps[i].va + min(p->filemaps[i].file->ip->size,length);
        //在这里需要用off进行读写，所以需要对原本的加载处off手动保存
        uint64 tmp_off = p->filemaps[i].file->off;
        p->filemaps[i].file->off = p->filemaps[i].offset+va-p->filemaps[i].va;

        //释放已经申请的页表项、内存，并且看看是不是需要写回
        while(start_va < bounder){
          if(p->filemaps[i].flags == MAP_SHARED){
            //写回
            filewrite(p->filemaps[i].file,start_va,PGSIZE);
          }
          uvmunmap(p->pagetable,start_va,1,1);
          start_va += PGSIZE;
        }

        //修改filemap结构体的起始地址va和长度，offset也要变，因为他记录va对应的是文件哪个位置
        if(va == p->filemaps[i].va){
          //释放的是头几页
          p->filemaps[i].offset += length;
          p->filemaps[i].va = va+length;
          p->filemaps[i].length -= length;
        }else {
          //释放的是尾几页
          p->filemaps[i].length -= p->filemaps[i].length - va;
        }
        // 检验map的合理性
        if(p->filemaps[i].length == 0 || p->filemaps[i].va >= p->filemaps[i].va+length
                        || p->filemaps[i].file->off > p->filemaps[i].file->ip->size){
          p->filemaps[i].isused = 0;//释放
          fileclose(p->filemaps[i].file);
        }
        p->filemaps[i].file->off = tmp_off;
      }
    }
    return 0;
}

exit和fork

exit
1
2
3
4
5
6
// 关闭map-file
for(int i=0;i<NFILEMAP;i++){
  if(p->filemaps[i].isused){
    munmap((void*)(p->filemaps[i].va),p->filemaps[i].length);
  }
}
fork
1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<NFILEMAP;i++){
  np->filemaps[i].isused = p->filemaps[i].isused;
  np->filemaps[i].va = p->filemaps[i].va;
  np->filemaps[i].okva = p->filemaps[i].okva;
  np->filemaps[i].file = p->filemaps[i].file;
  np->filemaps[i].length = p->filemaps[i].length;
  np->filemaps[i].flags = p->filemaps[i].flags;
  np->filemaps[i].offset = p->filemaps[i].offset;
  np->filemaps[i].prot = p->filemaps[i].prot;
  if(np->filemaps[i].file)
    filedup(np->filemaps[i].file);
}

修改uvmcopy和uvmunmap

1
2
3
4
5
6
7
8
9
// in uvmunmap()
    if((*pte & PTE_V) == 0){
      *pte = 0;
      continue;
    }
// in uvmcopy()
    if((*pte & PTE_V) == 0)
      //panic("uvmcopy: page not present");
      continue;