1 /*
2 * Memory-only VtBlock cache.
3 *
4 * The cached Venti blocks are in the hash chains.
5 * The cached local blocks are only in the blocks array.
6 * The free blocks are in the heap, which is supposed to
7 * be indexed by second-to-last use but actually
8 * appears to be last use.
9 */
10
11 #include <u.h>
12 #include <libc.h>
13 #include <venti.h>
14
15 int vtcachenread;
16 int vtcachencopy;
17 int vtcachenwrite;
18 int vttracelevel;
19
20 enum {
21 BioLocal = 1,
22 BioVenti,
23 BioReading,
24 BioWriting,
25 BioEmpty,
26 BioVentiError
27 };
28 enum {
29 BadHeap = ~0
30 };
31 struct VtCache
32 {
33 QLock lk;
34 VtConn *z;
35 u32int blocksize;
36 u32int now; /* ticks for usage time stamps */
37 VtBlock **hash; /* hash table for finding addresses */
38 int nhash;
39 VtBlock **heap; /* heap for finding victims */
40 int nheap;
41 VtBlock *block; /* all allocated blocks */
42 int nblock;
43 uchar *mem; /* memory for all blocks and data */
44 int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);
45 };
46
47 static void cachecheck(VtCache*);
48
49 VtCache*
vtcachealloc(VtConn * z,int blocksize,ulong nblock)50 vtcachealloc(VtConn *z, int blocksize, ulong nblock)
51 {
52 uchar *p;
53 VtCache *c;
54 int i;
55 VtBlock *b;
56
57 c = vtmallocz(sizeof(VtCache));
58
59 c->z = z;
60 c->blocksize = (blocksize + 127) & ~127;
61 c->nblock = nblock;
62 c->nhash = nblock;
63 c->hash = vtmallocz(nblock*sizeof(VtBlock*));
64 c->heap = vtmallocz(nblock*sizeof(VtBlock*));
65 c->block = vtmallocz(nblock*sizeof(VtBlock));
66 c->mem = vtmallocz(nblock*c->blocksize);
67 c->write = vtwrite;
68
69 p = c->mem;
70 for(i=0; i<nblock; i++){
71 b = &c->block[i];
72 b->addr = NilBlock;
73 b->c = c;
74 b->data = p;
75 b->heap = i;
76 c->heap[i] = b;
77 p += c->blocksize;
78 }
79 c->nheap = nblock;
80 cachecheck(c);
81 return c;
82 }
83
84 /*
85 * BUG This is here so that vbackup can override it and do some
86 * pipelining of writes. Arguably vtwrite or vtwritepacket or the
87 * cache itself should be providing this functionality.
88 */
89 void
vtcachesetwrite(VtCache * c,int (* write)(VtConn *,uchar[VtScoreSize],uint,uchar *,int))90 vtcachesetwrite(VtCache *c, int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int))
91 {
92 if(write == nil)
93 write = vtwrite;
94 c->write = write;
95 }
96
97 void
vtcachefree(VtCache * c)98 vtcachefree(VtCache *c)
99 {
100 int i;
101
102 qlock(&c->lk);
103
104 cachecheck(c);
105 for(i=0; i<c->nblock; i++)
106 assert(c->block[i].ref == 0);
107
108 vtfree(c->hash);
109 vtfree(c->heap);
110 vtfree(c->block);
111 vtfree(c->mem);
112 vtfree(c);
113 }
114
115 static void
vtcachedump(VtCache * c)116 vtcachedump(VtCache *c)
117 {
118 int i;
119 VtBlock *b;
120
121 for(i=0; i<c->nblock; i++){
122 b = &c->block[i];
123 print("cache block %d: type %d score %V iostate %d addr %d ref %d nlock %d\n",
124 i, b->type, b->score, b->iostate, b->addr, b->ref, b->nlock);
125 }
126 }
127
128 static void
cachecheck(VtCache * c)129 cachecheck(VtCache *c)
130 {
131 u32int size, now;
132 int i, k, refed;
133 VtBlock *b;
134
135 size = c->blocksize;
136 now = c->now;
137
138 for(i = 0; i < c->nheap; i++){
139 if(c->heap[i]->heap != i)
140 sysfatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
141 if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
142 sysfatal("bad heap ordering");
143 k = (i << 1) + 1;
144 if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
145 sysfatal("bad heap ordering");
146 k++;
147 if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
148 sysfatal("bad heap ordering");
149 }
150
151 refed = 0;
152 for(i = 0; i < c->nblock; i++){
153 b = &c->block[i];
154 if(b->data != &c->mem[i * size])
155 sysfatal("mis-blocked at %d", i);
156 if(b->ref && b->heap == BadHeap)
157 refed++;
158 else if(b->addr != NilBlock)
159 refed++;
160 }
161 assert(c->nheap + refed == c->nblock);
162 refed = 0;
163 for(i = 0; i < c->nblock; i++){
164 b = &c->block[i];
165 if(b->ref){
166 refed++;
167 }
168 }
169 }
170
171 static int
upheap(int i,VtBlock * b)172 upheap(int i, VtBlock *b)
173 {
174 VtBlock *bb;
175 u32int now;
176 int p;
177 VtCache *c;
178
179 c = b->c;
180 now = c->now;
181 for(; i != 0; i = p){
182 p = (i - 1) >> 1;
183 bb = c->heap[p];
184 if(b->used - now >= bb->used - now)
185 break;
186 c->heap[i] = bb;
187 bb->heap = i;
188 }
189 c->heap[i] = b;
190 b->heap = i;
191
192 return i;
193 }
194
195 static int
downheap(int i,VtBlock * b)196 downheap(int i, VtBlock *b)
197 {
198 VtBlock *bb;
199 u32int now;
200 int k;
201 VtCache *c;
202
203 c = b->c;
204 now = c->now;
205 for(; ; i = k){
206 k = (i << 1) + 1;
207 if(k >= c->nheap)
208 break;
209 if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
210 k++;
211 bb = c->heap[k];
212 if(b->used - now <= bb->used - now)
213 break;
214 c->heap[i] = bb;
215 bb->heap = i;
216 }
217 c->heap[i] = b;
218 b->heap = i;
219 return i;
220 }
221
222 /*
223 * Delete a block from the heap.
224 * Called with c->lk held.
225 */
226 static void
heapdel(VtBlock * b)227 heapdel(VtBlock *b)
228 {
229 int i, si;
230 VtCache *c;
231
232 c = b->c;
233
234 si = b->heap;
235 if(si == BadHeap)
236 return;
237 b->heap = BadHeap;
238 c->nheap--;
239 if(si == c->nheap)
240 return;
241 b = c->heap[c->nheap];
242 i = upheap(si, b);
243 if(i == si)
244 downheap(i, b);
245 }
246
247 /*
248 * Insert a block into the heap.
249 * Called with c->lk held.
250 */
251 static void
heapins(VtBlock * b)252 heapins(VtBlock *b)
253 {
254 assert(b->heap == BadHeap);
255 upheap(b->c->nheap++, b);
256 }
257
258 /*
259 * locate the vtBlock with the oldest second to last use.
260 * remove it from the heap, and fix up the heap.
261 */
262 /* called with c->lk held */
263 static VtBlock*
vtcachebumpblock(VtCache * c)264 vtcachebumpblock(VtCache *c)
265 {
266 VtBlock *b;
267
268 /*
269 * locate the vtBlock with the oldest second to last use.
270 * remove it from the heap, and fix up the heap.
271 */
272 if(c->nheap == 0){
273 vtcachedump(c);
274 fprint(2, "vtcachebumpblock: no free blocks in vtCache");
275 abort();
276 }
277 b = c->heap[0];
278 heapdel(b);
279
280 assert(b->heap == BadHeap);
281 assert(b->ref == 0);
282
283 /*
284 * unchain the vtBlock from hash chain if any
285 */
286 if(b->prev){
287 *(b->prev) = b->next;
288 if(b->next)
289 b->next->prev = b->prev;
290 b->prev = nil;
291 }
292
293
294 if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
295 /* set vtBlock to a reasonable state */
296 b->ref = 1;
297 b->iostate = BioEmpty;
298 return b;
299 }
300
301 /*
302 * fetch a local block from the memory cache.
303 * if it's not there, load it, bumping some other Block.
304 * if we're out of free blocks, we're screwed.
305 */
306 VtBlock*
vtcachelocal(VtCache * c,u32int addr,int type)307 vtcachelocal(VtCache *c, u32int addr, int type)
308 {
309 VtBlock *b;
310
311 if(addr == 0)
312 sysfatal("vtcachelocal: asked for nonexistent block 0");
313 if(addr > c->nblock)
314 sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",
315 addr, c->nblock);
316
317 b = &c->block[addr-1];
318 if(b->addr == NilBlock || b->iostate != BioLocal)
319 sysfatal("vtcachelocal: block is not local");
320
321 if(b->type != type)
322 sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type);
323
324 qlock(&c->lk);
325 b->ref++;
326 qunlock(&c->lk);
327
328 qlock(&b->lk);
329 b->nlock = 1;
330 b->pc = getcallerpc(&c);
331 return b;
332 }
333
334 VtBlock*
vtcacheallocblock(VtCache * c,int type)335 vtcacheallocblock(VtCache *c, int type)
336 {
337 VtBlock *b;
338
339 qlock(&c->lk);
340 b = vtcachebumpblock(c);
341 b->iostate = BioLocal;
342 b->type = type;
343 b->addr = (b - c->block)+1;
344 vtzeroextend(type, b->data, 0, c->blocksize);
345 vtlocaltoglobal(b->addr, b->score);
346 qunlock(&c->lk);
347
348 qlock(&b->lk);
349 b->nlock = 1;
350 b->pc = getcallerpc(&c);
351 return b;
352 }
353
354 /*
355 * fetch a global (Venti) block from the memory cache.
356 * if it's not there, load it, bumping some other block.
357 */
358 VtBlock*
vtcacheglobal(VtCache * c,uchar score[VtScoreSize],int type)359 vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
360 {
361 VtBlock *b;
362 ulong h;
363 int n;
364 u32int addr;
365
366 if(vttracelevel)
367 fprint(2, "vtcacheglobal %V %d from %p\n", score, type, getcallerpc(&c));
368 addr = vtglobaltolocal(score);
369 if(addr != NilBlock){
370 if(vttracelevel)
371 fprint(2, "vtcacheglobal %V %d => local\n", score, type);
372 b = vtcachelocal(c, addr, type);
373 if(b)
374 b->pc = getcallerpc(&c);
375 return b;
376 }
377
378 h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
379
380 /*
381 * look for the block in the cache
382 */
383 qlock(&c->lk);
384 for(b = c->hash[h]; b != nil; b = b->next){
385 if(b->addr != NilBlock || memcmp(b->score, score, VtScoreSize) != 0 || b->type != type)
386 continue;
387 heapdel(b);
388 b->ref++;
389 qunlock(&c->lk);
390 if(vttracelevel)
391 fprint(2, "vtcacheglobal %V %d => found in cache %p; locking\n", score, type, b);
392 qlock(&b->lk);
393 b->nlock = 1;
394 if(b->iostate == BioVentiError){
395 if(chattyventi)
396 fprint(2, "cached read error for %V\n", score);
397 if(vttracelevel)
398 fprint(2, "vtcacheglobal %V %d => cache read error\n", score, type);
399 vtblockput(b);
400 werrstr("venti i/o error");
401 return nil;
402 }
403 if(vttracelevel)
404 fprint(2, "vtcacheglobal %V %d => found in cache; returning\n", score, type);
405 b->pc = getcallerpc(&c);
406 return b;
407 }
408
409 /*
410 * not found
411 */
412 b = vtcachebumpblock(c);
413 b->addr = NilBlock;
414 b->type = type;
415 memmove(b->score, score, VtScoreSize);
416 /* chain onto correct hash */
417 b->next = c->hash[h];
418 c->hash[h] = b;
419 if(b->next != nil)
420 b->next->prev = &b->next;
421 b->prev = &c->hash[h];
422
423 /*
424 * Lock b before unlocking c, so that others wait while we read.
425 *
426 * You might think there is a race between this qlock(b) before qunlock(c)
427 * and the qlock(c) while holding a qlock(b) in vtblockwrite. However,
428 * the block here can never be the block in a vtblockwrite, so we're safe.
429 * We're certainly living on the edge.
430 */
431 if(vttracelevel)
432 fprint(2, "vtcacheglobal %V %d => bumped; locking %p\n", score, type, b);
433 qlock(&b->lk);
434 b->nlock = 1;
435 qunlock(&c->lk);
436
437 vtcachenread++;
438 n = vtread(c->z, score, type, b->data, c->blocksize);
439 if(n < 0){
440 if(chattyventi)
441 fprint(2, "read %V: %r\n", score);
442 if(vttracelevel)
443 fprint(2, "vtcacheglobal %V %d => bumped; read error\n", score, type);
444 b->iostate = BioVentiError;
445 vtblockput(b);
446 return nil;
447 }
448 vtzeroextend(type, b->data, n, c->blocksize);
449 b->iostate = BioVenti;
450 b->nlock = 1;
451 if(vttracelevel)
452 fprint(2, "vtcacheglobal %V %d => loaded into cache; returning\n", score, type);
453 b->pc = getcallerpc(&b);
454 return b;
455 }
456
457 /*
458 * The thread that has locked b may refer to it by
459 * multiple names. Nlock counts the number of
460 * references the locking thread holds. It will call
461 * vtblockput once per reference.
462 */
463 void
vtblockduplock(VtBlock * b)464 vtblockduplock(VtBlock *b)
465 {
466 assert(b->nlock > 0);
467 b->nlock++;
468 }
469
470 /*
471 * we're done with the block.
472 * unlock it. can't use it after calling this.
473 */
474 void
vtblockput(VtBlock * b)475 vtblockput(VtBlock* b)
476 {
477 VtCache *c;
478
479 if(b == nil)
480 return;
481
482 if(0)fprint(2, "vtblockput: %d: %x %d %d\n", getpid(), b->addr, c->nheap, b->iostate);
483 if(vttracelevel)
484 fprint(2, "vtblockput %p from %p\n", b, getcallerpc(&b));
485
486 if(--b->nlock > 0)
487 return;
488
489 /*
490 * b->nlock should probably stay at zero while
491 * the vtBlock is unlocked, but diskThread and vtSleep
492 * conspire to assume that they can just qlock(&b->lk); vtblockput(b),
493 * so we have to keep b->nlock set to 1 even
494 * when the vtBlock is unlocked.
495 */
496 assert(b->nlock == 0);
497 b->nlock = 1;
498
499 qunlock(&b->lk);
500 c = b->c;
501 qlock(&c->lk);
502
503 if(--b->ref > 0){
504 qunlock(&c->lk);
505 return;
506 }
507
508 assert(b->ref == 0);
509 switch(b->iostate){
510 case BioVenti:
511 /*if(b->addr != NilBlock) print("blockput %d\n", b->addr); */
512 b->used = c->now++;
513 /* fall through */
514 case BioVentiError:
515 heapins(b);
516 break;
517 case BioLocal:
518 break;
519 }
520 qunlock(&c->lk);
521 }
522
523 int
vtblockwrite(VtBlock * b)524 vtblockwrite(VtBlock *b)
525 {
526 uchar score[VtScoreSize];
527 VtCache *c;
528 uint h;
529 int n;
530
531 if(b->iostate != BioLocal){
532 werrstr("vtblockwrite: not a local block");
533 return -1;
534 }
535
536 c = b->c;
537 n = vtzerotruncate(b->type, b->data, c->blocksize);
538 vtcachenwrite++;
539 if(c->write(c->z, score, b->type, b->data, n) < 0)
540 return -1;
541
542 memmove(b->score, score, VtScoreSize);
543
544 qlock(&c->lk);
545 b->addr = NilBlock; /* now on venti */
546 b->iostate = BioVenti;
547 h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
548 b->next = c->hash[h];
549 c->hash[h] = b;
550 if(b->next != nil)
551 b->next->prev = &b->next;
552 b->prev = &c->hash[h];
553 qunlock(&c->lk);
554 return 0;
555 }
556
557 uint
vtcacheblocksize(VtCache * c)558 vtcacheblocksize(VtCache *c)
559 {
560 return c->blocksize;
561 }
562
563 VtBlock*
vtblockcopy(VtBlock * b)564 vtblockcopy(VtBlock *b)
565 {
566 VtBlock *bb;
567
568 vtcachencopy++;
569 bb = vtcacheallocblock(b->c, b->type);
570 if(bb == nil){
571 vtblockput(b);
572 return nil;
573 }
574 memmove(bb->data, b->data, b->c->blocksize);
575 vtblockput(b);
576 bb->pc = getcallerpc(&b);
577 return bb;
578 }
579
580 void
vtlocaltoglobal(u32int addr,uchar score[VtScoreSize])581 vtlocaltoglobal(u32int addr, uchar score[VtScoreSize])
582 {
583 memset(score, 0, 16);
584 score[16] = addr>>24;
585 score[17] = addr>>16;
586 score[18] = addr>>8;
587 score[19] = addr;
588 }
589
590
591 u32int
vtglobaltolocal(uchar score[VtScoreSize])592 vtglobaltolocal(uchar score[VtScoreSize])
593 {
594 static uchar zero[16];
595 if(memcmp(score, zero, 16) != 0)
596 return NilBlock;
597 return (score[16]<<24)|(score[17]<<16)|(score[18]<<8)|score[19];
598 }
599
600