123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599 |
- /*
- * Memory-only VtBlock cache.
- *
- * The cached Venti blocks are in the hash chains.
- * The cached local blocks are only in the blocks array.
- * The free blocks are in the heap, which is supposed to
- * be indexed by second-to-last use but actually
- * appears to be last use.
- */
- #include <u.h>
- #include <libc.h>
- #include <venti.h>
- int vtcachenread;
- int vtcachencopy;
- int vtcachenwrite;
- int vttracelevel;
- enum {
- BioLocal = 1,
- BioVenti,
- BioReading,
- BioWriting,
- BioEmpty,
- BioVentiError
- };
- enum {
- BadHeap = ~0
- };
- struct VtCache
- {
- QLock lk;
- VtConn *z;
- u32int blocksize;
- u32int now; /* ticks for usage time stamps */
- VtBlock **hash; /* hash table for finding addresses */
- int nhash;
- VtBlock **heap; /* heap for finding victims */
- int nheap;
- VtBlock *block; /* all allocated blocks */
- int nblock;
- uchar *mem; /* memory for all blocks and data */
- int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);
- };
- static void cachecheck(VtCache*);
- VtCache*
- vtcachealloc(VtConn *z, int blocksize, ulong nblock)
- {
- uchar *p;
- VtCache *c;
- int i;
- VtBlock *b;
- c = vtmallocz(sizeof(VtCache));
- c->z = z;
- c->blocksize = (blocksize + 127) & ~127;
- c->nblock = nblock;
- c->nhash = nblock;
- c->hash = vtmallocz(nblock*sizeof(VtBlock*));
- c->heap = vtmallocz(nblock*sizeof(VtBlock*));
- c->block = vtmallocz(nblock*sizeof(VtBlock));
- c->mem = vtmallocz(nblock*c->blocksize);
- c->write = vtwrite;
- p = c->mem;
- for(i=0; i<nblock; i++){
- b = &c->block[i];
- b->addr = NilBlock;
- b->c = c;
- b->data = p;
- b->heap = i;
- c->heap[i] = b;
- p += c->blocksize;
- }
- c->nheap = nblock;
- cachecheck(c);
- return c;
- }
- /*
- * BUG This is here so that vbackup can override it and do some
- * pipelining of writes. Arguably vtwrite or vtwritepacket or the
- * cache itself should be providing this functionality.
- */
- void
- vtcachesetwrite(VtCache *c, int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int))
- {
- if(write == nil)
- write = vtwrite;
- c->write = write;
- }
- void
- vtcachefree(VtCache *c)
- {
- int i;
- qlock(&c->lk);
- cachecheck(c);
- for(i=0; i<c->nblock; i++)
- assert(c->block[i].ref == 0);
- vtfree(c->hash);
- vtfree(c->heap);
- vtfree(c->block);
- vtfree(c->mem);
- vtfree(c);
- }
- static void
- vtcachedump(VtCache *c)
- {
- int i;
- VtBlock *b;
- for(i=0; i<c->nblock; i++){
- b = &c->block[i];
- print("cache block %d: type %d score %V iostate %d addr %d ref %d nlock %d\n",
- i, b->type, b->score, b->iostate, b->addr, b->ref, b->nlock);
- }
- }
- static void
- cachecheck(VtCache *c)
- {
- u32int size, now;
- int i, k, refed;
- VtBlock *b;
- size = c->blocksize;
- now = c->now;
- for(i = 0; i < c->nheap; i++){
- if(c->heap[i]->heap != i)
- sysfatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
- if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
- sysfatal("bad heap ordering");
- k = (i << 1) + 1;
- if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
- sysfatal("bad heap ordering");
- k++;
- if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
- sysfatal("bad heap ordering");
- }
- refed = 0;
- for(i = 0; i < c->nblock; i++){
- b = &c->block[i];
- if(b->data != &c->mem[i * size])
- sysfatal("mis-blocked at %d", i);
- if(b->ref && b->heap == BadHeap)
- refed++;
- else if(b->addr != NilBlock)
- refed++;
- }
- assert(c->nheap + refed == c->nblock);
- refed = 0;
- for(i = 0; i < c->nblock; i++){
- b = &c->block[i];
- if(b->ref){
- refed++;
- }
- }
- }
- static int
- upheap(int i, VtBlock *b)
- {
- VtBlock *bb;
- u32int now;
- int p;
- VtCache *c;
-
- c = b->c;
- now = c->now;
- for(; i != 0; i = p){
- p = (i - 1) >> 1;
- bb = c->heap[p];
- if(b->used - now >= bb->used - now)
- break;
- c->heap[i] = bb;
- bb->heap = i;
- }
- c->heap[i] = b;
- b->heap = i;
- return i;
- }
- static int
- downheap(int i, VtBlock *b)
- {
- VtBlock *bb;
- u32int now;
- int k;
- VtCache *c;
-
- c = b->c;
- now = c->now;
- for(; ; i = k){
- k = (i << 1) + 1;
- if(k >= c->nheap)
- break;
- if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
- k++;
- bb = c->heap[k];
- if(b->used - now <= bb->used - now)
- break;
- c->heap[i] = bb;
- bb->heap = i;
- }
- c->heap[i] = b;
- b->heap = i;
- return i;
- }
- /*
- * Delete a block from the heap.
- * Called with c->lk held.
- */
- static void
- heapdel(VtBlock *b)
- {
- int i, si;
- VtCache *c;
- c = b->c;
- si = b->heap;
- if(si == BadHeap)
- return;
- b->heap = BadHeap;
- c->nheap--;
- if(si == c->nheap)
- return;
- b = c->heap[c->nheap];
- i = upheap(si, b);
- if(i == si)
- downheap(i, b);
- }
- /*
- * Insert a block into the heap.
- * Called with c->lk held.
- */
- static void
- heapins(VtBlock *b)
- {
- assert(b->heap == BadHeap);
- upheap(b->c->nheap++, b);
- }
- /*
- * locate the vtBlock with the oldest second to last use.
- * remove it from the heap, and fix up the heap.
- */
- /* called with c->lk held */
- static VtBlock*
- vtcachebumpblock(VtCache *c)
- {
- VtBlock *b;
- /*
- * locate the vtBlock with the oldest second to last use.
- * remove it from the heap, and fix up the heap.
- */
- if(c->nheap == 0){
- vtcachedump(c);
- fprint(2, "vtcachebumpblock: no free blocks in vtCache");
- abort();
- }
- b = c->heap[0];
- heapdel(b);
- assert(b->heap == BadHeap);
- assert(b->ref == 0);
- /*
- * unchain the vtBlock from hash chain if any
- */
- if(b->prev){
- *(b->prev) = b->next;
- if(b->next)
- b->next->prev = b->prev;
- b->prev = nil;
- }
-
- if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
- /* set vtBlock to a reasonable state */
- b->ref = 1;
- b->iostate = BioEmpty;
- return b;
- }
- /*
- * fetch a local block from the memory cache.
- * if it's not there, load it, bumping some other Block.
- * if we're out of free blocks, we're screwed.
- */
- VtBlock*
- vtcachelocal(VtCache *c, u32int addr, int type)
- {
- VtBlock *b;
- if(addr == 0)
- sysfatal("vtcachelocal: asked for nonexistent block 0");
- if(addr > c->nblock)
- sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",
- addr, c->nblock);
- b = &c->block[addr-1];
- if(b->addr == NilBlock || b->iostate != BioLocal)
- sysfatal("vtcachelocal: block is not local");
- if(b->type != type)
- sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type);
- qlock(&c->lk);
- b->ref++;
- qunlock(&c->lk);
- qlock(&b->lk);
- b->nlock = 1;
- b->pc = getcallerpc(&c);
- return b;
- }
- VtBlock*
- vtcacheallocblock(VtCache *c, int type)
- {
- VtBlock *b;
- qlock(&c->lk);
- b = vtcachebumpblock(c);
- b->iostate = BioLocal;
- b->type = type;
- b->addr = (b - c->block)+1;
- vtzeroextend(type, b->data, 0, c->blocksize);
- vtlocaltoglobal(b->addr, b->score);
- qunlock(&c->lk);
- qlock(&b->lk);
- b->nlock = 1;
- b->pc = getcallerpc(&c);
- return b;
- }
- /*
- * fetch a global (Venti) block from the memory cache.
- * if it's not there, load it, bumping some other block.
- */
- VtBlock*
- vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
- {
- VtBlock *b;
- ulong h;
- int n;
- u32int addr;
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d from %p\n", score, type, getcallerpc(&c));
- addr = vtglobaltolocal(score);
- if(addr != NilBlock){
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => local\n", score, type);
- b = vtcachelocal(c, addr, type);
- if(b)
- b->pc = getcallerpc(&c);
- return b;
- }
- h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
- /*
- * look for the block in the cache
- */
- qlock(&c->lk);
- for(b = c->hash[h]; b != nil; b = b->next){
- if(b->addr != NilBlock || memcmp(b->score, score, VtScoreSize) != 0 || b->type != type)
- continue;
- heapdel(b);
- b->ref++;
- qunlock(&c->lk);
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => found in cache %p; locking\n", score, type, b);
- qlock(&b->lk);
- b->nlock = 1;
- if(b->iostate == BioVentiError){
- if(chattyventi)
- fprint(2, "cached read error for %V\n", score);
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => cache read error\n", score, type);
- vtblockput(b);
- werrstr("venti i/o error");
- return nil;
- }
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => found in cache; returning\n", score, type);
- b->pc = getcallerpc(&c);
- return b;
- }
- /*
- * not found
- */
- b = vtcachebumpblock(c);
- b->addr = NilBlock;
- b->type = type;
- memmove(b->score, score, VtScoreSize);
- /* chain onto correct hash */
- b->next = c->hash[h];
- c->hash[h] = b;
- if(b->next != nil)
- b->next->prev = &b->next;
- b->prev = &c->hash[h];
- /*
- * Lock b before unlocking c, so that others wait while we read.
- *
- * You might think there is a race between this qlock(b) before qunlock(c)
- * and the qlock(c) while holding a qlock(b) in vtblockwrite. However,
- * the block here can never be the block in a vtblockwrite, so we're safe.
- * We're certainly living on the edge.
- */
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => bumped; locking %p\n", score, type, b);
- qlock(&b->lk);
- b->nlock = 1;
- qunlock(&c->lk);
- vtcachenread++;
- n = vtread(c->z, score, type, b->data, c->blocksize);
- if(n < 0){
- if(chattyventi)
- fprint(2, "read %V: %r\n", score);
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => bumped; read error\n", score, type);
- b->iostate = BioVentiError;
- vtblockput(b);
- return nil;
- }
- vtzeroextend(type, b->data, n, c->blocksize);
- b->iostate = BioVenti;
- b->nlock = 1;
- if(vttracelevel)
- fprint(2, "vtcacheglobal %V %d => loaded into cache; returning\n", score, type);
- b->pc = getcallerpc(&b);
- return b;
- }
- /*
- * The thread that has locked b may refer to it by
- * multiple names. Nlock counts the number of
- * references the locking thread holds. It will call
- * vtblockput once per reference.
- */
- void
- vtblockduplock(VtBlock *b)
- {
- assert(b->nlock > 0);
- b->nlock++;
- }
- /*
- * we're done with the block.
- * unlock it. can't use it after calling this.
- */
- void
- vtblockput(VtBlock* b)
- {
- VtCache *c;
- if(b == nil)
- return;
- if(0)fprint(2, "vtblockput: %d: %x %d %d\n", getpid(), b->addr, c->nheap, b->iostate);
- if(vttracelevel)
- fprint(2, "vtblockput %p from %p\n", b, getcallerpc(&b));
- if(--b->nlock > 0)
- return;
- /*
- * b->nlock should probably stay at zero while
- * the vtBlock is unlocked, but diskThread and vtSleep
- * conspire to assume that they can just qlock(&b->lk); vtblockput(b),
- * so we have to keep b->nlock set to 1 even
- * when the vtBlock is unlocked.
- */
- assert(b->nlock == 0);
- b->nlock = 1;
- qunlock(&b->lk);
- c = b->c;
- qlock(&c->lk);
- if(--b->ref > 0){
- qunlock(&c->lk);
- return;
- }
- assert(b->ref == 0);
- switch(b->iostate){
- case BioVenti:
- /*if(b->addr != NilBlock) print("blockput %d\n", b->addr); */
- b->used = c->now++;
- /* fall through */
- case BioVentiError:
- heapins(b);
- break;
- case BioLocal:
- break;
- }
- qunlock(&c->lk);
- }
- int
- vtblockwrite(VtBlock *b)
- {
- uchar score[VtScoreSize];
- VtCache *c;
- uint h;
- int n;
- if(b->iostate != BioLocal){
- werrstr("vtblockwrite: not a local block");
- return -1;
- }
- c = b->c;
- n = vtzerotruncate(b->type, b->data, c->blocksize);
- vtcachenwrite++;
- if(c->write(c->z, score, b->type, b->data, n) < 0)
- return -1;
- memmove(b->score, score, VtScoreSize);
- qlock(&c->lk);
- b->addr = NilBlock; /* now on venti */
- b->iostate = BioVenti;
- h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
- b->next = c->hash[h];
- c->hash[h] = b;
- if(b->next != nil)
- b->next->prev = &b->next;
- b->prev = &c->hash[h];
- qunlock(&c->lk);
- return 0;
- }
- uint
- vtcacheblocksize(VtCache *c)
- {
- return c->blocksize;
- }
- VtBlock*
- vtblockcopy(VtBlock *b)
- {
- VtBlock *bb;
- vtcachencopy++;
- bb = vtcacheallocblock(b->c, b->type);
- if(bb == nil){
- vtblockput(b);
- return nil;
- }
- memmove(bb->data, b->data, b->c->blocksize);
- vtblockput(b);
- bb->pc = getcallerpc(&b);
- return bb;
- }
- void
- vtlocaltoglobal(u32int addr, uchar score[VtScoreSize])
- {
- memset(score, 0, 16);
- score[16] = addr>>24;
- score[17] = addr>>16;
- score[18] = addr>>8;
- score[19] = addr;
- }
- u32int
- vtglobaltolocal(uchar score[VtScoreSize])
- {
- static uchar zero[16];
- if(memcmp(score, zero, 16) != 0)
- return NilBlock;
- return (score[16]<<24)|(score[17]<<16)|(score[18]<<8)|score[19];
- }
|