{"thread":{"id":"36272","subject":"with reuse-delta patches, fetching with bitmaps segfaults due to possibly incomplete bitmap traverse","startedAt":"2014-03-22T02:58:55Z","lastAt":"2014-03-24T20:30:58Z","messageCount":4,"participants":["Siddharth Agarwal","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"237384","messageId":"532CFC6F.8000008@fb.com","threadId":"36272","inReplyTo":null,"subject":"with reuse-delta patches, fetching with bitmaps segfaults due to possibly incomplete bitmap traverse","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-22T02:58:55Z","receivedAt":"2014-03-22T02:58:55Z","isPatch":false,"sender":{"key":"sid0@fb.com","avatar":null},"body":"Hi all,\n\nAt Facebook we've found that fetch speed is a bottleneck for our Git \nrepos, so we've been looking to deploy bitmaps to speed up fetches. \nWe've been trying out git-next with the top two patches from \nhttps://github.com/peff/git/commits/jk/bitmap-reuse-delta, but the \nfollowing is reproducible with tip of that branch, currently 81cdec2.\n\nWe're finding that git fetches with bitmaps enabled are malfunctioning \nunder some circumstances. For at least one of our repositories, a \nparticular git fetch that an engineer ran segfaulted on the rmeote git \npack-objects because of writing to an array out of bounds. This is \nconsistently reproducible with the particular pair of (remote, local) \nrepositories.\n\nThe error looks like:\n\n(1) $ git fetch\nremote: Counting objects: 201614, done.\nremote: Compressing objects: 100% (36262/36262), done.\nerror: pack-objects died of signal 11\nerror: git upload-pack: git-pack-objects died with error.\nfatal: git upload-pack: aborting due to possible repository corruption \non the remote side.\nremote: aborting due to possible repository corruption on the remote side.\nfatal: protocol error: bad pack header\n\nIn contrast, when I disable bitmaps by removing the .bitmap file on the \nserver while using the same Git binary, I get\n\n(2) $ git fetch\nremote: Counting objects: 203466, done.\nremote: Compressing objects: 100% (46014/46104), done.\nReceiving objects: 100% (203466/203466), 55.52 MiB | 7.45 MiB/s, done.\nremote: Total 203466 (delta 169894), reused 187613 (delta 156621)\n\nNote the differences in the \"Counting objects\" and \"Compressing objects\" \nfigures between (1) and (2). I'm not sure if they're relevant.\n\nAs a baseline, if I run the same test with an older git -- version \n1.8.1, I get\n\n(3) $ git fetch\nremote: Counting objects: 235298, done.\nremote: Compressing objects: 100% (46104/46104), done.\nremote: Total 203466 (delta 169894), reused 187613 (delta 156621)\nReceiving objects: 100% (203466/203466), 55.52 MiB | 11.15 MiB/s, done.\n\nAs a control, I'm using the same version of Git on the client in all \nthree cases above -- git 1.8.1. The client Git doesn't matter -- using \n81cdec2 has the same effect. The transport is ssh in all three cases.\n\nI dug into this a bit and it looks like at this point:\n\nhttps://github.com/peff/git/blob/81cdec28fa24fdc613ab7c3406c1c67975dbf22f/builtin/pack-objects.c#L700\n\nat some object that add_family_to_write_order is called for, wo_end \nexceeds to_pack.nr_objects by over 1000 objects. More precisely, at the \npoint it crashes, wo_end is 218081 while to_pack.nr_objects is 201614. \n(This means wo_end overshot to_pack.nr_objects some time ago.)\n\nI bumped up the malloc at \nhttps://github.com/peff/git/blob/81cdec28fa24fdc613ab7c3406c1c67975dbf22f/builtin/pack-objects.c#L628 \nin order to prevent segfaulting, and the remote process dies with:\n\n(4) $ git fetch\nremote: Counting objects: 201614, done.\nremote: Compressing objects: 100% (36262/36262), done.\nremote: fatal: ordered 226227 objects, expected 201614\n\nIn contrast, in case (2) above, at the end of compute_pack_order, wo_end \nand to_pack.nr_objects are both 235298. I found it interesting that this \nnumber is not reflected anywhere in the output of (2) but is the same as \nthe output of the \"Counting objects\" step of (3). I'm not sure if this \nis a red herring or not.\n\nI suspect that the traverse_bitmap_commit_list call at \nhttps://github.com/peff/git/blob/81cdec28fa24fdc613ab7c3406c1c67975dbf22f/builtin/pack-objects.c#L2476 \nis somehow skipping objects.\n\nOther notes:\n- I cannot reproduce this with a plain old 'git clone <remote>' with \nbitmaps enabled and used on the remote. There's something particular \nabout either thin packs or the client repository that's triggering this.\n- There is exactly one pack containing slightly over 3.5 million \nobjects, and three loose objects in the remote repo.\n- The remote repo is isolated -- there are no concurrent writes going on.\n- While generating the bitmap I did not reuse existing any existing \nbitmaps: I removed the existing bitmap and ran git repack -adb.\n\nUnfortunately I do not have a reproducible test case with a repository \nthat's open source, or with one that I can share. However, I'm happy to \nprovide any other information about the structure of the repository, and \nto set up a debugging session over IRC or other means.\n"},{"id":"237391","messageId":"20140322125626.GA22890@sigill.intra.peff.net","threadId":"36272","inReplyTo":"532CFC6F.8000008@fb.com","subject":"Re: with reuse-delta patches, fetching with bitmaps segfaults due to possibly incomplete bitmap traverse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-03-22T12:56:27Z","receivedAt":"2014-03-22T12:56:27Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 21, 2014 at 07:58:55PM -0700, Siddharth Agarwal wrote:\n\n> At Facebook we've found that fetch speed is a bottleneck for our Git repos,\n> so we've been looking to deploy bitmaps to speed up fetches. We've been\n> trying out git-next with the top two patches from\n> https://github.com/peff/git/commits/jk/bitmap-reuse-delta, but the following\n> is reproducible with tip of that branch, currently 81cdec2.\n\nIs it also reproducible just with the tip of \"next\"? Note that the\npatches in jk/bitmap-reuse-delta have not been widely deployed (in\nparticular, we are not yet using them at GitHub, and we track segfaults\non our servers closely and have not seen any related to this).\n\nThose patches allocate extra \"fake\" entries in the entry->delta fields,\nwhich are not accounted for in to_pack.nr_objects. It's entirely\npossible that those entries are related to the bug you are seeing.\n\n> I dug into this a bit and it looks like at this point:\n> \n> https://github.com/peff/git/blob/81cdec28fa24fdc613ab7c3406c1c67975dbf22f/builtin/pack-objects.c#L700\n> \n> at some object that add_family_to_write_order is called for, wo_end exceeds\n> to_pack.nr_objects by over 1000 objects. More precisely, at the point it\n> crashes, wo_end is 218081 while to_pack.nr_objects is 201614. (This means\n> wo_end overshot to_pack.nr_objects some time ago.)\n\nHmm, yeah, that confirms my suspicion. In the earlier loops, we call\nadd_to_write_order, which only adds the object in question, and can\nnever exceed to_pack.nr_objects. In this final loop, we call\nadd_family_to_write_order, which is going to add any deltas that were\nnot already included.\n\nThe patch below may fix your problem, but I have a feeling it is not the\nright thing to do. The point of 81cdec28 is to try to point to a delta\nentry as if it were a \"preferred base\" (i.e., something we know that the\nother side has already). We perhaps want to add these entries to the\nactual packing list, and skip them as we do with normal preferred_base\nobjects.\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 9fc5321..ca1b0f7 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1437,6 +1437,7 @@ static void check_object(struct object_entry *entry)\n \t\t\tentry->delta = xcalloc(1, sizeof(*entry->delta));\n \t\t\thashcpy(entry->delta->idx.sha1, base_ref);\n \t\t\tentry->delta->preferred_base = 1;\n+\t\t\tentry->delta->filled = 1;\n \t\t\tunuse_pack(&w_curs);\n \t\t\treturn;\n \t\t}\n\n-Peff\n"},{"id":"237430","messageId":"532F75BC.7080301@fb.com","threadId":"36272","inReplyTo":"20140322125626.GA22890@sigill.intra.peff.net","subject":"Re: with reuse-delta patches, fetching with bitmaps segfaults due to possibly incomplete bitmap traverse","fromName":"Siddharth Agarwal","fromEmail":"sid0@fb.com","sentAt":"2014-03-24T00:01:00Z","receivedAt":"2014-03-24T00:01:00Z","isPatch":false,"sender":{"key":"sid0@fb.com","avatar":null},"body":"On 03/22/2014 05:56 AM, Jeff King wrote:\n> On Fri, Mar 21, 2014 at 07:58:55PM -0700, Siddharth Agarwal wrote:\n>\n> Is it also reproducible just with the tip of \"next\"? Note that the\n> patches in jk/bitmap-reuse-delta have not been widely deployed (in\n> particular, we are not yet using them at GitHub, and we track segfaults\n> on our servers closely and have not seen any related to this).\n\nI cannot reproduce this with the tip of next (tested with 4443bfd). \nThat's also --  unsurprisingly -- significantly slower in the \ncompression phase and sends much more data (3x for the pair of repos in \nthe OP) over the wire than a Git that doesn't use bitmaps.\n\n> Those patches allocate extra \"fake\" entries in the entry->delta fields,\n> which are not accounted for in to_pack.nr_objects. It's entirely\n> possible that those entries are related to the bug you are seeing.\n\nThat sounds like it could be the problem, yes.\n\n> Hmm, yeah, that confirms my suspicion. In the earlier loops, we call\n> add_to_write_order, which only adds the object in question, and can\n> never exceed to_pack.nr_objects. In this final loop, we call\n> add_family_to_write_order, which is going to add any deltas that were\n> not already included.\n>\n> The patch below may fix your problem, but I have a feeling it is not the\n> right thing to do. The point of 81cdec28 is to try to point to a delta\n> entry as if it were a \"preferred base\" (i.e., something we know that the\n> other side has already). We perhaps want to add these entries to the\n> actual packing list, and skip them as we do with normal preferred_base\n> objects.\n\nThe patch does stop Git from segfaulting. I know too little to judge its \ncorrectness, though.\n\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 9fc5321..ca1b0f7 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -1437,6 +1437,7 @@ static void check_object(struct object_entry *entry)\n>   \t\t\tentry->delta = xcalloc(1, sizeof(*entry->delta));\n>   \t\t\thashcpy(entry->delta->idx.sha1, base_ref);\n>   \t\t\tentry->delta->preferred_base = 1;\n> +\t\t\tentry->delta->filled = 1;\n>   \t\t\tunuse_pack(&w_curs);\n>   \t\t\treturn;\n>   \t\t}\n>\n> -Peff\n"},{"id":"237488","messageId":"xmqqmwgfpce5.fsf@gitster.dls.corp.google.com","threadId":"36272","inReplyTo":"20140322125626.GA22890@sigill.intra.peff.net","subject":"Re: with reuse-delta patches, fetching with bitmaps segfaults due to possibly incomplete bitmap traverse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-03-24T20:30:58Z","receivedAt":"2014-03-24T20:30:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Mar 21, 2014 at 07:58:55PM -0700, Siddharth Agarwal wrote:\n>\n>> At Facebook we've found that fetch speed is a bottleneck for our Git repos,\n>> so we've been looking to deploy bitmaps to speed up fetches. We've been\n>> trying out git-next with the top two patches from\n>> https://github.com/peff/git/commits/jk/bitmap-reuse-delta, but the following\n>> is reproducible with tip of that branch, currently 81cdec2.\n>\n> Is it also reproducible just with the tip of \"next\"? Note that the\n> patches in jk/bitmap-reuse-delta have not been widely deployed (in\n> particular, we are not yet using them at GitHub, and we track segfaults\n> on our servers closely and have not seen any related to this).\n\nNice to hear.  I was worried for a short while if I merged what was\nnot cooked well, before I realized that Siddharth is on a codebase\nthat is more bleeding edge than I use myself ;-)\n"}]}