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

[Junio C Hamano <gitster@pobox.com>]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

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

Hmph.  the use of ->util field in this patch feels that it was
something commit-slab data structure was invented to solve.


> 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.
> +			 */

... or perhaps make the bitmap into

	struct {
	        int refcnt;
        	uint32_t bits[FLEX_ARRAY];
	}

and refcnt them?


> +			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;

I am Confused.

The loop only made sure that all the elements in the array[] is
still missing (or, ... is this function supposed to be called before
installing a new pack???  It is unclear.  But if new objects were
unpacked while receiving, then there is no "not install the new
objects and check" possible, so I'd assume this is called after
receiving and registering a new pack to the object store).

But then, can it be that you had N-1 "shallow points" originally,
the pack has a reference to a new missing commit, and the array has
N "shallow points" in total?  Or is the caller expected to call this
function with shallow pointing at a pre-transfer shallow points?

> +	/*
> +	 * Prepare the commit graph to track what refs can reach what
> +	 * (new) shallow points.
> +	 */
> +	nr = get_max_object_index();

Hmph. At this point (again, there is no description on where in the
overall sequence of events this function is designed to be called,
so it is impossible to review the logic), is it expected that we
have seen all the objects under the sun and marked them in a
specific way?

> +	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;
> +}