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
initlumpcache(u32int size,u32int nblocks)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*
lookuplump(u8int * score,int type)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
insertlump(Lump * b,Packet * p)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
putlump(Lump * b)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*
bumplump(void)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
emptylumpcache(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
delheap(Lump * db)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
fixheap(int i,Lump * b)305 fixheap(int i, Lump *b)
306 {
307 if(upheap(i, b) == i)
308 downheap(i, b);
309 }
310
311 static int
upheap(int i,Lump * b)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
downheap(int i,Lump * b)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
findblock(Lump * bb)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
checklumpcache(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 }
429