# [PATCH] common_prefix: be more careful about pathspec bounds 8 messages from 2010-06-10 to 2010-06-15. Participants: Thomas Rast, Johannes Schindelin, Junio C Hamano. Thread: https://gitlist.dev/t/24074 ## Thomas Rast, 2010-06-10 18:24 Subject: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch> URL: https://gitlist.dev/e/825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast%40student.ethz.ch ``` 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 --- 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; -- 1.7.1.553.ga798e ``` ## Thomas Rast, 2010-06-15 08:16 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <201006151016.16492.trast@student.ethz.ch> URL: https://gitlist.dev/e/201006151016.16492.trast%40student.ethz.ch In-Reply-To: <825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch> ``` Thomas Rast wrote: > Normally this won't be a problem, which is probably why nobody has > noticed that this was broken since 2006. 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 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. [...] --- a/dir.c +++ b/dir.c @@ -24,8 +24,9 @@ int common_prefix(const char **pathspec) prefix = slash - path + 1; while ((next = *++pathspec) != NULL) { int len = strlen(next); - if (len >= prefix && !memcmp(path, next, len)) + if (len >= prefix && !memcmp(path, next, prefix)) continue; + len = prefix - 1; for (;;) { if (!len) return 0; -- Thomas Rast trast@{inf,student}.ethz.ch ``` ## Johannes Schindelin, 2010-06-15 09:05 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: URL: https://gitlist.dev/e/alpine.DEB.1.00.1006151104300.25388%40bonsai2 In-Reply-To: <201006151016.16492.trast@student.ethz.ch> ``` Hi, On Tue, 15 Jun 2010, Thomas Rast wrote: > Thomas Rast wrote: > > Normally this won't be a problem, which is probably why nobody has > > noticed that this was broken since 2006. > > 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 > Date: Mon Apr 23 10:21:25 2007 +0200 > > dir.c(common_prefix): Fix two bugs 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 ``` ## Junio C Hamano, 2010-06-15 15:05 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <7v8w6g8hfx.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v8w6g8hfx.fsf%40alter.siamese.dyndns.org In-Reply-To: <825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch> ``` Thomas Rast writes: > 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; } ``` ## Junio C Hamano, 2010-06-15 16:06 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <7v4oh48elm.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7v4oh48elm.fsf%40alter.siamese.dyndns.org In-Reply-To: <7v8w6g8hfx.fsf@alter.siamese.dyndns.org> ``` Junio C Hamano writes: > 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'? 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; } ``` ## Thomas Rast, 2010-06-15 18:04 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <201006152004.01507.trast@student.ethz.ch> URL: https://gitlist.dev/e/201006152004.01507.trast%40student.ethz.ch In-Reply-To: <7v4oh48elm.fsf@alter.siamese.dyndns.org> ``` Junio C Hamano wrote: > Junio C Hamano writes: > > > 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'? > > 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. [...] > 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; > } 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 > slash = strrchr(path, '/'); > if (!slash) > return 0; /* The first 'prefix' characters of 'path' always include the trailing slash of the prefix directory */ > prefix = slash - path + 1; to clean up any doubts about the correctness of the matching. -- Thomas Rast trast@{inf,student}.ethz.ch ``` ## Junio C Hamano, 2010-06-15 22:12 Subject: Re: [PATCH] common_prefix: be more careful about pathspec bounds Message-ID: <7vaaqwgd2q.fsf@alter.siamese.dyndns.org> URL: https://gitlist.dev/e/7vaaqwgd2q.fsf%40alter.siamese.dyndns.org In-Reply-To: <201006152004.01507.trast@student.ethz.ch> ``` Thomas Rast writes: > 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.) Because I was writing it in my MUA ;-) > > Maybe you could add a comment like > >> slash = strrchr(path, '/'); >> if (!slash) >> return 0; > /* The first 'prefix' characters of 'path' always include the > trailing slash of the prefix directory */ >> prefix = slash - path + 1; > > to clean up any doubts about the correctness of the matching. Perhaps.. ``` ## Thomas Rast, 2010-06-15 23:02 Subject: [PATCH] common_prefix: simplify and fix scanning for prefixes Message-ID: URL: https://gitlist.dev/e/f023050aede65c3cc6d9fdf0067c142dc0257c72.1276642610.git.trast%40student.ethz.ch In-Reply-To: <7vaaqwgd2q.fsf@alter.siamese.dyndns.org> ``` From: Junio C Hamano 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 --- Junio C Hamano wrote: > Thomas Rast writes: > > 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.) > > Because I was writing it in my MUA ;-) 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(-) diff --git a/dir.c b/dir.c index 5e36f8e..78eb869 100644 --- a/dir.c +++ b/dir.c @@ -33,20 +33,15 @@ 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)) + 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; - len = prefix - 1; - for (;;) { - if (!len) - return 0; - if (next[--len] != '/') - continue; - if (memcmp(path, next, len+1)) - continue; - prefix = len + 1; - break; - } + if (last_matching_slash < 0) + return 0; + prefix = last_matching_slash + 1; } return prefix; } -- 1.7.1.608.g80d39f ```