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