{"thread":{"id":"44763","subject":"Corner case involving null sha1, alternates, cache misses, and submodule config API","startedAt":"2016-12-25T02:39:01Z","lastAt":"2016-12-26T20:32:45Z","messageCount":2,"participants":["Mike Hommey","Stefan Beller"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"308324","messageId":"20161225022904.v2mixrnbitvlviuu@glandium.org","threadId":"44763","inReplyTo":null,"subject":"Corner case involving null sha1, alternates, cache misses, and submodule config API","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2016-12-25T02:29:04Z","receivedAt":"2016-12-25T02:39:01Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"Hi,\n\nAs you might be aware, I'm working on a mercurial remote helper for git.\nThe way it stores metadata for mercurial manifests abuses \"commit\"\nreferences in trees, which are normally used for submodules.\n\nSome operations in the helper use git diff-tree on those trees to find\nfiles faster than just using ls-tree on every commit would.\n\nAnyways, long story short, it turns out that a combination of\neverything mentioned in the subject of this email causes running git\ndiff-tree -r --stdin with a list of 300k+ pairs of commits to take 10\nminutes, when (after investigation) adding --ignore-submodules=dirty\nmade it take 1 minute instead, for the exact same 3GB output.\n\nIt turns out, this all starts in is_submodule_ignored(), which contains:\n\n        if (!DIFF_OPT_TST(options, OVERRIDE_SUBMODULE_CONFIG))\n                set_diffopt_flags_from_submodule_config(options, path);\n\nAnd set_diffopt_flags_from_submodule_config calls:\n\n        submodule_from_path(null_sha1, path);\n\nAnd because there is no actual submodule involved, at some point that\nnull_sha1 ends up in the call to read_sha1_file from\nsubmodule-config.c's config_from, which then proceeds to try to open the\nnull sha1 as a loose object in every alternate, doing multiple system\ncalls in each directory for something that is bound to fail. And to add\npain to injury, it repeats that for each and every line of input to git\ndiff-tree because the object cache doesn't care about storing negatives\n(which makes perfect sense for most cases).\n\nEven worse, when read_object returns NULL because the object doesn't\nexist, read_sha1_file_extended calls has_loose_object which does\nanother set of system calls.\n\nNow, while I realize my use case is very atypical, and that I should\njust use --ignore-submodule=dirty, the fact that using the null sha1 can\ntrigger such behavior strikes me as a footgun that would be better\navoided. Especially when you factor the fact that\nread_sha1_file_extended calls lookup_replace_object_extended, which\nsuggests one might interfere by creating a replace object for the null\nsha1. (BTW, it's not entirely clear to me, in the context of actual\nsubmodules, what the various --ignore-submodule options are supposed to\nmean for trees that are not the current HEAD ; also, the manual page say\n\"all\" is the default, but that doesn't appear to be true)\n\nFrom a cursory look at the output of `git grep \\\\bnull_sha1` it doesn't\nlook like the null sha1 is used anywhere else in a similar fashion where\nit can be attempted to be read as an object. So, one could consider this\nis something the submodule config code should handle on its own by\ntreating the null_sha1 argument to submodule_from_path (really\nconfig_from) specially. After all, gitmodule_sha1_from_commit already\navoids a get_sha1() call when it's given the null sha1.\n\nOTOH, it seems submodule_from_path and submodule_from_name, the only two\npublic functions that end up in config_from(), are *always* called with\neither the null sha1 or a literal null pointer. The *only* calls to\nthese functions that doesn't involve a null sha1 or a null pointer is\nfrom test code. So all in all, I'm not entirely sure what this sha1\nargument is all about in the first place.\n\nHowever, an argument could be made that null_sha1 should be treated\nspecially at a lower level (read_sha1_file, I guess).\n\nWhat would be sensible to do here?\n\nMike\n"},{"id":"308361","messageId":"CAGZ79kYAZ=zf8+xLDu1s4KUBhoDWbBdcO8ua4aWhfzieO4UVhA@mail.gmail.com","threadId":"44763","inReplyTo":"20161225022904.v2mixrnbitvlviuu@glandium.org","subject":"Re: Corner case involving null sha1, alternates, cache misses, and submodule config API","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-12-26T20:32:32Z","receivedAt":"2016-12-26T20:32:45Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sat, Dec 24, 2016 at 6:29 PM, Mike Hommey <mh@glandium.org> wrote:\n> Hi,\n>\n> As you might be aware, I'm working on a mercurial remote helper for git.\n> The way it stores metadata for mercurial manifests abuses \"commit\"\n> references in trees, which are normally used for submodules.\n>\n> Some operations in the helper use git diff-tree on those trees to find\n> files faster than just using ls-tree on every commit would.\n>\n> Anyways, long story short, it turns out that a combination of\n> everything mentioned in the subject of this email causes running git\n> diff-tree -r --stdin with a list of 300k+ pairs of commits to take 10\n> minutes, when (after investigation) adding --ignore-submodules=dirty\n> made it take 1 minute instead, for the exact same 3GB output.\n>\n> It turns out, this all starts in is_submodule_ignored(), which contains:\n>\n>         if (!DIFF_OPT_TST(options, OVERRIDE_SUBMODULE_CONFIG))\n>                 set_diffopt_flags_from_submodule_config(options, path);\n>\n> And set_diffopt_flags_from_submodule_config calls:\n>\n>         submodule_from_path(null_sha1, path);\n>\n> And because there is no actual submodule involved, at some point that\n> null_sha1 ends up in the call to read_sha1_file from\n> submodule-config.c's config_from, which then proceeds to try to open the\n> null sha1 as a loose object in every alternate, doing multiple system\n> calls in each directory for something that is bound to fail. And to add\n> pain to injury, it repeats that for each and every line of input to git\n> diff-tree because the object cache doesn't care about storing negatives\n> (which makes perfect sense for most cases).\n>\n> Even worse, when read_object returns NULL because the object doesn't\n> exist, read_sha1_file_extended calls has_loose_object which does\n> another set of system calls.\n>\n> Now, while I realize my use case is very atypical, and that I should\n> just use --ignore-submodule=dirty, the fact that using the null sha1 can\n> trigger such behavior strikes me as a footgun that would be better\n> avoided. Especially when you factor the fact that\n> read_sha1_file_extended calls lookup_replace_object_extended, which\n> suggests one might interfere by creating a replace object for the null\n> sha1. (BTW, it's not entirely clear to me, in the context of actual\n> submodules, what the various --ignore-submodule options are supposed to\n> mean for trees that are not the current HEAD ; also, the manual page say\n> \"all\" is the default, but that doesn't appear to be true)\n\nI think at this high level we should start optimizing submodules, i.e.\nnot HEAD / working tree -> select less aggressive submodule config.\n\n>\n> From a cursory look at the output of `git grep \\\\bnull_sha1` it doesn't\n> look like the null sha1 is used anywhere else in a similar fashion where\n> it can be attempted to be read as an object. So, one could consider this\n> is something the submodule config code should handle on its own by\n> treating the null_sha1 argument to submodule_from_path (really\n> config_from) specially. After all, gitmodule_sha1_from_commit already\n> avoids a get_sha1() call when it's given the null sha1.\n>\n> OTOH, it seems submodule_from_path and submodule_from_name, the only two\n> public functions that end up in config_from(), are *always* called with\n> either the null sha1 or a literal null pointer.\n\nWhen Heiko introduced the submodule config, the consensus\nwas to have a flexible API to lookup submodule configuration.\nThe sha1 argument defines where to lookup the submodule\nconfig (e.g. you could have moved a submodule such that the\nsubmodule_from_path returns a different submodule for HEAD^\nthan HEAD.\n\nThe null_sha1 is used for current working tree configuration, i.e.\nload .gitmodules and then overload with .git/config.\n\norigin/bw/grep-submodules changes the behavior as it preloads the\nnull_sha1 to be an actual commit-ish (HEAD^').\n\nI may make use of it in the checkout --recurse-submodules series.\n\n> The *only* calls to\n> these functions that doesn't involve a null sha1 or a null pointer is\n> from test code. So all in all, I'm not entirely sure what this sha1\n> argument is all about in the first place.\n\nSee Documentation/technical/api-submodule-config.txt (IIRC)\nin next(?).\n\n>\n> However, an argument could be made that null_sha1 should be treated\n> specially at a lower level (read_sha1_file, I guess).\n>\n> What would be sensible to do here?\n\nAs said above, the nul_sha1 is (ab-)used to mean\n\"use the preloaded config\" which as of now is .git/config on top\nof .gitmodules in the working tree.\n\nI would assume we want another earlier and cheaper switch\nfor all these functions. This may also come in handy for the\ngit-series, that uses gitlinks as non-submodules.\n\nSomething like\n\n    int treat_gitlinks_as_submodule()\n\nwhich can be configured to be \"auto\"[1]  and then\n\"on\", \"off\" that can be set for tools such as mercurial\nremote helper or git-series.\n\n[1] the default that\nrequires some slightly more expensive guess work, e.g.\nthe existence of the .gitmodules file. c.f.\nhttps://github.com/git/git/commit/1863e05af5be73d9f7b9a1d22a33ca9849726623\nstatic void preset_submodule_default(void)\nwould be a starting point to cheaply estimate\nif gitlinks are submodules.\n\n\n\n>\n> Mike\n"}]}