op public repos

Blob

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