Flash memory is not an infinitely reusable storage medium. The number of erase cycles per erase unit of flash memory is large but limited. Thus, with use, flash eventually degrades to a read-only state. As failure modes go, this one is uncommonly kind to data. Still, even if this failure mode is not catastrophic, it is best to delay it for as long as possible.

To maximize the lifetime of flash, it is necessary to balance usage over the entire medium so that no one part of flash is over-used and driven prematurely into a read-only state. This technique is known as wear leveling. The technique of wear leveling also helps avoid over-programming. To implement wear leveling, TrueFFS uses a block-to-flash translation system that is based on a dynamically maintained map. This map is adjusted as blocks are modified, moved, or garbage collected.

As is required of a block device driver, TrueFFS maps flash memory into an apparently contiguous array of storage blocks to which a file system can read and write data. These blocks are numbered from zero to one less than the total number of blocks.

Reading the data from a block is straight forward. The file system requests the contents of a particular block. In response, TrueFFS translates the block number into flash memory coordinates, retrieves the data at those coordinates, and returns the data to the file system. Writing data to a block can be just as straightforward if the target block is as yet unwritten. All TrueFFS needs to do is translate the block number into flash memory coordinates and write to the location.¹

However, if the write request seeks to modify the contents of a previously written block, the situation is more complex. Flash memory requires an erase cycle before it can be overwritten, and the erase cycle applies on a scale much larger than a single block. Thus, to simulate overwriting a particular block, TrueFFS first finds a writable area of flash (one that is already erased and ready to receive data). TrueFFS then writes the modified block data to that free area. After the data is safely written, TrueFFS updates its block-to-flash mapping structures so that the block now maps to the area of flash that contains the modified data.

The remapping of modified blocks to new flash memory coordinates does guarantee a certain degree of wear leveling. However, if some of the data stored in flash is essentially static, wear leveling only at modification time gives rise to a problem known as static file locking.

The areas of flash that store static data would not be cycled at all, at the expense of the remaining areas. This would lower the medium's life-expectancy significantly. TrueFFS overcomes static file locking by forcing transfers of static areas. Because the block-to-flash map is dynamic, TrueFFS is able to manage these wear-leveling transfers in a way that is invisible to the file system.

However, implementing absolute wear-leveling can have a negative impact on performance because of all the required data moves. To avoid this performance hit, TrueFFS implements a wear-leveling algorithm that is not quite absolute. The result is that all erase zones are used approximately equally. In the long run, you can expect the same number of erase cycles per erase unit without a degradation of performance. Given the large number of allowed erase cycles, this less than absolute approach to wear-leveling is good enough.

Finally, the TrueFFS wear leveling algorithm is further enhanced to break a failure mode known as dead locks. Some simple wear-leveling algorithms have been shown to "flip-flop" transfers between only two or more units for very long periods, neglecting all other units. The wear-leveling mechanism used by TrueFFS makes sure that such loops are curbed.²

Modifying blocks leaves behind block-sized regions of flash memory that no longer contain valid data. These regions of flash memory are also unwritable until erased. If there were no mechanism to reclaim these blocks, the flash medium would quickly revert to a read-only state. Unfortunately, reclaiming these blocks is complicated by the fact that blocks are not individually erasable. Erasure is limited to much larger regions (for example, 64 kilobytes for Intel Flash File devices) known as erase units.

To reclaim (erase) blocks that no longer contain valid data, TrueFFS uses a mechanism called garbage collection. This mechanism copies all the valid data blocks from a source erase unit into another erase unit known as a transfer unit. TrueFFS then updates the block-to-flash map and then erases the old erase unit. The virtual block presented to the outside world still appears to contain the same data even though that data now resides in a different part of flash.

If garbage collection is done too frequently, it defeats the wear-leveling algorithm and degrades the overall performance of the flash disk. Thus, within TrueFFS, garbage collection is triggered only as needed by the block allocation algorithm, which tries to keep available a pool of free consecutive blocks resident in the same erase unit. If the pool gets too small, the block allocation algorithm launches the garbage collection algorithm. The garbage collection algorithm then finds and reclaims an erase unit that best matches the following criteria:

• the largest number of garbage blocks

• the least number of erase cycles

• the most static areas

In addition to these measurable criteria, the garbage collection algorithm also factors in a random selection process. This helps guarantee that the reclamation process covers the entire medium evenly and is not biased due to the way applications use data.

To promote more efficient data retrieval, TrueFFS uses an allocation strategy that clusters related data (such as the blocks that comprise the sectors of a file) into a contiguous area in a single erase unit. To prepare for the clustering of related data, TrueFFS tries to maintain a pool of physically consecutive free blocks that are resident in the same erase unit. If a pool of physically consecutive blocks is impossible, TrueFFS tries to assure that all the blocks in the pool reside in the same erase unit. If that too is impossible, TrueFFS tries to allocate a pool of blocks in the erase unit that has the most space available.

This approach of clustering related data has several benefits. If TrueFFS must access flash through a small memory window, the clustered related data cuts down on the number of calls required to map physical blocks into the window. This allows faster retrieval times for files accessed sequentially (the usual case).

Clustering related data also cuts down on fragmentation. This is because deleting a file tends to free up complete blocks that can be easily reclaimed. This means that garbage collection is faster. Clustering related data also has the effect of localizing blocks that belong to static files. This makes it much easier to transfer these blocks when the wear-leveling algorithm decides to move static areas.

1:  Writing data to flash does require the mediation of a software module called an MTD, but that detail is not immediately relevant.

2:  For optimal wear-leveling performance, TrueFFS requires at least 12 erase units.