[PATCH v2 0/5] sha1_file: remove only current repository can have relative path limitation

[PATCH v2 0/5] sha1_file: remove only current repository can have relative path limitation

[Wang Hui]

Hi Junio & Martin,

In the V1, Junio said we should investigate why the limitation is originally
designed. This limitation is introduced by Martin in the 2006, so add him
at this time, hope he can share some information and knowledge for this
question although he is not seen in the maillist recently.

Below is my investigation:

In the link_alt_odb_entry(), each alt object path will be added to the struct
alternate_object_database and linked to a list, but we don't permit a same dir
is added twice, otherwise it will easily introduce lots of trouble like
dead-loop reference. To compare if two directories are same, original design
is using memcmp() to directly compare directory path names, this method can't
give a accurate result if paths include .. and multiple slash, e.g. ../../a
and ../../b/../a is the same dir, but this method will report they are
different. Knowing the reason, i implement a new direcotry comparison function
to replace the old one, then we can safely remove multi-level relative
alternates limitation now.


0001 is a simple cleanup patch, has no relation with multi-level relative
limitation.
0002 is a bug fix, has no relation with multi-level relative limitation.
Without this fix, all tests under t/ can work well so far, this is because we
are lucky that the ent->base[pfxlen+1] is 0, if it is not 0, we will see lots
of fails. After apply this fix, it is safe now.
0003 introduce a new directory comparison function to replace the old one.
0004 remove the multi-level relative alternates limitation
0005 change and add testcase to validate multi-level relative alternates.


after apply those 5 patches, all testcase under t can pass.

Hui Wang (5):
      sha1_file cleanup: remove redundant variable check
      sha1_file: remove a buggy value setting
      sha1_file: improve directories comparison method
      sha1_file: remove relative entries limitation
      t5710: add testcase for multi-level relative alternates

 abspath.c                 |   26 ++++++++++++++++++++++++++
 cache.h                   |    1 +
 sha1_file.c               |   22 +++++++---------------
 t/t5710-info-alternate.sh |   21 +++++++++++++++++++--
 4 files changed, 53 insertions(+), 17 deletions(-)

[PATCH v2 1/5] sha1_file cleanup: remove redundant variable check

[Wang Hui]

From: Hui Wang <Hui.Wang@windriver.com>

This variable check is always true, so it is redundant and need to be
removed.

We can't remove the init value for this variable, since removing
it will introduce building warning:
'base_len' may be used uninitialized in this function.

Signed-off-by: Hui Wang <Hui.Wang@windriver.com>
---
 sha1_file.c |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index f7c3408..d12a675 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -255,8 +255,7 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
 
 	if (!is_absolute_path(entry) && relative_base) {
 		/* Relative alt-odb */
-		if (base_len < 0)
-			base_len = strlen(relative_base) + 1;
+		base_len = strlen(relative_base) + 1;
 		entlen += base_len;
 		pfxlen += base_len;
 	}
-- 
1.6.3.1

[PATCH v2 2/5] sha1_file: remove a buggy value setting

[Wang Hui]

From: Hui Wang <Hui.Wang@windriver.com>

The ent->base[] is a character array, it has pfxlen characters from
position 0 to (pfxlen-1) to contain an alt object dir name, the
position pfxlen should be the string terminating character '\0' and
is deliberately set to '\0' at the previous code line. The position
(pfxlen+1) is given to ent->name.

>From above analysis, there is no reason to set ent->base[pfxlen] to
'/' at the end of this function, first it doesn't make sense to append
a '/' at the end of a dir name, second if you are not lucky that the
ent->base[pfxlen+1] is not 0, you will get a wrong alt object dir
name.

Signed-off-by: Hui Wang <Hui.Wang@windriver.com>
---
 sha1_file.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index d12a675..5940d84 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -304,8 +304,6 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
 	/* recursively add alternates */
 	read_info_alternates(ent->base, depth + 1);
 
-	ent->base[pfxlen] = '/';
-
 	return 0;
 }
 
-- 
1.6.3.1

[PATCH v2 3/5] sha1_file: improve directories comparison method

[Wang Hui]

From: Hui Wang <Hui.Wang@windriver.com>

In the past, to check if two directory paths are same, we use memcmp()
to directly compare their path strings, this method can't get an
accurate result if paths include ".." or "." or redundant slash, e.g.
current dir is /, "/a/b/c", "/a/b//c/d/e/../.." and "./a/b/f/../c"
should be the same dir, but current method will identify they are
different.

Now add a global function is_same_directory() to replace the old
memcmp() method, this function will change two input paths to real
path first, then normalized them and compare them.

Signed-off-by: Hui Wang <Hui.Wang@windriver.com>
---
 abspath.c   |   26 ++++++++++++++++++++++++++
 cache.h     |    1 +
 sha1_file.c |    4 ++--
 3 files changed, 29 insertions(+), 2 deletions(-)

diff --git a/abspath.c b/abspath.c
index 3005aed..7717f06 100644
--- a/abspath.c
+++ b/abspath.c
@@ -138,3 +138,29 @@ const char *absolute_path(const char *path)
 	}
 	return buf;
 }
+
+/* Compare two directories, if they are the same dir, return 1, otherwise
+ * return 0.
+ *
+ * The input path can be relative or absolute one, before the comparison, they
+ * will be changed to real path first, then be normalized to remove .. and
+ * redundant slash, in the end, we will compare two real and normalized paths.
+ */
+int is_same_directory(const char *dir1, const char *dir2)
+{
+	const char *real_path1, *real_path2;
+	char norm_path1[PATH_MAX], norm_path2[PATH_MAX];
+
+	real_path1 = real_path(dir1);
+	if (normalize_path_copy(norm_path1, real_path1))
+		return 0;
+
+	real_path2 = real_path(dir2);
+	if (normalize_path_copy(norm_path2, real_path2))
+		return 0;
+
+	if (strlen(norm_path1) != strlen(norm_path2))
+		return 0;
+
+	return !memcmp(norm_path1, norm_path2, strlen(norm_path1));
+}
diff --git a/cache.h b/cache.h
index e11cf6a..70056b5 100644
--- a/cache.h
+++ b/cache.h
@@ -758,6 +758,7 @@ int longest_ancestor_length(const char *path, const char *prefix_list);
 char *strip_path_suffix(const char *path, const char *suffix);
 int daemon_avoid_alias(const char *path);
 int offset_1st_component(const char *path);
+int is_same_directory(const char *dir1, const char *dir2);
 
 /* object replacement */
 #define READ_SHA1_FILE_REPLACE 1
diff --git a/sha1_file.c b/sha1_file.c
index 5940d84..18f7fb3 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -286,12 +286,12 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
 	 * thing twice, or object directory itself.
 	 */
 	for (alt = alt_odb_list; alt; alt = alt->next) {
-		if (!memcmp(ent->base, alt->base, pfxlen)) {
+		if (is_same_directory(ent->base, alt->base)) {
 			free(ent);
 			return -1;
 		}
 	}
-	if (!memcmp(ent->base, objdir, pfxlen)) {
+	if (is_same_directory(ent->base, objdir)) {
 		free(ent);
 		return -1;
 	}
-- 
1.6.3.1

[PATCH v2 4/5] sha1_file: remove relative entries limitation

[Wang Hui]

From: Hui Wang <Hui.Wang@windriver.com>

link_alt_odb_entries() will be called recursively if alternates has
valid object store paths, to avoid nesting too deep, the recursive
depth is limited to 5, this limitation is reasonable and safe for
dead-loop reference situation.

There is another limitation in this function to only permit the 1st
level alternates has relative paths, the purpose of this limitation
is to avoid inaccurate result when using memcmp() directly to compare
two directory path names, e.g. "./a/b/" and "./a/c/e/../../b" should
be the same dir, but memcmp() will report they are different dirs,
this will introduce the same dir be added twice or dead-loop
reference.

Now we have new method to compare two directories and can handle both
absolute path and relative path comparison, in addition to we already
have max depth 5 limitation, we can safely remove this limitation.

Moreover removing this limitation will make below two usage workable.

usage1: base-repos has relative path in the alternates
        %>git clone --reference base-repos src dest
usage2: src2 has relative path to point src1, src1 has relative path
	to point src
        %>git clone src2 dest

Signed-off-by: Hui Wang <Hui.Wang@windriver.com>
---
 sha1_file.c |   13 ++++---------
 1 files changed, 4 insertions(+), 9 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 18f7fb3..98fdb0a 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -329,15 +329,10 @@ static void link_alt_odb_entries(const char *alt, const char *ep, int sep,
 		}
 		while (cp < ep && *cp != sep)
 			cp++;
-		if (last != cp) {
-			if (!is_absolute_path(last) && depth) {
-				error("%s: ignoring relative alternate object store %s",
-						relative_base, last);
-			} else {
-				link_alt_odb_entry(last, cp - last,
-						relative_base, depth);
-			}
-		}
+		if (last != cp)
+			link_alt_odb_entry(last, cp - last,
+					relative_base, depth);
+
 		while (cp < ep && *cp == sep)
 			cp++;
 		last = cp;
-- 
1.6.3.1

[PATCH v2 5/5] t5710: add testcase for multi-level relative alternates

[Wang Hui]

From: Hui Wang <Hui.Wang@windriver.com>

Since we removed "relative alternates only possible for current dir"
limitation, it is needed to change an existing testcase to make it
pass for the relative path at the second level alternates.

Add a new testcase to make it pass when it work at a 5-level relative
alternates repository and make it fail when it work at a 6-level
relative alternates repository.

Signed-off-by: Hui Wang <Hui.Wang@windriver.com>
---
 t/t5710-info-alternate.sh |   21 +++++++++++++++++++--
 1 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/t/t5710-info-alternate.sh b/t/t5710-info-alternate.sh
index ef7127c..a606a94 100755
--- a/t/t5710-info-alternate.sh
+++ b/t/t5710-info-alternate.sh
@@ -102,9 +102,26 @@ test_valid_repo'
 cd "$base_dir"
 
 test_expect_success \
-    'that relative alternate is only possible for current dir' '
+    'that relative alternate is possible for none current dir' '
     cd D &&
-    ! (test_valid_repo)
+    test_valid_repo
+'
+
+cd "$base_dir"
+
+test_expect_success 'allow maxium 5 level relative alternate' \
+'echo "" > A/.git/objects/info/alternates &&
+echo "../../../A/.git/objects" > B/.git/objects/info/alternates &&
+echo "../../../B/.git/objects" > C/.git/objects/info/alternates &&
+echo "../../../C/.git/objects" > D/.git/objects/info/alternates &&
+echo "../../../D/.git/objects" > E/.git/objects/info/alternates &&
+echo "../../../E/.git/objects" > F/.git/objects/info/alternates &&
+echo "../../../F/.git/objects" > G/.git/objects/info/alternates &&
+cd F &&
+test_valid_repo &&
+cd ../G &&
+git fsck --full > fsck.err 2>&1 &&
+test `wc -l < fsck.err` != 0
 '
 
 cd "$base_dir"
-- 
1.6.3.1

Re: [PATCH v2 2/5] sha1_file: remove a buggy value setting

[Junio C Hamano]

Wang Hui <Hui.Wang@windriver.com> writes:

> From: Hui Wang <Hui.Wang@windriver.com>
>
> The ent->base[] is a character array, it has pfxlen characters from
> position 0 to (pfxlen-1) to contain an alt object dir name, the
> position pfxlen should be the string terminating character '\0' and
> is deliberately set to '\0' at the previous code line. The position
> (pfxlen+1) is given to ent->name.

Correct. Do you understand why?

We temporarily NUL terminate the ent->base[] so that we can give it to
is_directory() to see if that is a directory, but the invariants for a
alternate_object_database instance after it is properly initialized by
this function are to have:

 - the directory name followed by a slash in the base[] array;
 - the name pointer pointing at one byte beyond the slash;
 - name[2] filled with a slash; and
 - name[41] terminated with NUL.

Later, has_loose_object_nonlocal() calls fill_sha1_path() with the name
pointer to fill name[0..1, 3..40] with the hexadecimal representation of
the object name, which would result in base[] array to have the pathname
for a loose object found in that alternate. The same thing happens in
open_sha1_file() to read from a loose object in an alternate.

And you are breaking one of the above invariants by removing that slash
after the directory name. These callers of fill_sha1_path() will see the
directory name, your NUL, two hex, slash, and 38 hex in base[].

How would the code even work with your patch?

Re: [PATCH v2 3/5] sha1_file: improve directories comparison method

[Junio C Hamano]

Wang Hui <Hui.Wang@windriver.com> writes:

> From: Hui Wang <Hui.Wang@windriver.com>
>
> In the past, to check if two directory paths are same, we use memcmp()
> to directly compare their path strings, this method can't get an
> accurate result if paths include ".." or "." or redundant slash, e.g.
> current dir is /, "/a/b/c", "/a/b//c/d/e/../.." and "./a/b/f/../c"
> should be the same dir, but current method will identify they are
> different.
>
> Now add a global function is_same_directory() to replace the old
> memcmp() method, this function will change two input paths to real
> path first, then normalized them and compare them.

I do not like this patch _at all_. While it may result in correct result
if you _always_ make it absolute before comparing two entities, if you
will be storing the normalized result after running the comparison anyway,
and if you are comparing against the existing and supposedly already
normalized entities with a new candidate, why would anybody sane would
want to keep paying for the normalization cost at such a low level?

IOW, you are proposing to do:

	given a new candidate;
	for existing entities:
		normalize existing
                normalize candiate
                compare the above two
                if they are equal:
                	ignore
	if no match found
        	add the normalized candidate to the list

Wouldn't it make much more sense to do this:

	given a new candidate;
        normalize it
	for existing entities:
                compare existing and normalized candidate
		there is no point in normalizing the existing one!
                if they are equal:
                	ignore
	if no match found
        	add the normalized candidate to the list

Re: [PATCH v2 1/5] sha1_file cleanup: remove redundant variable check

[Junio C Hamano]

Wang Hui <Hui.Wang@windriver.com> writes:

> From: Hui Wang <Hui.Wang@windriver.com>
>
> This variable check is always true, so it is redundant and need to be
> removed.
>
> We can't remove the init value for this variable, since removing
> it will introduce building warning:
> 'base_len' may be used uninitialized in this function.

If we are into cleaning things up, we should instead notice and say "yuck"
to the repeated "is entry is absolute and relative base is given" check.

Wouldn't something like this makes things easier to follow and also avoids
the "when does the path normalized and made absolute" issue?

Completely untested and I may have off-by-one errors and such, but I think
you would get the idea...

 sha1_file.c |   29 ++++++++++++-----------------
 1 files changed, 12 insertions(+), 17 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index e002056..26aa3be 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -248,27 +248,22 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
 	const char *objdir = get_object_directory();
 	struct alternate_object_database *ent;
 	struct alternate_object_database *alt;
-	/* 43 = 40-byte + 2 '/' + terminating NUL */
-	int pfxlen = len;
-	int entlen = pfxlen + 43;
-	int base_len = -1;
+	int pfxlen, entlen;
+	struct strbuf pathbuf = STRBUF_INIT;
 
 	if (!is_absolute_path(entry) && relative_base) {
-		/* Relative alt-odb */
-		if (base_len < 0)
-			base_len = strlen(relative_base) + 1;
-		entlen += base_len;
-		pfxlen += base_len;
+		strbuf_addstr(&pathbuf, relative_base);
+		strbuf_addch(&pathbuf, '/');
 	}
-	ent = xmalloc(sizeof(*ent) + entlen);
+	strbuf_add(&pathbuf, entry, len);
+	normalize_path_copy(pathbuf.buf, pathbuf.buf);
+	strbuf_setlen(&pathbuf, strlen(pathbuf.buf));
 
-	if (!is_absolute_path(entry) && relative_base) {
-		memcpy(ent->base, relative_base, base_len - 1);
-		ent->base[base_len - 1] = '/';
-		memcpy(ent->base + base_len, entry, len);
-	}
-	else
-		memcpy(ent->base, entry, pfxlen);
+	pfxlen = pathbuf.len;
+	entlen = pfxlen + 43; /* '/' + 2 hex + '/' + 38 hex + NUL */
+	ent = xmalloc(sizeof(*ent) + entlen);
+	memcpy(ent->base, pathbuf.buf, pfxlen);
+	strbuf_release(&pathbuf);
 
 	ent->name = ent->base + pfxlen + 1;
 	ent->base[pfxlen + 3] = '/';

Re: [PATCH v2 2/5] sha1_file: remove a buggy value setting

[wanghui]

Junio C Hamano wrote:
> Wang Hui <Hui.Wang@windriver.com> writes:
>
>   
>> From: Hui Wang <Hui.Wang@windriver.com>
>>
>> The ent->base[] is a character array, it has pfxlen characters from
>> position 0 to (pfxlen-1) to contain an alt object dir name, the
>> position pfxlen should be the string terminating character '\0' and
>> is deliberately set to '\0' at the previous code line. The position
>> (pfxlen+1) is given to ent->name.
>>     
>
> Correct. Do you understand why?
>
> We temporarily NUL terminate the ent->base[] so that we can give it to
> is_directory() to see if that is a directory, but the invariants for a
> alternate_object_database instance after it is properly initialized by
> this function are to have:
>
>  - the directory name followed by a slash in the base[] array;
>  - the name pointer pointing at one byte beyond the slash;
>  - name[2] filled with a slash; and
>  - name[41] terminated with NUL.
>
> Later, has_loose_object_nonlocal() calls fill_sha1_path() with the name
> pointer to fill name[0..1, 3..40] with the hexadecimal representation of
> the object name, which would result in base[] array to have the pathname
> for a loose object found in that alternate. The same thing happens in
> open_sha1_file() to read from a loose object in an alternate.
>
> And you are breaking one of the above invariants by removing that slash
> after the directory name. These callers of fill_sha1_path() will see the
> directory name, your NUL, two hex, slash, and 38 hex in base[].
>
>   
Understand now, thanks for your explanation.
> How would the code even work with your patch?
>
>
>   

Re: [PATCH v2 1/5] sha1_file cleanup: remove redundant variable check

[wanghui]

Junio C Hamano wrote:
> Wang Hui <Hui.Wang@windriver.com> writes:
>
>   
>> From: Hui Wang <Hui.Wang@windriver.com>
>>
>> This variable check is always true, so it is redundant and need to be
>> removed.
>>
>> We can't remove the init value for this variable, since removing
>> it will introduce building warning:
>> 'base_len' may be used uninitialized in this function.
>>     
>
> If we are into cleaning things up, we should instead notice and say "yuck"
> to the repeated "is entry is absolute and relative base is given" check.
>
> Wouldn't something like this makes things easier to follow and also avoids
> the "when does the path normalized and made absolute" issue?
>
> Completely untested and I may have off-by-one errors and such, but I think
> you would get the idea...
>
>   
Yes, i got the idea, and some errors are pointed out below. I will 
prepare a V3 patch basing on it.
>  sha1_file.c |   29 ++++++++++++-----------------
>  1 files changed, 12 insertions(+), 17 deletions(-)
>
> diff --git a/sha1_file.c b/sha1_file.c
> index e002056..26aa3be 100644
> --- a/sha1_file.c
> +++ b/sha1_file.c
> @@ -248,27 +248,22 @@ static int link_alt_odb_entry(const char * entry, int len, const char * relative
>  	const char *objdir = get_object_directory();
>  	struct alternate_object_database *ent;
>  	struct alternate_object_database *alt;
> -	/* 43 = 40-byte + 2 '/' + terminating NUL */
> -	int pfxlen = len;
> -	int entlen = pfxlen + 43;
> -	int base_len = -1;
> +	int pfxlen, entlen;
> +	struct strbuf pathbuf = STRBUF_INIT;
>  
>  	if (!is_absolute_path(entry) && relative_base) {
> -		/* Relative alt-odb */
> -		if (base_len < 0)
> -			base_len = strlen(relative_base) + 1;
> -		entlen += base_len;
> -		pfxlen += base_len;
> +		strbuf_addstr(&pathbuf, relative_base);
>   
s/relative_base/real_path(relative_base)/ is better, since 
normalize_path_copy is not good at handle relative path. e.g. ". 
./objects/../../test2/objects" will be normalized to "objects"
> +		strbuf_addch(&pathbuf, '/');
>  	}
> -	ent = xmalloc(sizeof(*ent) + entlen);
> +	strbuf_add(&pathbuf, entry, len);
> +	normalize_path_copy(pathbuf.buf, pathbuf.buf);
>   
if pathbuf.buf[strlen(pathbuf.buf)] is '/', remove it. this can avoid to 
get a wrong result when comparing "/a/b" with "/a/b/".
> +	strbuf_setlen(&pathbuf, strlen(pathbuf.buf));
>   
above line can be removed, since we will release pathbuf soon.

>  
> -	if (!is_absolute_path(entry) && relative_base) {
> -		memcpy(ent->base, relative_base, base_len - 1);
> -		ent->base[base_len - 1] = '/';
> -		memcpy(ent->base + base_len, entry, len);
> -	}
> -	else
> -		memcpy(ent->base, entry, pfxlen);
> +	pfxlen = pathbuf.len;
> +	entlen = pfxlen + 43; /* '/' + 2 hex + '/' + 38 hex + NUL */
> +	ent = xmalloc(sizeof(*ent) + entlen);
> +	memcpy(ent->base, pathbuf.buf, pfxlen);
> +	strbuf_release(&pathbuf);
>  
>  	ent->name = ent->base + pfxlen + 1;
>  	ent->base[pfxlen + 3] = '/';
>
>