2 a0d146ed 2005-07-12 devnull * Disk cache.
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 fa325e9b 2020-01-10 cross * by using dirtydblock() before putdblock().
11 fa325e9b 2020-01-10 cross * 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.
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.
20 fa325e9b 2020-01-10 cross * 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.
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"
31 a0d146ed 2005-07-12 devnull typedef struct DCache DCache;
35 a0d146ed 2005-07-12 devnull HashLog = 9,
36 a0d146ed 2005-07-12 devnull HashSize = 1<<HashLog,
37 28b49df3 2006-07-18 devnull HashMask = HashSize - 1,
40 a0d146ed 2005-07-12 devnull struct DCache
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 */
60 a0d146ed 2005-07-12 devnull typedef struct Ra Ra;
61 a0d146ed 2005-07-12 devnull struct Ra
63 a0d146ed 2005-07-12 devnull Part *part;
64 a0d146ed 2005-07-12 devnull u64int addr;
67 a0d146ed 2005-07-12 devnull static DCache dcache;
69 a0d146ed 2005-07-12 devnull static int downheap(int i, DBlock *b);
70 a0d146ed 2005-07-12 devnull static int upheap(int i, DBlock *b);
71 a0d146ed 2005-07-12 devnull static DBlock *bumpdblock(void);
72 a0d146ed 2005-07-12 devnull static void delheap(DBlock *db);
73 a0d146ed 2005-07-12 devnull static void fixheap(int i, DBlock *b);
74 a0d146ed 2005-07-12 devnull static void flushproc(void*);
75 a0d146ed 2005-07-12 devnull static void writeproc(void*);
78 a0d146ed 2005-07-12 devnull initdcache(u32int mem)
80 a0d146ed 2005-07-12 devnull DBlock *b, *last;
81 a0d146ed 2005-07-12 devnull u32int nblocks, blocksize;
83 a0d146ed 2005-07-12 devnull u8int *p;
85 a0d146ed 2005-07-12 devnull if(mem < maxblocksize * 2)
86 a0d146ed 2005-07-12 devnull sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
87 a0d146ed 2005-07-12 devnull if(maxblocksize == 0)
88 a0d146ed 2005-07-12 devnull sysfatal("no max. block size given for disk cache");
89 a0d146ed 2005-07-12 devnull blocksize = maxblocksize;
90 a0d146ed 2005-07-12 devnull nblocks = mem / blocksize;
91 a0d146ed 2005-07-12 devnull dcache.full.l = &dcache.lock;
92 a0d146ed 2005-07-12 devnull dcache.nblocks = nblocks;
93 a0d146ed 2005-07-12 devnull dcache.maxdirty = (nblocks * 2) / 3;
94 a0d146ed 2005-07-12 devnull trace(TraceProc, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
95 a0d146ed 2005-07-12 devnull nblocks, blocksize, dcache.maxdirty);
96 a0d146ed 2005-07-12 devnull dcache.size = blocksize;
97 a0d146ed 2005-07-12 devnull dcache.heads = MKNZ(DBlock*, HashSize);
98 a0d146ed 2005-07-12 devnull dcache.heap = MKNZ(DBlock*, nblocks);
99 a0d146ed 2005-07-12 devnull dcache.blocks = MKNZ(DBlock, nblocks);
100 a0d146ed 2005-07-12 devnull dcache.write = MKNZ(DBlock*, nblocks);
101 a0d146ed 2005-07-12 devnull dcache.mem = MKNZ(u8int, (nblocks+1+128) * blocksize);
103 a0d146ed 2005-07-12 devnull last = nil;
104 54dd92be 2008-01-30 rsc p = (u8int*)(((uintptr)dcache.mem+blocksize-1)&~(uintptr)(blocksize-1));
105 a0d146ed 2005-07-12 devnull for(i = 0; i < nblocks; i++){
106 a0d146ed 2005-07-12 devnull b = &dcache.blocks[i];
107 a0d146ed 2005-07-12 devnull b->data = &p[i * blocksize];
108 a0d146ed 2005-07-12 devnull b->heap = TWID32;
109 a0d146ed 2005-07-12 devnull b->writedonechan = chancreate(sizeof(void*), 1);
110 a0d146ed 2005-07-12 devnull b->next = last;
111 a0d146ed 2005-07-12 devnull last = b;
114 a0d146ed 2005-07-12 devnull dcache.free = last;
115 a0d146ed 2005-07-12 devnull dcache.nheap = 0;
116 a0d146ed 2005-07-12 devnull setstat(StatDcacheSize, nblocks);
117 a0d146ed 2005-07-12 devnull initround(&dcache.round, "dcache", 120*1000);
119 a0d146ed 2005-07-12 devnull vtproc(flushproc, nil);
120 a0d146ed 2005-07-12 devnull vtproc(delaykickroundproc, &dcache.round);
123 a0d146ed 2005-07-12 devnull static u32int
124 a0d146ed 2005-07-12 devnull pbhash(u64int addr)
126 a0d146ed 2005-07-12 devnull u32int h;
128 a0d146ed 2005-07-12 devnull #define hashit(c) ((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
129 a0d146ed 2005-07-12 devnull h = (addr >> 32) ^ addr;
130 a0d146ed 2005-07-12 devnull return hashit(h);
134 a0d146ed 2005-07-12 devnull getdblock(Part *part, u64int addr, int mode)
136 a0d146ed 2005-07-12 devnull DBlock *b;
138 a0d146ed 2005-07-12 devnull b = _getdblock(part, addr, mode, 1);
139 a0d146ed 2005-07-12 devnull if(mode == OREAD || mode == ORDWR)
140 a0d146ed 2005-07-12 devnull addstat(StatDcacheRead, 1);
141 a0d146ed 2005-07-12 devnull if(mode == OWRITE || mode == ORDWR)
142 a0d146ed 2005-07-12 devnull addstat(StatDcacheWrite, 1);
143 a0d146ed 2005-07-12 devnull return b;
147 a0d146ed 2005-07-12 devnull _getdblock(Part *part, u64int addr, int mode, int load)
149 a0d146ed 2005-07-12 devnull DBlock *b;
150 54dd92be 2008-01-30 rsc u32int h, size, ms;
153 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock enter %s 0x%llux", part->name, addr);
154 a0d146ed 2005-07-12 devnull size = part->blocksize;
155 a0d146ed 2005-07-12 devnull if(size > dcache.size){
156 a0d146ed 2005-07-12 devnull seterr(EAdmin, "block size %d too big for cache with size %d", size, dcache.size);
158 54dd92be 2008-01-30 rsc addstat(StatDcacheLookup, 1);
159 a0d146ed 2005-07-12 devnull return nil;
161 a0d146ed 2005-07-12 devnull h = pbhash(addr);
164 a0d146ed 2005-07-12 devnull * look for the block in the cache
166 a0d146ed 2005-07-12 devnull qlock(&dcache.lock);
168 a0d146ed 2005-07-12 devnull for(b = dcache.heads[h]; b != nil; b = b->next){
169 a0d146ed 2005-07-12 devnull if(b->part == part && b->addr == addr){
171 54dd92be 2008-01-30 rsc addstat2(StatDcacheHit, 1, StatDcacheLookup, 1);
172 a0d146ed 2005-07-12 devnull goto found;
177 a0d146ed 2005-07-12 devnull * missed: locate the block with the oldest second to last use.
178 a0d146ed 2005-07-12 devnull * remove it from the heap, and fix up the heap.
180 a0d146ed 2005-07-12 devnull if(!load){
181 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
182 a0d146ed 2005-07-12 devnull return nil;
186 54dd92be 2008-01-30 rsc * Only start timer here, on cache miss - calling msec() on plain cache hits
187 54dd92be 2008-01-30 rsc * makes cache hits system-call bound.
189 54dd92be 2008-01-30 rsc ms = msec();
190 54dd92be 2008-01-30 rsc addstat2(StatDcacheLookup, 1, StatDcacheMiss, 1);
192 a0d146ed 2005-07-12 devnull b = bumpdblock();
193 a0d146ed 2005-07-12 devnull if(b == nil){
194 a0d146ed 2005-07-12 devnull trace(TraceBlock, "all disk cache blocks in use");
195 a0d146ed 2005-07-12 devnull addstat(StatDcacheStall, 1);
196 a0d146ed 2005-07-12 devnull rsleep(&dcache.full);
197 a0d146ed 2005-07-12 devnull addstat(StatDcacheStall, -1);
198 a0d146ed 2005-07-12 devnull goto again;
201 a0d146ed 2005-07-12 devnull assert(!b->dirty);
204 a0d146ed 2005-07-12 devnull * the new block has no last use, so assume it happens sometime in the middle
205 a0d146ed 2005-07-12 devnull ZZZ this is not reasonable
207 a0d146ed 2005-07-12 devnull b->used = (b->used2 + dcache.now) / 2;
210 a0d146ed 2005-07-12 devnull * rechain the block on the correct hash chain
212 a0d146ed 2005-07-12 devnull b->next = dcache.heads[h];
213 a0d146ed 2005-07-12 devnull dcache.heads[h] = b;
214 a0d146ed 2005-07-12 devnull if(b->next != nil)
215 a0d146ed 2005-07-12 devnull b->next->prev = b;
216 a0d146ed 2005-07-12 devnull b->prev = nil;
218 a0d146ed 2005-07-12 devnull b->addr = addr;
219 a0d146ed 2005-07-12 devnull b->part = part;
220 a0d146ed 2005-07-12 devnull b->size = 0;
223 a0d146ed 2005-07-12 devnull b->ref++;
224 a0d146ed 2005-07-12 devnull b->used2 = b->used;
225 a0d146ed 2005-07-12 devnull b->used = dcache.now++;
226 a0d146ed 2005-07-12 devnull if(b->heap != TWID32)
227 a0d146ed 2005-07-12 devnull fixheap(b->heap, b);
229 12c0e45f 2007-09-25 rsc if((mode == ORDWR || mode == OWRITE) && part->writechan == nil){
230 12c0e45f 2007-09-25 rsc trace(TraceBlock, "getdblock allocwriteproc %s", part->name);
231 12c0e45f 2007-09-25 rsc part->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
232 12c0e45f 2007-09-25 rsc vtproc(writeproc, part);
234 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
236 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock lock");
237 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, 1);
238 a0d146ed 2005-07-12 devnull if(mode == OREAD)
239 a0d146ed 2005-07-12 devnull rlock(&b->lock);
241 a0d146ed 2005-07-12 devnull wlock(&b->lock);
242 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, -1);
243 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock locked");
245 a0d146ed 2005-07-12 devnull if(b->size != size){
246 a0d146ed 2005-07-12 devnull if(mode == OREAD){
247 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, 1);
248 a0d146ed 2005-07-12 devnull runlock(&b->lock);
249 a0d146ed 2005-07-12 devnull wlock(&b->lock);
250 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, -1);
252 a0d146ed 2005-07-12 devnull if(b->size < size){
253 a0d146ed 2005-07-12 devnull if(mode == OWRITE)
254 a0d146ed 2005-07-12 devnull memset(&b->data[b->size], 0, size - b->size);
256 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock readpart %s 0x%llux", part->name, addr);
257 12c0e45f 2007-09-25 rsc diskaccess(0);
258 12c0e45f 2007-09-25 rsc if(readpart(part, addr + b->size, &b->data[b->size], size - b->size) < 0){
259 a0d146ed 2005-07-12 devnull b->mode = ORDWR; /* so putdblock wunlocks */
260 a0d146ed 2005-07-12 devnull putdblock(b);
261 a0d146ed 2005-07-12 devnull return nil;
263 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock readpartdone");
264 a0d146ed 2005-07-12 devnull addstat(StatApartRead, 1);
265 a0d146ed 2005-07-12 devnull addstat(StatApartReadBytes, size-b->size);
268 a0d146ed 2005-07-12 devnull b->size = size;
269 a0d146ed 2005-07-12 devnull if(mode == OREAD){
270 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, 1);
271 a0d146ed 2005-07-12 devnull wunlock(&b->lock);
272 a0d146ed 2005-07-12 devnull rlock(&b->lock);
273 a0d146ed 2005-07-12 devnull addstat(StatDblockStall, -1);
277 a0d146ed 2005-07-12 devnull b->mode = mode;
278 a0d146ed 2005-07-12 devnull trace(TraceBlock, "getdblock exit");
280 54dd92be 2008-01-30 rsc addstat(StatDcacheLookupTime, msec() - ms);
281 a0d146ed 2005-07-12 devnull return b;
285 a0d146ed 2005-07-12 devnull putdblock(DBlock *b)
287 a0d146ed 2005-07-12 devnull if(b == nil)
290 a0d146ed 2005-07-12 devnull trace(TraceBlock, "putdblock %s 0x%llux", b->part->name, b->addr);
292 a0d146ed 2005-07-12 devnull if(b->mode == OREAD)
293 a0d146ed 2005-07-12 devnull runlock(&b->lock);
295 a0d146ed 2005-07-12 devnull wunlock(&b->lock);
297 a0d146ed 2005-07-12 devnull qlock(&dcache.lock);
298 a0d146ed 2005-07-12 devnull if(--b->ref == 0 && !b->dirty){
299 a0d146ed 2005-07-12 devnull if(b->heap == TWID32)
300 a0d146ed 2005-07-12 devnull upheap(dcache.nheap++, b);
301 a0d146ed 2005-07-12 devnull rwakeupall(&dcache.full);
303 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
307 a0d146ed 2005-07-12 devnull dirtydblock(DBlock *b, int dirty)
309 a0d146ed 2005-07-12 devnull int odirty;
311 12c0e45f 2007-09-25 rsc trace(TraceBlock, "dirtydblock enter %s 0x%llux %d from 0x%lux",
312 12c0e45f 2007-09-25 rsc b->part->name, b->addr, dirty, getcallerpc(&b));
313 a0d146ed 2005-07-12 devnull assert(b->ref != 0);
314 a0d146ed 2005-07-12 devnull assert(b->mode==ORDWR || b->mode==OWRITE);
316 a0d146ed 2005-07-12 devnull odirty = b->dirty;
317 a0d146ed 2005-07-12 devnull if(b->dirty)
318 a0d146ed 2005-07-12 devnull assert(b->dirty == dirty);
320 a0d146ed 2005-07-12 devnull b->dirty = dirty;
322 a0d146ed 2005-07-12 devnull qlock(&dcache.lock);
323 a0d146ed 2005-07-12 devnull if(!odirty){
324 a0d146ed 2005-07-12 devnull dcache.ndirty++;
325 a0d146ed 2005-07-12 devnull setstat(StatDcacheDirty, dcache.ndirty);
326 a0d146ed 2005-07-12 devnull if(dcache.ndirty >= dcache.maxdirty)
327 a0d146ed 2005-07-12 devnull kickround(&dcache.round, 0);
329 a0d146ed 2005-07-12 devnull delaykickround(&dcache.round);
331 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
334 28b49df3 2006-07-18 devnull static void
335 28b49df3 2006-07-18 devnull unchain(DBlock *b)
337 28b49df3 2006-07-18 devnull ulong h;
340 28b49df3 2006-07-18 devnull * unchain the block
342 28b49df3 2006-07-18 devnull if(b->prev == nil){
343 28b49df3 2006-07-18 devnull h = pbhash(b->addr);
344 28b49df3 2006-07-18 devnull if(dcache.heads[h] != b)
345 28b49df3 2006-07-18 devnull sysfatal("bad hash chains in disk cache");
346 28b49df3 2006-07-18 devnull dcache.heads[h] = b->next;
348 28b49df3 2006-07-18 devnull b->prev->next = b->next;
349 28b49df3 2006-07-18 devnull if(b->next != nil)
350 28b49df3 2006-07-18 devnull b->next->prev = b->prev;
354 a0d146ed 2005-07-12 devnull * remove some block from use and update the free list and counters
356 a0d146ed 2005-07-12 devnull static DBlock*
357 a0d146ed 2005-07-12 devnull bumpdblock(void)
359 a0d146ed 2005-07-12 devnull DBlock *b;
361 a0d146ed 2005-07-12 devnull trace(TraceBlock, "bumpdblock enter");
362 a0d146ed 2005-07-12 devnull b = dcache.free;
363 a0d146ed 2005-07-12 devnull if(b != nil){
364 a0d146ed 2005-07-12 devnull dcache.free = b->next;
365 a0d146ed 2005-07-12 devnull return b;
368 a0d146ed 2005-07-12 devnull if(dcache.ndirty >= dcache.maxdirty)
369 a0d146ed 2005-07-12 devnull kickdcache();
372 a0d146ed 2005-07-12 devnull * remove blocks until we find one that is unused
373 a0d146ed 2005-07-12 devnull * referenced blocks are left in the heap even though
374 a0d146ed 2005-07-12 devnull * they can't be scavenged; this is simple a speed optimization
376 a0d146ed 2005-07-12 devnull for(;;){
377 a0d146ed 2005-07-12 devnull if(dcache.nheap == 0){
378 a0d146ed 2005-07-12 devnull kickdcache();
379 a0d146ed 2005-07-12 devnull trace(TraceBlock, "bumpdblock gotnothing");
380 a0d146ed 2005-07-12 devnull return nil;
382 a0d146ed 2005-07-12 devnull b = dcache.heap[0];
383 a0d146ed 2005-07-12 devnull delheap(b);
384 a0d146ed 2005-07-12 devnull if(!b->ref && !b->dirty)
388 a0d146ed 2005-07-12 devnull trace(TraceBlock, "bumpdblock bumping %s 0x%llux", b->part->name, b->addr);
390 28b49df3 2006-07-18 devnull unchain(b);
391 a0d146ed 2005-07-12 devnull return b;
395 28b49df3 2006-07-18 devnull emptydcache(void)
397 28b49df3 2006-07-18 devnull DBlock *b;
399 28b49df3 2006-07-18 devnull qlock(&dcache.lock);
400 28b49df3 2006-07-18 devnull while(dcache.nheap > 0){
401 28b49df3 2006-07-18 devnull b = dcache.heap[0];
402 28b49df3 2006-07-18 devnull delheap(b);
403 28b49df3 2006-07-18 devnull if(!b->ref && !b->dirty){
404 28b49df3 2006-07-18 devnull unchain(b);
405 28b49df3 2006-07-18 devnull b->next = dcache.free;
406 28b49df3 2006-07-18 devnull dcache.free = b;
409 28b49df3 2006-07-18 devnull qunlock(&dcache.lock);
413 a0d146ed 2005-07-12 devnull * delete an arbitrary block from the heap
415 a0d146ed 2005-07-12 devnull static void
416 a0d146ed 2005-07-12 devnull delheap(DBlock *db)
418 a0d146ed 2005-07-12 devnull if(db->heap == TWID32)
420 a0d146ed 2005-07-12 devnull fixheap(db->heap, dcache.heap[--dcache.nheap]);
421 a0d146ed 2005-07-12 devnull db->heap = TWID32;
425 a0d146ed 2005-07-12 devnull * push an element up or down to it's correct new location
427 a0d146ed 2005-07-12 devnull static void
428 a0d146ed 2005-07-12 devnull fixheap(int i, DBlock *b)
430 a0d146ed 2005-07-12 devnull if(upheap(i, b) == i)
431 a0d146ed 2005-07-12 devnull downheap(i, b);
434 a0d146ed 2005-07-12 devnull static int
435 a0d146ed 2005-07-12 devnull upheap(int i, DBlock *b)
437 a0d146ed 2005-07-12 devnull DBlock *bb;
438 a0d146ed 2005-07-12 devnull u32int now;
441 a0d146ed 2005-07-12 devnull now = dcache.now;
442 a0d146ed 2005-07-12 devnull for(; i != 0; i = p){
443 a0d146ed 2005-07-12 devnull p = (i - 1) >> 1;
444 a0d146ed 2005-07-12 devnull bb = dcache.heap[p];
445 a0d146ed 2005-07-12 devnull if(b->used2 - now >= bb->used2 - now)
447 a0d146ed 2005-07-12 devnull dcache.heap[i] = bb;
448 a0d146ed 2005-07-12 devnull bb->heap = i;
451 a0d146ed 2005-07-12 devnull dcache.heap[i] = b;
452 a0d146ed 2005-07-12 devnull b->heap = i;
453 a0d146ed 2005-07-12 devnull return i;
456 a0d146ed 2005-07-12 devnull static int
457 a0d146ed 2005-07-12 devnull downheap(int i, DBlock *b)
459 a0d146ed 2005-07-12 devnull DBlock *bb;
460 a0d146ed 2005-07-12 devnull u32int now;
463 a0d146ed 2005-07-12 devnull now = dcache.now;
464 a0d146ed 2005-07-12 devnull for(; ; i = k){
465 a0d146ed 2005-07-12 devnull k = (i << 1) + 1;
466 a0d146ed 2005-07-12 devnull if(k >= dcache.nheap)
468 a0d146ed 2005-07-12 devnull if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
470 a0d146ed 2005-07-12 devnull bb = dcache.heap[k];
471 a0d146ed 2005-07-12 devnull if(b->used2 - now <= bb->used2 - now)
473 a0d146ed 2005-07-12 devnull dcache.heap[i] = bb;
474 a0d146ed 2005-07-12 devnull bb->heap = i;
477 a0d146ed 2005-07-12 devnull dcache.heap[i] = b;
478 a0d146ed 2005-07-12 devnull b->heap = i;
479 a0d146ed 2005-07-12 devnull return i;
482 a0d146ed 2005-07-12 devnull static void
483 a0d146ed 2005-07-12 devnull findblock(DBlock *bb)
485 a0d146ed 2005-07-12 devnull DBlock *b, *last;
488 a0d146ed 2005-07-12 devnull last = nil;
489 a0d146ed 2005-07-12 devnull h = pbhash(bb->addr);
490 a0d146ed 2005-07-12 devnull for(b = dcache.heads[h]; b != nil; b = b->next){
491 a0d146ed 2005-07-12 devnull if(last != b->prev)
492 a0d146ed 2005-07-12 devnull sysfatal("bad prev link");
493 a0d146ed 2005-07-12 devnull if(b == bb)
495 a0d146ed 2005-07-12 devnull last = b;
497 a0d146ed 2005-07-12 devnull sysfatal("block missing from hash table");
501 a0d146ed 2005-07-12 devnull checkdcache(void)
503 a0d146ed 2005-07-12 devnull DBlock *b;
504 a0d146ed 2005-07-12 devnull u32int size, now;
505 a0d146ed 2005-07-12 devnull int i, k, refed, nfree;
507 a0d146ed 2005-07-12 devnull qlock(&dcache.lock);
508 a0d146ed 2005-07-12 devnull size = dcache.size;
509 a0d146ed 2005-07-12 devnull now = dcache.now;
510 a0d146ed 2005-07-12 devnull for(i = 0; i < dcache.nheap; i++){
511 a0d146ed 2005-07-12 devnull if(dcache.heap[i]->heap != i)
512 a0d146ed 2005-07-12 devnull sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
513 a0d146ed 2005-07-12 devnull if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
514 a0d146ed 2005-07-12 devnull sysfatal("dc: bad heap ordering");
515 a0d146ed 2005-07-12 devnull k = (i << 1) + 1;
516 a0d146ed 2005-07-12 devnull if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
517 a0d146ed 2005-07-12 devnull sysfatal("dc: bad heap ordering");
519 a0d146ed 2005-07-12 devnull if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
520 a0d146ed 2005-07-12 devnull sysfatal("dc: bad heap ordering");
523 a0d146ed 2005-07-12 devnull refed = 0;
524 a0d146ed 2005-07-12 devnull for(i = 0; i < dcache.nblocks; i++){
525 a0d146ed 2005-07-12 devnull b = &dcache.blocks[i];
526 a0d146ed 2005-07-12 devnull if(b->data != &dcache.mem[i * size])
527 a0d146ed 2005-07-12 devnull sysfatal("dc: mis-blocked at %d", i);
528 a0d146ed 2005-07-12 devnull if(b->ref && b->heap == TWID32)
529 a0d146ed 2005-07-12 devnull refed++;
530 a0d146ed 2005-07-12 devnull if(b->addr)
531 a0d146ed 2005-07-12 devnull findblock(b);
532 a0d146ed 2005-07-12 devnull if(b->heap != TWID32
533 a0d146ed 2005-07-12 devnull && dcache.heap[b->heap] != b)
534 a0d146ed 2005-07-12 devnull sysfatal("dc: spurious heap value");
537 a0d146ed 2005-07-12 devnull nfree = 0;
538 a0d146ed 2005-07-12 devnull for(b = dcache.free; b != nil; b = b->next){
539 a0d146ed 2005-07-12 devnull if(b->addr != 0 || b->heap != TWID32)
540 a0d146ed 2005-07-12 devnull sysfatal("dc: bad free list");
541 a0d146ed 2005-07-12 devnull nfree++;
544 a0d146ed 2005-07-12 devnull if(dcache.nheap + nfree + refed != dcache.nblocks)
545 a0d146ed 2005-07-12 devnull sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
546 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
550 a0d146ed 2005-07-12 devnull flushdcache(void)
552 a0d146ed 2005-07-12 devnull trace(TraceProc, "flushdcache enter");
553 a0d146ed 2005-07-12 devnull kickround(&dcache.round, 1);
554 a0d146ed 2005-07-12 devnull trace(TraceProc, "flushdcache exit");
558 a0d146ed 2005-07-12 devnull kickdcache(void)
560 a0d146ed 2005-07-12 devnull kickround(&dcache.round, 0);
563 a0d146ed 2005-07-12 devnull static int
564 a0d146ed 2005-07-12 devnull parallelwrites(DBlock **b, DBlock **eb, int dirty)
566 a0d146ed 2005-07-12 devnull DBlock **p, **q;
567 7e452401 2007-04-27 devnull Part *part;
569 a0d146ed 2005-07-12 devnull for(p=b; p<eb && (*p)->dirty == dirty; p++){
570 a0d146ed 2005-07-12 devnull assert(b<=p && p<eb);
571 a0d146ed 2005-07-12 devnull sendp((*p)->part->writechan, *p);
574 a0d146ed 2005-07-12 devnull for(p=b; p<q; p++){
575 a0d146ed 2005-07-12 devnull assert(b<=p && p<eb);
576 a0d146ed 2005-07-12 devnull recvp((*p)->writedonechan);
580 7e452401 2007-04-27 devnull * Flush the partitions that have been written to.
582 7e452401 2007-04-27 devnull part = nil;
583 7e452401 2007-04-27 devnull for(p=b; p<q; p++){
584 7e452401 2007-04-27 devnull if(part != (*p)->part){
585 7e452401 2007-04-27 devnull part = (*p)->part;
586 e46cacb0 2007-04-27 devnull flushpart(part); /* what if it fails? */
590 a0d146ed 2005-07-12 devnull return p-b;
594 a0d146ed 2005-07-12 devnull * Sort first by dirty flag, then by partition, then by address in partition.
596 a0d146ed 2005-07-12 devnull static int
597 a0d146ed 2005-07-12 devnull writeblockcmp(const void *va, const void *vb)
599 a0d146ed 2005-07-12 devnull DBlock *a, *b;
601 a0d146ed 2005-07-12 devnull a = *(DBlock**)va;
602 a0d146ed 2005-07-12 devnull b = *(DBlock**)vb;
604 a0d146ed 2005-07-12 devnull if(a->dirty != b->dirty)
605 a0d146ed 2005-07-12 devnull return a->dirty - b->dirty;
606 a0d146ed 2005-07-12 devnull if(a->part != b->part){
607 a0d146ed 2005-07-12 devnull if(a->part < b->part)
608 a0d146ed 2005-07-12 devnull return -1;
609 a0d146ed 2005-07-12 devnull if(a->part > b->part)
610 a0d146ed 2005-07-12 devnull return 1;
612 a0d146ed 2005-07-12 devnull if(a->addr < b->addr)
613 a0d146ed 2005-07-12 devnull return -1;
614 a0d146ed 2005-07-12 devnull return 1;
617 a0d146ed 2005-07-12 devnull static void
618 a0d146ed 2005-07-12 devnull flushproc(void *v)
620 a0d146ed 2005-07-12 devnull int i, j, n;
621 a0d146ed 2005-07-12 devnull ulong t0;
622 a0d146ed 2005-07-12 devnull DBlock *b, **write;
624 a0d146ed 2005-07-12 devnull USED(v);
625 a0d146ed 2005-07-12 devnull threadsetname("flushproc");
626 a0d146ed 2005-07-12 devnull for(;;){
627 a0d146ed 2005-07-12 devnull waitforkick(&dcache.round);
629 a0d146ed 2005-07-12 devnull trace(TraceWork, "start");
630 12c0e45f 2007-09-25 rsc t0 = nsec()/1000;
631 12c0e45f 2007-09-25 rsc trace(TraceProc, "build t=%lud", (ulong)(nsec()/1000)-t0);
633 a0d146ed 2005-07-12 devnull write = dcache.write;
635 a0d146ed 2005-07-12 devnull for(i=0; i<dcache.nblocks; i++){
636 a0d146ed 2005-07-12 devnull b = &dcache.blocks[i];
637 a0d146ed 2005-07-12 devnull if(b->dirty)
638 a0d146ed 2005-07-12 devnull write[n++] = b;
641 a0d146ed 2005-07-12 devnull qsort(write, n, sizeof(write[0]), writeblockcmp);
643 a0d146ed 2005-07-12 devnull /* Write each stage of blocks out. */
644 a0d146ed 2005-07-12 devnull trace(TraceProc, "writeblocks t=%lud", (ulong)(nsec()/1000)-t0);
646 a0d146ed 2005-07-12 devnull for(j=1; j<DirtyMax; j++){
647 12c0e45f 2007-09-25 rsc trace(TraceProc, "writeblocks.%d t=%lud",
648 12c0e45f 2007-09-25 rsc j, (ulong)(nsec()/1000)-t0);
649 a0d146ed 2005-07-12 devnull i += parallelwrites(write+i, write+n, j);
651 a0d146ed 2005-07-12 devnull if(i != n){
652 a0d146ed 2005-07-12 devnull fprint(2, "in flushproc i=%d n=%d\n", i, n);
653 a0d146ed 2005-07-12 devnull for(i=0; i<n; i++)
654 12c0e45f 2007-09-25 rsc fprint(2, "\tblock %d: dirty=%d\n",
655 12c0e45f 2007-09-25 rsc i, write[i]->dirty);
656 a0d146ed 2005-07-12 devnull abort();
660 12c0e45f 2007-09-25 rsc * b->dirty is protected by b->lock while ndirty is protected
661 12c0e45f 2007-09-25 rsc * by dcache.lock, so the --ndirty below is the delayed one
662 12c0e45f 2007-09-25 rsc * from clearing b->dirty in the write proc. It may happen
663 12c0e45f 2007-09-25 rsc * that some other proc has come along and redirtied b since
664 12c0e45f 2007-09-25 rsc * the write. That's okay, it just means that ndirty may be
665 12c0e45f 2007-09-25 rsc * one too high until we catch up and do the decrement.
667 a0d146ed 2005-07-12 devnull trace(TraceProc, "undirty.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
668 a0d146ed 2005-07-12 devnull qlock(&dcache.lock);
669 a0d146ed 2005-07-12 devnull for(i=0; i<n; i++){
670 a0d146ed 2005-07-12 devnull b = write[i];
671 a0d146ed 2005-07-12 devnull --dcache.ndirty;
672 a0d146ed 2005-07-12 devnull if(b->ref == 0 && b->heap == TWID32){
673 a0d146ed 2005-07-12 devnull upheap(dcache.nheap++, b);
674 a0d146ed 2005-07-12 devnull rwakeupall(&dcache.full);
677 a0d146ed 2005-07-12 devnull setstat(StatDcacheDirty, dcache.ndirty);
678 a0d146ed 2005-07-12 devnull qunlock(&dcache.lock);
679 a0d146ed 2005-07-12 devnull addstat(StatDcacheFlush, 1);
680 a0d146ed 2005-07-12 devnull trace(TraceWork, "finish");
684 a0d146ed 2005-07-12 devnull static void
685 a0d146ed 2005-07-12 devnull writeproc(void *v)
687 a0d146ed 2005-07-12 devnull DBlock *b;
688 a0d146ed 2005-07-12 devnull Part *p;
692 a0d146ed 2005-07-12 devnull threadsetname("writeproc:%s", p->name);
693 a0d146ed 2005-07-12 devnull for(;;){
694 a0d146ed 2005-07-12 devnull b = recvp(p->writechan);
695 a0d146ed 2005-07-12 devnull trace(TraceWork, "start");
696 a0d146ed 2005-07-12 devnull assert(b->part == p);
697 a0d146ed 2005-07-12 devnull trace(TraceProc, "wlock %s 0x%llux", p->name, b->addr);
698 a0d146ed 2005-07-12 devnull wlock(&b->lock);
699 a0d146ed 2005-07-12 devnull trace(TraceProc, "writepart %s 0x%llux", p->name, b->addr);
700 28b49df3 2006-07-18 devnull diskaccess(0);
701 a0d146ed 2005-07-12 devnull if(writepart(p, b->addr, b->data, b->size) < 0)
702 12c0e45f 2007-09-25 rsc fprint(2, "%s: writeproc: part %s addr 0x%llux: write error: %r\n",
703 12c0e45f 2007-09-25 rsc argv0, p->name, b->addr);
704 a0d146ed 2005-07-12 devnull addstat(StatApartWrite, 1);
705 a0d146ed 2005-07-12 devnull addstat(StatApartWriteBytes, b->size);
706 a0d146ed 2005-07-12 devnull b->dirty = 0;
707 a0d146ed 2005-07-12 devnull wunlock(&b->lock);
708 a0d146ed 2005-07-12 devnull trace(TraceProc, "finish %s 0x%llux", p->name, b->addr);
709 a0d146ed 2005-07-12 devnull trace(TraceWork, "finish");
710 a0d146ed 2005-07-12 devnull sendp(b->writedonechan, b);
