cache.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

	 * (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);
}