5 typedef struct ICache ICache;
8 QLock lock; /* locks hash table & all associated data */
10 IEntry **heads; /* heads of all the hash chains */
11 int bits; /* bits to use for indexing heads */
12 u32int size; /* number of heads; == 1 << bits, should be < entries */
13 IEntry *base; /* all allocated hash table entries */
14 u32int entries; /* elements in base */
15 IEntry *dirty; /* chain of dirty elements */
18 u32int unused; /* index of first unused element in base */
19 u32int stolen; /* last head from which an element was stolen */
28 static IEntry *icachealloc(IAddr *ia, u8int *score);
31 * bits is the number of bits in the icache hash table
32 * depth is the average depth
33 * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
36 initicache(int bits, int depth)
39 icache.size = 1 << bits;
40 icache.entries = depth * icache.size;
41 icache.maxdirty = icache.entries/2;
42 icache.base = MKNZ(IEntry, icache.entries);
43 icache.heads = MKNZ(IEntry*, icache.size);
44 icache.full.l = &icache.lock;
45 setstat(StatIcacheSize, icache.entries);
49 hashbits(u8int *sc, int bits)
53 v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
60 loadarenaclumps(Arena *arena, u64int aa)
66 fprint(2, "seed index cache with arena @%llud, (map %llud), %d clumps\n", arena->base, aa, arena->memstats.clumps);
67 for(i=0; i<arena->memstats.clumps; i++){
68 if(readclumpinfo(arena, i, &ci) < 0)
72 ia.blocks = (ci.size + ClumpSize + (1 << ABlockLog) - 1) >> ABlockLog;
74 aa += ClumpSize + ci.size;
75 if(ia.type != VtCorruptType)
76 insertscore(ci.score, &ia, 0);
81 ZZZ need to think about evicting the correct IEntry,
82 and writing back the wtime.
83 * look up data score in the index cache
84 * if this fails, pull it in from the disk index table, if it exists.
86 * must be called with the lump for this score locked
89 lookupscore(u8int *score, int type, IAddr *ia, int *rac)
102 trace(TraceLump, "lookupscore %V.%d", score, type);
105 h = hashbits(score, icache.bits);
107 for(ie = icache.heads[h]; ie != nil; ie = ie->next){
108 if(ie->ia.type == type && scorecmp(ie->score, score)==0){
110 last->next = ie->next;
112 icache.heads[h] = ie->next;
113 addstat(StatIcacheHit, 1);
115 trace(TraceLump, "lookupscore incache");
120 addstat(StatIcacheMiss, 1);
121 qunlock(&icache.lock);
123 if(loadientry(mainindex, score, type, &d) < 0){
125 addstat2(StatIcacheRead, 1, StatIcacheReadTime, ms);
129 addstat(StatIcacheFill, 1);
131 trace(TraceLump, "lookupscore loaded");
134 * no one else can load an entry for this score,
135 * since we have the overall score lock.
140 * If we notice that all the hits are coming from one arena,
141 * load the table of contents for that arena into the cache.
143 ie = icachealloc(&d.ia, score);
144 icache.last[icache.nlast++%nelem(icache.last)] = amapitoa(mainindex, ie->ia.addr, &aa);
145 aa = ie->ia.addr - aa; /* compute base addr of arena */
146 for(i=0; i<nelem(icache.last); i++)
147 if(icache.last[i] != icache.last[0])
149 if(i==nelem(icache.last) && icache.lastload != icache.last[0]){
150 load = icache.last[0];
151 icache.lastload = load;
155 ie->next = icache.heads[h];
156 icache.heads[h] = ie;
161 qunlock(&icache.lock);
164 trace(TraceProc, "preload 0x%llux", aa);
165 loadarenaclumps(load, aa);
168 addstat2(StatIcacheRead, 1, StatIcacheReadTime, ms);
174 * insert a new element in the hash table.
177 insertscore(u8int *score, IAddr *ia, int write)
182 trace(TraceLump, "insertscore enter");
184 addstat(StatIcacheWrite, 1);
186 addstat(StatIcachePrefetch, 1);
189 h = hashbits(score, icache.bits);
191 ie = icachealloc(ia, score);
194 setstat(StatIcacheDirty, icache.ndirty);
198 ie->next = icache.heads[h];
199 icache.heads[h] = ie;
202 qunlock(&icache.lock);
204 if(write && icache.ndirty >= icache.maxdirty)
208 * It's okay not to do this under icache.lock.
209 * Calling insertscore only happens when we hold
210 * the lump, meaning any searches for this block
211 * will hit in the lump cache until after we return.
213 markbloomfilter(mainindex->bloom, score);
219 * allocate a index cache entry which hasn't been used in a while.
220 * must be called with icache.lock locked
221 * if the score is already in the table, update the entry.
224 icachealloc(IAddr *ia, u8int *score)
227 IEntry *ie, *last, *clean, *lastclean;
230 h = hashbits(score, icache.bits);
232 for(ie = icache.heads[h]; ie != nil; ie = ie->next){
233 if(ie->ia.type == ia->type && scorecmp(ie->score, score)==0){
235 last->next = ie->next;
237 icache.heads[h] = ie->next;
238 trace(TraceLump, "icachealloc hit");
246 if(h < icache.entries){
247 ie = &icache.base[h++];
249 trace(TraceLump, "icachealloc unused");
258 if(i == icache.size){
259 trace(TraceLump, "icachealloc sleep");
260 addstat(StatIcacheStall, 1);
261 while(icache.ndirty == icache.entries){
263 * This is a bit suspect. Kickicache will wake up the
264 * icachewritecoord, but if all the index entries are for
265 * unflushed disk blocks, icachewritecoord won't be
266 * able to do much. It always rewakes everyone when
267 * it thinks it is done, though, so at least we'll go around
268 * the while loop again. Also, if icachewritecoord sees
269 * that the disk state hasn't change at all since the last
270 * time around, it kicks the disk. This needs to be
271 * rethought, but it shouldn't deadlock anymore.
274 rsleep(&icache.full);
276 addstat(StatIcacheStall, -1);
282 for(ie=icache.heads[h]; ie; last=ie, ie=ie->next){
290 lastclean->next = clean->next;
292 icache.heads[h] = clean->next;
296 trace(TraceLump, "icachealloc steal");
303 scorecp(ie->score, score);
309 icachedirty(u32int lo, u32int hi, u64int limit)
316 trace(TraceProc, "icachedirty enter");
318 for(i=0; i<icache.size; i++)
319 for(ie = icache.heads[i]; ie; ie=ie->next)
320 if(ie->dirty && ie->ia.addr != 0 && ie->ia.addr < limit){
321 h = hashbits(ie->score, 32);
322 if(lo <= h && h <= hi){
323 ie->nextdirty = dirty;
327 qunlock(&icache.lock);
328 trace(TraceProc, "icachedirty exit");
335 icacheclean(IEntry *ie)
337 trace(TraceProc, "icachedirty enter");
339 for(; ie; ie=ie->nextdirty){
343 setstat(StatIcacheDirty, icache.ndirty);
344 rwakeupall(&icache.full);
345 qunlock(&icache.lock);
346 trace(TraceProc, "icachedirty exit");