README-linux 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. Welcome to YAFFS, the first file system developed specifically for NAND flash.
  2. It is now YAFFS2 - original YAFFS (AYFFS1) only supports 512-byte page
  3. NAND and is now deprectated. YAFFS2 supports 512b page in 'YAFFS1
  4. compatibility' mode (CONFIG_YAFFS_YAFFS1) and 2K or larger page NAND
  5. in YAFFS2 mode (CONFIG_YAFFS_YAFFS2).
  6. A note on licencing
  7. -------------------
  8. YAFFS is available under the GPL and via alternative licensing
  9. arrangements with Aleph One. If you're using YAFFS as a Linux kernel
  10. file system then it will be under the GPL. For use in other situations
  11. you should discuss licensing issues with Aleph One.
  12. Terminology
  13. -----------
  14. Page - NAND addressable unit (normally 512b or 2Kbyte size) - can
  15. be read, written, marked bad. Has associated OOB.
  16. Block - Eraseable unit. 64 Pages. (128K on 2K NAND, 32K on 512b NAND)
  17. OOB - 'spare area' of each page for ECC, bad block marked and YAFFS
  18. tags. 16 bytes per 512b - 64 bytes for 2K page size.
  19. Chunk - Basic YAFFS addressable unit. Same size as Page.
  20. Object - YAFFS Object: File, Directory, Link, Device etc.
  21. YAFFS design
  22. ------------
  23. YAFFS is a log-structured filesystem. It is designed particularly for
  24. NAND (as opposed to NOR) flash, to be flash-friendly, robust due to
  25. journalling, and to have low RAM and boot time overheads. File data is
  26. stored in 'chunks'. Chunks are the same size as NAND pages. Each page
  27. is marked with file id and chunk number. These marking 'tags' are
  28. stored in the OOB (or 'spare') region of the flash. The chunk number
  29. is determined by dividing the file position by the chunk size. Each
  30. chunk has a number of valid bytes, which equals the page size for all
  31. except the last chunk in a file.
  32. File 'headers' are stored as the first page in a file, marked as a
  33. different type to data pages. The same mechanism is used to store
  34. directories, device files, links etc. The first page describes which
  35. type of object it is.
  36. YAFFS2 never re-writes a page, because the spec of NAND chips does not
  37. allow it. (YAFFS1 used to mark a block 'deleted' in the OOB). Deletion
  38. is managed by moving deleted objects to the special, hidden 'unlinked'
  39. directory. These records are preserved until all the pages containing
  40. the object have been erased (We know when this happen by keeping a
  41. count of chunks remaining on the system for each object - when it
  42. reaches zero the object really is gone).
  43. When data in a file is overwritten, the relevant chunks are replaced
  44. by writing new pages to flash containing the new data but the same
  45. tags.
  46. Pages are also marked with a short (2 bit) serial number that
  47. increments each time the page at this position is incremented. The
  48. reason for this is that if power loss/crash/other act of demonic
  49. forces happens before the replaced page is marked as discarded, it is
  50. possible to have two pages with the same tags. The serial number is
  51. used to arbitrate.
  52. A block containing only discarded pages (termed a dirty block) is an
  53. obvious candidate for garbage collection. Otherwise valid pages can be
  54. copied off a block thus rendering the whole block discarded and ready
  55. for garbage collection.
  56. In theory you don't need to hold the file structure in RAM... you
  57. could just scan the whole flash looking for pages when you need them.
  58. In practice though you'd want better file access times than that! The
  59. mechanism proposed here is to have a list of __u16 page addresses
  60. associated with each file. Since there are 2^18 pages in a 128MB NAND,
  61. a __u16 is insufficient to uniquely identify a page but is does
  62. identify a group of 4 pages - a small enough region to search
  63. exhaustively. This mechanism is clearly expandable to larger NAND
  64. devices - within reason. The RAM overhead with this approach is approx
  65. 2 bytes per page - 512kB of RAM for a whole 128MB NAND.
  66. Boot-time scanning to build the file structure lists only requires
  67. one pass reading NAND. If proper shutdowns happen the current RAM
  68. summary of the filesystem status is saved to flash, called
  69. 'checkpointing'. This saves re-scanning the flash on startup, and gives
  70. huge boot/mount time savings.
  71. YAFFS regenerates its state by 'replaying the tape' - i.e. by
  72. scanning the chunks in their allocation order (i.e. block sequence ID
  73. order), which is usually different form the media block order. Each
  74. block is still only read once - starting from the end of the media and
  75. working back.
  76. YAFFS tags in YAFFS1 mode:
  77. 18-bit Object ID (2^18 files, i.e. > 260,000 files). File id 0- is not
  78. valid and indicates a deleted page. File od 0x3ffff is also not valid.
  79. Synonymous with inode.
  80. 2-bit serial number
  81. 20-bit Chunk ID within file. Limit of 2^20 chunks/pages per file (i.e.
  82. > 500MB max file size). Chunk ID 0 is the file header for the file.
  83. 10-bit counter of the number of bytes used in the page.
  84. 12 bit ECC on tags
  85. YAFFS tags in YAFFS2 mode:
  86. 4 bytes 32-bit chunk ID
  87. 4 bytes 32-bit object ID
  88. 2 bytes Number of data bytes in this chunk
  89. 4 bytes Sequence number for this block
  90. 3 bytes ECC on tags
  91. 12 bytes ECC on data (3 bytes per 256 bytes of data)
  92. Page allocation and garbage collection
  93. Pages are allocated sequentially from the currently selected block.
  94. When all the pages in the block are filled, another clean block is
  95. selected for allocation. At least two or three clean blocks are
  96. reserved for garbage collection purposes. If there are insufficient
  97. clean blocks available, then a dirty block ( ie one containing only
  98. discarded pages) is erased to free it up as a clean block. If no dirty
  99. blocks are available, then the dirtiest block is selected for garbage
  100. collection.
  101. Garbage collection is performed by copying the valid data pages into
  102. new data pages thus rendering all the pages in this block dirty and
  103. freeing it up for erasure. I also like the idea of selecting a block
  104. at random some small percentage of the time - thus reducing the chance
  105. of wear differences.
  106. YAFFS is single-threaded. Garbage-collection is done as a parasitic
  107. task of writing data. So each time some data is written, a bit of
  108. pending garbage collection is done. More pages are garbage-collected
  109. when free space is tight.
  110. Flash writing
  111. YAFFS only ever writes each page once, complying with the requirements
  112. of the most restricitve NAND devices.
  113. Wear levelling
  114. This comes as a side-effect of the block-allocation strategy. Data is
  115. always written on the next free block, so they are all used equally.
  116. Blocks containing data that is written but never erased will not get
  117. back into the free list, so wear is levelled over only blocks which
  118. are free or become free, not blocks which never change.
  119. Some helpful info
  120. -----------------
  121. Formatting a YAFFS device is simply done by erasing it.
  122. Making an initial filesystem can be tricky because YAFFS uses the OOB
  123. and thus the bytes that get written depend on the YAFFS data (tags),
  124. and the ECC bytes and bad block markers which are dictated by the
  125. hardware and/or the MTD subsystem. The data layout also depends on the
  126. device page size (512b or 2K). Because YAFFS is only responsible for
  127. some of the OOB data, generating a filesystem offline requires
  128. detailed knowledge of what the other parts (MTD and NAND
  129. driver/hardware) are going to do.
  130. To make a YAFFS filesystem you have 3 options:
  131. 1) Boot the system with an empty NAND device mounted as YAFFS and copy
  132. stuff on.
  133. 2) Make a filesystem image offline, then boot the system and use
  134. MTDutils to write an image to flash.
  135. 3) Make a filesystem image offline and use some tool like a bootloader to
  136. write it to flash.
  137. Option 1 avoids a lot of issues because all the parts
  138. (YAFFS/MTD/hardware) all take care of their own bits and (if you have
  139. put things together properly) it will 'just work'. YAFFS just needs to
  140. know how many bytes of the OOB it can use. However sometimes it is not
  141. practical.
  142. Option 2 lets MTD/hardware take care of the ECC so the filesystem
  143. image just had to know which bytes to use for YAFFS Tags.
  144. Option 3 is hardest as the image creator needs to know exactly what
  145. ECC bytes, endianness and algorithm to use as well as which bytes are
  146. available to YAFFS.
  147. mkyaffs2image creates an image suitable for option 3 for the
  148. particular case of yaffs2 on 2K page NAND with default MTD layout.
  149. mkyaffsimage creates an equivalent image for 512b page NAND (i.e.
  150. yaffs1 format).
  151. Bootloaders
  152. -----------
  153. A bootloader using YAFFS needs to know how MTD is laying out the OOB
  154. so that it can skip bad blocks.
  155. YAFFS Tracing
  156. -------------