123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382 |
- #include "stdinc.h"
- #include "dat.h"
- #include "fns.h"
- typedef struct LumpCache LumpCache;
- enum
- {
- HashLog = 9,
- HashSize = 1<<HashLog,
- HashMask = HashSize - 1,
- };
- struct LumpCache
- {
- VtLock *lock;
- VtRendez *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.lock = vtLockAlloc();
- lumpCache.full = vtRendezAlloc(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);
- last = nil;
- for(i = 0; i < nblocks; i++){
- b = &lumpCache.blocks[i];
- b->type = TWID8;
- b->heap = TWID32;
- b->lock = vtLockAlloc();
- b->next = last;
- last = b;
- }
- lumpCache.free = last;
- lumpCache.nheap = 0;
- }
- Lump*
- lookupLump(u8int *score, int type)
- {
- Lump *b;
- u32int h;
- h = hashBits(score, HashLog);
- /*
- * look for the block in the cache
- */
- //checkLumpCache();
- vtLock(lumpCache.lock);
- again:
- for(b = lumpCache.heads[h]; b != nil; b = b->next){
- if(scoreEq(score, b->score) && type == b->type){
- vtLock(stats.lock);
- stats.lumpHit++;
- vtUnlock(stats.lock);
- goto found;
- }
- }
- /*
- * 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){
- if(bumpLump() == nil){
- logErr(EAdmin, "all lump cache blocks in use");
- vtSleep(lumpCache.full);
- goto again;
- }
- }
- vtLock(stats.lock);
- stats.lumpMiss++;
- vtUnlock(stats.lock);
- 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);
- vtUnlock(lumpCache.lock);
- //checkLumpCache();
- vtLock(b->lock);
- return b;
- }
- void
- insertLump(Lump *b, Packet *p)
- {
- u32int size;
- /*
- * look for the block in the cache
- */
- //checkLumpCache();
- vtLock(lumpCache.lock);
- again:
- /*
- * missed: locate the block with the oldest second to last use.
- * remove it from the heap, and fix up the heap.
- */
- size = packetAllocatedSize(p);
- //ZZZ
- while(lumpCache.avail < size){
- if(bumpLump() == nil){
- logErr(EAdmin, "all lump cache blocks in use");
- vtSleep(lumpCache.full);
- goto again;
- }
- }
- b->data = p;
- b->size = size;
- lumpCache.avail -= size;
- vtUnlock(lumpCache.lock);
- //checkLumpCache();
- }
- void
- putLump(Lump *b)
- {
- if(b == nil)
- return;
- vtUnlock(b->lock);
- //checkLumpCache();
- vtLock(lumpCache.lock);
- if(--b->ref == 0){
- if(b->heap == TWID32)
- upHeap(lumpCache.nheap++, b);
- vtWakeup(lumpCache.full);
- }
- vtUnlock(lumpCache.lock);
- //checkLumpCache();
- }
- /*
- * 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
- */
- for(;;){
- if(lumpCache.nheap == 0)
- return nil;
- b = lumpCache.heap[0];
- delHeap(b);
- if(!b->ref){
- vtWakeup(lumpCache.full);
- break;
- }
- }
- /*
- * unchain the block
- */
- if(b->prev == nil){
- h = hashBits(b->score, HashLog);
- if(lumpCache.heads[h] != b)
- fatal("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;
- return b;
- }
- /*
- * 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)
- fatal("bad prev link");
- if(b == bb)
- return;
- last = b;
- }
- fatal("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;
- vtLock(lumpCache.lock);
- now = lumpCache.now;
- for(i = 0; i < lumpCache.nheap; i++){
- if(lumpCache.heap[i]->heap != i)
- fatal("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)
- fatal("lc: bad heap ordering");
- k = (i << 1) + 1;
- if(k < lumpCache.nheap && lumpCache.heap[i]->used2 - now > lumpCache.heap[k]->used2 - now)
- fatal("lc: bad heap ordering");
- k++;
- if(k < lumpCache.nheap && lumpCache.heap[i]->used2 - now > lumpCache.heap[k]->used2 - now)
- fatal("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)
- fatal("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)
- fatal("lc: spurious heap value");
- }
- if(lumpCache.avail != lumpCache.allowed - size)
- fatal("mismatched available=%d and allowed=%d - used=%d space", lumpCache.avail, lumpCache.allowed, size);
- nfree = 0;
- for(b = lumpCache.free; b != nil; b = b->next){
- if(b->type != TWID8 || b->heap != TWID32)
- fatal("lc: bad free list");
- nfree++;
- }
- if(lumpCache.nheap + nfree + refed != lumpCache.nblocks)
- fatal("lc: missing blocks: %d %d %d %d", lumpCache.nheap, refed, nfree, lumpCache.nblocks);
- vtUnlock(lumpCache.lock);
- }
|