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