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