source.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		type = entryType(e);
		b = cacheGlobal(c, e->score, type, e->tag, mode);
	}else{
		type = p->l.type - 1;
		b = cacheGlobal(c, p->data + index*VtScoreSize, type, e->tag, mode);
	}

	if(b)
		b->pc = getcallerpc(&p);

	if(b == nil || mode == OReadOnly)
		return b;

	if(p->l.epoch != fs->ehi){
		fprint(2, "blockWalk: parent not writable\n");
		abort();
	}
	if(b->l.epoch == fs->ehi)
		return b;

	oe = *e;

	/*
	 * Copy on write.
	 */
	if(e->tag == 0){
		assert(p->l.type == BtDir);
		e->tag = tagGen();
		e->flags |= VtEntryLocal;
	}

	addr = b->addr;
	b = blockCopy(b, e->tag, fs->ehi, fs->elo);
	if(b == nil)
		return nil;

	b->pc = getcallerpc(&p);
	assert(b->l.epoch == fs->ehi);

	blockDirty(b);
	memmove(score, b->score, VtScoreSize);
	if(p->l.type == BtDir){
		memmove(e->score, b->score, VtScoreSize);
		entryPack(e, p->data, index);
		blockDependency(p, b, index, nil, &oe);
	}else{
		memmove(oscore, p->data+index*VtScoreSize, VtScoreSize);
		memmove(p->data+index*VtScoreSize, b->score, VtScoreSize);
		blockDependency(p, b, index, oscore, nil);
	}
	blockDirty(p);

	if(addr != NilBlock)
		blockRemoveLink(p, addr, type, e->tag, 0);

	return b;
}

/*
 * Change the depth of the source r.
 * The entry e for r is contained in block p.
 */
static int
sourceGrowDepth(Source *r, Block *p, Entry *e, int depth)
{
	Block *b, *bb;
	u32int tag;
	int type;
	Entry oe;

	assert(sourceIsLocked(r));
	assert(depth <= VtPointerDepth);

	type = entryType(e);
	b = cacheGlobal(r->fs->cache, e->score, type, e->tag, OReadWrite);
	if(b == nil)
		return 0;

	tag = e->tag;
	if(tag == 0)
		tag = tagGen();

	oe = *e;

	/*
	 * Keep adding layers until we get to the right depth
	 * or an error occurs.
	 */
	while(e->depth < depth){
		bb = cacheAllocBlock(r->fs->cache, type+1, tag, r->fs->ehi, r->fs->elo);
		if(bb == nil)
			break;
//fprint(2, "alloc %lux grow %V\n", bb->addr, b->score);
		memmove(bb->data, b->score, VtScoreSize);
		memmove(e->score, bb->score, VtScoreSize);
		e->depth++;
		type++;
		e->tag = tag;
		e->flags |= VtEntryLocal;
		blockDependency(bb, b, 0, vtZeroScore, nil);
		blockPut(b);
		b = bb;
		blockDirty(b);
	}

	entryPack(e, p->data, r->offset % r->epb);
	blockDependency(p, b, r->offset % r->epb, nil, &oe);
	blockPut(b);
	blockDirty(p);

	return e->depth == depth;
}

static int
sourceShrinkDepth(Source *r, Block *p, Entry *e, int depth)
{
	Block *b, *nb, *ob, *rb;
	u32int tag;
	int type, d;
	Entry oe;

	assert(sourceIsLocked(r));
	assert(depth <= VtPointerDepth);

	type = entryType(e);
	rb = cacheGlobal(r->fs->cache, e->score, type, e->tag, OReadWrite);
	if(rb == nil)
		return 0;

	tag = e->tag;
	if(tag == 0)
		tag = tagGen();

	/*
	 * Walk down to the new root block.
	 * We may stop early, but something is better than nothing.
	 */
	oe = *e;

	ob = nil;
	b = rb;
/* BUG: explain type++.  i think it is a real bug */
	for(d=e->depth; d > depth; d--, type++){
		nb = cacheGlobal(r->fs->cache, b->data, type-1, tag, OReadWrite);
		if(nb == nil)
			break;
		if(ob!=nil && ob!=rb)
			blockPut(ob);
		ob = b;
		b = nb;
	}

	if(b == rb){
		blockPut(rb);
		return 0;
	}

	/*
	 * Right now, e points at the root block rb, b is the new root block,
	 * and ob points at b.  To update:
	 *
	 *	(i) change e to point at b
	 *	(ii) zero the pointer ob -> b
	 *	(iii) free the root block
	 *
	 * p (the block containing e) must be written before
	 * anything else.
 	 */

	/* (i) */
	e->depth = d;
	/* might have been local and now global; reverse cannot happen */
	if(globalToLocal(b->score) == NilBlock)
		e->flags &= ~VtEntryLocal;
	memmove(e->score, b->score, VtScoreSize);
	entryPack(e, p->data, r->offset % r->epb);
	blockDependency(p, b, r->offset % r->epb, nil, &oe);
	blockDirty(p);

	/* (ii) */
	memmove(ob->data, vtZeroScore, VtScoreSize);
	blockDependency(ob, p, 0, b->score, nil);
	blockDirty(ob);

	/* (iii) */
	if(rb->addr != NilBlock)
		blockRemoveLink(p, rb->addr, rb->l.type, rb->l.tag, 1);

	blockPut(rb);
	if(ob!=nil && ob!=rb)
		blockPut(ob);
	blockPut(b);

	return d == depth;
}

/*
 * Normally we return the block at the given number.
 * If early is set, we stop earlier in the tree.  Setting early
 * to 1 gives us the block that contains the pointer to bn.
 */
Block *
_sourceBlock(Source *r, ulong bn, int mode, int early, ulong tag)
{
	Block *b, *bb;
	int index[VtPointerDepth+1];
	Entry e;
	int i, np;
	int m;

	assert(sourceIsLocked(r));
	assert(bn != NilBlock);

	/* mode for intermediate block */
	m = mode;
	if(m == OOverWrite)
		m = OReadWrite;

	b = sourceLoad(r, &e);
	if(b == nil)
		return nil;
	if(r->mode == OReadOnly && (e.flags & VtEntryNoArchive)){
		blockPut(b);
		vtSetError(ENotArchived);
		return nil;
	}

	if(tag){
		if(e.tag == 0)
			e.tag = tag;
		else if(e.tag != tag){
			fprint(2, "tag mismatch\n");
			vtSetError("tag mismatch");
			goto Err;
		}
	}

	np = e.psize/VtScoreSize;
	memset(index, 0, sizeof(index));
	for(i=0; bn > 0; i++){
		if(i >= VtPointerDepth){
			vtSetError(EBadAddr);
			goto Err;
		}
		index[i] = bn % np;
		bn /= np;
	}

	if(i > e.depth){
		if(mode == OReadOnly){
			vtSetError(EBadAddr);
			goto Err;
		}
		if(!sourceGrowDepth(r, b, &e, i))
			goto Err;
	}

	index[e.depth] = r->offset % r->epb;

	for(i=e.depth; i>=early; i--){
		bb = blockWalk(b, index[i], m, r->fs, &e);
		if(bb == nil)
			goto Err;
		blockPut(b);
		b = bb;
	}
	b->pc = getcallerpc(&r);
	return b;
Err:
	blockPut(b);
	return nil;
}

Block*
sourceBlock(Source *r, ulong bn, int mode)
{
	Block *b;

	b = _sourceBlock(r, bn, mode, 0, 0);
	if(b)
		b->pc = getcallerpc(&r);
	return b;
}

void
sourceClose(Source *r)
{
	if(r == nil)
		return;
	vtLock(r->lk);
	r->ref--;
	if(r->ref){
		vtUnlock(r->lk);
		return;
	}
	assert(r->ref == 0);
	vtUnlock(r->lk);
	if(r->parent)
		sourceClose(r->parent);
	vtLockFree(r->lk);
	memset(r, ~0, sizeof(*r));
	vtMemFree(r);
}

/*
 * Retrieve the block containing the entry for r.
 * If a snapshot has happened, we might need
 * to get a new copy of the block.  We avoid this
 * in the common case by caching the score for
 * the block and the last epoch in which it was valid.
 *
 * We use r->mode to tell the difference between active
 * file system sources (OReadWrite) and sources for the
 * snapshot file system (OReadOnly).
 */
static Block*
sourceLoadBlock(Source *r, int mode)
{
	u32int addr;
	Block *b;

	switch(r->mode){
	default:
		assert(0);
	case OReadWrite:
		assert(r->mode == OReadWrite);
		/*
		 * This needn't be true -- we might bump the low epoch
		 * to reclaim some old blocks, but since this score is
		 * OReadWrite, the blocks must all still be open, so none
		 * are reclaimed.  Thus it's okay that the epoch is so low.
		 * Proceed.
		assert(r->epoch >= r->fs->elo);
		 */
		if(r->epoch == r->fs->ehi){
			b = cacheGlobal(r->fs->cache, r->score, BtDir, r->tag, OReadWrite);
			if(b == nil)
				return nil;
			assert(r->epoch == b->l.epoch);
			return b;
		}
		assert(r->parent != nil);
		if(!sourceLock(r->parent, OReadWrite))
			return nil;
		b = sourceBlock(r->parent, r->offset/r->epb, OReadWrite);
		sourceUnlock(r->parent);
		if(b == nil)
			return nil;
		assert(b->l.epoch == r->fs->ehi);
	//	fprint(2, "sourceLoadBlock %p %V => %V\n", r, r->score, b->score);
		memmove(r->score, b->score, VtScoreSize);
		r->scoreEpoch = b->l.epoch;
		r->tag = b->l.tag;
		r->epoch = r->fs->ehi;
		return b;

	case OReadOnly:
		addr = globalToLocal(r->score);
		if(addr == NilBlock)
			return cacheGlobal(r->fs->cache, r->score, BtDir, r->tag, mode);

		b = cacheLocalData(r->fs->cache, addr, BtDir, r->tag, mode, r->scoreEpoch);
		if(b)
			return b;

		/*
		 * If it failed because the epochs don't match, the block has been
		 * archived and reclaimed.  Rewalk from the parent and get the
		 * new pointer.  This can't happen in the OReadWrite case
		 * above because blocks in the current epoch don't get
		 * reclaimed.  The fact that we're OReadOnly means we're
		 * a snapshot.  (Or else the file system is read-only, but then
		 * the archiver isn't going around deleting blocks.)
		 */
		if(strcmp(vtGetError(), ELabelMismatch) == 0){
			if(!sourceLock(r->parent, OReadOnly))
				return nil;
			b = sourceBlock(r->parent, r->offset/r->epb, OReadOnly);
			sourceUnlock(r->parent);
			if(b){
				fprint(2, "sourceAlloc: lost %V found %V\n",
					r->score, b->score);
				memmove(r->score, b->score, VtScoreSize);
				r->scoreEpoch = b->l.epoch;
				return b;
			}
		}
		return nil;
	}
}

int
sourceLock(Source *r, int mode)
{
	Block *b;

	if(mode == -1)
		mode = r->mode;

	b = sourceLoadBlock(r, mode);
	if(b == nil)
		return 0;
	/*
	 * The fact that we are holding b serves as the
	 * lock entitling us to write to r->b.
	 */
	assert(r->b == nil);
	r->b = b;
	if(r->mode == OReadWrite)
		assert(r->epoch == r->b->l.epoch);
	return 1;
}

/*
 * Lock two (usually sibling) sources.  This needs special care
 * because the Entries for both sources might be in the same block.
 * We also try to lock blocks in left-to-right order within the tree.
 */
int
sourceLock2(Source *r, Source *rr, int mode)
{
	Block *b, *bb;

	if(rr == nil)
		return sourceLock(r, mode);

	if(mode == -1)
		mode = r->mode;

	if(r->parent==rr->parent && r->offset/r->epb == rr->offset/rr->epb){
		b = sourceLoadBlock(r, mode);
		if(b == nil)
			return 0;
		if(memcmp(r->score, rr->score, VtScoreSize) != 0){
			memmove(rr->score, b->score, VtScoreSize);
			rr->scoreEpoch = b->l.epoch;
			rr->tag = b->l.tag;
			rr->epoch = rr->fs->ehi;
		}
		blockDupLock(b);
		bb = b;
	}else if(r->parent==rr->parent || r->offset > rr->offset){
		bb = sourceLoadBlock(rr, mode);
		b = sourceLoadBlock(r, mode);
	}else{
		b = sourceLoadBlock(r, mode);
		bb = sourceLoadBlock(rr, mode);
	}
	if(b == nil || bb == nil){
		if(b)
			blockPut(b);
		if(bb)
			blockPut(bb);
		return 0;
	}

	/*
	 * The fact that we are holding b and bb serves
	 * as the lock entitling us to write to r->b and rr->b.
	 */
	r->b = b;
	rr->b = bb;
	return 1;
}

void
sourceUnlock(Source *r)
{
	Block *b;

	if(r->b == nil){
		fprint(2, "sourceUnlock: already unlocked\n");
		abort();
	}
	b = r->b;
	r->b = nil;
	blockPut(b);
}

static Block*
sourceLoad(Source *r, Entry *e)
{
	Block *b;

	assert(sourceIsLocked(r));
	b = r->b;
	if(!entryUnpack(e, b->data, r->offset % r->epb))
		return nil;
	if(e->gen != r->gen){
		vtSetError(ERemoved);
		return nil;
	}
	blockDupLock(b);
	return b;
}

static int
sizeToDepth(uvlong s, int psize, int dsize)
{
	int np;
	int d;

	/* determine pointer depth */
	np = psize/VtScoreSize;
	s = (s + dsize - 1)/dsize;
	for(d = 0; s > 1; d++)
		s = (s + np - 1)/np;
	return d;
}

static u32int
tagGen(void)
{
	u32int tag;

	for(;;){
		tag = lrand();
		if(tag >= UserTag)
			break;
	}
	return tag;
}