JFFS2 garbage collector blocking for minutes after mount

JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

Hi,

I guess I'll be touching an old subject with this thread:

I have a "small" NAND device (32MByte) with JFFS2 on top used as the 
root-fs on my system. It's been working like a charm - until just now. 
After (over)writing a relative large file (11 megs uncomp. - 
~3-5compr.), the garbage collector (jffs2_gcd_mtd0) uses 8:45 minutes of 
CPU time (~99%) after booting - blocking any write operations.
Ok, I accept that some GC'ing should be performed when going "beyond the 
edge" - but shouldn't this be a one-time process, so the next time I 
boot this is done with?
I see it everytime I reboot - without touching any files on the system...

I use the mtd source from 2005-03-04...

BR,
  Martin Egholm

Re: JFFS2 garbage collector blocking for minutes after mount

[David Woodhouse]

On Wed, 2005-07-20 at 11:03 +0200, Martin Egholm Nielsen wrote:
> I have a "small" NAND device (32MByte) with JFFS2 on top used as the 
> root-fs on my system. It's been working like a charm - until just now. 
> After (over)writing a relative large file (11 megs uncomp. - 
> ~3-5compr.), the garbage collector (jffs2_gcd_mtd0) uses 8:45 minutes of 
> CPU time (~99%) after booting - blocking any write operations.
> Ok, I accept that some GC'ing should be performed when going "beyond the 
> edge" - but shouldn't this be a one-time process, so the next time I 
> boot this is done with?
> I see it everytime I reboot - without touching any files on the system...
> 
> I use the mtd source from 2005-03-04...

The garbage collection thread is also responsible for building up the
node tree for every inode after mounting, so that we know for sure which
nodes are valid and which are obsolete. On NAND flash we can't actually
mark nodes as obsolete.

We've made some significant improvements to that process since March,
especially where inodes with large numbers of nodes are concerned. We
used to sort all the nodes into a linked list before building the tree,
but now we use a tree data structure for that instead -- so it's
O(n log n) instead of O(n²) in the number of nodes.

Artem has patches which should improve it still further -- I'm not sure
if they are committed yet.

-- 
dwmw2

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

>>I have a "small" NAND device (32MByte) with JFFS2 on top used as the 
>>root-fs on my system. It's been working like a charm - until just now. 
>>After (over)writing a relative large file (11 megs uncomp. - 
>>~3-5compr.), the garbage collector (jffs2_gcd_mtd0) uses 8:45 minutes of 
>>CPU time (~99%) after booting - blocking any write operations.
>>Ok, I accept that some GC'ing should be performed when going "beyond the 
>>edge" - but shouldn't this be a one-time process, so the next time I 
>>boot this is done with?
>>I see it everytime I reboot - without touching any files on the system...
>>I use the mtd source from 2005-03-04...

> The garbage collection thread is also responsible for building up the
> node tree for every inode after mounting, so that we know for sure which
> nodes are valid and which are obsolete.
So you think this is what consumes the time?

> On NAND flash we can't actually mark nodes as obsolete.
> We've made some significant improvements to that process since March,
> especially where inodes with large numbers of nodes are concerned. We
> used to sort all the nodes into a linked list before building the tree,
> but now we use a tree data structure for that instead -- so it's
> O(n log n) instead of O(n²) in the number of nodes.

> Artem has patches which should improve it still further -- I'm not sure
> if they are committed yet.
Sounds interesting... Artems states it'll be ready sometimes soon (a 
week or so from now...)

BR,
  Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[David Woodhouse]

On Wed, 2005-07-20 at 16:12 +0200, Martin Egholm Nielsen wrote:
> So you think this is what consumes the time?

Quite feasibly. You spoke of a multi-megabyte file, and the performance
on such files is definitely a lot better than it was. Run it with
profiling and we'll see -- tell us where it's spending all its time, and
we'll see if we can improve that part of the code.

-- 
dwmw2

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

>>So you think this is what consumes the time?
> Quite feasibly. You spoke of a multi-megabyte file, and the performance
> on such files is definitely a lot better than it was. 
I just find it strange that this problem suddenly occur out of 
nowhere... I've been working with these big files many many times before 
this happened.
And I've tried reproducing it on another device by copying, moving, and 
deleting these 11megs of files back and forth... But no matter what I 
do, I get nothing resembling this behaviour...
I guess "fragmentation" has a saying here?!

> Run it with profiling and we'll see -- tell us where it's spending
> all its time, and we'll see if we can improve that part of the code.
I'm not comfortable with profiling the kernel... It could be arranged, 
but I rather see if the a recent CVS snapshot does it for me... ;-)

// Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[David Woodhouse]

On Wed, 2005-07-20 at 16:34 +0200, Martin Egholm Nielsen wrote:
> I'm not comfortable with profiling the kernel... It could be arranged, 
> but I rather see if the a recent CVS snapshot does it for me... ;-)

Profiling isn't hard or intrusive -- all you need to do is boot with
something like 'profile=1' on the kernel command line, then
read /proc/profile after the GC thread has finished doing its thing.

Then the readprofile tool will be able to tell you where the time was
spent.

-- 
dwmw2

Re: JFFS2 garbage collector blocking for minutes after mount

[Stephane Fillod]

On Wed, 2005-07-20 at 16:34 +0200, Martin Egholm Nielsen wrote:
> I'm not comfortable with profiling the kernel... It could be arranged, 
> but I rather see if the a recent CVS snapshot does it for me... 

Profiling the kernel? what about using OProfile?

-- 
Stephane

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

Hi there,

>>I'm not comfortable with profiling the kernel... It could be arranged, 
>>but I rather see if the a recent CVS snapshot does it for me... ;-)

> Profiling isn't hard or intrusive -- all you need to do is boot with
> something like 'profile=1' on the kernel command line, then
> read /proc/profile after the GC thread has finished doing its thing.
> 
> Then the readprofile tool will be able to tell you where the time was
> spent.

First of all, I patched my 2.4.20 kernel with CVS head from today 
(2005-07-22) - it took some time, but it surely seems to work...

That reduced the mount time of my "spoiled" flash from 8m45s 
(jffs2_gcd_mtd0) to some 45seconds! So that was a factor of ~10 in 
speed! That's more or less acceptable... (I really hope my patchin 
didn't spoil some other parts!)

Second, I tried running the profiling - *with* the new kernel/mtd 
source. The time consumers are - sorted by clock ticks:

47695	idled			384,63710
2997	nand_read_buf		62,43750
1122	nand_calculate_ecc	5,84380
677	__delay			33,85000
502	nand_do_read_ecc	0,26370

Right?!

BR,
  Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[David Woodhouse]

On Fri, 2005-07-22 at 16:47 +0200, Martin Egholm Nielsen wrote:
> 47695   idled                   384,63710
> 2997    nand_read_buf           62,43750
> 1122    nand_calculate_ecc      5,84380
> 677     __delay                 33,85000
> 502     nand_do_read_ecc        0,26370

Right, so we're spending most of that time actually reading the flash.
If you just read the entire flash device, how long does that take?
 (time dd if=/dev/mtd0 of=/dev/null) 

Artem's patch will improve things further by building up the fragtree
from newest to oldest node instead of from oldest to newest as we
currently do -- which actually means we don't need to check the CRC on
the oldest nodes before they never get added to the tree; we don't
actually need to read their data payload at all.

In the longer term, Ferenc's summary patch would decrease the amount of
reading from the flash even further. I keep meaning to go through that
in detail and make it mergeable.

-- 
dwmw2

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

>>47695   idled                   384,63710
>>2997    nand_read_buf           62,43750
>>1122    nand_calculate_ecc      5,84380
>>677     __delay                 33,85000
>>502     nand_do_read_ecc        0,26370
> Right, so we're spending most of that time actually reading the flash.
> If you just read the entire flash device, how long does that take?
>  (time dd if=/dev/mtd0 of=/dev/null) 
This takes some 22 secs - so that explains the half of the time (~45s), 
yes... I guess some of the time has to do with the fact that I used the 
NAND for my root fs - unfortunately also when I did the profiling...

> Artem's patch will improve things further by building up the fragtree
> from newest to oldest node instead of from oldest to newest as we
> currently do -- which actually means we don't need to check the CRC on
> the oldest nodes before they never get added to the tree; we don't
> actually need to read their data payload at all.
Looking forward to the patch leaving the preliminary state...

// Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[Artem B. Bityuckiy]

Martin Egholm Nielsen wrote:
> Looking forward to the patch leaving the preliminary state...
> 
Would be nice if you try it before we can commit it...

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

>> Looking forward to the patch leaving the preliminary state...
> Would be nice if you try it before we can commit it...
I will see if I can succesfully patch it in my already patched 
version... :-)

// Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[Ferenc Havasi]

>The garbage collection thread is also responsible for building up the
>node tree for every inode after mounting, so that we know for sure which
>nodes are valid and which are obsolete. On NAND flash we can't actually
>mark nodes as obsolete.
>  
>
Martin, you may should try our Centralizes Summary (CS) patch. It stores
every relevant memory representation at umount time, so at mount (if the
previous unmount was a clean one) you need only to read it without any
scanning and rebuilding.

It is downloadable from our web site
(http://www.inf.u-szeged.hu/jffs2/mount.php). I recommend the variant
which stores reference information on the first erase block.

Bye,
Ferenc

Re: JFFS2 garbage collector blocking for minutes after mount

[Artem B. Bityuckiy]

Ferenc Havasi wrote:
> Martin, you may should try our Centralizes Summary (CS) patch. It stores
> every relevant memory representation at umount time, so at mount (if the
> previous unmount was a clean one) you need only to read it without any
> scanning and rebuilding.
> 
> It is downloadable from our web site
> (http://www.inf.u-szeged.hu/jffs2/mount.php). I recommend the variant
> which stores reference information on the first erase block.
> 
Err, isn't your patch about speeding up scanning, not checking?

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

Ferenc Havasi wrote:
>>The garbage collection thread is also responsible for building up the
>>node tree for every inode after mounting, so that we know for sure which
>>nodes are valid and which are obsolete. On NAND flash we can't actually
>>mark nodes as obsolete.

> Martin, you may should try our Centralizes Summary (CS) patch. It stores
> every relevant memory representation at umount time, so at mount (if the
> previous unmount was a clean one) you need only to read it without any
> scanning and rebuilding.

Unfortunately, I have no (or almost no) clean umount's - the device will 
reboot due to power-failure...

But I'm still considering - just for the clean ones :-)

// Martin

Re: JFFS2 garbage collector blocking for minutes after mount

[Steven Scholz]

Ferenc,

  > Martin, you may should try our Centralizes Summary (CS) patch. It stores
> every relevant memory representation at umount time, so at mount (if the
> previous unmount was a clean one) you need only to read it without any
> scanning and rebuilding.

Does writing "every relevant memory representation" significantly increase 
umount time?

--
Steven

Re: JFFS2 garbage collector blocking for minutes after mount

[Ferenc Havasi]

Artem B. Bityuckiy wrote:

> Ferenc Havasi wrote:
>
>> Martin, you may should try our Centralizes Summary (CS) patch. It stores
>> every relevant memory representation at umount time, so at mount (if the
>> previous unmount was a clean one) you need only to read it without any
>> scanning and rebuilding.
>>
>> It is downloadable from our web site
>> (http://www.inf.u-szeged.hu/jffs2/mount.php). I recommend the variant
>> which stores reference information on the first erase block.
>>
> Err, isn't your patch about speeding up scanning, not checking?
>
Erase Block Summary just speeds up scanning - every other processes work
as before.

Centralizes Summary work very differently. It stores all the relevant
memory representation (inode caches, list, ...) onto flash (so the
obscolated information is also stored) at umount time, so at mount time
it only have to restore no other scanning and building is necessery. It
is some kind of "hibernating".

Ferenc

Re: JFFS2 garbage collector blocking for minutes after mount

[Ferenc Havasi]

Steven Scholz wrote:

> Does writing "every relevant memory representation" significantly
> increase umount time?

It depends on many-many things. Just an example: with a 6M image (where
there is a lot of small file) it costs 75K to write out.

Ferenc

Re: JFFS2 garbage collector blocking for minutes after mount

[Steven Scholz]

Ferenc Havasi wrote:
> Steven Scholz wrote:
> 
> 
>>Does writing "every relevant memory representation" significantly
>>increase umount time?
> 
> 
> It depends on many-many things. Just an example: with a 6M image (where
> there is a lot of small file) it costs 75K to write out.

So erasing and writing 2 64kB sectors on a normal NOR flash. Not much though. 
Compared with several seconds mount time ...

--
Steven

Re: JFFS2 garbage collector blocking for minutes after mount

[Martin Egholm Nielsen]

>>> Looking forward to the patch leaving the preliminary state...
>> Would be nice if you try it before we can commit it...
> I will see if I can succesfully patch it in my already patched 
> version... :-)
I will try this as soon I get a nasty bug fixed - boss' order...

// Matin