Documentation/yaffs-0.3.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
   2 <HTML>
   3 <HEAD>
   4         <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1">
   5         <TITLE></TITLE>
   6         <META NAME="GENERATOR" CONTENT="StarOffice/5.2 (Linux)">
   7         <META NAME="AUTHOR" CONTENT=" ">
   8         <META NAME="CREATED" CONTENT="20011219;22024300">
   9         <META NAME="CHANGEDBY" CONTENT=" ">
  10         <META NAME="CHANGED" CONTENT="20020128;21063000">
  11 </HEAD>
  12 <BODY>
  13 <H1 ALIGN=CENTER>YAFFS (yet another Flash File System)</H1>
  14 <H4 ALIGN=LEFT>Version 0.3<BR>Charles Manning (and Wookey), December 2001</H4>
  15 <P ALIGN=LEFT><BR><BR>
  16 </P>
  17 <H2>Revision History</H2>
  18 <TABLE WIDTH=548 BORDER=1 CELLPADDING=4 CELLSPACING=3>
  19         <COL WIDTH=88>
  20         <COL WIDTH=72>
  21         <COL WIDTH=350>
  22         <THEAD>
  23                 <TR>
  24                         <TH WIDTH=88 VALIGN=TOP>
  25                                 <P ALIGN=LEFT STYLE="font-style: normal">V0.0</P>
  26                         </TH>
  27                         <TH WIDTH=72 VALIGN=BOTTOM SDVAL="37245" SDNUM="5129;0;D/MM/YY">
  28                                 <P ALIGN=LEFT STYLE="font-style: normal">20/12/01</P>
  29                         </TH>
  30                         <TH WIDTH=350 VALIGN=TOP>
  31                                 <P ALIGN=LEFT STYLE="font-style: normal">First draft</P>
  32                         </TH>
  33                 </TR>
  34         </THEAD>
  35         <TBODY>
  36                 <TR>
  37                         <TD WIDTH=88 VALIGN=TOP>
  38                                 <P ALIGN=LEFT STYLE="font-style: normal">V0.1</P>
  39                         </TD>
  40                         <TD WIDTH=72 VALIGN=BOTTOM SDVAL="37267" SDNUM="5129;0;D/MM/YY">
  41                                 <P ALIGN=LEFT STYLE="font-style: normal">11/01/02</P>
  42                         </TD>
  43                         <TD WIDTH=350 VALIGN=TOP>
  44                                 <P ALIGN=LEFT STYLE="font-style: normal">Minor corrections &amp;
  45                                 cosmetics.<BR>Change use of data status byte.</P>
  46                         </TD>
  47                 </TR>
  48                 <TR>
  49                         <TD WIDTH=88 VALIGN=TOP>
  50                                 <P ALIGN=LEFT STYLE="font-style: normal">V0.2</P>
  51                         </TD>
  52                         <TD WIDTH=72 VALIGN=BOTTOM SDVAL="37284" SDNUM="5129;0;D/MM/YY">
  53                                 <P ALIGN=RIGHT STYLE="font-style: normal">28/01/02</P>
  54                         </TD>
  55                         <TD WIDTH=350 VALIGN=TOP>
  56                                 <P ALIGN=LEFT STYLE="font-style: normal">Added observations about
  57                                 inodes, file headers and hard links.</P>
  58                         </TD>
  59                 </TR>
  60                 <TR>
  61                         <TD WIDTH=88 VALIGN=TOP>
  62                                 <P ALIGN=LEFT STYLE="font-style: normal">V0.3</P>
  63                         </TD>
  64                         <TD WIDTH=72 VALIGN=BOTTOM SDVAL="37285" SDNUM="5129;0;D/MM/YY">
  65                                 <P ALIGN=RIGHT STYLE="font-style: normal">26/02/02</P>
  66                         </TD>
  67                         <TD WIDTH=350 VALIGN=TOP>
  68                                 <P ALIGN=LEFT STYLE="font-style: normal">W:Added some general
  69                                 observations on compatibility, partitions and bootloading.</P>
  70                         </TD>
  71                 </TR>
  72         </TBODY>
  73 </TABLE>
  74 <P ALIGN=LEFT><BR><BR>
  75 </P>
  76 <H2>Scope</H2>
  77 <P>The purpose of this document is to outline a potential
  78 NAND-friendly file system for Linux.</P>
  79 <H2>Background</H2>
  80 <P>There are already various flash-file systems (FFSs) or block
  81 drivers for flash (on top of which a regular FS runs). There are pros
  82 and cons with all of these.
  83 </P>
  84 <P>Flash memory has quite a few constraints which will not be
  85 addressed here. Various approaches are available to work around these
  86 constraints to provide a file system. It is important to recognise
  87 that &quot;flash&quot; includes both NOR and NAND flash which have
  88 different sets of constraints. It is easy to be mislead by the
  89 generic term &quot;flash&quot; into thinking that approaches
  90 appropriate for NOR flash are immediately suitable for NAND flash.</P>
  91 <P>The NAND block drivers (eg. SmartMedia [currently not available
  92 for Linux] and DiskOnChip NFTL) typically use FAT16 as the file
  93 system. This isn't too robust and nor is it that flash-friendly.
  94 These block drivers provide a logical to physical mapping layer to
  95 emulate rewritable blocks that look like disk sectors. When used with
  96 FAT16, these file systems work reasonably well. They have a low
  97 memory footprint and scale well. Like all FAT based systems they are
  98 prone to corruption (&quot;lost clusters etc&quot;).</P>
  99 <P>The other approach is to design an entire file system which does
 100 not work through a block driver layer and is flash-friendly. This
 101 allows more scope to work around issues.</P>
 102 <P>Currently, two Linux file systems that support NOR flash very well
 103 are JFFS and its derivative JFFS2. Both of these are based on the
 104 principles of journaling (hence the leading J) which significantly
 105 increases robustness - a particularly important feature in embedded
 106 systems. Unfortunately neither of these file systems scale
 107 particularly well in both boot time and RAM usage. Scaling is
 108 particularly relevant when one considers that a 16MB NOR array would
 109 be considered large while a 128MB NAND is available as a single chip.</P>
 110 <P>JFFS requires a RAM-based jffs_node structure for each journalling
 111 node in the flash. Each of these nodes is 48 bytes. JFFS2 makes a
 112 significant improvement here by reducing the equivalent structure
 113 (jffs2_raw_node_ref) to 16 bytes. Still, at say an average node-size
 114 of 512 bytes, a 128MB NAND might need 250000 of these ... 4MB!</P>
 115 <P>Both JFFS and JFFS2 require scanning the flash array at boot time
 116 to find the journaling nodes and determine the file structures. Since
 117 NAND is large, slow, serially accessed and needs ECC this does not
 118 scale well and will take an unacceptably long boot time for the
 119 target systems. As a thumb-suck, the scanning of a 128MB NAND array
 120 might take approx 25 seconds.</P>
 121 <P>The intentions of the design sketched here are:</P>
 122 <UL>
 123         <LI><P>Be NAND-flash friendly.</P>
 124         <LI><P>Robustness through journaling strategies.</P>
 125         <LI><P>Significantly reduce the RAM overheads and boot times
 126         associated with JFFSx.</P>
 127 </UL>
 128 <p>This FS is intended primarily for internal NAND rather than removable NAND
 129 (SM cards). On removable SM cards Smartmedia compatibility is likely to be
 130 important so SM/FAT will normally be used, although of course YAFFS makes a
 131 lot of sense if reliability is more important than compatibility.</p>
 132
 133 <H2>Overview</H2>
 134 <P>Here follows a simplified overview of YAFFS.</P>
 135 <P>YAFFS uses a physical flash format similar to SmartMedia. This is
 136 done for various reasons:</P>
 137 <UL>
 138         <LI><P>Some of the formatting, eg placement of bad block markers is
 139         determined by the NAND manufacturers and can't be changed.</P>
 140         <LI><P>Potential to reuse code.</P>
 141         <LI><P>If it ain't broke don't fix.</P>
 142 </UL>
 143 <P>Some of the fields are obviously different to reflect the
 144 different usage. Despite the similarities YAFFS is not actually compatible
 145 with SM/FAT. SM cards need to be reformatted to switch from using SM/FAT to
 146 YAFFS or vice versa.</P>
 147 <P>File data is stored in fixed size &quot;chunks&quot; consistent
 148 with the size of a page (ie. 512 bytes). Each page is marked with a
 149 file id and chunk number. These tags are stored in the &quot;spare
 150 data&quot; region of the flash. The chunk number is determined by
 151 dividing the file position by the chunk size.</P>
 152 <P>When data in a file is overwritten, the relevant chunks are
 153 replaced by writing new pages to flash containing the new data but
 154 the same tags. The overwritten data is marked as &quot;discarded&quot;.
 155 </P>
 156 <P>File &quot;headers&quot; are stored as a single page, marked so as
 157 to be differentiated from data pages.</P>
 158 <P>Pages are also marked with a short (2 bit) serial number that
 159 increments each time the page at this position is incremented. The
 160 reason for this is that if power loss/crash/other act of demonic
 161 forces happens before the replaced page is marked as discarded, it is
 162 possible to have two pages with the same tags. The serial number is
 163 used to arbitrate.</P>
 164 <P>A block containing only discarded pages (termed a <I>dirty block</I>)
 165 is an obvious candidate for garbage collection. Otherwise valid pages
 166 can be copied off a block thus rendering the whole block discarded
 167 and ready for garbage collection.</P>
 168 <P>In theory you don't need to hold the file structure in RAM... you
 169 could just scan the whole flash looking for pages when you need them.
 170 In practice though you'd want better file access times than that! The
 171 mechanism proposed here is to have a list of __u16 page addresses
 172 associated with each file. Since there are 2<SUP>18</SUP> pages in a
 173 128MB NAND, a __u16 is insufficient to uniquely identify a page but
 174 is does identify a group of 4 pages - a small enough region to search
 175 exhaustively. This mechanism is clearly expandable to larger NAND
 176 devices - within reason. The RAM overhead with this approach is
 177 approx 2 bytes per page - 512kB of RAM for a whole 128MB NAND.</P>
 178 <P>Boot-time scanning to build the file structure lists should
 179 require just one pass reading NAND. Since only the the spare data
 180 needs to be read, this should be relatively fast ( approx 3 seconds
 181 for 128MB). Improvements can be achieved by partitioning the NAND.
 182 ie. mount the critical partition first then mount the data partition
 183 afterwards.</P>
 184 <P>Various runtime improvements can be achieved by changing the
 185 &quot;chunk size&quot; to 1024 bytes or more. However this would
 186 likely reduce flash efficiency. As always, life is a compromise....</P>
 187 <P><BR><BR>
 188 </P>
 189 <H3>Spare area details</H3>
 190 <P>The following table summarizes the layout of the spare area of
 191 each page.</P>
 192 <TABLE WIDTH=674 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 193         <COL WIDTH=96>
 194         <COL WIDTH=249>
 195         <COL WIDTH=291>
 196         <THEAD>
 197                 <TR VALIGN=TOP>
 198                         <TH WIDTH=96>
 199                                 <P>Byte #</P>
 200                         </TH>
 201                         <TH WIDTH=249>
 202                                 <P>SmartMedia usage</P>
 203                         </TH>
 204                         <TH WIDTH=291>
 205                                 <P>YAFFS usage</P>
 206                         </TH>
 207                 </TR>
 208         </THEAD>
 209         <TBODY>
 210                 <TR VALIGN=TOP>
 211                         <TD WIDTH=96>
 212                                 <P>0..511</P>
 213                         </TD>
 214                         <TD WIDTH=249>
 215                                 <P>Data</P>
 216                         </TD>
 217                         <TD WIDTH=291>
 218                                 <P>Data. either file data or file header depending on tags</P>
 219                         </TD>
 220                 </TR>
 221                 <TR VALIGN=TOP>
 222                         <TD WIDTH=96>
 223                                 <P>512..515</P>
 224                         </TD>
 225                         <TD WIDTH=249>
 226                                 <P>Reserved</P>
 227                         </TD>
 228                         <TD WIDTH=291>
 229                                 <P>Tags</P>
 230                         </TD>
 231                 </TR>
 232                 <TR>
 233                         <TD WIDTH=96 VALIGN=BOTTOM SDVAL="516" SDNUM="5129;">
 234                                 <P ALIGN=RIGHT>516</P>
 235                         </TD>
 236                         <TD WIDTH=249 VALIGN=TOP>
 237                                 <P>Data status byte. Not used in SM code from Samsung</P>
 238                         </TD>
 239                         <TD WIDTH=291 VALIGN=TOP>
 240                                 <P>Data status byte. If more than 4 bits are zero, then this page
 241                                 is discarded.</P>
 242                         </TD>
 243                 </TR>
 244                 <TR>
 245                         <TD WIDTH=96 VALIGN=BOTTOM SDVAL="517" SDNUM="5129;">
 246                                 <P ALIGN=RIGHT>517</P>
 247                         </TD>
 248                         <TD WIDTH=249 VALIGN=TOP>
 249                                 <P>Block status byte</P>
 250                         </TD>
 251                         <TD WIDTH=291 VALIGN=TOP>
 252                                 <P>Block status byte</P>
 253                         </TD>
 254                 </TR>
 255                 <TR VALIGN=TOP>
 256                         <TD WIDTH=96>
 257                                 <P ALIGN=LEFT>518..519</P>
 258                         </TD>
 259                         <TD WIDTH=249>
 260                                 <P>Block address</P>
 261                         </TD>
 262                         <TD WIDTH=291>
 263                                 <P>Tags</P>
 264                         </TD>
 265                 </TR>
 266                 <TR VALIGN=TOP>
 267                         <TD WIDTH=96>
 268                                 <P ALIGN=LEFT>520..522</P>
 269                         </TD>
 270                         <TD WIDTH=249>
 271                                 <P>ECC on second 256 bytes part of data</P>
 272                         </TD>
 273                         <TD WIDTH=291>
 274                                 <P>ECC on second 256 bytes of data</P>
 275                         </TD>
 276                 </TR>
 277                 <TR VALIGN=TOP>
 278                         <TD WIDTH=96>
 279                                 <P ALIGN=LEFT>523..524</P>
 280                         </TD>
 281                         <TD WIDTH=249>
 282                                 <P>Block address</P>
 283                         </TD>
 284                         <TD WIDTH=291>
 285                                 <P>Tags</P>
 286                         </TD>
 287                 </TR>
 288                 <TR VALIGN=TOP>
 289                         <TD WIDTH=96>
 290                                 <P ALIGN=LEFT>525..527</P>
 291                         </TD>
 292                         <TD WIDTH=249>
 293                                 <P>ECC on first 256 bytes part of data</P>
 294                         </TD>
 295                         <TD WIDTH=291>
 296                                 <P>ECC on first 256 bytes part of data</P>
 297                         </TD>
 298                 </TR>
 299         </TBODY>
 300 </TABLE>
 301 <P><BR><BR>
 302 </P>
 303 <P>The block status is a reserved value that shows whether the block
 304 is damaged.</P>
 305 <P>The data status tracks whether the page is valid. If less than 4
 306 bits are zero, then the page is valid otherwise it is discarded.</P>
 307 <P>There are 8 bytes (64 bits) for use by YAFFS tags. This is
 308 partitioned as follows:</P>
 309 <TABLE WIDTH=596 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 310         <COL WIDTH=146>
 311         <COL WIDTH=423>
 312         <THEAD>
 313                 <TR VALIGN=TOP>
 314                         <TH WIDTH=146>
 315                                 <P>Number of bits</P>
 316                         </TH>
 317                         <TH WIDTH=423>
 318                                 <P>Usage</P>
 319                         </TH>
 320                 </TR>
 321         </THEAD>
 322         <TBODY>
 323                 <TR>
 324                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="18" SDNUM="5129;">
 325                                 <P ALIGN=RIGHT>18</P>
 326                         </TD>
 327                         <TD WIDTH=423 VALIGN=TOP>
 328                                 <P>18-bit file id. ie. Limit of 2<SUP>18</SUP> (over 260000)
 329                                 files. File id 0 is not valid and indicates a deleted page. File
 330                                 Id 0x3FFFF i is also not valid.</P>
 331                         </TD>
 332                 </TR>
 333                 <TR>
 334                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
 335                                 <P ALIGN=RIGHT>2</P>
 336                         </TD>
 337                         <TD WIDTH=423 VALIGN=TOP>
 338                                 <P ALIGN=LEFT>2-bit serial number.</P>
 339                         </TD>
 340                 </TR>
 341                 <TR>
 342                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="20" SDNUM="5129;">
 343                                 <P ALIGN=RIGHT>20</P>
 344                         </TD>
 345                         <TD WIDTH=423 VALIGN=TOP>
 346                                 <P>20-bit page id within file. Limit of 2<SUP>20</SUP> pages per
 347                                 file. ie. over 500MB file max size. Page id 0 means the file
 348                                 header for this file.</P>
 349                         </TD>
 350                 </TR>
 351                 <TR>
 352                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
 353                                 <P ALIGN=RIGHT>10</P>
 354                         </TD>
 355                         <TD WIDTH=423 VALIGN=TOP>
 356                                 <P>10-bit counter of the number of bytes used in the page.</P>
 357                         </TD>
 358                 </TR>
 359                 <TR>
 360                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="12" SDNUM="5129;">
 361                                 <P ALIGN=RIGHT>12</P>
 362                         </TD>
 363                         <TD WIDTH=423 VALIGN=TOP>
 364                                 <P>12-bit ECC on tags.</P>
 365                         </TD>
 366                 </TR>
 367                 <TR>
 368                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
 369                                 <P ALIGN=RIGHT>2</P>
 370                         </TD>
 371                         <TD WIDTH=423 VALIGN=TOP>
 372                                 <P>Unused. Keep as 1.</P>
 373                         </TD>
 374                 </TR>
 375                 <TR>
 376                         <TD WIDTH=146 VALIGN=BOTTOM SDVAL="64" SDNUM="5129;">
 377                                 <P ALIGN=RIGHT><B>64</B></P>
 378                         </TD>
 379                         <TD WIDTH=423 VALIGN=TOP>
 380                                 <P><B>Total</B></P>
 381                         </TD>
 382                 </TR>
 383         </TBODY>
 384 </TABLE>
 385 <P><BR><BR>
 386 </P>
 387 <P>A bit of explanation on the usage of some of these fields:</P>
 388 <P>file Id is synonymous with inode.</P>
 389 <P>The serial number is incremented each time a page with the same
 390 file_id:page_id is rewritten (because of data changes or copy during
 391 garbage collection). When a page is replaced, there is a brief period
 392 during which there are two pages with the same id. The serial number
 393 resolves this. Since there should never be a difference of less than
 394 more than one, a two-bit counter is sufficient to determine which is
 395 the current page.</P>
 396 <P>When the page is rewritten, the file id, these data status byte
 397 and the 12-bit ECC are all written to zero.</P>
 398 <P>The byte counter indicates how many bytes are valid in this page.
 399 Since the page would not exist if it contains zero bytes, this field
 400 should thus hold 512 for all pages except the last page in the file.
 401 The use of counters means that the file length integrity is preserved
 402 while the file is open without having to constantly update the file
 403 length in the file header. The file header only needs to be refreshed
 404 when the file is closed (rather than whenever it is appended to).
 405 This field is wide enough to allow expansion to 1024-byte &quot;chunks&quot;.</P>
 406 <P>File &quot;headers&quot; come in two flavours:</P>
 407 <UL>
 408         <LI><P>file info ( the mode, ower id, group id, length,...)</P>
 409         <LI><P>the hard link(s) that refers to the file.</P>
 410 </UL>
 411 <P>A directory also appears as a file (ie. has an inode and hard
 412 link(s)) but has no data.</P>
 413 <P>The 12-bit ECC applies to only the tag data uses a similar
 414 algorithm to the 22-bit ECCs used for file system data. They are kept
 415 independent.</P>
 416 <H3>RAM data details</H3>
 417 <P>Block management details are reasonably obvious and, I feel, don't
 418 need to be addressed here apart from stating that there will be a
 419 structure to track block status (eg. number of pages in use, failed
 420 blocks, and which are candidates for garbage collection etc).</P>
 421 <P>The files need an indexing structure of sorts to locate and track
 422 the pages in the file. Some sort of tree structure should work rather
 423 well. The look-up needs to be quite efficient in both CPU time and
 424 space.</P>
 425 <H3>Page allocation and garbage collection</H3>
 426 <P>Pages are allocated sequentially from the currently selected
 427 block. When all the pages in the block are filled, another clean
 428 block is selected for allocation. At least two or three clean blocks
 429 are reserved for garbage collection purposes. If there are
 430 insufficient clean blocks available, then a dirty block ( ie one
 431 containing only discarded pages) is erased to free it up as a clean
 432 block. If no dirty blocks are available, then the dirtiest block is
 433 selected for garbage collection.</P>
 434 <P>Garbage collection is performed by copying the valid data pages
 435 into new data pages thus rendering all the pages in this block dirty
 436 and freeing it up for erasure. I also like the idea of selecting a
 437 block at random some small percentage of the time - thus reducing the
 438 chance of wear differences.</P>
 439 <P>Relative to NOR, NAND writes and erases very fast. Therefore
 440 garbage collection might be performed on-demand (eg. during a write)
 441 without significant degradation in performance. Alternatively garbage
 442 collection might be delegated to a kernel tasklet.</P>
 443 <P>Relative to JFFSx, the garbage collection presented here is
 444 incredibly simple - thanks mainly to the use of fixed-size pages
 445 instead of journaling nodes.</P>
 446 <H3>Flash writing</H3>
 447 <P>As presented here, YAFFS only writes to the page's data area once
 448 and to the spare area twice (once when new page is written and once when it
 449 gets stomped on) before an erasure. This is within the limits of the most
 450 restrictive NAND flashes.</P>
 451
 452 <H3>Wear leveling</H3>
 453 <P>No wear leveling is explicitly used here. Instead we rely on two
 454 &quot;strategies&quot;:</P>
 455 <UL>
 456         <LI><P>Reserving some blocks to cater for failure. You need to do
 457         this anyway with NAND. The main purpose behind wear leveling is to
 458         prevent some blocks getting more wear and failing. Since we expect,
 459         and handle, failure this is no longer as important.</P>
 460         <LI><P>The infrequent random block selection should prevent low-wear
 461         blocks getting &quot;stuck&quot;.</P>
 462 </UL>
 463 <h3>Partitioning</h3>
 464 <p> Partitioning is not included in this spec, but could be added if
 465 required.</p>
 466 <h3>Bootloading</h3>
 467 <p>Bootloaders cannot just read files direct from NAND due to the high
 468 probability of bad blocks. Because YAFFS is quite simple it will be
 469 relatively straightforward for bootloaders to read from it (eg reading a
 470 kernel).</p>
 471
 472 <H3>Conclusion</H3>
 473 <P>YAFFS is very simple. It is also NAND-friendly, is relatively
 474 frugal with resources (especially RAM) and boots quickly. Like JFFSx
 475 it has journaling which makes it far more robust than FAT.</P>
 476 <P>While it might seem high-risk to develop YAFFS, it is probably
 477 about the same amount of effort as implementing changes to JFFS to
 478 get it to work effectively within the constraints of NAND. A
 479 resulting JFFSx system would still require significant amounts of RAM
 480 and have long boot times.</P>
 481 <P>While YAFFS is indeed a new file system internally, much of the
 482 file system glue code (including inode management, link management
 483 etc) can likely be stolen from JFFSx.
 484 </P>
 485 <P><BR><BR>
 486 </P>
 487 <P><BR><BR>
 488 </P>
 489 <P><BR><BR>
 490 </P>
 491 <P><BR><BR>
 492 </P>
 493 <P><BR><BR>
 494 </P>
 495 <P><BR><BR>
 496 </P>
 497 <P><BR><BR>
 498 </P>
 499 <P><BR><BR>
 500 </P>
 501 <P><BR><BR>
 502 </P>
 503 </BODY>
 504 </HTML>