{"thread":{"id":"35150","subject":"pack corruption post-mortem","startedAt":"2013-10-16T08:34:01Z","lastAt":"2015-04-02T00:49:55Z","messageCount":16,"participants":["Jeff King","Duy Nguyen","Martin Fick","Junio C Hamano","Nicolas Pitre","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"229063","messageId":"20131016083400.GA31266@sigill.intra.peff.net","threadId":"35150","inReplyTo":null,"subject":"pack corruption post-mortem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-16T08:34:01Z","receivedAt":"2013-10-16T08:34:01Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I was recently presented with a repository with a corrupted packfile,\nand was asked if the data was recoverable. This post-mortem describes\nthe steps I took to investigate and fix the problem. I thought others\nmight find the process interesting, and it might help somebody in the\nsame situation.\n\nI started with an fsck, which found a problem with exactly one object\n(I've used $pack and $obj below to keep the output readable, and also\nbecause I'll refer to them later):\n\n    $ git fsck\n    error: $pack SHA1 checksum mismatch\n    error: index CRC mismatch for object $obj from $pack at offset 51653873\n    error: inflate: data stream error (incorrect data check)\n    error: cannot unpack $obj from $pack at offset 51653873\n\nThe pack checksum failing means a byte is munged somewhere, and it is\npresumably in the object mentioned (since both the index checksum and\nzlib were failing).\n\nReading the zlib source code, I found that \"incorrect data check\" means\nthat the adler-32 checksum at the end of the zlib data did not match the\ninflated data. So stepping the data through zlib would not help, as it\ndid not fail until the very end, when we realize the crc does not match.\nThe problematic bytes could be anywhere in the object data.\n\nThe first thing I did was pull the broken data out of the packfile. I\nneeded to know how big the object was, which I found out with:\n\n  $ git show-index <$idx | cut -d' ' -f1 | sort -n | grep -A1 51653873\n  51653873\n  51664736\n\nShow-index gives us the list of objects and their offsets. We throw away\neverything but the offsets, and then sort them so that our interesting\noffset (which we got from the fsck output above) is followed immediately\nby the offset of the next object. Now we know that the object data is\n10863 bytes long, and we can grab it with:\n\n  dd if=$pack of=object bs=1 skip=51653873 count=10863\n\nI inspected a hexdump of the data, looking for any obvious bogosity\n(e.g., a 4K run of zeroes would be a good sign of filesystem\ncorruption). But everything looked pretty reasonable.\n\nNote that the \"object\" file isn't fit for feeding straight to zlib; it\nhas the git packed object header, which is variable-length. We want to\nstrip that off so we can start playing with the zlib data directly. You\ncan either work your way through it manually (the format is described in\nDocumentation/technical/pack-format.txt), or you can walk through it in\na debugger. I did the latter, creating a valid pack like:\n\n  # pack magic and version\n  printf 'PACK\\0\\0\\0\\2' >tmp.pack\n  # pack has one object\n  printf '\\0\\0\\0\\1' >>tmp.pack\n  # now add our object data\n  cat object >>tmp.pack\n  # and then append the pack trailer\n  /path/to/git.git/test-sha1 -b <tmp.pack >trailer\n  cat trailer >>tmp.pack\n\nand then running \"git index-pack tmp.pack\" in the debugger (stop at\nunpack_raw_entry). Doing this, I found that there were 3 bytes of header\n(and the header itself had a sane type and size). So I stripped those\noff with:\n\n  dd if=object of=zlib bs=1 skip=3\n\nI ran the result through zlib's inflate using a custom C program. And\nwhile it did report the error, I did get the right number of output\nbytes (i.e., it matched git's size header that we decoded above). But\nfeeding the result back to \"git hash-object\" didn't produce the same\nsha1. So there were some wrong bytes, but I didn't know which. The file\nhappened to be C source code, so I hoped I could notice something\nobviously wrong with it, but I didn't. I even got it to compile!\n\nI also tried comparing it to other versions of the same path in the\nrepository, hoping that there would be some part of the diff that didn't\nmake sense. Unfortunately, this happened to be the only revision of this\nparticular file in the repository, so I had nothing to compare against.\n\nSo I took a different approach. Working under the guess that the\ncorruption was limited to a single byte, I wrote a program to munge each\nbyte individually, and try inflating the result. Since the object was\nonly 10K compressed, that worked out to about 2.5M attempts, which took\na few minutes.\n\nThe program I used is here:\n\n-- >8 --\n#include <stdio.h>\n#include <unistd.h>\n#include <string.h>\n#include <signal.h>\n#include <zlib.h>\n\nstatic int try_zlib(unsigned char *buf, int len)\n{\n  /* make this absurdly large so we don't have to loop */\n  static unsigned char out[1024*1024];\n  z_stream z;\n  int ret;\n\n  memset(&z, 0, sizeof(z));\n  inflateInit(&z);\n\n  z.next_in = buf;\n  z.avail_in = len;\n  z.next_out = out;\n  z.avail_out = sizeof(out);\n\n  ret = inflate(&z, 0);\n  inflateEnd(&z);\n  return ret >= 0;\n}\n\n/* eye candy */\nstatic int counter = 0;\nstatic void progress(int sig)\n{\n  fprintf(stderr, \"\\r%d\", counter);\n  alarm(1);\n}\n\nint main(void)\n{\n  /* oversized so we can read the whole buffer in */\n  unsigned char buf[1024*1024];\n  int len;\n  unsigned i, j;\n\n  signal(SIGALRM, progress);\n  alarm(1);\n\n  len = read(0, buf, sizeof(buf));\n  for (i = 0; i < len; i++) {\n    unsigned char c = buf[i];\n    for (j = 0; j <= 0xff; j++) {\n      buf[i] = j;\n\n      counter++;\n      if (try_zlib(buf, len))\n        printf(\"i=%d, j=%x\\n\", i, j);\n    }\n    buf[i] = c;\n  }\n\n  alarm(0);\n  fprintf(stderr, \"\\n\");\n  return 0;\n}\n-- >8 --\n\nI compiled and ran with:\n\n  gcc -Wall -Werror -O3 munge.c -o munge -lz\n  ./munge <zlib\n\nThere were a few false positives early on (if you write \"no data\" in the\nzlib header, zlib thinks it's just fine :) ). But I got a hit about\nhalfway through:\n\n  i=5642, j=c7\n\nI let it run to completion, and got a few more hits at the end (where it\nwas munging the crc to match our broken data). So there was a good\nchance this middle hit was the source of the problem.\n\nI confirmed by tweaking the byte in a hex editor, zlib inflating the\nresult (no errors!), and then piping the output into \"git hash-object\",\nwhich reported the sha1 of the broken object. Success!\n\nI fixed the packfile itself with:\n\n  chmod +w $pack\n  printf '\\xc7' | dd of=$pack bs=1 seek=51659518 conv=notrunc\n  chmod -w $pack\n\nThe '\\xc7' comes from the replacement byte our \"munge\" program found.\nThe offset 51659518 is derived by taking the original object offset\n(51653873), adding the replacement offset found by \"munge\" (5642), and\nthen adding back in the 3 bytes of git header we stripped.\n\nAfter that, \"git fsck\" ran clean.\n\nAs for the corruption itself, I was lucky that it was indeed a single\nbyte. In fact, it turned out to be a single bit. The byte 0xc7 was\ncorrupted to 0xc5. So presumably it was caused by faulty hardware, or a\ncosmic ray.\n\nAnd the aborted attempt to look at the inflated output to see what was\nwrong? I could have looked forever and never found it. Here's the diff\nbetween what the corrupted data inflates to, versus the real data:\n\n  -       cp = strtok (arg, \"+\");\n  +       cp = strtok (arg, \".\");\n\nIt tweaked one byte and still ended up as valid, readable C that just\nhappened to do something totally different! One takeaway is that on a\nless unlucky day, looking at the zlib output might have actually been\nhelpful, as most random changes would actually break the C code.\n\nBut more importantly, git's hashing and checksumming noticed a problem\nthat easily could have gone undetected in another system. The result\nstill compiled, but would have caused an interesting bug (that would\nhave been blamed on some random commit).\n\n-Peff\n"},{"id":"229065","messageId":"CACsJy8CN6sOofVesHogk6Y9m0zHV31vyQr5HJZb9PTd-=DAyOw@mail.gmail.com","threadId":"35150","inReplyTo":"20131016083400.GA31266@sigill.intra.peff.net","subject":"Re: pack corruption post-mortem","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-16T08:59:26Z","receivedAt":"2013-10-16T08:59:26Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Oct 16, 2013 at 3:34 PM, Jeff King <peff@peff.net> wrote:\n> I was recently presented with a repository with a corrupted packfile,\n> and was asked if the data was recoverable. This post-mortem describes\n> the steps I took to investigate and fix the problem. I thought others\n> might find the process interesting, and it might help somebody in the\n> same situation.\n\nIt's like reading an LWN article. Thank you.\n-- \nDuy\n"},{"id":"229073","messageId":"201310160941.16904.mfick@codeaurora.org","threadId":"35150","inReplyTo":"20131016083400.GA31266@sigill.intra.peff.net","subject":"Re: pack corruption post-mortem","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-10-16T15:41:16Z","receivedAt":"2013-10-16T15:41:16Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Wednesday, October 16, 2013 02:34:01 am Jeff King wrote:\n> I was recently presented with a repository with a\n> corrupted packfile, and was asked if the data was\n> recoverable. This post-mortem describes the steps I took\n> to investigate and fix the problem. I thought others\n> might find the process interesting, and it might help\n> somebody in the same situation.\n\nThis is awesome Peff, thanks for the great writeup!\n\nI have nightmares about this sort of thing every now and \nthen, and we even experience some corruption here and there \nthat needs to be fixed (mainly missing objects when we toy \nwith different git repack arguments).  I cannot help but \nwonder, how we can improve git further to either help \ndiagnose or even fix some of these problems?  More inline \nbelow...\n\n\n> The first thing I did was pull the broken data out of the\n> packfile. I needed to know how big the object was, which\n> I found out with:\n> \n>   $ git show-index <$idx | cut -d' ' -f1 | sort -n | grep\n> -A1 51653873 51653873\n>   51664736\n> \n> Show-index gives us the list of objects and their\n> offsets. We throw away everything but the offsets, and\n> then sort them so that our interesting offset (which we\n> got from the fsck output above) is followed immediately\n> by the offset of the next object. Now we know that the\n> object data is 10863 bytes long, and we can grab it\n> with:\n> \n>   dd if=$pack of=object bs=1 skip=51653873 count=10863\n\nIs there a current plumbing command that should be enhanced \nto be able to do the 2 steps above directly for people \ndebugging (maybe with some new switch)?  If not, should we \ncreate one, git show --zlib, or git cat-file --zlib?\n\n\n> Note that the \"object\" file isn't fit for feeding\n> straight to zlib; it has the git packed object header,\n> which is variable-length. We want to strip that off so\n> we can start playing with the zlib data directly. You\n> can either work your way through it manually (the format\n> is described in\n> Documentation/technical/pack-format.txt), or you can\n> walk through it in a debugger. I did the latter,\n> creating a valid pack like:\n> \n>   # pack magic and version\n>   printf 'PACK\\0\\0\\0\\2' >tmp.pack\n>   # pack has one object\n>   printf '\\0\\0\\0\\1' >>tmp.pack\n>   # now add our object data\n>   cat object >>tmp.pack\n>   # and then append the pack trailer\n>   /path/to/git.git/test-sha1 -b <tmp.pack >trailer\n>   cat trailer >>tmp.pack\n> \n> and then running \"git index-pack tmp.pack\" in the\n> debugger (stop at unpack_raw_entry). Doing this, I found\n> that there were 3 bytes of header (and the header itself\n> had a sane type and size). So I stripped those off with:\n> \n>   dd if=object of=zlib bs=1 skip=3\n\nThis too feels like something we should be able to do with a \nplumbing command eventually?\n\ngit zlib-extract\n\n> So I took a different approach. Working under the guess\n> that the corruption was limited to a single byte, I\n> wrote a program to munge each byte individually, and try\n> inflating the result. Since the object was only 10K\n> compressed, that worked out to about 2.5M attempts,\n> which took a few minutes.\n\nAwesome!  Would this make a good new plumbing command, git \nzlib-fix?\n\n\n> I fixed the packfile itself with:\n> \n>   chmod +w $pack\n>   printf '\\xc7' | dd of=$pack bs=1 seek=51659518\n> conv=notrunc chmod -w $pack\n> \n> The '\\xc7' comes from the replacement byte our \"munge\"\n> program found. The offset 51659518 is derived by taking\n> the original object offset (51653873), adding the\n> replacement offset found by \"munge\" (5642), and then\n> adding back in the 3 bytes of git header we stripped.\n\nAnother plumbing command needed?  git pack-put --zlib?\n\nI am not saying my command suggestions are good, but maybe \nthey will inspire the right answer?\n\n-Martin\n"},{"id":"229109","messageId":"20131017003546.GA12439@sigill.intra.peff.net","threadId":"35150","inReplyTo":"201310160941.16904.mfick@codeaurora.org","subject":"Re: pack corruption post-mortem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-17T00:35:47Z","receivedAt":"2013-10-17T00:35:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 16, 2013 at 09:41:16AM -0600, Martin Fick wrote:\n\n> I have nightmares about this sort of thing every now and \n> then, and we even experience some corruption here and there \n> that needs to be fixed (mainly missing objects when we toy \n> with different git repack arguments).  I cannot help but \n> wonder, how we can improve git further to either help \n> diagnose or even fix some of these problems?  More inline \n> below...\n\nIn general, I don't think we know enough about patterns of recovery\ncorruption to say which commands would definitely be worth implementing.\nPart of the reason I wrote this up is to document this one case. But\nthis is the first time in 7 years of git usage that I've had to do this.\nSo I'd feel a little bit better about sinking time into it after seeing\na few more cases and realizing where the patterns are.\n\nOne of the major hassles is that the assumptions you can and can't make\ndepend on what data you have that _isn't_ corrupted. Do you have a pack\nindex, or a bare pack? Do you have zlib data that fails the crc, or zlib\ndata that cannot be parsed?\n\nIn this case there was no other copy of the repository. But if you know\nthe broken object (which we did here), and you can copy it from\nelsewhere, then git already will try to find other sources of the\nobject (loose, or in another pack).\n\n> >   dd if=$pack of=object bs=1 skip=51653873 count=10863\n> \n> Is there a current plumbing command that should be enhanced \n> to be able to do the 2 steps above directly for people \n> debugging (maybe with some new switch)?  If not, should we \n> create one, git show --zlib, or git cat-file --zlib?\n\nMost of the git plumbing commands deal with data at the object layer.\nThis is really about going a step below and saying \"Give me the on-disk\nrepresentation of the object\". We recently introduced an\n\"%(objectsize:disk)\" formatter for cat-file. The logical extension would\nbe to ask for \"%(contents:disk)\" or something. Though what you get would\ndepend on how the object is stored, so you would need to figure that out\nto do anything useful with it.\n\nNote that this implies you actually have a packfile index that says\n\"object XXX is at offset YYY\". In some corruption cases, you might have\nonly a packfile. That is generally enough to generate the index, but if\nthere is corruption, you cannot actually parse the pack to find out the\nsha1 of the objects.\n\nSo in the worst case, what you really want is something like \"dump the\nobject in packfile X at offset Y\". But even then, you don't know the\nlength of the object. The packfile is a stream, and the length we\ncalculated is from the index, which depends on the zlib data parsing in\nsome sane way.\n\n> > and then running \"git index-pack tmp.pack\" in the\n> > debugger (stop at unpack_raw_entry). Doing this, I found\n> > that there were 3 bytes of header (and the header itself\n> > had a sane type and size). So I stripped those off with:\n> > \n> >   dd if=object of=zlib bs=1 skip=3\n> \n> This too feels like something we should be able to do with a \n> plumbing command eventually?\n> \n> git zlib-extract\n\nPerhaps. I think if you had some \"extract object at offset X from the\npackfile\" command, it would be optional to give you the whole thing, or\njust the zlib data.\n\n> > So I took a different approach. Working under the guess\n> > that the corruption was limited to a single byte, I\n> > wrote a program to munge each byte individually, and try\n> > inflating the result. Since the object was only 10K\n> > compressed, that worked out to about 2.5M attempts,\n> > which took a few minutes.\n> \n> Awesome!  Would this make a good new plumbing command, git \n> zlib-fix?\n\nI'd like to see it actually work more than once first. This relies on\nthere being single-byte corruption. Even double-byte corruption starts\nto get expensive to brute-force like this. SHA1, by its nature, requires\nbrute-forcing. But it's possible that the crc, not being\ncryptographically secure, could be reverse-engineered to find likely\nspots of corruption. I don't know enough about it to say.\n\n> > I fixed the packfile itself with:\n> > \n> >   chmod +w $pack\n> >   printf '\\xc7' | dd of=$pack bs=1 seek=51659518\n> > conv=notrunc chmod -w $pack\n> > \n> > The '\\xc7' comes from the replacement byte our \"munge\"\n> > program found. The offset 51659518 is derived by taking\n> > the original object offset (51653873), adding the\n> > replacement offset found by \"munge\" (5642), and then\n> > adding back in the 3 bytes of git header we stripped.\n> \n> Another plumbing command needed?  git pack-put --zlib?\n\nI think in this case that dd does a nice job of solving the problem.\nSome of the stuff I did was very git-specific and required knowledge of\nthe formats. But this one is really just \"replace byte X at offset Y\",\nand I don't see any need to avoid a general-purpose tool (except that\ndd is itself reasonably arcane :) ).\n\n-Peff\n"},{"id":"229111","messageId":"CACsJy8ArdCrqn58wnx9c6wx148CfnQrWPfuxH5D7s1bvwr=cjQ@mail.gmail.com","threadId":"35150","inReplyTo":"201310160941.16904.mfick@codeaurora.org","subject":"Re: pack corruption post-mortem","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-17T01:06:50Z","receivedAt":"2013-10-17T01:06:50Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Oct 16, 2013 at 10:41 PM, Martin Fick <mfick@codeaurora.org> wrote:\n>> and then running \"git index-pack tmp.pack\" in the\n>> debugger (stop at unpack_raw_entry). Doing this, I found\n>> that there were 3 bytes of header (and the header itself\n>> had a sane type and size). So I stripped those off with:\n>>\n>>   dd if=object of=zlib bs=1 skip=3\n>\n> This too feels like something we should be able to do with a\n> plumbing command eventually?\n>\n> git zlib-extract\n\nNot an official plumbing, but I faced similar problems with pack v4. I\nneeded to verify that the output is correct and low level decoding\nlike this is generally a good thing to start with. So I wrote\ntest-dump [1] that can take an offset, a format and try to decode it.\nIt does not support zlib inflation yet, but adding one should be easy.\nAnd because this is just a test program we don't really need to think\nhard before adding something.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/235388\n-- \nDuy\n"},{"id":"229121","messageId":"xmqqfvrz3nnq.fsf@gitster.dls.corp.google.com","threadId":"35150","inReplyTo":"20131017003546.GA12439@sigill.intra.peff.net","subject":"Re: pack corruption post-mortem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-10-17T15:47:05Z","receivedAt":"2013-10-17T15:47:05Z","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 Wed, Oct 16, 2013 at 09:41:16AM -0600, Martin Fick wrote:\n>\n>> I have nightmares about this sort of thing every now and \n>> then, and we even experience some corruption here and there \n>> that needs to be fixed (mainly missing objects when we toy \n>> with different git repack arguments).  I cannot help but \n>> wonder, how we can improve git further to either help \n>> diagnose or even fix some of these problems?  More inline \n>> below...\n>\n> In general, I don't think we know enough about patterns of recovery\n> corruption to say which commands would definitely be worth implementing.\n> Part of the reason I wrote this up is to document this one case. But\n> this is the first time in 7 years of git usage that I've had to do this.\n> So I'd feel a little bit better about sinking time into it after seeing\n> a few more cases and realizing where the patterns are.\n\nThere was one area in our Documentation/ set we used to use to keep\nthis kind of message almost as-is; perhaps this message fits there?\n"},{"id":"229211","messageId":"CACsJy8ABdE8mZMVFZkqYMC4ZeN_baWw=XcYOZYBCZytWP97rRw@mail.gmail.com","threadId":"35150","inReplyTo":"20131016083400.GA31266@sigill.intra.peff.net","subject":"Re: pack corruption post-mortem","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-19T10:32:43Z","receivedAt":"2013-10-19T10:32:43Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Oct 16, 2013 at 3:34 PM, Jeff King <peff@peff.net> wrote:\n> I was recently presented with a repository with a corrupted packfile,\n> and was asked if the data was recoverable. This post-mortem describes\n> the steps I took to investigate and fix the problem. I thought others\n> might find the process interesting, and it might help somebody in the\n> same situation.\n>\n> I started with an fsck, which found a problem with exactly one object\n> (I've used $pack and $obj below to keep the output readable, and also\n> because I'll refer to them later):\n>\n>     $ git fsck\n>     error: $pack SHA1 checksum mismatch\n>     error: index CRC mismatch for object $obj from $pack at offset 51653873\n>     error: inflate: data stream error (incorrect data check)\n>     error: cannot unpack $obj from $pack at offset 51653873\n\nI wonder if we should protect the sha-1 and pathname tables in packv4\nwith CRC too. A bit flipped in there could cause stream of corrupt\nobjects and make it hard to pinpoint the corrupt location..\n-- \nDuy\n"},{"id":"229219","messageId":"alpine.LFD.2.03.1310191024000.1951@syhkavp.arg","threadId":"35150","inReplyTo":"CACsJy8ABdE8mZMVFZkqYMC4ZeN_baWw=XcYOZYBCZytWP97rRw@mail.gmail.com","subject":"Re: pack corruption post-mortem","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-19T14:41:08Z","receivedAt":"2013-10-19T14:41:08Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 19 Oct 2013, Duy Nguyen wrote:\n\n> On Wed, Oct 16, 2013 at 3:34 PM, Jeff King <peff@peff.net> wrote:\n> > I was recently presented with a repository with a corrupted packfile,\n> > and was asked if the data was recoverable. This post-mortem describes\n> > the steps I took to investigate and fix the problem. I thought others\n> > might find the process interesting, and it might help somebody in the\n> > same situation.\n> >\n> > I started with an fsck, which found a problem with exactly one object\n> > (I've used $pack and $obj below to keep the output readable, and also\n> > because I'll refer to them later):\n> >\n> >     $ git fsck\n> >     error: $pack SHA1 checksum mismatch\n> >     error: index CRC mismatch for object $obj from $pack at offset 51653873\n> >     error: inflate: data stream error (incorrect data check)\n> >     error: cannot unpack $obj from $pack at offset 51653873\n> \n> I wonder if we should protect the sha-1 and pathname tables in packv4\n> with CRC too. A bit flipped in there could cause stream of corrupt\n> objects and make it hard to pinpoint the corrupt location..\n\nIt turns out that we already have this covered.\n\nThe SHA1 used in the name of the pack file is actually the SHA1 checksum \nof the SHA1 table.\n\nThe path and ident tables are already protected by the CRC32 in the zlib \ndeflated stream.\n\nNormal objects are also zlib deflated (except for their header) but you \nneed to inflate them in order to have this CRC verified, which the pack \ndata copy tries to avoid.  Hence the separate CRC32 in the index file in \nthat case.\n\nHowever the pack v4 tables are very unlikely to be reused as is from one \npack to another.\n\n\nNicolas\n"},{"id":"229222","messageId":"CAJo=hJugNGkpDxh6o6azVGc7pP3fTGsK113vRgb4A7ipNeV2ZA@mail.gmail.com","threadId":"35150","inReplyTo":"alpine.LFD.2.03.1310191024000.1951@syhkavp.arg","subject":"Re: pack corruption post-mortem","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-10-19T19:17:52Z","receivedAt":"2013-10-19T19:17:52Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Oct 19, 2013 at 7:41 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> On Sat, 19 Oct 2013, Duy Nguyen wrote:\n>\n>> On Wed, Oct 16, 2013 at 3:34 PM, Jeff King <peff@peff.net> wrote:\n>> > I was recently presented with a repository with a corrupted packfile,\n>> > and was asked if the data was recoverable. This post-mortem describes\n>> > the steps I took to investigate and fix the problem. I thought others\n>> > might find the process interesting, and it might help somebody in the\n>> > same situation.\n>> >\n>> > I started with an fsck, which found a problem with exactly one object\n>> > (I've used $pack and $obj below to keep the output readable, and also\n>> > because I'll refer to them later):\n>> >\n>> >     $ git fsck\n>> >     error: $pack SHA1 checksum mismatch\n>> >     error: index CRC mismatch for object $obj from $pack at offset 51653873\n>> >     error: inflate: data stream error (incorrect data check)\n>> >     error: cannot unpack $obj from $pack at offset 51653873\n>>\n>> I wonder if we should protect the sha-1 and pathname tables in packv4\n>> with CRC too. A bit flipped in there could cause stream of corrupt\n>> objects and make it hard to pinpoint the corrupt location..\n>\n> It turns out that we already have this covered.\n>\n> The SHA1 used in the name of the pack file is actually the SHA1 checksum\n> of the SHA1 table.\n\nI continue to believe this naming is wrong. The pack file name should\nbe the SHA1 checksum of the pack data stream, but the SHA1 table. This\nwould allow cleaner update of a repository that was repacked with\ndifferent compression settings, but identical objects.\n"},{"id":"229230","messageId":"CACsJy8AATr9KfFN6x0E8mYsBmWhVmD=kaXgBmnFTiyww3MS8WQ@mail.gmail.com","threadId":"35150","inReplyTo":"alpine.LFD.2.03.1310191024000.1951@syhkavp.arg","subject":"Re: pack corruption post-mortem","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-20T04:44:32Z","receivedAt":"2013-10-20T04:44:32Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Oct 19, 2013 at 9:41 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> On Sat, 19 Oct 2013, Duy Nguyen wrote:\n> The SHA1 used in the name of the pack file is actually the SHA1 checksum\n> of the SHA1 table.\n>\n> The path and ident tables are already protected by the CRC32 in the zlib\n> deflated stream.\n>\n> Normal objects are also zlib deflated (except for their header) but you\n> need to inflate them in order to have this CRC verified, which the pack\n> data copy tries to avoid.  Hence the separate CRC32 in the index file in\n> that case.\n\nOK slight change in the subject, what about reading code (i.e.\nsha1_file.c)? With v2 crc32 is verified by object inflate code. With\nv4 trees or commits, because we store some (or all) data outside of\nthe deflated stream, we will not benefit from crc32 verifcation\npreviously done for all trees and commits. Should we perform explict\ncrc32 check when reading v4 trees and commits (and maybe verify the\nsha-1 table too)?\n-- \nDuy\n"},{"id":"229239","messageId":"alpine.LFD.2.03.1310201644330.1951@syhkavp.arg","threadId":"35150","inReplyTo":"CAJo=hJugNGkpDxh6o6azVGc7pP3fTGsK113vRgb4A7ipNeV2ZA@mail.gmail.com","subject":"Re: pack corruption post-mortem","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-20T20:56:44Z","receivedAt":"2013-10-20T20:56:44Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 19 Oct 2013, Shawn Pearce wrote:\n\n> On Sat, Oct 19, 2013 at 7:41 AM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> > On Sat, 19 Oct 2013, Duy Nguyen wrote:\n> >\n> >> On Wed, Oct 16, 2013 at 3:34 PM, Jeff King <peff@peff.net> wrote:\n> >> > I was recently presented with a repository with a corrupted packfile,\n> >> > and was asked if the data was recoverable. This post-mortem describes\n> >> > the steps I took to investigate and fix the problem. I thought others\n> >> > might find the process interesting, and it might help somebody in the\n> >> > same situation.\n> >> >\n> >> > I started with an fsck, which found a problem with exactly one object\n> >> > (I've used $pack and $obj below to keep the output readable, and also\n> >> > because I'll refer to them later):\n> >> >\n> >> >     $ git fsck\n> >> >     error: $pack SHA1 checksum mismatch\n> >> >     error: index CRC mismatch for object $obj from $pack at offset 51653873\n> >> >     error: inflate: data stream error (incorrect data check)\n> >> >     error: cannot unpack $obj from $pack at offset 51653873\n> >>\n> >> I wonder if we should protect the sha-1 and pathname tables in packv4\n> >> with CRC too. A bit flipped in there could cause stream of corrupt\n> >> objects and make it hard to pinpoint the corrupt location..\n> >\n> > It turns out that we already have this covered.\n> >\n> > The SHA1 used in the name of the pack file is actually the SHA1 checksum\n> > of the SHA1 table.\n> \n> I continue to believe this naming is wrong. The pack file name should\n> be the SHA1 checksum of the pack data stream, but the SHA1 table. This\n> would allow cleaner update of a repository that was repacked with\n> different compression settings, but identical objects.\n\nOK, after some thoughts, I decided that it is best _not_ to rely on the \npack name.  The pack name currently carries no meaning what so ever and \ngit works just fine if some packs are arbitrarily named.  Your concern \nabout its current naming scheme is certainly legitimate, and I don't \nwant pack v4 to introduce any kind of restrictions here.\n\nFurthermore, the SHA1 table is the only pack element which integrity may \nnot independently be verified at the moment.  This makes corruption \nisolation much harder when receiving a streamed pack.\n\nTherefore I decided to introduce a small pack v4 format change with the \nfollowing patch:\n\n----- >8\nFrom: Nicolas Pitre <nico@fluxnic.net>\nDate: Sun, 20 Oct 2013 14:52:24 -0400\nSubject: [PATCH] pack v4: add a SHA1 checksum to the SHA1 table\n\nEvery packed element currently has some integrity protection coming from\nthe CRC32 embedded in the zlib deflated stream, except for the SHA1 table.\n\nSome bit flip corruption in the SHA1 table may have repercutions on a\nwhole lot of objects and could be very hard to isolate.\n\nLet's add some integrity protection on the SHA1 table by terminating it\nwith an additional SHA1 entry being the SHA1 checksum of the table.\n\nSigned-off-by: Nicolas Pitre <nico@fluxnic.net>\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex fd2e737..a370f26 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -94,7 +94,9 @@ Git pack format\n === Pack v4 tables\n \n  - A table of sorted SHA-1 object names for all objects contained in\n-   the on-disk pack.\n+   the on-disk pack, with a final entry being the SHA1 sum of all the\n+   previous entries.  The size of this table is therefore\n+   (nr_objects + 1) * 20 bytes.\n \n    The SHA-1 table in thin packs must include the omitted objects as well.\n \ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex caec388..01300d6 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1471,7 +1471,10 @@ static struct packv4_dict *read_dict(void)\n \n static void parse_dictionaries(void)\n {\n+\tgit_SHA_CTX ctx;\n+\tunsigned char table_sha1[20];\n \tint i;\n+\n \tif (!packv4)\n \t\treturn;\n \n@@ -1485,6 +1488,12 @@ static void parse_dictionaries(void)\n \t\t\tdie(_(\"wrong order in SHA-1 table at entry %d\"), i);\n \t}\n \n+\tgit_SHA1_Init(&ctx);\n+\tgit_SHA1_Update(&ctx, sha1_table, 20 * nr_objects_final);\n+\tgit_SHA1_Final(table_sha1, &ctx);\n+\tif (hashcmp(table_sha1, fill_and_use(20)) != 0)\n+\t\tdie(_(\"SHA-1 table checksum mismatch\"));\n+\n \tname_dict = read_dict();\n \tpath_dict = read_dict();\n }\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex 9fd5640..eb57ada 100644\n--- a/builtin/unpack-objects.c\n+++ b/builtin/unpack-objects.c\n@@ -816,11 +816,18 @@ static void unpack_all(void)\n \tuse(sizeof(struct pack_header));\n \n \tif (packv4) {\n+\t\tgit_SHA_CTX ctx;\n+\t\tunsigned char table_sha1[20];\n \t\tsha1_table = xmalloc(20 * nr_objects);\n \t\tfor (i = 0; i < nr_objects; i++) {\n \t\t\tunsigned char *p = sha1_table + i * 20;\n \t\t\thashcpy(p, fill_and_use(20));\n \t\t}\n+\t\tgit_SHA1_Init(&ctx);\n+\t\tgit_SHA1_Update(&ctx, sha1_table, 20 * nr_objects);\n+\t\tgit_SHA1_Final(table_sha1, &ctx);\n+\t\tif (hashcmp(table_sha1, fill_and_use(20)) != 0)\n+\t\t\tdie(\"SHA-1 table checksum mismatch\");\n \t\tname_dict = read_dict();\n \t\tpath_dict = read_dict();\n \t}\ndiff --git a/packv4-create.c b/packv4-create.c\nindex 14be867..7b51792 100644\n--- a/packv4-create.c\n+++ b/packv4-create.c\n@@ -688,13 +688,20 @@ unsigned long packv4_write_tables(struct sha1file *f,\n \tstruct pack_idx_entry *objs = v4->all_objs;\n \tstruct dict_table *commit_ident_table = v4->commit_ident_table;\n \tstruct dict_table *tree_path_table = v4->tree_path_table;\n+\tgit_SHA_CTX ctx;\n+\tunsigned char table_sha1[20];\n \tunsigned i;\n \tunsigned long written = 0;\n \n \t/* The sorted list of object SHA1's is always first */\n-\tfor (i = 0; i < nr_objects; i++)\n+\tgit_SHA1_Init(&ctx);\n+\tfor (i = 0; i < nr_objects; i++) {\n+\t\tgit_SHA1_Update(&ctx, objs[i].sha1, 20);\n \t\tsha1write(f, objs[i].sha1, 20);\n-\twritten = 20 * nr_objects;\n+\t}\n+\tgit_SHA1_Final(table_sha1, &ctx);\n+\tsha1write(f, table_sha1, 20);\n+\twritten = 20 * (nr_objects + 1);\n \n \t/* Then the commit dictionary table */\n \twritten += write_dict_table(f, commit_ident_table,\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 31c89c7..e6f5028 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -128,7 +128,7 @@ static struct packv4_dict *load_dict(struct packed_git *p, off_t *offset)\n \n static void load_ident_dict(struct packed_git *p)\n {\n-\toff_t offset = 12 + p->num_objects * 20;\n+\toff_t offset = 12 + (p->num_objects + 1) * 20;\n \tstruct packv4_dict *names = load_dict(p, &offset);\n \tif (!names)\n \t\tdie(\"bad pack name dictionary in %s\", p->pack_name);\n\n\nNicolas\n"},{"id":"229240","messageId":"alpine.LFD.2.03.1310201657210.1951@syhkavp.arg","threadId":"35150","inReplyTo":"CACsJy8AATr9KfFN6x0E8mYsBmWhVmD=kaXgBmnFTiyww3MS8WQ@mail.gmail.com","subject":"Re: pack corruption post-mortem","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-20T21:08:30Z","receivedAt":"2013-10-20T21:08:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 20 Oct 2013, Duy Nguyen wrote:\n\n> On Sat, Oct 19, 2013 at 9:41 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> > On Sat, 19 Oct 2013, Duy Nguyen wrote:\n> > The SHA1 used in the name of the pack file is actually the SHA1 checksum\n> > of the SHA1 table.\n> >\n> > The path and ident tables are already protected by the CRC32 in the zlib\n> > deflated stream.\n> >\n> > Normal objects are also zlib deflated (except for their header) but you\n> > need to inflate them in order to have this CRC verified, which the pack\n> > data copy tries to avoid.  Hence the separate CRC32 in the index file in\n> > that case.\n> \n> OK slight change in the subject, what about reading code (i.e.\n> sha1_file.c)? With v2 crc32 is verified by object inflate code. With\n> v4 trees or commits, because we store some (or all) data outside of\n> the deflated stream, we will not benefit from crc32 verifcation\n> previously done for all trees and commits. Should we perform explict\n> crc32 check when reading v4 trees and commits (and maybe verify the\n> sha-1 table too)?\n\nI suppose that we should... at some point.\n\nI did the SHA1 table check only for index-pack and unpack-objects in my \nlatest patch.  Adding it to check_packed_git_idx() as well should be \ntrivial.\n\nI'm not sure about the best way to do systematic checks on tree objects \nthough.  We have both the CRC32 recorded in the index file and the \nobject SHA1 recorded in the SHA1 table.  But any of them needs to be \ncomputed as we walk the object and we currently havn't found the best \nway to do that yet.  So I'd suggest postponing this until the tree walk \nis properly implemented to perform well first.\n\n\nNicolas\n"},{"id":"229508","messageId":"20131025075502.GC17029@sigill.intra.peff.net","threadId":"35150","inReplyTo":"xmqqfvrz3nnq.fsf@gitster.dls.corp.google.com","subject":"Re: pack corruption post-mortem","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-10-25T07:55:02Z","receivedAt":"2013-10-25T07:55:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 17, 2013 at 08:47:05AM -0700, Junio C Hamano wrote:\n\n> > In general, I don't think we know enough about patterns of recovery\n> > corruption to say which commands would definitely be worth implementing.\n> > Part of the reason I wrote this up is to document this one case. But\n> > this is the first time in 7 years of git usage that I've had to do this.\n> > So I'd feel a little bit better about sinking time into it after seeing\n> > a few more cases and realizing where the patterns are.\n> \n> There was one area in our Documentation/ set we used to use to keep\n> this kind of message almost as-is; perhaps this message fits there?\n\nI've wondered if that howto section has much value, as they are already\navailable in the list archive, and often show their age after a while.\nStill, I suppose it is a sort of curated list of interesting posts.\n\nHere's my article, all gussied up for the howto directory. Take it or\nleave it.\n\n-- >8 --\nSubject: [PATCH] howto: add article on recovering a corrupted object\n\nThis is an asciidoc-ified version of a corruption post-mortem sent to\nthe git list. It complements the existing howto article, since it covers\na case where the object couldn't be easily recreated or copied from\nelsewhere.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Documentation/Makefile                             |   1 +\n .../howto/recover-corrupted-object-harder.txt      | 242 +++++++++++++++++++++\n 2 files changed, 243 insertions(+)\n create mode 100644 Documentation/howto/recover-corrupted-object-harder.txt\n\ndiff --git a/Documentation/Makefile b/Documentation/Makefile\nindex 4f13a23..91a12c7 100644\n--- a/Documentation/Makefile\n+++ b/Documentation/Makefile\n@@ -53,6 +53,7 @@ SP_ARTICLES += howto/setup-git-server-over-http\n SP_ARTICLES += howto/separating-topic-branches\n SP_ARTICLES += howto/revert-a-faulty-merge\n SP_ARTICLES += howto/recover-corrupted-blob-object\n+SP_ARTICLES += howto/recover-corrupted-object-harder\n SP_ARTICLES += howto/rebuild-from-update-hook\n SP_ARTICLES += howto/rebase-from-internal-branch\n SP_ARTICLES += howto/maintain-git\ndiff --git a/Documentation/howto/recover-corrupted-object-harder.txt b/Documentation/howto/recover-corrupted-object-harder.txt\nnew file mode 100644\nindex 0000000..6f33dac\n--- /dev/null\n+++ b/Documentation/howto/recover-corrupted-object-harder.txt\n@@ -0,0 +1,242 @@\n+Date: Wed, 16 Oct 2013 04:34:01 -0400\n+From: Jeff King <peff@peff.net>\n+Subject: pack corruption post-mortem\n+Abstract: Recovering a corrupted object when no good copy is available.\n+Content-type: text/asciidoc\n+\n+How to recover an object from scratch\n+=====================================\n+\n+I was recently presented with a repository with a corrupted packfile,\n+and was asked if the data was recoverable. This post-mortem describes\n+the steps I took to investigate and fix the problem. I thought others\n+might find the process interesting, and it might help somebody in the\n+same situation.\n+\n+********************************\n+Note: In this case, no good copy of the repository was available. For\n+the much easier case where you can get the corrupted object from\n+elsewhere, see link:recover-corrupted-blob-object.html[this howto].\n+********************************\n+\n+I started with an fsck, which found a problem with exactly one object\n+(I've used $pack and $obj below to keep the output readable, and also\n+because I'll refer to them later):\n+\n+-----------\n+    $ git fsck\n+    error: $pack SHA1 checksum mismatch\n+    error: index CRC mismatch for object $obj from $pack at offset 51653873\n+    error: inflate: data stream error (incorrect data check)\n+    error: cannot unpack $obj from $pack at offset 51653873\n+-----------\n+\n+The pack checksum failing means a byte is munged somewhere, and it is\n+presumably in the object mentioned (since both the index checksum and\n+zlib were failing).\n+\n+Reading the zlib source code, I found that \"incorrect data check\" means\n+that the adler-32 checksum at the end of the zlib data did not match the\n+inflated data. So stepping the data through zlib would not help, as it\n+did not fail until the very end, when we realize the crc does not match.\n+The problematic bytes could be anywhere in the object data.\n+\n+The first thing I did was pull the broken data out of the packfile. I\n+needed to know how big the object was, which I found out with:\n+\n+------------\n+    $ git show-index <$idx | cut -d' ' -f1 | sort -n | grep -A1 51653873\n+    51653873\n+    51664736\n+------------\n+\n+Show-index gives us the list of objects and their offsets. We throw away\n+everything but the offsets, and then sort them so that our interesting\n+offset (which we got from the fsck output above) is followed immediately\n+by the offset of the next object. Now we know that the object data is\n+10863 bytes long, and we can grab it with:\n+\n+------------\n+  dd if=$pack of=object bs=1 skip=51653873 count=10863\n+------------\n+\n+I inspected a hexdump of the data, looking for any obvious bogosity\n+(e.g., a 4K run of zeroes would be a good sign of filesystem\n+corruption). But everything looked pretty reasonable.\n+\n+Note that the \"object\" file isn't fit for feeding straight to zlib; it\n+has the git packed object header, which is variable-length. We want to\n+strip that off so we can start playing with the zlib data directly. You\n+can either work your way through it manually (the format is described in\n+link:../technical/pack-format.html[Documentation/technical/pack-format.txt]),\n+or you can walk through it in a debugger. I did the latter, creating a\n+valid pack like:\n+\n+------------\n+    # pack magic and version\n+    printf 'PACK\\0\\0\\0\\2' >tmp.pack\n+    # pack has one object\n+    printf '\\0\\0\\0\\1' >>tmp.pack\n+    # now add our object data\n+    cat object >>tmp.pack\n+    # and then append the pack trailer\n+    /path/to/git.git/test-sha1 -b <tmp.pack >trailer\n+    cat trailer >>tmp.pack\n+------------\n+\n+and then running \"git index-pack tmp.pack\" in the debugger (stop at\n+unpack_raw_entry). Doing this, I found that there were 3 bytes of header\n+(and the header itself had a sane type and size). So I stripped those\n+off with:\n+\n+------------\n+    dd if=object of=zlib bs=1 skip=3\n+------------\n+\n+I ran the result through zlib's inflate using a custom C program. And\n+while it did report the error, I did get the right number of output\n+bytes (i.e., it matched git's size header that we decoded above). But\n+feeding the result back to \"git hash-object\" didn't produce the same\n+sha1. So there were some wrong bytes, but I didn't know which. The file\n+happened to be C source code, so I hoped I could notice something\n+obviously wrong with it, but I didn't. I even got it to compile!\n+\n+I also tried comparing it to other versions of the same path in the\n+repository, hoping that there would be some part of the diff that didn't\n+make sense. Unfortunately, this happened to be the only revision of this\n+particular file in the repository, so I had nothing to compare against.\n+\n+So I took a different approach. Working under the guess that the\n+corruption was limited to a single byte, I wrote a program to munge each\n+byte individually, and try inflating the result. Since the object was\n+only 10K compressed, that worked out to about 2.5M attempts, which took\n+a few minutes.\n+\n+The program I used is here:\n+\n+----------------------------------------------\n+#include <stdio.h>\n+#include <unistd.h>\n+#include <string.h>\n+#include <signal.h>\n+#include <zlib.h>\n+\n+static int try_zlib(unsigned char *buf, int len)\n+{\n+\t/* make this absurdly large so we don't have to loop */\n+\tstatic unsigned char out[1024*1024];\n+\tz_stream z;\n+\tint ret;\n+\n+\tmemset(&z, 0, sizeof(z));\n+\tinflateInit(&z);\n+\n+\tz.next_in = buf;\n+\tz.avail_in = len;\n+\tz.next_out = out;\n+\tz.avail_out = sizeof(out);\n+\n+\tret = inflate(&z, 0);\n+\tinflateEnd(&z);\n+\treturn ret >= 0;\n+}\n+\n+/* eye candy */\n+static int counter = 0;\n+static void progress(int sig)\n+{\n+\tfprintf(stderr, \"\\r%d\", counter);\n+\talarm(1);\n+}\n+\n+int main(void)\n+{\n+\t/* oversized so we can read the whole buffer in */\n+\tunsigned char buf[1024*1024];\n+\tint len;\n+\tunsigned i, j;\n+\n+\tsignal(SIGALRM, progress);\n+\talarm(1);\n+\n+\tlen = read(0, buf, sizeof(buf));\n+\tfor (i = 0; i < len; i++) {\n+\t\tunsigned char c = buf[i];\n+\t\tfor (j = 0; j <= 0xff; j++) {\n+\t\t\tbuf[i] = j;\n+\n+\t\t\tcounter++;\n+\t\t\tif (try_zlib(buf, len))\n+\t\t\t\tprintf(\"i=%d, j=%x\\n\", i, j);\n+\t\t}\n+\t\tbuf[i] = c;\n+\t}\n+\n+\talarm(0);\n+\tfprintf(stderr, \"\\n\");\n+\treturn 0;\n+}\n+----------------------------------------------\n+\n+I compiled and ran with:\n+\n+-------\n+  gcc -Wall -Werror -O3 munge.c -o munge -lz\n+  ./munge <zlib\n+-------\n+\n+\n+There were a few false positives early on (if you write \"no data\" in the\n+zlib header, zlib thinks it's just fine :) ). But I got a hit about\n+halfway through:\n+\n+-------\n+  i=5642, j=c7\n+-------\n+\n+I let it run to completion, and got a few more hits at the end (where it\n+was munging the crc to match our broken data). So there was a good\n+chance this middle hit was the source of the problem.\n+\n+I confirmed by tweaking the byte in a hex editor, zlib inflating the\n+result (no errors!), and then piping the output into \"git hash-object\",\n+which reported the sha1 of the broken object. Success!\n+\n+I fixed the packfile itself with:\n+\n+-------\n+  chmod +w $pack\n+  printf '\\xc7' | dd of=$pack bs=1 seek=51659518 conv=notrunc\n+  chmod -w $pack\n+-------\n+\n+The `\\xc7` comes from the replacement byte our \"munge\" program found.\n+The offset 51659518 is derived by taking the original object offset\n+(51653873), adding the replacement offset found by \"munge\" (5642), and\n+then adding back in the 3 bytes of git header we stripped.\n+\n+After that, \"git fsck\" ran clean.\n+\n+As for the corruption itself, I was lucky that it was indeed a single\n+byte. In fact, it turned out to be a single bit. The byte 0xc7 was\n+corrupted to 0xc5. So presumably it was caused by faulty hardware, or a\n+cosmic ray.\n+\n+And the aborted attempt to look at the inflated output to see what was\n+wrong? I could have looked forever and never found it. Here's the diff\n+between what the corrupted data inflates to, versus the real data:\n+\n+--------------\n+  -       cp = strtok (arg, \"+\");\n+  +       cp = strtok (arg, \".\");\n+--------------\n+\n+It tweaked one byte and still ended up as valid, readable C that just\n+happened to do something totally different! One takeaway is that on a\n+less unlucky day, looking at the zlib output might have actually been\n+helpful, as most random changes would actually break the C code.\n+\n+But more importantly, git's hashing and checksumming noticed a problem\n+that easily could have gone undetected in another system. The result\n+still compiled, but would have caused an interesting bug (that would\n+have been blamed on some random commit).\n-- \n1.8.4.1.898.g8bf8a41.dirty\n"},{"id":"258837","messageId":"20150401210856.GA23050@peff.net","threadId":"35150","inReplyTo":"20131016083400.GA31266@sigill.intra.peff.net","subject":"[PATCH] howto: document more tools for recovery corruption","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-01T21:08:56Z","receivedAt":"2015-04-01T21:08:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Long ago, I documented a corruption recovery I did and gave\nsome C code that I used to help find a flipped bit.  I had\nto fix a similar case recently, and I ended up writing a few\nmore tools.  I hope nobody ever has to use these, but it\ndoes not hurt to share them, just in case.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n .../howto/recover-corrupted-object-harder.txt      | 237 +++++++++++++++++++++\n 1 file changed, 237 insertions(+)\n\ndiff --git a/Documentation/howto/recover-corrupted-object-harder.txt b/Documentation/howto/recover-corrupted-object-harder.txt\nindex 23e685d..9c4cd09 100644\n--- a/Documentation/howto/recover-corrupted-object-harder.txt\n+++ b/Documentation/howto/recover-corrupted-object-harder.txt\n@@ -240,3 +240,240 @@ But more importantly, git's hashing and checksumming noticed a problem\n that easily could have gone undetected in another system. The result\n still compiled, but would have caused an interesting bug (that would\n have been blamed on some random commit).\n+\n+\n+The adventure continues...\n+--------------------------\n+\n+I ended up doing this again! Same entity, new hardware. The assumption\n+at this point is that the old disk corrupted the packfile, and then the\n+corruption was migrated to the new hardware (because it was done by\n+rsync or similar, and no fsck was done at the time of migration).\n+\n+This time, the affected blob was over 20 megabytes, which was far too\n+large to do a brute-force on. I followed the instructions above to\n+create the `zlib` file. I then used the `inflate` program below to pull\n+the corrupted data from that. Examining that output gave me a hint about\n+where in the file the corruption was. But now I was working with the\n+file itself, not the zlib contents. So knowing the sha1 of the object\n+and the approximate area of the corruption, I used the `sha1-munge`\n+program below to brute-force the correct byte.\n+\n+Here's the inflate program (it's essentially `gunzip` but without the\n+`.gz` header processing):\n+\n+--------------------------\n+#include <stdio.h>\n+#include <string.h>\n+#include <zlib.h>\n+#include <stdlib.h>\n+\n+int main(int argc, char **argv)\n+{\n+\t/*\n+\t * oversized so we can read the whole buffer in;\n+\t * this could actually be switched to streaming\n+\t * to avoid any memory limitations\n+\t */\n+\tstatic unsigned char buf[25 * 1024 * 1024];\n+\tstatic unsigned char out[25 * 1024 * 1024];\n+\tint len;\n+\tz_stream z;\n+\tint ret;\n+\n+\tlen = read(0, buf, sizeof(buf));\n+\tmemset(&z, 0, sizeof(z));\n+\tinflateInit(&z);\n+\n+\tz.next_in = buf;\n+\tz.avail_in = len;\n+\tz.next_out = out;\n+\tz.avail_out = sizeof(out);\n+\n+\tret = inflate(&z, 0);\n+\tif (ret != Z_OK && ret != Z_STREAM_END)\n+\t\tfprintf(stderr, \"initial inflate failed (%d)\\n\", ret);\n+\n+\tfprintf(stderr, \"outputting %lu bytes\", z.total_out);\n+\tfwrite(out, 1, z.total_out, stdout);\n+\treturn 0;\n+}\n+--------------------------\n+\n+And here is the `sha1-munge` program:\n+\n+--------------------------\n+#include <stdio.h>\n+#include <unistd.h>\n+#include <string.h>\n+#include <signal.h>\n+#include <openssl/sha.h>\n+#include <stdlib.h>\n+\n+/* eye candy */\n+static int counter = 0;\n+static void progress(int sig)\n+{\n+\tfprintf(stderr, \"\\r%d\", counter);\n+\talarm(1);\n+}\n+\n+static const signed char hexval_table[256] = {\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 00-07 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 08-0f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 10-17 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 18-1f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 20-27 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 28-2f */\n+\t  0,  1,  2,  3,  4,  5,  6,  7,\t\t/* 30-37 */\n+\t  8,  9, -1, -1, -1, -1, -1, -1,\t\t/* 38-3f */\n+\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 40-47 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 48-4f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 50-57 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 58-5f */\n+\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 60-67 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 68-67 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 70-77 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 78-7f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 80-87 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 88-8f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 90-97 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 98-9f */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a0-a7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a8-af */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b0-b7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b8-bf */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c0-c7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c8-cf */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d0-d7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d8-df */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e0-e7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e8-ef */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f0-f7 */\n+\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f8-ff */\n+};\n+\n+static inline unsigned int hexval(unsigned char c)\n+{\n+return hexval_table[c];\n+}\n+\n+static int get_sha1_hex(const char *hex, unsigned char *sha1)\n+{\n+\tint i;\n+\tfor (i = 0; i < 20; i++) {\n+\t\tunsigned int val;\n+\t\t/*\n+\t\t * hex[1]=='\\0' is caught when val is checked below,\n+\t\t * but if hex[0] is NUL we have to avoid reading\n+\t\t * past the end of the string:\n+\t\t */\n+\t\tif (!hex[0])\n+\t\t\treturn -1;\n+\t\tval = (hexval(hex[0]) << 4) | hexval(hex[1]);\n+\t\tif (val & ~0xff)\n+\t\t\treturn -1;\n+\t\t*sha1++ = val;\n+\t\thex += 2;\n+\t}\n+\treturn 0;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\t/* oversized so we can read the whole buffer in */\n+\tstatic unsigned char buf[25 * 1024 * 1024];\n+\tchar header[32];\n+\tint header_len;\n+\tunsigned char have[20], want[20];\n+\tint start, len;\n+\tSHA_CTX orig;\n+\tunsigned i, j;\n+\n+\tif (!argv[1] || get_sha1_hex(argv[1], want)) {\n+\t\tfprintf(stderr, \"usage: sha1-munge <sha1> [start] <file.in\\n\");\n+\t\treturn 1;\n+\t}\n+\n+\tif (argv[2])\n+\t\tstart = atoi(argv[2]);\n+\telse\n+\t\tstart = 0;\n+\n+\tlen = read(0, buf, sizeof(buf));\n+\theader_len = sprintf(header, \"blob %d\", len) + 1;\n+\tfprintf(stderr, \"using header: %s\\n\", header);\n+\n+\t/*\n+\t * We keep a running sha1 so that if you are munging\n+\t * near the end of the file, we do not have to re-sha1\n+\t * the unchanged earlier bytes\n+\t */\n+\tSHA1_Init(&orig);\n+\tSHA1_Update(&orig, header, header_len);\n+\tif (start)\n+\t\tSHA1_Update(&orig, buf, start);\n+\n+\tsignal(SIGALRM, progress);\n+\talarm(1);\n+\n+\tfor (i = start; i < len; i++) {\n+\t\tunsigned char c;\n+\t\tSHA_CTX x;\n+\n+#if 0\n+\t\t/*\n+\t\t * deletion -- this would not actually work in practice,\n+\t\t * I think, because we've already committed to a\n+\t\t * particular size in the header. Ditto for addition\n+\t\t * below. In those cases, you'd have to do the whole\n+\t\t * sha1 from scratch, or possibly keep three running\n+\t\t * \"orig\" sha1 computations going.\n+\t\t */\n+\t\tmemcpy(&x, &orig, sizeof(x));\n+\t\tSHA1_Update(&x, buf + i + 1, len - i - 1);\n+\t\tSHA1_Final(have, &x);\n+\t\tif (!memcmp(have, want, 20))\n+\t\t\tprintf(\"i=%d, deletion\\n\", i);\n+#endif\n+\n+\t\t/*\n+\t\t * replacement -- note that this tries each of the 256\n+\t\t * possible bytes. If you suspect a single-bit flip,\n+\t\t * it would be much shorter to just try the 8\n+\t\t * bit-flipped variants.\n+\t\t */\n+\t\tc = buf[i];\n+\t\tfor (j = 0; j <= 0xff; j++) {\n+\t\t\tbuf[i] = j;\n+\n+\t\t\tmemcpy(&x, &orig, sizeof(x));\n+\t\t\tSHA1_Update(&x, buf + i, len - i);\n+\t\t\tSHA1_Final(have, &x);\n+\t\t\tif (!memcmp(have, want, 20))\n+\t\t\t\tprintf(\"i=%d, j=%02x\\n\", i, j);\n+\t\t}\n+\t\tbuf[i] = c;\n+\n+#if 0\n+\t\t/* addition */\n+\t\tfor (j = 0; j <= 0xff; j++) {\n+\t\t\tunsigned char extra = j;\n+\t\t\tmemcpy(&x, &orig, sizeof(x));\n+\t\t\tSHA1_Update(&x, &extra, 1);\n+\t\t\tSHA1_Update(&x, buf + i, len - i);\n+\t\t\tSHA1_Final(have, &x);\n+\t\t\tif (!memcmp(have, want, 20))\n+\t\t\t\tprintf(\"i=%d, addition=%02x\", i, j);\n+\t\t}\n+#endif\n+\n+\t\tSHA1_Update(&orig, buf + i, 1);\n+\t\tcounter++;\n+\t}\n+\n+\talarm(0);\n+\tfprintf(stderr, \"\\r%d\\n\", counter);\n+\treturn 0;\n+}\n+--------------------------\n-- \n2.4.0.rc0.363.gf9f328b\n"},{"id":"258841","messageId":"xmqq4mozmqw3.fsf@gitster.dls.corp.google.com","threadId":"35150","inReplyTo":"20150401210856.GA23050@peff.net","subject":"Re: [PATCH] howto: document more tools for recovery corruption","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-01T22:21:16Z","receivedAt":"2015-04-01T22:21:16Z","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> Long ago, I documented a corruption recovery I did and gave\n> some C code that I used to help find a flipped bit.  I had\n> to fix a similar case recently, and I ended up writing a few\n> more tools.  I hope nobody ever has to use these, but it\n> does not hurt to share them, just in case.\n\nI am having a hard time deciding if I should take the Date: header\nof the patch e-mail into consideration.  The munge thing looks\nserious enough, though.\n\n\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  .../howto/recover-corrupted-object-harder.txt      | 237 +++++++++++++++++++++\n>  1 file changed, 237 insertions(+)\n>\n> diff --git a/Documentation/howto/recover-corrupted-object-harder.txt\n> b/Documentation/howto/recover-corrupted-object-harder.txt\n> index 23e685d..9c4cd09 100644\n> --- a/Documentation/howto/recover-corrupted-object-harder.txt\n> +++ b/Documentation/howto/recover-corrupted-object-harder.txt\n> @@ -240,3 +240,240 @@ But more importantly, git's hashing and checksumming noticed a problem\n>  that easily could have gone undetected in another system. The result\n>  still compiled, but would have caused an interesting bug (that would\n>  have been blamed on some random commit).\n> +\n> +\n> +The adventure continues...\n> +--------------------------\n> +\n> +I ended up doing this again! Same entity, new hardware. The assumption\n> +at this point is that the old disk corrupted the packfile, and then the\n> +corruption was migrated to the new hardware (because it was done by\n> +rsync or similar, and no fsck was done at the time of migration).\n> +\n> +This time, the affected blob was over 20 megabytes, which was far too\n> +large to do a brute-force on. I followed the instructions above to\n> +create the `zlib` file. I then used the `inflate` program below to pull\n> +the corrupted data from that. Examining that output gave me a hint about\n> +where in the file the corruption was. But now I was working with the\n> +file itself, not the zlib contents. So knowing the sha1 of the object\n> +and the approximate area of the corruption, I used the `sha1-munge`\n> +program below to brute-force the correct byte.\n> +\n> +Here's the inflate program (it's essentially `gunzip` but without the\n> +`.gz` header processing):\n> +\n> +--------------------------\n> +#include <stdio.h>\n> +#include <string.h>\n> +#include <zlib.h>\n> +#include <stdlib.h>\n> +\n> +int main(int argc, char **argv)\n> +{\n> +\t/*\n> +\t * oversized so we can read the whole buffer in;\n> +\t * this could actually be switched to streaming\n> +\t * to avoid any memory limitations\n> +\t */\n> +\tstatic unsigned char buf[25 * 1024 * 1024];\n> +\tstatic unsigned char out[25 * 1024 * 1024];\n> +\tint len;\n> +\tz_stream z;\n> +\tint ret;\n> +\n> +\tlen = read(0, buf, sizeof(buf));\n> +\tmemset(&z, 0, sizeof(z));\n> +\tinflateInit(&z);\n> +\n> +\tz.next_in = buf;\n> +\tz.avail_in = len;\n> +\tz.next_out = out;\n> +\tz.avail_out = sizeof(out);\n> +\n> +\tret = inflate(&z, 0);\n> +\tif (ret != Z_OK && ret != Z_STREAM_END)\n> +\t\tfprintf(stderr, \"initial inflate failed (%d)\\n\", ret);\n> +\n> +\tfprintf(stderr, \"outputting %lu bytes\", z.total_out);\n> +\tfwrite(out, 1, z.total_out, stdout);\n> +\treturn 0;\n> +}\n> +--------------------------\n> +\n> +And here is the `sha1-munge` program:\n> +\n> +--------------------------\n> +#include <stdio.h>\n> +#include <unistd.h>\n> +#include <string.h>\n> +#include <signal.h>\n> +#include <openssl/sha.h>\n> +#include <stdlib.h>\n> +\n> +/* eye candy */\n> +static int counter = 0;\n> +static void progress(int sig)\n> +{\n> +\tfprintf(stderr, \"\\r%d\", counter);\n> +\talarm(1);\n> +}\n> +\n> +static const signed char hexval_table[256] = {\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 00-07 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 08-0f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 10-17 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 18-1f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 20-27 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 28-2f */\n> +\t  0,  1,  2,  3,  4,  5,  6,  7,\t\t/* 30-37 */\n> +\t  8,  9, -1, -1, -1, -1, -1, -1,\t\t/* 38-3f */\n> +\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 40-47 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 48-4f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 50-57 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 58-5f */\n> +\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 60-67 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 68-67 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 70-77 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 78-7f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 80-87 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 88-8f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 90-97 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 98-9f */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a0-a7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a8-af */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b0-b7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b8-bf */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c0-c7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c8-cf */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d0-d7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d8-df */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e0-e7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e8-ef */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f0-f7 */\n> +\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f8-ff */\n> +};\n> +\n> +static inline unsigned int hexval(unsigned char c)\n> +{\n> +return hexval_table[c];\n> +}\n> +\n> +static int get_sha1_hex(const char *hex, unsigned char *sha1)\n> +{\n> +\tint i;\n> +\tfor (i = 0; i < 20; i++) {\n> +\t\tunsigned int val;\n> +\t\t/*\n> +\t\t * hex[1]=='\\0' is caught when val is checked below,\n> +\t\t * but if hex[0] is NUL we have to avoid reading\n> +\t\t * past the end of the string:\n> +\t\t */\n> +\t\tif (!hex[0])\n> +\t\t\treturn -1;\n> +\t\tval = (hexval(hex[0]) << 4) | hexval(hex[1]);\n> +\t\tif (val & ~0xff)\n> +\t\t\treturn -1;\n> +\t\t*sha1++ = val;\n> +\t\thex += 2;\n> +\t}\n> +\treturn 0;\n> +}\n> +\n> +int main(int argc, char **argv)\n> +{\n> +\t/* oversized so we can read the whole buffer in */\n> +\tstatic unsigned char buf[25 * 1024 * 1024];\n> +\tchar header[32];\n> +\tint header_len;\n> +\tunsigned char have[20], want[20];\n> +\tint start, len;\n> +\tSHA_CTX orig;\n> +\tunsigned i, j;\n> +\n> +\tif (!argv[1] || get_sha1_hex(argv[1], want)) {\n> +\t\tfprintf(stderr, \"usage: sha1-munge <sha1> [start] <file.in\\n\");\n> +\t\treturn 1;\n> +\t}\n> +\n> +\tif (argv[2])\n> +\t\tstart = atoi(argv[2]);\n> +\telse\n> +\t\tstart = 0;\n> +\n> +\tlen = read(0, buf, sizeof(buf));\n> +\theader_len = sprintf(header, \"blob %d\", len) + 1;\n> +\tfprintf(stderr, \"using header: %s\\n\", header);\n> +\n> +\t/*\n> +\t * We keep a running sha1 so that if you are munging\n> +\t * near the end of the file, we do not have to re-sha1\n> +\t * the unchanged earlier bytes\n> +\t */\n> +\tSHA1_Init(&orig);\n> +\tSHA1_Update(&orig, header, header_len);\n> +\tif (start)\n> +\t\tSHA1_Update(&orig, buf, start);\n> +\n> +\tsignal(SIGALRM, progress);\n> +\talarm(1);\n> +\n> +\tfor (i = start; i < len; i++) {\n> +\t\tunsigned char c;\n> +\t\tSHA_CTX x;\n> +\n> +#if 0\n> +\t\t/*\n> +\t\t * deletion -- this would not actually work in practice,\n> +\t\t * I think, because we've already committed to a\n> +\t\t * particular size in the header. Ditto for addition\n> +\t\t * below. In those cases, you'd have to do the whole\n> +\t\t * sha1 from scratch, or possibly keep three running\n> +\t\t * \"orig\" sha1 computations going.\n> +\t\t */\n> +\t\tmemcpy(&x, &orig, sizeof(x));\n> +\t\tSHA1_Update(&x, buf + i + 1, len - i - 1);\n> +\t\tSHA1_Final(have, &x);\n> +\t\tif (!memcmp(have, want, 20))\n> +\t\t\tprintf(\"i=%d, deletion\\n\", i);\n> +#endif\n> +\n> +\t\t/*\n> +\t\t * replacement -- note that this tries each of the 256\n> +\t\t * possible bytes. If you suspect a single-bit flip,\n> +\t\t * it would be much shorter to just try the 8\n> +\t\t * bit-flipped variants.\n> +\t\t */\n> +\t\tc = buf[i];\n> +\t\tfor (j = 0; j <= 0xff; j++) {\n> +\t\t\tbuf[i] = j;\n> +\n> +\t\t\tmemcpy(&x, &orig, sizeof(x));\n> +\t\t\tSHA1_Update(&x, buf + i, len - i);\n> +\t\t\tSHA1_Final(have, &x);\n> +\t\t\tif (!memcmp(have, want, 20))\n> +\t\t\t\tprintf(\"i=%d, j=%02x\\n\", i, j);\n> +\t\t}\n> +\t\tbuf[i] = c;\n> +\n> +#if 0\n> +\t\t/* addition */\n> +\t\tfor (j = 0; j <= 0xff; j++) {\n> +\t\t\tunsigned char extra = j;\n> +\t\t\tmemcpy(&x, &orig, sizeof(x));\n> +\t\t\tSHA1_Update(&x, &extra, 1);\n> +\t\t\tSHA1_Update(&x, buf + i, len - i);\n> +\t\t\tSHA1_Final(have, &x);\n> +\t\t\tif (!memcmp(have, want, 20))\n> +\t\t\t\tprintf(\"i=%d, addition=%02x\", i, j);\n> +\t\t}\n> +#endif\n> +\n> +\t\tSHA1_Update(&orig, buf + i, 1);\n> +\t\tcounter++;\n> +\t}\n> +\n> +\talarm(0);\n> +\tfprintf(stderr, \"\\r%d\\n\", counter);\n> +\treturn 0;\n> +}\n> +--------------------------\n"},{"id":"258844","messageId":"20150402004955.GA25634@peff.net","threadId":"35150","inReplyTo":"xmqq4mozmqw3.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] howto: document more tools for recovery corruption","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-02T00:49:55Z","receivedAt":"2015-04-02T00:49:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 01, 2015 at 03:21:16PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > Long ago, I documented a corruption recovery I did and gave\n> > some C code that I used to help find a flipped bit.  I had\n> > to fix a similar case recently, and I ended up writing a few\n> > more tools.  I hope nobody ever has to use these, but it\n> > does not hurt to share them, just in case.\n> \n> I am having a hard time deciding if I should take the Date: header\n> of the patch e-mail into consideration.  The munge thing looks\n> serious enough, though.\n\nHeh, no, this is sadly a serious thing that I did today (but I was able\nto detect and correct a single flipped bit in a 60MB packfile, which is\nkind of neat, I guess).\n\nI hesitated sending them at all because they are not really note-worthy.\nOTOH, during today's exercise I found the instructions and sample\nprogram I had written last time to be very useful, so perhaps it can\nhelp somebody (or even me) at some later today.\n\n-Peff\n"}]}