ref: 26e00d014cebde8bc07725700b5ac9c0cade8171
dir: /sys/src/cmd/venti/srv/icache.c/
#include "stdinc.h" #include "dat.h" #include "fns.h" int icacheprefetch = 1; typedef struct ICache ICache; typedef struct IHash IHash; typedef struct ISum ISum; struct ICache { QLock lock; Rendez full; IHash *hash; IEntry *entries; int nentries; IEntry free; IEntry clean; IEntry dirty; u32int maxdirty; u32int ndirty; AState as; ISum **sum; int nsum; IHash *shash; IEntry *sentries; int nsentries; }; static ICache icache; /* * Hash table of IEntries */ struct IHash { int bits; u32int size; IEntry **table; }; static IHash* mkihash(int size1) { u32int size; int bits; IHash *ih; bits = 0; size = 1; while(size < size1){ bits++; size <<= 1; } ih = vtmallocz(sizeof(IHash)+size*sizeof(ih->table[0])); ih->table = (IEntry**)(ih+1); ih->bits = bits; ih->size = size; return ih; } static IEntry* ihashlookup(IHash *ih, u8int score[VtScoreSize], int type) { u32int h; IEntry *ie; h = hashbits(score, ih->bits); for(ie=ih->table[h]; ie; ie=ie->nexthash) if((type == -1 || type == ie->ia.type) && scorecmp(score, ie->score) == 0) return ie; return nil; } static void ihashdelete(IHash *ih, IEntry *ie, char *what) { u32int h; IEntry **l; h = hashbits(ie->score, ih->bits); for(l=&ih->table[h]; *l; l=&(*l)->nexthash) if(*l == ie){ *l = ie->nexthash; return; } fprint(2, "warning: %s %V not found in ihashdelete\n", what, ie->score); } static void ihashinsert(IHash *ih, IEntry *ie) { u32int h; h = hashbits(ie->score, ih->bits); ie->nexthash = ih->table[h]; ih->table[h] = ie; } /* * IEntry lists. */ static IEntry* popout(IEntry *ie) { if(ie->prev == nil && ie->next == nil) return ie; ie->prev->next = ie->next; ie->next->prev = ie->prev; ie->next = nil; ie->prev = nil; return ie; } static IEntry* poplast(IEntry *list) { if(list->prev == list) return nil; return popout(list->prev); } static IEntry* pushfirst(IEntry *list, IEntry *ie) { popout(ie); ie->prev = list; ie->next = list->next; ie->prev->next = ie; ie->next->prev = ie; return ie; } /* * Arena summary cache. */ struct ISum { QLock lock; IEntry *entries; int nentries; int loaded; u64int addr; u64int limit; Arena *arena; int g; }; static ISum* scachelookup(u64int addr) { int i; ISum *s; for(i=0; i<icache.nsum; i++){ s = icache.sum[i]; if(s->addr <= addr && addr < s->limit){ if(i > 0){ memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]); icache.sum[0] = s; } return s; } } return nil; } static void sumclear(ISum *s) { int i; for(i=0; i<s->nentries; i++) ihashdelete(icache.shash, &s->entries[i], "scache"); s->nentries = 0; s->loaded = 0; s->addr = 0; s->limit = 0; s->arena = nil; s->g = 0; } static ISum* scacheevict(void) { ISum *s; int i; for(i=icache.nsum-1; i>=0; i--){ s = icache.sum[i]; if(canqlock(&s->lock)){ if(i > 0){ memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]); icache.sum[0] = s; } sumclear(s); return s; } } return nil; } static void scachehit(u64int addr) { scachelookup(addr); /* for move-to-front */ } static void scachesetup(ISum *s, u64int addr) { u64int addr0, limit; int g; s->arena = amapitoag(mainindex, addr, &addr0, &limit, &g); s->addr = addr0; s->limit = limit; s->g = g; } static void scacheload(ISum *s) { int i, n; s->loaded = 1; n = asumload(s->arena, s->g, s->entries, ArenaCIGSize); /* * n can be less then ArenaCIGSize, either if the clump group * is the last in the arena and is only partially filled, or if there * are corrupt clumps in the group -- those are not returned. */ for(i=0; i<n; i++){ s->entries[i].ia.addr += s->addr; ihashinsert(icache.shash, &s->entries[i]); } //fprint(2, "%T scacheload %s %d - %d entries\n", s->arena->name, s->g, n); addstat(StatScachePrefetch, n); s->nentries = n; } static ISum* scachemiss(u64int addr) { ISum *s; if(!icacheprefetch) return nil; s = scachelookup(addr); if(s == nil){ /* first time: make an entry in the cache but don't populate it yet */ s = scacheevict(); if(s == nil) return nil; scachesetup(s, addr); qunlock(&s->lock); return nil; } /* second time: load from disk */ qlock(&s->lock); if(s->loaded || !icacheprefetch){ qunlock(&s->lock); return nil; } return s; /* locked */ } /* * Index cache. */ void initicache(u32int mem0) { u32int mem; int i, entries, scache; icache.full.l = &icache.lock; mem = mem0; entries = mem / (sizeof(IEntry)+sizeof(IEntry*)); scache = (entries/8) / ArenaCIGSize; entries -= entries/8; if(scache < 4) scache = 4; if(scache > 16) scache = 16; if(entries < 1000) entries = 1000; fprint(2, "icache %,d bytes = %,d entries; %d scache\n", mem0, entries, scache); icache.clean.prev = icache.clean.next = &icache.clean; icache.dirty.prev = icache.dirty.next = &icache.dirty; icache.free.prev = icache.free.next = &icache.free; icache.hash = mkihash(entries); icache.nentries = entries; setstat(StatIcacheSize, entries); icache.entries = vtmallocz(entries*sizeof icache.entries[0]); icache.maxdirty = entries / 2; for(i=0; i<entries; i++) pushfirst(&icache.free, &icache.entries[i]); icache.nsum = scache; icache.sum = vtmallocz(scache*sizeof icache.sum[0]); icache.sum[0] = vtmallocz(scache*sizeof icache.sum[0][0]); icache.nsentries = scache * ArenaCIGSize; icache.sentries = vtmallocz(scache*ArenaCIGSize*sizeof icache.sentries[0]); icache.shash = mkihash(scache*ArenaCIGSize); for(i=0; i<scache; i++){ icache.sum[i] = icache.sum[0] + i; icache.sum[i]->entries = icache.sentries + i*ArenaCIGSize; } } static IEntry* evictlru(void) { IEntry *ie; ie = poplast(&icache.clean); if(ie == nil) return nil; ihashdelete(icache.hash, ie, "evictlru"); return ie; } static void icacheinsert(u8int score[VtScoreSize], IAddr *ia, int state) { IEntry *ie; if((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){ addstat(StatIcacheStall, 1); while((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){ // Could safely return here if state == IEClean. // But if state == IEDirty, have to wait to make // sure we don't lose an index write. // Let's wait all the time. flushdcache(); kickicache(); rsleep(&icache.full); } addstat(StatIcacheStall, -1); } memmove(ie->score, score, VtScoreSize); ie->state = state; ie->ia = *ia; if(state == IEClean){ addstat(StatIcachePrefetch, 1); pushfirst(&icache.clean, ie); }else{ addstat(StatIcacheWrite, 1); assert(state == IEDirty); icache.ndirty++; setstat(StatIcacheDirty, icache.ndirty); delaykickicache(); pushfirst(&icache.dirty, ie); } ihashinsert(icache.hash, ie); } int icachelookup(u8int score[VtScoreSize], int type, IAddr *ia) { IEntry *ie; qlock(&icache.lock); addstat(StatIcacheLookup, 1); if((ie = ihashlookup(icache.hash, score, type)) != nil){ *ia = ie->ia; if(ie->state == IEClean) pushfirst(&icache.clean, ie); addstat(StatIcacheHit, 1); qunlock(&icache.lock); return 0; } if((ie = ihashlookup(icache.shash, score, type)) != nil){ *ia = ie->ia; icacheinsert(score, &ie->ia, IEClean); scachehit(ie->ia.addr); addstat(StatScacheHit, 1); qunlock(&icache.lock); return 0; } addstat(StatIcacheMiss, 1); qunlock(&icache.lock); return -1; } int insertscore(u8int score[VtScoreSize], IAddr *ia, int state, AState *as) { ISum *toload; qlock(&icache.lock); icacheinsert(score, ia, state); if(state == IEClean) toload = scachemiss(ia->addr); else{ assert(state == IEDirty); toload = nil; if(as == nil) fprint(2, "%T insertscore IEDirty without as; called from %#p\n", getcallerpc(&score)); else{ if(icache.as.aa > as->aa) fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa); icache.as = *as; } } qunlock(&icache.lock); if(toload){ scacheload(toload); qunlock(&toload->lock); } if(icache.ndirty >= icache.maxdirty) kickicache(); /* * It's okay not to do this under icache.lock. * Calling insertscore only happens when we hold * the lump, meaning any searches for this block * will hit in the lump cache until after we return. */ if(state == IEDirty) markbloomfilter(mainindex->bloom, score); return 0; } int lookupscore(u8int score[VtScoreSize], int type, IAddr *ia) { int ms, ret; IEntry d; if(icachelookup(score, type, ia) >= 0){ addstat(StatIcacheRead, 1); return 0; } ms = msec(); addstat(StatIcacheFill, 1); if(loadientry(mainindex, score, type, &d) < 0) ret = -1; else{ ret = 0; insertscore(score, &d.ia, IEClean, nil); *ia = d.ia; } addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms); return ret; } u32int hashbits(u8int *sc, int bits) { u32int v; v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3]; if(bits < 32) v >>= (32 - bits); return v; } ulong icachedirtyfrac(void) { return (vlong)icache.ndirty*IcacheFrac / icache.nentries; } /* * Return a singly-linked list of dirty index entries. * with 32-bit hash numbers between lo and hi * and address < limit. */ IEntry* icachedirty(u32int lo, u32int hi, u64int limit) { u32int h; IEntry *ie, *dirty; dirty = nil; trace(TraceProc, "icachedirty enter"); qlock(&icache.lock); for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){ if(ie->state == IEDirty && ie->ia.addr <= limit){ h = hashbits(ie->score, 32); if(lo <= h && h <= hi){ ie->nextdirty = dirty; dirty = ie; } } } qunlock(&icache.lock); trace(TraceProc, "icachedirty exit"); if(dirty == nil) flushdcache(); return dirty; } AState icachestate(void) { AState as; qlock(&icache.lock); as = icache.as; qunlock(&icache.lock); return as; } /* * The singly-linked non-circular list of index entries ie * has been written to disk. Move them to the clean list. */ void icacheclean(IEntry *ie) { IEntry *next; trace(TraceProc, "icacheclean enter"); qlock(&icache.lock); for(; ie; ie=next){ assert(ie->state == IEDirty); next = ie->nextdirty; ie->nextdirty = nil; popout(ie); /* from icache.dirty */ icache.ndirty--; ie->state = IEClean; pushfirst(&icache.clean, ie); } setstat(StatIcacheDirty, icache.ndirty); rwakeupall(&icache.full); qunlock(&icache.lock); trace(TraceProc, "icacheclean exit"); } void emptyicache(void) { int i; IEntry *ie; ISum *s; qlock(&icache.lock); while((ie = evictlru()) != nil) pushfirst(&icache.free, ie); for(i=0; i<icache.nsum; i++){ s = icache.sum[i]; qlock(&s->lock); sumclear(s); qunlock(&s->lock); } qunlock(&icache.lock); }