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

[Mark Tomlinson]

In reply to comments from Wolfgang Denk and Heiko Schocher:

My aim was to optimize U-Boot's loading of a JFFS2 file, since we needed to
boot much more quickly on one of our devices than we currently were. We had
discussed the possibility of abandoning JFFS2 entirely, but chose to see
how quickly JFFS2 could be made to work. We also knew that Linux would
mount this file system much quicker than u-boot did, so knew that at least
some speed improvement was possible.

The improvments was from three sources: (1) searching U-Boot mailing list
archives, (2) looking at the linux kernel, and (3) our own measurements and
improvements. For example, the merge sort (before my modifications) can be
found here: http://lists.denx.de/pipermail/u-boot/2007-January/018777.html

Two of the patches were inspired from the Linux kernel: Changing scansize,
and recognising the CLEANMARKER. While trying to synchronize U-Boot code
with Linux sounds like a good idea, I think this wouldn't be the right way
to go, since Linux needs to also build lists of blocks which are empty, and
a list of blocks that still need to be erased. Stripping this out is more
work than just enhancing what U-Boot currently has.

=== Original cover message follows ===

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.

Changes in v2:
- Fix comment style
- Remove extra {} pair.
- Changed comment style.
- Fixed some missing calls to put_fl_mem().
- Change comment style
- Change comment style
- Changed comment style
- Changed copyright notice to use SPDX-Licence-Identifier.
- Added URL to original mergesort code.
- Removed #ifdef, using Makefile change instead.

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   | 257 ++++++++++++++++++++++++++++++-----------------
 fs/jffs2/jffs2_private.h |   4 +
 fs/jffs2/mergesort.c     |  52 ++++++++++
 4 files changed, 223 insertions(+), 91 deletions(-)
 create mode 100644 fs/jffs2/mergesort.c

-- 
1.9.1