1 // Buffer cache. 2 // 3 // The buffer cache is a linked list of buf structures holding 4 // cached copies of disk block contents. Caching disk blocks 5 // in memory reduces the number of disk reads and also provides 6 // a synchronization point for disk blocks used by multiple processes. 7 // 8 // Interface: 9 // * To get a buffer for a particular disk block, call bread. 10 // * After changing buffer data, call bwrite to write it to disk. 11 // * When done with the buffer, call brelse. 12 // * Do not use the buffer after calling brelse. 13 // * Only one process at a time can use a buffer, 14 // so do not keep them longer than necessary. 15 // 16 // The implementation uses two state flags internally: 17 // * B_VALID: the buffer data has been read from the disk. 18 // * B_DIRTY: the buffer data has been modified 19 // and needs to be written to disk. 20 21 #include "types.h" 22 #include "defs.h" 23 #include "param.h" 24 #include "spinlock.h" 25 #include "sleeplock.h" 26 #include "fs.h" 27 #include "buf.h" 28 29 struct { 30 struct spinlock lock; 31 struct buf buf[NBUF]; 32 33 // Linked list of all buffers, through prev/next. 34 // head.next is most recently used. 35 struct buf head; 36 } bcache; 37 38 void 39 binit(void) 40 { 41 struct buf *b; 42 43 initlock(&bcache.lock, "bcache"); 44 45 //PAGEBREAK! 46 // Create linked list of buffers 47 bcache.head.prev = &bcache.head; 48 bcache.head.next = &bcache.head; 49 for(b = bcache.buf; b < bcache.buf+NBUF; b++){ 50 b->next = bcache.head.next; 51 b->prev = &bcache.head; 52 initsleeplock(&b->lock, "buffer"); 53 bcache.head.next->prev = b; 54 bcache.head.next = b; 55 } 56 } 57 58 // Look through buffer cache for block on device dev. 59 // If not found, allocate a buffer. 60 // In either case, return locked buffer. 61 static struct buf* 62 bget(uint dev, uint blockno) 63 { 64 struct buf *b; 65 66 acquire(&bcache.lock); 67 68 // Is the block already cached? 69 for(b = bcache.head.next; b != &bcache.head; b = b->next){ 70 if(b->dev == dev && b->blockno == blockno){ 71 b->refcnt++; 72 release(&bcache.lock); 73 acquiresleep(&b->lock); 74 return b; 75 } 76 } 77 78 // Not cached; recycle some unused buffer and clean buffer 79 // "clean" because B_DIRTY and not locked means log.c 80 // hasn't yet committed the changes to the buffer. 81 for(b = bcache.head.prev; b != &bcache.head; b = b->prev){ 82 if(b->refcnt == 0 && (b->flags & B_DIRTY) == 0) { 83 b->dev = dev; 84 b->blockno = blockno; 85 b->flags = 0; 86 b->refcnt = 1; 87 release(&bcache.lock); 88 acquiresleep(&b->lock); 89 return b; 90 } 91 } 92 panic("bget: no buffers"); 93 } 94 95 // Return a locked buf with the contents of the indicated block. 96 struct buf* 97 bread(uint dev, uint blockno) 98 { 99 struct buf *b; 100 101 b = bget(dev, blockno); 102 if(!(b->flags & B_VALID)) { 103 iderw(b); 104 } 105 return b; 106 } 107 108 // Write b's contents to disk. Must be locked. 109 void 110 bwrite(struct buf *b) 111 { 112 if(!holdingsleep(&b->lock)) 113 panic("bwrite"); 114 b->flags |= B_DIRTY; 115 iderw(b); 116 } 117 118 // Release a locked buffer. 119 // Move to the head of the MRU list. 120 void 121 brelse(struct buf *b) 122 { 123 if(!holdingsleep(&b->lock)) 124 panic("brelse"); 125 126 releasesleep(&b->lock); 127 128 acquire(&bcache.lock); 129 b->refcnt--; 130 if (b->refcnt == 0) { 131 // no one is waiting for it. 132 b->next->prev = b->prev; 133 b->prev->next = b->next; 134 b->next = bcache.head.next; 135 b->prev = &bcache.head; 136 bcache.head.next->prev = b; 137 bcache.head.next = b; 138 } 139 140 release(&bcache.lock); 141 } 142 //PAGEBREAK! 143 // Blank page. 144 145