op public repos

Blob

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