The sum_as_hex() function is now in the main code.
[rsync-patches.git] / link-by-hash.diff
1 Jason M. Felice wrote:
2
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
6 file's name.
7
8 To use this patch, run these commands for a successful build:
9
10     patch -p1 <patches/link-by-hash.diff
11     ./prepare-source
12     ./configure
13     make
14
15 based-on: 0488a14b9930bf91719ac0f1d1c0c8770ca10646
16 diff --git a/Makefile.in b/Makefile.in
17 --- a/Makefile.in
18 +++ 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 util2.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
29 --- a/checksum.c
30 +++ b/checksum.c
31 @@ -21,8 +21,11 @@
32  
33  #include "rsync.h"
34  
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];
40  
41  /*
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)
44  }
45  
46  static int32 sumresidue;
47 -static md_context md;
48 +static md_context md, md2;
49  
50  void sum_init(int seed)
51  {
52 @@ -164,6 +167,8 @@ void sum_init(int seed)
53                 sumresidue = 0;
54                 SIVAL(s, 0, seed);
55                 sum_update(s, 4);
56 +               if (link_by_hash_dir)
57 +                       md5_begin(&md2);
58         }
59  }
60  
61 @@ -182,6 +187,9 @@ void sum_update(const char *p, int32 len)
62                 return;
63         }
64  
65 +       if (link_by_hash_dir)
66 +               md5_update(&md2, (uchar *)p, len);
67 +
68         if (len + sumresidue < CSUM_CHUNK) {
69                 memcpy(md.buffer + sumresidue, p, len);
70                 sumresidue += len;
71 @@ -214,6 +222,9 @@ int sum_end(char *sum)
72                 return MD5_DIGEST_LEN;
73         }
74  
75 +       if (link_by_hash_dir)
76 +               md5_result(&md2, (uchar *)link_by_hash_extra_sum);
77 +
78         if (sumresidue || protocol_version >= 27)
79                 mdfour_update(&md, (uchar *)md.buffer, sumresidue);
80  
81 diff --git a/clientserver.c b/clientserver.c
82 --- a/clientserver.c
83 +++ b/clientserver.c
84 @@ -50,6 +50,7 @@ extern int logfile_format_has_i;
85  extern int logfile_format_has_o_or_i;
86  extern char *bind_address;
87  extern char *config_file;
88 +extern char *link_by_hash_dir;
89  extern char *logfile_format;
90  extern char *files_from;
91  extern char *tmpdir;
92 @@ -548,6 +549,9 @@ static int rsync_module(int f_in, int f_out, int i, const char *addr, const char
93                 return -1;
94         }
95  
96 +       if (*lp_link_by_hash_dir(i))
97 +               link_by_hash_dir = lp_link_by_hash_dir(i);
98 +
99         if (am_daemon && am_server) {
100                 rprintf(FLOG, "rsync allowed access on module %s from %s (%s)\n",
101                         name, host, addr);
102 diff --git a/compat.c b/compat.c
103 --- a/compat.c
104 +++ b/compat.c
105 @@ -55,6 +55,7 @@ extern char *partial_dir;
106  extern char *dest_option;
107  extern char *files_from;
108  extern char *filesfrom_host;
109 +extern char *link_by_hash_dir;
110  extern filter_rule_list filter_list;
111  extern int need_unsorted_flist;
112  #ifdef ICONV_OPTION
113 diff --git a/hashlink.c b/hashlink.c
114 new file mode 100644
115 --- /dev/null
116 +++ b/hashlink.c
117 @@ -0,0 +1,92 @@
118 +/*
119 +   Copyright (C) Cronosys, LLC 2004
120 +
121 +   This program is free software; you can redistribute it and/or modify
122 +   it under the terms of the GNU General Public License as published by
123 +   the Free Software Foundation; either version 2 of the License, or
124 +   (at your option) any later version.
125 +
126 +   This program is distributed in the hope that it will be useful,
127 +   but WITHOUT ANY WARRANTY; without even the implied warranty of
128 +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
129 +   GNU General Public License for more details.
130 +
131 +   You should have received a copy of the GNU General Public License
132 +   along with this program; if not, write to the Free Software
133 +   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
134 +*/
135 +
136 +/* This file contains code used by the --link-by-hash option. */
137 +
138 +#include "rsync.h"
139 +#include "inums.h"
140 +
141 +extern int protocol_version;
142 +extern char *link_by_hash_dir;
143 +extern char sender_file_sum[MAX_DIGEST_LEN];
144 +
145 +char link_by_hash_extra_sum[MAX_DIGEST_LEN]; /* Only used when md4 sums are in the transfer */
146 +
147 +#ifdef HAVE_LINK
148 +
149 +/* This function is always called after a file is received, so the
150 + * sender_file_sum buffer has whatever the last checksum was for the
151 + * transferred file. */
152 +void link_by_hash(const char *fname, const char *fnametmp, struct file_struct *file)
153 +{
154 +       STRUCT_STAT st;
155 +       char *hashname, *last_slash, *num_str;
156 +       const char *hex;
157 +       int num = 0;
158 +
159 +       /* We don't bother to hard-link 0-length files. */
160 +       if (F_LENGTH(file) == 0)
161 +               return;
162 +
163 +       hex = sum_as_hex(protocol_version >= 30 ? sender_file_sum : link_by_hash_extra_sum);
164 +       if (asprintf(&hashname, "%s/%.3s/%.3s/%.3s/%s.%s.000000",
165 +                    link_by_hash_dir, hex, hex+3, hex+6, hex+9, big_num(F_LENGTH(file))) < 0)
166 +       {
167 +               out_of_memory("make_hash_name");
168 +       }
169 +
170 +       last_slash = strrchr(hashname, '/');
171 +       num_str = strrchr(last_slash, '.') + 1;
172 +
173 +       while (1) {
174 +               if (num >= 999999) { /* Surely we'll never reach this... */
175 +                       if (DEBUG_GTE(HASHLINK, 1))
176 +                               rprintf(FINFO, "link-by-hash: giving up after \"%s\".\n", hashname);
177 +                       goto cleanup;
178 +               }
179 +               if (num > 0 && DEBUG_GTE(HASHLINK, 1))
180 +                       rprintf(FINFO, "link-by-hash: max link count exceeded, starting new file \"%s\".\n", hashname);
181 +
182 +               snprintf(num_str, 7, "%d", num++);
183 +               if (do_stat(hashname, &st) < 0)
184 +                       break;
185 +
186 +               if (do_link(hashname, fnametmp) < 0) {
187 +                       if (errno == EMLINK)
188 +                               continue;
189 +                       rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", hashname, full_fname(fname));
190 +               } else {
191 +                       if (DEBUG_GTE(HASHLINK, 2))
192 +                               rprintf(FINFO, "link-by-hash (existing): \"%s\" -> %s\n", hashname, full_fname(fname));
193 +                       robust_rename(fnametmp, fname, NULL, 0644);
194 +               }
195 +
196 +               goto cleanup;
197 +       }
198 +
199 +       if (DEBUG_GTE(HASHLINK, 2))
200 +               rprintf(FINFO, "link-by-hash (new): %s -> \"%s\"\n", full_fname(fname), hashname);
201 +
202 +       if (do_link(fname, hashname) < 0
203 +        && (errno != ENOENT || make_path(hashname, MKP_DROP_NAME) < 0 || do_link(fname, hashname) < 0))
204 +               rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", full_fname(fname), hashname);
205 +
206 +  cleanup:
207 +       free(hashname);
208 +}
209 +#endif
210 diff --git a/loadparm.c b/loadparm.c
211 --- a/loadparm.c
212 +++ b/loadparm.c
213 @@ -119,6 +119,7 @@ typedef struct {
214         char *include;
215         char *include_from;
216         char *incoming_chmod;
217 +       char *link_by_hash_dir;
218         char *lock_file;
219         char *log_file;
220         char *log_format;
221 @@ -195,6 +196,7 @@ static const all_vars Defaults = {
222   /* include; */                        NULL,
223   /* include_from; */           NULL,
224   /* incoming_chmod; */         NULL,
225 + /* link_by_hash_dir; */       NULL,
226   /* lock_file; */              DEFAULT_LOCK_FILE,
227   /* log_file; */               NULL,
228   /* log_format; */             "%o %h [%a] %m (%u) %f %l",
229 @@ -336,6 +338,7 @@ static struct parm_struct parm_table[] =
230   {"include from",      P_STRING, P_LOCAL, &Vars.l.include_from,        NULL,0},
231   {"include",           P_STRING, P_LOCAL, &Vars.l.include,             NULL,0},
232   {"incoming chmod",    P_STRING, P_LOCAL, &Vars.l.incoming_chmod,      NULL,0},
233 + {"link by hash dir",  P_STRING, P_LOCAL, &Vars.l.link_by_hash_dir,    NULL,0},
234   {"list",              P_BOOL,   P_LOCAL, &Vars.l.list,                NULL,0},
235   {"lock file",         P_STRING, P_LOCAL, &Vars.l.lock_file,           NULL,0},
236   {"log file",          P_STRING, P_LOCAL, &Vars.l.log_file,            NULL,0},
237 @@ -464,6 +467,7 @@ FN_LOCAL_STRING(lp_hosts_deny, hosts_deny)
238  FN_LOCAL_STRING(lp_include, include)
239  FN_LOCAL_STRING(lp_include_from, include_from)
240  FN_LOCAL_STRING(lp_incoming_chmod, incoming_chmod)
241 +FN_LOCAL_STRING(lp_link_by_hash_dir, link_by_hash_dir)
242  FN_LOCAL_STRING(lp_lock_file, lock_file)
243  FN_LOCAL_STRING(lp_log_file, log_file)
244  FN_LOCAL_STRING(lp_log_format, log_format)
245 diff --git a/options.c b/options.c
246 --- a/options.c
247 +++ b/options.c
248 @@ -158,6 +158,7 @@ char *backup_suffix = NULL;
249  char *tmpdir = NULL;
250  char *partial_dir = NULL;
251  char *basis_dir[MAX_BASIS_DIRS+1];
252 +char *link_by_hash_dir = NULL;
253  char *config_file = NULL;
254  char *shell_cmd = NULL;
255  char *logfile_name = NULL;
256 @@ -207,7 +208,7 @@ static const char *debug_verbosity[] = {
257         /*2*/ "BIND,CMD,CONNECT,DEL,DELTASUM,DUP,FILTER,FLIST,ICONV",
258         /*3*/ "ACL,BACKUP,CONNECT2,DELTASUM2,DEL2,EXIT,FILTER2,FLIST2,FUZZY,GENR,OWN,RECV,SEND,TIME",
259         /*4*/ "CMD2,DELTASUM3,DEL3,EXIT2,FLIST3,ICONV2,OWN2,PROTO,TIME2",
260 -       /*5*/ "CHDIR,DELTASUM4,FLIST4,FUZZY2,HASH,HLINK",
261 +       /*5*/ "CHDIR,DELTASUM4,FLIST4,FUZZY2,HASH,HASHLINK,HLINK",
262  };
263  
264  #define MAX_VERBOSITY ((int)(sizeof debug_verbosity / sizeof debug_verbosity[0]) - 1)
265 @@ -277,6 +278,7 @@ static struct output_struct debug_words[COUNT_DEBUG+1] = {
266         DEBUG_WORD(FUZZY, W_REC, "Debug fuzzy scoring (levels 1-2)"),
267         DEBUG_WORD(GENR, W_REC, "Debug generator functions"),
268         DEBUG_WORD(HASH, W_SND|W_REC, "Debug hashtable code"),
269 +       DEBUG_WORD(HASHLINK, W_REC, "Debug hashlink code (levels 1-2)"),
270         DEBUG_WORD(HLINK, W_SND|W_REC, "Debug hard-link actions (levels 1-3)"),
271         DEBUG_WORD(ICONV, W_CLI|W_SRV, "Debug iconv character conversions (levels 1-2)"),
272         DEBUG_WORD(IO, W_CLI|W_SRV, "Debug I/O routines (levels 1-4)"),
273 @@ -761,6 +763,7 @@ void usage(enum logcode F)
274    rprintf(F,"     --compare-dest=DIR      also compare destination files relative to DIR\n");
275    rprintf(F,"     --copy-dest=DIR         ... and include copies of unchanged files\n");
276    rprintf(F,"     --link-dest=DIR         hardlink to files in DIR when unchanged\n");
277 +  rprintf(F,"     --link-by-hash=DIR      create hardlinks by hash into DIR\n");
278    rprintf(F," -z, --compress              compress file data during the transfer\n");
279    rprintf(F,"     --compress-level=NUM    explicitly set compression level\n");
280    rprintf(F,"     --skip-compress=LIST    skip compressing files with a suffix in LIST\n");
281 @@ -817,7 +820,7 @@ enum {OPT_VERSION = 1000, OPT_DAEMON, OPT_SENDER, OPT_EXCLUDE, OPT_EXCLUDE_FROM,
282        OPT_FILTER, OPT_COMPARE_DEST, OPT_COPY_DEST, OPT_LINK_DEST, OPT_HELP,
283        OPT_INCLUDE, OPT_INCLUDE_FROM, OPT_MODIFY_WINDOW, OPT_MIN_SIZE, OPT_CHMOD,
284        OPT_READ_BATCH, OPT_WRITE_BATCH, OPT_ONLY_WRITE_BATCH, OPT_MAX_SIZE,
285 -      OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG,
286 +      OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG, OPT_LINK_BY_HASH,
287        OPT_USERMAP, OPT_GROUPMAP, OPT_CHOWN, OPT_BWLIMIT,
288        OPT_SERVER, OPT_REFUSED_BASE = 9000};
289  
290 @@ -961,6 +964,7 @@ static struct poptOption long_options[] = {
291    {"compare-dest",     0,  POPT_ARG_STRING, 0, OPT_COMPARE_DEST, 0, 0 },
292    {"copy-dest",        0,  POPT_ARG_STRING, 0, OPT_COPY_DEST, 0, 0 },
293    {"link-dest",        0,  POPT_ARG_STRING, 0, OPT_LINK_DEST, 0, 0 },
294 +  {"link-by-hash",     0,  POPT_ARG_STRING, 0, OPT_LINK_BY_HASH, 0, 0},
295    {"fuzzy",           'y', POPT_ARG_NONE,   0, 'y', 0, 0 },
296    {"no-fuzzy",         0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
297    {"no-y",             0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
298 @@ -1308,6 +1312,9 @@ int parse_arguments(int *argc_p, const char ***argv_p)
299                 iconv_opt = strdup(arg);
300  #endif
301  
302 +       if (*lp_link_by_hash_dir(module_id))
303 +               set_refuse_options("link-by-hash");
304 +
305         /* TODO: Call poptReadDefaultConfig; handle errors. */
306  
307         /* The context leaks in case of an error, but if there's a
308 @@ -1794,6 +1801,21 @@ int parse_arguments(int *argc_p, const char ***argv_p)
309                         return 0;
310  #endif
311  
312 +                case OPT_LINK_BY_HASH:
313 +#ifdef HAVE_LINK
314 +                       arg = poptGetOptArg(pc);
315 +                       if (sanitize_paths)
316 +                               arg = sanitize_path(NULL, arg, NULL, 0, SP_DEFAULT);
317 +                       link_by_hash_dir = (char *)arg;
318 +                       break;
319 +#else
320 +                       snprintf(err_buf, sizeof err_buf,
321 +                                "hard links are not supported on this %s\n",
322 +                                am_server ? "server" : "client");
323 +                       rprintf(FERROR, "ERROR: %s", err_buf);
324 +                       return 0;
325 +#endif
326 +
327                 default:
328                         /* A large opt value means that set_refuse_options()
329                          * turned this option off. */
330 @@ -2069,6 +2091,8 @@ int parse_arguments(int *argc_p, const char ***argv_p)
331                         tmpdir = sanitize_path(NULL, tmpdir, NULL, 0, SP_DEFAULT);
332                 if (backup_dir)
333                         backup_dir = sanitize_path(NULL, backup_dir, NULL, 0, SP_DEFAULT);
334 +               if (link_by_hash_dir)
335 +                       link_by_hash_dir = sanitize_path(NULL, link_by_hash_dir, NULL, 0, SP_DEFAULT);
336         }
337         if (daemon_filter_list.head && !am_sender) {
338                 filter_rule_list *elp = &daemon_filter_list;
339 @@ -2714,6 +2738,12 @@ void server_options(char **args, int *argc_p)
340         } else if (inplace)
341                 args[ac++] = "--inplace";
342  
343 +       if (link_by_hash_dir && am_sender) {
344 +               args[ac++] = "--link-by-hash";
345 +               args[ac++] = link_by_hash_dir;
346 +               link_by_hash_dir = NULL; /* optimize sending-side checksums */
347 +       }
348 +
349         if (files_from && (!am_sender || filesfrom_host)) {
350                 if (filesfrom_host) {
351                         args[ac++] = "--files-from";
352 diff --git a/rsync.c b/rsync.c
353 --- a/rsync.c
354 +++ b/rsync.c
355 @@ -49,6 +49,7 @@ extern int flist_eof;
356  extern int file_old_total;
357  extern int keep_dirlinks;
358  extern int make_backups;
359 +extern char *link_by_hash_dir;
360  extern struct file_list *cur_flist, *first_flist, *dir_flist;
361  extern struct chmod_mode_struct *daemon_chmod_modes;
362  #ifdef ICONV_OPTION
363 @@ -679,6 +680,10 @@ int finish_transfer(const char *fname, const char *fnametmp,
364         }
365         if (ret == 0) {
366                 /* The file was moved into place (not copied), so it's done. */
367 +#ifdef HAVE_LINK
368 +               if (link_by_hash_dir)
369 +                       link_by_hash(fname, fnametmp, file);
370 +#endif
371                 return 1;
372         }
373         /* The file was copied, so tweak the perms of the copied file.  If it
374 diff --git a/rsync.h b/rsync.h
375 --- a/rsync.h
376 +++ b/rsync.h
377 @@ -1263,7 +1263,8 @@ extern short info_levels[], debug_levels[];
378  #define DEBUG_FUZZY (DEBUG_FLIST+1)
379  #define DEBUG_GENR (DEBUG_FUZZY+1)
380  #define DEBUG_HASH (DEBUG_GENR+1)
381 -#define DEBUG_HLINK (DEBUG_HASH+1)
382 +#define DEBUG_HASHLINK (DEBUG_HASH+1)
383 +#define DEBUG_HLINK (DEBUG_HASHLINK+1)
384  #define DEBUG_ICONV (DEBUG_HLINK+1)
385  #define DEBUG_IO (DEBUG_ICONV+1)
386  #define DEBUG_OWN (DEBUG_IO+1)
387 diff --git a/rsync.yo b/rsync.yo
388 --- a/rsync.yo
389 +++ b/rsync.yo
390 @@ -416,6 +416,7 @@ to the detailed description below for a complete description.  verb(
391       --compare-dest=DIR      also compare received files relative to DIR
392       --copy-dest=DIR         ... and include copies of unchanged files
393       --link-dest=DIR         hardlink to files in DIR when unchanged
394 +     --link-by-hash=DIR      create hardlinks by hash into DIR
395   -z, --compress              compress file data during the transfer
396       --compress-level=NUM    explicitly set compression level
397       --skip-compress=LIST    skip compressing files with suffix in LIST
398 @@ -1849,6 +1850,48 @@ bf(--link-dest) from working properly for a non-super-user when bf(-o) was
399  specified (or implied by bf(-a)).  You can work-around this bug by avoiding
400  the bf(-o) option when sending to an old rsync.
401  
402 +dit(bf(--link-by-hash=DIR)) This option hard links the destination files into
403 +em(DIR), a link farm arranged by MD5 file hash. The result is that the system
404 +will only store (usually) one copy of the unique contents of each file,
405 +regardless of the file's name (it will use extra files if the links overflow
406 +the available maximum).
407 +
408 +This patch does not take into account file permissions, extended attributes,
409 +or ACLs when linking things together, so you should only use this if you
410 +don't care about preserving those extra file attributes (or if they are
411 +always the same for identical files).
412 +
413 +The DIR is relative to the destination directory, so either specify a full
414 +path to the hash hierarchy, or specify a relative path that puts the links
415 +outside the destination (e.g. "../links").
416 +
417 +Keep in mind that the hierarchy is never pruned, so if you need to reclaim
418 +space, you should remove any files that have just one link (since they are not
419 +linked into any destination dirs anymore):
420 +
421 +    find $DIR -links 1 -delete
422 +
423 +The link farm's directory hierarchy is determined by the file's (32-char) MD5
424 +hash and the file-length.  The hash is split up into directory shards.  For
425 +example, if a file is 54321 bytes long, it could be stored like this:
426 +
427 +    $DIR/123/456/789/01234567890123456789012.54321.0
428 +
429 +Note that the directory layout in this patch was modified for version 3.1.0,
430 +so anyone using an older version of this patch should move their existing
431 +link hierarchy out of the way and then use the newer rsync to copy the saved
432 +hierarchy into its new layout.  Assuming that no files have overflowed their
433 +link limits, this would work:
434 +
435 +    mv $DIR $DIR.old
436 +    rsync -aiv --link-by-hash=$DIR $DIR.old/ $DIR.tmp/
437 +    rm -rf $DIR.tmp
438 +    rm -rf $DIR.old
439 +
440 +If some of your files are at their link limit, you'd be better of using a
441 +script to calculate the md5 sum of each file in the hierarchy and move it
442 +to its new location.
443 +
444  dit(bf(-z, --compress)) With this option, rsync compresses the file data
445  as it is sent to the destination machine, which reduces the amount of data
446  being transmitted -- something that is useful over a slow connection.
447 diff --git a/rsyncd.conf.yo b/rsyncd.conf.yo
448 --- a/rsyncd.conf.yo
449 +++ b/rsyncd.conf.yo
450 @@ -283,6 +283,21 @@ message telling them to try later.  The default is 0, which means no limit.
451  A negative value disables the module.
452  See also the "lock file" parameter.
453  
454 +dit(bf(link by hash dir)) When the "link by hash dir" parameter is set to a
455 +non-empty string, received files will be hard linked into em(DIR), a link farm
456 +arranged by MD5 file hash. See the bf(--link-by-hash) option for a full
457 +explanation.
458 +
459 +The em(DIR) must be accessible inside any chroot restrictions for the module,
460 +but can exist outside the transfer location if there is an inside-the-chroot
461 +path to the module (see "use chroot").  Note that a user-specified option does
462 +not allow this outside-the-transfer-area placement.
463 +
464 +If this parameter is set, it will disable the bf(--link-by-hash) command-line
465 +option for copies into the module.
466 +
467 +The default is for this parameter to be unset.
468 +
469  dit(bf(log file)) When the "log file" parameter is set to a non-empty
470  string, the rsync daemon will log messages to the indicated file rather
471  than using syslog. This is particularly useful on systems (such as AIX)