README-linux

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