xref: /plan9-contrib/sys/src/cmd/fossil/cache.c (revision 39734e7ed1eb944f5e7b41936007d0d38b560d7f)
15e96a66cSDavid du Colombier #include "stdinc.h"
25e96a66cSDavid du Colombier #include "dat.h"
35e96a66cSDavid du Colombier #include "fns.h"
45e96a66cSDavid du Colombier #include "error.h"
55e96a66cSDavid du Colombier 
65e96a66cSDavid du Colombier #include "9.h"	/* for cacheFlush */
75e96a66cSDavid du Colombier 
85e96a66cSDavid du Colombier typedef struct FreeList FreeList;
95e96a66cSDavid du Colombier typedef struct BAddr BAddr;
105e96a66cSDavid du Colombier 
115e96a66cSDavid du Colombier enum {
125e96a66cSDavid du Colombier 	BadHeap = ~0,
135e96a66cSDavid du Colombier };
145e96a66cSDavid du Colombier 
155e96a66cSDavid du Colombier /*
165e96a66cSDavid du Colombier  * Store data to the memory cache in c->size blocks
175e96a66cSDavid du Colombier  * with the block zero extended to fill it out.  When writing to
185e96a66cSDavid du Colombier  * Venti, the block will be zero truncated.  The walker will also check
195e96a66cSDavid du Colombier  * that the block fits within psize or dsize as the case may be.
205e96a66cSDavid du Colombier  */
215e96a66cSDavid du Colombier 
225e96a66cSDavid du Colombier struct Cache
235e96a66cSDavid du Colombier {
245e96a66cSDavid du Colombier 	VtLock	*lk;
255e96a66cSDavid du Colombier 	int 	ref;
265e96a66cSDavid du Colombier 	int	mode;
275e96a66cSDavid du Colombier 
285e96a66cSDavid du Colombier 	Disk 	*disk;
295e96a66cSDavid du Colombier 	int	size;			/* block size */
3061201b97SDavid du Colombier 	int	ndmap;		/* size of per-block dirty pointer map used in blockWrite */
315e96a66cSDavid du Colombier 	VtSession *z;
325e96a66cSDavid du Colombier 	u32int	now;			/* ticks for usage timestamps */
335e96a66cSDavid du Colombier 	Block	**heads;		/* hash table for finding address */
345e96a66cSDavid du Colombier 	int	nheap;			/* number of available victims */
355e96a66cSDavid du Colombier 	Block	**heap;			/* heap for locating victims */
365e96a66cSDavid du Colombier 	long	nblocks;		/* number of blocks allocated */
375e96a66cSDavid du Colombier 	Block	*blocks;		/* array of block descriptors */
385e96a66cSDavid du Colombier 	u8int	*mem;			/* memory for all block data & blists */
395e96a66cSDavid du Colombier 
405e96a66cSDavid du Colombier 	BList	*blfree;
415e96a66cSDavid du Colombier 	VtRendez *blrend;
425e96a66cSDavid du Colombier 
435e96a66cSDavid du Colombier 	int 	ndirty;			/* number of dirty blocks in the cache */
445e96a66cSDavid du Colombier 	int 	maxdirty;		/* max number of dirty blocks */
455e96a66cSDavid du Colombier 	u32int	vers;
465e96a66cSDavid du Colombier 
475e96a66cSDavid du Colombier 	long hashSize;
485e96a66cSDavid du Colombier 
495e96a66cSDavid du Colombier 	FreeList *fl;
505e96a66cSDavid du Colombier 
515e96a66cSDavid du Colombier 	VtRendez *die;			/* daemon threads should die when != nil */
525e96a66cSDavid du Colombier 
535e96a66cSDavid du Colombier 	VtRendez *flush;
545e96a66cSDavid du Colombier 	VtRendez *flushwait;
555e96a66cSDavid du Colombier 	BAddr *baddr;
565e96a66cSDavid du Colombier 	int bw, br, be;
575e96a66cSDavid du Colombier 	int nflush;
585e96a66cSDavid du Colombier 
5961201b97SDavid du Colombier 	Periodic *sync;
6061201b97SDavid du Colombier 
615e96a66cSDavid du Colombier 	/* unlink daemon */
625e96a66cSDavid du Colombier 	BList *uhead;
635e96a66cSDavid du Colombier 	BList *utail;
645e96a66cSDavid du Colombier 	VtRendez *unlink;
657abd426fSDavid du Colombier 
667abd426fSDavid du Colombier 	/* block counts */
677abd426fSDavid du Colombier 	int nused;
687abd426fSDavid du Colombier 	int ndisk;
695e96a66cSDavid du Colombier };
705e96a66cSDavid du Colombier 
715e96a66cSDavid du Colombier struct BList {
725e96a66cSDavid du Colombier 	int part;
735e96a66cSDavid du Colombier 	u32int addr;
745e96a66cSDavid du Colombier 	uchar type;
755e96a66cSDavid du Colombier 	u32int tag;
765e96a66cSDavid du Colombier 	u32int epoch;
775e96a66cSDavid du Colombier 	u32int vers;
785e96a66cSDavid du Colombier 
795e96a66cSDavid du Colombier 	/* for roll back */
805e96a66cSDavid du Colombier 	int index;			/* -1 indicates not valid */
8161201b97SDavid du Colombier 	union {
825e96a66cSDavid du Colombier 		uchar score[VtScoreSize];
8361201b97SDavid du Colombier 		uchar entry[VtEntrySize];
8461201b97SDavid du Colombier 	} old;
855e96a66cSDavid du Colombier 	BList *next;
865e96a66cSDavid du Colombier };
875e96a66cSDavid du Colombier 
885e96a66cSDavid du Colombier struct BAddr {
895e96a66cSDavid du Colombier 	int part;
905e96a66cSDavid du Colombier 	u32int addr;
915e96a66cSDavid du Colombier 	u32int vers;
925e96a66cSDavid du Colombier };
935e96a66cSDavid du Colombier 
945e96a66cSDavid du Colombier struct FreeList {
955e96a66cSDavid du Colombier 	VtLock *lk;
965e96a66cSDavid du Colombier 	u32int last;	/* last block allocated */
975e96a66cSDavid du Colombier 	u32int end;	/* end of data partition */
987abd426fSDavid du Colombier 	u32int nfree;	/* number of free blocks */
997abd426fSDavid du Colombier 	u32int nused;	/* number of used blocks */
1007abd426fSDavid du Colombier 	u32int epochLow;	/* low epoch when last updated nfree and nused */
1015e96a66cSDavid du Colombier };
1025e96a66cSDavid du Colombier 
1035e96a66cSDavid du Colombier static FreeList *flAlloc(u32int end);
1045e96a66cSDavid du Colombier static void flFree(FreeList *fl);
1055e96a66cSDavid du Colombier 
1065e96a66cSDavid du Colombier static Block *cacheBumpBlock(Cache *c);
1075e96a66cSDavid du Colombier static void heapDel(Block*);
1085e96a66cSDavid du Colombier static void heapIns(Block*);
1095e96a66cSDavid du Colombier static void cacheCheck(Cache*);
1105e96a66cSDavid du Colombier static int readLabel(Cache*, Label*, u32int addr);
1115e96a66cSDavid du Colombier static void unlinkThread(void *a);
1125e96a66cSDavid du Colombier static void flushThread(void *a);
1135e96a66cSDavid du Colombier static void flushBody(Cache *c);
1145e96a66cSDavid du Colombier static void unlinkBody(Cache *c);
1155e96a66cSDavid du Colombier static int cacheFlushBlock(Cache *c);
11661201b97SDavid du Colombier static void cacheSync(void*);
1175e96a66cSDavid du Colombier /*
1185e96a66cSDavid du Colombier  * Mapping from local block type to Venti type
1195e96a66cSDavid du Colombier  */
1205e96a66cSDavid du Colombier int vtType[BtMax] = {
1215e96a66cSDavid du Colombier 	VtDataType,		/* BtData | 0  */
1225e96a66cSDavid du Colombier 	VtPointerType0,		/* BtData | 1  */
1235e96a66cSDavid du Colombier 	VtPointerType1,		/* BtData | 2  */
1245e96a66cSDavid du Colombier 	VtPointerType2,		/* BtData | 3  */
1255e96a66cSDavid du Colombier 	VtPointerType3,		/* BtData | 4  */
1265e96a66cSDavid du Colombier 	VtPointerType4,		/* BtData | 5  */
1275e96a66cSDavid du Colombier 	VtPointerType5,		/* BtData | 6  */
1285e96a66cSDavid du Colombier 	VtPointerType6,		/* BtData | 7  */
1295e96a66cSDavid du Colombier 	VtDirType,		/* BtDir | 0  */
1305e96a66cSDavid du Colombier 	VtPointerType0,		/* BtDir | 1  */
1315e96a66cSDavid du Colombier 	VtPointerType1,		/* BtDir | 2  */
1325e96a66cSDavid du Colombier 	VtPointerType2,		/* BtDir | 3  */
1335e96a66cSDavid du Colombier 	VtPointerType3,		/* BtDir | 4  */
1345e96a66cSDavid du Colombier 	VtPointerType4,		/* BtDir | 5  */
1355e96a66cSDavid du Colombier 	VtPointerType5,		/* BtDir | 6  */
1365e96a66cSDavid du Colombier 	VtPointerType6,		/* BtDir | 7  */
1375e96a66cSDavid du Colombier };
1385e96a66cSDavid du Colombier 
1395e96a66cSDavid du Colombier /*
1405e96a66cSDavid du Colombier  * Allocate the memory cache.
1415e96a66cSDavid du Colombier  */
1425e96a66cSDavid du Colombier Cache *
1435e96a66cSDavid du Colombier cacheAlloc(Disk *disk, VtSession *z, ulong nblocks, int mode)
1445e96a66cSDavid du Colombier {
1455e96a66cSDavid du Colombier 	int i;
1465e96a66cSDavid du Colombier 	Cache *c;
1475e96a66cSDavid du Colombier 	Block *b;
1485e96a66cSDavid du Colombier 	BList *bl;
1495e96a66cSDavid du Colombier 	u8int *p;
1505e96a66cSDavid du Colombier 	int nbl;
1515e96a66cSDavid du Colombier 
1525e96a66cSDavid du Colombier 	c = vtMemAllocZ(sizeof(Cache));
1535e96a66cSDavid du Colombier 
1545e96a66cSDavid du Colombier 	/* reasonable number of BList elements */
1555e96a66cSDavid du Colombier 	nbl = nblocks * 4;
1565e96a66cSDavid du Colombier 
1575e96a66cSDavid du Colombier 	c->lk = vtLockAlloc();
1585e96a66cSDavid du Colombier 	c->ref = 1;
1595e96a66cSDavid du Colombier 	c->disk = disk;
1605e96a66cSDavid du Colombier 	c->z = z;
1615e96a66cSDavid du Colombier 	c->size = diskBlockSize(disk);
1625e96a66cSDavid du Colombier bwatchSetBlockSize(c->size);
1635e96a66cSDavid du Colombier 	/* round c->size up to be a nice multiple */
1645e96a66cSDavid du Colombier 	c->size = (c->size + 127) & ~127;
16561201b97SDavid du Colombier 	c->ndmap = (c->size/20 + 7) / 8;
1665e96a66cSDavid du Colombier 	c->nblocks = nblocks;
1675e96a66cSDavid du Colombier 	c->hashSize = nblocks;
1685e96a66cSDavid du Colombier 	c->heads = vtMemAllocZ(c->hashSize*sizeof(Block*));
1695e96a66cSDavid du Colombier 	c->heap = vtMemAllocZ(nblocks*sizeof(Block*));
1705e96a66cSDavid du Colombier 	c->blocks = vtMemAllocZ(nblocks*sizeof(Block));
17161201b97SDavid du Colombier 	c->mem = vtMemAllocZ(nblocks * (c->size + c->ndmap) + nbl * sizeof(BList));
1725e96a66cSDavid du Colombier 	c->baddr = vtMemAllocZ(nblocks * sizeof(BAddr));
1735e96a66cSDavid du Colombier 	c->mode = mode;
1745e96a66cSDavid du Colombier 	c->vers++;
1755e96a66cSDavid du Colombier 	p = c->mem;
1765e96a66cSDavid du Colombier 	for(i = 0; i < nblocks; i++){
1775e96a66cSDavid du Colombier 		b = &c->blocks[i];
1785e96a66cSDavid du Colombier 		b->lk = vtLockAlloc();
1795e96a66cSDavid du Colombier 		b->c = c;
1805e96a66cSDavid du Colombier 		b->data = p;
1815e96a66cSDavid du Colombier 		b->heap = i;
1825e96a66cSDavid du Colombier 		b->ioready = vtRendezAlloc(b->lk);
1835e96a66cSDavid du Colombier 		c->heap[i] = b;
1845e96a66cSDavid du Colombier 		p += c->size;
1855e96a66cSDavid du Colombier 	}
1865e96a66cSDavid du Colombier 	c->nheap = nblocks;
1875e96a66cSDavid du Colombier 	for(i = 0; i < nbl; i++){
1885e96a66cSDavid du Colombier 		bl = (BList*)p;
1895e96a66cSDavid du Colombier 		bl->next = c->blfree;
1905e96a66cSDavid du Colombier 		c->blfree = bl;
1915e96a66cSDavid du Colombier 		p += sizeof(BList);
1925e96a66cSDavid du Colombier 	}
19361201b97SDavid du Colombier 	/* separate loop to keep blocks and blists reasonably aligned */
19461201b97SDavid du Colombier 	for(i = 0; i < nblocks; i++){
19561201b97SDavid du Colombier 		b = &c->blocks[i];
19661201b97SDavid du Colombier 		b->dmap = p;
19761201b97SDavid du Colombier 		p += c->ndmap;
19861201b97SDavid du Colombier 	}
19961201b97SDavid du Colombier 
2005e96a66cSDavid du Colombier 	c->blrend = vtRendezAlloc(c->lk);
2015e96a66cSDavid du Colombier 
2025e96a66cSDavid du Colombier 	c->maxdirty = nblocks*(DirtyPercentage*0.01);
2035e96a66cSDavid du Colombier 
2045e96a66cSDavid du Colombier 	c->fl = flAlloc(diskSize(disk, PartData));
2055e96a66cSDavid du Colombier 
2065e96a66cSDavid du Colombier 	c->unlink = vtRendezAlloc(c->lk);
2075e96a66cSDavid du Colombier 	c->flush = vtRendezAlloc(c->lk);
2085e96a66cSDavid du Colombier 	c->flushwait = vtRendezAlloc(c->lk);
20961201b97SDavid du Colombier 	c->sync = periodicAlloc(cacheSync, c, 30*1000);
2105e96a66cSDavid du Colombier 
2115e96a66cSDavid du Colombier 	if(mode == OReadWrite){
2125e96a66cSDavid du Colombier 		c->ref += 2;
2135e96a66cSDavid du Colombier 		vtThread(unlinkThread, c);
2145e96a66cSDavid du Colombier 		vtThread(flushThread, c);
2155e96a66cSDavid du Colombier 	}
2165e96a66cSDavid du Colombier 	cacheCheck(c);
2175e96a66cSDavid du Colombier 
2185e96a66cSDavid du Colombier 	return c;
2195e96a66cSDavid du Colombier }
2205e96a66cSDavid du Colombier 
2215e96a66cSDavid du Colombier /*
2225e96a66cSDavid du Colombier  * Free the whole memory cache, flushing all dirty blocks to the disk.
2235e96a66cSDavid du Colombier  */
2245e96a66cSDavid du Colombier void
2255e96a66cSDavid du Colombier cacheFree(Cache *c)
2265e96a66cSDavid du Colombier {
2275e96a66cSDavid du Colombier 	int i;
2285e96a66cSDavid du Colombier 
2295e96a66cSDavid du Colombier 	/* kill off daemon threads */
2305e96a66cSDavid du Colombier 	vtLock(c->lk);
2315e96a66cSDavid du Colombier 	c->die = vtRendezAlloc(c->lk);
23261201b97SDavid du Colombier 	periodicKill(c->sync);
2335e96a66cSDavid du Colombier 	vtWakeup(c->flush);
2345e96a66cSDavid du Colombier 	vtWakeup(c->unlink);
2355e96a66cSDavid du Colombier 	while(c->ref > 1)
2365e96a66cSDavid du Colombier 		vtSleep(c->die);
2375e96a66cSDavid du Colombier 
2385e96a66cSDavid du Colombier 	/* flush everything out */
2395e96a66cSDavid du Colombier 	do {
2405e96a66cSDavid du Colombier 		unlinkBody(c);
2415e96a66cSDavid du Colombier 		vtUnlock(c->lk);
2425e96a66cSDavid du Colombier 		while(cacheFlushBlock(c))
2435e96a66cSDavid du Colombier 			;
2445e96a66cSDavid du Colombier 		diskFlush(c->disk);
2455e96a66cSDavid du Colombier 		vtLock(c->lk);
2465e96a66cSDavid du Colombier 	} while(c->uhead || c->ndirty);
2475e96a66cSDavid du Colombier 	vtUnlock(c->lk);
2485e96a66cSDavid du Colombier 
2495e96a66cSDavid du Colombier 	cacheCheck(c);
2505e96a66cSDavid du Colombier 
2515e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
2525e96a66cSDavid du Colombier 		assert(c->blocks[i].ref == 0);
2535e96a66cSDavid du Colombier 		vtRendezFree(c->blocks[i].ioready);
2545e96a66cSDavid du Colombier 		vtLockFree(c->blocks[i].lk);
2555e96a66cSDavid du Colombier 	}
2565e96a66cSDavid du Colombier 	flFree(c->fl);
2575e96a66cSDavid du Colombier 	vtMemFree(c->baddr);
2585e96a66cSDavid du Colombier 	vtMemFree(c->heads);
2595e96a66cSDavid du Colombier 	vtMemFree(c->blocks);
2605e96a66cSDavid du Colombier 	vtMemFree(c->mem);
2615e96a66cSDavid du Colombier 	vtLockFree(c->lk);
2625e96a66cSDavid du Colombier 	diskFree(c->disk);
2635e96a66cSDavid du Colombier 	vtRendezFree(c->blrend);
2645e96a66cSDavid du Colombier 	/* don't close vtSession */
2655e96a66cSDavid du Colombier 	vtMemFree(c);
2665e96a66cSDavid du Colombier }
2675e96a66cSDavid du Colombier 
2685e96a66cSDavid du Colombier static void
2695e96a66cSDavid du Colombier cacheDump(Cache *c)
2705e96a66cSDavid du Colombier {
2715e96a66cSDavid du Colombier 	int i;
2725e96a66cSDavid du Colombier 	Block *b;
2735e96a66cSDavid du Colombier 
2745e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
2755e96a66cSDavid du Colombier 		b = &c->blocks[i];
2765e96a66cSDavid du Colombier 		fprint(2, "p=%d a=%ud %V t=%d ref=%d state=%s io=%s\n",
2775e96a66cSDavid du Colombier 			b->part, b->addr, b->score, b->l.type, b->ref,
2785e96a66cSDavid du Colombier 			bsStr(b->l.state), bioStr(b->iostate));
2795e96a66cSDavid du Colombier 	}
2805e96a66cSDavid du Colombier }
2815e96a66cSDavid du Colombier 
2825e96a66cSDavid du Colombier static void
2835e96a66cSDavid du Colombier cacheCheck(Cache *c)
2845e96a66cSDavid du Colombier {
2855e96a66cSDavid du Colombier 	u32int size, now;
2865e96a66cSDavid du Colombier 	int i, k, refed;
2875e96a66cSDavid du Colombier 	static uchar zero[VtScoreSize];
2885e96a66cSDavid du Colombier 	Block *b;
2895e96a66cSDavid du Colombier 
2905e96a66cSDavid du Colombier 	size = c->size;
2915e96a66cSDavid du Colombier 	now = c->now;
2925e96a66cSDavid du Colombier 
2935e96a66cSDavid du Colombier 	for(i = 0; i < c->nheap; i++){
2945e96a66cSDavid du Colombier 		if(c->heap[i]->heap != i)
2955e96a66cSDavid du Colombier 			vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
2965e96a66cSDavid du Colombier 		if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
2975e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
2985e96a66cSDavid du Colombier 		k = (i << 1) + 1;
2995e96a66cSDavid du Colombier 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
3005e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
3015e96a66cSDavid du Colombier 		k++;
3025e96a66cSDavid du Colombier 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
3035e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
3045e96a66cSDavid du Colombier 	}
3055e96a66cSDavid du Colombier 
3065e96a66cSDavid du Colombier 	refed = 0;
3075e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
3085e96a66cSDavid du Colombier 		b = &c->blocks[i];
3095e96a66cSDavid du Colombier 		if(b->data != &c->mem[i * size])
3105e96a66cSDavid du Colombier 			vtFatal("mis-blocked at %d", i);
3115e96a66cSDavid du Colombier 		if(b->ref && b->heap == BadHeap){
3125e96a66cSDavid du Colombier 			refed++;
3135e96a66cSDavid du Colombier 		}
3145e96a66cSDavid du Colombier 	}
3155e96a66cSDavid du Colombier if(c->nheap + refed != c->nblocks){
3165e96a66cSDavid du Colombier fprint(2, "cacheCheck: nheap %d refed %d nblocks %ld\n", c->nheap, refed, c->nblocks);
3175e96a66cSDavid du Colombier cacheDump(c);
3185e96a66cSDavid du Colombier }
3195e96a66cSDavid du Colombier 	assert(c->nheap + refed == c->nblocks);
3205e96a66cSDavid du Colombier 	refed = 0;
3215e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
3225e96a66cSDavid du Colombier 		b = &c->blocks[i];
3235e96a66cSDavid du Colombier 		if(b->ref){
3245e96a66cSDavid du Colombier if(1)fprint(2, "p=%d a=%ud %V ref=%d %L\n", b->part, b->addr, b->score, b->ref, &b->l);
3255e96a66cSDavid du Colombier 			refed++;
3265e96a66cSDavid du Colombier 		}
3275e96a66cSDavid du Colombier 	}
3285e96a66cSDavid du Colombier if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
3295e96a66cSDavid du Colombier }
3305e96a66cSDavid du Colombier 
3315e96a66cSDavid du Colombier 
3325e96a66cSDavid du Colombier /*
3335e96a66cSDavid du Colombier  * locate the block with the oldest second to last use.
3345e96a66cSDavid du Colombier  * remove it from the heap, and fix up the heap.
3355e96a66cSDavid du Colombier  */
3365e96a66cSDavid du Colombier /* called with c->lk held */
3375e96a66cSDavid du Colombier static Block *
3385e96a66cSDavid du Colombier cacheBumpBlock(Cache *c)
3395e96a66cSDavid du Colombier {
3405e96a66cSDavid du Colombier 	Block *b;
3415e96a66cSDavid du Colombier 
3425e96a66cSDavid du Colombier 	/*
3435e96a66cSDavid du Colombier 	 * locate the block with the oldest second to last use.
3445e96a66cSDavid du Colombier 	 * remove it from the heap, and fix up the heap.
3455e96a66cSDavid du Colombier 	 */
3465e96a66cSDavid du Colombier 	if(c->nheap == 0)
3475e96a66cSDavid du Colombier 		vtFatal("cacheBumpBlock: no free blocks in cache");
3485e96a66cSDavid du Colombier 	b = c->heap[0];
3495e96a66cSDavid du Colombier 	heapDel(b);
3505e96a66cSDavid du Colombier 
3515e96a66cSDavid du Colombier 	assert(b->heap == BadHeap);
3525e96a66cSDavid du Colombier 	assert(b->ref == 0);
3535e96a66cSDavid du Colombier 	assert(b->iostate == BioEmpty || b->iostate == BioLabel || b->iostate == BioClean);
3545e96a66cSDavid du Colombier 	assert(b->prior == nil);
3555e96a66cSDavid du Colombier 	assert(b->uhead == nil);
3565e96a66cSDavid du Colombier 
3575e96a66cSDavid du Colombier 	/*
3585e96a66cSDavid du Colombier 	 * unchain the block from hash chain
3595e96a66cSDavid du Colombier 	 */
3605e96a66cSDavid du Colombier 	if(b->prev){
3615e96a66cSDavid du Colombier 		*(b->prev) = b->next;
3625e96a66cSDavid du Colombier 		if(b->next)
3635e96a66cSDavid du Colombier 			b->next->prev = b->prev;
3645e96a66cSDavid du Colombier 		b->prev = nil;
3655e96a66cSDavid du Colombier 	}
3665e96a66cSDavid du Colombier 
3675e96a66cSDavid du Colombier 
3685e96a66cSDavid du Colombier if(0)fprint(2, "droping %d:%x:%V\n", b->part, b->addr, b->score);
3695e96a66cSDavid du Colombier 	/* set block to a reasonable state */
3705e96a66cSDavid du Colombier 	b->ref = 1;
3715e96a66cSDavid du Colombier 	b->part = PartError;
3725e96a66cSDavid du Colombier 	memset(&b->l, 0, sizeof(b->l));
3735e96a66cSDavid du Colombier 	b->iostate = BioEmpty;
3745e96a66cSDavid du Colombier 
3755e96a66cSDavid du Colombier 	return b;
3765e96a66cSDavid du Colombier }
3775e96a66cSDavid du Colombier 
3785e96a66cSDavid du Colombier /*
3795e96a66cSDavid du Colombier  * look for a particular version of the block in the memory cache.
3805e96a66cSDavid du Colombier  */
3815e96a66cSDavid du Colombier static Block *
3825e96a66cSDavid du Colombier _cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers,
3835e96a66cSDavid du Colombier 	int waitlock, int *lockfailure)
3845e96a66cSDavid du Colombier {
3855e96a66cSDavid du Colombier 	Block *b;
3865e96a66cSDavid du Colombier 	ulong h;
3875e96a66cSDavid du Colombier 
3885e96a66cSDavid du Colombier 	h = addr % c->hashSize;
3895e96a66cSDavid du Colombier 
3905e96a66cSDavid du Colombier 	if(lockfailure)
3915e96a66cSDavid du Colombier 		*lockfailure = 0;
3925e96a66cSDavid du Colombier 
3935e96a66cSDavid du Colombier 	/*
3945e96a66cSDavid du Colombier 	 * look for the block in the cache
3955e96a66cSDavid du Colombier 	 */
3965e96a66cSDavid du Colombier 	vtLock(c->lk);
3975e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
3985e96a66cSDavid du Colombier 		if(b->part == part && b->addr == addr)
3995e96a66cSDavid du Colombier 			break;
4005e96a66cSDavid du Colombier 	}
4015e96a66cSDavid du Colombier 	if(b == nil || b->vers != vers){
4025e96a66cSDavid du Colombier 		vtUnlock(c->lk);
4035e96a66cSDavid du Colombier 		return nil;
4045e96a66cSDavid du Colombier 	}
4055e96a66cSDavid du Colombier 	if(!waitlock && !vtCanLock(b->lk)){
4065e96a66cSDavid du Colombier 		*lockfailure = 1;
4075e96a66cSDavid du Colombier 		vtUnlock(c->lk);
4085e96a66cSDavid du Colombier 		return nil;
4095e96a66cSDavid du Colombier 	}
4105e96a66cSDavid du Colombier 	heapDel(b);
4115e96a66cSDavid du Colombier 	b->ref++;
4125e96a66cSDavid du Colombier 	vtUnlock(c->lk);
4135e96a66cSDavid du Colombier 
4145e96a66cSDavid du Colombier 	bwatchLock(b);
4155e96a66cSDavid du Colombier 	if(waitlock)
4165e96a66cSDavid du Colombier 		vtLock(b->lk);
4175e96a66cSDavid du Colombier 	b->nlock = 1;
4185e96a66cSDavid du Colombier 
4195e96a66cSDavid du Colombier 	for(;;){
4205e96a66cSDavid du Colombier 		switch(b->iostate){
4215e96a66cSDavid du Colombier 		default:
4225e96a66cSDavid du Colombier 			abort();
4235e96a66cSDavid du Colombier 		case BioEmpty:
4245e96a66cSDavid du Colombier 		case BioLabel:
4255e96a66cSDavid du Colombier 		case BioClean:
4265e96a66cSDavid du Colombier 		case BioDirty:
4275e96a66cSDavid du Colombier 			if(b->vers != vers){
4285e96a66cSDavid du Colombier 				blockPut(b);
4295e96a66cSDavid du Colombier 				return nil;
4305e96a66cSDavid du Colombier 			}
4315e96a66cSDavid du Colombier 			return b;
4325e96a66cSDavid du Colombier 		case BioReading:
4335e96a66cSDavid du Colombier 		case BioWriting:
4345e96a66cSDavid du Colombier 			vtSleep(b->ioready);
4355e96a66cSDavid du Colombier 			break;
4365e96a66cSDavid du Colombier 		case BioVentiError:
4375e96a66cSDavid du Colombier 		case BioReadError:
4385e96a66cSDavid du Colombier 			blockSetIOState(b, BioEmpty);
4395e96a66cSDavid du Colombier 			blockPut(b);
4405e96a66cSDavid du Colombier 			vtSetError(EIO);
4415e96a66cSDavid du Colombier 			return nil;
4425e96a66cSDavid du Colombier 		}
4435e96a66cSDavid du Colombier 	}
4445e96a66cSDavid du Colombier 	/* NOT REACHED */
4455e96a66cSDavid du Colombier }
4465e96a66cSDavid du Colombier static Block*
4475e96a66cSDavid du Colombier cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers)
4485e96a66cSDavid du Colombier {
4495e96a66cSDavid du Colombier 	return _cacheLocalLookup(c, part, addr, vers, 1, 0);
4505e96a66cSDavid du Colombier }
4515e96a66cSDavid du Colombier 
4525e96a66cSDavid du Colombier 
4535e96a66cSDavid du Colombier /*
4545e96a66cSDavid du Colombier  * fetch a local (on-disk) block from the memory cache.
4555e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
4565e96a66cSDavid du Colombier  */
4575e96a66cSDavid du Colombier Block *
4585e96a66cSDavid du Colombier _cacheLocal(Cache *c, int part, u32int addr, int mode, u32int epoch)
4595e96a66cSDavid du Colombier {
4605e96a66cSDavid du Colombier 	Block *b;
4615e96a66cSDavid du Colombier 	ulong h;
4625e96a66cSDavid du Colombier 
4635e96a66cSDavid du Colombier 	assert(part != PartVenti);
4645e96a66cSDavid du Colombier 
4655e96a66cSDavid du Colombier 	h = addr % c->hashSize;
4665e96a66cSDavid du Colombier 
4675e96a66cSDavid du Colombier 	/*
4685e96a66cSDavid du Colombier 	 * look for the block in the cache
4695e96a66cSDavid du Colombier 	 */
4705e96a66cSDavid du Colombier 	vtLock(c->lk);
4715e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
4725e96a66cSDavid du Colombier 		if(b->part != part || b->addr != addr)
4735e96a66cSDavid du Colombier 			continue;
4745e96a66cSDavid du Colombier 		if(epoch && b->l.epoch != epoch){
4755e96a66cSDavid du Colombier fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
4765e96a66cSDavid du Colombier 			vtUnlock(c->lk);
4775e96a66cSDavid du Colombier 			vtSetError(ELabelMismatch);
4785e96a66cSDavid du Colombier 			return nil;
4795e96a66cSDavid du Colombier 		}
4805e96a66cSDavid du Colombier 		heapDel(b);
4815e96a66cSDavid du Colombier 		b->ref++;
4825e96a66cSDavid du Colombier 		break;
4835e96a66cSDavid du Colombier 	}
4845e96a66cSDavid du Colombier 
4855e96a66cSDavid du Colombier 	if(b == nil){
4865e96a66cSDavid du Colombier 		b = cacheBumpBlock(c);
4875e96a66cSDavid du Colombier 
4885e96a66cSDavid du Colombier 		b->part = part;
4895e96a66cSDavid du Colombier 		b->addr = addr;
4905e96a66cSDavid du Colombier 		localToGlobal(addr, b->score);
4915e96a66cSDavid du Colombier 
4925e96a66cSDavid du Colombier 		/* chain onto correct hash */
4935e96a66cSDavid du Colombier 		b->next = c->heads[h];
4945e96a66cSDavid du Colombier 		c->heads[h] = b;
4955e96a66cSDavid du Colombier 		if(b->next != nil)
4965e96a66cSDavid du Colombier 			b->next->prev = &b->next;
4975e96a66cSDavid du Colombier 		b->prev = &c->heads[h];
4985e96a66cSDavid du Colombier 	}
4995e96a66cSDavid du Colombier 
5005e96a66cSDavid du Colombier 	vtUnlock(c->lk);
5015e96a66cSDavid du Colombier 
5025e96a66cSDavid du Colombier 	/*
5035e96a66cSDavid du Colombier 	 * BUG: what if the epoch changes right here?
5045e96a66cSDavid du Colombier 	 * In the worst case, we could end up in some weird
5055e96a66cSDavid du Colombier 	 * lock loop, because the block we want no longer exists,
5065e96a66cSDavid du Colombier 	 * and instead we're trying to lock a block we have no
5075e96a66cSDavid du Colombier 	 * business grabbing.
5085e96a66cSDavid du Colombier 	 *
5095e96a66cSDavid du Colombier 	 * For now, I'm not going to worry about it.
5105e96a66cSDavid du Colombier 	 */
5115e96a66cSDavid du Colombier 
5125e96a66cSDavid du Colombier if(0)fprint(2, "cacheLocal: %d: %d %x\n", getpid(), b->part, b->addr);
5135e96a66cSDavid du Colombier 	bwatchLock(b);
5145e96a66cSDavid du Colombier 	vtLock(b->lk);
5155e96a66cSDavid du Colombier 	b->nlock = 1;
5165e96a66cSDavid du Colombier 
5175e96a66cSDavid du Colombier 	if(part == PartData && b->iostate == BioEmpty){
5185e96a66cSDavid du Colombier 		if(!readLabel(c, &b->l, addr)){
5195e96a66cSDavid du Colombier 			blockPut(b);
5205e96a66cSDavid du Colombier 			return nil;
5215e96a66cSDavid du Colombier 		}
5225e96a66cSDavid du Colombier 		blockSetIOState(b, BioLabel);
5235e96a66cSDavid du Colombier 	}
5245e96a66cSDavid du Colombier 	if(epoch && b->l.epoch != epoch){
5255e96a66cSDavid du Colombier 		blockPut(b);
5265e96a66cSDavid du Colombier fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
5275e96a66cSDavid du Colombier 		vtSetError(ELabelMismatch);
5285e96a66cSDavid du Colombier 		return nil;
5295e96a66cSDavid du Colombier 	}
5305e96a66cSDavid du Colombier 
5315e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
5325e96a66cSDavid du Colombier 	for(;;){
5335e96a66cSDavid du Colombier 		switch(b->iostate){
5345e96a66cSDavid du Colombier 		default:
5355e96a66cSDavid du Colombier 			abort();
5365e96a66cSDavid du Colombier 		case BioEmpty:
5375e96a66cSDavid du Colombier 		case BioLabel:
5385e96a66cSDavid du Colombier 			if(mode == OOverWrite){
5395e96a66cSDavid du Colombier 				blockSetIOState(b, BioClean);
5405e96a66cSDavid du Colombier 				return b;
5415e96a66cSDavid du Colombier 			}
5425e96a66cSDavid du Colombier 			diskRead(c->disk, b);
5435e96a66cSDavid du Colombier 			vtSleep(b->ioready);
5445e96a66cSDavid du Colombier 			break;
5455e96a66cSDavid du Colombier 		case BioClean:
5465e96a66cSDavid du Colombier 		case BioDirty:
5475e96a66cSDavid du Colombier 			return b;
5485e96a66cSDavid du Colombier 		case BioReading:
5495e96a66cSDavid du Colombier 		case BioWriting:
5505e96a66cSDavid du Colombier 			vtSleep(b->ioready);
5515e96a66cSDavid du Colombier 			break;
5525e96a66cSDavid du Colombier 		case BioReadError:
5535e96a66cSDavid du Colombier 			blockSetIOState(b, BioEmpty);
5545e96a66cSDavid du Colombier 			blockPut(b);
5555e96a66cSDavid du Colombier 			vtSetError(EIO);
5565e96a66cSDavid du Colombier 			return nil;
5575e96a66cSDavid du Colombier 		}
5585e96a66cSDavid du Colombier 	}
5595e96a66cSDavid du Colombier 	/* NOT REACHED */
5605e96a66cSDavid du Colombier }
5615e96a66cSDavid du Colombier 
5625e96a66cSDavid du Colombier Block *
5635e96a66cSDavid du Colombier cacheLocal(Cache *c, int part, u32int addr, int mode)
5645e96a66cSDavid du Colombier {
5655e96a66cSDavid du Colombier 	return _cacheLocal(c, part, addr, mode, 0);
5665e96a66cSDavid du Colombier }
5675e96a66cSDavid du Colombier 
5685e96a66cSDavid du Colombier /*
5695e96a66cSDavid du Colombier  * fetch a local (on-disk) block from the memory cache.
5705e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
5715e96a66cSDavid du Colombier  * check tag and type.
5725e96a66cSDavid du Colombier  */
5735e96a66cSDavid du Colombier Block *
5745e96a66cSDavid du Colombier cacheLocalData(Cache *c, u32int addr, int type, u32int tag, int mode, u32int epoch)
5755e96a66cSDavid du Colombier {
5765e96a66cSDavid du Colombier 	Block *b;
5775e96a66cSDavid du Colombier 
5785e96a66cSDavid du Colombier 	b = _cacheLocal(c, PartData, addr, mode, epoch);
5795e96a66cSDavid du Colombier 	if(b == nil)
5805e96a66cSDavid du Colombier 		return nil;
5815e96a66cSDavid du Colombier 	if(b->l.type != type || b->l.tag != tag){
5825e96a66cSDavid du Colombier 		fprint(2, "cacheLocalData: addr=%d type got %d exp %d: tag got %x exp %x\n",
5835e96a66cSDavid du Colombier 			addr, b->l.type, type, b->l.tag, tag);
5845e96a66cSDavid du Colombier abort();
5855e96a66cSDavid du Colombier 		vtSetError(ELabelMismatch);
5865e96a66cSDavid du Colombier 		blockPut(b);
5875e96a66cSDavid du Colombier 		return nil;
5885e96a66cSDavid du Colombier 	}
5895e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
5905e96a66cSDavid du Colombier 	return b;
5915e96a66cSDavid du Colombier }
5925e96a66cSDavid du Colombier 
5935e96a66cSDavid du Colombier /*
5945e96a66cSDavid du Colombier  * fetch a global (Venti) block from the memory cache.
5955e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
5965e96a66cSDavid du Colombier  * check tag and type if it's really a local block in disguise.
5975e96a66cSDavid du Colombier  */
5985e96a66cSDavid du Colombier Block *
5995e96a66cSDavid du Colombier cacheGlobal(Cache *c, uchar score[VtScoreSize], int type, u32int tag, int mode)
6005e96a66cSDavid du Colombier {
6015e96a66cSDavid du Colombier 	int n;
6025e96a66cSDavid du Colombier 	Block *b;
6035e96a66cSDavid du Colombier 	ulong h;
6045e96a66cSDavid du Colombier 	u32int addr;
6055e96a66cSDavid du Colombier 
6065e96a66cSDavid du Colombier 	addr = globalToLocal(score);
6075e96a66cSDavid du Colombier 	if(addr != NilBlock){
6085e96a66cSDavid du Colombier 		b = cacheLocalData(c, addr, type, tag, mode, 0);
6095e96a66cSDavid du Colombier 		if(b)
6105e96a66cSDavid du Colombier 			b->pc = getcallerpc(&c);
6115e96a66cSDavid du Colombier 		return b;
6125e96a66cSDavid du Colombier 	}
6135e96a66cSDavid du Colombier 
6145e96a66cSDavid du Colombier 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->hashSize;
6155e96a66cSDavid du Colombier 
6165e96a66cSDavid du Colombier 	/*
6175e96a66cSDavid du Colombier 	 * look for the block in the cache
6185e96a66cSDavid du Colombier 	 */
6195e96a66cSDavid du Colombier 	vtLock(c->lk);
6205e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
6215e96a66cSDavid du Colombier 		if(b->part != PartVenti || memcmp(b->score, score, VtScoreSize) != 0 || b->l.type != type)
6225e96a66cSDavid du Colombier 			continue;
6235e96a66cSDavid du Colombier 		heapDel(b);
6245e96a66cSDavid du Colombier 		b->ref++;
6255e96a66cSDavid du Colombier 		break;
6265e96a66cSDavid du Colombier 	}
6275e96a66cSDavid du Colombier 
6285e96a66cSDavid du Colombier 	if(b == nil){
6295e96a66cSDavid du Colombier if(0)fprint(2, "cacheGlobal %V %d\n", score, type);
6305e96a66cSDavid du Colombier 
6315e96a66cSDavid du Colombier 		b = cacheBumpBlock(c);
6325e96a66cSDavid du Colombier 
6335e96a66cSDavid du Colombier 		b->part = PartVenti;
6345e96a66cSDavid du Colombier 		b->addr = NilBlock;
6355e96a66cSDavid du Colombier 		b->l.type = type;
6365e96a66cSDavid du Colombier 		memmove(b->score, score, VtScoreSize);
6375e96a66cSDavid du Colombier 
6385e96a66cSDavid du Colombier 		/* chain onto correct hash */
6395e96a66cSDavid du Colombier 		b->next = c->heads[h];
6405e96a66cSDavid du Colombier 		c->heads[h] = b;
6415e96a66cSDavid du Colombier 		if(b->next != nil)
6425e96a66cSDavid du Colombier 			b->next->prev = &b->next;
6435e96a66cSDavid du Colombier 		b->prev = &c->heads[h];
6445e96a66cSDavid du Colombier 	}
6455e96a66cSDavid du Colombier 	vtUnlock(c->lk);
6465e96a66cSDavid du Colombier 
6475e96a66cSDavid du Colombier 	bwatchLock(b);
6485e96a66cSDavid du Colombier 	vtLock(b->lk);
6495e96a66cSDavid du Colombier 	b->nlock = 1;
6505e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
6515e96a66cSDavid du Colombier 
6525e96a66cSDavid du Colombier 	switch(b->iostate){
6535e96a66cSDavid du Colombier 	default:
6545e96a66cSDavid du Colombier 		abort();
6555e96a66cSDavid du Colombier 	case BioEmpty:
6565e96a66cSDavid du Colombier 		n = vtRead(c->z, score, vtType[type], b->data, c->size);
6575e96a66cSDavid du Colombier 		if(n < 0 || !vtSha1Check(score, b->data, n)){
6585e96a66cSDavid du Colombier 			blockSetIOState(b, BioVentiError);
6595e96a66cSDavid du Colombier 			blockPut(b);
6605e96a66cSDavid du Colombier 			return nil;
6615e96a66cSDavid du Colombier 		}
6625e96a66cSDavid du Colombier 		vtZeroExtend(vtType[type], b->data, n, c->size);
6635e96a66cSDavid du Colombier 		blockSetIOState(b, BioClean);
6645e96a66cSDavid du Colombier 		return b;
6655e96a66cSDavid du Colombier 	case BioClean:
6665e96a66cSDavid du Colombier 		return b;
6675e96a66cSDavid du Colombier 	case BioVentiError:
6685e96a66cSDavid du Colombier 	case BioReadError:
6695e96a66cSDavid du Colombier 		blockPut(b);
6705e96a66cSDavid du Colombier 		vtSetError(EIO);
6715e96a66cSDavid du Colombier 		blockSetIOState(b, BioEmpty);
6725e96a66cSDavid du Colombier 		return nil;
6735e96a66cSDavid du Colombier 	}
6745e96a66cSDavid du Colombier 	/* NOT REACHED */
6755e96a66cSDavid du Colombier }
6765e96a66cSDavid du Colombier 
6775e96a66cSDavid du Colombier /*
6785e96a66cSDavid du Colombier  * allocate a new on-disk block and load it into the memory cache.
6795e96a66cSDavid du Colombier  * BUG: if the disk is full, should we flush some of it to Venti?
6805e96a66cSDavid du Colombier  */
6815e96a66cSDavid du Colombier static u32int lastAlloc;
6825e96a66cSDavid du Colombier 
6835e96a66cSDavid du Colombier Block *
6845e96a66cSDavid du Colombier cacheAllocBlock(Cache *c, int type, u32int tag, u32int epoch, u32int epochLow)
6855e96a66cSDavid du Colombier {
6865e96a66cSDavid du Colombier 	FreeList *fl;
6875e96a66cSDavid du Colombier 	u32int addr;
6885e96a66cSDavid du Colombier 	Block *b;
6895e96a66cSDavid du Colombier 	int n, nwrap;
6905e96a66cSDavid du Colombier 	Label lab;
6915e96a66cSDavid du Colombier 
6925e96a66cSDavid du Colombier 	n = c->size / LabelSize;
6935e96a66cSDavid du Colombier 	fl = c->fl;
6945e96a66cSDavid du Colombier 
6955e96a66cSDavid du Colombier 	vtLock(fl->lk);
6965e96a66cSDavid du Colombier 	addr = fl->last;
6975e96a66cSDavid du Colombier 	b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
6985e96a66cSDavid du Colombier 	if(b == nil){
6995e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx %R\n");
7005e96a66cSDavid du Colombier 		vtUnlock(fl->lk);
7015e96a66cSDavid du Colombier 		return nil;
7025e96a66cSDavid du Colombier 	}
7035e96a66cSDavid du Colombier 	nwrap = 0;
7045e96a66cSDavid du Colombier 	for(;;){
7055e96a66cSDavid du Colombier 		if(++addr >= fl->end){
7065e96a66cSDavid du Colombier 			addr = 0;
7075e96a66cSDavid du Colombier 			fprint(2, "cacheAllocBlock wrap %d\n", fl->end);
7085e96a66cSDavid du Colombier 			if(++nwrap >= 2){
7095e96a66cSDavid du Colombier 				blockPut(b);
7105e96a66cSDavid du Colombier 				fl->last = 0;
7115e96a66cSDavid du Colombier 				vtSetError("disk is full");
7125e96a66cSDavid du Colombier 				fprint(2, "cacheAllocBlock: xxx1 %R\n");
7135e96a66cSDavid du Colombier 				vtUnlock(fl->lk);
7145e96a66cSDavid du Colombier 				return nil;
7155e96a66cSDavid du Colombier 			}
7165e96a66cSDavid du Colombier 		}
7175e96a66cSDavid du Colombier 		if(addr%n == 0){
7185e96a66cSDavid du Colombier 			blockPut(b);
7195e96a66cSDavid du Colombier 			b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
7205e96a66cSDavid du Colombier 			if(b == nil){
7215e96a66cSDavid du Colombier 				fl->last = addr;
7225e96a66cSDavid du Colombier 				fprint(2, "cacheAllocBlock: xxx2 %R\n");
7235e96a66cSDavid du Colombier 				vtUnlock(fl->lk);
7245e96a66cSDavid du Colombier 				return nil;
7255e96a66cSDavid du Colombier 			}
7265e96a66cSDavid du Colombier 		}
7275e96a66cSDavid du Colombier 		if(!labelUnpack(&lab, b->data, addr%n))
7285e96a66cSDavid du Colombier 			continue;
7295e96a66cSDavid du Colombier 		if(lab.state == BsFree)
7305e96a66cSDavid du Colombier 			goto Found;
7315e96a66cSDavid du Colombier 		if((lab.state&BsClosed) && lab.epochClose <= epochLow)
7325e96a66cSDavid du Colombier 			goto Found;
7335e96a66cSDavid du Colombier 	}
7345e96a66cSDavid du Colombier Found:
7355e96a66cSDavid du Colombier 	blockPut(b);
7365e96a66cSDavid du Colombier 	b = cacheLocal(c, PartData, addr, OOverWrite);
7375e96a66cSDavid du Colombier 	if(b == nil){
7385e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx3 %R\n");
7395e96a66cSDavid du Colombier 		return nil;
7405e96a66cSDavid du Colombier 	}
7415e96a66cSDavid du Colombier assert(b->iostate == BioLabel || b->iostate == BioClean);
7425e96a66cSDavid du Colombier 	fl->last = addr;
7435e96a66cSDavid du Colombier 	lab.type = type;
7445e96a66cSDavid du Colombier 	lab.tag = tag;
7455e96a66cSDavid du Colombier 	lab.state = BsAlloc;
7465e96a66cSDavid du Colombier 	lab.epoch = epoch;
7475e96a66cSDavid du Colombier 	lab.epochClose = ~(u32int)0;
7485e96a66cSDavid du Colombier 	if(!blockSetLabel(b, &lab)){
7495e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx4 %R\n");
7505e96a66cSDavid du Colombier 		blockPut(b);
7515e96a66cSDavid du Colombier 		return nil;
7525e96a66cSDavid du Colombier 	}
7535e96a66cSDavid du Colombier 	vtZeroExtend(vtType[type], b->data, 0, c->size);
7545e96a66cSDavid du Colombier if(0)diskWrite(c->disk, b);
7555e96a66cSDavid du Colombier 
7565e96a66cSDavid du Colombier if(0)fprint(2, "fsAlloc %ud type=%d tag = %ux\n", addr, type, tag);
7575e96a66cSDavid du Colombier 	lastAlloc = addr;
7587abd426fSDavid du Colombier 	fl->nused++;
7595e96a66cSDavid du Colombier 	vtUnlock(fl->lk);
7605e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
7615e96a66cSDavid du Colombier 	return b;
7625e96a66cSDavid du Colombier }
7635e96a66cSDavid du Colombier 
7647abd426fSDavid du Colombier void
7657abd426fSDavid du Colombier cacheCountUsed(Cache *c, u32int epochLow, u32int *used, u32int *total, u32int *bsize)
7667abd426fSDavid du Colombier {
7677abd426fSDavid du Colombier 	int n;
7687abd426fSDavid du Colombier 	u32int addr, nused;
7697abd426fSDavid du Colombier 	Block *b;
7707abd426fSDavid du Colombier 	Label lab;
7717abd426fSDavid du Colombier 	FreeList *fl;
7727abd426fSDavid du Colombier 
7737abd426fSDavid du Colombier 	fl = c->fl;
7747abd426fSDavid du Colombier 	n = c->size / LabelSize;
7757abd426fSDavid du Colombier 	*bsize = c->size;
7767abd426fSDavid du Colombier 	vtLock(fl->lk);
7777abd426fSDavid du Colombier 	if(fl->epochLow == epochLow){
7787abd426fSDavid du Colombier 		*used = fl->nused;
7797abd426fSDavid du Colombier 		*total = fl->end;
7807abd426fSDavid du Colombier 		vtUnlock(fl->lk);
7817abd426fSDavid du Colombier 		return;
7827abd426fSDavid du Colombier 	}
7837abd426fSDavid du Colombier 	b = nil;
7847abd426fSDavid du Colombier 	nused = 0;
7857abd426fSDavid du Colombier 	for(addr=0; addr<fl->end; addr++){
7867abd426fSDavid du Colombier 		if(addr%n == 0){
7877abd426fSDavid du Colombier 			blockPut(b);
7887abd426fSDavid du Colombier 			b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
7897abd426fSDavid du Colombier 			if(b == nil){
7907abd426fSDavid du Colombier 				fprint(2, "flCountUsed: loading %ux: %R\n", addr/n);
7917abd426fSDavid du Colombier 				break;
7927abd426fSDavid du Colombier 			}
7937abd426fSDavid du Colombier 		}
7947abd426fSDavid du Colombier 		if(!labelUnpack(&lab, b->data, addr%n))
7957abd426fSDavid du Colombier 			continue;
7967abd426fSDavid du Colombier 		if(lab.state == BsFree)
7977abd426fSDavid du Colombier 			continue;
7987abd426fSDavid du Colombier 		if((lab.state&BsClosed) && lab.epochClose <= epochLow)
7997abd426fSDavid du Colombier 			continue;
8007abd426fSDavid du Colombier 		nused++;
8017abd426fSDavid du Colombier 	}
8027abd426fSDavid du Colombier 	blockPut(b);
8037abd426fSDavid du Colombier 	if(addr == fl->end){
8047abd426fSDavid du Colombier 		fl->nused = nused;
8057abd426fSDavid du Colombier 		fl->epochLow = epochLow;
8067abd426fSDavid du Colombier 	}
8077abd426fSDavid du Colombier 	*used = nused;
8087abd426fSDavid du Colombier 	*total = fl->end;
8097abd426fSDavid du Colombier 	vtUnlock(fl->lk);
8107abd426fSDavid du Colombier 	return;
8117abd426fSDavid du Colombier }
8127abd426fSDavid du Colombier 
8135e96a66cSDavid du Colombier static FreeList *
8145e96a66cSDavid du Colombier flAlloc(u32int end)
8155e96a66cSDavid du Colombier {
8165e96a66cSDavid du Colombier 	FreeList *fl;
8175e96a66cSDavid du Colombier 
8185e96a66cSDavid du Colombier 	fl = vtMemAllocZ(sizeof(*fl));
8195e96a66cSDavid du Colombier 	fl->lk = vtLockAlloc();
820b5e190f4SDavid du Colombier 	fl->last = 0;
8215e96a66cSDavid du Colombier 	fl->end = end;
8225e96a66cSDavid du Colombier 	return fl;
8235e96a66cSDavid du Colombier }
8245e96a66cSDavid du Colombier 
8255e96a66cSDavid du Colombier static void
8265e96a66cSDavid du Colombier flFree(FreeList *fl)
8275e96a66cSDavid du Colombier {
8285e96a66cSDavid du Colombier 	vtLockFree(fl->lk);
8295e96a66cSDavid du Colombier 	vtMemFree(fl);
8305e96a66cSDavid du Colombier }
8315e96a66cSDavid du Colombier 
8325e96a66cSDavid du Colombier u32int
8335e96a66cSDavid du Colombier cacheLocalSize(Cache *c, int part)
8345e96a66cSDavid du Colombier {
8355e96a66cSDavid du Colombier 	return diskSize(c->disk, part);
8365e96a66cSDavid du Colombier }
8375e96a66cSDavid du Colombier 
8385e96a66cSDavid du Colombier /*
8395e96a66cSDavid du Colombier  * Copy on write.  Copied blocks have to be marked BaCopy.
8405e96a66cSDavid du Colombier  * See the big comment near blockRemoveLink.
8415e96a66cSDavid du Colombier  */
8425e96a66cSDavid du Colombier Block*
8435e96a66cSDavid du Colombier blockCopy(Block *b, u32int tag, u32int ehi, u32int elo)
8445e96a66cSDavid du Colombier {
8455e96a66cSDavid du Colombier 	Block *bb, *lb;
8465e96a66cSDavid du Colombier 	Label l;
8475e96a66cSDavid du Colombier 
8485e96a66cSDavid du Colombier 	assert((b->l.state&BsClosed)==0 && b->l.epoch < ehi);
8495e96a66cSDavid du Colombier 	bb = cacheAllocBlock(b->c, b->l.type, tag, ehi, elo);
8505e96a66cSDavid du Colombier 	if(bb == nil){
8515e96a66cSDavid du Colombier 		blockPut(b);
8525e96a66cSDavid du Colombier 		return nil;
8535e96a66cSDavid du Colombier 	}
8545e96a66cSDavid du Colombier 
8557abd426fSDavid du Colombier //fprint(2, "alloc %lux copy %V\n", bb->addr, b->score);
8565e96a66cSDavid du Colombier 	/*
8575e96a66cSDavid du Colombier 	 * Change label on b to mark that we've copied it.
8585e96a66cSDavid du Colombier 	 * This has to come after cacheAllocBlock, since we
8595e96a66cSDavid du Colombier 	 * can't hold any labels blocks (lb) while we try to
8605e96a66cSDavid du Colombier 	 * fetch others (in cacheAllocBlock).
8615e96a66cSDavid du Colombier 	 */
8625e96a66cSDavid du Colombier 	if(!(b->l.state&BsCopied) && b->part==PartData){
8635e96a66cSDavid du Colombier 		l = b->l;
8645e96a66cSDavid du Colombier 		l.state |= BsCopied;
8655e96a66cSDavid du Colombier 		lb = _blockSetLabel(b, &l);
8665e96a66cSDavid du Colombier 		if(lb == nil){
8675e96a66cSDavid du Colombier 			/* can't set label => can't copy block */
8685e96a66cSDavid du Colombier 			blockPut(b);
8695e96a66cSDavid du Colombier 			l.type = BtMax;
8705e96a66cSDavid du Colombier 			l.state = BsFree;
8715e96a66cSDavid du Colombier 			l.epoch = 0;
8725e96a66cSDavid du Colombier 			l.epochClose = 0;
8735e96a66cSDavid du Colombier 			l.tag = 0;
8745e96a66cSDavid du Colombier 			/* ignore error: block gets lost on error */
8755e96a66cSDavid du Colombier 			blockSetLabel(bb, &l);
8765e96a66cSDavid du Colombier 			blockPut(bb);
8775e96a66cSDavid du Colombier 			return nil;
8785e96a66cSDavid du Colombier 		}
87961201b97SDavid du Colombier 		blockDependency(bb, lb, -1, nil, nil);
8805e96a66cSDavid du Colombier 		blockPut(lb);
8815e96a66cSDavid du Colombier 	}
8825e96a66cSDavid du Colombier 
8835e96a66cSDavid du Colombier 	if(0){
8845e96a66cSDavid du Colombier 		if(b->addr != NilBlock)
8855e96a66cSDavid du Colombier 			fprint(2, "blockCopy %#ux/%ud => %#ux/%ud\n",
8865e96a66cSDavid du Colombier 				b->addr, b->l.epoch, bb->addr, bb->l.epoch);
8875e96a66cSDavid du Colombier 		else if(memcmp(b->score, vtZeroScore, VtScoreSize) != 0)
8885e96a66cSDavid du Colombier 			fprint(2, "blockCopy %V => %#ux/%ud\n",
8895e96a66cSDavid du Colombier 				b->score, bb->addr, bb->l.epoch);
8905e96a66cSDavid du Colombier 	}
8915e96a66cSDavid du Colombier 
8925e96a66cSDavid du Colombier 	memmove(bb->data, b->data, b->c->size);
8935e96a66cSDavid du Colombier 	blockDirty(bb);
8945e96a66cSDavid du Colombier 	blockPut(b);
8955e96a66cSDavid du Colombier 	return bb;
8965e96a66cSDavid du Colombier }
8975e96a66cSDavid du Colombier 
8985e96a66cSDavid du Colombier /*
8995e96a66cSDavid du Colombier  * The thread that has locked b may refer to it by
9005e96a66cSDavid du Colombier  * multiple names.  Nlock counts the number of
9015e96a66cSDavid du Colombier  * references the locking thread holds.  It will call
9025e96a66cSDavid du Colombier  * blockPut once per reference.
9035e96a66cSDavid du Colombier  */
9045e96a66cSDavid du Colombier void
9055e96a66cSDavid du Colombier blockDupLock(Block *b)
9065e96a66cSDavid du Colombier {
9075e96a66cSDavid du Colombier 	assert(b->nlock > 0);
9085e96a66cSDavid du Colombier 	b->nlock++;
9095e96a66cSDavid du Colombier }
9105e96a66cSDavid du Colombier 
9115e96a66cSDavid du Colombier /*
9125e96a66cSDavid du Colombier  * we're done with the block.
9135e96a66cSDavid du Colombier  * unlock it.  can't use it after calling this.
9145e96a66cSDavid du Colombier  */
9155e96a66cSDavid du Colombier void
9165e96a66cSDavid du Colombier blockPut(Block* b)
9175e96a66cSDavid du Colombier {
9185e96a66cSDavid du Colombier 	Cache *c;
9195e96a66cSDavid du Colombier 
9205e96a66cSDavid du Colombier 	if(b == nil)
9215e96a66cSDavid du Colombier 		return;
9225e96a66cSDavid du Colombier 
9235e96a66cSDavid du Colombier if(0)fprint(2, "blockPut: %d: %d %x %d %s\n", getpid(), b->part, b->addr, c->nheap, bioStr(b->iostate));
9245e96a66cSDavid du Colombier 
9255e96a66cSDavid du Colombier 	if(b->iostate == BioDirty)
9265e96a66cSDavid du Colombier 		bwatchDependency(b);
9275e96a66cSDavid du Colombier 
9285e96a66cSDavid du Colombier 	if(--b->nlock > 0)
9295e96a66cSDavid du Colombier 		return;
9305e96a66cSDavid du Colombier 
9315e96a66cSDavid du Colombier 	/*
9325e96a66cSDavid du Colombier 	 * b->nlock should probably stay at zero while
9335e96a66cSDavid du Colombier 	 * the block is unlocked, but diskThread and vtSleep
9345e96a66cSDavid du Colombier 	 * conspire to assume that they can just vtLock(b->lk); blockPut(b),
9355e96a66cSDavid du Colombier 	 * so we have to keep b->nlock set to 1 even
9365e96a66cSDavid du Colombier 	 * when the block is unlocked.
9375e96a66cSDavid du Colombier 	 */
9385e96a66cSDavid du Colombier 	assert(b->nlock == 0);
9395e96a66cSDavid du Colombier 	b->nlock = 1;
9405e96a66cSDavid du Colombier //	b->pc = 0;
9415e96a66cSDavid du Colombier 
9425e96a66cSDavid du Colombier 	bwatchUnlock(b);
9435e96a66cSDavid du Colombier 	vtUnlock(b->lk);
9445e96a66cSDavid du Colombier 	c = b->c;
9455e96a66cSDavid du Colombier 	vtLock(c->lk);
9465e96a66cSDavid du Colombier 
9475e96a66cSDavid du Colombier 	if(--b->ref > 0){
9485e96a66cSDavid du Colombier 		vtUnlock(c->lk);
9495e96a66cSDavid du Colombier 		return;
9505e96a66cSDavid du Colombier 	}
9515e96a66cSDavid du Colombier 
9525e96a66cSDavid du Colombier 	assert(b->ref == 0);
9535e96a66cSDavid du Colombier 	switch(b->iostate){
9545e96a66cSDavid du Colombier 	default:
9555e96a66cSDavid du Colombier 		b->used = c->now++;
9565e96a66cSDavid du Colombier 		heapIns(b);
9575e96a66cSDavid du Colombier 		break;
9585e96a66cSDavid du Colombier 	case BioEmpty:
9595e96a66cSDavid du Colombier 	case BioLabel:
9605e96a66cSDavid du Colombier 		if(c->nheap == 0)
9615e96a66cSDavid du Colombier 			b->used = c->now++;
9625e96a66cSDavid du Colombier 		else
9635e96a66cSDavid du Colombier 			b->used = c->heap[0]->used;
9645e96a66cSDavid du Colombier 		heapIns(b);
9655e96a66cSDavid du Colombier 		break;
9665e96a66cSDavid du Colombier 	case BioDirty:
9675e96a66cSDavid du Colombier 		break;
9685e96a66cSDavid du Colombier 	}
9695e96a66cSDavid du Colombier 	vtUnlock(c->lk);
9705e96a66cSDavid du Colombier }
9715e96a66cSDavid du Colombier 
9725e96a66cSDavid du Colombier /*
9735e96a66cSDavid du Colombier  * we're deleting a block; delete all the blocks it points to
9745e96a66cSDavid du Colombier  * that are still active (i.e., not needed by snapshots).
9755e96a66cSDavid du Colombier  */
9765e96a66cSDavid du Colombier static void
9775e96a66cSDavid du Colombier blockCleanup(Block *b, u32int epoch)
9785e96a66cSDavid du Colombier {
9795e96a66cSDavid du Colombier 	Cache *c;
9805e96a66cSDavid du Colombier 	Block *bb;
9815e96a66cSDavid du Colombier 	int i, n;
9825e96a66cSDavid du Colombier 	Label l;
9835e96a66cSDavid du Colombier 	u32int a;
9845e96a66cSDavid du Colombier 	int type;
9855e96a66cSDavid du Colombier 	int mode;
9865e96a66cSDavid du Colombier 
9875e96a66cSDavid du Colombier 	type = b->l.type;
9885e96a66cSDavid du Colombier 	c = b->c;
9895e96a66cSDavid du Colombier 
9905e96a66cSDavid du Colombier 	bwatchReset(b->score);
9915e96a66cSDavid du Colombier 
9925e96a66cSDavid du Colombier 	blockSetIOState(b, BioClean);
9935e96a66cSDavid du Colombier 
9945e96a66cSDavid du Colombier 	/* do not recursively free directories */
9955e96a66cSDavid du Colombier 	if(type == BtData || type == BtDir)
9965e96a66cSDavid du Colombier 		return;
9975e96a66cSDavid du Colombier 
9985e96a66cSDavid du Colombier 	n = c->size / VtScoreSize;
9995e96a66cSDavid du Colombier 	mode = OReadWrite;
10005e96a66cSDavid du Colombier 	if(type-1 == BtData || type-1 == BtDir)
10015e96a66cSDavid du Colombier 		mode = OOverWrite;
10025e96a66cSDavid du Colombier 	for(i=0; i<n; i++){
10035e96a66cSDavid du Colombier 		a = globalToLocal(b->data + i*VtScoreSize);
10045e96a66cSDavid du Colombier 		if(a == NilBlock || !readLabel(c, &l, a))
10055e96a66cSDavid du Colombier 			continue;
10065e96a66cSDavid du Colombier 		if((l.state&BsClosed) || l.epoch != epoch)
10075e96a66cSDavid du Colombier 			continue;
10085e96a66cSDavid du Colombier 		bb = cacheLocalData(c, a, type-1, b->l.tag, mode, 0);
10095e96a66cSDavid du Colombier 		if(bb == nil)
10105e96a66cSDavid du Colombier 			continue;
10115e96a66cSDavid du Colombier 		if((bb->l.state&BsClosed) || bb->l.epoch != epoch){
10125e96a66cSDavid du Colombier 			fprint(2, "cleanupBlock: block %ud changed underfoot! expected %L got %L\n",
10135e96a66cSDavid du Colombier 				a, &l, &bb->l);
10145e96a66cSDavid du Colombier 			blockPut(bb);
10155e96a66cSDavid du Colombier 			continue;
10165e96a66cSDavid du Colombier 		}
10175e96a66cSDavid du Colombier 		blockCleanup(bb, epoch);
10185e96a66cSDavid du Colombier 		l.type = BtMax;
10195e96a66cSDavid du Colombier 		l.epoch = epoch;
10205e96a66cSDavid du Colombier 		l.epochClose = 0;
10215e96a66cSDavid du Colombier 		l.state = BsFree;
10225e96a66cSDavid du Colombier 		l.tag = 0;
10235e96a66cSDavid du Colombier 		blockSetLabel(bb, &l);
10245e96a66cSDavid du Colombier 		blockPut(bb);
10255e96a66cSDavid du Colombier 	}
10265e96a66cSDavid du Colombier }
10275e96a66cSDavid du Colombier 
10285e96a66cSDavid du Colombier /*
10295e96a66cSDavid du Colombier  * We don't need the block at addr anymore for the active file system.
10305e96a66cSDavid du Colombier  * If we don't need it for the snapshots, remove it completely.
10315e96a66cSDavid du Colombier  * Epoch is the epoch during which we got rid of the block.
10325e96a66cSDavid du Colombier  * See blockRemoveLink for more.
10335e96a66cSDavid du Colombier  */
10345e96a66cSDavid du Colombier static int
10355e96a66cSDavid du Colombier unlinkBlock(Cache *c, u32int addr, int type, u32int tag, u32int epoch)
10365e96a66cSDavid du Colombier {
10375e96a66cSDavid du Colombier 	Block *b;
10385e96a66cSDavid du Colombier 	Label l;
10395e96a66cSDavid du Colombier 
10405e96a66cSDavid du Colombier 	if(addr == NilBlock)
10415e96a66cSDavid du Colombier 		return 1;
10425e96a66cSDavid du Colombier 
10435e96a66cSDavid du Colombier //fprint(2, "unlinkBlock %#ux\n", addr);
10445e96a66cSDavid du Colombier 	b = cacheLocalData(c, addr, type, tag, OReadOnly, 0);
10455e96a66cSDavid du Colombier 	if(b == nil)
10465e96a66cSDavid du Colombier 		return 0;
10475e96a66cSDavid du Colombier 	if(b->l.epoch > epoch){
10485e96a66cSDavid du Colombier fprint(2, "unlinkBlock: strange epoch :%ud %ud\n", b->l.epoch, epoch);
10495e96a66cSDavid du Colombier 		blockPut(b);
10505e96a66cSDavid du Colombier 		return 0;
10515e96a66cSDavid du Colombier 	}
10525e96a66cSDavid du Colombier 
10535e96a66cSDavid du Colombier 	l = b->l;
10545e96a66cSDavid du Colombier 	if((b->l.state&BsClosed)==0 && b->l.epoch==epoch){
10555e96a66cSDavid du Colombier 		l.state = BsFree;
10565e96a66cSDavid du Colombier 		l.type = BtMax;
10575e96a66cSDavid du Colombier 		l.tag = 0;
10585e96a66cSDavid du Colombier 		l.epoch = 0;
10595e96a66cSDavid du Colombier 		l.epochClose = 0;
10605e96a66cSDavid du Colombier 		blockCleanup(b, epoch);
10615e96a66cSDavid du Colombier 	}else{
10625e96a66cSDavid du Colombier 		l.state |= BsClosed;
10635e96a66cSDavid du Colombier 		l.epochClose = epoch;
10645e96a66cSDavid du Colombier 	}
10655e96a66cSDavid du Colombier 	blockSetLabel(b, &l);
10665e96a66cSDavid du Colombier 	blockPut(b);
10675e96a66cSDavid du Colombier 	return 1;
10685e96a66cSDavid du Colombier }
10695e96a66cSDavid du Colombier 
10705e96a66cSDavid du Colombier /*
10715e96a66cSDavid du Colombier  * try to allocate a BList so we can record that b must
10725e96a66cSDavid du Colombier  * be written out before some other block.
10735e96a66cSDavid du Colombier  * if can't find a BList, write b out instead and return nil.
10745e96a66cSDavid du Colombier  */
10755e96a66cSDavid du Colombier static BList *
10765e96a66cSDavid du Colombier blistAlloc(Block *b)
10775e96a66cSDavid du Colombier {
10785e96a66cSDavid du Colombier 	Cache *c;
10795e96a66cSDavid du Colombier 	BList *p;
10805e96a66cSDavid du Colombier 
10815e96a66cSDavid du Colombier 	/*
10825e96a66cSDavid du Colombier 	 * It's possible that when we marked b dirty, there were
10835e96a66cSDavid du Colombier 	 * too many dirty blocks so we just wrote b there and then.
10845e96a66cSDavid du Colombier 	 * So b might not be dirty.  If it's not, no need to worry
10855e96a66cSDavid du Colombier 	 * about recording the write constraint.
10865e96a66cSDavid du Colombier 	 *
10875e96a66cSDavid du Colombier 	 * BlockRemoveLink depends on the fact that if blistAlloc
10885e96a66cSDavid du Colombier 	 * returns non-nil, b really is dirty.
10895e96a66cSDavid du Colombier 	 */
10905e96a66cSDavid du Colombier 	if(b->iostate != BioDirty){
10915e96a66cSDavid du Colombier 		assert(b->iostate == BioClean);
10925e96a66cSDavid du Colombier 		return nil;
10935e96a66cSDavid du Colombier 	}
10945e96a66cSDavid du Colombier 
10955e96a66cSDavid du Colombier 	/*
10965e96a66cSDavid du Colombier 	 * Easy: maybe there's a free list left.
10975e96a66cSDavid du Colombier 	 */
10985e96a66cSDavid du Colombier 	c = b->c;
10995e96a66cSDavid du Colombier 	vtLock(c->lk);
11005e96a66cSDavid du Colombier 	if(c->blfree){
11015e96a66cSDavid du Colombier 	HaveBlFree:
11025e96a66cSDavid du Colombier 		p = c->blfree;
11035e96a66cSDavid du Colombier 		c->blfree = p->next;
11045e96a66cSDavid du Colombier 		vtUnlock(c->lk);
11055e96a66cSDavid du Colombier 		return p;
11065e96a66cSDavid du Colombier 	}
11075e96a66cSDavid du Colombier 	vtUnlock(c->lk);
11085e96a66cSDavid du Colombier 
11095e96a66cSDavid du Colombier 	/*
11105e96a66cSDavid du Colombier 	 * No free BLists.  What are our options?
11115e96a66cSDavid du Colombier 	 */
11125e96a66cSDavid du Colombier 
11135e96a66cSDavid du Colombier 	/* Block has no priors? Just write it. */
11145e96a66cSDavid du Colombier 	if(b->prior == nil){
11155e96a66cSDavid du Colombier 		diskWrite(c->disk, b);
11165e96a66cSDavid du Colombier 		while(b->iostate != BioClean)
11175e96a66cSDavid du Colombier 			vtSleep(b->ioready);
11185e96a66cSDavid du Colombier 		return nil;
11195e96a66cSDavid du Colombier 	}
11205e96a66cSDavid du Colombier 
11215e96a66cSDavid du Colombier 	/*
11225e96a66cSDavid du Colombier 	 * Wake the flush thread, which will hopefully free up
11235e96a66cSDavid du Colombier 	 * some BLists for us.  We used to flush a block from
11245e96a66cSDavid du Colombier 	 * our own prior list and reclaim that BList, but this is
11255e96a66cSDavid du Colombier 	 * a no-no: some of the blocks on our prior list may
11265e96a66cSDavid du Colombier 	 * be locked by our caller.  Or maybe their label blocks
11275e96a66cSDavid du Colombier 	 * are locked by our caller.  In any event, it's too hard
11285e96a66cSDavid du Colombier 	 * to make sure we can do I/O for ourselves.  Instead,
11295e96a66cSDavid du Colombier 	 * we assume the flush thread will find something.
11305e96a66cSDavid du Colombier 	 * (The flush thread never blocks waiting for a block,
11315e96a66cSDavid du Colombier 	 * so it won't deadlock like we will.)
11325e96a66cSDavid du Colombier 	 */
11335e96a66cSDavid du Colombier 	vtLock(c->lk);
11345e96a66cSDavid du Colombier 	while(c->blfree == nil){
11355e96a66cSDavid du Colombier 		vtWakeup(c->flush);
11365e96a66cSDavid du Colombier 		vtSleep(c->blrend);
11375e96a66cSDavid du Colombier 	}
11385e96a66cSDavid du Colombier 	goto HaveBlFree;
11395e96a66cSDavid du Colombier }
11405e96a66cSDavid du Colombier 
11415e96a66cSDavid du Colombier void
11425e96a66cSDavid du Colombier blistFree(Cache *c, BList *bl)
11435e96a66cSDavid du Colombier {
11445e96a66cSDavid du Colombier 	vtLock(c->lk);
11455e96a66cSDavid du Colombier 	bl->next = c->blfree;
11465e96a66cSDavid du Colombier 	c->blfree = bl;
11475e96a66cSDavid du Colombier 	vtWakeup(c->blrend);
11485e96a66cSDavid du Colombier 	vtUnlock(c->lk);
11495e96a66cSDavid du Colombier }
11505e96a66cSDavid du Colombier 
11515e96a66cSDavid du Colombier /*
11525e96a66cSDavid du Colombier  * Flush b or one of the blocks it depends on.
11535e96a66cSDavid du Colombier  */
11545e96a66cSDavid du Colombier void
11555e96a66cSDavid du Colombier blockFlush(Block *b)
11565e96a66cSDavid du Colombier {
11575e96a66cSDavid du Colombier 	int first, nlock;
11585e96a66cSDavid du Colombier 	BList *p, **pp;
11595e96a66cSDavid du Colombier 	Block *bb;
11605e96a66cSDavid du Colombier 	Cache *c;
11615e96a66cSDavid du Colombier 
11625e96a66cSDavid du Colombier //fprint(2, "blockFlush %p\n", b);
11635e96a66cSDavid du Colombier 
11645e96a66cSDavid du Colombier 	c = b->c;
11655e96a66cSDavid du Colombier 
11665e96a66cSDavid du Colombier 	first = 1;
11675e96a66cSDavid du Colombier 	pp = &b->prior;
11685e96a66cSDavid du Colombier 	for(p=*pp; p; p=*pp){
11695e96a66cSDavid du Colombier 		bb = cacheLocalLookup(c, p->part, p->addr, p->vers);
11705e96a66cSDavid du Colombier 		if(bb == nil){
11715e96a66cSDavid du Colombier 			*pp = p->next;
11725e96a66cSDavid du Colombier 			blistFree(c, p);
11735e96a66cSDavid du Colombier 			continue;
11745e96a66cSDavid du Colombier 		}
11755e96a66cSDavid du Colombier 		if(!first)
11765e96a66cSDavid du Colombier 			blockPut(b);
11775e96a66cSDavid du Colombier 		first = 0;
11785e96a66cSDavid du Colombier 		b = bb;
11795e96a66cSDavid du Colombier 		pp = &b->prior;
11805e96a66cSDavid du Colombier 	}
11815e96a66cSDavid du Colombier 
11825e96a66cSDavid du Colombier 	/*
11835e96a66cSDavid du Colombier 	 * If b->nlock > 1, the block is aliased within
11845e96a66cSDavid du Colombier 	 * a single thread.  That thread is us, and it's
11855e96a66cSDavid du Colombier 	 * the block that was passed in (rather than a prior).
11865e96a66cSDavid du Colombier 	 * DiskWrite does some funny stuff with VtLock
11875e96a66cSDavid du Colombier 	 * and blockPut that basically assumes b->nlock==1.
11885e96a66cSDavid du Colombier 	 * We humor diskWrite by temporarily setting
11895e96a66cSDavid du Colombier 	 * nlock to 1.  This needs to be revisited.  (TODO)
11905e96a66cSDavid du Colombier 	 */
11915e96a66cSDavid du Colombier 	nlock = b->nlock;
11925e96a66cSDavid du Colombier 	if(nlock > 1){
11935e96a66cSDavid du Colombier 		assert(first);
11945e96a66cSDavid du Colombier 		b->nlock = 1;
11955e96a66cSDavid du Colombier 	}
11965e96a66cSDavid du Colombier 	diskWrite(c->disk, b);
11975e96a66cSDavid du Colombier 	while(b->iostate != BioClean)
11985e96a66cSDavid du Colombier 		vtSleep(b->ioready);
11995e96a66cSDavid du Colombier 	b->nlock = nlock;
12005e96a66cSDavid du Colombier 	if(!first)
12015e96a66cSDavid du Colombier 		blockPut(b);
12025e96a66cSDavid du Colombier }
12035e96a66cSDavid du Colombier 
12045e96a66cSDavid du Colombier /*
120561201b97SDavid du Colombier  * Record that bb must be written out before b.
120661201b97SDavid du Colombier  * If index is given, we're about to overwrite the score/e
120761201b97SDavid du Colombier  * at that index in the block.  Save the old value so we
12085e96a66cSDavid du Colombier  * can write a safer ``old'' version of the block if pressed.
12095e96a66cSDavid du Colombier  */
12105e96a66cSDavid du Colombier void
121161201b97SDavid du Colombier blockDependency(Block *b, Block *bb, int index, uchar *score, Entry *e)
12125e96a66cSDavid du Colombier {
12135e96a66cSDavid du Colombier 	BList *p;
12145e96a66cSDavid du Colombier 
12155e96a66cSDavid du Colombier 	if(bb->iostate == BioClean)
12165e96a66cSDavid du Colombier 		return;
12175e96a66cSDavid du Colombier 
121861201b97SDavid du Colombier 	/*
121961201b97SDavid du Colombier 	 * Dependencies for blocks containing Entry structures
122061201b97SDavid du Colombier 	 * or scores must always be explained.  The problem with
122161201b97SDavid du Colombier 	 * only explaining some of them is this.  Suppose we have two
122261201b97SDavid du Colombier 	 * dependencies for the same field, the first explained
122361201b97SDavid du Colombier 	 * and the second not.  We try to write the block when the first
122461201b97SDavid du Colombier 	 * dependency is not written but the second is.  We will roll back
122561201b97SDavid du Colombier 	 * the first change even though the second trumps it.
122661201b97SDavid du Colombier 	 */
122761201b97SDavid du Colombier 	if(index == -1 && bb->part == PartData)
122861201b97SDavid du Colombier 		assert(b->l.type == BtData);
122961201b97SDavid du Colombier 
12307abd426fSDavid du Colombier 	if(bb->iostate != BioDirty){
12317abd426fSDavid du Colombier 		fprint(2, "%d:%x:%d iostate is %d in blockDependency\n",
12327abd426fSDavid du Colombier 			bb->part, bb->addr, bb->l.type, bb->iostate);
12337abd426fSDavid du Colombier 		abort();
12347abd426fSDavid du Colombier 	}
12355e96a66cSDavid du Colombier 
12365e96a66cSDavid du Colombier 	p = blistAlloc(bb);
12375e96a66cSDavid du Colombier 	if(p == nil)
12385e96a66cSDavid du Colombier 		return;
12395e96a66cSDavid du Colombier 
12405e96a66cSDavid du Colombier if(0)fprint(2, "%d:%x:%d depends on %d:%x:%d\n", b->part, b->addr, b->l.type, bb->part, bb->addr, bb->l.type);
12415e96a66cSDavid du Colombier 
12425e96a66cSDavid du Colombier 	p->part = bb->part;
12435e96a66cSDavid du Colombier 	p->addr = bb->addr;
12445e96a66cSDavid du Colombier 	p->type = bb->l.type;
12455e96a66cSDavid du Colombier 	p->vers = bb->vers;
12465e96a66cSDavid du Colombier 	p->index = index;
124761201b97SDavid du Colombier 	if(p->index >= 0){
124861201b97SDavid du Colombier 		/*
124961201b97SDavid du Colombier 		 * This test would just be b->l.type==BtDir except
125061201b97SDavid du Colombier 		 * we need to exclude the super block.
125161201b97SDavid du Colombier 		 */
125261201b97SDavid du Colombier 		if(b->l.type == BtDir && b->part == PartData)
125361201b97SDavid du Colombier 			entryPack(e, p->old.entry, 0);
125461201b97SDavid du Colombier 		else
125561201b97SDavid du Colombier 			memmove(p->old.score, score, VtScoreSize);
125661201b97SDavid du Colombier 	}
12575e96a66cSDavid du Colombier 	p->next = b->prior;
12585e96a66cSDavid du Colombier 	b->prior = p;
12595e96a66cSDavid du Colombier }
12605e96a66cSDavid du Colombier 
12615e96a66cSDavid du Colombier /*
12625e96a66cSDavid du Colombier  * Mark an in-memory block as dirty.  If there are too many
12635e96a66cSDavid du Colombier  * dirty blocks, start writing some out to disk.  If there are way
12645e96a66cSDavid du Colombier  * too many dirty blocks, write this one out too.
12655e96a66cSDavid du Colombier  *
12665e96a66cSDavid du Colombier  * Note that since we might call blockFlush, which walks
12675e96a66cSDavid du Colombier  * the prior list, we can't call blockDirty while holding a lock
12685e96a66cSDavid du Colombier  * on any of our priors.  This can be tested by recompiling
12695e96a66cSDavid du Colombier  * with flush always set to 1 below.
12705e96a66cSDavid du Colombier  */
12715e96a66cSDavid du Colombier int
12725e96a66cSDavid du Colombier blockDirty(Block *b)
12735e96a66cSDavid du Colombier {
12745e96a66cSDavid du Colombier 	Cache *c;
12755e96a66cSDavid du Colombier 	int flush;
12765e96a66cSDavid du Colombier 
12775e96a66cSDavid du Colombier 	c = b->c;
12785e96a66cSDavid du Colombier 
12795e96a66cSDavid du Colombier 	assert(b->part != PartVenti);
12805e96a66cSDavid du Colombier 
12815e96a66cSDavid du Colombier 	if(b->iostate == BioDirty)
12825e96a66cSDavid du Colombier 		return 1;
12835e96a66cSDavid du Colombier 	assert(b->iostate == BioClean);
12845e96a66cSDavid du Colombier 
12855e96a66cSDavid du Colombier 	vtLock(c->lk);
128661201b97SDavid du Colombier 	b->iostate = BioDirty;
12875e96a66cSDavid du Colombier 	c->ndirty++;
12885e96a66cSDavid du Colombier 	if(c->ndirty > (c->maxdirty>>1))
12895e96a66cSDavid du Colombier 		vtWakeup(c->flush);
12905e96a66cSDavid du Colombier 	flush = c->ndirty > c->maxdirty;
12915e96a66cSDavid du Colombier 	vtUnlock(c->lk);
12925e96a66cSDavid du Colombier 
12935e96a66cSDavid du Colombier 	if(flush)
12945e96a66cSDavid du Colombier 		blockFlush(b);
12955e96a66cSDavid du Colombier 
12965e96a66cSDavid du Colombier 	return 1;
12975e96a66cSDavid du Colombier }
12985e96a66cSDavid du Colombier 
12995e96a66cSDavid du Colombier /*
13005e96a66cSDavid du Colombier  * Block b once pointed at the block bb at addr/type/tag, but no longer does.
13015e96a66cSDavid du Colombier  *
13025e96a66cSDavid du Colombier  * The file system maintains the following invariants (i-iv checked by flchk):
13035e96a66cSDavid du Colombier  *
13045e96a66cSDavid du Colombier  * (i) b.e in [bb.e, bb.eClose)
13055e96a66cSDavid du Colombier  * (ii) if b.e==bb.e,  then no other b' in e points at bb.
13065e96a66cSDavid du Colombier  * (iii) if !(b.state&Copied) and b.e==bb.e then no other b' points at bb.
13075e96a66cSDavid du Colombier  * (iv) if b is active then no other active b' points at bb.
13085e96a66cSDavid du Colombier  * (v) if b is a past life of b' then only one of b and b' is active (too hard to check)
13095e96a66cSDavid du Colombier  *
13105e96a66cSDavid du Colombier  * The file system initially satisfies these invariants, and we can verify that
13115e96a66cSDavid du Colombier  * the various file system operations maintain them.  See fossil.invariants.
13125e96a66cSDavid du Colombier  *
13135e96a66cSDavid du Colombier  * Condition (i) lets us reclaim blocks once the low epoch is greater
13145e96a66cSDavid du Colombier  * than epochClose.
13155e96a66cSDavid du Colombier  *
13165e96a66cSDavid du Colombier  * If the condition in (iii) is satisfied, then this is the only pointer to bb,
13175e96a66cSDavid du Colombier  * so bb can be reclaimed once b has been written to disk.  blockRemoveLink
13185e96a66cSDavid du Colombier  * checks !(b.state&Copied) as an optimization.  UnlinkBlock and blockCleanup
13195e96a66cSDavid du Colombier  * will check the conditions again for each block they consider.
13205e96a66cSDavid du Colombier  */
13215e96a66cSDavid du Colombier int
13225e96a66cSDavid du Colombier blockRemoveLink(Block *b, u32int addr, int type, u32int tag)
13235e96a66cSDavid du Colombier {
13245e96a66cSDavid du Colombier 	BList *bl;
13255e96a66cSDavid du Colombier 	BList *p, **pp;
13265e96a66cSDavid du Colombier 	Cache *c;
13275e96a66cSDavid du Colombier 
13285e96a66cSDavid du Colombier 	c = b->c;
13295e96a66cSDavid du Colombier 
13305e96a66cSDavid du Colombier 	/* remove unlinked block from prior list */
13315e96a66cSDavid du Colombier 	pp = &b->prior;
13325e96a66cSDavid du Colombier 	for(p=*pp; p; p=*pp){
13335e96a66cSDavid du Colombier 		if(p->part != PartData || p->addr != addr){
13345e96a66cSDavid du Colombier 			pp = &p->next;
13355e96a66cSDavid du Colombier 			continue;
13365e96a66cSDavid du Colombier 		}
13375e96a66cSDavid du Colombier 		*pp = p->next;
13385e96a66cSDavid du Colombier 		blistFree(c, p);
13395e96a66cSDavid du Colombier 	}
13405e96a66cSDavid du Colombier 
13415e96a66cSDavid du Colombier 	/* if b has been copied, can't reclaim blocks it points at. */
13425e96a66cSDavid du Colombier 	if(b->l.state & BsCopied)
13435e96a66cSDavid du Colombier 		return 0;
13445e96a66cSDavid du Colombier 
13455e96a66cSDavid du Colombier 	bl = blistAlloc(b);
13465e96a66cSDavid du Colombier 	if(bl == nil)
13475e96a66cSDavid du Colombier 		return unlinkBlock(b->c, addr, type, tag, b->l.epoch);
13485e96a66cSDavid du Colombier 
13495e96a66cSDavid du Colombier 	/*
13505e96a66cSDavid du Colombier 	 * Because bl != nil, we know b is dirty.
13515e96a66cSDavid du Colombier 	 * (Linking b->uhead onto a clean block is
13525e96a66cSDavid du Colombier 	 * counterproductive, since we only look at
13535e96a66cSDavid du Colombier 	 * b->uhead when a block transitions from
13545e96a66cSDavid du Colombier 	 * dirty to clean.)
13555e96a66cSDavid du Colombier 	 */
13565e96a66cSDavid du Colombier 	assert(b->iostate == BioDirty);
13575e96a66cSDavid du Colombier 
13585e96a66cSDavid du Colombier 	bl->part = PartData;
13595e96a66cSDavid du Colombier 	bl->addr = addr;
13605e96a66cSDavid du Colombier 	bl->type = type;
13615e96a66cSDavid du Colombier 	bl->tag = tag;
13625e96a66cSDavid du Colombier 	bl->epoch = b->l.epoch;
13635e96a66cSDavid du Colombier 	if(b->uhead == nil)
13645e96a66cSDavid du Colombier 		b->uhead = bl;
13655e96a66cSDavid du Colombier 	else
13665e96a66cSDavid du Colombier 		b->utail->next = bl;
13675e96a66cSDavid du Colombier 	b->utail = bl;
13685e96a66cSDavid du Colombier 	bl->next = nil;
13695e96a66cSDavid du Colombier 	return 1;
13705e96a66cSDavid du Colombier }
13715e96a66cSDavid du Colombier 
13725e96a66cSDavid du Colombier /*
13735e96a66cSDavid du Colombier  * set the label associated with a block.
13745e96a66cSDavid du Colombier  */
13755e96a66cSDavid du Colombier Block*
13765e96a66cSDavid du Colombier _blockSetLabel(Block *b, Label *l)
13775e96a66cSDavid du Colombier {
13785e96a66cSDavid du Colombier 	int lpb;
13795e96a66cSDavid du Colombier 	Block *bb;
13805e96a66cSDavid du Colombier 	u32int a;
13815e96a66cSDavid du Colombier 	Cache *c;
13825e96a66cSDavid du Colombier 
13835e96a66cSDavid du Colombier 	c = b->c;
13845e96a66cSDavid du Colombier 
13855e96a66cSDavid du Colombier 	assert(b->part == PartData);
13865e96a66cSDavid du Colombier 	assert(b->iostate == BioLabel || b->iostate == BioClean || b->iostate == BioDirty);
13875e96a66cSDavid du Colombier 	lpb = c->size / LabelSize;
13885e96a66cSDavid du Colombier 	a = b->addr / lpb;
13895e96a66cSDavid du Colombier 	bb = cacheLocal(c, PartLabel, a, OReadWrite);
13905e96a66cSDavid du Colombier 	if(bb == nil){
13915e96a66cSDavid du Colombier 		blockPut(b);
13925e96a66cSDavid du Colombier 		return nil;
13935e96a66cSDavid du Colombier 	}
13945e96a66cSDavid du Colombier 	b->l = *l;
13955e96a66cSDavid du Colombier 	labelPack(l, bb->data, b->addr%lpb);
13965e96a66cSDavid du Colombier 	blockDirty(bb);
13975e96a66cSDavid du Colombier 	return bb;
13985e96a66cSDavid du Colombier }
13995e96a66cSDavid du Colombier 
14005e96a66cSDavid du Colombier int
14015e96a66cSDavid du Colombier blockSetLabel(Block *b, Label *l)
14025e96a66cSDavid du Colombier {
14035e96a66cSDavid du Colombier 	Block *lb;
14045e96a66cSDavid du Colombier 	Label oldl;
14055e96a66cSDavid du Colombier 
14065e96a66cSDavid du Colombier 	oldl = b->l;
14075e96a66cSDavid du Colombier 	lb = _blockSetLabel(b, l);
14085e96a66cSDavid du Colombier 	if(lb == nil)
14095e96a66cSDavid du Colombier 		return 0;
14105e96a66cSDavid du Colombier 
14115e96a66cSDavid du Colombier 	/*
14125e96a66cSDavid du Colombier 	 * If we're allocating the block, make sure the label (bl)
14135e96a66cSDavid du Colombier 	 * goes to disk before the data block (b) itself.  This is to help
14145e96a66cSDavid du Colombier 	 * the blocks that in turn depend on b.
14155e96a66cSDavid du Colombier 	 *
14165e96a66cSDavid du Colombier 	 * Suppose bx depends on (must be written out after) b.
14175e96a66cSDavid du Colombier 	 * Once we write b we'll think it's safe to write bx.
14185e96a66cSDavid du Colombier 	 * Bx can't get at b unless it has a valid label, though.
14195e96a66cSDavid du Colombier 	 *
14205e96a66cSDavid du Colombier 	 * Allocation is the only case in which having a current label
14215e96a66cSDavid du Colombier 	 * is vital because:
14225e96a66cSDavid du Colombier 	 *
14235e96a66cSDavid du Colombier 	 *	- l.type is set at allocation and never changes.
14245e96a66cSDavid du Colombier 	 *	- l.tag is set at allocation and never changes.
14255e96a66cSDavid du Colombier 	 *	- l.state is not checked when we load blocks.
14265e96a66cSDavid du Colombier 	 *	- the archiver cares deeply about l.state being
14275e96a66cSDavid du Colombier 	 *		BaActive vs. BaCopied, but that's handled
14285e96a66cSDavid du Colombier 	 *		by direct calls to _blockSetLabel.
14295e96a66cSDavid du Colombier 	 */
14305e96a66cSDavid du Colombier 
14315e96a66cSDavid du Colombier 	if(oldl.state == BsFree)
143261201b97SDavid du Colombier 		blockDependency(b, lb, -1, nil, nil);
14335e96a66cSDavid du Colombier 	blockPut(lb);
14345e96a66cSDavid du Colombier 	return 1;
14355e96a66cSDavid du Colombier }
14365e96a66cSDavid du Colombier 
14375e96a66cSDavid du Colombier /*
143861201b97SDavid du Colombier  * We've decided to write out b.  Maybe b has some pointers to blocks
143961201b97SDavid du Colombier  * that haven't yet been written to disk.  If so, construct a slightly out-of-date
144061201b97SDavid du Colombier  * copy of b that is safe to write out.  (diskThread will make sure the block
14415e96a66cSDavid du Colombier  * remains marked as dirty.)
14425e96a66cSDavid du Colombier  */
14435e96a66cSDavid du Colombier uchar *
14445e96a66cSDavid du Colombier blockRollback(Block *b, uchar *buf)
14455e96a66cSDavid du Colombier {
14465e96a66cSDavid du Colombier 	u32int addr;
14475e96a66cSDavid du Colombier 	BList *p;
14485e96a66cSDavid du Colombier 	Super super;
14495e96a66cSDavid du Colombier 
14505e96a66cSDavid du Colombier 	/* easy case */
14515e96a66cSDavid du Colombier 	if(b->prior == nil)
14525e96a66cSDavid du Colombier 		return b->data;
14535e96a66cSDavid du Colombier 
14545e96a66cSDavid du Colombier 	memmove(buf, b->data, b->c->size);
14555e96a66cSDavid du Colombier 	for(p=b->prior; p; p=p->next){
14565e96a66cSDavid du Colombier 		/*
14575e96a66cSDavid du Colombier 		 * we know p->index >= 0 because blockWrite has vetted this block for us.
14585e96a66cSDavid du Colombier 		 */
14595e96a66cSDavid du Colombier 		assert(p->index >= 0);
14605e96a66cSDavid du Colombier 		assert(b->part == PartSuper || (b->part == PartData && b->l.type != BtData));
14615e96a66cSDavid du Colombier 		if(b->part == PartSuper){
14625e96a66cSDavid du Colombier 			assert(p->index == 0);
14635e96a66cSDavid du Colombier 			superUnpack(&super, buf);
146461201b97SDavid du Colombier 			addr = globalToLocal(p->old.score);
14655e96a66cSDavid du Colombier 			if(addr == NilBlock){
146661201b97SDavid du Colombier 				fprint(2, "rolling back super block: bad replacement addr %V\n", p->old.score);
14675e96a66cSDavid du Colombier 				abort();
14685e96a66cSDavid du Colombier 			}
14695e96a66cSDavid du Colombier 			super.active = addr;
14705e96a66cSDavid du Colombier 			superPack(&super, buf);
14715e96a66cSDavid du Colombier 			continue;
14725e96a66cSDavid du Colombier 		}
147361201b97SDavid du Colombier 		if(b->l.type == BtDir)
147461201b97SDavid du Colombier 			memmove(buf+p->index*VtEntrySize, p->old.entry, VtEntrySize);
147561201b97SDavid du Colombier 		else
147661201b97SDavid du Colombier 			memmove(buf+p->index*VtScoreSize, p->old.score, VtScoreSize);
14775e96a66cSDavid du Colombier 	}
14785e96a66cSDavid du Colombier 	return buf;
14795e96a66cSDavid du Colombier }
14805e96a66cSDavid du Colombier 
14815e96a66cSDavid du Colombier /*
14825e96a66cSDavid du Colombier  * Try to write block b.
14835e96a66cSDavid du Colombier  * If b depends on other blocks:
14845e96a66cSDavid du Colombier  *
14855e96a66cSDavid du Colombier  *	If the block has been written out, remove the dependency.
14867abd426fSDavid du Colombier  *	If the dependency is replaced by a more recent dependency,
14877abd426fSDavid du Colombier  *		throw it out.
14885e96a66cSDavid du Colombier  *	If we know how to write out an old version of b that doesn't
14895e96a66cSDavid du Colombier  *		depend on it, do that.
14905e96a66cSDavid du Colombier  *
14915e96a66cSDavid du Colombier  *	Otherwise, bail.
14925e96a66cSDavid du Colombier  */
14935e96a66cSDavid du Colombier int
14945e96a66cSDavid du Colombier blockWrite(Block *b)
14955e96a66cSDavid du Colombier {
149661201b97SDavid du Colombier 	uchar *dmap;
14975e96a66cSDavid du Colombier 	Cache *c;
14985e96a66cSDavid du Colombier 	BList *p, **pp;
14995e96a66cSDavid du Colombier 	Block *bb;
15005e96a66cSDavid du Colombier 	int lockfail;
15015e96a66cSDavid du Colombier 
15025e96a66cSDavid du Colombier 	c = b->c;
15035e96a66cSDavid du Colombier 
15045e96a66cSDavid du Colombier 	if(b->iostate != BioDirty)
15055e96a66cSDavid du Colombier 		return 1;
15065e96a66cSDavid du Colombier 
150761201b97SDavid du Colombier 	dmap = b->dmap;
150861201b97SDavid du Colombier 	memset(dmap, 0, c->ndmap);
15095e96a66cSDavid du Colombier 	pp = &b->prior;
15105e96a66cSDavid du Colombier 	for(p=*pp; p; p=*pp){
151161201b97SDavid du Colombier 		if(p->index >= 0){
151261201b97SDavid du Colombier 			/* more recent dependency has succeeded; this one can go */
151361201b97SDavid du Colombier 			if(dmap[p->index/8] & (1<<(p->index%8)))
151461201b97SDavid du Colombier 				goto ignblock;
151561201b97SDavid du Colombier 		}
151661201b97SDavid du Colombier 
151761201b97SDavid du Colombier 		lockfail = 0;
15185e96a66cSDavid du Colombier 		bb = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
15195e96a66cSDavid du Colombier 		if(bb == nil){
15205e96a66cSDavid du Colombier 			if(lockfail)
15215e96a66cSDavid du Colombier 				return 0;
152261201b97SDavid du Colombier 			/* block not in cache => was written already */
152361201b97SDavid du Colombier 			dmap[p->index/8] |= 1<<(p->index%8);
152461201b97SDavid du Colombier 			goto ignblock;
15255e96a66cSDavid du Colombier 		}
15265e96a66cSDavid du Colombier 
15275e96a66cSDavid du Colombier 		/*
15285e96a66cSDavid du Colombier 		 * same version of block is still in cache.
15295e96a66cSDavid du Colombier 		 *
15305e96a66cSDavid du Colombier 		 * the assertion is true because the block still has version p->vers,
15315e96a66cSDavid du Colombier 		 * which means it hasn't been written out since we last saw it.
15325e96a66cSDavid du Colombier 		 */
15337abd426fSDavid du Colombier 		if(bb->iostate != BioDirty){
15347abd426fSDavid du Colombier 			fprint(2, "%d:%x:%d iostate is %d in blockWrite\n",
15357abd426fSDavid du Colombier 				bb->part, bb->addr, bb->l.type, bb->iostate);
15367abd426fSDavid du Colombier 			/* probably BioWriting if it happens? */
15377abd426fSDavid du Colombier 		}
15387abd426fSDavid du Colombier 
15395e96a66cSDavid du Colombier 		blockPut(bb);
15405e96a66cSDavid du Colombier 
15415e96a66cSDavid du Colombier 		if(p->index < 0){
15425e96a66cSDavid du Colombier 			/*
15435e96a66cSDavid du Colombier 			 * We don't know how to temporarily undo
15445e96a66cSDavid du Colombier 			 * b's dependency on bb, so just don't write b yet.
15455e96a66cSDavid du Colombier 			 */
15465e96a66cSDavid du Colombier 			if(0) fprint(2, "blockWrite skipping %d %x %d %d; need to write %d %x %d\n",
15475e96a66cSDavid du Colombier 				b->part, b->addr, b->vers, b->l.type, p->part, p->addr, bb->vers);
15485e96a66cSDavid du Colombier 			return 0;
15495e96a66cSDavid du Colombier 		}
15505e96a66cSDavid du Colombier 		/* keep walking down the list */
15515e96a66cSDavid du Colombier 		pp = &p->next;
155261201b97SDavid du Colombier 		continue;
155361201b97SDavid du Colombier 
155461201b97SDavid du Colombier ignblock:
155561201b97SDavid du Colombier 		*pp = p->next;
155661201b97SDavid du Colombier 		blistFree(c, p);
155761201b97SDavid du Colombier 		continue;
15585e96a66cSDavid du Colombier 	}
15595e96a66cSDavid du Colombier 
15605e96a66cSDavid du Colombier 	diskWrite(c->disk, b);
15615e96a66cSDavid du Colombier 	return 1;
15625e96a66cSDavid du Colombier }
15635e96a66cSDavid du Colombier 
15645e96a66cSDavid du Colombier /*
15655e96a66cSDavid du Colombier  * Change the I/O state of block b.
15665e96a66cSDavid du Colombier  * Just an assignment except for magic in
15675e96a66cSDavid du Colombier  * switch statement (read comments there).
15685e96a66cSDavid du Colombier  */
15695e96a66cSDavid du Colombier void
15705e96a66cSDavid du Colombier blockSetIOState(Block *b, int iostate)
15715e96a66cSDavid du Colombier {
15725e96a66cSDavid du Colombier 	int dowakeup;
15735e96a66cSDavid du Colombier 	Cache *c;
15745e96a66cSDavid du Colombier 	BList *p, *q;
15755e96a66cSDavid du Colombier 
15765e96a66cSDavid du Colombier if(0) fprint(2, "iostate part=%d addr=%x %s->%s\n", b->part, b->addr, bioStr(b->iostate), bioStr(iostate));
15775e96a66cSDavid du Colombier 
15785e96a66cSDavid du Colombier 	c = b->c;
15795e96a66cSDavid du Colombier 
15805e96a66cSDavid du Colombier 	dowakeup = 0;
15815e96a66cSDavid du Colombier 	switch(iostate){
15825e96a66cSDavid du Colombier 	default:
15835e96a66cSDavid du Colombier 		abort();
15845e96a66cSDavid du Colombier 	case BioEmpty:
15855e96a66cSDavid du Colombier 		assert(!b->uhead);
15865e96a66cSDavid du Colombier 		break;
15875e96a66cSDavid du Colombier 	case BioLabel:
15885e96a66cSDavid du Colombier 		assert(!b->uhead);
15895e96a66cSDavid du Colombier 		break;
15905e96a66cSDavid du Colombier 	case BioClean:
15915e96a66cSDavid du Colombier 		bwatchDependency(b);
15925e96a66cSDavid du Colombier 		/*
15935e96a66cSDavid du Colombier 		 * If b->prior is set, it means a write just finished.
15945e96a66cSDavid du Colombier 		 * The prior list isn't needed anymore.
15955e96a66cSDavid du Colombier 		 */
15965e96a66cSDavid du Colombier 		for(p=b->prior; p; p=q){
15975e96a66cSDavid du Colombier 			q = p->next;
15985e96a66cSDavid du Colombier 			blistFree(c, p);
15995e96a66cSDavid du Colombier 		}
16005e96a66cSDavid du Colombier 		b->prior = nil;
16015e96a66cSDavid du Colombier 		/*
16025e96a66cSDavid du Colombier 		 * Freeing a block or just finished a write.
16035e96a66cSDavid du Colombier 		 * Move the blocks from the per-block unlink
16045e96a66cSDavid du Colombier 		 * queue to the cache unlink queue.
16055e96a66cSDavid du Colombier 		 */
16065e96a66cSDavid du Colombier 		if(b->iostate == BioDirty || b->iostate == BioWriting){
16075e96a66cSDavid du Colombier 			vtLock(c->lk);
16085e96a66cSDavid du Colombier 			c->ndirty--;
160961201b97SDavid du Colombier 			b->iostate = iostate;	/* change here to keep in sync with ndirty */
16105e96a66cSDavid du Colombier 			b->vers = c->vers++;
16115e96a66cSDavid du Colombier 			if(b->uhead){
16125e96a66cSDavid du Colombier 				/* add unlink blocks to unlink queue */
16135e96a66cSDavid du Colombier 				if(c->uhead == nil){
16145e96a66cSDavid du Colombier 					c->uhead = b->uhead;
16155e96a66cSDavid du Colombier 					vtWakeup(c->unlink);
16165e96a66cSDavid du Colombier 				}else
16175e96a66cSDavid du Colombier 					c->utail->next = b->uhead;
16185e96a66cSDavid du Colombier 				c->utail = b->utail;
16195e96a66cSDavid du Colombier 				b->uhead = nil;
16205e96a66cSDavid du Colombier 			}
16215e96a66cSDavid du Colombier 			vtUnlock(c->lk);
16225e96a66cSDavid du Colombier 		}
16235e96a66cSDavid du Colombier 		assert(!b->uhead);
16245e96a66cSDavid du Colombier 		dowakeup = 1;
16255e96a66cSDavid du Colombier 		break;
16265e96a66cSDavid du Colombier 	case BioDirty:
16275e96a66cSDavid du Colombier 		/*
16285e96a66cSDavid du Colombier 		 * Wrote out an old version of the block (see blockRollback).
16295e96a66cSDavid du Colombier 		 * Bump a version count, leave it dirty.
16305e96a66cSDavid du Colombier 		 */
16315e96a66cSDavid du Colombier 		if(b->iostate == BioWriting){
16325e96a66cSDavid du Colombier 			vtLock(c->lk);
16335e96a66cSDavid du Colombier 			b->vers = c->vers++;
16345e96a66cSDavid du Colombier 			vtUnlock(c->lk);
16355e96a66cSDavid du Colombier 			dowakeup = 1;
16365e96a66cSDavid du Colombier 		}
16375e96a66cSDavid du Colombier 		break;
16385e96a66cSDavid du Colombier 	case BioReading:
16395e96a66cSDavid du Colombier 	case BioWriting:
16405e96a66cSDavid du Colombier 		/*
16415e96a66cSDavid du Colombier 		 * Adding block to disk queue.  Bump reference count.
16425e96a66cSDavid du Colombier 		 * diskThread decs the count later by calling blockPut.
16435e96a66cSDavid du Colombier 		 * This is here because we need to lock c->lk to
16445e96a66cSDavid du Colombier 		 * manipulate the ref count.
16455e96a66cSDavid du Colombier 		 */
16465e96a66cSDavid du Colombier 		vtLock(c->lk);
16475e96a66cSDavid du Colombier 		b->ref++;
16485e96a66cSDavid du Colombier 		vtUnlock(c->lk);
16495e96a66cSDavid du Colombier 		break;
16505e96a66cSDavid du Colombier 	case BioReadError:
16515e96a66cSDavid du Colombier 	case BioVentiError:
16525e96a66cSDavid du Colombier 		/*
16535e96a66cSDavid du Colombier 		 * Oops.
16545e96a66cSDavid du Colombier 		 */
16555e96a66cSDavid du Colombier 		dowakeup = 1;
16565e96a66cSDavid du Colombier 		break;
16575e96a66cSDavid du Colombier 	}
16585e96a66cSDavid du Colombier 	b->iostate = iostate;
16595e96a66cSDavid du Colombier 	/*
16605e96a66cSDavid du Colombier 	 * Now that the state has changed, we can wake the waiters.
16615e96a66cSDavid du Colombier 	 */
16625e96a66cSDavid du Colombier 	if(dowakeup)
16635e96a66cSDavid du Colombier 		vtWakeupAll(b->ioready);
16645e96a66cSDavid du Colombier }
16655e96a66cSDavid du Colombier 
16665e96a66cSDavid du Colombier char*
16675e96a66cSDavid du Colombier bsStr(int state)
16685e96a66cSDavid du Colombier {
16695e96a66cSDavid du Colombier 	static char s[100];
16705e96a66cSDavid du Colombier 
16715e96a66cSDavid du Colombier 	if(state == BsFree)
16725e96a66cSDavid du Colombier 		return "Free";
16735e96a66cSDavid du Colombier 	if(state == BsBad)
16745e96a66cSDavid du Colombier 		return "Bad";
16755e96a66cSDavid du Colombier 
16765e96a66cSDavid du Colombier 	sprint(s, "%x", state);
16775e96a66cSDavid du Colombier 	if(!(state&BsAlloc))
16785e96a66cSDavid du Colombier 		strcat(s, ",Free");	/* should not happen */
16795e96a66cSDavid du Colombier 	if(state&BsCopied)
16805e96a66cSDavid du Colombier 		strcat(s, ",Copied");
16815e96a66cSDavid du Colombier 	if(state&BsVenti)
16825e96a66cSDavid du Colombier 		strcat(s, ",Venti");
16835e96a66cSDavid du Colombier 	if(state&BsClosed)
16845e96a66cSDavid du Colombier 		strcat(s, ",Closed");
16855e96a66cSDavid du Colombier 	return s;
16865e96a66cSDavid du Colombier }
16875e96a66cSDavid du Colombier 
16885e96a66cSDavid du Colombier char *
16895e96a66cSDavid du Colombier bioStr(int iostate)
16905e96a66cSDavid du Colombier {
16915e96a66cSDavid du Colombier 	switch(iostate){
16925e96a66cSDavid du Colombier 	default:
16935e96a66cSDavid du Colombier 		return "Unknown!!";
16945e96a66cSDavid du Colombier 	case BioEmpty:
16955e96a66cSDavid du Colombier 		return "Empty";
16965e96a66cSDavid du Colombier 	case BioLabel:
16975e96a66cSDavid du Colombier 		return "Label";
16985e96a66cSDavid du Colombier 	case BioClean:
16995e96a66cSDavid du Colombier 		return "Clean";
17005e96a66cSDavid du Colombier 	case BioDirty:
17015e96a66cSDavid du Colombier 		return "Dirty";
17025e96a66cSDavid du Colombier 	case BioReading:
17035e96a66cSDavid du Colombier 		return "Reading";
17045e96a66cSDavid du Colombier 	case BioWriting:
17055e96a66cSDavid du Colombier 		return "Writing";
17065e96a66cSDavid du Colombier 	case BioReadError:
17075e96a66cSDavid du Colombier 		return "ReadError";
17085e96a66cSDavid du Colombier 	case BioVentiError:
17095e96a66cSDavid du Colombier 		return "VentiError";
17105e96a66cSDavid du Colombier 	case BioMax:
17115e96a66cSDavid du Colombier 		return "Max";
17125e96a66cSDavid du Colombier 	}
17135e96a66cSDavid du Colombier }
17145e96a66cSDavid du Colombier 
17155e96a66cSDavid du Colombier static char *bttab[] = {
17165e96a66cSDavid du Colombier 	"BtData",
17175e96a66cSDavid du Colombier 	"BtData+1",
17185e96a66cSDavid du Colombier 	"BtData+2",
17195e96a66cSDavid du Colombier 	"BtData+3",
17205e96a66cSDavid du Colombier 	"BtData+4",
17215e96a66cSDavid du Colombier 	"BtData+5",
17225e96a66cSDavid du Colombier 	"BtData+6",
17235e96a66cSDavid du Colombier 	"BtData+7",
17245e96a66cSDavid du Colombier 	"BtDir",
17255e96a66cSDavid du Colombier 	"BtDir+1",
17265e96a66cSDavid du Colombier 	"BtDir+2",
17275e96a66cSDavid du Colombier 	"BtDir+3",
17285e96a66cSDavid du Colombier 	"BtDir+4",
17295e96a66cSDavid du Colombier 	"BtDir+5",
17305e96a66cSDavid du Colombier 	"BtDir+6",
17315e96a66cSDavid du Colombier 	"BtDir+7",
17325e96a66cSDavid du Colombier };
17335e96a66cSDavid du Colombier 
17345e96a66cSDavid du Colombier char*
17355e96a66cSDavid du Colombier btStr(int type)
17365e96a66cSDavid du Colombier {
17375e96a66cSDavid du Colombier 	if(type < nelem(bttab))
17385e96a66cSDavid du Colombier 		return bttab[type];
17395e96a66cSDavid du Colombier 	return "unknown";
17405e96a66cSDavid du Colombier }
17415e96a66cSDavid du Colombier 
17425e96a66cSDavid du Colombier int
17435e96a66cSDavid du Colombier labelFmt(Fmt *f)
17445e96a66cSDavid du Colombier {
17455e96a66cSDavid du Colombier 	Label *l;
17465e96a66cSDavid du Colombier 
17475e96a66cSDavid du Colombier 	l = va_arg(f->args, Label*);
17485e96a66cSDavid du Colombier 	return fmtprint(f, "%s,%s,e=%ud,%d,tag=%#ux",
17495e96a66cSDavid du Colombier 		btStr(l->type), bsStr(l->state), l->epoch, (int)l->epochClose, l->tag);
17505e96a66cSDavid du Colombier }
17515e96a66cSDavid du Colombier 
17525e96a66cSDavid du Colombier int
17535e96a66cSDavid du Colombier scoreFmt(Fmt *f)
17545e96a66cSDavid du Colombier {
17555e96a66cSDavid du Colombier 	uchar *v;
17565e96a66cSDavid du Colombier 	int i;
17575e96a66cSDavid du Colombier 	u32int addr;
17585e96a66cSDavid du Colombier 
17595e96a66cSDavid du Colombier 	v = va_arg(f->args, uchar*);
17605e96a66cSDavid du Colombier 	if(v == nil){
17615e96a66cSDavid du Colombier 		fmtprint(f, "*");
17625e96a66cSDavid du Colombier 	}else if((addr = globalToLocal(v)) != NilBlock)
17635e96a66cSDavid du Colombier 		fmtprint(f, "0x%.8ux", addr);
17645e96a66cSDavid du Colombier 	else{
17655e96a66cSDavid du Colombier 		for(i = 0; i < VtScoreSize; i++)
17665e96a66cSDavid du Colombier 			fmtprint(f, "%2.2ux", v[i]);
17675e96a66cSDavid du Colombier 	}
17685e96a66cSDavid du Colombier 
17695e96a66cSDavid du Colombier 	return 0;
17705e96a66cSDavid du Colombier }
17715e96a66cSDavid du Colombier 
17725e96a66cSDavid du Colombier static int
17735e96a66cSDavid du Colombier upHeap(int i, Block *b)
17745e96a66cSDavid du Colombier {
17755e96a66cSDavid du Colombier 	Block *bb;
17765e96a66cSDavid du Colombier 	u32int now;
17775e96a66cSDavid du Colombier 	int p;
17785e96a66cSDavid du Colombier 	Cache *c;
17795e96a66cSDavid du Colombier 
17805e96a66cSDavid du Colombier 	c = b->c;
17815e96a66cSDavid du Colombier 	now = c->now;
17825e96a66cSDavid du Colombier 	for(; i != 0; i = p){
17835e96a66cSDavid du Colombier 		p = (i - 1) >> 1;
17845e96a66cSDavid du Colombier 		bb = c->heap[p];
17855e96a66cSDavid du Colombier 		if(b->used - now >= bb->used - now)
17865e96a66cSDavid du Colombier 			break;
17875e96a66cSDavid du Colombier 		c->heap[i] = bb;
17885e96a66cSDavid du Colombier 		bb->heap = i;
17895e96a66cSDavid du Colombier 	}
17905e96a66cSDavid du Colombier 	c->heap[i] = b;
17915e96a66cSDavid du Colombier 	b->heap = i;
17925e96a66cSDavid du Colombier 
17935e96a66cSDavid du Colombier 	return i;
17945e96a66cSDavid du Colombier }
17955e96a66cSDavid du Colombier 
17965e96a66cSDavid du Colombier static int
17975e96a66cSDavid du Colombier downHeap(int i, Block *b)
17985e96a66cSDavid du Colombier {
17995e96a66cSDavid du Colombier 	Block *bb;
18005e96a66cSDavid du Colombier 	u32int now;
18015e96a66cSDavid du Colombier 	int k;
18025e96a66cSDavid du Colombier 	Cache *c;
18035e96a66cSDavid du Colombier 
18045e96a66cSDavid du Colombier 	c = b->c;
18055e96a66cSDavid du Colombier 	now = c->now;
18065e96a66cSDavid du Colombier 	for(; ; i = k){
18075e96a66cSDavid du Colombier 		k = (i << 1) + 1;
18085e96a66cSDavid du Colombier 		if(k >= c->nheap)
18095e96a66cSDavid du Colombier 			break;
18105e96a66cSDavid du Colombier 		if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
18115e96a66cSDavid du Colombier 			k++;
18125e96a66cSDavid du Colombier 		bb = c->heap[k];
18135e96a66cSDavid du Colombier 		if(b->used - now <= bb->used - now)
18145e96a66cSDavid du Colombier 			break;
18155e96a66cSDavid du Colombier 		c->heap[i] = bb;
18165e96a66cSDavid du Colombier 		bb->heap = i;
18175e96a66cSDavid du Colombier 	}
18185e96a66cSDavid du Colombier 	c->heap[i] = b;
18195e96a66cSDavid du Colombier 	b->heap = i;
18205e96a66cSDavid du Colombier 	return i;
18215e96a66cSDavid du Colombier }
18225e96a66cSDavid du Colombier 
18235e96a66cSDavid du Colombier /*
18245e96a66cSDavid du Colombier  * Delete a block from the heap.
18255e96a66cSDavid du Colombier  * Called with c->lk held.
18265e96a66cSDavid du Colombier  */
18275e96a66cSDavid du Colombier static void
18285e96a66cSDavid du Colombier heapDel(Block *b)
18295e96a66cSDavid du Colombier {
18305e96a66cSDavid du Colombier 	int i, si;
18315e96a66cSDavid du Colombier 	Cache *c;
18325e96a66cSDavid du Colombier 
18335e96a66cSDavid du Colombier 	c = b->c;
18345e96a66cSDavid du Colombier 
18355e96a66cSDavid du Colombier 	si = b->heap;
18365e96a66cSDavid du Colombier 	if(si == BadHeap)
18375e96a66cSDavid du Colombier 		return;
18385e96a66cSDavid du Colombier 	b->heap = BadHeap;
18395e96a66cSDavid du Colombier 	c->nheap--;
18405e96a66cSDavid du Colombier 	if(si == c->nheap)
18415e96a66cSDavid du Colombier 		return;
18425e96a66cSDavid du Colombier 	b = c->heap[c->nheap];
18435e96a66cSDavid du Colombier 	i = upHeap(si, b);
18445e96a66cSDavid du Colombier 	if(i == si)
18455e96a66cSDavid du Colombier 		downHeap(i, b);
18465e96a66cSDavid du Colombier }
18475e96a66cSDavid du Colombier 
18485e96a66cSDavid du Colombier /*
18495e96a66cSDavid du Colombier  * Insert a block into the heap.
18505e96a66cSDavid du Colombier  * Called with c->lk held.
18515e96a66cSDavid du Colombier  */
18525e96a66cSDavid du Colombier static void
18535e96a66cSDavid du Colombier heapIns(Block *b)
18545e96a66cSDavid du Colombier {
18555e96a66cSDavid du Colombier 	assert(b->heap == BadHeap);
18565e96a66cSDavid du Colombier 	upHeap(b->c->nheap++, b);
18575e96a66cSDavid du Colombier }
18585e96a66cSDavid du Colombier 
18595e96a66cSDavid du Colombier /*
18605e96a66cSDavid du Colombier  * Get just the label for a block.
18615e96a66cSDavid du Colombier  */
18625e96a66cSDavid du Colombier static int
18635e96a66cSDavid du Colombier readLabel(Cache *c, Label *l, u32int addr)
18645e96a66cSDavid du Colombier {
18655e96a66cSDavid du Colombier 	int lpb;
18665e96a66cSDavid du Colombier 	Block *b;
18675e96a66cSDavid du Colombier 	u32int a;
18685e96a66cSDavid du Colombier 
18695e96a66cSDavid du Colombier 	lpb = c->size / LabelSize;
18705e96a66cSDavid du Colombier 	a = addr / lpb;
18715e96a66cSDavid du Colombier 	b = cacheLocal(c, PartLabel, a, OReadOnly);
18725e96a66cSDavid du Colombier 	if(b == nil){
18735e96a66cSDavid du Colombier 		blockPut(b);
18745e96a66cSDavid du Colombier 		return 0;
18755e96a66cSDavid du Colombier 	}
18765e96a66cSDavid du Colombier 
18775e96a66cSDavid du Colombier 	if(!labelUnpack(l, b->data, addr%lpb)){
18785e96a66cSDavid du Colombier 		blockPut(b);
18795e96a66cSDavid du Colombier 		return 0;
18805e96a66cSDavid du Colombier 	}
18815e96a66cSDavid du Colombier 	blockPut(b);
18825e96a66cSDavid du Colombier 	return 1;
18835e96a66cSDavid du Colombier }
18845e96a66cSDavid du Colombier 
18855e96a66cSDavid du Colombier /*
18865e96a66cSDavid du Colombier  * Process unlink queue.
18875e96a66cSDavid du Colombier  * Called with c->lk held.
18885e96a66cSDavid du Colombier  */
18895e96a66cSDavid du Colombier static void
18905e96a66cSDavid du Colombier unlinkBody(Cache *c)
18915e96a66cSDavid du Colombier {
18925e96a66cSDavid du Colombier 	BList *p;
18935e96a66cSDavid du Colombier 
18945e96a66cSDavid du Colombier 	while(c->uhead != nil){
18955e96a66cSDavid du Colombier 		p = c->uhead;
18965e96a66cSDavid du Colombier 		c->uhead = p->next;
18975e96a66cSDavid du Colombier 		vtUnlock(c->lk);
18985e96a66cSDavid du Colombier 
18995e96a66cSDavid du Colombier 		if(!unlinkBlock(c, p->addr, p->type, p->tag, p->epoch))
19005e96a66cSDavid du Colombier 			fprint(2, "unlinkBlock failed: addr=%x type=%d tag = %ux: %r\n",
19015e96a66cSDavid du Colombier 				p->addr, p->type, p->tag);
19025e96a66cSDavid du Colombier 
19035e96a66cSDavid du Colombier 		vtLock(c->lk);
19045e96a66cSDavid du Colombier 		p->next = c->blfree;
19055e96a66cSDavid du Colombier 		c->blfree = p;
19065e96a66cSDavid du Colombier 	}
19075e96a66cSDavid du Colombier }
19085e96a66cSDavid du Colombier 
19095e96a66cSDavid du Colombier /*
19105e96a66cSDavid du Colombier  * Occasionally unlink the blocks on the cache unlink queue.
19115e96a66cSDavid du Colombier  */
19125e96a66cSDavid du Colombier static void
19135e96a66cSDavid du Colombier unlinkThread(void *a)
19145e96a66cSDavid du Colombier {
19155e96a66cSDavid du Colombier 	Cache *c = a;
19165e96a66cSDavid du Colombier 
19175e96a66cSDavid du Colombier 	vtThreadSetName("unlink");
19185e96a66cSDavid du Colombier 
19195e96a66cSDavid du Colombier 	vtLock(c->lk);
19205e96a66cSDavid du Colombier 	for(;;){
19215e96a66cSDavid du Colombier 		while(c->uhead == nil && c->die == nil)
19225e96a66cSDavid du Colombier 			vtSleep(c->unlink);
19235e96a66cSDavid du Colombier 		if(c->die != nil)
19245e96a66cSDavid du Colombier 			break;
19255e96a66cSDavid du Colombier 		unlinkBody(c);
19265e96a66cSDavid du Colombier 	}
19275e96a66cSDavid du Colombier 	c->ref--;
19285e96a66cSDavid du Colombier 	vtWakeup(c->die);
19295e96a66cSDavid du Colombier 	vtUnlock(c->lk);
19305e96a66cSDavid du Colombier }
19315e96a66cSDavid du Colombier 
19325e96a66cSDavid du Colombier static int
19335e96a66cSDavid du Colombier baddrCmp(void *a0, void *a1)
19345e96a66cSDavid du Colombier {
19355e96a66cSDavid du Colombier 	BAddr *b0, *b1;
19365e96a66cSDavid du Colombier 	b0 = a0;
19375e96a66cSDavid du Colombier 	b1 = a1;
19385e96a66cSDavid du Colombier 
19395e96a66cSDavid du Colombier 	if(b0->part < b1->part)
19405e96a66cSDavid du Colombier 		return -1;
19415e96a66cSDavid du Colombier 	if(b0->part > b1->part)
19425e96a66cSDavid du Colombier 		return 1;
19435e96a66cSDavid du Colombier 	if(b0->addr < b1->addr)
19445e96a66cSDavid du Colombier 		return -1;
19455e96a66cSDavid du Colombier 	if(b0->addr > b1->addr)
19465e96a66cSDavid du Colombier 		return 1;
19475e96a66cSDavid du Colombier 	return 0;
19485e96a66cSDavid du Colombier }
19495e96a66cSDavid du Colombier 
19505e96a66cSDavid du Colombier /*
19515e96a66cSDavid du Colombier  * Scan the block list for dirty blocks; add them to the list c->baddr.
19525e96a66cSDavid du Colombier  */
19535e96a66cSDavid du Colombier static void
19545e96a66cSDavid du Colombier flushFill(Cache *c)
19555e96a66cSDavid du Colombier {
195661201b97SDavid du Colombier 	int i, ndirty;
19575e96a66cSDavid du Colombier 	BAddr *p;
19585e96a66cSDavid du Colombier 	Block *b;
19595e96a66cSDavid du Colombier 
19605e96a66cSDavid du Colombier 	vtLock(c->lk);
1961*39734e7eSDavid du Colombier 	if(c->ndirty == 0){
1962*39734e7eSDavid du Colombier 		vtUnlock(c->lk);
1963*39734e7eSDavid du Colombier 		return;
1964*39734e7eSDavid du Colombier 	}
19655e96a66cSDavid du Colombier 
19665e96a66cSDavid du Colombier 	p = c->baddr;
196761201b97SDavid du Colombier 	ndirty = 0;
19685e96a66cSDavid du Colombier 	for(i=0; i<c->nblocks; i++){
19695e96a66cSDavid du Colombier 		b = c->blocks + i;
197061201b97SDavid du Colombier 		if(b->part == PartError)
197161201b97SDavid du Colombier 			continue;
197261201b97SDavid du Colombier 		if(b->iostate == BioDirty || b->iostate == BioWriting)
197361201b97SDavid du Colombier 			ndirty++;
197461201b97SDavid du Colombier 		if(b->iostate != BioDirty)
19755e96a66cSDavid du Colombier 			continue;
19765e96a66cSDavid du Colombier 		p->part = b->part;
19775e96a66cSDavid du Colombier 		p->addr = b->addr;
19785e96a66cSDavid du Colombier 		p->vers = b->vers;
19795e96a66cSDavid du Colombier 		p++;
19805e96a66cSDavid du Colombier 	}
198161201b97SDavid du Colombier 	if(ndirty != c->ndirty){
198261201b97SDavid du Colombier 		fprint(2, "ndirty mismatch expected %d found %d\n",
198361201b97SDavid du Colombier 			c->ndirty, ndirty);
198461201b97SDavid du Colombier 		c->ndirty = ndirty;
198561201b97SDavid du Colombier 	}
19865e96a66cSDavid du Colombier 	vtUnlock(c->lk);
19875e96a66cSDavid du Colombier 
19885e96a66cSDavid du Colombier 	c->bw = p - c->baddr;
19895e96a66cSDavid du Colombier 	qsort(c->baddr, c->bw, sizeof(BAddr), baddrCmp);
19905e96a66cSDavid du Colombier }
19915e96a66cSDavid du Colombier 
19925e96a66cSDavid du Colombier /*
19935e96a66cSDavid du Colombier  * This is not thread safe, i.e. it can't be called from multiple threads.
19945e96a66cSDavid du Colombier  *
19955e96a66cSDavid du Colombier  * It's okay how we use it, because it only gets called in
19965e96a66cSDavid du Colombier  * the flushThread.  And cacheFree, but only after
19975e96a66cSDavid du Colombier  * cacheFree has killed off the flushThread.
19985e96a66cSDavid du Colombier  */
19995e96a66cSDavid du Colombier static int
20005e96a66cSDavid du Colombier cacheFlushBlock(Cache *c)
20015e96a66cSDavid du Colombier {
20025e96a66cSDavid du Colombier 	Block *b;
20035e96a66cSDavid du Colombier 	BAddr *p;
20045e96a66cSDavid du Colombier 	int lockfail, nfail;
20055e96a66cSDavid du Colombier 
20065e96a66cSDavid du Colombier 	nfail = 0;
20075e96a66cSDavid du Colombier 	for(;;){
20085e96a66cSDavid du Colombier 		if(c->br == c->be){
20095e96a66cSDavid du Colombier 			if(c->bw == 0 || c->bw == c->be)
20105e96a66cSDavid du Colombier 				flushFill(c);
20115e96a66cSDavid du Colombier 			c->br = 0;
20125e96a66cSDavid du Colombier 			c->be = c->bw;
20135e96a66cSDavid du Colombier 			c->bw = 0;
20145e96a66cSDavid du Colombier 			c->nflush = 0;
20155e96a66cSDavid du Colombier 		}
20165e96a66cSDavid du Colombier 
20175e96a66cSDavid du Colombier 		if(c->br == c->be)
20185e96a66cSDavid du Colombier 			return 0;
20195e96a66cSDavid du Colombier 		p = c->baddr + c->br;
20205e96a66cSDavid du Colombier 		c->br++;
20215e96a66cSDavid du Colombier 		b = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
20225e96a66cSDavid du Colombier 
20235e96a66cSDavid du Colombier 		if(b && blockWrite(b)){
20245e96a66cSDavid du Colombier 			c->nflush++;
20255e96a66cSDavid du Colombier 			blockPut(b);
20265e96a66cSDavid du Colombier 			return 1;
20275e96a66cSDavid du Colombier 		}
20285e96a66cSDavid du Colombier 		if(b)
20295e96a66cSDavid du Colombier 			blockPut(b);
20305e96a66cSDavid du Colombier 
20315e96a66cSDavid du Colombier 		/*
20325e96a66cSDavid du Colombier 		 * Why didn't we write the block?
20335e96a66cSDavid du Colombier 		 */
20345e96a66cSDavid du Colombier 
20355e96a66cSDavid du Colombier 		/* Block already written out */
20365e96a66cSDavid du Colombier 		if(b == nil && !lockfail)
20375e96a66cSDavid du Colombier 			continue;
20385e96a66cSDavid du Colombier 
20395e96a66cSDavid du Colombier 		/* Failed to acquire lock; sleep if happens a lot. */
20405e96a66cSDavid du Colombier 		if(lockfail && ++nfail > 100)
20415e96a66cSDavid du Colombier 			sleep(500);
20425e96a66cSDavid du Colombier 
20435e96a66cSDavid du Colombier 		/* Requeue block. */
20445e96a66cSDavid du Colombier 		if(c->bw < c->be)
20455e96a66cSDavid du Colombier 			c->baddr[c->bw++] = *p;
20465e96a66cSDavid du Colombier 	}
20475e96a66cSDavid du Colombier 	return 0;
20485e96a66cSDavid du Colombier }
20495e96a66cSDavid du Colombier 
20505e96a66cSDavid du Colombier /*
20515e96a66cSDavid du Colombier  * Occasionally flush dirty blocks from memory to the disk.
20525e96a66cSDavid du Colombier  */
20535e96a66cSDavid du Colombier static void
20545e96a66cSDavid du Colombier flushThread(void *a)
20555e96a66cSDavid du Colombier {
20565e96a66cSDavid du Colombier 	Cache *c = a;
20575e96a66cSDavid du Colombier 	int i;
20585e96a66cSDavid du Colombier 
20595e96a66cSDavid du Colombier 	vtThreadSetName("flush");
20605e96a66cSDavid du Colombier 	vtLock(c->lk);
20615e96a66cSDavid du Colombier 	while(c->die == nil){
20625e96a66cSDavid du Colombier 		vtSleep(c->flush);
20635e96a66cSDavid du Colombier 		vtUnlock(c->lk);
20645e96a66cSDavid du Colombier 		for(i=0; i<FlushSize; i++)
20655e96a66cSDavid du Colombier 			if(!cacheFlushBlock(c))
20665e96a66cSDavid du Colombier 				break;
2067*39734e7eSDavid du Colombier 		if(i==0 && c->ndirty){
2068*39734e7eSDavid du Colombier 			/*
2069*39734e7eSDavid du Colombier 			 * All the blocks are being written right now -- there's nothing to do.
2070*39734e7eSDavid du Colombier 			 * We might be spinning with cacheFlush though -- he'll just keep
2071*39734e7eSDavid du Colombier 			 * kicking us until c->ndirty goes down.  Probably we should sleep
2072*39734e7eSDavid du Colombier 			 * on something that the diskThread can kick, but for now we'll
2073*39734e7eSDavid du Colombier 			 * just pause for a little while waiting for disks to finish.
2074*39734e7eSDavid du Colombier 			 */
2075*39734e7eSDavid du Colombier 			sleep(100);
2076*39734e7eSDavid du Colombier 		}
20775e96a66cSDavid du Colombier 		vtLock(c->lk);
20785e96a66cSDavid du Colombier 		vtWakeupAll(c->flushwait);
20795e96a66cSDavid du Colombier 	}
20805e96a66cSDavid du Colombier 	c->ref--;
20815e96a66cSDavid du Colombier 	vtWakeup(c->die);
20825e96a66cSDavid du Colombier 	vtUnlock(c->lk);
20835e96a66cSDavid du Colombier }
20845e96a66cSDavid du Colombier 
20855e96a66cSDavid du Colombier /*
20865e96a66cSDavid du Colombier  * Keep flushing until everything is clean.
20875e96a66cSDavid du Colombier  */
20885e96a66cSDavid du Colombier void
20895e96a66cSDavid du Colombier cacheFlush(Cache *c, int wait)
20905e96a66cSDavid du Colombier {
20915e96a66cSDavid du Colombier 	vtLock(c->lk);
20925e96a66cSDavid du Colombier 	if(wait){
20935e96a66cSDavid du Colombier 		while(c->ndirty){
2094dc5a79c1SDavid du Colombier 		//	consPrint("cacheFlush: %d dirty blocks, uhead %p\n",
2095dc5a79c1SDavid du Colombier 		//		c->ndirty, c->uhead);
20965e96a66cSDavid du Colombier 			vtWakeup(c->flush);
20975e96a66cSDavid du Colombier 			vtSleep(c->flushwait);
20985e96a66cSDavid du Colombier 		}
2099dc5a79c1SDavid du Colombier 	//	consPrint("cacheFlush: done (uhead %p)\n", c->ndirty, c->uhead);
21005e96a66cSDavid du Colombier 	}else
21015e96a66cSDavid du Colombier 		vtWakeup(c->flush);
21025e96a66cSDavid du Colombier 	vtUnlock(c->lk);
21035e96a66cSDavid du Colombier }
210461201b97SDavid du Colombier 
210561201b97SDavid du Colombier /*
210661201b97SDavid du Colombier  * Kick the flushThread every 30 seconds.
210761201b97SDavid du Colombier  */
210861201b97SDavid du Colombier static void
210961201b97SDavid du Colombier cacheSync(void *v)
211061201b97SDavid du Colombier {
211161201b97SDavid du Colombier 	Cache *c;
211261201b97SDavid du Colombier 
211361201b97SDavid du Colombier 	c = v;
211461201b97SDavid du Colombier 	cacheFlush(c, 0);
211561201b97SDavid du Colombier }
2116