cw.c

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

		return 0;
	nfs = fs + ADDFREE;
	if(nfs >= ws)
		nfs = ws;
	h->fsize = nfs;
	putbuf(cb);

	sb->fsize = nfs;
	filsys = dev2fs(dev);
	if (filsys == nil)
		print("%Z", dev);
	else
		print("%s", filsys->name);
	uidtostr(str, uid, 1);
	print(" grow from %lld to %lld limit %lld by %s uid=%d\n",
		(Wideoff)fs, (Wideoff)nfs, (Wideoff)ws, str, uid);
	for(nfs--; nfs>=fs; nfs--) {
		switch(cwio(dev, nfs, 0, Ogrow)) {
		case Cerror:
			return 0;
		case Cnone:
			addfree(dev, nfs, sb);
		}
	}
	return 1;
}

int
cwfree(Device *dev, Off addr)
{
	int state;

	if(dev->type == Devcw) {
		state = cwio(dev, addr, 0, Ofree);
		if(state != Cdirty)
			return 1;	/* do not put in freelist */
	}
	return 0;			/* put in freelist */
}

int
bktcheck(Bucket *b)
{
	Centry *c, *c1, *c2, *ce;
	int err;

	err = 0;
	if(b->agegen < CEPERBK || b->agegen > MAXAGE) {
		print("agegen %ld\n", b->agegen);
		err = 1;
	}

	ce = b->entry + CEPERBK;
	c1 = 0;		/* lowest age last pass */
	for(;;) {
		c2 = 0;		/* lowest age this pass */
		for(c = b->entry; c < ce; c++) {
			if(c1 != 0 && c != c1) {
				if(c->age == c1->age) {
					print("same age %d\n", c->age);
					err = 1;
				}
				if(c1->waddr == c->waddr)
				if(c1->state != Cnone)
				if(c->state != Cnone) {
					print("same waddr %lld\n", (Wideoff)c->waddr);
					err = 1;
				}
			}
			if(c1 != 0 && c->age <= c1->age)
				continue;
			if(c2 == 0 || c->age < c2->age)
				c2 = c;
		}
		if(c2 == 0)
			break;
		c1 = c2;
		if(c1->age >= b->agegen) {
			print("age >= generator %d %ld\n", c1->age, b->agegen);
			err = 1;
		}
	}
	return err;
}

void
resequence(Bucket *b)
{
	Centry *c, *ce, *cr;
	int age, i;

	ce = b->entry + CEPERBK;
	for(c = b->entry; c < ce; c++) {
		c->age += CEPERBK;
		if(c->age < CEPERBK)
			c->age = MAXAGE;
	}
	b->agegen += CEPERBK;

	age = 0;
	for(i=0;; i++) {
		cr = 0;
		for(c = b->entry; c < ce; c++) {
			if(c->age < i)
				continue;
			if(cr == 0 || c->age < age) {
				cr = c;
				age = c->age;
			}
		}
		if(cr == 0)
			break;
		cr->age = i;
	}
	b->agegen = i;
	cons.nreseq++;
}

Centry*
getcentry(Bucket *b, Off addr)
{
	Centry *c, *ce, *cr;
	int s, age;

	/*
	 * search for cache hit
	 * find oldest block as byproduct
	 */
	ce = b->entry + CEPERBK;
	age = 0;
	cr = 0;
	for(c = b->entry; c < ce; c++) {
		s = c->state;
		if(s == Cnone) {
			cr = c;
			age = 0;
			continue;
		}
		if(c->waddr == addr)
			goto found;
		if(s == Cread) {
			if(cr == 0 || c->age < age) {
				cr = c;
				age = c->age;
			}
		}
	}

	/*
	 * remap entry
	 */
	c = cr;
	if(c == 0)
		return 0;	/* bucket is full */

	c->state = Cnone;
	c->waddr = addr;

found:
	/*
	 * update the age to get filo cache.
	 * small number in age means old
	 */
	if(!cons.noage || c->state == Cnone) {
		age = b->agegen;
		c->age = age;
		age++;
		b->agegen = age;
		if(age < 0 || age >= MAXAGE)
			resequence(b);
	}
	return c;
}

/*
 * ream the cache
 * calculate new buckets
 */
Iobuf*
cacheinit(Device *dev)
{
	Iobuf *cb, *p;
	Cache *h;
	Device *cdev;
	Off m;

	print("cache init %Z\n", dev);
	cdev = CDEV(dev);
	devinit(cdev);

	cb = getbuf(cdev, CACHE_ADDR, Bmod|Bres);
	memset(cb->iobuf, 0, RBUFSIZE);
	settag(cb, Tcache, QPSUPER);
	h = (Cache*)cb->iobuf;

	/*
	 * calculate csize such that
	 * tsize = msize/BKPERBLK + csize and
	 * msize = csize/CEPERBK
	 */
	h->maddr = CACHE_ADDR + 1;
	m = devsize(cdev) - h->maddr;
	h->csize = ((Devsize)(m-1) * CEPERBK*BKPERBLK) / (CEPERBK*BKPERBLK+1);
	h->msize = h->csize/CEPERBK - 5;
	while(!prime(h->msize))
		h->msize--;
	h->csize = h->msize*CEPERBK;
	h->caddr = h->maddr + (h->msize+BKPERBLK-1)/BKPERBLK;
	h->wsize = devsize(WDEV(dev));

	if(h->msize <= 0)
		panic("cache too small");
	if(h->caddr + h->csize > m)
		panic("cache size error");

	/*
	 * setup cache map
	 */
	for(m=h->maddr; m<h->caddr; m++) {
		p = getbuf(cdev, m, Bmod);
		memset(p->iobuf, 0, RBUFSIZE);
		settag(p, Tbuck, m);
		putbuf(p);
	}
	print("done cacheinit\n");
	return cb;
}

Off
getstartsb(Device *dev)
{
	Filsys *f;
	Startsb *s;

	for(f=filsys; f->name; f++)
		if(devcmpr(f->dev, dev) == 0) {
			for(s=startsb; s->name; s++)
				if(strcmp(f->name, s->name) == 0)
					return s->startsb;
print("getstartsb: no special starting superblock for %Z %s\n", dev, f->name);
			return FIRST;
		}
print("getstartsb: no filsys for device %Z\n", dev);
	return FIRST;
}

/*
 * ream the cache
 * calculate new buckets
 * get superblock from
 * last worm dump block.
 */
void
cwrecover(Device *dev)
{
	Iobuf *p, *cb;
	Cache *h;
	Superb *s;
	Off m, baddr;
	Device *wdev;

	cwinit1(dev);
	wdev = WDEV(dev);

	p = getbuf(devnone, Cwxx1, 0);
	s = (Superb*)p->iobuf;
	baddr = 0;
	m = getstartsb(dev);
	localconfinit();
	if(conf.firstsb)
		m = conf.firstsb;
	for(;;) {
		memset(p->iobuf, 0, RBUFSIZE);
		if(devread(wdev, m, p->iobuf) ||
		   checktag(p, Tsuper, QPSUPER))
			break;
		baddr = m;
		m = s->next;
		print("dump %lld is good; %lld next\n", (Wideoff)baddr, (Wideoff)m);
		if(baddr == conf.recovsb)
			break;
	}
	putbuf(p);
	if(!baddr)
		panic("recover: no superblock\n");

	p = getbuf(wdev, baddr, Bread);
	s = (Superb*)p->iobuf;

	cb = cacheinit(dev);
	h = (Cache*)cb->iobuf;
	h->sbaddr = baddr;
	h->cwraddr = s->cwraddr;
	h->roraddr = s->roraddr;
	h->fsize = s->fsize + 100;		/* this must be conservative */
	if(conf.recovcw)
		h->cwraddr = conf.recovcw;
	if(conf.recovro)
		h->roraddr = conf.recovro;

	putbuf(cb);
	putbuf(p);

	p = getbuf(dev, baddr, Bread|Bmod);
	s = (Superb*)p->iobuf;
/* TODO: check s->magic byte order, arrange autoswabbing */

	memset(&s->fbuf, 0, sizeof(s->fbuf));
	s->fbuf.free[0] = 0;
	s->fbuf.nfree = 1;
	s->tfree = 0;
	if(conf.recovcw)
		s->cwraddr = conf.recovcw;
	if(conf.recovro)
		s->roraddr = conf.recovro;

	putbuf(p);
	print("done recover\n");
}

/*
 * ream the cache
 * calculate new buckets
 * initialize superblock.
 */
void
cwream(Device *dev)
{
	Iobuf *p, *cb;
	Cache *h;
	Superb *s;
	Off m, baddr;
	Device *cdev;

	print("cwream %Z\n", dev);
	cwinit1(dev);
	cdev = CDEV(dev);
	devinit(cdev);

	baddr = FIRST;	/*	baddr   = super addr
				baddr+1 = cw root
				baddr+2 = ro root
				baddr+3 = reserved next superblock */

	cb = cacheinit(dev);
	h = (Cache*)cb->iobuf;

	h->sbaddr = baddr;
	h->cwraddr = baddr+1;
	h->roraddr = baddr+2;
	h->fsize = 0;	/* prevents superream from freeing */

	putbuf(cb);

	for(m=0; m<3; m++)
		cwio(dev, baddr+m, 0, Ogrow);
	superream(dev, baddr);
	rootream(dev, baddr+1);			/* cw root */
	rootream(dev, baddr+2);			/* ro root */

	cb = getbuf(cdev, CACHE_ADDR, Bread|Bmod|Bres);
	h = (Cache*)cb->iobuf;
	h->fsize = baddr+4;
	putbuf(cb);

	p = getbuf(dev, baddr, Bread|Bmod|Bimm);
	s = (Superb*)p->iobuf;
	s->last = baddr;
	s->cwraddr = baddr+1;
	s->roraddr = baddr+2;
	s->next = baddr+3;
	s->fsize = baddr+4;
#ifdef AUTOSWAB
	s->magic = 0x123456789abcdef0;
#endif
	putbuf(p);

	for(m=0; m<3; m++)
		cwio(dev, baddr+m, 0, Odump);
}

Off
rewalk1(Cw *cw, Off addr, int slot, Wpath *up)
{
	Iobuf *p, *p1;
	Dentry *d;

	if(up == 0)
		return cwraddr(cw->dev);
	up->addr = rewalk1(cw, up->addr, up->slot, up->up);
	p = getbuf(cw->dev, up->addr, Bread|Bmod);
	d = getdir(p, up->slot);
	if(!d || !(d->mode & DALLOC)) {
		print("rewalk1 1\n");
		if(p)
			putbuf(p);
		return addr;
	}
	p1 = dnodebuf(p, d, slot/DIRPERBUF, 0, 0);
	if(!p1) {
		print("rewalk1 2\n");
		if(p)
			putbuf(p);
		return addr;
	}
	if(DEBUG)
		print("rewalk1 %lld to %lld \"%s\"\n",
			(Wideoff)addr, (Wideoff)p1->addr, d->name);
	addr = p1->addr;
	p1->flags |= Bmod;
	putbuf(p1);
	putbuf(p);
	return addr;
}

Off
rewalk2(Cw *cw, Off addr, int slot, Wpath *up)
{
	Iobuf *p, *p1;
	Dentry *d;

	if(up == 0)
		return cwraddr(cw->rodev);
	up->addr = rewalk2(cw, up->addr, up->slot, up->up);
	p = getbuf(cw->rodev, up->addr, Bread);
	d = getdir(p, up->slot);
	if(!d || !(d->mode & DALLOC)) {
		print("rewalk2 1\n");
		if(p)
			putbuf(p);
		return addr;
	}
	p1 = dnodebuf(p, d, slot/DIRPERBUF, 0, 0);
	if(!p1) {
		print("rewalk2 2\n");
		if(p)
			putbuf(p);
		return addr;
	}
	if(DEBUG)
		print("rewalk2 %lld to %lld \"%s\"\n",
			(Wideoff)addr, (Wideoff)p1->addr, d->name);
	addr = p1->addr;
	putbuf(p1);
	putbuf(p);
	return addr;
}

void
rewalk(Cw *cw)
{
	int h;
	File *f;

	for(h=0; h<nelem(flist); h++) {
		for(f=flist[h]; f; f=f->next) {
			if(!f->fs)
				continue;
			if(cw->dev == f->fs->dev)
				f->addr = rewalk1(cw, f->addr, f->slot, f->wpath);
			else
			if(cw->rodev == f->fs->dev)
				f->addr = rewalk2(cw, f->addr, f->slot, f->wpath);
		}
	}
}

Off
split(Cw *cw, Iobuf *p, Off addr)
{
	Off na;
	int state;

	na = 0;
	if(p && (p->flags & Bmod)) {
		p->flags |= Bimm;
		putbuf(p);
		p = 0;
	}
	state = cwio(cw->dev, addr, 0, Onone);	/* read the state (twice?) */
	switch(state)
	{
	default:
		panic("split: unknown state %s", cwnames[state]);

	case Cerror:
	case Cnone:
	case Cdump:
	case Cread:
		break;

	case Cdump1:
	case Cwrite:
		/*
		 * botch.. could be done by relabeling
		 */
		if(!p) {
			p = getbuf(cw->dev, addr, Bread);
			if(!p) {
				print("split: null getbuf\n");
				break;
			}
		}
		na = cw->fsize;
		cw->fsize = na+1;
		cwio(cw->dev, na, 0, Ogrow);
		cwio(cw->dev, na, p->iobuf, Owrite);
		cwio(cw->dev, na, 0, Odump);
		cwio(cw->dev, addr, 0, Orele);
		break;

	case Cdirty:
		cwio(cw->dev, addr, 0, Odump);
		break;
	}
	if(p)
		putbuf(p);
	return na;
}

int
isdirty(Cw *cw, Iobuf *p, Off addr, int tag)
{
	int s;

	if(p && (p->flags & Bmod))
		return 1;
	s = cwio(cw->dev, addr, 0, Onone);
	if(s == Cdirty || s == Cwrite)
		return 1;
	if(tag >= Tind1 && tag <= Tmaxind)
		/* botch, get these modified */
		if(s != Cnone)
			return 1;
	return 0;
}

Off
cwrecur(Cw *cw, Off addr, int tag, int tag1, long qp)
{
	Iobuf *p;
	Dentry *d;
	int i, j, shouldstop;
	Off na;
	char *np;

	shouldstop = 0;
	p = getbuf(cw->dev, addr, Bprobe);
	if(!isdirty(cw, p, addr, tag)) {
		if(!cw->all) {
			if(DEBUG)
				print("cwrecur: %lld t=%s not dirty %s\n",
					(Wideoff)addr, tagnames[tag], cw->name);
			if(p)
				putbuf(p);
			return 0;
		}
		shouldstop = 1;
	}
	if(DEBUG)
		print("cwrecur: %lld t=%s %s\n",
			(Wideoff)addr, tagnames[tag], cw->name);
	if(cw->depth >= 100) {
		print("dump depth too great %s\n", cw->name);
		if(p)
			putbuf(p);
		return 0;
	}
	cw->depth++;

	switch(tag)
	{
	default:
		print("cwrecur: unknown tag %d %s\n", tag, cw->name);

	case Tfile:
		break;

	case Tsuper:
	case Tdir:
		if(!p) {
			p = getbuf(cw->dev, addr, Bread);
			if(!p) {
				print("cwrecur: Tdir p null %s\n",
					cw->name);
				break;
			}
		}
		if(tag == Tdir) {
			cw->namepad[0] = 0;	/* force room */
			np = strchr(cw->name, 0);
			*np++ = '/';
		} else {
			np = 0;	/* set */
			cw->name[0] = 0;
		}

		for(i=0; i<DIRPERBUF; i++) {
			d = getdir(p, i);
			if(!(d->mode & DALLOC))
				continue;
			qp = d->qid.path & ~QPDIR;
			if(tag == Tdir)
				strncpy(np, d->name, NAMELEN);
			else
			if(i > 0)
				print("cwrecur: root with >1 directory\n");
			tag1 = Tfile;
			if(d->mode & DDIR)
				tag1 = Tdir;
			for(j=0; j<NDBLOCK; j++) {
				na = d->dblock[j];
				if(na) {
					na = cwrecur(cw, na, tag1, 0, qp);
					if(na) {
						d->dblock[j] = na;
						p->flags |= Bmod;
					}
				}
			}
			for (j = 0; j < NIBLOCK; j++) {
				na = d->iblocks[j];
				if(na) {
					na = cwrecur(cw, na, Tind1+j, tag1, qp);
					if(na) {
						d->iblocks[j] = na;
						p->flags |= Bmod;
					}
				}
			}
		}
		break;

	case Tind1:
		j = tag1;
		tag1 = 0;
		goto tind;

	case Tind2:
#ifndef OLD
	case Tind3:
	case Tind4:
	/* add more Tind tags here ... */
#endif
		j = tag-1;
	tind:
		if(!p) {
			p = getbuf(cw->dev, addr, Bread);
			if(!p) {
				print("cwrecur: Tind p null %s\n", cw->name);
				break;
			}
		}
		for(i=0; i<INDPERBUF; i++) {
			na = ((Off *)p->iobuf)[i];
			if(na) {
				na = cwrecur(cw, na, j, tag1, qp);
				if(na) {
					((Off *)p->iobuf)[i] = na;
					p->flags |= Bmod;
				}
			}
		}
		break;
	}
	na = split(cw, p, addr);
	cw->depth--;
	if(na && shouldstop) {
		if(cw->falsehits < 10)
			print("shouldstop %lld %lld t=%s %s\n",
				(Wideoff)addr, (Wideoff)na,
				tagnames[tag], cw->name);
		cw->falsehits++;
	}
	return na;
}

Timet	nextdump(Timet t);

void
cfsdump(Filsys *fs)
{
	long m, n, i;
	Off orba, rba, oroa, roa, sba, a;
	Timet tim;
	char tstr[20];
	Iobuf *pr, *p1, *p;
	Dentry *dr, *d1, *d;
	Cache *h;
	Superb *s;
	Cw *cw;

	if(fs->dev->type != Devcw) {
		print("cant dump; not cw device: %Z\n", fs->dev);
		return;
	}
	cw = fs->dev->private;
	if(cw == 0) {
		print("cant dump: has not been inited: %Z\n", fs->dev);
		return;
	}

	tim = toytime();
	wlock(&mainlock);		/* dump */

	/*
	 * set up static structure
	 * with frequent variables
	 */
	cw->ndump = 0;
	cw->name[0] = 0;
	cw->depth = 0;

	/*
	 * cw root
	 */
	sync("before dump");
	cw->fsize = cwsize(cw->dev);
	orba = cwraddr(cw->dev);
	print("cwroot %lld", (Wideoff)orba);
	cons.noage = 1;
	cw->all = cw->allflag;
	rba = cwrecur(cw, orba, Tsuper, 0, QPROOT);
	if(rba == 0)
		rba = orba;
	print("->%lld\n", (Wideoff)rba);
	sync("after cw");

	/*
	 * partial super block
	 */
	p = getbuf(cw->dev, cwsaddr(cw->dev), Bread|Bmod|Bimm);
	s = (Superb*)p->iobuf;
	s->fsize = cw->fsize;
	s->cwraddr = rba;
#ifdef AUTOSWAB
	s->magic = 0x123456789abcdef0;
#endif
	putbuf(p);

	/*
	 * partial cache block
	 */
	p = getbuf(cw->cdev, CACHE_ADDR, Bread|Bmod|Bimm|Bres);
	h = (Cache*)p->iobuf;
	h->fsize = cw->fsize;
	h->cwraddr = rba;
	putbuf(p);

	/*
	 * ro root
	 */
	oroa = cwraddr(cw->rodev);
	pr = getbuf(cw->dev, oroa, Bread|Bmod);
	dr = getdir(pr, 0);

	datestr(tstr, time());	/* tstr = "yyyymmdd" */
	n = 0;