venti/copy: synchronize with Plan 9; indent in verbose mode

http://codereview.appspot.com/110062

2 files changed, 146 insertions, 14 deletions

diff --git a/man/man1/venti.1 b/man/man1/venti.1
index 12d664f4..cf160091 100644
--- a/man/man1/venti.1
+++ b/man/man1/venti.1
@@ -28,7 +28,7 @@ read, write, copy \- simple Venti clients
 .br
 .B venti/copy
 [
-.B -fir
+.B -fimrVv
 ]
 [
 .B -t
@@ -99,14 +99,35 @@ the root block from the server
 to the server
 .IR dsthost .
 .PP
+Venti's blocks are arranged in a directed acyclic graph (see venti(6)); 
+there may be multiple paths from a root score to an 
+interior block (for example, if the same file contents are stored
+under multiple names in an archive).
+.I Copy
+runs more efficiently if it does not copy blocks 
+(and all their children) multiple times.
 The
 .B -f
 option causes
 .I copy
-to run in `fast' mode,
-assuming that if a block already exists on the
-destination Venti server, all its children also
-exist and need not be checked.
+to assume that if a block already exists on the destination
+Venti server, all its children also exist and need not be considered.
+The
+.B -m
+option causes
+.I copy
+to maintain an in-memory list of blocks it has copied
+and avoid considering the same block multiple times.
+The
+.B -f
+option is only useful if the destination Venti server is
+known not to have lost any blocks due to disk corruption
+or other failures.
+The
+.B -m
+option is only useful if enough memory is available to
+hold the block list, which typically requires about 1%
+of the total number of bytes being copied.
 .PP
 The
 .B -i
@@ -135,6 +156,14 @@ option is given,
 replaces pointers to unreadable blocks with
 pointers to the zero block.
 It writes the new root score to standard output.
+The
+.B -v
+option prints scores as it copies them, total writes, and other
+debugging information.
+The
+.B -V
+option prints debugging information about the Venti protocol
+messages send/received.
 .SH SOURCE
 .B \*9/src/cmd/venti
 .SH SEE ALSO
diff --git a/src/cmd/venti/copy.c b/src/cmd/venti/copy.c
index 4a05e053..87075e48 100644
--- a/src/cmd/venti/copy.c
+++ b/src/cmd/venti/copy.c
@@ -3,6 +3,8 @@
 #include <venti.h>
 #include <libsec.h>
 #include <thread.h>
+#include <avl.h>
+#include <bin.h>
 
 enum
 {
@@ -15,25 +17,93 @@ int rewrite;
 int ignoreerrors;
 int fast;
 int verbose;
+int nskip;
+int nwrite;
+
 VtConn *zsrc, *zdst;
+uchar zeroscore[VtScoreSize];	/* all zeros */
+
+typedef struct ScoreTree ScoreTree;
+struct ScoreTree
+{
+	Avl avl;
+	uchar score[VtScoreSize];
+	int type;
+};
+
+Avltree *scoretree;
+Bin *scorebin;
+
+static int
+scoretreecmp(Avl *va, Avl *vb)
+{
+	ScoreTree *a, *b;
+	int i;
+
+	a = (ScoreTree*)va;
+	b = (ScoreTree*)vb;
+
+	i = memcmp(a->score, b->score, VtScoreSize);
+	if(i != 0)
+		return i;
+	return a->type - b->type;
+}
+
+static int
+havevisited(uchar score[VtScoreSize], int type)
+{
+	ScoreTree a;
+	
+	if(scoretree == nil)
+		return 0;
+	memmove(a.score, score, VtScoreSize);
+	a.type = type;
+	return lookupavl(scoretree, &a.avl) != nil;
+}
+
+static void
+markvisited(uchar score[VtScoreSize], int type)
+{
+	ScoreTree *a;
+	Avl *old;
+
+	if(scoretree == nil)
+		return;
+	a = binalloc(&scorebin, sizeof *a, 1);
+	memmove(a->score, score, VtScoreSize);
+	a->type = type;
+	insertavl(scoretree, &a->avl, &old);
+}
 
 void
 usage(void)
 {
-	fprint(2, "usage: copy [-fir] [-t type] srchost dsthost score\n");
+	fprint(2, "usage: copy [-fimrVv] [-t type] srchost dsthost score\n");
 	threadexitsall("usage");
 }
 
 void
-walk(uchar score[VtScoreSize], uint type, int base)
+walk(uchar score[VtScoreSize], uint type, int base, int depth)
 {
 	int i, n;
 	uchar *buf;
+	uchar nscore[VtScoreSize];
 	VtEntry e;
 	VtRoot root;
 
-	if(memcmp(score, vtzeroscore, VtScoreSize) == 0)
+	if(verbose){
+		for(i = 0; i < depth; i++)
+			fprint(2, " ");
+		fprint(2, "-> %d %d %d %V\n", depth, type, base, score);
+	}
+
+	if(memcmp(score, vtzeroscore, VtScoreSize) == 0 || memcmp(score, zeroscore, VtScoreSize) == 0)
+		return;
+	
+	if(havevisited(score, type)){
+		nskip++;
 		return;
+	}
 
 	buf = vtmallocz(VtMaxLumpSize);
 	if(fast && vtread(zdst, score, type, buf, VtMaxLumpSize) >= 0){
@@ -59,8 +129,8 @@ walk(uchar score[VtScoreSize], uint type, int base)
 			fprint(2, "warning: could not unpack root in %V %d\n", score, type);
 			break;
 		}
-		walk(root.score, VtDirType, 0);
-		walk(root.prev, VtRootType, 0);
+		walk(root.prev, VtRootType, 0, depth+1);
+		walk(root.score, VtDirType, 0, depth+1);
 		if(rewrite)
 			vtrootpack(&root, buf);	/* walk might have changed score */
 		break;
@@ -73,7 +143,14 @@ walk(uchar score[VtScoreSize], uint type, int base)
 			}
 			if(!(e.flags & VtEntryActive))
 				continue;
-			walk(e.score, e.type, e.type&VtTypeBaseMask);
+			walk(e.score, e.type, e.type&VtTypeBaseMask, depth+1);
+			/*
+			 * Don't repack unless we're rewriting -- some old 
+			 * vac files have psize==0 and dsize==0, and these
+			 * get rewritten by vtentryunpack to have less strange
+			 * block sizes.  So vtentryunpack; vtentrypack does not
+			 * guarantee to preserve the exact bytes in buf.
+			 */
 			if(rewrite)
 				vtentrypack(&e, buf, i);
 		}
@@ -85,17 +162,31 @@ walk(uchar score[VtScoreSize], uint type, int base)
 	default:	/* pointers */
 		for(i=0; i<n; i+=VtScoreSize)
 			if(memcmp(buf+i, vtzeroscore, VtScoreSize) != 0)
-				walk(buf+i, type-1, base);
+				walk(buf+i, type-1, base, depth+1);
 		break;
 	}
 
-	if(vtwrite(zdst, score, type, buf, n) < 0){
+	nwrite++;
+	if(vtwrite(zdst, nscore, type, buf, n) < 0){
 		/* figure out score for better error message */
 		/* can't use input argument - might have changed contents */
 		n = vtzerotruncate(type, buf, n);
 		sha1(buf, n, score, nil);
 		sysfatal("writing block %V (type %d): %r", score, type);
 	}
+	if(!rewrite && memcmp(score, nscore, VtScoreSize) != 0)
+		sysfatal("not rewriting: wrote %V got %V", score, nscore);	
+
+	if((type !=0 || base !=0) && verbose){
+		n = vtzerotruncate(type, buf, n);
+		sha1(buf, n, score, nil);
+
+		for(i = 0; i < depth; i++)
+			fprint(2, " ");
+		fprint(2, "<- %V\n", score);
+	}
+	
+	markvisited(score, type);
 	free(buf);
 }
 
@@ -112,6 +203,9 @@ threadmain(int argc, char *argv[])
 
 	type = -1;
 	ARGBEGIN{
+	case 'V':
+		chattyventi++;
+		break;
 	case 'f':
 		fast = 1;
 		break;
@@ -120,6 +214,9 @@ threadmain(int argc, char *argv[])
 			usage();
 		ignoreerrors = 1;
 		break;
+	case 'm':
+		scoretree = mkavltree(scoretreecmp);
+		break;
 	case 'r':
 		if(ignoreerrors)
 			usage();
@@ -128,6 +225,9 @@ threadmain(int argc, char *argv[])
 	case 't':
 		type = atoi(EARGF(usage()));
 		break;
+	case 'v':
+		verbose = 1;
+		break;
 	default:
 		usage();
 		break;
@@ -167,10 +267,13 @@ threadmain(int argc, char *argv[])
 			sysfatal("could not find block %V of any type", score);
 	}
 
-	walk(score, type, VtDirType);
+	walk(score, type, VtDirType, 0);
 	if(changes)
 		print("%s:%V (%d pointers rewritten)\n", prefix, score, changes);
 
+	if(verbose)
+		print("%d skipped, %d written\n", nskip, nwrite);
+
 	if(vtsync(zdst) < 0)
 		sysfatal("could not sync dst server: %r");