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