cache.c

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

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

#include "9.h"	/* for cacheFlush */

typedef struct FreeList FreeList;
typedef struct BAddr BAddr;

enum {
	BadHeap = ~0,
};

/*
 * Store data to the memory cache in c->size blocks
 * with the block zero extended to fill it out.  When writing to
 * Venti, the block will be zero truncated.  The walker will also check
 * that the block fits within psize or dsize as the case may be.
 */

struct Cache
{
	VtLock	*lk;
	VtLock	*dirtylk;
	int 	ref;
	int	mode;

	Disk 	*disk;
	int	size;			/* block size */
	int	ndmap;		/* size of per-block dirty pointer map used in blockWrite */
	VtSession *z;
	u32int	now;			/* ticks for usage timestamps */
	Block	**heads;		/* hash table for finding address */
	int	nheap;			/* number of available victims */
	Block	**heap;			/* heap for locating victims */
	long	nblocks;		/* number of blocks allocated */
	Block	*blocks;		/* array of block descriptors */
	u8int	*mem;			/* memory for all block data & blists */

	BList	*blfree;
	VtRendez *blrend;

	int 	ndirty;			/* number of dirty blocks in the cache */
	int 	maxdirty;		/* max number of dirty blocks */
	u32int	vers;

	long hashSize;

	FreeList *fl;

	VtRendez *die;			/* daemon threads should die when != nil */

	VtRendez *flush;
	VtRendez *flushwait;
	VtRendez *heapwait;
	BAddr *baddr;
	int bw, br, be;
	int nflush;

	Periodic *sync;

	/* unlink daemon */
	BList *uhead;
	BList *utail;
	VtRendez *unlink;

	/* block counts */
	int nused;
	int ndisk;
};

struct BList {
	int part;
	u32int addr;
	uchar type;
	u32int tag;
	u32int epoch;
	u32int vers;

	int recurse;	/* for block unlink */

	/* for roll back */
	int index;			/* -1 indicates not valid */
	union {
		uchar score[VtScoreSize];
		uchar entry[VtEntrySize];
	} old;
	BList *next;
};

struct BAddr {
	int part;
	u32int addr;
	u32int vers;
};

struct FreeList {
	VtLock *lk;
	u32int last;	/* last block allocated */
	u32int end;	/* end of data partition */
	u32int nfree;	/* number of free blocks */
	u32int nused;	/* number of used blocks */
	u32int epochLow;	/* low epoch when last updated nfree and nused */
};

static FreeList *flAlloc(u32int end);
static void flFree(FreeList *fl);

static Block *cacheBumpBlock(Cache *c);
static void heapDel(Block*);
static void heapIns(Block*);
static void cacheCheck(Cache*);
static void unlinkThread(void *a);
static void flushThread(void *a);
static void flushBody(Cache *c);
static void unlinkBody(Cache *c);
static int cacheFlushBlock(Cache *c);
static void cacheSync(void*);
static BList *blistAlloc(Block*);
static void blistFree(Cache*, BList*);
static void doRemoveLink(Cache*, BList*);
static void doRemoveLinkList(Cache*, BList*);

/*
 * Mapping from local block type to Venti type
 */
int vtType[BtMax] = {
	VtDataType,		/* BtData | 0  */
	VtPointerType0,		/* BtData | 1  */
	VtPointerType1,		/* BtData | 2  */
	VtPointerType2,		/* BtData | 3  */
	VtPointerType3,		/* BtData | 4  */
	VtPointerType4,		/* BtData | 5  */
	VtPointerType5,		/* BtData | 6  */
	VtPointerType6,		/* BtData | 7  */
	VtDirType,		/* BtDir | 0  */
	VtPointerType0,		/* BtDir | 1  */
	VtPointerType1,		/* BtDir | 2  */
	VtPointerType2,		/* BtDir | 3  */
	VtPointerType3,		/* BtDir | 4  */
	VtPointerType4,		/* BtDir | 5  */
	VtPointerType5,		/* BtDir | 6  */
	VtPointerType6,		/* BtDir | 7  */
};

/*
 * Allocate the memory cache.
 */
Cache *
cacheAlloc(Disk *disk, VtSession *z, ulong nblocks, int mode)
{
	int i;
	Cache *c;
	Block *b;
	BList *bl;
	u8int *p;
	int nbl;

	c = vtMemAllocZ(sizeof(Cache));

	/* reasonable number of BList elements */
	nbl = nblocks * 4;

	c->lk = vtLockAlloc();
	c->dirtylk = vtLockAlloc();	/* allowed to dirty blocks */
	c->ref = 1;
	c->disk = disk;
	c->z = z;
	c->size = diskBlockSize(disk);
bwatchSetBlockSize(c->size);
	/* round c->size up to be a nice multiple */
	c->size = (c->size + 127) & ~127;
	c->ndmap = (c->size/20 + 7) / 8;
	c->nblocks = nblocks;
	c->hashSize = nblocks;
	c->heads = vtMemAllocZ(c->hashSize*sizeof(Block*));
	c->heap = vtMemAllocZ(nblocks*sizeof(Block*));
	c->blocks = vtMemAllocZ(nblocks*sizeof(Block));
	c->mem = vtMemAllocZ(nblocks * (c->size + c->ndmap) + nbl * sizeof(BList));
	c->baddr = vtMemAllocZ(nblocks * sizeof(BAddr));
	c->mode = mode;
	c->vers++;
	p = c->mem;
	for(i = 0; i < nblocks; i++){
		b = &c->blocks[i];
		b->lk = vtLockAlloc();
		b->c = c;
		b->data = p;
		b->heap = i;
		b->ioready = vtRendezAlloc(b->lk);
		c->heap[i] = b;
		p += c->size;
	}
	c->nheap = nblocks;
	for(i = 0; i < nbl; i++){
		bl = (BList*)p;
		bl->next = c->blfree;
		c->blfree = bl;
		p += sizeof(BList);
	}
	/* separate loop to keep blocks and blists reasonably aligned */
	for(i = 0; i < nblocks; i++){
		b = &c->blocks[i];
		b->dmap = p;
		p += c->ndmap;
	}

	c->blrend = vtRendezAlloc(c->lk);

	c->maxdirty = nblocks*(DirtyPercentage*0.01);

	c->fl = flAlloc(diskSize(disk, PartData));

	c->unlink = vtRendezAlloc(c->lk);
	c->flush = vtRendezAlloc(c->lk);
	c->flushwait = vtRendezAlloc(c->lk);
	c->heapwait = vtRendezAlloc(c->lk);
	c->sync = periodicAlloc(cacheSync, c, 30*1000);

	if(mode == OReadWrite){
		c->ref += 2;
		vtThread(unlinkThread, c);
		vtThread(flushThread, c);
	}
	cacheCheck(c);

	return c;
}

/*
 * Free the whole memory cache, flushing all dirty blocks to the disk.
 */
void
cacheFree(Cache *c)
{
	int i;

	/* kill off daemon threads */
	vtLock(c->lk);
	c->die = vtRendezAlloc(c->lk);
	periodicKill(c->sync);
	vtWakeup(c->flush);
	vtWakeup(c->unlink);
	while(c->ref > 1)
		vtSleep(c->die);

	/* flush everything out */
	do {
		unlinkBody(c);
		vtUnlock(c->lk);
		while(cacheFlushBlock(c))
			;
		diskFlush(c->disk);
		vtLock(c->lk);
	} while(c->uhead || c->ndirty);
	vtUnlock(c->lk);

	cacheCheck(c);

	for(i = 0; i < c->nblocks; i++){
		assert(c->blocks[i].ref == 0);
		vtRendezFree(c->blocks[i].ioready);
		vtLockFree(c->blocks[i].lk);
	}
	flFree(c->fl);
	vtMemFree(c->baddr);
	vtMemFree(c->heads);
	vtMemFree(c->blocks);
	vtMemFree(c->mem);
	vtLockFree(c->lk);
	diskFree(c->disk);
	vtRendezFree(c->blrend);
	/* don't close vtSession */
	vtMemFree(c);
}

static void
cacheDump(Cache *c)
{
	int i;
	Block *b;

	for(i = 0; i < c->nblocks; i++){
		b = &c->blocks[i];
		fprint(2, "%d. p=%d a=%ud %V t=%d ref=%d state=%s io=%s pc=%#p\n",
			i, b->part, b->addr, b->score, b->l.type, b->ref,
			bsStr(b->l.state), bioStr(b->iostate), b->pc);
	}
}

static void
cacheCheck(Cache *c)
{
	u32int size, now;
	int i, k, refed;
	static uchar zero[VtScoreSize];
	Block *b;

	size = c->size;
	now = c->now;

	for(i = 0; i < c->nheap; i++){
		if(c->heap[i]->heap != i)
			vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
		if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
			vtFatal("bad heap ordering");
		k = (i << 1) + 1;
		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
			vtFatal("bad heap ordering");
		k++;
		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
			vtFatal("bad heap ordering");
	}

	refed = 0;
	for(i = 0; i < c->nblocks; i++){
		b = &c->blocks[i];
		if(b->data != &c->mem[i * size])
			vtFatal("mis-blocked at %d", i);
		if(b->ref && b->heap == BadHeap){
			refed++;
		}
	}
if(c->nheap + refed != c->nblocks){
fprint(2, "cacheCheck: nheap %d refed %d nblocks %ld\n", c->nheap, refed, c->nblocks);
cacheDump(c);
}
	assert(c->nheap + refed == c->nblocks);
	refed = 0;
	for(i = 0; i < c->nblocks; i++){
		b = &c->blocks[i];
		if(b->ref){
if(1)fprint(2, "p=%d a=%ud %V ref=%d %L\n", b->part, b->addr, b->score, b->ref, &b->l);
			refed++;
		}
	}
if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
}


/*
 * locate the block with the oldest second to last use.
 * remove it from the heap, and fix up the heap.
 */
/* called with c->lk held */
static Block *
cacheBumpBlock(Cache *c)
{
	int printed;
	Block *b;

	/*
	 * locate the block with the oldest second to last use.
	 * remove it from the heap, and fix up the heap.
	 */
	printed = 0;
	if(c->nheap == 0){
		while(c->nheap == 0){
			vtWakeup(c->flush);
			vtSleep(c->heapwait);
			if(c->nheap == 0){
				printed = 1;
				fprint(2, "entire cache is busy, %d dirty -- waking flush thread\n", c->ndirty);
			}
		}
		if(printed)
			fprint(2, "cache is okay again, %d dirty\n", c->ndirty);
	}

	b = c->heap[0];
	heapDel(b);

	assert(b->heap == BadHeap);
	assert(b->ref == 0);
	assert(b->iostate != BioDirty && b->iostate != BioReading && b->iostate != BioWriting);
	assert(b->prior == nil);
	assert(b->uhead == nil);

	/*
	 * unchain the block from hash chain
	 */
	if(b->prev){
		*(b->prev) = b->next;
		if(b->next)
			b->next->prev = b->prev;
		b->prev = nil;
	}


if(0)fprint(2, "droping %d:%x:%V\n", b->part, b->addr, b->score);
	/* set block to a reasonable state */
	b->ref = 1;
	b->part = PartError;
	memset(&b->l, 0, sizeof(b->l));
	b->iostate = BioEmpty;

	return b;
}

/*
 * look for a particular version of the block in the memory cache.
 */
static Block *
_cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers,
	int waitlock, int *lockfailure)
{
	Block *b;
	ulong h;

	h = addr % c->hashSize;

	if(lockfailure)
		*lockfailure = 0;

	/*
	 * look for the block in the cache
	 */
	vtLock(c->lk);
	for(b = c->heads[h]; b != nil; b = b->next){
		if(b->part == part && b->addr == addr)
			break;
	}
	if(b == nil || b->vers != vers){
		vtUnlock(c->lk);
		return nil;
	}
	if(!waitlock && !vtCanLock(b->lk)){
		*lockfailure = 1;
		vtUnlock(c->lk);
		return nil;
	}
	heapDel(b);
	b->ref++;
	vtUnlock(c->lk);

	bwatchLock(b);
	if(waitlock)
		vtLock(b->lk);
	b->nlock = 1;

	for(;;){
		switch(b->iostate){
		default:
			abort();
		case BioEmpty:
		case BioLabel:
		case BioClean:
		case BioDirty:
			if(b->vers != vers){
				blockPut(b);
				return nil;
			}
			return b;
		case BioReading:
		case BioWriting:
			vtSleep(b->ioready);
			break;
		case BioVentiError:
			blockPut(b);
			vtSetError("venti i/o error block 0x%.8ux", addr);
			return nil;
		case BioReadError:
			blockPut(b);
			vtSetError("i/o error block 0x%.8ux", addr);
			return nil;
		}
	}
	/* NOT REACHED */
}
static Block*
cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers)
{
	return _cacheLocalLookup(c, part, addr, vers, 1, 0);
}


/*
 * fetch a local (on-disk) block from the memory cache.
 * if it's not there, load it, bumping some other block.
 */
Block *
_cacheLocal(Cache *c, int part, u32int addr, int mode, u32int epoch)
{
	Block *b;
	ulong h;

	assert(part != PartVenti);

	h = addr % c->hashSize;

	/*
	 * look for the block in the cache
	 */
	vtLock(c->lk);
	for(b = c->heads[h]; b != nil; b = b->next){
		if(b->part != part || b->addr != addr)
			continue;
		if(epoch && b->l.epoch != epoch){
fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
			vtUnlock(c->lk);
			vtSetError(ELabelMismatch);
			return nil;
		}
		heapDel(b);
		b->ref++;
		break;
	}

	if(b == nil){
		b = cacheBumpBlock(c);

		b->part = part;
		b->addr = addr;
		localToGlobal(addr, b->score);

		/* chain onto correct hash */
		b->next = c->heads[h];
		c->heads[h] = b;
		if(b->next != nil)
			b->next->prev = &b->next;
		b->prev = &c->heads[h];
	}

	vtUnlock(c->lk);

	/*
	 * BUG: what if the epoch changes right here?
	 * In the worst case, we could end up in some weird
	 * lock loop, because the block we want no longer exists,
	 * and instead we're trying to lock a block we have no
	 * business grabbing.
	 *
	 * For now, I'm not going to worry about it.
	 */

if(0)fprint(2, "cacheLocal: %d: %d %x\n", getpid(), b->part, b->addr);
	bwatchLock(b);
	vtLock(b->lk);
	b->nlock = 1;

	if(part == PartData && b->iostate == BioEmpty){
		if(!readLabel(c, &b->l, addr)){
			blockPut(b);
			return nil;
		}
		blockSetIOState(b, BioLabel);
	}
	if(epoch && b->l.epoch != epoch){
		blockPut(b);
fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
		vtSetError(ELabelMismatch);
		return nil;
	}

	b->pc = getcallerpc(&c);
	for(;;){
		switch(b->iostate){
		default:
			abort();
		case BioEmpty:
		case BioLabel:
			if(mode == OOverWrite){
				blockSetIOState(b, BioClean);
				return b;
			}
			diskRead(c->disk, b);
			vtSleep(b->ioready);
			break;
		case BioClean:
		case BioDirty:
			return b;
		case BioReading:
		case BioWriting:
			vtSleep(b->ioready);
			break;
		case BioReadError:
			blockSetIOState(b, BioEmpty);
			blockPut(b);
			vtSetError("i/o error block 0x%.8ux", addr);
			return nil;
		}
	}
	/* NOT REACHED */
}

Block *
cacheLocal(Cache *c, int part, u32int addr, int mode)
{
	return _cacheLocal(c, part, addr, mode, 0);
}

/*
 * fetch a local (on-disk) block from the memory cache.
 * if it's not there, load it, bumping some other block.
 * check tag and type.
 */
Block *
cacheLocalData(Cache *c, u32int addr, int type, u32int tag, int mode, u32int epoch)
{
	Block *b;

	b = _cacheLocal(c, PartData, addr, mode, epoch);
	if(b == nil)
		return nil;
	if(b->l.type != type || b->l.tag != tag){
		fprint(2, "cacheLocalData: addr=%d type got %d exp %d: tag got %ux exp %ux\n",
			addr, b->l.type, type, b->l.tag, tag);
		vtSetError(ELabelMismatch);
		blockPut(b);
		return nil;
	}
	b->pc = getcallerpc(&c);
	return b;
}

/*
 * fetch a global (Venti) block from the memory cache.
 * if it's not there, load it, bumping some other block.
 * check tag and type if it's really a local block in disguise.
 */
Block *
cacheGlobal(Cache *c, uchar score[VtScoreSize], int type, u32int tag, int mode)
{
	int n;
	Block *b;
	ulong h;
	u32int addr;

	addr = globalToLocal(score);
	if(addr != NilBlock){
		b = cacheLocalData(c, addr, type, tag, mode, 0);
		if(b)
			b->pc = getcallerpc(&c);
		return b;
	}

	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->hashSize;

	/*
	 * look for the block in the cache
	 */
	vtLock(c->lk);
	for(b = c->heads[h]; b != nil; b = b->next){
		if(b->part != PartVenti || memcmp(b->score, score, VtScoreSize) != 0 || b->l.type != type)
			continue;
		heapDel(b);
		b->ref++;
		break;
	}

	if(b == nil){
if(0)fprint(2, "cacheGlobal %V %d\n", score, type);

		b = cacheBumpBlock(c);

		b->part = PartVenti;
		b->addr = NilBlock;
		b->l.type = type;
		memmove(b->score, score, VtScoreSize);

		/* chain onto correct hash */
		b->next = c->heads[h];
		c->heads[h] = b;
		if(b->next != nil)
			b->next->prev = &b->next;
		b->prev = &c->heads[h];
	}
	vtUnlock(c->lk);

	bwatchLock(b);
	vtLock(b->lk);
	b->nlock = 1;
	b->pc = getcallerpc(&c);

	switch(b->iostate){
	default:
		abort();
	case BioEmpty:
		n = vtRead(c->z, score, vtType[type], b->data, c->size);
		if(n < 0 || !vtSha1Check(score, b->data, n)){
			blockSetIOState(b, BioVentiError);
			blockPut(b);
			vtSetError("venti i/o error block %V: %r", score);
			return nil;
		}
		vtZeroExtend(vtType[type], b->data, n, c->size);
		blockSetIOState(b, BioClean);
		return b;
	case BioClean:
		return b;
	case BioVentiError:
		blockPut(b);
		vtSetError("venti i/o error block %V", score);
		return nil;
	case BioReadError:
		blockPut(b);
		vtSetError("i/o error block %V", b->score);
		return nil;