git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 4/8] bundle-uri: download in creationToken order

From
Victoria Dye <vdye@github.com>
Date
Jan 19, 2023, 18:32 UTC
Message-ID
<ede340d1-bce4-0c1d-7afb-4874a67d1803@github.com>
In-Reply-To
<57c0174d3752fb61a05e0653de9d3057616ed16a.1673037405.git.gitgitgadget@gmail.com>
Derrick Stolee via GitGitGadget wrote:
Show 19 quoted lines
> +static int fetch_bundles_by_token(struct repository *r,
> +				  struct bundle_list *list)
> +{
> +	int cur;
> +	int pop_or_push = 0;
> +	struct bundle_list_context ctx = {
> +		.r = r,
> +		.list = list,
> +		.mode = list->mode,
> +	};
> +	struct sorted_bundle_list sorted = {
> +		.alloc = hashmap_get_size(&list->bundles),
> +	};
> +
> +	ALLOC_ARRAY(sorted.items, sorted.alloc);
> +
> +	for_all_bundles_in_list(list, insert_bundle, &sorted);
> +
> +	QSORT(sorted.items, sorted.nr, compare_creation_token);

So, at this point, 'sorted' is ordered by *decreasing* creation token? With the loop below being somewhat complex, it would be nice to have a comment mention that explicitly so readers have a clear understanding of the "initial state" before entering the loop.

Show 28 quoted lines
> +
> +	/*
> +	 * Use a stack-based approach to download the bundles and attempt
> +	 * to unbundle them in decreasing order by creation token. If we
> +	 * fail to unbundle (after a successful download) then move to the
> +	 * next non-downloaded bundle (push to the stack) and attempt
> +	 * downloading. Once we succeed in applying a bundle, move to the
> +	 * previous unapplied bundle (pop the stack) and attempt to unbundle
> +	 * it again.
> +	 *
> +	 * In the case of a fresh clone, we will likely download all of the
> +	 * bundles before successfully unbundling the oldest one, then the
> +	 * rest of the bundles unbundle successfully in increasing order
> +	 * of creationToken.
> +	 *
> +	 * If there are existing objects, then this process may terminate
> +	 * early when all required commits from "new" bundles exist in the
> +	 * repo's object store.
> +	 */
> +	cur = 0;
> +	while (cur >= 0 && cur < sorted.nr) {
> +		struct remote_bundle_info *bundle = sorted.items[cur];
> +		if (!bundle->file) {
> +			/* Not downloaded yet. Try downloading. */
> +			if (download_bundle_to_file(bundle, &ctx)) {
> +				/* Failure. Push to the stack. */
> +				pop_or_push = 1;
> +				goto stack_operation;

Personally, I find the use of "stack" terminology more confusing than not. 'sorted' isn't really a stack, it's a list with fixed contents being traversed stepwise with 'cur'. For example, 'pop_or_push' being renamed to 'move_direction' or 'step' something along those lines might more clearly indicate what's actually happening with 'cur' & 'sorted'.

Show 34 quoted lines
> +			}
> +
> +			/* We expect bundles when using creationTokens. */
> +			if (!is_bundle(bundle->file, 1)) {
> +				warning(_("file downloaded from '%s' is not a bundle"),
> +					bundle->uri);
> +				break;
> +			}
> +		}
> +
> +		if (bundle->file && !bundle->unbundled) {
> +			/*
> +			 * This was downloaded, but not successfully
> +			 * unbundled. Try unbundling again.
> +			 */
> +			if (unbundle_from_file(ctx.r, bundle->file)) {
> +				/* Failed to unbundle. Push to stack. */
> +				pop_or_push = 1;
> +			} else {
> +				/* Succeeded in unbundle. Pop stack. */
> +				pop_or_push = -1;
> +			}
> +		}
> +
> +		/*
> +		 * Else case: downloaded and unbundled successfully.
> +		 * Skip this by moving in the same direction as the
> +		 * previous step.
> +		 */
> +
> +stack_operation:
> +		/* Move in the specified direction and repeat. */
> +		cur += pop_or_push;
> +	}

After reading through this loop, I generally understood *what* its doing, but didn't really follow *why* the download & unbundling is done like this. I needed to refer back to the design doc ('Documentation/technical/bundle-uri.txt') to understand some basic assumptions about bundles:

- A new bundle's creation token should always be strictly greater than the
  previous newest bundle's creation token. I don't see any special handling
  for equal creation tokens, so my assumption is that the sorting of the
  list arbitrarily assigns one to be "greater" and it's dealt with that way.
- The bundle with the lowest creation token should always be unbundleable,
  since it contains all objects in an initial clone.
I do still have some questions, though:
- Why would 'unbundle_from_file()' fail? From context clues, I'm guessing it
  fails if it has some unreachable objects (as in an incremental bundle), or
  if it's corrupted somehow.
- Why would 'download_bundle_to_file()' to fail? Unlike
  'unbundle_from_file()', it looks like that represents an unexpected error.

Also - it seems like one of the assumptions here is that, if a bundle can't be downloaded & unbundled, no bundle with a higher creation token can be successfully unbundled ('download_bundle_to_file()' sets 'pop_or_push' to '1', which will cause the loop to ignore all higher-token bundles and return a nonzero value from the function).

I don't think that assumption is necessarily true, though. Suppose you have a "base" bundle 100 and incremental bundles 101 and 102. 101 has all objects from a new branch A, and 102 has all objects from a newer branch B (not based on any objects in A). In this case, 102 could be unbundled even if 101 is corrupted/can't be downloaded, but we'd run into issues if we store 102 as the "latest unbundled creation token" (because it implies that 101 was unbundled).

Is there any benefit to trying to unbundle those higher bundles *without* advancing the "latest creation token"? E.g. in my example, unbundle 102 but store '100' as the latest creation token?

Show 31 quoted lines
> diff --git a/t/t5558-clone-bundle-uri.sh b/t/t5558-clone-bundle-uri.sh
> index 328caeeae9a..d7461ec907e 100755
> --- a/t/t5558-clone-bundle-uri.sh
> +++ b/t/t5558-clone-bundle-uri.sh
> @@ -368,6 +368,8 @@ test_expect_success 'clone bundle list (HTTP, any mode)' '
>  '
>  
>  test_expect_success 'clone bundle list (http, creationToken)' '
> +	test_when_finished rm -f trace*.txt &&
> +
>  	cp clone-from/bundle-*.bundle "$HTTPD_DOCUMENT_ROOT_PATH/" &&
>  	cat >"$HTTPD_DOCUMENT_ROOT_PATH/bundle-list" <<-EOF &&
>  	[bundle]
> @@ -392,10 +394,45 @@ test_expect_success 'clone bundle list (http, creationToken)' '
>  		creationToken = 4
>  	EOF
>  
> -	git clone --bundle-uri="$HTTPD_URL/bundle-list" . clone-list-http-2 &&
> +	GIT_TRACE2_EVENT=$(pwd)/trace-clone.txt \
> +	git clone --bundle-uri="$HTTPD_URL/bundle-list" \
> +		clone-from clone-list-http-2 &&
>  
>  	git -C clone-from for-each-ref --format="%(objectname)" >oids &&
> -	git -C clone-list-http-2 cat-file --batch-check <oids
> +	git -C clone-list-http-2 cat-file --batch-check <oids &&
> +
> +	for b in 1 2 3 4
> +	do
> +		test_bundle_downloaded bundle-$b.bundle trace-clone.txt ||
> +			return 1
> +	done

If I understand correctly, these added conditions would have passed even if they were added when the test was initially created in patch 1, but they're added here to tie them to the implementation of the creationToken heuristic? Seems reasonable.

> +'
> +
> +test_expect_success 'clone bundle list (http, creationToken)' '

This new test has the same name as the one above it - how does it differ from that one? Whatever the difference is, can that be noted somehow in the title or a comment?

Show 42 quoted lines
> +	test_when_finished rm -f trace*.txt &&
> +
> +	cp clone-from/bundle-*.bundle "$HTTPD_DOCUMENT_ROOT_PATH/" &&
> +	cat >"$HTTPD_DOCUMENT_ROOT_PATH/bundle-list" <<-EOF &&
> +	[bundle]
> +		version = 1
> +		mode = all
> +		heuristic = creationToken
> +
> +	[bundle "bundle-1"]
> +		uri = bundle-1.bundle
> +		creationToken = 1
> +
> +	[bundle "bundle-2"]
> +		uri = bundle-2.bundle
> +		creationToken = 2
> +	EOF
> +
> +	GIT_TRACE2_EVENT=$(pwd)/trace-clone.txt \
> +	git clone --bundle-uri="$HTTPD_URL/bundle-list" \
> +		clone-from clone-token-http &&
> +
> +	test_bundle_downloaded bundle-1.bundle trace-clone.txt &&
> +	test_bundle_downloaded bundle-2.bundle trace-clone.txt
>  '
>  
>  # Do not add tests here unless they use the HTTP server, as they will
> diff --git a/t/t5601-clone.sh b/t/t5601-clone.sh
> index 1928ea1dd7c..57476b6e6d7 100755
> --- a/t/t5601-clone.sh
> +++ b/t/t5601-clone.sh
> @@ -831,6 +831,56 @@ test_expect_success 'auto-discover multiple bundles from HTTP clone' '
>  	grep -f pattern trace.txt
>  '
>  
> +# Usage: test_bundle_downloaded <bundle-id> <trace-filename>
> +test_bundle_downloaded () {
> +	cat >pattern <<-EOF &&
> +	"event":"child_start".*"argv":\["git-remote-https","$HTTPD_URL/$1.bundle"\]
> +	EOF
> +	grep -f pattern "$2"
> +}

This function is the same as the one created in 't5558'. Should it be moved to 'lib-bundle.sh' or 'test-lib.sh' to avoid duplicate code?

Show 46 quoted lines
> +
> +test_expect_success 'auto-discover multiple bundles from HTTP clone: creationToken heuristic' '
> +	test_when_finished rm -rf "$HTTPD_DOCUMENT_ROOT_PATH/repo4.git" &&
> +	test_when_finished rm -rf clone-heuristic trace*.txt &&
> +
> +	test_commit -C src newest &&
> +	git -C src bundle create "$HTTPD_DOCUMENT_ROOT_PATH/newest.bundle" HEAD~1..HEAD &&
> +	git clone --bare --no-local src "$HTTPD_DOCUMENT_ROOT_PATH/repo4.git" &&
> +
> +	cat >>"$HTTPD_DOCUMENT_ROOT_PATH/repo4.git/config" <<-EOF &&
> +	[uploadPack]
> +		advertiseBundleURIs = true
> +
> +	[bundle]
> +		version = 1
> +		mode = all
> +		heuristic = creationToken
> +
> +	[bundle "everything"]
> +		uri = $HTTPD_URL/everything.bundle
> +		creationtoken = 1
> +
> +	[bundle "new"]
> +		uri = $HTTPD_URL/new.bundle
> +		creationtoken = 2
> +
> +	[bundle "newest"]
> +		uri = $HTTPD_URL/newest.bundle
> +		creationtoken = 3
> +	EOF
> +
> +	GIT_TRACE2_EVENT="$(pwd)/trace-clone.txt" \
> +		git -c protocol.version=2 \
> +		    -c transfer.bundleURI=true clone \
> +		"$HTTPD_URL/smart/repo4.git" clone-heuristic &&
> +
> +	# We should fetch all bundles
> +	for b in everything new newest
> +	do
> +		test_bundle_downloaded $b trace-clone.txt || return 1
> +	done
> +'
> +
>  # DO NOT add non-httpd-specific tests here, because the last part of this
>  # test script is only executed when httpd is available and enabled.
>
Previous: Derrick StoleeNext: Derrick Stolee
Message 20 of 79 in “Bundle URIs V: creationToken heuristic for incremental fetches”
  1. 0/8 Bundle URIs V: creationToken heuristic for incremental fetchesDerrick Stolee via GitGitGadget, Jan 6, 2023
  2. 2/8 bundle-uri: parse bundle.heuristic=creationTokenDerrick Stolee via GitGitGadget, Jan 6, 2023
  3. Junio C HamanoJan 9, 2023
  4. Derrick StoleeJan 9, 2023
  5. Victoria DyeJan 17, 2023
  6. 1/8 t5558: add tests for creationToken heuristicDerrick Stolee via GitGitGadget, Jan 6, 2023
  7. Victoria DyeJan 17, 2023
  8. Derrick StoleeJan 17, 2023
  9. 6/8 bundle-uri: drop bundle.flag from design docDerrick Stolee via GitGitGadget, Jan 6, 2023
  10. Victoria DyeJan 19, 2023
  11. 5/8 clone: set fetch.bundleURI if appropriateDerrick Stolee via GitGitGadget, Jan 6, 2023
  12. Victoria DyeJan 19, 2023
  13. Derrick StoleeJan 20, 2023
  14. 7/8 fetch: fetch from an external bundle URIDerrick Stolee via GitGitGadget, Jan 6, 2023
  15. Victoria DyeJan 19, 2023
  16. Derrick StoleeJan 20, 2023
  17. 4/8 bundle-uri: download in creationToken orderDerrick Stolee via GitGitGadget, Jan 6, 2023
  18. Junio C HamanoJan 9, 2023
  19. Derrick StoleeJan 9, 2023
  20. Victoria DyeJan 19, 2023
  21. Derrick StoleeJan 20, 2023
  22. 8/8 bundle-uri: store fetch.bundleCreationTokenDerrick Stolee via GitGitGadget, Jan 6, 2023
  23. Victoria DyeJan 19, 2023
  24. Derrick StoleeJan 20, 2023
  25. 3/8 bundle-uri: parse bundle.<id>.creationToken valuesDerrick Stolee via GitGitGadget, Jan 6, 2023
  26. Junio C HamanoJan 9, 2023
  27. Derrick StoleeJan 9, 2023
  28. Victoria DyeJan 17, 2023
  29. 00/10 Bundle URIs V: creationToken heuristic for incremental fetchesDerrick Stolee via GitGitGadget, Jan 23, 2023
  30. 01/10 bundle: optionally skip reachability walkDerrick Stolee via GitGitGadget, Jan 23, 2023
  31. Junio C HamanoJan 23, 2023
  32. Derrick StoleeJan 23, 2023
  33. Junio C HamanoJan 23, 2023
  34. Junio C HamanoJan 23, 2023
  35. Derrick StoleeJan 24, 2023
  36. 01/11 bundle: test unbundling with incomplete historyDerrick Stolee, Jan 24, 2023
  37. Junio C HamanoJan 24, 2023
  38. 02/11 bundle: verify using connected()Derrick Stolee, Jan 24, 2023
  39. Junio C HamanoJan 24, 2023
  40. Derrick StoleeJan 24, 2023
  41. Junio C HamanoJan 24, 2023
  42. Junio C HamanoJan 24, 2023
  43. Junio C HamanoJan 23, 2023
  44. 02/10 t5558: add tests for creationToken heuristicDerrick Stolee via GitGitGadget, Jan 23, 2023
  45. Victoria DyeJan 27, 2023
  46. 04/10 bundle-uri: parse bundle.<id>.creationToken valuesDerrick Stolee via GitGitGadget, Jan 23, 2023
  47. 03/10 bundle-uri: parse bundle.heuristic=creationTokenDerrick Stolee via GitGitGadget, Jan 23, 2023
  48. 05/10 bundle-uri: download in creationToken orderDerrick Stolee via GitGitGadget, Jan 23, 2023
  49. Victoria DyeJan 27, 2023
  50. Junio C HamanoJan 27, 2023
  51. Derrick StoleeJan 30, 2023
  52. Junio C HamanoJan 30, 2023
  53. Derrick StoleeJan 30, 2023
  54. 06/10 clone: set fetch.bundleURI if appropriateDerrick Stolee via GitGitGadget, Jan 23, 2023
  55. 07/10 bundle-uri: drop bundle.flag from design docDerrick Stolee via GitGitGadget, Jan 23, 2023
  56. 09/10 bundle-uri: store fetch.bundleCreationTokenDerrick Stolee via GitGitGadget, Jan 23, 2023
  57. 10/10 bundle-uri: test missing bundles with heuristicDerrick Stolee via GitGitGadget, Jan 23, 2023
  58. Victoria DyeJan 27, 2023
  59. Derrick StoleeJan 30, 2023
  60. 08/10 fetch: fetch from an external bundle URIDerrick Stolee via GitGitGadget, Jan 23, 2023
  61. Victoria DyeJan 27, 2023
  62. Victoria DyeJan 27, 2023
  63. 00/11 Bundle URIs V: creationToken heuristic for incremental fetchesDerrick Stolee via GitGitGadget, Jan 31, 2023
  64. 01/11 bundle: test unbundling with incomplete historyDerrick Stolee via GitGitGadget, Jan 31, 2023
  65. 02/11 bundle: verify using check_connected()Derrick Stolee via GitGitGadget, Jan 31, 2023
  66. Junio C HamanoJan 31, 2023
  67. Derrick StoleeJan 31, 2023
  68. Junio C HamanoJan 31, 2023
  69. 03/11 t5558: add tests for creationToken heuristicDerrick Stolee via GitGitGadget, Jan 31, 2023
  70. 04/11 bundle-uri: parse bundle.heuristic=creationTokenDerrick Stolee via GitGitGadget, Jan 31, 2023
  71. 05/11 bundle-uri: parse bundle.<id>.creationToken valuesDerrick Stolee via GitGitGadget, Jan 31, 2023
  72. Junio C HamanoJan 31, 2023
  73. 07/11 clone: set fetch.bundleURI if appropriateDerrick Stolee via GitGitGadget, Jan 31, 2023
  74. 06/11 bundle-uri: download in creationToken orderDerrick Stolee via GitGitGadget, Jan 31, 2023
  75. 08/11 bundle-uri: drop bundle.flag from design docDerrick Stolee via GitGitGadget, Jan 31, 2023
  76. 09/11 fetch: fetch from an external bundle URIDerrick Stolee via GitGitGadget, Jan 31, 2023
  77. 11/11 bundle-uri: test missing bundles with heuristicDerrick Stolee via GitGitGadget, Jan 31, 2023
  78. 10/11 bundle-uri: store fetch.bundleCreationTokenDerrick Stolee via GitGitGadget, Jan 31, 2023
  79. Junio C HamanoJan 31, 2023

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.