テキストの68〜69ページ

本文

システムコールにおけるログの典型的な使い方は次のような感じである。

begin_trans();
…
bp = bread(…);
bp->data[…] = …;
log_write(bp);
…
commit_trans();

begin_trans関数は、ログへ独占的に書き込むためのロックを獲得できるまで待ち、獲得できたら呼び出し元へ返る。
log_write関数は、内部でbwrite関数を使い、書きこもうとしてるブロックの内容をログに追加し、セクタ番号を記録する。
log_write関数は、渡されたバッファを解放しないので、同じトランザクション中に続けてそのブロックを読み込んでも同じ内容が読み取れる。
log_writeは、一つのトランザクション中に特定のブロックへの書き込みが複数ある場合に注意し、ログに対するそのブロックの直前の書き込みを上書きする。

log.c

#include "types.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "fs.h"
#include "buf.h"

// Simple logging. Each system call that might write the file system
// should be surrounded with begin_trans() and commit_trans() calls.
//
// The log holds at most one transaction at a time. Commit forces
// the log (with commit record) to disk, then installs the affected
// blocks to disk, then erases the log. begin_trans() ensures that
// only one system call can be in a transaction; others must wait.
// 
// Allowing only one transaction at a time means that the file
// system code doesn't have to worry about the possibility of
// one transaction reading a block that another one has modified,
// for example an i-node block.
//
// Read-only system calls don't need to use transactions, though
// this means that they may observe uncommitted data. I-node and
// buffer locks prevent read-only calls from seeing inconsistent data.
//
// The log is a physical re-do log containing disk blocks.
// The on-disk log format:
//   header block, containing sector #s for block A, B, C, ...
//   block A
//   block B
//   block C
//   ...
// Log appends are synchronous.

// Contents of the header block, used for both the on-disk header block
// and to keep track in memory of logged sector #s before commit.
struct logheader {
  int n;   
  int sector[LOGSIZE];
};

struct log {
  struct spinlock lock;
  int start;
  int size;
  int intrans;
  int dev;
  struct logheader lh;
};
struct log log;

static void recover_from_log(void);

void
initlog(void)
{
  if (sizeof(struct logheader) >= BSIZE)
    panic("initlog: too big logheader");

  struct superblock sb;
  initlock(&log.lock, "log");
  readsb(ROOTDEV, &sb);
  log.start = sb.size - sb.nlog;
  log.size = sb.nlog;
  log.dev = ROOTDEV;
  recover_from_log();
}

// Copy committed blocks from log to their home location
static void 
install_trans(void)
{
  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.sector[tail]); // read dst
    memmove(dbuf->data, lbuf->data, BSIZE);  // copy block to dst
    bwrite(dbuf);  // flush dst to disk
    brelse(lbuf); 
    brelse(dbuf);
  }
}

// Read the log header from disk into the in-memory log header
static void
read_head(void)
{
  struct buf *buf = bread(log.dev, log.start);
  struct logheader *lh = (struct logheader *) (buf->data);
  int i;
  log.lh.n = lh->n;
  for (i = 0; i < log.lh.n; i++) {
    log.lh.sector[i] = lh->sector[i];
  }
  brelse(buf);
}

// Write in-memory log header to disk, committing log entries till head
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->sector[i] = log.lh.sector[i];
  }
  bwrite(buf);
  brelse(buf);
}

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

void
begin_trans(void)
{
  acquire(&log.lock);
  while (log.intrans) {
    sleep(&log, &log.lock);
  }
  log.intrans = 1;
  release(&log.lock);
}

void
commit_trans(void)
{
  if (log.lh.n > 0) {
    write_head();    // Causes all blocks till log.head to be commited
    install_trans(); // Install all the transactions till head
    log.lh.n = 0; 
    write_head();    // Reclaim log
  }
  
  acquire(&log.lock);
  log.intrans = 0;
  wakeup(&log);
  release(&log.lock);
}

// Caller has modified b->data and is done with the buffer.
// Append the block to the log and record the block number, 
// but don't write the log header (which would commit the write).
// log_write() replaces bwrite(); a typical use is:
//   bp = bread(...)
//   modify bp->data[]
//   log_write(bp)
//   brelse(bp)
void
log_write(struct buf *b)
{
  int i;

  if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
    panic("too big a transaction");
  if (!log.intrans)
    panic("write outside of trans");

  for (i = 0; i < log.lh.n; i++) {
    if (log.lh.sector[i] == b->sector)   // log absorbtion?
      break;
  }
  log.lh.sector[i] = b->sector;
  struct buf *lbuf = bread(b->dev, log.start+i+1);
  memmove(lbuf->data, b->data, BSIZE);
  bwrite(lbuf);
  brelse(lbuf);
  if (i == log.lh.n)
    log.lh.n++;
}

//PAGEBREAK!
// Blank page.

commit_trans関数は、まずディスクへログのヘッダブロックを書き込むので、この時点の直後におけるクラッシュは、リカバリ処理の実行（ログに記録されているブロックを再書き込みする）を引き起こすだろう。
commit_trans関数は、それからinstall_trans関数を呼び、ログに記録されているそれぞれのブロックを読み込み、ファイルシステム上のあるべき場所それを書き込む。
最後に、commit_transはログヘッダにゼロを書きこむので、次のトランザクションが開始した後にクラッシュしても、リカバリのコードによってそのログは無視される。

recover_from_log関数は、起動中、最初のユーザプロセスが開始される前に実行されるinitlog関数から呼ばれる。
recover_from_log関数は、ログヘッダを読み込み、そのヘッダがコミット済みのログがあることを示していたら、commit_transと同じような処理を行う。

filewrite関数に、ログの使い方の例がある。
そのトランザクションはこのような感じである。

begin_trans();
ilock(f->ip);
r = writei(f->ip, …);
iunlock(f->ip);
commit_trans();

このコードは、ログ溢れを回避するため、巨大な書き込みを一度に少しのセクタだけに限定し、個別のトランザクションに分割するループ内で実行される。
writei関数の呼び出しは、このトランザクションの一部として、多数のブロック（ファイルのinode, 一つ以上のビットマップブロック、いくつかのデータブロック）を書き込む。
デッドロックを避ける戦略の一環として、begin_transの後にilockを呼び出す。
各トランザクションの周りに効果的なロックがあるので（？）、デッドロックにならないロック順は、トランザクションのロック→inodeのロックである。

file.cのfilewrite関数

// Write to file f.  Addr is kernel address.
int
filewrite(struct file *f, char *addr, int n)
{
  int r;

  if(f->writable == 0)
    return -1;
  if(f->type == FD_PIPE)
    return pipewrite(f->pipe, addr, n);
  if(f->type == FD_INODE){
    // write a few blocks at a time to avoid exceeding
    // the maximum log transaction size, including
    // i-node, indirect block, allocation blocks,
    // and 2 blocks of slop for non-aligned writes.
    // this really belongs lower down, since writei()
    // might be writing a device like the console.
    int max = ((LOGSIZE-1-1-2) / 2) * 512;
    int i = 0;
    while(i < n){
      int n1 = n - i;
      if(n1 > max)
        n1 = max;

      begin_trans();
      ilock(f->ip);
      if ((r = writei(f->ip, addr + i, f->off, n1)) > 0)
        f->off += r;
      iunlock(f->ip);
      commit_trans();

      if(r < 0)
        break;
      if(r != n1)
        panic("short filewrite");
      i += r;
    }
    return i == n ? n : -1;
  }
  panic("filewrite");
}

感想

ログのコードの説明です。

「log_write関数は、渡されたバッファを解放しないので、同じトランザクション中に続けてそのブロックを読み込んでも同じ内容が読み取れる。」の部分の補足。
アプリレベルの処理として、ブロックの内容を読み込む→その内容を変更する→ディスクに反映、という流れを考えると、最後の「ディスクに反映」する処理の最初の方でlog_writeは呼ばれることになります。
log_writeが渡されたバッファを解放しないということは、メモリ上のバッファキャッシュにある、とあるブロックの変更された内容（未だディスクには反映されていない）がそのままメモリ上に残ることになるので、同じトランザクション中にそのブロックの内容を読み取っても、ちゃんと変更された内容（未だディスクには反映されてない。ログには反映されているけど）を読み取れるという事になります。
もしlog_writeが渡されたバッファを解放した場合、同じトランザクション中の同じブロックへの読み込みであっても、ディスクに変更前のデータを取りに行ってしまい、多分おかしなことになります。

前回、xv6にはビットマップブロックが一つしかないんじゃないか、的なことを書きましたが、今回本文で「一つ以上のビットマップブロック」と書かれてる部分があるので、予想が外れたかもしれません。
そのあたりは、以降でだんだん上の層に登っていくにつれて明らかになるんじゃないかと思います。

「デッドロックにならないロック順は、トランザクションのロック→inodeのロックである。」の部分について。
正直なぜなのかはよく分かりません。
begin_tansの構造としては、ロックを獲得→他のトランザクションが終わるまで待つ→トランザクション開始フラグを立てる→ロックを解放、という流れになっていて、ilockの方も粒度は違うけど同じような構造になっています。
粒度が小さいロック→粒度が大きいロック、よりは、粒度が大きいロック→粒度が小さいロック、の方がより安全であるのは何となくわかる気がします。
ただ、個別の順番ではなくて全体で順番を統一されてるかどうかに影響される気はしますが。
本文でもたいして説明されてないので、もしかしたらこの後の節で説明があるのかもしれません。