#include <9pm/u.h>
#include <9pm/libc.h>
#include <9pm/fcall.h>
#include <9pm/thread.h>

#define DEBUG		if(dbg<0){}else fprint
#define DFD		dbg
#define fidhash(s)	fhash[s%FHASHSIZE]

typedef struct Fsrpc Fsrpc;
typedef struct Fid Fid;
typedef struct File File;
typedef struct Proc Proc;
typedef struct Qidtab Qidtab;

struct Fsrpc
{
	int	busy;		/* Work buffer has pending rpc to service */
	int	pid;		/* Pid of slave process executing the rpc */
	int	canint;		/* Interrupt gate */
	int	flushtag;	/* Tag on which to reply to flush */
	Fcall work;		/* Plan 9 incoming Fcall */
	uchar	*buf;	/* Data buffer */
};

struct Fid
{
	int	fid;		/* system fd for i/o */
	File	*f;		/* File attached to this fid */
	int	mode;
	int	nr;		/* fid number */
	int	mid;		/* Mount id */
	Fid	*next;		/* hash link */
	vlong	offset;		/* current offset in directory */
//RSC: these can go after the transition
//RSC: can they?  preaddir seems to indicate no.
Dir	*dir;		/* buffer for reading directories */
int	ndir;		/* number of entries in dir */
int	cdir;		/* number of consumed entries in dir */
};

struct File
{
	char	*name;
	int	ref;
	Qid	qid;
	Qidtab	*qidt;
	int	inval;
	File	*parent;
	File	*child;
	File	*childlist;
};

struct Proc
{
	int	pid;
	int	busy;
	Proc	*next;
};

struct Qidtab
{
	int	ref;
	int	type;
	int	dev;
	vlong	path;
	vlong	uniqpath;
	Qidtab	*next;
};

enum
{
	MAXPROC		= 50,
	FHASHSIZE	= 64,
	Nr_workbufs 	= 50,
	Fidchunk	= 1000,
	Npsmpt		= 32,
	Nqidbits		= 5,
	Nqidtab		= (1<<Nqidbits),
};

static Fsrpc	*Workq;
static int  	dbg = -1;
static File	*root;
static File	*psmpt;
static Fid	**fhash;
static Fid	*fidfree;
static Proc	*Proclist;
static char	psmap[Npsmpt];
static Qidtab	*qidtab[Nqidtab];
static ulong	messagesize;

/* File system protocol service procedures */
static void Xattach(Fsrpc*);
static void Xauth(Fsrpc*);
static void Xclunk(Fsrpc*); 
static void Xcreate(Fsrpc*);
static void Xflush(Fsrpc*); 
static void Xnop(Fsrpc*);
static void Xremove(Fsrpc*);
static void Xstat(Fsrpc*);
static void Xversion(Fsrpc*);
static void Xwalk(Fsrpc*);
static void Xwstat(Fsrpc*);
static void slave(Fsrpc*);

static void	reply(Fcall*, Fcall*, char*);
static Fid 	*getfid(int);
static int	freefid(int);
static Fid	*newfid(int);
static Fsrpc	*getsbuf(void);
static void	initroot(void);
static void	fatal(char*, ...);
static char*	makepath(File*, char*);
static File	*file(File*, char*);
static void	freefile(File*);
static void	slaveopen(Fsrpc*);
static void	slaveread(Fsrpc*);
static void	slavewrite(Fsrpc*);
static void	blockingslave(void*);
static void	reopen(Fid *f);
static void	noteproc(int, char*);
static void	flushaction(void*, char*);
static void	pushfcall(char*);
static Qidtab* uniqueqid(Dir*);
static void	freeqid(Qidtab*);
static char*	estrdup(char*);
static void*	emallocz(uint);
static int		readmessage(int, char*, int);

static char Ebadfid[] = "Bad fid";
static char Enotdir[] = "Not a directory";
static char Edupfid[] = "Fid already in use";
static char Eopen[] = "Fid already opened";
static char Exmnt[] = "Cannot .. past mount point";
static char Emip[] = "Mount in progress";
static char Enopsmt[] = "Out of pseudo mount points";
static char Enomem[] = "No memory";
static char Eversion[] = "Bad 9P2000 version";

static ulong messagesize;

static void
Xversion(Fsrpc *t)
{
	Fcall rhdr;

	if(t->work.msize > messagesize)
		t->work.msize = messagesize;
	messagesize = t->work.msize;
	if(strncmp(t->work.version, "9P2000", 6) != 0){
		reply(&t->work, &rhdr, Eversion);
		return;
	}
	rhdr.version = "9P2000";
	rhdr.msize = t->work.msize;
	reply(&t->work, &rhdr, 0);
	t->busy = 0;
}

static void
Xauth(Fsrpc *t)
{
	Fcall rhdr;

	reply(&t->work, &rhdr, "exportfs: no authentication required");
	t->busy = 0;
}

static void
Xflush(Fsrpc *t)
{
	Fsrpc *w, *e;
	Fcall rhdr;

	e = &Workq[Nr_workbufs];

	for(w = Workq; w < e; w++) {
		if(w->work.tag == t->work.oldtag) {
			DEBUG(DFD, "\tQ busy %d pid %d can %d\n", w->busy, w->pid, w->canint);
			if(w->busy && w->pid) {
				w->flushtag = t->work.tag;
				DEBUG(DFD, "\tset flushtag %d\n", t->work.tag);
				if(w->canint)
					postnote(PNPROC, w->pid, "interrupt");
				t->busy = 0;
				return;
			}
		}
	}

	reply(&t->work, &rhdr, 0);
	DEBUG(DFD, "\tflush reply\n");
	t->busy = 0;
}

static void
Xattach(Fsrpc *t)
{
	Fcall rhdr;
	Fid *f;

	f = newfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}
	f->f = root;
	f->f->ref++;

	rhdr.qid = f->f->qid;
	reply(&t->work, &rhdr, 0);
	t->busy = 0;
}

static Fid*
clonefid(Fid *f, int new)
{
	Fid *n;

	n = newfid(new);
	if(n == 0) {
		n = getfid(new);
		if(n == 0)
			fatal("inconsistent fids");
		if(n->fid >= 0)
			close(n->fid);
		freefid(new);
		n = newfid(new);
		if(n == 0)
			fatal("inconsistent fids2");
	}
	n->f = f->f;
	n->f->ref++;
	return n;
}

static void
Xwalk(Fsrpc *t)
{
	char err[ERRMAX], *e;
	Fcall rhdr;
	Fid *f, *nf;
	File *wf;
	int i;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}

	nf = nil;
	if(t->work.newfid != t->work.fid){
		nf = clonefid(f, t->work.newfid);
		f = nf;
	}

	rhdr.nwqid = 0;
	e = nil;
	for(i=0; i<t->work.nwname; i++){
		if(i == MAXWELEM){
			e = "Too many path elements";
			break;
		}

		if(strcmp(t->work.wname[i], "..") == 0) {
			if(f->f->parent == nil) {
				e = Exmnt;
				break;
			}
			wf = f->f->parent;
			wf->ref++;
			goto Accept;
		}
	
		wf = file(f->f, t->work.wname[i]);
		if(wf == 0){
			errstr(err, sizeof err);
			e = err;
			break;
		}
    Accept:
		freefile(f->f);
		rhdr.wqid[rhdr.nwqid++] = wf->qid;
		f->f = wf;
		continue;
	}

	if(nf!=nil && (e!=nil || rhdr.nwqid!=t->work.nwname))
		freefid(t->work.newfid);
	if(rhdr.nwqid > 0)
		e = nil;
	reply(&t->work, &rhdr, e);
	t->busy = 0;
}

static void
Xclunk(Fsrpc *t)
{
	Fcall rhdr;
	Fid *f;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}

	if(f->fid >= 0)
		close(f->fid);

	freefid(t->work.fid);
	reply(&t->work, &rhdr, 0);
	t->busy = 0;
}

static void
Xstat(Fsrpc *t)
{
	char err[ERRMAX], *path;
	Fcall rhdr;
	Fid *f;
	Dir *d;
	int s;
	uchar *statbuf;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}
	if(f->fid >= 0)
		d = dirfstat(f->fid);
	else {
		path = makepath(f->f, "");
		d = dirstat(path);
		free(path);
	}

	if(d == nil) {
		errstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
		t->busy = 0;
		return;
	}

	d->qid.path = f->f->qidt->uniqpath;
	s = sizeD2M(d);
	statbuf = emallocz(s);
	s = convD2M(d, statbuf, s);
	rhdr.nstat = s;
	rhdr.stat = statbuf;
	reply(&t->work, &rhdr, 0);
	free(statbuf);
	t->busy = 0;
}

static int
getiounit(int fd)
{
	int n;

	n = iounit(fd);
	if(n > messagesize-IOHDRSZ)
		n = messagesize-IOHDRSZ;
	return n;
}

static void
Xcreate(Fsrpc *t)
{
	char err[ERRMAX], *path;
	Fcall rhdr;
	Fid *f;
	File *nf;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}
	

	path = makepath(f->f, t->work.name);
	f->fid = create(path, t->work.mode, t->work.perm);
	free(path);
	if(f->fid < 0) {
		errstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
		t->busy = 0;
		return;
	}

	nf = file(f->f, t->work.name);
	if(nf == 0) {
		errstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
		t->busy = 0;
		return;
	}

	f->mode = t->work.mode;
	freefile(f->f);
	f->f = nf;
	rhdr.qid = f->f->qid;
	rhdr.iounit = getiounit(f->fid);
	reply(&t->work, &rhdr, 0);
	t->busy = 0;
}

static void
Xremove(Fsrpc *t)
{
	char err[ERRMAX], *path;
	Fcall rhdr;
	Fid *f;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}

	path = makepath(f->f, "");
	DEBUG(DFD, "\tremove: %s\n", path);
	if(remove(path) < 0) {
		free(path);
		errstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
		t->busy = 0;
		return;
	}
	free(path);

	f->f->inval = 1;
	if(f->fid >= 0)
		close(f->fid);
	freefid(t->work.fid);

	reply(&t->work, &rhdr, 0);
	t->busy = 0;
}

static void
Xwstat(Fsrpc *t)
{
	char err[ERRMAX], *path;
	Fcall rhdr;
	Fid *f;
	int s;
	char *strings;
	Dir d;

	f = getfid(t->work.fid);
	if(f == 0) {
		reply(&t->work, &rhdr, Ebadfid);
		t->busy = 0;
		return;
	}
	strings = emallocz(t->work.nstat);	/* ample */
	if(convM2D(t->work.stat, t->work.nstat, &d, strings) < 0){
		rerrstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
		t->busy = 0;
		free(strings);
		return;
	}

	if(f->fid >= 0)
		s = dirfwstat(f->fid, &d);
	else {
		path = makepath(f->f, "");
		s = dirwstat(path, &d);
		free(path);
	}
	if(s < 0) {
		rerrstr(err, sizeof err);
		reply(&t->work, &rhdr, err);
	}
	else {
		/* wstat may really be rename */
		if(strcmp(d.name, f->f->name)!=0){
			free(f->f->name);
			f->f->name = estrdup(d.name);
		}
		reply(&t->work, &rhdr, 0);
	}
	free(strings);
	t->busy = 0;
}

static void
slave(Fsrpc *f)
{
	Proc *p;
	int pid;
	static int nproc;
	Channel *c;

	c = chancreate(sizeof(ulong), 0);
	for(;;) {
		for(p = Proclist; p; p = p->next) {
			if(p->busy == 0) {
				f->pid = p->pid;
				p->busy = 1;
				pid = rendezvous(p->pid, (ulong)f);
				if(pid != p->pid)
					fatal("rendezvous sync fail");
				return;
			}	
		}

		if(++nproc > MAXPROC)
			fatal("too many procs");

		proccreate(blockingslave, c, 8192);
		pid = recvul(c);

		p = mallocz(sizeof(Proc), 1);
		if(p == 0)
			fatal("out of memory");
		p->busy = 0;
		p->pid = pid;
		p->next = Proclist;
		Proclist = p;
		rendezvous(pid, (ulong)p);
	}
}

static void
blockingslave(void *c)
{
	Fsrpc *p;
	Fcall rhdr;
	Proc *m;
	int pid;

	notify(flushaction);

	pid = getpid();
	sendul(c, pid);

	m = (Proc*)rendezvous(pid, 0);
	
	for(;;) {
		p = (Fsrpc*)rendezvous(pid, pid);
		if((int)p == ~0)			/* Interrupted */
			continue;

		DEBUG(DFD, "\tslave: %d %F b %d p %d\n", pid, &p->work, p->busy, p->pid);
		if(p->flushtag != NOTAG)
			goto flushme;

		switch(p->work.type) {
		case Tread:
			slaveread(p);
			break;

		case Twrite:
			slavewrite(p);
			break;

		case Topen:
			slaveopen(p);
			break;

		default:
			reply(&p->work, &rhdr, "exportfs: slave type error");
		}
		if(p->flushtag != NOTAG) {
flushme:
			p->work.type = Tflush;
			p->work.tag = p->flushtag;
			reply(&p->work, &rhdr, 0);
		}
		p->busy = 0;
		m->busy = 0;
	}
}

static void
slaveopen(Fsrpc *p)
{
	char err[ERRMAX], *path;
	Fcall *work, rhdr;
	Fid *f;
	Dir *d;

	work = &p->work;

	f = getfid(work->fid);
	if(f == 0) {
		reply(work, &rhdr, Ebadfid);
		return;
	}
	if(f->fid >= 0) {
		close(f->fid);
		f->fid = -1;
	}
	
	path = makepath(f->f, "");
	DEBUG(DFD, "\topen: %s %d\n", path, work->mode);

	p->canint = 1;
	if(p->flushtag != NOTAG){
		free(path);
		return;
	}
	/* There is a race here I ignore because there are no locks */
	f->fid = open(path, work->mode);
	free(path);
	p->canint = 0;
	if(f->fid < 0 || (d = dirfstat(f->fid)) == nil) {
	Error:
		rerrstr(err, sizeof err);
		reply(work, &rhdr, err);
		return;
	}
	f->f->qid = d->qid;
	free(d);
	if(f->f->qid.type & QTMOUNT){	/* fork new exportfs for this */
		werrstr("cannot open mounted channel");
		goto Error;
	}

	DEBUG(DFD, "\topen: fd %d\n", f->fid);
	f->mode = work->mode;
	f->offset = 0;
	rhdr.iounit = getiounit(f->fid);
	rhdr.qid = f->f->qid;
	reply(work, &rhdr, 0);
}

static int
preaddir(Fid *f, uchar *data, int n, vlong offset)
{
	int r = 0, m;
	Dir *d;

	DEBUG(DFD, "\tpreaddir n=%d wo=%lld fo=%lld\n", n, offset, f->offset);
	if(offset == 0 && f->offset != 0){
		if(seek(f->fid, 0, 0) != 0)
			return -1;
		f->offset = f->cdir = f->ndir = 0;
		free(f->dir);
		f->dir = nil;
	}else if(offset != f->offset){
		werrstr("can't seek dir %lld to %lld", f->offset, offset);
		return -1;
	}

	while(n > 0){
		if(f->dir == nil){
			f->ndir = dirread(f->fid, &f->dir);
			if(f->ndir < 0)
				return f->ndir;
			if(f->ndir == 0)
				return r;
		}
		d = &f->dir[f->cdir++];
		m = convD2M(d, data, n);
		DEBUG(DFD, "\t\tconvD2M %d\n", m);
		if(m <= BIT16SZ){
			DEBUG(DFD, "\t\t\tneeded %d\n", GBIT16(data));
			/* not enough room for full entry; leave for next time */
			f->cdir--;
			return r;
		}else{
			data += m;
			n -= m;
			r += m;
			f->offset += m;
		}
		if(f->cdir >= f->ndir){
			f->cdir = f->ndir = 0;
			free(f->dir);
			f->dir = nil;
		}
	}
	return r;
}

static void
slaveread(Fsrpc *p)
{
	Fid *f;
	int n, r;
	Fcall *work, rhdr;
	char *data, err[ERRMAX];

	work = &p->work;

	f = getfid(work->fid);
	if(f == 0) {
		reply(work, &rhdr, Ebadfid);
		return;
	}

	n = (work->count > messagesize-IOHDRSZ) ? messagesize-IOHDRSZ : work->count;
	p->canint = 1;
	if(p->flushtag != NOTAG)
		return;
	data = malloc(n);
	if(data == nil)
		fatal(Enomem);

	/* can't just call pread, since directories must update the offset */
	if(f->f->qid.type&QTDIR){
		if(work->offset == 0)
			seek(f->fid, 0, 0);
		r = read(f->fid, data, n);
	}else
		r = pread(f->fid, data, n, work->offset);
	p->canint = 0;
	if(r < 0) {
		free(data);
		errstr(err, sizeof err);
		reply(work, &rhdr, err);
		return;
	}

	DEBUG(DFD, "\tread: fd=%d %d bytes\n", f->fid, r);

	rhdr.data = data;
	rhdr.count = r;
	reply(work, &rhdr, 0);
	free(data);
}

static void
slavewrite(Fsrpc *p)
{
	char err[ERRMAX];
	Fcall *work, rhdr;
	Fid *f;
	int n;

	work = &p->work;

	f = getfid(work->fid);
	if(f == 0) {
		reply(work, &rhdr, Ebadfid);
		return;
	}

	n = (work->count > messagesize-IOHDRSZ) ? messagesize-IOHDRSZ : work->count;
	p->canint = 1;
	if(p->flushtag != NOTAG)
		return;
	n = pwrite(f->fid, work->data, n, work->offset);
	p->canint = 0;
	if(n < 0) {
		errstr(err, sizeof err);
		reply(work, &rhdr, err);
		return;
	}

	DEBUG(DFD, "\twrite: %d bytes fd=%d\n", n, f->fid);

	rhdr.count = n;
	reply(work, &rhdr, 0);
}

static void
reopen(Fid *f)
{
	USED(f);
	fatal("reopen");
}

static void
flushaction(void *a, char *cause)
{
	USED(a);

	if(strncmp(cause, "sys:", 4) == 0 && !strstr(cause, "pipe")) {
		fprint(2, "exportsrv: note: %s\n", cause);
		threadexitsall("noted");
	}
	if(strncmp(cause, "kill", 4) == 0)
		noted(NDFLT);
	if(strncmp(cause, "hangup", 6) == 0)
		threadexitsall("hangup");

	noted(NCONT);
}

#define QIDPATH	((((vlong)1)<<48)-1)
vlong newqid = 0;

enum {
	Encnone,
	Encssl,
	Enctls,
};

static void (*fcalls[256])(Fsrpc*);

/* accounting and debugging counters */
static int	filecnt;
static int	freecnt;
static int	qidcnt;
static int	qfreecnt;
static int	ncollision;

static int	netfd;

void
export(int fd)
{
	Fsrpc *r;
	Fcall rhdr;
	int i, n;

	fcalls[Tversion] = Xversion;
	fcalls[Tauth] = Xauth;
	fcalls[Tflush] = Xflush;
	fcalls[Tattach] = Xattach;
	fcalls[Twalk] = Xwalk;
	fcalls[Topen] = slave;
	fcalls[Tcreate] = Xcreate;
	fcalls[Tclunk] = Xclunk;
	fcalls[Tread] = slave;
	fcalls[Twrite] = slave;
	fcalls[Tremove] = Xremove;
	fcalls[Tstat] = Xstat;
	fcalls[Twstat] = Xwstat;

//dbg = create("/tmp/a", OWRITE, 0666);
	messagesize = 32768+IOHDRSZ;

	Workq = emallocz(sizeof(Fsrpc)*Nr_workbufs);
	for(i=0; i<Nr_workbufs; i++)
		Workq[i].buf = emallocz(messagesize);
	fhash = emallocz(sizeof(Fid*)*FHASHSIZE);

	fmtinstall('F', fcallconv);

	chdir("/");
	initroot();

	netfd = fd;
	/*
	 * Start serving file requests from the network
	 */
	for(;;) {
		r = getsbuf();
		if(r == 0)
			fatal("Out of service buffers");
			
		n = read9pmsg(netfd, r->buf, messagesize);
		if(n <= 0)
			fatal(nil);

		if(convM2S(r->buf, n, &r->work) == 0)
			fatal("convM2S format error");

		DEBUG(DFD, "%F\n", &r->work);
		if(r->work.type < 0 || r->work.type>nelem(fcalls)
		|| fcalls[r->work.type]==nil)
			reply(&r->work, &rhdr, "bad fcall");
		else
			(fcalls[r->work.type])(r);
	}
}

static void
reply(Fcall *r, Fcall *t, char *err)
{
	uchar *data;
	int n;

	t->tag = r->tag;
	t->fid = r->fid;
	if(err) {
		t->type = Rerror;
		t->ename = err;
	}
	else 
		t->type = r->type + 1;

	DEBUG(DFD, "\t%F\n", t);

	data = malloc(messagesize);	/* not mallocz; no need to clear */
	if(data == nil)
		fatal(Enomem);
	n = convS2M(t, data, messagesize);
	if(write(netfd, data, n)!=n)
		fatal("mount write");
	free(data);
}

static Fid *
getfid(int nr)
{
	Fid *f;

	for(f = fidhash(nr); f; f = f->next)
		if(f->nr == nr)
			return f;

	return 0;
}

static int
freefid(int nr)
{
	Fid *f, **l;
	char buf[128];

	l = &fidhash(nr);
	for(f = *l; f; f = f->next) {
		if(f->nr == nr) {
			if(f->mid) {
				sprint(buf, "/mnt/exportfs/%d", f->mid);
				unmount(0, buf);
				psmap[f->mid] = 0;
			}
			if(f->f) {
				freefile(f->f);
				f->f = nil;
			}
			*l = f->next;
			f->next = fidfree;
			fidfree = f;
			return 1;
		}
		l = &f->next;
	}

	return 0;	
}

static Fid *
newfid(int nr)
{
	Fid *new, **l;
	int i;

	l = &fidhash(nr);
	for(new = *l; new; new = new->next)
		if(new->nr == nr)
			return 0;

	if(fidfree == 0) {
		fidfree = emallocz(sizeof(Fid) * Fidchunk);

		for(i = 0; i < Fidchunk-1; i++)
			fidfree[i].next = &fidfree[i+1];

		fidfree[Fidchunk-1].next = 0;
	}

	new = fidfree;
	fidfree = new->next;

	memset(new, 0, sizeof(Fid));
	new->next = *l;
	*l = new;
	new->nr = nr;
	new->fid = -1;
	new->mid = 0;

	return new;	
}

static Fsrpc *
getsbuf(void)
{
	static int ap;
	int look, rounds;
	Fsrpc *wb;

	for(rounds = 0; rounds < 10; rounds++) {
		for(look = 0; look < Nr_workbufs; look++) {
			if(++ap == Nr_workbufs)
				ap = 0;
			if(Workq[ap].busy == 0)
				break;
		}

		if(look == Nr_workbufs){
			sleep(10 * rounds);
			continue;
		}

		wb = &Workq[ap];
		wb->pid = 0;
		wb->canint = 0;
		wb->flushtag = NOTAG;
		wb->busy = 1;

		return wb;
	}
	fatal("No more work buffers");
	return nil;
}

static void
freefile(File *f)
{
	File *parent, *child;

Loop:
	f->ref--;
	if(f->ref > 0)
		return;
	freecnt++;
	if(f->ref < 0) abort();
	DEBUG(DFD, "free %s\n", f->name);
	/* delete from parent */
	parent = f->parent;
	if(parent->child == f)
		parent->child = f->childlist;
	else{
		for(child=parent->child; child->childlist!=f; child=child->childlist)
			if(child->childlist == nil)
				fatal("bad child list");
		child->childlist = f->childlist;
	}
	freeqid(f->qidt);
	free(f->name);
	f->name = nil;
	free(f);
	f = parent;
	if(f != nil)
		goto Loop;
}

static File *
file(File *parent, char *name)
{
	Dir *dir;
	char *path;
	File *f;

	DEBUG(DFD, "\tfile: 0x%p %s name %s\n", parent, parent->name, name);

	path = makepath(parent, name);
	dir = dirstat(path);
	free(path);
	if(dir == nil)
		return nil;

	for(f = parent->child; f; f = f->childlist)
		if(strcmp(name, f->name) == 0)
			break;

	if(f == nil){
		f = emallocz(sizeof(File));
		f->name = estrdup(name);

		f->parent = parent;
		f->childlist = parent->child;
		parent->child = f;
		parent->ref++;
		f->ref = 0;
		filecnt++;
	}
	f->ref++;
	f->qid.type = dir->qid.type;
	f->qid.vers = dir->qid.vers;
	f->qidt = uniqueqid(dir);
	f->qid.path = f->qidt->uniqpath;

	f->inval = 0;

	free(dir);

	return f;
}

static void
initroot(void)
{
	Dir *dir;

	root = emallocz(sizeof(File));
	root->name = estrdup(".");

	dir = dirstat(root->name);
	if(dir == nil)
		fatal("root stat");

	root->ref = 1;
	root->qid.vers = dir->qid.vers;
	root->qidt = uniqueqid(dir);
	root->qid.path = root->qidt->uniqpath;
	root->qid.type = QTDIR;
	free(dir);

	psmpt = emallocz(sizeof(File));
	psmpt->name = estrdup("/");

	dir = dirstat(psmpt->name);
	if(dir == nil)
		return;

	psmpt->ref = 1;
	psmpt->qid.vers = dir->qid.vers;
	psmpt->qidt = uniqueqid(dir);
	psmpt->qid.path = psmpt->qidt->uniqpath;
	free(dir);

	psmpt = file(psmpt, "mnt");
	if(psmpt == 0)
		return;
	psmpt = file(psmpt, "exportfs");
}

static char*
makepath(File *p, char *name)
{
	int i, n;
	char *c, *s, *path, *seg[256];

	seg[0] = name;
	n = strlen(name)+2;
	for(i = 1; i < 256 && p; i++, p = p->parent){
		seg[i] = p->name;
		n += strlen(p->name)+1;
	}
	path = malloc(n);
	if(path == nil)
		fatal("out of memory");
	s = path;

	while(i--) {
		for(c = seg[i]; *c; c++)
			*s++ = *c;
		*s++ = '/';
	}
	while(s[-1] == '/')
		s--;
	*s = '\0';

	return path;
}

static int
qidhash(vlong path)
{
	int h, n;

	h = 0;
	for(n=0; n<64; n+=Nqidbits){
		h ^= path;
		path >>= Nqidbits;
	}
	return h & (Nqidtab-1);
}

static void
freeqid(Qidtab *q)
{
	ulong h;
	Qidtab *l;

	q->ref--;
	if(q->ref > 0)
		return;
	qfreecnt++;
	h = qidhash(q->path);
	if(qidtab[h] == q)
		qidtab[h] = q->next;
	else{
		for(l=qidtab[h]; l->next!=q; l=l->next)
			if(l->next == nil)
				fatal("bad qid list");
		l->next = q->next;
	}
	free(q);
}

static Qidtab*
qidlookup(Dir *d)
{
	ulong h;
	Qidtab *q;

	h = qidhash(d->qid.path);
	for(q=qidtab[h]; q!=nil; q=q->next)
		if(q->type==d->type && q->dev==d->dev && q->path==d->qid.path)
			return q;
	return nil;
}

static int
qidexists(vlong path)
{
	int h;
	Qidtab *q;

	for(h=0; h<Nqidtab; h++)
		for(q=qidtab[h]; q!=nil; q=q->next)
			if(q->uniqpath == path)
				return 1;
	return 0;
}

static Qidtab*
uniqueqid(Dir *d)
{
	ulong h;
	vlong path;
	Qidtab *q;

	q = qidlookup(d);
	if(q != nil){
		q->ref++;
		return q;
	}
	path = d->qid.path;
	while(qidexists(path)){
		DEBUG(DFD, "collision on %s\n", d->name);
		/* collision: find a new one */
		ncollision++;
		path &= QIDPATH;
		++newqid;
		if(newqid >= (1<<16)){
			DEBUG(DFD, "collision wraparound\n");
			newqid = 1;
		}
		path |= newqid<<48;
		DEBUG(DFD, "assign qid %.16llux\n", path);
	}
	q = mallocz(sizeof(Qidtab), 1);
	if(q == nil)
		fatal("no memory for qid table");
	qidcnt++;
	q->ref = 1;
	q->type = d->type;
	q->dev = d->dev;
	q->path = d->qid.path;
	q->uniqpath = path;
	h = qidhash(d->qid.path);
	q->next = qidtab[h];
	qidtab[h] = q;
	return q;
}

static void
fatal(char *s, ...)
{
	char buf[128];
	va_list arg;

	if (s) {
		va_start(arg, s);
		doprint(buf, buf + sizeof buf, s, arg);
		va_end(arg);
		sysfatal("%s", buf);
	}else
		threadexitsall(nil);
}

static void*
emallocz(uint n)
{
	void *p;

	p = mallocz(n, 1);
	if(p == nil)
		fatal(Enomem);
	return p;
}

static char*
estrdup(char *s)
{
	char *t;

	t = strdup(s);
	if(t == nil)
		fatal(Enomem);
	return t;
}
