1 0c98da8b 2005-07-13 devnull #include <u.h>
2 0c98da8b 2005-07-13 devnull #include <libc.h>
3 0c98da8b 2005-07-13 devnull #include <diskfs.h>
6 0c98da8b 2005-07-13 devnull * Disk cache. Caches by offset, so higher levels have
7 0c98da8b 2005-07-13 devnull * to deal with alignment issues (if we get asked for the
8 6fc7da3c 2006-10-19 devnull * blocks at offsets 0 and 1, we'll do two reads).
11 0c98da8b 2005-07-13 devnull typedef struct DiskCache DiskCache;
12 0c98da8b 2005-07-13 devnull typedef struct DiskCacheBlock DiskCacheBlock;
14 0c98da8b 2005-07-13 devnull struct DiskCache
16 0c98da8b 2005-07-13 devnull Disk disk;
17 0c98da8b 2005-07-13 devnull Disk *subdisk;
18 0c98da8b 2005-07-13 devnull DiskCacheBlock **h;
19 0c98da8b 2005-07-13 devnull DiskCacheBlock *lruhead;
20 0c98da8b 2005-07-13 devnull DiskCacheBlock *lrutail;
21 0c98da8b 2005-07-13 devnull int nhash;
22 0c98da8b 2005-07-13 devnull int blocksize;
26 0c98da8b 2005-07-13 devnull struct DiskCacheBlock
28 0c98da8b 2005-07-13 devnull Block block;
29 0c98da8b 2005-07-13 devnull Block *subblock;
32 0c98da8b 2005-07-13 devnull DiskCache *dc;
33 0c98da8b 2005-07-13 devnull DiskCacheBlock *next;
34 0c98da8b 2005-07-13 devnull DiskCacheBlock *lrunext;
35 0c98da8b 2005-07-13 devnull DiskCacheBlock *lruprev;
36 0c98da8b 2005-07-13 devnull u64int offset;
39 0c98da8b 2005-07-13 devnull static void
40 0c98da8b 2005-07-13 devnull addtohash(DiskCache *d, DiskCacheBlock *b, u64int offset)
44 0c98da8b 2005-07-13 devnull if(b->offset != ~(u64int)0){
45 0c98da8b 2005-07-13 devnull fprint(2, "bad offset in addtohash\n");
48 0c98da8b 2005-07-13 devnull b->offset = offset;
49 0c98da8b 2005-07-13 devnull h = offset % d->nhash;
50 0c98da8b 2005-07-13 devnull b->next = d->h[h];
51 0c98da8b 2005-07-13 devnull d->h[h] = b;
54 0c98da8b 2005-07-13 devnull static void
55 0c98da8b 2005-07-13 devnull delfromhash(DiskCache *d, DiskCacheBlock *b)
58 0c98da8b 2005-07-13 devnull DiskCacheBlock **l;
60 0c98da8b 2005-07-13 devnull if(b->offset == ~(u64int)0)
63 0c98da8b 2005-07-13 devnull h = b->offset % d->nhash;
64 0c98da8b 2005-07-13 devnull for(l=&d->h[h]; *l; l=&(*l)->next)
65 0c98da8b 2005-07-13 devnull if(*l == b){
66 0c98da8b 2005-07-13 devnull *l = b->next;
67 0c98da8b 2005-07-13 devnull b->offset = ~(u64int)0;
70 0c98da8b 2005-07-13 devnull fprint(2, "delfromhash: didn't find in hash table\n");
74 0c98da8b 2005-07-13 devnull static void
75 0c98da8b 2005-07-13 devnull putmru(DiskCache *d, DiskCacheBlock *b)
77 0c98da8b 2005-07-13 devnull b->lruprev = nil;
78 0c98da8b 2005-07-13 devnull b->lrunext = d->lruhead;
79 0c98da8b 2005-07-13 devnull d->lruhead = b;
80 0c98da8b 2005-07-13 devnull if(b->lrunext == nil)
81 0c98da8b 2005-07-13 devnull d->lrutail = b;
83 0c98da8b 2005-07-13 devnull b->lrunext->lruprev = b;
86 0c98da8b 2005-07-13 devnull static void
87 0c98da8b 2005-07-13 devnull putlru(DiskCache *d, DiskCacheBlock *b)
89 0c98da8b 2005-07-13 devnull b->lruprev = d->lrutail;
90 0c98da8b 2005-07-13 devnull b->lrunext = nil;
91 0c98da8b 2005-07-13 devnull d->lrutail = b;
92 0c98da8b 2005-07-13 devnull if(b->lruprev == nil)
93 0c98da8b 2005-07-13 devnull d->lruhead = b;
95 0c98da8b 2005-07-13 devnull b->lruprev->lrunext = b;
98 0c98da8b 2005-07-13 devnull static void
99 0c98da8b 2005-07-13 devnull delfromlru(DiskCache *d, DiskCacheBlock *b)
101 0c98da8b 2005-07-13 devnull if(b->lruprev)
102 0c98da8b 2005-07-13 devnull b->lruprev->lrunext = b->lrunext;
104 0c98da8b 2005-07-13 devnull d->lruhead = b->lrunext;
105 0c98da8b 2005-07-13 devnull if(b->lrunext)
106 0c98da8b 2005-07-13 devnull b->lrunext->lruprev = b->lruprev;
108 0c98da8b 2005-07-13 devnull d->lrutail = b->lruprev;
111 0c98da8b 2005-07-13 devnull static DiskCacheBlock*
112 0c98da8b 2005-07-13 devnull getlru(DiskCache *d)
114 0c98da8b 2005-07-13 devnull DiskCacheBlock *b;
116 0c98da8b 2005-07-13 devnull b = d->lrutail;
118 0c98da8b 2005-07-13 devnull delfromlru(d, b);
119 0c98da8b 2005-07-13 devnull delfromhash(d, b);
120 0c98da8b 2005-07-13 devnull blockput(b->subblock);
121 0c98da8b 2005-07-13 devnull b->subblock = nil;
123 0c98da8b 2005-07-13 devnull return b;
126 0c98da8b 2005-07-13 devnull static DiskCacheBlock*
127 0c98da8b 2005-07-13 devnull findblock(DiskCache *d, u64int offset)
130 0c98da8b 2005-07-13 devnull DiskCacheBlock *b;
132 0c98da8b 2005-07-13 devnull h = offset % d->nhash;
133 0c98da8b 2005-07-13 devnull for(b=d->h[h]; b; b=b->next)
134 0c98da8b 2005-07-13 devnull if(b->offset == offset)
135 0c98da8b 2005-07-13 devnull return b;
136 0c98da8b 2005-07-13 devnull return nil;
139 0c98da8b 2005-07-13 devnull static DiskCacheBlock*
140 0c98da8b 2005-07-13 devnull diskcachereadbig(DiskCache *d, u64int offset)
142 0c98da8b 2005-07-13 devnull Block *b;
143 0c98da8b 2005-07-13 devnull DiskCacheBlock *dcb;
145 0c98da8b 2005-07-13 devnull lock(&d->lk);
146 0c98da8b 2005-07-13 devnull dcb = findblock(d, offset);
147 0c98da8b 2005-07-13 devnull if(dcb){
148 cbeb0b26 2006-04-01 devnull /*fprint(2, "found %llud in cache %p\n", (uvlong)offset, dcb);*/
149 0c98da8b 2005-07-13 devnull if(dcb->ref++ == 0)
150 0c98da8b 2005-07-13 devnull delfromlru(d, dcb);
151 0c98da8b 2005-07-13 devnull unlock(&d->lk);
152 0c98da8b 2005-07-13 devnull return dcb;
155 0c98da8b 2005-07-13 devnull dcb = getlru(d);
156 0c98da8b 2005-07-13 devnull unlock(&d->lk);
157 0c98da8b 2005-07-13 devnull if(dcb == nil){
158 0c98da8b 2005-07-13 devnull fprint(2, "diskcacheread: all blocks in use\n");
159 0c98da8b 2005-07-13 devnull return nil;
162 0c98da8b 2005-07-13 devnull b = diskread(d->subdisk, d->blocksize, offset);
163 0c98da8b 2005-07-13 devnull lock(&d->lk);
164 0c98da8b 2005-07-13 devnull if(b == nil){
165 0c98da8b 2005-07-13 devnull putlru(d, dcb);
166 0c98da8b 2005-07-13 devnull dcb = nil;
168 cbeb0b26 2006-04-01 devnull /*fprint(2, "read %llud from disk %p\n", (uvlong)offset, dcb); */
169 0c98da8b 2005-07-13 devnull dcb->subblock = b;
170 0c98da8b 2005-07-13 devnull dcb->ref++;
171 0c98da8b 2005-07-13 devnull addtohash(d, dcb, offset);
173 0c98da8b 2005-07-13 devnull unlock(&d->lk);
174 0c98da8b 2005-07-13 devnull return dcb;
177 0c98da8b 2005-07-13 devnull static void
178 0c98da8b 2005-07-13 devnull diskcacheblockclose(Block *bb)
180 0c98da8b 2005-07-13 devnull DiskCacheBlock *b = bb->priv;
182 0c98da8b 2005-07-13 devnull lock(&b->dc->lk);
183 0c98da8b 2005-07-13 devnull if(--b->ref == 0)
184 0c98da8b 2005-07-13 devnull putmru(b->dc, b);
185 0c98da8b 2005-07-13 devnull unlock(&b->dc->lk);
186 0c98da8b 2005-07-13 devnull free(bb);
189 0c98da8b 2005-07-13 devnull static Block*
190 0c98da8b 2005-07-13 devnull diskcacheread(Disk *dd, u32int len, u64int offset)
192 0c98da8b 2005-07-13 devnull int frag, dlen;
193 0c98da8b 2005-07-13 devnull DiskCache *d = (DiskCache*)dd;
194 0c98da8b 2005-07-13 devnull DiskCacheBlock *dcb;
195 0c98da8b 2005-07-13 devnull Block *b;
197 0c98da8b 2005-07-13 devnull if(offset/d->blocksize != (offset+len-1)/d->blocksize){
198 0c98da8b 2005-07-13 devnull fprint(2, "diskBigRead: request for block crossing big block boundary\n");
199 0c98da8b 2005-07-13 devnull return nil;
202 0c98da8b 2005-07-13 devnull b = mallocz(sizeof(Block), 1);
203 0c98da8b 2005-07-13 devnull if(b == nil)
204 0c98da8b 2005-07-13 devnull return nil;
206 0c98da8b 2005-07-13 devnull frag = offset%d->blocksize;
208 0c98da8b 2005-07-13 devnull dcb = diskcachereadbig(d, offset-frag);
209 0c98da8b 2005-07-13 devnull if(dcb == nil){
210 0c98da8b 2005-07-13 devnull free(b);
211 0c98da8b 2005-07-13 devnull return nil;
213 0c98da8b 2005-07-13 devnull b->priv = dcb;
214 0c98da8b 2005-07-13 devnull b->_close = diskcacheblockclose;
215 0c98da8b 2005-07-13 devnull b->data = dcb->subblock->data+frag;
217 0c98da8b 2005-07-13 devnull dlen = dcb->subblock->len;
218 0c98da8b 2005-07-13 devnull if(frag+len >= dlen){
219 0c98da8b 2005-07-13 devnull if(frag >= dlen){
220 0c98da8b 2005-07-13 devnull blockput(b);
221 0c98da8b 2005-07-13 devnull return nil;
223 0c98da8b 2005-07-13 devnull len = dlen-frag;
225 0c98da8b 2005-07-13 devnull b->len = len;
226 cbeb0b26 2006-04-01 devnull /*fprint(2, "offset %llud at pointer %p %lux\n", (uvlong)offset, b->data, *(ulong*)(b->data+4)); */
227 0c98da8b 2005-07-13 devnull return b;
231 0c98da8b 2005-07-13 devnull * It's okay to remove these from the hash table.
232 0c98da8b 2005-07-13 devnull * Either the block is in use by someone or it is on
233 0c98da8b 2005-07-13 devnull * the lru list. If it's in use it will get put on the lru
234 0c98da8b 2005-07-13 devnull * list once the refs go away.
236 0c98da8b 2005-07-13 devnull static int
237 0c98da8b 2005-07-13 devnull diskcachesync(Disk *dd)
239 0c98da8b 2005-07-13 devnull DiskCache *d = (DiskCache*)dd;
240 0c98da8b 2005-07-13 devnull DiskCacheBlock *b, *nextb;
243 0c98da8b 2005-07-13 devnull lock(&d->lk);
244 0c98da8b 2005-07-13 devnull for(i=0; i<d->nhash; i++){
245 0c98da8b 2005-07-13 devnull for(b=d->h[i]; b; b=nextb){
246 0c98da8b 2005-07-13 devnull nextb = b->next;
247 0c98da8b 2005-07-13 devnull b->next = nil;
248 0c98da8b 2005-07-13 devnull b->offset = ~(u64int)0;
250 0c98da8b 2005-07-13 devnull d->h[i] = nil;
252 0c98da8b 2005-07-13 devnull unlock(&d->lk);
253 0c98da8b 2005-07-13 devnull return disksync(d->subdisk);
256 0c98da8b 2005-07-13 devnull static void
257 0c98da8b 2005-07-13 devnull diskcacheclose(Disk *dd)
259 0c98da8b 2005-07-13 devnull DiskCacheBlock *b;
260 0c98da8b 2005-07-13 devnull DiskCache *d = (DiskCache*)dd;
262 0c98da8b 2005-07-13 devnull diskclose(d->subdisk);
263 0c98da8b 2005-07-13 devnull for(b=d->lruhead; b; b=b->lrunext)
264 0c98da8b 2005-07-13 devnull blockput(b->subblock);
265 0c98da8b 2005-07-13 devnull free(d);
268 0c98da8b 2005-07-13 devnull /* needn't be fast */
269 0c98da8b 2005-07-13 devnull static int
270 0c98da8b 2005-07-13 devnull isprime(int n)
274 0c98da8b 2005-07-13 devnull for(i=2; i*i<=n; i++)
275 0c98da8b 2005-07-13 devnull if(n%i == 0)
276 0c98da8b 2005-07-13 devnull return 0;
277 0c98da8b 2005-07-13 devnull return 1;
281 0c98da8b 2005-07-13 devnull diskcache(Disk *subdisk, uint blocksize, uint ncache)
283 0c98da8b 2005-07-13 devnull int nhash, i;
284 0c98da8b 2005-07-13 devnull DiskCache *d;
285 0c98da8b 2005-07-13 devnull DiskCacheBlock *b;
287 0c98da8b 2005-07-13 devnull nhash = ncache;
288 0c98da8b 2005-07-13 devnull while(nhash > 1 && !isprime(nhash))
289 0c98da8b 2005-07-13 devnull nhash--;
290 0c98da8b 2005-07-13 devnull d = mallocz(sizeof(DiskCache)+ncache*sizeof(DiskCacheBlock)+nhash*sizeof(DiskCacheBlock*), 1);
291 0c98da8b 2005-07-13 devnull if(d == nil)
292 0c98da8b 2005-07-13 devnull return nil;
294 0c98da8b 2005-07-13 devnull b = (DiskCacheBlock*)&d[1];
295 0c98da8b 2005-07-13 devnull d->h = (DiskCacheBlock**)&b[ncache];
296 0c98da8b 2005-07-13 devnull d->nhash = nhash;
297 0c98da8b 2005-07-13 devnull d->blocksize = blocksize;
298 0c98da8b 2005-07-13 devnull d->subdisk = subdisk;
299 0c98da8b 2005-07-13 devnull d->disk._read = diskcacheread;
300 0c98da8b 2005-07-13 devnull d->disk._sync = diskcachesync;
301 0c98da8b 2005-07-13 devnull d->disk._close = diskcacheclose;
303 0c98da8b 2005-07-13 devnull for(i=0; i<ncache; i++){
304 0c98da8b 2005-07-13 devnull b[i].block._close = diskcacheblockclose;
305 0c98da8b 2005-07-13 devnull b[i].offset = ~(u64int)0;
306 0c98da8b 2005-07-13 devnull b[i].dc = d;
307 0c98da8b 2005-07-13 devnull putlru(d, &b[i]);
310 0c98da8b 2005-07-13 devnull return &d->disk;