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