Download raw body.
rsync(1): add fuzzy mode
When I was creating a package mirror for my local VMs I noticed that
--fuzzy is recommended on on the website [0] when using rsync(1). Sadly the
option is currently not supported (same as --delete-delay and
--delay-updates).
This patches add the --fuzzy option to rsync(1), a regress test and
updates the man page.
Like the rsync from ports this patch also adds the mtime and size beats
filenames short curcuit. That means a renamed file with the same size will
be the best match based on its size (and mtime) and not on its name.
[0] https://www.openbsd.org/ftp.html
diff --git regress/usr.bin/rsync/test14_fuzzy.test regress/usr.bin/rsync/test14_fuzzy.test
new file mode 100644
index 00000000000..5c696550cf4
--- /dev/null
+++ regress/usr.bin/rsync/test14_fuzzy.test
@@ -0,0 +1,32 @@
+#! /bin/sh
+
+. ${tstdir-.}/lib.sh
+. ${tstdir-.}/conf.sh
+
+umask 022
+rm -rf dir1 dir2 dir3
+
+mkdir dir1
+cd dir1
+dd if=/dev/zero bs=1m count=1 status=none > data.txt
+echo "the new version of the file" >> data.txt
+cd ..
+
+# the files we want
+mkdir dir2
+cd dir2
+dd if=/dev/zero bs=1m count=1 status=none > data.txt
+echo "the new version of the file" >> data.txt
+dd if=/dev/zero bs=1m count=1 status=none > data.txt.bak
+echo "the old version of the file" >> data.txt.bak
+cd ..
+
+mkdir dir3
+cd dir3
+dd if=/dev/zero bs=1m count=1 status=none > data.txt.bak
+echo "the old version of the file" >> data.txt.bak
+cd ..
+
+echo $rsync -a --ignore-times --fuzzy dir1/ dir3
+$rsync -a --ignore-times --fuzzy dir1/ dir3
+compare_trees dir2 dir3
diff --git usr.bin/rsync/Makefile usr.bin/rsync/Makefile
index 3c60f18e07f..ae83024f3c9 100644
--- usr.bin/rsync/Makefile
+++ usr.bin/rsync/Makefile
@@ -1,8 +1,8 @@
# $OpenBSD: Makefile,v 1.13 2021/10/29 08:00:59 claudio Exp $
PROG= openrsync
-SRCS= blocks.c client.c copy.c downloader.c fargs.c flist.c hash.c ids.c \
- io.c log.c main.c misc.c mkpath.c mktemp.c receiver.c rmatch.c \
+SRCS= blocks.c client.c copy.c downloader.c fargs.c flist.c fuzzy.c hash.c \
+ ids.c io.c log.c main.c misc.c mkpath.c mktemp.c receiver.c rmatch.c \
rules.c sender.c server.c session.c socket.c symlinks.c uploader.c
LDADD+= -lcrypto -lm -lutil
DPADD+= ${LIBCRYPTO} ${LIBM} ${LIBUTIL}
diff --git usr.bin/rsync/downloader.c usr.bin/rsync/downloader.c
index cab6eb23f9f..100e5fe3742 100644
--- usr.bin/rsync/downloader.c
+++ usr.bin/rsync/downloader.c
@@ -64,6 +64,7 @@ struct download {
const struct flist *fl; /* file list */
size_t flsz; /* size of file list */
int rootfd; /* destination directory */
+ char **basis; /* fuzzy basis per file or NULL */
int fdin; /* read descriptor from sender */
char *obuf; /* pre-write buffer */
size_t obufsz; /* current size of obuf */
@@ -172,7 +173,7 @@ download_cleanup(struct download *p, int cleanup)
*/
struct download *
download_alloc(struct sess *sess, int fdin,
- const struct flist *fl, size_t flsz, int rootfd)
+ const struct flist *fl, size_t flsz, int rootfd, char **basis)
{
struct download *p;
@@ -185,6 +186,7 @@ download_alloc(struct sess *sess, int fdin,
p->fl = fl;
p->flsz = flsz;
p->rootfd = rootfd;
+ p->basis = basis;
p->fdin = fdin;
download_reinit(sess, p, 0);
p->obufsz = 0;
@@ -360,7 +362,18 @@ rsync_downloader(struct download *p, struct sess *sess, int *ofd)
return 1;
}
- /* Fall-through: there's no file. */
+ /* There's no exact file. Try fuzzy basis, if enabled. */
+ if (p->basis != NULL && sess->opts->fuzzy &&
+ p->basis[idx] != NULL) {
+ p->ofd = openat(p->rootfd, p->basis[idx],
+ O_RDONLY | O_NONBLOCK);
+ if (p->ofd == -1) {
+ ERR("%s: openat", p->basis[idx]);
+ goto out;
+ }
+ *ofd = p->ofd;
+ return 1;
+ }
}
/*
diff --git usr.bin/rsync/extern.h usr.bin/rsync/extern.h
index e4dd3031116..8d342d9c5dd 100644
--- usr.bin/rsync/extern.h
+++ usr.bin/rsync/extern.h
@@ -143,6 +143,7 @@ struct opts {
int preserve_uids; /* -u */
int del; /* --delete */
int devices; /* --devices */
+ int fuzzy; /* --fuzzy */
int specials; /* --specials */
int no_motd; /* --no-motd */
int numeric_ids; /* --numeric-ids */
@@ -324,6 +325,8 @@ int flist_gen_dels(struct sess *, const char *, struct flist **, size_t *,
const char *alt_base_mode(int);
char **fargs_cmdline(struct sess *, const struct fargs *, size_t *);
+char *fuzzy_find(int, const struct flist *, size_t, size_t);
+
int io_read_buf(struct sess *, int, void *, size_t);
int io_read_byte(struct sess *, int, uint8_t *);
int io_read_check(int);
@@ -368,10 +371,10 @@ int rsync_uploader(struct upload *, int *, struct sess *, int *);
int rsync_uploader_tail(struct upload *, struct sess *);
struct download *download_alloc(struct sess *, int, const struct flist *,
- size_t, int);
+ size_t, int, char **);
void download_free(struct download *);
struct upload *upload_alloc(const char *, int, int, size_t,
- const struct flist *, size_t, mode_t);
+ const struct flist *, size_t, mode_t, char **);
void upload_free(struct upload *);
struct blktab *blkhash_alloc(void);
diff --git usr.bin/rsync/fargs.c usr.bin/rsync/fargs.c
index cbc8537f38c..afbd4c3da46 100644
--- usr.bin/rsync/fargs.c
+++ usr.bin/rsync/fargs.c
@@ -146,6 +146,8 @@ fargs_cmdline(struct sess *sess, const struct fargs *f, size_t *skip)
addargs(&args, "-J");
if (sess->opts->size_only)
addargs(&args, "--size-only");
+ if (sess->opts->fuzzy)
+ addargs(&args, "--fuzzy");
/* only add --compare-dest, etc if this is the sender */
if (sess->opts->alt_base_mode != 0) {
diff --git usr.bin/rsync/fuzzy.c usr.bin/rsync/fuzzy.c
new file mode 100644
index 00000000000..8b8af01e365
--- /dev/null
+++ usr.bin/rsync/fuzzy.c
@@ -0,0 +1,290 @@
+/*
+ * Copyright (c) 2026 Jan Schreiber <jes@posteo.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+
+#include <sys/stat.h>
+
+#include <dirent.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "extern.h"
+
+#define SCALE (1 << 16)
+
+/* Levenshtein distance algorithm */
+static uint32_t
+fuzzy_distance(const char *s1, size_t l1, const char *s2, size_t l2,
+ uint32_t limit)
+{
+ size_t i, j;
+ uint32_t cost, del, ins, sub, ret;
+ uint32_t **d;
+
+ if (l1 == 0)
+ return l2 * SCALE;
+ if (l2 == 0)
+ return l1 * SCALE;
+
+ if (l1 > l2) {
+ if ((l1 - l2) > limit)
+ return UINT32_MAX;
+ } else {
+ if ((l2 - l1) > limit)
+ return UINT32_MAX;
+ }
+
+
+ if ((d = reallocarray(NULL, l1 + 1, sizeof(*d))) == NULL) {
+ ERR("reallocarray");
+ return UINT32_MAX;
+ }
+
+ for (i = 0; i <= l1; i++) {
+ if ((d[i] = reallocarray(NULL, l2 + 1, sizeof(**d))) == NULL) {
+ while (i-- > 0)
+ free(d[i]);
+ free(d);
+ ERR("reallocarray");
+ return UINT32_MAX;
+ }
+ }
+
+
+ for (i = 0; i <= l1; i++)
+ d[i][0] = i * SCALE;
+ for (j = 0; j <= l2; j++)
+ d[0][j] = j * SCALE;
+
+ for (i = 1; i <= l1; i++) {
+ for (j = 1; j <= l2; j++) {
+ if (s1[i - 1] == s2[j - 1])
+ cost = 0;
+ else
+ cost = SCALE;
+
+ del = d[i - 1][j] + SCALE;
+ ins = d[i][j - 1] + SCALE;
+ sub = d[i - 1][j - 1] + cost;
+
+ d[i][j] = MINIMUM(del, MINIMUM(ins, sub));
+ }
+ }
+ ret = d[l1][l2];
+ for (i = 0; i <= l1; i++)
+ free(d[i]);
+ free(d);
+
+
+ return ret;
+}
+
+/* Return a pointer to the filename ending after a ".". */
+static const char *
+fuzzy_suffix(const char *name, size_t len, size_t *suflen)
+{
+ const char *dot = NULL;
+ size_t i;
+
+ for (i = 1; i + 1 < len; i++)
+ if (name[i] == '.')
+ dot = &name[i];
+
+ if (dot == NULL) {
+ *suflen = 0;
+ return name + len;
+ }
+
+ *suflen = len - (dot + 1 - name);
+
+ return dot + 1;
+}
+
+/* Score removes one SCALE (one edit) if both extensions match. */
+static uint32_t
+fuzzy_score(const char *base, size_t baselen,
+ const char *cand, size_t candlen, uint32_t limit)
+{
+ const char *bsuf, *csuf;
+ size_t bsuflen, csuflen;
+ uint32_t dist;
+
+ dist = fuzzy_distance(base, baselen, cand, candlen, limit);
+ if (dist == UINT32_MAX)
+ return dist;
+
+ bsuf = fuzzy_suffix(base, baselen, &bsuflen);
+ csuf = fuzzy_suffix(cand, candlen, &csuflen);
+
+ if (bsuflen != 0 && bsuflen == csuflen &&
+ memcmp(bsuf, csuf, bsuflen) == 0)
+ dist -= MINIMUM(dist, SCALE);
+
+ return dist;
+}
+
+/* Do not choose our own temp files as basis. */
+static int
+fuzzy_is_tmp(const char *name, size_t len)
+{
+ if (len < 13)
+ return 0;
+ if (name[0] != '.')
+ return 0;
+ return name[len - 11] == '.';
+}
+
+static int
+fuzzy_in_flist(const struct flist *fl, size_t flsz, const char *path)
+{
+ size_t i;
+
+ for (i = 0; i < flsz; i++)
+ if (strcmp(fl[i].path, path) == 0)
+ return 1;
+
+ return 0;
+}
+
+char *
+fuzzy_find(int rootfd, const struct flist *fl, size_t flsz, size_t idx)
+{
+ DIR *dirp;
+ struct dirent *dp;
+ struct stat st;
+ const char *path = fl[idx].path;
+ const char *base;
+ char *dir = NULL, *best = NULL, *cand;
+ size_t baselen, dirlen;
+ int dfd;
+ uint32_t dist, lowest = UINT32_MAX;
+ uint32_t limit;
+
+ base = strrchr(path, '/');
+ if (base == NULL) {
+ base = path;
+ dirlen = 0;
+ } else {
+ dirlen = base - path;
+ base++;
+ }
+ baselen = strlen(base);
+ if (baselen == 0)
+ return NULL;
+
+ if (dirlen == 0)
+ dfd = openat(rootfd, ".", O_RDONLY | O_DIRECTORY);
+ else {
+ if ((dir = strndup(path, dirlen)) == NULL) {
+ ERR("strndup");
+ return NULL;
+ }
+ dfd = openat(rootfd, dir, O_RDONLY | O_DIRECTORY);
+ }
+
+ if (dfd == -1) {
+ if (errno != ENOENT)
+ ERR("%s: openat", dir != NULL ? dir : ".");
+ free(dir);
+ return NULL;
+ }
+
+ if ((dirp = fdopendir(dfd)) == NULL) {
+ ERR("fdopendir");
+ close(dfd);
+ free(dir);
+ return NULL;
+ }
+
+ while ((dp = readdir(dirp)) != NULL) {
+ const char *name = dp->d_name;
+
+ if (name[0] == '.' && (name[1] == '\0' ||
+ (name[1] == '.' && name[2] == '\0')))
+ continue;
+
+ if (strcmp(name, base) == 0)
+ continue;
+
+ if (fuzzy_is_tmp(name, strlen(name)))
+ continue;
+
+ if (fstatat(dfd, name, &st, AT_SYMLINK_NOFOLLOW) == -1)
+ continue;
+ if (!S_ISREG(st.st_mode))
+ continue;
+ /* Skip zero length candidates. */
+ if (st.st_size == 0)
+ continue;
+
+ if (dirlen == 0) {
+ cand = strdup(name);
+ if (cand == NULL) {
+ ERR("strdup");
+ break;
+ }
+ }
+ else if (asprintf(&cand, "%s/%s", dir, name) == -1)
+ cand = NULL;
+ if (cand == NULL) {
+ ERR("asprintf");
+ break;
+ }
+
+ if (fuzzy_in_flist(fl, flsz, cand)) {
+ free(cand);
+ continue;
+ }
+
+ /* Same size and mtime beats file name scores. */
+ if (st.st_size == fl[idx].st.size &&
+ st.st_mtime == fl[idx].st.mtime) {
+ free(best);
+ best = cand;
+ break;
+ }
+
+ if (lowest == UINT32_MAX)
+ limit = baselen;
+ else
+ limit = lowest / SCALE;
+
+ dist = fuzzy_score(base, baselen, name, strlen(name),
+ limit);
+
+ if (dist >= lowest) {
+ free(cand);
+ continue;
+ }
+
+ lowest = dist;
+ free(best);
+ best = cand;
+ }
+
+ closedir(dirp);
+ free(dir);
+
+ if (best != NULL)
+ LOG3("%s: fuzzy basis is %s", path, best);
+
+ return best;
+}
diff --git usr.bin/rsync/main.c usr.bin/rsync/main.c
index 26063fcf343..4873ddb7ec1 100644
--- usr.bin/rsync/main.c
+++ usr.bin/rsync/main.c
@@ -310,6 +310,7 @@ const struct option lopts[] = {
{ "dry-run", no_argument, &opts.dry_run, 1 },
{ "exclude", required_argument, NULL, OP_EXCLUDE },
{ "exclude-from", required_argument, NULL, OP_EXCLUDE_FROM },
+ { "fuzzy", no_argument, &opts.fuzzy, 1 },
{ "group", no_argument, &opts.preserve_gids, 1 },
{ "no-group", no_argument, &opts.preserve_gids, 0 },
{ "help", no_argument, NULL, 'h' },
@@ -370,7 +371,7 @@ main(int argc, char *argv[])
opts.max_size = opts.min_size = -1;
- while ((c = getopt_long(argc, argv, "aDe:ghIJlnOoprtVvxz",
+ while ((c = getopt_long(argc, argv, "aDe:ghIJlnOoprtVvxyz",
lopts, &lidx)) != -1) {
switch (c) {
case 'D':
@@ -430,6 +431,9 @@ main(int argc, char *argv[])
case 'x':
opts.one_file_system++;
break;
+ case 'y':
+ opts.fuzzy = 1;
+ break;
case 'z':
fprintf(stderr, "%s: -z not supported yet\n", getprogname());
break;
@@ -659,9 +663,9 @@ basedir:
exit(rc);
usage:
fprintf(stderr, "usage: %s"
- " [-aDgIJlnOoprtVvx] [-e program] [--address=sourceaddr]\n"
+ " [-aDgIJlnOoprtVvxy] [-e program] [--address=sourceaddr]\n"
"\t[--contimeout=seconds] [--compare-dest=dir] [--del] [--exclude]\n"
- "\t[--exclude-from=file] [--include] [--include-from=file]\n"
+ "\t[--exclude-from=file] [--fuzzy] [--include] [--include-from=file]\n"
"\t[--no-motd] [--numeric-ids] [--port=portnumber]\n"
"\t[--rsync-path=program] [--size-only] [--timeout=seconds]\n"
"\tsource ... directory\n",
diff --git usr.bin/rsync/receiver.c usr.bin/rsync/receiver.c
index 3cef0528003..0c638074c50 100644
--- usr.bin/rsync/receiver.c
+++ usr.bin/rsync/receiver.c
@@ -180,6 +180,7 @@ rsync_receiver(struct sess *sess, int fdin, int fdout, const char *root)
struct pollfd pfd[PFD__MAX];
struct download *dl = NULL;
struct upload *ul = NULL;
+ char **basis = NULL;
mode_t oumask;
/*
@@ -289,15 +290,21 @@ rsync_receiver(struct sess *sess, int fdin, int fdout, const char *root)
pfd[PFD_DOWNLOADER_IN].events = POLLIN;
pfd[PFD_SENDER_OUT].events = POLLOUT;
+ if (sess->opts->fuzzy && flsz > 0 &&
+ (basis = calloc(flsz, sizeof(char *))) == NULL) {
+ ERR("calloc");
+ goto out;
+ }
+
ul = upload_alloc(root, dfd, fdout, CSUM_LENGTH_PHASE1, fl, flsz,
- oumask);
+ oumask, basis);
if (ul == NULL) {
ERRX1("upload_alloc");
goto out;
}
- dl = download_alloc(sess, fdin, fl, flsz, dfd);
+ dl = download_alloc(sess, fdin, fl, flsz, dfd, basis);
if (dl == NULL) {
ERRX1("download_alloc");
goto out;
@@ -437,6 +444,11 @@ out:
close(dfd);
upload_free(ul);
download_free(dl);
+ if (basis != NULL) {
+ for (i = 0; i < flsz; i++)
+ free(basis[i]);
+ free(basis);
+ }
flist_free(fl, flsz);
flist_free(dfl, dflsz);
return rc;
diff --git usr.bin/rsync/rsync.1 usr.bin/rsync/rsync.1
index d8660fec7f9..a357713dbc2 100644
--- usr.bin/rsync/rsync.1
+++ usr.bin/rsync/rsync.1
@@ -22,7 +22,7 @@
.Nd synchronise local and remote files
.Sh SYNOPSIS
.Nm openrsync
-.Op Fl aDgIJlnOoprtVvx
+.Op Fl aDgIJlnOoprtVvxy
.Op Fl e Ar program
.Op Fl -address Ns = Ns Ar sourceaddr
.Op Fl -compare-dest Ns = Ns Ar directory
@@ -231,6 +231,19 @@ Do not cross filesystem boundaries.
If this option is repeated, all mount point directories from the copy are
omitted.
Otherwise, it includes an empty directory at each mount point it encounters.
+.It Fl y , -fuzzy
+When a file to be transferred does not exist in the destination
+directory, look for a file in the same directory with a similar name
+and use it as the basis for the delta transfer.
+If a file of identical size and modification time is found, it is preferred
+to the one with a similar name.
+Only regular files are considered.
+Files that are themselves part of the transfer are ignored.
+If
+.Fl -delete
+is also given, destination files that do not exist in the source are
+removed before the transfer begins and are therefore not available
+as a basis.
.El
.Pp
A remote
diff --git usr.bin/rsync/uploader.c usr.bin/rsync/uploader.c
index 4d534e4a4aa..9e5b9ce646b 100644
--- usr.bin/rsync/uploader.c
+++ usr.bin/rsync/uploader.c
@@ -57,6 +57,7 @@ struct upload {
const struct flist *fl; /* file list */
size_t flsz; /* size of file list */
int *newdir; /* non-zero if mkdir'd */
+ char **basis; /* fuzzy basis per file or NULL */
};
/*
@@ -796,6 +797,30 @@ pre_file(const struct upload *p, int *filefd, off_t *size,
return -1;
}
+ /* With fuzzy, use a similarly named file as basis. */
+ if (*filefd == -1 && sess->opts->fuzzy && p->basis != NULL) {
+ char *fz;
+
+ /* Clear any stale entry from rsync's phase 1. */
+ free(p->basis[p->idx]);
+ p->basis[p->idx] = NULL;
+
+ if ((fz = fuzzy_find(p->rootfd, p->fl, p->flsz, p->idx)) !=
+ NULL) {
+ *filefd = openat(p->rootfd, fz, O_RDONLY | O_NOFOLLOW);
+ if (*filefd == -1 || fstat(*filefd, &st) == -1 ||
+ !S_ISREG(st.st_mode)) {
+ if (*filefd != -1)
+ close(*filefd);
+ *filefd = -1;
+ free(fz);
+ } else {
+ *size = st.st_size;
+ p->basis[p->idx] = fz;
+ }
+ }
+ }
+
/* file needs attention */
return 1;
}
@@ -807,7 +832,8 @@ pre_file(const struct upload *p, int *filefd, off_t *size,
*/
struct upload *
upload_alloc(const char *root, int rootfd, int fdout,
- size_t clen, const struct flist *fl, size_t flsz, mode_t msk)
+ size_t clen, const struct flist *fl, size_t flsz, mode_t msk,
+ char **basis)
{
struct upload *p;
@@ -829,6 +855,7 @@ upload_alloc(const char *root, int rootfd, int fdout,
p->fdout = fdout;
p->fl = fl;
p->flsz = flsz;
+ p->basis = basis;
p->newdir = calloc(flsz, sizeof(int));
if (p->newdir == NULL) {
ERR("calloc");
rsync(1): add fuzzy mode