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 "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 b->dev = -1; 53 bcache.head.next->prev = b; 54 bcache.head.next = b; 55 } 56 } 57 58 // Look through buffer cache for sector on device dev. 59 // If not found, allocate fresh block. 60 // In either case, return B_BUSY buffer. 61 static struct buf* 62 bget(uint dev, uint sector) 63 { 64 struct buf *b; 65 66 acquire(&bcache.lock); 67 68 loop: 69 // Is the sector already cached? 70 for(b = bcache.head.next; b != &bcache.head; b = b->next){ 71 if(b->dev == dev && b->sector == sector){ 72 if(!(b->flags & B_BUSY)){ 73 b->flags |= B_BUSY; 74 release(&bcache.lock); 75 return b; 76 } 77 sleep(b, &bcache.lock); 78 goto loop; 79 } 80 } 81 82 // Not cached; recycle some non-busy and clean buffer. 83 // "clean" because B_DIRTY and !B_BUSY means log.c 84 // hasn't yet committed the changes to the buffer. 85 for(b = bcache.head.prev; b != &bcache.head; b = b->prev){ 86 if((b->flags & B_BUSY) == 0 && (b->flags & B_DIRTY) == 0){ 87 b->dev = dev; 88 b->sector = sector; 89 b->flags = B_BUSY; 90 release(&bcache.lock); 91 return b; 92 } 93 } 94 panic("bget: no buffers"); 95 } 96 97 // Return a B_BUSY buf with the contents of the indicated disk sector. 98 struct buf* 99 bread(uint dev, uint sector) 100 { 101 struct buf *b; 102 103 b = bget(dev, sector); 104 if(!(b->flags & B_VALID)) 105 iderw(b); 106 return b; 107 } 108 109 // Write b's contents to disk. Must be B_BUSY. 110 void 111 bwrite(struct buf *b) 112 { 113 if((b->flags & B_BUSY) == 0) 114 panic("bwrite"); 115 b->flags |= B_DIRTY; 116 iderw(b); 117 } 118 119 // Release a B_BUSY buffer. 120 // Move to the head of the MRU list. 121 void 122 brelse(struct buf *b) 123 { 124 if((b->flags & B_BUSY) == 0) 125 panic("brelse"); 126 127 acquire(&bcache.lock); 128 129 b->next->prev = b->prev; 130 b->prev->next = b->next; 131 b->next = bcache.head.next; 132 b->prev = &bcache.head; 133 bcache.head.next->prev = b; 134 bcache.head.next = b; 135 136 b->flags &= ~B_BUSY; 137 wakeup(b); 138 139 release(&bcache.lock); 140 } 141 142