<div dir="ltr"><div>There are two different formats in Android's OTA infrastructure:</div><div><br></div><div>1. The OTA format. This is what we generate from two android images, and this is what Android devices download when installing an update.</div><div> 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.</div><div>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,</div><div> but much better disk read performance.</div><div><br></div><div>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.</div><div><br></div><div>Below are some instructions on how to produce android OTA packages(format #1)</div><div><br></div>Android's OTA generator is open source at <a href="https://cs.android.com/android/platform/superproject/+/master:system/update_engine/payload_generator/generate_delta_main.cc?q=generate_delta_main">https://cs.android.com/android/platform/superproject/+/master:system/update_engine/payload_generator/generate_delta_main.cc?q=generate_delta_main</a><div><br></div><div>We have precompiled OTA generator binaries available at <a href="https://ci.android.com/">https://ci.android.com/</a> . To download:</div><div>1. Look for column "aosp_cf_x86_64_phone"</div><div>2. Click on any green squares</div><div>3. Click on "artifacts" tab e.g. <a href="https://ci.android.com/builds/submitted/7945102/aosp_cf_x86_64_phone-userdebug/latest">https://ci.android.com/builds/submitted/7945102/aosp_cf_x86_64_phone-userdebug/latest</a></div><div>4. Look for otatools.zip , download it</div><div><br></div><div>The same <a href="https://ci.android.com/">https://ci.android.com/</a> website also has android images available for download. To fetch an android image:</div><div><br></div><div>1. Look for column "aosp_cf_x86_64_phone"</div><div>2. Click on any green squares</div><div>3. Click on "artifacts" tab</div><div>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.</div><div><br></div><div>To generate an incremental OTA package:</div><div><br></div><div>1. Extract otatools.zip, add bin/ subdir to your PATH, add lib/lib64 subdir to LD_LIBRARY_PATH</div><div>2. ota_from_target_files -v -i source_build_target_files.zip target_build_target_files.zip ota.zip<br><div><br></div></div><div><br></div><div>> How do you search for blocks that are similar, so that the "XOR" method is<br>> benefical for them? <br></div><div><br></div><div>In short, we use BSDIFF. The core algorithm is explained in <a href="https://www.daemonology.net/papers/bsdiff.pdf">https://www.daemonology.net/papers/bsdiff.pdf</a> . It uses suffix array + some heuristics to identify similar blocks.</div><div><br></div><div>> How do you make sure that you don't perform the "XOR"</div>> operation twice, if there's system crash when performing it?<div><br></div><div>That's handled by snapuserd. Akilesh can show you all the details. But basically:</div><div><br></div><div>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).</div><div>2. The snapuserd has to write checkpoint data to disk so it can properly resume.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Nov 24, 2021 at 3:44 PM Akilesh Kailash <<a href="mailto:akailash@google.com">akailash@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Wed, Nov 24, 2021 at 8:10 AM Mikulas Patocka <<a href="mailto:mpatocka@redhat.com" target="_blank">mpatocka@redhat.com</a>> wrote:<br>
><br>
><br>
><br>
> On Tue, 23 Nov 2021, David Anderson wrote:<br>
><br>
> > In our ecosystem, the OTA generation and on-device application process<br>
> > has evolved continually, in every release, for over 10 years now. So<br>
> > we think it's unlikely that we'll stop making improvements to it. Our<br>
> > current roadmap has other changes in the pipeline too. It's not just<br>
> > us trying to eek out diminishing returns. Other parts of the system<br>
> > change around us, and the OTA system needs to adapt.<br>
> ><br>
> > The performance penalty is something we've been working on, and have<br>
> > improved a lot since our first iteration. We're currently<br>
> > experimenting with io_uring as well.<br>
> ><br>
> > Best,<br>
> ><br>
> > -David<br>
><br>
> Hi<br>
><br>
> I understand that an update format developed over 10 years will have<br>
> better compression ratio than my format developed in 2 months.<br>
><br>
> I'd be interested in extending dm-update to handle your your update format<br>
> and possibly add some abstraction, so that it can work with multiple<br>
> formats.<br>
><br>
> You say that you have "COPY" and "XOR" operations.<br>
><br>
> How do you search for blocks that are similar, so that the "XOR" method is<br>
> benefical for them? How do you make sure that you don't perform the "XOR"<br>
> operation twice, if there's system crash when performing it?<br>
<br>
CC: Kelvin and Tianjie who are familiar with the OTA generation.<br>
<br>
> Could it be possible for you to give us two Android images and a program<br>
> that calculates difference between them? So that we could see how well we<br>
> are performing compared to the existing solution.<br>
><br>
> Mikulas<br>
><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr">Sincerely,<div><br></div><div>Kelvin Zhang</div></div></div>