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)+size*sizeof(ih->table[0]));
72 	ih->table = (IEntry**)(ih+1);
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 	qlock(&icache.lock);
391 	addstat(StatIcacheLookup, 1);
392 	if((ie = ihashlookup(icache.hash, score, type)) != nil){
393 		*ia = ie->ia;
394 		if(ie->state == IEClean)
395 			pushfirst(&icache.clean, ie);
396 		addstat(StatIcacheHit, 1);
397 		qunlock(&icache.lock);
398 		return 0;
399 	}
400 
401 	if((ie = ihashlookup(icache.shash, score, type)) != nil){
402 		*ia = ie->ia;
403 		icacheinsert(score, &ie->ia, IEClean);
404 		scachehit(ie->ia.addr);
405 		addstat(StatScacheHit, 1);
406 		qunlock(&icache.lock);
407 		return 0;
408 	}
409 	addstat(StatIcacheMiss, 1);
410 	qunlock(&icache.lock);
411 
412 	return -1;
413 }
414 
415 int
416 insertscore(u8int score[VtScoreSize], IAddr *ia, int state, AState *as)
417 {
418 	ISum *toload;
419 
420 	qlock(&icache.lock);
421 	icacheinsert(score, ia, state);
422 	if(state == IEClean)
423 		toload = scachemiss(ia->addr);
424 	else{
425 		assert(state == IEDirty);
426 		toload = nil;
427 		if(as == nil)
428 			fprint(2, "%T insertscore IEDirty without as; called from %lux\n", getcallerpc(&score));
429 		else{
430 			if(icache.as.aa > as->aa)
431 				fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa);
432 			icache.as = *as;
433 		}
434 	}
435 	qunlock(&icache.lock);
436 	if(toload){
437 		scacheload(toload);
438 		qunlock(&toload->lock);
439 	}
440 	
441 	if(icache.ndirty >= icache.maxdirty)
442 		kickicache();
443 
444 	/*
445 	 * It's okay not to do this under icache.lock.
446 	 * Calling insertscore only happens when we hold
447 	 * the lump, meaning any searches for this block
448 	 * will hit in the lump cache until after we return.
449 	 */
450 	if(state == IEDirty)
451 		markbloomfilter(mainindex->bloom, score);
452 
453 	return 0;
454 }
455 
456 int
457 lookupscore(u8int score[VtScoreSize], int type, IAddr *ia)
458 {
459 	int ms, ret;
460 	IEntry d;
461 
462 	if(icachelookup(score, type, ia) >= 0){
463 		addstat(StatIcacheRead, 1);
464 		return 0;
465 	}
466 
467 	ms = msec();
468 	addstat(StatIcacheFill, 1);
469 	if(loadientry(mainindex, score, type, &d) < 0)
470 		ret = -1;
471 	else{
472 		ret = 0;
473 		insertscore(score, &d.ia, IEClean, nil);
474 		*ia = d.ia;
475 	}
476 	addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms);
477 	return ret;
478 }
479 	
480 u32int
481 hashbits(u8int *sc, int bits)
482 {
483 	u32int v;
484 
485 	v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
486 	if(bits < 32)
487 		 v >>= (32 - bits);
488 	return v;
489 }
490 
491 ulong
492 icachedirtyfrac(void)
493 {
494 	return (vlong)icache.ndirty*IcacheFrac / icache.nentries;
495 }
496 
497 /*
498  * Return a singly-linked list of dirty index entries.
499  * with 32-bit hash numbers between lo and hi
500  * and address < limit.
501  */
502 IEntry*
503 icachedirty(u32int lo, u32int hi, u64int limit)
504 {
505 	u32int h;
506 	IEntry *ie, *dirty;
507 
508 	dirty = nil;
509 	trace(TraceProc, "icachedirty enter");
510 	qlock(&icache.lock);
511 	for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){
512 		if(ie->state == IEDirty && ie->ia.addr <= limit){
513 			h = hashbits(ie->score, 32);
514 			if(lo <= h && h <= hi){
515 				ie->nextdirty = dirty;
516 				dirty = ie;
517 			}
518 		}
519 	}
520 	qunlock(&icache.lock);
521 	trace(TraceProc, "icachedirty exit");
522 	if(dirty == nil)
523 		flushdcache();
524 	return dirty;
525 }
526 
527 AState
528 icachestate(void)
529 {
530 	AState as;
531 
532 	qlock(&icache.lock);
533 	as = icache.as;
534 	qunlock(&icache.lock);
535 	return as;
536 }
537 
538 /*
539  * The singly-linked non-circular list of index entries ie
540  * has been written to disk.  Move them to the clean list.
541  */
542 void
543 icacheclean(IEntry *ie)
544 {
545 	IEntry *next;
546 	
547 	trace(TraceProc, "icacheclean enter");
548 	qlock(&icache.lock);
549 	for(; ie; ie=next){
550 		assert(ie->state == IEDirty);
551 		next = ie->nextdirty;
552 		ie->nextdirty = nil;
553 		popout(ie); /* from icache.dirty */
554 		icache.ndirty--;
555 		ie->state = IEClean;
556 		pushfirst(&icache.clean, ie);
557 	}
558 	setstat(StatIcacheDirty, icache.ndirty);
559 	rwakeupall(&icache.full);
560 	qunlock(&icache.lock);
561 	trace(TraceProc, "icacheclean exit");
562 }
563 
564 void
565 emptyicache(void)
566 {
567 	int i;
568 	IEntry *ie;
569 	ISum *s;
570 	
571 	qlock(&icache.lock);
572 	while((ie = evictlru()) != nil)
573 		pushfirst(&icache.free, ie);
574 	for(i=0; i<icache.nsum; i++){
575 		s = icache.sum[i];
576 		qlock(&s->lock);
577 		sumclear(s);
578 		qunlock(&s->lock);
579 	}
580 	qunlock(&icache.lock);
581 }
582