113a96baeSFrans Kaashoek #include "types.h" 213a96baeSFrans Kaashoek #include "defs.h" 313a96baeSFrans Kaashoek #include "param.h" 413a96baeSFrans Kaashoek #include "spinlock.h" 513a96baeSFrans Kaashoek #include "fs.h" 613a96baeSFrans Kaashoek #include "buf.h" 713a96baeSFrans Kaashoek 871453f72SRobert Morris // Simple logging that allows concurrent FS system calls. 92e590463SRobert Morris // 1011183588SRobert Morris // A log transaction contains the updates of multiple FS system 1111183588SRobert Morris // calls. The logging system only commits when there are 1271453f72SRobert Morris // no FS system calls active. Thus there is never 1371453f72SRobert Morris // any reasoning required about whether a commit might 1471453f72SRobert Morris // write an uncommitted system call's updates to disk. 152e590463SRobert Morris // 1671453f72SRobert Morris // A system call should call begin_op()/end_op() to mark 1771453f72SRobert Morris // its start and end. Usually begin_op() just increments 1871453f72SRobert Morris // the count of in-progress FS system calls and returns. 1971453f72SRobert Morris // But if it thinks the log is close to running out, it 2011183588SRobert Morris // sleeps until the last outstanding end_op() commits. 212e590463SRobert Morris // 222e590463SRobert Morris // The log is a physical re-do log containing disk blocks. 232e590463SRobert Morris // The on-disk log format: 24*c24ac5d7SFrans Kaashoek // header block, containing block #s for block A, B, C, ... 252e590463SRobert Morris // block A 262e590463SRobert Morris // block B 272e590463SRobert Morris // block C 282e590463SRobert Morris // ... 292e590463SRobert Morris // Log appends are synchronous. 3013a96baeSFrans Kaashoek 312e590463SRobert Morris // Contents of the header block, used for both the on-disk header block 32*c24ac5d7SFrans Kaashoek // and to keep track in memory of logged block# before commit. 3313a96baeSFrans Kaashoek struct logheader { 342e590463SRobert Morris int n; 35*c24ac5d7SFrans Kaashoek int block[LOGSIZE]; 3613a96baeSFrans Kaashoek }; 3713a96baeSFrans Kaashoek 38ee1b3306SAustin Clements struct log { 3913a96baeSFrans Kaashoek struct spinlock lock; 4013a96baeSFrans Kaashoek int start; 4113a96baeSFrans Kaashoek int size; 4271453f72SRobert Morris int outstanding; // how many FS sys calls are executing. 4371453f72SRobert Morris int committing; // in commit(), please wait. 4413a96baeSFrans Kaashoek int dev; 4513a96baeSFrans Kaashoek struct logheader lh; 46ee1b3306SAustin Clements }; 47ee1b3306SAustin Clements struct log log; 4813a96baeSFrans Kaashoek 4913a96baeSFrans Kaashoek static void recover_from_log(void); 5071453f72SRobert Morris static void commit(); 5113a96baeSFrans Kaashoek 5213a96baeSFrans Kaashoek void 5313a96baeSFrans Kaashoek initlog(void) 5413a96baeSFrans Kaashoek { 5513a96baeSFrans Kaashoek if (sizeof(struct logheader) >= BSIZE) 5613a96baeSFrans Kaashoek panic("initlog: too big logheader"); 5713a96baeSFrans Kaashoek 5813a96baeSFrans Kaashoek struct superblock sb; 5913a96baeSFrans Kaashoek initlock(&log.lock, "log"); 6013a96baeSFrans Kaashoek readsb(ROOTDEV, &sb); 6113a96baeSFrans Kaashoek log.start = sb.size - sb.nlog; 6213a96baeSFrans Kaashoek log.size = sb.nlog; 6313a96baeSFrans Kaashoek log.dev = ROOTDEV; 6413a96baeSFrans Kaashoek recover_from_log(); 6513a96baeSFrans Kaashoek } 6613a96baeSFrans Kaashoek 6713a96baeSFrans Kaashoek // Copy committed blocks from log to their home location 6813a96baeSFrans Kaashoek static void 6913a96baeSFrans Kaashoek install_trans(void) 7013a96baeSFrans Kaashoek { 7113a96baeSFrans Kaashoek int tail; 7213a96baeSFrans Kaashoek 732e590463SRobert Morris for (tail = 0; tail < log.lh.n; tail++) { 74e25b74caSFrans Kaashoek struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block 75*c24ac5d7SFrans Kaashoek struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst 76e25b74caSFrans Kaashoek memmove(dbuf->data, lbuf->data, BSIZE); // copy block to dst 77a5fbfe41SRobert Morris bwrite(dbuf); // write dst to disk 7813a96baeSFrans Kaashoek brelse(lbuf); 7913a96baeSFrans Kaashoek brelse(dbuf); 8013a96baeSFrans Kaashoek } 8113a96baeSFrans Kaashoek } 8213a96baeSFrans Kaashoek 8313a96baeSFrans Kaashoek // Read the log header from disk into the in-memory log header 8413a96baeSFrans Kaashoek static void 8513a96baeSFrans Kaashoek read_head(void) 8613a96baeSFrans Kaashoek { 8713a96baeSFrans Kaashoek struct buf *buf = bread(log.dev, log.start); 8813a96baeSFrans Kaashoek struct logheader *lh = (struct logheader *) (buf->data); 8913a96baeSFrans Kaashoek int i; 902e590463SRobert Morris log.lh.n = lh->n; 912e590463SRobert Morris for (i = 0; i < log.lh.n; i++) { 92*c24ac5d7SFrans Kaashoek log.lh.block[i] = lh->block[i]; 9313a96baeSFrans Kaashoek } 9413a96baeSFrans Kaashoek brelse(buf); 9513a96baeSFrans Kaashoek } 9613a96baeSFrans Kaashoek 97a5fbfe41SRobert Morris // Write in-memory log header to disk. 98a5fbfe41SRobert Morris // This is the true point at which the 99a5fbfe41SRobert Morris // current transaction commits. 10013a96baeSFrans Kaashoek static void 10113a96baeSFrans Kaashoek write_head(void) 10213a96baeSFrans Kaashoek { 10313a96baeSFrans Kaashoek struct buf *buf = bread(log.dev, log.start); 10413a96baeSFrans Kaashoek struct logheader *hb = (struct logheader *) (buf->data); 10513a96baeSFrans Kaashoek int i; 1062e590463SRobert Morris hb->n = log.lh.n; 1072e590463SRobert Morris for (i = 0; i < log.lh.n; i++) { 108*c24ac5d7SFrans Kaashoek hb->block[i] = log.lh.block[i]; 10913a96baeSFrans Kaashoek } 11013a96baeSFrans Kaashoek bwrite(buf); 11113a96baeSFrans Kaashoek brelse(buf); 11213a96baeSFrans Kaashoek } 11313a96baeSFrans Kaashoek 11413a96baeSFrans Kaashoek static void 11513a96baeSFrans Kaashoek recover_from_log(void) 11613a96baeSFrans Kaashoek { 11713a96baeSFrans Kaashoek read_head(); 1185053dd6aSRobert Morris install_trans(); // if committed, copy from log to disk 1192e590463SRobert Morris log.lh.n = 0; 1205053dd6aSRobert Morris write_head(); // clear the log 12113a96baeSFrans Kaashoek } 12213a96baeSFrans Kaashoek 12311183588SRobert Morris // called at the start of each FS system call. 12413a96baeSFrans Kaashoek void 12571453f72SRobert Morris begin_op(void) 12613a96baeSFrans Kaashoek { 12713a96baeSFrans Kaashoek acquire(&log.lock); 12871453f72SRobert Morris while(1){ 12971453f72SRobert Morris if(log.committing){ 1301ddfbbb1SFrans Kaashoek sleep(&log, &log.lock); 13148aa9174SRobert Morris } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){ 13248aa9174SRobert Morris // this op might exhaust log space; wait for commit. 13348aa9174SRobert Morris sleep(&log, &log.lock); 13471453f72SRobert Morris } else { 13571453f72SRobert Morris log.outstanding += 1; 13613a96baeSFrans Kaashoek release(&log.lock); 13771453f72SRobert Morris break; 13871453f72SRobert Morris } 13971453f72SRobert Morris } 14013a96baeSFrans Kaashoek } 14113a96baeSFrans Kaashoek 14211183588SRobert Morris // called at the end of each FS system call. 14311183588SRobert Morris // commits if this was the last outstanding operation. 14413a96baeSFrans Kaashoek void 14571453f72SRobert Morris end_op(void) 14671453f72SRobert Morris { 14771453f72SRobert Morris int do_commit = 0; 14871453f72SRobert Morris 14971453f72SRobert Morris acquire(&log.lock); 15071453f72SRobert Morris log.outstanding -= 1; 15171453f72SRobert Morris if(log.committing) 15271453f72SRobert Morris panic("log.committing"); 15371453f72SRobert Morris if(log.outstanding == 0){ 15471453f72SRobert Morris do_commit = 1; 15571453f72SRobert Morris log.committing = 1; 15648aa9174SRobert Morris } else { 15748aa9174SRobert Morris // begin_op() may be waiting for log space. 15848aa9174SRobert Morris wakeup(&log); 15971453f72SRobert Morris } 16071453f72SRobert Morris release(&log.lock); 16171453f72SRobert Morris 16271453f72SRobert Morris if(do_commit){ 16311183588SRobert Morris // call commit w/o holding locks, since not allowed 16411183588SRobert Morris // to sleep with locks. 16571453f72SRobert Morris commit(); 16671453f72SRobert Morris acquire(&log.lock); 16771453f72SRobert Morris log.committing = 0; 16871453f72SRobert Morris wakeup(&log); 16971453f72SRobert Morris release(&log.lock); 17071453f72SRobert Morris } 17171453f72SRobert Morris } 17271453f72SRobert Morris 1732b2c1971SRobert Morris // Copy modified blocks from cache to log. 1742b2c1971SRobert Morris static void 1752b2c1971SRobert Morris write_log(void) 1762b2c1971SRobert Morris { 1772b2c1971SRobert Morris int tail; 1782b2c1971SRobert Morris 1792b2c1971SRobert Morris for (tail = 0; tail < log.lh.n; tail++) { 1802b2c1971SRobert Morris struct buf *to = bread(log.dev, log.start+tail+1); // log block 181*c24ac5d7SFrans Kaashoek struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block 1822b2c1971SRobert Morris memmove(to->data, from->data, BSIZE); 1832b2c1971SRobert Morris bwrite(to); // write the log 1842b2c1971SRobert Morris brelse(from); 1852b2c1971SRobert Morris brelse(to); 1862b2c1971SRobert Morris } 1872b2c1971SRobert Morris } 1882b2c1971SRobert Morris 18971453f72SRobert Morris static void 19071453f72SRobert Morris commit() 19113a96baeSFrans Kaashoek { 192843eecfcSAustin Clements if (log.lh.n > 0) { 1932b2c1971SRobert Morris write_log(); // Write modified blocks from cache to log 194a5fbfe41SRobert Morris write_head(); // Write header to disk -- the real commit 195a5fbfe41SRobert Morris install_trans(); // Now install writes to home locations 1962e590463SRobert Morris log.lh.n = 0; 197a5fbfe41SRobert Morris write_head(); // Erase the transaction from the log 198843eecfcSAustin Clements } 19913a96baeSFrans Kaashoek } 20013a96baeSFrans Kaashoek 2012e590463SRobert Morris // Caller has modified b->data and is done with the buffer. 2022b2c1971SRobert Morris // Record the block number and pin in the cache with B_DIRTY. 2032b2c1971SRobert Morris // commit()/write_log() will do the disk write. 2042b2c1971SRobert Morris // 2052e590463SRobert Morris // log_write() replaces bwrite(); a typical use is: 2062e590463SRobert Morris // bp = bread(...) 2072e590463SRobert Morris // modify bp->data[] 2082e590463SRobert Morris // log_write(bp) 2092e590463SRobert Morris // brelse(bp) 21013a96baeSFrans Kaashoek void 21113a96baeSFrans Kaashoek log_write(struct buf *b) 21213a96baeSFrans Kaashoek { 21313a96baeSFrans Kaashoek int i; 21413a96baeSFrans Kaashoek 2152e590463SRobert Morris if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1) 21613a96baeSFrans Kaashoek panic("too big a transaction"); 21771453f72SRobert Morris if (log.outstanding < 1) 2182b2c1971SRobert Morris panic("log_write outside of trans"); 21913a96baeSFrans Kaashoek 2203d2dedd4SCody Cutler acquire(&log.lock); 2212e590463SRobert Morris for (i = 0; i < log.lh.n; i++) { 222*c24ac5d7SFrans Kaashoek if (log.lh.block[i] == b->blockno) // log absorbtion 22313a96baeSFrans Kaashoek break; 22413a96baeSFrans Kaashoek } 225*c24ac5d7SFrans Kaashoek log.lh.block[i] = b->blockno; 2262e590463SRobert Morris if (i == log.lh.n) 2272e590463SRobert Morris log.lh.n++; 22811183588SRobert Morris b->flags |= B_DIRTY; // prevent eviction 2293d2dedd4SCody Cutler release(&log.lock); 23013a96baeSFrans Kaashoek } 2319bb1e53dSAustin Clements 232