1: /*
2: * Utility routines used in rsync.
3: *
4: * Copyright (C) 1996-2000 Andrew Tridgell
5: * Copyright (C) 1996 Paul Mackerras
6: * Copyright (C) 2001, 2002 Martin Pool <mbp@samba.org>
7: * Copyright (C) 2003-2009 Wayne Davison
8: *
9: * This program is free software; you can redistribute it and/or modify
10: * it under the terms of the GNU General Public License as published by
11: * the Free Software Foundation; either version 3 of the License, or
12: * (at your option) any later version.
13: *
14: * This program is distributed in the hope that it will be useful,
15: * but WITHOUT ANY WARRANTY; without even the implied warranty of
16: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17: * GNU General Public License for more details.
18: *
19: * You should have received a copy of the GNU General Public License along
20: * with this program; if not, visit the http://fsf.org website.
21: */
22:
23: #include "rsync.h"
24: #include "ifuncs.h"
25:
26: extern int verbose;
27: extern int module_id;
28: extern int modify_window;
29: extern int relative_paths;
30: extern int preserve_times;
31: extern int human_readable;
32: extern int preserve_xattrs;
33: extern char *module_dir;
34: extern unsigned int module_dirlen;
35: extern mode_t orig_umask;
36: extern char *partial_dir;
37: extern struct filter_list_struct daemon_filter_list;
38:
39: int sanitize_paths = 0;
40:
41: char curr_dir[MAXPATHLEN];
42: unsigned int curr_dir_len;
43: int curr_dir_depth; /* This is only set for a sanitizing daemon. */
44:
45: /* Set a fd into nonblocking mode. */
46: void set_nonblocking(int fd)
47: {
48: int val;
49:
50: if ((val = fcntl(fd, F_GETFL)) == -1)
51: return;
52: if (!(val & NONBLOCK_FLAG)) {
53: val |= NONBLOCK_FLAG;
54: fcntl(fd, F_SETFL, val);
55: }
56: }
57:
58: /* Set a fd into blocking mode. */
59: void set_blocking(int fd)
60: {
61: int val;
62:
63: if ((val = fcntl(fd, F_GETFL)) == -1)
64: return;
65: if (val & NONBLOCK_FLAG) {
66: val &= ~NONBLOCK_FLAG;
67: fcntl(fd, F_SETFL, val);
68: }
69: }
70:
71: /**
72: * Create a file descriptor pair - like pipe() but use socketpair if
73: * possible (because of blocking issues on pipes).
74: *
75: * Always set non-blocking.
76: */
77: int fd_pair(int fd[2])
78: {
79: int ret;
80:
81: #ifdef HAVE_SOCKETPAIR
82: ret = socketpair(AF_UNIX, SOCK_STREAM, 0, fd);
83: #else
84: ret = pipe(fd);
85: #endif
86:
87: if (ret == 0) {
88: set_nonblocking(fd[0]);
89: set_nonblocking(fd[1]);
90: }
91:
92: return ret;
93: }
94:
95: void print_child_argv(const char *prefix, char **cmd)
96: {
97: rprintf(FCLIENT, "%s ", prefix);
98: for (; *cmd; cmd++) {
99: /* Look for characters that ought to be quoted. This
100: * is not a great quoting algorithm, but it's
101: * sufficient for a log message. */
102: if (strspn(*cmd, "abcdefghijklmnopqrstuvwxyz"
103: "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
104: "0123456789"
105: ",.-_=+@/") != strlen(*cmd)) {
106: rprintf(FCLIENT, "\"%s\" ", *cmd);
107: } else {
108: rprintf(FCLIENT, "%s ", *cmd);
109: }
110: }
111: rprintf(FCLIENT, "\n");
112: }
113:
114: NORETURN void out_of_memory(const char *str)
115: {
116: rprintf(FERROR, "ERROR: out of memory in %s [%s]\n", str, who_am_i());
117: exit_cleanup(RERR_MALLOC);
118: }
119:
120: NORETURN void overflow_exit(const char *str)
121: {
122: rprintf(FERROR, "ERROR: buffer overflow in %s [%s]\n", str, who_am_i());
123: exit_cleanup(RERR_MALLOC);
124: }
125:
126: /* This returns 0 for success, 1 for a symlink if symlink time-setting
127: * is not possible, or -1 for any other error. */
128: int set_modtime(const char *fname, time_t modtime, mode_t mode)
129: {
130: static int switch_step = 0;
131:
132: if (verbose > 2) {
133: rprintf(FINFO, "set modtime of %s to (%ld) %s",
134: fname, (long)modtime,
135: asctime(localtime(&modtime)));
136: }
137:
138: switch (switch_step) {
139: #ifdef HAVE_UTIMENSAT
140: #include "case_N.h"
141: if (do_utimensat(fname, modtime, 0) == 0)
142: break;
143: if (errno != ENOSYS)
144: return -1;
145: switch_step++;
146: /* FALLTHROUGH */
147: #endif
148:
149: #ifdef HAVE_LUTIMES
150: #include "case_N.h"
151: if (do_lutimes(fname, modtime, 0) == 0)
152: break;
153: if (errno != ENOSYS)
154: return -1;
155: switch_step++;
156: /* FALLTHROUGH */
157: #endif
158:
159: #include "case_N.h"
160: switch_step++;
161: if (preserve_times & PRESERVE_LINK_TIMES) {
162: preserve_times &= ~PRESERVE_LINK_TIMES;
163: if (S_ISLNK(mode))
164: return 1;
165: }
166: /* FALLTHROUGH */
167:
168: #include "case_N.h"
169: #ifdef HAVE_UTIMES
170: if (do_utimes(fname, modtime, 0) == 0)
171: break;
172: #else
173: if (do_utime(fname, modtime, 0) == 0)
174: break;
175: #endif
176:
177: return -1;
178: }
179:
180: return 0;
181: }
182:
183: /* This creates a new directory with default permissions. Since there
184: * might be some directory-default permissions affecting this, we can't
185: * force the permissions directly using the original umask and mkdir(). */
186: int mkdir_defmode(char *fname)
187: {
188: int ret;
189:
190: umask(orig_umask);
191: ret = do_mkdir(fname, ACCESSPERMS);
192: umask(0);
193:
194: return ret;
195: }
196:
197: /* Create any necessary directories in fname. Any missing directories are
198: * created with default permissions. */
199: int create_directory_path(char *fname)
200: {
201: char *p;
202: int ret = 0;
203:
204: while (*fname == '/')
205: fname++;
206: while (strncmp(fname, "./", 2) == 0)
207: fname += 2;
208:
209: umask(orig_umask);
210: p = fname;
211: while ((p = strchr(p,'/')) != NULL) {
212: *p = '\0';
213: if (do_mkdir(fname, ACCESSPERMS) < 0 && errno != EEXIST)
214: ret = -1;
215: *p++ = '/';
216: }
217: umask(0);
218:
219: return ret;
220: }
221:
222: /**
223: * Write @p len bytes at @p ptr to descriptor @p desc, retrying if
224: * interrupted.
225: *
226: * @retval len upon success
227: *
228: * @retval <0 write's (negative) error code
229: *
230: * Derived from GNU C's cccp.c.
231: */
232: int full_write(int desc, const char *ptr, size_t len)
233: {
234: int total_written;
235:
236: total_written = 0;
237: while (len > 0) {
238: int written = write(desc, ptr, len);
239: if (written < 0) {
240: if (errno == EINTR)
241: continue;
242: return written;
243: }
244: total_written += written;
245: ptr += written;
246: len -= written;
247: }
248: return total_written;
249: }
250:
251: /**
252: * Read @p len bytes at @p ptr from descriptor @p desc, retrying if
253: * interrupted.
254: *
255: * @retval >0 the actual number of bytes read
256: *
257: * @retval 0 for EOF
258: *
259: * @retval <0 for an error.
260: *
261: * Derived from GNU C's cccp.c. */
262: static int safe_read(int desc, char *ptr, size_t len)
263: {
264: int n_chars;
265:
266: if (len == 0)
267: return len;
268:
269: do {
270: n_chars = read(desc, ptr, len);
271: } while (n_chars < 0 && errno == EINTR);
272:
273: return n_chars;
274: }
275:
276: /* Copy a file. If ofd < 0, copy_file unlinks and opens the "dest" file.
277: * Otherwise, it just writes to and closes the provided file descriptor.
278: * In either case, if --xattrs are being preserved, the dest file will
279: * have its xattrs set from the source file.
280: *
281: * This is used in conjunction with the --temp-dir, --backup, and
282: * --copy-dest options. */
283: int copy_file(const char *source, const char *dest, int ofd,
284: mode_t mode, int create_bak_dir)
285: {
286: int ifd;
287: char buf[1024 * 8];
288: int len; /* Number of bytes read into `buf'. */
289:
290: if ((ifd = do_open(source, O_RDONLY, 0)) < 0) {
291: int save_errno = errno;
292: rsyserr(FERROR_XFER, errno, "open %s", full_fname(source));
293: errno = save_errno;
294: return -1;
295: }
296:
297: if (ofd < 0) {
298: if (robust_unlink(dest) && errno != ENOENT) {
299: int save_errno = errno;
300: rsyserr(FERROR_XFER, errno, "unlink %s", full_fname(dest));
301: errno = save_errno;
302: return -1;
303: }
304:
305: if ((ofd = do_open(dest, O_WRONLY | O_CREAT | O_TRUNC | O_EXCL, mode)) < 0) {
306: int save_errno = errno ? errno : EINVAL; /* 0 paranoia */
307: if (create_bak_dir && errno == ENOENT && make_bak_dir(dest) == 0) {
308: if ((ofd = do_open(dest, O_WRONLY | O_CREAT | O_TRUNC | O_EXCL, mode)) < 0)
309: save_errno = errno ? errno : save_errno;
310: else
311: save_errno = 0;
312: }
313: if (save_errno) {
314: rsyserr(FERROR_XFER, save_errno, "open %s", full_fname(dest));
315: close(ifd);
316: errno = save_errno;
317: return -1;
318: }
319: }
320: }
321:
322: while ((len = safe_read(ifd, buf, sizeof buf)) > 0) {
323: if (full_write(ofd, buf, len) < 0) {
324: int save_errno = errno;
325: rsyserr(FERROR_XFER, errno, "write %s", full_fname(dest));
326: close(ifd);
327: close(ofd);
328: errno = save_errno;
329: return -1;
330: }
331: }
332:
333: if (len < 0) {
334: int save_errno = errno;
335: rsyserr(FERROR_XFER, errno, "read %s", full_fname(source));
336: close(ifd);
337: close(ofd);
338: errno = save_errno;
339: return -1;
340: }
341:
342: if (close(ifd) < 0) {
343: rsyserr(FWARNING, errno, "close failed on %s",
344: full_fname(source));
345: }
346:
347: if (close(ofd) < 0) {
348: int save_errno = errno;
349: rsyserr(FERROR_XFER, errno, "close failed on %s",
350: full_fname(dest));
351: errno = save_errno;
352: return -1;
353: }
354:
355: #ifdef SUPPORT_XATTRS
356: if (preserve_xattrs)
357: copy_xattrs(source, dest);
358: #endif
359:
360: return 0;
361: }
362:
363: /* MAX_RENAMES should be 10**MAX_RENAMES_DIGITS */
364: #define MAX_RENAMES_DIGITS 3
365: #define MAX_RENAMES 1000
366:
367: /**
368: * Robust unlink: some OS'es (HPUX) refuse to unlink busy files, so
369: * rename to <path>/.rsyncNNN instead.
370: *
371: * Note that successive rsync runs will shuffle the filenames around a
372: * bit as long as the file is still busy; this is because this function
373: * does not know if the unlink call is due to a new file coming in, or
374: * --delete trying to remove old .rsyncNNN files, hence it renames it
375: * each time.
376: **/
377: int robust_unlink(const char *fname)
378: {
379: #ifndef ETXTBSY
380: return do_unlink(fname);
381: #else
382: static int counter = 1;
383: int rc, pos, start;
384: char path[MAXPATHLEN];
385:
386: rc = do_unlink(fname);
387: if (rc == 0 || errno != ETXTBSY)
388: return rc;
389:
390: if ((pos = strlcpy(path, fname, MAXPATHLEN)) >= MAXPATHLEN)
391: pos = MAXPATHLEN - 1;
392:
393: while (pos > 0 && path[pos-1] != '/')
394: pos--;
395: pos += strlcpy(path+pos, ".rsync", MAXPATHLEN-pos);
396:
397: if (pos > (MAXPATHLEN-MAX_RENAMES_DIGITS-1)) {
398: errno = ETXTBSY;
399: return -1;
400: }
401:
402: /* start where the last one left off to reduce chance of clashes */
403: start = counter;
404: do {
405: snprintf(&path[pos], MAX_RENAMES_DIGITS+1, "%03d", counter);
406: if (++counter >= MAX_RENAMES)
407: counter = 1;
408: } while ((rc = access(path, 0)) == 0 && counter != start);
409:
410: if (verbose > 0) {
411: rprintf(FWARNING, "renaming %s to %s because of text busy\n",
412: fname, path);
413: }
414:
415: /* maybe we should return rename()'s exit status? Nah. */
416: if (do_rename(fname, path) != 0) {
417: errno = ETXTBSY;
418: return -1;
419: }
420: return 0;
421: #endif
422: }
423:
424: /* Returns 0 on successful rename, 1 if we successfully copied the file
425: * across filesystems, -2 if copy_file() failed, and -1 on other errors.
426: * If partialptr is not NULL and we need to do a copy, copy the file into
427: * the active partial-dir instead of over the destination file. */
428: int robust_rename(const char *from, const char *to, const char *partialptr,
429: int mode)
430: {
431: int tries = 4;
432:
433: while (tries--) {
434: if (do_rename(from, to) == 0)
435: return 0;
436:
437: switch (errno) {
438: #ifdef ETXTBSY
439: case ETXTBSY:
440: if (robust_unlink(to) != 0) {
441: errno = ETXTBSY;
442: return -1;
443: }
444: errno = ETXTBSY;
445: break;
446: #endif
447: case EXDEV:
448: if (partialptr) {
449: if (!handle_partial_dir(partialptr,PDIR_CREATE))
450: return -2;
451: to = partialptr;
452: }
453: if (copy_file(from, to, -1, mode, 0) != 0)
454: return -2;
455: do_unlink(from);
456: return 1;
457: default:
458: return -1;
459: }
460: }
461: return -1;
462: }
463:
464: static pid_t all_pids[10];
465: static int num_pids;
466:
467: /** Fork and record the pid of the child. **/
468: pid_t do_fork(void)
469: {
470: pid_t newpid = fork();
471:
472: if (newpid != 0 && newpid != -1) {
473: all_pids[num_pids++] = newpid;
474: }
475: return newpid;
476: }
477:
478: /**
479: * Kill all children.
480: *
481: * @todo It would be kind of nice to make sure that they are actually
482: * all our children before we kill them, because their pids may have
483: * been recycled by some other process. Perhaps when we wait for a
484: * child, we should remove it from this array. Alternatively we could
485: * perhaps use process groups, but I think that would not work on
486: * ancient Unix versions that don't support them.
487: **/
488: void kill_all(int sig)
489: {
490: int i;
491:
492: for (i = 0; i < num_pids; i++) {
493: /* Let's just be a little careful where we
494: * point that gun, hey? See kill(2) for the
495: * magic caused by negative values. */
496: pid_t p = all_pids[i];
497:
498: if (p == getpid())
499: continue;
500: if (p <= 0)
501: continue;
502:
503: kill(p, sig);
504: }
505: }
506:
507: /** Turn a user name into a uid */
508: int name_to_uid(const char *name, uid_t *uid_p)
509: {
510: struct passwd *pass;
511: if (!name || !*name)
512: return 0;
513: if (!(pass = getpwnam(name)))
514: return 0;
515: *uid_p = pass->pw_uid;
516: return 1;
517: }
518:
519: /** Turn a group name into a gid */
520: int name_to_gid(const char *name, gid_t *gid_p)
521: {
522: struct group *grp;
523: if (!name || !*name)
524: return 0;
525: if (!(grp = getgrnam(name)))
526: return 0;
527: *gid_p = grp->gr_gid;
528: return 1;
529: }
530:
531: /** Lock a byte range in a open file */
532: int lock_range(int fd, int offset, int len)
533: {
534: struct flock lock;
535:
536: lock.l_type = F_WRLCK;
537: lock.l_whence = SEEK_SET;
538: lock.l_start = offset;
539: lock.l_len = len;
540: lock.l_pid = 0;
541:
542: return fcntl(fd,F_SETLK,&lock) == 0;
543: }
544:
545: #define ENSURE_MEMSPACE(buf, type, sz, req) \
546: if ((req) > sz && !(buf = realloc_array(buf, type, sz = MAX(sz * 2, req)))) \
547: out_of_memory("glob_expand")
548:
549: static inline void call_glob_match(const char *name, int len, int from_glob,
550: char *arg, int abpos, int fbpos);
551:
552: static struct glob_data {
553: char *arg_buf, *filt_buf, **argv;
554: int absize, fbsize, maxargs, argc;
555: } glob;
556:
557: static void glob_match(char *arg, int abpos, int fbpos)
558: {
559: int len;
560: char *slash;
561:
562: while (*arg == '.' && arg[1] == '/') {
563: if (fbpos < 0) {
564: ENSURE_MEMSPACE(glob.filt_buf, char, glob.fbsize, glob.absize);
565: memcpy(glob.filt_buf, glob.arg_buf, abpos + 1);
566: fbpos = abpos;
567: }
568: ENSURE_MEMSPACE(glob.arg_buf, char, glob.absize, abpos + 3);
569: glob.arg_buf[abpos++] = *arg++;
570: glob.arg_buf[abpos++] = *arg++;
571: glob.arg_buf[abpos] = '\0';
572: }
573: if ((slash = strchr(arg, '/')) != NULL) {
574: *slash = '\0';
575: len = slash - arg;
576: } else
577: len = strlen(arg);
578: if (strpbrk(arg, "*?[")) {
579: struct dirent *di;
580: DIR *d;
581:
582: if (!(d = opendir(abpos ? glob.arg_buf : ".")))
583: return;
584: while ((di = readdir(d)) != NULL) {
585: char *dname = d_name(di);
586: if (dname[0] == '.' && (dname[1] == '\0'
587: || (dname[1] == '.' && dname[2] == '\0')))
588: continue;
589: if (!wildmatch(arg, dname))
590: continue;
591: call_glob_match(dname, strlen(dname), 1,
592: slash ? arg + len + 1 : NULL,
593: abpos, fbpos);
594: }
595: closedir(d);
596: } else {
597: call_glob_match(arg, len, 0,
598: slash ? arg + len + 1 : NULL,
599: abpos, fbpos);
600: }
601: if (slash)
602: *slash = '/';
603: }
604:
605: static inline void call_glob_match(const char *name, int len, int from_glob,
606: char *arg, int abpos, int fbpos)
607: {
608: char *use_buf;
609:
610: ENSURE_MEMSPACE(glob.arg_buf, char, glob.absize, abpos + len + 2);
611: memcpy(glob.arg_buf + abpos, name, len);
612: abpos += len;
613: glob.arg_buf[abpos] = '\0';
614:
615: if (fbpos >= 0) {
616: ENSURE_MEMSPACE(glob.filt_buf, char, glob.fbsize, fbpos + len + 2);
617: memcpy(glob.filt_buf + fbpos, name, len);
618: fbpos += len;
619: glob.filt_buf[fbpos] = '\0';
620: use_buf = glob.filt_buf;
621: } else
622: use_buf = glob.arg_buf;
623:
624: if (from_glob || (arg && len)) {
625: STRUCT_STAT st;
626: int is_dir;
627:
628: if (do_stat(glob.arg_buf, &st) != 0)
629: return;
630: is_dir = S_ISDIR(st.st_mode) != 0;
631: if (arg && !is_dir)
632: return;
633:
634: if (daemon_filter_list.head
635: && check_filter(&daemon_filter_list, FLOG, use_buf, is_dir) < 0)
636: return;
637: }
638:
639: if (arg) {
640: glob.arg_buf[abpos++] = '/';
641: glob.arg_buf[abpos] = '\0';
642: if (fbpos >= 0) {
643: glob.filt_buf[fbpos++] = '/';
644: glob.filt_buf[fbpos] = '\0';
645: }
646: glob_match(arg, abpos, fbpos);
647: } else {
648: ENSURE_MEMSPACE(glob.argv, char *, glob.maxargs, glob.argc + 1);
649: if (!(glob.argv[glob.argc++] = strdup(glob.arg_buf)))
650: out_of_memory("glob_match");
651: }
652: }
653:
654: /* This routine performs wild-card expansion of the pathname in "arg". Any
655: * daemon-excluded files/dirs will not be matched by the wildcards. Returns 0
656: * if a wild-card string is the only returned item (due to matching nothing). */
657: int glob_expand(const char *arg, char ***argv_p, int *argc_p, int *maxargs_p)
658: {
659: int ret, save_argc;
660: char *s;
661:
662: if (!arg) {
663: if (glob.filt_buf)
664: free(glob.filt_buf);
665: free(glob.arg_buf);
666: memset(&glob, 0, sizeof glob);
667: return -1;
668: }
669:
670: if (sanitize_paths)
671: s = sanitize_path(NULL, arg, "", 0, SP_KEEP_DOT_DIRS);
672: else {
673: s = strdup(arg);
674: if (!s)
675: out_of_memory("glob_expand");
676: clean_fname(s, CFN_KEEP_DOT_DIRS
677: | CFN_KEEP_TRAILING_SLASH
678: | CFN_COLLAPSE_DOT_DOT_DIRS);
679: }
680:
681: ENSURE_MEMSPACE(glob.arg_buf, char, glob.absize, MAXPATHLEN);
682: *glob.arg_buf = '\0';
683:
684: glob.argc = save_argc = *argc_p;
685: glob.argv = *argv_p;
686: glob.maxargs = *maxargs_p;
687:
688: ENSURE_MEMSPACE(glob.argv, char *, glob.maxargs, 100);
689:
690: glob_match(s, 0, -1);
691:
692: /* The arg didn't match anything, so add the failed arg to the list. */
693: if (glob.argc == save_argc) {
694: ENSURE_MEMSPACE(glob.argv, char *, glob.maxargs, glob.argc + 1);
695: glob.argv[glob.argc++] = s;
696: ret = 0;
697: } else {
698: free(s);
699: ret = 1;
700: }
701:
702: *maxargs_p = glob.maxargs;
703: *argv_p = glob.argv;
704: *argc_p = glob.argc;
705:
706: return ret;
707: }
708:
709: /* This routine is only used in daemon mode. */
710: void glob_expand_module(char *base1, char *arg, char ***argv_p, int *argc_p, int *maxargs_p)
711: {
712: char *p, *s;
713: char *base = base1;
714: int base_len = strlen(base);
715:
716: if (!arg || !*arg)
717: return;
718:
719: if (strncmp(arg, base, base_len) == 0)
720: arg += base_len;
721:
722: if (!(arg = strdup(arg)))
723: out_of_memory("glob_expand_module");
724:
725: if (asprintf(&base," %s/", base1) <= 0)
726: out_of_memory("glob_expand_module");
727: base_len++;
728:
729: for (s = arg; *s; s = p + base_len) {
730: if ((p = strstr(s, base)) != NULL)
731: *p = '\0'; /* split it at this point */
732: glob_expand(s, argv_p, argc_p, maxargs_p);
733: if (!p)
734: break;
735: }
736:
737: free(arg);
738: free(base);
739: }
740:
741: /**
742: * Convert a string to lower case
743: **/
744: void strlower(char *s)
745: {
746: while (*s) {
747: if (isUpper(s))
748: *s = toLower(s);
749: s++;
750: }
751: }
752:
753: /* Join strings p1 & p2 into "dest" with a guaranteed '/' between them. (If
754: * p1 ends with a '/', no extra '/' is inserted.) Returns the length of both
755: * strings + 1 (if '/' was inserted), regardless of whether the null-terminated
756: * string fits into destsize. */
757: size_t pathjoin(char *dest, size_t destsize, const char *p1, const char *p2)
758: {
759: size_t len = strlcpy(dest, p1, destsize);
760: if (len < destsize - 1) {
761: if (!len || dest[len-1] != '/')
762: dest[len++] = '/';
763: if (len < destsize - 1)
764: len += strlcpy(dest + len, p2, destsize - len);
765: else {
766: dest[len] = '\0';
767: len += strlen(p2);
768: }
769: }
770: else
771: len += strlen(p2) + 1; /* Assume we'd insert a '/'. */
772: return len;
773: }
774:
775: /* Join any number of strings together, putting them in "dest". The return
776: * value is the length of all the strings, regardless of whether the null-
777: * terminated whole fits in destsize. Your list of string pointers must end
778: * with a NULL to indicate the end of the list. */
779: size_t stringjoin(char *dest, size_t destsize, ...)
780: {
781: va_list ap;
782: size_t len, ret = 0;
783: const char *src;
784:
785: va_start(ap, destsize);
786: while (1) {
787: if (!(src = va_arg(ap, const char *)))
788: break;
789: len = strlen(src);
790: ret += len;
791: if (destsize > 1) {
792: if (len >= destsize)
793: len = destsize - 1;
794: memcpy(dest, src, len);
795: destsize -= len;
796: dest += len;
797: }
798: }
799: *dest = '\0';
800: va_end(ap);
801:
802: return ret;
803: }
804:
805: int count_dir_elements(const char *p)
806: {
807: int cnt = 0, new_component = 1;
808: while (*p) {
809: if (*p++ == '/')
810: new_component = (*p != '.' || (p[1] != '/' && p[1] != '\0'));
811: else if (new_component) {
812: new_component = 0;
813: cnt++;
814: }
815: }
816: return cnt;
817: }
818:
819: /* Turns multiple adjacent slashes into a single slash (possible exception:
820: * the preserving of two leading slashes at the start), drops all leading or
821: * interior "." elements unless CFN_KEEP_DOT_DIRS is flagged. Will also drop
822: * a trailing '.' after a '/' if CFN_DROP_TRAILING_DOT_DIR is flagged, removes
823: * a trailing slash (perhaps after removing the aforementioned dot) unless
824: * CFN_KEEP_TRAILING_SLASH is flagged, and will also collapse ".." elements
825: * (except at the start) if CFN_COLLAPSE_DOT_DOT_DIRS is flagged. If the
826: * resulting name would be empty, returns ".". */
827: unsigned int clean_fname(char *name, int flags)
828: {
829: char *limit = name - 1, *t = name, *f = name;
830: int anchored;
831:
832: if (!name)
833: return 0;
834:
835: if ((anchored = *f == '/') != 0) {
836: *t++ = *f++;
837: #ifdef __CYGWIN__
838: /* If there are exactly 2 slashes at the start, preserve
839: * them. Would break daemon excludes unless the paths are
840: * really treated differently, so used this sparingly. */
841: if (*f == '/' && f[1] != '/')
842: *t++ = *f++;
843: #endif
844: } else if (flags & CFN_KEEP_DOT_DIRS && *f == '.' && f[1] == '/') {
845: *t++ = *f++;
846: *t++ = *f++;
847: }
848: while (*f) {
849: /* discard extra slashes */
850: if (*f == '/') {
851: f++;
852: continue;
853: }
854: if (*f == '.') {
855: /* discard interior "." dirs */
856: if (f[1] == '/' && !(flags & CFN_KEEP_DOT_DIRS)) {
857: f += 2;
858: continue;
859: }
860: if (f[1] == '\0' && flags & CFN_DROP_TRAILING_DOT_DIR)
861: break;
862: /* collapse ".." dirs */
863: if (flags & CFN_COLLAPSE_DOT_DOT_DIRS
864: && f[1] == '.' && (f[2] == '/' || !f[2])) {
865: char *s = t - 1;
866: if (s == name && anchored) {
867: f += 2;
868: continue;
869: }
870: while (s > limit && *--s != '/') {}
871: if (s != t - 1 && (s < name || *s == '/')) {
872: t = s + 1;
873: f += 2;
874: continue;
875: }
876: limit = t + 2;
877: }
878: }
879: while (*f && (*t++ = *f++) != '/') {}
880: }
881:
882: if (t > name+anchored && t[-1] == '/' && !(flags & CFN_KEEP_TRAILING_SLASH))
883: t--;
884: if (t == name)
885: *t++ = '.';
886: *t = '\0';
887:
888: return t - name;
889: }
890:
891: /* Make path appear as if a chroot had occurred. This handles a leading
892: * "/" (either removing it or expanding it) and any leading or embedded
893: * ".." components that attempt to escape past the module's top dir.
894: *
895: * If dest is NULL, a buffer is allocated to hold the result. It is legal
896: * to call with the dest and the path (p) pointing to the same buffer, but
897: * rootdir will be ignored to avoid expansion of the string.
898: *
899: * The rootdir string contains a value to use in place of a leading slash.
900: * Specify NULL to get the default of "module_dir".
901: *
902: * The depth var is a count of how many '..'s to allow at the start of the
903: * path.
904: *
905: * We also clean the path in a manner similar to clean_fname() but with a
906: * few differences:
907: *
908: * Turns multiple adjacent slashes into a single slash, gets rid of "." dir
909: * elements (INCLUDING a trailing dot dir), PRESERVES a trailing slash, and
910: * ALWAYS collapses ".." elements (except for those at the start of the
911: * string up to "depth" deep). If the resulting name would be empty,
912: * change it into a ".". */
913: char *sanitize_path(char *dest, const char *p, const char *rootdir, int depth,
914: int flags)
915: {
916: char *start, *sanp;
917: int rlen = 0, drop_dot_dirs = !relative_paths || !(flags & SP_KEEP_DOT_DIRS);
918:
919: if (dest != p) {
920: int plen = strlen(p);
921: if (*p == '/') {
922: if (!rootdir)
923: rootdir = module_dir;
924: rlen = strlen(rootdir);
925: depth = 0;
926: p++;
927: }
928: if (dest) {
929: if (rlen + plen + 1 >= MAXPATHLEN)
930: return NULL;
931: } else if (!(dest = new_array(char, rlen + plen + 1)))
932: out_of_memory("sanitize_path");
933: if (rlen) {
934: memcpy(dest, rootdir, rlen);
935: if (rlen > 1)
936: dest[rlen++] = '/';
937: }
938: }
939:
940: if (drop_dot_dirs) {
941: while (*p == '.' && p[1] == '/')
942: p += 2;
943: }
944:
945: start = sanp = dest + rlen;
946: /* This loop iterates once per filename component in p, pointing at
947: * the start of the name (past any prior slash) for each iteration. */
948: while (*p) {
949: /* discard leading or extra slashes */
950: if (*p == '/') {
951: p++;
952: continue;
953: }
954: if (drop_dot_dirs) {
955: if (*p == '.' && (p[1] == '/' || p[1] == '\0')) {
956: /* skip "." component */
957: p++;
958: continue;
959: }
960: }
961: if (*p == '.' && p[1] == '.' && (p[2] == '/' || p[2] == '\0')) {
962: /* ".." component followed by slash or end */
963: if (depth <= 0 || sanp != start) {
964: p += 2;
965: if (sanp != start) {
966: /* back up sanp one level */
967: --sanp; /* now pointing at slash */
968: while (sanp > start && sanp[-1] != '/')
969: sanp--;
970: }
971: continue;
972: }
973: /* allow depth levels of .. at the beginning */
974: depth--;
975: /* move the virtual beginning to leave the .. alone */
976: start = sanp + 3;
977: }
978: /* copy one component through next slash */
979: while (*p && (*sanp++ = *p++) != '/') {}
980: }
981: if (sanp == dest) {
982: /* ended up with nothing, so put in "." component */
983: *sanp++ = '.';
984: }
985: *sanp = '\0';
986:
987: return dest;
988: }
989:
990: /* Like chdir(), but it keeps track of the current directory (in the
991: * global "curr_dir"), and ensures that the path size doesn't overflow.
992: * Also cleans the path using the clean_fname() function. */
993: int change_dir(const char *dir, int set_path_only)
994: {
995: static int initialised;
996: unsigned int len;
997:
998: if (!initialised) {
999: initialised = 1;
1000: if (getcwd(curr_dir, sizeof curr_dir - 1) == NULL) {
1001: rsyserr(FERROR, errno, "getcwd()");
1002: exit_cleanup(RERR_FILESELECT);
1003: }
1004: curr_dir_len = strlen(curr_dir);
1005: }
1006:
1007: if (!dir) /* this call was probably just to initialize */
1008: return 0;
1009:
1010: len = strlen(dir);
1011: if (len == 1 && *dir == '.')
1012: return 1;
1013:
1014: if (*dir == '/') {
1015: if (len >= sizeof curr_dir) {
1016: errno = ENAMETOOLONG;
1017: return 0;
1018: }
1019: if (!set_path_only && chdir(dir))
1020: return 0;
1021: memcpy(curr_dir, dir, len + 1);
1022: } else {
1023: if (curr_dir_len + 1 + len >= sizeof curr_dir) {
1024: errno = ENAMETOOLONG;
1025: return 0;
1026: }
1027: if (!(curr_dir_len && curr_dir[curr_dir_len-1] == '/'))
1028: curr_dir[curr_dir_len++] = '/';
1029: memcpy(curr_dir + curr_dir_len, dir, len + 1);
1030:
1031: if (!set_path_only && chdir(curr_dir)) {
1032: curr_dir[curr_dir_len] = '\0';
1033: return 0;
1034: }
1035: }
1036:
1037: curr_dir_len = clean_fname(curr_dir, CFN_COLLAPSE_DOT_DOT_DIRS);
1038: if (sanitize_paths) {
1039: if (module_dirlen > curr_dir_len)
1040: module_dirlen = curr_dir_len;
1041: curr_dir_depth = count_dir_elements(curr_dir + module_dirlen);
1042: }
1043:
1044: if (verbose >= 5 && !set_path_only)
1045: rprintf(FINFO, "[%s] change_dir(%s)\n", who_am_i(), curr_dir);
1046:
1047: return 1;
1048: }
1049:
1050: /* This will make a relative path absolute and clean it up via clean_fname().
1051: * Returns the string, which might be newly allocated, or NULL on error. */
1052: char *normalize_path(char *path, BOOL force_newbuf, unsigned int *len_ptr)
1053: {
1054: unsigned int len;
1055:
1056: if (*path != '/') { /* Make path absolute. */
1057: int len = strlen(path);
1058: if (curr_dir_len + 1 + len >= sizeof curr_dir)
1059: return NULL;
1060: curr_dir[curr_dir_len] = '/';
1061: memcpy(curr_dir + curr_dir_len + 1, path, len + 1);
1062: if (!(path = strdup(curr_dir)))
1063: out_of_memory("normalize_path");
1064: curr_dir[curr_dir_len] = '\0';
1065: } else if (force_newbuf) {
1066: if (!(path = strdup(path)))
1067: out_of_memory("normalize_path");
1068: }
1069:
1070: len = clean_fname(path, CFN_COLLAPSE_DOT_DOT_DIRS | CFN_DROP_TRAILING_DOT_DIR);
1071:
1072: if (len_ptr)
1073: *len_ptr = len;
1074:
1075: return path;
1076: }
1077:
1078: /**
1079: * Return a quoted string with the full pathname of the indicated filename.
1080: * The string " (in MODNAME)" may also be appended. The returned pointer
1081: * remains valid until the next time full_fname() is called.
1082: **/
1083: char *full_fname(const char *fn)
1084: {
1085: static char *result = NULL;
1086: char *m1, *m2, *m3;
1087: char *p1, *p2;
1088:
1089: if (result)
1090: free(result);
1091:
1092: if (*fn == '/')
1093: p1 = p2 = "";
1094: else {
1095: p1 = curr_dir + module_dirlen;
1096: for (p2 = p1; *p2 == '/'; p2++) {}
1097: if (*p2)
1098: p2 = "/";
1099: }
1100: if (module_id >= 0) {
1101: m1 = " (in ";
1102: m2 = lp_name(module_id);
1103: m3 = ")";
1104: } else
1105: m1 = m2 = m3 = "";
1106:
1107: if (asprintf(&result, "\"%s%s%s\"%s%s%s", p1, p2, fn, m1, m2, m3) <= 0)
1108: out_of_memory("full_fname");
1109:
1110: return result;
1111: }
1112:
1113: static char partial_fname[MAXPATHLEN];
1114:
1115: char *partial_dir_fname(const char *fname)
1116: {
1117: char *t = partial_fname;
1118: int sz = sizeof partial_fname;
1119: const char *fn;
1120:
1121: if ((fn = strrchr(fname, '/')) != NULL) {
1122: fn++;
1123: if (*partial_dir != '/') {
1124: int len = fn - fname;
1125: strncpy(t, fname, len); /* safe */
1126: t += len;
1127: sz -= len;
1128: }
1129: } else
1130: fn = fname;
1131: if ((int)pathjoin(t, sz, partial_dir, fn) >= sz)
1132: return NULL;
1133: if (daemon_filter_list.head) {
1134: t = strrchr(partial_fname, '/');
1135: *t = '\0';
1136: if (check_filter(&daemon_filter_list, FLOG, partial_fname, 1) < 0)
1137: return NULL;
1138: *t = '/';
1139: if (check_filter(&daemon_filter_list, FLOG, partial_fname, 0) < 0)
1140: return NULL;
1141: }
1142:
1143: return partial_fname;
1144: }
1145:
1146: /* If no --partial-dir option was specified, we don't need to do anything
1147: * (the partial-dir is essentially '.'), so just return success. */
1148: int handle_partial_dir(const char *fname, int create)
1149: {
1150: char *fn, *dir;
1151:
1152: if (fname != partial_fname)
1153: return 1;
1154: if (!create && *partial_dir == '/')
1155: return 1;
1156: if (!(fn = strrchr(partial_fname, '/')))
1157: return 1;
1158:
1159: *fn = '\0';
1160: dir = partial_fname;
1161: if (create) {
1162: STRUCT_STAT st;
1163: int statret = do_lstat(dir, &st);
1164: if (statret == 0 && !S_ISDIR(st.st_mode)) {
1165: if (do_unlink(dir) < 0) {
1166: *fn = '/';
1167: return 0;
1168: }
1169: statret = -1;
1170: }
1171: if (statret < 0 && do_mkdir_path(dir, 0700) < 0) {
1172: *fn = '/';
1173: return 0;
1174: }
1175: } else
1176: do_rmdir(dir);
1177: *fn = '/';
1178:
1179: return 1;
1180: }
1181:
1182: /* We need to supply our own strcmp function for file list comparisons
1183: * to ensure that signed/unsigned usage is consistent between machines. */
1184: int u_strcmp(const char *p1, const char *p2)
1185: {
1186: for ( ; *p1; p1++, p2++) {
1187: if (*p1 != *p2)
1188: break;
1189: }
1190:
1191: return (int)*(uchar*)p1 - (int)*(uchar*)p2;
1192: }
1193:
1194: /* We need a memcmp function compares unsigned-byte values. */
1195: int u_memcmp(const void *p1, const void *p2, size_t len)
1196: {
1197: const uchar *u1 = p1;
1198: const uchar *u2 = p2;
1199:
1200: while (len--) {
1201: if (*u1 != *u2)
1202: return (int)*u1 - (int)*u2;
1203: }
1204:
1205: return 0;
1206: }
1207:
1208: /* Determine if a symlink points outside the current directory tree.
1209: * This is considered "unsafe" because e.g. when mirroring somebody
1210: * else's machine it might allow them to establish a symlink to
1211: * /etc/passwd, and then read it through a web server.
1212: *
1213: * Returns 1 if unsafe, 0 if safe.
1214: *
1215: * Null symlinks and absolute symlinks are always unsafe.
1216: *
1217: * Basically here we are concerned with symlinks whose target contains
1218: * "..", because this might cause us to walk back up out of the
1219: * transferred directory. We are not allowed to go back up and
1220: * reenter.
1221: *
1222: * "dest" is the target of the symlink in question.
1223: *
1224: * "src" is the top source directory currently applicable at the level
1225: * of the referenced symlink. This is usually the symlink's full path
1226: * (including its name), as referenced from the root of the transfer. */
1227: int unsafe_symlink(const char *dest, const char *src)
1228: {
1229: const char *name, *slash;
1230: int depth = 0;
1231:
1232: /* all absolute and null symlinks are unsafe */
1233: if (!dest || !*dest || *dest == '/')
1234: return 1;
1235:
1236: /* find out what our safety margin is */
1237: for (name = src; (slash = strchr(name, '/')) != 0; name = slash+1) {
1238: /* ".." segment starts the count over. "." segment is ignored. */
1239: if (*name == '.' && (name[1] == '/' || (name[1] == '.' && name[2] == '/'))) {
1240: if (name[1] == '.')
1241: depth = 0;
1242: } else
1243: depth++;
1244: while (slash[1] == '/') slash++; /* just in case src isn't clean */
1245: }
1246: if (*name == '.' && name[1] == '.' && name[2] == '\0')
1247: depth = 0;
1248:
1249: for (name = dest; (slash = strchr(name, '/')) != 0; name = slash+1) {
1250: if (*name == '.' && (name[1] == '/' || (name[1] == '.' && name[2] == '/'))) {
1251: if (name[1] == '.') {
1252: /* if at any point we go outside the current directory
1253: then stop - it is unsafe */
1254: if (--depth < 0)
1255: return 1;
1256: }
1257: } else
1258: depth++;
1259: while (slash[1] == '/') slash++;
1260: }
1261: if (*name == '.' && name[1] == '.' && name[2] == '\0')
1262: depth--;
1263:
1264: return depth < 0;
1265: }
1266:
1267: #define HUMANIFY(mult) \
1268: do { \
1269: if (num >= mult || num <= -mult) { \
1270: double dnum = (double)num / mult; \
1271: char units; \
1272: if (num < 0) \
1273: dnum = -dnum; \
1274: if (dnum < mult) \
1275: units = 'K'; \
1276: else if ((dnum /= mult) < mult) \
1277: units = 'M'; \
1278: else { \
1279: dnum /= mult; \
1280: units = 'G'; \
1281: } \
1282: if (num < 0) \
1283: dnum = -dnum; \
1284: snprintf(bufs[n], sizeof bufs[0], "%.2f%c", dnum, units); \
1285: return bufs[n]; \
1286: } \
1287: } while (0)
1288:
1289: /* Return the int64 number as a string. If the --human-readable option was
1290: * specified, we may output the number in K, M, or G units. We can return
1291: * up to 4 buffers at a time. */
1292: char *human_num(int64 num)
1293: {
1294: static char bufs[4][128]; /* more than enough room */
1295: static unsigned int n;
1296: char *s;
1297: int negated;
1298:
1299: n = (n + 1) % (sizeof bufs / sizeof bufs[0]);
1300:
1301: if (human_readable) {
1302: if (human_readable == 1)
1303: HUMANIFY(1000);
1304: else
1305: HUMANIFY(1024);
1306: }
1307:
1308: s = bufs[n] + sizeof bufs[0] - 1;
1309: *s = '\0';
1310:
1311: if (!num)
1312: *--s = '0';
1313: if (num < 0) {
1314: /* A maximum-size negated number can't fit as a positive,
1315: * so do one digit in negated form to start us off. */
1316: *--s = (char)(-(num % 10)) + '0';
1317: num = -(num / 10);
1318: negated = 1;
1319: } else
1320: negated = 0;
1321:
1322: while (num) {
1323: *--s = (char)(num % 10) + '0';
1324: num /= 10;
1325: }
1326:
1327: if (negated)
1328: *--s = '-';
1329:
1330: return s;
1331: }
1332:
1333: /* Return the double number as a string. If the --human-readable option was
1334: * specified, we may output the number in K, M, or G units. We use a buffer
1335: * from human_num() to return our result. */
1336: char *human_dnum(double dnum, int decimal_digits)
1337: {
1338: char *buf = human_num(dnum);
1339: int len = strlen(buf);
1340: if (isDigit(buf + len - 1)) {
1341: /* There's extra room in buf prior to the start of the num. */
1342: buf -= decimal_digits + 2;
1343: snprintf(buf, len + decimal_digits + 3, "%.*f", decimal_digits, dnum);
1344: }
1345: return buf;
1346: }
1347:
1348: /* Return the date and time as a string. Some callers tweak returned buf. */
1349: char *timestring(time_t t)
1350: {
1351: static char TimeBuf[200];
1352: struct tm *tm = localtime(&t);
1353: char *p;
1354:
1355: #ifdef HAVE_STRFTIME
1356: strftime(TimeBuf, sizeof TimeBuf - 1, "%Y/%m/%d %H:%M:%S", tm);
1357: #else
1358: strlcpy(TimeBuf, asctime(tm), sizeof TimeBuf);
1359: #endif
1360:
1361: if ((p = strchr(TimeBuf, '\n')) != NULL)
1362: *p = '\0';
1363:
1364: return TimeBuf;
1365: }
1366:
1367: /**
1368: * Sleep for a specified number of milliseconds.
1369: *
1370: * Always returns TRUE. (In the future it might return FALSE if
1371: * interrupted.)
1372: **/
1373: int msleep(int t)
1374: {
1375: int tdiff = 0;
1376: struct timeval tval, t1, t2;
1377:
1378: gettimeofday(&t1, NULL);
1379:
1380: while (tdiff < t) {
1381: tval.tv_sec = (t-tdiff)/1000;
1382: tval.tv_usec = 1000*((t-tdiff)%1000);
1383:
1384: errno = 0;
1385: select(0,NULL,NULL, NULL, &tval);
1386:
1387: gettimeofday(&t2, NULL);
1388: tdiff = (t2.tv_sec - t1.tv_sec)*1000 +
1389: (t2.tv_usec - t1.tv_usec)/1000;
1390: }
1391:
1392: return True;
1393: }
1394:
1395: /* Determine if two time_t values are equivalent (either exact, or in
1396: * the modification timestamp window established by --modify-window).
1397: *
1398: * @retval 0 if the times should be treated as the same
1399: *
1400: * @retval +1 if the first is later
1401: *
1402: * @retval -1 if the 2nd is later
1403: **/
1404: int cmp_time(time_t file1, time_t file2)
1405: {
1406: if (file2 > file1) {
1407: if (file2 - file1 <= modify_window)
1408: return 0;
1409: return -1;
1410: }
1411: if (file1 - file2 <= modify_window)
1412: return 0;
1413: return 1;
1414: }
1415:
1416:
1417: #ifdef __INSURE__XX
1418: #include <dlfcn.h>
1419:
1420: /**
1421: This routine is a trick to immediately catch errors when debugging
1422: with insure. A xterm with a gdb is popped up when insure catches
1423: a error. It is Linux specific.
1424: **/
1425: int _Insure_trap_error(int a1, int a2, int a3, int a4, int a5, int a6)
1426: {
1427: static int (*fn)();
1428: int ret;
1429: char *cmd;
1430:
1431: asprintf(&cmd, "/usr/X11R6/bin/xterm -display :0 -T Panic -n Panic -e /bin/sh -c 'cat /tmp/ierrs.*.%d ; gdb /proc/%d/exe %d'",
1432: getpid(), getpid(), getpid());
1433:
1434: if (!fn) {
1435: static void *h;
1436: h = dlopen("/usr/local/parasoft/insure++lite/lib.linux2/libinsure.so", RTLD_LAZY);
1437: fn = dlsym(h, "_Insure_trap_error");
1438: }
1439:
1440: ret = fn(a1, a2, a3, a4, a5, a6);
1441:
1442: system(cmd);
1443:
1444: free(cmd);
1445:
1446: return ret;
1447: }
1448: #endif
1449:
1450: #define MALLOC_MAX 0x40000000
1451:
1452: void *_new_array(unsigned long num, unsigned int size, int use_calloc)
1453: {
1454: if (num >= MALLOC_MAX/size)
1455: return NULL;
1456: return use_calloc ? calloc(num, size) : malloc(num * size);
1457: }
1458:
1459: void *_realloc_array(void *ptr, unsigned int size, size_t num)
1460: {
1461: if (num >= MALLOC_MAX/size)
1462: return NULL;
1463: if (!ptr)
1464: return malloc(size * num);
1465: return realloc(ptr, size * num);
1466: }
1467:
1468: /* Take a filename and filename length and return the most significant
1469: * filename suffix we can find. This ignores suffixes such as "~",
1470: * ".bak", ".orig", ".~1~", etc. */
1471: const char *find_filename_suffix(const char *fn, int fn_len, int *len_ptr)
1472: {
1473: const char *suf, *s;
1474: BOOL had_tilde;
1475: int s_len;
1476:
1477: /* One or more dots at the start aren't a suffix. */
1478: while (fn_len && *fn == '.') fn++, fn_len--;
1479:
1480: /* Ignore the ~ in a "foo~" filename. */
1481: if (fn_len > 1 && fn[fn_len-1] == '~')
1482: fn_len--, had_tilde = True;
1483: else
1484: had_tilde = False;
1485:
1486: /* Assume we don't find an suffix. */
1487: suf = "";
1488: *len_ptr = 0;
1489:
1490: /* Find the last significant suffix. */
1491: for (s = fn + fn_len; fn_len > 1; ) {
1492: while (*--s != '.' && s != fn) {}
1493: if (s == fn)
1494: break;
1495: s_len = fn_len - (s - fn);
1496: fn_len = s - fn;
1497: if (s_len == 4) {
1498: if (strcmp(s+1, "bak") == 0
1499: || strcmp(s+1, "old") == 0)
1500: continue;
1501: } else if (s_len == 5) {
1502: if (strcmp(s+1, "orig") == 0)
1503: continue;
1504: } else if (s_len > 2 && had_tilde
1505: && s[1] == '~' && isDigit(s + 2))
1506: continue;
1507: *len_ptr = s_len;
1508: suf = s;
1509: if (s_len == 1)
1510: break;
1511: /* Determine if the suffix is all digits. */
1512: for (s++, s_len--; s_len > 0; s++, s_len--) {
1513: if (!isDigit(s))
1514: return suf;
1515: }
1516: /* An all-digit suffix may not be that signficant. */
1517: s = suf;
1518: }
1519:
1520: return suf;
1521: }
1522:
1523: /* This is an implementation of the Levenshtein distance algorithm. It
1524: * was implemented to avoid needing a two-dimensional matrix (to save
1525: * memory). It was also tweaked to try to factor in the ASCII distance
1526: * between changed characters as a minor distance quantity. The normal
1527: * Levenshtein units of distance (each signifying a single change between
1528: * the two strings) are defined as a "UNIT". */
1529:
1530: #define UNIT (1 << 16)
1531:
1532: uint32 fuzzy_distance(const char *s1, int len1, const char *s2, int len2)
1533: {
1534: uint32 a[MAXPATHLEN], diag, above, left, diag_inc, above_inc, left_inc;
1535: int32 cost;
1536: int i1, i2;
1537:
1538: if (!len1 || !len2) {
1539: if (!len1) {
1540: s1 = s2;
1541: len1 = len2;
1542: }
1543: for (i1 = 0, cost = 0; i1 < len1; i1++)
1544: cost += s1[i1];
1545: return (int32)len1 * UNIT + cost;
1546: }
1547:
1548: for (i2 = 0; i2 < len2; i2++)
1549: a[i2] = (i2+1) * UNIT;
1550:
1551: for (i1 = 0; i1 < len1; i1++) {
1552: diag = i1 * UNIT;
1553: above = (i1+1) * UNIT;
1554: for (i2 = 0; i2 < len2; i2++) {
1555: left = a[i2];
1556: if ((cost = *((uchar*)s1+i1) - *((uchar*)s2+i2)) != 0) {
1557: if (cost < 0)
1558: cost = UNIT - cost;
1559: else
1560: cost = UNIT + cost;
1561: }
1562: diag_inc = diag + cost;
1563: left_inc = left + UNIT + *((uchar*)s1+i1);
1564: above_inc = above + UNIT + *((uchar*)s2+i2);
1565: a[i2] = above = left < above
1566: ? (left_inc < diag_inc ? left_inc : diag_inc)
1567: : (above_inc < diag_inc ? above_inc : diag_inc);
1568: diag = left;
1569: }
1570: }
1571:
1572: return a[len2-1];
1573: }
1574:
1575: #define BB_SLOT_SIZE (16*1024) /* Desired size in bytes */
1576: #define BB_PER_SLOT_BITS (BB_SLOT_SIZE * 8) /* Number of bits per slot */
1577: #define BB_PER_SLOT_INTS (BB_SLOT_SIZE / 4) /* Number of int32s per slot */
1578:
1579: struct bitbag {
1580: uint32 **bits;
1581: int slot_cnt;
1582: };
1583:
1584: struct bitbag *bitbag_create(int max_ndx)
1585: {
1586: struct bitbag *bb = new(struct bitbag);
1587: bb->slot_cnt = (max_ndx + BB_PER_SLOT_BITS - 1) / BB_PER_SLOT_BITS;
1588:
1589: if (!(bb->bits = (uint32**)calloc(bb->slot_cnt, sizeof (uint32*))))
1590: out_of_memory("bitbag_create");
1591:
1592: return bb;
1593: }
1594:
1595: void bitbag_set_bit(struct bitbag *bb, int ndx)
1596: {
1597: int slot = ndx / BB_PER_SLOT_BITS;
1598: ndx %= BB_PER_SLOT_BITS;
1599:
1600: if (!bb->bits[slot]) {
1601: if (!(bb->bits[slot] = (uint32*)calloc(BB_PER_SLOT_INTS, 4)))
1602: out_of_memory("bitbag_set_bit");
1603: }
1604:
1605: bb->bits[slot][ndx/32] |= 1u << (ndx % 32);
1606: }
1607:
1608: #if 0 /* not needed yet */
1609: void bitbag_clear_bit(struct bitbag *bb, int ndx)
1610: {
1611: int slot = ndx / BB_PER_SLOT_BITS;
1612: ndx %= BB_PER_SLOT_BITS;
1613:
1614: if (!bb->bits[slot])
1615: return;
1616:
1617: bb->bits[slot][ndx/32] &= ~(1u << (ndx % 32));
1618: }
1619:
1620: int bitbag_check_bit(struct bitbag *bb, int ndx)
1621: {
1622: int slot = ndx / BB_PER_SLOT_BITS;
1623: ndx %= BB_PER_SLOT_BITS;
1624:
1625: if (!bb->bits[slot])
1626: return 0;
1627:
1628: return bb->bits[slot][ndx/32] & (1u << (ndx % 32)) ? 1 : 0;
1629: }
1630: #endif
1631:
1632: /* Call this with -1 to start checking from 0. Returns -1 at the end. */
1633: int bitbag_next_bit(struct bitbag *bb, int after)
1634: {
1635: uint32 bits, mask;
1636: int i, ndx = after + 1;
1637: int slot = ndx / BB_PER_SLOT_BITS;
1638: ndx %= BB_PER_SLOT_BITS;
1639:
1640: mask = (1u << (ndx % 32)) - 1;
1641: for (i = ndx / 32; slot < bb->slot_cnt; slot++, i = mask = 0) {
1642: if (!bb->bits[slot])
1643: continue;
1644: for ( ; i < BB_PER_SLOT_INTS; i++, mask = 0) {
1645: if (!(bits = bb->bits[slot][i] & ~mask))
1646: continue;
1647: /* The xor magic figures out the lowest enabled bit in
1648: * bits, and the switch quickly computes log2(bit). */
1649: switch (bits ^ (bits & (bits-1))) {
1650: #define LOG2(n) case 1u << n: return slot*BB_PER_SLOT_BITS + i*32 + n
1651: LOG2(0); LOG2(1); LOG2(2); LOG2(3);
1652: LOG2(4); LOG2(5); LOG2(6); LOG2(7);
1653: LOG2(8); LOG2(9); LOG2(10); LOG2(11);
1654: LOG2(12); LOG2(13); LOG2(14); LOG2(15);
1655: LOG2(16); LOG2(17); LOG2(18); LOG2(19);
1656: LOG2(20); LOG2(21); LOG2(22); LOG2(23);
1657: LOG2(24); LOG2(25); LOG2(26); LOG2(27);
1658: LOG2(28); LOG2(29); LOG2(30); LOG2(31);
1659: }
1660: return -1; /* impossible... */
1661: }
1662: }
1663:
1664: return -1;
1665: }
1666:
1667: void flist_ndx_push(flist_ndx_list *lp, int ndx)
1668: {
1669: struct flist_ndx_item *item;
1670:
1671: if (!(item = new(struct flist_ndx_item)))
1672: out_of_memory("flist_ndx_push");
1673: item->next = NULL;
1674: item->ndx = ndx;
1675: if (lp->tail)
1676: lp->tail->next = item;
1677: else
1678: lp->head = item;
1679: lp->tail = item;
1680: }
1681:
1682: int flist_ndx_pop(flist_ndx_list *lp)
1683: {
1684: struct flist_ndx_item *next;
1685: int ndx;
1686:
1687: if (!lp->head)
1688: return -1;
1689:
1690: ndx = lp->head->ndx;
1691: next = lp->head->next;
1692: free(lp->head);
1693: lp->head = next;
1694: if (!next)
1695: lp->tail = NULL;
1696:
1697: return ndx;
1698: }
1699:
1700: void *expand_item_list(item_list *lp, size_t item_size,
1701: const char *desc, int incr)
1702: {
1703: /* First time through, 0 <= 0, so list is expanded. */
1704: if (lp->malloced <= lp->count) {
1705: void *new_ptr;
1706: size_t new_size = lp->malloced;
1707: if (incr < 0)
1708: new_size += -incr; /* increase slowly */
1709: else if (new_size < (size_t)incr)
1710: new_size += incr;
1711: else
1712: new_size *= 2;
1713: if (new_size < lp->malloced)
1714: overflow_exit("expand_item_list");
1715: /* Using _realloc_array() lets us pass the size, not a type. */
1716: new_ptr = _realloc_array(lp->items, item_size, new_size);
1717: if (verbose >= 4) {
1718: rprintf(FINFO, "[%s] expand %s to %.0f bytes, did%s move\n",
1719: who_am_i(), desc, (double)new_size * item_size,
1720: new_ptr == lp->items ? " not" : "");
1721: }
1722: if (!new_ptr)
1723: out_of_memory("expand_item_list");
1724:
1725: lp->items = new_ptr;
1726: lp->malloced = new_size;
1727: }
1728: return (char*)lp->items + (lp->count++ * item_size);
1729: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to util.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync