3 This patch adds the --link-by-hash=DIR option, which hard links received files
4 in a link farm arranged by MD4 or MD5 file hash. The result is that the system
5 will only store one copy of the unique contents of each file, regardless of the
8 To use this patch, run these commands for a successful build:
10 patch -p1 <patches/link-by-hash.diff
15 based-on: 1e9ee19a716b72454dfeab663802c626b81cdf2e
16 diff --git a/Makefile.in b/Makefile.in
19 @@ -37,7 +37,7 @@ OBJS1=flist.o rsync.o generator.o receiver.o cleanup.o sender.o exclude.o \
20 util.o main.o checksum.o match.o syscall.o log.o backup.o delete.o
21 OBJS2=options.o io.o compat.o hlink.o token.o uidlist.o socket.o hashtable.o \
22 fileio.o batch.o clientname.o chmod.o acls.o xattrs.o
23 -OBJS3=progress.o pipe.o
24 +OBJS3=progress.o pipe.o hashlink.o
25 DAEMON_OBJ = params.o loadparm.o clientserver.o access.o connection.o authenticate.o
26 popt_OBJS=popt/findme.o popt/popt.o popt/poptconfig.o \
27 popt/popthelp.o popt/poptparse.o
28 diff --git a/checksum.c b/checksum.c
35 +extern int checksum_len;
36 extern int checksum_seed;
37 extern int protocol_version;
38 +extern char *link_by_hash_dir;
39 +extern char link_by_hash_extra_sum[MAX_DIGEST_LEN];
42 a simple 32 bit checksum that can be upadted from either end
43 @@ -151,7 +154,7 @@ void file_checksum(char *fname, char *sum, OFF_T size)
46 static int32 sumresidue;
47 -static md_context md;
48 +static md_context md, md2;
50 void sum_init(int seed)
52 @@ -164,6 +167,8 @@ void sum_init(int seed)
56 + if (link_by_hash_dir)
61 @@ -182,6 +187,9 @@ void sum_update(const char *p, int32 len)
65 + if (link_by_hash_dir)
66 + md5_update(&md2, (uchar *)p, len);
68 if (len + sumresidue < CSUM_CHUNK) {
69 memcpy(md.buffer + sumresidue, p, len);
71 @@ -214,6 +222,9 @@ int sum_end(char *sum)
72 return MD5_DIGEST_LEN;
75 + if (link_by_hash_dir)
76 + md5_result(&md2, (uchar *)link_by_hash_extra_sum);
78 if (sumresidue || protocol_version >= 27)
79 mdfour_update(&md, (uchar *)md.buffer, sumresidue);
81 @@ -221,3 +232,24 @@ int sum_end(char *sum)
83 return MD4_DIGEST_LEN;
86 +const char *sum_as_hex(const char *sum)
88 + static char buf[MAX_DIGEST_LEN*2+1];
90 + char *c = buf + checksum_len*2;
92 + assert(c - buf < (int)sizeof buf);
96 + for (i = checksum_len; --i >= 0; ) {
100 + *--c = x1 <= 9 ? x1 + '0' : x1 + 'a' - 10;
101 + *--c = x2 <= 9 ? x2 + '0' : x2 + 'a' - 10;
106 diff --git a/clientserver.c b/clientserver.c
109 @@ -50,6 +50,7 @@ extern int logfile_format_has_i;
110 extern int logfile_format_has_o_or_i;
111 extern char *bind_address;
112 extern char *config_file;
113 +extern char *link_by_hash_dir;
114 extern char *logfile_format;
115 extern char *files_from;
117 @@ -548,6 +549,9 @@ static int rsync_module(int f_in, int f_out, int i, const char *addr, const char
121 + if (*lp_link_by_hash_dir(i))
122 + link_by_hash_dir = lp_link_by_hash_dir(i);
124 if (am_daemon && am_server) {
125 rprintf(FLOG, "rsync allowed access on module %s from %s (%s)\n",
127 diff --git a/compat.c b/compat.c
130 @@ -55,6 +55,7 @@ extern char *partial_dir;
131 extern char *dest_option;
132 extern char *files_from;
133 extern char *filesfrom_host;
134 +extern char *link_by_hash_dir;
135 extern filter_rule_list filter_list;
136 extern int need_unsorted_flist;
138 diff --git a/hashlink.c b/hashlink.c
144 + Copyright (C) Cronosys, LLC 2004
146 + This program is free software; you can redistribute it and/or modify
147 + it under the terms of the GNU General Public License as published by
148 + the Free Software Foundation; either version 2 of the License, or
149 + (at your option) any later version.
151 + This program is distributed in the hope that it will be useful,
152 + but WITHOUT ANY WARRANTY; without even the implied warranty of
153 + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
154 + GNU General Public License for more details.
156 + You should have received a copy of the GNU General Public License
157 + along with this program; if not, write to the Free Software
158 + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
161 +/* This file contains code used by the --link-by-hash option. */
166 +extern int protocol_version;
167 +extern char *link_by_hash_dir;
168 +extern char sender_file_sum[MAX_DIGEST_LEN];
170 +char link_by_hash_extra_sum[MAX_DIGEST_LEN]; /* Only used when md4 sums are in the transfer */
174 +/* This function is always called after a file is received, so the
175 + * sender_file_sum buffer has whatever the last checksum was for the
176 + * transferred file. */
177 +void link_by_hash(const char *fname, const char *fnametmp, struct file_struct *file)
180 + char *hashname, *last_slash, *num_str;
184 + /* We don't bother to hard-link 0-length files. */
185 + if (F_LENGTH(file) == 0)
188 + hex = sum_as_hex(protocol_version >= 30 ? sender_file_sum : link_by_hash_extra_sum);
189 + if (asprintf(&hashname, "%s/%.3s/%.3s/%.3s/%s.%s.000000",
190 + link_by_hash_dir, hex, hex+3, hex+6, hex+9, big_num(F_LENGTH(file))) < 0)
192 + out_of_memory("make_hash_name");
195 + last_slash = strrchr(hashname, '/');
196 + num_str = strrchr(last_slash, '.') + 1;
199 + if (num >= 999999) { /* Surely we'll never reach this... */
200 + if (DEBUG_GTE(HASHLINK, 1))
201 + rprintf(FINFO, "link-by-hash: giving up after \"%s\".\n", hashname);
204 + if (num > 0 && DEBUG_GTE(HASHLINK, 1))
205 + rprintf(FINFO, "link-by-hash: max link count exceeded, starting new file \"%s\".\n", hashname);
207 + snprintf(num_str, 7, "%d", num++);
208 + if (do_stat(hashname, &st) < 0)
211 + if (do_link(hashname, fnametmp) < 0) {
212 + if (errno == EMLINK)
214 + rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", hashname, full_fname(fname));
216 + if (DEBUG_GTE(HASHLINK, 2))
217 + rprintf(FINFO, "link-by-hash (existing): \"%s\" -> %s\n", hashname, full_fname(fname));
218 + robust_rename(fnametmp, fname, NULL, 0644);
224 + if (DEBUG_GTE(HASHLINK, 2))
225 + rprintf(FINFO, "link-by-hash (new): %s -> \"%s\"\n", full_fname(fname), hashname);
227 + if (do_link(fname, hashname) < 0
228 + && (errno != ENOENT || make_path(hashname, MKP_DROP_NAME) < 0 || do_link(fname, hashname) < 0))
229 + rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", full_fname(fname), hashname);
235 diff --git a/loadparm.c b/loadparm.c
238 @@ -119,6 +119,7 @@ typedef struct {
241 char *incoming_chmod;
242 + char *link_by_hash_dir;
246 @@ -195,6 +196,7 @@ static const all_vars Defaults = {
248 /* include_from; */ NULL,
249 /* incoming_chmod; */ NULL,
250 + /* link_by_hash_dir; */ NULL,
251 /* lock_file; */ DEFAULT_LOCK_FILE,
252 /* log_file; */ NULL,
253 /* log_format; */ "%o %h [%a] %m (%u) %f %l",
254 @@ -336,6 +338,7 @@ static struct parm_struct parm_table[] =
255 {"include from", P_STRING, P_LOCAL, &Vars.l.include_from, NULL,0},
256 {"include", P_STRING, P_LOCAL, &Vars.l.include, NULL,0},
257 {"incoming chmod", P_STRING, P_LOCAL, &Vars.l.incoming_chmod, NULL,0},
258 + {"link by hash dir", P_STRING, P_LOCAL, &Vars.l.link_by_hash_dir, NULL,0},
259 {"list", P_BOOL, P_LOCAL, &Vars.l.list, NULL,0},
260 {"lock file", P_STRING, P_LOCAL, &Vars.l.lock_file, NULL,0},
261 {"log file", P_STRING, P_LOCAL, &Vars.l.log_file, NULL,0},
262 @@ -464,6 +467,7 @@ FN_LOCAL_STRING(lp_hosts_deny, hosts_deny)
263 FN_LOCAL_STRING(lp_include, include)
264 FN_LOCAL_STRING(lp_include_from, include_from)
265 FN_LOCAL_STRING(lp_incoming_chmod, incoming_chmod)
266 +FN_LOCAL_STRING(lp_link_by_hash_dir, link_by_hash_dir)
267 FN_LOCAL_STRING(lp_lock_file, lock_file)
268 FN_LOCAL_STRING(lp_log_file, log_file)
269 FN_LOCAL_STRING(lp_log_format, log_format)
270 diff --git a/log.c b/log.c
273 @@ -683,23 +683,14 @@ static void log_formatted(enum logcode code, const char *format, const char *op,
274 if (protocol_version >= 30
275 && (iflags & ITEM_TRANSFER
276 || (always_checksum && S_ISREG(file->mode)))) {
278 const char *sum = iflags & ITEM_TRANSFER
279 ? sender_file_sum : F_SUM(file);
280 - c = buf2 + checksum_len*2;
282 - for (i = checksum_len; --i >= 0; ) {
286 - *--c = x1 <= 9 ? x1 + '0' : x1 + 'a' - 10;
287 - *--c = x2 <= 9 ? x2 + '0' : x2 + 'a' - 10;
289 + n = sum_as_hex(sum);
291 memset(buf2, ' ', checksum_len*2);
292 buf2[checksum_len*2] = '\0';
298 if (iflags & ITEM_DELETED) {
299 diff --git a/options.c b/options.c
302 @@ -159,6 +159,7 @@ char *backup_suffix = NULL;
304 char *partial_dir = NULL;
305 char *basis_dir[MAX_BASIS_DIRS+1];
306 +char *link_by_hash_dir = NULL;
307 char *config_file = NULL;
308 char *shell_cmd = NULL;
309 char *logfile_name = NULL;
310 @@ -208,7 +209,7 @@ static const char *debug_verbosity[] = {
311 /*2*/ "BIND,CMD,CONNECT,DEL,DELTASUM,DUP,FILTER,FLIST,ICONV",
312 /*3*/ "ACL,BACKUP,CONNECT2,DELTASUM2,DEL2,EXIT,FILTER2,FLIST2,FUZZY,GENR,OWN,RECV,SEND,TIME",
313 /*4*/ "CMD2,DELTASUM3,DEL3,EXIT2,FLIST3,ICONV2,OWN2,PROTO,TIME2",
314 - /*5*/ "CHDIR,DELTASUM4,FLIST4,FUZZY2,HASH,HLINK",
315 + /*5*/ "CHDIR,DELTASUM4,FLIST4,FUZZY2,HASH,HASHLINK,HLINK",
318 #define MAX_VERBOSITY ((int)(sizeof debug_verbosity / sizeof debug_verbosity[0]) - 1)
319 @@ -278,6 +279,7 @@ static struct output_struct debug_words[COUNT_DEBUG+1] = {
320 DEBUG_WORD(FUZZY, W_REC, "Debug fuzzy scoring (levels 1-2)"),
321 DEBUG_WORD(GENR, W_REC, "Debug generator functions"),
322 DEBUG_WORD(HASH, W_SND|W_REC, "Debug hashtable code"),
323 + DEBUG_WORD(HASHLINK, W_REC, "Debug hashlink code (levels 1-2)"),
324 DEBUG_WORD(HLINK, W_SND|W_REC, "Debug hard-link actions (levels 1-3)"),
325 DEBUG_WORD(ICONV, W_CLI|W_SRV, "Debug iconv character conversions (levels 1-2)"),
326 DEBUG_WORD(IO, W_CLI|W_SRV, "Debug I/O routines (levels 1-4)"),
327 @@ -762,6 +764,7 @@ void usage(enum logcode F)
328 rprintf(F," --compare-dest=DIR also compare destination files relative to DIR\n");
329 rprintf(F," --copy-dest=DIR ... and include copies of unchanged files\n");
330 rprintf(F," --link-dest=DIR hardlink to files in DIR when unchanged\n");
331 + rprintf(F," --link-by-hash=DIR create hardlinks by hash into DIR\n");
332 rprintf(F," -z, --compress compress file data during the transfer\n");
333 rprintf(F," --compress-level=NUM explicitly set compression level\n");
334 rprintf(F," --skip-compress=LIST skip compressing files with a suffix in LIST\n");
335 @@ -817,7 +820,7 @@ enum {OPT_VERSION = 1000, OPT_DAEMON, OPT_SENDER, OPT_EXCLUDE, OPT_EXCLUDE_FROM,
336 OPT_FILTER, OPT_COMPARE_DEST, OPT_COPY_DEST, OPT_LINK_DEST, OPT_HELP,
337 OPT_INCLUDE, OPT_INCLUDE_FROM, OPT_MODIFY_WINDOW, OPT_MIN_SIZE, OPT_CHMOD,
338 OPT_READ_BATCH, OPT_WRITE_BATCH, OPT_ONLY_WRITE_BATCH, OPT_MAX_SIZE,
339 - OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG,
340 + OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG, OPT_LINK_BY_HASH,
341 OPT_USERMAP, OPT_GROUPMAP, OPT_CHOWN, OPT_BWLIMIT,
342 OPT_SERVER, OPT_REFUSED_BASE = 9000};
344 @@ -961,6 +964,7 @@ static struct poptOption long_options[] = {
345 {"compare-dest", 0, POPT_ARG_STRING, 0, OPT_COMPARE_DEST, 0, 0 },
346 {"copy-dest", 0, POPT_ARG_STRING, 0, OPT_COPY_DEST, 0, 0 },
347 {"link-dest", 0, POPT_ARG_STRING, 0, OPT_LINK_DEST, 0, 0 },
348 + {"link-by-hash", 0, POPT_ARG_STRING, 0, OPT_LINK_BY_HASH, 0, 0},
349 {"fuzzy", 'y', POPT_ARG_NONE, 0, 'y', 0, 0 },
350 {"no-fuzzy", 0, POPT_ARG_VAL, &fuzzy_basis, 0, 0, 0 },
351 {"no-y", 0, POPT_ARG_VAL, &fuzzy_basis, 0, 0, 0 },
352 @@ -1308,6 +1312,9 @@ int parse_arguments(int *argc_p, const char ***argv_p)
353 iconv_opt = strdup(arg);
356 + if (*lp_link_by_hash_dir(module_id))
357 + set_refuse_options("link-by-hash");
359 /* TODO: Call poptReadDefaultConfig; handle errors. */
361 /* The context leaks in case of an error, but if there's a
362 @@ -1794,6 +1801,21 @@ int parse_arguments(int *argc_p, const char ***argv_p)
366 + case OPT_LINK_BY_HASH:
368 + arg = poptGetOptArg(pc);
369 + if (sanitize_paths)
370 + arg = sanitize_path(NULL, arg, NULL, 0, SP_DEFAULT);
371 + link_by_hash_dir = (char *)arg;
374 + snprintf(err_buf, sizeof err_buf,
375 + "hard links are not supported on this %s\n",
376 + am_server ? "server" : "client");
377 + rprintf(FERROR, "ERROR: %s", err_buf);
382 /* A large opt value means that set_refuse_options()
383 * turned this option off. */
384 @@ -2078,6 +2100,8 @@ int parse_arguments(int *argc_p, const char ***argv_p)
385 tmpdir = sanitize_path(NULL, tmpdir, NULL, 0, SP_DEFAULT);
387 backup_dir = sanitize_path(NULL, backup_dir, NULL, 0, SP_DEFAULT);
388 + if (link_by_hash_dir)
389 + link_by_hash_dir = sanitize_path(NULL, link_by_hash_dir, NULL, 0, SP_DEFAULT);
391 if (daemon_filter_list.head && !am_sender) {
392 filter_rule_list *elp = &daemon_filter_list;
393 @@ -2723,6 +2747,12 @@ void server_options(char **args, int *argc_p)
395 args[ac++] = "--inplace";
397 + if (link_by_hash_dir && am_sender) {
398 + args[ac++] = "--link-by-hash";
399 + args[ac++] = link_by_hash_dir;
400 + link_by_hash_dir = NULL; /* optimize sending-side checksums */
403 if (files_from && (!am_sender || filesfrom_host)) {
404 if (filesfrom_host) {
405 args[ac++] = "--files-from";
406 diff --git a/rsync.c b/rsync.c
409 @@ -49,6 +49,7 @@ extern int flist_eof;
410 extern int file_old_total;
411 extern int keep_dirlinks;
412 extern int make_backups;
413 +extern char *link_by_hash_dir;
414 extern struct file_list *cur_flist, *first_flist, *dir_flist;
415 extern struct chmod_mode_struct *daemon_chmod_modes;
417 @@ -679,6 +680,10 @@ int finish_transfer(const char *fname, const char *fnametmp,
420 /* The file was moved into place (not copied), so it's done. */
422 + if (link_by_hash_dir)
423 + link_by_hash(fname, fnametmp, file);
427 /* The file was copied, so tweak the perms of the copied file. If it
428 diff --git a/rsync.h b/rsync.h
431 @@ -1263,7 +1263,8 @@ extern short info_levels[], debug_levels[];
432 #define DEBUG_FUZZY (DEBUG_FLIST+1)
433 #define DEBUG_GENR (DEBUG_FUZZY+1)
434 #define DEBUG_HASH (DEBUG_GENR+1)
435 -#define DEBUG_HLINK (DEBUG_HASH+1)
436 +#define DEBUG_HASHLINK (DEBUG_HASH+1)
437 +#define DEBUG_HLINK (DEBUG_HASHLINK+1)
438 #define DEBUG_ICONV (DEBUG_HLINK+1)
439 #define DEBUG_IO (DEBUG_ICONV+1)
440 #define DEBUG_OWN (DEBUG_IO+1)
441 diff --git a/rsync.yo b/rsync.yo
444 @@ -416,6 +416,7 @@ to the detailed description below for a complete description. verb(
445 --compare-dest=DIR also compare received files relative to DIR
446 --copy-dest=DIR ... and include copies of unchanged files
447 --link-dest=DIR hardlink to files in DIR when unchanged
448 + --link-by-hash=DIR create hardlinks by hash into DIR
449 -z, --compress compress file data during the transfer
450 --compress-level=NUM explicitly set compression level
451 --skip-compress=LIST skip compressing files with suffix in LIST
452 @@ -1849,6 +1850,48 @@ bf(--link-dest) from working properly for a non-super-user when bf(-o) was
453 specified (or implied by bf(-a)). You can work-around this bug by avoiding
454 the bf(-o) option when sending to an old rsync.
456 +dit(bf(--link-by-hash=DIR)) This option hard links the destination files into
457 +em(DIR), a link farm arranged by MD5 file hash. The result is that the system
458 +will only store (usually) one copy of the unique contents of each file,
459 +regardless of the file's name (it will use extra files if the links overflow
460 +the available maximum).
462 +This patch does not take into account file permissions, extended attributes,
463 +or ACLs when linking things together, so you should only use this if you
464 +don't care about preserving those extra file attributes (or if they are
465 +always the same for identical files).
467 +The DIR is relative to the destination directory, so either specify a full
468 +path to the hash hierarchy, or specify a relative path that puts the links
469 +outside the destination (e.g. "../links").
471 +Keep in mind that the hierarchy is never pruned, so if you need to reclaim
472 +space, you should remove any files that have just one link (since they are not
473 +linked into any destination dirs anymore):
475 + find $DIR -links 1 -delete
477 +The link farm's directory hierarchy is determined by the file's (32-char) MD5
478 +hash and the file-length. The hash is split up into directory shards. For
479 +example, if a file is 54321 bytes long, it could be stored like this:
481 + $DIR/123/456/789/01234567890123456789012.54321.0
483 +Note that the directory layout in this patch was modified for version 3.1.0,
484 +so anyone using an older version of this patch should move their existing
485 +link hierarchy out of the way and then use the newer rsync to copy the saved
486 +hierarchy into its new layout. Assuming that no files have overflowed their
487 +link limits, this would work:
490 + rsync -aiv --link-by-hash=$DIR $DIR.old/ $DIR.tmp/
494 +If some of your files are at their link limit, you'd be better of using a
495 +script to calculate the md5 sum of each file in the hierarchy and move it
496 +to its new location.
498 dit(bf(-z, --compress)) With this option, rsync compresses the file data
499 as it is sent to the destination machine, which reduces the amount of data
500 being transmitted -- something that is useful over a slow connection.
501 diff --git a/rsyncd.conf.yo b/rsyncd.conf.yo
504 @@ -283,6 +283,21 @@ message telling them to try later. The default is 0, which means no limit.
505 A negative value disables the module.
506 See also the "lock file" parameter.
508 +dit(bf(link by hash dir)) When the "link by hash dir" parameter is set to a
509 +non-empty string, received files will be hard linked into em(DIR), a link farm
510 +arranged by MD5 file hash. See the bf(--link-by-hash) option for a full
513 +The em(DIR) must be accessible inside any chroot restrictions for the module,
514 +but can exist outside the transfer location if there is an inside-the-chroot
515 +path to the module (see "use chroot"). Note that a user-specified option does
516 +not allow this outside-the-transfer-area placement.
518 +If this parameter is set, it will disable the bf(--link-by-hash) command-line
519 +option for copies into the module.
521 +The default is for this parameter to be unset.
523 dit(bf(log file)) When the "log file" parameter is set to a non-empty
524 string, the rsync daemon will log messages to the indicated file rather
525 than using syslog. This is particularly useful on systems (such as AIX)