cache.c

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

	if(b->heap != BadHeap)
		fixHeap(b->heap, b);

	vtUnlock(c->lk);

	vtLock(b->lk);
	if(b->state != LumpFree)
		return b;
	
	n = vtRead(c->z, score, type, b->data, size);
	if(n < 0) {
		lumpDecRef(b, 1);
		return nil;
	}
	if(!vtSha1Check(score, b->data, n)) {
		vtSetError("vtSha1Check failed");
		lumpDecRef(b, 1);
		return nil;
	}
	vtZeroExtend(type, b->data, n, size);
	b->asize = size;
	lumpSetState(b, LumpVenti);

	return b;
}

static char *
lumpState(int state)
{
	switch(state) {
	default:
		return "Unknown!!";
	case LumpFree:
		return "Free";
	case LumpActive:
		return "Active";
	case LumpSnap:
		return "Snap";
	case LumpZombie:
		return "Zombie";
	case LumpVenti:
		return "Venti";
	}
}

static void
lumpSetState(Lump *u, int state)
{
//	if(u->state != LumpFree)
//		fprint(2, "%V: %s -> %s\n", u->score, lumpState(u->state), lumpState(state));
	u->state = state;
}
	
int
lumpGetScore(Lump *u, int offset, uchar score[VtScoreSize])
{
	uchar *sp;
	VtRoot root;
	VtEntry dir;

	vtLock(u->lk);

	switch(u->type) {
	default:
		vtSetError("bad type");
		goto Err;
	case VtPointerType0:
	case VtPointerType1:
	case VtPointerType2:
	case VtPointerType3:
	case VtPointerType4:
	case VtPointerType5:
	case VtPointerType6:
		if((offset+1)*VtScoreSize > u->asize)
			sp = nil;
		else
			sp = u->data + offset*VtScoreSize;
		break;
	case VtRootType:
		if(u->asize < VtRootSize) {
			vtSetError("runt root block");
			goto Err;
		}
		if(!vtRootUnpack(&root, u->data))
			goto Err;
		sp = root.score;
		break;
	case VtDirType:
		if((offset+1)*VtEntrySize > u->asize) {
			vtSetError(ENoDir);
			goto Err;
		}
		if(!vtEntryUnpack(&dir, u->data, offset))
			goto Err;
		if(!dir.flags & VtEntryActive) {
			vtSetError(ENoDir);
			goto Err;
		}
		sp = dir.score;
		break;
	}

	if(sp == nil)
		memmove(score, vtZeroScore, VtScoreSize);
	else
		memmove(score, sp, VtScoreSize);

	vtUnlock(u->lk);
	return !scoreIsLocal(score);
Err:
	vtUnlock(u->lk);
	return 0;
}

Lump *
lumpWalk(Lump *u, int offset, int type, int size, int readOnly, int lock)
{
	Lump *v, *vv;
	Cache *c;
	uchar score[VtScoreSize], *sp;
	VtRoot root;
	VtEntry dir;
	int split, isdir;

	c = u->c;
	vtLock(u->lk);

Again:
	v = nil;
	vv = nil;

	isdir = u->dir;
	switch(u->type) {
	default:
		vtSetError("bad type");
		goto Err;
	case VtPointerType0:
	case VtPointerType1:
	case VtPointerType2:
	case VtPointerType3:
	case VtPointerType4:
	case VtPointerType5:
	case VtPointerType6:
		if((offset+1)*VtScoreSize > u->asize)
			sp = nil;
		else
			sp = u->data + offset*VtScoreSize;
		break;
	case VtRootType:
		if(u->asize < VtRootSize) {
			vtSetError("runt root block");
			goto Err;
		}
		if(!vtRootUnpack(&root, u->data))
			goto Err;
		sp = root.score;
		break;
	case VtDirType:
		if((offset+1)*VtEntrySize > u->asize) {
			vtSetError(ENoDir);
			goto Err;
		}
		if(!vtEntryUnpack(&dir, u->data, offset))
			goto Err;
		if(!(dir.flags & VtEntryActive)) {
			vtSetError(ENoDir);
			goto Err;
		}
		isdir = (dir.flags & VtEntryDir) != 0;
//		sp = dir.score;
		sp = u->data + offset*VtEntrySize + 20;
		break;
	}

	if(sp == nil)
		memmove(score, vtZeroScore, VtScoreSize);
	else
		memmove(score, sp, VtScoreSize);
	
	vtUnlock(u->lk);


if(0)fprint(2, "lumpWalk: %V:%s %d:%d-> %V:%d\n", u->score, lumpState(u->state), u->type, offset, score, type);
	v = cacheGetLump(c, score, type, size);
	if(v == nil)
		return nil;

	split = 1;
	if(readOnly)
		split = 0;

	switch(v->state) {
	default:
		assert(0);
	case LumpFree:
fprint(2, "block is free %V!\n", v->score);
		vtSetError("phase error");
		goto Err2;
	case LumpActive:	
		if(v->gen < u->gen) {
print("LumpActive gen\n");
			lumpSetState(v, LumpSnap);
			v->gen = u->gen;
		} else
			split = 0;
		break;
	case LumpSnap:
	case LumpVenti:
		break;
	}
	
	/* easy case */
	if(!split) {
		if(!lock)
			vtUnlock(v->lk);
		return v;
	}

	if(sp == nil) {
		vtSetError("bad offset");
		goto Err2;
	}

	vv = cacheAllocLump(c, v->type, size, isdir);
	/* vv is locked */
	vv->gen = u->gen;
	memmove(vv->data, v->data, v->asize);
if(0)fprint(2, "split %V into %V\n", v->score, vv->score);

	lumpDecRef(v, 1);
	v = nil;

	vtLock(u->lk);
	if(u->state != LumpActive) {
		vtSetError("bad parent state: can not happen");
		goto Err;
	}

	/* check that nothing changed underfoot */
	if(memcmp(sp, score, VtScoreSize) != 0) {
		lumpDecRef(vv, 1);
fprint(2, "lumpWalk: parent changed under foot\n");
		goto Again;
	}

	/* XXX - hold Active blocks up - will go eventually */
	lumpIncRef(vv);

	/* change the parent */
	memmove(sp, vv->score, VtScoreSize);
	
	vtUnlock(u->lk);
	
	if(!lock)
		vtUnlock(vv->lk);
	return vv;
Err:
	vtUnlock(u->lk);
	lumpDecRef(v, 0);
	lumpDecRef(vv, 1);
	return nil;
Err2:
	lumpDecRef(v, 1);
	return nil;
	
}

void
lumpFreeEntry(Lump *u, int entry)
{
	uchar score[VtScoreSize];
	int type;
	ulong gen;
	VtEntry dir;
	Cache *c;

	c = u->c;
	vtLock(u->lk);
	if(u->state == LumpVenti)
		goto Exit;

	switch(u->type) {
	default:
		fprint(2, "freeing bad lump type: %d\n", u->type);
		return;
	case VtPointerType0:
		if((entry+1)*VtScoreSize > u->asize)
			goto Exit;
		memmove(score, u->data + entry*VtScoreSize, VtScoreSize);
		memmove(u->data + entry*VtScoreSize, vtZeroScore, VtScoreSize);
		type = u->dir?VtDirType:VtDataType;
		break;
	case VtPointerType1:
	case VtPointerType2:
	case VtPointerType3:
	case VtPointerType4:
	case VtPointerType5:
	case VtPointerType6:
		if((entry+1)*VtScoreSize > u->asize)
			goto Exit;
		memmove(score, u->data + entry*VtScoreSize, VtScoreSize);
		memmove(u->data + entry*VtScoreSize, vtZeroScore, VtScoreSize);
		type = u->type-1;
		break;
	case VtDirType:
		if((entry+1)*VtEntrySize > u->asize)
			goto Exit;
		if(!vtEntryUnpack(&dir, u->data, entry))
			goto Exit;
		if(!dir.flags & VtEntryActive)
			goto Exit;
		gen = dir.gen;
		if(gen != ~0)
			gen++;
		if(dir.depth == 0)
			type = (dir.flags&VtEntryDir)?VtDirType:VtDataType;
		else
			type = VtPointerType0 + dir.depth - 1;
		memmove(score, dir.score, VtScoreSize);
		memset(&dir, 0, sizeof(dir));
		dir.gen = gen;
		vtEntryPack(&dir, u->data, entry);
		break;
	case VtDataType:
		type = VtErrType;
		break;
	}
	vtUnlock(u->lk);
	if(type == VtErrType || !scoreIsLocal(score))
		return;

	u = cacheGetLump(c, score, type, c->size);
	if(u == nil)
		return;
	lumpDecRef(u, 1);
	/* XXX remove extra reference */
	lumpDecRef(u, 0);
	return;
Exit:
	vtUnlock(u->lk);
	return;

}

void
lumpCleanup(Lump *u)
{
	int i, n;

	switch(u->type) {
	default:
		return;
	case VtPointerType0:
	case VtPointerType1:
	case VtPointerType2:
	case VtPointerType3:
	case VtPointerType4:
	case VtPointerType5:
	case VtPointerType6:
		n = u->asize/VtScoreSize;
		break;	
	case VtDirType:
		n = u->asize/VtEntrySize;
		break;
	}

	for(i=0; i<n; i++)
		lumpFreeEntry(u, i);
}


void
lumpDecRef(Lump *b, int unlock)
{
	int i;
	Cache *c;

	if(b == nil)
		return;

	if(unlock)
		vtUnlock(b->lk);

	c = b->c;
	vtLock(c->lk);
	if(--b->ref > 0) {
		vtUnlock(c->lk);
		return;
	}
	assert(b->ref == 0);

	switch(b->state) {
	default:
		fprint(2, "bad state: %s\n", lumpState(b->state));
		assert(0);
	case LumpActive:
		/* hack - but will do for now */
		b->ref++;
		vtUnlock(c->lk);
		lumpCleanup(b);
		vtLock(c->lk);
		b->ref--;
		lumpSetState(b, LumpFree);
		break;
	case LumpZombie:
		lumpSetState(b, LumpFree);
		break;
	case LumpFree:
	case LumpVenti:
		break;
	}

	/*
	 * reinsert in the free heap
	 */
	if(b->heap == BadHeap) {
		i = upHeap(c->nheap++, b);
		c->heap[i] = b;
		b->heap = i;
	}

	vtUnlock(c->lk);
}

Lump *
lumpIncRef(Lump *b)
{
	Cache *c;

	c = b->c;

	vtLock(c->lk);
	assert(b->ref > 0);
	b->ref++;
	vtUnlock(c->lk);
	return b;
}