5 typedef struct LumpCache LumpCache;
10 HashSize = 1<<HashLog,
11 HashMask = HashSize - 1,
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 */
29 static LumpCache lumpcache;
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);
38 initlumpcache(u32int size, u32int nblocks)
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);
52 for(i = 0; i < nblocks; i++){
53 b = &lumpcache.blocks[i];
59 lumpcache.free = last;
64 lookuplump(u8int *score, int type)
69 h = hashbits(score, HashLog);
72 * look for the block in the cache
75 qlock(&lumpcache.lock);
77 for(b = lumpcache.heads[h]; b != nil; b = b->next){
78 if(scorecmp(score, b->score)==0 && type == b->type){
87 * missed: locate the block with the oldest second to last use.
88 * remove it from the heap, and fix up the heap.
90 while(lumpcache.free == nil){
91 if(bumplump() == nil){
92 logerr(EAdmin, "all lump cache blocks in use");
93 rsleep(&lumpcache.full);
102 lumpcache.free = b->next;
105 * the new block has no last use, so assume it happens sometime in the middle
106 ZZZ this is not reasonable
108 b->used = (b->used2 + lumpcache.now) / 2;
111 * rechain the block on the correct hash chain
113 b->next = lumpcache.heads[h];
114 lumpcache.heads[h] = b;
119 scorecp(b->score, score);
127 b->used = lumpcache.now++;
128 if(b->heap != TWID32)
130 qunlock(&lumpcache.lock);
140 insertlump(Lump *b, Packet *p)
145 * look for the block in the cache
148 qlock(&lumpcache.lock);
152 * missed: locate the block with the oldest second to last use.
153 * remove it from the heap, and fix up the heap.
155 size = packetasize(p);
157 while(lumpcache.avail < size){
158 if(bumplump() == nil){
159 logerr(EAdmin, "all lump cache blocks in use");
160 rsleep(&lumpcache.full);
166 lumpcache.avail -= size;
168 qunlock(&lumpcache.lock);
180 qlock(&lumpcache.lock);
182 if(b->heap == TWID32)
183 upheap(lumpcache.nheap++, b);
184 rwakeup(&lumpcache.full);
187 qunlock(&lumpcache.lock);
192 * remove some lump from use and update the free list and counters
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
206 if(lumpcache.nheap == 0)
208 b = lumpcache.heap[0];
211 rwakeup(&lumpcache.full);
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;
225 b->prev->next = b->next;
227 b->next->prev = b->prev;
232 lumpcache.avail += b->size;
237 b->next = lumpcache.free;
244 * delete an arbitrary block from the heap
249 fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
254 * push an element up or down to it's correct new location
257 fixheap(int i, Lump *b)
259 if(upheap(i, b) == i)
264 upheap(int i, Lump *b)
271 for(; i != 0; i = p){
273 bb = lumpcache.heap[p];
274 if(b->used2 - now >= bb->used2 - now)
276 lumpcache.heap[i] = bb;
280 lumpcache.heap[i] = b;
286 downheap(int i, Lump *b)
295 if(k >= lumpcache.nheap)
297 if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
299 bb = lumpcache.heap[k];
300 if(b->used2 - now <= bb->used2 - now)
302 lumpcache.heap[i] = bb;
306 lumpcache.heap[i] = b;
318 h = hashbits(bb->score, HashLog);
319 for(b = lumpcache.heads[h]; b != nil; b = b->next){
321 sysfatal("bad prev link");
326 sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
333 u32int size, now, nfree;
336 qlock(&lumpcache.lock);
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");
344 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
345 sysfatal("lc: bad heap ordering");
347 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
348 sysfatal("lc: bad heap ordering");
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)
359 if(b->type != TWID8){
364 && lumpcache.heap[b->heap] != b)
365 sysfatal("lc: spurious heap value");
367 if(lumpcache.avail != lumpcache.allowed - size)
368 sysfatal("mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
371 for(b = lumpcache.free; b != nil; b = b->next){
372 if(b->type != TWID8 || b->heap != TWID32)
373 sysfatal("lc: bad free list");
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);