fs: jffs2: improve one-pass reader and add metadata
cover fs: jffs2: improve one-pass reader and add metadata
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(-)
Signature · 1 line
2.43.0
PATCH 1/7 fs: jffs2: check cached-node reads before dereferencing
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.
--- fs/jffs2/jffs2_1pass.c | 59 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+)
fs/jffs2/jffs2_1pass.c +59 -0
@@ -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 );
Signature · 1 line
2.43.0
PATCH 2/7 fs: jffs2: reject missing fragments and fail incomplete loads
In reply to Wagner Popov dos Santosjffs2_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.
--- fs/jffs2/jffs2_1pass.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-)
fs/jffs2/jffs2_1pass.c +10 -3
@@ -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
Signature · 1 line
2.43.0
PATCH 3/7 fs: jffs2: resolve symlink targets safely
In reply to Wagner Popov dos SantosThe 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.
--- fs/jffs2/jffs2_1pass.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)
fs/jffs2/jffs2_1pass.c +15 -1
@@ -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);
Signature · 1 line
2.43.0
PATCH 4/7 fs: jffs2: release dirents on comparison read errors
In reply to Wagner Popov dos SantosRelease 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.
--- fs/jffs2/jffs2_1pass.c | 3 +++ 1 file changed, 3 insertions(+)
fs/jffs2/jffs2_1pass.c +3 -0
@@ -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 ; }
Signature · 1 line
2.43.0
PATCH 5/7 fs: jffs2: retain the selected raw dirent when listing
In reply to Wagner Popov dos SantosRetain 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.
--- fs/jffs2/jffs2_1pass.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
fs/jffs2/jffs2_1pass.c +4 -3
@@ -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 ) {
Signature · 1 line
2.43.0
PATCH 6/7 fs: jffs2: cache directory metadata during one-pass scans
In reply to Wagner Popov dos SantosIntern 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.
--- fs/jffs2/Kconfig | 21 +++++ fs/jffs2/jffs2_1pass.c | 164 ++++++++++++++++++++++++++++++++++++++- fs/jffs2/jffs2_private.h | 30 +++++++ 3 files changed, 214 insertions(+), 1 deletion(-)
fs/jffs2/Kconfig +21 -0
@@ -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.
fs/jffs2/jffs2_1pass.c +163 -1
236 lines not on this page · raw message
fs/jffs2/jffs2_private.h +30 -0
@@ -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; };
Signature · 1 line
2.43.0
PATCH 7/7 fs: jffs2: document post-scan merge sort
In reply to Wagner Popov dos SantosDescribe 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.
--- fs/jffs2/Kconfig | 8 ++++---- fs/jffs2/jffs2_1pass.c | 5 ++--- 2 files changed, 6 insertions(+), 7 deletions(-)
fs/jffs2/Kconfig +4 -4
@@ -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"
fs/jffs2/jffs2_1pass.c +2 -3
@@ -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.
Signature · 1 line
2.43.0
Quoted 27 lines · 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_WIDTHcontrols 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.
Quoted 4 lines
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, [email protected] 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.
Signature · 1 line
Tom
Hi,
please resend this series on the new list:
U-Boot Mailing List <[email protected]>
Thanks!
bye,
Heiko
Quoted 46 lines · 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_WIDTHcontrols 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 sortfs/jffs2/Kconfig | 29 ++++- fs/jffs2/jffs2_1pass.c | 261 +++++++++++++++++++++++++++++++++++++-- fs/jffs2/jffs2_private.h | 30 +++++ 3 files changed, 308 insertions(+), 12 deletions(-)
Signature · 5 lines
Nabla Software Engineering HRB 40522 Augsburg Phone: +49 821 45592596 E-Mail: [email protected] Geschäftsführer : Stefano Babic