{"thread":{"id":"24074","subject":"[PATCH] common_prefix: be more careful about pathspec bounds","startedAt":"2010-06-10T18:24:20Z","lastAt":"2010-06-15T23:02:03Z","messageCount":8,"participants":["Thomas Rast","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"143464","messageId":"825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch","threadId":"24074","inReplyTo":null,"subject":"[PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-06-10T18:24:20Z","receivedAt":"2010-06-10T18:24:20Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"common_prefix() scans backwards from the far end of each 'next'\npathspec, starting from 'len', shortening the 'prefix' using 'path' as\na reference.\n\nHowever, there was a small opportunity for an out-of-bounds access:\nlen is unconditionally set to prefix-1 after a \"direct match\" test\nfailed. This means that if 'next' is shorter than prefix+2, we read\npast it.\n\nNormally this won't be a problem, which is probably why nobody has\nnoticed that this was broken since 2006. Even if we find a slash\nsomewhere beyond the actual contents of 'next', the memcmp after it\ncan never match because of the terminating NUL. However, if we are\nunlucky and 'next' is right before a page boundary, we may not have\nany read access beyond it.\n\nTo fix, only set len to prefix-1 if that is actually inside 'next',\ni.e., reduces the available length. As explained in the last\nparagraph, increasing the length never results in more matches.\n\nSigned-off-by: Thomas Rast \n---\n\nFound by valgrind.\n\n dir.c | 8 +++++---\n 1 files changed, 5 insertions(+), 3 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 5615f33..ca689ff 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -34,9 +34,11 @@ static int common_prefix(const char **pathspec)\n \tprefix = slash - path + 1;\n \twhile ((next = *++pathspec) != NULL) {\n \t\tint len = strlen(next);\n-\t\tif (len >= prefix && !memcmp(path, next, prefix))\n-\t\t\tcontinue;\n-\t\tlen = prefix - 1;\n+\t\tif (len >= prefix) {\n+\t\t\tif (!memcmp(path, next, prefix))\n+\t\t\t\tcontinue;\n+\t\t\tlen = prefix - 1;\n+\t\t}\n \t\tfor (;;) {\n \t\t\tif (!len)\n \t\t\t\treturn 0;\n-- \n1.7.1.553.ga798e\n"},{"id":"143725","messageId":"201006151016.16492.trast@student.ethz.ch","threadId":"24074","inReplyTo":"825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-06-15T08:16:16Z","receivedAt":"2010-06-15T08:16:16Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast wrote:\n> Normally this won't be a problem, which is probably why nobody has\n> noticed that this was broken since 2006.\n\nActually I just noticed it's not from back in 2006 when Linus wrote\nthis code, but from the following:\n\ncommit c7f34c180b7117cf60ad12a8b180eed33716e390\nAuthor: Johannes Schindelin \nDate: Mon Apr 23 10:21:25 2007 +0200\n\n dir.c(common_prefix): Fix two bugs\n \n The function common_prefix() is used to find the common subdirectory of\n a couple of pathnames. When checking if the next pathname matches up with\n the prefix, it incorrectly checked the whole path, not just the prefix\n (including the slash). Thus, the expensive part of the loop was executed\n always.\n \n The other bug is more serious: if the first and the last pathname in the\n list have a longer common prefix than the common prefix for _all_ pathnames\n in the list, the longer one would be chosen. This bug was probably hidden\n by the fact that bash's wildcard expansion sorts the results, and the code\n just so happens to work with sorted input.\n[...]\n--- a/dir.c\n+++ b/dir.c\n@@ -24,8 +24,9 @@ int common_prefix(const char **pathspec)\n prefix = slash - path + 1;\n while ((next = *++pathspec) != NULL) {\n int len = strlen(next);\n- if (len >= prefix && !memcmp(path, next, len))\n+ if (len >= prefix && !memcmp(path, next, prefix))\n continue;\n+ len = prefix - 1;\n for (;;) {\n if (!len)\n return 0;\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"143726","messageId":"alpine.DEB.1.00.1006151104300.25388@bonsai2","threadId":"24074","inReplyTo":"201006151016.16492.trast@student.ethz.ch","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2010-06-15T09:05:36Z","receivedAt":"2010-06-15T09:05:36Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 15 Jun 2010, Thomas Rast wrote:\n\n> Thomas Rast wrote:\n> > Normally this won't be a problem, which is probably why nobody has\n> > noticed that this was broken since 2006.\n> \n> Actually I just noticed it's not from back in 2006 when Linus wrote\n> this code, but from the following:\n> \n> commit c7f34c180b7117cf60ad12a8b180eed33716e390\n> Author: Johannes Schindelin \n> Date: Mon Apr 23 10:21:25 2007 +0200\n> \n> dir.c(common_prefix): Fix two bugs\n\nSorry, my Git time budget for this week was 0 hours, so I used that up \nquite thoroughly. Besides, I do not know anything about the original \nissue, so there is little chance that I even would know where to start.\n\nCiao,\nDscho\n"},{"id":"143749","messageId":"7v8w6g8hfx.fsf@alter.siamese.dyndns.org","threadId":"24074","inReplyTo":"825550ec93610c2d3c7dae7550729d96fc6cebbc.1276194169.git.trast@student.ethz.ch","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-06-15T15:05:22Z","receivedAt":"2010-06-15T15:05:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> common_prefix() scans backwards from the far end of each 'next'\n> pathspec, starting from 'len', shortening the 'prefix' using 'path' as\n> a reference.\n>\n> However, there was a small opportunity for an out-of-bounds access:\n> len is unconditionally set to prefix-1 after a \"direct match\" test\n> failed. This means that if 'next' is shorter than prefix+2, we read\n> past it.\n> ...\n> Found by valgrind.\n>\n> dir.c | 8 +++++---\n> 1 files changed, 5 insertions(+), 3 deletions(-)\n>\n> diff --git a/dir.c b/dir.c\n> index 5615f33..ca689ff 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -34,9 +34,11 @@ static int common_prefix(const char **pathspec)\n> \tprefix = slash - path + 1;\n> \twhile ((next = *++pathspec) != NULL) {\n> \t\tint len = strlen(next);\n> -\t\tif (len >= prefix && !memcmp(path, next, prefix))\n> -\t\t\tcontinue;\n> -\t\tlen = prefix - 1;\n> +\t\tif (len >= prefix) {\n> +\t\t\tif (!memcmp(path, next, prefix))\n> +\t\t\t\tcontinue;\n> +\t\t\tlen = prefix - 1;\n> +\t\t}\n> \t\tfor (;;) {\n> \t\t\tif (!len)\n> \t\t\t\treturn 0;\n\nThe structure of this loop is somewhat curious. It starts out by setting\nprefix based on what is found in \"path\" (i.e. the first proposed common\nprefix is the longest leading directory path of \"path\"), and when it finds\nthat the prefix being considered does not match \"next\", it uses what is\nfound in \"next\" to shorten it.\n\nIsn't it more intuitive to structure the loop by saying 'Ok, if \"path\" up\nto the currently proposed \"prefix\" is too long to match, let's shorten it\nby one path component and try again'? IOW, something like...\n\nstatic int common_prefix(const char **pathspec)\n{\n\tconst char *path, *slash, *next;\n\tint prefix;\n\n\tif (!pathspec)\n\t\treturn 0;\n\n\tpath = *pathspec;\n\tslash = strrchr(path, '/');\n\tif (!slash)\n\t\treturn 0;\n\n\tprefix = slash - path + 1;\n\twhile ((next = *++pathspec) != NULL) {\n\t\tint len;\n\tagain:\n\t\tlen = strlen(next);\n\t\tif (len > prefix && !memcmp(path, next, prefix))\n\t\t\tcontinue;\n\t\twhile (0 < --prefix && path[prefix - 1] != '/')\n\t\t\t;\n\t\tif (!prefix)\n\t\t\tbreak;\n\t\tgoto again;\n\t}\n\treturn prefix;\n}\n"},{"id":"143754","messageId":"7v4oh48elm.fsf@alter.siamese.dyndns.org","threadId":"24074","inReplyTo":"7v8w6g8hfx.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-06-15T16:06:45Z","receivedAt":"2010-06-15T16:06:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Isn't it more intuitive to structure the loop by saying 'Ok, if \"path\" up\n> to the currently proposed \"prefix\" is too long to match, let's shorten it\n> by one path component and try again'?\n\nAnother way of saying this, which probably needs less number of scans,\nwould be to shorten prefix to what is known to match --- use of memcmp()\ndiscards this information.\n\nstatic int common_prefix(const char **pathspec)\n{\n\tconst char *path, *slash, *next;\n\tint prefix;\n\n\tif (!pathspec)\n\t\treturn 0;\n\n\tpath = *pathspec;\n\tslash = strrchr(path, '/');\n\tif (!slash)\n\t\treturn 0;\n\tprefix = slash - path + 1;\n\n\twhile ((next = *++pathspec) != NULL) {\n\t\tint len, last_matching_slash = -1;\n\t\tfor (len = 0;\n\t\t len < prefix && next[len] == path[len];\n\t\t len++)\n\t\t\tif (next[len] == '/')\n\t\t\t\tlast_matching_slash = len;\n\t\tif (len == prefix)\n\t\t\tcontinue;\n\t\tif (last_matching_slash < 0)\n\t\t\treturn 0;\n\t\tprefix = last_matching_slash + 1;\n\t}\n\treturn prefix;\n}\n"},{"id":"143772","messageId":"201006152004.01507.trast@student.ethz.ch","threadId":"24074","inReplyTo":"7v4oh48elm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-06-15T18:04:01Z","receivedAt":"2010-06-15T18:04:01Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano wrote:\n> Junio C Hamano writes:\n> \n> > Isn't it more intuitive to structure the loop by saying 'Ok, if \"path\" up\n> > to the currently proposed \"prefix\" is too long to match, let's shorten it\n> > by one path component and try again'?\n> \n> Another way of saying this, which probably needs less number of scans,\n> would be to shorten prefix to what is known to match --- use of memcmp()\n> discards this information.\n[...]\n> \twhile ((next = *++pathspec) != NULL) {\n> \t\tint len, last_matching_slash = -1;\n> \t\tfor (len = 0; len < prefix && next[len] == path[len]; len++)\n> \t\t\tif (next[len] == '/')\n> \t\t\t\tlast_matching_slash = len;\n> \t\tif (len == prefix)\n> \t\t\tcontinue;\n> \t\tif (last_matching_slash < 0)\n> \t\t\treturn 0;\n> \t\tprefix = last_matching_slash + 1;\n> \t}\n> \treturn prefix;\n> }\n\nI really didn't like the two-interleaved-loops version in your last\nmail, but this one is way more readable than even the original.\n\n(Why did you wrap the for loop? It's only 76 chars.)\n\nMaybe you could add a comment like\n\n> \tslash = strrchr(path, '/');\n> \tif (!slash)\n> \t\treturn 0;\n\t/* The first 'prefix' characters of 'path' always include the\n\t trailing slash of the prefix directory */\n> \tprefix = slash - path + 1;\n\nto clean up any doubts about the correctness of the matching.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"143790","messageId":"7vaaqwgd2q.fsf@alter.siamese.dyndns.org","threadId":"24074","inReplyTo":"201006152004.01507.trast@student.ethz.ch","subject":"Re: [PATCH] common_prefix: be more careful about pathspec bounds","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-06-15T22:12:29Z","receivedAt":"2010-06-15T22:12:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n> I really didn't like the two-interleaved-loops version in your last\n> mail, but this one is way more readable than even the original.\n>\n> (Why did you wrap the for loop? It's only 76 chars.)\n\nBecause I was writing it in my MUA ;-)\n\n>\n> Maybe you could add a comment like\n>\n>> \tslash = strrchr(path, '/');\n>> \tif (!slash)\n>> \t\treturn 0;\n> \t/* The first 'prefix' characters of 'path' always include the\n> \t trailing slash of the prefix directory */\n>> \tprefix = slash - path + 1;\n>\n> to clean up any doubts about the correctness of the matching.\n\nPerhaps..\n"},{"id":"143801","messageId":"f023050aede65c3cc6d9fdf0067c142dc0257c72.1276642610.git.trast@student.ethz.ch","threadId":"24074","inReplyTo":"7vaaqwgd2q.fsf@alter.siamese.dyndns.org","subject":"[PATCH] common_prefix: simplify and fix scanning for prefixes","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-06-15T23:02:03Z","receivedAt":"2010-06-15T23:02:03Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Junio C Hamano \n\ncommon_prefix() scans backwards from the far end of each 'next'\npathspec, starting from 'len', shortening the 'prefix' using 'path' as\na reference.\n\nHowever, there is a small opportunity for an out-of-bounds access\nbecause len is unconditionally set to prefix-1 after a \"direct match\"\ntest failed. This means that if 'next' is shorter than prefix+2, we\nread past it.\n\nInstead of a minimal fix, simplify the loop: scan *forward* over the\n'next' entry, remembering the last '/' where it matched the prefix\nknown so far. This is far easier to read and also has the advantage\nthat we only scan over each entry once.\n\nAcked-by: Thomas Rast \n---\n\nJunio C Hamano wrote:\n> Thomas Rast writes:\n> > I really didn't like the two-interleaved-loops version in your last\n> > mail, but this one is way more readable than even the original.\n> >\n> > (Why did you wrap the for loop? It's only 76 chars.)\n> \n> Because I was writing it in my MUA ;-)\n\nWell then, perhaps I can at least repay the favour by suggesting a\ncommit message.\n\n\n dir.c | 21 ++++++++-------------\n 1 files changed, 8 insertions(+), 13 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 5e36f8e..78eb869 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -33,20 +33,15 @@ static int common_prefix(const char **pathspec)\n \n \tprefix = slash - path + 1;\n \twhile ((next = *++pathspec) != NULL) {\n-\t\tint len = strlen(next);\n-\t\tif (len >= prefix && !memcmp(path, next, prefix))\n+\t\tint len, last_matching_slash = -1;\n+\t\tfor (len = 0; len < prefix && next[len] == path[len]; len++)\n+\t\t\tif (next[len] == '/')\n+\t\t\t\tlast_matching_slash = len;\n+\t\tif (len == prefix)\n \t\t\tcontinue;\n-\t\tlen = prefix - 1;\n-\t\tfor (;;) {\n-\t\t\tif (!len)\n-\t\t\t\treturn 0;\n-\t\t\tif (next[--len] != '/')\n-\t\t\t\tcontinue;\n-\t\t\tif (memcmp(path, next, len+1))\n-\t\t\t\tcontinue;\n-\t\t\tprefix = len + 1;\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (last_matching_slash < 0)\n+\t\t\treturn 0;\n+\t\tprefix = last_matching_slash + 1;\n \t}\n \treturn prefix;\n }\n-- \n1.7.1.608.g80d39f\n"}]}