{"thread":{"id":"44979","subject":"[PATCH 0/2] (re-)optimizing fsck --connectivity-only","startedAt":"2017-01-26T04:10:33Z","lastAt":"2017-01-26T19:13:06Z","messageCount":6,"participants":["Jeff King","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"310288","messageId":"20170126041025.hqg3znwew7jxgxxg@sigill.intra.peff.net","threadId":"44979","inReplyTo":null,"subject":"[PATCH 0/2] (re-)optimizing fsck --connectivity-only","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-26T04:10:25Z","receivedAt":"2017-01-26T04:10:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I've been playing around with the newly-fixed `fsck --connectivity-only`.\nWhile it's much faster than it was, I was sad to find a case that is\nstill much slower than \"git rev-list --objects --all\".\n\nThis goes on top of my origin/jk/fsck-connectivity-check-fix, and gives\na noticeable speedup. IMHO it's worth considering as part of the same\ntopic (which is currently in 'next').\n\n  [1/2]: fsck: move typename() printing to its own function\n  [2/2]: fsck: lazily load types under --connectivity-only\n\n builtin/fsck.c | 87 ++++++++++++++++++----------------------------------------\n fsck.c         |  4 +++\n 2 files changed, 31 insertions(+), 60 deletions(-)\n\n-Peff\n"},{"id":"310289","messageId":"20170126041100.nndm45ha6yviiugk@sigill.intra.peff.net","threadId":"44979","inReplyTo":"20170126041025.hqg3znwew7jxgxxg@sigill.intra.peff.net","subject":"[PATCH 1/2] fsck: move typename() printing to its own function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-26T04:11:00Z","receivedAt":"2017-01-26T04:11:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When an object has a problem, we mention its type. But we do\nso by feeding the result of typename() directly to\nfprintf(). This is potentially dangerous because typename()\ncan return NULL for some type values (like OBJ_NONE).\n\nIt's doubtful that this can be triggered in practice with\nthe current code, so this is probably not fixing a bug. But\nit future-proofs us against modifications that make things\nlike OBJ_NONE more likely (and gives future patches a\ncentral point to handle them).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fsck.c | 29 ++++++++++++++++++++---------\n 1 file changed, 20 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 57f529b41..3d5ced2d3 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -56,6 +56,17 @@ static const char *describe_object(struct object *obj)\n \treturn buf.buf;\n }\n \n+static const char *printable_type(struct object *obj)\n+{\n+\tconst char *ret;\n+\n+\tret = typename(obj->type);\n+\tif (!ret)\n+\t\tret = \"unknown\";\n+\n+\treturn ret;\n+}\n+\n static int fsck_config(const char *var, const char *value, void *cb)\n {\n \tif (strcmp(var, \"fsck.skiplist\") == 0) {\n@@ -83,7 +94,7 @@ static void objreport(struct object *obj, const char *msg_type,\n \t\t\tconst char *err)\n {\n \tfprintf(stderr, \"%s in %s %s: %s\\n\",\n-\t\tmsg_type, typename(obj->type), describe_object(obj), err);\n+\t\tmsg_type, printable_type(obj), describe_object(obj), err);\n }\n \n static int objerror(struct object *obj, const char *err)\n@@ -114,7 +125,7 @@ static int mark_object(struct object *obj, int type, void *data, struct fsck_opt\n \tif (!obj) {\n \t\t/* ... these references to parent->fld are safe here */\n \t\tprintf(\"broken link from %7s %s\\n\",\n-\t\t\t   typename(parent->type), describe_object(parent));\n+\t\t\t   printable_type(parent), describe_object(parent));\n \t\tprintf(\"broken link from %7s %s\\n\",\n \t\t\t   (type == OBJ_ANY ? \"unknown\" : typename(type)), \"unknown\");\n \t\terrors_found |= ERROR_REACHABLE;\n@@ -131,9 +142,9 @@ static int mark_object(struct object *obj, int type, void *data, struct fsck_opt\n \tif (!(obj->flags & HAS_OBJ)) {\n \t\tif (parent && !has_object_file(&obj->oid)) {\n \t\t\tprintf(\"broken link from %7s %s\\n\",\n-\t\t\t\t typename(parent->type), describe_object(parent));\n+\t\t\t\t printable_type(parent), describe_object(parent));\n \t\t\tprintf(\"              to %7s %s\\n\",\n-\t\t\t\t typename(obj->type), describe_object(obj));\n+\t\t\t\t printable_type(obj), describe_object(obj));\n \t\t\terrors_found |= ERROR_REACHABLE;\n \t\t}\n \t\treturn 1;\n@@ -205,7 +216,7 @@ static void check_reachable_object(struct object *obj)\n \tif (!(obj->flags & HAS_OBJ)) {\n \t\tif (has_sha1_pack(obj->oid.hash))\n \t\t\treturn; /* it is in pack - forget about it */\n-\t\tprintf(\"missing %s %s\\n\", typename(obj->type),\n+\t\tprintf(\"missing %s %s\\n\", printable_type(obj),\n \t\t\tdescribe_object(obj));\n \t\terrors_found |= ERROR_REACHABLE;\n \t\treturn;\n@@ -231,7 +242,7 @@ static void check_unreachable_object(struct object *obj)\n \t * since this is something that is prunable.\n \t */\n \tif (show_unreachable) {\n-\t\tprintf(\"unreachable %s %s\\n\", typename(obj->type),\n+\t\tprintf(\"unreachable %s %s\\n\", printable_type(obj),\n \t\t\tdescribe_object(obj));\n \t\treturn;\n \t}\n@@ -250,7 +261,7 @@ static void check_unreachable_object(struct object *obj)\n \t */\n \tif (!obj->used) {\n \t\tif (show_dangling)\n-\t\t\tprintf(\"dangling %s %s\\n\", typename(obj->type),\n+\t\t\tprintf(\"dangling %s %s\\n\", printable_type(obj),\n \t\t\t       describe_object(obj));\n \t\tif (write_lost_and_found) {\n \t\t\tchar *filename = git_pathdup(\"lost-found/%s/%s\",\n@@ -324,7 +335,7 @@ static int fsck_obj(struct object *obj)\n \n \tif (verbose)\n \t\tfprintf(stderr, \"Checking %s %s\\n\",\n-\t\t\ttypename(obj->type), describe_object(obj));\n+\t\t\tprintable_type(obj), describe_object(obj));\n \n \tif (fsck_walk(obj, NULL, &fsck_obj_options))\n \t\tobjerror(obj, \"broken links\");\n@@ -350,7 +361,7 @@ static int fsck_obj(struct object *obj)\n \t\tstruct tag *tag = (struct tag *) obj;\n \n \t\tif (show_tags && tag->tagged) {\n-\t\t\tprintf(\"tagged %s %s\", typename(tag->tagged->type),\n+\t\t\tprintf(\"tagged %s %s\", printable_type(tag->tagged),\n \t\t\t\tdescribe_object(tag->tagged));\n \t\t\tprintf(\" (%s) in %s\\n\", tag->tag,\n \t\t\t\tdescribe_object(&tag->object));\n-- \n2.11.0.840.gd37c5973a\n\n"},{"id":"310290","messageId":"20170126041206.5qfv7r7czbwfqvaa@sigill.intra.peff.net","threadId":"44979","inReplyTo":"20170126041025.hqg3znwew7jxgxxg@sigill.intra.peff.net","subject":"[PATCH 2/2] fsck: lazily load types under --connectivity-only","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-26T04:12:07Z","receivedAt":"2017-01-26T04:12:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The recent fixes to \"fsck --connectivity-only\" load all of\nthe objects with their correct types. This keeps the\nconnectivity-only code path close to the regular one, but it\nalso introduces some unnecessary inefficiency. While getting\nthe type of an object is cheap compared to actually opening\nand parsing the object (as the non-connectivity-only case\nwould do), it's still not free.\n\nFor reachable non-blob objects, we end up having to parse\nthem later anyway (to see what they point to), making our\ntype lookup here redundant.\n\nFor unreachable objects, we might never hit them at all in\nthe reachability traversal, making the lookup completely\nwasted. And in some cases, we might have quite a few\nunreachable objects (e.g., when alternates are used for\nshared object storage between repositories, it's normal for\nthere to be objects reachable from other repositories but\nnot the one running fsck).\n\nThe comment in mark_object_for_connectivity() claims two\nbenefits to getting the type up front:\n\n  1. We need to know the types during fsck_walk(). (And not\n     explicitly mentioned, but we also need them when\n     printing the types of broken or dangling commits).\n\n     We can address this by lazy-loading the types as\n     necessary. Most objects never need this lazy-load at\n     all, because they fall into one of these categories:\n\n       a. Reachable from our tips, and are coerced into the\n\t  correct type as we traverse (e.g., a parent link\n\t  will call lookup_commit(), which converts OBJ_NONE\n\t  to OBJ_COMMIT).\n\n       b. Unreachable, but not at the tip of a chunk of\n          unreachable history. We only mention the tips as\n\t  \"dangling\", so an unreachable commit which links\n\t  to hundreds of other objects needs only report the\n\t  type of the tip commit.\n\n  2. It serves as a cross-check that the coercion in (1a) is\n     correct (i.e., we'll complain about a parent link that\n     points to a blob). But we get most of this for free\n     already, because right after coercing, we'll parse any\n     non-blob objects. So we'd notice then if we expected a\n     commit and got a blob.\n\n     The one exception is when we expect a blob, in which\n     case we never actually read the object contents.\n\n     So this is a slight weakening, but given that the whole\n     point of --connectivity-only is to sacrifice some data\n     integrity checks for speed, this seems like an\n     acceptable tradeoff.\n\nHere are before and after timings for an extreme case with\n~5M reachable objects and another ~12M unreachable (it's the\ntorvalds/linux repository on GitHub, connected to shared\nstorage for all of the other kernel forks):\n\n  [before]\n  $ time git fsck --no-dangling --connectivity-only\n  real\t3m4.323s\n  user\t1m25.121s\n  sys\t1m38.710s\n\n  [after]\n  $ time git fsck --no-dangling --connectivity-only\n  real\t0m51.497s\n  user\t0m49.575s\n  sys\t0m1.776s\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/fsck.c | 58 +++++++---------------------------------------------------\n fsck.c         |  4 ++++\n 2 files changed, 11 insertions(+), 51 deletions(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 3d5ced2d3..140357b6f 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -60,6 +60,12 @@ static const char *printable_type(struct object *obj)\n {\n \tconst char *ret;\n \n+\tif (obj->type == OBJ_NONE) {\n+\t\tenum object_type type = sha1_object_info(obj->oid.hash, NULL);\n+\t\tif (type > 0)\n+\t\t\tobject_as_type(obj, type, 0);\n+\t}\n+\n \tret = typename(obj->type);\n \tif (!ret)\n \t\tret = \"unknown\";\n@@ -595,57 +601,7 @@ static int fsck_cache_tree(struct cache_tree *it)\n \n static void mark_object_for_connectivity(const unsigned char *sha1)\n {\n-\tstruct object *obj = lookup_object(sha1);\n-\n-\t/*\n-\t * Setting the object type here isn't strictly necessary for a\n-\t * connectivity check. In most cases, our walk will expect a certain\n-\t * type (e.g., a tree referencing a blob) and will use lookup_blob() to\n-\t * assign the type. But doing it here has two advantages:\n-\t *\n-\t *   1. When the fsck_walk code looks at objects that _don't_ come from\n-\t *      links (e.g., the tip of a ref), it may complain about the\n-\t *      \"unknown object type\".\n-\t *\n-\t *   2. This serves as a nice cross-check that the graph links are\n-\t *      sane. So --connectivity-only does not check that the bits of\n-\t *      blobs are not corrupted, but it _does_ check that 100644 tree\n-\t *      entries point to blobs, and so forth.\n-\t *\n-\t * Unfortunately we can't just use parse_object() here, because the\n-\t * whole point of --connectivity-only is to avoid reading the object\n-\t * data more than necessary.\n-\t */\n-\tif (!obj || obj->type == OBJ_NONE) {\n-\t\tenum object_type type = sha1_object_info(sha1, NULL);\n-\t\tswitch (type) {\n-\t\tcase OBJ_BAD:\n-\t\t\terror(\"%s: unable to read object type\",\n-\t\t\t      sha1_to_hex(sha1));\n-\t\t\tbreak;\n-\t\tcase OBJ_COMMIT:\n-\t\t\tobj = (struct object *)lookup_commit(sha1);\n-\t\t\tbreak;\n-\t\tcase OBJ_TREE:\n-\t\t\tobj = (struct object *)lookup_tree(sha1);\n-\t\t\tbreak;\n-\t\tcase OBJ_BLOB:\n-\t\t\tobj = (struct object *)lookup_blob(sha1);\n-\t\t\tbreak;\n-\t\tcase OBJ_TAG:\n-\t\t\tobj = (struct object *)lookup_tag(sha1);\n-\t\t\tbreak;\n-\t\tdefault:\n-\t\t\terror(\"%s: unknown object type %d\",\n-\t\t\t      sha1_to_hex(sha1), type);\n-\t\t}\n-\n-\t\tif (!obj || obj->type == OBJ_NONE) {\n-\t\t\terrors_found |= ERROR_OBJECT;\n-\t\t\treturn;\n-\t\t}\n-\t}\n-\n+\tstruct object *obj = lookup_unknown_object(sha1);\n \tobj->flags |= HAS_OBJ;\n }\n \ndiff --git a/fsck.c b/fsck.c\nindex 4a3069e20..939792752 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -458,6 +458,10 @@ int fsck_walk(struct object *obj, void *data, struct fsck_options *options)\n {\n \tif (!obj)\n \t\treturn -1;\n+\n+\tif (obj->type == OBJ_NONE)\n+\t\tparse_object(obj->oid.hash);\n+\n \tswitch (obj->type) {\n \tcase OBJ_BLOB:\n \t\treturn 0;\n-- \n2.11.0.840.gd37c5973a\n"},{"id":"310307","messageId":"alpine.DEB.2.20.1701261307261.3469@virtualbox","threadId":"44979","inReplyTo":"20170126041206.5qfv7r7czbwfqvaa@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: lazily load types under --connectivity-only","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-01-26T12:07:51Z","receivedAt":"2017-01-26T12:08:24Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Wed, 25 Jan 2017, Jeff King wrote:\n\n>  builtin/fsck.c | 58 +++++++---------------------------------------------------\n>  fsck.c         |  4 ++++\n>  2 files changed, 11 insertions(+), 51 deletions(-)\n\nPatch looks good to my eyes.\n\nCiao,\nJohannes\n"},{"id":"310346","messageId":"xmqqziid4puz.fsf@gitster.mtv.corp.google.com","threadId":"44979","inReplyTo":"20170126041206.5qfv7r7czbwfqvaa@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] fsck: lazily load types under --connectivity-only","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-01-26T18:51:00Z","receivedAt":"2017-01-26T18:51:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The recent fixes to \"fsck --connectivity-only\" load all of\n> the objects with their correct types. This keeps the\n> connectivity-only code path close to the regular one, but it\n> also introduces some unnecessary inefficiency. While getting\n> the type of an object is cheap compared to actually opening\n> and parsing the object (as the non-connectivity-only case\n> would do), it's still not free.\n>\n> For reachable non-blob objects, we end up having to parse\n> them later anyway (to see what they point to), making our\n> type lookup here redundant.\n>\n> For unreachable objects, we might never hit them at all in\n> the reachability traversal, making the lookup completely\n> wasted. And in some cases, we might have quite a few\n> unreachable objects (e.g., when alternates are used for\n> shared object storage between repositories, it's normal for\n> there to be objects reachable from other repositories but\n> not the one running fsck).\n>\n> The comment in mark_object_for_connectivity() claims two\n> benefits to getting the type up front:\n>\n>   1. We need to know the types during fsck_walk(). (And not\n>      explicitly mentioned, but we also need them when\n>      printing the types of broken or dangling commits).\n>\n>      We can address this by lazy-loading the types as\n>      necessary. Most objects never need this lazy-load at\n>      all, because they fall into one of these categories:\n>\n>        a. Reachable from our tips, and are coerced into the\n> \t  correct type as we traverse (e.g., a parent link\n> \t  will call lookup_commit(), which converts OBJ_NONE\n> \t  to OBJ_COMMIT).\n>\n>        b. Unreachable, but not at the tip of a chunk of\n>           unreachable history. We only mention the tips as\n> \t  \"dangling\", so an unreachable commit which links\n> \t  to hundreds of other objects needs only report the\n> \t  type of the tip commit.\n>\n>   2. It serves as a cross-check that the coercion in (1a) is\n>      correct (i.e., we'll complain about a parent link that\n>      points to a blob). But we get most of this for free\n>      already, because right after coercing, we'll parse any\n>      non-blob objects. So we'd notice then if we expected a\n>      commit and got a blob.\n>\n>      The one exception is when we expect a blob, in which\n>      case we never actually read the object contents.\n>\n>      So this is a slight weakening, but given that the whole\n>      point of --connectivity-only is to sacrifice some data\n>      integrity checks for speed, this seems like an\n>      acceptable tradeoff.\n\nThe only weakening is that a non-blob (or a corrupt blob) object\nthat sits where we expect a blob (because the containing tree or the\ntag says so) would not be diagnosed as an error, then?  I think that\nis in line with the spirit of --connectivity-only and is a good\ntrade-off.\n"},{"id":"310350","messageId":"20170126191205.iu54sxbjisucsv6t@sigill.intra.peff.net","threadId":"44979","inReplyTo":"xmqqziid4puz.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 2/2] fsck: lazily load types under --connectivity-only","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-26T19:12:05Z","receivedAt":"2017-01-26T19:13:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 26, 2017 at 10:51:00AM -0800, Junio C Hamano wrote:\n\n> >   2. It serves as a cross-check that the coercion in (1a) is\n> >      correct (i.e., we'll complain about a parent link that\n> >      points to a blob). But we get most of this for free\n> >      already, because right after coercing, we'll parse any\n> >      non-blob objects. So we'd notice then if we expected a\n> >      commit and got a blob.\n> >\n> >      The one exception is when we expect a blob, in which\n> >      case we never actually read the object contents.\n> >\n> >      So this is a slight weakening, but given that the whole\n> >      point of --connectivity-only is to sacrifice some data\n> >      integrity checks for speed, this seems like an\n> >      acceptable tradeoff.\n> \n> The only weakening is that a non-blob (or a corrupt blob) object\n> that sits where we expect a blob (because the containing tree or the\n> tag says so) would not be diagnosed as an error, then?  I think that\n> is in line with the spirit of --connectivity-only and is a good\n> trade-off.\n\nCorrect. The corrupt-blob case we always knew was a tradeoff (that's the\nwhole point of --connectivity-only). We could add back in the \"we expect\na blob, is it really one?\" at the moment we traverse to it, but IMHO\nit's not interesting enough to even be worth the sha1_object_info()\nlookup time.\n\n-Peff\n"}]}