Chrome的小胡瓜(Courgette) 收藏

轉(zhuǎn)自http://blog.csdn.net/xingtian713/archive/2009/08/25/4483810.aspx


在Chrome中有一個很有意思的工具courgette，翻譯成中文是小胡瓜的意思。我很難把這個單詞和這個小工具聯(lián)系在一起，也許作者比較偏愛這個蔬菜吧！

背景
我們用C++編寫程序時，經(jīng)常會出現(xiàn)修改了一行代碼，重新編譯一下之后，再去對比一下新的二進(jìn)制文件，就可以發(fā)現(xiàn)千差萬別了。往往出現(xiàn)我們要發(fā)布一個修改了一行代碼的補(bǔ)丁，需要替換整個DLL或者EXE。這對于Chrome中類似于Chrome.dll（10M左右）文件來說，升級一次的代價還是挺高的。本人在去年下半年負(fù)責(zé)的一個升級服務(wù)器項目中，就曾動過念頭，是否有一種方法可以尋找出兩個二進(jìn)制文件的差異，將這個差異打成一個補(bǔ)丁，用戶下載后，可以通過這個補(bǔ)丁，可以自動生成新的DLL。可惜功力不夠，最后放棄了。最近讀Chrome的代碼時，發(fā)現(xiàn)Chrome已經(jīng)實現(xiàn)了該功能。這個就是Courgette的功勞了。

Courgette做什么的？
Courgette主要用于Chrome的升級過程，他的主要作用是，針對兩個版本不同的二進(jìn)制文件(Binary File)，尋找其中區(qū)別，生成補(bǔ)丁文件；另外就是根據(jù)這個補(bǔ)丁文件加上舊版本的二進(jìn)制文件生成新版本的二進(jìn)制文件的還原過程了。類似于加解密流程。

Courgette的實現(xiàn)原理？
Courgette構(gòu)建在一個開源代碼bsdiff和bspatch 基礎(chǔ)上的。并在bsdiff的基礎(chǔ)上做了一些優(yōu)化。

本人是半路出家的人，對編譯原理和匯編了解不深，按照我對bsdiff的算法 理解，一個二進(jìn)制文件里面，包含了代碼部分（函數(shù)，數(shù)據(jù)），指向這些函數(shù)的指針列表（編譯鏈接產(chǎn)生，包含了如何定位函數(shù)等信息），由于這些地址是內(nèi)部的相對地址，即使更改了一小行代碼，重新編譯后，函數(shù)的地址將發(fā)生變化了，指向這些函數(shù)的指針值也全部變化了。因此，即使更改了一個小小的變量，也會導(dǎo)致很多部分的修改。bsdiff的原理就是對二進(jìn)制文件進(jìn)行反匯編，將上面所說的兩部分進(jìn)行分別處理，對于代碼部分，其實就和普通的文本文件類似了，改變不會太大，這部分體積基本上占去了整個二進(jìn)制文件的80%左右。然后對動態(tài)指針部分進(jìn)行一些更新處理，就基本上達(dá)到了打補(bǔ)丁的目標(biāo)了。

    server:

        diff = bsdiff(original, update)

        transmit diff


    client:

        receive diff

        update = bspatch(original, diff)
大致流程如上，制作補(bǔ)丁時調(diào)用bsdiff函數(shù)，根據(jù)兩個不同版本的二進(jìn)制文件，生成補(bǔ)丁文件?？蛻舳讼螺d補(bǔ)丁后，調(diào)用bspatch函數(shù)，根據(jù)舊版本二進(jìn)制文件和補(bǔ)丁生成新的二進(jìn)制文件。

Chrome在bsdiff的基礎(chǔ)上做了一些優(yōu)化，主要體現(xiàn)在動態(tài)指針列表部分，chrome對代碼部分的每一個模塊地址分配了一個標(biāo)簽（Label），這些標(biāo)簽都是整數(shù)，并把這些標(biāo)簽保存到一個數(shù)組中，然后指針列表中映射的地址改為指向數(shù)組的索引，由于一些函數(shù)地址被調(diào)用多次，通過這種方法確實可以減少一些體積。做了一些優(yōu)化后，在bsdiff的基礎(chǔ)上又減少了30%左右吧（這是google的說法，我沒驗證過）。
    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)
Chrome的大致處理流程如上，和bsdiff流程類似，多了 asm_new_adjusted = adjust(asm_new, asm_old)這一個步驟，這個步驟主要就是上面說的對地址標(biāo)簽化的過程。