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