1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098 |
- #include "stdinc.h"
- #include "dat.h"
- #include "fns.h"
- #include "error.h"
- #include "9.h" /* for cacheFlush */
- typedef struct FreeList FreeList;
- typedef struct BAddr BAddr;
- enum {
- BadHeap = ~0,
- };
- /*
- * Store data to the memory cache in c->size blocks
- * with the block zero extended to fill it out. When writing to
- * Venti, the block will be zero truncated. The walker will also check
- * that the block fits within psize or dsize as the case may be.
- */
- struct Cache
- {
- VtLock *lk;
- VtLock *dirtylk;
- int ref;
- int mode;
- Disk *disk;
- int size; /* block size */
- int ndmap; /* size of per-block dirty pointer map used in blockWrite */
- VtSession *z;
- u32int now; /* ticks for usage timestamps */
- Block **heads; /* hash table for finding address */
- int nheap; /* number of available victims */
- Block **heap; /* heap for locating victims */
- long nblocks; /* number of blocks allocated */
- Block *blocks; /* array of block descriptors */
- u8int *mem; /* memory for all block data & blists */
- BList *blfree;
- VtRendez *blrend;
- int ndirty; /* number of dirty blocks in the cache */
- int maxdirty; /* max number of dirty blocks */
- u32int vers;
- long hashSize;
- FreeList *fl;
- VtRendez *die; /* daemon threads should die when != nil */
- VtRendez *flush;
- VtRendez *flushwait;
- VtRendez *heapwait;
- BAddr *baddr;
- int bw, br, be;
- int nflush;
- Periodic *sync;
- /* unlink daemon */
- BList *uhead;
- BList *utail;
- VtRendez *unlink;
- /* block counts */
- int nused;
- int ndisk;
- };
- struct BList {
- int part;
- u32int addr;
- uchar type;
- u32int tag;
- u32int epoch;
- u32int vers;
- int recurse; /* for block unlink */
- /* for roll back */
- int index; /* -1 indicates not valid */
- union {
- uchar score[VtScoreSize];
- uchar entry[VtEntrySize];
- } old;
- BList *next;
- };
- struct BAddr {
- int part;
- u32int addr;
- u32int vers;
- };
- struct FreeList {
- VtLock *lk;
- u32int last; /* last block allocated */
- u32int end; /* end of data partition */
- u32int nfree; /* number of free blocks */
- u32int nused; /* number of used blocks */
- u32int epochLow; /* low epoch when last updated nfree and nused */
- };
- static FreeList *flAlloc(u32int end);
- static void flFree(FreeList *fl);
- static Block *cacheBumpBlock(Cache *c);
- static void heapDel(Block*);
- static void heapIns(Block*);
- static void cacheCheck(Cache*);
- static void unlinkThread(void *a);
- static void flushThread(void *a);
- static void flushBody(Cache *c);
- static void unlinkBody(Cache *c);
- static int cacheFlushBlock(Cache *c);
- static void cacheSync(void*);
- static BList *blistAlloc(Block*);
- static void blistFree(Cache*, BList*);
- static void doRemoveLink(Cache*, BList*);
- static void doRemoveLinkList(Cache*, BList*);
- /*
- * Mapping from local block type to Venti type
- */
- int vtType[BtMax] = {
- VtDataType, /* BtData | 0 */
- VtPointerType0, /* BtData | 1 */
- VtPointerType1, /* BtData | 2 */
- VtPointerType2, /* BtData | 3 */
- VtPointerType3, /* BtData | 4 */
- VtPointerType4, /* BtData | 5 */
- VtPointerType5, /* BtData | 6 */
- VtPointerType6, /* BtData | 7 */
- VtDirType, /* BtDir | 0 */
- VtPointerType0, /* BtDir | 1 */
- VtPointerType1, /* BtDir | 2 */
- VtPointerType2, /* BtDir | 3 */
- VtPointerType3, /* BtDir | 4 */
- VtPointerType4, /* BtDir | 5 */
- VtPointerType5, /* BtDir | 6 */
- VtPointerType6, /* BtDir | 7 */
- };
- /*
- * Allocate the memory cache.
- */
- Cache *
- cacheAlloc(Disk *disk, VtSession *z, ulong nblocks, int mode)
- {
- int i;
- Cache *c;
- Block *b;
- BList *bl;
- u8int *p;
- int nbl;
- c = vtMemAllocZ(sizeof(Cache));
- /* reasonable number of BList elements */
- nbl = nblocks * 4;
- c->lk = vtLockAlloc();
- c->dirtylk = vtLockAlloc(); /* allowed to dirty blocks */
- c->ref = 1;
- c->disk = disk;
- c->z = z;
- c->size = diskBlockSize(disk);
- bwatchSetBlockSize(c->size);
- /* round c->size up to be a nice multiple */
- c->size = (c->size + 127) & ~127;
- c->ndmap = (c->size/20 + 7) / 8;
- c->nblocks = nblocks;
- c->hashSize = nblocks;
- c->heads = vtMemAllocZ(c->hashSize*sizeof(Block*));
- c->heap = vtMemAllocZ(nblocks*sizeof(Block*));
- c->blocks = vtMemAllocZ(nblocks*sizeof(Block));
- c->mem = vtMemAllocZ(nblocks * (c->size + c->ndmap) + nbl * sizeof(BList));
- c->baddr = vtMemAllocZ(nblocks * sizeof(BAddr));
- c->mode = mode;
- c->vers++;
- p = c->mem;
- for(i = 0; i < nblocks; i++){
- b = &c->blocks[i];
- b->lk = vtLockAlloc();
- b->c = c;
- b->data = p;
- b->heap = i;
- b->ioready = vtRendezAlloc(b->lk);
- c->heap[i] = b;
- p += c->size;
- }
- c->nheap = nblocks;
- for(i = 0; i < nbl; i++){
- bl = (BList*)p;
- bl->next = c->blfree;
- c->blfree = bl;
- p += sizeof(BList);
- }
- /* separate loop to keep blocks and blists reasonably aligned */
- for(i = 0; i < nblocks; i++){
- b = &c->blocks[i];
- b->dmap = p;
- p += c->ndmap;
- }
- c->blrend = vtRendezAlloc(c->lk);
- c->maxdirty = nblocks*(DirtyPercentage*0.01);
- c->fl = flAlloc(diskSize(disk, PartData));
- c->unlink = vtRendezAlloc(c->lk);
- c->flush = vtRendezAlloc(c->lk);
- c->flushwait = vtRendezAlloc(c->lk);
- c->heapwait = vtRendezAlloc(c->lk);
- c->sync = periodicAlloc(cacheSync, c, 30*1000);
- if(mode == OReadWrite){
- c->ref += 2;
- vtThread(unlinkThread, c);
- vtThread(flushThread, c);
- }
- cacheCheck(c);
- return c;
- }
- /*
- * Free the whole memory cache, flushing all dirty blocks to the disk.
- */
- void
- cacheFree(Cache *c)
- {
- int i;
- /* kill off daemon threads */
- vtLock(c->lk);
- c->die = vtRendezAlloc(c->lk);
- periodicKill(c->sync);
- vtWakeup(c->flush);
- vtWakeup(c->unlink);
- while(c->ref > 1)
- vtSleep(c->die);
- /* flush everything out */
- do {
- unlinkBody(c);
- vtUnlock(c->lk);
- while(cacheFlushBlock(c))
- ;
- diskFlush(c->disk);
- vtLock(c->lk);
- } while(c->uhead || c->ndirty);
- vtUnlock(c->lk);
- cacheCheck(c);
- for(i = 0; i < c->nblocks; i++){
- assert(c->blocks[i].ref == 0);
- vtRendezFree(c->blocks[i].ioready);
- vtLockFree(c->blocks[i].lk);
- }
- flFree(c->fl);
- vtMemFree(c->baddr);
- vtMemFree(c->heads);
- vtMemFree(c->blocks);
- vtMemFree(c->mem);
- vtLockFree(c->lk);
- diskFree(c->disk);
- vtRendezFree(c->blrend);
- /* don't close vtSession */
- vtMemFree(c);
- }
- static void
- cacheDump(Cache *c)
- {
- int i;
- Block *b;
- for(i = 0; i < c->nblocks; i++){
- b = &c->blocks[i];
- fprint(2, "%d. p=%d a=%ud %V t=%d ref=%d state=%s io=%s pc=%#p\n",
- i, b->part, b->addr, b->score, b->l.type, b->ref,
- bsStr(b->l.state), bioStr(b->iostate), b->pc);
- }
- }
- static void
- cacheCheck(Cache *c)
- {
- u32int size, now;
- int i, k, refed;
- static uchar zero[VtScoreSize];
- Block *b;
- size = c->size;
- now = c->now;
- for(i = 0; i < c->nheap; i++){
- if(c->heap[i]->heap != i)
- vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
- if(i > 0 && c->heap[(i - 1) >> 1]->used - now > c->heap[i]->used - now)
- vtFatal("bad heap ordering");
- k = (i << 1) + 1;
- if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
- vtFatal("bad heap ordering");
- k++;
- if(k < c->nheap && c->heap[i]->used - now > c->heap[k]->used - now)
- vtFatal("bad heap ordering");
- }
- refed = 0;
- for(i = 0; i < c->nblocks; i++){
- b = &c->blocks[i];
- if(b->data != &c->mem[i * size])
- vtFatal("mis-blocked at %d", i);
- if(b->ref && b->heap == BadHeap){
- refed++;
- }
- }
- if(c->nheap + refed != c->nblocks){
- fprint(2, "cacheCheck: nheap %d refed %d nblocks %ld\n", c->nheap, refed, c->nblocks);
- cacheDump(c);
- }
- assert(c->nheap + refed == c->nblocks);
- refed = 0;
- for(i = 0; i < c->nblocks; i++){
- b = &c->blocks[i];
- if(b->ref){
- if(1)fprint(2, "p=%d a=%ud %V ref=%d %L\n", b->part, b->addr, b->score, b->ref, &b->l);
- refed++;
- }
- }
- if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
- }
- /*
- * locate the block with the oldest second to last use.
- * remove it from the heap, and fix up the heap.
- */
- /* called with c->lk held */
- static Block *
- cacheBumpBlock(Cache *c)
- {
- int printed;
- Block *b;
- /*
- * locate the block with the oldest second to last use.
- * remove it from the heap, and fix up the heap.
- */
- printed = 0;
- if(c->nheap == 0){
- while(c->nheap == 0){
- vtWakeup(c->flush);
- vtSleep(c->heapwait);
- if(c->nheap == 0){
- printed = 1;
- fprint(2, "entire cache is busy, %d dirty -- waking flush thread\n", c->ndirty);
- }
- }
- if(printed)
- fprint(2, "cache is okay again, %d dirty\n", c->ndirty);
- }
- b = c->heap[0];
- heapDel(b);
- assert(b->heap == BadHeap);
- assert(b->ref == 0);
- assert(b->iostate != BioDirty && b->iostate != BioReading && b->iostate != BioWriting);
- assert(b->prior == nil);
- assert(b->uhead == nil);
- /*
- * unchain the block from hash chain
- */
- if(b->prev){
- *(b->prev) = b->next;
- if(b->next)
- b->next->prev = b->prev;
- b->prev = nil;
- }
- if(0)fprint(2, "droping %d:%x:%V\n", b->part, b->addr, b->score);
- /* set block to a reasonable state */
- b->ref = 1;
- b->part = PartError;
- memset(&b->l, 0, sizeof(b->l));
- b->iostate = BioEmpty;
- return b;
- }
- /*
- * look for a particular version of the block in the memory cache.
- */
- static Block *
- _cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers,
- int waitlock, int *lockfailure)
- {
- Block *b;
- ulong h;
- h = addr % c->hashSize;
- if(lockfailure)
- *lockfailure = 0;
- /*
- * look for the block in the cache
- */
- vtLock(c->lk);
- for(b = c->heads[h]; b != nil; b = b->next){
- if(b->part == part && b->addr == addr)
- break;
- }
- if(b == nil || b->vers != vers){
- vtUnlock(c->lk);
- return nil;
- }
- if(!waitlock && !vtCanLock(b->lk)){
- *lockfailure = 1;
- vtUnlock(c->lk);
- return nil;
- }
- heapDel(b);
- b->ref++;
- vtUnlock(c->lk);
- bwatchLock(b);
- if(waitlock)
- vtLock(b->lk);
- b->nlock = 1;
- for(;;){
- switch(b->iostate){
- default:
- abort();
- case BioEmpty:
- case BioLabel:
- case BioClean:
- case BioDirty:
- if(b->vers != vers){
- blockPut(b);
- return nil;
- }
- return b;
- case BioReading:
- case BioWriting:
- vtSleep(b->ioready);
- break;
- case BioVentiError:
- blockPut(b);
- vtSetError("venti i/o error block 0x%.8ux", addr);
- return nil;
- case BioReadError:
- blockPut(b);
- vtSetError("error reading block 0x%.8ux", addr);
- return nil;
- }
- }
- /* NOT REACHED */
- }
- static Block*
- cacheLocalLookup(Cache *c, int part, u32int addr, u32int vers)
- {
- return _cacheLocalLookup(c, part, addr, vers, 1, 0);
- }
- /*
- * fetch a local (on-disk) block from the memory cache.
- * if it's not there, load it, bumping some other block.
- */
- Block *
- _cacheLocal(Cache *c, int part, u32int addr, int mode, u32int epoch)
- {
- Block *b;
- ulong h;
- assert(part != PartVenti);
- h = addr % c->hashSize;
- /*
- * look for the block in the cache
- */
- vtLock(c->lk);
- for(b = c->heads[h]; b != nil; b = b->next){
- if(b->part != part || b->addr != addr)
- continue;
- if(epoch && b->l.epoch != epoch){
- fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
- vtUnlock(c->lk);
- vtSetError(ELabelMismatch);
- return nil;
- }
- heapDel(b);
- b->ref++;
- break;
- }
- if(b == nil){
- b = cacheBumpBlock(c);
- b->part = part;
- b->addr = addr;
- localToGlobal(addr, b->score);
- /* chain onto correct hash */
- b->next = c->heads[h];
- c->heads[h] = b;
- if(b->next != nil)
- b->next->prev = &b->next;
- b->prev = &c->heads[h];
- }
- vtUnlock(c->lk);
- /*
- * BUG: what if the epoch changes right here?
- * In the worst case, we could end up in some weird
- * lock loop, because the block we want no longer exists,
- * and instead we're trying to lock a block we have no
- * business grabbing.
- *
- * For now, I'm not going to worry about it.
- */
- if(0)fprint(2, "cacheLocal: %d: %d %x\n", getpid(), b->part, b->addr);
- bwatchLock(b);
- vtLock(b->lk);
- b->nlock = 1;
- if(part == PartData && b->iostate == BioEmpty){
- if(!readLabel(c, &b->l, addr)){
- blockPut(b);
- return nil;
- }
- blockSetIOState(b, BioLabel);
- }
- if(epoch && b->l.epoch != epoch){
- blockPut(b);
- fprint(2, "_cacheLocal want epoch %ud got %ud\n", epoch, b->l.epoch);
- vtSetError(ELabelMismatch);
- return nil;
- }
- b->pc = getcallerpc(&c);
- for(;;){
- switch(b->iostate){
- default:
- abort();
- case BioEmpty:
- case BioLabel:
- if(mode == OOverWrite){
- blockSetIOState(b, BioClean);
- return b;
- }
- diskRead(c->disk, b);
- vtSleep(b->ioready);
- break;
- case BioClean:
- case BioDirty:
- return b;
- case BioReading:
- case BioWriting:
- vtSleep(b->ioready);
- break;
- case BioReadError:
- blockSetIOState(b, BioEmpty);
- blockPut(b);
- vtSetError("error reading block 0x%.8ux", addr);
- return nil;
- }
- }
- /* NOT REACHED */
- }
- Block *
- cacheLocal(Cache *c, int part, u32int addr, int mode)
- {
- return _cacheLocal(c, part, addr, mode, 0);
- }
- /*
- * fetch a local (on-disk) block from the memory cache.
- * if it's not there, load it, bumping some other block.
- * check tag and type.
- */
- Block *
- cacheLocalData(Cache *c, u32int addr, int type, u32int tag, int mode, u32int epoch)
- {
- Block *b;
- b = _cacheLocal(c, PartData, addr, mode, epoch);
- if(b == nil)
- return nil;
- if(b->l.type != type || b->l.tag != tag){
- fprint(2, "cacheLocalData: addr=%d type got %d exp %d: tag got %ux exp %ux\n",
- addr, b->l.type, type, b->l.tag, tag);
- vtSetError(ELabelMismatch);
- blockPut(b);
- return nil;
- }
- b->pc = getcallerpc(&c);
- return b;
- }
- /*
- * fetch a global (Venti) block from the memory cache.
- * if it's not there, load it, bumping some other block.
- * check tag and type if it's really a local block in disguise.
- */
- Block *
- cacheGlobal(Cache *c, uchar score[VtScoreSize], int type, u32int tag, int mode)
- {
- int n;
- Block *b;
- ulong h;
- u32int addr;
- addr = globalToLocal(score);
- if(addr != NilBlock){
- b = cacheLocalData(c, addr, type, tag, mode, 0);
- if(b)
- b->pc = getcallerpc(&c);
- return b;
- }
- h = (u32int)(score[0]|(score[1]<<8)|(score[2]<<16)|(score[3]<<24)) % c->hashSize;
- /*
- * look for the block in the cache
- */
- vtLock(c->lk);
- for(b = c->heads[h]; b != nil; b = b->next){
- if(b->part != PartVenti || memcmp(b->score, score, VtScoreSize) != 0 || b->l.type != type)
- continue;
- heapDel(b);
- b->ref++;
- break;
- }
- if(b == nil){
- if(0)fprint(2, "cacheGlobal %V %d\n", score, type);
- b = cacheBumpBlock(c);
- b->part = PartVenti;
- b->addr = NilBlock;
- b->l.type = type;
- memmove(b->score, score, VtScoreSize);
- /* chain onto correct hash */
- b->next = c->heads[h];
- c->heads[h] = b;
- if(b->next != nil)
- b->next->prev = &b->next;
- b->prev = &c->heads[h];
- }
- vtUnlock(c->lk);
- bwatchLock(b);
- vtLock(b->lk);
- b->nlock = 1;
- b->pc = getcallerpc(&c);
- switch(b->iostate){
- default:
- abort();
- case BioEmpty:
- n = vtRead(c->z, score, vtType[type], b->data, c->size);
- if(n < 0 || !vtSha1Check(score, b->data, n)){
- blockSetIOState(b, BioVentiError);
- blockPut(b);
- vtSetError(
- "venti error reading block %V or wrong score: %r",
- score);
- return nil;
- }
- vtZeroExtend(vtType[type], b->data, n, c->size);
- blockSetIOState(b, BioClean);
- return b;
- case BioClean:
- return b;
- case BioVentiError:
- blockPut(b);
- vtSetError("venti i/o error or wrong score, block %V", score);
- return nil;
- case BioReadError:
- blockPut(b);
- vtSetError("error reading block %V", b->score);
- return nil;
- }
- /* NOT REACHED */
- }
- /*
- * allocate a new on-disk block and load it into the memory cache.
- * BUG: if the disk is full, should we flush some of it to Venti?
- */
- static u32int lastAlloc;
- Block *
- cacheAllocBlock(Cache *c, int type, u32int tag, u32int epoch, u32int epochLow)
- {
- FreeList *fl;
- u32int addr;
- Block *b;
- int n, nwrap;
- Label lab;
- n = c->size / LabelSize;
- fl = c->fl;
- vtLock(fl->lk);
- addr = fl->last;
- b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
- if(b == nil){
- fprint(2, "cacheAllocBlock: xxx %R\n");
- vtUnlock(fl->lk);
- return nil;
- }
- nwrap = 0;
- for(;;){
- if(++addr >= fl->end){
- addr = 0;
- if(++nwrap >= 2){
- blockPut(b);
- fl->last = 0;
- vtSetError("disk is full");
- fprint(2, "cacheAllocBlock: xxx1 %R\n");
- vtUnlock(fl->lk);
- return nil;
- }
- }
- if(addr%n == 0){
- blockPut(b);
- b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
- if(b == nil){
- fl->last = addr;
- fprint(2, "cacheAllocBlock: xxx2 %R\n");
- vtUnlock(fl->lk);
- return nil;
- }
- }
- if(!labelUnpack(&lab, b->data, addr%n))
- continue;
- if(lab.state == BsFree)
- goto Found;
- if(lab.state&BsClosed)
- if(lab.epochClose <= epochLow || lab.epoch==lab.epochClose)
- goto Found;
- }
- Found:
- blockPut(b);
- b = cacheLocal(c, PartData, addr, OOverWrite);
- if(b == nil){
- fprint(2, "cacheAllocBlock: xxx3 %R\n");
- return nil;
- }
- assert(b->iostate == BioLabel || b->iostate == BioClean);
- fl->last = addr;
- lab.type = type;
- lab.tag = tag;
- lab.state = BsAlloc;
- lab.epoch = epoch;
- lab.epochClose = ~(u32int)0;
- if(!blockSetLabel(b, &lab, 1)){
- fprint(2, "cacheAllocBlock: xxx4 %R\n");
- blockPut(b);
- return nil;
- }
- vtZeroExtend(vtType[type], b->data, 0, c->size);
- if(0)diskWrite(c->disk, b);
- if(0)fprint(2, "fsAlloc %ud type=%d tag = %ux\n", addr, type, tag);
- lastAlloc = addr;
- fl->nused++;
- vtUnlock(fl->lk);
- b->pc = getcallerpc(&c);
- return b;
- }
- int
- cacheDirty(Cache *c)
- {
- return c->ndirty;
- }
- void
- cacheCountUsed(Cache *c, u32int epochLow, u32int *used, u32int *total, u32int *bsize)
- {
- int n;
- u32int addr, nused;
- Block *b;
- Label lab;
- FreeList *fl;
- fl = c->fl;
- n = c->size / LabelSize;
- *bsize = c->size;
- vtLock(fl->lk);
- if(fl->epochLow == epochLow){
- *used = fl->nused;
- *total = fl->end;
- vtUnlock(fl->lk);
- return;
- }
- b = nil;
- nused = 0;
- for(addr=0; addr<fl->end; addr++){
- if(addr%n == 0){
- blockPut(b);
- b = cacheLocal(c, PartLabel, addr/n, OReadOnly);
- if(b == nil){
- fprint(2, "flCountUsed: loading %ux: %R\n", addr/n);
- break;
- }
- }
- if(!labelUnpack(&lab, b->data, addr%n))
- continue;
- if(lab.state == BsFree)
- continue;
- if(lab.state&BsClosed)
- if(lab.epochClose <= epochLow || lab.epoch==lab.epochClose)
- continue;
- nused++;
- }
- blockPut(b);
- if(addr == fl->end){
- fl->nused = nused;
- fl->epochLow = epochLow;
- }
- *used = nused;
- *total = fl->end;
- vtUnlock(fl->lk);
- return;
- }
- static FreeList *
- flAlloc(u32int end)
- {
- FreeList *fl;
- fl = vtMemAllocZ(sizeof(*fl));
- fl->lk = vtLockAlloc();
- fl->last = 0;
- fl->end = end;
- return fl;
- }
- static void
- flFree(FreeList *fl)
- {
- vtLockFree(fl->lk);
- vtMemFree(fl);
- }
- u32int
- cacheLocalSize(Cache *c, int part)
- {
- return diskSize(c->disk, part);
- }
- /*
- * The thread that has locked b may refer to it by
- * multiple names. Nlock counts the number of
- * references the locking thread holds. It will call
- * blockPut once per reference.
- */
- void
- blockDupLock(Block *b)
- {
- assert(b->nlock > 0);
- b->nlock++;
- }
- /*
- * we're done with the block.
- * unlock it. can't use it after calling this.
- */
- void
- blockPut(Block* b)
- {
- Cache *c;
- if(b == nil)
- return;
- if(0)fprint(2, "blockPut: %d: %d %x %d %s\n", getpid(), b->part, b->addr, c->nheap, bioStr(b->iostate));
- if(b->iostate == BioDirty)
- bwatchDependency(b);
- if(--b->nlock > 0)
- return;
- /*
- * b->nlock should probably stay at zero while
- * the block is unlocked, but diskThread and vtSleep
- * conspire to assume that they can just vtLock(b->lk); blockPut(b),
- * so we have to keep b->nlock set to 1 even
- * when the block is unlocked.
- */
- assert(b->nlock == 0);
- b->nlock = 1;
- // b->pc = 0;
- bwatchUnlock(b);
- vtUnlock(b->lk);
- c = b->c;
- vtLock(c->lk);
- if(--b->ref > 0){
- vtUnlock(c->lk);
- return;
- }
- assert(b->ref == 0);
- switch(b->iostate){
- default:
- b->used = c->now++;
- heapIns(b);
- break;
- case BioEmpty:
- case BioLabel:
- if(c->nheap == 0)
- b->used = c->now++;
- else
- b->used = c->heap[0]->used;
- heapIns(b);
- break;
- case BioDirty:
- break;
- }
- vtUnlock(c->lk);
- }
- /*
- * set the label associated with a block.
- */
- Block*
- _blockSetLabel(Block *b, Label *l)
- {
- int lpb;
- Block *bb;
- u32int a;
- Cache *c;
- c = b->c;
- assert(b->part == PartData);
- assert(b->iostate == BioLabel || b->iostate == BioClean || b->iostate == BioDirty);
- lpb = c->size / LabelSize;
- a = b->addr / lpb;
- bb = cacheLocal(c, PartLabel, a, OReadWrite);
- if(bb == nil){
- blockPut(b);
- return nil;
- }
- b->l = *l;
- labelPack(l, bb->data, b->addr%lpb);
- blockDirty(bb);
- return bb;
- }
- int
- blockSetLabel(Block *b, Label *l, int allocating)
- {
- Block *lb;
- Label oldl;
- oldl = b->l;
- lb = _blockSetLabel(b, l);
- if(lb == nil)
- return 0;
- /*
- * If we're allocating the block, make sure the label (bl)
- * goes to disk before the data block (b) itself. This is to help
- * the blocks that in turn depend on b.
- *
- * Suppose bx depends on (must be written out after) b.
- * Once we write b we'll think it's safe to write bx.
- * Bx can't get at b unless it has a valid label, though.
- *
- * Allocation is the only case in which having a current label
- * is vital because:
- *
- * - l.type is set at allocation and never changes.
- * - l.tag is set at allocation and never changes.
- * - l.state is not checked when we load blocks.
- * - the archiver cares deeply about l.state being
- * BaActive vs. BaCopied, but that's handled
- * by direct calls to _blockSetLabel.
- */
- if(allocating)
- blockDependency(b, lb, -1, nil, nil);
- blockPut(lb);
- return 1;
- }
- /*
- * Record that bb must be written out before b.
- * If index is given, we're about to overwrite the score/e
- * at that index in the block. Save the old value so we
- * can write a safer ``old'' version of the block if pressed.
- */
- void
- blockDependency(Block *b, Block *bb, int index, uchar *score, Entry *e)
- {
- BList *p;
- if(bb->iostate == BioClean)
- return;
- /*
- * Dependencies for blocks containing Entry structures
- * or scores must always be explained. The problem with
- * only explaining some of them is this. Suppose we have two
- * dependencies for the same field, the first explained
- * and the second not. We try to write the block when the first
- * dependency is not written but the second is. We will roll back
- * the first change even though the second trumps it.
- */
- if(index == -1 && bb->part == PartData)
- assert(b->l.type == BtData);
- if(bb->iostate != BioDirty){
- fprint(2, "%d:%x:%d iostate is %d in blockDependency\n",
- bb->part, bb->addr, bb->l.type, bb->iostate);
- abort();
- }
- p = blistAlloc(bb);
- if(p == nil)
- return;
- assert(bb->iostate == BioDirty);
- if(0)fprint(2, "%d:%x:%d depends on %d:%x:%d\n", b->part, b->addr, b->l.type, bb->part, bb->addr, bb->l.type);
- p->part = bb->part;
- p->addr = bb->addr;
- p->type = bb->l.type;
- p->vers = bb->vers;
- p->index = index;
- if(p->index >= 0){
- /*
- * This test would just be b->l.type==BtDir except
- * we need to exclude the super block.
- */
- if(b->l.type == BtDir && b->part == PartData)
- entryPack(e, p->old.entry, 0);
- else
- memmove(p->old.score, score, VtScoreSize);
- }
- p->next = b->prior;
- b->prior = p;
- }
- /*
- * Mark an in-memory block as dirty. If there are too many
- * dirty blocks, start writing some out to disk.
- *
- * If there were way too many dirty blocks, we used to
- * try to do some flushing ourselves, but it's just too dangerous --
- * it implies that the callers cannot have any of our priors locked,
- * but this is hard to avoid in some cases.
- */
- int
- blockDirty(Block *b)
- {
- Cache *c;
- c = b->c;
- assert(b->part != PartVenti);
- if(b->iostate == BioDirty)
- return 1;
- assert(b->iostate == BioClean);
- vtLock(c->dirtylk);
- vtLock(c->lk);
- b->iostate = BioDirty;
- c->ndirty++;
- if(c->ndirty > (c->maxdirty>>1))
- vtWakeup(c->flush);
- vtUnlock(c->lk);
- vtUnlock(c->dirtylk);
- return 1;
- }
- /*
- * We've decided to write out b. Maybe b has some pointers to blocks
- * that haven't yet been written to disk. If so, construct a slightly out-of-date
- * copy of b that is safe to write out. (diskThread will make sure the block
- * remains marked as dirty.)
- */
- uchar *
- blockRollback(Block *b, uchar *buf)
- {
- u32int addr;
- BList *p;
- Super super;
- /* easy case */
- if(b->prior == nil)
- return b->data;
- memmove(buf, b->data, b->c->size);
- for(p=b->prior; p; p=p->next){
- /*
- * we know p->index >= 0 because blockWrite has vetted this block for us.
- */
- assert(p->index >= 0);
- assert(b->part == PartSuper || (b->part == PartData && b->l.type != BtData));
- if(b->part == PartSuper){
- assert(p->index == 0);
- superUnpack(&super, buf);
- addr = globalToLocal(p->old.score);
- if(addr == NilBlock){
- fprint(2, "rolling back super block: bad replacement addr %V\n", p->old.score);
- abort();
- }
- super.active = addr;
- superPack(&super, buf);
- continue;
- }
- if(b->l.type == BtDir)
- memmove(buf+p->index*VtEntrySize, p->old.entry, VtEntrySize);
- else
- memmove(buf+p->index*VtScoreSize, p->old.score, VtScoreSize);
- }
- return buf;
- }
- /*
- * Try to write block b.
- * If b depends on other blocks:
- *
- * If the block has been written out, remove the dependency.
- * If the dependency is replaced by a more recent dependency,
- * throw it out.
- * If we know how to write out an old version of b that doesn't
- * depend on it, do that.
- *
- * Otherwise, bail.
- */
- int
- blockWrite(Block *b)
- {
- uchar *dmap;
- Cache *c;
- BList *p, **pp;
- Block *bb;
- int lockfail;
- c = b->c;
- if(b->iostate != BioDirty)
- return 1;
- dmap = b->dmap;
- memset(dmap, 0, c->ndmap);
- pp = &b->prior;
- for(p=*pp; p; p=*pp){
- if(p->index >= 0){
- /* more recent dependency has succeeded; this one can go */
- if(dmap[p->index/8] & (1<<(p->index%8)))
- goto ignblock;
- }
- lockfail = 0;
- bb = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
- if(bb == nil){
- if(lockfail)
- return 0;
- /* block not in cache => was written already */
- dmap[p->index/8] |= 1<<(p->index%8);
- goto ignblock;
- }
- /*
- * same version of block is still in cache.
- *
- * the assertion is true because the block still has version p->vers,
- * which means it hasn't been written out since we last saw it.
- */
- if(bb->iostate != BioDirty){
- fprint(2, "%d:%x:%d iostate is %d in blockWrite\n",
- bb->part, bb->addr, bb->l.type, bb->iostate);
- /* probably BioWriting if it happens? */
- if(bb->iostate == BioClean)
- goto ignblock;
- }
- blockPut(bb);
- if(p->index < 0){
- /*
- * We don't know how to temporarily undo
- * b's dependency on bb, so just don't write b yet.
- */
- if(0) fprint(2, "blockWrite skipping %d %x %d %d; need to write %d %x %d\n",
- b->part, b->addr, b->vers, b->l.type, p->part, p->addr, bb->vers);
- return 0;
- }
- /* keep walking down the list */
- pp = &p->next;
- continue;
- ignblock:
- *pp = p->next;
- blistFree(c, p);
- continue;
- }
- /*
- * DiskWrite must never be called with a double-locked block.
- * This call to diskWrite is okay because blockWrite is only called
- * from the cache flush thread, which never double-locks a block.
- */
- diskWrite(c->disk, b);
- return 1;
- }
- /*
- * Change the I/O state of block b.
- * Just an assignment except for magic in
- * switch statement (read comments there).
- */
- void
- blockSetIOState(Block *b, int iostate)
- {
- int dowakeup;
- Cache *c;
- BList *p, *q;
- if(0) fprint(2, "iostate part=%d addr=%x %s->%s\n", b->part, b->addr, bioStr(b->iostate), bioStr(iostate));
- c = b->c;
- dowakeup = 0;
- switch(iostate){
- default:
- abort();
- case BioEmpty:
- assert(!b->uhead);
- break;
- case BioLabel:
- assert(!b->uhead);
- break;
- case BioClean:
- bwatchDependency(b);
- /*
- * If b->prior is set, it means a write just finished.
- * The prior list isn't needed anymore.
- */
- for(p=b->prior; p; p=q){
- q = p->next;
- blistFree(c, p);
- }
- b->prior = nil;
- /*
- * Freeing a block or just finished a write.
- * Move the blocks from the per-block unlink
- * queue to the cache unlink queue.
- */
- if(b->iostate == BioDirty || b->iostate == BioWriting){
- vtLock(c->lk);
- c->ndirty--;
- b->iostate = iostate; /* change here to keep in sync with ndirty */
- b->vers = c->vers++;
- if(b->uhead){
- /* add unlink blocks to unlink queue */
- if(c->uhead == nil){
- c->uhead = b->uhead;
- vtWakeup(c->unlink);
- }else
- c->utail->next = b->uhead;
- c->utail = b->utail;
- b->uhead = nil;
- }
- vtUnlock(c->lk);
- }
- assert(!b->uhead);
- dowakeup = 1;
- break;
- case BioDirty:
- /*
- * Wrote out an old version of the block (see blockRollback).
- * Bump a version count, leave it dirty.
- */
- if(b->iostate == BioWriting){
- vtLock(c->lk);
- b->vers = c->vers++;
- vtUnlock(c->lk);
- dowakeup = 1;
- }
- break;
- case BioReading:
- case BioWriting:
- /*
- * Adding block to disk queue. Bump reference count.
- * diskThread decs the count later by calling blockPut.
- * This is here because we need to lock c->lk to
- * manipulate the ref count.
- */
- vtLock(c->lk);
- b->ref++;
- vtUnlock(c->lk);
- break;
- case BioReadError:
- case BioVentiError:
- /*
- * Oops.
- */
- dowakeup = 1;
- break;
- }
- b->iostate = iostate;
- /*
- * Now that the state has changed, we can wake the waiters.
- */
- if(dowakeup)
- vtWakeupAll(b->ioready);
- }
- /*
- * The active file system is a tree of blocks.
- * When we add snapshots to the mix, the entire file system
- * becomes a dag and thus requires a bit more care.
- *
- * The life of the file system is divided into epochs. A snapshot
- * ends one epoch and begins the next. Each file system block
- * is marked with the epoch in which it was created (b.epoch).
- * When the block is unlinked from the file system (closed), it is marked
- * with the epoch in which it was removed (b.epochClose).
- * Once we have discarded or archived all snapshots up to
- * b.epochClose, we can reclaim the block.
- *
- * If a block was created in a past epoch but is not yet closed,
- * it is treated as copy-on-write. Of course, in order to insert the
- * new pointer into the tree, the parent must be made writable,
- * and so on up the tree. The recursion stops because the root
- * block is always writable.
- *
- * If blocks are never closed, they will never be reused, and
- * we will run out of disk space. But marking a block as closed
- * requires some care about dependencies and write orderings.
- *
- * (1) If a block p points at a copy-on-write block b and we
- * copy b to create bb, then p must be written out after bb and
- * lbb (bb's label block).
- *
- * (2) We have to mark b as closed, but only after we switch
- * the pointer, so lb must be written out after p. In fact, we
- * can't even update the in-memory copy, or the cache might
- * mistakenly give out b for reuse before p gets written.
- *
- * CacheAllocBlock's call to blockSetLabel records a "bb after lbb" dependency.
- * The caller is expected to record a "p after bb" dependency
- * to finish (1), and also expected to call blockRemoveLink
- * to arrange for (2) to happen once p is written.
- *
- * Until (2) happens, some pieces of the code (e.g., the archiver)
- * still need to know whether a block has been copied, so we
- * set the BsCopied bit in the label and force that to disk *before*
- * the copy gets written out.
- */
- Block*
- blockCopy(Block *b, u32int tag, u32int ehi, u32int elo)
- {
- Block *bb, *lb;
- Label l;
- if((b->l.state&BsClosed) || b->l.epoch >= ehi)
- fprint(2, "blockCopy %#ux %L but fs is [%ud,%ud]\n",
- b->addr, &b->l, elo, ehi);
- bb = cacheAllocBlock(b->c, b->l.type, tag, ehi, elo);
- if(bb == nil){
- blockPut(b);
- return nil;
- }
- /*
- * Update label so we know the block has been copied.
- * (It will be marked closed once it has been unlinked from
- * the tree.) This must follow cacheAllocBlock since we
- * can't be holding onto lb when we call cacheAllocBlock.
- */
- if((b->l.state&BsCopied)==0)
- if(b->part == PartData){ /* not the superblock */
- l = b->l;
- l.state |= BsCopied;
- lb = _blockSetLabel(b, &l);
- if(lb == nil){
- /* can't set label => can't copy block */
- blockPut(b);
- l.type = BtMax;
- l.state = BsFree;
- l.epoch = 0;
- l.epochClose = 0;
- l.tag = 0;
- blockSetLabel(bb, &l, 0);
- blockPut(bb);
- return nil;
- }
- blockDependency(bb, lb, -1, nil, nil);
- blockPut(lb);
- }
- memmove(bb->data, b->data, b->c->size);
- blockDirty(bb);
- blockPut(b);
- return bb;
- }
- /*
- * Block b once pointed at the block bb at addr/type/tag, but no longer does.
- * If recurse is set, we are unlinking all of bb's children as well.
- *
- * We can't reclaim bb (or its kids) until the block b gets written to disk. We add
- * the relevant information to b's list of unlinked blocks. Once b is written,
- * the list will be queued for processing.
- *
- * If b depends on bb, it doesn't anymore, so we remove bb from the prior list.
- */
- void
- blockRemoveLink(Block *b, u32int addr, int type, u32int tag, int recurse)
- {
- BList *p, **pp, bl;
-
- /* remove bb from prior list */
- for(pp=&b->prior; (p=*pp)!=nil; ){
- if(p->part == PartData && p->addr == addr){
- *pp = p->next;
- blistFree(b->c, p);
- }else
- pp = &p->next;
- }
- bl.part = PartData;
- bl.addr = addr;
- bl.type = type;
- bl.tag = tag;
- if(b->l.epoch == 0)
- assert(b->part == PartSuper);
- bl.epoch = b->l.epoch;
- bl.next = nil;
- bl.recurse = recurse;
- p = blistAlloc(b);
- if(p == nil){
- /*
- * We were out of blists so blistAlloc wrote b to disk.
- */
- doRemoveLink(b->c, &bl);
- return;
- }
- /* Uhead is only processed when the block goes from Dirty -> Clean */
- assert(b->iostate == BioDirty);
- *p = bl;
- if(b->uhead == nil)
- b->uhead = p;
- else
- b->utail->next = p;
- b->utail = p;
- }
- /*
- * Process removal of a single block and perhaps its children.
- */
- static void
- doRemoveLink(Cache *c, BList *p)
- {
- int i, n, recurse;
- u32int a;
- Block *b;
- Label l;
- BList bl;
- recurse = (p->recurse && p->type != BtData && p->type != BtDir);
- /*
- * We're not really going to overwrite b, but if we're not
- * going to look at its contents, there is no point in reading
- * them from the disk.
- */
- b = cacheLocalData(c, p->addr, p->type, p->tag, recurse ? OReadOnly : OOverWrite, 0);
- if(b == nil)
- return;
- /*
- * When we're unlinking from the superblock, close with the next epoch.
- */
- if(p->epoch == 0)
- p->epoch = b->l.epoch+1;
- /* sanity check */
- if(b->l.epoch > p->epoch){
- fprint(2, "doRemoveLink: strange epoch %ud > %ud\n", b->l.epoch, p->epoch);
- blockPut(b);
- return;
- }
- if(recurse){
- n = c->size / VtScoreSize;
- for(i=0; i<n; i++){
- a = globalToLocal(b->data + i*VtScoreSize);
- if(a == NilBlock || !readLabel(c, &l, a))
- continue;
- if(l.state&BsClosed)
- continue;
- /*
- * If stack space becomes an issue...
- p->addr = a;
- p->type = l.type;
- p->tag = l.tag;
- doRemoveLink(c, p);
- */
- bl.part = PartData;
- bl.addr = a;
- bl.type = l.type;
- bl.tag = l.tag;
- bl.epoch = p->epoch;
- bl.next = nil;
- bl.recurse = 1;
- /* give up the block lock - share with others */
- blockPut(b);
- doRemoveLink(c, &bl);
- b = cacheLocalData(c, p->addr, p->type, p->tag, OReadOnly, 0);
- if(b == nil){
- fprint(2, "warning: lost block in doRemoveLink\n");
- return;
- }
- }
- }
- l = b->l;
- l.state |= BsClosed;
- l.epochClose = p->epoch;
- blockSetLabel(b, &l, 0);
- blockPut(b);
- }
- /*
- * Allocate a BList so that we can record a dependency
- * or queue a removal related to block b.
- * If we can't find a BList, we write out b and return nil.
- */
- static BList *
- blistAlloc(Block *b)
- {
- Cache *c;
- BList *p;
- if(b->iostate != BioDirty){
- /*
- * should not happen anymore -
- * blockDirty used to flush but no longer does.
- */
- assert(b->iostate == BioClean);
- fprint(2, "blistAlloc: called on clean block\n");
- return nil;
- }
- c = b->c;
- vtLock(c->lk);
- if(c->blfree == nil){
- /*
- * No free BLists. What are our options?
- */
-
- /* Block has no priors? Just write it. */
- if(b->prior == nil){
- vtUnlock(c->lk);
- diskWriteAndWait(c->disk, b);
- return nil;
- }
- /*
- * Wake the flush thread, which will hopefully free up
- * some BLists for us. We used to flush a block from
- * our own prior list and reclaim that BList, but this is
- * a no-no: some of the blocks on our prior list may
- * be locked by our caller. Or maybe their label blocks
- * are locked by our caller. In any event, it's too hard
- * to make sure we can do I/O for ourselves. Instead,
- * we assume the flush thread will find something.
- * (The flush thread never blocks waiting for a block,
- * so it can't deadlock like we can.)
- */
- vtLock(c->lk);
- while(c->blfree == nil){
- vtWakeup(c->flush);
- vtSleep(c->blrend);
- if(c->blfree == nil)
- fprint(2, "flushing for blists\n");
- }
- }
- p = c->blfree;
- c->blfree = p->next;
- vtUnlock(c->lk);
- return p;
- }
- static void
- blistFree(Cache *c, BList *bl)
- {
- vtLock(c->lk);
- bl->next = c->blfree;
- c->blfree = bl;
- vtWakeup(c->blrend);
- vtUnlock(c->lk);
- }
- char*
- bsStr(int state)
- {
- static char s[100];
- if(state == BsFree)
- return "Free";
- if(state == BsBad)
- return "Bad";
- sprint(s, "%x", state);
- if(!(state&BsAlloc))
- strcat(s, ",Free"); /* should not happen */
- if(state&BsCopied)
- strcat(s, ",Copied");
- if(state&BsVenti)
- strcat(s, ",Venti");
- if(state&BsClosed)
- strcat(s, ",Closed");
- return s;
- }
- char *
- bioStr(int iostate)
- {
- switch(iostate){
- default:
- return "Unknown!!";
- case BioEmpty:
- return "Empty";
- case BioLabel:
- return "Label";
- case BioClean:
- return "Clean";
- case BioDirty:
- return "Dirty";
- case BioReading:
- return "Reading";
- case BioWriting:
- return "Writing";
- case BioReadError:
- return "ReadError";
- case BioVentiError:
- return "VentiError";
- case BioMax:
- return "Max";
- }
- }
- static char *bttab[] = {
- "BtData",
- "BtData+1",
- "BtData+2",
- "BtData+3",
- "BtData+4",
- "BtData+5",
- "BtData+6",
- "BtData+7",
- "BtDir",
- "BtDir+1",
- "BtDir+2",
- "BtDir+3",
- "BtDir+4",
- "BtDir+5",
- "BtDir+6",
- "BtDir+7",
- };
- char*
- btStr(int type)
- {
- if(type < nelem(bttab))
- return bttab[type];
- return "unknown";
- }
- int
- labelFmt(Fmt *f)
- {
- Label *l;
- l = va_arg(f->args, Label*);
- return fmtprint(f, "%s,%s,e=%ud,%d,tag=%#ux",
- btStr(l->type), bsStr(l->state), l->epoch, (int)l->epochClose, l->tag);
- }
- int
- scoreFmt(Fmt *f)
- {
- uchar *v;
- int i;
- u32int addr;
- v = va_arg(f->args, uchar*);
- if(v == nil){
- fmtprint(f, "*");
- }else if((addr = globalToLocal(v)) != NilBlock)
- fmtprint(f, "0x%.8ux", addr);
- else{
- for(i = 0; i < VtScoreSize; i++)
- fmtprint(f, "%2.2ux", v[i]);
- }
- return 0;
- }
- static int
- upHeap(int i, Block *b)
- {
- Block *bb;
- u32int now;
- int p;
- Cache *c;
- c = b->c;
- now = c->now;
- for(; i != 0; i = p){
- p = (i - 1) >> 1;
- bb = c->heap[p];
- if(b->used - now >= bb->used - now)
- break;
- c->heap[i] = bb;
- bb->heap = i;
- }
- c->heap[i] = b;
- b->heap = i;
- return i;
- }
- static int
- downHeap(int i, Block *b)
- {
- Block *bb;
- u32int now;
- int k;
- Cache *c;
- c = b->c;
- now = c->now;
- for(; ; i = k){
- k = (i << 1) + 1;
- if(k >= c->nheap)
- break;
- if(k + 1 < c->nheap && c->heap[k]->used - now > c->heap[k + 1]->used - now)
- k++;
- bb = c->heap[k];
- if(b->used - now <= bb->used - now)
- break;
- c->heap[i] = bb;
- bb->heap = i;
- }
- c->heap[i] = b;
- b->heap = i;
- return i;
- }
- /*
- * Delete a block from the heap.
- * Called with c->lk held.
- */
- static void
- heapDel(Block *b)
- {
- int i, si;
- Cache *c;
- c = b->c;
- si = b->heap;
- if(si == BadHeap)
- return;
- b->heap = BadHeap;
- c->nheap--;
- if(si == c->nheap)
- return;
- b = c->heap[c->nheap];
- i = upHeap(si, b);
- if(i == si)
- downHeap(i, b);
- }
- /*
- * Insert a block into the heap.
- * Called with c->lk held.
- */
- static void
- heapIns(Block *b)
- {
- assert(b->heap == BadHeap);
- upHeap(b->c->nheap++, b);
- vtWakeup(b->c->heapwait);
- }
- /*
- * Get just the label for a block.
- */
- int
- readLabel(Cache *c, Label *l, u32int addr)
- {
- int lpb;
- Block *b;
- u32int a;
- lpb = c->size / LabelSize;
- a = addr / lpb;
- b = cacheLocal(c, PartLabel, a, OReadOnly);
- if(b == nil){
- blockPut(b);
- return 0;
- }
- if(!labelUnpack(l, b->data, addr%lpb)){
- blockPut(b);
- return 0;
- }
- blockPut(b);
- return 1;
- }
- /*
- * Process unlink queue.
- * Called with c->lk held.
- */
- static void
- unlinkBody(Cache *c)
- {
- BList *p;
- while(c->uhead != nil){
- p = c->uhead;
- c->uhead = p->next;
- vtUnlock(c->lk);
- doRemoveLink(c, p);
- vtLock(c->lk);
- p->next = c->blfree;
- c->blfree = p;
- }
- }
- /*
- * Occasionally unlink the blocks on the cache unlink queue.
- */
- static void
- unlinkThread(void *a)
- {
- Cache *c = a;
- vtThreadSetName("unlink");
- vtLock(c->lk);
- for(;;){
- while(c->uhead == nil && c->die == nil)
- vtSleep(c->unlink);
- if(c->die != nil)
- break;
- unlinkBody(c);
- }
- c->ref--;
- vtWakeup(c->die);
- vtUnlock(c->lk);
- }
- static int
- baddrCmp(void *a0, void *a1)
- {
- BAddr *b0, *b1;
- b0 = a0;
- b1 = a1;
- if(b0->part < b1->part)
- return -1;
- if(b0->part > b1->part)
- return 1;
- if(b0->addr < b1->addr)
- return -1;
- if(b0->addr > b1->addr)
- return 1;
- return 0;
- }
- /*
- * Scan the block list for dirty blocks; add them to the list c->baddr.
- */
- static void
- flushFill(Cache *c)
- {
- int i, ndirty;
- BAddr *p;
- Block *b;
- vtLock(c->lk);
- if(c->ndirty == 0){
- vtUnlock(c->lk);
- return;
- }
- p = c->baddr;
- ndirty = 0;
- for(i=0; i<c->nblocks; i++){
- b = c->blocks + i;
- if(b->part == PartError)
- continue;
- if(b->iostate == BioDirty || b->iostate == BioWriting)
- ndirty++;
- if(b->iostate != BioDirty)
- continue;
- p->part = b->part;
- p->addr = b->addr;
- p->vers = b->vers;
- p++;
- }
- if(ndirty != c->ndirty){
- fprint(2, "ndirty mismatch expected %d found %d\n",
- c->ndirty, ndirty);
- c->ndirty = ndirty;
- }
- vtUnlock(c->lk);
- c->bw = p - c->baddr;
- qsort(c->baddr, c->bw, sizeof(BAddr), baddrCmp);
- }
- /*
- * This is not thread safe, i.e. it can't be called from multiple threads.
- *
- * It's okay how we use it, because it only gets called in
- * the flushThread. And cacheFree, but only after
- * cacheFree has killed off the flushThread.
- */
- static int
- cacheFlushBlock(Cache *c)
- {
- Block *b;
- BAddr *p;
- int lockfail, nfail;
- nfail = 0;
- for(;;){
- if(c->br == c->be){
- if(c->bw == 0 || c->bw == c->be)
- flushFill(c);
- c->br = 0;
- c->be = c->bw;
- c->bw = 0;
- c->nflush = 0;
- }
- if(c->br == c->be)
- return 0;
- p = c->baddr + c->br;
- c->br++;
- b = _cacheLocalLookup(c, p->part, p->addr, p->vers, 0, &lockfail);
- if(b && blockWrite(b)){
- c->nflush++;
- blockPut(b);
- return 1;
- }
- if(b)
- blockPut(b);
- /*
- * Why didn't we write the block?
- */
- /* Block already written out */
- if(b == nil && !lockfail)
- continue;
- /* Failed to acquire lock; sleep if happens a lot. */
- if(lockfail && ++nfail > 100){
- sleep(500);
- nfail = 0;
- }
- /* Requeue block. */
- if(c->bw < c->be)
- c->baddr[c->bw++] = *p;
- }
- }
- /*
- * Occasionally flush dirty blocks from memory to the disk.
- */
- static void
- flushThread(void *a)
- {
- Cache *c = a;
- int i;
- vtThreadSetName("flush");
- vtLock(c->lk);
- while(c->die == nil){
- vtSleep(c->flush);
- vtUnlock(c->lk);
- for(i=0; i<FlushSize; i++)
- if(!cacheFlushBlock(c)){
- /*
- * If i==0, could be someone is waking us repeatedly
- * to flush the cache but there's no work to do.
- * Pause a little.
- */
- if(i==0){
- // fprint(2, "flushthread found nothing to flush - %d dirty\n", c->ndirty);
- sleep(250);
- }
- break;
- }
- if(i==0 && c->ndirty){
- /*
- * All the blocks are being written right now -- there's nothing to do.
- * We might be spinning with cacheFlush though -- he'll just keep
- * kicking us until c->ndirty goes down. Probably we should sleep
- * on something that the diskThread can kick, but for now we'll
- * just pause for a little while waiting for disks to finish.
- */
- sleep(100);
- }
- vtLock(c->lk);
- vtWakeupAll(c->flushwait);
- }
- c->ref--;
- vtWakeup(c->die);
- vtUnlock(c->lk);
- }
- /*
- * Flush the cache.
- */
- void
- cacheFlush(Cache *c, int wait)
- {
- /*
- * Lock c->dirtylk so that more blocks aren't being dirtied
- * while we try to write out what's already here.
- * Otherwise we might not ever finish!
- */
- vtLock(c->dirtylk);
- vtLock(c->lk);
- if(wait){
- while(c->ndirty){
- // consPrint("cacheFlush: %d dirty blocks, uhead %p\n",
- // c->ndirty, c->uhead);
- vtWakeup(c->flush);
- vtSleep(c->flushwait);
- }
- // consPrint("cacheFlush: done (uhead %p)\n", c->ndirty, c->uhead);
- }else if(c->ndirty)
- vtWakeup(c->flush);
- vtUnlock(c->lk);
- vtUnlock(c->dirtylk);
- }
- /*
- * Kick the flushThread every 30 seconds.
- */
- static void
- cacheSync(void *v)
- {
- Cache *c;
- c = v;
- cacheFlush(c, 0);
- }
|