Theme Preview

修复损坏的 git pack 文件

由 李晓岚 在 2018年08月02日发表

事由

从朋友处得到一个 git repo 的 tgz 存档文件,解压之,然后使用 git fsck 来校验存档的完整性,当看到输出 error: ./objects/pack/pack-73ca*.pack SHA1 checksum mismatch 时,心想:“完蛋了,十几个 G 的文件损坏了,又得重来来过”。转念一想,有没有可能修复呢?

声明

本文中不涉及 git pack 文件自身的任何修复信息,所有修复信息都来自外部信源。据我所知,git pack 文件也不包含任何冗余信息可以用于自愈。

文中所有 git object id 都经过编辑处理。

意外的惊喜

下面是 git fsck 完整的输出结果。乍一看,很多行错误,研判之后发现其实只有三五个 object 损坏。

leexiaolan@cherry:~/corrupted.git$ git fsck
Checking object directories: 100% (256/256), done.
error: ./objects/pack/pack-73ca*.pack SHA1 checksum mismatch
error: index CRC mismatch for object 600f* from ./objects/pack/pack-73ca*.pack at offset 705539900
error: inflate: data stream error (incorrect data check)
error: cannot unpack 600f* from ./objects/pack/pack-73ca*.pack at offset 705539900
error: index CRC mismatch for object c7cd* from ./objects/pack/pack-73ca*.pack at offset 3409251380
error: inflate: data stream error (incorrect data check)
error: cannot unpack c7cd* from ./objects/pack/pack-73ca*.pack at offset 3409251380
error: inflate: data stream error (incorrect data check)
error: failed to read delta base object c7cd* at offset 3409251380 from ./objects/pack/pack-73ca*.pack
error: cannot unpack b7d6* from ./objects/pack/pack-73ca*.pack at offset 3435711445
error: index CRC mismatch for object c0b6* from ./objects/pack/pack-73ca*.pack at offset 6495930501
error: inflate: data stream error (incorrect data check)
error: failed to unpack compressed delta at offset 6495930510 from ./objects/pack/pack-73ca*.pack
error: cannot unpack c0b6* from ./objects/pack/pack-73ca*.pack at offset 6495930501
error: inflate: data stream error (incorrect data check)
error: failed to unpack compressed delta at offset 6495930510 from ./objects/pack/pack-73ca*.pack
error: failed to read delta base object c0b6* at offset 6495930501 from ./objects/pack/pack-73ca*.pack
error: cannot unpack 3efb* from ./objects/pack/pack-73ca*.pack at offset 6506530415
error: inflate: data stream error (incorrect data check)
error: failed to unpack compressed delta at offset 6495930510 from ./objects/pack/pack-73ca*.pack
error: failed to read delta base object c0b6* at offset 6495930501 from ./objects/pack/pack-73ca*.pack
error: cannot unpack 9db7* from ./objects/pack/pack-73ca*.pack at offset 6684278448
error: index CRC mismatch for object 3b53* from ./objects/pack/pack-73ca*.pack at offset 15644018296
error: inflate: data stream error (incorrect data check)
error: cannot unpack 3b53* from ./objects/pack/pack-73ca*.pack at offset 15644018296
Checking objects: 100% (7812/7812), done.

在对 git fsck 的结果失望过后,回想起解压过程中,有看到 tmp_pack_* 之类的文件。很多程序在处理文件时都是先用临时文件来保存中间结果,等所有写操作都完成之后,再将临时文件重命名为期望的文件名,gitpack 文件的操作也如此。如果残留的 tmp_pack_* 临时文件和损坏的 pack-73ca*.pack 文件相关的话,tmp_pack_* 的内容应该就是 pack-73ca*.pack 的前半部分。所以,上述 git fsck 报告中损坏的 object 在文件中的位置 offset,如果小于 tmp_pack_* 文件长度,则很可能 tmp_pack_* 中包含了损坏 object 的正确内容,继而得以从 tmp_pack_* 中恢复此 object

那到底 tmp_pack_*pack-73ca*.pack 是否相关呢?那就来比较一下两文件的内容。

leexiaolan@cherry:~/corrupted.git/objects/pack$ cmp -lb pack-73ca*.pack tmp_pack_h3N0ZY
cmp: EOF on tmp_pack_h3N0ZY
 709450211 175 }    135 ]
3157919099   7 ^G    47 '
3417553763 266 M-6  226 M-^V
6501742392  55 -     15 ^M

tmp_pack_* 文件长度大于 7G,和 pack-73ca*.pack 只存在 4 个字节的差异,很明显是相关的。再对比 git fsck 的输出,除了偏移 3157919098cmp 输出为从 1 开始的计数,非 0 开始的偏移)之外,其它三处附近均有 object 损坏,故将这三处用 tmp_pack_* 的数据去恢复 pack-73ca*.pack 中对应数据。对恢复之后的结果执行 git fsck,看看有什么变化。

leexiaolan@cherry:~/corrupted.git/objects/pack$ T=709450210; dd if=tmp_pack_h3N0ZY \
  of=pack-73ca*.pack bs=1 count=1 skip=$T seek=$T conv=notrunc
1+0 records in
1+0 records out
1 byte copied, 0.0396145 s, 0.0 kB/s
leexiaolan@cherry:~/corrupted.git/objects/pack$ T=3417553762; dd if=tmp_pack_h3N0ZY \
  of=pack-73ca*.pack bs=1 count=1 skip=$T seek=$T conv=notrunc
1+0 records in
1+0 records out
1 byte copied, 0.0237443 s, 0.0 kB/s
leexiaolan@cherry:~/corrupted.git/objects/pack$ T=6501742391; dd if=tmp_pack_h3N0ZY \
  of=pack-73ca*.pack bs=1 count=1 skip=$T seek=$T conv=notrunc
1+0 records in
1+0 records out
1 byte copied, 0.0455239 s, 0.0 kB/s
leexiaolan@cherry:~/corrupted.git$ git fsck
Checking object directories: 100% (256/256), done.
error: ./objects/pack/pack-73ca*.pack SHA1 checksum mismatch
error: index CRC mismatch for object 3b53* from ./objects/pack/pack-73ca*.pack at offset 15644018296
error: inflate: data stream error (incorrect data check)
error: cannot unpack 3b53* from ./objects/pack/pack-73ca*.pack at offset 15644018296
Checking objects: 100% (7812/7812), done.

Hooray! git fsck 报告只有一个 object 损坏了,但这个 object 位于偏移 15644018296,大于 tmp_pack_* 文件大小,tmp_pack_* 已经无能为力了。

反观字节损坏模式

上面 cmp 输出中报告有 4 个字节差异,其中我们已经恢复到 pack-73ca*.pack 文件的有三处,而且 git fsck 的结果也说明这三处 tmp_pack_* 中保存的是正确值,相反,被故意忽略的那个字节,保存在 pack-73ca*.pack 中的值才是正确的,对应 tmp_pack_* 中的值是损坏的。总结下来,损坏数据如下(cmp 输出为八进制)。

corrupted    correct
     0175    0135
      047      07
     0266    0226
      055     015

很明显,corrupted - correct == 040, 损坏的数据都是每个字节的第五个 bit 意外置 1。如果我们对偏移 15644018296 损坏的 object 做这样的假设:

  1. 损坏的字节也是因为第五个 bit 置位。
  2. 整个 object 中,有且只有一个字节损坏。

基于这样的假设,有没有可能通过穷举损坏的字节来恢复最后一个 object 数据呢?

穷举

阅读 git-show-index文档 得知,pack-*.idx 中保存每个 objectpack 中的偏移和 CRC32。同样假定这些保存在 pack-*.idx 文件中的信息是正确的,因此穷举过程中,可以通过计算 CRC32 来验证合法性。通过源代码 pack-objects.c 得知,pack 文件中相邻 object 之间是没有任何其它数据或 padding 的,因此可以通过前后两个 object 的偏移之差来计算前面 object 的大小。通过偏移和大小,已经可以获取到 object 的数据了,虽然这个数据是损坏的。有了这些信息,便可以设计一个穷举过程来恢复数据了。

穷举过程大概是这样的:对于损坏数据中,每一个第五 bit 被置位的字节,我们都尝试将其清零,然后计算 CRC32,若清零后计算得到的 CRC32pack-*.idx 文件中保存的值相同,则认为找到了损坏的字节。

leexiaolan@cherry:~/corrupted.git/objects/pack$ git show-index<pack-*.idx|sort -n|grep \\b3b53 -A1
15644018296 3b53* (3bbff14e)
15651154929 eda3* (2e391a6d)
# 损坏 `object` `3b53*` 大小为 15651154929-15644018296,
# 偏移为 15644018296,CRC32 为 0x3bbff14e
leexiaolan@cherry:~/corrupted.git/objects/pack$ cat corruption
#!/usr/bin/env python2
# Parameters: pack offset length expectedCrc [start [end]]

import sys
from zlib import crc32

def main():
  argv = list(sys.argv[1:])
  pack = argv.pop(0)
  offset = int(argv.pop(0), 0)
  length = int(argv.pop(0), 0)
  expectedCrc = int(argv.pop(0), 0) & 0xffffffff
  start = int(argv.pop(0), 0) if argv else 0
  end = int(argv.pop(0), 0) if argv else sys.maxint

  with open(pack, 'rb') as fi:
    fi.seek(offset)
    d=fi.read(length)

  prev = crc32(d[:start]) if 0 < start else 0
  for i in range(start, min(end, len(d))):
    if i % 4096 == 0: print 'trying', hex(i)
    byte = ord(d[i])
    if (byte & 0x20) != 0:
      crc = crc32(d[i+1:], crc32(chr(byte & ~0x20), prev)) & 0xffffffff
      if crc == expectedCrc:
    print 'found fix at offset', hex(i), hex(byte), '->', hex(byte & ~0x20)
    return 0

    prev = crc32(d[i], prev)

  print 'not found'
  return 1

if '__main__' == __name__:
  sys.exit(main())
leexiaolan@cherry:~/corrupted.git/objects/pack$ ./corruption pack-*.pack \
  15644018296 $((15651154929-15644018296)) 0x3bbff14e
... # 几个小时后
trying 0x1d0000
trying 0x1d1000
found fix at offset 0x1d1e81 0xa1 -> 0x81

验证

前面穷举过程中找到的解,虽然通过了 CRC32 的验证,但是不排除碰撞的可能,尽管概率比较小。如果修复后的 packgit fsck 没有报告 SHA1 checksum mismatch,因为两种不同方法的 checksum 都同时碰撞的概率就非常小了,这样就有很高的置信度认为修复是成功的。

leexiaolan@cherry:~/corrupted.git/objects/pack$ echo -en \\x81 | \
  dd of=pack-73ca*.pack conv=notrunc bs=1 seek=$((15644018296+0x1d1e81))
1+0 records in
1+0 records out
1 byte copied, 0.023496 s, 0.0 kB/s
leexiaolan@cherry:~/corrupted.git$ git fsck
Checking object directories: 100% (256/256), done.
Checking objects: 100% (7812/7812), done.

'git fsck` 没有报告任何错误,看起来上面所做假设都是对的,修复很成功。

结论

本文中涉及的文件损坏,不是因为网络传输导致的,网络传输的是 tgz 存档。tgz 存档文件本身已经做过 md5sum 校验无误。损坏进入的时机应该是在 tgz 存档文件创建之时。损坏字节的变化模式也很明显,都是第五个 bit 意外置位,这个模式也是我们得以修复的关键所在。最后,损坏的 git object 大小 7M+,穷举所耗费时间 python 代码大概 4,5 个小时(单 CPU 时间),基本可以接受。

标签:gitdata corruption

comments powered by Disqus