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
probability.
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.
