I have made a very simple mod to cbfstool that is compatible with the

src/lib/ code in coreboot. I.e. the tool changes but the coreboot code
does not.

Currently, as cbfstool manages the ROM, there are files and empty
space. To allocate files, the code does, first, a walk of the headers
and, if that fails, does a brute-force search of the rest of the
space.

We all agree that the brute-force search has lots of problems from a
performance and correctness standpoint.

I've made a slight change. Instead of an "empty space" area with no
valid headers, I've made a header for the empty space.

So cbfs creation looks like this:
- set up the boot block
- create a file, of type CBFS_COMPONENT_NULL, that contains the empty
space. CBFS_COMPONENT_NULL was already defined in cbfs.h

Here's an example:

[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs create 1048576 2048
(cbfstool) E: Unable to open (null): Bad address
[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs print
testcbfs: 1024 kB, bootblocksize 2048, romsize 1048576, offset 0x0
Alignment: 16 bytes

Name                           Offset     Type         Size
                              0x0        0xffffffff   1046456

So how do we create a new file?

It's easy: walk the files and find a file of type CBFS_COMPONENT_NULL,
which is as large
or larger than the file you are trying to create. Then you use that file.
- if the file is the same size as the NULL file, then it's easy: take it
- if the file is smaller than the NULL file, you split the NULL file
into two parts.

note that this works in the base case: the base case is that the whole
storage is CBFS_COMPONENT_NULL.

Here's an example of adding a file.
[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs add-stage testfixed t
[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs print
testcbfs: 1024 kB, bootblocksize 2048, romsize 1048576, offset 0x0
Alignment: 16 bytes

Name                           Offset     Type         Size
t                              0x0        stage        23176
                              0x5ab0     0xffffffff   1023240

Note that the NULL split and got smaller. But the entire ROM is still
contained by the two files. To walk this entire rom will require two
FLASH accesses.

Add another file:
[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs add-stage testfixed tt
[rminnich@xcpu2 cbfstool]$ ./cbfstool testcbfs print
testcbfs: 1024 kB, bootblocksize 2048, romsize 1048576, offset 0x0
Alignment: 16 bytes

Name                           Offset     Type         Size
t                              0x0        stage        23176
tt                             0x5ab0     stage        23176
                              0xb560     0xffffffff   1000024
[rminnich@xcpu2 cbfstool]$

So, taking current ROMs as an example, I can reduce FLASH accesses for
cbfs from (potentially) thousands to (typically) less than 10.

Index: fs.c
Changes for readability and cleanliness. Move common blobs of code to functions. 
New function: rom_alloc,which allocates files by finding NULL files and using/splitting. 
Other changes as needed to support this usage. 
Index: util.c
Creating a cbfs archive now requires creation of a NULL file covering the file system space. 
Index: cbfs.h
Add a DELETED file type with value 0. Any file can be marked deleted by zero its type; this is a 
FLASH-friendly definition for all known FLASH types. 

Signed-off-by: Ronald G. Minnich <rminnich@gmail.com>

I think it is a step in the right direction.  Could you add the
function prototype to cbfstool.h?

Acked-by: Myles Watson <mylesgw@gmail.com>
(I added the prototype)




git-svn-id: svn://svn.coreboot.org/coreboot/trunk@4261 2b7e53f0-3cfb-0310-b3e9-8179ed1497e1

4 files changed, 177 insertions, 59 deletions

diff --git a/util/cbfstool/cbfs.h b/util/cbfstool/cbfs.h
index 95159ebaa8..04a12fc24a 100644
--- a/util/cbfstool/cbfs.h
+++ b/util/cbfstool/cbfs.h
@@ -38,6 +38,16 @@
 #define CBFS_COMPONENT_PAYLOAD   0x20
 #define CBFS_COMPONENT_OPTIONROM 0x30
 
+/* The deleted type is chosen to be a value
+ * that can be written in a FLASH from all other
+ * values. 
+ */
+#define CBFS_COMPONENT_DELETED 0
+
+/* for all known FLASH, this value can be changed 
+ * to all other values. This allows NULL files to be 
+ * changed without a block erase
+ */
 #define CBFS_COMPONENT_NULL 0xFFFFFFFF
 
 /** this is the master cbfs header - it need to be
diff --git a/util/cbfstool/cbfstool.h b/util/cbfstool/cbfstool.h
index 289b4812ab..51abd29b58 100644
--- a/util/cbfstool/cbfstool.h
+++ b/util/cbfstool/cbfstool.h
@@ -71,6 +71,8 @@ struct cbfs_file *rom_find(struct rom *rom, unsigned int offset);
 struct cbfs_file *rom_find_first(struct rom *);
 struct cbfs_file *rom_find_next(struct rom *, struct cbfs_file *);
 int rom_add(struct rom *rom, const char *name, void *, int size, int type);
+int rom_set_header(struct rom *rom, struct cbfs_file *c, 
+	const char*name, int size, int type);
 int rom_extract(struct rom *rom, const char *name, void **buf, unsigned long *size);
 int rom_remove(struct rom *rom, const char *name);
 unsigned int rom_used_space(struct rom *rom);
diff --git a/util/cbfstool/fs.c b/util/cbfstool/fs.c
index ff5741e37e..8292163961 100644
--- a/util/cbfstool/fs.c
+++ b/util/cbfstool/fs.c
@@ -18,8 +18,140 @@
  */
 
 #include <string.h>
+#include <stdlib.h>
 #include "cbfstool.h"
 
+int namelen(const char *name)
+{
+	return ALIGN(strlen(name) + 1, 16);
+}
+
+/**
+ * Given a name, return the header size for that name. 
+ * @param name The name
+ * @returns The header size given that name
+ */
+int headersize(const char *name)
+{
+	return sizeof(struct cbfs_file) + namelen(name);
+}
+
+/**
+ * Given a name, set it into the header in a standard way
+ * @param file the cbfs file
+ * @param name The name
+ */
+void setname(struct cbfs_file *file, const char *name)
+{
+	memset(CBFS_NAME(file), 0, namelen(name));
+	strcpy((char *)CBFS_NAME(file), name);
+}
+
+/**
+ * Given a name, size, and type, set them into the header in a standard way. 
+ * Special case of size of -1: set the size to all of ROM
+ * @param rom The rom
+ * @param c The cbfs file
+ * @param name The name
+ * @param size The size
+ * @param type The type
+ * @returns Always 0 for now
+ */
+int rom_set_header(struct rom *rom, struct cbfs_file *c, const char *name, int size, int type)
+{
+	unsigned int csize;
+	csize = headersize(name);
+
+	strcpy(c->magic, COMPONENT_MAGIC);
+
+	/* special case -- if size is -1, means "as much as you can"
+	 * it's usually only used in init. 
+	 */
+	if (size < 0)
+		size = rom->fssize - csize;
+	c->len = htonl(size);
+	c->offset = htonl(csize);
+	c->type = htonl(type);
+
+	setname(c, name);
+	return 0;
+}
+
+int nextfile(struct rom *rom, struct cbfs_file *c, int offset)
+{
+	return ALIGN(offset + ntohl(c->len),
+					ntohl(rom->header->align));
+}
+
+/**
+ * rom_alloc
+ * Given a rom, walk the headers and find the first header of type 
+ * CBFS_COMPONENT_NULL that is >= the desired size. 
+ * If the CBFS_COMPONENT_NULL is 'align' bytes > size, 
+ * create a new header of CBFS_COMPONENT_NULL following the file. 
+ * The 'len' structure member of the desired file is initialized, but 
+ * nothing else is. 
+ * @param rom The rom
+ * @param size the size of the file needed
+ * @returns pointer to a cbfs_file struct. 
+ */
+struct cbfs_file * rom_alloc(struct rom *rom, unsigned long size)
+{
+	/* walk the rom and find an empty file with a base > base, and a large enough size */
+	unsigned int offset = ntohl(rom->header->offset);
+	unsigned int ret = -1;
+	struct cbfs_file *c = NULL;
+	unsigned long nextoffset, truncoffset;
+	struct cbfs_file *newfile = NULL;
+
+	while (offset < rom->fssize) {
+
+		c = (struct cbfs_file *)ROM_PTR(rom, offset);
+
+		if (!strcmp(c->magic, COMPONENT_MAGIC)) {
+			if (c->type != CBFS_COMPONENT_NULL) {
+				offset += ALIGN(ntohl(c->offset) + ntohl(c->len),
+					ntohl(rom->header->align));
+				continue;
+		}
+			/* Is this file big enough for our needs? */
+			if (ntohl(c->len) >= size){
+				ret = offset;
+				break;
+			}
+			offset += ALIGN(ntohl(c->offset) + ntohl(c->len),
+					ntohl(rom->header->align));
+		} else {
+			fprintf(stderr, "Corrupt rom -- found no header at %d\n", offset);
+			exit(1);
+		}
+	}
+
+	if (ret < 0)
+		return NULL;
+
+	/* figure out the real end of this file, and hence the size */
+	/* compute where the next file is */
+	nextoffset = ALIGN(ret + ntohl(c->len) + headersize((char *)CBFS_NAME(c)),
+				ntohl(rom->header->align));
+	/* compute where the end of this new file might be */
+	truncoffset = ALIGN(ret + size + headersize((char *)CBFS_NAME(c)),
+				ntohl(rom->header->align));
+	/* If there is more than align bytes difference, create a new empty file */
+	/* later, we can add code to merge all empty files. */
+	if (nextoffset - truncoffset > ntohl(rom->header->align)) {
+		unsigned int csize;
+		csize = headersize("");
+		newfile = (struct cbfs_file *)ROM_PTR(rom, truncoffset);
+		rom_set_header(rom, newfile, "", 
+			nextoffset - truncoffset - csize, CBFS_COMPONENT_NULL);
+	} else truncoffset = nextoffset;
+
+	c->len = htonl(size);
+
+	return ((struct cbfs_file *)ROM_PTR(rom, ret));
+}
+
 struct cbfs_file *rom_find(struct rom *rom, unsigned int offset)
 {
 	while (offset < rom->fssize) {
@@ -49,29 +181,6 @@ struct cbfs_file *rom_find_next(struct rom *rom, struct cbfs_file *prev)
 			      ntohl(rom->header->align)));
 }
 
-struct cbfs_file *rom_find_empty(struct rom *rom)
-{
-	unsigned int offset = ntohl(rom->header->offset);
-	unsigned int ret = ntohl(rom->header->offset);
-
-	while (offset < rom->fssize) {
-
-		struct cbfs_file *c =
-		    (struct cbfs_file *)ROM_PTR(rom, offset);
-
-		if (!strcmp(c->magic, COMPONENT_MAGIC)) {
-			offset += ALIGN(ntohl(c->offset) + ntohl(c->len),
-					ntohl(rom->header->align));
-
-			ret = offset;
-		} else
-			offset += ntohl(rom->header->align);
-	}
-
-	return (ret < rom->fssize) ?
-	    (struct cbfs_file *)ROM_PTR(rom, ret) : NULL;
-}
-
 struct cbfs_file *rom_find_by_name(struct rom *rom, const char *name)
 {
 	struct cbfs_file *c = rom_find_first(rom);
@@ -92,43 +201,36 @@ unsigned int rom_used_space(struct rom *rom)
 	unsigned int ret = 0;
 
 	while (c) {
-		ret = ROM_OFFSET(rom, c) + ntohl(c->offset) + ntohl(c->len);
+		int type;
+		type = ntohl(c->type);
+		if ((c->type == CBFS_COMPONENT_DELETED) ||
+			(c->type == CBFS_COMPONENT_NULL))
+			continue;
+		ret += ROM_OFFSET(rom, c) + ntohl(c->offset) + ntohl(c->len);
 		c = rom_find_next(rom, c);
 	}
 
 	return ret;
 }
 
+/** 
+ * delete an item. This is a flash-friendly version -- it just blows the 
+ * type to 0. Nothing else is changed. 
+ * N.B. We no longer shuffle contents of ROM. That will come later. 
+ * @param rom The rom
+ * @param name Name of file to remove. 
+ * @return -1 on error, 0 if a file was set to deleted. 
+ */
 int rom_remove(struct rom *rom, const char *name)
 {
 	struct cbfs_file *c = rom_find_by_name(rom, name);
-	struct cbfs_file *n;
-	int clear;
 
 	if (c == NULL) {
 		ERROR("Component %s does not exist\n", name);
 		return -1;
 	}
 
-	/* Get the next component - and copy it into the current space if it
- 	 * exists.  If there is no next component, just delete c. */
-
-	n = rom_find_next(rom, c);
-	
-	if (n != NULL) {
-		memcpy(c, n, rom->fssize - ROM_OFFSET(rom, n));
-		clear = ROM_OFFSET(rom, n) - ROM_OFFSET(rom, c);
-	}
-	else { /* No component after this one. */
-		unsigned int csize;
-		csize = sizeof(struct cbfs_file) + ALIGN(strlen(name) + 1, 16);
-		clear = ntohl(c->len) + csize;
-		memcpy(c, ((void*)c) + clear, 
-		       rom->fssize - (ROM_OFFSET(rom, c)+clear));
-	}
-
-	/* Zero the new space, which is always at the end. */
-	memset(ROM_PTR(rom, rom->fssize - clear), 0, clear);
+	c->type = CBFS_COMPONENT_DELETED; 
 
 	return 0;
 }
@@ -145,14 +247,24 @@ int rom_extract(struct rom *rom, const char *name, void** buf, unsigned long *si
 
 	*size = ntohl(c->len);
 
-	csize = sizeof(struct cbfs_file) + ALIGN(strlen(name) + 1, 16);
+	csize = headersize(name);
 	*buf = ((unsigned char *)c) + csize;
 	return 0;
 }
 
+/**
+ * Add a new file named 'name', of type 'type', size 'size'. Initialize that file
+ * with the contents of 'buffer'. 
+ * @param rom The rom
+ * @param name file name
+ * @param buffer file data
+ * @param size Amount of data
+ * @param type File type
+ * @returns -1 on failure, 0 on success
+ */
 int rom_add(struct rom *rom, const char *name, void *buffer, int size, int type)
 {
-	struct cbfs_file *c = rom_find_empty(rom);
+	struct cbfs_file *c = rom_alloc(rom, size);
 	unsigned int offset;
 	unsigned int csize;
 
@@ -166,27 +278,18 @@ int rom_add(struct rom *rom, const char *name, void *buffer, int size, int type)
 		return -1;
 	}
 
-	csize = sizeof(struct cbfs_file) + ALIGN(strlen(name) + 1, 16);
+	csize = headersize(name);
 
 	offset = ROM_OFFSET(rom, c);
 
-	if (offset + csize + size > rom->fssize) {
-		ERROR("There is not enough room in this ROM for this\n");
-		ERROR("component. I need %d bytes, only have %d bytes avail\n",
-		      csize + size, rom->fssize - offset);
-
-		return -1;
-	}
-
 	strcpy(c->magic, COMPONENT_MAGIC);
 
-	c->len = htonl(size);
 	c->offset = htonl(csize);
 	c->type = htonl(type);
 
-	memset(CBFS_NAME(c), 0, ALIGN(strlen(name) + 1, 16));
-	strcpy((char *)CBFS_NAME(c), name);
+	setname(c, name);
 
 	memcpy(((unsigned char *)c) + csize, buffer, size);
 	return 0;
 }
+
diff --git a/util/cbfstool/util.c b/util/cbfstool/util.c
index 8f2a65bd0c..b36e9187a0 100644
--- a/util/cbfstool/util.c
+++ b/util/cbfstool/util.c
@@ -218,6 +218,9 @@ int create_rom(struct rom *rom, const unsigned char *filename,
 
 	ROM_WRITEL(rom, rom->size - 4,
 		   0xFFFFFFF0 - bootblocksize - sizeof(struct cbfs_header));
+
+	/* write the empty header */
+	rom_set_header(rom, (struct cbfs_file *)rom->ptr, "", -1, CBFS_COMPONENT_NULL);
 	return 0;
 }