From fc62e033cd93ff6b93e312d89bfb5683a4c6f90c Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:29 +0000 Subject: pack-objects: add --name-hash-version option The previous change introduced a new pack_name_hash_v2() function that intends to satisfy much of the hash locality features of the existing pack_name_hash() function while also distinguishing paths with similar final components of their paths. This change adds a new --name-hash-version option for 'git pack-objects' to allow users to select their preferred function version. This use of an integer version allows for future expansion and a direct way to later store a name hash version in the .bitmap format. For now, let's consider how effective this mechanism is when repacking a repository with different name hash versions. Specifically, we will execute 'git pack-objects' the same way a 'git repack -adf' process would, except we include --name-hash-version= for testing. On the Git repository, we do not expect much difference. All path names are short. This is backed by our results: | Stage | Pack Size | Repack Time | |-----------------------|-----------|-------------| | After clone | 260 MB | N/A | | --name-hash-version=1 | 127 MB | 129s | | --name-hash-version=2 | 127 MB | 112s | This example demonstrates how there is some natural overhead coming from the cloned copy because the server is hosting many forks and has not optimized for exactly this set of reachable objects. But the full repack has similar characteristics for both versions. Let's consider some repositories that are hitting too many collisions with version 1. First, let's explore the kinds of paths that are commonly causing these collisions: * "/CHANGELOG.json" is 15 characters, and is created by the beachball [1] tool. Only the final character of the parent directory can differentiate different versions of this file, but also only the two most-significant digits. If that character is a letter, then this is always a collision. Similar issues occur with the similar "/CHANGELOG.md" path, though there is more opportunity for differences In the parent directory. * Localization files frequently have common filenames but differentiates via parent directories. In C#, the name "/strings.resx.lcl" is used for these localization files and they will all collide in name-hash. [1] https://github.com/microsoft/beachball I've come across many other examples where some internal tool uses a common name across multiple directories and is causing Git to repack poorly due to name-hash collisions. One open-source example is the fluentui [2] repo, which uses beachball to generate CHANGELOG.json and CHANGELOG.md files, and these files have very poor delta characteristics when comparing against versions across parent directories. | Stage | Pack Size | Repack Time | |-----------------------|-----------|-------------| | After clone | 694 MB | N/A | | --name-hash-version=1 | 438 MB | 728s | | --name-hash-version=2 | 168 MB | 142s | [2] https://github.com/microsoft/fluentui In this example, we see significant gains in the compressed packfile size as well as the time taken to compute the packfile. Using a collection of repositories that use the beachball tool, I was able to make similar comparisions with dramatic results. While the fluentui repo is public, the others are private so cannot be shared for reproduction. The results are so significant that I find it important to share here: | Repo | --name-hash-version=1 | --name-hash-version=2 | |----------|-----------------------|-----------------------| | fluentui | 440 MB | 161 MB | | Repo B | 6,248 MB | 856 MB | | Repo C | 37,278 MB | 6,755 MB | | Repo D | 131,204 MB | 7,463 MB | Future changes could include making --name-hash-version implied by a config value or even implied by default during a full repack. It is important to point out that the name hash value is stored in the .bitmap file format, so we must force --name-hash-version=1 when bitmaps are being read or written. Later, the bitmap format could be updated to be aware of the name hash version so deltas can be quickly computed across the bitmapped/not-bitmapped boundary. To promote the safety of this parameter, the validate_name_hash_version() method will die() if the given name-hash version is incorrect and will disable newer versions if not yet compatible with other features, such as --write-bitmap-index. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- builtin/pack-objects.c | 52 +++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 47 insertions(+), 5 deletions(-) (limited to 'builtin/pack-objects.c') diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 0800714267..d0c717e9d0 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -266,6 +266,35 @@ struct configured_exclusion { static struct oidmap configured_exclusions; static struct oidset excluded_by_config; +static int name_hash_version = 1; + +/** + * Check whether the name_hash_version chosen by user input is appropriate, + * and also validate whether it is compatible with other features. + */ +static void validate_name_hash_version(void) +{ + if (name_hash_version < 1 || name_hash_version > 2) + die(_("invalid --name-hash-version option: %d"), name_hash_version); + if (write_bitmap_index && name_hash_version != 1) { + warning(_("currently, --write-bitmap-index requires --name-hash-version=1")); + name_hash_version = 1; + } +} + +static inline uint32_t pack_name_hash_fn(const char *name) +{ + switch (name_hash_version) { + case 1: + return pack_name_hash(name); + + case 2: + return pack_name_hash_v2((const unsigned char *)name); + + default: + BUG("invalid name-hash version: %d", name_hash_version); + } +} /* * stats @@ -1698,7 +1727,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type, return 0; } - create_object_entry(oid, type, pack_name_hash(name), + create_object_entry(oid, type, pack_name_hash_fn(name), exclude, name && no_try_delta(name), found_pack, found_offset); return 1; @@ -1912,7 +1941,7 @@ static void add_preferred_base_object(const char *name) { struct pbase_tree *it; size_t cmplen; - unsigned hash = pack_name_hash(name); + unsigned hash = pack_name_hash_fn(name); if (!num_preferred_base || check_pbase_path(hash)) return; @@ -3422,7 +3451,7 @@ static void show_object_pack_hint(struct object *object, const char *name, * here using a now in order to perhaps improve the delta selection * process. */ - oe->hash = pack_name_hash(name); + oe->hash = pack_name_hash_fn(name); oe->no_try_delta = name && no_try_delta(name); stdin_packs_hints_nr++; @@ -3572,7 +3601,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type entry = packlist_find(&to_pack, oid); if (entry) { if (name) { - entry->hash = pack_name_hash(name); + entry->hash = pack_name_hash_fn(name); entry->no_try_delta = no_try_delta(name); } } else { @@ -3595,7 +3624,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type return; } - entry = create_object_entry(oid, type, pack_name_hash(name), + entry = create_object_entry(oid, type, pack_name_hash_fn(name), 0, name && no_try_delta(name), pack, offset); } @@ -4069,6 +4098,15 @@ static int get_object_list_from_bitmap(struct rev_info *revs) if (!(bitmap_git = prepare_bitmap_walk(revs, 0))) return -1; + /* + * For now, force the name-hash version to be 1 since that + * is the version implied by the bitmap format. Later, the + * format can include this version explicitly in its format, + * allowing readers to know the version that was used during + * the bitmap write. + */ + name_hash_version = 1; + if (pack_options_allow_reuse()) reuse_partial_packfile_from_bitmap(bitmap_git, &reuse_packfiles, @@ -4429,6 +4467,8 @@ int cmd_pack_objects(int argc, OPT_STRING_LIST(0, "uri-protocol", &uri_protocols, N_("protocol"), N_("exclude any configured uploadpack.blobpackfileuri with this protocol")), + OPT_INTEGER(0, "name-hash-version", &name_hash_version, + N_("use the specified name-hash function to group similar objects")), OPT_END(), }; @@ -4576,6 +4616,8 @@ int cmd_pack_objects(int argc, if (pack_to_stdout || !rev_list_all) write_bitmap_index = 0; + validate_name_hash_version(); + if (use_delta_islands) strvec_push(&rp, "--topo-order"); -- cgit v1.3 From ce961135ccf5bc008b8160404cc7c995789b942e Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:31 +0000 Subject: pack-objects: add GIT_TEST_NAME_HASH_VERSION Add a new environment variable to opt-in to different values of the --name-hash-version= option in 'git pack-objects'. This allows for extra testing of the feature without repeating all of the test scenarios. Unlike many GIT_TEST_* variables, we are choosing to not add this to the linux-TEST-vars CI build as that test run is already overloaded. The behavior exposed by this test variable is of low risk and should be sufficient to allow manual testing when an issue arises. But this option isn't free. There are a few tests that change behavior with the variable enabled. First, there are a few tests that are very sensitive to certain delta bases being picked. These are both involving the generation of thin bundles and then counting their objects via 'git index-pack --fix-thin' which pulls the delta base into the new packfile. For these tests, disable the option as a decent long-term option. Second, there are some tests that compare the exact output of a 'git pack-objects' process when using bitmaps. The warning that ignores the --name-hash-version=2 and forces version 1 causes these tests to fail. Disable the environment variable to get around this issue. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- builtin/pack-objects.c | 5 ++++- t/README | 4 ++++ t/t5300-pack-object.sh | 7 +++++-- t/t5310-pack-bitmaps.sh | 5 ++++- t/t5333-pseudo-merge-bitmaps.sh | 3 ++- t/t5510-fetch.sh | 7 ++++++- t/t6020-bundle-misc.sh | 6 +++++- t/t7406-submodule-update.sh | 4 +++- t/t7700-repack.sh | 10 ++++++++-- 9 files changed, 41 insertions(+), 10 deletions(-) (limited to 'builtin/pack-objects.c') diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index d0c717e9d0..8ae77deb92 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -266,7 +266,7 @@ struct configured_exclusion { static struct oidmap configured_exclusions; static struct oidset excluded_by_config; -static int name_hash_version = 1; +static int name_hash_version = -1; /** * Check whether the name_hash_version chosen by user input is appropriate, @@ -4616,6 +4616,9 @@ int cmd_pack_objects(int argc, if (pack_to_stdout || !rev_list_all) write_bitmap_index = 0; + if (name_hash_version < 0) + name_hash_version = (int)git_env_ulong("GIT_TEST_NAME_HASH_VERSION", 1); + validate_name_hash_version(); if (use_delta_islands) diff --git a/t/README b/t/README index 8c0319b58e..e63d236085 100644 --- a/t/README +++ b/t/README @@ -492,6 +492,10 @@ a test and then fails then the whole test run will abort. This can help to make sure the expected tests are executed and not silently skipped when their dependency breaks or is simply not present in a new environment. +GIT_TEST_NAME_HASH_VERSION=, when set, causes 'git pack-objects' to +assume '--name-hash-version='. + + Naming Tests ------------ diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh index 4270eabe8b..97fe9e561c 100755 --- a/t/t5300-pack-object.sh +++ b/t/t5300-pack-object.sh @@ -675,15 +675,18 @@ do done test_expect_success 'valid and invalid --name-hash-versions' ' + sane_unset GIT_TEST_NAME_HASH_VERSION && + # Valid values are hard to verify other than "do not fail". # Performance tests will be more valuable to validate these versions. - for value in 1 2 + # Negative values are converted to version 1. + for value in -1 1 2 do git pack-objects base --all --name-hash-version=$value || return 1 done && # Invalid values have clear post-conditions. - for value in -1 0 3 + for value in 0 3 do test_must_fail git pack-objects base --all --name-hash-version=$value 2>err && test_grep "invalid --name-hash-version option" err || return 1 diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh index 7044c7d7c6..c30522b57f 100755 --- a/t/t5310-pack-bitmaps.sh +++ b/t/t5310-pack-bitmaps.sh @@ -420,7 +420,10 @@ test_bitmap_cases () { cat >expect <<-\EOF && error: missing value for '\''pack.preferbitmaptips'\'' EOF - git repack -adb 2>actual && + + # Disable name hash version adjustment due to stderr comparison. + GIT_TEST_NAME_HASH_VERSION=1 \ + git repack -adb 2>actual && test_cmp expect actual ) ' diff --git a/t/t5333-pseudo-merge-bitmaps.sh b/t/t5333-pseudo-merge-bitmaps.sh index eca4a1eb8c..971f9d2d4e 100755 --- a/t/t5333-pseudo-merge-bitmaps.sh +++ b/t/t5333-pseudo-merge-bitmaps.sh @@ -209,7 +209,8 @@ test_expect_success 'bitmapPseudoMerge.stableThreshold creates stable groups' ' ' test_expect_success 'out of order thresholds are rejected' ' - test_must_fail git \ + # Disable the test var to remove a stderr message. + test_must_fail env GIT_TEST_NAME_HASH_VERSION=1 git \ -c bitmapPseudoMerge.test.pattern="refs/*" \ -c bitmapPseudoMerge.test.threshold=1.month.ago \ -c bitmapPseudoMerge.test.stableThreshold=1.week.ago \ diff --git a/t/t5510-fetch.sh b/t/t5510-fetch.sh index 0890b9f61c..1699c3a3bb 100755 --- a/t/t5510-fetch.sh +++ b/t/t5510-fetch.sh @@ -1062,7 +1062,12 @@ test_expect_success 'all boundary commits are excluded' ' test_tick && git merge otherside && ad=$(git log --no-walk --format=%ad HEAD) && - git bundle create twoside-boundary.bdl main --since="$ad" && + + # If the a different name hash function is used here, then no delta + # pair is found and the bundle does not expand to three objects + # when fixing the thin object. + GIT_TEST_NAME_HASH_VERSION=1 \ + git bundle create twoside-boundary.bdl main --since="$ad" && test_bundle_object_count --thin twoside-boundary.bdl 3 ' diff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh index 34b5cd62c2..a1f18ae71f 100755 --- a/t/t6020-bundle-misc.sh +++ b/t/t6020-bundle-misc.sh @@ -247,7 +247,11 @@ test_expect_success 'create bundle with --since option' ' EOF test_cmp expect actual && - git bundle create since.bdl \ + # If a different name hash function is used, then one fewer + # delta base is found and this counts a different number + # of objects after performing --fix-thin. + GIT_TEST_NAME_HASH_VERSION=1 \ + git bundle create since.bdl \ --since "Thu Apr 7 15:27:00 2005 -0700" \ --all && diff --git a/t/t7406-submodule-update.sh b/t/t7406-submodule-update.sh index 0f0c86f9cb..ebd9941075 100755 --- a/t/t7406-submodule-update.sh +++ b/t/t7406-submodule-update.sh @@ -1094,7 +1094,9 @@ test_expect_success 'submodule update --quiet passes quietness to fetch with a s ) && git clone super4 super5 && (cd super5 && - git submodule update --quiet --init --depth=1 submodule3 >out 2>err && + # This test var can mess with the stderr output checked in this test. + GIT_TEST_NAME_HASH_VERSION=1 \ + git submodule update --quiet --init --depth=1 submodule3 >out 2>err && test_must_be_empty out && test_must_be_empty err ) && diff --git a/t/t7700-repack.sh b/t/t7700-repack.sh index b9a5759e01..16861f80c9 100755 --- a/t/t7700-repack.sh +++ b/t/t7700-repack.sh @@ -309,7 +309,10 @@ test_expect_success 'no bitmaps created if .keep files present' ' keep=${pack%.pack}.keep && test_when_finished "rm -f \"\$keep\"" && >"$keep" && - git -C bare.git repack -ad 2>stderr && + + # Disable --name-hash-version test due to stderr comparison. + GIT_TEST_NAME_HASH_VERSION=1 \ + git -C bare.git repack -ad 2>stderr && test_must_be_empty stderr && find bare.git/objects/pack/ -type f -name "*.bitmap" >actual && test_must_be_empty actual @@ -320,7 +323,10 @@ test_expect_success 'auto-bitmaps do not complain if unavailable' ' blob=$(test-tool genrandom big $((1024*1024)) | git -C bare.git hash-object -w --stdin) && git -C bare.git update-ref refs/tags/big $blob && - git -C bare.git repack -ad 2>stderr && + + # Disable --name-hash-version test due to stderr comparison. + GIT_TEST_NAME_HASH_VERSION=1 \ + git -C bare.git repack -ad 2>stderr && test_must_be_empty stderr && find bare.git/objects/pack -type f -name "*.bitmap" >actual && test_must_be_empty actual -- cgit v1.3 From b4cf68476a983ff063846b43cd46ee9805f2c0bb Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Mon, 27 Jan 2025 19:02:34 +0000 Subject: pack-objects: prevent name hash version change When the --name-hash-version option is used in 'git pack-objects', it can change from the initial assignment to when it is used based on interactions with other arguments. Specifically, when writing or reading bitmaps, we must force version 1 for now. This could change in the future when the bitmap format can store a name hash version value, indicating which was used during the writing of the packfile. Protect the 'git pack-objects' process from getting confused by failing with a BUG() statement if the value of the name hash version changes between calls to pack_name_hash_fn(). Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- builtin/pack-objects.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'builtin/pack-objects.c') diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 8ae77deb92..fa09a35cf5 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -284,6 +284,14 @@ static void validate_name_hash_version(void) static inline uint32_t pack_name_hash_fn(const char *name) { + static int seen_version = -1; + + if (seen_version < 0) + seen_version = name_hash_version; + else if (seen_version != name_hash_version) + BUG("name hash version changed from %d to %d mid-process", + seen_version, name_hash_version); + switch (name_hash_version) { case 1: return pack_name_hash(name); -- cgit v1.3