{"thread":{"id":"58475","subject":"[INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all?","startedAt":"2022-09-20T19:27:42Z","lastAt":"2022-09-22T22:16:18Z","messageCount":10,"participants":["John Cai","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"463323","messageId":"9304B938-4A59-456B-B091-DBBCAA1823B2@gmail.com","threadId":"58475","inReplyTo":null,"subject":"[INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all?","fromName":"John Cai","fromEmail":"johncai86@gmail.com","sentAt":"2022-09-20T19:27:29Z","receivedAt":"2022-09-20T19:27:42Z","isPatch":false,"sender":{"key":"johncai86@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2354211?v=4"},"body":"Hi everyone,\n\nI would love your thoughts about something I'm noticing in git fsck\n--connectivity-only. I noticed that for large repositories, this operation can\ntake up alot of memory.\n\nHere at GitLab we are exploring using `git rev-list --all --objects` as a proxy\nfor checking connectivity. In doing so, I noticed `git fsck --connectivity-only`\nis much more expensive than `git rev-list --all --objects`.\n\nUsing Valgrind, here are some memory profile results from running both on the\nlinux repo:\n\n`git fsck --connectivity-only`:\n\n GB\n1.916^ :\n | @@:@@:#:\n | :::@@:@@@:@@:#:\n | :::@::@:::@@:@@@:@@:#:\n | :::@@@@:: @::@:::@@:@@@:@@:#:\n | @@::::::: :@ @@:: @::@:::@@:@@@:@@:#:\n | :::::::@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | ::::@@::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | ::::::@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | :::::::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | ::::::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | ::::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n | : ::: ::::: ::::: :@::::@ ::: :: :@@: ::: : :@ @@:: @::@:::@@:@@@:@@:#:\n 0 +----------------------------------------------------------------------->Gi\n 0 233.7\n\n\n`git rev-list --all --objects`:\n\n MB\n979.8^ #\n | #\n | #\n | #::::\n | #::::\n | #::::\n | @@@:@@#::::\n | ::@@@:@@@@@@:@@#::::\n | ::::@::::::@@@:@@@@@@:@@#::::\n | @@ :::::::::: ::@::::::@@@:@@@@@@:@@#::::\n | @ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | @@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | ::::@::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | @@::::::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | @ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | @ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | :@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | ::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | :::::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n | :::: ::@@ ::: ::: @::::@@@:@ :@:::::: :::: ::@::::::@@@:@@@@@@:@@#::::\n 0 +----------------------------------------------------------------------->Gi\n 0 245.5\n\nAs we can see, `git fsck` uses about twice the amount of memory as `git\nrev-list`, which was a bit surprising to me.\n\nDigging in a bit, here is the stack trace analysis:\n\n`git fsck --connectivity-only`:\n\n98.37% (2,008,484,573B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.\n->84.04% (1,715,907,794B) 0x35779F: do_xmalloc (wrapper.c:51)\n| ->50.73% (1,035,816,788B) 0x35781F: do_xmallocz.part.0 (wrapper.c:85)\n| | ->40.48% (826,445,820B) 0x2B2447: unpack_compressed_entry (packfile.c:1601)\n| | | ->40.48% (826,445,820B) 0x2B46AB: unpack_entry (packfile.c:1768)\n| | | | ->40.48% (826,445,820B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)\n| | | | ->40.48% (826,445,820B) 0x2B4A23: packed_object_info (packfile.c:1516)\n| | | | ->40.48% (826,445,820B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n| | | | ->40.48% (826,445,820B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n| | | | ->40.48% (826,445,820B) 0x29EDC3: read_object (object-file.c:1671)\n| | | | ->40.48% (826,445,820B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n| | | | ->40.12% (819,056,147B) 0x2143BB: repo_read_object_file (object-store.h:253)\n| | | | | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:511)\n| | | | | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:495)\n| | | | | ->40.12% (819,056,147B) 0x25A747: repo_parse_commit (commit.h:90)\n| | | | | ->40.12% (819,056,147B) 0x25A747: fsck_walk_commit (fsck.c:355)\n| | | | | ->40.12% (819,056,147B) 0x25A747: fsck_walk (fsck.c:441)\n| | | | | ->40.12% (819,056,147B) 0x16C7BB: traverse_one_object (fsck.c:175)\n| | | | | ->40.12% (819,056,147B) 0x16C7BB: traverse_reachable (fsck.c:192)\n| | | | | ->40.12% (819,056,147B) 0x16C7BB: check_connectivity (fsck.c:363)\n| | | | | ->40.12% (819,056,147B) 0x16C7BB: cmd_fsck (fsck.c:982)\n| | | | | ->40.12% (819,056,147B) 0x128007: run_builtin (git.c:466)\n| | | | | ->40.12% (819,056,147B) 0x128007: handle_builtin (git.c:720)\n| | | | | ->40.12% (819,056,147B) 0x129127: cmd_main (git.c:888)\n| | | | | ->40.12% (819,056,147B) 0x127B67: main (common-main.c:56)\n| | | | |\n| | | | ->00.36% (7,389,673B) in 1+ places, all below ms_print's threshold (01.00%)\n| | | |\n| | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->08.61% (175,870,114B) 0x2B9DC3: patch_delta (patch-delta.c:36)\n| | | ->08.61% (175,870,114B) 0x2B42EB: unpack_entry (packfile.c:1829)\n| | | ->08.61% (175,870,114B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)\n| | | ->08.61% (175,870,114B) 0x2B4A23: packed_object_info (packfile.c:1516)\n| | | ->08.61% (175,870,114B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n| | | ->08.61% (175,870,114B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n| | | ->08.61% (175,870,114B) 0x29EDC3: read_object (object-file.c:1671)\n| | | ->08.61% (175,870,114B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n| | | ->04.52% (92,219,588B) 0x3461CB: repo_read_object_file (object-store.h:253)\n| | | | ->04.52% (92,219,588B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)\n| | | | ->04.52% (92,219,588B) 0x25A4EB: parse_tree (tree.h:24)\n| | | | ->04.52% (92,219,588B) 0x25A4EB: fsck_walk_tree (fsck.c:307)\n| | | | ->04.52% (92,219,588B) 0x25A4EB: fsck_walk (fsck.c:439)\n| | | | ->04.52% (92,219,588B) 0x16C7BB: traverse_one_object (fsck.c:175)\n| | | | ->04.52% (92,219,588B) 0x16C7BB: traverse_reachable (fsck.c:192)\n| | | | ->04.52% (92,219,588B) 0x16C7BB: check_connectivity (fsck.c:363)\n| | | | ->04.52% (92,219,588B) 0x16C7BB: cmd_fsck (fsck.c:982)\n| | | | ->04.52% (92,219,588B) 0x128007: run_builtin (git.c:466)\n| | | | ->04.52% (92,219,588B) 0x128007: handle_builtin (git.c:720)\n| | | | ->04.52% (92,219,588B) 0x129127: cmd_main (git.c:888)\n| | | | ->04.52% (92,219,588B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->04.10% (83,650,526B) 0x2143BB: repo_read_object_file (object-store.h:253)\n| | | | ->04.10% (83,650,526B) 0x2143BB: repo_parse_commit_internal (commit.c:511)\n| | | | ->04.10% (83,650,526B) 0x2143BB: repo_parse_commit_internal (commit.c:495)\n| | | | ->04.10% (83,650,526B) 0x25A747: repo_parse_commit (commit.h:90)\n| | | | ->04.10% (83,650,526B) 0x25A747: fsck_walk_commit (fsck.c:355)\n| | | | ->04.10% (83,650,526B) 0x25A747: fsck_walk (fsck.c:441)\n| | | | ->04.10% (83,650,526B) 0x16C7BB: traverse_one_object (fsck.c:175)\n| | | | ->04.10% (83,650,526B) 0x16C7BB: traverse_reachable (fsck.c:192)\n| | | | ->04.10% (83,650,526B) 0x16C7BB: check_connectivity (fsck.c:363)\n| | | | ->04.10% (83,650,526B) 0x16C7BB: cmd_fsck (fsck.c:982)\n| | | | ->04.10% (83,650,526B) 0x128007: run_builtin (git.c:466)\n| | | | ->04.10% (83,650,526B) 0x128007: handle_builtin (git.c:720)\n| | | | ->04.10% (83,650,526B) 0x129127: cmd_main (git.c:888)\n| | | | ->04.10% (83,650,526B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->01.64% (33,500,854B) 0x357903: do_xmallocz (wrapper.c:83)\n| | | ->01.64% (33,500,854B) 0x357903: xmallocz (wrapper.c:93)\n| | | ->01.64% (33,500,854B) 0x357903: xmemdupz (wrapper.c:109)\n| | | ->01.64% (33,493,416B) 0x2B476F: cache_or_unpack_entry (packfile.c:1444)\n| | | | ->01.64% (33,493,416B) 0x2B476F: packed_object_info (packfile.c:1516)\n| | | | ->01.64% (33,493,416B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n| | | | ->01.64% (33,493,416B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n| | | | ->01.64% (33,493,416B) 0x29EDC3: read_object (object-file.c:1671)\n| | | | ->01.64% (33,493,416B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n| | | | ->01.64% (33,438,291B) 0x2143BB: repo_read_object_file (object-store.h:253)\n| | | | | ->01.64% (33,438,291B) 0x2143BB: repo_parse_commit_internal (commit.c:511)\n| | | | | ->01.64% (33,438,291B) 0x2143BB: repo_parse_commit_internal (commit.c:495)\n| | | | | ->01.64% (33,438,291B) 0x25A747: repo_parse_commit (commit.h:90)\n| | | | | ->01.64% (33,438,291B) 0x25A747: fsck_walk_commit (fsck.c:355)\n| | | | | ->01.64% (33,438,291B) 0x25A747: fsck_walk (fsck.c:441)\n| | | | | ->01.64% (33,438,291B) 0x16C7BB: traverse_one_object (fsck.c:175)\n| | | | | ->01.64% (33,438,291B) 0x16C7BB: traverse_reachable (fsck.c:192)\n| | | | | ->01.64% (33,438,291B) 0x16C7BB: check_connectivity (fsck.c:363)\n| | | | | ->01.64% (33,438,291B) 0x16C7BB: cmd_fsck (fsck.c:982)\n| | | | | ->01.64% (33,438,291B) 0x128007: run_builtin (git.c:466)\n| | | | | ->01.64% (33,438,291B) 0x128007: handle_builtin (git.c:720)\n| | | | | ->01.64% (33,438,291B) 0x129127: cmd_main (git.c:888)\n| | | | | ->01.64% (33,438,291B) 0x127B67: main (common-main.c:56)\n| | | | |\n| | | | ->00.00% (55,125B) in 1+ places, all below ms_print's threshold (01.00%)\n| | | |\n| | | ->00.00% (7,438B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->31.69% (646,963,200B) 0x369A07: alloc_node (alloc.c:59)\n| | ->31.69% (646,963,200B) 0x369A07: alloc_object_node (alloc.c:95)\n| | ->31.69% (646,963,200B) 0x2A3A0F: lookup_unknown_object (object.c:184)\n| | ->31.69% (646,963,200B) 0x16B19B: mark_object_for_connectivity (fsck.c:800)\n| | ->31.69% (646,963,200B) 0x16B19B: mark_packed_for_connectivity (fsck.c:817)\n| | ->31.69% (646,963,200B) 0x2B50AB: for_each_object_in_pack (packfile.c:2176)\n| | ->31.69% (646,963,200B) 0x2B5217: for_each_packed_object (packfile.c:2207)\n| | ->31.69% (646,963,200B) 0x16C6A3: cmd_fsck (fsck.c:881)\n| | ->31.69% (646,963,200B) 0x128007: run_builtin (git.c:466)\n| | ->31.69% (646,963,200B) 0x128007: handle_builtin (git.c:720)\n| | ->31.69% (646,963,200B) 0x129127: cmd_main (git.c:888)\n| | ->31.69% (646,963,200B) 0x127B67: main (common-main.c:56)\n| |\n| ->01.62% (33,127,806B) in 14 places, all below massif's threshold (1.00%)\n|\n->14.12% (288,287,504B) 0x357A37: xcalloc (wrapper.c:150)\n| ->13.15% (268,435,456B) 0x2A386B: grow_object_hash (object.c:130)\n| | ->13.15% (268,435,456B) 0x2A386B: create_object (object.c:152)\n| | ->13.15% (268,435,456B) 0x16B19B: mark_object_for_connectivity (fsck.c:800)\n| | ->13.15% (268,435,456B) 0x16B19B: mark_packed_for_connectivity (fsck.c:817)\n| | ->13.15% (268,435,456B) 0x2B50AB: for_each_object_in_pack (packfile.c:2176)\n| | ->13.15% (268,435,456B) 0x2B5217: for_each_packed_object (packfile.c:2207)\n| | ->13.15% (268,435,456B) 0x16C6A3: cmd_fsck (fsck.c:881)\n| | ->13.15% (268,435,456B) 0x128007: run_builtin (git.c:466)\n| | ->13.15% (268,435,456B) 0x128007: handle_builtin (git.c:720)\n| | ->13.15% (268,435,456B) 0x129127: cmd_main (git.c:888)\n| | ->13.15% (268,435,456B) 0x127B67: main (common-main.c:56)\n| |\n| ->00.97% (19,852,048B) in 1+ places, all below ms_print's threshold (01.00%)\n|\n->00.21% (4,289,275B) in 1+ places, all below ms_print's threshold (01.00%)\n\n`git rev-list --all --objects`:\n\n99.88% (1,026,125,720B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.\n->54.04% (555,159,796B) 0x35779F: do_xmalloc (wrapper.c:51)\n| ->27.44% (281,960,448B) 0x369803: alloc_node (alloc.c:59)\n| | ->27.44% (281,960,448B) 0x369803: alloc_tree_node (alloc.c:81)\n| | ->27.44% (281,960,448B) 0x3462DF: lookup_tree (tree.c:109)\n| | ->27.44% (281,960,448B) 0x3462DF: lookup_tree (tree.c:105)\n| | ->21.38% (219,684,864B) 0x270707: process_tree_contents (list-objects.c:142)\n| | | ->21.38% (219,684,864B) 0x270707: process_tree (list-objects.c:221)\n| | | ->15.11% (155,287,552B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | ->15.11% (155,287,552B) 0x27072B: process_tree (list-objects.c:221)\n| | | | ->08.64% (88,768,512B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | ->08.64% (88,768,512B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | ->04.77% (49,029,120B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | ->04.77% (49,029,120B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | ->04.77% (49,029,120B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | ->04.77% (49,029,120B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | ->04.77% (49,029,120B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | ->04.77% (49,029,120B) 0x128007: run_builtin (git.c:466)\n| | | | | | ->04.77% (49,029,120B) 0x128007: handle_builtin (git.c:720)\n| | | | | | ->04.77% (49,029,120B) 0x129127: cmd_main (git.c:888)\n| | | | | | ->04.77% (49,029,120B) 0x127B67: main (common-main.c:56)\n| | | | | |\n| | | | | ->03.87% (39,739,392B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | ->03.87% (39,739,392B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | ->02.45% (25,174,016B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | ->02.45% (25,174,016B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | ->02.45% (25,174,016B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | ->02.45% (25,174,016B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | ->02.45% (25,174,016B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | ->02.45% (25,174,016B) 0x128007: run_builtin (git.c:466)\n| | | | | | ->02.45% (25,174,016B) 0x128007: handle_builtin (git.c:720)\n| | | | | | ->02.45% (25,174,016B) 0x129127: cmd_main (git.c:888)\n| | | | | | ->02.45% (25,174,016B) 0x127B67: main (common-main.c:56)\n| | | | | |\n| | | | | ->01.42% (14,565,376B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | ->01.42% (14,565,376B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | ->01.00% (10,321,920B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | ->01.00% (10,321,920B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | ->01.00% (10,321,920B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | ->01.00% (10,321,920B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | ->01.00% (10,321,920B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | ->01.00% (10,321,920B) 0x128007: run_builtin (git.c:466)\n| | | | | | ->01.00% (10,321,920B) 0x128007: handle_builtin (git.c:720)\n| | | | | | ->01.00% (10,321,920B) 0x129127: cmd_main (git.c:888)\n| | | | | | ->01.00% (10,321,920B) 0x127B67: main (common-main.c:56)\n| | | | | |\n| | | | | ->00.41% (4,243,456B) in 1+ places, all below ms_print's threshold (01.00%)\n| | | | |\n| | | | ->06.47% (66,519,040B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | ->06.47% (66,519,040B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | ->06.47% (66,519,040B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | ->06.47% (66,519,040B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | ->06.47% (66,519,040B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | ->06.47% (66,519,040B) 0x128007: run_builtin (git.c:466)\n| | | | ->06.47% (66,519,040B) 0x128007: handle_builtin (git.c:720)\n| | | | ->06.47% (66,519,040B) 0x129127: cmd_main (git.c:888)\n| | | | ->06.47% (66,519,040B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->06.27% (64,397,312B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | ->06.27% (64,397,312B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | ->06.27% (64,397,312B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | ->06.27% (64,397,312B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | ->06.27% (64,397,312B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | ->06.27% (64,397,312B) 0x128007: run_builtin (git.c:466)\n| | | ->06.27% (64,397,312B) 0x128007: handle_builtin (git.c:720)\n| | | ->06.27% (64,397,312B) 0x129127: cmd_main (git.c:888)\n| | | ->06.27% (64,397,312B) 0x127B67: main (common-main.c:56)\n| | |\n| | ->06.06% (62,275,584B) 0x213F93: parse_commit_buffer (commit.c:440)\n| | ->06.06% (62,218,240B) 0x2143E7: repo_parse_commit_internal (commit.c:522)\n| | | ->06.06% (62,218,240B) 0x2143E7: repo_parse_commit_internal (commit.c:495)\n| | | ->06.06% (62,218,240B) 0x2FC77B: process_parents (revision.c:1169)\n| | | ->06.06% (62,218,240B) 0x2FFEBB: get_revision_1 (revision.c:4080)\n| | | ->06.06% (62,218,240B) 0x3000EB: get_revision_internal (revision.c:4188)\n| | | ->06.06% (62,218,240B) 0x30026F: get_revision (revision.c:4266)\n| | | ->06.06% (62,218,240B) 0x270C63: do_traverse (list-objects.c:397)\n| | | ->06.06% (62,218,240B) 0x270C63: traverse_commit_list_filtered (list-objects.c:453)\n| | | ->06.06% (62,218,240B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | ->06.06% (62,218,240B) 0x128007: run_builtin (git.c:466)\n| | | ->06.06% (62,218,240B) 0x128007: handle_builtin (git.c:720)\n| | | ->06.06% (62,218,240B) 0x129127: cmd_main (git.c:888)\n| | | ->06.06% (62,218,240B) 0x127B67: main (common-main.c:56)\n| | |\n| | ->00.01% (57,344B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->09.80% (100,703,562B) 0x35781F: do_xmallocz.part.0 (wrapper.c:85)\n| | ->09.47% (97,307,344B) 0x2B9DC3: patch_delta (patch-delta.c:36)\n| | | ->09.47% (97,307,344B) 0x2B42EB: unpack_entry (packfile.c:1829)\n| | | ->09.47% (97,307,344B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)\n| | | ->09.47% (97,307,344B) 0x2B4A23: packed_object_info (packfile.c:1516)\n| | | ->09.47% (97,307,344B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n| | | ->09.47% (97,307,344B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n| | | ->09.47% (97,307,344B) 0x29EDC3: read_object (object-file.c:1671)\n| | | ->09.47% (97,307,344B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n| | | ->09.47% (97,307,344B) 0x3461CB: repo_read_object_file (object-store.h:253)\n| | | | ->09.47% (97,307,344B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)\n| | | | ->09.47% (97,307,344B) 0x2703EF: process_tree (list-objects.c:188)\n| | | | ->09.07% (93,167,206B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | ->09.07% (93,167,206B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | ->07.49% (76,907,030B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | | ->07.49% (76,907,030B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | | ->05.69% (58,476,176B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | | ->05.69% (58,476,176B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | | ->05.69% (58,476,176B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | | ->05.69% (58,476,176B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | | ->05.69% (58,476,176B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | | ->05.69% (58,476,176B) 0x128007: run_builtin (git.c:466)\n| | | | | | | ->05.69% (58,476,176B) 0x128007: handle_builtin (git.c:720)\n| | | | | | | ->05.69% (58,476,176B) 0x129127: cmd_main (git.c:888)\n| | | | | | | ->05.69% (58,476,176B) 0x127B67: main (common-main.c:56)\n| | | | | | |\n| | | | | | ->01.79% (18,430,854B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | | ->01.79% (18,430,854B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | | ->01.26% (12,951,424B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | | ->01.26% (12,951,424B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | | ->01.26% (12,951,424B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | | ->01.26% (12,951,424B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | | ->01.26% (12,951,424B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | | ->01.26% (12,951,424B) 0x128007: run_builtin (git.c:466)\n| | | | | | | ->01.26% (12,951,424B) 0x128007: handle_builtin (git.c:720)\n| | | | | | | ->01.26% (12,951,424B) 0x129127: cmd_main (git.c:888)\n| | | | | | | ->01.26% (12,951,424B) 0x127B67: main (common-main.c:56)\n| | | | | | |\n| | | | | | ->00.53% (5,479,430B) in 1+ places, all below ms_print's threshold (01.00%)\n| | | | | |\n| | | | | ->01.58% (16,260,176B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | ->01.58% (16,260,176B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | ->01.58% (16,260,176B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | ->01.58% (16,260,176B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | ->01.58% (16,260,176B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | ->01.58% (16,260,176B) 0x128007: run_builtin (git.c:466)\n| | | | | ->01.58% (16,260,176B) 0x128007: handle_builtin (git.c:720)\n| | | | | ->01.58% (16,260,176B) 0x129127: cmd_main (git.c:888)\n| | | | | ->01.58% (16,260,176B) 0x127B67: main (common-main.c:56)\n| | | | |\n| | | | ->00.40% (4,140,138B) in 1+ places, all below ms_print's threshold (01.00%)\n| | | |\n| | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->00.33% (3,396,218B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->08.68% (89,210,880B) 0x36970B: alloc_node (alloc.c:59)\n| | ->08.68% (89,210,880B) 0x36970B: alloc_blob_node (alloc.c:74)\n| | ->08.68% (89,210,880B) 0x1FEE17: lookup_blob (blob.c:12)\n| | ->08.68% (89,210,880B) 0x27066F: process_tree_contents (list-objects.c:155)\n| | ->08.68% (89,210,880B) 0x27066F: process_tree (list-objects.c:221)\n| | ->08.59% (88,227,840B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | ->08.59% (88,227,840B) 0x27072B: process_tree (list-objects.c:221)\n| | | ->08.24% (84,623,360B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | ->08.24% (84,623,360B) 0x27072B: process_tree (list-objects.c:221)\n| | | | ->05.85% (60,088,320B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | ->05.85% (60,088,320B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | ->03.17% (32,604,160B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | | ->03.17% (32,604,160B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | | ->01.92% (19,742,720B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | | | ->01.92% (19,742,720B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | | | ->01.92% (19,742,720B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | | | ->01.92% (19,742,720B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | | | ->01.92% (19,742,720B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | | | ->01.92% (19,742,720B) 0x128007: run_builtin (git.c:466)\n| | | | | | | ->01.92% (19,742,720B) 0x128007: handle_builtin (git.c:720)\n| | | | | | | ->01.92% (19,742,720B) 0x129127: cmd_main (git.c:888)\n| | | | | | | ->01.92% (19,742,720B) 0x127B67: main (common-main.c:56)\n| | | | | | |\n| | | | | | ->01.25% (12,861,440B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | | | | ->01.25% (12,861,440B) 0x27072B: process_tree (list-objects.c:221)\n| | | | | | ->01.25% (12,861,440B) in 2 places, all below massif's threshold (1.00%)\n| | | | | |\n| | | | | ->02.68% (27,484,160B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | | ->02.68% (27,484,160B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | | ->02.68% (27,484,160B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | | ->02.68% (27,484,160B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | | ->02.68% (27,484,160B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | | ->02.68% (27,484,160B) 0x128007: run_builtin (git.c:466)\n| | | | | ->02.68% (27,484,160B) 0x128007: handle_builtin (git.c:720)\n| | | | | ->02.68% (27,484,160B) 0x129127: cmd_main (git.c:888)\n| | | | | ->02.68% (27,484,160B) 0x127B67: main (common-main.c:56)\n| | | | |\n| | | | ->02.39% (24,535,040B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | ->02.39% (24,535,040B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | ->02.39% (24,535,040B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | ->02.39% (24,535,040B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | ->02.39% (24,535,040B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | ->02.39% (24,535,040B) 0x128007: run_builtin (git.c:466)\n| | | | ->02.39% (24,535,040B) 0x128007: handle_builtin (git.c:720)\n| | | | ->02.39% (24,535,040B) 0x129127: cmd_main (git.c:888)\n| | | | ->02.39% (24,535,040B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->00.35% (3,604,480B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->00.10% (983,040B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->07.87% (80,879,616B) 0x369B27: alloc_node (alloc.c:59)\n| | ->07.87% (80,879,616B) 0x369B27: alloc_commit_node (alloc.c:119)\n| | ->07.87% (80,879,616B) 0x2133B7: lookup_commit (commit.c:66)\n| | ->07.87% (80,879,616B) 0x2133B7: lookup_commit (commit.c:62)\n| | ->07.87% (80,805,888B) 0x21411B: parse_commit_buffer (commit.c:466)\n| | | ->07.86% (80,732,160B) 0x2143E7: repo_parse_commit_internal (commit.c:522)\n| | | | ->07.86% (80,732,160B) 0x2143E7: repo_parse_commit_internal (commit.c:495)\n| | | | ->07.86% (80,732,160B) 0x2FC77B: process_parents (revision.c:1169)\n| | | | ->07.86% (80,732,160B) 0x2FFEBB: get_revision_1 (revision.c:4080)\n| | | | ->07.86% (80,732,160B) 0x3000EB: get_revision_internal (revision.c:4188)\n| | | | ->07.86% (80,732,160B) 0x30026F: get_revision (revision.c:4266)\n| | | | ->07.86% (80,732,160B) 0x270C63: do_traverse (list-objects.c:397)\n| | | | ->07.86% (80,732,160B) 0x270C63: traverse_commit_list_filtered (list-objects.c:453)\n| | | | ->07.86% (80,732,160B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | ->07.86% (80,732,160B) 0x128007: run_builtin (git.c:466)\n| | | | ->07.86% (80,732,160B) 0x128007: handle_builtin (git.c:720)\n| | | | ->07.86% (80,732,160B) 0x129127: cmd_main (git.c:888)\n| | | | ->07.86% (80,732,160B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->00.01% (73,728B) in 1+ places, all below ms_print's threshold (01.00%)\n| | |\n| | ->00.01% (73,728B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->00.23% (2,405,290B) in 1+ places, all below ms_print's threshold (01.00%)\n|\n->39.29% (403,708,926B) 0x357A37: xcalloc (wrapper.c:150)\n| ->39.19% (402,653,184B) 0x2A386B: grow_object_hash (object.c:130)\n| | ->39.19% (402,653,184B) 0x2A386B: create_object (object.c:152)\n| | ->39.19% (402,653,184B) 0x270707: process_tree_contents (list-objects.c:142)\n| | | ->39.19% (402,653,184B) 0x270707: process_tree (list-objects.c:221)\n| | | ->26.13% (268,435,456B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | | ->26.13% (268,435,456B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | | ->26.13% (268,435,456B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | | ->26.13% (268,435,456B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | | ->26.13% (268,435,456B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | | ->26.13% (268,435,456B) 0x128007: run_builtin (git.c:466)\n| | | | ->26.13% (268,435,456B) 0x128007: handle_builtin (git.c:720)\n| | | | ->26.13% (268,435,456B) 0x129127: cmd_main (git.c:888)\n| | | | ->26.13% (268,435,456B) 0x127B67: main (common-main.c:56)\n| | | |\n| | | ->13.06% (134,217,728B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | ->13.06% (134,217,728B) 0x27072B: process_tree (list-objects.c:221)\n| | | ->13.06% (134,217,728B) 0x27072B: process_tree_contents (list-objects.c:149)\n| | | ->13.06% (134,217,728B) 0x27072B: process_tree (list-objects.c:221)\n| | | ->13.06% (134,217,728B) 0x2708D3: traverse_non_commits (list-objects.c:378)\n| | | ->13.06% (134,217,728B) 0x2708D3: traverse_non_commits (list-objects.c:357)\n| | | ->13.06% (134,217,728B) 0x270D5B: do_traverse (list-objects.c:432)\n| | | ->13.06% (134,217,728B) 0x270D5B: traverse_commit_list_filtered (list-objects.c:453)\n| | | ->13.06% (134,217,728B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | ->13.06% (134,217,728B) 0x128007: run_builtin (git.c:466)\n| | | ->13.06% (134,217,728B) 0x128007: handle_builtin (git.c:720)\n| | | ->13.06% (134,217,728B) 0x129127: cmd_main (git.c:888)\n| | | ->13.06% (134,217,728B) 0x127B67: main (common-main.c:56)\n| | |\n| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->00.10% (1,055,742B) in 1+ places, all below ms_print's threshold (01.00%)\n|\n->06.54% (67,228,381B) 0x3579CF: xrealloc (wrapper.c:136)\n| ->06.53% (67,106,816B) 0x2A406B: add_object_array_with_path (object.c:353)\n| | ->06.53% (67,106,816B) 0x2F8427: add_pending_object_with_path (revision.c:343)\n| | ->06.53% (67,106,816B) 0x270D17: add_pending_tree (list-objects.c:354)\n| | | ->06.53% (67,106,816B) 0x270D17: do_traverse (list-objects.c:413)\n| | | ->06.53% (67,106,816B) 0x270D17: traverse_commit_list_filtered (list-objects.c:453)\n| | | ->06.53% (67,106,816B) 0x1BD3D3: cmd_rev_list (rev-list.c:721)\n| | | ->06.53% (67,106,816B) 0x128007: run_builtin (git.c:466)\n| | | ->06.53% (67,106,816B) 0x128007: handle_builtin (git.c:720)\n| | | ->06.53% (67,106,816B) 0x129127: cmd_main (git.c:888)\n| | | ->06.53% (67,106,816B) 0x127B67: main (common-main.c:56)\n| | |\n| | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)\n| |\n| ->00.01% (121,565B) in 1+ places, all below ms_print's threshold (01.00%)\n|\n->00.00% (28,617B) in 1+ places, all below ms_print's threshold (01.00%)\n\nOne observation is that `git-fsck` seems to use up alot more memory in calling\nunpack_compressed_entry() than `git-rev-list` does.\n\nBut, not having delved too deeply into the code, I wanted to ask the list if\nanything jumps out as to why `git-fsck` consumes so much more memory than\n`git-rev-list`--perhaps there is opportunity for improvement/optimization?\n\nthanks!\nJohn\n"},{"id":"463344","messageId":"YyoljwDIn7PxRlC9@coredump.intra.peff.net","threadId":"58475","inReplyTo":"9304B938-4A59-456B-B091-DBBCAA1823B2@gmail.com","subject":"Re: [INVESTIGATION] why is fsck --connectivity-only so much more expensive than rev-list --objects --all?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-20T20:41:51Z","receivedAt":"2022-09-20T20:41:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 20, 2022 at 03:27:29PM -0400, John Cai wrote:\n\n> One observation is that `git-fsck` seems to use up alot more memory in calling\n> unpack_compressed_entry() than `git-rev-list` does.\n\nThat just means it's data coming from a pack. The interesting parts are\nfurther up the stack, I think:\n\n> | | ->40.48% (826,445,820B) 0x2B2447: unpack_compressed_entry (packfile.c:1601)\n> | | | ->40.48% (826,445,820B) 0x2B46AB: unpack_entry (packfile.c:1768)\n> | | | | ->40.48% (826,445,820B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)\n> | | | | ->40.48% (826,445,820B) 0x2B4A23: packed_object_info (packfile.c:1516)\n> | | | | ->40.48% (826,445,820B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n> | | | | ->40.48% (826,445,820B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n> | | | | ->40.48% (826,445,820B) 0x29EDC3: read_object (object-file.c:1671)\n> | | | | ->40.48% (826,445,820B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n> | | | | ->40.12% (819,056,147B) 0x2143BB: repo_read_object_file (object-store.h:253)\n> | | | | | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:511)\n> | | | | | ->40.12% (819,056,147B) 0x2143BB: repo_parse_commit_internal (commit.c:495)\n> | | | | | ->40.12% (819,056,147B) 0x25A747: repo_parse_commit (commit.h:90)\n> | | | | | ->40.12% (819,056,147B) 0x25A747: fsck_walk_commit (fsck.c:355)\n\nOK, so we're holding onto commit buffers after parsing them. We probably\nshould tell the parser not to do that. It's useful for git-log, etc,\nwhich are going to pretty-print the buffer, but not for this use. You\ncan set the global save_commit_buffer to do that.\n\n> | | ->08.61% (175,870,114B) 0x2B9DC3: patch_delta (patch-delta.c:36)\n> | | | ->08.61% (175,870,114B) 0x2B42EB: unpack_entry (packfile.c:1829)\n> | | | ->08.61% (175,870,114B) 0x2B4A23: cache_or_unpack_entry (packfile.c:1438)\n> | | | ->08.61% (175,870,114B) 0x2B4A23: packed_object_info (packfile.c:1516)\n> | | | ->08.61% (175,870,114B) 0x29EA83: do_oid_object_info_extended (object-file.c:1620)\n> | | | ->08.61% (175,870,114B) 0x29EBDB: oid_object_info_extended (object-file.c:1639)\n> | | | ->08.61% (175,870,114B) 0x29EDC3: read_object (object-file.c:1671)\n> | | | ->08.61% (175,870,114B) 0x29EE5B: read_object_file_extended (object-file.c:1714)\n> | | | ->04.52% (92,219,588B) 0x3461CB: repo_read_object_file (object-store.h:253)\n> | | | | ->04.52% (92,219,588B) 0x3461CB: parse_tree_gently.part.0 (tree.c:132)\n> | | | | ->04.52% (92,219,588B) 0x25A4EB: parse_tree (tree.h:24)\n> | | | | ->04.52% (92,219,588B) 0x25A4EB: fsck_walk_tree (fsck.c:307)\n\nAnd this is data we've allocated for trees. It kind of looks like\nfsck_walk_tree() never bothers to clean up the trees it parses, leaving\nthe buffers attached to the tree structs. But that can't be the case,\nbecause linux.git has something like 16GB of trees. These may be entries\nwe keep in the internal delta cache, though it should be a bit smaller\nthan what you have here (the default is 96MB; you can drop it with\ncore.deltaBaseCacheLimit, but runtime may suffer).\n\nThere's a call to free_tree_buffer() in builtin/fsck.c:traverse_one();\nthat may be what ends up freeing things. It's been a while since I've\ntraced through the call paths for fsck.\n\n> But, not having delved too deeply into the code, I wanted to ask the list if\n> anything jumps out as to why `git-fsck` consumes so much more memory than\n> `git-rev-list`--perhaps there is opportunity for improvement/optimization?\n\nThe patch below improves my peak heap (as reported by massif) for \"git\nfsck --connectivity-only\" on linux.git from ~2GB to ~1GB.\n\nBut in general, I think \"rev-list\" is a better tool for connectivity\nchecks. One problem with fsck is that it tries to read the set of\navailable objects up front, making it racy in a repository which is\nreceiving pushes, or which may be repacked (e.g., if somebody makes a\nnew object and references it, \"fsck --connectivity-only\" may fail to\nnotice the new object but will see the updated ref, and think the ref is\ncorrupt).\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex f7916f06ed..949073a00d 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -853,6 +853,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)\n \n \terrors_found = 0;\n \tread_replace_refs = 0;\n+\tsave_commit_buffer = 0;\n \n \targc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);\n \n\n-Peff\n"},{"id":"463432","messageId":"Yyw0PSVe3YTQGgRS@coredump.intra.peff.net","threadId":"58475","inReplyTo":"YyoljwDIn7PxRlC9@coredump.intra.peff.net","subject":"[PATCH 0/3] reducing fsck memory usage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T10:09:01Z","receivedAt":"2022-09-22T10:09:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 20, 2022 at 04:41:51PM -0400, Jeff King wrote:\n\n> And this is data we've allocated for trees. It kind of looks like\n> fsck_walk_tree() never bothers to clean up the trees it parses, leaving\n> the buffers attached to the tree structs. But that can't be the case,\n> because linux.git has something like 16GB of trees. These may be entries\n> we keep in the internal delta cache, though it should be a bit smaller\n> than what you have here (the default is 96MB; you can drop it with\n> core.deltaBaseCacheLimit, but runtime may suffer).\n> \n> There's a call to free_tree_buffer() in builtin/fsck.c:traverse_one();\n> that may be what ends up freeing things. It's been a while since I've\n> traced through the call paths for fsck.\n\nI dug into this a bit more. We do indeed free the trees correctly in\nmost of the code paths, but there's one where we don't, and you can\nconvince it to hold all of the trees in memory at once (though in\npractice few people are likely to hit this case).\n\nSo here's a fix for that, plus a cleaned up version of the patch I sent\nearlier which should drop your memory usage, plus a bonus small memory\nreduction and cleanup in the third patch.\n\n [1/3]: fsck: free tree buffers after walking unreachable objects\n [2/3]: fsck: turn off save_commit_buffer\n [3/3]: parse_object_buffer(): respect save_commit_buffer\n\n builtin/fsck.c | 6 +++---\n object.c | 3 ++-\n 2 files changed, 5 insertions(+), 4 deletions(-)\n\n-Peff\n"},{"id":"463433","messageId":"Yyw031PqCyYlEqCX@coredump.intra.peff.net","threadId":"58475","inReplyTo":"Yyw0PSVe3YTQGgRS@coredump.intra.peff.net","subject":"[PATCH 1/3] fsck: free tree buffers after walking unreachable objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T10:11:43Z","receivedAt":"2022-09-22T10:11:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"After calling fsck_walk(), a tree object struct may be left in the\nparsed state, with the full tree contents available via tree->buffer.\nIt's the responsibility of the caller to free these when it's done with\nthe object to avoid having many trees allocated at once.\n\nIn a regular \"git fsck\", we hit fsck_walk() only from fsck_obj(), which\ndoes call free_tree_buffer(). Likewise for \"--connectivity-only\", we see\nmost objects via traverse_one_object(), which makes a similar call.\n\nThe exception is in mark_unreachable_referents(). When using both\n\"--connectivity-only\" and \"--dangling\" (the latter of which is the\ndefault), we walk all of the unreachable objects, and there we forget to\nfree. Most cases would not notice this, because they don't have a lot of\nunreachable objects, but you can make a pathological case like this:\n\n git clone --bare /path/to/linux.git repo.git\n cd repo.git\n rm packed-refs ;# now everything is unreachable!\n git fsck --connectivity-only\n\nThat ends up with peak heap usage ~18GB, which is (not coincidentally)\nclose to the size of all uncompressed trees in the repository. After\nthis patch, the peak heap is only ~2GB.\n\nA few things to note:\n\n - it might seem like fsck_walk(), if it is parsing the trees, should\n be responsible for freeing them. But the situation is quite tricky.\n In the non-connectivity mode, after we call fsck_walk() we then\n proceed with fsck_object() which actually does the type-specific\n sanity checks on the object contents. We do pass our own separate\n buffer to fsck_object(), but there's a catch: our earlier call to\n parse_object_buffer() may have attached that buffer to the object\n struct! So by freeing it, we leave the rest of the code with a\n dangling pointer.\n\n Likewise, the call to fsck_walk() in index-pack is subtle. It\n attaches a buffer to the tree object that must not be freed! And\n so rather than calling free_tree_buffer(), it actually detaches it\n by setting tree->buffer to NULL.\n\n These cases would _probably_ be fixable by having fsck_walk() free\n the tree buffer only when it was the one who allocated it via\n parse_tree(). But that would still leave the callers responsible for\n freeing other cases, so they wouldn't be simplified. While the\n current semantics for fsck_walk() make it easy to accidentally leak\n in new callers, at least they are simple to explain, and it's not a\n function that's likely to get a lot of new call-sites.\n\n And in any case, it's probably sensible to fix the leak first with\n this simple patch, and try any more complicated refactoring\n separately.\n\n - a careful reader may notice that fsck_obj() also frees commit\n buffers, but neither the call in traverse_one_object() nor the one\n touched in this patch does so. And indeed, this is another problem\n for --connectivity-only (and accounts for most of the 2GB heap after\n this patch), but it's one we'll fix in a separate commit.\n\nSigned-off-by: Jeff King \n---\n builtin/fsck.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex f7916f06ed..34e575a170 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)\n \n \toptions.walk = mark_used;\n \tfsck_walk(obj, NULL, &options);\n+\tif (obj->type == OBJ_TREE)\n+\t\tfree_tree_buffer((struct tree *)obj);\n }\n \n static int mark_loose_unreachable_referents(const struct object_id *oid,\n-- \n2.38.0.rc1.583.ga560cd8328\n\n"},{"id":"463434","messageId":"Yyw1UIhhj5zVtl1T@coredump.intra.peff.net","threadId":"58475","inReplyTo":"Yyw0PSVe3YTQGgRS@coredump.intra.peff.net","subject":"[PATCH 2/3] fsck: turn off save_commit_buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T10:13:36Z","receivedAt":"2022-09-22T10:14:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When parsing a commit, the default behavior is to stuff the original\nbuffer into a commit_slab (which takes ownership of it). But for a tool\nlike fsck, this isn't useful. While we may look at the buffer further as\npart of fsck_commit(), we'll always do so through a separate pointer;\nattaching the buffer to the slab doesn't help.\n\nWorse, it means we have to remember to free the commit buffer in all\ncall paths. We do so in fsck_obj(), which covers a regular \"git fsck\".\nBut with \"--connectivity-only\", we forget to do so in both\ntraverse_one_object(), which covers reachable objects, and\nmark_unreachable_referents(), which covers unreachable ones. As a\nresult, that mode ends up storing an uncompressed copy of every commit\non the heap at once.\n\nWe could teach the code paths for --connectivity-only to also free\ncommit buffers. But there's an even easier fix: we can just turn off the\nsave_commit_buffer flag, and then we won't attach them to the commits in\nthe first place.\n\nThis reduces the peak heap of running \"git fsck --connectivity-only\" in\na clone of linux.git from ~2GB to ~1GB. According to massif, the\nremaining memory goes where you'd expect: the object structs themselves,\nthe obj_hash containing them, and the delta base cache.\n\nNote that we'll leave the call to free commit buffers in fsck_obj() for\nnow; it's not quite redundant because of a related bug that we'll fix in\na subsequent commit.\n\nSigned-off-by: Jeff King \n---\n builtin/fsck.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 34e575a170..b45de003d4 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -855,6 +855,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)\n \n \terrors_found = 0;\n \tread_replace_refs = 0;\n+\tsave_commit_buffer = 0;\n \n \targc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);\n \n-- \n2.38.0.rc1.583.ga560cd8328\n\n"},{"id":"463435","messageId":"Yyw1ytQv35+m76VC@coredump.intra.peff.net","threadId":"58475","inReplyTo":"Yyw0PSVe3YTQGgRS@coredump.intra.peff.net","subject":"[PATCH 3/3] parse_object_buffer(): respect save_commit_buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T10:15:38Z","receivedAt":"2022-09-22T10:15:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If the global variable \"save_commit_buffer\" is set to 0, then\nparse_commit() will throw away the commit object data after parsing it,\nrather than sticking it into a commit slab. This goes all the way back\nto 60ab26de99 ([PATCH] Avoid wasting memory in git-rev-list,\n2005-09-15).\n\nBut there's another code path which may similarly stash the buffer:\nparse_object_buffer(). This is where we end up if we parse a commit via\nparse_object(), and it's used directly in a few other code paths like\ngit-fsck.\n\nThe original goal of 60ab26de99 was avoiding extra memory usage for\nrev-list. And there it's not all that important to catch parse_object().\nWe use that function only for looking at the tips of the traversal, and\nthe majority of the commits are parsed by following parent links, where\nwe use parse_commit() directly. So we were wasting some memory, but only\na small portion.\n\nIt's much easier to see the effect with fsck. Since we now turn off\nsave_commit_buffer by default there, we _should_ be able to drop the\nfreeing of the commit buffer in fsck_obj(). But if we do so (taking the\nfirst hunk of this patch without the rest), then the peak heap of \"git\nfsck\" in a clone of git.git goes from 136MB to 194MB. Teaching\nparse_object_buffer() to respect save_commit_buffer brings that down to\n134.5MB (it's hard to tell from massif's output, but I suspect the\nsavings comes from avoiding the overhead of the mostly-empty commit\nslab).\n\nOther programs should see a small improvement. Both \"rev-list --all\" and\n\"fsck --connectivity-only\" improve by a few hundred kilobytes, as they'd\navoid loading the tip objects of their traversals.\n\nMost importantly, no code should be hurt by doing this. Any program that\nturns off save_commit_buffer is already making the assumption that any\ncommit it sees may need to have its object data loaded on demand, as it\ndoesn't know which ones were parsed by parse_commit() versus\nparse_object(). Not to mention that anything parsed by the commit graph\nmay be in the same boat, even if save_commit_buffer was not disabled.\n\nThis should be the only spot that needs to be fixed. Grepping for\nset_commit_buffer() shows that this and parse_commit() are the only\nrelevant calls.\n\nSigned-off-by: Jeff King \n---\n builtin/fsck.c | 3 ---\n object.c | 3 ++-\n 2 files changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex b45de003d4..41acbc229e 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -439,9 +439,6 @@ static int fsck_obj(struct object *obj, void *buffer, unsigned long size)\n out:\n \tif (obj->type == OBJ_TREE)\n \t\tfree_tree_buffer((struct tree *)obj);\n-\tif (obj->type == OBJ_COMMIT)\n-\t\tfree_commit_buffer(the_repository->parsed_objects,\n-\t\t\t\t (struct commit *)obj);\n \treturn err;\n }\n \ndiff --git a/object.c b/object.c\nindex 2e4589bae5..8a74eb85e9 100644\n--- a/object.c\n+++ b/object.c\n@@ -233,7 +233,8 @@ struct object *parse_object_buffer(struct repository *r, const struct object_id\n \t\tif (commit) {\n \t\t\tif (parse_commit_buffer(r, commit, buffer, size, 1))\n \t\t\t\treturn NULL;\n-\t\t\tif (!get_cached_commit_buffer(r, commit, NULL)) {\n+\t\t\tif (save_commit_buffer &&\n+\t\t\t !get_cached_commit_buffer(r, commit, NULL)) {\n \t\t\t\tset_commit_buffer(r, commit, buffer, size);\n \t\t\t\t*eaten_p = 1;\n \t\t\t}\n-- \n2.38.0.rc1.583.ga560cd8328\n"},{"id":"463459","messageId":"xmqqa66rz20q.fsf@gitster.g","threadId":"58475","inReplyTo":"Yyw031PqCyYlEqCX@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-09-22T18:40:05Z","receivedAt":"2022-09-22T18:40:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> After calling fsck_walk(), a tree object struct may be left in the\n> parsed state, with the full tree contents available via tree->buffer.\n> It's the responsibility of the caller to free these when it's done with\n> the object to avoid having many trees allocated at once.\n>\n> In a regular \"git fsck\", we hit fsck_walk() only from fsck_obj(), which\n> does call free_tree_buffer(). Likewise for \"--connectivity-only\", we see\n> most objects via traverse_one_object(), which makes a similar call.\n>\n> The exception is in mark_unreachable_referents(). When using both\n> \"--connectivity-only\" and \"--dangling\" (the latter of which is the\n> default), we walk all of the unreachable objects, and there we forget to\n> free. Most cases would not notice this, because they don't have a lot of\n> unreachable objects, but you can make a pathological case like this:\n>\n> git clone --bare /path/to/linux.git repo.git\n> cd repo.git\n> rm packed-refs ;# now everything is unreachable!\n> git fsck --connectivity-only\n>\n> That ends up with peak heap usage ~18GB, which is (not coincidentally)\n> close to the size of all uncompressed trees in the repository. After\n> this patch, the peak heap is only ~2GB.\n>\n> A few things to note:\n>\n> - it might seem like fsck_walk(), if it is parsing the trees, should\n> be responsible for freeing them. But the situation is quite tricky.\n> In the non-connectivity mode, after we call fsck_walk() we then\n> proceed with fsck_object() which actually does the type-specific\n> sanity checks on the object contents. We do pass our own separate\n> buffer to fsck_object(), but there's a catch: our earlier call to\n> parse_object_buffer() may have attached that buffer to the object\n> struct! So by freeing it, we leave the rest of the code with a\n> dangling pointer.\n>\n> Likewise, the call to fsck_walk() in index-pack is subtle. It\n> attaches a buffer to the tree object that must not be freed! And\n> so rather than calling free_tree_buffer(), it actually detaches it\n> by setting tree->buffer to NULL.\n>\n> These cases would _probably_ be fixable by having fsck_walk() free\n> the tree buffer only when it was the one who allocated it via\n> parse_tree(). But that would still leave the callers responsible for\n> freeing other cases, so they wouldn't be simplified. While the\n> current semantics for fsck_walk() make it easy to accidentally leak\n> in new callers, at least they are simple to explain, and it's not a\n> function that's likely to get a lot of new call-sites.\n>\n> And in any case, it's probably sensible to fix the leak first with\n> this simple patch, and try any more complicated refactoring\n> separately.\n>\n> - a careful reader may notice that fsck_obj() also frees commit\n> buffers, but neither the call in traverse_one_object() nor the one\n> touched in this patch does so. And indeed, this is another problem\n> for --connectivity-only (and accounts for most of the 2GB heap after\n> this patch), but it's one we'll fix in a separate commit.\n>\n> Signed-off-by: Jeff King \n> ---\n> builtin/fsck.c | 2 ++\n> 1 file changed, 2 insertions(+)\n>\n> diff --git a/builtin/fsck.c b/builtin/fsck.c\n> index f7916f06ed..34e575a170 100644\n> --- a/builtin/fsck.c\n> +++ b/builtin/fsck.c\n> @@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)\n> \n> \toptions.walk = mark_used;\n> \tfsck_walk(obj, NULL, &options);\n> +\tif (obj->type == OBJ_TREE)\n> +\t\tfree_tree_buffer((struct tree *)obj);\n> }\n\nUnlike codepaths like mark_object(), which uses the REACHABLE bit to\navoid the walker coming into an already marked objects, we have no\nprotection that says \"this tree is already marked as USED, so lets\nnot go into its contents\" (it would be a disaster if we free tree\nbuffer here and then later end up calling the function on the same\ntree), but it is OK because this is an unreachable object nobody\npoints at and we will never come back?\n"},{"id":"463462","messageId":"YyywSdrWO61Kza0e@coredump.intra.peff.net","threadId":"58475","inReplyTo":"xmqqa66rz20q.fsf@gitster.g","subject":"Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T18:58:17Z","receivedAt":"2022-09-22T18:58:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 22, 2022 at 11:40:05AM -0700, Junio C Hamano wrote:\n\n> > diff --git a/builtin/fsck.c b/builtin/fsck.c\n> > index f7916f06ed..34e575a170 100644\n> > --- a/builtin/fsck.c\n> > +++ b/builtin/fsck.c\n> > @@ -228,6 +228,8 @@ static void mark_unreachable_referents(const struct object_id *oid)\n> > \n> > \toptions.walk = mark_used;\n> > \tfsck_walk(obj, NULL, &options);\n> > +\tif (obj->type == OBJ_TREE)\n> > +\t\tfree_tree_buffer((struct tree *)obj);\n> > }\n> \n> Unlike codepaths like mark_object(), which uses the REACHABLE bit to\n> avoid the walker coming into an already marked objects, we have no\n> protection that says \"this tree is already marked as USED, so lets\n> not go into its contents\" (it would be a disaster if we free tree\n> buffer here and then later end up calling the function on the same\n> tree), but it is OK because this is an unreachable object nobody\n> points at and we will never come back?\n\nI do think it is true that this is the final time we'd look at these\nobjects. But I don't think it would be a disaster if somebody did. The\nfree_tree_buffer() function clears the \"parsed\" flag on the struct. And\nanybody wishing to look at the tree contents would need to call\nparse_tree(), which would then re-load the contents.\n\nIn general, that's _possibly_ less efficient if we visit the same tree\ntwice, but it would be balanced against not holding all of the tree data\nin RAM at once. And as I said, that doesn't happen for this use case\nanyway.\n\nAs a side note, IMHO having tree->buffer at all is a mistake, because it\nleads to exactly this kind of confusion about when the buffer should be\ndiscarded. We'd be better off having all callers parse directly into a\nlocal buffer, and then clean up when they're done. It effectively ends\nup the same, except then it's obvious when a tree is \"leaked\" because\nthe local buffer goes out of scope, rather than hanging around in the\nglobal struct and just wasting memory. But that's obviously a much\nbigger change.\n\n-Peff\n"},{"id":"463466","messageId":"xmqq5yhfyztm.fsf@gitster.g","threadId":"58475","inReplyTo":"YyywSdrWO61Kza0e@coredump.intra.peff.net","subject":"Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-09-22T19:27:33Z","receivedAt":"2022-09-22T19:27:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I do think it is true that this is the final time we'd look at these\n> objects. But I don't think it would be a disaster if somebody did. The\n> free_tree_buffer() function clears the \"parsed\" flag on the struct. \n\nAh, that is perfectly fine, then. Thanks.\n\n> As a side note, IMHO having tree->buffer at all is a mistake, because it\n> leads to exactly this kind of confusion about when the buffer should be\n> discarded. We'd be better off having all callers parse directly into a\n> local buffer, and then clean up when they're done.\n\nYeah, tree-walk.c users woud use tree_desc structure anyway, and\ninstead of having a moving pointer that points into a separate thing\n(i.e. tree->buffer), it could have its own copy of the \"whole buffer\"\nthat can be used to free when it is done iterating over entries.\n\n> .... But that's obviously a much bigger change.\n\nYup.\n\nThanks.\n"},{"id":"463480","messageId":"YyzerG/hXFCsI7Lt@coredump.intra.peff.net","threadId":"58475","inReplyTo":"xmqq5yhfyztm.fsf@gitster.g","subject":"Re: [PATCH 1/3] fsck: free tree buffers after walking unreachable objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-09-22T22:16:12Z","receivedAt":"2022-09-22T22:16:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 22, 2022 at 12:27:33PM -0700, Junio C Hamano wrote:\n\n> > As a side note, IMHO having tree->buffer at all is a mistake, because it\n> > leads to exactly this kind of confusion about when the buffer should be\n> > discarded. We'd be better off having all callers parse directly into a\n> > local buffer, and then clean up when they're done.\n> \n> Yeah, tree-walk.c users woud use tree_desc structure anyway, and\n> instead of having a moving pointer that points into a separate thing\n> (i.e. tree->buffer), it could have its own copy of the \"whole buffer\"\n> that can be used to free when it is done iterating over entries.\n> \n> > .... But that's obviously a much bigger change.\n> \n> Yup.\n\nI took a (very) brief stab at this, out of curiosity. The sticking point\nbecomes obvious very quickly: how do we get the buffer to the caller? If\nyou are calling parse_tree(), we can add new out-parameters to provide\nthe buffer. But something like parse_object() is just returning an\nobject struct, and we have to stuff anything we want to communicate to\nthe caller inside the polymorphic struct which contains it.\n\nWe could split the concept of \"parse\" away from \"get the buffer\"\nentirely, but then we have a potential slowdown. The \"parse\" functions\nreally want to open the object contents and check the hash (and removing\nthat in the general case would probably break part of fsck, at least).\nSo we'd end up inflating the object contents twice, which would probably\nhave a measurable impact.\n\nI don't plan on digging any further on it for now, so this is just a\nnote for future people who do. :)\n\n-Peff\n"}]}