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 = msec();
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 	addstat(StatLcacheMiss, 1);
116 	b = lumpcache.free;
117 	lumpcache.free = b->next;
118 
119 	/*
120 	 * the new block has no last use, so assume it happens sometime in the middle
121 ZZZ this is not reasonable
122 	 */
123 	b->used = (b->used2 + lumpcache.now) / 2;
124 
125 	/*
126 	 * rechain the block on the correct hash chain
127 	 */
128 	b->next = lumpcache.heads[h];
129 	lumpcache.heads[h] = b;
130 	if(b->next != nil)
131 		b->next->prev = b;
132 	b->prev = nil;
133 
134 	scorecp(b->score, score);
135 	b->type = type;
136 	b->size = 0;
137 	b->data = nil;
138 
139 found:
140 	b->ref++;
141 	b->used2 = b->used;
142 	b->used = lumpcache.now++;
143 	if(b->heap != TWID32)
144 		fixheap(b->heap, b);
145 	CHECK(checklumpcache());
146 	qunlock(&lumpcache.lock);
147 
148 
149 	addstat(StatLumpStall, 1);
150 	qlock(&b->lock);
151 	addstat(StatLumpStall, -1);
152 
153 	trace(TraceLump, "lookuplump exit");
154 	addstat2(StatLcacheRead, 1, StatLcacheReadTime, msec()-ms);
155 	return b;
156 }
157 
158 void
159 insertlump(Lump *b, Packet *p)
160 {
161 	u32int size;
162 
163 	/*
164 	 * look for the block in the cache
165 	 */
166 	trace(TraceLump, "insertlump enter");
167 	qlock(&lumpcache.lock);
168 	CHECK(checklumpcache());
169 again:
170 
171 	addstat(StatLcacheWrite, 1);
172 
173 	/*
174 	 * missed: locate the block with the oldest second to last use.
175 	 * remove it from the heap, and fix up the heap.
176 	 */
177 	size = packetasize(p);
178 //ZZZ
179 	while(lumpcache.avail < size){
180 		trace(TraceLump, "insertlump bump");
181 		CHECK(checklumpcache());
182 		if(bumplump() == nil){
183 			logerr(EAdmin, "all lump cache blocks in use");
184 			addstat(StatLcacheStall, 1);
185 			CHECK(checklumpcache());
186 			rsleep(&lumpcache.full);
187 			CHECK(checklumpcache());
188 			addstat(StatLcacheStall, -1);
189 			goto again;
190 		}
191 		CHECK(checklumpcache());
192 	}
193 	b->data = p;
194 	b->size = size;
195 	lumpcache.avail -= size;
196 	CHECK(checklumpcache());
197 	qunlock(&lumpcache.lock);
198 	trace(TraceLump, "insertlump exit");
199 }
200 
201 void
202 putlump(Lump *b)
203 {
204 	if(b == nil)
205 		return;
206 
207 	trace(TraceLump, "putlump");
208 	qunlock(&b->lock);
209 	qlock(&lumpcache.lock);
210 	CHECK(checklumpcache());
211 	if(--b->ref == 0){
212 		if(b->heap == TWID32)
213 			upheap(lumpcache.nheap++, b);
214 		trace(TraceLump, "putlump wakeup");
215 		rwakeupall(&lumpcache.full);
216 	}
217 	CHECK(checklumpcache());
218 	qunlock(&lumpcache.lock);
219 }
220 
221 /*
222  * remove some lump from use and update the free list and counters
223  */
224 static Lump*
225 bumplump(void)
226 {
227 	Lump *b;
228 	u32int h;
229 
230 	/*
231 	 * remove blocks until we find one that is unused
232 	 * referenced blocks are left in the heap even though
233 	 * they can't be scavenged; this is simple a speed optimization
234 	 */
235 	CHECK(checklumpcache());
236 	for(;;){
237 		if(lumpcache.nheap == 0){
238 			trace(TraceLump, "bumplump emptyheap");
239 			return nil;
240 		}
241 		b = lumpcache.heap[0];
242 		delheap(b);
243 		if(!b->ref){
244 			trace(TraceLump, "bumplump wakeup");
245 			rwakeupall(&lumpcache.full);
246 			break;
247 		}
248 	}
249 
250 	/*
251 	 * unchain the block
252 	 */
253 	trace(TraceLump, "bumplump unchain");
254 	if(b->prev == nil){
255 		h = hashbits(b->score, HashLog);
256 		if(lumpcache.heads[h] != b)
257 			sysfatal("bad hash chains in lump cache");
258 		lumpcache.heads[h] = b->next;
259 	}else
260 		b->prev->next = b->next;
261 	if(b->next != nil)
262 		b->next->prev = b->prev;
263 
264 	if(b->data != nil){
265 		packetfree(b->data);
266 		b->data = nil;
267 		lumpcache.avail += b->size;
268 		b->size = 0;
269 	}
270 	b->type = TWID8;
271 
272 	b->next = lumpcache.free;
273 	lumpcache.free = b;
274 
275 	CHECK(checklumpcache());
276 	trace(TraceLump, "bumplump exit");
277 	return b;
278 }
279 
280 /*
281  * delete an arbitrary block from the heap
282  */
283 static void
284 delheap(Lump *db)
285 {
286 	fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
287 	db->heap = TWID32;
288 }
289 
290 /*
291  * push an element up or down to it's correct new location
292  */
293 static void
294 fixheap(int i, Lump *b)
295 {
296 	if(upheap(i, b) == i)
297 		downheap(i, b);
298 }
299 
300 static int
301 upheap(int i, Lump *b)
302 {
303 	Lump *bb;
304 	u32int now;
305 	int p;
306 
307 	now = lumpcache.now;
308 	for(; i != 0; i = p){
309 		p = (i - 1) >> 1;
310 		bb = lumpcache.heap[p];
311 		if(b->used2 - now >= bb->used2 - now)
312 			break;
313 		lumpcache.heap[i] = bb;
314 		bb->heap = i;
315 	}
316 
317 	lumpcache.heap[i] = b;
318 	b->heap = i;
319 	return i;
320 }
321 
322 static int
323 downheap(int i, Lump *b)
324 {
325 	Lump *bb;
326 	u32int now;
327 	int k;
328 
329 	now = lumpcache.now;
330 	for(; ; i = k){
331 		k = (i << 1) + 1;
332 		if(k >= lumpcache.nheap)
333 			break;
334 		if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
335 			k++;
336 		bb = lumpcache.heap[k];
337 		if(b->used2 - now <= bb->used2 - now)
338 			break;
339 		lumpcache.heap[i] = bb;
340 		bb->heap = i;
341 	}
342 
343 	lumpcache.heap[i] = b;
344 	b->heap = i;
345 	return i;
346 }
347 
348 static void
349 findblock(Lump *bb)
350 {
351 	Lump *b, *last;
352 	int h;
353 
354 	last = nil;
355 	h = hashbits(bb->score, HashLog);
356 	for(b = lumpcache.heads[h]; b != nil; b = b->next){
357 		if(last != b->prev)
358 			sysfatal("bad prev link");
359 		if(b == bb)
360 			return;
361 		last = b;
362 	}
363 	sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
364 }
365 
366 void
367 checklumpcache(void)
368 {
369 	Lump *b;
370 	u32int size, now, nfree;
371 	int i, k, refed;
372 
373 	now = lumpcache.now;
374 	for(i = 0; i < lumpcache.nheap; i++){
375 		if(lumpcache.heap[i]->heap != i)
376 			sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
377 		if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
378 			sysfatal("lc: bad heap ordering");
379 		k = (i << 1) + 1;
380 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
381 			sysfatal("lc: bad heap ordering");
382 		k++;
383 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
384 			sysfatal("lc: bad heap ordering");
385 	}
386 
387 	refed = 0;
388 	size = 0;
389 	for(i = 0; i < lumpcache.nblocks; i++){
390 		b = &lumpcache.blocks[i];
391 		if(b->data == nil && b->size != 0)
392 			sysfatal("bad size: %d data=%p", b->size, b->data);
393 		if(b->ref && b->heap == TWID32)
394 			refed++;
395 		if(b->type != TWID8){
396 			findblock(b);
397 			size += b->size;
398 		}
399 		if(b->heap != TWID32
400 		&& lumpcache.heap[b->heap] != b)
401 			sysfatal("lc: spurious heap value");
402 	}
403 	if(lumpcache.avail != lumpcache.allowed - size){
404 		fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
405 		*(int*)0=0;
406 	}
407 
408 	nfree = 0;
409 	for(b = lumpcache.free; b != nil; b = b->next){
410 		if(b->type != TWID8 || b->heap != TWID32)
411 			sysfatal("lc: bad free list");
412 		nfree++;
413 	}
414 
415 	if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
416 		sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
417 }