git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
* [INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all?
@ 2022-09-20 19:27 John Cai
  2022-09-20 20:41 ` Jeff King
  0 siblings, 1 reply; 10+ messages in thread
From: John Cai @ 2022-09-20 19:27 UTC (permalink / raw)
  To: git; +Cc: Christian Couder

Hi everyone,

I would love your thoughts about something I'm noticing in git fsck
--connectivity-only. I noticed that for large repositories, this operation can
take up alot of memory.

Here at GitLab we are exploring using `git rev-list --all --objects` as a proxy
for checking connectivity. In doing so, I noticed `git fsck --connectivity-only`
is much more expensive than `git rev-list --all --objects`.

Using Valgrind, here are some memory profile results from running both on the
linux repo:

`git fsck --connectivity-only`:

    GB
1.916^                                                                       :
     |                                                                @@:@@:#:
     |                                                         :::@@:@@@:@@:#:
     |                                                  :::@::@:::@@:@@@:@@:#:
     |                                           :::@@@@:: @::@:::@@:@@@:@@:#:
     |                                   @@::::::: :@ @@:: @::@:::@@:@@@:@@:#:
     |                            :::::::@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     |                     ::::@@::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     |              ::::::@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     |        :::::::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     |   ::::::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | ::::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
     | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:
   0 +----------------------------------------------------------------------->Gi
     0                                                                   233.7


`git rev-list --all --objects`:

    MB
979.8^                                                                   #
     |                                                                   #
     |                                                                   #
     |                                                                   #::::
     |                                                                   #::::
     |                                                                   #::::
     |                                                             @@@:@@#::::
     |                                                    ::@@@:@@@@@@:@@#::::
     |                                           ::::@::::::@@@:@@@@@@:@@#::::
     |                             @@   :::::::::: ::@::::::@@@:@@@@@@:@@#::::
     |                             @ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |                          @@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |                ::::@::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |          @@::::::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |          @ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |          @ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |        :@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |       ::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |    :::::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
     |  :::: ::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::
   0 +----------------------------------------------------------------------->Gi
     0                                                                   245.5

As we can see, `git fsck` uses about twice the amount of memory as `git
rev-list`, which was a bit surprising to me.

Digging in a bit, here is the stack trace analysis:

`git fsck --connectivity-only`:

98.37% (2,008,484,573B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->84.04% (1,715,907,794B) 0x35779F: do_xmalloc (wrapper.c:51)
| ->50.73% (1,035,816,788B) 0x35781F: do_xmallocz.part.0 (wrapper.c:85)
| | ->40.48% (826,445,820B) 0x2B2447: unpack_compressed_entry (packfile.c:1601)
| | | ->40.48% (826,445,820B) 0x2B46AB: unpack_entry (packfile.c:1768)
| | | | ->40.48% (826,445,820B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)
| | | |   ->40.48% (826,445,820B) 0x2B4A23: packed_object_info (packfile.c:1516)
| | | |     ->40.48% (826,445,820B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
| | | |       ->40.48% (826,445,820B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
| | | |         ->40.48% (826,445,820B) 0x29EDC3: read_object (object-file.c:1671)
| | | |           ->40.48% (826,445,820B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
| | | |             ->40.12% (819,056,147B) 0x2143BB: repo_read_object_file (object-store.h:253)
| | | |             | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:511)
| | | |             |   ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:495)
| | | |             |     ->40.12% (819,056,147B) 0x25A747: repo_parse_commit (commit.h:90)
| | | |             |       ->40.12% (819,056,147B) 0x25A747: fsck_walk_commit (fsck.c:355)
| | | |             |         ->40.12% (819,056,147B) 0x25A747: fsck_walk (fsck.c:441)
| | | |             |           ->40.12% (819,056,147B) 0x16C7BB: traverse_one_object (fsck.c:175)
| | | |             |             ->40.12% (819,056,147B) 0x16C7BB: traverse_reachable (fsck.c:192)
| | | |             |               ->40.12% (819,056,147B) 0x16C7BB: check_connectivity (fsck.c:363)
| | | |             |                 ->40.12% (819,056,147B) 0x16C7BB: cmd_fsck (fsck.c:982)
| | | |             |                   ->40.12% (819,056,147B) 0x128007: run_builtin (git.c:466)
| | | |             |                     ->40.12% (819,056,147B) 0x128007: handle_builtin (git.c:720)
| | | |             |                       ->40.12% (819,056,147B) 0x129127: cmd_main (git.c:888)
| | | |             |                         ->40.12% (819,056,147B) 0x127B67: main (common-main.c:56)
| | | |             |
| | | |             ->00.36% (7,389,673B) in 1+ places, all below ms_print's threshold (01.00%)
| | | |
| | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| | |
| | ->08.61% (175,870,114B) 0x2B9DC3: patch_delta (patch-delta.c:36)
| | | ->08.61% (175,870,114B) 0x2B42EB: unpack_entry (packfile.c:1829)
| | |   ->08.61% (175,870,114B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)
| | |     ->08.61% (175,870,114B) 0x2B4A23: packed_object_info (packfile.c:1516)
| | |       ->08.61% (175,870,114B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
| | |         ->08.61% (175,870,114B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
| | |           ->08.61% (175,870,114B) 0x29EDC3: read_object (object-file.c:1671)
| | |             ->08.61% (175,870,114B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
| | |               ->04.52% (92,219,588B) 0x3461CB: repo_read_object_file (object-store.h:253)
| | |               | ->04.52% (92,219,588B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)
| | |               |   ->04.52% (92,219,588B) 0x25A4EB: parse_tree (tree.h:24)
| | |               |     ->04.52% (92,219,588B) 0x25A4EB: fsck_walk_tree (fsck.c:307)
| | |               |       ->04.52% (92,219,588B) 0x25A4EB: fsck_walk (fsck.c:439)
| | |               |         ->04.52% (92,219,588B) 0x16C7BB: traverse_one_object (fsck.c:175)
| | |               |           ->04.52% (92,219,588B) 0x16C7BB: traverse_reachable (fsck.c:192)
| | |               |             ->04.52% (92,219,588B) 0x16C7BB: check_connectivity (fsck.c:363)
| | |               |               ->04.52% (92,219,588B) 0x16C7BB: cmd_fsck (fsck.c:982)
| | |               |                 ->04.52% (92,219,588B) 0x128007: run_builtin (git.c:466)
| | |               |                   ->04.52% (92,219,588B) 0x128007: handle_builtin (git.c:720)
| | |               |                     ->04.52% (92,219,588B) 0x129127: cmd_main (git.c:888)
| | |               |                       ->04.52% (92,219,588B) 0x127B67: main (common-main.c:56)
| | |               |
| | |               ->04.10% (83,650,526B) 0x2143BB: repo_read_object_file (object-store.h:253)
| | |               | ->04.10% (83,650,526B) 0x2143BB: repo_parse_commit_internal (commit.c:511)
| | |               |   ->04.10% (83,650,526B) 0x2143BB: repo_parse_commit_internal (commit.c:495)
| | |               |     ->04.10% (83,650,526B) 0x25A747: repo_parse_commit (commit.h:90)
| | |               |       ->04.10% (83,650,526B) 0x25A747: fsck_walk_commit (fsck.c:355)
| | |               |         ->04.10% (83,650,526B) 0x25A747: fsck_walk (fsck.c:441)
| | |               |           ->04.10% (83,650,526B) 0x16C7BB: traverse_one_object (fsck.c:175)
| | |               |             ->04.10% (83,650,526B) 0x16C7BB: traverse_reachable (fsck.c:192)
| | |               |               ->04.10% (83,650,526B) 0x16C7BB: check_connectivity (fsck.c:363)
| | |               |                 ->04.10% (83,650,526B) 0x16C7BB: cmd_fsck (fsck.c:982)
| | |               |                   ->04.10% (83,650,526B) 0x128007: run_builtin (git.c:466)
| | |               |                     ->04.10% (83,650,526B) 0x128007: handle_builtin (git.c:720)
| | |               |                       ->04.10% (83,650,526B) 0x129127: cmd_main (git.c:888)
| | |               |                         ->04.10% (83,650,526B) 0x127B67: main (common-main.c:56)
| | |               |
| | |               ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| | |
| | ->01.64% (33,500,854B) 0x357903: do_xmallocz (wrapper.c:83)
| | | ->01.64% (33,500,854B) 0x357903: xmallocz (wrapper.c:93)
| | |   ->01.64% (33,500,854B) 0x357903: xmemdupz (wrapper.c:109)
| | |     ->01.64% (33,493,416B) 0x2B476F: cache_or_unpack_entry (packfile.c:1444)
| | |     | ->01.64% (33,493,416B) 0x2B476F: packed_object_info (packfile.c:1516)
| | |     |   ->01.64% (33,493,416B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
| | |     |     ->01.64% (33,493,416B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
| | |     |       ->01.64% (33,493,416B) 0x29EDC3: read_object (object-file.c:1671)
| | |     |         ->01.64% (33,493,416B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
| | |     |           ->01.64% (33,438,291B) 0x2143BB: repo_read_object_file (object-store.h:253)
| | |     |           | ->01.64% (33,438,291B) 0x2143BB: repo_parse_commit_internal (commit.c:511)
| | |     |           |   ->01.64% (33,438,291B) 0x2143BB: repo_parse_commit_internal (commit.c:495)
| | |     |           |     ->01.64% (33,438,291B) 0x25A747: repo_parse_commit (commit.h:90)
| | |     |           |       ->01.64% (33,438,291B) 0x25A747: fsck_walk_commit (fsck.c:355)
| | |     |           |         ->01.64% (33,438,291B) 0x25A747: fsck_walk (fsck.c:441)
| | |     |           |           ->01.64% (33,438,291B) 0x16C7BB: traverse_one_object (fsck.c:175)
| | |     |           |             ->01.64% (33,438,291B) 0x16C7BB: traverse_reachable (fsck.c:192)
| | |     |           |               ->01.64% (33,438,291B) 0x16C7BB: check_connectivity (fsck.c:363)
| | |     |           |                 ->01.64% (33,438,291B) 0x16C7BB: cmd_fsck (fsck.c:982)
| | |     |           |                   ->01.64% (33,438,291B) 0x128007: run_builtin (git.c:466)
| | |     |           |                     ->01.64% (33,438,291B) 0x128007: handle_builtin (git.c:720)
| | |     |           |                       ->01.64% (33,438,291B) 0x129127: cmd_main (git.c:888)
| | |     |           |                         ->01.64% (33,438,291B) 0x127B67: main (common-main.c:56)
| | |     |           |
| | |     |           ->00.00% (55,125B) in 1+ places, all below ms_print's threshold (01.00%)
| | |     |
| | |     ->00.00% (7,438B) in 1+ places, all below ms_print's threshold (01.00%)
| | |
| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->31.69% (646,963,200B) 0x369A07: alloc_node (alloc.c:59)
| | ->31.69% (646,963,200B) 0x369A07: alloc_object_node (alloc.c:95)
| |   ->31.69% (646,963,200B) 0x2A3A0F: lookup_unknown_object (object.c:184)
| |     ->31.69% (646,963,200B) 0x16B19B: mark_object_for_connectivity (fsck.c:800)
| |       ->31.69% (646,963,200B) 0x16B19B: mark_packed_for_connectivity (fsck.c:817)
| |         ->31.69% (646,963,200B) 0x2B50AB: for_each_object_in_pack (packfile.c:2176)
| |           ->31.69% (646,963,200B) 0x2B5217: for_each_packed_object (packfile.c:2207)
| |             ->31.69% (646,963,200B) 0x16C6A3: cmd_fsck (fsck.c:881)
| |               ->31.69% (646,963,200B) 0x128007: run_builtin (git.c:466)
| |                 ->31.69% (646,963,200B) 0x128007: handle_builtin (git.c:720)
| |                   ->31.69% (646,963,200B) 0x129127: cmd_main (git.c:888)
| |                     ->31.69% (646,963,200B) 0x127B67: main (common-main.c:56)
| |
| ->01.62% (33,127,806B) in 14 places, all below massif's threshold (1.00%)
|
->14.12% (288,287,504B) 0x357A37: xcalloc (wrapper.c:150)
| ->13.15% (268,435,456B) 0x2A386B: grow_object_hash (object.c:130)
| | ->13.15% (268,435,456B) 0x2A386B: create_object (object.c:152)
| |   ->13.15% (268,435,456B) 0x16B19B: mark_object_for_connectivity (fsck.c:800)
| |     ->13.15% (268,435,456B) 0x16B19B: mark_packed_for_connectivity (fsck.c:817)
| |       ->13.15% (268,435,456B) 0x2B50AB: for_each_object_in_pack (packfile.c:2176)
| |         ->13.15% (268,435,456B) 0x2B5217: for_each_packed_object (packfile.c:2207)
| |           ->13.15% (268,435,456B) 0x16C6A3: cmd_fsck (fsck.c:881)
| |             ->13.15% (268,435,456B) 0x128007: run_builtin (git.c:466)
| |               ->13.15% (268,435,456B) 0x128007: handle_builtin (git.c:720)
| |                 ->13.15% (268,435,456B) 0x129127: cmd_main (git.c:888)
| |                   ->13.15% (268,435,456B) 0x127B67: main (common-main.c:56)
| |
| ->00.97% (19,852,048B) in 1+ places, all below ms_print's threshold (01.00%)
|
->00.21% (4,289,275B) in 1+ places, all below ms_print's threshold (01.00%)

`git rev-list --all --objects`:

99.88% (1,026,125,720B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->54.04% (555,159,796B) 0x35779F: do_xmalloc (wrapper.c:51)
| ->27.44% (281,960,448B) 0x369803: alloc_node (alloc.c:59)
| | ->27.44% (281,960,448B) 0x369803: alloc_tree_node (alloc.c:81)
| |   ->27.44% (281,960,448B) 0x3462DF: lookup_tree (tree.c:109)
| |     ->27.44% (281,960,448B) 0x3462DF: lookup_tree (tree.c:105)
| |       ->21.38% (219,684,864B) 0x270707: process_tree_contents (list-objects.c:142)
| |       | ->21.38% (219,684,864B) 0x270707: process_tree (list-objects.c:221)
| |       |   ->15.11% (155,287,552B) 0x27072B: process_tree_contents (list-objects.c:149)
| |       |   | ->15.11% (155,287,552B) 0x27072B: process_tree (list-objects.c:221)
| |       |   |   ->08.64% (88,768,512B) 0x27072B: process_tree_contents (list-objects.c:149)
| |       |   |   | ->08.64% (88,768,512B) 0x27072B: process_tree (list-objects.c:221)
| |       |   |   |   ->04.77% (49,029,120B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |       |   |   |   | ->04.77% (49,029,120B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |       |   |   |   |   ->04.77% (49,029,120B) 0x270D5B: do_traverse (list-objects.c:432)
| |       |   |   |   |     ->04.77% (49,029,120B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |       |   |   |   |       ->04.77% (49,029,120B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       |   |   |   |         ->04.77% (49,029,120B) 0x128007: run_builtin (git.c:466)
| |       |   |   |   |           ->04.77% (49,029,120B) 0x128007: handle_builtin (git.c:720)
| |       |   |   |   |             ->04.77% (49,029,120B) 0x129127: cmd_main (git.c:888)
| |       |   |   |   |               ->04.77% (49,029,120B) 0x127B67: main (common-main.c:56)
| |       |   |   |   |
| |       |   |   |   ->03.87% (39,739,392B) 0x27072B: process_tree_contents (list-objects.c:149)
| |       |   |   |     ->03.87% (39,739,392B) 0x27072B: process_tree (list-objects.c:221)
| |       |   |   |       ->02.45% (25,174,016B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |       |   |   |       | ->02.45% (25,174,016B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |       |   |   |       |   ->02.45% (25,174,016B) 0x270D5B: do_traverse (list-objects.c:432)
| |       |   |   |       |     ->02.45% (25,174,016B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |       |   |   |       |       ->02.45% (25,174,016B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       |   |   |       |         ->02.45% (25,174,016B) 0x128007: run_builtin (git.c:466)
| |       |   |   |       |           ->02.45% (25,174,016B) 0x128007: handle_builtin (git.c:720)
| |       |   |   |       |             ->02.45% (25,174,016B) 0x129127: cmd_main (git.c:888)
| |       |   |   |       |               ->02.45% (25,174,016B) 0x127B67: main (common-main.c:56)
| |       |   |   |       |
| |       |   |   |       ->01.42% (14,565,376B) 0x27072B: process_tree_contents (list-objects.c:149)
| |       |   |   |         ->01.42% (14,565,376B) 0x27072B: process_tree (list-objects.c:221)
| |       |   |   |           ->01.00% (10,321,920B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |       |   |   |           | ->01.00% (10,321,920B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |       |   |   |           |   ->01.00% (10,321,920B) 0x270D5B: do_traverse (list-objects.c:432)
| |       |   |   |           |     ->01.00% (10,321,920B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |       |   |   |           |       ->01.00% (10,321,920B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       |   |   |           |         ->01.00% (10,321,920B) 0x128007: run_builtin (git.c:466)
| |       |   |   |           |           ->01.00% (10,321,920B) 0x128007: handle_builtin (git.c:720)
| |       |   |   |           |             ->01.00% (10,321,920B) 0x129127: cmd_main (git.c:888)
| |       |   |   |           |               ->01.00% (10,321,920B) 0x127B67: main (common-main.c:56)
| |       |   |   |           |
| |       |   |   |           ->00.41% (4,243,456B) in 1+ places, all below ms_print's threshold (01.00%)
| |       |   |   |
| |       |   |   ->06.47% (66,519,040B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |       |   |     ->06.47% (66,519,040B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |       |   |       ->06.47% (66,519,040B) 0x270D5B: do_traverse (list-objects.c:432)
| |       |   |         ->06.47% (66,519,040B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |       |   |           ->06.47% (66,519,040B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       |   |             ->06.47% (66,519,040B) 0x128007: run_builtin (git.c:466)
| |       |   |               ->06.47% (66,519,040B) 0x128007: handle_builtin (git.c:720)
| |       |   |                 ->06.47% (66,519,040B) 0x129127: cmd_main (git.c:888)
| |       |   |                   ->06.47% (66,519,040B) 0x127B67: main (common-main.c:56)
| |       |   |
| |       |   ->06.27% (64,397,312B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |       |     ->06.27% (64,397,312B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |       |       ->06.27% (64,397,312B) 0x270D5B: do_traverse (list-objects.c:432)
| |       |         ->06.27% (64,397,312B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |       |           ->06.27% (64,397,312B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       |             ->06.27% (64,397,312B) 0x128007: run_builtin (git.c:466)
| |       |               ->06.27% (64,397,312B) 0x128007: handle_builtin (git.c:720)
| |       |                 ->06.27% (64,397,312B) 0x129127: cmd_main (git.c:888)
| |       |                   ->06.27% (64,397,312B) 0x127B67: main (common-main.c:56)
| |       |
| |       ->06.06% (62,275,584B) 0x213F93: parse_commit_buffer (commit.c:440)
| |         ->06.06% (62,218,240B) 0x2143E7: repo_parse_commit_internal (commit.c:522)
| |         | ->06.06% (62,218,240B) 0x2143E7: repo_parse_commit_internal (commit.c:495)
| |         |   ->06.06% (62,218,240B) 0x2FC77B: process_parents (revision.c:1169)
| |         |     ->06.06% (62,218,240B) 0x2FFEBB: get_revision_1 (revision.c:4080)
| |         |       ->06.06% (62,218,240B) 0x3000EB: get_revision_internal (revision.c:4188)
| |         |         ->06.06% (62,218,240B) 0x30026F: get_revision (revision.c:4266)
| |         |           ->06.06% (62,218,240B) 0x270C63: do_traverse (list-objects.c:397)
| |         |             ->06.06% (62,218,240B) 0x270C63: traverse_commit_list_filtered (list-objects.c:453)
| |         |               ->06.06% (62,218,240B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |         |                 ->06.06% (62,218,240B) 0x128007: run_builtin (git.c:466)
| |         |                   ->06.06% (62,218,240B) 0x128007: handle_builtin (git.c:720)
| |         |                     ->06.06% (62,218,240B) 0x129127: cmd_main (git.c:888)
| |         |                       ->06.06% (62,218,240B) 0x127B67: main (common-main.c:56)
| |         |
| |         ->00.01% (57,344B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->09.80% (100,703,562B) 0x35781F: do_xmallocz.part.0 (wrapper.c:85)
| | ->09.47% (97,307,344B) 0x2B9DC3: patch_delta (patch-delta.c:36)
| | | ->09.47% (97,307,344B) 0x2B42EB: unpack_entry (packfile.c:1829)
| | |   ->09.47% (97,307,344B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)
| | |     ->09.47% (97,307,344B) 0x2B4A23: packed_object_info (packfile.c:1516)
| | |       ->09.47% (97,307,344B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
| | |         ->09.47% (97,307,344B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
| | |           ->09.47% (97,307,344B) 0x29EDC3: read_object (object-file.c:1671)
| | |             ->09.47% (97,307,344B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
| | |               ->09.47% (97,307,344B) 0x3461CB: repo_read_object_file (object-store.h:253)
| | |               | ->09.47% (97,307,344B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)
| | |               |   ->09.47% (97,307,344B) 0x2703EF: process_tree (list-objects.c:188)
| | |               |     ->09.07% (93,167,206B) 0x27072B: process_tree_contents (list-objects.c:149)
| | |               |     | ->09.07% (93,167,206B) 0x27072B: process_tree (list-objects.c:221)
| | |               |     |   ->07.49% (76,907,030B) 0x27072B: process_tree_contents (list-objects.c:149)
| | |               |     |   | ->07.49% (76,907,030B) 0x27072B: process_tree (list-objects.c:221)
| | |               |     |   |   ->05.69% (58,476,176B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| | |               |     |   |   | ->05.69% (58,476,176B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| | |               |     |   |   |   ->05.69% (58,476,176B) 0x270D5B: do_traverse (list-objects.c:432)
| | |               |     |   |   |     ->05.69% (58,476,176B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| | |               |     |   |   |       ->05.69% (58,476,176B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| | |               |     |   |   |         ->05.69% (58,476,176B) 0x128007: run_builtin (git.c:466)
| | |               |     |   |   |           ->05.69% (58,476,176B) 0x128007: handle_builtin (git.c:720)
| | |               |     |   |   |             ->05.69% (58,476,176B) 0x129127: cmd_main (git.c:888)
| | |               |     |   |   |               ->05.69% (58,476,176B) 0x127B67: main (common-main.c:56)
| | |               |     |   |   |
| | |               |     |   |   ->01.79% (18,430,854B) 0x27072B: process_tree_contents (list-objects.c:149)
| | |               |     |   |     ->01.79% (18,430,854B) 0x27072B: process_tree (list-objects.c:221)
| | |               |     |   |       ->01.26% (12,951,424B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| | |               |     |   |       | ->01.26% (12,951,424B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| | |               |     |   |       |   ->01.26% (12,951,424B) 0x270D5B: do_traverse (list-objects.c:432)
| | |               |     |   |       |     ->01.26% (12,951,424B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| | |               |     |   |       |       ->01.26% (12,951,424B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| | |               |     |   |       |         ->01.26% (12,951,424B) 0x128007: run_builtin (git.c:466)
| | |               |     |   |       |           ->01.26% (12,951,424B) 0x128007: handle_builtin (git.c:720)
| | |               |     |   |       |             ->01.26% (12,951,424B) 0x129127: cmd_main (git.c:888)
| | |               |     |   |       |               ->01.26% (12,951,424B) 0x127B67: main (common-main.c:56)
| | |               |     |   |       |
| | |               |     |   |       ->00.53% (5,479,430B) in 1+ places, all below ms_print's threshold (01.00%)
| | |               |     |   |
| | |               |     |   ->01.58% (16,260,176B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| | |               |     |     ->01.58% (16,260,176B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| | |               |     |       ->01.58% (16,260,176B) 0x270D5B: do_traverse (list-objects.c:432)
| | |               |     |         ->01.58% (16,260,176B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| | |               |     |           ->01.58% (16,260,176B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| | |               |     |             ->01.58% (16,260,176B) 0x128007: run_builtin (git.c:466)
| | |               |     |               ->01.58% (16,260,176B) 0x128007: handle_builtin (git.c:720)
| | |               |     |                 ->01.58% (16,260,176B) 0x129127: cmd_main (git.c:888)
| | |               |     |                   ->01.58% (16,260,176B) 0x127B67: main (common-main.c:56)
| | |               |     |
| | |               |     ->00.40% (4,140,138B) in 1+ places, all below ms_print's threshold (01.00%)
| | |               |
| | |               ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| | |
| | ->00.33% (3,396,218B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->08.68% (89,210,880B) 0x36970B: alloc_node (alloc.c:59)
| | ->08.68% (89,210,880B) 0x36970B: alloc_blob_node (alloc.c:74)
| |   ->08.68% (89,210,880B) 0x1FEE17: lookup_blob (blob.c:12)
| |     ->08.68% (89,210,880B) 0x27066F: process_tree_contents (list-objects.c:155)
| |       ->08.68% (89,210,880B) 0x27066F: process_tree (list-objects.c:221)
| |         ->08.59% (88,227,840B) 0x27072B: process_tree_contents (list-objects.c:149)
| |         | ->08.59% (88,227,840B) 0x27072B: process_tree (list-objects.c:221)
| |         |   ->08.24% (84,623,360B) 0x27072B: process_tree_contents (list-objects.c:149)
| |         |   | ->08.24% (84,623,360B) 0x27072B: process_tree (list-objects.c:221)
| |         |   |   ->05.85% (60,088,320B) 0x27072B: process_tree_contents (list-objects.c:149)
| |         |   |   | ->05.85% (60,088,320B) 0x27072B: process_tree (list-objects.c:221)
| |         |   |   |   ->03.17% (32,604,160B) 0x27072B: process_tree_contents (list-objects.c:149)
| |         |   |   |   | ->03.17% (32,604,160B) 0x27072B: process_tree (list-objects.c:221)
| |         |   |   |   |   ->01.92% (19,742,720B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |         |   |   |   |   | ->01.92% (19,742,720B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |         |   |   |   |   |   ->01.92% (19,742,720B) 0x270D5B: do_traverse (list-objects.c:432)
| |         |   |   |   |   |     ->01.92% (19,742,720B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |         |   |   |   |   |       ->01.92% (19,742,720B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |         |   |   |   |   |         ->01.92% (19,742,720B) 0x128007: run_builtin (git.c:466)
| |         |   |   |   |   |           ->01.92% (19,742,720B) 0x128007: handle_builtin (git.c:720)
| |         |   |   |   |   |             ->01.92% (19,742,720B) 0x129127: cmd_main (git.c:888)
| |         |   |   |   |   |               ->01.92% (19,742,720B) 0x127B67: main (common-main.c:56)
| |         |   |   |   |   |
| |         |   |   |   |   ->01.25% (12,861,440B) 0x27072B: process_tree_contents (list-objects.c:149)
| |         |   |   |   |     ->01.25% (12,861,440B) 0x27072B: process_tree (list-objects.c:221)
| |         |   |   |   |       ->01.25% (12,861,440B) in 2 places, all below massif's threshold (1.00%)
| |         |   |   |   |
| |         |   |   |   ->02.68% (27,484,160B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |         |   |   |     ->02.68% (27,484,160B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |         |   |   |       ->02.68% (27,484,160B) 0x270D5B: do_traverse (list-objects.c:432)
| |         |   |   |         ->02.68% (27,484,160B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |         |   |   |           ->02.68% (27,484,160B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |         |   |   |             ->02.68% (27,484,160B) 0x128007: run_builtin (git.c:466)
| |         |   |   |               ->02.68% (27,484,160B) 0x128007: handle_builtin (git.c:720)
| |         |   |   |                 ->02.68% (27,484,160B) 0x129127: cmd_main (git.c:888)
| |         |   |   |                   ->02.68% (27,484,160B) 0x127B67: main (common-main.c:56)
| |         |   |   |
| |         |   |   ->02.39% (24,535,040B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |         |   |     ->02.39% (24,535,040B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |         |   |       ->02.39% (24,535,040B) 0x270D5B: do_traverse (list-objects.c:432)
| |         |   |         ->02.39% (24,535,040B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |         |   |           ->02.39% (24,535,040B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |         |   |             ->02.39% (24,535,040B) 0x128007: run_builtin (git.c:466)
| |         |   |               ->02.39% (24,535,040B) 0x128007: handle_builtin (git.c:720)
| |         |   |                 ->02.39% (24,535,040B) 0x129127: cmd_main (git.c:888)
| |         |   |                   ->02.39% (24,535,040B) 0x127B67: main (common-main.c:56)
| |         |   |
| |         |   ->00.35% (3,604,480B) in 1+ places, all below ms_print's threshold (01.00%)
| |         |
| |         ->00.10% (983,040B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->07.87% (80,879,616B) 0x369B27: alloc_node (alloc.c:59)
| | ->07.87% (80,879,616B) 0x369B27: alloc_commit_node (alloc.c:119)
| |   ->07.87% (80,879,616B) 0x2133B7: lookup_commit (commit.c:66)
| |     ->07.87% (80,879,616B) 0x2133B7: lookup_commit (commit.c:62)
| |       ->07.87% (80,805,888B) 0x21411B: parse_commit_buffer (commit.c:466)
| |       | ->07.86% (80,732,160B) 0x2143E7: repo_parse_commit_internal (commit.c:522)
| |       | | ->07.86% (80,732,160B) 0x2143E7: repo_parse_commit_internal (commit.c:495)
| |       | |   ->07.86% (80,732,160B) 0x2FC77B: process_parents (revision.c:1169)
| |       | |     ->07.86% (80,732,160B) 0x2FFEBB: get_revision_1 (revision.c:4080)
| |       | |       ->07.86% (80,732,160B) 0x3000EB: get_revision_internal (revision.c:4188)
| |       | |         ->07.86% (80,732,160B) 0x30026F: get_revision (revision.c:4266)
| |       | |           ->07.86% (80,732,160B) 0x270C63: do_traverse (list-objects.c:397)
| |       | |             ->07.86% (80,732,160B) 0x270C63: traverse_commit_list_filtered (list-objects.c:453)
| |       | |               ->07.86% (80,732,160B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |       | |                 ->07.86% (80,732,160B) 0x128007: run_builtin (git.c:466)
| |       | |                   ->07.86% (80,732,160B) 0x128007: handle_builtin (git.c:720)
| |       | |                     ->07.86% (80,732,160B) 0x129127: cmd_main (git.c:888)
| |       | |                       ->07.86% (80,732,160B) 0x127B67: main (common-main.c:56)
| |       | |
| |       | ->00.01% (73,728B) in 1+ places, all below ms_print's threshold (01.00%)
| |       |
| |       ->00.01% (73,728B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.23% (2,405,290B) in 1+ places, all below ms_print's threshold (01.00%)
|
->39.29% (403,708,926B) 0x357A37: xcalloc (wrapper.c:150)
| ->39.19% (402,653,184B) 0x2A386B: grow_object_hash (object.c:130)
| | ->39.19% (402,653,184B) 0x2A386B: create_object (object.c:152)
| |   ->39.19% (402,653,184B) 0x270707: process_tree_contents (list-objects.c:142)
| |   | ->39.19% (402,653,184B) 0x270707: process_tree (list-objects.c:221)
| |   |   ->26.13% (268,435,456B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |   |   | ->26.13% (268,435,456B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |   |   |   ->26.13% (268,435,456B) 0x270D5B: do_traverse (list-objects.c:432)
| |   |   |     ->26.13% (268,435,456B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |   |   |       ->26.13% (268,435,456B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |   |   |         ->26.13% (268,435,456B) 0x128007: run_builtin (git.c:466)
| |   |   |           ->26.13% (268,435,456B) 0x128007: handle_builtin (git.c:720)
| |   |   |             ->26.13% (268,435,456B) 0x129127: cmd_main (git.c:888)
| |   |   |               ->26.13% (268,435,456B) 0x127B67: main (common-main.c:56)
| |   |   |
| |   |   ->13.06% (134,217,728B) 0x27072B: process_tree_contents (list-objects.c:149)
| |   |     ->13.06% (134,217,728B) 0x27072B: process_tree (list-objects.c:221)
| |   |       ->13.06% (134,217,728B) 0x27072B: process_tree_contents (list-objects.c:149)
| |   |         ->13.06% (134,217,728B) 0x27072B: process_tree (list-objects.c:221)
| |   |           ->13.06% (134,217,728B) 0x2708D3: traverse_non_commits (list-objects.c:378)
| |   |             ->13.06% (134,217,728B) 0x2708D3: traverse_non_commits (list-objects.c:357)
| |   |               ->13.06% (134,217,728B) 0x270D5B: do_traverse (list-objects.c:432)
| |   |                 ->13.06% (134,217,728B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)
| |   |                   ->13.06% (134,217,728B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |   |                     ->13.06% (134,217,728B) 0x128007: run_builtin (git.c:466)
| |   |                       ->13.06% (134,217,728B) 0x128007: handle_builtin (git.c:720)
| |   |                         ->13.06% (134,217,728B) 0x129127: cmd_main (git.c:888)
| |   |                           ->13.06% (134,217,728B) 0x127B67: main (common-main.c:56)
| |   |
| |   ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.10% (1,055,742B) in 1+ places, all below ms_print's threshold (01.00%)
|
->06.54% (67,228,381B) 0x3579CF: xrealloc (wrapper.c:136)
| ->06.53% (67,106,816B) 0x2A406B: add_object_array_with_path (object.c:353)
| | ->06.53% (67,106,816B) 0x2F8427: add_pending_object_with_path (revision.c:343)
| |   ->06.53% (67,106,816B) 0x270D17: add_pending_tree (list-objects.c:354)
| |   | ->06.53% (67,106,816B) 0x270D17: do_traverse (list-objects.c:413)
| |   |   ->06.53% (67,106,816B) 0x270D17: traverse_commit_list_filtered (list-objects.c:453)
| |   |     ->06.53% (67,106,816B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)
| |   |       ->06.53% (67,106,816B) 0x128007: run_builtin (git.c:466)
| |   |         ->06.53% (67,106,816B) 0x128007: handle_builtin (git.c:720)
| |   |           ->06.53% (67,106,816B) 0x129127: cmd_main (git.c:888)
| |   |             ->06.53% (67,106,816B) 0x127B67: main (common-main.c:56)
| |   |
| |   ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
| |
| ->00.01% (121,565B) in 1+ places, all below ms_print's threshold (01.00%)
|
->00.00% (28,617B) in 1+ places, all below ms_print's threshold (01.00%)

One observation is that `git-fsck` seems to use up alot more memory in calling
unpack_compressed_entry() than `git-rev-list` does.

But, not having delved too deeply into the code, I wanted to ask the list if
anything jumps out as to why `git-fsck` consumes so much more memory than
`git-rev-list`--perhaps there is opportunity for improvement/optimization?

thanks!
John

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all?
  2022-09-20 19:27 [INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all? John Cai
@ 2022-09-20 20:41 ` Jeff King
  2022-09-22 10:09   ` [PATCH 0/3] reducing fsck memory usage Jeff King
  0 siblings, 1 reply; 10+ messages in thread
From: Jeff King @ 2022-09-20 20:41 UTC (permalink / raw)
  To: John Cai; +Cc: git, Christian Couder

On Tue, Sep 20, 2022 at 03:27:29PM -0400, John Cai wrote:

> One observation is that `git-fsck` seems to use up alot more memory in calling
> unpack_compressed_entry() than `git-rev-list` does.

That just means it's data coming from a pack. The interesting parts are
further up the stack, I think:

> | | ->40.48% (826,445,820B) 0x2B2447: unpack_compressed_entry (packfile.c:1601)
> | | | ->40.48% (826,445,820B) 0x2B46AB: unpack_entry (packfile.c:1768)
> | | | | ->40.48% (826,445,820B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)
> | | | |   ->40.48% (826,445,820B) 0x2B4A23: packed_object_info (packfile.c:1516)
> | | | |     ->40.48% (826,445,820B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
> | | | |       ->40.48% (826,445,820B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
> | | | |         ->40.48% (826,445,820B) 0x29EDC3: read_object (object-file.c:1671)
> | | | |           ->40.48% (826,445,820B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
> | | | |             ->40.12% (819,056,147B) 0x2143BB: repo_read_object_file (object-store.h:253)
> | | | |             | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:511)
> | | | |             |   ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:495)
> | | | |             |     ->40.12% (819,056,147B) 0x25A747: repo_parse_commit (commit.h:90)
> | | | |             |       ->40.12% (819,056,147B) 0x25A747: fsck_walk_commit (fsck.c:355)

OK, so we're holding onto commit buffers after parsing them. We probably
should tell the parser not to do that. It's useful for git-log, etc,
which are going to pretty-print the buffer, but not for this use. You
can set the global save_commit_buffer to do that.

> | | ->08.61% (175,870,114B) 0x2B9DC3: patch_delta (patch-delta.c:36)
> | | | ->08.61% (175,870,114B) 0x2B42EB: unpack_entry (packfile.c:1829)
> | | |   ->08.61% (175,870,114B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)
> | | |     ->08.61% (175,870,114B) 0x2B4A23: packed_object_info (packfile.c:1516)
> | | |       ->08.61% (175,870,114B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)
> | | |         ->08.61% (175,870,114B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)
> | | |           ->08.61% (175,870,114B) 0x29EDC3: read_object (object-file.c:1671)
> | | |             ->08.61% (175,870,114B) 0x29EE5B: read_object_file_extended (object-file.c:1714)
> | | |               ->04.52% (92,219,588B) 0x3461CB: repo_read_object_file (object-store.h:253)
> | | |               | ->04.52% (92,219,588B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)
> | | |               |   ->04.52% (92,219,588B) 0x25A4EB: parse_tree (tree.h:24)
> | | |               |     ->04.52% (92,219,588B) 0x25A4EB: fsck_walk_tree (fsck.c:307)

And this is data we've allocated for trees. It kind of looks like
fsck_walk_tree() never bothers to clean up the trees it parses, leaving
the buffers attached to the tree structs. But that can't be the case,
because linux.git has something like 16GB of trees. These may be entries
we keep in the internal delta cache, though it should be a bit smaller
than what you have here (the default is 96MB; you can drop it with
core.deltaBaseCacheLimit, but runtime may suffer).

There's a call to free_tree_buffer() in builtin/fsck.c:traverse_one();
that may be what ends up freeing things. It's been a while since I've
traced through the call paths for fsck.

> But, not having delved too deeply into the code, I wanted to ask the list if
> anything jumps out as to why `git-fsck` consumes so much more memory than
> `git-rev-list`--perhaps there is opportunity for improvement/optimization?

The patch below improves my peak heap (as reported by massif) for "git
fsck --connectivity-only" on linux.git from ~2GB to ~1GB.

But in general, I think "rev-list" is a better tool for connectivity
checks. One problem with fsck is that it tries to read the set of
available objects up front, making it racy in a repository which is
receiving pushes, or which may be repacked (e.g., if somebody makes a
new object and references it, "fsck --connectivity-only" may fail to
notice the new object but will see the updated ref, and think the ref is
corrupt).

diff --git a/builtin/fsck.c b/builtin/fsck.c
index f7916f06ed..949073a00d 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -853,6 +853,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 
 	errors_found = 0;
 	read_replace_refs = 0;
+	save_commit_buffer = 0;
 
 	argc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);
 

-Peff

^ permalink raw reply related	[flat|nested] 10+ messages in thread

* [PATCH 0/3] reducing fsck memory usage
  2022-09-20 20:41 ` Jeff King
@ 2022-09-22 10:09   ` Jeff King
  2022-09-22 10:11     ` [PATCH 1/3] fsck: free tree buffers after walking unreachable objects Jeff King
                       ` (2 more replies)
  0 siblings, 3 replies; 10+ messages in thread
From: Jeff King @ 2022-09-22 10:09 UTC (permalink / raw)
  To: John Cai; +Cc: git, Christian Couder

On Tue, Sep 20, 2022 at 04:41:51PM -0400, Jeff King wrote:

> And this is data we've allocated for trees. It kind of looks like
> fsck_walk_tree() never bothers to clean up the trees it parses, leaving
> the buffers attached to the tree structs. But that can't be the case,
> because linux.git has something like 16GB of trees. These may be entries
> we keep in the internal delta cache, though it should be a bit smaller
> than what you have here (the default is 96MB; you can drop it with
> core.deltaBaseCacheLimit, but runtime may suffer).
> 
> There's a call to free_tree_buffer() in builtin/fsck.c:traverse_one();
> that may be what ends up freeing things. It's been a while since I've
> traced through the call paths for fsck.

I dug into this a bit more. We do indeed free the trees correctly in
most of the code paths, but there's one where we don't, and you can
convince it to hold all of the trees in memory at once (though in
practice few people are likely to hit this case).

So here's a fix for that, plus a cleaned up version of the patch I sent
earlier which should drop your memory usage, plus a bonus small memory
reduction and cleanup in the third patch.

  [1/3]: fsck: free tree buffers after walking unreachable objects
  [2/3]: fsck: turn off save_commit_buffer
  [3/3]: parse_object_buffer(): respect save_commit_buffer

 builtin/fsck.c | 6 +++---
 object.c       | 3 ++-
 2 files changed, 5 insertions(+), 4 deletions(-)

-Peff

^ permalink raw reply	[flat|nested] 10+ messages in thread

* [PATCH 1/3] fsck: free tree buffers after walking unreachable objects
  2022-09-22 10:09   ` [PATCH 0/3] reducing fsck memory usage Jeff King
@ 2022-09-22 10:11     ` Jeff King
  2022-09-22 18:40       ` Junio C Hamano
  2022-09-22 10:13     ` [PATCH 2/3] fsck: turn off save_commit_buffer Jeff King
  2022-09-22 10:15     ` [PATCH 3/3] parse_object_buffer(): respect save_commit_buffer Jeff King
  2 siblings, 1 reply; 10+ messages in thread
From: Jeff King @ 2022-09-22 10:11 UTC (permalink / raw)
  To: John Cai; +Cc: git, Christian Couder

After calling fsck_walk(), a tree object struct may be left in the
parsed state, with the full tree contents available via tree->buffer.
It's the responsibility of the caller to free these when it's done with
the object to avoid having many trees allocated at once.

In a regular "git fsck", we hit fsck_walk() only from fsck_obj(), which
does call free_tree_buffer(). Likewise for "--connectivity-only", we see
most objects via traverse_one_object(), which makes a similar call.

The exception is in mark_unreachable_referents(). When using both
"--connectivity-only" and "--dangling" (the latter of which is the
default), we walk all of the unreachable objects, and there we forget to
free. Most cases would not notice this, because they don't have a lot of
unreachable objects, but you can make a pathological case like this:

  git clone --bare /path/to/linux.git repo.git
  cd repo.git
  rm packed-refs ;# now everything is unreachable!
  git fsck --connectivity-only

That ends up with peak heap usage ~18GB, which is (not coincidentally)
close to the size of all uncompressed trees in the repository. After
this patch, the peak heap is only ~2GB.

A few things to note:

  - it might seem like fsck_walk(), if it is parsing the trees, should
    be responsible for freeing them. But the situation is quite tricky.
    In the non-connectivity mode, after we call fsck_walk() we then
    proceed with fsck_object() which actually does the type-specific
    sanity checks on the object contents. We do pass our own separate
    buffer to fsck_object(), but there's a catch: our earlier call to
    parse_object_buffer() may have attached that buffer to the object
    struct! So by freeing it, we leave the rest of the code with a
    dangling pointer.

    Likewise, the call to fsck_walk() in index-pack is subtle. It
    attaches a buffer to the tree object that must not be freed! And
    so rather than calling free_tree_buffer(), it actually detaches it
    by setting tree->buffer to NULL.

    These cases would _probably_ be fixable by having fsck_walk() free
    the tree buffer only when it was the one who allocated it via
    parse_tree(). But that would still leave the callers responsible for
    freeing other cases, so they wouldn't be simplified. While the
    current semantics for fsck_walk() make it easy to accidentally leak
    in new callers, at least they are simple to explain, and it's not a
    function that's likely to get a lot of new call-sites.

    And in any case, it's probably sensible to fix the leak first with
    this simple patch, and try any more complicated refactoring
    separately.

  - a careful reader may notice that fsck_obj() also frees commit
    buffers, but neither the call in traverse_one_object() nor the one
    touched in this patch does so. And indeed, this is another problem
    for --connectivity-only (and accounts for most of the 2GB heap after
    this patch), but it's one we'll fix in a separate commit.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/fsck.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index f7916f06ed..34e575a170 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)
 
 	options.walk = mark_used;
 	fsck_walk(obj, NULL, &options);
+	if (obj->type == OBJ_TREE)
+		free_tree_buffer((struct tree *)obj);
 }
 
 static int mark_loose_unreachable_referents(const struct object_id *oid,
-- 
@@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)
 
 	options.walk = mark_used;
 	fsck_walk(obj, NULL, &options);
+	if (obj->type == OBJ_TREE)
+		free_tree_buffer((struct tree *)obj);
 }
 
 static int mark_loose_unreachable_referents(const struct object_id *oid,
-- 
2.38.0.rc1.583.ga560cd8328


^ permalink raw reply related	[flat|nested] 10+ messages in thread

* [PATCH 2/3] fsck: turn off save_commit_buffer
  2022-09-22 10:09   ` [PATCH 0/3] reducing fsck memory usage Jeff King
  2022-09-22 10:11     ` [PATCH 1/3] fsck: free tree buffers after walking unreachable objects Jeff King
@ 2022-09-22 10:13     ` Jeff King
  2022-09-22 10:15     ` [PATCH 3/3] parse_object_buffer(): respect save_commit_buffer Jeff King
  2 siblings, 0 replies; 10+ messages in thread
From: Jeff King @ 2022-09-22 10:13 UTC (permalink / raw)
  To: John Cai; +Cc: git, Christian Couder

When parsing a commit, the default behavior is to stuff the original
buffer into a commit_slab (which takes ownership of it). But for a tool
like fsck, this isn't useful. While we may look at the buffer further as
part of fsck_commit(), we'll always do so through a separate pointer;
attaching the buffer to the slab doesn't help.

Worse, it means we have to remember to free the commit buffer in all
call paths. We do so in fsck_obj(), which covers a regular "git fsck".
But with "--connectivity-only", we forget to do so in both
traverse_one_object(), which covers reachable objects, and
mark_unreachable_referents(), which covers unreachable ones. As a
result, that mode ends up storing an uncompressed copy of every commit
on the heap at once.

We could teach the code paths for --connectivity-only to also free
commit buffers. But there's an even easier fix: we can just turn off the
save_commit_buffer flag, and then we won't attach them to the commits in
the first place.

This reduces the peak heap of running "git fsck --connectivity-only" in
a clone of linux.git from ~2GB to ~1GB. According to massif, the
remaining memory goes where you'd expect: the object structs themselves,
the obj_hash containing them, and the delta base cache.

Note that we'll leave the call to free commit buffers in fsck_obj() for
now; it's not quite redundant because of a related bug that we'll fix in
a subsequent commit.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/fsck.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index 34e575a170..b45de003d4 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -855,6 +855,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 
 	errors_found = 0;
 	read_replace_refs = 0;
+	save_commit_buffer = 0;
 
 	argc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);
 
-- 
@@ -855,6 +855,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 
 	errors_found = 0;
 	read_replace_refs = 0;
+	save_commit_buffer = 0;
 
 	argc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);
 
-- 
2.38.0.rc1.583.ga560cd8328


^ permalink raw reply related	[flat|nested] 10+ messages in thread

* [PATCH 3/3] parse_object_buffer(): respect save_commit_buffer
  2022-09-22 10:09   ` [PATCH 0/3] reducing fsck memory usage Jeff King
  2022-09-22 10:11     ` [PATCH 1/3] fsck: free tree buffers after walking unreachable objects Jeff King
  2022-09-22 10:13     ` [PATCH 2/3] fsck: turn off save_commit_buffer Jeff King
@ 2022-09-22 10:15     ` Jeff King
  2 siblings, 0 replies; 10+ messages in thread
From: Jeff King @ 2022-09-22 10:15 UTC (permalink / raw)
  To: John Cai; +Cc: git, Christian Couder

If the global variable "save_commit_buffer" is set to 0, then
parse_commit() will throw away the commit object data after parsing it,
rather than sticking it into a commit slab. This goes all the way back
to 60ab26de99 ([PATCH] Avoid wasting memory in git-rev-list,
2005-09-15).

But there's another code path which may similarly stash the buffer:
parse_object_buffer(). This is where we end up if we parse a commit via
parse_object(), and it's used directly in a few other code paths like
git-fsck.

The original goal of 60ab26de99 was avoiding extra memory usage for
rev-list. And there it's not all that important to catch parse_object().
We use that function only for looking at the tips of the traversal, and
the majority of the commits are parsed by following parent links, where
we use parse_commit() directly. So we were wasting some memory, but only
a small portion.

It's much easier to see the effect with fsck. Since we now turn off
save_commit_buffer by default there, we _should_ be able to drop the
freeing of the commit buffer in fsck_obj(). But if we do so (taking the
first hunk of this patch without the rest), then the peak heap of "git
fsck" in a clone of git.git goes from 136MB to 194MB. Teaching
parse_object_buffer() to respect save_commit_buffer brings that down to
134.5MB (it's hard to tell from massif's output, but I suspect the
savings comes from avoiding the overhead of the mostly-empty commit
slab).

Other programs should see a small improvement. Both "rev-list --all" and
"fsck --connectivity-only" improve by a few hundred kilobytes, as they'd
avoid loading the tip objects of their traversals.

Most importantly, no code should be hurt by doing this. Any program that
turns off save_commit_buffer is already making the assumption that any
commit it sees may need to have its object data loaded on demand, as it
doesn't know which ones were parsed by parse_commit() versus
parse_object(). Not to mention that anything parsed by the commit graph
may be in the same boat, even if save_commit_buffer was not disabled.

This should be the only spot that needs to be fixed. Grepping for
set_commit_buffer() shows that this and parse_commit() are the only
relevant calls.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/fsck.c | 3 ---
 object.c       | 3 ++-
 2 files changed, 2 insertions(+), 4 deletions(-)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index b45de003d4..41acbc229e 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -439,9 +439,6 @@ static int fsck_obj(struct object *obj, void *buffer, unsigned long size)
 out:
 	if (obj->type == OBJ_TREE)
 		free_tree_buffer((struct tree *)obj);
-	if (obj->type == OBJ_COMMIT)
-		free_commit_buffer(the_repository->parsed_objects,
-				   (struct commit *)obj);
 	return err;
 }
 
diff --git a/object.c b/object.c
index 2e4589bae5..8a74eb85e9 100644
--- a/object.c
+++ b/object.c
@@ -233,7 +233,8 @@ struct object *parse_object_buffer(struct repository *r, const struct object_id
 		if (commit) {
 			if (parse_commit_buffer(r, commit, buffer, size, 1))
 				return NULL;
-			if (!get_cached_commit_buffer(r, commit, NULL)) {
+			if (save_commit_buffer &&
+			    !get_cached_commit_buffer(r, commit, NULL)) {
 				set_commit_buffer(r, commit, buffer, size);
 				*eaten_p = 1;
 			}
-- 
@@ -233,7 +233,8 @@ struct object *parse_object_buffer(struct repository *r, const struct object_id
 		if (commit) {
 			if (parse_commit_buffer(r, commit, buffer, size, 1))
 				return NULL;
-			if (!get_cached_commit_buffer(r, commit, NULL)) {
+			if (save_commit_buffer &&
+			    !get_cached_commit_buffer(r, commit, NULL)) {
 				set_commit_buffer(r, commit, buffer, size);
 				*eaten_p = 1;
 			}
-- 
2.38.0.rc1.583.ga560cd8328

^ permalink raw reply related	[flat|nested] 10+ messages in thread

* Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects
  2022-09-22 10:11     ` [PATCH 1/3] fsck: free tree buffers after walking unreachable objects Jeff King
@ 2022-09-22 18:40       ` Junio C Hamano
  2022-09-22 18:58         ` Jeff King
  0 siblings, 1 reply; 10+ messages in thread
From: Junio C Hamano @ 2022-09-22 18:40 UTC (permalink / raw)
  To: Jeff King; +Cc: John Cai, git, Christian Couder

Jeff King <peff@peff.net> writes:

> After calling fsck_walk(), a tree object struct may be left in the
> parsed state, with the full tree contents available via tree->buffer.
> It's the responsibility of the caller to free these when it's done with
> the object to avoid having many trees allocated at once.
>
> In a regular "git fsck", we hit fsck_walk() only from fsck_obj(), which
> does call free_tree_buffer(). Likewise for "--connectivity-only", we see
> most objects via traverse_one_object(), which makes a similar call.
>
> The exception is in mark_unreachable_referents(). When using both
> "--connectivity-only" and "--dangling" (the latter of which is the
> default), we walk all of the unreachable objects, and there we forget to
> free. Most cases would not notice this, because they don't have a lot of
> unreachable objects, but you can make a pathological case like this:
>
>   git clone --bare /path/to/linux.git repo.git
>   cd repo.git
>   rm packed-refs ;# now everything is unreachable!
>   git fsck --connectivity-only
>
> That ends up with peak heap usage ~18GB, which is (not coincidentally)
> close to the size of all uncompressed trees in the repository. After
> this patch, the peak heap is only ~2GB.
>
> A few things to note:
>
>   - it might seem like fsck_walk(), if it is parsing the trees, should
>     be responsible for freeing them. But the situation is quite tricky.
>     In the non-connectivity mode, after we call fsck_walk() we then
>     proceed with fsck_object() which actually does the type-specific
>     sanity checks on the object contents. We do pass our own separate
>     buffer to fsck_object(), but there's a catch: our earlier call to
>     parse_object_buffer() may have attached that buffer to the object
>     struct! So by freeing it, we leave the rest of the code with a
>     dangling pointer.
>
>     Likewise, the call to fsck_walk() in index-pack is subtle. It
>     attaches a buffer to the tree object that must not be freed! And
>     so rather than calling free_tree_buffer(), it actually detaches it
>     by setting tree->buffer to NULL.
>
>     These cases would _probably_ be fixable by having fsck_walk() free
>     the tree buffer only when it was the one who allocated it via
>     parse_tree(). But that would still leave the callers responsible for
>     freeing other cases, so they wouldn't be simplified. While the
>     current semantics for fsck_walk() make it easy to accidentally leak
>     in new callers, at least they are simple to explain, and it's not a
>     function that's likely to get a lot of new call-sites.
>
>     And in any case, it's probably sensible to fix the leak first with
>     this simple patch, and try any more complicated refactoring
>     separately.
>
>   - a careful reader may notice that fsck_obj() also frees commit
>     buffers, but neither the call in traverse_one_object() nor the one
>     touched in this patch does so. And indeed, this is another problem
>     for --connectivity-only (and accounts for most of the 2GB heap after
>     this patch), but it's one we'll fix in a separate commit.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  builtin/fsck.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/builtin/fsck.c b/builtin/fsck.c
> index f7916f06ed..34e575a170 100644
> --- a/builtin/fsck.c
> +++ b/builtin/fsck.c
> @@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)
>  
>  	options.walk = mark_used;
>  	fsck_walk(obj, NULL, &options);
> +	if (obj->type == OBJ_TREE)
> +		free_tree_buffer((struct tree *)obj);
>  }

Unlike codepaths like mark_object(), which uses the REACHABLE bit to
avoid the walker coming into an already marked objects, we have no
protection that says "this tree is already marked as USED, so lets
not go into its contents" (it would be a disaster if we free tree
buffer here and then later end up calling the function on the same
tree), but it is OK because this is an unreachable object nobody
points at and we will never come back?

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects
  2022-09-22 18:40       ` Junio C Hamano
@ 2022-09-22 18:58         ` Jeff King
  2022-09-22 19:27           ` Junio C Hamano
  0 siblings, 1 reply; 10+ messages in thread
From: Jeff King @ 2022-09-22 18:58 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: John Cai, git, Christian Couder

On Thu, Sep 22, 2022 at 11:40:05AM -0700, Junio C Hamano wrote:

> > diff --git a/builtin/fsck.c b/builtin/fsck.c
> > index f7916f06ed..34e575a170 100644
> > --- a/builtin/fsck.c
> > +++ b/builtin/fsck.c
> > @@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)
> >  
> >  	options.walk = mark_used;
> >  	fsck_walk(obj, NULL, &options);
> > +	if (obj->type == OBJ_TREE)
> > +		free_tree_buffer((struct tree *)obj);
> >  }
> 
> Unlike codepaths like mark_object(), which uses the REACHABLE bit to
> avoid the walker coming into an already marked objects, we have no
> protection that says "this tree is already marked as USED, so lets
> not go into its contents" (it would be a disaster if we free tree
> buffer here and then later end up calling the function on the same
> tree), but it is OK because this is an unreachable object nobody
> points at and we will never come back?

I do think it is true that this is the final time we'd look at these
objects. But I don't think it would be a disaster if somebody did. The
free_tree_buffer() function clears the "parsed" flag on the struct. And
anybody wishing to look at the tree contents would need to call
parse_tree(), which would then re-load the contents.

In general, that's _possibly_ less efficient if we visit the same tree
twice, but it would be balanced against not holding all of the tree data
in RAM at once. And as I said, that doesn't happen for this use case
anyway.

As a side note, IMHO having tree->buffer at all is a mistake, because it
leads to exactly this kind of confusion about when the buffer should be
discarded. We'd be better off having all callers parse directly into a
local buffer, and then clean up when they're done. It effectively ends
up the same, except then it's obvious when a tree is "leaked" because
the local buffer goes out of scope, rather than hanging around in the
global struct and just wasting memory. But that's obviously a much
bigger change.

-Peff

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects
  2022-09-22 18:58         ` Jeff King
@ 2022-09-22 19:27           ` Junio C Hamano
  2022-09-22 22:16             ` Jeff King
  0 siblings, 1 reply; 10+ messages in thread
From: Junio C Hamano @ 2022-09-22 19:27 UTC (permalink / raw)
  To: Jeff King; +Cc: John Cai, git, Christian Couder

Jeff King <peff@peff.net> writes:

> I do think it is true that this is the final time we'd look at these
> objects. But I don't think it would be a disaster if somebody did. The
> free_tree_buffer() function clears the "parsed" flag on the struct. 

Ah, that is perfectly fine, then.  Thanks.

> As a side note, IMHO having tree->buffer at all is a mistake, because it
> leads to exactly this kind of confusion about when the buffer should be
> discarded. We'd be better off having all callers parse directly into a
> local buffer, and then clean up when they're done.

Yeah, tree-walk.c users woud use tree_desc structure anyway, and
instead of having a moving pointer that points into a separate thing
(i.e. tree->buffer), it could have its own copy of the "whole buffer"
that can be used to free when it is done iterating over entries.

> .... But that's obviously a much bigger change.

Yup.

Thanks.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects
  2022-09-22 19:27           ` Junio C Hamano
@ 2022-09-22 22:16             ` Jeff King
  0 siblings, 0 replies; 10+ messages in thread
From: Jeff King @ 2022-09-22 22:16 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: John Cai, git, Christian Couder

On Thu, Sep 22, 2022 at 12:27:33PM -0700, Junio C Hamano wrote:

> > As a side note, IMHO having tree->buffer at all is a mistake, because it
> > leads to exactly this kind of confusion about when the buffer should be
> > discarded. We'd be better off having all callers parse directly into a
> > local buffer, and then clean up when they're done.
> 
> Yeah, tree-walk.c users woud use tree_desc structure anyway, and
> instead of having a moving pointer that points into a separate thing
> (i.e. tree->buffer), it could have its own copy of the "whole buffer"
> that can be used to free when it is done iterating over entries.
> 
> > .... But that's obviously a much bigger change.
> 
> Yup.

I took a (very) brief stab at this, out of curiosity. The sticking point
becomes obvious very quickly: how do we get the buffer to the caller? If
you are calling parse_tree(), we can add new out-parameters to provide
the buffer. But something like parse_object() is just returning an
object struct, and we have to stuff anything we want to communicate to
the caller inside the polymorphic struct which contains it.

We could split the concept of "parse" away from "get the buffer"
entirely, but then we have a potential slowdown. The "parse" functions
really want to open the object contents and check the hash (and removing
that in the general case would probably break part of fsck, at least).
So we'd end up inflating the object contents twice, which would probably
have a measurable impact.

I don't plan on digging any further on it for now, so this is just a
note for future people who do. :)

-Peff

^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2022-09-22 22:16 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-20 19:27 [INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all? John Cai
2022-09-20 20:41 ` Jeff King
2022-09-22 10:09   ` [PATCH 0/3] reducing fsck memory usage Jeff King
2022-09-22 10:11     ` [PATCH 1/3] fsck: free tree buffers after walking unreachable objects Jeff King
2022-09-22 18:40       ` Junio C Hamano
2022-09-22 18:58         ` Jeff King
2022-09-22 19:27           ` Junio C Hamano
2022-09-22 22:16             ` Jeff King
2022-09-22 10:13     ` [PATCH 2/3] fsck: turn off save_commit_buffer Jeff King
2022-09-22 10:15     ` [PATCH 3/3] parse_object_buffer(): respect save_commit_buffer Jeff King

Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).