[U-Boot-Users] jffs2 fsload - SOLVED.

[U-Boot-Users] jffs2 fsload - SOLVED.

[Dan Merillat]

Booting off jffs2 is now a valid configuration.   The failure was that
for each node, jffs2_1pass.c was doing an insertion sort.   That's an
O(N^2) operation, and that's not
current filecount, that's every filename version that has ever existed
on your flash.

I made a pathological test case on my linux desktop (loop, block2mtd,
jffs2mount)
by running bonnie on it.   I rapidly generated 72000 dentries and
61000 inodes to go through. On a 2.4ghz athlon X2, it took over 13
minutes to load the filesystem with stock jffs2_1pass.c

I changed it from a insertion sort to a list-based mergesort (no extra
heap requirements) and it read the filesystem in 650ms.

Back on the flash chip, ARM with 32meg jffs2 filesystem takes ~15
seconds JUST to read the flash with

while(offset<max) junk=*offset;

Other hits:

the spinner: all those compares added 15 seconds to the boot time.  Removed.

get_node_mem() calls - huge overhead (45 seconds, or roughly 66% of
the total time)

jffs2_scan_empty() - any erased sectors were bog slow, to do the EXACT
same thing the
main loop was doing.  Removed.

Added ignore cases for erase and summary blocks (from another patch)
that gets rid
of those warnings with new kernels.  It still does the right thing, by
checking magic, CRC and length then skipping it.


The main problem is that there's no dcache on ARM, so we pay a massive
penalty for
function calls or even memory->register loads.   Simple addition
became quite expensive, hence changing offset+part->offset into
offset.

This does add the assumption that a partition will be contiguous in
memory.  I'm not sure if that is valid on all platforms, but it is on
every one I'm working on.

The mergesort license seems to be GPL compatable, (no restrictions or
advertising clause).  If it's a problem I can rewrite it myself under
GPL.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: u-boot-1.1.6-jffs2-fsload.patch
Type: application/octet-stream
Size: 0 bytes
Desc: not available
Url : http://lists.denx.de/pipermail/u-boot/attachments/20070112/12ef0e7b/attachment.obj 

[U-Boot-Users] Fwd: jffs2 fsload - SOLVED.

[Dan Merillat]

Ok, let's try this again.

Patch attached, and in-case it gets screwed up again, it's also at
http://mutley.ao.net/~harik/u-boot-1.1.6-jffs2-fsload.patch

I've found one additional problem: RAM issues.  My board is configured
with a 128k malloc arena for u-boot, and we trivially run out of that
(less then 16384 total nodes, minus whatever else has used malloc on
boot)   A lightly-used FS image right now has
10,000 nodes, so it will soon hit that limit and fail to boot.    For
me, I'm just going to
allocate the array in some random RAM area, but that's a pretty awful
non-solution.   Once I have more free time I'll convert fsload to the
jffs2read source.


---------- Forwarded message ----------
From: Dan Merillat <harik.attar@gmail.com>
Date: Jan 12, 2007 2:14 AM
Subject: jffs2 fsload - SOLVED.
To: u-boot-users at lists.sourceforge.net


Booting off jffs2 is now a valid configuration.   The failure was that
for each node, jffs2_1pass.c was doing an insertion sort.   That's an
O(N^2) operation, and that's not
current filecount, that's every filename version that has ever existed
on your flash.

I made a pathological test case on my linux desktop (loop, block2mtd,
jffs2mount)
by running bonnie on it.   I rapidly generated 72000 dentries and
61000 inodes to go through. On a 2.4ghz athlon X2, it took over 13
minutes to load the filesystem with stock jffs2_1pass.c

I changed it from a insertion sort to a list-based mergesort (no extra
heap requirements) and it read the filesystem in 650ms.

Back on the flash chip, ARM with 32meg jffs2 filesystem takes ~15
seconds JUST to read the flash with

while(offset<max) junk=*offset;

Other hits:

the spinner: all those compares added 15 seconds to the boot time.  Removed.

get_node_mem() calls - huge overhead (45 seconds, or roughly 66% of
the total time)

jffs2_scan_empty() - any erased sectors were bog slow, to do the EXACT
same thing the
main loop was doing.  Removed.

Added ignore cases for erase and summary blocks (from another patch)
that gets rid
of those warnings with new kernels.  It still does the right thing, by
checking magic, CRC and length then skipping it.


The main problem is that there's no dcache on ARM, so we pay a massive
penalty for
function calls or even memory->register loads.   Simple addition
became quite expensive, hence changing offset+part->offset into
offset.

This does add the assumption that a partition will be contiguous in
memory.  I'm not sure if that is valid on all platforms, but it is on
every one I'm working on.

The mergesort license seems to be GPL compatable, (no restrictions or
advertising clause).  If it's a problem I can rewrite it myself under
GPL.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: u-boot-1.1.6-jffs2-fsload.patch
Type: application/octet-stream
Size: 6981 bytes
Desc: not available
Url : http://lists.denx.de/pipermail/u-boot/attachments/20070116/e0b228a8/attachment.obj 

[U-Boot-Users] jffs2 fsload - SOLVED.

[Dan Merillat]

On 1/16/07, Dan Merillat <harik.attar@gmail.com> wrote:
> Ok, let's try this again.
>
> Patch attached, and in-case it gets screwed up again, it's also at
> http://mutley.ao.net/~harik/u-boot-1.1.6-jffs2-fsload.patch

Any feedback on this?

[U-Boot-Users] jffs2 fsload - SOLVED.

[Ronny Nilsson]

> ---------- Forwarded message ----------
> From: Dan Merillat <harik.attar@gmail.com>
> Date: Jan 12, 2007 2:14 AM
> Subject: jffs2 fsload - SOLVED.
> To: u-boot-users at lists.sourceforge.net
>
>
> Booting off jffs2 is now a valid configuration.   The failure was
> that for each node, jffs2_1pass.c was doing an insertion sort.  
> That's an O(N^2) operation, and that's not
> current filecount, that's every filename version that has ever
> existed on your flash.

Hi
I'm very interested in your patch because my system is also suffering 
from extreme slow boot. However, currently I haven't the time to try 
your patch out (hopefully later though). Made a quick view of it though 
and it looks promising. Beyond you patch I too have identified some 
hotspots in the JFFS2 driver and is working on a patch myself which I 
think will complement yours.


> I changed it from a insertion sort to a list-based mergesort (no
> extra heap requirements) and it read the filesystem in 650ms.

Very nice.


> the spinner: all those compares added 15 seconds to the boot time. 
> Removed.

Realy? That much?


> The main problem is that there's no dcache on ARM, so we pay a
> massive penalty for
> function calls or even memory->register loads.   Simple addition
> became quite expensive, hence changing offset+part->offset into
> offset.

This is not true. It depends on the ARM HW implementation if there is a 
dcache or not. Some has (like mine) and some don't.


Regards
/Ronny