coreboot: Use binary search to find current vboot NVRAM record |
|||||||||||
Issue descriptionNVRAM records in flash are 16-byte records stored in up to 16KB of flash. Currently we just blindly loop through it to find the most recent record. That's not so bad on a freshly erased flash, but pretty inefficient after a lot of updates. It would be better to binary-search. On a half-full flash, that would cut the amount of data read from 8KB to 16 * log2(8KB/16) = 144 bytes. There's no change in the data format, so this is backwards-compatible. src/third_party/coreboot/src/vboot/vbnv_flash.c A similar change could probably be made to the ELOG module.
,
Aug 24 2016
We should be able to transfer 16KB in <3ms, but apparently Kevin is 10x that at present. I'm hoping to look at improving that, but in any case, this idea sounds good to me.
,
Aug 24 2016
You can't do that on ELOG. Unless you don't want to bother verifying you have a valid elog. And you need to magically recover where the true end is by verifying a variable length event w/ no start marker.
,
Aug 24 2016
+1, this sounds reasonably simple and good enough. Note that it has to be implemented in both coreboot and depthcharge/src/vboot/callbacks/nvstorage_flash.c (and possibly mosys, but that one is not as critical).
,
Aug 29 2016
Patches: https://chromium-review.googlesource.com/376928 (coreboot) https://chromium-review.googlesource.com/377601 (depthcharge) I haven't tested them on Kevin yet (don't have one) but I did save money on my car insurance by switching to Geico. Oh, and I used the attached standalone test.
,
Sep 1 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromiumos/third_party/coreboot/+/db9bb2d3927ad57270d7acfd42cf0652102993b1 commit db9bb2d3927ad57270d7acfd42cf0652102993b1 Author: Randall Spangler <rspangler@chromium.org> Date: Fri Aug 26 23:01:16 2016 vboot/vbnv_flash: Binary search to find last used entry This improves the previous linear search to O(log n). No change in storage format. BUG= chromium:640656 BRANCH=none TEST=Manual (test empty) flashrom -i RW_NVRAM -e Reboot; device should boot normally. (start using records) crossystem kern_nv=0xaab0 crossystem recovery_request=1 && reboot Device should go into recovery mode with reason 1 Reboot again; it should boot normally. crossystem kern_nv (should still contain 0xaab0) Repeat steps several times with request=2, 3, etc. flashrom -i RW_NVRAM -r nvdata Modify nvdata to copy the first record across all valid records flashrom -i RW_NVRAM -w nvdata Reboot; device should boot normally. Change-Id: I1eb5fd9fa6b2ae56833f024bcd3c250147bcc7a1 Signed-off-by: Randall Spangler <rspangler@chromium.org> Reviewed-on: https://chromium-review.googlesource.com/376928 Reviewed-by: Julius Werner <jwerner@chromium.org> [modify] https://crrev.com/db9bb2d3927ad57270d7acfd42cf0652102993b1/src/vboot/vbnv_flash.c
,
Sep 2 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromiumos/platform/depthcharge/+/0819dd49baa0ad59174fa5bc5092c8d74a3092f3 commit 0819dd49baa0ad59174fa5bc5092c8d74a3092f3 Author: Randall Spangler <rspangler@chromium.org> Date: Mon Aug 29 23:19:20 2016 vboot: Binary search nvstorage_flash to find last used entry This improves the previous linear search to O(log n). No change in storage format. BUG= chromium:640656 BRANCH=none TEST=Manual Place device in developer mode. (test empty) flashrom -i RW_NVRAM -e Reboot; device should boot normally. (start using records, altering a field depthcharge cares about) crossystem kern_nv=0xaab0 crossystem dev_boot_usb=1 && reboot At the dev warning screen, try booting from USB; should succeed crossystem dev_boot_usb=0 && reboot At the dev warning screen, try booting from USB; should fail crossystem kern_nv (should still contain 0xaab0) Repeat steps several times flashrom -i RW_NVRAM -r nvdata Modify nvdata to copy the first record across all valid records flashrom -i RW_NVRAM -w nvdata Reboot; device should boot normally. Change-Id: I356aefeb81ea5670d2732d7a320798b38f79b23f Signed-off-by: Randall Spangler <rspangler@chromium.org> Reviewed-on: https://chromium-review.googlesource.com/377601 Reviewed-by: Julius Werner <jwerner@chromium.org> [modify] https://crrev.com/0819dd49baa0ad59174fa5bc5092c8d74a3092f3/src/vboot/callbacks/nvstorage_flash.c
,
Sep 2 2016
,
Oct 7 2016
,
Nov 19 2016
,
Jan 21 2017
,
Mar 4 2017
,
Apr 17 2017
,
May 30 2017
,
Aug 1 2017
,
Oct 14 2017
|
|||||||||||
►
Sign in to add a comment |
|||||||||||
Comment 1 by rspangler@chromium.org
, Aug 24 2016