[dm-devel] [PATCH] announcing the dm-update target

[Kelvin Zhang]

There are two different formats in Android's OTA infrastructure:

1. The OTA format. This is what we generate from two android images, and
this is what Android devices download when installing an update.
    This format is designed to be as small as possible. Therefore it is not
suitable to serve as an on disk COW format, as disk read performance would
be horrible.
2. The COW format. After the device downloads the OTA package, it will
translate OTA format into COW format. The COW format has larger disk space
footprint,
    but much better disk read performance.

Unfortunately you can't get example COW images easily. As we don't [yet]
have tools to create them on host. The only way to get a COW image is to
apply OTA on device and read data from the android device.

Below are some instructions on how to produce android OTA packages(format
#1)

Android's OTA generator is open source at
https://cs.android.com/android/platform/superproject/+/master:system/update_engine/payload_generator/generate_delta_main.cc?q=generate_delta_main

We have precompiled OTA generator binaries available at
https://ci.android.com/ . To download:
1. Look for column "aosp_cf_x86_64_phone"
2. Click on any green squares
3. Click on "artifacts" tab e.g.
https://ci.android.com/builds/submitted/7945102/aosp_cf_x86_64_phone-userdebug/latest
4. Look for otatools.zip , download it

The same https://ci.android.com/ website also has android images available
for download. To fetch an android image:

1. Look for column "aosp_cf_x86_64_phone"
2. Click on any green squares
3. Click on "artifacts" tab
4. Look for "target_files" e.g.
aosp_cf_x86_64_phone-target_files-7945102.zip . Note, this name will be
different for each build.

To generate an incremental OTA package:

1. Extract otatools.zip, add bin/ subdir to your PATH, add lib/lib64 subdir
to LD_LIBRARY_PATH
2. ota_from_target_files -v -i source_build_target_files.zip
target_build_target_files.zip ota.zip


> How do you search for blocks that are similar, so that the "XOR" method is
> benefical for them?

In short, we use BSDIFF. The core algorithm is explained in
https://www.daemonology.net/papers/bsdiff.pdf . It uses suffix array + some
heuristics to identify similar blocks.

> How do you make sure that you don't perform the "XOR"
> operation twice, if there's system crash when performing it?

That's handled by snapuserd. Akilesh can show you all the details. But
basically:

1. We compute an order which COW operation should be applied, and this
order is guaranteed to be conflict free(an operation earlier in the order
will never overwrite blocks needed by a later operation).
2. The snapuserd has to write checkpoint data to disk so it can properly
resume.

On Wed, Nov 24, 2021 at 3:44 PM Akilesh Kailash <akailash at google.com> wrote:

> On Wed, Nov 24, 2021 at 8:10 AM Mikulas Patocka <mpatocka at redhat.com>
> wrote:
> >
> >
> >
> > On Tue, 23 Nov 2021, David Anderson wrote:
> >
> > > In our ecosystem, the OTA generation and on-device application process
> > > has evolved continually, in every release, for over 10 years now. So
> > > we think it's unlikely that we'll stop making improvements to it. Our
> > > current roadmap has other changes in the pipeline too. It's not just
> > > us trying to eek out diminishing returns. Other parts of the system
> > > change around us, and the OTA system needs to adapt.
> > >
> > > The performance penalty is something we've been working on, and have
> > > improved a lot since our first iteration. We're currently
> > > experimenting with io_uring as well.
> > >
> > > Best,
> > >
> > > -David
> >
> > Hi
> >
> > I understand that an update format developed over 10 years will have
> > better compression ratio than my format developed in 2 months.
> >
> > I'd be interested in extending dm-update to handle your your update
> format
> > and possibly add some abstraction, so that it can work with multiple
> > formats.
> >
> > You say that you have "COPY" and "XOR" operations.
> >
> > How do you search for blocks that are similar, so that the "XOR" method
> is
> > benefical for them? How do you make sure that you don't perform the "XOR"
> > operation twice, if there's system crash when performing it?
>
> CC: Kelvin and Tianjie who are familiar with the  OTA generation.
>
> > Could it be possible for you to give us two Android images and a program
> > that calculates difference between them? So that we could see how well we
> > are performing compared to the existing solution.
> >
> > Mikulas
> >
>


-- 
Sincerely,

Kelvin Zhang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listman.redhat.com/archives/dm-devel/attachments/20211124/93dce96c/attachment.htm>