1 files changed, 474 insertions, 0 deletions
diff --git a/src/lib/region_file.c b/src/lib/region_file.c
new file mode 100644
index 0000000000..9d103f2404
--- /dev/null
+++ b/src/lib/region_file.c
@@ -0,0 +1,474 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright 2016 Google Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ */
+
+#include <commonlib/helpers.h>
+#include <console/console.h>
+#include <region_file.h>
+#include <string.h>
+
+/*
+ * A region file provides generic support for appending new data
+ * within a storage region. The book keeping is tracked in metadata
+ * blocks where an offset pointer points to the last byte of a newly
+ * allocated byte sequence. Thus, by taking 2 block offets one can
+ * determine start and size of the latest update. The data does not
+ * have to be the same consistent size, but the data size has be small
+ * enough to fit a metadata block and one data write within the region.
+ *
+ * The granularity of the block offsets are 16 bytes. By using 16-bit
+ * block offsets a region's total size can be no larger than 1MiB.
+ * However, the last 32 bytes cannot be used in the 1MiB maximum region
+ * because one needs to put a block offset indicating last byte written.
+ * An unused block offset is the value 0xffff or 0xffff0 bytes. The last
+ * block offset that can be written is 0xfffe or 0xfffe0 byte offset.
+ *
+ * The goal of this library is to provide a simple mechanism for
+ * allocating blocks of data for updates. The metadata is written first
+ * followed by the data. That means a power event between the block offset
+ * write and the data write results in blocks being allocated but not
+ * entirely written. It's up to the user of the library to sanity check
+ * data stored.
+ */
+
+#define REGF_BLOCK_SHIFT		4
+#define REGF_BLOCK_GRANULARITY		(1 << REGF_BLOCK_SHIFT)
+#define REGF_METADATA_BLOCK_SIZE	REGF_BLOCK_GRANULARITY
+#define REGF_UNALLOCATED_BLOCK		0xffff
+#define REGF_UPDATES_PER_METADATA_BLOCK	\
+	(REGF_METADATA_BLOCK_SIZE / sizeof(uint16_t))
+
+enum {
+	RF_ONLY_METADATA = 0,
+	RF_EMPTY = -1,
+	RF_NEED_TO_EMPTY = -2,
+	RF_FATAL = -3,
+};
+
+struct metadata_block {
+	uint16_t blocks[REGF_UPDATES_PER_METADATA_BLOCK];
+};
+
+static size_t block_to_bytes(uint16_t offset)
+{
+	return (size_t)offset << REGF_BLOCK_SHIFT;
+}
+
+static size_t bytes_to_block(size_t bytes)
+{
+	return bytes >> REGF_BLOCK_SHIFT;
+}
+
+static inline int block_offset_unallocated(uint16_t offset)
+{
+	return offset == REGF_UNALLOCATED_BLOCK;
+}
+
+static inline size_t region_file_data_begin(const struct region_file *f)
+{
+	return f->data_blocks[0];
+}
+
+static inline size_t region_file_data_end(const struct region_file *f)
+{
+	return f->data_blocks[1];
+}
+
+static int all_block_offsets_unallocated(const struct metadata_block *mb)
+{
+	size_t i;
+
+	for (i = 0; i < ARRAY_SIZE(mb->blocks); i++) {
+		if (!block_offset_unallocated(mb->blocks[i]))
+			return 0;
+	}
+
+	return 1;
+}
+
+/* Read metadata block at block i. */
+static int read_mb(size_t i, struct metadata_block *mb,
+			const struct region_file *f)
+{
+	size_t offset = block_to_bytes(i);
+
+	if (rdev_readat(&f->metadata, mb, offset, sizeof(*mb)) < 0)
+		return -1;
+
+	return 0;
+}
+
+/* Locate metadata block with the latest update */
+static int find_latest_mb(struct metadata_block *mb, size_t num_mb_blocks,
+				struct region_file *f)
+{
+	size_t l = 0;
+	size_t r = num_mb_blocks;
+
+	while (l + 1 < r) {
+		size_t mid = (l + r) / 2;
+
+		if (read_mb(mid, mb, f) < 0)
+			return -1;
+		if (all_block_offsets_unallocated(mb))
+			r = mid;
+		else
+			l = mid;
+	}
+
+	/* Set the base block slot. */
+	f->slot = l * REGF_UPDATES_PER_METADATA_BLOCK;
+
+	/* Re-read metadata block with the latest update. */
+	if (read_mb(l, mb, f) < 0)
+		return -1;
+
+	return 0;
+}
+
+static void find_latest_slot(struct metadata_block *mb, struct region_file *f)
+{
+	size_t i;
+
+	for (i = REGF_UPDATES_PER_METADATA_BLOCK - 1; i > 0; i--) {
+		if (!block_offset_unallocated(mb->blocks[i]))
+			break;
+	}
+
+	f->slot += i;
+}
+
+static int fill_data_boundaries(struct region_file *f)
+{
+	struct region_device slots;
+	size_t offset;
+	size_t size = sizeof(f->data_blocks);
+
+	if (f->slot == RF_ONLY_METADATA) {
+		size_t start = bytes_to_block(region_device_sz(&f->metadata));
+		f->data_blocks[0] = start;
+		f->data_blocks[1] = start;
+		return 0;
+	}
+
+	/* Sanity check the 2 slot sequence to read. If it's out of the
+	 * metadata blocks' bounds then one needs to empty it. This is done
+	 * to uniquely identify I/O vs data errors in the readat() below. */
+	offset = (f->slot - 1) * sizeof(f->data_blocks[0]);
+	if (rdev_chain(&slots, &f->metadata, offset, size)) {
+		f->slot = RF_NEED_TO_EMPTY;
+		return 0;
+	}
+
+	if (rdev_readat(&slots, &f->data_blocks, 0, size) < 0) {
+		printk(BIOS_ERR, "REGF failed to read data boundaries.\n");
+		return -1;
+	}
+
+	/* All used blocks should be incrementing from previous write. */
+	if (region_file_data_begin(f) >= region_file_data_end(f)) {
+		printk(BIOS_ERR, "REGF data boundaries wrong. [%zd,%zd) Need to empty.\n",
+			region_file_data_begin(f), region_file_data_end(f));
+		f->slot = RF_NEED_TO_EMPTY;
+		return 0;
+	}
+
+	/* Ensure data doesn't exceed the region. */
+	if (region_file_data_end(f) >
+		bytes_to_block(region_device_sz(&f->rdev))) {
+		printk(BIOS_ERR, "REGF data exceeds region %zd > %zd\n",
+			region_file_data_end(f),
+			bytes_to_block(region_device_sz(&f->rdev)));
+		f->slot = RF_NEED_TO_EMPTY;
+	}
+
+	return 0;
+}
+
+int region_file_init(struct region_file *f, const struct region_device *p)
+{
+	struct metadata_block mb;
+
+	/* Total number of metadata blocks is found by reading the first
+	 * block offset as the metadata is allocated first. At least one
+	 * metadata block is available. */
+
+	memset(f, 0, sizeof(*f));
+	f->slot = RF_FATAL;
+
+	/* Keep parent around for accessing data later. */
+	if (rdev_chain(&f->rdev, p, 0, region_device_sz(p)))
+		return -1;
+
+	if (rdev_readat(p, &mb, 0, sizeof(mb)) < 0) {
+		printk(BIOS_ERR, "REGF fail reading first metadata block.\n");
+		return -1;
+	}
+
+	/* No metadata has been allocated. Assume region is empty. */
+	if (block_offset_unallocated(mb.blocks[0])) {
+		f->slot = RF_EMPTY;
+		return 0;
+	}
+
+	/* If metadata block is 0 in size then need to empty. */
+	if (mb.blocks[0] == 0) {
+		f->slot = RF_NEED_TO_EMPTY;
+		return 0;
+	}
+
+	/* The region needs to be emptied as the metadata is broken. */
+	if (rdev_chain(&f->metadata, p, 0, block_to_bytes(mb.blocks[0]))) {
+		f->slot = RF_NEED_TO_EMPTY;
+		return 0;
+	}
+
+	/* Locate latest metadata block with latest update. */
+	if (find_latest_mb(&mb, mb.blocks[0], f)) {
+		printk(BIOS_ERR, "REGF fail locating latest metadata block.\n");
+		f->slot = RF_FATAL;
+		return -1;
+	}
+
+	find_latest_slot(&mb, f);
+
+	/* Fill in the data blocks marking the latest update. */
+	if (fill_data_boundaries(f)) {
+		printk(BIOS_ERR, "REGF fail locating data boundaries.\n");
+		f->slot = RF_FATAL;
+		return -1;
+	}
+
+	return 0;
+}
+
+int region_file_data(const struct region_file *f, struct region_device *rdev)
+{
+
+	size_t offset;
+	size_t size;
+
+	/* Slot indicates if any data is available. */
+	if (f->slot <= RF_ONLY_METADATA)
+		return -1;
+
+	offset = block_to_bytes(region_file_data_begin(f));
+	size = block_to_bytes(region_file_data_end(f)) - offset;
+
+	return rdev_chain(rdev, &f->rdev, offset, size);
+}
+
+/*
+ * Allocate enough metadata blocks to maximize data updates. Do this in
+ * terms of blocks. To solve the balance of metadata vs data, 2 linear
+ * equations are solved in terms of blocks where 'x' is number of
+ * data updates and 'y' is number of metadata blocks:
+ *
+ *   x = number of data updates
+ *   y = number of metadata blocks
+ *   T = total blocks in region
+ *   D = data size in blocks
+ *   M = metadata size in blocks
+ *   A = updates accounted for in each metadata block
+ *
+ *   T = D * x + M * y
+ *   y = x / A
+ *   -----------------
+ *   T = D * x + M * x / A = x * (D + M / A)
+ *   T * A = x * (D * A + M)
+ *   x = T * A / (D * A + M)
+ */
+static int allocate_metadata(struct region_file *f, size_t data_blks)
+{
+	size_t t, m;
+	size_t x, y;
+	uint16_t tot_metadata;
+	const size_t a = REGF_UPDATES_PER_METADATA_BLOCK;
+	const size_t d = data_blks;
+
+	t = bytes_to_block(ALIGN_DOWN(region_device_sz(&f->rdev),
+					REGF_BLOCK_GRANULARITY));
+	m = bytes_to_block(ALIGN_UP(REGF_METADATA_BLOCK_SIZE,
+					REGF_BLOCK_GRANULARITY));
+
+	/* Ensure at least one data update can fit with 1 metadata block
+	 * within the region. */
+	if (d > t - m)
+		return -1;
+
+	/* Maximize number of updates by aligning up to the number updates in
+	 * a metadata block. May not really be able to achieve the number of
+	 * updates in practice, but it ensures enough metadata blocks are
+	 * allocated. */
+	x = ALIGN_UP(t * a / (d * a + m), a);
+
+	/* One data block has to fit. */
+	if (x == 0)
+		x = 1;
+
+	/* Now calculate how many metadata blocks are needed. */
+	y = ALIGN_UP(x, a) / a;
+
+	/* Need to commit the metadata allocation. */
+	tot_metadata = m * y;
+	if (rdev_writeat(&f->rdev, &tot_metadata, 0, sizeof(tot_metadata)) < 0)
+		return -1;
+
+	if (rdev_chain(&f->metadata, &f->rdev, 0,
+				block_to_bytes(tot_metadata)))
+		return -1;
+
+	/* Initialize a 0 data block to start appending from. */
+	f->data_blocks[0] = tot_metadata;
+	f->data_blocks[1] = tot_metadata;
+
+	return 0;
+}
+
+static int update_can_fit(const struct region_file *f, size_t data_blks)
+{
+	size_t metadata_slots;
+	size_t end_blk;
+
+	metadata_slots = region_device_sz(&f->metadata) / sizeof(uint16_t);
+
+	/* No more slots. */
+	if ((size_t)f->slot + 1 >= metadata_slots)
+		return 0;
+
+	/* See where the last block lies from the current one. */
+	end_blk = data_blks + region_file_data_end(f);
+
+	/* Update would have exceeded block addressing. */
+	if (end_blk >= REGF_UNALLOCATED_BLOCK)
+		return 0;
+
+	/* End block exceeds size of region. */
+	if (end_blk > bytes_to_block(region_device_sz(&f->rdev)))
+		return 0;
+
+	return 1;
+}
+
+static int commit_data_allocation(struct region_file *f, size_t data_blks)
+{
+	size_t offset;
+
+	f->slot++;
+
+	offset = f->slot * sizeof(uint16_t);
+	f->data_blocks[0] = region_file_data_end(f);
+	f->data_blocks[1] = region_file_data_begin(f) + data_blks;
+
+	if (rdev_writeat(&f->metadata, &f->data_blocks[1], offset,
+				sizeof(f->data_blocks[1])) < 0)
+		return -1;
+
+	return 0;
+}
+
+static int commit_data(const struct region_file *f, const void *buf,
+			size_t size)
+{
+	size_t offset = block_to_bytes(region_file_data_begin(f));
+	if (rdev_writeat(&f->rdev, buf, offset, size) < 0)
+		return -1;
+	return 0;
+}
+
+static int handle_empty(struct region_file *f, size_t data_blks)
+{
+	if (allocate_metadata(f, data_blks)) {
+		printk(BIOS_ERR, "REGF metadata allocation failed: %zd data blocks %zd total blocks\n",
+			data_blks, bytes_to_block(region_device_sz(&f->rdev)));
+		return -1;
+	}
+
+	f->slot = RF_ONLY_METADATA;
+
+	return 0;
+}
+
+static int handle_need_to_empty(struct region_file *f)
+{
+	if (rdev_eraseat(&f->rdev, 0, region_device_sz(&f->rdev)) < 0) {
+		printk(BIOS_ERR, "REGF empty failed.\n");
+		return -1;
+	}
+
+	f->slot = RF_EMPTY;
+
+	return 0;
+}
+
+static int handle_update(struct region_file *f, size_t blocks, const void *buf,
+				size_t size)
+{
+	if (!update_can_fit(f, blocks)) {
+		printk(BIOS_INFO, "REGF update can't fit. Will empty.\n");
+		f->slot = RF_NEED_TO_EMPTY;
+		return 0;
+	}
+
+	if (commit_data_allocation(f, blocks)) {
+		printk(BIOS_ERR, "REGF failed to commit data allocation.\n");
+		return -1;
+	}
+
+	if (commit_data(f, buf, size)) {
+		printk(BIOS_ERR, "REGF failed to commit data.\n");
+		return -1;
+	}
+
+	return 0;
+}
+
+int region_file_update_data(struct region_file *f, const void *buf, size_t size)
+{
+	int ret;
+	size_t blocks;
+
+	blocks = bytes_to_block(ALIGN_UP(size, REGF_BLOCK_GRANULARITY));
+
+	while (1) {
+		int prev_slot = f->slot;
+
+		switch (f->slot) {
+		case RF_EMPTY:
+			ret = handle_empty(f, blocks);
+			break;
+		case RF_NEED_TO_EMPTY:
+			ret = handle_need_to_empty(f);
+			break;
+		case RF_FATAL:
+			ret = -1;
+			break;
+		default:
+			ret = handle_update(f, blocks, buf, size);
+			break;
+		}
+
+		/* Failing case. No more updates allowed to be attempted. */
+		if (ret) {
+			f->slot = RF_FATAL;
+			break;
+		}
+
+		/* No more state changes and data commited. */
+		if (f->slot > RF_ONLY_METADATA && prev_slot != f->slot)
+			break;
+	}
+
+	return ret;
+}