From aa1d314ac2febafc5243266b420ff57b280621c5 Mon Sep 17 00:00:00 2001 From: Randall Spangler Date: Fri, 26 Aug 2016 16:01:16 -0700 Subject: 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: Ieb97563ab92bd1d18a4f6a9e1d20157efe311fb4 Signed-off-by: Martin Roth Original-Commit-Id: db9bb2d3927ad57270d7acfd42cf0652102993b1 Original-Change-Id: I1eb5fd9fa6b2ae56833f024bcd3c250147bcc7a1 Original-Signed-off-by: Randall Spangler Original-Reviewed-on: https://chromium-review.googlesource.com/376928 Original-Reviewed-by: Julius Werner Reviewed-on: https://review.coreboot.org/16577 Tested-by: build bot (Jenkins) Reviewed-by: Vadim Bendebury Reviewed-by: Patrick Georgi --- src/vboot/vbnv_flash.c | 28 +++++++++++++++++----------- 1 file changed, 17 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/vboot/vbnv_flash.c b/src/vboot/vbnv_flash.c index 81c4f087af..dd128a9235 100644 --- a/src/vboot/vbnv_flash.c +++ b/src/vboot/vbnv_flash.c @@ -65,6 +65,7 @@ static int init_vbnv(void) struct region_device *rdev = &ctx->vbnv_dev; uint8_t buf[BLOB_SIZE]; uint8_t empty_blob[BLOB_SIZE]; + int used_below, empty_above; int offset; int i; @@ -78,25 +79,30 @@ static int init_vbnv(void) for (i = 0; i < BLOB_SIZE; i++) empty_blob[i] = erase_value(); - offset = 0; ctx->top_offset = region_device_sz(rdev) - BLOB_SIZE; - /* - * after the loop, offset is supposed to point the blob right before - * the first empty blob, the last blob in the nvram if there is no - * empty blob, or the base of the region if the nvram has never been - * used. - */ - for (i = 0; i <= ctx->top_offset; i += BLOB_SIZE) { - if (rdev_readat(rdev, buf, i, BLOB_SIZE) < 0) { + /* Binary search for the border between used and empty */ + used_below = 0; + empty_above = region_device_sz(rdev) / BLOB_SIZE; + + while (used_below + 1 < empty_above) { + int guess = (used_below + empty_above) / 2; + if (rdev_readat(rdev, buf, guess * BLOB_SIZE, BLOB_SIZE) < 0) { printk(BIOS_ERR, "failed to read nvdata\n"); return 1; } if (!memcmp(buf, empty_blob, BLOB_SIZE)) - break; - offset = i; + empty_above = guess; + else + used_below = guess; } + /* + * Offset points to the last non-empty blob. Or if all blobs are empty + * (nvram is totally erased), point to the first blob. + */ + offset = used_below * BLOB_SIZE; + /* reread the nvdata and write it to the cache */ if (rdev_readat(rdev, ctx->cache, offset, BLOB_SIZE) < 0) { printk(BIOS_ERR, "failed to read nvdata\n"); -- cgit v1.2.3