Some patches for fsck for missing objects

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

Introduce a new repository extension option "extensions.lazyobject", of data type string. If this is set in a repository, Git will tolerate objects being missing in that repository. When Git needs those objects, it will invoke the command in that option.

Teach fsck about the new state of affairs. In this commit, teach fsck that missing objects referenced from the reflog are not an error case; in future commits, fsck will be taught about other cases.

builtin/fsck.c +1 -1

index fb0947009..1cfb8d98c 100644
@@ -402,7 +402,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,
 					xstrfmt("%s@{%"PRItime"}", refname, timestamp));
 			obj->flags |= USED;
 			mark_object_reachable(obj);
-		} else {
+		} else if (!repository_format_lazy_object) {
 			error("%s: invalid reflog entry %s", refname, oid_to_hex(oid));
 			errors_found |= ERROR_REACHABLE;
 		}

cache.h +0 -0

index 6c8242340..9e6bc0a21 100644

t/t0410-lazy-object.sh new file +31 -0

new file mode 100755
index 000000000..36442531f
@@ -0,0 +1,32 @@
+#!/bin/sh
+
+test_description='lazy object'
+
+. ./test-lib.sh
+
+delete_object () {
+	rm $1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40)
+}
+
+test_expect_success 'fsck fails on lazy object in reflog' '
+	test_create_repo repo &&
+	test_commit -C repo 1 &&
+
+	A=$(git -C repo commit-tree -m a HEAD^{tree}) &&
+	B=$(git -C repo commit-tree -m b HEAD^{tree}) &&
+
+	# Reference $A only from reflog, and delete it
+	git -C repo branch mybranch "$A" &&
+	git -C repo branch -f mybranch "$B" &&
+	delete_object repo "$A" &&
+
+	test_must_fail git -C repo fsck
+'
+test_expect_success '...but succeeds if lazyobject is set' '
+	git -C repo config core.repositoryformatversion 1 &&
+	git -C repo config extensions.lazyobject "arbitrary string" &&
+	git -C repo fsck
+'
+
+test_done

Quoted 7 lines · Jonathan Tan

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

Quoted 4 lines

Introduce a new repository extension option "extensions.lazyobject", of data type string. If this is set in a repository, Git will tolerate objects being missing in that repository. When Git needs those objects, it will invoke the command in that option.

My reading hiccupped after the first sentence, as the problem description made it sound like this was a boolean ("are we using lazy object feature?"), after reading "data type string". And then "the command in that option" made me hiccup one more time, as it did not "click" that "in that option" was trying to say that the string is used as the command name (or is it a whole command line? The leading part of the command line to which some arguments are appended before it gets invoked as a command? or what?).

Logically, I think it is more like

- extensions.lazyobject can be set to tell Git to consider missing

    objects in certain cases are not errors;

- the value of extensions.lazyobject variable must be a string, which is used to name the command to lazily make the object "appear" in the repository on demand.

Quoted 3 lines

Teach fsck about the new state of affairs. In this commit, teach fsck that missing objects referenced from the reflog are not an error case; in future commits, fsck will be taught about other cases.

In any case, sounds like a small and good first step.

Documentation/technical/repository-version.txt for testing format-1 compatibility. · line 95

Quoted 7 lines

Documentation/technical/repository-version.txt +7 -0

+
+`lazyObject`
+~~~~~~~~~~~~~~~~~
+
+When the config key `extensions.lazyObject` is set to a string, Git
+tolerates objects being missing in the repository. This string contains
+the command to be run whenever a missing object is needed.

This has the same issue but to a lessor degree as there is "string contains". What the command will do (e.g. "makes the object magically appear in the object store" or "emits the contents of the object to its standard output, so that Git can hash it to make it appear in the object store"), and how it is used (e.g. "this is a single command name and nothing else", "this is a leading part of command line and arguments are appended at the end, before the whole thing is passed to the shell to be executed", etc.) will need to be clarified in the final version of the series (not necessarily at this step---the series can elaborate in the later patches).

Quoted 18 lines

builtin/fsck.c +1 -1

index fb0947009..1cfb8d98c 100644
@@ -402,7 +402,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,
  					xstrfmt("%s@{%"PRItime"}", refname, timestamp));
  			obj->flags |= USED;
  			mark_object_reachable(obj);
-		} else {
+		} else if (!repository_format_lazy_object) {
  			error("%s: invalid reflog entry %s", refname, oid_to_hex(oid));
  			errors_found |= ERROR_REACHABLE;
  		}

cache.h +0 -0

index 6c8242340..9e6bc0a21 100644

cache.h extern int grafts_replace_parents; · line 856

Quoted 4 lines

cache.h +1 -0

@@ -853,10 +853,12 @@ extern int grafts_replace_parents;
  #define GIT_REPO_VERSION 0
  #define GIT_REPO_VERSION_READ 1
  extern int repository_format_precious_objects;
+extern char *repository_format_lazy_object;

This is not a new problem, but I think these two should be called repository_extension_$NAME not repository_format_$NAME.

Quoted 37 lines

t/t0410-lazy-object.sh new file +31 -0

new file mode 100755
index 000000000..36442531f
@@ -0,0 +1,32 @@
+#!/bin/sh
+
+test_description='lazy object'
+
+. ./test-lib.sh
+
+delete_object () {
+	rm $1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40)
+}
+
+test_expect_success 'fsck fails on lazy object in reflog' '
+	test_create_repo repo &&
+	test_commit -C repo 1 &&
+
+	A=$(git -C repo commit-tree -m a HEAD^{tree}) &&
+	B=$(git -C repo commit-tree -m b HEAD^{tree}) &&
+
+	# Reference $A only from reflog, and delete it
+	git -C repo branch mybranch "$A" &&
+	git -C repo branch -f mybranch "$B" &&
+	delete_object repo "$A" &&
+
+	test_must_fail git -C repo fsck
+'
+test_expect_success '...but succeeds if lazyobject is set' '
+	git -C repo config core.repositoryformatversion 1 &&
+	git -C repo config extensions.lazyobject "arbitrary string" &&
+	git -C repo fsck
+'
+
+test_done

My reading hiccupped after the first sentence, as the problem description made it sound like this was a boolean ("are we using lazy object feature?"), after reading "data type string". And then "the command in that option" made me hiccup one more time, as it did not "click" that "in that option" was trying to say that the string is used as the command name (or is it a whole command line? The leading part of the command line to which some arguments are appended before it gets invoked as a command? or what?).

Logically, I think it is more like

- extensions.lazyobject can be set to tell Git to consider missing objects in certain cases are not errors;

- the value of extensions.lazyobject variable must be a string, which is used to name the command to lazily make the object "appear" in the repository on demand.

Quoted 2 lines

extern int repository_format_precious_objects;
+extern char *repository_format_lazy_object;

This is not a new problem, but I think these two should be called repository_extension_$NAME not repository_format_$NAME.

Quoted 5 lines

Quoted 2 lines

extern int repository_format_precious_objects;
+extern char *repository_format_lazy_object;

This is not a new problem, but I think these two should be called repository_extension_$NAME not repository_format_$NAME.

Looking at the original commit 067fbd4 ("introduce "preciousObjects" repository extension", 2015-06-24), it seems that this was so named to be analogous to the existing "struct repository_format { int version; ...}" => "int repository_format_version;". The existing repository_format_$NAME thus seems reasonable to me.

Teach fsck to not treat refs with missing targets as an error when extensions.lazyobject is set.

For the purposes of warning about no default refs, such refs are still treated as legitimate refs.

Signed-off-by Jonathan Tan <[email protected]>

---
 builtin/fsck.c         |  8 ++++++++
 t/t0410-lazy-object.sh | 20 ++++++++++++++++++++
 2 files changed, 28 insertions(+)

builtin/fsck.c +0 -0

index 1cfb8d98c..e29ff760b 100644
@@ -438,6 +438,14 @@ static int fsck_handle_ref(const char *refname, const struct object_id *oid,
 
 	obj = parse_object(oid);
 	if (!obj) {

builtin/fsck.c +6 -0

+test_expect_success '...but succeeds if lazyobject is set' '
+	git -C repo config core.repositoryformatversion 1 &&
+	git -C repo config extensions.lazyobject "arbitrary string" &&
+	git -C repo fsck
+'
+
 test_done

Quoted 12 lines

builtin/fsck.c +8 -0

@@ -438,6 +438,14 @@ static int fsck_handle_ref(const char *refname, const struct object_id *oid,
 
 	obj = parse_object(oid);
 	if (!obj) {
+		if (repository_format_lazy_object) {
+			/*
+			 * Increment default_refs anyway, because this is a
+			 * valid ref.
+			 */
+			default_refs++;
+			return 0;
+		}

builtin/fsck.c static int fsck_handle_ref(const char *refname, const struct object_id *oid, · line 450

Quoted 2 lines

builtin/fsck.c +0 -0

 		error("%s: invalid sha1 pointer %s", refname, oid_to_hex(oid));
 		errors_found |= ERROR_REACHABLE;

At this point, do we know (or can we tell) if this is a missing object or a file exists as a loose object but is corrupt? If we could, it would be nice to do this only for the former to avoid sweeping a real corruption that is unrelated to the lazy fetch under the rug.

Quoted 9 lines

t/t0410-lazy-object.sh +9 -0

+test_expect_success 'fsck fails on lazy object pointed to by ref' '
+	rm -rf repo &&
+	test_create_repo repo &&
+	test_commit -C repo 1 &&
+
+	A=$(git -C repo commit-tree -m a HEAD^{tree}) &&
+
+	# Reference $A only from ref, and delete it
+	git -C repo branch mybranch "$A" &&

t/t0410-lazy-object.sh test_expect_success '...but succeeds if lazyobject is set' ' · line 44

Quoted 4 lines

t/t0410-lazy-object.sh +4 -0

+	delete_object repo "$A" &&
+
+	test_must_fail git -C repo fsck
+'

And a new test that uses a helper different from delete_object (perhaps call it corrupt_object?) can be used to make sure that we complain in that case here.

Quoted 12 lines · On Thu, 27 Jul 2017 11:59:47 -0700 Junio C Hamano <[email protected]> wrote:

Quoted 12 lines

builtin/fsck.c +8 -0

@@ -438,6 +438,14 @@ static int fsck_handle_ref(const char *refname, const struct object_id *oid,
 
  	obj = parse_object(oid);
  	if (!obj) {
+		if (repository_format_lazy_object) {
+			/*
+			 * Increment default_refs anyway, because this is a
+			 * valid ref.
+			 */
+			default_refs++;
+			return 0;
+		}

Quoted 8 lines

builtin/fsck.c static int fsck_handle_ref(const char *refname, const struct object_id *oid, · line 450

Quoted 2 lines

builtin/fsck.c +0 -0

  		error("%s: invalid sha1 pointer %s", refname, oid_to_hex(oid));
  		errors_found |= ERROR_REACHABLE;

At this point, do we know (or can we tell) if this is a missing object or a file exists as a loose object but is corrupt? If we could, it would be nice to do this only for the former to avoid sweeping a real corruption that is unrelated to the lazy fetch under the rug.

Before all this is run, there is a check over all loose and packed objects and I've verified that this check reports failure in corrupt-object situations (see test below).

It is true that parse_object() cannot report the difference, but since fsck has already verified non-corruptness, I don't think it needs to know the difference at this point.

Quoted 9 lines

Quoted 9 lines

t/t0410-lazy-object.sh +9 -0

+test_expect_success 'fsck fails on lazy object pointed to by ref' '
+	rm -rf repo &&
+	test_create_repo repo &&
+	test_commit -C repo 1 &&
+
+	A=$(git -C repo commit-tree -m a HEAD^{tree}) &&
+
+	# Reference $A only from ref, and delete it
+	git -C repo branch mybranch "$A" &&

Quoted 8 lines

t/t0410-lazy-object.sh test_expect_success '...but succeeds if lazyobject is set' ' · line 44

Quoted 4 lines

t/t0410-lazy-object.sh +4 -0

+	delete_object repo "$A" &&
+
+	test_must_fail git -C repo fsck
+'

And a new test that uses a helper different from delete_object (perhaps call it corrupt_object?) can be used to make sure that we complain in that case here.

I agree that object corruption can cause this specific part of the production code to falsely work. But I think that this specific part of the code can and should rely on object corruption being checked elsewhere. (I usually don't like to assume that other components work and will continue to work, but in this case, I think that fsck checking for object corruption is very foundational and should be relied upon.)

But if we think that defense "in depth" is a good idea, I have no problem adding such tests (like the one below).

---

delete_object () {
	rm $1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40)
}

corrupt_object () {
	chmod a+w $1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40) &&
	echo CORRUPT >$1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40)
}

setup_object_in_reflog () {
	rm -rf repo &&
	test_create_repo repo &&
	test_commit -C repo 1 &&

	A=$(git -C repo commit-tree -m a HEAD^{tree}) &&
	B=$(git -C repo commit-tree -m b HEAD^{tree}) &&

	# Reference $A only from reflog
	git -C repo branch mybranch "$A" &&
	git -C repo branch -f mybranch "$B"
}

test_expect_success 'lazy object in reflog' '

	setup_object_in_reflog &&
	delete_object repo "$A" &&
	test_must_fail git -C repo fsck &&
	git -C repo config core.repositoryformatversion 1 &&
	git -C repo config extensions.lazyobject "arbitrary string" &&
	git -C repo fsck

'

test_expect_success 'corrupt loose object in reflog' '

	setup_object_in_reflog &&
	corrupt_object repo "$A" &&
	test_must_fail git -C repo fsck &&
	git -C repo config core.repositoryformatversion 1 &&
	git -C repo config extensions.lazyobject "arbitrary string" &&
	test_must_fail git -C repo fsck

'

test_expect_success 'missing packed object in reflog' '

	setup_object_in_reflog &&
	git -C repo repack -a &&
	delete_object repo "$A" &&
	chmod a+w repo/.git/objects/pack/*.pack &&
	echo CORRUPT >"$(echo repo/.git/objects/pack/*.pack)" &&
	test_must_fail git -C repo fsck &&
	git -C repo config core.repositoryformatversion 1 &&
	git -C repo config extensions.lazyobject "arbitrary string" &&
	test_must_fail git -C repo fsck

'

Teach fsck to not treat missing objects indirectly pointed to by refs as an error when extensions.lazyobject is set.

Signed-off-by Jonathan Tan <[email protected]>

---
 builtin/fsck.c         | 11 +++++++++++
 t/t0410-lazy-object.sh | 27 +++++++++++++++++++++++++++
 2 files changed, 38 insertions(+)

builtin/fsck.c +0 -0

index e29ff760b..238532cc2 100644
@@ -149,6 +149,15 @@ static int mark_object(struct object *obj, int type, void *data, struct fsck_opt
 		return 0;
 	obj->flags |= REACHABLE;

The same comment as 2/4 applies here.

builtin/fsck.c static void check_reachable_object(struct object *obj) · line 228

Quoted 10 lines

builtin/fsck.c +2 -0

@@ -212,6 +221,8 @@ static void check_reachable_object(struct object *obj)
 	 * do a full fsck
 	 */
 	if (!(obj->flags & HAS_OBJ)) {
+		if (repository_format_lazy_object)
+			return;
 		if (has_sha1_pack(obj->oid.hash))
 			return; /* it is in pack - forget about it */
 		printf("missing %s %s\n", printable_type(obj),

Also this reminds as a related issue. Imagine:

- An object X was once retrieved, perhaps but not necessarily lazily, together with another object Y that is referred to by X (e.g. X is a tree, Y is a blob in the directory at path D, which is represented by X).

- The same blob Y is added to the index in a different directory at path E.

- The user decides to make this a slimmed-down "narrow clone" style repository and tells Git that path D is not interesting. We lose X, but not Y because Y is still referenced from the index.

- "git reset --hard" happens, and there no longer is any reference to Y.

Now, when we run fsck, should we diagnose Y as "unreachable and/or dangling"?

Teach fsck to not treat missing objects indirectly pointed to by refs as an error when extensions.lazyobject is set.

This is an updated version of my previous patch [1], but without the list of promises. It is somewhat different now because fsck cannot just mark all promised objects as HAS_OBJ.

This could be adapted and incorporated into patch sets that have objects missing from the local repo.

I split this up into 4 patches so that you can see how the changes in fsck are being tested, but eventually these should probably be combined into 1 patch.

Quoted 7 lines · Jonathan Tan

This is an updated version of my previous patch [1], but without the list of promises. It is somewhat different now because fsck cannot just mark all promised objects as HAS_OBJ.

This could be adapted and incorporated into patch sets that have objects missing from the local repo.

Quoted 3 lines

I split this up into 4 patches so that you can see how the changes in fsck are being tested, but eventually these should probably be combined into 1 patch.

I looked at this and I like the direction it's going. It's pretty simple and straightforward, which I also like.

I looked at this and I like the direction it's going. It's pretty simple and straightforward, which I also like.

What I'd recommend is that instead of making lazyObject a string, we make it an integer representing a protocol version. We then add a different config setting that is the actual program to invoke, using the given protocol version. This lets us change the way we speak to the tool without breaking backwards compatibility, and it also allows us to simply check the lazyObject script for supported protocols up front.

Quoted 2 lines · On Wed, 26 Jul 2017 23:42:38 +0000 "brian m. carlson"…

I looked at this and I like the direction it's going. It's pretty simple and straightforward, which I also like.

Thanks.

Quoted 6 lines

What I'd recommend is that instead of making lazyObject a string, we make it an integer representing a protocol version. We then add a different config setting that is the actual program to invoke, using the given protocol version. This lets us change the way we speak to the tool without breaking backwards compatibility, and it also allows us to simply check the lazyObject script for supported protocols up front.

That's possible too. As for version negotiation, I think we'll end up using a protocol similar to the clean/smudge long-running process protocol (as documented as gitattributes), so that does not need to be taken care of here, but making lazyObject be the version integer is fine too.

Teach sha1_file to invoke the command configured in extensions.lazyObject whenever an object is requested and unavailable.

The usage of the hook can be suppressed through a flag when invoking has_object_file_with_flags() and other similar functions.

This is meant as a temporary measure to ensure that all Git commands work in such a situation. Future patches will update some commands to either tolerate missing objects (without invoking the command) or be more efficient in invoking this command.

In order to determine the code changes in sha1_file.c necessary, I investigated the following:
(1) functions in sha1_file that take in a hash, without the user regarding how the object is stored (loose or packed)
(2) functions in sha1_file that operate on packed objects (because I need to check callers that know about the loose/packed distinction and operate on both differently, and ensure that they can handle the concept of objects that are neither loose nor packed)

(1) is handled by the modification to sha1_object_info_extended().

For (2), I looked at for_each_packed_object and at the packed-related functions that take in a hash. For for_each_packed_object, the callers either already work or are fixed in this patch:
- reachable - only to find recent objects
- builtin/fsck - already knows about missing objects
- builtin/cat-file - warning message added in this commit

Callers of the other functions do not need to be changed:
- parse_pack_index
- http - indirectly from http_get_info_packs
- find_pack_entry_one
- this searches a single pack that is provided as an argument; the caller already knows (through other means) that the sought object is in a specific pack
- find_sha1_pack
- fast-import - appears to be an optimization to not store a file if it is already in a pack
- http-walker - to search through a struct alt_base
- http-push - to search through remote packs
- has_sha1_pack
- builtin/fsck - already knows about promised objects
- builtin/count-objects - informational purposes only (check if loose object is also packed)
- builtin/prune-packed - check if object to be pruned is packed (if not, don't prune it)
- revision - used to exclude packed objects if requested by user
- diff - just for optimization

An alternative design that I considered but rejected:

- Adding a hook whenever a packed object is requested, not on any object. That is, whenever we attempt to search the packfiles for an object, if it is missing (from the packfiles and from the loose object storage), to invoke the hook (which must then store it as a packfile), open the packfile the hook generated, and report that the object is found in that new packfile. This reduces the amount of analysis needed (in that we only need to look at how packed objects are handled), but requires that the hook generate packfiles (or for sha1_file to pack whatever loose objects are generated), creating one packfile for each missing object and potentially very many packfiles that must be linearly searched. This may be tolerable now for repos that only have a few missing objects (for example, repos that only want to exclude large blobs), and might be tolerable in the future if we have batching support for the most commonly used commands, but is not tolerable now for repos that exclude a large amount of objects.

Helped-by Ben Peart <[email protected]>

Signed-off-by Jonathan Tan <[email protected]>

---

Teach sha1_file to invoke the command configured in extensions.lazyObject whenever an object is requested and unavailable.

The usage of the hook can be suppressed through a flag when invoking has_object_file_with_flags() and other similar functions.

This is meant as a temporary measure to ensure that all Git commands work in such a situation. Future patches will update some commands to either tolerate missing objects (without invoking the command) or be more efficient in invoking this command.

sha1_file.c +9 -14

index b60ae15f7..1785c61d8 100644
@@ -28,6 +28,11 @@
  #include "list.h"
  #include "mergesort.h"
  #include "quote.h"
+#include "iterator.h"
+#include "dir-iterator.h"
+#include "sha1-lookup.h"
+#include "lazy-object.h"
+#include "sha1-array.h"
 
  #define SZ_FMT PRIuMAX
  static inline uintmax_t sz_fmt(size_t s) { return s; }

@@ -2984,6 +2989,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
  	const unsigned char *real = (flags & OBJECT_INFO_LOOKUP_REPLACE) ?
  				    lookup_replace_object(sha1) :
  				    sha1;
+	int already_retried = 0;
 
  	if (!oi)
  		oi = &blank_oi;

@@ -3008,30 +3014,38 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
  		}
  	}
 
-	if (!find_pack_entry(real, &e)) {
-		/* Most likely it's a loose object. */
-		if (!sha1_loose_object_info(real, oi, flags)) {
-			oi->whence = OI_LOOSE;
-			return 0;
-		}
+retry:
+	if (find_pack_entry(real, &e))
+		goto found_packed;
 
-		/* Not a loose object; someone else may have just packed it. */
-		if (flags & OBJECT_INFO_QUICK) {
-			return -1;
-		} else {
-			reprepare_packed_git();
-			if (!find_pack_entry(real, &e))
-				return -1;
-		}

t/t0410/lazy-object new file +12 -0

new file mode 100755
index 000000000..4f4a9c38a
@@ -0,0 +1,102 @@
+#!/usr/bin/perl
+#
+# Example implementation for the Git lazyObject protocol version 1. See
+# the documentation for extensions.lazyObject in
+# Documentation/technical/repository-version.txt
+#
+# Allows you to test the ability for blobs to be pulled from a host git repo
+# "on demand."  Called when git needs a blob it couldn't find locally due to
+# a lazy clone that only cloned the commits and trees.
+#
+# Please note, this sample is a minimal skeleton. No proper error handling
+# was implemented.

t/t0410/lazy-object new file +80 -0

+sub packet_bin_read {
+	my $buffer;
+	my $bytes_read = read STDIN, $buffer, 4;
+	if ( $bytes_read == 0 ) {
+
+		# EOF - Git stopped talking to us!
+		exit();
+	}
+	elsif ( $bytes_read != 4 ) {
+		die "invalid packet: '$buffer'";
+	}
+	my $pkt_size = hex($buffer);
+	if ( $pkt_size == 0 ) {
+		return ( 1, "" );
+	}
+	elsif ( $pkt_size > 4 ) {
+		my $content_size = $pkt_size - 4;
+		$bytes_read = read STDIN, $buffer, $content_size;
+		if ( $bytes_read != $content_size ) {
+			die "invalid packet ($content_size bytes expected; $bytes_read bytes read)";
+		}
+		return ( 0, $buffer );
+	}
+	else {
+		die "invalid packet size: $pkt_size";
+	}
+}
+
+sub packet_txt_read {
+	my ( $res, $buf ) = packet_bin_read();
+	unless ( $buf =~ s/\n$// ) {
+		die "A non-binary line MUST be terminated by an LF.";
+	}
+	return ( $res, $buf );
+}
+
+sub packet_bin_write {
+	my $buf = shift;
+	print STDOUT sprintf( "%04x", length($buf) + 4 );
+	print STDOUT $buf;
+	STDOUT->flush();
+}
+
+sub packet_txt_write {
+	packet_bin_write( $_[0] . "\n" );
+}
+
+sub packet_flush {
+	print STDOUT sprintf( "%04x", 0 );
+	STDOUT->flush();
+}
+
+( packet_txt_read() eq ( 0, "git-lazy-object-client" ) ) || die "bad initialize";
+( packet_txt_read() eq ( 0, "version=1" ) )		 || die "bad version";
+( packet_bin_read() eq ( 1, "" ) )                       || die "bad version end";
+
+packet_txt_write("git-lazy-object-server");
+packet_txt_write("version=1");
+packet_flush();
+
+( packet_txt_read() eq ( 0, "capability=get" ) )    || die "bad capability";
+( packet_bin_read() eq ( 1, "" ) )                  || die "bad capability end";
+
+packet_txt_write("capability=get");
+packet_flush();
+
+while (1) {
+	my ($command) = packet_txt_read() =~ /^command=([^=]+)$/;
+
+	if ( $command eq "get" ) {
+		my ($sha1) = packet_txt_read() =~ /^sha1=([0-9a-f]{40})$/;
+		packet_bin_read();
+
+		system ('git --git-dir="' . $DIR . '" cat-file blob ' . $sha1 . ' | git -c extensions.lazyobject=false hash-object -w --stdin >/dev/null 2>&1');
+		packet_txt_write(($?) ? "status=error" : "status=success");
+		packet_flush();
+	} else {
+		die "bad command '$command'";
+	}
+}

Besides review changes, this patch set now includes my rewritten lazy-loading sha1_file patch, so you can now do this (excerpted from one of the tests):

test_create_repo server
test_commit -C server 1 1.t abcdefgh
HASH=$(git hash-object server/1.t)

test_create_repo client
test_must_fail git -C client cat-file -p "$HASH"
git -C client config core.repositoryformatversion 1
git -C client config extensions.lazyobject \
"\"$TEST_DIRECTORY/t0410/lazy-object\" \"$(pwd)/server/.git\""
git -C client cat-file -p "$HASH"

with fsck still working. Also, there is no need for a list of promised blobs, and the long-running process protocol is being used.

Quoted 15 lines · Jonathan Tan

Besides review changes, this patch set now includes my rewritten lazy-loading sha1_file patch, so you can now do this (excerpted from one of the tests):

test_create_repo server
test_commit -C server 1 1.t abcdefgh
HASH=$(git hash-object server/1.t)

test_create_repo client
test_must_fail git -C client cat-file -p "$HASH"
git -C client config core.repositoryformatversion 1
git -C client config extensions.lazyobject \
"\"$TEST_DIRECTORY/t0410/lazy-object\" \"$(pwd)/server/.git\""
git -C client cat-file -p "$HASH"

Quoted 2 lines

with fsck still working. Also, there is no need for a list of promised blobs, and the long-running process protocol is being used.

I do not think I read your response to my last comment on this series, so I could be missing something large, but I am afraid that the resulting fsck is only half as useful as the normal fsck. I do not see it any better than a hypothetical castrated version of fsck that only checks the integrity of objects that appear in the local object store, without doing any connectivity checks.

Don't get me wrong. The integrity check on local objects you still do is important---that is what allows us to make sure that the local "cache" does not prevent us from going to the real source of the remote object store by having a corrupt copy.

But not being able to tell if a missing object is OK to be missing (because we can get them if/as needed from elsewhere) or we lost the sole copy of an object that we created and have not pushed out (hence we are in deep yogurt) makes it pretty much pointless to run "fsck", doesn't it? It does not give us any guarantee that our repository plus perfect network connectivity gives us an environment to build further work on.

Or am I missing something fundamental?

Well, the fsck can still detect issues like corrupt objects (as you mention above) and dangling heads, which might be real issues. But it is true that it does not give you the guarantee you describe.

From a user standpoint, this might be able to be worked around by providing a network-requiring object connectivity checking tool or by just having the user running a build to ensure that all necessary files are present.

Can we do something similar, i.e. maintain minimum set of cut-off points and adjust that set incrementally, just sufficient to ensure the integrity of objects locally created and not yet safely stored away by pushing them the "other side"?

I haven't thought things through (and I know you, Ben and others have thought much longer and harder), but I would imagine if we have a commit object [*1*], some of whose parent commits, trees and blobs are locally missing, and know that the commit exists on the "other side", we know that all of these "missing" objects that are referenced by the commit are also available from the "other side". IOW, I suspect that the same principle "shallow" uses to give us the integrity guarantee can be naturally extended to allow us to see if a broken connectivity is OK.

If we are deeply worried about this kind of broken connectivity, there is another case to care about: the server can "promise" to serve requests for some object (e.g., the tree pointed to by the server's "master") and then decide it does not want to fulfill that promise (e.g., that tree pointed to private key material and "master" was rewound to avoid it).

In the promises model, how we do we get a fresh understanding of what the server wants to promise now?

Let's step back a bit and think what already happens in the pre- lazy-object world. We record cut-off commits when a depth limited clone is created in "shallow". These essentially are promises, saying something like:

Rest assured that everything in the history behind these commits are on the other side and you can retrieve them by unshallowing.

If you traverse from your local tips and find no missing objects before reaching one of these commits, then you do not have any local corruption you need to worry about.

the other end made to us, when the shallow clone was made. And we take this promise and build more commits on top, and then we adjust these cut-off commits incrementally as we deepen our clone or make it even shallower. For this assurance to work, we of course need to assume a bit more than what we assume for a complete clone, namely, the "other side" will hold onto the history behind these, i.e. does not remind the tips it already has shown to us, or even if it does, the objects that are reachable from these cut-off points will somehow always be available to us on demand.

Can we do something similar, i.e. maintain minimum set of cut-off points and adjust that set incrementally, just sufficient to ensure the integrity of objects locally created and not yet safely stored away by pushing them the "other side"?

One possibility to conceptually have the same thing without the overhead of the list is to put the obtained-from-elsewhere objects into its own alternate object store, so that we can distinguish the two.

I mentioned
this in my e-mail but rejected it, but after some more thought, this might be sufficient - we might still need to iterate through every object to know exactly what we can assume the remote to have, but the "frontier" solution also needs this iteration, so we are no worse off.

Quoted 3 lines · Jonathan Tan

One possibility to conceptually have the same thing without the overhead of the list is to put the obtained-from-elsewhere objects into its own alternate object store, so that we can distinguish the two.

Now you are talking. Either a separate object store, or a packfile that is specially marked as such, would work.

"Maintaining a list
of object names in a flat file is too costly" is not a valid excuse to discard the integrity of locally created objects, without which Git will no longer be a version control system,

Quoted 5 lines

I mentioned
this in my e-mail but rejected it, but after some more thought, this might be sufficient - we might still need to iterate through every object to know exactly what we can assume the remote to have, but the "frontier" solution also needs this iteration, so we are no worse off.

Most importantly, this is allowed to be costly---we are doing this not at runtime all the time, but when the user says "make sure that I haven't lost objects and it is safe for me to build further on what I created locally so far" by running "git fsck".

Quoted 8 lines · Junio C Hamano

Quoted 3 lines · Jonathan Tan

One possibility to conceptually have the same thing without the overhead of the list is to put the obtained-from-elsewhere objects into its own alternate object store, so that we can distinguish the two.

Now you are talking. Either a separate object store, or a packfile that is specially marked as such, would work.

Jonathan's not in today, so let me say a few more words about this approach.

This approach implies a relaxed connectivity guarantee, by creating two classes of objects:

1. Objects that I made should satisfy the connectivity check. They can point to other objects I made, objects I fetched, or (*) objects pointed to directly by objects I fetched. More on (*) below.

The complication is in the "git gc" operation for the case (*). Today, "git gc" uses a reachability walk to decide which objects to remove --- an object referenced by no other object is fair game to remove. With (*), there is another kind of object that must not be
removed: if an object that I made, M, points to a missing/promised object, O, pointed to by a an object I fetched, F, then I cannot prune F unless there is another fetched object present to anchor O.

For example: suppose I have a sparse checkout and run

git fetch origin refs/pulls/x
git checkout -b topic FETCH_HEAD
echo "Some great modification" >> README
git add README
git commit --amend

When I run "git gc", there is nothing pointing to the commit that was pointed to by the remote ref refs/pulls/x, so it can be pruned. I would naively also expect that the tree pointed to by that commit could be pruned. But pruning it means pruning the promise that made it permissible to lack various blobs that my topic branch refers to that are outside the sparse checkout area. So "git gc" must notice that it is not safe to prune that tree.

This feels hacky. I prefer the promised object list over this approach.

Can you spell this out more? To be clear, are you speaking as a reviewer or as the project maintainer? In other words, if other reviewers are able to settle on a design that involves a relaxed guarantee for fsck in this mode that they can agree on, does this represent a veto meaning the patch can still not go through?

Quoted 5 lines · Jonathan Nieder

Can you spell this out more? To be clear, are you speaking as a reviewer or as the project maintainer? In other words, if other reviewers are able to settle on a design that involves a relaxed guarantee for fsck in this mode that they can agree on, does this represent a veto meaning the patch can still not go through?

Consider it a veto over punting without making sure that we can later come up with a solution to give such a guarantee. I am not getting a feeling that "other reviewers" are even seeking a "relaxed guarantee"---all I've seen in the thread is to give up any guarantee and to hope for the best.

Quoted 7 lines

The complication is in the "git gc" operation for the case (*). Today, "git gc" uses a reachability walk to decide which objects to remove --- an object referenced by no other object is fair game to remove. With (*), there is another kind of object that must not be
removed: if an object that I made, M, points to a missing/promised object, O, pointed to by a an object I fetched, F, then I cannot prune F unless there is another fetched object present to anchor O.

Absolutely. Lazy-objects support comes with certain cost and this is one of them.

But I do not think it is realistic to expect that you can prune anything you fetched from the "other place" (i.e. the source 'lazy-objects' hook reads from). After all, once they give out objects to their clients (like us in this case), they cannot prune it, if we take the "implicit promise" approach to avoid the cost to transmit and maintain a separate "object list".

Quoted 16 lines

For example: suppose I have a sparse checkout and run

git fetch origin refs/pulls/x
git checkout -b topic FETCH_HEAD
echo "Some great modification" >> README
git add README
git commit --amend

When I run "git gc", there is nothing pointing to the commit that was pointed to by the remote ref refs/pulls/x, so it can be pruned. I would naively also expect that the tree pointed to by that commit could be pruned. But pruning it means pruning the promise that made it permissible to lack various blobs that my topic branch refers to that are outside the sparse checkout area. So "git gc" must notice that it is not safe to prune that tree.

Quoted 2 lines

This feels hacky. I prefer the promised object list over this approach.

I think they are moral equivalents implemented differently with different assumptions. The example we are discussing makes an extra
assumption: In order to reduce the cost of transferring and maintaining the list, we assume that all objects that came during that transfer are implicitly "promised", i.e. everything behind each of these objects will later be available on demand. How these objects are marked is up to the exact mechanism (my preference is to mark the resulting packfile as special; Jon Tan's message to which my message was a resopnse alluded to using an alternate object store). If you choose to maintain a separate "object list" and have the "other side" explicitly give it, perhaps you can lift that assumption and replace it with some other assumption that assumes less.

Besides review changes, this patch set now includes my rewritten lazy-loading sha1_file patch, so you can now do this (excerpted from one of the tests):

test_create_repo server
test_commit -C server 1 1.t abcdefgh
HASH=$(git hash-object server/1.t)

test_create_repo client
test_must_fail git -C client cat-file -p "$HASH"
git -C client config core.repositoryformatversion 1
git -C client config extensions.lazyobject \
"\"$TEST_DIRECTORY/t0410/lazy-object\" \"$(pwd)/server/.git\""
git -C client cat-file -p "$HASH"

with fsck still working. Also, there is no need for a list of promised blobs, and the long-running process protocol is being used.

Changes from v1:
- added last patch that supports lazy loading
- clarified documentation in "introduce lazyobject extension" patch (following Junio's comments [1])

As listed in the changes above, I have rewritten my lazy-loading sha1_file patch to no longer use the list of promises. Also, I have added documentation about the protocol used to (hopefully) the appropriate places.

This is a minimal implementation, hopefully enough of a foundation to be built upon. In particular, I haven't added the environment variable to suppress lazy loading, and the lazy loading protocol only supports one object at a time.

Other work
----------

This differs slightly from Ben Peart's patch [2] in that the lazy-loading functionality is provided through a configured shell command instead of a hook shell script. I envision commands like "git clone", in the future, needing to pre-configure lazy loading, and I think that it will be less surprising to the user if "git clone" wrote a default configuration instead of a default hook.

This also differs from Christian Couder's patch set [3] that implement a larger-scale object database, in that (i) my patch set does not support putting objects into external databases, and (ii) my patch set requires the lazy loader to make the objects available in the local repo, instead of allowing the objects to only be stored in the external database.

[1] https://public-inbox.org/git/[email protected]/
[2] https://public-inbox.org/git/[email protected]/
[3] https://public-inbox.org/git/[email protected]/

Jonathan Tan (5):
environment, fsck: introduce lazyobject extension
fsck: support refs pointing to lazy objects
fsck: support referenced lazy objects
fsck: support lazy objects as CLI argument
sha1_file: support loading lazy objects

  Documentation/Makefile                             |   1 +
  Documentation/gitattributes.txt                    |  54 ++--------
  Documentation/gitrepository-layout.txt             |   3 +
  .../technical/long-running-process-protocol.txt    |  50 +++++++++
  Documentation/technical/repository-version.txt     |  23 +++++
  Makefile                                           |   1 +
  builtin/cat-file.c                                 |   2 +
  builtin/fsck.c                                     |  25 ++++-
  cache.h                                            |   4 +
  environment.c                                      |   1 +
  lazy-object.c                                      |  80 +++++++++++++++
  lazy-object.h                                      |  12 +++
  object.c                                           |   7 ++
  object.h                                           |  13 +++
  setup.c                                            |   7 +-
  sha1_file.c                                        |  44 +++++---
  t/t0410-lazy-object.sh                             | 113 +++++++++++++++++++++
  t/t0410/lazy-object                                | 102 +++++++++++++++++++
  18 files changed, 478 insertions(+), 64 deletions(-)

create mode 100644 Documentation/technical/long-running-process-protocol.txt create mode 100644 lazy-object.c
create mode 100644 lazy-object.h
create mode 100755 t/t0410-lazy-object.sh
create mode 100755 t/t0410/lazy-object