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 three state flags internally: 17 // * B_BUSY: the block has been returned from bread 18 // and has not been passed back to brelse. 19 // * B_VALID: the buffer data has been read from the disk. 20 // * B_DIRTY: the buffer data has been modified 21 // and needs to be written to disk. 22 23 #include "types.h" 24 #include "defs.h" 25 #include "param.h" 26 #include "spinlock.h" 27 #include "fs.h" 28 #include "buf.h" 29 30 struct { 31 struct spinlock lock; 32 struct buf buf[NBUF]; 33 34 // Linked list of all buffers, through prev/next. 35 // head.next is most recently used. 36 struct buf head; 37 } bcache; 38 39 void 40 binit(void) 41 { 42 struct buf *b; 43 44 initlock(&bcache.lock, "bcache"); 45 46 //PAGEBREAK! 47 // Create linked list of buffers 48 bcache.head.prev = &bcache.head; 49 bcache.head.next = &bcache.head; 50 for(b = bcache.buf; b < bcache.buf+NBUF; b++){ 51 b->next = bcache.head.next; 52 b->prev = &bcache.head; 53 b->dev = -1; 54 bcache.head.next->prev = b; 55 bcache.head.next = b; 56 } 57 } 58 59 // Look through buffer cache for block on device dev. 60 // If not found, allocate a buffer. 61 // In either case, return B_BUSY buffer. 62 static struct buf* 63 bget(uint dev, uint blockno) 64 { 65 struct buf *b; 66 67 acquire(&bcache.lock); 68 69 loop: 70 // Is the block already cached? 71 for(b = bcache.head.next; b != &bcache.head; b = b->next){ 72 if(b->dev == dev && b->blockno == blockno){ 73 if(!(b->flags & B_BUSY)){ 74 b->flags |= B_BUSY; 75 release(&bcache.lock); 76 return b; 77 } 78 sleep(b, &bcache.lock); 79 goto loop; 80 } 81 } 82 83 // Not cached; recycle some non-busy and clean buffer. 84 // "clean" because B_DIRTY and !B_BUSY means log.c 85 // hasn't yet committed the changes to the buffer. 86 for(b = bcache.head.prev; b != &bcache.head; b = b->prev){ 87 if((b->flags & B_BUSY) == 0 && (b->flags & B_DIRTY) == 0){ 88 b->dev = dev; 89 b->blockno = blockno; 90 b->flags = B_BUSY; 91 release(&bcache.lock); 92 return b; 93 } 94 } 95 panic("bget: no buffers"); 96 } 97 98 // Return a B_BUSY buf with the contents of the indicated block. 99 struct buf* 100 bread(uint dev, uint blockno) 101 { 102 struct buf *b; 103 104 b = bget(dev, blockno); 105 if(!(b->flags & B_VALID)) { 106 iderw(b); 107 } 108 return b; 109 } 110 111 // Write b's contents to disk. Must be B_BUSY. 112 void 113 bwrite(struct buf *b) 114 { 115 if((b->flags & B_BUSY) == 0) 116 panic("bwrite"); 117 b->flags |= B_DIRTY; 118 iderw(b); 119 } 120 121 // Release a B_BUSY buffer. 122 // Move to the head of the MRU list. 123 void 124 brelse(struct buf *b) 125 { 126 if((b->flags & B_BUSY) == 0) 127 panic("brelse"); 128 129 acquire(&bcache.lock); 130 131 b->next->prev = b->prev; 132 b->prev->next = b->next; 133 b->next = bcache.head.next; 134 b->prev = &bcache.head; 135 bcache.head.next->prev = b; 136 bcache.head.next = b; 137 138 b->flags &= ~B_BUSY; 139 wakeup(b); 140 141 release(&bcache.lock); 142 } 143 //PAGEBREAK! 144 // Blank page. 145 146