5 /* #define CHECK(x) x */
8 typedef struct LumpCache LumpCache;
13 HashSize = 1<<HashLog,
14 HashMask = HashSize - 1,
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 */
32 static LumpCache lumpcache;
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);
41 initlumpcache(u32int size, u32int nblocks)
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);
56 for(i = 0; i < nblocks; i++){
57 b = &lumpcache.blocks[i];
63 lumpcache.free = last;
68 lookuplump(u8int *score, int type)
75 trace(TraceLump, "lookuplump enter");
77 h = hashbits(score, HashLog);
80 * look for the block in the cache
82 qlock(&lumpcache.lock);
83 CHECK(checklumpcache());
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");
93 trace(TraceLump, "lookuplump miss");
96 * missed: locate the block with the oldest second to last use.
97 * remove it from the heap, and fix up the heap.
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);
112 CHECK(checklumpcache());
115 addstat(StatLcacheMiss, 1);
117 lumpcache.free = b->next;
120 * the new block has no last use, so assume it happens sometime in the middle
121 ZZZ this is not reasonable
123 b->used = (b->used2 + lumpcache.now) / 2;
126 * rechain the block on the correct hash chain
128 b->next = lumpcache.heads[h];
129 lumpcache.heads[h] = b;
134 scorecp(b->score, score);
142 b->used = lumpcache.now++;
143 if(b->heap != TWID32)
145 CHECK(checklumpcache());
146 qunlock(&lumpcache.lock);
149 addstat(StatLumpStall, 1);
151 addstat(StatLumpStall, -1);
153 trace(TraceLump, "lookuplump exit");
154 addstat2(StatLcacheRead, 1, StatLcacheReadTime, msec()-ms);
159 insertlump(Lump *b, Packet *p)
164 * look for the block in the cache
166 trace(TraceLump, "insertlump enter");
167 qlock(&lumpcache.lock);
168 CHECK(checklumpcache());
171 addstat(StatLcacheWrite, 1);
174 * missed: locate the block with the oldest second to last use.
175 * remove it from the heap, and fix up the heap.
177 size = packetasize(p);
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);
191 CHECK(checklumpcache());
195 lumpcache.avail -= size;
196 CHECK(checklumpcache());
197 qunlock(&lumpcache.lock);
198 trace(TraceLump, "insertlump exit");
207 trace(TraceLump, "putlump");
209 qlock(&lumpcache.lock);
210 CHECK(checklumpcache());
212 if(b->heap == TWID32)
213 upheap(lumpcache.nheap++, b);
214 trace(TraceLump, "putlump wakeup");
215 rwakeupall(&lumpcache.full);
217 CHECK(checklumpcache());
218 qunlock(&lumpcache.lock);
222 * remove some lump from use and update the free list and counters
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
235 CHECK(checklumpcache());
237 if(lumpcache.nheap == 0){
238 trace(TraceLump, "bumplump emptyheap");
241 b = lumpcache.heap[0];
244 trace(TraceLump, "bumplump wakeup");
245 rwakeupall(&lumpcache.full);
253 trace(TraceLump, "bumplump unchain");
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;
260 b->prev->next = b->next;
262 b->next->prev = b->prev;
267 lumpcache.avail += b->size;
272 b->next = lumpcache.free;
275 CHECK(checklumpcache());
276 trace(TraceLump, "bumplump exit");
281 * delete an arbitrary block from the heap
286 fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
291 * push an element up or down to it's correct new location
294 fixheap(int i, Lump *b)
296 if(upheap(i, b) == i)
301 upheap(int i, Lump *b)
308 for(; i != 0; i = p){
310 bb = lumpcache.heap[p];
311 if(b->used2 - now >= bb->used2 - now)
313 lumpcache.heap[i] = bb;
317 lumpcache.heap[i] = b;
323 downheap(int i, Lump *b)
332 if(k >= lumpcache.nheap)
334 if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
336 bb = lumpcache.heap[k];
337 if(b->used2 - now <= bb->used2 - now)
339 lumpcache.heap[i] = bb;
343 lumpcache.heap[i] = b;
355 h = hashbits(bb->score, HashLog);
356 for(b = lumpcache.heads[h]; b != nil; b = b->next){
358 sysfatal("bad prev link");
363 sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
370 u32int size, now, nfree;
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");
380 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
381 sysfatal("lc: bad heap ordering");
383 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
384 sysfatal("lc: bad heap ordering");
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)
395 if(b->type != TWID8){
400 && lumpcache.heap[b->heap] != b)
401 sysfatal("lc: spurious heap value");
403 if(lumpcache.avail != lumpcache.allowed - size){
404 fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
409 for(b = lumpcache.free; b != nil; b = b->next){
410 if(b->type != TWID8 || b->heap != TWID32)
411 sysfatal("lc: bad free list");
415 if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
416 sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);