util.c

Rsync 3.0.5 source code

}

/* If no --partial-dir option was specified, we don't need to do anything
 * (the partial-dir is essentially '.'), so just return success. */
int handle_partial_dir(const char *fname, int create)
{
	char *fn, *dir;

	if (fname != partial_fname)
		return 1;
	if (!create && *partial_dir == '/')
		return 1;
	if (!(fn = strrchr(partial_fname, '/')))
		return 1;

	*fn = '\0';
	dir = partial_fname;
	if (create) {
		STRUCT_STAT st;
		int statret = do_lstat(dir, &st);
		if (statret == 0 && !S_ISDIR(st.st_mode)) {
			if (do_unlink(dir) < 0) {
				*fn = '/';
				return 0;
			}
			statret = -1;
		}
		if (statret < 0 && do_mkdir(dir, 0700) < 0) {
			*fn = '/';
			return 0;
		}
	} else
		do_rmdir(dir);
	*fn = '/';

	return 1;
}

/**
 * Determine if a symlink points outside the current directory tree.
 * This is considered "unsafe" because e.g. when mirroring somebody
 * else's machine it might allow them to establish a symlink to
 * /etc/passwd, and then read it through a web server.
 *
 * Null symlinks and absolute symlinks are always unsafe.
 *
 * Basically here we are concerned with symlinks whose target contains
 * "..", because this might cause us to walk back up out of the
 * transferred directory.  We are not allowed to go back up and
 * reenter.
 *
 * @param dest Target of the symlink in question.
 *
 * @param src Top source directory currently applicable.  Basically this
 * is the first parameter to rsync in a simple invocation, but it's
 * modified by flist.c in slightly complex ways.
 *
 * @retval True if unsafe
 * @retval False is unsafe
 *
 * @sa t_unsafe.c
 **/
int unsafe_symlink(const char *dest, const char *src)
{
	const char *name, *slash;
	int depth = 0;

	/* all absolute and null symlinks are unsafe */
	if (!dest || !*dest || *dest == '/')
		return 1;

	/* find out what our safety margin is */
	for (name = src; (slash = strchr(name, '/')) != 0; name = slash+1) {
		if (strncmp(name, "../", 3) == 0) {
			depth = 0;
		} else if (strncmp(name, "./", 2) == 0) {
			/* nothing */
		} else {
			depth++;
		}
	}
	if (strcmp(name, "..") == 0)
		depth = 0;

	for (name = dest; (slash = strchr(name, '/')) != 0; name = slash+1) {
		if (strncmp(name, "../", 3) == 0) {
			/* if at any point we go outside the current directory
			   then stop - it is unsafe */
			if (--depth < 0)
				return 1;
		} else if (strncmp(name, "./", 2) == 0) {
			/* nothing */
		} else {
			depth++;
		}
	}
	if (strcmp(name, "..") == 0)
		depth--;

	return (depth < 0);
}

#define HUMANIFY(mult) \
	do { \
		if (num >= mult || num <= -mult) { \
			double dnum = (double)num / mult; \
			char units; \
			if (num < 0) \
				dnum = -dnum; \
			if (dnum < mult) \
				units = 'K'; \
			else if ((dnum /= mult) < mult) \
				units = 'M'; \
			else { \
				dnum /= mult; \
				units = 'G'; \
			} \
			if (num < 0) \
				dnum = -dnum; \
			snprintf(bufs[n], sizeof bufs[0], "%.2f%c", dnum, units); \
			return bufs[n]; \
		} \
	} while (0)

/* Return the int64 number as a string.  If the --human-readable option was
 * specified, we may output the number in K, M, or G units.  We can return
 * up to 4 buffers at a time. */
char *human_num(int64 num)
{
	static char bufs[4][128]; /* more than enough room */
	static unsigned int n;
	char *s;
	int negated;

	n = (n + 1) % (sizeof bufs / sizeof bufs[0]);

	if (human_readable) {
		if (human_readable == 1)
			HUMANIFY(1000);
		else
			HUMANIFY(1024);
	}

	s = bufs[n] + sizeof bufs[0] - 1;
	*s = '\0';

	if (!num)
		*--s = '0';
	if (num < 0) {
		/* A maximum-size negated number can't fit as a positive,
		 * so do one digit in negated form to start us off. */
		*--s = (char)(-(num % 10)) + '0';
		num = -(num / 10);
		negated = 1;
	} else
		negated = 0;

	while (num) {
		*--s = (char)(num % 10) + '0';
		num /= 10;
	}

	if (negated)
		*--s = '-';

	return s;
}

/* Return the double number as a string.  If the --human-readable option was
 * specified, we may output the number in K, M, or G units.  We use a buffer
 * from human_num() to return our result. */
char *human_dnum(double dnum, int decimal_digits)
{
	char *buf = human_num(dnum);
	int len = strlen(buf);
	if (isDigit(buf + len - 1)) {
		/* There's extra room in buf prior to the start of the num. */
		buf -= decimal_digits + 2;
		snprintf(buf, len + decimal_digits + 3, "%.*f", decimal_digits, dnum);
	}
	return buf;
}

/* Return the date and time as a string.  Some callers tweak returned buf. */
char *timestring(time_t t)
{
	static char TimeBuf[200];
	struct tm *tm = localtime(&t);
	char *p;

#ifdef HAVE_STRFTIME
	strftime(TimeBuf, sizeof TimeBuf - 1, "%Y/%m/%d %H:%M:%S", tm);
#else
	strlcpy(TimeBuf, asctime(tm), sizeof TimeBuf);
#endif

	if ((p = strchr(TimeBuf, '\n')) != NULL)
		*p = '\0';

	return TimeBuf;
}

/**
 * Sleep for a specified number of milliseconds.
 *
 * Always returns TRUE.  (In the future it might return FALSE if
 * interrupted.)
 **/
int msleep(int t)
{
	int tdiff = 0;
	struct timeval tval, t1, t2;

	gettimeofday(&t1, NULL);

	while (tdiff < t) {
		tval.tv_sec = (t-tdiff)/1000;
		tval.tv_usec = 1000*((t-tdiff)%1000);

		errno = 0;
		select(0,NULL,NULL, NULL, &tval);

		gettimeofday(&t2, NULL);
		tdiff = (t2.tv_sec - t1.tv_sec)*1000 +
			(t2.tv_usec - t1.tv_usec)/1000;
	}

	return True;
}

/* Determine if two time_t values are equivalent (either exact, or in
 * the modification timestamp window established by --modify-window).
 *
 * @retval 0 if the times should be treated as the same
 *
 * @retval +1 if the first is later
 *
 * @retval -1 if the 2nd is later
 **/
int cmp_time(time_t file1, time_t file2)
{
	if (file2 > file1) {
		if (file2 - file1 <= modify_window)
			return 0;
		return -1;
	}
	if (file1 - file2 <= modify_window)
		return 0;
	return 1;
}


#ifdef __INSURE__XX
#include <dlfcn.h>

/**
   This routine is a trick to immediately catch errors when debugging
   with insure. A xterm with a gdb is popped up when insure catches
   a error. It is Linux specific.
**/
int _Insure_trap_error(int a1, int a2, int a3, int a4, int a5, int a6)
{
	static int (*fn)();
	int ret;
	char *cmd;

	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'",
		getpid(), getpid(), getpid());

	if (!fn) {
		static void *h;
		h = dlopen("/usr/local/parasoft/insure++lite/lib.linux2/libinsure.so", RTLD_LAZY);
		fn = dlsym(h, "_Insure_trap_error");
	}

	ret = fn(a1, a2, a3, a4, a5, a6);

	system(cmd);

	free(cmd);

	return ret;
}
#endif

#define MALLOC_MAX 0x40000000

void *_new_array(unsigned long num, unsigned int size, int use_calloc)
{
	if (num >= MALLOC_MAX/size)
		return NULL;
	return use_calloc ? calloc(num, size) : malloc(num * size);
}

void *_realloc_array(void *ptr, unsigned int size, size_t num)
{
	if (num >= MALLOC_MAX/size)
		return NULL;
	if (!ptr)
		return malloc(size * num);
	return realloc(ptr, size * num);
}

/* Take a filename and filename length and return the most significant
 * filename suffix we can find.  This ignores suffixes such as "~",
 * ".bak", ".orig", ".~1~", etc. */
const char *find_filename_suffix(const char *fn, int fn_len, int *len_ptr)
{
	const char *suf, *s;
	BOOL had_tilde;
	int s_len;

	/* One or more dots at the start aren't a suffix. */
	while (fn_len && *fn == '.') fn++, fn_len--;

	/* Ignore the ~ in a "foo~" filename. */
	if (fn_len > 1 && fn[fn_len-1] == '~')
		fn_len--, had_tilde = True;
	else
		had_tilde = False;

	/* Assume we don't find an suffix. */
	suf = "";
	*len_ptr = 0;

	/* Find the last significant suffix. */
	for (s = fn + fn_len; fn_len > 1; ) {
		while (*--s != '.' && s != fn) {}
		if (s == fn)
			break;
		s_len = fn_len - (s - fn);
		fn_len = s - fn;
		if (s_len == 4) {
			if (strcmp(s+1, "bak") == 0
			 || strcmp(s+1, "old") == 0)
				continue;
		} else if (s_len == 5) {
			if (strcmp(s+1, "orig") == 0)
				continue;
		} else if (s_len > 2 && had_tilde
		    && s[1] == '~' && isDigit(s + 2))
			continue;
		*len_ptr = s_len;
		suf = s;
		if (s_len == 1)
			break;
		/* Determine if the suffix is all digits. */
		for (s++, s_len--; s_len > 0; s++, s_len--) {
			if (!isDigit(s))
				return suf;
		}
		/* An all-digit suffix may not be that signficant. */
		s = suf;
	}

	return suf;
}

/* This is an implementation of the Levenshtein distance algorithm.  It
 * was implemented to avoid needing a two-dimensional matrix (to save
 * memory).  It was also tweaked to try to factor in the ASCII distance
 * between changed characters as a minor distance quantity.  The normal
 * Levenshtein units of distance (each signifying a single change between
 * the two strings) are defined as a "UNIT". */

#define UNIT (1 << 16)

uint32 fuzzy_distance(const char *s1, int len1, const char *s2, int len2)
{
	uint32 a[MAXPATHLEN], diag, above, left, diag_inc, above_inc, left_inc;
	int32 cost;
	int i1, i2;

	if (!len1 || !len2) {
		if (!len1) {
			s1 = s2;
			len1 = len2;
		}
		for (i1 = 0, cost = 0; i1 < len1; i1++)
			cost += s1[i1];
		return (int32)len1 * UNIT + cost;
	}

	for (i2 = 0; i2 < len2; i2++)
		a[i2] = (i2+1) * UNIT;

	for (i1 = 0; i1 < len1; i1++) {
		diag = i1 * UNIT;
		above = (i1+1) * UNIT;
		for (i2 = 0; i2 < len2; i2++) {
			left = a[i2];
			if ((cost = *((uchar*)s1+i1) - *((uchar*)s2+i2)) != 0) {
				if (cost < 0)
					cost = UNIT - cost;
				else
					cost = UNIT + cost;
			}
			diag_inc = diag + cost;
			left_inc = left + UNIT + *((uchar*)s1+i1);
			above_inc = above + UNIT + *((uchar*)s2+i2);
			a[i2] = above = left < above
			      ? (left_inc < diag_inc ? left_inc : diag_inc)
			      : (above_inc < diag_inc ? above_inc : diag_inc);
			diag = left;
		}
	}

	return a[len2-1];
}

#define BB_SLOT_SIZE     (16*1024)          /* Desired size in bytes */
#define BB_PER_SLOT_BITS (BB_SLOT_SIZE * 8) /* Number of bits per slot */
#define BB_PER_SLOT_INTS (BB_SLOT_SIZE / 4) /* Number of int32s per slot */

struct bitbag {
    uint32 **bits;
    int slot_cnt;
};

struct bitbag *bitbag_create(int max_ndx)
{
	struct bitbag *bb = new(struct bitbag);
	bb->slot_cnt = (max_ndx + BB_PER_SLOT_BITS - 1) / BB_PER_SLOT_BITS;

	if (!(bb->bits = (uint32**)calloc(bb->slot_cnt, sizeof (uint32*))))
		out_of_memory("bitbag_create");

	return bb;
}

void bitbag_set_bit(struct bitbag *bb, int ndx)
{
	int slot = ndx / BB_PER_SLOT_BITS;
	ndx %= BB_PER_SLOT_BITS;

	if (!bb->bits[slot]) {
		if (!(bb->bits[slot] = (uint32*)calloc(BB_PER_SLOT_INTS, 4)))
			out_of_memory("bitbag_set_bit");
	}

	bb->bits[slot][ndx/32] |= 1u << (ndx % 32);
}

#if 0 /* not needed yet */
void bitbag_clear_bit(struct bitbag *bb, int ndx)
{
	int slot = ndx / BB_PER_SLOT_BITS;
	ndx %= BB_PER_SLOT_BITS;

	if (!bb->bits[slot])
		return;

	bb->bits[slot][ndx/32] &= ~(1u << (ndx % 32));
}

int bitbag_check_bit(struct bitbag *bb, int ndx)
{
	int slot = ndx / BB_PER_SLOT_BITS;
	ndx %= BB_PER_SLOT_BITS;

	if (!bb->bits[slot])
		return 0;

	return bb->bits[slot][ndx/32] & (1u << (ndx % 32)) ? 1 : 0;
}
#endif

/* Call this with -1 to start checking from 0.  Returns -1 at the end. */
int bitbag_next_bit(struct bitbag *bb, int after)
{
	uint32 bits, mask;
	int i, ndx = after + 1;
	int slot = ndx / BB_PER_SLOT_BITS;
	ndx %= BB_PER_SLOT_BITS;

	mask = (1u << (ndx % 32)) - 1;
	for (i = ndx / 32; slot < bb->slot_cnt; slot++, i = mask = 0) {
		if (!bb->bits[slot])
			continue;
		for ( ; i < BB_PER_SLOT_INTS; i++, mask = 0) {
			if (!(bits = bb->bits[slot][i] & ~mask))
				continue;
			/* The xor magic figures out the lowest enabled bit in
			 * bits, and the switch quickly computes log2(bit). */
			switch (bits ^ (bits & (bits-1))) {
#define LOG2(n) case 1u << n: return slot*BB_PER_SLOT_BITS + i*32 + n
			    LOG2(0);  LOG2(1);  LOG2(2);  LOG2(3);
			    LOG2(4);  LOG2(5);  LOG2(6);  LOG2(7);
			    LOG2(8);  LOG2(9);  LOG2(10); LOG2(11);
			    LOG2(12); LOG2(13); LOG2(14); LOG2(15);
			    LOG2(16); LOG2(17); LOG2(18); LOG2(19);
			    LOG2(20); LOG2(21); LOG2(22); LOG2(23);
			    LOG2(24); LOG2(25); LOG2(26); LOG2(27);
			    LOG2(28); LOG2(29); LOG2(30); LOG2(31);
			}
			return -1; /* impossible... */
		}
	}

	return -1;
}

void flist_ndx_push(flist_ndx_list *lp, int ndx)
{
	struct flist_ndx_item *item;

	if (!(item = new(struct flist_ndx_item)))
		out_of_memory("flist_ndx_push");
	item->next = NULL;
	item->ndx = ndx;
	if (lp->tail)
		lp->tail->next = item;
	else
		lp->head = item;
	lp->tail = item;
}

int flist_ndx_pop(flist_ndx_list *lp)
{
	struct flist_ndx_item *next;
	int ndx;

	if (!lp->head)
		return -1;

	ndx = lp->head->ndx;
	next = lp->head->next;
	free(lp->head);
	lp->head = next;
	if (!next)
		lp->tail = NULL;

	return ndx;
}

void *expand_item_list(item_list *lp, size_t item_size,
		       const char *desc, int incr)
{
	/* First time through, 0 <= 0, so list is expanded. */
	if (lp->malloced <= lp->count) {
		void *new_ptr;
		size_t new_size = lp->malloced;
		if (incr < 0)
			new_size += -incr; /* increase slowly */
		else if (new_size < (size_t)incr)
			new_size += incr;
		else
			new_size *= 2;
		if (new_size < lp->malloced)
			overflow_exit("expand_item_list");
		/* Using _realloc_array() lets us pass the size, not a type. */
		new_ptr = _realloc_array(lp->items, item_size, new_size);
		if (verbose >= 4) {
			rprintf(FINFO, "[%s] expand %s to %.0f bytes, did%s move\n",
				who_am_i(), desc, (double)new_size * item_size,
				new_ptr == lp->items ? " not" : "");
		}
		if (!new_ptr)
			out_of_memory("expand_item_list");

		lp->items = new_ptr;
		lp->malloced = new_size;
	}
	return (char*)lp->items + (lp->count++ * item_size);
}