ref: 17ebe55031ae6945ad1f671b69267a672328e4b1
dir: /sys/src/cmd/venti/srv/lumpcache.c/
#include "stdinc.h" #include "dat.h" #include "fns.h" /* #define CHECK(x) x */ #define CHECK(x) typedef struct LumpCache LumpCache; enum { HashLog = 9, HashSize = 1<<HashLog, HashMask = HashSize - 1, }; struct LumpCache { QLock lock; Rendez full; Lump *free; /* list of available lumps */ u32int allowed; /* total allowable space for packets */ u32int avail; /* remaining space for packets */ u32int now; /* ticks for usage timestamps */ Lump **heads; /* hash table for finding address */ int nheap; /* number of available victims */ Lump **heap; /* heap for locating victims */ int nblocks; /* number of blocks allocated */ Lump *blocks; /* array of block descriptors */ }; static LumpCache lumpcache; static void delheap(Lump *db); static int downheap(int i, Lump *b); static void fixheap(int i, Lump *b); static int upheap(int i, Lump *b); static Lump *bumplump(void); void initlumpcache(u32int size, u32int nblocks) { Lump *last, *b; int i; lumpcache.full.l = &lumpcache.lock; lumpcache.nblocks = nblocks; lumpcache.allowed = size; lumpcache.avail = size; lumpcache.heads = MKNZ(Lump*, HashSize); lumpcache.heap = MKNZ(Lump*, nblocks); lumpcache.blocks = MKNZ(Lump, nblocks); setstat(StatLcacheSize, lumpcache.nblocks); last = nil; for(i = 0; i < nblocks; i++){ b = &lumpcache.blocks[i]; b->type = TWID8; b->heap = TWID32; b->next = last; last = b; } lumpcache.free = last; lumpcache.nheap = 0; } Lump* lookuplump(u8int *score, int type) { uint ms; Lump *b; u32int h; ms = 0; trace(TraceLump, "lookuplump enter"); h = hashbits(score, HashLog); /* * look for the block in the cache */ qlock(&lumpcache.lock); CHECK(checklumpcache()); again: for(b = lumpcache.heads[h]; b != nil; b = b->next){ if(scorecmp(score, b->score)==0 && type == b->type){ addstat(StatLcacheHit, 1); trace(TraceLump, "lookuplump hit"); goto found; } } trace(TraceLump, "lookuplump miss"); /* * missed: locate the block with the oldest second to last use. * remove it from the heap, and fix up the heap. */ while(lumpcache.free == nil){ trace(TraceLump, "lookuplump bump"); CHECK(checklumpcache()); if(bumplump() == nil){ CHECK(checklumpcache()); logerr(EAdmin, "all lump cache blocks in use"); addstat(StatLcacheStall, 1); CHECK(checklumpcache()); rsleep(&lumpcache.full); CHECK(checklumpcache()); addstat(StatLcacheStall, -1); goto again; } CHECK(checklumpcache()); } /* start timer on cache miss to avoid system call on cache hit */ ms = msec(); addstat(StatLcacheMiss, 1); b = lumpcache.free; lumpcache.free = b->next; /* * the new block has no last use, so assume it happens sometime in the middle ZZZ this is not reasonable */ b->used = (b->used2 + lumpcache.now) / 2; /* * rechain the block on the correct hash chain */ b->next = lumpcache.heads[h]; lumpcache.heads[h] = b; if(b->next != nil) b->next->prev = b; b->prev = nil; scorecp(b->score, score); b->type = type; b->size = 0; b->data = nil; found: b->ref++; b->used2 = b->used; b->used = lumpcache.now++; if(b->heap != TWID32) fixheap(b->heap, b); CHECK(checklumpcache()); qunlock(&lumpcache.lock); addstat(StatLumpStall, 1); qlock(&b->lock); addstat(StatLumpStall, -1); trace(TraceLump, "lookuplump exit"); addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0); return b; } void insertlump(Lump *b, Packet *p) { u32int size; /* * look for the block in the cache */ trace(TraceLump, "insertlump enter"); qlock(&lumpcache.lock); CHECK(checklumpcache()); again: addstat(StatLcacheWrite, 1); /* * missed: locate the block with the oldest second to last use. * remove it from the heap, and fix up the heap. */ size = packetasize(p); while(lumpcache.avail < size){ trace(TraceLump, "insertlump bump"); CHECK(checklumpcache()); if(bumplump() == nil){ logerr(EAdmin, "all lump cache blocks in use"); addstat(StatLcacheStall, 1); CHECK(checklumpcache()); rsleep(&lumpcache.full); CHECK(checklumpcache()); addstat(StatLcacheStall, -1); goto again; } CHECK(checklumpcache()); } b->data = p; b->size = size; lumpcache.avail -= size; CHECK(checklumpcache()); qunlock(&lumpcache.lock); trace(TraceLump, "insertlump exit"); } void putlump(Lump *b) { if(b == nil) return; trace(TraceLump, "putlump"); qunlock(&b->lock); qlock(&lumpcache.lock); CHECK(checklumpcache()); if(--b->ref == 0){ if(b->heap == TWID32) upheap(lumpcache.nheap++, b); trace(TraceLump, "putlump wakeup"); rwakeupall(&lumpcache.full); } CHECK(checklumpcache()); qunlock(&lumpcache.lock); } /* * remove some lump from use and update the free list and counters */ static Lump* bumplump(void) { Lump *b; u32int h; /* * remove blocks until we find one that is unused * referenced blocks are left in the heap even though * they can't be scavenged; this is simple a speed optimization */ CHECK(checklumpcache()); for(;;){ if(lumpcache.nheap == 0){ trace(TraceLump, "bumplump emptyheap"); return nil; } b = lumpcache.heap[0]; delheap(b); if(!b->ref){ trace(TraceLump, "bumplump wakeup"); rwakeupall(&lumpcache.full); break; } } /* * unchain the block */ trace(TraceLump, "bumplump unchain"); if(b->prev == nil){ h = hashbits(b->score, HashLog); if(lumpcache.heads[h] != b) sysfatal("bad hash chains in lump cache"); lumpcache.heads[h] = b->next; }else b->prev->next = b->next; if(b->next != nil) b->next->prev = b->prev; if(b->data != nil){ packetfree(b->data); b->data = nil; lumpcache.avail += b->size; b->size = 0; } b->type = TWID8; b->next = lumpcache.free; lumpcache.free = b; CHECK(checklumpcache()); trace(TraceLump, "bumplump exit"); return b; } void emptylumpcache(void) { qlock(&lumpcache.lock); while(bumplump()) ; qunlock(&lumpcache.lock); } /* * delete an arbitrary block from the heap */ static void delheap(Lump *db) { fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]); db->heap = TWID32; } /* * push an element up or down to it's correct new location */ static void fixheap(int i, Lump *b) { if(upheap(i, b) == i) downheap(i, b); } static int upheap(int i, Lump *b) { Lump *bb; u32int now; int p; now = lumpcache.now; for(; i != 0; i = p){ p = (i - 1) >> 1; bb = lumpcache.heap[p]; if(b->used2 - now >= bb->used2 - now) break; lumpcache.heap[i] = bb; bb->heap = i; } lumpcache.heap[i] = b; b->heap = i; return i; } static int downheap(int i, Lump *b) { Lump *bb; u32int now; int k; now = lumpcache.now; for(; ; i = k){ k = (i << 1) + 1; if(k >= lumpcache.nheap) break; if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now) k++; bb = lumpcache.heap[k]; if(b->used2 - now <= bb->used2 - now) break; lumpcache.heap[i] = bb; bb->heap = i; } lumpcache.heap[i] = b; b->heap = i; return i; } static void findblock(Lump *bb) { Lump *b, *last; int h; last = nil; h = hashbits(bb->score, HashLog); for(b = lumpcache.heads[h]; b != nil; b = b->next){ if(last != b->prev) sysfatal("bad prev link"); if(b == bb) return; last = b; } sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type); } void checklumpcache(void) { Lump *b; u32int size, now, nfree; int i, k, refed; now = lumpcache.now; for(i = 0; i < lumpcache.nheap; i++){ if(lumpcache.heap[i]->heap != i) sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap); if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now) sysfatal("lc: bad heap ordering"); k = (i << 1) + 1; if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now) sysfatal("lc: bad heap ordering"); k++; if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now) sysfatal("lc: bad heap ordering"); } refed = 0; size = 0; for(i = 0; i < lumpcache.nblocks; i++){ b = &lumpcache.blocks[i]; if(b->data == nil && b->size != 0) sysfatal("bad size: %d data=%p", b->size, b->data); if(b->ref && b->heap == TWID32) refed++; if(b->type != TWID8){ findblock(b); size += b->size; } if(b->heap != TWID32 && lumpcache.heap[b->heap] != b) sysfatal("lc: spurious heap value"); } if(lumpcache.avail != lumpcache.allowed - size){ fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size); *(int*)0=0; } nfree = 0; for(b = lumpcache.free; b != nil; b = b->next){ if(b->type != TWID8 || b->heap != TWID32) sysfatal("lc: bad free list"); nfree++; } if(lumpcache.nheap + nfree + refed != lumpcache.nblocks) sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks); }