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