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