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 0000000000..f54b6631af
--- /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 e5aa852617..b61b956524 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 aaee62f4c3..64dcf9f5ba 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_ */