xref: /plan9-contrib/sys/src/cmd/fossil/cache.c (revision fe853e2326f51910bb38886e9bfc22ecdef993d7)
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;
55*fe853e23SDavid du Colombier 	VtRendez *heapwait;
565e96a66cSDavid du Colombier 	BAddr *baddr;
575e96a66cSDavid du Colombier 	int bw, br, be;
585e96a66cSDavid du Colombier 	int nflush;
595e96a66cSDavid du Colombier 
6061201b97SDavid du Colombier 	Periodic *sync;
6161201b97SDavid du Colombier 
625e96a66cSDavid du Colombier 	/* unlink daemon */
635e96a66cSDavid du Colombier 	BList *uhead;
645e96a66cSDavid du Colombier 	BList *utail;
655e96a66cSDavid du Colombier 	VtRendez *unlink;
667abd426fSDavid du Colombier 
677abd426fSDavid du Colombier 	/* block counts */
687abd426fSDavid du Colombier 	int nused;
697abd426fSDavid du Colombier 	int ndisk;
705e96a66cSDavid du Colombier };
715e96a66cSDavid du Colombier 
725e96a66cSDavid du Colombier struct BList {
735e96a66cSDavid du Colombier 	int part;
745e96a66cSDavid du Colombier 	u32int addr;
755e96a66cSDavid du Colombier 	uchar type;
765e96a66cSDavid du Colombier 	u32int tag;
775e96a66cSDavid du Colombier 	u32int epoch;
785e96a66cSDavid du Colombier 	u32int vers;
795e96a66cSDavid du Colombier 
805e96a66cSDavid du Colombier 	/* for roll back */
815e96a66cSDavid du Colombier 	int index;			/* -1 indicates not valid */
8261201b97SDavid du Colombier 	union {
835e96a66cSDavid du Colombier 		uchar score[VtScoreSize];
8461201b97SDavid du Colombier 		uchar entry[VtEntrySize];
8561201b97SDavid du Colombier 	} old;
865e96a66cSDavid du Colombier 	BList *next;
875e96a66cSDavid du Colombier };
885e96a66cSDavid du Colombier 
895e96a66cSDavid du Colombier struct BAddr {
905e96a66cSDavid du Colombier 	int part;
915e96a66cSDavid du Colombier 	u32int addr;
925e96a66cSDavid du Colombier 	u32int vers;
935e96a66cSDavid du Colombier };
945e96a66cSDavid du Colombier 
955e96a66cSDavid du Colombier struct FreeList {
965e96a66cSDavid du Colombier 	VtLock *lk;
975e96a66cSDavid du Colombier 	u32int last;	/* last block allocated */
985e96a66cSDavid du Colombier 	u32int end;	/* end of data partition */
997abd426fSDavid du Colombier 	u32int nfree;	/* number of free blocks */
1007abd426fSDavid du Colombier 	u32int nused;	/* number of used blocks */
1017abd426fSDavid du Colombier 	u32int epochLow;	/* low epoch when last updated nfree and nused */
1025e96a66cSDavid du Colombier };
1035e96a66cSDavid du Colombier 
1045e96a66cSDavid du Colombier static FreeList *flAlloc(u32int end);
1055e96a66cSDavid du Colombier static void flFree(FreeList *fl);
1065e96a66cSDavid du Colombier 
1075e96a66cSDavid du Colombier static Block *cacheBumpBlock(Cache *c);
1085e96a66cSDavid du Colombier static void heapDel(Block*);
1095e96a66cSDavid du Colombier static void heapIns(Block*);
1105e96a66cSDavid du Colombier static void cacheCheck(Cache*);
1115e96a66cSDavid du Colombier static int readLabel(Cache*, Label*, u32int addr);
1125e96a66cSDavid du Colombier static void unlinkThread(void *a);
1135e96a66cSDavid du Colombier static void flushThread(void *a);
1145e96a66cSDavid du Colombier static void flushBody(Cache *c);
1155e96a66cSDavid du Colombier static void unlinkBody(Cache *c);
1165e96a66cSDavid du Colombier static int cacheFlushBlock(Cache *c);
11761201b97SDavid du Colombier static void cacheSync(void*);
1185e96a66cSDavid du Colombier /*
1195e96a66cSDavid du Colombier  * Mapping from local block type to Venti type
1205e96a66cSDavid du Colombier  */
1215e96a66cSDavid du Colombier int vtType[BtMax] = {
1225e96a66cSDavid du Colombier 	VtDataType,		/* BtData | 0  */
1235e96a66cSDavid du Colombier 	VtPointerType0,		/* BtData | 1  */
1245e96a66cSDavid du Colombier 	VtPointerType1,		/* BtData | 2  */
1255e96a66cSDavid du Colombier 	VtPointerType2,		/* BtData | 3  */
1265e96a66cSDavid du Colombier 	VtPointerType3,		/* BtData | 4  */
1275e96a66cSDavid du Colombier 	VtPointerType4,		/* BtData | 5  */
1285e96a66cSDavid du Colombier 	VtPointerType5,		/* BtData | 6  */
1295e96a66cSDavid du Colombier 	VtPointerType6,		/* BtData | 7  */
1305e96a66cSDavid du Colombier 	VtDirType,		/* BtDir | 0  */
1315e96a66cSDavid du Colombier 	VtPointerType0,		/* BtDir | 1  */
1325e96a66cSDavid du Colombier 	VtPointerType1,		/* BtDir | 2  */
1335e96a66cSDavid du Colombier 	VtPointerType2,		/* BtDir | 3  */
1345e96a66cSDavid du Colombier 	VtPointerType3,		/* BtDir | 4  */
1355e96a66cSDavid du Colombier 	VtPointerType4,		/* BtDir | 5  */
1365e96a66cSDavid du Colombier 	VtPointerType5,		/* BtDir | 6  */
1375e96a66cSDavid du Colombier 	VtPointerType6,		/* BtDir | 7  */
1385e96a66cSDavid du Colombier };
1395e96a66cSDavid du Colombier 
1405e96a66cSDavid du Colombier /*
1415e96a66cSDavid du Colombier  * Allocate the memory cache.
1425e96a66cSDavid du Colombier  */
1435e96a66cSDavid du Colombier Cache *
1445e96a66cSDavid du Colombier cacheAlloc(Disk *disk, VtSession *z, ulong nblocks, int mode)
1455e96a66cSDavid du Colombier {
1465e96a66cSDavid du Colombier 	int i;
1475e96a66cSDavid du Colombier 	Cache *c;
1485e96a66cSDavid du Colombier 	Block *b;
1495e96a66cSDavid du Colombier 	BList *bl;
1505e96a66cSDavid du Colombier 	u8int *p;
1515e96a66cSDavid du Colombier 	int nbl;
1525e96a66cSDavid du Colombier 
1535e96a66cSDavid du Colombier 	c = vtMemAllocZ(sizeof(Cache));
1545e96a66cSDavid du Colombier 
1555e96a66cSDavid du Colombier 	/* reasonable number of BList elements */
1565e96a66cSDavid du Colombier 	nbl = nblocks * 4;
1575e96a66cSDavid du Colombier 
1585e96a66cSDavid du Colombier 	c->lk = vtLockAlloc();
1595e96a66cSDavid du Colombier 	c->ref = 1;
1605e96a66cSDavid du Colombier 	c->disk = disk;
1615e96a66cSDavid du Colombier 	c->z = z;
1625e96a66cSDavid du Colombier 	c->size = diskBlockSize(disk);
1635e96a66cSDavid du Colombier bwatchSetBlockSize(c->size);
1645e96a66cSDavid du Colombier 	/* round c->size up to be a nice multiple */
1655e96a66cSDavid du Colombier 	c->size = (c->size + 127) & ~127;
16661201b97SDavid du Colombier 	c->ndmap = (c->size/20 + 7) / 8;
1675e96a66cSDavid du Colombier 	c->nblocks = nblocks;
1685e96a66cSDavid du Colombier 	c->hashSize = nblocks;
1695e96a66cSDavid du Colombier 	c->heads = vtMemAllocZ(c->hashSize*sizeof(Block*));
1705e96a66cSDavid du Colombier 	c->heap = vtMemAllocZ(nblocks*sizeof(Block*));
1715e96a66cSDavid du Colombier 	c->blocks = vtMemAllocZ(nblocks*sizeof(Block));
17261201b97SDavid du Colombier 	c->mem = vtMemAllocZ(nblocks * (c->size + c->ndmap) + nbl * sizeof(BList));
1735e96a66cSDavid du Colombier 	c->baddr = vtMemAllocZ(nblocks * sizeof(BAddr));
1745e96a66cSDavid du Colombier 	c->mode = mode;
1755e96a66cSDavid du Colombier 	c->vers++;
1765e96a66cSDavid du Colombier 	p = c->mem;
1775e96a66cSDavid du Colombier 	for(i = 0; i < nblocks; i++){
1785e96a66cSDavid du Colombier 		b = &c->blocks[i];
1795e96a66cSDavid du Colombier 		b->lk = vtLockAlloc();
1805e96a66cSDavid du Colombier 		b->c = c;
1815e96a66cSDavid du Colombier 		b->data = p;
1825e96a66cSDavid du Colombier 		b->heap = i;
1835e96a66cSDavid du Colombier 		b->ioready = vtRendezAlloc(b->lk);
1845e96a66cSDavid du Colombier 		c->heap[i] = b;
1855e96a66cSDavid du Colombier 		p += c->size;
1865e96a66cSDavid du Colombier 	}
1875e96a66cSDavid du Colombier 	c->nheap = nblocks;
1885e96a66cSDavid du Colombier 	for(i = 0; i < nbl; i++){
1895e96a66cSDavid du Colombier 		bl = (BList*)p;
1905e96a66cSDavid du Colombier 		bl->next = c->blfree;
1915e96a66cSDavid du Colombier 		c->blfree = bl;
1925e96a66cSDavid du Colombier 		p += sizeof(BList);
1935e96a66cSDavid du Colombier 	}
19461201b97SDavid du Colombier 	/* separate loop to keep blocks and blists reasonably aligned */
19561201b97SDavid du Colombier 	for(i = 0; i < nblocks; i++){
19661201b97SDavid du Colombier 		b = &c->blocks[i];
19761201b97SDavid du Colombier 		b->dmap = p;
19861201b97SDavid du Colombier 		p += c->ndmap;
19961201b97SDavid du Colombier 	}
20061201b97SDavid du Colombier 
2015e96a66cSDavid du Colombier 	c->blrend = vtRendezAlloc(c->lk);
2025e96a66cSDavid du Colombier 
2035e96a66cSDavid du Colombier 	c->maxdirty = nblocks*(DirtyPercentage*0.01);
2045e96a66cSDavid du Colombier 
2055e96a66cSDavid du Colombier 	c->fl = flAlloc(diskSize(disk, PartData));
2065e96a66cSDavid du Colombier 
2075e96a66cSDavid du Colombier 	c->unlink = vtRendezAlloc(c->lk);
2085e96a66cSDavid du Colombier 	c->flush = vtRendezAlloc(c->lk);
2095e96a66cSDavid du Colombier 	c->flushwait = vtRendezAlloc(c->lk);
210*fe853e23SDavid du Colombier 	c->heapwait = vtRendezAlloc(c->lk);
21161201b97SDavid du Colombier 	c->sync = periodicAlloc(cacheSync, c, 30*1000);
2125e96a66cSDavid du Colombier 
2135e96a66cSDavid du Colombier 	if(mode == OReadWrite){
2145e96a66cSDavid du Colombier 		c->ref += 2;
2155e96a66cSDavid du Colombier 		vtThread(unlinkThread, c);
2165e96a66cSDavid du Colombier 		vtThread(flushThread, c);
2175e96a66cSDavid du Colombier 	}
2185e96a66cSDavid du Colombier 	cacheCheck(c);
2195e96a66cSDavid du Colombier 
2205e96a66cSDavid du Colombier 	return c;
2215e96a66cSDavid du Colombier }
2225e96a66cSDavid du Colombier 
2235e96a66cSDavid du Colombier /*
2245e96a66cSDavid du Colombier  * Free the whole memory cache, flushing all dirty blocks to the disk.
2255e96a66cSDavid du Colombier  */
2265e96a66cSDavid du Colombier void
2275e96a66cSDavid du Colombier cacheFree(Cache *c)
2285e96a66cSDavid du Colombier {
2295e96a66cSDavid du Colombier 	int i;
2305e96a66cSDavid du Colombier 
2315e96a66cSDavid du Colombier 	/* kill off daemon threads */
2325e96a66cSDavid du Colombier 	vtLock(c->lk);
2335e96a66cSDavid du Colombier 	c->die = vtRendezAlloc(c->lk);
23461201b97SDavid du Colombier 	periodicKill(c->sync);
2355e96a66cSDavid du Colombier 	vtWakeup(c->flush);
2365e96a66cSDavid du Colombier 	vtWakeup(c->unlink);
2375e96a66cSDavid du Colombier 	while(c->ref > 1)
2385e96a66cSDavid du Colombier 		vtSleep(c->die);
2395e96a66cSDavid du Colombier 
2405e96a66cSDavid du Colombier 	/* flush everything out */
2415e96a66cSDavid du Colombier 	do {
2425e96a66cSDavid du Colombier 		unlinkBody(c);
2435e96a66cSDavid du Colombier 		vtUnlock(c->lk);
2445e96a66cSDavid du Colombier 		while(cacheFlushBlock(c))
2455e96a66cSDavid du Colombier 			;
2465e96a66cSDavid du Colombier 		diskFlush(c->disk);
2475e96a66cSDavid du Colombier 		vtLock(c->lk);
2485e96a66cSDavid du Colombier 	} while(c->uhead || c->ndirty);
2495e96a66cSDavid du Colombier 	vtUnlock(c->lk);
2505e96a66cSDavid du Colombier 
2515e96a66cSDavid du Colombier 	cacheCheck(c);
2525e96a66cSDavid du Colombier 
2535e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
2545e96a66cSDavid du Colombier 		assert(c->blocks[i].ref == 0);
2555e96a66cSDavid du Colombier 		vtRendezFree(c->blocks[i].ioready);
2565e96a66cSDavid du Colombier 		vtLockFree(c->blocks[i].lk);
2575e96a66cSDavid du Colombier 	}
2585e96a66cSDavid du Colombier 	flFree(c->fl);
2595e96a66cSDavid du Colombier 	vtMemFree(c->baddr);
2605e96a66cSDavid du Colombier 	vtMemFree(c->heads);
2615e96a66cSDavid du Colombier 	vtMemFree(c->blocks);
2625e96a66cSDavid du Colombier 	vtMemFree(c->mem);
2635e96a66cSDavid du Colombier 	vtLockFree(c->lk);
2645e96a66cSDavid du Colombier 	diskFree(c->disk);
2655e96a66cSDavid du Colombier 	vtRendezFree(c->blrend);
2665e96a66cSDavid du Colombier 	/* don't close vtSession */
2675e96a66cSDavid du Colombier 	vtMemFree(c);
2685e96a66cSDavid du Colombier }
2695e96a66cSDavid du Colombier 
2705e96a66cSDavid du Colombier static void
2715e96a66cSDavid du Colombier cacheDump(Cache *c)
2725e96a66cSDavid du Colombier {
2735e96a66cSDavid du Colombier 	int i;
2745e96a66cSDavid du Colombier 	Block *b;
2755e96a66cSDavid du Colombier 
2765e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
2775e96a66cSDavid du Colombier 		b = &c->blocks[i];
278*fe853e23SDavid du Colombier 		fprint(2, "%d. p=%d a=%ud %V t=%d ref=%d state=%s io=%s pc=0x%lux\n",
279*fe853e23SDavid du Colombier 			i, b->part, b->addr, b->score, b->l.type, b->ref,
280*fe853e23SDavid du Colombier 			bsStr(b->l.state), bioStr(b->iostate), b->pc);
2815e96a66cSDavid du Colombier 	}
2825e96a66cSDavid du Colombier }
2835e96a66cSDavid du Colombier 
2845e96a66cSDavid du Colombier static void
2855e96a66cSDavid du Colombier cacheCheck(Cache *c)
2865e96a66cSDavid du Colombier {
2875e96a66cSDavid du Colombier 	u32int size, now;
2885e96a66cSDavid du Colombier 	int i, k, refed;
2895e96a66cSDavid du Colombier 	static uchar zero[VtScoreSize];
2905e96a66cSDavid du Colombier 	Block *b;
2915e96a66cSDavid du Colombier 
2925e96a66cSDavid du Colombier 	size = c->size;
2935e96a66cSDavid du Colombier 	now = c->now;
2945e96a66cSDavid du Colombier 
2955e96a66cSDavid du Colombier 	for(i = 0; i < c->nheap; i++){
2965e96a66cSDavid du Colombier 		if(c->heap[i]->heap != i)
2975e96a66cSDavid du Colombier 			vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
2985e96a66cSDavid du Colombier 		if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
2995e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
3005e96a66cSDavid du Colombier 		k = (i << 1) + 1;
3015e96a66cSDavid du Colombier 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
3025e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
3035e96a66cSDavid du Colombier 		k++;
3045e96a66cSDavid du Colombier 		if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
3055e96a66cSDavid du Colombier 			vtFatal("bad heap ordering");
3065e96a66cSDavid du Colombier 	}
3075e96a66cSDavid du Colombier 
3085e96a66cSDavid du Colombier 	refed = 0;
3095e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
3105e96a66cSDavid du Colombier 		b = &c->blocks[i];
3115e96a66cSDavid du Colombier 		if(b->data != &c->mem[i * size])
3125e96a66cSDavid du Colombier 			vtFatal("mis-blocked at %d", i);
3135e96a66cSDavid du Colombier 		if(b->ref && b->heap == BadHeap){
3145e96a66cSDavid du Colombier 			refed++;
3155e96a66cSDavid du Colombier 		}
3165e96a66cSDavid du Colombier 	}
3175e96a66cSDavid du Colombier if(c->nheap + refed != c->nblocks){
3185e96a66cSDavid du Colombier fprint(2, "cacheCheck: nheap %d refed %d nblocks %ld\n", c->nheap, refed, c->nblocks);
3195e96a66cSDavid du Colombier cacheDump(c);
3205e96a66cSDavid du Colombier }
3215e96a66cSDavid du Colombier 	assert(c->nheap + refed == c->nblocks);
3225e96a66cSDavid du Colombier 	refed = 0;
3235e96a66cSDavid du Colombier 	for(i = 0; i < c->nblocks; i++){
3245e96a66cSDavid du Colombier 		b = &c->blocks[i];
3255e96a66cSDavid du Colombier 		if(b->ref){
3265e96a66cSDavid 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);
3275e96a66cSDavid du Colombier 			refed++;
3285e96a66cSDavid du Colombier 		}
3295e96a66cSDavid du Colombier 	}
3305e96a66cSDavid du Colombier if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
3315e96a66cSDavid du Colombier }
3325e96a66cSDavid du Colombier 
3335e96a66cSDavid du Colombier 
3345e96a66cSDavid du Colombier /*
3355e96a66cSDavid du Colombier  * locate the block with the oldest second to last use.
3365e96a66cSDavid du Colombier  * remove it from the heap, and fix up the heap.
3375e96a66cSDavid du Colombier  */
3385e96a66cSDavid du Colombier /* called with c->lk held */
3395e96a66cSDavid du Colombier static Block *
3405e96a66cSDavid du Colombier cacheBumpBlock(Cache *c)
3415e96a66cSDavid du Colombier {
3425e96a66cSDavid du Colombier 	Block *b;
3435e96a66cSDavid du Colombier 
3445e96a66cSDavid du Colombier 	/*
3455e96a66cSDavid du Colombier 	 * locate the block with the oldest second to last use.
3465e96a66cSDavid du Colombier 	 * remove it from the heap, and fix up the heap.
3475e96a66cSDavid du Colombier 	 */
348*fe853e23SDavid du Colombier 	if(c->nheap == 0){
349*fe853e23SDavid du Colombier 		while(c->nheap == 0){
350*fe853e23SDavid du Colombier 			fprint(2, "entire cache is busy, %d dirty -- waking flush thread\n", c->ndirty);
351*fe853e23SDavid du Colombier 			vtWakeup(c->flush);
352*fe853e23SDavid du Colombier 			vtSleep(c->heapwait);
353*fe853e23SDavid du Colombier 		}
354*fe853e23SDavid du Colombier 		fprint(2, "cache is okay again\n");
355*fe853e23SDavid du Colombier 	}
356*fe853e23SDavid du Colombier 
3575e96a66cSDavid du Colombier 	b = c->heap[0];
3585e96a66cSDavid du Colombier 	heapDel(b);
3595e96a66cSDavid du Colombier 
3605e96a66cSDavid du Colombier 	assert(b->heap == BadHeap);
3615e96a66cSDavid du Colombier 	assert(b->ref == 0);
36261a5f0d0SDavid du Colombier 	assert(b->iostate != BioDirty && b->iostate != BioReading && b->iostate != BioWriting);
3635e96a66cSDavid du Colombier 	assert(b->prior == nil);
3645e96a66cSDavid du Colombier 	assert(b->uhead == nil);
3655e96a66cSDavid du Colombier 
3665e96a66cSDavid du Colombier 	/*
3675e96a66cSDavid du Colombier 	 * unchain the block from hash chain
3685e96a66cSDavid du Colombier 	 */
3695e96a66cSDavid du Colombier 	if(b->prev){
3705e96a66cSDavid du Colombier 		*(b->prev) = b->next;
3715e96a66cSDavid du Colombier 		if(b->next)
3725e96a66cSDavid du Colombier 			b->next->prev = b->prev;
3735e96a66cSDavid du Colombier 		b->prev = nil;
3745e96a66cSDavid du Colombier 	}
3755e96a66cSDavid du Colombier 
3765e96a66cSDavid du Colombier 
3775e96a66cSDavid du Colombier if(0)fprint(2, "droping %d:%x:%V\n", b->part, b->addr, b->score);
3785e96a66cSDavid du Colombier 	/* set block to a reasonable state */
3795e96a66cSDavid du Colombier 	b->ref = 1;
3805e96a66cSDavid du Colombier 	b->part = PartError;
3815e96a66cSDavid du Colombier 	memset(&b->l, 0, sizeof(b->l));
3825e96a66cSDavid du Colombier 	b->iostate = BioEmpty;
3835e96a66cSDavid du Colombier 
3845e96a66cSDavid du Colombier 	return b;
3855e96a66cSDavid du Colombier }
3865e96a66cSDavid du Colombier 
3875e96a66cSDavid du Colombier /*
3885e96a66cSDavid du Colombier  * look for a particular version of the block in the memory cache.
3895e96a66cSDavid du Colombier  */
3905e96a66cSDavid du Colombier static Block *
3915e96a66cSDavid du Colombier _cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers,
3925e96a66cSDavid du Colombier 	int waitlock, int *lockfailure)
3935e96a66cSDavid du Colombier {
3945e96a66cSDavid du Colombier 	Block *b;
3955e96a66cSDavid du Colombier 	ulong h;
3965e96a66cSDavid du Colombier 
3975e96a66cSDavid du Colombier 	h = addr % c->hashSize;
3985e96a66cSDavid du Colombier 
3995e96a66cSDavid du Colombier 	if(lockfailure)
4005e96a66cSDavid du Colombier 		*lockfailure = 0;
4015e96a66cSDavid du Colombier 
4025e96a66cSDavid du Colombier 	/*
4035e96a66cSDavid du Colombier 	 * look for the block in the cache
4045e96a66cSDavid du Colombier 	 */
4055e96a66cSDavid du Colombier 	vtLock(c->lk);
4065e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
4075e96a66cSDavid du Colombier 		if(b->part == part && b->addr == addr)
4085e96a66cSDavid du Colombier 			break;
4095e96a66cSDavid du Colombier 	}
4105e96a66cSDavid du Colombier 	if(b == nil || b->vers != vers){
4115e96a66cSDavid du Colombier 		vtUnlock(c->lk);
4125e96a66cSDavid du Colombier 		return nil;
4135e96a66cSDavid du Colombier 	}
4145e96a66cSDavid du Colombier 	if(!waitlock && !vtCanLock(b->lk)){
4155e96a66cSDavid du Colombier 		*lockfailure = 1;
4165e96a66cSDavid du Colombier 		vtUnlock(c->lk);
4175e96a66cSDavid du Colombier 		return nil;
4185e96a66cSDavid du Colombier 	}
4195e96a66cSDavid du Colombier 	heapDel(b);
4205e96a66cSDavid du Colombier 	b->ref++;
4215e96a66cSDavid du Colombier 	vtUnlock(c->lk);
4225e96a66cSDavid du Colombier 
4235e96a66cSDavid du Colombier 	bwatchLock(b);
4245e96a66cSDavid du Colombier 	if(waitlock)
4255e96a66cSDavid du Colombier 		vtLock(b->lk);
4265e96a66cSDavid du Colombier 	b->nlock = 1;
4275e96a66cSDavid du Colombier 
4285e96a66cSDavid du Colombier 	for(;;){
4295e96a66cSDavid du Colombier 		switch(b->iostate){
4305e96a66cSDavid du Colombier 		default:
4315e96a66cSDavid du Colombier 			abort();
4325e96a66cSDavid du Colombier 		case BioEmpty:
4335e96a66cSDavid du Colombier 		case BioLabel:
4345e96a66cSDavid du Colombier 		case BioClean:
4355e96a66cSDavid du Colombier 		case BioDirty:
4365e96a66cSDavid du Colombier 			if(b->vers != vers){
4375e96a66cSDavid du Colombier 				blockPut(b);
4385e96a66cSDavid du Colombier 				return nil;
4395e96a66cSDavid du Colombier 			}
4405e96a66cSDavid du Colombier 			return b;
4415e96a66cSDavid du Colombier 		case BioReading:
4425e96a66cSDavid du Colombier 		case BioWriting:
4435e96a66cSDavid du Colombier 			vtSleep(b->ioready);
4445e96a66cSDavid du Colombier 			break;
4455e96a66cSDavid du Colombier 		case BioVentiError:
4465e96a66cSDavid du Colombier 		case BioReadError:
4475e96a66cSDavid du Colombier 			blockPut(b);
4485e96a66cSDavid du Colombier 			vtSetError(EIO);
4495e96a66cSDavid du Colombier 			return nil;
4505e96a66cSDavid du Colombier 		}
4515e96a66cSDavid du Colombier 	}
4525e96a66cSDavid du Colombier 	/* NOT REACHED */
4535e96a66cSDavid du Colombier }
4545e96a66cSDavid du Colombier static Block*
4555e96a66cSDavid du Colombier cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers)
4565e96a66cSDavid du Colombier {
4575e96a66cSDavid du Colombier 	return _cacheLocalLookup(c, part, addr, vers, 1, 0);
4585e96a66cSDavid du Colombier }
4595e96a66cSDavid du Colombier 
4605e96a66cSDavid du Colombier 
4615e96a66cSDavid du Colombier /*
4625e96a66cSDavid du Colombier  * fetch a local (on-disk) block from the memory cache.
4635e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
4645e96a66cSDavid du Colombier  */
4655e96a66cSDavid du Colombier Block *
4665e96a66cSDavid du Colombier _cacheLocal(Cache *c, int part, u32int addr, int mode, u32int epoch)
4675e96a66cSDavid du Colombier {
4685e96a66cSDavid du Colombier 	Block *b;
4695e96a66cSDavid du Colombier 	ulong h;
4705e96a66cSDavid du Colombier 
4715e96a66cSDavid du Colombier 	assert(part != PartVenti);
4725e96a66cSDavid du Colombier 
4735e96a66cSDavid du Colombier 	h = addr % c->hashSize;
4745e96a66cSDavid du Colombier 
4755e96a66cSDavid du Colombier 	/*
4765e96a66cSDavid du Colombier 	 * look for the block in the cache
4775e96a66cSDavid du Colombier 	 */
4785e96a66cSDavid du Colombier 	vtLock(c->lk);
4795e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
4805e96a66cSDavid du Colombier 		if(b->part != part || b->addr != addr)
4815e96a66cSDavid du Colombier 			continue;
4825e96a66cSDavid du Colombier 		if(epoch && b->l.epoch != epoch){
4835e96a66cSDavid du Colombier fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
4845e96a66cSDavid du Colombier 			vtUnlock(c->lk);
4855e96a66cSDavid du Colombier 			vtSetError(ELabelMismatch);
4865e96a66cSDavid du Colombier 			return nil;
4875e96a66cSDavid du Colombier 		}
4885e96a66cSDavid du Colombier 		heapDel(b);
4895e96a66cSDavid du Colombier 		b->ref++;
4905e96a66cSDavid du Colombier 		break;
4915e96a66cSDavid du Colombier 	}
4925e96a66cSDavid du Colombier 
4935e96a66cSDavid du Colombier 	if(b == nil){
4945e96a66cSDavid du Colombier 		b = cacheBumpBlock(c);
4955e96a66cSDavid du Colombier 
4965e96a66cSDavid du Colombier 		b->part = part;
4975e96a66cSDavid du Colombier 		b->addr = addr;
4985e96a66cSDavid du Colombier 		localToGlobal(addr, b->score);
4995e96a66cSDavid du Colombier 
5005e96a66cSDavid du Colombier 		/* chain onto correct hash */
5015e96a66cSDavid du Colombier 		b->next = c->heads[h];
5025e96a66cSDavid du Colombier 		c->heads[h] = b;
5035e96a66cSDavid du Colombier 		if(b->next != nil)
5045e96a66cSDavid du Colombier 			b->next->prev = &b->next;
5055e96a66cSDavid du Colombier 		b->prev = &c->heads[h];
5065e96a66cSDavid du Colombier 	}
5075e96a66cSDavid du Colombier 
5085e96a66cSDavid du Colombier 	vtUnlock(c->lk);
5095e96a66cSDavid du Colombier 
5105e96a66cSDavid du Colombier 	/*
5115e96a66cSDavid du Colombier 	 * BUG: what if the epoch changes right here?
5125e96a66cSDavid du Colombier 	 * In the worst case, we could end up in some weird
5135e96a66cSDavid du Colombier 	 * lock loop, because the block we want no longer exists,
5145e96a66cSDavid du Colombier 	 * and instead we're trying to lock a block we have no
5155e96a66cSDavid du Colombier 	 * business grabbing.
5165e96a66cSDavid du Colombier 	 *
5175e96a66cSDavid du Colombier 	 * For now, I'm not going to worry about it.
5185e96a66cSDavid du Colombier 	 */
5195e96a66cSDavid du Colombier 
5205e96a66cSDavid du Colombier if(0)fprint(2, "cacheLocal: %d: %d %x\n", getpid(), b->part, b->addr);
5215e96a66cSDavid du Colombier 	bwatchLock(b);
5225e96a66cSDavid du Colombier 	vtLock(b->lk);
5235e96a66cSDavid du Colombier 	b->nlock = 1;
5245e96a66cSDavid du Colombier 
5255e96a66cSDavid du Colombier 	if(part == PartData && b->iostate == BioEmpty){
5265e96a66cSDavid du Colombier 		if(!readLabel(c, &b->l, addr)){
5275e96a66cSDavid du Colombier 			blockPut(b);
5285e96a66cSDavid du Colombier 			return nil;
5295e96a66cSDavid du Colombier 		}
5305e96a66cSDavid du Colombier 		blockSetIOState(b, BioLabel);
5315e96a66cSDavid du Colombier 	}
5325e96a66cSDavid du Colombier 	if(epoch && b->l.epoch != epoch){
5335e96a66cSDavid du Colombier 		blockPut(b);
5345e96a66cSDavid du Colombier fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
5355e96a66cSDavid du Colombier 		vtSetError(ELabelMismatch);
5365e96a66cSDavid du Colombier 		return nil;
5375e96a66cSDavid du Colombier 	}
5385e96a66cSDavid du Colombier 
5395e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
5405e96a66cSDavid du Colombier 	for(;;){
5415e96a66cSDavid du Colombier 		switch(b->iostate){
5425e96a66cSDavid du Colombier 		default:
5435e96a66cSDavid du Colombier 			abort();
5445e96a66cSDavid du Colombier 		case BioEmpty:
5455e96a66cSDavid du Colombier 		case BioLabel:
5465e96a66cSDavid du Colombier 			if(mode == OOverWrite){
5475e96a66cSDavid du Colombier 				blockSetIOState(b, BioClean);
5485e96a66cSDavid du Colombier 				return b;
5495e96a66cSDavid du Colombier 			}
5505e96a66cSDavid du Colombier 			diskRead(c->disk, b);
5515e96a66cSDavid du Colombier 			vtSleep(b->ioready);
5525e96a66cSDavid du Colombier 			break;
5535e96a66cSDavid du Colombier 		case BioClean:
5545e96a66cSDavid du Colombier 		case BioDirty:
5555e96a66cSDavid du Colombier 			return b;
5565e96a66cSDavid du Colombier 		case BioReading:
5575e96a66cSDavid du Colombier 		case BioWriting:
5585e96a66cSDavid du Colombier 			vtSleep(b->ioready);
5595e96a66cSDavid du Colombier 			break;
5605e96a66cSDavid du Colombier 		case BioReadError:
5615e96a66cSDavid du Colombier 			blockSetIOState(b, BioEmpty);
5625e96a66cSDavid du Colombier 			blockPut(b);
5635e96a66cSDavid du Colombier 			vtSetError(EIO);
5645e96a66cSDavid du Colombier 			return nil;
5655e96a66cSDavid du Colombier 		}
5665e96a66cSDavid du Colombier 	}
5675e96a66cSDavid du Colombier 	/* NOT REACHED */
5685e96a66cSDavid du Colombier }
5695e96a66cSDavid du Colombier 
5705e96a66cSDavid du Colombier Block *
5715e96a66cSDavid du Colombier cacheLocal(Cache *c, int part, u32int addr, int mode)
5725e96a66cSDavid du Colombier {
5735e96a66cSDavid du Colombier 	return _cacheLocal(c, part, addr, mode, 0);
5745e96a66cSDavid du Colombier }
5755e96a66cSDavid du Colombier 
5765e96a66cSDavid du Colombier /*
5775e96a66cSDavid du Colombier  * fetch a local (on-disk) block from the memory cache.
5785e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
5795e96a66cSDavid du Colombier  * check tag and type.
5805e96a66cSDavid du Colombier  */
5815e96a66cSDavid du Colombier Block *
5825e96a66cSDavid du Colombier cacheLocalData(Cache *c, u32int addr, int type, u32int tag, int mode, u32int epoch)
5835e96a66cSDavid du Colombier {
5845e96a66cSDavid du Colombier 	Block *b;
5855e96a66cSDavid du Colombier 
5865e96a66cSDavid du Colombier 	b = _cacheLocal(c, PartData, addr, mode, epoch);
5875e96a66cSDavid du Colombier 	if(b == nil)
5885e96a66cSDavid du Colombier 		return nil;
5895e96a66cSDavid du Colombier 	if(b->l.type != type || b->l.tag != tag){
590*fe853e23SDavid du Colombier 		fprint(2, "cacheLocalData: addr=%d type got %d exp %d: tag got %ux exp %ux\n",
5915e96a66cSDavid du Colombier 			addr, b->l.type, type, b->l.tag, tag);
5925e96a66cSDavid du Colombier 		vtSetError(ELabelMismatch);
5935e96a66cSDavid du Colombier 		blockPut(b);
5945e96a66cSDavid du Colombier 		return nil;
5955e96a66cSDavid du Colombier 	}
5965e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
5975e96a66cSDavid du Colombier 	return b;
5985e96a66cSDavid du Colombier }
5995e96a66cSDavid du Colombier 
6005e96a66cSDavid du Colombier /*
6015e96a66cSDavid du Colombier  * fetch a global (Venti) block from the memory cache.
6025e96a66cSDavid du Colombier  * if it's not there, load it, bumping some other block.
6035e96a66cSDavid du Colombier  * check tag and type if it's really a local block in disguise.
6045e96a66cSDavid du Colombier  */
6055e96a66cSDavid du Colombier Block *
6065e96a66cSDavid du Colombier cacheGlobal(Cache *c, uchar score[VtScoreSize], int type, u32int tag, int mode)
6075e96a66cSDavid du Colombier {
6085e96a66cSDavid du Colombier 	int n;
6095e96a66cSDavid du Colombier 	Block *b;
6105e96a66cSDavid du Colombier 	ulong h;
6115e96a66cSDavid du Colombier 	u32int addr;
6125e96a66cSDavid du Colombier 
6135e96a66cSDavid du Colombier 	addr = globalToLocal(score);
6145e96a66cSDavid du Colombier 	if(addr != NilBlock){
6155e96a66cSDavid du Colombier 		b = cacheLocalData(c, addr, type, tag, mode, 0);
6165e96a66cSDavid du Colombier 		if(b)
6175e96a66cSDavid du Colombier 			b->pc = getcallerpc(&c);
6185e96a66cSDavid du Colombier 		return b;
6195e96a66cSDavid du Colombier 	}
6205e96a66cSDavid du Colombier 
6215e96a66cSDavid du Colombier 	h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->hashSize;
6225e96a66cSDavid du Colombier 
6235e96a66cSDavid du Colombier 	/*
6245e96a66cSDavid du Colombier 	 * look for the block in the cache
6255e96a66cSDavid du Colombier 	 */
6265e96a66cSDavid du Colombier 	vtLock(c->lk);
6275e96a66cSDavid du Colombier 	for(b = c->heads[h]; b != nil; b = b->next){
6285e96a66cSDavid du Colombier 		if(b->part != PartVenti || memcmp(b->score, score, VtScoreSize) != 0 || b->l.type != type)
6295e96a66cSDavid du Colombier 			continue;
6305e96a66cSDavid du Colombier 		heapDel(b);
6315e96a66cSDavid du Colombier 		b->ref++;
6325e96a66cSDavid du Colombier 		break;
6335e96a66cSDavid du Colombier 	}
6345e96a66cSDavid du Colombier 
6355e96a66cSDavid du Colombier 	if(b == nil){
6365e96a66cSDavid du Colombier if(0)fprint(2, "cacheGlobal %V %d\n", score, type);
6375e96a66cSDavid du Colombier 
6385e96a66cSDavid du Colombier 		b = cacheBumpBlock(c);
6395e96a66cSDavid du Colombier 
6405e96a66cSDavid du Colombier 		b->part = PartVenti;
6415e96a66cSDavid du Colombier 		b->addr = NilBlock;
6425e96a66cSDavid du Colombier 		b->l.type = type;
6435e96a66cSDavid du Colombier 		memmove(b->score, score, VtScoreSize);
6445e96a66cSDavid du Colombier 
6455e96a66cSDavid du Colombier 		/* chain onto correct hash */
6465e96a66cSDavid du Colombier 		b->next = c->heads[h];
6475e96a66cSDavid du Colombier 		c->heads[h] = b;
6485e96a66cSDavid du Colombier 		if(b->next != nil)
6495e96a66cSDavid du Colombier 			b->next->prev = &b->next;
6505e96a66cSDavid du Colombier 		b->prev = &c->heads[h];
6515e96a66cSDavid du Colombier 	}
6525e96a66cSDavid du Colombier 	vtUnlock(c->lk);
6535e96a66cSDavid du Colombier 
6545e96a66cSDavid du Colombier 	bwatchLock(b);
6555e96a66cSDavid du Colombier 	vtLock(b->lk);
6565e96a66cSDavid du Colombier 	b->nlock = 1;
6575e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
6585e96a66cSDavid du Colombier 
6595e96a66cSDavid du Colombier 	switch(b->iostate){
6605e96a66cSDavid du Colombier 	default:
6615e96a66cSDavid du Colombier 		abort();
6625e96a66cSDavid du Colombier 	case BioEmpty:
6635e96a66cSDavid du Colombier 		n = vtRead(c->z, score, vtType[type], b->data, c->size);
6645e96a66cSDavid du Colombier 		if(n < 0 || !vtSha1Check(score, b->data, n)){
6655e96a66cSDavid du Colombier 			blockSetIOState(b, BioVentiError);
6665e96a66cSDavid du Colombier 			blockPut(b);
66761a5f0d0SDavid du Colombier 			vtSetError(EIO);
6685e96a66cSDavid du Colombier 			return nil;
6695e96a66cSDavid du Colombier 		}
6705e96a66cSDavid du Colombier 		vtZeroExtend(vtType[type], b->data, n, c->size);
6715e96a66cSDavid du Colombier 		blockSetIOState(b, BioClean);
6725e96a66cSDavid du Colombier 		return b;
6735e96a66cSDavid du Colombier 	case BioClean:
6745e96a66cSDavid du Colombier 		return b;
6755e96a66cSDavid du Colombier 	case BioVentiError:
6765e96a66cSDavid du Colombier 	case BioReadError:
6775e96a66cSDavid du Colombier 		blockPut(b);
6785e96a66cSDavid du Colombier 		vtSetError(EIO);
6795e96a66cSDavid du Colombier 		return nil;
6805e96a66cSDavid du Colombier 	}
6815e96a66cSDavid du Colombier 	/* NOT REACHED */
6825e96a66cSDavid du Colombier }
6835e96a66cSDavid du Colombier 
6845e96a66cSDavid du Colombier /*
6855e96a66cSDavid du Colombier  * allocate a new on-disk block and load it into the memory cache.
6865e96a66cSDavid du Colombier  * BUG: if the disk is full, should we flush some of it to Venti?
6875e96a66cSDavid du Colombier  */
6885e96a66cSDavid du Colombier static u32int lastAlloc;
6895e96a66cSDavid du Colombier 
6905e96a66cSDavid du Colombier Block *
6915e96a66cSDavid du Colombier cacheAllocBlock(Cache *c, int type, u32int tag, u32int epoch, u32int epochLow)
6925e96a66cSDavid du Colombier {
6935e96a66cSDavid du Colombier 	FreeList *fl;
6945e96a66cSDavid du Colombier 	u32int addr;
6955e96a66cSDavid du Colombier 	Block *b;
6965e96a66cSDavid du Colombier 	int n, nwrap;
6975e96a66cSDavid du Colombier 	Label lab;
6985e96a66cSDavid du Colombier 
6995e96a66cSDavid du Colombier 	n = c->size / LabelSize;
7005e96a66cSDavid du Colombier 	fl = c->fl;
7015e96a66cSDavid du Colombier 
7025e96a66cSDavid du Colombier 	vtLock(fl->lk);
7035e96a66cSDavid du Colombier 	addr = fl->last;
7045e96a66cSDavid du Colombier 	b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
7055e96a66cSDavid du Colombier 	if(b == nil){
7065e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx %R\n");
7075e96a66cSDavid du Colombier 		vtUnlock(fl->lk);
7085e96a66cSDavid du Colombier 		return nil;
7095e96a66cSDavid du Colombier 	}
7105e96a66cSDavid du Colombier 	nwrap = 0;
7115e96a66cSDavid du Colombier 	for(;;){
7125e96a66cSDavid du Colombier 		if(++addr >= fl->end){
7135e96a66cSDavid du Colombier 			addr = 0;
7145e96a66cSDavid du Colombier 			if(++nwrap >= 2){
7155e96a66cSDavid du Colombier 				blockPut(b);
7165e96a66cSDavid du Colombier 				fl->last = 0;
7175e96a66cSDavid du Colombier 				vtSetError("disk is full");
7185e96a66cSDavid du Colombier 				fprint(2, "cacheAllocBlock: xxx1 %R\n");
7195e96a66cSDavid du Colombier 				vtUnlock(fl->lk);
7205e96a66cSDavid du Colombier 				return nil;
7215e96a66cSDavid du Colombier 			}
7225e96a66cSDavid du Colombier 		}
7235e96a66cSDavid du Colombier 		if(addr%n == 0){
7245e96a66cSDavid du Colombier 			blockPut(b);
7255e96a66cSDavid du Colombier 			b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
7265e96a66cSDavid du Colombier 			if(b == nil){
7275e96a66cSDavid du Colombier 				fl->last = addr;
7285e96a66cSDavid du Colombier 				fprint(2, "cacheAllocBlock: xxx2 %R\n");
7295e96a66cSDavid du Colombier 				vtUnlock(fl->lk);
7305e96a66cSDavid du Colombier 				return nil;
7315e96a66cSDavid du Colombier 			}
7325e96a66cSDavid du Colombier 		}
7335e96a66cSDavid du Colombier 		if(!labelUnpack(&lab, b->data, addr%n))
7345e96a66cSDavid du Colombier 			continue;
7355e96a66cSDavid du Colombier 		if(lab.state == BsFree)
7365e96a66cSDavid du Colombier 			goto Found;
7375e96a66cSDavid du Colombier 		if((lab.state&BsClosed) && lab.epochClose <= epochLow)
7385e96a66cSDavid du Colombier 			goto Found;
7395e96a66cSDavid du Colombier 	}
7405e96a66cSDavid du Colombier Found:
7415e96a66cSDavid du Colombier 	blockPut(b);
7425e96a66cSDavid du Colombier 	b = cacheLocal(c, PartData, addr, OOverWrite);
7435e96a66cSDavid du Colombier 	if(b == nil){
7445e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx3 %R\n");
7455e96a66cSDavid du Colombier 		return nil;
7465e96a66cSDavid du Colombier 	}
7475e96a66cSDavid du Colombier assert(b->iostate == BioLabel || b->iostate == BioClean);
7485e96a66cSDavid du Colombier 	fl->last = addr;
7495e96a66cSDavid du Colombier 	lab.type = type;
7505e96a66cSDavid du Colombier 	lab.tag = tag;
7515e96a66cSDavid du Colombier 	lab.state = BsAlloc;
7525e96a66cSDavid du Colombier 	lab.epoch = epoch;
7535e96a66cSDavid du Colombier 	lab.epochClose = ~(u32int)0;
7545e96a66cSDavid du Colombier 	if(!blockSetLabel(b, &lab)){
7555e96a66cSDavid du Colombier 		fprint(2, "cacheAllocBlock: xxx4 %R\n");
7565e96a66cSDavid du Colombier 		blockPut(b);
7575e96a66cSDavid du Colombier 		return nil;
7585e96a66cSDavid du Colombier 	}
7595e96a66cSDavid du Colombier 	vtZeroExtend(vtType[type], b->data, 0, c->size);
7605e96a66cSDavid du Colombier if(0)diskWrite(c->disk, b);
7615e96a66cSDavid du Colombier 
7625e96a66cSDavid du Colombier if(0)fprint(2, "fsAlloc %ud type=%d tag = %ux\n", addr, type, tag);
7635e96a66cSDavid du Colombier 	lastAlloc = addr;
7647abd426fSDavid du Colombier 	fl->nused++;
7655e96a66cSDavid du Colombier 	vtUnlock(fl->lk);
7665e96a66cSDavid du Colombier 	b->pc = getcallerpc(&c);
7675e96a66cSDavid du Colombier 	return b;
7685e96a66cSDavid du Colombier }
7695e96a66cSDavid du Colombier 
7707abd426fSDavid du Colombier void
7717abd426fSDavid du Colombier cacheCountUsed(Cache *c, u32int epochLow, u32int *used, u32int *total, u32int *bsize)
7727abd426fSDavid du Colombier {
7737abd426fSDavid du Colombier 	int n;
7747abd426fSDavid du Colombier 	u32int addr, nused;
7757abd426fSDavid du Colombier 	Block *b;
7767abd426fSDavid du Colombier 	Label lab;
7777abd426fSDavid du Colombier 	FreeList *fl;
7787abd426fSDavid du Colombier 
7797abd426fSDavid du Colombier 	fl = c->fl;
7807abd426fSDavid du Colombier 	n = c->size / LabelSize;
7817abd426fSDavid du Colombier 	*bsize = c->size;
7827abd426fSDavid du Colombier 	vtLock(fl->lk);
7837abd426fSDavid du Colombier 	if(fl->epochLow == epochLow){
7847abd426fSDavid du Colombier 		*used = fl->nused;
7857abd426fSDavid du Colombier 		*total = fl->end;
7867abd426fSDavid du Colombier 		vtUnlock(fl->lk);
7877abd426fSDavid du Colombier 		return;
7887abd426fSDavid du Colombier 	}
7897abd426fSDavid du Colombier 	b = nil;
7907abd426fSDavid du Colombier 	nused = 0;
7917abd426fSDavid du Colombier 	for(addr=0; addr<fl->end; addr++){
7927abd426fSDavid du Colombier 		if(addr%n == 0){
7937abd426fSDavid du Colombier 			blockPut(b);
7947abd426fSDavid du Colombier 			b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
7957abd426fSDavid du Colombier 			if(b == nil){
7967abd426fSDavid du Colombier 				fprint(2, "flCountUsed: loading %ux: %R\n", addr/n);
7977abd426fSDavid du Colombier 				break;
7987abd426fSDavid du Colombier 			}
7997abd426fSDavid du Colombier 		}
8007abd426fSDavid du Colombier 		if(!labelUnpack(&lab, b->data, addr%n))
8017abd426fSDavid du Colombier 			continue;
8027abd426fSDavid du Colombier 		if(lab.state == BsFree)
8037abd426fSDavid du Colombier 			continue;
8047abd426fSDavid du Colombier 		if((lab.state&BsClosed) && lab.epochClose <= epochLow)
8057abd426fSDavid du Colombier 			continue;
8067abd426fSDavid du Colombier 		nused++;
8077abd426fSDavid du Colombier 	}
8087abd426fSDavid du Colombier 	blockPut(b);
8097abd426fSDavid du Colombier 	if(addr == fl->end){
8107abd426fSDavid du Colombier 		fl->nused = nused;
8117abd426fSDavid du Colombier 		fl->epochLow = epochLow;
8127abd426fSDavid du Colombier 	}
8137abd426fSDavid du Colombier 	*used = nused;
8147abd426fSDavid du Colombier 	*total = fl->end;
8157abd426fSDavid du Colombier 	vtUnlock(fl->lk);
8167abd426fSDavid du Colombier 	return;
8177abd426fSDavid du Colombier }
8187abd426fSDavid du Colombier 
8195e96a66cSDavid du Colombier static FreeList *
8205e96a66cSDavid du Colombier flAlloc(u32int end)
8215e96a66cSDavid du Colombier {
8225e96a66cSDavid du Colombier 	FreeList *fl;
8235e96a66cSDavid du Colombier 
8245e96a66cSDavid du Colombier 	fl = vtMemAllocZ(sizeof(*fl));
8255e96a66cSDavid du Colombier 	fl->lk = vtLockAlloc();
826b5e190f4SDavid du Colombier 	fl->last = 0;
8275e96a66cSDavid du Colombier 	fl->end = end;
8285e96a66cSDavid du Colombier 	return fl;
8295e96a66cSDavid du Colombier }
8305e96a66cSDavid du Colombier 
8315e96a66cSDavid du Colombier static void
8325e96a66cSDavid du Colombier flFree(FreeList *fl)
8335e96a66cSDavid du Colombier {
8345e96a66cSDavid du Colombier 	vtLockFree(fl->lk);
8355e96a66cSDavid du Colombier 	vtMemFree(fl);
8365e96a66cSDavid du Colombier }
8375e96a66cSDavid du Colombier 
8385e96a66cSDavid du Colombier u32int
8395e96a66cSDavid du Colombier cacheLocalSize(Cache *c, int part)
8405e96a66cSDavid du Colombier {
8415e96a66cSDavid du Colombier 	return diskSize(c->disk, part);
8425e96a66cSDavid du Colombier }
8435e96a66cSDavid du Colombier 
8445e96a66cSDavid du Colombier /*
8455e96a66cSDavid du Colombier  * Copy on write.  Copied blocks have to be marked BaCopy.
8465e96a66cSDavid du Colombier  * See the big comment near blockRemoveLink.
8475e96a66cSDavid du Colombier  */
8485e96a66cSDavid du Colombier Block*
8495e96a66cSDavid du Colombier blockCopy(Block *b, u32int tag, u32int ehi, u32int elo)
8505e96a66cSDavid du Colombier {
8515e96a66cSDavid du Colombier 	Block *bb, *lb;
8525e96a66cSDavid du Colombier 	Label l;
8535e96a66cSDavid du Colombier 
8545e96a66cSDavid du Colombier 	assert((b->l.state&BsClosed)==0 && b->l.epoch < ehi);
8555e96a66cSDavid du Colombier 	bb = cacheAllocBlock(b->c, b->l.type, tag, ehi, elo);
8565e96a66cSDavid du Colombier 	if(bb == nil){
8575e96a66cSDavid du Colombier 		blockPut(b);
8585e96a66cSDavid du Colombier 		return nil;
8595e96a66cSDavid du Colombier 	}
8605e96a66cSDavid du Colombier 
8617abd426fSDavid du Colombier //fprint(2, "alloc %lux copy %V\n", bb->addr, b->score);
8625e96a66cSDavid du Colombier 	/*
8635e96a66cSDavid du Colombier 	 * Change label on b to mark that we've copied it.
8645e96a66cSDavid du Colombier 	 * This has to come after cacheAllocBlock, since we
8655e96a66cSDavid du Colombier 	 * can't hold any labels blocks (lb) while we try to
8665e96a66cSDavid du Colombier 	 * fetch others (in cacheAllocBlock).
8675e96a66cSDavid du Colombier 	 */
8685e96a66cSDavid du Colombier 	if(!(b->l.state&BsCopied) && b->part==PartData){
8695e96a66cSDavid du Colombier 		l = b->l;
8705e96a66cSDavid du Colombier 		l.state |= BsCopied;
8715e96a66cSDavid du Colombier 		lb = _blockSetLabel(b, &l);
8725e96a66cSDavid du Colombier 		if(lb == nil){
8735e96a66cSDavid du Colombier 			/* can't set label => can't copy block */
8745e96a66cSDavid du Colombier 			blockPut(b);
8755e96a66cSDavid du Colombier 			l.type = BtMax;
8765e96a66cSDavid du Colombier 			l.state = BsFree;
8775e96a66cSDavid du Colombier 			l.epoch = 0;
8785e96a66cSDavid du Colombier 			l.epochClose = 0;
8795e96a66cSDavid du Colombier 			l.tag = 0;
8805e96a66cSDavid du Colombier 			/* ignore error: block gets lost on error */
8815e96a66cSDavid du Colombier 			blockSetLabel(bb, &l);
8825e96a66cSDavid du Colombier 			blockPut(bb);
8835e96a66cSDavid du Colombier 			return nil;
8845e96a66cSDavid du Colombier 		}
88561201b97SDavid du Colombier 		blockDependency(bb, lb, -1, nil, nil);
8865e96a66cSDavid du Colombier 		blockPut(lb);
8875e96a66cSDavid du Colombier 	}
8885e96a66cSDavid du Colombier 
8895e96a66cSDavid du Colombier 	if(0){
8905e96a66cSDavid du Colombier 		if(b->addr != NilBlock)
8915e96a66cSDavid du Colombier 			fprint(2, "blockCopy %#ux/%ud => %#ux/%ud\n",
8925e96a66cSDavid du Colombier 				b->addr, b->l.epoch, bb->addr, bb->l.epoch);
8935e96a66cSDavid du Colombier 		else if(memcmp(b->score, vtZeroScore, VtScoreSize) != 0)
8945e96a66cSDavid du Colombier 			fprint(2, "blockCopy %V => %#ux/%ud\n",
8955e96a66cSDavid du Colombier 				b->score, bb->addr, bb->l.epoch);
8965e96a66cSDavid du Colombier 	}
8975e96a66cSDavid du Colombier 
8985e96a66cSDavid du Colombier 	memmove(bb->data, b->data, b->c->size);
8995e96a66cSDavid du Colombier 	blockDirty(bb);
9005e96a66cSDavid du Colombier 	blockPut(b);
9015e96a66cSDavid du Colombier 	return bb;
9025e96a66cSDavid du Colombier }
9035e96a66cSDavid du Colombier 
9045e96a66cSDavid du Colombier /*
9055e96a66cSDavid du Colombier  * The thread that has locked b may refer to it by
9065e96a66cSDavid du Colombier  * multiple names.  Nlock counts the number of
9075e96a66cSDavid du Colombier  * references the locking thread holds.  It will call
9085e96a66cSDavid du Colombier  * blockPut once per reference.
9095e96a66cSDavid du Colombier  */
9105e96a66cSDavid du Colombier void
9115e96a66cSDavid du Colombier blockDupLock(Block *b)
9125e96a66cSDavid du Colombier {
9135e96a66cSDavid du Colombier 	assert(b->nlock > 0);
9145e96a66cSDavid du Colombier 	b->nlock++;
9155e96a66cSDavid du Colombier }
9165e96a66cSDavid du Colombier 
9175e96a66cSDavid du Colombier /*
9185e96a66cSDavid du Colombier  * we're done with the block.
9195e96a66cSDavid du Colombier  * unlock it.  can't use it after calling this.
9205e96a66cSDavid du Colombier  */
9215e96a66cSDavid du Colombier void
9225e96a66cSDavid du Colombier blockPut(Block* b)
9235e96a66cSDavid du Colombier {
9245e96a66cSDavid du Colombier 	Cache *c;
9255e96a66cSDavid du Colombier 
9265e96a66cSDavid du Colombier 	if(b == nil)
9275e96a66cSDavid du Colombier 		return;
9285e96a66cSDavid du Colombier 
9295e96a66cSDavid du Colombier if(0)fprint(2, "blockPut: %d: %d %x %d %s\n", getpid(), b->part, b->addr, c->nheap, bioStr(b->iostate));
9305e96a66cSDavid du Colombier 
9315e96a66cSDavid du Colombier 	if(b->iostate == BioDirty)
9325e96a66cSDavid du Colombier 		bwatchDependency(b);
9335e96a66cSDavid du Colombier 
9345e96a66cSDavid du Colombier 	if(--b->nlock > 0)
9355e96a66cSDavid du Colombier 		return;
9365e96a66cSDavid du Colombier 
9375e96a66cSDavid du Colombier 	/*
9385e96a66cSDavid du Colombier 	 * b->nlock should probably stay at zero while
9395e96a66cSDavid du Colombier 	 * the block is unlocked, but diskThread and vtSleep
9405e96a66cSDavid du Colombier 	 * conspire to assume that they can just vtLock(b->lk); blockPut(b),
9415e96a66cSDavid du Colombier 	 * so we have to keep b->nlock set to 1 even
9425e96a66cSDavid du Colombier 	 * when the block is unlocked.
9435e96a66cSDavid du Colombier 	 */
9445e96a66cSDavid du Colombier 	assert(b->nlock == 0);
9455e96a66cSDavid du Colombier 	b->nlock = 1;
9465e96a66cSDavid du Colombier //	b->pc = 0;
9475e96a66cSDavid du Colombier 
9485e96a66cSDavid du Colombier 	bwatchUnlock(b);
9495e96a66cSDavid du Colombier 	vtUnlock(b->lk);
9505e96a66cSDavid du Colombier 	c = b->c;
9515e96a66cSDavid du Colombier 	vtLock(c->lk);
9525e96a66cSDavid du Colombier 
9535e96a66cSDavid du Colombier 	if(--b->ref > 0){
9545e96a66cSDavid du Colombier 		vtUnlock(c->lk);
9555e96a66cSDavid du Colombier 		return;
9565e96a66cSDavid du Colombier 	}
9575e96a66cSDavid du Colombier 
9585e96a66cSDavid du Colombier 	assert(b->ref == 0);
9595e96a66cSDavid du Colombier 	switch(b->iostate){
9605e96a66cSDavid du Colombier 	default:
9615e96a66cSDavid du Colombier 		b->used = c->now++;
9625e96a66cSDavid du Colombier 		heapIns(b);
9635e96a66cSDavid du Colombier 		break;
9645e96a66cSDavid du Colombier 	case BioEmpty:
9655e96a66cSDavid du Colombier 	case BioLabel:
9665e96a66cSDavid du Colombier 		if(c->nheap == 0)
9675e96a66cSDavid du Colombier 			b->used = c->now++;
9685e96a66cSDavid du Colombier 		else
9695e96a66cSDavid du Colombier 			b->used = c->heap[0]->used;
9705e96a66cSDavid du Colombier 		heapIns(b);
9715e96a66cSDavid du Colombier 		break;
9725e96a66cSDavid du Colombier 	case BioDirty:
9735e96a66cSDavid du Colombier 		break;
9745e96a66cSDavid du Colombier 	}
9755e96a66cSDavid du Colombier 	vtUnlock(c->lk);
9765e96a66cSDavid du Colombier }
9775e96a66cSDavid du Colombier 
9785e96a66cSDavid du Colombier /*
9795e96a66cSDavid du Colombier  * we're deleting a block; delete all the blocks it points to
9805e96a66cSDavid du Colombier  * that are still active (i.e., not needed by snapshots).
9815e96a66cSDavid du Colombier  */
9825e96a66cSDavid du Colombier static void
9835e96a66cSDavid du Colombier blockCleanup(Block *b, u32int epoch)
9845e96a66cSDavid du Colombier {
9855e96a66cSDavid du Colombier 	Cache *c;
9865e96a66cSDavid du Colombier 	Block *bb;
9875e96a66cSDavid du Colombier 	int i, n;
9885e96a66cSDavid du Colombier 	Label l;
9895e96a66cSDavid du Colombier 	u32int a;
9905e96a66cSDavid du Colombier 	int type;
9915e96a66cSDavid du Colombier 	int mode;
9925e96a66cSDavid du Colombier 
9935e96a66cSDavid du Colombier 	type = b->l.type;
9945e96a66cSDavid du Colombier 	c = b->c;
9955e96a66cSDavid du Colombier 
9965e96a66cSDavid du Colombier 	bwatchReset(b->score);
9975e96a66cSDavid du Colombier 
9985e96a66cSDavid du Colombier 	blockSetIOState(b, BioClean);
9995e96a66cSDavid du Colombier 
10005e96a66cSDavid du Colombier 	/* do not recursively free directories */
10015e96a66cSDavid du Colombier 	if(type == BtData || type == BtDir)
10025e96a66cSDavid du Colombier 		return;
10035e96a66cSDavid du Colombier 
10045e96a66cSDavid du Colombier 	n = c->size / VtScoreSize;
10055e96a66cSDavid du Colombier 	mode = OReadWrite;
10065e96a66cSDavid du Colombier 	if(type-1 == BtData || type-1 == BtDir)
10075e96a66cSDavid du Colombier 		mode = OOverWrite;
10085e96a66cSDavid du Colombier 	for(i=0; i<n; i++){
10095e96a66cSDavid du Colombier 		a = globalToLocal(b->data + i*VtScoreSize);
10105e96a66cSDavid du Colombier 		if(a == NilBlock || !readLabel(c, &l, a))
10115e96a66cSDavid du Colombier 			continue;
10125e96a66cSDavid du Colombier 		if((l.state&BsClosed) || l.epoch != epoch)
10135e96a66cSDavid du Colombier 			continue;
10145e96a66cSDavid du Colombier 		bb = cacheLocalData(c, a, type-1, b->l.tag, mode, 0);
10155e96a66cSDavid du Colombier 		if(bb == nil)
10165e96a66cSDavid du Colombier 			continue;
10175e96a66cSDavid du Colombier 		if((bb->l.state&BsClosed) || bb->l.epoch != epoch){
10185e96a66cSDavid du Colombier 			fprint(2, "cleanupBlock: block %ud changed underfoot! expected %L got %L\n",
10195e96a66cSDavid du Colombier 				a, &l, &bb->l);
10205e96a66cSDavid du Colombier 			blockPut(bb);
10215e96a66cSDavid du Colombier 			continue;
10225e96a66cSDavid du Colombier 		}
10235e96a66cSDavid du Colombier 		blockCleanup(bb, epoch);
10245e96a66cSDavid du Colombier 		l.type = BtMax;
10255e96a66cSDavid du Colombier 		l.epoch = epoch;
10265e96a66cSDavid du Colombier 		l.epochClose = 0;
10275e96a66cSDavid du Colombier 		l.state = BsFree;
10285e96a66cSDavid du Colombier 		l.tag = 0;
10295e96a66cSDavid du Colombier 		blockSetLabel(bb, &l);
10305e96a66cSDavid du Colombier 		blockPut(bb);
10315e96a66cSDavid du Colombier 	}
10325e96a66cSDavid du Colombier }
10335e96a66cSDavid du Colombier 
10345e96a66cSDavid du Colombier /*
10355e96a66cSDavid du Colombier  * We don't need the block at addr anymore for the active file system.
10365e96a66cSDavid du Colombier  * If we don't need it for the snapshots, remove it completely.
10375e96a66cSDavid du Colombier  * Epoch is the epoch during which we got rid of the block.
10385e96a66cSDavid du Colombier  * See blockRemoveLink for more.
10395e96a66cSDavid du Colombier  */
10405e96a66cSDavid du Colombier static int
10415e96a66cSDavid du Colombier unlinkBlock(Cache *c, u32int addr, int type, u32int tag, u32int epoch)
10425e96a66cSDavid du Colombier {
10435e96a66cSDavid du Colombier 	Block *b;
10445e96a66cSDavid du Colombier 	Label l;
10455e96a66cSDavid du Colombier 
10465e96a66cSDavid du Colombier 	if(addr == NilBlock)
10475e96a66cSDavid du Colombier 		return 1;
10485e96a66cSDavid du Colombier 
10495e96a66cSDavid du Colombier //fprint(2, "unlinkBlock %#ux\n", addr);
10505e96a66cSDavid du Colombier 	b = cacheLocalData(c, addr, type, tag, OReadOnly, 0);
10515e96a66cSDavid du Colombier 	if(b == nil)
10525e96a66cSDavid du Colombier 		return 0;
10535e96a66cSDavid du Colombier 	if(b->l.epoch > epoch){
10545e96a66cSDavid du Colombier fprint(2, "unlinkBlock: strange epoch :%ud %ud\n", b->l.epoch, epoch);
10555e96a66cSDavid du Colombier 		blockPut(b);
10565e96a66cSDavid du Colombier 		return 0;
10575e96a66cSDavid du Colombier 	}
10585e96a66cSDavid du Colombier 
10595e96a66cSDavid du Colombier 	l = b->l;
10605e96a66cSDavid du Colombier 	if((b->l.state&BsClosed)==0 && b->l.epoch==epoch){
10615e96a66cSDavid du Colombier 		l.state = BsFree;
10625e96a66cSDavid du Colombier 		l.type = BtMax;
10635e96a66cSDavid du Colombier 		l.tag = 0;
10645e96a66cSDavid du Colombier 		l.epoch = 0;
10655e96a66cSDavid du Colombier 		l.epochClose = 0;
10665e96a66cSDavid du Colombier 		blockCleanup(b, epoch);
10675e96a66cSDavid du Colombier 	}else{
10685e96a66cSDavid du Colombier 		l.state |= BsClosed;
10695e96a66cSDavid du Colombier 		l.epochClose = epoch;
10705e96a66cSDavid du Colombier 	}
10715e96a66cSDavid du Colombier 	blockSetLabel(b, &l);
10725e96a66cSDavid du Colombier 	blockPut(b);
10735e96a66cSDavid du Colombier 	return 1;
10745e96a66cSDavid du Colombier }
10755e96a66cSDavid du Colombier 
10765e96a66cSDavid du Colombier /*
10775e96a66cSDavid du Colombier  * try to allocate a BList so we can record that b must
10785e96a66cSDavid du Colombier  * be written out before some other block.
10795e96a66cSDavid du Colombier  * if can't find a BList, write b out instead and return nil.
10805e96a66cSDavid du Colombier  */
10815e96a66cSDavid du Colombier static BList *
10825e96a66cSDavid du Colombier blistAlloc(Block *b)
10835e96a66cSDavid du Colombier {
10845e96a66cSDavid du Colombier 	Cache *c;
10855e96a66cSDavid du Colombier 	BList *p;
10865e96a66cSDavid du Colombier 
10875e96a66cSDavid du Colombier 	/*
10885e96a66cSDavid du Colombier 	 * It's possible that when we marked b dirty, there were
10895e96a66cSDavid du Colombier 	 * too many dirty blocks so we just wrote b there and then.
10905e96a66cSDavid du Colombier 	 * So b might not be dirty.  If it's not, no need to worry
10915e96a66cSDavid du Colombier 	 * about recording the write constraint.
10925e96a66cSDavid du Colombier 	 *
10935e96a66cSDavid du Colombier 	 * BlockRemoveLink depends on the fact that if blistAlloc
10945e96a66cSDavid du Colombier 	 * returns non-nil, b really is dirty.
10955e96a66cSDavid du Colombier 	 */
10965e96a66cSDavid du Colombier 	if(b->iostate != BioDirty){
10975e96a66cSDavid du Colombier 		assert(b->iostate == BioClean);
10985e96a66cSDavid du Colombier 		return nil;
10995e96a66cSDavid du Colombier 	}
11005e96a66cSDavid du Colombier 
11015e96a66cSDavid du Colombier 	/*
11025e96a66cSDavid du Colombier 	 * Easy: maybe there's a free list left.
11035e96a66cSDavid du Colombier 	 */
11045e96a66cSDavid du Colombier 	c = b->c;
11055e96a66cSDavid du Colombier 	vtLock(c->lk);
11065e96a66cSDavid du Colombier 	if(c->blfree){
11075e96a66cSDavid du Colombier 	HaveBlFree:
11085e96a66cSDavid du Colombier 		p = c->blfree;
11095e96a66cSDavid du Colombier 		c->blfree = p->next;
11105e96a66cSDavid du Colombier 		vtUnlock(c->lk);
11117f1bc48aSDavid du Colombier assert(b->iostate == BioDirty);
11125e96a66cSDavid du Colombier 		return p;
11135e96a66cSDavid du Colombier 	}
11145e96a66cSDavid du Colombier 	vtUnlock(c->lk);
11155e96a66cSDavid du Colombier 
11165e96a66cSDavid du Colombier 	/*
11175e96a66cSDavid du Colombier 	 * No free BLists.  What are our options?
11185e96a66cSDavid du Colombier 	 */
11195e96a66cSDavid du Colombier 
11205e96a66cSDavid du Colombier 	/* Block has no priors? Just write it. */
11215e96a66cSDavid du Colombier 	if(b->prior == nil){
1122867bfcc6SDavid du Colombier 		diskWriteAndWait(c->disk, b);
11235e96a66cSDavid du Colombier 		return nil;
11245e96a66cSDavid du Colombier 	}
11255e96a66cSDavid du Colombier 
11265e96a66cSDavid du Colombier 	/*
11275e96a66cSDavid du Colombier 	 * Wake the flush thread, which will hopefully free up
11285e96a66cSDavid du Colombier 	 * some BLists for us.  We used to flush a block from
11295e96a66cSDavid du Colombier 	 * our own prior list and reclaim that BList, but this is
11305e96a66cSDavid du Colombier 	 * a no-no: some of the blocks on our prior list may
11315e96a66cSDavid du Colombier 	 * be locked by our caller.  Or maybe their label blocks
11325e96a66cSDavid du Colombier 	 * are locked by our caller.  In any event, it's too hard
11335e96a66cSDavid du Colombier 	 * to make sure we can do I/O for ourselves.  Instead,
11345e96a66cSDavid du Colombier 	 * we assume the flush thread will find something.
11355e96a66cSDavid du Colombier 	 * (The flush thread never blocks waiting for a block,
11365e96a66cSDavid du Colombier 	 * so it won't deadlock like we will.)
11375e96a66cSDavid du Colombier 	 */
11385e96a66cSDavid du Colombier 	vtLock(c->lk);
11395e96a66cSDavid du Colombier 	while(c->blfree == nil){
11405e96a66cSDavid du Colombier 		vtWakeup(c->flush);
11415e96a66cSDavid du Colombier 		vtSleep(c->blrend);
11425e96a66cSDavid du Colombier 	}
11435e96a66cSDavid du Colombier 	goto HaveBlFree;
11445e96a66cSDavid du Colombier }
11455e96a66cSDavid du Colombier 
11465e96a66cSDavid du Colombier void
11475e96a66cSDavid du Colombier blistFree(Cache *c, BList *bl)
11485e96a66cSDavid du Colombier {
11495e96a66cSDavid du Colombier 	vtLock(c->lk);
11505e96a66cSDavid du Colombier 	bl->next = c->blfree;
11515e96a66cSDavid du Colombier 	c->blfree = bl;
11525e96a66cSDavid du Colombier 	vtWakeup(c->blrend);
11535e96a66cSDavid du Colombier 	vtUnlock(c->lk);
11547f1bc48aSDavid du Colombier cacheFlush(c, 0);
11555e96a66cSDavid du Colombier }
11565e96a66cSDavid du Colombier 
11575e96a66cSDavid du Colombier /*
115861201b97SDavid du Colombier  * Record that bb must be written out before b.
115961201b97SDavid du Colombier  * If index is given, we're about to overwrite the score/e
116061201b97SDavid du Colombier  * at that index in the block.  Save the old value so we
11615e96a66cSDavid du Colombier  * can write a safer ``old'' version of the block if pressed.
11625e96a66cSDavid du Colombier  */
11635e96a66cSDavid du Colombier void
116461201b97SDavid du Colombier blockDependency(Block *b, Block *bb, int index, uchar *score, Entry *e)
11655e96a66cSDavid du Colombier {
11665e96a66cSDavid du Colombier 	BList *p;
11675e96a66cSDavid du Colombier 
11685e96a66cSDavid du Colombier 	if(bb->iostate == BioClean)
11695e96a66cSDavid du Colombier 		return;
11705e96a66cSDavid du Colombier 
117161201b97SDavid du Colombier 	/*
117261201b97SDavid du Colombier 	 * Dependencies for blocks containing Entry structures
117361201b97SDavid du Colombier 	 * or scores must always be explained.  The problem with
117461201b97SDavid du Colombier 	 * only explaining some of them is this.  Suppose we have two
117561201b97SDavid du Colombier 	 * dependencies for the same field, the first explained
117661201b97SDavid du Colombier 	 * and the second not.  We try to write the block when the first
117761201b97SDavid du Colombier 	 * dependency is not written but the second is.  We will roll back
117861201b97SDavid du Colombier 	 * the first change even though the second trumps it.
117961201b97SDavid du Colombier 	 */
118061201b97SDavid du Colombier 	if(index == -1 && bb->part == PartData)
118161201b97SDavid du Colombier 		assert(b->l.type == BtData);
118261201b97SDavid du Colombier 
11837abd426fSDavid du Colombier 	if(bb->iostate != BioDirty){
11847abd426fSDavid du Colombier 		fprint(2, "%d:%x:%d iostate is %d in blockDependency\n",
11857abd426fSDavid du Colombier 			bb->part, bb->addr, bb->l.type, bb->iostate);
11867abd426fSDavid du Colombier 		abort();
11877abd426fSDavid du Colombier 	}
11885e96a66cSDavid du Colombier 
11895e96a66cSDavid du Colombier 	p = blistAlloc(bb);
11905e96a66cSDavid du Colombier 	if(p == nil)
11915e96a66cSDavid du Colombier 		return;
11925e96a66cSDavid du Colombier 
11937f1bc48aSDavid du Colombier 	assert(bb->iostate == BioDirty);
11945e96a66cSDavid 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);
11955e96a66cSDavid du Colombier 
11965e96a66cSDavid du Colombier 	p->part = bb->part;
11975e96a66cSDavid du Colombier 	p->addr = bb->addr;
11985e96a66cSDavid du Colombier 	p->type = bb->l.type;
11995e96a66cSDavid du Colombier 	p->vers = bb->vers;
12005e96a66cSDavid du Colombier 	p->index = index;
120161201b97SDavid du Colombier 	if(p->index >= 0){
120261201b97SDavid du Colombier 		/*
120361201b97SDavid du Colombier 		 * This test would just be b->l.type==BtDir except
120461201b97SDavid du Colombier 		 * we need to exclude the super block.
120561201b97SDavid du Colombier 		 */
120661201b97SDavid du Colombier 		if(b->l.type == BtDir && b->part == PartData)
120761201b97SDavid du Colombier 			entryPack(e, p->old.entry, 0);
120861201b97SDavid du Colombier 		else
120961201b97SDavid du Colombier 			memmove(p->old.score, score, VtScoreSize);
121061201b97SDavid du Colombier 	}
12115e96a66cSDavid du Colombier 	p->next = b->prior;
12125e96a66cSDavid du Colombier 	b->prior = p;
12135e96a66cSDavid du Colombier }
12145e96a66cSDavid du Colombier 
12155e96a66cSDavid du Colombier /*
12165e96a66cSDavid du Colombier  * Mark an in-memory block as dirty.  If there are too many
1217*fe853e23SDavid du Colombier  * dirty blocks, start writing some out to disk.
12185e96a66cSDavid du Colombier  *
1219*fe853e23SDavid du Colombier  * If there were way too many dirty blocks, we used to
1220*fe853e23SDavid du Colombier  * try to do some flushing ourselves, but it's just too dangerous --
1221*fe853e23SDavid du Colombier  * it implies that the callers cannot have any of our priors locked,
1222*fe853e23SDavid du Colombier  * but this is hard to avoid in some cases.
12235e96a66cSDavid du Colombier  */
12245e96a66cSDavid du Colombier int
12255e96a66cSDavid du Colombier blockDirty(Block *b)
12265e96a66cSDavid du Colombier {
12275e96a66cSDavid du Colombier 	Cache *c;
12285e96a66cSDavid du Colombier 
12295e96a66cSDavid du Colombier 	c = b->c;
12305e96a66cSDavid du Colombier 
12315e96a66cSDavid du Colombier 	assert(b->part != PartVenti);
12325e96a66cSDavid du Colombier 
12335e96a66cSDavid du Colombier 	if(b->iostate == BioDirty)
12345e96a66cSDavid du Colombier 		return 1;
12355e96a66cSDavid du Colombier 	assert(b->iostate == BioClean);
12365e96a66cSDavid du Colombier 
12375e96a66cSDavid du Colombier 	vtLock(c->lk);
123861201b97SDavid du Colombier 	b->iostate = BioDirty;
12395e96a66cSDavid du Colombier 	c->ndirty++;
12405e96a66cSDavid du Colombier 	if(c->ndirty > (c->maxdirty>>1))
12415e96a66cSDavid du Colombier 		vtWakeup(c->flush);
12425e96a66cSDavid du Colombier 	vtUnlock(c->lk);
12435e96a66cSDavid du Colombier 
12445e96a66cSDavid du Colombier 	return 1;
12455e96a66cSDavid du Colombier }
12465e96a66cSDavid du Colombier 
12475e96a66cSDavid du Colombier /*
12485e96a66cSDavid du Colombier  * Block b once pointed at the block bb at addr/type/tag, but no longer does.
12495e96a66cSDavid du Colombier  *
12505e96a66cSDavid du Colombier  * The file system maintains the following invariants (i-iv checked by flchk):
12515e96a66cSDavid du Colombier  *
12525e96a66cSDavid du Colombier  * (i) b.e in [bb.e, bb.eClose)
12535e96a66cSDavid du Colombier  * (ii) if b.e==bb.e,  then no other b' in e points at bb.
12545e96a66cSDavid du Colombier  * (iii) if !(b.state&Copied) and b.e==bb.e then no other b' points at bb.
12555e96a66cSDavid du Colombier  * (iv) if b is active then no other active b' points at bb.
12565e96a66cSDavid du Colombier  * (v) if b is a past life of b' then only one of b and b' is active (too hard to check)
12575e96a66cSDavid du Colombier  *
12585e96a66cSDavid du Colombier  * The file system initially satisfies these invariants, and we can verify that
12595e96a66cSDavid du Colombier  * the various file system operations maintain them.  See fossil.invariants.
12605e96a66cSDavid du Colombier  *
12615e96a66cSDavid du Colombier  * Condition (i) lets us reclaim blocks once the low epoch is greater
12625e96a66cSDavid du Colombier  * than epochClose.
12635e96a66cSDavid du Colombier  *
12645e96a66cSDavid du Colombier  * If the condition in (iii) is satisfied, then this is the only pointer to bb,
12655e96a66cSDavid du Colombier  * so bb can be reclaimed once b has been written to disk.  blockRemoveLink
12665e96a66cSDavid du Colombier  * checks !(b.state&Copied) as an optimization.  UnlinkBlock and blockCleanup
12675e96a66cSDavid du Colombier  * will check the conditions again for each block they consider.
12685e96a66cSDavid du Colombier  */
12695e96a66cSDavid du Colombier int
12705e96a66cSDavid du Colombier blockRemoveLink(Block *b, u32int addr, int type, u32int tag)
12715e96a66cSDavid du Colombier {
12725e96a66cSDavid du Colombier 	BList *bl;
12735e96a66cSDavid du Colombier 	BList *p, **pp;
12745e96a66cSDavid du Colombier 	Cache *c;
12755e96a66cSDavid du Colombier 
12765e96a66cSDavid du Colombier 	c = b->c;
12775e96a66cSDavid du Colombier 
12785e96a66cSDavid du Colombier 	/* remove unlinked block from prior list */
12795e96a66cSDavid du Colombier 	pp = &b->prior;
12805e96a66cSDavid du Colombier 	for(p=*pp; p; p=*pp){
12815e96a66cSDavid du Colombier 		if(p->part != PartData || p->addr != addr){
12825e96a66cSDavid du Colombier 			pp = &p->next;
12835e96a66cSDavid du Colombier 			continue;
12845e96a66cSDavid du Colombier 		}
12855e96a66cSDavid du Colombier 		*pp = p->next;
12865e96a66cSDavid du Colombier 		blistFree(c, p);
12875e96a66cSDavid du Colombier 	}
12885e96a66cSDavid du Colombier 
12895e96a66cSDavid du Colombier 	/* if b has been copied, can't reclaim blocks it points at. */
12905e96a66cSDavid du Colombier 	if(b->l.state & BsCopied)
12915e96a66cSDavid du Colombier 		return 0;
12925e96a66cSDavid du Colombier 
12935e96a66cSDavid du Colombier 	bl = blistAlloc(b);
12945e96a66cSDavid du Colombier 	if(bl == nil)
12955e96a66cSDavid du Colombier 		return unlinkBlock(b->c, addr, type, tag, b->l.epoch);
12965e96a66cSDavid du Colombier 
12975e96a66cSDavid du Colombier 	/*
12985e96a66cSDavid du Colombier 	 * Because bl != nil, we know b is dirty.
12995e96a66cSDavid du Colombier 	 * (Linking b->uhead onto a clean block is
13005e96a66cSDavid du Colombier 	 * counterproductive, since we only look at
13015e96a66cSDavid du Colombier 	 * b->uhead when a block transitions from
13025e96a66cSDavid du Colombier 	 * dirty to clean.)
13035e96a66cSDavid du Colombier 	 */
13045e96a66cSDavid du Colombier 	assert(b->iostate == BioDirty);
13055e96a66cSDavid du Colombier 
13065e96a66cSDavid du Colombier 	bl->part = PartData;
13075e96a66cSDavid du Colombier 	bl->addr = addr;
13085e96a66cSDavid du Colombier 	bl->type = type;
13095e96a66cSDavid du Colombier 	bl->tag = tag;
13105e96a66cSDavid du Colombier 	bl->epoch = b->l.epoch;
13115e96a66cSDavid du Colombier 	if(b->uhead == nil)
13125e96a66cSDavid du Colombier 		b->uhead = bl;
13135e96a66cSDavid du Colombier 	else
13145e96a66cSDavid du Colombier 		b->utail->next = bl;
13155e96a66cSDavid du Colombier 	b->utail = bl;
13165e96a66cSDavid du Colombier 	bl->next = nil;
13175e96a66cSDavid du Colombier 	return 1;
13185e96a66cSDavid du Colombier }
13195e96a66cSDavid du Colombier 
13205e96a66cSDavid du Colombier /*
13215e96a66cSDavid du Colombier  * set the label associated with a block.
13225e96a66cSDavid du Colombier  */
13235e96a66cSDavid du Colombier Block*
13245e96a66cSDavid du Colombier _blockSetLabel(Block *b, Label *l)
13255e96a66cSDavid du Colombier {
13265e96a66cSDavid du Colombier 	int lpb;
13275e96a66cSDavid du Colombier 	Block *bb;
13285e96a66cSDavid du Colombier 	u32int a;
13295e96a66cSDavid du Colombier 	Cache *c;
13305e96a66cSDavid du Colombier 
13315e96a66cSDavid du Colombier 	c = b->c;
13325e96a66cSDavid du Colombier 
13335e96a66cSDavid du Colombier 	assert(b->part == PartData);
13345e96a66cSDavid du Colombier 	assert(b->iostate == BioLabel || b->iostate == BioClean || b->iostate == BioDirty);
13355e96a66cSDavid du Colombier 	lpb = c->size / LabelSize;
13365e96a66cSDavid du Colombier 	a = b->addr / lpb;
13375e96a66cSDavid du Colombier 	bb = cacheLocal(c, PartLabel, a, OReadWrite);
13385e96a66cSDavid du Colombier 	if(bb == nil){
13395e96a66cSDavid du Colombier 		blockPut(b);
13405e96a66cSDavid du Colombier 		return nil;
13415e96a66cSDavid du Colombier 	}
13425e96a66cSDavid du Colombier 	b->l = *l;
13435e96a66cSDavid du Colombier 	labelPack(l, bb->data, b->addr%lpb);
13445e96a66cSDavid du Colombier 	blockDirty(bb);
13455e96a66cSDavid du Colombier 	return bb;
13465e96a66cSDavid du Colombier }
13475e96a66cSDavid du Colombier 
13485e96a66cSDavid du Colombier int
13495e96a66cSDavid du Colombier blockSetLabel(Block *b, Label *l)
13505e96a66cSDavid du Colombier {
13515e96a66cSDavid du Colombier 	Block *lb;
13525e96a66cSDavid du Colombier 	Label oldl;
13535e96a66cSDavid du Colombier 
13545e96a66cSDavid du Colombier 	oldl = b->l;
13555e96a66cSDavid du Colombier 	lb = _blockSetLabel(b, l);
13565e96a66cSDavid du Colombier 	if(lb == nil)
13575e96a66cSDavid du Colombier 		return 0;
13585e96a66cSDavid du Colombier 
13595e96a66cSDavid du Colombier 	/*
13605e96a66cSDavid du Colombier 	 * If we're allocating the block, make sure the label (bl)
13615e96a66cSDavid du Colombier 	 * goes to disk before the data block (b) itself.  This is to help
13625e96a66cSDavid du Colombier 	 * the blocks that in turn depend on b.
13635e96a66cSDavid du Colombier 	 *
13645e96a66cSDavid du Colombier 	 * Suppose bx depends on (must be written out after) b.
13655e96a66cSDavid du Colombier 	 * Once we write b we'll think it's safe to write bx.
13665e96a66cSDavid du Colombier 	 * Bx can't get at b unless it has a valid label, though.
13675e96a66cSDavid du Colombier 	 *
13685e96a66cSDavid du Colombier 	 * Allocation is the only case in which having a current label
13695e96a66cSDavid du Colombier 	 * is vital because:
13705e96a66cSDavid du Colombier 	 *
13715e96a66cSDavid du Colombier 	 *	- l.type is set at allocation and never changes.
13725e96a66cSDavid du Colombier 	 *	- l.tag is set at allocation and never changes.
13735e96a66cSDavid du Colombier 	 *	- l.state is not checked when we load blocks.
13745e96a66cSDavid du Colombier 	 *	- the archiver cares deeply about l.state being
13755e96a66cSDavid du Colombier 	 *		BaActive vs. BaCopied, but that's handled
13765e96a66cSDavid du Colombier 	 *		by direct calls to _blockSetLabel.
13775e96a66cSDavid du Colombier 	 */
13785e96a66cSDavid du Colombier 
13795e96a66cSDavid du Colombier 	if(oldl.state == BsFree)
138061201b97SDavid du Colombier 		blockDependency(b, lb, -1, nil, nil);
13815e96a66cSDavid du Colombier 	blockPut(lb);
13825e96a66cSDavid du Colombier 	return 1;
13835e96a66cSDavid du Colombier }
13845e96a66cSDavid du Colombier 
13855e96a66cSDavid du Colombier /*
138661201b97SDavid du Colombier  * We've decided to write out b.  Maybe b has some pointers to blocks
138761201b97SDavid du Colombier  * that haven't yet been written to disk.  If so, construct a slightly out-of-date
138861201b97SDavid du Colombier  * copy of b that is safe to write out.  (diskThread will make sure the block
13895e96a66cSDavid du Colombier  * remains marked as dirty.)
13905e96a66cSDavid du Colombier  */
13915e96a66cSDavid du Colombier uchar *
13925e96a66cSDavid du Colombier blockRollback(Block *b, uchar *buf)
13935e96a66cSDavid du Colombier {
13945e96a66cSDavid du Colombier 	u32int addr;
13955e96a66cSDavid du Colombier 	BList *p;
13965e96a66cSDavid du Colombier 	Super super;
13975e96a66cSDavid du Colombier 
13985e96a66cSDavid du Colombier 	/* easy case */
13995e96a66cSDavid du Colombier 	if(b->prior == nil)
14005e96a66cSDavid du Colombier 		return b->data;
14015e96a66cSDavid du Colombier 
14025e96a66cSDavid du Colombier 	memmove(buf, b->data, b->c->size);
14035e96a66cSDavid du Colombier 	for(p=b->prior; p; p=p->next){
14045e96a66cSDavid du Colombier 		/*
14055e96a66cSDavid du Colombier 		 * we know p->index >= 0 because blockWrite has vetted this block for us.
14065e96a66cSDavid du Colombier 		 */
14075e96a66cSDavid du Colombier 		assert(p->index >= 0);
14085e96a66cSDavid du Colombier 		assert(b->part == PartSuper || (b->part == PartData && b->l.type != BtData));
14095e96a66cSDavid du Colombier 		if(b->part == PartSuper){
14105e96a66cSDavid du Colombier 			assert(p->index == 0);
14115e96a66cSDavid du Colombier 			superUnpack(&super, buf);
141261201b97SDavid du Colombier 			addr = globalToLocal(p->old.score);
14135e96a66cSDavid du Colombier 			if(addr == NilBlock){
141461201b97SDavid du Colombier 				fprint(2, "rolling back super block: bad replacement addr %V\n", p->old.score);
14155e96a66cSDavid du Colombier 				abort();
14165e96a66cSDavid du Colombier 			}
14175e96a66cSDavid du Colombier 			super.active = addr;
14185e96a66cSDavid du Colombier 			superPack(&super, buf);
14195e96a66cSDavid du Colombier 			continue;
14205e96a66cSDavid du Colombier 		}
142161201b97SDavid du Colombier 		if(b->l.type == BtDir)
142261201b97SDavid du Colombier 			memmove(buf+p->index*VtEntrySize, p->old.entry, VtEntrySize);
142361201b97SDavid du Colombier 		else
142461201b97SDavid du Colombier 			memmove(buf+p->index*VtScoreSize, p->old.score, VtScoreSize);
14255e96a66cSDavid du Colombier 	}
14265e96a66cSDavid du Colombier 	return buf;
14275e96a66cSDavid du Colombier }
14285e96a66cSDavid du Colombier 
14295e96a66cSDavid du Colombier /*
14305e96a66cSDavid du Colombier  * Try to write block b.
14315e96a66cSDavid du Colombier  * If b depends on other blocks:
14325e96a66cSDavid du Colombier  *
14335e96a66cSDavid du Colombier  *	If the block has been written out, remove the dependency.
14347abd426fSDavid du Colombier  *	If the dependency is replaced by a more recent dependency,
14357abd426fSDavid du Colombier  *		throw it out.
14365e96a66cSDavid du Colombier  *	If we know how to write out an old version of b that doesn't
14375e96a66cSDavid du Colombier  *		depend on it, do that.
14385e96a66cSDavid du Colombier  *
14395e96a66cSDavid du Colombier  *	Otherwise, bail.
14405e96a66cSDavid du Colombier  */
14415e96a66cSDavid du Colombier int
14425e96a66cSDavid du Colombier blockWrite(Block *b)
14435e96a66cSDavid du Colombier {
144461201b97SDavid du Colombier 	uchar *dmap;
14455e96a66cSDavid du Colombier 	Cache *c;
14465e96a66cSDavid du Colombier 	BList *p, **pp;
14475e96a66cSDavid du Colombier 	Block *bb;
14485e96a66cSDavid du Colombier 	int lockfail;
14495e96a66cSDavid du Colombier 
14505e96a66cSDavid du Colombier 	c = b->c;
14515e96a66cSDavid du Colombier 
14525e96a66cSDavid du Colombier 	if(b->iostate != BioDirty)
14535e96a66cSDavid du Colombier 		return 1;
14545e96a66cSDavid du Colombier 
145561201b97SDavid du Colombier 	dmap = b->dmap;
145661201b97SDavid du Colombier 	memset(dmap, 0, c->ndmap);
14575e96a66cSDavid du Colombier 	pp = &b->prior;
14585e96a66cSDavid du Colombier 	for(p=*pp; p; p=*pp){
145961201b97SDavid du Colombier 		if(p->index >= 0){
146061201b97SDavid du Colombier 			/* more recent dependency has succeeded; this one can go */
146161201b97SDavid du Colombier 			if(dmap[p->index/8] & (1<<(p->index%8)))
146261201b97SDavid du Colombier 				goto ignblock;
146361201b97SDavid du Colombier 		}
146461201b97SDavid du Colombier 
146561201b97SDavid du Colombier 		lockfail = 0;
14665e96a66cSDavid du Colombier 		bb = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
14675e96a66cSDavid du Colombier 		if(bb == nil){
14685e96a66cSDavid du Colombier 			if(lockfail)
14695e96a66cSDavid du Colombier 				return 0;
147061201b97SDavid du Colombier 			/* block not in cache => was written already */
147161201b97SDavid du Colombier 			dmap[p->index/8] |= 1<<(p->index%8);
147261201b97SDavid du Colombier 			goto ignblock;
14735e96a66cSDavid du Colombier 		}
14745e96a66cSDavid du Colombier 
14755e96a66cSDavid du Colombier 		/*
14765e96a66cSDavid du Colombier 		 * same version of block is still in cache.
14775e96a66cSDavid du Colombier 		 *
14785e96a66cSDavid du Colombier 		 * the assertion is true because the block still has version p->vers,
14795e96a66cSDavid du Colombier 		 * which means it hasn't been written out since we last saw it.
14805e96a66cSDavid du Colombier 		 */
14817abd426fSDavid du Colombier 		if(bb->iostate != BioDirty){
14827abd426fSDavid du Colombier 			fprint(2, "%d:%x:%d iostate is %d in blockWrite\n",
14837abd426fSDavid du Colombier 				bb->part, bb->addr, bb->l.type, bb->iostate);
14847abd426fSDavid du Colombier 			/* probably BioWriting if it happens? */
14857f1bc48aSDavid du Colombier 			if(bb->iostate == BioClean)
14867f1bc48aSDavid du Colombier 				goto ignblock;
14877abd426fSDavid du Colombier 		}
14887abd426fSDavid du Colombier 
14895e96a66cSDavid du Colombier 		blockPut(bb);
14905e96a66cSDavid du Colombier 
14915e96a66cSDavid du Colombier 		if(p->index < 0){
14925e96a66cSDavid du Colombier 			/*
14935e96a66cSDavid du Colombier 			 * We don't know how to temporarily undo
14945e96a66cSDavid du Colombier 			 * b's dependency on bb, so just don't write b yet.
14955e96a66cSDavid du Colombier 			 */
14965e96a66cSDavid du Colombier 			if(0) fprint(2, "blockWrite skipping %d %x %d %d; need to write %d %x %d\n",
14975e96a66cSDavid du Colombier 				b->part, b->addr, b->vers, b->l.type, p->part, p->addr, bb->vers);
14985e96a66cSDavid du Colombier 			return 0;
14995e96a66cSDavid du Colombier 		}
15005e96a66cSDavid du Colombier 		/* keep walking down the list */
15015e96a66cSDavid du Colombier 		pp = &p->next;
150261201b97SDavid du Colombier 		continue;
150361201b97SDavid du Colombier 
150461201b97SDavid du Colombier ignblock:
150561201b97SDavid du Colombier 		*pp = p->next;
150661201b97SDavid du Colombier 		blistFree(c, p);
150761201b97SDavid du Colombier 		continue;
15085e96a66cSDavid du Colombier 	}
15095e96a66cSDavid du Colombier 
1510867bfcc6SDavid du Colombier 	/*
1511867bfcc6SDavid du Colombier 	 * DiskWrite must never be called with a double-locked block.
1512867bfcc6SDavid du Colombier 	 * This call to diskWrite is okay because blockWrite is only called
1513867bfcc6SDavid du Colombier 	 * from the cache flush thread, which never double-locks a block.
1514867bfcc6SDavid du Colombier 	 */
15155e96a66cSDavid du Colombier 	diskWrite(c->disk, b);
15165e96a66cSDavid du Colombier 	return 1;
15175e96a66cSDavid du Colombier }
15185e96a66cSDavid du Colombier 
15195e96a66cSDavid du Colombier /*
15205e96a66cSDavid du Colombier  * Change the I/O state of block b.
15215e96a66cSDavid du Colombier  * Just an assignment except for magic in
15225e96a66cSDavid du Colombier  * switch statement (read comments there).
15235e96a66cSDavid du Colombier  */
15245e96a66cSDavid du Colombier void
15255e96a66cSDavid du Colombier blockSetIOState(Block *b, int iostate)
15265e96a66cSDavid du Colombier {
15275e96a66cSDavid du Colombier 	int dowakeup;
15285e96a66cSDavid du Colombier 	Cache *c;
15295e96a66cSDavid du Colombier 	BList *p, *q;
15305e96a66cSDavid du Colombier 
15315e96a66cSDavid du Colombier if(0) fprint(2, "iostate part=%d addr=%x %s->%s\n", b->part, b->addr, bioStr(b->iostate), bioStr(iostate));
15325e96a66cSDavid du Colombier 
15335e96a66cSDavid du Colombier 	c = b->c;
15345e96a66cSDavid du Colombier 
15355e96a66cSDavid du Colombier 	dowakeup = 0;
15365e96a66cSDavid du Colombier 	switch(iostate){
15375e96a66cSDavid du Colombier 	default:
15385e96a66cSDavid du Colombier 		abort();
15395e96a66cSDavid du Colombier 	case BioEmpty:
15405e96a66cSDavid du Colombier 		assert(!b->uhead);
15415e96a66cSDavid du Colombier 		break;
15425e96a66cSDavid du Colombier 	case BioLabel:
15435e96a66cSDavid du Colombier 		assert(!b->uhead);
15445e96a66cSDavid du Colombier 		break;
15455e96a66cSDavid du Colombier 	case BioClean:
15465e96a66cSDavid du Colombier 		bwatchDependency(b);
15475e96a66cSDavid du Colombier 		/*
15485e96a66cSDavid du Colombier 		 * If b->prior is set, it means a write just finished.
15495e96a66cSDavid du Colombier 		 * The prior list isn't needed anymore.
15505e96a66cSDavid du Colombier 		 */
15515e96a66cSDavid du Colombier 		for(p=b->prior; p; p=q){
15525e96a66cSDavid du Colombier 			q = p->next;
15535e96a66cSDavid du Colombier 			blistFree(c, p);
15545e96a66cSDavid du Colombier 		}
15555e96a66cSDavid du Colombier 		b->prior = nil;
15565e96a66cSDavid du Colombier 		/*
15575e96a66cSDavid du Colombier 		 * Freeing a block or just finished a write.
15585e96a66cSDavid du Colombier 		 * Move the blocks from the per-block unlink
15595e96a66cSDavid du Colombier 		 * queue to the cache unlink queue.
15605e96a66cSDavid du Colombier 		 */
15615e96a66cSDavid du Colombier 		if(b->iostate == BioDirty || b->iostate == BioWriting){
15625e96a66cSDavid du Colombier 			vtLock(c->lk);
15635e96a66cSDavid du Colombier 			c->ndirty--;
156461201b97SDavid du Colombier 			b->iostate = iostate;	/* change here to keep in sync with ndirty */
15655e96a66cSDavid du Colombier 			b->vers = c->vers++;
15665e96a66cSDavid du Colombier 			if(b->uhead){
15675e96a66cSDavid du Colombier 				/* add unlink blocks to unlink queue */
15685e96a66cSDavid du Colombier 				if(c->uhead == nil){
15695e96a66cSDavid du Colombier 					c->uhead = b->uhead;
15705e96a66cSDavid du Colombier 					vtWakeup(c->unlink);
15715e96a66cSDavid du Colombier 				}else
15725e96a66cSDavid du Colombier 					c->utail->next = b->uhead;
15735e96a66cSDavid du Colombier 				c->utail = b->utail;
15745e96a66cSDavid du Colombier 				b->uhead = nil;
15755e96a66cSDavid du Colombier 			}
15765e96a66cSDavid du Colombier 			vtUnlock(c->lk);
15775e96a66cSDavid du Colombier 		}
15785e96a66cSDavid du Colombier 		assert(!b->uhead);
15795e96a66cSDavid du Colombier 		dowakeup = 1;
15805e96a66cSDavid du Colombier 		break;
15815e96a66cSDavid du Colombier 	case BioDirty:
15825e96a66cSDavid du Colombier 		/*
15835e96a66cSDavid du Colombier 		 * Wrote out an old version of the block (see blockRollback).
15845e96a66cSDavid du Colombier 		 * Bump a version count, leave it dirty.
15855e96a66cSDavid du Colombier 		 */
15865e96a66cSDavid du Colombier 		if(b->iostate == BioWriting){
15875e96a66cSDavid du Colombier 			vtLock(c->lk);
15885e96a66cSDavid du Colombier 			b->vers = c->vers++;
15895e96a66cSDavid du Colombier 			vtUnlock(c->lk);
15905e96a66cSDavid du Colombier 			dowakeup = 1;
15915e96a66cSDavid du Colombier 		}
15925e96a66cSDavid du Colombier 		break;
15935e96a66cSDavid du Colombier 	case BioReading:
15945e96a66cSDavid du Colombier 	case BioWriting:
15955e96a66cSDavid du Colombier 		/*
15965e96a66cSDavid du Colombier 		 * Adding block to disk queue.  Bump reference count.
15975e96a66cSDavid du Colombier 		 * diskThread decs the count later by calling blockPut.
15985e96a66cSDavid du Colombier 		 * This is here because we need to lock c->lk to
15995e96a66cSDavid du Colombier 		 * manipulate the ref count.
16005e96a66cSDavid du Colombier 		 */
16015e96a66cSDavid du Colombier 		vtLock(c->lk);
16025e96a66cSDavid du Colombier 		b->ref++;
16035e96a66cSDavid du Colombier 		vtUnlock(c->lk);
16045e96a66cSDavid du Colombier 		break;
16055e96a66cSDavid du Colombier 	case BioReadError:
16065e96a66cSDavid du Colombier 	case BioVentiError:
16075e96a66cSDavid du Colombier 		/*
16085e96a66cSDavid du Colombier 		 * Oops.
16095e96a66cSDavid du Colombier 		 */
16105e96a66cSDavid du Colombier 		dowakeup = 1;
16115e96a66cSDavid du Colombier 		break;
16125e96a66cSDavid du Colombier 	}
16135e96a66cSDavid du Colombier 	b->iostate = iostate;
16145e96a66cSDavid du Colombier 	/*
16155e96a66cSDavid du Colombier 	 * Now that the state has changed, we can wake the waiters.
16165e96a66cSDavid du Colombier 	 */
16175e96a66cSDavid du Colombier 	if(dowakeup)
16185e96a66cSDavid du Colombier 		vtWakeupAll(b->ioready);
16195e96a66cSDavid du Colombier }
16205e96a66cSDavid du Colombier 
16215e96a66cSDavid du Colombier char*
16225e96a66cSDavid du Colombier bsStr(int state)
16235e96a66cSDavid du Colombier {
16245e96a66cSDavid du Colombier 	static char s[100];
16255e96a66cSDavid du Colombier 
16265e96a66cSDavid du Colombier 	if(state == BsFree)
16275e96a66cSDavid du Colombier 		return "Free";
16285e96a66cSDavid du Colombier 	if(state == BsBad)
16295e96a66cSDavid du Colombier 		return "Bad";
16305e96a66cSDavid du Colombier 
16315e96a66cSDavid du Colombier 	sprint(s, "%x", state);
16325e96a66cSDavid du Colombier 	if(!(state&BsAlloc))
16335e96a66cSDavid du Colombier 		strcat(s, ",Free");	/* should not happen */
16345e96a66cSDavid du Colombier 	if(state&BsCopied)
16355e96a66cSDavid du Colombier 		strcat(s, ",Copied");
16365e96a66cSDavid du Colombier 	if(state&BsVenti)
16375e96a66cSDavid du Colombier 		strcat(s, ",Venti");
16385e96a66cSDavid du Colombier 	if(state&BsClosed)
16395e96a66cSDavid du Colombier 		strcat(s, ",Closed");
16405e96a66cSDavid du Colombier 	return s;
16415e96a66cSDavid du Colombier }
16425e96a66cSDavid du Colombier 
16435e96a66cSDavid du Colombier char *
16445e96a66cSDavid du Colombier bioStr(int iostate)
16455e96a66cSDavid du Colombier {
16465e96a66cSDavid du Colombier 	switch(iostate){
16475e96a66cSDavid du Colombier 	default:
16485e96a66cSDavid du Colombier 		return "Unknown!!";
16495e96a66cSDavid du Colombier 	case BioEmpty:
16505e96a66cSDavid du Colombier 		return "Empty";
16515e96a66cSDavid du Colombier 	case BioLabel:
16525e96a66cSDavid du Colombier 		return "Label";
16535e96a66cSDavid du Colombier 	case BioClean:
16545e96a66cSDavid du Colombier 		return "Clean";
16555e96a66cSDavid du Colombier 	case BioDirty:
16565e96a66cSDavid du Colombier 		return "Dirty";
16575e96a66cSDavid du Colombier 	case BioReading:
16585e96a66cSDavid du Colombier 		return "Reading";
16595e96a66cSDavid du Colombier 	case BioWriting:
16605e96a66cSDavid du Colombier 		return "Writing";
16615e96a66cSDavid du Colombier 	case BioReadError:
16625e96a66cSDavid du Colombier 		return "ReadError";
16635e96a66cSDavid du Colombier 	case BioVentiError:
16645e96a66cSDavid du Colombier 		return "VentiError";
16655e96a66cSDavid du Colombier 	case BioMax:
16665e96a66cSDavid du Colombier 		return "Max";
16675e96a66cSDavid du Colombier 	}
16685e96a66cSDavid du Colombier }
16695e96a66cSDavid du Colombier 
16705e96a66cSDavid du Colombier static char *bttab[] = {
16715e96a66cSDavid du Colombier 	"BtData",
16725e96a66cSDavid du Colombier 	"BtData+1",
16735e96a66cSDavid du Colombier 	"BtData+2",
16745e96a66cSDavid du Colombier 	"BtData+3",
16755e96a66cSDavid du Colombier 	"BtData+4",
16765e96a66cSDavid du Colombier 	"BtData+5",
16775e96a66cSDavid du Colombier 	"BtData+6",
16785e96a66cSDavid du Colombier 	"BtData+7",
16795e96a66cSDavid du Colombier 	"BtDir",
16805e96a66cSDavid du Colombier 	"BtDir+1",
16815e96a66cSDavid du Colombier 	"BtDir+2",
16825e96a66cSDavid du Colombier 	"BtDir+3",
16835e96a66cSDavid du Colombier 	"BtDir+4",
16845e96a66cSDavid du Colombier 	"BtDir+5",
16855e96a66cSDavid du Colombier 	"BtDir+6",
16865e96a66cSDavid du Colombier 	"BtDir+7",
16875e96a66cSDavid du Colombier };
16885e96a66cSDavid du Colombier 
16895e96a66cSDavid du Colombier char*
16905e96a66cSDavid du Colombier btStr(int type)
16915e96a66cSDavid du Colombier {
16925e96a66cSDavid du Colombier 	if(type < nelem(bttab))
16935e96a66cSDavid du Colombier 		return bttab[type];
16945e96a66cSDavid du Colombier 	return "unknown";
16955e96a66cSDavid du Colombier }
16965e96a66cSDavid du Colombier 
16975e96a66cSDavid du Colombier int
16985e96a66cSDavid du Colombier labelFmt(Fmt *f)
16995e96a66cSDavid du Colombier {
17005e96a66cSDavid du Colombier 	Label *l;
17015e96a66cSDavid du Colombier 
17025e96a66cSDavid du Colombier 	l = va_arg(f->args, Label*);
17035e96a66cSDavid du Colombier 	return fmtprint(f, "%s,%s,e=%ud,%d,tag=%#ux",
17045e96a66cSDavid du Colombier 		btStr(l->type), bsStr(l->state), l->epoch, (int)l->epochClose, l->tag);
17055e96a66cSDavid du Colombier }
17065e96a66cSDavid du Colombier 
17075e96a66cSDavid du Colombier int
17085e96a66cSDavid du Colombier scoreFmt(Fmt *f)
17095e96a66cSDavid du Colombier {
17105e96a66cSDavid du Colombier 	uchar *v;
17115e96a66cSDavid du Colombier 	int i;
17125e96a66cSDavid du Colombier 	u32int addr;
17135e96a66cSDavid du Colombier 
17145e96a66cSDavid du Colombier 	v = va_arg(f->args, uchar*);
17155e96a66cSDavid du Colombier 	if(v == nil){
17165e96a66cSDavid du Colombier 		fmtprint(f, "*");
17175e96a66cSDavid du Colombier 	}else if((addr = globalToLocal(v)) != NilBlock)
17185e96a66cSDavid du Colombier 		fmtprint(f, "0x%.8ux", addr);
17195e96a66cSDavid du Colombier 	else{
17205e96a66cSDavid du Colombier 		for(i = 0; i < VtScoreSize; i++)
17215e96a66cSDavid du Colombier 			fmtprint(f, "%2.2ux", v[i]);
17225e96a66cSDavid du Colombier 	}
17235e96a66cSDavid du Colombier 
17245e96a66cSDavid du Colombier 	return 0;
17255e96a66cSDavid du Colombier }
17265e96a66cSDavid du Colombier 
17275e96a66cSDavid du Colombier static int
17285e96a66cSDavid du Colombier upHeap(int i, Block *b)
17295e96a66cSDavid du Colombier {
17305e96a66cSDavid du Colombier 	Block *bb;
17315e96a66cSDavid du Colombier 	u32int now;
17325e96a66cSDavid du Colombier 	int p;
17335e96a66cSDavid du Colombier 	Cache *c;
17345e96a66cSDavid du Colombier 
17355e96a66cSDavid du Colombier 	c = b->c;
17365e96a66cSDavid du Colombier 	now = c->now;
17375e96a66cSDavid du Colombier 	for(; i != 0; i = p){
17385e96a66cSDavid du Colombier 		p = (i - 1) >> 1;
17395e96a66cSDavid du Colombier 		bb = c->heap[p];
17405e96a66cSDavid du Colombier 		if(b->used - now >= bb->used - now)
17415e96a66cSDavid du Colombier 			break;
17425e96a66cSDavid du Colombier 		c->heap[i] = bb;
17435e96a66cSDavid du Colombier 		bb->heap = i;
17445e96a66cSDavid du Colombier 	}
17455e96a66cSDavid du Colombier 	c->heap[i] = b;
17465e96a66cSDavid du Colombier 	b->heap = i;
17475e96a66cSDavid du Colombier 
17485e96a66cSDavid du Colombier 	return i;
17495e96a66cSDavid du Colombier }
17505e96a66cSDavid du Colombier 
17515e96a66cSDavid du Colombier static int
17525e96a66cSDavid du Colombier downHeap(int i, Block *b)
17535e96a66cSDavid du Colombier {
17545e96a66cSDavid du Colombier 	Block *bb;
17555e96a66cSDavid du Colombier 	u32int now;
17565e96a66cSDavid du Colombier 	int k;
17575e96a66cSDavid du Colombier 	Cache *c;
17585e96a66cSDavid du Colombier 
17595e96a66cSDavid du Colombier 	c = b->c;
17605e96a66cSDavid du Colombier 	now = c->now;
17615e96a66cSDavid du Colombier 	for(; ; i = k){
17625e96a66cSDavid du Colombier 		k = (i << 1) + 1;
17635e96a66cSDavid du Colombier 		if(k >= c->nheap)
17645e96a66cSDavid du Colombier 			break;
17655e96a66cSDavid du Colombier 		if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
17665e96a66cSDavid du Colombier 			k++;
17675e96a66cSDavid du Colombier 		bb = c->heap[k];
17685e96a66cSDavid du Colombier 		if(b->used - now <= bb->used - now)
17695e96a66cSDavid du Colombier 			break;
17705e96a66cSDavid du Colombier 		c->heap[i] = bb;
17715e96a66cSDavid du Colombier 		bb->heap = i;
17725e96a66cSDavid du Colombier 	}
17735e96a66cSDavid du Colombier 	c->heap[i] = b;
17745e96a66cSDavid du Colombier 	b->heap = i;
17755e96a66cSDavid du Colombier 	return i;
17765e96a66cSDavid du Colombier }
17775e96a66cSDavid du Colombier 
17785e96a66cSDavid du Colombier /*
17795e96a66cSDavid du Colombier  * Delete a block from the heap.
17805e96a66cSDavid du Colombier  * Called with c->lk held.
17815e96a66cSDavid du Colombier  */
17825e96a66cSDavid du Colombier static void
17835e96a66cSDavid du Colombier heapDel(Block *b)
17845e96a66cSDavid du Colombier {
17855e96a66cSDavid du Colombier 	int i, si;
17865e96a66cSDavid du Colombier 	Cache *c;
17875e96a66cSDavid du Colombier 
17885e96a66cSDavid du Colombier 	c = b->c;
17895e96a66cSDavid du Colombier 
17905e96a66cSDavid du Colombier 	si = b->heap;
17915e96a66cSDavid du Colombier 	if(si == BadHeap)
17925e96a66cSDavid du Colombier 		return;
17935e96a66cSDavid du Colombier 	b->heap = BadHeap;
17945e96a66cSDavid du Colombier 	c->nheap--;
17955e96a66cSDavid du Colombier 	if(si == c->nheap)
17965e96a66cSDavid du Colombier 		return;
17975e96a66cSDavid du Colombier 	b = c->heap[c->nheap];
17985e96a66cSDavid du Colombier 	i = upHeap(si, b);
17995e96a66cSDavid du Colombier 	if(i == si)
18005e96a66cSDavid du Colombier 		downHeap(i, b);
18015e96a66cSDavid du Colombier }
18025e96a66cSDavid du Colombier 
18035e96a66cSDavid du Colombier /*
18045e96a66cSDavid du Colombier  * Insert a block into the heap.
18055e96a66cSDavid du Colombier  * Called with c->lk held.
18065e96a66cSDavid du Colombier  */
18075e96a66cSDavid du Colombier static void
18085e96a66cSDavid du Colombier heapIns(Block *b)
18095e96a66cSDavid du Colombier {
18105e96a66cSDavid du Colombier 	assert(b->heap == BadHeap);
18115e96a66cSDavid du Colombier 	upHeap(b->c->nheap++, b);
1812*fe853e23SDavid du Colombier 	vtWakeup(b->c->heapwait);
18135e96a66cSDavid du Colombier }
18145e96a66cSDavid du Colombier 
18155e96a66cSDavid du Colombier /*
18165e96a66cSDavid du Colombier  * Get just the label for a block.
18175e96a66cSDavid du Colombier  */
18185e96a66cSDavid du Colombier static int
18195e96a66cSDavid du Colombier readLabel(Cache *c, Label *l, u32int addr)
18205e96a66cSDavid du Colombier {
18215e96a66cSDavid du Colombier 	int lpb;
18225e96a66cSDavid du Colombier 	Block *b;
18235e96a66cSDavid du Colombier 	u32int a;
18245e96a66cSDavid du Colombier 
18255e96a66cSDavid du Colombier 	lpb = c->size / LabelSize;
18265e96a66cSDavid du Colombier 	a = addr / lpb;
18275e96a66cSDavid du Colombier 	b = cacheLocal(c, PartLabel, a, OReadOnly);
18285e96a66cSDavid du Colombier 	if(b == nil){
18295e96a66cSDavid du Colombier 		blockPut(b);
18305e96a66cSDavid du Colombier 		return 0;
18315e96a66cSDavid du Colombier 	}
18325e96a66cSDavid du Colombier 
18335e96a66cSDavid du Colombier 	if(!labelUnpack(l, b->data, addr%lpb)){
18345e96a66cSDavid du Colombier 		blockPut(b);
18355e96a66cSDavid du Colombier 		return 0;
18365e96a66cSDavid du Colombier 	}
18375e96a66cSDavid du Colombier 	blockPut(b);
18385e96a66cSDavid du Colombier 	return 1;
18395e96a66cSDavid du Colombier }
18405e96a66cSDavid du Colombier 
18415e96a66cSDavid du Colombier /*
18425e96a66cSDavid du Colombier  * Process unlink queue.
18435e96a66cSDavid du Colombier  * Called with c->lk held.
18445e96a66cSDavid du Colombier  */
18455e96a66cSDavid du Colombier static void
18465e96a66cSDavid du Colombier unlinkBody(Cache *c)
18475e96a66cSDavid du Colombier {
18485e96a66cSDavid du Colombier 	BList *p;
18495e96a66cSDavid du Colombier 
18505e96a66cSDavid du Colombier 	while(c->uhead != nil){
18515e96a66cSDavid du Colombier 		p = c->uhead;
18525e96a66cSDavid du Colombier 		c->uhead = p->next;
18535e96a66cSDavid du Colombier 		vtUnlock(c->lk);
18545e96a66cSDavid du Colombier 
18555e96a66cSDavid du Colombier 		if(!unlinkBlock(c, p->addr, p->type, p->tag, p->epoch))
18565e96a66cSDavid du Colombier 			fprint(2, "unlinkBlock failed: addr=%x type=%d tag = %ux: %r\n",
18575e96a66cSDavid du Colombier 				p->addr, p->type, p->tag);
18585e96a66cSDavid du Colombier 
18595e96a66cSDavid du Colombier 		vtLock(c->lk);
18605e96a66cSDavid du Colombier 		p->next = c->blfree;
18615e96a66cSDavid du Colombier 		c->blfree = p;
18625e96a66cSDavid du Colombier 	}
18635e96a66cSDavid du Colombier }
18645e96a66cSDavid du Colombier 
18655e96a66cSDavid du Colombier /*
18665e96a66cSDavid du Colombier  * Occasionally unlink the blocks on the cache unlink queue.
18675e96a66cSDavid du Colombier  */
18685e96a66cSDavid du Colombier static void
18695e96a66cSDavid du Colombier unlinkThread(void *a)
18705e96a66cSDavid du Colombier {
18715e96a66cSDavid du Colombier 	Cache *c = a;
18725e96a66cSDavid du Colombier 
18735e96a66cSDavid du Colombier 	vtThreadSetName("unlink");
18745e96a66cSDavid du Colombier 
18755e96a66cSDavid du Colombier 	vtLock(c->lk);
18765e96a66cSDavid du Colombier 	for(;;){
18775e96a66cSDavid du Colombier 		while(c->uhead == nil && c->die == nil)
18785e96a66cSDavid du Colombier 			vtSleep(c->unlink);
18795e96a66cSDavid du Colombier 		if(c->die != nil)
18805e96a66cSDavid du Colombier 			break;
18815e96a66cSDavid du Colombier 		unlinkBody(c);
18825e96a66cSDavid du Colombier 	}
18835e96a66cSDavid du Colombier 	c->ref--;
18845e96a66cSDavid du Colombier 	vtWakeup(c->die);
18855e96a66cSDavid du Colombier 	vtUnlock(c->lk);
18865e96a66cSDavid du Colombier }
18875e96a66cSDavid du Colombier 
18885e96a66cSDavid du Colombier static int
18895e96a66cSDavid du Colombier baddrCmp(void *a0, void *a1)
18905e96a66cSDavid du Colombier {
18915e96a66cSDavid du Colombier 	BAddr *b0, *b1;
18925e96a66cSDavid du Colombier 	b0 = a0;
18935e96a66cSDavid du Colombier 	b1 = a1;
18945e96a66cSDavid du Colombier 
18955e96a66cSDavid du Colombier 	if(b0->part < b1->part)
18965e96a66cSDavid du Colombier 		return -1;
18975e96a66cSDavid du Colombier 	if(b0->part > b1->part)
18985e96a66cSDavid du Colombier 		return 1;
18995e96a66cSDavid du Colombier 	if(b0->addr < b1->addr)
19005e96a66cSDavid du Colombier 		return -1;
19015e96a66cSDavid du Colombier 	if(b0->addr > b1->addr)
19025e96a66cSDavid du Colombier 		return 1;
19035e96a66cSDavid du Colombier 	return 0;
19045e96a66cSDavid du Colombier }
19055e96a66cSDavid du Colombier 
19065e96a66cSDavid du Colombier /*
19075e96a66cSDavid du Colombier  * Scan the block list for dirty blocks; add them to the list c->baddr.
19085e96a66cSDavid du Colombier  */
19095e96a66cSDavid du Colombier static void
19105e96a66cSDavid du Colombier flushFill(Cache *c)
19115e96a66cSDavid du Colombier {
191261201b97SDavid du Colombier 	int i, ndirty;
19135e96a66cSDavid du Colombier 	BAddr *p;
19145e96a66cSDavid du Colombier 	Block *b;
19155e96a66cSDavid du Colombier 
19165e96a66cSDavid du Colombier 	vtLock(c->lk);
191739734e7eSDavid du Colombier 	if(c->ndirty == 0){
191839734e7eSDavid du Colombier 		vtUnlock(c->lk);
191939734e7eSDavid du Colombier 		return;
192039734e7eSDavid du Colombier 	}
19215e96a66cSDavid du Colombier 
19225e96a66cSDavid du Colombier 	p = c->baddr;
192361201b97SDavid du Colombier 	ndirty = 0;
19245e96a66cSDavid du Colombier 	for(i=0; i<c->nblocks; i++){
19255e96a66cSDavid du Colombier 		b = c->blocks + i;
192661201b97SDavid du Colombier 		if(b->part == PartError)
192761201b97SDavid du Colombier 			continue;
192861201b97SDavid du Colombier 		if(b->iostate == BioDirty || b->iostate == BioWriting)
192961201b97SDavid du Colombier 			ndirty++;
193061201b97SDavid du Colombier 		if(b->iostate != BioDirty)
19315e96a66cSDavid du Colombier 			continue;
19325e96a66cSDavid du Colombier 		p->part = b->part;
19335e96a66cSDavid du Colombier 		p->addr = b->addr;
19345e96a66cSDavid du Colombier 		p->vers = b->vers;
19355e96a66cSDavid du Colombier 		p++;
19365e96a66cSDavid du Colombier 	}
193761201b97SDavid du Colombier 	if(ndirty != c->ndirty){
193861201b97SDavid du Colombier 		fprint(2, "ndirty mismatch expected %d found %d\n",
193961201b97SDavid du Colombier 			c->ndirty, ndirty);
194061201b97SDavid du Colombier 		c->ndirty = ndirty;
194161201b97SDavid du Colombier 	}
19425e96a66cSDavid du Colombier 	vtUnlock(c->lk);
19435e96a66cSDavid du Colombier 
19445e96a66cSDavid du Colombier 	c->bw = p - c->baddr;
19455e96a66cSDavid du Colombier 	qsort(c->baddr, c->bw, sizeof(BAddr), baddrCmp);
19465e96a66cSDavid du Colombier }
19475e96a66cSDavid du Colombier 
19485e96a66cSDavid du Colombier /*
19495e96a66cSDavid du Colombier  * This is not thread safe, i.e. it can't be called from multiple threads.
19505e96a66cSDavid du Colombier  *
19515e96a66cSDavid du Colombier  * It's okay how we use it, because it only gets called in
19525e96a66cSDavid du Colombier  * the flushThread.  And cacheFree, but only after
19535e96a66cSDavid du Colombier  * cacheFree has killed off the flushThread.
19545e96a66cSDavid du Colombier  */
19555e96a66cSDavid du Colombier static int
19565e96a66cSDavid du Colombier cacheFlushBlock(Cache *c)
19575e96a66cSDavid du Colombier {
19585e96a66cSDavid du Colombier 	Block *b;
19595e96a66cSDavid du Colombier 	BAddr *p;
19605e96a66cSDavid du Colombier 	int lockfail, nfail;
19615e96a66cSDavid du Colombier 
19625e96a66cSDavid du Colombier 	nfail = 0;
19635e96a66cSDavid du Colombier 	for(;;){
19645e96a66cSDavid du Colombier 		if(c->br == c->be){
19655e96a66cSDavid du Colombier 			if(c->bw == 0 || c->bw == c->be)
19665e96a66cSDavid du Colombier 				flushFill(c);
19675e96a66cSDavid du Colombier 			c->br = 0;
19685e96a66cSDavid du Colombier 			c->be = c->bw;
19695e96a66cSDavid du Colombier 			c->bw = 0;
19705e96a66cSDavid du Colombier 			c->nflush = 0;
19715e96a66cSDavid du Colombier 		}
19725e96a66cSDavid du Colombier 
19735e96a66cSDavid du Colombier 		if(c->br == c->be)
19745e96a66cSDavid du Colombier 			return 0;
19755e96a66cSDavid du Colombier 		p = c->baddr + c->br;
19765e96a66cSDavid du Colombier 		c->br++;
19775e96a66cSDavid du Colombier 		b = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
19785e96a66cSDavid du Colombier 
19795e96a66cSDavid du Colombier 		if(b && blockWrite(b)){
19805e96a66cSDavid du Colombier 			c->nflush++;
19815e96a66cSDavid du Colombier 			blockPut(b);
19825e96a66cSDavid du Colombier 			return 1;
19835e96a66cSDavid du Colombier 		}
19845e96a66cSDavid du Colombier 		if(b)
19855e96a66cSDavid du Colombier 			blockPut(b);
19865e96a66cSDavid du Colombier 
19875e96a66cSDavid du Colombier 		/*
19885e96a66cSDavid du Colombier 		 * Why didn't we write the block?
19895e96a66cSDavid du Colombier 		 */
19905e96a66cSDavid du Colombier 
19915e96a66cSDavid du Colombier 		/* Block already written out */
19925e96a66cSDavid du Colombier 		if(b == nil && !lockfail)
19935e96a66cSDavid du Colombier 			continue;
19945e96a66cSDavid du Colombier 
19955e96a66cSDavid du Colombier 		/* Failed to acquire lock; sleep if happens a lot. */
1996*fe853e23SDavid du Colombier 		if(lockfail && ++nfail > 100){
19975e96a66cSDavid du Colombier 			sleep(500);
1998*fe853e23SDavid du Colombier 			nfail = 0;
1999*fe853e23SDavid du Colombier 		}
20005e96a66cSDavid du Colombier 		/* Requeue block. */
20015e96a66cSDavid du Colombier 		if(c->bw < c->be)
20025e96a66cSDavid du Colombier 			c->baddr[c->bw++] = *p;
20035e96a66cSDavid du Colombier 	}
20045e96a66cSDavid du Colombier 	return 0;
20055e96a66cSDavid du Colombier }
20065e96a66cSDavid du Colombier 
20075e96a66cSDavid du Colombier /*
20085e96a66cSDavid du Colombier  * Occasionally flush dirty blocks from memory to the disk.
20095e96a66cSDavid du Colombier  */
20105e96a66cSDavid du Colombier static void
20115e96a66cSDavid du Colombier flushThread(void *a)
20125e96a66cSDavid du Colombier {
20135e96a66cSDavid du Colombier 	Cache *c = a;
20145e96a66cSDavid du Colombier 	int i;
20155e96a66cSDavid du Colombier 
20165e96a66cSDavid du Colombier 	vtThreadSetName("flush");
20175e96a66cSDavid du Colombier 	vtLock(c->lk);
20185e96a66cSDavid du Colombier 	while(c->die == nil){
20195e96a66cSDavid du Colombier 		vtSleep(c->flush);
20205e96a66cSDavid du Colombier 		vtUnlock(c->lk);
20215e96a66cSDavid du Colombier 		for(i=0; i<FlushSize; i++)
202267031067SDavid du Colombier 			if(!cacheFlushBlock(c)){
202367031067SDavid du Colombier 				/*
202467031067SDavid du Colombier 				 * If i==0, could be someone is waking us repeatedly
202567031067SDavid du Colombier 				 * to flush the cache but there's no work to do.
202667031067SDavid du Colombier 				 * Pause a little.
202767031067SDavid du Colombier 				 */
202867031067SDavid du Colombier 				if(i==0)
202967031067SDavid du Colombier 					sleep(250);
20305e96a66cSDavid du Colombier 				break;
203167031067SDavid du Colombier 			}
203239734e7eSDavid du Colombier 		if(i==0 && c->ndirty){
203339734e7eSDavid du Colombier 			/*
203439734e7eSDavid du Colombier 			 * All the blocks are being written right now -- there's nothing to do.
203539734e7eSDavid du Colombier 			 * We might be spinning with cacheFlush though -- he'll just keep
203639734e7eSDavid du Colombier 			 * kicking us until c->ndirty goes down.  Probably we should sleep
203739734e7eSDavid du Colombier 			 * on something that the diskThread can kick, but for now we'll
203839734e7eSDavid du Colombier 			 * just pause for a little while waiting for disks to finish.
203939734e7eSDavid du Colombier 			 */
204039734e7eSDavid du Colombier 			sleep(100);
204139734e7eSDavid du Colombier 		}
20425e96a66cSDavid du Colombier 		vtLock(c->lk);
20435e96a66cSDavid du Colombier 		vtWakeupAll(c->flushwait);
20445e96a66cSDavid du Colombier 	}
20455e96a66cSDavid du Colombier 	c->ref--;
20465e96a66cSDavid du Colombier 	vtWakeup(c->die);
20475e96a66cSDavid du Colombier 	vtUnlock(c->lk);
20485e96a66cSDavid du Colombier }
20495e96a66cSDavid du Colombier 
20505e96a66cSDavid du Colombier /*
20515e96a66cSDavid du Colombier  * Keep flushing until everything is clean.
20525e96a66cSDavid du Colombier  */
20535e96a66cSDavid du Colombier void
20545e96a66cSDavid du Colombier cacheFlush(Cache *c, int wait)
20555e96a66cSDavid du Colombier {
20565e96a66cSDavid du Colombier 	vtLock(c->lk);
20575e96a66cSDavid du Colombier 	if(wait){
20585e96a66cSDavid du Colombier 		while(c->ndirty){
2059dc5a79c1SDavid du Colombier 		//	consPrint("cacheFlush: %d dirty blocks, uhead %p\n",
2060dc5a79c1SDavid du Colombier 		//		c->ndirty, c->uhead);
20615e96a66cSDavid du Colombier 			vtWakeup(c->flush);
20625e96a66cSDavid du Colombier 			vtSleep(c->flushwait);
20635e96a66cSDavid du Colombier 		}
2064dc5a79c1SDavid du Colombier 	//	consPrint("cacheFlush: done (uhead %p)\n", c->ndirty, c->uhead);
20655e96a66cSDavid du Colombier 	}else
20665e96a66cSDavid du Colombier 		vtWakeup(c->flush);
20675e96a66cSDavid du Colombier 	vtUnlock(c->lk);
20685e96a66cSDavid du Colombier }
206961201b97SDavid du Colombier 
207061201b97SDavid du Colombier /*
207161201b97SDavid du Colombier  * Kick the flushThread every 30 seconds.
207261201b97SDavid du Colombier  */
207361201b97SDavid du Colombier static void
207461201b97SDavid du Colombier cacheSync(void *v)
207561201b97SDavid du Colombier {
207661201b97SDavid du Colombier 	Cache *c;
207761201b97SDavid du Colombier 
207861201b97SDavid du Colombier 	c = v;
207961201b97SDavid du Colombier 	cacheFlush(c, 0);
208061201b97SDavid du Colombier }
2081