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         VtEntry oe;
 507
 508         switch(p->type){
 509         case VtDataType:
 510                 assert(0);
 511         case VtDirType:
 512                 type = e->type;
 513                 score = e->score;
 514                 break;
 515         default:
 516                 type = p->type - 1;
 517                 score = p->data+index*VtScoreSize;
 518                 break;
 519         }
 520 /*print("walk from %V/%d ty %d to %V ty %d\n", p->score, index, p->type, score, type); */
 521
 522         if(mode == VtOWRITE && vtglobaltolocal(score) == NilBlock){
 523                 b = vtcacheallocblock(c, type);
 524                 if(b)
 525                         goto HaveCopy;
 526         }else
 527                 b = vtcacheglobal(c, score, type);
 528
 529         if(b == nil || mode == VtOREAD)
 530                 return b;
 531
 532         if(vtglobaltolocal(b->score) != NilBlock)
 533                 return b;
 534
 535         oe = *e;
 536
 537         /*
 538          * Copy on write.
 539          */
 540         e->flags |= VtEntryLocal;
 541
 542         b = vtblockcopy(b/*, e->tag, fs->ehi, fs->elo*/);
 543         if(b == nil)
 544                 return nil;
 545
 546 HaveCopy:
 547         if(p->type == VtDirType){
 548                 memmove(e->score, b->score, VtScoreSize);
 549                 vtentrypack(e, p->data, index);
 550         }else{
 551                 memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
 552         }
 553         return b;
 554 }
 555
 556 /*
 557  * Change the depth of the VtFile r.
 558  * The entry e for r is contained in block p.
 559  */
 560 static int
 561 growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 562 {
 563         VtBlock *b, *bb;
 564         VtEntry oe;
 565
 566         assert(ISLOCKED(r));
 567         assert(depth <= VtPointerDepth);
 568
 569         b = vtcacheglobal(r->c, e->score, e->type);
 570         if(b == nil)
 571                 return -1;
 572
 573         oe = *e;
 574
 575         /*
 576          * Keep adding layers until we get to the right depth
 577          * or an error occurs.
 578          */
 579         while(DEPTH(e->type) < depth){
 580                 bb = vtcacheallocblock(r->c, e->type+1);
 581                 if(bb == nil)
 582                         break;
 583                 memmove(bb->data, b->score, VtScoreSize);
 584                 memmove(e->score, bb->score, VtScoreSize);
 585                 e->type++;
 586                 e->flags |= VtEntryLocal;
 587                 vtblockput(b);
 588                 b = bb;
 589         }
 590
 591         vtentrypack(e, p->data, r->offset % r->epb);
 592         vtblockput(b);
 593
 594         if(DEPTH(e->type) == depth)
 595                 return 0;
 596         return -1;
 597 }
 598
 599 static int
 600 shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 601 {
 602         VtBlock *b, *nb, *ob, *rb;
 603         VtEntry oe;
 604
 605         assert(ISLOCKED(r));
 606         assert(depth <= VtPointerDepth);
 607
 608         rb = vtcacheglobal(r->c, e->score, e->type);
 609         if(rb == nil)
 610                 return -1;
 611
 612         /*
 613          * Walk down to the new root block.
 614          * We may stop early, but something is better than nothing.
 615          */
 616         oe = *e;
 617
 618         ob = nil;
 619         b = rb;
 620         for(; DEPTH(e->type) > depth; e->type--){
 621                 nb = vtcacheglobal(r->c, b->data, e->type-1);
 622                 if(nb == nil)
 623                         break;
 624                 if(ob!=nil && ob!=rb)
 625                         vtblockput(ob);
 626                 ob = b;
 627                 b = nb;
 628         }
 629
 630         if(b == rb){
 631                 vtblockput(rb);
 632                 return 0;
 633         }
 634
 635         /*
 636          * Right now, e points at the root block rb, b is the new root block,
 637          * and ob points at b.  To update:
 638          *
 639          *      (i) change e to point at b
 640          *      (ii) zero the pointer ob -> b
 641          *      (iii) free the root block
 642          *
 643          * p (the block containing e) must be written before
 644          * anything else.
 645          */
 646
 647         /* (i) */
 648         memmove(e->score, b->score, VtScoreSize);
 649         vtentrypack(e, p->data, r->offset % r->epb);
 650
 651         /* (ii) */
 652         memmove(ob->data, vtzeroscore, VtScoreSize);
 653
 654         /* (iii) */
 655         vtblockput(rb);
 656         if(ob!=nil && ob!=rb)
 657                 vtblockput(ob);
 658         vtblockput(b);
 659
 660         if(DEPTH(e->type) == depth)
 661                 return 0;
 662         return -1;
 663 }
 664
 665 static int
 666 mkindices(VtEntry *e, u32int bn, int *index)
 667 {
 668         int i, np;
 669
 670         memset(index, 0, (VtPointerDepth+1)*sizeof(int));
 671
 672         np = e->psize/VtScoreSize;
 673         for(i=0; bn > 0; i++){
 674                 if(i >= VtPointerDepth){
 675                         werrstr("bad address 0x%lux", (ulong)bn);
 676                         return -1;
 677                 }
 678                 index[i] = bn % np;
 679                 bn /= np;
 680         }
 681         return i;
 682 }
 683
 684 VtBlock *
 685 vtfileblock(VtFile *r, u32int bn, int mode)
 686 {
 687         VtBlock *b, *bb;
 688         int index[VtPointerDepth+1];
 689         VtEntry e;
 690         int i;
 691         int m;
 692
 693         assert(ISLOCKED(r));
 694         assert(bn != NilBlock);
 695
 696         b = fileload(r, &e);
 697         if(b == nil)
 698                 return nil;
 699
 700         i = mkindices(&e, bn, index);
 701         if(i < 0)
 702                 goto Err;
 703         if(i > DEPTH(e.type)){
 704                 if(mode == VtOREAD){
 705                         werrstr("bad address 0x%lux", (ulong)bn);
 706                         goto Err;
 707                 }
 708                 index[i] = 0;
 709                 if(growdepth(r, b, &e, i) < 0)
 710                         goto Err;
 711         }
 712
 713 assert(b->type == VtDirType);
 714
 715         index[DEPTH(e.type)] = r->offset % r->epb;
 716
 717         /* mode for intermediate block */
 718         m = mode;
 719         if(m == VtOWRITE)
 720                 m = VtORDWR;
 721
 722         for(i=DEPTH(e.type); i>=0; i--){
 723                 bb = blockwalk(b, index[i], r->c, i==0 ? mode : m, &e);
 724                 if(bb == nil)
 725                         goto Err;
 726                 vtblockput(b);
 727                 b = bb;
 728         }
 729         b->pc = getcallerpc(&r);
 730         return b;
 731 Err:
 732         vtblockput(b);
 733         return nil;
 734 }
 735
 736 int
 737 vtfileblockscore(VtFile *r, u32int bn, uchar score[VtScoreSize])
 738 {
 739         VtBlock *b, *bb;
 740         int index[VtPointerDepth+1];
 741         VtEntry e;
 742         int i;
 743
 744         assert(ISLOCKED(r));
 745         assert(bn != NilBlock);
 746
 747         b = fileload(r, &e);
 748         if(b == nil)
 749                 return -1;
 750
 751         if(DEPTH(e.type) == 0){
 752                 memmove(score, e.score, VtScoreSize);
 753                 vtblockput(b);
 754                 return 0;
 755         }
 756
 757         i = mkindices(&e, bn, index);
 758         if(i < 0){
 759                 vtblockput(b);
 760                 return -1;
 761         }
 762         if(i > DEPTH(e.type)){
 763                 memmove(score, vtzeroscore, VtScoreSize);
 764                 vtblockput(b);
 765                 return 0;
 766         }
 767
 768         index[DEPTH(e.type)] = r->offset % r->epb;
 769
 770         for(i=DEPTH(e.type); i>=1; i--){
 771                 bb = blockwalk(b, index[i], r->c, VtOREAD, &e);
 772                 if(bb == nil)
 773                         goto Err;
 774                 vtblockput(b);
 775                 b = bb;
 776                 if(memcmp(b->score, vtzeroscore, VtScoreSize) == 0)
 777                         break;
 778         }
 779
 780         memmove(score, b->data+index[0]*VtScoreSize, VtScoreSize);
 781         vtblockput(b);
 782         return 0;
 783
 784 Err:
 785         vtblockput(b);
 786         return -1;
 787 }
 788
 789 void
 790 vtfileincref(VtFile *r)
 791 {
 792         qlock(&r->lk);
 793         r->ref++;
 794         qunlock(&r->lk);
 795 }
 796
 797 void
 798 vtfileclose(VtFile *r)
 799 {
 800         if(r == nil)
 801                 return;
 802         qlock(&r->lk);
 803         r->ref--;
 804         if(r->ref){
 805                 qunlock(&r->lk);
 806                 return;
 807         }
 808         assert(r->ref == 0);
 809         qunlock(&r->lk);
 810         if(r->parent)
 811                 vtfileclose(r->parent);
 812         memset(r, ~0, sizeof(*r));
 813         vtfree(r);
 814 }
 815
 816 /*
 817  * Retrieve the block containing the entry for r.
 818  * If a snapshot has happened, we might need
 819  * to get a new copy of the block.  We avoid this
 820  * in the common case by caching the score for
 821  * the block and the last epoch in which it was valid.
 822  *
 823  * We use r->mode to tell the difference between active
 824  * file system VtFiles (VtORDWR) and VtFiles for the
 825  * snapshot file system (VtOREAD).
 826  */
 827 static VtBlock*
 828 fileloadblock(VtFile *r, int mode)
 829 {
 830         char e[ERRMAX];
 831         u32int addr;
 832         VtBlock *b;
 833
 834         switch(r->mode){
 835         default:
 836                 assert(0);
 837         case VtORDWR:
 838                 assert(r->mode == VtORDWR);
 839                 if(r->local == 1){
 840                         b = vtcacheglobal(r->c, r->score, VtDirType);
 841                         if(b == nil)
 842                                 return nil;
 843                         b->pc = getcallerpc(&r);
 844                         return b;
 845                 }
 846                 assert(r->parent != nil);
 847                 if(vtfilelock(r->parent, VtORDWR) < 0)
 848                         return nil;
 849                 b = vtfileblock(r->parent, r->offset/r->epb, VtORDWR);
 850                 vtfileunlock(r->parent);
 851                 if(b == nil)
 852                         return nil;
 853                 memmove(r->score, b->score, VtScoreSize);
 854                 r->local = 1;
 855                 return b;
 856
 857         case VtOREAD:
 858                 if(mode == VtORDWR){
 859                         werrstr("read/write lock of read-only file");
 860                         return nil;
 861                 }
 862                 addr = vtglobaltolocal(r->score);
 863                 if(addr == NilBlock)
 864                         return vtcacheglobal(r->c, r->score, VtDirType);
 865
 866                 b = vtcachelocal(r->c, addr, VtDirType);
 867                 if(b)
 868                         return b;
 869
 870                 /*
 871                  * If it failed because the epochs don't match, the block has been
 872                  * archived and reclaimed.  Rewalk from the parent and get the
 873                  * new pointer.  This can't happen in the VtORDWR case
 874                  * above because blocks in the current epoch don't get
 875                  * reclaimed.  The fact that we're VtOREAD means we're
 876                  * a snapshot.  (Or else the file system is read-only, but then
 877                  * the archiver isn't going around deleting blocks.)
 878                  */
 879                 rerrstr(e, sizeof e);
 880                 if(strcmp(e, ELabelMismatch) == 0){
 881                         if(vtfilelock(r->parent, VtOREAD) < 0)
 882                                 return nil;
 883                         b = vtfileblock(r->parent, r->offset/r->epb, VtOREAD);
 884                         vtfileunlock(r->parent);
 885                         if(b){
 886                                 fprint(2, "vtfilealloc: lost %V found %V\n",
 887                                         r->score, b->score);
 888                                 memmove(r->score, b->score, VtScoreSize);
 889                                 return b;
 890                         }
 891                 }
 892                 return nil;
 893         }
 894 }
 895
 896 int
 897 vtfilelock(VtFile *r, int mode)
 898 {
 899         VtBlock *b;
 900
 901         if(mode == -1)
 902                 mode = r->mode;
 903
 904         b = fileloadblock(r, mode);
 905         if(b == nil)
 906                 return -1;
 907         /*
 908          * The fact that we are holding b serves as the
 909          * lock entitling us to write to r->b.
 910          */
 911         assert(r->b == nil);
 912         r->b = b;
 913         b->pc = getcallerpc(&r);
 914         return 0;
 915 }
 916
 917 /*
 918  * Lock two (usually sibling) VtFiles.  This needs special care
 919  * because the Entries for both vtFiles might be in the same block.
 920  * We also try to lock blocks in left-to-right order within the tree.
 921  */
 922 int
 923 vtfilelock2(VtFile *r, VtFile *rr, int mode)
 924 {
 925         VtBlock *b, *bb;
 926
 927         if(rr == nil)
 928                 return vtfilelock(r, mode);
 929
 930         if(mode == -1)
 931                 mode = r->mode;
 932
 933         if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
 934                 b = fileloadblock(r, mode);
 935                 if(b == nil)
 936                         return -1;
 937                 vtblockduplock(b);
 938                 bb = b;
 939         }else if(r->parent==rr->parent || r->offset > rr->offset){
 940                 bb = fileloadblock(rr, mode);
 941                 b = fileloadblock(r, mode);
 942         }else{
 943                 b = fileloadblock(r, mode);
 944                 bb = fileloadblock(rr, mode);
 945         }
 946         if(b == nil || bb == nil){
 947                 if(b)
 948                         vtblockput(b);
 949                 if(bb)
 950                         vtblockput(bb);
 951                 return -1;
 952         }
 953
 954         /*
 955          * The fact that we are holding b and bb serves
 956          * as the lock entitling us to write to r->b and rr->b.
 957          */
 958         r->b = b;
 959         rr->b = bb;
 960         b->pc = getcallerpc(&r);
 961         bb->pc = getcallerpc(&r);
 962         return 0;
 963 }
 964
 965 void
 966 vtfileunlock(VtFile *r)
 967 {
 968         VtBlock *b;
 969
 970         if(r->b == nil){
 971                 fprint(2, "vtfileunlock: already unlocked\n");
 972                 abort();
 973         }
 974         b = r->b;
 975         r->b = nil;
 976         vtblockput(b);
 977 }
 978
 979 static VtBlock*
 980 fileload(VtFile *r, VtEntry *e)
 981 {
 982         VtBlock *b;
 983
 984         assert(ISLOCKED(r));
 985         b = r->b;
 986         if(vtentryunpack(e, b->data, r->offset % r->epb) < 0)
 987                 return nil;
 988         vtblockduplock(b);
 989         return b;
 990 }
 991
 992 static int
 993 sizetodepth(uvlong s, int psize, int dsize)
 994 {
 995         int np;
 996         int d;
 997
 998         /* determine pointer depth */
 999         np = psize/VtScoreSize;
1000         s = (s + dsize - 1)/dsize;
1001         for(d = 0; s > 1; d++)
1002                 s = (s + np - 1)/np;
1003         return d;
1004 }
1005
1006 long
1007 vtfileread(VtFile *f, void *data, long count, vlong offset)
1008 {
1009         int frag;
1010         VtBlock *b;
1011         VtEntry e;
1012
1013         assert(ISLOCKED(f));
1014
1015         vtfilegetentry(f, &e);
1016         if(count == 0)
1017                 return 0;
1018         if(count < 0 || offset < 0){
1019                 werrstr("vtfileread: bad offset or count");
1020                 return -1;
1021         }
1022         if(offset >= e.size)
1023                 return 0;
1024
1025         if(offset+count > e.size)
1026                 count = e.size - offset;
1027
1028         frag = offset % e.dsize;
1029         if(frag+count > e.dsize)
1030                 count = e.dsize - frag;
1031
1032         b = vtfileblock(f, offset/e.dsize, VtOREAD);
1033         if(b == nil)
1034                 return -1;
1035
1036         memmove(data, b->data+frag, count);
1037         vtblockput(b);
1038         return count;
1039 }
1040
1041 static long
1042 filewrite1(VtFile *f, void *data, long count, vlong offset)
1043 {
1044         int frag, m;
1045         VtBlock *b;
1046         VtEntry e;
1047
1048         vtfilegetentry(f, &e);
1049         if(count < 0 || offset < 0){
1050                 werrstr("vtfilewrite: bad offset or count");
1051                 return -1;
1052         }
1053
1054         frag = offset % e.dsize;
1055         if(frag+count > e.dsize)
1056                 count = e.dsize - frag;
1057
1058         m = VtORDWR;
1059         if(frag == 0 && count == e.dsize)
1060                 m = VtOWRITE;
1061
1062         b = vtfileblock(f, offset/e.dsize, m);
1063         if(b == nil)
1064                 return -1;
1065
1066         memmove(b->data+frag, data, count);
1067         if(m == VtOWRITE && frag+count < e.dsize)
1068                 memset(b->data+frag+count, 0, e.dsize-frag-count);
1069
1070         if(offset+count > e.size){
1071                 vtfilegetentry(f, &e);
1072                 e.size = offset+count;
1073                 vtfilesetentry(f, &e);
1074         }
1075
1076         vtblockput(b);
1077         return count;
1078 }
1079
1080 long
1081 vtfilewrite(VtFile *f, void *data, long count, vlong offset)
1082 {
1083         long tot, m;
1084
1085         assert(ISLOCKED(f));
1086
1087         tot = 0;
1088         m = 0;
1089         while(tot < count){
1090                 m = filewrite1(f, (char*)data+tot, count-tot, offset+tot);
1091                 if(m <= 0)
1092                         break;
1093                 tot += m;
1094         }
1095         if(tot==0)
1096                 return m;
1097         return tot;
1098 }
1099
1100 static int
1101 flushblock(VtCache *c, VtBlock *bb, uchar score[VtScoreSize], int ppb, int epb,
1102         int type)
1103 {
1104         u32int addr;
1105         VtBlock *b;
1106         VtEntry e;
1107         int i;
1108
1109         addr = vtglobaltolocal(score);
1110         if(addr == NilBlock)
1111                 return 0;
1112
1113         if(bb){
1114                 b = bb;
1115                 if(memcmp(b->score, score, VtScoreSize) != 0)
1116                         abort();
1117         }else
1118                 if((b = vtcachelocal(c, addr, type)) == nil)
1119                         return -1;
1120
1121         switch(type){
1122         case VtDataType:
1123                 break;
1124
1125         case VtDirType:
1126                 for(i=0; i<epb; i++){
1127                         if(vtentryunpack(&e, b->data, i) < 0)
1128                                 goto Err;
1129                         if(!(e.flags&VtEntryActive))
1130                                 continue;
1131                         if(flushblock(c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1132                                 e.type) < 0)
1133                                 goto Err;
1134                         vtentrypack(&e, b->data, i);
1135                 }
1136                 break;
1137
1138         default:        /* VtPointerTypeX */
1139                 for(i=0; i<ppb; i++){
1140                         if(flushblock(c, nil, b->data+VtScoreSize*i, ppb, epb, type-1) < 0)
1141                                 goto Err;
1142                 }
1143                 break;
1144         }
1145
1146         if(vtblockwrite(b) < 0)
1147                 goto Err;
1148         memmove(score, b->score, VtScoreSize);
1149         if(b != bb)
1150                 vtblockput(b);
1151         return 0;
1152
1153 Err:
1154         if(b != bb)
1155                 vtblockput(b);
1156         return -1;
1157 }
1158
1159 int
1160 vtfileflush(VtFile *f)
1161 {
1162         int ret;
1163         VtBlock *b;
1164         VtEntry e;
1165
1166         assert(ISLOCKED(f));
1167         b = fileload(f, &e);
1168         if(!(e.flags&VtEntryLocal)){
1169                 vtblockput(b);
1170                 return 0;
1171         }
1172
1173         ret = flushblock(f->c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1174                 e.type);
1175         if(ret < 0){
1176                 vtblockput(b);
1177                 return -1;
1178         }
1179
1180         vtentrypack(&e, b->data, f->offset % f->epb);
1181         vtblockput(b);
1182         return 0;
1183 }
1184
1185 int
1186 vtfileflushbefore(VtFile *r, u64int offset)
1187 {
1188         VtBlock *b, *bb;
1189         VtEntry e;
1190         int i, base, depth, ppb, epb, doflush;
1191         int index[VtPointerDepth+1], j, ret;
1192         VtBlock *bi[VtPointerDepth+2];
1193         uchar *score;
1194
1195         assert(ISLOCKED(r));
1196         if(offset == 0)
1197                 return 0;
1198
1199         b = fileload(r, &e);
1200         if(b == nil)
1201                 return -1;
1202
1203         /*
1204          * compute path through tree for the last written byte and the next one.
1205          */
1206         ret = -1;
1207         memset(bi, 0, sizeof bi);
1208         depth = DEPTH(e.type);
1209         bi[depth+1] = b;
1210         i = mkindices(&e, (offset-1)/e.dsize, index);
1211         if(i < 0)
1212                 goto Err;
1213         if(i > depth)
1214                 goto Err;
1215         ppb = e.psize / VtScoreSize;
1216         epb = e.dsize / VtEntrySize;
1217
1218         /*
1219          * load the blocks along the last written byte
1220          */
1221         index[depth] = r->offset % r->epb;
1222         for(i=depth; i>=0; i--){
1223                 bb = blockwalk(b, index[i], r->c, VtORDWR, &e);
1224                 if(bb == nil)
1225                         goto Err;
1226                 bi[i] = bb;
1227                 b = bb;
1228         }
1229         ret = 0;
1230
1231         /*
1232          * walk up the path from leaf to root, flushing anything that
1233          * has been finished.
1234          */
1235         base = e.type&~VtTypeDepthMask;
1236         for(i=0; i<=depth; i++){
1237                 doflush = 0;
1238                 if(i == 0){
1239                         /* leaf: data or dir block */
1240                         if(offset%e.dsize == 0)
1241                                 doflush = 1;
1242                 }else{
1243                         /*
1244                          * interior node: pointer blocks.
1245                          * specifically, b = bi[i] is a block whose index[i-1]'th entry
1246                          * points at bi[i-1].
1247                          */
1248                         b = bi[i];
1249
1250                         /*
1251                          * the index entries up to but not including index[i-1] point at
1252                          * finished blocks, so flush them for sure.
1253                          */
1254                         for(j=0; j<index[i-1]; j++)
1255                                 if(flushblock(r->c, nil, b->data+j*VtScoreSize, ppb, epb, base+i-1) < 0)
1256                                         goto Err;
1257
1258                         /*
1259                          * if index[i-1] is the last entry in the block and is global
1260                          * (i.e. the kid is flushed), then we can flush this block.
1261                          */
1262                         if(j==ppb-1 && vtglobaltolocal(b->data+j*VtScoreSize)==NilBlock)
1263                                 doflush = 1;
1264                 }
1265                 if(doflush){
1266                         if(i == depth)
1267                                 score = e.score;
1268                         else
1269                                 score = bi[i+1]->data+index[i]*VtScoreSize;
1270                         if(flushblock(r->c, bi[i], score, ppb, epb, base+i) < 0)
1271                                 goto Err;
1272                 }
1273         }
1274
1275 Err:
1276         /* top: entry.  do this always so that the score is up-to-date */
1277         vtentrypack(&e, bi[depth+1]->data, index[depth]);
1278         for(i=0; i<nelem(bi); i++)
1279                 if(bi[i])
1280                         vtblockput(bi[i]);
1281         return ret;
1282 }