Google Chrome Courgette differential compression algorithm

http://dev.chromium.org/developers/design-documents/software-updates-courgette

by dajobe • 15 years ago

71 21 15 years ago

dev.chromium.org

Courgette uses a primitive object disassembler adjuster to compute "assembly language" differences that are about 10% size of bsdiff.

codabrink2• 15 years ago

This is exactly how updates should be done. Usually, I'm not that big of a fan of things that Google does, but this is a great achievement. Hats off to those who contributed to this. I hope all update systems eventually work this way.

LukeShu• 15 years ago

Well, most binary updates do go through bsdiff, which was designed for exactly this. I'm surprised they were able to beat it by such a margin. Shit, the guy who made bsdiff did his doctoral thesis on the subject (actually, the algorithm used in bsdiff generates patches about 25% larger than the one in the thesis, but at huge performance increase (or, the thesis generates patches 20% smaller)).

codabrink2• 15 years ago

Really, I wasn't aware that that many projects used bsdiff.

akronim• 15 years ago

I think Google could handle spending a bit of extra time on a single diff, in order to save 25% of their update bandwidth. Maybe they should just implement the thesis.

cperciva3• 15 years ago

I'm surprised they were able to beat it by such a margin.

Technology marches on. I have ideas for improving bsdiff, too.

joezydeco2• 15 years ago

Call me stupid, but why do you have to disassemble the program to get the symbol pointers when you just finished compiling the thing in the first place?

Couldn't this intermediate step of pointer collection be part of the prelink process and skip all this guesswork?

InclinedPlane• 15 years ago

Sadly, most compilers are not modular so it's generally easier to add a post-compilation step than to add an intermediate compilation step.

barrkel• 15 years ago

If the source is in a single language, compiled by a single tool, with one single version, and entirely linked by a single linker strictly at the end of the process, then that might be feasible. But that's probably not the case. If there is much heterogeneity at all, getting proper symbol information may be a lot more work than analysing the binary for control and data flow. For example, intermediate linking steps may resolve symbol fixups internally and just leave a list of relocations behind, or perhaps use strictly relative addresses within what looks to the final linker like a monolithic blob.

joezydeco2• 15 years ago

If we're talking about a way to generate an upgrade image for a single architecture, taking a known version # of an executable to another known version #, built on a production build machine, I would think that could cover the case easily.

That kind of led to my second question: this makes really small images, but only from one known version to another, right? What happens if the target to be upgraded is 80 revisions behind?

stcredzero2• 15 years ago

We want smaller updates because it narrows the window of vulnerability. If the update is a tenth of the size, we can push ten times as many per unit of bandwidth. We have enough users that this means more users will be protected earlier.

They're trying to get the vulnerability window down to minutes! If they succeed, this is going to have an impact on the economic viability of running malware.

seiji• 15 years ago

We're also giving google implicit permission to push code to our machines anytime they want.

We should have conflicting feelings about this.

stcredzero2• 15 years ago

We're also giving google implicit permission to push code to our machines anytime they want.

We should have conflicting feelings about this

You have a point. But I think the answer to that is in the market.

Through Chrome, the browser is evolving into a new kind of platform. It will be a platform that encompasses locally execution and memory and all of the flexibility and availability of the cloud, and it will all just work.

There are sure to be competitors. If one competitor fails, we can always take our business elsewhere. We only have to worry if the government legislates us out of a means for oversight.

spatulon• 15 years ago

The last I heard, Google were being sued due to the use of Courgette allegedly infringing a patent and, as a result, they had stopped using Courgette to distribute Chrome updates. Does anyone know the result of that case? Are they now using Courgette again?

http://news.softpedia.com/news/Google-Sued-over-the-Courgett...

dajobe• 15 years ago

Looks like it is still ongoing: http://dockets.justia.com/docket/massachusetts/madce/1:2009c... reports news from Nov 2010. Can't decode the legal language.

cperciva3• 15 years ago

Red Bend's attempt at a preliminary injunction was quashed recently, with the court stating that "with insufficient evidence that Courgette infringes on at least one patent claim, Red Bend cannot prove a likelyhood of success",

I'm no lawyer, but this sounds pretty bad for Red Bend.

Google Chrome Courgette differential compression algorithm

Related Stories