Add support for compressed ota updates

[davisonja]

A useful improvement to the OTA system would be to transfer the update in a compressed format that is expanded as part of the final flash process.

This issue is to provide a place to discuss, plan and exchange clever ideas.

The very first discussion points appeared initially on #905

[devyte]

From #905:

The idea was floated at some point to add support for compressed images, i.e.: receive an image that is compressed.

The following possibilities for implementation have shown up:

Try for full (de)compression, i.e.: deflate, possibly use code from miniz from the flash_stub, which is already known to work on the ESP (because the flash_stub is used by esptool.py). Take the absolute minimum code to deflate and add it to eboot. There is a bit of space left between the end of the eboot bin and the start of the current sketch in the flash. This should be the best solution, because it would allow writing the received image in fully compressed form, then after reboot it could get decompressed on the fly while copying. Also, if the code fits, it would not increase bin size.
Pros:
would allow writing of larger images, thereby relaxing a bit the restriction of bin size for boards with smaller flash size
faster transfer speed
known algorithm and code
wouldn't increase bin size
Cons:
may not fit after eboot due to bin size
Try for some variation of RLE (run-length encoding). Similar idea as above, but with a simpler algorithm instead of miniz. If the above doesn't fit in the available eboot space, maybe this will.
Pros:
would allow writing of larger images, although less so than point 1 above
faster transfer speed, although less so than point 1 above
wouldn't increase bin size
more likely to fit in the available space after eboot
Cons:
less compression than deflate
likely custom compression/decompression code
Put all of miniz into Updater. That would allow receiving a fully compressed image, but it would require deflating it before writing it to the empty space area.
Pros:
smaller transfer size (faster transfer speed) like point 1 above
the eboot code would remain as-is
Cons:
bin size restrictions remain as current (decompress on receive instead of on copy)
bin size increment

[devyte]

@earlephilhower said:

MiniZ inflator alone takes 0x14b2 = 5298 bytes pf code when built with -Os.

I just patched in a naive version into the bootloader and updated the makefile to -Os and function/data_sections with gc-sections to drop everything that's not needed.

earle@server:~/Arduino/hardware/esp8266com/esp8266/bootloaders/eboot$ make
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o eboot.o eboot.c
eboot.c: In function 'copy_raw':
eboot.c:119:10: warning: type defaults to 'int' in declaration of 'status' [enabled by default]
     auto status = tinfl_decompress(&inflator, buffer, &in_bytes,
          ^
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o eboot_command.o eboot_command.c
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o miniz.o miniz.c
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-ar cru eboot.a eboot.o eboot_command.o miniz.o
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -Teboot.ld -Wl,--gc-sections -nostdlib -Wl,--no-check-sections -umain eboot.a -o eboot.elf
earle@server:~/Arduino/hardware/esp8266com/esp8266/bootloaders/eboot$ objdump -t eboot.elf  | grep .text | sort -k1
4010f000 g       *ABS*	00000000 _text_start
4010f000 g       .text	00000000 _stext
4010f000 l    d  .text	00000000 .text
4010f010 g     F .text	00000079 print_version
4010f0a0 g     F .text	0000009b load_app_from_flash_raw
4010f168 g     F .text	00000114 copy_raw
4010f290 g     F .text	000000ea main
4010f380 g     F .text	00000038 crc_update
4010f3b8 g     F .text	00000019 eboot_command_calculate_crc32
4010f3e0 g     F .text	00000049 eboot_command_read
4010f430 g     F .text	00000014 eboot_command_clear
4010f4b8 g     F .text	0000129b tinfl_decompress
40110753 g       *ABS*	00000000 _text_end
40110753 g       .text	00000000 _etext
40110770 l     O .text	00000080 s_dist_base$2064
401107f0 l     O .text	00000080 s_dist_extra$2065
40110870 l     O .text	0000007c s_length_base$2062
401108ec l     O .text	0000007c s_length_extra$2063
40110968 l     O .text	00000013 s_length_dezigzag$2066
4011097c l     O .text	0000000c s_min_table_sizes$2067
40240000 g       *ABS*	00000000 _irom0_text_end
40240000 g       *ABS*	00000000 _irom0_text_start

[devyte]

@davisonja said:

That's a more comprehensive assessment. I commented out the compressor code and built it to get an absolute upper bound, which was about 15k (with eboot, but no optimisations). It seemed like a viable prospect even at that size.

[devyte]

@earlephilhower said:

For eboot, the makefile needs ti go from -O0 to -Os, since at 0 it won't even do simple optimizations.

Then, the problem is that minigz has compress and decompress in one file and the linker will include the entire file even if compression is unused (-flto doesn't work on GCC 4.8). So add in -f(data|function)-sections and -fgc-sections (check exact syntax in our platform.txt) and it'll finally drop the compression bits and you'll be left with the minimum needed.

Granted, I did not test the resulting ELF, just looked at sizes. The eboot.c might have some code that's busted in a way to require no optimization to work.

[devyte]

Alright, let's continue the compressed OTA discussion here.

[TD-er]

Is the typical gain in size comparable with the compression levels reported by the flash tool?

[earlephilhower]

Using the 5.5k miniz would give exactly the same compression as the uploader. The simpler RLE would give about 0 compression on binaries, but close to the same on sparse filesystems.

[davisonja]

While I've certainly encountered obscure optimisation issues with bootloaders in other places, it's been fairly irrelevant for eboot.
It's currently less than a single 4k page in size.

[davisonja]

Iirc lzw ends up being fairly small and does better than rle. It's been a while since I built it in C, tho.

With only a little thought we should be able to expose inflator code in eboot for use in main code meaning it would save additional space in images.

[d-a-v]

Very interesting, lzw

[TD-er]

Just a question/thought I have.
If the image can already be compressed significantly using run-length-encoding, can't the linker/compiler do something to create a smaller image which is still able to be executed by the ESP?
I understand offsets to functions and data have to be re-calculated, but what may be the reason it cannot be done at compile time? (just assuming it cannot be done, otherwise it has already been done, so what am I missing here :) )

Is it only RLE, or is it also using some very basic dictionary and thus able to compress English words/texts by a significant factor?

[earlephilhower]

@TD-er ... RLE + dictionary ~= LZW. :) I thought zlib was LZW, too, but maybe I'm thinking of original AT&T compress or something...

GNU LD or GCC are not going to do any kind of exe compression like that. The CPU already has variable-length instructions, helping minimize code size vs. a nice, clean, 32b insn word like in the Hennessy and Patterson everyone starts with.

There's really no runs of constant values in the executable portion of a binary, so RLE won't affect size there.

[TD-er]

What part of the binary is then compressed/compressible using RLE?
Thing is, I'm a bit amazed by the amount of compression achieved using just RLE.

[earlephilhower]

RLE will compress ~0% of the executable. On a 1MB filesystem with 100k of files, RLE will compress a heck of a lot.

zlib/miniz gives maybe 20-30% compression on the binaries, and great #s on a sparse FS (the long runs of 0s will give ~ same as RLE, while the data pages will get whatever miniz can do on them)

[TD-er]

But when I do an OTA of the sketch, I don't have the filesystem included, right?
0% compression on the executable is what I would expect. Maybe even slightly larger when attempted to compress using RLE.
So what is then being compressed using RLE that would allow for smaller space requirements for OTA and also done by esptool.py?

[d-a-v]

esptool uploads a gzip zlib inflater to esp-ram through serial (that is quite phat in ram usage at runtime). We currently don't have a zlib inflater in flash for OTA (a one being not phat in ram and in eboot flash is needed).
edit: unless eboot loads the decompressor from flash to ram then execute it like esptool inflater does ?
edit2: unless we find another lightweight enough zlib inflater to fit in eboot flash ?

[davisonja]

eboot currently runs from ram that's how it is able to overwrite itself (which it does as part of every upgrade). I don't have any concerns about adding the inflator to eboot and having everything run as it currently does - unless I've misread something :)

[earlephilhower]

One issue to keep in mind when doing compressed updates is signed binaries. You have to sign the uncompressed binary and perform the check in Updater.cpp to ensure it's not been tampered with. I suppose it's possible to make signing.py do the actual compression and sign that blob, but then the uploader needs to make sure it doesn't try it again...

[TD-er]

Or you could also sign the compressed one?
If you only check for uncompressed binary, you may need to either uncompress it twice or reject it after writing it all to flash.

Another thing to keep in mind is the uncompressed size of the binary, so it may not overwrite the SPIFFS or EEPROM part of the flash layout unintended.

[davisonja]

I'd opt for signing the compressed one. The bootloader should be able to assume the data its dealing with is valid/acceptable. Unless we're looking at making the bootloader a sort of utility library for main code to use we should aim to keep it fairly lightweight and small - so we don't want to be adding signature verification to it.

[devyte]

What's the status here? can this be closed?

[earlephilhower]

Yeah, I think this is closed with the commit since OTA is the only way to get a compressed update in flash.

[sticilface]

Forgive me for commenting on a closed issue. I'm trying to get my head around the progress that's been made in the last year that i've been out of the loop.

Compression is a brilliant idea but the workflow at the moment seems to be that you have to manually compress it, then sign it if you want that, then upload it.

Is there a reason that the uploader (espota.py) cannot support a --compress flag to compress the binary with a menu option in arduino/ flag in pio. There are issues discussing moving to esptool.py which does support compression but having a very superficial look I can't see that, and 1.7.4 just contains esptool no esptool.py.

Furthermore would it be possible to have the OTA query the device to see if the updaterClass supports compression eg via the FS_ATOMIC_UPDATES flag and send a compressed binary/FS? This way the entire process is transparent and backwards compatible!

I can open a new issue if desired.

[d-a-v]

I can open a new issue if desired.

That is advised.
Build scripts may be able to generate both .bin and .bin.gz.
I think it is possible to add an option in espota.py to use the .bin.gz.
This can be discussed in the issue you will open about it.