1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4
5 int icacheprefetch = 1;
6
7 typedef struct ICache ICache;
8 typedef struct IHash IHash;
9 typedef struct ISum ISum;
10
11 struct ICache
12 {
13 QLock lock;
14 Rendez full;
15 IHash *hash;
16 IEntry *entries;
17 int nentries;
18 IEntry free;
19 IEntry clean;
20 IEntry dirty;
21 u32int maxdirty;
22 u32int ndirty;
23 AState as;
24
25 ISum **sum;
26 int nsum;
27 IHash *shash;
28 IEntry *sentries;
29 int nsentries;
30 };
31
32 static ICache icache;
33
34 /*
35 * Hash table of IEntries
36 */
37
38 struct IHash
39 {
40 int bits;
41 u32int size;
42 IEntry **table;
43 };
44
45 static IHash*
mkihash(int size1)46 mkihash(int size1)
47 {
48 u32int size;
49 int bits;
50 IHash *ih;
51
52 bits = 0;
53 size = 1;
54 while(size < size1){
55 bits++;
56 size <<= 1;
57 }
58
59 ih = vtmallocz(sizeof(IHash)+size*sizeof(ih->table[0]));
60 ih->table = (IEntry**)(ih+1);
61 ih->bits = bits;
62 ih->size = size;
63 return ih;
64 }
65
66 static IEntry*
ihashlookup(IHash * ih,u8int score[VtScoreSize],int type)67 ihashlookup(IHash *ih, u8int score[VtScoreSize], int type)
68 {
69 u32int h;
70 IEntry *ie;
71
72 h = hashbits(score, ih->bits);
73 for(ie=ih->table[h]; ie; ie=ie->nexthash)
74 if((type == -1 || type == ie->ia.type) && scorecmp(score, ie->score) == 0)
75 return ie;
76 return nil;
77 }
78
79 static void
ihashdelete(IHash * ih,IEntry * ie,char * what)80 ihashdelete(IHash *ih, IEntry *ie, char *what)
81 {
82 u32int h;
83 IEntry **l;
84
85 h = hashbits(ie->score, ih->bits);
86 for(l=&ih->table[h]; *l; l=&(*l)->nexthash)
87 if(*l == ie){
88 *l = ie->nexthash;
89 return;
90 }
91 fprint(2, "warning: %s %V not found in ihashdelete\n", what, ie->score);
92 }
93
94 static void
ihashinsert(IHash * ih,IEntry * ie)95 ihashinsert(IHash *ih, IEntry *ie)
96 {
97 u32int h;
98
99 h = hashbits(ie->score, ih->bits);
100 ie->nexthash = ih->table[h];
101 ih->table[h] = ie;
102 }
103
104
105 /*
106 * IEntry lists.
107 */
108
109 static IEntry*
popout(IEntry * ie)110 popout(IEntry *ie)
111 {
112 if(ie->prev == nil && ie->next == nil)
113 return ie;
114 ie->prev->next = ie->next;
115 ie->next->prev = ie->prev;
116 ie->next = nil;
117 ie->prev = nil;
118 return ie;
119 }
120
121 static IEntry*
poplast(IEntry * list)122 poplast(IEntry *list)
123 {
124 if(list->prev == list)
125 return nil;
126 return popout(list->prev);
127 }
128
129 static IEntry*
pushfirst(IEntry * list,IEntry * ie)130 pushfirst(IEntry *list, IEntry *ie)
131 {
132 popout(ie);
133 ie->prev = list;
134 ie->next = list->next;
135 ie->prev->next = ie;
136 ie->next->prev = ie;
137 return ie;
138 }
139
140 /*
141 * Arena summary cache.
142 */
143 struct ISum
144 {
145 QLock lock;
146 IEntry *entries;
147 int nentries;
148 int loaded;
149 u64int addr;
150 u64int limit;
151 Arena *arena;
152 int g;
153 };
154
155 static ISum*
scachelookup(u64int addr)156 scachelookup(u64int addr)
157 {
158 int i;
159 ISum *s;
160
161 for(i=0; i<icache.nsum; i++){
162 s = icache.sum[i];
163 if(s->addr <= addr && addr < s->limit){
164 if(i > 0){
165 memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
166 icache.sum[0] = s;
167 }
168 return s;
169 }
170 }
171 return nil;
172 }
173
174 static void
sumclear(ISum * s)175 sumclear(ISum *s)
176 {
177 int i;
178
179 for(i=0; i<s->nentries; i++)
180 ihashdelete(icache.shash, &s->entries[i], "scache");
181 s->nentries = 0;
182 s->loaded = 0;
183 s->addr = 0;
184 s->limit = 0;
185 s->arena = nil;
186 s->g = 0;
187 }
188
189 static ISum*
scacheevict(void)190 scacheevict(void)
191 {
192 ISum *s;
193 int i;
194
195 for(i=icache.nsum-1; i>=0; i--){
196 s = icache.sum[i];
197 if(canqlock(&s->lock)){
198 if(i > 0){
199 memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
200 icache.sum[0] = s;
201 }
202 sumclear(s);
203 return s;
204 }
205 }
206 return nil;
207 }
208
209 static void
scachehit(u64int addr)210 scachehit(u64int addr)
211 {
212 scachelookup(addr); /* for move-to-front */
213 }
214
215 static void
scachesetup(ISum * s,u64int addr)216 scachesetup(ISum *s, u64int addr)
217 {
218 u64int addr0, limit;
219 int g;
220
221 s->arena = amapitoag(mainindex, addr, &addr0, &limit, &g);
222 s->addr = addr0;
223 s->limit = limit;
224 s->g = g;
225 }
226
227 static void
scacheload(ISum * s)228 scacheload(ISum *s)
229 {
230 int i, n;
231
232 s->loaded = 1;
233 n = asumload(s->arena, s->g, s->entries, ArenaCIGSize);
234 /*
235 * n can be less then ArenaCIGSize, either if the clump group
236 * is the last in the arena and is only partially filled, or if there
237 * are corrupt clumps in the group -- those are not returned.
238 */
239 for(i=0; i<n; i++){
240 s->entries[i].ia.addr += s->addr;
241 ihashinsert(icache.shash, &s->entries[i]);
242 }
243 //fprint(2, "%T scacheload %s %d - %d entries\n", s->arena->name, s->g, n);
244 addstat(StatScachePrefetch, n);
245 s->nentries = n;
246 }
247
248 static ISum*
scachemiss(u64int addr)249 scachemiss(u64int addr)
250 {
251 ISum *s;
252
253 if(!icacheprefetch)
254 return nil;
255 s = scachelookup(addr);
256 if(s == nil){
257 /* first time: make an entry in the cache but don't populate it yet */
258 s = scacheevict();
259 if(s == nil)
260 return nil;
261 scachesetup(s, addr);
262 qunlock(&s->lock);
263 return nil;
264 }
265
266 /* second time: load from disk */
267 qlock(&s->lock);
268 if(s->loaded || !icacheprefetch){
269 qunlock(&s->lock);
270 return nil;
271 }
272
273 return s; /* locked */
274 }
275
276 /*
277 * Index cache.
278 */
279
280 void
initicache(u32int mem0)281 initicache(u32int mem0)
282 {
283 u32int mem;
284 int i, entries, scache;
285
286 icache.full.l = &icache.lock;
287
288 mem = mem0;
289 entries = mem / (sizeof(IEntry)+sizeof(IEntry*));
290 scache = (entries/8) / ArenaCIGSize;
291 entries -= entries/8;
292 if(scache < 4)
293 scache = 4;
294 if(scache > 16)
295 scache = 16;
296 if(entries < 1000)
297 entries = 1000;
298 fprint(2, "icache %,d bytes = %,d entries; %d scache\n", mem0, entries, scache);
299
300 icache.clean.prev = icache.clean.next = &icache.clean;
301 icache.dirty.prev = icache.dirty.next = &icache.dirty;
302 icache.free.prev = icache.free.next = &icache.free;
303
304 icache.hash = mkihash(entries);
305 icache.nentries = entries;
306 setstat(StatIcacheSize, entries);
307 icache.entries = vtmallocz(entries*sizeof icache.entries[0]);
308 icache.maxdirty = entries / 2;
309 for(i=0; i<entries; i++)
310 pushfirst(&icache.free, &icache.entries[i]);
311
312 icache.nsum = scache;
313 icache.sum = vtmallocz(scache*sizeof icache.sum[0]);
314 icache.sum[0] = vtmallocz(scache*sizeof icache.sum[0][0]);
315 icache.nsentries = scache * ArenaCIGSize;
316 icache.sentries = vtmallocz(scache*ArenaCIGSize*sizeof icache.sentries[0]);
317 icache.shash = mkihash(scache*ArenaCIGSize);
318 for(i=0; i<scache; i++){
319 icache.sum[i] = icache.sum[0] + i;
320 icache.sum[i]->entries = icache.sentries + i*ArenaCIGSize;
321 }
322 }
323
324
325 static IEntry*
evictlru(void)326 evictlru(void)
327 {
328 IEntry *ie;
329
330 ie = poplast(&icache.clean);
331 if(ie == nil)
332 return nil;
333 ihashdelete(icache.hash, ie, "evictlru");
334 return ie;
335 }
336
337 static void
icacheinsert(u8int score[VtScoreSize],IAddr * ia,int state)338 icacheinsert(u8int score[VtScoreSize], IAddr *ia, int state)
339 {
340 IEntry *ie;
341
342 if((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
343 addstat(StatIcacheStall, 1);
344 while((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
345 // Could safely return here if state == IEClean.
346 // But if state == IEDirty, have to wait to make
347 // sure we don't lose an index write.
348 // Let's wait all the time.
349 flushdcache();
350 kickicache();
351 rsleep(&icache.full);
352 }
353 addstat(StatIcacheStall, -1);
354 }
355
356 memmove(ie->score, score, VtScoreSize);
357 ie->state = state;
358 ie->ia = *ia;
359 if(state == IEClean){
360 addstat(StatIcachePrefetch, 1);
361 pushfirst(&icache.clean, ie);
362 }else{
363 addstat(StatIcacheWrite, 1);
364 assert(state == IEDirty);
365 icache.ndirty++;
366 setstat(StatIcacheDirty, icache.ndirty);
367 delaykickicache();
368 pushfirst(&icache.dirty, ie);
369 }
370 ihashinsert(icache.hash, ie);
371 }
372
373 int
icachelookup(u8int score[VtScoreSize],int type,IAddr * ia)374 icachelookup(u8int score[VtScoreSize], int type, IAddr *ia)
375 {
376 IEntry *ie;
377
378 qlock(&icache.lock);
379 addstat(StatIcacheLookup, 1);
380 if((ie = ihashlookup(icache.hash, score, type)) != nil){
381 *ia = ie->ia;
382 if(ie->state == IEClean)
383 pushfirst(&icache.clean, ie);
384 addstat(StatIcacheHit, 1);
385 qunlock(&icache.lock);
386 return 0;
387 }
388
389 if((ie = ihashlookup(icache.shash, score, type)) != nil){
390 *ia = ie->ia;
391 icacheinsert(score, &ie->ia, IEClean);
392 scachehit(ie->ia.addr);
393 addstat(StatScacheHit, 1);
394 qunlock(&icache.lock);
395 return 0;
396 }
397 addstat(StatIcacheMiss, 1);
398 qunlock(&icache.lock);
399
400 return -1;
401 }
402
403 int
insertscore(u8int score[VtScoreSize],IAddr * ia,int state,AState * as)404 insertscore(u8int score[VtScoreSize], IAddr *ia, int state, AState *as)
405 {
406 ISum *toload;
407
408 qlock(&icache.lock);
409 icacheinsert(score, ia, state);
410 if(state == IEClean)
411 toload = scachemiss(ia->addr);
412 else{
413 assert(state == IEDirty);
414 toload = nil;
415 if(as == nil)
416 fprint(2, "%T insertscore IEDirty without as; called from %#p\n",
417 getcallerpc(&score));
418 else{
419 if(icache.as.aa > as->aa)
420 fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa);
421 icache.as = *as;
422 }
423 }
424 qunlock(&icache.lock);
425 if(toload){
426 scacheload(toload);
427 qunlock(&toload->lock);
428 }
429
430 if(icache.ndirty >= icache.maxdirty)
431 kickicache();
432
433 /*
434 * It's okay not to do this under icache.lock.
435 * Calling insertscore only happens when we hold
436 * the lump, meaning any searches for this block
437 * will hit in the lump cache until after we return.
438 */
439 if(state == IEDirty)
440 markbloomfilter(mainindex->bloom, score);
441
442 return 0;
443 }
444
445 int
lookupscore(u8int score[VtScoreSize],int type,IAddr * ia)446 lookupscore(u8int score[VtScoreSize], int type, IAddr *ia)
447 {
448 int ms, ret;
449 IEntry d;
450
451 if(icachelookup(score, type, ia) >= 0){
452 addstat(StatIcacheRead, 1);
453 return 0;
454 }
455
456 ms = msec();
457 addstat(StatIcacheFill, 1);
458 if(loadientry(mainindex, score, type, &d) < 0)
459 ret = -1;
460 else{
461 ret = 0;
462 insertscore(score, &d.ia, IEClean, nil);
463 *ia = d.ia;
464 }
465 addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms);
466 return ret;
467 }
468
469 u32int
hashbits(u8int * sc,int bits)470 hashbits(u8int *sc, int bits)
471 {
472 u32int v;
473
474 v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
475 if(bits < 32)
476 v >>= (32 - bits);
477 return v;
478 }
479
480 ulong
icachedirtyfrac(void)481 icachedirtyfrac(void)
482 {
483 return (vlong)icache.ndirty*IcacheFrac / icache.nentries;
484 }
485
486 /*
487 * Return a singly-linked list of dirty index entries.
488 * with 32-bit hash numbers between lo and hi
489 * and address < limit.
490 */
491 IEntry*
icachedirty(u32int lo,u32int hi,u64int limit)492 icachedirty(u32int lo, u32int hi, u64int limit)
493 {
494 u32int h;
495 IEntry *ie, *dirty;
496
497 dirty = nil;
498 trace(TraceProc, "icachedirty enter");
499 qlock(&icache.lock);
500 for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){
501 if(ie->state == IEDirty && ie->ia.addr <= limit){
502 h = hashbits(ie->score, 32);
503 if(lo <= h && h <= hi){
504 ie->nextdirty = dirty;
505 dirty = ie;
506 }
507 }
508 }
509 qunlock(&icache.lock);
510 trace(TraceProc, "icachedirty exit");
511 if(dirty == nil)
512 flushdcache();
513 return dirty;
514 }
515
516 AState
icachestate(void)517 icachestate(void)
518 {
519 AState as;
520
521 qlock(&icache.lock);
522 as = icache.as;
523 qunlock(&icache.lock);
524 return as;
525 }
526
527 /*
528 * The singly-linked non-circular list of index entries ie
529 * has been written to disk. Move them to the clean list.
530 */
531 void
icacheclean(IEntry * ie)532 icacheclean(IEntry *ie)
533 {
534 IEntry *next;
535
536 trace(TraceProc, "icacheclean enter");
537 qlock(&icache.lock);
538 for(; ie; ie=next){
539 assert(ie->state == IEDirty);
540 next = ie->nextdirty;
541 ie->nextdirty = nil;
542 popout(ie); /* from icache.dirty */
543 icache.ndirty--;
544 ie->state = IEClean;
545 pushfirst(&icache.clean, ie);
546 }
547 setstat(StatIcacheDirty, icache.ndirty);
548 rwakeupall(&icache.full);
549 qunlock(&icache.lock);
550 trace(TraceProc, "icacheclean exit");
551 }
552
553 void
emptyicache(void)554 emptyicache(void)
555 {
556 int i;
557 IEntry *ie;
558 ISum *s;
559
560 qlock(&icache.lock);
561 while((ie = evictlru()) != nil)
562 pushfirst(&icache.free, ie);
563 for(i=0; i<icache.nsum; i++){
564 s = icache.sum[i];
565 qlock(&s->lock);
566 sumclear(s);
567 qunlock(&s->lock);
568 }
569 qunlock(&icache.lock);
570 }
571
572