diff options
author | rsc <devnull@localhost> | 2003-11-23 18:19:58 +0000 |
---|---|---|
committer | rsc <devnull@localhost> | 2003-11-23 18:19:58 +0000 |
commit | 056fe1ba7fa0b70f871dfb9005b24eb8e4cc230b (patch) | |
tree | 9ad42f31c3bc124cf6617cf9eb41dd525eccce83 /src/libventi/cache.c | |
parent | 9df487d720a59bf8cb0dc4ccffc30ad8eb48256a (diff) | |
download | plan9port-056fe1ba7fa0b70f871dfb9005b24eb8e4cc230b.tar.gz plan9port-056fe1ba7fa0b70f871dfb9005b24eb8e4cc230b.tar.bz2 plan9port-056fe1ba7fa0b70f871dfb9005b24eb8e4cc230b.zip |
new venti library.
Diffstat (limited to 'src/libventi/cache.c')
-rw-r--r-- | src/libventi/cache.c | 560 |
1 files changed, 560 insertions, 0 deletions
diff --git a/src/libventi/cache.c b/src/libventi/cache.c new file mode 100644 index 00000000..ed8a7f2f --- /dev/null +++ b/src/libventi/cache.c @@ -0,0 +1,560 @@ +/* + * 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 nread, ncopy, nwrite; + +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 mode; +}; + +static void cachecheck(VtCache*); + +VtCache* +vtcachealloc(VtConn *z, int blocksize, ulong nblock, int mode) +{ + 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->mode = mode; + + 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; +} + +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++; + } +if(c->nheap + refed != c->nblock){ +fprint(2, "cachecheck: nheap %d refed %d nblocks %d\n", c->nheap, refed, c->nblock); +//vtcachedump(c); +} + assert(c->nheap + refed == c->nblock); + refed = 0; + for(i = 0; i < c->nblock; i++){ + b = &c->block[i]; + if(b->ref){ +if(1)fprint(2, "a=%ud %V ref=%d\n", b->addr, b->score, b->ref); + refed++; + } + } +if(refed > 0)fprint(2, "cachecheck: in used %d\n", 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); +abort(); + sysfatal("vtcachebumpblock: no free blocks in vtCache"); + } + 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 >= c->nblock) + sysfatal("vtcachelocal: asked for block #%ud; only %d blocks\n", + addr, c->nblock); + + b = &c->block[addr]; + if(b->addr == NilBlock || b->iostate != BioLocal) +{ +abort(); + sysfatal("vtcachelocal: block is not local"); +} + + if(b->type != type) +{ +print("%d != %d\n", b->type, type); +abort(); + 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; + return b; +} + +VtBlock* +vtcacheallocblock(VtCache *c, int type) +{ + VtBlock *b; + +if(type >= VtMaxType) + abort(); + + qlock(&c->lk); + b = vtcachebumpblock(c); + b->iostate = BioLocal; + b->type = type; + b->addr = b - c->block; + vtzeroextend(type, b->data, 0, c->blocksize); + vtlocaltoglobal(b->addr, b->score); + qunlock(&c->lk); + + qlock(&b->lk); + b->nlock = 1; + + 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; + + addr = vtglobaltolocal(score); + if(addr != NilBlock) + return vtcachelocal(c, addr, type); + + 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); + qlock(&b->lk); + b->nlock = 1; + 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. + */ + qlock(&b->lk); + b->nlock = 1; + qunlock(&c->lk); + + n = vtread(c->z, score, type, b->data, c->blocksize); + if(n < 0){ +fprint(2, "vtread: %r\n"); + b->iostate = BioVentiError; + vtblockput(b); + return nil; + } + vtzeroextend(type, b->data, n, c->blocksize); + b->iostate = BioVenti; + b->nlock = 1; + b->decrypted = 0; + 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(--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++; + 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){ + abort(); + sysfatal("vtBlockWrite: not a local block"); + } + + c = b->c; + n = vtzerotruncate(b->type, b->data, c->blocksize); + if(vtwrite(c->z, score, b->type, b->data, n) < 0) + return -1; + + memmove(b->score, score, VtScoreSize); + + qlock(&c->lk); + 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; + +ncopy++; + bb = vtcacheallocblock(b->c, b->type); + if(bb == nil){ + vtblockput(b); + return nil; + } + memmove(bb->data, b->data, b->c->blocksize); + vtblockput(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]; +} |