Implement FEC generation and validation

[chenxiaolong]

Currently, avbroot's AVB logic can only verify and update the hash tree portion of hash tree descriptors. The FEC (forward error correction) data is left untouched. We currently don't modify dm-verity partitions, but if we need to in the future, broken/invalid FEC data could cause the user's device to crash or soft brick in the event of a bit flip that trips dm-verity.

(My original understanding of how things worked)

AVB FEC uses RS(255, 253) (Reed-Solomon codewords with 253 bytes of data and 2 bytes of parity) over GF(256) with the 0x11d primitive polynomial. The data fed into RS is not the raw data, but instead, an interleaving pattern. The interleaving is determined by 3 variables:

• FEC block size. This is always 4096.
• RS K value. The K component of RS(N, K), ie. the number of data bytes per codeword. AOSP defaults to 253, which is the only value avbroot will support (because the best Rust library for these calculations uses code generation that requires the K value at compile time). EDIT: avbroot will support everything in [231, 253] (everything allowed by dm-verity).
• "rounds" value. It's undocumented in AOSP, but is equal to ceil(file size / FEC block size / RS K value).

Interleaving pattern:
* Input offset 0 == output offset 0.
* Each time the input offset is incremented by 1, the output offset is incremented by this value times the block size.
~* Once the input offset cross a multiple of rs_k, the output offset "wraps around" and starts again at the beginning again.`

For example, with file_size=2048000 and rs_k=253 (and thus, rounds=2):

offset 0   -> offset 0       (= 0 + 0   * 2 * 4096)
offset 1   -> offset 8192    (= 0 + 1   * 2 * 4096)
offset 2   -> offset 16384   (= 0 + 2   * 2 * 4096)
...
offset 252 -> offset 2064384 (= 0 + 252 * 2 * 4096)
# rs_k chunk boundary.
offset 253 -> offset 1       (= 1 + 0   * 2 * 4096)
offset 254 -> offset 8193    (= 1 + 1   * 2 * 4096)
offset 255 -> offset 16385   (= 1 + 2   * 2 * 4096)
...
# Pattern repeats until EOF.

EDIT: Better documented in the implementation:

avbroot/avbroot/src/format/fec.rs

Lines 121 to 144 in f18a681

	/// The interleaving access pattern can be visualized by placing the file
	/// offsets in a two-dimensional grid. For example, when reading a 2072576-byte
	/// file for calculating RS(255, 253):
	///
	/// ```text
	/// | <-------- Round 0 --------> | <-------- Round 1 --------> |
	/// |-----------------------------|-----------------------------|
	/// ^ | 0 1 ... 4095 | 4096 4097 ... 8191 |
	/// | | 8192 8192 ... 12287 | 12288 12289 ... 16383 |
	/// rs_k | 16384 16385 ... 20479 | 20480 20481 ... 24575 |
	/// | | ....... ....... ... ....... | ....... ....... ... ....... |
	/// v | 2064384 2064385 ... 2068479 | 2068480 2068481 ... 2072575 |
	/// ```
	///
	/// A regular sequential read of the file is traversing the grid row-by-row,
	/// while an interleaving read is traversing the grid column-by-column. Each
	/// column is always `rs_k` items tall, so each column forms the data portion of
	/// an RS codeword. The number of columns is always a multiple of the FEC block
	/// size. Since RS operates on fixed-size codewords and a file size might not
	/// always fill the grid completely, out-of-bounds offsets are treated as if
	/// they contain a `\0` byte.
	///
	/// All operations are multithreaded with I/O operations parallelized at the
	/// "round" level and RS operations parallelized at the column level.

When calculating this FEC data, avbroot will probably default to reading everything into memory with an option to use mmap for memory-constrained systems. The access pattern is probably going to cause a whole lot of thrashing with mmap due to it needing to read one byte at a time all over the file. EDIT: avbroot now uses a much smarter way of doing the interleaved reads, inspired by cryptsetup's veritysetup.

Once implemented (already have a working proof of concept), avbroot avb verify and avbroot ota verify will be updated to check the validity of the FEC data.

[chenxiaolong]

Also, once this is implemented, I plan on adding avbroot avb unpack and avbroot avb pack commands to make it possible to edit and re-sign AVB images on the command line (#144).

[chenxiaolong]

OK... I might only implement the read-whole-file-to-memory method. That runs in 5 seconds against the Pixel 7 Pro's stock system.img.

The read + seek (well, pread) method with 16 threads took 10m16s, spending 99.3% of the CPU time in the kernel's zfs driver. Reading 1 byte at a time all over the place really is a worst case scenario for zfs 🙂 Mmap wouldn't change that.

EDIT: Some benchmarks. mmap is far faster than what I assumed. Even with the page caches cleared out, the first run only takes twice as long as the average time.

Tool	Method	Time
AOSP libfec	Read to memory	4.9s
avbroot	Read to memory	1.4s
avbroot	pread	10m16s
avbroot	mmap	0.7s

EDIT 2: Reading 1-byte at a time is dumb. avbroot fec is now smarter, taking inspiration from how cryptsetup's veritysetup reads data. #146 (comment)