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