[PATCH] attr: fix off-by-one directory component length calculation

94bc671 (Add directory pattern matching to attributes - 2012-12-08)
uses find_basename() to calculate the length of directory part in
prepare_attr_stack. This function expects the directory without the
trailing slash (as "origin" field in match_attr struct is without the
trailing slash). find_basename() includes the trailing slash and
confuses push/pop algorithm.

Consider path = "abc/def" and the push down code:

	while (1) {
		len = strlen(attr_stack->origin);
		if (dirlen <= len)
			break;
		cp = memchr(path + len + 1, '/', dirlen - len - 1);
		if (!cp)
			cp = path + dirlen;

dirlen is 4, not 3, without this patch. So when attr_stack->origin is
"abc", it'll miss the exit condition because 4 <= 3 is wrong. It'll
then try to push "abc/" down the attr stack (because "cp" would be
NULL). So we have both "abc" and "abc/" in the stack.

Next time when "abc/ghi" is checked, "abc/" is popped out because of
the off-by-one dirlen, only to be pushed back in again by the above
code. This repeats for all files in the same directory. Which means
at least one failed open syscall per file, or more if .gitattributes
exists.

This is the perf result with 10 runs on git.git:

Test                                     94bc671^          94bc671                   HEAD
----------------------------------------------------------------------------------------------------------
7810.1: grep worktree, cheap regex       0.02(0.01+0.04)   0.05(0.03+0.05) +150.0%   0.02(0.01+0.04) +0.0%
7810.2: grep worktree, expensive regex   0.25(0.94+0.01)   0.26(0.94+0.02) +4.0%     0.25(0.93+0.02) +0.0%
7810.3: grep --cached, cheap regex       0.11(0.10+0.00)   0.12(0.10+0.02) +9.1%     0.10(0.10+0.00) -9.1%
7810.4: grep --cached, expensive regex   0.61(0.60+0.01)   0.62(0.61+0.01) +1.6%     0.61(0.60+0.00) +0.0%

Reported-by: Ross Lagerwall <redacted>
Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 This may be an indication that our perf framework is never actively used :-(

 attr.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/attr.c b/attr.c
index 466c93f..bb9a470 100644
--- a/attr.c
+++ b/attr.c

@@ -584,6 +584,13 @@ static void prepare_attr_stack(const char *path)
 	dirlen = find_basename(path) - path;
 
 	/*
+	 * find_basename() includes the trailing slash, but we do
+	 * _not_ want it.
+	 */
+	if (dirlen)
+		dirlen--;
+
+	/*
 	 * At the bottom of the attribute stack is the built-in
 	 * set of attribute definitions, followed by the contents
 	 * of $(prefix)/etc/gitattributes and a file specified by

-- 
1.8.0.rc2.23.g1fb49df

Thank you for the explanation.

I did not monitor the system calls when writing that patch. 
Where is the perf framework?

As the mistake is located in the "find_basename" function, I would propose a 
fix directly into it so that the output fits what the other functions expect.

Something in the line of:

diff --git a/attr.c b/attr.c
index d6d7190..b6e72f3 100644
--- a/attr.c
+++ b/attr.c

@@ -572,7 +572,7 @@ static const char *find_basename(const char *path)
                if (*cp == '/' && cp[1])
                        last_slash = cp;
        }
-       return last_slash ? last_slash + 1 : path;
+       return last_slash ? last_slash : path;
 }
 
 static void prepare_attr_stack(const char *path)

@@ -770,6 +770,10 @@ static void collect_all_attrs(const char *path)
                check_all_attr[i].value = ATTR__UNKNOWN;
 
        basename = find_basename(path);
+       /* the slash is included in the basename
+          so that it can be matched by a directory pattern */
+       if (basename != path)
+               basename++;
        pathlen = strlen(path);
        rem = attr_nr;
        for (stk = attr_stack; 0 < rem && stk; stk = stk->prev)

On Wed, Jan 16, 2013 at 2:14 AM, Jean-Noël AVILA [off-list ref] wrote:

I did not monitor the system calls when writing that patch.
Where is the perf framework?

It's in t/perf. I think you can do:

./run HEAD .

to run and compare performance of HEAD and working directory (assume
you haven't commit yet). Check out the README file.
-- 
Duy