op public repos

Blob

Date:: Wed Dec 14 20:06:43 2005 UTC
Message:: better errors
Actions:: History | Blame | Raw File
1 /*
2  * Memory-only VtBlock cache.
3  *
4  * The cached Venti blocks are in the hash chains.
5  * The cached local blocks are only in the blocks array.
6  * The free blocks are in the heap, which is supposed to
7  * be indexed by second-to-last use but actually
8  * appears to be last use.
9  */
10 
11 #include <u.h>
12 #include <libc.h>
13 #include <venti.h>
14 
15 int vtcachenread;
16 int vtcachencopy;
17 int vtcachenwrite;
18 
19 enum {
20 	BioLocal = 1,
21 	BioVenti,
22 	BioReading,
23 	BioWriting,
24 	BioEmpty,
25 	BioVentiError,
26 };
27 enum {
28 	BadHeap = ~0,
29 };
30 struct VtCache
31 {
32 	QLock	lk;
33 	VtConn	*z;
34 	u32int	blocksize;
35 	u32int	now;		/* ticks for usage time stamps */
36 	VtBlock	**hash;	/* hash table for finding addresses */
37 	int		nhash;
38 	VtBlock	**heap;	/* heap for finding victims */
39 	int		nheap;
40 	VtBlock	*block;	/* all allocated blocks */
41 	int		nblock;
42 	uchar	*mem;	/* memory for all blocks and data */
43 	int		(*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);
44 };
45 
46 static void cachecheck(VtCache*);
47 
48 VtCache*
49 vtcachealloc(VtConn *z, int blocksize, ulong nblock)
50 {
51 	uchar *p;
52 	VtCache *c;
53 	int i;
54 	VtBlock *b;
55 
56 	c = vtmallocz(sizeof(VtCache));
57 
58 	c->z = z;
59 	c->blocksize = (blocksize + 127) & ~127;
60 	c->nblock = nblock;
61 	c->nhash = nblock;
62 	c->hash = vtmallocz(nblock*sizeof(VtBlock*));
63 	c->heap = vtmallocz(nblock*sizeof(VtBlock*));
64 	c->block = vtmallocz(nblock*sizeof(VtBlock));
65 	c->mem = vtmallocz(nblock*c->blocksize);
66 	c->write = vtwrite;
67 
68 	p = c->mem;
69 	for(i=0; i<nblock; i++){
70 		b = &c->block[i];
71 		b->addr = NilBlock;
72 		b->c = c;
73 		b->data = p;
74 		b->heap = i;
75 		c->heap[i] = b;
76 		p += c->blocksize;
77 	}
78 	c->nheap = nblock;
79 	cachecheck(c);
80 	return c;
81 }
82 
83 /*
84  * BUG This is here so that vbackup can override it and do some
85  * pipelining of writes.  Arguably vtwrite or vtwritepacket or the
86  * cache itself should be providing this functionality.
87  */
88 void
89 vtcachesetwrite(VtCache *c, int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int))
90 {
91 	if(write == nil)
92 		write = vtwrite;
93 	c->write = write;
94 }
95 
96 void
97 vtcachefree(VtCache *c)
98 {
99 	int i;
100 
101 	qlock(&c->lk);
102 
103 	cachecheck(c);
104 	for(i=0; i<c->nblock; i++)
105 		assert(c->block[i].ref == 0);
106 
107 	vtfree(c->hash);
108 	vtfree(c->heap);
109 	vtfree(c->block);
110 	vtfree(c->mem);
111 	vtfree(c);
112 }
113 
114 static void
115 vtcachedump(VtCache *c)
116 {
117 	int i;
118 	VtBlock *b;
119 
120 	for(i=0; i<c->nblock; i++){
121 		b = &c->block[i];
122 		print("cache block %d: type %d score %V iostate %d addr %d ref %d nlock %d\n",
123 			i, b->type, b->score, b->iostate, b->addr, b->ref, b->nlock);
124 	}
125 }
126 
127 static void
128 cachecheck(VtCache *c)
129 {
130 	u32int size, now;
131 	int i, k, refed;
132 	VtBlock *b;
133 
134 	size = c->blocksize;
135 	now = c->now;
136 
137 	for(i = 0; i < c->nheap; i++){
138 		if(c->heap[i]->heap != i)
139 			sysfatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
140 		if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
141 			sysfatal("bad heap ordering");
142 		k = (i << 1) + 1;
143 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
144 			sysfatal("bad heap ordering");
145 		k++;
146 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
147 			sysfatal("bad heap ordering");
148 	}
149 
150 	refed = 0;
151 	for(i = 0; i < c->nblock; i++){
152 		b = &c->block[i];
153 		if(b->data != &c->mem[i * size])
154 			sysfatal("mis-blocked at %d", i);
155 		if(b->ref && b->heap == BadHeap)
156 			refed++;
157 		else if(b->addr != NilBlock)
158 			refed++;
159 	}
160 if(c->nheap + refed != c->nblock){
161 fprint(2, "cachecheck: nheap %d refed %d nblocks %d\n", c->nheap, refed, c->nblock);
162 //vtcachedump(c);
163 }
164 	assert(c->nheap + refed == c->nblock);
165 	refed = 0;
166 	for(i = 0; i < c->nblock; i++){
167 		b = &c->block[i];
168 		if(b->ref){
169 if(1)fprint(2, "a=%ud %V ref=%d\n", b->addr, b->score, b->ref);
170 			refed++;
171 		}
172 	}
173 if(refed > 0)fprint(2, "cachecheck: in used %d\n", refed);
174 }
175 
176 static int
177 upheap(int i, VtBlock *b)
178 {
179 	VtBlock *bb;
180 	u32int now;
181 	int p;
182 	VtCache *c;
183 	
184 	c = b->c;
185 	now = c->now;
186 	for(; i != 0; i = p){
187 		p = (i - 1) >> 1;
188 		bb = c->heap[p];
189 		if(b->used - now >= bb->used - now)
190 			break;
191 		c->heap[i] = bb;
192 		bb->heap = i;
193 	}
194 	c->heap[i] = b;
195 	b->heap = i;
196 
197 	return i;
198 }
199 
200 static int
201 downheap(int i, VtBlock *b)
202 {
203 	VtBlock *bb;
204 	u32int now;
205 	int k;
206 	VtCache *c;
207 	
208 	c = b->c;
209 	now = c->now;
210 	for(; ; i = k){
211 		k = (i << 1) + 1;
212 		if(k >= c->nheap)
213 			break;
214 		if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
215 			k++;
216 		bb = c->heap[k];
217 		if(b->used - now <= bb->used - now)
218 			break;
219 		c->heap[i] = bb;
220 		bb->heap = i;
221 	}
222 	c->heap[i] = b;
223 	b->heap = i;
224 	return i;
225 }
226 
227 /*
228  * Delete a block from the heap.
229  * Called with c->lk held.
230  */
231 static void
232 heapdel(VtBlock *b)
233 {
234 	int i, si;
235 	VtCache *c;
236 
237 	c = b->c;
238 
239 	si = b->heap;
240 	if(si == BadHeap)
241 		return;
242 	b->heap = BadHeap;
243 	c->nheap--;
244 	if(si == c->nheap)
245 		return;
246 	b = c->heap[c->nheap];
247 	i = upheap(si, b);
248 	if(i == si)
249 		downheap(i, b);
250 }
251 
252 /*
253  * Insert a block into the heap.
254  * Called with c->lk held.
255  */
256 static void
257 heapins(VtBlock *b)
258 {
259 	assert(b->heap == BadHeap);
260 	upheap(b->c->nheap++, b);
261 }
262 
263 /*
264  * locate the vtBlock with the oldest second to last use.
265  * remove it from the heap, and fix up the heap.
266  */
267 /* called with c->lk held */
268 static VtBlock*
269 vtcachebumpblock(VtCache *c)
270 {
271 	VtBlock *b;
272 
273 	/*
274 	 * locate the vtBlock with the oldest second to last use.
275 	 * remove it from the heap, and fix up the heap.
276 	 */
277 	if(c->nheap == 0){
278 		vtcachedump(c);
279 		fprint(2, "vtcachebumpblock: no free blocks in vtCache");
280 		abort();
281 	}
282 	b = c->heap[0];
283 	heapdel(b);
284 
285 	assert(b->heap == BadHeap);
286 	assert(b->ref == 0);
287 
288 	/*
289 	 * unchain the vtBlock from hash chain if any
290 	 */
291 	if(b->prev){
292 		*(b->prev) = b->next;
293 		if(b->next)
294 			b->next->prev = b->prev;
295 		b->prev = nil;
296 	}
297 
298  	
299 if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
300 	/* set vtBlock to a reasonable state */
301 	b->ref = 1;
302 	b->iostate = BioEmpty;
303 	return b;
304 }
305 
306 /*
307  * fetch a local block from the memory cache.
308  * if it's not there, load it, bumping some other Block.
309  * if we're out of free blocks, we're screwed.
310  */
311 VtBlock*
312 vtcachelocal(VtCache *c, u32int addr, int type)
313 {
314 	VtBlock *b;
315 
316 	if(addr == 0)
317 		sysfatal("vtcachelocal: asked for nonexistent block 0");
318 	if(addr > c->nblock)
319 		sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",
320 			addr, c->nblock);
321 
322 	b = &c->block[addr-1];
323 	if(b->addr == NilBlock || b->iostate != BioLocal)
324 		sysfatal("vtcachelocal: block is not local");
325 
326 	if(b->type != type)
327 		sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type);
328 
329 	qlock(&c->lk);
330 	b->ref++;
331 	qunlock(&c->lk);
332 
333 	qlock(&b->lk);
334 	b->nlock = 1;
335 	return b;
336 }
337 
338 VtBlock*
339 vtcacheallocblock(VtCache *c, int type)
340 {
341 	VtBlock *b;
342 
343 	qlock(&c->lk);
344 	b = vtcachebumpblock(c);
345 	b->iostate = BioLocal;
346 	b->type = type;
347 	b->addr = (b - c->block)+1;
348 	vtzeroextend(type, b->data, 0, c->blocksize);
349 	vtlocaltoglobal(b->addr, b->score);
350 	qunlock(&c->lk);
351 
352 	qlock(&b->lk);
353 	b->nlock = 1;
354 
355 	return b;
356 }
357 
358 /*
359  * fetch a global (Venti) block from the memory cache.
360  * if it's not there, load it, bumping some other block.
361  */
362 VtBlock*
363 vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
364 {
365 	VtBlock *b;
366 	ulong h;
367 	int n;
368 	u32int addr;
369 
370 	addr = vtglobaltolocal(score);
371 	if(addr != NilBlock)
372 		return vtcachelocal(c, addr, type);
373 
374 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
375 
376 	/*
377 	 * look for the block in the cache
378 	 */
379 	qlock(&c->lk);
380 	for(b = c->hash[h]; b != nil; b = b->next){
381 		if(b->addr != NilBlock || memcmp(b->score, score, VtScoreSize) != 0 || b->type != type)
382 			continue;
383 		heapdel(b);
384 		b->ref++;
385 		qunlock(&c->lk);
386 		qlock(&b->lk);
387 		b->nlock = 1;
388 		if(b->iostate == BioVentiError){
389 			if(chattyventi)
390 				fprint(2, "cached read error for %V\n", score);
391 			werrstr("venti i/o error");
392 			vtblockput(b);
393 			return nil;
394 		}
395 		return b;
396 	}
397 
398 	/*
399 	 * not found
400 	 */
401 	b = vtcachebumpblock(c);
402 	b->addr = NilBlock;
403 	b->type = type;
404 	memmove(b->score, score, VtScoreSize);
405 	/* chain onto correct hash */
406 	b->next = c->hash[h];
407 	c->hash[h] = b;
408 	if(b->next != nil)
409 		b->next->prev = &b->next;
410 	b->prev = &c->hash[h];
411 
412 	/*
413 	 * Lock b before unlocking c, so that others wait while we read.
414 	 * 
415 	 * You might think there is a race between this qlock(b) before qunlock(c)
416 	 * and the qlock(c) while holding a qlock(b) in vtblockwrite.  However,
417 	 * the block here can never be the block in a vtblockwrite, so we're safe.
418 	 * We're certainly living on the edge.
419 	 */
420 	qlock(&b->lk);
421 	b->nlock = 1;
422 	qunlock(&c->lk);
423 
424 	vtcachenread++;
425 	n = vtread(c->z, score, type, b->data, c->blocksize);
426 	if(n < 0){
427 		if(chattyventi)
428 			fprint(2, "read %V: %r\n", score);
429 		b->iostate = BioVentiError;
430 		vtblockput(b);
431 		return nil;
432 	}
433 	vtzeroextend(type, b->data, n, c->blocksize);
434 	b->iostate = BioVenti;
435 	b->nlock = 1;
436 	return b;
437 }
438 
439 /*
440  * The thread that has locked b may refer to it by
441  * multiple names.  Nlock counts the number of
442  * references the locking thread holds.  It will call
443  * vtblockput once per reference.
444  */
445 void
446 vtblockduplock(VtBlock *b)
447 {
448 	assert(b->nlock > 0);
449 	b->nlock++;
450 }
451 
452 /*
453  * we're done with the block.
454  * unlock it.  can't use it after calling this.
455  */
456 void
457 vtblockput(VtBlock* b)
458 {
459 	VtCache *c;
460 
461 	if(b == nil)
462 		return;
463 
464 if(0)fprint(2, "vtblockput: %d: %x %d %d\n", getpid(), b->addr, c->nheap, b->iostate);
465 
466 	if(--b->nlock > 0)
467 		return;
468 
469 	/*
470 	 * b->nlock should probably stay at zero while
471 	 * the vtBlock is unlocked, but diskThread and vtSleep
472 	 * conspire to assume that they can just qlock(&b->lk); vtblockput(b),
473 	 * so we have to keep b->nlock set to 1 even 
474 	 * when the vtBlock is unlocked.
475 	 */
476 	assert(b->nlock == 0);
477 	b->nlock = 1;
478 
479 	qunlock(&b->lk);
480 	c = b->c;
481 	qlock(&c->lk);
482 
483 	if(--b->ref > 0){
484 		qunlock(&c->lk);
485 		return;
486 	}
487 
488 	assert(b->ref == 0);
489 	switch(b->iostate){
490 	case BioVenti:
491 //if(b->addr != NilBlock) print("blockput %d\n", b->addr);
492 		b->used = c->now++;
493 	case BioVentiError:
494 		heapins(b);
495 		break;
496 	case BioLocal:
497 		break;
498 	}
499 	qunlock(&c->lk);
500 }
501 
502 int
503 vtblockwrite(VtBlock *b)
504 {
505 	uchar score[VtScoreSize];
506 	VtCache *c;
507 	uint h;
508 	int n;
509 
510 	if(b->iostate != BioLocal){
511 		werrstr("vtblockwrite: not a local block");
512 		return -1;
513 	}
514 
515 	c = b->c;
516 	n = vtzerotruncate(b->type, b->data, c->blocksize);
517 	vtcachenwrite++;
518 	if(c->write(c->z, score, b->type, b->data, n) < 0)
519 		return -1;
520 
521 	memmove(b->score, score, VtScoreSize);
522 
523 	qlock(&c->lk);
524 	b->iostate = BioVenti;
525 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
526 	b->next = c->hash[h];
527 	c->hash[h] = b;
528 	if(b->next != nil)
529 		b->next->prev = &b->next;
530 	b->prev = &c->hash[h];
531 	qunlock(&c->lk);
532 	return 0;
533 }
534 
535 uint
536 vtcacheblocksize(VtCache *c)
537 {
538 	return c->blocksize;
539 }
540 
541 VtBlock*
542 vtblockcopy(VtBlock *b)
543 {
544 	VtBlock *bb;
545 
546 	vtcachencopy++;
547 	bb = vtcacheallocblock(b->c, b->type);
548 	if(bb == nil){
549 		vtblockput(b);
550 		return nil;
551 	}
552 	memmove(bb->data, b->data, b->c->blocksize);
553 	vtblockput(b);
554 	return bb;
555 }
556 
557 void
558 vtlocaltoglobal(u32int addr, uchar score[VtScoreSize])
559 {
560 	memset(score, 0, 16);
561 	score[16] = addr>>24;
562 	score[17] = addr>>16;
563 	score[18] = addr>>8;
564 	score[19] = addr;
565 }
566 
567 
568 u32int
569 vtglobaltolocal(uchar score[VtScoreSize])
570 {
571 	static uchar zero[16];
572 	if(memcmp(score, zero, 16) != 0)
573 		return NilBlock;
574 	return (score[16]<<24)|(score[17]<<16)|(score[18]<<8)|score[19];
575 }
576