summaryrefslogtreecommitdiff
path: root/src/lib/region_file.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/region_file.c')
-rw-r--r--src/lib/region_file.c474
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;
+}