1 a0d146ed 2005-07-12 devnull #include "stdinc.h"
2 a0d146ed 2005-07-12 devnull #include "dat.h"
3 a0d146ed 2005-07-12 devnull #include "fns.h"
5 a0d146ed 2005-07-12 devnull typedef struct ICache ICache;
6 a0d146ed 2005-07-12 devnull struct ICache
8 a0d146ed 2005-07-12 devnull QLock lock; /* locks hash table & all associated data */
9 a0d146ed 2005-07-12 devnull Rendez full;
10 a0d146ed 2005-07-12 devnull IEntry **heads; /* heads of all the hash chains */
11 a0d146ed 2005-07-12 devnull int bits; /* bits to use for indexing heads */
12 a0d146ed 2005-07-12 devnull u32int size; /* number of heads; == 1 << bits, should be < entries */
13 a0d146ed 2005-07-12 devnull IEntry *base; /* all allocated hash table entries */
14 a0d146ed 2005-07-12 devnull u32int entries; /* elements in base */
15 a0d146ed 2005-07-12 devnull IEntry *dirty; /* chain of dirty elements */
16 a0d146ed 2005-07-12 devnull u32int ndirty;
17 a0d146ed 2005-07-12 devnull u32int maxdirty;
18 a0d146ed 2005-07-12 devnull u32int unused; /* index of first unused element in base */
19 a0d146ed 2005-07-12 devnull u32int stolen; /* last head from which an element was stolen */
21 a0d146ed 2005-07-12 devnull Arena *last[4];
22 a0d146ed 2005-07-12 devnull Arena *lastload;
23 a0d146ed 2005-07-12 devnull int nlast;
26 a0d146ed 2005-07-12 devnull static ICache icache;
28 a0d146ed 2005-07-12 devnull static IEntry *icachealloc(IAddr *ia, u8int *score);
31 a0d146ed 2005-07-12 devnull * bits is the number of bits in the icache hash table
32 a0d146ed 2005-07-12 devnull * depth is the average depth
33 a0d146ed 2005-07-12 devnull * memory usage is about (1<<bits) * depth * sizeof(IEntry) + (1<<bits) * sizeof(IEntry*)
36 a0d146ed 2005-07-12 devnull initicache(int bits, int depth)
38 a0d146ed 2005-07-12 devnull icache.bits = bits;
39 a0d146ed 2005-07-12 devnull icache.size = 1 << bits;
40 a0d146ed 2005-07-12 devnull icache.entries = depth * icache.size;
41 a0d146ed 2005-07-12 devnull icache.maxdirty = icache.entries/2;
42 a0d146ed 2005-07-12 devnull icache.base = MKNZ(IEntry, icache.entries);
43 a0d146ed 2005-07-12 devnull icache.heads = MKNZ(IEntry*, icache.size);
44 a0d146ed 2005-07-12 devnull icache.full.l = &icache.lock;
45 a0d146ed 2005-07-12 devnull setstat(StatIcacheSize, icache.entries);
49 a0d146ed 2005-07-12 devnull hashbits(u8int *sc, int bits)
51 a0d146ed 2005-07-12 devnull u32int v;
53 a0d146ed 2005-07-12 devnull v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
54 a0d146ed 2005-07-12 devnull if(bits < 32)
55 a0d146ed 2005-07-12 devnull v >>= (32 - bits);
56 a0d146ed 2005-07-12 devnull return v;
59 a0d146ed 2005-07-12 devnull static void
60 a0d146ed 2005-07-12 devnull loadarenaclumps(Arena *arena, u64int aa)
63 a0d146ed 2005-07-12 devnull ClumpInfo ci;
64 a0d146ed 2005-07-12 devnull IAddr ia;
66 a0d146ed 2005-07-12 devnull fprint(2, "seed index cache with arena @%llud, (map %llud), %d clumps\n", arena->base, aa, arena->memstats.clumps);
67 a0d146ed 2005-07-12 devnull for(i=0; i<arena->memstats.clumps; i++){
68 a0d146ed 2005-07-12 devnull if(readclumpinfo(arena, i, &ci) < 0)
70 a0d146ed 2005-07-12 devnull ia.type = ci.type;
71 a0d146ed 2005-07-12 devnull ia.size = ci.uncsize;
72 a0d146ed 2005-07-12 devnull ia.blocks = (ci.size + ClumpSize + (1 << ABlockLog) - 1) >> ABlockLog;
73 a0d146ed 2005-07-12 devnull ia.addr = aa;
74 a0d146ed 2005-07-12 devnull aa += ClumpSize + ci.size;
75 a0d146ed 2005-07-12 devnull if(ia.type != VtCorruptType)
76 a0d146ed 2005-07-12 devnull insertscore(ci.score, &ia, 0);
81 a0d146ed 2005-07-12 devnull ZZZ need to think about evicting the correct IEntry,
82 a0d146ed 2005-07-12 devnull and writing back the wtime.
83 a0d146ed 2005-07-12 devnull * look up data score in the index cache
84 a0d146ed 2005-07-12 devnull * if this fails, pull it in from the disk index table, if it exists.
86 a0d146ed 2005-07-12 devnull * must be called with the lump for this score locked
89 a0d146ed 2005-07-12 devnull lookupscore(u8int *score, int type, IAddr *ia, int *rac)
91 a0d146ed 2005-07-12 devnull IEntry d, *ie, *last;
92 a0d146ed 2005-07-12 devnull u32int h;
93 a0d146ed 2005-07-12 devnull u64int aa;
94 a0d146ed 2005-07-12 devnull Arena *load;
98 a0d146ed 2005-07-12 devnull load = nil;
100 a0d146ed 2005-07-12 devnull ms = msec();
102 a0d146ed 2005-07-12 devnull trace(TraceLump, "lookupscore %V.%d", score, type);
104 a0d146ed 2005-07-12 devnull qlock(&icache.lock);
105 a0d146ed 2005-07-12 devnull h = hashbits(score, icache.bits);
106 a0d146ed 2005-07-12 devnull last = nil;
107 a0d146ed 2005-07-12 devnull for(ie = icache.heads[h]; ie != nil; ie = ie->next){
108 a0d146ed 2005-07-12 devnull if(ie->ia.type == type && scorecmp(ie->score, score)==0){
109 a0d146ed 2005-07-12 devnull if(last != nil)
110 a0d146ed 2005-07-12 devnull last->next = ie->next;
112 a0d146ed 2005-07-12 devnull icache.heads[h] = ie->next;
113 a0d146ed 2005-07-12 devnull addstat(StatIcacheHit, 1);
114 a0d146ed 2005-07-12 devnull ie->rac = 1;
115 a0d146ed 2005-07-12 devnull trace(TraceLump, "lookupscore incache");
116 a0d146ed 2005-07-12 devnull goto found;
118 a0d146ed 2005-07-12 devnull last = ie;
120 a0d146ed 2005-07-12 devnull addstat(StatIcacheMiss, 1);
121 a0d146ed 2005-07-12 devnull qunlock(&icache.lock);
123 a0d146ed 2005-07-12 devnull if(loadientry(mainindex, score, type, &d) < 0){
124 a0d146ed 2005-07-12 devnull ms = msec() - ms;
125 a0d146ed 2005-07-12 devnull addstat2(StatIcacheRead, 1, StatIcacheReadTime, ms);
126 a0d146ed 2005-07-12 devnull return -1;
129 a0d146ed 2005-07-12 devnull addstat(StatIcacheFill, 1);
131 a0d146ed 2005-07-12 devnull trace(TraceLump, "lookupscore loaded");
134 a0d146ed 2005-07-12 devnull * no one else can load an entry for this score,
135 a0d146ed 2005-07-12 devnull * since we have the overall score lock.
137 a0d146ed 2005-07-12 devnull qlock(&icache.lock);
140 a0d146ed 2005-07-12 devnull * If we notice that all the hits are coming from one arena,
141 a0d146ed 2005-07-12 devnull * load the table of contents for that arena into the cache.
143 a0d146ed 2005-07-12 devnull ie = icachealloc(&d.ia, score);
144 a0d146ed 2005-07-12 devnull icache.last[icache.nlast++%nelem(icache.last)] = amapitoa(mainindex, ie->ia.addr, &aa);
145 a0d146ed 2005-07-12 devnull aa = ie->ia.addr - aa; /* compute base addr of arena */
146 a0d146ed 2005-07-12 devnull for(i=0; i<nelem(icache.last); i++)
147 a0d146ed 2005-07-12 devnull if(icache.last[i] != icache.last[0])
149 a0d146ed 2005-07-12 devnull if(i==nelem(icache.last) && icache.lastload != icache.last[0]){
150 a0d146ed 2005-07-12 devnull load = icache.last[0];
151 a0d146ed 2005-07-12 devnull icache.lastload = load;
155 a0d146ed 2005-07-12 devnull ie->next = icache.heads[h];
156 a0d146ed 2005-07-12 devnull icache.heads[h] = ie;
158 a0d146ed 2005-07-12 devnull *ia = ie->ia;
159 a0d146ed 2005-07-12 devnull *rac = ie->rac;
161 a0d146ed 2005-07-12 devnull qunlock(&icache.lock);
163 a0d146ed 2005-07-12 devnull if(load){
164 a0d146ed 2005-07-12 devnull trace(TraceProc, "preload 0x%llux", aa);
165 a0d146ed 2005-07-12 devnull loadarenaclumps(load, aa);
167 a0d146ed 2005-07-12 devnull ms = msec() - ms;
168 a0d146ed 2005-07-12 devnull addstat2(StatIcacheRead, 1, StatIcacheReadTime, ms);
170 a0d146ed 2005-07-12 devnull return 0;
174 a0d146ed 2005-07-12 devnull * insert a new element in the hash table.
177 a0d146ed 2005-07-12 devnull insertscore(u8int *score, IAddr *ia, int write)
179 a0d146ed 2005-07-12 devnull IEntry *ie, se;
180 a0d146ed 2005-07-12 devnull u32int h;
182 a0d146ed 2005-07-12 devnull trace(TraceLump, "insertscore enter");
183 a0d146ed 2005-07-12 devnull if(write)
184 a0d146ed 2005-07-12 devnull addstat(StatIcacheWrite, 1);
186 a0d146ed 2005-07-12 devnull addstat(StatIcachePrefetch, 1);
188 a0d146ed 2005-07-12 devnull qlock(&icache.lock);
189 a0d146ed 2005-07-12 devnull h = hashbits(score, icache.bits);
191 a0d146ed 2005-07-12 devnull ie = icachealloc(ia, score);
192 a0d146ed 2005-07-12 devnull if(write){
193 a0d146ed 2005-07-12 devnull icache.ndirty++;
194 a0d146ed 2005-07-12 devnull setstat(StatIcacheDirty, icache.ndirty);
195 a0d146ed 2005-07-12 devnull delaykickicache();
196 a0d146ed 2005-07-12 devnull ie->dirty = 1;
198 a0d146ed 2005-07-12 devnull ie->next = icache.heads[h];
199 a0d146ed 2005-07-12 devnull icache.heads[h] = ie;
201 a0d146ed 2005-07-12 devnull se = *ie;
202 a0d146ed 2005-07-12 devnull qunlock(&icache.lock);
204 a0d146ed 2005-07-12 devnull if(write && icache.ndirty >= icache.maxdirty)
205 a0d146ed 2005-07-12 devnull kickicache();
208 a0d146ed 2005-07-12 devnull * It's okay not to do this under icache.lock.
209 a0d146ed 2005-07-12 devnull * Calling insertscore only happens when we hold
210 a0d146ed 2005-07-12 devnull * the lump, meaning any searches for this block
211 a0d146ed 2005-07-12 devnull * will hit in the lump cache until after we return.
213 a0d146ed 2005-07-12 devnull markbloomfilter(mainindex->bloom, score);
215 a0d146ed 2005-07-12 devnull return 0;
219 a0d146ed 2005-07-12 devnull * allocate a index cache entry which hasn't been used in a while.
220 a0d146ed 2005-07-12 devnull * must be called with icache.lock locked
221 a0d146ed 2005-07-12 devnull * if the score is already in the table, update the entry.
223 a0d146ed 2005-07-12 devnull static IEntry *
224 a0d146ed 2005-07-12 devnull icachealloc(IAddr *ia, u8int *score)
227 a0d146ed 2005-07-12 devnull IEntry *ie, *last, *clean, *lastclean;
228 a0d146ed 2005-07-12 devnull u32int h;
230 a0d146ed 2005-07-12 devnull h = hashbits(score, icache.bits);
231 a0d146ed 2005-07-12 devnull last = nil;
232 a0d146ed 2005-07-12 devnull for(ie = icache.heads[h]; ie != nil; ie = ie->next){
233 a0d146ed 2005-07-12 devnull if(ie->ia.type == ia->type && scorecmp(ie->score, score)==0){
234 a0d146ed 2005-07-12 devnull if(last != nil)
235 a0d146ed 2005-07-12 devnull last->next = ie->next;
237 a0d146ed 2005-07-12 devnull icache.heads[h] = ie->next;
238 a0d146ed 2005-07-12 devnull trace(TraceLump, "icachealloc hit");
239 a0d146ed 2005-07-12 devnull ie->rac = 1;
240 a0d146ed 2005-07-12 devnull return ie;
242 a0d146ed 2005-07-12 devnull last = ie;
245 a0d146ed 2005-07-12 devnull h = icache.unused;
246 a0d146ed 2005-07-12 devnull if(h < icache.entries){
247 a0d146ed 2005-07-12 devnull ie = &icache.base[h++];
248 a0d146ed 2005-07-12 devnull icache.unused = h;
249 a0d146ed 2005-07-12 devnull trace(TraceLump, "icachealloc unused");
250 a0d146ed 2005-07-12 devnull goto Found;
253 a0d146ed 2005-07-12 devnull h = icache.stolen;
254 a0d146ed 2005-07-12 devnull for(i=0;; i++){
256 a0d146ed 2005-07-12 devnull if(h >= icache.size)
258 a0d146ed 2005-07-12 devnull if(i == icache.size){
259 a0d146ed 2005-07-12 devnull trace(TraceLump, "icachealloc sleep");
260 a0d146ed 2005-07-12 devnull addstat(StatIcacheStall, 1);
261 a0d146ed 2005-07-12 devnull while(icache.ndirty == icache.entries){
263 a0d146ed 2005-07-12 devnull * This is a bit suspect. Kickicache will wake up the
264 a0d146ed 2005-07-12 devnull * icachewritecoord, but if all the index entries are for
265 a0d146ed 2005-07-12 devnull * unflushed disk blocks, icachewritecoord won't be
266 a0d146ed 2005-07-12 devnull * able to do much. It always rewakes everyone when
267 a0d146ed 2005-07-12 devnull * it thinks it is done, though, so at least we'll go around
268 a0d146ed 2005-07-12 devnull * the while loop again. Also, if icachewritecoord sees
269 a0d146ed 2005-07-12 devnull * that the disk state hasn't change at all since the last
270 a0d146ed 2005-07-12 devnull * time around, it kicks the disk. This needs to be
271 a0d146ed 2005-07-12 devnull * rethought, but it shouldn't deadlock anymore.
273 a0d146ed 2005-07-12 devnull kickicache();
274 a0d146ed 2005-07-12 devnull rsleep(&icache.full);
276 a0d146ed 2005-07-12 devnull addstat(StatIcacheStall, -1);
279 a0d146ed 2005-07-12 devnull lastclean = nil;
280 a0d146ed 2005-07-12 devnull clean = nil;
281 a0d146ed 2005-07-12 devnull last = nil;
282 a0d146ed 2005-07-12 devnull for(ie=icache.heads[h]; ie; last=ie, ie=ie->next){
283 a0d146ed 2005-07-12 devnull if(!ie->dirty){
284 a0d146ed 2005-07-12 devnull clean = ie;
285 a0d146ed 2005-07-12 devnull lastclean = last;
288 a0d146ed 2005-07-12 devnull if(clean){
289 a0d146ed 2005-07-12 devnull if(lastclean)
290 a0d146ed 2005-07-12 devnull lastclean->next = clean->next;
292 a0d146ed 2005-07-12 devnull icache.heads[h] = clean->next;
293 a0d146ed 2005-07-12 devnull clean->next = nil;
294 a0d146ed 2005-07-12 devnull icache.stolen = h;
295 a0d146ed 2005-07-12 devnull ie = clean;
296 a0d146ed 2005-07-12 devnull trace(TraceLump, "icachealloc steal");
297 a0d146ed 2005-07-12 devnull goto Found;
302 a0d146ed 2005-07-12 devnull ie->ia = *ia;
303 a0d146ed 2005-07-12 devnull scorecp(ie->score, score);
304 a0d146ed 2005-07-12 devnull ie->rac = 0;
305 a0d146ed 2005-07-12 devnull return ie;
309 a0d146ed 2005-07-12 devnull icachedirty(u32int lo, u32int hi, u64int limit)
312 a0d146ed 2005-07-12 devnull u32int h;
313 a0d146ed 2005-07-12 devnull IEntry *ie, *dirty;
315 a0d146ed 2005-07-12 devnull dirty = nil;
316 a0d146ed 2005-07-12 devnull trace(TraceProc, "icachedirty enter");
317 a0d146ed 2005-07-12 devnull qlock(&icache.lock);
318 a0d146ed 2005-07-12 devnull for(i=0; i<icache.size; i++)
319 a0d146ed 2005-07-12 devnull for(ie = icache.heads[i]; ie; ie=ie->next)
320 a0d146ed 2005-07-12 devnull if(ie->dirty && ie->ia.addr != 0 && ie->ia.addr < limit){
321 a0d146ed 2005-07-12 devnull h = hashbits(ie->score, 32);
322 a0d146ed 2005-07-12 devnull if(lo <= h && h <= hi){
323 a0d146ed 2005-07-12 devnull ie->nextdirty = dirty;
324 a0d146ed 2005-07-12 devnull dirty = ie;
327 a0d146ed 2005-07-12 devnull qunlock(&icache.lock);
328 a0d146ed 2005-07-12 devnull trace(TraceProc, "icachedirty exit");
329 a0d146ed 2005-07-12 devnull if(dirty == nil)
330 a0d146ed 2005-07-12 devnull flushdcache();
331 a0d146ed 2005-07-12 devnull return dirty;
335 a0d146ed 2005-07-12 devnull icacheclean(IEntry *ie)
337 a0d146ed 2005-07-12 devnull trace(TraceProc, "icachedirty enter");
338 a0d146ed 2005-07-12 devnull qlock(&icache.lock);
339 a0d146ed 2005-07-12 devnull for(; ie; ie=ie->nextdirty){
340 a0d146ed 2005-07-12 devnull icache.ndirty--;
341 a0d146ed 2005-07-12 devnull ie->dirty = 0;
343 a0d146ed 2005-07-12 devnull setstat(StatIcacheDirty, icache.ndirty);
344 a0d146ed 2005-07-12 devnull rwakeupall(&icache.full);
345 a0d146ed 2005-07-12 devnull qunlock(&icache.lock);
346 a0d146ed 2005-07-12 devnull trace(TraceProc, "icachedirty exit");