feat: Make patch sizes smaller on iOS

[eseidel]

Currently patch sizes are often 10s of kb. Which is plenty small for many applications. However we're using a binary diffing algorithm which knows nothing about what it's diffing and could probably be another 10x smaller if it did.

[eseidel]

We should, yes. But we'll do this later as part of optimizing our costs.

[eseidel]

I looked into this briefly (for iOS) today. I had forgotten that we use ELF as a format for patch distribution, even on iOS. I believe that's the main reason the patches end up larger on iOS is we're diffing an ELF file against a MachO file. We could get around this by instead using our own custom format, which just contained the 4 dart blobs and did not bother to package in elf since we don't need any of the features of elf, just the 4 raw blobs which we load read-only anyways.

[eseidel]

I also looked at reducing the LinkTable size and found that moving from 64bit ints to 32bit ints had less savings than I was expecting?

64bit ints: LinkTable size: 196608 bytes

32bit ints: LinkTable size: 131072 bytes

Moving to LEB128: LinkTable size: 131072 bytes

I guess it's padding that's making these so even?

[eseidel]

LEB128 code:

diff --git a/pkg/aot_tools/lib/src/linker/linker.dart b/pkg/aot_tools/lib/src/linker/linker.dart
index 279d461bc2c..2307bc0fa3b 100644
--- a/pkg/aot_tools/lib/src/linker/linker.dart
+++ b/pkg/aot_tools/lib/src/linker/linker.dart
@@ -1,5 +1,3 @@
-import 'dart:typed_data';
-
 import 'package:aot_tools/src/linker/link_reporter.dart';
 import 'package:aot_tools/src/linker/shorebird_linker_overrides.dart';
 import 'package:aot_tools/src/snapshot_analysis.dart';
@@ -12,10 +10,51 @@ class ByteWriter {
   final bytes = <int>[];
 
   /// Write a 64-bit integer in little endian to the byte stream.
-  void addInt64(int value) {
-    /// Arm64 is little endian.
-    final byteData = ByteData(8)..setInt64(0, value, Endian.little);
-    bytes.addAll(byteData.buffer.asUint8List());
+  // TODO(eseidel): Use 32-bit integers or LEB-128 instead to save space.
+  // void addInt64(int value) {
+  //   assert(value >= 0 && value <= 0xFFFFFFFFFFFFFFFF, 'value: $value');
+
+  //   /// Arm64 is little endian.
+  //   final byteData = ByteData(8)..setInt64(0, value, Endian.little);
+  //   bytes.addAll(byteData.buffer.asUint8List());
+  // }
+
+  void _writeByte(int value) {
+    assert(value >= 0 && value <= 0xFF, value);
+    bytes.add(value);
+  }
+
+  /// Write one ULEB128 number.
+  void addInt64(int unsignedInt) {
+    // First bit in every byte is a signal if there is more data.
+    // So, we split the number into 7-bit parts and write them smaller to larger,
+    // prefixing with the signal.
+    var value = unsignedInt;
+    assert(value >= 0 && value <= 0xFFFFFFFFFFFFFFFF, 'value: $value');
+    var bytes = 0;
+    for (;;) {
+      var part = 0x7F & value;
+      value >>= 7;
+
+      if (value != 0) {
+        // Signal that there is more data.
+        part |= 0x80;
+      }
+      bytes++;
+      _writeByte(part);
+
+      if (value == 0) {
+        break;
+      }
+
+      if (value == -1) {
+        for (var i = 0; i < 9 - bytes; i++) {
+          _writeByte(0xFF);
+        }
+        _writeByte(1);
+        break;
+      }
+    }
   }
 }
 

[eseidel]

I think the next thing to test here is what the order of symbols between macho and elf are. If they're not in the same order, that's the easy thing to fix.

We could trivially make our own non-elf replacement format for patches, we would just want to make sure that the "symbol order" in the package matched the order in mach-o for maximum similarity?

[eseidel]

macho order:

0000000000004080 T _kDartVmSnapshotInstructions
0000000000011280 T _kDartIsolateSnapshotInstructions
00000000000c4880 S _kDartVmSnapshotData
00000000000cd8c0 S _kDartIsolateSnapshotData
00000000001a4000 b _kDartVmSnapshotBss
00000000001a4018 b _kDartIsolateSnapshotBss

elf order:

00000000000001c8 R _kDartSnapshotBuildId
0000000000000200 R _kDartVmSnapshotData
0000000000009240 R _kDartIsolateSnapshotData
00000000000e0000 T _kDartVmSnapshotInstructions
00000000000ed200 T _kDartIsolateSnapshotInstructions

[eseidel]

Yeah, so it looks like mach-o puts instructions before data and elf the opposite way around. That's presumably why the diffs end up extra large. I'm not sure how well zstd handles reordering sections within binary files.

[eseidel]

Another test we could do is to write a tiny tool that read in a mach-o snapshot and wrote out an elf snapshot and then ran patch against the two to see.

[eseidel]

OK, so I looked into this again this last weekend. Turns out we've already done most of the work. We just currently dump our patch in the ELF order, rather than the Mach-O order. zstd does not seem to be able to find similarities well enough with the sections out of order.

I believe the fix here is to add a new flag to analyze_snapshot to control the order in dump_blobs: https://github.com/shorebirdtech/dart-sdk/blob/shorebird/dev/runtime/bin/analyze_snapshot.cc#L196

We would also need to change the engine to return the "base" file in macho order: https://github.com/shorebirdtech/engine/blob/shorebird/dev/shell/common/shorebird/snapshots_data_handle.cc#L90

I've also written a reader for these patch files, but we don't actually need to land that I don't think: https://github.com/shorebirdtech/dart-sdk/pull/635

[eseidel]

The bulk of this change will be making the shorebird tool be able to handle the file format change across versions.

And of course verifying that this does shrink patch sizes. But I think there isn't a lot of technical heavy lifting left here, and this should be able to bring our average iOS patch size from 1M down to 100k or smaller.

We can (separately) bring down Android patch sizes, by having Android use our multi-pass compiler like iOS does, which makes a patch snapshot more similar to the release snapshot.

[eseidel]

I think the first thing to do here is to change the engine and analyze_snapshot segment order, test that it makes patch sizes smaller, and then go about making shorebird and aot_tools support backwards compatibility. Presumably by introducing a new argument to dump_blobs which controls order, and make dump_blobs assume the elf order (what it currently does) when not provided.

[eseidel]

This is probably a ~day of work for me and would be win for our customers, our customers' customers, and our own server costs.

[eseidel]

In case others are curious, I attempted to explain this bug in plain language to a customer today:

""" Imagine if you had pictures of an Alligator, Bear, Camel and Dog and combined them all into one file and then tried to update the picture of the alligator by sending down a diff between the Dog, Camel, Bear and Alligator (updated) also combined into a file. That's what we do. And so the diff algorithm gets confused and tries to make a difference between Dog <-> Alligator, Bear <->Camel, etc. instead of Alligator <-> Alligator, etc. And thus makes these huge diffs, unnecessarily. """

[eseidel]

Working on this again now. I attempted to change the dump order in dump_blobs and that didn't help.

However it appears dump_blobs is stripping so much from the binary that the patches have to re-include and that may be causing the oversized nature of ios patches.

Using a flutter and friends diff (currently 77% linking) as an example: --before=b236d272a719e4f171d69be0aa62aa68239611b2 --after=48bc3caa145969a073d74deae90d638201476072

% du -h release.aot
6.2M    release.aot
% du -h release.aot.blobs 
4.8M    release.aot.blobs

% file release.aot
release.aot: Mach-O 64-bit dynamically linked shared library arm64

[eseidel]

I'm very confused as to why dump_blobs would end up stripping 2.4mb out of that dump.

dump_blobs just reads out the dart blobs and dumps them. What would the other 2.4mb be? Maybe the way I'm compiling for my test case is including symbols or something that it shouldn't and that's the problem?

[eseidel]

OK, I looked into this more and the problem was my debugging tools, not the patches themselves.

The patches actually look to be about the right size (e.g I have a 1.1 mb patch for a 4.9mb release which links at 77%, which seems about correct). The problem is that we don't always link as well as we should.

[eseidel]

patch_size / release_size = 1 - link_percentage (approximately)

[eseidel]

The rest of the work for this is probably part of https://github.com/shorebirdtech/shorebird/issues/2965.

We could also run a verification over our database to confirm that patch_size / release_size = 1 - link_percentage. (If it's not, then there might be other sources of patch inflation). But otherwise I think we can close this for now.

[eseidel]

It's possible that my logic above re: link_percentage is wrong. Our linker is completely insensitive to function relocation (if you jumbled all the functions in a snapshot but made no other changes our linker wouldn't care), however the binary diffing we use is very sensitive to function location because branches are common and diffing algorithms deal well with long repeating patterns, which if you re-sorted all the functions you'd end up with lots and lots of branch destination diffs every few instructions. In any case, that's my theory. We could probably do some of our own re-encoding of branch instructions before patching to reduce patch size, but the bigger bang for the buck is definitely to just improve link_percentages further.