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"
  4 7a4ee46d 2003-11-23 devnull 
  5 7a4ee46d 2003-11-23 devnull typedef struct LumpCache	LumpCache;
  6 7a4ee46d 2003-11-23 devnull 
  7 7a4ee46d 2003-11-23 devnull enum
  8 7a4ee46d 2003-11-23 devnull {
  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,
 12 7a4ee46d 2003-11-23 devnull };
 13 7a4ee46d 2003-11-23 devnull 
 14 7a4ee46d 2003-11-23 devnull struct LumpCache
 15 7a4ee46d 2003-11-23 devnull {
 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 */
 27 7a4ee46d 2003-11-23 devnull };
 28 7a4ee46d 2003-11-23 devnull 
 29 7a4ee46d 2003-11-23 devnull static LumpCache	lumpcache;
 30 7a4ee46d 2003-11-23 devnull 
 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);
 36 7a4ee46d 2003-11-23 devnull 
 37 7a4ee46d 2003-11-23 devnull void
 38 7a4ee46d 2003-11-23 devnull initlumpcache(u32int size, u32int nblocks)
 39 7a4ee46d 2003-11-23 devnull {
 40 7a4ee46d 2003-11-23 devnull 	Lump *last, *b;
 41 7a4ee46d 2003-11-23 devnull 	int i;
 42 7a4ee46d 2003-11-23 devnull 
 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);
 50 7a4ee46d 2003-11-23 devnull 
 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;
 58 7a4ee46d 2003-11-23 devnull 	}
 59 7a4ee46d 2003-11-23 devnull 	lumpcache.free = last;
 60 7a4ee46d 2003-11-23 devnull 	lumpcache.nheap = 0;
 61 7a4ee46d 2003-11-23 devnull }
 62 7a4ee46d 2003-11-23 devnull 
 63 7a4ee46d 2003-11-23 devnull Lump*
 64 7a4ee46d 2003-11-23 devnull lookuplump(u8int *score, int type)
 65 7a4ee46d 2003-11-23 devnull {
 66 7a4ee46d 2003-11-23 devnull 	Lump *b;
 67 7a4ee46d 2003-11-23 devnull 	u32int h;
 68 7a4ee46d 2003-11-23 devnull 
 69 7a4ee46d 2003-11-23 devnull 	h = hashbits(score, HashLog);
 70 7a4ee46d 2003-11-23 devnull 
 71 7a4ee46d 2003-11-23 devnull 	/*
 72 7a4ee46d 2003-11-23 devnull 	 * look for the block in the cache
 73 7a4ee46d 2003-11-23 devnull 	 */
 74 7a4ee46d 2003-11-23 devnull //checklumpcache();
 75 7a4ee46d 2003-11-23 devnull 	qlock(&lumpcache.lock);
 76 7a4ee46d 2003-11-23 devnull again:
 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;
 83 7a4ee46d 2003-11-23 devnull 		}
 84 7a4ee46d 2003-11-23 devnull 	}
 85 7a4ee46d 2003-11-23 devnull 
 86 7a4ee46d 2003-11-23 devnull 	/*
 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.
 89 7a4ee46d 2003-11-23 devnull 	 */
 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;
 95 7a4ee46d 2003-11-23 devnull 		}
 96 7a4ee46d 2003-11-23 devnull 	}
 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);
100 7a4ee46d 2003-11-23 devnull 
101 7a4ee46d 2003-11-23 devnull 	b = lumpcache.free;
102 7a4ee46d 2003-11-23 devnull 	lumpcache.free = b->next;
103 7a4ee46d 2003-11-23 devnull 
104 7a4ee46d 2003-11-23 devnull 	/*
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
107 7a4ee46d 2003-11-23 devnull 	 */
108 7a4ee46d 2003-11-23 devnull 	b->used = (b->used2 + lumpcache.now) / 2;
109 7a4ee46d 2003-11-23 devnull 
110 7a4ee46d 2003-11-23 devnull 	/*
111 7a4ee46d 2003-11-23 devnull 	 * rechain the block on the correct hash chain
112 7a4ee46d 2003-11-23 devnull 	 */
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;
118 7a4ee46d 2003-11-23 devnull 
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;
123 7a4ee46d 2003-11-23 devnull 
124 7a4ee46d 2003-11-23 devnull found:
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);
131 7a4ee46d 2003-11-23 devnull 
132 7a4ee46d 2003-11-23 devnull //checklumpcache();
133 7a4ee46d 2003-11-23 devnull 
134 7a4ee46d 2003-11-23 devnull 	qlock(&b->lock);
135 7a4ee46d 2003-11-23 devnull 
136 7a4ee46d 2003-11-23 devnull 	return b;
137 7a4ee46d 2003-11-23 devnull }
138 7a4ee46d 2003-11-23 devnull 
139 7a4ee46d 2003-11-23 devnull void
140 7a4ee46d 2003-11-23 devnull insertlump(Lump *b, Packet *p)
141 7a4ee46d 2003-11-23 devnull {
142 7a4ee46d 2003-11-23 devnull 	u32int size;
143 7a4ee46d 2003-11-23 devnull 
144 7a4ee46d 2003-11-23 devnull 	/*
145 7a4ee46d 2003-11-23 devnull 	 * look for the block in the cache
146 7a4ee46d 2003-11-23 devnull 	 */
147 7a4ee46d 2003-11-23 devnull //checklumpcache();
148 7a4ee46d 2003-11-23 devnull 	qlock(&lumpcache.lock);
149 7a4ee46d 2003-11-23 devnull again:
150 7a4ee46d 2003-11-23 devnull 
151 7a4ee46d 2003-11-23 devnull 	/*
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.
154 7a4ee46d 2003-11-23 devnull 	 */
155 7a4ee46d 2003-11-23 devnull 	size = packetasize(p);
156 7a4ee46d 2003-11-23 devnull //ZZZ
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;
162 7a4ee46d 2003-11-23 devnull 		}
163 7a4ee46d 2003-11-23 devnull 	}
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;
167 7a4ee46d 2003-11-23 devnull 
168 7a4ee46d 2003-11-23 devnull 	qunlock(&lumpcache.lock);
169 7a4ee46d 2003-11-23 devnull //checklumpcache();
170 7a4ee46d 2003-11-23 devnull }
171 7a4ee46d 2003-11-23 devnull 
172 7a4ee46d 2003-11-23 devnull void
173 7a4ee46d 2003-11-23 devnull putlump(Lump *b)
174 7a4ee46d 2003-11-23 devnull {
175 7a4ee46d 2003-11-23 devnull 	if(b == nil)
176 7a4ee46d 2003-11-23 devnull 		return;
177 7a4ee46d 2003-11-23 devnull 
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);
185 7a4ee46d 2003-11-23 devnull 	}
186 7a4ee46d 2003-11-23 devnull 
187 7a4ee46d 2003-11-23 devnull 	qunlock(&lumpcache.lock);
188 7a4ee46d 2003-11-23 devnull //checklumpcache();
189 7a4ee46d 2003-11-23 devnull }
190 7a4ee46d 2003-11-23 devnull 
191 7a4ee46d 2003-11-23 devnull /*
192 7a4ee46d 2003-11-23 devnull  * remove some lump from use and update the free list and counters
193 7a4ee46d 2003-11-23 devnull  */
194 7a4ee46d 2003-11-23 devnull static Lump*
195 7a4ee46d 2003-11-23 devnull bumplump(void)
196 7a4ee46d 2003-11-23 devnull {
197 7a4ee46d 2003-11-23 devnull 	Lump *b;
198 7a4ee46d 2003-11-23 devnull 	u32int h;
199 7a4ee46d 2003-11-23 devnull 
200 7a4ee46d 2003-11-23 devnull 	/*
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
204 7a4ee46d 2003-11-23 devnull 	 */
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);
212 7a4ee46d 2003-11-23 devnull 			break;
213 7a4ee46d 2003-11-23 devnull 		}
214 7a4ee46d 2003-11-23 devnull 	}
215 7a4ee46d 2003-11-23 devnull 
216 7a4ee46d 2003-11-23 devnull 	/*
217 7a4ee46d 2003-11-23 devnull 	 * unchain the block
218 7a4ee46d 2003-11-23 devnull 	 */
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;
224 7a4ee46d 2003-11-23 devnull 	}else
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;
228 7a4ee46d 2003-11-23 devnull 
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;
234 7a4ee46d 2003-11-23 devnull 	}
235 7a4ee46d 2003-11-23 devnull 	b->type = TWID8;
236 7a4ee46d 2003-11-23 devnull 
237 7a4ee46d 2003-11-23 devnull 	b->next = lumpcache.free;
238 7a4ee46d 2003-11-23 devnull 	lumpcache.free = b;
239 7a4ee46d 2003-11-23 devnull 
240 7a4ee46d 2003-11-23 devnull 	return b;
241 7a4ee46d 2003-11-23 devnull }
242 7a4ee46d 2003-11-23 devnull 
243 7a4ee46d 2003-11-23 devnull /*
244 7a4ee46d 2003-11-23 devnull  * delete an arbitrary block from the heap
245 7a4ee46d 2003-11-23 devnull  */
246 7a4ee46d 2003-11-23 devnull static void
247 7a4ee46d 2003-11-23 devnull delheap(Lump *db)
248 7a4ee46d 2003-11-23 devnull {
249 7a4ee46d 2003-11-23 devnull 	fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
250 7a4ee46d 2003-11-23 devnull 	db->heap = TWID32;
251 7a4ee46d 2003-11-23 devnull }
252 7a4ee46d 2003-11-23 devnull 
253 7a4ee46d 2003-11-23 devnull /*
254 7a4ee46d 2003-11-23 devnull  * push an element up or down to it's correct new location
255 7a4ee46d 2003-11-23 devnull  */
256 7a4ee46d 2003-11-23 devnull static void
257 7a4ee46d 2003-11-23 devnull fixheap(int i, Lump *b)
258 7a4ee46d 2003-11-23 devnull {
259 7a4ee46d 2003-11-23 devnull 	if(upheap(i, b) == i)
260 7a4ee46d 2003-11-23 devnull 		downheap(i, b);
261 7a4ee46d 2003-11-23 devnull }
262 7a4ee46d 2003-11-23 devnull 
263 7a4ee46d 2003-11-23 devnull static int
264 7a4ee46d 2003-11-23 devnull upheap(int i, Lump *b)
265 7a4ee46d 2003-11-23 devnull {
266 7a4ee46d 2003-11-23 devnull 	Lump *bb;
267 7a4ee46d 2003-11-23 devnull 	u32int now;
268 7a4ee46d 2003-11-23 devnull 	int p;
269 7a4ee46d 2003-11-23 devnull 
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)
275 7a4ee46d 2003-11-23 devnull 			break;
276 7a4ee46d 2003-11-23 devnull 		lumpcache.heap[i] = bb;
277 7a4ee46d 2003-11-23 devnull 		bb->heap = i;
278 7a4ee46d 2003-11-23 devnull 	}
279 7a4ee46d 2003-11-23 devnull 
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;
283 7a4ee46d 2003-11-23 devnull }
284 7a4ee46d 2003-11-23 devnull 
285 7a4ee46d 2003-11-23 devnull static int
286 7a4ee46d 2003-11-23 devnull downheap(int i, Lump *b)
287 7a4ee46d 2003-11-23 devnull {
288 7a4ee46d 2003-11-23 devnull 	Lump *bb;
289 7a4ee46d 2003-11-23 devnull 	u32int now;
290 7a4ee46d 2003-11-23 devnull 	int k;
291 7a4ee46d 2003-11-23 devnull 
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)
296 7a4ee46d 2003-11-23 devnull 			break;
297 7a4ee46d 2003-11-23 devnull 		if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
298 7a4ee46d 2003-11-23 devnull 			k++;
299 7a4ee46d 2003-11-23 devnull 		bb = lumpcache.heap[k];
300 7a4ee46d 2003-11-23 devnull 		if(b->used2 - now <= bb->used2 - now)
301 7a4ee46d 2003-11-23 devnull 			break;
302 7a4ee46d 2003-11-23 devnull 		lumpcache.heap[i] = bb;
303 7a4ee46d 2003-11-23 devnull 		bb->heap = i;
304 7a4ee46d 2003-11-23 devnull 	}
305 7a4ee46d 2003-11-23 devnull 
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;
309 7a4ee46d 2003-11-23 devnull }
310 7a4ee46d 2003-11-23 devnull 
311 7a4ee46d 2003-11-23 devnull static void
312 7a4ee46d 2003-11-23 devnull findblock(Lump *bb)
313 7a4ee46d 2003-11-23 devnull {
314 7a4ee46d 2003-11-23 devnull 	Lump *b, *last;
315 7a4ee46d 2003-11-23 devnull 	int h;
316 7a4ee46d 2003-11-23 devnull 
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)
323 7a4ee46d 2003-11-23 devnull 			return;
324 7a4ee46d 2003-11-23 devnull 		last = b;
325 7a4ee46d 2003-11-23 devnull 	}
326 7a4ee46d 2003-11-23 devnull 	sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
327 7a4ee46d 2003-11-23 devnull }
328 7a4ee46d 2003-11-23 devnull 
329 7a4ee46d 2003-11-23 devnull void
330 7a4ee46d 2003-11-23 devnull checklumpcache(void)
331 7a4ee46d 2003-11-23 devnull {
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;
335 7a4ee46d 2003-11-23 devnull 
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");
346 7a4ee46d 2003-11-23 devnull 		k++;
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");
349 7a4ee46d 2003-11-23 devnull 	}
350 7a4ee46d 2003-11-23 devnull 
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;
362 7a4ee46d 2003-11-23 devnull 		}
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");
366 7a4ee46d 2003-11-23 devnull 	}
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);
369 7a4ee46d 2003-11-23 devnull 
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++;
375 7a4ee46d 2003-11-23 devnull 	}
376 7a4ee46d 2003-11-23 devnull 
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);
380 7a4ee46d 2003-11-23 devnull }