misc-utils/hardlink.c

   1 /* Copyright (C) 2001 Red Hat, Inc.
   2
   3    Written by Jakub Jelinek <jakub@redhat.com>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public
  16    License along with this program; see the file COPYING.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 /*  Changes by Rémy Card to use constants and add option -n.  */
  21
  22 #define _GNU_SOURCE
  23 #include <sys/types.h>
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include <unistd.h>
  27 #include <sys/stat.h>
  28 #include <sys/mman.h>
  29 #include <string.h>
  30 #include <dirent.h>
  31 #include <fcntl.h>
  32
  33 #define NHASH   131072  /* Must be a power of 2! */
  34 #define NAMELEN 4096
  35 #define NBUF    64
  36
  37 struct _f;
  38 typedef struct _h {
  39   struct _h *next;
  40   struct _f *chain;
  41   off_t size;
  42   time_t mtime;
  43 } h;
  44
  45 typedef struct _d {
  46   struct _d *next;
  47   char name[0];
  48 } d;
  49
  50 d *dirs;
  51
  52 h *hps[NHASH];
  53
  54 int no_link = 0;
  55 int verbose = 0;
  56 int content_only = 0;
  57
  58 typedef struct _f {
  59   struct _f *next;
  60   ino_t ino;
  61   dev_t dev;
  62   unsigned int cksum;
  63   char name[0];
  64 } f;
  65
  66 inline unsigned int hash(off_t size, time_t mtime)
  67 {
  68   return (size ^ mtime) & (NHASH - 1);
  69 }
  70
  71 inline int stcmp(struct stat *st1, struct stat *st2, int content_only)
  72 {
  73   if (content_only)
  74     return st1->st_size != st2->st_size;
  75   return st1->st_mode != st2->st_mode || st1->st_uid != st2->st_uid ||
  76          st1->st_gid != st2->st_gid || st1->st_size != st2->st_size ||
  77          st1->st_mtime != st2->st_mtime;
  78 }
  79
  80 long long ndirs, nobjects, nregfiles, nmmap, ncomp, nlinks, nsaved;
  81
  82 void doexit(int i)
  83 {
  84   if (verbose) {
  85     fprintf(stderr, "\n\n");
  86     fprintf(stderr, "Directories %lld\n", ndirs);
  87     fprintf(stderr, "Objects %lld\n", nobjects);
  88     fprintf(stderr, "IFREG %lld\n", nregfiles);
  89     fprintf(stderr, "Mmaps %lld\n", nmmap);
  90     fprintf(stderr, "Comparisons %lld\n", ncomp);
  91     fprintf(stderr, "%s %lld\n", (no_link ? "Would link" : "Linked"), nlinks);
  92     fprintf(stderr, "%s %lld\n", (no_link ? "Would save" : "saved"), nsaved);
  93   }
  94   exit(i);
  95 }
  96
  97 void usage(char *prog)
  98 {
  99   fprintf (stderr, "Usage: %s [-cnvh] directories...\n", prog);
 100   fprintf (stderr, "  -c    When finding candidates for linking, compare only file contents.\n");
 101   fprintf (stderr, "  -n    Don't actually link anything, just report what would be done.\n");
 102   fprintf (stderr, "  -v    Operate in verbose mode.\n");
 103   fprintf (stderr, "  -h    Show help.\n");
 104   exit(255);
 105 }
 106
 107 unsigned int buf[NBUF];
 108 char nambuf1[NAMELEN], nambuf2[NAMELEN];
 109
 110 void rf (char *name)
 111 {
 112   struct stat st, st2, st3;
 113   nobjects++;
 114   if (lstat (name, &st))
 115     return;
 116   if (S_ISDIR (st.st_mode)) {
 117     d * dp = malloc(sizeof(d) + 1 + strlen (name));
 118     if (!dp) {
 119       fprintf(stderr, "\nOut of memory 3\n");
 120       doexit(3);
 121     }
 122     strcpy (dp->name, name);
 123     dp->next = dirs;
 124     dirs = dp;
 125   } else if (S_ISREG (st.st_mode)) {
 126     int fd, i;
 127     f * fp, * fp2;
 128     h * hp;
 129     char *p = NULL, *q;
 130     char *n1, *n2;
 131     int cksumsize = sizeof(buf);
 132     unsigned int cksum;
 133     time_t mtime = content_only ? 0 : st.st_mtime;
 134     unsigned int hsh = hash (st.st_size, mtime);
 135     nregfiles++;
 136     if (verbose > 1)
 137       fprintf(stderr, "  %s", name);
 138     fd = open (name, O_RDONLY);
 139     if (fd < 0) return;
 140     if (st.st_size < sizeof(buf)) {
 141       cksumsize = st.st_size;
 142       memset (((char *)buf) + cksumsize, 0, (sizeof(buf) - cksumsize) % sizeof(buf[0]));
 143     }
 144     if (read (fd, buf, cksumsize) != cksumsize) {
 145       close(fd);
 146       if (verbose > 1)
 147         fprintf(stderr, "\r%*s\r", (int)strlen(name)+2, "");
 148       return;
 149     }
 150     cksumsize = (cksumsize + sizeof(buf[0]) - 1) / sizeof(buf[0]);
 151     for (i = 0, cksum = 0; i < cksumsize; i++) {
 152       if (cksum + buf[i] < cksum)
 153         cksum += buf[i] + 1;
 154       else
 155         cksum += buf[i];
 156     }
 157     for (hp = hps[hsh]; hp; hp = hp->next)
 158       if (hp->size == st.st_size && hp->mtime == mtime)
 159         break;
 160     if (!hp) {
 161       hp = malloc(sizeof(h));
 162       if (!hp) {
 163         fprintf(stderr, "\nOut of memory 1\n");
 164         doexit(1);
 165       }
 166       hp->size = st.st_size;
 167       hp->mtime = mtime;
 168       hp->chain = NULL;
 169       hp->next = hps[hsh];
 170       hps[hsh] = hp;
 171     }
 172     for (fp = hp->chain; fp; fp = fp->next)
 173       if (fp->cksum == cksum)
 174         break;
 175     for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next)
 176       if (fp2->ino == st.st_ino && fp2->dev == st.st_dev) {
 177         close(fd);
 178         if (verbose > 1)
 179           fprintf(stderr, "\r%*s\r", (int)strlen(name)+2, "");
 180         return;
 181       }
 182     if (fp && st.st_size > 0) {
 183       p = mmap (NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
 184       nmmap++;
 185       if (p == (void *)-1) {
 186         close(fd);
 187         fprintf(stderr, "\nFailed to mmap %s\n", name);
 188         return;
 189       }
 190     }
 191     for (fp2 = fp; fp2 && fp2->cksum == cksum; fp2 = fp2->next)
 192       if (!lstat (fp2->name, &st2) && S_ISREG (st2.st_mode) &&
 193           !stcmp (&st, &st2, content_only) &&
 194           st2.st_ino != st.st_ino &&
 195           st2.st_dev == st.st_dev) {
 196         int fd2 = open (fp2->name, O_RDONLY);
 197         if (fd2 < 0) continue;
 198         if (fstat (fd2, &st2) || !S_ISREG (st2.st_mode) || st2.st_size == 0) {
 199           close (fd2);
 200           continue;
 201         }
 202         ncomp++;
 203         q = mmap (NULL, st.st_size, PROT_READ, MAP_SHARED, fd2, 0);
 204         if (q == (void *)-1) {
 205           close(fd2);
 206           fprintf(stderr, "\nFailed to mmap %s\n", fp2->name);
 207           continue;
 208         }
 209         if (memcmp (p, q, st.st_size)) {
 210           munmap (q, st.st_size);
 211           close(fd2);
 212           continue;
 213         }
 214         munmap (q, st.st_size);
 215         close(fd2);
 216         if (lstat (name, &st3)) {
 217           fprintf(stderr, "\nCould not stat %s again\n", name);
 218           munmap (p, st.st_size);
 219           close(fd);
 220           return;
 221         }
 222         st3.st_atime = st.st_atime;
 223         if (stcmp (&st, &st3, 0)) {
 224           fprintf(stderr, "\nFile %s changed underneath us\n", name);
 225           munmap (p, st.st_size);
 226           close(fd);
 227           return;
 228         }
 229         n1 = fp2->name;
 230         n2 = name;
 231         if (!no_link) {
 232           strcpy (stpcpy (nambuf2, n2), ".$$$___cleanit___$$$");
 233           if (rename (n2, nambuf2)) {
 234             fprintf(stderr, "\nFailed to rename %s to %s\n", n2, nambuf2);
 235             continue;
 236           }
 237           if (link (n1, n2)) {
 238             fprintf(stderr, "\nFailed to hardlink %s to %s\n", n1, n2);
 239             if (rename (nambuf2, n2)) {
 240               fprintf(stderr, "\nBad bad - failed to rename back %s to %s\n", nambuf2, n2);
 241             }
 242             munmap (p, st.st_size);
 243             close(fd);
 244             return;
 245           }
 246           unlink (nambuf2);
 247         }
 248         nlinks++;
 249         if (st3.st_nlink > 1) {
 250           /* We actually did not save anything this time, since the link second argument
 251              had some other links as well.  */
 252           if (verbose > 1)
 253             fprintf(stderr, "\r%*s\r%s %s to %s\n", (int)strlen(name)+2, "", (no_link ? "Would link" : "Linked"), n1, n2);
 254         } else {
 255           nsaved+=((st.st_size+4095)/4096)*4096;
 256           if (verbose > 1)
 257             fprintf(stderr, "\r%*s\r%s %s to %s, %s %ld\n", (int)strlen(name)+2, "", (no_link ? "Would link" : "Linked"), n1, n2, (no_link ? "would save" : "saved"), st.st_size);
 258         }
 259         munmap (p, st.st_size);
 260         close(fd);
 261         return;
 262       }
 263     if (fp)
 264       munmap (p, st.st_size);
 265     fp2 = malloc(sizeof(f) + 1 + strlen (name));
 266     if (!fp2) {
 267       fprintf(stderr, "\nOut of memory 2\n");
 268       doexit(2);
 269     }
 270     close(fd);
 271     fp2->ino = st.st_ino;
 272     fp2->dev = st.st_dev;
 273     fp2->cksum = cksum;
 274     strcpy(fp2->name, name);
 275     if (fp) {
 276       fp2->next = fp->next;
 277       fp->next = fp2;
 278     } else {
 279       fp2->next = hp->chain;
 280       hp->chain = fp2;
 281     }
 282     if (verbose > 1)
 283       fprintf(stderr, "\r%*s\r", (int)strlen(name)+2, "");
 284     return;
 285   }
 286 }
 287
 288 int main(int argc, char **argv)
 289 {
 290   int ch;
 291   int i;
 292   char *p;
 293   d * dp;
 294   DIR *dh;
 295   struct dirent *di;
 296   while ((ch = getopt (argc, argv, "cnvh")) != -1) {
 297     switch (ch) {
 298     case 'n':
 299       no_link++;
 300       break;
 301     case 'v':
 302       verbose++;
 303       break;
 304     case 'c':
 305       content_only++;
 306       break;
 307     case 'h':
 308     default:
 309       usage(argv[0]);
 310     }
 311   }
 312   if (optind >= argc)
 313     usage(argv[0]);
 314   for (i = optind; i < argc; i++)
 315     rf(argv[i]);
 316   while (dirs) {
 317     dp = dirs;
 318     dirs = dp->next;
 319     strcpy (nambuf1, dp->name);
 320     free (dp);
 321     strcat (nambuf1, "/");
 322     p = strchr (nambuf1, 0);
 323     dh = opendir (nambuf1);
 324     if (dh == NULL)
 325       continue;
 326     ndirs++;
 327     while ((di = readdir (dh)) != NULL) {
 328       if (!di->d_name[0])
 329         continue;
 330       if (di->d_name[0] == '.') {
 331         char *q;
 332         if (!di->d_name[1] || !strcmp (di->d_name, "..") || !strncmp (di->d_name, ".in.", 4))
 333           continue;
 334         q = strrchr (di->d_name, '.');
 335         if (q && strlen (q) == 7 && q != di->d_name) {
 336           *p = 0;
 337           if (verbose)
 338             fprintf(stderr, "Skipping %s%s\n", nambuf1, di->d_name);
 339           continue;
 340         }
 341       }
 342       strcpy (p, di->d_name);
 343       rf(nambuf1);
 344     }
 345     closedir(dh);
 346   }
 347   doexit(0);
 348   return 0;
 349 }