Tuesday, April 21, 2009

UFFS mounting process

One of the most important feature of UFFS is that it can boot up very fast.How fast is it ? Typically, mounting a full loaded 1Gb(with 8192 blocks, page size 512) NAND flash cost less than 1 seconds on ARM7 CPU.

Mounting a UFFS partition needs three steps:

* Step one: scan the NAND flash
On this step, UFFS will read the first page spare of every block, which tells the block attribute one of:
* Marked bad block
* Erased(free) block
* Dir block
* File block
* File data block

UFFS will build a in-memory tree during this step, every block will be classified into the hashed tree nodes.

When a file or file data block is scanned, it also need to read one (for full loaded file block) or all (for half-loaded file block) spares on this block to obtain the data length of this block.

It also search the tree nodes to find if the block is an unclean block (If the system is power off during writing to a block, then it could result two blocks having the same serial number, one of them is unclean block). If an unclean block is found, UFFS will check the timestamps and erase the unclean block.

(reading 1 spare) x (total_blocks + total-file-data-blocks - 1) +
(reading 1 to pages_per_blocks - 1 spare) x total-files +
(1 tree scan) x non-free-blocks +
(erasing block) x (0 or 1)

* Step two: randomize the start point of erased blocks list.

In order to implement ware-leveling across power recycle, UFFS randomly choose a start point for erased block list.
The time cost depends on the random number generation method, it should be very fast for most system.

* Step three: process the orphan nodes.

In this step, UFFS will scan the file data nodes in tree, find the orphan nodes(which can be produced when power lost in the middle of deleting/truncating a file) and erase it.

TIME COST: (1 tree scan) * file-data-blocks

* Summary:

The total time cost when mounting an UFFS partition is:

(reading 1 spare) x (total_blocks + total-file-data-blocks - 1) +
(reading 1 to pages_per_blocks - 1 spare) x total-files +
(1 tree scan) x (non-free-blocks + file-data-blocks)

* For unclean power off, it may need to erase 1 block when mounting.
* The in-memory tree is a hash tree with key composed from serial number, so scan the tree with a given serial number is very fast.

No comments:

Post a Comment