v2, 5 partssha1_file: remove a buggy value setting

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(-)

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(-)

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.

'/' 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(-)

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(-)

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(-)

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(-)

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

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

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

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?

Junio C Hamano wrote:

Understand now, thanks for your explanation.

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

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(-)

Junio C Hamano wrote:

Yes, i got the idea, and some errors are pointed out below. I will prepare a V3 patch basing on it.

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"

if pathbuf.buf[strlen(pathbuf.buf)] is '/', remove it. this can avoid to get a wrong result when comparing "/a/b" with "/a/b/".

above line can be removed, since we will release pathbuf soon.