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*
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*
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
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
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*
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*
134 poplast(volatile IEntry *list)
135 {
136 	if(list->prev == list)
137 		return nil;
138 	return popout(list->prev);
139 }
140 
141 static IEntry*
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*
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
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*
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
222 scachehit(u64int addr)
223 {
224 	scachelookup(addr);	/* for move-to-front */
225 }
226 
227 static void
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
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*
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
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*
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
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
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
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
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
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
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*
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
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
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
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 }