Mit6.s081 Lec15: xv6 的 logging system

Logging layer

file system 设计的一大重要问题就是 crash recovery。这是因为文件系统操作往往涉及向磁盘多次写入，而几次写入之后的 crash 可能导致磁盘上的文件系统处于一个不一致的状态。

For example, suppose a crash occurs during file truncation (setting the length of a file to zero and freeing its content blocks). Depending on the order of the disk writes, the crash may either leave an inode with a reference to a content block that is marked free, or it may leave an allocated but unreferenced content block.

前者当系统重启之后,可能导致一个磁盘 block 被两个文件所对应，这是一个很严重的问题。

xv6 的解决方法是使用 logging（日志）。xv6 的系统调用不会直接向 on-disk file system data structure（例如 buffer 以及磁盘 block？）写入，而是将它所有希望执行的磁盘写入的描述放在磁盘的某个 log 中，once the system call has logged all of its writes, it writes a special commit record to the disk indicating that the log contains a complete operation（这里不知道怎么翻译好了）。此时，系统调用才将 disk write 应用到 on-disk file system data structure。当所有的写入操作完成后，系统调用会清除磁盘上的 log。

如果系统崩溃重启，那么 file-system 代码会在运行进程之前，先检查磁盘上的 log。如果 log 被标记为包含完整的操作，那么 file-system recovery code 会将 log 中的写操作应用到对应的 on-disk file system；否则 file-system recovery code 会直接清除 log，不执行写入操作。

如果 file system 恢复时看到 log 被标记为不包含完整操作，那么说明 log 中的写入操作都还没有应用到磁盘上，即磁盘没有发生真正的写入，因此直接清除 log 即可，不需要执行任何写入操作。

log 使得这些写入操作对 crash 来说是原子的，要么都没写入，要么全都写入到磁盘了。

Log design

log 存在于磁盘的 superblock 中，它由一个 header block 和后面的一系列 updated block copies（更新块的副本，又称 logged blocks） 组成。header block 包含一个扇区号（sector index）的数组，每个 sector index 对应一个 logged block，还包含着 log blocks 的数量。header block 中的计数要么为 $0$，说明 log 中不存在 transaction，要么不为 $0$，说明 log 包含一个完整的已、已提交的 transaction，并包含指定数量的 logged blocks。

xv6 在 transaction 提交时，向 header block 写入数据，在将 logged blocks 复制到 file system 之后，将 header block 的计数置为 $0$。

为了允许 file system 的操作被不同进程并发执行，日志系统（logging system）会将多个系统调用的写操作合并成一个 transaction。因此，单次的 commit 可能涉及多个完整的系统调用的写操作，为了避免一次系统调用被划分成两次 transaction，日志系统只会在没有 file-system 系统调用的时候进行 commit。

一次一起 commit 多个 transaction 的方法被称为 group commit，group commit 能通过平摊一次提交的开销到多次操作上来降低所需的磁盘操作数。

xv6 在磁盘上标识出了一段固定大小的空间用来存放 log。因此，系统调用要写入的 blocks 必须能被这块空间容纳。对 write 和 unlink 系统调用来说，这个限制可能会导致两个问题：

1. 假设 write 要写一个大文件，那么可能要写入许多 data blocks、bitmap blocks 和 inode blocks，unlink 一个大文件可能要写入许多 bitmap blocks 和 inode blocks。为了解决这一问题，xv6 的 write 会将一次大的写入划分成多个更小的适合 log 的写入操作，由于 xv6 只使用一个 bitmap lock，因此 unlink 不会造成问题；
2. 除非能确定系统调用的写入能容纳于 log 的剩余空间中，否则系统不会允许系统调用执行；

Code: logging

系统调用中的 log 的使用一般如下图所示：

begin_op wait until the logging system is not currently commiting, and until there is enough unreserved log space to hold the writes from this call. log.outstanding 会统计预订了 log space 的系统调用的数量，被预订的总空间就是 log.outstanding 乘上 MAXOPBLOCKS。递增 log.outstanding 会预订 log space，并且防止在此系统调用期间发生 commit。 xv6 保守地预计每个系统调用都会写入 MAXOPBLOCKS 个不同的 block。

事实上 等 end_op 完成 commit() 之后，begin_op 才会被唤醒，此时不仅是 log 被提交，更新也已经被应用到了磁盘。

log_write 表现得就像是 bwrite 的代理那样。它将 block 的 sector number 记录在内存中，在 disk 的 log 部分给这个 block 预留了一个槽位，并调用了 bpin(b) 来保证 buffer b 一定不会被 evict。

调用 log_write 时，调用者已经完成了对 buffer 的数据的修改； file system 中，bwrite 只会出现于 end_op 中； 调用 bpin(b) 之后，哪怕 buffer 缓存不足时，buffer b 也不会被换出，它修改了 buffer b 的 refcnt，之所以要这样设置，是因为假设 buffer b 中途被换出到磁盘，就违背了“必须 commit 之后再将写入应用到磁盘”的设定了，也就破坏了磁盘写入相对于 crash 的原子性。

void log_write(struct buf *b) {
    int i;

    acquire(&log.lock);
    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");

    for (i = 0; i < log.lh.n; i++) {
        if (log.lh.block[i] == b->blockno) // log absorption
            break;
    }
    log.lh.block[i] = b->blockno;
    if (i == log.lh.n) { // Add new block to log?
        bpin(b);
        log.lh.n++;
    }
    release(&log.lock);
}

在 commit 之前，block 必须要缓存在 buffer 上， 这是因为 buffer 唯一地记录着我们对这个 block 的修改；只有在 commit 之后，才可以将 buffer 写入磁盘上的位置；同一 transaction 的假设要读取这个 block，那么它必须能看到对这个 buffer 的修改。log_write 会注意到一个 transaction 中，多次写入同一个 block 的情况，如果是写入同一个 block，那么就不会添加新 block 到 log 中，而是在 log 中为该 block 分配相同的槽位。这种优化通常被称为 absorption（合并），这样的话，从 buffer 写入到 log 的槽位只会发生一次，即使写入 buffer 发生了很多次。

end_op 首先会减少未完成的系统调用的计数（说明有系统调用完成了），如果计数被递减到了 $0$，它就会通过调用 commit() 来提交当前的 transaction。这个过程分为四个阶段：

1. write_log 将每个在 transaction 被修改的 block 的 buffer 复制到 log 对应的槽位中（先复制到了 log 的 buffer 的对应的槽位中，然后将这个 log 的 buffer 写入到磁盘）
2. write_head 将 header block 从 buffer 写到磁盘中，而这就是 commit 的关键节点：
   • 当完成 header block 的从 buffer 写入到磁盘后，如果发生了 crash，那么恢复程序会从 log 中执行该次事务的写操作，将数据从 log 的 buffer 写入到磁盘；TODO(zwyyy)，如果 write_head 的 bwrite(buf) 发生了一半呢？
3. install_trans 会从 log 的 buffer 中读取每个 block 的 buffer，然后写入到文件系统（磁盘）；
4. end_op 将 log header 的计数重置为 $0$（说明 log 中不存在 transaction），这会在下一个 transaction 要写入 logged blocks 之前完成，这保证了 crash 恢复时，不会将前一个 transaction 的 header 与下一个 transaction 的 logged blocks 混在一起恢复，即保证了一次恢复不会涉及两个 transaction。

recover_from_log 会被 inilog 调用，而 initlog 会被 fsinit 调用，这个调用的时间点在第一个用户进程运行之前，即第一个用户进程运行之间，文件系统会进行自检。它会读取 log header，如果 log 包含一次已提交的 transaction，那么它会模拟 end_op 的操作。

使用 log 的例子可以参照 kernel/file.c 中的 filewrite，注意 writei 会调用 write_log：

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

同一个 transaction 中的并发系统调用

在 xv6 中，不同地系统调用来临时，如果 transaction 没有处于 committing，那么是可以有新的系统调用参与的，它们的执行顺序可以如下图：

这里，可以参与的系统调用数受到了一个限制：log.lh.n + (log.outstanding + 1) * MAXOPBLOCKS > LOGSIZE)，其中 log.lh.n 在 log_write 中是会增加的，由于 log space 在 commit 之前是不会被释放的，log.outstanding 只统计了未完成的系统调用数，end_op 递减 outstanding 不会释放对应的 log space，配合 log.lh.n 的限制，才真正避免了 log space 被撑爆。

如上图的调用顺序，在 begin_op 中可能不会发生 sleep（假设 log space 够用），因此 end_op 唤醒时，可能发现没有进程可以唤醒，但是无伤大雅。