2 * Manage tree of VtFiles stored in the block cache.
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
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
19 #define MaxBlock (1UL<<31)
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";
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);
32 #define ISLOCKED(r) ((r)->b != nil)
33 #define DEPTH(t) ((t)&VtTypeDepthMask)
36 vtfilealloc(VtCache *c, VtBlock *b, VtFile *p, u32int offset, int mode)
42 assert(p==nil || ISLOCKED(p));
48 epb = p->dsize / VtEntrySize;
50 if(b->type != VtDirType){
51 werrstr("bad block type %#uo", b->type);
56 * a non-active entry is the only thing that
57 * can legitimately happen here. all the others
60 if(vtentryunpack(&e, b->data, offset % epb) < 0){
61 fprint(2, "vtentryunpack failed: %r (%.*H)\n", VtEntrySize, b->data+VtEntrySize*(offset%epb));
64 if(!(e.flags & VtEntryActive)){
65 werrstr("entry not active");
69 if(DEPTH(e.type) < sizetodepth(e.size, e.psize, e.dsize)){
70 fprint(2, "depth %ud size %llud psize %lud dsize %lud\n",
71 DEPTH(e.type), e.size, e.psize, e.dsize);
76 r = vtmallocz(sizeof(VtFile));
83 r->dir = (e.type & VtTypeBaseMask) == VtDirType;
88 assert(mode == VtOREAD || p->mode == VtORDWR);
92 assert(b->addr != NilBlock);
95 memmove(r->score, b->score, VtScoreSize);
103 vtfileroot(VtCache *c, u32int addr, int mode)
108 b = vtcachelocal(c, addr, VtDirType);
111 r = vtfilealloc(c, b, nil, 0, mode);
117 vtfileopenroot(VtCache *c, VtEntry *e)
122 b = vtcacheallocblock(c, VtDirType, VtEntrySize);
126 vtentrypack(e, b->data, 0);
127 f = vtfilealloc(c, b, nil, 0, VtORDWR);
133 vtfilecreateroot(VtCache *c, int psize, int dsize, int type)
137 memset(&e, 0, sizeof e);
138 e.flags = VtEntryActive;
142 memmove(e.score, vtzeroscore, VtScoreSize);
144 return vtfileopenroot(c, &e);
148 vtfileopen(VtFile *r, u32int offset, int mode)
159 bn = offset/(r->dsize/VtEntrySize);
161 b = vtfileblock(r, bn, mode);
164 r = vtfilealloc(r->c, b, r, offset, mode);
170 vtfilecreate(VtFile *r, int psize, int dsize, int type)
172 return _vtfilecreate(r, -1, psize, dsize, type);
176 _vtfilecreate(VtFile *r, int o, int psize, int dsize, int type)
187 assert(type == VtDirType || type == VtDataType);
194 epb = r->dsize/VtEntrySize;
196 size = vtfilegetdirsize(r);
198 * look at a random block to see if we can find an empty entry
201 offset = lnrand(size+1);
202 offset -= offset % epb;
206 /* try the given block and then try the last block */
209 b = vtfileblock(r, bn, VtORDWR);
212 for(i=offset%r->epb; i<epb; i++){
213 if(vtentryunpack(&e, b->data, i) < 0)
215 if((e.flags&VtEntryActive) == 0 && e.gen != ~0)
220 fprint(2, "vtfilecreate: cannot happen\n");
221 werrstr("vtfilecreate: cannot happen");
228 /* found an entry - gen already set */
231 e.flags = VtEntryActive;
234 memmove(e.score, vtzeroscore, VtScoreSize);
235 vtentrypack(&e, b->data, i);
239 if(vtfilesetdirsize(r, offset+1) < 0){
245 rr = vtfilealloc(r->c, b, r, offset, VtORDWR);
251 vtfilekill(VtFile *r, int doremove)
261 if(doremove==0 && e.size == 0){
262 /* already truncated */
274 e.flags &= ~VtEntryLocal;
277 memmove(e.score, vtzeroscore, VtScoreSize);
278 vtentrypack(&e, b->data, r->offset % r->epb);
290 vtfileremove(VtFile *r)
292 return vtfilekill(r, 1);
296 vtfiletruncate(VtFile *r)
298 return vtfilekill(r, 0);
302 vtfilegetsize(VtFile *r)
317 shrinksize(VtFile *r, VtEntry *e, uvlong size)
319 int i, depth, bsiz, type, isdir, ppb;
321 uchar score[VtScoreSize];
324 b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
329 ppb = e->psize/VtScoreSize;
332 for(i=0; i+1<depth; i++)
336 while(DEPTH(type) > 0){
337 if(b->addr == NilBlock){
338 /* not worth copying the block just so we can zero some of it */
344 * invariant: each pointer in the tree rooted at b accounts for ptrsz bytes
347 /* zero the pointers to unnecessary blocks */
348 i = (size+ptrsz-1)/ptrsz;
350 memmove(b->data+i*VtScoreSize, vtzeroscore, VtScoreSize);
352 /* recurse (go around again) on the partially necessary block */
361 memmove(score, b->data+i*VtScoreSize, VtScoreSize);
363 if(type == VtDataType || type == VtDirType)
367 b = vtcacheglobal(r->c, score, type, bsiz);
372 if(b->addr == NilBlock){
378 * No one ever truncates BtDir blocks.
380 if(depth==0 && !isdir && e->dsize > size)
381 memset(b->data+size, 0, e->dsize-size);
387 vtfilesetsize(VtFile *r, u64int size)
395 return vtfiletruncate(r);
397 if(size > VtMaxFileSize || size > ((uvlong)MaxBlock)*r->dsize){
412 depth = sizetodepth(size, e.psize, e.dsize);
413 edepth = DEPTH(e.type);
415 if(shrinkdepth(r, b, &e, depth) < 0){
419 }else if(depth > edepth){
420 if(growdepth(r, b, &e, depth) < 0){
427 shrinksize(r, &e, size);
430 vtentrypack(&e, b->data, r->offset % r->epb);
437 vtfilesetdirsize(VtFile *r, u32int ds)
443 epb = r->dsize/VtEntrySize;
445 size = (uvlong)r->dsize*(ds/epb);
446 size += VtEntrySize*(ds%epb);
447 return vtfilesetsize(r, size);
451 vtfilegetdirsize(VtFile *r)
458 epb = r->dsize/VtEntrySize;
460 size = vtfilegetsize(r);
461 ds = epb*(size/r->dsize);
462 ds += (size%r->dsize)/VtEntrySize;
467 vtfilegetentry(VtFile *r, VtEntry *e)
481 vtfilesetentry(VtFile *r, VtEntry *e)
487 b = fileload(r, &ee);
490 vtentrypack(e, b->data, r->offset % r->epb);
496 blockwalk(VtFile *r, VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
511 score = p->data+index*VtScoreSize;
514 /*print("walk from %V/%d ty %d to %V ty %d\n", p->score, index, p->type, score, type); */
516 if(type == VtDirType || type == VtDataType)
520 if(mode == VtOWRITE && vtglobaltolocal(score) == NilBlock){
521 b = vtcacheallocblock(c, type, size);
525 b = vtcacheglobal(c, score, type, size);
527 if(b == nil || mode == VtOREAD)
530 if(vtglobaltolocal(b->score) != NilBlock)
536 e->flags |= VtEntryLocal;
538 b = vtblockcopy(b/*, e->tag, fs->ehi, fs->elo*/);
543 if(p->type == VtDirType){
544 memmove(e->score, b->score, VtScoreSize);
545 vtentrypack(e, p->data, index);
547 memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
553 * Change the depth of the VtFile r.
554 * The entry e for r is contained in block p.
557 growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
562 assert(depth <= VtPointerDepth);
564 b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
569 * Keep adding layers until we get to the right depth
570 * or an error occurs.
572 while(DEPTH(e->type) < depth){
573 bb = vtcacheallocblock(r->c, e->type+1, r->psize);
576 memmove(bb->data, b->score, VtScoreSize);
577 memmove(e->score, bb->score, VtScoreSize);
579 e->flags |= VtEntryLocal;
584 vtentrypack(e, p->data, r->offset % r->epb);
587 if(DEPTH(e->type) == depth)
593 shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
595 VtBlock *b, *nb, *ob, *rb;
598 assert(depth <= VtPointerDepth);
600 rb = vtcacheglobal(r->c, e->score, e->type, r->psize);
605 * Walk down to the new root block.
606 * We may stop early, but something is better than nothing.
611 for(; DEPTH(e->type) > depth; e->type--){
612 nb = vtcacheglobal(r->c, b->data, e->type-1, r->psize);
615 if(ob!=nil && ob!=rb)
627 * Right now, e points at the root block rb, b is the new root block,
628 * and ob points at b. To update:
630 * (i) change e to point at b
631 * (ii) zero the pointer ob -> b
632 * (iii) free the root block
634 * p (the block containing e) must be written before
639 memmove(e->score, b->score, VtScoreSize);
640 vtentrypack(e, p->data, r->offset % r->epb);
643 memmove(ob->data, vtzeroscore, VtScoreSize);
647 if(ob!=nil && ob!=rb)
651 if(DEPTH(e->type) == depth)
657 mkindices(VtEntry *e, u32int bn, int *index)
661 memset(index, 0, (VtPointerDepth+1)*sizeof(int));
663 np = e->psize/VtScoreSize;
664 for(i=0; bn > 0; i++){
665 if(i >= VtPointerDepth){
666 werrstr("bad address 0x%lux", (ulong)bn);
676 vtfileblock(VtFile *r, u32int bn, int mode)
679 int index[VtPointerDepth+1];
685 assert(bn != NilBlock);
691 i = mkindices(&e, bn, index);
694 if(i > DEPTH(e.type)){
696 werrstr("bad address 0x%lux", (ulong)bn);
700 if(growdepth(r, b, &e, i) < 0)
704 assert(b->type == VtDirType);
706 index[DEPTH(e.type)] = r->offset % r->epb;
708 /* mode for intermediate block */
713 for(i=DEPTH(e.type); i>=0; i--){
714 bb = blockwalk(r, b, index[i], r->c, i==0 ? mode : m, &e);
720 b->pc = getcallerpc(&r);
728 vtfileblockscore(VtFile *r, u32int bn, uchar score[VtScoreSize])
731 int index[VtPointerDepth+1];
736 assert(bn != NilBlock);
742 if(DEPTH(e.type) == 0){
743 memmove(score, e.score, VtScoreSize);
748 i = mkindices(&e, bn, index);
753 if(i > DEPTH(e.type)){
754 memmove(score, vtzeroscore, VtScoreSize);
759 index[DEPTH(e.type)] = r->offset % r->epb;
761 for(i=DEPTH(e.type); i>=1; i--){
762 bb = blockwalk(r, b, index[i], r->c, VtOREAD, &e);
767 if(memcmp(b->score, vtzeroscore, VtScoreSize) == 0)
771 memmove(score, b->data+index[0]*VtScoreSize, VtScoreSize);
781 vtfileincref(VtFile *r)
789 vtfileclose(VtFile *r)
802 vtfileclose(r->parent);
803 memset(r, ~0, sizeof(*r));
808 * Retrieve the block containing the entry for r.
809 * If a snapshot has happened, we might need
810 * to get a new copy of the block. We avoid this
811 * in the common case by caching the score for
812 * the block and the last epoch in which it was valid.
814 * We use r->mode to tell the difference between active
815 * file system VtFiles (VtORDWR) and VtFiles for the
816 * snapshot file system (VtOREAD).
819 fileloadblock(VtFile *r, int mode)
829 assert(r->mode == VtORDWR);
831 b = vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
834 b->pc = getcallerpc(&r);
837 assert(r->parent != nil);
838 if(vtfilelock(r->parent, VtORDWR) < 0)
840 b = vtfileblock(r->parent, r->offset/r->epb, VtORDWR);
841 vtfileunlock(r->parent);
844 memmove(r->score, b->score, VtScoreSize);
850 werrstr("read/write lock of read-only file");
853 addr = vtglobaltolocal(r->score);
855 return vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
857 b = vtcachelocal(r->c, addr, VtDirType);
862 * If it failed because the epochs don't match, the block has been
863 * archived and reclaimed. Rewalk from the parent and get the
864 * new pointer. This can't happen in the VtORDWR case
865 * above because blocks in the current epoch don't get
866 * reclaimed. The fact that we're VtOREAD means we're
867 * a snapshot. (Or else the file system is read-only, but then
868 * the archiver isn't going around deleting blocks.)
870 rerrstr(e, sizeof e);
871 if(strcmp(e, ELabelMismatch) == 0){
872 if(vtfilelock(r->parent, VtOREAD) < 0)
874 b = vtfileblock(r->parent, r->offset/r->epb, VtOREAD);
875 vtfileunlock(r->parent);
877 fprint(2, "vtfilealloc: lost %V found %V\n",
879 memmove(r->score, b->score, VtScoreSize);
888 vtfilelock(VtFile *r, int mode)
895 b = fileloadblock(r, mode);
899 * The fact that we are holding b serves as the
900 * lock entitling us to write to r->b.
904 b->pc = getcallerpc(&r);
909 * Lock two (usually sibling) VtFiles. This needs special care
910 * because the Entries for both vtFiles might be in the same block.
911 * We also try to lock blocks in left-to-right order within the tree.
914 vtfilelock2(VtFile *r, VtFile *rr, int mode)
919 return vtfilelock(r, mode);
924 if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
925 b = fileloadblock(r, mode);
930 }else if(r->parent==rr->parent || r->offset > rr->offset){
931 bb = fileloadblock(rr, mode);
932 b = fileloadblock(r, mode);
934 b = fileloadblock(r, mode);
935 bb = fileloadblock(rr, mode);
937 if(b == nil || bb == nil){
946 * The fact that we are holding b and bb serves
947 * as the lock entitling us to write to r->b and rr->b.
951 b->pc = getcallerpc(&r);
952 bb->pc = getcallerpc(&r);
957 vtfileunlock(VtFile *r)
962 fprint(2, "vtfileunlock: already unlocked\n");
971 fileload(VtFile *r, VtEntry *e)
977 if(vtentryunpack(e, b->data, r->offset % r->epb) < 0)
984 sizetodepth(uvlong s, int psize, int dsize)
989 /* determine pointer depth */
990 np = psize/VtScoreSize;
991 s = (s + dsize - 1)/dsize;
992 for(d = 0; s > 1; d++)
998 vtfileread(VtFile *f, void *data, long count, vlong offset)
1004 assert(ISLOCKED(f));
1006 vtfilegetentry(f, &e);
1009 if(count < 0 || offset < 0){
1010 werrstr("vtfileread: bad offset or count");
1013 if(offset >= e.size)
1016 if(offset+count > e.size)
1017 count = e.size - offset;
1019 frag = offset % e.dsize;
1020 if(frag+count > e.dsize)
1021 count = e.dsize - frag;
1023 b = vtfileblock(f, offset/e.dsize, VtOREAD);
1027 memmove(data, b->data+frag, count);
1033 filewrite1(VtFile *f, void *data, long count, vlong offset)
1039 vtfilegetentry(f, &e);
1040 if(count < 0 || offset < 0){
1041 werrstr("vtfilewrite: bad offset or count");
1045 frag = offset % e.dsize;
1046 if(frag+count > e.dsize)
1047 count = e.dsize - frag;
1050 if(frag == 0 && count == e.dsize)
1053 b = vtfileblock(f, offset/e.dsize, m);
1057 memmove(b->data+frag, data, count);
1058 if(m == VtOWRITE && frag+count < e.dsize)
1059 memset(b->data+frag+count, 0, e.dsize-frag-count);
1061 if(offset+count > e.size){
1062 vtfilegetentry(f, &e);
1063 e.size = offset+count;
1064 vtfilesetentry(f, &e);
1072 vtfilewrite(VtFile *f, void *data, long count, vlong offset)
1076 assert(ISLOCKED(f));
1081 m = filewrite1(f, (char*)data+tot, count-tot, offset+tot);
1092 flushblock(VtCache *c, VtBlock *bb, uchar score[VtScoreSize], int ppb, int epb,
1100 addr = vtglobaltolocal(score);
1101 if(addr == NilBlock)
1106 if(memcmp(b->score, score, VtScoreSize) != 0)
1109 if((b = vtcachelocal(c, addr, type)) == nil)
1117 for(i=0; i<epb; i++){
1118 if(vtentryunpack(&e, b->data, i) < 0)
1120 if(!(e.flags&VtEntryActive))
1122 if(flushblock(c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1125 vtentrypack(&e, b->data, i);
1129 default: /* VtPointerTypeX */
1130 for(i=0; i<ppb; i++){
1131 if(flushblock(c, nil, b->data+VtScoreSize*i, ppb, epb, type-1) < 0)
1137 if(vtblockwrite(b) < 0)
1139 memmove(score, b->score, VtScoreSize);
1151 vtfileflush(VtFile *f)
1157 assert(ISLOCKED(f));
1158 b = fileload(f, &e);
1159 if(!(e.flags&VtEntryLocal)){
1164 ret = flushblock(f->c, nil, e.score, e.psize/VtScoreSize, e.dsize/VtEntrySize,
1171 vtentrypack(&e, b->data, f->offset % f->epb);
1177 vtfileflushbefore(VtFile *r, u64int offset)
1181 int i, base, depth, ppb, epb, doflush;
1182 int index[VtPointerDepth+1], j, ret;
1183 VtBlock *bi[VtPointerDepth+2];
1186 assert(ISLOCKED(r));
1190 b = fileload(r, &e);
1195 * compute path through tree for the last written byte and the next one.
1198 memset(bi, 0, sizeof bi);
1199 depth = DEPTH(e.type);
1201 i = mkindices(&e, (offset-1)/e.dsize, index);
1206 ppb = e.psize / VtScoreSize;
1207 epb = e.dsize / VtEntrySize;
1210 * load the blocks along the last written byte
1212 index[depth] = r->offset % r->epb;
1213 for(i=depth; i>=0; i--){
1214 bb = blockwalk(r, b, index[i], r->c, VtORDWR, &e);
1223 * walk up the path from leaf to root, flushing anything that
1224 * has been finished.
1226 base = e.type&~VtTypeDepthMask;
1227 for(i=0; i<=depth; i++){
1230 /* leaf: data or dir block */
1231 if(offset%e.dsize == 0)
1235 * interior node: pointer blocks.
1236 * specifically, b = bi[i] is a block whose index[i-1]'th entry
1237 * points at bi[i-1].
1242 * the index entries up to but not including index[i-1] point at
1243 * finished blocks, so flush them for sure.
1245 for(j=0; j<index[i-1]; j++)
1246 if(flushblock(r->c, nil, b->data+j*VtScoreSize, ppb, epb, base+i-1) < 0)
1250 * if index[i-1] is the last entry in the block and is global
1251 * (i.e. the kid is flushed), then we can flush this block.
1253 if(j==ppb-1 && vtglobaltolocal(b->data+j*VtScoreSize)==NilBlock)
1260 score = bi[i+1]->data+index[i]*VtScoreSize;
1261 if(flushblock(r->c, bi[i], score, ppb, epb, base+i) < 0)
1267 /* top: entry. do this always so that the score is up-to-date */
1268 vtentrypack(&e, bi[depth+1]->data, index[depth]);
1269 for(i=0; i<nelem(bi); i++)