1 a0d146ed 2005-07-12 devnull /*
  2 a0d146ed 2005-07-12 devnull  * Disk cache.
  3 a0d146ed 2005-07-12 devnull  * 
  4 a0d146ed 2005-07-12 devnull  * Caches raw disk blocks.  Getdblock() gets a block, putdblock puts it back.
  5 a0d146ed 2005-07-12 devnull  * Getdblock has a mode parameter that determines i/o and access to a block:
  6 a0d146ed 2005-07-12 devnull  * if mode is OREAD or ORDWR, it is read from disk if not already in memory.
  7 a0d146ed 2005-07-12 devnull  * If mode is ORDWR or OWRITE, it is locked for exclusive use before being returned.
  8 a0d146ed 2005-07-12 devnull  * It is *not* marked dirty -- once changes have been made, they should be noted
  9 a0d146ed 2005-07-12 devnull  * by using dirtydblock() before putdblock().  
 10 a0d146ed 2005-07-12 devnull  *
 11 a0d146ed 2005-07-12 devnull  * There is a global cache lock as well as a lock on each block. 
 12 a0d146ed 2005-07-12 devnull  * Within a thread, the cache lock can be acquired while holding a block lock,
 13 a0d146ed 2005-07-12 devnull  * but not vice versa; and a block cannot be locked if you already hold the lock
 14 a0d146ed 2005-07-12 devnull  * on another block.
 15 a0d146ed 2005-07-12 devnull  * 
 16 a0d146ed 2005-07-12 devnull  * The flush proc writes out dirty blocks in batches, one batch per dirty tag.
 17 a0d146ed 2005-07-12 devnull  * For example, the DirtyArena blocks are all written to disk before any of the
 18 a0d146ed 2005-07-12 devnull  * DirtyArenaCib blocks.
 19 a0d146ed 2005-07-12 devnull  *
 20 a0d146ed 2005-07-12 devnull  * This code used to be in charge of flushing the dirty index blocks out to 
 21 a0d146ed 2005-07-12 devnull  * disk, but updating the index turned out to benefit from extra care.
 22 a0d146ed 2005-07-12 devnull  * Now cached index blocks are never marked dirty.  The index.c code takes
 23 a0d146ed 2005-07-12 devnull  * care of updating them behind our back, and uses _getdblock to update any
 24 a0d146ed 2005-07-12 devnull  * cached copies of the blocks as it changes them on disk.
 25 a0d146ed 2005-07-12 devnull  */
 26 a0d146ed 2005-07-12 devnull 
 27 a0d146ed 2005-07-12 devnull #include "stdinc.h"
 28 a0d146ed 2005-07-12 devnull #include "dat.h"
 29 a0d146ed 2005-07-12 devnull #include "fns.h"
 30 a0d146ed 2005-07-12 devnull 
 31 a0d146ed 2005-07-12 devnull typedef struct DCache	DCache;
 32 a0d146ed 2005-07-12 devnull 
 33 a0d146ed 2005-07-12 devnull enum
 34 a0d146ed 2005-07-12 devnull {
 35 a0d146ed 2005-07-12 devnull 	HashLog		= 9,
 36 a0d146ed 2005-07-12 devnull 	HashSize	= 1<<HashLog,
 37 a0d146ed 2005-07-12 devnull 	HashMask	= HashSize - 1,
 38 a0d146ed 2005-07-12 devnull };
 39 a0d146ed 2005-07-12 devnull 
 40 a0d146ed 2005-07-12 devnull struct DCache
 41 a0d146ed 2005-07-12 devnull {
 42 a0d146ed 2005-07-12 devnull 	QLock		lock;
 43 a0d146ed 2005-07-12 devnull 	RWLock		dirtylock;		/* must be held to inspect or set b->dirty */
 44 a0d146ed 2005-07-12 devnull 	Rendez		full;
 45 a0d146ed 2005-07-12 devnull 	Round		round;
 46 a0d146ed 2005-07-12 devnull 	DBlock		*free;			/* list of available lumps */
 47 a0d146ed 2005-07-12 devnull 	u32int		now;			/* ticks for usage timestamps */
 48 a0d146ed 2005-07-12 devnull 	int		size;			/* max. size of any block; allocated to each block */
 49 a0d146ed 2005-07-12 devnull 	DBlock		**heads;		/* hash table for finding address */
 50 a0d146ed 2005-07-12 devnull 	int		nheap;			/* number of available victims */
 51 a0d146ed 2005-07-12 devnull 	DBlock		**heap;			/* heap for locating victims */
 52 a0d146ed 2005-07-12 devnull 	int		nblocks;		/* number of blocks allocated */
 53 a0d146ed 2005-07-12 devnull 	DBlock		*blocks;		/* array of block descriptors */
 54 a0d146ed 2005-07-12 devnull 	DBlock		**write;		/* array of block pointers to be written */
 55 a0d146ed 2005-07-12 devnull 	u8int		*mem;			/* memory for all block descriptors */
 56 a0d146ed 2005-07-12 devnull 	int		ndirty;			/* number of dirty blocks */
 57 a0d146ed 2005-07-12 devnull 	int		maxdirty;		/* max. number of dirty blocks */
 58 a0d146ed 2005-07-12 devnull 	Channel	*ra;
 59 a0d146ed 2005-07-12 devnull 	u8int		*rabuf;
 60 a0d146ed 2005-07-12 devnull 	u32int		ramax;
 61 a0d146ed 2005-07-12 devnull 	u32int		rasize;
 62 a0d146ed 2005-07-12 devnull 	u64int		raaddr;
 63 a0d146ed 2005-07-12 devnull 	Part		*rapart;
 64 a0d146ed 2005-07-12 devnull 
 65 a0d146ed 2005-07-12 devnull 	AState	diskstate;
 66 a0d146ed 2005-07-12 devnull 	AState	state;
 67 a0d146ed 2005-07-12 devnull };
 68 a0d146ed 2005-07-12 devnull 
 69 a0d146ed 2005-07-12 devnull typedef struct Ra Ra;
 70 a0d146ed 2005-07-12 devnull struct Ra
 71 a0d146ed 2005-07-12 devnull {
 72 a0d146ed 2005-07-12 devnull 	Part *part;
 73 a0d146ed 2005-07-12 devnull 	u64int addr;
 74 a0d146ed 2005-07-12 devnull };
 75 a0d146ed 2005-07-12 devnull 
 76 a0d146ed 2005-07-12 devnull static DCache	dcache;
 77 a0d146ed 2005-07-12 devnull 
 78 a0d146ed 2005-07-12 devnull static int	downheap(int i, DBlock *b);
 79 a0d146ed 2005-07-12 devnull static int	upheap(int i, DBlock *b);
 80 a0d146ed 2005-07-12 devnull static DBlock	*bumpdblock(void);
 81 a0d146ed 2005-07-12 devnull static void	delheap(DBlock *db);
 82 a0d146ed 2005-07-12 devnull static void	fixheap(int i, DBlock *b);
 83 a0d146ed 2005-07-12 devnull static void	flushproc(void*);
 84 a0d146ed 2005-07-12 devnull static void	writeproc(void*);
 85 a0d146ed 2005-07-12 devnull static void raproc(void*);
 86 a0d146ed 2005-07-12 devnull 
 87 a0d146ed 2005-07-12 devnull void
 88 a0d146ed 2005-07-12 devnull initdcache(u32int mem)
 89 a0d146ed 2005-07-12 devnull {
 90 a0d146ed 2005-07-12 devnull 	DBlock *b, *last;
 91 a0d146ed 2005-07-12 devnull 	u32int nblocks, blocksize;
 92 a0d146ed 2005-07-12 devnull 	int i;
 93 a0d146ed 2005-07-12 devnull 	u8int *p;
 94 a0d146ed 2005-07-12 devnull 
 95 a0d146ed 2005-07-12 devnull 	if(mem < maxblocksize * 2)
 96 a0d146ed 2005-07-12 devnull 		sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
 97 a0d146ed 2005-07-12 devnull 	if(maxblocksize == 0)
 98 a0d146ed 2005-07-12 devnull 		sysfatal("no max. block size given for disk cache");
 99 a0d146ed 2005-07-12 devnull 	blocksize = maxblocksize;
100 a0d146ed 2005-07-12 devnull 	nblocks = mem / blocksize;
101 a0d146ed 2005-07-12 devnull 	dcache.full.l = &dcache.lock;
102 a0d146ed 2005-07-12 devnull 	dcache.nblocks = nblocks;
103 a0d146ed 2005-07-12 devnull 	dcache.maxdirty = (nblocks * 2) / 3;
104 a0d146ed 2005-07-12 devnull 	trace(TraceProc, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
105 a0d146ed 2005-07-12 devnull 			nblocks, blocksize, dcache.maxdirty);
106 a0d146ed 2005-07-12 devnull 	dcache.size = blocksize;
107 a0d146ed 2005-07-12 devnull 	dcache.heads = MKNZ(DBlock*, HashSize);
108 a0d146ed 2005-07-12 devnull 	dcache.heap = MKNZ(DBlock*, nblocks);
109 a0d146ed 2005-07-12 devnull 	dcache.blocks = MKNZ(DBlock, nblocks);
110 a0d146ed 2005-07-12 devnull 	dcache.write = MKNZ(DBlock*, nblocks);
111 a0d146ed 2005-07-12 devnull 	dcache.mem = MKNZ(u8int, (nblocks+1+128) * blocksize);
112 a0d146ed 2005-07-12 devnull 	dcache.ra = chancreate(sizeof(Ra), 0);
113 a0d146ed 2005-07-12 devnull 
114 a0d146ed 2005-07-12 devnull 	last = nil;
115 a0d146ed 2005-07-12 devnull 	p = (u8int*)(((ulong)dcache.mem+blocksize-1)&~(ulong)(blocksize-1));
116 a0d146ed 2005-07-12 devnull 	for(i = 0; i < nblocks; i++){
117 a0d146ed 2005-07-12 devnull 		b = &dcache.blocks[i];
118 a0d146ed 2005-07-12 devnull 		b->data = &p[i * blocksize];
119 a0d146ed 2005-07-12 devnull 		b->heap = TWID32;
120 a0d146ed 2005-07-12 devnull 		b->writedonechan = chancreate(sizeof(void*), 1);
121 a0d146ed 2005-07-12 devnull 		b->next = last;
122 a0d146ed 2005-07-12 devnull 		last = b;
123 a0d146ed 2005-07-12 devnull 	}
124 a0d146ed 2005-07-12 devnull 	dcache.rabuf = &p[i*blocksize];
125 a0d146ed 2005-07-12 devnull 	dcache.ramax = 128*blocksize;
126 a0d146ed 2005-07-12 devnull 	dcache.raaddr = 0;
127 a0d146ed 2005-07-12 devnull 	dcache.rapart = nil;
128 a0d146ed 2005-07-12 devnull 
129 a0d146ed 2005-07-12 devnull 	dcache.free = last;
130 a0d146ed 2005-07-12 devnull 	dcache.nheap = 0;
131 a0d146ed 2005-07-12 devnull 	setstat(StatDcacheSize, nblocks);
132 a0d146ed 2005-07-12 devnull 	initround(&dcache.round, "dcache", 120*1000);
133 a0d146ed 2005-07-12 devnull 
134 a0d146ed 2005-07-12 devnull 	vtproc(flushproc, nil);
135 a0d146ed 2005-07-12 devnull 	vtproc(delaykickroundproc, &dcache.round);
136 a0d146ed 2005-07-12 devnull 	vtproc(raproc, nil);
137 a0d146ed 2005-07-12 devnull }
138 a0d146ed 2005-07-12 devnull 
139 a0d146ed 2005-07-12 devnull void
140 a0d146ed 2005-07-12 devnull setdcachestate(AState *a)
141 a0d146ed 2005-07-12 devnull {
142 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "setdcachestate %s 0x%llux clumps %d", a->arena ? a->arena->name : nil, a->aa, a->stats.clumps);
143 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
144 a0d146ed 2005-07-12 devnull 	dcache.state = *a;
145 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
146 a0d146ed 2005-07-12 devnull }
147 a0d146ed 2005-07-12 devnull 
148 a0d146ed 2005-07-12 devnull AState
149 a0d146ed 2005-07-12 devnull diskstate(void)
150 a0d146ed 2005-07-12 devnull {
151 a0d146ed 2005-07-12 devnull 	AState a;
152 a0d146ed 2005-07-12 devnull 
153 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
154 a0d146ed 2005-07-12 devnull 	a = dcache.diskstate;
155 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
156 a0d146ed 2005-07-12 devnull 	return a;
157 a0d146ed 2005-07-12 devnull }
158 a0d146ed 2005-07-12 devnull 
159 a0d146ed 2005-07-12 devnull static void
160 a0d146ed 2005-07-12 devnull raproc(void *v)
161 a0d146ed 2005-07-12 devnull {
162 a0d146ed 2005-07-12 devnull 	Ra ra;
163 a0d146ed 2005-07-12 devnull 	DBlock *b;
164 a0d146ed 2005-07-12 devnull 
165 a0d146ed 2005-07-12 devnull 	USED(v);
166 a0d146ed 2005-07-12 devnull 	while(recv(dcache.ra, &ra) == 1){
167 a0d146ed 2005-07-12 devnull 		if(ra.part->size <= ra.addr)
168 a0d146ed 2005-07-12 devnull 			continue;
169 a0d146ed 2005-07-12 devnull 		b = _getdblock(ra.part, ra.addr, OREAD, 2);
170 a0d146ed 2005-07-12 devnull 		putdblock(b);
171 a0d146ed 2005-07-12 devnull 	}
172 a0d146ed 2005-07-12 devnull }	
173 a0d146ed 2005-07-12 devnull 
174 a0d146ed 2005-07-12 devnull void
175 a0d146ed 2005-07-12 devnull dreadahead(Part *part, u64int addr, int miss)
176 a0d146ed 2005-07-12 devnull {
177 a0d146ed 2005-07-12 devnull 	Ra ra;
178 a0d146ed 2005-07-12 devnull 	static struct {
179 a0d146ed 2005-07-12 devnull 		Part *part;
180 a0d146ed 2005-07-12 devnull 		u64int addr;
181 a0d146ed 2005-07-12 devnull 	} lastmiss;
182 a0d146ed 2005-07-12 devnull 	static struct {
183 a0d146ed 2005-07-12 devnull 		Part *part;
184 a0d146ed 2005-07-12 devnull 		u64int addr;
185 a0d146ed 2005-07-12 devnull 		int dir;
186 a0d146ed 2005-07-12 devnull 	} lastra;
187 a0d146ed 2005-07-12 devnull 
188 a0d146ed 2005-07-12 devnull return;
189 a0d146ed 2005-07-12 devnull 	if(miss){
190 a0d146ed 2005-07-12 devnull 		if(lastmiss.part==part && lastmiss.addr==addr-dcache.size){
191 a0d146ed 2005-07-12 devnull 		XRa:
192 a0d146ed 2005-07-12 devnull 			lastra.part = part;
193 a0d146ed 2005-07-12 devnull 			lastra.dir = addr-lastmiss.addr;
194 a0d146ed 2005-07-12 devnull 			lastra.addr = addr+lastra.dir;
195 a0d146ed 2005-07-12 devnull 			ra.part = part;
196 a0d146ed 2005-07-12 devnull 			ra.addr = lastra.addr;
197 a0d146ed 2005-07-12 devnull 			nbsend(dcache.ra, &ra);
198 a0d146ed 2005-07-12 devnull 		}else if(lastmiss.part==part && lastmiss.addr==addr+dcache.size){
199 a0d146ed 2005-07-12 devnull 			addr -= dcache.size;
200 a0d146ed 2005-07-12 devnull 			goto XRa;
201 a0d146ed 2005-07-12 devnull 		}
202 a0d146ed 2005-07-12 devnull 	}else{
203 a0d146ed 2005-07-12 devnull 		if(lastra.part==part && lastra.addr==addr){
204 a0d146ed 2005-07-12 devnull 			lastra.addr += lastra.dir;
205 a0d146ed 2005-07-12 devnull 			ra.part = part;
206 a0d146ed 2005-07-12 devnull 			ra.addr = lastra.addr;
207 a0d146ed 2005-07-12 devnull 			nbsend(dcache.ra, &ra);
208 a0d146ed 2005-07-12 devnull 		}
209 a0d146ed 2005-07-12 devnull 	}
210 a0d146ed 2005-07-12 devnull 
211 a0d146ed 2005-07-12 devnull 	if(miss){
212 a0d146ed 2005-07-12 devnull 		lastmiss.part = part;
213 a0d146ed 2005-07-12 devnull 		lastmiss.addr = addr;
214 a0d146ed 2005-07-12 devnull 	}
215 a0d146ed 2005-07-12 devnull 
216 a0d146ed 2005-07-12 devnull //	fprint(2, "%s %llx %s\n", part->name, addr, miss ? "miss" : "hit");
217 a0d146ed 2005-07-12 devnull }
218 a0d146ed 2005-07-12 devnull 
219 a0d146ed 2005-07-12 devnull int
220 a0d146ed 2005-07-12 devnull rareadpart(Part *part, u64int addr, u8int *buf, uint n, int load)
221 a0d146ed 2005-07-12 devnull {
222 a0d146ed 2005-07-12 devnull 	uint nn;
223 a0d146ed 2005-07-12 devnull 	static RWLock ralock;
224 a0d146ed 2005-07-12 devnull 
225 a0d146ed 2005-07-12 devnull 	rlock(&ralock);
226 a0d146ed 2005-07-12 devnull 	if(dcache.rapart==part && dcache.raaddr <= addr && addr+n <= dcache.raaddr+dcache.rasize){
227 a0d146ed 2005-07-12 devnull 		memmove(buf, dcache.rabuf+(addr-dcache.raaddr), n);
228 a0d146ed 2005-07-12 devnull 		runlock(&ralock);
229 a0d146ed 2005-07-12 devnull 		return 0;
230 a0d146ed 2005-07-12 devnull 	}
231 a0d146ed 2005-07-12 devnull 	if(load != 2 || addr >= part->size){	/* addr >= part->size: let readpart do the error */	
232 a0d146ed 2005-07-12 devnull 		runlock(&ralock);
233 a0d146ed 2005-07-12 devnull 		return readpart(part, addr, buf, n);
234 a0d146ed 2005-07-12 devnull 	}
235 a0d146ed 2005-07-12 devnull 
236 a0d146ed 2005-07-12 devnull 	runlock(&ralock);
237 a0d146ed 2005-07-12 devnull 	wlock(&ralock);
238 a0d146ed 2005-07-12 devnull fprint(2, "raread %s %llx\n", part->name, addr);
239 a0d146ed 2005-07-12 devnull 	nn = dcache.ramax;
240 a0d146ed 2005-07-12 devnull 	if(addr+nn > part->size)
241 a0d146ed 2005-07-12 devnull 		nn = part->size - addr;
242 a0d146ed 2005-07-12 devnull 	if(readpart(part, addr, dcache.rabuf, nn) < 0){
243 a0d146ed 2005-07-12 devnull 		wunlock(&ralock);
244 a0d146ed 2005-07-12 devnull 		return -1;
245 a0d146ed 2005-07-12 devnull 	}
246 a0d146ed 2005-07-12 devnull 	memmove(buf, dcache.rabuf, n);	
247 a0d146ed 2005-07-12 devnull 	dcache.rapart = part;
248 a0d146ed 2005-07-12 devnull 	dcache.rasize = nn;
249 a0d146ed 2005-07-12 devnull 	dcache.raaddr = addr;
250 a0d146ed 2005-07-12 devnull 	wunlock(&ralock);
251 a0d146ed 2005-07-12 devnull 
252 a0d146ed 2005-07-12 devnull 	addstat(StatApartReadBytes, nn-n);
253 a0d146ed 2005-07-12 devnull 	return 0;
254 a0d146ed 2005-07-12 devnull }
255 a0d146ed 2005-07-12 devnull 
256 a0d146ed 2005-07-12 devnull static u32int
257 a0d146ed 2005-07-12 devnull pbhash(u64int addr)
258 a0d146ed 2005-07-12 devnull {
259 a0d146ed 2005-07-12 devnull 	u32int h;
260 a0d146ed 2005-07-12 devnull 
261 a0d146ed 2005-07-12 devnull #define hashit(c)	((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
262 a0d146ed 2005-07-12 devnull 	h = (addr >> 32) ^ addr;
263 a0d146ed 2005-07-12 devnull 	return hashit(h);
264 a0d146ed 2005-07-12 devnull }
265 a0d146ed 2005-07-12 devnull 
266 a0d146ed 2005-07-12 devnull DBlock*
267 a0d146ed 2005-07-12 devnull getdblock(Part *part, u64int addr, int mode)
268 a0d146ed 2005-07-12 devnull {
269 a0d146ed 2005-07-12 devnull 	DBlock *b;
270 a0d146ed 2005-07-12 devnull 	uint ms;
271 a0d146ed 2005-07-12 devnull 	
272 a0d146ed 2005-07-12 devnull 	ms = msec();
273 a0d146ed 2005-07-12 devnull 	b = _getdblock(part, addr, mode, 1);
274 a0d146ed 2005-07-12 devnull 	if(mode == OREAD || mode == ORDWR)
275 a0d146ed 2005-07-12 devnull 		addstat(StatDcacheRead, 1);
276 a0d146ed 2005-07-12 devnull 	if(mode == OWRITE || mode == ORDWR)
277 a0d146ed 2005-07-12 devnull 		addstat(StatDcacheWrite, 1);
278 a0d146ed 2005-07-12 devnull 	ms = msec() - ms;
279 a0d146ed 2005-07-12 devnull 	addstat2(StatDcacheLookup, 1, StatDcacheLookupTime, ms);
280 a0d146ed 2005-07-12 devnull 	return b;
281 a0d146ed 2005-07-12 devnull }
282 a0d146ed 2005-07-12 devnull 
283 a0d146ed 2005-07-12 devnull DBlock*
284 a0d146ed 2005-07-12 devnull _getdblock(Part *part, u64int addr, int mode, int load)
285 a0d146ed 2005-07-12 devnull {
286 a0d146ed 2005-07-12 devnull 	DBlock *b;
287 a0d146ed 2005-07-12 devnull 	u32int h, size;
288 a0d146ed 2005-07-12 devnull 
289 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "getdblock enter %s 0x%llux", part->name, addr);
290 a0d146ed 2005-07-12 devnull 	size = part->blocksize;
291 a0d146ed 2005-07-12 devnull 	if(size > dcache.size){
292 a0d146ed 2005-07-12 devnull 		seterr(EAdmin, "block size %d too big for cache with size %d", size, dcache.size);
293 a0d146ed 2005-07-12 devnull 		return nil;
294 a0d146ed 2005-07-12 devnull 	}
295 a0d146ed 2005-07-12 devnull 	h = pbhash(addr);
296 a0d146ed 2005-07-12 devnull 
297 a0d146ed 2005-07-12 devnull 	/*
298 a0d146ed 2005-07-12 devnull 	 * look for the block in the cache
299 a0d146ed 2005-07-12 devnull 	 */
300 a0d146ed 2005-07-12 devnull //checkdcache();
301 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
302 a0d146ed 2005-07-12 devnull again:
303 a0d146ed 2005-07-12 devnull 	for(b = dcache.heads[h]; b != nil; b = b->next){
304 a0d146ed 2005-07-12 devnull 		if(b->part == part && b->addr == addr){
305 a0d146ed 2005-07-12 devnull 			/*
306 a0d146ed 2005-07-12 devnull 			qlock(&stats.lock);
307 a0d146ed 2005-07-12 devnull 			stats.pchit++;
308 a0d146ed 2005-07-12 devnull 			qunlock(&stats.lock);
309 a0d146ed 2005-07-12 devnull 			*/
310 a0d146ed 2005-07-12 devnull 			if(load){
311 a0d146ed 2005-07-12 devnull 				addstat(StatDcacheHit, 1);
312 a0d146ed 2005-07-12 devnull 				if(load != 2 && mode != OWRITE)
313 a0d146ed 2005-07-12 devnull 					dreadahead(part, b->addr, 0);
314 a0d146ed 2005-07-12 devnull 			}
315 a0d146ed 2005-07-12 devnull 			goto found;
316 a0d146ed 2005-07-12 devnull 		}
317 a0d146ed 2005-07-12 devnull 	}
318 a0d146ed 2005-07-12 devnull 
319 a0d146ed 2005-07-12 devnull 	/*
320 a0d146ed 2005-07-12 devnull 	 * missed: locate the block with the oldest second to last use.
321 a0d146ed 2005-07-12 devnull 	 * remove it from the heap, and fix up the heap.
322 a0d146ed 2005-07-12 devnull 	 */
323 a0d146ed 2005-07-12 devnull 	if(!load){
324 a0d146ed 2005-07-12 devnull 		qunlock(&dcache.lock);
325 a0d146ed 2005-07-12 devnull 		return nil;
326 a0d146ed 2005-07-12 devnull 	}
327 a0d146ed 2005-07-12 devnull 
328 a0d146ed 2005-07-12 devnull 	addstat(StatDcacheMiss, 1);
329 a0d146ed 2005-07-12 devnull 
330 a0d146ed 2005-07-12 devnull 	b = bumpdblock();
331 a0d146ed 2005-07-12 devnull 	if(b == nil){
332 a0d146ed 2005-07-12 devnull 		trace(TraceBlock, "all disk cache blocks in use");
333 a0d146ed 2005-07-12 devnull 		addstat(StatDcacheStall, 1);
334 a0d146ed 2005-07-12 devnull 		rsleep(&dcache.full);
335 a0d146ed 2005-07-12 devnull 		addstat(StatDcacheStall, -1);
336 a0d146ed 2005-07-12 devnull 		goto again;
337 a0d146ed 2005-07-12 devnull 	}
338 a0d146ed 2005-07-12 devnull 
339 a0d146ed 2005-07-12 devnull 	assert(!b->dirty);
340 a0d146ed 2005-07-12 devnull 
341 a0d146ed 2005-07-12 devnull 	/*
342 a0d146ed 2005-07-12 devnull 	 * the new block has no last use, so assume it happens sometime in the middle
343 a0d146ed 2005-07-12 devnull ZZZ this is not reasonable
344 a0d146ed 2005-07-12 devnull 	 */
345 a0d146ed 2005-07-12 devnull 	b->used = (b->used2 + dcache.now) / 2;
346 a0d146ed 2005-07-12 devnull 
347 a0d146ed 2005-07-12 devnull 	/*
348 a0d146ed 2005-07-12 devnull 	 * rechain the block on the correct hash chain
349 a0d146ed 2005-07-12 devnull 	 */
350 a0d146ed 2005-07-12 devnull 	b->next = dcache.heads[h];
351 a0d146ed 2005-07-12 devnull 	dcache.heads[h] = b;
352 a0d146ed 2005-07-12 devnull 	if(b->next != nil)
353 a0d146ed 2005-07-12 devnull 		b->next->prev = b;
354 a0d146ed 2005-07-12 devnull 	b->prev = nil;
355 a0d146ed 2005-07-12 devnull 
356 a0d146ed 2005-07-12 devnull 	b->addr = addr;
357 a0d146ed 2005-07-12 devnull 	b->part = part;
358 a0d146ed 2005-07-12 devnull 	b->size = 0;
359 a0d146ed 2005-07-12 devnull 	if(load != 2 && mode != OWRITE)
360 a0d146ed 2005-07-12 devnull 		dreadahead(part, b->addr, 1);
361 a0d146ed 2005-07-12 devnull 
362 a0d146ed 2005-07-12 devnull found:
363 a0d146ed 2005-07-12 devnull 	b->ref++;
364 a0d146ed 2005-07-12 devnull 	b->used2 = b->used;
365 a0d146ed 2005-07-12 devnull 	b->used = dcache.now++;
366 a0d146ed 2005-07-12 devnull 	if(b->heap != TWID32)
367 a0d146ed 2005-07-12 devnull 		fixheap(b->heap, b);
368 a0d146ed 2005-07-12 devnull 
369 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
370 a0d146ed 2005-07-12 devnull //checkdcache();
371 a0d146ed 2005-07-12 devnull 
372 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "getdblock lock");
373 a0d146ed 2005-07-12 devnull 	addstat(StatDblockStall, 1);
374 a0d146ed 2005-07-12 devnull 	if(mode == OREAD)
375 a0d146ed 2005-07-12 devnull 		rlock(&b->lock);
376 a0d146ed 2005-07-12 devnull 	else
377 a0d146ed 2005-07-12 devnull 		wlock(&b->lock);
378 a0d146ed 2005-07-12 devnull 	addstat(StatDblockStall, -1);
379 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "getdblock locked");
380 a0d146ed 2005-07-12 devnull 
381 a0d146ed 2005-07-12 devnull 	if(b->size != size){
382 a0d146ed 2005-07-12 devnull 		if(mode == OREAD){
383 a0d146ed 2005-07-12 devnull 			addstat(StatDblockStall, 1);
384 a0d146ed 2005-07-12 devnull 			runlock(&b->lock);
385 a0d146ed 2005-07-12 devnull 			wlock(&b->lock);
386 a0d146ed 2005-07-12 devnull 			addstat(StatDblockStall, -1);
387 a0d146ed 2005-07-12 devnull 		}
388 a0d146ed 2005-07-12 devnull 		if(b->size < size){
389 a0d146ed 2005-07-12 devnull 			if(mode == OWRITE)
390 a0d146ed 2005-07-12 devnull 				memset(&b->data[b->size], 0, size - b->size);
391 a0d146ed 2005-07-12 devnull 			else{
392 a0d146ed 2005-07-12 devnull 				trace(TraceBlock, "getdblock readpart %s 0x%llux", part->name, addr);
393 a0d146ed 2005-07-12 devnull 				if(rareadpart(part, addr + b->size, &b->data[b->size], size - b->size, load) < 0){
394 a0d146ed 2005-07-12 devnull 					b->mode = ORDWR;	/* so putdblock wunlocks */
395 a0d146ed 2005-07-12 devnull 					putdblock(b);
396 a0d146ed 2005-07-12 devnull 					return nil;
397 a0d146ed 2005-07-12 devnull 				}
398 a0d146ed 2005-07-12 devnull 				trace(TraceBlock, "getdblock readpartdone");
399 a0d146ed 2005-07-12 devnull 				addstat(StatApartRead, 1);
400 a0d146ed 2005-07-12 devnull 				addstat(StatApartReadBytes, size-b->size);
401 a0d146ed 2005-07-12 devnull 			}
402 a0d146ed 2005-07-12 devnull 		}
403 a0d146ed 2005-07-12 devnull 		b->size = size;
404 a0d146ed 2005-07-12 devnull 		if(mode == OREAD){
405 a0d146ed 2005-07-12 devnull 			addstat(StatDblockStall, 1);
406 a0d146ed 2005-07-12 devnull 			wunlock(&b->lock);
407 a0d146ed 2005-07-12 devnull 			rlock(&b->lock);
408 a0d146ed 2005-07-12 devnull 			addstat(StatDblockStall, -1);
409 a0d146ed 2005-07-12 devnull 		}
410 a0d146ed 2005-07-12 devnull 	}
411 a0d146ed 2005-07-12 devnull 
412 a0d146ed 2005-07-12 devnull 	b->mode = mode;
413 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "getdblock exit");
414 a0d146ed 2005-07-12 devnull 	return b;
415 a0d146ed 2005-07-12 devnull }
416 a0d146ed 2005-07-12 devnull 
417 a0d146ed 2005-07-12 devnull void
418 a0d146ed 2005-07-12 devnull putdblock(DBlock *b)
419 a0d146ed 2005-07-12 devnull {
420 a0d146ed 2005-07-12 devnull 	if(b == nil)
421 a0d146ed 2005-07-12 devnull 		return;
422 a0d146ed 2005-07-12 devnull 
423 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "putdblock %s 0x%llux", b->part->name, b->addr);
424 a0d146ed 2005-07-12 devnull 
425 a0d146ed 2005-07-12 devnull 	if(b->mode == OREAD)
426 a0d146ed 2005-07-12 devnull 		runlock(&b->lock);
427 a0d146ed 2005-07-12 devnull 	else
428 a0d146ed 2005-07-12 devnull 		wunlock(&b->lock);
429 a0d146ed 2005-07-12 devnull 
430 a0d146ed 2005-07-12 devnull //checkdcache();
431 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
432 a0d146ed 2005-07-12 devnull 	if(--b->ref == 0 && !b->dirty){
433 a0d146ed 2005-07-12 devnull 		if(b->heap == TWID32)
434 a0d146ed 2005-07-12 devnull 			upheap(dcache.nheap++, b);
435 a0d146ed 2005-07-12 devnull 		rwakeupall(&dcache.full);
436 a0d146ed 2005-07-12 devnull 	}
437 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
438 a0d146ed 2005-07-12 devnull //checkdcache();
439 a0d146ed 2005-07-12 devnull }
440 a0d146ed 2005-07-12 devnull 
441 a0d146ed 2005-07-12 devnull void
442 a0d146ed 2005-07-12 devnull dirtydblock(DBlock *b, int dirty)
443 a0d146ed 2005-07-12 devnull {
444 a0d146ed 2005-07-12 devnull 	int odirty;
445 a0d146ed 2005-07-12 devnull 	Part *p;
446 a0d146ed 2005-07-12 devnull 
447 a0d146ed 2005-07-12 devnull 
448 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "dirtydblock enter %s 0x%llux %d from 0x%lux", b->part->name, b->addr, dirty, getcallerpc(&b));
449 a0d146ed 2005-07-12 devnull 	assert(b->ref != 0);
450 a0d146ed 2005-07-12 devnull 	assert(b->mode==ORDWR || b->mode==OWRITE);
451 a0d146ed 2005-07-12 devnull 
452 a0d146ed 2005-07-12 devnull 	odirty = b->dirty;
453 a0d146ed 2005-07-12 devnull 	if(b->dirty)
454 a0d146ed 2005-07-12 devnull 		assert(b->dirty == dirty);
455 a0d146ed 2005-07-12 devnull 	else
456 a0d146ed 2005-07-12 devnull 		b->dirty = dirty;
457 a0d146ed 2005-07-12 devnull 
458 a0d146ed 2005-07-12 devnull 	p = b->part;
459 a0d146ed 2005-07-12 devnull 	if(p->writechan == nil){
460 a0d146ed 2005-07-12 devnull 		trace(TraceBlock, "dirtydblock allocwriteproc %s", p->name);
461 a0d146ed 2005-07-12 devnull 		/* XXX hope this doesn't fail! */
462 a0d146ed 2005-07-12 devnull 		p->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
463 a0d146ed 2005-07-12 devnull 		vtproc(writeproc, p);
464 a0d146ed 2005-07-12 devnull 	}
465 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
466 a0d146ed 2005-07-12 devnull 	if(!odirty){
467 a0d146ed 2005-07-12 devnull 		dcache.ndirty++;
468 a0d146ed 2005-07-12 devnull 		setstat(StatDcacheDirty, dcache.ndirty);
469 a0d146ed 2005-07-12 devnull 		if(dcache.ndirty >= dcache.maxdirty)
470 a0d146ed 2005-07-12 devnull 			kickround(&dcache.round, 0);
471 a0d146ed 2005-07-12 devnull 		else
472 a0d146ed 2005-07-12 devnull 			delaykickround(&dcache.round);
473 a0d146ed 2005-07-12 devnull 	}
474 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
475 a0d146ed 2005-07-12 devnull }
476 a0d146ed 2005-07-12 devnull 
477 a0d146ed 2005-07-12 devnull /*
478 a0d146ed 2005-07-12 devnull  * remove some block from use and update the free list and counters
479 a0d146ed 2005-07-12 devnull  */
480 a0d146ed 2005-07-12 devnull static DBlock*
481 a0d146ed 2005-07-12 devnull bumpdblock(void)
482 a0d146ed 2005-07-12 devnull {
483 a0d146ed 2005-07-12 devnull 	DBlock *b;
484 a0d146ed 2005-07-12 devnull 	ulong h;
485 a0d146ed 2005-07-12 devnull 
486 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "bumpdblock enter");
487 a0d146ed 2005-07-12 devnull 	b = dcache.free;
488 a0d146ed 2005-07-12 devnull 	if(b != nil){
489 a0d146ed 2005-07-12 devnull 		dcache.free = b->next;
490 a0d146ed 2005-07-12 devnull 		return b;
491 a0d146ed 2005-07-12 devnull 	}
492 a0d146ed 2005-07-12 devnull 
493 a0d146ed 2005-07-12 devnull 	if(dcache.ndirty >= dcache.maxdirty)
494 a0d146ed 2005-07-12 devnull 		kickdcache();
495 a0d146ed 2005-07-12 devnull 
496 a0d146ed 2005-07-12 devnull 	/*
497 a0d146ed 2005-07-12 devnull 	 * remove blocks until we find one that is unused
498 a0d146ed 2005-07-12 devnull 	 * referenced blocks are left in the heap even though
499 a0d146ed 2005-07-12 devnull 	 * they can't be scavenged; this is simple a speed optimization
500 a0d146ed 2005-07-12 devnull 	 */
501 a0d146ed 2005-07-12 devnull 	for(;;){
502 a0d146ed 2005-07-12 devnull 		if(dcache.nheap == 0){
503 a0d146ed 2005-07-12 devnull 			kickdcache();
504 a0d146ed 2005-07-12 devnull 			trace(TraceBlock, "bumpdblock gotnothing");
505 a0d146ed 2005-07-12 devnull 			return nil;
506 a0d146ed 2005-07-12 devnull 		}
507 a0d146ed 2005-07-12 devnull 		b = dcache.heap[0];
508 a0d146ed 2005-07-12 devnull 		delheap(b);
509 a0d146ed 2005-07-12 devnull 		if(!b->ref && !b->dirty)
510 a0d146ed 2005-07-12 devnull 			break;
511 a0d146ed 2005-07-12 devnull 	}
512 a0d146ed 2005-07-12 devnull 
513 a0d146ed 2005-07-12 devnull 	trace(TraceBlock, "bumpdblock bumping %s 0x%llux", b->part->name, b->addr);
514 a0d146ed 2005-07-12 devnull 
515 a0d146ed 2005-07-12 devnull 	/*
516 a0d146ed 2005-07-12 devnull 	 * unchain the block
517 a0d146ed 2005-07-12 devnull 	 */
518 a0d146ed 2005-07-12 devnull 	if(b->prev == nil){
519 a0d146ed 2005-07-12 devnull 		h = pbhash(b->addr);
520 a0d146ed 2005-07-12 devnull 		if(dcache.heads[h] != b)
521 a0d146ed 2005-07-12 devnull 			sysfatal("bad hash chains in disk cache");
522 a0d146ed 2005-07-12 devnull 		dcache.heads[h] = b->next;
523 a0d146ed 2005-07-12 devnull 	}else
524 a0d146ed 2005-07-12 devnull 		b->prev->next = b->next;
525 a0d146ed 2005-07-12 devnull 	if(b->next != nil)
526 a0d146ed 2005-07-12 devnull 		b->next->prev = b->prev;
527 a0d146ed 2005-07-12 devnull 
528 a0d146ed 2005-07-12 devnull 	return b;
529 a0d146ed 2005-07-12 devnull }
530 a0d146ed 2005-07-12 devnull 
531 a0d146ed 2005-07-12 devnull /*
532 a0d146ed 2005-07-12 devnull  * delete an arbitrary block from the heap
533 a0d146ed 2005-07-12 devnull  */
534 a0d146ed 2005-07-12 devnull static void
535 a0d146ed 2005-07-12 devnull delheap(DBlock *db)
536 a0d146ed 2005-07-12 devnull {
537 a0d146ed 2005-07-12 devnull 	if(db->heap == TWID32)
538 a0d146ed 2005-07-12 devnull 		return;
539 a0d146ed 2005-07-12 devnull 	fixheap(db->heap, dcache.heap[--dcache.nheap]);
540 a0d146ed 2005-07-12 devnull 	db->heap = TWID32;
541 a0d146ed 2005-07-12 devnull }
542 a0d146ed 2005-07-12 devnull 
543 a0d146ed 2005-07-12 devnull /*
544 a0d146ed 2005-07-12 devnull  * push an element up or down to it's correct new location
545 a0d146ed 2005-07-12 devnull  */
546 a0d146ed 2005-07-12 devnull static void
547 a0d146ed 2005-07-12 devnull fixheap(int i, DBlock *b)
548 a0d146ed 2005-07-12 devnull {
549 a0d146ed 2005-07-12 devnull 	if(upheap(i, b) == i)
550 a0d146ed 2005-07-12 devnull 		downheap(i, b);
551 a0d146ed 2005-07-12 devnull }
552 a0d146ed 2005-07-12 devnull 
553 a0d146ed 2005-07-12 devnull static int
554 a0d146ed 2005-07-12 devnull upheap(int i, DBlock *b)
555 a0d146ed 2005-07-12 devnull {
556 a0d146ed 2005-07-12 devnull 	DBlock *bb;
557 a0d146ed 2005-07-12 devnull 	u32int now;
558 a0d146ed 2005-07-12 devnull 	int p;
559 a0d146ed 2005-07-12 devnull 
560 a0d146ed 2005-07-12 devnull 	now = dcache.now;
561 a0d146ed 2005-07-12 devnull 	for(; i != 0; i = p){
562 a0d146ed 2005-07-12 devnull 		p = (i - 1) >> 1;
563 a0d146ed 2005-07-12 devnull 		bb = dcache.heap[p];
564 a0d146ed 2005-07-12 devnull 		if(b->used2 - now >= bb->used2 - now)
565 a0d146ed 2005-07-12 devnull 			break;
566 a0d146ed 2005-07-12 devnull 		dcache.heap[i] = bb;
567 a0d146ed 2005-07-12 devnull 		bb->heap = i;
568 a0d146ed 2005-07-12 devnull 	}
569 a0d146ed 2005-07-12 devnull 
570 a0d146ed 2005-07-12 devnull 	dcache.heap[i] = b;
571 a0d146ed 2005-07-12 devnull 	b->heap = i;
572 a0d146ed 2005-07-12 devnull 	return i;
573 a0d146ed 2005-07-12 devnull }
574 a0d146ed 2005-07-12 devnull 
575 a0d146ed 2005-07-12 devnull static int
576 a0d146ed 2005-07-12 devnull downheap(int i, DBlock *b)
577 a0d146ed 2005-07-12 devnull {
578 a0d146ed 2005-07-12 devnull 	DBlock *bb;
579 a0d146ed 2005-07-12 devnull 	u32int now;
580 a0d146ed 2005-07-12 devnull 	int k;
581 a0d146ed 2005-07-12 devnull 
582 a0d146ed 2005-07-12 devnull 	now = dcache.now;
583 a0d146ed 2005-07-12 devnull 	for(; ; i = k){
584 a0d146ed 2005-07-12 devnull 		k = (i << 1) + 1;
585 a0d146ed 2005-07-12 devnull 		if(k >= dcache.nheap)
586 a0d146ed 2005-07-12 devnull 			break;
587 a0d146ed 2005-07-12 devnull 		if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
588 a0d146ed 2005-07-12 devnull 			k++;
589 a0d146ed 2005-07-12 devnull 		bb = dcache.heap[k];
590 a0d146ed 2005-07-12 devnull 		if(b->used2 - now <= bb->used2 - now)
591 a0d146ed 2005-07-12 devnull 			break;
592 a0d146ed 2005-07-12 devnull 		dcache.heap[i] = bb;
593 a0d146ed 2005-07-12 devnull 		bb->heap = i;
594 a0d146ed 2005-07-12 devnull 	}
595 a0d146ed 2005-07-12 devnull 
596 a0d146ed 2005-07-12 devnull 	dcache.heap[i] = b;
597 a0d146ed 2005-07-12 devnull 	b->heap = i;
598 a0d146ed 2005-07-12 devnull 	return i;
599 a0d146ed 2005-07-12 devnull }
600 a0d146ed 2005-07-12 devnull 
601 a0d146ed 2005-07-12 devnull static void
602 a0d146ed 2005-07-12 devnull findblock(DBlock *bb)
603 a0d146ed 2005-07-12 devnull {
604 a0d146ed 2005-07-12 devnull 	DBlock *b, *last;
605 a0d146ed 2005-07-12 devnull 	int h;
606 a0d146ed 2005-07-12 devnull 
607 a0d146ed 2005-07-12 devnull 	last = nil;
608 a0d146ed 2005-07-12 devnull 	h = pbhash(bb->addr);
609 a0d146ed 2005-07-12 devnull 	for(b = dcache.heads[h]; b != nil; b = b->next){
610 a0d146ed 2005-07-12 devnull 		if(last != b->prev)
611 a0d146ed 2005-07-12 devnull 			sysfatal("bad prev link");
612 a0d146ed 2005-07-12 devnull 		if(b == bb)
613 a0d146ed 2005-07-12 devnull 			return;
614 a0d146ed 2005-07-12 devnull 		last = b;
615 a0d146ed 2005-07-12 devnull 	}
616 a0d146ed 2005-07-12 devnull 	sysfatal("block missing from hash table");
617 a0d146ed 2005-07-12 devnull }
618 a0d146ed 2005-07-12 devnull 
619 a0d146ed 2005-07-12 devnull void
620 a0d146ed 2005-07-12 devnull checkdcache(void)
621 a0d146ed 2005-07-12 devnull {
622 a0d146ed 2005-07-12 devnull 	DBlock *b;
623 a0d146ed 2005-07-12 devnull 	u32int size, now;
624 a0d146ed 2005-07-12 devnull 	int i, k, refed, nfree;
625 a0d146ed 2005-07-12 devnull 
626 a0d146ed 2005-07-12 devnull 	qlock(&dcache.lock);
627 a0d146ed 2005-07-12 devnull 	size = dcache.size;
628 a0d146ed 2005-07-12 devnull 	now = dcache.now;
629 a0d146ed 2005-07-12 devnull 	for(i = 0; i < dcache.nheap; i++){
630 a0d146ed 2005-07-12 devnull 		if(dcache.heap[i]->heap != i)
631 a0d146ed 2005-07-12 devnull 			sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
632 a0d146ed 2005-07-12 devnull 		if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
633 a0d146ed 2005-07-12 devnull 			sysfatal("dc: bad heap ordering");
634 a0d146ed 2005-07-12 devnull 		k = (i << 1) + 1;
635 a0d146ed 2005-07-12 devnull 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
636 a0d146ed 2005-07-12 devnull 			sysfatal("dc: bad heap ordering");
637 a0d146ed 2005-07-12 devnull 		k++;
638 a0d146ed 2005-07-12 devnull 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
639 a0d146ed 2005-07-12 devnull 			sysfatal("dc: bad heap ordering");
640 a0d146ed 2005-07-12 devnull 	}
641 a0d146ed 2005-07-12 devnull 
642 a0d146ed 2005-07-12 devnull 	refed = 0;
643 a0d146ed 2005-07-12 devnull 	for(i = 0; i < dcache.nblocks; i++){
644 a0d146ed 2005-07-12 devnull 		b = &dcache.blocks[i];
645 a0d146ed 2005-07-12 devnull 		if(b->data != &dcache.mem[i * size])
646 a0d146ed 2005-07-12 devnull 			sysfatal("dc: mis-blocked at %d", i);
647 a0d146ed 2005-07-12 devnull 		if(b->ref && b->heap == TWID32)
648 a0d146ed 2005-07-12 devnull 			refed++;
649 a0d146ed 2005-07-12 devnull 		if(b->addr)
650 a0d146ed 2005-07-12 devnull 			findblock(b);
651 a0d146ed 2005-07-12 devnull 		if(b->heap != TWID32
652 a0d146ed 2005-07-12 devnull 		&& dcache.heap[b->heap] != b)
653 a0d146ed 2005-07-12 devnull 			sysfatal("dc: spurious heap value");
654 a0d146ed 2005-07-12 devnull 	}
655 a0d146ed 2005-07-12 devnull 
656 a0d146ed 2005-07-12 devnull 	nfree = 0;
657 a0d146ed 2005-07-12 devnull 	for(b = dcache.free; b != nil; b = b->next){
658 a0d146ed 2005-07-12 devnull 		if(b->addr != 0 || b->heap != TWID32)
659 a0d146ed 2005-07-12 devnull 			sysfatal("dc: bad free list");
660 a0d146ed 2005-07-12 devnull 		nfree++;
661 a0d146ed 2005-07-12 devnull 	}
662 a0d146ed 2005-07-12 devnull 
663 a0d146ed 2005-07-12 devnull 	if(dcache.nheap + nfree + refed != dcache.nblocks)
664 a0d146ed 2005-07-12 devnull 		sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
665 a0d146ed 2005-07-12 devnull 	qunlock(&dcache.lock);
666 a0d146ed 2005-07-12 devnull }
667 a0d146ed 2005-07-12 devnull 
668 a0d146ed 2005-07-12 devnull void
669 a0d146ed 2005-07-12 devnull flushdcache(void)
670 a0d146ed 2005-07-12 devnull {
671 a0d146ed 2005-07-12 devnull 	trace(TraceProc, "flushdcache enter");
672 a0d146ed 2005-07-12 devnull 	kickround(&dcache.round, 1);
673 a0d146ed 2005-07-12 devnull 	trace(TraceProc, "flushdcache exit");
674 a0d146ed 2005-07-12 devnull }
675 a0d146ed 2005-07-12 devnull 
676 a0d146ed 2005-07-12 devnull void
677 a0d146ed 2005-07-12 devnull kickdcache(void)
678 a0d146ed 2005-07-12 devnull {
679 a0d146ed 2005-07-12 devnull 	kickround(&dcache.round, 0);
680 a0d146ed 2005-07-12 devnull }
681 a0d146ed 2005-07-12 devnull 
682 a0d146ed 2005-07-12 devnull static int
683 a0d146ed 2005-07-12 devnull parallelwrites(DBlock **b, DBlock **eb, int dirty)
684 a0d146ed 2005-07-12 devnull {
685 a0d146ed 2005-07-12 devnull 	DBlock **p, **q;
686 a0d146ed 2005-07-12 devnull 	for(p=b; p<eb && (*p)->dirty == dirty; p++){
687 a0d146ed 2005-07-12 devnull 		assert(b<=p && p<eb);
688 a0d146ed 2005-07-12 devnull 		sendp((*p)->part->writechan, *p);
689 a0d146ed 2005-07-12 devnull 	}
690 a0d146ed 2005-07-12 devnull 	q = p;
691 a0d146ed 2005-07-12 devnull 	for(p=b; p<q; p++){
692 a0d146ed 2005-07-12 devnull 		assert(b<=p && p<eb);
693 a0d146ed 2005-07-12 devnull 		recvp((*p)->writedonechan);
694 a0d146ed 2005-07-12 devnull 	}
695 a0d146ed 2005-07-12 devnull 
696 a0d146ed 2005-07-12 devnull 	return p-b;
697 a0d146ed 2005-07-12 devnull }
698 a0d146ed 2005-07-12 devnull 
699 a0d146ed 2005-07-12 devnull /*
700 a0d146ed 2005-07-12 devnull  * Sort first by dirty flag, then by partition, then by address in partition.
701 a0d146ed 2005-07-12 devnull  */
702 a0d146ed 2005-07-12 devnull static int
703 a0d146ed 2005-07-12 devnull writeblockcmp(const void *va, const void *vb)
704 a0d146ed 2005-07-12 devnull {
705 a0d146ed 2005-07-12 devnull 	DBlock *a, *b;
706 a0d146ed 2005-07-12 devnull 
707 a0d146ed 2005-07-12 devnull 	a = *(DBlock**)va;
708 a0d146ed 2005-07-12 devnull 	b = *(DBlock**)vb;
709 a0d146ed 2005-07-12 devnull 
710 a0d146ed 2005-07-12 devnull 	if(a->dirty != b->dirty)
711 a0d146ed 2005-07-12 devnull 		return a->dirty - b->dirty;
712 a0d146ed 2005-07-12 devnull 	if(a->part != b->part){
713 a0d146ed 2005-07-12 devnull 		if(a->part < b->part)
714 a0d146ed 2005-07-12 devnull 			return -1;
715 a0d146ed 2005-07-12 devnull 		if(a->part > b->part)
716 a0d146ed 2005-07-12 devnull 			return 1;
717 a0d146ed 2005-07-12 devnull 	}
718 a0d146ed 2005-07-12 devnull 	if(a->addr < b->addr)
719 a0d146ed 2005-07-12 devnull 		return -1;
720 a0d146ed 2005-07-12 devnull 	return 1;
721 a0d146ed 2005-07-12 devnull }
722 a0d146ed 2005-07-12 devnull 
723 a0d146ed 2005-07-12 devnull static void
724 a0d146ed 2005-07-12 devnull flushproc(void *v)
725 a0d146ed 2005-07-12 devnull {
726 a0d146ed 2005-07-12 devnull 	int i, j, n;
727 a0d146ed 2005-07-12 devnull 	ulong t0;
728 a0d146ed 2005-07-12 devnull 	DBlock *b, **write;
729 a0d146ed 2005-07-12 devnull 	AState as;
730 a0d146ed 2005-07-12 devnull 
731 a0d146ed 2005-07-12 devnull 	USED(v);
732 a0d146ed 2005-07-12 devnull 	threadsetname("flushproc");
733 a0d146ed 2005-07-12 devnull 	for(;;){
734 a0d146ed 2005-07-12 devnull 		waitforkick(&dcache.round);
735 a0d146ed 2005-07-12 devnull 
736 a0d146ed 2005-07-12 devnull 		trace(TraceWork, "start");
737 a0d146ed 2005-07-12 devnull 		qlock(&dcache.lock);
738 a0d146ed 2005-07-12 devnull 		as = dcache.state;
739 a0d146ed 2005-07-12 devnull 		qunlock(&dcache.lock);
740 a0d146ed 2005-07-12 devnull 
741 a0d146ed 2005-07-12 devnull 		t0 = nsec()/1000;
742 a0d146ed 2005-07-12 devnull 
743 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "build t=%lud", (ulong)(nsec()/1000)-t0);
744 a0d146ed 2005-07-12 devnull 		write = dcache.write;
745 a0d146ed 2005-07-12 devnull 		n = 0;
746 a0d146ed 2005-07-12 devnull 		for(i=0; i<dcache.nblocks; i++){
747 a0d146ed 2005-07-12 devnull 			b = &dcache.blocks[i];
748 a0d146ed 2005-07-12 devnull 			if(b->dirty)
749 a0d146ed 2005-07-12 devnull 				write[n++] = b;
750 a0d146ed 2005-07-12 devnull 		}
751 a0d146ed 2005-07-12 devnull 
752 a0d146ed 2005-07-12 devnull 		qsort(write, n, sizeof(write[0]), writeblockcmp);
753 a0d146ed 2005-07-12 devnull 
754 a0d146ed 2005-07-12 devnull 		/* Write each stage of blocks out. */
755 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "writeblocks t=%lud", (ulong)(nsec()/1000)-t0);
756 a0d146ed 2005-07-12 devnull 		i = 0;
757 a0d146ed 2005-07-12 devnull 		for(j=1; j<DirtyMax; j++){
758 a0d146ed 2005-07-12 devnull 			trace(TraceProc, "writeblocks.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
759 a0d146ed 2005-07-12 devnull 			i += parallelwrites(write+i, write+n, j);
760 a0d146ed 2005-07-12 devnull 		}
761 a0d146ed 2005-07-12 devnull 		if(i != n){
762 a0d146ed 2005-07-12 devnull 			fprint(2, "in flushproc i=%d n=%d\n", i, n);
763 a0d146ed 2005-07-12 devnull 			for(i=0; i<n; i++)
764 a0d146ed 2005-07-12 devnull 				fprint(2, "\tblock %d: dirty=%d\n", i, write[i]->dirty);
765 a0d146ed 2005-07-12 devnull 			abort();
766 a0d146ed 2005-07-12 devnull 		}
767 a0d146ed 2005-07-12 devnull 
768 a0d146ed 2005-07-12 devnull /* XXX
769 a0d146ed 2005-07-12 devnull * the locking here is suspect.  what if a block is redirtied
770 a0d146ed 2005-07-12 devnull * after the write happens?  we'll still decrement dcache.ndirty here.
771 a0d146ed 2005-07-12 devnull */
772 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "undirty.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
773 a0d146ed 2005-07-12 devnull 		qlock(&dcache.lock);
774 a0d146ed 2005-07-12 devnull 		dcache.diskstate = as;
775 a0d146ed 2005-07-12 devnull 		for(i=0; i<n; i++){
776 a0d146ed 2005-07-12 devnull 			b = write[i];
777 a0d146ed 2005-07-12 devnull 			--dcache.ndirty;
778 a0d146ed 2005-07-12 devnull 			if(b->ref == 0 && b->heap == TWID32){
779 a0d146ed 2005-07-12 devnull 				upheap(dcache.nheap++, b);
780 a0d146ed 2005-07-12 devnull 				rwakeupall(&dcache.full);
781 a0d146ed 2005-07-12 devnull 			}
782 a0d146ed 2005-07-12 devnull 		}
783 a0d146ed 2005-07-12 devnull 		setstat(StatDcacheDirty, dcache.ndirty);
784 a0d146ed 2005-07-12 devnull 		qunlock(&dcache.lock);
785 a0d146ed 2005-07-12 devnull 		addstat(StatDcacheFlush, 1);
786 a0d146ed 2005-07-12 devnull 		trace(TraceWork, "finish");
787 a0d146ed 2005-07-12 devnull 	}
788 a0d146ed 2005-07-12 devnull }
789 a0d146ed 2005-07-12 devnull 
790 a0d146ed 2005-07-12 devnull static void
791 a0d146ed 2005-07-12 devnull writeproc(void *v)
792 a0d146ed 2005-07-12 devnull {
793 a0d146ed 2005-07-12 devnull 	DBlock *b;
794 a0d146ed 2005-07-12 devnull 	Part *p;
795 a0d146ed 2005-07-12 devnull 
796 a0d146ed 2005-07-12 devnull 	p = v;
797 a0d146ed 2005-07-12 devnull 
798 a0d146ed 2005-07-12 devnull 	threadsetname("writeproc:%s", p->name);
799 a0d146ed 2005-07-12 devnull 	for(;;){
800 a0d146ed 2005-07-12 devnull 		b = recvp(p->writechan);
801 a0d146ed 2005-07-12 devnull 		trace(TraceWork, "start");
802 a0d146ed 2005-07-12 devnull 		assert(b->part == p);
803 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "wlock %s 0x%llux", p->name, b->addr);
804 a0d146ed 2005-07-12 devnull 		wlock(&b->lock);
805 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "writepart %s 0x%llux", p->name, b->addr);
806 a0d146ed 2005-07-12 devnull 		if(writepart(p, b->addr, b->data, b->size) < 0)
807 a0d146ed 2005-07-12 devnull 			fprint(2, "write error: %r\n"); /* XXX details! */
808 a0d146ed 2005-07-12 devnull 		addstat(StatApartWrite, 1);
809 a0d146ed 2005-07-12 devnull 		addstat(StatApartWriteBytes, b->size);
810 a0d146ed 2005-07-12 devnull 		b->dirty = 0;
811 a0d146ed 2005-07-12 devnull 		wunlock(&b->lock);
812 a0d146ed 2005-07-12 devnull 		trace(TraceProc, "finish %s 0x%llux", p->name, b->addr);
813 a0d146ed 2005-07-12 devnull 		trace(TraceWork, "finish");
814 a0d146ed 2005-07-12 devnull 		sendp(b->writedonechan, b);
815 a0d146ed 2005-07-12 devnull 	}
816 a0d146ed 2005-07-12 devnull }