/*  * This file is part of the UCB release of Plan 9. It is subject to the license * terms in the LICENSE file found in the top-level directory of this * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No * part of the UCB release of Plan 9, including this file, may be copied, * modified, propagated, or distributed except according to the terms contained * in the LICENSE file. */ #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;	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 nused;		/* number of used blocks */	u32int epochLow;	/* low epoch when last updated 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 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*); /* * 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->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. */voidcacheFree(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 voidcacheDump(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 voidcacheCheck(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, "%s: cacheCheck: nheap %d refed %d nblocks %ld\n", argv0, 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, "%s: p=%d a=%ud %V ref=%d %L\n", argv0, b->part, b->addr, b->score, b->ref, &b->l);			refed++;		}	}if(refed > 0)fprint(2, "%s: cacheCheck: in used %d\n", argv0, 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, "%s: entire cache is busy, %d dirty "					"-- waking flush thread\n",					argv0, c->ndirty);			}		}		if(printed)			fprint(2, "%s: cache is okay again, %d dirty\n",				argv0, 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, "%s: dropping %d:%x:%V\n", argv0, 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("error reading 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, Waitlock, 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

Lines 1–500 of 2123. Load more