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