[U-Boot] [PATCH 0/8] JFFS2 fixes and performance improvements

[U-Boot] [PATCH 0/8] JFFS2 fixes and performance improvements

[Mark Tomlinson]

These patches fix bugs and improve performance of JFFS2. Some of these
improvements can already be found in old mailing lists, but for some
reason they have not made their way into the u-boot source. I have the
feeling that any one of these patches didn't show enough performance gain
to warrant adding it to the source. I am hopeful that together, all these
patches can be seen to make a big difference.

One of these patches ("Only list each directory entry once") is a bug fix,
all the rest are for performance. Although performance is not high on the
priority list for a bootloader, the length of time it was taking to scan
a JFFS2 filesystem was painfully slow.

The code for mergesort was found in an abandoned u-boot patch, although I
have refactored the code somewhat. The original author is still shown at
the top of that file.

The timings below are with jffs2_summary_support turned off. With these
improvements, summary support was no longer useful - most of our time is
now spent loading the actual release. Even without this feature turned on,
the code will still load from a filesystem that has summary nodes.

Due to not having other resources, I also have not done anything for NAND
flash. At least some of these changes will be directly applicable to NAND
as well as NOR.

My own testing is on a system with a 1GHz PowerPC, and 256MB of NOR Flash.
The flash accesses are slow compared with processing power and RAM, so
minimising the number of flash accesses makes a huge difference. Here are
the timing comparisons for three JFFS2 operations on this system:
1) Scanning the file system
2) Getting a director listing of the top level, and
3) Loading a 30MB file.

Times are in seconds, and the contribution from each patch has been
measured:

                         Scan    List    Load    Total
Original:               266.0    17.3    23.4   306.7
Speed up comparison:     52.3    17.3    23.4    93.0
List dir entries once:   52.3    11.0    23.4    86.7
Improve read speed:      52.3     0.8     5.4    58.5
Optimize building lists: 31.9     0.8     5.4    38.1
Change scansize:         30.8     0.8     5.4    37.0
Use cleanmarker:         16.0     0.8     5.4    22.2
Use mergesort:            2.0     0.8     5.4     8.2

Note that "List dir entries once" is not a speed improvement as such, but
because old versions of a file and deleted files are no longer scanned,
there is an improvement on this filesystem (the flash is approx half full).

Also, "change scansize" appears to do very little in this benchmark list.
But without it, the "use cleanmarker" would not show as much improvement.


Mark Tomlinson (8):
  JFFS2: Return early when file read not necessary
  JFFS2: Speed up and fix comparison functions
  JFFS2: Only list each directory entry once
  JFFS2: Improve speed reading flash files
  JFFS2: Optimize building lists during scan
  JFFS2: Change scansize to match linux kernel
  JFFS2: Use CLEANMARKER to reduce scanning time
  JFFS2: Use merge sort when parsing filesystem

 fs/jffs2/Makefile        |   1 +
 fs/jffs2/jffs2_1pass.c   | 245 +++++++++++++++++++++++++++++------------------
 fs/jffs2/jffs2_private.h |   4 +
 fs/jffs2/mergesort.c     |  70 ++++++++++++++
 4 files changed, 228 insertions(+), 92 deletions(-)
 create mode 100644 fs/jffs2/mergesort.c

-- 
1.9.1

[U-Boot] [PATCH 1/8] JFFS2: Return early when file read not necessary

[Mark Tomlinson]

If a destination is not provided, jffs2_1pass_read_inode() only
returns the length of the file. In this case, avoid reading all
the data nodes, and return as soon as the length of the file is
known.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index b1d6470..2335db1 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -719,6 +719,12 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 		}
 		put_fl_mem(jNode, pL->readbuf);
 	}
+	/* If no destination is provided, we are done.
+	 * Just return the total size.
+	 */
+	if (!dest) {
+		return totalSize;
+	}
 #endif
 
 	for (b = pL->frag.listHead; b != NULL; b = b->next) {
-- 
1.9.1

[U-Boot] [PATCH 2/8] JFFS2: Speed up and fix comparison functions

[Mark Tomlinson]

Copying complete nodes from flash can be slow if the flash is slow
to read. By only reading the data needed, the sorting operation can
be made much faster.

The directory entry comparison function also had a two bugs. First, it
did not ensure the name was copied, so the name comparison may have
been faulty (although it would have worked with NOR flash).  Second,
setting the ino to zero to ignore the entry did not work, since this
was either writing to a temporary buffer, or (for NOR flash) directly
to flash. Either way, the change was not remembered.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 82 ++++++++++++++++++++++++++------------------------
 1 file changed, 42 insertions(+), 40 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 2335db1..079bb73 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -598,14 +598,17 @@ insert_node(struct b_list *list, u32 offset)
  */
 static int compare_inodes(struct b_node *new, struct b_node *old)
 {
-	struct jffs2_raw_inode ojNew;
-	struct jffs2_raw_inode ojOld;
-	struct jffs2_raw_inode *jNew =
-		(struct jffs2_raw_inode *)get_fl_mem(new->offset, sizeof(ojNew), &ojNew);
-	struct jffs2_raw_inode *jOld =
-		(struct jffs2_raw_inode *)get_fl_mem(old->offset, sizeof(ojOld), &ojOld);
-
-	return jNew->version > jOld->version;
+	/* Only read in the version info from flash, not the entire inode.
+	 * This can make a big difference to speed if flash is slow.
+	 */
+	u32 new_version;
+	u32 old_version;
+	get_fl_mem(new->offset + offsetof(struct jffs2_raw_inode, version),
+		   sizeof(new_version), &new_version);
+	get_fl_mem(old->offset + offsetof(struct jffs2_raw_inode, version),
+		   sizeof(old_version), &old_version);
+
+	return new_version > old_version;
 }
 
 /* Sort directory entries so all entries in the same directory
@@ -615,42 +618,41 @@ static int compare_inodes(struct b_node *new, struct b_node *old)
  */
 static int compare_dirents(struct b_node *new, struct b_node *old)
 {
-	struct jffs2_raw_dirent ojNew;
-	struct jffs2_raw_dirent ojOld;
-	struct jffs2_raw_dirent *jNew =
-		(struct jffs2_raw_dirent *)get_fl_mem(new->offset, sizeof(ojNew), &ojNew);
-	struct jffs2_raw_dirent *jOld =
-		(struct jffs2_raw_dirent *)get_fl_mem(old->offset, sizeof(ojOld), &ojOld);
-	int cmp;
-
-	/* ascending sort by pino */
-	if (jNew->pino != jOld->pino)
-		return jNew->pino > jOld->pino;
-
-	/* pino is the same, so use ascending sort by nsize, so
-	 * we don't do strncmp unless we really must.
-	 */
-	if (jNew->nsize != jOld->nsize)
-		return jNew->nsize > jOld->nsize;
-
-	/* length is also the same, so use ascending sort by name
-	 */
-	cmp = strncmp((char *)jNew->name, (char *)jOld->name, jNew->nsize);
-	if (cmp != 0)
-		return cmp > 0;
-
-	/* we have duplicate names in this directory, so use ascending
-	 * sort by version
+	/* Using NULL as the buffer for NOR flash prevents the entire node
+	 * being read. This makes most comparisons much quicker as only one
+	 * or two entries from the node will be used most of the time.
 	 */
-	if (jNew->version > jOld->version) {
-		/* since jNew is newer, we know jOld is not valid, so
-		 * mark it with inode 0 and it will not be used
+	struct jffs2_raw_dirent *jNew = get_node_mem(new->offset, NULL);
+	struct jffs2_raw_dirent *jOld = get_node_mem(old->offset, NULL);
+	int cmp;
+	int ret;
+
+	if (jNew->pino != jOld->pino) {
+		/* ascending sort by pino */
+		ret = jNew->pino > jOld->pino;
+	} else if (jNew->nsize != jOld->nsize) {
+		/* pino is the same, so use ascending sort by nsize, so
+		 * we don't do strncmp unless we really must.
 		 */
-		jOld->ino = 0;
-		return 1;
+		ret = jNew->nsize > jOld->nsize;
+	} else {
+		/* length is also the same, so use ascending sort by name
+		 */
+		cmp = strncmp((char *)jNew->name, (char *)jOld->name,
+			jNew->nsize);
+		if (cmp != 0) {
+			ret = cmp > 0;
+		} else {
+			/* we have duplicate names in this directory,
+			 * so use ascending sort by version
+			 */
+			ret = jNew->version > jOld->version;
+		}
 	}
+	put_fl_mem(jNew, NULL);
+	put_fl_mem(jOld, NULL);
 
-	return 0;
+	return ret;
 }
 #endif
 
-- 
1.9.1

[U-Boot] [PATCH 3/8] JFFS2: Only list each directory entry once

[Mark Tomlinson]

If multiple versions of a file exist, only the most recent version
should be used. The scheme to write 0 for the inode in older versions
did not work, since this would have required writing to flash.

The only time this caused an issue was listing a directory, where older
versions of the file would still be seen. Since the directory entries
are sorted, just look at the next entry in the list, and if it's the same
move to that entry instead.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 37 ++++++++++++++++++++++++++++++++-----
 1 file changed, 32 insertions(+), 5 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 079bb73..1f6eea7 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -840,7 +840,6 @@ jffs2_1pass_find_inode(struct b_lists * pL, const char *name, u32 pino)
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
 		if ((pino == jDir->pino) && (len == jDir->nsize) &&
-		    (jDir->ino) &&	/* 0 for unlink */
 		    (!strncmp((char *)jDir->name, name, len))) {	/* a match */
 			if (jDir->version < version) {
 				put_fl_mem(jDir, pL->readbuf);
@@ -961,13 +960,42 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 	for (b = pL->dir.listHead; b; b = b->next) {
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
-		if ((pino == jDir->pino) && (jDir->ino)) { /* ino=0 -> unlink */
+		if (pino == jDir->pino) {
 			u32 i_version = 0;
 			struct jffs2_raw_inode ojNode;
 			struct jffs2_raw_inode *jNode, *i = NULL;
-			struct b_node *b2 = pL->frag.listHead;
+			struct b_node *b2;
 
-			while (b2) {
+#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
+			/* Check for more recent versions of this file */
+			int match;
+			do {
+				struct b_node *next = b->next;
+				struct jffs2_raw_dirent *jDirNext;
+				if (!next)
+					break;
+				jDirNext = (struct jffs2_raw_dirent *)
+					get_node_mem(next->offset, NULL);
+				match = jDirNext->pino == jDir->pino &&
+					jDirNext->nsize == jDir->nsize &&
+					strncmp((char *)jDirNext->name,
+						(char *)jDir->name,
+						jDir->nsize) == 0;
+				if (match) {
+					/* Use next. It is more recent */
+					b = next;
+					/* Update buffer with the new info */
+					*jDir = *jDirNext;
+					put_fl_mem(jDirNext, NULL);
+				}
+			} while (match);
+#endif
+			if (jDir->ino == 0) {
+				/* Deleted file */
+				continue;
+			}
+
+			for (b2 = pL->frag.listHead; b2; b2 = b2->next) {
 				jNode = (struct jffs2_raw_inode *)
 					get_fl_mem(b2->offset, sizeof(ojNode), &ojNode);
 				if (jNode->ino == jDir->ino && jNode->version >= i_version) {
@@ -983,7 +1011,6 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 							       sizeof(*i),
 							       NULL);
 				}
-				b2 = b2->next;
 			}
 
 			dump_inode(pL, jDir, i);
-- 
1.9.1

[U-Boot] [PATCH 4/8] JFFS2: Improve speed reading flash files

[Mark Tomlinson]

jffs2_1pass_read_inode() would read the entire data for each node
in the filesystem, regardless of whether it was part of the file
to be loaded or not. By only reading the header data for an inode,
and then reading the data only when it is found to be part of the
file to be loaded, much copying of data is saved.

jffs2_1pass_list_inodes() read each inode for every file in the
directory into a buffer. By using NULL as a buffer pointer, NOR
flash simply returns a pointer, and therefore avoids a memory copy.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 1f6eea7..80210be 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -730,8 +730,12 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 #endif
 
 	for (b = pL->frag.listHead; b != NULL; b = b->next) {
-		jNode = (struct jffs2_raw_inode *) get_node_mem(b->offset,
-								pL->readbuf);
+		/* Copy just the node and not the data at this point,
+		 * since we don't yet know if we need this data.
+		 */
+		jNode = (struct jffs2_raw_inode *)get_fl_mem(b->offset,
+				sizeof(struct jffs2_raw_inode),
+				pL->readbuf);
 		if (inode == jNode->ino) {
 #if 0
 			putLabeledWord("\r\n\r\nread_inode: totlen = ", jNode->totlen);
@@ -755,7 +759,14 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 #endif
 
 			if(dest) {
-				src = ((uchar *) jNode) + sizeof(struct jffs2_raw_inode);
+				/* Now that the inode has been checked,
+				 * read the entire inode, including data.
+				 */
+				put_fl_mem(jNode, pL->readbuf);
+				jNode = (struct jffs2_raw_inode *)
+					get_node_mem(b->offset, pL->readbuf);
+				src = ((uchar *)jNode) +
+					sizeof(struct jffs2_raw_inode);
 				/* ignore data behind latest known EOF */
 				if (jNode->offset > totalSize) {
 					put_fl_mem(jNode, pL->readbuf);
@@ -962,7 +973,6 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 								pL->readbuf);
 		if (pino == jDir->pino) {
 			u32 i_version = 0;
-			struct jffs2_raw_inode ojNode;
 			struct jffs2_raw_inode *jNode, *i = NULL;
 			struct b_node *b2;
 
@@ -997,8 +1007,10 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 
 			for (b2 = pL->frag.listHead; b2; b2 = b2->next) {
 				jNode = (struct jffs2_raw_inode *)
-					get_fl_mem(b2->offset, sizeof(ojNode), &ojNode);
-				if (jNode->ino == jDir->ino && jNode->version >= i_version) {
+					get_fl_mem(b2->offset, sizeof(*jNode),
+						   NULL);
+				if (jNode->ino == jDir->ino &&
+				    jNode->version >= i_version) {
 					i_version = jNode->version;
 					if (i)
 						put_fl_mem(i, NULL);
@@ -1011,6 +1023,7 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 							       sizeof(*i),
 							       NULL);
 				}
+				put_fl_mem(jNode, NULL);
 			}
 
 			dump_inode(pL, jDir, i);
-- 
1.9.1

[U-Boot] [PATCH 5/8] JFFS2: Optimize building lists during scan

[Mark Tomlinson]

If the flash is slow, reading less from the flash into buffers makes
the process faster.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 80210be..10bd7be 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -1493,7 +1493,7 @@ jffs2_1pass_build_lists(struct part_info * part)
 	u32 counterF = 0;
 	u32 counterN = 0;
 	u32 max_totlen = 0;
-	u32 buf_size = DEFAULT_EMPTY_SCAN_SIZE;
+	u32 buf_size;
 	char *buf;
 
 	nr_sectors = lldiv(part->size, part->sector_size);
@@ -1505,7 +1505,7 @@ jffs2_1pass_build_lists(struct part_info * part)
 	/* if we are building a list we need to refresh the cache. */
 	jffs_init_1pass_list(part);
 	pL = (struct b_lists *)part->jffs2_priv;
-	buf = malloc(buf_size);
+	buf = malloc(DEFAULT_EMPTY_SCAN_SIZE);
 	puts ("Scanning JFFS2 FS:   ");
 
 	/* start at the beginning of the partition */
@@ -1521,6 +1521,8 @@ jffs2_1pass_build_lists(struct part_info * part)
 		int ret;
 #endif
 
+		/* Set buf_size to maximum length */
+		buf_size = DEFAULT_EMPTY_SCAN_SIZE;
 		WATCHDOG_RESET();
 
 #ifdef CONFIG_JFFS2_SUMMARY
@@ -1595,6 +1597,10 @@ jffs2_1pass_build_lists(struct part_info * part)
 
 		ofs += sector_ofs;
 		prevofs = ofs - 1;
+		/* Set buf_size down to the minimum size required.
+		 * This prevents reading in chunks of flash data unnecessarily.
+		 */
+		buf_size = sizeof(union jffs2_node_union);
 
 	scan_more:
 		while (ofs < sector_ofs + part->sector_size) {
@@ -1675,13 +1681,18 @@ jffs2_1pass_build_lists(struct part_info * part)
 			case JFFS2_NODETYPE_INODE:
 				if (buf_ofs + buf_len < ofs + sizeof(struct
 							jffs2_raw_inode)) {
+					buf_len = min_t(uint32_t,
+							sizeof(struct jffs2_raw_inode),
+							sector_ofs +
+							part->sector_size -
+							ofs);
 					get_fl_mem((u32)part->offset + ofs,
 						   buf_len, buf);
 					buf_ofs = ofs;
 					node = (void *)buf;
 				}
-				if (!inode_crc((struct jffs2_raw_inode *) node))
-				       break;
+				if (!inode_crc((struct jffs2_raw_inode *)node))
+					break;
 
 				if (insert_node(&pL->frag, (u32) part->offset +
 						ofs) == NULL) {
@@ -1698,6 +1709,11 @@ jffs2_1pass_build_lists(struct part_info * part)
 							((struct
 							 jffs2_raw_dirent *)
 							node)->nsize) {
+					buf_len = min_t(uint32_t,
+							node->totlen,
+							sector_ofs +
+							part->sector_size -
+							ofs);
 					get_fl_mem((u32)part->offset + ofs,
 						   buf_len, buf);
 					buf_ofs = ofs;
-- 
1.9.1

[U-Boot] [PATCH 6/8] JFFS2: Change scansize to match linux kernel

[Mark Tomlinson]

The scan code is similar to the linux kernel, but the kernel defines a much
smaller size to scan through before deciding a sector is blank. Assuming
that what is in the kernel is OK, make these two match.

On its own, this change makes no difference to scanning of any sectors
which have a clean marker at the beginning, since the entire sector is not
blank.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 10bd7be..d78fb06 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -1472,7 +1472,7 @@ dump_dirents(struct b_lists *pL)
 }
 #endif
 
-#define DEFAULT_EMPTY_SCAN_SIZE	4096
+#define DEFAULT_EMPTY_SCAN_SIZE	256
 
 static inline uint32_t EMPTY_SCAN_SIZE(uint32_t sector_size)
 {
-- 
1.9.1

[U-Boot] [PATCH 7/8] JFFS2: Use CLEANMARKER to reduce scanning time

[Mark Tomlinson]

If a sector has a CLEANMARKER at the beginning, it indicates that the
entire sector has been erased. Therefore, if this is found, we can skip the
entire block. This was not being done before this patch.

The code now does the same as the kernel does when encountering a
CLEANMARKER. It still checks that the next few words are FFFFFFFF, and if
so, the block is assumed to be empty, and so is skipped.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/jffs2_1pass.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index d78fb06..26a748f 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -1520,6 +1520,8 @@ jffs2_1pass_build_lists(struct part_info * part)
 		uint32_t sumlen;
 		int ret;
 #endif
+		/* Indicates a sector with a CLEANMARKER was found */
+		int clean_sector = 0;
 
 		/* Set buf_size to maximum length */
 		buf_size = DEFAULT_EMPTY_SCAN_SIZE;
@@ -1643,6 +1645,13 @@ jffs2_1pass_build_lists(struct part_info * part)
 					ofs += 4;
 				}
 				/* Ran off end. */
+				/* If this sector had a clean marker at the
+				 * beginning, and immediately following this
+				 * have been a bunch of FF bytes, treat the
+				 * entire sector as empty.
+				 */
+				if (clean_sector)
+					break;
 
 				/* See how much more there is to read in this
 				 * eraseblock...
@@ -1664,6 +1673,10 @@ jffs2_1pass_build_lists(struct part_info * part)
 				buf_ofs = ofs;
 				goto more_empty;
 			}
+			/* Found something not erased in the sector, so reset
+			 * the 'clean_sector' flag.
+			 */
+			clean_sector = 0;
 			if (node->magic != JFFS2_MAGIC_BITMASK ||
 					!hdr_crc(node)) {
 				ofs += 4;
@@ -1745,6 +1758,15 @@ jffs2_1pass_build_lists(struct part_info * part)
 						"%d != %zu\n",
 						node->totlen,
 						sizeof(struct jffs2_unknown_node));
+				if ((node->totlen ==
+				     sizeof(struct jffs2_unknown_node)) &&
+				    (ofs == sector_ofs)) {
+					/* Found a CLEANMARKER at the beginning
+					 * of the sector. It's in the correct
+					 * place with correct size and CRC.
+					 */
+					clean_sector = 1;
+				}
 				break;
 			case JFFS2_NODETYPE_PADDING:
 				if (node->totlen < sizeof(struct jffs2_unknown_node))
-- 
1.9.1

[U-Boot] [PATCH 8/8] JFFS2: Use merge sort when parsing filesystem

[Mark Tomlinson]

When building the file system the existing code does an insertion into
a linked list. It attempts to speed this up by keeping a pointer to
where the last entry was inserted but it's still slow.

Now the nodes are just inserted into the list without searching
through for the correct place. This unsorted list is then sorted once
using mergesort after all the entries have been added to the list.
This speeds up the scanning of the flash file system considerably.

Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
---

 fs/jffs2/Makefile        |  1 +
 fs/jffs2/jffs2_1pass.c   | 47 ++++++++------------------------
 fs/jffs2/jffs2_private.h |  4 +++
 fs/jffs2/mergesort.c     | 70 ++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 86 insertions(+), 36 deletions(-)
 create mode 100644 fs/jffs2/mergesort.c

diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
index 4cb0600..90524ba 100644
--- a/fs/jffs2/Makefile
+++ b/fs/jffs2/Makefile
@@ -10,4 +10,5 @@ obj-y += compr_rtime.o
 obj-y += compr_rubin.o
 obj-y += compr_zlib.o
 obj-y += jffs2_1pass.o
+obj-y += mergesort.o
 obj-y += mini_inflate.o
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 26a748f..a456650 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -125,7 +125,6 @@
 
 #include "jffs2_private.h"
 
-
 #define	NODE_CHUNK	1024	/* size of memory allocation chunk in b_nodes */
 #define	SPIN_BLKSIZE	18	/* spin after having scanned 1<<BLKSIZE bytes */
 
@@ -545,49 +544,19 @@ static struct b_node *
 insert_node(struct b_list *list, u32 offset)
 {
 	struct b_node *new;
-#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
-	struct b_node *b, *prev;
-#endif
 
 	if (!(new = add_node(list))) {
 		putstr("add_node failed!\r\n");
 		return NULL;
 	}
 	new->offset = offset;
+	new->next = NULL;
 
-#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
-	if (list->listTail != NULL && list->listCompare(new, list->listTail))
-		prev = list->listTail;
-	else if (list->listLast != NULL && list->listCompare(new, list->listLast))
-		prev = list->listLast;
+	if (list->listTail != NULL)
+		list->listTail->next = new;
 	else
-		prev = NULL;
-
-	for (b = (prev ? prev->next : list->listHead);
-	     b != NULL && list->listCompare(new, b);
-	     prev = b, b = b->next) {
-		list->listLoops++;
-	}
-	if (b != NULL)
-		list->listLast = prev;
-
-	if (b != NULL) {
-		new->next = b;
-		if (prev != NULL)
-			prev->next = new;
-		else
-			list->listHead = new;
-	} else
-#endif
-	{
-		new->next = (struct b_node *) NULL;
-		if (list->listTail != NULL) {
-			list->listTail->next = new;
-			list->listTail = new;
-		} else {
-			list->listTail = list->listHead = new;
-		}
-	}
+		list->listHead = new;
+	list->listTail = new;
 
 	return new;
 }
@@ -1788,6 +1757,12 @@ jffs2_1pass_build_lists(struct part_info * part)
 	}
 
 	free(buf);
+#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+	/* Sort the lists.
+	 */
+	sort_list(&pL->frag);
+	sort_list(&pL->dir);
+#endif
 	putstr("\b\b done.\r\n");		/* close off the dots */
 
 	/* We don't care if malloc failed - then each read operation will
diff --git a/fs/jffs2/jffs2_private.h b/fs/jffs2/jffs2_private.h
index 658b325..06b6ca2 100644
--- a/fs/jffs2/jffs2_private.h
+++ b/fs/jffs2/jffs2_private.h
@@ -98,4 +98,8 @@ data_crc(struct jffs2_raw_inode *node)
 	}
 }
 
+#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+/* External merge sort. */
+int sort_list(struct b_list *list);
+#endif
 #endif /* jffs2_private.h */
diff --git a/fs/jffs2/mergesort.c b/fs/jffs2/mergesort.c
new file mode 100644
index 0000000..10ecc8d
--- /dev/null
+++ b/fs/jffs2/mergesort.c
@@ -0,0 +1,70 @@
+/*
+ * This file is copyright 2001 Simon Tatham.
+ * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
+ * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+ * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <common.h>
+#include "jffs2_private.h"
+
+#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+int sort_list(struct b_list *list)
+{
+	struct b_node *p, *q, *e, **tail;
+	int k, psize, qsize;
+
+	if (!list->listHead)
+		return 0;
+
+	for (k = 1; k < list->listCount; k *= 2) {
+		tail = &list->listHead;
+		for (p = q = list->listHead; p; p = q) {
+			/* step 'k' places from p; */
+			for (psize = 0; q && psize < k; psize++)
+				q = q->next;
+			qsize = k;
+
+			/* two lists, merge them. */
+			while (psize || (qsize && q)) {
+				/* merge the next element */
+				if (psize == 0 ||
+				    ((qsize && q) &&
+				     list->listCompare(p, q))) {
+					/* p is empty, or p > q, so q next */
+					e = q;
+					q = q->next;
+					qsize--;
+				} else {
+					e = p;
+					p = p->next;
+					psize--;
+				}
+				e->next = NULL; /* break accidental loops. */
+				*tail = e;
+				tail = &e->next;
+			}
+		}
+	}
+	return 0;
+}
+#endif
-- 
1.9.1

[U-Boot] [PATCH 1/8] JFFS2: Return early when file read not necessary

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> If a destination is not provided, jffs2_1pass_read_inode() only
> returns the length of the file. In this case, avoid reading all
> the data nodes, and return as soon as the length of the file is
> known.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 6 ++++++
>   1 file changed, 6 insertions(+)
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index b1d6470..2335db1 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -719,6 +719,12 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
>   		}
>   		put_fl_mem(jNode, pL->readbuf);
>   	}
> +	/* If no destination is provided, we are done.
> +	 * Just return the total size.
> +	 */

please change this into

	/*
	 * If no destination is provided, we are done.
	 * Just return the total size.
	 */

to fit with Coding style.


> +	if (!dest) {
> +		return totalSize;
> +	}

no {} needed

Beside of this:

Acked-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>   #endif
>
>   	for (b = pL->frag.listHead; b != NULL; b = b->next) {
>

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 2/8] JFFS2: Speed up and fix comparison functions

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> Copying complete nodes from flash can be slow if the flash is slow
> to read. By only reading the data needed, the sorting operation can
> be made much faster.
>
> The directory entry comparison function also had a two bugs. First, it
> did not ensure the name was copied, so the name comparison may have
> been faulty (although it would have worked with NOR flash).  Second,
> setting the ino to zero to ignore the entry did not work, since this
> was either writing to a temporary buffer, or (for NOR flash) directly
> to flash. Either way, the change was not remembered.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 82 ++++++++++++++++++++++++++------------------------
>   1 file changed, 42 insertions(+), 40 deletions(-)
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 2335db1..079bb73 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -598,14 +598,17 @@ insert_node(struct b_list *list, u32 offset)
>    */
>   static int compare_inodes(struct b_node *new, struct b_node *old)
>   {
> -	struct jffs2_raw_inode ojNew;
> -	struct jffs2_raw_inode ojOld;
> -	struct jffs2_raw_inode *jNew =
> -		(struct jffs2_raw_inode *)get_fl_mem(new->offset, sizeof(ojNew), &ojNew);
> -	struct jffs2_raw_inode *jOld =
> -		(struct jffs2_raw_inode *)get_fl_mem(old->offset, sizeof(ojOld), &ojOld);
> -
> -	return jNew->version > jOld->version;
> +	/* Only read in the version info from flash, not the entire inode.

please fix your comment style globally, thanks1

> +	 * This can make a big difference to speed if flash is slow.
> +	 */
> +	u32 new_version;
> +	u32 old_version;
> +	get_fl_mem(new->offset + offsetof(struct jffs2_raw_inode, version),
> +		   sizeof(new_version), &new_version);
> +	get_fl_mem(old->offset + offsetof(struct jffs2_raw_inode, version),
> +		   sizeof(old_version), &old_version);
> +
> +	return new_version > old_version;
>   }
>
>   /* Sort directory entries so all entries in the same directory
> @@ -615,42 +618,41 @@ static int compare_inodes(struct b_node *new, struct b_node *old)
>    */
>   static int compare_dirents(struct b_node *new, struct b_node *old)
>   {
> -	struct jffs2_raw_dirent ojNew;
> -	struct jffs2_raw_dirent ojOld;
> -	struct jffs2_raw_dirent *jNew =
> -		(struct jffs2_raw_dirent *)get_fl_mem(new->offset, sizeof(ojNew), &ojNew);
> -	struct jffs2_raw_dirent *jOld =
> -		(struct jffs2_raw_dirent *)get_fl_mem(old->offset, sizeof(ojOld), &ojOld);
> -	int cmp;
> -
> -	/* ascending sort by pino */
> -	if (jNew->pino != jOld->pino)
> -		return jNew->pino > jOld->pino;
> -
> -	/* pino is the same, so use ascending sort by nsize, so
> -	 * we don't do strncmp unless we really must.
> -	 */
> -	if (jNew->nsize != jOld->nsize)
> -		return jNew->nsize > jOld->nsize;
> -
> -	/* length is also the same, so use ascending sort by name
> -	 */
> -	cmp = strncmp((char *)jNew->name, (char *)jOld->name, jNew->nsize);
> -	if (cmp != 0)
> -		return cmp > 0;
> -
> -	/* we have duplicate names in this directory, so use ascending
> -	 * sort by version
> +	/* Using NULL as the buffer for NOR flash prevents the entire node
> +	 * being read. This makes most comparisons much quicker as only one
> +	 * or two entries from the node will be used most of the time.
>   	 */
> -	if (jNew->version > jOld->version) {
> -		/* since jNew is newer, we know jOld is not valid, so
> -		 * mark it with inode 0 and it will not be used
> +	struct jffs2_raw_dirent *jNew = get_node_mem(new->offset, NULL);
> +	struct jffs2_raw_dirent *jOld = get_node_mem(old->offset, NULL);
> +	int cmp;
> +	int ret;
> +
> +	if (jNew->pino != jOld->pino) {
> +		/* ascending sort by pino */
> +		ret = jNew->pino > jOld->pino;
> +	} else if (jNew->nsize != jOld->nsize) {
> +		/* pino is the same, so use ascending sort by nsize, so
> +		 * we don't do strncmp unless we really must.
>   		 */
> -		jOld->ino = 0;
> -		return 1;
> +		ret = jNew->nsize > jOld->nsize;
> +	} else {
> +		/* length is also the same, so use ascending sort by name
> +		 */
> +		cmp = strncmp((char *)jNew->name, (char *)jOld->name,
> +			jNew->nsize);
> +		if (cmp != 0) {
> +			ret = cmp > 0;
> +		} else {
> +			/* we have duplicate names in this directory,
> +			 * so use ascending sort by version
> +			 */
> +			ret = jNew->version > jOld->version;
> +		}
>   	}
> +	put_fl_mem(jNew, NULL);
> +	put_fl_mem(jOld, NULL);
>
> -	return 0;
> +	return ret;
>   }
>   #endif

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 3/8] JFFS2: Only list each directory entry once

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> If multiple versions of a file exist, only the most recent version
> should be used. The scheme to write 0 for the inode in older versions
> did not work, since this would have required writing to flash.
>
> The only time this caused an issue was listing a directory, where older
> versions of the file would still be seen. Since the directory entries
> are sorted, just look at the next entry in the list, and if it's the same
> move to that entry instead.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 37 ++++++++++++++++++++++++++++++++-----
>   1 file changed, 32 insertions(+), 5 deletions(-)

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 079bb73..1f6eea7 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -840,7 +840,6 @@ jffs2_1pass_find_inode(struct b_lists * pL, const char *name, u32 pino)
>   		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
>   								pL->readbuf);
>   		if ((pino == jDir->pino) && (len == jDir->nsize) &&
> -		    (jDir->ino) &&	/* 0 for unlink */
>   		    (!strncmp((char *)jDir->name, name, len))) {	/* a match */
>   			if (jDir->version < version) {
>   				put_fl_mem(jDir, pL->readbuf);
> @@ -961,13 +960,42 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
>   	for (b = pL->dir.listHead; b; b = b->next) {
>   		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
>   								pL->readbuf);
> -		if ((pino == jDir->pino) && (jDir->ino)) { /* ino=0 -> unlink */
> +		if (pino == jDir->pino) {
>   			u32 i_version = 0;
>   			struct jffs2_raw_inode ojNode;
>   			struct jffs2_raw_inode *jNode, *i = NULL;
> -			struct b_node *b2 = pL->frag.listHead;
> +			struct b_node *b2;
>
> -			while (b2) {
> +#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
> +			/* Check for more recent versions of this file */
> +			int match;
> +			do {
> +				struct b_node *next = b->next;
> +				struct jffs2_raw_dirent *jDirNext;
> +				if (!next)
> +					break;
> +				jDirNext = (struct jffs2_raw_dirent *)
> +					get_node_mem(next->offset, NULL);
> +				match = jDirNext->pino == jDir->pino &&
> +					jDirNext->nsize == jDir->nsize &&
> +					strncmp((char *)jDirNext->name,
> +						(char *)jDir->name,
> +						jDir->nsize) == 0;
> +				if (match) {
> +					/* Use next. It is more recent */
> +					b = next;
> +					/* Update buffer with the new info */
> +					*jDir = *jDirNext;
> +					put_fl_mem(jDirNext, NULL);
> +				}
> +			} while (match);
> +#endif
> +			if (jDir->ino == 0) {
> +				/* Deleted file */
> +				continue;
> +			}
> +
> +			for (b2 = pL->frag.listHead; b2; b2 = b2->next) {
>   				jNode = (struct jffs2_raw_inode *)
>   					get_fl_mem(b2->offset, sizeof(ojNode), &ojNode);
>   				if (jNode->ino == jDir->ino && jNode->version >= i_version) {
> @@ -983,7 +1011,6 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
>   							       sizeof(*i),
>   							       NULL);
>   				}
> -				b2 = b2->next;
>   			}
>
>   			dump_inode(pL, jDir, i);
>

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 4/8] JFFS2: Improve speed reading flash files

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> jffs2_1pass_read_inode() would read the entire data for each node
> in the filesystem, regardless of whether it was part of the file
> to be loaded or not. By only reading the header data for an inode,
> and then reading the data only when it is found to be part of the
> file to be loaded, much copying of data is saved.
>
> jffs2_1pass_list_inodes() read each inode for every file in the
> directory into a buffer. By using NULL as a buffer pointer, NOR
> flash simply returns a pointer, and therefore avoids a memory copy.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 25 +++++++++++++++++++------
>   1 file changed, 19 insertions(+), 6 deletions(-)

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 1f6eea7..80210be 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -730,8 +730,12 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
>   #endif
>
>   	for (b = pL->frag.listHead; b != NULL; b = b->next) {
> -		jNode = (struct jffs2_raw_inode *) get_node_mem(b->offset,
> -								pL->readbuf);
> +		/* Copy just the node and not the data at this point,
> +		 * since we don't yet know if we need this data.
> +		 */
> +		jNode = (struct jffs2_raw_inode *)get_fl_mem(b->offset,
> +				sizeof(struct jffs2_raw_inode),
> +				pL->readbuf);
>   		if (inode == jNode->ino) {
>   #if 0
>   			putLabeledWord("\r\n\r\nread_inode: totlen = ", jNode->totlen);
> @@ -755,7 +759,14 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
>   #endif
>
>   			if(dest) {
> -				src = ((uchar *) jNode) + sizeof(struct jffs2_raw_inode);
> +				/* Now that the inode has been checked,
> +				 * read the entire inode, including data.
> +				 */
> +				put_fl_mem(jNode, pL->readbuf);
> +				jNode = (struct jffs2_raw_inode *)
> +					get_node_mem(b->offset, pL->readbuf);
> +				src = ((uchar *)jNode) +
> +					sizeof(struct jffs2_raw_inode);
>   				/* ignore data behind latest known EOF */
>   				if (jNode->offset > totalSize) {
>   					put_fl_mem(jNode, pL->readbuf);
> @@ -962,7 +973,6 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
>   								pL->readbuf);
>   		if (pino == jDir->pino) {
>   			u32 i_version = 0;
> -			struct jffs2_raw_inode ojNode;
>   			struct jffs2_raw_inode *jNode, *i = NULL;
>   			struct b_node *b2;
>
> @@ -997,8 +1007,10 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
>
>   			for (b2 = pL->frag.listHead; b2; b2 = b2->next) {
>   				jNode = (struct jffs2_raw_inode *)
> -					get_fl_mem(b2->offset, sizeof(ojNode), &ojNode);
> -				if (jNode->ino == jDir->ino && jNode->version >= i_version) {
> +					get_fl_mem(b2->offset, sizeof(*jNode),
> +						   NULL);
> +				if (jNode->ino == jDir->ino &&
> +				    jNode->version >= i_version) {
>   					i_version = jNode->version;
>   					if (i)
>   						put_fl_mem(i, NULL);
> @@ -1011,6 +1023,7 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
>   							       sizeof(*i),
>   							       NULL);
>   				}
> +				put_fl_mem(jNode, NULL);
>   			}
>
>   			dump_inode(pL, jDir, i);
>

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 5/8] JFFS2: Optimize building lists during scan

[Heiko Schocher invitel]

Hello Mark,

please fix Tom rinis mail address globally for your patchset into

Tom Rini <trini@konsulko.com>

I fixed it for my response manually, thanks!

BTW: You can use patman for creating patches/patchset.
Look into u-boot:tools/patman

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> If the flash is slow, reading less from the flash into buffers makes
> the process faster.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 24 ++++++++++++++++++++----
>   1 file changed, 20 insertions(+), 4 deletions(-)

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 80210be..10bd7be 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -1493,7 +1493,7 @@ jffs2_1pass_build_lists(struct part_info * part)
>   	u32 counterF = 0;
>   	u32 counterN = 0;
>   	u32 max_totlen = 0;
> -	u32 buf_size = DEFAULT_EMPTY_SCAN_SIZE;
> +	u32 buf_size;
>   	char *buf;
>
>   	nr_sectors = lldiv(part->size, part->sector_size);
> @@ -1505,7 +1505,7 @@ jffs2_1pass_build_lists(struct part_info * part)
>   	/* if we are building a list we need to refresh the cache. */
>   	jffs_init_1pass_list(part);
>   	pL = (struct b_lists *)part->jffs2_priv;
> -	buf = malloc(buf_size);
> +	buf = malloc(DEFAULT_EMPTY_SCAN_SIZE);
>   	puts ("Scanning JFFS2 FS:   ");
>
>   	/* start at the beginning of the partition */
> @@ -1521,6 +1521,8 @@ jffs2_1pass_build_lists(struct part_info * part)
>   		int ret;
>   #endif
>
> +		/* Set buf_size to maximum length */
> +		buf_size = DEFAULT_EMPTY_SCAN_SIZE;
>   		WATCHDOG_RESET();
>
>   #ifdef CONFIG_JFFS2_SUMMARY
> @@ -1595,6 +1597,10 @@ jffs2_1pass_build_lists(struct part_info * part)
>
>   		ofs += sector_ofs;
>   		prevofs = ofs - 1;
> +		/* Set buf_size down to the minimum size required.
> +		 * This prevents reading in chunks of flash data unnecessarily.
> +		 */
> +		buf_size = sizeof(union jffs2_node_union);
>
>   	scan_more:
>   		while (ofs < sector_ofs + part->sector_size) {
> @@ -1675,13 +1681,18 @@ jffs2_1pass_build_lists(struct part_info * part)
>   			case JFFS2_NODETYPE_INODE:
>   				if (buf_ofs + buf_len < ofs + sizeof(struct
>   							jffs2_raw_inode)) {
> +					buf_len = min_t(uint32_t,
> +							sizeof(struct jffs2_raw_inode),
> +							sector_ofs +
> +							part->sector_size -
> +							ofs);
>   					get_fl_mem((u32)part->offset + ofs,
>   						   buf_len, buf);
>   					buf_ofs = ofs;
>   					node = (void *)buf;
>   				}
> -				if (!inode_crc((struct jffs2_raw_inode *) node))
> -				       break;
> +				if (!inode_crc((struct jffs2_raw_inode *)node))
> +					break;
>
>   				if (insert_node(&pL->frag, (u32) part->offset +
>   						ofs) == NULL) {
> @@ -1698,6 +1709,11 @@ jffs2_1pass_build_lists(struct part_info * part)
>   							((struct
>   							 jffs2_raw_dirent *)
>   							node)->nsize) {
> +					buf_len = min_t(uint32_t,
> +							node->totlen,
> +							sector_ofs +
> +							part->sector_size -
> +							ofs);
>   					get_fl_mem((u32)part->offset + ofs,
>   						   buf_len, buf);
>   					buf_ofs = ofs;
>

[U-Boot] [PATCH 6/8] JFFS2: Change scansize to match linux kernel

[Heiko Schocher invitel]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> The scan code is similar to the linux kernel, but the kernel defines a much
> smaller size to scan through before deciding a sector is blank. Assuming
> that what is in the kernel is OK, make these two match.
>
> On its own, this change makes no difference to scanning of any sectors
> which have a clean marker at the beginning, since the entire sector is not
> blank.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 10bd7be..d78fb06 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -1472,7 +1472,7 @@ dump_dirents(struct b_lists *pL)
>   }
>   #endif
>
> -#define DEFAULT_EMPTY_SCAN_SIZE	4096
> +#define DEFAULT_EMPTY_SCAN_SIZE	256
>
>   static inline uint32_t EMPTY_SCAN_SIZE(uint32_t sector_size)
>   {
>

[U-Boot] [PATCH 7/8] JFFS2: Use CLEANMARKER to reduce scanning time

[Heiko Schocher invitel]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> If a sector has a CLEANMARKER at the beginning, it indicates that the
> entire sector has been erased. Therefore, if this is found, we can skip the
> entire block. This was not being done before this patch.
>
> The code now does the same as the kernel does when encountering a
> CLEANMARKER. It still checks that the next few words are FFFFFFFF, and if
> so, the block is assumed to be empty, and so is skipped.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 22 ++++++++++++++++++++++
>   1 file changed, 22 insertions(+)

Beside of your comment style

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index d78fb06..26a748f 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -1520,6 +1520,8 @@ jffs2_1pass_build_lists(struct part_info * part)
>   		uint32_t sumlen;
>   		int ret;
>   #endif
> +		/* Indicates a sector with a CLEANMARKER was found */
> +		int clean_sector = 0;
>
>   		/* Set buf_size to maximum length */
>   		buf_size = DEFAULT_EMPTY_SCAN_SIZE;
> @@ -1643,6 +1645,13 @@ jffs2_1pass_build_lists(struct part_info * part)
>   					ofs += 4;
>   				}
>   				/* Ran off end. */
> +				/* If this sector had a clean marker at the
> +				 * beginning, and immediately following this
> +				 * have been a bunch of FF bytes, treat the
> +				 * entire sector as empty.
> +				 */
> +				if (clean_sector)
> +					break;
>
>   				/* See how much more there is to read in this
>   				 * eraseblock...
> @@ -1664,6 +1673,10 @@ jffs2_1pass_build_lists(struct part_info * part)
>   				buf_ofs = ofs;
>   				goto more_empty;
>   			}
> +			/* Found something not erased in the sector, so reset
> +			 * the 'clean_sector' flag.
> +			 */
> +			clean_sector = 0;
>   			if (node->magic != JFFS2_MAGIC_BITMASK ||
>   					!hdr_crc(node)) {
>   				ofs += 4;
> @@ -1745,6 +1758,15 @@ jffs2_1pass_build_lists(struct part_info * part)
>   						"%d != %zu\n",
>   						node->totlen,
>   						sizeof(struct jffs2_unknown_node));
> +				if ((node->totlen ==
> +				     sizeof(struct jffs2_unknown_node)) &&
> +				    (ofs == sector_ofs)) {
> +					/* Found a CLEANMARKER at the beginning
> +					 * of the sector. It's in the correct
> +					 * place with correct size and CRC.
> +					 */
> +					clean_sector = 1;
> +				}
>   				break;
>   			case JFFS2_NODETYPE_PADDING:
>   				if (node->totlen < sizeof(struct jffs2_unknown_node))
>

[U-Boot] [PATCH 7/8] JFFS2: Use CLEANMARKER to reduce scanning time

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> If a sector has a CLEANMARKER at the beginning, it indicates that the
> entire sector has been erased. Therefore, if this is found, we can skip the
> entire block. This was not being done before this patch.
>
> The code now does the same as the kernel does when encountering a
> CLEANMARKER. It still checks that the next few words are FFFFFFFF, and if
> so, the block is assumed to be empty, and so is skipped.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/jffs2_1pass.c | 22 ++++++++++++++++++++++
>   1 file changed, 22 insertions(+)

Beside of your comment style

Reviewed-by: Heiko Schocher <hs@denx.de>

bye,
Heiko
>
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index d78fb06..26a748f 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -1520,6 +1520,8 @@ jffs2_1pass_build_lists(struct part_info * part)
>   		uint32_t sumlen;
>   		int ret;
>   #endif
> +		/* Indicates a sector with a CLEANMARKER was found */
> +		int clean_sector = 0;
>
>   		/* Set buf_size to maximum length */
>   		buf_size = DEFAULT_EMPTY_SCAN_SIZE;
> @@ -1643,6 +1645,13 @@ jffs2_1pass_build_lists(struct part_info * part)
>   					ofs += 4;
>   				}
>   				/* Ran off end. */
> +				/* If this sector had a clean marker at the
> +				 * beginning, and immediately following this
> +				 * have been a bunch of FF bytes, treat the
> +				 * entire sector as empty.
> +				 */
> +				if (clean_sector)
> +					break;
>
>   				/* See how much more there is to read in this
>   				 * eraseblock...
> @@ -1664,6 +1673,10 @@ jffs2_1pass_build_lists(struct part_info * part)
>   				buf_ofs = ofs;
>   				goto more_empty;
>   			}
> +			/* Found something not erased in the sector, so reset
> +			 * the 'clean_sector' flag.
> +			 */
> +			clean_sector = 0;
>   			if (node->magic != JFFS2_MAGIC_BITMASK ||
>   					!hdr_crc(node)) {
>   				ofs += 4;
> @@ -1745,6 +1758,15 @@ jffs2_1pass_build_lists(struct part_info * part)
>   						"%d != %zu\n",
>   						node->totlen,
>   						sizeof(struct jffs2_unknown_node));
> +				if ((node->totlen ==
> +				     sizeof(struct jffs2_unknown_node)) &&
> +				    (ofs == sector_ofs)) {
> +					/* Found a CLEANMARKER at the beginning
> +					 * of the sector. It's in the correct
> +					 * place with correct size and CRC.
> +					 */
> +					clean_sector = 1;
> +				}
>   				break;
>   			case JFFS2_NODETYPE_PADDING:
>   				if (node->totlen < sizeof(struct jffs2_unknown_node))
>

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 8/8] JFFS2: Use merge sort when parsing filesystem

[Heiko Schocher denx]

Hello Mark,

Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
> When building the file system the existing code does an insertion into
> a linked list. It attempts to speed this up by keeping a pointer to
> where the last entry was inserted but it's still slow.
>
> Now the nodes are just inserted into the list without searching
> through for the correct place. This unsorted list is then sorted once
> using mergesort after all the entries have been added to the list.
> This speeds up the scanning of the flash file system considerably.
>
> Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
> ---
>
>   fs/jffs2/Makefile        |  1 +
>   fs/jffs2/jffs2_1pass.c   | 47 ++++++++------------------------
>   fs/jffs2/jffs2_private.h |  4 +++
>   fs/jffs2/mergesort.c     | 70 ++++++++++++++++++++++++++++++++++++++++++++++++
>   4 files changed, 86 insertions(+), 36 deletions(-)
>   create mode 100644 fs/jffs2/mergesort.c
>
> diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
> index 4cb0600..90524ba 100644
> --- a/fs/jffs2/Makefile
> +++ b/fs/jffs2/Makefile
> @@ -10,4 +10,5 @@ obj-y += compr_rtime.o
>   obj-y += compr_rubin.o
>   obj-y += compr_zlib.o
>   obj-y += jffs2_1pass.o
> +obj-y += mergesort.o
>   obj-y += mini_inflate.o
> diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
> index 26a748f..a456650 100644
> --- a/fs/jffs2/jffs2_1pass.c
> +++ b/fs/jffs2/jffs2_1pass.c
> @@ -125,7 +125,6 @@
>
>   #include "jffs2_private.h"
>
> -

This change has nothing to do with your commit message ...

>   #define	NODE_CHUNK	1024	/* size of memory allocation chunk in b_nodes */
>   #define	SPIN_BLKSIZE	18	/* spin after having scanned 1<<BLKSIZE bytes */
>
> @@ -545,49 +544,19 @@ static struct b_node *
>   insert_node(struct b_list *list, u32 offset)
>   {
>   	struct b_node *new;
> -#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
> -	struct b_node *b, *prev;
> -#endif
>
>   	if (!(new = add_node(list))) {
>   		putstr("add_node failed!\r\n");
>   		return NULL;
>   	}
>   	new->offset = offset;
> +	new->next = NULL;
>
> -#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
> -	if (list->listTail != NULL && list->listCompare(new, list->listTail))
> -		prev = list->listTail;
> -	else if (list->listLast != NULL && list->listCompare(new, list->listLast))
> -		prev = list->listLast;
> +	if (list->listTail != NULL)
> +		list->listTail->next = new;
>   	else
> -		prev = NULL;
> -
> -	for (b = (prev ? prev->next : list->listHead);
> -	     b != NULL && list->listCompare(new, b);
> -	     prev = b, b = b->next) {
> -		list->listLoops++;
> -	}
> -	if (b != NULL)
> -		list->listLast = prev;
> -
> -	if (b != NULL) {
> -		new->next = b;
> -		if (prev != NULL)
> -			prev->next = new;
> -		else
> -			list->listHead = new;
> -	} else
> -#endif
> -	{
> -		new->next = (struct b_node *) NULL;
> -		if (list->listTail != NULL) {
> -			list->listTail->next = new;
> -			list->listTail = new;
> -		} else {
> -			list->listTail = list->listHead = new;
> -		}
> -	}
> +		list->listHead = new;
> +	list->listTail = new;
>
>   	return new;
>   }
> @@ -1788,6 +1757,12 @@ jffs2_1pass_build_lists(struct part_info * part)
>   	}
>
>   	free(buf);
> +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
> +	/* Sort the lists.
> +	 */
> +	sort_list(&pL->frag);
> +	sort_list(&pL->dir);
> +#endif
>   	putstr("\b\b done.\r\n");		/* close off the dots */
>
>   	/* We don't care if malloc failed - then each read operation will
> diff --git a/fs/jffs2/jffs2_private.h b/fs/jffs2/jffs2_private.h
> index 658b325..06b6ca2 100644
> --- a/fs/jffs2/jffs2_private.h
> +++ b/fs/jffs2/jffs2_private.h
> @@ -98,4 +98,8 @@ data_crc(struct jffs2_raw_inode *node)
>   	}
>   }
>
> +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
> +/* External merge sort. */
> +int sort_list(struct b_list *list);
> +#endif
>   #endif /* jffs2_private.h */
> diff --git a/fs/jffs2/mergesort.c b/fs/jffs2/mergesort.c
> new file mode 100644
> index 0000000..10ecc8d
> --- /dev/null
> +++ b/fs/jffs2/mergesort.c
> @@ -0,0 +1,70 @@
> +/*
> + * This file is copyright 2001 Simon Tatham.
> + * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
> + *
> + * Permission is hereby granted, free of charge, to any person
> + * obtaining a copy of this software and associated documentation
> + * files (the "Software"), to deal in the Software without
> + * restriction, including without limitation the rights to use,
> + * copy, modify, merge, publish, distribute, sublicense, and/or
> + * sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following
> + * conditions:
> + *
> + * The above copyright notice and this permission notice shall be
> + * included in all copies or substantial portions of the Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
> + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
> + * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
> + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
> + * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
> + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
> + * SOFTWARE.
> + */

Could you replace this license text with a SPDX-License-Identifier?
And a description from where this code comes?
See here:
http://www.denx.de/wiki/view/U-Boot/Patches#Attributing_Code_Copyrights_Sign

Thanks!

> +
> +#include <common.h>
> +#include "jffs2_private.h"
> +
> +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)

you can move this into fs/jffs2/Makefile

obj-$(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) += mergesort.o

and remove this
"#if defined ..." here ...

bye,
Heiko
> +int sort_list(struct b_list *list)
> +{
> +	struct b_node *p, *q, *e, **tail;
> +	int k, psize, qsize;
> +
> +	if (!list->listHead)
> +		return 0;
> +
> +	for (k = 1; k < list->listCount; k *= 2) {
> +		tail = &list->listHead;
> +		for (p = q = list->listHead; p; p = q) {
> +			/* step 'k' places from p; */
> +			for (psize = 0; q && psize < k; psize++)
> +				q = q->next;
> +			qsize = k;
> +
> +			/* two lists, merge them. */
> +			while (psize || (qsize && q)) {
> +				/* merge the next element */
> +				if (psize == 0 ||
> +				    ((qsize && q) &&
> +				     list->listCompare(p, q))) {
> +					/* p is empty, or p > q, so q next */
> +					e = q;
> +					q = q->next;
> +					qsize--;
> +				} else {
> +					e = p;
> +					p = p->next;
> +					psize--;
> +				}
> +				e->next = NULL; /* break accidental loops. */
> +				*tail = e;
> +				tail = &e->next;
> +			}
> +		}
> +	}
> +	return 0;
> +}
> +#endif
>

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany

[U-Boot] [PATCH 0/8] JFFS2 fixes and performance improvements

[Wolfgang Denk]

Dear Mark,

In message <1435554149-18042-1-git-send-email-mark.tomlinson@alliedtelesis.co.nz> you wrote:
> These patches fix bugs and improve performance of JFFS2. Some of these
> improvements can already be found in old mailing lists, but for some
> reason they have not made their way into the u-boot source. I have the
> feeling that any one of these patches didn't show enough performance gain
> to warrant adding it to the source. I am hopeful that together, all these
> patches can be seen to make a big difference.

It would be a good thing to know where exactly these changes are
coming from?  Is this independent optoimization within U-Boot only, or
did you for example try to synchronize the U-Boot code against a
recent Linux kernel version?  I feel that would be a pretty useful
undertaking...

Best regards,

Wolfgang Denk

-- 
DENX Software Engineering GmbH,      Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
Bankers do it with interest (penalty for early withdrawal).