chenxiaolong/Custota

Feature request: Incremental updates support

archandanime opened this issue · 3 comments

archandanime commented

Hi, I've found ota_from_target_files tool (from otatools.zip bundle) from Google that allows to generate incremental OTA from 2 OTA zip files and it looks really promising. Would you mind taking a look?
If this is outside of avroot's scope, does Custota support installing incremental OTA from a manually generated incremental OTA zip?

chenxiaolong commented

ota_from_target_files.py (delta_generator behind the scenes) is a nice tool, but it's pretty tailored to how AOSP does things. It operates on two "target files" zips, not OTA zips. This is what a target files zip looks like: https://gist.github.com/chenxiaolong/fa7db944325cc919c317e43d11fc549e.

I haven't not taken a really close look at the code, but I think these are the subset of files that delta_generator cares about. It's theoretically possible to generate them from a full OTA.

  • IMAGES/*.img (Android partition images) and RADIO/*.img (bootloader, modem, and other firmware images)
    • Can be extracted from payload.bin from the full OTA.
    • Everything could just go inside IMAGES/. The code doesn't distinguish between the two folders.
  • META/apex_info.pb
    • Only needed from the target OTA. Easily unzipped--just a regular file.
  • META/dynamic_partitions_info.txt (example)
    • Should be possible to partially generate from the DynamicPartitionMetadata fields inside payload.bin's header. Some fields will be missing, but delta_generator doesn't look at those.
  • META/postinstall_config.txt (example)
    • Should be possible to fully generate from the PartitionUpdate fields inside payload.bin's header.

Once a "target files" zip is created, running ota_from_target_files would hopefully just work. It would take care of the signing step too.

The biggest downside is that none of this stuff can be built outside of AOSP. You'd have to download AOSP to be able to compile delta_generator (a C++ project). Looking at my GrapheneOS folder, this would probably be around 200 GiB...

As far as doing a custom implementation in avbroot, I most likely won't do that. The way the deltas are computed is pretty complex.

Inside payload.bin, the deltas are stored as bsdiff patches, but just running the regular bsdiff command isn't enough. I played around with the Pixel 7 Pro's product.img a bit:

  • Computing a diff between the old and new product.img requires ~50 GiB of RAM. bsdiff requires RAM at least 17 times the size of the old file. I'm not sure how big the resulting delta is--I gave up waiting after a few hours.
  • If the partition is split up into small chunks (eg. 2 MiB), then the resulting delta is nearly the same size as the full OTA. This is because even if a file (eg. app/Camera/Camera.apk) doesn't change, it is likely to be located in a different block/sector on the old and new partition images, so the vast majority of the chunks will have differences. My test run (2.9 GiB product.img from the Pixel 7 Pro July and August updates, split into 2 MiB chunks) took 40 minutes to generate a 1.5 GiB delta.

AOSP's delta_generator works around this by looking at individual files instead of the whole partition image. It does this by including (well, hackily integrating 🙂) parsers for ext4 and erofs. This way, it can tell if eg. bin/sh moved from block 1000 to 1007 without the contents changing. In this scenario, it just stores a move existing block at 1000 to 1007 operation inside payload.bin. No need to (slowly) compute a delta at all.

Implementing something like that would be too difficult for me to do, unfortunately. And without that kind of optimization, it's not worth generating a delta at all.

does Custota support installing incremental OTA from a manually generated incremental OTA zip?

It doesn't, but it's designed in a way that would make it very easy to add in the future. The only thing missing is the code for generating and reading the appropriate fields inside the <device>.json file. The actual installation process for a delta and full OTA are identical.

archandanime commented

That seems a lot of work and resources for individuals to implement. Thank you for very detailed explanation!

  • 👍1
chenxiaolong commented

In case you have the time and resources to compile AOSP, I made a proof of concept tool that uses delta_generator (same tool as what ota_from_target_files.py uses): https://github.com/chenxiaolong/avbroot-inc-ota

It takes two full OTAs and generates an incremental OTA. The payload.bin generation is handled by delta_generator and the signing and zip creation is done by avbroot. Tested on my Pixel 7 Pro 🙂

  • 👀1