zhuyie's blog

bsdiff源码解析

Posted on Feb 16, 2022

简介

bsdiff是一种二进制增量编码（delta encoding1）算法。它由Colin Percival发明及开源，被广泛应用于各类二进制数据（特别是可执行程序）的增量更新（delta updates）场景中，例如Android使用bsdiff来减小OTA更新数据包的尺寸2。

bsdiff的官网在https://www.daemonology.net/bsdiff/，它由bsdiff和bspatch两个模块组成，前者负责生成新版本相对于旧版本的增量数据，后者负责基于旧版本和增量数据还原出新版本。bsdiff目前的最新版本是（很多年发布的）4.3。

作为一个典型的博士生作品，bsdiff源码的工程化水平相当一般，代码结构和风格、变量命名等都比较马虎。为了便于理解，这里结合4.3的源码进行一个详细点的分析。

原理

Colin Percival有一篇3页的小论文Naive differences of executable code，描述了bsdiff算法的基本原理和思路。简单来说，源代码中的少量修改（例如增/删/改几行代码）反映到编译后的可执行文件上会出现修改量大幅度放大的情况。这主要是因为可执行文件中会记录很多地址类数据（例如分支语句的跳转目标），大量的地址会因为少量源代码的修改而出现位移。此时如果按照传统的copy-and-insert方法来构造binary patch，效率会相当低下。在作者的实验中，一个500kB左右的可执行程序（按常规经验至少对应10万行以上的C源码）的源码中进行1行修改，会产生约50kB的patch文件。

对这个问题的一种可能的处理方法是，在算法上加入对可执行文件的格式和内部结构的理解。例如通过反汇编的方式将可执行文件还原为类汇编源码的形态，再对新旧两个版本的源码进行增量编码。这种方法的问题是算法复杂且和特定平台相关。Google的Courgette就用了这种思路。

bsdiff的目标是以平台无关的方式解决上述问题。它基于两个重要观察：

  • 在可执行文件的与源码修改无直接对应关系的区域，所产生的差异是相当稀疏的（sparse）：(a)地址位移仅影响到部分的编译后指令；(b)地址位移的幅度一般较小，很多时候只影响到地址字的最后1～2个字节；
  • 数据和代码倾向于按整块的方式移动，通常存在很多“块”，其中的地址位移都按相同的差值发生了变化；

由此可以想到，如果找出某个可执行程序的两个版本中那些对应源码没有改动的区域，对这些区域按字节计算差值（bytewise differences），其结果应该会存在很多0（因为内容相同），即使不为0也经常会出现高频重复值。换句话说，这些差值结果具有很高的可压缩性（highly compressible）。

源码解析

patchfile format

这部分在bspatch.c中有较详细的注释：

/*
File format:
	0	8	"BSDIFF40"
	8	8	X
	16	8	Y
	24	8	sizeof(newfile)
	32	X	bzip2(control block)
	32+X	Y	bzip2(diff block)
	32+X+Y	???	bzip2(extra block)
with control block a set of triples (x,y,z) meaning "add x bytes
from oldfile to x bytes from the diff block; copy y bytes from the
extra block; seek forwards in oldfile by z bytes".
*/

依次为：

  • 文件格式签名，8字节常量"BSDIFF40"；
  • control block压缩流的长度（X），8字节整数；
  • diff block压缩流的长度（Y），8字节整数；
  • newfile的长度，8字节整数；
  • control block压缩流，长度为X字节；
  • diff block压缩流，长度为Y字节；
  • extra block压缩流；

其中的control block是一个数组，其每个元素为3个8字节整数所组成的三元组（x, y, z）。对这个三元组各部分的注释，直接的描述了bspatch主循环中每次所执行的逻辑：

  1. 从diff block和oldfile的当前位置分别读取x个字节，按字节分别相加，结果写入到newfile；
  2. 从extra block读取y个字节（y可能为0），直接写入到newfile；
  3. 调整oldfile的当前位置，增加z个字节；注意z可能为负数；

上述的8字节整数，采用的是原码表示（sign–magnitude3）以及大端模式（big-endian4）存储，bspatch.c中的offtin函数和bsdiff.c中的offtout函数用于处理它与host中off_t类型的互转。

此外，control block, diff block和extra block都使用bzip5算法进行了压缩。这些压缩是patch文件实际尺寸会减小的原因，而算法本身只是负责构建出这些具有高压缩性的数据。

bspatch

搞懂了patchfile的格式以后，bspatch的逻辑就很容易理解了：

  • 打开patchfile，校验文件头，从对应位置打开3个bzip文件句柄，分别用于读取control block, diff block和extra block；
  • 打开oldfile，将其完整内容读取到内存中；
  • 从patchfile中取得newfile的长度newsize，分配出对应长度的内存缓冲区newfile；
  • 设置两个变量oldpos和newpos，分别表示oldfile和newfile中当前读/写的位置。进入主循环：
    • 从control block中读取1个控制三元组（x, y, z）；
    • 从diff block中读取x个字节，写入到newfile中newpos开始的位置，再将每个字节依次加上oldfile中oldpos开始的对应字节；oldpos+=x && newpos+=x；
    • 从extra block中读取y个字节，写入到newfile中newpos开始的位置；newpos+=y；
    • oldpos+=z；
    • 当newpos>=newsize时退出循环；
  • 至此，newfile的内容已经重建完毕，将其写入到文件；

bsdiff

现在我们已经知道，patch文件中包含了3个子文件control block, diff block和extra block，对后两者的使用由control block中的一系列ctrl三元组数据来控制。具体到某一个ctrl三元组来说，它可能包括一个diff区段和一个extra区段。diff区段通过和oldfile中的内容相加后还原newfile，这是前述原理中求差值操作的逆运算，因此对应的是一个“与源码修改无直接对应关系的区域”。而extra区段被直接写入newfile，因此对应的是“存在源码修改的区域”。extra区段不一定存在，两者相连且先后顺序固定。

因此，bsdiff算法的核心，就是对newfile从前向后尝试，在oldfile中搜寻一个和newfile当前位置开始的内容近似匹配（approximate matches）的对应区段，这个近似匹配中包含一段“与源码修改无直接关系的区域”，可能再跟着一段“存在源码修改的区域”。基于这个对应区段构建一组ctrl以及相关联的diff和extra数据。持续此过程直至newfile文件结束，然后将所得的control block, diff block和extra block按前述文件格式生成patch文件。

接下来我们实际看下bsdiff.c的流程。

◈ 首先是判断输入参数是否合法。程序需要3个参数，argv[1], argv[2]和argv[3]分别对应oldfile, newfile和patchfile的文件路径。

	if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);

◈ 打开oldfile，分配对应大小的buffer，将文件内容读取到内存buffer中。之所以要malloc(oldsize+1)是因为oldsize可能为0，与之相对的newsize也可能为0。

	/* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
		that we never try to malloc(0) and get a NULL pointer */
	if(((fd=open(argv[1],O_RDONLY,0))<0) ||
		((oldsize=lseek(fd,0,SEEK_END))==-1) ||
		((old=malloc(oldsize+1))==NULL) ||
		(lseek(fd,0,SEEK_SET)!=0) ||
		(read(fd,old,oldsize)!=oldsize) ||
		(close(fd)==-1)) err(1,"%s",argv[1]);

◈ 基于oldfile的内容构建一个后缀数组（suffix array6），用于后面在oldfile中快速搜索与newfile中内容匹配的区域。bsdiff使用qsufsort来进行后缀排序，这个算法需要用到两个额外数组I和V，其中I用于保存结果后缀数组，V为辅助空间，执行完就可以释放。

可以不去理解qsufsort函数（及其辅助函数split）的内部实现。首先把它当成黑盒不影响对bsdiff流程的理解，只要你知道suffix array是什么东西；其次qsufsort在今天看起来并不是一个很好的后缀排序实现，可以考虑将它替换成其它更优的库。

需要关注的点是这块的内存占用。off_t在32位环境下一般typedef为int，占用4字节。设oldfile的size为n，则I和V这两个数组会占用8n的内存空间，再加上之前已经加载到内存的一份oldfile，我们的峰值内存需求已经达到了9n！如果要考虑64位就更加恐怖了。

	if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
		((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);

	qsufsort(I,V,old,oldsize);

	free(V);

◈ 将newfile读取到内存中：

	/* Allocate newsize+1 bytes instead of newsize bytes to ensure
		that we never try to malloc(0) and get a NULL pointer */
	if(((fd=open(argv[2],O_RDONLY,0))<0) ||
		((newsize=lseek(fd,0,SEEK_END))==-1) ||
		((new=malloc(newsize+1))==NULL) ||
		(lseek(fd,0,SEEK_SET)!=0) ||
		(read(fd,new,newsize)!=newsize) ||
		(close(fd)==-1)) err(1,"%s",argv[2]);

◈ 为db和eb这两个buffer分配内存。这两个buffer对应的是子文件diff block和extra block，其最大长度不会超过newsize（因为它们对应到newfile的某些部分）。它们的内容会在后面的步骤中逐渐写入，dblen和eblen用于描述它们当前有效数据的长度。

	if(((db=malloc(newsize+1))==NULL) ||
		((eb=malloc(newsize+1))==NULL)) err(1,NULL);
	dblen=0;
	eblen=0;

◈ 创建patchfile，写入一个用来占位的文件头，其内容在主循环走完以后还会再更新。

	/* Create the patch file */
	if ((pf = fopen(argv[3], "w")) == NULL)
		err(1, "%s", argv[3]);

	memcpy(header,"BSDIFF40",8);
	offtout(0, header + 8);
	offtout(0, header + 16);
	offtout(newsize, header + 24);
	if (fwrite(header, 32, 1, pf) != 1)
		err(1, "fwrite(%s)", argv[3]);

◈ pf的当前file position为32，此时基于pf创建一个bzip文件句柄（因此结果bzip压缩流会写入在32字节偏移开始的区域），用于control block的写入：

	/* Compute the differences, writing ctrl as we go */
	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);

◈ 接下来是主循环了，这部分逻辑较为复杂，我们先将它进行简化，整理出结构。

	scan=0;len=0;
	// lastscan是当前“候选”匹配区域在new中的开始位置；
	// lastpos 是当前“候选”匹配区域在old中的开始位置；
	// lastoffset是当前“候选”匹配区域中old中位置相对于new中对应位置的差值，
	//   因此<new_pos>+lastoffset=<old_pos>；
	lastscan=0;lastpos=0;lastoffset=0;
	// 循环处理整个newfile
	while(scan<newsize) {
		oldscore=0;

		// 从scan开始向后搜索，符合某种条件时跳出循环；
		for(scsc=scan+=len;scan<newsize;scan++) {
			...
		};

		// len!=oldscore说明当前“候选”匹配区域不需要再继续向后搜索了；
		// scan==newsize说明已经已到达文件尾；
		// 符合这两个条件之一时，我们开始处理当前这个近似匹配区域；
		if((len!=oldscore) || (scan==newsize)) {
			// 确定lenf的长度。区域[lastscan, lastscan+lenf)被称为forward extension
			s=0;Sf=0;lenf=0;
			for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
				...
			};

			// 确定lenb的长度。区域[scan-lenb, scan)被称为backward extension
			lenb=0;
			if(scan<newsize) {
				s=0;Sb=0;
				for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
					...
				};
			};

			if(lastscan+lenf>scan-lenb) {
				// forword extension和backward extension区域出现重叠时需要调整lenf和lenb
				...
			};

			// forward extension即为diff区段，减去old中对应位置的值，结果写到db中
			for(i=0;i<lenf;i++)
				db[dblen+i]=new[lastscan+i]-old[lastpos+i];
			// forward extension和backward extension若不相连，两者中间的区域
			// 即为extra区段，其内容直接复制到eb中
			for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
				eb[eblen+i]=new[lastscan+lenf+i];

			dblen+=lenf;
			eblen+=(scan-lenb)-(lastscan+lenf);

			// 写入三元组的x
			offtout(lenf,buf);
			...
			// 写入三元组的y
			offtout((scan-lenb)-(lastscan+lenf),buf);
			...
			// 写入三元组的z
			offtout((pos-lenb)-(lastpos+lenf),buf);
			...

			// backward extension会被作为下一轮“候选”匹配区域的开始部分，
			// 也就是变成下一次的forward extension的一部分
			lastscan=scan-lenb;
			lastpos=pos-lenb;
			lastoffset=pos-scan;
		};
	};

细看下确定scan, len和oldscore的逻辑：

		// 当前“候选”匹配区域为：new[lastscan, scan) <-> old[lastpos, scan+lastoffset)

		// 重置oldscore
		oldscore=0;

		// 注意scan值变动的方式：进入循环时(+=len)，之后每执行完一次时(++)；
		for(scsc=scan+=len;scan<newsize;scan++) {
			// 这里对new中scan处开始的内容，在old中搜索一个完全匹配区域。
			// len返回完全匹配区域的长度，pos为old中与scan所对应的位置。
			// search函数是一个标准的二分查找算法，I是前面构建出来的后缀数组。
			len=search(I,old,oldsize,new+scan,newsize-scan,
					0,oldsize,&pos);

			// 上一步的搜索，得到了“候选”匹配区域new的向后延伸，在old中完全匹配区域的开始位置和长度，
			//   但这个开始位置和“候选”匹配区域中old的结束位置有可能并不相连。

			// 统计new中[scan, scan+len)与old中“候选”匹配区域的对应延伸区段中相等的字节数，
			// 累加到oldscore中。注意循环变量是scsc，因此不会重复累加。
			for(;scsc<scan+len;scsc++)
			if((scsc+lastoffset<oldsize) &&
				(old[scsc+lastoffset] == new[scsc]))
				oldscore++;

			// (len==oldscore) && (len!=0) 说明当前“候选”区域的延伸区域仍然匹配的很好，
			//   那么可以扩展“候选”匹配区域，并继续向后搜索；
			// (len>oldscore+8) 说明延伸区域中至少有8个以上的字节是不匹配的，
			//   那么当前“候选”区域应该到此截止而不扩展；
			if(((len==oldscore) && (len!=0)) || 
				(len>oldscore+8)) break;

			// 走到这里说明当前不相等的字节数没有大于8，需要继续循环。
			// 由于下次循环是从scan+1的位置上尝试，因此若scan对应的字节是相等的，
			// 它已经被计算在oldscore之内的值需要被减掉。
			if((scan+lastoffset<oldsize) &&
				(old[scan+lastoffset] == new[scan]))
				oldscore--;
		};

再看一下确定lenf长度部分的逻辑，后面的lenb，以及lenf和lenb重叠时的处理，逻辑类似：

			s=0;Sf=0;lenf=0;
			// 从lastscan开始向后搜索，上界为scan
			for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
				// s记录对应字节相等的次数
				if(old[lastpos+i]==new[lastscan+i]) s++;
				i++;
				// Sf保存着lenf更新时对应的s，两者的初始值均为0，因此这个判断最开始
				// 相当于if(s*2-i>0)，也就是是否有50%以上的i对应的字节是相同的。
				// 在lenf更新过1次以后，这个判断相当于比较当前相同比率是否比前一次候选
				// lenf所对应的相同比率更高。
				if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
			};

简单总结：

  1. 从一个空的“候选”匹配区域开始，基于new持续向后探查。当(a)探查到文件尾，或者(b)当前探查位置在old中存在一个长度为len的完全匹配，并且当前“候选”匹配区域向后扩展len字节的区域中存在大于8个字节的不匹配时，结束当前“候选”的探查并进行这一“近似匹配区段”的数据输出。否则就扩展当前“候选”区域并继续探查。
  2. 输出某一处“近似匹配区域”时，从区域的开始处向后找一个长度lenf，以及从区域的结束位置向前找一个长度lenb。lenf和lenb的判断标准都是看对应字节相同的比率是否达到50%。当lenf区段和lenb区段重叠时，在重叠区域中搜寻一个位置，使得此“近似匹配区域”的字节相同个数最大化，以此作为lenf区域和lenb区域的边界。
  3. lenf对应的内容会按diff block子文件来处理（计算差值后写入）；lenf和lenb若不相连，其中间的区域会按extra block子文件来处理（直接写入）；lenb对应的内容则会作为下一次“候选”匹配区域的开始部分。

◈ 最后的收尾部分注释较多，逻辑也比较直白：

  • 写完control block压缩流；
  • 将db的内容写入一个新的bzip压缩流，也就是diff block子文件；
  • 将eb的内容写入一个新的bzip压缩流，也就是extra block子文件；
  • 更新文件头中两个子文件长度X和Y（之前仅仅做了占位）；

可能需要改进的点

首先是内存占用需求较高（设oldfile的size为n，newfile的size为m）：

  1. patch流程的内存需求为n+m+O(1)。因为patch流程通常在客户端运行，内存资源受限的可能性比较大。
  2. diff流程的内存需求在32位时为max(9n,5n+3m)+O(1)，前面的9n对应后缀数组构建的阶段，后面的5n+3m对应扫描阶段。以250MB左右的文件为例，9n为2250MB，这已经超过了很多32位操作系统中用户态程序的可用地址空间（例如Windows通常为2GB）。

其次是运行性能。qsufsort的性能比较一般，可以考虑用更好的后缀排序库来代替（例如libdivsufsort7）。bzip2以今天的眼光看在压缩率、性能上也算不上优秀，可以考虑更换压缩算法和压缩库。整体代码对性能优化考虑较少，存在很多不必要的seek动作和小数据量的IO动作。

最后还存在一些安全性漏洞，例如CVE-2014-98628。

感兴趣的同学可以看下这个仓库，针对上述问题做了一些改进：bsdiff

References

  1. https://en.wikipedia.org/wiki/Delta_encoding ↩︎

  2. https://source.android.com/devices/tech/ota/reduce_size ↩︎

  3. https://en.wikipedia.org/wiki/Signed_number_representations#Sign-and-magnitude_method ↩︎

  4. https://betterexplained.com/articles/understanding-big-and-little-endian-byte-order/ ↩︎

  5. https://www.sourceware.org/bzip2/ ↩︎

  6. https://en.wikipedia.org/wiki/Suffix_array ↩︎

  7. https://github.com/y-256/libdivsufsort ↩︎

  8. https://security-tracker.debian.org/tracker/CVE-2014-9862 ↩︎