Mercurial > yaffs-ecoscentric
annotate README-linux @ 346:6750f63cd377
More test code
| author | charles |
|---|---|
| date | Mon, 09 Nov 2009 19:16:33 +0000 |
| parents | 239cfd4cf194 |
| children |
| rev | line source |
|---|---|
| 175 | 1 Welcome to YAFFS, the first file system developed specifically for NAND flash. |
| 2 | |
| 3 It is now YAFFS2 - original YAFFS (AYFFS1) only supports 512-byte page | |
| 206 | 4 NAND and is now deprecated. YAFFS2 supports 512b page in 'YAFFS1 |
| 175 | 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 ------------------- | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
11 YAFFS is available under the GPL and via alternative licensing |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
51 reaches zero the object really is gone). |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
55 tags. |
| 175 | 56 |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
57 Pages are also marked with a short (2 bit) serial number that |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
58 increments each time the page at this position is incremented. The |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
59 reason for this is that if power loss/crash/other act of demonic |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
60 forces happens before the replaced page is marked as discarded, it is |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
61 possible to have two pages with the same tags. The serial number is |
| 175 | 62 used to arbitrate. |
| 63 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
64 A block containing only discarded pages (termed a dirty block) is an |
| 175 | 65 obvious candidate for garbage collection. Otherwise valid pages can be |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
66 copied off a block thus rendering the whole block discarded and ready |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
67 for garbage collection. |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
68 |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
72 mechanism proposed here is to have a list of __u16 page addresses |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
80 Boot-time scanning to build the file structure lists only requires |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
84 huge boot/mount time savings. |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
90 working back. |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
112 Page allocation and garbage collection |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
113 |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
114 Pages are allocated sequentially from the currently selected block. |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
115 When all the pages in the block are filled, another clean block is |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
116 selected for allocation. At least two or three clean blocks are |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
117 reserved for garbage collection purposes. If there are insufficient |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
118 clean blocks available, then a dirty block ( ie one containing only |
| 175 | 119 discarded pages) is erased to free it up as a clean block. If no dirty |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
120 blocks are available, then the dirtiest block is selected for garbage |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
121 collection. |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
122 |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
123 Garbage collection is performed by copying the valid data pages into |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
124 new data pages thus rendering all the pages in this block dirty and |
|
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
125 freeing it up for erasure. I also like the idea of selecting a block |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
132 when free space is tight. |
| 175 | 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 | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
146 are free or become free, not blocks which never change. |
| 175 | 147 |
| 148 | |
| 149 | |
| 150 Some helpful info | |
| 151 ----------------- | |
| 152 | |
| 153 Formatting a YAFFS device is simply done by erasing it. | |
| 154 | |
| 155 Making an initial filesystem can be tricky because YAFFS uses the OOB | |
| 156 and thus the bytes that get written depend on the YAFFS data (tags), | |
| 157 and the ECC bytes and bad block markers which are dictated by the | |
| 158 hardware and/or the MTD subsystem. The data layout also depends on the | |
| 159 device page size (512b or 2K). Because YAFFS is only responsible for | |
| 160 some of the OOB data, generating a filesystem offline requires | |
| 161 detailed knowledge of what the other parts (MTD and NAND | |
| 162 driver/hardware) are going to do. | |
| 163 | |
| 164 To make a YAFFS filesystem you have 3 options: | |
| 165 | |
| 166 1) Boot the system with an empty NAND device mounted as YAFFS and copy | |
| 167 stuff on. | |
| 168 | |
| 169 2) Make a filesystem image offline, then boot the system and use | |
| 170 MTDutils to write an image to flash. | |
| 171 | |
| 172 3) Make a filesystem image offline and use some tool like a bootloader to | |
| 173 write it to flash. | |
| 174 | |
| 175 Option 1 avoids a lot of issues because all the parts | |
| 176 (YAFFS/MTD/hardware) all take care of their own bits and (if you have | |
| 177 put things together properly) it will 'just work'. YAFFS just needs to | |
| 178 know how many bytes of the OOB it can use. However sometimes it is not | |
| 179 practical. | |
| 180 | |
| 181 Option 2 lets MTD/hardware take care of the ECC so the filesystem | |
| 182 image just had to know which bytes to use for YAFFS Tags. | |
| 183 | |
| 184 Option 3 is hardest as the image creator needs to know exactly what | |
| 185 ECC bytes, endianness and algorithm to use as well as which bytes are | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
186 available to YAFFS. |
| 175 | 187 |
| 188 mkyaffs2image creates an image suitable for option 3 for the | |
| 189 particular case of yaffs2 on 2K page NAND with default MTD layout. | |
| 190 | |
| 191 mkyaffsimage creates an equivalent image for 512b page NAND (i.e. | |
| 192 yaffs1 format). | |
| 193 | |
| 194 Bootloaders | |
| 195 ----------- | |
| 196 | |
| 197 A bootloader using YAFFS needs to know how MTD is laying out the OOB | |
|
205
f95fdc6123fb
Cleanup patch - Remove all trailing whitespace and fix a few typos.
wookey
parents:
175
diff
changeset
|
198 so that it can skip bad blocks. |
| 175 | 199 |
| 200 YAFFS Tracing | |
| 201 ------------- |