diff options
| -rw-r--r-- | kernel/bio.c | 36 | ||||
| -rw-r--r-- | kernel/buf.h | 5 | ||||
| -rw-r--r-- | kernel/defs.h | 4 | ||||
| -rw-r--r-- | kernel/log.c | 8 | ||||
| -rw-r--r-- | kernel/virtio_disk.c | 21 | ||||
| -rw-r--r-- | labs/lock.html | 32 |
6 files changed, 68 insertions, 38 deletions
diff --git a/kernel/bio.c b/kernel/bio.c index a08884b..a1074f2 100644 --- a/kernel/bio.c +++ b/kernel/bio.c @@ -12,11 +12,7 @@ // * Do not use the buffer after calling brelse. // * Only one process at a time can use a buffer, // so do not keep them longer than necessary. -// -// The implementation uses two state flags internally: -// * B_VALID: the buffer data has been read from the disk. -// * B_DIRTY: the buffer data has been modified -// and needs to be written to disk. + #include "types.h" #include "param.h" @@ -76,13 +72,11 @@ bget(uint dev, uint blockno) } // Not cached; recycle an unused buffer. - // Even if refcnt==0, B_DIRTY indicates a buffer is in use - // because log.c has modified it but not yet committed it. for(b = bcache.head.prev; b != &bcache.head; b = b->prev){ - if(b->refcnt == 0 && (b->flags & B_DIRTY) == 0) { + if(b->refcnt == 0) { b->dev = dev; b->blockno = blockno; - b->flags = 0; + b->valid = 0; b->refcnt = 1; release(&bcache.lock); acquiresleep(&b->lock); @@ -99,8 +93,9 @@ bread(uint dev, uint blockno) struct buf *b; b = bget(dev, blockno); - if((b->flags & B_VALID) == 0) { - virtio_disk_rw(b); + if(!b->valid) { + virtio_disk_rw(b, 0); + b->valid = 1; } return b; } @@ -111,8 +106,7 @@ bwrite(struct buf *b) { if(!holdingsleep(&b->lock)) panic("bwrite"); - b->flags |= B_DIRTY; - virtio_disk_rw(b); + virtio_disk_rw(b, 1); } // Release a locked buffer. @@ -139,3 +133,19 @@ brelse(struct buf *b) release(&bcache.lock); } + +void +bpin(struct buf *b) { + acquire(&bcache.lock); + b->refcnt++; + release(&bcache.lock); +} + +void +bunpin(struct buf *b) { + acquire(&bcache.lock); + b->refcnt--; + release(&bcache.lock); +} + + diff --git a/kernel/buf.h b/kernel/buf.h index 3266495..4a3a39d 100644 --- a/kernel/buf.h +++ b/kernel/buf.h @@ -1,5 +1,6 @@ struct buf { - int flags; + int valid; // has data been read from disk? + int disk; // does disk "own" buf? uint dev; uint blockno; struct sleeplock lock; @@ -9,6 +10,4 @@ struct buf { struct buf *qnext; // disk queue uchar data[BSIZE]; }; -#define B_VALID 0x2 // buffer has been read from disk -#define B_DIRTY 0x4 // buffer needs to be written to disk diff --git a/kernel/defs.h b/kernel/defs.h index de4acfd..2689bed 100644 --- a/kernel/defs.h +++ b/kernel/defs.h @@ -14,6 +14,8 @@ void binit(void); struct buf* bread(uint, uint); void brelse(struct buf*); void bwrite(struct buf*); +void bpin(struct buf*); +void bunpin(struct buf*); // console.c void consoleinit(void); @@ -177,7 +179,7 @@ void plic_complete(int); // virtio_disk.c void virtio_disk_init(void); -void virtio_disk_rw(struct buf *); +void virtio_disk_rw(struct buf *, int); void virtio_disk_intr(); // number of elements in fixed-size array diff --git a/kernel/log.c b/kernel/log.c index c8f7e62..59984db 100644 --- a/kernel/log.c +++ b/kernel/log.c @@ -77,6 +77,7 @@ install_trans(void) struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst memmove(dbuf->data, lbuf->data, BSIZE); // copy block to dst bwrite(dbuf); // write dst to disk + bunpin(dbuf); brelse(lbuf); brelse(dbuf); } @@ -203,7 +204,7 @@ commit() } // Caller has modified b->data and is done with the buffer. -// Record the block number and pin in the cache with B_DIRTY. +// Record the block number and pin in the cache by increasing refcnt. // commit()/write_log() will do the disk write. // // log_write() replaces bwrite(); a typical use is: @@ -227,9 +228,10 @@ log_write(struct buf *b) break; } log.lh.block[i] = b->blockno; - if (i == log.lh.n) + if (i == log.lh.n) { // Add new block to log? + bpin(b); log.lh.n++; - b->flags |= B_DIRTY; // prevent eviction + } release(&log.lock); } diff --git a/kernel/virtio_disk.c b/kernel/virtio_disk.c index 3ace5ef..14c718d 100644 --- a/kernel/virtio_disk.c +++ b/kernel/virtio_disk.c @@ -164,7 +164,7 @@ alloc3_desc(int *idx) } void -virtio_disk_rw(struct buf *b) +virtio_disk_rw(struct buf *b, int write) { uint64 sector = b->blockno * (BSIZE / 512); @@ -192,7 +192,7 @@ virtio_disk_rw(struct buf *b) uint64 sector; } buf0; - if(b->flags & B_DIRTY) + if(write) buf0.type = VIRTIO_BLK_T_OUT; // write the disk else buf0.type = VIRTIO_BLK_T_IN; // read the disk @@ -208,7 +208,7 @@ virtio_disk_rw(struct buf *b) desc[idx[1]].addr = (uint64) b->data; desc[idx[1]].len = BSIZE; - if(b->flags & B_DIRTY) + if(write) desc[idx[1]].flags = 0; // device reads b->data else desc[idx[1]].flags = VRING_DESC_F_WRITE; // device writes b->data @@ -222,6 +222,7 @@ virtio_disk_rw(struct buf *b) desc[idx[2]].next = 0; // record struct buf for virtio_disk_intr(). + b->disk = 1; info[idx[0]].b = b; // avail[0] is flags @@ -235,10 +236,13 @@ virtio_disk_rw(struct buf *b) *R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number // Wait for virtio_disk_intr() to say request has finished. - while((b->flags & (B_VALID|B_DIRTY)) != B_VALID){ + while(b->disk == 1) { sleep(b, &vdisk_lock); } + info[idx[0]].b = 0; + free_chain(idx[0]); + release(&vdisk_lock); } @@ -252,15 +256,10 @@ virtio_disk_intr() if(info[id].status != 0) panic("virtio_disk_intr status"); - - info[id].b->flags |= B_VALID; - info[id].b->flags &= ~B_DIRTY; - + + info[id].b->disk = 0; // disk is done with buf wakeup(info[id].b); - info[id].b = 0; - free_chain(id); - used_idx = (used_idx + 1) % NUM; } diff --git a/labs/lock.html b/labs/lock.html index b43a51b..707d6c4 100644 --- a/labs/lock.html +++ b/labs/lock.html @@ -82,7 +82,7 @@ workloads. <p>Run usertests to see if you don't break anything. -<h2>Lock-free bcache lookup</h2> +<h2>More scalabale bcache lookup</h2> <p>Several processes reading different files repeatedly will @@ -98,7 +98,7 @@ workloads. and run test0 from bcachetest and you will see "!"s. <p>Modify <tt>bget</tt> so that a lookup for a buffer that is in the - bcache doesn't need to acquire <tt>bcache.lock</tt>. This more + bcache doesn't need to acquire <tt>bcache.lock</tt>. This is more tricky than the kalloc assignment, because bcache buffers are truly shared among processes. You must maintain the invariant that a buffer is only once in memory. @@ -116,15 +116,33 @@ against, including: <p>A challenge is testing whether you code is still correct. One way to do is to artificially delay certain operations - using <tt>sleepticks</tt>. + using <tt>sleepticks</tt>. <tt>test1</tt> trashes the buffer cache + and exercises more code paths. <p>Here are some hints: <ul> - <li> Use an atomic increment instruction for incrementing and - decrementing <tt>b->ref</tt> (see <tt>__sync_fetch_and_add() and - related primitives</tt>) - <li>Don't walk the <tt>bcache.head</tt> list to find a buffer + <li>Read the description of buffer cache in the xv6 book (Section 7.2). + <li>Use a simple design: i.e., don't design a lock-free implementation. + <li>Use a simple hash table with locks per bucket. + <li>Searching in hash table for a buffer and allocating an entry + for that buffer when the buffer is not found must be atomic. + <li>It is fine to acquire <tt>bcache.lock</tt> in <tt>brelse</tt> + to update the LRU/MRU list. </ul> + +<p>Check that your implementation has less contention + on <tt>test0</tt> + +<p>Make sure your implementation passes bcachetest and usertests. + +<p>Optional: + <ul> + <li>make the buffer cache more scalable (e.g., avoid taking + out <tt>bcache.lock</tt> on <tt>brelse</tt>). + <li>make lookup lock-free (Hint: use gcc's <tt>__sync_*</tt> + functions.) How do you convince yourself that your implementation is correct? + </ul> + </body> </html> |