NAND Translation Layer

Owned by Former user (Deleted)
Last updated: Feb 04, 2014 by Former user (Deleted)
4 min read

The NAND translation layer is the main layer of the driver, implemented by the files fs_dev_nand.c and fs_dev_nand.h. This layer contains most of the algorithms necessary to overcome the following limitations of NAND flash technology:

  • Write operations can only change a bit state from ‘1’ to ‘0’. Only erase operations can revert the bit state, from ‘0’ to ‘1’.
  • Erase operations are only performed on large sections of the memory called blocks (typically between 16 kB and 512 kB).
  • Write operations are performed on a sub-section of a block, called a page (typically between 512 and 8192 octets).
  • Some devices support partial page programming (splitting the operation to write a full page into multiple operations that each write a sub-section of the page). Other devices can only have their pages written in a single operation before they are erased.
  • Some devices must write the pages of a block in a sequential manner (page 0, page 1, page 2, etc.).
  • Blocks can only be erased a limited number of times (typically 10k to 100k) before the integrity of the memory is compromised.
  • Some device blocks can’t be used reliably and are considered bad blocks. These blocks are either marked at the factory or become bad during the device’s life.
  • Electric disturbance can cause read errors. An error correction mechanism must be used to decrease the bit error rate.

The role of the translation layer is to translate those NAND flash specific requirements into a disk interface, based on sector access. This disk interface allows the NAND driver to be used with traditional sector-based file systems like FAT, which is used by µC/FS.

The translation layer implementation provided with the NAND driver is inspired by the KAST (K-Associative Sector Translation) as proposed by Cho (see Bibliography).

In the provided implementation, three types of blocks are present on the device. The data blocks typically occupy the major portion of the storage space. Data blocks are used to contain the data written to the device by the application or file system. A mapping between the logical addresses of the blocks and their physical locations is used to enable wear-leveling.

This mapping, as well as other metadata, is contained in metadata blocks. Typically, only one block is used to store metadata. This block is also moved around for wear-leveling reasons.

The third type of blocks are update blocks. All data written on the device must first be written through update blocks. Under specific circumstances (including an update block becoming full), the contents of an update block are folded onto data blocks. The folding operation roughly consists of three steps. The first step is to find an unused block and erase it. Secondly, the contents of the corresponding data block must be merged with the more recent, but incomplete data contained in the update block. This merged data is written in the recently-erased block. Once this operation is complete, metadata must be updated: the old data block and the update block are marked as free to erase and use, and the block mapping must be updated to point to the new data block.

In this implementation, it is possible to specify how many different data blocks pointed to by a single update block. This specification is called maximum associativity (see the configuration field .RUB_MaxAssoc in Translation Layer Configuration). If this value is greater than one, the merge operation must be performed for each data block associated with the update block being folded.

Each update block can be of one of the two sub-types: random update blocks (RUBs) and sequential update blocks (SUBs). Sequential update blocks can only refer to a single data block (associativity is always 1). Also, they must use the same exact layout as a data block (i.e. logical sector 0 written at physical sector 0, logical sector 1 written at physical sector 1, etc.). The advantage of SUBs is that they have a much lower merge cost. They can be converted into data blocks in-place by copying missing sectors from the associated data block and updating some metadata. Random update blocks, on the other hand, can contain sectors from multiple data blocks. Those sectors can be written at any location in the RUB since it contains additional metadata to map each sector to an appropriate location in a data block, resulting in an increased merge cost but allowing for better wear-leveling since it leads to better block usage in the case of random writes.

Another important functionality of the translation layer is to keep track of the number of erase operations performed on each block. The erase count is critical for two reasons. First, the erase count can be used to efficiently drive the wear-leveling algorithm, allowing seldom erased blocks to be preferred over frequently erased blocks, when a new block is required. Secondly, the erase count allows the translation layer to detect the blocks that have reached their erase limit.

Since the erase count information is stored in each block, each erase count must be backed-up somewhere else in the device prior to erasing a block. Blocks that have their erase count backed-up are called available blocks. When the translation layer needs a new block, it will always be taken from the available blocks table to make sure its erase count is not lost in the case of an unexpected power-down.

All this functionality is embedded within the translation layer. Using the software itself does not require a deep understanding of the mechanisms as they are all abstracted into a simpler, easier to understand disk interface. However, understanding the internals can be useful to efficiently configure the translation layer.