cbfs: Add metadata cache

This patch adds a new CBFS "mcache" (metadata cache) -- a memory buffer
that stores the headers of all CBFS files. Similar to the existing FMAP
cache, this cache should reduce the amount of SPI accesses we need to do
every boot: rather than having to re-read all CBFS headers from SPI
flash every time we're looking for a file, we can just walk the same
list in this in-memory copy and finally use it to directly access the
flash at the right position for the file data.

This patch adds the code to support the cache but doesn't enable it on
any platform. The next one will turn it on by default.

Change-Id: I5b1084bfdad1c6ab0ee1b143ed8dd796827f4c65
Signed-off-by: Julius Werner <jwerner@chromium.org>
Reviewed-on: https://review.coreboot.org/c/coreboot/+/38423
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Aaron Durbin <adurbin@chromium.org>

3 files changed, 165 insertions, 0 deletions

diff --git a/src/commonlib/bsd/cbfs_mcache.c b/src/commonlib/bsd/cbfs_mcache.c
new file mode 100644
index 000000000000..f54b6631afd5
--- /dev/null
+++ b/src/commonlib/bsd/cbfs_mcache.c
@@ -0,0 +1,143 @@
+/* SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-or-later */
+
+#include <assert.h>
+#include <commonlib/bsd/cbfs_private.h>
+
+/*
+ * A CBFS metadata cache is an in memory data structure storing CBFS file headers (= metadata).
+ * It is defined by its start pointer and size. It contains a sequence of variable-length
+ * union mcache_entry entries. There is no overall header structure for the cache.
+ *
+ * Each mcache_entry is the raw metadata for a CBFS file (including attributes) in the same form
+ * as stored on flash (i.e. values in big-endian), except that the CBFS magic signature in the
+ * first 8 bytes ('LARCHIVE') is overwritten with mcache-internal bookkeeping data. The first 4
+ * bytes are a magic number (MCACHE_MAGIC_FILE) and the next 4 bytes are the absolute offset in
+ * bytes on the cbfs_dev_t that this metadata blob was found at. (Note that depending on the
+ * implementation of cbfs_dev_t, this offset may still be relative to the start of a subregion
+ * of the underlying storage device.)
+ *
+ * The length of an mcache_entry (i.e. length of the underlying metadata blob) is encoded in the
+ * metadata (entry->file.h.offset). The next mcache_entry begins at the next
+ * CBFS_MCACHE_ALIGNMENT boundary after that. The cache is terminated by a special 4-byte
+ * mcache_entry that consists only of a magic number (MCACHE_MAGIC_END or MCACHE_MAGIC_FULL).
+ */
+
+#define MCACHE_MAGIC_FILE	0x454c4946	/* 'FILE' */
+#define MCACHE_MAGIC_FULL	0x4c4c5546	/* 'FULL' */
+#define MCACHE_MAGIC_END	0x444e4524	/* '$END' */
+
+union mcache_entry {
+	union cbfs_mdata file;
+	struct {	/* These fields exactly overlap file.h.magic */
+		uint32_t magic;
+		uint32_t offset;
+	};
+};
+
+struct cbfs_mcache_build_args {
+	void *mcache;
+	void *end;
+	int count;
+};
+
+static cb_err_t build_walker(cbfs_dev_t dev, size_t offset, const union cbfs_mdata *mdata,
+			     size_t already_read, void *arg)
+{
+	struct cbfs_mcache_build_args *args = arg;
+	union mcache_entry *entry = args->mcache;
+	const uint32_t data_offset = be32toh(mdata->h.offset);
+
+	if (args->end - args->mcache < data_offset)
+		return CB_CBFS_CACHE_FULL;
+
+	if (cbfs_copy_fill_metadata(args->mcache, mdata, already_read, dev, offset))
+		return CB_CBFS_IO;
+
+	entry->magic = MCACHE_MAGIC_FILE;
+	entry->offset = offset;
+
+	args->mcache += ALIGN_UP(data_offset, CBFS_MCACHE_ALIGNMENT);
+	args->count++;
+
+	return CB_CBFS_NOT_FOUND;
+}
+
+cb_err_t cbfs_mcache_build(cbfs_dev_t dev, void *mcache, size_t size,
+			   struct vb2_hash *metadata_hash)
+{
+	struct cbfs_mcache_build_args args = {
+		.mcache = mcache,
+		.end = mcache + ALIGN_DOWN(size, CBFS_MCACHE_ALIGNMENT)
+		       - sizeof(uint32_t), /* leave space for terminating magic */
+		.count = 0,
+	};
+
+	assert(size > sizeof(uint32_t) && IS_ALIGNED((uintptr_t)mcache, CBFS_MCACHE_ALIGNMENT));
+	cb_err_t ret = cbfs_walk(dev, build_walker, &args, metadata_hash, 0);
+	union mcache_entry *entry = args.mcache;
+	if (ret == CB_CBFS_NOT_FOUND) {
+		ret = CB_SUCCESS;
+		entry->magic = MCACHE_MAGIC_END;
+	} else if (ret == CB_CBFS_CACHE_FULL) {
+		ERROR("mcache overflow, should increase CBFS_MCACHE size!\n");
+		entry->magic = MCACHE_MAGIC_FULL;
+	}
+
+	LOG("mcache @%p built for %d files, used %#zx of %#zx bytes\n", mcache,
+	    args.count, args.mcache + sizeof(entry->magic) - mcache, size);
+	return ret;
+}
+
+cb_err_t cbfs_mcache_lookup(const void *mcache, size_t mcache_size, const char *name,
+			    union cbfs_mdata *mdata_out, size_t *data_offset_out)
+{
+	const size_t namesize = strlen(name) + 1; /* Count trailing \0 so we can memcmp() it. */
+	const void *end = mcache + mcache_size;
+	const void *current = mcache;
+
+	while (current + sizeof(uint32_t) < end) {
+		const union mcache_entry *entry = current;
+
+		if (entry->magic == MCACHE_MAGIC_END)
+			return CB_CBFS_NOT_FOUND;
+		if (entry->magic == MCACHE_MAGIC_FULL)
+			return CB_CBFS_CACHE_FULL;
+
+		assert(entry->magic == MCACHE_MAGIC_FILE);
+		const uint32_t data_offset = be32toh(entry->file.h.offset);
+		const uint32_t data_length = be32toh(entry->file.h.len);
+		if (namesize <= data_offset - offsetof(union cbfs_mdata, filename) &&
+		    memcmp(name, entry->file.filename, namesize) == 0) {
+			LOG("Found '%s' @%#x size %#x in mcache @%p\n",
+			    name, entry->offset, data_length, current);
+			*data_offset_out = entry->offset + data_offset;
+			memcpy(mdata_out, &entry->file, data_offset);
+			return CB_SUCCESS;
+		}
+
+		current += ALIGN_UP(data_offset, CBFS_MCACHE_ALIGNMENT);
+	}
+
+	ERROR("CBFS mcache overflow!\n");
+	return CB_ERR;
+}
+
+size_t cbfs_mcache_real_size(const void *mcache, size_t mcache_size)
+{
+	const void *end = mcache + mcache_size;
+	const void *current = mcache;
+
+	while (current + sizeof(uint32_t) < end) {
+		const union mcache_entry *entry = current;
+
+		if (entry->magic == MCACHE_MAGIC_FULL || entry->magic == MCACHE_MAGIC_END) {
+			current += sizeof(entry->magic);
+			break;
+		}
+
+		assert(entry->magic == MCACHE_MAGIC_FILE);
+		current += ALIGN_UP(be32toh(entry->file.h.offset), CBFS_MCACHE_ALIGNMENT);
+	}
+
+	return current - mcache;
+}
diff --git a/src/commonlib/bsd/include/commonlib/bsd/cb_err.h b/src/commonlib/bsd/include/commonlib/bsd/cb_err.h
index e5aa852617b1..b61b956524ad 100644
--- a/src/commonlib/bsd/include/commonlib/bsd/cb_err.h
+++ b/src/commonlib/bsd/include/commonlib/bsd/cb_err.h
@@ -39,6 +39,7 @@ enum cb_err {
 	CB_CBFS_IO		= -400, /**< Underlying I/O error */
 	CB_CBFS_NOT_FOUND	= -401, /**< File not found in directory */
 	CB_CBFS_HASH_MISMATCH	= -402, /**< Master hash validation failed */
+	CB_CBFS_CACHE_FULL	= -403, /**< Metadata cache overflowed */
 };
 
 /* Don't typedef the enum directly, so the size is unambiguous for serialization. */
diff --git a/src/commonlib/bsd/include/commonlib/bsd/cbfs_private.h b/src/commonlib/bsd/include/commonlib/bsd/cbfs_private.h
index aaee62f4c3c8..64dcf9f5bac8 100644
--- a/src/commonlib/bsd/include/commonlib/bsd/cbfs_private.h
+++ b/src/commonlib/bsd/include/commonlib/bsd/cbfs_private.h
@@ -113,4 +113,25 @@ cb_err_t cbfs_copy_fill_metadata(union cbfs_mdata *dst, const union cbfs_mdata *
 cb_err_t cbfs_lookup(cbfs_dev_t dev, const char *name, union cbfs_mdata *mdata_out,
 		     size_t *data_offset_out, struct vb2_hash *metadata_hash);
 
+/* Both base address and size of CBFS mcaches must be aligned to this value! */
+#define CBFS_MCACHE_ALIGNMENT	sizeof(uint32_t)	/* Largest data type used in CBFS */
+
+/* Build an in-memory CBFS metadata cache out of the CBFS on |dev| into a |mcache_size| bytes
+ * memory area at |mcache|. Also verify |metadata_hash| unless it is NULL. If this returns
+ * CB_CBFS_CACHE_FULL, the mcache is still valid and can be used, but lookups may return
+ * CB_CBFS_CACHE_FULL for files that didn't fit to indicate that the caller needs to fall back
+ * to cbfs_lookup(). */
+cb_err_t cbfs_mcache_build(cbfs_dev_t dev, void *mcache, size_t mcache_size,
+			   struct vb2_hash *metadata_hash);
+
+/*
+ * Find a file named |name| in a CBFS metadata cache and copy its metadata into |mdata_out|.
+ * Pass out offset to the file data (on the original CBFS device used for cbfs_mcache_build()).
+ */
+cb_err_t cbfs_mcache_lookup(const void *mcache, size_t mcache_size, const char *name,
+			    union cbfs_mdata *mdata_out, size_t *data_offset_out);
+
+/* Returns the amount of bytes actually used by the CBFS metadata cache in |mcache|. */
+size_t cbfs_mcache_real_size(const void *mcache, size_t mcache_size);
+
 #endif	/* _COMMONLIB_BSD_CBFS_PRIVATE_H_ */