1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 #include "error.h"
5 #include "9.h"
6 
7 static int	sizeToDepth(uvlong s, int psize, int dsize);
8 static u32int 	tagGen(void);
9 static Block 	*sourceLoad(Source *r, Entry *e);
10 static int	sourceShrinkDepth(Source*, Block*, Entry*, int);
11 static int	sourceShrinkSize(Source*, Entry*, uvlong);
12 static int	sourceGrowDepth(Source*, Block*, Entry*, int);
13 
14 #define sourceIsLocked(r)	((r)->b != nil)
15 
16 static Source *
17 sourceAlloc(Fs *fs, Block *b, Source *p, u32int offset, int mode, int issnapshot)
18 {
19 	int epb;
20 	u32int epoch;
21 	char *pname = nil;
22 	Source *r;
23 	Entry e;
24 
25 	assert(p==nil || sourceIsLocked(p));
26 
27 	if(p == nil){
28 		assert(offset == 0);
29 		epb = 1;
30 	}else
31 		epb = p->dsize / VtEntrySize;
32 
33 	if(b->l.type != BtDir)
34 		goto Bad;
35 
36 	/*
37 	 * a non-active entry is the only thing that
38 	 * can legitimately happen here. all the others
39 	 * get prints.
40 	 */
41 	if(!entryUnpack(&e, b->data, offset % epb)){
42 		pname = sourceName(p);
43 		consPrint("%s: %s %V: sourceAlloc: entryUnpack failed\n",
44 			fs->name, pname, b->score);
45 		goto Bad;
46 	}
47 	if(!(e.flags & VtEntryActive)){
48 		pname = sourceName(p);
49 		if(0) consPrint("%s: %s %V: sourceAlloc: not active\n",
50 			fs->name, pname, e.score);
51 		goto Bad;
52 	}
53 	if(e.psize < 256 || e.dsize < 256){
54 		pname = sourceName(p);
55 		consPrint("%s: %s %V: sourceAlloc: psize %ud or dsize %ud < 256\n",
56 			fs->name, pname, e.score, e.psize, e.dsize);
57 		goto Bad;
58 	}
59 
60 	if(e.depth < sizeToDepth(e.size, e.psize, e.dsize)){
61 		pname = sourceName(p);
62 		consPrint("%s: %s %V: sourceAlloc: depth %ud size %llud "
63 			"psize %ud dsize %ud\n", fs->name, pname,
64 			e.score, e.depth, e.size, e.psize, e.dsize);
65 		goto Bad;
66 	}
67 
68 	if((e.flags & VtEntryLocal) && e.tag == 0){
69 		pname = sourceName(p);
70 		consPrint("%s: %s %V: sourceAlloc: flags %#ux tag %#ux\n",
71 			fs->name, pname, e.score, e.flags, e.tag);
72 		goto Bad;
73 	}
74 
75 	if(e.dsize > fs->blockSize || e.psize > fs->blockSize){
76 		pname = sourceName(p);
77 		consPrint("%s: %s %V: sourceAlloc: psize %ud or dsize %ud "
78 			"> blocksize %ud\n", fs->name, pname, e.score,
79 			e.psize, e.dsize, fs->blockSize);
80 		goto Bad;
81 	}
82 
83 	epoch = b->l.epoch;
84 	if(mode == OReadWrite){
85 		if(e.snap != 0){
86 			werrstr(ESnapRO);
87 			return nil;
88 		}
89 	}else if(e.snap != 0){
90 		if(e.snap < fs->elo){
91 			werrstr(ESnapOld);
92 			return nil;
93 		}
94 		if(e.snap >= fs->ehi)
95 			goto Bad;
96 		epoch = e.snap;
97 	}
98 
99 	r = vtmallocz(sizeof(Source));
100 	r->fs = fs;
101 	r->mode = mode;
102 	r->issnapshot = issnapshot;
103 	r->dsize = e.dsize;
104 	r->gen = e.gen;
105 	r->dir = (e.flags & _VtEntryDir) != 0;
106 	r->ref = 1;
107 	r->parent = p;
108 	if(p){
109 		qlock(&p->lk);
110 		assert(mode == OReadOnly || p->mode == OReadWrite);
111 		p->ref++;
112 		qunlock(&p->lk);
113 	}
114 	r->epoch = epoch;
115 //	consPrint("sourceAlloc: have %V be.%d fse.%d %s\n", b->score,
116 //		b->l.epoch, r->fs->ehi, mode == OReadWrite? "rw": "ro");
117 	memmove(r->score, b->score, VtScoreSize);
118 	r->scoreEpoch = b->l.epoch;
119 	r->offset = offset;
120 	r->epb = epb;
121 	r->tag = b->l.tag;
122 
123 //	consPrint("%s: sourceAlloc: %p -> %V %d\n", r, r->score, r->offset);
124 
125 	return r;
126 Bad:
127 	free(pname);
128 	werrstr(EBadEntry);
129 	return nil;
130 }
131 
132 Source *
133 sourceRoot(Fs *fs, u32int addr, int mode)
134 {
135 	Source *r;
136 	Block *b;
137 
138 	b = cacheLocalData(fs->cache, addr, BtDir, RootTag, mode, 0);
139 	if(b == nil)
140 		return nil;
141 
142 	if(mode == OReadWrite && b->l.epoch != fs->ehi){
143 		consPrint("sourceRoot: fs->ehi = %ud, b->l = %L\n",
144 			fs->ehi, &b->l);
145 		blockPut(b);
146 		werrstr(EBadRoot);
147 		return nil;
148 	}
149 
150 	r = sourceAlloc(fs, b, nil, 0, mode, 0);
151 	blockPut(b);
152 	return r;
153 }
154 
155 Source *
156 sourceOpen(Source *r, ulong offset, int mode, int issnapshot)
157 {
158 	ulong bn;
159 	Block *b;
160 
161 	assert(sourceIsLocked(r));
162 	if(r->mode == OReadWrite)
163 		assert(r->epoch == r->b->l.epoch);
164 	if(!r->dir){
165 		werrstr(ENotDir);
166 		return nil;
167 	}
168 
169 	bn = offset/(r->dsize/VtEntrySize);
170 
171 	b = sourceBlock(r, bn, mode);
172 	if(b == nil)
173 		return nil;
174 	r = sourceAlloc(r->fs, b, r, offset, mode, issnapshot);
175 	blockPut(b);
176 	return r;
177 }
178 
179 Source *
180 sourceCreate(Source *r, int dsize, int dir, u32int offset)
181 {
182 	int i, epb, psize;
183 	u32int bn, size;
184 	Block *b;
185 	Entry e;
186 	Source *rr;
187 
188 	assert(sourceIsLocked(r));
189 
190 	if(!r->dir){
191 		werrstr(ENotDir);
192 		return nil;
193 	}
194 
195 	epb = r->dsize/VtEntrySize;
196 	psize = (dsize/VtScoreSize)*VtScoreSize;
197 
198 	size = sourceGetDirSize(r);
199 	if(offset == 0){
200 		/*
201 		 * look at a random block to see if we can find an empty entry
202 		 */
203 		offset = lnrand(size+1);
204 		offset -= offset % epb;
205 	}
206 
207 	/* try the given block and then try the last block */
208 	for(;;){
209 		bn = offset/epb;
210 		b = sourceBlock(r, bn, OReadWrite);
211 		if(b == nil)
212 			return nil;
213 		for(i=offset%r->epb; i<epb; i++){
214 			entryUnpack(&e, b->data, i);
215 			if((e.flags&VtEntryActive) == 0 && e.gen != ~0)
216 				goto Found;
217 		}
218 		blockPut(b);
219 		if(offset == size){
220 			fprint(2, "sourceCreate: cannot happen\n");
221 			werrstr("sourceCreate: cannot happen");
222 			return nil;
223 		}
224 		offset = size;
225 	}
226 
227 Found:
228 	/* found an entry - gen already set */
229 	e.psize = psize;
230 	e.dsize = dsize;
231 	assert(psize && dsize);
232 	e.flags = VtEntryActive;
233 	if(dir)
234 		e.flags |= _VtEntryDir;
235 	e.depth = 0;
236 	e.size = 0;
237 	memmove(e.score, vtzeroscore, VtScoreSize);
238 	e.tag = 0;
239 	e.snap = 0;
240 	e.archive = 0;
241 	entryPack(&e, b->data, i);
242 	blockDirty(b);
243 
244 	offset = bn*epb + i;
245 	if(offset+1 > size){
246 		if(!sourceSetDirSize(r, offset+1)){
247 			blockPut(b);
248 			return nil;
249 		}
250 	}
251 
252 	rr = sourceAlloc(r->fs, b, r, offset, OReadWrite, 0);
253 	blockPut(b);
254 	return rr;
255 }
256 
257 static int
258 sourceKill(Source *r, int doremove)
259 {
260 	Entry e;
261 	Block *b;
262 	u32int addr;
263 	u32int tag;
264 	int type;
265 
266 	assert(sourceIsLocked(r));
267 	b = sourceLoad(r, &e);
268 	if(b == nil)
269 		return 0;
270 
271 	assert(b->l.epoch == r->fs->ehi);
272 
273 	if(doremove==0 && e.size == 0){
274 		/* already truncated */
275 		blockPut(b);
276 		return 1;
277 	}
278 
279 	/* remember info on link we are removing */
280 	addr = globalToLocal(e.score);
281 	type = entryType(&e);
282 	tag = e.tag;
283 
284 	if(doremove){
285 		if(e.gen != ~0)
286 			e.gen++;
287 		e.dsize = 0;
288 		e.psize = 0;
289 		e.flags = 0;
290 	}else{
291 		e.flags &= ~VtEntryLocal;
292 	}
293 	e.depth = 0;
294 	e.size = 0;
295 	e.tag = 0;
296 	memmove(e.score, vtzeroscore, VtScoreSize);
297 	entryPack(&e, b->data, r->offset % r->epb);
298 	blockDirty(b);
299 	if(addr != NilBlock)
300 		blockRemoveLink(b, addr, type, tag, 1);
301 	blockPut(b);
302 
303 	if(doremove){
304 		sourceUnlock(r);
305 		sourceClose(r);
306 	}
307 
308 	return 1;
309 }
310 
311 int
312 sourceRemove(Source *r)
313 {
314 	return sourceKill(r, 1);
315 }
316 
317 int
318 sourceTruncate(Source *r)
319 {
320 	return sourceKill(r, 0);
321 }
322 
323 uvlong
324 sourceGetSize(Source *r)
325 {
326 	Entry e;
327 	Block *b;
328 
329 	assert(sourceIsLocked(r));
330 	b = sourceLoad(r, &e);
331 	if(b == nil)
332 		return 0;
333 	blockPut(b);
334 
335 	return e.size;
336 }
337 
338 static int
339 sourceShrinkSize(Source *r, Entry *e, uvlong size)
340 {
341 	int i, type, ppb;
342 	uvlong ptrsz;
343 	u32int addr;
344 	uchar score[VtScoreSize];
345 	Block *b;
346 
347 	type = entryType(e);
348 	b = cacheGlobal(r->fs->cache, e->score, type, e->tag, OReadWrite);
349 	if(b == nil)
350 		return 0;
351 
352 	ptrsz = e->dsize;
353 	ppb = e->psize/VtScoreSize;
354 	for(i=0; i+1<e->depth; i++)
355 		ptrsz *= ppb;
356 
357 	while(type&BtLevelMask){
358 		if(b->addr == NilBlock || b->l.epoch != r->fs->ehi){
359 			/* not worth copying the block just so we can zero some of it */
360 			blockPut(b);
361 			return 0;
362 		}
363 
364 		/*
365 		 * invariant: each pointer in the tree rooted at b accounts for ptrsz bytes
366 		 */
367 
368 		/* zero the pointers to unnecessary blocks */
369 		i = (size+ptrsz-1)/ptrsz;
370 		for(; i<ppb; i++){
371 			addr = globalToLocal(b->data+i*VtScoreSize);
372 			memmove(b->data+i*VtScoreSize, vtzeroscore, VtScoreSize);
373 			blockDirty(b);
374 			if(addr != NilBlock)
375 				blockRemoveLink(b, addr, type-1, e->tag, 1);
376 		}
377 
378 		/* recurse (go around again) on the partially necessary block */
379 		i = size/ptrsz;
380 		size = size%ptrsz;
381 		if(size == 0){
382 			blockPut(b);
383 			return 1;
384 		}
385 		ptrsz /= ppb;
386 		type--;
387 		memmove(score, b->data+i*VtScoreSize, VtScoreSize);
388 		blockPut(b);
389 		b = cacheGlobal(r->fs->cache, score, type, e->tag, OReadWrite);
390 		if(b == nil)
391 			return 0;
392 	}
393 
394 	if(b->addr == NilBlock || b->l.epoch != r->fs->ehi){
395 		blockPut(b);
396 		return 0;
397 	}
398 
399 	/*
400 	 * No one ever truncates BtDir blocks.
401 	 */
402 	if(type == BtData && e->dsize > size){
403 		memset(b->data+size, 0, e->dsize-size);
404 		blockDirty(b);
405 	}
406 	blockPut(b);
407 	return 1;
408 }
409 
410 int
411 sourceSetSize(Source *r, uvlong size)
412 {
413 	int depth;
414 	Entry e;
415 	Block *b;
416 
417 	assert(sourceIsLocked(r));
418 	if(size == 0)
419 		return sourceTruncate(r);
420 
421 	if(size > VtMaxFileSize || size > ((uvlong)MaxBlock)*r->dsize){
422 		werrstr(ETooBig);
423 		return 0;
424 	}
425 
426 	b = sourceLoad(r, &e);
427 	if(b == nil)
428 		return 0;
429 
430 	/* quick out */
431 	if(e.size == size){
432 		blockPut(b);
433 		return 1;
434 	}
435 
436 	depth = sizeToDepth(size, e.psize, e.dsize);
437 
438 	if(depth < e.depth){
439 		if(!sourceShrinkDepth(r, b, &e, depth)){
440 			blockPut(b);
441 			return 0;
442 		}
443 	}else if(depth > e.depth){
444 		if(!sourceGrowDepth(r, b, &e, depth)){
445 			blockPut(b);
446 			return 0;
447 		}
448 	}
449 
450 	if(size < e.size)
451 		sourceShrinkSize(r, &e, size);
452 
453 	e.size = size;
454 	entryPack(&e, b->data, r->offset % r->epb);
455 	blockDirty(b);
456 	blockPut(b);
457 
458 	return 1;
459 }
460 
461 int
462 sourceSetDirSize(Source *r, ulong ds)
463 {
464 	uvlong size;
465 	int epb;
466 
467 	assert(sourceIsLocked(r));
468 	epb = r->dsize/VtEntrySize;
469 
470 	size = (uvlong)r->dsize*(ds/epb);
471 	size += VtEntrySize*(ds%epb);
472 	return sourceSetSize(r, size);
473 }
474 
475 ulong
476 sourceGetDirSize(Source *r)
477 {
478 	ulong ds;
479 	uvlong size;
480 	int epb;
481 
482 	assert(sourceIsLocked(r));
483 	epb = r->dsize/VtEntrySize;
484 
485 	size = sourceGetSize(r);
486 	ds = epb*(size/r->dsize);
487 	ds += (size%r->dsize)/VtEntrySize;
488 	return ds;
489 }
490 
491 int
492 sourceGetEntry(Source *r, Entry *e)
493 {
494 	Block *b;
495 
496 	assert(sourceIsLocked(r));
497 	b = sourceLoad(r, e);
498 	if(b == nil)
499 		return 0;
500 	blockPut(b);
501 
502 	return 1;
503 }
504 
505 /*
506  * Must be careful with this.  Doesn't record
507  * dependencies, so don't introduce any!
508  */
509 int
510 sourceSetEntry(Source *r, Entry *e)
511 {
512 	Block *b;
513 	Entry oe;
514 
515 	assert(sourceIsLocked(r));
516 	b = sourceLoad(r, &oe);
517 	if(b == nil)
518 		return 0;
519 	entryPack(e, b->data, r->offset%r->epb);
520 	blockDirty(b);
521 	blockPut(b);
522 
523 	return 1;
524 }
525 
526 static Block *
527 blockWalk(Block *p, int index, int mode, Fs *fs, Entry *e)
528 {
529 	Block *b;
530 	Cache *c;
531 	u32int addr;
532 	int type;
533 	uchar oscore[VtScoreSize], score[VtScoreSize];
534 	Entry oe;
535 
536 	c = fs->cache;
537 
538 	if((p->l.type & BtLevelMask) == 0){
539 		assert(p->l.type == BtDir);
540 		type = entryType(e);
541 		b = cacheGlobal(c, e->score, type, e->tag, mode);
542 	}else{
543 		type = p->l.type - 1;
544 		b = cacheGlobal(c, p->data + index*VtScoreSize, type, e->tag, mode);
545 	}
546 
547 	if(b)
548 		b->pc = getcallerpc(&p);
549 
550 	if(b == nil || mode == OReadOnly)
551 		return b;
552 
553 	if(p->l.epoch != fs->ehi){
554 		fprint(2, "blockWalk: parent not writable\n");
555 		abort();
556 	}
557 	if(b->l.epoch == fs->ehi)
558 		return b;
559 
560 	oe = *e;
561 
562 	/*
563 	 * Copy on write.
564 	 */
565 	if(e->tag == 0){
566 		assert(p->l.type == BtDir);
567 		e->tag = tagGen();
568 		e->flags |= VtEntryLocal;
569 	}
570 
571 	addr = b->addr;
572 	b = blockCopy(b, e->tag, fs->ehi, fs->elo);
573 	if(b == nil)
574 		return nil;
575 
576 	b->pc = getcallerpc(&p);
577 	assert(b->l.epoch == fs->ehi);
578 
579 	blockDirty(b);
580 	memmove(score, b->score, VtScoreSize);
581 	if(p->l.type == BtDir){
582 		memmove(e->score, b->score, VtScoreSize);
583 		entryPack(e, p->data, index);
584 		blockDependency(p, b, index, nil, &oe);
585 	}else{
586 		memmove(oscore, p->data+index*VtScoreSize, VtScoreSize);
587 		memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
588 		blockDependency(p, b, index, oscore, nil);
589 	}
590 	blockDirty(p);
591 
592 	if(addr != NilBlock)
593 		blockRemoveLink(p, addr, type, e->tag, 0);
594 
595 	return b;
596 }
597 
598 /*
599  * Change the depth of the source r.
600  * The entry e for r is contained in block p.
601  */
602 static int
603 sourceGrowDepth(Source *r, Block *p, Entry *e, int depth)
604 {
605 	Block *b, *bb;
606 	u32int tag;
607 	int type;
608 	Entry oe;
609 
610 	assert(sourceIsLocked(r));
611 	assert(depth <= VtPointerDepth);
612 
613 	type = entryType(e);
614 	b = cacheGlobal(r->fs->cache, e->score, type, e->tag, OReadWrite);
615 	if(b == nil)
616 		return 0;
617 
618 	tag = e->tag;
619 	if(tag == 0)
620 		tag = tagGen();
621 
622 	oe = *e;
623 
624 	/*
625 	 * Keep adding layers until we get to the right depth
626 	 * or an error occurs.
627 	 */
628 	while(e->depth < depth){
629 		bb = cacheAllocBlock(r->fs->cache, type+1, tag, r->fs->ehi, r->fs->elo);
630 		if(bb == nil)
631 			break;
632 //fprint(2, "alloc %lux grow %V\n", bb->addr, b->score);
633 		memmove(bb->data, b->score, VtScoreSize);
634 		memmove(e->score, bb->score, VtScoreSize);
635 		e->depth++;
636 		type++;
637 		e->tag = tag;
638 		e->flags |= VtEntryLocal;
639 		blockDependency(bb, b, 0, vtzeroscore, nil);
640 		blockPut(b);
641 		b = bb;
642 		blockDirty(b);
643 	}
644 
645 	entryPack(e, p->data, r->offset % r->epb);
646 	blockDependency(p, b, r->offset % r->epb, nil, &oe);
647 	blockPut(b);
648 	blockDirty(p);
649 
650 	return e->depth == depth;
651 }
652 
653 static int
654 sourceShrinkDepth(Source *r, Block *p, Entry *e, int depth)
655 {
656 	Block *b, *nb, *ob, *rb;
657 	u32int tag;
658 	int type, d;
659 	Entry oe;
660 
661 	assert(sourceIsLocked(r));
662 	assert(depth <= VtPointerDepth);
663 
664 	type = entryType(e);
665 	rb = cacheGlobal(r->fs->cache, e->score, type, e->tag, OReadWrite);
666 	if(rb == nil)
667 		return 0;
668 
669 	tag = e->tag;
670 	if(tag == 0)
671 		tag = tagGen();
672 
673 	/*
674 	 * Walk down to the new root block.
675 	 * We may stop early, but something is better than nothing.
676 	 */
677 	oe = *e;
678 
679 	ob = nil;
680 	b = rb;
681 /* BUG: explain type++.  i think it is a real bug */
682 	for(d=e->depth; d > depth; d--, type++){
683 		nb = cacheGlobal(r->fs->cache, b->data, type-1, tag, OReadWrite);
684 		if(nb == nil)
685 			break;
686 		if(ob!=nil && ob!=rb)
687 			blockPut(ob);
688 		ob = b;
689 		b = nb;
690 	}
691 
692 	if(b == rb){
693 		blockPut(rb);
694 		return 0;
695 	}
696 
697 	/*
698 	 * Right now, e points at the root block rb, b is the new root block,
699 	 * and ob points at b.  To update:
700 	 *
701 	 *	(i) change e to point at b
702 	 *	(ii) zero the pointer ob -> b
703 	 *	(iii) free the root block
704 	 *
705 	 * p (the block containing e) must be written before
706 	 * anything else.
707  	 */
708 
709 	/* (i) */
710 	e->depth = d;
711 	/* might have been local and now global; reverse cannot happen */
712 	if(globalToLocal(b->score) == NilBlock)
713 		e->flags &= ~VtEntryLocal;
714 	memmove(e->score, b->score, VtScoreSize);
715 	entryPack(e, p->data, r->offset % r->epb);
716 	blockDependency(p, b, r->offset % r->epb, nil, &oe);
717 	blockDirty(p);
718 
719 	/* (ii) */
720 	memmove(ob->data, vtzeroscore, VtScoreSize);
721 	blockDependency(ob, p, 0, b->score, nil);
722 	blockDirty(ob);
723 
724 	/* (iii) */
725 	if(rb->addr != NilBlock)
726 		blockRemoveLink(p, rb->addr, rb->l.type, rb->l.tag, 1);
727 
728 	blockPut(rb);
729 	if(ob!=nil && ob!=rb)
730 		blockPut(ob);
731 	blockPut(b);
732 
733 	return d == depth;
734 }
735 
736 /*
737  * Normally we return the block at the given number.
738  * If early is set, we stop earlier in the tree.  Setting early
739  * to 1 gives us the block that contains the pointer to bn.
740  */
741 Block *
742 _sourceBlock(Source *r, ulong bn, int mode, int early, ulong tag)
743 {
744 	Block *b, *bb;
745 	int index[VtPointerDepth+1];
746 	Entry e;
747 	int i, np;
748 	int m;
749 
750 	assert(sourceIsLocked(r));
751 	assert(bn != NilBlock);
752 
753 	/* mode for intermediate block */
754 	m = mode;
755 	if(m == OOverWrite)
756 		m = OReadWrite;
757 
758 	b = sourceLoad(r, &e);
759 	if(b == nil)
760 		return nil;
761 	if(r->issnapshot && (e.flags & VtEntryNoArchive)){
762 		blockPut(b);
763 		werrstr(ENotArchived);
764 		return nil;
765 	}
766 
767 	if(tag){
768 		if(e.tag == 0)
769 			e.tag = tag;
770 		else if(e.tag != tag){
771 			fprint(2, "tag mismatch\n");
772 			werrstr("tag mismatch");
773 			goto Err;
774 		}
775 	}
776 
777 	np = e.psize/VtScoreSize;
778 	memset(index, 0, sizeof(index));
779 	for(i=0; bn > 0; i++){
780 		if(i >= VtPointerDepth){
781 			werrstr(EBadAddr);
782 			goto Err;
783 		}
784 		index[i] = bn % np;
785 		bn /= np;
786 	}
787 
788 	if(i > e.depth){
789 		if(mode == OReadOnly){
790 			werrstr(EBadAddr);
791 			goto Err;
792 		}
793 		if(!sourceGrowDepth(r, b, &e, i))
794 			goto Err;
795 	}
796 
797 	index[e.depth] = r->offset % r->epb;
798 
799 	for(i=e.depth; i>=early; i--){
800 		bb = blockWalk(b, index[i], m, r->fs, &e);
801 		if(bb == nil)
802 			goto Err;
803 		blockPut(b);
804 		b = bb;
805 	}
806 	b->pc = getcallerpc(&r);
807 	return b;
808 Err:
809 	blockPut(b);
810 	return nil;
811 }
812 
813 Block*
814 sourceBlock(Source *r, ulong bn, int mode)
815 {
816 	Block *b;
817 
818 	b = _sourceBlock(r, bn, mode, 0, 0);
819 	if(b)
820 		b->pc = getcallerpc(&r);
821 	return b;
822 }
823 
824 void
825 sourceClose(Source *r)
826 {
827 	if(r == nil)
828 		return;
829 	qlock(&r->lk);
830 	r->ref--;
831 	if(r->ref){
832 		qunlock(&r->lk);
833 		return;
834 	}
835 	assert(r->ref == 0);
836 	qunlock(&r->lk);
837 	if(r->parent)
838 		sourceClose(r->parent);
839 	memset(r, ~0, sizeof(*r));
840 	vtfree(r);
841 }
842 
843 /*
844  * Retrieve the block containing the entry for r.
845  * If a snapshot has happened, we might need
846  * to get a new copy of the block.  We avoid this
847  * in the common case by caching the score for
848  * the block and the last epoch in which it was valid.
849  *
850  * We use r->mode to tell the difference between active
851  * file system sources (OReadWrite) and sources for the
852  * snapshot file system (OReadOnly).
853  */
854 static Block*
855 sourceLoadBlock(Source *r, int mode)
856 {
857 	u32int addr;
858 	Block *b;
859 	char e[ERRMAX];
860 
861 	switch(r->mode){
862 	default:
863 		assert(0);
864 	case OReadWrite:
865 		assert(r->mode == OReadWrite);
866 		/*
867 		 * This needn't be true -- we might bump the low epoch
868 		 * to reclaim some old blocks, but since this score is
869 		 * OReadWrite, the blocks must all still be open, so none
870 		 * are reclaimed.  Thus it's okay that the epoch is so low.
871 		 * Proceed.
872 		assert(r->epoch >= r->fs->elo);
873 		 */
874 		if(r->epoch == r->fs->ehi){
875 			b = cacheGlobal(r->fs->cache, r->score, BtDir, r->tag, OReadWrite);
876 			if(b == nil)
877 				return nil;
878 			assert(r->epoch == b->l.epoch);
879 			return b;
880 		}
881 		assert(r->parent != nil);
882 		if(!sourceLock(r->parent, OReadWrite))
883 			return nil;
884 		b = sourceBlock(r->parent, r->offset/r->epb, OReadWrite);
885 		sourceUnlock(r->parent);
886 		if(b == nil)
887 			return nil;
888 		assert(b->l.epoch == r->fs->ehi);
889 	//	fprint(2, "sourceLoadBlock %p %V => %V\n", r, r->score, b->score);
890 		memmove(r->score, b->score, VtScoreSize);
891 		r->scoreEpoch = b->l.epoch;
892 		r->tag = b->l.tag;
893 		r->epoch = r->fs->ehi;
894 		return b;
895 
896 	case OReadOnly:
897 		addr = globalToLocal(r->score);
898 		if(addr == NilBlock)
899 			return cacheGlobal(r->fs->cache, r->score, BtDir, r->tag, mode);
900 
901 		b = cacheLocalData(r->fs->cache, addr, BtDir, r->tag, mode, r->scoreEpoch);
902 		if(b)
903 			return b;
904 
905 		/*
906 		 * If it failed because the epochs don't match, the block has been
907 		 * archived and reclaimed.  Rewalk from the parent and get the
908 		 * new pointer.  This can't happen in the OReadWrite case
909 		 * above because blocks in the current epoch don't get
910 		 * reclaimed.  The fact that we're OReadOnly means we're
911 		 * a snapshot.  (Or else the file system is read-only, but then
912 		 * the archiver isn't going around deleting blocks.)
913 		 */
914 		rerrstr(e, sizeof e);
915 		if(strcmp(e, ELabelMismatch) == 0){
916 			if(!sourceLock(r->parent, OReadOnly))
917 				return nil;
918 			b = sourceBlock(r->parent, r->offset/r->epb, OReadOnly);
919 			sourceUnlock(r->parent);
920 			if(b){
921 				fprint(2, "sourceAlloc: lost %V found %V\n",
922 					r->score, b->score);
923 				memmove(r->score, b->score, VtScoreSize);
924 				r->scoreEpoch = b->l.epoch;
925 				return b;
926 			}
927 		}
928 		return nil;
929 	}
930 }
931 
932 int
933 sourceLock(Source *r, int mode)
934 {
935 	Block *b;
936 
937 	if(mode == -1)
938 		mode = r->mode;
939 
940 	b = sourceLoadBlock(r, mode);
941 	if(b == nil)
942 		return 0;
943 	/*
944 	 * The fact that we are holding b serves as the
945 	 * lock entitling us to write to r->b.
946 	 */
947 	assert(r->b == nil);
948 	r->b = b;
949 	if(r->mode == OReadWrite)
950 		assert(r->epoch == r->b->l.epoch);
951 	return 1;
952 }
953 
954 /*
955  * Lock two (usually sibling) sources.  This needs special care
956  * because the Entries for both sources might be in the same block.
957  * We also try to lock blocks in left-to-right order within the tree.
958  */
959 int
960 sourceLock2(Source *r, Source *rr, int mode)
961 {
962 	Block *b, *bb;
963 
964 	if(rr == nil)
965 		return sourceLock(r, mode);
966 
967 	if(mode == -1)
968 		mode = r->mode;
969 
970 	if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
971 		b = sourceLoadBlock(r, mode);
972 		if(b == nil)
973 			return 0;
974 		if(memcmp(r->score, rr->score, VtScoreSize) != 0){
975 			memmove(rr->score, b->score, VtScoreSize);
976 			rr->scoreEpoch = b->l.epoch;
977 			rr->tag = b->l.tag;
978 			rr->epoch = rr->fs->ehi;
979 		}
980 		blockDupLock(b);
981 		bb = b;
982 	}else if(r->parent==rr->parent || r->offset > rr->offset){
983 		bb = sourceLoadBlock(rr, mode);
984 		b = sourceLoadBlock(r, mode);
985 	}else{
986 		b = sourceLoadBlock(r, mode);
987 		bb = sourceLoadBlock(rr, mode);
988 	}
989 	if(b == nil || bb == nil){
990 		if(b)
991 			blockPut(b);
992 		if(bb)
993 			blockPut(bb);
994 		return 0;
995 	}
996 
997 	/*
998 	 * The fact that we are holding b and bb serves
999 	 * as the lock entitling us to write to r->b and rr->b.
1000 	 */
1001 	r->b = b;
1002 	rr->b = bb;
1003 	return 1;
1004 }
1005 
1006 void
1007 sourceUnlock(Source *r)
1008 {
1009 	Block *b;
1010 
1011 	if(r->b == nil){
1012 		fprint(2, "sourceUnlock: already unlocked\n");
1013 		abort();
1014 	}
1015 	b = r->b;
1016 	r->b = nil;
1017 	blockPut(b);
1018 }
1019 
1020 static Block*
1021 sourceLoad(Source *r, Entry *e)
1022 {
1023 	Block *b;
1024 
1025 	assert(sourceIsLocked(r));
1026 	b = r->b;
1027 	if(!entryUnpack(e, b->data, r->offset % r->epb))
1028 		return nil;
1029 	if(e->gen != r->gen){
1030 		werrstr(ERemoved);
1031 		return nil;
1032 	}
1033 	blockDupLock(b);
1034 	return b;
1035 }
1036 
1037 static int
1038 sizeToDepth(uvlong s, int psize, int dsize)
1039 {
1040 	int np;
1041 	int d;
1042 
1043 	/* determine pointer depth */
1044 	np = psize/VtScoreSize;
1045 	s = (s + dsize - 1)/dsize;
1046 	for(d = 0; s > 1; d++)
1047 		s = (s + np - 1)/np;
1048 	return d;
1049 }
1050 
1051 static u32int
1052 tagGen(void)
1053 {
1054 	u32int tag;
1055 
1056 	for(;;){
1057 		tag = lrand();
1058 		if(tag >= UserTag)
1059 			break;
1060 	}
1061 	return tag;
1062 }
1063 
1064 char *
1065 sourceName(Source *s)
1066 {
1067 	return fileName(s->file);
1068 }