1 #include "types.h" 2 #include "defs.h" 3 #include "param.h" 4 #include "spinlock.h" 5 #include "sleeplock.h" 6 #include "fs.h" 7 #include "buf.h" 8 9 // Simple logging that allows concurrent FS system calls. 10 // 11 // A log transaction contains the updates of multiple FS system 12 // calls. The logging system only commits when there are 13 // no FS system calls active. Thus there is never 14 // any reasoning required about whether a commit might 15 // write an uncommitted system call's updates to disk. 16 // 17 // A system call should call begin_op()/end_op() to mark 18 // its start and end. Usually begin_op() just increments 19 // the count of in-progress FS system calls and returns. 20 // But if it thinks the log is close to running out, it 21 // sleeps until the last outstanding end_op() commits. 22 // 23 // The log is a physical re-do log containing disk blocks. 24 // The on-disk log format: 25 // header block, containing block #s for block A, B, C, ... 26 // block A 27 // block B 28 // block C 29 // ... 30 // Log appends are synchronous. 31 32 // Contents of the header block, used for both the on-disk header block 33 // and to keep track in memory of logged block# before commit. 34 struct logheader { 35 int n; 36 int block[LOGSIZE]; 37 }; 38 39 struct log { 40 struct spinlock lock; 41 int start; 42 int size; 43 int outstanding; // how many FS sys calls are executing. 44 int committing; // in commit(), please wait. 45 int dev; 46 struct logheader lh; 47 }; 48 struct log log; 49 50 static void recover_from_log(void); 51 static void commit(); 52 53 void 54 initlog(int dev) 55 { 56 if (sizeof(struct logheader) >= BSIZE) 57 panic("initlog: too big logheader"); 58 59 struct superblock sb; 60 initlock(&log.lock, "log"); 61 readsb(dev, &sb); 62 log.start = sb.logstart; 63 log.size = sb.nlog; 64 log.dev = dev; 65 recover_from_log(); 66 } 67 68 // Copy committed blocks from log to their home location 69 static void 70 install_trans(void) 71 { 72 int tail; 73 74 for (tail = 0; tail < log.lh.n; tail++) { 75 struct buf *lbuf = bread(log.dev, log.start+tail+1); // read log block 76 struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst 77 memmove(dbuf->data, lbuf->data, BSIZE); // copy block to dst 78 bwrite(dbuf); // write dst to disk 79 brelse(lbuf); 80 brelse(dbuf); 81 } 82 } 83 84 // Read the log header from disk into the in-memory log header 85 static void 86 read_head(void) 87 { 88 struct buf *buf = bread(log.dev, log.start); 89 struct logheader *lh = (struct logheader *) (buf->data); 90 int i; 91 log.lh.n = lh->n; 92 for (i = 0; i < log.lh.n; i++) { 93 log.lh.block[i] = lh->block[i]; 94 } 95 brelse(buf); 96 } 97 98 // Write in-memory log header to disk. 99 // This is the true point at which the 100 // current transaction commits. 101 static void 102 write_head(void) 103 { 104 struct buf *buf = bread(log.dev, log.start); 105 struct logheader *hb = (struct logheader *) (buf->data); 106 int i; 107 hb->n = log.lh.n; 108 for (i = 0; i < log.lh.n; i++) { 109 hb->block[i] = log.lh.block[i]; 110 } 111 bwrite(buf); 112 brelse(buf); 113 } 114 115 static void 116 recover_from_log(void) 117 { 118 read_head(); 119 install_trans(); // if committed, copy from log to disk 120 log.lh.n = 0; 121 write_head(); // clear the log 122 } 123 124 // called at the start of each FS system call. 125 void 126 begin_op(void) 127 { 128 acquire(&log.lock); 129 while(1){ 130 if(log.committing){ 131 sleep(&log, &log.lock); 132 } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE){ 133 // this op might exhaust log space; wait for commit. 134 sleep(&log, &log.lock); 135 } else { 136 log.outstanding += 1; 137 release(&log.lock); 138 break; 139 } 140 } 141 } 142 143 // called at the end of each FS system call. 144 // commits if this was the last outstanding operation. 145 void 146 end_op(void) 147 { 148 int do_commit = 0; 149 150 acquire(&log.lock); 151 log.outstanding -= 1; 152 if(log.committing) 153 panic("log.committing"); 154 if(log.outstanding == 0){ 155 do_commit = 1; 156 log.committing = 1; 157 } else { 158 // begin_op() may be waiting for log space. 159 wakeup(&log); 160 } 161 release(&log.lock); 162 163 if(do_commit){ 164 // call commit w/o holding locks, since not allowed 165 // to sleep with locks. 166 commit(); 167 acquire(&log.lock); 168 log.committing = 0; 169 wakeup(&log); 170 release(&log.lock); 171 } 172 } 173 174 // Copy modified blocks from cache to log. 175 static void 176 write_log(void) 177 { 178 int tail; 179 180 for (tail = 0; tail < log.lh.n; tail++) { 181 struct buf *to = bread(log.dev, log.start+tail+1); // log block 182 struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block 183 memmove(to->data, from->data, BSIZE); 184 bwrite(to); // write the log 185 brelse(from); 186 brelse(to); 187 } 188 } 189 190 static void 191 commit() 192 { 193 if (log.lh.n > 0) { 194 write_log(); // Write modified blocks from cache to log 195 write_head(); // Write header to disk -- the real commit 196 install_trans(); // Now install writes to home locations 197 log.lh.n = 0; 198 write_head(); // Erase the transaction from the log 199 } 200 } 201 202 // Caller has modified b->data and is done with the buffer. 203 // Record the block number and pin in the cache with B_DIRTY. 204 // commit()/write_log() will do the disk write. 205 // 206 // log_write() replaces bwrite(); a typical use is: 207 // bp = bread(...) 208 // modify bp->data[] 209 // log_write(bp) 210 // brelse(bp) 211 void 212 log_write(struct buf *b) 213 { 214 int i; 215 216 if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1) 217 panic("too big a transaction"); 218 if (log.outstanding < 1) 219 panic("log_write outside of trans"); 220 221 acquire(&log.lock); 222 for (i = 0; i < log.lh.n; i++) { 223 if (log.lh.block[i] == b->blockno) // log absorbtion 224 break; 225 } 226 log.lh.block[i] = b->blockno; 227 if (i == log.lh.n) 228 log.lh.n++; 229 b->flags |= B_DIRTY; // prevent eviction 230 release(&log.lock); 231 } 232 233