Import sources from 2011-03-30 iso image

11 files changed, 3243 insertions, 0 deletions

diff --git a/sys/src/cmd/replica/all.h b/sys/src/cmd/replica/all.h
new file mode 100755
index 000000000..96d8e1f54
--- /dev/null
+++ b/sys/src/cmd/replica/all.h
@@ -0,0 +1,70 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <disk.h>
+
+/* avl.c */
+typedef struct Avl Avl;
+typedef struct Avltree Avltree;
+typedef struct Avlwalk Avlwalk;
+
+#pragma incomplete Avltree
+#pragma incomplete Avlwalk
+
+struct Avl
+{
+	Avl *p;	/* parent */
+	Avl *n[2];	/* children */
+	int bal;	/* balance bits */
+};
+
+Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
+void insertavl(Avltree *tree, Avl *new, Avl **oldp); 
+Avl *lookupavl(Avltree *tree, Avl *key);
+void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
+Avlwalk *avlwalk(Avltree *tree);
+Avl *avlnext(Avlwalk *walk);
+Avl	*avlprev(Avlwalk *walk);
+void endwalk(Avlwalk *walk);
+
+/* db.c */
+typedef struct Db Db;
+typedef struct Entry Entry;
+struct Entry
+{
+	Avl a;
+	char *name;
+	struct {
+		char *name;
+		char *uid;
+		char *gid;
+		ulong mtime;
+		ulong mode;
+		int mark;
+		vlong length;
+	} d;
+};
+
+
+typedef struct Db Db;
+struct Db
+{
+	Avltree *avl;
+	int fd;
+};
+Db *opendb(char*);
+int finddb(Db*, char*, Dir*);
+void removedb(Db*, char*);
+void insertdb(Db*, char*, Dir*);
+int markdb(Db*, char*, Dir*);
+
+/* util.c */
+void *erealloc(void*, int);
+void *emalloc(int);
+char *estrdup(char*);
+char *atom(char*);
+char *unroot(char*, char*);
+
+/* revproto.c */
+int revrdproto(char*, char*, char*, Protoenum*, Protowarn*, void*);
+
diff --git a/sys/src/cmd/replica/applychanges.c b/sys/src/cmd/replica/applychanges.c
new file mode 100755
index 000000000..70534e804
--- /dev/null
+++ b/sys/src/cmd/replica/applychanges.c
@@ -0,0 +1,332 @@
+/*
+ * push changes from client to server.
+ */
+#include "all.h"
+
+int douid;
+Db *db;
+char **x;
+int nx;
+int justshow;
+int verbose;
+int conflicts;
+char newpath[10000];
+char oldpath[10000];
+char *clientroot;
+char *serverroot;
+int copyfile(char*, char*, Dir*, int);
+int metafile(char*, Dir*);
+char **match;
+int nmatch;
+
+int
+ismatch(char *s)
+{
+	int i, len;
+
+	if(nmatch == 0)
+		return 1;
+	for(i=0; i<nmatch; i++){
+		if(strcmp(s, match[i]) == 0)
+			return 1;
+		len = strlen(match[i]);
+		if(strncmp(s, match[i], len) == 0 && s[len]=='/')
+			return 1;
+	}
+	return 0;
+}
+
+void
+xlog(char c, char *path, Dir *d)
+{
+	if(!verbose)
+		return;
+	print("%c %s %luo %s %s %lud\n", c, path, d->mode, d->uid, d->gid, d->mtime);
+}
+
+void
+walk(char *new, char *old, Dir *pd, void*)
+{
+	int i, len;
+	Dir od, d;
+	static Dir *xd;
+
+	new = unroot(new, "/");
+	old = unroot(old, serverroot);
+
+	if(!ismatch(new))
+		return;
+	if(xd != nil){
+		free(xd);
+		xd = nil;
+	}
+
+	for(i=0; i<nx; i++){
+		if(strcmp(new, x[i]) == 0)
+			return;
+		len = strlen(x[i]);
+		if(strncmp(new, x[i], len)==0 && new[len]=='/')
+			return;
+	}
+
+	d = *pd;
+	d.name = old;
+	memset(&od, 0, sizeof od);
+	snprint(newpath, sizeof newpath, "%s/%s", clientroot, new);
+	snprint(oldpath, sizeof oldpath, "%s/%s", serverroot, old);
+
+	xd = dirstat(oldpath);
+	if(markdb(db, new, &od) < 0){
+		if(xd != nil){
+			print("x %s create/create conflict\n", new);
+			conflicts = 1;
+			return;
+		}
+		xlog('a', new, &d);
+		d.muid = "mark";	/* mark bit */
+		if(!justshow){
+			if(copyfile(newpath, oldpath, &d, 1) == 0)
+				insertdb(db, new, &d);
+		}
+	}else{
+		if((d.mode&DMDIR)==0 && od.mtime!=d.mtime){
+			if(xd==nil){
+				print("%s update/remove conflict\n", new);
+				conflicts = 1;
+				return;
+			}
+			if(xd->mtime != od.mtime){
+				print("%s update/update conflict\n", new);
+				conflicts = 1;
+				return;
+			}
+			od.mtime = d.mtime;
+			od.muid = "mark";
+			xlog('c', new, &od);
+			if(!justshow){
+				if(copyfile(newpath, oldpath, &od, 0) == 0)
+					insertdb(db, new, &od);
+			}
+		}
+		if((douid&&strcmp(od.uid,d.uid)!=0)
+		|| strcmp(od.gid,d.gid)!=0 
+		|| od.mode!=d.mode){
+			if(xd==nil){
+				print("%s metaupdate/remove conflict\n", new);
+				conflicts = 1;
+				return;
+			}
+			if((douid&&strcmp(od.uid,xd->uid)!=0)
+			|| strcmp(od.uid,xd->gid)!=0
+			|| od.mode!=xd->mode){
+				print("%s metaupdate/metaupdate conflict\n", new);
+				conflicts = 1;
+				return;
+			}
+			if(douid)
+				od.uid = d.uid;
+			od.gid = d.gid;
+			od.mode = d.mode;
+			od.muid = "mark";
+			xlog('m', new, &od);
+			if(!justshow){
+				if(metafile(oldpath, &od) == 0)
+					insertdb(db, new, &od);
+			}
+		}
+	}
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: replica/applychanges [-nuv] [-p proto] [-x path]... clientdb clientroot serverroot [path ...]\n");
+	exits("usage");
+}
+
+void
+main(int argc, char **argv)
+{
+	char *proto;
+	Avlwalk *w;
+	Dir *xd, d;
+	Entry *e;
+
+	quotefmtinstall();
+	proto = "/sys/lib/sysconfig/proto/allproto";
+	ARGBEGIN{
+	case 'n':
+		justshow = 1;
+		verbose = 1;
+		break;
+	case 'p':
+		proto = EARGF(usage());
+		break;
+	case 'u':
+		douid = 1;
+		break;
+	case 'v':
+		verbose = 1;
+		break;
+	case 'x':
+		if(nx%16 == 0)
+			x = erealloc(x, (nx+16)*sizeof(x[0]));
+		x[nx++] = EARGF(usage());
+		break;
+	default:
+		usage();
+	}ARGEND
+
+	if(argc < 3)
+		usage();
+
+	db = opendb(argv[0]);
+	clientroot = argv[1];
+	serverroot = argv[2];
+	match = argv+3;
+	nmatch = argc-3;
+
+
+	if(revrdproto(proto, clientroot, serverroot, walk, nil, nil) < 0)
+		sysfatal("rdproto: %r");
+
+	w = avlwalk(db->avl);
+	while(e = (Entry*)avlprev(w)){
+		if(!ismatch(e->name))
+			continue;
+		if(!e->d.mark){		/* not visited during walk */
+			snprint(newpath, sizeof newpath, "%s/%s", clientroot, e->name);
+			snprint(oldpath, sizeof oldpath, "%s/%s", serverroot, e->d.name);
+			xd = dirstat(oldpath);
+			if(xd == nil){
+				removedb(db, e->name);
+				continue;
+			}
+			if(xd->mtime != e->d.mtime && (e->d.mode&xd->mode&DMDIR)==0){
+				print("x %q remove/update conflict\n", e->name);
+				free(xd);
+				continue;
+			}
+			memset(&d, 0, sizeof d);
+			d.name = e->d.name;
+			d.uid = e->d.uid;
+			d.gid = e->d.gid;
+			d.mtime = e->d.mtime;
+			d.mode = e->d.mode;
+			xlog('d', e->name, &d);
+			if(!justshow){
+				if(remove(oldpath) == 0)
+					removedb(db, e->name);
+			}
+			free(xd);
+		}
+	}
+
+	if(conflicts)
+		exits("conflicts");
+	exits(nil);
+}
+
+enum { DEFB = 8192 };
+
+static int
+copy1(int fdf, int fdt, char *from, char *to)
+{
+	char buf[DEFB];
+	long n, n1, rcount;
+	int rv;
+	char err[ERRMAX];
+
+	/* clear any residual error */
+	err[0] = '\0';
+	errstr(err, ERRMAX);
+	rv = 0;
+	for(rcount=0;; rcount++) {
+		n = read(fdf, buf, DEFB);
+		if(n <= 0)
+			break;
+		n1 = write(fdt, buf, n);
+		if(n1 != n) {
+			fprint(2, "error writing %q: %r\n", to);
+			rv = -1;
+			break;
+		}
+	}
+	if(n < 0) {
+		fprint(2, "error reading %q: %r\n", from);
+		rv = -1;
+	}
+	return rv;
+}
+
+int
+copyfile(char *from, char *to, Dir *d, int dowstat)
+{
+	Dir nd;
+	int rfd, wfd, didcreate;
+	
+	if((rfd = open(from, OREAD)) < 0)
+		return -1;
+
+	didcreate = 0;
+	if(d->mode&DMDIR){
+		if((wfd = create(to, OREAD, DMDIR)) < 0){
+			fprint(2, "mkdir %q: %r\n", to);
+			close(rfd);
+			return -1;
+		}
+	}else{
+		if((wfd = open(to, OTRUNC|OWRITE)) < 0){
+			if((wfd = create(to, OWRITE, 0)) < 0){
+				close(rfd);
+				return -1;
+			}
+			didcreate = 1;
+		}
+		if(copy1(rfd, wfd, from, to) < 0){
+			close(rfd);
+			close(wfd);
+			return -1;
+		}
+	}
+	close(rfd);
+	if(didcreate || dowstat){
+		nulldir(&nd);
+		nd.mode = d->mode;
+		if(dirfwstat(wfd, &nd) < 0)
+			fprint(2, "warning: cannot set mode on %q\n", to);
+		nulldir(&nd);
+		nd.gid = d->gid;
+		if(dirfwstat(wfd, &nd) < 0)
+			fprint(2, "warning: cannot set gid on %q\n", to);
+		if(douid){
+			nulldir(&nd);
+			nd.uid = d->uid;
+			if(dirfwstat(wfd, &nd) < 0)
+				fprint(2, "warning: cannot set uid on %q\n", to);
+		}
+	}
+	nulldir(&nd);
+	nd.mtime = d->mtime;
+	if(dirfwstat(wfd, &nd) < 0)
+		fprint(2, "warning: cannot set mtime on %q\n", to);
+	close(wfd);
+	return 0;
+}
+
+int
+metafile(char *path, Dir *d)
+{
+	Dir nd;
+
+	nulldir(&nd);
+	nd.gid = d->gid;
+	nd.mode = d->mode;
+	if(douid)
+		nd.uid = d->uid;
+	if(dirwstat(path, &nd) < 0){
+		fprint(2, "dirwstat %q: %r\n", path);
+		return -1;
+	}
+	return 0;
+}
diff --git a/sys/src/cmd/replica/applylog.c b/sys/src/cmd/replica/applylog.c
new file mode 100755
index 000000000..183011400
--- /dev/null
+++ b/sys/src/cmd/replica/applylog.c
@@ -0,0 +1,1253 @@
+#include "all.h"
+
+#define	Nwork	16
+
+int localdirstat(char*, Dir*);
+int ismatch(char*);
+void conflict(char*, char*, ...);
+void error(char*, ...);
+int isdir(char*);
+
+void worker(int fdf, int fdt, char *from, char *to);
+vlong	nextoff(void);
+void	failure(void *, char *note);
+
+QLock	lk;
+vlong	off;
+
+int errors;
+int nconf;
+int donothing;
+int verbose;
+char **match;
+int nmatch;
+int tempspool = 1;
+int safeinstall = 1;
+char *lroot;
+char *rroot;
+Db *clientdb;
+int skip;
+int douid;
+char *mkname(char*, int, char*, char*);
+char localbuf[10240];
+char remotebuf[10240];
+int copyfile(char*, char*, char*, Dir*, int, int*);
+ulong maxnow;
+int maxn;
+char *timefile;
+int timefd;
+int samecontents(char*, char*);
+
+Db *copyerr;
+
+typedef struct Res Res;
+struct Res
+{
+	char c;
+	char *name;
+};
+
+Res *res;
+int nres;
+
+void 
+addresolve(int c, char *name)
+{
+	if(name[0] == '/')
+		name++;
+	res = erealloc(res, (nres+1)*sizeof res[0]);
+	res[nres].c = c;
+	res[nres].name = name;
+	nres++;
+}
+
+int
+resolve(char *name)
+{
+	int i, len;
+
+	for(i=0; i<nres; i++){
+		len = strlen(res[i].name);
+		if(len == 0)
+			return res[i].c;
+		if(strncmp(name, res[i].name, len) == 0 && (name[len]=='/' || name[len] == 0))
+			return res[i].c;
+	}
+	return '?';
+}
+
+void
+readtimefile(void)
+{
+	int n;
+	char buf[24];
+
+	if((timefd = open(timefile, ORDWR)) < 0
+	&& (timefd = create(timefile, ORDWR|OEXCL, 0666)) < 0)
+		return;
+
+	n = readn(timefd, buf, sizeof buf);
+	if(n < sizeof buf)
+		return;
+
+	maxnow = atoi(buf);
+	maxn = atoi(buf+12);
+}
+
+void
+writetimefile(void)
+{
+	char buf[24+1];
+
+	snprint(buf, sizeof buf, "%11lud %11d ", maxnow, maxn);
+	pwrite(timefd, buf, 24, 0);
+}
+
+static void membogus(char**);
+
+void
+addce(char *local)
+{
+	char e[ERRMAX];
+	Dir d;
+
+	memset(&d, 0, sizeof d);
+	rerrstr(e, sizeof e);
+	d.name = atom(e);
+	d.uid = "";
+	d.gid = "";
+	insertdb(copyerr, atom(local), &d);
+}
+
+void
+delce(char *local)
+{
+	removedb(copyerr, local);
+}
+
+void
+chat(char *f, ...)
+{
+	Fmt fmt;
+	char buf[256];
+	va_list arg;
+
+	if(!verbose)
+		return;
+
+	fmtfdinit(&fmt, 1, buf, sizeof buf);
+	va_start(arg, f);
+	fmtvprint(&fmt, f, arg);
+	va_end(arg);
+	fmtfdflush(&fmt);
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: replica/applylog [-cnSstuv] [-T timefile] clientdb clientroot serverroot [path ...]\n");
+	exits("usage");
+}
+
+int
+notexists(char *path)
+{
+	char buf[ERRMAX];
+
+	if(access(path, AEXIST) >= 0)
+		return 0;
+	
+	rerrstr(buf, sizeof buf);
+	if(strstr(buf, "entry not found") || strstr(buf, "not exist"))
+		return 1;
+
+	/* some other error, like network hangup */
+	return 0;
+}
+
+void
+main(int argc, char **argv)
+{ 
+	char *f[10], *local, *name, *remote, *s, *t, verb;
+	int fd, havedb, havelocal, i, k, n, nf, resolve1, skip;
+	int checkedmatch1, checkedmatch2, 
+		checkedmatch3, checkedmatch4;
+	ulong now;
+	Biobuf bin;
+	Dir dbd, ld, nd, rd;
+	Avlwalk *w;
+	Entry *e;
+
+	membogus(argv);
+	quotefmtinstall();
+	ARGBEGIN{
+	case 's':
+	case 'c':
+		i = ARGC();
+		addresolve(i, EARGF(usage()));
+		break;
+	case 'n':
+		donothing = 1;
+		verbose = 1;
+		break;
+	case 'S':
+		safeinstall = 0;
+		break;
+	case 'T':
+		timefile = EARGF(usage());
+		break;
+	case 't':
+		tempspool = 0;
+		break;
+	case 'u':
+		douid = 1;
+		break;
+	case 'v':
+		verbose++;
+		break;
+	default:
+		usage();
+	}ARGEND
+
+	if(argc < 3)
+		usage();
+
+	if(timefile)
+		readtimefile();
+
+	lroot = argv[1];
+	if(!isdir(lroot))
+		sysfatal("bad local root directory");
+	rroot = argv[2];
+	if(!isdir(rroot))
+		sysfatal("bad remote root directory");
+
+	match = argv+3;
+	nmatch = argc-3;
+	for(i=0; i<nmatch; i++)
+		if(match[i][0] == '/')
+			match[i]++;
+
+	if((clientdb = opendb(argv[0])) == nil)
+		sysfatal("opendb %q: %r", argv[2]);
+	
+	copyerr = opendb(nil);
+
+	skip = 0;
+	Binit(&bin, 0, OREAD);
+	for(; s=Brdstr(&bin, '\n', 1); free(s)){
+		t = estrdup(s);
+		nf = tokenize(s, f, nelem(f));
+		if(nf != 10 || strlen(f[2]) != 1){
+			skip = 1;
+			fprint(2, "warning: skipping bad log entry <%s>\n", t);
+			free(t);
+			continue;
+		}
+		free(t);
+		now = strtoul(f[0], 0, 0);
+		n = atoi(f[1]);
+		verb = f[2][0];
+		name = f[3];
+		if(now < maxnow || (now==maxnow && n <= maxn))
+			continue;
+		local = mkname(localbuf, sizeof localbuf, lroot, name);
+		if(strcmp(f[4], "-") == 0)
+			f[4] = f[3];
+		remote = mkname(remotebuf, sizeof remotebuf, rroot, f[4]);
+		rd.name = f[4];
+		rd.mode = strtoul(f[5], 0, 8);
+		rd.uid = f[6];
+		rd.gid = f[7];
+		rd.mtime = strtoul(f[8], 0, 10);
+		rd.length = strtoll(f[9], 0, 10);
+		havedb = finddb(clientdb, name, &dbd)>=0;
+		havelocal = localdirstat(local, &ld)>=0;
+
+		resolve1 = resolve(name);
+
+		/*
+		 * if(!ismatch(name)){
+		 *	skip = 1;
+		 *	continue;
+		 * }
+		 * 
+		 * This check used to be right here, but we want
+		 * the time to be able to move forward past entries
+		 * that don't match and have already been applied.
+		 * So now every path below must checked !ismatch(name)
+		 * before making any changes to the local file
+		 * system.  The fake variable checkedmatch
+		 * tracks whether !ismatch(name) has been checked.
+		 * If the compiler doesn't produce any used/set
+		 * warnings, then all the paths should be okay.
+		 * Even so, we have the asserts to fall back on.
+		 */
+		switch(verb){
+		case 'd':	/* delete file */
+			delce(local);
+			if(!havelocal)	/* doesn't exist; who cares? */
+				break;
+			if(access(remote, AEXIST) >= 0)	/* got recreated! */
+				break;
+			if(!ismatch(name)){
+				if(!skip)
+					fprint(2, "stopped updating log apply time because of %s\n", name);
+				skip = 1;
+				continue;
+			}
+			SET(checkedmatch1);
+			if(!havedb){
+				if(resolve1 == 's')
+					goto DoRemove;
+				else if(resolve1 == 'c')
+					goto DoRemoveDb;
+				conflict(name, "locally created; will not remove");
+				skip = 1;
+				continue;
+			}
+			assert(havelocal && havedb);
+			if(dbd.mtime > rd.mtime)		/* we have a newer file than what was deleted */
+				break;
+			if(samecontents(local, remote) > 0){	/* going to get recreated */
+				chat("= %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+				break;
+			}
+			if(!(dbd.mode&DMDIR) && (dbd.mtime != ld.mtime || dbd.length != ld.length)){	/* locally modified since we downloaded it */
+				if(resolve1 == 's')
+					goto DoRemove;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "locally modified; will not remove");
+				skip = 1;
+				continue;
+			}
+		    DoRemove:
+			USED(checkedmatch1);
+			assert(ismatch(name));
+			chat("d %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+			if(donothing)
+				break;
+			if(remove(local) < 0){
+				error("removing %q: %r", name);
+				skip = 1;
+				continue;
+			}
+		    DoRemoveDb:
+			USED(checkedmatch1);
+			assert(ismatch(name));
+			removedb(clientdb, name);
+			break;
+
+		case 'a':	/* add file */
+			if(!havedb){
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch2);
+				if(!havelocal)
+					goto DoCreate;
+				if((ld.mode&DMDIR) && (rd.mode&DMDIR))
+					break;
+				if(samecontents(local, remote) > 0){
+					chat("= %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+					goto DoCreateDb;
+				}
+				if(resolve1 == 's')
+					goto DoCreate;
+				else if(resolve1 == 'c')
+					goto DoCreateDb;
+				conflict(name, "locally created; will not overwrite");
+				skip = 1;
+				continue;
+			}
+			assert(havedb);
+			if(dbd.mtime >= rd.mtime)	/* already created this file; ignore */
+				break;
+			if(havelocal){
+				if((ld.mode&DMDIR) && (rd.mode&DMDIR))
+					break;
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch2);
+				if(samecontents(local, remote) > 0){
+					chat("= %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+					goto DoCreateDb;
+				}
+				if(dbd.mtime==ld.mtime && dbd.length==ld.length)
+					goto DoCreate;
+				if(resolve1=='s')
+					goto DoCreate;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "locally modified; will not overwrite");
+				skip = 1;
+				continue;
+			}
+			if(!ismatch(name)){
+				if(!skip)
+					fprint(2, "stopped updating log apply time because of %s\n", name);
+				skip = 1;
+				continue;
+			}
+			SET(checkedmatch2);
+		    DoCreate:
+			USED(checkedmatch2);
+			assert(ismatch(name));
+			if(notexists(remote)){
+				addce(local);
+				/* no skip=1 */
+				break;;
+			}
+			chat("a %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+			if(donothing)
+				break;
+			if(rd.mode&DMDIR){
+				fd = create(local, OREAD, DMDIR);
+				if(fd < 0 && isdir(local))
+					fd = open(local, OREAD);
+				if(fd  < 0){
+					error("mkdir %q: %r", name);
+					skip = 1;
+					continue;
+				}
+				nulldir(&nd);
+				nd.mode = rd.mode;
+				if(dirfwstat(fd, &nd) < 0)
+					fprint(2, "warning: cannot set mode on %q\n", local);
+				nulldir(&nd);
+				nd.gid = rd.gid;
+				if(dirfwstat(fd, &nd) < 0)
+					fprint(2, "warning: cannot set gid on %q\n", local);
+				if(douid){
+					nulldir(&nd);
+					nd.uid = rd.uid;
+					if(dirfwstat(fd, &nd) < 0)
+						fprint(2, "warning: cannot set uid on %q\n", local);
+				}
+				close(fd);
+				rd.mtime = now;
+			}else{
+				if(copyfile(local, remote, name, &rd, 1, &k) < 0){
+					if(k)
+						addce(local);
+					skip = 1;
+					continue;
+				}
+			}
+		    DoCreateDb:
+			USED(checkedmatch2);
+			assert(ismatch(name));
+			insertdb(clientdb, name, &rd);
+			break;
+			
+		case 'c':	/* change contents */
+			if(!havedb){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch3);
+				if(resolve1 == 's')
+					goto DoCopy;
+				else if(resolve1=='c')
+					goto DoCopyDb;
+				if(samecontents(local, remote) > 0){
+					chat("= %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+					goto DoCopyDb;
+				}
+				if(havelocal)
+					conflict(name, "locally created; will not update");
+				else
+					conflict(name, "not replicated; will not update");
+				skip = 1;
+				continue;
+			}
+			if(dbd.mtime >= rd.mtime)		/* already have/had this version; ignore */
+				break;
+			if(!ismatch(name)){
+				if(!skip)
+					fprint(2, "stopped updating log apply time because of %s\n", name);
+				skip = 1;
+				continue;
+			}
+			SET(checkedmatch3);
+			if(!havelocal){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(resolve1 == 's')
+					goto DoCopy;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "locally removed; will not update");
+				skip = 1;
+				continue;
+			}
+			assert(havedb && havelocal);
+			if(dbd.mtime != ld.mtime || dbd.length != ld.length){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(samecontents(local, remote) > 0){
+					chat("= %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+					goto DoCopyDb;
+				}
+				if(resolve1 == 's')
+					goto DoCopy;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "locally modified; will not update [%llud %lud -> %llud %lud]", dbd.length, dbd.mtime, ld.length, ld.mtime);
+				skip = 1;
+				continue;
+			}
+		    DoCopy:
+			USED(checkedmatch3);
+			assert(ismatch(name));
+			if(notexists(remote)){
+				addce(local);
+				/* no skip=1 */
+				break;
+			}
+			chat("c %q\n", name);
+			if(donothing)
+				break;
+			if(copyfile(local, remote, name, &rd, 0, &k) < 0){
+				if(k)
+					addce(local);
+				skip = 1;
+				continue;
+			}
+		    DoCopyDb:
+			USED(checkedmatch3);
+			assert(ismatch(name));
+			if(!havedb){
+				if(havelocal)
+					dbd = ld;
+				else
+					dbd = rd;
+			}
+			dbd.mtime = rd.mtime;
+			dbd.length = rd.length;
+			insertdb(clientdb, name, &dbd);
+			break;			
+
+		case 'm':	/* change metadata */
+			if(!havedb){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch4);
+				if(resolve1 == 's'){
+					USED(checkedmatch4);
+					SET(checkedmatch2);
+					goto DoCreate;
+				}
+				else if(resolve1 == 'c')
+					goto DoMetaDb;
+				if(havelocal)
+					conflict(name, "locally created; will not update metadata");
+				else
+					conflict(name, "not replicated; will not update metadata");
+				skip = 1;
+				continue;
+			}
+			if(!(dbd.mode&DMDIR) && dbd.mtime > rd.mtime)		/* have newer version; ignore */
+				break;
+			if((dbd.mode&DMDIR) && dbd.mtime > now)
+				break;
+			if(havelocal && (!douid || strcmp(ld.uid, rd.uid)==0) && strcmp(ld.gid, rd.gid)==0 && ld.mode==rd.mode)
+				break;
+			if(!havelocal){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch4);
+				if(resolve1 == 's'){
+					USED(checkedmatch4);
+					SET(checkedmatch2);
+					goto DoCreate;
+				}
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "locally removed; will not update metadata");
+				skip = 1;
+				continue;
+			}
+			if(!(dbd.mode&DMDIR) && (dbd.mtime != ld.mtime || dbd.length != ld.length)){	/* this check might be overkill */
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch4);
+				if(resolve1 == 's' || samecontents(local, remote) > 0)
+					goto DoMeta;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "contents locally modified (%s); will not update metadata to %s %s %luo",
+					dbd.mtime != ld.mtime ? "mtime" :
+					dbd.length != ld.length ? "length" : 
+					"unknown",
+					rd.uid, rd.gid, rd.mode);
+				skip = 1;
+				continue;
+			}
+			if((douid && strcmp(ld.uid, dbd.uid)!=0) || strcmp(ld.gid, dbd.gid)!=0 || ld.mode!=dbd.mode){
+				if(notexists(remote)){
+					addce(local);
+					/* no skip=1 */
+					break;
+				}
+				if(!ismatch(name)){
+					if(!skip)
+						fprint(2, "stopped updating log apply time because of %s\n", name);
+					skip = 1;
+					continue;
+				}
+				SET(checkedmatch4);
+				if(resolve1 == 's')
+					goto DoMeta;
+				else if(resolve1 == 'c')
+					break;
+				conflict(name, "metadata locally changed; will not update metadata to %s %s %luo", rd.uid, rd.gid, rd.mode);
+				skip = 1;
+				continue;
+			}
+			if(!ismatch(name)){
+				if(!skip)
+					fprint(2, "stopped updating log apply time because of %s\n", name);
+				skip = 1;
+				continue;
+			}
+			SET(checkedmatch4);
+		    DoMeta:
+			USED(checkedmatch4);
+			assert(ismatch(name));
+			if(notexists(remote)){
+				addce(local);
+				/* no skip=1 */
+				break;
+			}
+			chat("m %q %luo %q %q %lud\n", name, rd.mode, rd.uid, rd.gid, rd.mtime);
+			if(donothing)
+				break;
+			nulldir(&nd);
+			nd.gid = rd.gid;
+			nd.mode = rd.mode;
+			if(douid)
+				nd.uid = rd.uid;
+			if(dirwstat(local, &nd) < 0){
+				error("dirwstat %q: %r", name);
+				skip = 1;
+				continue;
+			}
+		    DoMetaDb:
+			USED(checkedmatch4);
+			assert(ismatch(name));
+			if(!havedb){
+				if(havelocal)
+					dbd = ld;
+				else
+					dbd = rd;
+			}
+			if(dbd.mode&DMDIR)
+				dbd.mtime = now;
+			dbd.gid = rd.gid;
+			dbd.mode = rd.mode;
+			if(douid)
+				dbd.uid = rd.uid;
+			insertdb(clientdb, name, &dbd);
+			break;
+		}
+		if(!skip && !donothing){
+			maxnow = now;
+			maxn = n;
+		}
+	}
+
+	w = avlwalk(copyerr->avl);
+	while(e = (Entry*)avlnext(w))
+		error("copying %q: %s\n", e->name, e->d.name);
+
+	if(timefile)
+		writetimefile();
+	if(nconf)
+		exits("conflicts");
+
+	if(errors)
+		exits("errors");
+	exits(nil);
+}
+
+
+char*
+mkname(char *buf, int nbuf, char *a, char *b)
+{
+	if(strlen(a)+strlen(b)+2 > nbuf)
+		sysfatal("name too long");
+
+	strcpy(buf, a);
+	if(a[strlen(a)-1] != '/')
+		strcat(buf, "/");
+	strcat(buf, b);
+	return buf;
+}
+
+int
+isdir(char *s)
+{
+	ulong m;
+	Dir *d;
+
+	if((d = dirstat(s)) == nil)
+		return 0;
+	m = d->mode;
+	free(d);
+	return (m&DMDIR) != 0;
+}
+
+void
+conflict(char *name, char *f, ...)
+{
+	char *s;
+	va_list arg;
+
+	va_start(arg, f);
+	s = vsmprint(f, arg);
+	va_end(arg);
+
+	fprint(2, "! %s: %s\n", name, s);
+	free(s);
+
+	nconf++;
+}
+
+void
+error(char *f, ...)
+{
+	char *s;
+	va_list arg;
+
+	va_start(arg, f);
+	s = vsmprint(f, arg);
+	va_end(arg);
+	fprint(2, "error: %s\n", s);
+	free(s);
+	errors = 1;
+}
+
+int
+ismatch(char *s)
+{
+	int i, len;
+
+	if(nmatch == 0)
+		return 1;
+	for(i=0; i<nmatch; i++){
+		len = strlen(match[i]);
+		if(len == 0)
+			return 1;
+		if(strncmp(s, match[i], len) == 0 && (s[len]=='/' || s[len] == 0))
+			return 1;
+	}
+	return 0;
+}
+
+int
+localdirstat(char *name, Dir *d)
+{
+	static Dir *d2;
+
+	free(d2);
+	if((d2 = dirstat(name)) == nil)
+		return -1;
+	*d = *d2;
+	return 0;
+}
+
+enum { DEFB = 8192 };
+
+static int
+cmp1(int fd1, int fd2)
+{
+	char buf1[DEFB];
+	char buf2[DEFB];
+	int n1, n2;
+	
+	for(;;){
+		n1 = readn(fd1, buf1, DEFB);
+		n2 = readn(fd2, buf2, DEFB);
+		if(n1 < 0 || n2 < 0)
+			return -1;
+		if(n1 != n2)
+			return 0;
+		if(n1 == 0)
+			return 1;
+		if(memcmp(buf1, buf2, n1) != 0)
+			return 0;
+	}
+}
+
+static int
+copy1(int fdf, int fdt, char *from, char *to)
+{
+	int i, n, rv, pid[Nwork];
+	Waitmsg *w;
+
+	n = 0;
+	off = 0;
+	for(i=0; i<Nwork; i++){
+		switch(pid[n] = rfork(RFPROC|RFMEM)){
+		case 0:
+			notify(failure);
+			worker(fdf, fdt, from, to);
+		case -1:
+			break;
+		default:
+			n++;
+			break;
+		}
+	}
+	if(n == 0){
+		fprint(2, "cp: rfork: %r\n");
+		return -1;
+	}
+
+	rv = 0;
+	while((w = wait()) != nil){
+		if(w->msg[0]){
+			rv = -1;
+			for(i=0; i<n; i++)
+				if(pid[i] > 0)
+					postnote(PNPROC, pid[i], "failure");
+		}
+		free(w);
+	}
+	return rv;
+}
+
+void
+worker(int fdf, int fdt, char *from, char *to)
+{
+	char buf[DEFB], *bp;
+	long len, n;
+	vlong o;
+
+	len = sizeof(buf);
+	bp = buf;
+	o = nextoff();
+
+	while(n = pread(fdf, bp, len, o)){
+		if(n < 0){
+			fprint(2, "reading %s: %r\n", from);
+			_exits("bad");
+		}
+		if(pwrite(fdt, buf, n, o) != n){
+			fprint(2, "writing %s: %r\n", to);
+			_exits("bad");
+		}
+		bp += n;
+		o += n;
+		len -= n;
+		if(len == 0){
+			len = sizeof buf;
+			bp = buf;
+			o = nextoff();
+		}
+	}
+	_exits(nil);
+}
+
+vlong
+nextoff(void)
+{
+	vlong o;
+
+	qlock(&lk);
+	o = off;
+	off += DEFB;
+	qunlock(&lk);
+
+	return o;
+}
+
+void
+failure(void*, char *note)
+{
+	if(strcmp(note, "failure") == 0)
+		_exits(nil);
+	noted(NDFLT);
+}
+
+
+static int
+opentemp(char *template)
+{
+	int fd, i;
+	char *p;
+
+	p = estrdup(template);
+	fd = -1;
+	for(i=0; i<10; i++){
+		mktemp(p);
+		if((fd=create(p, ORDWR|OEXCL|ORCLOSE, 0000)) >= 0)
+			break;
+		strcpy(p, template);
+	}
+	if(fd < 0)
+		return -1;
+	strcpy(template, p);
+	free(p);
+	return fd;
+}
+
+int
+copyfile(char *local, char *remote, char *name, Dir *d, int dowstat, int *printerror)
+{
+	Dir *d0, *d1, *dl;
+	Dir nd;
+	int rfd, tfd, wfd, didcreate;
+	char tmp[32], *p, *safe;
+	char err[ERRMAX];
+
+Again:
+	*printerror = 0;
+	if((rfd = open(remote, OREAD)) < 0)
+		return -1;
+
+	d0 = dirfstat(rfd);
+	if(d0 == nil){
+		close(rfd);
+		return -1;
+	}
+	*printerror = 1;
+	if(!tempspool){
+		tfd = rfd;
+		goto DoCopy;
+	}
+	strcpy(tmp, "/tmp/replicaXXXXXXXX");
+	tfd = opentemp(tmp);
+	if(tfd < 0){
+		close(rfd);
+		free(d0);
+		return -1;
+	}
+	if(copy1(rfd, tfd, remote, tmp) < 0 || (d1 = dirfstat(rfd)) == nil){
+		close(rfd);
+		close(tfd);
+		free(d0);
+		return -1;
+	}
+	close(rfd);
+	if(d0->qid.path != d1->qid.path
+	|| d0->qid.vers != d1->qid.vers
+	|| d0->mtime != d1->mtime
+	|| d0->length != d1->length){
+		/* file changed underfoot; go around again */
+		close(tfd);
+		free(d0);
+		free(d1);
+		goto Again;
+	}
+	free(d1);
+	if(seek(tfd, 0, 0) != 0){
+		close(tfd);
+		free(d0);
+		return -1;
+	}
+
+DoCopy:
+	/*
+	 * clumsy but important hack to do safeinstall-like installs.
+	 */
+	p = strchr(name, '/');
+	if(safeinstall && p && strncmp(p, "/bin/", 5) == 0 && access(local, AEXIST) >= 0){
+		/* 
+		 * remove bin/_targ
+		 */
+		safe = emalloc(strlen(local)+2);
+		strcpy(safe, local);
+		p = strrchr(safe, '/')+1;
+		memmove(p+1, p, strlen(p)+1);
+		p[0] = '_';
+		remove(safe);	/* ignore failure */
+
+		/*
+		 * rename bin/targ to bin/_targ
+		 */
+		nulldir(&nd);
+		nd.name = p;
+		if(dirwstat(local, &nd) < 0)
+			fprint(2, "warning: rename %s to %s: %r\n", local, p);
+	}
+
+	didcreate = 0;
+	if((dl = dirstat(local)) == nil){
+		if((wfd = create(local, OWRITE, 0)) >= 0){
+			didcreate = 1;
+			goto okay;
+		}
+		goto err;
+	}else{
+		if((wfd = open(local, OTRUNC|OWRITE)) >= 0)
+			goto okay;
+		rerrstr(err, sizeof err);
+		if(strstr(err, "permission") == nil)
+			goto err;
+		nulldir(&nd);
+		/*
+		 * Assume the person running pull is in the appropriate
+		 * groups.  We could set 0666 instead, but I'm worried
+		 * about leaving the file world-readable or world-writable
+		 * when it shouldn't be.
+		 */
+		nd.mode = dl->mode | 0660;
+		if(nd.mode == dl->mode)
+			goto err;
+		if(dirwstat(local, &nd) < 0)
+			goto err;
+		if((wfd = open(local, OTRUNC|OWRITE)) >= 0){
+			nd.mode = dl->mode;
+			if(dirfwstat(wfd, &nd) < 0)
+				fprint(2, "warning: set mode on %s to 0660 to open; cannot set back to %luo: %r\n", local, nd.mode);
+			goto okay;
+		}
+		nd.mode = dl->mode;
+		if(dirwstat(local, &nd) < 0)
+			fprint(2, "warning: set mode on %s to %luo to open; open failed; cannot set mode back to %luo: %r\n", local, nd.mode|0660, nd.mode);
+		goto err;
+	}
+		
+err:
+	close(tfd);
+	free(d0);
+	free(dl);
+	return -1;
+
+okay:
+	free(dl);
+	if(copy1(tfd, wfd, tmp, local) < 0){
+		close(tfd);
+		close(wfd);
+		free(d0);
+		return -1;
+	}
+	close(tfd);
+	if(didcreate || dowstat){
+		nulldir(&nd);
+		nd.mode = d->mode;
+		if(dirfwstat(wfd, &nd) < 0)
+			fprint(2, "warning: cannot set mode on %s\n", local);
+		nulldir(&nd);
+		nd.gid = d->gid;
+		if(dirfwstat(wfd, &nd) < 0)
+			fprint(2, "warning: cannot set gid on %s\n", local);
+		if(douid){
+			nulldir(&nd);
+			nd.uid = d->uid;
+			if(dirfwstat(wfd, &nd) < 0)
+				fprint(2, "warning: cannot set uid on %s\n", local);
+		}
+	}
+	d->mtime = d0->mtime;
+	d->length = d0->length;
+	nulldir(&nd);
+	nd.mtime = d->mtime;
+	if(dirfwstat(wfd, &nd) < 0)
+		fprint(2, "warning: cannot set mtime on %s\n", local);
+	free(d0);
+
+	close(wfd);
+	return 0;
+}
+
+int
+samecontents(char *local, char *remote)
+{
+	Dir *d0, *d1;
+	int rfd, tfd, lfd, ret;
+	char tmp[32];
+
+	/* quick check: sizes must match */
+	d1 = nil;
+	if((d0 = dirstat(local)) == nil || (d1 = dirstat(remote)) == nil){
+		free(d0);
+		free(d1);
+		return -1;
+	}
+	if(d0->length != d1->length){
+		free(d0);
+		free(d1);
+		return 0;
+	}
+
+Again:
+	if((rfd = open(remote, OREAD)) < 0)
+		return -1;
+	d0 = dirfstat(rfd);
+	if(d0 == nil){
+		close(rfd);
+		return -1;
+	}
+
+	strcpy(tmp, "/tmp/replicaXXXXXXXX");
+	tfd = opentemp(tmp);
+	if(tfd < 0){
+		close(rfd);
+		free(d0);
+		return -1;
+	}
+	if(copy1(rfd, tfd, remote, tmp) < 0 || (d1 = dirfstat(rfd)) == nil){
+		close(rfd);
+		close(tfd);
+		free(d0);
+		return -1;
+	}
+	close(rfd);
+	if(d0->qid.path != d1->qid.path
+	|| d0->qid.vers != d1->qid.vers
+	|| d0->mtime != d1->mtime
+	|| d0->length != d1->length){
+		/* file changed underfoot; go around again */
+		close(tfd);
+		free(d0);
+		free(d1);
+		goto Again;
+	}
+	free(d1);
+	free(d0);
+	if(seek(tfd, 0, 0) != 0){
+		close(tfd);
+		return -1;
+	}
+
+	/*
+	 * now compare
+	 */
+	if((lfd = open(local, OREAD)) < 0){
+		close(tfd);
+		return -1;
+	}
+	
+	ret = cmp1(lfd, tfd);
+	close(lfd);
+	close(tfd);
+	return ret;
+}
+
+/*
+ * Applylog might try to overwrite itself.
+ * To avoid problems with this, we copy ourselves
+ * into /tmp and then re-exec.
+ */
+char *rmargv0;
+
+static void
+rmself(void)
+{
+	remove(rmargv0);
+}
+
+static int
+genopentemp(char *template, int mode, int perm)
+{
+	int fd, i;
+	char *p;	
+
+	p = estrdup(template);
+	fd = -1;
+	for(i=0; i<10; i++){
+		mktemp(p);
+		if(access(p, 0) < 0 && (fd=create(p, mode, perm)) >= 0)
+			break;
+		strcpy(p, template);
+	}
+	if(fd < 0)
+		sysfatal("could not create temporary file");
+
+	strcpy(template, p);
+	free(p);
+
+	return fd;
+}
+
+static void
+membogus(char **argv)
+{
+	int n, fd, wfd;
+	char template[50], buf[1024];
+
+	if(strncmp(argv[0], "/tmp/_applylog_", 1+3+1+1+8+1)==0) {
+		rmargv0 = argv[0];
+		atexit(rmself);
+		return;
+	}
+
+	if((fd = open(argv[0], OREAD)) < 0)
+		return;
+
+	strcpy(template, "/tmp/_applylog_XXXXXX");
+	if((wfd = genopentemp(template, OWRITE, 0700)) < 0)
+		return;
+
+	while((n = read(fd, buf, sizeof buf)) > 0)
+		if(write(wfd, buf, n) != n)
+			goto Error;
+
+	if(n != 0)
+		goto Error;
+
+	close(fd);
+	close(wfd);
+
+	argv[0] = template;
+	exec(template, argv);
+	fprint(2, "exec error %r\n");
+
+Error:
+	close(fd);
+	close(wfd);
+	remove(template);
+	return;
+}
diff --git a/sys/src/cmd/replica/avl.c b/sys/src/cmd/replica/avl.c
new file mode 100755
index 000000000..42391ac89
--- /dev/null
+++ b/sys/src/cmd/replica/avl.c
@@ -0,0 +1,415 @@
+#include "all.h"
+
+/*
+ * In-memory database stored as self-balancing AVL tree.
+ * See Lewis & Denenberg, Data Structures and Their Algorithms.
+ */
+static void
+singleleft(Avl **tp, Avl *p)
+{
+	Avl *a, *c;
+	int l, r2;
+
+	a = *tp;
+	c = a->n[1];
+
+	r2 = c->bal;
+	l = (r2 > 0 ? r2 : 0)+1 - a->bal;
+
+	if((a->n[1] = c->n[0]) != nil)
+		a->n[1]->p = a;
+
+	if((c->n[0] = a) != nil)
+		c->n[0]->p = c;
+
+	if((*tp = c) != nil)
+		(*tp)->p = p;
+
+	a->bal = -l;
+	c->bal = r2 - ((l > 0 ? l : 0)+1);
+
+}
+
+static void
+singleright(Avl **tp, Avl *p)
+{
+	Avl *a, *c;
+	int l2, r;
+
+	a = *tp;
+	c = a->n[0];
+	l2 = - c->bal;
+	r = a->bal + ((l2 > 0 ? l2 : 0)+1);
+
+	if((a->n[0] = c->n[1]) != nil)
+		a->n[0]->p = a;
+
+	if((c->n[1] = a) != nil)
+		c->n[1]->p = c;
+
+	if((*tp = c) != nil)
+		(*tp)->p = p;
+
+	a->bal = r;
+	c->bal = ((r > 0 ? r : 0)+1) - l2;
+}
+
+static void
+doublerightleft(Avl **tp, Avl *p)
+{
+	singleright(&(*tp)->n[1], *tp);
+	singleleft(tp, p);
+}
+
+static void
+doubleleftright(Avl **tp, Avl *p)
+{
+	singleleft(&(*tp)->n[0], *tp);
+	singleright(tp, p);
+}
+
+static void
+balance(Avl **tp, Avl *p)
+{
+	switch((*tp)->bal){
+	case -2:
+		if((*tp)->n[0]->bal <= 0)
+			singleright(tp, p);
+		else if((*tp)->n[0]->bal == 1)
+			doubleleftright(tp, p);
+		else
+			assert(0);
+		break;
+
+	case 2:
+		if((*tp)->n[1]->bal >= 0)
+			singleleft(tp, p);
+		else if((*tp)->n[1]->bal == -1)
+			doublerightleft(tp, p);
+		else
+			assert(0);
+		break;
+	}
+}
+
+static int
+canoncmp(int cmp)
+{
+	if(cmp < 0)
+		return -1;
+	else if(cmp > 0)
+		return 1;
+	return 0;
+}
+
+static int
+_insertavl(Avl **tp, Avl *p, Avl *r, int (*cmp)(Avl*,Avl*), Avl **rfree)
+{
+	int i, ob;
+
+	if(*tp == nil){
+		r->bal = 0;
+		r->n[0] = nil;
+		r->n[1] = nil;
+		r->p = p;
+		*tp = r;
+		return 1;
+	}
+	ob = (*tp)->bal;
+	if((i=canoncmp(cmp(r, *tp))) != 0){
+		(*tp)->bal += i*_insertavl(&(*tp)->n[(i+1)/2], *tp, r, cmp, rfree);
+		balance(tp, p);
+		return ob==0 && (*tp)->bal != 0;
+	}
+
+	/* install new entry */
+	*rfree = *tp;	/* save old node for freeing */
+	*tp = r;		/* insert new node */
+	**tp = **rfree;	/* copy old node's Avl contents */
+	if(r->n[0])		/* fix node's children's parent pointers */
+		r->n[0]->p = r;
+	if(r->n[1])
+		r->n[1]->p = r;
+
+	return 0;
+}
+
+static Avl*
+_lookupavl(Avl *t, Avl *r, int (*cmp)(Avl*,Avl*))
+{
+	int i;
+	Avl *p;
+
+	p = nil;
+	while(t != nil){
+		assert(t->p == p);
+		if((i=canoncmp(cmp(r, t)))==0)
+			return t;
+		p = t;
+		t = t->n[(i+1)/2];
+	}
+	return nil;
+}
+
+static int
+successor(Avl **tp, Avl *p, Avl **r)
+{
+	int ob;
+
+	if((*tp)->n[0] == nil){
+		*r = *tp;
+		*tp = (*r)->n[1];
+		if(*tp)
+			(*tp)->p = p;
+		return -1;
+	}
+	ob = (*tp)->bal;
+	(*tp)->bal -= successor(&(*tp)->n[0], *tp, r);
+	balance(tp, p);
+	return -(ob!=0 && (*tp)->bal==0);
+}
+
+static int
+_deleteavl(Avl **tp, Avl *p, Avl *rx, int(*cmp)(Avl*,Avl*), Avl **del, void (*predel)(Avl*, void*), void *arg)
+{
+	int i, ob;
+	Avl *r, *or;
+
+	if(*tp == nil)
+		return 0;
+
+	ob = (*tp)->bal;
+	if((i=canoncmp(cmp(rx, *tp))) != 0){
+		(*tp)->bal += i*_deleteavl(&(*tp)->n[(i+1)/2], *tp, rx, cmp, del, predel, arg);
+		balance(tp, p);
+		return -(ob!=0 && (*tp)->bal==0);
+	}
+
+	if(predel)
+		(*predel)(*tp, arg);
+
+	or = *tp;
+	if(or->n[i=0]==nil || or->n[i=1]==nil){
+		*tp = or->n[1-i];
+		if(*tp)
+			(*tp)->p = p;
+		*del = or;
+		return -1;
+	}
+
+	/* deleting node with two kids, find successor */
+	or->bal += successor(&or->n[1], or, &r);
+	r->bal = or->bal;
+	r->n[0] = or->n[0];
+	r->n[1] = or->n[1];
+	*tp = r;
+	(*tp)->p = p;
+	/* node has changed; fix children's parent pointers */
+	if(r->n[0])
+		r->n[0]->p = r;
+	if(r->n[1])
+		r->n[1]->p = r;
+	*del = or;
+	balance(tp, p);
+	return -(ob!=0 && (*tp)->bal==0);
+}
+
+static void
+checkparents(Avl *a, Avl *p)
+{
+	if(a==nil)
+		return;
+	if(a->p != p)
+		print("bad parent\n");
+	checkparents(a->n[0], a);
+	checkparents(a->n[1], a);
+}
+
+struct Avltree
+{
+	Avl *root;
+	int (*cmp)(Avl*, Avl*);
+	Avlwalk *walks;
+};
+struct Avlwalk
+{
+	int started;
+	int moved;
+	Avlwalk *next;
+	Avltree *tree;
+	Avl *node;
+};
+
+
+Avltree*
+mkavltree(int (*cmp)(Avl*, Avl*))
+{
+	Avltree *t;
+
+	t = emalloc(sizeof(*t));
+	t->cmp = cmp;
+	return t;
+}
+
+void
+insertavl(Avltree *t, Avl *new, Avl **oldp)
+{
+	*oldp = nil;
+	_insertavl(&t->root, nil, new, t->cmp, oldp);
+}
+
+Avl*
+lookupavl(Avltree *t, Avl *key)
+{
+	return _lookupavl(t->root, key, t->cmp);
+}
+
+static Avl*
+findpredecessor(Avl *a)
+{
+
+	if(a == nil)
+		return nil;
+
+	if(a->n[0] != nil){
+		/* predecessor is rightmost descendant of left child */
+		for(a=a->n[0]; a->n[1]; a=a->n[1])
+			;
+		return a;
+	}else{
+		/* we're at a leaf, successor is a parent we enter from the right */
+		while(a->p && a->p->n[0]==a)
+			a = a->p;
+		return a->p;
+	}
+}		
+
+static Avl*
+findsuccessor(Avl *a)
+{
+
+	if(a == nil)
+		return nil;
+
+	if(a->n[1] != nil){
+		/* successor is leftmost descendant of right child */
+		for(a=a->n[1]; a->n[0]; a=a->n[0])
+			;
+		return a;
+	}else{
+		/* we're at a leaf, successor is a parent we enter from the left going up */
+		while(a->p && a->p->n[1] == a)
+			a = a->p;
+		return a->p;
+	}
+}
+
+static void
+walkdel(Avl *a, void *v)
+{
+	Avl *p;
+	Avlwalk *w;
+	Avltree *t;
+
+	if(a == nil)
+		return;
+
+	p = findpredecessor(a);
+	t = v;
+	for(w=t->walks; w; w=w->next){
+		if(w->node == a){
+			/* back pointer to predecessor; not perfect but adequate */
+			w->moved = 1;
+			w->node = p;
+			if(p == nil)
+				w->started = 0;
+		}
+	}
+}
+
+void
+deleteavl(Avltree *t, Avl *key, Avl **oldp)
+{
+	*oldp = nil;
+	_deleteavl(&t->root, nil, key, t->cmp, oldp, walkdel, t);
+}
+
+Avlwalk*
+avlwalk(Avltree *t)
+{
+	Avlwalk *w;
+
+	w = emalloc(sizeof(*w));
+	w->tree = t;
+	w->next = t->walks;
+	t->walks = w;
+	return w;
+}
+
+Avl*
+avlnext(Avlwalk *w)
+{
+	Avl *a;
+
+	if(w->started==0){
+		for(a=w->tree->root; a && a->n[0]; a=a->n[0])
+			;
+		w->node = a;
+		w->started = 1;
+	}else{
+		a = findsuccessor(w->node);
+		if(a == w->node)
+			abort();
+		w->node = a;
+	}
+	return w->node;
+}
+
+Avl*
+avlprev(Avlwalk *w)
+{
+	Avl *a;
+
+	if(w->started == 0){
+		for(a=w->tree->root; a && a->n[1]; a=a->n[1])
+			;
+		w->node = a;
+		w->started = 1;
+	}else if(w->moved){
+		w->moved = 0;
+		return w->node;
+	}else{
+		a = findpredecessor(w->node);
+		if(a == w->node)
+			abort();
+		w->node = a;
+	}
+	return w->node;
+}
+
+void
+endwalk(Avlwalk *w)
+{
+	Avltree *t;
+	Avlwalk **l;
+
+	t = w->tree;
+	for(l=&t->walks; *l; l=&(*l)->next){
+		if(*l == w){
+			*l = w->next;
+			break;
+		}
+	}
+	free(w);
+}
+
+static void
+walkavl(Avl *t, void (*f)(Avl*, void*), void *v)
+{
+	if(t == nil)
+		return;
+	walkavl(t->n[0], f, v);
+	f(t, v);
+	walkavl(t->n[1], f, v);
+}
+
diff --git a/sys/src/cmd/replica/compactdb.c b/sys/src/cmd/replica/compactdb.c
new file mode 100755
index 000000000..df9af7809
--- /dev/null
+++ b/sys/src/cmd/replica/compactdb.c
@@ -0,0 +1,42 @@
+/*
+ * compact a database file
+ */
+#include "all.h"
+
+Db *db;
+
+void
+usage(void)
+{
+	fprint(2, "usage: replica/compactdb db\n");
+	exits("usage");
+}
+
+void
+main(int argc, char **argv)
+{
+	Avlwalk *w;
+	Biobuf bout;
+	Entry *e;
+
+	quotefmtinstall();
+	ARGBEGIN{
+	default:
+		usage();
+	}ARGEND
+
+	if(argc != 1)
+		usage();
+
+	Binit(&bout, 1, OWRITE);
+	db = opendb(argv[0]);
+	w = avlwalk(db->avl);
+	while(e = (Entry*)avlnext(w))
+		Bprint(&bout, "%q %q %luo %q %q %lud %lld\n",
+			e->name, strcmp(e->name, e->d.name)==0 ? "-" : e->d.name, e->d.mode,
+			e->d.uid, e->d.gid, e->d.mtime, e->d.length);
+	if(Bterm(&bout) < 0)
+		sysfatal("writing output: %r");
+
+	exits(nil);
+}
diff --git a/sys/src/cmd/replica/db.c b/sys/src/cmd/replica/db.c
new file mode 100755
index 000000000..29e6b0a39
--- /dev/null
+++ b/sys/src/cmd/replica/db.c
@@ -0,0 +1,179 @@
+#include "all.h"
+
+static Entry *fe;
+
+static Entry*
+allocentry(void)
+{
+	int i;
+	Entry *e;
+
+	if(fe == nil){
+		fe = emalloc(128*sizeof(Entry));
+		for(i=0; i<128-1; i++)
+			fe[i].name = (char*)&fe[i+1];
+		fe[i].name = nil;
+	}
+
+	e = fe;
+	fe = (Entry*)e->name;
+	memset(e, 0, sizeof *e);
+	return e;
+}
+
+static void
+freeentry(Entry *e)
+{
+	e->name = (char*)fe;
+	fe = e;
+}
+
+static void
+_removedb(Db *db, char *name)
+{
+	Entry *e, k;
+
+	memset(&k, 0, sizeof k);
+	k.name = name;
+	e = nil;
+	deleteavl(db->avl, (Avl*)&k, (Avl**)&e);
+	if(e)
+		freeentry(e);
+}
+
+static void
+_insertdb(Db *db, Entry *e)
+{
+	Entry *o, *ne;
+
+	ne = allocentry();
+	*ne = *e;
+	o = nil;
+	insertavl(db->avl, (Avl*)ne, (Avl**)&o);
+	if(o)
+		freeentry(o);
+}
+
+static int
+entrycmp(Avl *a, Avl *b)
+{
+	Entry *ea, *eb;
+
+	ea = (Entry*)a;
+	eb = (Entry*)b;
+	return strcmp(ea->name, eb->name);
+}
+
+Db*
+opendb(char *file)
+{
+	char *f[10], *s, *t;
+	int i, fd, nf;
+	Biobuf b;
+	Db *db;
+	Entry e;
+
+	if(file == nil)
+		fd = -1;
+	else if((fd = open(file, ORDWR)) < 0)
+		sysfatal("opendb %s: %r", file);
+	db = emalloc(sizeof(Db));
+	db->avl = mkavltree(entrycmp);
+	db->fd = fd;
+	if(fd < 0)
+		return db;
+	Binit(&b, fd, OREAD);
+	i = 0;
+	for(; s=Brdstr(&b, '\n', 1); free(s)){
+		t = estrdup(s);
+		nf = tokenize(s, f, nelem(f));
+		if(nf != 7)
+			sysfatal("bad database entry '%s'", t);
+		free(t);
+		if(strcmp(f[2], "REMOVED") == 0)
+			_removedb(db, f[0]);
+		else{
+			memset(&e, 0, sizeof e);
+			e.name = atom(f[0]);
+			e.d.name = atom(f[1]);
+			if(strcmp(e.d.name, "-")==0)
+				e.d.name = e.name;
+			e.d.mode = strtoul(f[2], 0, 8);
+			e.d.uid = atom(f[3]);
+			e.d.gid = atom(f[4]);
+			e.d.mtime = strtoul(f[5], 0, 10);
+			e.d.length = strtoll(f[6], 0, 10);
+			_insertdb(db, &e);
+			i++;
+		}
+	}
+	return db;
+}
+
+static int
+_finddb(Db *db, char *name, Dir *d, int domark)
+{
+	Entry *e, k;
+
+	memset(&k, 0, sizeof k);
+	k.name = name;
+
+	e = (Entry*)lookupavl(db->avl, (Avl*)&k);
+	if(e == nil)
+		return -1;
+	memset(d, 0, sizeof *d);
+	d->name = e->d.name;
+	d->uid = e->d.uid;
+	d->gid = e->d.gid;
+	d->mtime = e->d.mtime;
+	d->mode = e->d.mode;
+	d->length = e->d.length;
+	if(domark)
+		e->d.mark = 1;
+	return 0;
+}
+
+int
+finddb(Db *db, char *name, Dir *d)
+{
+	return _finddb(db, name, d, 0);
+}
+
+int
+markdb(Db *db, char *name, Dir *d)
+{
+	return _finddb(db, name, d, 1);
+}
+
+void
+removedb(Db *db, char *name)
+{
+	if(db->fd>=0 && fprint(db->fd, "%q xxx REMOVED xxx xxx 0 0\n", name) < 0)
+		sysfatal("appending to db: %r");
+	_removedb(db, name);
+}
+
+void
+insertdb(Db *db, char *name, Dir *d)
+{
+	char *dname;
+	Entry e;
+
+	memset(&e, 0, sizeof e);
+	e.name = atom(name);
+	e.d.name = atom(d->name);
+	e.d.uid = atom(d->uid);
+	e.d.gid = atom(d->gid);
+	e.d.mtime = d->mtime;
+	e.d.mode = d->mode;
+	e.d.length = d->length;
+	e.d.mark = d->muid!=0;
+
+	dname = d->name;
+	if(strcmp(name, dname) == 0)
+		dname = "-";
+	if(db->fd>=0 && fprint(db->fd, "%q %q %luo %q %q %lud %lld\n", name, dname, d->mode, d->uid, d->gid, d->mtime, d->length) < 0)
+		sysfatal("appending to db: %r");
+	_insertdb(db, &e);
+}
+
diff --git a/sys/src/cmd/replica/mkfile b/sys/src/cmd/replica/mkfile
new file mode 100755
index 000000000..966bd5c78
--- /dev/null
+++ b/sys/src/cmd/replica/mkfile
@@ -0,0 +1,49 @@
+</$objtype/mkfile
+
+SCRIPTS=\
+	changes\
+	pull\
+	push\
+	scan\
+	setupdirs\
+	
+TARG=\
+	applychanges\
+	applylog\
+	compactdb\
+	updatedb\
+	$SCRIPTS\
+
+OFILES=\
+	avl.$O\
+	db.$O\
+	util.$O\
+
+HFILES=all.h
+
+UPDATE=\
+	mkfile\
+	/sys/man/1/replica\
+	/sys/man/8/replica\
+	${OFILES:%.$O=%.c}\
+	revproto.c\
+	$HFILES\
+	applychanges.c\
+	updatedb.c\
+	${TARG:%=/386/bin/replica/%}\
+	${SCRIPTS:%=/rc/bin/replica/%}\
+	/rc/bin/replica/defs\
+
+
+BIN=/$objtype/bin/replica
+</sys/src/cmd/mkmany
+
+$O.applychanges: revproto.$O
+
+${SCRIPTS:%=$BIN/%}:
+	{ echo '#!/bin/rc'; echo 'exec /rc/bin/replica/'^`{basename $target}^' $*' } >$target
+	chmod +x $target
+
+${SCRIPTS:%=$O.%}:QV:
+	;
+
diff --git a/sys/src/cmd/replica/revdump.c b/sys/src/cmd/replica/revdump.c
new file mode 100755
index 000000000..e94443750
--- /dev/null
+++ b/sys/src/cmd/replica/revdump.c
@@ -0,0 +1,40 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <disk.h>
+
+static void
+enm(char *new, char *old, Dir *d, void*)
+{
+	print("%s %s%s%s%luo %s %s %s\n",
+		new, (d->mode&DMDIR)?"d":"", (d->mode&DMAPPEND)?"a":"",
+		(d->mode&DMEXCL)?"l":"", (d->mode&~(DMDIR|DMAPPEND|DMEXCL)), 
+		d->uid, d->gid, old);
+}
+
+static void
+usage(void)
+{
+	fprint(2, "usage: protodump [-r root] proto\n");
+	exits("usage");
+}
+
+void
+main(int argc, char **argv)
+{
+	char *root;
+
+	root = "/";
+	ARGBEGIN{
+	case 'r':
+		root = EARGF(usage());
+		break;
+	}ARGEND
+
+	if(argc != 1)
+		usage();
+
+	if(revrdproto(argv[0], root, enm, nil, nil) < 0)
+		sysfatal("rdproto: %r");
+	exits(nil);
+}
diff --git a/sys/src/cmd/replica/revproto.c b/sys/src/cmd/replica/revproto.c
new file mode 100755
index 000000000..36704d786
--- /dev/null
+++ b/sys/src/cmd/replica/revproto.c
@@ -0,0 +1,512 @@
+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <auth.h>
+#include <fcall.h>
+#include <disk.h>
+
+enum {
+	LEN	= 8*1024,
+	HUNKS	= 128,
+};
+
+typedef struct File File;
+struct File{
+	char	*new;
+	char	*elem;
+	char	*old;
+	char	*uid;
+	char	*gid;
+	ulong	mode;
+};
+
+typedef void Mkfserr(char*, void*);
+typedef void Mkfsenum(char*, char*, Dir*, void*);
+
+typedef struct Name Name;
+struct Name {
+	int n;
+	char *s;
+};
+
+typedef struct Mkaux Mkaux;
+struct Mkaux {
+	Mkfserr *warn;
+	Mkfsenum *mkenum;
+	char *root;
+	char *xroot;
+	char *proto;
+	jmp_buf jmp;
+	Biobuf *b;
+
+	Name oldfile;
+	Name fullname;
+	int	lineno;
+	int	indent;
+
+	void *a;
+};
+
+static void domkfs(Mkaux *mkaux, File *me, int level);
+
+static int	copyfile(Mkaux*, File*, Dir*, int);
+static void	freefile(File*);
+static File*	getfile(Mkaux*, File*);
+static char*	getmode(Mkaux*, char*, ulong*);
+static char*	getname(Mkaux*, char*, char**);
+static char*	getpath(Mkaux*, char*);
+static int	mkfile(Mkaux*, File*);
+static char*	mkpath(Mkaux*, char*, char*);
+static void	mktree(Mkaux*, File*, int);
+static void	setnames(Mkaux*, File*);
+static void	skipdir(Mkaux*);
+static void	warn(Mkaux*, char *, ...);
+
+//static void
+//mprint(char *new, char *old, Dir *d, void*)
+//{
+//	print("%s %s %D\n", new, old, d);
+//}
+
+int
+revrdproto(char *proto, char *root, char *xroot, Mkfsenum *mkenum, Mkfserr *mkerr, void *a)
+{
+	Mkaux mx, *m;
+	File file;
+	int rv;
+
+	m = &mx;
+	memset(&mx, 0, sizeof mx);
+	if(root == nil)
+		root = "/";
+
+	m->root = root;
+	m->xroot = xroot;
+	m->warn = mkerr;
+	m->mkenum = mkenum;
+	m->a = a;
+	m->proto = proto;
+	m->lineno = 0;
+	m->indent = 0;
+	if((m->b = Bopen(proto, OREAD)) == nil) {
+		werrstr("open '%s': %r", proto);
+		return -1;
+	}
+
+	memset(&file, 0, sizeof file);
+	file.new = "";
+	file.old = nil;
+
+	rv = 0;
+	if(setjmp(m->jmp) == 0)
+		domkfs(m, &file, -1);
+	else
+		rv = -1;
+	free(m->oldfile.s);
+	free(m->fullname.s);
+	return rv;
+}
+
+static void*
+emalloc(Mkaux *mkaux, ulong n)
+{
+	void *v;
+
+	v = malloc(n);
+	if(v == nil)
+		longjmp(mkaux->jmp, 1);	/* memory leak */
+	memset(v, 0, n);
+	return v;
+}
+
+static char*
+estrdup(Mkaux *mkaux, char *s)
+{
+	s = strdup(s);
+	if(s == nil)
+		longjmp(mkaux->jmp, 1);	/* memory leak */
+	return s;
+}
+
+static void
+domkfs(Mkaux *mkaux, File *me, int level)
+{
+	File *child;
+	int rec;
+
+	child = getfile(mkaux, me);
+	if(!child)
+		return;
+	if((child->elem[0] == '+' || child->elem[0] == '*') && child->elem[1] == '\0'){
+		rec = child->elem[0] == '+';
+		free(child->new);
+		child->new = estrdup(mkaux, me->new);
+		setnames(mkaux, child);
+		mktree(mkaux, child, rec);
+		freefile(child);
+		child = getfile(mkaux, me);
+	}
+	while(child && mkaux->indent > level){
+		if(mkfile(mkaux, child))
+			domkfs(mkaux, child, mkaux->indent);
+		freefile(child);
+		child = getfile(mkaux, me);
+	}
+	if(child){
+		freefile(child);
+		Bseek(mkaux->b, -Blinelen(mkaux->b), 1);
+		mkaux->lineno--;
+	}
+}
+
+enum {
+	SLOP = 30
+};
+
+static void
+setname(Mkaux *mkaux, Name *name, char *s1, char *s2)
+{
+	int l;
+
+	l = strlen(s1)+strlen(s2)+1;
+	if(name->n < l) {
+		free(name->s);
+		name->s = emalloc(mkaux, l+SLOP);
+		name->n = l+SLOP;
+	}
+	snprint(name->s, name->n, "%s%s%s", s1, s2[0] && s2[0]!='/' ? "/" : "", s2);
+}
+
+static void
+mktree(Mkaux *mkaux, File *me, int rec)
+{
+	File child;
+	Dir *d;
+	int i, n, fd;
+
+	setname(mkaux, &mkaux->fullname, mkaux->root, me->new);
+	fd = open(mkaux->fullname.s, OREAD);
+	if(fd < 0){
+		warn(mkaux, "can't open %s: %r", mkaux->fullname.s);
+		return;
+	}
+
+	child = *me;
+	while((n = dirread(fd, &d)) > 0){
+		for(i = 0; i < n; i++){
+			child.new = mkpath(mkaux, me->new, d[i].name);
+			if(me->old)
+				child.old = mkpath(mkaux, me->old, d[i].name);
+			child.elem = d[i].name;
+			setnames(mkaux, &child);
+			if(copyfile(mkaux, &child, &d[i], 1) && rec)
+				mktree(mkaux, &child, rec);
+			free(child.new);
+			if(child.old)
+				free(child.old);
+		}
+	}
+	close(fd);
+}
+
+static int
+mkfile(Mkaux *mkaux, File *f)
+{
+	Dir *d;
+
+	setname(mkaux, &mkaux->fullname, mkaux->root, f->new);
+	if((d = dirstat(mkaux->fullname.s)) == nil){
+		warn(mkaux, "can't stat file %s: %r", mkaux->fullname.s);
+		skipdir(mkaux);
+		return 0;
+	}
+	return copyfile(mkaux, f, d, 0);
+}
+
+static int
+copyfile(Mkaux *mkaux, File *f, Dir *d, int permonly)
+{
+	Dir *nd;
+	ulong xmode;
+	char *p;
+
+	/*
+	 * Extra stat here is inefficient but accounts for binds.
+	 */
+	setname(mkaux, &mkaux->fullname, mkaux->root, f->new);
+	if((nd = dirstat(mkaux->fullname.s)) != nil)
+		d = nd;
+
+	setname(mkaux, &mkaux->fullname, mkaux->xroot, f->old ? f->old : f->new);
+	d->name = f->elem;
+	if(d->type != 'M'){
+		d->uid = "sys";
+		d->gid = "sys";
+		xmode = (d->mode >> 6) & 7;
+		d->mode |= xmode | (xmode << 3);
+	}
+	if(strcmp(f->uid, "-") != 0)
+		d->uid = f->uid;
+	if(strcmp(f->gid, "-") != 0)
+		d->gid = f->gid;
+	if(f->mode != ~0){
+		if(permonly)
+			d->mode = (d->mode & ~0666) | (f->mode & 0666);
+		else if((d->mode&DMDIR) != (f->mode&DMDIR))
+			warn(mkaux, "inconsistent mode for %s", f->new);
+		else
+			d->mode = f->mode;
+	}
+
+	if(p = strrchr(f->new, '/'))
+		d->name = p+1;
+	else
+		d->name = f->new;
+
+	mkaux->mkenum(f->new, mkaux->fullname.s, d, mkaux->a);
+	xmode = d->mode;
+	free(nd);
+	return (xmode&DMDIR) != 0;
+}
+
+static char *
+mkpath(Mkaux *mkaux, char *prefix, char *elem)
+{
+	char *p;
+	int n;
+
+	n = strlen(prefix) + strlen(elem) + 2;
+	p = emalloc(mkaux, n);
+	strcpy(p, prefix);
+	strcat(p, "/");
+	strcat(p, elem);
+	return p;
+}
+
+static void
+setnames(Mkaux *mkaux, File *f)
+{
+	
+	if(f->old){
+		if(f->old[0] == '/')
+			setname(mkaux, &mkaux->oldfile, f->old, "");
+		else
+			setname(mkaux, &mkaux->oldfile, mkaux->xroot, f->old);
+	} else
+		setname(mkaux, &mkaux->oldfile, mkaux->xroot, f->new);
+}
+
+static void
+freefile(File *f)
+{
+	if(f->old)
+		free(f->old);
+	if(f->new)
+		free(f->new);
+	free(f);
+}
+
+/*
+ * skip all files in the proto that
+ * could be in the current dir
+ */
+static void
+skipdir(Mkaux *mkaux)
+{
+	char *p, c;
+	int level;
+
+	if(mkaux->indent < 0)
+		return;
+	level = mkaux->indent;
+	for(;;){
+		mkaux->indent = 0;
+		p = Brdline(mkaux->b, '\n');
+		mkaux->lineno++;
+		if(!p){
+			mkaux->indent = -1;
+			return;
+		}
+		while((c = *p++) != '\n')
+			if(c == ' ')
+				mkaux->indent++;
+			else if(c == '\t')
+				mkaux->indent += 8;
+			else
+				break;
+		if(mkaux->indent <= level){
+			Bseek(mkaux->b, -Blinelen(mkaux->b), 1);
+			mkaux->lineno--;
+			return;
+		}
+	}
+}
+
+static File*
+getfile(Mkaux *mkaux, File *old)
+{
+	File *f;
+	char *elem;
+	char *p;
+	int c;
+
+	if(mkaux->indent < 0)
+		return 0;
+loop:
+	mkaux->indent = 0;
+	p = Brdline(mkaux->b, '\n');
+	mkaux->lineno++;
+	if(!p){
+		mkaux->indent = -1;
+		return 0;
+	}
+	while((c = *p++) != '\n')
+		if(c == ' ')
+			mkaux->indent++;
+		else if(c == '\t')
+			mkaux->indent += 8;
+		else
+			break;
+	if(c == '\n' || c == '#')
+		goto loop;
+	p--;
+	f = emalloc(mkaux, sizeof *f);
+	p = getname(mkaux, p, &elem);
+	if(p == nil)
+		return nil;
+
+	f->new = mkpath(mkaux, old->new, elem);
+	free(elem);
+	f->elem = utfrrune(f->new, L'/') + 1;
+	p = getmode(mkaux, p, &f->mode);
+	p = getname(mkaux, p, &f->uid);	/* LEAK */
+	if(p == nil)
+		return nil;
+
+	if(!*f->uid)
+		f->uid = "-";		/* LEAK */
+	p = getname(mkaux, p, &f->gid);	/* LEAK */
+	if(p == nil)
+		return nil;
+
+	if(!*f->gid)
+		f->gid = "-";		/* LEAK */
+	f->old = getpath(mkaux, p);
+	if(f->old && strcmp(f->old, "-") == 0){
+		free(f->old);
+		f->old = 0;
+	}
+	setnames(mkaux, f);
+
+	return f;
+}
+
+static char*
+getpath(Mkaux *mkaux, char *p)
+{
+	char *q, *new;
+	int c, n;
+
+	while((c = *p) == ' ' || c == '\t')
+		p++;
+	q = p;
+	while((c = *q) != '\n' && c != ' ' && c != '\t')
+		q++;
+	if(q == p)
+		return 0;
+	n = q - p;
+	new = emalloc(mkaux, n + 1);
+	memcpy(new, p, n);
+	new[n] = 0;
+	return new;
+}
+
+static char*
+getname(Mkaux *mkaux, char *p, char **buf)
+{
+	char *s, *start;
+	int c;
+
+	while((c = *p) == ' ' || c == '\t')
+		p++;
+
+	start = p;
+	while((c = *p) != '\n' && c != ' ' && c != '\t')
+		p++;
+
+	*buf = malloc(p+1-start);
+	if(*buf == nil)
+		return nil;
+	memmove(*buf, start, p-start);
+
+	(*buf)[p-start] = '\0';
+
+	if(**buf == '$'){
+		s = getenv(*buf+1);
+		if(s == 0){
+			warn(mkaux, "can't read environment variable %s", *buf+1);
+			skipdir(mkaux);
+			free(*buf);
+			return nil;
+		}
+		free(*buf);
+		*buf = s;
+	}
+	return p;
+}
+
+static char*
+getmode(Mkaux *mkaux, char *p, ulong *xmode)
+{
+	char *buf, *s;
+	ulong m;
+
+	*xmode = ~0;
+	p = getname(mkaux, p, &buf);
+	if(p == nil)
+		return nil;
+
+	s = buf;
+	if(!*s || strcmp(s, "-") == 0)
+		return p;
+	m = 0;
+	if(*s == 'd'){
+		m |= DMDIR;
+		s++;
+	}
+	if(*s == 'a'){
+		m |= DMAPPEND;
+		s++;
+	}
+	if(*s == 'l'){
+		m |= DMEXCL;
+		s++;
+	}
+	if(s[0] < '0' || s[0] > '7'
+	|| s[1] < '0' || s[1] > '7'
+	|| s[2] < '0' || s[2] > '7'
+	|| s[3]){
+		warn(mkaux, "bad mode specification %s", buf);
+		free(buf);
+		return p;
+	}
+	*xmode = m | strtoul(s, 0, 8);
+	free(buf);
+	return p;
+}
+
+static void
+warn(Mkaux *mkaux, char *fmt, ...)
+{
+	char buf[256];
+	va_list va;
+
+	va_start(va, fmt);
+	vseprint(buf, buf+sizeof(buf), fmt, va);
+	va_end(va);
+
+	if(mkaux->warn)
+		mkaux->warn(buf, mkaux->a);
+	else
+		fprint(2, "warning: %s\n", buf);
+}
diff --git a/sys/src/cmd/replica/updatedb.c b/sys/src/cmd/replica/updatedb.c
new file mode 100755
index 000000000..d63a53c0f
--- /dev/null
+++ b/sys/src/cmd/replica/updatedb.c
@@ -0,0 +1,214 @@
+/*
+ * generate a list of files and their metadata
+ * using a given proto file.
+ */
+#include "all.h"
+
+int changesonly;
+char *uid;
+Db *db;
+Biobuf blog;
+ulong now;
+int n;
+char **x;
+int nx;
+int justlog;
+char *root=".";
+char **match;
+int nmatch;
+
+int
+ismatch(char *s)
+{
+	int i, len;
+
+	if(nmatch == 0)
+		return 1;
+	for(i=0; i<nmatch; i++){
+		if(strcmp(s, match[i]) == 0)
+			return 1;
+		len = strlen(match[i]);
+		if(strncmp(s, match[i], len) == 0 && s[len]=='/')
+			return 1;
+	}
+	return 0;
+}
+
+void
+xlog(int c, char *name, Dir *d)
+{
+	char *dname;
+
+	dname = d->name;
+	if(strcmp(dname, name) == 0)
+		dname = "-";
+	if(!justlog)
+		Bprint(&blog, "%lud %d ", now, n++);
+	Bprint(&blog, "%c %q %q %luo %q %q %lud %lld\n",
+		c, name, dname, d->mode, uid ? uid : d->uid, d->gid, d->mtime, d->length);
+}
+
+void
+walk(char *new, char *old, Dir *xd, void*)
+{
+	int i, change, len;
+	Dir od, d;
+
+	new = unroot(new, "/");
+	old = unroot(old, root);
+
+	if(!ismatch(new))
+		return;
+	for(i=0; i<nx; i++){
+		if(strcmp(new, x[i]) == 0)
+			return;
+		len = strlen(x[i]);
+		if(strncmp(new, x[i], len)==0 && new[len]=='/')
+			return;
+	}
+
+	d = *xd;
+	d.name = old;
+	memset(&od, 0, sizeof od);
+	change = 0;
+	if(markdb(db, new, &od) < 0){
+		if(!changesonly){
+			xlog('a', new, &d);
+			change = 1;
+		}
+	}else{
+		if((d.mode&DMDIR)==0 && (od.mtime!=d.mtime || od.length!=d.length)){
+			xlog('c', new, &d);
+			change = 1;
+		}
+		if((!uid&&strcmp(od.uid,d.uid)!=0)
+		|| strcmp(od.gid,d.gid)!=0 
+		|| od.mode!=d.mode){
+			xlog('m', new, &d);
+			change = 1;
+		}
+	}
+	if(!justlog && change){
+		if(uid)
+			d.uid = uid;
+		d.muid = "mark";	/* mark bit */
+		insertdb(db, new, &d);
+	}
+}
+
+void
+warn(char *msg, void*)
+{
+	char *p;
+
+	fprint(2, "warning: %s\n", msg);
+
+	/* find the %r in "can't open foo: %r" */
+	p = strstr(msg, ": ");
+	if(p)
+		p += 2;
+
+	/*
+	 * if the error is about a remote server failing,
+	 * then there's no point in continuing to look
+	 * for changes -- we'll think everything got deleted!
+	 *
+	 * actual errors i see are:
+	 *	"i/o on hungup channel" for a local hangup
+	 *	"i/o on hungup channel" for a timeout (yank the network wire)
+	 *	"'/n/sources/plan9' Hangup" for a remote hangup
+	 * the rest is paranoia.
+	 */
+	if(p){
+		if(cistrstr(p, "hungup") || cistrstr(p, "Hangup")
+		|| cistrstr(p, "rpc error")
+		|| cistrstr(p, "shut down")
+		|| cistrstr(p, "i/o")
+		|| cistrstr(p, "connection"))
+			sysfatal("suspected network or i/o error - bailing out");
+	}
+}
+
+void
+usage(void)
+{
+	fprint(2, "usage: replica/updatedb [-c] [-p proto] [-r root] [-t now n] [-u uid] [-x path]... db [paths]\n");
+	exits("usage");
+}
+
+void
+main(int argc, char **argv)
+{
+	char *proto;
+	Avlwalk *w;
+	Dir d;
+	Entry *e;
+
+	quotefmtinstall();
+	proto = "/sys/lib/sysconfig/proto/allproto";
+	now = time(0);
+	Binit(&blog, 1, OWRITE);
+	ARGBEGIN{
+	case 'c':
+		changesonly = 1;
+		break;
+	case 'l':
+		justlog = 1;
+		break;
+	case 'p':
+		proto = EARGF(usage());
+		break;
+	case 'r':
+		root = EARGF(usage());
+		break;
+	case 't':
+		now = strtoul(EARGF(usage()), 0, 0);
+		n = atoi(EARGF(usage()));
+		break;
+	case 'u':
+		uid = EARGF(usage());
+		break;
+	case 'x':
+		if(nx%16 == 0)
+			x = erealloc(x, (nx+16)*sizeof(x[0]));
+		x[nx++] = EARGF(usage());
+		break;
+	default:
+		usage();
+	}ARGEND
+
+	if(argc <1)
+		usage();
+
+	match = argv+1;
+	nmatch = argc-1;
+
+	db = opendb(argv[0]);
+	if(rdproto(proto, root, walk, warn, nil) < 0)
+		sysfatal("rdproto: %r");
+
+	if(!changesonly){
+		w = avlwalk(db->avl);
+		while(e = (Entry*)avlprev(w)){
+			if(!ismatch(e->name))
+				continue;
+			if(!e->d.mark){		/* not visited during walk */
+				memset(&d, 0, sizeof d);
+				d.name = e->d.name;
+				d.uid = e->d.uid;
+				d.gid = e->d.gid;
+				d.mtime = e->d.mtime;
+				d.mode = e->d.mode;
+				xlog('d', e->name, &d);
+				if(!justlog)
+					removedb(db, e->name);
+			}
+		}
+	}
+
+	if(Bterm(&blog) < 0)
+		sysfatal("writing output: %r");
+
+	exits(nil);
+}
+
diff --git a/sys/src/cmd/replica/util.c b/sys/src/cmd/replica/util.c
new file mode 100755
index 000000000..f05b85ec7
--- /dev/null
+++ b/sys/src/cmd/replica/util.c
@@ -0,0 +1,137 @@
+#include "all.h"
+
+void*
+erealloc(void *a, int n)
+{
+	a = realloc(a, n);
+	if(a==nil)
+		sysfatal("realloc: %r");
+	return a;
+}
+
+char*
+estrdup(char *s)
+{
+	s = strdup(s);
+	if(s == nil)
+		sysfatal("strdup: %r");
+	return s;
+}
+
+void*
+emalloc(int n)
+{
+	void *a;
+
+	a = mallocz(n, 1);
+	if(a == nil)
+		sysfatal("malloc: %r");
+	return a;
+}
+
+/*
+ *	Custom allocators to avoid malloc overheads on small objects.
+ * 	We never free these.  (See below.)
+ */
+typedef struct Stringtab	Stringtab;
+struct Stringtab {
+	Stringtab *link;
+	char *str;
+};
+static Stringtab*
+taballoc(void)
+{
+	static Stringtab *t;
+	static uint nt;
+
+	if(nt == 0){
+		t = malloc(64*sizeof(Stringtab));
+		if(t == 0)
+			sysfatal("out of memory");
+		nt = 64;
+	}
+	nt--;
+	return t++;
+}
+
+static char*
+xstrdup(char *s)
+{
+	char *r;
+	int len;
+	static char *t;
+	static int nt;
+
+	len = strlen(s)+1;
+	if(len >= 8192)
+		sysfatal("strdup big string");
+
+	if(nt < len){
+		t = malloc(8192);
+		if(t == 0)
+			sysfatal("out of memory");
+		nt = 8192;
+	}
+	r = t;
+	t += len;
+	nt -= len;
+	strcpy(r, s);
+	return r;
+}
+
+/*
+ *	Return a uniquely allocated copy of a string.
+ *	Don't free these -- they stay in the table for the 
+ *	next caller who wants that particular string.
+ *	String comparison can be done with pointer comparison 
+ *	if you know both strings are atoms.
+ */
+static Stringtab *stab[1024];
+
+static uint
+hash(char *s)
+{
+	uint h;
+	uchar *p;
+
+	h = 0;
+	for(p=(uchar*)s; *p; p++)
+		h = h*37 + *p;
+	return h;
+}
+
+char*
+atom(char *str)
+{
+	uint h;
+	Stringtab *tab;
+	
+	h = hash(str) % nelem(stab);
+	for(tab=stab[h]; tab; tab=tab->link)
+		if(strcmp(str, tab->str) == 0)
+			return tab->str;
+
+	tab = taballoc();
+	tab->str = xstrdup(str);
+	tab->link = stab[h];
+	stab[h] = tab;
+	return tab->str;
+}
+
+char*
+unroot(char *path, char *root)
+{
+	int len;
+	char *s;
+
+	len = strlen(root);
+	while(len >= 1 && root[len-1]=='/')
+		len--;
+	if(strncmp(path, root, len)==0 && (path[len]=='/' || path[len]=='\0')){
+		s = path+len;
+		while(*s == '/')
+			s++;
+		return s;
+	}
+	return path;
+}