Refactor the memory wipe infrastructure to better support x86

The memory wipe infrastructure in u-boot makes some assumptions about how
memory is arranged that make it not quite fit with x86. Specifically, it
assumes that there is a single region of memory, and with certain exceptions
that's what should be wiped. In x86, specifically in the e820 map, there are
multiple regions of RAM, possibly multiple regions to exclued from that that
may completely, partially, or not overlap with the others, and then u-boot
related regions.

This is addressed by making the memory wipe infrastructure a little more
generic. Now, areas can be added and subtracted arbitrarily, and will
accumulate in the order they're encountered. In the x86 use case, we can add
the e820 regions marked as RAM, subtract the areas marked as anything else, and
subtract the u-boot related regions.

Rather than tracking the actual regions of the address space, this
implementation tracks the boundaries between the regions using a linked list.
The code itself is short and relatively simple, and I tried to ensure that it
was as clear as possible to make any memory (or other) bugs easier to see and
fix.

BUG=chrome-os-partner:6195
BUG=chrome-os-partner:6194
TEST=Built and booted on kaen using the A-A cable. Ran vboot_test memwipe, and
a modified version that took advantage of the new API.

Change-Id: I122fbf499ef473350afa27b612cb0e565366b1ad
Signed-off-by: Gabe Black <gabeblack@google.com>
Reviewed-on: http://gerrit.chromium.org/gerrit/9715
Reviewed-by: Simon Glass <sjg@chromium.org>

4 files changed, 144 insertions, 63 deletions

diff --git a/common/cmd_vboot_test.c b/common/cmd_vboot_test.c
index 8521a62e03..ff8b9efbb3 100644
--- a/common/cmd_vboot_test.c
+++ b/common/cmd_vboot_test.c
@@ -123,21 +123,22 @@ static int do_vboot_test_memwipe(cmd_tbl_t *cmdtp,
 	const size_t size = strlen(s);
 	uintptr_t base = (uintptr_t)s;
 
-	memory_wipe_init(&wipe, base, base + size);
+	memory_wipe_init(&wipe);
+	memory_wipe_add(&wipe, base, base + size);
 	/* Result: ---------- */
-	memory_wipe_exclude(&wipe, base + 1, base + 2);
+	memory_wipe_sub(&wipe, base + 1, base + 2);
 	/* Result: -B-------- */
-	memory_wipe_exclude(&wipe, base + 5, base + 7);
+	memory_wipe_sub(&wipe, base + 5, base + 7);
 	/* Result: -B---FG--- */
-	memory_wipe_exclude(&wipe, base + 2, base + 3);
+	memory_wipe_sub(&wipe, base + 2, base + 3);
 	/* Result: -BC--FG--- */
-	memory_wipe_exclude(&wipe, base + 9, base + 10);
+	memory_wipe_sub(&wipe, base + 9, base + 10);
 	/* Result: -BC--FG--J */
-	memory_wipe_exclude(&wipe, base + 4, base + 6);
+	memory_wipe_sub(&wipe, base + 4, base + 6);
 	/* Result: -BC-EFG--J */
-	memory_wipe_exclude(&wipe, base + 3, base + 5);
+	memory_wipe_sub(&wipe, base + 3, base + 5);
 	/* Result: -BCDEFG--J */
-	memory_wipe_exclude(&wipe, base + 2, base + 8);
+	memory_wipe_sub(&wipe, base + 2, base + 8);
 	/* Result: -BCDEFGH-J */
 	memory_wipe_execute(&wipe);
 
diff --git a/common/cmd_vboot_twostop.c b/common/cmd_vboot_twostop.c
index d56b627141..9441041a83 100644
--- a/common/cmd_vboot_twostop.c
+++ b/common/cmd_vboot_twostop.c
@@ -178,27 +178,28 @@ wipe_unused_memory(crossystem_data_t *cdata, VbCommonParams *cparams)
 	if (fdt_decode_memory(gd->blob, &config))
 		VbExError(PREFIX "FDT decode memory section error\n");
 
-	memory_wipe_init(&wipe, config.start, config.end);
+	memory_wipe_init(&wipe);
+	memory_wipe_add(&wipe, config.start, config.end);
 
 	/* Excludes stack, fdt, gd, bd, heap, u-boot, framebuffer, etc. */
-	memory_wipe_exclude(&wipe, get_current_sp() - STACK_MARGIN, config.end);
+	memory_wipe_sub(&wipe, get_current_sp() - STACK_MARGIN, config.end);
 
 	/* Excludes the shared data between bootstub and main firmware. */
-	memory_wipe_exclude(&wipe, (uintptr_t)cdata,
+	memory_wipe_sub(&wipe, (uintptr_t)cdata,
 			(uintptr_t)cdata + sizeof(*cdata));
-	memory_wipe_exclude(&wipe, (uintptr_t)cparams->gbb_data,
+	memory_wipe_sub(&wipe, (uintptr_t)cparams->gbb_data,
 			(uintptr_t)cparams->gbb_data + cparams->gbb_size);
 
 	/* Excludes the LP0 vector. */
-	memory_wipe_exclude(&wipe,
-			    (uintptr_t)TEGRA_LP0_ADDR,
-			    (uintptr_t)(TEGRA_LP0_ADDR + TEGRA_LP0_SIZE));
+	memory_wipe_sub(&wipe,
+			(uintptr_t)TEGRA_LP0_ADDR,
+			(uintptr_t)(TEGRA_LP0_ADDR + TEGRA_LP0_SIZE));
 
 	/* Excludes the frame buffer. */
 	fb_size = lcd_get_size(&lcd_line_length);
-	memory_wipe_exclude(&wipe,
-			    (uintptr_t)gd->fb_base,
-			    (uintptr_t)gd->fb_base + fb_size);
+	memory_wipe_sub(&wipe,
+			(uintptr_t)gd->fb_base,
+			(uintptr_t)gd->fb_base + fb_size);
 
 	memory_wipe_execute(&wipe);
 #endif
diff --git a/include/chromeos/memory_wipe.h b/include/chromeos/memory_wipe.h
index 5ce0913b75..cc3535a1ba 100644
--- a/include/chromeos/memory_wipe.h
+++ b/include/chromeos/memory_wipe.h
@@ -23,32 +23,49 @@
 
 #include <linux/types.h>
 
-#define MAX_EXCLUDED_REGIONS    16
+/* A node in a linked list of edges, each at position "pos". */
+typedef struct memory_wipe_edge_t {
+	struct memory_wipe_edge_t *next;
+	uintptr_t pos;
+} memory_wipe_edge_t;
 
-typedef struct {
-	uintptr_t start;
-	uintptr_t end;
-} memory_region_t;
-
-typedef struct {
-	memory_region_t whole;
-	memory_region_t excluded[MAX_EXCLUDED_REGIONS];
-	int excluded_count;
+/*
+ * Data describing memory to wipe. Contains a linked list of edges between the
+ * regions of memory to wipe and not wipe.
+ */
+typedef struct memory_wipe_t {
+	memory_wipe_edge_t head;
 } memory_wipe_t;
 
 /*
  * Initializes the memory region that needs to be cleared.
+ *
+ * @param wipe		Wipe structure to initialize.
+ */
+void memory_wipe_init(memory_wipe_t *wipe);
+
+/*
+ * Adds a memory region to be cleared.
+ *
+ * @param wipe		Wipe structure to add the region to.
+ * @param start		The start of the region.
+ * @param end		The end of the region.
  */
-void memory_wipe_init(memory_wipe_t *wipe, uintptr_t start, uintptr_t end);
+void memory_wipe_add(memory_wipe_t *wipe, uintptr_t start, uintptr_t end);
 
 /*
- * Excludes a memory region from the to-be-cleared region.
- * The function returns 0 on success; otherwise -1.
+ * Subtracts a memory region.
+ *
+ * @param wipe		Wipe structure to subtract the region from.
+ * @param start		The start of the region.
+ * @param end		The end of the region.
  */
-int memory_wipe_exclude(memory_wipe_t *wipe, uintptr_t start, uintptr_t end);
+void memory_wipe_sub(memory_wipe_t *wipe, uintptr_t start, uintptr_t end);
 
 /*
- * Executes the memory wipe to the memory regions which was not excluded.
+ * Executes the memory wipe.
+ *
+ * @param wipe		Wipe structure to execute.
  */
 void memory_wipe_execute(memory_wipe_t *wipe);
 
diff --git a/lib/chromeos/memory_wipe.c b/lib/chromeos/memory_wipe.c
index 59ea0ef145..f8476b35ab 100644
--- a/lib/chromeos/memory_wipe.c
+++ b/lib/chromeos/memory_wipe.c
@@ -11,58 +11,120 @@
 #include <common.h>
 #include <chromeos/common.h>
 #include <chromeos/memory_wipe.h>
+#include <malloc.h>
 
 #include <vboot_api.h>
 
 #define PREFIX		"memory_wipe: "
 
-void memory_wipe_init(memory_wipe_t *wipe, uintptr_t start, uintptr_t end)
+/*
+ * This implementation tracks regions of memory that need to be wiped by
+ * filling them with zeroes. It does that by keeping a linked list of the
+ * edges between regions where memory should be wiped and not wiped. New
+ * regions take precedence over older regions they overlap with. With
+ * increasing addresses, the regions of memory alternate between needing to be
+ * wiped and needing to be left alone. Edges similarly alternate between
+ * starting a wipe region and starting a not wiped region.
+ */
+
+static void memory_wipe_insert_between(memory_wipe_edge_t *before,
+	memory_wipe_edge_t *after, uintptr_t pos)
 {
-	wipe->whole.start = start;
-	wipe->whole.end = end;
-	wipe->excluded_count = 0;
+	memory_wipe_edge_t *new_edge =
+		(memory_wipe_edge_t *)malloc(sizeof(*new_edge));
+
+	assert(new_edge);
+	assert(before != after);
+
+	new_edge->next = after;
+	new_edge->pos = pos;
+	before->next = new_edge;
 }
 
-int memory_wipe_exclude(memory_wipe_t *wipe, uintptr_t start, uintptr_t end)
+void memory_wipe_init(memory_wipe_t *wipe)
 {
-	int i = wipe->excluded_count;
+	wipe->head.next = NULL;
+	wipe->head.pos = 0;
+}
+
+static void memory_wipe_set_region_to(memory_wipe_t *wipe_info,
+	uintptr_t start, uintptr_t end, int new_wiped)
+{
+	/* whether the current region was originally going to be wiped. */
+	int wipe = 0;
+
+	assert(start != end);
 
-	if (i >= MAX_EXCLUDED_REGIONS) {
-		VBDEBUG(PREFIX "the number of excluded regions reaches"
-				"the maximum: %d\n", MAX_EXCLUDED_REGIONS);
-		return -1;
+	/* prev is never NULL, but cur might be. */
+	memory_wipe_edge_t *prev = &wipe_info->head;
+	memory_wipe_edge_t *cur = prev->next;
+
+	/*
+	 * Find the start of the new region. After this loop, prev will be
+	 * before the start of the new region, and cur will be after it or
+	 * overlapping start. If they overlap, this ensures that the existing
+	 * edge is deleted and we don't end up with two edges in the same spot.
+	 */
+	while (cur && cur->pos < start) {
+		prev = cur;
+		cur = cur->next;
+		wipe = !wipe;
+	}
+
+	/* Add the "start" edge between prev and cur, if needed. */
+	if (new_wiped != wipe) {
+		memory_wipe_insert_between(prev, cur, start);
+		prev = prev->next;
 	}
 
-	while (i > 0 && wipe->excluded[i - 1].start > start) {
-		wipe->excluded[i].start = wipe->excluded[i - 1].start;
-		wipe->excluded[i].end = wipe->excluded[i - 1].end;
-		i--;
+	/*
+	 * Delete any edges obscured by the new region. After this loop, prev
+	 * will be before the end of the new region or overlapping it, and cur
+	 * will be after if, if there is a edge after it. For the same
+	 * reason as above, we want to ensure that we end up with one edge if
+	 * there's an overlap.
+	 */
+	while (cur && cur->pos <= end) {
+		cur = cur->next;
+		free(prev->next);
+		prev->next = cur;
+		wipe = !wipe;
 	}
-	wipe->excluded[i].start = start;
-	wipe->excluded[i].end = end;
-	wipe->excluded_count++;
 
-	return 0;
+	/* Add the "end" edge between prev and cur, if needed. */
+	if (wipe != new_wiped)
+		memory_wipe_insert_between(prev, cur, end);
 }
 
-static void zero_mem(uintptr_t start, uintptr_t end)
+/* Set a region to "wiped". */
+void memory_wipe_add(memory_wipe_t *wipe, uintptr_t start, uintptr_t end)
 {
-	if (end > start) {
-		VBDEBUG(PREFIX "\t[0x%08x, 0x%08x)\n", start, end);
-		memset((void *)start, '\0', (size_t)(end - start));
-	}
+	memory_wipe_set_region_to(wipe, start, end, 1);
 }
 
+/* Set a region to "not wiped". */
+void memory_wipe_sub(memory_wipe_t *wipe, uintptr_t start, uintptr_t end)
+{
+	memory_wipe_set_region_to(wipe, start, end, 0);
+}
+
+/* Actually wipe memory. */
 void memory_wipe_execute(memory_wipe_t *wipe)
 {
-	uintptr_t addr = wipe->whole.start;
-	int i;
+	memory_wipe_edge_t *cur;
 
 	VBDEBUG(PREFIX "Wipe memory regions:\n");
-	for (i = 0; i < wipe->excluded_count; i++) {
-		zero_mem(addr, wipe->excluded[i].start);
-		if (wipe->excluded[i].end > addr)
-			addr = wipe->excluded[i].end;
+	for (cur = wipe->head.next; cur; cur = cur->next->next) {
+		uintptr_t start, end;
+
+		if (!cur->next) {
+			VBDEBUG(PREFIX "Odd number of region edges!\n");
+			return;
+		}
+
+		start = cur->pos;
+		end = cur->next->pos;
+		VBDEBUG(PREFIX "\t[%#08x, 0x%08x)\n", start, end);
+		memset((void *)start, 0, end - start);
 	}
-	zero_mem(addr, wipe->whole.end);
 }