source.c

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

#include "stdinc.h"
#include "dat.h"
#include "fns.h"
#include "error.h"

static int	sizeToDepth(uvlong s, int psize, int dsize);
static u32int 	tagGen(void);
static Block 	*sourceLoad(Source *r, Entry *e);
static Block	*sourceLoadUnlocked(Source *r, Entry *e);
static int	sourceShrinkDepth(Source*, Block*, Entry*, int);
static int	sourceShrinkSize(Source*, Entry*, uvlong);
static int	sourceGrowDepth(Source*, Block*, Entry*, int);

#define sourceIsLocked(r)	((r)->b != nil)

static Source *
sourceAlloc(Fs *fs, Block *b, Source *p, u32int offset, int mode)
{
	Source *r;
	int epb;
	u32int epoch;
	Entry e;

	assert(p==nil || sourceIsLocked(p));

	if(p == nil){
		assert(offset == 0);
		epb = 1;
	}else
		epb = p->dsize / VtEntrySize;

	if(b->l.type != BtDir)
		goto Bad;

	/*
	 * a non-active entry is the only thing that
	 * can legitimately happen here. all the others
	 * get prints.
	 */
	if(!entryUnpack(&e, b->data, offset % epb)){
		fprint(2, "entryUnpack failed\n");
		goto Bad;
	}
	if(!(e.flags & VtEntryActive)){
		if(0)fprint(2, "not active\n");
		goto Bad;
	}
	if(e.psize < 256 || e.dsize < 256){
		fprint(2, "psize %ud dsize %ud\n", e.psize, e.dsize);
		goto Bad;
	}

	if(e.depth < sizeToDepth(e.size, e.psize, e.dsize)){
		fprint(2, "depth %ud size %llud psize %ud dsize %ud\n", e.depth, e.size, e.psize, e.dsize);
		goto Bad;
	}

	if((e.flags & VtEntryLocal) && e.tag == 0){
		fprint(2, "flags %#ux tag %#ux\n", e.flags, e.tag);
		goto Bad;
	}

	if(e.dsize > fs->blockSize || e.psize > fs->blockSize){
		fprint(2, "psize %ud dsize %ud blocksize %ud\n", e.psize, e.dsize, fs->blockSize);
		goto Bad;
	}

	epoch = b->l.epoch;
	if(mode == OReadWrite){
		if(e.snap != 0){
			vtSetError(ESnapRO);
			return nil;
		}
	}else if(e.snap != 0){
		if(e.snap < fs->elo){
			vtSetError(ESnapOld);
			return nil;
		}
		if(e.snap >= fs->ehi)
			goto Bad;
		epoch = e.snap;
	}

	r = vtMemAllocZ(sizeof(Source));
	r->fs = fs;
	r->mode = mode;
	r->dsize = e.dsize;
	r->gen = e.gen;
	r->dir = (e.flags & VtEntryDir) != 0;
	r->lk = vtLockAlloc();
	r->ref = 1;
	r->parent = p;
	if(p){
		vtLock(p->lk);
		assert(mode == OReadOnly || p->mode == OReadWrite);
		p->ref++;
		vtUnlock(p->lk);
	}
	r->epoch = epoch;
//fprint(2, "sourceAlloc have %V be.%d fse.%d %s\n", b->score, b->l.epoch, r->fs->ehi, mode==OReadWrite ? "rw" : "ro");
	memmove(r->score, b->score, VtScoreSize);
	r->scoreEpoch = b->l.epoch;
	r->offset = offset;
	r->epb = epb;
	r->tag = b->l.tag;

//fprint(2, "sourceAlloc: %p -> %V %d\n", r, r->score, r->offset);

	return r;
Bad:
	vtSetError(EBadEntry);
	return nil;

}

Source *
sourceRoot(Fs *fs, u32int addr, int mode)
{
	Source *r;
	Block *b;

	b = cacheLocalData(fs->cache, addr, BtDir, RootTag, mode, 0);
	if(b == nil)
		return nil;

	if(mode == OReadWrite && b->l.epoch != fs->ehi){
		fprint(2, "sourceRoot: fs->ehi = %ud, b->l = %L\n", fs->ehi, &b->l);
		blockPut(b);
		vtSetError(EBadRoot);
		return nil;
	}

	r = sourceAlloc(fs, b, nil, 0, mode);
	blockPut(b);
	return r;
}

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

	assert(sourceIsLocked(r));
	if(r->mode == OReadWrite)
		assert(r->epoch == r->b->l.epoch);
	if(!r->dir){
		vtSetError(ENotDir);
		return nil;
	}

	bn = offset/(r->dsize/VtEntrySize);

	b = sourceBlock(r, bn, mode);
	if(b == nil)
		return nil;
	r = sourceAlloc(r->fs, b, r, offset, mode);
	blockPut(b);
	return r;
}

Source *
sourceCreate(Source *r, int dsize, int dir, u32int offset)
{
	int i;
	Block *b;
	u32int bn, size;
	Entry e;
	int epb;
	int psize;
	Source *rr;

	assert(sourceIsLocked(r));

	if(!r->dir){
		vtSetError(ENotDir);
		return nil;
	}

	epb = r->dsize/VtEntrySize;
	psize = (dsize/VtScoreSize)*VtScoreSize;

	size = sourceGetDirSize(r);
	if(offset == 0){
		/*
		 * look at a random block to see if we can find an empty entry
		 */
		offset = lnrand(size+1);
		offset -= offset % epb;
	}

	/* try the given block and then try the last block */
	for(;;){
		bn = offset/epb;
		b = sourceBlock(r, bn, OReadWrite);
		if(b == nil)
			return nil;
		for(i=offset%r->epb; i<epb; i++){
			entryUnpack(&e, b->data, i);
			if((e.flags&VtEntryActive) == 0 && e.gen != ~0)
				goto Found;
		}
		blockPut(b);
		if(offset == size){
			fprint(2, "sourceCreate: cannot happen\n");
			vtSetError("sourceCreate: cannot happen");
			return nil;
		}
		offset = size;
	}

Found:
	/* found an entry - gen already set */
	e.psize = psize;
	e.dsize = dsize;
	assert(psize && dsize);
	e.flags = VtEntryActive;
	if(dir)
		e.flags |= VtEntryDir;
	e.depth = 0;
	e.size = 0;
	memmove(e.score, vtZeroScore, VtScoreSize);
	e.tag = 0;
	e.snap = 0;
	e.archive = 0;
	entryPack(&e, b->data, i);
	blockDirty(b);

	offset = bn*epb + i;
	if(offset+1 > size){
		if(!sourceSetDirSize(r, offset+1)){
			blockPut(b);
			return nil;
		}
	}

	rr = sourceAlloc(r->fs, b, r, offset, OReadWrite);
	blockPut(b);
	return rr;
}

static int
sourceKill(Source *r, int doremove)
{
	Entry e;
	Block *b;
	u32int addr;
	u32int tag;
	int type;

	assert(sourceIsLocked(r));
	b = sourceLoad(r, &e);
	if(b == nil)
		return 0;

	assert(b->l.epoch == r->fs->ehi);

	if(doremove==0 && e.size == 0){
		/* already truncated */
		blockPut(b);
		return 1;
	}

	/* remember info on link we are removing */
	addr = globalToLocal(e.score);
	type = entryType(&e);
	tag = e.tag;

	if(doremove){
		if(e.gen != ~0)
			e.gen++;
		e.dsize = 0;
		e.psize = 0;
		e.flags = 0;
	}else{
		e.flags &= ~VtEntryLocal;
	}
	e.depth = 0;
	e.size = 0;
	e.tag = 0;
	memmove(e.score, vtZeroScore, VtScoreSize);
	entryPack(&e, b->data, r->offset % r->epb);
	blockDirty(b);
	if(addr != NilBlock)
		blockRemoveLink(b, addr, type, tag, 1);
	blockPut(b);

	if(doremove){
		sourceUnlock(r);
		sourceClose(r);
	}

	return 1;
}

int
sourceRemove(Source *r)
{
	return sourceKill(r, 1);
}

int
sourceTruncate(Source *r)
{
	return sourceKill(r, 0);
}

uvlong
sourceGetSize(Source *r)
{
	Entry e;
	Block *b;

	assert(sourceIsLocked(r));
	b = sourceLoad(r, &e);
	if(b == nil)
		return 0;
	blockPut(b);

	return e.size;
}

static int
sourceShrinkSize(Source *r, Entry *e, uvlong size)
{
	int i, type, ppb;
	uvlong ptrsz;
	u32int addr;
	uchar score[VtScoreSize];
	Block *b;

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

	ptrsz = e->dsize;
	ppb = e->psize/VtScoreSize;
	for(i=0; i+1<e->depth; i++)
		ptrsz *= ppb;

	while(type&BtLevelMask){
		if(b->addr == NilBlock || b->l.epoch != r->fs->ehi){
			/* not worth copying the block just so we can zero some of it */
			blockPut(b);
			return 0;
		}

		/*
		 * invariant: each pointer in the tree rooted at b accounts for ptrsz bytes
		 */

		/* zero the pointers to unnecessary blocks */
		i = (size+ptrsz-1)/ptrsz;
		for(; i<ppb; i++){
			addr = globalToLocal(b->data+i*VtScoreSize);
			memmove(b->data+i*VtScoreSize, vtZeroScore, VtScoreSize);
			blockDirty(b);
			if(addr != NilBlock)
				blockRemoveLink(b, addr, type-1, e->tag, 1);
		}

		/* recurse (go around again) on the partially necessary block */
		i = size/ptrsz;
		size = size%ptrsz;
		if(size == 0){
			blockPut(b);
			return 1;
		}
		ptrsz /= ppb;
		type--;
		memmove(score, b->data+i*VtScoreSize, VtScoreSize);
		blockPut(b);
		b = cacheGlobal(r->fs->cache, score, type, e->tag, OReadWrite);
		if(b == nil)
			return 0;
	}

	if(b->addr == NilBlock || b->l.epoch != r->fs->ehi){
		blockPut(b);
		return 0;
	}

	/*
	 * No one ever truncates BtDir blocks.
	 */
	if(type == BtData && e->dsize > size){
		memset(b->data+size, 0, e->dsize-size);
		blockDirty(b);
	}
	blockPut(b);
	return 1;
}

int
sourceSetSize(Source *r, uvlong size)
{
	int depth;
	Entry e;
	Block *b;

	assert(sourceIsLocked(r));
	if(size == 0)
		return sourceTruncate(r);

	if(size > VtMaxFileSize || size > ((uvlong)MaxBlock)*r->dsize){
		vtSetError(ETooBig);
		return 0;
	}

	b = sourceLoad(r, &e);
	if(b == nil)
		return 0;

	/* quick out */
	if(e.size == size){
		blockPut(b);
		return 1;
	}

	depth = sizeToDepth(size, e.psize, e.dsize);

	if(depth < e.depth){
		if(!sourceShrinkDepth(r, b, &e, depth)){
			blockPut(b);
			return 0;
		}
	}else if(depth > e.depth){
		if(!sourceGrowDepth(r, b, &e, depth)){
			blockPut(b);
			return 0;
		}
	}

	if(size < e.size)
		sourceShrinkSize(r, &e, size);

	e.size = size;
	entryPack(&e, b->data, r->offset % r->epb);
	blockDirty(b);
	blockPut(b);

	return 1;
}

int
sourceSetDirSize(Source *r, ulong ds)
{
	uvlong size;
	int epb;

	assert(sourceIsLocked(r));
	epb = r->dsize/VtEntrySize;

	size = (uvlong)r->dsize*(ds/epb);
	size += VtEntrySize*(ds%epb);
	return sourceSetSize(r, size);
}

ulong
sourceGetDirSize(Source *r)
{
	ulong ds;
	uvlong size;
	int epb;

	assert(sourceIsLocked(r));
	epb = r->dsize/VtEntrySize;

	size = sourceGetSize(r);
	ds = epb*(size/r->dsize);
	ds += (size%r->dsize)/VtEntrySize;
	return ds;
}

int
sourceGetEntry(Source *r, Entry *e)
{
	Block *b;

	assert(sourceIsLocked(r));
	b = sourceLoad(r, e);
	if(b == nil)
		return 0;
	blockPut(b);

	return 1;
}

/*
 * Must be careful with this.  Doesn't record
 * dependencies, so don't introduce any!
 */
int
sourceSetEntry(Source *r, Entry *e)
{
	Block *b;
	Entry oe;

	assert(sourceIsLocked(r));
	b = sourceLoad(r, &oe);
	if(b == nil)
		return 0;
	entryPack(e, b->data, r->offset%r->epb);
	blockDirty(b);
	blockPut(b);

	return 1;
}

static Block *
blockWalk(Block *p, int index, int mode, Fs *fs, Entry *e)
{
	Block *b;
	Cache *c;
	u32int addr;
	int type;
	uchar oscore[VtScoreSize], score[VtScoreSize];
	Entry oe;

	c = fs->cache;

	if((p->l.type & BtLevelMask) == 0){
		assert(p->l.type == BtDir);