util/cbfstool: add 'compact' command

While assembling CBFS images within the RW slots on Chrome OS
machines the current approach is to 'cbfstool copy' from the
RO CBFS to each RW CBFS. Additional fixups are required such
as removing unneeded files from the RW CBFS (e.g. verstage)
as well as removing and adding back files with the proper
arguments (FSP relocation as well as romstage XIP relocation).
This ends up leaving holes in the RW CBFS. To speed up RW
CBFS slot hashing it's beneficial to pack all non-empty files
together at the beginning of the CBFS. Therefore, provide
the 'compact' command which bubbles all the empty entries to
the end of the CBFS.

Change-Id: I8311172d71a2ccfccab384f8286cf9f21a17dec9
Signed-off-by: Aaron Durbin <adurbin@chromium.org>
Reviewed-on: https://review.coreboot.org/13479
Tested-by: build bot (Jenkins)
Reviewed-by: Patrick Georgi <pgeorgi@google.com>

3 files changed, 138 insertions, 0 deletions

diff --git a/util/cbfstool/cbfs_image.c b/util/cbfstool/cbfs_image.c
index 64266b0b5a..314ea5741d 100644
--- a/util/cbfstool/cbfs_image.c
+++ b/util/cbfstool/cbfs_image.c
@@ -441,6 +441,127 @@ int cbfs_copy_instance(struct cbfs_image *image, struct buffer *dst)
 	return 0;
 }
 
+static size_t cbfs_file_entry_metadata_size(const struct cbfs_file *f)
+{
+	return ntohl(f->offset);
+}
+
+static size_t cbfs_file_entry_data_size(const struct cbfs_file *f)
+{
+	return ntohl(f->len);
+}
+
+static size_t cbfs_file_entry_size(const struct cbfs_file *f)
+{
+	return cbfs_file_entry_metadata_size(f) + cbfs_file_entry_data_size(f);
+}
+
+int cbfs_compact_instance(struct cbfs_image *image)
+{
+	assert(image);
+
+	struct cbfs_file *prev;
+	struct cbfs_file *cur;
+
+	/* The prev entry will always be an empty entry. */
+	prev = NULL;
+
+	/*
+	 * Note: this function does not honor alignment or fixed location files.
+	 * It's behavior is akin to cbfs_copy_instance() in that it expects
+	 * the caller to understand the ramifications of compacting a
+	 * fragmented CBFS image.
+	 */
+
+	for (cur = cbfs_find_first_entry(image);
+	     cur && cbfs_is_valid_entry(image, cur);
+	     cur = cbfs_find_next_entry(image, cur)) {
+		size_t prev_size;
+		size_t cur_size;
+		size_t empty_metadata_size;
+		size_t spill_size;
+		uint32_t type = htonl(cur->type);
+
+		/* Current entry is empty. Kepp track of it. */
+		if ((type == htonl(CBFS_COMPONENT_NULL)) ||
+		    (type == htonl(CBFS_COMPONENT_DELETED))) {
+			prev = cur;
+			continue;
+		}
+
+		/* Need to ensure the previous entry is an empty one. */
+		if (prev == NULL)
+			continue;
+
+		/* At this point prev is an empty entry. Put the non-empty
+		 * file in prev's location. Then add a new emptry entry. This
+		 * essentialy bubbles empty entries towards the end. */
+
+		prev_size = cbfs_file_entry_size(prev);
+		cur_size = cbfs_file_entry_size(cur);
+
+		/*
+		 * Adjust the empty file size by the actual space occupied
+		 * bewtween the beginning of the empty file and the non-empty
+		 * file.
+		 */
+		prev_size += (cbfs_get_entry_addr(image, cur) -
+				cbfs_get_entry_addr(image, prev)) - prev_size;
+
+		/* Move the non-empty file over the empty file. */
+		memmove(prev, cur, cur_size);
+
+		/*
+		 * Get location of the empty file. Note that since prev was
+		 * overwritten with the non-empty file the previously moved
+		 * file needs to be used to calculate the empty file's location.
+		 */
+		cur = cbfs_find_next_entry(image, prev);
+
+		/*
+		 * The total space to work with for swapping the 2 entries
+		 * consists of the 2 files' sizes combined. However, the
+		 * cbfs_file entries start on CBFS_ALIGNMENT boundaries.
+		 * Because of this the empty file size may end up smaller
+		 * because of the non-empty file's metadata and data length.
+		 *
+		 * Calculate the spill size which is the amount of data lost
+		 * due to the alignment constraints after moving the non-empty
+		 * file.
+		 */
+		spill_size = (cbfs_get_entry_addr(image, cur) -
+				cbfs_get_entry_addr(image, prev)) - cur_size;
+
+		empty_metadata_size = cbfs_calculate_file_header_size("");
+
+		/* Check if new empty size can contain the metadata. */
+		if (empty_metadata_size + spill_size > prev_size) {
+			ERROR("Unable to swap '%s' with prev empty entry.\n",
+				prev->filename);
+			return 1;
+		}
+
+		/* Update the empty file's size. */
+		prev_size -= spill_size + empty_metadata_size;
+
+		/* Create new empty file. */
+		cbfs_create_empty_entry(cur, CBFS_COMPONENT_NULL,
+					prev_size, "");
+
+		/* Merge any potential empty entries together. */
+		cbfs_walk(image, cbfs_merge_empty_entry, NULL);
+
+		/*
+		 * Since current switched to an empty file keep track of it.
+		 * Even if any empty files were merged the empty entry still
+		 * starts at previously calculated location.
+		 */
+		prev = cur;
+	}
+
+	return 0;
+}
+
 int cbfs_image_delete(struct cbfs_image *image)
 {
 	if (image == NULL)
diff --git a/util/cbfstool/cbfs_image.h b/util/cbfstool/cbfs_image.h
index 38510d2cfc..0d7877a7cc 100644
--- a/util/cbfstool/cbfs_image.h
+++ b/util/cbfstool/cbfs_image.h
@@ -76,6 +76,10 @@ int cbfs_image_from_buffer(struct cbfs_image *out, struct buffer *in,
  * Will not succeed on new-style images without a master header. */
 int cbfs_copy_instance(struct cbfs_image *image, struct buffer *dst);
 
+/* Compact a fragmented CBFS image by placing all the non-empty files at the
+ * beginning of the image. Returns 0 on success, otherwise non-zero.  */
+int cbfs_compact_instance(struct cbfs_image *image);
+
 /* Releases the CBFS image. Returns 0 on success, otherwise non-zero. */
 int cbfs_image_delete(struct cbfs_image *image);
 
diff --git a/util/cbfstool/cbfstool.c b/util/cbfstool/cbfstool.c
index 13a9956045..5be2d6549c 100644
--- a/util/cbfstool/cbfstool.c
+++ b/util/cbfstool/cbfstool.c
@@ -1054,6 +1054,16 @@ static int cbfs_copy(void)
 	return cbfs_copy_instance(&src_image, param.image_region);
 }
 
+static int cbfs_compact(void)
+{
+	struct cbfs_image image;
+	if (cbfs_image_from_buffer(&image, param.image_region,
+							param.headeroffset))
+		return 1;
+	WARN("Compacting a CBFS doesn't honor alignment or fixed addresses!\n");
+	return cbfs_compact_instance(&image);
+}
+
 static const struct command commands[] = {
 	{"add", "H:r:f:n:t:c:b:a:vA:gh?", cbfs_add, true, true},
 	{"add-flat-binary", "H:r:f:n:l:e:c:b:vA:gh?", cbfs_add_flat_binary,
@@ -1064,6 +1074,7 @@ static const struct command commands[] = {
 				true, true},
 	{"add-int", "H:r:i:n:b:vgh?", cbfs_add_integer, true, true},
 	{"add-master-header", "H:r:vh?", cbfs_add_master_header, true, true},
+	{"compact", "r:h?", cbfs_compact, true, true},
 	{"copy", "r:R:h?", cbfs_copy, true, true},
 	{"create", "M:r:s:B:b:H:o:m:vh?", cbfs_create, true, true},
 	{"hashcbfs", "r:R:A:vh?", cbfs_hash, true, true},
@@ -1198,6 +1209,8 @@ static void usage(char *name)
 			"Add a legacy CBFS master header\n"
 	     " remove [-r image,regions] -n NAME                           "
 			"Remove a component\n"
+	     " compact -r image,regions                                    "
+			"Defragment CBFS image.\n"
 	     " copy -r image,regions -R source-region                      "
 			"Create a copy (duplicate) cbfs instance in fmap\n"
 	     " create -m ARCH -s size [-b bootblock offset] \\\n"