finddup.c

   1
   2 /*
   3  *  finddup is a simple utility to find duplicated files, files common
   4  *  to several directories, or files present in one directory and not
   5  *  in another one.
   6  *
   7  *  Copyright (c) 2010 Francois Fleuret
   8  *  Written by Francois Fleuret <francois@fleuret.org>
   9  *
  10  *  This file is part of finddup.
  11  *
  12  *  finddup is free software: you can redistribute it and/or modify it
  13  *  under the terms of the GNU General Public License version 3 as
  14  *  published by the Free Software Foundation.
  15  *
  16  *  finddup is distributed in the hope that it will be useful, but WITHOUT
  17  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18  *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  19  *  License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with finddup.  If not, see <http://www.gnu.org/licenses/>.
  23  *
  24  */
  25
  26 #define VERSION_NUMBER "0.9"
  27
  28 #define _BSD_SOURCE
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <sys/param.h>
  33 #include <dirent.h>
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <unistd.h>
  37 #include <errno.h>
  38 #include <string.h>
  39 #include <sys/ioctl.h>
  40 #include <locale.h>
  41 #include <getopt.h>
  42 #include <fcntl.h>
  43 #ifdef WITH_MD5
  44 #include <openssl/md5.h>
  45 #endif
  46
  47 /* 1M really helps compared to 64k */
  48 #define READ_BUFFER_SIZE (1024 * 1024)
  49
  50 #define PROGRESS_BUFFER_SIZE 1024
  51
  52 typedef int64_t size_sum_t;
  53
  54 /* Yeah, global variables! */
  55
  56 int ignore_dotfiles = 0; /* 1 means ignore files and directories
  57                             starting with a dot */
  58
  59 int ignore_empty_files = 0; /* 1 means ignore empty files */
  60
  61 int show_realpaths = 0; /* 1 means ignore files and directories
  62                             starting with a dot */
  63
  64 int show_progress = 0; /* 1 means show a progress bar when we are in a
  65                           tty */
  66
  67 int show_hits = 1; /* 1 means to show the files from dir2
  68                       corresponding to the ones from dir1 */
  69
  70 int show_groups = 1; /* 1 means to show the group IDs when printing
  71                         file names */
  72
  73 int same_inodes_are_different = 0; /* 1 means that comparison between
  74                                       two files with same inode will
  75                                       always be false */
  76
  77 #ifdef WITH_MD5
  78 int use_md5 = 0; /* 1 means we keep an MD5 signature for each file */
  79 #endif
  80
  81 /********************************************************************/
  82
  83 /* malloc with error checking.  */
  84
  85 void *safe_malloc(size_t n) {
  86   void *p = malloc(n);
  87   if (!p && n != 0) {
  88     printf("Can not allocate memory: %s\n", strerror(errno));
  89     exit(EXIT_FAILURE);
  90   }
  91   return p;
  92 }
  93
  94 /********************************************************************/
  95
  96 int ignore_entry(const char *name) {
  97   return
  98     strcmp(name, ".") == 0 ||
  99     strcmp(name, "..") == 0 ||
 100     (ignore_dotfiles && name[0] == '.' && name[1] != '/');
 101 }
 102
 103 /**********************************************************************/
 104
 105 struct file_node {
 106   struct file_node *next;
 107   char *name;
 108   size_t size;
 109   ino_t inode;
 110   int group_id; /* one per identical file content */
 111   int dir_id; /* 1 for DIR1, and 2 for DIR2 */
 112 #ifdef WITH_MD5
 113   int md5_computed;
 114   unsigned char md5[MD5_DIGEST_LENGTH];
 115 #endif
 116 };
 117
 118 void file_list_delete(struct file_node *head) {
 119   struct file_node *next;
 120   while(head) {
 121     next = head->next;
 122     free(head->name);
 123     free(head);
 124     head = next;
 125   }
 126 }
 127
 128 int file_list_length(struct file_node *head) {
 129   int l = 0;
 130   while(head) {
 131     l++;
 132     head = head->next;
 133   }
 134   return l;
 135 }
 136
 137 /**********************************************************************/
 138
 139 int same_content(struct file_node *f1, struct file_node *f2,
 140                  char *buffer1, char *buffer2) {
 141   int fd1, fd2, s1, s2;
 142
 143 #ifdef WITH_MD5
 144   MD5_CTX c1, c2;
 145
 146   if(use_md5) {
 147     if(f1->md5_computed && f2->md5_computed) {
 148       if(!memcmp(f1->md5, f2->md5, MD5_DIGEST_LENGTH)) {
 149         return 0;
 150       }
 151     } else {
 152       if(!f1->md5_computed) {
 153         MD5_Init(&c1);
 154       }
 155       if(!f2->md5_computed) {
 156         MD5_Init(&c2);
 157       }
 158     }
 159   }
 160 #endif
 161
 162   fd1 = open(f1->name, O_RDONLY);
 163   fd2 = open(f2->name, O_RDONLY);
 164
 165   if(fd1 >= 0 && fd2 >= 0) {
 166     while(1) {
 167       s1 = read(fd1, buffer1, READ_BUFFER_SIZE);
 168       s2 = read(fd2, buffer2, READ_BUFFER_SIZE);
 169
 170       if(s1 < 0 || s2 < 0) {
 171         close(fd1);
 172         close(fd2);
 173         return 0;
 174       }
 175
 176       if(s1 == s2) {
 177         if(s1 == 0) {
 178           close(fd1);
 179           close(fd2);
 180 #ifdef WITH_MD5
 181           if(use_md5) {
 182             if(!f1->md5_computed) {
 183               MD5_Final(f1->md5, &c1);
 184               f1->md5_computed = 1;
 185             }
 186             if(!f2->md5_computed) {
 187               MD5_Final(f2->md5, &c2);
 188               f2->md5_computed = 1;
 189             }
 190           }
 191 #endif
 192           return 1;
 193         } else {
 194           if(memcmp(buffer1, buffer2, s1)) {
 195             close(fd1);
 196             close(fd2);
 197             return 0;
 198           }
 199 #ifdef WITH_MD5
 200           if(use_md5) {
 201             if(!f1->md5_computed) {
 202               MD5_Update(&c1, buffer1, s1);
 203             }
 204             if(!f2->md5_computed) {
 205               MD5_Update(&c2, buffer2, s2);
 206             }
 207           }
 208 #endif
 209         }
 210       } else {
 211         fprintf(stderr,
 212                 "Different read size without error on files of same size.\n");
 213         exit(EXIT_FAILURE);
 214       }
 215     }
 216   } else {
 217
 218     if(fd1 < 0) {
 219       fprintf(stderr,
 220               "Can not open \"%s\" error: %s\n",
 221               f1->name,
 222               strerror(errno));
 223     }
 224
 225     if(fd2 < 0) {
 226       fprintf(stderr,
 227               "Can not open \"%s\" error: %s\n",
 228               f2->name,
 229               strerror(errno));
 230     }
 231
 232     exit(EXIT_FAILURE);
 233   }
 234 }
 235
 236 int same_files(struct file_node *f1, struct file_node *f2,
 237                char *buffer1, char *buffer2) {
 238   if(same_inodes_are_different && f1->inode == f2->inode) {
 239     return 0;
 240   }
 241
 242   return f1->size == f2->size && same_content(f1, f2, buffer1, buffer2);
 243 }
 244
 245 /**********************************************************************/
 246
 247 struct file_node *scan_directory(struct file_node *tail, const char *name) {
 248   DIR *dir;
 249   struct dirent *dir_e;
 250   struct stat sb;
 251   struct file_node *tmp;
 252   char subname[PATH_MAX + 1];
 253
 254   if(lstat(name, &sb) != 0) {
 255     fprintf(stderr, "Can not stat \"%s\": %s\n", name, strerror(errno));
 256     exit(EXIT_FAILURE);
 257   }
 258
 259   if(S_ISLNK(sb.st_mode)) {
 260     return tail;
 261   }
 262
 263   dir = opendir(name);
 264
 265   if(dir) {
 266     while((dir_e = readdir(dir))) {
 267       if(!ignore_entry(dir_e->d_name)) {
 268         snprintf(subname, PATH_MAX, "%s/%s", name, dir_e->d_name);
 269         tail = scan_directory(tail, subname);
 270       }
 271     }
 272     closedir(dir);
 273   } else {
 274     if(S_ISREG(sb.st_mode)) {
 275       if(!ignore_entry(name)) {
 276         if(!ignore_empty_files || sb.st_size > 0) {
 277           tmp = safe_malloc(sizeof(struct file_node));
 278           tmp->next = tail;
 279           tmp->name = strdup(name);
 280           tmp->size = sb.st_size;
 281           tmp->inode = sb.st_ino;
 282           tmp->group_id = -1;
 283           tmp->dir_id = -1;
 284 #ifdef WITH_MD5
 285           tmp->md5_computed = 0;
 286 #endif
 287           tail = tmp;
 288         }
 289       }
 290     }
 291   }
 292
 293   return tail;
 294 }
 295
 296 void print_file(struct file_node *node) {
 297   char tmp[PATH_MAX + 1];
 298   if(show_realpaths) {
 299     if(realpath(node->name, tmp)) {
 300       if(show_groups) {
 301         printf("%d %s\n", node->group_id, tmp);
 302       } else {
 303         printf("%s\n", tmp);
 304       }
 305     } else {
 306       printf("Can not get the realpath of \"%s\": %s\n",
 307              node->name,
 308              strerror(errno));
 309       exit(EXIT_FAILURE);
 310     }
 311   } else {
 312     if(show_groups) {
 313       printf("%d %s\n", node->group_id, node->name);
 314     } else {
 315       printf("%s\n", node->name);
 316     }
 317   }
 318 }
 319
 320 int compare_nodes(const void *x1, const void *x2) {
 321   const struct file_node **f1, **f2;
 322
 323   f1 = (const struct file_node **) x1;
 324   f2 = (const struct file_node **) x2;
 325
 326   if((*f1)->group_id < (*f2)->group_id) {
 327     return -1;
 328   } else if((*f1)->group_id > (*f2)->group_id) {
 329     return 1;
 330   } else {
 331     if((*f1)->dir_id < (*f2)->dir_id) {
 332       return -1;
 333     } else if((*f1)->dir_id > (*f2)->dir_id) {
 334       return 1;
 335     } else {
 336       return 0;
 337     }
 338   }
 339 }
 340
 341
 342 void print_result(struct file_node *list1, struct file_node *list2) {
 343   struct file_node *node1, *node2;
 344   struct file_node **nodes;
 345   int nb, n;
 346
 347   nb = 0;
 348   for(node1 = list1; node1; node1 = node1->next) {
 349     if(node1->group_id >= 0) { nb++; }
 350   }
 351
 352   if(list2) {
 353     for(node2 = list2; node2; node2 = node2->next) {
 354       if(node2->group_id >= 0) { nb++; }
 355     }
 356   }
 357
 358   nodes = safe_malloc(nb * sizeof(struct file_node *));
 359
 360   n = 0;
 361   for(node1 = list1; node1; node1 = node1->next) {
 362     if(node1->group_id >= 0) {
 363       nodes[n++] = node1;
 364     }
 365   }
 366
 367   if(list2) {
 368     for(node2 = list2; node2; node2 = node2->next) {
 369       if(node2->group_id >= 0) {
 370         nodes[n++] = node2;
 371       }
 372     }
 373   }
 374
 375   qsort(nodes, nb, sizeof(struct file_node *), compare_nodes);
 376
 377   for(n = 0; n < nb; n++) {
 378     if(!show_groups && n > 0 && nodes[n]->group_id != nodes[n-1]->group_id) {
 379       printf("\n");
 380     }
 381     print_file(nodes[n]);
 382   }
 383
 384   free(nodes);
 385 }
 386
 387 struct progress_state {
 388   int bar_width;
 389   int nb_values, value;
 390   int last_position;
 391 };
 392
 393 void print_progress(struct progress_state *state) {
 394   int position, k;
 395   struct winsize win;
 396   char buffer[PROGRESS_BUFFER_SIZE];
 397   char *s;
 398
 399   if(show_progress) {
 400     /* We use the previous bar_width to compute the position, so that
 401        we avoid doing too many ioctls */
 402     position = (state->bar_width * state->value) / (state->nb_values - 1);
 403     if(state->bar_width <= 0 || position != state->last_position) {
 404       if(!ioctl (STDERR_FILENO, TIOCGWINSZ, (char *) &win)) {
 405         /* Something weird is going on if the previous test is wrong */
 406         if(win.ws_col >= PROGRESS_BUFFER_SIZE - 3) {
 407           state->bar_width = PROGRESS_BUFFER_SIZE - 10;
 408         } else {
 409           state->bar_width = win.ws_col - 7;
 410         }
 411         position = (state->bar_width * state->value) / (state->nb_values - 1);
 412         state->last_position = position;
 413         s = buffer;
 414         for(k = 0; k < position; k++) {
 415           *(s++) = '+';
 416         }
 417         for(; k < state->bar_width; k++) {
 418           *(s++) = '-';
 419         }
 420
 421         /* We need four % because of the fprintf that follows */
 422         sprintf(s, " [%3d%%%%]\r",
 423                 (100 * state->value) / (state->nb_values - 1));
 424
 425         fprintf(stderr, buffer);
 426       }
 427     }
 428   }
 429 }
 430
 431 void start(const char *dirname1, const char *dirname2) {
 432   struct file_node *list1, *list2;
 433   struct file_node *node1, *node2;
 434   struct progress_state progress_state;
 435   int not_in, found;
 436   int nb_groups, nb_nodes;
 437   int list1_length, list2_length, previous_progress;
 438
 439   char *buffer1 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 440   char *buffer2 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 441
 442   not_in = 0;
 443
 444   if(show_progress) {
 445     fprintf(stderr, "Scanning %s ... ", dirname1);
 446   }
 447
 448   list1 = scan_directory(0, dirname1);
 449
 450   list1_length = file_list_length(list1);
 451
 452   if(dirname2) {
 453     if(strncmp(dirname2, "not:", 4) == 0) {
 454       not_in = 1;
 455       /* groups are not computed in the not: mode */
 456       show_groups = 0;
 457       dirname2 += 4;
 458     } else if(strncmp(dirname2, "and:", 4) == 0) {
 459       dirname2 += 4;
 460     }
 461     if(show_progress) {
 462       fprintf(stderr, "%s ... ", dirname2);
 463     }
 464     list2 = scan_directory(0, dirname2);
 465   } else {
 466     list2 = list1;
 467   }
 468
 469   if(show_progress) {
 470     fprintf(stderr, "done.\n");
 471     fprintf(stderr,
 472             "%s: %d file%s.\n",
 473             dirname1, list1_length, (list1_length > 1 ? "s" : ""));
 474     if(dirname2) {
 475       list2_length = file_list_length(list2);
 476       fprintf(stderr,
 477               "%s: %d file%s.\n",
 478               dirname2, list2_length, (list2_length > 1 ? "s" : ""));
 479     }
 480     fprintf(stderr, "Now looking for identical files.\n");
 481   }
 482
 483   nb_groups = 0;
 484   previous_progress = -1;
 485   nb_nodes = 0;
 486
 487   progress_state.bar_width = -1;
 488   progress_state.last_position = -1;
 489   progress_state.nb_values = list1_length;
 490
 491   if(not_in) {
 492     for(node1 = list1; node1; node1 = node1->next) {
 493       progress_state.value = nb_nodes;
 494       print_progress(&progress_state);
 495       nb_nodes++;
 496
 497       found = 0;
 498
 499       for(node2 = list2; !found && node2; node2 = node2->next) {
 500         if(same_files(node1, node2, buffer1, buffer2)) {
 501           found = 1;
 502         }
 503       }
 504
 505       if(!found) {
 506         if(show_realpaths) {
 507           printf("%s\n", realpath(node1->name, 0));
 508         } else {
 509           printf("%s\n", node1->name);
 510         }
 511       }
 512     }
 513
 514   } else {
 515     for(node1 = list1; node1; node1 = node1->next) {
 516       progress_state.value = nb_nodes;
 517       print_progress(&progress_state);
 518       nb_nodes++;
 519
 520       for(node2 = list2; node2; node2 = node2->next) {
 521         if(node1->group_id < 0 || node2->group_id < 0) {
 522           if(same_files(node1, node2, buffer1, buffer2)) {
 523             if(node1->group_id < 0) {
 524               if(node2->group_id >= 0) {
 525                 node1->group_id = node2->group_id;
 526               } else {
 527                 node1->group_id = nb_groups;
 528                 node1->dir_id = 1;
 529                 nb_groups++;
 530               }
 531             }
 532             if(node2->group_id < 0) {
 533               node2->group_id = node1->group_id;
 534               node2->dir_id = 2;
 535             }
 536           }
 537         }
 538       }
 539     }
 540   }
 541
 542   if(show_progress) {
 543     fprintf(stderr, "\n");
 544   }
 545
 546   if(dirname2) {
 547     print_result(list1, list2);
 548     file_list_delete(list1);
 549     file_list_delete(list2);
 550   } else {
 551     print_result(list1, 0);
 552     file_list_delete(list1);
 553   }
 554
 555   free(buffer1);
 556   free(buffer2);
 557 }
 558
 559 void usage(FILE *out) {
 560   fprintf(out, "Usage: finddup [OPTION]... DIR1 [[and:|not:]DIR2]\n");
 561   fprintf(out, "Version %s (%s)\n", VERSION_NUMBER, UNAME);
 562   fprintf(out, "Without DIR2, lists duplicated files found in DIR1. With DIR2, lists files common to both directories. With the not: prefix, lists files found in DIR1 which do not exist in DIR2. The and: prefix is the default and should be used only if you have a directory starting with 'not:'\n");
 563   fprintf(out, "\n");
 564   /*            01234567890123456789012345678901234567890123456789012345678901234567890123456789*/
 565   fprintf(out, "   -h, --help                 show this help\n");
 566   fprintf(out, "   -d, --ignore-dots          ignore dot files and directories\n");
 567   fprintf(out, "   -0, --ignore-empty         ignore empty files\n");
 568   fprintf(out, "   -c, --hide-matchings       do not show which files in DIR2 corresponds to\n");
 569   fprintf(out, "                              those in DIR1\n");
 570   fprintf(out, "   -g, --no-group-ids         do not show the file groups\n");
 571   fprintf(out, "   -p, --show-progress        show progress\n");
 572   fprintf(out, "   -r, --real-paths           show the real file paths\n");
 573   fprintf(out, "   -i, --same-inodes-are-different\n");
 574   fprintf(out, "                              consider files with same inode as different\n");
 575 #ifdef WITH_MD5
 576   fprintf(out, "   -m, --md5                  use MD5 hashing\n");
 577 #endif
 578   fprintf(out, "\n");
 579   fprintf(out, "Report bugs and comments to <francois@fleuret.org>.\n");
 580 }
 581
 582 /**********************************************************************/
 583
 584 static struct option long_options[] = {
 585   { "help", no_argument, 0, 'h' },
 586   { "same-inodes-are-different", no_argument, 0, 'i' },
 587   { "real-paths", no_argument, 0, 'r' },
 588   { "hide-matchings", no_argument, 0, 'c' },
 589   { "no-group-ids", no_argument, 0, 'g' },
 590   { "ignore-dots", no_argument, 0, 'd' },
 591   { "ignore-empty", no_argument, 0, '0' },
 592   { "show-progress", no_argument, 0, 'p' },
 593   { "md5", no_argument, 0, 'm' },
 594   { 0, 0, 0, 0 }
 595 };
 596
 597 int main(int argc, char **argv) {
 598   int c;
 599
 600   setlocale (LC_ALL, "");
 601
 602   while ((c = getopt_long(argc, argv, "hircgd0pm",
 603                           long_options, NULL)) != -1) {
 604     switch (c) {
 605
 606     case 'h':
 607       usage(stdout);
 608       exit(EXIT_SUCCESS);
 609
 610       break;
 611
 612     case 'd':
 613       ignore_dotfiles = 1;
 614       break;
 615
 616     case '0':
 617       ignore_empty_files = 1;
 618       break;
 619
 620     case 'r':
 621       show_realpaths = 1;
 622       break;
 623
 624     case 'i':
 625       same_inodes_are_different = 1;
 626       break;
 627
 628     case 'g':
 629       show_groups = 0;
 630       break;
 631
 632     case 'p':
 633       show_progress = 1;
 634       break;
 635
 636     case 'c':
 637       show_hits = 0;
 638       break;
 639
 640     case 'm':
 641 #ifdef WITH_MD5
 642       use_md5 = 1;
 643 #else
 644       fprintf(stderr,
 645               "finddup has not been compiled with MD5 hashing.\n");
 646       usage(stderr);
 647       exit(EXIT_FAILURE);
 648 #endif
 649       break;
 650
 651     default:
 652       usage(stderr);
 653       exit(EXIT_FAILURE);
 654     }
 655   }
 656
 657   if(!isatty(STDERR_FILENO)) {
 658     show_progress = 0;
 659   }
 660
 661   if(optind + 2 == argc) {
 662     start(argv[optind], argv[optind + 1]);
 663   } else if(optind + 1 == argc) {
 664     same_inodes_are_different = 1;
 665     start(argv[optind], 0);
 666   } else {
 667     usage(stderr);
 668     exit(EXIT_FAILURE);
 669   }
 670
 671   exit(EXIT_SUCCESS);
 672 }