Linux下的差异和补丁工具

我爱我贾

补丁（Patch）是软件生命周期管理的一部分，当软件有BUG需要进行修复，或者新增特性时都可以通过打补丁的形式更新到用户手里。补丁按照作用可以分为N种：修复BUG的叫BUGFIX、解决安全问题的叫安全补丁、等等。软件更新中的补丁文件类型主要是二进制的，补丁也大量用于代码开发过程中，想当年Linux内核的代码主要就是靠社区开发者把修改制作成补丁发给Linus大佬，据说Apache服务器的名字就来自“A Patch”，如今的版本控制软件SVN、Git虽说可以自动完成修改的合并，但其原理也是基于差异和补丁的思想。



差异和补丁

补丁是软件、代码、各种更新中非常重要的手段，废话不多说，今天主要介绍一下Linux生成补丁的差异工具（Diff）和打补丁的工具（Patch）：

• 历史悠久的diff 和 patch，主要用于制作文本类型的补丁。
  
• 二进制差异和补丁工具bsdiff 和 bspath
  
• Google的小胡瓜Courgette。
  

diff 和 patch

diff和patch在代码开发过程中大量使用，用于文本文件。就以代码为例做下简单演示：
假设有文件test.cpp内容如下（暂且叫它为test_v1.0.cpp）：
#include <iostream>
#include <fstream>

int main()
{
        std::cout << "hello" << std::endl;
}
经过一次修改后，内容如下（修改后的文件内容如test_v1.1.cpp）：
#include <iostream>
#include <string>

int main()
{
        std::cout << "hello world" << std::endl;
}
制作补丁：
diff -u test_v1.0.cpp test_v1.1.cpp > test.patch生成的补丁内容如下，看着是不是很眼熟，svn diff和git diff差不多也长这样：
--- test_v1.0.cpp       2018-12-08 14:51:39.551061200 +0800
+++ test_v1.1.cpp       2018-12-08 14:47:59.530074200 +0800
@@ -1,7 +1,7 @@
#include <iostream>
-#include <fstream>
+#include <string>

int main()
{
-       std::cout << "hello" << std::endl;
+       std::cout << "hello world" << std::endl;
}
打补丁，下面任何一条命令都可以，执行完就把test_v1.0.cpp的内容更新到和test_v1.1.cpp完全一样了：
patch -p0 <test.patch
patch test_v1.0.cpp test.patchPS. 文件夹之间也可以直接做差异，示例如下：
diff -Naur sources-orig/ sources-fixed/ > source.patch
patch -p1 < source.patch不要问我这些命令参数到底是什么意思，自行--help或者google！
bsdiff 和 bspatch

虽说diff和patch也可以用来对二进制文件进行差异，但生成的差异文件太大，效果一般。对于二进制文件要进行差异，有一对更好用的工具bsdiff和bspatch，这两个工具在Googe Chromium自动更新中使用，代码简单而强悍，很容易嵌入到自己的工程。
两个命令的用法如下：
bsdiff oldfile newfile patchfile  
bspatch oldfile newfile patchfile

• bsdiff - 对oldfile和newfile进行差异，生成补丁文件patchfile。bsdiff是比较费内存的，需要大概max(17n,9n+m)+O(1)字节（其中：n是oldfile的大小，m是newfile的大小），时间复杂度为O((n+m) log n)，对于大文件还是挺花时间的，不过一般情况下制作补丁是在软件开发者手里进行的，只要保证打补丁的过程速度够快，问题也不大。
  
• bspatch - 对oldfile打补丁patchfile，生成newfile。bspatch对内存的需求是n+m+O(1)字节，时间复杂度为O(n+m)，速度不错。
  

下面就以一个游戏服务器可执行文件为例，大小大概为386M：
差异下制作二进制补丁：
time bsdiff 20181101R1/BillServer  20181109/BillServer  BillServer.patch

real    5m7.083s
user    5m4.776s
sys 0m2.022s在比较强力的服务器上面竟然用了5分钟。看下生成的结果：
ll -h 20181101R1/BillServer  20181109/BillServer  BillServer.patch BillServer.patch
-rwxrwxr-x 1 ztgame ztgame 386M 11月  1 17:02 20181101R1/BillServer
-rwxrwxr-x 1 ztgame ztgame 386M 11月  8 19:15 20181109/BillServer
-rw-rw-r-- 1 ztgame ztgame 5.7M 12月  8 15:18 BillServer.patch好在补丁内容是非常小只有5.7MB，毕竟时间不久，两个版本之间的差异还没有多大。
打补丁：
time bsdiff-4.3/bspatch 20181101R1/BillServer BillServer BillServer.patch

real    0m3.225s
user    0m2.694s
sys 0m0.528s速度很快，完全可以接受。验证下结果，没啥问题：
md5sum 20181109R1/BillServer BillServer
5f028efba51254d557e0e97e41d89763  20181109R1_ZT2/release/BillServer
5f028efba51254d557e0e97e41d89763  BillServer可以看到对游戏服务器版本的更新，采用二进制差异进行会更快：更小的网络中转、更快的补丁时间。
Courgette

上面提到Google这帮大神，在做Chrom自动更新时，选择了bsdiff和bspatch方案，但他们还不满足于此，还是觉得bsdiff生成的补丁有些大，要做到极致，最后自行开发了一套差异和补丁机制Courgette，特别时对代码生成文件效果极佳。
一般，使用bsdiff大概过程是这样的：
server:
        diff = bsdiff(original, update)
        transmit diff

    client:
        receive diff
        update = bspatch(original, diff)Courgette另辟蹊径，有些时候我们修改一两行代码，生成的可执行文件的差异会很大，但是源码其实时没有多大差异的，于是先进行反编译，然后对反编译的汇编代码进行调整（这步是最关键的），最终使用汇编代码进行差异。大概过程如下：
server:
    asm_old = disassemble(original)
    asm_new = disassemble(update)
    asm_new_adjusted = adjust(asm_new, asm_old)
    asm_diff = bsdiff(asm_old, asm_new_adjusted)
    transmit asm_diff

client:
    receive asm_diff
    asm_old = disassemble(original)
    asm_new_adjusted = bspatch(asm_old, asm_diff)
    update = assemble(asm_new_adjusted)下面是Google的对比数据：
完整更新     10,385,920
bsdiff更新    704,512
Courgette更新       78,848效果还是很明显的，其实不光对于可执行文件，普通二进制Courgette也是可以搞定的。不细说了，有兴趣的直接看参考资料里面的链接。Courgette并没有进行实测，它的代码位于Chromium项目，需要自行进行编译，时间原因了解下即可，若那天要用一定要尝试下。
参考资料

• https://opensource.com/article/18/8/diffs-patches
  
• http://www.daemonology.net/bsdiff/
  
• http://dev.chromium.org/developers/design-documents/software-updates-courgette