Re: [PATCH v2 4/5] index-pack, unpack-objects: add --not-so-strict for connectivity check

3 messages, 3 authors, 2016-06-15 · open the first message on its own page

Re: [PATCH v2 4/5] index-pack, unpack-objects: add --not-so-strict for connectivity check

From: Junio C Hamano <hidden>
Date: 2016-06-15 22:57:07

Junio C Hamano [off-list ref] writes:
Duy Nguyen [off-list ref] writes:
quoted
What do you mean by "partial history"? Do we have dangling pointers
after doing that commit walker?
"^C" will leave the objects and it is safe because it will not
update refs.

But your code that does not verify the full connectivity from such
an object (that is outside the transferred pack) to the rest of the
history will then make the resulting repository broken, if you
update your ref to point at such an object, no?  Ading a single
has_sha1_file() only verifies that single object, not the history
behind it.
Let's illustrate.  Imagine your project as a whole has this history:

---A---B---C---D---E

When you cloned, it only had up to A, so that is what you have.
Then you try http walker, which slurps E, wants to go to D and dig
down, but after fetching E, some trees and blobs in E, and fetching
D, but before completing D' trees and blobs, your ISP cuts you off.

You have these in your object store:

---A           D---E

but your ref is pointing at A, because we promise that we make sure
full connectivity before we update the ref, and even if you have
commits D and E, the associated trees, blobs, and commits behind
this subpart of the history are missing.

Now you try to fetch from another mirror over the pack transport.
You advertise that you have A (but you do not advertise E, because
your refs do not point at it), and you expect all objects that are
listed in "rev-list --objects A..E" to be gien to you.

Unfortunately, the mirror is broken, in that it only packs the
objects that appear in "rev-list --objects A..B", but still tells
you that it is sending objects to complete history leading to E.

Your object store would have objects like this after this transfer:

---A---B       D---E

You may still have commits D and E unpruned, but are missing C, and
trees and blobs that are needed in D or E.

You have to walk the history from E and list the necessary objects
yourself, running has_sha1_file() on all of them, to prove that you
have everything needed, and the only things you can trust are your
refs (in this case, A).

If you verify that all the objects in the transferred pack are
complete, and also verify that the object the transfer proposes to
update your ref to is _in_ that pack, then you can detect a mirror
that is broken and only sends objects for A..B, but that does not
actually solve the issue.  Imagine another broken mirror that
instead sends objects for E.  E, its trees and all its blobs may be
in the pack and the only outgoing link from that pack may be a
pointer out of E pointing at D.  You happen to _have_ it in your
object store, but that does not mean you can update your ref to E
(remember, you do not have trees and blobs to complete D, or the
history behind it).

The current check is implemented in the way we currently do it,
_not_ because we were stupid and did not realize the optimization
possibility (in other words, what your patch proposes is not new),
but because we rejected this approach because it was not safe.

Re: [PATCH v2 4/5] index-pack, unpack-objects: add --not-so-strict for connectivity check

From: Duy Nguyen <hidden>
Date: 2016-06-15 22:57:07

On Thu, May 02, 2013 at 11:55:57PM -0700, Junio C Hamano wrote:
Let's illustrate.  Imagine your project as a whole has this history:
[snip]

OK I agree my approach is flawed. But if all these are met, we can be
sure the new refs are good, correct?

 - all refs point to an object in the pack
 - there are no dangling pointers in any object in the pack
 - all objects in the pack does not point to any objects outside the
   pack

We can check all these for the clone case with the patch below, even
if somehow we get some bad objects in the cloned repository before the
new pack arrives.

-- 8< --
Subject: [PATCH] clone: open a shortcut for connectivity check

In order to make sure the cloned repository is good, we run "rev-list
--objects --not --all $new_refs" on the repository. This is expensive
on large repositories. This patch attempts to mitigate the impact in
this special case.

In the "good" clone case, we only have one pack. If all of the
following are met, we can be sure that all objects reachable from the
new refs exist, which is the intention of running "rev-list ...":

 - all refs point to an object in the pack
 - there are no dangling pointers in any object in the pack
 - all objects in the pack does not point to objects outside the pack

The second and third checks can be done with the help of index-pack as
a slight modification of --strict check (which introduces a new
condition for the shortcut: pack transfer must be used and the number
of objects large enough to call index-pack). The first is checked in
check_everything_connected after we get an "ok" from index-pack.

"index-pack + new checks" is still faster than "index-pack + rev-list"
currently, which is the whole point of this patch. If any of the
conditions fails, we fall back to good old and expensive "rev-list
..". In that case it's even more expensive because we have to pay for
the new checks in index-pack.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 Documentation/git-index-pack.txt |  3 +++
 builtin/clone.c                  | 11 ++++++++---
 builtin/index-pack.c             | 35 ++++++++++++++++++++++++++---------
 connected.c                      | 34 +++++++++++++++++++++++++++++++++-
 connected.h                      |  5 +++++
 fetch-pack.c                     | 11 ++++++++++-
 fetch-pack.h                     |  4 +++-
 transport.c                      |  4 ++++
 transport.h                      |  2 ++
 9 files changed, 94 insertions(+), 15 deletions(-)
diff --git a/Documentation/git-index-pack.txt b/Documentation/git-index-pack.txt
index bde8eec..7a4e055 100644
--- a/Documentation/git-index-pack.txt
+++ b/Documentation/git-index-pack.txt
@@ -74,6 +74,9 @@ OPTIONS
 --strict::
 	Die, if the pack contains broken objects or links.
 
+--check-self-contained-and-connected::
+	Die if the pack contains broken links. For internal use only.
+
 --threads=<n>::
 	Specifies the number of threads to spawn when resolving
 	deltas. This requires that index-pack be compiled with
diff --git a/builtin/clone.c b/builtin/clone.c
index dad4265..427bec4 100644
--- a/builtin/clone.c
+++ b/builtin/clone.c
@@ -542,13 +542,15 @@ static void update_remote_refs(const struct ref *refs,
 			       const struct ref *mapped_refs,
 			       const struct ref *remote_head_points_at,
 			       const char *branch_top,
-			       const char *msg)
+			       const char *msg,
+			       struct transport *transport)
 {
 	const struct ref *rm = mapped_refs;
 
 	if (0 <= option_verbosity)
 		printf(_("Checking connectivity... "));
-	if (check_everything_connected(iterate_ref_map, 0, &rm))
+	if (check_everything_connected_with_transport(iterate_ref_map,
+						      0, &rm, transport))
 		die(_("remote did not send all necessary objects"));
 	if (0 <= option_verbosity)
 		printf(_("done\n"));
@@ -893,6 +895,9 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		if (option_upload_pack)
 			transport_set_option(transport, TRANS_OPT_UPLOADPACK,
 					     option_upload_pack);
+
+		if (transport->smart_options)
+			transport->smart_options->check_self_contained_and_connected = 1;
 	}
 
 	refs = transport_get_remote_refs(transport);
@@ -954,7 +959,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		transport_fetch_refs(transport, mapped_refs);
 
 	update_remote_refs(refs, mapped_refs, remote_head_points_at,
-			   branch_top.buf, reflog_msg.buf);
+			   branch_top.buf, reflog_msg.buf, transport);
 
 	update_head(our_head_points_at, remote_head, reflog_msg.buf);
 
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 1fd56d9..6aa7bb6 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -77,8 +77,10 @@ static int nr_threads;
 
 static int from_stdin;
 static int strict;
+static int do_fsck_object;
 static int verbose;
 static int show_stat;
+static int check_self_contained_and_connected;
 
 static struct progress *progress;
 
@@ -187,13 +189,13 @@ static int mark_link(struct object *obj, int type, void *data)
 
 /* The content of each linked object must have been checked
    or it must be already present in the object database */
-static void check_object(struct object *obj)
+static unsigned check_object(struct object *obj)
 {
 	if (!obj)
-		return;
+		return 0;
 
 	if (!(obj->flags & FLAG_LINK))
-		return;
+		return 0;
 
 	if (!(obj->flags & FLAG_CHECKED)) {
 		unsigned long size;
@@ -201,17 +203,20 @@ static void check_object(struct object *obj)
 		if (type != obj->type || type <= 0)
 			die(_("object of unexpected type"));
 		obj->flags |= FLAG_CHECKED;
-		return;
+		return 1;
 	}
+
+	return 0;
 }
 
-static void check_objects(void)
+static unsigned check_objects(void)
 {
-	unsigned i, max;
+	unsigned i, max, foreign_nr;
 
 	max = get_max_object_index();
 	for (i = 0; i < max; i++)
-		check_object(get_indexed_object(i));
+		foreign_nr += check_object(get_indexed_object(i));
+	return foreign_nr;
 }
 
 
@@ -756,7 +761,8 @@ static void sha1_object(const void *data, struct object_entry *obj_entry,
 			obj = parse_object_buffer(sha1, type, size, buf, &eaten);
 			if (!obj)
 				die(_("invalid %s"), typename(type));
-			if (fsck_object(obj, 1, fsck_error_function))
+			if (do_fsck_object &&
+			    fsck_object(obj, 1, fsck_error_function))
 				die(_("Error in object"));
 			if (fsck_walk(obj, mark_link, NULL))
 				die(_("Not all child objects of %s are reachable"), sha1_to_hex(obj->sha1));
@@ -1490,6 +1496,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	struct pack_idx_entry **idx_objects;
 	struct pack_idx_option opts;
 	unsigned char pack_sha1[20];
+	unsigned foreign_nr = 1;	/* zero is a "good" value, assume bad */
 
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage(index_pack_usage);
@@ -1511,6 +1518,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 				fix_thin_pack = 1;
 			} else if (!strcmp(arg, "--strict")) {
 				strict = 1;
+				do_fsck_object = 1;
+			} else if (!strcmp(arg, "--check-self-contained-and-connected")) {
+				strict = 1;
+				check_self_contained_and_connected = 1;
 			} else if (!strcmp(arg, "--verify")) {
 				verify = 1;
 			} else if (!strcmp(arg, "--verify-stat")) {
@@ -1624,7 +1635,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	conclude_pack(fix_thin_pack, curr_pack, pack_sha1);
 	free(deltas);
 	if (strict)
-		check_objects();
+		foreign_nr = check_objects();
 
 	if (show_stat)
 		show_pack_info(stat_only);
@@ -1650,5 +1661,11 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	if (index_name == NULL)
 		free((void *) curr_index);
 
+	/*
+	 * Let the caller know this pack is not self contained
+	 */
+	if (check_self_contained_and_connected && foreign_nr)
+		return 1;
+
 	return 0;
 }
diff --git a/connected.c b/connected.c
index 1e89c1c..fae8d64 100644
--- a/connected.c
+++ b/connected.c
@@ -2,7 +2,12 @@
 #include "run-command.h"
 #include "sigchain.h"
 #include "connected.h"
+#include "transport.h"
 
+int check_everything_connected(sha1_iterate_fn fn, int quiet, void *cb_data)
+{
+	return check_everything_connected_with_transport(fn, quiet, cb_data, NULL);
+}
 /*
  * If we feed all the commits we want to verify to this command
  *
@@ -14,7 +19,10 @@
  *
  * Returns 0 if everything is connected, non-zero otherwise.
  */
-int check_everything_connected(sha1_iterate_fn fn, int quiet, void *cb_data)
+int check_everything_connected_with_transport(sha1_iterate_fn fn,
+					      int quiet,
+					      void *cb_data,
+					      struct transport *transport)
 {
 	struct child_process rev_list;
 	const char *argv[] = {"rev-list", "--objects",
@@ -22,10 +30,23 @@ int check_everything_connected(sha1_iterate_fn fn, int quiet, void *cb_data)
 	char commit[41];
 	unsigned char sha1[20];
 	int err = 0;
+	struct packed_git *new_pack = NULL;
 
 	if (fn(cb_data, sha1))
 		return err;
 
+	if (transport && transport->smart_options &&
+	    transport->smart_options->self_contained_and_connected &&
+	    transport->pack_lockfile &&
+	    !suffixcmp(transport->pack_lockfile, ".keep")) {
+		struct strbuf idx_file = STRBUF_INIT;
+		strbuf_addstr(&idx_file, transport->pack_lockfile);
+		strbuf_setlen(&idx_file, idx_file.len - 5); /* ".keep" */
+		strbuf_addstr(&idx_file, ".idx");
+		new_pack = add_packed_git(idx_file.buf, idx_file.len, 1);
+		strbuf_release(&idx_file);
+	}
+
 	if (quiet)
 		argv[5] = "--quiet";
 
@@ -42,6 +63,17 @@ int check_everything_connected(sha1_iterate_fn fn, int quiet, void *cb_data)
 
 	commit[40] = '\n';
 	do {
+		/*
+		 * If index-pack already checked that:
+		 * - there are no dangling pointers in the new pack
+		 * - the pack is self contained
+		 * Then if the updated ref is in the new pack, then we
+		 * are sure the ref is good and not sending it to
+		 * rev-list for verification.
+		 */
+		if (new_pack && find_pack_entry_one(sha1, new_pack))
+			continue;
+
 		memcpy(commit, sha1_to_hex(sha1), 40);
 		if (write_in_full(rev_list.in, commit, 41) < 0) {
 			if (errno != EPIPE && errno != EINVAL)
diff --git a/connected.h b/connected.h
index 7e4585a..0b060b7 100644
--- a/connected.h
+++ b/connected.h
@@ -1,6 +1,8 @@
 #ifndef CONNECTED_H
 #define CONNECTED_H
 
+struct transport;
+
 /*
  * Take callback data, and return next object name in the buffer.
  * When called after returning the name for the last object, return -1
@@ -16,5 +18,8 @@ typedef int (*sha1_iterate_fn)(void *, unsigned char [20]);
  * Return 0 if Ok, non zero otherwise (i.e. some missing objects)
  */
 extern int check_everything_connected(sha1_iterate_fn, int quiet, void *cb_data);
+extern int check_everything_connected_with_transport(sha1_iterate_fn, int quiet,
+						     void *cb_data,
+						     struct transport *transport);
 
 #endif /* CONNECTED_H */
diff --git a/fetch-pack.c b/fetch-pack.c
index 17cfa88..75c6f05 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -690,6 +690,7 @@ static int get_pack(struct fetch_pack_args *args,
 	const char **av;
 	int do_keep = args->keep_pack;
 	struct child_process cmd;
+	int ret;
 
 	memset(&demux, 0, sizeof(demux));
 	if (use_sideband) {
@@ -741,11 +742,14 @@ static int get_pack(struct fetch_pack_args *args,
 				strcpy(keep_arg + s, "localhost");
 			*av++ = keep_arg;
 		}
+		if (args->check_self_contained_and_connected)
+			*av++ = "--check-self-contained-and-connected";
 	}
 	else {
 		*av++ = "unpack-objects";
 		if (args->quiet || args->no_progress)
 			*av++ = "-q";
+		args->check_self_contained_and_connected = 0;
 	}
 	if (*hdr_arg)
 		*av++ = hdr_arg;
@@ -766,7 +770,12 @@ static int get_pack(struct fetch_pack_args *args,
 		close(cmd.out);
 	}
 
-	if (finish_command(&cmd))
+	ret = finish_command(&cmd);
+	if (!ret || (args->check_self_contained_and_connected && ret == 1))
+		args->self_contained_and_connected =
+			args->check_self_contained_and_connected &&
+			ret == 0;
+	else
 		die("%s failed", argv[0]);
 	if (use_sideband && finish_async(&demux))
 		die("error in sideband demultiplexer");
diff --git a/fetch-pack.h b/fetch-pack.h
index dc5266c..40f08ba 100644
--- a/fetch-pack.h
+++ b/fetch-pack.h
@@ -16,7 +16,9 @@ struct fetch_pack_args {
 		verbose:1,
 		no_progress:1,
 		include_tag:1,
-		stateless_rpc:1;
+		stateless_rpc:1,
+		check_self_contained_and_connected:1,
+		self_contained_and_connected:1;
 };
 
 /*
diff --git a/transport.c b/transport.c
index ba5d8af..359a671 100644
--- a/transport.c
+++ b/transport.c
@@ -534,6 +534,8 @@ static int fetch_refs_via_pack(struct transport *transport,
 	args.quiet = (transport->verbose < 0);
 	args.no_progress = !transport->progress;
 	args.depth = data->options.depth;
+	args.check_self_contained_and_connected =
+		data->options.check_self_contained_and_connected;
 
 	if (!data->got_remote_heads) {
 		connect_setup(transport, 0, 0);
@@ -551,6 +553,8 @@ static int fetch_refs_via_pack(struct transport *transport,
 		refs = NULL;
 	data->conn = NULL;
 	data->got_remote_heads = 0;
+	data->options.self_contained_and_connected =
+		args.self_contained_and_connected;
 
 	free_refs(refs_tmp);
 
diff --git a/transport.h b/transport.h
index fcb1d25..4edebc5 100644
--- a/transport.h
+++ b/transport.h
@@ -8,6 +8,8 @@ struct git_transport_options {
 	unsigned thin : 1;
 	unsigned keep : 1;
 	unsigned followtags : 1;
+	unsigned check_self_contained_and_connected : 1;
+	unsigned self_contained_and_connected : 1;
 	int depth;
 	const char *uploadpack;
 	const char *receivepack;
-- 
1.8.2.82.gc24b958
-- 8< --

Re: [PATCH v2 4/5] index-pack, unpack-objects: add --not-so-strict for connectivity check

From: Eric Sunshine <hidden>
Date: 2016-06-15 22:57:07

On Fri, May 3, 2013 at 3:09 AM, Duy Nguyen [off-list ref] wrote:
Subject: [PATCH] clone: open a shortcut for connectivity check

In order to make sure the cloned repository is good, we run "rev-list
--objects --not --all $new_refs" on the repository. This is expensive
on large repositories. This patch attempts to mitigate the impact in
this special case.

In the "good" clone case, we only have one pack. If all of the
following are met, we can be sure that all objects reachable from the
new refs exist, which is the intention of running "rev-list ...":

 - all refs point to an object in the pack
 - there are no dangling pointers in any object in the pack
 - all objects in the pack does not point to objects outside the pack
"no objects in the pack point to..."
The second and third checks can be done with the help of index-pack as
a slight modification of --strict check (which introduces a new
condition for the shortcut: pack transfer must be used and the number
of objects large enough to call index-pack). The first is checked in
check_everything_connected after we get an "ok" from index-pack.

"index-pack + new checks" is still faster than "index-pack + rev-list"
currently, which is the whole point of this patch. If any of the
conditions fails, we fall back to good old and expensive "rev-list
..". In that case it's even more expensive because we have to pay for
the new checks in index-pack.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help