xref: /dflybsd-src/bin/cpdup/cpdup.c (revision 9d509a69ab2b7b806df8f2de570667d384d4d4f1)
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.6 2004/07/22 13:09:02 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 static struct hlink *hltlookup(struct stat *);
96 static struct hlink *hltadd(struct stat *, const char *);
97 static int shash(const char *s);
98 static void hltdelete(struct hlink *);
99 int YesNo(const char *path);
100 static int xrename(const char *src, const char *dst, u_long flags);
101 static int xlink(const char *src, const char *dst, u_long flags);
102 int WildCmp(const char *s1, const char *s2);
103 static MD5Node *md5_lookup(const char *sfile);
104 static int md5_check(const char *spath, const char *dpath);
105 static void md5_flush(void);
106 static void md5_cache(const char *spath, int sdirlen);
107 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 
1362