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) {
 407           state->bar_width = PROGRESS_BUFFER_SIZE - 8;
 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         sprintf(s, " [%3d%%]\r",
 421                 (100 * state->value) / (state->nb_values - 1));
 422
 423         fprintf(stderr, buffer);
 424       }
 425     }
 426   }
 427 }
 428
 429 void start(const char *dirname1, const char *dirname2) {
 430   struct file_node *list1, *list2;
 431   struct file_node *node1, *node2;
 432   struct progress_state progress_state;
 433   int not_in, found;
 434   int nb_groups, nb_nodes;
 435   int list1_length, list2_length, previous_progress;
 436
 437   char *buffer1 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 438   char *buffer2 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
 439
 440   not_in = 0;
 441
 442   if(show_progress) {
 443     fprintf(stderr, "Scanning %s ... ", dirname1);
 444   }
 445
 446   list1 = scan_directory(0, dirname1);
 447
 448   list1_length = file_list_length(list1);
 449
 450   if(dirname2) {
 451     if(strncmp(dirname2, "not:", 4) == 0) {
 452       not_in = 1;
 453       /* groups are not computed in the not: mode */
 454       show_groups = 0;
 455       dirname2 += 4;
 456     } else if(strncmp(dirname2, "and:", 4) == 0) {
 457       dirname2 += 4;
 458     }
 459     if(show_progress) {
 460       fprintf(stderr, "%s ... ", dirname2);
 461     }
 462     list2 = scan_directory(0, dirname2);
 463   } else {
 464     list2 = list1;
 465   }
 466
 467   if(show_progress) {
 468     fprintf(stderr, "done.\n");
 469     fprintf(stderr,
 470             "%s: %d file%s.\n",
 471             dirname1, list1_length, (list1_length > 1 ? "s" : ""));
 472     if(dirname2) {
 473       list2_length = file_list_length(list2);
 474       fprintf(stderr,
 475               "%s: %d file%s.\n",
 476               dirname2, list2_length, (list2_length > 1 ? "s" : ""));
 477     }
 478     fprintf(stderr, "Now looking for identical files.\n");
 479   }
 480
 481   nb_groups = 0;
 482   previous_progress = -1;
 483   nb_nodes = 0;
 484
 485   progress_state.bar_width = -1;
 486   progress_state.last_position = -1;
 487   progress_state.nb_values = list1_length;
 488
 489   if(not_in) {
 490     for(node1 = list1; node1; node1 = node1->next) {
 491       progress_state.value = nb_nodes;
 492       print_progress(&progress_state);
 493       nb_nodes++;
 494
 495       found = 0;
 496
 497       for(node2 = list2; !found && node2; node2 = node2->next) {
 498         if(same_files(node1, node2, buffer1, buffer2)) {
 499           found = 1;
 500         }
 501       }
 502
 503       if(!found) {
 504         if(show_realpaths) {
 505           printf("%s\n", realpath(node1->name, 0));
 506         } else {
 507           printf("%s\n", node1->name);
 508         }
 509       }
 510     }
 511
 512   } else {
 513     for(node1 = list1; node1; node1 = node1->next) {
 514       progress_state.value = nb_nodes;
 515       print_progress(&progress_state);
 516       nb_nodes++;
 517
 518       for(node2 = list2; node2; node2 = node2->next) {
 519         if(node1->group_id < 0 || node2->group_id < 0) {
 520           if(same_files(node1, node2, buffer1, buffer2)) {
 521             if(node1->group_id < 0) {
 522               if(node2->group_id >= 0) {
 523                 node1->group_id = node2->group_id;
 524               } else {
 525                 node1->group_id = nb_groups;
 526                 node1->dir_id = 1;
 527                 nb_groups++;
 528               }
 529             }
 530             if(node2->group_id < 0) {
 531               node2->group_id = node1->group_id;
 532               node2->dir_id = 2;
 533             }
 534           }
 535         }
 536       }
 537     }
 538   }
 539
 540   if(show_progress) {
 541     fprintf(stderr, "\n");
 542   }
 543
 544   if(dirname2) {
 545     print_result(list1, list2);
 546     file_list_delete(list1);
 547     file_list_delete(list2);
 548   } else {
 549     print_result(list1, 0);
 550     file_list_delete(list1);
 551   }
 552
 553   free(buffer1);
 554   free(buffer2);
 555 }
 556
 557 void usage(FILE *out) {
 558   fprintf(out, "Usage: finddup [OPTION]... DIR1 [[and:|not:]DIR2]\n");
 559   fprintf(out, "Version %s (%s)\n", VERSION_NUMBER, UNAME);
 560   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");
 561   fprintf(out, "\n");
 562   /*            01234567890123456789012345678901234567890123456789012345678901234567890123456789*/
 563   fprintf(out, "   -h, --help                 show this help\n");
 564   fprintf(out, "   -d, --ignore-dots          ignore dot files and directories\n");
 565   fprintf(out, "   -0, --ignore-empty         ignore empty files\n");
 566   fprintf(out, "   -c, --hide-matchings       do not show which files in DIR2 corresponds to\n");
 567   fprintf(out, "                              those in DIR1\n");
 568   fprintf(out, "   -g, --no-group-ids         do not show the file groups\n");
 569   fprintf(out, "   -p, --show-progress        show progress\n");
 570   fprintf(out, "   -r, --real-paths           show the real file paths\n");
 571   fprintf(out, "   -i, --same-inodes-are-different\n");
 572   fprintf(out, "                              consider files with same inode as different\n");
 573 #ifdef WITH_MD5
 574   fprintf(out, "   -m, --md5                  use MD5 hashing\n");
 575 #endif
 576   fprintf(out, "\n");
 577   fprintf(out, "Report bugs and comments to <francois@fleuret.org>.\n");
 578 }
 579
 580 /**********************************************************************/
 581
 582 static struct option long_options[] = {
 583   { "help", no_argument, 0, 'h' },
 584   { "same-inodes-are-different", no_argument, 0, 'i' },
 585   { "real-paths", no_argument, 0, 'r' },
 586   { "hide-matchings", no_argument, 0, 'c' },
 587   { "no-group-ids", no_argument, 0, 'g' },
 588   { "ignore-dots", no_argument, 0, 'd' },
 589   { "ignore-empty", no_argument, 0, '0' },
 590   { "show-progress", no_argument, 0, 'p' },
 591   { "md5", no_argument, 0, 'm' },
 592   { 0, 0, 0, 0 }
 593 };
 594
 595 int main(int argc, char **argv) {
 596   int c;
 597
 598   setlocale (LC_ALL, "");
 599
 600   while ((c = getopt_long(argc, argv, "hircgd0pm",
 601                           long_options, NULL)) != -1) {
 602     switch (c) {
 603
 604     case 'h':
 605       usage(stdout);
 606       exit(EXIT_SUCCESS);
 607
 608       break;
 609
 610     case 'd':
 611       ignore_dotfiles = 1;
 612       break;
 613
 614     case '0':
 615       ignore_empty_files = 1;
 616       break;
 617
 618     case 'r':
 619       show_realpaths = 1;
 620       break;
 621
 622     case 'i':
 623       same_inodes_are_different = 1;
 624       break;
 625
 626     case 'g':
 627       show_groups = 0;
 628       break;
 629
 630     case 'p':
 631       show_progress = 1;
 632       break;
 633
 634     case 'c':
 635       show_hits = 0;
 636       break;
 637
 638     case 'm':
 639 #ifdef WITH_MD5
 640       use_md5 = 1;
 641 #else
 642       fprintf(stderr,
 643               "finddup has not been compiled with MD5 hashing.\n");
 644       usage(stderr);
 645       exit(EXIT_FAILURE);
 646 #endif
 647       break;
 648
 649     default:
 650       usage(stderr);
 651       exit(EXIT_FAILURE);
 652     }
 653   }
 654
 655   if(!isatty(STDERR_FILENO)) {
 656     show_progress = 0;
 657   }
 658
 659   if(optind + 2 == argc) {
 660     start(argv[optind], argv[optind + 1]);
 661   } else if(optind + 1 == argc) {
 662     same_inodes_are_different = 1;
 663     start(argv[optind], 0);
 664   } else {
 665     usage(stderr);
 666     exit(EXIT_FAILURE);
 667   }
 668
 669   exit(EXIT_SUCCESS);
 670 }