src/cmd/venti/srv/dcache.c - plan9 - Git at Google

 /*
  * Disk cache.
  *
  * Caches raw disk blocks.  Getdblock() gets a block, putdblock puts it back.
  * Getdblock has a mode parameter that determines i/o and access to a block:
  * if mode is OREAD or ORDWR, it is read from disk if not already in memory.
  * If mode is ORDWR or OWRITE, it is locked for exclusive use before being returned.
  * It is *not* marked dirty -- once changes have been made, they should be noted
  * by using dirtydblock() before putdblock().
  *
  * There is a global cache lock as well as a lock on each block.
  * Within a thread, the cache lock can be acquired while holding a block lock,
  * but not vice versa; and a block cannot be locked if you already hold the lock
  * on another block.
  *
  * The flush proc writes out dirty blocks in batches, one batch per dirty tag.
  * For example, the DirtyArena blocks are all written to disk before any of the
  * DirtyArenaCib blocks.
  *
  * This code used to be in charge of flushing the dirty index blocks out to
  * disk, but updating the index turned out to benefit from extra care.
  * Now cached index blocks are never marked dirty.  The index.c code takes
  * care of updating them behind our back, and uses _getdblock to update any
  * cached copies of the blocks as it changes them on disk.
  */

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

 typedef struct DCache	DCache;

 enum
 {
 	HashLog		= 9,
 	HashSize	= 1<<HashLog,
 	HashMask	= HashSize - 1,
 };

 struct DCache
 {
 	QLock		lock;
 	RWLock		dirtylock;		/* must be held to inspect or set b->dirty */
 	Rendez		full;
 	Round		round;
 	DBlock		*free;			/* list of available lumps */
 	u32int		now;			/* ticks for usage timestamps */
 	int		size;			/* max. size of any block; allocated to each block */
 	DBlock		**heads;		/* hash table for finding address */
 	int		nheap;			/* number of available victims */
 	DBlock		**heap;			/* heap for locating victims */
 	int		nblocks;		/* number of blocks allocated */
 	DBlock		*blocks;		/* array of block descriptors */
 	DBlock		**write;		/* array of block pointers to be written */
 	u8int		*mem;			/* memory for all block descriptors */
 	int		ndirty;			/* number of dirty blocks */
 	int		maxdirty;		/* max. number of dirty blocks */
 };

 typedef struct Ra Ra;
 struct Ra
 {
 	Part *part;
 	u64int addr;
 };

 static DCache	dcache;

 static int	downheap(int i, DBlock *b);
 static int	upheap(int i, DBlock *b);
 static DBlock	*bumpdblock(void);
 static void	delheap(DBlock *db);
 static void	fixheap(int i, DBlock *b);
 static void	flushproc(void*);
 static void	writeproc(void*);

 void
 initdcache(u32int mem)
 {
 	DBlock *b, *last;
 	u32int nblocks, blocksize;
 	int i;
 	u8int *p;

 	if(mem < maxblocksize * 2)
 		sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
 	if(maxblocksize == 0)
 		sysfatal("no max. block size given for disk cache");
 	blocksize = maxblocksize;
 	nblocks = mem / blocksize;
 	dcache.full.l = &dcache.lock;
 	dcache.nblocks = nblocks;
 	dcache.maxdirty = (nblocks * 2) / 3;
 	trace(TraceProc, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
 			nblocks, blocksize, dcache.maxdirty);
 	dcache.size = blocksize;
 	dcache.heads = MKNZ(DBlock*, HashSize);
 	dcache.heap = MKNZ(DBlock*, nblocks);
 	dcache.blocks = MKNZ(DBlock, nblocks);
 	dcache.write = MKNZ(DBlock*, nblocks);
 	dcache.mem = MKNZ(u8int, (nblocks+1+128) * blocksize);

 	last = nil;
 	p = (u8int*)(((uintptr)dcache.mem+blocksize-1)&~(uintptr)(blocksize-1));
 	for(i = 0; i < nblocks; i++){
 		b = &dcache.blocks[i];
 		b->data = &p[i * blocksize];
 		b->heap = TWID32;
 		b->writedonechan = chancreate(sizeof(void*), 1);
 		b->next = last;
 		last = b;
 	}

 	dcache.free = last;
 	dcache.nheap = 0;
 	setstat(StatDcacheSize, nblocks);
 	initround(&dcache.round, "dcache", 120*1000);

 	vtproc(flushproc, nil);
 	vtproc(delaykickroundproc, &dcache.round);
 }

 static u32int
 pbhash(u64int addr)
 {
 	u32int h;

 #define hashit(c)	((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
 	h = (addr >> 32) ^ addr;
 	return hashit(h);
 }

 DBlock*
 getdblock(Part *part, u64int addr, int mode)
 {
 	DBlock *b;

 	b = _getdblock(part, addr, mode, 1);
 	if(mode == OREAD || mode == ORDWR)
 		addstat(StatDcacheRead, 1);
 	if(mode == OWRITE || mode == ORDWR)
 		addstat(StatDcacheWrite, 1);
 	return b;
 }

 DBlock*
 _getdblock(Part *part, u64int addr, int mode, int load)
 {
 	DBlock *b;
 	u32int h, size, ms;

 	ms = 0;
 	trace(TraceBlock, "getdblock enter %s 0x%llux", part->name, addr);
 	size = part->blocksize;
 	if(size > dcache.size){
 		seterr(EAdmin, "block size %d too big for cache with size %d", size, dcache.size);
 		if(load)
 			addstat(StatDcacheLookup, 1);
 		return nil;
 	}
 	h = pbhash(addr);

 	/*
 	 * look for the block in the cache
 	 */
 	qlock(&dcache.lock);
 again:
 	for(b = dcache.heads[h]; b != nil; b = b->next){
 		if(b->part == part && b->addr == addr){
 			if(load)
 				addstat2(StatDcacheHit, 1, StatDcacheLookup, 1);
 			goto found;
 		}
 	}

 	/*
 	 * missed: locate the block with the oldest second to last use.
 	 * remove it from the heap, and fix up the heap.
 	 */
 	if(!load){
 		qunlock(&dcache.lock);
 		return nil;
 	}

 	/*
 	 * Only start timer here, on cache miss - calling msec() on plain cache hits
 	 * makes cache hits system-call bound.
 	 */
 	ms = msec();
 	addstat2(StatDcacheLookup, 1, StatDcacheMiss, 1);

 	b = bumpdblock();
 	if(b == nil){
 		trace(TraceBlock, "all disk cache blocks in use");
 		addstat(StatDcacheStall, 1);
 		rsleep(&dcache.full);
 		addstat(StatDcacheStall, -1);
 		goto again;
 	}

 	assert(!b->dirty);

 	/*
 	 * the new block has no last use, so assume it happens sometime in the middle
 ZZZ this is not reasonable
 	 */
 	b->used = (b->used2 + dcache.now) / 2;

 	/*
 	 * rechain the block on the correct hash chain
 	 */
 	b->next = dcache.heads[h];
 	dcache.heads[h] = b;
 	if(b->next != nil)
 		b->next->prev = b;
 	b->prev = nil;

 	b->addr = addr;
 	b->part = part;
 	b->size = 0;

 found:
 	b->ref++;
 	b->used2 = b->used;
 	b->used = dcache.now++;
 	if(b->heap != TWID32)
 		fixheap(b->heap, b);

 	if((mode == ORDWR || mode == OWRITE) && part->writechan == nil){
 		trace(TraceBlock, "getdblock allocwriteproc %s", part->name);
 		part->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
 		vtproc(writeproc, part);
 	}
 	qunlock(&dcache.lock);

 	trace(TraceBlock, "getdblock lock");
 	addstat(StatDblockStall, 1);
 	if(mode == OREAD)
 		rlock(&b->lock);
 	else
 		wlock(&b->lock);
 	addstat(StatDblockStall, -1);
 	trace(TraceBlock, "getdblock locked");

 	if(b->size != size){
 		if(mode == OREAD){
 			addstat(StatDblockStall, 1);
 			runlock(&b->lock);
 			wlock(&b->lock);
 			addstat(StatDblockStall, -1);
 		}
 		if(b->size < size){
 			if(mode == OWRITE)
 				memset(&b->data[b->size], 0, size - b->size);
 			else{
 				trace(TraceBlock, "getdblock readpart %s 0x%llux", part->name, addr);
 				diskaccess(0);
 				if(readpart(part, addr + b->size, &b->data[b->size], size - b->size) < 0){
 					b->mode = ORDWR;	/* so putdblock wunlocks */
 					putdblock(b);
 					return nil;
 				}
 				trace(TraceBlock, "getdblock readpartdone");
 				addstat(StatApartRead, 1);
 				addstat(StatApartReadBytes, size-b->size);
 			}
 		}
 		b->size = size;
 		if(mode == OREAD){
 			addstat(StatDblockStall, 1);
 			wunlock(&b->lock);
 			rlock(&b->lock);
 			addstat(StatDblockStall, -1);
 		}
 	}

 	b->mode = mode;
 	trace(TraceBlock, "getdblock exit");
 	if(ms)
 		addstat(StatDcacheLookupTime, msec() - ms);
 	return b;
 }

 void
 putdblock(DBlock *b)
 {
 	if(b == nil)
 		return;

 	trace(TraceBlock, "putdblock %s 0x%llux", b->part->name, b->addr);

 	if(b->mode == OREAD)
 		runlock(&b->lock);
 	else
 		wunlock(&b->lock);

 	qlock(&dcache.lock);
 	if(--b->ref == 0 && !b->dirty){
 		if(b->heap == TWID32)
 			upheap(dcache.nheap++, b);
 		rwakeupall(&dcache.full);
 	}
 	qunlock(&dcache.lock);
 }

 void
 dirtydblock(DBlock *b, int dirty)
 {
 	int odirty;

 	trace(TraceBlock, "dirtydblock enter %s 0x%llux %d from 0x%lux",
 		b->part->name, b->addr, dirty, getcallerpc(&b));
 	assert(b->ref != 0);
 	assert(b->mode==ORDWR || b->mode==OWRITE);

 	odirty = b->dirty;
 	if(b->dirty)
 		assert(b->dirty == dirty);
 	else
 		b->dirty = dirty;

 	qlock(&dcache.lock);
 	if(!odirty){
 		dcache.ndirty++;
 		setstat(StatDcacheDirty, dcache.ndirty);
 		if(dcache.ndirty >= dcache.maxdirty)
 			kickround(&dcache.round, 0);
 		else
 			delaykickround(&dcache.round);
 	}
 	qunlock(&dcache.lock);
 }

 static void
 unchain(DBlock *b)
 {
 	ulong h;

 	/*
 	 * unchain the block
 	 */
 	if(b->prev == nil){
 		h = pbhash(b->addr);
 		if(dcache.heads[h] != b)
 			sysfatal("bad hash chains in disk cache");
 		dcache.heads[h] = b->next;
 	}else
 		b->prev->next = b->next;
 	if(b->next != nil)
 		b->next->prev = b->prev;
 }

 /*
  * remove some block from use and update the free list and counters
  */
 static DBlock*
 bumpdblock(void)
 {
 	DBlock *b;

 	trace(TraceBlock, "bumpdblock enter");
 	b = dcache.free;
 	if(b != nil){
 		dcache.free = b->next;
 		return b;
 	}

 	if(dcache.ndirty >= dcache.maxdirty)
 		kickdcache();

 	/*
 	 * remove blocks until we find one that is unused
 	 * referenced blocks are left in the heap even though
 	 * they can't be scavenged; this is simple a speed optimization
 	 */
 	for(;;){
 		if(dcache.nheap == 0){
 			kickdcache();
 			trace(TraceBlock, "bumpdblock gotnothing");
 			return nil;
 		}
 		b = dcache.heap[0];
 		delheap(b);
 		if(!b->ref && !b->dirty)
 			break;
 	}

 	trace(TraceBlock, "bumpdblock bumping %s 0x%llux", b->part->name, b->addr);

 	unchain(b);
 	return b;
 }

 void
 emptydcache(void)
 {
 	DBlock *b;

 	qlock(&dcache.lock);
 	while(dcache.nheap > 0){
 		b = dcache.heap[0];
 		delheap(b);
 		if(!b->ref && !b->dirty){
 			unchain(b);
 			b->next = dcache.free;
 			dcache.free = b;
 		}
 	}
 	qunlock(&dcache.lock);
 }

 /*
  * delete an arbitrary block from the heap
  */
 static void
 delheap(DBlock *db)
 {
 	if(db->heap == TWID32)
 		return;
 	fixheap(db->heap, dcache.heap[--dcache.nheap]);
 	db->heap = TWID32;
 }

 /*
  * push an element up or down to it's correct new location
  */
 static void
 fixheap(int i, DBlock *b)
 {
 	if(upheap(i, b) == i)
 		downheap(i, b);
 }

 static int
 upheap(int i, DBlock *b)
 {
 	DBlock *bb;
 	u32int now;
 	int p;

 	now = dcache.now;
 	for(; i != 0; i = p){
 		p = (i - 1) >> 1;
 		bb = dcache.heap[p];
 		if(b->used2 - now >= bb->used2 - now)
 			break;
 		dcache.heap[i] = bb;
 		bb->heap = i;
 	}

 	dcache.heap[i] = b;
 	b->heap = i;
 	return i;
 }

 static int
 downheap(int i, DBlock *b)
 {
 	DBlock *bb;
 	u32int now;
 	int k;

 	now = dcache.now;
 	for(; ; i = k){
 		k = (i << 1) + 1;
 		if(k >= dcache.nheap)
 			break;
 		if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
 			k++;
 		bb = dcache.heap[k];
 		if(b->used2 - now <= bb->used2 - now)
 			break;
 		dcache.heap[i] = bb;
 		bb->heap = i;
 	}

 	dcache.heap[i] = b;
 	b->heap = i;
 	return i;
 }

 static void
 findblock(DBlock *bb)
 {
 	DBlock *b, *last;
 	int h;

 	last = nil;
 	h = pbhash(bb->addr);
 	for(b = dcache.heads[h]; b != nil; b = b->next){
 		if(last != b->prev)
 			sysfatal("bad prev link");
 		if(b == bb)
 			return;
 		last = b;
 	}
 	sysfatal("block missing from hash table");
 }

 void
 checkdcache(void)
 {
 	DBlock *b;
 	u32int size, now;
 	int i, k, refed, nfree;

 	qlock(&dcache.lock);
 	size = dcache.size;
 	now = dcache.now;
 	for(i = 0; i < dcache.nheap; i++){
 		if(dcache.heap[i]->heap != i)
 			sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
 		if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
 			sysfatal("dc: bad heap ordering");
 		k = (i << 1) + 1;
 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
 			sysfatal("dc: bad heap ordering");
 		k++;
 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
 			sysfatal("dc: bad heap ordering");
 	}

 	refed = 0;
 	for(i = 0; i < dcache.nblocks; i++){
 		b = &dcache.blocks[i];
 		if(b->data != &dcache.mem[i * size])
 			sysfatal("dc: mis-blocked at %d", i);
 		if(b->ref && b->heap == TWID32)
 			refed++;
 		if(b->addr)
 			findblock(b);
 		if(b->heap != TWID32
 		&& dcache.heap[b->heap] != b)
 			sysfatal("dc: spurious heap value");
 	}

 	nfree = 0;
 	for(b = dcache.free; b != nil; b = b->next){
 		if(b->addr != 0 || b->heap != TWID32)
 			sysfatal("dc: bad free list");
 		nfree++;
 	}

 	if(dcache.nheap + nfree + refed != dcache.nblocks)
 		sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
 	qunlock(&dcache.lock);
 }

 void
 flushdcache(void)
 {
 	trace(TraceProc, "flushdcache enter");
 	kickround(&dcache.round, 1);
 	trace(TraceProc, "flushdcache exit");
 }

 void
 kickdcache(void)
 {
 	kickround(&dcache.round, 0);
 }

 static int
 parallelwrites(DBlock **b, DBlock **eb, int dirty)
 {
 	DBlock **p, **q;
 	Part *part;

 	for(p=b; p<eb && (*p)->dirty == dirty; p++){
 		assert(b<=p && p<eb);
 		sendp((*p)->part->writechan, *p);
 	}
 	q = p;
 	for(p=b; p<q; p++){
 		assert(b<=p && p<eb);
 		recvp((*p)->writedonechan);
 	}

 	/*
 	 * Flush the partitions that have been written to.
 	 */
 	part = nil;
 	for(p=b; p<q; p++){
 		if(part != (*p)->part){
 			part = (*p)->part;
 			flushpart(part);	/* what if it fails? */
 		}
 	}

 	return p-b;
 }

 /*
  * Sort first by dirty flag, then by partition, then by address in partition.
  */
 static int
 writeblockcmp(const void *va, const void *vb)
 {
 	DBlock *a, *b;

 	a = *(DBlock**)va;
 	b = *(DBlock**)vb;

 	if(a->dirty != b->dirty)
 		return a->dirty - b->dirty;
 	if(a->part != b->part){
 		if(a->part < b->part)
 			return -1;
 		if(a->part > b->part)
 			return 1;
 	}
 	if(a->addr < b->addr)
 		return -1;
 	return 1;
 }

 static void
 flushproc(void *v)
 {
 	int i, j, n;
 	ulong t0;
 	DBlock *b, **write;

 	USED(v);
 	threadsetname("flushproc");
 	for(;;){
 		waitforkick(&dcache.round);

 		trace(TraceWork, "start");
 		t0 = nsec()/1000;
 		trace(TraceProc, "build t=%lud", (ulong)(nsec()/1000)-t0);

 		write = dcache.write;
 		n = 0;
 		for(i=0; i<dcache.nblocks; i++){
 			b = &dcache.blocks[i];
 			if(b->dirty)
 				write[n++] = b;
 		}

 		qsort(write, n, sizeof(write[0]), writeblockcmp);

 		/* Write each stage of blocks out. */
 		trace(TraceProc, "writeblocks t=%lud", (ulong)(nsec()/1000)-t0);
 		i = 0;
 		for(j=1; j<DirtyMax; j++){
 			trace(TraceProc, "writeblocks.%d t=%lud",
 				j, (ulong)(nsec()/1000)-t0);
 			i += parallelwrites(write+i, write+n, j);
 		}
 		if(i != n){
 			fprint(2, "in flushproc i=%d n=%d\n", i, n);
 			for(i=0; i<n; i++)
 				fprint(2, "\tblock %d: dirty=%d\n",
 					i, write[i]->dirty);
 			abort();
 		}

 		/*
 		 * b->dirty is protected by b->lock while ndirty is protected
 		 * by dcache.lock, so the --ndirty below is the delayed one
 		 * from clearing b->dirty in the write proc.  It may happen
 		 * that some other proc has come along and redirtied b since
 		 * the write.  That's okay, it just means that ndirty may be
 		 * one too high until we catch up and do the decrement.
 		 */
 		trace(TraceProc, "undirty.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
 		qlock(&dcache.lock);
 		for(i=0; i<n; i++){
 			b = write[i];
 			--dcache.ndirty;
 			if(b->ref == 0 && b->heap == TWID32){
 				upheap(dcache.nheap++, b);
 				rwakeupall(&dcache.full);
 			}
 		}
 		setstat(StatDcacheDirty, dcache.ndirty);
 		qunlock(&dcache.lock);
 		addstat(StatDcacheFlush, 1);
 		trace(TraceWork, "finish");
 	}
 }

 static void
 writeproc(void *v)
 {
 	DBlock *b;
 	Part *p;

 	p = v;

 	threadsetname("writeproc:%s", p->name);
 	for(;;){
 		b = recvp(p->writechan);
 		trace(TraceWork, "start");
 		assert(b->part == p);
 		trace(TraceProc, "wlock %s 0x%llux", p->name, b->addr);
 		wlock(&b->lock);
 		trace(TraceProc, "writepart %s 0x%llux", p->name, b->addr);
 		diskaccess(0);
 		if(writepart(p, b->addr, b->data, b->size) < 0)
 			fprint(2, "%s: writeproc: part %s addr 0x%llux: write error: %r\n",
 				argv0, p->name, b->addr);
 		addstat(StatApartWrite, 1);
 		addstat(StatApartWriteBytes, b->size);
 		b->dirty = 0;
 		wunlock(&b->lock);
 		trace(TraceProc, "finish %s 0x%llux", p->name, b->addr);
 		trace(TraceWork, "finish");
 		sendp(b->writedonechan, b);
 	}
 }
	/*
	* Disk cache.
	*
	* Caches raw disk blocks. Getdblock() gets a block, putdblock puts it back.
	* Getdblock has a mode parameter that determines i/o and access to a block:
	* if mode is OREAD or ORDWR, it is read from disk if not already in memory.
	* If mode is ORDWR or OWRITE, it is locked for exclusive use before being returned.
	* It is not marked dirty -- once changes have been made, they should be noted
	* by using dirtydblock() before putdblock().
	*
	* There is a global cache lock as well as a lock on each block.
	* Within a thread, the cache lock can be acquired while holding a block lock,
	* but not vice versa; and a block cannot be locked if you already hold the lock
	* on another block.
	*
	* The flush proc writes out dirty blocks in batches, one batch per dirty tag.
	* For example, the DirtyArena blocks are all written to disk before any of the
	* DirtyArenaCib blocks.
	*
	* This code used to be in charge of flushing the dirty index blocks out to
	* disk, but updating the index turned out to benefit from extra care.
	* Now cached index blocks are never marked dirty. The index.c code takes
	* care of updating them behind our back, and uses _getdblock to update any
	* cached copies of the blocks as it changes them on disk.
	*/

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

	typedef struct DCache DCache;

	enum
	{
	HashLog = 9,
	HashSize = 1<<HashLog,
	HashMask = HashSize - 1,
	};

	struct DCache
	{
	QLock lock;
	RWLock dirtylock; /* must be held to inspect or set b->dirty */
	Rendez full;
	Round round;
	DBlock free; / list of available lumps */
	u32int now; /* ticks for usage timestamps */
	int size; /* max. size of any block; allocated to each block */
	DBlock *heads; / hash table for finding address */
	int nheap; /* number of available victims */
	DBlock *heap; / heap for locating victims */
	int nblocks; /* number of blocks allocated */
	DBlock blocks; / array of block descriptors */
	DBlock *write; / array of block pointers to be written */
	u8int mem; / memory for all block descriptors */
	int ndirty; /* number of dirty blocks */
	int maxdirty; /* max. number of dirty blocks */
	};

	typedef struct Ra Ra;
	struct Ra
	{
	Part *part;
	u64int addr;
	};

	static DCache dcache;

	static int downheap(int i, DBlock *b);
	static int upheap(int i, DBlock *b);
	static DBlock *bumpdblock(void);
	static void delheap(DBlock *db);
	static void fixheap(int i, DBlock *b);
	static void flushproc(void*);
	static void writeproc(void*);

	void
	initdcache(u32int mem)
	{
	DBlock b, last;
	u32int nblocks, blocksize;
	int i;
	u8int *p;

	if(mem < maxblocksize * 2)
	sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
	if(maxblocksize == 0)
	sysfatal("no max. block size given for disk cache");
	blocksize = maxblocksize;
	nblocks = mem / blocksize;
	dcache.full.l = &dcache.lock;
	dcache.nblocks = nblocks;
	dcache.maxdirty = (nblocks * 2) / 3;
	trace(TraceProc, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
	nblocks, blocksize, dcache.maxdirty);
	dcache.size = blocksize;
	dcache.heads = MKNZ(DBlock*, HashSize);
	dcache.heap = MKNZ(DBlock*, nblocks);
	dcache.blocks = MKNZ(DBlock, nblocks);
	dcache.write = MKNZ(DBlock*, nblocks);
	dcache.mem = MKNZ(u8int, (nblocks+1+128) * blocksize);

	last = nil;
	p = (u8int*)(((uintptr)dcache.mem+blocksize-1)&~(uintptr)(blocksize-1));
	for(i = 0; i < nblocks; i++){
	b = &dcache.blocks[i];
	b->data = &p[i * blocksize];
	b->heap = TWID32;
	b->writedonechan = chancreate(sizeof(void*), 1);
	b->next = last;
	last = b;
	}

	dcache.free = last;
	dcache.nheap = 0;
	setstat(StatDcacheSize, nblocks);
	initround(&dcache.round, "dcache", 120*1000);

	vtproc(flushproc, nil);
	vtproc(delaykickroundproc, &dcache.round);
	}

	static u32int
	pbhash(u64int addr)
	{
	u32int h;

	#define hashit(c) ((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
	h = (addr >> 32) ^ addr;
	return hashit(h);
	}

	DBlock*
	getdblock(Part *part, u64int addr, int mode)
	{
	DBlock *b;

	b = _getdblock(part, addr, mode, 1);
	if(mode == OREAD \|\| mode == ORDWR)
	addstat(StatDcacheRead, 1);
	if(mode == OWRITE \|\| mode == ORDWR)
	addstat(StatDcacheWrite, 1);
	return b;
	}

	DBlock*
	_getdblock(Part *part, u64int addr, int mode, int load)
	{
	DBlock *b;
	u32int h, size, ms;

	ms = 0;
	trace(TraceBlock, "getdblock enter %s 0x%llux", part->name, addr);
	size = part->blocksize;
	if(size > dcache.size){
	seterr(EAdmin, "block size %d too big for cache with size %d", size, dcache.size);
	if(load)
	addstat(StatDcacheLookup, 1);
	return nil;
	}
	h = pbhash(addr);

	/*
	* look for the block in the cache
	*/
	qlock(&dcache.lock);
	again:
	for(b = dcache.heads[h]; b != nil; b = b->next){
	if(b->part == part && b->addr == addr){
	if(load)
	addstat2(StatDcacheHit, 1, StatDcacheLookup, 1);
	goto found;
	}
	}

	/*
	* missed: locate the block with the oldest second to last use.
	* remove it from the heap, and fix up the heap.
	*/
	if(!load){
	qunlock(&dcache.lock);
	return nil;
	}

	/*
	* Only start timer here, on cache miss - calling msec() on plain cache hits
	* makes cache hits system-call bound.
	*/
	ms = msec();
	addstat2(StatDcacheLookup, 1, StatDcacheMiss, 1);

	b = bumpdblock();
	if(b == nil){
	trace(TraceBlock, "all disk cache blocks in use");
	addstat(StatDcacheStall, 1);
	rsleep(&dcache.full);
	addstat(StatDcacheStall, -1);
	goto again;
	}

	assert(!b->dirty);

	/*
	* the new block has no last use, so assume it happens sometime in the middle
	ZZZ this is not reasonable
	*/
	b->used = (b->used2 + dcache.now) / 2;

	/*
	* rechain the block on the correct hash chain
	*/
	b->next = dcache.heads[h];
	dcache.heads[h] = b;
	if(b->next != nil)
	b->next->prev = b;
	b->prev = nil;

	b->addr = addr;
	b->part = part;
	b->size = 0;

	found:
	b->ref++;
	b->used2 = b->used;
	b->used = dcache.now++;
	if(b->heap != TWID32)
	fixheap(b->heap, b);

	if((mode == ORDWR \|\| mode == OWRITE) && part->writechan == nil){
	trace(TraceBlock, "getdblock allocwriteproc %s", part->name);
	part->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
	vtproc(writeproc, part);
	}
	qunlock(&dcache.lock);

	trace(TraceBlock, "getdblock lock");
	addstat(StatDblockStall, 1);
	if(mode == OREAD)
	rlock(&b->lock);
	else
	wlock(&b->lock);
	addstat(StatDblockStall, -1);
	trace(TraceBlock, "getdblock locked");

	if(b->size != size){
	if(mode == OREAD){
	addstat(StatDblockStall, 1);
	runlock(&b->lock);
	wlock(&b->lock);
	addstat(StatDblockStall, -1);
	}
	if(b->size < size){
	if(mode == OWRITE)
	memset(&b->data[b->size], 0, size - b->size);
	else{
	trace(TraceBlock, "getdblock readpart %s 0x%llux", part->name, addr);
	diskaccess(0);
	if(readpart(part, addr + b->size, &b->data[b->size], size - b->size) < 0){
	b->mode = ORDWR; /* so putdblock wunlocks */
	putdblock(b);
	return nil;
	}
	trace(TraceBlock, "getdblock readpartdone");
	addstat(StatApartRead, 1);
	addstat(StatApartReadBytes, size-b->size);
	}
	}
	b->size = size;
	if(mode == OREAD){
	addstat(StatDblockStall, 1);
	wunlock(&b->lock);
	rlock(&b->lock);
	addstat(StatDblockStall, -1);
	}
	}

	b->mode = mode;
	trace(TraceBlock, "getdblock exit");
	if(ms)
	addstat(StatDcacheLookupTime, msec() - ms);
	return b;
	}

	void
	putdblock(DBlock *b)
	{
	if(b == nil)
	return;

	trace(TraceBlock, "putdblock %s 0x%llux", b->part->name, b->addr);

	if(b->mode == OREAD)
	runlock(&b->lock);
	else
	wunlock(&b->lock);

	qlock(&dcache.lock);
	if(--b->ref == 0 && !b->dirty){
	if(b->heap == TWID32)
	upheap(dcache.nheap++, b);
	rwakeupall(&dcache.full);
	}
	qunlock(&dcache.lock);
	}

	void
	dirtydblock(DBlock *b, int dirty)
	{
	int odirty;

	trace(TraceBlock, "dirtydblock enter %s 0x%llux %d from 0x%lux",
	b->part->name, b->addr, dirty, getcallerpc(&b));
	assert(b->ref != 0);
	assert(b->mode==ORDWR \|\| b->mode==OWRITE);

	odirty = b->dirty;
	if(b->dirty)
	assert(b->dirty == dirty);
	else
	b->dirty = dirty;

	qlock(&dcache.lock);
	if(!odirty){
	dcache.ndirty++;
	setstat(StatDcacheDirty, dcache.ndirty);
	if(dcache.ndirty >= dcache.maxdirty)
	kickround(&dcache.round, 0);
	else
	delaykickround(&dcache.round);
	}
	qunlock(&dcache.lock);
	}

	static void
	unchain(DBlock *b)
	{
	ulong h;

	/*
	* unchain the block
	*/
	if(b->prev == nil){
	h = pbhash(b->addr);
	if(dcache.heads[h] != b)
	sysfatal("bad hash chains in disk cache");
	dcache.heads[h] = b->next;
	}else
	b->prev->next = b->next;
	if(b->next != nil)
	b->next->prev = b->prev;
	}

	/*
	* remove some block from use and update the free list and counters
	*/
	static DBlock*
	bumpdblock(void)
	{
	DBlock *b;

	trace(TraceBlock, "bumpdblock enter");
	b = dcache.free;
	if(b != nil){
	dcache.free = b->next;
	return b;
	}

	if(dcache.ndirty >= dcache.maxdirty)
	kickdcache();

	/*
	* remove blocks until we find one that is unused
	* referenced blocks are left in the heap even though
	* they can't be scavenged; this is simple a speed optimization
	*/
	for(;;){
	if(dcache.nheap == 0){
	kickdcache();
	trace(TraceBlock, "bumpdblock gotnothing");
	return nil;
	}
	b = dcache.heap[0];
	delheap(b);
	if(!b->ref && !b->dirty)
	break;
	}

	trace(TraceBlock, "bumpdblock bumping %s 0x%llux", b->part->name, b->addr);

	unchain(b);
	return b;
	}

	void
	emptydcache(void)
	{
	DBlock *b;

	qlock(&dcache.lock);
	while(dcache.nheap > 0){
	b = dcache.heap[0];
	delheap(b);
	if(!b->ref && !b->dirty){
	unchain(b);
	b->next = dcache.free;
	dcache.free = b;
	}
	}
	qunlock(&dcache.lock);
	}

	/*
	* delete an arbitrary block from the heap
	*/
	static void
	delheap(DBlock *db)
	{
	if(db->heap == TWID32)
	return;
	fixheap(db->heap, dcache.heap[--dcache.nheap]);
	db->heap = TWID32;
	}

	/*
	* push an element up or down to it's correct new location
	*/
	static void
	fixheap(int i, DBlock *b)
	{
	if(upheap(i, b) == i)
	downheap(i, b);
	}

	static int
	upheap(int i, DBlock *b)
	{
	DBlock *bb;
	u32int now;
	int p;

	now = dcache.now;
	for(; i != 0; i = p){
	p = (i - 1) >> 1;
	bb = dcache.heap[p];
	if(b->used2 - now >= bb->used2 - now)
	break;
	dcache.heap[i] = bb;
	bb->heap = i;
	}

	dcache.heap[i] = b;
	b->heap = i;
	return i;
	}

	static int
	downheap(int i, DBlock *b)
	{
	DBlock *bb;
	u32int now;
	int k;

	now = dcache.now;
	for(; ; i = k){
	k = (i << 1) + 1;
	if(k >= dcache.nheap)
	break;
	if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
	k++;
	bb = dcache.heap[k];
	if(b->used2 - now <= bb->used2 - now)
	break;
	dcache.heap[i] = bb;
	bb->heap = i;
	}

	dcache.heap[i] = b;
	b->heap = i;
	return i;
	}

	static void
	findblock(DBlock *bb)
	{
	DBlock b, last;
	int h;

	last = nil;
	h = pbhash(bb->addr);
	for(b = dcache.heads[h]; b != nil; b = b->next){
	if(last != b->prev)
	sysfatal("bad prev link");
	if(b == bb)
	return;
	last = b;
	}
	sysfatal("block missing from hash table");
	}

	void
	checkdcache(void)
	{
	DBlock *b;
	u32int size, now;
	int i, k, refed, nfree;

	qlock(&dcache.lock);
	size = dcache.size;
	now = dcache.now;
	for(i = 0; i < dcache.nheap; i++){
	if(dcache.heap[i]->heap != i)
	sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
	if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
	sysfatal("dc: bad heap ordering");
	k = (i << 1) + 1;
	if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
	sysfatal("dc: bad heap ordering");
	k++;
	if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
	sysfatal("dc: bad heap ordering");
	}

	refed = 0;
	for(i = 0; i < dcache.nblocks; i++){
	b = &dcache.blocks[i];
	if(b->data != &dcache.mem[i * size])
	sysfatal("dc: mis-blocked at %d", i);
	if(b->ref && b->heap == TWID32)
	refed++;
	if(b->addr)
	findblock(b);
	if(b->heap != TWID32
	&& dcache.heap[b->heap] != b)
	sysfatal("dc: spurious heap value");
	}

	nfree = 0;
	for(b = dcache.free; b != nil; b = b->next){
	if(b->addr != 0 \|\| b->heap != TWID32)
	sysfatal("dc: bad free list");
	nfree++;
	}

	if(dcache.nheap + nfree + refed != dcache.nblocks)
	sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
	qunlock(&dcache.lock);
	}

	void
	flushdcache(void)
	{
	trace(TraceProc, "flushdcache enter");
	kickround(&dcache.round, 1);
	trace(TraceProc, "flushdcache exit");
	}

	void
	kickdcache(void)
	{
	kickround(&dcache.round, 0);
	}

	static int
	parallelwrites(DBlock b, DBlock eb, int dirty)
	{
	DBlock p, q;
	Part *part;

	for(p=b; p<eb && (*p)->dirty == dirty; p++){
	assert(b<=p && p<eb);
	sendp((p)->part->writechan, p);
	}
	q = p;
	for(p=b; p<q; p++){
	assert(b<=p && p<eb);
	recvp((*p)->writedonechan);
	}

	/*
	* Flush the partitions that have been written to.
	*/
	part = nil;
	for(p=b; p<q; p++){
	if(part != (*p)->part){
	part = (*p)->part;
	flushpart(part); /* what if it fails? */
	}
	}

	return p-b;
	}

	/*
	* Sort first by dirty flag, then by partition, then by address in partition.
	*/
	static int
	writeblockcmp(const void va, const void vb)
	{
	DBlock a, b;

	a = (DBlock*)va;
	b = (DBlock*)vb;

	if(a->dirty != b->dirty)
	return a->dirty - b->dirty;
	if(a->part != b->part){
	if(a->part < b->part)
	return -1;
	if(a->part > b->part)
	return 1;
	}
	if(a->addr < b->addr)
	return -1;
	return 1;
	}

	static void
	flushproc(void *v)
	{
	int i, j, n;
	ulong t0;
	DBlock b, *write;

	USED(v);
	threadsetname("flushproc");
	for(;;){
	waitforkick(&dcache.round);

	trace(TraceWork, "start");
	t0 = nsec()/1000;
	trace(TraceProc, "build t=%lud", (ulong)(nsec()/1000)-t0);

	write = dcache.write;
	n = 0;
	for(i=0; i<dcache.nblocks; i++){
	b = &dcache.blocks[i];
	if(b->dirty)
	write[n++] = b;
	}

	qsort(write, n, sizeof(write[0]), writeblockcmp);

	/* Write each stage of blocks out. */
	trace(TraceProc, "writeblocks t=%lud", (ulong)(nsec()/1000)-t0);
	i = 0;
	for(j=1; j<DirtyMax; j++){
	trace(TraceProc, "writeblocks.%d t=%lud",
	j, (ulong)(nsec()/1000)-t0);
	i += parallelwrites(write+i, write+n, j);
	}
	if(i != n){
	fprint(2, "in flushproc i=%d n=%d\n", i, n);
	for(i=0; i<n; i++)
	fprint(2, "\tblock %d: dirty=%d\n",
	i, write[i]->dirty);
	abort();
	}

	/*
	* b->dirty is protected by b->lock while ndirty is protected
	* by dcache.lock, so the --ndirty below is the delayed one
	* from clearing b->dirty in the write proc. It may happen
	* that some other proc has come along and redirtied b since
	* the write. That's okay, it just means that ndirty may be
	* one too high until we catch up and do the decrement.
	*/
	trace(TraceProc, "undirty.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
	qlock(&dcache.lock);
	for(i=0; i<n; i++){
	b = write[i];
	--dcache.ndirty;
	if(b->ref == 0 && b->heap == TWID32){
	upheap(dcache.nheap++, b);
	rwakeupall(&dcache.full);
	}
	}
	setstat(StatDcacheDirty, dcache.ndirty);
	qunlock(&dcache.lock);
	addstat(StatDcacheFlush, 1);
	trace(TraceWork, "finish");
	}
	}

	static void
	writeproc(void *v)
	{
	DBlock *b;
	Part *p;

	p = v;

	threadsetname("writeproc:%s", p->name);
	for(;;){
	b = recvp(p->writechan);
	trace(TraceWork, "start");
	assert(b->part == p);
	trace(TraceProc, "wlock %s 0x%llux", p->name, b->addr);
	wlock(&b->lock);
	trace(TraceProc, "writepart %s 0x%llux", p->name, b->addr);
	diskaccess(0);
	if(writepart(p, b->addr, b->data, b->size) < 0)
	fprint(2, "%s: writeproc: part %s addr 0x%llux: write error: %r\n",
	argv0, p->name, b->addr);
	addstat(StatApartWrite, 1);
	addstat(StatApartWriteBytes, b->size);
	b->dirty = 0;
	wunlock(&b->lock);
	trace(TraceProc, "finish %s 0x%llux", p->name, b->addr);
	trace(TraceWork, "finish");
	sendp(b->writedonechan, b);
	}
	}