Updating patches.
[rsync-patches.git] / detect-renamed.diff
1 This patch adds the --detect-renamed option which makes rsync notice files
2 that either (1) match in size & modify-time (plus the basename, if possible)
3 or (2) match in size & checksum (when --checksum was also specified) and use
4 each match as an alternate basis file to speed up the transfer.
5
6 The algorithm attempts to scan the receiving-side's files in an efficient
7 manner.  If --delete[-before] is enabled, we'll take advantage of the
8 pre-transfer delete pass to prepare any alternate-basis-file matches we
9 might find.  If --delete-before is not enabled, rsync does the rename scan
10 during the regular file-sending scan (scanning each directory right before
11 the generator starts updating files from that dir).  In this latter mode,
12 rsync might delay the updating of a file (if no alternate-basis match was
13 yet found) until the full scan of the receiving side is complete, at which
14 point any delayed files are processed.
15
16 I chose to hard-link the alternate-basis files into a ".~tmp~" subdir that
17 takes advantage of rsync's pre-existing partial-dir logic.  This uses less
18 memory than trying to keep track of the matches internally, and also allows
19 any deletions or file-updates to occur normally without interfering with
20 these alternate-basis discoveries.
21
22 To use this patch, run these commands for a successful build:
23
24     patch -p1 <patches/detect-renamed.diff
25     ./configure                                 (optional if already run)
26     make
27
28 TODO:
29
30   The routine that makes missing directories for files that get renamed
31   down into a new sub-hierarchy doesn't properly handle the case where some
32   path elements might exist but not be a dir yet.  We need to either change
33   our stash-ahead algorithm (to not require unknown path elements) or we
34   need to create a better path-making routine.
35
36   We need to never return a match from fattr_find() that has a basis
37   file.  This will ensure that we don't try to give a renamed file to
38   a file that can't use it, while missing out on giving it to a file
39   that could use it.
40
41 based-on: 2ac35b45071c7bfd8be6be41bfd45326f1f57bce
42 diff --git a/compat.c b/compat.c
43 --- a/compat.c
44 +++ b/compat.c
45 @@ -44,6 +44,7 @@ extern int checksum_seed;
46  extern int basis_dir_cnt;
47  extern int prune_empty_dirs;
48  extern int protocol_version;
49 +extern int detect_renamed;
50  extern int protect_args;
51  extern int preserve_uid;
52  extern int preserve_gid;
53 @@ -125,6 +126,7 @@ void set_allow_inc_recurse(void)
54                 allow_inc_recurse = 0;
55         else if (!am_sender
56          && (delete_before || delete_after
57 +         || detect_renamed
58           || delay_updates || prune_empty_dirs))
59                 allow_inc_recurse = 0;
60         else if (am_server && !local_server
61 diff --git a/delete.c b/delete.c
62 --- a/delete.c
63 +++ b/delete.c
64 @@ -25,6 +25,7 @@
65  extern int am_root;
66  extern int make_backups;
67  extern int max_delete;
68 +extern int detect_renamed;
69  extern char *backup_dir;
70  extern char *backup_suffix;
71  extern int backup_suffix_len;
72 @@ -44,6 +45,8 @@ static inline int is_backup_file(char *fn)
73   * its contents, otherwise just checks for content.  Returns DR_SUCCESS or
74   * DR_NOT_EMPTY.  Note that fname must point to a MAXPATHLEN buffer!  (The
75   * buffer is used for recursion, but returned unchanged.)
76 + *
77 + * Note: --detect-rename may use this routine with DEL_NO_DELETIONS set!
78   */
79  static enum delret delete_dir_contents(char *fname, uint16 flags)
80  {
81 @@ -63,7 +66,9 @@ static enum delret delete_dir_contents(char *fname, uint16 flags)
82         save_filters = push_local_filters(fname, dlen);
83  
84         non_perishable_cnt = 0;
85 +       file_extra_cnt += SUM_EXTRA_CNT;
86         dirlist = get_dirlist(fname, dlen, 0);
87 +       file_extra_cnt -= SUM_EXTRA_CNT;
88         ret = non_perishable_cnt ? DR_NOT_EMPTY : DR_SUCCESS;
89  
90         if (!dirlist->used)
91 @@ -103,7 +108,8 @@ static enum delret delete_dir_contents(char *fname, uint16 flags)
92                 if (S_ISDIR(fp->mode)) {
93                         if (delete_dir_contents(fname, flags | DEL_RECURSE) != DR_SUCCESS)
94                                 ret = DR_NOT_EMPTY;
95 -               }
96 +               } else if (detect_renamed && S_ISREG(fp->mode))
97 +                       look_for_rename(fp, fname);
98                 if (delete_item(fname, fp->mode, flags) != DR_SUCCESS)
99                         ret = DR_NOT_EMPTY;
100         }
101 @@ -126,6 +132,8 @@ static enum delret delete_dir_contents(char *fname, uint16 flags)
102   *
103   * Note that fbuf must point to a MAXPATHLEN buffer if the mode indicates it's
104   * a directory! (The buffer is used for recursion, but returned unchanged.)
105 + *
106 + * Also note: --detect-rename may use this routine with DEL_NO_DELETIONS set!
107   */
108  enum delret delete_item(char *fbuf, uint16 mode, uint16 flags)
109  {
110 @@ -153,6 +161,9 @@ enum delret delete_item(char *fbuf, uint16 mode, uint16 flags)
111                 /* OK: try to delete the directory. */
112         }
113  
114 +       if (flags & DEL_NO_DELETIONS)
115 +               return DR_SUCCESS;
116 +
117         if (!(flags & DEL_MAKE_ROOM) && max_delete >= 0 && stats.deleted_files >= max_delete) {
118                 skipped_deletes++;
119                 return DR_AT_LIMIT;
120 diff --git a/flist.c b/flist.c
121 --- a/flist.c
122 +++ b/flist.c
123 @@ -60,6 +60,7 @@ extern int non_perishable_cnt;
124  extern int prune_empty_dirs;
125  extern int copy_links;
126  extern int copy_unsafe_links;
127 +extern int detect_renamed;
128  extern int protocol_version;
129  extern int sanitize_paths;
130  extern int munge_symlinks;
131 @@ -125,6 +126,8 @@ static int64 tmp_dev = -1, tmp_ino;
132  #endif
133  static char tmp_sum[MAX_DIGEST_LEN];
134  
135 +struct file_list the_fattr_list;
136 +
137  static char empty_sum[MAX_DIGEST_LEN];
138  static int flist_count_offset; /* for --delete --progress */
139  
140 @@ -292,6 +295,45 @@ static int is_excluded(const char *fname, int is_dir, int filter_level)
141         return 0;
142  }
143  
144 +static int fattr_compare(struct file_struct **file1, struct file_struct **file2)
145 +{
146 +       struct file_struct *f1 = *file1;
147 +       struct file_struct *f2 = *file2;
148 +       int64 len1 = F_LENGTH(f1), len2 = F_LENGTH(f2);
149 +       int diff;
150 +
151 +       if (!f1->basename || !S_ISREG(f1->mode) || !len1) {
152 +               if (!f2->basename || !S_ISREG(f2->mode) || !len2)
153 +                       return 0;
154 +               return 1;
155 +       }
156 +       if (!f2->basename || !S_ISREG(f2->mode) || !len2)
157 +               return -1;
158 +
159 +       /* Don't use diff for values that are longer than an int. */
160 +       if (len1 != len2)
161 +               return len1 < len2 ? -1 : 1;
162 +
163 +       if (always_checksum) {
164 +               diff = u_memcmp(F_SUM(f1), F_SUM(f2), checksum_len);
165 +               if (diff)
166 +                       return diff;
167 +       } else if (f1->modtime != f2->modtime)
168 +               return f1->modtime < f2->modtime ? -1 : 1;
169 +
170 +       diff = u_strcmp(f1->basename, f2->basename);
171 +       if (diff)
172 +               return diff;
173 +
174 +       if (f1->dirname == f2->dirname)
175 +               return 0;
176 +       if (!f1->dirname)
177 +               return -1;
178 +       if (!f2->dirname)
179 +               return 1;
180 +       return u_strcmp(f1->dirname, f2->dirname);
181 +}
182 +
183  static void send_directory(int f, struct file_list *flist,
184                            char *fbuf, int len, int flags);
185  
186 @@ -2586,6 +2628,25 @@ struct file_list *recv_file_list(int f, int dir_ndx)
187          * for a non-relative transfer in recv_file_entry(). */
188         flist_sort_and_clean(flist, relative_paths);
189  
190 +       if (detect_renamed) {
191 +               int j = flist->used;
192 +               the_fattr_list.used = j;
193 +               the_fattr_list.files = new_array(struct file_struct *, j);
194 +               if (!the_fattr_list.files)
195 +                       out_of_memory("recv_file_list");
196 +               memcpy(the_fattr_list.files, flist->files,
197 +                      j * sizeof (struct file_struct *));
198 +               qsort(the_fattr_list.files, j,
199 +                     sizeof the_fattr_list.files[0], (int (*)())fattr_compare);
200 +               the_fattr_list.low = 0;
201 +               while (j-- > 0) {
202 +                       struct file_struct *fp = the_fattr_list.files[j];
203 +                       if (fp->basename && S_ISREG(fp->mode) && F_LENGTH(fp))
204 +                               break;
205 +               }
206 +               the_fattr_list.high = j;
207 +       }
208 +
209         if (protocol_version < 30) {
210                 /* Recv the io_error flag */
211                 int err = read_int(f);
212 diff --git a/generator.c b/generator.c
213 --- a/generator.c
214 +++ b/generator.c
215 @@ -79,6 +79,7 @@ extern char *partial_dir;
216  extern int compare_dest;
217  extern int copy_dest;
218  extern int link_dest;
219 +extern int detect_renamed;
220  extern int whole_file;
221  extern int list_only;
222  extern int read_batch;
223 @@ -97,10 +98,12 @@ extern char *tmpdir;
224  extern char *basis_dir[MAX_BASIS_DIRS+1];
225  extern struct file_list *cur_flist, *first_flist, *dir_flist;
226  extern filter_rule_list filter_list, daemon_filter_list;
227 +extern struct file_list the_fattr_list;
228  
229  int maybe_ATTRS_REPORT = 0;
230  
231  static dev_t dev_zero;
232 +static int unexplored_dirs = 1;
233  static int deldelay_size = 0, deldelay_cnt = 0;
234  static char *deldelay_buf = NULL;
235  static int deldelay_fd = -1;
236 @@ -271,13 +274,18 @@ static void do_delayed_deletions(char *delbuf)
237   * all the --delete-WHEN options.  Note that the fbuf pointer must point to a
238   * MAXPATHLEN buffer with the name of the directory in it (the functions we
239   * call will append names onto the end, but the old dir value will be restored
240 - * on exit). */
241 -static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev)
242 + * on exit).
243 + *
244 + * Note:  --detect-rename may use this routine with DEL_NO_DELETIONS set!
245 + */
246 +static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev,
247 +                         int del_flags)
248  {
249         static int already_warned = 0;
250         struct file_list *dirlist;
251 -       char delbuf[MAXPATHLEN];
252 -       int dlen, i;
253 +       char *p, delbuf[MAXPATHLEN];
254 +       unsigned remainder;
255 +       int dlen, i, restore_dot = 0;
256  
257         if (!fbuf) {
258                 change_local_filter_dir(NULL, 0, 0);
259 @@ -291,17 +299,22 @@ static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev)
260                 maybe_send_keepalive(time(NULL), MSK_ALLOW_FLUSH);
261  
262         if (io_error & IOERR_GENERAL && !ignore_errors) {
263 -               if (already_warned)
264 +               if (!already_warned) {
265 +                       rprintf(FINFO,
266 +                           "IO error encountered -- skipping file deletion\n");
267 +                       already_warned = 1;
268 +               }
269 +               if (!detect_renamed)
270                         return;
271 -               rprintf(FINFO,
272 -                       "IO error encountered -- skipping file deletion\n");
273 -               already_warned = 1;
274 -               return;
275 +               del_flags |= DEL_NO_DELETIONS;
276         }
277  
278         dlen = strlen(fbuf);
279         change_local_filter_dir(fbuf, dlen, F_DEPTH(file));
280  
281 +       if (detect_renamed)
282 +               unexplored_dirs--;
283 +
284         if (one_file_system) {
285                 if (file->flags & FLAG_TOP_DIR)
286                         filesystem_dev = *fs_dev;
287 @@ -311,6 +324,14 @@ static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev)
288  
289         dirlist = get_dirlist(fbuf, dlen, 0);
290  
291 +       p = fbuf + dlen;
292 +       if (dlen == 1 && *fbuf == '.') {
293 +               restore_dot = 1;
294 +               p = fbuf;
295 +       } else if (dlen != 1 || *fbuf != '/')
296 +               *p++ = '/';
297 +       remainder = MAXPATHLEN - (p - fbuf);
298 +
299         /* If an item in dirlist is not found in flist, delete it
300          * from the filesystem. */
301         for (i = dirlist->used; i--; ) {
302 @@ -323,6 +344,10 @@ static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev)
303                                         f_name(fp, NULL));
304                         continue;
305                 }
306 +               if (detect_renamed && S_ISREG(fp->mode)) {
307 +                       strlcpy(p, fp->basename, remainder);
308 +                       look_for_rename(fp, fbuf);
309 +               }
310                 /* Here we want to match regardless of file type.  Replacement
311                  * of a file with one of another type is handled separately by
312                  * a delete_item call with a DEL_MAKE_ROOM flag. */
313 @@ -331,14 +356,19 @@ static void delete_in_dir(char *fbuf, struct file_struct *file, dev_t *fs_dev)
314                         if (!(fp->mode & S_IWUSR) && !am_root && fp->flags & FLAG_OWNED_BY_US)
315                                 flags |= DEL_NO_UID_WRITE;
316                         f_name(fp, delbuf);
317 -                       if (delete_during == 2) {
318 -                               if (!remember_delete(fp, delbuf, flags))
319 +                       if (delete_during == 2 && !(del_flags & DEL_NO_DELETIONS)) {
320 +                               if (!remember_delete(fp, delbuf, del_flags | flags))
321                                         break;
322                         } else
323 -                               delete_item(delbuf, fp->mode, flags);
324 -               }
325 +                               delete_item(delbuf, fp->mode, del_flags | flags);
326 +               } else if (detect_renamed && S_ISDIR(fp->mode))
327 +                       unexplored_dirs++;
328         }
329  
330 +       if (restore_dot)
331 +               fbuf[0] = '.';
332 +       fbuf[dlen] = '\0';
333 +
334         flist_free(dirlist);
335  }
336  
337 @@ -374,14 +404,125 @@ static void do_delete_pass(void)
338                  || !S_ISDIR(st.st_mode))
339                         continue;
340  
341 -               delete_in_dir(fbuf, file, &st.st_dev);
342 +               delete_in_dir(fbuf, file, &st.st_dev, 0);
343         }
344 -       delete_in_dir(NULL, NULL, &dev_zero);
345 +       delete_in_dir(NULL, NULL, &dev_zero, 0);
346  
347         if (INFO_GTE(FLIST, 2) && !am_server)
348                 rprintf(FINFO, "                    \r");
349  }
350  
351 +/* Search for a regular file that matches either (1) the size & modified
352 + * time (plus the basename, if possible) or (2) the size & checksum.  If
353 + * we find an exact match down to the dirname, return -1 because we found
354 + * an up-to-date file in the transfer, not a renamed file. */
355 +static int fattr_find(struct file_struct *f, char *fname)
356 +{
357 +       int low = the_fattr_list.low, high = the_fattr_list.high;
358 +       int mid, ok_match = -1, good_match = -1;
359 +       struct file_struct *fmid;
360 +       int diff;
361 +
362 +       while (low <= high) {
363 +               mid = (low + high) / 2;
364 +               fmid = the_fattr_list.files[mid];
365 +               if (F_LENGTH(fmid) != F_LENGTH(f)) {
366 +                       if (F_LENGTH(fmid) < F_LENGTH(f))
367 +                               low = mid + 1;
368 +                       else
369 +                               high = mid - 1;
370 +                       continue;
371 +               }
372 +               if (always_checksum) {
373 +                       /* We use the FLAG_FILE_SENT flag to indicate when we
374 +                        * have computed the checksum for an entry. */
375 +                       if (!(f->flags & FLAG_FILE_SENT)) {
376 +                               STRUCT_STAT st;
377 +                               if (fmid->modtime == f->modtime
378 +                                && f_name_cmp(fmid, f) == 0)
379 +                                       return -1; /* assume we can't help */
380 +                               st.st_size = F_LENGTH(f);
381 +                               st.st_mtime = f->modtime;
382 +                               file_checksum(fname, &st, F_SUM(f));
383 +                               f->flags |= FLAG_FILE_SENT;
384 +                       }
385 +                       diff = u_memcmp(F_SUM(fmid), F_SUM(f), checksum_len);
386 +                       if (diff) {
387 +                               if (diff < 0)
388 +                                       low = mid + 1;
389 +                               else
390 +                                       high = mid - 1;
391 +                               continue;
392 +                       }
393 +               } else {
394 +                       if (fmid->modtime != f->modtime) {
395 +                               if (fmid->modtime < f->modtime)
396 +                                       low = mid + 1;
397 +                               else
398 +                                       high = mid - 1;
399 +                               continue;
400 +                       }
401 +               }
402 +               ok_match = mid;
403 +               diff = u_strcmp(fmid->basename, f->basename);
404 +               if (diff == 0) {
405 +                       good_match = mid;
406 +                       if (fmid->dirname == f->dirname)
407 +                               return -1; /* file is up-to-date */
408 +                       if (!fmid->dirname) {
409 +                               low = mid + 1;
410 +                               continue;
411 +                       }
412 +                       if (!f->dirname) {
413 +                               high = mid - 1;
414 +                               continue;
415 +                       }
416 +                       diff = u_strcmp(fmid->dirname, f->dirname);
417 +                       if (diff == 0)
418 +                               return -1; /* file is up-to-date */
419 +               }
420 +               if (diff < 0)
421 +                       low = mid + 1;
422 +               else
423 +                       high = mid - 1;
424 +       }
425 +
426 +       return good_match >= 0 ? good_match : ok_match;
427 +}
428 +
429 +void look_for_rename(struct file_struct *file, char *fname)
430 +{
431 +       struct file_struct *fp;
432 +       char *partialptr, *fn;
433 +       STRUCT_STAT st;
434 +       int ndx;
435 +
436 +       if (!partial_dir || (ndx = fattr_find(file, fname)) < 0)
437 +               return;
438 +
439 +       fp = the_fattr_list.files[ndx];
440 +       fn = f_name(fp, NULL);
441 +       /* We don't provide an alternate-basis file if there is a basis file. */
442 +       if (link_stat(fn, &st, 0) == 0)
443 +               return;
444 +
445 +       if (!dry_run) {
446 +               if ((partialptr = partial_dir_fname(fn)) == NULL
447 +                || !handle_partial_dir(partialptr, PDIR_CREATE))
448 +                       return;
449 +               /* We only use the file if we can hard-link it into our tmp dir. */
450 +               if (link(fname, partialptr) != 0) {
451 +                       if (errno != EEXIST)
452 +                               handle_partial_dir(partialptr, PDIR_DELETE);
453 +                       return;
454 +               }
455 +       }
456 +
457 +       /* I think this falls into the -vv category with "%s is uptodate", etc. */
458 +       if (INFO_GTE(MISC, 2))
459 +               rprintf(FINFO, "found renamed: %s => %s\n", fname, fn);
460 +}
461 +
462  static inline int time_differs(struct file_struct *file, stat_x *sxp)
463  {
464         return cmp_time(sxp->st.st_mtime, file->modtime);
465 @@ -1151,6 +1292,7 @@ static void list_file_entry(struct file_struct *f)
466         }
467  }
468  
469 +static struct bitbag *delayed_bits = NULL;
470  static int phase = 0;
471  static int dflt_perms;
472  
473 @@ -1260,7 +1402,7 @@ static void recv_generator(char *fname, struct file_struct *file, int ndx,
474                          && do_stat(dn, &sx.st) < 0) {
475                                 if (dry_run)
476                                         goto parent_is_dry_missing;
477 -                               if (make_path(fname, MKP_DROP_NAME | MKP_SKIP_SLASH) < 0) {
478 +                               if (make_path(fname, ACCESSPERMS, MKP_DROP_NAME | MKP_SKIP_SLASH) < 0) {
479                                         rsyserr(FERROR_XFER, errno,
480                                                 "recv_generator: mkdir %s failed",
481                                                 full_fname(dn));
482 @@ -1413,7 +1555,7 @@ static void recv_generator(char *fname, struct file_struct *file, int ndx,
483                 }
484                 if (real_ret != 0 && do_mkdir(fname,file->mode|added_perms) < 0 && errno != EEXIST) {
485                         if (!relative_paths || errno != ENOENT
486 -                        || make_path(fname, MKP_DROP_NAME | MKP_SKIP_SLASH) < 0
487 +                        || make_path(fname, ACCESSPERMS, MKP_DROP_NAME | MKP_SKIP_SLASH) < 0
488                          || (do_mkdir(fname, file->mode|added_perms) < 0 && errno != EEXIST)) {
489                                 rsyserr(FERROR_XFER, errno,
490                                         "recv_generator: mkdir %s failed",
491 @@ -1462,9 +1604,12 @@ static void recv_generator(char *fname, struct file_struct *file, int ndx,
492                 }
493                 else if (delete_during && f_out != -1 && !phase
494                     && !(file->flags & FLAG_MISSING_DIR)) {
495 -                       if (file->flags & FLAG_CONTENT_DIR)
496 -                               delete_in_dir(fname, file, &real_sx.st.st_dev);
497 -                       else
498 +                       if (file->flags & FLAG_CONTENT_DIR) {
499 +                               if (detect_renamed && real_ret != 0)
500 +                                       unexplored_dirs++;
501 +                               delete_in_dir(fname, file, &real_sx.st.st_dev,
502 +                                             delete_during < 0 ? DEL_NO_DELETIONS : 0);
503 +                       } else
504                                 change_local_filter_dir(fname, strlen(fname), F_DEPTH(file));
505                 }
506                 goto cleanup;
507 @@ -1729,8 +1874,14 @@ static void recv_generator(char *fname, struct file_struct *file, int ndx,
508                         goto cleanup;
509                 }
510  #endif
511 -               if (stat_errno == ENOENT)
512 +               if (stat_errno == ENOENT) {
513 +                       if (detect_renamed && unexplored_dirs > 0
514 +                        && F_LENGTH(file)) {
515 +                               bitbag_set_bit(delayed_bits, ndx);
516 +                               return;
517 +                       }
518                         goto notify_others;
519 +               }
520                 rsyserr(FERROR_XFER, stat_errno, "recv_generator: failed to stat %s",
521                         full_fname(fname));
522                 goto cleanup;
523 @@ -2190,6 +2341,12 @@ void generate_files(int f_out, const char *local_name)
524         if (DEBUG_GTE(GENR, 1))
525                 rprintf(FINFO, "generator starting pid=%d\n", (int)getpid());
526  
527 +       if (detect_renamed) {
528 +               delayed_bits = bitbag_create(cur_flist->used);
529 +               if (!delete_before && !delete_during)
530 +                       delete_during = -1;
531 +       }
532 +
533         if (delete_before && !solo_file && cur_flist->used > 0)
534                 do_delete_pass();
535         if (delete_during == 2) {
536 @@ -2200,7 +2357,7 @@ void generate_files(int f_out, const char *local_name)
537         }
538         info_levels[INFO_FLIST] = info_levels[INFO_PROGRESS] = 0;
539  
540 -       if (append_mode > 0 || whole_file < 0)
541 +       if (append_mode > 0 || detect_renamed || whole_file < 0)
542                 whole_file = 0;
543         if (DEBUG_GTE(FLIST, 1)) {
544                 rprintf(FINFO, "delta-transmission %s\n",
545 @@ -2236,7 +2393,7 @@ void generate_files(int f_out, const char *local_name)
546                                                 dirdev = MAKEDEV(DEV_MAJOR(devp), DEV_MINOR(devp));
547                                         } else
548                                                 dirdev = MAKEDEV(0, 0);
549 -                                       delete_in_dir(fbuf, fp, &dirdev);
550 +                                       delete_in_dir(fbuf, fp, &dirdev, 0);
551                                 } else
552                                         change_local_filter_dir(fbuf, strlen(fbuf), F_DEPTH(fp));
553                         }
554 @@ -2283,7 +2440,21 @@ void generate_files(int f_out, const char *local_name)
555         } while ((cur_flist = cur_flist->next) != NULL);
556  
557         if (delete_during)
558 -               delete_in_dir(NULL, NULL, &dev_zero);
559 +               delete_in_dir(NULL, NULL, &dev_zero, 0);
560 +       if (detect_renamed) {
561 +               if (delete_during < 0)
562 +                       delete_during = 0;
563 +               detect_renamed = 0;
564 +
565 +               for (i = -1; (i = bitbag_next_bit(delayed_bits, i)) >= 0; ) {
566 +                       struct file_struct *file = cur_flist->files[i];
567 +                       if (local_name)
568 +                               strlcpy(fbuf, local_name, sizeof fbuf);
569 +                       else
570 +                               f_name(file, fbuf);
571 +                       recv_generator(fbuf, file, i, itemizing, code, f_out);
572 +               }
573 +       }
574         phase++;
575         if (DEBUG_GTE(GENR, 1))
576                 rprintf(FINFO, "generate_files phase=%d\n", phase);
577 diff --git a/main.c b/main.c
578 --- a/main.c
579 +++ b/main.c
580 @@ -850,7 +850,7 @@ static int do_recv(int f_in, int f_out, char *local_name)
581         }
582  
583         if (backup_dir) {
584 -               int ret = make_path(backup_dir_buf, MKP_DROP_NAME); /* drops trailing slash */
585 +               int ret = make_path(backup_dir_buf, ACCESSPERMS, MKP_DROP_NAME); /* drops trailing slash */
586                 if (ret < 0)
587                         exit_cleanup(RERR_SYNTAX);
588                 if (ret)
589 diff --git a/options.c b/options.c
590 --- a/options.c
591 +++ b/options.c
592 @@ -83,6 +83,7 @@ int am_server = 0;
593  int am_sender = 0;
594  int am_starting_up = 1;
595  int relative_paths = -1;
596 +int detect_renamed = 0;
597  int implied_dirs = 1;
598  int missing_args = 0; /* 0 = FERROR_XFER, 1 = ignore, 2 = delete */
599  int numeric_ids = 0;
600 @@ -760,6 +761,7 @@ void usage(enum logcode F)
601    rprintf(F,"     --modify-window=NUM     compare mod-times with reduced accuracy\n");
602    rprintf(F," -T, --temp-dir=DIR          create temporary files in directory DIR\n");
603    rprintf(F," -y, --fuzzy                 find similar file for basis if no dest file\n");
604 +  rprintf(F,"     --detect-renamed        try to find renamed files to speed up the transfer\n");
605    rprintf(F,"     --compare-dest=DIR      also compare destination files relative to DIR\n");
606    rprintf(F,"     --copy-dest=DIR         ... and include copies of unchanged files\n");
607    rprintf(F,"     --link-dest=DIR         hardlink to files in DIR when unchanged\n");
608 @@ -963,6 +965,7 @@ static struct poptOption long_options[] = {
609    {"compare-dest",     0,  POPT_ARG_STRING, 0, OPT_COMPARE_DEST, 0, 0 },
610    {"copy-dest",        0,  POPT_ARG_STRING, 0, OPT_COPY_DEST, 0, 0 },
611    {"link-dest",        0,  POPT_ARG_STRING, 0, OPT_LINK_DEST, 0, 0 },
612 +  {"detect-renamed",   0,  POPT_ARG_NONE,   &detect_renamed, 0, 0, 0 },
613    {"fuzzy",           'y', POPT_ARG_NONE,   0, 'y', 0, 0 },
614    {"no-fuzzy",         0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
615    {"no-y",             0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
616 @@ -2248,7 +2251,7 @@ int parse_arguments(int *argc_p, const char ***argv_p)
617                 inplace = 1;
618         }
619  
620 -       if (delay_updates && !partial_dir)
621 +       if ((delay_updates || detect_renamed) && !partial_dir)
622                 partial_dir = tmp_partialdir;
623  
624         if (inplace) {
625 @@ -2257,6 +2260,7 @@ int parse_arguments(int *argc_p, const char ***argv_p)
626                         snprintf(err_buf, sizeof err_buf,
627                                  "--%s cannot be used with --%s\n",
628                                  append_mode ? "append" : "inplace",
629 +                                detect_renamed ? "detect-renamed" :
630                                  delay_updates ? "delay-updates" : "partial-dir");
631                         return 0;
632                 }
633 @@ -2633,6 +2637,8 @@ void server_options(char **args, int *argc_p)
634                         args[ac++] = "--super";
635                 if (size_only)
636                         args[ac++] = "--size-only";
637 +               if (detect_renamed)
638 +                       args[ac++] = "--detect-renamed";
639                 if (do_stats)
640                         args[ac++] = "--stats";
641         } else {
642 diff --git a/receiver.c b/receiver.c
643 --- a/receiver.c
644 +++ b/receiver.c
645 @@ -212,7 +212,7 @@ int open_tmpfile(char *fnametmp, const char *fname, struct file_struct *file)
646          * information should have been previously transferred, but that may
647          * not be the case with -R */
648         if (fd == -1 && relative_paths && errno == ENOENT
649 -        && make_path(fnametmp, MKP_SKIP_SLASH | MKP_DROP_NAME) == 0) {
650 +        && make_path(fnametmp, ACCESSPERMS, MKP_SKIP_SLASH | MKP_DROP_NAME) == 0) {
651                 /* Get back to name with XXXXXX in it. */
652                 get_tmpname(fnametmp, fname, False);
653                 fd = do_mkstemp(fnametmp, (file->mode|added_perms) & INITACCESSPERMS);
654 diff --git a/rsync.h b/rsync.h
655 --- a/rsync.h
656 +++ b/rsync.h
657 @@ -252,7 +252,7 @@ enum msgcode {
658  #define NDX_DEL_STATS -3
659  #define NDX_FLIST_OFFSET -101
660  
661 -/* For calling delete_item() and delete_dir_contents(). */
662 +/* For calling delete_item(), delete_dir_contents(), and delete_in_dir(). */
663  #define DEL_NO_UID_WRITE       (1<<0) /* file/dir has our uid w/o write perm */
664  #define DEL_RECURSE            (1<<1) /* if dir, delete all contents */
665  #define DEL_DIR_IS_EMPTY       (1<<2) /* internal delete_FUNCTIONS use only */
666 @@ -262,6 +262,7 @@ enum msgcode {
667  #define DEL_FOR_DEVICE         (1<<6) /* making room for a replacement device */
668  #define DEL_FOR_SPECIAL        (1<<7) /* making room for a replacement special */
669  #define DEL_FOR_BACKUP         (1<<8) /* the delete is for a backup operation */
670 +#define DEL_NO_DELETIONS       (1<<9) /* just check for renames w/o deleting */
671  
672  #define DEL_MAKE_ROOM (DEL_FOR_FILE|DEL_FOR_DIR|DEL_FOR_SYMLINK|DEL_FOR_DEVICE|DEL_FOR_SPECIAL)
673  
674 diff --git a/rsync.yo b/rsync.yo
675 --- a/rsync.yo
676 +++ b/rsync.yo
677 @@ -416,6 +416,7 @@ to the detailed description below for a complete description.  verb(
678       --modify-window=NUM     compare mod-times with reduced accuracy
679   -T, --temp-dir=DIR          create temporary files in directory DIR
680   -y, --fuzzy                 find similar file for basis if no dest file
681 +     --detect-renamed        try to find renamed files to speed the xfer
682       --compare-dest=DIR      also compare received files relative to DIR
683       --copy-dest=DIR         ... and include copies of unchanged files
684       --link-dest=DIR         hardlink to files in DIR when unchanged
685 @@ -1798,6 +1799,21 @@ Note that the use of the bf(--delete) option might get rid of any potential
686  fuzzy-match files, so either use bf(--delete-after) or specify some
687  filename exclusions if you need to prevent this.
688  
689 +dit(bf(--detect-renamed)) With this option, for each new source file
690 +(call it em(src/S)), rsync looks for a file em(dest/D) anywhere in the
691 +destination that passes the quick check with em(src/S).  If such a em(dest/D)
692 +is found, rsync uses it as an alternate basis for transferring em(S).  The
693 +idea is that if em(src/S) was renamed from em(src/D) (as opposed to em(src/S)
694 +passing the quick check with em(dest/D) by coincidence), the delta-transfer
695 +algorithm will find that all the data matches between em(src/S) and em(dest/D),
696 +and the transfer will be really fast.
697 +
698 +By default, alternate-basis files are hard-linked into a directory named
699 +".~tmp~" in each file's destination directory, but if you've specified
700 +the bf(--partial-dir) option, that directory will be used instead.  These
701 +potential alternate-basis files will be removed as the transfer progresses.
702 +This option conflicts with bf(--inplace) and bf(--append).
703 +
704  dit(bf(--compare-dest=DIR)) This option instructs rsync to use em(DIR) on
705  the destination machine as an additional hierarchy to compare destination
706  files against doing transfers (if the files are missing in the destination
707 diff --git a/util.c b/util.c
708 --- a/util.c
709 +++ b/util.c
710 @@ -175,7 +175,7 @@ int set_modtime(const char *fname, time_t modtime, uint32 mod_nsec, mode_t mode)
711  /* Create any necessary directories in fname.  Any missing directories are
712   * created with default permissions.  Returns < 0 on error, or the number
713   * of directories created. */
714 -int make_path(char *fname, int flags)
715 +int make_path(char *fname, mode_t mode, int flags)
716  {
717         char *end, *p;
718         int ret = 0;
719 @@ -206,7 +206,7 @@ int make_path(char *fname, int flags)
720                                 else
721                                         errno = ENOTDIR;
722                         }
723 -               } else if (do_mkdir(fname, ACCESSPERMS) == 0) {
724 +               } else if (do_mkdir(fname, mode) == 0) {
725                         ret++;
726                         break;
727                 }
728 @@ -243,7 +243,7 @@ int make_path(char *fname, int flags)
729                 p += strlen(p);
730                 if (ret < 0) /* Skip mkdir on error, but keep restoring the path. */
731                         continue;
732 -               if (do_mkdir(fname, ACCESSPERMS) < 0)
733 +               if (do_mkdir(fname, mode) < 0)
734                         ret = -ret - 1;
735                 else
736                         ret++;
737 @@ -1131,6 +1131,32 @@ char *normalize_path(char *path, BOOL force_newbuf, unsigned int *len_ptr)
738         return path;
739  }
740  
741 +/* We need to supply our own strcmp function for file list comparisons
742 + * to ensure that signed/unsigned usage is consistent between machines. */
743 +int u_strcmp(const char *p1, const char *p2)
744 +{
745 +        for ( ; *p1; p1++, p2++) {
746 +               if (*p1 != *p2)
747 +                       break;
748 +       }
749 +
750 +       return (int)*(uchar*)p1 - (int)*(uchar*)p2;
751 +}
752 +
753 +/* We need a memcmp function compares unsigned-byte values. */
754 +int u_memcmp(const void *p1, const void *p2, size_t len)
755 +{
756 +       const uchar *u1 = p1;
757 +       const uchar *u2 = p2;
758 +
759 +       while (len--) {
760 +               if (*u1 != *u2)
761 +                       return (int)*u1 - (int)*u2;
762 +       }
763 +
764 +       return 0;
765 +}
766 +
767  /**
768   * Return a quoted string with the full pathname of the indicated filename.
769   * The string " (in MODNAME)" may also be appended.  The returned pointer
770 @@ -1224,7 +1250,7 @@ int handle_partial_dir(const char *fname, int create)
771                         }
772                         statret = -1;
773                 }
774 -               if (statret < 0 && do_mkdir(dir, 0700) < 0) {
775 +               if (statret < 0 && make_path(dir, 0700, 0) < 0) {
776                         *fn = '/';
777                         return 0;
778                 }