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