[Discussion] Depend on an pre-existing incremental OTA, and be inefficient ourselves.

[kitlith]

Core idea here is that it should be valid to be a little inefficient in an incremental OTA, and do things like always use REPLACE_* when embedding magisk, when a "real" update would be copying it from where it was previously located. So, given the source OTA, the target OTA, and an incremental OTA between the two, it should be possible to reuse (most of) the incremental OTA and not need to rerun delta_generator ourselves, instead choosing to do a 'dumb' bsdiff or similar on the small number of changes we actually need to make compared to stock. I'd hope the inefficiencies here are still a win over downloading full OTAs.

One thing that isn't clear to me yet is if there is a guaranteed order that the update operations run in, or if they're done in parallel/random order. If they are run sequentially (or as-if sequentially), though, I have a simple naive solution: return to stock, apply the stock incremental ota, and then re-root.

1. For each full OTA (partition), output the following lists of install operations:
   • stock_to_avbroot (i.e. a diff from the stock image to the rooted image)
   • avbroot_to_stock (ditto, but the opposite direction)
2. When patching the incremental OTA (partitions), replace the list of operations with the following:
   • avbroot_to_stock from the source full OTA
   • the operations from the incremental OTA
   • stock_to_avbroot from the target full OTA

A solution could be probably be made that still uses the above idea conceptually, but 'optimizes' it ahead of time to avoid writing to the same location twice, but the implementation would actually need to think about the semantics of each instruction, handle splitting them if necessary, etc.

... does a tool already exist for 'merging' or 'stacking' incremental OTAs? i.e. if you have an OTA for A->B and an OTA for B->C, is there a tool that lets you generate an OTA for A->C? because that would be exactly what I'm looking for implementation-wise, here. Such a tool wouldn't be useful for stock devices, though, since you wouldn't be able to generate a valid signature for the A->C update (even though the resulting partitions would be correct), so I'm guessing probably not.

Sorry for trailing off into a stream of thought, I'm still mulling this idea around in my head. I wouldn't be surprised if I've missed something that wrecks the whole idea, though.

[chenxiaolong]

This is a neat idea and I can't think of any reason offhand why it wouldn't work.

I don't personally use incremental OTAs, so avbroot-inc-ota is kind of a dead proof-of-concept project, but still happy to discuss!

One thing that isn't clear to me yet is if there is a guaranteed order that the update operations run in, or if they're done in parallel/random order. ... A solution could be probably be made that still uses the above idea conceptually, but 'optimizes' it ahead of time to avoid writing to the same location twice

There is no guaranteed order. On Virtual A/B devices, it's almost guaranteed that reordering will happen.

If I remember correctly, update_engine explicitly checks that there are no overlaps in install/merge operations so that an OTA won't be installed incorrectly.

... does a tool already exist for 'merging' or 'stacking' incremental OTAs? i.e. if you have an OTA for A->B and an OTA for B->C, is there a tool that lets you generate an OTA for A->C?

Because of the previous point, I don't think such a tool is possible unless the source and target extents used by all the incremental OTAs happened to be disjoint.

The full OTA for A would need to be available and you'd probably need to simulate an installation and generate the bsdiff operations for A->C afterwards.

handle splitting them if necessary

Yup. Generating stock_to_avbroot and avbroot_to_stock should be easy enough since both delta_generator and avbroot split at 2 MiB boundaries for the install operations. Merging avbroot_to_stock + stock incremental OTA + stock_to_avbroot could get a little ugly though.

[kitlith]

There is no guaranteed order. On Virtual A/B devices, it's almost guaranteed that reordering will happen.

If I remember correctly, update_engine explicitly checks that there are no overlaps in install/merge operations so that an OTA won't be installed incorrectly.

That only appears to re-order the CoW hint operations, and not the install operations themselves. The protobuf also calls out that Each operation is applied in order by the client. but I wouldn't want to rely on that before properly verifying it.

The real annoying thing is that the naive solution breaks down for operations reading the source partition. i.e., a SOURCECOPY from a location that we previously had magisk installed into. (particularly thinking of the boot partition here, since everything seems to be placed one-after-the-other without a filesystem). We could translate some operations into their deprecated non- SOURCE counterparts, but that doesn't cover all the newer operations that don't come with MOVE style counterparts.

The full OTA for A would need to be available and you'd probably need to simulate an installation and generate the bsdiff operations for A->C afterwards.

This, at least, feels like something we could do. Essentially, instead of rerunning delta_generator, we'd just 'regenerate' the blob for every install operation listed in the delta OTA between the two full OTAs. (or really, just the ones that would be affected by our patches, but let's not get too far ahead of ourselves.) We would still need to take into account that the original list of install operations wouldn't include our patches, but that only matters for blocks that only our patches touched, i think. This might still increase complexity if we're planning on being completely generic, because now we need to support applying and generating every type of install operation, even if we no longer need filesystem parsing/delta_generator, but that might be acceptable?

EDIT: In total, we'd be relying on having on hand:

• The source avbroot patched+signed full OTA (to avoid any potential reproducibility issues in re-creating it)
• The target unpatched full OTA (we'll be patching it as part of the process)
• The unpatched source->target incremental OTA.
• A means to unpatch the source image back to stock, so that we can verify that the incremental does indeed go between these two full OTAs.