sys/src/libventi/cache.c

   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