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