bin/cpdup/cpdup.c

   1 /*-
   2  * CPDUP.C
   3  *
   4  * CPDUP <options> source destination
   5  *
   6  * (c) Copyright 1997-1999 by Matthew Dillon and Dima Ruban.  Permission to
   7  *     use and distribute based on the FreeBSD copyright.  Supplied as-is,
   8  *     USE WITH EXTREME CAUTION.
   9  *
  10  * This program attempts to duplicate the source onto the destination as
  11  * exactly as possible, retaining modify times, flags, perms, uid, and gid.
  12  * It can duplicate devices, files (including hardlinks), softlinks,
  13  * directories, and so forth.  It is recursive by default!  The duplication
  14  * is inclusive of removal of files/directories on the destination that do
  15  * not exist on the source.  This program supports a per-directory exception
  16  * file called .cpignore, or a user-specified exception file.
  17  *
  18  * Safety features:
  19  *
  20  *      - does not cross partition boundries on source
  21  *      - asks for confirmation on deletions unless -i0 is specified
  22  *      - refuses to replace a destination directory with a source file
  23  *        unless -s0 is specified.
  24  *      - terminates on error
  25  *
  26  * Copying features:
  27  *
  28  *      - does not copy file if mtime, flags, perms, and size match unless
  29  *        forced
  30  *
  31  *      - copies to temporary and renames-over the original, allowing
  32  *        you to update live systems
  33  *
  34  *      - copies uid, gid, mtime, perms, flags, softlinks, devices, hardlinks,
  35  *        and recurses through directories.
  36  *
  37  *      - accesses a per-directory exclusion file, .cpignore, containing
  38  *        standard wildcarded ( ? / * style, NOT regex) exclusions.
  39  *
  40  *      - tries to play permissions and flags smart in regards to overwriting
  41  *        schg files and doing related stuff.
  42  *
  43  *      - Can do MD5 consistancy checks
  44  *
  45  *      - Is able to do incremental mirroring/backups via hardlinks from
  46  *        the 'previous' version (supplied with -H path).
  47  *
  48  * $DragonFly: src/bin/cpdup/cpdup.c,v 1.12 2006/07/05 17:20:37 dillon Exp $
  49  */
  50
  51 /*-
  52  * Example: cc -O cpdup.c -o cpdup -lmd
  53  *
  54  * ".MD5.CHECKSUMS" contains md5 checksumms for the current directory.
  55  * This file is stored on the source.
  56  */
  57
  58 #include "cpdup.h"
  59
  60 #define HSIZE   16384
  61 #define HMASK   (HSIZE-1)
  62 #define HLSIZE  8192
  63 #define HLMASK  (HLSIZE - 1)
  64
  65 typedef struct Node {
  66     struct Node *no_Next;
  67     struct Node *no_HNext;
  68     int  no_Value;
  69     char no_Name[4];
  70 } Node;
  71
  72 typedef struct List {
  73     Node        li_Node;
  74     Node        *li_Hash[HSIZE];
  75 } List;
  76
  77 struct hlink {
  78     ino_t ino;
  79     ino_t dino;
  80     char name[2048];
  81     struct hlink *next;
  82     struct hlink *prev;
  83     nlink_t nlinked;
  84 };
  85
  86 struct hlink *hltable[HLSIZE];
  87
  88 void RemoveRecur(const char *dpath, dev_t devNo);
  89 void InitList(List *list);
  90 void ResetList(List *list);
  91 int AddList(List *list, const char *name, int n);
  92 static struct hlink *hltlookup(struct stat *);
  93 static struct hlink *hltadd(struct stat *, const char *);
  94 static char *checkHLPath(struct stat *st, const char *spath, const char *dpath);
  95 static int shash(const char *s);
  96 static void hltdelete(struct hlink *);
  97 int YesNo(const char *path);
  98 static int xrename(const char *src, const char *dst, u_long flags);
  99 static int xlink(const char *src, const char *dst, u_long flags);
 100 int WildCmp(const char *s1, const char *s2);
 101 int DoCopy(const char *spath, const char *dpath, dev_t sdevNo, dev_t ddevNo);
 102
 103 int AskConfirmation = 1;
 104 int SafetyOpt = 1;
 105 int ForceOpt;
 106 int VerboseOpt;
 107 int QuietOpt;
 108 int NoRemoveOpt;
 109 int UseMD5Opt;
 110 int UseFSMIDOpt;
 111 int SummaryOpt;
 112 int EnableDirectoryRetries;
 113 int DstBaseLen;
 114 char IOBuf1[65536];
 115 char IOBuf2[65536];
 116 const char *UseCpFile;
 117 const char *UseHLPath;
 118 const char *MD5CacheFile;
 119 const char *FSMIDCacheFile;
 120
 121 int64_t CountSourceBytes;
 122 int64_t CountSourceItems;
 123 int64_t CountCopiedItems;
 124 int64_t CountReadBytes;
 125 int64_t CountWriteBytes;
 126 int64_t CountRemovedItems;
 127
 128 int
 129 main(int ac, char **av)
 130 {
 131     int i;
 132     char *src = NULL;
 133     char *dst = NULL;
 134     struct timeval start;
 135
 136     gettimeofday(&start, NULL);
 137     for (i = 1; i < ac; ++i) {
 138         char *ptr = av[i];
 139         int v = 1;
 140
 141         if (*ptr != '-') {
 142             if (src == NULL) {
 143                 src = ptr;
 144             } else if (dst == NULL) {
 145                 dst = ptr;
 146             } else {
 147                 fatal("too many arguments");
 148                 /* not reached */
 149             }
 150             continue;
 151         }
 152         ptr += 2;
 153
 154         if (*ptr)
 155             v = strtol(ptr, NULL, 0);
 156
 157         switch(ptr[-1]) {
 158         case 'v':
 159             VerboseOpt = 1;
 160             while (*ptr == 'v') {
 161                 ++VerboseOpt;
 162                 ++ptr;
 163             }
 164             if (*ptr >= '0' && *ptr <= '9')
 165                 VerboseOpt = strtol(ptr, NULL, 0);
 166             break;
 167         case 'I':
 168             SummaryOpt = v;
 169             break;
 170         case 'o':
 171             NoRemoveOpt = v;
 172             break;
 173         case 'x':
 174             UseCpFile = ".cpignore";
 175             break;
 176         case 'X':
 177             UseCpFile = (*ptr) ? ptr : av[++i];
 178             break;
 179         case 'H':
 180             UseHLPath = (*ptr) ? ptr : av[++i];
 181             break;
 182         case 'f':
 183             ForceOpt = v;
 184             break;
 185         case 'i':
 186             AskConfirmation = v;
 187             break;
 188         case 's':
 189             SafetyOpt = v;
 190             break;
 191         case 'q':
 192             QuietOpt = v;
 193             break;
 194         case 'k':
 195             UseFSMIDOpt = v;
 196             FSMIDCacheFile = ".FSMID.CHECK";
 197             break;
 198         case 'K':
 199             UseFSMIDOpt = v;
 200             FSMIDCacheFile = av[++i];
 201             break;
 202         case 'M':
 203             UseMD5Opt = v;
 204             MD5CacheFile = av[++i];
 205             break;
 206         case 'm':
 207             UseMD5Opt = v;
 208             MD5CacheFile = ".MD5.CHECKSUMS";
 209             break;
 210         case 'u':
 211             setvbuf(stdout, NULL, _IOLBF, 0);
 212             break;
 213         default:
 214             fatal("illegal option: %s\n", ptr - 2);
 215             /* not reached */
 216             break;
 217         }
 218     }
 219
 220     /*
 221      * dst may be NULL only if -m option is specified,
 222      * which forces an update of the MD5 checksums
 223      */
 224
 225     if (dst == NULL && UseMD5Opt == 0) {
 226         fatal(NULL);
 227         /* not reached */
 228     }
 229     if (dst) {
 230         DstBaseLen = strlen(dst);
 231         i = DoCopy(src, dst, (dev_t)-1, (dev_t)-1);
 232     } else {
 233         i = DoCopy(src, NULL, (dev_t)-1, (dev_t)-1);
 234     }
 235     md5_flush();
 236     fsmid_flush();
 237
 238     if (SummaryOpt && i == 0) {
 239         long duration;
 240         struct timeval end;
 241
 242         gettimeofday(&end, NULL);
 243         CountSourceBytes += sizeof(struct stat) * CountSourceItems;
 244         CountReadBytes += sizeof(struct stat) * CountSourceItems;
 245         CountWriteBytes +=  sizeof(struct stat) * CountCopiedItems;
 246         CountWriteBytes +=  sizeof(struct stat) * CountRemovedItems;
 247
 248         duration = end.tv_sec - start.tv_sec;
 249         duration *= 1000000;
 250         duration += end.tv_usec - start.tv_usec;
 251         if (duration == 0) duration = 1;
 252         logstd("cpdup completed successfully\n");
 253         logstd("%lld bytes source %lld bytes read %lld bytes written (%.1fX speedup)\n",
 254             (long long)CountSourceBytes,
 255             (long long)CountReadBytes,
 256             (long long)CountWriteBytes,
 257             ((double)CountSourceBytes * 2.0) / ((double)(CountReadBytes + CountWriteBytes)));
 258         logstd("%lld source items %lld items copied %lld things deleted\n",
 259             (long long)CountSourceItems,
 260             (long long)CountCopiedItems,
 261             (long long)CountRemovedItems);
 262         logstd("%.1f seconds %5d Kbytes/sec synced %5d Kbytes/sec scanned\n",
 263             (float)duration / (float)1000000,
 264             (long)((long)1000000 * (CountReadBytes + CountWriteBytes) / duration  / 1024.0),
 265             (long)((long)1000000 * CountSourceBytes / duration / 1024.0));
 266     }
 267     exit((i == 0) ? 0 : 1);
 268 }
 269
 270 static struct hlink *
 271 hltlookup(struct stat *stp)
 272 {
 273     struct hlink *hl;
 274     int n;
 275
 276     n = stp->st_ino & HLMASK;
 277
 278     for (hl = hltable[n]; hl; hl = hl->next)
 279         if (hl->ino == stp->st_ino)
 280               return hl;
 281
 282     return NULL;
 283 }
 284
 285 static struct hlink *
 286 hltadd(struct stat *stp, const char *path)
 287 {
 288     struct hlink *new;
 289     int n;
 290
 291     if (!(new = malloc(sizeof (struct hlink)))) {
 292         fprintf(stderr, "out of memory\n");
 293         exit(EXIT_FAILURE);
 294     }
 295
 296     /* initialize and link the new element into the table */
 297     new->ino = stp->st_ino;
 298     new->dino = 0;
 299     strncpy(new->name, path, 2048);
 300     new->nlinked = 1;
 301     new->prev = NULL;
 302     n = stp->st_ino & HLMASK;
 303     new->next = hltable[n];
 304     if (hltable[n])
 305         hltable[n]->prev = new;
 306     hltable[n] = new;
 307
 308     return new;
 309 }
 310
 311 static void
 312 hltdelete(struct hlink *hl)
 313 {
 314     if (hl->prev) {
 315         if (hl->next)
 316             hl->next->prev = hl->prev;
 317         hl->prev->next = hl->next;
 318     } else {
 319         if (hl->next)
 320             hl->next->prev = NULL;
 321
 322         hltable[hl->ino & HLMASK] = hl->next;
 323     }
 324
 325     free(hl);
 326 }
 327
 328 /*
 329  * If UseHLPath is defined check to see if the file in question is
 330  * the same as the source file, and if it is return a pointer to the
 331  * -H path based file for hardlinking.  Else return NULL.
 332  */
 333 static char *
 334 checkHLPath(struct stat *st1, const char *spath, const char *dpath)
 335 {
 336     struct stat sthl;
 337     char *hpath;
 338     int fd1;
 339     int fd2;
 340     int good;
 341
 342     asprintf(&hpath, "%s%s", UseHLPath, dpath + DstBaseLen);
 343
 344     /*
 345      * stat info matches ?
 346      */
 347     if (stat(hpath, &sthl) < 0 ||
 348         st1->st_size != sthl.st_size ||
 349         st1->st_uid != sthl.st_uid ||
 350         st1->st_gid != sthl.st_gid ||
 351         st1->st_mtime != sthl.st_mtime
 352     ) {
 353         free(hpath);
 354         return(NULL);
 355     }
 356
 357     /*
 358      * If ForceOpt is set we have to compare the files
 359      */
 360     if (ForceOpt) {
 361         fd1 = open(spath, O_RDONLY);
 362         fd2 = open(hpath, O_RDONLY);
 363         good = 0;
 364
 365         if (fd1 >= 0 && fd2 >= 0) {
 366             int n;
 367
 368             while ((n = read(fd1, IOBuf1, sizeof(IOBuf1))) > 0) {
 369                 if (read(fd2, IOBuf2, sizeof(IOBuf2)) != n)
 370                     break;
 371                 if (bcmp(IOBuf1, IOBuf2, n) != 0)
 372                     break;
 373             }
 374             if (n == 0)
 375                 good = 1;
 376         }
 377         if (fd1 >= 0)
 378             close(fd1);
 379         if (fd2 >= 0)
 380             close(fd2);
 381         if (good == 0) {
 382             free(hpath);
 383             hpath = NULL;
 384         }
 385     }
 386     return(hpath);
 387 }
 388
 389 int
 390 DoCopy(const char *spath, const char *dpath, dev_t sdevNo, dev_t ddevNo)
 391 {
 392     struct stat st1;
 393     struct stat st2;
 394     int r, mres, fres, st2Valid;
 395     struct hlink *hln;
 396     List list;
 397     u_int64_t size;
 398
 399     InitList(&list);
 400     r = mres = fres = st2Valid = 0;
 401     size = 0;
 402     hln = NULL;
 403
 404     if (lstat(spath, &st1) != 0)
 405         return(0);
 406     st2.st_mode = 0;    /* in case lstat fails */
 407     st2.st_flags = 0;   /* in case lstat fails */
 408     if (dpath && lstat(dpath, &st2) == 0)
 409         st2Valid = 1;
 410
 411     if (S_ISREG(st1.st_mode)) {
 412         size = st1.st_blocks * 512;
 413         if (st1.st_size % 512)
 414             size += st1.st_size % 512 - 512;
 415     }
 416
 417     /*
 418      * Handle hardlinks
 419      */
 420
 421     if (S_ISREG(st1.st_mode) && st1.st_nlink > 1 && dpath) {
 422         if ((hln = hltlookup(&st1)) != NULL) {
 423             hln->nlinked++;
 424
 425             if (st2Valid) {
 426                 if (st2.st_ino == hln->dino) {
 427                     /*
 428                      * hard link is already correct, nothing to do
 429                      */
 430                     if (VerboseOpt >= 3)
 431                         logstd("%-32s nochange\n", (dpath) ? dpath : spath);
 432                     if (hln->nlinked == st1.st_nlink)
 433                         hltdelete(hln);
 434                     CountSourceItems++;
 435                     return 0;
 436                 } else {
 437                     /*
 438                      * hard link is not correct, attempt to unlink it
 439                      */
 440                     if (unlink(dpath) < 0) {
 441                         logerr("%-32s hardlink: unable to unlink: %s\n",
 442                             ((dpath) ? dpath : spath), strerror(errno));
 443                         hltdelete(hln);
 444                         return (r + 1);
 445                     }
 446                 }
 447             }
 448
 449             if (xlink(hln->name, dpath, st1.st_flags) < 0) {
 450                 int tryrelink = (errno == EMLINK);
 451                 logerr("%-32s hardlink: unable to link to %s: %s\n",
 452                     (dpath ? dpath : spath), hln->name, strerror(errno)
 453                 );
 454                 hltdelete(hln);
 455                 hln = NULL;
 456                 if (tryrelink) {
 457                     logerr("%-20s hardlink: will attempt to copy normally\n");
 458                     goto relink;
 459                 }
 460                 ++r;
 461             } else {
 462                 if (hln->nlinked == st1.st_nlink) {
 463                     hltdelete(hln);
 464                     hln = NULL;
 465                 }
 466                 if (r == 0) {
 467                     if (VerboseOpt) {
 468                         logstd("%-32s hardlink: %s\n",
 469                             (dpath ? dpath : spath),
 470                             (st2Valid ? "relinked" : "linked")
 471                         );
 472                     }
 473                     CountSourceItems++;
 474                     CountCopiedItems++;
 475                     return 0;
 476                 }
 477             }
 478         } else {
 479             /*
 480              * first instance of hardlink must be copied normally
 481              */
 482 relink:
 483             hln = hltadd(&st1, dpath);
 484         }
 485     }
 486
 487     /*
 488      * Do we need to copy the file/dir/link/whatever?  Early termination
 489      * if we do not.  Always redo links.  Directories are always traversed
 490      * except when the FSMID options are used.
 491      *
 492      * NOTE: st2Valid is true only if dpath != NULL *and* dpath stats good.
 493      */
 494
 495     if (
 496         st2Valid &&
 497         st1.st_mode == st2.st_mode &&
 498         st1.st_flags == st2.st_flags
 499     ) {
 500         if (S_ISLNK(st1.st_mode) || S_ISDIR(st1.st_mode)) {
 501             /*
 502              * If FSMID tracking is turned on we can avoid recursing through
 503              * an entire directory subtree if the FSMID matches.
 504              */
 505 #ifdef _ST_FSMID_PRESENT_
 506             if (ForceOpt == 0 &&
 507                 (UseFSMIDOpt && (fres = fsmid_check(st1.st_fsmid, dpath)) == 0)
 508             ) {
 509                 if (VerboseOpt >= 3) {
 510                     if (UseFSMIDOpt)
 511                         logstd("%-32s fsmid-nochange\n", (dpath ? dpath : spath));
 512                     else
 513                         logstd("%-32s nochange\n", (dpath ? dpath : spath));
 514                 }
 515                 return(0);
 516             }
 517 #endif
 518         } else {
 519             if (ForceOpt == 0 &&
 520                 st1.st_size == st2.st_size &&
 521                 st1.st_uid == st2.st_uid &&
 522                 st1.st_gid == st2.st_gid &&
 523                 st1.st_mtime == st2.st_mtime
 524                 && (UseMD5Opt == 0 || (mres = md5_check(spath, dpath)) == 0)
 525 #ifdef _ST_FSMID_PRESENT_
 526                 && (UseFSMIDOpt == 0 || (fres = fsmid_check(st1.st_fsmid, dpath)) == 0)
 527 #endif
 528             ) {
 529                 if (hln)
 530                     hln->dino = st2.st_ino;
 531                 if (VerboseOpt >= 3) {
 532                     if (UseMD5Opt)
 533                         logstd("%-32s md5-nochange\n", (dpath ? dpath : spath));
 534                     else if (UseFSMIDOpt)
 535                         logstd("%-32s fsmid-nochange\n", (dpath ? dpath : spath));
 536                     else
 537                         logstd("%-32s nochange\n", (dpath ? dpath : spath));
 538                 }
 539                 CountSourceBytes += size;
 540                 CountSourceItems++;
 541
 542                 return(0);
 543             }
 544         }
 545     }
 546     if (st2Valid && !S_ISDIR(st1.st_mode) && S_ISDIR(st2.st_mode)) {
 547         if (SafetyOpt) {
 548             logerr("%-32s SAFETY - refusing to copy file over directory\n",
 549                 (dpath ? dpath : spath)
 550             );
 551             ++r;                /* XXX */
 552             return(0);  /* continue with the cpdup anyway */
 553         }
 554         if (QuietOpt == 0 || AskConfirmation) {
 555             logstd("%-32s WARNING: non-directory source will blow away\n"
 556                    "%-32s preexisting dest directory, continuing anyway!\n",
 557                    ((dpath) ? dpath : spath), "");
 558         }
 559         if (dpath)
 560             RemoveRecur(dpath, ddevNo);
 561     }
 562
 563     /*
 564      * The various comparisons failed, copy it.
 565      */
 566     if (S_ISDIR(st1.st_mode)) {
 567         DIR *dir;
 568
 569         if (fres < 0)
 570             logerr("%-32s/ fsmid-CHECK-FAILED\n", (dpath) ? dpath : spath);
 571         if ((dir = opendir(spath)) != NULL) {
 572             struct dirent *den;
 573             int noLoop = 0;
 574
 575             if (dpath) {
 576                 if (S_ISDIR(st2.st_mode) == 0) {
 577                     remove(dpath);
 578                     if (mkdir(dpath, st1.st_mode | 0700) != 0) {
 579                         logerr("%s: mkdir failed: %s\n",
 580                             (dpath ? dpath : spath), strerror(errno));
 581                         r = 1;
 582                         noLoop = 1;
 583                     }
 584                     /*
 585                      * Matt: why don't you check error codes here?
 586                      */
 587                     lstat(dpath, &st2);
 588                     chown(dpath, st1.st_uid, st1.st_gid);
 589                     CountCopiedItems++;
 590                 } else {
 591                     /*
 592                      * Directory must be scanable by root for cpdup to
 593                      * work.  We'll fix it later if the directory isn't
 594                      * supposed to be readable ( which is why we fixup
 595                      * st2.st_mode to match what we did ).
 596                      */
 597                     if ((st2.st_mode & 0700) != 0700) {
 598                         chmod(dpath, st2.st_mode | 0700);
 599                         st2.st_mode |= 0700;
 600                     }
 601                     if (VerboseOpt >= 2)
 602                         logstd("%s\n", dpath ? dpath : spath);
 603                 }
 604             }
 605
 606             if ((int)sdevNo >= 0 && st1.st_dev != sdevNo) {
 607                 noLoop = 1;
 608             } else {
 609                 sdevNo = st1.st_dev;
 610             }
 611
 612             if ((int)ddevNo >= 0 && st2.st_dev != ddevNo) {
 613                 noLoop = 1;
 614             } else {
 615                 ddevNo = st2.st_dev;
 616             }
 617
 618             /*
 619              * scan .cpignore file for files/directories
 620              * to ignore.
 621              */
 622
 623             if (UseCpFile) {
 624                 FILE *fi;
 625                 char buf[8192];
 626                 char *fpath;
 627
 628                 if (UseCpFile[0] == '/') {
 629                     fpath = mprintf("%s", UseCpFile);
 630                 } else {
 631                     fpath = mprintf("%s/%s", spath, UseCpFile);
 632                 }
 633                 AddList(&list, strrchr(fpath, '/') + 1, 1);
 634                 if ((fi = fopen(fpath, "r")) != NULL) {
 635                     while (fgets(buf, sizeof(buf), fi) != NULL) {
 636                         int l = strlen(buf);
 637                         CountReadBytes += l;
 638                         if (l && buf[l-1] == '\n')
 639                             buf[--l] = 0;
 640                         if (buf[0] && buf[0] != '#')
 641                             AddList(&list, buf, 1);
 642                     }
 643                     fclose(fi);
 644                 }
 645                 free(fpath);
 646             }
 647
 648             /*
 649              * Automatically exclude MD5CacheFile that we create on the
 650              * source from the copy to the destination.
 651              *
 652              * Automatically exclude a FSMIDCacheFile on the source that
 653              * would otherwise overwrite the one we maintain on the target.
 654              */
 655             if (UseMD5Opt)
 656                 AddList(&list, MD5CacheFile, 1);
 657             if (UseFSMIDOpt)
 658                 AddList(&list, FSMIDCacheFile, 1);
 659
 660             while (noLoop == 0 && (den = readdir(dir)) != NULL) {
 661                 /*
 662                  * ignore . and ..
 663                  */
 664                 char *nspath;
 665                 char *ndpath = NULL;
 666
 667                 if (strcmp(den->d_name, ".") == 0 ||
 668                     strcmp(den->d_name, "..") == 0
 669                 ) {
 670                     continue;
 671                 }
 672                 /*
 673                  * ignore if on .cpignore list
 674                  */
 675                 if (AddList(&list, den->d_name, 0) == 1) {
 676                     continue;
 677                 }
 678                 nspath = mprintf("%s/%s", spath, den->d_name);
 679                 if (dpath)
 680                     ndpath = mprintf("%s/%s", dpath, den->d_name);
 681                 r += DoCopy(
 682                     nspath,
 683                     ndpath,
 684                     sdevNo,
 685                     ddevNo
 686                 );
 687                 free(nspath);
 688                 if (ndpath)
 689                     free(ndpath);
 690             }
 691
 692             closedir(dir);
 693
 694             /*
 695              * Remove files/directories from destination that do not appear
 696              * in the source.
 697              */
 698             if (dpath && (dir = opendir(dpath)) != NULL) {
 699                 while (noLoop == 0 && (den = readdir(dir)) != NULL) {
 700                     /*
 701                      * ignore . or ..
 702                      */
 703                     if (strcmp(den->d_name, ".") == 0 ||
 704                         strcmp(den->d_name, "..") == 0
 705                     ) {
 706                         continue;
 707                     }
 708                     /*
 709                      * If object does not exist in source or .cpignore
 710                      * then recursively remove it.
 711                      */
 712                     if (AddList(&list, den->d_name, 3) == 3) {
 713                         char *ndpath;
 714
 715                         ndpath = mprintf("%s/%s", dpath, den->d_name);
 716                         RemoveRecur(ndpath, ddevNo);
 717                         free(ndpath);
 718                     }
 719                 }
 720                 closedir(dir);
 721             }
 722
 723             if (dpath) {
 724                 if (ForceOpt ||
 725                     st2Valid == 0 ||
 726                     st1.st_uid != st2.st_uid ||
 727                     st1.st_gid != st2.st_gid
 728                 ) {
 729                     chown(dpath, st1.st_uid, st1.st_gid);
 730                 }
 731                 if (st2Valid == 0 || st1.st_mode != st2.st_mode) {
 732                     chmod(dpath, st1.st_mode);
 733                 }
 734                 if (st2Valid == 0 || st1.st_flags != st2.st_flags) {
 735                     chflags(dpath, st1.st_flags);
 736                 }
 737             }
 738         }
 739     } else if (dpath == NULL) {
 740         /*
 741          * If dpath is NULL, we are just updating the MD5
 742          */
 743         if (UseMD5Opt && S_ISREG(st1.st_mode)) {
 744             mres = md5_check(spath, NULL);
 745
 746             if (VerboseOpt > 1) {
 747                 if (mres < 0)
 748                     logstd("%-32s md5-update\n", (dpath) ? dpath : spath);
 749                 else
 750                     logstd("%-32s md5-ok\n", (dpath) ? dpath : spath);
 751             } else if (!QuietOpt && mres < 0) {
 752                 logstd("%-32s md5-update\n", (dpath) ? dpath : spath);
 753             }
 754         }
 755     } else if (S_ISREG(st1.st_mode)) {
 756         char *path;
 757         char *hpath;
 758         int fd1;
 759         int fd2;
 760
 761         path = mprintf("%s.tmp", dpath);
 762
 763         /*
 764          * Handle check failure message.
 765          */
 766         if (mres < 0)
 767             logerr("%-32s md5-CHECK-FAILED\n", (dpath) ? dpath : spath);
 768         else if (fres < 0)
 769             logerr("%-32s fsmid-CHECK-FAILED\n", (dpath) ? dpath : spath);
 770
 771         /*
 772          * Not quite ready to do the copy yet.  If UseHLPath is defined,
 773          * see if we can hardlink instead.
 774          */
 775
 776         if (UseHLPath && (hpath = checkHLPath(&st1, spath, dpath)) != NULL) {
 777                 if (link(hpath, dpath) == 0) {
 778                         if (VerboseOpt) {
 779                             logstd("%-32s hardlinked(-H)\n",
 780                                    (dpath ? dpath : spath));
 781                         }
 782                         free(hpath);
 783                         goto skip_copy;
 784                 }
 785                 /*
 786                  * Shucks, we may have hit a filesystem hard linking limit,
 787                  * we have to copy instead.
 788                  */
 789                 free(hpath);
 790         }
 791
 792         if ((fd1 = open(spath, O_RDONLY)) >= 0) {
 793             if ((fd2 = open(path, O_WRONLY|O_CREAT|O_EXCL, 0600)) < 0) {
 794                 /*
 795                  * There could be a .tmp file from a previously interrupted
 796                  * run, delete and retry.  Fail if we still can't get at it.
 797                  */
 798                 chflags(path, 0);
 799                 remove(path);
 800                 fd2 = open(path, O_WRONLY|O_CREAT|O_EXCL|O_TRUNC, 0600);
 801             }
 802             if (fd2 >= 0) {
 803                 const char *op;
 804                 int n;
 805
 806                 /*
 807                  * Matt: What about holes?
 808                  */
 809                 op = "read";
 810                 while ((n = read(fd1, IOBuf1, sizeof(IOBuf1))) > 0) {
 811                     op = "write";
 812                     if (write(fd2, IOBuf1, n) != n)
 813                         break;
 814                     op = "read";
 815                 }
 816                 close(fd2);
 817                 if (n == 0) {
 818                     struct timeval tv[2];
 819
 820                     bzero(tv, sizeof(tv));
 821                     tv[0].tv_sec = st1.st_mtime;
 822                     tv[1].tv_sec = st1.st_mtime;
 823
 824                     utimes(path, tv);
 825                     chown(path, st1.st_uid, st1.st_gid);
 826                     chmod(path, st1.st_mode);
 827                     if (xrename(path, dpath, st2.st_flags) != 0) {
 828                         logerr("%-32s rename-after-copy failed: %s\n",
 829                             (dpath ? dpath : spath), strerror(errno)
 830                         );
 831                         ++r;
 832                     } else {
 833                         if (VerboseOpt)
 834                             logstd("%-32s copy-ok\n", (dpath ? dpath : spath));
 835                         if (st1.st_flags)
 836                             chflags(dpath, st1.st_flags);
 837                     }
 838                     CountReadBytes += size;
 839                     CountWriteBytes += size;
 840                     CountSourceBytes += size;
 841                     CountSourceItems++;
 842                     CountCopiedItems++;
 843                 } else {
 844                     logerr("%-32s %s failed: %s\n",
 845                         (dpath ? dpath : spath), op, strerror(errno)
 846                     );
 847                     remove(path);
 848                     ++r;
 849                 }
 850             } else {
 851                 logerr("%-32s create (uid %d, euid %d) failed: %s\n",
 852                     (dpath ? dpath : spath), getuid(), geteuid(),
 853                     strerror(errno)
 854                 );
 855                 ++r;
 856             }
 857             close(fd1);
 858         } else {
 859             logerr("%-32s copy: open failed: %s\n",
 860                 (dpath ? dpath : spath),
 861                 strerror(errno)
 862             );
 863             ++r;
 864         }
 865 skip_copy:
 866         free(path);
 867
 868         if (hln) {
 869             if (!r && stat(dpath, &st2) == 0)
 870                 hln->dino = st2.st_ino;
 871             else
 872                 hltdelete(hln);
 873         }
 874     } else if (S_ISLNK(st1.st_mode)) {
 875         char link1[1024];
 876         char link2[1024];
 877         char path[2048];
 878         int n1;
 879         int n2;
 880
 881         snprintf(path, sizeof(path), "%s.tmp", dpath);
 882         n1 = readlink(spath, link1, sizeof(link1) - 1);
 883         n2 = readlink(dpath, link2, sizeof(link2) - 1);
 884         if (n1 >= 0) {
 885             if (ForceOpt || n1 != n2 || bcmp(link1, link2, n1) != 0) {
 886                 umask(~st1.st_mode);
 887                 remove(path);
 888                 link1[n1] = 0;
 889                 if (symlink(link1, path) < 0) {
 890                       logerr("%-32s symlink (%s->%s) failed: %s\n",
 891                           (dpath ? dpath : spath), link1, path,
 892                           strerror(errno)
 893                       );
 894                       ++r;
 895                 } else {
 896                     lchown(path, st1.st_uid, st1.st_gid);
 897                     /*
 898                      * there is no lchmod() or lchflags(), we
 899                      * cannot chmod or chflags a softlink.
 900                      */
 901                     if (xrename(path, dpath, st2.st_flags) != 0) {
 902                         logerr("%-32s rename softlink (%s->%s) failed: %s\n",
 903                             (dpath ? dpath : spath),
 904                             path, dpath, strerror(errno));
 905                     } else if (VerboseOpt) {
 906                         logstd("%-32s softlink-ok\n", (dpath ? dpath : spath));
 907                     }
 908                     umask(000);
 909                     CountWriteBytes += n1;
 910                     CountCopiedItems++;
 911                 }
 912             } else {
 913                 if (VerboseOpt >= 3)
 914                     logstd("%-32s nochange\n", (dpath ? dpath : spath));
 915             }
 916             CountSourceBytes += n1;
 917             CountReadBytes += n1;
 918             if (n2 > 0) CountReadBytes += n2;
 919             CountSourceItems++;
 920         } else {
 921             r = 1;
 922             logerr("%-32s softlink-failed\n", (dpath ? dpath : spath));
 923         }
 924     } else if (S_ISCHR(st1.st_mode) || S_ISBLK(st1.st_mode)) {
 925         char path[2048];
 926
 927         if (ForceOpt ||
 928             st2Valid == 0 ||
 929             st1.st_mode != st2.st_mode ||
 930             st1.st_rdev != st2.st_rdev ||
 931             st1.st_uid != st2.st_uid ||
 932             st1.st_gid != st2.st_gid
 933         ) {
 934             snprintf(path, sizeof(path), "%s.tmp", dpath);
 935
 936             remove(path);
 937             if (mknod(path, st1.st_mode, st1.st_rdev) == 0) {
 938                 chmod(path, st1.st_mode);
 939                 chown(path, st1.st_uid, st1.st_gid);
 940                 remove(dpath);
 941                 if (xrename(path, dpath, st2.st_flags) != 0) {
 942                     logerr("%-32s dev-rename-after-create failed: %s\n",
 943                         (dpath ? dpath : spath),
 944                         strerror(errno)
 945                     );
 946                 } else if (VerboseOpt) {
 947                     logstd("%-32s dev-ok\n", (dpath ? dpath : spath));
 948                 }
 949                 CountCopiedItems++;
 950             } else {
 951                 r = 1;
 952                 logerr("%-32s dev failed: %s\n",
 953                     (dpath ? dpath : spath), strerror(errno)
 954                 );
 955             }
 956         } else {
 957             if (VerboseOpt >= 3)
 958                 logstd("%-32s nochange\n", (dpath ? dpath : spath));
 959         }
 960         CountSourceItems++;
 961     }
 962     ResetList(&list);
 963     return (r);
 964 }
 965
 966 /*
 967  * RemoveRecur()
 968  */
 969
 970 void
 971 RemoveRecur(const char *dpath, dev_t devNo)
 972 {
 973     struct stat st;
 974
 975     if (lstat(dpath, &st) == 0) {
 976         if ((int)devNo < 0)
 977             devNo = st.st_dev;
 978         if (st.st_dev == devNo) {
 979             if (S_ISDIR(st.st_mode)) {
 980                 DIR *dir;
 981
 982                 if ((dir = opendir(dpath)) != NULL) {
 983                     struct dirent *den;
 984                     while ((den = readdir(dir)) != NULL) {
 985                         char *ndpath;
 986
 987                         if (strcmp(den->d_name, ".") == 0)
 988                             continue;
 989                         if (strcmp(den->d_name, "..") == 0)
 990                             continue;
 991                         ndpath = mprintf("%s/%s", dpath, den->d_name);
 992                         RemoveRecur(ndpath, devNo);
 993                         free(ndpath);
 994                     }
 995                     closedir(dir);
 996                 }
 997                 if (AskConfirmation && NoRemoveOpt == 0) {
 998                     if (YesNo(dpath)) {
 999                         if (rmdir(dpath) < 0) {
1000                             logerr("%-32s rmdir failed: %s\n",
1001                                 dpath, strerror(errno)
1002                             );
1003                         }
1004                         CountRemovedItems++;
1005                     }
1006                 } else {
1007                     if (NoRemoveOpt) {
1008                         if (VerboseOpt)
1009                             logstd("%-32s not-removed\n", dpath);
1010                     } else if (rmdir(dpath) == 0) {
1011                         if (VerboseOpt)
1012                             logstd("%-32s rmdir-ok\n", dpath);
1013                         CountRemovedItems++;
1014                     } else {
1015                         logerr("%-32s rmdir failed: %s\n",
1016                             dpath, strerror(errno)
1017                         );
1018                     }
1019                 }
1020             } else {
1021                 if (AskConfirmation && NoRemoveOpt == 0) {
1022                     if (YesNo(dpath)) {
1023                         if (remove(dpath) < 0) {
1024                             logerr("%-32s remove failed: %s\n",
1025                                 dpath, strerror(errno)
1026                             );
1027                         }
1028                         CountRemovedItems++;
1029                     }
1030                 } else {
1031                     if (NoRemoveOpt) {
1032                         if (VerboseOpt)
1033                             logstd("%-32s not-removed\n", dpath);
1034                     } else if (remove(dpath) == 0) {
1035                         if (VerboseOpt)
1036                             logstd("%-32s remove-ok\n", dpath);
1037                         CountRemovedItems++;
1038                     } else {
1039                         logerr("%-32s remove failed: %s\n",
1040                             dpath, strerror(errno)
1041                         );
1042                     }
1043                 }
1044             }
1045         }
1046     }
1047 }
1048
1049 void
1050 InitList(List *list)
1051 {
1052     bzero(list, sizeof(List));
1053     list->li_Node.no_Next = &list->li_Node;
1054 }
1055
1056 void
1057 ResetList(List *list)
1058 {
1059     Node *node;
1060
1061     while ((node = list->li_Node.no_Next) != &list->li_Node) {
1062         list->li_Node.no_Next = node->no_Next;
1063         free(node);
1064     }
1065     InitList(list);
1066 }
1067
1068 int
1069 AddList(List *list, const char *name, int n)
1070 {
1071     Node *node;
1072     int hv;
1073
1074     hv = shash(name);
1075
1076     /*
1077      * Scan against wildcards.  Only a node value of 1 can be a wildcard
1078      * ( usually scanned from .cpignore )
1079      */
1080
1081     for (node = list->li_Hash[0]; node; node = node->no_HNext) {
1082         if (strcmp(name, node->no_Name) == 0 ||
1083             (n != 1 && node->no_Value == 1 && WildCmp(node->no_Name, name) == 0)
1084         ) {
1085             return(node->no_Value);
1086         }
1087     }
1088
1089     /*
1090      * Look for exact match
1091      */
1092
1093     for (node = list->li_Hash[hv]; node; node = node->no_HNext) {
1094         if (strcmp(name, node->no_Name) == 0) {
1095             return(node->no_Value);
1096         }
1097     }
1098     node = malloc(sizeof(Node) + strlen(name) + 1);
1099     if (node == NULL) {
1100         fprintf(stderr, "out of memory\n");
1101         exit(EXIT_FAILURE);
1102     }
1103
1104     node->no_Next = list->li_Node.no_Next;
1105     list->li_Node.no_Next = node;
1106
1107     node->no_HNext = list->li_Hash[hv];
1108     list->li_Hash[hv] = node;
1109
1110     strcpy(node->no_Name, name);
1111     node->no_Value = n;
1112
1113     return(n);
1114 }
1115
1116 static int
1117 shash(const char *s)
1118 {
1119     int hv;
1120
1121     hv = 0xA4FB3255;
1122
1123     while (*s) {
1124         if (*s == '*' || *s == '?' ||
1125             *s == '{' || *s == '}' ||
1126             *s == '[' || *s == ']' ||
1127             *s == '|'
1128         ) {
1129             return(0);
1130         }
1131         hv = (hv << 5) ^ *s ^ (hv >> 23);
1132         ++s;
1133     }
1134     return(((hv >> 16) ^ hv) & HMASK);
1135 }
1136
1137 /*
1138  * WildCmp() - compare wild string to sane string
1139  *
1140  *      Return 0 on success, -1 on failure.
1141  */
1142
1143 int
1144 WildCmp(const char *w, const char *s)
1145 {
1146     /*
1147      * skip fixed portion
1148      */
1149
1150     for (;;) {
1151         switch(*w) {
1152         case '*':
1153             if (w[1] == 0)      /* optimize wild* case */
1154                 return(0);
1155             {
1156                 int i;
1157                 int l = strlen(s);
1158
1159                 for (i = 0; i <= l; ++i) {
1160                     if (WildCmp(w + 1, s + i) == 0)
1161                         return(0);
1162                 }
1163             }
1164             return(-1);
1165         case '?':
1166             if (*s == 0)
1167                 return(-1);
1168             ++w;
1169             ++s;
1170             break;
1171         default:
1172             if (*w != *s)
1173                 return(-1);
1174             if (*w == 0)        /* terminator */
1175                 return(0);
1176             ++w;
1177             ++s;
1178             break;
1179         }
1180     }
1181     /* not reached */
1182     return(-1);
1183 }
1184
1185 int
1186 YesNo(const char *path)
1187 {
1188     int ch, first;
1189
1190     fprintf(stderr, "remove %s (Yes/No) [No]? ", path);
1191     fflush(stderr);
1192
1193     first = ch = getchar();
1194     while (ch != '\n' && ch != EOF)
1195         ch = getchar();
1196     return ((first == 'y' || first == 'Y'));
1197 }
1198
1199 /*
1200  * xrename() - rename with override
1201  *
1202  *      If the rename fails, attempt to override st_flags on the
1203  *      destination and rename again.  If that fails too, try to
1204  *      set the flags back the way they were and give up.
1205  */
1206
1207 static int
1208 xrename(const char *src, const char *dst, u_long flags)
1209 {
1210     int r;
1211
1212     r = 0;
1213
1214     if ((r = rename(src, dst)) < 0) {
1215         chflags(dst, 0);
1216         if ((r = rename(src, dst)) < 0)
1217                 chflags(dst, flags);
1218     }
1219     return(r);
1220 }
1221
1222 static int
1223 xlink(const char *src, const char *dst, u_long flags)
1224 {
1225     int r, e;
1226
1227     r = 0;
1228
1229     if ((r = link(src, dst)) < 0) {
1230         chflags(src, 0);
1231         r = link(src, dst);
1232         e = errno;
1233         chflags(src, flags);
1234         errno = e;
1235     }
1236     return(r);
1237 }
1238