[coreboot-gerrit] New patch to review for coreboot: vboot/vbnv_flash: Binary search to find last used entry

[Martin Roth (martinroth@google.com)]

Martin Roth (martinroth at google.com) just uploaded a new patch set to gerrit, which you can find at https://review.coreboot.org/16577

-gerrit

commit 77b85086f61deec1e48a557469730c3892955c50
Author: Randall Spangler <rspangler at chromium.org>
Date:   Fri Aug 26 16:01:16 2016 -0700

    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 <martinroth at chromium.org>
    Original-Commit-Id: db9bb2d3927ad57270d7acfd42cf0652102993b1
    Original-Change-Id: I1eb5fd9fa6b2ae56833f024bcd3c250147bcc7a1
    Original-Signed-off-by: Randall Spangler <rspangler at chromium.org>
    Original-Reviewed-on: https://chromium-review.googlesource.com/376928
    Original-Reviewed-by: Julius Werner <jwerner at chromium.org>
---
 src/vboot/vbnv_flash.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)

diff --git a/src/vboot/vbnv_flash.c b/src/vboot/vbnv_flash.c
index 81c4f08..dd128a9 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");