1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
2 7a4ee46d 2003-11-23 devnull #include "dat.h"
3 7a4ee46d 2003-11-23 devnull #include "fns.h"
5 7a4ee46d 2003-11-23 devnull typedef struct LumpCache LumpCache;
9 7a4ee46d 2003-11-23 devnull HashLog = 9,
10 7a4ee46d 2003-11-23 devnull HashSize = 1<<HashLog,
11 7a4ee46d 2003-11-23 devnull HashMask = HashSize - 1,
14 7a4ee46d 2003-11-23 devnull struct LumpCache
16 7a4ee46d 2003-11-23 devnull QLock lock;
17 7a4ee46d 2003-11-23 devnull Rendez full;
18 7a4ee46d 2003-11-23 devnull Lump *free; /* list of available lumps */
19 7a4ee46d 2003-11-23 devnull u32int allowed; /* total allowable space for packets */
20 7a4ee46d 2003-11-23 devnull u32int avail; /* remaining space for packets */
21 7a4ee46d 2003-11-23 devnull u32int now; /* ticks for usage timestamps */
22 7a4ee46d 2003-11-23 devnull Lump **heads; /* hash table for finding address */
23 7a4ee46d 2003-11-23 devnull int nheap; /* number of available victims */
24 7a4ee46d 2003-11-23 devnull Lump **heap; /* heap for locating victims */
25 7a4ee46d 2003-11-23 devnull int nblocks; /* number of blocks allocated */
26 7a4ee46d 2003-11-23 devnull Lump *blocks; /* array of block descriptors */
29 7a4ee46d 2003-11-23 devnull static LumpCache lumpcache;
31 7a4ee46d 2003-11-23 devnull static void delheap(Lump *db);
32 7a4ee46d 2003-11-23 devnull static int downheap(int i, Lump *b);
33 7a4ee46d 2003-11-23 devnull static void fixheap(int i, Lump *b);
34 7a4ee46d 2003-11-23 devnull static int upheap(int i, Lump *b);
35 7a4ee46d 2003-11-23 devnull static Lump *bumplump(void);
38 7a4ee46d 2003-11-23 devnull initlumpcache(u32int size, u32int nblocks)
40 7a4ee46d 2003-11-23 devnull Lump *last, *b;
43 7a4ee46d 2003-11-23 devnull lumpcache.full.l = &lumpcache.lock;
44 7a4ee46d 2003-11-23 devnull lumpcache.nblocks = nblocks;
45 7a4ee46d 2003-11-23 devnull lumpcache.allowed = size;
46 7a4ee46d 2003-11-23 devnull lumpcache.avail = size;
47 7a4ee46d 2003-11-23 devnull lumpcache.heads = MKNZ(Lump*, HashSize);
48 7a4ee46d 2003-11-23 devnull lumpcache.heap = MKNZ(Lump*, nblocks);
49 7a4ee46d 2003-11-23 devnull lumpcache.blocks = MKNZ(Lump, nblocks);
51 7a4ee46d 2003-11-23 devnull last = nil;
52 7a4ee46d 2003-11-23 devnull for(i = 0; i < nblocks; i++){
53 7a4ee46d 2003-11-23 devnull b = &lumpcache.blocks[i];
54 7a4ee46d 2003-11-23 devnull b->type = TWID8;
55 7a4ee46d 2003-11-23 devnull b->heap = TWID32;
56 7a4ee46d 2003-11-23 devnull b->next = last;
57 7a4ee46d 2003-11-23 devnull last = b;
59 7a4ee46d 2003-11-23 devnull lumpcache.free = last;
60 7a4ee46d 2003-11-23 devnull lumpcache.nheap = 0;
64 7a4ee46d 2003-11-23 devnull lookuplump(u8int *score, int type)
67 7a4ee46d 2003-11-23 devnull u32int h;
69 7a4ee46d 2003-11-23 devnull h = hashbits(score, HashLog);
72 7a4ee46d 2003-11-23 devnull * look for the block in the cache
74 7a4ee46d 2003-11-23 devnull //checklumpcache();
75 7a4ee46d 2003-11-23 devnull qlock(&lumpcache.lock);
77 7a4ee46d 2003-11-23 devnull for(b = lumpcache.heads[h]; b != nil; b = b->next){
78 7a4ee46d 2003-11-23 devnull if(scorecmp(score, b->score)==0 && type == b->type){
79 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
80 7a4ee46d 2003-11-23 devnull stats.lumphit++;
81 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
82 7a4ee46d 2003-11-23 devnull goto found;
87 7a4ee46d 2003-11-23 devnull * missed: locate the block with the oldest second to last use.
88 7a4ee46d 2003-11-23 devnull * remove it from the heap, and fix up the heap.
90 7a4ee46d 2003-11-23 devnull while(lumpcache.free == nil){
91 7a4ee46d 2003-11-23 devnull if(bumplump() == nil){
92 7a4ee46d 2003-11-23 devnull logerr(EAdmin, "all lump cache blocks in use");
93 7a4ee46d 2003-11-23 devnull rsleep(&lumpcache.full);
94 7a4ee46d 2003-11-23 devnull goto again;
97 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
98 7a4ee46d 2003-11-23 devnull stats.lumpmiss++;
99 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
101 7a4ee46d 2003-11-23 devnull b = lumpcache.free;
102 7a4ee46d 2003-11-23 devnull lumpcache.free = b->next;
105 7a4ee46d 2003-11-23 devnull * the new block has no last use, so assume it happens sometime in the middle
106 7a4ee46d 2003-11-23 devnull ZZZ this is not reasonable
108 7a4ee46d 2003-11-23 devnull b->used = (b->used2 + lumpcache.now) / 2;
111 7a4ee46d 2003-11-23 devnull * rechain the block on the correct hash chain
113 7a4ee46d 2003-11-23 devnull b->next = lumpcache.heads[h];
114 7a4ee46d 2003-11-23 devnull lumpcache.heads[h] = b;
115 7a4ee46d 2003-11-23 devnull if(b->next != nil)
116 7a4ee46d 2003-11-23 devnull b->next->prev = b;
117 7a4ee46d 2003-11-23 devnull b->prev = nil;
119 7a4ee46d 2003-11-23 devnull scorecp(b->score, score);
120 7a4ee46d 2003-11-23 devnull b->type = type;
121 7a4ee46d 2003-11-23 devnull b->size = 0;
122 7a4ee46d 2003-11-23 devnull b->data = nil;
125 7a4ee46d 2003-11-23 devnull b->ref++;
126 7a4ee46d 2003-11-23 devnull b->used2 = b->used;
127 7a4ee46d 2003-11-23 devnull b->used = lumpcache.now++;
128 7a4ee46d 2003-11-23 devnull if(b->heap != TWID32)
129 7a4ee46d 2003-11-23 devnull fixheap(b->heap, b);
130 7a4ee46d 2003-11-23 devnull qunlock(&lumpcache.lock);
132 7a4ee46d 2003-11-23 devnull //checklumpcache();
134 7a4ee46d 2003-11-23 devnull qlock(&b->lock);
136 7a4ee46d 2003-11-23 devnull return b;
140 7a4ee46d 2003-11-23 devnull insertlump(Lump *b, Packet *p)
142 7a4ee46d 2003-11-23 devnull u32int size;
145 7a4ee46d 2003-11-23 devnull * look for the block in the cache
147 7a4ee46d 2003-11-23 devnull //checklumpcache();
148 7a4ee46d 2003-11-23 devnull qlock(&lumpcache.lock);
152 7a4ee46d 2003-11-23 devnull * missed: locate the block with the oldest second to last use.
153 7a4ee46d 2003-11-23 devnull * remove it from the heap, and fix up the heap.
155 7a4ee46d 2003-11-23 devnull size = packetasize(p);
157 7a4ee46d 2003-11-23 devnull while(lumpcache.avail < size){
158 7a4ee46d 2003-11-23 devnull if(bumplump() == nil){
159 7a4ee46d 2003-11-23 devnull logerr(EAdmin, "all lump cache blocks in use");
160 7a4ee46d 2003-11-23 devnull rsleep(&lumpcache.full);
161 7a4ee46d 2003-11-23 devnull goto again;
164 7a4ee46d 2003-11-23 devnull b->data = p;
165 7a4ee46d 2003-11-23 devnull b->size = size;
166 7a4ee46d 2003-11-23 devnull lumpcache.avail -= size;
168 7a4ee46d 2003-11-23 devnull qunlock(&lumpcache.lock);
169 7a4ee46d 2003-11-23 devnull //checklumpcache();
173 7a4ee46d 2003-11-23 devnull putlump(Lump *b)
175 7a4ee46d 2003-11-23 devnull if(b == nil)
178 7a4ee46d 2003-11-23 devnull qunlock(&b->lock);
179 7a4ee46d 2003-11-23 devnull //checklumpcache();
180 7a4ee46d 2003-11-23 devnull qlock(&lumpcache.lock);
181 7a4ee46d 2003-11-23 devnull if(--b->ref == 0){
182 7a4ee46d 2003-11-23 devnull if(b->heap == TWID32)
183 7a4ee46d 2003-11-23 devnull upheap(lumpcache.nheap++, b);
184 7a4ee46d 2003-11-23 devnull rwakeup(&lumpcache.full);
187 7a4ee46d 2003-11-23 devnull qunlock(&lumpcache.lock);
188 7a4ee46d 2003-11-23 devnull //checklumpcache();
192 7a4ee46d 2003-11-23 devnull * remove some lump from use and update the free list and counters
194 7a4ee46d 2003-11-23 devnull static Lump*
195 7a4ee46d 2003-11-23 devnull bumplump(void)
197 7a4ee46d 2003-11-23 devnull Lump *b;
198 7a4ee46d 2003-11-23 devnull u32int h;
201 7a4ee46d 2003-11-23 devnull * remove blocks until we find one that is unused
202 7a4ee46d 2003-11-23 devnull * referenced blocks are left in the heap even though
203 7a4ee46d 2003-11-23 devnull * they can't be scavenged; this is simple a speed optimization
205 7a4ee46d 2003-11-23 devnull for(;;){
206 7a4ee46d 2003-11-23 devnull if(lumpcache.nheap == 0)
207 7a4ee46d 2003-11-23 devnull return nil;
208 7a4ee46d 2003-11-23 devnull b = lumpcache.heap[0];
209 7a4ee46d 2003-11-23 devnull delheap(b);
210 7a4ee46d 2003-11-23 devnull if(!b->ref){
211 7a4ee46d 2003-11-23 devnull rwakeup(&lumpcache.full);
217 7a4ee46d 2003-11-23 devnull * unchain the block
219 7a4ee46d 2003-11-23 devnull if(b->prev == nil){
220 7a4ee46d 2003-11-23 devnull h = hashbits(b->score, HashLog);
221 7a4ee46d 2003-11-23 devnull if(lumpcache.heads[h] != b)
222 7a4ee46d 2003-11-23 devnull sysfatal("bad hash chains in lump cache");
223 7a4ee46d 2003-11-23 devnull lumpcache.heads[h] = b->next;
225 7a4ee46d 2003-11-23 devnull b->prev->next = b->next;
226 7a4ee46d 2003-11-23 devnull if(b->next != nil)
227 7a4ee46d 2003-11-23 devnull b->next->prev = b->prev;
229 7a4ee46d 2003-11-23 devnull if(b->data != nil){
230 7a4ee46d 2003-11-23 devnull packetfree(b->data);
231 7a4ee46d 2003-11-23 devnull b->data = nil;
232 7a4ee46d 2003-11-23 devnull lumpcache.avail += b->size;
233 7a4ee46d 2003-11-23 devnull b->size = 0;
235 7a4ee46d 2003-11-23 devnull b->type = TWID8;
237 7a4ee46d 2003-11-23 devnull b->next = lumpcache.free;
238 7a4ee46d 2003-11-23 devnull lumpcache.free = b;
240 7a4ee46d 2003-11-23 devnull return b;
244 7a4ee46d 2003-11-23 devnull * delete an arbitrary block from the heap
246 7a4ee46d 2003-11-23 devnull static void
247 7a4ee46d 2003-11-23 devnull delheap(Lump *db)
249 7a4ee46d 2003-11-23 devnull fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
250 7a4ee46d 2003-11-23 devnull db->heap = TWID32;
254 7a4ee46d 2003-11-23 devnull * push an element up or down to it's correct new location
256 7a4ee46d 2003-11-23 devnull static void
257 7a4ee46d 2003-11-23 devnull fixheap(int i, Lump *b)
259 7a4ee46d 2003-11-23 devnull if(upheap(i, b) == i)
260 7a4ee46d 2003-11-23 devnull downheap(i, b);
263 7a4ee46d 2003-11-23 devnull static int
264 7a4ee46d 2003-11-23 devnull upheap(int i, Lump *b)
266 7a4ee46d 2003-11-23 devnull Lump *bb;
267 7a4ee46d 2003-11-23 devnull u32int now;
270 7a4ee46d 2003-11-23 devnull now = lumpcache.now;
271 7a4ee46d 2003-11-23 devnull for(; i != 0; i = p){
272 7a4ee46d 2003-11-23 devnull p = (i - 1) >> 1;
273 7a4ee46d 2003-11-23 devnull bb = lumpcache.heap[p];
274 7a4ee46d 2003-11-23 devnull if(b->used2 - now >= bb->used2 - now)
276 7a4ee46d 2003-11-23 devnull lumpcache.heap[i] = bb;
277 7a4ee46d 2003-11-23 devnull bb->heap = i;
280 7a4ee46d 2003-11-23 devnull lumpcache.heap[i] = b;
281 7a4ee46d 2003-11-23 devnull b->heap = i;
282 7a4ee46d 2003-11-23 devnull return i;
285 7a4ee46d 2003-11-23 devnull static int
286 7a4ee46d 2003-11-23 devnull downheap(int i, Lump *b)
288 7a4ee46d 2003-11-23 devnull Lump *bb;
289 7a4ee46d 2003-11-23 devnull u32int now;
292 7a4ee46d 2003-11-23 devnull now = lumpcache.now;
293 7a4ee46d 2003-11-23 devnull for(; ; i = k){
294 7a4ee46d 2003-11-23 devnull k = (i << 1) + 1;
295 7a4ee46d 2003-11-23 devnull if(k >= lumpcache.nheap)
297 7a4ee46d 2003-11-23 devnull if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
299 7a4ee46d 2003-11-23 devnull bb = lumpcache.heap[k];
300 7a4ee46d 2003-11-23 devnull if(b->used2 - now <= bb->used2 - now)
302 7a4ee46d 2003-11-23 devnull lumpcache.heap[i] = bb;
303 7a4ee46d 2003-11-23 devnull bb->heap = i;
306 7a4ee46d 2003-11-23 devnull lumpcache.heap[i] = b;
307 7a4ee46d 2003-11-23 devnull b->heap = i;
308 7a4ee46d 2003-11-23 devnull return i;
311 7a4ee46d 2003-11-23 devnull static void
312 7a4ee46d 2003-11-23 devnull findblock(Lump *bb)
314 7a4ee46d 2003-11-23 devnull Lump *b, *last;
317 7a4ee46d 2003-11-23 devnull last = nil;
318 7a4ee46d 2003-11-23 devnull h = hashbits(bb->score, HashLog);
319 7a4ee46d 2003-11-23 devnull for(b = lumpcache.heads[h]; b != nil; b = b->next){
320 7a4ee46d 2003-11-23 devnull if(last != b->prev)
321 7a4ee46d 2003-11-23 devnull sysfatal("bad prev link");
322 7a4ee46d 2003-11-23 devnull if(b == bb)
324 7a4ee46d 2003-11-23 devnull last = b;
326 7a4ee46d 2003-11-23 devnull sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
330 7a4ee46d 2003-11-23 devnull checklumpcache(void)
332 7a4ee46d 2003-11-23 devnull Lump *b;
333 7a4ee46d 2003-11-23 devnull u32int size, now, nfree;
334 7a4ee46d 2003-11-23 devnull int i, k, refed;
336 7a4ee46d 2003-11-23 devnull qlock(&lumpcache.lock);
337 7a4ee46d 2003-11-23 devnull now = lumpcache.now;
338 7a4ee46d 2003-11-23 devnull for(i = 0; i < lumpcache.nheap; i++){
339 7a4ee46d 2003-11-23 devnull if(lumpcache.heap[i]->heap != i)
340 7a4ee46d 2003-11-23 devnull sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
341 7a4ee46d 2003-11-23 devnull if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
342 7a4ee46d 2003-11-23 devnull sysfatal("lc: bad heap ordering");
343 7a4ee46d 2003-11-23 devnull k = (i << 1) + 1;
344 7a4ee46d 2003-11-23 devnull if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
345 7a4ee46d 2003-11-23 devnull sysfatal("lc: bad heap ordering");
347 7a4ee46d 2003-11-23 devnull if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
348 7a4ee46d 2003-11-23 devnull sysfatal("lc: bad heap ordering");
351 7a4ee46d 2003-11-23 devnull refed = 0;
352 7a4ee46d 2003-11-23 devnull size = 0;
353 7a4ee46d 2003-11-23 devnull for(i = 0; i < lumpcache.nblocks; i++){
354 7a4ee46d 2003-11-23 devnull b = &lumpcache.blocks[i];
355 7a4ee46d 2003-11-23 devnull if(b->data == nil && b->size != 0)
356 7a4ee46d 2003-11-23 devnull sysfatal("bad size: %d data=%p", b->size, b->data);
357 7a4ee46d 2003-11-23 devnull if(b->ref && b->heap == TWID32)
358 7a4ee46d 2003-11-23 devnull refed++;
359 7a4ee46d 2003-11-23 devnull if(b->type != TWID8){
360 7a4ee46d 2003-11-23 devnull findblock(b);
361 7a4ee46d 2003-11-23 devnull size += b->size;
363 7a4ee46d 2003-11-23 devnull if(b->heap != TWID32
364 7a4ee46d 2003-11-23 devnull && lumpcache.heap[b->heap] != b)
365 7a4ee46d 2003-11-23 devnull sysfatal("lc: spurious heap value");
367 7a4ee46d 2003-11-23 devnull if(lumpcache.avail != lumpcache.allowed - size)
368 7a4ee46d 2003-11-23 devnull sysfatal("mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
370 7a4ee46d 2003-11-23 devnull nfree = 0;
371 7a4ee46d 2003-11-23 devnull for(b = lumpcache.free; b != nil; b = b->next){
372 7a4ee46d 2003-11-23 devnull if(b->type != TWID8 || b->heap != TWID32)
373 7a4ee46d 2003-11-23 devnull sysfatal("lc: bad free list");
374 7a4ee46d 2003-11-23 devnull nfree++;
377 7a4ee46d 2003-11-23 devnull if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
378 7a4ee46d 2003-11-23 devnull sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
379 7a4ee46d 2003-11-23 devnull qunlock(&lumpcache.lock);