op public repos

Blob

Date:: Sat Apr 21 19:43:09 2007 UTC
Message:: sync with plan 9
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 	assert(c->nheap + refed == c->nblock);
162 	refed = 0;
163 	for(i = 0; i < c->nblock; i++){
164 		b = &c->block[i];
165 		if(b->ref){
166 			refed++;
167 		}
168 	}
169 }
170 
171 static int
172 upheap(int i, VtBlock *b)
173 {
174 	VtBlock *bb;
175 	u32int now;
176 	int p;
177 	VtCache *c;
178 	
179 	c = b->c;
180 	now = c->now;
181 	for(; i != 0; i = p){
182 		p = (i - 1) >> 1;
183 		bb = c->heap[p];
184 		if(b->used - now >= bb->used - now)
185 			break;
186 		c->heap[i] = bb;
187 		bb->heap = i;
188 	}
189 	c->heap[i] = b;
190 	b->heap = i;
191 
192 	return i;
193 }
194 
195 static int
196 downheap(int i, VtBlock *b)
197 {
198 	VtBlock *bb;
199 	u32int now;
200 	int k;
201 	VtCache *c;
202 	
203 	c = b->c;
204 	now = c->now;
205 	for(; ; i = k){
206 		k = (i << 1) + 1;
207 		if(k >= c->nheap)
208 			break;
209 		if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
210 			k++;
211 		bb = c->heap[k];
212 		if(b->used - now <= bb->used - now)
213 			break;
214 		c->heap[i] = bb;
215 		bb->heap = i;
216 	}
217 	c->heap[i] = b;
218 	b->heap = i;
219 	return i;
220 }
221 
222 /*
223  * Delete a block from the heap.
224  * Called with c->lk held.
225  */
226 static void
227 heapdel(VtBlock *b)
228 {
229 	int i, si;
230 	VtCache *c;
231 
232 	c = b->c;
233 
234 	si = b->heap;
235 	if(si == BadHeap)
236 		return;
237 	b->heap = BadHeap;
238 	c->nheap--;
239 	if(si == c->nheap)
240 		return;
241 	b = c->heap[c->nheap];
242 	i = upheap(si, b);
243 	if(i == si)
244 		downheap(i, b);
245 }
246 
247 /*
248  * Insert a block into the heap.
249  * Called with c->lk held.
250  */
251 static void
252 heapins(VtBlock *b)
253 {
254 	assert(b->heap == BadHeap);
255 	upheap(b->c->nheap++, b);
256 }
257 
258 /*
259  * locate the vtBlock with the oldest second to last use.
260  * remove it from the heap, and fix up the heap.
261  */
262 /* called with c->lk held */
263 static VtBlock*
264 vtcachebumpblock(VtCache *c)
265 {
266 	VtBlock *b;
267 
268 	/*
269 	 * locate the vtBlock with the oldest second to last use.
270 	 * remove it from the heap, and fix up the heap.
271 	 */
272 	if(c->nheap == 0){
273 		vtcachedump(c);
274 		fprint(2, "vtcachebumpblock: no free blocks in vtCache");
275 		abort();
276 	}
277 	b = c->heap[0];
278 	heapdel(b);
279 
280 	assert(b->heap == BadHeap);
281 	assert(b->ref == 0);
282 
283 	/*
284 	 * unchain the vtBlock from hash chain if any
285 	 */
286 	if(b->prev){
287 		*(b->prev) = b->next;
288 		if(b->next)
289 			b->next->prev = b->prev;
290 		b->prev = nil;
291 	}
292 
293  	
294 if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
295 	/* set vtBlock to a reasonable state */
296 	b->ref = 1;
297 	b->iostate = BioEmpty;
298 	return b;
299 }
300 
301 /*
302  * fetch a local block from the memory cache.
303  * if it's not there, load it, bumping some other Block.
304  * if we're out of free blocks, we're screwed.
305  */
306 VtBlock*
307 vtcachelocal(VtCache *c, u32int addr, int type)
308 {
309 	VtBlock *b;
310 
311 	if(addr == 0)
312 		sysfatal("vtcachelocal: asked for nonexistent block 0");
313 	if(addr > c->nblock)
314 		sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",
315 			addr, c->nblock);
316 
317 	b = &c->block[addr-1];
318 	if(b->addr == NilBlock || b->iostate != BioLocal)
319 		sysfatal("vtcachelocal: block is not local");
320 
321 	if(b->type != type)
322 		sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type);
323 
324 	qlock(&c->lk);
325 	b->ref++;
326 	qunlock(&c->lk);
327 
328 	qlock(&b->lk);
329 	b->nlock = 1;
330 	b->pc = getcallerpc(&c);
331 	return b;
332 }
333 
334 VtBlock*
335 vtcacheallocblock(VtCache *c, int type)
336 {
337 	VtBlock *b;
338 
339 	qlock(&c->lk);
340 	b = vtcachebumpblock(c);
341 	b->iostate = BioLocal;
342 	b->type = type;
343 	b->addr = (b - c->block)+1;
344 	vtzeroextend(type, b->data, 0, c->blocksize);
345 	vtlocaltoglobal(b->addr, b->score);
346 	qunlock(&c->lk);
347 
348 	qlock(&b->lk);
349 	b->nlock = 1;
350 	b->pc = getcallerpc(&c);
351 	return b;
352 }
353 
354 /*
355  * fetch a global (Venti) block from the memory cache.
356  * if it's not there, load it, bumping some other block.
357  */
358 VtBlock*
359 vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
360 {
361 	VtBlock *b;
362 	ulong h;
363 	int n;
364 	u32int addr;
365 
366 	if(vttracelevel)
367 		fprint(2, "vtcacheglobal %V %d from %p\n", score, type, getcallerpc(&c));
368 	addr = vtglobaltolocal(score);
369 	if(addr != NilBlock){
370 		if(vttracelevel)
371 			fprint(2, "vtcacheglobal %V %d => local\n", score, type);
372 		b = vtcachelocal(c, addr, type);
373 		if(b)
374 			b->pc = getcallerpc(&c);
375 		return b;
376 	}
377 
378 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
379 
380 	/*
381 	 * look for the block in the cache
382 	 */
383 	qlock(&c->lk);
384 	for(b = c->hash[h]; b != nil; b = b->next){
385 		if(b->addr != NilBlock || memcmp(b->score, score, VtScoreSize) != 0 || b->type != type)
386 			continue;
387 		heapdel(b);
388 		b->ref++;
389 		qunlock(&c->lk);
390 		if(vttracelevel)
391 			fprint(2, "vtcacheglobal %V %d => found in cache %p; locking\n", score, type, b);
392 		qlock(&b->lk);
393 		b->nlock = 1;
394 		if(b->iostate == BioVentiError){
395 			if(chattyventi)
396 				fprint(2, "cached read error for %V\n", score);
397 			if(vttracelevel)
398 				fprint(2, "vtcacheglobal %V %d => cache read error\n", score, type);
399 			vtblockput(b);
400 			werrstr("venti i/o error");
401 			return nil;
402 		}
403 		if(vttracelevel)
404 			fprint(2, "vtcacheglobal %V %d => found in cache; returning\n", score, type);
405 		b->pc = getcallerpc(&c);
406 		return b;
407 	}
408 
409 	/*
410 	 * not found
411 	 */
412 	b = vtcachebumpblock(c);
413 	b->addr = NilBlock;
414 	b->type = type;
415 	memmove(b->score, score, VtScoreSize);
416 	/* chain onto correct hash */
417 	b->next = c->hash[h];
418 	c->hash[h] = b;
419 	if(b->next != nil)
420 		b->next->prev = &b->next;
421 	b->prev = &c->hash[h];
422 
423 	/*
424 	 * Lock b before unlocking c, so that others wait while we read.
425 	 * 
426 	 * You might think there is a race between this qlock(b) before qunlock(c)
427 	 * and the qlock(c) while holding a qlock(b) in vtblockwrite.  However,
428 	 * the block here can never be the block in a vtblockwrite, so we're safe.
429 	 * We're certainly living on the edge.
430 	 */
431 	if(vttracelevel)
432 		fprint(2, "vtcacheglobal %V %d => bumped; locking %p\n", score, type, b);
433 	qlock(&b->lk);
434 	b->nlock = 1;
435 	qunlock(&c->lk);
436 
437 	vtcachenread++;
438 	n = vtread(c->z, score, type, b->data, c->blocksize);
439 	if(n < 0){
440 		if(chattyventi)
441 			fprint(2, "read %V: %r\n", score);
442 		if(vttracelevel)
443 			fprint(2, "vtcacheglobal %V %d => bumped; read error\n", score, type);
444 		b->iostate = BioVentiError;
445 		vtblockput(b);
446 		return nil;
447 	}
448 	vtzeroextend(type, b->data, n, c->blocksize);
449 	b->iostate = BioVenti;
450 	b->nlock = 1;
451 	if(vttracelevel)
452 		fprint(2, "vtcacheglobal %V %d => loaded into cache; returning\n", score, type);
453 	b->pc = getcallerpc(&b);
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 		/* fall through */
514 	case BioVentiError:
515 		heapins(b);
516 		break;
517 	case BioLocal:
518 		break;
519 	}
520 	qunlock(&c->lk);
521 }
522 
523 int
524 vtblockwrite(VtBlock *b)
525 {
526 	uchar score[VtScoreSize];
527 	VtCache *c;
528 	uint h;
529 	int n;
530 
531 	if(b->iostate != BioLocal){
532 		werrstr("vtblockwrite: not a local block");
533 		return -1;
534 	}
535 
536 	c = b->c;
537 	n = vtzerotruncate(b->type, b->data, c->blocksize);
538 	vtcachenwrite++;
539 	if(c->write(c->z, score, b->type, b->data, n) < 0)
540 		return -1;
541 
542 	memmove(b->score, score, VtScoreSize);
543 
544 	qlock(&c->lk);
545 	b->addr = NilBlock;	/* now on venti */
546 	b->iostate = BioVenti;
547 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash;
548 	b->next = c->hash[h];
549 	c->hash[h] = b;
550 	if(b->next != nil)
551 		b->next->prev = &b->next;
552 	b->prev = &c->hash[h];
553 	qunlock(&c->lk);
554 	return 0;
555 }
556 
557 uint
558 vtcacheblocksize(VtCache *c)
559 {
560 	return c->blocksize;
561 }
562 
563 VtBlock*
564 vtblockcopy(VtBlock *b)
565 {
566 	VtBlock *bb;
567 
568 	vtcachencopy++;
569 	bb = vtcacheallocblock(b->c, b->type);
570 	if(bb == nil){
571 		vtblockput(b);
572 		return nil;
573 	}
574 	memmove(bb->data, b->data, b->c->blocksize);
575 	vtblockput(b);
576 	bb->pc = getcallerpc(&b);
577 	return bb;
578 }
579 
580 void
581 vtlocaltoglobal(u32int addr, uchar score[VtScoreSize])
582 {
583 	memset(score, 0, 16);
584 	score[16] = addr>>24;
585 	score[17] = addr>>16;
586 	score[18] = addr>>8;
587 	score[19] = addr;
588 }
589 
590 
591 u32int
592 vtglobaltolocal(uchar score[VtScoreSize])
593 {
594 	static uchar zero[16];
595 	if(memcmp(score, zero, 16) != 0)
596 		return NilBlock;
597 	return (score[16]<<24)|(score[17]<<16)|(score[18]<<8)|score[19];
598 }
599