4 * Caches raw disk blocks. Getdblock() gets a block, putdblock puts it back.
5 * Getdblock has a mode parameter that determines i/o and access to a block:
6 * if mode is OREAD or ORDWR, it is read from disk if not already in memory.
7 * If mode is ORDWR or OWRITE, it is locked for exclusive use before being returned.
8 * It is *not* marked dirty -- once changes have been made, they should be noted
9 * by using dirtydblock() before putdblock().
11 * There is a global cache lock as well as a lock on each block.
12 * Within a thread, the cache lock can be acquired while holding a block lock,
13 * but not vice versa; and a block cannot be locked if you already hold the lock
16 * The flush proc writes out dirty blocks in batches, one batch per dirty tag.
17 * For example, the DirtyArena blocks are all written to disk before any of the
18 * DirtyArenaCib blocks.
20 * This code used to be in charge of flushing the dirty index blocks out to
21 * disk, but updating the index turned out to benefit from extra care.
22 * Now cached index blocks are never marked dirty. The index.c code takes
23 * care of updating them behind our back, and uses _getdblock to update any
24 * cached copies of the blocks as it changes them on disk.
31 typedef struct DCache DCache;
36 HashSize = 1<<HashLog,
37 HashMask = HashSize - 1,
43 RWLock dirtylock; /* must be held to inspect or set b->dirty */
46 DBlock *free; /* list of available lumps */
47 u32int now; /* ticks for usage timestamps */
48 int size; /* max. size of any block; allocated to each block */
49 DBlock **heads; /* hash table for finding address */
50 int nheap; /* number of available victims */
51 DBlock **heap; /* heap for locating victims */
52 int nblocks; /* number of blocks allocated */
53 DBlock *blocks; /* array of block descriptors */
54 DBlock **write; /* array of block pointers to be written */
55 u8int *mem; /* memory for all block descriptors */
56 int ndirty; /* number of dirty blocks */
57 int maxdirty; /* max. number of dirty blocks */
78 static int downheap(int i, DBlock *b);
79 static int upheap(int i, DBlock *b);
80 static DBlock *bumpdblock(void);
81 static void delheap(DBlock *db);
82 static void fixheap(int i, DBlock *b);
83 static void flushproc(void*);
84 static void writeproc(void*);
85 static void raproc(void*);
88 initdcache(u32int mem)
91 u32int nblocks, blocksize;
95 if(mem < maxblocksize * 2)
96 sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
98 sysfatal("no max. block size given for disk cache");
99 blocksize = maxblocksize;
100 nblocks = mem / blocksize;
101 dcache.full.l = &dcache.lock;
102 dcache.nblocks = nblocks;
103 dcache.maxdirty = (nblocks * 2) / 3;
104 trace(TraceProc, "initialize disk cache with %d blocks of %d bytes, maximum %d dirty blocks\n",
105 nblocks, blocksize, dcache.maxdirty);
106 dcache.size = blocksize;
107 dcache.heads = MKNZ(DBlock*, HashSize);
108 dcache.heap = MKNZ(DBlock*, nblocks);
109 dcache.blocks = MKNZ(DBlock, nblocks);
110 dcache.write = MKNZ(DBlock*, nblocks);
111 dcache.mem = MKNZ(u8int, (nblocks+1+128) * blocksize);
112 dcache.ra = chancreate(sizeof(Ra), 0);
115 p = (u8int*)(((ulong)dcache.mem+blocksize-1)&~(ulong)(blocksize-1));
116 for(i = 0; i < nblocks; i++){
117 b = &dcache.blocks[i];
118 b->data = &p[i * blocksize];
120 b->writedonechan = chancreate(sizeof(void*), 1);
124 dcache.rabuf = &p[i*blocksize];
125 dcache.ramax = 128*blocksize;
131 setstat(StatDcacheSize, nblocks);
132 initround(&dcache.round, "dcache", 120*1000);
134 vtproc(flushproc, nil);
135 vtproc(delaykickroundproc, &dcache.round);
140 setdcachestate(AState *a)
142 trace(TraceBlock, "setdcachestate %s 0x%llux clumps %d", a->arena ? a->arena->name : nil, a->aa, a->stats.clumps);
145 qunlock(&dcache.lock);
154 a = dcache.diskstate;
155 qunlock(&dcache.lock);
166 while(recv(dcache.ra, &ra) == 1){
167 if(ra.part->size <= ra.addr)
169 b = _getdblock(ra.part, ra.addr, OREAD, 2);
175 dreadahead(Part *part, u64int addr, int miss)
190 if(lastmiss.part==part && lastmiss.addr==addr-dcache.size){
193 lastra.dir = addr-lastmiss.addr;
194 lastra.addr = addr+lastra.dir;
196 ra.addr = lastra.addr;
197 nbsend(dcache.ra, &ra);
198 }else if(lastmiss.part==part && lastmiss.addr==addr+dcache.size){
203 if(lastra.part==part && lastra.addr==addr){
204 lastra.addr += lastra.dir;
206 ra.addr = lastra.addr;
207 nbsend(dcache.ra, &ra);
212 lastmiss.part = part;
213 lastmiss.addr = addr;
216 // fprint(2, "%s %llx %s\n", part->name, addr, miss ? "miss" : "hit");
220 rareadpart(Part *part, u64int addr, u8int *buf, uint n, int load)
223 static RWLock ralock;
226 if(dcache.rapart==part && dcache.raaddr <= addr && addr+n <= dcache.raaddr+dcache.rasize){
227 memmove(buf, dcache.rabuf+(addr-dcache.raaddr), n);
231 if(load != 2 || addr >= part->size){ /* addr >= part->size: let readpart do the error */
233 return readpart(part, addr, buf, n);
238 fprint(2, "raread %s %llx\n", part->name, addr);
240 if(addr+nn > part->size)
241 nn = part->size - addr;
242 if(readpart(part, addr, dcache.rabuf, nn) < 0){
246 memmove(buf, dcache.rabuf, n);
247 dcache.rapart = part;
249 dcache.raaddr = addr;
252 addstat(StatApartReadBytes, nn-n);
261 #define hashit(c) ((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
262 h = (addr >> 32) ^ addr;
267 getdblock(Part *part, u64int addr, int mode)
273 b = _getdblock(part, addr, mode, 1);
274 if(mode == OREAD || mode == ORDWR)
275 addstat(StatDcacheRead, 1);
276 if(mode == OWRITE || mode == ORDWR)
277 addstat(StatDcacheWrite, 1);
279 addstat2(StatDcacheLookup, 1, StatDcacheLookupTime, ms);
284 _getdblock(Part *part, u64int addr, int mode, int load)
289 trace(TraceBlock, "getdblock enter %s 0x%llux", part->name, addr);
290 size = part->blocksize;
291 if(size > dcache.size){
292 seterr(EAdmin, "block size %d too big for cache with size %d", size, dcache.size);
298 * look for the block in the cache
303 for(b = dcache.heads[h]; b != nil; b = b->next){
304 if(b->part == part && b->addr == addr){
308 qunlock(&stats.lock);
311 addstat(StatDcacheHit, 1);
312 if(load != 2 && mode != OWRITE)
313 dreadahead(part, b->addr, 0);
320 * missed: locate the block with the oldest second to last use.
321 * remove it from the heap, and fix up the heap.
324 qunlock(&dcache.lock);
328 addstat(StatDcacheMiss, 1);
332 trace(TraceBlock, "all disk cache blocks in use");
333 addstat(StatDcacheStall, 1);
334 rsleep(&dcache.full);
335 addstat(StatDcacheStall, -1);
342 * the new block has no last use, so assume it happens sometime in the middle
343 ZZZ this is not reasonable
345 b->used = (b->used2 + dcache.now) / 2;
348 * rechain the block on the correct hash chain
350 b->next = dcache.heads[h];
359 if(load != 2 && mode != OWRITE)
360 dreadahead(part, b->addr, 1);
365 b->used = dcache.now++;
366 if(b->heap != TWID32)
369 qunlock(&dcache.lock);
372 trace(TraceBlock, "getdblock lock");
373 addstat(StatDblockStall, 1);
378 addstat(StatDblockStall, -1);
379 trace(TraceBlock, "getdblock locked");
383 addstat(StatDblockStall, 1);
386 addstat(StatDblockStall, -1);
390 memset(&b->data[b->size], 0, size - b->size);
392 trace(TraceBlock, "getdblock readpart %s 0x%llux", part->name, addr);
393 if(rareadpart(part, addr + b->size, &b->data[b->size], size - b->size, load) < 0){
394 b->mode = ORDWR; /* so putdblock wunlocks */
398 trace(TraceBlock, "getdblock readpartdone");
399 addstat(StatApartRead, 1);
400 addstat(StatApartReadBytes, size-b->size);
405 addstat(StatDblockStall, 1);
408 addstat(StatDblockStall, -1);
413 trace(TraceBlock, "getdblock exit");
423 trace(TraceBlock, "putdblock %s 0x%llux", b->part->name, b->addr);
432 if(--b->ref == 0 && !b->dirty){
433 if(b->heap == TWID32)
434 upheap(dcache.nheap++, b);
435 rwakeupall(&dcache.full);
437 qunlock(&dcache.lock);
442 dirtydblock(DBlock *b, int dirty)
448 trace(TraceBlock, "dirtydblock enter %s 0x%llux %d from 0x%lux", b->part->name, b->addr, dirty, getcallerpc(&b));
450 assert(b->mode==ORDWR || b->mode==OWRITE);
454 assert(b->dirty == dirty);
459 if(p->writechan == nil){
460 trace(TraceBlock, "dirtydblock allocwriteproc %s", p->name);
461 /* XXX hope this doesn't fail! */
462 p->writechan = chancreate(sizeof(DBlock*), dcache.nblocks);
463 vtproc(writeproc, p);
468 setstat(StatDcacheDirty, dcache.ndirty);
469 if(dcache.ndirty >= dcache.maxdirty)
470 kickround(&dcache.round, 0);
472 delaykickround(&dcache.round);
474 qunlock(&dcache.lock);
478 * remove some block from use and update the free list and counters
486 trace(TraceBlock, "bumpdblock enter");
489 dcache.free = b->next;
493 if(dcache.ndirty >= dcache.maxdirty)
497 * remove blocks until we find one that is unused
498 * referenced blocks are left in the heap even though
499 * they can't be scavenged; this is simple a speed optimization
502 if(dcache.nheap == 0){
504 trace(TraceBlock, "bumpdblock gotnothing");
509 if(!b->ref && !b->dirty)
513 trace(TraceBlock, "bumpdblock bumping %s 0x%llux", b->part->name, b->addr);
520 if(dcache.heads[h] != b)
521 sysfatal("bad hash chains in disk cache");
522 dcache.heads[h] = b->next;
524 b->prev->next = b->next;
526 b->next->prev = b->prev;
532 * delete an arbitrary block from the heap
537 if(db->heap == TWID32)
539 fixheap(db->heap, dcache.heap[--dcache.nheap]);
544 * push an element up or down to it's correct new location
547 fixheap(int i, DBlock *b)
549 if(upheap(i, b) == i)
554 upheap(int i, DBlock *b)
561 for(; i != 0; i = p){
564 if(b->used2 - now >= bb->used2 - now)
576 downheap(int i, DBlock *b)
585 if(k >= dcache.nheap)
587 if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
590 if(b->used2 - now <= bb->used2 - now)
602 findblock(DBlock *bb)
608 h = pbhash(bb->addr);
609 for(b = dcache.heads[h]; b != nil; b = b->next){
611 sysfatal("bad prev link");
616 sysfatal("block missing from hash table");
624 int i, k, refed, nfree;
629 for(i = 0; i < dcache.nheap; i++){
630 if(dcache.heap[i]->heap != i)
631 sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
632 if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
633 sysfatal("dc: bad heap ordering");
635 if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
636 sysfatal("dc: bad heap ordering");
638 if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
639 sysfatal("dc: bad heap ordering");
643 for(i = 0; i < dcache.nblocks; i++){
644 b = &dcache.blocks[i];
645 if(b->data != &dcache.mem[i * size])
646 sysfatal("dc: mis-blocked at %d", i);
647 if(b->ref && b->heap == TWID32)
652 && dcache.heap[b->heap] != b)
653 sysfatal("dc: spurious heap value");
657 for(b = dcache.free; b != nil; b = b->next){
658 if(b->addr != 0 || b->heap != TWID32)
659 sysfatal("dc: bad free list");
663 if(dcache.nheap + nfree + refed != dcache.nblocks)
664 sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
665 qunlock(&dcache.lock);
671 trace(TraceProc, "flushdcache enter");
672 kickround(&dcache.round, 1);
673 trace(TraceProc, "flushdcache exit");
679 kickround(&dcache.round, 0);
683 parallelwrites(DBlock **b, DBlock **eb, int dirty)
686 for(p=b; p<eb && (*p)->dirty == dirty; p++){
687 assert(b<=p && p<eb);
688 sendp((*p)->part->writechan, *p);
692 assert(b<=p && p<eb);
693 recvp((*p)->writedonechan);
700 * Sort first by dirty flag, then by partition, then by address in partition.
703 writeblockcmp(const void *va, const void *vb)
710 if(a->dirty != b->dirty)
711 return a->dirty - b->dirty;
712 if(a->part != b->part){
713 if(a->part < b->part)
715 if(a->part > b->part)
718 if(a->addr < b->addr)
732 threadsetname("flushproc");
734 waitforkick(&dcache.round);
736 trace(TraceWork, "start");
739 qunlock(&dcache.lock);
743 trace(TraceProc, "build t=%lud", (ulong)(nsec()/1000)-t0);
744 write = dcache.write;
746 for(i=0; i<dcache.nblocks; i++){
747 b = &dcache.blocks[i];
752 qsort(write, n, sizeof(write[0]), writeblockcmp);
754 /* Write each stage of blocks out. */
755 trace(TraceProc, "writeblocks t=%lud", (ulong)(nsec()/1000)-t0);
757 for(j=1; j<DirtyMax; j++){
758 trace(TraceProc, "writeblocks.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
759 i += parallelwrites(write+i, write+n, j);
762 fprint(2, "in flushproc i=%d n=%d\n", i, n);
764 fprint(2, "\tblock %d: dirty=%d\n", i, write[i]->dirty);
769 * the locking here is suspect. what if a block is redirtied
770 * after the write happens? we'll still decrement dcache.ndirty here.
772 trace(TraceProc, "undirty.%d t=%lud", j, (ulong)(nsec()/1000)-t0);
774 dcache.diskstate = as;
778 if(b->ref == 0 && b->heap == TWID32){
779 upheap(dcache.nheap++, b);
780 rwakeupall(&dcache.full);
783 setstat(StatDcacheDirty, dcache.ndirty);
784 qunlock(&dcache.lock);
785 addstat(StatDcacheFlush, 1);
786 trace(TraceWork, "finish");
798 threadsetname("writeproc:%s", p->name);
800 b = recvp(p->writechan);
801 trace(TraceWork, "start");
802 assert(b->part == p);
803 trace(TraceProc, "wlock %s 0x%llux", p->name, b->addr);
805 trace(TraceProc, "writepart %s 0x%llux", p->name, b->addr);
806 if(writepart(p, b->addr, b->data, b->size) < 0)
807 fprint(2, "write error: %r\n"); /* XXX details! */
808 addstat(StatApartWrite, 1);
809 addstat(StatApartWriteBytes, b->size);
812 trace(TraceProc, "finish %s 0x%llux", p->name, b->addr);
813 trace(TraceWork, "finish");
814 sendp(b->writedonechan, b);