git/bundle-uri.c, branch v2.40.2

Merge branch 'ds/bundle-uri-5'

2023-02-16T01:11:52Z

The bundle-URI subsystem adds support for creation-token heuristics to help incremental fetches. * ds/bundle-uri-5: bundle-uri: test missing bundles with heuristic bundle-uri: store fetch.bundleCreationToken fetch: fetch from an external bundle URI bundle-uri: drop bundle.flag from design doc clone: set fetch.bundleURI if appropriate bundle-uri: download in creationToken order bundle-uri: parse bundle..creationToken values bundle-uri: parse bundle.heuristic=creationToken t5558: add tests for creationToken heuristic bundle: verify using check_connected() bundle: test unbundling with incomplete history

bundle-uri: store fetch.bundleCreationToken

2023-01-31T16:57:48Z

When a bundle list specifies the "creationToken" heuristic, the Git client downloads the list and then starts downloading bundles in descending creationToken order. This process stops as soon as all downloaded bundles can be applied to the repository (because all required commits are present in the repository or in the downloaded bundles). When checking the same bundle list twice, this strategy requires downloading the bundle with the maximum creationToken again, which is wasteful. The creationToken heuristic promises that the client will not have a use for that bundle if its creationToken value is at most the previous creationToken value. To prevent these wasteful downloads, create a fetch.bundleCreationToken config setting that the Git client sets after downloading bundles. This value allows skipping that maximum bundle download when this config value is the same value (or larger). To test that this works correctly, we can insert some "duplicate" fetches into existing tests and demonstrate that only the bundle list is downloaded. The previous logic for downloading bundles by creationToken worked even if the bundle list was empty, but now we have logic that depends on the first entry of the list. Terminate early in the (non-sensical) case of an empty bundle list. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

clone: set fetch.bundleURI if appropriate

2023-01-31T16:57:48Z

Bundle providers may organize their bundle lists in a way that is intended to improve incremental fetches, not just initial clones. However, they do need to state that they have organized with that in mind, or else the client will not expect to save time by downloading bundles after the initial clone. This is done by specifying a bundle.heuristic value. There are two types of bundle lists: those at a static URI and those that are advertised from a Git remote over protocol v2. The new fetch.bundleURI config value applies for static bundle URIs that are not advertised over protocol v2. If the user specifies a static URI via 'git clone --bundle-uri', then Git can set this config as a reminder for future 'git fetch' operations to check the bundle list before connecting to the remote(s). For lists provided over protocol v2, we will want to take a different approach and create a property of the remote itself by creating a remote..* type config key. That is not implemented in this change. Later changes will update 'git fetch' to consume this option. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

bundle-uri: download in creationToken order

2023-01-31T16:57:48Z

The creationToken heuristic provides an ordering on the bundles advertised by a bundle list. Teach the Git client to download bundles differently when this heuristic is advertised. The bundles in the list are sorted by their advertised creationToken values, then downloaded in decreasing order. This avoids the previous strategy of downloading bundles in an arbitrary order and attempting to apply them (likely failing in the case of required commits) until discovering the order through attempted unbundling. During a fresh 'git clone', it may make sense to download the bundles in increasing order, since that would prevent the need to attempt unbundling a bundle with required commits that do not exist in our empty object store. The cost of testing an unbundle is quite low, and instead the chosen order is optimizing for a future bundle download during a 'git fetch' operation with a non-empty object store. Since the Git client continues fetching from the Git remote after downloading and unbundling bundles, the client's object store can be ahead of the bundle provider's object store. The next time it attempts to download from the bundle list, it makes most sense to download only the most-recent bundles until all tips successfully unbundle. The strategy implemented here provides that short-circuit where the client downloads a minimal set of bundles. However, we are not satisfied by the naive approach of downloading bundles until one successfully unbundles, expecting the earlier bundles to successfully unbundle now. The example repository in t5558 demonstrates this well: ---------------- bundle-4 4 / \ ----|---|------- bundle-3 | | | 3 | | ----|---|------- bundle-2 | | 2 | | | ----|---|------- bundle-1 \ / 1 | (previous commits) In this repository, if we already have the objects for bundle-1 and then try to fetch from this list, the naive approach will fail. bundle-4 requires both bundle-3 and bundle-2, though bundle-3 will successfully unbundle without bundle-2. Thus, the algorithm needs to keep this in mind. A later implementation detail will store the maximum creationToken seen during such a bundle download, and the client will avoid downloading a bundle unless its creationToken is strictly greater than that stored value. For now, if the client seeks to download from an identical bundle list since its previous download, it will download the most-recent bundle then stop since its required commits are already in the object store. Add tests that exercise this behavior, but we will expand upon these tests when incremental downloads during 'git fetch' make use of creationToken values. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

bundle-uri: parse bundle..creationToken values

2023-01-31T16:57:48Z

The previous change taught Git to parse the bundle.heuristic value, especially when its value is "creationToken". Now, teach Git to parse the bundle..creationToken values on each bundle in a bundle list. Before implementing any logic based on creationToken values for the creationToken heuristic, parse and print these values for testing purposes. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

bundle-uri: parse bundle.heuristic=creationToken

2023-01-31T16:57:48Z

The bundle.heuristic value communicates that the bundle list is organized to make use of the bundle..creationToken values that may be provided in the bundle list. Those values will create a total order on the bundles, allowing the Git client to download them in a specific order and even remember previously-downloaded bundles by storing the maximum creation token value. Before implementing any logic that parses or uses the bundle..creationToken values, teach Git to parse the bundle.heuristic value from a bundle list. We can use 'test-tool bundle-uri' to print the heuristic value and verify that the parsing works correctly. As an extra precaution, create the internal 'heuristics' array to be a list of (enum, string) pairs so we can iterate through the array entries carefully, regardless of the enum values. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

convert trivial uses of strncmp() to starts_with()

2023-01-08T01:34:35Z

It's more readable to use starts_with() instead of strncmp() to match a prefix, as the latter requires a manually-computed length, and has the funny "matching is zero" return value common to cmp functions. This patch converts several cases which were found with: git grep 'strncmp(.*, [0-9]*)' But note that it doesn't convert all such cases. There are several where the magic length number is repeated elsewhere in the code, like: /* handle "buf" which isn't NUL-terminated and might be too small */ if (len >= 3 && !strncmp(buf, "foo", 3)) or: /* exact match for "foo", but within a larger string */ if (end - buf == 3 && !strncmp(buf, "foo", 3)) While it would not produce the wrong outcome to use starts_with() in these cases, we'd still be left with one instance of "3". We're better to leave them for now, as the repeated "3" makes it clear that the two are linked (there may be other refactorings that handle both, but they're out of scope for this patch). A few things to note while reading the patch: - all cases but one are trying to match, and so lose the extra "!". The case in the first hunk of urlmatch.c is not-matching, and hence gains a "!". - the case in remote-fd.c is matching the beginning of "connect foo", but we never look at str+8 to parse the "foo" part (which would make this a candidate for skip_prefix(), not starts_with()). This seems at first glance like a bug, but is a limitation of how remote-fd works. - the second hunk in urlmatch.c shows some cases adjacent to other strncmp() calls that are left. These are of the "exact match within a larger string" type, as described above. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

bundle-uri: download bundles from an advertised list

2022-12-25T07:24:24Z

The logic in fetch_bundle_uri() is useful for the --bundle-uri option of 'git clone', but is not helpful when the clone operation discovers a list of URIs from the bundle-uri protocol v2 command. To actually download and unbundle the advertised bundles, we need a different mechanism. Create the new fetch_bundle_list() method which is very similar to fetch_bundle_uri() except that it relies on download_bundle_list() instead of fetch_bundle_uri_internal(). The download_bundle_list() method will recursively call fetch_bundle_uri_internal() if any of the advertised URIs serve a bundle list instead of a bundle. This will also follow the bundle.list.mode setting from the input list: "any" will download only one such URI while "all" will download data from all of the URIs. In an identical way to fetch_bundle_uri(), the bundles are unbundled after all of the bundle lists have been expanded and all necessary URIs. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

bundle-uri: allow relative URLs in bundle lists

2022-12-25T07:24:24Z

Bundle providers may want to distribute that data across multiple CDNs. This might require a change in the base URI, all the way to the domain name. If all bundles require an absolute URI in their 'uri' value, then every push to a CDN would require altering the table of contents to match the expected domain and exact location within it. Allow a bundle list to specify a relative URI for the bundles. This URI is based on where the client received the bundle list. For a list provided in the 'bundle-uri' protocol v2 command, the Git remote URI is the base URI. Otherwise, the bundle list was provided from an HTTP URI not using the Git protocol, and that URI is the base URI. This allows easier distribution of bundle data. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

bundle-uri: serve bundle.* keys from config

2022-12-25T07:24:24Z

Implement the "bundle-uri" protocol v2 capability by populating the key=value packet lines from the local Git config. The list of bundles is provided from the keys beginning with "bundle.". In the future, we may want to filter this list to be more specific to the exact known keys that the server intends to share, but for flexibility at the moment we will assume that the config values are well-formed. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano