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