misc-utils/hardlink.c

   1 /*
   2  * hardlink - consolidate duplicate files via hardlinks
   3  *
   4  * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
   5  * Written by Jakub Jelinek <jakub@redhat.com>
   6  *
   7  * Copyright (C) 2019 Karel Zak <kzak@redhat.com>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it would be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; if not, write to the Free Software Foundation, Inc.,
  21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  22  */
  23 #include <sys/types.h>
  24 #include <stdlib.h>
  25 #include <getopt.h>
  26 #include <stdio.h>
  27 #include <unistd.h>
  28 #include <sys/stat.h>
  29 #include <sys/mman.h>
  30 #include <string.h>
  31 #include <dirent.h>
  32 #include <fcntl.h>
  33 #include <errno.h>
  34 #ifdef HAVE_PCRE
  35 # define PCRE2_CODE_UNIT_WIDTH 8
  36 # include <pcre2.h>
  37 #endif
  38
  39 #include "c.h"
  40 #include "xalloc.h"
  41 #include "nls.h"
  42 #include "closestream.h"
  43
  44 #define NHASH   (1<<17)  /* Must be a power of 2! */
  45 #define NBUF    64
  46
  47 struct hardlink_file;
  48
  49 struct hardlink_hash {
  50         struct hardlink_hash *next;
  51         struct hardlink_file *chain;
  52         off_t size;
  53         time_t mtime;
  54 };
  55
  56 struct hardlink_dir {
  57         struct hardlink_dir *next;
  58         char name[];
  59 };
  60
  61 struct hardlink_file {
  62         struct hardlink_file *next;
  63         ino_t ino;
  64         dev_t dev;
  65         unsigned int cksum;
  66         char name[];
  67 };
  68
  69 struct hardlink_dynstr {
  70         char *buf;
  71         size_t alloc;
  72 };
  73
  74 struct hardlink_ctl {
  75         struct hardlink_dir *dirs;
  76         struct hardlink_hash *hps[NHASH];
  77         char iobuf1[BUFSIZ];
  78         char iobuf2[BUFSIZ];
  79         /* summary counters */
  80         unsigned long long ndirs;
  81         unsigned long long nobjects;
  82         unsigned long long nregfiles;
  83         unsigned long long ncomp;
  84         unsigned long long nlinks;
  85         unsigned long long nsaved;
  86         /* current device */
  87         dev_t dev;
  88         /* flags */
  89         unsigned int verbose;
  90         unsigned int
  91                 no_link:1,
  92                 content_only:1,
  93                 force:1;
  94 };
  95 /* ctl is in global scope due use in atexit() */
  96 struct hardlink_ctl global_ctl;
  97
  98 __attribute__ ((always_inline))
  99 static inline unsigned int hash(off_t size, time_t mtime)
 100 {
 101         return (size ^ mtime) & (NHASH - 1);
 102 }
 103
 104 __attribute__ ((always_inline))
 105 static inline int stcmp(struct stat *st1, struct stat *st2, int content_scope)
 106 {
 107         if (content_scope)
 108                 return st1->st_size != st2->st_size;
 109
 110         return st1->st_mode != st2->st_mode
 111                 || st1->st_uid != st2->st_uid
 112                 || st1->st_gid != st2->st_gid
 113                 || st1->st_size != st2->st_size
 114                 || st1->st_mtime != st2->st_mtime;
 115 }
 116
 117 static void print_summary(void)
 118 {
 119         struct hardlink_ctl const *const ctl = &global_ctl;
 120
 121         if (!ctl->verbose)
 122                 return;
 123
 124         if (ctl->verbose > 1 && ctl->nlinks)
 125                 fputc('\n', stdout);
 126
 127         printf(_("Directories:   %9lld\n"), ctl->ndirs);
 128         printf(_("Objects:       %9lld\n"), ctl->nobjects);
 129         printf(_("Regular files: %9lld\n"), ctl->nregfiles);
 130         printf(_("Comparisons:   %9lld\n"), ctl->ncomp);
 131         printf(  "%s%9lld\n", (ctl->no_link ?
 132                _("Would link:    ") :
 133                _("Linked:        ")), ctl->nlinks);
 134         printf(  "%s %9lld\n", (ctl->no_link ?
 135                _("Would save:   ") :
 136                _("Saved:        ")), ctl->nsaved);
 137 }
 138
 139 static void __attribute__((__noreturn__)) usage(void)
 140 {
 141         fputs(USAGE_HEADER, stdout);
 142         printf(_(" %s [options] directory...\n"), program_invocation_short_name);
 143
 144         fputs(USAGE_SEPARATOR, stdout);
 145         puts(_("Consolidate duplicate files using hardlinks."));
 146
 147         fputs(USAGE_OPTIONS, stdout);
 148         puts(_(" -c, --content          compare only contents, ignore permission, etc."));
 149         puts(_(" -n, --dry-run          don't actually link anything"));
 150         puts(_(" -v, --verbose          print summary after hardlinking"));
 151         puts(_(" -vv                    print every hardlinked file and summary"));
 152         puts(_(" -f, --force            force hardlinking across filesystems"));
 153         puts(_(" -x, --exclude <regex>  exclude files matching pattern"));
 154
 155         fputs(USAGE_SEPARATOR, stdout);
 156         printf(USAGE_HELP_OPTIONS(16)); /* char offset to align option descriptions */
 157         printf(USAGE_MAN_TAIL("hardlink(1)"));
 158         exit(EXIT_SUCCESS);
 159 }
 160
 161 __attribute__ ((always_inline))
 162 static inline size_t add2(size_t a, size_t b)
 163 {
 164         size_t sum = a + b;
 165
 166         if (sum < a)
 167                 errx(EXIT_FAILURE, _("integer overflow"));
 168         return sum;
 169 }
 170
 171 __attribute__ ((always_inline))
 172 static inline size_t add3(size_t a, size_t b, size_t c)
 173 {
 174         return add2(add2(a, b), c);
 175 }
 176
 177 static void growstr(struct hardlink_dynstr *str, size_t newlen)
 178 {
 179         if (newlen < str->alloc)
 180                 return;
 181         str->buf = xrealloc(str->buf, str->alloc = add2(newlen, 1));
 182 }
 183
 184 static void process_path(struct hardlink_ctl *ctl, const char *name)
 185 {
 186         struct stat st, st2, st3;
 187         const size_t namelen = strlen(name);
 188
 189         ctl->nobjects++;
 190         if (lstat(name, &st))
 191                 return;
 192
 193         if (st.st_dev != ctl->dev && !ctl->force) {
 194                 if (ctl->dev)
 195                         errx(EXIT_FAILURE,
 196                              _("%s is on different filesystem than the rest "
 197                                "(use -f option to override)."), name);
 198                 ctl->dev = st.st_dev;
 199         }
 200         if (S_ISDIR(st.st_mode)) {
 201                 struct hardlink_dir *dp = xmalloc(add3(sizeof(*dp), namelen, 1));
 202                 memcpy(dp->name, name, namelen + 1);
 203                 dp->next = ctl->dirs;
 204                 ctl->dirs = dp;
 205
 206         } else if (S_ISREG(st.st_mode)) {
 207                 int fd, i;
 208                 struct hardlink_file *fp, *fp2;
 209                 struct hardlink_hash *hp;
 210                 const char *n1, *n2;
 211                 unsigned int buf[NBUF];
 212                 int cksumsize = sizeof(buf);
 213                 unsigned int cksum;
 214                 time_t mtime = ctl->content_only ? 0 : st.st_mtime;
 215                 unsigned int hsh = hash(st.st_size, mtime);
 216                 off_t fsize;
 217
 218                 ctl->nregfiles++;
 219                 if (ctl->verbose > 1)
 220                         printf("%s\n", name);
 221
 222                 fd = open(name, O_RDONLY);
 223                 if (fd < 0)
 224                         return;
 225
 226                 if ((size_t)st.st_size < sizeof(buf)) {
 227                         cksumsize = st.st_size;
 228                         memset(((char *)buf) + cksumsize, 0,
 229                                (sizeof(buf) - cksumsize) % sizeof(buf[0]));
 230                 }
 231                 if (read(fd, buf, cksumsize) != cksumsize) {
 232                         close(fd);
 233                         return;
 234                 }
 235                 cksumsize = (cksumsize + sizeof(buf[0]) - 1) / sizeof(buf[0]);
 236                 for (i = 0, cksum = 0; i < cksumsize; i++) {
 237                         if (cksum + buf[i] < cksum)
 238                                 cksum += buf[i] + 1;
 239                         else
 240                                 cksum += buf[i];
 241                 }
 242                 for (hp = ctl->hps[hsh]; hp; hp = hp->next) {
 243                         if (hp->size == st.st_size && hp->mtime == mtime)
 244                                 break;
 245                 }
 246                 if (!hp) {
 247                         hp = xmalloc(sizeof(*hp));
 248                         hp->size = st.st_size;
 249                         hp->mtime = mtime;
 250                         hp->chain = NULL;
 251                         hp->next = ctl->hps[hsh];
 252                         ctl->hps[hsh] = hp;
 253                 }
 254                 for (fp = hp->chain; fp; fp = fp->next) {
 255                         if (fp->cksum == cksum)
 256                                 break;
 257                 }
 258                 for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next) {
 259                         if (fp2->ino == st.st_ino && fp2->dev == st.st_dev) {
 260                                 close(fd);
 261                                 return;
 262                         }
 263                 }
 264                 for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next) {
 265
 266                         if (!lstat(fp2->name, &st2) && S_ISREG(st2.st_mode) &&
 267                             !stcmp(&st, &st2, ctl->content_only) &&
 268                             st2.st_ino != st.st_ino &&
 269                             st2.st_dev == st.st_dev) {
 270
 271                                 int fd2 = open(fp2->name, O_RDONLY);
 272                                 if (fd2 < 0)
 273                                         continue;
 274
 275                                 if (fstat(fd2, &st2) || !S_ISREG(st2.st_mode)
 276                                     || st2.st_size == 0) {
 277                                         close(fd2);
 278                                         continue;
 279                                 }
 280                                 ctl->ncomp++;
 281                                 lseek(fd, 0, SEEK_SET);
 282
 283                                 for (fsize = st.st_size; fsize > 0;
 284                                      fsize -= (off_t)sizeof(ctl->iobuf1)) {
 285                                         ssize_t xsz;
 286                                         ssize_t rsize = fsize > (ssize_t) sizeof(ctl->iobuf1) ?
 287                                                         (ssize_t) sizeof(ctl->iobuf1) : fsize;
 288
 289                                         if ((xsz = read(fd, ctl->iobuf1, rsize)) != rsize)
 290                                                 warn(_("cannot read %s"), name);
 291                                         else if ((xsz = read(fd2, ctl->iobuf2, rsize)) != rsize)
 292                                                 warn(_("cannot read %s"), fp2->name);
 293
 294                                         if (xsz != rsize) {
 295                                                 close(fd);
 296                                                 close(fd2);
 297                                                 return;
 298                                         }
 299                                         if (memcmp(ctl->iobuf1, ctl->iobuf2, rsize))
 300                                                 break;
 301                                 }
 302                                 close(fd2);
 303                                 if (fsize > 0)
 304                                         continue;
 305                                 if (lstat(name, &st3)) {
 306                                         warn(_("cannot stat %s"), name);
 307                                         close(fd);
 308                                         return;
 309                                 }
 310                                 st3.st_atime = st.st_atime;
 311                                 if (stcmp(&st, &st3, 0)) {
 312                                         warnx(_("file %s changed underneath us"), name);
 313                                         close(fd);
 314                                         return;
 315                                 }
 316                                 n1 = fp2->name;
 317                                 n2 = name;
 318
 319                                 if (!ctl->no_link) {
 320                                         const char *suffix =
 321                                             ".$$$___cleanit___$$$";
 322                                         const size_t suffixlen = strlen(suffix);
 323                                         size_t n2len = strlen(n2);
 324                                         struct hardlink_dynstr nam2 = { NULL, 0 };
 325
 326                                         growstr(&nam2, add2(n2len, suffixlen));
 327                                         memcpy(nam2.buf, n2, n2len);
 328                                         memcpy(&nam2.buf[n2len], suffix,
 329                                                suffixlen + 1);
 330                                         /* First create a temporary link to n1 under a new name */
 331                                         if (link(n1, nam2.buf)) {
 332                                                 warn(_("failed to hardlink %s to %s (create temporary link as %s failed)"),
 333                                                         n1, n2, nam2.buf);
 334                                                 free(nam2.buf);
 335                                                 continue;
 336                                         }
 337                                         /* Then rename into place over the existing n2 */
 338                                         if (rename(nam2.buf, n2)) {
 339                                                 warn(_("failed to hardlink %s to %s (rename temporary link to %s failed)"),
 340                                                         n1, n2, n2);
 341                                                 /* Something went wrong, try to remove the now redundant temporary link */
 342                                                 if (unlink(nam2.buf))
 343                                                         warn(_("failed to remove temporary link %s"), nam2.buf);
 344                                                 free(nam2.buf);
 345                                                 continue;
 346                                         }
 347                                         free(nam2.buf);
 348                                 }
 349                                 ctl->nlinks++;
 350                                 if (st3.st_nlink > 1) {
 351                                         /* We actually did not save anything this time, since the link second argument
 352                                            had some other links as well.  */
 353                                         if (ctl->verbose > 1)
 354                                                 printf(_(" %s %s to %s\n"),
 355                                                         (ctl->no_link ? _("Would link") : _("Linked")),
 356                                                         n1, n2);
 357                                 } else {
 358                                         ctl->nsaved += ((st.st_size + 4095) / 4096) * 4096;
 359                                         if (ctl->verbose > 1)
 360                                                 printf(_(" %s %s to %s, %s %jd\n"),
 361                                                         (ctl->no_link ? _("Would link") : _("Linked")),
 362                                                         n1, n2,
 363                                                         (ctl->no_link ? _("would save") : _("saved")),
 364                                                         (intmax_t)st.st_size);
 365                                 }
 366                                 close(fd);
 367                                 return;
 368                         }
 369                 }
 370                 fp2 = xmalloc(add3(sizeof(*fp2), namelen, 1));
 371                 close(fd);
 372                 fp2->ino = st.st_ino;
 373                 fp2->dev = st.st_dev;
 374                 fp2->cksum = cksum;
 375                 memcpy(fp2->name, name, namelen + 1);
 376
 377                 if (fp) {
 378                         fp2->next = fp->next;
 379                         fp->next = fp2;
 380                 } else {
 381                         fp2->next = hp->chain;
 382                         hp->chain = fp2;
 383                 }
 384                 return;
 385         }
 386 }
 387
 388 int main(int argc, char **argv)
 389 {
 390         int ch;
 391         int i;
 392 #ifdef HAVE_PCRE
 393         int errornumber;
 394         PCRE2_SIZE erroroffset;
 395         pcre2_code *re = NULL;
 396         PCRE2_SPTR exclude_pattern = NULL;
 397         pcre2_match_data *match_data = NULL;
 398 #endif
 399         struct hardlink_dynstr nam1 = { NULL, 0 };
 400         struct hardlink_ctl *ctl = &global_ctl;
 401
 402         static const struct option longopts[] = {
 403                 { "content",    no_argument, NULL, 'c' },
 404                 { "dry-run",    no_argument, NULL, 'n' },
 405                 { "exclude",    required_argument, NULL, 'x' },
 406                 { "force",      no_argument, NULL, 'f' },
 407                 { "help",       no_argument, NULL, 'h' },
 408                 { "verbose",    no_argument, NULL, 'v' },
 409                 { "version",    no_argument, NULL, 'V' },
 410                 { NULL, 0, NULL, 0 },
 411         };
 412
 413         setlocale(LC_ALL, "");
 414         bindtextdomain(PACKAGE, LOCALEDIR);
 415         textdomain(PACKAGE);
 416         close_stdout_atexit();
 417
 418         while ((ch = getopt_long(argc, argv, "cnvfx:Vh", longopts, NULL)) != -1) {
 419                 switch (ch) {
 420                 case 'n':
 421                         ctl->no_link = 1;
 422                         break;
 423                 case 'v':
 424                         ctl->verbose++;
 425                         break;
 426                 case 'c':
 427                         ctl->content_only = 1;
 428                         break;
 429                 case 'f':
 430                         ctl->force = 1;
 431                         break;
 432                 case 'x':
 433 #ifdef HAVE_PCRE
 434                         exclude_pattern = (PCRE2_SPTR) optarg;
 435 #else
 436                         errx(EXIT_FAILURE,
 437                              _("option --exclude not supported (built without pcre2)"));
 438 #endif
 439                         break;
 440                 case 'V':
 441                         print_version(EXIT_SUCCESS);
 442                 case 'h':
 443                         usage();
 444                 default:
 445                         errtryhelp(EXIT_FAILURE);
 446                 }
 447         }
 448
 449         if (optind == argc) {
 450                 warnx(_("no directory specified"));
 451                 errtryhelp(EXIT_FAILURE);
 452         }
 453
 454 #ifdef HAVE_PCRE
 455         if (exclude_pattern) {
 456                 re = pcre2_compile(exclude_pattern, /* the pattern */
 457                                    PCRE2_ZERO_TERMINATED, /* indicates pattern is zero-terminate */
 458                                    0, /* default options */
 459                                    &errornumber, &erroroffset, NULL); /* use default compile context */
 460                 if (!re) {
 461                         PCRE2_UCHAR buffer[256];
 462                         pcre2_get_error_message(errornumber, buffer,
 463                                                 sizeof(buffer));
 464                         errx(EXIT_FAILURE, _("pattern error at offset %d: %s"),
 465                                 (int)erroroffset, buffer);
 466                 }
 467                 match_data = pcre2_match_data_create_from_pattern(re, NULL);
 468         }
 469 #endif
 470         atexit(print_summary);
 471
 472         for (i = optind; i < argc; i++)
 473                 process_path(ctl, argv[i]);
 474
 475         while (ctl->dirs) {
 476                 DIR *dh;
 477                 struct dirent *di;
 478                 struct hardlink_dir *dp = ctl->dirs;
 479                 size_t nam1baselen = strlen(dp->name);
 480
 481                 ctl->dirs = dp->next;
 482                 growstr(&nam1, add2(nam1baselen, 1));
 483                 memcpy(nam1.buf, dp->name, nam1baselen);
 484                 free(dp);
 485                 nam1.buf[nam1baselen++] = '/';
 486                 nam1.buf[nam1baselen] = 0;
 487                 dh = opendir(nam1.buf);
 488
 489                 if (dh == NULL)
 490                         continue;
 491                 ctl->ndirs++;
 492
 493                 while ((di = readdir(dh)) != NULL) {
 494                         if (!di->d_name[0])
 495                                 continue;
 496                         if (di->d_name[0] == '.') {
 497                                 if (!di->d_name[1] || !strcmp(di->d_name, ".."))
 498                                         continue;
 499                         }
 500 #ifdef HAVE_PCRE
 501                         if (re && pcre2_match(re, /* compiled regex */
 502                                               (PCRE2_SPTR) di->d_name, strlen(di->d_name), 0, /* start at offset 0 */
 503                                               0, /* default options */
 504                                               match_data, /* block for storing the result */
 505                                               NULL) /* use default match context */
 506                             >=0) {
 507                                 if (ctl->verbose) {
 508                                         nam1.buf[nam1baselen] = 0;
 509                                         printf(_("Skipping %s%s\n"), nam1.buf, di->d_name);
 510                                 }
 511                                 continue;
 512                         }
 513 #endif
 514                         {
 515                                 size_t subdirlen;
 516                                 growstr(&nam1,
 517                                         add2(nam1baselen, subdirlen =
 518                                              strlen(di->d_name)));
 519                                 memcpy(&nam1.buf[nam1baselen], di->d_name,
 520                                        add2(subdirlen, 1));
 521                         }
 522                         process_path(ctl, nam1.buf);
 523                 }
 524                 closedir(dh);
 525         }
 526
 527         return 0;
 528 }