[PATCH 0/7] fs: jffs2: improve one-pass reader and add metadata

[PATCH 0/7] fs: jffs2: improve one-pass reader and add metadata

[Wagner Popov dos Santos]

This series improves the robustness of the JFFS2 one-pass reader and
introduces CONFIG_JFFS2_CACHE_TO_SPEED_UP, an optional directory
metadata cache designed to reduce repeated flash reads during sorting,
directory listing, and pathname lookup when loading files.

With the cache enabled, directory entry names are interned in a
configurable hash table during both full and summary-based filesystem
scans. Cached names, inode numbers, and parent inode numbers allow
lookup and sorting to use in-memory metadata. When fragment sorting
is enabled, listing can also identify successive versions of the same
directory entry through interned-name pointer equality before reading
the selected raw node.

The optimization trades additional RAM for fewer directory entry reads.
Names are allocated from 10 KiB pools, and
CONFIG_JFFS2_CACHE_NAMES_HASH_WIDTH controls the hash table size,
defaulting to 256 buckets. Cache memory is released with the filesystem
cache, and raw-node comparisons remain available when names are not
cached. Listing still reads selected directory entries and inode
information, and loading still reads file data.

The preceding fixes address unchecked node reads, missing inode
fragments, incomplete file loads incorrectly reported as successful,
unsafe symlink target handling, leaked dirents on comparison errors,
and incorrect handling of the selected raw dirent during listing.
These fixes apply independently of the new cache option.

The final patch corrects the sorting documentation to describe the
existing post-scan merge sort with O(n log n) comparisons. This series
does not introduce a new sorting algorithm; its performance focus is
reducing flash accesses through cached metadata.

Wagner Popov dos Santos (7):
  fs: jffs2: check cached-node reads before dereferencing
  fs: jffs2: reject missing fragments and fail incomplete loads
  fs: jffs2: resolve symlink targets safely
  fs: jffs2: release dirents on comparison read errors
  fs: jffs2: retain the selected raw dirent when listing
  fs: jffs2: cache directory metadata during one-pass scans
  fs: jffs2: document post-scan merge sort

 fs/jffs2/Kconfig         |  29 ++++-
 fs/jffs2/jffs2_1pass.c   | 261 +++++++++++++++++++++++++++++++++++++--
 fs/jffs2/jffs2_private.h |  30 +++++
 3 files changed, 308 insertions(+), 12 deletions(-)

-- 
2.43.0

[PATCH 1/7] fs: jffs2: check cached-node reads before dereferencing

[Wagner Popov dos Santos]

The one-pass reader assumes that get_node_mem() and get_fl_mem() always
return valid pointers. Read or allocation failures can therefore cause
NULL pointer dereferences during file loading, directory lookup and
listing, sorting, or symbolic link resolution.

Check the returned pointers before accessing raw nodes and report the
affected inode or flash offset. Return an error if the latest inode
header cannot be read, and skip unreadable entries where the operation
can continue examining the remaining nodes.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/jffs2_1pass.c | 59 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 60dacf13448..f21def1821d 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -604,6 +604,17 @@ static int compare_dirents(struct b_node *new, struct b_node *old)
 	int cmp;
 	int ret;
 
+	if(!jNew) {
+		printf("%s: failed to get new record memory at offset 0x%08x\n",
+		       __func__, (u32)new->offset);
+		return 0;
+	}
+	if(!jOld) {
+		printf("%s: failed to get old record memory at offset 0x%08x\n",
+		       __func__, (u32)old->offset);
+		return 1;
+	}
+
 	if (jNew->pino != jOld->pino) {
 		/* ascending sort by pino */
 		ret = jNew->pino > jOld->pino;
@@ -704,6 +715,11 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 	if (latestOffset >= 0) {
 		jNode = (struct jffs2_raw_inode *)get_fl_mem(latestOffset,
 			sizeof(struct jffs2_raw_inode), pL->readbuf);
+		if(!jNode) {
+			printf("%s: failed to get latest offset at 0x%08x\n",
+			       __func__, (u32)latestOffset);
+			return -1;
+		}
 		totalSize = jNode->isize;
 		put_fl_mem(jNode, pL->readbuf);
 	}
@@ -724,6 +740,11 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 			jNode = (struct jffs2_raw_inode *)get_fl_mem(b->offset,
 					sizeof(struct jffs2_raw_inode),
 					pL->readbuf);
+			if(!jNode) {
+				printf("%s: failed to get memory at 0x%X\n",
+				       __func__, b->offset);
+				continue;
+			}
 #if 0
 			putLabeledWord("\r\n\r\nread_inode: totlen = ", jNode->totlen);
 			putLabeledWord("read_inode: inode = ", jNode->ino);
@@ -745,6 +766,11 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 				put_fl_mem(jNode, pL->readbuf);
 				jNode = (struct jffs2_raw_inode *)
 					get_node_mem(b->offset, pL->readbuf);
+				if (!jNode) {
+					printf("%s: failed to get node at 0x%X\n",
+					       __func__, b->offset);
+					continue;
+				}
 				src = ((uchar *)jNode) +
 					sizeof(struct jffs2_raw_inode);
 				/* ignore data behind latest known EOF */
@@ -830,6 +856,11 @@ jffs2_1pass_find_inode(struct b_lists * pL, const char *name, u32 pino)
 	for(b = pL->dir.listHead; b; b = b->next, counter++) {
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
+		if (!jDir) {
+			printf("%s: failed to get jDir memory at 0x%X\n",
+			       __func__, b->offset);
+			continue;
+		}
 		if ((pino == jDir->pino) && (len == jDir->nsize) &&
 		    (!strncmp((char *)jDir->name, name, len))) {	/* a match */
 			if (jDir->version < version) {
@@ -957,6 +988,11 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 
 			jDir = (struct jffs2_raw_dirent *)
 				get_node_mem(b->offset, pL->readbuf);
+			if (!jDir) {
+				printf("%s: failed to get jDir memory at 0x%X\n",
+				       __func__, b->offset);
+				continue;
+			}
 #ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
 			/* Check for more recent versions of this file */
 			int match;
@@ -967,6 +1003,11 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 					break;
 				jDirNext = (struct jffs2_raw_dirent *)
 					get_node_mem(next->offset, NULL);
+				if (!jDirNext) {
+					printf("%s: failed to get jDir memory at 0x%X\n",
+					       __func__, next->offset);
+					break;
+				}
 				match = jDirNext->pino == jDir->pino &&
 					jDirNext->nsize == jDir->nsize &&
 					strncmp((char *)jDirNext->name,
@@ -1002,6 +1043,13 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 						   sizeof(*jNode),
 						   NULL);
 
+			if (!jNode) {
+				printf("%s: failed to get jNode for inode %u\n",
+				       __func__, jDir->ino);
+				put_fl_mem(jDir, pL->readbuf);
+				continue;
+			}
+
 			dump_inode(pL, jDir, jNode);
 			put_fl_mem(jNode, NULL);
 
@@ -1086,6 +1134,11 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 	for(b = pL->dir.listHead; b; b = b->next) {
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
+		if (!jDir) {
+			printf("%s: failed to get jDir memory at 0x%X\n",
+			       __func__, b->offset);
+			continue;
+		}
 		if (ino == jDir->ino) {
 			if (jDir->version < version) {
 				put_fl_mem(jDir, pL->readbuf);
@@ -1116,6 +1169,12 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 	while (b2) {
 		jNode = (struct jffs2_raw_inode *) get_node_mem(b2->offset,
 								pL->readbuf);
+		if (!jNode) {
+			printf("%s: failed to get jNode at 0x%X\n",
+			       __func__, b2->offset);
+			b2 = b2->next;
+			continue;
+		}
 		if (jNode->ino == jDirFoundIno) {
 			src = (unsigned char *)jNode + sizeof(struct jffs2_raw_inode);
 
-- 
2.43.0

[PATCH 2/7] fs: jffs2: reject missing fragments and fail incomplete loads

[Wagner Popov dos Santos]

jffs2_1pass_list_inodes() initializes the selected fragment offset to
-1, but previously passed it to the flash reader when no inode fragment
matched a directory entry. Check that a fragment was found, report the
affected inode, and skip the inconsistent entry before reading flash.

Also fail file loading when a fragment header or payload cannot be
read. Skipping these failures could leave incomplete data in memory
while returning the full file size, causing fsload to report success.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/jffs2_1pass.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index f21def1821d..6dedecfe741 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -740,10 +740,10 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 			jNode = (struct jffs2_raw_inode *)get_fl_mem(b->offset,
 					sizeof(struct jffs2_raw_inode),
 					pL->readbuf);
-			if(!jNode) {
+			if (!jNode) {
 				printf("%s: failed to get memory at 0x%X\n",
 				       __func__, b->offset);
-				continue;
+				return -1;
 			}
 #if 0
 			putLabeledWord("\r\n\r\nread_inode: totlen = ", jNode->totlen);
@@ -769,7 +769,7 @@ jffs2_1pass_read_inode(struct b_lists *pL, u32 inode, char *dest)
 				if (!jNode) {
 					printf("%s: failed to get node at 0x%X\n",
 					       __func__, b->offset);
-					continue;
+					return -1;
 				}
 				src = ((uchar *)jNode) +
 					sizeof(struct jffs2_raw_inode);
@@ -1036,6 +1036,13 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 				}
 			}
 
+			if (i_offset < 0) {
+				printf("%s: failed to find a valid fragment for inode %u\n",
+				       __func__, jDir->ino);
+				put_fl_mem(jDir, pL->readbuf);
+				continue;
+			}
+
 			if (jDir->type == DT_LNK)
 				jNode = get_node_mem(i_offset, NULL);
 			else
-- 
2.43.0

[PATCH 3/7] fs: jffs2: resolve symlink targets safely

[Wagner Popov dos Santos]

The symlink resolver stops at the first matching inode fragment even
when fragment sorting is enabled, potentially selecting an older target.

Continue through sorted fragments so the last matching version supplies
the target, while retaining the early exit for unsorted lists. Filter
unrelated fragments by their cached inode number before reading flash,
and advance the list when skipping them.

Reject targets that do not fit in the local buffer before copying them.
Initialize the buffer so that a missing or unreadable target does not
pass uninitialized stack data to pathname lookup.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/jffs2_1pass.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 6dedecfe741..f32846442d9 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -1132,7 +1132,7 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 	u8 jDirFoundType = 0;
 	u32 jDirFoundIno = 0;
 	u32 jDirFoundPino = 0;
-	char tmp[256];
+	char tmp[256] = { 0 };
 	u32 version = 0;
 	u32 pino;
 	unsigned char *src;
@@ -1174,6 +1174,10 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 	/* it's a soft link so we follow it again. */
 	b2 = pL->frag.listHead;
 	while (b2) {
+		if (b2->ino != jDirFoundIno) {
+			b2 = b2->next;
+			continue;
+		}
 		jNode = (struct jffs2_raw_inode *) get_node_mem(b2->offset,
 								pL->readbuf);
 		if (!jNode) {
@@ -1191,10 +1195,20 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 			putnstr(src, jNode->dsize);
 			putstr("\r\n");
 #endif
+			if (jNode->dsize >= sizeof(tmp)) {
+				printf("%s: soft link target too long: dsize = %u\n",
+				       __func__, jNode->dsize);
+				put_fl_mem(jNode, pL->readbuf);
+				return 0;
+			}
+
 			strncpy(tmp, (char *)src, jNode->dsize);
 			tmp[jNode->dsize] = '\0';
+#ifndef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
+			/* don't search for a newer soft link target */
 			put_fl_mem(jNode, pL->readbuf);
 			break;
+#endif
 		}
 		b2 = b2->next;
 		put_fl_mem(jNode, pL->readbuf);
-- 
2.43.0

[PATCH 4/7] fs: jffs2: release dirents on comparison read errors

[Wagner Popov dos Santos]

Release the other raw dirent before returning when one comparison read
fails, avoiding leaks during sorting. Handle failure to read both nodes
without attempting to release a missing node.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/jffs2_1pass.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index f32846442d9..fe44271b270 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -607,11 +607,14 @@ static int compare_dirents(struct b_node *new, struct b_node *old)
 	if(!jNew) {
 		printf("%s: failed to get new record memory at offset 0x%08x\n",
 		       __func__, (u32)new->offset);
+		if(jOld)
+			put_fl_mem(jOld, NULL);
 		return 0;
 	}
 	if(!jOld) {
 		printf("%s: failed to get old record memory at offset 0x%08x\n",
 		       __func__, (u32)old->offset);
+		put_fl_mem(jNew, NULL);
 		return 1;
 	}
 
-- 
2.43.0

[PATCH 5/7] fs: jffs2: retain the selected raw dirent when listing

[Wagner Popov dos Santos]

Retain the latest raw dirent instead of copying its header into the
previous node. This avoids writing to memory-mapped flash and keeps the
selected name and metadata in the same node.

Release the previous node when replacing it, or the next node when it
does not match.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/jffs2_1pass.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index fe44271b270..0021697c907 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -1019,10 +1019,11 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 				if (match) {
 					/* Use next. It is more recent */
 					b = next;
-					/* Update buffer with the new info */
-					*jDir = *jDirNext;
+					put_fl_mem(jDir, pL->readbuf);
+					jDir = jDirNext;
+				} else {
+					put_fl_mem(jDirNext, NULL);
 				}
-				put_fl_mem(jDirNext, NULL);
 			} while (match);
 #endif
 			if (jDir->ino == 0) {
-- 
2.43.0

[PATCH 6/7] fs: jffs2: cache directory metadata during one-pass scans

[Wagner Popov dos Santos]

Intern directory entry names in a configurable hash table during full
and summary-based scans. Allocate names from 10 KiB pools and cache
inode numbers, parent inode numbers, and name pointers.

Use cached metadata for lookup, sorting, and listing. Group sorted
versions by interned-name pointer equality, while preserving raw dirent
comparisons when names are not cached and checking deletion after
selecting the latest entry.

Add Kconfig options for the cache and hash width, document remaining
reads and memory costs, and free the name pools with the filesystem
cache.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/Kconfig         |  21 +++++
 fs/jffs2/jffs2_1pass.c   | 164 ++++++++++++++++++++++++++++++++++++++-
 fs/jffs2/jffs2_private.h |  30 +++++++
 3 files changed, 214 insertions(+), 1 deletion(-)

diff --git a/fs/jffs2/Kconfig b/fs/jffs2/Kconfig
index dede59ee336..2fe2ce96eae 100644
--- a/fs/jffs2/Kconfig
+++ b/fs/jffs2/Kconfig
@@ -30,3 +30,24 @@ config SYS_JFFS2_SORT_FRAGMENTS
 	  though.  Sorting is done while inserting into the fragment list,
 	  which is more or less a bubble sort. That algorithm is known to be
 	  O(n^2), thus you should really consider if you can avoid it!
+
+config JFFS2_CACHE_TO_SPEED_UP
+	bool "Enable JFFS2 extra cache to speed up sort, list and load"
+	depends on FS_JFFS2
+	help
+	  Cache JFFS2 directory entry names while building the filesystem
+	  lists. This reduces directory entry reads when sorting, listing or
+	  loading files, but listing still reads the selected directory entry
+	  nodes. Additional memory is used by the hash bucket array, name
+	  pools and extra metadata in each cached inode and directory entry.
+
+config JFFS2_CACHE_NAMES_HASH_WIDTH
+	int "Hash width for cached names"
+	depends on JFFS2_CACHE_TO_SPEED_UP
+	range 4 16
+	default 8
+	help
+	  Selects the number of bits used from the name CRC to select a hash
+	  bucket. The number of buckets is 2^value. With the value 16, the
+	  bucket array uses 256 KiB on 32-bit targets plus the blocks for the
+	  names.
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 0021697c907..021c524f444 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -409,6 +409,79 @@ static inline void *get_node_mem_nor(u32 off, void *ext_buf)
 }
 #endif
 
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+
+/*
+ * To avoid frequent small memory allocations, allocate memory in
+ * larger blocks.
+ */
+#define MEM_BLK_NAMES_SIZE   (10 * 1024)
+
+static void jffs2_cache_name_free(struct jffs2_name_cache *cache)
+{
+	struct jffs2_name_pool *pool, *next;
+
+	for (pool = cache->pools; pool; pool = next) {
+		next = pool->next;
+		free(pool);
+	}
+	cache->pools = NULL;
+	memset(cache->buckets, 0, sizeof(cache->buckets));
+}
+
+static void *jffs2_cache_name_alloc(struct jffs2_name_cache *cache, u32 size)
+{
+	struct jffs2_name_pool *pool = cache->pools;
+	void *ret;
+
+	if (size > MEM_BLK_NAMES_SIZE)
+		return NULL;
+
+	if (!pool || pool->remaining < size) {
+		pool = malloc(sizeof(*pool) + MEM_BLK_NAMES_SIZE);
+		if (!pool) {
+			printf("%s: Failed to allocate memory for name cache!\n",
+			       __func__);
+			return NULL;
+		}
+		pool->cur = (char *)(pool + 1);
+		pool->remaining = MEM_BLK_NAMES_SIZE;
+		pool->next = cache->pools;
+		cache->pools = pool;
+	}
+
+	ret = pool->cur;
+	pool->cur += size;
+	pool->remaining -= size;
+	return ret;
+}
+
+static const char *jffs2_cache_name_add(struct jffs2_name_cache *cache,
+					 u32 name_crc, const char *name, u8 len)
+{
+	struct jffs2_cached_name *cached;
+	const u32 bucket_idx = name_crc & (JFFS2_CACHE_NAME_BUCKETS - 1);
+	const u32 alloc_size = ALIGN(sizeof(*cached) + 1 + len, sizeof(uintptr_t));
+
+	for (cached = cache->buckets[bucket_idx]; cached;
+	     cached = cached->next) {
+		if (strlen(cached->name) == len)
+			if (!memcmp(cached->name, name, len))
+				return cached->name;
+	}
+
+	cached = jffs2_cache_name_alloc(cache, alloc_size);
+	if (!cached)
+		return NULL;
+
+	memcpy(cached->name, name, len);
+	cached->name[len] = '\0';
+	cached->next = cache->buckets[bucket_idx];
+	cache->buckets[bucket_idx] = cached;
+	return cached->name;
+}
+#endif
+
 /*
  * Generic jffs2 raw memory and node read routines.
  *
@@ -599,6 +672,25 @@ static int compare_dirents(struct b_node *new, struct b_node *old)
 	 * being read. This makes most comparisons much quicker as only one
 	 * or two entries from the node will be used most of the time.
 	 */
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+	if (new->pino != old->pino) {
+		/* ascending sort by pino */
+		return new->pino > old->pino;
+	}
+
+	if (new->name && old->name) {
+		size_t new_len = strlen(new->name);
+		size_t old_len = strlen(old->name);
+
+		if (new_len != old_len)
+			return new_len > old_len;
+		if (new->name != old->name)
+			return strcmp(new->name, old->name) > 0;
+
+		/* Duplicate names are sorted by ascending version. */
+		return new->version > old->version;
+	}
+#endif
 	struct jffs2_raw_dirent *jNew = get_node_mem(new->offset, NULL);
 	struct jffs2_raw_dirent *jOld = get_node_mem(old->offset, NULL);
 	int cmp;
@@ -659,6 +751,9 @@ jffs2_free_cache(struct part_info *part)
 		pL = (struct b_lists *)part->jffs2_priv;
 		free_nodes(&pL->frag);
 		free_nodes(&pL->dir);
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+		jffs2_cache_name_free(&pL->names);
+#endif
 		free(pL->readbuf);
 		free(pL);
 		part->jffs2_priv = NULL;
@@ -857,6 +952,20 @@ jffs2_1pass_find_inode(struct b_lists * pL, const char *name, u32 pino)
 	counter = 0;
 	/* we need to search all and return the inode with the highest version */
 	for(b = pL->dir.listHead; b; b = b->next, counter++) {
+		if (b->pino != pino)
+			continue;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+		if (b->name) {
+			if (strcmp(b->name, name) != 0)
+				continue;
+			if (b->version < version)
+				continue;
+			inode = b->ino;
+			version = b->version;
+			continue;
+		}
+#endif
+
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
 		if (!jDir) {
@@ -988,7 +1097,17 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 			int i_offset = -1;
 			struct jffs2_raw_inode *jNode = NULL;
 			struct b_node *b2;
-
+#if defined(CONFIG_JFFS2_CACHE_TO_SPEED_UP) && \
+	defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+			struct b_node *next;
+			for (next = b->next; next; next = b->next) {
+				if (b->name && next->pino == pino &&
+				    next->name == b->name)
+					b = next;
+				else
+					break;
+			}
+#endif
 			jDir = (struct jffs2_raw_dirent *)
 				get_node_mem(b->offset, pL->readbuf);
 			if (!jDir) {
@@ -1004,6 +1123,12 @@ jffs2_1pass_list_inodes(struct b_lists * pL, u32 pino)
 				struct jffs2_raw_dirent *jDirNext;
 				if (!next)
 					break;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+				if (b->name && next->name &&
+				    (next->pino != pino ||
+				     next->name != b->name))
+					break;
+#endif
 				jDirNext = (struct jffs2_raw_dirent *)
 					get_node_mem(next->offset, NULL);
 				if (!jDirNext) {
@@ -1143,6 +1268,13 @@ jffs2_1pass_resolve_inode(struct b_lists * pL, u32 ino)
 
 	/* we need to search all and return the inode with the highest version */
 	for(b = pL->dir.listHead; b; b = b->next) {
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+		if (b->ino != ino)
+			continue;
+		if (b->version < version)
+			continue;
+#endif
+
 		jDir = (struct jffs2_raw_dirent *) get_node_mem(b->offset,
 								pL->readbuf);
 		if (!jDir) {
@@ -1369,6 +1501,10 @@ static int jffs2_sum_process_sum_data(struct part_info *part, uint32_t offset,
 						b->ino = sum_get_unaligned32(
 							&spi->inode);
 						b->datacrc = CRC_UNKNOWN;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+						b->pino = 0;
+						b->name = NULL;
+#endif
 					}
 
 					sp += JFFS2_SUMMARY_INODE_SIZE;
@@ -1377,6 +1513,10 @@ static int jffs2_sum_process_sum_data(struct part_info *part, uint32_t offset,
 				}
 				case JFFS2_NODETYPE_DIRENT: {
 					struct jffs2_sum_dirent_flash *spd;
+	#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+					u32 name_crc;
+	#endif
+
 					spd = sp;
 					if (pass) {
 						b = insert_node(&pL->dir);
@@ -1390,6 +1530,17 @@ static int jffs2_sum_process_sum_data(struct part_info *part, uint32_t offset,
 							&spd->version);
 						b->pino = sum_get_unaligned32(
 							&spd->pino);
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+						b->ino = sum_get_unaligned32(
+							&spd->ino);
+						name_crc = crc32_no_comp(0,
+							(const unsigned char *)spd->name,
+							spd->nsize);
+						b->name = jffs2_cache_name_add(
+							&pL->names, name_crc,
+							(const char *)spd->name,
+							spd->nsize);
+#endif
 						b->datacrc = CRC_UNKNOWN;
 					}
 
@@ -1812,6 +1963,10 @@ jffs2_1pass_build_lists(struct part_info * part)
 				b->version = node->i.version;
 				b->ino = node->i.ino;
 				b->datacrc = CRC_UNKNOWN;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+				b->name = NULL;
+				b->pino = 0;
+#endif
 				if (max_totlen < node->u.totlen)
 					max_totlen = node->u.totlen;
 				break;
@@ -1851,6 +2006,13 @@ jffs2_1pass_build_lists(struct part_info * part)
 				b->version = node->d.version;
 				b->pino = node->d.pino;
 				b->datacrc = CRC_UNKNOWN;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+				b->ino = node->d.ino;
+				b->name = jffs2_cache_name_add(&pL->names,
+								node->d.name_crc,
+								(const char *)node->d.name,
+								node->d.nsize);
+#endif
 				if (max_totlen < node->u.totlen)
 					max_totlen = node->u.totlen;
 				counterN++;
diff --git a/fs/jffs2/jffs2_private.h b/fs/jffs2/jffs2_private.h
index 9284ab5c2c1..fcde1b9e54f 100644
--- a/fs/jffs2/jffs2_private.h
+++ b/fs/jffs2/jffs2_private.h
@@ -8,12 +8,39 @@ struct b_node {
 	struct b_node *next;
 	enum { CRC_UNKNOWN = 0, CRC_OK, CRC_BAD } datacrc;
 	u32 version;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+	u32 ino; /* for inodes and dirents */
+	u32 pino; /* for dirents */
+	const char *name; /* for dirents */
+#else
 	union {
 		u32 ino; /* for inodes */
 		u32 pino; /* for dirents */
 	};
+#endif
+};
+
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+#define JFFS2_CACHE_NAME_BUCKETS \
+	(1U << CONFIG_JFFS2_CACHE_NAMES_HASH_WIDTH)
+
+struct jffs2_name_pool {
+	struct jffs2_name_pool *next;
+	char *cur;
+	u32 remaining;
 };
 
+struct jffs2_cached_name {
+	struct jffs2_cached_name *next;
+	char name[];
+};
+
+struct jffs2_name_cache {
+	struct jffs2_name_pool *pools;
+	struct jffs2_cached_name *buckets[JFFS2_CACHE_NAME_BUCKETS];
+};
+#endif
+
 struct b_list {
 	struct b_node *listTail;
 	struct b_node *listHead;
@@ -29,6 +56,9 @@ struct b_list {
 struct b_lists {
 	struct b_list dir;
 	struct b_list frag;
+#ifdef CONFIG_JFFS2_CACHE_TO_SPEED_UP
+	struct jffs2_name_cache names;
+#endif
 	void *readbuf;
 };
 
-- 
2.43.0

[PATCH 7/7] fs: jffs2: document post-scan merge sort

[Wagner Popov dos Santos]

Describe the existing merge sort performed after scanning, with O(n log
n) comparisons, instead of insertion-time bubble sort. Update both
Kconfig help and the related source comment, and explain how name
caching reduces directory entry reads during sorting.

Signed-off-by: Wagner Popov dos Santos <wpopov@gmail.com>
---
 fs/jffs2/Kconfig       | 8 ++++----
 fs/jffs2/jffs2_1pass.c | 5 ++---
 2 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/fs/jffs2/Kconfig b/fs/jffs2/Kconfig
index 2fe2ce96eae..6ee29af2aeb 100644
--- a/fs/jffs2/Kconfig
+++ b/fs/jffs2/Kconfig
@@ -26,10 +26,10 @@ config SYS_JFFS2_SORT_FRAGMENTS
 	  If you boot from a partition which is mounted writable, and you
 	  update your boot environment by replacing single files on that
 	  partition, you should also define CONFIG_SYS_JFFS2_SORT_FRAGMENTS.
-	  Scanning the JFFS2 filesystem takes *much* longer with this feature,
-	  though.  Sorting is done while inserting into the fragment list,
-	  which is more or less a bubble sort. That algorithm is known to be
-	  O(n^2), thus you should really consider if you can avoid it!
+	  Fragment and directory entry lists are sorted after scanning using
+	  merge sort, with O(n log n) comparisons. Sorting directory entries
+	  can require repeated flash reads. Enable JFFS2_CACHE_TO_SPEED_UP to
+	  reduce these reads.
 
 config JFFS2_CACHE_TO_SPEED_UP
 	bool "Enable JFFS2 extra cache to speed up sort, list and load"
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 021c524f444..e66cd0a571e 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -93,9 +93,8 @@
  *   if there are multiple copies of fragments for a certain file offset.
  *
  * The fragment sorting feature must be enabled by CONFIG_SYS_JFFS2_SORT_FRAGMENTS.
- * Sorting is done while adding fragments to the lists, which is more or less a
- * bubble sort. This takes a lot of time, and is most probably not an issue if
- * the boot filesystem is always mounted readonly.
+ * Sorting is done after scanning using merge sort. Directory entry comparisons
+ * may require repeated flash reads unless name caching is enabled.
  *
  * You should define it if the boot filesystem is mounted writable, and updates
  * to the boot files are done by copying files to that filesystem.
-- 
2.43.0

Re: [PATCH 0/7] fs: jffs2: improve one-pass reader and add metadata

[Tom Rini]

[-- Attachment #1: Type: text/plain, Size: 2396 bytes --]

On Tue, Nov 03, 2026 at 01:49:46PM -0300, Wagner Popov dos Santos wrote:

> This series improves the robustness of the JFFS2 one-pass reader and
> introduces CONFIG_JFFS2_CACHE_TO_SPEED_UP, an optional directory
> metadata cache designed to reduce repeated flash reads during sorting,
> directory listing, and pathname lookup when loading files.
> 
> With the cache enabled, directory entry names are interned in a
> configurable hash table during both full and summary-based filesystem
> scans. Cached names, inode numbers, and parent inode numbers allow
> lookup and sorting to use in-memory metadata. When fragment sorting
> is enabled, listing can also identify successive versions of the same
> directory entry through interned-name pointer equality before reading
> the selected raw node.
> 
> The optimization trades additional RAM for fewer directory entry reads.
> Names are allocated from 10 KiB pools, and
> CONFIG_JFFS2_CACHE_NAMES_HASH_WIDTH controls the hash table size,
> defaulting to 256 buckets. Cache memory is released with the filesystem
> cache, and raw-node comparisons remain available when names are not
> cached. Listing still reads selected directory entries and inode
> information, and loading still reads file data.
> 
> The preceding fixes address unchecked node reads, missing inode
> fragments, incomplete file loads incorrectly reported as successful,
> unsafe symlink target handling, leaked dirents on comparison errors,
> and incorrect handling of the selected raw dirent during listing.
> These fixes apply independently of the new cache option.
> 
> The final patch corrects the sorting documentation to describe the
> existing post-scan merge sort with O(n log n) comparisons. This series
> does not introduce a new sorting algorithm; its performance focus is
> reducing flash accesses through cached metadata.

First, you need to send this to the new list address,
u-boot@lists.u-boot-project.org so that it shows up in the archives,
etc, correctly. Second, what's the motivation for this series? The
initial patches in this series do likely address the various known
security issues, but as I've noted before, we're down to two platforms
using this filesystem and I would be inclined to just remove it. We
don't even build-test it in CI because it has issues being built for
64bit platforms. Thanks.

-- 
Tom

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: [PATCH 0/7] fs: jffs2: improve one-pass reader and add metadata

[Heiko Schocher]

Hi,

please resend this series on the new list:

U-Boot Mailing List <u-boot@lists.u-boot-project.org>

Thanks!

bye,
Heiko

On 03.11.26 17:49, Wagner Popov dos Santos wrote:
> This series improves the robustness of the JFFS2 one-pass reader and
> introduces CONFIG_JFFS2_CACHE_TO_SPEED_UP, an optional directory
> metadata cache designed to reduce repeated flash reads during sorting,
> directory listing, and pathname lookup when loading files.
> 
> With the cache enabled, directory entry names are interned in a
> configurable hash table during both full and summary-based filesystem
> scans. Cached names, inode numbers, and parent inode numbers allow
> lookup and sorting to use in-memory metadata. When fragment sorting
> is enabled, listing can also identify successive versions of the same
> directory entry through interned-name pointer equality before reading
> the selected raw node.
> 
> The optimization trades additional RAM for fewer directory entry reads.
> Names are allocated from 10 KiB pools, and
> CONFIG_JFFS2_CACHE_NAMES_HASH_WIDTH controls the hash table size,
> defaulting to 256 buckets. Cache memory is released with the filesystem
> cache, and raw-node comparisons remain available when names are not
> cached. Listing still reads selected directory entries and inode
> information, and loading still reads file data.
> 
> The preceding fixes address unchecked node reads, missing inode
> fragments, incomplete file loads incorrectly reported as successful,
> unsafe symlink target handling, leaked dirents on comparison errors,
> and incorrect handling of the selected raw dirent during listing.
> These fixes apply independently of the new cache option.
> 
> The final patch corrects the sorting documentation to describe the
> existing post-scan merge sort with O(n log n) comparisons. This series
> does not introduce a new sorting algorithm; its performance focus is
> reducing flash accesses through cached metadata.
> 
> Wagner Popov dos Santos (7):
>    fs: jffs2: check cached-node reads before dereferencing
>    fs: jffs2: reject missing fragments and fail incomplete loads
>    fs: jffs2: resolve symlink targets safely
>    fs: jffs2: release dirents on comparison read errors
>    fs: jffs2: retain the selected raw dirent when listing
>    fs: jffs2: cache directory metadata during one-pass scans
>    fs: jffs2: document post-scan merge sort
> 
>   fs/jffs2/Kconfig         |  29 ++++-
>   fs/jffs2/jffs2_1pass.c   | 261 +++++++++++++++++++++++++++++++++++++--
>   fs/jffs2/jffs2_private.h |  30 +++++
>   3 files changed, 308 insertions(+), 12 deletions(-)
> 

-- 
Nabla Software Engineering
HRB 40522 Augsburg
Phone: +49 821 45592596
E-Mail: office@nabladev.com
Geschäftsführer : Stefano Babic