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