aa76c54
/* Copyright (C) 2001 Red Hat, Inc.
aa76c54
aa76c54
   Written by Jakub Jelinek <jakub@redhat.com>.
4495481
aa76c54
   This program is free software; you can redistribute it and/or
aa76c54
   modify it under the terms of the GNU General Public License as
aa76c54
   published by the Free Software Foundation; either version 2 of the
aa76c54
   License, or (at your option) any later version.
4495481
aa76c54
   This program is distributed in the hope that it will be useful,
aa76c54
   but WITHOUT ANY WARRANTY; without even the implied warranty of
aa76c54
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
aa76c54
   General Public License for more details.
4495481
Francisco Javier Tsao Santín 4367f46
   You should have received a copy of the GNU General Public License 
Francisco Javier Tsao Santín 4367f46
   along with this program; if not, write to the Free Software Foundation, 
Francisco Javier Tsao Santín 4367f46
   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */
4495481
1ada992
/*  Changes by Rémy Card to use constants and add option -n.  */
ad11a27
/*  Changes by Jindrich Novy to add option -h, -f, replace mmap(2), fix overflows */
Francisco Javier Tsao Santín 4367f46
/*  Changes by Travers Carter to make atomic hardlinking */
Francisco Javier Tsao Santín 23a1fe5
/*  Changes by Todd Lewis that adds option -x to exclude files with pcre lib */
aa76c54
aa76c54
#define _GNU_SOURCE
Todd Lewis cc12cc7
#define PCRE2_CODE_UNIT_WIDTH 8
aa76c54
#include <sys/types.h>
aa76c54
#include <stdlib.h>
aa76c54
#include <stdio.h>
aa76c54
#include <unistd.h>
aa76c54
#include <sys/stat.h>
aa76c54
#include <sys/mman.h>
aa76c54
#include <string.h>
aa76c54
#include <dirent.h>
aa76c54
#include <fcntl.h>
Travers Carter d2e7a72
#include <errno.h>
Todd Lewis cc12cc7
#include <pcre2.h>
aa76c54
8385109
#define NHASH	(1<<17)	/* Must be a power of 2! */
8385109
#define NIOBUF	(1<<12)
aa76c54
#define NAMELEN	4096
aa76c54
#define NBUF	64
aa76c54
Todd Lewis cc12cc7
pcre2_code *re;
Todd Lewis cc12cc7
PCRE2_SPTR exclude_pattern;
Todd Lewis cc12cc7
pcre2_match_data *match_data;
Todd Lewis cc12cc7
aa76c54
struct _f;
aa76c54
typedef struct _h {
aa76c54
  struct _h *next;
aa76c54
  struct _f *chain;
aa76c54
  off_t size;
aa76c54
  time_t mtime;
aa76c54
} h;
aa76c54
aa76c54
typedef struct _d {
aa76c54
  struct _d *next;
aa76c54
  char name[0];
aa76c54
} d;
aa76c54
aa76c54
d *dirs;
aa76c54
aa76c54
h *hps[NHASH];
aa76c54
aa76c54
int no_link = 0;
aa76c54
int verbose = 0;
aa76c54
int content_only = 0;
ad11a27
int force = 0;
aa76c54
aa76c54
typedef struct _f {
aa76c54
  struct _f *next;
aa76c54
  ino_t ino;
aa76c54
  dev_t dev;
aa76c54
  unsigned int cksum;
aa76c54
  char name[0];
aa76c54
} f;
aa76c54
Francisco Javier Tsao Santín fd6df66
__attribute__((always_inline)) inline unsigned int hash(off_t size, time_t mtime)
aa76c54
{
aa76c54
  return (size ^ mtime) & (NHASH - 1);
aa76c54
}
aa76c54
Francisco Javier Tsao Santín fd6df66
__attribute__((always_inline)) inline int stcmp(struct stat *st1, struct stat *st2, int content_only)
aa76c54
{
aa76c54
  if (content_only)
aa76c54
    return st1->st_size != st2->st_size;
aa76c54
  return st1->st_mode != st2->st_mode || st1->st_uid != st2->st_uid ||
aa76c54
         st1->st_gid != st2->st_gid || st1->st_size != st2->st_size ||
aa76c54
         st1->st_mtime != st2->st_mtime;
aa76c54
}
aa76c54
8385109
long long ndirs, nobjects, nregfiles, ncomp, nlinks, nsaved;
aa76c54
aa76c54
void doexit(int i)
aa76c54
{
4495481
  if (verbose) {
aa76c54
    fprintf(stderr, "\n\n");
aa76c54
    fprintf(stderr, "Directories %lld\n", ndirs);
aa76c54
    fprintf(stderr, "Objects %lld\n", nobjects);
aa76c54
    fprintf(stderr, "IFREG %lld\n", nregfiles);
aa76c54
    fprintf(stderr, "Comparisons %lld\n", ncomp);
aa76c54
    fprintf(stderr, "%s %lld\n", (no_link ? "Would link" : "Linked"), nlinks);
aa76c54
    fprintf(stderr, "%s %lld\n", (no_link ? "Would save" : "saved"), nsaved);
aa76c54
  }
aa76c54
  exit(i);
aa76c54
}
aa76c54
8c8d153
void usage(char *prog)
aa76c54
{
Todd Lewis cc12cc7
  fprintf (stderr, "Usage: %s [-cnvhf] [-x pat] directories...\n", prog);
88049ce
  fprintf (stderr, "  -c    When finding candidates for linking, compare only file contents.\n");
88049ce
  fprintf (stderr, "  -n    Don't actually link anything, just report what would be done.\n");
3f7d2b4
  fprintf (stderr, "  -v    Print summary after hardlinking.\n");
3f7d2b4
  fprintf (stderr, "  -vv   Print every hardlinked file and bytes saved + summary.\n");
ad11a27
  fprintf (stderr, "  -f    Force hardlinking across filesystems.\n");
Todd Lewis cc12cc7
  fprintf (stderr, "  -x pat Exclude files matching pattern.\n");
56723b3
  fprintf (stderr, "  -h    Show help.\n");
aa76c54
  exit(255);
aa76c54
}
aa76c54
aa76c54
unsigned int buf[NBUF];
8385109
char iobuf1[NIOBUF], iobuf2[NIOBUF];
aa76c54
Francisco Javier Tsao Santín fd6df66
__attribute__((always_inline)) inline size_t add2(size_t a, size_t b)
4495481
{
4495481
  size_t sum = a + b;
4495481
  if (sum < a) {
4495481
    fprintf(stderr, "\nInteger overflow\n");
4495481
    doexit(5);
4495481
  }
4495481
  return sum;
4495481
}
4495481
Francisco Javier Tsao Santín fd6df66
__attribute__((always_inline)) inline size_t add3(size_t a, size_t b, size_t c) 
4495481
{
4495481
  return add2(add2(a, b), c);
4495481
}
4495481
4495481
typedef struct {
4495481
  char *buf;
4495481
  size_t alloc;
4495481
} dynstr;
4495481
4495481
void growstr(dynstr *str, size_t newlen)
4495481
{
4495481
  if (newlen < str->alloc)
4495481
    return;
4495481
  str->buf = realloc(str->buf, str->alloc = add2(newlen, 1));
4495481
  if (!str->buf) {
4495481
    fprintf(stderr, "\nOut of memory 4\n");
4495481
    doexit(4);
4495481
  }
4495481
}
ad11a27
dev_t dev = 0;
4495481
void rf (const char *name)
aa76c54
{
aa76c54
  struct stat st, st2, st3;
4495481
  const size_t namelen = strlen(name);
aa76c54
  nobjects++;
aa76c54
  if (lstat (name, &st))
aa76c54
    return;
ad11a27
  if (st.st_dev != dev && !force) {
ad11a27
    if (dev) {
ad11a27
      fprintf(stderr, "%s is on different filesystem than the rest.\nUse -f option to override.\n", name);
ad11a27
      doexit(6);
ad11a27
    }
ad11a27
    dev = st.st_dev;
ad11a27
  }
aa76c54
  if (S_ISDIR (st.st_mode)) {
4495481
    d * dp = malloc(add3(sizeof(d), namelen, 1));
aa76c54
    if (!dp) {
aa76c54
      fprintf(stderr, "\nOut of memory 3\n");
aa76c54
      doexit(3);
aa76c54
    }
4495481
    memcpy(dp->name, name, namelen + 1);
aa76c54
    dp->next = dirs;
aa76c54
    dirs = dp;
aa76c54
  } else if (S_ISREG (st.st_mode)) {
aa76c54
    int fd, i;
aa76c54
    f * fp, * fp2;
aa76c54
    h * hp;
4495481
    const char *n1, *n2;
aa76c54
    int cksumsize = sizeof(buf);
aa76c54
    unsigned int cksum;
aa76c54
    time_t mtime = content_only ? 0 : st.st_mtime;
aa76c54
    unsigned int hsh = hash (st.st_size, mtime);
8385109
    off_t fsize;
aa76c54
    nregfiles++;
aa76c54
    if (verbose > 1)
aa76c54
      fprintf(stderr, "  %s", name);
aa76c54
    fd = open (name, O_RDONLY);
aa76c54
    if (fd < 0) return;
aa76c54
    if (st.st_size < sizeof(buf)) {
aa76c54
      cksumsize = st.st_size;
aa76c54
      memset (((char *)buf) + cksumsize, 0, (sizeof(buf) - cksumsize) % sizeof(buf[0]));
aa76c54
    }
aa76c54
    if (read (fd, buf, cksumsize) != cksumsize) {
aa76c54
      close(fd);
4495481
      if (verbose > 1 && namelen <= NAMELEN)
4495481
        fprintf(stderr, "\r%*s\r", (int)(namelen + 2), "");
aa76c54
      return;
aa76c54
    }
aa76c54
    cksumsize = (cksumsize + sizeof(buf[0]) - 1) / sizeof(buf[0]);
aa76c54
    for (i = 0, cksum = 0; i < cksumsize; i++) {
aa76c54
      if (cksum + buf[i] < cksum)
aa76c54
        cksum += buf[i] + 1;
aa76c54
      else
aa76c54
        cksum += buf[i];
aa76c54
    }
aa76c54
    for (hp = hps[hsh]; hp; hp = hp->next)
aa76c54
      if (hp->size == st.st_size && hp->mtime == mtime)
aa76c54
        break;
aa76c54
    if (!hp) {
aa76c54
      hp = malloc(sizeof(h));
aa76c54
      if (!hp) {
aa76c54
        fprintf(stderr, "\nOut of memory 1\n");
aa76c54
        doexit(1);
aa76c54
      }
aa76c54
      hp->size = st.st_size;
aa76c54
      hp->mtime = mtime;
aa76c54
      hp->chain = NULL;
aa76c54
      hp->next = hps[hsh];
aa76c54
      hps[hsh] = hp;
aa76c54
    }
aa76c54
    for (fp = hp->chain; fp; fp = fp->next)
aa76c54
      if (fp->cksum == cksum)
aa76c54
        break;
aa76c54
    for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next)
aa76c54
      if (fp2->ino == st.st_ino && fp2->dev == st.st_dev) {
aa76c54
        close(fd);
4495481
        if (verbose > 1 && namelen <= NAMELEN)
4495481
          fprintf(stderr, "\r%*s\r", (int)(namelen + 2), "");
aa76c54
        return;
aa76c54
      }
aa76c54
    for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next)
aa76c54
      if (!lstat (fp2->name, &st2) && S_ISREG (st2.st_mode) &&
aa76c54
          !stcmp (&st, &st2, content_only) &&
aa76c54
          st2.st_ino != st.st_ino &&
aa76c54
          st2.st_dev == st.st_dev) {
aa76c54
        int fd2 = open (fp2->name, O_RDONLY);
aa76c54
        if (fd2 < 0) continue;
687892a
        if (fstat (fd2, &st2) || !S_ISREG (st2.st_mode) || st2.st_size == 0) {
aa76c54
          close (fd2);
aa76c54
          continue;
aa76c54
        }
aa76c54
        ncomp++;
8385109
	lseek(fd, 0, SEEK_SET);
8385109
	for (fsize = st.st_size; fsize > 0; fsize -= NIOBUF) {
8385109
	  off_t rsize = fsize >= NIOBUF ? NIOBUF : fsize;
8385109
	  if (read (fd, iobuf1, rsize) != rsize || read (fd2, iobuf2, rsize) != rsize) {
8385109
	    close(fd);
8385109
	    close(fd2);
8385109
	    fprintf(stderr, "\nReading error\n");
8385109
	    return;
8385109
	  }
8385109
	  if (memcmp (iobuf1, iobuf2, rsize)) break;
8385109
	}
8385109
	close(fd2);
8385109
	if (fsize > 0) continue;
aa76c54
        if (lstat (name, &st3)) {
aa76c54
          fprintf(stderr, "\nCould not stat %s again\n", name);
aa76c54
          close(fd);
aa76c54
          return;
aa76c54
        }
aa76c54
        st3.st_atime = st.st_atime;
aa76c54
        if (stcmp (&st, &st3, 0)) {
aa76c54
          fprintf(stderr, "\nFile %s changed underneath us\n", name);
aa76c54
          close(fd);
aa76c54
          return;
aa76c54
        }
aa76c54
        n1 = fp2->name;
aa76c54
        n2 = name;
aa76c54
        if (!no_link) {
4495481
          const char *suffix = ".$$$___cleanit___$$$";
4495481
          const size_t suffixlen = strlen(suffix);
4495481
          size_t n2len = strlen(n2);
4495481
          dynstr nam2 = {NULL, 0};
4495481
          growstr(&nam2, add2(n2len, suffixlen));
4495481
          memcpy(nam2.buf, n2, n2len);
4495481
          memcpy(&nam2.buf[n2len], suffix, suffixlen + 1);
Travers Carter d2e7a72
          /* First create a temporary link to n1 under a new name */
Travers Carter d2e7a72
          if (link(n1, nam2.buf)) {
Travers Carter d2e7a72
            fprintf(stderr, "\nFailed to hardlink %s to %s (create temporary link as %s failed - %s)\n", n1, n2, nam2.buf, strerror(errno));
4495481
            free(nam2.buf);
aa76c54
            continue;
aa76c54
          }
Travers Carter d2e7a72
          /* Then rename into place over the existing n2 */
Travers Carter d2e7a72
          if (rename (nam2.buf, n2)) {
Travers Carter d2e7a72
            fprintf(stderr, "\nFailed to hardlink %s to %s (rename temporary link to %s failed - %s)\n", n1, n2, n2, strerror(errno));
Travers Carter d2e7a72
            /* Something went wrong, try to remove the now redundant temporary link */
Travers Carter d2e7a72
            if (unlink(nam2.buf)) {
Travers Carter d2e7a72
              fprintf(stderr, "\nFailed to remove temporary link %s - %s\n", nam2.buf, strerror(errno));
aa76c54
            }
4495481
            free(nam2.buf);
Travers Carter d2e7a72
            continue;
aa76c54
          }
4495481
          free(nam2.buf);
aa76c54
        }
aa76c54
        nlinks++;
aa76c54
        if (st3.st_nlink > 1) {
aa76c54
	  /* We actually did not save anything this time, since the link second argument
aa76c54
	     had some other links as well.  */
aa76c54
          if (verbose > 1)
4495481
            fprintf(stderr, "\r%*s\r%s %s to %s\n", (int)(((namelen > NAMELEN) ? 0 : namelen) + 2), "", (no_link ? "Would link" : "Linked"), n1, n2);
aa76c54
        } else {
aa76c54
          nsaved+=((st.st_size+4095)/4096)*4096;
aa76c54
          if (verbose > 1)
4495481
            fprintf(stderr, "\r%*s\r%s %s to %s, %s %ld\n", (int)(((namelen > NAMELEN) ? 0 : namelen) + 2), "", (no_link ? "Would link" : "Linked"), n1, n2, (no_link ? "would save" : "saved"), st.st_size);
aa76c54
	}
aa76c54
        close(fd);
aa76c54
        return;
aa76c54
      }
4495481
    fp2 = malloc(add3(sizeof(f), namelen, 1));
aa76c54
    if (!fp2) {
aa76c54
      fprintf(stderr, "\nOut of memory 2\n");
aa76c54
      doexit(2);
aa76c54
    }
aa76c54
    close(fd);
aa76c54
    fp2->ino = st.st_ino;
aa76c54
    fp2->dev = st.st_dev;
aa76c54
    fp2->cksum = cksum;
4495481
    memcpy(fp2->name, name, namelen + 1);
aa76c54
    if (fp) {
aa76c54
      fp2->next = fp->next;
aa76c54
      fp->next = fp2;
aa76c54
    } else {
aa76c54
      fp2->next = hp->chain;
aa76c54
      hp->chain = fp2;
aa76c54
    }
4495481
    if (verbose > 1 && namelen <= NAMELEN)
4495481
      fprintf(stderr, "\r%*s\r", (int)(namelen + 2), "");
aa76c54
    return;
aa76c54
  }
aa76c54
}
aa76c54
aa76c54
int main(int argc, char **argv)
aa76c54
{
aa76c54
  int ch;
aa76c54
  int i;
Todd Lewis cc12cc7
  int errornumber;
Todd Lewis cc12cc7
  PCRE2_SIZE erroroffset;
4495481
  dynstr nam1 = {NULL, 0};
Todd Lewis cc12cc7
  while ((ch = getopt (argc, argv, "cnvhfx:")) != -1) {
aa76c54
    switch (ch) {
aa76c54
    case 'n':
aa76c54
      no_link++;
aa76c54
      break;
aa76c54
    case 'v':
aa76c54
      verbose++;
aa76c54
      break;
aa76c54
    case 'c':
aa76c54
      content_only++;
aa76c54
      break;
ad11a27
    case 'f':
ad11a27
      force=1;
ad11a27
      break;
Todd Lewis cc12cc7
    case 'x':
Todd Lewis cc12cc7
    	exclude_pattern = (PCRE2_SPTR)optarg;
Todd Lewis cc12cc7
    	break;
56723b3
    case 'h':
aa76c54
    default:
aa76c54
      usage(argv[0]);
aa76c54
    }
aa76c54
  }
aa76c54
  if (optind >= argc)
aa76c54
    usage(argv[0]);
Todd Lewis cc12cc7
  if (exclude_pattern) {
Todd Lewis cc12cc7
    re = pcre2_compile(
Todd Lewis cc12cc7
          exclude_pattern,       /* the pattern */
Todd Lewis cc12cc7
          PCRE2_ZERO_TERMINATED, /* indicates pattern is zero-terminate */
Todd Lewis cc12cc7
          0,                     /* default options */
Todd Lewis cc12cc7
          &errornumber,
Todd Lewis cc12cc7
          &erroroffset,
Todd Lewis cc12cc7
          NULL);                 /* use default compile context */
Todd Lewis cc12cc7
    if (!re) {
Todd Lewis cc12cc7
      PCRE2_UCHAR buffer[256];
Todd Lewis cc12cc7
      pcre2_get_error_message(errornumber, buffer, sizeof(buffer));
Todd Lewis cc12cc7
      fprintf(stderr, "pattern error at offset %d: %s\n", (int)erroroffset, buffer);
Todd Lewis cc12cc7
      usage(argv[0]);
Todd Lewis cc12cc7
    }
Todd Lewis cc12cc7
    match_data = pcre2_match_data_create_from_pattern(re, NULL);
Todd Lewis cc12cc7
  }
aa76c54
  for (i = optind; i < argc; i++)
aa76c54
    rf(argv[i]);
aa76c54
  while (dirs) {
4495481
    DIR *dh;
4495481
    struct dirent *di;
4495481
    d * dp = dirs;
4495481
    size_t nam1baselen = strlen(dp->name);
aa76c54
    dirs = dp->next;
4495481
    growstr(&nam1, add2(nam1baselen, 1));
4495481
    memcpy(nam1.buf, dp->name, nam1baselen);
aa76c54
    free (dp);
4495481
    nam1.buf[nam1baselen++] = '/';
4495481
    nam1.buf[nam1baselen] = 0;
4495481
    dh = opendir (nam1.buf);
aa76c54
    if (dh == NULL)
aa76c54
      continue;
aa76c54
    ndirs++;
aa76c54
    while ((di = readdir (dh)) != NULL) {
aa76c54
      if (!di->d_name[0])
aa76c54
        continue;
aa76c54
      if (di->d_name[0] == '.') {
Todd Lewis cc12cc7
        if (!di->d_name[1] || !strcmp(di->d_name, ".."))
aa76c54
          continue;
Todd Lewis cc12cc7
      }
Todd Lewis cc12cc7
      if (re && pcre2_match(
Todd Lewis cc12cc7
                  re,                 /* compiled regex */
Todd Lewis cc12cc7
                  (PCRE2_SPTR)di->d_name,
Todd Lewis cc12cc7
                  strlen(di->d_name),
Todd Lewis cc12cc7
                  0,                  /* start at offset 0 */
Todd Lewis cc12cc7
                  0,                  /* default options */
Todd Lewis cc12cc7
                  match_data,         /* block for storing the result */
Todd Lewis cc12cc7
                  NULL)              /* use default match context */
Todd Lewis cc12cc7
                        >= 0) {
Todd Lewis cc12cc7
        if (verbose) {
4495481
          nam1.buf[nam1baselen] = 0;
Todd Lewis cc12cc7
          fprintf(stderr,"Skipping %s%s\n", nam1.buf, di->d_name);
aa76c54
        }
Todd Lewis cc12cc7
        continue; 
aa76c54
      }
4495481
      {
4495481
        size_t subdirlen;
4495481
        growstr(&nam1, add2(nam1baselen, subdirlen = strlen(di->d_name)));
4495481
        memcpy(&nam1.buf[nam1baselen], di->d_name, add2(subdirlen, 1));
4495481
      }
4495481
      rf(nam1.buf);
aa76c54
    }
aa76c54
    closedir(dh);
aa76c54
  }
aa76c54
  doexit(0);
aa76c54
  return 0;
aa76c54
}