X-Git-Url: https://mattmccutchen.net/rsync/rsync.git/blobdiff_plain/bb24028f51bac18097e688c1459924f648bc407e..d5c973ccb7da1bc87c5caa5d5ac594bc217016f7:/generator.c

diff --git a/generator.c b/generator.c
index 84264dcc..812fef42 100644
--- a/generator.c
+++ b/generator.c
@@ -32,7 +32,6 @@ extern int preserve_devices;
 extern int preserve_hard_links;
 extern int update_only;
 extern int opt_ignore_existing;
-extern int block_size;
 extern int csum_length;
 extern int ignore_times;
 extern int size_only;
@@ -56,8 +55,8 @@ static int skip_file(char *fname,
 		extern int preserve_uid;
 		extern int preserve_gid;
 
-		if((preserve_perms
-		    && st->st_mode & ~_S_IFMT) !=  (file->mode & ~_S_IFMT))
+		if(preserve_perms
+		    && (st->st_mode & ~_S_IFMT) !=  (file->mode & ~_S_IFMT))
 			return 0;
 
 		if (preserve_uid && st->st_uid != file->uid)
@@ -100,32 +99,105 @@ static int skip_file(char *fname,
 }
 
 
-/* use a larger block size for really big files */
-static int adapt_block_size(struct file_struct *file, int bsize)
+/*
+ * 	NULL sum_struct means we have no checksums
+ */
+
+void write_sum_head(int f, struct sum_struct *sum)
 {
-	int ret;
+	static struct sum_struct null_sum;
 
-	if (bsize != BLOCK_SIZE) return bsize;
+	if (sum == (struct sum_struct *)NULL)
+		sum = &null_sum;
 
-	ret = file->length / (10000); /* rough heuristic */
-	ret = ret & ~15; /* multiple of 16 */
-	if (ret < bsize) ret = bsize;
-	if (ret > CHUNK_SIZE/2) ret = CHUNK_SIZE/2;
-	return ret;
+	write_int(f, sum->count);
+	write_int(f, sum->blength);
+	if (remote_version >= 27)
+		write_int(f, sum->s2length);
+	write_int(f, sum->remainder);
 }
 
+/* 
+ * set (initialize) the size entries in the per-file sum_struct
+ * calulating dynamic block ans checksum sizes.
+ *
+ * This is only called from generate_and_send_sums() but is a seperate
+ * function to encapsulate the logic.
+ *
+ * The block size is a rounded square root of file length.
+ *
+ * The checksum size is determined according to:
+ *     blocksum_bits = BLOCKSUM_EXP + 2*log2(file_len) - log2(block_len)
+ * provided by Donovan Baarda which gives a probability of rsync
+ * algorithm corrupting data and falling back using the whole md4
+ * checksums.
+ *
+ * This might be made one of several selectable heuristics.
+ */
 
-/*
-  send a header that says "we have no checksums" down the f_out fd
-  */
-static void send_null_sums(int f_out)
+static void sum_sizes_sqroot_baarda(struct sum_struct *sum, uint64 len)
 {
-	write_int(f_out, 0);
-	write_int(f_out, block_size);
-	write_int(f_out, 0);
-}
+	extern int block_size;
+	int blength, s2length, b;
+	uint32 c;
+	uint64 l;
+
+	if (block_size) {
+		blength = block_size;
+	} else if (len <= BLOCK_SIZE * BLOCK_SIZE) {
+		blength = BLOCK_SIZE;
+	} else {
+		l = len;
+		c = 1;
+		while (l >>= 2) {
+			c <<= 1;
+		}
+		blength = 0;
+		do {
+			blength |= c;
+			if (len < (uint64)(blength * blength))
+				blength &= ~c;
+			c >>= 1;
+		} while (c >= 8);	/* round to multiple of 8 */
+		blength = MAX(blength, BLOCK_SIZE);
+	}
 
+	if (remote_version < 27) {
+		s2length = csum_length;
+	} else if (csum_length == SUM_LENGTH) {
+		s2length = SUM_LENGTH;
+	} else {
+		b = BLOCKSUM_BIAS;
+		l = len;
+		while (l >>= 1) {
+			b += 2;
+		}
+		c = blength;
+		while (c >>= 1 && b) {
+			b--;
+		}
+		s2length = (b + 1 - 32 + 7) / 8; /* add a bit,
+						  * subtract rollsum,
+						  * round up
+						  *    --optimize in compiler--
+						  */
+		s2length = MAX(s2length, csum_length);
+		s2length = MIN(s2length, SUM_LENGTH);
+	}
 
+	sum->flength	= len;
+	sum->blength	= blength;
+	sum->s2length	= s2length;
+	sum->count	= (len + (blength - 1)) / blength;
+	sum->remainder	= (len % blength);
+
+	if (sum->count && verbose > 2) {
+		rprintf(FINFO, "count=%ld rem=%ld blength=%ld s2length=%ld flength=%.0f\n",
+			(long) sum->count, (long) sum->remainder,
+			(long) sum->blength, (long) sum->s2length,
+			(double) sum->flength);
+	}
+}
 
 /**
  * Perhaps we want to just send an empty checksum set for this file,
@@ -155,31 +227,18 @@ static BOOL disable_deltas_p(void)
  *
  * Generate approximately one checksum every block_len bytes.
  */
-static void generate_and_send_sums(struct map_struct *buf, OFF_T len,
-				   int block_len, int f_out)
+static void generate_and_send_sums(struct map_struct *buf, OFF_T len, int f_out)
 {
 	size_t i;
 	struct sum_struct sum;
 	OFF_T offset = 0;
 
-	sum.count = (len + (block_len - 1)) / block_len;
-	sum.remainder = (len % block_len);
-	sum.n = block_len;
-	sum.flength = len;
-	/* not needed here  sum.sums = NULL; */
+	sum_sizes_sqroot_baarda(&sum, len);
 
-	if (sum.count && verbose > 3) {
-		rprintf(FINFO, "count=%ld rem=%ld n=%ld flength=%.0f\n",
-			(long) sum.count, (long) sum.remainder,
-			(long) sum.n, (double) sum.flength);
-	}
-
-	write_int(f_out, sum.count);
-	write_int(f_out, sum.n);
-	write_int(f_out, sum.remainder);
+	write_sum_head(f_out, &sum);
 
 	for (i = 0; i < sum.count; i++) {
-		int n1 = MIN(len, block_len);
+		int n1 = MIN(len, sum.blength);
 		char *map = map_ptr(buf, offset, n1);
 		uint32 sum1 = get_checksum1(map, n1);
 		char sum2[SUM_LENGTH];
@@ -188,11 +247,11 @@ static void generate_and_send_sums(struct map_struct *buf, OFF_T len,
 
 		if (verbose > 3) {
 			rprintf(FINFO,
-				"chunk[%d] offset=%.0f len=%d sum1=%08lx\n",
-				i, (double) offset, n1, (unsigned long) sum1);
+				"chunk[%ld] offset=%.0f len=%d sum1=%08lx\n",
+				(long)i,(double)offset,n1,(unsigned long)sum1);
 		}
 		write_int(f_out, sum1);
-		write_buf(f_out, sum2, csum_length);
+		write_buf(f_out, sum2, sum.s2length);
 		len -= n1;
 		offset += n1;
 	}
@@ -384,7 +443,7 @@ void recv_generator(char *fname, struct file_list *flist, int i, int f_out)
 	if (statret == -1) {
 		if (errno == ENOENT) {
 			write_int(f_out,i);
-			if (!dry_run) send_null_sums(f_out);
+			if (!dry_run) write_sum_head(f_out, NULL);
 		} else {
 			if (verbose > 1)
 				rprintf(FERROR, RSYNC_NAME
@@ -401,7 +460,7 @@ void recv_generator(char *fname, struct file_list *flist, int i, int f_out)
 
 		/* now pretend the file didn't exist */
 		write_int(f_out,i);
-		if (!dry_run) send_null_sums(f_out);
+		if (!dry_run) write_sum_head(f_out, NULL);
 		return;
 	}
 
@@ -430,7 +489,7 @@ void recv_generator(char *fname, struct file_list *flist, int i, int f_out)
 
 	if (disable_deltas_p()) {
 		write_int(f_out,i);
-		send_null_sums(f_out);
+		write_sum_head(f_out, NULL);
 		return;
 	}
 
@@ -441,7 +500,7 @@ void recv_generator(char *fname, struct file_list *flist, int i, int f_out)
 		rprintf(FERROR,RSYNC_NAME": failed to open \"%s\", continuing : %s\n",fnamecmp,strerror(errno));
 		/* pretend the file didn't exist */
 		write_int(f_out,i);
-		send_null_sums(f_out);
+		write_sum_head(f_out, NULL);
 		return;
 	}
 
@@ -458,8 +517,7 @@ void recv_generator(char *fname, struct file_list *flist, int i, int f_out)
 		rprintf(FINFO, "generating and sending sums for %d\n", i);
 
 	write_int(f_out,i);
-	generate_and_send_sums(buf, st.st_size,
-			       adapt_block_size(file, block_size), f_out);
+	generate_and_send_sums(buf, st.st_size, f_out);
 
 	close(fd);
 	if (buf) unmap_file(buf);
@@ -516,19 +574,16 @@ void generate_files(int f,struct file_list *flist,char *local_name,int f_recv)
 
 	write_int(f,-1);
 
-	if (remote_version >= 13) {
-		/* in newer versions of the protocol the files can cycle through
-		   the system more than once to catch initial checksum errors */
-		for (i=read_int(f_recv); i != -1; i=read_int(f_recv)) {
-			struct file_struct *file = flist->files[i];
-			recv_generator(local_name?local_name:f_name(file),
-				       flist,i,f);
-		}
+	/* files can cycle through the system more than once
+	 * to catch initial checksum errors */
+	for (i=read_int(f_recv); i != -1; i=read_int(f_recv)) {
+		struct file_struct *file = flist->files[i];
+		recv_generator(local_name?local_name:f_name(file), flist,i,f);
+	}
 
-		phase++;
-		if (verbose > 2)
-			rprintf(FINFO,"generate_files phase=%d\n",phase);
+	phase++;
+	if (verbose > 2)
+		rprintf(FINFO,"generate_files phase=%d\n",phase);
 
-		write_int(f,-1);
-	}
+	write_int(f,-1);
 }