Embedded Linux News

The flash storage volume manager UBI and its corresponding file system UBIFS made their way into the Linux kernel in release 2.6.27, quite a few years ago. At the time, there were only two practically usable read/write filesystems for flash devices in Linux: JFFS2 and YAFFS2. JFFS2 was designed for relatively small flashes (in the order of 4 to 64 MB) and had memory consumption and performance issues with bigger flashes, while YAFFS2 was never merged into the mainline, due to a disinterest from the developers to see it merged mainline. UBIFS was therefore the new generation filesystem for flash devices in Linux, which many new embedded Linux products now use in production.

Put it simply, UBI is a volume manager: it maps virtual blocks to physical blocks of flashes, which allows to create, remove and resize logical volumes easily. It takes care of spreading the erase/write load of those blocks in order to ensure the longest lifetime for the flash, and it also takes care of replacing physical blocks that have become unusable by fresh physical blocks. On top of this, UBIFS provide a read/write filesystem, that is exposed to userspace as a regular Linux filesystem. This separation between UBI and UBIFS allows for a cleaner design, by separating the multiple issues that a flash filesystem must handle into two separate layers. But it also allows to have several filesystems into several volumes while preserving a global wear-leveling strategy (so that even if some volumes are mostly read-only and some other volumes have a more write-intensive workload, UBI will do the wear-leveling globally on all physical blocks).

However, one important problem that appeared quite soon is that UBI, at boot time, required a time linear with the flash size to reconstruct its mapping of virtual blocks to physical blocks. This made UBI not fully satisfying on large flashes.

Every year, the CE Linux Forum opens up proposals for various projects helpful to improve the state of Linux in embedded systems, and a project to solve this particular problem was proposed. The CE Linux Forum decided to sponsor it, and Richard Weinberger, who works for Linutronix was in charge of doing this work.

He posted the first RFC version of what was called at the time UBI checkpointing support in February this year, and month after month, he posted nineteen revisions of this patch set, taking into account comments from reviewers, especially from Artem Bityutskiy, the UBI maintainer.

And finally, on September 26th, Richard posted the 19th version of his patch set, with a request for inclusion, and it seems like it will actually be merged in 3.7-rc1, so it should appear in the next stable version of the Linux kernel.

Richard also posted an updated to the documentation of UBI, which details how fastmap works:

Fastmap

Fastmap is an experimental and optional UBI feature, which can be enabled by setting CONFIG_MTD_UBI_FASTMAP to ‘y’. Once enabled UBI evaluates the module parameter “fm_autoconvert”. If it is set to 1 (default is 0) UBI automatically enables fastmap for any attached image. This means UBI creates a new internal volume with the fastmap data such that next time the fast attach mode can be used.

In the default configuration UBI will use the information stored in this fastmap volume to accelerate the attach procedure. If you want to test fastmap, set fm_autoconvert to 1 and attach a volume.

Backwards compatibility

The fastmap on-disk data structure makes use of delete compatible volumes, therefore fastmap enabled images are fully backwards compatible with UBI implementaions which do not support fastmap. The kernel will remove the fastmap volumes and continue with scanning.
This includes not only v3.6- but also v3.7+ with this option disabled.

Technical design

A on-disk fastmap contains all information needed to attach the whole image, namely all erase counter values, a list of all PEBs and their state, a list of all volumes and their current EBA, … To avoid too much writes of the fastmap it contains also a list of PEBs which may have changed and need a full scan while attaching. This list is called “fastmap pool” and has a fixed sized, 5% of the total
amount of PEBs. Using this technique UBI needs to write the fastmap only if the pool contains no free PEBs. Otherwise it would have to write the fastmap each time when the EBA of a volume has changed.

A fastmap consists of a super block (also known as anchor PEB) and payload data which can life on any PEB. The anchor PEB has to be located within the first 64 PEBs on the MTD device. It contains pointers to the remaining PEBs which carry the actual fastmap
data. On modern NAND chips the whole fastmap fits into a single PEB. Hence, the anchor PEB points to itself. After loading the fastmap data, UBI attach information structure is created from it.

The attach process works as follows:

1. UBI tries to find the fastmap anchor PEB,
   if no anchor PEB was found UBI performs traditional full scan
2. It follows the pointers stored in the anchor PEB and reads
   the fastmap payload data
3. Then it performs a traditional scan only on PEBs in the pool
   instead of all PEBs

If UBI detects that the used fastmap is invalid or corrupted it automatically falls back to scanning mode and performsa full scan. Using a CRC32 checksum and consistency checks of the internal UBI structures UBI is able to detect whether a fastmap is invalid or not.

A fastmap is written to the devices each time the fastmap pool becomes full (no free PEBs are available), the volume layout changes or the image is detached. One may wonder why writing at detach time is needed. if UBI would not write a new fastmap at detach time all erase counter modifications since the last fastmap are lost.

Overhead

Is fastmap enabled UBI will reserve enough PEBs to carry two complete fastmaps. In practice on modern NAND chips two PEBs are reserved for fastmap.

There is also some runtime overhead, to guarantee that the new fastmap is valid and conistent UBI has to take care that all IO which would cause EBA changes are blocked while attaching. Depending on flash Chip this can take up to one second. Therefore, fastmap makes only sense on fast and large flash devices where a full scan takes too long. E.g. On 4GiB NAND chips a full scan takes several seconds whereas a fast attach needs less than one second.