text: #include "types.h"
  #include "defs.h"
  #include "param.h"
  #include "spinlock.h"
  #include "sleeplock.h"
  #include "fs.h"
  #include "buf.h"
  #include "mmu.h"
  #include "proc.h"
  
  // Simple logging that allows concurrent FS system calls.
  //
  // A log transaction contains the updates of multiple FS system
  // calls. The logging system only commits when there are
  // no FS system calls active. Thus there is never
  // any reasoning required about whether a commit might
  // write an uncommitted system call's updates to disk.
  //
  // A system call should call begin_op()/end_op() to mark
  // its start and end. Usually begin_op() just increments
  // the count of in-progress FS system calls and returns.
  // But if it thinks the log is close to running out, it
  // sleeps until the last outstanding end_op() commits.
  //
  // The log is a physical re-do log containing disk blocks.
  // The on-disk log format:
  //   header block, containing block #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 block# before commit.
  // write header when commit, and set n to zero after writing to file system
  struct logheader
  {
    int n; // zero if no transaction in log, or non-zero if contains a complete committed transaction with # of logged block
    int block[LOGSIZE];
  };
  
  struct log
  {
    struct spinlock lock;
    int start;
    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;
  
  static void recover_from_log(void);
  static void commit();
  
  void initlog(int dev)
  {
    if (sizeof(struct logheader) >= BSIZE)
      panic("initlog: too big logheader");
  
    struct superblock sb;
    initlock(&log.lock, "log");
    readsb(dev, &sb);
    log.start = sb.logstart;
    log.size = sb.nlog;
    log.dev = dev;
    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 *dbuf = bread(log.dev, log.lh.block[tail]);   // read dst
      if (!log.committing) {
        struct buf *lbuf = bread(log.dev, log.start + tail + 1); // read log block
        memmove(dbuf->data, lbuf->data, BSIZE);                  // copy block to dst
        bwrite(dbuf);                                            // write dst to disk
        brelse(lbuf);
      } else {
        bwrite(dbuf);
      }
  
      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.block[i] = lh->block[i];
    }
    brelse(buf);
  }
  
  // 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);
  }
  
  static void
  recover_from_log(void)
  {
    read_head();     // read log header
    install_trans(); // if committed, copy from log to disk
    log.lh.n = 0;
    write_head(); // clear the log
  
    // code to ignore recovery
  
    // read_head();
    // cprintf("recovery: n=%d but ignoring\n", log.lh.n);
    // log.lh.n = 0;
  }
  
  // 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
      {
        // reserves space and prevents a commit from occuring during this syscall
        // conservatively assumes that each syscall might write up to MAXOPBLOCKS distinct blocks
        log.outstanding += 1;
        release(&log.lock);
        break;
      }
    }
  }
  
  // called at the end of each FS system call.
  // 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");
  
    // commit if count becomes 0
    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);
    }
  }
  
  // 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(to);
    }
  }
  
  static void
  commit()
  {
    if (log.lh.n > 0)
    {
      write_log();     // Write modified blocks from cache to log
      write_head();    // Write header to disk -- the real commit
      install_trans(); // Now install writes to proper place in the file system
      log.lh.n = 0;
      write_head(); // Erase the transaction from the log
      // must happen before next transaction, otherwise there is
      // inconsistence between count and logged block
    }
  
    // code to deliberately cause a crash
  
    // int pid = myproc()->pid;
    // if (log.lh.n > 0) {
    //   write_log();
    //   write_head();
    //   if (pid > 1)              // suppress this buggy behavior for init, which creates files before the shell starts.
    //     log.lh.block[0] = 0;
    //   install_trans();
    //   if (pid > 1)
    //     panic("commit mimicking crash");
    //   log.lh.n = 0;
    //   write_head();
    // }
  }
  
  // Caller has modified b->data and is done with the buffer.
  // Record the block number and pin in the cache with B_DIRTY.
  // commit()/write_log() will do the disk 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.outstanding < 1)
      panic("log_write outside of trans");
  
    acquire(&log.lock);
    // block is written multiple times during a single transaction
    // allocate the same slot in log
    // it's common to have a single disk block containing inodes of several files
    // written multiple times within a single transaction
    // absorbtion saves log space
    for (i = 0; i < log.lh.n; i++)
    {
      if (log.lh.block[i] == b->blockno) // log absorbtion
        break;
    }
    // record block's sector number in memory
    log.lh.block[i] = b->blockno;
    if (i == log.lh.n)
      log.lh.n++;
    b->flags |= B_DIRTY; // prevent eviction
    release(&log.lock);
  }
  