Wear Leveling in JFFS2 NOT working!(?)

Wear Leveling in JFFS2 NOT working!(?)

[Vipin Malik]

I setup a simple test to measure the wear leveling. During my power down
tests (which are at 10,090 cycles!) I print to the console which sector
is being erased.

Then using a simple program, I went through the console log and got the
following result: (Note! This data is only from 3615 of the total 10,090
pwr cycles).

Sector Address:0x780000 Number Of Erases:2050
Sector Address:0x640000 Number Of Erases:1573
Sector Address:0x600000 Number Of Erases:1503
Sector Address:0x5c0000 Number Of Erases:1406
Sector Address:0x580000 Number Of Erases:1297
Sector Address:0x500000 Number Of Erases:1045
Sector Address:0x4c0000 Number Of Erases:824
Sector Address:0x7c0000 Number Of Erases:2283
Sector Address:0x740000 Number Of Erases:1906
Sector Address:0x700000 Number Of Erases:1817
Sector Address:0x6c0000 Number Of Erases:1753
Sector Address:0x680000 Number Of Erases:1654
Sector Address:0x540000 Number Of Erases:1190
Sector Address:0x480000 Number Of Erases:514
Sector Address:0x440000 Number Of Erases:216
Sector Address:0x400000 Number Of Erases:60
Sector Address:0x3c0000 Number Of Erases:13
Sector Address:0x380000 Number Of Erases:1

Total Unique Sectors Found= 20, total sum of all erases=21105

Obviously, not all sectors are being "cycled" evenly. As a matter of
fact, none of the sectors below 0x380000 are being cycled at all.

I am using 4x wide 8bit memory for a total of 8MBytes (for a total of 32
sectors). 12 sectors haven't even been touched.

The fs is a "root" fs, with about 4-5Megs of the 8MB with static OS data
and the rest being used to write out 100 binary files (about 100-400KB
total).

Now, one thing that may be tripping up the wear leveling algorithm is
the fact that the system is being cycled every 2-3 minutes.


David? What does the algorithm to "pickup" a new "less cycled" sector
and give a over-used sector a rest depend on?

Thanks

Vipin

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

On Mon, 30 Apr 2001, Vipin Malik wrote:

> Obviously, not all sectors are being "cycled" evenly. As a matter of
> fact, none of the sectors below 0x380000 are being cycled at all.
>
> Now, one thing that may be tripping up the wear leveling algorithm is
> the fact that the system is being cycled every 2-3 minutes.

That's almost certainly the reason. My testing on prolonged stress tests
showed a fairly even wear levelling.

> David? What does the algorithm to "pickup" a new "less cycled" sector
> and give a over-used sector a rest depend on?

Most of the time we pick the block off the end of the dirty_list. With a
1/100 probability, we pick a block off the clean_list instead.
Freshly-dirtied blocks get put on the back of the dirty_list. Likewise,
freshly-filled blocks get put on back of the clean_list. So it tends to
use them fairly evenly.

However, when we remount the filesystem, we lose that ordering. The blocks
get put on the lists in order, and we pick the block nearest the end of
the medium.

Suggested fix: introduce some randomness to the initial list after
mounting.

Either:
	1. After scan, move the first <n> blocks in the list to the end
		of the list, where 1 < n < sizeof(list).
	2. When adding entries to the lists during scan, do something
		like: if (jiffies % 1) list_add_tail() else list_add().

-- 
dwmw2

Re: Wear Leveling in JFFS2 NOT working!(?)

[Tim Riker]

David Woodhouse wrote:
> Either:
>         1. After scan, move the first <n> blocks in the list to the end
>                 of the list, where 1 < n < sizeof(list).

Providing n is random, this is a good solution. Can the list be hacked
to change the top/bottom without actually walking through n blocks and
moving them? I have not looked at the source, but for a linked list you
could join top and bottom entries and then break n and n-1 nodes and
start becomes n, end becomes n-1, etc.

>         2. When adding entries to the lists during scan, do something
>                 like: if (jiffies % 1) list_add_tail() else list_add().

This will still be somewhat pattern oriented. last blocks scanned will
be either at front or back so I suspect wear numbers will increase
towards the end of scanned blocks. ie: first scanned blocks would never
be on the end of the dirty list.
-- 
Tim Riker - http://rikers.org/ - short SIGs! <g>
All I need to know I could have learned in Kindergarten
... if I'd just been paying attention.

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

Tim@Rikers.org said:
> Providing n is random, this is a good solution. Can the list be hacked
> to change the top/bottom without actually walking through n blocks and
> moving them? I have not looked at the source, but for a linked list
> you could join top and bottom entries and then break n and n-1 nodes
> and start becomes n, end becomes n-1, etc.

Yep, hacking the list is fairly easy. Coming up with a pseudo-random number 
of reasonable quality at boot time when the entropy pool is empty is the 
more interesting bit. The 'jiffies mod' trick would give repeatable
results.

Just to restate the obvious - it doesn't have to be _random_, just evenly 
distributed.

> This will still be somewhat pattern oriented. last blocks scanned will
> be either at front or back so I suspect wear numbers will increase
> towards the end of scanned blocks. ie: first scanned blocks would never
> be on the end of the dirty list.

Agreed.

--
dwmw2

Re: Wear Leveling in JFFS2 NOT working!(?)

[Tim Riker]

David Woodhouse wrote:
> 
> Tim@Rikers.org said:
> > Providing n is random, this is a good solution. Can the list be hacked
> > to change the top/bottom without actually walking through n blocks and
> > moving them? I have not looked at the source, but for a linked list
> > you could join top and bottom entries and then break n and n-1 nodes
> > and start becomes n, end becomes n-1, etc.
> 
> Yep, hacking the list is fairly easy. Coming up with a pseudo-random number
> of reasonable quality at boot time when the entropy pool is empty is the
> more interesting bit. The 'jiffies mod' trick would give repeatable
> results.

RTC should not be relied on as some hardware has this broken (iPAQ at
present ;-) What about totaling the checksums for each block as we scan
them at mount time and then mod that by numblocks? This would also be
repeatable given the same original filesystem. Every filesystem write
changes it. Reads do not, but then they don't need wear leveling do
they? ;-)

> Just to restate the obvious - it doesn't have to be _random_, just evenly
> distributed.

agreed

-- 
Tim Riker - http://rikers.org/ - short SIGs! <g>
All I need to know I could have learned in Kindergarten
... if I'd just been paying attention.

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

Tim@Rikers.org said:
> > The 'jiffies mod' trick would give repeatable results.

> RTC should not be relied on as some hardware has this broken (iPAQ at
> present ;-) What about totaling the checksums for each block as we
> scan them at mount time and then mod that by numblocks? This would
> also be repeatable given the same original filesystem.

By 'repeatable' I meant it would give a badly-distributed pattern, which is
a bad thing. It's not at all necessary that it's predictable given the 
filesystem state before mount.

Totalling the checksums as you suggest would work, but I'm a little 
reluctant to do that because of the layering implications. It would be 
nicer if we could use information which is already available to the code at 
that point. How about just rotating the lists by (highest_inode + 
highest_version_in_it) ?

Over the lifetime of the filesystem, the range of 
	(highest_inode + highest_ver) % nr_blocks
is going to be fairly evenly distributed, isn't it?

--
dwmw2

Re: Wear Leveling in JFFS2 NOT working!(?)

[Jim Gettys]

If you have some way to remember how far you got the last time,
(approximately), then you could restart at the same place, rather
than at the beginning.

This has the same desired effect as starting randomly....

Of course, this may be just reducing the problem to the previously
unsolved problem, potentially...
                      - Jim
--
Jim Gettys
Technology and Corporate Development
Compaq Computer Corporation
jg@pa.dec.com

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

jg@pa.dec.com said:
> If you have some way to remember how far you got the last time,
> (approximately), then you could restart at the same place, rather than
> at the beginning.

> This has the same desired effect as starting randomly....

> Of course, this may be just reducing the problem to the previously
> unsolved problem, potentially...

It is, but the previously unsolved problem in question is one which we
_might_ need to solve anyway for checkpointing - if we decide that mounts
are slow enough that we actually need checkpointing, that is. 

If that's the case, I suppose we just have a block counter which we stick 
in the erase marker at the beginning of each block, and on scan we order 
the blocks such that the oldest blocks are recycled first. We need 
something like that for checking that blocks still contain the same data as 
the checkpoint tells us, anyway.

But I'm hoping to avoid having to implement checkpointing. We don't have to 
use the blocks strictly in order - just try to make sure we start in a 
different place each time.

--
dwmw2

Re: Wear Leveling in JFFS2 NOT working!(?)

[Vipin Malik]

David Woodhouse wrote:

> On Mon, 30 Apr 2001, Vipin Malik wrote:
>
> > Obviously, not all sectors are being "cycled" evenly. As a matter of
> > fact, none of the sectors below 0x380000 are being cycled at all.
> >
> > Now, one thing that may be tripping up the wear leveling algorithm is
> > the fact that the system is being cycled every 2-3 minutes.
>
> That's almost certainly the reason. My testing on prolonged stress tests
> showed a fairly even wear levelling.

Ok, I logged the current state of the num of sectors erased, stopped cycling
power
(but let the infinite write to JFFS2 continue). After 3 days I took another
snapshot
of the num erase sectors:

(The results are posted below if anyone is interested)
As hypothesized, the every few minutes cycling was what was screwing up the
wear leveling algorithm. After the cycling stopped, all sectors showed up in
the log
and additionally each was cycled the same number of times!

In my opinion, there should be no need to fix the algorithm to accommodate
the
frequent cycling. Power going down every few minutes is (usually) NOT a
normal
mode of operation of an embedded system.

At least I'm happy with it the way it currently is.

Vipin

************ Data follows *********************************************
***Snap shot1 (when power was being cycled, you can see the uneven wear
leveling of the sectors.
Additionally only 20 sectors have ever been erased in >3000 cycles) ****

Sector Address:0x780000 Number Of Erases:2823
Sector Address:0x640000 Number Of Erases:2162
Sector Address:0x600000 Number Of Erases:2077
Sector Address:0x5c0000 Number Of Erases:1939
Sector Address:0x580000 Number Of Erases:1795
Sector Address:0x500000 Number Of Erases:1454
Sector Address:0x4c0000 Number Of Erases:1146
Sector Address:0x7c0000 Number Of Erases:3143
Sector Address:0x740000 Number Of Erases:2627
Sector Address:0x700000 Number Of Erases:2499
Sector Address:0x6c0000 Number Of Erases:2410
Sector Address:0x680000 Number Of Erases:2280
Sector Address:0x540000 Number Of Erases:1644
Sector Address:0x480000 Number Of Erases:727
Sector Address:0x440000 Number Of Erases:301
Sector Address:0x400000 Number Of Erases:90
Sector Address:0x3c0000 Number Of Erases:17
Sector Address:0x380000 Number Of Erases:3
Total Unique Sectors Found= 20, total sum of all erases=29137

*** Power cycling was now stopped . Snapshot data follows (from after 1 days
worth of writes to JFFS2) *********

Sector Address:0x780000 Number Of Erases:3214
Sector Address:0x640000 Number Of Erases:2552
Sector Address:0x600000 Number Of Erases:2467
Sector Address:0x5c0000 Number Of Erases:2330
Sector Address:0x580000 Number Of Erases:2185
Sector Address:0x500000 Number Of Erases:1844
Sector Address:0x4c0000 Number Of Erases:1537
Sector Address:0x7c0000 Number Of Erases:3534
Sector Address:0x740000 Number Of Erases:3018
Sector Address:0x700000 Number Of Erases:2889
Sector Address:0x6c0000 Number Of Erases:2800
Sector Address:0x680000 Number Of Erases:2670
Sector Address:0x540000 Number Of Erases:2035
Sector Address:0x480000 Number Of Erases:1118
Sector Address:0x440000 Number Of Erases:691
Sector Address:0x400000 Number Of Erases:480
Sector Address:0x3c0000 Number Of Erases:407
Sector Address:0x380000 Number Of Erases:393
Sector Address:0x340000 Number Of Erases:390
Sector Address:0x300000 Number Of Erases:390
Sector Address:0x2c0000 Number Of Erases:390
Sector Address:0x280000 Number Of Erases:390
Sector Address:0x240000 Number Of Erases:390
Sector Address:0x200000 Number Of Erases:390
Sector Address:0x1c0000 Number Of Erases:390
Sector Address:0x180000 Number Of Erases:390
Sector Address:0x140000 Number Of Erases:389
Sector Address:0x100000 Number Of Erases:389
Sector Address:0xc0000  Number Of Erases:389
Sector Address:0x80000  Number Of Erases:389
Sector Address:0x40000  Number Of Erases:389
Sector Address:0x0      Number Of Erases:389
Total Unique Sectors Found= 34, total sum of all erases=41618

...and viola all sectors show up on the list and each has been erased *an
additional* 389-390 times from the last snapshot when power cycling was still
going on.

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

vipin.malik@daniel.com said:
> As hypothesized, the every few minutes cycling was what was screwing up
> the wear leveling algorithm. After the cycling stopped, all sectors
> showed up in the log and additionally each was cycled the same number
> of times!

Good :)

> In my opinion, there should be no need to fix the algorithm to
> accommodate the frequent cycling. Power going down every few minutes
> is (usually) NOT a normal mode of operation of an embedded system.

It's not normal, but given that it's quite easy for us to deal with it by
attempting to start in a different place each time, we might as well do so.

If it were more difficult, I'd be inclined to agree with you that it's not 
worth the effort.

--
dwmw2

RE: Wear Leveling in JFFS2 NOT working!(?)

[Chris Read]

There are applications where a deeply embedded system may get power cycled 
frequently; thus I would advocate that wear levelling should work correctly 
in this case.

Chris Read

On 03 May 2001 16:30, David Woodhouse [SMTP:dwmw2@infradead.org] wrote:
>
> vipin.malik@daniel.com said:
> > As hypothesized, the every few minutes cycling was what was screwing up
> > the wear leveling algorithm. After the cycling stopped, all sectors
> > showed up in the log and additionally each was cycled the same number
> > of times!
>
> Good :)
>
> > In my opinion, there should be no need to fix the algorithm to
> > accommodate the frequent cycling. Power going down every few minutes
> > is (usually) NOT a normal mode of operation of an embedded system.
>
> It's not normal, but given that it's quite easy for us to deal with it by
> attempting to start in a different place each time, we might as well do 
so.
>
> If it were more difficult, I'd be inclined to agree with you that it's 
not
> worth the effort.
>
> --
> dwmw2
>
>
>
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/

Re: Wear Leveling in JFFS2 NOT working!(?)

[David Woodhouse]

chris.read@activesilicon.co.uk said:
> There are applications where a deeply embedded system may get power
> cycled  frequently; thus I would advocate that wear levelling should
> work correctly  in this case.

We know how. Just that nobody's provided me with a patch or sufficient 
motivation to do it myself yet :)

--
dwmw2