From 71453f72f285a17ccf0520b9dbdafdc701ff2f4a Mon Sep 17 00:00:00 2001 From: Robert Morris Date: Wed, 27 Aug 2014 17:15:30 -0400 Subject: a start at concurrent FS system calls --- log.c | 82 +++++++++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 58 insertions(+), 24 deletions(-) (limited to 'log.c') diff --git a/log.c b/log.c index 95cc4d5..159df98 100644 --- a/log.c +++ b/log.c @@ -5,18 +5,22 @@ #include "fs.h" #include "buf.h" -// Simple logging. Each file system system call -// should be surrounded with begin_trans() and commit_trans() calls. +// Simple logging that allows concurrent FS system 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. +// A log transaction contains the updates of *multiple* FS system +// calls. The logging systems 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 +// blocks this system call, and causes the system to wait +// until end_op() indicates there are no executing FS +// system calls, at which point the last end_op() commits +// all the system calls' writes. // // The log is a physical re-do log containing disk blocks. // The on-disk log format: @@ -38,13 +42,15 @@ struct log { struct spinlock lock; int start; int size; - int busy; // a transaction is active + 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(void) @@ -117,19 +123,52 @@ recover_from_log(void) write_head(); // clear the log } +// an FS system call should call begin_op() when it starts. void -begin_trans(void) +begin_op(void) { acquire(&log.lock); - while (log.busy) { - sleep(&log, &log.lock); + while(1){ + if(log.committing){ + sleep(&log, &log.lock); + } else { + // XXX wait (for a commit) if log is longish. + // need to reserve to avoid over-commit of log space. + log.outstanding += 1; + release(&log.lock); + break; + } } - log.busy = 1; - release(&log.lock); } +// an FS system call should call end_op() after it finishes. +// can't write the disk &c while holding locks, thus do_commit. void -commit_trans(void) +end_op(void) +{ + int do_commit = 0; + + acquire(&log.lock); + log.outstanding -= 1; + if(log.committing) + panic("log.committing"); + if(log.outstanding == 0){ + do_commit = 1; + log.committing = 1; + } + release(&log.lock); + + if(do_commit){ + commit(); + acquire(&log.lock); + log.committing = 0; + wakeup(&log); + release(&log.lock); + } +} + +static void +commit() { if (log.lh.n > 0) { write_head(); // Write header to disk -- the real commit @@ -137,11 +176,6 @@ commit_trans(void) log.lh.n = 0; write_head(); // Erase the transaction from the log } - - acquire(&log.lock); - log.busy = 0; - wakeup(&log); - release(&log.lock); } // Caller has modified b->data and is done with the buffer. @@ -159,7 +193,7 @@ log_write(struct buf *b) if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1) panic("too big a transaction"); - if (!log.busy) + if (log.outstanding < 1) panic("write outside of trans"); for (i = 0; i < log.lh.n; i++) { -- cgit v1.2.3 From 48aa917403de1599a02924e429a9f43ea31e9cc1 Mon Sep 17 00:00:00 2001 From: Robert Morris Date: Thu, 28 Aug 2014 05:57:47 -0400 Subject: i think this is a working concurrent logging scheme --- log.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-) (limited to 'log.c') diff --git a/log.c b/log.c index 159df98..9d42ea8 100644 --- a/log.c +++ b/log.c @@ -52,6 +52,10 @@ struct log log; static void recover_from_log(void); static void commit(); +// statistics, delete eventually XXX. +static int maxsize; +static int maxoutstanding; + void initlog(void) { @@ -131,10 +135,15 @@ begin_op(void) 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 { - // XXX wait (for a commit) if log is longish. - // need to reserve to avoid over-commit of log space. log.outstanding += 1; + if(log.outstanding > maxoutstanding){ + maxoutstanding = log.outstanding; + cprintf("%d outstanding\n", log.outstanding); + } release(&log.lock); break; } @@ -155,6 +164,9 @@ end_op(void) if(log.outstanding == 0){ do_commit = 1; log.committing = 1; + } else { + // begin_op() may be waiting for log space. + wakeup(&log); } release(&log.lock); @@ -208,6 +220,11 @@ log_write(struct buf *b) if (i == log.lh.n) log.lh.n++; b->flags |= B_DIRTY; // XXX prevent eviction + + if(log.lh.n > maxsize){ + maxsize = log.lh.n; + cprintf("log size %d/%d\n", log.lh.n, LOGSIZE); + } } //PAGEBREAK! -- cgit v1.2.3 From 11183588dc69085b834e013564fc48526e23ef70 Mon Sep 17 00:00:00 2001 From: Robert Morris Date: Thu, 28 Aug 2014 06:27:01 -0400 Subject: nits --- log.c | 34 ++++++++++------------------------ 1 file changed, 10 insertions(+), 24 deletions(-) (limited to 'log.c') diff --git a/log.c b/log.c index 9d42ea8..6900b8d 100644 --- a/log.c +++ b/log.c @@ -7,8 +7,8 @@ // Simple logging that allows concurrent FS system calls. // -// A log transaction contains the updates of *multiple* FS system -// calls. The logging systems only commits when there are +// 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. @@ -17,10 +17,7 @@ // 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 -// blocks this system call, and causes the system to wait -// until end_op() indicates there are no executing FS -// system calls, at which point the last end_op() commits -// all the system calls' writes. +// sleeps until the last outstanding end_op() commits. // // The log is a physical re-do log containing disk blocks. // The on-disk log format: @@ -52,10 +49,6 @@ struct log log; static void recover_from_log(void); static void commit(); -// statistics, delete eventually XXX. -static int maxsize; -static int maxoutstanding; - void initlog(void) { @@ -127,7 +120,7 @@ recover_from_log(void) write_head(); // clear the log } -// an FS system call should call begin_op() when it starts. +// called at the start of each FS system call. void begin_op(void) { @@ -140,18 +133,14 @@ begin_op(void) sleep(&log, &log.lock); } else { log.outstanding += 1; - if(log.outstanding > maxoutstanding){ - maxoutstanding = log.outstanding; - cprintf("%d outstanding\n", log.outstanding); - } release(&log.lock); break; } } } -// an FS system call should call end_op() after it finishes. -// can't write the disk &c while holding locks, thus do_commit. +// called at the end of each FS system call. +// commits if this was the last outstanding operation. void end_op(void) { @@ -171,6 +160,8 @@ end_op(void) 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; @@ -209,7 +200,7 @@ log_write(struct buf *b) panic("write outside of trans"); for (i = 0; i < log.lh.n; i++) { - if (log.lh.sector[i] == b->sector) // log absorbtion? + if (log.lh.sector[i] == b->sector) // log absorbtion break; } log.lh.sector[i] = b->sector; @@ -219,12 +210,7 @@ log_write(struct buf *b) brelse(lbuf); if (i == log.lh.n) log.lh.n++; - b->flags |= B_DIRTY; // XXX prevent eviction - - if(log.lh.n > maxsize){ - maxsize = log.lh.n; - cprintf("log size %d/%d\n", log.lh.n, LOGSIZE); - } + b->flags |= B_DIRTY; // prevent eviction } //PAGEBREAK! -- cgit v1.2.3 From 2b2c1971fc2c3cc6fa1f2f3e7b507a3a35a0cbb8 Mon Sep 17 00:00:00 2001 From: Robert Morris Date: Thu, 28 Aug 2014 16:06:12 -0400 Subject: write log blocks from cache only at end of transaction --- log.c | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-) (limited to 'log.c') diff --git a/log.c b/log.c index 6900b8d..0abe1fe 100644 --- a/log.c +++ b/log.c @@ -170,10 +170,27 @@ end_op(void) } } +// 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.sector[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 home locations log.lh.n = 0; @@ -182,8 +199,9 @@ commit() } // 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). +// 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[] @@ -197,17 +215,13 @@ log_write(struct buf *b) if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1) panic("too big a transaction"); if (log.outstanding < 1) - panic("write outside of trans"); + panic("log_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++; b->flags |= B_DIRTY; // prevent eviction -- cgit v1.2.3