Solution for wear-leveling

Flash is a type of electrically-erasable

programmable read-only memory (EEPROM) which is

non-volatile. There are three operations on it: read,

write and erase. Flash chips are divided into erase

units, sometimes called erase blocks. During a write

operation, a bit can be changed from logical one to

logical zero. To change a bit from zero to one, the

whole erase unit has to be erased. The lifetime of an

erase unit depends on the number of erase cycles.

Manufacturers guarantee the number of cycles range

from 10,000 to 1,000,000 per erase unit, after which an

erase unit could wear out and becomes unreliable. To

avoid this, a flash file system has to distribute the erase

cycles around the medium, so-called wear-leveling.

YAFFS2 does not implement any wear-leveling.

For most part, the designer thinks it’s not a problem for

a log-structured file system like YAFFS2 because

usage cycles tend to clear out and reuse areas. But for

small-sized NAND device, it’s still necessary to avoid

heavily uneven using of the blocks. The below is the

algorithm for wear-leveling designed for YAFFS2.

Before garbage collection, we iterate the whole

device to get the dirtiest N blocks.

dirtiest_blocks[i (1<= i <= N)] = { block id };

The smaller the variable i is, the more invalid pages

the block will have, or the dirter. For example,

dirtiest_blocks[1] should be the block which has the

maximum invalid pages. The block that we will select

as garbage collection is:

N - [logM(rand_based_on_current_time%MN)]

The probability of i is:

P(i) = (M(N-i+1)-M(N-i))/MN = (M-1)/Mi

It can guarantee that the probability of each block

selected will depend on “the degree of dirtiness” or the

number of invalid pages. It’s not liner relationship. The

dirter is, the far higher the probability of this block will

be. Even the block N in the array dirtiest_blocks still

has the chance to be selected with the very low


M and N can be customized by the size of the

NAND device and the limited number of erase cycles.

Suppose M = 1 on the 64M NAND device with

512-byte pages, there are total 32 pages in one block,

so the dirtiest may have 31 invalid pages. If all of them

are invalid pages, it absolutely will be the target as

garbage collection firstly. It is assumed that a NAND

has all the blocks whose invalid pages range from 31 to

1, the probability for each block as the next garbage

collection are:

P[block with 31 invalid pages] = 1/2

P[block with 30 invalid pages] = 1/4

P[block with n invalid pages] = 1/2(32-n)

where P means probability. Any block with invalid

pages may be selected as garbage collection but its

chance depends on how many invalid pages are.

原文发布于微信公众号 - 瓜大三哥(xiguazai_tortoise)





0 条评论
登录 后参与评论