git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Junio C Hamano <gitster@pobox.com>
To: Srinidhi Kaushik <shrinidhi.kaushik@gmail.com>
Cc: git@vger.kernel.org
Subject: Re: [PATCH v7 1/3] push: add reflog check for "--force-if-includes"
Date: Sat, 26 Sep 2020 16:42:10 -0700	[thread overview]
Message-ID: <xmqqwo0ggl65.fsf@gitster.c.googlers.com> (raw)
In-Reply-To: <20200926114626.28823-2-shrinidhi.kaushik@gmail.com> (Srinidhi Kaushik's message of "Sat, 26 Sep 2020 17:16:24 +0530")

Srinidhi Kaushik <shrinidhi.kaushik@gmail.com> writes:

> @@ -2252,11 +2263,11 @@ int is_empty_cas(const struct push_cas_option *cas)
>  /*
>   * Look at remote.fetch refspec and see if we have a remote
>   * tracking branch for the refname there.  Fill its current
> - * value in sha1[].
> + * value in sha1[], and as a string.

I think the array being referred to was renamed to oid[] sometime
ago.  "and as a string" makes it sound as if sha1[] gets the value
as 40-hex object name text, but that is not what is being done.

    Fill the name of the remote-tracking branch in *dst_refname,
    and the name of the commit object at tis tip in oid[].

perhaps?

>   * If we cannot do so, return negative to signal an error.
>   */
>  static int remote_tracking(struct remote *remote, const char *refname,
> -			   struct object_id *oid)
> +			   struct object_id *oid, char **dst_refname)
>  {
>  	char *dst;
>  
> @@ -2265,9 +2276,154 @@ static int remote_tracking(struct remote *remote, const char *refname,
>  		return -1; /* no tracking ref for refname at remote */
>  	if (read_ref(dst, oid))
>  		return -1; /* we know what the tracking ref is but we cannot read it */
> +
> +	*dst_refname = dst;
> +	return 0;
> +}
> +
> +/*
> + * The struct "reflog_commit_list" and related helper functions
> + * for list manipulation are used for collecting commits into a
> + * list during reflog traversals in "if_exists_or_grab_until()".

Has the name of that function changed since this comment was
written?

> + */
> +struct reflog_commit_list {
> +	struct commit **items;

Name an array in singular when its primary use is to work on an
element at a time---that will let you say item[4] to call the 4-th
item, instead of items[4] that smells awkward.

An array that is used mostly to pass around a collection as a whole
is easier to think about when given a plural name, though.

> +	size_t nr, alloc;
> +};
> +
> +/* Add a commit to list. */
> +static void add_commit(struct reflog_commit_list *list, struct commit *commit)
> +{
> +	ALLOC_GROW(list->items, list->nr + 1, list->alloc);
> +	list->items[list->nr++] = commit;
> +}
> +
> +/* Free and reset the list. */
> +static void free_reflog_commit_list(struct reflog_commit_list *list)
> +{
> +	FREE_AND_NULL(list->items);
> +	list->nr = list->alloc = 0;
> +}
> +
> +struct check_and_collect_until_cb_data {
> +	struct commit *remote_commit;
> +	struct reflog_commit_list *local_commits;
> +	timestamp_t remote_reflog_timestamp;
> +};
> +
> +/* Get the timestamp of the latest entry. */
> +static int peek_reflog(struct object_id *o_oid, struct object_id *n_oid,
> +		       const char *ident, timestamp_t timestamp,
> +		       int tz, const char *message, void *cb_data)
> +{
> +	timestamp_t *ts = cb_data;
> +	*ts = timestamp;
> +	return 1;
> +}

The idea is to use a callback that immediately says "no more" to
grab the data from the first item in the iteration.  It feels
somewhat awkward but because there is no "give us the Nth entry" API
function, it is the cleanest way we can do this.

> +static int check_and_collect_until(struct object_id *o_oid,
> +				   struct object_id *n_oid,
> +				   const char *ident, timestamp_t timestamp,
> +				   int tz, const char *message, void *cb_data)
> +{
> +	struct commit *commit;
> +	struct check_and_collect_until_cb_data *cb = cb_data;
> +
> +	/*
> +	 * If the reflog entry timestamp is older than the remote ref's
> +	 * latest reflog entry, there is no need to check or collect
> +	 * entries older than this one.
> +	 */
> +	if (timestamp < cb->remote_reflog_timestamp)
> +		return -1;
> +
> +	/* An entry was found. */
> +	if (oideq(n_oid, &cb->remote_commit->object.oid))
> +		return 1;
> +
> +	/* Look-up the commit and append it to the list. */
> +	if ((commit = lookup_commit_reference(the_repository, n_oid)))
> +		add_commit(cb->local_commits, commit);

This is merely a minor naming thing, but if you rename add_commit()
to append_commit(), you probably do not even need the comment before
this statement.

>  	return 0;
>  }
>  
> +#define MERGE_BASES_BATCH_SIZE 8

Hmph.  Do we still need batching?

> +/*
> + * Iterate through the reflog of the local ref to check if there is an entry
> + * for the given remote-tracking ref; runs until the timestamp of an entry is
> + * older than latest timestamp of remote-tracking ref's reflog. Any commits
> + * are that seen along the way are collected into a list to check if the
> + * remote-tracking ref is reachable from any of them.
> + */
> +static int is_reachable_in_reflog(const char *local, const struct ref *remote)
> +{
> +	timestamp_t date;
> +	struct commit *commit;
> +	struct commit **chunk;
> +	struct check_and_collect_until_cb_data cb;
> +	struct reflog_commit_list list = { NULL, 0, 0 };
> +	size_t count = 0, batch_size = 0;
> +	int ret = 0;
> +
> +	commit = lookup_commit_reference(the_repository, &remote->old_oid);
> +	if (!commit)
> +		goto cleanup_return;
> +
> +	/*
> +	 * Get the timestamp from the latest entry
> +	 * of the remote-tracking ref's reflog.
> +	 */
> +	for_each_reflog_ent_reverse(remote->tracking_ref, peek_reflog, &date);
> +
> +	cb.remote_commit = commit;
> +	cb.local_commits = &list;
> +	cb.remote_reflog_timestamp = date;
> +	ret = for_each_reflog_ent_reverse(local, check_and_collect_until, &cb);
> +
> +	/* We found an entry in the reflog. */
> +	if (ret > 0)
> +		goto cleanup_return;

Good.  So '1' from the callback is "we found one, no need to look
further and no need to do merge-base", and '-1' from the callback is
"we looked at all entries that are young enough to matter and we
didn't find exact match".  Makes sense.

> +	/*
> +	 * Check if the remote commit is reachable from any
> +	 * of the commits in the collected list, in batches.
> +	 */

I do not know if batching would help (have you measured it?), but if
we were to batch, it is more common to arrange the loop like this:

	for (chunk = list.items;
             chunk < list.items + list.nr;
	     chunk += size) {
             	size = list.items + list.nr - chunk;
                if (MERGE_BASES_BATCH_SIZE < size)
			size = MERGE_BASES_BATCH_SIZE;
		... use chunk[0..size] ...
		chunk += size;
	}

That is, assume that we can grab everything during this round, and
if that bites off too many, clamp it to the maximum value.  If you
are not comfortable with pointer arithmetic, it is also fine to use
an auxiliary variable 'count', but ...

> +	chunk = list.items;
> +	while (count < list.nr) {
> +		batch_size = MERGE_BASES_BATCH_SIZE;
> +
> +		/* For any leftover entries. */
> +		if ((count + MERGE_BASES_BATCH_SIZE) > list.nr)
> +			batch_size = list.nr - count;
> +
> +		if ((ret = in_merge_bases_many(commit, batch_size, chunk)))
> +			break;
> +
> +		chunk += batch_size;
> +		count += MERGE_BASES_BATCH_SIZE;

... you are risking chunk and count to go out of sync here.

It does not matter within this loop (count will point beyond the end
of list.item[] while chunk will never go past the array), but future
developers can be confused into thinking that they can use chunk and
count interchangeably after this loop exits, and at that point the
discrepancy may start to matter.

But all of the above matters if it is a good idea to batch.  Does it
make a difference?

    ... goes and looks at in_merge_bases_many() ...

Ah, it probably would.  

I thought in_merge_bases_many() would stop early as soon as any of
the traversal from chunk[] reaches commit, but it uses a rather more
generic paint_down_to_common() so extra items in chunk[] that are
topologically older than commit would result in additional traversal
from commit down to them, which would not contribute much to the end
result.  It may be a good #leftovebit idea for future improvement to
teach in_merge_bases_many() to use a custom replacement for
paint_down_to_common() that stops early as soon as we find the
answer is true.

> +	}
> +
> +cleanup_return:
> +	free_reflog_commit_list(&list);
> +	return ret;
> +}
> +

Thanks.

  reply	other threads:[~2020-09-26 23:42 UTC|newest]

Thread overview: 120+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-09-04 18:51 [PATCH] push: make `--force-with-lease[=<ref>]` safer Srinidhi Kaushik
2020-09-07 15:23 ` Phillip Wood
2020-09-08 15:48   ` Srinidhi Kaushik
2020-09-07 16:14 ` Junio C Hamano
2020-09-08 16:00   ` Srinidhi Kaushik
2020-09-08 21:00     ` Junio C Hamano
2020-09-07 19:45 ` Johannes Schindelin
2020-09-08 15:58   ` Junio C Hamano
2020-09-09  3:40     ` Johannes Schindelin
2020-09-08 16:59   ` Srinidhi Kaushik
2020-09-16 11:55     ` Johannes Schindelin
2020-09-08 19:34   ` Junio C Hamano
2020-09-09  3:44     ` Johannes Schindelin
2020-09-10 10:22       ` Johannes Schindelin
2020-09-10 14:44         ` Srinidhi Kaushik
2020-09-11 22:16           ` Johannes Schindelin
2020-09-14 11:06             ` Srinidhi Kaushik
2020-09-14 20:08             ` Junio C Hamano
2020-09-16  5:31               ` Srinidhi Kaushik
2020-09-16 10:20                 ` Johannes Schindelin
2020-09-19 17:48                   ` Junio C Hamano
2020-09-10 14:46         ` Junio C Hamano
2020-09-11 22:17           ` Johannes Schindelin
2020-09-14 20:07             ` Junio C Hamano
2020-09-12 15:04 ` [PATCH v2 0/2] push: make "--force-with-lease" safer Srinidhi Kaushik
2020-09-12 15:04   ` [PATCH v2 1/2] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-12 18:20     ` Junio C Hamano
2020-09-12 21:25       ` Srinidhi Kaushik
2020-09-12 15:04   ` [PATCH v2 2/2] push: enable "forceIfIncludesWithLease" by default Srinidhi Kaushik
2020-09-12 18:22     ` Junio C Hamano
2020-09-12 18:15   ` [PATCH v2 0/2] push: make "--force-with-lease" safer Junio C Hamano
2020-09-12 21:03     ` Srinidhi Kaushik
2020-09-13 14:54   ` [PATCH v3 0/7] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 1/7] remote: add reflog check for "force-if-includes" Srinidhi Kaushik
2020-09-14 20:17       ` Junio C Hamano
2020-09-16 10:51         ` Srinidhi Kaushik
2020-09-14 20:31       ` Junio C Hamano
2020-09-14 21:13       ` Junio C Hamano
2020-09-16 12:35       ` Johannes Schindelin
2020-09-19 17:01         ` Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 2/7] transport: add flag for "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 3/7] send-pack: check ref status for "force-if-includes" Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 4/7] transport-helper: update " Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 5/7] builtin/push: add option "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-16 12:36       ` Johannes Schindelin
2020-09-13 14:54     ` [PATCH v3 6/7] doc: add reference for "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-14 21:01       ` Junio C Hamano
2020-09-16  5:35         ` Srinidhi Kaushik
2020-09-13 14:54     ` [PATCH v3 7/7] t: add tests for "force-if-includes" Srinidhi Kaushik
2020-09-16 12:47     ` [PATCH v3 0/7] push: add "--[no-]force-if-includes" Johannes Schindelin
2020-09-19 17:03   ` [PATCH v4 0/3] " Srinidhi Kaushik
2020-09-19 17:03     ` [PATCH v4 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-09-19 20:03       ` Junio C Hamano
2020-09-21  8:42         ` Srinidhi Kaushik
2020-09-21 18:48           ` Junio C Hamano
2020-09-23 10:22             ` Srinidhi Kaushik
2020-09-23 16:47               ` Junio C Hamano
2020-09-21 13:19         ` Phillip Wood
2020-09-21 16:12           ` Junio C Hamano
2020-09-21 18:11             ` Junio C Hamano
2020-09-23 10:27           ` Srinidhi Kaushik
2020-09-19 17:03     ` [PATCH v4 2/3] push: parse and set flag " Srinidhi Kaushik
2020-09-19 20:26       ` Junio C Hamano
2020-09-19 17:03     ` [PATCH v4 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-09-19 20:42       ` Junio C Hamano
2020-09-23  7:30     ` [PATCH v5 0/3] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-23  7:30       ` [PATCH v5 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-09-23 10:18         ` Phillip Wood
2020-09-23 11:26           ` Srinidhi Kaushik
2020-09-23 16:24           ` Junio C Hamano
2020-09-23 16:29         ` Junio C Hamano
2020-09-23  7:30       ` [PATCH v5 2/3] push: parse and set flag " Srinidhi Kaushik
2020-09-23  7:30       ` [PATCH v5 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-09-23 10:24         ` Phillip Wood
2020-09-26 10:13       ` [PATCH v6 0/3] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-26 10:13         ` [PATCH v6 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-09-26 10:13         ` [PATCH v6 2/3] push: parse and set flag " Srinidhi Kaushik
2020-09-26 10:13         ` [PATCH v6 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-09-26 10:21         ` [PATCH v6 0/3] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-26 11:46         ` [PATCH v7 " Srinidhi Kaushik
2020-09-26 11:46           ` [PATCH v7 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-09-26 23:42             ` Junio C Hamano [this message]
2020-09-27 12:27               ` Srinidhi Kaushik
2020-09-26 11:46           ` [PATCH v7 2/3] push: parse and set flag " Srinidhi Kaushik
2020-09-26 11:46           ` [PATCH v7 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-09-27 14:17           ` [PATCH v8 0/3] push: add "--[no-]force-if-includes" Srinidhi Kaushik
2020-09-27 14:17             ` [PATCH v8 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-09-27 14:17             ` [PATCH v8 2/3] push: parse and set flag " Srinidhi Kaushik
2020-09-27 14:17             ` [PATCH v8 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-09-30 12:54               ` Philip Oakley
2020-09-30 14:27                 ` Srinidhi Kaushik
2020-09-28 17:31             ` [PATCH v8 0/3] push: add "--[no-]force-if-includes" Junio C Hamano
2020-09-28 17:46               ` SZEDER Gábor
2020-09-28 19:34                 ` Srinidhi Kaushik
2020-09-28 19:51                   ` Junio C Hamano
2020-09-28 20:00                 ` Junio C Hamano
2020-10-01  8:21             ` [PATCH v9 " Srinidhi Kaushik
2020-10-01  8:21               ` [PATCH v9 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-10-02 13:52                 ` Johannes Schindelin
2020-10-02 14:50                   ` Johannes Schindelin
2020-10-02 16:22                     ` Junio C Hamano
2020-10-02 15:07                   ` Srinidhi Kaushik
2020-10-02 16:41                     ` Junio C Hamano
2020-10-02 19:39                       ` Srinidhi Kaushik
2020-10-02 20:14                         ` Junio C Hamano
2020-10-02 20:58                           ` Srinidhi Kaushik
2020-10-02 21:36                             ` Junio C Hamano
2020-10-02 16:26                   ` Junio C Hamano
2020-10-01  8:21               ` [PATCH v9 2/3] push: parse and set flag " Srinidhi Kaushik
2020-10-01  8:21               ` [PATCH v9 3/3] t, doc: update tests, reference " Srinidhi Kaushik
2020-10-01 15:46               ` [PATCH v9 0/3] push: add "--[no-]force-if-includes" Junio C Hamano
2020-10-01 17:12                 ` Junio C Hamano
2020-10-01 17:54                   ` Srinidhi Kaushik
2020-10-01 18:32                     ` Junio C Hamano
2020-10-02 16:50                     ` Junio C Hamano
2020-10-02 19:42                       ` Srinidhi Kaushik
2020-10-03 12:10               ` [PATCH v10 " Srinidhi Kaushik
2020-10-03 12:10                 ` [PATCH v10 1/3] push: add reflog check for "--force-if-includes" Srinidhi Kaushik
2020-10-03 12:10                 ` [PATCH v10 2/3] push: parse and set flag " Srinidhi Kaushik
2020-10-03 12:10                 ` [PATCH v10 3/3] t, doc: update tests, reference " Srinidhi Kaushik

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=xmqqwo0ggl65.fsf@gitster.c.googlers.com \
    --to=gitster@pobox.com \
    --cc=git@vger.kernel.org \
    --cc=shrinidhi.kaushik@gmail.com \
    --subject='Re: [PATCH v7 1/3] push: add reflog check for "--force-if-includes"' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).