Consolidate reachability logic #10

derrickstolee · 2018-07-13T20:08:47Z

There are many places in Git that use a commit walk to determine
reachability between commits and/or refs. A lot of this logic is
duplicated.

I wanted to achieve the following:

Consolidate several different commit walks into one file
Reduce duplicate reachability logic
Increase testability (correctness and performance)
Improve performance of reachability queries

My approach is mostly in three parts:

I. Move code to a new commit-reach.c file.
II. Add a 'test-tool reach' command to test these methods directly.
III. Modify the logic by improving performance and calling methods with
similar logic but different prototypes.

The 'test-tool reach' command is helpful to make sure I don't break
anything as I change the logic, but also so I can test methods that are
normally only exposed by other more complicated commands. For instance,
ref_newer() is part of 'git push -f' and ok_to_give_up() is buried deep
within fetch negotiation. Both of these methods have some problematic
performance issues that are corrected by this series. As I discovered
them, it was clear that it would be better to consolidate walk logic
instead of discovering a new walk in another file hidden somewhere.

For the ok_to_give_up() method, I refactored the method so I could pull
the logic out of the depths of fetch negotiation. In the commit
"commit-reach: make can_all_from_reach... linear" I discuss how the
existing algorithm is quadratic and how we can make it linear. Also, we
can use heuristic knowledge about the shape of the commit graph and the
usual haves/wants to get some extra performance bonus. (The heuristic is
to do a DFS with first-parents first, and stop on first found result. We
expect haves/wants to include ref tips, which typically have their
previous values in their first-parent history.)

One major difference in this series versus the RFC is that I added a new
method 'generation_numbers_enabled()' to detect if we have a commit-graph
file with non-zero generation numbers. Using can_all_from_reach in
is_descendant_of is only faster if we have generation numbers as a cutoff.

V2 Update: The biggest material change in this version is that we drop the
method declarations from commit.h, which requires adding a lot of references
to commit-reach.h across the codebase. This change is in a commit on its own.
In addition, we have the following style-based cleanups:

Use 'unsigned int' for the flag variables.
Properly align the here-doc test input data.
Use singe rev-parse commands in test output, and pipe the OIDs through 'sort'
Check output of parse_commit()
Update flag documentation in object.h
Add tests for commit_contains() including both algorithms.
Reduce size of "mixed-mode" commit-graph to ensure we start commit walks
'above' the graph and then walk into the commits with generation numbers.

Thanks,
-Stolee

This series is based on jt/commit-graph-per-object-store

Cc: [email protected]
Cc: [email protected]

derrickstolee · 2018-07-13T20:40:40Z

/submit

gitgitgadget · 2018-07-13T20:41:08Z

An error occurred while submitting:

Error: git format-patch --thread --stdout --signature=gitgitgadget --add-header=Fcc: Sent --add-header=Content-Type: text/plain; charset=UTF-8 --add-header=Content-Transfer-Encoding: 8bit --add-header=MIME-Version: 1.0 --base upstream/master --to=[email protected] --cc=Junio C Hamano [email protected] --cover-letter upstream/master..a60b701 failed: 128,
fatal: base commit should be the ancestor of revision list

derrickstolee · 2018-07-16T12:09:18Z

/submit

gitgitgadget · 2018-07-16T12:09:52Z

An error occurred while submitting:

Error: git format-patch --thread --stdout --signature=gitgitgadget --add-header=Fcc: Sent --add-header=Content-Type: text/plain; charset=UTF-8 --add-header=Content-Transfer-Encoding: 8bit --add-header=MIME-Version: 1.0 --base 9026cfc --to=[email protected] --cc=Junio C Hamano [email protected] --cover-letter 9026cfc..a60b701 failed: 128,
fatal: base commit should be the ancestor of revision list

derrickstolee · 2018-07-16T12:59:31Z

/submit

gitgitgadget · 2018-07-16T13:01:41Z

Submitted as [email protected]

dscho · 2018-07-16T14:05:11Z

So the build & test failed... but it is in the submodule code!

clicketyclick

Ah! You target pu, which is currently broken: https://git-for-windows.visualstudio.com/git/git%20Team/_build/results?buildId=12365&view=logs (same issue, so it is not your patch series' fault).

dscho · 2018-07-19T09:40:09Z

@derrickstolee Maybe we need to mirror the branches from https://github.com/gitster/git here, so that you can target the correct branch in pu? It just causes too much pain, obviously, to base your branch on top of pu.

Of course, you could also rebase your branch on top of the respective branch instead of pu...

There are several commit walks in the codebase. Group them together into a new commit-reach.c file and corresponding header. After we group these walks into one place, we can reduce duplicate logic by calling equivalent methods. The method declarations in commit.h are not touched by this commit and will be moved in a following commit. Many consumers need to point to commit-reach.h and that would bloat this commit. Signed-off-by: Derrick Stolee <[email protected]>

These methods are now declared in commit-reach.h. Remove them from commit.h and add new include statements in all files that require these declarations. Signed-off-by: Derrick Stolee <[email protected]>

There are several commit walks in the codebase. Group them together into a new commit-reach.c file and corresponding header. After we group these walks into one place, we can reduce duplicate logic by calling equivalent methods. The ref_newer() method is used by 'git push -f' to check if a force-push is necessary. By making the method public, we make it possible to test the method directly without setting up an envieronment where a 'git push' call makes sense. Signed-off-by: Derrick Stolee <[email protected]>

There are several commit walks in the codebase. Group them together into a new commit-reach.c file and corresponding header. After we group these walks into one place, we can reduce duplicate logic by calling equivalent methods. All methods are direct moves, except we also make the commit_contains() method public so its consumers in ref-filter.c can still call it. We can also test this method in a test-tool in a later commit. Signed-off-by: Derrick Stolee <[email protected]>

In anticipation of moving the reachable() method to commit-reach.c, modify the prototype to be more generic to flags known outside of upload-pack.c. Also rename 'want' to 'from' to make the statement more clear outside of the context of haves/wants negotiation. Signed-off-by: Derrick Stolee <[email protected]>

In anticipation of consolidating all commit reachability algorithms, refactor ok_to_give_up() in order to allow splitting its logic into an external method. Signed-off-by: Derrick Stolee <[email protected]>

The ok_to_give_up() method uses the commit date as a cutoff to avoid walking the entire reachble set of commits. Before moving the reachable() method to commit-reach.c, pull out the dependence on the global constant 'oldest_have' with a 'min_commit_date' parameter. Signed-off-by: Derrick Stolee <[email protected]>

There are several commit walks in the codebase. Group them together into a new commit-reach.c file and corresponding header. After we group these walks into one place, we can reduce duplicate logic by calling equivalent methods. The can_all_from_reach_with_flags method is used in a stateful way by upload-pack.c. The parameters are very flexible, so we will be able to use its commit walking logic for many other callers. Signed-off-by: Derrick Stolee <[email protected]>

As we prepare to change the behavior of the algorithms in commit-reach.c, create a new test-tool subcommand 'reach' to test these methods on interesting commit-graph shapes. To use the new test-tool, use 'test-tool reach <method>' and provide input to stdin that describes the inputs to the method. Currently, we only implement the ref_newer method, which requires two commits. Use lines "A:<committish>" and "B:<committish>" for the two inputs. We will expand this input later to accommodate methods that take lists of commits. The test t6600-test-reach.sh creates a repo whose commits form a two-dimensional grid. This grid makes it easy for us to determine reachability because commit-A-B can reach commit-X-Y if and only if A is at least X and B is at least Y. This helps create interesting test cases for each result of the methods in commit-reach.c. We test all methods in three different states of the commit-graph file: Non-existent (no generation numbers), fully computed, and mixed (some commits have generation numbers and others do not). Signed-off-by: Derrick Stolee <[email protected]>

Signed-off-by: Derrick Stolee <[email protected]>

The is_descendant_of method takes a single commit as its first parameter and a list of commits as its second parameter. Extend the input of the 'test-tool reach' command to take multiple lines of the form "X:<committish>" to construct a list of commits. Pass these to is_descendant_of and create tests that check each result. Signed-off-by: Derrick Stolee <[email protected]>

The get_merge_bases_many method returns a list of merge bases for a single commit (A) against a list of commits (X). Some care is needed in constructing the expected behavior because the result is not the expected merge-base for an octopus merge with those parents but instead the set of maximal commits that are reachable from A and at least one of the commits in X. Add get_merge_bases_many to 'test-tool reach' and create a test that demonstrates that this output returns multiple results. Specifically, we select a list of three commits such that we output two commits that are reachable from one of the first two, respectively, and none are reachable from the third. Signed-off-by: Derrick Stolee <[email protected]>

Signed-off-by: Derrick Stolee <[email protected]>

The can_all_from_reach_with_flags method is used by ok_to_give_up in upload-pack.c to see if we have done enough negotiation during a fetch. This method is intentionally created to preserve state between calls to assist with stateful negotiation, such as over SSH. To make this method testable, add a new can_all_from_reach method that does the initial setup and final tear-down. We will later use this method in production code. Call the method from 'test-tool reach' for now. Since this is a many-to-many reachability query, add a new type of input to the 'test-tool reach' input format. Lines "Y:<committish>" create a list of commits to be the reachability targets from the commits in the 'X' list. In the context of fetch negotiation, the 'X' commits are the 'want' commits and the 'Y' commits are the 'have' commits. Signed-off-by: Derrick Stolee <[email protected]>

It was recently reported that concurrent reads and writes may cause the reftable backend to segfault. The root cause of this is that we do not properly keep track of reftable readers across reloads. Suppose that you have a reftable iterator and then decide to reload the stack while iterating through the iterator. When the stack has been rewritten since we have created the iterator, then we would end up discarding a subset of readers that may still be in use by the iterator. The consequence is that we now try to reference deallocated memory, which of course segfaults. One way to trigger this is in t5616, where some background maintenance jobs have been leaking from one test into another. This leads to stack traces like the following one: + git -c protocol.version=0 -C pc1 fetch --filter=blob:limit=29999 --refetch origin AddressSanitizer:DEADLYSIGNAL ================================================================= ==657994==ERROR: AddressSanitizer: SEGV on unknown address 0x7fa0f0ec6089 (pc 0x55f23e52ddf9 bp 0x7ffe7bfa1700 sp 0x7ffe7bfa1700 T0) ==657994==The signal is caused by a READ memory access. #0 0x55f23e52ddf9 in get_var_int reftable/record.c:29 #1 0x55f23e53295e in reftable_decode_keylen reftable/record.c:170 #2 0x55f23e532cc0 in reftable_decode_key reftable/record.c:194 #3 0x55f23e54e72e in block_iter_next reftable/block.c:398 #4 0x55f23e5573dc in table_iter_next_in_block reftable/reader.c:240 #5 0x55f23e5573dc in table_iter_next reftable/reader.c:355 #6 0x55f23e5573dc in table_iter_next reftable/reader.c:339 #7 0x55f23e551283 in merged_iter_advance_subiter reftable/merged.c:69 #8 0x55f23e55169e in merged_iter_next_entry reftable/merged.c:123 #9 0x55f23e55169e in merged_iter_next_void reftable/merged.c:172 #10 0x55f23e537625 in reftable_iterator_next_ref reftable/generic.c:175 #11 0x55f23e2cf9c6 in reftable_ref_iterator_advance refs/reftable-backend.c:464 #12 0x55f23e2d996e in ref_iterator_advance refs/iterator.c:13 #13 0x55f23e2d996e in do_for_each_ref_iterator refs/iterator.c:452 #14 0x55f23dca6767 in get_ref_map builtin/fetch.c:623 #15 0x55f23dca6767 in do_fetch builtin/fetch.c:1659 #16 0x55f23dca6767 in fetch_one builtin/fetch.c:2133 #17 0x55f23dca6767 in cmd_fetch builtin/fetch.c:2432 #18 0x55f23dba7764 in run_builtin git.c:484 #19 0x55f23dba7764 in handle_builtin git.c:741 #20 0x55f23dbab61e in run_argv git.c:805 #21 0x55f23dbab61e in cmd_main git.c:1000 #22 0x55f23dba4781 in main common-main.c:64 #23 0x7fa0f063fc89 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58 #24 0x7fa0f063fd44 in __libc_start_main_impl ../csu/libc-start.c:360 #25 0x55f23dba6ad0 in _start (git+0xadfad0) (BuildId: 803b2b7f59beb03d7849fb8294a8e2145dd4aa27) While it is somewhat awkward that the maintenance processes survive tests in the first place, it is totally expected that reftables should work alright with concurrent writers. Seemingly they don't. The only underlying resource that we need to care about in this context is the reftable reader, which is responsible for reading a single table from disk. These readers get discarded immediately (unless reused) when calling `reftable_stack_reload()`, which is wrong. We can only close them once we know that there are no iterators using them anymore. Prepare for a fix by converting the reftable readers to be refcounted. Reported-by: Jeff King <[email protected]> Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

The incremental MIDX bitmap work was done prior to 9d4855e (midx-write: fix leaking buffer, 2024-09-30), and causes test failures in t5334 in a post-9d4855eef3 world. The leak looks like: Direct leak of 264 byte(s) in 1 object(s) allocated from: #0 0x7f6bcd87eaca in calloc ../../../../src/libsanitizer/lsan/lsan_interceptors.cpp:90 #1 0x55ad1428e8a4 in xcalloc wrapper.c:151 #2 0x55ad14199e16 in prepare_midx_bitmap_git pack-bitmap.c:742 #3 0x55ad14199447 in open_midx_bitmap_1 pack-bitmap.c:507 #4 0x55ad14199cca in open_midx_bitmap pack-bitmap.c:704 #5 0x55ad14199d44 in open_bitmap pack-bitmap.c:717 #6 0x55ad14199dc2 in prepare_bitmap_git pack-bitmap.c:733 #7 0x55ad1419e496 in test_bitmap_walk pack-bitmap.c:2698 #8 0x55ad14047b0b in cmd_rev_list builtin/rev-list.c:629 #9 0x55ad13f71cd6 in run_builtin git.c:487 #10 0x55ad13f72132 in handle_builtin git.c:756 #11 0x55ad13f72380 in run_argv git.c:826 #12 0x55ad13f728f4 in cmd_main git.c:961 #13 0x55ad1407d3ae in main common-main.c:64 #14 0x7f6bcd5f0c89 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58 #15 0x7f6bcd5f0d44 in __libc_start_main_impl ../csu/libc-start.c:360 #16 0x55ad13f6ff90 in _start (git+0x1ef90) (BuildId: 3e63cdd415f1d185b21da3035cb48332510dddce) , and is a result of us not freeing the resources corresponding to the bitmap's base layer, if one was present. Rectify that leak by calling the newly-introduced free_bitmap_index() function on the base layer to ensure that its resources are also freed. Signed-off-by: Taylor Blau <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

This one is a little bit more curious. In t6112, we have a test that exercises the `git rev-list --filter` option with invalid filters. We execute git-rev-list(1) via `test_must_fail`, which means that we check for leaks even though Git exits with an error code. This causes the following leak: Direct leak of 27 byte(s) in 1 object(s) allocated from: #0 0x5555555e6946 in realloc.part.0 lsan_interceptors.cpp.o #1 0x5555558fb4b6 in xrealloc wrapper.c:137:8 #2 0x5555558b6e06 in strbuf_grow strbuf.c:112:2 #3 0x5555558b7550 in strbuf_add strbuf.c:311:2 #4 0x5555557c1a88 in strbuf_addstr strbuf.h:310:2 #5 0x5555557c1d4c in parse_list_objects_filter list-objects-filter-options.c:261:3 #6 0x555555885ead in handle_revision_pseudo_opt revision.c:2899:3 #7 0x555555884e20 in setup_revisions revision.c:3014:11 #8 0x5555556c4b42 in cmd_rev_list builtin/rev-list.c:588:9 #9 0x5555555ec5e3 in run_builtin git.c:483:11 #10 0x5555555eb1e4 in handle_builtin git.c:749:13 #11 0x5555555ec001 in run_argv git.c:819:4 #12 0x5555555eaf94 in cmd_main git.c:954:19 #13 0x5555556fd569 in main common-main.c:64:11 #14 0x7ffff7ca714d in __libc_start_call_main (.../lib/libc.so.6+0x2a14d) #15 0x7ffff7ca7208 in __libc_start_main@GLIBC_2.2.5 (.../libc.so.6+0x2a208) #16 0x5555555ad064 in _start (git+0x59064) This leak is valid, as we call `die()` and do not clean up the memory at all. But what's curious is that this is the only leak reported, because we don't clean up any other allocated memory, either, and I have no idea why the leak sanitizer treats this buffer specially. In any case, we can work around the leak by shuffling things around a bit. Instead of calling `gently_parse_list_objects_filter()` and dying after we have modified the filter spec, we simply do so beforehand. Like this we don't allocate the buffer in the error case, which makes the reported leak go away. It's not pretty, but it manages to make t6112 leak free. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Taylor Blau <[email protected]>

This one is a little bit more curious. In t6112, we have a test that exercises the `git rev-list --filter` option with invalid filters. We execute git-rev-list(1) via `test_must_fail`, which means that we check for leaks even though Git exits with an error code. This causes the following leak: Direct leak of 27 byte(s) in 1 object(s) allocated from: #0 0x5555555e6946 in realloc.part.0 lsan_interceptors.cpp.o #1 0x5555558fb4b6 in xrealloc wrapper.c:137:8 #2 0x5555558b6e06 in strbuf_grow strbuf.c:112:2 #3 0x5555558b7550 in strbuf_add strbuf.c:311:2 #4 0x5555557c1a88 in strbuf_addstr strbuf.h:310:2 #5 0x5555557c1d4c in parse_list_objects_filter list-objects-filter-options.c:261:3 #6 0x555555885ead in handle_revision_pseudo_opt revision.c:2899:3 #7 0x555555884e20 in setup_revisions revision.c:3014:11 #8 0x5555556c4b42 in cmd_rev_list builtin/rev-list.c:588:9 #9 0x5555555ec5e3 in run_builtin git.c:483:11 #10 0x5555555eb1e4 in handle_builtin git.c:749:13 #11 0x5555555ec001 in run_argv git.c:819:4 #12 0x5555555eaf94 in cmd_main git.c:954:19 #13 0x5555556fd569 in main common-main.c:64:11 #14 0x7ffff7ca714d in __libc_start_call_main (.../lib/libc.so.6+0x2a14d) #15 0x7ffff7ca7208 in __libc_start_main@GLIBC_2.2.5 (.../libc.so.6+0x2a208) #16 0x5555555ad064 in _start (git+0x59064) This leak is valid, as we call `die()` and do not clean up the memory at all. But what's curious is that this is the only leak reported, because we don't clean up any other allocated memory, either, and I have no idea why the leak sanitizer treats this buffer specially. In any case, we can work around the leak by shuffling things around a bit. Instead of calling `gently_parse_list_objects_filter()` and dying after we have modified the filter spec, we simply do so beforehand. Like this we don't allocate the buffer in the error case, which makes the reported leak go away. It's not pretty, but it manages to make t6112 leak free. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

In 1b9e9be (csum-file.c: use unsafe SHA-1 implementation when available, 2024-09-26) we have converted our `struct hashfile` to use the unsafe SHA1 backend, which results in a significant speedup. One needs to be careful with how to use that structure now though because callers need to consistently use either the safe or unsafe variants of SHA1, as otherwise one can easily trigger corruption. As it turns out, we have one inconsistent usage in our tree because we directly initialize `struct hashfile_checkpoint::ctx` with the safe variant of SHA1, but end up writing to that context with the unsafe ones. This went unnoticed so far because our CI systems do not exercise different hash functions for these two backends, and consequently safe and unsafe variants are equivalent. But when using SHA1DC as safe and OpenSSL as unsafe backend this leads to a crash an t1050: ++ git -c core.compression=0 add large1 AddressSanitizer:DEADLYSIGNAL ================================================================= ==1367==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000040 (pc 0x7ffff7a01a99 bp 0x507000000db0 sp 0x7fffffff5690 T0) ==1367==The signal is caused by a READ memory access. ==1367==Hint: address points to the zero page. #0 0x7ffff7a01a99 in EVP_MD_CTX_copy_ex (/nix/store/h1ydpxkw9qhjdxjpic1pdc2nirggyy6f-openssl-3.3.2/lib/libcrypto.so.3+0x201a99) (BuildId: 41746a580d39075fc85e8c8065b6c07fb34e97d4) #1 0x555555ddde56 in openssl_SHA1_Clone ../sha1/openssl.h:40:2 #2 0x555555dce2fc in git_hash_sha1_clone_unsafe ../object-file.c:123:2 #3 0x555555c2d5f8 in hashfile_checkpoint ../csum-file.c:211:2 #4 0x555555b9905d in deflate_blob_to_pack ../bulk-checkin.c:286:4 #5 0x555555b98ae9 in index_blob_bulk_checkin ../bulk-checkin.c:362:15 #6 0x555555ddab62 in index_blob_stream ../object-file.c:2756:9 #7 0x555555dda420 in index_fd ../object-file.c:2778:9 #8 0x555555ddad76 in index_path ../object-file.c:2796:7 #9 0x555555e947f3 in add_to_index ../read-cache.c:771:7 #10 0x555555e954a4 in add_file_to_index ../read-cache.c:804:9 #11 0x5555558b5c39 in add_files ../builtin/add.c:355:7 #12 0x5555558b412e in cmd_add ../builtin/add.c:578:18 #13 0x555555b1f493 in run_builtin ../git.c:480:11 #14 0x555555b1bfef in handle_builtin ../git.c:740:9 #15 0x555555b1e6f4 in run_argv ../git.c:807:4 #16 0x555555b1b87a in cmd_main ../git.c:947:19 #17 0x5555561649e6 in main ../common-main.c:64:11 #18 0x7ffff742a1fb in __libc_start_call_main (/nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: bf320110569c8ec2425e9a0c5e4eb7e97f1fb6e4) #19 0x7ffff742a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: bf320110569c8ec2425e9a0c5e4eb7e97f1fb6e4) #20 0x555555772c84 in _start (git+0x21ec84) ==1367==Register values: rax = 0x0000511000001080 rbx = 0x0000000000000000 rcx = 0x000000000000000c rdx = 0x0000000000000000 rdi = 0x0000000000000000 rsi = 0x0000507000000db0 rbp = 0x0000507000000db0 rsp = 0x00007fffffff5690 r8 = 0x0000000000000000 r9 = 0x0000000000000000 r10 = 0x0000000000000000 r11 = 0x00007ffff7a01a30 r12 = 0x0000000000000000 r13 = 0x00007fffffff6b38 r14 = 0x00007ffff7ffd000 r15 = 0x00005555563b9910 AddressSanitizer can not provide additional info. SUMMARY: AddressSanitizer: SEGV (/nix/store/h1ydpxkw9qhjdxjpic1pdc2nirggyy6f-openssl-3.3.2/lib/libcrypto.so.3+0x201a99) (BuildId: 41746a580d39075fc85e8c8065b6c07fb34e97d4) in EVP_MD_CTX_copy_ex ==1367==ABORTING ./test-lib.sh: line 1023: 1367 Aborted git $config add large1 error: last command exited with $?=134 not ok 4 - add with -c core.compression=0 Fix the issue by using the unsafe variant instead. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

Same as with the preceding commit, git-fast-import(1) is using the safe variant to initialize a hashfile checkpoint. This leads to a segfault when passing the checkpoint into the hashfile subsystem because it would use the unsafe variants instead: ++ git --git-dir=R/.git fast-import --big-file-threshold=1 AddressSanitizer:DEADLYSIGNAL ================================================================= ==577126==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000040 (pc 0x7ffff7a01a99 bp 0x5070000009c0 sp 0x7fffffff5b30 T0) ==577126==The signal is caused by a READ memory access. ==577126==Hint: address points to the zero page. #0 0x7ffff7a01a99 in EVP_MD_CTX_copy_ex (/nix/store/h1ydpxkw9qhjdxjpic1pdc2nirggyy6f-openssl-3.3.2/lib/libcrypto.so.3+0x201a99) (BuildId: 41746a580d39075fc85e8c8065b6c07fb34e97d4) #1 0x555555ddde56 in openssl_SHA1_Clone ../sha1/openssl.h:40:2 #2 0x555555dce2fc in git_hash_sha1_clone_unsafe ../object-file.c:123:2 #3 0x555555c2d5f8 in hashfile_checkpoint ../csum-file.c:211:2 #4 0x5555559647d1 in stream_blob ../builtin/fast-import.c:1110:2 #5 0x55555596247b in parse_and_store_blob ../builtin/fast-import.c:2031:3 #6 0x555555967f91 in file_change_m ../builtin/fast-import.c:2408:5 #7 0x55555595d8a2 in parse_new_commit ../builtin/fast-import.c:2768:4 #8 0x55555595bb7a in cmd_fast_import ../builtin/fast-import.c:3614:4 #9 0x555555b1f493 in run_builtin ../git.c:480:11 #10 0x555555b1bfef in handle_builtin ../git.c:740:9 #11 0x555555b1e6f4 in run_argv ../git.c:807:4 #12 0x555555b1b87a in cmd_main ../git.c:947:19 #13 0x5555561649e6 in main ../common-main.c:64:11 #14 0x7ffff742a1fb in __libc_start_call_main (/nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: bf320110569c8ec2425e9a0c5e4eb7e97f1fb6e4) #15 0x7ffff742a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: bf320110569c8ec2425e9a0c5e4eb7e97f1fb6e4) #16 0x555555772c84 in _start (git+0x21ec84) ==577126==Register values: rax = 0x0000511000000cc0 rbx = 0x0000000000000000 rcx = 0x000000000000000c rdx = 0x0000000000000000 rdi = 0x0000000000000000 rsi = 0x00005070000009c0 rbp = 0x00005070000009c0 rsp = 0x00007fffffff5b30 r8 = 0x0000000000000000 r9 = 0x0000000000000000 r10 = 0x0000000000000000 r11 = 0x00007ffff7a01a30 r12 = 0x0000000000000000 r13 = 0x00007fffffff6b60 r14 = 0x00007ffff7ffd000 r15 = 0x00005555563b9910 AddressSanitizer can not provide additional info. SUMMARY: AddressSanitizer: SEGV (/nix/store/h1ydpxkw9qhjdxjpic1pdc2nirggyy6f-openssl-3.3.2/lib/libcrypto.so.3+0x201a99) (BuildId: 41746a580d39075fc85e8c8065b6c07fb34e97d4) in EVP_MD_CTX_copy_ex ==577126==ABORTING ./test-lib.sh: line 1039: 577126 Aborted git --git-dir=R/.git fast-import --big-file-threshold=1 < input error: last command exited with $?=134 not ok 167 - R: blob bigger than threshold The segfault is only exposed in case the unsafe and safe backends are different from one another. Fix the issue by initializing the context with the unsafe SHA1 variant. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

When trying to create a Unix socket in a path that exceeds the maximum socket name length we try to first change the directory into the parent folder before creating the socket to reduce the length of the name. When this fails we error out of `unix_sockaddr_init()` with an error code, which indicates to the caller that the context has not been initialized. Consequently, they don't release that context. This leads to a memory leak: when we have already populated the context with the original directory that we need to chdir(3p) back into, but then the chdir(3p) into the socket's parent directory fails, then we won't release the original directory's path. The leak is exposed by t0301, but only via Meson with `meson setup -Dsanitize=leak`: Direct leak of 129 byte(s) in 1 object(s) allocated from: #0 0x5555555e85c6 in realloc.part.0 lsan_interceptors.cpp.o #1 0x55555590e3d6 in xrealloc ../wrapper.c:140:8 #2 0x5555558c8fc6 in strbuf_grow ../strbuf.c:114:2 #3 0x5555558cacab in strbuf_getcwd ../strbuf.c:605:3 #4 0x555555923ff6 in unix_sockaddr_init ../unix-socket.c:65:7 #5 0x555555923e42 in unix_stream_connect ../unix-socket.c:84:6 #6 0x55555562a984 in send_request ../builtin/credential-cache.c:46:11 #7 0x55555562a89e in do_cache ../builtin/credential-cache.c:108:6 #8 0x55555562a655 in cmd_credential_cache ../builtin/credential-cache.c:178:3 #9 0x555555700547 in run_builtin ../git.c:480:11 #10 0x5555556ff0e0 in handle_builtin ../git.c:740:9 #11 0x5555556ffee8 in run_argv ../git.c:807:4 #12 0x5555556fee6b in cmd_main ../git.c:947:19 #13 0x55555593f689 in main ../common-main.c:64:11 #14 0x7ffff7a2a1fb in __libc_start_call_main (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #15 0x7ffff7a2a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #16 0x5555555ad1d4 in _start (git+0x591d4) DEDUP_TOKEN: ___interceptor_realloc.part.0--xrealloc--strbuf_grow--strbuf_getcwd--unix_sockaddr_init--unix_stream_connect--send_request--do_cache--cmd_credential_cache--run_builtin--handle_builtin--run_argv--cmd_main--main--__libc_start_call_main--__libc_start_main@GLIBC_2.2.5--_start SUMMARY: LeakSanitizer: 129 byte(s) leaked in 1 allocation(s). Fix this leak. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

We don't free the result of `remote_default_branch()`, leading to a memory leak. This leak is exposed by t9211, but only when run with Meson via `meson setup -Dsanitize=leak`: Direct leak of 5 byte(s) in 1 object(s) allocated from: #0 0x5555555cfb93 in malloc (scalar+0x7bb93) #1 0x5555556b05c2 in do_xmalloc ../wrapper.c:55:8 #2 0x5555556b06c4 in do_xmallocz ../wrapper.c:89:8 #3 0x5555556b0656 in xmallocz ../wrapper.c:97:9 #4 0x5555556b0728 in xmemdupz ../wrapper.c:113:16 #5 0x5555556b07a7 in xstrndup ../wrapper.c:119:9 #6 0x5555555d3a4b in remote_default_branch ../scalar.c:338:14 #7 0x5555555d20e6 in cmd_clone ../scalar.c:493:28 #8 0x5555555d196b in cmd_main ../scalar.c:992:14 #9 0x5555557c4059 in main ../common-main.c:64:11 #10 0x7ffff7a2a1fb in __libc_start_call_main (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #11 0x7ffff7a2a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #12 0x555555592054 in _start (scalar+0x3e054) DEDUP_TOKEN: __interceptor_malloc--do_xmalloc--do_xmallocz--xmallocz--xmemdupz--xstrndup--remote_default_branch--cmd_clone--cmd_main--main--__libc_start_call_main--__libc_start_main@GLIBC_2.2.5--_start SUMMARY: LeakSanitizer: 5 byte(s) leaked in 1 allocation(s). As the `branch` variable may contain a string constant obtained from parsing command line arguments we cannot free the leaking variable directly. Instead, introduce a new `branch_to_free` variable that only ever gets assigned the allocated string and free that one to plug the leak. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

When trying to create a Unix socket in a path that exceeds the maximum socket name length we try to first change the directory into the parent folder before creating the socket to reduce the length of the name. When this fails we error out of `unix_sockaddr_init()` with an error code, which indicates to the caller that the context has not been initialized. Consequently, they don't release that context. This leads to a memory leak: when we have already populated the context with the original directory that we need to chdir(3p) back into, but then the chdir(3p) into the socket's parent directory fails, then we won't release the original directory's path. The leak is exposed by t0301, but only when running tests in a directory hierarchy whose path is long enough to make the socket name length exceed the maximum socket name length: Direct leak of 129 byte(s) in 1 object(s) allocated from: #0 0x5555555e85c6 in realloc.part.0 lsan_interceptors.cpp.o #1 0x55555590e3d6 in xrealloc ../wrapper.c:140:8 #2 0x5555558c8fc6 in strbuf_grow ../strbuf.c:114:2 #3 0x5555558cacab in strbuf_getcwd ../strbuf.c:605:3 #4 0x555555923ff6 in unix_sockaddr_init ../unix-socket.c:65:7 #5 0x555555923e42 in unix_stream_connect ../unix-socket.c:84:6 #6 0x55555562a984 in send_request ../builtin/credential-cache.c:46:11 #7 0x55555562a89e in do_cache ../builtin/credential-cache.c:108:6 #8 0x55555562a655 in cmd_credential_cache ../builtin/credential-cache.c:178:3 #9 0x555555700547 in run_builtin ../git.c:480:11 #10 0x5555556ff0e0 in handle_builtin ../git.c:740:9 #11 0x5555556ffee8 in run_argv ../git.c:807:4 #12 0x5555556fee6b in cmd_main ../git.c:947:19 #13 0x55555593f689 in main ../common-main.c:64:11 #14 0x7ffff7a2a1fb in __libc_start_call_main (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #15 0x7ffff7a2a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #16 0x5555555ad1d4 in _start (git+0x591d4) DEDUP_TOKEN: ___interceptor_realloc.part.0--xrealloc--strbuf_grow--strbuf_getcwd--unix_sockaddr_init--unix_stream_connect--send_request--do_cache--cmd_credential_cache--run_builtin--handle_builtin--run_argv--cmd_main--main--__libc_start_call_main--__libc_start_main@GLIBC_2.2.5--_start SUMMARY: LeakSanitizer: 129 byte(s) leaked in 1 allocation(s). Fix this leak. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

We don't free the result of `remote_default_branch()`, leading to a memory leak. This leak is exposed by t9211, but only when run with Meson with the `-Db_sanitize=leak` option: Direct leak of 5 byte(s) in 1 object(s) allocated from: #0 0x5555555cfb93 in malloc (scalar+0x7bb93) #1 0x5555556b05c2 in do_xmalloc ../wrapper.c:55:8 #2 0x5555556b06c4 in do_xmallocz ../wrapper.c:89:8 #3 0x5555556b0656 in xmallocz ../wrapper.c:97:9 #4 0x5555556b0728 in xmemdupz ../wrapper.c:113:16 #5 0x5555556b07a7 in xstrndup ../wrapper.c:119:9 #6 0x5555555d3a4b in remote_default_branch ../scalar.c:338:14 #7 0x5555555d20e6 in cmd_clone ../scalar.c:493:28 #8 0x5555555d196b in cmd_main ../scalar.c:992:14 #9 0x5555557c4059 in main ../common-main.c:64:11 #10 0x7ffff7a2a1fb in __libc_start_call_main (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a1fb) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #11 0x7ffff7a2a2b8 in __libc_start_main@GLIBC_2.2.5 (/nix/store/h7zcxabfxa7v5xdna45y2hplj31ncf8a-glibc-2.40-36/lib/libc.so.6+0x2a2b8) (BuildId: 0a855678aa0cb573cecbb2bcc73ab8239ec472d0) #12 0x555555592054 in _start (scalar+0x3e054) DEDUP_TOKEN: __interceptor_malloc--do_xmalloc--do_xmallocz--xmallocz--xmemdupz--xstrndup--remote_default_branch--cmd_clone--cmd_main--main--__libc_start_call_main--__libc_start_main@GLIBC_2.2.5--_start SUMMARY: LeakSanitizer: 5 byte(s) leaked in 1 allocation(s). As the `branch` variable may contain a string constant obtained from parsing command line arguments we cannot free the leaking variable directly. Instead, introduce a new `branch_to_free` variable that only ever gets assigned the allocated string and free that one to plug the leak. It is unclear why the leak isn't flagged when running the test via our Makefile. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

find_cfg_ent() allocates a struct reflog_expire_entry_option via FLEX_ALLOC_MEM and inserts it into a linked list in the reflog_expire_options structure. The entries in this list are never freed, resulting in a leak in cmd_reflog_expire and the gc reflog expire maintenance task: Direct leak of 39 byte(s) in 1 object(s) allocated from: #0 0x7ff975ee6883 in calloc (/lib64/libasan.so.8+0xe6883) #1 0x0000010edada in xcalloc ../wrapper.c:154 #2 0x000000df0898 in find_cfg_ent ../reflog.c:28 #3 0x000000df0898 in reflog_expire_config ../reflog.c:70 #4 0x00000095c451 in configset_iter ../config.c:2116 #5 0x0000006d29e7 in git_config ../config.h:724 #6 0x0000006d29e7 in cmd_reflog_expire ../builtin/reflog.c:205 #7 0x0000006d504c in cmd_reflog ../builtin/reflog.c:419 #8 0x0000007e4054 in run_builtin ../git.c:480 #9 0x0000007e4054 in handle_builtin ../git.c:746 #10 0x0000007e8a35 in run_argv ../git.c:813 #11 0x0000007e8a35 in cmd_main ../git.c:953 #12 0x000000441e8f in main ../common-main.c:9 #13 0x7ff9754115f4 in __libc_start_call_main (/lib64/libc.so.6+0x35f4) #14 0x7ff9754116a7 in __libc_start_main@@GLIBC_2.34 (/lib64/libc.so.6+0x36a7) #15 0x000000444184 in _start (/home/jekeller/libexec/git-core/git+0x444184) Close this leak by adding a reflog_clear_expire_config() function which iterates the linked list and frees its elements. Call it upon exit of cmd_reflog_expire() and reflog_expire_condition(). Signed-off-by: Jacob Keller <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

find_cfg_ent() allocates a struct reflog_expire_entry_option via FLEX_ALLOC_MEM and inserts it into a linked list in the reflog_expire_options structure. The entries in this list are never freed, resulting in a leak in cmd_reflog_expire and the gc reflog expire maintenance task: Direct leak of 39 byte(s) in 1 object(s) allocated from: #0 0x7ff975ee6883 in calloc (/lib64/libasan.so.8+0xe6883) #1 0x0000010edada in xcalloc ../wrapper.c:154 #2 0x000000df0898 in find_cfg_ent ../reflog.c:28 #3 0x000000df0898 in reflog_expire_config ../reflog.c:70 #4 0x00000095c451 in configset_iter ../config.c:2116 #5 0x0000006d29e7 in git_config ../config.h:724 #6 0x0000006d29e7 in cmd_reflog_expire ../builtin/reflog.c:205 #7 0x0000006d504c in cmd_reflog ../builtin/reflog.c:419 #8 0x0000007e4054 in run_builtin ../git.c:480 #9 0x0000007e4054 in handle_builtin ../git.c:746 #10 0x0000007e8a35 in run_argv ../git.c:813 #11 0x0000007e8a35 in cmd_main ../git.c:953 #12 0x000000441e8f in main ../common-main.c:9 #13 0x7ff9754115f4 in __libc_start_call_main (/lib64/libc.so.6+0x35f4) #14 0x7ff9754116a7 in __libc_start_main@@GLIBC_2.34 (/lib64/libc.so.6+0x36a7) #15 0x000000444184 in _start (/home/jekeller/libexec/git-core/git+0x444184) Close this leak by adding a reflog_clear_expire_config() function which iterates the linked list and frees its elements. Call it upon exit of cmd_reflog_expire() and reflog_expire_condition(). Add a basic test which covers this leak. While at it, cover the functionality from commit commit 3cb22b8 (Per-ref reflog expiry configuration, 2008-06-15). We've had this support for years, but lacked any tests. Co-developed-by: Jeff King <[email protected]> Signed-off-by: Jacob Keller <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

When performing auto-maintenance we check whether commit graphs need to be generated by counting the number of commits that are reachable by any reference, but not covered by a commit graph. This search is performed by iterating through all references and then doing a depth-first search until we have found enough commits that are not present in the commit graph. This logic has a memory leak though: Direct leak of 16 byte(s) in 1 object(s) allocated from: #0 0x55555562e433 in malloc (git+0xda433) #1 0x555555964322 in do_xmalloc ../wrapper.c:55:8 #2 0x5555559642e6 in xmalloc ../wrapper.c:76:9 #3 0x55555579bf29 in commit_list_append ../commit.c:1872:35 #4 0x55555569f160 in dfs_on_ref ../builtin/gc.c:1165:4 #5 0x5555558c33fd in do_for_each_ref_iterator ../refs/iterator.c:431:12 #6 0x5555558af520 in do_for_each_ref ../refs.c:1828:9 #7 0x5555558ac317 in refs_for_each_ref ../refs.c:1833:9 #8 0x55555569e207 in should_write_commit_graph ../builtin/gc.c:1188:11 #9 0x55555569c915 in maintenance_is_needed ../builtin/gc.c:3492:8 #10 0x55555569b76a in cmd_maintenance ../builtin/gc.c:3542:9 #11 0x55555575166a in run_builtin ../git.c:506:11 #12 0x5555557502f0 in handle_builtin ../git.c:779:9 #13 0x555555751127 in run_argv ../git.c:862:4 #14 0x55555575007b in cmd_main ../git.c:984:19 #15 0x5555557523aa in main ../common-main.c:9:11 #16 0x7ffff7a2a4d7 in __libc_start_call_main (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x2a4d7) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #17 0x7ffff7a2a59a in __libc_start_main@GLIBC_2.2.5 (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x2a59a) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #18 0x5555555f0934 in _start (git+0x9c934) The root cause of this memory leak is our use of `commit_list_append()`. This function expects as parameters the item to append and the _tail_ of the list to append. This tail will then be overwritten with the new tail of the list so that it can be used in subsequent calls. But we call it with `commit_list_append(parent->item, &stack)`, so we end up losing everything but the new item. This issue only surfaces when counting merge commits. Next to being a memory leak, it also shows that we're in fact miscounting as we only respect children of the last parent. All previous parents are discarded, so their children will be disregarded unless they are hit via another reference. While crafting a test case for the issue I was puzzled that I couldn't establish the proper border at which the auto-condition would be fulfilled. As it turns out, there's another bug: if an object is at the tip of any reference we don't mark it as seen. Consequently, if it is reachable via any other reference, we'd count that object twice. Fix both of these bugs so that we properly count objects without leaking any memory. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

In the next commit we are about to move the packfile store into the ODB source so that we have one store per source. This will lead to a memory leak in the following commit when reading data from a submodule via git-grep(1): Direct leak of 192 byte(s) in 1 object(s) allocated from: #0 0x55555562e726 in calloc (git+0xda726) #1 0x555555964734 in xcalloc ../wrapper.c:154:8 #2 0x555555835136 in load_multi_pack_index_one ../midx.c:135:2 #3 0x555555834fd6 in load_multi_pack_index ../midx.c:382:6 #4 0x5555558365b6 in prepare_multi_pack_index_one ../midx.c:716:17 #5 0x55555586c605 in packfile_store_prepare ../packfile.c:1103:3 #6 0x55555586c90c in packfile_store_reprepare ../packfile.c:1118:2 #7 0x5555558546b3 in odb_reprepare ../odb.c:1106:2 #8 0x5555558539e4 in do_oid_object_info_extended ../odb.c:715:4 #9 0x5555558533d1 in odb_read_object_info_extended ../odb.c:862:8 #10 0x5555558540bd in odb_read_object ../odb.c:920:6 #11 0x55555580a330 in grep_source_load_oid ../grep.c:1934:12 #12 0x55555580a13a in grep_source_load ../grep.c:1986:10 #13 0x555555809103 in grep_source_is_binary ../grep.c:2014:7 #14 0x555555807574 in grep_source_1 ../grep.c:1625:8 #15 0x555555807322 in grep_source ../grep.c:1837:10 #16 0x5555556a5c58 in run ../builtin/grep.c:208:10 #17 0x55555562bb42 in void* ThreadStartFunc<false>(void*) lsan_interceptors.cpp.o #18 0x7ffff7a9a979 in start_thread (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x9a979) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #19 0x7ffff7b22d2b in __GI___clone3 (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x122d2b) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) The root caues of this leak is the way we set up and release the submodule: 1. We use `repo_submodule_init()` to initialize a new repository. This repository is stored in `repos_to_free`. 2. We now read data from the submodule repository. 3. We then call `repo_clear()` on the submodule repositories. 4. `repo_clear()` calls `odb_free()`. 5. `odb_free()` calls `odb_free_sources()` followed by `odb_close()`. The issue here is the 5th step: we call `odb_free_sources()` _before_ we call `odb_close()`. But `odb_free_sources()` already frees all sources, so the logic that closes them in `odb_close()` now becomes a no-op. As a consequence, we never explicitly close sources at all. Fix the leak by closing the store before we free the sources. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

When pushing to a set of remotes using a nickname for the group, the client initializes the connection to each remote, talks to the remote and reads and parses capabilities line, and holds the capabilities in a file-scope static variable server_capabilities_v1. There are a few other such file-scope static variables, and these connections cannot be parallelized until they are refactored to a structure that keeps track of active connections. Which is *not* the theme of this patch ;-) For a single connection, the server_capabilities_v1 variable is initialized to NULL (at the program initialization), populated when we talk to the other side, used to look up capabilities of the other sdie possible multiple times, and the memory is held by the variable until program exit, without leaking. When talking to multiple remotes, however, the server capabilities from the second connection overwrites without freeing the one from the first connection, which leaks. ==1080970==ERROR: LeakSanitizer: detected memory leaks Direct leak of 421 byte(s) in 2 object(s) allocated from: #0 0x5615305f849e in strdup (/home/gitster/g/git-jch/bin/bin/git+0x2b349e) (BuildId: 54d149994c9e85374831958f694bd0aa3b8b1e26) #1 0x561530e76cc4 in xstrdup /home/gitster/w/build/wrapper.c:43:14 #2 0x5615309cd7fa in process_capabilities /home/gitster/w/build/connect.c:243:27 #3 0x5615309cd502 in get_remote_heads /home/gitster/w/build/connect.c:366:4 #4 0x561530e2cb0b in handshake /home/gitster/w/build/transport.c:372:3 #5 0x561530e29ed7 in get_refs_via_connect /home/gitster/w/build/transport.c:398:9 #6 0x561530e26464 in transport_push /home/gitster/w/build/transport.c:1421:16 #7 0x561530800bec in push_with_options /home/gitster/w/build/builtin/push.c:387:8 #8 0x5615307ffb99 in do_push /home/gitster/w/build/builtin/push.c:442:7 #9 0x5615307fe926 in cmd_push /home/gitster/w/build/builtin/push.c:664:7 #10 0x56153065673f in run_builtin /home/gitster/w/build/git.c:506:11 #11 0x56153065342f in handle_builtin /home/gitster/w/build/git.c:779:9 #12 0x561530655b89 in run_argv /home/gitster/w/build/git.c:862:4 #13 0x561530652cba in cmd_main /home/gitster/w/build/git.c:984:19 #14 0x5615308dda0a in main /home/gitster/w/build/common-main.c:9:11 #15 0x7f051651bca7 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16 SUMMARY: AddressSanitizer: 421 byte(s) leaked in 2 allocation(s). Free the capablities data for the previous server before overwriting it with the next server to plug this leak. The added test fails without the freeing with SANITIZE=leak; I somehow couldn't get it fail reliably with SANITIZE=leak,address though. Signed-off-by: Junio C Hamano <[email protected]>

When pushing to a set of remotes using a nickname for the group, the client initializes the connection to each remote, talks to the remote and reads and parses capabilities line, and holds the capabilities in a file-scope static variable server_capabilities_v1. There are a few other such file-scope static variables, and these connections cannot be parallelized until they are refactored to a structure that keeps track of active connections. Which is *not* the theme of this patch ;-) For a single connection, the server_capabilities_v1 variable is initialized to NULL (at the program initialization), populated when we talk to the other side, used to look up capabilities of the other side possibly multiple times, and the memory is held by the variable until program exit, without leaking. When talking to multiple remotes, however, the server capabilities from the second connection overwrites without freeing the one from the first connection, which leaks. ==1080970==ERROR: LeakSanitizer: detected memory leaks Direct leak of 421 byte(s) in 2 object(s) allocated from: #0 0x5615305f849e in strdup (/home/gitster/g/git-jch/bin/bin/git+0x2b349e) (BuildId: 54d149994c9e85374831958f694bd0aa3b8b1e26) #1 0x561530e76cc4 in xstrdup /home/gitster/w/build/wrapper.c:43:14 #2 0x5615309cd7fa in process_capabilities /home/gitster/w/build/connect.c:243:27 #3 0x5615309cd502 in get_remote_heads /home/gitster/w/build/connect.c:366:4 #4 0x561530e2cb0b in handshake /home/gitster/w/build/transport.c:372:3 #5 0x561530e29ed7 in get_refs_via_connect /home/gitster/w/build/transport.c:398:9 #6 0x561530e26464 in transport_push /home/gitster/w/build/transport.c:1421:16 #7 0x561530800bec in push_with_options /home/gitster/w/build/builtin/push.c:387:8 #8 0x5615307ffb99 in do_push /home/gitster/w/build/builtin/push.c:442:7 #9 0x5615307fe926 in cmd_push /home/gitster/w/build/builtin/push.c:664:7 #10 0x56153065673f in run_builtin /home/gitster/w/build/git.c:506:11 #11 0x56153065342f in handle_builtin /home/gitster/w/build/git.c:779:9 #12 0x561530655b89 in run_argv /home/gitster/w/build/git.c:862:4 #13 0x561530652cba in cmd_main /home/gitster/w/build/git.c:984:19 #14 0x5615308dda0a in main /home/gitster/w/build/common-main.c:9:11 #15 0x7f051651bca7 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16 SUMMARY: AddressSanitizer: 421 byte(s) leaked in 2 allocation(s). Free the capablities data for the previous server before overwriting it with the next server to plug this leak. The added test fails without the freeing with SANITIZE=leak; I somehow couldn't get it fail reliably with SANITIZE=leak,address though. Signed-off-by: Junio C Hamano <[email protected]>

When performing auto-maintenance we check whether commit graphs need to be generated by counting the number of commits that are reachable by any reference, but not covered by a commit graph. This search is performed by iterating through all references and then doing a depth-first search until we have found enough commits that are not present in the commit graph. This logic has a memory leak though: Direct leak of 16 byte(s) in 1 object(s) allocated from: #0 0x55555562e433 in malloc (git+0xda433) #1 0x555555964322 in do_xmalloc ../wrapper.c:55:8 #2 0x5555559642e6 in xmalloc ../wrapper.c:76:9 #3 0x55555579bf29 in commit_list_append ../commit.c:1872:35 #4 0x55555569f160 in dfs_on_ref ../builtin/gc.c:1165:4 #5 0x5555558c33fd in do_for_each_ref_iterator ../refs/iterator.c:431:12 #6 0x5555558af520 in do_for_each_ref ../refs.c:1828:9 #7 0x5555558ac317 in refs_for_each_ref ../refs.c:1833:9 #8 0x55555569e207 in should_write_commit_graph ../builtin/gc.c:1188:11 #9 0x55555569c915 in maintenance_is_needed ../builtin/gc.c:3492:8 #10 0x55555569b76a in cmd_maintenance ../builtin/gc.c:3542:9 #11 0x55555575166a in run_builtin ../git.c:506:11 #12 0x5555557502f0 in handle_builtin ../git.c:779:9 #13 0x555555751127 in run_argv ../git.c:862:4 #14 0x55555575007b in cmd_main ../git.c:984:19 #15 0x5555557523aa in main ../common-main.c:9:11 #16 0x7ffff7a2a4d7 in __libc_start_call_main (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x2a4d7) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #17 0x7ffff7a2a59a in __libc_start_main@GLIBC_2.2.5 (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x2a59a) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #18 0x5555555f0934 in _start (git+0x9c934) The root cause of this memory leak is our use of `commit_list_append()`. This function expects as parameters the item to append and the _tail_ of the list to append. This tail will then be overwritten with the new tail of the list so that it can be used in subsequent calls. But we call it with `commit_list_append(parent->item, &stack)`, so we end up losing everything but the new item. This issue only surfaces when counting merge commits. Next to being a memory leak, it also shows that we're in fact miscounting as we only respect children of the last parent. All previous parents are discarded, so their children will be disregarded unless they are hit via another reference. While crafting a test case for the issue I was puzzled that I couldn't establish the proper border at which the auto-condition would be fulfilled. As it turns out, there's another bug: if an object is at the tip of any reference we don't mark it as seen. Consequently, if it is reachable via any other reference, we'd count that object twice. Fix both of these bugs so that we properly count objects without leaking any memory. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

It is possible to hit a memory leak when reading data from a submodule via git-grep(1): Direct leak of 192 byte(s) in 1 object(s) allocated from: #0 0x55555562e726 in calloc (git+0xda726) #1 0x555555964734 in xcalloc ../wrapper.c:154:8 #2 0x555555835136 in load_multi_pack_index_one ../midx.c:135:2 #3 0x555555834fd6 in load_multi_pack_index ../midx.c:382:6 #4 0x5555558365b6 in prepare_multi_pack_index_one ../midx.c:716:17 #5 0x55555586c605 in packfile_store_prepare ../packfile.c:1103:3 #6 0x55555586c90c in packfile_store_reprepare ../packfile.c:1118:2 #7 0x5555558546b3 in odb_reprepare ../odb.c:1106:2 #8 0x5555558539e4 in do_oid_object_info_extended ../odb.c:715:4 #9 0x5555558533d1 in odb_read_object_info_extended ../odb.c:862:8 #10 0x5555558540bd in odb_read_object ../odb.c:920:6 #11 0x55555580a330 in grep_source_load_oid ../grep.c:1934:12 #12 0x55555580a13a in grep_source_load ../grep.c:1986:10 #13 0x555555809103 in grep_source_is_binary ../grep.c:2014:7 #14 0x555555807574 in grep_source_1 ../grep.c:1625:8 #15 0x555555807322 in grep_source ../grep.c:1837:10 #16 0x5555556a5c58 in run ../builtin/grep.c:208:10 #17 0x55555562bb42 in void* ThreadStartFunc<false>(void*) lsan_interceptors.cpp.o #18 0x7ffff7a9a979 in start_thread (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x9a979) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) #19 0x7ffff7b22d2b in __GI___clone3 (/nix/store/xx7cm72qy2c0643cm1ipngd87aqwkcdp-glibc-2.40-66/lib/libc.so.6+0x122d2b) (BuildId: cddea92d6cba8333be952b5a02fd47d61054c5ab) The root caues of this leak is the way we set up and release the submodule: 1. We use `repo_submodule_init()` to initialize a new repository. This repository is stored in `repos_to_free`. 2. We now read data from the submodule repository. 3. We then call `repo_clear()` on the submodule repositories. 4. `repo_clear()` calls `odb_free()`. 5. `odb_free()` calls `odb_free_sources()` followed by `odb_close()`. The issue here is the 5th step: we call `odb_free_sources()` _before_ we call `odb_close()`. But `odb_free_sources()` already frees all sources, so the logic that closes them in `odb_close()` now becomes a no-op. As a consequence, we never explicitly close sources at all. Fix the leak by closing the store before we free the sources. Signed-off-by: Patrick Steinhardt <[email protected]> Signed-off-by: Junio C Hamano <[email protected]>

derrickstolee force-pushed the reach/refactor branch from 154bac6 to a60b701 Compare July 13, 2018 20:27

dscho mentioned this pull request Jul 16, 2018

PatchSeries: use merge base for the --base argument gitgitgadget/gitgitgadget#21

Merged

dscho force-pushed the pu branch 3 times, most recently from 88546d3 to 610a4cc Compare July 17, 2018 23:27

derrickstolee force-pushed the reach/refactor branch from a60b701 to abccb56 Compare July 18, 2018 19:41

dscho force-pushed the pu branch from 610a4cc to 1aaaa8c Compare July 18, 2018 22:57

dscho force-pushed the pu branch from 1aaaa8c to ebd3154 Compare July 19, 2018 21:57

derrickstolee added 14 commits July 20, 2018 10:15

commit.h: remove method declarations

ca88ec3

These methods are now declared in commit-reach.h. Remove them from commit.h and add new include statements in all files that require these declarations. Signed-off-by: Derrick Stolee <[email protected]>

upload-pack: refactor ok_to_give_up()

08dcd4e

In anticipation of consolidating all commit reachability algorithms, refactor ok_to_give_up() in order to allow splitting its logic into an external method. Signed-off-by: Derrick Stolee <[email protected]>

test-reach: test in_merge_bases

10bda49

Signed-off-by: Derrick Stolee <[email protected]>

test-reach: test reduce_heads

91a6297

Signed-off-by: Derrick Stolee <[email protected]>

gitgitgadget bot pushed a commit that referenced this pull request Aug 27, 2024

What's cooking (2024/08 #10)

9018121

gitgitgadget bot pushed a commit that referenced this pull request Sep 25, 2024

What's cooking (2024/09 #10)

4e49940

gitgitgadget bot pushed a commit that referenced this pull request Oct 22, 2024

What's cooking (2024/10 #10)

d486550

gitgitgadget bot pushed a commit that referenced this pull request Nov 28, 2024

What's cooking (2024/11 #10)

c8d5b50

gitgitgadget bot pushed a commit that referenced this pull request Dec 28, 2024

What's cooking (2024/12 #10)

ecac596

gitgitgadget bot pushed a commit that referenced this pull request Aug 22, 2025

What's cooking (2025/08 #10)

dc4cc3d

gitgitgadget bot pushed a commit that referenced this pull request Sep 29, 2025

What's cooking (2025/09 #10)

ff31f76

gitgitgadget bot pushed a commit that referenced this pull request Oct 30, 2025

What's cooking (2025/10 #10)

670511c

gitgitgadget bot pushed a commit that referenced this pull request Dec 1, 2025

What's cooking (2025/11 #10)

72582ff

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Consolidate reachability logic #10

Consolidate reachability logic #10

Uh oh!

derrickstolee commented Jul 13, 2018 •

edited

Loading

Uh oh!

derrickstolee commented Jul 13, 2018

Uh oh!

gitgitgadget bot commented Jul 13, 2018

Uh oh!

derrickstolee commented Jul 16, 2018

Uh oh!

gitgitgadget bot commented Jul 16, 2018

Uh oh!

derrickstolee commented Jul 16, 2018

Uh oh!

gitgitgadget bot commented Jul 16, 2018

Uh oh!

dscho commented Jul 16, 2018

Uh oh!

dscho commented Jul 19, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Consolidate reachability logic #10

Consolidate reachability logic #10

Uh oh!

Conversation

derrickstolee commented Jul 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

derrickstolee commented Jul 13, 2018

Uh oh!

gitgitgadget bot commented Jul 13, 2018

Uh oh!

derrickstolee commented Jul 16, 2018

Uh oh!

gitgitgadget bot commented Jul 16, 2018

Uh oh!

derrickstolee commented Jul 16, 2018

Uh oh!

gitgitgadget bot commented Jul 16, 2018

Uh oh!

dscho commented Jul 16, 2018

Uh oh!

dscho commented Jul 19, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

derrickstolee commented Jul 13, 2018 •

edited

Loading