前言

我本想把上篇中没讲完的剩余层全部在本篇中讲完，但没想到越写越多。日志层的代码不多，其思想和解决问题的手段也不算难以理解，但其背后涉及的原理和思想还是非常值得回味的，因此我打算用一整篇完整的blog来讲解日志层，并对其作出一点扩展。
本篇内容应该也会帮你对事务的拥有一个更好地理解。

聊聊xv6的文件系统（上篇）：https://www.cnblogs.com/KatyuMarisaBlog/p/14366115.html

浅谈一致性

警告：

本节内容我越写越觉得自己是个民科，整出了一套四不像的东西来强行糊弄自己，如果觉得这部分内容辣眼睛的话就请跳过吧（留下了蔡鸡的泪水）

《xv6 book》中告诉我们，文件系统必须支持crash recovery，即文件系统在访问文件的过程中如果经历断电等情况，经过重启仍然能够正常工作。更加严谨的说法是，文件系统在面临崩溃等情况后，仍然能够保证一致性。这里的一致性可能与我们所预想的定义有所出入。为了能够正确的理解日志层为文件系统提供的作用，我们必须首先正确理解本文中所谈及的一致性的具体含义。

首先我们给出wikipedia上关于一致性的严谨定义：

The semantic definition states that a theory is consistent if it has a model, i.e., there exists an interpretation under which all formulas in the theory are true.
The syntactic definition states a theory T is consistent if there is no formula φ such that both φ and its negation ??φ are elements of the set of consequences of T.
https://en.wikipedia.org/wiki/Consistency

将这个定义迁移到程序设计上，我个人给出我自己关于一致性的论述：对于一个系统M，定义其合法的操作集合P，并假设其当前状态为S，且一切的一致性约束条件都成立，如果经过操作p（p∈P）后状态转换为S’，且S’内部的一切约束性条件仍然成立，那么则称这个系统在操作集合P下能保持一致性。

现在将这个论述套用到文件系统上，设磁盘为我们的系统M，并设定对这个系统的操作集合P为xv6中的事务操作，设定一致性约束条件为磁盘的元数据能正确反映磁盘的状态，文件的元数据能正确反映文件的状态，这即是xv6文件系统的一致性模型。

这种定义可能比较拗口，既不像数学定义那样高度抽象且严谨，也没能做到让人容易理解。为了让这些定义更加形象一些，我们首先脑补一些可能会产生不一致状态的情景。

情景1：

假设释放盘块的操作的先后顺序为先置位图位为0，再将盘块的内容置零，且分配盘块时不再重置盘块的内容（因为认为释放盘块时空间已被置空了，无需重复操作），且没有日志层的支持。

考虑删除文件的操作。删除文件时，会将改文件所涉及的所有盘块一一释放。假设断电发生在置盘块bn的位图位为0后，将bn中的内容清零之前，然后系统重启，注意此时盘块bn的内容并没有被置空。如果这个盘块被分配了出去，则获得这个盘块的文件中就包含了前面那个文件被删除的数据，即脏数据，这一点便违背了一致性约束条件：文件的元数据必须能正确反映文件的状态。
当然我们有很多的办法可以避免这种情况，例如说盘块被分配时再执行一次清空操作、记录文件偏移值等等；

情景2：

仍然考虑删除文件的操作。阅读xv6的相关代码代码可知，文件系统通过struct inode实现对文件内容的读写，其中inode->addr记录着文件的内容所占据的盘块的盘块号（这将在下篇的inode层进行介绍）。如果删除操作是先释放掉存放文件内容的盘块，再将inode回写到inode区其对应的盘块上，且断电发生在盘块内容被删除后，inode被回写前，那么inode便索引到了一块内容已经被清空的盘块，这也违背了我们的一致性约束条件：文件的元数据必须正确反映文件的状态；

情景3：

位图在磁盘空间的分配和回收中担任着重要的角色，因此其可以被看做是磁盘的元数据。我们在魔改操作系统代码时，也可能会使得位图将一个已经被释放掉的盘块标注为已分配，或者将一个已经被分配出去的盘块标注为未分配。这种情况同样违背了我们的一致性约束条件：磁盘的元数据必须正确反映磁盘的状态。

了解前文中所提到的磁盘的一致性约束条件的具体内容后，我们接下来思考下文件的写操作的情景。一次写操作可能涉及到对inode的修改、对bitmap的修改、对data区盘块的修改等。原则上讲，我们必须保证文件的写操作p满足 p ∈ P，即完成文件的写操作后，所有其涉及到的盘块都需要被正确的修改（否则我们写的代码就是有bug的代码），这样磁盘的一致性状态可以在执行p后仍能保持。但文件系统仍然有一个大敌：崩溃。崩溃会使得操作p在执行的中间被打断，而不完整的p无法保证磁盘的一致性。

我们接下来通过几张图片来了解一下系统是如何进入不一致状态的。

系统为什么会进入不一致的状态？

导致系统进入不一致状态的原因可以分为三种：

1）对于一个现状态为不一致的系统执行任何操作p，无法预期操作完成后该系统的状态；

2）对于一个现状态为一致的系统，执行操作p（p ? P，即操作p无法保证执行后系统能保持一致性），系统可能会进入不一致的状态；

3）对于一个现状态为一致的系统，执行操作p（p ∈ P ）的中间被打断，p中断执行；一个未完全执行的操作p很可能不属于P，这也可能导致系统进入不一致的状态；

第一种情况不难理解；第二种情况可以这样设想：我们希望设计一个属于P的操作p，但由于我们的设计存在bug，导致我们实现的p’无法完成预期的功能，这样导致系统进入了不一致的状态，而不一致状态的系统的执行结果是无法保证的；第三种情况即对应着我们的断电重启情景。

唯一能够保证一致性的情景是，在系统处于一致状态时，完整的执行属于p的操作：

一致性协议的基本要求

理解以上情形后，我们就可以思考如何通过设计来保证我们的系统的一致性了，而使得系统能够保证一致性的设计与实现即为该系统的一致性协议。我们现在已经可以提出一致性协议的基本要求了：

1）必须保证我们系统的初始状态满足所有的一致性约束条件。这点是显然成立的；
2）必须保证该系统的所有操作op均满足 op ∈ P。xv6的代码组织可以保证这一点；
3）必须保证操作p的原子性，即p要么全部被执行，要么没有被执行；

根据前文中我们给出的一致性模型可知，只要实现了上述三点要求，即可保证我们的系统（磁盘）能够在保持一致性。xv6的日志层提供了事务（transaction）的抽象，其要求我们将对文件的写操作组织到事务中来完成。xv6的设计保证，事务的串行执行和并发执行都是符合我们的一致性协议的，即只要我们将文件的写操作组织到事务中，磁盘的状态必定能保持一致（磁盘的元数据能正确反映磁盘的状态，文件的元数据能正确反映文件的状态）。xv6关于事务的抽象与DBMS的事务十分相似，但其具体实现并不相同（DBMS要求事务能够实现回滚操作，而xv6的事务不需要实现回滚）。接下来我们通过代码来了解xv6的事务抽象与一致性协议的实现。

日志与事务

xv6的事务是通过日志的机制来支持实现的。一份日志就是一个脏块，这些脏块既包括文件的内容所对应的盘块，也包括一系列文件相关、磁盘相关的元数据盘块（例如说bitmap的盘块、inode的盘块等）。我们知道，一次对文件的写操作，可能会涉及到bitmap的改动、inode的改动等等，这些数据块都有可能变为“脏块”，xv6并不会直接将脏块回写到对应的磁盘上，而是会先将这些脏块的副本写入到磁盘的日志区。当一组事务相关的所有日志均已成功存储到日志区后，xv6会将logheader回写到磁盘的日志区，标明这批日志已经可以成功提交。

一批完整的、状态为可提交的日志完全囊括了一组文件写操作所涉及到的所有盘块的全部修改，因此如果在执行这组写操作前磁盘的状态是一致的，那么将这批日志中的块全部回写后，磁盘的状态必定仍会保持一致。概括的来讲，即事务的操作属于 P ，这样我们的一致性协议的前两条需求都可以保证。下面我们上手源码，来了解xv6中事务和日志的设计与实现。

首先我们来看一下xv6中日志的数据结构：

struct logheader {
    int n;                      // the num of logs (mark the length of array)
    int block[LOGSIZE];         // the conresponding subscript of buf in buf array
};

struct log {
    struct spinlock lock;
    int start;                  // the log start at this block
    int size;                   // the max log num
    int outstanding;            // how many FS sys calls are executing.
    int committing;             // in commit(), please wait.
    int dev;                    // the dev num
    struct logheader lh;
};
struct log log[NDISK];

begin_op();
...
bp = bread(...);
bp->data[...] = ...;
log_write(bp); 
...
end_op();

void
begin_op(int dev)
{
    acquire(&log[dev].lock);
    while(1){
        if(log[dev].committing){
            sleep(&log, &log[dev].lock);
        } else if(log[dev].lh.n + (log[dev].outstanding+1)*MAXOPBLOCKS > LOGSIZE){
            // this op might exhaust log space; wait for commit.
            sleep(&log, &log[dev].lock);
        } else {
            log[dev].outstanding += 1;
            release(&log[dev].lock);
            break;
        }
    }
}

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

    int dev = b->dev;
    if (log[dev].lh.n >= LOGSIZE || log[dev].lh.n >= log[dev].size - 1)
        panic("too big a transaction");
    if (log[dev].outstanding < 1)
        panic("log_write outside of trans");

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

void
end_op(int dev)
{
    int do_commit = 0;

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

    if(do_commit){
        // call commit w/o holding locks, since not allowed
        // to sleep with locks.
        commit(dev);
        acquire(&log[dev].lock);
        log[dev].committing = 0;
        wakeup(&log);
        release(&log[dev].lock);
    }
}

static void
commit(int dev)
{
    if (log[dev].lh.n > 0) {
        write_log(dev);     // Write modified blocks from cache to log
        write_head(dev);    // Write header to disk -- the real commit
        install_trans(dev); // Now install writes to home locations
        log[dev].lh.n = 0;
        write_head(dev);    // Erase the transaction from the log
    }
}

static void
write_log(int dev)
{
    int tail;

    for (tail = 0; tail < log[dev].lh.n; tail++) {
        struct buf *to = bread(dev, log[dev].start+tail+1); // log block
        struct buf *from = bread(dev, log[dev].lh.block[tail]); // cache block
        memmove(to->data, from->data, BSIZE);
        bwrite(to);  // write the log
        brelse(from);
        brelse(to);
    }
}

static void
write_head(int dev)
{
    struct buf *buf = bread(dev, log[dev].start);
    struct logheader *hb = (struct logheader *) (buf->data);
    int i;
    hb->n = log[dev].lh.n;
    for (i = 0; i < log[dev].lh.n; i++) {
        hb->block[i] = log[dev].lh.block[i];
    }
    bwrite(buf);
    brelse(buf);
}

static void
install_trans(int dev)
{
    int tail;

    for (tail = 0; tail < log[dev].lh.n; tail++) {
        struct buf *lbuf = bread(dev, log[dev].start+tail+1); // read log block
        struct buf *dbuf = bread(dev, log[dev].lh.block[tail]); // read dst
        memmove(dbuf->data, lbuf->data, BSIZE);  // copy block to dst
        bwrite(dbuf);  // write dst to disk
        bunpin(dbuf);
        brelse(lbuf);
        brelse(dbuf);
    }
}

static void
recover_from_log(int dev)
{
    read_head(dev);
    install_trans(dev); // if committed, copy from log to disk
    log[dev].lh.n = 0;
    write_head(dev); // clear the log
}

int main(int argc, char **argv) {
    int fd = open("test.txt", O_CREATE|O_RDWR, 0666);
    int ret = write(fd, "abcde", 5);
    if (ret == 5) {
        printf("nice!");
    }
    exit(0);
}