UFFS code repo moving to Git

I've moved the source code repo to Git, you can clone git repo from:

git://uffs.git.sourceforge.net/gitroot/uffs

The main reason moving to git is that it's fast and easier for cooperative development.

If you want to contribute codes to UFFS project but don't have a sourceforge account or prefer somewhere else like github to store your codes, you can clone a UFFS repo, publish your repo and I'll pull from you :-)

If you subscribe to this feed, you may find that there are A LOT commits recently :-)





The tasks of UFFS v1.3

The tasks of next UFFS minor version(v1.3) would be:

* New API:

int uffs_SkipObject(uffs_Object *obj, int size);

This function will make the file object skip "size" bytes from head, return bytes have been skipped. It's not a POSIX standard api, but it would be very useful when using the file as FIFO. For example, when recording streaming video to a file, it allows to skip the earliest content and keep recording when flash become full.

* Introduce buffer group

Use grouped buffers to cache data across blocks. This will avoid performance penalty when opening multiple files for write.

* Interface to Linux MTD

This interface allows to use mtd device as low level flash driver on linux. It's not implies that you can use file operation APIs from libc to access UFFS file system. You still use uffs_xxx APIs, UFFS as a library linked to your application, running on user space not kernel space.

One may ask why not just use YAFFS2 or JFFS2 ? Well, the new introduced "uffs_SkipObject" API may be one of the reason, it can't be implemented effetively on top of POSIX api.

UFFS usage guidline

UFFS is not a generic file system for every day use like FAT32 or Ext3, or generic flash file system like JFFS2 or YAFFS2 for NAND.

The fact that UFFS consumes one block for each directory and one or more blocks for each file makes it not suitable for large numbers of directories or files.

Not using separate thread for GC makes UFFS very predictable (good for read-time system), but it may also beat performance badly if you randomly moving file pointer across block boundary and modifying the file content.

What UFFS best suit for:

* Not many directories.
Too many directories will cause in low space efficiency but no performance penalty. In fact, many embedded system don't use directory. (UFFS2 will fix this by allowing multiple directories on one block)

* Not many small files.
Full of small files will also cause low space efficiency. (UFFS2 will fix this by allowing multiple files on one block)

* Large file size.
UFFS performs well when reading/seeking/writing/appending in large size file.

* Appending a file.
UFFS has the best performence if you are appending a file, or doing the modifies within the last block boundary.

* Random reading.
Seeking file pointer is very fast in UFFS.

What should you minimize or avoid:

* Creating and deleting files frequently.
Create a file then delete it results in erasing 2 blocks, which is not a good practice for NAND flash if doing that frequently.

* Moving file pointer across block boundary and modifying the file content.
UFFS won't cache the data across block boundary when writing to a file, so it need to do the block recover immeditly (which will erase one block). This may beat the performance badly.

For example, if you have a size 1MB file, seek the file pointer to 0, write 1 byte, then seek the pointer to 1MB(the end of file), write 1 byte, then close file. The whole process will cause 2 block recoveries, as result, 2 blocks will be erased.

* Opening multiple files for write.
The fact that UFFS can't cache the data across block baundary and files are in different blocks, opening multiple files and writing to them will make UFFS frequetly flush out the cache and cause bock recovery.

* Truncating/Deleting large size file.
When deleting a file, UFFS will erase all blocks belong to the file, which may take quite a long time for large file on slow NAND flash. Truncating a file will also cause erasing the discarded blocks.

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.

TIME COST:
(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.

Build simulator on Windows (Visual Studio)

UFFS (>1.2.0) source code tree structure:

.
|-- doc
`-- src
|-- emu ---> NAND flash simulation, helper codes.
|-- example ---> Example codes
|-- inc
| `-- uffs
|-- uffs ---> UFFS core sources
`-- utils ---> simulator utility

From v1.2.0, UFFS use 'cmake' to generate Makefiles or project files for compile the simulator.

'cmake' can be downloaded from here: http://www.cmake.org/cmake/resources/software.html

When installing 'cmake', choose "Add cmake to System PATH".

Check out UFFS source codes from SF.net:

  svn co https://uffs.svn.sourceforge.net/svnroot/uffs/trunk uffs-trunk

Create a 'build' dir along with uffs-trunk:


Enter 'build' dir, and run "cmake ..\uffs-trunk" to create project files:


(Make sure that your cl.exe is in PATH).

Cmake will generate project files for you:



Now, you can open "uffs.dsw" with Visual Studio:



Set "mkuffs" project as active project, then compile/run it.

UFFS2 features

UFFS2 is under design. Compares to UFFS1, UFFS2 will have new features/improvements:

1) Reduce memory footprint by using smaller tree node data structure, save 20%~50% memory comparing with UFFS1.

typedef struct uffs_HeadNodeSt {
  u16 block;
  u16 info;     //point to info node
  u16 next;
  u16 prev;
} uffs_LoadNode;

typedef struct uffs_InfoNodeSt {
  u16 father;
  u16 serial;
  u16 sum;
  u8 attr:2;      //00 dir, 01 normal file, 10 symbol link, 11 reserved
  u8 status:2;    //data status:
  u8 pageid;
} uffs_InfoNode;

typedef struct uffs_FreeNodeSt {
  u16 block;
  u16 next;
  u16 prev;
} uffs_FreeNode;

typedef struct uffs_DataNodeSt {
  u16 block;
  u16 father;
  u16 serial;
  u8  status; //0 - no free page, 1 - has free page
  u8  page;   //first free page
} uffs_DataNode;

typedef struct uffs_TreeNodeSt {
  union {
     struct uffs_HeadNodeSt head;
     struct uffs_DataNodeSt data;
     struct uffs_FreeNodeSt free;
  } u;
} TreeNode;

Tree nodes memory cost:
total_blocks * 8 + max_files_and_dirs * 8

e.g.:
for 1Gb NAND flash:
page sze: 512,
pages_per_block: 32,
total_blocks: 8192,
max_files_and_dirs: 1000

tree nodes memory cost: 8192 * 8 + 1000 * 8 = 72KB
(compares to UFFS1: 8192 * 16 = 131KB, save 45%)

2) Allow multiple files/dirs on one block. This will significantly improve flash space efficiency in many circumstances.

Directories and symbol link will only cost one page, small file cost 2~pages_per_block pages, configurable. Large files will use full block.

3) Move ECC to page spare.
ECC data are compatible with YAFFS2.

4) Support Linux VFS interface. This will allow using UFFS2 as file system in embedded linux.
UFFS2 can be used as root file system.