#include "stdinc.h"#include "vac.h"#include "dat.h"#include "fns.h" typedef struct Label Label; enum { BadHeap = ~0,}; /* * the plan is to store data to the cache in c->size blocks * with the block zero extended to fill it out. When writing to * venti, the block will be zero truncated. The walker will also check * that the block fits within psize or dsize as the case may be. */ /* * the tag for a block is hash(index, parent tag) */ struct Cache{ VtLock *lk; VtSession *z; u32int now; /* ticks for usage timestamps */ int size; /* max. size of any block; allocated to each block */ Lump **heads; /* hash table for finding address */ int nheap; /* number of available victims */ Lump **heap; /* heap for locating victims */ long nblocks; /* number of blocks allocated */ Lump *blocks; /* array of block descriptors */ u8int *mem; /* memory for all block descriptors */ Lump *free; /* free list of lumps */ long hashSize;}; struct Label { uchar gen[4]; uchar state; uchar type; /* top bit indicates it is part of a directory */ uchar tag[4]; /* tag of file it is in */}; static char ENoDir[] = "directory entry is not allocated"; static void fixHeap(int si, Lump *b);static int upHeap(int i, Lump *b);static int downHeap(int i, Lump *b);static char *lumpState(int);static void lumpSetState(Lump *u, int state); Cache *cacheAlloc(VtSession *z, int blockSize, long nblocks){ int i; Cache *c; Lump *b; c = vtMemAllocZ(sizeof(Cache)); c->lk = vtLockAlloc(); c->z = z; c->size = blockSize; c->nblocks = nblocks; c->hashSize = nblocks; c->heads = vtMemAllocZ(c->hashSize*sizeof(Lump*)); c->heap = vtMemAllocZ(nblocks*sizeof(Lump*)); c->blocks = vtMemAllocZ(nblocks*sizeof(Lump)); c->mem = vtMemAllocZ(nblocks * blockSize); for(i = 0; i < nblocks; i++){ b = &c->blocks[i]; b->lk = vtLockAlloc(); b->c = c; b->data = &c->mem[i * blockSize]; b->addr = i+1; b->state = LumpFree; b->heap = BadHeap; b->next = c->free; c->free = b; } c->nheap = 0; return c;} longcacheGetSize(Cache *c){ return c->nblocks;} intcacheGetBlockSize(Cache *c){ return c->size;} intcacheSetSize(Cache *c, long nblocks){ USED(c); USED(nblocks); return 0;} voidcacheFree(Cache *c){ int i; for(i = 0; i < c->nblocks; i++){ assert(c->blocks[i].ref == 0); vtLockFree(c->blocks[i].lk); } vtMemFree(c->heads); vtMemFree(c->blocks); vtMemFree(c->mem); vtMemFree(c);} static u32inthash(Cache *c, uchar score[VtScoreSize], int type){ u32int h; uchar *p = score + VtScoreSize-4; h = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]; h += type; return h % c->hashSize;} static voidfindLump(Cache *c, Lump *bb){ Lump *b, *last; int h; last = nil; h = hash(c, bb->score, bb->type); for(b = c->heads[h]; b != nil; b = b->next){ if(last != b->prev) vtFatal("bad prev link"); if(b == bb) return; last = b; } vtFatal("block missing from hash table");} voidcacheCheck(Cache *c){ u32int size, now; int i, k, refed, free; static uchar zero[VtScoreSize]; Lump *p; size = c->size; now = c->now; free = 0; for(p=c->free; p; p=p->next) free++; for(i = 0; i < c->nheap; i++){ if(c->heap[i]->heap != i) vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap); if(i > 0 && c->heap[(i - 1) >> 1]->used2 - now > c->heap[i]->used2 - now) vtFatal("bad heap ordering"); k = (i << 1) + 1; if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now) vtFatal("bad heap ordering"); k++; if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now) vtFatal("bad heap ordering"); } refed = 0; for(i = 0; i < c->nblocks; i++){ if(c->blocks[i].data != &c->mem[i * size]) vtFatal("mis-blocked at %d", i); if(c->blocks[i].ref && c->blocks[i].heap == BadHeap){ refed++; } if(memcmp(zero, c->blocks[i].score, VtScoreSize)) findLump(c, &c->blocks[i]); }if(refed > 0)fprint(2, "cacheCheck: nheap %d refed %d free %d\n", c->nheap, refed, free); assert(c->nheap + refed + free == c->nblocks); refed = 0; for(i = 0; i < c->nblocks; i++){ if(c->blocks[i].ref) {if(1)fprint(2, "%d %V %d %s\n", c->blocks[i].type, c->blocks[i].score, c->blocks[i].ref, lumpState(c->blocks[i].state)); refed++; } }if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);} /* * delete an arbitrary block from the heap */static voiddelHeap(Lump *db){ fixHeap(db->heap, db->c->heap[--db->c->nheap]); db->heap = BadHeap;} static voidfixHeap(int si, Lump *b){ int i; i = upHeap(si, b); if(i == si) downHeap(i, b);} static intupHeap(int i, Lump *b){ Lump *bb; u32int now; int p; Cache *c; c = b->c; now = c->now; for(; i != 0; i = p){ p = (i - 1) >> 1; bb = c->heap[p]; if(b->used2 - now >= bb->used2 - now) break; c->heap[i] = bb; bb->heap = i; } c->heap[i] = b; b->heap = i; return i;} static intdownHeap(int i, Lump *b){ Lump *bb; u32int now; int k; Cache *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]->used2 - now > c->heap[k + 1]->used2 - now) k++; bb = c->heap[k]; if(b->used2 - now <= bb->used2 - now) break; c->heap[i] = bb; bb->heap = i; } c->heap[i] = b; b->heap = i; return i;} /* called with c->lk held */Lump *cacheBumpLump(Cache *c){ Lump *b; /* * missed: locate the block with the oldest second to last use. * remove it from the heap, and fix up the heap. */ if(c->free) { b = c->free; c->free = b->next; } else { for(;;){ if(c->nheap == 0) { cacheCheck(c); assert(0); return nil; } b = c->heap[0]; delHeap(b); if(b->ref == 0) break; } /* * unchain the block from hash chain */ if(b->prev == nil) c->heads[hash(c, b->score, b->type)] = b->next; else b->prev->next = b->next; if(b->next != nil) b->next->prev = b->prev; } /* * the new block has no last use, so assume it happens sometime in the middle */ b->used = (b->used2 + c->now) / 2; b->size = 0; return b;} Lump *cacheAllocLump(Cache *c, int type, int size, int dir){ Lump *b; ulong h; assert(size <= c->size); again: vtLock(c->lk); b = cacheBumpLump(c); if(b == nil) { vtUnlock(c->lk); sleep(100); goto again; } vtLock(b->lk); assert(b->ref == 0); b->ref++; b->used2 = b->used; b->used = c->now++; /* convert addr into score */ memset(b->score, 0, VtScoreSize-4); b->score[VtScoreSize-4] = b->addr>>24; b->score[VtScoreSize-3] = b->addr>>16; b->score[VtScoreSize-2] = b->addr>>8; b->score[VtScoreSize-1] = b->addr; b->dir = dir; b->type = type; b->gen = 0; b->size = size; b->state = LumpFree; h = hash(c, b->score, b->type); /* chain onto correct hash */ b->next = c->heads[h]; c->heads[h] = b; if(b->next != nil) b->next->prev = b; b->prev = nil; vtUnlock(c->lk); vtZeroExtend(type, b->data, 0, size); lumpSetState(b, LumpActive); return b;} intscoreIsLocal(uchar score[VtScoreSize]){ static uchar zero[VtScoreSize]; return memcmp(score, zero, VtScoreSize-4) == 0;} Lump *cacheGetLump(Cache *c, uchar score[VtScoreSize], int type, int size){ Lump *b; ulong h; int n; static uchar zero[VtScoreSize]; assert(size <= c->size); h = hash(c, score, type); again: /* * look for the block in the cache */ vtLock(c->lk); for(b = c->heads[h]; b != nil; b = b->next){ if(memcmp(b->score, score, VtScoreSize) == 0 && b->type == type) goto found; } /* should not be looking for a temp block */ if(scoreIsLocal(score)) { if(memcmp(score, zero, VtScoreSize) == 0) vtSetError("looking for zero score"); else vtSetError("missing local block"); vtUnlock(c->lk); return nil; } b = cacheBumpLump(c); if(b == nil) { vtUnlock(c->lk); sleep(100); goto again; } /* chain onto correct hash */ b->next = c->heads[h]; c->heads[h] = b; if(b->next != nil) b->next->prev = b; b->prev = nil; memmove(b->score, score, VtScoreSize); b->type = type; b->state = LumpFree; found: b->ref++; b->used2 = b->used; b->used = c->now++; if(b->heap != BadHeap) fixHeap(b->heap, b); vtUnlock(c->lk); vtLock(b->lk); if(b->state != LumpFree) return b; n = vtRead(c->z, score, type, b->data, size); if(n < 0) {fprint(2, "vtRead failed: %V %d %d: %R\n", score, type, size); lumpDecRef(b, 1); return nil; } if(!vtSha1Check(score, b->data, n)) { vtSetError("vtSha1Check failed"); lumpDecRef(b, 1); return nil; } b->size = n; lumpSetState(b, LumpVenti); return b;} static char *lumpState(int state){ switch(state) { default: return "Unknown!!"; case LumpFree: return "Free"; case LumpActive: return "Active"; case LumpSnap: return "Snap"; case LumpZombie: return "Zombie"; case LumpVenti: return "Venti"; }} static voidlumpSetState(Lump *u, int state){// if(u->state != LumpFree)// fprint(2, "%V: %s -> %s\n", u->score, lumpState(u->state), lumpState(state)); u->state = state;} intlumpGetScore(Lump *u, int offset, uchar score[VtScoreSize]){ uchar *sp; VtRootLump *root; VtDirEntry2 *dir; vtLock(u->lk); Lines 1–500 of 868. Load more
#include "stdinc.h" #include "vac.h" #include "dat.h" #include "fns.h" typedef struct Label Label; enum { BadHeap = ~0, }; /* * the plan is to store data to the cache in c->size blocks * with the block zero extended to fill it out. When writing to * venti, the block will be zero truncated. The walker will also check * that the block fits within psize or dsize as the case may be. */ /* * the tag for a block is hash(index, parent tag) */ struct Cache { VtLock *lk; VtSession *z; u32int now; /* ticks for usage timestamps */ int size; /* max. size of any block; allocated to each block */ Lump **heads; /* hash table for finding address */ int nheap; /* number of available victims */ Lump **heap; /* heap for locating victims */ long nblocks; /* number of blocks allocated */ Lump *blocks; /* array of block descriptors */ u8int *mem; /* memory for all block descriptors */ Lump *free; /* free list of lumps */ long hashSize; }; struct Label { uchar gen[4]; uchar state; uchar type; /* top bit indicates it is part of a directory */ uchar tag[4]; /* tag of file it is in */ }; static char ENoDir[] = "directory entry is not allocated"; static void fixHeap(int si, Lump *b); static int upHeap(int i, Lump *b); static int downHeap(int i, Lump *b); static char *lumpState(int); static void lumpSetState(Lump *u, int state); Cache * cacheAlloc(VtSession *z, int blockSize, long nblocks) { int i; Cache *c; Lump *b; c = vtMemAllocZ(sizeof(Cache)); c->lk = vtLockAlloc(); c->z = z; c->size = blockSize; c->nblocks = nblocks; c->hashSize = nblocks; c->heads = vtMemAllocZ(c->hashSize*sizeof(Lump*)); c->heap = vtMemAllocZ(nblocks*sizeof(Lump*)); c->blocks = vtMemAllocZ(nblocks*sizeof(Lump)); c->mem = vtMemAllocZ(nblocks * blockSize); for(i = 0; i < nblocks; i++){ b = &c->blocks[i]; b->lk = vtLockAlloc(); b->c = c; b->data = &c->mem[i * blockSize]; b->addr = i+1; b->state = LumpFree; b->heap = BadHeap; b->next = c->free; c->free = b; } c->nheap = 0; return c; } long cacheGetSize(Cache *c) { return c->nblocks; } int cacheGetBlockSize(Cache *c) { return c->size; } int cacheSetSize(Cache *c, long nblocks) { USED(c); USED(nblocks); return 0; } void cacheFree(Cache *c) { int i; for(i = 0; i < c->nblocks; i++){ assert(c->blocks[i].ref == 0); vtLockFree(c->blocks[i].lk); } vtMemFree(c->heads); vtMemFree(c->blocks); vtMemFree(c->mem); vtMemFree(c); } static u32int hash(Cache *c, uchar score[VtScoreSize], int type) { u32int h; uchar *p = score + VtScoreSize-4; h = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]; h += type; return h % c->hashSize; } static void findLump(Cache *c, Lump *bb) { Lump *b, *last; int h; last = nil; h = hash(c, bb->score, bb->type); for(b = c->heads[h]; b != nil; b = b->next){ if(last != b->prev) vtFatal("bad prev link"); if(b == bb) return; last = b; } vtFatal("block missing from hash table"); } void cacheCheck(Cache *c) { u32int size, now; int i, k, refed, free; static uchar zero[VtScoreSize]; Lump *p; size = c->size; now = c->now; free = 0; for(p=c->free; p; p=p->next) free++; for(i = 0; i < c->nheap; i++){ if(c->heap[i]->heap != i) vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap); if(i > 0 && c->heap[(i - 1) >> 1]->used2 - now > c->heap[i]->used2 - now) vtFatal("bad heap ordering"); k = (i << 1) + 1; if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now) vtFatal("bad heap ordering"); k++; if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now) vtFatal("bad heap ordering"); } refed = 0; for(i = 0; i < c->nblocks; i++){ if(c->blocks[i].data != &c->mem[i * size]) vtFatal("mis-blocked at %d", i); if(c->blocks[i].ref && c->blocks[i].heap == BadHeap){ refed++; } if(memcmp(zero, c->blocks[i].score, VtScoreSize)) findLump(c, &c->blocks[i]); } if(refed > 0)fprint(2, "cacheCheck: nheap %d refed %d free %d\n", c->nheap, refed, free); assert(c->nheap + refed + free == c->nblocks); refed = 0; for(i = 0; i < c->nblocks; i++){ if(c->blocks[i].ref) { if(1)fprint(2, "%d %V %d %s\n", c->blocks[i].type, c->blocks[i].score, c->blocks[i].ref, lumpState(c->blocks[i].state)); refed++; } } if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed); } /* * delete an arbitrary block from the heap */ static void delHeap(Lump *db) { fixHeap(db->heap, db->c->heap[--db->c->nheap]); db->heap = BadHeap; } static void fixHeap(int si, Lump *b) { int i; i = upHeap(si, b); if(i == si) downHeap(i, b); } static int upHeap(int i, Lump *b) { Lump *bb; u32int now; int p; Cache *c; c = b->c; now = c->now; for(; i != 0; i = p){ p = (i - 1) >> 1; bb = c->heap[p]; if(b->used2 - now >= bb->used2 - now) break; c->heap[i] = bb; bb->heap = i; } c->heap[i] = b; b->heap = i; return i; } static int downHeap(int i, Lump *b) { Lump *bb; u32int now; int k; Cache *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]->used2 - now > c->heap[k + 1]->used2 - now) k++; bb = c->heap[k]; if(b->used2 - now <= bb->used2 - now) break; c->heap[i] = bb; bb->heap = i; } c->heap[i] = b; b->heap = i; return i; } /* called with c->lk held */ Lump * cacheBumpLump(Cache *c) { Lump *b; /* * missed: locate the block with the oldest second to last use. * remove it from the heap, and fix up the heap. */ if(c->free) { b = c->free; c->free = b->next; } else { for(;;){ if(c->nheap == 0) { cacheCheck(c); assert(0); return nil; } b = c->heap[0]; delHeap(b); if(b->ref == 0) break; } /* * unchain the block from hash chain */ if(b->prev == nil) c->heads[hash(c, b->score, b->type)] = b->next; else b->prev->next = b->next; if(b->next != nil) b->next->prev = b->prev; } /* * the new block has no last use, so assume it happens sometime in the middle */ b->used = (b->used2 + c->now) / 2; b->size = 0; return b; } Lump * cacheAllocLump(Cache *c, int type, int size, int dir) { Lump *b; ulong h; assert(size <= c->size); again: vtLock(c->lk); b = cacheBumpLump(c); if(b == nil) { vtUnlock(c->lk); sleep(100); goto again; } vtLock(b->lk); assert(b->ref == 0); b->ref++; b->used2 = b->used; b->used = c->now++; /* convert addr into score */ memset(b->score, 0, VtScoreSize-4); b->score[VtScoreSize-4] = b->addr>>24; b->score[VtScoreSize-3] = b->addr>>16; b->score[VtScoreSize-2] = b->addr>>8; b->score[VtScoreSize-1] = b->addr; b->dir = dir; b->type = type; b->gen = 0; b->size = size; b->state = LumpFree; h = hash(c, b->score, b->type); /* chain onto correct hash */ b->next = c->heads[h]; c->heads[h] = b; if(b->next != nil) b->next->prev = b; b->prev = nil; vtUnlock(c->lk); vtZeroExtend(type, b->data, 0, size); lumpSetState(b, LumpActive); return b; } int scoreIsLocal(uchar score[VtScoreSize]) { static uchar zero[VtScoreSize]; return memcmp(score, zero, VtScoreSize-4) == 0; } Lump * cacheGetLump(Cache *c, uchar score[VtScoreSize], int type, int size) { Lump *b; ulong h; int n; static uchar zero[VtScoreSize]; assert(size <= c->size); h = hash(c, score, type); again: /* * look for the block in the cache */ vtLock(c->lk); for(b = c->heads[h]; b != nil; b = b->next){ if(memcmp(b->score, score, VtScoreSize) == 0 && b->type == type) goto found; } /* should not be looking for a temp block */ if(scoreIsLocal(score)) { if(memcmp(score, zero, VtScoreSize) == 0) vtSetError("looking for zero score"); else vtSetError("missing local block"); vtUnlock(c->lk); return nil; } b = cacheBumpLump(c); if(b == nil) { vtUnlock(c->lk); sleep(100); goto again; } /* chain onto correct hash */ b->next = c->heads[h]; c->heads[h] = b; if(b->next != nil) b->next->prev = b; b->prev = nil; memmove(b->score, score, VtScoreSize); b->type = type; b->state = LumpFree; found: b->ref++; b->used2 = b->used; b->used = c->now++; if(b->heap != BadHeap) fixHeap(b->heap, b); vtUnlock(c->lk); vtLock(b->lk); if(b->state != LumpFree) return b; n = vtRead(c->z, score, type, b->data, size); if(n < 0) { fprint(2, "vtRead failed: %V %d %d: %R\n", score, type, size); lumpDecRef(b, 1); return nil; } if(!vtSha1Check(score, b->data, n)) { vtSetError("vtSha1Check failed"); lumpDecRef(b, 1); return nil; } b->size = n; lumpSetState(b, LumpVenti); return b; } static char * lumpState(int state) { switch(state) { default: return "Unknown!!"; case LumpFree: return "Free"; case LumpActive: return "Active"; case LumpSnap: return "Snap"; case LumpZombie: return "Zombie"; case LumpVenti: return "Venti"; } } static void lumpSetState(Lump *u, int state) { // if(u->state != LumpFree) // fprint(2, "%V: %s -> %s\n", u->score, lumpState(u->state), lumpState(state)); u->state = state; } int lumpGetScore(Lump *u, int offset, uchar score[VtScoreSize]) { uchar *sp; VtRootLump *root; VtDirEntry2 *dir; vtLock(u->lk);