patchcommon_prefix: be more careful about pathspec bounds

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.

Normally this won't be a problem, which is probably why nobody has noticed that this was broken since 2006. Even if we find a slash somewhere beyond the actual contents of 'next', the memcmp after it can never match because of the terminating NUL. However, if we are unlucky and 'next' is right before a page boundary, we may not have any read access beyond it.

To fix, only set len to prefix-1 if that is actually inside 'next', i.e., reduces the available length. As explained in the last paragraph, increasing the length never results in more matches.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

Found by valgrind.

 dir.c |    8 +++++---
 1 files changed, 5 insertions(+), 3 deletions(-)

Thomas Rast wrote:

Actually I just noticed it's not from back in 2006 when Linus wrote this code, but from the following:

commit c7f34c180b7117cf60ad12a8b180eed33716e390
Author: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Date:   Mon Apr 23 10:21:25 2007 +0200

    dir.c(common_prefix): Fix two bugs
    
    The function common_prefix() is used to find the common subdirectory of
    a couple of pathnames. When checking if the next pathname matches up with
    the prefix, it incorrectly checked the whole path, not just the prefix
    (including the slash). Thus, the expensive part of the loop was executed
    always.
    
    The other bug is more serious: if the first and the last pathname in the
    list have a longer common prefix than the common prefix for _all_ pathnames
    in the list, the longer one would be chosen. This bug was probably hidden
    by the fact that bash's wildcard expansion sorts the results, and the code
    just so happens to work with sorted input.
[...]

Hi,

On Tue, 15 Jun 2010, Thomas Rast wrote:

Sorry, my Git time budget for this week was 0 hours, so I used that up quite thoroughly. Besides, I do not know anything about the original issue, so there is little chance that I even would know where to start.

Ciao, Dscho

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

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;
}

Junio C Hamano <gitster@pobox.com> writes:

Another way of saying this, which probably needs less number of scans, would be to shorten prefix to what is known to match --- use of memcmp() discards this information.

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, last_matching_slash = -1;
		for (len = 0;
		     len < prefix && next[len] == path[len];
		     len++)
			if (next[len] == '/')
				last_matching_slash = len;
		if (len == prefix)
			continue;
		if (last_matching_slash < 0)
			return 0;
		prefix = last_matching_slash + 1;
	}
	return prefix;
}

Junio C Hamano wrote:

[...]

I really didn't like the two-interleaved-loops version in your last mail, but this one is way more readable than even the original.

(Why did you wrap the for loop? It's only 76 chars.)

Maybe you could add a comment like

	/* The first 'prefix' characters of 'path' always include the
	   trailing slash of the prefix directory */

to clean up any doubts about the correctness of the matching.

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

Because I was writing it in my MUA ;-)

Perhaps..

From: Junio C Hamano <gitster@pobox.com>

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 is a small opportunity for an out-of-bounds access because 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.

Instead of a minimal fix, simplify the loop: scan *forward* over the 'next' entry, remembering the last '/' where it matched the prefix known so far. This is far easier to read and also has the advantage that we only scan over each entry once.

Acked-by: Thomas Rast <trast@student.ethz.ch>
---

Junio C Hamano wrote:

Well then, perhaps I can at least repay the favour by suggesting a commit message.

 dir.c |   21 ++++++++-------------
 1 files changed, 8 insertions(+), 13 deletions(-)