1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 
5 /* #define CHECK(x)	x */
6 #define CHECK(x)
7 
8 typedef struct LumpCache	LumpCache;
9 
10 enum
11 {
12 	HashLog		= 9,
13 	HashSize	= 1<<HashLog,
14 	HashMask	= HashSize - 1,
15 };
16 
17 struct LumpCache
18 {
19 	QLock		lock;
20 	Rendez		full;
21 	Lump		*free;			/* list of available lumps */
22 	u32int		allowed;		/* total allowable space for packets */
23 	u32int		avail;			/* remaining space for packets */
24 	u32int		now;			/* ticks for usage timestamps */
25 	Lump		**heads;		/* hash table for finding address */
26 	int		nheap;			/* number of available victims */
27 	Lump		**heap;			/* heap for locating victims */
28 	int		nblocks;		/* number of blocks allocated */
29 	Lump		*blocks;		/* array of block descriptors */
30 };
31 
32 static LumpCache	lumpcache;
33 
34 static void	delheap(Lump *db);
35 static int	downheap(int i, Lump *b);
36 static void	fixheap(int i, Lump *b);
37 static int	upheap(int i, Lump *b);
38 static Lump	*bumplump(void);
39 
40 void
41 initlumpcache(u32int size, u32int nblocks)
42 {
43 	Lump *last, *b;
44 	int i;
45 
46 	lumpcache.full.l = &lumpcache.lock;
47 	lumpcache.nblocks = nblocks;
48 	lumpcache.allowed = size;
49 	lumpcache.avail = size;
50 	lumpcache.heads = MKNZ(Lump*, HashSize);
51 	lumpcache.heap = MKNZ(Lump*, nblocks);
52 	lumpcache.blocks = MKNZ(Lump, nblocks);
53 	setstat(StatLcacheSize, lumpcache.nblocks);
54 
55 	last = nil;
56 	for(i = 0; i < nblocks; i++){
57 		b = &lumpcache.blocks[i];
58 		b->type = TWID8;
59 		b->heap = TWID32;
60 		b->next = last;
61 		last = b;
62 	}
63 	lumpcache.free = last;
64 	lumpcache.nheap = 0;
65 }
66 
67 Lump*
68 lookuplump(u8int *score, int type)
69 {
70 	uint ms;
71 	Lump *b;
72 	u32int h;
73 
74 	ms = 0;
75 	trace(TraceLump, "lookuplump enter");
76 
77 	h = hashbits(score, HashLog);
78 
79 	/*
80 	 * look for the block in the cache
81 	 */
82 	qlock(&lumpcache.lock);
83 	CHECK(checklumpcache());
84 again:
85 	for(b = lumpcache.heads[h]; b != nil; b = b->next){
86 		if(scorecmp(score, b->score)==0 && type == b->type){
87 			addstat(StatLcacheHit, 1);
88 			trace(TraceLump, "lookuplump hit");
89 			goto found;
90 		}
91 	}
92 
93 	trace(TraceLump, "lookuplump miss");
94 
95 	/*
96 	 * missed: locate the block with the oldest second to last use.
97 	 * remove it from the heap, and fix up the heap.
98 	 */
99 	while(lumpcache.free == nil){
100 		trace(TraceLump, "lookuplump bump");
101 		CHECK(checklumpcache());
102 		if(bumplump() == nil){
103 			CHECK(checklumpcache());
104 			logerr(EAdmin, "all lump cache blocks in use");
105 			addstat(StatLcacheStall, 1);
106 			CHECK(checklumpcache());
107 			rsleep(&lumpcache.full);
108 			CHECK(checklumpcache());
109 			addstat(StatLcacheStall, -1);
110 			goto again;
111 		}
112 		CHECK(checklumpcache());
113 	}
114 
115 	/* start timer on cache miss to avoid system call on cache hit */
116 	ms = msec();
117 
118 	addstat(StatLcacheMiss, 1);
119 	b = lumpcache.free;
120 	lumpcache.free = b->next;
121 
122 	/*
123 	 * the new block has no last use, so assume it happens sometime in the middle
124 ZZZ this is not reasonable
125 	 */
126 	b->used = (b->used2 + lumpcache.now) / 2;
127 
128 	/*
129 	 * rechain the block on the correct hash chain
130 	 */
131 	b->next = lumpcache.heads[h];
132 	lumpcache.heads[h] = b;
133 	if(b->next != nil)
134 		b->next->prev = b;
135 	b->prev = nil;
136 
137 	scorecp(b->score, score);
138 	b->type = type;
139 	b->size = 0;
140 	b->data = nil;
141 
142 found:
143 	b->ref++;
144 	b->used2 = b->used;
145 	b->used = lumpcache.now++;
146 	if(b->heap != TWID32)
147 		fixheap(b->heap, b);
148 	CHECK(checklumpcache());
149 	qunlock(&lumpcache.lock);
150 
151 
152 	addstat(StatLumpStall, 1);
153 	qlock(&b->lock);
154 	addstat(StatLumpStall, -1);
155 
156 	trace(TraceLump, "lookuplump exit");
157 	addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0);
158 	return b;
159 }
160 
161 void
162 insertlump(Lump *b, Packet *p)
163 {
164 	u32int size;
165 
166 	/*
167 	 * look for the block in the cache
168 	 */
169 	trace(TraceLump, "insertlump enter");
170 	qlock(&lumpcache.lock);
171 	CHECK(checklumpcache());
172 again:
173 
174 	addstat(StatLcacheWrite, 1);
175 
176 	/*
177 	 * missed: locate the block with the oldest second to last use.
178 	 * remove it from the heap, and fix up the heap.
179 	 */
180 	size = packetasize(p);
181 	while(lumpcache.avail < size){
182 		trace(TraceLump, "insertlump bump");
183 		CHECK(checklumpcache());
184 		if(bumplump() == nil){
185 			logerr(EAdmin, "all lump cache blocks in use");
186 			addstat(StatLcacheStall, 1);
187 			CHECK(checklumpcache());
188 			rsleep(&lumpcache.full);
189 			CHECK(checklumpcache());
190 			addstat(StatLcacheStall, -1);
191 			goto again;
192 		}
193 		CHECK(checklumpcache());
194 	}
195 	b->data = p;
196 	b->size = size;
197 	lumpcache.avail -= size;
198 	CHECK(checklumpcache());
199 	qunlock(&lumpcache.lock);
200 	trace(TraceLump, "insertlump exit");
201 }
202 
203 void
204 putlump(Lump *b)
205 {
206 	if(b == nil)
207 		return;
208 
209 	trace(TraceLump, "putlump");
210 	qunlock(&b->lock);
211 	qlock(&lumpcache.lock);
212 	CHECK(checklumpcache());
213 	if(--b->ref == 0){
214 		if(b->heap == TWID32)
215 			upheap(lumpcache.nheap++, b);
216 		trace(TraceLump, "putlump wakeup");
217 		rwakeupall(&lumpcache.full);
218 	}
219 	CHECK(checklumpcache());
220 	qunlock(&lumpcache.lock);
221 }
222 
223 /*
224  * remove some lump from use and update the free list and counters
225  */
226 static Lump*
227 bumplump(void)
228 {
229 	Lump *b;
230 	u32int h;
231 
232 	/*
233 	 * remove blocks until we find one that is unused
234 	 * referenced blocks are left in the heap even though
235 	 * they can't be scavenged; this is simple a speed optimization
236 	 */
237 	CHECK(checklumpcache());
238 	for(;;){
239 		if(lumpcache.nheap == 0){
240 			trace(TraceLump, "bumplump emptyheap");
241 			return nil;
242 		}
243 		b = lumpcache.heap[0];
244 		delheap(b);
245 		if(!b->ref){
246 			trace(TraceLump, "bumplump wakeup");
247 			rwakeupall(&lumpcache.full);
248 			break;
249 		}
250 	}
251 
252 	/*
253 	 * unchain the block
254 	 */
255 	trace(TraceLump, "bumplump unchain");
256 	if(b->prev == nil){
257 		h = hashbits(b->score, HashLog);
258 		if(lumpcache.heads[h] != b)
259 			sysfatal("bad hash chains in lump cache");
260 		lumpcache.heads[h] = b->next;
261 	}else
262 		b->prev->next = b->next;
263 	if(b->next != nil)
264 		b->next->prev = b->prev;
265 
266 	if(b->data != nil){
267 		packetfree(b->data);
268 		b->data = nil;
269 		lumpcache.avail += b->size;
270 		b->size = 0;
271 	}
272 	b->type = TWID8;
273 
274 	b->next = lumpcache.free;
275 	lumpcache.free = b;
276 
277 	CHECK(checklumpcache());
278 	trace(TraceLump, "bumplump exit");
279 	return b;
280 }
281 
282 void
283 emptylumpcache(void)
284 {
285 	qlock(&lumpcache.lock);
286 	while(bumplump())
287 		;
288 	qunlock(&lumpcache.lock);
289 }
290 
291 /*
292  * delete an arbitrary block from the heap
293  */
294 static void
295 delheap(Lump *db)
296 {
297 	fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
298 	db->heap = TWID32;
299 }
300 
301 /*
302  * push an element up or down to it's correct new location
303  */
304 static void
305 fixheap(int i, Lump *b)
306 {
307 	if(upheap(i, b) == i)
308 		downheap(i, b);
309 }
310 
311 static int
312 upheap(int i, Lump *b)
313 {
314 	Lump *bb;
315 	u32int now;
316 	int p;
317 
318 	now = lumpcache.now;
319 	for(; i != 0; i = p){
320 		p = (i - 1) >> 1;
321 		bb = lumpcache.heap[p];
322 		if(b->used2 - now >= bb->used2 - now)
323 			break;
324 		lumpcache.heap[i] = bb;
325 		bb->heap = i;
326 	}
327 
328 	lumpcache.heap[i] = b;
329 	b->heap = i;
330 	return i;
331 }
332 
333 static int
334 downheap(int i, Lump *b)
335 {
336 	Lump *bb;
337 	u32int now;
338 	int k;
339 
340 	now = lumpcache.now;
341 	for(; ; i = k){
342 		k = (i << 1) + 1;
343 		if(k >= lumpcache.nheap)
344 			break;
345 		if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
346 			k++;
347 		bb = lumpcache.heap[k];
348 		if(b->used2 - now <= bb->used2 - now)
349 			break;
350 		lumpcache.heap[i] = bb;
351 		bb->heap = i;
352 	}
353 
354 	lumpcache.heap[i] = b;
355 	b->heap = i;
356 	return i;
357 }
358 
359 static void
360 findblock(Lump *bb)
361 {
362 	Lump *b, *last;
363 	int h;
364 
365 	last = nil;
366 	h = hashbits(bb->score, HashLog);
367 	for(b = lumpcache.heads[h]; b != nil; b = b->next){
368 		if(last != b->prev)
369 			sysfatal("bad prev link");
370 		if(b == bb)
371 			return;
372 		last = b;
373 	}
374 	sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
375 }
376 
377 void
378 checklumpcache(void)
379 {
380 	Lump *b;
381 	u32int size, now, nfree;
382 	int i, k, refed;
383 
384 	now = lumpcache.now;
385 	for(i = 0; i < lumpcache.nheap; i++){
386 		if(lumpcache.heap[i]->heap != i)
387 			sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
388 		if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
389 			sysfatal("lc: bad heap ordering");
390 		k = (i << 1) + 1;
391 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
392 			sysfatal("lc: bad heap ordering");
393 		k++;
394 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
395 			sysfatal("lc: bad heap ordering");
396 	}
397 
398 	refed = 0;
399 	size = 0;
400 	for(i = 0; i < lumpcache.nblocks; i++){
401 		b = &lumpcache.blocks[i];
402 		if(b->data == nil && b->size != 0)
403 			sysfatal("bad size: %d data=%p", b->size, b->data);
404 		if(b->ref && b->heap == TWID32)
405 			refed++;
406 		if(b->type != TWID8){
407 			findblock(b);
408 			size += b->size;
409 		}
410 		if(b->heap != TWID32
411 		&& lumpcache.heap[b->heap] != b)
412 			sysfatal("lc: spurious heap value");
413 	}
414 	if(lumpcache.avail != lumpcache.allowed - size){
415 		fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
416 		*(volatile int*)0=0;
417 	}
418 
419 	nfree = 0;
420 	for(b = lumpcache.free; b != nil; b = b->next){
421 		if(b->type != TWID8 || b->heap != TWID32)
422 			sysfatal("lc: bad free list");
423 		nfree++;
424 	}
425 
426 	if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
427 		sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
428 }