1 7763a61a 2003-11-23 devnull #include "stdinc.h"
  2 7763a61a 2003-11-23 devnull #include "vac.h"
  3 7763a61a 2003-11-23 devnull #include "dat.h"
  4 7763a61a 2003-11-23 devnull #include "fns.h"
  5 7763a61a 2003-11-23 devnull 
  6 7763a61a 2003-11-23 devnull typedef struct Label Label;
  7 7763a61a 2003-11-23 devnull 
  8 7763a61a 2003-11-23 devnull enum {
  9 7763a61a 2003-11-23 devnull 	BadHeap = ~0,
 10 7763a61a 2003-11-23 devnull };
 11 7763a61a 2003-11-23 devnull 
 12 7763a61a 2003-11-23 devnull /*
 13 7763a61a 2003-11-23 devnull  * the plan is to store data to the cache in c->size blocks
 14 7763a61a 2003-11-23 devnull  * with the block zero extended to fill it out.  When writing to
 15 7763a61a 2003-11-23 devnull  * venti, the block will be zero truncated.  The walker will also check
 16 7763a61a 2003-11-23 devnull  * that the block fits within psize or dsize as the case may be.
 17 7763a61a 2003-11-23 devnull  */
 18 7763a61a 2003-11-23 devnull 
 19 7763a61a 2003-11-23 devnull struct Cache
 20 7763a61a 2003-11-23 devnull {
 21 7763a61a 2003-11-23 devnull 	VtLock	*lk;
 22 7763a61a 2003-11-23 devnull 	VtSession *z;
 23 7763a61a 2003-11-23 devnull 	u32int	now;			/* ticks for usage timestamps */
 24 7763a61a 2003-11-23 devnull 	int	size;			/* max. size of any block; allocated to each block */
 25 7763a61a 2003-11-23 devnull 	Lump	**heads;		/* hash table for finding address */
 26 7763a61a 2003-11-23 devnull 	int	nheap;			/* number of available victims */
 27 7763a61a 2003-11-23 devnull 	Lump	**heap;			/* heap for locating victims */
 28 7763a61a 2003-11-23 devnull 	long	nblocks;		/* number of blocks allocated */
 29 7763a61a 2003-11-23 devnull 	Lump	*blocks;		/* array of block descriptors */
 30 7763a61a 2003-11-23 devnull 	u8int	*mem;			/* memory for all block descriptors */
 31 7763a61a 2003-11-23 devnull 	Lump	*free;			/* free list of lumps */
 32 7763a61a 2003-11-23 devnull 
 33 7763a61a 2003-11-23 devnull 	long hashSize;
 34 7763a61a 2003-11-23 devnull };
 35 7763a61a 2003-11-23 devnull 
 36 7763a61a 2003-11-23 devnull /*
 37 7763a61a 2003-11-23 devnull  * the tag for a block is hash(index, parent tag)
 38 7763a61a 2003-11-23 devnull  */
 39 7763a61a 2003-11-23 devnull 
 40 7763a61a 2003-11-23 devnull struct Label {
 41 7763a61a 2003-11-23 devnull 	uchar gen[4];
 42 7763a61a 2003-11-23 devnull 	uchar state;
 43 7763a61a 2003-11-23 devnull 	uchar type;		/* top bit indicates it is part of a directory */
 44 7763a61a 2003-11-23 devnull 	uchar tag[4];		/* tag of file it is in */
 45 7763a61a 2003-11-23 devnull };
 46 7763a61a 2003-11-23 devnull 
 47 7763a61a 2003-11-23 devnull 
 48 7763a61a 2003-11-23 devnull static char ENoDir[] = "directory entry is not allocated";
 49 7763a61a 2003-11-23 devnull 
 50 7763a61a 2003-11-23 devnull static void fixHeap(int si, Lump *b);
 51 7763a61a 2003-11-23 devnull static int upHeap(int i, Lump *b);
 52 7763a61a 2003-11-23 devnull static int downHeap(int i, Lump *b);
 53 7763a61a 2003-11-23 devnull static char	*lumpState(int);
 54 7763a61a 2003-11-23 devnull static void	lumpSetState(Lump *u, int state);
 55 7763a61a 2003-11-23 devnull 
 56 7763a61a 2003-11-23 devnull Cache *
 57 7763a61a 2003-11-23 devnull cacheAlloc(VtSession *z, int blockSize, long nblocks)
 58 7763a61a 2003-11-23 devnull {
 59 7763a61a 2003-11-23 devnull 	int i;
 60 7763a61a 2003-11-23 devnull 	Cache *c;
 61 7763a61a 2003-11-23 devnull 	Lump *b;
 62 7763a61a 2003-11-23 devnull 
 63 7763a61a 2003-11-23 devnull 	c = vtMemAllocZ(sizeof(Cache));
 64 7763a61a 2003-11-23 devnull 	
 65 7763a61a 2003-11-23 devnull 	c->lk = vtLockAlloc();
 66 7763a61a 2003-11-23 devnull 	c->z = z;
 67 7763a61a 2003-11-23 devnull 	c->size = blockSize;
 68 7763a61a 2003-11-23 devnull 	c->nblocks = nblocks;
 69 7763a61a 2003-11-23 devnull 	c->hashSize = nblocks;
 70 7763a61a 2003-11-23 devnull 	c->heads = vtMemAllocZ(c->hashSize*sizeof(Lump*));
 71 7763a61a 2003-11-23 devnull 	c->heap = vtMemAllocZ(nblocks*sizeof(Lump*));
 72 7763a61a 2003-11-23 devnull 	c->blocks = vtMemAllocZ(nblocks*sizeof(Lump));
 73 7763a61a 2003-11-23 devnull 	c->mem = vtMemAllocZ(nblocks * blockSize);
 74 7763a61a 2003-11-23 devnull 	for(i = 0; i < nblocks; i++){
 75 7763a61a 2003-11-23 devnull 		b = &c->blocks[i];
 76 7763a61a 2003-11-23 devnull 		b->lk = vtLockAlloc();
 77 7763a61a 2003-11-23 devnull 		b->c = c;
 78 7763a61a 2003-11-23 devnull 		b->data = &c->mem[i * blockSize];
 79 7763a61a 2003-11-23 devnull 		b->addr = i+1;
 80 7763a61a 2003-11-23 devnull 		b->state = LumpFree;
 81 7763a61a 2003-11-23 devnull 		b->heap = BadHeap;
 82 7763a61a 2003-11-23 devnull 		b->next = c->free;
 83 7763a61a 2003-11-23 devnull 		c->free = b;
 84 7763a61a 2003-11-23 devnull 	}
 85 7763a61a 2003-11-23 devnull 	c->nheap = 0;
 86 7763a61a 2003-11-23 devnull 
 87 7763a61a 2003-11-23 devnull 	return c;
 88 7763a61a 2003-11-23 devnull }
 89 7763a61a 2003-11-23 devnull 
 90 7763a61a 2003-11-23 devnull long
 91 7763a61a 2003-11-23 devnull cacheGetSize(Cache *c)
 92 7763a61a 2003-11-23 devnull {
 93 7763a61a 2003-11-23 devnull 	return c->nblocks;
 94 7763a61a 2003-11-23 devnull }
 95 7763a61a 2003-11-23 devnull 
 96 7763a61a 2003-11-23 devnull int
 97 7763a61a 2003-11-23 devnull cacheGetBlockSize(Cache *c)
 98 7763a61a 2003-11-23 devnull {
 99 7763a61a 2003-11-23 devnull 	return c->size;
100 7763a61a 2003-11-23 devnull }
101 7763a61a 2003-11-23 devnull 
102 7763a61a 2003-11-23 devnull int
103 7763a61a 2003-11-23 devnull cacheSetSize(Cache *c, long nblocks)
104 7763a61a 2003-11-23 devnull {
105 7763a61a 2003-11-23 devnull 	USED(c);
106 7763a61a 2003-11-23 devnull 	USED(nblocks);
107 7763a61a 2003-11-23 devnull 	return 0;
108 7763a61a 2003-11-23 devnull }
109 7763a61a 2003-11-23 devnull 
110 7763a61a 2003-11-23 devnull void
111 7763a61a 2003-11-23 devnull cacheFree(Cache *c)
112 7763a61a 2003-11-23 devnull {
113 7763a61a 2003-11-23 devnull 	int i;
114 7763a61a 2003-11-23 devnull 
115 7763a61a 2003-11-23 devnull 	for(i = 0; i < c->nblocks; i++){
116 7763a61a 2003-11-23 devnull 		assert(c->blocks[i].ref == 0);
117 7763a61a 2003-11-23 devnull 		vtLockFree(c->blocks[i].lk);
118 7763a61a 2003-11-23 devnull 	}
119 7763a61a 2003-11-23 devnull 	vtMemFree(c->heads);
120 7763a61a 2003-11-23 devnull 	vtMemFree(c->blocks);
121 7763a61a 2003-11-23 devnull 	vtMemFree(c->mem);
122 7763a61a 2003-11-23 devnull 	vtMemFree(c);
123 7763a61a 2003-11-23 devnull }
124 7763a61a 2003-11-23 devnull 
125 7763a61a 2003-11-23 devnull static u32int
126 7763a61a 2003-11-23 devnull hash(Cache *c, uchar score[VtScoreSize], int type)
127 7763a61a 2003-11-23 devnull {
128 7763a61a 2003-11-23 devnull 	u32int h;
129 7763a61a 2003-11-23 devnull 	uchar *p = score + VtScoreSize-4;
130 7763a61a 2003-11-23 devnull 
131 7763a61a 2003-11-23 devnull 	h = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
132 7763a61a 2003-11-23 devnull 	h += type;
133 7763a61a 2003-11-23 devnull 	return h % c->hashSize;
134 7763a61a 2003-11-23 devnull }
135 7763a61a 2003-11-23 devnull 
136 7763a61a 2003-11-23 devnull static void
137 7763a61a 2003-11-23 devnull findLump(Cache *c, Lump *bb)
138 7763a61a 2003-11-23 devnull {
139 7763a61a 2003-11-23 devnull 	Lump *b, *last;
140 7763a61a 2003-11-23 devnull 	int h;
141 7763a61a 2003-11-23 devnull 
142 7763a61a 2003-11-23 devnull 	last = nil;
143 7763a61a 2003-11-23 devnull 	h = hash(c, bb->score, bb->type);
144 7763a61a 2003-11-23 devnull 	for(b = c->heads[h]; b != nil; b = b->next){
145 7763a61a 2003-11-23 devnull 		if(last != b->prev)
146 7763a61a 2003-11-23 devnull 			vtFatal("bad prev link");
147 7763a61a 2003-11-23 devnull 		if(b == bb)
148 7763a61a 2003-11-23 devnull 			return;
149 7763a61a 2003-11-23 devnull 		last = b;
150 7763a61a 2003-11-23 devnull 	}
151 7763a61a 2003-11-23 devnull 	vtFatal("block missing from hash table");
152 7763a61a 2003-11-23 devnull }
153 7763a61a 2003-11-23 devnull 
154 7763a61a 2003-11-23 devnull void
155 7763a61a 2003-11-23 devnull cacheCheck(Cache *c)
156 7763a61a 2003-11-23 devnull {
157 7763a61a 2003-11-23 devnull 	u32int size, now;
158 7763a61a 2003-11-23 devnull 	int i, k, refed, free;
159 7763a61a 2003-11-23 devnull 	static uchar zero[VtScoreSize];
160 7763a61a 2003-11-23 devnull 	Lump *p;
161 7763a61a 2003-11-23 devnull 
162 7763a61a 2003-11-23 devnull 	size = c->size;
163 7763a61a 2003-11-23 devnull 	now = c->now;
164 7763a61a 2003-11-23 devnull 
165 7763a61a 2003-11-23 devnull 	free = 0;
166 7763a61a 2003-11-23 devnull 	for(p=c->free; p; p=p->next)
167 7763a61a 2003-11-23 devnull 		free++;
168 7763a61a 2003-11-23 devnull 	for(i = 0; i < c->nheap; i++){
169 7763a61a 2003-11-23 devnull 		if(c->heap[i]->heap != i)
170 7763a61a 2003-11-23 devnull 			vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
171 7763a61a 2003-11-23 devnull 		if(i > 0 && c->heap[(i - 1) >> 1]->used2 - now > c->heap[i]->used2 - now)
172 7763a61a 2003-11-23 devnull 			vtFatal("bad heap ordering");
173 7763a61a 2003-11-23 devnull 		k = (i << 1) + 1;
174 7763a61a 2003-11-23 devnull 		if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now)
175 7763a61a 2003-11-23 devnull 			vtFatal("bad heap ordering");
176 7763a61a 2003-11-23 devnull 		k++;
177 7763a61a 2003-11-23 devnull 		if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now)
178 7763a61a 2003-11-23 devnull 			vtFatal("bad heap ordering");
179 7763a61a 2003-11-23 devnull 	}
180 7763a61a 2003-11-23 devnull 
181 7763a61a 2003-11-23 devnull 	refed = 0;
182 7763a61a 2003-11-23 devnull 	for(i = 0; i < c->nblocks; i++){
183 7763a61a 2003-11-23 devnull 		if(c->blocks[i].data != &c->mem[i * size])
184 7763a61a 2003-11-23 devnull 			vtFatal("mis-blocked at %d", i);
185 7763a61a 2003-11-23 devnull 		if(c->blocks[i].ref && c->blocks[i].heap == BadHeap){
186 7763a61a 2003-11-23 devnull 			refed++;
187 7763a61a 2003-11-23 devnull 		}
188 7763a61a 2003-11-23 devnull 		if(memcmp(zero, c->blocks[i].score, VtScoreSize))
189 7763a61a 2003-11-23 devnull 			findLump(c, &c->blocks[i]);
190 7763a61a 2003-11-23 devnull 	}
191 7763a61a 2003-11-23 devnull if(refed > 0)fprint(2, "cacheCheck: nheap %d refed %d free %d\n", c->nheap, refed, free);
192 7763a61a 2003-11-23 devnull 	assert(c->nheap + refed + free == c->nblocks);
193 7763a61a 2003-11-23 devnull 	refed = 0;
194 7763a61a 2003-11-23 devnull 	for(i = 0; i < c->nblocks; i++){
195 7763a61a 2003-11-23 devnull 		if(c->blocks[i].ref) {
196 7763a61a 2003-11-23 devnull if(1)fprint(2, "%d %V %d %s\n", c->blocks[i].type, c->blocks[i].score, c->blocks[i].ref, lumpState(c->blocks[i].state));
197 7763a61a 2003-11-23 devnull 			refed++;
198 7763a61a 2003-11-23 devnull 		}
199 7763a61a 2003-11-23 devnull 	}
200 7763a61a 2003-11-23 devnull if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
201 7763a61a 2003-11-23 devnull }
202 7763a61a 2003-11-23 devnull 
203 7763a61a 2003-11-23 devnull /*
204 7763a61a 2003-11-23 devnull  * delete an arbitrary block from the heap
205 7763a61a 2003-11-23 devnull  */
206 7763a61a 2003-11-23 devnull static void
207 7763a61a 2003-11-23 devnull delHeap(Lump *db)
208 7763a61a 2003-11-23 devnull {
209 7763a61a 2003-11-23 devnull 	fixHeap(db->heap, db->c->heap[--db->c->nheap]);
210 7763a61a 2003-11-23 devnull 	db->heap = BadHeap;
211 7763a61a 2003-11-23 devnull }
212 7763a61a 2003-11-23 devnull 
213 7763a61a 2003-11-23 devnull static void
214 7763a61a 2003-11-23 devnull fixHeap(int si, Lump *b)
215 7763a61a 2003-11-23 devnull {
216 7763a61a 2003-11-23 devnull 	int i;
217 7763a61a 2003-11-23 devnull 
218 7763a61a 2003-11-23 devnull 	i = upHeap(si, b);
219 7763a61a 2003-11-23 devnull 	if(i == si)
220 7763a61a 2003-11-23 devnull 		downHeap(i, b);
221 7763a61a 2003-11-23 devnull }
222 7763a61a 2003-11-23 devnull 
223 7763a61a 2003-11-23 devnull static int
224 7763a61a 2003-11-23 devnull upHeap(int i, Lump *b)
225 7763a61a 2003-11-23 devnull {
226 7763a61a 2003-11-23 devnull 	Lump *bb;
227 7763a61a 2003-11-23 devnull 	u32int now;
228 7763a61a 2003-11-23 devnull 	int p;
229 7763a61a 2003-11-23 devnull 	Cache *c;
230 7763a61a 2003-11-23 devnull 	
231 7763a61a 2003-11-23 devnull 	c = b->c;
232 7763a61a 2003-11-23 devnull 	now = c->now;
233 7763a61a 2003-11-23 devnull 	for(; i != 0; i = p){
234 7763a61a 2003-11-23 devnull 		p = (i - 1) >> 1;
235 7763a61a 2003-11-23 devnull 		bb = c->heap[p];
236 7763a61a 2003-11-23 devnull 		if(b->used2 - now >= bb->used2 - now)
237 7763a61a 2003-11-23 devnull 			break;
238 7763a61a 2003-11-23 devnull 		c->heap[i] = bb;
239 7763a61a 2003-11-23 devnull 		bb->heap = i;
240 7763a61a 2003-11-23 devnull 	}
241 7763a61a 2003-11-23 devnull 	c->heap[i] = b;
242 7763a61a 2003-11-23 devnull 	b->heap = i;
243 7763a61a 2003-11-23 devnull 
244 7763a61a 2003-11-23 devnull 	return i;
245 7763a61a 2003-11-23 devnull }
246 7763a61a 2003-11-23 devnull 
247 7763a61a 2003-11-23 devnull static int
248 7763a61a 2003-11-23 devnull downHeap(int i, Lump *b)
249 7763a61a 2003-11-23 devnull {
250 7763a61a 2003-11-23 devnull 	Lump *bb;
251 7763a61a 2003-11-23 devnull 	u32int now;
252 7763a61a 2003-11-23 devnull 	int k;
253 7763a61a 2003-11-23 devnull 	Cache *c;
254 7763a61a 2003-11-23 devnull 	
255 7763a61a 2003-11-23 devnull 	c = b->c;
256 7763a61a 2003-11-23 devnull 	now = c->now;
257 7763a61a 2003-11-23 devnull 	for(; ; i = k){
258 7763a61a 2003-11-23 devnull 		k = (i << 1) + 1;
259 7763a61a 2003-11-23 devnull 		if(k >= c->nheap)
260 7763a61a 2003-11-23 devnull 			break;
261 7763a61a 2003-11-23 devnull 		if(k + 1 < c->nheap && c->heap[k]->used2 - now > c->heap[k + 1]->used2 - now)
262 7763a61a 2003-11-23 devnull 			k++;
263 7763a61a 2003-11-23 devnull 		bb = c->heap[k];
264 7763a61a 2003-11-23 devnull 		if(b->used2 - now <= bb->used2 - now)
265 7763a61a 2003-11-23 devnull 			break;
266 7763a61a 2003-11-23 devnull 		c->heap[i] = bb;
267 7763a61a 2003-11-23 devnull 		bb->heap = i;
268 7763a61a 2003-11-23 devnull 	}
269 7763a61a 2003-11-23 devnull 	c->heap[i] = b;
270 7763a61a 2003-11-23 devnull 	b->heap = i;
271 7763a61a 2003-11-23 devnull 	return i;
272 7763a61a 2003-11-23 devnull }
273 7763a61a 2003-11-23 devnull 
274 7763a61a 2003-11-23 devnull 
275 7763a61a 2003-11-23 devnull /* called with c->lk held */
276 7763a61a 2003-11-23 devnull Lump *
277 7763a61a 2003-11-23 devnull cacheBumpLump(Cache *c)
278 7763a61a 2003-11-23 devnull {
279 7763a61a 2003-11-23 devnull 	Lump *b;
280 7763a61a 2003-11-23 devnull 
281 7763a61a 2003-11-23 devnull 	/*
282 7763a61a 2003-11-23 devnull 	 * missed: locate the block with the oldest second to last use.
283 7763a61a 2003-11-23 devnull 	 * remove it from the heap, and fix up the heap.
284 7763a61a 2003-11-23 devnull 	 */
285 7763a61a 2003-11-23 devnull 	if(c->free) {
286 7763a61a 2003-11-23 devnull 		b = c->free;
287 7763a61a 2003-11-23 devnull 		c->free = b->next;
288 7763a61a 2003-11-23 devnull 	} else {
289 7763a61a 2003-11-23 devnull 		for(;;){
290 7763a61a 2003-11-23 devnull 			if(c->nheap == 0) {
291 7763a61a 2003-11-23 devnull 				cacheCheck(c);
292 7763a61a 2003-11-23 devnull 				assert(0);
293 7763a61a 2003-11-23 devnull 				return nil;
294 7763a61a 2003-11-23 devnull 			}
295 7763a61a 2003-11-23 devnull 			b = c->heap[0];
296 7763a61a 2003-11-23 devnull 			delHeap(b);
297 7763a61a 2003-11-23 devnull 			if(b->ref == 0)
298 7763a61a 2003-11-23 devnull 				break;
299 7763a61a 2003-11-23 devnull 		}
300 7763a61a 2003-11-23 devnull 
301 7763a61a 2003-11-23 devnull 		/*
302 7763a61a 2003-11-23 devnull 		 * unchain the block from hash chain
303 7763a61a 2003-11-23 devnull 		 */
304 7763a61a 2003-11-23 devnull 		if(b->prev == nil)
305 7763a61a 2003-11-23 devnull 			c->heads[hash(c, b->score, b->type)] = b->next;
306 7763a61a 2003-11-23 devnull 		else
307 7763a61a 2003-11-23 devnull 			b->prev->next = b->next;
308 7763a61a 2003-11-23 devnull 		if(b->next != nil)
309 7763a61a 2003-11-23 devnull 			b->next->prev = b->prev;
310 7763a61a 2003-11-23 devnull 
311 7763a61a 2003-11-23 devnull 	}
312 7763a61a 2003-11-23 devnull 
313 7763a61a 2003-11-23 devnull 	/*
314 7763a61a 2003-11-23 devnull 	 * the new block has no last use, so assume it happens sometime in the middle
315 7763a61a 2003-11-23 devnull 	 */
316 7763a61a 2003-11-23 devnull 	b->used = (b->used2 + c->now) / 2;
317 7763a61a 2003-11-23 devnull 	b->asize = 0;
318 7763a61a 2003-11-23 devnull 
319 7763a61a 2003-11-23 devnull 	return b;
320 7763a61a 2003-11-23 devnull }
321 7763a61a 2003-11-23 devnull 
322 7763a61a 2003-11-23 devnull Lump *
323 7763a61a 2003-11-23 devnull cacheAllocLump(Cache *c, int type, int size, int dir)
324 7763a61a 2003-11-23 devnull {
325 7763a61a 2003-11-23 devnull 	Lump *b;
326 7763a61a 2003-11-23 devnull 	ulong h;
327 7763a61a 2003-11-23 devnull 
328 7763a61a 2003-11-23 devnull 	assert(size <= c->size);
329 7763a61a 2003-11-23 devnull 
330 7763a61a 2003-11-23 devnull again:
331 7763a61a 2003-11-23 devnull 	vtLock(c->lk);
332 7763a61a 2003-11-23 devnull 	b = cacheBumpLump(c);
333 7763a61a 2003-11-23 devnull 	if(b == nil) {
334 7763a61a 2003-11-23 devnull 		vtUnlock(c->lk);
335 7763a61a 2003-11-23 devnull fprint(2, "cache is full\n");
336 7763a61a 2003-11-23 devnull 		/* XXX should be better */
337 7763a61a 2003-11-23 devnull 		sleep(100);
338 7763a61a 2003-11-23 devnull 		goto again;
339 7763a61a 2003-11-23 devnull 	}
340 7763a61a 2003-11-23 devnull 
341 7763a61a 2003-11-23 devnull 	vtLock(b->lk);
342 7763a61a 2003-11-23 devnull 
343 7763a61a 2003-11-23 devnull 	assert(b->ref == 0);
344 7763a61a 2003-11-23 devnull 	b->ref++;
345 7763a61a 2003-11-23 devnull 	b->used2 = b->used;
346 7763a61a 2003-11-23 devnull 	b->used = c->now++;
347 7763a61a 2003-11-23 devnull 
348 7763a61a 2003-11-23 devnull 	/* convert addr into score */
349 7763a61a 2003-11-23 devnull 	memset(b->score, 0, VtScoreSize-4);
350 7763a61a 2003-11-23 devnull 	b->score[VtScoreSize-4] = b->addr>>24;
351 7763a61a 2003-11-23 devnull 	b->score[VtScoreSize-3] = b->addr>>16;
352 7763a61a 2003-11-23 devnull 	b->score[VtScoreSize-2] = b->addr>>8;
353 7763a61a 2003-11-23 devnull 	b->score[VtScoreSize-1] = b->addr;
354 7763a61a 2003-11-23 devnull 	
355 7763a61a 2003-11-23 devnull 	b->dir = dir;
356 7763a61a 2003-11-23 devnull 	b->type = type;
357 7763a61a 2003-11-23 devnull 	b->gen = 0;
358 7763a61a 2003-11-23 devnull 	b->asize = size;
359 7763a61a 2003-11-23 devnull 	b->state = LumpFree;
360 7763a61a 2003-11-23 devnull 
361 7763a61a 2003-11-23 devnull 	h = hash(c, b->score, b->type);
362 7763a61a 2003-11-23 devnull 
363 7763a61a 2003-11-23 devnull 	/* chain onto correct hash */
364 7763a61a 2003-11-23 devnull 	b->next = c->heads[h];
365 7763a61a 2003-11-23 devnull 	c->heads[h] = b;
366 7763a61a 2003-11-23 devnull 	if(b->next != nil)
367 7763a61a 2003-11-23 devnull 		b->next->prev = b;
368 7763a61a 2003-11-23 devnull 	b->prev = nil;
369 7763a61a 2003-11-23 devnull 
370 7763a61a 2003-11-23 devnull 	vtUnlock(c->lk);
371 7763a61a 2003-11-23 devnull 
372 7763a61a 2003-11-23 devnull 	vtZeroExtend(type, b->data, 0, size);
373 7763a61a 2003-11-23 devnull 	lumpSetState(b, LumpActive);
374 7763a61a 2003-11-23 devnull 
375 7763a61a 2003-11-23 devnull 	return b;
376 7763a61a 2003-11-23 devnull }
377 7763a61a 2003-11-23 devnull 
378 7763a61a 2003-11-23 devnull int
379 7763a61a 2003-11-23 devnull scoreIsLocal(uchar score[VtScoreSize])
380 7763a61a 2003-11-23 devnull {
381 7763a61a 2003-11-23 devnull 	static uchar zero[VtScoreSize];
382 7763a61a 2003-11-23 devnull 	
383 7763a61a 2003-11-23 devnull 	return memcmp(score, zero, VtScoreSize-4) == 0;
384 7763a61a 2003-11-23 devnull }
385 7763a61a 2003-11-23 devnull 
386 7763a61a 2003-11-23 devnull Lump *
387 7763a61a 2003-11-23 devnull cacheGetLump(Cache *c, uchar score[VtScoreSize], int type, int size)
388 7763a61a 2003-11-23 devnull {
389 7763a61a 2003-11-23 devnull 	Lump *b;
390 7763a61a 2003-11-23 devnull 	ulong h;
391 7763a61a 2003-11-23 devnull 	int n;
392 7763a61a 2003-11-23 devnull 	static uchar zero[VtScoreSize];
393 7763a61a 2003-11-23 devnull 
394 7763a61a 2003-11-23 devnull 	assert(size <= c->size);
395 7763a61a 2003-11-23 devnull 
396 7763a61a 2003-11-23 devnull 	h = hash(c, score, type);
397 7763a61a 2003-11-23 devnull 
398 7763a61a 2003-11-23 devnull again:
399 7763a61a 2003-11-23 devnull 	/*
400 7763a61a 2003-11-23 devnull 	 * look for the block in the cache
401 7763a61a 2003-11-23 devnull 	 */
402 7763a61a 2003-11-23 devnull 	vtLock(c->lk);
403 7763a61a 2003-11-23 devnull 	for(b = c->heads[h]; b != nil; b = b->next){
404 7763a61a 2003-11-23 devnull 		if(memcmp(b->score, score, VtScoreSize) == 0 && b->type == type)
405 7763a61a 2003-11-23 devnull 			goto found;
406 7763a61a 2003-11-23 devnull 	}
407 7763a61a 2003-11-23 devnull 
408 7763a61a 2003-11-23 devnull 	/* should not be looking for a temp block */
409 7763a61a 2003-11-23 devnull 	if(scoreIsLocal(score)) {
410 7763a61a 2003-11-23 devnull 		if(memcmp(score, zero, VtScoreSize) == 0)
411 7763a61a 2003-11-23 devnull 			vtSetError("looking for zero score");
412 7763a61a 2003-11-23 devnull 		else
413 7763a61a 2003-11-23 devnull 			vtSetError("missing local block");
414 7763a61a 2003-11-23 devnull 		vtUnlock(c->lk);
415 7763a61a 2003-11-23 devnull 		return nil;
416 7763a61a 2003-11-23 devnull 	}
417 7763a61a 2003-11-23 devnull 
418 7763a61a 2003-11-23 devnull 	b = cacheBumpLump(c);
419 7763a61a 2003-11-23 devnull 	if(b == nil) {
420 7763a61a 2003-11-23 devnull 		vtUnlock(c->lk);
421 7763a61a 2003-11-23 devnull 		sleep(100);
422 7763a61a 2003-11-23 devnull 		goto again;
423 7763a61a 2003-11-23 devnull 	}
424 7763a61a 2003-11-23 devnull 
425 7763a61a 2003-11-23 devnull 	/* chain onto correct hash */
426 7763a61a 2003-11-23 devnull 	b->next = c->heads[h];
427 7763a61a 2003-11-23 devnull 	c->heads[h] = b;
428 7763a61a 2003-11-23 devnull 	if(b->next != nil)
429 7763a61a 2003-11-23 devnull 		b->next->prev = b;
430 7763a61a 2003-11-23 devnull 	b->prev = nil;
431 7763a61a 2003-11-23 devnull 
432 7763a61a 2003-11-23 devnull 	memmove(b->score, score, VtScoreSize);	
433 7763a61a 2003-11-23 devnull 	b->type = type;
434 7763a61a 2003-11-23 devnull 	b->state = LumpFree;
435 7763a61a 2003-11-23 devnull 
436 7763a61a 2003-11-23 devnull found:
437 7763a61a 2003-11-23 devnull 	b->ref++;
438 7763a61a 2003-11-23 devnull 	b->used2 = b->used;
439 7763a61a 2003-11-23 devnull 	b->used = c->now++;
440 7763a61a 2003-11-23 devnull 	if(b->heap != BadHeap)
441 7763a61a 2003-11-23 devnull 		fixHeap(b->heap, b);
442 7763a61a 2003-11-23 devnull 
443 7763a61a 2003-11-23 devnull 	vtUnlock(c->lk);
444 7763a61a 2003-11-23 devnull 
445 7763a61a 2003-11-23 devnull 	vtLock(b->lk);
446 7763a61a 2003-11-23 devnull 	if(b->state != LumpFree)
447 7763a61a 2003-11-23 devnull 		return b;
448 7763a61a 2003-11-23 devnull 	
449 7763a61a 2003-11-23 devnull 	n = vtRead(c->z, score, type, b->data, size);
450 7763a61a 2003-11-23 devnull 	if(n < 0) {
451 7763a61a 2003-11-23 devnull 		lumpDecRef(b, 1);
452 7763a61a 2003-11-23 devnull 		return nil;
453 7763a61a 2003-11-23 devnull 	}
454 7763a61a 2003-11-23 devnull 	if(!vtSha1Check(score, b->data, n)) {
455 7763a61a 2003-11-23 devnull 		vtSetError("vtSha1Check failed");
456 7763a61a 2003-11-23 devnull 		lumpDecRef(b, 1);
457 7763a61a 2003-11-23 devnull 		return nil;
458 7763a61a 2003-11-23 devnull 	}
459 7763a61a 2003-11-23 devnull 	vtZeroExtend(type, b->data, n, size);
460 7763a61a 2003-11-23 devnull 	b->asize = size;
461 7763a61a 2003-11-23 devnull 	lumpSetState(b, LumpVenti);
462 7763a61a 2003-11-23 devnull 
463 7763a61a 2003-11-23 devnull 	return b;
464 7763a61a 2003-11-23 devnull }
465 7763a61a 2003-11-23 devnull 
466 7763a61a 2003-11-23 devnull static char *
467 7763a61a 2003-11-23 devnull lumpState(int state)
468 7763a61a 2003-11-23 devnull {
469 7763a61a 2003-11-23 devnull 	switch(state) {
470 7763a61a 2003-11-23 devnull 	default:
471 7763a61a 2003-11-23 devnull 		return "Unknown!!";
472 7763a61a 2003-11-23 devnull 	case LumpFree:
473 7763a61a 2003-11-23 devnull 		return "Free";
474 7763a61a 2003-11-23 devnull 	case LumpActive:
475 7763a61a 2003-11-23 devnull 		return "Active";
476 7763a61a 2003-11-23 devnull 	case LumpSnap:
477 7763a61a 2003-11-23 devnull 		return "Snap";
478 7763a61a 2003-11-23 devnull 	case LumpZombie:
479 7763a61a 2003-11-23 devnull 		return "Zombie";
480 7763a61a 2003-11-23 devnull 	case LumpVenti:
481 7763a61a 2003-11-23 devnull 		return "Venti";
482 7763a61a 2003-11-23 devnull 	}
483 7763a61a 2003-11-23 devnull }
484 7763a61a 2003-11-23 devnull 
485 7763a61a 2003-11-23 devnull static void
486 7763a61a 2003-11-23 devnull lumpSetState(Lump *u, int state)
487 7763a61a 2003-11-23 devnull {
488 7763a61a 2003-11-23 devnull //	if(u->state != LumpFree)
489 7763a61a 2003-11-23 devnull //		fprint(2, "%V: %s -> %s\n", u->score, lumpState(u->state), lumpState(state));
490 7763a61a 2003-11-23 devnull 	u->state = state;
491 7763a61a 2003-11-23 devnull }
492 7763a61a 2003-11-23 devnull 	
493 7763a61a 2003-11-23 devnull int
494 7763a61a 2003-11-23 devnull lumpGetScore(Lump *u, int offset, uchar score[VtScoreSize])
495 7763a61a 2003-11-23 devnull {
496 7763a61a 2003-11-23 devnull 	uchar *sp;
497 7763a61a 2003-11-23 devnull 	VtRoot root;
498 7763a61a 2003-11-23 devnull 	VtEntry dir;
499 7763a61a 2003-11-23 devnull 
500 7763a61a 2003-11-23 devnull 	vtLock(u->lk);
501 7763a61a 2003-11-23 devnull 
502 7763a61a 2003-11-23 devnull 	switch(u->type) {
503 7763a61a 2003-11-23 devnull 	default:
504 7763a61a 2003-11-23 devnull 		vtSetError("bad type");
505 7763a61a 2003-11-23 devnull 		goto Err;
506 7763a61a 2003-11-23 devnull 	case VtPointerType0:
507 7763a61a 2003-11-23 devnull 	case VtPointerType1:
508 7763a61a 2003-11-23 devnull 	case VtPointerType2:
509 7763a61a 2003-11-23 devnull 	case VtPointerType3:
510 7763a61a 2003-11-23 devnull 	case VtPointerType4:
511 7763a61a 2003-11-23 devnull 	case VtPointerType5:
512 7763a61a 2003-11-23 devnull 	case VtPointerType6:
513 7763a61a 2003-11-23 devnull 		if((offset+1)*VtScoreSize > u->asize)
514 7763a61a 2003-11-23 devnull 			sp = nil;
515 7763a61a 2003-11-23 devnull 		else
516 7763a61a 2003-11-23 devnull 			sp = u->data + offset*VtScoreSize;
517 7763a61a 2003-11-23 devnull 		break;
518 7763a61a 2003-11-23 devnull 	case VtRootType:
519 7763a61a 2003-11-23 devnull 		if(u->asize < VtRootSize) {
520 7763a61a 2003-11-23 devnull 			vtSetError("runt root block");
521 7763a61a 2003-11-23 devnull 			goto Err;
522 7763a61a 2003-11-23 devnull 		}
523 7763a61a 2003-11-23 devnull 		if(!vtRootUnpack(&root, u->data))
524 7763a61a 2003-11-23 devnull 			goto Err;
525 7763a61a 2003-11-23 devnull 		sp = root.score;
526 7763a61a 2003-11-23 devnull 		break;
527 7763a61a 2003-11-23 devnull 	case VtDirType:
528 7763a61a 2003-11-23 devnull 		if((offset+1)*VtEntrySize > u->asize) {
529 7763a61a 2003-11-23 devnull 			vtSetError(ENoDir);
530 7763a61a 2003-11-23 devnull 			goto Err;
531 7763a61a 2003-11-23 devnull 		}
532 7763a61a 2003-11-23 devnull 		if(!vtEntryUnpack(&dir, u->data, offset))
533 7763a61a 2003-11-23 devnull 			goto Err;
534 7763a61a 2003-11-23 devnull 		if(!dir.flags & VtEntryActive) {
535 7763a61a 2003-11-23 devnull 			vtSetError(ENoDir);
536 7763a61a 2003-11-23 devnull 			goto Err;
537 7763a61a 2003-11-23 devnull 		}
538 7763a61a 2003-11-23 devnull 		sp = dir.score;
539 7763a61a 2003-11-23 devnull 		break;
540 7763a61a 2003-11-23 devnull 	}
541 7763a61a 2003-11-23 devnull 
542 7763a61a 2003-11-23 devnull 	if(sp == nil)
543 7763a61a 2003-11-23 devnull 		memmove(score, vtZeroScore, VtScoreSize);
544 7763a61a 2003-11-23 devnull 	else
545 7763a61a 2003-11-23 devnull 		memmove(score, sp, VtScoreSize);
546 7763a61a 2003-11-23 devnull 
547 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
548 7763a61a 2003-11-23 devnull 	return !scoreIsLocal(score);
549 7763a61a 2003-11-23 devnull Err:
550 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
551 7763a61a 2003-11-23 devnull 	return 0;
552 7763a61a 2003-11-23 devnull }
553 7763a61a 2003-11-23 devnull 
554 7763a61a 2003-11-23 devnull Lump *
555 7763a61a 2003-11-23 devnull lumpWalk(Lump *u, int offset, int type, int size, int readOnly, int lock)
556 7763a61a 2003-11-23 devnull {
557 7763a61a 2003-11-23 devnull 	Lump *v, *vv;
558 7763a61a 2003-11-23 devnull 	Cache *c;
559 7763a61a 2003-11-23 devnull 	uchar score[VtScoreSize], *sp;
560 7763a61a 2003-11-23 devnull 	VtRoot root;
561 7763a61a 2003-11-23 devnull 	VtEntry dir;
562 7763a61a 2003-11-23 devnull 	int split, isdir;
563 7763a61a 2003-11-23 devnull 
564 7763a61a 2003-11-23 devnull 	c = u->c;
565 7763a61a 2003-11-23 devnull 	vtLock(u->lk);
566 7763a61a 2003-11-23 devnull 
567 7763a61a 2003-11-23 devnull Again:
568 7763a61a 2003-11-23 devnull 	v = nil;
569 7763a61a 2003-11-23 devnull 	vv = nil;
570 7763a61a 2003-11-23 devnull 
571 7763a61a 2003-11-23 devnull 	isdir = u->dir;
572 7763a61a 2003-11-23 devnull 	switch(u->type) {
573 7763a61a 2003-11-23 devnull 	default:
574 7763a61a 2003-11-23 devnull 		vtSetError("bad type");
575 7763a61a 2003-11-23 devnull 		goto Err;
576 7763a61a 2003-11-23 devnull 	case VtPointerType0:
577 7763a61a 2003-11-23 devnull 	case VtPointerType1:
578 7763a61a 2003-11-23 devnull 	case VtPointerType2:
579 7763a61a 2003-11-23 devnull 	case VtPointerType3:
580 7763a61a 2003-11-23 devnull 	case VtPointerType4:
581 7763a61a 2003-11-23 devnull 	case VtPointerType5:
582 7763a61a 2003-11-23 devnull 	case VtPointerType6:
583 7763a61a 2003-11-23 devnull 		if((offset+1)*VtScoreSize > u->asize)
584 7763a61a 2003-11-23 devnull 			sp = nil;
585 7763a61a 2003-11-23 devnull 		else
586 7763a61a 2003-11-23 devnull 			sp = u->data + offset*VtScoreSize;
587 7763a61a 2003-11-23 devnull 		break;
588 7763a61a 2003-11-23 devnull 	case VtRootType:
589 7763a61a 2003-11-23 devnull 		if(u->asize < VtRootSize) {
590 7763a61a 2003-11-23 devnull 			vtSetError("runt root block");
591 7763a61a 2003-11-23 devnull 			goto Err;
592 7763a61a 2003-11-23 devnull 		}
593 7763a61a 2003-11-23 devnull 		if(!vtRootUnpack(&root, u->data))
594 7763a61a 2003-11-23 devnull 			goto Err;
595 7763a61a 2003-11-23 devnull 		sp = root.score;
596 7763a61a 2003-11-23 devnull 		break;
597 7763a61a 2003-11-23 devnull 	case VtDirType:
598 7763a61a 2003-11-23 devnull 		if((offset+1)*VtEntrySize > u->asize) {
599 7763a61a 2003-11-23 devnull 			vtSetError(ENoDir);
600 7763a61a 2003-11-23 devnull 			goto Err;
601 7763a61a 2003-11-23 devnull 		}
602 7763a61a 2003-11-23 devnull 		if(!vtEntryUnpack(&dir, u->data, offset))
603 7763a61a 2003-11-23 devnull 			goto Err;
604 7763a61a 2003-11-23 devnull 		if(!(dir.flags & VtEntryActive)) {
605 7763a61a 2003-11-23 devnull 			vtSetError(ENoDir);
606 7763a61a 2003-11-23 devnull 			goto Err;
607 7763a61a 2003-11-23 devnull 		}
608 7763a61a 2003-11-23 devnull 		isdir = (dir.flags & VtEntryDir) != 0;
609 7763a61a 2003-11-23 devnull //		sp = dir.score;
610 7763a61a 2003-11-23 devnull 		sp = u->data + offset*VtEntrySize + 20;
611 7763a61a 2003-11-23 devnull 		break;
612 7763a61a 2003-11-23 devnull 	}
613 7763a61a 2003-11-23 devnull 
614 7763a61a 2003-11-23 devnull 	if(sp == nil)
615 7763a61a 2003-11-23 devnull 		memmove(score, vtZeroScore, VtScoreSize);
616 7763a61a 2003-11-23 devnull 	else
617 7763a61a 2003-11-23 devnull 		memmove(score, sp, VtScoreSize);
618 7763a61a 2003-11-23 devnull 	
619 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
620 7763a61a 2003-11-23 devnull 
621 7763a61a 2003-11-23 devnull 
622 7763a61a 2003-11-23 devnull if(0)fprint(2, "lumpWalk: %V:%s %d:%d-> %V:%d\n", u->score, lumpState(u->state), u->type, offset, score, type);
623 7763a61a 2003-11-23 devnull 	v = cacheGetLump(c, score, type, size);
624 7763a61a 2003-11-23 devnull 	if(v == nil)
625 7763a61a 2003-11-23 devnull 		return nil;
626 7763a61a 2003-11-23 devnull 
627 7763a61a 2003-11-23 devnull 	split = 1;
628 7763a61a 2003-11-23 devnull 	if(readOnly)
629 7763a61a 2003-11-23 devnull 		split = 0;
630 7763a61a 2003-11-23 devnull 
631 7763a61a 2003-11-23 devnull 	switch(v->state) {
632 7763a61a 2003-11-23 devnull 	default:
633 7763a61a 2003-11-23 devnull 		assert(0);
634 7763a61a 2003-11-23 devnull 	case LumpFree:
635 7763a61a 2003-11-23 devnull fprint(2, "block is free %V!\n", v->score);
636 7763a61a 2003-11-23 devnull 		vtSetError("phase error");
637 7763a61a 2003-11-23 devnull 		goto Err2;
638 7763a61a 2003-11-23 devnull 	case LumpActive:	
639 7763a61a 2003-11-23 devnull 		if(v->gen < u->gen) {
640 7763a61a 2003-11-23 devnull print("LumpActive gen\n");
641 7763a61a 2003-11-23 devnull 			lumpSetState(v, LumpSnap);
642 7763a61a 2003-11-23 devnull 			v->gen = u->gen;
643 7763a61a 2003-11-23 devnull 		} else
644 7763a61a 2003-11-23 devnull 			split = 0;
645 7763a61a 2003-11-23 devnull 		break;
646 7763a61a 2003-11-23 devnull 	case LumpSnap:
647 7763a61a 2003-11-23 devnull 	case LumpVenti:
648 7763a61a 2003-11-23 devnull 		break;
649 7763a61a 2003-11-23 devnull 	}
650 7763a61a 2003-11-23 devnull 	
651 7763a61a 2003-11-23 devnull 	/* easy case */
652 7763a61a 2003-11-23 devnull 	if(!split) {
653 7763a61a 2003-11-23 devnull 		if(!lock)
654 7763a61a 2003-11-23 devnull 			vtUnlock(v->lk);
655 7763a61a 2003-11-23 devnull 		return v;
656 7763a61a 2003-11-23 devnull 	}
657 7763a61a 2003-11-23 devnull 
658 7763a61a 2003-11-23 devnull 	if(sp == nil) {
659 7763a61a 2003-11-23 devnull 		vtSetError("bad offset");
660 7763a61a 2003-11-23 devnull 		goto Err2;
661 7763a61a 2003-11-23 devnull 	}
662 7763a61a 2003-11-23 devnull 
663 7763a61a 2003-11-23 devnull 	vv = cacheAllocLump(c, v->type, size, isdir);
664 7763a61a 2003-11-23 devnull 	/* vv is locked */
665 7763a61a 2003-11-23 devnull 	vv->gen = u->gen;
666 7763a61a 2003-11-23 devnull 	memmove(vv->data, v->data, v->asize);
667 7763a61a 2003-11-23 devnull if(0)fprint(2, "split %V into %V\n", v->score, vv->score);
668 7763a61a 2003-11-23 devnull 
669 7763a61a 2003-11-23 devnull 	lumpDecRef(v, 1);
670 7763a61a 2003-11-23 devnull 	v = nil;
671 7763a61a 2003-11-23 devnull 
672 7763a61a 2003-11-23 devnull 	vtLock(u->lk);
673 7763a61a 2003-11-23 devnull 	if(u->state != LumpActive) {
674 7763a61a 2003-11-23 devnull 		vtSetError("bad parent state: can not happen");
675 7763a61a 2003-11-23 devnull 		goto Err;
676 7763a61a 2003-11-23 devnull 	}
677 7763a61a 2003-11-23 devnull 
678 7763a61a 2003-11-23 devnull 	/* check that nothing changed underfoot */
679 7763a61a 2003-11-23 devnull 	if(memcmp(sp, score, VtScoreSize) != 0) {
680 7763a61a 2003-11-23 devnull 		lumpDecRef(vv, 1);
681 7763a61a 2003-11-23 devnull fprint(2, "lumpWalk: parent changed under foot\n");
682 7763a61a 2003-11-23 devnull 		goto Again;
683 7763a61a 2003-11-23 devnull 	}
684 7763a61a 2003-11-23 devnull 
685 7763a61a 2003-11-23 devnull 	/* XXX - hold Active blocks up - will go eventually */
686 7763a61a 2003-11-23 devnull 	lumpIncRef(vv);
687 7763a61a 2003-11-23 devnull 
688 7763a61a 2003-11-23 devnull 	/* change the parent */
689 7763a61a 2003-11-23 devnull 	memmove(sp, vv->score, VtScoreSize);
690 7763a61a 2003-11-23 devnull 	
691 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
692 7763a61a 2003-11-23 devnull 	
693 7763a61a 2003-11-23 devnull 	if(!lock)
694 7763a61a 2003-11-23 devnull 		vtUnlock(vv->lk);
695 7763a61a 2003-11-23 devnull 	return vv;
696 7763a61a 2003-11-23 devnull Err:
697 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
698 7763a61a 2003-11-23 devnull 	lumpDecRef(v, 0);
699 7763a61a 2003-11-23 devnull 	lumpDecRef(vv, 1);
700 7763a61a 2003-11-23 devnull 	return nil;
701 7763a61a 2003-11-23 devnull Err2:
702 7763a61a 2003-11-23 devnull 	lumpDecRef(v, 1);
703 7763a61a 2003-11-23 devnull 	return nil;
704 7763a61a 2003-11-23 devnull 	
705 7763a61a 2003-11-23 devnull }
706 7763a61a 2003-11-23 devnull 
707 7763a61a 2003-11-23 devnull void
708 7763a61a 2003-11-23 devnull lumpFreeEntry(Lump *u, int entry)
709 7763a61a 2003-11-23 devnull {
710 7763a61a 2003-11-23 devnull 	uchar score[VtScoreSize];
711 7763a61a 2003-11-23 devnull 	int type;
712 7763a61a 2003-11-23 devnull 	ulong gen;
713 7763a61a 2003-11-23 devnull 	VtEntry dir;
714 7763a61a 2003-11-23 devnull 	Cache *c;
715 7763a61a 2003-11-23 devnull 
716 7763a61a 2003-11-23 devnull 	c = u->c;
717 7763a61a 2003-11-23 devnull 	vtLock(u->lk);
718 7763a61a 2003-11-23 devnull 	if(u->state == LumpVenti)
719 7763a61a 2003-11-23 devnull 		goto Exit;
720 7763a61a 2003-11-23 devnull 
721 7763a61a 2003-11-23 devnull 	switch(u->type) {
722 7763a61a 2003-11-23 devnull 	default:
723 7763a61a 2003-11-23 devnull 		fprint(2, "freeing bad lump type: %d\n", u->type);
724 7763a61a 2003-11-23 devnull 		return;
725 7763a61a 2003-11-23 devnull 	case VtPointerType0:
726 7763a61a 2003-11-23 devnull 		if((entry+1)*VtScoreSize > u->asize)
727 7763a61a 2003-11-23 devnull 			goto Exit;
728 7763a61a 2003-11-23 devnull 		memmove(score, u->data + entry*VtScoreSize, VtScoreSize);
729 7763a61a 2003-11-23 devnull 		memmove(u->data + entry*VtScoreSize, vtZeroScore, VtScoreSize);
730 7763a61a 2003-11-23 devnull 		type = u->dir?VtDirType:VtDataType;
731 7763a61a 2003-11-23 devnull 		break;
732 7763a61a 2003-11-23 devnull 	case VtPointerType1:
733 7763a61a 2003-11-23 devnull 	case VtPointerType2:
734 7763a61a 2003-11-23 devnull 	case VtPointerType3:
735 7763a61a 2003-11-23 devnull 	case VtPointerType4:
736 7763a61a 2003-11-23 devnull 	case VtPointerType5:
737 7763a61a 2003-11-23 devnull 	case VtPointerType6:
738 7763a61a 2003-11-23 devnull 		if((entry+1)*VtScoreSize > u->asize)
739 7763a61a 2003-11-23 devnull 			goto Exit;
740 7763a61a 2003-11-23 devnull 		memmove(score, u->data + entry*VtScoreSize, VtScoreSize);
741 7763a61a 2003-11-23 devnull 		memmove(u->data + entry*VtScoreSize, vtZeroScore, VtScoreSize);
742 7763a61a 2003-11-23 devnull 		type = u->type-1;
743 7763a61a 2003-11-23 devnull 		break;
744 7763a61a 2003-11-23 devnull 	case VtDirType:
745 7763a61a 2003-11-23 devnull 		if((entry+1)*VtEntrySize > u->asize)
746 7763a61a 2003-11-23 devnull 			goto Exit;
747 7763a61a 2003-11-23 devnull 		if(!vtEntryUnpack(&dir, u->data, entry))
748 7763a61a 2003-11-23 devnull 			goto Exit;
749 7763a61a 2003-11-23 devnull 		if(!dir.flags & VtEntryActive)
750 7763a61a 2003-11-23 devnull 			goto Exit;
751 7763a61a 2003-11-23 devnull 		gen = dir.gen;
752 7763a61a 2003-11-23 devnull 		if(gen != ~0)
753 7763a61a 2003-11-23 devnull 			gen++;
754 7763a61a 2003-11-23 devnull 		if(dir.depth == 0)
755 7763a61a 2003-11-23 devnull 			type = (dir.flags&VtEntryDir)?VtDirType:VtDataType;
756 7763a61a 2003-11-23 devnull 		else
757 7763a61a 2003-11-23 devnull 			type = VtPointerType0 + dir.depth - 1;
758 7763a61a 2003-11-23 devnull 		memmove(score, dir.score, VtScoreSize);
759 7763a61a 2003-11-23 devnull 		memset(&dir, 0, sizeof(dir));
760 7763a61a 2003-11-23 devnull 		dir.gen = gen;
761 7763a61a 2003-11-23 devnull 		vtEntryPack(&dir, u->data, entry);
762 7763a61a 2003-11-23 devnull 		break;
763 7763a61a 2003-11-23 devnull 	case VtDataType:
764 7763a61a 2003-11-23 devnull 		type = VtErrType;
765 7763a61a 2003-11-23 devnull 		break;
766 7763a61a 2003-11-23 devnull 	}
767 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
768 7763a61a 2003-11-23 devnull 	if(type == VtErrType || !scoreIsLocal(score))
769 7763a61a 2003-11-23 devnull 		return;
770 7763a61a 2003-11-23 devnull 
771 7763a61a 2003-11-23 devnull 	u = cacheGetLump(c, score, type, c->size);
772 7763a61a 2003-11-23 devnull 	if(u == nil)
773 7763a61a 2003-11-23 devnull 		return;
774 7763a61a 2003-11-23 devnull 	lumpDecRef(u, 1);
775 7763a61a 2003-11-23 devnull 	/* XXX remove extra reference */
776 7763a61a 2003-11-23 devnull 	lumpDecRef(u, 0);
777 7763a61a 2003-11-23 devnull 	return;
778 7763a61a 2003-11-23 devnull Exit:
779 7763a61a 2003-11-23 devnull 	vtUnlock(u->lk);
780 7763a61a 2003-11-23 devnull 	return;
781 7763a61a 2003-11-23 devnull 
782 7763a61a 2003-11-23 devnull }
783 7763a61a 2003-11-23 devnull 
784 7763a61a 2003-11-23 devnull void
785 7763a61a 2003-11-23 devnull lumpCleanup(Lump *u)
786 7763a61a 2003-11-23 devnull {
787 7763a61a 2003-11-23 devnull 	int i, n;
788 7763a61a 2003-11-23 devnull 
789 7763a61a 2003-11-23 devnull 	switch(u->type) {
790 7763a61a 2003-11-23 devnull 	default:
791 7763a61a 2003-11-23 devnull 		return;
792 7763a61a 2003-11-23 devnull 	case VtPointerType0:
793 7763a61a 2003-11-23 devnull 	case VtPointerType1:
794 7763a61a 2003-11-23 devnull 	case VtPointerType2:
795 7763a61a 2003-11-23 devnull 	case VtPointerType3:
796 7763a61a 2003-11-23 devnull 	case VtPointerType4:
797 7763a61a 2003-11-23 devnull 	case VtPointerType5:
798 7763a61a 2003-11-23 devnull 	case VtPointerType6:
799 7763a61a 2003-11-23 devnull 		n = u->asize/VtScoreSize;
800 7763a61a 2003-11-23 devnull 		break;	
801 7763a61a 2003-11-23 devnull 	case VtDirType:
802 7763a61a 2003-11-23 devnull 		n = u->asize/VtEntrySize;
803 7763a61a 2003-11-23 devnull 		break;
804 7763a61a 2003-11-23 devnull 	}
805 7763a61a 2003-11-23 devnull 
806 7763a61a 2003-11-23 devnull 	for(i=0; i<n; i++)
807 7763a61a 2003-11-23 devnull 		lumpFreeEntry(u, i);
808 7763a61a 2003-11-23 devnull }
809 7763a61a 2003-11-23 devnull 
810 7763a61a 2003-11-23 devnull 
811 7763a61a 2003-11-23 devnull void
812 7763a61a 2003-11-23 devnull lumpDecRef(Lump *b, int unlock)
813 7763a61a 2003-11-23 devnull {
814 7763a61a 2003-11-23 devnull 	int i;
815 7763a61a 2003-11-23 devnull 	Cache *c;
816 7763a61a 2003-11-23 devnull 
817 7763a61a 2003-11-23 devnull 	if(b == nil)
818 7763a61a 2003-11-23 devnull 		return;
819 7763a61a 2003-11-23 devnull 
820 7763a61a 2003-11-23 devnull 	if(unlock)
821 7763a61a 2003-11-23 devnull 		vtUnlock(b->lk);
822 7763a61a 2003-11-23 devnull 
823 7763a61a 2003-11-23 devnull 	c = b->c;
824 7763a61a 2003-11-23 devnull 	vtLock(c->lk);
825 7763a61a 2003-11-23 devnull 	if(--b->ref > 0) {
826 7763a61a 2003-11-23 devnull 		vtUnlock(c->lk);
827 7763a61a 2003-11-23 devnull 		return;
828 7763a61a 2003-11-23 devnull 	}
829 7763a61a 2003-11-23 devnull 	assert(b->ref == 0);
830 7763a61a 2003-11-23 devnull 
831 7763a61a 2003-11-23 devnull 	switch(b->state) {
832 7763a61a 2003-11-23 devnull 	default:
833 7763a61a 2003-11-23 devnull 		fprint(2, "bad state: %s\n", lumpState(b->state));
834 7763a61a 2003-11-23 devnull 		assert(0);
835 7763a61a 2003-11-23 devnull 	case LumpActive:
836 7763a61a 2003-11-23 devnull 		/* hack - but will do for now */
837 7763a61a 2003-11-23 devnull 		b->ref++;
838 7763a61a 2003-11-23 devnull 		vtUnlock(c->lk);
839 7763a61a 2003-11-23 devnull 		lumpCleanup(b);
840 7763a61a 2003-11-23 devnull 		vtLock(c->lk);
841 7763a61a 2003-11-23 devnull 		b->ref--;
842 7763a61a 2003-11-23 devnull 		lumpSetState(b, LumpFree);
843 7763a61a 2003-11-23 devnull 		break;
844 7763a61a 2003-11-23 devnull 	case LumpZombie:
845 7763a61a 2003-11-23 devnull 		lumpSetState(b, LumpFree);
846 7763a61a 2003-11-23 devnull 		break;
847 7763a61a 2003-11-23 devnull 	case LumpFree:
848 7763a61a 2003-11-23 devnull 	case LumpVenti:
849 7763a61a 2003-11-23 devnull 		break;
850 7763a61a 2003-11-23 devnull 	}
851 7763a61a 2003-11-23 devnull 
852 7763a61a 2003-11-23 devnull 	/*
853 7763a61a 2003-11-23 devnull 	 * reinsert in the free heap
854 7763a61a 2003-11-23 devnull 	 */
855 7763a61a 2003-11-23 devnull 	if(b->heap == BadHeap) {
856 7763a61a 2003-11-23 devnull 		i = upHeap(c->nheap++, b);
857 7763a61a 2003-11-23 devnull 		c->heap[i] = b;
858 7763a61a 2003-11-23 devnull 		b->heap = i;
859 7763a61a 2003-11-23 devnull 	}
860 7763a61a 2003-11-23 devnull 
861 7763a61a 2003-11-23 devnull 	vtUnlock(c->lk);
862 7763a61a 2003-11-23 devnull }
863 7763a61a 2003-11-23 devnull 
864 7763a61a 2003-11-23 devnull Lump *
865 7763a61a 2003-11-23 devnull lumpIncRef(Lump *b)
866 7763a61a 2003-11-23 devnull {
867 7763a61a 2003-11-23 devnull 	Cache *c;
868 7763a61a 2003-11-23 devnull 
869 7763a61a 2003-11-23 devnull 	c = b->c;
870 7763a61a 2003-11-23 devnull 
871 7763a61a 2003-11-23 devnull 	vtLock(c->lk);
872 7763a61a 2003-11-23 devnull 	assert(b->ref > 0);
873 7763a61a 2003-11-23 devnull 	b->ref++;
874 7763a61a 2003-11-23 devnull 	vtUnlock(c->lk);
875 7763a61a 2003-11-23 devnull 	return b;
876 7763a61a 2003-11-23 devnull }