/* * Memory-only VtBlock cache. * * The cached Venti blocks are in the hash chains. * The cached local blocks are only in the blocks array. * The free blocks are in the heap, which is supposed to * be indexed by second-to-last use but actually * appears to be last use. */ #include <u.h>#include <libc.h>#include <venti.h> int vtcachenread;int vtcachencopy;int vtcachenwrite;int vttracelevel; enum {	BioLocal = 1,	BioVenti,	BioReading,	BioWriting,	BioEmpty,	BioVentiError};enum {	BadHeap = ~0};struct VtCache{	QLock	lk;	VtConn	*z;	u32int	blocksize;	u32int	now;		/* ticks for usage time stamps */	VtBlock	**hash;	/* hash table for finding addresses */	int		nhash;	VtBlock	**heap;	/* heap for finding victims */	int		nheap;	VtBlock	*block;	/* all allocated blocks */	int		nblock;	uchar	*mem;	/* memory for all blocks and data */	int		(*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);}; static void cachecheck(VtCache*); VtCache*vtcachealloc(VtConn *z, int blocksize, ulong nblock){	uchar *p;	VtCache *c;	int i;	VtBlock *b; 	c = vtmallocz(sizeof(VtCache)); 	c->z = z;	c->blocksize = (blocksize + 127) & ~127;	c->nblock = nblock;	c->nhash = nblock;	c->hash = vtmallocz(nblock*sizeof(VtBlock*));	c->heap = vtmallocz(nblock*sizeof(VtBlock*));	c->block = vtmallocz(nblock*sizeof(VtBlock));	c->mem = vtmallocz(nblock*c->blocksize);	c->write = vtwrite; 	p = c->mem;	for(i=0; i<nblock; i++){		b = &c->block[i];		b->addr = NilBlock;		b->c = c;		b->data = p;		b->heap = i;		c->heap[i] = b;		p += c->blocksize;	}	c->nheap = nblock;	cachecheck(c);	return c;} /* * BUG This is here so that vbackup can override it and do some * pipelining of writes.  Arguably vtwrite or vtwritepacket or the * cache itself should be providing this functionality. */voidvtcachesetwrite(VtCache *c, int (*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int)){	if(write == nil)		write = vtwrite;	c->write = write;} voidvtcachefree(VtCache *c){	int i; 	qlock(&c->lk); 	cachecheck(c);	for(i=0; i<c->nblock; i++)		assert(c->block[i].ref == 0); 	vtfree(c->hash);	vtfree(c->heap);	vtfree(c->block);	vtfree(c->mem);	vtfree(c);} static voidvtcachedump(VtCache *c){	int i;	VtBlock *b; 	for(i=0; i<c->nblock; i++){		b = &c->block[i];		print("cache block %d: type %d score %V iostate %d addr %d ref %d nlock %d\n",			i, b->type, b->score, b->iostate, b->addr, b->ref, b->nlock);	}} static voidcachecheck(VtCache *c){	u32int size, now;	int i, k, refed;	VtBlock *b; 	size = c->blocksize;	now = c->now; 	for(i = 0; i < c->nheap; i++){		if(c->heap[i]->heap != i)			sysfatal("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)			sysfatal("bad heap ordering");		k = (i << 1) + 1;		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)			sysfatal("bad heap ordering");		k++;		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)			sysfatal("bad heap ordering");	} 	refed = 0;	for(i = 0; i < c->nblock; i++){		b = &c->block[i];		if(b->data != &c->mem[i * size])			sysfatal("mis-blocked at %d", i);		if(b->ref && b->heap == BadHeap)			refed++;		else if(b->addr != NilBlock)			refed++;	}	assert(c->nheap + refed == c->nblock);	refed = 0;	for(i = 0; i < c->nblock; i++){		b = &c->block[i];		if(b->ref){			refed++;		}	}} static intupheap(int i, VtBlock *b){	VtBlock *bb;	u32int now;	int p;	VtCache *c;		c = b->c;	now = c->now;	for(; i != 0; i = p){		p = (i - 1) >> 1;		bb = c->heap[p];		if(b->used - now >= bb->used - now)			break;		c->heap[i] = bb;		bb->heap = i;	}	c->heap[i] = b;	b->heap = i; 	return i;} static intdownheap(int i, VtBlock *b){	VtBlock *bb;	u32int now;	int k;	VtCache *c;		c = b->c;	now = c->now;	for(; ; i = k){		k = (i << 1) + 1;		if(k >= c->nheap)			break;		if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)			k++;		bb = c->heap[k];		if(b->used - now <= bb->used - now)			break;		c->heap[i] = bb;		bb->heap = i;	}	c->heap[i] = b;	b->heap = i;	return i;} /* * Delete a block from the heap. * Called with c->lk held. */static voidheapdel(VtBlock *b){	int i, si;	VtCache *c; 	c = b->c; 	si = b->heap;	if(si == BadHeap)		return;	b->heap = BadHeap;	c->nheap--;	if(si == c->nheap)		return;	b = c->heap[c->nheap];	i = upheap(si, b);	if(i == si)		downheap(i, b);} /* * Insert a block into the heap. * Called with c->lk held. */static voidheapins(VtBlock *b){	assert(b->heap == BadHeap);	upheap(b->c->nheap++, b);} /* * locate the vtBlock with the oldest second to last use. * remove it from the heap, and fix up the heap. *//* called with c->lk held */static VtBlock*vtcachebumpblock(VtCache *c){	VtBlock *b; 	/*	 * locate the vtBlock with the oldest second to last use.	 * remove it from the heap, and fix up the heap.	 */	if(c->nheap == 0){		vtcachedump(c);		fprint(2, "vtcachebumpblock: no free blocks in vtCache");		abort();	}	b = c->heap[0];	heapdel(b); 	assert(b->heap == BadHeap);	assert(b->ref == 0); 	/*	 * unchain the vtBlock from hash chain if any	 */	if(b->prev){		*(b->prev) = b->next;		if(b->next)			b->next->prev = b->prev;		b->prev = nil;	}  	if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);	/* set vtBlock to a reasonable state */	b->ref = 1;	b->iostate = BioEmpty;	return b;} /* * fetch a local block from the memory cache. * if it's not there, load it, bumping some other Block. * if we're out of free blocks, we're screwed. */VtBlock*vtcachelocal(VtCache *c, u32int addr, int type){	VtBlock *b; 	if(addr == 0)		sysfatal("vtcachelocal: asked for nonexistent block 0");	if(addr > c->nblock)		sysfatal("vtcachelocal: asked for block #%ud; only %d blocks",			addr, c->nblock); 	b = &c->block[addr-1];	if(b->addr == NilBlock || b->iostate != BioLocal)		sysfatal("vtcachelocal: block is not local"); 	if(b->type != type)		sysfatal("vtcachelocal: block has wrong type %d != %d", b->type, type); 	qlock(&c->lk);	b->ref++;	qunlock(&c->lk); 	qlock(&b->lk);	b->nlock = 1;	b->pc = getcallerpc(&c);	return b;} VtBlock*vtcacheallocblock(VtCache *c, int type){	VtBlock *b; 	qlock(&c->lk);	b = vtcachebumpblock(c);	b->iostate = BioLocal;	b->type = type;	b->addr = (b - c->block)+1;	vtzeroextend(type, b->data, 0, c->blocksize);	vtlocaltoglobal(b->addr, b->score);	qunlock(&c->lk); 	qlock(&b->lk);	b->nlock = 1;	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. */VtBlock*vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type){	VtBlock *b;	ulong h;	int n;	u32int addr; 	if(vttracelevel)		fprint(2, "vtcacheglobal %V %d from %p\n", score, type, getcallerpc(&c));	addr = vtglobaltolocal(score);	if(addr != NilBlock){		if(vttracelevel)			fprint(2, "vtcacheglobal %V %d => local\n", score, type);		b = vtcachelocal(c, addr, type);		if(b)			b->pc = getcallerpc(&c);		return b;	} 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->nhash; 	/*	 * look for the block in the cache	 */	qlock(&c->lk);	for(b = c->hash[h]; b != nil; b = b->next){		if(b->addr != NilBlock || memcmp(b->score, score, VtScoreSize) != 0 || b->type != type)			continue;		heapdel(b);		b->ref++;		qunlock(&c->lk);		if(vttracelevel)			fprint(2, "vtcacheglobal %V %d => found in cache %p; locking\n", score, type, b);		qlock(&b->lk);		b->nlock = 1;		if(b->iostate == BioVentiError){			if(chattyventi)				fprint(2, "cached read error for %V\n", score);			if(vttracelevel)				fprint(2, "vtcacheglobal %V %d => cache read error\n", score, type);			vtblockput(b);			werrstr("venti i/o error");			return nil;		}		if(vttracelevel)			fprint(2, "vtcacheglobal %V %d => found in cache; returning\n", score, type);		b->pc = getcallerpc(&c);		return b;	} 	/*	 * not found	 */	b = vtcachebumpblock(c);	b->addr = NilBlock;	b->type = type;	memmove(b->score, score, VtScoreSize);	/* chain onto correct hash */	b->next = c->hash[h];	c->hash[h] = b;	if(b->next != nil)		b->next->prev = &b->next;	b->prev = &c->hash[h]; 	/*	 * Lock b before unlocking c, so that others wait while we read.	 * 	 * You might think there is a race between this qlock(b) before qunlock(c)	 * and the qlock(c) while holding a qlock(b) in vtblockwrite.  However,	 * the block here can never be the block in a vtblockwrite, so we're safe.	 * We're certainly living on the edge.	 */	if(vttracelevel)		fprint(2, "vtcacheglobal %V %d => bumped; locking %p\n", score, type, b);	qlock(&b->lk);	b->nlock = 1;	qunlock(&c->lk); 	vtcachenread++;	n = vtread(c->z, score, type, b->data, c->blocksize);	if(n < 0){		if(chattyventi)			fprint(2, "read %V: %r\n", score);		if(vttracelevel)			fprint(2, "vtcacheglobal %V %d => bumped; read error\n", score, type);		b->iostate = BioVentiError;		vtblockput(b);		return nil;	}	vtzeroextend(type, b->data, n, c->blocksize);	b->iostate = BioVenti;	b->nlock = 1;	if(vttracelevel)		fprint(2, "vtcacheglobal %V %d => loaded into cache; returning\n", score, type);	b->pc = getcallerpc(&b);	return b;} /* * The thread that has locked b may refer to it by * multiple names.  Nlock counts the number of * references the locking thread holds.  It will call * vtblockput once per reference. */voidvtblockduplock(VtBlock *b){	assert(b->nlock > 0);	b->nlock++;} /* * we're done with the block. * unlock it.  can't use it after calling this. */voidvtblockput(VtBlock* b){	VtCache *c; 	if(b == nil)		return; if(0)fprint(2, "vtblockput: %d: %x %d %d\n", getpid(), b->addr, c->nheap, b->iostate);	if(vttracelevel)		fprint(2, "vtblockput %p from %p\n", b, getcallerpc(&b)); 	if(--b->nlock > 0)		return; 	/*	 * b->nlock should probably stay at zero while	 * the vtBlock is unlocked, but diskThread and vtSleep	 * conspire to assume that they can just qlock(&b->lk); vtblockput(b),	 * so we have to keep b->nlock set to 1 even 	 * when the vtBlock is unlocked.	 */	assert(b->nlock == 0);	b->nlock = 1; 	qunlock(&b->lk);	c = b->c;

Lines 1–500 of 599. Load more