113a96baeSFrans Kaashoek #include "types.h"
213a96baeSFrans Kaashoek #include "defs.h"
313a96baeSFrans Kaashoek #include "param.h"
413a96baeSFrans Kaashoek #include "spinlock.h"
56670d3b5SFrans Kaashoek #include "sleeplock.h"
613a96baeSFrans Kaashoek #include "fs.h"
713a96baeSFrans Kaashoek #include "buf.h"
813a96baeSFrans Kaashoek
971453f72SRobert Morris // Simple logging that allows concurrent FS system calls.
102e590463SRobert Morris //
1111183588SRobert Morris // A log transaction contains the updates of multiple FS system
1211183588SRobert Morris // calls. The logging system only commits when there are
1371453f72SRobert Morris // no FS system calls active. Thus there is never
1471453f72SRobert Morris // any reasoning required about whether a commit might
1571453f72SRobert Morris // write an uncommitted system call's updates to disk.
162e590463SRobert Morris //
1771453f72SRobert Morris // A system call should call begin_op()/end_op() to mark
1871453f72SRobert Morris // its start and end. Usually begin_op() just increments
1971453f72SRobert Morris // the count of in-progress FS system calls and returns.
2071453f72SRobert Morris // But if it thinks the log is close to running out, it
2111183588SRobert Morris // sleeps until the last outstanding end_op() commits.
222e590463SRobert Morris //
232e590463SRobert Morris // The log is a physical re-do log containing disk blocks.
242e590463SRobert Morris // The on-disk log format:
25c24ac5d7SFrans Kaashoek // header block, containing block #s for block A, B, C, ...
262e590463SRobert Morris // block A
272e590463SRobert Morris // block B
282e590463SRobert Morris // block C
292e590463SRobert Morris // ...
302e590463SRobert Morris // Log appends are synchronous.
3113a96baeSFrans Kaashoek
322e590463SRobert Morris // Contents of the header block, used for both the on-disk header block
33c24ac5d7SFrans Kaashoek // and to keep track in memory of logged block# before commit.
3413a96baeSFrans Kaashoek struct logheader {
352e590463SRobert Morris int n;
36c24ac5d7SFrans Kaashoek int block[LOGSIZE];
3713a96baeSFrans Kaashoek };
3813a96baeSFrans Kaashoek
39ee1b3306SAustin Clements struct log {
4013a96baeSFrans Kaashoek struct spinlock lock;
4113a96baeSFrans Kaashoek int start;
4213a96baeSFrans Kaashoek int size;
4371453f72SRobert Morris int outstanding; // how many FS sys calls are executing.
4471453f72SRobert Morris int committing; // in commit(), please wait.
4513a96baeSFrans Kaashoek int dev;
4613a96baeSFrans Kaashoek struct logheader lh;
47ee1b3306SAustin Clements };
48ee1b3306SAustin Clements struct log log;
4913a96baeSFrans Kaashoek
5013a96baeSFrans Kaashoek static void recover_from_log(void);
5171453f72SRobert Morris static void commit();
5213a96baeSFrans Kaashoek
5313a96baeSFrans Kaashoek void
initlog(int dev)548320d61bSFrans Kaashoek initlog(int dev)
5513a96baeSFrans Kaashoek {
5613a96baeSFrans Kaashoek if (sizeof(struct logheader) >= BSIZE)
5713a96baeSFrans Kaashoek panic("initlog: too big logheader");
5813a96baeSFrans Kaashoek
5913a96baeSFrans Kaashoek struct superblock sb;
6013a96baeSFrans Kaashoek initlock(&log.lock, "log");
618320d61bSFrans Kaashoek readsb(dev, &sb);
628320d61bSFrans Kaashoek log.start = sb.logstart;
6313a96baeSFrans Kaashoek log.size = sb.nlog;
648320d61bSFrans Kaashoek log.dev = dev;
6513a96baeSFrans Kaashoek recover_from_log();
6613a96baeSFrans Kaashoek }
6713a96baeSFrans Kaashoek
6813a96baeSFrans Kaashoek // Copy committed blocks from log to their home location
6913a96baeSFrans Kaashoek static void
install_trans(void)7013a96baeSFrans Kaashoek install_trans(void)
7113a96baeSFrans Kaashoek {
7213a96baeSFrans Kaashoek int tail;
7313a96baeSFrans Kaashoek
742e590463SRobert Morris for (tail = 0; tail < log.lh.n; tail++) {
75e25b74caSFrans Kaashoek struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block
76c24ac5d7SFrans Kaashoek struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst
77e25b74caSFrans Kaashoek memmove(dbuf->data, lbuf->data, BSIZE); // copy block to dst
78a5fbfe41SRobert Morris bwrite(dbuf); // write dst to disk
7913a96baeSFrans Kaashoek brelse(lbuf);
8013a96baeSFrans Kaashoek brelse(dbuf);
8113a96baeSFrans Kaashoek }
8213a96baeSFrans Kaashoek }
8313a96baeSFrans Kaashoek
8413a96baeSFrans Kaashoek // Read the log header from disk into the in-memory log header
8513a96baeSFrans Kaashoek static void
read_head(void)8613a96baeSFrans Kaashoek read_head(void)
8713a96baeSFrans Kaashoek {
8813a96baeSFrans Kaashoek struct buf *buf = bread(log.dev, log.start);
8913a96baeSFrans Kaashoek struct logheader *lh = (struct logheader *) (buf->data);
9013a96baeSFrans Kaashoek int i;
912e590463SRobert Morris log.lh.n = lh->n;
922e590463SRobert Morris for (i = 0; i < log.lh.n; i++) {
93c24ac5d7SFrans Kaashoek log.lh.block[i] = lh->block[i];
9413a96baeSFrans Kaashoek }
9513a96baeSFrans Kaashoek brelse(buf);
9613a96baeSFrans Kaashoek }
9713a96baeSFrans Kaashoek
98a5fbfe41SRobert Morris // Write in-memory log header to disk.
99a5fbfe41SRobert Morris // This is the true point at which the
100a5fbfe41SRobert Morris // current transaction commits.
10113a96baeSFrans Kaashoek static void
write_head(void)10213a96baeSFrans Kaashoek write_head(void)
10313a96baeSFrans Kaashoek {
10413a96baeSFrans Kaashoek struct buf *buf = bread(log.dev, log.start);
10513a96baeSFrans Kaashoek struct logheader *hb = (struct logheader *) (buf->data);
10613a96baeSFrans Kaashoek int i;
1072e590463SRobert Morris hb->n = log.lh.n;
1082e590463SRobert Morris for (i = 0; i < log.lh.n; i++) {
109c24ac5d7SFrans Kaashoek hb->block[i] = log.lh.block[i];
11013a96baeSFrans Kaashoek }
11113a96baeSFrans Kaashoek bwrite(buf);
11213a96baeSFrans Kaashoek brelse(buf);
11313a96baeSFrans Kaashoek }
11413a96baeSFrans Kaashoek
11513a96baeSFrans Kaashoek static void
recover_from_log(void)11613a96baeSFrans Kaashoek recover_from_log(void)
11713a96baeSFrans Kaashoek {
11813a96baeSFrans Kaashoek read_head();
1195053dd6aSRobert Morris install_trans(); // if committed, copy from log to disk
1202e590463SRobert Morris log.lh.n = 0;
1215053dd6aSRobert Morris write_head(); // clear the log
12213a96baeSFrans Kaashoek }
12313a96baeSFrans Kaashoek
12411183588SRobert Morris // called at the start of each FS system call.
12513a96baeSFrans Kaashoek void
begin_op(void)12671453f72SRobert Morris begin_op(void)
12713a96baeSFrans Kaashoek {
12813a96baeSFrans Kaashoek acquire(&log.lock);
12971453f72SRobert Morris while(1){
13071453f72SRobert Morris if(log.committing){
1311ddfbbb1SFrans Kaashoek sleep(&log, &log.lock);
13248aa9174SRobert Morris } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){
13348aa9174SRobert Morris // this op might exhaust log space; wait for commit.
13448aa9174SRobert Morris sleep(&log, &log.lock);
13571453f72SRobert Morris } else {
13671453f72SRobert Morris log.outstanding += 1;
13713a96baeSFrans Kaashoek release(&log.lock);
13871453f72SRobert Morris break;
13971453f72SRobert Morris }
14071453f72SRobert Morris }
14113a96baeSFrans Kaashoek }
14213a96baeSFrans Kaashoek
14311183588SRobert Morris // called at the end of each FS system call.
14411183588SRobert Morris // commits if this was the last outstanding operation.
14513a96baeSFrans Kaashoek void
end_op(void)14671453f72SRobert Morris end_op(void)
14771453f72SRobert Morris {
14871453f72SRobert Morris int do_commit = 0;
14971453f72SRobert Morris
15071453f72SRobert Morris acquire(&log.lock);
15171453f72SRobert Morris log.outstanding -= 1;
15271453f72SRobert Morris if(log.committing)
15371453f72SRobert Morris panic("log.committing");
15471453f72SRobert Morris if(log.outstanding == 0){
15571453f72SRobert Morris do_commit = 1;
15671453f72SRobert Morris log.committing = 1;
15748aa9174SRobert Morris } else {
158*6389d9d4SRobert Morris // begin_op() may be waiting for log space,
159*6389d9d4SRobert Morris // and decrementing log.outstanding has decreased
160*6389d9d4SRobert Morris // the amount of reserved space.
16148aa9174SRobert Morris wakeup(&log);
16271453f72SRobert Morris }
16371453f72SRobert Morris release(&log.lock);
16471453f72SRobert Morris
16571453f72SRobert Morris if(do_commit){
16611183588SRobert Morris // call commit w/o holding locks, since not allowed
16711183588SRobert Morris // to sleep with locks.
16871453f72SRobert Morris commit();
16971453f72SRobert Morris acquire(&log.lock);
17071453f72SRobert Morris log.committing = 0;
17171453f72SRobert Morris wakeup(&log);
17271453f72SRobert Morris release(&log.lock);
17371453f72SRobert Morris }
17471453f72SRobert Morris }
17571453f72SRobert Morris
1762b2c1971SRobert Morris // Copy modified blocks from cache to log.
1772b2c1971SRobert Morris static void
write_log(void)1782b2c1971SRobert Morris write_log(void)
1792b2c1971SRobert Morris {
1802b2c1971SRobert Morris int tail;
1812b2c1971SRobert Morris
1822b2c1971SRobert Morris for (tail = 0; tail < log.lh.n; tail++) {
1832b2c1971SRobert Morris struct buf *to = bread(log.dev, log.start+tail+1); // log block
184c24ac5d7SFrans Kaashoek struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
1852b2c1971SRobert Morris memmove(to->data, from->data, BSIZE);
1862b2c1971SRobert Morris bwrite(to); // write the log
1872b2c1971SRobert Morris brelse(from);
1882b2c1971SRobert Morris brelse(to);
1892b2c1971SRobert Morris }
1902b2c1971SRobert Morris }
1912b2c1971SRobert Morris
19271453f72SRobert Morris static void
commit()19371453f72SRobert Morris commit()
19413a96baeSFrans Kaashoek {
195843eecfcSAustin Clements if (log.lh.n > 0) {
1962b2c1971SRobert Morris write_log(); // Write modified blocks from cache to log
197a5fbfe41SRobert Morris write_head(); // Write header to disk -- the real commit
198a5fbfe41SRobert Morris install_trans(); // Now install writes to home locations
1992e590463SRobert Morris log.lh.n = 0;
200a5fbfe41SRobert Morris write_head(); // Erase the transaction from the log
201843eecfcSAustin Clements }
20213a96baeSFrans Kaashoek }
20313a96baeSFrans Kaashoek
2042e590463SRobert Morris // Caller has modified b->data and is done with the buffer.
2052b2c1971SRobert Morris // Record the block number and pin in the cache with B_DIRTY.
2062b2c1971SRobert Morris // commit()/write_log() will do the disk write.
2072b2c1971SRobert Morris //
2082e590463SRobert Morris // log_write() replaces bwrite(); a typical use is:
2092e590463SRobert Morris // bp = bread(...)
2102e590463SRobert Morris // modify bp->data[]
2112e590463SRobert Morris // log_write(bp)
2122e590463SRobert Morris // brelse(bp)
21313a96baeSFrans Kaashoek void
log_write(struct buf * b)21413a96baeSFrans Kaashoek log_write(struct buf *b)
21513a96baeSFrans Kaashoek {
21613a96baeSFrans Kaashoek int i;
21713a96baeSFrans Kaashoek
2182e590463SRobert Morris if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
21913a96baeSFrans Kaashoek panic("too big a transaction");
22071453f72SRobert Morris if (log.outstanding < 1)
2212b2c1971SRobert Morris panic("log_write outside of trans");
22213a96baeSFrans Kaashoek
2233d2dedd4SCody Cutler acquire(&log.lock);
2242e590463SRobert Morris for (i = 0; i < log.lh.n; i++) {
225c24ac5d7SFrans Kaashoek if (log.lh.block[i] == b->blockno) // log absorbtion
22613a96baeSFrans Kaashoek break;
22713a96baeSFrans Kaashoek }
228c24ac5d7SFrans Kaashoek log.lh.block[i] = b->blockno;
2292e590463SRobert Morris if (i == log.lh.n)
2302e590463SRobert Morris log.lh.n++;
23111183588SRobert Morris b->flags |= B_DIRTY; // prevent eviction
2323d2dedd4SCody Cutler release(&log.lock);
23313a96baeSFrans Kaashoek }
2349bb1e53dSAustin Clements
235