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 flush 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 initialized 20 // with the associated disk block contents. 21 // * B_DIRTY: the buffer data has been modified 22 // and needs to be written to disk. 23 24 #include "types.h" 25 #include "defs.h" 26 #include "param.h" 27 #include "spinlock.h" 28 #include "buf.h" 29 30 struct buf buf[NBUF]; 31 struct spinlock buf_table_lock; 32 33 // Linked list of all buffers, through prev/next. 34 // bufhead->next is most recently used. 35 // bufhead->tail is least recently used. 36 struct buf bufhead; 37 38 void 39 binit(void) 40 { 41 struct buf *b; 42 43 initlock(&buf_table_lock, "buf_table"); 44 45 //PAGEBREAK! 46 // Create linked list of buffers 47 bufhead.prev = &bufhead; 48 bufhead.next = &bufhead; 49 for(b = buf; b < buf+NBUF; b++){ 50 b->next = bufhead.next; 51 b->prev = &bufhead; 52 bufhead.next->prev = b; 53 bufhead.next = b; 54 } 55 } 56 57 // Look through buffer cache for sector on device dev. 58 // If not found, allocate fresh block. 59 // In either case, return locked buffer. 60 static struct buf* 61 bget(uint dev, uint sector) 62 { 63 struct buf *b; 64 65 acquire(&buf_table_lock); 66 67 loop: 68 // Try for cached block. 69 for(b = bufhead.next; b != &bufhead; b = b->next){ 70 if((b->flags & (B_BUSY|B_VALID)) && 71 b->dev == dev && b->sector == sector){ 72 if(!(b->flags & B_BUSY)){ 73 b->flags |= B_BUSY; 74 release(&buf_table_lock); 75 return b; 76 } 77 sleep(b, &buf_table_lock); 78 goto loop; 79 } 80 } 81 82 // Allocate fresh block. 83 for(b = bufhead.prev; b != &bufhead; b = b->prev){ 84 if((b->flags & B_BUSY) == 0){ 85 b->dev = dev; 86 b->sector = sector; 87 b->flags = B_BUSY; 88 release(&buf_table_lock); 89 return b; 90 } 91 } 92 panic("bget: no buffers"); 93 } 94 95 // Return a B_BUSY buf with the contents of the indicated disk sector. 96 struct buf* 97 bread(uint dev, uint sector) 98 { 99 struct buf *b; 100 101 b = bget(dev, sector); 102 if(!(b->flags & B_VALID)) 103 iderw(b); 104 return b; 105 } 106 107 // Write buf's contents to disk. Must be locked. 108 void 109 bwrite(struct buf *b) 110 { 111 if((b->flags & B_BUSY) == 0) 112 panic("bwrite"); 113 b->flags |= B_DIRTY; 114 iderw(b); 115 } 116 117 // Release the buffer buf. 118 void 119 brelse(struct buf *b) 120 { 121 if((b->flags & B_BUSY) == 0) 122 panic("brelse"); 123 124 acquire(&buf_table_lock); 125 126 b->next->prev = b->prev; 127 b->prev->next = b->next; 128 b->next = bufhead.next; 129 b->prev = &bufhead; 130 bufhead.next->prev = b; 131 bufhead.next = b; 132 133 b->flags &= ~B_BUSY; 134 wakeup(b); 135 136 release(&buf_table_lock); 137 } 138 139