[PATCH v3 08/28] shallow.c: add mark_new_shallow_refs()

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

When we receive a pack and the shallow points from another repository,
we may need to add more shallow points to current repo to make sure no
commits point to nowhere. But usually we don't want to do so because
(in future) new shallow points invalidate pack bitmaps and we need to
rebuild them again, which is not cheap.

So the default way is we allow ref updates that do not introduce new
shallow points and mark the others. If the user is fine with new
shallow point addition, we accept the marked refs.

But even so we do not blindly accept all shallow points provided. Some
of them might not point to any commits in the new pack. Some might
even do, but those might be unreachable object islands. Only shallow
points that are reachable from old and new refs can stay.

The way it's implemented is paint down from each ref, attach a bitmap
to each commit where one bit represents one ref. In order to avoid
allocating new bitmap for every commit, we try to reuse the same
bitmap for parent commits if possible. This reduces allocation and
leaks deliberately because it's hard to keep/time consuming track how
many pointers to the same buffer.

In a typical push or fetch, the new pack should not carry new shallow
roots. If the current repo does not have any commit islands refered by
the sender's shallow roots either, this function is just a few
has_sha1_file(). So quite cheap.

Once the sender diverts from that path (or the receiver detects
shallow roots attached to commit islands from remove_reachable_shallow_points),
it'll be a lot more expensive. Pack bitmaps won't help this kind of
commit traversal, but commit cache might.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit.h  |   4 ++
 shallow.c | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 223 insertions(+)

diff --git a/commit.h b/commit.h
index 98044e6..e1fd587 100644
--- a/commit.h
+++ b/commit.h
@@ -194,6 +194,7 @@ extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);
 #define INFINITE_DEPTH 0x7fffffff
 
 struct extra_have_objects;
+struct ref;
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
 extern int for_each_commit_graft(each_commit_graft_fn, void *);
@@ -209,6 +210,9 @@ extern char *setup_temporary_shallow(void);
 extern void advertise_shallow_grafts(int);
 extern void remove_reachable_shallow_points(struct extra_have_objects *out,
 					    const struct extra_have_objects *in);
+extern int mark_new_shallow_refs(const struct extra_have_objects *ref,
+				 int *ref_status, uint32_t **used,
+				 const struct extra_have_objects *shallow);
 
 int is_descendant_of(struct commit *, struct commit_list *);
 int in_merge_bases(struct commit *, struct commit *);
diff --git a/shallow.c b/shallow.c
index a974d2d..c92a1dc 100644
--- a/shallow.c
+++ b/shallow.c
@@ -4,6 +4,8 @@
 #include "pkt-line.h"
 #include "remote.h"
 #include "refs.h"
+#include "diff.h"
+#include "revision.h"
 
 static int is_shallow = -1;
 static struct stat shallow_stat;
@@ -280,3 +282,220 @@ void remove_reachable_shallow_points(struct extra_have_objects *out,
 	}
 	free(ca.commits);
 }
+
+static int paint_down(const unsigned char *sha1, int id, int nr_bits, int quick)
+{
+	int hit_bottom = 0;
+	unsigned int i, nr;
+	struct commit_list *head = NULL;
+	int bitmap_nr = (nr_bits + 31) / 32;
+	int bitmap_size = bitmap_nr * sizeof(uint32_t);
+	uint32_t *tmp = xmalloc(bitmap_size);
+	uint32_t *bitmap = xcalloc(bitmap_size, sizeof(uint32_t));
+	bitmap[id / 32] |= (1 << (id % 32));
+	commit_list_insert(lookup_commit(sha1), &head);
+	while (head) {
+		struct commit_list *p;
+		struct commit *c = head->item;
+		uint32_t *c_util = c->util;
+
+		p = head;
+		head = head->next;
+		free(p);
+
+		if (c->object.flags & (SEEN | UNINTERESTING))
+			continue;
+		else
+			c->object.flags |= SEEN;
+
+		if (c->util == NULL)
+			c->util = bitmap;
+		else {
+			/*
+			 * Deliberately leak a lot in commit->util
+			 * because there can be many pointers to the
+			 * same bitmap. Probably should allocate in a
+			 * pool and free the whole pool at the end.
+			 */
+			memcpy(tmp, c_util, bitmap_size);
+			for (i = 0; i < bitmap_nr; i++)
+				tmp[i] |= bitmap[i];
+			if (memcmp(tmp, c_util, bitmap_size)) {
+				c->util = xmalloc(bitmap_size);
+				memcpy(c->util, tmp, bitmap_size);
+			}
+		}
+
+		if (c->object.flags & BOTTOM) {
+			hit_bottom = 1;
+			if (quick) {
+				free_commit_list(head);
+				break;
+			} else
+				continue;
+		}
+
+		if (parse_commit(c))
+			die("unable to parse commit %s",
+			    sha1_to_hex(c->object.sha1));
+
+		for (p = c->parents; p; p = p->next) {
+			if (p->item->object.flags & SEEN)
+				continue;
+			if (p->item->util == NULL || p->item->util == c_util)
+				p->item->util = c->util;
+			commit_list_insert(p->item, &head);
+		}
+	}
+
+	nr = get_max_object_index();
+	for (i = 0; i < nr; i++) {
+		struct object *o = get_indexed_object(i);
+		if (o && o->type == OBJ_COMMIT) {
+			o->flags &= ~SEEN;
+		}
+	}
+
+	free(tmp);
+	return hit_bottom;
+}
+
+static int mark_uninteresting(const char *refname,
+			      const unsigned char *sha1,
+			      int flags, void *cb_data)
+{
+	struct commit *commit = lookup_commit(sha1);
+	commit->object.flags |= UNINTERESTING;
+	mark_parents_uninteresting(commit);
+	return 0;
+}
+
+struct saved_util {
+	unsigned char sha1[20];
+	void *util;
+};
+
+/*
+ * Given a set of refs and shallow roots, find out what ref can reach
+ * any of the given roots. If so mark that ref "reject_flag". If
+ * "used" is not NULL, mark all reachable roots. Return how many refs
+ * that need new shallow points.
+ */
+int mark_new_shallow_refs(const struct extra_have_objects *ref,
+			  int *ref_status, uint32_t **used,
+			  const struct extra_have_objects *shallow)
+{
+	struct saved_util *util = NULL;
+	unsigned int i, nr, ret = 0, nr_util = 0, alloc_util = 0;
+
+	/*
+	 * Quick check to see if we may need to add new shallow
+	 * roots. Go through the list of root candidates and check if
+	 * they exist (either in current repo, or in the new pack, we
+	 * can't distinguish).
+	 *
+	 * 1) If none of the new roots exist, the pack must connect to
+	 *    the main object graph, which is already guarded by
+	 *    current repo's shallow roots and we will not need to
+	 *    consider adding new shallow roots, so we can exit early.
+	 *
+	 * 2) The pack may connect to some existing object islands in
+	 *    current repo then add shallow roots to plug loose ends
+	 *    from those islands. In that case, new shallow roots must
+	 *    also exist in the repo as this stage (old objects plus
+	 *    the new pack).
+	 *
+	 * 3) The last, easiest case, is the pack contains some
+	 *    shallow roots, which may be used to tie up loose ends of
+	 *    some new refs, or redundanty (tying up loose ends of new
+	 *    object islands)
+	 */
+	for (i = 0;i < shallow->nr; i++)
+		if (has_sha1_file(shallow->array[i]))
+			break;
+	if (i == shallow->nr)
+		/*
+		 * this is the first and also the common case, where
+		 * the new pack does not carry any new shallow
+		 * points. No need to to the expensive commit traverse
+		 * dance below.
+		 */
+		return 0;
+
+	/*
+	 * Prepare the commit graph to track what refs can reach what
+	 * (new) shallow points.
+	 */
+	nr = get_max_object_index();
+	for (i = 0; i < nr; i++) {
+		struct object *o = get_indexed_object(i);
+		struct commit *c = (struct commit *)o;
+		if (!o || o->type != OBJ_COMMIT)
+			continue;
+
+		o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
+		/*
+		 * git-fetch makes use of "util" field. Save it and
+		 * restore later. For fetch/clone/push, "nr" should be
+		 * small because rev-list is delayed to pack-objects.
+		 */
+		if (c->util) {
+			ALLOC_GROW(util, nr_util+1, alloc_util);
+			hashcpy(util[nr_util].sha1, o->sha1);
+			util[nr_util].util = c->util;
+			nr_util++;
+			c->util = NULL;
+		}
+	}
+
+	/*
+	 * "--not --all" to cut short the traversal if new refs
+	 * connect to old refs. If not (e.g. force ref updates) it'll
+	 * have to go down to the current shallow roots.
+	 *
+	 * We could detect that a new commit is connected to an
+	 * existing commit by keeping new objects in a pack (i.e. the
+	 * index-pack code path) then check commit origin. If so stop
+	 * short, so we don't need to get to the bottom. But then it
+	 * will not work for case #2 because we need to go through
+	 * some of our commits before reaching new shallow roots.
+	 */
+	head_ref(mark_uninteresting, NULL);
+	for_each_ref(mark_uninteresting, NULL);
+
+	for (i = 0; i < shallow->nr; i++)
+		if (has_sha1_file(shallow->array[i])) {
+			struct commit *c = lookup_commit(shallow->array[i]);
+			c->object.flags |= BOTTOM;
+		}
+
+	for (i = 0; i < ref->nr; i++)
+		if (paint_down(ref->array[i], i, ref->nr, used == NULL)) {
+			if (ref_status)
+				ref_status[i] = 1;
+			ret++;
+		}
+
+	if (used) {
+		for (i = 0; i < shallow->nr; i++) {
+			struct commit *c = lookup_commit(shallow->array[i]);
+			used[i] = c->util;
+		}
+	}
+
+	if (nr_util) {
+		nr = get_max_object_index();
+		for (i = 0; i < nr; i++) {
+			struct object *o = get_indexed_object(i);
+			if (o && o->type == OBJ_COMMIT)
+				((struct commit *)o)->util = NULL;
+		}
+		for (i = 0; i < nr_util; i++) {
+			struct commit *c = lookup_commit(util[i].sha1);
+			c->util = util[i].util;
+		}
+		free(util);
+	}
+
+	return ret;
+}
-- 
1.8.2.83.gc99314b