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
29struct {
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
38void
39binit(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.
61static struct buf*
62bget(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 an unused buffer.
79 // Even if refcnt==0, B_DIRTY indicates a buffer is in use
80 // because log.c has modified it but not yet committed it.
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.
96struct buf*
97bread(uint dev, uint blockno)
98{
99 struct buf *b;
100
101 b = bget(dev, blockno);
102 if((b->flags & B_VALID) == 0) {
103 iderw(b);
104 }
105 return b;
106}
107
108// Write b's contents to disk. Must be locked.
109void
110bwrite(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.
120void
121brelse(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