tcache.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tcache.c (12782B)
---
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 }