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 28b49df3 2006-07-18 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 54dd92be 2008-01-30 rsc 	ms = 0;
 75 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "lookuplump enter");
 76 fa325e9b 2020-01-10 cross 
 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 54dd92be 2008-01-30 rsc 	/* start timer on cache miss to avoid system call on cache hit */
116 54dd92be 2008-01-30 rsc 	ms = msec();
117 54dd92be 2008-01-30 rsc 
118 a0d146ed 2005-07-12 devnull 	addstat(StatLcacheMiss, 1);
119 a0d146ed 2005-07-12 devnull 	b = lumpcache.free;
120 a0d146ed 2005-07-12 devnull 	lumpcache.free = b->next;
121 a0d146ed 2005-07-12 devnull 
122 a0d146ed 2005-07-12 devnull 	/*
123 a0d146ed 2005-07-12 devnull 	 * the new block has no last use, so assume it happens sometime in the middle
124 a0d146ed 2005-07-12 devnull ZZZ this is not reasonable
125 a0d146ed 2005-07-12 devnull 	 */
126 a0d146ed 2005-07-12 devnull 	b->used = (b->used2 + lumpcache.now) / 2;
127 a0d146ed 2005-07-12 devnull 
128 a0d146ed 2005-07-12 devnull 	/*
129 a0d146ed 2005-07-12 devnull 	 * rechain the block on the correct hash chain
130 a0d146ed 2005-07-12 devnull 	 */
131 a0d146ed 2005-07-12 devnull 	b->next = lumpcache.heads[h];
132 a0d146ed 2005-07-12 devnull 	lumpcache.heads[h] = b;
133 a0d146ed 2005-07-12 devnull 	if(b->next != nil)
134 a0d146ed 2005-07-12 devnull 		b->next->prev = b;
135 a0d146ed 2005-07-12 devnull 	b->prev = nil;
136 a0d146ed 2005-07-12 devnull 
137 a0d146ed 2005-07-12 devnull 	scorecp(b->score, score);
138 a0d146ed 2005-07-12 devnull 	b->type = type;
139 a0d146ed 2005-07-12 devnull 	b->size = 0;
140 a0d146ed 2005-07-12 devnull 	b->data = nil;
141 a0d146ed 2005-07-12 devnull 
142 a0d146ed 2005-07-12 devnull found:
143 a0d146ed 2005-07-12 devnull 	b->ref++;
144 a0d146ed 2005-07-12 devnull 	b->used2 = b->used;
145 a0d146ed 2005-07-12 devnull 	b->used = lumpcache.now++;
146 a0d146ed 2005-07-12 devnull 	if(b->heap != TWID32)
147 a0d146ed 2005-07-12 devnull 		fixheap(b->heap, b);
148 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
149 a0d146ed 2005-07-12 devnull 	qunlock(&lumpcache.lock);
150 a0d146ed 2005-07-12 devnull 
151 a0d146ed 2005-07-12 devnull 
152 a0d146ed 2005-07-12 devnull 	addstat(StatLumpStall, 1);
153 a0d146ed 2005-07-12 devnull 	qlock(&b->lock);
154 a0d146ed 2005-07-12 devnull 	addstat(StatLumpStall, -1);
155 a0d146ed 2005-07-12 devnull 
156 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "lookuplump exit");
157 54dd92be 2008-01-30 rsc 	addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0);
158 a0d146ed 2005-07-12 devnull 	return b;
159 a0d146ed 2005-07-12 devnull }
160 a0d146ed 2005-07-12 devnull 
161 a0d146ed 2005-07-12 devnull void
162 a0d146ed 2005-07-12 devnull insertlump(Lump *b, Packet *p)
163 a0d146ed 2005-07-12 devnull {
164 a0d146ed 2005-07-12 devnull 	u32int size;
165 a0d146ed 2005-07-12 devnull 
166 a0d146ed 2005-07-12 devnull 	/*
167 a0d146ed 2005-07-12 devnull 	 * look for the block in the cache
168 a0d146ed 2005-07-12 devnull 	 */
169 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "insertlump enter");
170 a0d146ed 2005-07-12 devnull 	qlock(&lumpcache.lock);
171 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
172 a0d146ed 2005-07-12 devnull again:
173 a0d146ed 2005-07-12 devnull 
174 a0d146ed 2005-07-12 devnull 	addstat(StatLcacheWrite, 1);
175 a0d146ed 2005-07-12 devnull 
176 a0d146ed 2005-07-12 devnull 	/*
177 a0d146ed 2005-07-12 devnull 	 * missed: locate the block with the oldest second to last use.
178 a0d146ed 2005-07-12 devnull 	 * remove it from the heap, and fix up the heap.
179 a0d146ed 2005-07-12 devnull 	 */
180 a0d146ed 2005-07-12 devnull 	size = packetasize(p);
181 a0d146ed 2005-07-12 devnull 	while(lumpcache.avail < size){
182 a0d146ed 2005-07-12 devnull 		trace(TraceLump, "insertlump bump");
183 a0d146ed 2005-07-12 devnull 		CHECK(checklumpcache());
184 a0d146ed 2005-07-12 devnull 		if(bumplump() == nil){
185 a0d146ed 2005-07-12 devnull 			logerr(EAdmin, "all lump cache blocks in use");
186 a0d146ed 2005-07-12 devnull 			addstat(StatLcacheStall, 1);
187 a0d146ed 2005-07-12 devnull 			CHECK(checklumpcache());
188 a0d146ed 2005-07-12 devnull 			rsleep(&lumpcache.full);
189 a0d146ed 2005-07-12 devnull 			CHECK(checklumpcache());
190 a0d146ed 2005-07-12 devnull 			addstat(StatLcacheStall, -1);
191 a0d146ed 2005-07-12 devnull 			goto again;
192 a0d146ed 2005-07-12 devnull 		}
193 a0d146ed 2005-07-12 devnull 		CHECK(checklumpcache());
194 a0d146ed 2005-07-12 devnull 	}
195 a0d146ed 2005-07-12 devnull 	b->data = p;
196 a0d146ed 2005-07-12 devnull 	b->size = size;
197 a0d146ed 2005-07-12 devnull 	lumpcache.avail -= size;
198 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
199 a0d146ed 2005-07-12 devnull 	qunlock(&lumpcache.lock);
200 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "insertlump exit");
201 a0d146ed 2005-07-12 devnull }
202 a0d146ed 2005-07-12 devnull 
203 a0d146ed 2005-07-12 devnull void
204 a0d146ed 2005-07-12 devnull putlump(Lump *b)
205 a0d146ed 2005-07-12 devnull {
206 a0d146ed 2005-07-12 devnull 	if(b == nil)
207 a0d146ed 2005-07-12 devnull 		return;
208 a0d146ed 2005-07-12 devnull 
209 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "putlump");
210 a0d146ed 2005-07-12 devnull 	qunlock(&b->lock);
211 a0d146ed 2005-07-12 devnull 	qlock(&lumpcache.lock);
212 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
213 a0d146ed 2005-07-12 devnull 	if(--b->ref == 0){
214 a0d146ed 2005-07-12 devnull 		if(b->heap == TWID32)
215 a0d146ed 2005-07-12 devnull 			upheap(lumpcache.nheap++, b);
216 a0d146ed 2005-07-12 devnull 		trace(TraceLump, "putlump wakeup");
217 a0d146ed 2005-07-12 devnull 		rwakeupall(&lumpcache.full);
218 a0d146ed 2005-07-12 devnull 	}
219 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
220 a0d146ed 2005-07-12 devnull 	qunlock(&lumpcache.lock);
221 a0d146ed 2005-07-12 devnull }
222 a0d146ed 2005-07-12 devnull 
223 a0d146ed 2005-07-12 devnull /*
224 a0d146ed 2005-07-12 devnull  * remove some lump from use and update the free list and counters
225 a0d146ed 2005-07-12 devnull  */
226 a0d146ed 2005-07-12 devnull static Lump*
227 a0d146ed 2005-07-12 devnull bumplump(void)
228 a0d146ed 2005-07-12 devnull {
229 a0d146ed 2005-07-12 devnull 	Lump *b;
230 a0d146ed 2005-07-12 devnull 	u32int h;
231 a0d146ed 2005-07-12 devnull 
232 a0d146ed 2005-07-12 devnull 	/*
233 a0d146ed 2005-07-12 devnull 	 * remove blocks until we find one that is unused
234 a0d146ed 2005-07-12 devnull 	 * referenced blocks are left in the heap even though
235 a0d146ed 2005-07-12 devnull 	 * they can't be scavenged; this is simple a speed optimization
236 a0d146ed 2005-07-12 devnull 	 */
237 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
238 a0d146ed 2005-07-12 devnull 	for(;;){
239 a0d146ed 2005-07-12 devnull 		if(lumpcache.nheap == 0){
240 a0d146ed 2005-07-12 devnull 			trace(TraceLump, "bumplump emptyheap");
241 a0d146ed 2005-07-12 devnull 			return nil;
242 a0d146ed 2005-07-12 devnull 		}
243 a0d146ed 2005-07-12 devnull 		b = lumpcache.heap[0];
244 a0d146ed 2005-07-12 devnull 		delheap(b);
245 a0d146ed 2005-07-12 devnull 		if(!b->ref){
246 a0d146ed 2005-07-12 devnull 			trace(TraceLump, "bumplump wakeup");
247 a0d146ed 2005-07-12 devnull 			rwakeupall(&lumpcache.full);
248 a0d146ed 2005-07-12 devnull 			break;
249 a0d146ed 2005-07-12 devnull 		}
250 a0d146ed 2005-07-12 devnull 	}
251 a0d146ed 2005-07-12 devnull 
252 a0d146ed 2005-07-12 devnull 	/*
253 a0d146ed 2005-07-12 devnull 	 * unchain the block
254 a0d146ed 2005-07-12 devnull 	 */
255 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "bumplump unchain");
256 a0d146ed 2005-07-12 devnull 	if(b->prev == nil){
257 a0d146ed 2005-07-12 devnull 		h = hashbits(b->score, HashLog);
258 a0d146ed 2005-07-12 devnull 		if(lumpcache.heads[h] != b)
259 a0d146ed 2005-07-12 devnull 			sysfatal("bad hash chains in lump cache");
260 a0d146ed 2005-07-12 devnull 		lumpcache.heads[h] = b->next;
261 a0d146ed 2005-07-12 devnull 	}else
262 a0d146ed 2005-07-12 devnull 		b->prev->next = b->next;
263 a0d146ed 2005-07-12 devnull 	if(b->next != nil)
264 a0d146ed 2005-07-12 devnull 		b->next->prev = b->prev;
265 a0d146ed 2005-07-12 devnull 
266 a0d146ed 2005-07-12 devnull 	if(b->data != nil){
267 a0d146ed 2005-07-12 devnull 		packetfree(b->data);
268 a0d146ed 2005-07-12 devnull 		b->data = nil;
269 a0d146ed 2005-07-12 devnull 		lumpcache.avail += b->size;
270 a0d146ed 2005-07-12 devnull 		b->size = 0;
271 a0d146ed 2005-07-12 devnull 	}
272 a0d146ed 2005-07-12 devnull 	b->type = TWID8;
273 a0d146ed 2005-07-12 devnull 
274 a0d146ed 2005-07-12 devnull 	b->next = lumpcache.free;
275 a0d146ed 2005-07-12 devnull 	lumpcache.free = b;
276 a0d146ed 2005-07-12 devnull 
277 a0d146ed 2005-07-12 devnull 	CHECK(checklumpcache());
278 a0d146ed 2005-07-12 devnull 	trace(TraceLump, "bumplump exit");
279 a0d146ed 2005-07-12 devnull 	return b;
280 a0d146ed 2005-07-12 devnull }
281 a0d146ed 2005-07-12 devnull 
282 28b49df3 2006-07-18 devnull void
283 28b49df3 2006-07-18 devnull emptylumpcache(void)
284 28b49df3 2006-07-18 devnull {
285 28b49df3 2006-07-18 devnull 	qlock(&lumpcache.lock);
286 28b49df3 2006-07-18 devnull 	while(bumplump())
287 28b49df3 2006-07-18 devnull 		;
288 28b49df3 2006-07-18 devnull 	qunlock(&lumpcache.lock);
289 28b49df3 2006-07-18 devnull }
290 28b49df3 2006-07-18 devnull 
291 a0d146ed 2005-07-12 devnull /*
292 a0d146ed 2005-07-12 devnull  * delete an arbitrary block from the heap
293 a0d146ed 2005-07-12 devnull  */
294 a0d146ed 2005-07-12 devnull static void
295 a0d146ed 2005-07-12 devnull delheap(Lump *db)
296 a0d146ed 2005-07-12 devnull {
297 a0d146ed 2005-07-12 devnull 	fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
298 a0d146ed 2005-07-12 devnull 	db->heap = TWID32;
299 a0d146ed 2005-07-12 devnull }
300 a0d146ed 2005-07-12 devnull 
301 a0d146ed 2005-07-12 devnull /*
302 a0d146ed 2005-07-12 devnull  * push an element up or down to it's correct new location
303 a0d146ed 2005-07-12 devnull  */
304 a0d146ed 2005-07-12 devnull static void
305 a0d146ed 2005-07-12 devnull fixheap(int i, Lump *b)
306 a0d146ed 2005-07-12 devnull {
307 a0d146ed 2005-07-12 devnull 	if(upheap(i, b) == i)
308 a0d146ed 2005-07-12 devnull 		downheap(i, b);
309 a0d146ed 2005-07-12 devnull }
310 a0d146ed 2005-07-12 devnull 
311 a0d146ed 2005-07-12 devnull static int
312 a0d146ed 2005-07-12 devnull upheap(int i, Lump *b)
313 a0d146ed 2005-07-12 devnull {
314 a0d146ed 2005-07-12 devnull 	Lump *bb;
315 a0d146ed 2005-07-12 devnull 	u32int now;
316 a0d146ed 2005-07-12 devnull 	int p;
317 a0d146ed 2005-07-12 devnull 
318 a0d146ed 2005-07-12 devnull 	now = lumpcache.now;
319 a0d146ed 2005-07-12 devnull 	for(; i != 0; i = p){
320 a0d146ed 2005-07-12 devnull 		p = (i - 1) >> 1;
321 a0d146ed 2005-07-12 devnull 		bb = lumpcache.heap[p];
322 a0d146ed 2005-07-12 devnull 		if(b->used2 - now >= bb->used2 - now)
323 a0d146ed 2005-07-12 devnull 			break;
324 a0d146ed 2005-07-12 devnull 		lumpcache.heap[i] = bb;
325 a0d146ed 2005-07-12 devnull 		bb->heap = i;
326 a0d146ed 2005-07-12 devnull 	}
327 a0d146ed 2005-07-12 devnull 
328 a0d146ed 2005-07-12 devnull 	lumpcache.heap[i] = b;
329 a0d146ed 2005-07-12 devnull 	b->heap = i;
330 a0d146ed 2005-07-12 devnull 	return i;
331 a0d146ed 2005-07-12 devnull }
332 a0d146ed 2005-07-12 devnull 
333 a0d146ed 2005-07-12 devnull static int
334 a0d146ed 2005-07-12 devnull downheap(int i, Lump *b)
335 a0d146ed 2005-07-12 devnull {
336 a0d146ed 2005-07-12 devnull 	Lump *bb;
337 a0d146ed 2005-07-12 devnull 	u32int now;
338 a0d146ed 2005-07-12 devnull 	int k;
339 a0d146ed 2005-07-12 devnull 
340 a0d146ed 2005-07-12 devnull 	now = lumpcache.now;
341 a0d146ed 2005-07-12 devnull 	for(; ; i = k){
342 a0d146ed 2005-07-12 devnull 		k = (i << 1) + 1;
343 a0d146ed 2005-07-12 devnull 		if(k >= lumpcache.nheap)
344 a0d146ed 2005-07-12 devnull 			break;
345 a0d146ed 2005-07-12 devnull 		if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
346 a0d146ed 2005-07-12 devnull 			k++;
347 a0d146ed 2005-07-12 devnull 		bb = lumpcache.heap[k];
348 a0d146ed 2005-07-12 devnull 		if(b->used2 - now <= bb->used2 - now)
349 a0d146ed 2005-07-12 devnull 			break;
350 a0d146ed 2005-07-12 devnull 		lumpcache.heap[i] = bb;
351 a0d146ed 2005-07-12 devnull 		bb->heap = i;
352 a0d146ed 2005-07-12 devnull 	}
353 a0d146ed 2005-07-12 devnull 
354 a0d146ed 2005-07-12 devnull 	lumpcache.heap[i] = b;
355 a0d146ed 2005-07-12 devnull 	b->heap = i;
356 a0d146ed 2005-07-12 devnull 	return i;
357 a0d146ed 2005-07-12 devnull }
358 a0d146ed 2005-07-12 devnull 
359 a0d146ed 2005-07-12 devnull static void
360 a0d146ed 2005-07-12 devnull findblock(Lump *bb)
361 a0d146ed 2005-07-12 devnull {
362 a0d146ed 2005-07-12 devnull 	Lump *b, *last;
363 a0d146ed 2005-07-12 devnull 	int h;
364 a0d146ed 2005-07-12 devnull 
365 a0d146ed 2005-07-12 devnull 	last = nil;
366 a0d146ed 2005-07-12 devnull 	h = hashbits(bb->score, HashLog);
367 a0d146ed 2005-07-12 devnull 	for(b = lumpcache.heads[h]; b != nil; b = b->next){
368 a0d146ed 2005-07-12 devnull 		if(last != b->prev)
369 a0d146ed 2005-07-12 devnull 			sysfatal("bad prev link");
370 a0d146ed 2005-07-12 devnull 		if(b == bb)
371 a0d146ed 2005-07-12 devnull 			return;
372 a0d146ed 2005-07-12 devnull 		last = b;
373 a0d146ed 2005-07-12 devnull 	}
374 a0d146ed 2005-07-12 devnull 	sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
375 a0d146ed 2005-07-12 devnull }
376 a0d146ed 2005-07-12 devnull 
377 a0d146ed 2005-07-12 devnull void
378 a0d146ed 2005-07-12 devnull checklumpcache(void)
379 a0d146ed 2005-07-12 devnull {
380 a0d146ed 2005-07-12 devnull 	Lump *b;
381 a0d146ed 2005-07-12 devnull 	u32int size, now, nfree;
382 a0d146ed 2005-07-12 devnull 	int i, k, refed;
383 a0d146ed 2005-07-12 devnull 
384 a0d146ed 2005-07-12 devnull 	now = lumpcache.now;
385 a0d146ed 2005-07-12 devnull 	for(i = 0; i < lumpcache.nheap; i++){
386 a0d146ed 2005-07-12 devnull 		if(lumpcache.heap[i]->heap != i)
387 a0d146ed 2005-07-12 devnull 			sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
388 a0d146ed 2005-07-12 devnull 		if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
389 a0d146ed 2005-07-12 devnull 			sysfatal("lc: bad heap ordering");
390 a0d146ed 2005-07-12 devnull 		k = (i << 1) + 1;
391 a0d146ed 2005-07-12 devnull 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
392 a0d146ed 2005-07-12 devnull 			sysfatal("lc: bad heap ordering");
393 a0d146ed 2005-07-12 devnull 		k++;
394 a0d146ed 2005-07-12 devnull 		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
395 a0d146ed 2005-07-12 devnull 			sysfatal("lc: bad heap ordering");
396 a0d146ed 2005-07-12 devnull 	}
397 a0d146ed 2005-07-12 devnull 
398 a0d146ed 2005-07-12 devnull 	refed = 0;
399 a0d146ed 2005-07-12 devnull 	size = 0;
400 a0d146ed 2005-07-12 devnull 	for(i = 0; i < lumpcache.nblocks; i++){
401 a0d146ed 2005-07-12 devnull 		b = &lumpcache.blocks[i];
402 a0d146ed 2005-07-12 devnull 		if(b->data == nil && b->size != 0)
403 a0d146ed 2005-07-12 devnull 			sysfatal("bad size: %d data=%p", b->size, b->data);
404 a0d146ed 2005-07-12 devnull 		if(b->ref && b->heap == TWID32)
405 a0d146ed 2005-07-12 devnull 			refed++;
406 a0d146ed 2005-07-12 devnull 		if(b->type != TWID8){
407 a0d146ed 2005-07-12 devnull 			findblock(b);
408 a0d146ed 2005-07-12 devnull 			size += b->size;
409 a0d146ed 2005-07-12 devnull 		}
410 a0d146ed 2005-07-12 devnull 		if(b->heap != TWID32
411 a0d146ed 2005-07-12 devnull 		&& lumpcache.heap[b->heap] != b)
412 a0d146ed 2005-07-12 devnull 			sysfatal("lc: spurious heap value");
413 a0d146ed 2005-07-12 devnull 	}
414 a0d146ed 2005-07-12 devnull 	if(lumpcache.avail != lumpcache.allowed - size){
415 a0d146ed 2005-07-12 devnull 		fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
416 0cfb3760 2012-10-21 rsc 		*(volatile int*)0=0;
417 a0d146ed 2005-07-12 devnull 	}
418 a0d146ed 2005-07-12 devnull 
419 a0d146ed 2005-07-12 devnull 	nfree = 0;
420 a0d146ed 2005-07-12 devnull 	for(b = lumpcache.free; b != nil; b = b->next){
421 a0d146ed 2005-07-12 devnull 		if(b->type != TWID8 || b->heap != TWID32)
422 a0d146ed 2005-07-12 devnull 			sysfatal("lc: bad free list");
423 a0d146ed 2005-07-12 devnull 		nfree++;
424 a0d146ed 2005-07-12 devnull 	}
425 a0d146ed 2005-07-12 devnull 
426 a0d146ed 2005-07-12 devnull 	if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
427 a0d146ed 2005-07-12 devnull 		sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
428 a0d146ed 2005-07-12 devnull }