2 * Memory-only VtBlock cache.
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.
36 u32int now; /* ticks for usage time stamps */
37 VtBlock **hash; /* hash table for finding addresses */
39 VtBlock **heap; /* heap for finding victims */
41 VtBlock *block; /* all allocated blocks */
43 uchar *mem; /* memory for all blocks and data */
44 int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);
47 static void cachecheck(VtCache*);
50 vtcachealloc(VtConn *z, int blocksize, ulong nblock)
57 c = vtmallocz(sizeof(VtCache));
60 c->blocksize = (blocksize + 127) & ~127;
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);
70 for(i=0; i<nblock; i++){
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.
90 vtcachesetwrite(VtCache *c, int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int))
98 vtcachefree(VtCache *c)
105 for(i=0; i<c->nblock; i++)
106 assert(c->block[i].ref == 0);
116 vtcachedump(VtCache *c)
121 for(i=0; i<c->nblock; 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);
129 cachecheck(VtCache *c)
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");
144 if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
145 sysfatal("bad heap ordering");
147 if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
148 sysfatal("bad heap ordering");
152 for(i = 0; i < c->nblock; i++){
154 if(b->data != &c->mem[i * size])
155 sysfatal("mis-blocked at %d", i);
156 if(b->ref && b->heap == BadHeap)
158 else if(b->addr != NilBlock)
161 assert(c->nheap + refed == c->nblock);
163 for(i = 0; i < c->nblock; i++){
172 upheap(int i, VtBlock *b)
181 for(; i != 0; i = p){
184 if(b->used - now >= bb->used - now)
196 downheap(int i, VtBlock *b)
209 if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
212 if(b->used - now <= bb->used - now)
223 * Delete a block from the heap.
224 * Called with c->lk held.
241 b = c->heap[c->nheap];
248 * Insert a block into the heap.
249 * Called with c->lk held.
254 assert(b->heap == BadHeap);
255 upheap(b->c->nheap++, b);
259 * locate the vtBlock with the oldest second to last use.
260 * remove it from the heap, and fix up the heap.
262 /* called with c->lk held */
264 vtcachebumpblock(VtCache *c)
269 * locate the vtBlock with the oldest second to last use.
270 * remove it from the heap, and fix up the heap.
274 fprint(2, "vtcachebumpblock: no free blocks in vtCache");
280 assert(b->heap == BadHeap);
284 * unchain the vtBlock from hash chain if any
287 *(b->prev) = b->next;
289 b->next->prev = b->prev;
294 if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
295 /* set vtBlock to a reasonable state */
297 b->iostate = BioEmpty;
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.
307 vtcachelocal(VtCache *c, u32int addr, int type)
312 sysfatal("vtcachelocal: asked for nonexistent block 0");
314 sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",
317 b = &c->block[addr-1];
318 if(b->addr == NilBlock || b->iostate != BioLocal)
319 sysfatal("vtcachelocal: block is not local");
322 sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type);
330 b->pc = getcallerpc(&c);
335 vtcacheallocblock(VtCache *c, int type)
340 b = vtcachebumpblock(c);
341 b->iostate = BioLocal;
343 b->addr = (b - c->block)+1;
344 vtzeroextend(type, b->data, 0, c->blocksize);
345 vtlocaltoglobal(b->addr, b->score);
350 b->pc = getcallerpc(&c);
355 * fetch a global (Venti) block from the memory cache.
356 * if it's not there, load it, bumping some other block.
359 vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
367 fprint(2, "vtcacheglobal %V %d from %p\n", score, type, getcallerpc(&c));
368 addr = vtglobaltolocal(score);
369 if(addr != NilBlock){
371 fprint(2, "vtcacheglobal %V %d => local\n", score, type);
372 b = vtcachelocal(c, addr, type);
374 b->pc = getcallerpc(&c);
378 h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
381 * look for the block in the cache
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)
391 fprint(2, "vtcacheglobal %V %d => found in cache %p; locking\n", score, type, b);
394 if(b->iostate == BioVentiError){
396 fprint(2, "cached read error for %V\n", score);
398 fprint(2, "vtcacheglobal %V %d => cache read error\n", score, type);
400 werrstr("venti i/o error");
404 fprint(2, "vtcacheglobal %V %d => found in cache; returning\n", score, type);
405 b->pc = getcallerpc(&c);
412 b = vtcachebumpblock(c);
415 memmove(b->score, score, VtScoreSize);
416 /* chain onto correct hash */
417 b->next = c->hash[h];
420 b->next->prev = &b->next;
421 b->prev = &c->hash[h];
424 * Lock b before unlocking c, so that others wait while we read.
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.
432 fprint(2, "vtcacheglobal %V %d => bumped; locking %p\n", score, type, b);
438 n = vtread(c->z, score, type, b->data, c->blocksize);
441 fprint(2, "read %V: %r\n", score);
443 fprint(2, "vtcacheglobal %V %d => bumped; read error\n", score, type);
444 b->iostate = BioVentiError;
448 vtzeroextend(type, b->data, n, c->blocksize);
449 b->iostate = BioVenti;
452 fprint(2, "vtcacheglobal %V %d => loaded into cache; returning\n", score, type);
453 b->pc = getcallerpc(&b);
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.
464 vtblockduplock(VtBlock *b)
466 assert(b->nlock > 0);
471 * we're done with the block.
472 * unlock it. can't use it after calling this.
475 vtblockput(VtBlock* b)
482 if(0)fprint(2, "vtblockput: %d: %x %d %d\n", getpid(), b->addr, c->nheap, b->iostate);
484 fprint(2, "vtblockput %p from %p\n", b, getcallerpc(&b));
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.
496 assert(b->nlock == 0);
511 /*if(b->addr != NilBlock) print("blockput %d\n", b->addr); */
524 vtblockwrite(VtBlock *b)
526 uchar score[VtScoreSize];
531 if(b->iostate != BioLocal){
532 werrstr("vtblockwrite: not a local block");
537 n = vtzerotruncate(b->type, b->data, c->blocksize);
539 if(c->write(c->z, score, b->type, b->data, n) < 0)
542 memmove(b->score, score, VtScoreSize);
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];
551 b->next->prev = &b->next;
552 b->prev = &c->hash[h];
558 vtcacheblocksize(VtCache *c)
564 vtblockcopy(VtBlock *b)
569 bb = vtcacheallocblock(b->c, b->type);
574 memmove(bb->data, b->data, b->c->blocksize);
576 bb->pc = getcallerpc(&b);
581 vtlocaltoglobal(u32int addr, uchar score[VtScoreSize])
583 memset(score, 0, 16);
584 score[16] = addr>>24;
585 score[17] = addr>>16;
592 vtglobaltolocal(uchar score[VtScoreSize])
594 static uchar zero[16];
595 if(memcmp(score, zero, 16) != 0)
597 return (score[16]<<24)|(score[17]<<16)|(score[18]<<8)|score[19];