From: Jan Schreiber Subject: rsync(1): add fuzzy mode To: tech@openbsd.org Date: Tue, 20 Oct 2026 15:05:29 +0000 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 + * + * 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 + +#include +#include +#include +#include +#include +#include +#include +#include + +#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");