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