2 24998851 2004-03-11 devnull * The locking here is getting a little out of hand.
5 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
6 7a4ee46d 2003-11-23 devnull #include "dat.h"
7 7a4ee46d 2003-11-23 devnull #include "fns.h"
9 7a4ee46d 2003-11-23 devnull typedef struct DCache DCache;
13 7a4ee46d 2003-11-23 devnull HashLog = 9,
14 7a4ee46d 2003-11-23 devnull HashSize = 1<<HashLog,
15 7a4ee46d 2003-11-23 devnull HashMask = HashSize - 1,
18 7a4ee46d 2003-11-23 devnull struct DCache
20 7a4ee46d 2003-11-23 devnull QLock lock;
21 24998851 2004-03-11 devnull RWLock dirtylock; /* must be held to inspect or set b->dirty */
22 24998851 2004-03-11 devnull u32int flushround;
23 24998851 2004-03-11 devnull Rendez anydirty;
24 7a4ee46d 2003-11-23 devnull Rendez full;
25 24998851 2004-03-11 devnull Rendez flush;
26 24998851 2004-03-11 devnull Rendez flushdone;
27 7a4ee46d 2003-11-23 devnull DBlock *free; /* list of available lumps */
28 7a4ee46d 2003-11-23 devnull u32int now; /* ticks for usage timestamps */
29 7a4ee46d 2003-11-23 devnull int size; /* max. size of any block; allocated to each block */
30 7a4ee46d 2003-11-23 devnull DBlock **heads; /* hash table for finding address */
31 7a4ee46d 2003-11-23 devnull int nheap; /* number of available victims */
32 7a4ee46d 2003-11-23 devnull DBlock **heap; /* heap for locating victims */
33 7a4ee46d 2003-11-23 devnull int nblocks; /* number of blocks allocated */
34 7a4ee46d 2003-11-23 devnull DBlock *blocks; /* array of block descriptors */
35 24998851 2004-03-11 devnull DBlock **write; /* array of block pointers to be written */
36 7a4ee46d 2003-11-23 devnull u8int *mem; /* memory for all block descriptors */
37 24998851 2004-03-11 devnull int ndirty; /* number of dirty blocks */
38 24998851 2004-03-11 devnull int maxdirty; /* max. number of dirty blocks */
41 7a4ee46d 2003-11-23 devnull static DCache dcache;
43 7a4ee46d 2003-11-23 devnull static int downheap(int i, DBlock *b);
44 7a4ee46d 2003-11-23 devnull static int upheap(int i, DBlock *b);
45 7a4ee46d 2003-11-23 devnull static DBlock *bumpdblock(void);
46 7a4ee46d 2003-11-23 devnull static void delheap(DBlock *db);
47 7a4ee46d 2003-11-23 devnull static void fixheap(int i, DBlock *b);
48 24998851 2004-03-11 devnull static void _flushdcache(void);
49 24998851 2004-03-11 devnull static void flushproc(void*);
50 24998851 2004-03-11 devnull static void flushtimerproc(void*);
51 24998851 2004-03-11 devnull static void writeproc(void*);
54 7a4ee46d 2003-11-23 devnull initdcache(u32int mem)
56 7a4ee46d 2003-11-23 devnull DBlock *b, *last;
57 7a4ee46d 2003-11-23 devnull u32int nblocks, blocksize;
60 7a4ee46d 2003-11-23 devnull if(mem < maxblocksize * 2)
61 7a4ee46d 2003-11-23 devnull sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
62 7a4ee46d 2003-11-23 devnull if(maxblocksize == 0)
63 7a4ee46d 2003-11-23 devnull sysfatal("no max. block size given for disk cache");
64 7a4ee46d 2003-11-23 devnull blocksize = maxblocksize;
65 7a4ee46d 2003-11-23 devnull nblocks = mem / blocksize;
66 7a4ee46d 2003-11-23 devnull dcache.full.l = &dcache.lock;
67 24998851 2004-03-11 devnull dcache.flush.l = &dcache.lock;
68 24998851 2004-03-11 devnull dcache.anydirty.l = &dcache.lock;
69 24998851 2004-03-11 devnull dcache.flushdone.l = &dcache.lock;
70 7a4ee46d 2003-11-23 devnull dcache.nblocks = nblocks;
71 24998851 2004-03-11 devnull dcache.maxdirty = (nblocks * 3) / 4;
73 24998851 2004-03-11 devnull fprint(2, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
74 24998851 2004-03-11 devnull nblocks, blocksize, dcache.maxdirty);
75 7a4ee46d 2003-11-23 devnull dcache.size = blocksize;
76 7a4ee46d 2003-11-23 devnull dcache.heads = MKNZ(DBlock*, HashSize);
77 7a4ee46d 2003-11-23 devnull dcache.heap = MKNZ(DBlock*, nblocks);
78 7a4ee46d 2003-11-23 devnull dcache.blocks = MKNZ(DBlock, nblocks);
79 24998851 2004-03-11 devnull dcache.write = MKNZ(DBlock*, nblocks);
80 7a4ee46d 2003-11-23 devnull dcache.mem = MKNZ(u8int, nblocks * blocksize);
82 7a4ee46d 2003-11-23 devnull last = nil;
83 7a4ee46d 2003-11-23 devnull for(i = 0; i < nblocks; i++){
84 7a4ee46d 2003-11-23 devnull b = &dcache.blocks[i];
85 7a4ee46d 2003-11-23 devnull b->data = &dcache.mem[i * blocksize];
86 7a4ee46d 2003-11-23 devnull b->heap = TWID32;
87 24998851 2004-03-11 devnull chaninit(&b->writedonechan, sizeof(void*), 1);
88 7a4ee46d 2003-11-23 devnull b->next = last;
89 7a4ee46d 2003-11-23 devnull last = b;
91 7a4ee46d 2003-11-23 devnull dcache.free = last;
92 7a4ee46d 2003-11-23 devnull dcache.nheap = 0;
94 24998851 2004-03-11 devnull vtproc(flushproc, nil);
95 24998851 2004-03-11 devnull vtproc(flushtimerproc, nil);
98 7a4ee46d 2003-11-23 devnull static u32int
99 7a4ee46d 2003-11-23 devnull pbhash(u64int addr)
101 7a4ee46d 2003-11-23 devnull u32int h;
103 7a4ee46d 2003-11-23 devnull #define hashit(c) ((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
104 7a4ee46d 2003-11-23 devnull h = (addr >> 32) ^ addr;
105 7a4ee46d 2003-11-23 devnull return hashit(h);
109 7a4ee46d 2003-11-23 devnull getdblock(Part *part, u64int addr, int read)
111 7a4ee46d 2003-11-23 devnull DBlock *b;
112 7a4ee46d 2003-11-23 devnull u32int h, size;
114 7a4ee46d 2003-11-23 devnull size = part->blocksize;
115 7a4ee46d 2003-11-23 devnull if(size > dcache.size){
116 7a4ee46d 2003-11-23 devnull seterr(EAdmin, "block size %d too big for cache", size);
117 7a4ee46d 2003-11-23 devnull return nil;
119 7a4ee46d 2003-11-23 devnull h = pbhash(addr);
122 7a4ee46d 2003-11-23 devnull * look for the block in the cache
124 7a4ee46d 2003-11-23 devnull //checkdcache();
125 7a4ee46d 2003-11-23 devnull qlock(&dcache.lock);
127 7a4ee46d 2003-11-23 devnull for(b = dcache.heads[h]; b != nil; b = b->next){
128 7a4ee46d 2003-11-23 devnull if(b->part == part && b->addr == addr){
129 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
130 7a4ee46d 2003-11-23 devnull stats.pchit++;
131 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
132 7a4ee46d 2003-11-23 devnull goto found;
135 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
136 7a4ee46d 2003-11-23 devnull stats.pcmiss++;
137 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
140 7a4ee46d 2003-11-23 devnull * missed: locate the block with the oldest second to last use.
141 7a4ee46d 2003-11-23 devnull * remove it from the heap, and fix up the heap.
143 7a4ee46d 2003-11-23 devnull b = bumpdblock();
144 7a4ee46d 2003-11-23 devnull if(b == nil){
145 7a4ee46d 2003-11-23 devnull logerr(EAdmin, "all disk cache blocks in use");
146 7a4ee46d 2003-11-23 devnull rsleep(&dcache.full);
147 7a4ee46d 2003-11-23 devnull goto again;
151 7a4ee46d 2003-11-23 devnull * the new block has no last use, so assume it happens sometime in the middle
152 7a4ee46d 2003-11-23 devnull ZZZ this is not reasonable
154 7a4ee46d 2003-11-23 devnull b->used = (b->used2 + dcache.now) / 2;
157 7a4ee46d 2003-11-23 devnull * rechain the block on the correct hash chain
159 7a4ee46d 2003-11-23 devnull b->next = dcache.heads[h];
160 7a4ee46d 2003-11-23 devnull dcache.heads[h] = b;
161 7a4ee46d 2003-11-23 devnull if(b->next != nil)
162 7a4ee46d 2003-11-23 devnull b->next->prev = b;
163 7a4ee46d 2003-11-23 devnull b->prev = nil;
165 7a4ee46d 2003-11-23 devnull b->addr = addr;
166 7a4ee46d 2003-11-23 devnull b->part = part;
167 7a4ee46d 2003-11-23 devnull b->size = 0;
170 7a4ee46d 2003-11-23 devnull b->ref++;
171 7a4ee46d 2003-11-23 devnull b->used2 = b->used;
172 7a4ee46d 2003-11-23 devnull b->used = dcache.now++;
173 7a4ee46d 2003-11-23 devnull if(b->heap != TWID32)
174 7a4ee46d 2003-11-23 devnull fixheap(b->heap, b);
176 7a4ee46d 2003-11-23 devnull qunlock(&dcache.lock);
177 7a4ee46d 2003-11-23 devnull //checkdcache();
179 7a4ee46d 2003-11-23 devnull qlock(&b->lock);
180 7a4ee46d 2003-11-23 devnull if(b->size != size){
181 7a4ee46d 2003-11-23 devnull if(b->size < size){
182 7a4ee46d 2003-11-23 devnull if(!read)
183 7a4ee46d 2003-11-23 devnull memset(&b->data[b->size], 0, size - b->size);
185 7a4ee46d 2003-11-23 devnull if(readpart(part, addr + b->size, &b->data[b->size], size - b->size) < 0){
186 7a4ee46d 2003-11-23 devnull putdblock(b);
187 7a4ee46d 2003-11-23 devnull return nil;
189 7a4ee46d 2003-11-23 devnull qlock(&stats.lock);
190 7a4ee46d 2003-11-23 devnull stats.pcreads++;
191 7a4ee46d 2003-11-23 devnull stats.pcbreads += size - b->size;
192 7a4ee46d 2003-11-23 devnull qunlock(&stats.lock);
195 7a4ee46d 2003-11-23 devnull b->size = size;
198 7a4ee46d 2003-11-23 devnull return b;
202 7a4ee46d 2003-11-23 devnull putdblock(DBlock *b)
204 7a4ee46d 2003-11-23 devnull if(b == nil)
207 24998851 2004-03-11 devnull if(b->dirtying){
208 24998851 2004-03-11 devnull b->dirtying = 0;
209 24998851 2004-03-11 devnull runlock(&dcache.dirtylock);
211 7a4ee46d 2003-11-23 devnull qunlock(&b->lock);
213 7a4ee46d 2003-11-23 devnull //checkdcache();
214 7a4ee46d 2003-11-23 devnull qlock(&dcache.lock);
215 24998851 2004-03-11 devnull if(b->dirty)
216 24998851 2004-03-11 devnull delheap(b);
217 24998851 2004-03-11 devnull else if(--b->ref == 0){
218 7a4ee46d 2003-11-23 devnull if(b->heap == TWID32)
219 7a4ee46d 2003-11-23 devnull upheap(dcache.nheap++, b);
220 24998851 2004-03-11 devnull rwakeupall(&dcache.full);
223 7a4ee46d 2003-11-23 devnull qunlock(&dcache.lock);
224 7a4ee46d 2003-11-23 devnull //checkdcache();
228 24998851 2004-03-11 devnull dirtydblock(DBlock *b, int dirty)
230 24998851 2004-03-11 devnull int odirty;
231 24998851 2004-03-11 devnull Part *p;
234 24998851 2004-03-11 devnull assert(b->ref != 0);
237 333c1dcc 2004-03-13 devnull * Because we use an rlock to keep track of how
238 333c1dcc 2004-03-13 devnull * many blocks are being dirtied (and a wlock to
239 333c1dcc 2004-03-13 devnull * stop dirtying), we cannot try to dirty two blocks
240 333c1dcc 2004-03-13 devnull * at the same time in the same thread -- if the
241 333c1dcc 2004-03-13 devnull * wlock happens between them, we get a deadlock.
243 333c1dcc 2004-03-13 devnull * The only place in the code where we need to
244 333c1dcc 2004-03-13 devnull * dirty multiple blocks at once is in splitiblock, when
245 333c1dcc 2004-03-13 devnull * we split an index block. The new block has a dirty
246 333c1dcc 2004-03-13 devnull * flag of DirtyIndexSplit already, because it has to get
247 333c1dcc 2004-03-13 devnull * written to disk before the old block (DirtyIndex).
248 333c1dcc 2004-03-13 devnull * So when we see the DirtyIndexSplit block, we don't
249 333c1dcc 2004-03-13 devnull * acquire the rlock (and we don't set dirtying, so putdblock
250 333c1dcc 2004-03-13 devnull * won't drop the rlock). This kludginess means that
251 333c1dcc 2004-03-13 devnull * the caller will have to be sure to putdblock on the
252 333c1dcc 2004-03-13 devnull * new block before putdblock on the old block.
254 333c1dcc 2004-03-13 devnull if(dirty == DirtyIndexSplit){
255 333c1dcc 2004-03-13 devnull /* caller should have another dirty block */
256 333c1dcc 2004-03-13 devnull assert(!canwlock(&dcache.dirtylock));
257 333c1dcc 2004-03-13 devnull /* this block should be clean */
258 333c1dcc 2004-03-13 devnull assert(b->dirtying == 0);
259 333c1dcc 2004-03-13 devnull assert(b->dirty == 0);
261 333c1dcc 2004-03-13 devnull rlock(&dcache.dirtylock);
262 333c1dcc 2004-03-13 devnull assert(b->dirtying == 0);
263 333c1dcc 2004-03-13 devnull b->dirtying = 1;
266 24998851 2004-03-11 devnull qlock(&stats.lock);
267 24998851 2004-03-11 devnull if(b->dirty)
268 24998851 2004-03-11 devnull stats.absorbedwrites++;
269 24998851 2004-03-11 devnull stats.dirtydblocks++;
270 24998851 2004-03-11 devnull qunlock(&stats.lock);
273 9ffbb5ad 2004-03-12 devnull * In general, shouldn't mark any block as more than one
274 9ffbb5ad 2004-03-12 devnull * type, except that split index blocks are a subcase of index
275 9ffbb5ad 2004-03-12 devnull * blocks. Only clean blocks ever get marked DirtyIndexSplit,
276 9ffbb5ad 2004-03-12 devnull * though, so we don't need the opposite conjunction here.
278 333c1dcc 2004-03-13 devnull odirty = b->dirty;
279 24998851 2004-03-11 devnull if(b->dirty)
280 9ffbb5ad 2004-03-12 devnull assert(b->dirty == dirty
281 9ffbb5ad 2004-03-12 devnull || (b->dirty==DirtyIndexSplit && dirty==DirtyIndex));
283 333c1dcc 2004-03-13 devnull b->dirty = dirty;
285 24998851 2004-03-11 devnull p = b->part;
286 24998851 2004-03-11 devnull if(p->writechan == nil){
287 24998851 2004-03-11 devnull fprint(2, "allocate write proc for part %s\n", p->name);
288 24998851 2004-03-11 devnull /* XXX hope this doesn't fail! */
289 24998851 2004-03-11 devnull p->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
290 24998851 2004-03-11 devnull vtproc(writeproc, p);
292 24998851 2004-03-11 devnull qlock(&dcache.lock);
293 24998851 2004-03-11 devnull if(!odirty){
294 24998851 2004-03-11 devnull dcache.ndirty++;
295 24998851 2004-03-11 devnull rwakeupall(&dcache.anydirty);
297 24998851 2004-03-11 devnull qunlock(&dcache.lock);
301 7a4ee46d 2003-11-23 devnull * remove some block from use and update the free list and counters
303 7a4ee46d 2003-11-23 devnull static DBlock*
304 7a4ee46d 2003-11-23 devnull bumpdblock(void)
306 24998851 2004-03-11 devnull int flushed;
307 7a4ee46d 2003-11-23 devnull DBlock *b;
308 7a4ee46d 2003-11-23 devnull ulong h;
310 7a4ee46d 2003-11-23 devnull b = dcache.free;
311 7a4ee46d 2003-11-23 devnull if(b != nil){
312 7a4ee46d 2003-11-23 devnull dcache.free = b->next;
313 7a4ee46d 2003-11-23 devnull return b;
316 24998851 2004-03-11 devnull if(dcache.ndirty >= dcache.maxdirty)
317 24998851 2004-03-11 devnull _flushdcache();
320 7a4ee46d 2003-11-23 devnull * remove blocks until we find one that is unused
321 7a4ee46d 2003-11-23 devnull * referenced blocks are left in the heap even though
322 7a4ee46d 2003-11-23 devnull * they can't be scavenged; this is simple a speed optimization
324 24998851 2004-03-11 devnull flushed = 0;
325 7a4ee46d 2003-11-23 devnull for(;;){
326 24998851 2004-03-11 devnull if(dcache.nheap == 0){
327 24998851 2004-03-11 devnull _flushdcache();
328 7a4ee46d 2003-11-23 devnull return nil;
330 7a4ee46d 2003-11-23 devnull b = dcache.heap[0];
331 7a4ee46d 2003-11-23 devnull delheap(b);
332 7a4ee46d 2003-11-23 devnull if(!b->ref)
336 333c1dcc 2004-03-13 devnull fprint(2, "bump %s at %llud\n", b->part->name, b->addr);
339 7a4ee46d 2003-11-23 devnull * unchain the block
341 7a4ee46d 2003-11-23 devnull if(b->prev == nil){
342 7a4ee46d 2003-11-23 devnull h = pbhash(b->addr);
343 7a4ee46d 2003-11-23 devnull if(dcache.heads[h] != b)
344 7a4ee46d 2003-11-23 devnull sysfatal("bad hash chains in disk cache");
345 7a4ee46d 2003-11-23 devnull dcache.heads[h] = b->next;
347 7a4ee46d 2003-11-23 devnull b->prev->next = b->next;
348 7a4ee46d 2003-11-23 devnull if(b->next != nil)
349 7a4ee46d 2003-11-23 devnull b->next->prev = b->prev;
351 7a4ee46d 2003-11-23 devnull return b;
355 7a4ee46d 2003-11-23 devnull * delete an arbitrary block from the heap
357 7a4ee46d 2003-11-23 devnull static void
358 7a4ee46d 2003-11-23 devnull delheap(DBlock *db)
360 24998851 2004-03-11 devnull if(db->heap == TWID32)
362 7a4ee46d 2003-11-23 devnull fixheap(db->heap, dcache.heap[--dcache.nheap]);
363 7a4ee46d 2003-11-23 devnull db->heap = TWID32;
367 7a4ee46d 2003-11-23 devnull * push an element up or down to it's correct new location
369 7a4ee46d 2003-11-23 devnull static void
370 7a4ee46d 2003-11-23 devnull fixheap(int i, DBlock *b)
372 7a4ee46d 2003-11-23 devnull if(upheap(i, b) == i)
373 7a4ee46d 2003-11-23 devnull downheap(i, b);
376 7a4ee46d 2003-11-23 devnull static int
377 7a4ee46d 2003-11-23 devnull upheap(int i, DBlock *b)
379 7a4ee46d 2003-11-23 devnull DBlock *bb;
380 7a4ee46d 2003-11-23 devnull u32int now;
383 7a4ee46d 2003-11-23 devnull now = dcache.now;
384 7a4ee46d 2003-11-23 devnull for(; i != 0; i = p){
385 7a4ee46d 2003-11-23 devnull p = (i - 1) >> 1;
386 7a4ee46d 2003-11-23 devnull bb = dcache.heap[p];
387 7a4ee46d 2003-11-23 devnull if(b->used2 - now >= bb->used2 - now)
389 7a4ee46d 2003-11-23 devnull dcache.heap[i] = bb;
390 7a4ee46d 2003-11-23 devnull bb->heap = i;
393 7a4ee46d 2003-11-23 devnull dcache.heap[i] = b;
394 7a4ee46d 2003-11-23 devnull b->heap = i;
395 7a4ee46d 2003-11-23 devnull return i;
398 7a4ee46d 2003-11-23 devnull static int
399 7a4ee46d 2003-11-23 devnull downheap(int i, DBlock *b)
401 7a4ee46d 2003-11-23 devnull DBlock *bb;
402 7a4ee46d 2003-11-23 devnull u32int now;
405 7a4ee46d 2003-11-23 devnull now = dcache.now;
406 7a4ee46d 2003-11-23 devnull for(; ; i = k){
407 7a4ee46d 2003-11-23 devnull k = (i << 1) + 1;
408 7a4ee46d 2003-11-23 devnull if(k >= dcache.nheap)
410 7a4ee46d 2003-11-23 devnull if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
412 7a4ee46d 2003-11-23 devnull bb = dcache.heap[k];
413 7a4ee46d 2003-11-23 devnull if(b->used2 - now <= bb->used2 - now)
415 7a4ee46d 2003-11-23 devnull dcache.heap[i] = bb;
416 7a4ee46d 2003-11-23 devnull bb->heap = i;
419 7a4ee46d 2003-11-23 devnull dcache.heap[i] = b;
420 7a4ee46d 2003-11-23 devnull b->heap = i;
421 7a4ee46d 2003-11-23 devnull return i;
424 7a4ee46d 2003-11-23 devnull static void
425 7a4ee46d 2003-11-23 devnull findblock(DBlock *bb)
427 7a4ee46d 2003-11-23 devnull DBlock *b, *last;
430 7a4ee46d 2003-11-23 devnull last = nil;
431 7a4ee46d 2003-11-23 devnull h = pbhash(bb->addr);
432 7a4ee46d 2003-11-23 devnull for(b = dcache.heads[h]; b != nil; b = b->next){
433 7a4ee46d 2003-11-23 devnull if(last != b->prev)
434 7a4ee46d 2003-11-23 devnull sysfatal("bad prev link");
435 7a4ee46d 2003-11-23 devnull if(b == bb)
437 7a4ee46d 2003-11-23 devnull last = b;
439 7a4ee46d 2003-11-23 devnull sysfatal("block missing from hash table");
443 7a4ee46d 2003-11-23 devnull checkdcache(void)
445 7a4ee46d 2003-11-23 devnull DBlock *b;
446 7a4ee46d 2003-11-23 devnull u32int size, now;
447 7a4ee46d 2003-11-23 devnull int i, k, refed, nfree;
449 7a4ee46d 2003-11-23 devnull qlock(&dcache.lock);
450 7a4ee46d 2003-11-23 devnull size = dcache.size;
451 7a4ee46d 2003-11-23 devnull now = dcache.now;
452 7a4ee46d 2003-11-23 devnull for(i = 0; i < dcache.nheap; i++){
453 7a4ee46d 2003-11-23 devnull if(dcache.heap[i]->heap != i)
454 7a4ee46d 2003-11-23 devnull sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
455 7a4ee46d 2003-11-23 devnull if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
456 7a4ee46d 2003-11-23 devnull sysfatal("dc: bad heap ordering");
457 7a4ee46d 2003-11-23 devnull k = (i << 1) + 1;
458 7a4ee46d 2003-11-23 devnull if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
459 7a4ee46d 2003-11-23 devnull sysfatal("dc: bad heap ordering");
461 7a4ee46d 2003-11-23 devnull if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
462 7a4ee46d 2003-11-23 devnull sysfatal("dc: bad heap ordering");
465 7a4ee46d 2003-11-23 devnull refed = 0;
466 7a4ee46d 2003-11-23 devnull for(i = 0; i < dcache.nblocks; i++){
467 7a4ee46d 2003-11-23 devnull b = &dcache.blocks[i];
468 7a4ee46d 2003-11-23 devnull if(b->data != &dcache.mem[i * size])
469 7a4ee46d 2003-11-23 devnull sysfatal("dc: mis-blocked at %d", i);
470 7a4ee46d 2003-11-23 devnull if(b->ref && b->heap == TWID32)
471 7a4ee46d 2003-11-23 devnull refed++;
472 7a4ee46d 2003-11-23 devnull if(b->addr)
473 7a4ee46d 2003-11-23 devnull findblock(b);
474 7a4ee46d 2003-11-23 devnull if(b->heap != TWID32
475 7a4ee46d 2003-11-23 devnull && dcache.heap[b->heap] != b)
476 7a4ee46d 2003-11-23 devnull sysfatal("dc: spurious heap value");
479 7a4ee46d 2003-11-23 devnull nfree = 0;
480 7a4ee46d 2003-11-23 devnull for(b = dcache.free; b != nil; b = b->next){
481 7a4ee46d 2003-11-23 devnull if(b->addr != 0 || b->heap != TWID32)
482 7a4ee46d 2003-11-23 devnull sysfatal("dc: bad free list");
483 7a4ee46d 2003-11-23 devnull nfree++;
486 7a4ee46d 2003-11-23 devnull if(dcache.nheap + nfree + refed != dcache.nblocks)
487 7a4ee46d 2003-11-23 devnull sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
488 7a4ee46d 2003-11-23 devnull qunlock(&dcache.lock);
492 24998851 2004-03-11 devnull flushdcache(void)
494 24998851 2004-03-11 devnull u32int flushround;
496 24998851 2004-03-11 devnull qlock(&dcache.lock);
497 24998851 2004-03-11 devnull flushround = dcache.flushround;
498 24998851 2004-03-11 devnull rwakeupall(&dcache.flush);
499 24998851 2004-03-11 devnull while(flushround == dcache.flushround)
500 24998851 2004-03-11 devnull rsleep(&dcache.flushdone);
501 24998851 2004-03-11 devnull qunlock(&dcache.lock);
504 24998851 2004-03-11 devnull static void
505 24998851 2004-03-11 devnull _flushdcache(void)
507 24998851 2004-03-11 devnull rwakeupall(&dcache.flush);
510 24998851 2004-03-11 devnull static int
511 24998851 2004-03-11 devnull parallelwrites(DBlock **b, DBlock **eb, int dirty)
513 24998851 2004-03-11 devnull DBlock **p;
515 24998851 2004-03-11 devnull for(p=b; p<eb && (*p)->dirty == dirty; p++)
516 24998851 2004-03-11 devnull sendp((*p)->part->writechan, *p);
517 24998851 2004-03-11 devnull for(p=b; p<eb && (*p)->dirty == dirty; p++)
518 24998851 2004-03-11 devnull recvp(&(*p)->writedonechan);
520 24998851 2004-03-11 devnull return p-b;
524 24998851 2004-03-11 devnull * Sort first by dirty flag, then by partition, then by address in partition.
526 24998851 2004-03-11 devnull static int
527 24998851 2004-03-11 devnull writeblockcmp(const void *va, const void *vb)
529 24998851 2004-03-11 devnull DBlock *a, *b;
531 24998851 2004-03-11 devnull a = *(DBlock**)va;
532 24998851 2004-03-11 devnull b = *(DBlock**)vb;
534 24998851 2004-03-11 devnull if(a->dirty != b->dirty)
535 24998851 2004-03-11 devnull return a->dirty - b->dirty;
536 24998851 2004-03-11 devnull if(a->part != b->part){
537 24998851 2004-03-11 devnull if(a->part < b->part)
538 24998851 2004-03-11 devnull return -1;
539 24998851 2004-03-11 devnull if(a->part > b->part)
540 24998851 2004-03-11 devnull return 1;
542 24998851 2004-03-11 devnull if(a->addr < b->addr)
543 24998851 2004-03-11 devnull return -1;
544 24998851 2004-03-11 devnull return 1;
547 24998851 2004-03-11 devnull static void
548 24998851 2004-03-11 devnull flushtimerproc(void *v)
550 24998851 2004-03-11 devnull u32int round;
552 24998851 2004-03-11 devnull for(;;){
553 24998851 2004-03-11 devnull qlock(&dcache.lock);
554 24998851 2004-03-11 devnull while(dcache.ndirty == 0)
555 24998851 2004-03-11 devnull rsleep(&dcache.anydirty);
556 24998851 2004-03-11 devnull round = dcache.flushround;
557 24998851 2004-03-11 devnull qunlock(&dcache.lock);
559 24998851 2004-03-11 devnull sleep(60*1000);
561 24998851 2004-03-11 devnull qlock(&dcache.lock);
562 24998851 2004-03-11 devnull if(round == dcache.flushround){
563 24998851 2004-03-11 devnull rwakeupall(&dcache.flush);
564 24998851 2004-03-11 devnull while(round == dcache.flushround)
565 24998851 2004-03-11 devnull rsleep(&dcache.flushdone);
567 24998851 2004-03-11 devnull qunlock(&dcache.lock);
571 24998851 2004-03-11 devnull static void
572 24998851 2004-03-11 devnull flushproc(void *v)
574 9ffbb5ad 2004-03-12 devnull int i, j, n;
575 333c1dcc 2004-03-13 devnull ulong t0;
576 24998851 2004-03-11 devnull DBlock *b, **write;
578 24998851 2004-03-11 devnull USED(v);
579 24998851 2004-03-11 devnull for(;;){
580 24998851 2004-03-11 devnull qlock(&dcache.lock);
581 24998851 2004-03-11 devnull dcache.flushround++;
582 24998851 2004-03-11 devnull rwakeupall(&dcache.flushdone);
583 24998851 2004-03-11 devnull rsleep(&dcache.flush);
584 24998851 2004-03-11 devnull qunlock(&dcache.lock);
586 333c1dcc 2004-03-13 devnull fprint(2, "flushing dcache: t=0 ms\n");
587 333c1dcc 2004-03-13 devnull t0 = nsec()/1000;
590 24998851 2004-03-11 devnull * Because we don't record any dependencies at all, we must write out
591 24998851 2004-03-11 devnull * all blocks currently dirty. Thus we must lock all the blocks that
592 24998851 2004-03-11 devnull * are currently dirty.
594 24998851 2004-03-11 devnull * We grab dirtylock to stop the dirtying of new blocks.
595 24998851 2004-03-11 devnull * Then we wait until all the current blocks finish being dirtied.
596 24998851 2004-03-11 devnull * Now all the dirty blocks in the system are immutable (clean blocks
597 24998851 2004-03-11 devnull * might still get recycled), so we can plan our disk writes.
599 24998851 2004-03-11 devnull * In a better scheme, dirtiers might lock the block for writing in getdblock,
600 24998851 2004-03-11 devnull * so that flushproc could lock all the blocks here and then unlock them as it
601 24998851 2004-03-11 devnull * finishes with them.
604 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: wlock at t=%lud\n", (ulong)(nsec()/1000) - t0);
605 24998851 2004-03-11 devnull wlock(&dcache.dirtylock);
607 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: build list at t=%lud\n", (ulong)(nsec()/1000) - t0);
608 24998851 2004-03-11 devnull write = dcache.write;
610 24998851 2004-03-11 devnull for(i=0; i<dcache.nblocks; i++){
611 24998851 2004-03-11 devnull b = &dcache.blocks[i];
612 24998851 2004-03-11 devnull if(b->dirty)
613 24998851 2004-03-11 devnull write[n++] = b;
616 24998851 2004-03-11 devnull qsort(write, n, sizeof(write[0]), writeblockcmp);
618 9ffbb5ad 2004-03-12 devnull /* Write each stage of blocks out. */
619 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: write blocks at t=%lud\n", (ulong)(nsec()/1000) - t0);
621 333c1dcc 2004-03-13 devnull for(j=1; j<DirtyMax; j++){
622 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: flush dirty %d at t=%lud\n", j, (ulong)(nsec()/1000) - t0);
623 9ffbb5ad 2004-03-12 devnull i += parallelwrites(write+i, write+n, j);
625 24998851 2004-03-11 devnull assert(i == n);
627 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: update dirty bits at t=%lud\n", (ulong)(nsec()/1000) - t0);
628 24998851 2004-03-11 devnull qlock(&dcache.lock);
629 24998851 2004-03-11 devnull for(i=0; i<n; i++){
630 24998851 2004-03-11 devnull b = write[i];
631 24998851 2004-03-11 devnull b->dirty = 0;
632 24998851 2004-03-11 devnull --dcache.ndirty;
633 24998851 2004-03-11 devnull if(b->ref == 0 && b->heap == TWID32){
634 24998851 2004-03-11 devnull upheap(dcache.nheap++, b);
635 24998851 2004-03-11 devnull rwakeupall(&dcache.full);
638 24998851 2004-03-11 devnull qunlock(&dcache.lock);
639 24998851 2004-03-11 devnull wunlock(&dcache.dirtylock);
641 333c1dcc 2004-03-13 devnull fprint(2, "flushproc: done at t=%lud\n", (ulong)(nsec()/1000) - t0);
643 24998851 2004-03-11 devnull qlock(&stats.lock);
644 24998851 2004-03-11 devnull stats.dcacheflushes++;
645 24998851 2004-03-11 devnull stats.dcacheflushwrites += n;
646 24998851 2004-03-11 devnull qunlock(&stats.lock);
650 24998851 2004-03-11 devnull static void
651 24998851 2004-03-11 devnull writeproc(void *v)
653 24998851 2004-03-11 devnull DBlock *b;
654 24998851 2004-03-11 devnull Part *p;
658 24998851 2004-03-11 devnull for(;;){
659 24998851 2004-03-11 devnull b = recvp(p->writechan);
660 24998851 2004-03-11 devnull if(writepart(p, b->addr, b->data, b->size) < 0)
661 24998851 2004-03-11 devnull fprint(2, "write error: %r\n"); /* XXX details! */
662 24998851 2004-03-11 devnull sendp(&b->writedonechan, b);