Re: [PATCH] common_prefix: be more careful about pathspec bounds

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 15, 2010, 15:05 UTC
Message-ID: <7v8w6g8hfx.fsf@alter.siamese.dyndns.org>
In-Reply-To: <825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch>

Thomas Rast <trast@student.ethz.ch> writes:

Show 33 quoted lines

> common_prefix() scans backwards from the far end of each 'next'
> pathspec, starting from 'len', shortening the 'prefix' using 'path' as
> a reference.
>
> However, there was a small opportunity for an out-of-bounds access:
> len is unconditionally set to prefix-1 after a "direct match" test
> failed.  This means that if 'next' is shorter than prefix+2, we read
> past it.
> ...
> Found by valgrind.
>
>  dir.c |    8 +++++---
>  1 files changed, 5 insertions(+), 3 deletions(-)
>
> diff --git a/dir.c b/dir.c
> index 5615f33..ca689ff 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -34,9 +34,11 @@ static int common_prefix(const char **pathspec)
>  	prefix = slash - path + 1;
>  	while ((next = *++pathspec) != NULL) {
>  		int len = strlen(next);
> -		if (len >= prefix && !memcmp(path, next, prefix))
> -			continue;
> -		len = prefix - 1;
> +		if (len >= prefix) {
> +			if (!memcmp(path, next, prefix))
> +				continue;
> +			len = prefix - 1;
> +		}
>  		for (;;) {
>  			if (!len)
>  				return 0;

The structure of this loop is somewhat curious. It starts out by setting prefix based on what is found in "path" (i.e. the first proposed common prefix is the longest leading directory path of "path"), and when it finds that the prefix being considered does not match "next", it uses what is found in "next" to shorten it.

Isn't it more intuitive to structure the loop by saying 'Ok, if "path" up to the currently proposed "prefix" is too long to match, let's shorten it by one path component and try again'? IOW, something like...

static int common_prefix(const char **pathspec)
{
	const char *path, *slash, *next;
	int prefix;

	if (!pathspec)
		return 0;

	path = *pathspec;
	slash = strrchr(path, '/');
	if (!slash)
		return 0;

	prefix = slash - path + 1;
	while ((next = *++pathspec) != NULL) {
		int len;
	again:
		len = strlen(next);
		if (len > prefix && !memcmp(path, next, prefix))
			continue;
		while (0 < --prefix && path[prefix - 1] != '/')
			;
		if (!prefix)
			break;
		goto again;
	}
	return prefix;
}