sys/src/libventi/file.c

   1 /*
   2  * Manage tree of VtFiles stored in the block cache.
   3  *
   4  * The single point of truth for the info about the VtFiles themselves
   5  * is the block data.  Because of this, there is no explicit locking of
   6  * VtFile structures, and indeed there may be more than one VtFile
   7  * structure for a given Venti file.  They synchronize through the
   8  * block cache.
   9  *
  10  * This is a bit simpler than fossil because there are no epochs
  11  * or tags or anything else.  Just mutable local blocks and immutable
  12  * Venti blocks.
  13  */
  14
  15 #include <u.h>
  16 #include <libc.h>
  17 #include <venti.h>
  18
  19 #define MaxBlock (1UL<<31)
  20
  21 static char ENotDir[] = "walk in non-directory";
  22 static char ETooBig[] = "file too big";
  23 /* static char EBadAddr[] = "bad address"; */
  24 static char ELabelMismatch[] = "label mismatch";
  25
  26 static int      sizetodepth(uvlong s, int psize, int dsize);
  27 static VtBlock  *fileload(VtFile *r, VtEntry *e);
  28 static int      shrinkdepth(VtFile*, VtBlock*, VtEntry*, int);
  29 static int      shrinksize(VtFile*, VtEntry*, uvlong);
  30 static int      growdepth(VtFile*, VtBlock*, VtEntry*, int);
  31
  32 #define ISLOCKED(r)     ((r)->b != nil)
  33 #define DEPTH(t)        ((t)&VtTypeDepthMask)
  34
  35 static VtFile *
  36 vtfilealloc(VtCache *c, VtBlock *b, VtFile *p, u32int offset, int mode)
  37 {
  38         int epb;
  39         u32int size;
  40         VtEntry e;
  41         VtFile *r;
  42
  43         assert(p==nil || ISLOCKED(p));
  44
  45         if(p == nil){
  46                 assert(offset == 0);
  47                 epb = 1;
  48         }else
  49                 epb = p->dsize / VtEntrySize;
  50
  51         if(b->type != VtDirType){
  52                 werrstr("bad block type %#uo", b->type);
  53                 return nil;
  54         }
  55
  56         /*
  57          * a non-active entry is the only thing that
  58          * can legitimately happen here. all the others
  59          * get prints.
  60          */
  61         if(vtentryunpack(&e, b->data, offset % epb) < 0){
  62                 fprint(2, "vtentryunpack failed: %r (%.*H)\n", VtEntrySize, b->data+VtEntrySize*(offset%epb));
  63                 return nil;
  64         }
  65         if(!(e.flags & VtEntryActive)){
  66                 werrstr("entry not active");
  67                 return nil;
  68         }
  69
  70         if(DEPTH(e.type) < sizetodepth(e.size, e.psize, e.dsize)){
  71                 fprint(2, "depth %ud size %llud psize %ud dsize %ud\n",
  72                         DEPTH(e.type), e.size, e.psize, e.dsize);
  73                 werrstr("bad depth");
  74                 return nil;
  75         }
  76
  77         size = vtcacheblocksize(c);
  78         if(e.dsize > size || e.psize > size){
  79                 werrstr("block sizes %ud, %ud bigger than cache block size %ud",
  80                         e.psize, e.dsize, size);
  81                 return nil;
  82         }
  83
  84         r = vtmallocz(sizeof(VtFile));
  85         r->c = c;
  86         r->mode = mode;
  87         r->dsize = e.dsize;
  88         r->psize = e.psize;
  89         r->gen = e.gen;
  90         r->dir = (e.type & VtTypeBaseMask) == VtDirType;
  91         r->ref = 1;
  92         r->parent = p;
  93         if(p){
  94                 qlock(&p->lk);
  95                 assert(mode == VtOREAD || p->mode == VtORDWR);
  96                 p->ref++;
  97                 qunlock(&p->lk);
  98         }else{
  99                 assert(b->addr != NilBlock);
 100                 r->local = 1;
 101         }
 102         memmove(r->score, b->score, VtScoreSize);
 103         r->offset = offset;
 104         r->epb = epb;
 105
 106         return r;
 107 }
 108
 109 VtFile *
 110 vtfileroot(VtCache *c, u32int addr, int mode)
 111 {
 112         VtFile *r;
 113         VtBlock *b;
 114
 115         b = vtcachelocal(c, addr, VtDirType);
 116         if(b == nil)
 117                 return nil;
 118         r = vtfilealloc(c, b, nil, 0, mode);
 119         vtblockput(b);
 120         return r;
 121 }
 122
 123 VtFile*
 124 vtfileopenroot(VtCache *c, VtEntry *e)
 125 {
 126         VtBlock *b;
 127         VtFile *f;
 128
 129         b = vtcacheallocblock(c, VtDirType);
 130         if(b == nil)
 131                 return nil;
 132
 133         vtentrypack(e, b->data, 0);
 134         f = vtfilealloc(c, b, nil, 0, VtORDWR);
 135         vtblockput(b);
 136         return f;
 137 }
 138
 139 VtFile *
 140 vtfilecreateroot(VtCache *c, int psize, int dsize, int type)
 141 {
 142         VtEntry e;
 143
 144         memset(&e, 0, sizeof e);
 145         e.flags = VtEntryActive;
 146         e.psize = psize;
 147         e.dsize = dsize;
 148         e.type = type;
 149         memmove(e.score, vtzeroscore, VtScoreSize);
 150
 151         return vtfileopenroot(c, &e);
 152 }
 153
 154 VtFile *
 155 vtfileopen(VtFile *r, u32int offset, int mode)
 156 {
 157         ulong bn;
 158         VtBlock *b;
 159
 160         assert(ISLOCKED(r));
 161         if(!r->dir){
 162                 werrstr(ENotDir);
 163                 return nil;
 164         }
 165
 166         bn = offset/(r->dsize/VtEntrySize);
 167
 168         b = vtfileblock(r, bn, mode);
 169         if(b == nil)
 170                 return nil;
 171         r = vtfilealloc(r->c, b, r, offset, mode);
 172         vtblockput(b);
 173         return r;
 174 }
 175
 176 VtFile*
 177 vtfilecreate(VtFile *r, int psize, int dsize, int type)
 178 {
 179         return _vtfilecreate(r, -1, psize, dsize, type);
 180 }
 181
 182 VtFile*
 183 _vtfilecreate(VtFile *r, int o, int psize, int dsize, int type)
 184 {
 185         int i;
 186         VtBlock *b;
 187         u32int bn, size;
 188         VtEntry e;
 189         int epb;
 190         VtFile *rr;
 191         u32int offset;
 192
 193         assert(ISLOCKED(r));
 194         assert(psize <= VtMaxLumpSize);
 195         assert(dsize <= VtMaxLumpSize);
 196         assert(type == VtDirType || type == VtDataType);
 197
 198         if(!r->dir){
 199                 werrstr(ENotDir);
 200                 return nil;
 201         }
 202
 203         epb = r->dsize/VtEntrySize;
 204
 205         size = vtfilegetdirsize(r);
 206         /*
 207          * look at a random block to see if we can find an empty entry
 208          */
 209         if(o == -1){
 210                 offset = lnrand(size+1);
 211                 offset -= offset % epb;
 212         }else
 213                 offset = o;
 214
 215         /* try the given block and then try the last block */
 216         for(;;){
 217                 bn = offset/epb;
 218                 b = vtfileblock(r, bn, VtORDWR);
 219                 if(b == nil)
 220                         return nil;
 221                 for(i=offset%r->epb; i<epb; i++){
 222                         if(vtentryunpack(&e, b->data, i) < 0)
 223                                 continue;
 224                         if((e.flags&VtEntryActive) == 0 && e.gen != ~0)
 225                                 goto Found;
 226                 }
 227                 vtblockput(b);
 228                 if(offset == size){
 229                         fprint(2, "vtfilecreate: cannot happen\n");
 230                         werrstr("vtfilecreate: cannot happen");
 231                         return nil;
 232                 }
 233                 offset = size;
 234         }
 235
 236 Found:
 237         /* found an entry - gen already set */
 238         e.psize = psize;
 239         e.dsize = dsize;
 240         e.flags = VtEntryActive;
 241         e.type = type;
 242         e.size = 0;
 243         memmove(e.score, vtzeroscore, VtScoreSize);
 244         vtentrypack(&e, b->data, i);
 245
 246         offset = bn*epb + i;
 247         if(offset+1 > size){
 248                 if(vtfilesetdirsize(r, offset+1) < 0){
 249                         vtblockput(b);
 250                         return nil;
 251                 }
 252         }
 253
 254         rr = vtfilealloc(r->c, b, r, offset, VtORDWR);
 255         vtblockput(b);
 256         return rr;
 257 }
 258
 259 static int
 260 vtfilekill(VtFile *r, int doremove)
 261 {
 262         VtEntry e;
 263         VtBlock *b;
 264
 265         assert(ISLOCKED(r));
 266         b = fileload(r, &e);
 267         if(b == nil)
 268                 return -1;
 269
 270         if(doremove==0 && e.size == 0){
 271                 /* already truncated */
 272                 vtblockput(b);
 273                 return 0;
 274         }
 275
 276         if(doremove){
 277                 if(e.gen != ~0)
 278                         e.gen++;
 279                 e.dsize = 0;
 280                 e.psize = 0;
 281                 e.flags = 0;
 282         }else
 283                 e.flags &= ~VtEntryLocal;
 284         e.type = 0;
 285         e.size = 0;
 286         memmove(e.score, vtzeroscore, VtScoreSize);
 287         vtentrypack(&e, b->data, r->offset % r->epb);
 288         vtblockput(b);
 289
 290         if(doremove){
 291                 vtfileunlock(r);
 292                 vtfileclose(r);
 293         }
 294
 295         return 0;
 296 }
 297
 298 int
 299 vtfileremove(VtFile *r)
 300 {
 301         return vtfilekill(r, 1);
 302 }
 303
 304 int
 305 vtfiletruncate(VtFile *r)
 306 {
 307         return vtfilekill(r, 0);
 308 }
 309
 310 uvlong
 311 vtfilegetsize(VtFile *r)
 312 {
 313         VtEntry e;
 314         VtBlock *b;
 315
 316         assert(ISLOCKED(r));
 317         b = fileload(r, &e);
 318         if(b == nil)
 319                 return ~(uvlong)0;
 320         vtblockput(b);
 321
 322         return e.size;
 323 }
 324
 325 static int
 326 shrinksize(VtFile *r, VtEntry *e, uvlong size)
 327 {
 328         int i, depth, type, isdir, ppb;
 329         uvlong ptrsz;
 330         uchar score[VtScoreSize];
 331         VtBlock *b;
 332
 333         b = vtcacheglobal(r->c, e->score, e->type);
 334         if(b == nil)
 335                 return -1;
 336
 337         ptrsz = e->dsize;
 338         ppb = e->psize/VtScoreSize;
 339         type = e->type;
 340         depth = DEPTH(type);
 341         for(i=0; i+1<depth; i++)
 342                 ptrsz *= ppb;
 343
 344         isdir = r->dir;
 345         while(depth > 0){
 346                 if(b->addr == NilBlock){
 347                         /* not worth copying the block just so we can zero some of it */
 348                         vtblockput(b);
 349                         return -1;
 350                 }
 351
 352                 /*
 353                  * invariant: each pointer in the tree rooted at b accounts for ptrsz bytes
 354                  */
 355
 356                 /* zero the pointers to unnecessary blocks */
 357                 i = (size+ptrsz-1)/ptrsz;
 358                 for(; i<ppb; i++)
 359                         memmove(b->data+i*VtScoreSize, vtzeroscore, VtScoreSize);
 360
 361                 /* recurse (go around again) on the partially necessary block */
 362                 i = size/ptrsz;
 363                 size = size%ptrsz;
 364                 if(size == 0){
 365                         vtblockput(b);
 366                         return 0;
 367                 }
 368                 ptrsz /= ppb;
 369                 type--;
 370                 memmove(score, b->data+i*VtScoreSize, VtScoreSize);
 371                 vtblockput(b);
 372                 b = vtcacheglobal(r->c, score, type);
 373                 if(b == nil)
 374                         return -1;
 375         }
 376
 377         if(b->addr == NilBlock){
 378                 vtblockput(b);
 379                 return -1;
 380         }
 381
 382         /*
 383          * No one ever truncates BtDir blocks.
 384          */
 385         if(depth==0 && !isdir && e->dsize > size)
 386                 memset(b->data+size, 0, e->dsize-size);
 387         vtblockput(b);
 388         return 0;
 389 }
 390
 391 int
 392 vtfilesetsize(VtFile *r, u64int size)
 393 {
 394         int depth, edepth;
 395         VtEntry e;
 396         VtBlock *b;
 397
 398         assert(ISLOCKED(r));
 399         if(size == 0)
 400                 return vtfiletruncate(r);
 401
 402         if(size > VtMaxFileSize || size > ((uvlong)MaxBlock)*r->dsize){
 403                 werrstr(ETooBig);
 404                 return -1;
 405         }
 406
 407         b = fileload(r, &e);
 408         if(b == nil)
 409                 return -1;
 410
 411         /* quick out */
 412         if(e.size == size){
 413                 vtblockput(b);
 414                 return 0;
 415         }
 416
 417         depth = sizetodepth(size, e.psize, e.dsize);
 418         edepth = DEPTH(e.type);
 419         if(depth < edepth){
 420                 if(shrinkdepth(r, b, &e, depth) < 0){
 421                         vtblockput(b);
 422                         return -1;
 423                 }
 424         }else if(depth > edepth){
 425                 if(growdepth(r, b, &e, depth) < 0){
 426                         vtblockput(b);
 427                         return -1;
 428                 }
 429         }
 430
 431         if(size < e.size)
 432                 shrinksize(r, &e, size);
 433
 434         e.size = size;
 435         vtentrypack(&e, b->data, r->offset % r->epb);
 436         vtblockput(b);
 437
 438         return 0;
 439 }
 440
 441 int
 442 vtfilesetdirsize(VtFile *r, u32int ds)
 443 {
 444         uvlong size;
 445         int epb;
 446
 447         assert(ISLOCKED(r));
 448         epb = r->dsize/VtEntrySize;
 449
 450         size = (uvlong)r->dsize*(ds/epb);
 451         size += VtEntrySize*(ds%epb);
 452         return vtfilesetsize(r, size);
 453 }
 454
 455 u32int
 456 vtfilegetdirsize(VtFile *r)
 457 {
 458         ulong ds;
 459         uvlong size;
 460         int epb;
 461
 462         assert(ISLOCKED(r));
 463         epb = r->dsize/VtEntrySize;
 464
 465         size = vtfilegetsize(r);
 466         ds = epb*(size/r->dsize);
 467         ds += (size%r->dsize)/VtEntrySize;
 468         return ds;
 469 }
 470
 471 int
 472 vtfilegetentry(VtFile *r, VtEntry *e)
 473 {
 474         VtBlock *b;
 475
 476         assert(ISLOCKED(r));
 477         b = fileload(r, e);
 478         if(b == nil)
 479                 return -1;
 480         vtblockput(b);
 481
 482         return 0;
 483 }
 484
 485 int
 486 vtfilesetentry(VtFile *r, VtEntry *e)
 487 {
 488         VtBlock *b;
 489         VtEntry ee;
 490
 491         assert(ISLOCKED(r));
 492         b = fileload(r, &ee);
 493         if(b == nil)
 494                 return -1;
 495         vtentrypack(e, b->data, r->offset % r->epb);
 496         vtblockput(b);
 497         return 0;
 498 }
 499
 500 static VtBlock *
 501 blockwalk(VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
 502 {
 503         VtBlock *b;
 504         int type;
 505         uchar *score;
 506
 507         switch(p->type){
 508         case VtDataType:
 509                 assert(0);
 510         case VtDirType:
 511                 type = e->type;
 512                 score = e->score;
 513                 break;
 514         default:
 515                 type = p->type - 1;
 516                 score = p->data+index*VtScoreSize;
 517                 break;
 518         }
 519 /*print("walk from %V/%d ty %d to %V ty %d\n", p->score, index, p->type, score, type); */
 520
 521         if(mode == VtOWRITE && vtglobaltolocal(score) == NilBlock){
 522                 b = vtcacheallocblock(c, type);
 523                 if(b)
 524                         goto HaveCopy;
 525         }else
 526                 b = vtcacheglobal(c, score, type);
 527
 528         if(b == nil || mode == VtOREAD)
 529                 return b;
 530
 531         if(vtglobaltolocal(b->score) != NilBlock)
 532                 return b;
 533
 534         /*
 535          * Copy on write.
 536          */
 537         e->flags |= VtEntryLocal;
 538
 539         b = vtblockcopy(b/*, e->tag, fs->ehi, fs->elo*/);
 540         if(b == nil)
 541                 return nil;
 542
 543 HaveCopy:
 544         if(p->type == VtDirType){
 545                 memmove(e->score, b->score, VtScoreSize);
 546                 vtentrypack(e, p->data, index);
 547         }else{
 548                 memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
 549         }
 550         return b;
 551 }
 552
 553 /*
 554  * Change the depth of the VtFile r.
 555  * The entry e for r is contained in block p.
 556  */
 557 static int
 558 growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 559 {
 560         VtBlock *b, *bb;
 561         VtEntry oe;
 562
 563         assert(ISLOCKED(r));
 564         assert(depth <= VtPointerDepth);
 565
 566         b = vtcacheglobal(r->c, e->score, e->type);
 567         if(b == nil)
 568                 return -1;
 569
 570         oe = *e;
 571
 572         /*
 573          * Keep adding layers until we get to the right depth
 574          * or an error occurs.
 575          */
 576         while(DEPTH(e->type) < depth){
 577                 bb = vtcacheallocblock(r->c, e->type+1);
 578                 if(bb == nil)
 579                         break;
 580                 memmove(bb->data, b->score, VtScoreSize);
 581                 memmove(e->score, bb->score, VtScoreSize);
 582                 e->type++;
 583                 e->flags |= VtEntryLocal;
 584                 vtblockput(b);
 585                 b = bb;
 586         }
 587
 588         vtentrypack(e, p->data, r->offset % r->epb);
 589         vtblockput(b);
 590
 591         if(DEPTH(e->type) == depth)
 592                 return 0;
 593         return -1;
 594 }
 595
 596 static int
 597 shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 598 {
 599         VtBlock *b, *nb, *ob, *rb;
 600
 601         assert(ISLOCKED(r));
 602         assert(depth <= VtPointerDepth);
 603
 604         rb = vtcacheglobal(r->c, e->score, e->type);
 605         if(rb == nil)
 606                 return -1;
 607
 608         ob = nil;
 609         b = rb;
 610         for(; DEPTH(e->type) > depth; e->type--){
 611                 nb = vtcacheglobal(r->c, b->data, e->type-1);
 612                 if(nb == nil)
 613                         break;
 614                 if(ob!=nil && ob!=rb)
 615                         vtblockput(ob);
 616                 ob = b;
 617                 b = nb;
 618         }
 619
 620         if(b == rb){
 621                 vtblockput(rb);
 622                 return 0;
 623         }
 624
 625         /*
 626          * Right now, e points at the root block rb, b is the new root block,
 627          * and ob points at b.  To update:
 628          *
 629          *      (i) change e to point at b
 630          *      (ii) zero the pointer ob -> b
 631          *      (iii) free the root block
 632          *
 633          * p (the block containing e) must be written before
 634          * anything else.
 635          */
 636
 637         /* (i) */
 638         memmove(e->score, b->score, VtScoreSize);
 639         vtentrypack(e, p->data, r->offset % r->epb);
 640
 641         /* (ii) */
 642         memmove(ob->data, vtzeroscore, VtScoreSize);
 643
 644         /* (iii) */
 645         vtblockput(rb);
 646         if(ob!=nil && ob!=rb)
 647                 vtblockput(ob);
 648         vtblockput(b);
 649
 650         if(DEPTH(e->type) == depth)
 651                 return 0;
 652         return -1;
 653 }
 654
 655 static int
 656 mkindices(VtEntry *e, u32int bn, int *index)
 657 {
 658         int i, np;
 659
 660         memset(index, 0, (VtPointerDepth+1)*sizeof(int));
 661
 662         np = e->psize/VtScoreSize;
 663         for(i=0; bn > 0; i++){
 664                 if(i >= VtPointerDepth){
 665                         werrstr("bad address 0x%lux", (ulong)bn);
 666                         return -1;
 667                 }
 668                 index[i] = bn % np;
 669                 bn /= np;
 670         }
 671         return i;
 672 }
 673
 674 VtBlock *
 675 vtfileblock(VtFile *r, u32int bn, int mode)
 676 {
 677         VtBlock *b, *bb;
 678         int index[VtPointerDepth+1];
 679         VtEntry e;
 680         int i;
 681         int m;
 682
 683         assert(ISLOCKED(r));
 684         assert(bn != NilBlock);
 685
 686         b = fileload(r, &e);
 687         if(b == nil)
 688                 return nil;
 689
 690         i = mkindices(&e, bn, index);
 691         if(i < 0)
 692                 goto Err;
 693         if(i > DEPTH(e.type)){
 694                 if(mode == VtOREAD){
 695                         werrstr("bad address 0x%lux", (ulong)bn);
 696                         goto Err;
 697                 }
 698                 index[i] = 0;
 699                 if(growdepth(r, b, &e, i) < 0)
 700                         goto Err;
 701         }
 702
 703 assert(b->type == VtDirType);
 704
 705         index[DEPTH(e.type)] = r->offset % r->epb;
 706
 707         /* mode for intermediate block */
 708         m = mode;
 709         if(m == VtOWRITE)
 710                 m = VtORDWR;
 711
 712         for(i=DEPTH(e.type); i>=0; i--){
 713                 bb = blockwalk(b, index[i], r->c, i==0 ? mode : m, &e);
 714                 if(bb == nil)
 715                         goto Err;
 716                 vtblockput(b);
 717                 b = bb;
 718         }
 719         b->pc = getcallerpc(&r);
 720         return b;
 721 Err:
 722         vtblockput(b);
 723         return nil;
 724 }
 725
 726 int
 727 vtfileblockscore(VtFile *r, u32int bn, uchar score[VtScoreSize])
 728 {
 729         VtBlock *b, *bb;
 730         int index[VtPointerDepth+1];
 731         VtEntry e;
 732         int i;
 733
 734         assert(ISLOCKED(r));
 735         assert(bn != NilBlock);
 736
 737         b = fileload(r, &e);
 738         if(b == nil)
 739                 return -1;
 740
 741         if(DEPTH(e.type) == 0){
 742                 memmove(score, e.score, VtScoreSize);
 743                 vtblockput(b);
 744                 return 0;
 745         }
 746
 747         i = mkindices(&e, bn, index);
 748         if(i < 0){
 749                 vtblockput(b);
 750                 return -1;
 751         }
 752         if(i > DEPTH(e.type)){
 753                 memmove(score, vtzeroscore, VtScoreSize);
 754                 vtblockput(b);
 755                 return 0;
 756         }
 757
 758         index[DEPTH(e.type)] = r->offset % r->epb;
 759
 760         for(i=DEPTH(e.type); i>=1; i--){
 761                 bb = blockwalk(b, index[i], r->c, VtOREAD, &e);
 762                 if(bb == nil)
 763                         goto Err;
 764                 vtblockput(b);
 765                 b = bb;
 766                 if(memcmp(b->score, vtzeroscore, VtScoreSize) == 0)
 767                         break;
 768         }
 769
 770         memmove(score, b->data+index[0]*VtScoreSize, VtScoreSize);
 771         vtblockput(b);
 772         return 0;
 773
 774 Err:
 775         vtblockput(b);
 776         return -1;
 777 }
 778
 779 void
 780 vtfileincref(VtFile *r)
 781 {
 782         qlock(&r->lk);
 783         r->ref++;
 784         qunlock(&r->lk);
 785 }
 786
 787 void
 788 vtfileclose(VtFile *r)
 789 {
 790         if(r == nil)
 791                 return;
 792         qlock(&r->lk);
 793         r->ref--;
 794         if(r->ref){
 795                 qunlock(&r->lk);
 796                 return;
 797         }
 798         assert(r->ref == 0);
 799         qunlock(&r->lk);
 800         if(r->parent)
 801                 vtfileclose(r->parent);
 802         memset(r, ~0, sizeof(*r));
 803         vtfree(r);
 804 }
 805
 806 /*
 807  * Retrieve the block containing the entry for r.
 808  * If a snapshot has happened, we might need
 809  * to get a new copy of the block.  We avoid this
 810  * in the common case by caching the score for
 811  * the block and the last epoch in which it was valid.
 812  *
 813  * We use r->mode to tell the difference between active
 814  * file system VtFiles (VtORDWR) and VtFiles for the
 815  * snapshot file system (VtOREAD).
 816  */
 817 static VtBlock*
 818 fileloadblock(VtFile *r, int mode)
 819 {
 820         char e[ERRMAX];
 821         u32int addr;
 822         VtBlock *b;
 823
 824         switch(r->mode){
 825         default:
 826                 assert(0);
 827         case VtORDWR:
 828                 assert(r->mode == VtORDWR);
 829                 if(r->local == 1){
 830                         b = vtcacheglobal(r->c, r->score, VtDirType);
 831                         if(b == nil)
 832                                 return nil;
 833                         b->pc = getcallerpc(&r);
 834                         return b;
 835                 }
 836                 assert(r->parent != nil);
 837                 if(vtfilelock(r->parent, VtORDWR) < 0)
 838                         return nil;
 839                 b = vtfileblock(r->parent, r->offset/r->epb, VtORDWR);
 840                 vtfileunlock(r->parent);
 841                 if(b == nil)
 842                         return nil;
 843                 memmove(r->score, b->score, VtScoreSize);
 844                 r->local = 1;
 845                 return b;
 846
 847         case VtOREAD:
 848                 if(mode == VtORDWR){
 849                         werrstr("read/write lock of read-only file");
 850                         return nil;
 851                 }
 852                 addr = vtglobaltolocal(r->score);
 853                 if(addr == NilBlock)
 854                         return vtcacheglobal(r->c, r->score, VtDirType);
 855
 856                 b = vtcachelocal(r->c, addr, VtDirType);
 857                 if(b)
 858                         return b;
 859
 860                 /*
 861                  * If it failed because the epochs don't match, the block has been
 862                  * archived and reclaimed.  Rewalk from the parent and get the
 863                  * new pointer.  This can't happen in the VtORDWR case
 864                  * above because blocks in the current epoch don't get
 865                  * reclaimed.  The fact that we're VtOREAD means we're
 866                  * a snapshot.  (Or else the file system is read-only, but then
 867                  * the archiver isn't going around deleting blocks.)
 868                  */
 869                 rerrstr(e, sizeof e);
 870                 if(strcmp(e, ELabelMismatch) == 0){
 871                         if(vtfilelock(r->parent, VtOREAD) < 0)
 872                                 return nil;
 873                         b = vtfileblock(r->parent, r->offset/r->epb, VtOREAD);
 874                         vtfileunlock(r->parent);
 875                         if(b){
 876                                 fprint(2, "vtfilealloc: lost %V found %V\n",
 877                                         r->score, b->score);
 878                                 memmove(r->score, b->score, VtScoreSize);
 879                                 return b;
 880                         }
 881                 }
 882                 return nil;
 883         }
 884 }
 885
 886 int
 887 vtfilelock(VtFile *r, int mode)
 888 {
 889         VtBlock *b;
 890
 891         if(mode == -1)
 892                 mode = r->mode;
 893
 894         b = fileloadblock(r, mode);
 895         if(b == nil)
 896                 return -1;
 897         /*
 898          * The fact that we are holding b serves as the
 899          * lock entitling us to write to r->b.
 900          */
 901         assert(r->b == nil);
 902         r->b = b;
 903         b->pc = getcallerpc(&r);
 904         return 0;
 905 }
 906
 907 /*
 908  * Lock two (usually sibling) VtFiles.  This needs special care
 909  * because the Entries for both vtFiles might be in the same block.
 910  * We also try to lock blocks in left-to-right order within the tree.
 911  */
 912 int
 913 vtfilelock2(VtFile *r, VtFile *rr, int mode)
 914 {
 915         VtBlock *b, *bb;
 916
 917         if(rr == nil)
 918                 return vtfilelock(r, mode);
 919
 920         if(mode == -1)
 921                 mode = r->mode;
 922
 923         if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
 924                 b = fileloadblock(r, mode);
 925                 if(b == nil)
 926                         return -1;
 927                 vtblockduplock(b);
 928                 bb = b;
 929         }else if(r->parent==rr->parent || r->offset > rr->offset){
 930                 bb = fileloadblock(rr, mode);
 931                 b = fileloadblock(r, mode);
 932         }else{
 933                 b = fileloadblock(r, mode);
 934                 bb = fileloadblock(rr, mode);
 935         }
 936         if(b == nil || bb == nil){
 937                 if(b)
 938                         vtblockput(b);
 939                 if(bb)
 940                         vtblockput(bb);
 941                 return -1;
 942         }
 943
 944         /*
 945          * The fact that we are holding b and bb serves
 946          * as the lock entitling us to write to r->b and rr->b.
 947          */
 948         r->b = b;
 949         rr->b = bb;
 950         b->pc = getcallerpc(&r);
 951         bb->pc = getcallerpc(&r);
 952         return 0;
 953 }
 954
 955 void
 956 vtfileunlock(VtFile *r)
 957 {
 958         VtBlock *b;
 959
 960         if(r->b == nil){
 961                 fprint(2, "vtfileunlock: already unlocked\n");
 962                 abort();
 963         }
 964         b = r->b;
 965         r->b = nil;
 966         vtblockput(b);
 967 }
 968
 969 static VtBlock*
 970 fileload(VtFile *r, VtEntry *e)
 971 {
 972         VtBlock *b;
 973
 974         assert(ISLOCKED(r));
 975         b = r->b;
 976         if(vtentryunpack(e, b->data, r->offset % r->epb) < 0)
 977                 return nil;
 978         vtblockduplock(b);
 979         return b;
 980 }
 981
 982 static int
 983 sizetodepth(uvlong s, int psize, int dsize)
 984 {
 985         int np;
 986         int d;
 987
 988         /* determine pointer depth */
 989         np = psize/VtScoreSize;
 990         s = (s + dsize - 1)/dsize;
 991         for(d = 0; s > 1; d++)
 992                 s = (s + np - 1)/np;
 993         return d;
 994 }
 995
 996 long
 997 vtfileread(VtFile *f, void *data, long count, vlong offset)
 998 {
 999         int frag;
1000         VtBlock *b;
1001         VtEntry e;
1002
1003         assert(ISLOCKED(f));
1004
1005         vtfilegetentry(f, &e);
1006         if(count == 0)
1007                 return 0;
1008         if(count < 0 || offset < 0){
1009                 werrstr("vtfileread: bad offset or count");
1010                 return -1;
1011         }
1012         if(offset >= e.size)
1013                 return 0;
1014
1015         if(offset+count > e.size)
1016                 count = e.size - offset;
1017
1018         frag = offset % e.dsize;
1019         if(frag+count > e.dsize)
1020                 count = e.dsize - frag;
1021
1022         b = vtfileblock(f, offset/e.dsize, VtOREAD);
1023         if(b == nil)
1024                 return -1;
1025
1026         memmove(data, b->data+frag, count);
1027         vtblockput(b);
1028         return count;
1029 }
1030
1031 static long
1032 filewrite1(VtFile *f, void *data, long count, vlong offset)
1033 {
1034         int frag, m;
1035         VtBlock *b;
1036         VtEntry e;
1037
1038         vtfilegetentry(f, &e);
1039         if(count < 0 || offset < 0){
1040                 werrstr("vtfilewrite: bad offset or count");
1041                 return -1;
1042         }
1043
1044         frag = offset % e.dsize;
1045         if(frag+count > e.dsize)
1046                 count = e.dsize - frag;
1047
1048         m = VtORDWR;
1049         if(frag == 0 && count == e.dsize)
1050                 m = VtOWRITE;
1051
1052         b = vtfileblock(f, offset/e.dsize, m);
1053         if(b == nil)
1054                 return -1;
1055
1056         memmove(b->data+frag, data, count);
1057         if(m == VtOWRITE && frag+count < e.dsize)
1058                 memset(b->data+frag+count, 0, e.dsize-frag-count);
1059
1060         if(offset+count > e.size){
1061                 vtfilegetentry(f, &e);
1062                 e.size = offset+count;
1063                 vtfilesetentry(f, &e);
1064         }
1065
1066         vtblockput(b);
1067         return count;
1068 }
1069
1070 long
1071 vtfilewrite(VtFile *f, void *data, long count, vlong offset)
1072 {
1073         long tot, m;
1074
1075         assert(ISLOCKED(f));
1076
1077         tot = 0;
1078         m = 0;
1079         while(tot < count){
1080                 m = filewrite1(f, (char*)data+tot, count-tot, offset+tot);
1081                 if(m <= 0)
1082                         break;
1083                 tot += m;
1084         }
1085         if(tot==0)
1086                 return m;
1087         return tot;
1088 }
1089
1090 static int
1091 flushblock(VtCache *c, VtBlock *bb, uchar score[VtScoreSize], int ppb, int epb,
1092         int type)
1093 {
1094         u32int addr;
1095         VtBlock *b;
1096         VtEntry e;
1097         int i;
1098
1099         addr = vtglobaltolocal(score);
1100         if(addr == NilBlock)
1101                 return 0;
1102
1103         if(bb){
1104                 b = bb;
1105                 if(memcmp(b->score, score, VtScoreSize) != 0)
1106                         abort();
1107         }else
1108                 if((b = vtcachelocal(c, addr, type)) == nil)
1109                         return -1;
1110
1111         switch(type){
1112         case VtDataType:
1113                 break;
1114
1115         case VtDirType:
1116                 for(i=0; i<epb; i++){
1117                         if(vtentryunpack(&e, b->data, i) < 0)
1118                                 goto Err;
1119                         if(!(e.flags&VtEntryActive))
1120                                 continue;
1121                         if(flushblock(c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1122                                 e.type) < 0)
1123                                 goto Err;
1124                         vtentrypack(&e, b->data, i);
1125                 }
1126                 break;
1127
1128         default:        /* VtPointerTypeX */
1129                 for(i=0; i<ppb; i++){
1130                         if(flushblock(c, nil, b->data+VtScoreSize*i, ppb, epb, type-1) < 0)
1131                                 goto Err;
1132                 }
1133                 break;
1134         }
1135
1136         if(vtblockwrite(b) < 0)
1137                 goto Err;
1138         memmove(score, b->score, VtScoreSize);
1139         if(b != bb)
1140                 vtblockput(b);
1141         return 0;
1142
1143 Err:
1144         if(b != bb)
1145                 vtblockput(b);
1146         return -1;
1147 }
1148
1149 int
1150 vtfileflush(VtFile *f)
1151 {
1152         int ret;
1153         VtBlock *b;
1154         VtEntry e;
1155
1156         assert(ISLOCKED(f));
1157         b = fileload(f, &e);
1158         if(!(e.flags&VtEntryLocal)){
1159                 vtblockput(b);
1160                 return 0;
1161         }
1162
1163         ret = flushblock(f->c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1164                 e.type);
1165         if(ret < 0){
1166                 vtblockput(b);
1167                 return -1;
1168         }
1169
1170         vtentrypack(&e, b->data, f->offset % f->epb);
1171         vtblockput(b);
1172         return 0;
1173 }
1174
1175 int
1176 vtfileflushbefore(VtFile *r, u64int offset)
1177 {
1178         VtBlock *b, *bb;
1179         VtEntry e;
1180         int i, base, depth, ppb, epb, doflush;
1181         int index[VtPointerDepth+1], j, ret;
1182         VtBlock *bi[VtPointerDepth+2];
1183         uchar *score;
1184
1185         assert(ISLOCKED(r));
1186         if(offset == 0)
1187                 return 0;
1188
1189         b = fileload(r, &e);
1190         if(b == nil)
1191                 return -1;
1192
1193         /*
1194          * compute path through tree for the last written byte and the next one.
1195          */
1196         ret = -1;
1197         memset(bi, 0, sizeof bi);
1198         depth = DEPTH(e.type);
1199         bi[depth+1] = b;
1200         i = mkindices(&e, (offset-1)/e.dsize, index);
1201         if(i < 0)
1202                 goto Err;
1203         if(i > depth)
1204                 goto Err;
1205         ppb = e.psize / VtScoreSize;
1206         epb = e.dsize / VtEntrySize;
1207
1208         /*
1209          * load the blocks along the last written byte
1210          */
1211         index[depth] = r->offset % r->epb;
1212         for(i=depth; i>=0; i--){
1213                 bb = blockwalk(b, index[i], r->c, VtORDWR, &e);
1214                 if(bb == nil)
1215                         goto Err;
1216                 bi[i] = bb;
1217                 b = bb;
1218         }
1219         ret = 0;
1220
1221         /*
1222          * walk up the path from leaf to root, flushing anything that
1223          * has been finished.
1224          */
1225         base = e.type&~VtTypeDepthMask;
1226         for(i=0; i<=depth; i++){
1227                 doflush = 0;
1228                 if(i == 0){
1229                         /* leaf: data or dir block */
1230                         if(offset%e.dsize == 0)
1231                                 doflush = 1;
1232                 }else{
1233                         /*
1234                          * interior node: pointer blocks.
1235                          * specifically, b = bi[i] is a block whose index[i-1]'th entry
1236                          * points at bi[i-1].
1237                          */
1238                         b = bi[i];
1239
1240                         /*
1241                          * the index entries up to but not including index[i-1] point at
1242                          * finished blocks, so flush them for sure.
1243                          */
1244                         for(j=0; j<index[i-1]; j++)
1245                                 if(flushblock(r->c, nil, b->data+j*VtScoreSize, ppb, epb, base+i-1) < 0)
1246                                         goto Err;
1247
1248                         /*
1249                          * if index[i-1] is the last entry in the block and is global
1250                          * (i.e. the kid is flushed), then we can flush this block.
1251                          */
1252                         if(j==ppb-1 && vtglobaltolocal(b->data+j*VtScoreSize)==NilBlock)
1253                                 doflush = 1;
1254                 }
1255                 if(doflush){
1256                         if(i == depth)
1257                                 score = e.score;
1258                         else
1259                                 score = bi[i+1]->data+index[i]*VtScoreSize;
1260                         if(flushblock(r->c, bi[i], score, ppb, epb, base+i) < 0)
1261                                 goto Err;
1262                 }
1263         }
1264
1265 Err:
1266         /* top: entry.  do this always so that the score is up-to-date */
1267         vtentrypack(&e, bi[depth+1]->data, index[depth]);
1268         for(i=0; i<nelem(bi); i++)
1269                 if(bi[i])
1270                         vtblockput(bi[i]);
1271         return ret;
1272 }