cbfstool: Use cbfs_image API for "locate" command.

To support platforms without top-aligned address mapping like ARM, "locate"
command now outputs platform independent ROM offset by default.  To retrieve x86
style top-aligned virtual address, add "-T".

To test:
	cbfstool coreboot.rom locate -f stage -n stage -a 0x100000 -T
	# Example output: 0xffffdc10

Change-Id: I474703c4197b36524b75407a91faab1194edc64d
Signed-off-by: Hung-Te Lin <hungte@chromium.org>
Reviewed-on: http://review.coreboot.org/2213
Tested-by: build bot (Jenkins)
Reviewed-by: Stefan Reinauer <stefan.reinauer@coreboot.org>

3 files changed, 194 insertions, 8 deletions

diff --git a/util/cbfstool/cbfs_image.c b/util/cbfstool/cbfs_image.c
index f8e2ae71a6..2f38cec0b4 100644
--- a/util/cbfstool/cbfs_image.c
+++ b/util/cbfstool/cbfs_image.c
@@ -359,6 +359,49 @@ int cbfs_print_directory(struct cbfs_image *image) {
 	return 0;
 }
 
+int cbfs_merge_empty_entry(struct cbfs_image *image, struct cbfs_file *entry,
+			   void *arg) {
+	struct cbfs_file *next;
+	uint32_t type, addr, last_addr;
+
+	type = ntohl(entry->type);
+	if (type == CBFS_COMPONENT_DELETED) {
+		// Ready to be recycled.
+		type = CBFS_COMPONENT_NULL;
+		entry->type = htonl(type);
+	}
+	if (type != CBFS_COMPONENT_NULL)
+		return 0;
+
+	next = cbfs_find_next_entry(image, entry);
+
+	while (next && cbfs_is_valid_entry(next)) {
+		type = ntohl(next->type);
+		if (type == CBFS_COMPONENT_DELETED) {
+			type = CBFS_COMPONENT_NULL;
+			next->type = htonl(type);
+		}
+		if (type != CBFS_COMPONENT_NULL)
+			return 0;
+
+		addr = cbfs_get_entry_addr(image, entry);
+		last_addr = cbfs_get_entry_addr(
+				image, cbfs_find_next_entry(image, next));
+
+		// Now, we find two deleted/empty entries; try to merge now.
+		DEBUG("join_empty_entry: combine 0x%x+0x%x and 0x%x+0x%x.\n",
+		      cbfs_get_entry_addr(image, entry), ntohl(entry->len),
+		      cbfs_get_entry_addr(image, next), ntohl(next->len));
+		cbfs_create_empty_entry(image, entry,
+					(last_addr - addr -
+					 cbfs_calculate_file_header_size("")),
+					"");
+		DEBUG("new empty entry: length=0x%x\n", ntohl(entry->len));
+		next = cbfs_find_next_entry(image, entry);
+	}
+	return 0;
+}
+
 int cbfs_walk(struct cbfs_image *image, cbfs_entry_callback callback,
 	      void *arg) {
 	int count = 0;
@@ -435,3 +478,99 @@ int cbfs_is_valid_entry(struct cbfs_file *entry) {
 			       sizeof(entry->magic)) == 0);
 }
 
+int cbfs_create_empty_entry(struct cbfs_image *image, struct cbfs_file *entry,
+		      size_t len, const char *name) {
+	memset(entry, CBFS_CONTENT_DEFAULT_VALUE, sizeof(*entry));
+	memcpy(entry->magic, CBFS_FILE_MAGIC, sizeof(entry->magic));
+	entry->type = htonl(CBFS_COMPONENT_NULL);
+	entry->len = htonl(len);
+	entry->checksum = 0;  // TODO Build a checksum algorithm.
+	entry->offset = htonl(cbfs_calculate_file_header_size(name));
+	memset(CBFS_NAME(entry), 0, ntohl(entry->offset) - sizeof(*entry));
+	strcpy(CBFS_NAME(entry), name);
+	memset(CBFS_SUBHEADER(entry), CBFS_CONTENT_DEFAULT_VALUE, len);
+	return 0;
+}
+
+/* Finds a place to hold whole stage data in same memory page.
+ */
+static int is_in_same_page(uint32_t start, uint32_t size, uint32_t page) {
+	if (!page)
+		return 1;
+	return (start / page) == (start + size - 1) / page;
+}
+
+int32_t cbfs_locate_entry(struct cbfs_image *image, const char *name,
+			  uint32_t size, uint32_t page_size) {
+	struct cbfs_file *entry;
+	size_t need_len;
+	uint32_t addr, addr_next, addr2, addr3, header_len;
+	assert(size < page_size);
+
+	if (page_size % ntohl(image->header->align))
+		WARN("locate_entry: page does not align with CBFS image.\n");
+
+	/* TODO Old cbfstool always assume input is a stage file (and adding
+	 * sizeof(cbfs_stage) for header. We should fix that by adding "-t"
+	 * (type) param in future. For right now, follow old behavior. */
+	header_len = (cbfs_calculate_file_header_size(name) +
+		      sizeof(struct cbfs_stage));
+	need_len = header_len + size;
+
+	// Merge empty entries to build get max available pages.
+	cbfs_walk(image, cbfs_merge_empty_entry, NULL);
+
+	/* Three cases of content location on memory page:
+	 * case 1.
+	 *          |  PAGE 1  |   PAGE 2  |
+	 *          |     <header><content>| Fit. Return start of content.
+	 *
+	 * case 2.
+	 *          |  PAGE 1  |   PAGE 2  |
+	 *          | <header><content>    | Fits when we shift content to align
+	 *  shift-> |  <header>|<content>  | at starting of PAGE 2.
+	 *
+	 * case 3. (large content filling whole page)
+	 *  |  PAGE 1  |   PAGE 2  | PAGE 3|
+	 *  | <header><  content > |       | Can't fit. If we shift content to
+	 *  |       {   free space .       } PAGE 2, header can't fit in free
+	 *  |  shift->     <header><content> space, so we must use PAGE 3.
+	 *
+	 * The returned address will be used to re-link stage file, and then
+	 * assigned to add-stage command (-b), which will be then re-calculated
+	 * by ELF loader and positioned by cbfs_add_entry.
+	 */
+	for (entry = cbfs_find_first_entry(image);
+	     entry && cbfs_is_valid_entry(entry);
+	     entry = cbfs_find_next_entry(image, entry)) {
+
+		uint32_t type = ntohl(entry->type);
+		if (type != CBFS_COMPONENT_NULL)
+			continue;
+
+		addr = cbfs_get_entry_addr(image, entry);
+		addr_next = cbfs_get_entry_addr(image, cbfs_find_next_entry(
+				image, entry));
+		if (addr_next - addr < need_len)
+			continue;
+		if (is_in_same_page(addr + header_len, size, page_size)) {
+			DEBUG("cbfs_locate_entry: FIT (PAGE1).");
+			return addr + header_len;
+		}
+
+		addr2 = align_up(addr, page_size);
+		if (addr2 < addr_next && addr_next - addr2 >= size &&
+		    addr2 - addr >= header_len) {
+			DEBUG("cbfs_locate_entry: OVERLAP (PAGE2).");
+			return addr2;
+		}
+
+		addr3 = addr2 + page_size;
+		if (addr3 < addr_next && addr_next - addr3 >= size &&
+		    addr3 - addr >= header_len) {
+			DEBUG("cbfs_locate_entry: OVERLAP+ (PAGE3).");
+			return addr3;
+		}
+	}
+	return -1;
+}
diff --git a/util/cbfstool/cbfs_image.h b/util/cbfstool/cbfs_image.h
index 73b262da18..d99bee851e 100644
--- a/util/cbfstool/cbfs_image.h
+++ b/util/cbfstool/cbfs_image.h
@@ -49,6 +49,16 @@ int cbfs_export_entry(struct cbfs_image *image, const char *entry_name,
 /* Removes an entry from CBFS image. Returns 0 on success, otherwise non-zero. */
 int cbfs_remove_entry(struct cbfs_image *image, const char *name);
 
+/* Initializes a new empty (type = NULL) entry with size and name in CBFS image.
+ * Returns 0 on success, otherwise (ex, not found) non-zero. */
+int cbfs_create_empty_entry(struct cbfs_image *image, struct cbfs_file *entry,
+			    size_t len, const char *name);
+
+/* Finds a location to put given content in same memory page.
+ * Returns a valid offset, or -1 on failure. */
+int32_t cbfs_locate_entry(struct cbfs_image *image, const char *name,
+			  uint32_t size, uint32_t page_size);
+
 /* Callback function used by cbfs_walk.
  * Returns 0 on success, or non-zero to stop further iteration. */
 typedef int (*cbfs_entry_callback)(struct cbfs_image *image,
@@ -90,4 +100,9 @@ int cbfs_print_header_info(struct cbfs_image *image);
 int cbfs_print_entry_info(struct cbfs_image *image, struct cbfs_file *entry,
 			  void *arg);
 
+/* Merge empty entries starting from given entry.
+ * Returns 0 on success, otherwise non-zero. */
+int cbfs_merge_empty_entry(struct cbfs_image *image, struct cbfs_file *entry,
+			   void *arg);
+
 #endif
diff --git a/util/cbfstool/cbfstool.c b/util/cbfstool/cbfstool.c
index e653a33bd5..98f6b62ee7 100644
--- a/util/cbfstool/cbfstool.c
+++ b/util/cbfstool/cbfstool.c
@@ -48,6 +48,7 @@ static struct param {
 	uint32_t size;
 	uint32_t alignment;
 	uint32_t offset;
+	uint32_t top_aligned;
 	comp_algo algo;
 } param = {
 	/* All variables not listed are initialized as zero. */
@@ -363,7 +364,9 @@ static int cbfs_create(void)
 
 static int cbfs_locate(void)
 {
-	uint32_t filesize, location;
+	struct cbfs_image image;
+	struct buffer buffer;
+	int32_t address;
 
 	if (!param.filename) {
 		ERROR("You need to specify -f/--filename.\n");
@@ -375,13 +378,37 @@ static int cbfs_locate(void)
 		return 1;
 	}
 
-	filesize = getfilesize(param.filename);
+	if (cbfs_image_from_file(&image, param.cbfs_name) != 0) {
+		ERROR("Failed to load %s.\n", param.cbfs_name);
+		return 1;
+	}
+
+	if (cbfs_get_entry(&image, param.name))
+		WARN("'%s' already in CBFS.\n", param.name);
+
+	if (buffer_from_file(&buffer, param.filename) != 0) {
+		ERROR("Cannot load %s.\n", param.filename);
+		cbfs_image_delete(&image);
+		return 1;
+	}
 
-	location = cbfs_find_location(param.cbfs_name, filesize,
-					param.name, param.alignment);
+	address = cbfs_locate_entry(&image, param.name, buffer.size,
+				    param.alignment);
+	buffer_delete(&buffer);
 
-	printf("0x%x\n", location);
-	return location == 0 ? 1 : 0;
+	if (address == -1) {
+		ERROR("'%s' can't fit in CBFS for align 0x%x.\n",
+		      param.name, param.alignment);
+		cbfs_image_delete(&image);
+		return 1;
+	}
+
+	if (param.top_aligned)
+		address = address - ntohl(image.header->romsize);
+
+	cbfs_image_delete(&image);
+	printf("0x%x\n", address);
+	return 0;
 }
 
 static int cbfs_print(void)
@@ -432,7 +459,7 @@ static const struct command commands[] = {
 	{"add-flat-binary", "f:n:l:e:c:b:vh?", cbfs_add_flat_binary},
 	{"remove", "n:vh?", cbfs_remove},
 	{"create", "s:B:a:o:m:vh?", cbfs_create},
-	{"locate", "f:n:a:vh?", cbfs_locate},
+	{"locate", "f:n:a:Tvh?", cbfs_locate},
 	{"print", "vh?", cbfs_print},
 	{"extract", "n:f:vh?", cbfs_extract},
 };
@@ -443,6 +470,7 @@ static struct option long_options[] = {
 	{"compression",  required_argument, 0, 'c' },
 	{"base-address", required_argument, 0, 'b' },
 	{"load-address", required_argument, 0, 'l' },
+	{"top-aligned",  required_argument, 0, 'T' },
 	{"entry-point",  required_argument, 0, 'e' },
 	{"size",         required_argument, 0, 's' },
 	{"bootblock",    required_argument, 0, 'B' },
@@ -461,6 +489,7 @@ static void usage(char *name)
 	    ("cbfstool: Management utility for CBFS formatted ROM images\n\n"
 	     "USAGE:\n" " %s [-h]\n"
 	     " %s FILE COMMAND [-v] [PARAMETERS]...\n\n" "OPTIONs:\n"
+	     "  -T              Output top-aligned memory address\n"
 	     "  -v              Provide verbose output\n"
 	     "  -h              Display this help message\n\n"
 	     "COMMANDs:\n"
@@ -477,7 +506,7 @@ static void usage(char *name)
 			"Remove a component\n"
 	     " create -s size -B bootblock -m ARCH [-a align] [-o offset]  "
 			"Create a ROM file\n"
-	     " locate -f FILE -n NAME -a align                             "
+	     " locate -f FILE -n NAME [-a align] [-T]                      "
 			"Find a place for a file of that size\n"
 	     " print                                                       "
 			"Show the contents of the ROM\n"
@@ -578,6 +607,9 @@ int main(int argc, char **argv)
 			case 'f':
 				param.filename = optarg;
 				break;
+			case 'T':
+				param.top_aligned = 1;
+				break;
 			case 'v':
 				verbose++;
 				break;