git/tree-diff.c, branch v2.42.2

Merge branch 'jc/tree-walk-drop-base-offset'

2023-08-02T16:37:23Z

Code simplification. * jc/tree-walk-drop-base-offset: tree-walk: drop unused base_offset from do_match() tree-walk: lose base_offset that is never used in tree_entry_interesting

tree-walk: lose base_offset that is never used in tree_entry_interesting

2023-07-07T22:27:28Z

The tree_entry_interesting() function takes base_offset, allowing its callers to potentially pass a non-zero number to skip the early part of the path string. The feature is never exercised and we do not even know what bugs are lurking there, as all callers pass 0 to the parameter. Signed-off-by: Junio C Hamano

diff.h: remove unnecessary include of oidset.h

2023-06-21T20:39:53Z

This also made it clear that several .c files depended upon various things that oidset included, but had omitted the direct #include for those headers. Add those now. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

diff.h: reduce unnecessary includes

2023-04-24T19:47:33Z

Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

treewide: remove cache.h inclusion due to previous changes

2023-04-24T19:47:33Z

Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

tree-diff.c: move S_DIFFTREE_IFXMIN_NEQ define from cache.h

2023-04-24T19:47:32Z

S_DIFFTREE_IFXMIN_NEQ is *only* used in tree-diff.c, so there is no point exposing it in cache.h. Move it to tree-diff.c. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

pathspec: use BUG(...) not die("BUG:%s:%d....", , )

2021-12-07T20:31:17Z

Change code that was added in 8f4f8f4579f (guard against new pathspec magic in pathspec matching code, 2013-07-14) to use the BUG() macro instead of emitting a "fatal" message with the "__FILE__"-name and "__LINE__"-numbers. The original code predated the existence of the BUG() function, which was added in d8193743e08 (usage.c: add BUG() function, 2017-05-12). Signed-off-by: Junio C Hamano Signed-off-by: Ævar Arnfjörð Bjarmason Signed-off-by: Junio C Hamano

tree-diff: fix leak when not HAVE_ALLOCA_H

2021-09-16T20:43:42Z

b8ba412bf7 (tree-diff: avoid alloca for large allocations, 2016-06-07) adds a way to route some bigger allocations out of the stack and free them through the addition of two conveniently named macros, but leaves the calls to free the xalloca part, which could be also in the heap, if the system doesn't HAVE_ALLOCA_H (ex: macOS and other BSD). Add the missing free call, xalloca_free(), which is a noop if we allocated memory in the stack frame, but a real free() if we allocated in the heap instead, and while at it, change the expression to match in both macros for ease of readability. This avoids a leak reported by LSAN while running t0000 but that wouldn't fail the test (which is fixed in the next patch): SUMMARY: LeakSanitizer: 1034 byte(s) leaked in 15 allocation(s). Signed-off-by: Carlo Marcelo Arenas Belón Signed-off-by: Junio C Hamano

hash: provide per-algorithm null OIDs

2021-04-27T07:31:39Z

Up until recently, object IDs did not have an algorithm member, only a hash. Consequently, it was possible to share one null (all-zeros) object ID among all hash algorithms. Now that we're going to be handling objects from multiple hash algorithms, it's important to make sure that all object IDs have a correct algorithm field. Introduce a per-algorithm null OID, and add it to struct hash_algo. Introduce a wrapper function as well, and use it everywhere we used to use the null_oid constant. Signed-off-by: brian m. carlson Signed-off-by: Junio C Hamano

bloom/diff: properly short-circuit on max_changes

2020-09-17T16:31:25Z

Commit e3696980 (diff: halt tree-diff early after max_changes, 2020-03-30) intended to create a mechanism to short-circuit a diff calculation after a certain number of paths were modified. By incrementing a "num_changes" counter throughout the recursive ll_diff_tree_paths(), this was supposed to match the number of changes that would be written into the changed-path Bloom filters. Unfortunately, this was not implemented correctly and instead misses simple cases like file modifications. This then does not stop very large changed-path filters from being written (unless they add or remove many files). To start, change the implementation in ll_diff_tree_paths() to instead use the global diff_queue_diff struct's 'nr' member as the count. This is a way to simplify the logic instead of making more mistakes in the complicated diff code. This has a drawback: the diff_queue_diff struct only lists the paths corresponding to blob changes, not their leading directories. Thus, get_or_compute_bloom_filter() needs an additional check to see if the hashmap with the leading directories becomes too large. One reason why this was not caught by test cases was that the test in t4216-log-bloom.sh that was supposed to check this "too many changes" condition only checked this on the initial commit of a repository. The old logic counted these values correctly. Update this test in a few ways: 1. Use GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS to reduce the limit, allowing smaller commits to engage with this logic. 2. Create several interesting cases of edits, adds, removes, and mode changes (in the second commit). By testing both sides of the inequality with the *_MAX_CHANGED_PATHS variable, we can see that the count is exactly correct, so none of these changes are missed or over-counted. 3. Use the trace2 data value filter_found_large to verify that these commits are on the correct side of the limit. Another way to verify the behavior is correct is through performance tests. By testing on my local copies of the Git repository and the Linux kernel repository, I could measure the effect of these short-circuits when computing a fresh commit-graph file with changed-path Bloom filters using the command GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=N time \ git commit-graph write --reachable --changed-paths and reporting the wall time and resulting commit-graph size. For Git, the results are | | N=1 | N=10 | N=512 | |--------|----------------|----------------|----------------| | HEAD~1 | 10.90s 9.18MB | 11.11s 9.34MB | 11.31s 9.35MB | | HEAD | 9.21s 8.62MB | 11.11s 9.29MB | 11.29s 9.34MB | For Linux, the results are | | N=1 | N=20 | N=512 | |--------|----------------|---------------|---------------| | HEAD~1 | 61.28s 64.3MB | 76.9s 72.6MB | 77.6s 72.6MB | | HEAD | 49.44s 56.3MB | 68.7s 65.9MB | 69.2s 65.9MB | Naturally, the improvement becomes much less as the limit grows, as fewer commits satisfy the short-circuit. Reported-by: SZEDER Gábor Signed-off-by: Derrick Stolee Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano