op public repos

Blob

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