The patches for 3.2.0pre1.
[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: c528f8d5c8aa7b16b20cda72a9f4119699890c28
16 diff --git a/Makefile.in b/Makefile.in
17 --- a/Makefile.in
18 +++ b/Makefile.in
19 @@ -45,7 +45,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 @@ -36,6 +36,8 @@ extern int whole_file;
32  extern int checksum_seed;
33  extern int protocol_version;
34  extern int proper_seed_order;
35 +extern char *link_by_hash_dir;
36 +extern char link_by_hash_extra_sum[MAX_DIGEST_LEN];
37  extern const char *checksum_choice;
38  
39  struct name_num_obj valid_checksums = {
40 @@ -385,7 +387,7 @@ static union {
41         MD4_CTX m4;
42  #endif
43         MD5_CTX m5;
44 -} ctx;
45 +} ctx, ctx2;
46  #ifdef SUPPORT_XXHASH
47  static XXH64_state_t* xxh64_state;
48  #endif
49 @@ -409,6 +411,8 @@ void sum_init(int csum_type, int seed)
50  #endif
51           case CSUM_MD5:
52                 MD5_Init(&ctx.m5);
53 +               if (link_by_hash_dir)
54 +                       MD5_Init(&ctx2.m5);
55                 break;
56           case CSUM_MD4:
57  #ifdef USE_OPENSSL
58 @@ -451,6 +455,8 @@ void sum_update(const char *p, int32 len)
59  #endif
60           case CSUM_MD5:
61                 MD5_Update(&ctx.m5, (uchar *)p, len);
62 +               if (link_by_hash_dir)
63 +                       MD5_Update(&ctx2.m5, (uchar *)p, len);
64                 break;
65           case CSUM_MD4:
66  #ifdef USE_OPENSSL
67 @@ -505,6 +511,8 @@ int sum_end(char *sum)
68  #endif
69           case CSUM_MD5:
70                 MD5_Final((uchar *)sum, &ctx.m5);
71 +               if (link_by_hash_dir)
72 +                       MD5_Final((uchar *)link_by_hash_extra_sum, &ctx2.m5);
73                 break;
74           case CSUM_MD4:
75  #ifdef USE_OPENSSL
76 diff --git a/clientserver.c b/clientserver.c
77 --- a/clientserver.c
78 +++ b/clientserver.c
79 @@ -51,6 +51,7 @@ extern int logfile_format_has_i;
80  extern int logfile_format_has_o_or_i;
81  extern char *bind_address;
82  extern char *config_file;
83 +extern char *link_by_hash_dir;
84  extern char *logfile_format;
85  extern char *files_from;
86  extern char *tmpdir;
87 @@ -631,6 +632,9 @@ static int rsync_module(int f_in, int f_out, int i, const char *addr, const char
88                 return -1;
89         }
90  
91 +       if (*lp_link_by_hash_dir(i))
92 +               link_by_hash_dir = lp_link_by_hash_dir(i);
93 +
94         if (am_daemon > 0) {
95                 rprintf(FLOG, "rsync allowed access on module %s from %s (%s)\n",
96                         name, host, addr);
97 diff --git a/hashlink.c b/hashlink.c
98 new file mode 100644
99 --- /dev/null
100 +++ b/hashlink.c
101 @@ -0,0 +1,92 @@
102 +/*
103 +   Copyright (C) Cronosys, LLC 2004
104 +
105 +   This program is free software; you can redistribute it and/or modify
106 +   it under the terms of the GNU General Public License as published by
107 +   the Free Software Foundation; either version 2 of the License, or
108 +   (at your option) any later version.
109 +
110 +   This program is distributed in the hope that it will be useful,
111 +   but WITHOUT ANY WARRANTY; without even the implied warranty of
112 +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
113 +   GNU General Public License for more details.
114 +
115 +   You should have received a copy of the GNU General Public License
116 +   along with this program; if not, write to the Free Software
117 +   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
118 +*/
119 +
120 +/* This file contains code used by the --link-by-hash option. */
121 +
122 +#include "rsync.h"
123 +#include "inums.h"
124 +
125 +extern int protocol_version;
126 +extern char *link_by_hash_dir;
127 +extern char sender_file_sum[MAX_DIGEST_LEN];
128 +
129 +char link_by_hash_extra_sum[MAX_DIGEST_LEN]; /* Only used when md4 sums are in the transfer */
130 +
131 +#ifdef HAVE_LINK
132 +
133 +/* This function is always called after a file is received, so the
134 + * sender_file_sum buffer has whatever the last checksum was for the
135 + * transferred file. */
136 +void link_by_hash(const char *fname, const char *fnametmp, struct file_struct *file)
137 +{
138 +       STRUCT_STAT st;
139 +       char *hashname, *last_slash, *num_str;
140 +       const char *hex;
141 +       int num = 0;
142 +
143 +       /* We don't bother to hard-link 0-length files. */
144 +       if (F_LENGTH(file) == 0)
145 +               return;
146 +
147 +       hex = sum_as_hex(5, protocol_version >= 30 ? sender_file_sum : link_by_hash_extra_sum, 0);
148 +       if (asprintf(&hashname, "%s/%.3s/%.3s/%.3s/%s.%s.000000",
149 +                    link_by_hash_dir, hex, hex+3, hex+6, hex+9, big_num(F_LENGTH(file))) < 0)
150 +       {
151 +               out_of_memory("make_hash_name");
152 +       }
153 +
154 +       last_slash = strrchr(hashname, '/');
155 +       num_str = strrchr(last_slash, '.') + 1;
156 +
157 +       while (1) {
158 +               if (num >= 999999) { /* Surely we'll never reach this... */
159 +                       if (DEBUG_GTE(HASHLINK, 1))
160 +                               rprintf(FINFO, "link-by-hash: giving up after \"%s\".\n", hashname);
161 +                       goto cleanup;
162 +               }
163 +               if (num > 0 && DEBUG_GTE(HASHLINK, 1))
164 +                       rprintf(FINFO, "link-by-hash: max link count exceeded, starting new file \"%s\".\n", hashname);
165 +
166 +               snprintf(num_str, 7, "%d", num++);
167 +               if (do_stat(hashname, &st) < 0)
168 +                       break;
169 +
170 +               if (do_link(hashname, fnametmp) < 0) {
171 +                       if (errno == EMLINK)
172 +                               continue;
173 +                       rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", hashname, full_fname(fname));
174 +               } else {
175 +                       if (DEBUG_GTE(HASHLINK, 2))
176 +                               rprintf(FINFO, "link-by-hash (existing): \"%s\" -> %s\n", hashname, full_fname(fname));
177 +                       robust_rename(fnametmp, fname, NULL, 0644);
178 +               }
179 +
180 +               goto cleanup;
181 +       }
182 +
183 +       if (DEBUG_GTE(HASHLINK, 2))
184 +               rprintf(FINFO, "link-by-hash (new): %s -> \"%s\"\n", full_fname(fname), hashname);
185 +
186 +       if (do_link(fname, hashname) < 0
187 +        && (errno != ENOENT || make_path(hashname, MKP_DROP_NAME) < 0 || do_link(fname, hashname) < 0))
188 +               rsyserr(FERROR, errno, "link \"%s\" -> \"%s\"", full_fname(fname), hashname);
189 +
190 +  cleanup:
191 +       free(hashname);
192 +}
193 +#endif
194 diff --git a/loadparm.c b/loadparm.c
195 --- a/loadparm.c
196 +++ b/loadparm.c
197 @@ -134,6 +134,7 @@ typedef struct {
198         char *include;
199         char *include_from;
200         char *incoming_chmod;
201 +       char *link_by_hash_dir;
202         char *lock_file;
203         char *log_file;
204         char *log_format;
205 @@ -163,6 +164,7 @@ typedef struct {
206         BOOL include_EXP;
207         BOOL include_from_EXP;
208         BOOL incoming_chmod_EXP;
209 +       BOOL link_by_hash_dir_EXP;
210         BOOL lock_file_EXP;
211         BOOL log_file_EXP;
212         BOOL log_format_EXP;
213 @@ -252,6 +254,7 @@ static const all_vars Defaults = {
214   /* include; */                        NULL,
215   /* include_from; */           NULL,
216   /* incoming_chmod; */         NULL,
217 + /* link_by_hash_dir; */       NULL,
218   /* lock_file; */              DEFAULT_LOCK_FILE,
219   /* log_file; */               NULL,
220   /* log_format; */             "%o %h [%a] %m (%u) %f %l",
221 @@ -280,6 +283,7 @@ static const all_vars Defaults = {
222   /* include_EXP; */            False,
223   /* include_from_EXP; */       False,
224   /* incoming_chmod_EXP; */     False,
225 + /* link_by_hash_dir_EXP; */   False,
226   /* lock_file_EXP; */          False,
227   /* log_file_EXP; */           False,
228   /* log_format_EXP; */         False,
229 @@ -427,6 +431,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 @@ -565,6 +570,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 @@ -164,6 +164,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 @@ -212,7 +213,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 @@ -282,6 +283,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 @@ -735,7 +737,7 @@ enum {OPT_SERVER = 1000, OPT_DAEMON, OPT_SENDER, OPT_EXCLUDE, OPT_EXCLUDE_FROM,
274        OPT_FILTER, OPT_COMPARE_DEST, OPT_COPY_DEST, OPT_LINK_DEST, OPT_HELP,
275        OPT_INCLUDE, OPT_INCLUDE_FROM, OPT_MODIFY_WINDOW, OPT_MIN_SIZE, OPT_CHMOD,
276        OPT_READ_BATCH, OPT_WRITE_BATCH, OPT_ONLY_WRITE_BATCH, OPT_MAX_SIZE,
277 -      OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG,
278 +      OPT_NO_D, OPT_APPEND, OPT_NO_ICONV, OPT_INFO, OPT_DEBUG, OPT_LINK_BY_HASH,
279        OPT_USERMAP, OPT_GROUPMAP, OPT_CHOWN, OPT_BWLIMIT,
280        OPT_OLD_COMPRESS, OPT_NEW_COMPRESS, OPT_NO_COMPRESS,
281        OPT_REFUSED_BASE = 9000};
282 @@ -890,6 +892,7 @@ static struct poptOption long_options[] = {
283    {"compare-dest",     0,  POPT_ARG_STRING, 0, OPT_COMPARE_DEST, 0, 0 },
284    {"copy-dest",        0,  POPT_ARG_STRING, 0, OPT_COPY_DEST, 0, 0 },
285    {"link-dest",        0,  POPT_ARG_STRING, 0, OPT_LINK_DEST, 0, 0 },
286 +  {"link-by-hash",     0,  POPT_ARG_STRING, 0, OPT_LINK_BY_HASH, 0, 0},
287    {"fuzzy",           'y', POPT_ARG_NONE,   0, 'y', 0, 0 },
288    {"no-fuzzy",         0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
289    {"no-y",             0,  POPT_ARG_VAL,    &fuzzy_basis, 0, 0, 0 },
290 @@ -1134,6 +1137,9 @@ static void set_refuse_options(void)
291                 ref = cp + 1;
292         }
293  
294 +       if (*lp_link_by_hash_dir(module_id))
295 +               parse_one_refuse_match(0, "link-by-hash", list_end);
296 +
297         if (am_daemon) {
298  #ifdef ICONV_OPTION
299                 if (!*lp_charset(module_id))
300 @@ -1832,6 +1838,21 @@ int parse_arguments(int *argc_p, const char ***argv_p)
301                         return 0;
302  #endif
303  
304 +                case OPT_LINK_BY_HASH:
305 +#ifdef HAVE_LINK
306 +                       arg = poptGetOptArg(pc);
307 +                       if (sanitize_paths)
308 +                               arg = sanitize_path(NULL, arg, NULL, 0, SP_DEFAULT);
309 +                       link_by_hash_dir = (char *)arg;
310 +                       break;
311 +#else
312 +                       snprintf(err_buf, sizeof err_buf,
313 +                                "hard links are not supported on this %s\n",
314 +                                am_server ? "server" : "client");
315 +                       rprintf(FERROR, "ERROR: %s", err_buf);
316 +                       return 0;
317 +#endif
318 +
319                 default:
320                         /* A large opt value means that set_refuse_options()
321                          * turned this option off. */
322 @@ -2136,6 +2157,8 @@ int parse_arguments(int *argc_p, const char ***argv_p)
323                         tmpdir = sanitize_path(NULL, tmpdir, NULL, 0, SP_DEFAULT);
324                 if (backup_dir)
325                         backup_dir = sanitize_path(NULL, backup_dir, NULL, 0, SP_DEFAULT);
326 +               if (link_by_hash_dir)
327 +                       link_by_hash_dir = sanitize_path(NULL, link_by_hash_dir, NULL, 0, SP_DEFAULT);
328         }
329         if (daemon_filter_list.head && !am_sender) {
330                 filter_rule_list *elp = &daemon_filter_list;
331 @@ -2811,6 +2834,12 @@ void server_options(char **args, int *argc_p)
332         } else if (inplace)
333                 args[ac++] = "--inplace";
334  
335 +       if (link_by_hash_dir && am_sender) {
336 +               args[ac++] = "--link-by-hash";
337 +               args[ac++] = link_by_hash_dir;
338 +               link_by_hash_dir = NULL; /* optimize sending-side checksums */
339 +       }
340 +
341         if (files_from && (!am_sender || filesfrom_host)) {
342                 if (filesfrom_host) {
343                         args[ac++] = "--files-from";
344 diff --git a/rsync.1.md b/rsync.1.md
345 --- a/rsync.1.md
346 +++ b/rsync.1.md
347 @@ -421,6 +421,7 @@ detailed description below for a complete description.
348  --compare-dest=DIR       also compare destination files relative to DIR
349  --copy-dest=DIR          ... and include copies of unchanged files
350  --link-dest=DIR          hardlink to files in DIR when unchanged
351 +--link-by-hash=DIR       create hardlinks by hash into DIR
352  --compress, -z           compress file data during the transfer
353  --compress-level=NUM     explicitly set compression level
354  --skip-compress=LIST     skip compressing files with suffix in LIST
355 @@ -2244,6 +2245,50 @@ your home directory (remove the '=' for that).
356      specified (or implied by `-a`).  You can work-around this bug by avoiding
357      the `-o` option when sending to an old rsync.
358  
359 +0.  `--link-by-hash=DIR`
360 +
361 +    This option hard links the destination files into `DIR`, a link farm
362 +    arranged by MD5 file hash. The result is that the system will only store
363 +    (usually) one copy of the unique contents of each file, regardless of the
364 +    file's name (it will use extra files if the links overflow the available
365 +    maximum).
366 +
367 +    This patch does not take into account file permissions, extended
368 +    attributes, or ACLs when linking things together, so you should only use
369 +    this if you don't care about preserving those extra file attributes (or if
370 +    they are always the same for identical files).
371 +
372 +    The DIR is relative to the destination directory, so either specify a full
373 +    path to the hash hierarchy, or specify a relative path that puts the links
374 +    outside the destination (e.g. "../links").
375 +
376 +    Keep in mind that the hierarchy is never pruned, so if you need to reclaim
377 +    space, you should remove any files that have just one link (since they are
378 +    not linked into any destination dirs anymore):
379 +
380 +    >     find $DIR -links 1 -delete
381 +
382 +    The link farm's directory hierarchy is determined by the file's (32-char)
383 +    MD5 hash and the file-length.  The hash is split up into directory shards.
384 +    For example, if a file is 54321 bytes long, it could be stored like this:
385 +
386 +    >     $DIR/123/456/789/01234567890123456789012.54321.0
387 +
388 +    Note that the directory layout in this patch was modified for version
389 +    3.1.0, so anyone using an older version of this patch should move their
390 +    existing link hierarchy out of the way and then use the newer rsync to copy
391 +    the saved hierarchy into its new layout.  Assuming that no files have
392 +    overflowed their link limits, this would work:
393 +
394 +    >     mv $DIR $DIR.old
395 +    >     rsync -aiv --link-by-hash=$DIR $DIR.old/ $DIR.tmp/
396 +    >     rm -rf $DIR.tmp
397 +    >     rm -rf $DIR.old
398 +
399 +    If some of your files are at their link limit, you'd be better of using a
400 +    script to calculate the md5 sum of each file in the hierarchy and move it
401 +    to its new location.
402 +
403  0.  `--compress`, `-z`
404  
405      With this option, rsync compresses the file data as it is sent to the
406 diff --git a/rsync.c b/rsync.c
407 --- a/rsync.c
408 +++ b/rsync.c
409 @@ -50,6 +50,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 int sanitize_paths;
415  extern struct file_list *cur_flist, *first_flist, *dir_flist;
416  extern struct chmod_mode_struct *daemon_chmod_modes;
417 @@ -735,6 +736,10 @@ int finish_transfer(const char *fname, const char *fnametmp,
418         }
419         if (ret == 0) {
420                 /* The file was moved into place (not copied), so it's done. */
421 +#ifdef HAVE_LINK
422 +               if (link_by_hash_dir)
423 +                       link_by_hash(fname, fnametmp, file);
424 +#endif
425                 return 1;
426         }
427         /* The file was copied, so tweak the perms of the copied file.  If it
428 diff --git a/rsync.h b/rsync.h
429 --- a/rsync.h
430 +++ b/rsync.h
431 @@ -1356,7 +1356,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_NSTR (DEBUG_IO+1)
441 diff --git a/rsyncd.conf.5.md b/rsyncd.conf.5.md
442 --- a/rsyncd.conf.5.md
443 +++ b/rsyncd.conf.5.md
444 @@ -339,6 +339,23 @@ the values of parameters.  See the GLOBAL PARAMETERS section for more details.
445      is 0, which means no limit.  A negative value disables the module.  See
446      also the "lock file" parameter.
447  
448 +0.  `link by hash dir`
449 +
450 +    When the "link by hash dir" parameter is set to a non-empty string,
451 +    received files will be hard linked into **DIR**, a link farm arranged by
452 +    MD5 file hash. See the `--link-by-hash` option for a full explanation.
453 +
454 +    The **DIR** must be accessible inside any chroot restrictions for the
455 +    module, but can exist outside the transfer location if there is an
456 +    inside-the-chroot path to the module (see "use chroot").  Note that a
457 +    user-specified option does not allow this outside-the-transfer-area
458 +    placement.
459 +
460 +    If this parameter is set, it will disable the `--link-by-hash` command-line
461 +    option for copies into the module.
462 +
463 +The default is for this parameter to be unset.
464 +
465  0.  `log file`
466  
467      When the "log file" parameter is set to a non-empty string, the rsync