[U-Boot-Users] jffs2 fsload - SOLVED.
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.
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@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.
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?
---------- Forwarded message ---------- From: Dan Merillat harik.attar@gmail.com Date: Jan 12, 2007 2:14 AM Subject: jffs2 fsload - SOLVED. To: u-boot-users@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
participants (2)
-
Dan Merillat -
Ronny Nilsson