Welcome to YAFFS, the first file system developed specifically for NAND flash.It is now YAFFS2 - original YAFFS (AYFFS1) only supports 512-byte pageNAND and is now deprecated. YAFFS2 supports 512b page in 'YAFFS1compatibility' mode (CONFIG_YAFFS_YAFFS1) and 2K or larger page NANDin YAFFS2 mode (CONFIG_YAFFS_YAFFS2).A note on licencing-------------------YAFFS is available under the GPL and via alternative licensingarrangements with Aleph One. If you're using YAFFS as a Linux kernelfile system then it will be under the GPL. For use in other situationsyou should discuss licensing issues with Aleph One.Terminology-----------Page -  NAND addressable unit (normally 512b or 2Kbyte size) - can        be read, written, marked bad. Has associated OOB.Block - Eraseable unit. 64 Pages. (128K on 2K NAND, 32K on 512b NAND)OOB -   'spare area' of each page for ECC, bad block marked and YAFFS        tags. 16 bytes per 512b - 64 bytes for 2K page size.Chunk - Basic YAFFS addressable unit. Same size as Page.Object - YAFFS Object: File, Directory, Link, Device etc.YAFFS design------------YAFFS is a log-structured filesystem. It is designed particularly forNAND (as opposed to NOR) flash, to be flash-friendly, robust due tojournalling, and to have low RAM and boot time overheads. File data isstored in 'chunks'. Chunks are the same size as NAND pages. Each pageis marked with file id and chunk number. These marking 'tags' arestored in the OOB (or 'spare') region of the flash. The chunk numberis determined by dividing the file position by the chunk size. Eachchunk has a number of valid bytes, which equals the page size for allexcept the last chunk in a file.File 'headers' are stored as the first page in a file, marked as adifferent type to data pages. The same mechanism is used to storedirectories, device files, links etc. The first page describes whichtype of object it is.YAFFS2 never re-writes a page, because the spec of NAND chips does notallow it. (YAFFS1 used to mark a block 'deleted' in the OOB). Deletionis managed by moving deleted objects to the special, hidden 'unlinked'directory. These records are preserved until all the pages containingthe object have been erased (We know when this happen by keeping acount of chunks remaining on the system for each object - when itreaches zero the object really is gone).When data in a file is overwritten, the relevant chunks are replacedby writing new pages to flash containing the new data but the sametags.Pages are also marked with a short (2 bit) serial number thatincrements each time the page at this position is incremented. Thereason for this is that if power loss/crash/other act of demonicforces happens before the replaced page is marked as discarded, it ispossible to have two pages with the same tags. The serial number isused to arbitrate.A block containing only discarded pages (termed a dirty block) is anobvious candidate for garbage collection. Otherwise valid pages can becopied off a block thus rendering the whole block discarded and readyfor garbage collection.In theory you don't need to hold the file structure in RAM... youcould just scan the whole flash looking for pages when you need them.In practice though you'd want better file access times than that! Themechanism proposed here is to have a list of __u16 page addressesassociated with each file. Since there are 2^18 pages in a 128MB NAND,a __u16 is insufficient to uniquely identify a page but is doesidentify a group of 4 pages - a small enough region to searchexhaustively. This mechanism is clearly expandable to larger NANDdevices - within reason. The RAM overhead with this approach is approx2 bytes per page - 512kB of RAM for a whole 128MB NAND.Boot-time scanning to build the file structure lists only requiresone pass reading NAND. If proper shutdowns happen the current RAMsummary of the filesystem status is saved to flash, called'checkpointing'. This saves re-scanning the flash on startup, and giveshuge boot/mount time savings.YAFFS regenerates its state by 'replaying the tape'  - i.e. byscanning the chunks in their allocation order (i.e. block sequence IDorder), which is usually different form the media block order. Eachblock is still only read once - starting from the end of the media andworking back.YAFFS tags in YAFFS1 mode:18-bit Object ID (2^18 files, i.e. > 260,000 files). File id 0- is not       valid and indicates a deleted page. File od 0x3ffff is also not valid.       Synonymous with inode.2-bit  serial number20-bit Chunk ID within file. Limit of 2^20 chunks/pages per file (i.e.       > 500MB max file size). Chunk ID 0 is the file header for the file.10-bit counter of the number of bytes used in the page.12 bit ECC on tagsYAFFS tags in YAFFS2 mode:  4 bytes 32-bit chunk ID  4 bytes 32-bit object ID  2 bytes Number of data bytes in this chunk  4 bytes Sequence number for this block  3 bytes ECC on tags 12 bytes ECC on data (3 bytes per 256 bytes of data)Page allocation and garbage collectionPages are allocated sequentially from the currently selected block.When all the pages in the block are filled, another clean block isselected for allocation. At least two or three clean blocks arereserved for garbage collection purposes. If there are insufficientclean blocks available, then a dirty block ( ie one containing onlydiscarded pages) is erased to free it up as a clean block. If no dirtyblocks are available, then the dirtiest block is selected for garbagecollection.Garbage collection is performed by copying the valid data pages intonew data pages thus rendering all the pages in this block dirty andfreeing it up for erasure. I also like the idea of selecting a blockat random some small percentage of the time - thus reducing the chanceof wear differences.YAFFS is single-threaded. Garbage-collection is done as a parasitictask of writing data. So each time some data is written, a bit ofpending garbage collection is done. More pages are garbage-collectedwhen free space is tight.Flash writingYAFFS only ever writes each page once, complying with the requirementsof the most restricitve NAND devices.Wear levellingThis comes as a side-effect of the block-allocation strategy. Data isalways written on the next free block, so they are all used equally.Blocks containing data that is written but never erased will not getback into the free list, so wear is levelled over only blocks whichare free or become free, not blocks which never change.Some helpful info-----------------Formatting a YAFFS device is simply done by erasing it.Making an initial filesystem can be tricky because YAFFS uses the OOBand thus the bytes that get written depend on the YAFFS data (tags),and the ECC bytes and bad block markers which are dictated by thehardware and/or the MTD subsystem. The data layout also depends on thedevice page size (512b or 2K). Because YAFFS is only responsible forsome of the OOB data, generating a filesystem offline requiresdetailed knowledge of what the other parts (MTD and NANDdriver/hardware) are going to do.To make a YAFFS filesystem you have 3 options:1) Boot the system with an empty NAND device mounted as YAFFS and copy   stuff on.2) Make a filesystem image offline, then boot the system and use   MTDutils to write an image to flash.3) Make a filesystem image offline and use some tool like a bootloader to   write it to flash.Option 1 avoids a lot of issues because all the parts(YAFFS/MTD/hardware) all take care of their own bits and (if you haveput things together properly) it will 'just work'. YAFFS just needs toknow how many bytes of the OOB it can use. However sometimes it is notpractical.Option 2 lets MTD/hardware take care of the ECC so the filesystemimage just had to know which bytes to use for YAFFS Tags.Option 3 is hardest as the image creator needs to know exactly whatECC bytes, endianness and algorithm to use as well as which bytes areavailable to YAFFS.mkyaffs2image creates an image suitable for option 3 for theparticular case of yaffs2 on 2K page NAND with default MTD layout.mkyaffsimage creates an equivalent image for 512b page NAND (i.e.yaffs1 format).Bootloaders-----------A bootloader using YAFFS needs to know how MTD is laying out the OOBso that it can skip bad blocks.YAFFS Tracing-------------