{"thread":{"id":"46999","subject":"[PATCH/RFC] grep: turn off threading when recursing submodules","startedAt":"2017-10-19T19:07:26Z","lastAt":"2017-11-01T21:12:17Z","messageCount":7,"participants":["Martin Ågren","Brandon Williams","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"330661","messageId":"20171019190703.1534-1-martin.agren@gmail.com","threadId":"46999","inReplyTo":null,"subject":"[PATCH/RFC] grep: turn off threading when recursing submodules","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2017-10-19T19:07:03Z","receivedAt":"2017-10-19T19:07:26Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"With --recurse-submodules, we use the machinery for alternate object\ndatabases and pretend that the repository is an alternate ODB. This has\nsome drawbacks since the list of alternates is global and will grow as\nwe proceed. Still, that's a problem with performance, not correctness.\nThe other immediately available option is to spawn an external process.\nWe actually used to do this until f9ee2fcdf (grep: recurse in-process\nusing 'struct repository', 2017-08-02).\n\nSo, as we encounter submodules during our recursing, we add them to the\nlist of ODBs. But with threading, our changes to the list are not\nprotected against races. Indeed, ThreadSanitizer reports a problem in\nthis area with t7814.\n\nThe race which ThreadSanitizer detects is that `grep_submodule()` calls\n`add_to_alternates_memory()` around the same time that\n`grep_source_load_oid()` ends up calling `prepare_packed_git()`. A\nsimilar race might occur if two threads encounter a submodule each at\nthe same time and add them to the list of ODBs. This might end up losing\none of them and could give incorrect results.\n\nTurn off threading when we're recursing submodules to avoid this race.\nLong term, a better approach will be to address the existing NEEDSWORK\nin builtin/grep.c to introduce per-repo object stores. Then we should be\nable to revert this commit.\n\nAlternatively, we could equip the list with a mutex (or maybe do some\nlock-less cleverness), but it seems a bit sad considering it shouldn't\nreally be needed: the list of ODBs would normally be fully populated\nbefore we start using it.\n\nAnother approach would be to first recurse the submodules and collect\nthe ODBs, then recurse again to do the actual grepping. That would be a\nmore involved change. Or, we could revert f9ee2fcdf. That would hurt\nthose who do not use threading.\n\nSigned-off-by: Martin Ågren <martin.agren@gmail.com>\n---\nThis is a simple, stupid solution. I'm posting this in patch-form so\nthat I can do one better than just mailing about the race and waving my\nhands. Maybe threading is common enough that reverting could be a better\napproach. Or implementing some (optional) locking...\n\nOutput from ThreadSanitizer below the patch.\n\n builtin/grep.c | 9 +++++++++\n 1 file changed, 9 insertions(+)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 2d65f27d0..29f79104d 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -1023,6 +1023,15 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n \t\tdie(_(\"invalid number of threads specified (%d)\"), num_threads);\n \tif (num_threads == 1)\n \t\tnum_threads = 0;\n+\t/*\n+\t * NEEDSWORK: When we recurse through submodules we misuse the\n+\t * alt-odb-mechanism (alternate object databases). Doing so may hit\n+\t * data-races if we are threading. This can be removed once the object\n+\t * store is no longer global and instead is a member of the repository\n+\t * object.\n+\t */\n+\tif (recurse_submodules)\n+\t\tnum_threads = 0;\n #else\n \tif (num_threads)\n \t\twarning(_(\"no threads support, ignoring --threads\"));\n-- \nWARNING: ThreadSanitizer: data race (pid=27207)\n  Write of size 8 at 0x7d4c0000de40 by main thread:\n    #0 link_alt_odb_entry sha1_file.c:361\n    #1 link_alt_odb_entries.lto_priv.1377 sha1_file.c:422\n    #2 add_to_alternates_memory sha1_file.c:510\n    #3 grep_submodule builtin/grep.c:434\n    #4 grep_cache builtin/grep.c:508\n    #5 grep_submodule builtin/grep.c:462\n    #6 grep_cache builtin/grep.c:508\n    #7 cmd_grep builtin/grep.c:1092\n    #8 run_builtin git.c:346\n    #9 handle_builtin.lto_priv.1929 git.c:554\n    #10 run_argv git.c:606\n    #11 cmd_main git.c:683\n    #12 main common-main.c:43\n\n  Previous read of size 8 at 0x7d4c0000de40 by thread T4 (mutexes: write\nM6):\n    #0 prepare_packed_git.part.9.lto_priv.953 packfile.c:883\n    #1 prepare_packed_git packfile.c:289\n    #2 find_pack_entry packfile.c:1836\n    #3 sha1_object_info_extended sha1_file.c:1179\n    #4 read_object.lto_priv.900 packfile.c:1453\n    #5 read_sha1_file_extended.constprop.779 sha1_file.c:1279\n    #6 read_sha1_file cache.h:1162\n    #7 grep_source_load_oid grep.c:1966\n    #8 grep_source_load grep.c:2019\n    #9 grep_source_is_binary grep.c:2045\n    #10 grep_source_1 grep.c:1689\n    #11 grep_source grep.c:1897\n    #12 run builtin/grep.c:183\n    #13 <null> <null>\n\n  Location is heap block of size 408 at 0x7d4c0000de40 allocated by main\nthread:\n    #0 calloc <null>\n    #1 xcalloc.constprop.820 wrapper.c:160\n    #2 alloc_alt_odb sha1_file.c:449\n    #3 link_alt_odb_entry sha1_file.c:358\n    #4 link_alt_odb_entries.lto_priv.1377 sha1_file.c:422\n    #5 add_to_alternates_memory sha1_file.c:510\n    #6 grep_submodule builtin/grep.c:434\n    #7 grep_cache builtin/grep.c:508\n    #8 cmd_grep builtin/grep.c:1092\n    #9 run_builtin git.c:346\n    #10 handle_builtin.lto_priv.1929 git.c:554\n    #11 run_argv git.c:606\n    #12 cmd_main git.c:683\n    #13 main common-main.c:43\n\n  Mutex M6 (0x000000959340) created at:\n    #0 pthread_mutex_init <null>\n    #1 start_threads builtin/grep.c:204\n    #2 cmd_grep builtin/grep.c:1047\n    #3 run_builtin git.c:346\n    #4 handle_builtin.lto_priv.1929 git.c:554\n    #5 run_argv git.c:606\n    #6 cmd_main git.c:683\n    #7 main common-main.c:43\n\n  Thread T4 (tid=27212, running) created by main thread at:\n    #0 pthread_create <null>\n    #1 start_threads builtin/grep.c:223\n    #2 cmd_grep builtin/grep.c:1047\n    #3 run_builtin git.c:346\n    #4 handle_builtin.lto_priv.1929 git.c:554\n    #5 run_argv git.c:606\n    #6 cmd_main git.c:683\n    #7 main common-main.c:43\n\nSUMMARY: ThreadSanitizer: data race sha1_file.c:361 link_alt_odb_entry\n\n-- \n2.15.0.rc1.71.g1477d2401\n\n"},{"id":"330663","messageId":"20171019192618.GB84767@google.com","threadId":"46999","inReplyTo":"20171019190703.1534-1-martin.agren@gmail.com","subject":"Re: [PATCH/RFC] grep: turn off threading when recursing submodules","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-10-19T19:26:18Z","receivedAt":"2017-10-19T19:26:26Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 10/19, Martin Ågren wrote:\n> With --recurse-submodules, we use the machinery for alternate object\n> databases and pretend that the repository is an alternate ODB. This has\n> some drawbacks since the list of alternates is global and will grow as\n> we proceed. Still, that's a problem with performance, not correctness.\n> The other immediately available option is to spawn an external process.\n> We actually used to do this until f9ee2fcdf (grep: recurse in-process\n> using 'struct repository', 2017-08-02).\n>\n> So, as we encounter submodules during our recursing, we add them to the\n> list of ODBs. But with threading, our changes to the list are not\n> protected against races. Indeed, ThreadSanitizer reports a problem in\n> this area with t7814.\n>\n> The race which ThreadSanitizer detects is that `grep_submodule()` calls\n> `add_to_alternates_memory()` around the same time that\n> `grep_source_load_oid()` ends up calling `prepare_packed_git()`. A\n> similar race might occur if two threads encounter a submodule each at\n> the same time and add them to the list of ODBs. This might end up losing\n> one of them and could give incorrect results.\n>\n> Turn off threading when we're recursing submodules to avoid this race.\n> Long term, a better approach will be to address the existing NEEDSWORK\n> in builtin/grep.c to introduce per-repo object stores. Then we should be\n> able to revert this commit.\n>\n> Alternatively, we could equip the list with a mutex (or maybe do some\n> lock-less cleverness), but it seems a bit sad considering it shouldn't\n> really be needed: the list of ODBs would normally be fully populated\n> before we start using it.\n>\n> Another approach would be to first recurse the submodules and collect\n> the ODBs, then recurse again to do the actual grepping. That would be a\n> more involved change. Or, we could revert f9ee2fcdf. That would hurt\n> those who do not use threading.\n>\n> Signed-off-by: Martin Ågren <martin.agren@gmail.com>\n> ---\n> This is a simple, stupid solution. I'm posting this in patch-form so\n> that I can do one better than just mailing about the race and waving my\n> hands. Maybe threading is common enough that reverting could be a better\n> approach. Or implementing some (optional) locking...\n>\n> Output from ThreadSanitizer below the patch.\n\nThanks for finding this mistake of mine.  I would think that even after\nmoving towards removing the 'add_to_alternates_memory()' calls and\ninstead having the object store embedded in the repository struct we\nwould still need to use locking to ensure that multiple threads are able\nto read from the object store properly (because even now two threads\ncan't read from it without a lock).\n\nOne alternative to turning off threading would be to employ proper\nlocking (like I failed to do) by wrapping the call the\n'add_to_alternates_memory()' in calls to grep_read_lock/unlock:\n\n  +       grep_read_lock();\n          add_to_alternates_memory(submodule.objectdir);\n  +       grep_read_unlock();\n\nThat way adding the submodule to the object database won't happen at the\nsame time another thread is trying to read from the object store.\n\n>\n>  builtin/grep.c | 9 +++++++++\n>  1 file changed, 9 insertions(+)\n>\n> diff --git a/builtin/grep.c b/builtin/grep.c\n> index 2d65f27d0..29f79104d 100644\n> --- a/builtin/grep.c\n> +++ b/builtin/grep.c\n> @@ -1023,6 +1023,15 @@ int cmd_grep(int argc, const char **argv, const char *prefix)\n>  \t\tdie(_(\"invalid number of threads specified (%d)\"), num_threads);\n>  \tif (num_threads == 1)\n>  \t\tnum_threads = 0;\n> +\t/*\n> +\t * NEEDSWORK: When we recurse through submodules we misuse the\n> +\t * alt-odb-mechanism (alternate object databases). Doing so may hit\n> +\t * data-races if we are threading. This can be removed once the object\n> +\t * store is no longer global and instead is a member of the repository\n> +\t * object.\n> +\t */\n> +\tif (recurse_submodules)\n> +\t\tnum_threads = 0;\n>  #else\n>  \tif (num_threads)\n>  \t\twarning(_(\"no threads support, ignoring --threads\"));\n> --\n> WARNING: ThreadSanitizer: data race (pid=27207)\n>   Write of size 8 at 0x7d4c0000de40 by main thread:\n>     #0 link_alt_odb_entry sha1_file.c:361\n>     #1 link_alt_odb_entries.lto_priv.1377 sha1_file.c:422\n>     #2 add_to_alternates_memory sha1_file.c:510\n>     #3 grep_submodule builtin/grep.c:434\n>     #4 grep_cache builtin/grep.c:508\n>     #5 grep_submodule builtin/grep.c:462\n>     #6 grep_cache builtin/grep.c:508\n>     #7 cmd_grep builtin/grep.c:1092\n>     #8 run_builtin git.c:346\n>     #9 handle_builtin.lto_priv.1929 git.c:554\n>     #10 run_argv git.c:606\n>     #11 cmd_main git.c:683\n>     #12 main common-main.c:43\n>\n>   Previous read of size 8 at 0x7d4c0000de40 by thread T4 (mutexes: write\n> M6):\n>     #0 prepare_packed_git.part.9.lto_priv.953 packfile.c:883\n>     #1 prepare_packed_git packfile.c:289\n>     #2 find_pack_entry packfile.c:1836\n>     #3 sha1_object_info_extended sha1_file.c:1179\n>     #4 read_object.lto_priv.900 packfile.c:1453\n>     #5 read_sha1_file_extended.constprop.779 sha1_file.c:1279\n>     #6 read_sha1_file cache.h:1162\n>     #7 grep_source_load_oid grep.c:1966\n>     #8 grep_source_load grep.c:2019\n>     #9 grep_source_is_binary grep.c:2045\n>     #10 grep_source_1 grep.c:1689\n>     #11 grep_source grep.c:1897\n>     #12 run builtin/grep.c:183\n>     #13 <null> <null>\n>\n>   Location is heap block of size 408 at 0x7d4c0000de40 allocated by main\n> thread:\n>     #0 calloc <null>\n>     #1 xcalloc.constprop.820 wrapper.c:160\n>     #2 alloc_alt_odb sha1_file.c:449\n>     #3 link_alt_odb_entry sha1_file.c:358\n>     #4 link_alt_odb_entries.lto_priv.1377 sha1_file.c:422\n>     #5 add_to_alternates_memory sha1_file.c:510\n>     #6 grep_submodule builtin/grep.c:434\n>     #7 grep_cache builtin/grep.c:508\n>     #8 cmd_grep builtin/grep.c:1092\n>     #9 run_builtin git.c:346\n>     #10 handle_builtin.lto_priv.1929 git.c:554\n>     #11 run_argv git.c:606\n>     #12 cmd_main git.c:683\n>     #13 main common-main.c:43\n>\n>   Mutex M6 (0x000000959340) created at:\n>     #0 pthread_mutex_init <null>\n>     #1 start_threads builtin/grep.c:204\n>     #2 cmd_grep builtin/grep.c:1047\n>     #3 run_builtin git.c:346\n>     #4 handle_builtin.lto_priv.1929 git.c:554\n>     #5 run_argv git.c:606\n>     #6 cmd_main git.c:683\n>     #7 main common-main.c:43\n>\n>   Thread T4 (tid=27212, running) created by main thread at:\n>     #0 pthread_create <null>\n>     #1 start_threads builtin/grep.c:223\n>     #2 cmd_grep builtin/grep.c:1047\n>     #3 run_builtin git.c:346\n>     #4 handle_builtin.lto_priv.1929 git.c:554\n>     #5 run_argv git.c:606\n>     #6 cmd_main git.c:683\n>     #7 main common-main.c:43\n>\n> SUMMARY: ThreadSanitizer: data race sha1_file.c:361 link_alt_odb_entry\n>\n> --\n> 2.15.0.rc1.71.g1477d2401\n>\n\n--\nBrandon Williams\n"},{"id":"330665","messageId":"20171019193413.prx5pkmwaxk6mpdt@sigill.intra.peff.net","threadId":"46999","inReplyTo":"20171019192618.GB84767@google.com","subject":"Re: [PATCH/RFC] grep: turn off threading when recursing submodules","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-19T19:34:13Z","receivedAt":"2017-10-19T19:34:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 19, 2017 at 12:26:18PM -0700, Brandon Williams wrote:\n\n> One alternative to turning off threading would be to employ proper\n> locking (like I failed to do) by wrapping the call the\n> 'add_to_alternates_memory()' in calls to grep_read_lock/unlock:\n> \n>   +       grep_read_lock();\n>           add_to_alternates_memory(submodule.objectdir);\n>   +       grep_read_unlock();\n> \n> That way adding the submodule to the object database won't happen at the\n> same time another thread is trying to read from the object store.\n\nYeah, I think that is the right approach. Many of Git's APIs aren't\nthread-safe, so we need a big mutex around \"I am doing anything except\nactually looking at the already-read blob contents\". We just missed this\nspot.\n\n-Peff\n"},{"id":"330667","messageId":"CAN0heSpxJDxmSXu=P0stq+CsKVqjsvOnjDpOoMT9GdWxeZU2Pw@mail.gmail.com","threadId":"46999","inReplyTo":"20171019193413.prx5pkmwaxk6mpdt@sigill.intra.peff.net","subject":"Re: [PATCH/RFC] grep: turn off threading when recursing submodules","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2017-10-19T19:50:15Z","receivedAt":"2017-10-19T19:50:20Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On 19 October 2017 at 21:34, Jeff King <peff@peff.net> wrote:\n> On Thu, Oct 19, 2017 at 12:26:18PM -0700, Brandon Williams wrote:\n>\n>> One alternative to turning off threading would be to employ proper\n>> locking (like I failed to do) by wrapping the call the\n>> 'add_to_alternates_memory()' in calls to grep_read_lock/unlock:\n>>\n>>   +       grep_read_lock();\n>>           add_to_alternates_memory(submodule.objectdir);\n>>   +       grep_read_unlock();\n>>\n>> That way adding the submodule to the object database won't happen at the\n>> same time another thread is trying to read from the object store.\n>\n> Yeah, I think that is the right approach. Many of Git's APIs aren't\n> thread-safe, so we need a big mutex around \"I am doing anything except\n> actually looking at the already-read blob contents\". We just missed this\n> spot.\n\nThat's a big glaring lock I missed, right in front of me. Looks like the\nright solution!\n"},{"id":"331606","messageId":"20171101204506.5481-1-martin.agren@gmail.com","threadId":"46999","inReplyTo":"CAN0heSpxJDxmSXu=P0stq+CsKVqjsvOnjDpOoMT9GdWxeZU2Pw@mail.gmail.com","subject":"[PATCH v2] grep: take the read-lock when adding a submodule","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2017-11-01T20:45:06Z","receivedAt":"2017-11-01T20:45:33Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"With --recurse-submodules, we add each submodule that we encounter to\nthe list of alternate object databases. With threading, our changes to\nthe list are not protected against races. Indeed, ThreadSanitizer\nreports a race when we call `add_to_alternates_memory()` around the same\ntime that another thread is reading in the list through\n`read_sha1_file()`.\n\nTake the grep read-lock while adding the submodule. The lock is used to\nserialize uses of non-thread-safe parts of Git's API, including\n`read_sha1_file()`.\n\nHelped-by: Brandon Williams <bmwill@google.com>\nSigned-off-by: Martin Ågren <martin.agren@gmail.com>\n---\nMany thanks to Brandon for showing how this should have been done.\n\n builtin/grep.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 2d65f27d0..5a6cfe6b4 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -431,7 +431,9 @@ static int grep_submodule(struct grep_opt *opt, struct repository *superproject,\n \t * store is no longer global and instead is a member of the repository\n \t * object.\n \t */\n+\tgrep_read_lock();\n \tadd_to_alternates_memory(submodule.objectdir);\n+\tgrep_read_unlock();\n \n \tif (oid) {\n \t\tstruct object *object;\n-- \n2.15.0.415.gac1375d7e\n\n"},{"id":"331607","messageId":"20171101205522.GA188245@google.com","threadId":"46999","inReplyTo":"20171101204506.5481-1-martin.agren@gmail.com","subject":"Re: [PATCH v2] grep: take the read-lock when adding a submodule","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-11-01T20:55:22Z","receivedAt":"2017-11-01T20:55:30Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 11/01, Martin Ågren wrote:\n> With --recurse-submodules, we add each submodule that we encounter to\n> the list of alternate object databases. With threading, our changes to\n> the list are not protected against races. Indeed, ThreadSanitizer\n> reports a race when we call `add_to_alternates_memory()` around the same\n> time that another thread is reading in the list through\n> `read_sha1_file()`.\n> \n> Take the grep read-lock while adding the submodule. The lock is used to\n> serialize uses of non-thread-safe parts of Git's API, including\n> `read_sha1_file()`.\n> \n> Helped-by: Brandon Williams <bmwill@google.com>\n> Signed-off-by: Martin Ågren <martin.agren@gmail.com>\n> ---\n> Many thanks to Brandon for showing how this should have been done.\n\nOf course! Happy to help :)\n\nAnd this looks good, thanks for fixing my mistake!\n\n> \n>  builtin/grep.c | 2 ++\n>  1 file changed, 2 insertions(+)\n> \n> diff --git a/builtin/grep.c b/builtin/grep.c\n> index 2d65f27d0..5a6cfe6b4 100644\n> --- a/builtin/grep.c\n> +++ b/builtin/grep.c\n> @@ -431,7 +431,9 @@ static int grep_submodule(struct grep_opt *opt, struct repository *superproject,\n>  \t * store is no longer global and instead is a member of the repository\n>  \t * object.\n>  \t */\n> +\tgrep_read_lock();\n>  \tadd_to_alternates_memory(submodule.objectdir);\n> +\tgrep_read_unlock();\n>  \n>  \tif (oid) {\n>  \t\tstruct object *object;\n> -- \n> 2.15.0.415.gac1375d7e\n> \n\n-- \nBrandon Williams\n"},{"id":"331610","messageId":"20171101211159.qy2rnk7nmbaa4va3@sigill.intra.peff.net","threadId":"46999","inReplyTo":"20171101204506.5481-1-martin.agren@gmail.com","subject":"Re: [PATCH v2] grep: take the read-lock when adding a submodule","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-11-01T21:11:59Z","receivedAt":"2017-11-01T21:12:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 01, 2017 at 09:45:06PM +0100, Martin Ågren wrote:\n\n> With --recurse-submodules, we add each submodule that we encounter to\n> the list of alternate object databases. With threading, our changes to\n> the list are not protected against races. Indeed, ThreadSanitizer\n> reports a race when we call `add_to_alternates_memory()` around the same\n> time that another thread is reading in the list through\n> `read_sha1_file()`.\n> \n> Take the grep read-lock while adding the submodule. The lock is used to\n> serialize uses of non-thread-safe parts of Git's API, including\n> `read_sha1_file()`.\n> \n> Helped-by: Brandon Williams <bmwill@google.com>\n> Signed-off-by: Martin Ågren <martin.agren@gmail.com>\n\nThis looks good to me.\n\n-Peff\n"}]}