Skip to contentSkip to conversation

Wear Leveling in JFFS2 NOT working!(?)

DISCUSSION Vipin Malik 4 participants 10 messages Apr 30, 2001 – May 3, 2001 Memory technology devices (MTD)

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 5 lines · Vipin Malik

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.

Quoted 2 lines

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().

Signature · 1 line
dwmw2
#2 lore raw
Quoted 3 lines · David Woodhouse

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.

Quoted 2 lines

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.

Signature · 3 lines
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.
#3 lore raw
Quoted 5 lines · [email protected] 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.

Quoted 4 lines

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

#4 lore raw
Quoted 8 lines · David Woodhouse
Quoted 5 lines · [email protected] 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.

Quoted 4 lines

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? ;-)

Quoted 2 lines

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

agreed

Signature · 3 lines
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.
#5 lore raw
Quoted 6 lines · [email protected] said:
Quoted 1 line

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

#6 lore raw
In reply to David Woodhouse

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
[email protected]

#7 lore raw
Quoted 8 lines · [email protected] 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

#8 lore raw
In reply to David Woodhouse
Quoted 10 lines · David Woodhouse
Quoted 5 lines · Vipin Malik

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.

#9 lore raw
Quoted 4 lines · [email protected] 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 :)

Quoted 3 lines

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