1 /* -*- c-file-style: "linux" -*-
3 * Copyright (C) 1996-2000 by Andrew Tridgell
4 * Copyright (C) Paul Mackerras 1996
5 * Copyright (C) 2001, 2002 by Martin Pool <mbp@samba.org>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
25 * Utilities used in rsync
33 extern int modify_window;
34 extern int relative_paths;
35 extern int human_readable;
36 extern char *partial_dir;
37 extern struct filter_list_struct server_filter_list;
39 int sanitize_paths = 0;
44 * Set a fd into nonblocking mode
46 void set_nonblocking(int fd)
50 if ((val = fcntl(fd, F_GETFL, 0)) == -1)
52 if (!(val & NONBLOCK_FLAG)) {
54 fcntl(fd, F_SETFL, val);
59 * Set a fd into blocking mode
61 void set_blocking(int fd)
65 if ((val = fcntl(fd, F_GETFL, 0)) == -1)
67 if (val & NONBLOCK_FLAG) {
68 val &= ~NONBLOCK_FLAG;
69 fcntl(fd, F_SETFL, val);
74 * Create a file descriptor pair - like pipe() but use socketpair if
75 * possible (because of blocking issues on pipes).
77 * Always set non-blocking.
79 int fd_pair(int fd[2])
83 #ifdef HAVE_SOCKETPAIR
84 ret = socketpair(AF_UNIX, SOCK_STREAM, 0, fd);
90 set_nonblocking(fd[0]);
91 set_nonblocking(fd[1]);
97 void print_child_argv(char **cmd)
99 rprintf(FINFO, "opening connection using ");
100 for (; *cmd; cmd++) {
101 /* Look for characters that ought to be quoted. This
102 * is not a great quoting algorithm, but it's
103 * sufficient for a log message. */
104 if (strspn(*cmd, "abcdefghijklmnopqrstuvwxyz"
105 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
107 ",.-_=+@/") != strlen(*cmd)) {
108 rprintf(FINFO, "\"%s\" ", *cmd);
110 rprintf(FINFO, "%s ", *cmd);
113 rprintf(FINFO, "\n");
116 void out_of_memory(char *str)
118 rprintf(FERROR, "ERROR: out of memory in %s\n", str);
119 exit_cleanup(RERR_MALLOC);
122 void overflow_exit(char *str)
124 rprintf(FERROR, "ERROR: buffer overflow in %s\n", str);
125 exit_cleanup(RERR_MALLOC);
128 int set_modtime(char *fname, time_t modtime, mode_t mode)
130 #if !defined HAVE_LUTIMES || !defined HAVE_UTIMES
136 rprintf(FINFO, "set modtime of %s to (%ld) %s",
137 fname, (long)modtime,
138 asctime(localtime(&modtime)));
147 t[0].tv_sec = time(NULL);
149 t[1].tv_sec = modtime;
153 return lutimes(fname, t);
155 return utimes(fname, t);
156 #elif defined HAVE_UTIMBUF
158 tbuf.actime = time(NULL);
159 tbuf.modtime = modtime;
160 return utime(fname,&tbuf);
161 #elif defined HAVE_UTIME
165 return utime(fname,t);
167 #error No file-time-modification routine found!
173 Create any necessary directories in fname. Unfortunately we don't know
174 what perms to give the directory when this is called so we need to rely
177 int create_directory_path(char *fname, int base_umask)
181 while (*fname == '/')
183 while (strncmp(fname, "./", 2) == 0)
187 while ((p = strchr(p,'/')) != NULL) {
189 do_mkdir(fname, 0777 & ~base_umask);
197 * Write @p len bytes at @p ptr to descriptor @p desc, retrying if
200 * @retval len upon success
202 * @retval <0 write's (negative) error code
204 * Derived from GNU C's cccp.c.
206 int full_write(int desc, char *ptr, size_t len)
212 int written = write(desc, ptr, len);
218 total_written += written;
222 return total_written;
226 * Read @p len bytes at @p ptr from descriptor @p desc, retrying if
229 * @retval >0 the actual number of bytes read
233 * @retval <0 for an error.
235 * Derived from GNU C's cccp.c. */
236 static int safe_read(int desc, char *ptr, size_t len)
244 n_chars = read(desc, ptr, len);
245 } while (n_chars < 0 && errno == EINTR);
252 * This is used in conjunction with the --temp-dir, --backup, and
253 * --copy-dest options. */
254 int copy_file(const char *source, const char *dest, mode_t mode)
259 int len; /* Number of bytes read into `buf'. */
261 ifd = do_open(source, O_RDONLY, 0);
263 rsyserr(FERROR, errno, "open %s", full_fname(source));
267 if (robust_unlink(dest) && errno != ENOENT) {
268 rsyserr(FERROR, errno, "unlink %s", full_fname(dest));
272 ofd = do_open(dest, O_WRONLY | O_CREAT | O_TRUNC | O_EXCL, mode);
274 rsyserr(FERROR, errno, "open %s", full_fname(dest));
279 while ((len = safe_read(ifd, buf, sizeof buf)) > 0) {
280 if (full_write(ofd, buf, len) < 0) {
281 rsyserr(FERROR, errno, "write %s", full_fname(dest));
289 rsyserr(FERROR, errno, "read %s", full_fname(source));
295 if (close(ifd) < 0) {
296 rsyserr(FINFO, errno, "close failed on %s",
300 if (close(ofd) < 0) {
301 rsyserr(FERROR, errno, "close failed on %s",
309 /* MAX_RENAMES should be 10**MAX_RENAMES_DIGITS */
310 #define MAX_RENAMES_DIGITS 3
311 #define MAX_RENAMES 1000
314 * Robust unlink: some OS'es (HPUX) refuse to unlink busy files, so
315 * rename to <path>/.rsyncNNN instead.
317 * Note that successive rsync runs will shuffle the filenames around a
318 * bit as long as the file is still busy; this is because this function
319 * does not know if the unlink call is due to a new file coming in, or
320 * --delete trying to remove old .rsyncNNN files, hence it renames it
323 int robust_unlink(const char *fname)
326 return do_unlink(fname);
328 static int counter = 1;
330 char path[MAXPATHLEN];
332 rc = do_unlink(fname);
333 if (rc == 0 || errno != ETXTBSY)
336 if ((pos = strlcpy(path, fname, MAXPATHLEN)) >= MAXPATHLEN)
337 pos = MAXPATHLEN - 1;
339 while (pos > 0 && path[pos-1] != '/')
341 pos += strlcpy(path+pos, ".rsync", MAXPATHLEN-pos);
343 if (pos > (MAXPATHLEN-MAX_RENAMES_DIGITS-1)) {
348 /* start where the last one left off to reduce chance of clashes */
351 sprintf(&path[pos], "%03d", counter);
352 if (++counter >= MAX_RENAMES)
354 } while ((rc = access(path, 0)) == 0 && counter != start);
357 rprintf(FINFO,"renaming %s to %s because of text busy\n",
361 /* maybe we should return rename()'s exit status? Nah. */
362 if (do_rename(fname, path) != 0) {
370 /* Returns 0 on successful rename, 1 if we successfully copied the file
371 * across filesystems, -2 if copy_file() failed, and -1 on other errors.
372 * If partialptr is not NULL and we need to do a copy, copy the file into
373 * the active partial-dir instead of over the destination file. */
374 int robust_rename(char *from, char *to, char *partialptr,
380 if (do_rename(from, to) == 0)
386 if (robust_unlink(to) != 0)
392 if (!handle_partial_dir(partialptr,PDIR_CREATE))
396 if (copy_file(from, to, mode) != 0)
407 static pid_t all_pids[10];
410 /** Fork and record the pid of the child. **/
413 pid_t newpid = fork();
415 if (newpid != 0 && newpid != -1) {
416 all_pids[num_pids++] = newpid;
424 * @todo It would be kind of nice to make sure that they are actually
425 * all our children before we kill them, because their pids may have
426 * been recycled by some other process. Perhaps when we wait for a
427 * child, we should remove it from this array. Alternatively we could
428 * perhaps use process groups, but I think that would not work on
429 * ancient Unix versions that don't support them.
431 void kill_all(int sig)
435 for (i = 0; i < num_pids; i++) {
436 /* Let's just be a little careful where we
437 * point that gun, hey? See kill(2) for the
438 * magic caused by negative values. */
439 pid_t p = all_pids[i];
450 /** Turn a user name into a uid */
451 int name_to_uid(char *name, uid_t *uid)
456 pass = getpwnam(name);
464 /** Turn a group name into a gid */
465 int name_to_gid(char *name, gid_t *gid)
470 grp = getgrnam(name);
478 /** Lock a byte range in a open file */
479 int lock_range(int fd, int offset, int len)
483 lock.l_type = F_WRLCK;
484 lock.l_whence = SEEK_SET;
485 lock.l_start = offset;
489 return fcntl(fd,F_SETLK,&lock) == 0;
492 static int filter_server_path(char *arg)
496 if (server_filter_list.head) {
497 for (s = arg; (s = strchr(s, '/')) != NULL; ) {
499 if (check_filter(&server_filter_list, arg, 1) < 0) {
500 /* We must leave arg truncated! */
509 static void glob_expand_one(char *s, char ***argv_ptr, int *argc_ptr,
512 char **argv = *argv_ptr;
513 int argc = *argc_ptr;
514 int maxargs = *maxargs_ptr;
515 #if !defined HAVE_GLOB || !defined HAVE_GLOB_H
516 if (argc == maxargs) {
518 if (!(argv = realloc_array(argv, char *, maxargs)))
519 out_of_memory("glob_expand_one");
521 *maxargs_ptr = maxargs;
525 s = argv[argc++] = strdup(s);
526 filter_server_path(s);
536 s = sanitize_path(NULL, s, "", 0);
540 memset(&globbuf, 0, sizeof globbuf);
541 if (!filter_server_path(s))
542 glob(s, 0, NULL, &globbuf);
543 if (MAX((int)globbuf.gl_pathc, 1) > maxargs - argc) {
544 maxargs += globbuf.gl_pathc + MAX_ARGS;
545 if (!(argv = realloc_array(argv, char *, maxargs)))
546 out_of_memory("glob_expand_one");
548 *maxargs_ptr = maxargs;
550 if (globbuf.gl_pathc == 0)
555 for (i = 0; i < (int)globbuf.gl_pathc; i++) {
556 if (!(argv[argc++] = strdup(globbuf.gl_pathv[i])))
557 out_of_memory("glob_expand_one");
565 /* This routine is only used in daemon mode. */
566 void glob_expand(char *base1, char ***argv_ptr, int *argc_ptr, int *maxargs_ptr)
568 char *s = (*argv_ptr)[*argc_ptr];
571 int base_len = strlen(base);
576 if (strncmp(s, base, base_len) == 0)
579 if (!(s = strdup(s)))
580 out_of_memory("glob_expand");
582 if (asprintf(&base," %s/", base1) <= 0)
583 out_of_memory("glob_expand");
586 for (q = s; *q; q = p + base_len) {
587 if ((p = strstr(q, base)) != NULL)
588 *p = '\0'; /* split it at this point */
589 glob_expand_one(q, argv_ptr, argc_ptr, maxargs_ptr);
599 * Convert a string to lower case
601 void strlower(char *s)
604 if (isupper(*(unsigned char *)s))
605 *s = tolower(*(unsigned char *)s);
610 /* Join strings p1 & p2 into "dest" with a guaranteed '/' between them. (If
611 * p1 ends with a '/', no extra '/' is inserted.) Returns the length of both
612 * strings + 1 (if '/' was inserted), regardless of whether the null-terminated
613 * string fits into destsize. */
614 size_t pathjoin(char *dest, size_t destsize, const char *p1, const char *p2)
616 size_t len = strlcpy(dest, p1, destsize);
617 if (len < destsize - 1) {
618 if (!len || dest[len-1] != '/')
620 if (len < destsize - 1)
621 len += strlcpy(dest + len, p2, destsize - len);
628 len += strlen(p2) + 1; /* Assume we'd insert a '/'. */
632 /* Join any number of strings together, putting them in "dest". The return
633 * value is the length of all the strings, regardless of whether the null-
634 * terminated whole fits in destsize. Your list of string pointers must end
635 * with a NULL to indicate the end of the list. */
636 size_t stringjoin(char *dest, size_t destsize, ...)
642 va_start(ap, destsize);
644 if (!(src = va_arg(ap, const char *)))
651 memcpy(dest, src, len);
662 int count_dir_elements(const char *p)
664 int cnt = 0, new_component = 1;
668 else if (new_component) {
676 /* Turns multiple adjacent slashes into a single slash, gets rid of "./"
677 * elements (but not a trailing dot dir), removes a trailing slash, and
678 * optionally collapses ".." elements (except for those at the start of the
679 * string). If the resulting name would be empty, change it into a ".". */
680 unsigned int clean_fname(char *name, BOOL collapse_dot_dot)
682 char *limit = name - 1, *t = name, *f = name;
688 if ((anchored = *f == '/') != 0)
691 /* discard extra slashes */
697 /* discard "." dirs (but NOT a trailing '.'!) */
702 /* collapse ".." dirs */
704 && f[1] == '.' && (f[2] == '/' || !f[2])) {
706 if (s == name && anchored) {
710 while (s > limit && *--s != '/') {}
711 if (s != t - 1 && (s < name || *s == '/')) {
719 while (*f && (*t++ = *f++) != '/') {}
722 if (t > name+anchored && t[-1] == '/')
731 /* Make path appear as if a chroot had occurred. This handles a leading
732 * "/" (either removing it or expanding it) and any leading or embedded
733 * ".." components that attempt to escape past the module's top dir.
735 * If dest is NULL, a buffer is allocated to hold the result. It is legal
736 * to call with the dest and the path (p) pointing to the same buffer, but
737 * rootdir will be ignored to avoid expansion of the string.
739 * The rootdir string contains a value to use in place of a leading slash.
740 * Specify NULL to get the default of lp_path(module_id).
742 * If depth is >= 0, it is a count of how many '..'s to allow at the start
743 * of the path. Use -1 to allow unlimited depth.
745 * We also clean the path in a manner similar to clean_fname() but with a
748 * Turns multiple adjacent slashes into a single slash, gets rid of "." dir
749 * elements (INCLUDING a trailing dot dir), PRESERVES a trailing slash, and
750 * ALWAYS collapses ".." elements (except for those at the start of the
751 * string up to "depth" deep). If the resulting name would be empty,
752 * change it into a ".". */
753 char *sanitize_path(char *dest, const char *p, const char *rootdir, int depth)
756 int rlen = 0, leave_one_dotdir = relative_paths;
759 int plen = strlen(p);
762 rootdir = lp_path(module_id);
763 rlen = strlen(rootdir);
768 if (rlen + plen + 1 >= MAXPATHLEN)
770 } else if (!(dest = new_array(char, rlen + plen + 1)))
771 out_of_memory("sanitize_path");
773 memcpy(dest, rootdir, rlen);
779 start = sanp = dest + rlen;
781 /* discard leading or extra slashes */
786 /* this loop iterates once per filename component in p.
787 * both p (and sanp if the original had a slash) should
788 * always be left pointing after a slash
790 if (*p == '.' && (p[1] == '/' || p[1] == '\0')) {
791 if (leave_one_dotdir && p[1])
792 leave_one_dotdir = 0;
794 /* skip "." component */
799 if (*p == '.' && p[1] == '.' && (p[2] == '/' || p[2] == '\0')) {
800 /* ".." component followed by slash or end */
801 if (depth <= 0 || sanp != start) {
804 /* back up sanp one level */
805 --sanp; /* now pointing at slash */
806 while (sanp > start && sanp[-1] != '/') {
807 /* skip back up to slash */
813 /* allow depth levels of .. at the beginning */
815 /* move the virtual beginning to leave the .. alone */
818 /* copy one component through next slash */
819 while (*p && (*sanp++ = *p++) != '/') {}
822 /* ended up with nothing, so put in "." component */
830 char curr_dir[MAXPATHLEN];
831 unsigned int curr_dir_len;
834 * Like chdir(), but it keeps track of the current directory (in the
835 * global "curr_dir"), and ensures that the path size doesn't overflow.
836 * Also cleans the path using the clean_fname() function.
838 int push_dir(char *dir)
840 static int initialised;
845 getcwd(curr_dir, sizeof curr_dir - 1);
846 curr_dir_len = strlen(curr_dir);
849 if (!dir) /* this call was probably just to initialize */
853 if (len == 1 && *dir == '.')
856 if ((*dir == '/' ? len : curr_dir_len + 1 + len) >= sizeof curr_dir)
863 memcpy(curr_dir, dir, len + 1);
866 curr_dir[curr_dir_len++] = '/';
867 memcpy(curr_dir + curr_dir_len, dir, len + 1);
871 curr_dir_len = clean_fname(curr_dir, 1);
877 * Reverse a push_dir() call. You must pass in an absolute path
878 * that was copied from a prior value of "curr_dir".
880 int pop_dir(char *dir)
885 curr_dir_len = strlcpy(curr_dir, dir, sizeof curr_dir);
886 if (curr_dir_len >= sizeof curr_dir)
887 curr_dir_len = sizeof curr_dir - 1;
893 * Return a quoted string with the full pathname of the indicated filename.
894 * The string " (in MODNAME)" may also be appended. The returned pointer
895 * remains valid until the next time full_fname() is called.
897 char *full_fname(const char *fn)
899 static char *result = NULL;
910 for (p2 = p1; *p2 == '/'; p2++) {}
914 if (module_id >= 0) {
916 m2 = lp_name(module_id);
918 if (p1 == curr_dir) {
919 if (!lp_use_chroot(module_id)) {
920 char *p = lp_path(module_id);
921 if (*p != '/' || p[1])
928 asprintf(&result, "\"%s%s%s\"%s%s%s", p1, p2, fn, m1, m2, m3);
933 static char partial_fname[MAXPATHLEN];
935 char *partial_dir_fname(const char *fname)
937 char *t = partial_fname;
938 int sz = sizeof partial_fname;
941 if ((fn = strrchr(fname, '/')) != NULL) {
943 if (*partial_dir != '/') {
944 int len = fn - fname;
945 strncpy(t, fname, len); /* safe */
951 if ((int)pathjoin(t, sz, partial_dir, fn) >= sz)
953 if (server_filter_list.head) {
956 len = strlen(partial_dir);
958 if (check_filter(&server_filter_list, partial_fname, 1) < 0)
961 if (check_filter(&server_filter_list, partial_fname, 0) < 0)
965 return partial_fname;
968 /* If no --partial-dir option was specified, we don't need to do anything
969 * (the partial-dir is essentially '.'), so just return success. */
970 int handle_partial_dir(const char *fname, int create)
974 if (fname != partial_fname)
976 if (!create && *partial_dir == '/')
978 if (!(fn = strrchr(partial_fname, '/')))
985 int statret = do_lstat(dir, &st);
986 if (statret == 0 && !S_ISDIR(st.st_mode)) {
987 if (do_unlink(dir) < 0)
991 if (statret < 0 && do_mkdir(dir, 0700) < 0)
1001 * Determine if a symlink points outside the current directory tree.
1002 * This is considered "unsafe" because e.g. when mirroring somebody
1003 * else's machine it might allow them to establish a symlink to
1004 * /etc/passwd, and then read it through a web server.
1006 * Null symlinks and absolute symlinks are always unsafe.
1008 * Basically here we are concerned with symlinks whose target contains
1009 * "..", because this might cause us to walk back up out of the
1010 * transferred directory. We are not allowed to go back up and
1013 * @param dest Target of the symlink in question.
1015 * @param src Top source directory currently applicable. Basically this
1016 * is the first parameter to rsync in a simple invocation, but it's
1017 * modified by flist.c in slightly complex ways.
1019 * @retval True if unsafe
1020 * @retval False is unsafe
1024 int unsafe_symlink(const char *dest, const char *src)
1026 const char *name, *slash;
1029 /* all absolute and null symlinks are unsafe */
1030 if (!dest || !*dest || *dest == '/')
1033 /* find out what our safety margin is */
1034 for (name = src; (slash = strchr(name, '/')) != 0; name = slash+1) {
1035 if (strncmp(name, "../", 3) == 0) {
1037 } else if (strncmp(name, "./", 2) == 0) {
1043 if (strcmp(name, "..") == 0)
1046 for (name = dest; (slash = strchr(name, '/')) != 0; name = slash+1) {
1047 if (strncmp(name, "../", 3) == 0) {
1048 /* if at any point we go outside the current directory
1049 then stop - it is unsafe */
1052 } else if (strncmp(name, "./", 2) == 0) {
1058 if (strcmp(name, "..") == 0)
1064 /* Return the int64 number as a string. If the --human-readable option was
1065 * specified, we may output the number in K, M, or G units. We can return
1066 * up to 4 buffers at a time. */
1067 char *human_num(int64 num)
1069 static char bufs[4][128]; /* more than enough room */
1070 static unsigned int n;
1073 n = (n + 1) % (sizeof bufs / sizeof bufs[0]);
1075 if (human_readable) {
1077 int mult = human_readable == 1 ? 1000 : 1024;
1079 if (num > mult*mult*mult) {
1080 dnum = (double)num / (mult*mult*mult);
1082 } else if (num > mult*mult) {
1083 dnum = (double)num / (mult*mult);
1085 } else if (num > mult) {
1086 dnum = (double)num / mult;
1090 sprintf(bufs[n], "%.2f%c", dnum, units);
1095 s = bufs[n] + sizeof bufs[0] - 1;
1101 *--s = (num % 10) + '0';
1107 /* Return the double number as a string. If the --human-readable option was
1108 * specified, we may output the number in K, M, or G units. We use a buffer
1109 * from human_num() to return our result. */
1110 char *human_dnum(double dnum, int decimal_digits)
1112 char *buf = human_num(dnum);
1113 int len = strlen(buf);
1114 if (isdigit(*(uchar*)(buf+len-1))) {
1115 /* There's extra room in buf prior to the start of the num. */
1116 buf -= decimal_digits + 1;
1117 snprintf(buf, len + decimal_digits + 2, "%.*f", decimal_digits, dnum);
1123 * Return the date and time as a string
1125 char *timestring(time_t t)
1127 static char TimeBuf[200];
1128 struct tm *tm = localtime(&t);
1131 #ifdef HAVE_STRFTIME
1132 strftime(TimeBuf, sizeof TimeBuf - 1, "%Y/%m/%d %H:%M:%S", tm);
1134 strlcpy(TimeBuf, asctime(tm), sizeof TimeBuf);
1137 if ((p = strchr(TimeBuf, '\n')) != NULL)
1144 * Sleep for a specified number of milliseconds.
1146 * Always returns TRUE. (In the future it might return FALSE if
1152 struct timeval tval, t1, t2;
1154 gettimeofday(&t1, NULL);
1157 tval.tv_sec = (t-tdiff)/1000;
1158 tval.tv_usec = 1000*((t-tdiff)%1000);
1161 select(0,NULL,NULL, NULL, &tval);
1163 gettimeofday(&t2, NULL);
1164 tdiff = (t2.tv_sec - t1.tv_sec)*1000 +
1165 (t2.tv_usec - t1.tv_usec)/1000;
1171 /* Determine if two time_t values are equivalent (either exact, or in
1172 * the modification timestamp window established by --modify-window).
1174 * @retval 0 if the times should be treated as the same
1176 * @retval +1 if the first is later
1178 * @retval -1 if the 2nd is later
1180 int cmp_time(time_t file1, time_t file2)
1182 if (file2 > file1) {
1183 if (file2 - file1 <= modify_window)
1187 if (file1 - file2 <= modify_window)
1197 This routine is a trick to immediately catch errors when debugging
1198 with insure. A xterm with a gdb is popped up when insure catches
1199 a error. It is Linux specific.
1201 int _Insure_trap_error(int a1, int a2, int a3, int a4, int a5, int a6)
1207 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'",
1208 getpid(), getpid(), getpid());
1212 h = dlopen("/usr/local/parasoft/insure++lite/lib.linux2/libinsure.so", RTLD_LAZY);
1213 fn = dlsym(h, "_Insure_trap_error");
1216 ret = fn(a1, a2, a3, a4, a5, a6);
1226 #define MALLOC_MAX 0x40000000
1228 void *_new_array(unsigned int size, unsigned long num)
1230 if (num >= MALLOC_MAX/size)
1232 return malloc(size * num);
1235 void *_realloc_array(void *ptr, unsigned int size, unsigned long num)
1237 if (num >= MALLOC_MAX/size)
1239 /* No realloc should need this, but just in case... */
1241 return malloc(size * num);
1242 return realloc(ptr, size * num);
1245 /* Take a filename and filename length and return the most significant
1246 * filename suffix we can find. This ignores suffixes such as "~",
1247 * ".bak", ".orig", ".~1~", etc. */
1248 const char *find_filename_suffix(const char *fn, int fn_len, int *len_ptr)
1250 const char *suf, *s;
1254 /* One or more dots at the start aren't a suffix. */
1255 while (fn_len && *fn == '.') fn++, fn_len--;
1257 /* Ignore the ~ in a "foo~" filename. */
1258 if (fn_len > 1 && fn[fn_len-1] == '~')
1259 fn_len--, had_tilde = True;
1263 /* Assume we don't find an suffix. */
1267 /* Find the last significant suffix. */
1268 for (s = fn + fn_len; fn_len > 1; ) {
1269 while (*--s != '.' && s != fn) {}
1272 s_len = fn_len - (s - fn);
1275 if (strcmp(s+1, "bak") == 0
1276 || strcmp(s+1, "old") == 0)
1278 } else if (s_len == 5) {
1279 if (strcmp(s+1, "orig") == 0)
1281 } else if (s_len > 2 && had_tilde
1282 && s[1] == '~' && isdigit(*(uchar*)(s+2)))
1288 /* Determine if the suffix is all digits. */
1289 for (s++, s_len--; s_len > 0; s++, s_len--) {
1290 if (!isdigit(*(uchar*)s))
1293 /* An all-digit suffix may not be that signficant. */
1300 /* This is an implementation of the Levenshtein distance algorithm. It
1301 * was implemented to avoid needing a two-dimensional matrix (to save
1302 * memory). It was also tweaked to try to factor in the ASCII distance
1303 * between changed characters as a minor distance quantity. The normal
1304 * Levenshtein units of distance (each signifying a single change between
1305 * the two strings) are defined as a "UNIT". */
1307 #define UNIT (1 << 16)
1309 uint32 fuzzy_distance(const char *s1, int len1, const char *s2, int len2)
1311 uint32 a[MAXPATHLEN], diag, above, left, diag_inc, above_inc, left_inc;
1315 if (!len1 || !len2) {
1320 for (i1 = 0, cost = 0; i1 < len1; i1++)
1322 return (int32)len1 * UNIT + cost;
1325 for (i2 = 0; i2 < len2; i2++)
1326 a[i2] = (i2+1) * UNIT;
1328 for (i1 = 0; i1 < len1; i1++) {
1330 above = (i1+1) * UNIT;
1331 for (i2 = 0; i2 < len2; i2++) {
1333 if ((cost = *((uchar*)s1+i1) - *((uchar*)s2+i2)) != 0) {
1339 diag_inc = diag + cost;
1340 left_inc = left + UNIT + *((uchar*)s1+i1);
1341 above_inc = above + UNIT + *((uchar*)s2+i2);
1342 a[i2] = above = left < above
1343 ? (left_inc < diag_inc ? left_inc : diag_inc)
1344 : (above_inc < diag_inc ? above_inc : diag_inc);
1352 #define BB_SLOT_SIZE (16*1024) /* Desired size in bytes */
1353 #define BB_PER_SLOT_BITS (BB_SLOT_SIZE * 8) /* Number of bits per slot */
1354 #define BB_PER_SLOT_INTS (BB_SLOT_SIZE / 4) /* Number of int32s per slot */
1361 struct bitbag *bitbag_create(int max_ndx)
1363 struct bitbag *bb = new(struct bitbag);
1364 bb->slot_cnt = (max_ndx + BB_PER_SLOT_BITS - 1) / BB_PER_SLOT_BITS;
1366 if (!(bb->bits = (uint32**)calloc(bb->slot_cnt, sizeof (uint32*))))
1367 out_of_memory("bitbag_create");
1372 void bitbag_set_bit(struct bitbag *bb, int ndx)
1374 int slot = ndx / BB_PER_SLOT_BITS;
1375 ndx %= BB_PER_SLOT_BITS;
1377 if (!bb->bits[slot]) {
1378 if (!(bb->bits[slot] = (uint32*)calloc(BB_PER_SLOT_INTS, 4)))
1379 out_of_memory("bitbag_set_bit");
1382 bb->bits[slot][ndx/32] |= 1u << (ndx % 32);
1385 #if 0 /* not needed yet */
1386 void bitbag_clear_bit(struct bitbag *bb, int ndx)
1388 int slot = ndx / BB_PER_SLOT_BITS;
1389 ndx %= BB_PER_SLOT_BITS;
1391 if (!bb->bits[slot])
1394 bb->bits[slot][ndx/32] &= ~(1u << (ndx % 32));
1397 int bitbag_check_bit(struct bitbag *bb, int ndx)
1399 int slot = ndx / BB_PER_SLOT_BITS;
1400 ndx %= BB_PER_SLOT_BITS;
1402 if (!bb->bits[slot])
1405 return bb->bits[slot][ndx/32] & (1u << (ndx % 32)) ? 1 : 0;
1409 /* Call this with -1 to start checking from 0. Returns -1 at the end. */
1410 int bitbag_next_bit(struct bitbag *bb, int after)
1413 int i, ndx = after + 1;
1414 int slot = ndx / BB_PER_SLOT_BITS;
1415 ndx %= BB_PER_SLOT_BITS;
1417 mask = (1u << (ndx % 32)) - 1;
1418 for (i = ndx / 32; slot < bb->slot_cnt; slot++, i = mask = 0) {
1419 if (!bb->bits[slot])
1421 for ( ; i < BB_PER_SLOT_INTS; i++, mask = 0) {
1422 if (!(bits = bb->bits[slot][i] & ~mask))
1424 /* The xor magic figures out the lowest enabled bit in
1425 * bits, and the switch quickly computes log2(bit). */
1426 switch (bits ^ (bits & (bits-1))) {
1427 #define LOG2(n) case 1u << n: return slot*BB_PER_SLOT_BITS + i*32 + n
1428 LOG2(0); LOG2(1); LOG2(2); LOG2(3);
1429 LOG2(4); LOG2(5); LOG2(6); LOG2(7);
1430 LOG2(8); LOG2(9); LOG2(10); LOG2(11);
1431 LOG2(12); LOG2(13); LOG2(14); LOG2(15);
1432 LOG2(16); LOG2(17); LOG2(18); LOG2(19);
1433 LOG2(20); LOG2(21); LOG2(22); LOG2(23);
1434 LOG2(24); LOG2(25); LOG2(26); LOG2(27);
1435 LOG2(28); LOG2(29); LOG2(30); LOG2(31);
1437 return -1; /* impossible... */