123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199 |
- #include "stdinc.h"
- #include "dat.h"
- #include "fns.h"
- struct ICache
- {
- VtLock *lock; /* locks hash table & all associated data */
- IEntry **heads; /* heads of all the hash chains */
- int bits; /* bits to use for indexing heads */
- u32int size; /* number of heads; == 1 << bits, should be < entries */
- IEntry *base; /* all allocated hash table entries */
- u32int entries; /* elements in base */
- u32int unused; /* index of first unused element in base */
- u32int stolen; /* last head from which an element was stolen */
- };
- static ICache icache;
- static IEntry *icacheAlloc(IAddr *ia, u8int *score);
- /*
- * bits is the number of bits in the icache hash table
- * depth is the average depth
- * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
- */
- void
- initICache(int bits, int depth)
- {
- icache.lock = vtLockAlloc();
- icache.bits = bits;
- icache.size = 1 << bits;
- icache.entries = depth * icache.size;
- icache.base = MKNZ(IEntry, icache.entries);
- icache.heads = MKNZ(IEntry*, icache.size);
- }
- 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;
- }
- /*
- ZZZ need to think about evicting the correct IEntry,
- and writing back the wtime.
- * look up data score in the index cache
- * if this fails, pull it in from the disk index table, if it exists.
- *
- * must be called with the lump for this score locked
- */
- int
- lookupScore(u8int *score, int type, IAddr *ia, int *rac)
- {
- IEntry d, *ie, *last;
- u32int h;
- vtLock(stats.lock);
- stats.icLookups++;
- vtUnlock(stats.lock);
- vtLock(icache.lock);
- h = hashBits(score, icache.bits);
- last = nil;
- for(ie = icache.heads[h]; ie != nil; ie = ie->next){
- if(ie->ia.type == type && scoreEq(ie->score, score)){
- if(last != nil)
- last->next = ie->next;
- else
- icache.heads[h] = ie->next;
- vtLock(stats.lock);
- stats.icHits++;
- vtUnlock(stats.lock);
- ie->rac = 1;
- goto found;
- }
- last = ie;
- }
- vtUnlock(icache.lock);
- if(!loadIEntry(mainIndex, score, type, &d))
- return 0;
- /*
- * no one else can load an entry for this score,
- * since we have the overall score lock.
- */
- vtLock(stats.lock);
- stats.icFills++;
- vtUnlock(stats.lock);
- vtLock(icache.lock);
- ie = icacheAlloc(&d.ia, score);
- found:
- ie->next = icache.heads[h];
- icache.heads[h] = ie;
- *ia = ie->ia;
- *rac = ie->rac;
- vtUnlock(icache.lock);
- return 1;
- }
- /*
- * insert a new element in the hash table.
- */
- int
- insertScore(u8int *score, IAddr *ia, int write)
- {
- IEntry *ie, se;
- u32int h;
- vtLock(stats.lock);
- stats.icInserts++;
- vtUnlock(stats.lock);
- vtLock(icache.lock);
- h = hashBits(score, icache.bits);
- ie = icacheAlloc(ia, score);
- ie->next = icache.heads[h];
- icache.heads[h] = ie;
- se = *ie;
- vtUnlock(icache.lock);
- if(!write)
- return 1;
- return storeIEntry(mainIndex, &se);
- }
- /*
- * allocate a index cache entry which hasn't been used in a while.
- * must be called with icache.lock locked
- * if the score is already in the table, update the entry.
- */
- static IEntry *
- icacheAlloc(IAddr *ia, u8int *score)
- {
- IEntry *ie, *last, *next;
- u32int h;
- h = hashBits(score, icache.bits);
- last = nil;
- for(ie = icache.heads[h]; ie != nil; ie = ie->next){
- if(ie->ia.type == ia->type && scoreEq(ie->score, score)){
- if(last != nil)
- last->next = ie->next;
- else
- icache.heads[h] = ie->next;
- ie->rac = 1;
- return ie;
- }
- last = ie;
- }
- h = icache.unused;
- if(h < icache.entries){
- ie = &icache.base[h++];
- icache.unused = h;
- goto Found;
- }
- h = icache.stolen;
- for(;;){
- h++;
- if(h >= icache.size)
- h = 0;
- ie = icache.heads[h];
- if(ie != nil){
- last = nil;
- for(; next = ie->next; ie = next)
- last = ie;
- if(last != nil)
- last->next = nil;
- else
- icache.heads[h] = nil;
- icache.stolen = h;
- goto Found;
- }
- }
- Found:
- ie->ia = *ia;
- scoreCp(ie->score, score);
- ie->rac = 0;
- return ie;
- }
|